Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library

[Neil Horman <nhorman@tuxdriver.com>]

On Wed, Jan 07, 2015 at 04:39:11PM +0000, Reshma Pattan wrote:
> From: Reshma Pattan <reshma.pattan@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@intel.com>
>         Signed-off-by: Richardson Bruce <bruce.richardson@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
> +
> +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;
> +	}
How does this work if you get two packets with the same sequence number?  That
situation seems like it would happen frequently with your example app, and from
my read of the above, you just wind up overwriting the same pointer in ther
entries array here, which leads to silent packet loss.