From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <smonroy@ecsmtp.ir.intel.com>
Received: from mga14.intel.com (mga14.intel.com [192.55.52.115])
by dpdk.org (Postfix) with ESMTP id 18089255
for <dev@dpdk.org>; Fri, 6 Feb 2015 16:06:08 +0100 (CET)
Received: from orsmga002.jf.intel.com ([10.7.209.21])
by fmsmga103.fm.intel.com with ESMTP; 06 Feb 2015 06:59:21 -0800
X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.09,529,1418112000"; d="scan'208";a="682009332"
Received: from irvmail001.ir.intel.com ([163.33.26.43])
by orsmga002.jf.intel.com with ESMTP; 06 Feb 2015 07:06:06 -0800
Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com
[10.237.217.46])
by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id
t16F65JK004390 for <dev@dpdk.org>; Fri, 6 Feb 2015 15:06:05 GMT
Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1])
by sivswdev02.ir.intel.com with ESMTP id t16F64hM003874
for <dev@dpdk.org>; Fri, 6 Feb 2015 15:06:04 GMT
Received: (from smonroy@localhost)
by sivswdev02.ir.intel.com with id t16F64Up003870
for dev@dpdk.org; Fri, 6 Feb 2015 15:06:04 GMT
From: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>
To: dev@dpdk.org
Date: Fri, 6 Feb 2015 15:06:03 +0000
Message-Id: <1423235164-3808-5-git-send-email-sergio.gonzalez.monroy@intel.com>
X-Mailer: git-send-email 1.8.5.4
In-Reply-To: <1423235164-3808-1-git-send-email-sergio.gonzalez.monroy@intel.com>
References: <1422623694-6430-1-git-send-email-sergio.gonzalez.monroy@intel.com>
<1423235164-3808-1-git-send-email-sergio.gonzalez.monroy@intel.com>
Subject: [dpdk-dev] [PATCH v3 4/5] doc: new reorder library description
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: patches and discussions about DPDK <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=subscribe>
X-List-Received-Date: Fri, 06 Feb 2015 15:06:09 -0000
This patch introduces a new section in the programmers guide describing
the reorder library.
Signed-off-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>
---
doc/guides/prog_guide/index.rst | 1 +
doc/guides/prog_guide/reorder_lib.rst | 115 ++++++++++++++++++++++++++++++++++
2 files changed, 116 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..bbd0521
--- /dev/null
+++ b/doc/guides/prog_guide/reorder_lib.rst
@@ -0,0 +1,115 @@
+.. BSD LICENSE
+ Copyright(c) 2015 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.
+
+.. _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 in-order
+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 to hold.
+For example, given a reorder buffer with 200 entries and a minimum sequence
+number of 350, the sequence window has low and high limits of 350 and 550
+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 accommodate early
+mbufs.
+
+
+Implementation Details
+-------------------------
+
+The reorder library is implemented as a pair of buffers, which referred to as
+the *Order* buffer and the *Ready* buffer.
+
+On an insert call, valid mbufs are inserted directly into the Order buffer and
+late mbufs are returned to the user with an error.
+
+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 that would otherwise be outside the
+reordering window.
+
+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 mbufs from at least the next 15 slots in
+the Order buffer to the Ready buffer, as long as there is room in the Ready buffer.
+Any gaps in the Order buffer at that point are skipped, and those packet will
+be reported as late packets when they arrive. The process of moving packets
+to the Ready buffer continues beyond the minimum required until a gap,
+i.e. missing mbuf, in the Order buffer is encountered.
+
+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 with
+multiple workers cores.
+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.
+
+NOTE: Currently the reorder buffer is not thread safe so the same thread is
+responsible for inserting and draining mbufs.
--
1.9.3