DPDK20.05 – rte_ring无锁环形队列的管理

1、简介

rte_ring库支持队列管理,该库并不是包含无限大小的链表,但支持以下特性:

  • FIFO
  • 最大大小尺寸是固定的,指针保存在一个table中
  • 无锁实现
  • 多消费者与单消费者出队列
  • 多生产者与单生产者入队列
  • Bulk dequeue – 如果可以 dequeue 指定数量的全部对象则成功,否则失败
  • Bulk enqueue – 如果可以 enqueue 指定数量的全部对象则成功,否则失败
  • Burst dequeue – 如果指定的出队数量没有填满,则dequeue最大可用的对象
  • Burst enqueue – 如果指定的入队数量没有填满,则enqueue最大可用的对象

这种数据结构与链表队列相比的好处是:

  • 更快:只需要对一个32位的Compare-and-swap指令操作,而不是多个指针大小的compare-and-swap指令
  • 比完全的无锁队列简单
  • 与bulk enqueue/dequeue操作适配:由于对象保存在table中,从队列中dequeue多个对象时不会产生像链表队列那么多cache misses。同时,dequeue多个对象与dequeue一个对象的消耗差不多

与链表队列相比的劣势是:

  • 大小是固定的
  • 与链表队列相比需要消耗更多内存。一个空的ring也需要包含至少N个对象

2、解析

ring结构由两组 head 和 tail 对组成,一组由生产者使用,一组由消费者使用。
后文的图中将其引用为

每个图片表示ring环形buffer的一种简化的状态。
函数本地变量的值在图片中ring环的上面,ring结构中对应的变量在图片中ring环的下面。
相关的代码可参考 DPDK 源码的 lib/librte_ring/rte_ring.h 文件。

2.1 单生产者 enqueue

当一个生产者将一个对象添加到ring中时,只有生产者的head和tail(ring->prod.head和ring->prod.tail)会被修改。
初始状态是使prod_head的值与ring中对应的值相同,另外需要一个本地变量 prod_next 指向 enqueue 之后生产者指向的位置。

2.1.1 单生产者 enqueue 第一步

首先,将 ring->prod.head 拷贝到本地变量 prod_head 中。
另一个本地变量prod_next指针table中的下一个对象,或经过批量 enqueue 后的某个对象。

这部分代码在 __rte_ring_do_enqueue() 函数中调用 __rte_ring_move_prod_head() 函数实现:

简单归纳就是:

2.1.2 enqueue 第二步

进行实际的enqueue操作,该操作由宏 ENQUEUE_PTRS() 完成,其定义如下:

2.1.3 enqueue的最后一步

当要插入的对象已经enqueue到ring中之后,就要调整 ring->prod.tail 的值,使其与新的 ring->prod.head 相等。该操作由 update_tail() 函数实现:

至此,单生产者的 enqueue操作就完成了。

在这个过程中可以看到,其调用的函数__rte_ring_move_prod_head() 是单生产者和多生产者共用的,update_tail()是所有这些生产者消费者模型共用的。后文介绍多生产者与多消费者时再做相应的介绍。

2.2 单消费者 dequeue

当消费者从ring中dequeue一个对象时,只有消费者的head和tail会被修改。

2.2.1 单消费者dequeue的第一步

首先,将ring->cons.head拷贝到本地变量cons_head中。
另一个本地变量cons_next指向当前table中cons_head的下一个对象,或经过批量 dequeue 后的某个元素。
如果ring中没有足够的对象,则判断 dequeue 模式:
如果是bulk 方式,则返回0;
如果是burst方式,则返回现有的对象数;

这部分代码在 __rte_ring_do_dequeue() 函数中调用 __rte_ring_move_cons_head() 函数实现:

简化描述就是:

2.2.2 单消费者dequeue 第二步

进行实际的dequeue操作,该操作由宏 DEQUEUE_PTRS() 完成,其定义如下:

2.2.3 单消费者dequeue 第三步

当要出队的对象已经dequeue出ring之后,就要调整 ring->cons.tail 的值,使其与新的 ring->cons.head 相等。该操作同样由 update_tail() 函数实现,前文已经介绍过该函数,这里不再复述。

至此,单消费者的dequeue操作就完成了。

2.3 多生产者

这里介绍当两个生产者同时向同一ring添加一个对象时的过程。只有生产者的head和tail会被修改。
初始状态是每个生产者将本地变量 prod_head 指向ring结构中相同的位置。

2.3.1 多生产者 enqueue 第一步

在两个core上,ring->prod.head被拷贝到每个core的本地变量prod_head中。
同时每个core上的另一个本地变量prod_next指向table中的下一个对象,或经过批量enqueue操作后的某个对象。
如果ring中没有足够的元素(通过检查cons_tail可以得知),会返回一个错误。
这部分功能通过在 __rte_ring_do_enqueue() 函数中调用 __rte_ring_move_prod_head() 函数实现,该函数之前已经介绍过,这里只介绍关于多生产者的部分:

rte_atomic32_cmpset() 函数是一个CAS(Comapre And Swap)原子操作,作用是先判断ring->prod.head与 *old_head 的值是否相等:
如果相等,则赋值 ring->prod.head = *new_head,函数返回非0值,循环重新开始;
如果不相等,则函数执行失败,函数返回0。

