[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-block] [PATCH for 2.6 3/3] hbitmap: Drop "granularity"
|
From: |
Fam Zheng |
|
Subject: |
[Qemu-block] [PATCH for 2.6 3/3] hbitmap: Drop "granularity" |
|
Date: |
Fri, 20 Nov 2015 17:59:53 +0800 |
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 <address@hidden>
---
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 address@hidden
- * 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