[dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
Richard Sanger
rsangerarj at gmail.com
Wed Jan 7 22:09:44 CET 2015
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,
More information about the dev
mailing list