From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:58435) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZzoSp-00052g-Bu for qemu-devel@nongnu.org; Fri, 20 Nov 2015 11:23:10 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZzoSk-0008Dp-Cz for qemu-devel@nongnu.org; Fri, 20 Nov 2015 11:23:07 -0500 Message-ID: <564F48D8.3010401@virtuozzo.com> Date: Fri, 20 Nov 2015 19:22:48 +0300 From: Vladimir Sementsov-Ogievskiy MIME-Version: 1.0 References: <1448013593-14282-1-git-send-email-famz@redhat.com> <1448013593-14282-4-git-send-email-famz@redhat.com> In-Reply-To: <1448013593-14282-4-git-send-email-famz@redhat.com> Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH for 2.6 3/3] hbitmap: Drop "granularity" List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Fam Zheng , qemu-devel@nongnu.org Cc: Kevin Wolf , qemu-block@nongnu.org, Jeff Cody , mreitz@redhat.com, pbonzini@redhat.com, jsnow@redhat.com 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 > --- > 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? -- Best regards, Vladimir * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.