From: Chas Williams <3chas3@gmail.com>
To: dev@dpdk.org
Cc: cristian.dumitrescu@intel.com, "Charles (Chas) Williams" <chas3@att.com>
Subject: [dpdk-dev] [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 [dpdk-dev] [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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).