[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