[dpdk-dev,v2,4/4] doc: new reorder library description
Commit Message
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 | 110 ++++++++++++++++++++++++++++++++++
2 files changed, 111 insertions(+)
create mode 100644 doc/guides/prog_guide/reorder_lib.rst
Comments
> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Sergio Gonzalez Monroy
> Sent: Friday, January 30, 2015 1:15 PM
> To: dev@dpdk.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 <sergio.gonzalez.monroy@intel.com>
> ---
> 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.
@@ -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
new file mode 100644
@@ -0,0 +1,110 @@
+.. BSD LICENSE
+ Copyright(c) 2010-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 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.