[dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library

[Reshma Pattan]

From: Reshma Pattan <reshma.pattan at intel.com>

            1)New library to provide reordering of out of ordered
            mbufs based on sequence number of mbuf. Library uses reorder buffer structure
            which in tern uses two circular buffers called ready and order buffers.
            *rte_reorder_create API creates instance of reorder buffer.
            *rte_reorder_init API initializes given reorder buffer instance.
            *rte_reorder_reset API resets given reorder buffer instance.
            *rte_reorder_insert API inserts the mbuf into order circular buffer.
            *rte_reorder_fill_overflow moves mbufs from order buffer to ready buffer
            to accomodate early packets in order buffer.
            *rte_reorder_drain API provides draining facility to fetch out
            reordered mbufs from order and ready buffers.

        Signed-off-by: Reshma Pattan <reshma.pattan at intel.com>
        Signed-off-by: Richardson Bruce <bruce.richardson at intel.com>
---
 config/common_bsdapp                           |   5 +
 config/common_linuxapp                         |   5 +
 lib/Makefile                                   |   1 +
 lib/librte_eal/common/include/rte_tailq_elem.h |   2 +
 lib/librte_mbuf/rte_mbuf.h                     |   3 +
 lib/librte_reorder/Makefile                    |  50 +++
 lib/librte_reorder/rte_reorder.c               | 464 +++++++++++++++++++++++++
 lib/librte_reorder/rte_reorder.h               | 184 ++++++++++
 8 files changed, 714 insertions(+)
 create mode 100644 lib/librte_reorder/Makefile
 create mode 100644 lib/librte_reorder/rte_reorder.c
 create mode 100644 lib/librte_reorder/rte_reorder.h

diff --git a/config/common_bsdapp b/config/common_bsdapp
index 9177db1..e3e0e94 100644
--- a/config/common_bsdapp
+++ b/config/common_bsdapp
@@ -334,6 +334,11 @@ CONFIG_RTE_SCHED_PORT_N_GRINDERS=8
 CONFIG_RTE_LIBRTE_DISTRIBUTOR=y
 
 #
+# Compile the reorder library
+#
+CONFIG_RTE_LIBRTE_REORDER=y
+
+#
 # Compile librte_port
 #
 CONFIG_RTE_LIBRTE_PORT=y
diff --git a/config/common_linuxapp b/config/common_linuxapp
index 2f9643b..b5ec730 100644
--- a/config/common_linuxapp
+++ b/config/common_linuxapp
@@ -342,6 +342,11 @@ CONFIG_RTE_SCHED_PORT_N_GRINDERS=8
 CONFIG_RTE_LIBRTE_DISTRIBUTOR=y
 
 #
+# Compile the reorder library
+#
+CONFIG_RTE_LIBRTE_REORDER=y
+
+#
 # Compile librte_port
 #
 CONFIG_RTE_LIBRTE_PORT=y
diff --git a/lib/Makefile b/lib/Makefile
index 0ffc982..5919d32 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -65,6 +65,7 @@ DIRS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR) += librte_distributor
 DIRS-$(CONFIG_RTE_LIBRTE_PORT) += librte_port
 DIRS-$(CONFIG_RTE_LIBRTE_TABLE) += librte_table
 DIRS-$(CONFIG_RTE_LIBRTE_PIPELINE) += librte_pipeline
+DIRS-$(CONFIG_RTE_LIBRTE_REORDER) += librte_reorder
 
 ifeq ($(CONFIG_RTE_EXEC_ENV_LINUXAPP),y)
 DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni
diff --git a/lib/librte_eal/common/include/rte_tailq_elem.h b/lib/librte_eal/common/include/rte_tailq_elem.h
index f74fc7c..3013869 100644
--- a/lib/librte_eal/common/include/rte_tailq_elem.h
+++ b/lib/librte_eal/common/include/rte_tailq_elem.h
@@ -84,6 +84,8 @@ rte_tailq_elem(RTE_TAILQ_ACL, "RTE_ACL")
 
 rte_tailq_elem(RTE_TAILQ_DISTRIBUTOR, "RTE_DISTRIBUTOR")
 
+rte_tailq_elem(RTE_TAILQ_REORDER, "RTE_REORDER")
+
 rte_tailq_end(RTE_TAILQ_NUM)
 
 #undef rte_tailq_elem
