Thread (1 message) 1 message, 1 author, 2015-02-02

Re: [PATCH v2 4/4] doc: new reorder library description

From: Iremonger, Bernard <hidden>
Date: 2015-02-02 12:18:32

quoted hunk
-----Original Message-----
From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Sergio Gonzalez Monroy
Sent: Friday, January 30, 2015 1:15 PM
To: dev-VfR2kkLFssw@public.gmane.org
Subject: [dpdk-dev] [PATCH v2 4/4] doc: new reorder library description

This patch introduces a new section in the programmers guide describing the reorder library.

Signed-off-by: Sergio Gonzalez Monroy <redacted>
---
 doc/guides/prog_guide/index.rst       |   1 +
 doc/guides/prog_guide/reorder_lib.rst | 110 ++++++++++++++++++++++++++++++++++
 2 files changed, 111 insertions(+)
 create mode 100644 doc/guides/prog_guide/reorder_lib.rst
diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index
8d86dd4..de69682 100644
--- a/doc/guides/prog_guide/index.rst
+++ b/doc/guides/prog_guide/index.rst
@@ -61,6 +61,7 @@ Programmer's Guide
     lpm_lib
     lpm6_lib
     packet_distrib_lib
+    reorder_lib
     ip_fragment_reassembly_lib
     multi_proc_support
     kernel_nic_interface
diff --git a/doc/guides/prog_guide/reorder_lib.rst b/doc/guides/prog_guide/reorder_lib.rst
new file mode 100644
index 0000000..558804d
--- /dev/null
+++ b/doc/guides/prog_guide/reorder_lib.rst
@@ -0,0 +1,110 @@
+..  BSD LICENSE
+    Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
Hi Sergio,
"2010-2015" should be change to "2015" as this is a new file.
+    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.
+
+.. _Reorder_Library:
+
+Reorder Library
+=================
+
+The Reorder Library provides a mechanism for reordering mbufs based on
+their sequence number.
+
+Operation
+----------
+
+The reorder library is essentially a buffer that reorders mbufs.
+The user inserts out of order mbufs into the reorder buffer and pulls
+ordered mbufs from it.
+
+At a given time, the reorder buffer contains mbufs whose sequence
+number are inside the sequence window. The sequence window is
+determined by the minimum sequence number and the number of entries that the buffer was
configured with.
+As an example, given a reorder buffer with 200 entries and a minimum
+sequence number of 350, the sequence window has high and low limits of
+550 and 350 respectively.
+
+When inserting mbufs, the reorder library differentiates between valid,
+early and late mbufs depending on the sequence number of the inserted mbuf:
+
+* valid: the sequence number is inside the window.
+* late: the sequence number is outside the window and less than the low limit.
+* early: the sequence number is outside the window and greater than the
+high
+  limit.
+
+The reorder buffer directly returns late mbufs and tries to allocate
+early mbufs.
+
+
+Implementation Details
+-------------------------
+
+The reorder library is implemented as a double buffer, which we will
+refer to as the *Order* buffer and the *Ready* buffer.
+
+Valid mbufs are inserted directly into the Order buffer and late mbufs
+are returned to the user.
+
+In the case of early mbufs, the reorder buffer will try to move the
+window (incrementing the minimum sequence number) so that the mbuf becomes a valid one.
+To that end, mbufs in the Order buffer are moved into the Ready buffer.
+Any mbufs that have not arrived yet are ignored and therefore will
+become late mbufs.
+This means that as long as there is room in the Ready buffer, the
+window will be moved to accommodate early mbufs.
+
+For example, assuming that we have a buffer of 200 entries with a 350
+minimum sequence number, and we need to insert an early mbuf with 565 sequence number.
+That means that we would need to move the windows at least 15 positions
+to accommodate the mbuf.
+The reorder buffer would try to move at least 15 mbufs from the Order
+to the Ready buffer, as long as there is room in the Ready buffer.
+
+When draining mbufs, the reorder buffer would return  mbufs in the
+Ready buffer first and then from the Order buffer until a gap is found
+(mbufs that have not arrived yet).
+
+Use Case: Packet Distributor
+-------------------------------
+
+An application using the DPDK packet distributor could make use of the
+reorder library to transmit packets in the same order they were received.
+
+A basic packet distributor use case would consist of a distributor core
+with multiple workers.
+The processing of packets by the workers is not guaranteed to be in
+order, hence a reorder buffer can be used to order as many packets as possible.
+
+In such a scenario, the distributor assigns a sequence number to mbufs
+before delivering them to the workers.
+As the workers finish processing the packets, the distributor inserts
+those mbufs into the reorder buffer and finally transmit drained mbufs.
+
+Currently the reorder buffer is not thread safe so the same thread is
+responsible for inserting and draining mbufs.
--
1.9.3
Regards,

Bernard.
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help