doc/guides/prog_guide/reorder_lib.rst

   1 ..  BSD LICENSE
   2     Copyright(c) 2015 Intel Corporation. All rights reserved.
   3     All rights reserved.
   4
   5     Redistribution and use in source and binary forms, with or without
   6     modification, are permitted provided that the following conditions
   7     are met:
   8
   9     * Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11     * Redistributions in binary form must reproduce the above copyright
  12     notice, this list of conditions and the following disclaimer in
  13     the documentation and/or other materials provided with the
  14     distribution.
  15     * Neither the name of Intel Corporation nor the names of its
  16     contributors may be used to endorse or promote products derived
  17     from this software without specific prior written permission.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30
  31 .. _Reorder_Library:
  32
  33 Reorder Library
  34 =================
  35
  36 The Reorder Library provides a mechanism for reordering mbufs based on their
  37 sequence number.
  38
  39 Operation
  40 ----------
  41
  42 The reorder library is essentially a buffer that reorders mbufs.
  43 The user inserts out of order mbufs into the reorder buffer and pulls in-order
  44 mbufs from it.
  45
  46 At a given time, the reorder buffer contains mbufs whose sequence number are
  47 inside the sequence window. The sequence window is determined by the minimum
  48 sequence number and the number of entries that the buffer was configured to hold.
  49 For example, given a reorder buffer with 200 entries and a minimum sequence
  50 number of 350, the sequence window has low and high limits of 350 and 550
  51 respectively.
  52
  53 When inserting mbufs, the reorder library differentiates between valid, early
  54 and late mbufs depending on the sequence number of the inserted mbuf:
  55
  56 * valid: the sequence number is inside the window.
  57 * late: the sequence number is outside the window and less than the low limit.
  58 * early: the sequence number is outside the window and greater than the high
  59   limit.
  60
  61 The reorder buffer directly returns late mbufs and tries to accommodate early
  62 mbufs.
  63
  64
  65 Implementation Details
  66 -------------------------
  67
  68 The reorder library is implemented as a pair of buffers, which referred to as
  69 the *Order* buffer and the *Ready* buffer.
  70
  71 On an insert call, valid mbufs are inserted directly into the Order buffer and
  72 late mbufs are returned to the user with an error.
  73
  74 In the case of early mbufs, the reorder buffer will try to move the window
  75 (incrementing the minimum sequence number) so that the mbuf becomes a valid one.
  76 To that end, mbufs in the Order buffer are moved into the Ready buffer.
  77 Any mbufs that have not arrived yet are ignored and therefore will become
  78 late mbufs.
  79 This means that as long as there is room in the Ready buffer, the window will
  80 be moved to accommodate early mbufs that would otherwise be outside the
  81 reordering window.
  82
  83 For example, assuming that we have a buffer of 200 entries with a 350 minimum
  84 sequence number, and we need to insert an early mbuf with 565 sequence number.
  85 That means that we would need to move the windows at least 15 positions to
  86 accommodate the mbuf.
  87 The reorder buffer would try to move mbufs from at least the next 15 slots in
  88 the Order buffer to the Ready buffer, as long as there is room in the Ready buffer.
  89 Any gaps in the Order buffer at that point are skipped, and those packet will
  90 be reported as late packets when they arrive. The process of moving packets
  91 to the Ready buffer continues beyond the minimum required until a gap,
  92 i.e. missing mbuf, in the Order buffer is encountered.
  93
  94 When draining mbufs, the reorder buffer would return  mbufs in the Ready
  95 buffer first and then from the Order buffer until a gap is found (mbufs that
  96 have not arrived yet).
  97
  98 Use Case: Packet Distributor
  99 -------------------------------
 100
 101 An application using the DPDK packet distributor could make use of the reorder
 102 library to transmit packets in the same order they were received.
 103
 104 A basic packet distributor use case would consist of a distributor with
 105 multiple workers cores.
 106 The processing of packets by the workers is not guaranteed to be in order,
 107 hence a reorder buffer can be used to order as many packets as possible.
 108
 109 In such a scenario, the distributor assigns a sequence number to mbufs before
 110 delivering them to the workers.
 111 As the workers finish processing the packets, the distributor inserts those
 112 mbufs into the reorder buffer and finally transmit drained mbufs.
 113
 114 NOTE: Currently the reorder buffer is not thread safe so the same thread is
 115 responsible for inserting and draining mbufs.