Title: acc_freelist / buf512_freelist / accessors[] , buffers512[]

While being processed by the network service, packets and configuration data are temporarily stored in buffers associated with struct's named "accessors". These accessors are chained together to form linked lists and can be manipulated by a number of functions. There are two linked lists of signifigance in buf.c: acc_freelist and buf512_freelist. After initialization, these linked lists are as follows:

where the elements of buffers512[] are of type buf512_t:

typedef struct buf512 

buf_t buf_header;
char buf_data[512]; /* the user data is found here */
} buf512_t

typedef struct buf
int buf_linkC;
buffree_t buf_free;
size_t buf_size;
char *buf_data_p;
} buf_t;
and the elements of accessors[] are of type acc_t:

typedef struct acc

int acc_linkC;
int acc_offset, acc_length;
buf_t *acc_buffer;
struct acc *acc_next, *acc_ext_link;
} acc_t;
The fields of these struct's are described in the context of the functions that access them.

buf512_freelist is the linked list of accessors that have associated buffers and acc_freelist is the linked list of accessors that do not have associated buffers. When a buffer is needed, an accessor from buf512_freelist is taken (see bf_memreq() below). When a single accessor or a segment of the linked list is duplicated, the duplicate accessor is taken from acc_freelist (see bf_dupacc() and bf_cut() below).

If an accessor is at the beginning of a linked list or if only a single accessor is referencing it, acc_linkC will be one. If more than one accessor references another accessor, however, acc_linkC for the referenced accessor will be greater than one. Similarly, if only a single accessor references a buffer, buf_linkC will be one. If more than one accessor references a buffer, the buffer's buf_linkC will be greater than one. For two good examples of functions that affect acc_linkC/buf_linkC, see bf_dupacc() and bf_cut() below.

As with other queues within the network service, the memory for the acc_freelist queue and the buf512_freelist queue (and its associated buffers) come from arrays with a limited number of elements. This must be done because memory within Minix is scarce (for one reason, Minix does not have virtual memory).

When buffer space for data is needed (for example, for an incoming ethernet packet), bf_memreq() is called to acquire the space. For example, if ETH_MAX_PACK_SIZE (#define'd as 1514) bytes of buffer space are required, bf_memreq() will remove 3 accessors from buf512_freelist and will return a pointer to the first accessor:

If an accessor needs to be duplicated, bf_dupacc() is called. For example, if acc (see figure below) is needed to be duplicated, bf_dupacc(acc) will return new_acc:

Note that the buf_linkC of buffers512[127] and the acc_linkC of accessors[65] are incremented to 2. Also note that the accessor returned by bf_dupacc() (in this case, new_acc) is taken from acc_freelist and not from buf512_freelist.

After a chain of accessors is no longer needed, the chain can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors or their associated buffers in the linked list is not equal to one, then the entire chain will not be freed. For example, if buf_afree(acc1) is called for the following chain:

Then the resulting chain will be:

bf_afree() returns acc1 (accessors[63]) to acc_freelist (recall that acc_freelist is the linked list of acc_t's without an associated buffer). However, buffers512[127] cannot be freed because acc2 (accessors[64]) still references it.

bf_afree() is called after an accessor's associated data is no longer needed (for example, after a packet has been sent off by the ethernet driver).

If a section of a linked list needs to be duplicated (as opposed to a single accessor - see bf_dupacc() above), bf_cut() is called. For example, if a section of length 50 starting at an offset of 75 of the linked list below needs to be duplicated, bf_cut(data, 75, 50) is called:

bf_cut() is used in a number of scenarios, including cutting a received ethernet packet to size. bf_afree() is generally called after bf_cut() to free up the original accessor linked list.

If only the beginning of a linked list can be freed, bf_delhead() is called. If acc_linkC and buf_linkC are one for all of the relevant accessors and their associated buffers in the linked list, the operation is straight-forward:

bf_delhead() is often called to remove the header (e.g., ip header) from a packet. Note that the buffers of the accessors returned to the buf512_freelist have their buf_linkC field set to zero (0).

bf_append() appends one accessor linked list to another accessor linked list. For example, if the payload of an ethernet packet (1500 bytes) is appended to an ethernet header (14 bytes):

the resulting linked list is as follows:

If data is not already packed and aligned, bf_align(acc, size, alignment) packs SIZE bytes from ACC, a linked list of accessors, by calling bf_pack(). This packing is necessary to ensure that all of the fields from a header are easily accessed. For example, the ip code aligns a packet's header contained in the accessors before accessing the various ip header fields.