November 12, 2022

BSD TCP/IP for Kyu - Queues

In particular, I am interested in the insque and remque routines.

These are macros that call _insque and _remque. The VAX conveniently provided single instructions for these (apparently). On the m68k and sparc these were coded in assembly. On the i386 they were simply coded in straightforward C. I made some changes to it and produced the following:

The macros themselves are in sys/systm.h 

struct  llist {
        struct  llist *f_link;
        struct  llist *r_link;
};

void
_insque ( struct llist *element, struct llist *head)
{
        element->f_link = head->f_link;
        head->f_link = element;
        element->r_link = head;
        (element->f_link)->r_link = element;
}

void
_remque ( struct llist *element)
{
        (element->f_link)->r_link = element->r_link;
        (element->r_link)->f_link = element->f_link;
        // element->r_link = (struct llist *)0;
}
A peek at NetBSD-1.3 shows that they introduced macros with names like LIST_REMOVE, LIST_INSERT_HEAD, LIST_INSERT_AFTER.

Use in in_pcb.c

Here a list of protocol control blocks are kept with "tcb" being the head of the list. The routine pcb_alloc() adds blocks to the list and the routine in_pcbdetach() removes blocks from the list.

The following line initializes the queue: 

tcb.inp_next = tcb.inp_prev = &tcb;
This list is used in a variety of places, in particular tcp_input calls in_pcblookup() to scan the list for a matching entry. It begins with head and keeps going until it goes full circle to the head. A doubly linked list allows entries to be removed.

For code like that shown above to work, the inpcb structure must have the first two elements be links as follows: 

struct inpcb {
        struct  inpcb *inp_next,*inp_prev;

Use for the TCP reassembly queue

Here mbuf structures are being linked in a queue. The linking is done using the first two elements in a struct tcpiphdr -- which is within the mbuf itself. This is certainly some exciting coding, but apparently it works. Indeed, the first 2 elements of a tcpiphdr is like this: 
caddr_t ih_next, ih_prev;

The function "insque" is called from one place in tcp_input.c. The call is in tcp_reass() and is putting a segment on the reassembly queue.

The function "remque" is called from three places. Two are in tcp_input.c and one is in tcp_subr.c (in tcp_close()). The calls in tcp_input.c are both in tcp_reass() and deal with the reassembly queue. The call in tcp_close() cleans up the reassembly queue, removing and freeing any mbufs on it.

Have any comments? Questions? Drop me a line!

Kyu / tom@mmto.org