[dpdk-dev,1/3] librte_reorder: New reorder library
Commit Message
From: Reshma Pattan <reshma.pattan@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@intel.com>
Signed-off-by: Richardson Bruce <bruce.richardson@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
Comments
On Wed, Jan 07, 2015 at 04:39:11PM +0000, Reshma Pattan wrote:
> From: Reshma Pattan <reshma.pattan@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@intel.com>
> Signed-off-by: Richardson Bruce <bruce.richardson@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
> +
> +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;
> + }
How does this work if you get two packets with the same sequence number? That
situation seems like it would happen frequently with your example app, and from
my read of the above, you just wind up overwriting the same pointer in ther
entries array here, which leads to silent packet loss.
On 8 January 2015 at 05:39, Reshma Pattan <reshma.pattan@intel.com> wrote:
> From: Reshma Pattan <reshma.pattan@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@intel.com>
> Signed-off-by: Richardson Bruce <bruce.richardson@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
>
Using uint32_t's for sequence numbers is susceptible to overflow, they
should probably be uint64_t's unless there is a good reason not to.
Cheers,
> -----Original Message-----
> From: Neil Horman [mailto:nhorman@tuxdriver.com]
> Sent: Wednesday, January 7, 2015 5:45 PM
> To: Pattan, Reshma
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
>
> On Wed, Jan 07, 2015 at 04:39:11PM +0000, Reshma Pattan wrote:
> > From: Reshma Pattan <reshma.pattan@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@intel.com>
> > Signed-off-by: Richardson Bruce <bruce.richardson@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
> > +
> > +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;
> > + }
> How does this work if you get two packets with the same sequence number?
> That situation seems like it would happen frequently with your example app, and
> from my read of the above, you just wind up overwriting the same pointer in
> ther entries array here, which leads to silent packet loss.
Hi Neil,
Sequence numbers are assigned globally by a single core , and not per port. So it is impossible to get the packets with same sequence number.
Getting packets with same sequence number should happen only when sequence number wraps around in same window of earlier same sequence number packet and which is not drained, but this is unlikely as there will be sufficient wrap around times .
Thanks,
Reshma
> -----Original Message-----
> From: Richard Sanger [mailto:rsangerarj@gmail.com]
> Sent: Wednesday, January 7, 2015 9:10 PM
> To: Pattan, Reshma
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
>
> On 8 January 2015 at 05:39, Reshma Pattan <reshma.pattan@intel.com> wrote:
> > From: Reshma Pattan <reshma.pattan@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@intel.com>
> > Signed-off-by: Richardson Bruce <bruce.richardson@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
> >
>
> Using uint32_t's for sequence numbers is susceptible to overflow, they should
> probably be uint64_t's unless there is a good reason not to.
>
> Cheers,
Hi,
Using Uint64_t for seqn consumes another 4 extra bytes in mbuf on cache line0. To avoid the same it is chosen uint32_t.
Thanks,
Reshma
Hi,
2015-01-07 16:39, Reshma Pattan:
> 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@intel.com>
> Signed-off-by: Richardson Bruce <bruce.richardson@intel.com>
I think 2 things are missing in this patchset:
1) Could you show some performance numbers to compare a simple forwarding
with and without this library, in the commit log?
2) Could you add some documentation in doc/ directory for programmer's guide?
Thank you
Hi Thomas,
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Thomas Monjalon
> Sent: Tuesday, January 20, 2015 8:01 AM
> To: Pattan, Reshma
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
>
> Hi,
>
> 2015-01-07 16:39, Reshma Pattan:
> > 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@intel.com>
> > Signed-off-by: Richardson Bruce <bruce.richardson@intel.com>
>
> I think 2 things are missing in this patchset:
>
> 1) Could you show some performance numbers to compare a simple
> forwarding with and without this library, in the commit log?
>
I'm not allowed to provide specific performance numbers.
I could try to give some kind of relative performance estimate (%), but anyone else is free to provide those numbers.
> 2) Could you add some documentation in doc/ directory for programmer's
> guide?
>
I'll be sending a v2 shortly with a new entry for the programmers guide.
Thank you,
Sergio
> Thank you
> --
> Thomas
On Thu, Jan 29, 2015 at 05:35:09PM +0000, Gonzalez Monroy, Sergio wrote:
> Hi Thomas,
>
> > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Thomas Monjalon
> > Sent: Tuesday, January 20, 2015 8:01 AM
> > To: Pattan, Reshma
> > Cc: dev@dpdk.org
> > Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
> >
> > Hi,
> >
> > 2015-01-07 16:39, Reshma Pattan:
> > > 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@intel.com>
> > > Signed-off-by: Richardson Bruce <bruce.richardson@intel.com>
> >
> > I think 2 things are missing in this patchset:
> >
> > 1) Could you show some performance numbers to compare a simple
> > forwarding with and without this library, in the commit log?
> >
> I'm not allowed to provide specific performance numbers.
Can you elaborate on this? Why can you not provide specific performance numbers
from your testing? Is there some concern over the validity of the measurements?
> From: Neil Horman [mailto:nhorman@tuxdriver.com]
> Sent: Thursday, January 29, 2015 8:40 PM
> To: Gonzalez Monroy, Sergio
> Cc: Thomas Monjalon; Pattan, Reshma; dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
>
> On Thu, Jan 29, 2015 at 05:35:09PM +0000, Gonzalez Monroy, Sergio wrote:
> > Hi Thomas,
> >
> > > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Thomas
> Monjalon
> > > Sent: Tuesday, January 20, 2015 8:01 AM
> > > To: Pattan, Reshma
> > > Cc: dev@dpdk.org
> > > Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder
> > > library
> > >
> > > Hi,
> > >
> > > 2015-01-07 16:39, Reshma Pattan:
> > > > 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@intel.com>
> > > > Signed-off-by: Richardson Bruce
> > > > <bruce.richardson@intel.com>
> > >
> > > I think 2 things are missing in this patchset:
> > >
> > > 1) Could you show some performance numbers to compare a simple
> > > forwarding with and without this library, in the commit log?
> > >
> > I'm not allowed to provide specific performance numbers.
> Can you elaborate on this? Why can you not provide specific performance
> numbers from your testing? Is there some concern over the validity of the
> measurements?
Hi Neil,
As far as I know, that is exactly the reason.
Any Intel specific performance data goes through a performance validation team before being released.
Thanks,
Sergio
This series introduces the new reorder library along with unit tests,
sample app and a new entry in the programmers guide describing the library.
The library provides reordering of mbufs based on their sequence number.
As mention in the patch describing the library, one use case is the
packet distributor.
The distributor receives packets, assigns them a sequence number and sends
them to the workers.
The workers process those packets and return them to the distributor.
The distributor collects out-of-order packets from the workers and uses
this library to reorder the packets based on the sequence number they
were assigned.
v2:
- add programmers guide entry describing the library
- use malloc instead of memzone to allocate memory
- modify create and init implementation, init takes a reorder buffer as input
and create reserves memory and call init.
- update unit tests
Sergio Gonzalez Monroy (4):
reorder: new reorder library
app: New reorder unit test
examples: new sample app packet_ordering
doc: new reorder library description
app/test/Makefile | 2 +
app/test/test_reorder.c | 393 +++++++++++++++
config/common_bsdapp | 5 +
config/common_linuxapp | 5 +
doc/guides/prog_guide/index.rst | 1 +
doc/guides/prog_guide/reorder_lib.rst | 115 +++++
examples/packet_ordering/Makefile | 50 ++
examples/packet_ordering/main.c | 637 +++++++++++++++++++++++++
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 | 416 ++++++++++++++++
lib/librte_reorder/rte_reorder.h | 181 +++++++
mk/rte.app.mk | 4 +
15 files changed, 1865 insertions(+)
create mode 100644 app/test/test_reorder.c
create mode 100644 doc/guides/prog_guide/reorder_lib.rst
create mode 100644 examples/packet_ordering/Makefile
create mode 100644 examples/packet_ordering/main.c
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
This series introduces the new reorder library along with unit tests,
sample app and a new entry in the programmers guide describing the library.
The library provides reordering of mbufs based on their sequence number.
As mention in the patch describing the library, one use case is the
packet distributor.
The distributor receives packets, assigns them a sequence number and sends
them to the workers.
The workers process those packets and return them to the distributor.
The distributor collects out-of-order packets from the workers and uses
this library to reorder the packets based on the sequence number they
were assigned.
v3:
- fix copyright date
- add option to sample app to disable reordering
- add packet ordering sample guide entry
v2:
- add programmers guide entry describing the library
- use malloc instead of memzone to allocate memory
- modify create and init implementation, init takes a reorder buffer as input
and create reserves memory and call init.
- update unit tests
Sergio Gonzalez Monroy (5):
reorder: new reorder library
app: New reorder unit test
examples: new sample app packet_ordering
doc: new reorder library description
doc: new packet ordering app description
app/test/Makefile | 2 +
app/test/test_reorder.c | 393 ++++++++++++++
config/common_bsdapp | 5 +
config/common_linuxapp | 5 +
doc/guides/prog_guide/index.rst | 1 +
doc/guides/prog_guide/reorder_lib.rst | 115 ++++
doc/guides/sample_app_ug/index.rst | 1 +
doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
examples/packet_ordering/Makefile | 50 ++
examples/packet_ordering/main.c | 695 +++++++++++++++++++++++++
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 | 416 +++++++++++++++
lib/librte_reorder/rte_reorder.h | 181 +++++++
mk/rte.app.mk | 4 +
17 files changed, 2026 insertions(+)
create mode 100644 app/test/test_reorder.c
create mode 100644 doc/guides/prog_guide/reorder_lib.rst
create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
create mode 100644 examples/packet_ordering/Makefile
create mode 100644 examples/packet_ordering/main.c
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
On Fri, Feb 06, 2015 at 03:05:59PM +0000, Sergio Gonzalez Monroy wrote:
> This series introduces the new reorder library along with unit tests,
> sample app and a new entry in the programmers guide describing the library.
>
> The library provides reordering of mbufs based on their sequence number.
>
> As mention in the patch describing the library, one use case is the
> packet distributor.
> The distributor receives packets, assigns them a sequence number and sends
> them to the workers.
> The workers process those packets and return them to the distributor.
> The distributor collects out-of-order packets from the workers and uses
> this library to reorder the packets based on the sequence number they
> were assigned.
>
> v3:
> - fix copyright date
> - add option to sample app to disable reordering
> - add packet ordering sample guide entry
>
> v2:
> - add programmers guide entry describing the library
> - use malloc instead of memzone to allocate memory
> - modify create and init implementation, init takes a reorder buffer as input
> and create reserves memory and call init.
> - update unit tests
>
> Sergio Gonzalez Monroy (5):
> reorder: new reorder library
> app: New reorder unit test
> examples: new sample app packet_ordering
> doc: new reorder library description
> doc: new packet ordering app description
>
> app/test/Makefile | 2 +
> app/test/test_reorder.c | 393 ++++++++++++++
> config/common_bsdapp | 5 +
> config/common_linuxapp | 5 +
> doc/guides/prog_guide/index.rst | 1 +
> doc/guides/prog_guide/reorder_lib.rst | 115 ++++
> doc/guides/sample_app_ug/index.rst | 1 +
> doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
> examples/packet_ordering/Makefile | 50 ++
> examples/packet_ordering/main.c | 695 +++++++++++++++++++++++++
> 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 | 416 +++++++++++++++
> lib/librte_reorder/rte_reorder.h | 181 +++++++
> mk/rte.app.mk | 4 +
> 17 files changed, 2026 insertions(+)
> create mode 100644 app/test/test_reorder.c
> create mode 100644 doc/guides/prog_guide/reorder_lib.rst
> create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
> create mode 100644 examples/packet_ordering/Makefile
> create mode 100644 examples/packet_ordering/main.c
> 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
>
> --
> 1.9.3
>
>
Functionally it looks pretty good. You need to define an export map and
LIBABIVER macro in your makefile though.
Neil
> From: Neil Horman [mailto:nhorman@tuxdriver.com]
> Sent: Sunday, February 8, 2015 1:59 PM
> To: Gonzalez Monroy, Sergio
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH v3 0/5] New Reorder Library
>
> On Fri, Feb 06, 2015 at 03:05:59PM +0000, Sergio Gonzalez Monroy wrote:
> > This series introduces the new reorder library along with unit tests,
> > sample app and a new entry in the programmers guide describing the
> library.
> >
> > The library provides reordering of mbufs based on their sequence number.
> >
> > As mention in the patch describing the library, one use case is the
> > packet distributor.
> > The distributor receives packets, assigns them a sequence number and
> > sends them to the workers.
> > The workers process those packets and return them to the distributor.
> > The distributor collects out-of-order packets from the workers and
> > uses this library to reorder the packets based on the sequence number
> > they were assigned.
> >
> > v3:
> > - fix copyright date
> > - add option to sample app to disable reordering
> > - add packet ordering sample guide entry
> >
> > v2:
> > - add programmers guide entry describing the library
> > - use malloc instead of memzone to allocate memory
> > - modify create and init implementation, init takes a reorder buffer as
> input
> > and create reserves memory and call init.
> > - update unit tests
> >
> > Sergio Gonzalez Monroy (5):
> > reorder: new reorder library
> > app: New reorder unit test
> > examples: new sample app packet_ordering
> > doc: new reorder library description
> > doc: new packet ordering app description
> >
> > app/test/Makefile | 2 +
> > app/test/test_reorder.c | 393 ++++++++++++++
> > config/common_bsdapp | 5 +
> > config/common_linuxapp | 5 +
> > doc/guides/prog_guide/index.rst | 1 +
> > doc/guides/prog_guide/reorder_lib.rst | 115 ++++
> > doc/guides/sample_app_ug/index.rst | 1 +
> > doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
> > examples/packet_ordering/Makefile | 50 ++
> > examples/packet_ordering/main.c | 695
> +++++++++++++++++++++++++
> > 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 | 416 +++++++++++++++
> > lib/librte_reorder/rte_reorder.h | 181 +++++++
> > mk/rte.app.mk | 4 +
> > 17 files changed, 2026 insertions(+)
> > create mode 100644 app/test/test_reorder.c create mode 100644
> > doc/guides/prog_guide/reorder_lib.rst
> > create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
> > create mode 100644 examples/packet_ordering/Makefile create mode
> > 100644 examples/packet_ordering/main.c 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
> >
> > --
> > 1.9.3
> >
> >
> Functionally it looks pretty good. You need to define an export map and
> LIBABIVER macro in your makefile though.
> Neil
Oh yes! I did forget about the versioning.
I'll send v4 shortly.
Regards,
Sergio
This series introduces the new reorder library along with unit tests,
sample app and a new entry in the programmers guide describing the library.
The library provides reordering of mbufs based on their sequence number.
As mention in the patch describing the library, one use case is the
packet distributor.
The distributor receives packets, assigns them a sequence number and sends
them to the workers.
The workers process those packets and return them to the distributor.
The distributor collects out-of-order packets from the workers and uses
this library to reorder the packets based on the sequence number they
were assigned.
v4:
- add missing version.map and related versioning macros
v3:
- fix copyright date
- add option to sample app to disable reordering
- add packet ordering sample guide entry
v2:
- add programmers guide entry describing the library
- use malloc instead of memzone to allocate memory
- modify create and init implementation, init takes a reorder buffer as input
and create reserves memory and call init.
- update unit tests
Sergio Gonzalez Monroy (5):
reorder: new reorder library
app: New reorder unit test
examples: new sample app packet_ordering
doc: new reorder library description
doc: new packet ordering app description
app/test/Makefile | 2 +
app/test/test_reorder.c | 393 ++++++++++++++
config/common_bsdapp | 5 +
config/common_linuxapp | 5 +
doc/guides/prog_guide/index.rst | 1 +
doc/guides/prog_guide/reorder_lib.rst | 115 ++++
doc/guides/sample_app_ug/index.rst | 1 +
doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
examples/packet_ordering/Makefile | 50 ++
examples/packet_ordering/main.c | 695 +++++++++++++++++++++++++
lib/Makefile | 1 +
lib/librte_eal/common/include/rte_tailq_elem.h | 2 +
lib/librte_mbuf/rte_mbuf.h | 3 +
lib/librte_reorder/Makefile | 54 ++
lib/librte_reorder/rte_reorder.c | 416 +++++++++++++++
lib/librte_reorder/rte_reorder.h | 181 +++++++
lib/librte_reorder/rte_reorder_version.map | 13 +
mk/rte.app.mk | 4 +
18 files changed, 2043 insertions(+)
create mode 100644 app/test/test_reorder.c
create mode 100644 doc/guides/prog_guide/reorder_lib.rst
create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
create mode 100644 examples/packet_ordering/Makefile
create mode 100644 examples/packet_ordering/main.c
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
create mode 100644 lib/librte_reorder/rte_reorder_version.map
On Wed, Feb 11, 2015 at 01:07:30PM +0000, Sergio Gonzalez Monroy wrote:
> This series introduces the new reorder library along with unit tests,
> sample app and a new entry in the programmers guide describing the library.
>
> The library provides reordering of mbufs based on their sequence number.
>
> As mention in the patch describing the library, one use case is the
> packet distributor.
> The distributor receives packets, assigns them a sequence number and sends
> them to the workers.
> The workers process those packets and return them to the distributor.
> The distributor collects out-of-order packets from the workers and uses
> this library to reorder the packets based on the sequence number they
> were assigned.
>
> v4:
> - add missing version.map and related versioning macros
>
> v3:
> - fix copyright date
> - add option to sample app to disable reordering
> - add packet ordering sample guide entry
>
> v2:
> - add programmers guide entry describing the library
> - use malloc instead of memzone to allocate memory
> - modify create and init implementation, init takes a reorder buffer as input
> and create reserves memory and call init.
> - update unit tests
>
> Sergio Gonzalez Monroy (5):
> reorder: new reorder library
> app: New reorder unit test
> examples: new sample app packet_ordering
> doc: new reorder library description
> doc: new packet ordering app description
>
> app/test/Makefile | 2 +
> app/test/test_reorder.c | 393 ++++++++++++++
> config/common_bsdapp | 5 +
> config/common_linuxapp | 5 +
> doc/guides/prog_guide/index.rst | 1 +
> doc/guides/prog_guide/reorder_lib.rst | 115 ++++
> doc/guides/sample_app_ug/index.rst | 1 +
> doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
> examples/packet_ordering/Makefile | 50 ++
> examples/packet_ordering/main.c | 695 +++++++++++++++++++++++++
> lib/Makefile | 1 +
> lib/librte_eal/common/include/rte_tailq_elem.h | 2 +
> lib/librte_mbuf/rte_mbuf.h | 3 +
> lib/librte_reorder/Makefile | 54 ++
> lib/librte_reorder/rte_reorder.c | 416 +++++++++++++++
> lib/librte_reorder/rte_reorder.h | 181 +++++++
> lib/librte_reorder/rte_reorder_version.map | 13 +
> mk/rte.app.mk | 4 +
> 18 files changed, 2043 insertions(+)
> create mode 100644 app/test/test_reorder.c
> create mode 100644 doc/guides/prog_guide/reorder_lib.rst
> create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
> create mode 100644 examples/packet_ordering/Makefile
> create mode 100644 examples/packet_ordering/main.c
> 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
> create mode 100644 lib/librte_reorder/rte_reorder_version.map
>
> --
> 1.9.3
>
>
Series
Acked-by: Neil Horman <nhorman@tuxdriver.com>
On 11/02/15 13:07, Sergio Gonzalez Monroy wrote:
> This series introduces the new reorder library along with unit tests,
> sample app and a new entry in the programmers guide describing the library.
>
> The library provides reordering of mbufs based on their sequence number.
>
> As mention in the patch describing the library, one use case is the
> packet distributor.
> The distributor receives packets, assigns them a sequence number and sends
> them to the workers.
> The workers process those packets and return them to the distributor.
> The distributor collects out-of-order packets from the workers and uses
> this library to reorder the packets based on the sequence number they
> were assigned.
>
> v4:
> - add missing version.map and related versioning macros
>
> v3:
> - fix copyright date
> - add option to sample app to disable reordering
> - add packet ordering sample guide entry
>
> v2:
> - add programmers guide entry describing the library
> - use malloc instead of memzone to allocate memory
> - modify create and init implementation, init takes a reorder buffer as input
> and create reserves memory and call init.
> - update unit tests
>
> Sergio Gonzalez Monroy (5):
> reorder: new reorder library
> app: New reorder unit test
> examples: new sample app packet_ordering
> doc: new reorder library description
> doc: new packet ordering app description
>
> app/test/Makefile | 2 +
> app/test/test_reorder.c | 393 ++++++++++++++
> config/common_bsdapp | 5 +
> config/common_linuxapp | 5 +
> doc/guides/prog_guide/index.rst | 1 +
> doc/guides/prog_guide/reorder_lib.rst | 115 ++++
> doc/guides/sample_app_ug/index.rst | 1 +
> doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
> examples/packet_ordering/Makefile | 50 ++
> examples/packet_ordering/main.c | 695 +++++++++++++++++++++++++
> lib/Makefile | 1 +
> lib/librte_eal/common/include/rte_tailq_elem.h | 2 +
> lib/librte_mbuf/rte_mbuf.h | 3 +
> lib/librte_reorder/Makefile | 54 ++
> lib/librte_reorder/rte_reorder.c | 416 +++++++++++++++
> lib/librte_reorder/rte_reorder.h | 181 +++++++
> lib/librte_reorder/rte_reorder_version.map | 13 +
> mk/rte.app.mk | 4 +
> 18 files changed, 2043 insertions(+)
> create mode 100644 app/test/test_reorder.c
> create mode 100644 doc/guides/prog_guide/reorder_lib.rst
> create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
> create mode 100644 examples/packet_ordering/Makefile
> create mode 100644 examples/packet_ordering/main.c
> 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
> create mode 100644 lib/librte_reorder/rte_reorder_version.map
>
Series Acked-by: Declan Doherty <declan.doherty@intel.com>
Hi Sergio,
2015-02-11 13:07, Sergio Gonzalez Monroy:
> This series introduces the new reorder library along with unit tests,
> sample app and a new entry in the programmers guide describing the library.
>
> The library provides reordering of mbufs based on their sequence number.
>
> As mention in the patch describing the library, one use case is the
> packet distributor.
> The distributor receives packets, assigns them a sequence number and sends
> them to the workers.
> The workers process those packets and return them to the distributor.
> The distributor collects out-of-order packets from the workers and uses
> this library to reorder the packets based on the sequence number they
> were assigned.
>
> v4:
> - add missing version.map and related versioning macros
You forgot to update the MAINTAINERS file.
> v3:
> - fix copyright date
> - add option to sample app to disable reordering
> - add packet ordering sample guide entry
>
> v2:
> - add programmers guide entry describing the library
> - use malloc instead of memzone to allocate memory
> - modify create and init implementation, init takes a reorder buffer as input
> and create reserves memory and call init.
> - update unit tests
>
> Sergio Gonzalez Monroy (5):
> reorder: new reorder library
> app: New reorder unit test
> examples: new sample app packet_ordering
> doc: new reorder library description
> doc: new packet ordering app description
On 18/02/2015 14:22, Thomas Monjalon wrote:
> Hi Sergio,
>
> 2015-02-11 13:07, Sergio Gonzalez Monroy:
>> This series introduces the new reorder library along with unit tests,
>> sample app and a new entry in the programmers guide describing the library.
>>
>> The library provides reordering of mbufs based on their sequence number.
>>
>> As mention in the patch describing the library, one use case is the
>> packet distributor.
>> The distributor receives packets, assigns them a sequence number and sends
>> them to the workers.
>> The workers process those packets and return them to the distributor.
>> The distributor collects out-of-order packets from the workers and uses
>> this library to reorder the packets based on the sequence number they
>> were assigned.
>>
>> v4:
>> - add missing version.map and related versioning macros
> You forgot to update the MAINTAINERS file.
>
>> v3:
>> - fix copyright date
>> - add option to sample app to disable reordering
>> - add packet ordering sample guide entry
>>
>> v2:
>> - add programmers guide entry describing the library
>> - use malloc instead of memzone to allocate memory
>> - modify create and init implementation, init takes a reorder buffer as input
>> and create reserves memory and call init.
>> - update unit tests
>>
>> Sergio Gonzalez Monroy (5):
>> reorder: new reorder library
>> app: New reorder unit test
>> examples: new sample app packet_ordering
>> doc: new reorder library description
>> doc: new packet ordering app description
True!
I'll do v5.
Sergio
This series introduces the new reorder library along with unit tests,
sample app and a new entry in the programmers guide describing the library.
The library provides reordering of mbufs based on their sequence number.
As mention in the patch describing the library, one use case is the
packet distributor.
The distributor receives packets, assigns them a sequence number and sends
them to the workers.
The workers process those packets and return them to the distributor.
The distributor collects out-of-order packets from the workers and uses
this library to reorder the packets based on the sequence number they
were assigned.
v5:
- update MAINTAINERS
v4:
- add missing version.map and related versioning macros
v3:
- fix copyright date
- add option to sample app to disable reordering
- add packet ordering sample guide entry
v2:
- add programmers guide entry describing the library
- use malloc instead of memzone to allocate memory
- modify create and init implementation, init takes a reorder buffer as input
and create reserves memory and call init.
- update unit tests
Sergio Gonzalez Monroy (6):
reorder: new reorder library
app: New reorder unit test
examples: new sample app packet_ordering
doc: new reorder library description
doc: new packet ordering app description
MAINTAINERS: add and claim reorder
MAINTAINERS | 8 +
app/test/Makefile | 2 +
app/test/test_reorder.c | 393 ++++++++++++++
config/common_bsdapp | 5 +
config/common_linuxapp | 5 +
doc/guides/prog_guide/index.rst | 1 +
doc/guides/prog_guide/reorder_lib.rst | 115 ++++
doc/guides/sample_app_ug/index.rst | 1 +
doc/guides/sample_app_ug/packet_ordering.rst | 102 ++++
examples/packet_ordering/Makefile | 50 ++
examples/packet_ordering/main.c | 695 +++++++++++++++++++++++++
lib/Makefile | 1 +
lib/librte_eal/common/include/rte_tailq_elem.h | 2 +
lib/librte_mbuf/rte_mbuf.h | 3 +
lib/librte_reorder/Makefile | 54 ++
lib/librte_reorder/rte_reorder.c | 416 +++++++++++++++
lib/librte_reorder/rte_reorder.h | 181 +++++++
lib/librte_reorder/rte_reorder_version.map | 13 +
mk/rte.app.mk | 4 +
19 files changed, 2051 insertions(+)
create mode 100644 app/test/test_reorder.c
create mode 100644 doc/guides/prog_guide/reorder_lib.rst
create mode 100644 doc/guides/sample_app_ug/packet_ordering.rst
create mode 100644 examples/packet_ordering/Makefile
create mode 100644 examples/packet_ordering/main.c
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
create mode 100644 lib/librte_reorder/rte_reorder_version.map
> This series introduces the new reorder library along with unit tests,
> sample app and a new entry in the programmers guide describing the library.
>
> The library provides reordering of mbufs based on their sequence number.
>
> As mention in the patch describing the library, one use case is the
> packet distributor.
> The distributor receives packets, assigns them a sequence number and sends
> them to the workers.
> The workers process those packets and return them to the distributor.
> The distributor collects out-of-order packets from the workers and uses
> this library to reorder the packets based on the sequence number they
> were assigned.
>
> v5:
> - update MAINTAINERS
>
> v4:
> - add missing version.map and related versioning macros
>
> v3:
> - fix copyright date
> - add option to sample app to disable reordering
> - add packet ordering sample guide entry
>
> v2:
> - add programmers guide entry describing the library
> - use malloc instead of memzone to allocate memory
> - modify create and init implementation, init takes a reorder buffer as input
> and create reserves memory and call init.
> - update unit tests
>
> Sergio Gonzalez Monroy (6):
> reorder: new reorder library
> app: New reorder unit test
> examples: new sample app packet_ordering
> doc: new reorder library description
> doc: new packet ordering app description
> MAINTAINERS: add and claim reorder
Applied, thanks
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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;
new file mode 100644
@@ -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
new file mode 100644
@@ -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;
+}
new file mode 100644
@@ -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_ */