1.. BSD LICENSE 2 Copyright(c) 2010-2014 Intel Corporation. All rights reserved. 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions 7 are met: 8 9 * Redistributions of source code must retain the above copyright 10 notice, this list of conditions and the following disclaimer. 11 * Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in 13 the documentation and/or other materials provided with the 14 distribution. 15 * Neither the name of Intel Corporation nor the names of its 16 contributors may be used to endorse or promote products derived 17 from this software without specific prior written permission. 18 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31.. _Ring_Library: 32 33Ring Library 34============ 35 36The ring allows the management of queues. 37Instead of having a linked list of infinite size, the rte_ring has the following properties: 38 39* FIFO 40 41* Maximum size is fixed, the pointers are stored in a table 42 43* Lockless implementation 44 45* Multi-consumer or single-consumer dequeue 46 47* Multi-producer or single-producer enqueue 48 49* Bulk dequeue - Dequeues the specified count of objects if successful; otherwise fails 50 51* Bulk enqueue - Enqueues the specified count of objects if successful; otherwise fails 52 53* Burst dequeue - Dequeue the maximum available objects if the specified count cannot be fulfilled 54 55* Burst enqueue - Enqueue the maximum available objects if the specified count cannot be fulfilled 56 57The advantages of this data structure over a linked list queue are as follows: 58 59* Faster; only requires a single Compare-And-Swap instruction of sizeof(void \*) instead of several double-Compare-And-Swap instructions. 60 61* Simpler than a full lockless queue. 62 63* Adapted to bulk enqueue/dequeue operations. 64 As pointers are stored in a table, a dequeue of several objects will not produce as many cache misses as in a linked queue. 65 Also, a bulk dequeue of many objects does not cost more than a dequeue of a simple object. 66 67The disadvantages: 68 69* Size is fixed 70 71* Having many rings costs more in terms of memory than a linked list queue. An empty ring contains at least N pointers. 72 73A simplified representation of a Ring is shown in with consumer and producer head and tail pointers to objects stored in the data structure. 74 75.. _pg_figure_4: 76 77**Figure 4. Ring Structure** 78 79.. image5_png has been replaced 80 81|ring1| 82 83References for Ring Implementation in FreeBSD* 84---------------------------------------------- 85 86The following code was added in FreeBSD 8.0, and is used in some network device drivers (at least in Intel drivers): 87 88 * `bufring.h in FreeBSD <http://svn.freebsd.org/viewvc/base/release/8.0.0/sys/sys/buf_ring.h?revision=199625&view=markup>`_ 89 90 * `bufring.c in FreeBSD <http://svn.freebsd.org/viewvc/base/release/8.0.0/sys/kern/subr_bufring.c?revision=199625&view=markup>`_ 91 92Lockless Ring Buffer in Linux* 93------------------------------ 94 95The following is a link describing the `Linux Lockless Ring Buffer Design <http://lwn.net/Articles/340400/>`_. 96 97Additional Features 98------------------- 99 100Name 101~~~~ 102 103A ring is identified by a unique name. 104It is not possible to create two rings with the same name (rte_ring_create() returns NULL if this is attempted). 105 106Water Marking 107~~~~~~~~~~~~~ 108 109The ring can have a high water mark (threshold). 110Once an enqueue operation reaches the high water mark, the producer is notified, if the water mark is configured. 111 112This mechanism can be used, for example, to exert a back pressure on I/O to inform the LAN to PAUSE. 113 114Debug 115~~~~~ 116 117When debug is enabled (CONFIG_RTE_LIBRTE_RING_DEBUG is set), 118the library stores some per-ring statistic counters about the number of enqueues/dequeues. 119These statistics are per-core to avoid concurrent accesses or atomic operations. 120 121Use Cases 122--------- 123 124Use cases for the Ring library include: 125 126 * Communication between applications in the Intel® DPDK 127 128 * Used by memory pool allocator 129 130Anatomy of a Ring Buffer 131------------------------ 132 133This section explains how a ring buffer operates. 134The ring structure is composed of two head and tail couples; one is used by producers and one is used by the consumers. 135The figures of the following sections refer to them as prod_head, prod_tail, cons_head and cons_tail. 136 137Each figure represents a simplified state of the ring, which is a circular buffer. 138The content of the function local variables is represented on the top of the figure, 139and the content of ring structure is represented on the bottom of the figure. 140 141Single Producer Enqueue 142~~~~~~~~~~~~~~~~~~~~~~~ 143 144This section explains what occurs when a producer adds an object to the ring. 145In this example, only the producer head and tail (prod_head and prod_tail) are modified, 146and there is only one producer. 147 148The initial state is to have a prod_head and prod_tail pointing at the same location. 149 150Enqueue First Step 151^^^^^^^^^^^^^^^^^^ 152 153First, *ring->prod_head* and ring->cons_tail are copied in local variables. 154The prod_next local variable points to the next element of the table, or several elements after in case of bulk enqueue. 155 156If there is not enough room in the ring (this is detected by checking cons_tail), it returns an error. 157 158.. image6_png has been replaced 159 160|ring-enqueue1| 161 162Enqueue Second Step 163^^^^^^^^^^^^^^^^^^^ 164 165The second step is to modify *ring->prod_head* in ring structure to point to the same location as prod_next. 166 167A pointer to the added object is copied in the ring (obj4). 168 169.. image7_png has been replaced 170 171|ring-enqueue2| 172 173Enqueue Last Step 174^^^^^^^^^^^^^^^^^ 175 176Once the object is added in the ring, ring->prod_tail in the ring structure is modified to point to the same location as *ring->prod_head*. 177The enqueue operation is finished. 178 179.. image8_png has been replaced 180 181|ring-enqueue3| 182 183Single Consumer Dequeue 184~~~~~~~~~~~~~~~~~~~~~~~ 185 186This section explains what occurs when a consumer dequeues an object from the ring. 187In this example, only the consumer head and tail (cons_head and cons_tail) are modified and there is only one consumer. 188 189The initial state is to have a cons_head and cons_tail pointing at the same location. 190 191Dequeue First Step 192^^^^^^^^^^^^^^^^^^ 193 194First, ring->cons_head and ring->prod_tail are copied in local variables. 195The cons_next local variable points to the next element of the table, or several elements after in the case of bulk dequeue. 196 197If there are not enough objects in the ring (this is detected by checking prod_tail), it returns an error. 198 199.. image9_png has been replaced 200 201|ring-dequeue1| 202 203Dequeue Second Step 204^^^^^^^^^^^^^^^^^^^ 205 206The second step is to modify ring->cons_head in the ring structure to point to the same location as cons_next. 207 208The pointer to the dequeued object (obj1) is copied in the pointer given by the user. 209 210.. image10_png has been replaced 211 212|ring-dequeue2| 213 214Dequeue Last Step 215^^^^^^^^^^^^^^^^^ 216 217Finally, ring->cons_tail in the ring structure is modified to point to the same location as ring->cons_head. 218The dequeue operation is finished. 219 220.. image11_png has been replaced 221 222|ring-dequeue3| 223 224Multiple Producers Enqueue 225~~~~~~~~~~~~~~~~~~~~~~~~~~ 226 227This section explains what occurs when two producers concurrently add an object to the ring. 228In this example, only the producer head and tail (prod_head and prod_tail) are modified. 229 230The initial state is to have a prod_head and prod_tail pointing at the same location. 231 232MC Enqueue First Step 233^^^^^^^^^^^^^^^^^^^^^ 234 235On both cores, *ring->prod_head* and ring->cons_tail are copied in local variables. 236The prod_next local variable points to the next element of the table, 237or several elements after in the case of bulk enqueue. 238 239If there is not enough room in the ring (this is detected by checking cons_tail), it returns an error. 240 241.. image12_png has been replaced 242 243|ring-mp-enqueue1| 244 245MC Enqueue Second Step 246^^^^^^^^^^^^^^^^^^^^^^ 247 248The second step is to modify ring->prod_head in the ring structure to point to the same location as prod_next. 249This operation is done using a Compare And Swap (CAS) instruction, which does the following operations atomically: 250 251* If ring->prod_head is different to local variable prod_head, 252 the CAS operation fails, and the code restarts at first step. 253 254* Otherwise, ring->prod_head is set to local prod_next, 255 the CAS operation is successful, and processing continues. 256 257In the figure, the operation succeeded on core 1, and step one restarted on core 2. 258 259.. image13_png has been replaced 260 261|ring-mp-enqueue2| 262 263MC Enqueue Third Step 264^^^^^^^^^^^^^^^^^^^^^ 265 266The CAS operation is retried on core 2 with success. 267 268The core 1 updates one element of the ring(obj4), and the core 2 updates another one (obj5). 269 270.. image14_png has been replaced 271 272|ring-mp-enqueue3| 273 274MC Enqueue Fourth Step 275^^^^^^^^^^^^^^^^^^^^^^ 276 277Each core now wants to update ring->prod_tail. 278A core can only update it if ring->prod_tail is equal to the prod_head local variable. 279This is only true on core 1. The operation is finished on core 1. 280 281.. image15_png has been replaced 282 283|ring-mp-enqueue4| 284 285MC Enqueue Last Step 286^^^^^^^^^^^^^^^^^^^^ 287 288Once ring->prod_tail is updated by core 1, core 2 is allowed to update it too. 289The operation is also finished on core 2. 290 291.. image16_png has been replaced 292 293|ring-mp-enqueue5| 294 295Modulo 32-bit Indexes 296~~~~~~~~~~~~~~~~~~~~~ 297 298In the preceding figures, the prod_head, prod_tail, cons_head and cons_tail indexes are represented by arrows. 299In the actual implementation, these values are not between 0 and size(ring)-1 as would be assumed. 300The indexes are between 0 and 2^32 -1, and we mask their value when we access the pointer table (the ring itself). 30132-bit modulo also implies that operations on indexes (such as, add/subtract) will automatically do 2^32 modulo 302if the result overflows the 32-bit number range. 303 304The following are two examples that help to explain how indexes are used in a ring. 305 306.. note:: 307 308 To simplify the explanation, operations with modulo 16-bit are used instead of modulo 32-bit. 309 In addition, the four indexes are defined as unsigned 16-bit integers, 310 as opposed to unsigned 32-bit integers in the more realistic case. 311 312.. image17_png has been replaced 313 314|ring-modulo1| 315 316This ring contains 11000 entries. 317 318.. image18_png has been replaced 319 320|ring-modulo2| 321 322This ring contains 12536 entries. 323 324.. note:: 325 326 For ease of understanding, we use modulo 65536 operations in the above examples. 327 In real execution cases, this is redundant for low efficiency, but is done automatically when the result overflows. 328 329The code always maintains a distance between producer and consumer between 0 and size(ring)-1. 330Thanks to this property, we can do subtractions between 2 index values in a modulo-32bit base: 331that's why the overflow of the indexes is not a problem. 332 333At any time, entries and free_entries are between 0 and size(ring)-1, 334even if only the first term of subtraction has overflowed: 335 336.. code-block:: c 337 338 uint32_t entries = (prod_tail - cons_head); 339 uint32_t free_entries = (mask + cons_tail -prod_head); 340 341References 342---------- 343 344 * `bufring.h in FreeBSD <http://svn.freebsd.org/viewvc/base/release/8.0.0/sys/sys/buf_ring.h?revision=199625&view=markup>`_ (version 8) 345 346 * `bufring.c in FreeBSD <http://svn.freebsd.org/viewvc/base/release/8.0.0/sys/kern/subr_bufring.c?revision=199625&view=markup>`_ (version 8) 347 348 * `Linux Lockless Ring Buffer Design <http://lwn.net/Articles/340400/>`_ 349 350.. |ring1| image:: img/ring1.svg 351 352.. |ring-enqueue1| image:: img/ring-enqueue1.svg 353 354.. |ring-enqueue2| image:: img/ring-enqueue2.svg 355 356.. |ring-enqueue3| image:: img/ring-enqueue3.svg 357 358.. |ring-dequeue1| image:: img/ring-dequeue1.svg 359 360.. |ring-dequeue2| image:: img/ring-dequeue2.svg 361 362.. |ring-dequeue3| image:: img/ring-dequeue3.svg 363 364.. |ring-mp-enqueue1| image:: img/ring-mp-enqueue1.svg 365 366.. |ring-mp-enqueue2| image:: img/ring-mp-enqueue2.svg 367 368.. |ring-mp-enqueue3| image:: img/ring-mp-enqueue3.svg 369 370.. |ring-mp-enqueue4| image:: img/ring-mp-enqueue4.svg 371 372.. |ring-mp-enqueue5| image:: img/ring-mp-enqueue5.svg 373 374.. |ring-modulo1| image:: img/ring-modulo1.svg 375 376.. |ring-modulo2| image:: img/ring-modulo2.svg 377
