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

["Pattan, Reshma" <reshma.pattan@intel.com>]

> -----Original Message-----
> From: Neil Horman [mailto:nhorman@tuxdriver.com]
> Sent: Wednesday, January 7, 2015 5:45 PM
> To: Pattan, Reshma
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 1/3] librte_reorder: New reorder library
> 
> 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.

Hi Neil,

Sequence numbers are assigned globally by a single core , and not per port. So it is impossible to get the  packets with same sequence number.
Getting packets with same sequence number should  happen only when sequence number wraps around in same window of earlier same sequence number packet and which is not drained, but this  is unlikely as there will be sufficient wrap around times .

Thanks,
Reshma