[PATCH 0/3] reorder: introduce new APIs

[PATCH 0/3] reorder: introduce new APIs

[Volodymyr Fialko]

This patch series provides new APIs for reorder library and test cases for
them.

Volodymyr Fialko (3):
  reorder: add new drain up to seq number API
  reorder: add ability to set min sequence number
  test/reorder: add cases to cover new API

 app/test/test_reorder.c   | 160 ++++++++++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.c | 108 +++++++++++++++++++++++++
 lib/reorder/rte_reorder.h |  43 ++++++++++
 lib/reorder/version.map   |   2 +
 4 files changed, 313 insertions(+)

-- 
2.34.1

[PATCH 1/3] reorder: add new drain up to seq number API

[Volodymyr Fialko]

Introduce new reorder drain API:
`rte_reorder_drain_up_to_seqn` - exhaustively drain all inserted mbufs
up to the given sequence number.

Currently there's no ability to force the drain from reorder buffer,
i.e. only consecutive ordered or ready packets could be drained.
New function would give user ability to drain inserted packets, without
need to wait for missing or newer packets.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 lib/reorder/rte_reorder.c | 77 +++++++++++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.h | 25 +++++++++++++
 lib/reorder/version.map   |  1 +
 3 files changed, 103 insertions(+)

diff --git a/lib/reorder/rte_reorder.c b/lib/reorder/rte_reorder.c
index 385ee479da..57cc1b286b 100644
--- a/lib/reorder/rte_reorder.c
+++ b/lib/reorder/rte_reorder.c
@@ -406,3 +406,80 @@ rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 
 	return drain_cnt;
 }
+
+/* Binary search seqn in ready buffer */
+static inline uint32_t
+ready_buffer_seqn_find(const struct cir_buffer *ready_buf, const uint32_t seqn)
+{
+	uint32_t mid, value, position, high;
+	uint32_t low = 0;
+
+	if (ready_buf->tail > ready_buf->head)
+		high = ready_buf->tail - ready_buf->head;
+	else
+		high = ready_buf->head - ready_buf->tail;
+
+	while (low <= high) {
+		mid = low + (high - low) / 2;
+		position = (ready_buf->tail + mid) & ready_buf->mask;
+		value = *rte_reorder_seqn(ready_buf->entries[position]);
+		if (seqn == value)
+			return mid;
+		else if (seqn > value)
+			low = mid + 1;
+		else
+			high = mid - 1;
+	}
+
+	return low;
+}
+
+unsigned int
+rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
+		const unsigned int max_mbufs, const rte_reorder_seqn_t seqn)
+{
+	uint32_t i, position, offset;
+	unsigned int drain_cnt = 0;
+
+	struct cir_buffer *order_buf = &b->order_buf,
+			*ready_buf = &b->ready_buf;
+
+	/* Seqn in Ready buffer */
+	if (seqn < b->min_seqn) {
+		/* All sequence numbers are higher then given */
+		if (*rte_reorder_seqn(ready_buf->entries[ready_buf->tail]) > seqn)
+			return 0;
+
+		offset = ready_buffer_seqn_find(ready_buf, seqn);
+
+		for (i = 0; (i < offset) && (drain_cnt < max_mbufs); i++) {
+			position = (ready_buf->tail + i) & ready_buf->mask;
+			mbufs[drain_cnt++] = ready_buf->entries[position];
+			ready_buf->entries[position] = NULL;
+		}
+		ready_buf->tail = (ready_buf->tail + i) & ready_buf->mask;
+
+		return drain_cnt;
+	}
+
+	/* Seqn in Order buffer, add all buffers from Ready buffer */
+	while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head)) {
+		mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail];
+		ready_buf->entries[ready_buf->tail] = NULL;
+		ready_buf->tail = (ready_buf->tail + 1) & ready_buf->mask;
+	}
+
+	/* Fetch buffers from Order buffer up to given sequence number (exclusive) */
+	offset = RTE_MIN(seqn - b->min_seqn, b->order_buf.size);
+	for (i = 0; (i < offset) && (drain_cnt < max_mbufs); i++) {
+		position = (order_buf->head + i) & order_buf->mask;
+		if (order_buf->entries[position] == NULL)
+			continue;
+		mbufs[drain_cnt++] = order_buf->entries[position];
+		order_buf->entries[position] = NULL;
+	}
+	b->min_seqn += i;
+	order_buf->head = (order_buf->head + i) & order_buf->mask;
+
+	return drain_cnt;
+}
diff --git a/lib/reorder/rte_reorder.h b/lib/reorder/rte_reorder.h
index 5abdb258e2..c5b354b53d 100644
--- a/lib/reorder/rte_reorder.h
+++ b/lib/reorder/rte_reorder.h
@@ -167,6 +167,31 @@ unsigned int
 rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 		unsigned max_mbufs);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Fetch set of reordered packets up to specified sequence number (exclusive)
+ *
+ * Returns a set of in-order packets from the reorder buffer structure.
+ * Gaps may be present since reorder buffer will try to fetch all possible packets up to given
+ * sequence number.
+ *
+ * @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.
+ * @param seqn
+ *   Sequence number up to which buffer will be drained.
+ * @return
+ *   Number of mbuf pointers written to mbufs. 0 <= N < max_mbufs.
+ */
+__rte_experimental
+unsigned int
+rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
+		unsigned int max_mbufs, rte_reorder_seqn_t seqn);
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/reorder/version.map b/lib/reorder/version.map
index e114d17730..e3f41ea7ef 100644
--- a/lib/reorder/version.map
+++ b/lib/reorder/version.map
@@ -16,4 +16,5 @@ EXPERIMENTAL {
 	global:
 
 	rte_reorder_seqn_dynfield_offset;
+	rte_reorder_drain_up_to_seqn;
 };
