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 33Reorder Library 34================= 35 36The Reorder Library provides a mechanism for reordering mbufs based on their 37sequence number. 38 39Operation 40---------- 41 42The reorder library is essentially a buffer that reorders mbufs. 43The user inserts out of order mbufs into the reorder buffer and pulls in-order 44mbufs from it. 45 46At a given time, the reorder buffer contains mbufs whose sequence number are 47inside the sequence window. The sequence window is determined by the minimum 48sequence number and the number of entries that the buffer was configured to hold. 49For example, given a reorder buffer with 200 entries and a minimum sequence 50number of 350, the sequence window has low and high limits of 350 and 550 51respectively. 52 53When inserting mbufs, the reorder library differentiates between valid, early 54and 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 61The reorder buffer directly returns late mbufs and tries to accommodate early 62mbufs. 63 64 65Implementation Details 66------------------------- 67 68The reorder library is implemented as a pair of buffers, which referred to as 69the *Order* buffer and the *Ready* buffer. 70 71On an insert call, valid mbufs are inserted directly into the Order buffer and 72late mbufs are returned to the user with an error. 73 74In 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. 76To that end, mbufs in the Order buffer are moved into the Ready buffer. 77Any mbufs that have not arrived yet are ignored and therefore will become 78late mbufs. 79This means that as long as there is room in the Ready buffer, the window will 80be moved to accommodate early mbufs that would otherwise be outside the 81reordering window. 82 83For example, assuming that we have a buffer of 200 entries with a 350 minimum 84sequence number, and we need to insert an early mbuf with 565 sequence number. 85That means that we would need to move the windows at least 15 positions to 86accommodate the mbuf. 87The reorder buffer would try to move mbufs from at least the next 15 slots in 88the Order buffer to the Ready buffer, as long as there is room in the Ready buffer. 89Any gaps in the Order buffer at that point are skipped, and those packet will 90be reported as late packets when they arrive. The process of moving packets 91to the Ready buffer continues beyond the minimum required until a gap, 92i.e. missing mbuf, in the Order buffer is encountered. 93 94When draining mbufs, the reorder buffer would return mbufs in the Ready 95buffer first and then from the Order buffer until a gap is found (mbufs that 96have not arrived yet). 97 98Use Case: Packet Distributor 99------------------------------- 100 101An application using the DPDK packet distributor could make use of the reorder 102library to transmit packets in the same order they were received. 103 104A basic packet distributor use case would consist of a distributor with 105multiple workers cores. 106The processing of packets by the workers is not guaranteed to be in order, 107hence a reorder buffer can be used to order as many packets as possible. 108 109In such a scenario, the distributor assigns a sequence number to mbufs before 110delivering them to the workers. 111As the workers finish processing the packets, the distributor inserts those 112mbufs into the reorder buffer and finally transmit drained mbufs. 113 114NOTE: Currently the reorder buffer is not thread safe so the same thread is 115responsible for inserting and draining mbufs. 116