From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-f181.google.com (mail-ob0-f181.google.com [209.85.214.181]) by dpdk.org (Postfix) with ESMTP id 153CA58DD for ; Wed, 7 Jan 2015 22:09:45 +0100 (CET) Received: by mail-ob0-f181.google.com with SMTP id gq1so5137273obb.12 for ; Wed, 07 Jan 2015 13:09:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Hac6P1dW5+aiGoWx5bNKF509jjtpHGBMVNrxFX5q8tk=; b=YL6OUULcYYq08Bc5Z7BRbMHvJqD/FybTcvPVQBlyTsW9PpES7gz8o6b+pw2G44m37R z7N/hsFsnKjXxxGeJ8H0dJ9HC+zBMxTqTSgswkjB6HOm5vE53IkWZT718fiQ3y+kwLIx 0JvBbO09JhRFVFF6lkcgLKfAMwLZpxnJ+cZ59OTxmtRkWk1AdxA1T7dp/2tcTqqOiNQY MqtTQ0Kwg+y7flD9uUeryEIyPysgXwGyoNAkp+PHJdf5xbpL755UWmVV2AhB/+rlVVHU 50LlqO4fdfFVyWoBr/QDdRjzDs+e7WYb/SNT3YLIpcnngXxtr4W/MZ5ZvDx65Ixu0qUn DOxw== MIME-Version: 1.0 X-Received: by 10.202.137.70 with SMTP id l67mr3113984oid.89.1420664984355; Wed, 07 Jan 2015 13:09:44 -0800 (PST) Received: by 10.76.71.197 with HTTP; Wed, 7 Jan 2015 13:09:44 -0800 (PST) In-Reply-To: <1420648753-17136-1-git-send-email-reshma.pattan@intel.com> References: <1420648753-17136-1-git-send-email-reshma.pattan@intel.com> Date: Thu, 8 Jan 2015 10:09:44 +1300 Message-ID: From: Richard Sanger To: Reshma Pattan Content-Type: text/plain; charset=UTF-8 Cc: dev@dpdk.org Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 07 Jan 2015 21:09:45 -0000 On 8 January 2015 at 05:39, Reshma Pattan wrote: > From: Reshma Pattan > > 1)New library to provide reordering of out of ordered > mbufs based on sequence number of mbuf. Library uses reorder buffer structure > which in tern uses two circular buffers called ready and order buffers. > *rte_reorder_create API creates instance of reorder buffer. > *rte_reorder_init API initializes given reorder buffer instance. > *rte_reorder_reset API resets given reorder buffer instance. > *rte_reorder_insert API inserts the mbuf into order circular buffer. > *rte_reorder_fill_overflow moves mbufs from order buffer to ready buffer > to accomodate early packets in order buffer. > *rte_reorder_drain API provides draining facility to fetch out > reordered mbufs from order and ready buffers. > > Signed-off-by: Reshma Pattan > Signed-off-by: Richardson Bruce > --- > 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 > +#include > + > +#include > +#include > +#include > +#include > +#include > +#include > +#include > + > +#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,