> -----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
