【他引】
代码：linux-2.4 Kernel
图一 ：Linux TCP IP 协议栈分析.pdf【背景】
sk_buff{}结构是linux 网络协议栈的重要结构体，本结构描述的数据包（package）穿梭于运输层~链路层之间。每个数据包都有对应的sk_buff进行描述，而系统对这么多的sk_buff的处理时以循环双链表的形式组织的。见如下图：
图一
【数据结构】
//链表表头，维护一个表，作为一个链表的标杆，不做具体数据的存储
struct sk_buff_head {
struct sk_buff* next;
struct sk_buff* prev;
__u32qlen;
spinlock_tlock;
};
//链表数据节点
struct sk_buff {
/* 链表结构参数*/
struct sk_buff* next;/* Next buffer in list */
struct sk_buff* prev;/* Previous buffer in list */
struct sk_buff_head * list;/* List we are on*/
/*...
data
...*/
}
【List init】
链表的初始化...
//链表的表头的初始化
static inline void skb_queue_head_init(struct sk_buff_head *list)
{
spin_lock_init(&list->lock);
list->prev = (struct sk_buff *)list;
list->next = (struct sk_buff *)list;
list->qlen = 0;
}
【Operations】
链表的每个操作有两个函数构成，形如__fun(),fun()。而且都是在fun()中调用__fun()。
主要原因是__fun()是非原子操作，在fun()中添加锁机制，确保__fun()操作的原子性。
比如：__skb_quque_head()和skb_queue_head();
static inline void __skb_queue_head(struct sk_buff_head *list, struct sk_buff *newsk)
{
struct sk_buff *prev, *next;
newsk->list = list;
list->qlen++;
prev = (struct sk_buff *)list;
next = prev->next;
newsk->next = next;
newsk->prev = prev;
next->prev = newsk;
prev->next = newsk;
}
/**
*skb_queue_head - queue a buffer at the list head
*@list: list to use
*@newsk: buffer to queue
*
*Queue a buffer at the start of the list. This function takes the
*list lock and can be used safely with other locking &sk_buff functions
*safely.
*/
//头部添加
static inline void skb_queue_head(struct sk_buff_head *list, struct sk_buff *newsk)
{
unsigned long flags;
spin_lock_irqsave(&list->lock, flags);
__skb_queue_head(list, newsk);
spin_unlock_irqrestore(&list->lock, flags);
}
其他函数的fun()基本显示，下面就主要贴出每个链表操作的具体实现的函数__fun().
/**
*__skb_queue_tail - queue a buffer at the list tail
*@list: list to use
*@newsk: buffer to queue
*
*Queue a buffer at the end of a list. This function takes no locks
*and you must therefore hold required locks before calling it.
*
*A buffer cannot be placed on two lists at the same time.
*/
//尾部添加
static inline void __skb_queue_tail(struct sk_buff_head *list, struct sk_buff *newsk)
{
struct sk_buff *prev, *next;
newsk->list = list;
list->qlen++;
next = (struct sk_buff *)list;
prev = next->prev;
newsk->next = next;
newsk->prev = prev;
next->prev = newsk;
prev->next = newsk;
}
/**
*__skb_dequeue - remove from the head of the queue
*@list: list to dequeue from
*
*Remove the head of the list. This function does not take any locks
*so must be used with appropriate locks held only. The head item is
*returned or %NULL if the list is empty.
*/
//删除第一个数据节点
static inline struct sk_buff *__skb_dequeue(struct sk_buff_head *list)
{
struct sk_buff *next, *prev, *result;
prev = (struct sk_buff *) list;
next = prev->next;
result = NULL;
if (next != prev) {
result = next;
next = next->next;
list->qlen--;
next->prev = prev;
prev->next = next;
result->next = NULL;
result->prev = NULL;
result->list = NULL;
}
return result;
}
/**
*__skb_dequeue_tail - remove from the tail of the queue
*@list: list to dequeue from
*
*Remove the tail of the list. This function does not take any locks
*so must be used with appropriate locks held only. The tail item is
*returned or %NULL if the list is empty.
*/
//删除最后一个数据节点
static inline struct sk_buff *__skb_dequeue_tail(struct sk_buff_head *list)
{
struct sk_buff *skb = skb_peek_tail(list);
if (skb)
__skb_unlink(skb, list);
return skb;
}
/*
*Insert a packet on a list.
*/
static inline void __skb_insert(struct sk_buff *newsk,
struct sk_buff * prev, struct sk_buff *next,
struct sk_buff_head * list)
{
newsk->next = next;
newsk->prev = prev;
next->prev = newsk;
prev->next = newsk;
newsk->list = list;
list->qlen++;
}
/*
*Place a packet after a given packet in a list.
*/
static inline void __skb_append(struct sk_buff *old, struct sk_buff *newsk)
{
__skb_insert(newsk, old, old->next, old->list);
}
/*
* remove sk_buff from list. _Must_ be called atomically, and with
* the list known..
*/
static inline void __skb_unlink(struct sk_buff *skb, struct sk_buff_head *list)
{
struct sk_buff * next, * prev;
list->qlen--;
next = skb->next;
prev = skb->prev;
skb->next = NULL;
skb->prev = NULL;
skb->list = NULL;
next->prev = prev;
prev->next = next;
}