| When a packet is currently not handled by a protocol instance, it is normally managed in queues. Linux supports the management of packets in a queue structure (struct sk_buff_head) and in a number of operations on this structure. The programmer can use these functions to abstract from the actual implementation of a socket buffer and queues to easily change the underlying implementation of the queue management. Figure 4-6 shows that the socket buffers stored in a queue are dual-concatenated in a ring structure. This dual concatenation allows quick navigation in either of the two directions. The ring structure facilitates concatenation and prevents the occurrence of NULL pointers. Figure 4-6. Packet queues in the Linux kernel. 
A queue header consists of the following skb_queue_head structure: struct sk_buff_head { struct sk_buff *next; struct sk_buff *prev; __u32 qlen; spinlock_t lock; };
next and prev are used to concatenate socket buffers; next points to the first and prev to the last packet in the queue. qlen specifies the current length of the queue in packets. lock is a spinlock (see Section 2.3.2) and can be used for atomic execution of operations on the queue. When a critical access occurs, if the spinlock is not free, the access will have to wait until it is released.
4.2.1 Operations on Socket-Buffer Queues Socket-buffer queues are a powerful tool to arrange packets in Linux. The power of this functionality is complemented by a large number of methods to manage socket buffers in queues. Most operations on socket buffers are executed during critical phases, or they can be interrupted by higher-priority operations (interrupt handling, soft-IRQ, tasklet, etc.). For this reason, packet data and pointer structures should be processed in an atomic way. Though this introduces some additional cost, because certain mechanisms (e.g., spinlocks and semaphores) have to be used to achieve save states, it is the only way to prevent inconsistent states, which could endanger the stability of the network subsystem and thus of the entire operating system. Security and stability are always more important than performance or benchmarks in Linux. For example, a fault concatenation could be produced by consecutive nested operations on a queue. The consequence would be a memory access error and eventually a system crash (kernel panic). For this reason, (mainly) the multiprocessor capability of Linux requires atomic handling of such critical processes. Most queue operations are defined as inline procedures in the include file <linux/skbuff.h>. This inline definition means that there are no real procedures; instead, procedures are built into the body of the calling function, similarly to macros. This reduces overhead of a function call and tolerates a slightly larger kernel. During each function call, we would otherwise have to pack the registers onto the stack and initialize the variable environment of the new function. For the smaller socket-buffer functions, this is far too costly; that's why they are declared inline. The role of each function is still maintained to keep the source code easy to understand and maintain. Managing Queue Structures skb_queue_head_init() | include/linux/skbuff.h |
skb_queue_head-init(list) initializes an skb_queue_head structure so that it can be used as a queue. Essentially, pointers are set to the structure, and the length is set to null (i.e., next and prev in an empty queue point to the queue list and not to NULL). skb_queue_empty() | include/linux/skbuff.h |
skb_queue_empty(list) checks on whether the queue (list) is empty or still contains buffers. The queue length list?gt;qlen is returned for the sake of simplicity. If it is null, then it is considered to be false; otherwise, it is true. skb_queue_len() | include/linux/skbuff.h |
skb_queue_len(list) returns the actual length of the specified queue, in packets. Managing Socket Buffers in Queues The following functions are available to manage packets in queues. These are mainly different strategies for arranging or removing socket buffers in a socket-buffer queue. When a packet is inserted into a queue, then the parameter skb?gt;list of the socket-buffer structure points to this queue. Of course, a packet can always be in one queue only. Each of the following functions exists in two different versions one with and a second without locked interrupts. This means that, when a function already disabled interrupts, we don't have to do this in queue functions. Functions without locked interrupts are marked by two leading underlines, e.g.,__skb_dequeue(). skb_queue_head() | include/linux/skbuff.h |
skb_queue_head(list, skb) orders a packet at the header of the specified queue and increments the length of the queue, (list?gt;qlen), by one. skb_queue_tail() | include/linux/skbuff.h |
skb_queue_tail(list, skb) appends the socket buffer skb to the end of the queue and increments its length, (list?gt;qlen), by one. skb_dequeue() | include/linux/skbuff.h |
skb_dequeue(list) removes the top packet from the queue and returns a pointer to it. The length of the queue is decremented by one. If there is no packet in the queue, then the NULL pointer is returned. skb_dequeue_tail() | include/linux/skbuff.h |
skb_dequeue_tail(list) removes the last packet from a queue and returns a pointer to it. If there is no packet in the list, then NULL is returned. skb_queue_purge() | include/linux/skbuff.h |
skb_queue_purge empties the queue list: All packets are removed from the list and released by kfree_skb(). skb_insert() | include/linux/skbuff.h |
skb_insert(oldskb, newskb) orders the socket buffer newskb in front of the buffer oldskb in the queue. In addition, it sets the list pointer of the new socket buffer to the list of the next buffer and increments the queue length. skb_append() | include/linux/skbuff.h |
skb_append(oldskb, newskb) places the socket buffer newskb behind oldskb in the queue of oldskb. Additionally, the list pointer is set to the queue of the previous buffer and the queue length is incremented by one. skb_unlink() | include/linux/skbuff.h |
skb_unlink(skb) removes the specified socket buffer from its queue (it is not explicitly passed as parameter) and decrements the queue length. skb_unlink() checks explicitly for whether the list exists; the function __skb_unlink(skb, list) does not run this test, which means that we have to ensure that the buffer is actually in a list. skb_peek() | include/linux/skbuff.h |
skb_peek(list) returns a pointer to the first element of a list, if this list is not empty; otherwise, it returns NULL. If a socket buffer is in the queue, then only a pointer to this socket buffer is returned; the socket buffer is not removed from the queue. This is to ensure that no other activities in the kernel can remove that buffer from the queue while operations run on the socket buffer, which can lead to inconsistencies. There is no interrupt-save version of skb_peek(). skb_peek_tail() | include/linux/skbuff.h |
skb_peek_tail(list) returns a pointer to the last element of a queue. If this queue is empty, then NULL is returned. Again, the buffer remains in the queue and should be protected. (See skb_peek().) | 
