[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH v3 4/4] hbitmap: Drop "granularity"
|
From: |
Fam Zheng |
|
Subject: |
[Qemu-devel] [PATCH v3 4/4] hbitmap: Drop "granularity" |
|
Date: |
Wed, 25 Nov 2015 12:19:20 +0800 |
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 <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