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.

CRAMPED

CRAMPED is #define'd in inet.h as 0 for an 80836 processor or better and 1 for anything less (e.g., 8086). In the figures and discussions in this documentation, it is assumed that the system is an 80836 or better.

If the system is not even an 80386, it is a fair assumption that there is not much memory to work with (i.e., the memory is "cramped").

On line 2071, an array of BUF512_NR (128) buffer elements (of type buf512_t - see line 2059) elements is created. These buffers are used to build outgoing packets and store incoming packets. These buffers are associated with accessors in the manner described at the top of this file.

Assuming that BUF2K_NR and BUF32K_NR are 0 (which is the default), ACC_NR will be 192.

ACC_NR = (128 + 0 + 0) * 3/2 = 192

The six "clients" are ethernet (0), psip (1), ip (2), icmp (3), tcp (4), and udp (5). For more details, see bf_logon() on line 2199.

---

/* The following is not used for the default configuration.

do while(0)

Note that the do loop in the macro ends with "while(0)". Therefore, this loop will execute only once.

Here is an explanation of this construct (from Steve Summit - scs@eskimo.com):

10.4:	What's the best way to write a multi-statement macro?



A:	The usual goal is to write a macro that can be invoked as if it

	were a statement consisting of a single function call.  This

	means that the "caller" will be supplying the final semicolon,

	so the macro body should not.  The macro body cannot therefore

	be a simple brace-enclosed compound statement, because syntax

	errors would result if it were invoked (apparently as a single

	statement, but with a resultant extra semicolon) as the if

	branch of an if/else statement with an explicit else clause.



	The traditional solution, therefore, is to use



		#define MACRO(arg1, arg2) do {	\

			/* declarations */	\

			stmt1;			\

			stmt2;			\

			/* ... */		\

			} while(0)	/* (no trailing ; ) */



	When the caller appends a semicolon, this expansion becomes a

	single statement regardless of context.  (An optimizing compiler

	will remove any "dead" tests or branches on the constant

	condition 0, although lint may complain.)

*/

---

In other words, do nothing if malloc() is not used to allocate space for the buffers. By default, malloc() is not used. Instead, the global variable buffers512[] is used for the buffer space.

The macro DECLARE_TYPE() is #define'd on line 2041. DECLARE_TYPE(buf512, buf512_t, 512) produces the following code:

typedef struct buf512

{  

   buf_t buf_header;

   char buf_data[512];

} buf512_t



typedef struct buf 

{ 

   int buf_linkC; 

   buffree_t buf_free; 

   size_t buf_size; 

   char *buf_data_p; 

} buf_t;

Click here for a description of the preceding struct's.

The macro DECLARE_STORAGE() is #define'd on lines 2061-2062. DECLARE_STORAGE(buf512_5, buffers512, BUF512_NR) produces the following code:

PRIVATE buf512_5 buffers512[BUF512_NR]

where BUF512_NR is #define'd above as 128.

So there will be will be 128 buffers with a storage of 512 bytes (.5 KB) each for a total of 64KB. This value is equal to the maximum size of an IPv4 datagram. However, data link protocols typically do not produce datagrams of this size.

Click here for a description of the preceding array.

The macro DECLARE_STORAGE() is #define'd on lines 2061-2062. DECLARE_STORAGE(acc_t, accessors, ACC_NR) produces the following code:

PRIVATE acc_t accessors[ACC_NR]

where ACC_NR is #define's above as 192.

Click here for a description of this array.

freereq[] is an array of pointers to functions that consists of 6 elements. CLIENT_NR is #define'd as 6 and is the number of clients in the network service (eth, psip, ip, icmp, tcp, and udp; see bf_logon() on line 2199). These functions free buffers used by their respective client. For example, the element in freereq[] corresponding to the ethernet client is eth_buffree().

bf_freereq_t is declared as a type in buf.h:

typedef void (*bf_freereq_t) ARGS(( int priority ));

In other words, a variable of type bf_freereq_t is a pointer to a function that returns a void and takes an int as a parameter.

bf_free_bufsize is the size of all the buffers that are associated with acc's on the buf512_freelist.

---

/* The following is not used for the default configuration.

*/

---

bf_init()

bf_init() is called by nw_init(). bf_init() allocates space for buffers512[] and accessors[] and initializes buf512_freelist and acc_freelist.

