[PATCH v2] bitmap: add scan from offset function

[Volodymyr Fialko]

Currently, in the case when we search for a bit set after a particular
value, the bitmap has to be scanned from the beginning and
rte_bitmap_scan() has to be called multiple times until we hit the value.

Add a new rte_bitmap_scan_from_offset() function to initialize scan
state at the given offset and perform scan, this will allow getting
the next set bit after certain offset within one scan call.

Signed-off-by: Volodymyr Fialko <vfialko at marvell.com>
---
 app/test/test_bitmap.c       | 33 ++++++++++++++++++++-
 lib/eal/include/rte_bitmap.h | 56 ++++++++++++++++++++++++++++++++++++
 2 files changed, 88 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index e9c61590ae..9e38087408 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -18,8 +18,8 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 {
 	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
 	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	int i, nb_clear, nb_set, next_cl;
 	uint32_t pos = 0, start_pos;
-	int i, nb_clear, nb_set;
 	uint64_t out_slab = 0;
 
 	rte_bitmap_reset(bmp);
@@ -71,6 +71,37 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
+	/* Scan with offset check. */
+	if (!rte_bitmap_scan_from_offset(bmp, RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan from offset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan with offset wrap around check. */
+	if (!rte_bitmap_scan_from_offset(bmp, 2 * RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan from offset with wrap around operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Test scan when the bit set is on a next cline */
+	rte_bitmap_reset(bmp);
+	next_cl = RTE_MIN(RTE_BITMAP_CL_BIT_SIZE, MAX_BITS);
+	rte_bitmap_set(bmp, next_cl);
+	if (!rte_bitmap_scan_from_offset(bmp, 0, &pos, &out_slab)) {
+		printf("Failed to get slab from next cache line from bitmap.\n");
+		return TEST_FAILED;
+	}
+
 	/* Test scan when a cline is half full */
 	rte_bitmap_reset(bmp);
 	for (i = 0; i < MAX_BITS; i++)
diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h
index 27ee3d18a4..624365b9c5 100644
--- a/lib/eal/include/rte_bitmap.h
+++ b/lib/eal/include/rte_bitmap.h
@@ -137,6 +137,30 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	bmp->go2 = 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap initialize internal scan pointers at the given position for the scan function.
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   Bit position to start scan
+ */
+__rte_experimental
+static inline void
+__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
+{
+	uint64_t *slab1;
+
+	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+	slab1 = bmp->array1 + bmp->index1;
+	bmp->go2 = *slab1 & (1llu << bmp->offset1);
+}
+
 /**
  * Bitmap memory footprint calculation
  *
@@ -591,6 +615,38 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	return 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap scan from the given offset.
+ * Function will reset internal scan state to start scanning from the offset
+ * position.
+ * @see rte_bitmap_scan()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param offset
+ *   Bit offset to start scan
+ * @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.
+ *   When function call returns 0, slab is not modified.
+ * @return
+ *   0 if there is no bit set in the bitmap, 1 otherwise
+ */
+__rte_experimental
+static inline int
+rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset,
+			    uint32_t *pos, uint64_t *slab)
+{
+	__rte_bitmap_scan_init_at(bmp, offset);
+	return rte_bitmap_scan(bmp, pos, slab);
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.34.1