最近需要实现对双向TCP流的做保序、重组、去重功能，需要建立基于报文五元组的流表。在编译upf-vpp的时候粗略看到也有流表的管理，想参考一下其流表老化功能的实现的。看到代码中是基于dlist来实现的，所以就有了这篇关于dlist的介绍。
我们项目中的流表的老化实现是使用vpp底层库tw_timer（时间轮来实现的），参考了vpp的tcp协议栈实现策略，实现无锁化的tcp session的管理。 而upg项目完全是自己基于dlist来实现的时间轮算法,不清楚和vpp底层tw-timer性能如何。有类型功能的也可以去参考一下实现方式。upg-vpp项目路径可以参考文章：基于vpp的开源upf-vpp编译
Dlist数据结构
Dlist数据结构及api所在文件：src/vppinfra/dlist.h，总共也就140行代码非常简练。下面是其结构体字段描述：
代码语言：javascript复制typedef struct
{
u32 next; /*next指向，存储索引*/
u32 prev; /*prev指向，存储索引*/
u32 value;/*当前数据块的value数值*/
} dlist_elt_t
Dlist相关api
双向的链表的实现很干净利落。值得学习。但是在函数clib_dlist_remove_tail应该存在bug。
Dlist链表的初始化
代码语言：javascript复制/* 双向循环链表头节点的初始化*/
static inline void
clib_dlist_init (dlist_elt_t * pool, u32 index)
{
dlist_elt_t *head = pool_elt_at_index (pool, index);
clib_memset (head, 0xFF, sizeof (*head));
}
初始化函数中参数需要使用者自己管理，参数说明如下： dlist_elt_t pool ：双向链表的pool池 u32 index ：双向链表中头节点对应在pool池的索引。
双向循环链表插入元素
从双向链表尾部插入元素。
代码语言：javascript复制/*插入到双向循环链表尾部
*dlist_elt_t * pool： 双向循环链表pool池
*u32 head_index： 双向循环链表头节点对应的pool索引
*u32 new_index：待插入节点对应的pool索引
*/
static inline void
clib_dlist_addtail (dlist_elt_t * pool, u32 head_index, u32 new_index)
{
dlist_elt_t *head = pool_elt_at_index (pool, head_index);
u32 old_last_index;
dlist_elt_t *old_last;
dlist_elt_t *new;
/*双向循环链表表头中vlalue必须是全FF*/
ASSERT (head->value == ~0);
/*获取待插入节点的指针*/
new = pool_elt_at_index (pool, new_index);
/*表示当前是首次插入元素*/
if (PREDICT_FALSE (head->next == ~0))
{
head->next = head->prev = new_index;
new->next = new->prev = head_index;
return;
}
/*找到双向循环链表的尾节点，将当前接入插入*/
old_last_index = head->prev;
old_last = pool_elt_at_index (pool, old_last_index);
new->next = old_last->next;
new->prev = old_last_index;
old_last->next = new_index;
head->prev = new_index;
}
插入到双向循环链表头部
代码语言：javascript复制static inline void
clib_dlist_addhead (dlist_elt_t * pool, u32 head_index, u32 new_index)
{
dlist_elt_t *head = pool_elt_at_index (pool, head_index);
dlist_elt_t *old_first;
u32 old_first_index;
dlist_elt_t *new;
ASSERT (head->value == ~0);
new = pool_elt_at_index (pool, new_index);
if (PREDICT_FALSE (head->next == ~0))
{
head->next = head->prev = new_index;
new->next = new->prev = head_index;
return;
}
/*找到双向循环链表的头节点，将当前节点插入*/
old_first_index = head->next;
old_first = pool_elt_at_index (pool, old_first_index);
new->next = old_first_index;
new->prev = old_first->prev;
old_first->prev = new_index;
head->next = new_index;
}
当前节点从双向循环链表中删除
代码语言：javascript复制/*将index对应的节点从双向链表中删除*/
static inline void
clib_dlist_remove (dlist_elt_t * pool, u32 index)
{
dlist_elt_t *elt = pool_elt_at_index (pool, index);
dlist_elt_t *next_elt, *prev_elt;
/* listhead, not so much 不能是双向循环链表头*/
ASSERT (elt->value != ~0);
next_elt = pool_elt_at_index (pool, elt->next);
prev_elt = pool_elt_at_index (pool, elt->prev);
next_elt->prev = elt->prev;
prev_elt->next = elt->next;
elt->prev = elt->next = ~0;
}
/*删除双向循环链表的首元素*/
static inline u32
clib_dlist_remove_head (dlist_elt_t * pool, u32 head_index)
{
dlist_elt_t *head = pool_elt_at_index (pool, head_index);
u32 rv;
ASSERT (head->value == ~0);
/*当前双向循环链表为空存在2中情况，考虑比较周全。*/
if (head->next == ~0 || (head->next == head_index))
return ~0;
rv = head->next;
clib_dlist_remove (pool, rv);
return rv;
}
/*删除双向链表的尾元素*/
static inline u32
clib_dlist_remove_tail (dlist_elt_t * pool, u32 head_index)
{
dlist_elt_t *head = pool_elt_at_index (pool, head_index);
u32 rv;
ASSERT (head->value == ~0);
/*这里居然和remove head有差异。A bug ？*/
if (head->prev == ~0)
return ~0;
rv = head->prev;
clib_dlist_remove (pool, rv);
return rv;
}
简单的使用案例
我们以mfib_signal来学习一下具体的使用。
代码语言：javascript复制/*双向循环链表pool池*/
static dlist_elt_t *mfib_signal_dlist_pool；
typedef struct mfib_signal_q_t_
{
/*双向循环链表头节点索引the dlist indext that is the head of the list*/
u32 mip_head;
/*自旋锁Spin lock to protect the list*/
int mip_lock;
} mfib_signal_q_t;
/*mfib信号的待发送队列
static mfib_signal_q_t mfib_signal_pending ；
/*————————————————初始化——————————————————————*/
/*从全局pool池获取一个节点，作为双向循环链表的头节点。*/
pool_get(mfib_signal_dlist_pool, head);
hi = head - mfib_signal_dlist_pool;
mfib_signal_pending.mip_head = hi;
clib_dlist_init(mfib_signal_dlist_pool, hi);
/*————————————————从双向循环链表头去除元素处理—————————*/
li = clib_dlist_remove_head(mfib_signal_dlist_pool,
mfib_signal_pending.mip_head)；
/*————————————————从双向循环链表头插入元素处理—————————*/
/*从双向链表获取一个元素，并插入到双向循环链表头。*/
pool_get(mfib_signal_dlist_pool, elt);
li = elt - mfib_signal_dlist_pool;
/*存储数值*/
elt->value = si;
clib_dlist_addhead(mfib_signal_dlist_pool,
mfib_signal_pending.mip_head,
li);
总结
本文简单介绍vppinfra库中dlist的结构及使用举例。代码实现还是比较简单，干净利落的。在以后的项目开发中可以借鉴。