BUF_S is #define'd in inet/const.h:

#define BUF_S 512

CLIENT_NR is #define'd as 6 and corresponds to the 6 "clients": eth (0), psip (1), ip (2), icmp (3), tcp (4), and udp (5). freereq[] is an array of pointers to functions that free buffers used by their respective clients (by calling bf_afree()). The loop here simply sets each element to null. bf_logon(), on the other hand, sets these elements to meaningful values. For example, the ethernet code calls bf_logon() to set the ethernet element to eth_buffree().

---

/* The following is not used for the default configuration.

*/

---

BUF512_NR is #define'd above as 128 if it's not CRAMPED (i.e., not in real mode). BUF2K_NR and BUF32K_NR are both #define'd as 0.

The macro ALLOC_STORAGE is #define'd on line 2064. For the current configuration (BUF_USEMALLOC is not defined), ALLOC_STORAGE does nothing.

---

/* The following is not used for the default configuration.

*/

---

This for loop zeroes out all of the accessors and initializes the acc_freelist linked list. Note, however, that these accessors are altered immediately after the loop by INIT_BUFFERS (see below).

INIT_BUFFERS is #define'd below and then called immediately after the #define (see line 2185).

INIT_BUFFERS initializes several fields of the accessors and their associated buffers.

When called from line 2184, Freefunc is bf_512free() (see line 2840). bf_512free() simply sticks the acc_t back on buf512_freelist, making the buffer available for future buffer requests.

buf_data_p is a pointer to the actual data.

do while(0)

Note that the do loop in the macro ends with "while(0)". Therefore, this loop will execute only once.

Here is an explanation of this construct (from Steve Summit - scs@eskimo.com):

10.4:	What's the best way to write a multi-statement macro?



A:	The usual goal is to write a macro that can be invoked as if it

	were a statement consisting of a single function call.  This

	means that the "caller" will be supplying the final semicolon,

	so the macro body should not.  The macro body cannot therefore

	be a simple brace-enclosed compound statement, because syntax

	errors would result if it were invoked (apparently as a single

	statement, but with a resultant extra semicolon) as the if

	branch of an if/else statement with an explicit else clause.



	The traditional solution, therefore, is to use



		#define MACRO(arg1, arg2) do {	\

			/* declarations */	\

			stmt1;			\

			stmt2;			\

			/* ... */		\

			} while(0)	/* (no trailing ; ) */



	When the caller appends a semicolon, this expansion becomes a

	single statement regardless of context.  (An optimizing compiler

	will remove any "dead" tests or branches on the constant

	condition 0, although lint may complain.)

After this macro is executed, accessors[] is as follows:



There are two items of interest in this figure. First, note that only accessors in the buf512_freelist have buffers associated with them. Also, note that all the linkC's (acc_linkC and buf_linkC) are initialized to zero.

bf_512free() (see line 2840) is the function that frees the accessor by simply putting the accessor back on the buf512_freelist. These accessors can then be used for future requests for buffer space.

---

/* The following is not used in the default configuration.

*/

---

bf_logon()

bf_logon() is used by eth_init(), psip_init(), ip_init(), icmp_init(), tcp_init(), and udp_init() to register their functions for freeing buffers. For example, eth_init() calls bf_logon() with an argument of eth_buffree().

After bf_logon() is finished, freereq[] is configured as follows:

freereq[0]=eth_buffree
freereq[1]=psip_buffree
freereq[2]=ip_buffree
freereq[3]=icmp_buffree
freereq[4]=tcp_buffree
freereq[5]=udp_buffree

The first time that bf_logon() is called, freereq[0] is set and bf_logon() returns; the second time bf_logon() is called, freereq[1] is set and bf_logon()() returns and so on.

The first "client" to call bf_logon() is the ethernet code followed by the psip code, the ip code, the icmp code, the tcp code, and then finally the udp code.

bf_memreq()

After the buffers have been initialized, accessors[] looks like the following:



bf_memreq() allocates accessors to the caller. For example, if 1514 bytes of buffer space are requested immediately after the network process starts and each buffer is 512 bytes (the default), then accessors[] will look like the following:



Note that three elements of accessors[] have been removed from buf512_freelist and that the head of the chain of the 3 accessors is returned by bf_memreq(). Also note that the acc_linkC and buf_linkC fields have been set to one and acc_length and acc_offset have been set to their appropriate values.