diff --git a/lib/librte_mbuf/rte_mbuf.h b/lib/librte_mbuf/rte_mbuf.h
index 16059c6..ed27eb8 100644
--- a/lib/librte_mbuf/rte_mbuf.h
+++ b/lib/librte_mbuf/rte_mbuf.h
@@ -262,6 +262,9 @@ struct rte_mbuf {
 		uint32_t usr;	  /**< User defined tags. See @rte_distributor_process */
 	} hash;                   /**< hash information */
 
+	/* sequence number - field used in distributor and reorder library */
+	uint32_t seqn;
+
 	/* second cache line - fields only used in slow path or on TX */
 	MARKER cacheline1 __rte_cache_aligned;
 
diff --git a/lib/librte_reorder/Makefile b/lib/librte_reorder/Makefile
new file mode 100644
index 0000000..12b916f
--- /dev/null
+++ b/lib/librte_reorder/Makefile
@@ -0,0 +1,50 @@
+#   BSD LICENSE
+#
+#   Copyright(c) 2010-2014 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.
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_reorder.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_REORDER) := rte_reorder.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_REORDER)-include := rte_reorder.h
+
+# this lib depends upon:
+DEPDIRS-$(CONFIG_RTE_LIBRTE_REORDER) += lib/librte_mbuf
+DEPDIRS-$(CONFIG_RTE_LIBRTE_REORDER) += lib/librte_eal
+
+include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_reorder/rte_reorder.c b/lib/librte_reorder/rte_reorder.c
new file mode 100644
index 0000000..fb3e986
--- /dev/null
+++ b/lib/librte_reorder/rte_reorder.c
@@ -0,0 +1,464 @@
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2010-2014 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.
+ */
+
+#include <inttypes.h>
+#include <string.h>
+
+#include <rte_log.h>
+#include <rte_mbuf.h>
+#include <rte_memzone.h>
+#include <rte_eal_memconfig.h>
+#include <rte_errno.h>
+#include <rte_tailq.h>
+#include <rte_malloc.h>
+
+#include "rte_reorder.h"
+
+TAILQ_HEAD(rte_reorder_list, rte_tailq_entry);
+
+#define NO_FLAGS 0
+#define RTE_REORDER_PREFIX "RO_"
+#define RTE_REORDER_NAMESIZE 32
+
+/* Macros for printing using RTE_LOG */
+#define RTE_LOGTYPE_REORDER	RTE_LOGTYPE_USER1
+
+/* A generic circular buffer */
+struct cir_buffer {
+	unsigned int size;   /**< Number of entries that can be stored */
+	unsigned int mask;   /**< [buffer_size - 1]: used for wrap-around */
+	unsigned int head;   /**< insertion point in buffer */
+	unsigned int tail;   /**< extraction point in buffer */
+	struct rte_mbuf **entries;
+} __rte_cache_aligned;
+
+/* The reorder buffer data structure itself */
+struct rte_reorder_buffer {
+	char name[RTE_REORDER_NAMESIZE];
+	uint32_t min_seqn;  /**< Lowest seq. number that can be in the buffer */
+	unsigned int memsize; /**< memory area size of reorder buffer */
+	struct cir_buffer ready_buf; /**< temp buffer for dequeued entries */
+	struct cir_buffer order_buf; /**< buffer used to reorder entries */
+} __rte_cache_aligned;
+
+struct rte_reorder_buffer *
+rte_reorder_init(void *buf, unsigned int bufsize,
+	const char *name, unsigned int size)
+{
+	struct rte_reorder_buffer *b = (struct rte_reorder_buffer *)buf;
+	const unsigned int min_bufsize = sizeof(*b) +
+					(2 * size * sizeof(struct rte_mbuf *));
+
+	struct rte_reorder_buffer *be;
+	struct rte_tailq_entry *te;
+	struct rte_reorder_list *reorder_list;
+
+	/* check that we have an initialised tail queue */
+	reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER, rte_reorder_list);
+	if (!reorder_list) {
+		rte_errno = E_RTE_NO_TAILQ;
+		return NULL;
+	}
+
+	if (!rte_is_power_of_2(size)) {
+		RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
+				" - Not a power of 2\n");
+		rte_errno = EINVAL;
+		return NULL;
+	}
+	if (b == NULL) {
+		RTE_LOG(ERR, REORDER, "Invalid reorder buffer parameter:"
+					" NULL\n");
+		rte_errno = EINVAL;
+		return NULL;
+	}
+	if (name == NULL) {
+		RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
+					" NULL\n");
+		rte_errno = EINVAL;
+		return NULL;
+	}
+	if (bufsize < min_bufsize) {
+		RTE_LOG(ERR, REORDER, "Invalid reorder buffer size:%u, "
+			"should be minimum:%u\n", bufsize, min_bufsize);
+		rte_errno = ENOMEM;
+		return NULL;
+	}
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* guarantee there's no existing */
+	TAILQ_FOREACH(te, reorder_list, next) {
+		be = (struct rte_reorder_buffer *) te->data;
+		if (strncmp(name, be->name, RTE_REORDER_NAMESIZE) == 0)
+			break;
+	}
+	if (te != NULL) {
+		b = be;
+		memset(b, 0, bufsize);
+		snprintf(b->name, sizeof(b->name), "%s", name);
+		b->memsize = bufsize;
+		b->order_buf.size = b->ready_buf.size = size;
+		b->order_buf.mask = b->ready_buf.mask = size - 1;
+		b->ready_buf.entries = (void *)&b[1];
+		b->order_buf.entries = RTE_PTR_ADD(&b[1],
+				size * sizeof(b->ready_buf.entries[0]));
+		goto exit;
+	}
+
+	/* allocate tailq entry */
+	te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0);
+	if (te == NULL) {
+		RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n");
+		goto exit;
+	}
+
+	memset(b, 0, bufsize);
+	snprintf(b->name, sizeof(b->name), "%s", name);
+	b->memsize = bufsize;
+	b->order_buf.size = b->ready_buf.size = size;
+	b->order_buf.mask = b->ready_buf.mask = size - 1;
+	b->ready_buf.entries = (void *)&b[1];
+	b->order_buf.entries = RTE_PTR_ADD(&b[1],
+			size * sizeof(b->ready_buf.entries[0]));
+
+	te->data = (void *) b;
+
+	TAILQ_INSERT_TAIL(reorder_list, te, next);
+
+exit:
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+	return b;
+}
+
+void rte_reorder_reset(struct rte_reorder_buffer *b)
+{
+	unsigned int i = 0;
+	char name[RTE_REORDER_NAMESIZE];
+	/* Free up the mbufs of order buffer & ready buffer */
+	for (i = 0; i < b->order_buf.size; i++) {
+		if (b->order_buf.entries[i])
+			rte_pktmbuf_free(b->order_buf.entries[i]);
+		if (b->ready_buf.entries[i])
+			rte_pktmbuf_free(b->ready_buf.entries[i]);
+	}
+	snprintf(name, sizeof(name), "%s", b->name);
+	rte_reorder_init(b, b->memsize, name, b->order_buf.size);
+}
+
+struct rte_reorder_buffer*
+rte_reorder_create(const char *name, unsigned socket_id, unsigned int size)
+{
+	const struct rte_memzone *mz;
+	struct rte_reorder_buffer *b = NULL;
+	struct rte_tailq_entry *te;
+	struct rte_reorder_list *reorder_list;
+	char mz_name[RTE_MEMZONE_NAMESIZE];
+
+	/* check that we have an initialised tail queue */
+	reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER, rte_reorder_list);
+	if (!reorder_list) {
+		rte_errno = E_RTE_NO_TAILQ;
+		return NULL;
+	}
+
+	/* Check user arguments. */
+	if (!rte_is_power_of_2(size)) {
+		RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
+				" - Not a power of 2\n");
+		rte_errno = EINVAL;
+		return NULL;
+	}
+	if (name == NULL) {
+		RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
+					" NULL\n");
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* guarantee there's no existing */
+	TAILQ_FOREACH(te, reorder_list, next) {
+		b = (struct rte_reorder_buffer *) te->data;
+		if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0)
+			break;
+	}
+	if (te != NULL)
+		goto exit;
+
+	/* allocate tailq entry */
+	te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0);
+	if (te == NULL) {
+		RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n");
+		goto exit;
+	}
+
+	/* Allocate memory to store the reorder buffer structure. */
+	const unsigned int bufsize = sizeof(struct rte_reorder_buffer) +
+					(2 * size * sizeof(struct rte_mbuf *));
+	snprintf(mz_name, sizeof(mz_name), RTE_REORDER_PREFIX"%s", name);
+	mz = rte_memzone_reserve(mz_name, bufsize,
+			socket_id, NO_FLAGS);
+	if (mz == NULL) {
+		RTE_LOG(ERR, REORDER, "Memzone allocation failed\n");
+		rte_errno = ENOMEM;
+		return NULL;
+	}
+	b = mz->addr;
+	memset(b, 0, bufsize);
+	snprintf(b->name, sizeof(b->name), "%s", name);
+	b->memsize = bufsize;
+	b->order_buf.size = b->ready_buf.size = size;
+	b->order_buf.mask = b->ready_buf.mask = size - 1;
+	b->ready_buf.entries = (void *)&b[1];
+	b->order_buf.entries = RTE_PTR_ADD(&b[1],
+			size * sizeof(b->ready_buf.entries[0]));
+
+	te->data = (void *) b;
+
+	TAILQ_INSERT_TAIL(reorder_list, te, next);
+
+exit:
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+	return b;
+}
+
+void
+rte_reorder_free(struct rte_reorder_buffer *b)
+{
+	struct rte_reorder_list *reorder_list;
+	struct rte_tailq_entry *te;
+
+	/* Check user arguments. */
+	if (b == NULL)
+		return;
+
+	/* check that we have an initialised tail queue */
+	reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER, rte_reorder_list);
+	if (!reorder_list) {
+		rte_errno = E_RTE_NO_TAILQ;
+		return;
+	}
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* find our tailq entry */
+	TAILQ_FOREACH(te, reorder_list, next) {
+		if (te->data == (void *) b)
+			break;
+	}
+	if (te == NULL) {
+		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+		return;
+	}
+
+	TAILQ_REMOVE(reorder_list, te, next);
+
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	rte_free(b);
+	rte_free(te);
+}
+
+struct rte_reorder_buffer *
+rte_reorder_find_existing(const char *name)
+{
+	struct rte_reorder_buffer *b = NULL;
+	struct rte_tailq_entry *te;
+	struct rte_reorder_list *reorder_list;
+
+	/* check that we have an initialised tail queue */
+	reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER, rte_reorder_list);
+	if (!reorder_list) {
+		rte_errno = E_RTE_NO_TAILQ;
+		return NULL;
+	}
+
+	rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
+	TAILQ_FOREACH(te, reorder_list, next) {
+		b = (struct rte_reorder_buffer *) te->data;
+		if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0)
+			break;
+	}
+	rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	if (te == NULL) {
+		rte_errno = ENOENT;
+		return NULL;
+	}
+
+	return b;
+}
+
+static unsigned
+rte_reorder_fill_overflow(struct rte_reorder_buffer *b, unsigned n)
+{
+	/*
+	 * 1. Move all ready entries that fit to the ready_buf
+	 * 2. check if we meet the minimum needed (n).
+	 * 3. If not, then skip any gaps and keep moving.
+	 * 4. If at any point the ready buffer is full, stop
+	 * 5. Return the number of positions the order_buf head has moved
+	 */
+
+	struct cir_buffer *order_buf = &b->order_buf,
+			*ready_buf = &b->ready_buf;
+
+	unsigned int order_head_adv = 0;
+
+	/*
+	 * move at least n packets to ready buffer, assuming ready buffer
+	 * has room for those packets.
+	 */
+	while (order_head_adv < n &&
+			((ready_buf->head + 1) & ready_buf->mask) != ready_buf->tail) {
+
+		/* if we are blocked waiting on a packet, skip it */
+		if (order_buf->entries[order_buf->head] == NULL) {
+			order_buf->head++, order_head_adv++;
+
+			if (order_buf->head == order_buf->size)
+				order_buf->head = 0;
+		}
+
+		/* Move all ready entries that fit to the ready_buf */
+		while (order_buf->entries[order_buf->head] != NULL) {
+			ready_buf->entries[ready_buf->head++] =
+					order_buf->entries[order_buf->head];
+
+			order_buf->entries[order_buf->head++] = NULL;
+			order_head_adv++;
+
+			if (ready_buf->head == ready_buf->size)
+				ready_buf->head = 0;
+			if (order_buf->head == order_buf->size)
+				order_buf->head = 0;
+
+			if (((ready_buf->head+1) & ready_buf->mask) == ready_buf->tail)
+				break;
+		}
+	}
+
+	b->min_seqn += order_head_adv;
+	/* Return the number of positions the order_buf head has moved */
+	return order_head_adv;
+}
+
+int
+rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf *mbuf)
+{
+	uint32_t offset, position;
+	struct cir_buffer *order_buf = &b->order_buf;
+
+	/*
+	 * calculate the offset from the head pointer we need to go.
+	 * The subtraction takes care of the sequence number wrapping.
+	 * For example (using 16-bit for brevity):
+	 *	min_seqn  = 0xFFFD
+	 *	mbuf_seqn = 0x0010
+	 *	offset    = 0x0010 - 0xFFFD = 0x13
+	 */
+	offset = mbuf->seqn - b->min_seqn;
+
+	/*
+	 * action to take depends on offset.
+	 * offset < buffer->size: the mbuf fits within the current window of
+	 *    sequence numbers we can reorder. EXPECTED CASE.
+	 * offset > buffer->size: the mbuf is outside the current window. There
+	 *    are a number of cases to consider:
+	 *    1. The packet sequence is just outside the window, then we need
+	 *       to see about shifting the head pointer and taking any ready
+	 *       to return packets out of the ring. If there was a delayed
+	 *       or dropped packet preventing drains from shifting the window
+	 *       this case will skip over the dropped packet instead, and any
+	 *       packets dequeued here will be returned on the next drain call.
+	 *    2. The packet sequence number is vastly outside our window, taken
+	 *       here as having offset greater than twice the buffer size. In
+	 *       this case, the packet is probably an old or late packet that
+	 *       was previously skipped, so just enqueue the packet for
+	 *       immediate return on the next drain call, or else return error.
+	 */
+	if (offset < b->order_buf.size) {
+		position = (order_buf->head + offset) & order_buf->mask;
+		order_buf->entries[position] = mbuf;
+	} else if (offset < 2 * b->order_buf.size) {
+		if (rte_reorder_fill_overflow(b, offset - order_buf->size) <
+				offset - order_buf->size) {
+			/* Put in handling for enqueue straight to output */
+			rte_errno = ENOSPC;
+			return -1;
+		}
+		offset = mbuf->seqn - b->min_seqn;
+		position = (order_buf->head + offset) & order_buf->mask;
+		order_buf->entries[position] = mbuf;
+	} else {
+		/* Put in handling for enqueue straight to output */
+		rte_errno = ERANGE;
+		return -1;
+	}
+	return 0;
+}
+
+unsigned int
+rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
+		unsigned max_mbufs)
+{
+	unsigned int drain_cnt = 0;
+
+	struct cir_buffer *order_buf = &b->order_buf,
+			*ready_buf = &b->ready_buf;
+
+	/* Try to fetch requested number of mbufs from ready buffer */
+	while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head)) {
+		mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail++];
+		if (ready_buf->tail == ready_buf->size)
+			ready_buf->tail = 0;
+	}
+
+	/*
+	 * If requested number of buffers not fetched from ready buffer, fetch
+	 * remaining buffers from order buffer
+	 */
+	while ((drain_cnt < max_mbufs) &&
+			(order_buf->entries[order_buf->head] != NULL)) {
+		mbufs[drain_cnt++] = order_buf->entries[order_buf->head];
+		order_buf->entries[order_buf->head] = NULL;
+		b->min_seqn++;
+		order_buf->head++;
+		if (order_buf->head == order_buf->size)
+			order_buf->head = 0;
+	}
+
+	return drain_cnt;
+}
diff --git a/lib/librte_reorder/rte_reorder.h b/lib/librte_reorder/rte_reorder.h
new file mode 100644
index 0000000..3ec7011
--- /dev/null
+++ b/lib/librte_reorder/rte_reorder.h
@@ -0,0 +1,184 @@
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2010-2014 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.
+ */
+
+#ifndef _RTE_REORDER_H_
+#define _RTE_REORDER_H_
+
+/**
+ * @file
+ * RTE reorder
+ *
+ * Reorder library is a component which is designed to
+ * provide ordering of out of ordered packets based on
+ * sequence number present in mbuf.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct rte_reorder_buffer;
+
+/**
+ * Create a new reorder buffer instance
+ *
+ * Allocate memory and initialize a new reorder buffer in that
+ * memory, returning the reorder buffer pointer to the user
+ *
+ * @param name
+ *   The name to be given to the reorder buffer instance.
+ * @param socket_id
+ *   The NUMA node on which the memory for the reorder buffer
+ *   instance is to be reserved.
+ * @param size
+ *   Max number of elements that can be stored in the reorder buffer
+ * @return
+ *   The initialized reorder buffer instance, or NULL on error
+ *   On error case, rte_errno will be set appropriately:
+ *    - ENOMEM - no appropriate memory area found in which to create memzone
+ *    - EINVAL - invalid parameters
+ */
+struct rte_reorder_buffer *
+rte_reorder_create(const char *name, unsigned socket_id, unsigned int size);
+
+/**
+ * Initializes given reorder buffer instance
+ *
+ * @param buf
+ *   Pointer to memory area where reorder buffer instance
+ *   should be initialized
+ * @param bufsize
+ *   Size of the memory area to be used for reorder buffer instance
+ *   initialization
+ * @param name
+ *   The name to be given to the reorder buffer instance
+ * @param size
+ *   Number of elements that can be stored in reorder buffer
+ * @return
+ *   The initialized reorder buffer instance, or NULL on error
+ *   On error case, rte_errno will be set appropriately:
+ *    - EINVAL - invalid parameters
+ *    - ENOMEM - not enough memory for reorder buffer instance
+ *    initialization
+ */
+struct rte_reorder_buffer *
+rte_reorder_init(void *buf, unsigned int bufsize,
+		const char *name, unsigned int size);
+
+/**
+ * Reset the given reorder buffer instance with initial values.
+ *
+ * @param b
+ *   Reorder buffer instance which has to be reset
+ */
+void rte_reorder_reset(struct rte_reorder_buffer *b);
+
+/**
+ * Find an existing reorder buffer instance
+ * and return a pointer to it.
+ *
+ * @param name
+ *   Name of the reorder buffer instacne as passed to rte_reorder_create()
+ * @return
+ *   Pointer to reorder buffer instance or NULL if object not found with rte_errno
+ *   set appropriately. Possible rte_errno values include:
+ *    - ENOENT - required entry not available to return.
+ *    - E_RTE_NO_TAILQ - no tailq list could be got for the
+ *    reorder instance list
+ */
+struct rte_reorder_buffer *
+rte_reorder_find_existing(const char *name);
+
+/**
+ * Free reorder buffer instance.
+ *
+ * @param b
+ *   reorder buffer instance
+ * @return
+ *   None
+ */
+void
+rte_reorder_free(struct rte_reorder_buffer *b);
+
+/**
+ * Insert given mbuf in reorder buffer in its correct position
+ *
+ * The given mbuf is to be reordered relative to other mbufs in the system.
+ * The mbuf must contain a sequence number which is then used to place
+ * the buffer in the correct position in the reorder buffer. Reordered
+ * packets can later be taken from the buffer using the rte_reorder_drain()
+ * API.
+ *
+ * @param b
+ *   Reorder buffer where the mbuf has to be inserted.
+ * @param mbuf
+ *   mbuf of packet that needs to be inserted in reorder buffer.
+ * @return
+ *   0 on success
+ *   -1 on error
+ *   On error case, rte_errno will be set appropriately:
+ *    - ENOSPC - Cannot move existing mbufs from reorder buffer to accomodate ealry mbuf.
+ *    But mbuf can be accomodated by performing drain and then insert.
+ *    - ERANGE - Too early or late mbuf which is vastly out of
+ *    range of expected window should be ingnored without any handling.
+ */
+int
+rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf *mbuf);
+
+/**
+ * Fetch reordered buffers
+ *
+ * Returns a set of in-order buffers from the reorder buffer structure. Gaps
+ * may be present in the sequence numbers of the mbuf if packets have been
+ * delayed too long before reaching the reorder window, or have been previously
+ * dropped by the system.
+ *
+ * @param b
+ *   Reorder buffer instance from which packets are to be drained
+ * @param mbufs
+ *   array of mbufs where reordered packets will be inserted from reorder buffer
+ * @param max_mbufs
+ *   the number of elements in the mbufs array.
+ * @return
+ *   number of mbuf pointers written to mbufs. 0 <= N < max_mbufs.
+ */
+unsigned int
+rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
+	unsigned max_mbufs);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_REORDER_H_ */
-- 
1.8.3.1