Browse Prior Art Database

Efficient Re-assembly of Mbufs Into Clusters

IP.com Disclosure Number: IPCOM000123178D
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 101K

Publishing Venue

IBM

Related People

Madan, B: AUTHOR [+2]

Abstract

TCP/IP stack memory after a time may become highly fragmented. If we now want to send a large data-gram, we may encounter either inefficiency or failure, depending on the exact TCP/IP stack implementation. This is because a large enough contiguous memory may not be available due to fragmentation. This technical idea describes an efficient method to re-assemble small free fragments into large contiguous memory units.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient Re-assembly of Mbufs Into Clusters

   TCP/IP stack memory after a time may become highly
fragmented.  If we now want to send a large data-gram, we may
encounter either inefficiency or failure, depending on the exact
TCP/IP stack implementation.  This is because a large enough
contiguous memory may not be available due to fragmentation.  This
technical idea describes an efficient method to re-assemble small
free fragments into large contiguous memory units.

   Mbufs and clusters are the commonly used data structures
for a variety of dynamically allocated storage needs in the
implementation of the TCP/IP.  After their usage, mbufs and clusters
are dynamically freed and placed on their respective free lists.
Typically, mbufs have a size of 128 or 256 bytes and these are
obtained by dividing a cluster of size 2K or 4K bytes.  Clusters in
turn are obtained by dividing larger blocks (typically 64K bytes
segments) which are also dynamically allocated.  Now consider the
following situation wherein we send or receive a very large number of
small datagrams thus creating a very large number of mbufs over a
period time.  This may result in most of the available memory being
converted into mbufs.  After an interval of time, all these mbufs may
be freed and these will be placed on a linear linked list 'mfree',
inorder re-alllocated again.  At this stage if there is a need for
some clusters, the system will not be able to meet this request
despite a large amount of free memory being available in the form of
mbufs.  This scenario clearly highlights the need for re-assembling
free mbufs into free clusters.  Carrying this arguments to the next
logical step would highlight a similar need for re-assembling free
clusters into a 64K byte segment, if possible.

   This disclosure describes an efficient method for
performing this re-assembly of smaller and contiguous mbufs into
larger clusters which in turn can be re-assembled into a segment.
The method outlined here works by visiting each mbuf on the freelist
no more than once.  Hence the computational complexity of this method
is linear in the size of the 'mfree' list, i.e. O(N), where, N is the
size of the mfree list.

   Clusters and mbufs are created out of 64KB memory
segments.  At the time of initialization of the tcp/ip stack, we
acquire a certain number of these memory segments which are broken
down into clusters and mbufs.  In our design, all such segments are
linked together as a linked list.  The structure of these segments is
as shown in Fig.1.  Note that the last cluster in each segment is
used for maintaining the house-keeping
information.   Each element of the c_or_mbuf array is used as a
flag to indicate whether a particular cluster has been divided into
mbufs or not.  If it has been, then the mbufs lying in such...