So what happens if there are not enough buffers on the buf512_freelist to satisfy a request? On lines 2280-2290 of buf.c, functions that free buffers for the specific clients (e.g., eth_buffree()) are called until there are enough buffers on buf512_freelist.

For a complete description of the network service's buffer management, click here.

size_t is declared in include\sys\types.h:

typedef unsigned int size_t;

Variables of type size_t hold the results of the sizeof operator.

The author is referring to the "else" on line 2260. This "else" is implemented with the macro that follows.

BUF_S is #define'd in const.h as 512. If this conditional holds true, buffer space is still needed and exists in Freelist (for our configuration, buf512_freelist) and is ready to be allocated. This macro removes one of the accessors off the Freelist (buf512_freelist).

acc_linkC is nonzero if the accessor is no longer on the acc_freelist or the buf512_freelist. acc_linkC is greater than one if more than one accessors reference the accessor (see comments for line 2001).

The macro above is substituted at line 2264.

---

/* The following is not used for the default configuration.

*/

---

When using macros, a good practice is to undefine (#undef) the macro immediately after using it. This helps eliminate name space pollution.

We continue from here on with the "dangling else" (referred to on line 2247). This block helps free up accessors so that they can return to the buf512_freelist. They can then be acquired by this call to bf_memreq().

This loop first frees up buffers of priority 1 by calling the client (eth, psip, ip, icmp, udp, and tcp) specific functions for freeing buffers with a parameter of 1 (e.g., eth_buffree(1) and then calling the same functions with a parameter of 2 and so on until 10.

MAX_BUFREQ_PRI is #define'd in inet/generic/buf.h:

#define MAX_BUFREQ_PRI 10

Each client is responsible for determining the priority level of an accessor that they have acquired.

Call the client specific function for freeing buffers (e.g., eth_buffree()). These functions all call bf_afree() (see line 2347).

---

/* The following is not used for the default configuration.

*/

---

If the attempt to free up buffers is not successful, we've got problems.

The end of the "dangling else".

---

/* The followng is not used for the default configuration.

*/

---

Place the first accessor at the head of the linked list and all subsequent accessors at the tail.

If the size requested is not a multiple of 512, the last accessor will have an acc_length of less than 512.

The end of the "while" loop that started at line 2243.

This function is simply a wrapper for bf_memreq() and is called in only one location by bf_append().

---

/* The following is not used in the default configuration.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

bf_afree() is a big while loop. Each time around the while loop, either an accessor in the linked list is freed or the loop ends. The loop ends if the accessor is the last element in the linked list or its acc_linkC is greater than one. If the accessor has an acc_linkC greater than one, more than one accessor linked list contains this accessor. For this reason, this accessor cannot be returned to either buf512_freelist or acc_freelist.

An accessor that is freed is returned to either buf512_freelist or acc_freelist. If the accessor's associated buffer has a buf_linkC equal to one, the freed accessor is the only element that is referencing the buffer and so the accessor is returned to buf512_freelist (remember that buf512_freelist contains accessors and their associated buffers). If the associated buffer has a buf_linkC greater than one, the accessor is not the only accessor that is referencing the buffer and so the buffer cannot be freed. For this reason, the freed accessor is returned to acc_freelist and not buf512_freelist (remember that acc_list contains only accessors with no associated buffers).

In the figure below, bf_afree(acc1) is called. This figure shows the state of the linked list at each iteration around the loop.



During the next iteration of the loop, the acc_linkC field of accessors[65] is decremented (line 2366) but the code breaks out of the loop and the function returns.

---

/* The following is not used in the default configuration.

*/

---

If this accessor is referenced by more than one accessor, do not free this accessor nor any additional accessors (note that bf_afree() immediately returns after this loop is exited).

How does an accessor have a acc_linkC greater than one? See bf_dupacc() on line 2414.

---

/* The following is not used in the default configuration.

*/

---

---

/* The following is not used in the default configuration.

*/

---

buf_linkC for a buffer can be greater than one if more than one accessor references it. For example, for the figure below, the buffer associated with acc2 (buffers512[127]) is referenced by two accessors, acc1 and acc2.



If more than one accessors references an accessor's associated buffer, the accessor will be freed without its associated buffer (i.e., the accessor will be returned to acc_freelist).

---

/* The following is not used in the default configuration.

*/

---

bf_free_bufsize is the size of the buffers in buf512_freelist. Increase bf_free_bufsize by the size of the buffer just released.

---

/* The following is not used in the default configuration.

*/

---

For the current configuration, buf_free is the function bf_512free().

bf_512free() simply puts the acc back on the buf512_freelist linked list. Remember that buf512_freelist is the linked list of all the free accessors that have associated buffers and that acc_freelist is the linked list of all the free accessors that do not have associated buffers.

---

/* The following is not used in the default configuration.

*/

---

bf_dupacc()

bf_dupacc(acc_ptr) creates a new accessor that is a duplicate of acc_ptr, bf_dupacc()'s only parameter.

More specifically, bf_dupacc() removes an accessor from acc_freelist and copies the accessor referred to by acc_ptr and sets acc_linkC of the new accessor to one. If acc_next is non-null, bf_dupacc() also increments acc_linkC of acc_next (the next accessor in the linked list). And if acc_buffer is non-null, bf_dupacc() also increments buf_linkC of the buffer.

This process is best described by a diagram:



Note that the link counts (acc_linkC and buf_linkC) for accessors[65] and buffers512[127] are incremented.

Remember that free accessors associated with buffers reside on buf512_freelist and free accessors not associated with buffers reside on acc_freelist. In addition, acc_linkC is one or greater if the accessor is no longer on either of the freelists and is greater than one if more than one accessor refers to it (through acc_next). buf_linkC is one or greater if its associated accessor (or accessors) are not on buf512_freelist and is greater than one if more than one accessor refers to it (through acc_buffer).

free_accs()

If there are no accessors on acc_freelist (the linked list of unused accessors without buffers), bf_dupacc() calls free_accs() to free up accessors. free_accs() goes through all the different priority levels for the 6 different clients (eth, psip, ip, icmp, tcp, and udp), calling the client-specific buffer-freeing functions (e.g., eth_buffree()).

Recall that acc_freelist contains free accessors that do not have associated buffers. buf512_freelist contains free accessors that have associated buffers. The duplicate accessor comes from acc_freelist.

The new accessor becomes a copy of the accessor passed in (acc_ptr).

As described in the comments on line 2414, acc_linkC of the next accessor in the linked list is incremented and buf_linkC of the associated buffer is incremented.

Indicate that the accessor is in use.

---

/* The following is not used in the default configuration.

*/

---

bf_bufsize()

bf_bufsize() returns the total buffer size of a linked list of accessors (i.e., the sum of acc_length for the accessors in a linked list).

For a detailed description of the network service's buffer management, click here.

Go until the end of the accessor linked list.

Note that acc_length of an accessor may be less than buf_size. For example, if an ethernet packet is dumped into the buffers of a linked list of accessors by the ethernet driver and the size of the packet is less than a multiple of buf_size, the acc_length field of the last accessor in the linked list will be less than than buf_size.

---

/* The following is not used in the default configuration.

*/

---

bf_packIffLess()

If the data in a linked list of accessors is less than min_len (the second parameter), bf_packIffLess(pack, min_len) packs the data by calling bf_pack().

bf_packIffLess() is often called to ensure that a packet's header is in a single contiguous buffer so that the individual fields of the header can be easily accessed.

For a detailed description of the network service's buffer management, click here.

---

/* The following is not used in the default configuration.

*/

---

---

/* The following is not used in the default configuration.

*/

---

bf_pack()

bf_pack(old_acc) creates a new linked list of accessors of old_acc's equivalent length and copies the data from old_acc to it. In this way, the data is compressed (or packed).

For example, bf_pack(old_acc) will return new_acc:



(Note that 300+200+300=800=512+288.)

If old_acc is null (in other words, there is no linked list of accessors), there's nothing to pack. If old_acc is only a single accessor in the linked list (i.e., old_acc->acc_next is null) and the accessor or its buffer is not a part of another accessor linked list (i.e., acc_linkC and buf_linkC are one), the buffer is already as "packed" as it ever will be.

If the accessor or buffer is shared by another linked list of accessors (i.e., acc_linkC or buf_linkC is greater than one), a new accessor is acquired by bf_memreq() and the buffer from the old accessor is copied to this buffer and the acc_linkC of the accessor and buf_linkC of its associated buffer are decremented. In this way, the buffer from the new accessor is no longer associated with another accessor linked list.

bf_bufsize()

bf_bufsize() returns the total buffer size of a linked list of accessors (i.e., the sum of acc_length for the accessors in a linked list).

For a detailed description of the network service's buffer management, click here.

The existing linked list of accessors will not be modified. A new linked list of accessors is instead created with bf_memreq().


bf_memreq()

After the buffers have been initialized, accessors[] looks like the following:



bf_memreq() allocates accessors to the caller. For example, if 1514 bytes of buffer space are requested immediately after the network process starts and each buffer is 512 bytes (the default), then accessors[] will look like the following:



Note that three elements of accessors[] have been removed from buf512_freelist and that the head of the chain of the 3 accessors is returned by bf_memreq(). Also note that the acc_linkC and buf_linkC fields have been set to one and acc_length and acc_offset have been set to their appropriate values.

So what happens if there are not enough buffers on the buf512_freelist to satisfy a request? On lines 2280-2290 of buf.c, functions that free buffers for the specific clients (e.g., eth_buffree()) are called until there are enough buffers on buf512_freelist.

For a complete description of the network service's buffer management, click here.

The code within the while loop consists of bookkeeping and copying.

For example, in the scenario described in the comments on line 2488, the 300 bytes from old_acc's first buffer are copied to new_acc's first buffer. Next, the 200 bytes from old_acc's second buffer are copied to new_acc's first buffer. Next, 12 bytes from old_acc's third buffer are copied to new_acc's first buffer and then the remaining 288 bytes are copied to new_acc's second buffer.

If true, all of the data from the current old buffer has already been copied to the current new buffer. Move on to the next old buffer.

All of the data from the current old buffer may not be able to be copied into the current new buffer. The rest of the data will be copied into the next new buffer (on the next iteration).

bf_temporary_acc is a pointer to acc_t, defined in line 2094 as:



memcpy()

memcpy is declared in include/string.h:

void *memcpy(void *s1, const void *s2, size_t n)

memcpy() copies n bytes from location s1 to location s2.


ptr2acc_data()

The macro ptr2acc_data is #define'd in inet/generic/buf.h as:

#define ptr2acc_data(/* acc_t * */ a) (bf_temporary_acc=(a), \
(&bf_temporary_acc->acc_buffer->buf_data_p[bf_temporary_acc-> \
acc_offset]))

ptr2acc_data() simply returns a pointer to the actual data within an accessor.

ptr2acc_data() is usually called so that the fields of a header (e.g., ip header) can be analyzed.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

---

/* The following is not used in the default configuration.

*/

---

bf_cut()

If a section of a linked list needs to be duplicated, bf_cut(data, offset, length) 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:



Note that the original linked list remains unchanged and that acc_linkC for all the accessors in the new linked list is one.

If length (the second parameter) is zero, simply duplicate the first accessor in the linked list but set acc_length=0 and acc_next=null. In other words, create a linked list of length one accessor whose acc_length is 0.

bf_cut() is used in a number of scenarios, including cutting a received ethernet packet to size.

For a full description of the network service's buffer management, click here.

---

/* The following is not used in the default configuration.

*/

---

If length (the second parameter) is zero, simply duplicate the first accessor in the linked list but set acc_length=0 and acc_next=null. In other words, create an accessor linked list of length one and the acc_length of this one accessor will be 0.

bf_dupacc()

bf_dupacc(acc_ptr) creates a new accessor that is a duplicate of acc_ptr, bf_dupacc()'s only parameter.

More specifically, bf_dupacc() removes an accessor from acc_freelist and copies the accessor referred to by acc_ptr and sets acc_linkC of the new accessor to one. If acc_next is non-null, bf_dupacc() also increments acc_linkC of acc_next (the next accessor in the linked list). And if acc_buffer is non-null, bf_dupacc() also increments buf_linkC of the buffer.

This process is best described by a diagram:



Note that the link counts (acc_linkC and buf_linkC) for accessors[65] and buffers512[127] are incremented.

Remember that free accessors associated with buffers reside on buf512_freelist and free accessors not associated with buffers reside on acc_freelist. In addition, acc_linkC is one or greater if the accessor is no longer on either of the freelists and is greater than one if more than one accessor refers to it (through acc_next). buf_linkC is one or greater if its associated accessor (or accessors) are not on buf512_freelist and is greater than one if more than one accessor refers to it (through acc_buffer).

One of the things that bf_dupacc() does is to increment acc_linkC of acc_next by one. Since acc_next is set to null on the next line, acc_linkC is decremented by one.

Remember that acc_linkC for all accessors not on the freelists (buf512_freelist or acc_freelist) have values greater than or equal to one. If an accessor is referenced by acc_next by more than one other accessor, its acc_linkC will be greater than one.


bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

---

/* The following is not used in the default configuration.

*/

---

If length (the second parameter) is not zero (the usual case), a section of the original linked list is duplicated:



Note that the new accessors come from acc_freelist. Recall that acc_freelist is made up of accessors without associated buffers. buf512_freelist is made up of accessors with associated buffers.

Determine which accessor's buffer to begin duplicating.

Create the head of the new linked list.

bf_dupacc()

bf_dupacc(acc_ptr) creates a new accessor that is a duplicate of acc_ptr, bf_dupacc()'s only parameter.

More specifically, bf_dupacc() removes an accessor from acc_freelist and copies the accessor referred to by acc_ptr and sets acc_linkC of the new accessor to one. If acc_next is non-null, bf_dupacc() also increments acc_linkC of acc_next (the next accessor in the linked list). And if acc_buffer is non-null, bf_dupacc() also increments buf_linkC of the buffer.

This process is best described by a diagram:



Note that the link counts (acc_linkC and buf_linkC) for accessors[65] and buffers512[127] are incremented.

Remember that free accessors associated with buffers reside on buf512_freelist and free accessors not associated with buffers reside on acc_freelist. In addition, acc_linkC is one or greater if the accessor is no longer on either of the freelists and is greater than one if more than one accessor refers to it (through acc_next). buf_linkC is one or greater if its associated accessor (or accessors) are not on buf512_freelist and is greater than one if more than one accessor refers to it (through acc_buffer).

One of the things that bf_dupacc() does is to increment acc_linkC of acc_next by one. Since acc_next is set to null on the next line, acc_linkC is decremented by one.

Remember that acc_linkC for all accessors not on the freelists (buf512_freelist or acc_freelist) have values greater than or equal to one. If an accessor is referenced by acc_next by more than one other accessor, its acc_linkC will be greater than one.

Note that this is the rationale for the bf_afree() on lines 2610 and 2626.


bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

Create the midsection of the linked list.

Create the tail of the linked list.

---

/* The following is not used in the default configuration.

*/

---

---

/* The following is not used in the default configuration.

*/

---

'register' is a declaration modifier that requests that the compiler use a cpu register instead of ram (which is slower) for the variable. It is common to declare loop counter variables as register variables.

bf_delhead()

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.

For a detailed description of the network service's buffer management, click here.

The following example shows an ethernet header being removed. Initially, data points to an ethernet packet with its ethernet header.

Advance new_acc past the accessors that contain buffers that will be removed. For our example, since only 14 bytes will be removed and since 14 bytes falls within the first accessor's buffer, new_acc does not advance beyond the first accessor.

---

/* The following is not used in the default configuration.

*/

---

Since new_acc did not advance beyond data, the linked list appears as follows:

For our example, since new_acc does not advance, no accessors will be freed by bf_afree() and the linked list does not change.

The acc_linkC field of new_acc is incremented to prevent bf_afree() from freeing new_acc.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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 acc_linkC is greater than one, the accessor that data and new_acc reference is also a link in another accessor linked list. Since this function modifies the acc_length and acc_offset fields of the accessor, call bf_dupacc() to duplicate the accessor referenced by data so that the other link list(s) are not affected.

bf_dupacc()

bf_dupacc(acc_ptr) creates a new accessor that is a duplicate of acc_ptr, bf_dupacc()'s only parameter.

More specifically, bf_dupacc() removes an accessor from acc_freelist and copies the accessor referred to by acc_ptr and sets acc_linkC of the new accessor to one. If acc_next is non-null, bf_dupacc() also increments acc_linkC of acc_next (the next accessor in the linked list). And if acc_buffer is non-null, bf_dupacc() also increments buf_linkC of the buffer.

This process is best described by a diagram:



Note that the link counts (acc_linkC and buf_linkC) for accessors[65] and buffers512[127] are incremented.

Remember that free accessors associated with buffers reside on buf512_freelist and free accessors not associated with buffers reside on acc_freelist. In addition, acc_linkC is one or greater if the accessor is no longer on either of the freelists and is greater than one if more than one accessor refers to it (through acc_next). buf_linkC is one or greater if its associated accessor (or accessors) are not on buf512_freelist and is greater than one if more than one accessor refers to it (through acc_buffer).

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

For our example, since no other accessor linked list also contains the accessor referenced by data, the linked list remains as before.

---

/* The following is not used in the default configuration.

*/

---

bf_append()

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:

The two linked lists of accessors, data_first and data_second, in the figure below are used as an example in the comments below.

Verify that there are indeed two linked lists to join together and not just one.

If acc_linkC is nonzero for any of the accessors, not only is the first accessor duplicated but all accessors that follow are duplicated. This is done to prevent changes on the linked lists that share accessors with the linked list that begins with data_first.

bf_dupacc()

bf_dupacc(acc_ptr) creates a new accessor that is a duplicate of acc_ptr, bf_dupacc()'s only parameter.

More specifically, bf_dupacc() removes an accessor from acc_freelist and copies the accessor referred to by acc_ptr and sets acc_linkC of the new accessor to one. If acc_next is non-null, bf_dupacc() also increments acc_linkC of acc_next (the next accessor in the linked list). And if acc_buffer is non-null, bf_dupacc() also increments buf_linkC of the buffer.

This process is best described by a diagram:



Note that the link counts (acc_linkC and buf_linkC) for accessors[65] and buffers512[127] are incremented.

Remember that free accessors associated with buffers reside on buf512_freelist and free accessors not associated with buffers reside on acc_freelist. In addition, acc_linkC is one or greater if the accessor is no longer on either of the freelists and is greater than one if more than one accessor refers to it (through acc_next). buf_linkC is one or greater if its associated accessor (or accessors) are not on buf512_freelist and is greater than one if more than one accessor refers to it (through acc_buffer).

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

Get rid of any accessors in the first linked list that have no data.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

At this point, the two linked lists appear as follows:

At this point, acc_next should point to null anyway (the last link in a linked list always points to null).

Remove the empty acc_t's at the beginning of the linked list.

There is no data in the second linked list.

In this case, there's no possibility to merge the tail of the first linked list with the head of the second linked list so just stick them together and return the head of the first linked list.

The rest of the code involves merging the last buffer of the first linked list with the first buffer of the second linked list.

If more than one accessor references the buffer (i.e., buf_linkC > 1), do not alter the buffer.

bf_buf_gran is the same size as buf_size (512). It is unclear under what circumstances bf_buf_gran would differ from buf_size.

Copy the data from the first buffer in the second linked list to the last buffer in the first linked list.

Make sure that the second accessor in the second linked list isn't freed by the call to bf_afree().

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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 more than one accessor references the last buffer of the first linked list, a new accessor and its associated buffer must be acquired through bf_small_memreq(). After the new accessor is acquired, the data in the last buffer of the first linked list and the first buffer of the last linked list must be copied to the new accessor.

bf_small_memreq() is a wrapper for bf_memreq().


bf_memreq()

After the buffers have been initialized, accessors[] looks like the following:



bf_memreq() allocates accessors to the caller. For example, if 1514 bytes of buffer space are requested immediately after the network process starts and each buffer is 512 bytes (the default), then accessors[] will look like the following:



Note that three elements of accessors[] have been removed from buf512_freelist and that the head of the chain of the 3 accessors is returned by bf_memreq(). Also note that the acc_linkC and buf_linkC fields have been set to one and acc_length and acc_offset have been set to their appropriate values.

So what happens if there are not enough buffers on the buf512_freelist to satisfy a request? On lines 2280-2290 of buf.c, functions that free buffers for the specific clients (e.g., eth_buffree()) are called until there are enough buffers on buf512_freelist.

For a complete description of the network service's buffer management, click here.

Copy the data of the last buffer of the first linked list to the new buffer.

ptr2acc_data()

The macro ptr2acc_data is #define'd in inet/generic/buf.h as:

#define ptr2acc_data(/* acc_t * */ a) (bf_temporary_acc=(a), \
(&bf_temporary_acc->acc_buffer->buf_data_p[bf_temporary_acc-> \
acc_offset]))