-- 
2.34.1

Re: [PATCH 1/3] reorder: add new drain up to seq number API

[Thomas Monjalon]

We are waiting for a detailed review.
The series could be merged without review.

Please fix cosmetic comments below and send a new version to check CI result.

20/01/2023 11:21, Volodymyr Fialko:
> Introduce new reorder drain API:
> `rte_reorder_drain_up_to_seqn` - exhaustively drain all inserted mbufs
> up to the given sequence number.
> 
> Currently there's no ability to force the drain from reorder buffer,
> i.e. only consecutive ordered or ready packets could be drained.
> New function would give user ability to drain inserted packets, without
> need to wait for missing or newer packets.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
[...]
> --- a/lib/reorder/rte_reorder.h
> +++ b/lib/reorder/rte_reorder.h
> @@ -167,6 +167,31 @@ unsigned int
>  rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
>  		unsigned max_mbufs);
>  
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Fetch set of reordered packets up to specified sequence number (exclusive)
> + *
> + * Returns a set of in-order packets from the reorder buffer structure.
> + * Gaps may be present since reorder buffer will try to fetch all possible packets up to given
> + * sequence number.
> + *
> + * @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.
> + * @param seqn
> + *   Sequence number up to which buffer will be drained.
> + * @return
> + *   Number of mbuf pointers written to mbufs. 0 <= N < max_mbufs.
> + */
> +__rte_experimental
> +unsigned int
> +rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
> +		unsigned int max_mbufs, rte_reorder_seqn_t seqn);
>  #ifdef __cplusplus

blank line missing

> --- a/lib/reorder/version.map
> +++ b/lib/reorder/version.map
> @@ -16,4 +16,5 @@ EXPERIMENTAL {
>  	global:
>  
>  	rte_reorder_seqn_dynfield_offset;
> +	rte_reorder_drain_up_to_seqn;

Please add a comment "# added in 23.03" as we do in other libs.

[PATCH 2/3] reorder: add ability to set min sequence number

[Volodymyr Fialko]

Add API `rte_reorder_min_seqn_set` to allow user to specify minimum
sequence number.
Currently sequence number of first inserted packet is used as minimum
sequence number. But for case when we want to wait for packets before
the received one this will not work.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 lib/reorder/rte_reorder.c | 31 +++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.h | 18 ++++++++++++++++++
 lib/reorder/version.map   |  1 +
 3 files changed, 50 insertions(+)

diff --git a/lib/reorder/rte_reorder.c b/lib/reorder/rte_reorder.c
index 57cc1b286b..0d4c7209f9 100644
--- a/lib/reorder/rte_reorder.c
+++ b/lib/reorder/rte_reorder.c
@@ -483,3 +483,34 @@ rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbu
 
 	return drain_cnt;
 }
+
+static bool
+rte_reorder_is_empty(const struct rte_reorder_buffer *b)
+{
+	const struct cir_buffer *order_buf = &b->order_buf, *ready_buf = &b->ready_buf;
+	unsigned int i;
+
+	/* Ready buffer does not have gaps */
+	if (ready_buf->tail != ready_buf->head)
+		return false;
+
+	/* Order buffer could have gaps, iterate */
+	for (i = 0; i < order_buf->size; i++) {
+		if (order_buf->entries[i] != NULL)
+			return false;
+	}
+
+	return true;
+}
+
+unsigned int
+rte_reorder_min_seqn_set(struct rte_reorder_buffer *b, uint32_t min_seqn)
+{
+	if (!rte_reorder_is_empty(b))
+		return -ENOTEMPTY;
+
+	b->min_seqn = min_seqn;
+	b->is_initialized = true;
+
+	return 0;
+}
diff --git a/lib/reorder/rte_reorder.h b/lib/reorder/rte_reorder.h
index c5b354b53d..9f6710bad2 100644
--- a/lib/reorder/rte_reorder.h
+++ b/lib/reorder/rte_reorder.h
@@ -192,6 +192,24 @@ __rte_experimental
 unsigned int
 rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 		unsigned int max_mbufs, rte_reorder_seqn_t seqn);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Set minimum sequence number of packet allowed to be buffered.
+ * To successfully set new value reorder buffer has to be empty(after create, reset or drain_all).
+ *
+ * @param b
+ *   Empty reorder buffer instance to modify.
+ * @param min_seqn
+ *   New sequence number to set.
+ * @return
+ *   0 on success, a negative value otherwise.
+ */
+__rte_experimental
+unsigned int
+rte_reorder_min_seqn_set(struct rte_reorder_buffer *b, uint32_t min_seqn);
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/reorder/version.map b/lib/reorder/version.map
index e3f41ea7ef..aafdf0b5ae 100644
--- a/lib/reorder/version.map
+++ b/lib/reorder/version.map
@@ -17,4 +17,5 @@ EXPERIMENTAL {
 
 	rte_reorder_seqn_dynfield_offset;
 	rte_reorder_drain_up_to_seqn;
+	rte_reorder_min_seqn_set;
 };
-- 
2.34.1

[PATCH 3/3] test/reorder: add cases to cover new API

[Volodymyr Fialko]

Add new test cases to cover `rte_reorder_drain_up_to_seqn` and
`rte_reorder_min_seqn_set`.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 app/test/test_reorder.c | 160 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 160 insertions(+)

