From: Chas Williams <3chas3@gmail.com>
To: dev@dpdk.org
Cc: cristian.dumitrescu@intel.com, "Charles (Chas) Williams" <chas3@att.com>
Subject: [PATCH 2/2] lib: fix bitmap scanning
Date: Fri, 9 Feb 2018 15:20:03 -0500 [thread overview]
Message-ID: <20180209202003.28546-2-3chas3@gmail.com> (raw)
In-Reply-To: <20180209202003.28546-1-3chas3@gmail.com>
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
prev parent reply other threads:[~2018-02-09 20:20 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-02-09 20:20 [PATCH 1/2] test/bitmap: add additional tests Chas Williams
2018-02-09 20:20 ` Chas Williams [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180209202003.28546-2-3chas3@gmail.com \
--to=3chas3@gmail.com \
--cc=chas3@att.com \
--cc=cristian.dumitrescu@intel.com \
--cc=dev@dpdk.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.