ptr2acc_data() simply returns a pointer to the actual data within an accessor.

ptr2acc_data() is usually called so that the fields of a header (e.g., ip header) can be analyzed.

Copy the data of the first buffer of the second accessor linked list to the buffer of the accessor just acquired.

ptr2acc_data()

The macro ptr2acc_data is #define'd in inet/generic/buf.h as:

#define ptr2acc_data(/* acc_t * */ a) (bf_temporary_acc=(a), \
(&bf_temporary_acc->acc_buffer->buf_data_p[bf_temporary_acc-> \
acc_offset]))

ptr2acc_data() simply returns a pointer to the actual data within an accessor.

ptr2acc_data() is usually called so that the fields of a header (e.g., ip header) can be analyzed.

The new accessor that was acquired by bf_small_memreq() must have the same values as the accessor it replaced.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

I don't believe that this will ever be true.

CHRISTOS, IS THIS TRUE?

Join the two linked lists together.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

---

/* The following is not used in the default configuration.

*/

---

---

/* The following is not used in the default configuration.

*/

---

free_accs()

If there are no accessors on acc_freelist (the linked list of unused accessors without buffers), bf_dupacc() calls free_accs() to free up accessors. free_accs() goes through all the different priority levels for the 6 different clients (eth, psip, ip, icmp, tcp, and udp), calling the client-specific buffer-freeing functions (e.g., eth_buffree()).