diff --git a/app/test/test_reorder.c b/app/test/test_reorder.c
index f0714a5c18..c345a72e0c 100644
--- a/app/test/test_reorder.c
+++ b/app/test/test_reorder.c
@@ -335,6 +335,164 @@ test_reorder_drain(void)
 	return ret;
 }
 
+static void
+buffer_to_reorder_move(struct rte_mbuf **mbuf, struct rte_reorder_buffer *b)
+{
+	rte_reorder_insert(b, *mbuf);
+	*mbuf = NULL;
+}
+
+static int
+test_reorder_drain_up_to_seqn(void)
+{
+	struct rte_mempool *p = test_params->p;
+	struct rte_reorder_buffer *b = NULL;
+	const unsigned int num_bufs = 10;
+	const unsigned int size = 4;
+	unsigned int i, cnt;
+	int ret = 0;
+
+	struct rte_mbuf *bufs[num_bufs];
+	struct rte_mbuf *robufs[num_bufs];
+
+	/* initialize all robufs to NULL */
+	memset(robufs, 0, sizeof(robufs));
+
+	/* This would create a reorder buffer instance consisting of:
+	 * reorder_seq = 0
+	 * ready_buf: RB[size] = {NULL, NULL, NULL, NULL}
+	 * order_buf: OB[size] = {NULL, NULL, NULL, NULL}
+	 */
+	b = rte_reorder_create("test_drain_up_to_seqn", rte_socket_id(), size);
+	TEST_ASSERT_NOT_NULL(b, "Failed to create reorder buffer");
+
+	for (i = 0; i < num_bufs; i++) {
+		bufs[i] = rte_pktmbuf_alloc(p);
+		TEST_ASSERT_NOT_NULL(bufs[i], "Packet allocation failed\n");
+		*rte_reorder_seqn(bufs[i]) = i;
+	}
+
+	/* Insert packet with seqn 1 and 3:
+	 * RB[] = {NULL, NULL, NULL, NULL}
+	 * OB[] = {1, 2, 3, NULL}
+	 */
+	buffer_to_reorder_move(&bufs[1], b);
+	buffer_to_reorder_move(&bufs[2], b);
+	buffer_to_reorder_move(&bufs[3], b);
+	/* Draining 1, 2 */
+	cnt = rte_reorder_drain_up_to_seqn(b, robufs, num_bufs, 3);
+	if (cnt != 2) {
+		printf("%s:%d:%d: number of expected packets not drained\n",
+				__func__, __LINE__, cnt);
+		ret = -1;
+		goto exit;
+	}
+	for (i = 0; i < 2; i++)
+		rte_pktmbuf_free(robufs[i]);
+	memset(robufs, 0, sizeof(robufs));
+
+	/* Insert more packets
+	 * RB[] = {NULL, NULL, NULL, NULL}
+	 * OB[] = {3, 4, NULL, 6}
+	 */
+	buffer_to_reorder_move(&bufs[4], b);
+	buffer_to_reorder_move(&bufs[6], b);
+	/* Insert more packets to utilize Ready buffer
+	 * RB[] = {3, NULL, 5, 6}
+	 * OB[] = {NULL, NULL, 8, NULL}
+	 */
+	buffer_to_reorder_move(&bufs[8], b);
+
+	/* Drain 3 and 5 */
+	cnt = rte_reorder_drain_up_to_seqn(b, robufs, num_bufs, 6);
+	if (cnt != 2) {
+		printf("%s:%d:%d: number of expected packets not drained\n",
+				__func__, __LINE__, cnt);
+		ret = -1;
+		goto exit;
+	}
+	for (i = 0; i < 2; i++)
+		rte_pktmbuf_free(robufs[i]);
+	memset(robufs, 0, sizeof(robufs));
+
+	ret = 0;
+exit:
+	rte_reorder_free(b);
+	for (i = 0; i < num_bufs; i++) {
+		rte_pktmbuf_free(bufs[i]);
+		rte_pktmbuf_free(robufs[i]);
+	}
+	return ret;
+}
+
+static int
+test_reorder_set_seqn(void)
+{
+	struct rte_mempool *p = test_params->p;
+	struct rte_reorder_buffer *b = NULL;
+	const unsigned int num_bufs = 7;
+	const unsigned int size = 4;
+	unsigned int i;
+	int ret = 0;
+
+	struct rte_mbuf *bufs[num_bufs];
+
+	/* This would create a reorder buffer instance consisting of:
+	 * reorder_seq = 0
+	 * ready_buf: RB[size] = {NULL, NULL, NULL, NULL}
+	 * order_buf: OB[size] = {NULL, NULL, NULL, NULL}
+	 */
+	b = rte_reorder_create("test_min_seqn_set", rte_socket_id(), size);
+	TEST_ASSERT_NOT_NULL(b, "Failed to create reorder buffer");
+
+	for (i = 0; i < num_bufs; i++) {
+		bufs[i] = rte_pktmbuf_alloc(p);
+		if (bufs[i] == NULL) {
+			printf("Packet allocation failed\n");
+			goto exit;
+		}
+		*rte_reorder_seqn(bufs[i]) = i;
+	}
+
+	ret = rte_reorder_min_seqn_set(b, 5);
+	if (ret != 0) {
+		printf("%s:%d: Error in setting min sequence number\n", __func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+
+	ret = rte_reorder_insert(b, bufs[0]);
+	if (ret >= 0) {
+		printf("%s:%d: Insertion with value less the min seq number\n", __func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+
+	ret = rte_reorder_insert(b, bufs[5]);
+	if (ret != 0) {
+		printf("%s:%d: Error inserting packet with valid seqn\n", __func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+	bufs[5] = NULL;
+
+	ret = rte_reorder_min_seqn_set(b, 0);
+	if (ret >= 0) {
+		printf("%s:%d: Error in setting min sequence number with non-empty buffer\n",
+				__func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+
+	ret = 0;
+exit:
+	rte_reorder_free(b);
+	for (i = 0; i < num_bufs; i++)
+		rte_pktmbuf_free(bufs[i]);
+
+	return ret;
+}
+
 static int
 test_setup(void)
 {
@@ -385,6 +543,8 @@ static struct unit_test_suite reorder_test_suite  = {
 		TEST_CASE(test_reorder_free),
 		TEST_CASE(test_reorder_insert),
 		TEST_CASE(test_reorder_drain),
+		TEST_CASE(test_reorder_drain_up_to_seqn),
+		TEST_CASE(test_reorder_set_seqn),
 		TEST_CASES_END()
 	}
 };
-- 
2.34.1

RE: [PATCH 3/3] test/reorder: add cases to cover new API

[Volodymyr Fialko]

Depends-on: series-26425 ("lib/reorder: fix drain/free issues")

Test failure is caused by this bug in drain/api test - http://patches.dpdk.org/project/dpdk/list/?series=26425
It wasn't seen before seen before because drain was the last test, but now following test receive pointer to same packet twice due to double free.

> -----Original Message-----
> From: Volodymyr Fialko <vfialko@marvell.com>
> Sent: Friday, January 20, 2023 11:22 AM
> To: dev@dpdk.org; Reshma Pattan <reshma.pattan@intel.com>
> Cc: Jerin Jacob Kollanukkaran <jerinj@marvell.com>; Anoob Joseph <anoobj@marvell.com>;
> Volodymyr Fialko <vfialko@marvell.com>
> Subject: [PATCH 3/3] test/reorder: add cases to cover new API
> 
> Add new test cases to cover `rte_reorder_drain_up_to_seqn` and `rte_reorder_min_seqn_set`.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---
>  app/test/test_reorder.c | 160 ++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 160 insertions(+)
> 
> diff --git a/app/test/test_reorder.c b/app/test/test_reorder.c index f0714a5c18..c345a72e0c 100644
> --- a/app/test/test_reorder.c
> +++ b/app/test/test_reorder.c
> @@ -335,6 +335,164 @@ test_reorder_drain(void)
>  	return ret;
>  }
> 
> +static void
> +buffer_to_reorder_move(struct rte_mbuf **mbuf, struct
> +rte_reorder_buffer *b) {
> +	rte_reorder_insert(b, *mbuf);
> +	*mbuf = NULL;
> +}
> +
> +static int
> +test_reorder_drain_up_to_seqn(void)
> +{
> +	struct rte_mempool *p = test_params->p;
> +	struct rte_reorder_buffer *b = NULL;
> +	const unsigned int num_bufs = 10;
> +	const unsigned int size = 4;
> +	unsigned int i, cnt;
> +	int ret = 0;
> +
> +	struct rte_mbuf *bufs[num_bufs];
> +	struct rte_mbuf *robufs[num_bufs];
> +
> +	/* initialize all robufs to NULL */
> +	memset(robufs, 0, sizeof(robufs));
> +
> +	/* This would create a reorder buffer instance consisting of:
> +	 * reorder_seq = 0
> +	 * ready_buf: RB[size] = {NULL, NULL, NULL, NULL}
> +	 * order_buf: OB[size] = {NULL, NULL, NULL, NULL}
> +	 */
> +	b = rte_reorder_create("test_drain_up_to_seqn", rte_socket_id(), size);
> +	TEST_ASSERT_NOT_NULL(b, "Failed to create reorder buffer");
> +
> +	for (i = 0; i < num_bufs; i++) {
> +		bufs[i] = rte_pktmbuf_alloc(p);
> +		TEST_ASSERT_NOT_NULL(bufs[i], "Packet allocation failed\n");
> +		*rte_reorder_seqn(bufs[i]) = i;
> +	}
> +
> +	/* Insert packet with seqn 1 and 3:
> +	 * RB[] = {NULL, NULL, NULL, NULL}
> +	 * OB[] = {1, 2, 3, NULL}
> +	 */
> +	buffer_to_reorder_move(&bufs[1], b);
> +	buffer_to_reorder_move(&bufs[2], b);
> +	buffer_to_reorder_move(&bufs[3], b);
> +	/* Draining 1, 2 */
> +	cnt = rte_reorder_drain_up_to_seqn(b, robufs, num_bufs, 3);
> +	if (cnt != 2) {
> +		printf("%s:%d:%d: number of expected packets not drained\n",
> +				__func__, __LINE__, cnt);
> +		ret = -1;
> +		goto exit;
> +	}
> +	for (i = 0; i < 2; i++)
> +		rte_pktmbuf_free(robufs[i]);
> +	memset(robufs, 0, sizeof(robufs));
> +
> +	/* Insert more packets
> +	 * RB[] = {NULL, NULL, NULL, NULL}
> +	 * OB[] = {3, 4, NULL, 6}
> +	 */
> +	buffer_to_reorder_move(&bufs[4], b);
> +	buffer_to_reorder_move(&bufs[6], b);
> +	/* Insert more packets to utilize Ready buffer
> +	 * RB[] = {3, NULL, 5, 6}
> +	 * OB[] = {NULL, NULL, 8, NULL}
> +	 */
> +	buffer_to_reorder_move(&bufs[8], b);
> +
> +	/* Drain 3 and 5 */
> +	cnt = rte_reorder_drain_up_to_seqn(b, robufs, num_bufs, 6);
> +	if (cnt != 2) {
> +		printf("%s:%d:%d: number of expected packets not drained\n",
> +				__func__, __LINE__, cnt);
> +		ret = -1;
> +		goto exit;
> +	}
> +	for (i = 0; i < 2; i++)
> +		rte_pktmbuf_free(robufs[i]);
> +	memset(robufs, 0, sizeof(robufs));
> +
> +	ret = 0;
> +exit:
> +	rte_reorder_free(b);
> +	for (i = 0; i < num_bufs; i++) {
> +		rte_pktmbuf_free(bufs[i]);
> +		rte_pktmbuf_free(robufs[i]);
> +	}
> +	return ret;
> +}
> +
> +static int
> +test_reorder_set_seqn(void)
> +{
> +	struct rte_mempool *p = test_params->p;
> +	struct rte_reorder_buffer *b = NULL;
> +	const unsigned int num_bufs = 7;
> +	const unsigned int size = 4;
> +	unsigned int i;
> +	int ret = 0;
> +
> +	struct rte_mbuf *bufs[num_bufs];
> +
> +	/* This would create a reorder buffer instance consisting of:
> +	 * reorder_seq = 0
> +	 * ready_buf: RB[size] = {NULL, NULL, NULL, NULL}
> +	 * order_buf: OB[size] = {NULL, NULL, NULL, NULL}
> +	 */
> +	b = rte_reorder_create("test_min_seqn_set", rte_socket_id(), size);
> +	TEST_ASSERT_NOT_NULL(b, "Failed to create reorder buffer");
> +
> +	for (i = 0; i < num_bufs; i++) {
> +		bufs[i] = rte_pktmbuf_alloc(p);
> +		if (bufs[i] == NULL) {
> +			printf("Packet allocation failed\n");
> +			goto exit;
> +		}
> +		*rte_reorder_seqn(bufs[i]) = i;
> +	}
> +
> +	ret = rte_reorder_min_seqn_set(b, 5);
> +	if (ret != 0) {
> +		printf("%s:%d: Error in setting min sequence number\n", __func__, __LINE__);
> +		ret = -1;
> +		goto exit;
> +	}
> +
> +	ret = rte_reorder_insert(b, bufs[0]);
> +	if (ret >= 0) {
> +		printf("%s:%d: Insertion with value less the min seq number\n", __func__, __LINE__);
> +		ret = -1;
> +		goto exit;
> +	}
> +
> +	ret = rte_reorder_insert(b, bufs[5]);
> +	if (ret != 0) {
> +		printf("%s:%d: Error inserting packet with valid seqn\n", __func__, __LINE__);
> +		ret = -1;
> +		goto exit;
> +	}
> +	bufs[5] = NULL;
> +
> +	ret = rte_reorder_min_seqn_set(b, 0);
> +	if (ret >= 0) {
> +		printf("%s:%d: Error in setting min sequence number with non-empty buffer\n",
> +				__func__, __LINE__);
> +		ret = -1;
> +		goto exit;
> +	}
> +
> +	ret = 0;
> +exit:
> +	rte_reorder_free(b);
> +	for (i = 0; i < num_bufs; i++)
> +		rte_pktmbuf_free(bufs[i]);
> +
> +	return ret;
> +}
> +
>  static int
>  test_setup(void)
>  {
> @@ -385,6 +543,8 @@ static struct unit_test_suite reorder_test_suite  = {
>  		TEST_CASE(test_reorder_free),
>  		TEST_CASE(test_reorder_insert),
>  		TEST_CASE(test_reorder_drain),
> +		TEST_CASE(test_reorder_drain_up_to_seqn),
> +		TEST_CASE(test_reorder_set_seqn),
>  		TEST_CASES_END()
>  	}
>  };
> --
> 2.34.1

Re: [PATCH 3/3] test/reorder: add cases to cover new API

[Thomas Monjalon]

20/01/2023 11:21, Volodymyr Fialko:
> Add new test cases to cover `rte_reorder_drain_up_to_seqn` and
> `rte_reorder_min_seqn_set`.

Instead of doing a separate patch, please squash the tests
when adding the new API functions in patches 1 & 2.

Re: [PATCH 0/3] reorder: introduce new APIs

[David Marchand]

On Fri, Jan 20, 2023 at 11:22 AM Volodymyr Fialko <vfialko@marvell.com> wrote:
>
> This patch series provides new APIs for reorder library and test cases for
> them.
>
> Volodymyr Fialko (3):
>   reorder: add new drain up to seq number API
>   reorder: add ability to set min sequence number
>   test/reorder: add cases to cover new API
>
>  app/test/test_reorder.c   | 160 ++++++++++++++++++++++++++++++++++++++
>  lib/reorder/rte_reorder.c | 108 +++++++++++++++++++++++++
>  lib/reorder/rte_reorder.h |  43 ++++++++++
>  lib/reorder/version.map   |   2 +
>  4 files changed, 313 insertions(+)
>

Volodymyr, don't forget to Cc: the maintainer.

Reshma, can you review this series?
Thanks.


-- 
David Marchand

[PATCH v2 0/2] reorder: introduce new APIs

[Volodymyr Fialko]

This patch series provides new APIs for reorder library and test cases for
them.

v2:
- squash tests with corresponding API patches
- address minor comments

Volodymyr Fialko (2):
  reorder: add new drain up to seq number API
  reorder: add ability to set min sequence number

 app/test/test_reorder.c   | 160 ++++++++++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.c | 109 ++++++++++++++++++++++++++
 lib/reorder/rte_reorder.h |  44 +++++++++++
 lib/reorder/version.map   |   3 +
 4 files changed, 316 insertions(+)

-- 
2.34.1

[PATCH v2 1/2] reorder: add new drain up to seq number API

[Volodymyr Fialko]

Introduce new reorder drain API:
`rte_reorder_drain_up_to_seqn` - exhaustively drain all inserted mbufs
up to the given sequence number.

Currently there's no ability to force the drain from reorder buffer,
i.e. only consecutive ordered or ready packets could be drained.
New function would give user ability to drain inserted packets, without
need to wait for missing or newer packets.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 app/test/test_reorder.c   | 91 +++++++++++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.c | 78 +++++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.h | 26 +++++++++++
 lib/reorder/version.map   |  2 +
 4 files changed, 197 insertions(+)

diff --git a/app/test/test_reorder.c b/app/test/test_reorder.c
index 7b5e590bac..a37dc28f65 100644
--- a/app/test/test_reorder.c
+++ b/app/test/test_reorder.c
@@ -337,6 +337,96 @@ test_reorder_drain(void)
 	return ret;
 }
 
+static void
+buffer_to_reorder_move(struct rte_mbuf **mbuf, struct rte_reorder_buffer *b)
+{
+	rte_reorder_insert(b, *mbuf);
+	*mbuf = NULL;
+}
+
+static int
+test_reorder_drain_up_to_seqn(void)
+{
+	struct rte_mempool *p = test_params->p;
+	struct rte_reorder_buffer *b = NULL;
+	const unsigned int num_bufs = 10;
+	const unsigned int size = 4;
+	unsigned int i, cnt;
+	int ret = 0;
+
+	struct rte_mbuf *bufs[num_bufs];
+	struct rte_mbuf *robufs[num_bufs];
+
+	/* initialize all robufs to NULL */
+	memset(robufs, 0, sizeof(robufs));
+
+	/* This would create a reorder buffer instance consisting of:
+	 * reorder_seq = 0
+	 * ready_buf: RB[size] = {NULL, NULL, NULL, NULL}
+	 * order_buf: OB[size] = {NULL, NULL, NULL, NULL}
+	 */
+	b = rte_reorder_create("test_drain_up_to_seqn", rte_socket_id(), size);
+	TEST_ASSERT_NOT_NULL(b, "Failed to create reorder buffer");
+
+	for (i = 0; i < num_bufs; i++) {
+		bufs[i] = rte_pktmbuf_alloc(p);
+		TEST_ASSERT_NOT_NULL(bufs[i], "Packet allocation failed\n");
+		*rte_reorder_seqn(bufs[i]) = i;
+	}
+
+	/* Insert packet with seqn 1 and 3:
+	 * RB[] = {NULL, NULL, NULL, NULL}
+	 * OB[] = {1, 2, 3, NULL}
+	 */
+	buffer_to_reorder_move(&bufs[1], b);
+	buffer_to_reorder_move(&bufs[2], b);
+	buffer_to_reorder_move(&bufs[3], b);
+	/* Draining 1, 2 */
+	cnt = rte_reorder_drain_up_to_seqn(b, robufs, num_bufs, 3);
+	if (cnt != 2) {
+		printf("%s:%d:%d: number of expected packets not drained\n",
+				__func__, __LINE__, cnt);
+		ret = -1;
+		goto exit;
+	}
+	for (i = 0; i < 2; i++)
+		rte_pktmbuf_free(robufs[i]);
+	memset(robufs, 0, sizeof(robufs));
+
+	/* Insert more packets
+	 * RB[] = {NULL, NULL, NULL, NULL}
+	 * OB[] = {3, 4, NULL, 6}
+	 */
+	buffer_to_reorder_move(&bufs[4], b);
+	buffer_to_reorder_move(&bufs[6], b);
+	/* Insert more packets to utilize Ready buffer
+	 * RB[] = {3, NULL, 5, 6}
+	 * OB[] = {NULL, NULL, 8, NULL}
+	 */
+	buffer_to_reorder_move(&bufs[8], b);
+
+	/* Drain 3 and 5 */
+	cnt = rte_reorder_drain_up_to_seqn(b, robufs, num_bufs, 6);
+	if (cnt != 2) {
+		printf("%s:%d:%d: number of expected packets not drained\n",
+				__func__, __LINE__, cnt);
+		ret = -1;
+		goto exit;
+	}
+	for (i = 0; i < 2; i++)
+		rte_pktmbuf_free(robufs[i]);
+	memset(robufs, 0, sizeof(robufs));
+
+	ret = 0;
+exit:
+	rte_reorder_free(b);
+	for (i = 0; i < num_bufs; i++) {
+		rte_pktmbuf_free(bufs[i]);
+		rte_pktmbuf_free(robufs[i]);
+	}
+	return ret;
+}
+
 static int
 test_setup(void)
 {
@@ -387,6 +477,7 @@ static struct unit_test_suite reorder_test_suite  = {
 		TEST_CASE(test_reorder_free),
 		TEST_CASE(test_reorder_insert),
 		TEST_CASE(test_reorder_drain),
+		TEST_CASE(test_reorder_drain_up_to_seqn),
 		TEST_CASES_END()
 	}
 };
diff --git a/lib/reorder/rte_reorder.c b/lib/reorder/rte_reorder.c
index b38e71f460..bd0e1f8793 100644
--- a/lib/reorder/rte_reorder.c
+++ b/lib/reorder/rte_reorder.c
@@ -407,3 +407,81 @@ rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 
 	return drain_cnt;
 }
+
+/* Binary search seqn in ready buffer */
+static inline uint32_t
+ready_buffer_seqn_find(const struct cir_buffer *ready_buf, const uint32_t seqn)
+{
+	uint32_t mid, value, position, high;
+	uint32_t low = 0;
+
+	if (ready_buf->tail > ready_buf->head)
+		high = ready_buf->tail - ready_buf->head;
+	else
+		high = ready_buf->head - ready_buf->tail;
+
+	while (low <= high) {
+		mid = low + (high - low) / 2;
+		position = (ready_buf->tail + mid) & ready_buf->mask;
+		value = *rte_reorder_seqn(ready_buf->entries[position]);
+		if (seqn == value)
+			return mid;
+		else if (seqn > value)
+			low = mid + 1;
+		else
+			high = mid - 1;
+	}
+
+	return low;
+}
+
+unsigned int
+rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
+		const unsigned int max_mbufs, const rte_reorder_seqn_t seqn)
+{
+	uint32_t i, position, offset;
+	unsigned int drain_cnt = 0;
+
+	struct cir_buffer *order_buf = &b->order_buf,
+			*ready_buf = &b->ready_buf;
+
+	/* Seqn in Ready buffer */
+	if (seqn < b->min_seqn) {
+		/* All sequence numbers are higher then given */
+		if ((ready_buf->tail == ready_buf->head) ||
+		    (*rte_reorder_seqn(ready_buf->entries[ready_buf->tail]) > seqn))
+			return 0;
+
+		offset = ready_buffer_seqn_find(ready_buf, seqn);
+
+		for (i = 0; (i < offset) && (drain_cnt < max_mbufs); i++) {
+			position = (ready_buf->tail + i) & ready_buf->mask;
+			mbufs[drain_cnt++] = ready_buf->entries[position];
+			ready_buf->entries[position] = NULL;
+		}
+		ready_buf->tail = (ready_buf->tail + i) & ready_buf->mask;
+
+		return drain_cnt;
+	}
+
+	/* Seqn in Order buffer, add all buffers from Ready buffer */
+	while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head)) {
+		mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail];
+		ready_buf->entries[ready_buf->tail] = NULL;
+		ready_buf->tail = (ready_buf->tail + 1) & ready_buf->mask;
+	}
+
+	/* Fetch buffers from Order buffer up to given sequence number (exclusive) */
+	offset = RTE_MIN(seqn - b->min_seqn, b->order_buf.size);
+	for (i = 0; (i < offset) && (drain_cnt < max_mbufs); i++) {
+		position = (order_buf->head + i) & order_buf->mask;
+		if (order_buf->entries[position] == NULL)
+			continue;
+		mbufs[drain_cnt++] = order_buf->entries[position];
+		order_buf->entries[position] = NULL;
+	}
+	b->min_seqn += i;
+	order_buf->head = (order_buf->head + i) & order_buf->mask;
+
+	return drain_cnt;
+}
diff --git a/lib/reorder/rte_reorder.h b/lib/reorder/rte_reorder.h
index 5abdb258e2..db740495be 100644
--- a/lib/reorder/rte_reorder.h
+++ b/lib/reorder/rte_reorder.h
@@ -167,6 +167,32 @@ unsigned int
 rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 		unsigned max_mbufs);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Fetch set of reordered packets up to specified sequence number (exclusive)
