1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2015 Intel Corporation. 3 4.. _Reorder_Library: 5 6Reorder Library 7================= 8 9The Reorder Library provides a mechanism for reordering mbufs based on their 10sequence number. 11 12Operation 13---------- 14 15The reorder library is essentially a buffer that reorders mbufs. 16The user inserts out of order mbufs into the reorder buffer and pulls in-order 17mbufs from it. 18 19At a given time, the reorder buffer contains mbufs whose sequence number are 20inside the sequence window. The sequence window is determined by the minimum 21sequence number and the number of entries that the buffer was configured to hold. 22For example, given a reorder buffer with 200 entries and a minimum sequence 23number of 350, the sequence window has low and high limits of 350 and 550 24respectively. 25 26When inserting mbufs, the reorder library differentiates between valid, early 27and late mbufs depending on the sequence number of the inserted mbuf: 28 29* valid: the sequence number is inside the window. 30* late: the sequence number is outside the window and less than the low limit. 31* early: the sequence number is outside the window and greater than the high 32 limit. 33 34The reorder buffer directly returns late mbufs and tries to accommodate early 35mbufs. 36 37 38Implementation Details 39------------------------- 40 41The reorder library is implemented as a pair of buffers, which referred to as 42the *Order* buffer and the *Ready* buffer. 43 44On an insert call, valid mbufs are inserted directly into the Order buffer and 45late mbufs are returned to the user with an error. 46 47In the case of early mbufs, the reorder buffer will try to move the window 48(incrementing the minimum sequence number) so that the mbuf becomes a valid one. 49To that end, mbufs in the Order buffer are moved into the Ready buffer. 50Any mbufs that have not arrived yet are ignored and therefore will become 51late mbufs. 52This means that as long as there is room in the Ready buffer, the window will 53be moved to accommodate early mbufs that would otherwise be outside the 54reordering window. 55 56For example, assuming that we have a buffer of 200 entries with a 350 minimum 57sequence number, and we need to insert an early mbuf with 565 sequence number. 58That means that we would need to move the windows at least 15 positions to 59accommodate the mbuf. 60The reorder buffer would try to move mbufs from at least the next 15 slots in 61the Order buffer to the Ready buffer, as long as there is room in the Ready buffer. 62Any gaps in the Order buffer at that point are skipped, and those packet will 63be reported as late packets when they arrive. The process of moving packets 64to the Ready buffer continues beyond the minimum required until a gap, 65i.e. missing mbuf, in the Order buffer is encountered. 66 67When draining mbufs, the reorder buffer would return mbufs in the Ready 68buffer first and then from the Order buffer until a gap is found (mbufs that 69have not arrived yet). 70 71Use Case: Packet Distributor 72------------------------------- 73 74An application using the DPDK packet distributor could make use of the reorder 75library to transmit packets in the same order they were received. 76 77A basic packet distributor use case would consist of a distributor with 78multiple workers cores. 79The processing of packets by the workers is not guaranteed to be in order, 80hence a reorder buffer can be used to order as many packets as possible. 81 82In such a scenario, the distributor assigns a sequence number to mbufs before 83delivering them to the workers. 84As the workers finish processing the packets, the distributor inserts those 85mbufs into the reorder buffer and finally transmit drained mbufs. 86 87NOTE: Currently the reorder buffer is not thread safe so the same thread is 88responsible for inserting and draining mbufs. 89