[dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
Pattan, Reshma
reshma.pattan at intel.com
Thu Jan 8 17:28:15 CET 2015
> -----Original Message-----
> From: Richard Sanger [mailto:rsangerarj at gmail.com]
> Sent: Wednesday, January 7, 2015 9:10 PM
> To: Pattan, Reshma
> Cc: dev at 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 at intel.com> wrote:
> > From: Reshma Pattan <reshma.pattan at intel.com>
> >
> > 1)New library to provide reordering of out of ordered
> > mbufs based on sequence number of mbuf. Library uses reorder buffer
> structure
> > which in tern uses two circular buffers called ready and order buffers.
> > *rte_reorder_create API creates instance of reorder buffer.
> > *rte_reorder_init API initializes given reorder buffer instance.
> > *rte_reorder_reset API resets given reorder buffer instance.
> > *rte_reorder_insert API inserts the mbuf into order circular buffer.
> > *rte_reorder_fill_overflow moves mbufs from order buffer to ready
> buffer
> > to accomodate early packets in order buffer.
> > *rte_reorder_drain API provides draining facility to fetch out
> > reordered mbufs from order and ready buffers.
> >
> > Signed-off-by: Reshma Pattan <reshma.pattan at intel.com>
> > Signed-off-by: Richardson Bruce <bruce.richardson at intel.com>
> > ---
> > config/common_bsdapp | 5 +
> > config/common_linuxapp | 5 +
> > lib/Makefile | 1 +
> > lib/librte_eal/common/include/rte_tailq_elem.h | 2 +
> > lib/librte_mbuf/rte_mbuf.h | 3 +
> > lib/librte_reorder/Makefile | 50 +++
> > lib/librte_reorder/rte_reorder.c | 464 +++++++++++++++++++++++++
> > lib/librte_reorder/rte_reorder.h | 184 ++++++++++
> > 8 files changed, 714 insertions(+)
> > create mode 100644 lib/librte_reorder/Makefile create mode 100644
> > lib/librte_reorder/rte_reorder.c create mode 100644
> > lib/librte_reorder/rte_reorder.h
> >
> > diff --git a/config/common_bsdapp b/config/common_bsdapp index
> > 9177db1..e3e0e94 100644
> > --- a/config/common_bsdapp
> > +++ b/config/common_bsdapp
> > @@ -334,6 +334,11 @@ CONFIG_RTE_SCHED_PORT_N_GRINDERS=8
> > CONFIG_RTE_LIBRTE_DISTRIBUTOR=y
> >
> > #
> > +# Compile the reorder library
> > +#
> > +CONFIG_RTE_LIBRTE_REORDER=y
> > +
> > +#
> > # Compile librte_port
> > #
> > CONFIG_RTE_LIBRTE_PORT=y
> > diff --git a/config/common_linuxapp b/config/common_linuxapp index
> > 2f9643b..b5ec730 100644
> > --- a/config/common_linuxapp
> > +++ b/config/common_linuxapp
> > @@ -342,6 +342,11 @@ CONFIG_RTE_SCHED_PORT_N_GRINDERS=8
> > CONFIG_RTE_LIBRTE_DISTRIBUTOR=y
> >
> > #
> > +# Compile the reorder library
> > +#
> > +CONFIG_RTE_LIBRTE_REORDER=y
> > +
> > +#
> > # Compile librte_port
> > #
> > CONFIG_RTE_LIBRTE_PORT=y
> > diff --git a/lib/Makefile b/lib/Makefile index 0ffc982..5919d32 100644
> > --- a/lib/Makefile
> > +++ b/lib/Makefile
> > @@ -65,6 +65,7 @@ DIRS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR) +=
> > librte_distributor
> > DIRS-$(CONFIG_RTE_LIBRTE_PORT) += librte_port
> > DIRS-$(CONFIG_RTE_LIBRTE_TABLE) += librte_table
> > DIRS-$(CONFIG_RTE_LIBRTE_PIPELINE) += librte_pipeline
> > +DIRS-$(CONFIG_RTE_LIBRTE_REORDER) += librte_reorder
> >
> > ifeq ($(CONFIG_RTE_EXEC_ENV_LINUXAPP),y)
> > DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni diff --git
> > a/lib/librte_eal/common/include/rte_tailq_elem.h
> > b/lib/librte_eal/common/include/rte_tailq_elem.h
> > index f74fc7c..3013869 100644
> > --- a/lib/librte_eal/common/include/rte_tailq_elem.h
> > +++ b/lib/librte_eal/common/include/rte_tailq_elem.h
> > @@ -84,6 +84,8 @@ rte_tailq_elem(RTE_TAILQ_ACL, "RTE_ACL")
> >
> > rte_tailq_elem(RTE_TAILQ_DISTRIBUTOR, "RTE_DISTRIBUTOR")
> >
> > +rte_tailq_elem(RTE_TAILQ_REORDER, "RTE_REORDER")
> > +
> > rte_tailq_end(RTE_TAILQ_NUM)
> >
> > #undef rte_tailq_elem
> > diff --git a/lib/librte_mbuf/rte_mbuf.h b/lib/librte_mbuf/rte_mbuf.h
> > index 16059c6..ed27eb8 100644
> > --- a/lib/librte_mbuf/rte_mbuf.h
> > +++ b/lib/librte_mbuf/rte_mbuf.h
> > @@ -262,6 +262,9 @@ struct rte_mbuf {
> > uint32_t usr; /**< User defined tags. See @rte_distributor_process
> */
> > } hash; /**< hash information */
> >
> > + /* sequence number - field used in distributor and reorder library */
> > + uint32_t seqn;
> > +
> > /* second cache line - fields only used in slow path or on TX */
> > MARKER cacheline1 __rte_cache_aligned;
> >
> > diff --git a/lib/librte_reorder/Makefile b/lib/librte_reorder/Makefile
> > new file mode 100644 index 0000000..12b916f
> > --- /dev/null
> > +++ b/lib/librte_reorder/Makefile
> > @@ -0,0 +1,50 @@
> > +# BSD LICENSE
> > +#
> > +# Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
> > +# All rights reserved.
> > +#
> > +# Redistribution and use in source and binary forms, with or without
> > +# modification, are permitted provided that the following conditions
> > +# are met:
> > +#
> > +# * Redistributions of source code must retain the above copyright
> > +# notice, this list of conditions and the following disclaimer.
> > +# * Redistributions in binary form must reproduce the above copyright
> > +# notice, this list of conditions and the following disclaimer in
> > +# the documentation and/or other materials provided with the
> > +# distribution.
> > +# * Neither the name of Intel Corporation nor the names of its
> > +# contributors may be used to endorse or promote products derived
> > +# from this software without specific prior written permission.
> > +#
> > +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> CONTRIBUTORS
> > +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
> NOT
> > +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> FITNESS FOR
> > +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> COPYRIGHT
> > +# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> INCIDENTAL,
> > +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
> NOT
> > +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
> OF USE,
> > +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
> AND ON ANY
> > +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
> TORT
> > +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> THE USE
> > +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> DAMAGE.
> > +
> > +include $(RTE_SDK)/mk/rte.vars.mk
> > +
> > +# library name
> > +LIB = librte_reorder.a
> > +
> > +CFLAGS += -O3
> > +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
> > +
> > +# all source are stored in SRCS-y
> > +SRCS-$(CONFIG_RTE_LIBRTE_REORDER) := rte_reorder.c
> > +
> > +# install this header file
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_REORDER)-include := rte_reorder.h
> > +
> > +# this lib depends upon:
> > +DEPDIRS-$(CONFIG_RTE_LIBRTE_REORDER) += lib/librte_mbuf
> > +DEPDIRS-$(CONFIG_RTE_LIBRTE_REORDER) += lib/librte_eal
> > +
> > +include $(RTE_SDK)/mk/rte.lib.mk
> > diff --git a/lib/librte_reorder/rte_reorder.c
> > b/lib/librte_reorder/rte_reorder.c
> > new file mode 100644
> > index 0000000..fb3e986
> > --- /dev/null
> > +++ b/lib/librte_reorder/rte_reorder.c
> > @@ -0,0 +1,464 @@
> > +/*-
> > + * BSD LICENSE
> > + *
> > + * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
> > + * All rights reserved.
> > + *
> > + * Redistribution and use in source and binary forms, with or without
> > + * modification, are permitted provided that the following conditions
> > + * are met:
> > + *
> > + * * Redistributions of source code must retain the above copyright
> > + * notice, this list of conditions and the following disclaimer.
> > + * * Redistributions in binary form must reproduce the above copyright
> > + * notice, this list of conditions and the following disclaimer in
> > + * the documentation and/or other materials provided with the
> > + * distribution.
> > + * * Neither the name of Intel Corporation nor the names of its
> > + * contributors may be used to endorse or promote products derived
> > + * from this software without specific prior written permission.
> > + *
> > + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> CONTRIBUTORS
> > + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
> NOT
> > + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> FITNESS FOR
> > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> COPYRIGHT
> > + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> INCIDENTAL,
> > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
> NOT
> > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
> OF USE,
> > + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
> AND ON ANY
> > + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
> TORT
> > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> THE USE
> > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> DAMAGE.
> > + */
> > +
> > +#include <inttypes.h>
> > +#include <string.h>
> > +
> > +#include <rte_log.h>
> > +#include <rte_mbuf.h>
> > +#include <rte_memzone.h>
> > +#include <rte_eal_memconfig.h>
> > +#include <rte_errno.h>
> > +#include <rte_tailq.h>
> > +#include <rte_malloc.h>
> > +
> > +#include "rte_reorder.h"
> > +
> > +TAILQ_HEAD(rte_reorder_list, rte_tailq_entry);
> > +
> > +#define NO_FLAGS 0
> > +#define RTE_REORDER_PREFIX "RO_"
> > +#define RTE_REORDER_NAMESIZE 32
> > +
> > +/* Macros for printing using RTE_LOG */
> > +#define RTE_LOGTYPE_REORDER RTE_LOGTYPE_USER1
> > +
> > +/* A generic circular buffer */
> > +struct cir_buffer {
> > + unsigned int size; /**< Number of entries that can be stored */
> > + unsigned int mask; /**< [buffer_size - 1]: used for wrap-around */
> > + unsigned int head; /**< insertion point in buffer */
> > + unsigned int tail; /**< extraction point in buffer */
> > + struct rte_mbuf **entries;
> > +} __rte_cache_aligned;
> > +
> > +/* The reorder buffer data structure itself */ struct
> > +rte_reorder_buffer {
> > + char name[RTE_REORDER_NAMESIZE];
> > + uint32_t min_seqn; /**< Lowest seq. number that can be in the buffer */
> > + unsigned int memsize; /**< memory area size of reorder buffer */
> > + struct cir_buffer ready_buf; /**< temp buffer for dequeued entries */
> > + struct cir_buffer order_buf; /**< buffer used to reorder
> > +entries */ } __rte_cache_aligned;
> > +
> > +struct rte_reorder_buffer *
> > +rte_reorder_init(void *buf, unsigned int bufsize,
> > + const char *name, unsigned int size) {
> > + struct rte_reorder_buffer *b = (struct rte_reorder_buffer *)buf;
> > + const unsigned int min_bufsize = sizeof(*b) +
> > + (2 * size * sizeof(struct
> > +rte_mbuf *));
> > +
> > + struct rte_reorder_buffer *be;
> > + struct rte_tailq_entry *te;
> > + struct rte_reorder_list *reorder_list;
> > +
> > + /* check that we have an initialised tail queue */
> > + reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER,
> rte_reorder_list);
> > + if (!reorder_list) {
> > + rte_errno = E_RTE_NO_TAILQ;
> > + return NULL;
> > + }
> > +
> > + if (!rte_is_power_of_2(size)) {
> > + RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
> > + " - Not a power of 2\n");
> > + rte_errno = EINVAL;
> > + return NULL;
> > + }
> > + if (b == NULL) {
> > + RTE_LOG(ERR, REORDER, "Invalid reorder buffer parameter:"
> > + " NULL\n");
> > + rte_errno = EINVAL;
> > + return NULL;
> > + }
> > + if (name == NULL) {
> > + RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
> > + " NULL\n");
> > + rte_errno = EINVAL;
> > + return NULL;
> > + }
> > + if (bufsize < min_bufsize) {
> > + RTE_LOG(ERR, REORDER, "Invalid reorder buffer size:%u, "
> > + "should be minimum:%u\n", bufsize, min_bufsize);
> > + rte_errno = ENOMEM;
> > + return NULL;
> > + }
> > +
> > + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> > +
> > + /* guarantee there's no existing */
> > + TAILQ_FOREACH(te, reorder_list, next) {
> > + be = (struct rte_reorder_buffer *) te->data;
> > + if (strncmp(name, be->name, RTE_REORDER_NAMESIZE) == 0)
> > + break;
> > + }
> > + if (te != NULL) {
> > + b = be;
> > + memset(b, 0, bufsize);
> > + snprintf(b->name, sizeof(b->name), "%s", name);
> > + b->memsize = bufsize;
> > + b->order_buf.size = b->ready_buf.size = size;
> > + b->order_buf.mask = b->ready_buf.mask = size - 1;
> > + b->ready_buf.entries = (void *)&b[1];
> > + b->order_buf.entries = RTE_PTR_ADD(&b[1],
> > + size * sizeof(b->ready_buf.entries[0]));
> > + goto exit;
> > + }
> > +
> > + /* allocate tailq entry */
> > + te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0);
> > + if (te == NULL) {
> > + RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n");
> > + goto exit;
> > + }
> > +
> > + memset(b, 0, bufsize);
> > + snprintf(b->name, sizeof(b->name), "%s", name);
> > + b->memsize = bufsize;
> > + b->order_buf.size = b->ready_buf.size = size;
> > + b->order_buf.mask = b->ready_buf.mask = size - 1;
> > + b->ready_buf.entries = (void *)&b[1];
> > + b->order_buf.entries = RTE_PTR_ADD(&b[1],
> > + size * sizeof(b->ready_buf.entries[0]));
> > +
> > + te->data = (void *) b;
> > +
> > + TAILQ_INSERT_TAIL(reorder_list, te, next);
> > +
> > +exit:
> > + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> > + return b;
> > +}
> > +
> > +void rte_reorder_reset(struct rte_reorder_buffer *b) {
> > + unsigned int i = 0;
> > + char name[RTE_REORDER_NAMESIZE];
> > + /* Free up the mbufs of order buffer & ready buffer */
> > + for (i = 0; i < b->order_buf.size; i++) {
> > + if (b->order_buf.entries[i])
> > + rte_pktmbuf_free(b->order_buf.entries[i]);
> > + if (b->ready_buf.entries[i])
> > + rte_pktmbuf_free(b->ready_buf.entries[i]);
> > + }
> > + snprintf(name, sizeof(name), "%s", b->name);
> > + rte_reorder_init(b, b->memsize, name, b->order_buf.size); }
> > +
> > +struct rte_reorder_buffer*
> > +rte_reorder_create(const char *name, unsigned socket_id, unsigned int
> > +size) {
> > + const struct rte_memzone *mz;
> > + struct rte_reorder_buffer *b = NULL;
> > + struct rte_tailq_entry *te;
> > + struct rte_reorder_list *reorder_list;
> > + char mz_name[RTE_MEMZONE_NAMESIZE];
> > +
> > + /* check that we have an initialised tail queue */
> > + reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER,
> rte_reorder_list);
> > + if (!reorder_list) {
> > + rte_errno = E_RTE_NO_TAILQ;
> > + return NULL;
> > + }
> > +
> > + /* Check user arguments. */
> > + if (!rte_is_power_of_2(size)) {
> > + RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
> > + " - Not a power of 2\n");
> > + rte_errno = EINVAL;
> > + return NULL;
> > + }
> > + if (name == NULL) {
> > + RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
> > + " NULL\n");
> > + rte_errno = EINVAL;
> > + return NULL;
> > + }
> > +
> > + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> > +
> > + /* guarantee there's no existing */
> > + TAILQ_FOREACH(te, reorder_list, next) {
> > + b = (struct rte_reorder_buffer *) te->data;
> > + if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0)
> > + break;
> > + }
> > + if (te != NULL)
> > + goto exit;
> > +
> > + /* allocate tailq entry */
> > + te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0);
> > + if (te == NULL) {
> > + RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n");
> > + goto exit;
> > + }
> > +
> > + /* Allocate memory to store the reorder buffer structure. */
> > + const unsigned int bufsize = sizeof(struct rte_reorder_buffer) +
> > + (2 * size * sizeof(struct rte_mbuf *));
> > + snprintf(mz_name, sizeof(mz_name), RTE_REORDER_PREFIX"%s", name);
> > + mz = rte_memzone_reserve(mz_name, bufsize,
> > + socket_id, NO_FLAGS);
> > + if (mz == NULL) {
> > + RTE_LOG(ERR, REORDER, "Memzone allocation failed\n");
> > + rte_errno = ENOMEM;
> > + return NULL;
> > + }
> > + b = mz->addr;
> > + memset(b, 0, bufsize);
> > + snprintf(b->name, sizeof(b->name), "%s", name);
> > + b->memsize = bufsize;
> > + b->order_buf.size = b->ready_buf.size = size;
> > + b->order_buf.mask = b->ready_buf.mask = size - 1;
> > + b->ready_buf.entries = (void *)&b[1];
> > + b->order_buf.entries = RTE_PTR_ADD(&b[1],
> > + size * sizeof(b->ready_buf.entries[0]));
> > +
> > + te->data = (void *) b;
> > +
> > + TAILQ_INSERT_TAIL(reorder_list, te, next);
> > +
> > +exit:
> > + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> > + return b;
> > +}
> > +
> > +void
> > +rte_reorder_free(struct rte_reorder_buffer *b) {
> > + struct rte_reorder_list *reorder_list;
> > + struct rte_tailq_entry *te;
> > +
> > + /* Check user arguments. */
> > + if (b == NULL)
> > + return;
> > +
> > + /* check that we have an initialised tail queue */
> > + reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER,
> rte_reorder_list);
> > + if (!reorder_list) {
> > + rte_errno = E_RTE_NO_TAILQ;
> > + return;
> > + }
> > +
> > + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> > +
> > + /* find our tailq entry */
> > + TAILQ_FOREACH(te, reorder_list, next) {
> > + if (te->data == (void *) b)
> > + break;
> > + }
> > + if (te == NULL) {
> > + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> > + return;
> > + }
> > +
> > + TAILQ_REMOVE(reorder_list, te, next);
> > +
> > + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> > +
> > + rte_free(b);
> > + rte_free(te);
> > +}
> > +
> > +struct rte_reorder_buffer *
> > +rte_reorder_find_existing(const char *name) {
> > + struct rte_reorder_buffer *b = NULL;
> > + struct rte_tailq_entry *te;
> > + struct rte_reorder_list *reorder_list;
> > +
> > + /* check that we have an initialised tail queue */
> > + reorder_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_REORDER,
> rte_reorder_list);
> > + if (!reorder_list) {
> > + rte_errno = E_RTE_NO_TAILQ;
> > + return NULL;
> > + }
> > +
> > + rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
> > + TAILQ_FOREACH(te, reorder_list, next) {
> > + b = (struct rte_reorder_buffer *) te->data;
> > + if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0)
> > + break;
> > + }
> > + rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
> > +
> > + if (te == NULL) {
> > + rte_errno = ENOENT;
> > + return NULL;
> > + }
> > +
> > + return b;
> > +}
> > +
> > +static unsigned
> > +rte_reorder_fill_overflow(struct rte_reorder_buffer *b, unsigned n) {
> > + /*
> > + * 1. Move all ready entries that fit to the ready_buf
> > + * 2. check if we meet the minimum needed (n).
> > + * 3. If not, then skip any gaps and keep moving.
> > + * 4. If at any point the ready buffer is full, stop
> > + * 5. Return the number of positions the order_buf head has moved
> > + */
> > +
> > + struct cir_buffer *order_buf = &b->order_buf,
> > + *ready_buf = &b->ready_buf;
> > +
> > + unsigned int order_head_adv = 0;
> > +
> > + /*
> > + * move at least n packets to ready buffer, assuming ready buffer
> > + * has room for those packets.
> > + */
> > + while (order_head_adv < n &&
> > + ((ready_buf->head + 1) & ready_buf->mask) !=
> > + ready_buf->tail) {
> > +
> > + /* if we are blocked waiting on a packet, skip it */
> > + if (order_buf->entries[order_buf->head] == NULL) {
> > + order_buf->head++, order_head_adv++;
> > +
> > + if (order_buf->head == order_buf->size)
> > + order_buf->head = 0;
> > + }
> > +
> > + /* Move all ready entries that fit to the ready_buf */
> > + while (order_buf->entries[order_buf->head] != NULL) {
> > + ready_buf->entries[ready_buf->head++] =
> > +
> > + order_buf->entries[order_buf->head];
> > +
> > + order_buf->entries[order_buf->head++] = NULL;
> > + order_head_adv++;
> > +
> > + if (ready_buf->head == ready_buf->size)
> > + ready_buf->head = 0;
> > + if (order_buf->head == order_buf->size)
> > + order_buf->head = 0;
> > +
> > + if (((ready_buf->head+1) & ready_buf->mask) == ready_buf->tail)
> > + break;
> > + }
> > + }
> > +
> > + b->min_seqn += order_head_adv;
> > + /* Return the number of positions the order_buf head has moved */
> > + return order_head_adv;
> > +}
> > +
> > +int
> > +rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf
> > +*mbuf) {
> > + uint32_t offset, position;
> > + struct cir_buffer *order_buf = &b->order_buf;
> > +
> > + /*
> > + * calculate the offset from the head pointer we need to go.
> > + * The subtraction takes care of the sequence number wrapping.
> > + * For example (using 16-bit for brevity):
> > + * min_seqn = 0xFFFD
> > + * mbuf_seqn = 0x0010
> > + * offset = 0x0010 - 0xFFFD = 0x13
> > + */
> > + offset = mbuf->seqn - b->min_seqn;
> > +
> > + /*
> > + * action to take depends on offset.
> > + * offset < buffer->size: the mbuf fits within the current window of
> > + * sequence numbers we can reorder. EXPECTED CASE.
> > + * offset > buffer->size: the mbuf is outside the current window. There
> > + * are a number of cases to consider:
> > + * 1. The packet sequence is just outside the window, then we need
> > + * to see about shifting the head pointer and taking any ready
> > + * to return packets out of the ring. If there was a delayed
> > + * or dropped packet preventing drains from shifting the window
> > + * this case will skip over the dropped packet instead, and any
> > + * packets dequeued here will be returned on the next drain call.
> > + * 2. The packet sequence number is vastly outside our window, taken
> > + * here as having offset greater than twice the buffer size. In
> > + * this case, the packet is probably an old or late packet that
> > + * was previously skipped, so just enqueue the packet for
> > + * immediate return on the next drain call, or else return error.
> > + */
> > + if (offset < b->order_buf.size) {
> > + position = (order_buf->head + offset) & order_buf->mask;
> > + order_buf->entries[position] = mbuf;
> > + } else if (offset < 2 * b->order_buf.size) {
> > + if (rte_reorder_fill_overflow(b, offset - order_buf->size) <
> > + offset - order_buf->size) {
> > + /* Put in handling for enqueue straight to output */
> > + rte_errno = ENOSPC;
> > + return -1;
> > + }
> > + offset = mbuf->seqn - b->min_seqn;
> > + position = (order_buf->head + offset) & order_buf->mask;
> > + order_buf->entries[position] = mbuf;
> > + } else {
> > + /* Put in handling for enqueue straight to output */
> > + rte_errno = ERANGE;
> > + return -1;
> > + }
> > + return 0;
> > +}
> > +
> > +unsigned int
> > +rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
> > + unsigned max_mbufs)
> > +{
> > + unsigned int drain_cnt = 0;
> > +
> > + struct cir_buffer *order_buf = &b->order_buf,
> > + *ready_buf = &b->ready_buf;
> > +
> > + /* Try to fetch requested number of mbufs from ready buffer */
> > + while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head))
> {
> > + mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail++];
> > + if (ready_buf->tail == ready_buf->size)
> > + ready_buf->tail = 0;
> > + }
> > +
> > + /*
> > + * If requested number of buffers not fetched from ready buffer, fetch
> > + * remaining buffers from order buffer
> > + */
> > + while ((drain_cnt < max_mbufs) &&
> > + (order_buf->entries[order_buf->head] != NULL)) {
> > + mbufs[drain_cnt++] = order_buf->entries[order_buf->head];
> > + order_buf->entries[order_buf->head] = NULL;
> > + b->min_seqn++;
> > + order_buf->head++;
> > + if (order_buf->head == order_buf->size)
> > + order_buf->head = 0;
> > + }
> > +
> > + return drain_cnt;
> > +}
> > diff --git a/lib/librte_reorder/rte_reorder.h
> > b/lib/librte_reorder/rte_reorder.h
> > new file mode 100644
> > index 0000000..3ec7011
> > --- /dev/null
> > +++ b/lib/librte_reorder/rte_reorder.h
> > @@ -0,0 +1,184 @@
> > +/*-
> > + * BSD LICENSE
> > + *
> > + * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
> > + * All rights reserved.
> > + *
> > + * Redistribution and use in source and binary forms, with or without
> > + * modification, are permitted provided that the following conditions
> > + * are met:
> > + *
> > + * * Redistributions of source code must retain the above copyright
> > + * notice, this list of conditions and the following disclaimer.
> > + * * Redistributions in binary form must reproduce the above copyright
> > + * notice, this list of conditions and the following disclaimer in
> > + * the documentation and/or other materials provided with the
> > + * distribution.
> > + * * Neither the name of Intel Corporation nor the names of its
> > + * contributors may be used to endorse or promote products derived
> > + * from this software without specific prior written permission.
> > + *
> > + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> CONTRIBUTORS
> > + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
> NOT
> > + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> FITNESS FOR
> > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> COPYRIGHT
> > + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> INCIDENTAL,
> > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
> NOT
> > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
> OF USE,
> > + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
> AND ON ANY
> > + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
> TORT
> > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> THE USE
> > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> DAMAGE.
> > + */
> > +
> > +#ifndef _RTE_REORDER_H_
> > +#define _RTE_REORDER_H_
> > +
> > +/**
> > + * @file
> > + * RTE reorder
> > + *
> > + * Reorder library is a component which is designed to
> > + * provide ordering of out of ordered packets based on
> > + * sequence number present in mbuf.
> > + *
> > + */
> > +
> > +#ifdef __cplusplus
> > +extern "C" {
> > +#endif
> > +
> > +struct rte_reorder_buffer;
> > +
> > +/**
> > + * Create a new reorder buffer instance
> > + *
> > + * Allocate memory and initialize a new reorder buffer in that
> > + * memory, returning the reorder buffer pointer to the user
> > + *
> > + * @param name
> > + * The name to be given to the reorder buffer instance.
> > + * @param socket_id
> > + * The NUMA node on which the memory for the reorder buffer
> > + * instance is to be reserved.
> > + * @param size
> > + * Max number of elements that can be stored in the reorder buffer
> > + * @return
> > + * The initialized reorder buffer instance, or NULL on error
> > + * On error case, rte_errno will be set appropriately:
> > + * - ENOMEM - no appropriate memory area found in which to create
> memzone
> > + * - EINVAL - invalid parameters
> > + */
> > +struct rte_reorder_buffer *
> > +rte_reorder_create(const char *name, unsigned socket_id, unsigned int
> > +size);
> > +
> > +/**
> > + * Initializes given reorder buffer instance
> > + *
> > + * @param buf
> > + * Pointer to memory area where reorder buffer instance
> > + * should be initialized
> > + * @param bufsize
> > + * Size of the memory area to be used for reorder buffer instance
> > + * initialization
> > + * @param name
> > + * The name to be given to the reorder buffer instance
> > + * @param size
> > + * Number of elements that can be stored in reorder buffer
> > + * @return
> > + * The initialized reorder buffer instance, or NULL on error
> > + * On error case, rte_errno will be set appropriately:
> > + * - EINVAL - invalid parameters
> > + * - ENOMEM - not enough memory for reorder buffer instance
> > + * initialization
> > + */
> > +struct rte_reorder_buffer *
> > +rte_reorder_init(void *buf, unsigned int bufsize,
> > + const char *name, unsigned int size);
> > +
> > +/**
> > + * Reset the given reorder buffer instance with initial values.
> > + *
> > + * @param b
> > + * Reorder buffer instance which has to be reset
> > + */
> > +void rte_reorder_reset(struct rte_reorder_buffer *b);
> > +
> > +/**
> > + * Find an existing reorder buffer instance
> > + * and return a pointer to it.
> > + *
> > + * @param name
> > + * Name of the reorder buffer instacne as passed to rte_reorder_create()
> > + * @return
> > + * Pointer to reorder buffer instance or NULL if object not found with
> rte_errno
> > + * set appropriately. Possible rte_errno values include:
> > + * - ENOENT - required entry not available to return.
> > + * - E_RTE_NO_TAILQ - no tailq list could be got for the
> > + * reorder instance list
> > + */
> > +struct rte_reorder_buffer *
> > +rte_reorder_find_existing(const char *name);
> > +
> > +/**
> > + * Free reorder buffer instance.
> > + *
> > + * @param b
> > + * reorder buffer instance
> > + * @return
> > + * None
> > + */
> > +void
> > +rte_reorder_free(struct rte_reorder_buffer *b);
> > +
> > +/**
> > + * Insert given mbuf in reorder buffer in its correct position
> > + *
> > + * The given mbuf is to be reordered relative to other mbufs in the system.
> > + * The mbuf must contain a sequence number which is then used to
> > +place
> > + * the buffer in the correct position in the reorder buffer.
> > +Reordered
> > + * packets can later be taken from the buffer using the
> > +rte_reorder_drain()
> > + * API.
> > + *
> > + * @param b
> > + * Reorder buffer where the mbuf has to be inserted.
> > + * @param mbuf
> > + * mbuf of packet that needs to be inserted in reorder buffer.
> > + * @return
> > + * 0 on success
> > + * -1 on error
> > + * On error case, rte_errno will be set appropriately:
> > + * - ENOSPC - Cannot move existing mbufs from reorder buffer to
> accomodate ealry mbuf.
> > + * But mbuf can be accomodated by performing drain and then insert.
> > + * - ERANGE - Too early or late mbuf which is vastly out of
> > + * range of expected window should be ingnored without any handling.
> > + */
> > +int
> > +rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf
> > +*mbuf);
> > +
> > +/**
> > + * Fetch reordered buffers
> > + *
> > + * Returns a set of in-order buffers from the reorder buffer
> > +structure. Gaps
> > + * may be present in the sequence numbers of the mbuf if packets have
> > +been
> > + * delayed too long before reaching the reorder window, or have been
> > +previously
> > + * dropped by the system.
> > + *
> > + * @param b
> > + * Reorder buffer instance from which packets are to be drained
> > + * @param mbufs
> > + * array of mbufs where reordered packets will be inserted from reorder
> buffer
> > + * @param max_mbufs
> > + * the number of elements in the mbufs array.
> > + * @return
> > + * number of mbuf pointers written to mbufs. 0 <= N < max_mbufs.
> > + */
> > +unsigned int
> > +rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
> > + unsigned max_mbufs);
> > +
> > +#ifdef __cplusplus
> > +}
> > +#endif
> > +
> > +#endif /* _RTE_REORDER_H_ */
> > --
> > 1.8.3.1
> >
>
> 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
More information about the dev
mailing list