+ *
+ * Returns a set of in-order packets from the reorder buffer structure.
+ * Gaps may be present since reorder buffer will try to fetch all possible packets up to given
+ * sequence number.
+ *
+ * @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.
+ * @param seqn
+ *   Sequence number up to which buffer will be drained.
+ * @return
+ *   Number of mbuf pointers written to mbufs. 0 <= N < max_mbufs.
+ */
+__rte_experimental
+unsigned int
+rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
+		unsigned int max_mbufs, rte_reorder_seqn_t seqn);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/reorder/version.map b/lib/reorder/version.map
index e114d17730..d322da03bd 100644
--- a/lib/reorder/version.map
+++ b/lib/reorder/version.map
@@ -16,4 +16,6 @@ EXPERIMENTAL {
 	global:
 
 	rte_reorder_seqn_dynfield_offset;
+	# added in 23.03
+	rte_reorder_drain_up_to_seqn;
 };
-- 
2.34.1

[PATCH v2 2/2] reorder: add ability to set min sequence number

[Volodymyr Fialko]

Add API `rte_reorder_min_seqn_set` to allow user to specify minimum
sequence number.
Currently sequence number of first inserted packet is used as minimum
sequence number. But for case when we want to wait for packets before
the received one this will not work.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 app/test/test_reorder.c   | 69 +++++++++++++++++++++++++++++++++++++++
 lib/reorder/rte_reorder.c | 31 ++++++++++++++++++
 lib/reorder/rte_reorder.h | 18 ++++++++++
 lib/reorder/version.map   |  1 +
 4 files changed, 119 insertions(+)

