[PATCH 1/2] test/bitmap: add additional tests

[PATCH 1/2] test/bitmap: add additional tests

[Chas Williams]

From: "Charles (Chas) Williams" <chas3@att.com>

Add addtional units tests for the rte_bitmap_scan() routine.  Test that
we are gettting the bits returned that we expect.

Signed-off-by: Chas Williams <chas3@att.com>
---
 test/test/test_bitmap.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)

diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c
index 05d547e..f498c02 100644
--- a/test/test/test_bitmap.c
+++ b/test/test/test_bitmap.c
@@ -74,6 +74,71 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 }
 
 static int
+test_bitmap_scan_operations2(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t out_slab = 0;
+	uint32_t pattern[] = { 10, 11, 100, 101, 500, 501 };
+	uint32_t pattern2[] = { 11, 101, 501 };
+	uint32_t i;
+
+	rte_bitmap_reset(bmp);
+
+	/* Setup the initial bitmap. */
+	for (i = 0; i < sizeof(pattern)/sizeof(uint32_t); i++)
+		rte_bitmap_set(bmp, pattern[i]);
+
+	/* Iterate. */
+	for (i = 0; i < sizeof(pattern)/sizeof(uint32_t); i++) {
+		if (!rte_bitmap_scan(bmp, &pos, &out_slab) ||
+		    pos != pattern[i]) {
+			printf("Failed to get pos %d from bitmap.\n",
+			       pattern[i]);
+			return TEST_FAILED;
+		}
+	}
+
+	/* Check wrap around. */
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != pattern[0]) {
+		printf("Failed to get pos %d from bitmap.\n", pattern[0]);
+		return TEST_FAILED;
+	}
+
+	/* Delete half the entries in the slabs. */
+	rte_bitmap_clear(bmp, 10);
+	rte_bitmap_clear(bmp, 100);
+	rte_bitmap_clear(bmp, 500);
+
+	/* Iterate. */
+	for (i = 0; i < sizeof(pattern2)/sizeof(uint32_t); i++) {
+		if (!rte_bitmap_scan(bmp, &pos, &out_slab) ||
+		    pos != pattern2[i]) {
+			printf("Failed to get pos %d from bitmap.\n",
+			       pattern2[i]);
+			return TEST_FAILED;
+		}
+	}
+
+	/* Check wrap around. */
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != pattern2[0]) {
+		printf("Failed to get pos %d from bitmap.\n", pattern2[0]);
+		return TEST_FAILED;
+	}
+
+	rte_bitmap_clear(bmp, 11);
+	rte_bitmap_clear(bmp, 101);
+	rte_bitmap_clear(bmp, 501);
+
+	/* Ensure bitmap it empty. */
+	if (rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Found pos %d in empty bitmap.\n", pos);
+		return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
 test_bitmap_slab_set_get(struct rte_bitmap *bmp)
 {
 	uint32_t pos = 0;
@@ -158,6 +223,9 @@ test_bitmap(void)
 	if (test_bitmap_scan_operations(bmp) < 0)
 		return TEST_FAILED;
 
+	if (test_bitmap_scan_operations2(bmp) < 0)
+		return TEST_FAILED;
+
 	return TEST_SUCCESS;
 }
 
-- 
2.9.5

[PATCH 2/2] lib: fix bitmap scanning

[Chas Williams]

From: "Charles (Chas) Williams" <chas3@att.com>

index2 is used inconsistently, both as an array offset and as a bit
offset.  Fix usage to be consistent as a bit offset.  Additonally,
offset1 needs to be shifted with the size of the array1 slab entries,
not the cache line sizes.  __rte_bitmap_scan_read() needs to examine
the current array2 slab bit by bit to find the next set bit.

The unit tests for rte_bitmap_scan() aren't correct.  If a slab isn't
empty, there is no reason to expect rte_bitmap_scan() to advance to
the next slab.  Change the slab magic values so that rte_bitmap_scan()
will advance on reading a bit from each slab and verify it is the bit
position we expect.

Fixes: de3cfa2c9823a ("sched: initial import")

Signed-off-by: Chas Williams <chas3@att.com>
---
 lib/librte_eal/common/include/rte_bitmap.h | 31 +++++++++++++++---------------
 test/test/test_bitmap.c                    | 12 ++++++------
 2 files changed, 22 insertions(+), 21 deletions(-)

diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
index 7d4935f..27084d9 100644
--- a/lib/librte_eal/common/include/rte_bitmap.h
+++ b/lib/librte_eal/common/include/rte_bitmap.h
@@ -94,7 +94,8 @@ __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
 static inline void
 __rte_bitmap_index2_set(struct rte_bitmap *bmp)
 {
-	bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
+	bmp->index2 = ((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) +
+		       bmp->offset1) << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 }
 
 #if RTE_BITMAP_OPTIMIZATIONS
@@ -172,7 +173,6 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	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->go2 = 0;
 }
