From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:46069) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1a1RYt-00051g-Fh for qemu-devel@nongnu.org; Tue, 24 Nov 2015 23:20:09 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1a1RYr-0003xt-0A for qemu-devel@nongnu.org; Tue, 24 Nov 2015 23:20:07 -0500 From: Fam Zheng Date: Wed, 25 Nov 2015 12:19:20 +0800 Message-Id: <1448425160-26092-5-git-send-email-famz@redhat.com> In-Reply-To: <1448425160-26092-1-git-send-email-famz@redhat.com> References: <1448425160-26092-1-git-send-email-famz@redhat.com> Subject: [Qemu-devel] [PATCH v3 4/4] hbitmap: Drop "granularity" List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: Kevin Wolf , vsementsov@virtuozzo.com, qemu-block@nongnu.org, Jeff Cody , mreitz@redhat.com, pbonzini@redhat.com, jsnow@redhat.com Now all callers except the test code use zero, 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; } -- 2.4.3