MAX_BUFREQ_PRI is #define'd in inet/generic/buf.h:

#define MAX_BUFREQ_PRI 10

Each client is responsible for determining the priority level of an accessor that they have acquired.

Call the client-specific buffer-freeing function (e.g., eth_buffree()) for a given priority.

bf_align()

If data is not already packed and aligned, bf_align(acc, size, alignment) packs size (bf_align's second parameter) bytes from acc, bf_align()'s first parameter and a linked list of accessors (i.e., a packet), 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.

For a detailed description of the network service's buffer management, click here.

If the data is already packed and aligned, do nothing.

Note that both bf_pack() (line 3176) and bf_cut() (lines 3179-3180) return accessors with buffers that are aligned.

Note that one of the side effects of bf_pack() is that data is aligned. For example, even if the first accessor in the linked list has an acc_offset greater than zero, the first accessor in the new, packed linked list will have an acc_offset of zero. This effectively aligns the data.


bf_pack()

bf_pack(old_acc) creates a new linked list of accessors of old_acc's equivalent length and copies the data from old_acc to it. In this way, the data is compressed (or packed).

For example, bf_pack(old_acc) will return new_acc:



(Note that 300+200+300=800=512+288.)

The first size (bf_align()'s second parameter) bytes are placed in the first accessor (created by the first call to bf_cut()) and then packed. The remaining bytes are placed in the buffers of the accessor linked list created by the second call to bf_cut().

bf_cut()

If a section of a linked list needs to be duplicated, bf_cut(data, offset, length) 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:



Note that the original linked list remains unchanged and that acc_linkC for all the accessors in the new linked list is one.

If length (the second parameter) is zero, simply duplicate the first accessor in the linked list but set acc_length=0 and acc_next=null. In other words, create a linked list of length one accessor whose acc_length is 0.

bf_cut() is used in a number of scenarios, including cutting a received ethernet packet to size.

For a full description of the network service's buffer management, click here.

bf_cut()

If a section of a linked list needs to be duplicated, bf_cut(data, offset, length) 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:



Note that the original linked list remains unchanged and that acc_linkC for all the accessors in the new linked list is one.

If length (the second parameter) is zero, simply duplicate the first accessor in the linked list but set acc_length=0 and acc_next=null. In other words, create a linked list of length one accessor whose acc_length is 0.

bf_cut() is used in a number of scenarios, including cutting a received ethernet packet to size.

For a full description of the network service's buffer management, click here.

bf_afree()

After a chain of accessors is no longer needed, the chain (and not simply the single accessor passed as the parameter) can be freed by calling bf_free(). However, if either acc_linkC or buf_linkC of one of the accessors in the linked list is not equal to one (1), 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).

bf_pack()

bf_pack(old_acc) creates a new linked list of accessors of old_acc's equivalent length and copies the data from old_acc to it. In this way, the data is compressed (or packed).

For example, bf_pack(old_acc) will return new_acc:



(Note that 300+200+300=800=512+288.)

---

/* The following is not used in the default configuration.

*/

---