@@ -338,7 +338,8 @@ rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
 	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 	offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
-	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	offset1 = (pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) &
+						RTE_BITMAP_SLAB_BIT_MASK;
 	slab2 = bmp->array2 + index2;
 	slab1 = bmp->array1 + index1;
 
@@ -365,7 +366,8 @@ rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
 	/* Set bits in array2 slab and set bit in array1 slab */
 	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
-	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	offset1 = (pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) &
+						RTE_BITMAP_SLAB_BIT_MASK;
 	slab2 = bmp->array2 + index2;
 	slab1 = bmp->array1 + index1;
 
@@ -422,7 +424,8 @@ rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
 
 	/* The array2 cache line is all-zeros, so clear bit in array1 slab */
 	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
-	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	offset1 = (pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) &
+						RTE_BITMAP_SLAB_BIT_MASK;
 	slab1 = bmp->array1 + index1;
 	*slab1 &= ~(1lu << offset1);
 
@@ -471,15 +474,14 @@ __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) {
-		if (*slab2) {
-			*pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
-			*slab = *slab2;
+	slab2 = bmp->array2 + (bmp->index2 >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2);
+	for ( ; bmp->go2 ; bmp->index2++,
+			   bmp->go2 = bmp->index2 & RTE_BITMAP_SLAB_BIT_MASK) {
+		uint32_t offset2 = bmp->index2 & RTE_BITMAP_SLAB_BIT_MASK;
 
-			bmp->index2 ++;
-			slab2 ++;
-			bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
+		if (*slab2 & (1lu << offset2)) {
+			*pos = bmp->index2++;
+			*slab = *slab2;
 			return 1;
 		}
 	}
@@ -518,8 +520,7 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	/* Look for non-empty array2 line */
 	if (__rte_bitmap_scan_search(bmp)) {
 		__rte_bitmap_scan_read_init(bmp);
-		__rte_bitmap_scan_read(bmp, pos, slab);
-		return 1;
+		return __rte_bitmap_scan_read(bmp, pos, slab);
 	}
 
 	/* Empty bitmap */
diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c
index f498c02..ffbbc02 100644
--- a/test/test/test_bitmap.c
+++ b/test/test/test_bitmap.c
@@ -17,8 +17,8 @@ static int
 test_bitmap_scan_operations(struct rte_bitmap *bmp)
 {
 	uint32_t pos = 0;
-	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
-	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	uint64_t slab1_magic = 0x80; /* pos = 7 */
+	uint64_t slab2_magic = 0x08; /* pos = 67 */
 	uint64_t out_slab = 0;
 
 	rte_bitmap_reset(bmp);
@@ -26,7 +26,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 	rte_bitmap_set_slab(bmp, pos, slab1_magic);
 	rte_bitmap_set_slab(bmp, pos + RTE_BITMAP_SLAB_BIT_SIZE, slab2_magic);
 
-	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 7) {
 		printf("Failed to get slab from bitmap.\n");
 		return TEST_FAILED;
 	}
@@ -36,7 +36,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
-	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 67) {
 		printf("Failed to get slab from bitmap.\n");
 		return TEST_FAILED;
 	}
@@ -47,7 +47,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 	}
 
 	/* Wrap around */
-	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 7) {
 		printf("Failed to get slab from bitmap.\n");
 		return TEST_FAILED;
 	}
@@ -60,7 +60,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 	/* Scan reset check. */
 	__rte_bitmap_scan_init(bmp);
 
-	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 7) {
 		printf("Failed to get slab from bitmap.\n");
 		return TEST_FAILED;
 	}
-- 
2.9.5