vppinfra---Dlist

dpdk-vpp源码解读

发布于 2023-03-07 17:02:16

2800

发布于 2023-03-07 17:02:16

最近需要实现对双向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行代码非常简练。下面是其结构体字段描述：

typedef struct
{
  u32 next; /*next指向，存储索引*/
  u32 prev; /*prev指向，存储索引*/
  u32 value;/*当前数据块的value数值*/
} dlist_elt_t

Dlist相关api

双向的链表的实现很干净利落。值得学习。但是在函数clib_dlist_remove_tail应该存在bug。

Dlist链表的初始化

/* 双向循环链表头节点的初始化*/
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池的索引。

双向循环链表插入元素

从双向链表尾部插入元素。

/*插入到双向循环链表尾部
 *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;
}

插入到双向循环链表头部

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;
}

当前节点从双向循环链表中删除

/*将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来学习一下具体的使用。

/*双向循环链表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);