[dpdk-dev] [PATCH 0/2] eal/bitmap: support reverse bitmap scan

[dpdk-dev] [PATCH 0/2] eal/bitmap: support reverse bitmap scan

[Vivek Sharma]

This patchset implements the support for reverse bitmap scanning along with
test support. Reverse scanning is quite useful when bit position signifies
an ordering according to some attribute, e.g., priority ordering.

Prerequisite:
* Note that this patchset is dependent on patch:-
  'http://patches.dpdk.org/patch/45307/'

Vivek Sharma (2):
  eal/bitmap: support bitmap reverse scanning
  test/bitmap: implement reverse bitmap scan test

 lib/librte_eal/common/include/rte_bitmap.h | 164 +++++++++++++++++++++++++----
 test/test/test_bitmap.c                    |  71 ++++++++++++-
 2 files changed, 213 insertions(+), 22 deletions(-)

-- 
2.7.4

[dpdk-dev] [PATCH 1/2] eal/bitmap: support bitmap reverse scanning

[Vivek Sharma]

Currently bitmap supports only forward scanning starting from zero
bit position. This patch implements reverse scanning starting from
highest bit position towards zero bit position.

Signed-off-by: Vivek Sharma <vivek.sharma@caviumnetworks.com>
---
Prerequisite:
* Note that this patchset is dependent on patch:
  'http://patches.dpdk.org/patch/45307/'

 lib/librte_eal/common/include/rte_bitmap.h | 164 +++++++++++++++++++++++++----
 1 file changed, 143 insertions(+), 21 deletions(-)

diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
index 7a36ce7..4b3437e 100644
--- a/lib/librte_eal/common/include/rte_bitmap.h
+++ b/lib/librte_eal/common/include/rte_bitmap.h
@@ -61,6 +61,11 @@ extern "C" {
 #define RTE_BITMAP_CL_SLAB_SIZE_LOG2             (RTE_BITMAP_CL_BIT_SIZE_LOG2 - RTE_BITMAP_SLAB_BIT_SIZE_LOG2)
 #define RTE_BITMAP_CL_SLAB_MASK                  (RTE_BITMAP_CL_SLAB_SIZE - 1)
 
+enum rte_scan_dir {
+	RTE_BITMAP_REV_SCAN = -1,
+	RTE_BITMAP_FWD_SCAN = 1
+};
+
 /** Bitmap data structure */
 struct rte_bitmap {
 	/* Context for array1 and array2 */
@@ -74,6 +79,7 @@ struct rte_bitmap {
 	uint32_t offset1; /**< Bitmap scan: Offset of current bit within current array1 slab */
 	uint32_t index2;  /**< Bitmap scan: Index of current array2 slab */
 	uint32_t go2;     /**< Bitmap scan: Go/stop condition for current array2 cache line */
+	enum rte_scan_dir dir; /**< Bitmap scan: Current scan direction */
 
 	/* Storage space for array1 and array2 */
 	uint8_t memory[];
@@ -82,13 +88,16 @@ struct rte_bitmap {
 static inline void
 __rte_bitmap_index1_inc(struct rte_bitmap *bmp)
 {
-	bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1);
+	bmp->index1 = (bmp->index1 + bmp->dir) & (bmp->array1_size - 1);
 }
 
 static inline uint64_t
 __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
 {
-	return (~1llu) << bmp->offset1;
+	if (bmp->dir == RTE_BITMAP_FWD_SCAN)
+		return (~1llu) << bmp->offset1;
+	else
+		return (~0llu) ^ ((~0llu) << bmp->offset1);
 }
 
 static inline void
@@ -110,6 +119,16 @@ rte_bsf64(uint64_t slab, uint32_t *pos)
 	return 1;
 }
 
+static inline int
+rte_bsl64(uint64_t slab, uint32_t *pos)
+{
+	if (likely(!slab))
+		return 0;
+
+	*pos = RTE_BITMAP_SLAB_BIT_SIZE - 1 - __builtin_clzll(slab);
+	return 1;
+}
+
 #else
 
 static inline int
@@ -132,6 +151,25 @@ rte_bsf64(uint64_t slab, uint32_t *pos)
 	return 0;
 }
 
+static inline int
+rte_bsl64(uint64_t slab, uint32_t *pos)
+{
+	uint64_t mask;
+	int i;
+
+	if (likely(!slab))
+		return 0;
+
+	for (i = RTE_BITMAP_SLAB_BIT_SIZE - 1, mask = 1; i >= 0; i--) {
+		if (unlikely(slab & (mask << i))) {
+			*pos = i;
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
 #endif
 
 static inline uint32_t
@@ -167,16 +205,29 @@ __rte_bitmap_get_memory_footprint(uint32_t n_bits,
 }
 
 static inline void
-__rte_bitmap_scan_init(struct rte_bitmap *bmp)
+__rte_bitmap_scan_init_generic(struct rte_bitmap *bmp, enum rte_scan_dir dir)
 {
-	bmp->index1 = bmp->array1_size - 1;
-	bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
-	__rte_bitmap_index2_set(bmp);
-	bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE;
-
+	if (dir == RTE_BITMAP_FWD_SCAN) {
+		bmp->index1 = bmp->array1_size - 1;
+		bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
+		__rte_bitmap_index2_set(bmp);
+		bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE;
+		bmp->dir = RTE_BITMAP_FWD_SCAN;
+	} else {
+		bmp->index1 = 0;
+		bmp->offset1 = 0;
+		bmp->index2 = 0;
+		bmp->dir = RTE_BITMAP_REV_SCAN;
+	}
 	bmp->go2 = 0;
 }
 
+static inline void
+__rte_bitmap_scan_init(struct rte_bitmap *bmp)
+{
+	__rte_bitmap_scan_init_generic(bmp, RTE_BITMAP_FWD_SCAN);
+}
+
 /**
  * Bitmap memory footprint calculation
  *
@@ -439,19 +490,32 @@ __rte_bitmap_scan_search(struct rte_bitmap *bmp)
 	value1 = bmp->array1[bmp->index1];
 	value1 &= __rte_bitmap_mask1_get(bmp);
 
-	if (rte_bsf64(value1, &bmp->offset1)) {
-		return 1;
+	if (bmp->dir == RTE_BITMAP_FWD_SCAN) {
+		if (rte_bsf64(value1, &bmp->offset1))
+			return 1;
+	} else {
+		if (rte_bsl64(value1, &bmp->offset1))
+			return 1;
 	}
 
 	__rte_bitmap_index1_inc(bmp);
-	bmp->offset1 = 0;
+
+	if (bmp->dir == RTE_BITMAP_FWD_SCAN)
+		bmp->offset1 = 0;
+	else
+		bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
 
 	/* Look for another array1 slab */
-	for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) {
+	for (i = 0; i < bmp->array1_size;
+	     i++, __rte_bitmap_index1_inc(bmp)) {
 		value1 = bmp->array1[bmp->index1];
 
-		if (rte_bsf64(value1, &bmp->offset1)) {
-			return 1;
+		if (bmp->dir == RTE_BITMAP_FWD_SCAN) {
+			if (rte_bsf64(value1, &bmp->offset1))
+				return 1;
+		} else {
+			if (rte_bsl64(value1, &bmp->offset1))
+				return 1;
 		}
 	}
 
@@ -462,8 +526,12 @@ static inline void
 __rte_bitmap_scan_read_init(struct rte_bitmap *bmp)
 {
 	__rte_bitmap_index2_set(bmp);
+
+	if (bmp->dir == RTE_BITMAP_REV_SCAN)
+		bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE - 1;
+
 	bmp->go2 = 1;
-	rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8));
+	rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8 * bmp->dir));
 }
 
 static inline int
@@ -472,23 +540,42 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	uint64_t *slab2;
 
 	slab2 = bmp->array2 + bmp->index2;
-	for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
+
+	for ( ; bmp->go2; ) {
 		if (*slab2) {
 			*pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 			*slab = *slab2;
 
-			bmp->index2 ++;
-			slab2 ++;
-			bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
+			bmp->index2 += bmp->dir;
+			slab2 += bmp->dir;
+
+			if (bmp->dir == RTE_BITMAP_FWD_SCAN)
+				bmp->go2 =
+					bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
+			else
+				/* stop once index2 crosses zero while
+				 * decreasing.
+				 */
+				bmp->go2 = (bmp->index2 ^ (~0));
 			return 1;
 		}
+
+		bmp->index2 += bmp->dir;
+		slab2 += bmp->dir;
+
+		if (bmp->dir == RTE_BITMAP_FWD_SCAN)
+			bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
+		else
+			bmp->go2 = (bmp->index2 ^ (~0));
+
+		bmp->index2 &= RTE_BITMAP_CL_SLAB_MASK;
 	}
 
 	return 0;
 }
 
 /**
- * Bitmap scan (with automatic wrap-around)
+ * Bitmap scan generic (with automatic wrap-around)
  *
  * @param bmp
  *   Handle to bitmap instance
@@ -504,12 +591,20 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
  *   after this slab, so the same slab will not be returned again if it
  *   contains more than one bit which is set. When function call returns 0,
  *   slab is not modified.
+ * @param dir
+ *   Scanning direction, whether in forward/positive(increasing bit index)
+ *   or reverse/backward/negative(decreasing bit index) direction.
  * @return
  *   0 if there is no bit set in the bitmap, 1 otherwise
  */
 static inline int
-rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
+rte_bitmap_scan_generic(struct rte_bitmap *bmp, uint32_t *pos,
+		       uint64_t *slab, enum rte_scan_dir dir)
 {
+	/* Init scan parameters as per requested scan direction */
+	if (unlikely(bmp->dir != dir))
+		__rte_bitmap_scan_init_generic(bmp, dir);
+
 	/* Return data from current array2 line if available */
 	if (__rte_bitmap_scan_read(bmp, pos, slab)) {
 		return 1;
@@ -526,6 +621,33 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	return 0;
 }
 
+/**
+ * Bitmap scan (with automatic wrap-around)
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   When function call returns 1, pos contains the position of the next set
+ *   bit, otherwise not modified
+ * @param slab
+ *   When function call returns 1, slab contains the value of the entire 64-bit
+ *   slab where the bit indicated by pos is located. Slabs are always 64-bit
+ *   aligned, so the position of the first bit of the slab (this bit is not
+ *   necessarily set) is pos / 64. Once a slab has been returned by the bitmap
+ *   scan operation, the internal pointers of the bitmap are updated to point
+ *   after this slab, so the same slab will not be returned again if it
+ *   contains more than one bit which is set. When function call returns 0,
+ *   slab is not modified.
+ * @return
+ *   0 if there is no bit set in the bitmap, 1 otherwise
+ */
+static inline int
+rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos,
+		       uint64_t *slab)
+{
+	return rte_bitmap_scan_generic(bmp, pos, slab, RTE_BITMAP_FWD_SCAN);
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.7.4

[dpdk-dev] [PATCH 2/2] test/bitmap: implement reverse bitmap scan test

[Vivek Sharma]

This patch implements support for testing bitmap reverse scan.
Bits in bitmap are changed to be an exact multiple of slab size.

Signed-off-by: Vivek Sharma <vivek.sharma@caviumnetworks.com>
---
Prerequisite:
* Note that this patchset is dependent on patch:
  'http://patches.dpdk.org/patch/45307/'

 test/test/test_bitmap.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 70 insertions(+), 1 deletion(-)

diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c
index 95c5184..21a193b 100644
--- a/test/test/test_bitmap.c
+++ b/test/test/test_bitmap.c
@@ -11,7 +11,7 @@
 
 #include "test.h"
 
-#define MAX_BITS 1000
+#define MAX_BITS 1024
 
 static int
 test_bitmap_scan_operations(struct rte_bitmap *bmp)
@@ -74,6 +74,72 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 }
 
 static int
+test_bitmap_scan_reverse_operations(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
+	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+
+	rte_bitmap_set_slab(bmp, MAX_BITS - RTE_BITMAP_SLAB_BIT_SIZE,
+			    slab2_magic);
+	rte_bitmap_set_slab(bmp, MAX_BITS - (2 * RTE_BITMAP_SLAB_BIT_SIZE),
+			    slab1_magic);
+
+	if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab,
+				     RTE_BITMAP_REV_SCAN)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab,
+				     RTE_BITMAP_REV_SCAN)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Wrap around */
+	if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab,
+				     RTE_BITMAP_REV_SCAN)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan operation wrap around failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan reset check. */
+	__rte_bitmap_scan_init_generic(bmp, RTE_BITMAP_REV_SCAN);
+
+	if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab,
+				     RTE_BITMAP_REV_SCAN)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan reset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
 test_bitmap_slab_set_get(struct rte_bitmap *bmp)
 {
 	uint32_t pos = 0;
@@ -176,6 +242,9 @@ test_bitmap(void)
 	if (test_bitmap_scan_operations(bmp) < 0)
 		return TEST_FAILED;
 
+	if (test_bitmap_scan_reverse_operations(bmp) < 0)
+		return TEST_FAILED;
+
 	rte_bitmap_free(bmp);
 	rte_free(mem);
 
-- 
2.7.4

Re: [dpdk-dev] [PATCH 0/2] eal/bitmap: support reverse bitmap scan

[Stephen Hemminger]

On Tue,  9 Oct 2018 13:24:57 +0530
Vivek Sharma <vivek.sharma@caviumnetworks.com> wrote:

> This patchset implements the support for reverse bitmap scanning along with
> test support. Reverse scanning is quite useful when bit position signifies
> an ordering according to some attribute, e.g., priority ordering.
> 
> Prerequisite:
> * Note that this patchset is dependent on patch:-
>   'http://patches.dpdk.org/patch/45307/'
> 
> Vivek Sharma (2):
>   eal/bitmap: support bitmap reverse scanning
>   test/bitmap: implement reverse bitmap scan test
> 
>  lib/librte_eal/common/include/rte_bitmap.h | 164 +++++++++++++++++++++++++----
>  test/test/test_bitmap.c                    |  71 ++++++++++++-
>  2 files changed, 213 insertions(+), 22 deletions(-)
> 

This patchset has had no feedback in 5 years.
* There was never an application that needed it.
* EAL directory structure changed.
* It would cause an ABI breakage.

If you have an example that needs it, then rebase and follow ABI
rules and the next ABI change will be for 23.11