Reassembly

This example shows how IP reassembles fragments that arrive over the network back into a complete datagram. One reason we give this particular piece of code is that it is representative of a large fraction of networking code---it does little more than tedious and unglamorous bookkeeping. In this case, the code has to keep track of what fragments have and have not arrived.

First, we define the key data structure ( FragList) that is used to hold the individual fragments that arrive at the destination. Incoming fragments are saved in this data structure until all the fragments in the original datagram have arrived, at which time they are reassembled into a complete datagram and passed up to some higher level protocol. Note that each element in FragList contains either a fragment or a hole.

#define FRAGOFFMASK      0x1fff
#define FRAGOFFSET(flag) ((fragflag) & FRAGOFFMASK)
#define INFINITE_OFFSET  0xffff

typedef struct fid {
    IpHost  source;
    IpHost  dest;
    u_char  prot;
    u_char  pad;
    u_short ident;
} FragId;

typedef struct hole {
    u_int first;
    u_int last;
} Hole;

#define HOLE  1
#define FRAG  2

typedef struct fragif {
    u_char type;
    union {
        Hole hole;
        Msg  frag;
    } u;
    struct fragif *next, *prev;
} FragInfo;

typedef struct FragList {
    u_short  nholes;
    FragInfo head;       /* dummy header node */
    Bind     binding;
    bool     gcMark;
} FragList;

The reassembly routine, ipReassemble, takes the session to which the datagram belongs ( s), an incoming datagram ( dg), and the IP header for that datagram ( hdr) as arguments. The final argument ( fragMap) is used to map the incoming datagram into appropriate FragList. (Recall that the group of fragments that are being reassembled together are uniquely identified by several fields in the IP header, as defined by structure FragId given above.)

The actual work done in ipReassemble is straightforward; as stated above, it is mostly bookkeeping. First, the routine extracts the fields from the IP header that uniquely identify the datagram being reassembled, constructs a key from these fields, and looks this key up in fragMap to find the appropriate FragList. Next, it inserts the new fragment into this FragList. This involves comparing the sum of the offset and length of this fragment with the offset of the next fragment in the list. Some of this work is done in subroutine hole_create, which is given below. Finally, ipReassemble checks to see if all the holes are filled. If all the fragments are present, it calls the x-kernel routine msgJoin to actually reassemble the fragments into a whole datagram and then calls xDemux to pass this datagram up the protocol graph.

static XkReturn
ipReassemble(Sessn s, Msg *dg, IpHdr *hdr, Map fragMap)
{
    FragId   fragid;
    FragList *list;
    FragInfo *fi, *prev;
    Hole     *hole;
    u_short  offset, len;

    /* extract fragmentation info from header and create id for this frag */
    offset = FRAGOFFSET(hdr->frag)*8;
    len = hdr->dlen - GET_HLEN(hdr) * 4;
    bzero((char *)&fragid, sizeof(FragId));
    fragid.source = hdr->source;
    fragid.dest   = hdr->dest;
    fragid.prot   = hdr->prot;
    fragid.ident  = hdr->ident;

    /* find reassembly list for this frag; create one if this none exists */
    if (mapResolve(fragMap, &fragid, (void **)&list) == XK_FAILURE) {
        list = X_NEW(FragList);
        list->binding = mapBind(fragMap, &fragid, list);

        /* initialize list with a single hole spanning the whole datagram */
        list->nholes     = 1;
        list->head.next  = fi = X_NEW(FragInfo);
        fi->next         = 0;
        fi->type         = HOLE;
        fi->u.hole.first = 0;
        fi->u.hole.last  = INFINITE_OFFSET;
    }
    list->gcMark = FALSE;

    prev = &list->head;
    for (fi = prev->next; fi != 0; prev = fi, fi = fi->next) {
        if (fi->type == FRAG)
            continue;
        hole = &fi->u.hole;
        if (offset < hole->last && offset + len > hole->first) {
            /* check to see if frag overlaps previously received frags */
            if (offset < hole->first) {
                /* truncate message from left */
                msgPop(dg, hole->first - offset);
                offset = hole->first;
            }
            if (offset + len > hole->last) {
                /* truncate message from right */
                msgTruncate(dg, hole->last - offset);
                len = hole->last - offset;
            }

            /* now check to see if new hole(s) need to be made */
            if (offset + len < hole->last && hdr->frag & MOREFRAGMENTS) {
                /* creating new hole above */
                hole_create(prev, fi, (offset+len), hole->last);
                list->nholes++;
            }
            if (offset > hole->first) {
                /* creating new hole below */
                hole_create(fi, fi->next, hole->first, (offset));
                list->nholes++;
            }

            /* change this FragInfo structure to be an FRAG */
            list->nholes--;
            fi->type = FRAG;
            msgConstructCopy(&fi->u.frag, dg);
            break;
        } /* if found a hole */
    } /* for loop */

    /* check to see if we're done, and if so, pass datagram up */
    if (list->nholes == 0)
    {
        Msg fullMsg;

        /* now have a full datagram */
        msgConstructEmpty(&fullMsg);
        for (fi = list->head.next; fi != 0; fi = fi->next)
            msgJoin(&fullMsg, &fi->u.frag, &fullMsg);
        mapRemoveBinding(fragMap, list->binding);
        ipFreeFragList(list);
        xDemux(xGetUp(s), s, &fullMsg);
        msgDestroy(&fullMsg);
    }
    return XK_SUCCESS;
}

Subroutine hole_create creates a new hole in the fragment list that begins at offset first and continues to offset last. It makes use of the x-kernel utility X_NEW, which creates an instance of the given structure.

static int
hole_create(FragInfo *prev, FragInfo *next, u_int first, u_int last)
{
    FragInfo *fi;

    /* creating new hole from first to last */
    fi = X_NEW(FragInfo);
    fi->type         = HOLE;
    fi->u.hole.first = first;
    fi->u.hole.last  = last;
    fi->next         = next;
    prev->next       = fi;
}

Finally, note that these routines do not capture the entire picture of reassembly. What is not shown is a background process (x-kernel event) that periodically checks to see if there has been any recent activity on this datagram (it looks at field gcMark), and if not, deletes the corresponding FragList. IP does not attempt to recover from the situation where one or more of the fragments does not arrive; it simply gives up and reclaims the memory that was being used for reassembly.