On Fri, 11/20 19:22, Vladimir Sementsov-Ogievskiy wrote:
> On 20.11.2015 12:59, Fam Zheng wrote:
> >Sometimes confused with the granularity with coarse levels in HBitmap, the
> >granularity in the hbitmap_alloc is not an essential concept of a bitmap.
> >Now
> >that all callers except the test code use zero, it's possible to drop the
> >parameter to make the interface cleaner and more intuitive.
> >
> >Test code of hbitmap granularity is removed together.
> >
> >Signed-off-by: Fam Zheng <f...@redhat.com>
> >---
> > block.c | 4 +-
> > include/qemu/hbitmap.h | 20 +----
> > tests/test-hbitmap.c | 206
> > ++++++++-----------------------------------------
> > util/hbitmap.c | 64 +++------------
> > 4 files changed, 49 insertions(+), 245 deletions(-)
> >
> >diff --git a/block.c b/block.c
> >index e225050..86b32a0 100644
> >--- a/block.c
> >+++ b/block.c
> >@@ -3183,7 +3183,7 @@ BdrvDirtyBitmap
> >*bdrv_create_dirty_bitmap(BlockDriverState *bs,
> > return NULL;
> > }
> > bitmap = g_new0(BdrvDirtyBitmap, 1);
> >- bitmap->bitmap = hbitmap_alloc(bitmap_size, 0);
> >+ bitmap->bitmap = hbitmap_alloc(bitmap_size);
> > bitmap->gran_shift = gran_shift;
> > bitmap->size = bitmap_size;
> > bitmap->name = g_strdup(name);
> >@@ -3453,7 +3453,7 @@ void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> >HBitmap **out)
> > hbitmap_reset_all(bitmap->bitmap);
> > } else {
> > HBitmap *backup = bitmap->bitmap;
> >- bitmap->bitmap = hbitmap_alloc(bitmap->size, 0);
> >+ bitmap->bitmap = hbitmap_alloc(bitmap->size);
> > *out = backup;
> > }
> > }
> >diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> >index bb94a00..0f81483 100644
> >--- a/include/qemu/hbitmap.h
> >+++ b/include/qemu/hbitmap.h
> >@@ -39,9 +39,6 @@ typedef struct HBitmapIter HBitmapIter;
> > struct HBitmapIter {
> > const HBitmap *hb;
> >- /* Copied from hb for access in the inline functions (hb is opaque). */
> >- int granularity;
> >-
> > /* Entry offset into the last-level array of longs. */
> > size_t pos;
> >@@ -54,15 +51,10 @@ struct HBitmapIter {
> > /**
> > * hbitmap_alloc:
> > * @size: Number of bits in the bitmap.
> >- * @granularity: Granularity of the bitmap. Aligned groups of
> >2^@granularity
> >- * bits will be represented by a single bit. Each operation on a
> >- * range of bits first rounds the bits to determine which group they land
> >- * in, and then affect the entire set; iteration will only visit the first
> >- * bit of each group.
> > *
> > * Allocate a new HBitmap.
> > */
> >-HBitmap *hbitmap_alloc(uint64_t size, int granularity);
> >+HBitmap *hbitmap_alloc(uint64_t size);
> > /**
> > * hbitmap_truncate:
> >@@ -96,14 +88,6 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b);
> > bool hbitmap_empty(const HBitmap *hb);
> > /**
> >- * hbitmap_granularity:
> >- * @hb: HBitmap to operate on.
> >- *
> >- * Return the granularity of the HBitmap.
> >- */
> >-int hbitmap_granularity(const HBitmap *hb);
> >-
> >-/**
> > * hbitmap_count:
> > * @hb: HBitmap to operate on.
> > *
> >@@ -204,7 +188,7 @@ static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
> > hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> > item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
> >- return item << hbi->granularity;
> >+ return item;
> > }
> > /**
> >diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> >index abcea0c..dc8485a 100644
> >--- a/tests/test-hbitmap.c
> >+++ b/tests/test-hbitmap.c
> >@@ -26,7 +26,6 @@ typedef struct TestHBitmapData {
> > unsigned long *bits;
> > size_t size;
> > size_t old_size;
> >- int granularity;
> > } TestHBitmapData;
> >@@ -70,17 +69,16 @@ static void hbitmap_test_check(TestHBitmapData *data,
> > }
> > if (first == 0) {
> >- g_assert_cmpint(count << data->granularity, ==,
> >hbitmap_count(data->hb));
> >+ g_assert_cmpint(count, ==, hbitmap_count(data->hb));
> > }
> > }
> > /* This is provided instead of a test setup function so that the sizes
> > are kept in the test functions (and not in main()) */
> >-static void hbitmap_test_init(TestHBitmapData *data,
> >- uint64_t size, int granularity)
> >+static void hbitmap_test_init(TestHBitmapData *data, uint64_t size)
> > {
> > size_t n;
> >- data->hb = hbitmap_alloc(size, granularity);
> >+ data->hb = hbitmap_alloc(size);
> > n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
> > if (n == 0) {
> >@@ -88,7 +86,6 @@ static void hbitmap_test_init(TestHBitmapData *data,
> > }
> > data->bits = g_new0(unsigned long, n);
> > data->size = size;
> >- data->granularity = granularity;
> > if (size) {
> > hbitmap_test_check(data, 0);
> > }
> >@@ -158,9 +155,7 @@ static void hbitmap_test_set(TestHBitmapData *data,
> > data->bits[pos] |= 1UL << bit;
> > }
> >- if (data->granularity == 0) {
> >- hbitmap_test_check(data, 0);
> >- }
> >+ hbitmap_test_check(data, 0);
> > }
> > /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
> >@@ -177,9 +172,7 @@ static void hbitmap_test_reset(TestHBitmapData *data,
> > data->bits[pos] &= ~(1UL << bit);
> > }
> >- if (data->granularity == 0) {
> >- hbitmap_test_check(data, 0);
> >- }
> >+ hbitmap_test_check(data, 0);
> > }
> > static void hbitmap_test_reset_all(TestHBitmapData *data)
> >@@ -194,9 +187,7 @@ static void hbitmap_test_reset_all(TestHBitmapData *data)
> > }
> > memset(data->bits, 0, n * sizeof(unsigned long));
> >- if (data->granularity == 0) {
> >- hbitmap_test_check(data, 0);
> >- }
> >+ hbitmap_test_check(data, 0);
> > }
> > static void hbitmap_test_check_get(TestHBitmapData *data)
> >@@ -217,13 +208,13 @@ static void hbitmap_test_check_get(TestHBitmapData
> >*data)
> > static void test_hbitmap_zero(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, 0, 0);
> >+ hbitmap_test_init(data, 0);
> > }
> > static void test_hbitmap_unaligned(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3 + 23, 0);
> >+ hbitmap_test_init(data, L3 + 23);
> > hbitmap_test_set(data, 0, 1);
> > hbitmap_test_set(data, L3 + 22, 1);
> > }
> >@@ -231,13 +222,13 @@ static void test_hbitmap_unaligned(TestHBitmapData
> >*data,
> > static void test_hbitmap_iter_empty(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L1, 0);
> >+ hbitmap_test_init(data, L1);
> > }
> > static void test_hbitmap_iter_partial(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3, 0);
> >+ hbitmap_test_init(data, L3);
> > hbitmap_test_set(data, 0, L3);
> > hbitmap_test_check(data, 1);
> > hbitmap_test_check(data, L1 - 1);
> >@@ -259,14 +250,14 @@ static void test_hbitmap_iter_partial(TestHBitmapData
> >*data,
> > static void test_hbitmap_set_all(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3, 0);
> >+ hbitmap_test_init(data, L3);
> > hbitmap_test_set(data, 0, L3);
> > }
> > static void test_hbitmap_get_all(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3, 0);
> >+ hbitmap_test_init(data, L3);
> > hbitmap_test_set(data, 0, L3);
> > hbitmap_test_check_get(data);
> > }
> >@@ -274,7 +265,7 @@ static void test_hbitmap_get_all(TestHBitmapData *data,
> > static void test_hbitmap_get_some(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, 2 * L2, 0);
> >+ hbitmap_test_init(data, 2 * L2);
> > hbitmap_test_set(data, 10, 1);
> > hbitmap_test_check_get(data);
> > hbitmap_test_set(data, L1 - 1, 1);
> >@@ -290,7 +281,7 @@ static void test_hbitmap_get_some(TestHBitmapData *data,
> > static void test_hbitmap_set_one(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, 2 * L2, 0);
> >+ hbitmap_test_init(data, 2 * L2);
> > hbitmap_test_set(data, 10, 1);
> > hbitmap_test_set(data, L1 - 1, 1);
> > hbitmap_test_set(data, L1, 1);
> >@@ -301,7 +292,7 @@ static void test_hbitmap_set_one(TestHBitmapData *data,
> > static void test_hbitmap_set_two_elem(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, 2 * L2, 0);
> >+ hbitmap_test_init(data, 2 * L2);
> > hbitmap_test_set(data, L1 - 1, 2);
> > hbitmap_test_set(data, L1 * 2 - 1, 4);
> > hbitmap_test_set(data, L1 * 4, L1 + 1);
> >@@ -315,7 +306,7 @@ static void test_hbitmap_set_two_elem(TestHBitmapData
> >*data,
> > static void test_hbitmap_set(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3 * 2, 0);
> >+ hbitmap_test_init(data, L3 * 2);
> > hbitmap_test_set(data, L1 - 1, L1 + 2);
> > hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
> > hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
> >@@ -330,7 +321,7 @@ static void test_hbitmap_set(TestHBitmapData *data,
> > static void test_hbitmap_set_twice(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L1 * 3, 0);
> >+ hbitmap_test_init(data, L1 * 3);
> > hbitmap_test_set(data, 0, L1 * 3);
> > hbitmap_test_set(data, L1, 1);
> > }
> >@@ -338,7 +329,7 @@ static void test_hbitmap_set_twice(TestHBitmapData *data,
> > static void test_hbitmap_set_overlap(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3 * 2, 0);
> >+ hbitmap_test_init(data, L3 * 2);
> > hbitmap_test_set(data, L1 - 1, L1 + 2);
> > hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
> > hbitmap_test_set(data, 0, L1 * 3);
> >@@ -354,14 +345,14 @@ static void test_hbitmap_set_overlap(TestHBitmapData
> >*data,
> > static void test_hbitmap_reset_empty(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3, 0);
> >+ hbitmap_test_init(data, L3);
> > hbitmap_test_reset(data, 0, L3);
> > }
> > static void test_hbitmap_reset(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3 * 2, 0);
> >+ hbitmap_test_init(data, L3 * 2);
> > hbitmap_test_set(data, L1 - 1, L1 + 2);
> > hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
> > hbitmap_test_set(data, 0, L1 * 3);
> >@@ -382,7 +373,7 @@ static void test_hbitmap_reset(TestHBitmapData *data,
> > static void test_hbitmap_reset_all(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_init(data, L3 * 2, 0);
> >+ hbitmap_test_init(data, L3 * 2);
> > hbitmap_test_set(data, L1 - 1, L1 + 2);
> > hbitmap_test_reset_all(data);
> > hbitmap_test_set(data, 0, L1 * 3);
> >@@ -399,52 +390,6 @@ static void test_hbitmap_reset_all(TestHBitmapData
> >*data,
> > hbitmap_test_reset_all(data);
> > }
> >-static void test_hbitmap_granularity(TestHBitmapData *data,
> >- const void *unused)
> >-{
> >- /* Note that hbitmap_test_check has to be invoked manually in this
> >test. */
> >- hbitmap_test_init(data, L1, 1);
> >- hbitmap_test_set(data, 0, 1);
> >- g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
> >- hbitmap_test_check(data, 0);
> >- hbitmap_test_set(data, 2, 1);
> >- g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
> >- hbitmap_test_check(data, 0);
> >- hbitmap_test_set(data, 0, 3);
> >- g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
> >- hbitmap_test_reset(data, 0, 1);
> >- g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
> >-}
> >-
> >-static void test_hbitmap_iter_granularity(TestHBitmapData *data,
> >- const void *unused)
> >-{
> >- HBitmapIter hbi;
> >-
> >- /* Note that hbitmap_test_check has to be invoked manually in this
> >test. */
> >- hbitmap_test_init(data, 131072 << 7, 7);
> >- hbitmap_iter_init(&hbi, data->hb, 0);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> >-
> >- hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
> >- hbitmap_iter_init(&hbi, data->hb, 0);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> >-
> >- hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> >-
> >- hbitmap_test_set(data, (131072 << 7) - 8, 8);
> >- hbitmap_iter_init(&hbi, data->hb, 0);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> >-
> >- hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> >- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> >-}
> >-
> > static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t
> > diff)
> > {
> > size_t size = data->size;
> >@@ -460,40 +405,21 @@ static void
> >hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
> > }
> > /* Last bit */
> > hbitmap_test_set(data, size - 1, 1);
> >- if (data->granularity == 0) {
> >- hbitmap_test_check_get(data);
> >- }
> >+ hbitmap_test_check_get(data);
> > }
> > static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
> > {
> >- size_t size = MIN(data->size, data->old_size);
> >-
> >- if (data->granularity == 0) {
> >- hbitmap_test_check_get(data);
> >- hbitmap_test_check(data, 0);
> >- } else {
> >- /* If a granularity was set, note that every distinct
> >- * (bit >> granularity) value that was set will increase
> >- * the bit pop count by 2^granularity, not just 1.
> >- *
> >- * The hbitmap_test_check facility does not currently tolerate
> >- * non-zero granularities, so test the boundaries and the population
> >- * count manually.
> >- */
> >- g_assert(hbitmap_get(data->hb, 0));
> >- g_assert(hbitmap_get(data->hb, size - 1));
> >- g_assert_cmpint(2 << data->granularity, ==,
> >hbitmap_count(data->hb));
> >- }
> >+ hbitmap_test_check_get(data);
> >+ hbitmap_test_check(data, 0);
> > }
> > /* Generic truncate test. */
> > static void hbitmap_test_truncate(TestHBitmapData *data,
> > size_t size,
> >- ssize_t diff,
> >- int granularity)
> >+ ssize_t diff)
> > {
> >- hbitmap_test_init(data, size, granularity);
> >+ hbitmap_test_init(data, size);
> > hbitmap_test_set_boundary_bits(data, diff);
> > hbitmap_test_truncate_impl(data, size + diff);
> > hbitmap_test_check_boundary_bits(data);
> >@@ -502,63 +428,7 @@ static void hbitmap_test_truncate(TestHBitmapData *data,
> > static void test_hbitmap_truncate_nop(TestHBitmapData *data,
> > const void *unused)
> > {
> >- hbitmap_test_truncate(data, L2, 0, 0);
> >-}
> >-
> >-/**
> >- * Grow by an amount smaller than the granularity, without crossing
> >- * a granularity alignment boundary. Effectively a NOP.
> >- */
> >-static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
> >- const void *unused)
> >-{
> >- size_t size = L2 - 1;
> >- size_t diff = 1;
> >- int granularity = 1;
> >-
> >- hbitmap_test_truncate(data, size, diff, granularity);
> >-}
> >-
> >-/**
> >- * Shrink by an amount smaller than the granularity, without crossing
> >- * a granularity alignment boundary. Effectively a NOP.
> >- */
> >-static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
> >- const void *unused)
> >-{
> >- size_t size = L2;
> >- ssize_t diff = -1;
> >- int granularity = 1;
> >-
> >- hbitmap_test_truncate(data, size, diff, granularity);
> >-}
> >-
> >-/**
> >- * Grow by an amount smaller than the granularity, but crossing over
> >- * a granularity alignment boundary.
> >- */
> >-static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
> >- const void *unused)
> >-{
> >- size_t size = L2 - 2;
> >- ssize_t diff = 1;
> >- int granularity = 1;
> >-
> >- hbitmap_test_truncate(data, size, diff, granularity);
> >-}
> >-
> >-/**
> >- * Shrink by an amount smaller than the granularity, but crossing over
> >- * a granularity alignment boundary.
> >- */
> >-static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
> >- const void *unused)
> >-{
> >- size_t size = L2 - 1;
> >- ssize_t diff = -1;
> >- int granularity = 1;
> >-
> >- hbitmap_test_truncate(data, size, diff, granularity);
> >+ hbitmap_test_truncate(data, L2, 0);
> > }
> > /**
> >@@ -571,7 +441,7 @@ static void
> >test_hbitmap_truncate_grow_small(TestHBitmapData *data,
> > size_t size = L2 + 1;
> > size_t diff = sizeof(long) / 2;
> >- hbitmap_test_truncate(data, size, diff, 0);
> >+ hbitmap_test_truncate(data, size, diff);
> > }
> > /**
> >@@ -584,7 +454,7 @@ static void
> >test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
> > size_t size = L2;
> > size_t diff = sizeof(long) / 2;
> >- hbitmap_test_truncate(data, size, -diff, 0);
> >+ hbitmap_test_truncate(data, size, -diff);
> > }
> > /**
> >@@ -597,7 +467,7 @@ static void
> >test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
> > size_t size = L2 - 1;
> > size_t diff = sizeof(long) / 2;
> >- hbitmap_test_truncate(data, size, diff, 0);
> >+ hbitmap_test_truncate(data, size, diff);
> > }
> > /**
> >@@ -610,7 +480,7 @@ static void
> >test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
> > size_t size = L2 + 1;
> > size_t diff = sizeof(long) / 2;
> >- hbitmap_test_truncate(data, size, -diff, 0);
> >+ hbitmap_test_truncate(data, size, -diff);
> > }
> > /**
> >@@ -622,7 +492,7 @@ static void
> >test_hbitmap_truncate_grow_large(TestHBitmapData *data,
> > size_t size = L2;
> > size_t diff = 8 * sizeof(long);
> >- hbitmap_test_truncate(data, size, diff, 0);
> >+ hbitmap_test_truncate(data, size, diff);
> > }
> > /**
> >@@ -634,7 +504,7 @@ static void
> >test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
> > size_t size = L2;
> > size_t diff = 8 * sizeof(long);
> >- hbitmap_test_truncate(data, size, -diff, 0);
> >+ hbitmap_test_truncate(data, size, -diff);
> > }
> > static void hbitmap_test_add(const char *testpath,
> >@@ -651,7 +521,6 @@ int main(int argc, char **argv)
> > hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
> > hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
> > hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
> >- hbitmap_test_add("/hbitmap/iter/granularity",
> >test_hbitmap_iter_granularity);
> > hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
> > hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
> > hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
> >@@ -663,17 +532,8 @@ int main(int argc, char **argv)
> > hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
> > hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
> > hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
> >- hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
> > hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
> >- hbitmap_test_add("/hbitmap/truncate/grow/negligible",
> >- test_hbitmap_truncate_grow_negligible);
> >- hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
> >- test_hbitmap_truncate_shrink_negligible);
> >- hbitmap_test_add("/hbitmap/truncate/grow/tiny",
> >- test_hbitmap_truncate_grow_tiny);
> >- hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
> >- test_hbitmap_truncate_shrink_tiny);
> > hbitmap_test_add("/hbitmap/truncate/grow/small",
> > test_hbitmap_truncate_grow_small);
> > hbitmap_test_add("/hbitmap/truncate/shrink/small",
> >diff --git a/util/hbitmap.c b/util/hbitmap.c
> >index 50b888f..31df7c0 100644
> >--- a/util/hbitmap.c
> >+++ b/util/hbitmap.c
> >@@ -61,26 +61,6 @@ struct HBitmap {
> > /* Number of set bits in the bottom level. */
> > uint64_t count;
> >- /* A scaling factor. Given a granularity of G, each bit in the bitmap
> >will
> >- * will actually represent a group of 2^G elements. Each operation on a
> >- * range of bits first rounds the bits to determine which group they
> >land
> >- * in, and then affect the entire page; iteration will only visit the
> >first
> >- * bit of each group. Here is an example of operations in a size-16,
> >- * granularity-1 HBitmap:
> >- *
> >- * initial state 00000000
> >- * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
> >- * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
> >- * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
> >- * reset(start=5, count=5) 00000000
> >- *
> >- * From an implementation point of view, when setting or resetting bits,
> >- * the bitmap will scale bit numbers right by this amount of bits. When
> >- * iterating, the bitmap will scale bit numbers left by this amount of
> >- * bits.
> >- */
> >- int granularity;
> >-
> > /* A number of progressively less coarse bitmaps (i.e. level 0 is the
> > * coarsest). Each bit in level N represents a word in level N+1 that
> > * has a set bit, except the last level where each bit represents the
> >@@ -145,10 +125,9 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap
> >*hb, uint64_t first)
> > uint64_t pos;
> > hbi->hb = hb;
> >- pos = first >> hb->granularity;
> >+ pos = first;
> > assert(pos < hb->size);
> > hbi->pos = pos >> BITS_PER_LEVEL;
> >- hbi->granularity = hb->granularity;
> > for (i = HBITMAP_LEVELS; i-- > 0; ) {
> > bit = pos & (BITS_PER_LONG - 1);
> >@@ -171,18 +150,13 @@ bool hbitmap_empty(const HBitmap *hb)
> > return hb->count == 0;
> > }
> >-int hbitmap_granularity(const HBitmap *hb)
> >-{
> >- return hb->granularity;
> >-}
> >-
> > uint64_t hbitmap_count(const HBitmap *hb)
> > {
> >- return hb->count << hb->granularity;
> >+ return hb->count;
> > }
> >-/* Count the number of set bits between start and end, not accounting for
> >- * the granularity. Also an example of how to use hbitmap_iter_next_word.
> >+/* Count the number of set bits between start and end.
> >+ * Also an example of how to use hbitmap_iter_next_word.
> > */
> > static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t
> > last)
> > {
> >@@ -192,7 +166,7 @@ static uint64_t hb_count_between(HBitmap *hb, uint64_t
> >start, uint64_t last)
> > unsigned long cur;
> > size_t pos;
> >- hbitmap_iter_init(&hbi, hb, start << hb->granularity);
> >+ hbitmap_iter_init(&hbi, hb, start);
> > for (;;) {
> > pos = hbitmap_iter_next_word(&hbi, &cur);
> > if (pos >= (end >> BITS_PER_LEVEL)) {
> >@@ -266,11 +240,8 @@ void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t
> >count)
> > /* Compute range in the last layer. */
> > uint64_t last = start + count - 1;
> >- trace_hbitmap_set(hb, start, count,
> >- start >> hb->granularity, last >> hb->granularity);
> >+ trace_hbitmap_set(hb, start, count, start, last);
> >- start >>= hb->granularity;
> >- last >>= hb->granularity;
> > count = last - start + 1;
> > hb->count += count - hb_count_between(hb, start, last);
> >@@ -346,11 +317,7 @@ void hbitmap_reset(HBitmap *hb, uint64_t start,
> >uint64_t count)
> > /* Compute range in the last layer. */
> > uint64_t last = start + count - 1;
> >- trace_hbitmap_reset(hb, start, count,
> >- start >> hb->granularity, last >> hb->granularity);
> >-
> >- start >>= hb->granularity;
> >- last >>= hb->granularity;
> >+ trace_hbitmap_reset(hb, start, count, start, last);
> > hb->count -= hb_count_between(hb, start, last);
> > hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
> >@@ -372,7 +339,7 @@ void hbitmap_reset_all(HBitmap *hb)
> > bool hbitmap_get(const HBitmap *hb, uint64_t item)
> > {
> > /* Compute position and bit in the last layer. */
> >- uint64_t pos = item >> hb->granularity;
> >+ uint64_t pos = item;
> > unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
> > return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit)
> > != 0;
> >@@ -387,17 +354,14 @@ void hbitmap_free(HBitmap *hb)
> > g_free(hb);
> > }
> >-HBitmap *hbitmap_alloc(uint64_t size, int granularity)
> >+HBitmap *hbitmap_alloc(uint64_t size)
> > {
> > HBitmap *hb = g_new0(struct HBitmap, 1);
> > unsigned i;
> >- assert(granularity >= 0 && granularity < 64);
> >- size = (size + (1ULL << granularity) - 1) >> granularity;
> > assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
> > hb->size = size;
> >- hb->granularity = granularity;
> > for (i = HBITMAP_LEVELS; i-- > 0; ) {
> > size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
> > hb->sizes[i] = size;
> >@@ -420,8 +384,6 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
> > uint64_t num_elements = size;
> > uint64_t old;
> >- /* Size comes in as logical elements, adjust for granularity. */
> >- size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
> > assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
> > shrink = size < hb->size;
> >@@ -435,10 +397,8 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
> > * us from carrying around garbage bits beyond the end of the map.
> > */
> > if (shrink) {
> >- /* Don't clear partial granularity groups;
> >- * start at the first full one. */
> >- uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
> >- uint64_t fix_count = (hb->size << hb->granularity) - start;
> >+ uint64_t start = num_elements;
> >+ uint64_t fix_count = hb->size - start;
> > assert(fix_count);
> > hbitmap_reset(hb, start, fix_count);
> >@@ -473,7 +433,7 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
> > int i;
> > uint64_t j;
> >- if ((a->size != b->size) || (a->granularity != b->granularity)) {
> >+ if (a->size != b->size) {
> > return false;
> > }
>
> Ok for me, one question:
>
> Is it ok, that you are deleting some test cases, where granularity =
> 1? Shouldn't they be tuned to test bitmap with granularity = 0, or
> they just tests granularity itself?
"Granularity = 0" is the "1:1" case, while "granularity = 1" is the "1 bit for
2 items" scaling. So I deleted those and only left the "0" cases.
Fam
