From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id DAE889AA1 for ; Wed, 11 Feb 2015 14:07:58 +0100 (CET) Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by orsmga101.jf.intel.com with ESMTP; 11 Feb 2015 05:07:38 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.09,558,1418112000"; d="scan'208";a="664831076" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga001.fm.intel.com with ESMTP; 11 Feb 2015 05:07:36 -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 t1BD7a1b031676 for ; Wed, 11 Feb 2015 13:07:36 GMT Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t1BD7awD023986 for ; Wed, 11 Feb 2015 13:07:36 GMT Received: (from smonroy@localhost) by sivswdev02.ir.intel.com with id t1BD7akJ023982 for dev@dpdk.org; Wed, 11 Feb 2015 13:07:36 GMT From: Sergio Gonzalez Monroy To: dev@dpdk.org Date: Wed, 11 Feb 2015 13:07:34 +0000 Message-Id: <1423660055-23920-5-git-send-email-sergio.gonzalez.monroy@intel.com> X-Mailer: git-send-email 1.8.5.4 In-Reply-To: <1423660055-23920-1-git-send-email-sergio.gonzalez.monroy@intel.com> References: <1423235164-3808-1-git-send-email-sergio.gonzalez.monroy@intel.com> <1423660055-23920-1-git-send-email-sergio.gonzalez.monroy@intel.com> Subject: [dpdk-dev] [PATCH v4 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 11 Feb 2015 13:07:59 -0000 This patch introduces a new section in the programmers guide describing the reorder library. Signed-off-by: Sergio Gonzalez Monroy --- 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