假设该操作在 core 1 上执行成功,将ring->prod.head 指向core 1 本地的prod_next 值;
而在core 2 上,此时读取到的ring->prod.head值是core 1 设置的新值,执行失败, 会重新执行该循环操作。

在core执行第二次循环时,会得到新的 *old_head(prod_head) 值与 *new_head(prod_next) 值,此时可以执行成功。

2.3.2 多生产者 enqueue 第二步

两个生产者执行 enqueue 操作,分别调用 ENQUEUE_PTRS() 宏向指定的位置插入对象。

2.3.3 多生产者 enqueue 第三步

最后,两个生产者调用update_tail() 函数,执行更新 ring->prod.tail的操作。

函数会判断ring->prod.tail 是否与old_val相等,即每个生产者本地的prod_head 值。
根据上面的分析可以知道,开始时ring->prod.tail 与 core 1 中的本地变量 prod_head 相等,因此core 1 更新ring->prod.tail 成功,如下图所示:

之后,prod.tail 与 core 2中的prod_head 相等,在 core 2中执行更新 prod.tail 的操作:

2.4 多消费者

这里介绍当两个消费者同时向同一ring添加一个对象时的过程。
只有消费者的head和tail(ring->cons.head和ring->cons.tail)会被修改。
初始状态是每个生产者将本地变量cons_head与cons_tail指向ring结构中相同的位置。

2.4.1 多消费者 dequeue 第一步

在两个core上,ring->cons.head被拷贝到每个core的本地变量cons_head中。
同时每个core上的另一个本地变量prod_next指向table中的下一个对象,或经过批量enqueue操作后的某个对象。
如果ring中没有足够的对象,则判断 dequeue 模式:
如果是bulk 方式,则返回0;
如果是burst方式,则返回现有的对象数;

这部分功能通过在 __rte_ring_do_dequeue() 函数中调用 __rte_ring_move_cons_head() 函数实现,该函数之前已经介绍过,这里只介绍关于多消费者的部分:

*old_head 的值即为本地 cons_head 的值。假设 core 1 先执行成功,则 ring->cons.head 被设置为 *new_head 的值,即本地的 cons_next 的值,如下图所示:

此时 core 2 的本地变量 cons_head 与 ring->cons.head 不相同,cmpset 操作执行失败,进入下一次循环,得到新的*old_head 和 *new_head 值,即新的 cons_head 与 cons_next 值:

2.4.2 多消费者 dequeue 第二步

之后,就是每个消费者各个调用 DEQUEUE_PTRS() 宏,进行对象的 dequeue 操作。

2.4.3 多消费者 dequeue 第三步

之后调用 update_tail() 函数,对ring->cons.tail 进行更新:

这时,old_val 即消费者本地的 cons_head,只有 core 1 的本地 cons_head 与 ring->cons.tail 的值相等,因此 core 1 执行成功:

之后,在 core 2 中的本地 cons_head 与 ring->cons.tail 的值相等,core 2 执行成功:

至此,所有消费者线程对 ring->cons.tail 的值的更新成功,完成了所有消费者的dequeue操作。

3、对32位索引进行求模运算

在 enqueue 与 dequeue 的计算过程中,直接使用的32位的head 与 tail 值,在实际执行过程中,这些值的范围并不是 0 到 size(ring) -1 之间,而是在 0 到 2^32 -1 之间,在通过 head 与 tail 访问 ring中的具体对象时,需要先对这些值进行掩码运算,得到实际的掩码值。

使用无符号整数的 32 位模运算也意味着对索引的操作(如加/减法等)的结果如果超过32位整数能表示的范围,会自动对结果进行取模运算。

以下两个例子有助于理解这一特性:
(注:为了便于演示,这两个例子使用16位的模运行代表32位,同时,这些生产者与消费者的索引被定义为16位无符号整数。在实际使用中应该被定义为32位无符号整数。)

3.1 例一

16位无符号整数表示的最大值为65535(2^16 – 1),例子中ring的大小为16384,表示有2 ^ 15 个对象。
掩码为16383,即 2 ^ 15 – 1。

计算得到ring中已有对象数量为:

计算得到ring空闲空间为:

3.2 例二

例子中ring的大小为16384,表示有2 ^ 15 个对象。
掩码为16383,即 2 ^ 15 – 1。

计算得到ring中已有对象数量为:

计算得到ring空闲空间为:

3.3 说明

以上两个例子中,在计算时使用了65535进行了取模计算,在实际情况下,其结果在溢出时会自动执行,不需要手动去处理。
代码会一直在生产者与消费者之间维护一个“距离” ,该距离在 0 到 size(ring) – 1之间。依赖该特性,我们可以对模32位数据之间的任意两个索引做减法操作,这也是为什么索引的溢出不会产生问题的原因。

在任何时候,entries和free_entries都在 0 和 size(ring) – 1 之间,即使减法会产生溢出也不会出问题:

4、参考

————————————————————

原创文章,转载请注明: 转载自孙希栋的博客

本文链接地址: 《DPDK20.05 – rte_ring无锁环形队列的管理》

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注