From: "Charles (Chas) Williams" <ch...@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 <ch...@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