X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=doc%2Fguides%2Fprog_guide%2Fring_lib.rst;h=5a9b6137e7f00c3e5671ef002c6b4215f6c78229;hb=ccee5d18a470242ee86c58c9203b40ca112a49b3;hp=95f773e8fe0e7e3cfc3fdf953ed0abea991cd442;hpb=48624fd96e7c4a9603e383baa193909fea392232;p=dpdk.git diff --git a/doc/guides/prog_guide/ring_lib.rst b/doc/guides/prog_guide/ring_lib.rst index 95f773e8fe..5a9b6137e7 100644 --- a/doc/guides/prog_guide/ring_lib.rst +++ b/doc/guides/prog_guide/ring_lib.rst @@ -1,32 +1,5 @@ -.. BSD LICENSE - Copyright(c) 2010-2014 Intel Corporation. All rights reserved. - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions - are met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in - the documentation and/or other materials provided with the - distribution. - * Neither the name of Intel Corporation nor the names of its - contributors may be used to endorse or promote products derived - from this software without specific prior written permission. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2010-2014 Intel Corporation. .. _Ring_Library: @@ -72,13 +45,12 @@ The disadvantages: A simplified representation of a Ring is shown in with consumer and producer head and tail pointers to objects stored in the data structure. -.. _pg_figure_4: +.. _figure_ring1: -**Figure 4. Ring Structure** +.. figure:: img/ring1.* -.. image5_png has been replaced + Ring Structure -|ring1| References for Ring Implementation in FreeBSD* ---------------------------------------------- @@ -103,21 +75,6 @@ Name A ring is identified by a unique name. It is not possible to create two rings with the same name (rte_ring_create() returns NULL if this is attempted). -Water Marking -~~~~~~~~~~~~~ - -The ring can have a high water mark (threshold). -Once an enqueue operation reaches the high water mark, the producer is notified, if the water mark is configured. - -This mechanism can be used, for example, to exert a back pressure on I/O to inform the LAN to PAUSE. - -Debug -~~~~~ - -When debug is enabled (CONFIG_RTE_LIBRTE_RING_DEBUG is set), -the library stores some per-ring statistic counters about the number of enqueues/dequeues. -These statistics are per-core to avoid concurrent accesses or atomic operations. - Use Cases --------- @@ -155,9 +112,13 @@ The prod_next local variable points to the next element of the table, or several If there is not enough room in the ring (this is detected by checking cons_tail), it returns an error. -.. image6_png has been replaced -|ring-enqueue1| +.. _figure_ring-enqueue1: + +.. figure:: img/ring-enqueue1.* + + Enqueue first step + Enqueue Second Step ^^^^^^^^^^^^^^^^^^^ @@ -166,9 +127,13 @@ The second step is to modify *ring->prod_head* in ring structure to point to the A pointer to the added object is copied in the ring (obj4). -.. image7_png has been replaced -|ring-enqueue2| +.. _figure_ring-enqueue2: + +.. figure:: img/ring-enqueue2.* + + Enqueue second step + Enqueue Last Step ^^^^^^^^^^^^^^^^^ @@ -176,9 +141,13 @@ Enqueue Last Step Once 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*. The enqueue operation is finished. -.. image8_png has been replaced -|ring-enqueue3| +.. _figure_ring-enqueue3: + +.. figure:: img/ring-enqueue3.* + + Enqueue last step + Single Consumer Dequeue ~~~~~~~~~~~~~~~~~~~~~~~ @@ -196,9 +165,13 @@ The cons_next local variable points to the next element of the table, or several If there are not enough objects in the ring (this is detected by checking prod_tail), it returns an error. -.. image9_png has been replaced -|ring-dequeue1| +.. _figure_ring-dequeue1: + +.. figure:: img/ring-dequeue1.* + + Dequeue last step + Dequeue Second Step ^^^^^^^^^^^^^^^^^^^ @@ -207,9 +180,13 @@ The second step is to modify ring->cons_head in the ring structure to point to t The pointer to the dequeued object (obj1) is copied in the pointer given by the user. -.. image10_png has been replaced -|ring-dequeue2| +.. _figure_ring-dequeue2: + +.. figure:: img/ring-dequeue2.* + + Dequeue second step + Dequeue Last Step ^^^^^^^^^^^^^^^^^ @@ -217,9 +194,13 @@ Dequeue Last Step Finally, ring->cons_tail in the ring structure is modified to point to the same location as ring->cons_head. The dequeue operation is finished. -.. image11_png has been replaced -|ring-dequeue3| +.. _figure_ring-dequeue3: + +.. figure:: img/ring-dequeue3.* + + Dequeue last step + Multiple Producers Enqueue ~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -229,8 +210,8 @@ In this example, only the producer head and tail (prod_head and prod_tail) are m The initial state is to have a prod_head and prod_tail pointing at the same location. -MC Enqueue First Step -^^^^^^^^^^^^^^^^^^^^^ +Multiple Producers Enqueue First Step +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ On both cores, *ring->prod_head* and ring->cons_tail are copied in local variables. The prod_next local variable points to the next element of the table, @@ -238,12 +219,16 @@ or several elements after in the case of bulk enqueue. If there is not enough room in the ring (this is detected by checking cons_tail), it returns an error. -.. image12_png has been replaced -|ring-mp-enqueue1| +.. _figure_ring-mp-enqueue1: + +.. figure:: img/ring-mp-enqueue1.* + + Multiple producer enqueue first step + -MC Enqueue Second Step -^^^^^^^^^^^^^^^^^^^^^^ +Multiple Producers Enqueue Second Step +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The second step is to modify ring->prod_head in the ring structure to point to the same location as prod_next. This operation is done using a Compare And Swap (CAS) instruction, which does the following operations atomically: @@ -256,41 +241,57 @@ This operation is done using a Compare And Swap (CAS) instruction, which does th In the figure, the operation succeeded on core 1, and step one restarted on core 2. -.. image13_png has been replaced -|ring-mp-enqueue2| +.. _figure_ring-mp-enqueue2: + +.. figure:: img/ring-mp-enqueue2.* + + Multiple producer enqueue second step + -MC Enqueue Third Step -^^^^^^^^^^^^^^^^^^^^^ +Multiple Producers Enqueue Third Step +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The CAS operation is retried on core 2 with success. The core 1 updates one element of the ring(obj4), and the core 2 updates another one (obj5). -.. image14_png has been replaced -|ring-mp-enqueue3| +.. _figure_ring-mp-enqueue3: -MC Enqueue Fourth Step -^^^^^^^^^^^^^^^^^^^^^^ +.. figure:: img/ring-mp-enqueue3.* + + Multiple producer enqueue third step + + +Multiple Producers Enqueue Fourth Step +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Each core now wants to update ring->prod_tail. A core can only update it if ring->prod_tail is equal to the prod_head local variable. This is only true on core 1. The operation is finished on core 1. -.. image15_png has been replaced -|ring-mp-enqueue4| +.. _figure_ring-mp-enqueue4: + +.. figure:: img/ring-mp-enqueue4.* -MC Enqueue Last Step -^^^^^^^^^^^^^^^^^^^^ + Multiple producer enqueue fourth step + + +Multiple Producers Enqueue Last Step +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Once ring->prod_tail is updated by core 1, core 2 is allowed to update it too. The operation is also finished on core 2. -.. image16_png has been replaced -|ring-mp-enqueue5| +.. _figure_ring-mp-enqueue5: + +.. figure:: img/ring-mp-enqueue5.* + + Multiple producer enqueue last step + Modulo 32-bit Indexes ~~~~~~~~~~~~~~~~~~~~~ @@ -309,15 +310,23 @@ The following are two examples that help to explain how indexes are used in a ri In addition, the four indexes are defined as unsigned 16-bit integers, as opposed to unsigned 32-bit integers in the more realistic case. -.. image17_png has been replaced -|ring-modulo1| +.. _figure_ring-modulo1: + +.. figure:: img/ring-modulo1.* + + Modulo 32-bit indexes - Example 1 + This ring contains 11000 entries. -.. image18_png has been replaced -|ring-modulo2| +.. _figure_ring-modulo2: + +.. figure:: img/ring-modulo2.* + + Modulo 32-bit indexes - Example 2 + This ring contains 12536 entries. @@ -346,31 +355,3 @@ References * `bufring.c in FreeBSD `_ (version 8) * `Linux Lockless Ring Buffer Design `_ - -.. |ring1| image:: img/ring1.svg - -.. |ring-enqueue1| image:: img/ring-enqueue1.svg - -.. |ring-enqueue2| image:: img/ring-enqueue2.svg - -.. |ring-enqueue3| image:: img/ring-enqueue3.svg - -.. |ring-dequeue1| image:: img/ring-dequeue1.svg - -.. |ring-dequeue2| image:: img/ring-dequeue2.svg - -.. |ring-dequeue3| image:: img/ring-dequeue3.svg - -.. |ring-mp-enqueue1| image:: img/ring-mp-enqueue1.svg - -.. |ring-mp-enqueue2| image:: img/ring-mp-enqueue2.svg - -.. |ring-mp-enqueue3| image:: img/ring-mp-enqueue3.svg - -.. |ring-mp-enqueue4| image:: img/ring-mp-enqueue4.svg - -.. |ring-mp-enqueue5| image:: img/ring-mp-enqueue5.svg - -.. |ring-modulo1| image:: img/ring-modulo1.svg - -.. |ring-modulo2| image:: img/ring-modulo2.svg