diff --git a/app/test/test_reorder.c b/app/test/test_reorder.c
index a37dc28f65..f391597a78 100644
--- a/app/test/test_reorder.c
+++ b/app/test/test_reorder.c
@@ -427,6 +427,74 @@ test_reorder_drain_up_to_seqn(void)
 	return ret;
 }
 
+static int
+test_reorder_set_seqn(void)
+{
+	struct rte_mempool *p = test_params->p;
+	struct rte_reorder_buffer *b = NULL;
+	const unsigned int num_bufs = 7;
+	const unsigned int size = 4;
+	unsigned int i;
+	int ret = 0;
+
+	struct rte_mbuf *bufs[num_bufs];
+
+	/* This would create a reorder buffer instance consisting of:
+	 * reorder_seq = 0
+	 * ready_buf: RB[size] = {NULL, NULL, NULL, NULL}
+	 * order_buf: OB[size] = {NULL, NULL, NULL, NULL}
+	 */
+	b = rte_reorder_create("test_min_seqn_set", rte_socket_id(), size);
+	TEST_ASSERT_NOT_NULL(b, "Failed to create reorder buffer");
+
+	for (i = 0; i < num_bufs; i++) {
+		bufs[i] = rte_pktmbuf_alloc(p);
+		if (bufs[i] == NULL) {
+			printf("Packet allocation failed\n");
+			goto exit;
+		}
+		*rte_reorder_seqn(bufs[i]) = i;
+	}
+
+	ret = rte_reorder_min_seqn_set(b, 5);
+	if (ret != 0) {
+		printf("%s:%d: Error in setting min sequence number\n", __func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+
+	ret = rte_reorder_insert(b, bufs[0]);
+	if (ret >= 0) {
+		printf("%s:%d: Insertion with value less the min seq number\n", __func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+
+	ret = rte_reorder_insert(b, bufs[5]);
+	if (ret != 0) {
+		printf("%s:%d: Error inserting packet with valid seqn\n", __func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+	bufs[5] = NULL;
+
+	ret = rte_reorder_min_seqn_set(b, 0);
+	if (ret >= 0) {
+		printf("%s:%d: Error in setting min sequence number with non-empty buffer\n",
+				__func__, __LINE__);
+		ret = -1;
+		goto exit;
+	}
+
+	ret = 0;
+exit:
+	rte_reorder_free(b);
+	for (i = 0; i < num_bufs; i++)
+		rte_pktmbuf_free(bufs[i]);
+
+	return ret;
+}
+
 static int
 test_setup(void)
 {
@@ -478,6 +546,7 @@ static struct unit_test_suite reorder_test_suite  = {
 		TEST_CASE(test_reorder_insert),
 		TEST_CASE(test_reorder_drain),
 		TEST_CASE(test_reorder_drain_up_to_seqn),
+		TEST_CASE(test_reorder_set_seqn),
 		TEST_CASES_END()
 	}
 };
diff --git a/lib/reorder/rte_reorder.c b/lib/reorder/rte_reorder.c
index bd0e1f8793..6e029c9e02 100644
--- a/lib/reorder/rte_reorder.c
+++ b/lib/reorder/rte_reorder.c
@@ -485,3 +485,34 @@ rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbu
 
 	return drain_cnt;
 }
+
+static bool
+rte_reorder_is_empty(const struct rte_reorder_buffer *b)
+{
+	const struct cir_buffer *order_buf = &b->order_buf, *ready_buf = &b->ready_buf;
+	unsigned int i;
+
+	/* Ready buffer does not have gaps */
+	if (ready_buf->tail != ready_buf->head)
+		return false;
+
+	/* Order buffer could have gaps, iterate */
+	for (i = 0; i < order_buf->size; i++) {
+		if (order_buf->entries[i] != NULL)
+			return false;
+	}
+
+	return true;
+}
+
+unsigned int
+rte_reorder_min_seqn_set(struct rte_reorder_buffer *b, rte_reorder_seqn_t min_seqn)
+{
+	if (!rte_reorder_is_empty(b))
+		return -ENOTEMPTY;
+
+	b->min_seqn = min_seqn;
+	b->is_initialized = true;
+
+	return 0;
+}
diff --git a/lib/reorder/rte_reorder.h b/lib/reorder/rte_reorder.h
index db740495be..cc95015fa6 100644
--- a/lib/reorder/rte_reorder.h
+++ b/lib/reorder/rte_reorder.h
@@ -193,6 +193,24 @@ unsigned int
 rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 		unsigned int max_mbufs, rte_reorder_seqn_t seqn);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Set minimum sequence number of packet allowed to be buffered.
+ * To successfully set new value reorder buffer has to be empty(after create, reset or drain_all).
+ *
+ * @param b
+ *   Empty reorder buffer instance to modify.
+ * @param min_seqn
+ *   New sequence number to set.
+ * @return
+ *   0 on success, a negative value otherwise.
+ */
+__rte_experimental
+unsigned int
+rte_reorder_min_seqn_set(struct rte_reorder_buffer *b, rte_reorder_seqn_t min_seqn);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/reorder/version.map b/lib/reorder/version.map
index d322da03bd..e21b91f526 100644
--- a/lib/reorder/version.map
+++ b/lib/reorder/version.map
@@ -18,4 +18,5 @@ EXPERIMENTAL {
 	rte_reorder_seqn_dynfield_offset;
 	# added in 23.03
 	rte_reorder_drain_up_to_seqn;
+	rte_reorder_min_seqn_set;
 };
-- 
2.34.1

Re: [PATCH v2 0/2] reorder: introduce new APIs

[Thomas Monjalon]

20/02/2023 11:48, Volodymyr Fialko:
> This patch series provides new APIs for reorder library and test cases for
> them.
> 
> v2:
> - squash tests with corresponding API patches
> - address minor comments

Thanks
In absence of review, I will just wait for the CI to complete before merging.

Re: [PATCH v2 0/2] reorder: introduce new APIs

[Thomas Monjalon]

20/02/2023 12:01, Thomas Monjalon:
> 20/02/2023 11:48, Volodymyr Fialko:
> > This patch series provides new APIs for reorder library and test cases for
> > them.
> > 
> > v2:
> > - squash tests with corresponding API patches
> > - address minor comments
> 
> Thanks
> In absence of review, I will just wait for the CI to complete before merging.

CI looks green.

Applied, thanks.