* [Qemu-devel] [PATCH v2 2/3] block: Hide HBitmap in block dirty bitmap interface
2015-11-24 5:30 [Qemu-devel] [PATCH v2 0/3] Bitmap clean-up patches for 2.6 Fam Zheng
2015-11-24 5:30 ` [Qemu-devel] [PATCH v2 1/3] backup: Use Bitmap to replace "s->bitmap" Fam Zheng
@ 2015-11-24 5:30 ` Fam Zheng
2015-11-24 5:30 ` [Qemu-devel] [PATCH v2 3/3] hbitmap: Drop "granularity" Fam Zheng
2 siblings, 0 replies; 4+ messages in thread
From: Fam Zheng @ 2015-11-24 5:30 UTC (permalink / raw)
To: qemu-devel
Cc: Kevin Wolf, vsementsov, qemu-block, Jeff Cody, mreitz, pbonzini,
jsnow
HBitmap is an implementation detail of block dirty bitmap that should be hidden
from users. Introduce a BdrvDirtyBitmapIter to encapsulate the underlying
HBitmapIter.
A small difference in the interface is, before, an HBitmapIter is initialized
in place, now the new BdrvDirtyBitmapIter must be dynamically allocated because
the structure definition is in block.c.
Two current users are converted too.
Signed-off-by: Fam Zheng <famz@redhat.com>
---
block.c | 79 ++++++++++++++++++++++++++++++++++++++-------------
block/backup.c | 14 +++++----
block/mirror.c | 14 +++++----
include/block/block.h | 9 ++++--
4 files changed, 82 insertions(+), 34 deletions(-)
diff --git a/block.c b/block.c
index 3a7324b..e225050 100644
--- a/block.c
+++ b/block.c
@@ -63,14 +63,22 @@
* or enabled. A frozen bitmap can only abdicate() or reclaim().
*/
struct BdrvDirtyBitmap {
+ int gran_shift; /* Bits to right shift from sector number to
+ bit index. */
HBitmap *bitmap; /* Dirty sector bitmap implementation */
BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
char *name; /* Optional non-empty unique ID */
int64_t size; /* Size of the bitmap (Number of sectors) */
bool disabled; /* Bitmap is read-only */
+ int active_iterators; /* How many iterators are active */
QLIST_ENTRY(BdrvDirtyBitmap) list;
};
+struct BdrvDirtyBitmapIter {
+ HBitmapIter hbi;
+ BdrvDirtyBitmap *bitmap;
+};
+
#define NOT_DONE 0x7fffffff /* used while emulated sync operation in progress */
struct BdrvStates bdrv_states = QTAILQ_HEAD_INITIALIZER(bdrv_states);
@@ -3157,24 +3165,26 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
{
int64_t bitmap_size;
BdrvDirtyBitmap *bitmap;
- uint32_t sector_granularity;
+ int gran_shift;
assert((granularity & (granularity - 1)) == 0);
+ /* Caller should check that */
+ assert(granularity >= BDRV_SECTOR_SIZE);
+ gran_shift = ctz32(granularity) - BDRV_SECTOR_BITS;
if (name && bdrv_find_dirty_bitmap(bs, name)) {
error_setg(errp, "Bitmap already exists: %s", name);
return NULL;
}
- sector_granularity = granularity >> BDRV_SECTOR_BITS;
- assert(sector_granularity);
- bitmap_size = bdrv_nb_sectors(bs);
+ bitmap_size = DIV_ROUND_UP(bdrv_getlength(bs), granularity);
if (bitmap_size < 0) {
error_setg_errno(errp, -bitmap_size, "could not get length of device");
errno = -bitmap_size;
return NULL;
}
bitmap = g_new0(BdrvDirtyBitmap, 1);
- bitmap->bitmap = hbitmap_alloc(bitmap_size, ctz32(sector_granularity));
+ bitmap->bitmap = hbitmap_alloc(bitmap_size, 0);
+ bitmap->gran_shift = gran_shift;
bitmap->size = bitmap_size;
bitmap->name = g_strdup(name);
bitmap->disabled = false;
@@ -3293,9 +3303,10 @@ BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap(BlockDriverState *bs,
static void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
{
BdrvDirtyBitmap *bitmap;
- uint64_t size = bdrv_nb_sectors(bs);
QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
+ int64_t size = bdrv_nb_sectors(bs) >> bitmap->gran_shift;
+ /* TODO: what if size < 0? */
assert(!bdrv_dirty_bitmap_frozen(bitmap));
hbitmap_truncate(bitmap->bitmap, size);
bitmap->size = size;
@@ -3307,6 +3318,7 @@ void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap)
BdrvDirtyBitmap *bm, *next;
QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
if (bm == bitmap) {
+ assert(!bitmap->active_iterators);
assert(!bdrv_dirty_bitmap_frozen(bm));
QLIST_REMOVE(bitmap, list);
hbitmap_free(bitmap->bitmap);
@@ -3354,7 +3366,7 @@ BlockDirtyInfoList *bdrv_query_dirty_bitmaps(BlockDriverState *bs)
int bdrv_get_dirty(BlockDriverState *bs, BdrvDirtyBitmap *bitmap, int64_t sector)
{
if (bitmap) {
- return hbitmap_get(bitmap->bitmap, sector);
+ return hbitmap_get(bitmap->bitmap, sector >> bitmap->gran_shift);
} else {
return 0;
}
@@ -3382,26 +3394,56 @@ uint32_t bdrv_get_default_bitmap_granularity(BlockDriverState *bs)
uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
{
- return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
+ return BDRV_SECTOR_SIZE << bitmap->gran_shift;
}
-void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, HBitmapIter *hbi)
+BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
+ uint64_t first_sector)
{
- hbitmap_iter_init(hbi, bitmap->bitmap, 0);
+ BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
+ hbitmap_iter_init(&iter->hbi, bitmap->bitmap,
+ first_sector >> bitmap->gran_shift);
+ iter->bitmap = bitmap;
+ bitmap->active_iterators++;
+ return iter;
+}
+
+void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
+{
+ if (!iter) {
+ return;
+ }
+ assert(iter->bitmap->active_iterators > 0);
+ iter->bitmap->active_iterators--;
+ g_free(iter);
+}
+
+int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
+{
+ int64_t ret = hbitmap_iter_next(&iter->hbi);
+ return ret < 0 ? ret : ret << iter->bitmap->gran_shift;
}
void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
int64_t cur_sector, int nr_sectors)
{
+ int64_t start = cur_sector >> bitmap->gran_shift;
+ int64_t end = DIV_ROUND_UP(cur_sector + nr_sectors,
+ 1 << bitmap->gran_shift);
+
assert(bdrv_dirty_bitmap_enabled(bitmap));
- hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
+ hbitmap_set(bitmap->bitmap, start, end - start);
}
void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
int64_t cur_sector, int nr_sectors)
{
+ int64_t start = cur_sector >> bitmap->gran_shift;
+ int64_t end = DIV_ROUND_UP(cur_sector + nr_sectors,
+ 1 << bitmap->gran_shift);
+
assert(bdrv_dirty_bitmap_enabled(bitmap));
- hbitmap_reset(bitmap->bitmap, cur_sector, nr_sectors);
+ hbitmap_reset(bitmap->bitmap, start, end - start);
}
void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap **out)
@@ -3411,8 +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,
- hbitmap_granularity(backup));
+ bitmap->bitmap = hbitmap_alloc(bitmap->size, 0);
*out = backup;
}
}
@@ -3433,22 +3474,22 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
if (!bdrv_dirty_bitmap_enabled(bitmap)) {
continue;
}
- hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
+ bdrv_set_dirty_bitmap(bitmap, cur_sector, nr_sectors);
}
}
/**
* Advance an HBitmapIter to an arbitrary offset.
*/
-void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
+void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *iter, int64_t sector_num)
{
- assert(hbi->hb);
- hbitmap_iter_init(hbi, hbi->hb, offset);
+ hbitmap_iter_init(&iter->hbi, iter->bitmap->bitmap,
+ sector_num >> iter->bitmap->gran_shift);
}
int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
{
- return hbitmap_count(bitmap->bitmap);
+ return hbitmap_count(bitmap->bitmap) << bitmap->gran_shift;
}
/* Get a reference to bs */
diff --git a/block/backup.c b/block/backup.c
index 695b698..ecbfb56 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -326,14 +326,14 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
int64_t end;
int64_t last_cluster = -1;
BlockDriverState *bs = job->common.bs;
- HBitmapIter hbi;
+ BdrvDirtyBitmapIter *dbi;
granularity = bdrv_dirty_bitmap_granularity(job->sync_bitmap);
clusters_per_iter = MAX((granularity / BACKUP_CLUSTER_SIZE), 1);
- bdrv_dirty_iter_init(job->sync_bitmap, &hbi);
+ dbi = bdrv_dirty_iter_new(job->sync_bitmap, 0);
/* Find the next dirty sector(s) */
- while ((sector = hbitmap_iter_next(&hbi)) != -1) {
+ while ((sector = bdrv_dirty_iter_next(dbi)) != -1) {
cluster = sector / BACKUP_SECTORS_PER_CLUSTER;
/* Fake progress updates for any clusters we skipped */
@@ -345,7 +345,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
for (end = cluster + clusters_per_iter; cluster < end; cluster++) {
do {
if (yield_and_check(job)) {
- return ret;
+ goto out;
}
ret = backup_do_cow(bs, cluster * BACKUP_SECTORS_PER_CLUSTER,
BACKUP_SECTORS_PER_CLUSTER, &error_is_read,
@@ -353,7 +353,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
if ((ret < 0) &&
backup_error_action(job, error_is_read, -ret) ==
BLOCK_ERROR_ACTION_REPORT) {
- return ret;
+ goto out;
}
} while (ret < 0);
}
@@ -361,7 +361,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
/* If the bitmap granularity is smaller than the backup granularity,
* we need to advance the iterator pointer to the next cluster. */
if (granularity < BACKUP_CLUSTER_SIZE) {
- bdrv_set_dirty_iter(&hbi, cluster * BACKUP_SECTORS_PER_CLUSTER);
+ bdrv_set_dirty_iter(dbi, cluster * BACKUP_SECTORS_PER_CLUSTER);
}
last_cluster = cluster - 1;
@@ -373,6 +373,8 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
job->common.offset += ((end - last_cluster - 1) * BACKUP_CLUSTER_SIZE);
}
+out:
+ bdrv_dirty_iter_free(dbi);
return ret;
}
diff --git a/block/mirror.c b/block/mirror.c
index 52c9abf..6515455 100644
--- a/block/mirror.c
+++ b/block/mirror.c
@@ -51,7 +51,7 @@ typedef struct MirrorBlockJob {
int64_t bdev_length;
unsigned long *cow_bitmap;
BdrvDirtyBitmap *dirty_bitmap;
- HBitmapIter hbi;
+ BdrvDirtyBitmapIter *dbi;
uint8_t *buf;
QSIMPLEQ_HEAD(, MirrorBuffer) buf_free;
int buf_free_count;
@@ -167,10 +167,11 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
int pnum;
int64_t ret;
- s->sector_num = hbitmap_iter_next(&s->hbi);
+ s->sector_num = bdrv_dirty_iter_next(s->dbi);
if (s->sector_num < 0) {
- bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
- s->sector_num = hbitmap_iter_next(&s->hbi);
+ bdrv_dirty_iter_free(s->dbi);
+ s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
+ s->sector_num = bdrv_dirty_iter_next(s->dbi);
trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
assert(s->sector_num >= 0);
}
@@ -288,7 +289,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
*/
if (next_sector > hbitmap_next_sector
&& bdrv_get_dirty(source, s->dirty_bitmap, next_sector)) {
- hbitmap_next_sector = hbitmap_iter_next(&s->hbi);
+ hbitmap_next_sector = bdrv_dirty_iter_next(s->dbi);
}
next_sector += sectors_per_chunk;
@@ -487,7 +488,7 @@ static void coroutine_fn mirror_run(void *opaque)
}
}
- bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
+ s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
for (;;) {
uint64_t delay_ns = 0;
int64_t cnt;
@@ -600,6 +601,7 @@ immediate_exit:
qemu_vfree(s->buf);
g_free(s->cow_bitmap);
g_free(s->in_flight_bitmap);
+ bdrv_dirty_iter_free(s->dbi);
bdrv_release_dirty_bitmap(bs, s->dirty_bitmap);
if (s->target->blk) {
blk_iostatus_disable(s->target->blk);
diff --git a/include/block/block.h b/include/block/block.h
index 73edb1a..bc6f2e3 100644
--- a/include/block/block.h
+++ b/include/block/block.h
@@ -470,8 +470,8 @@ void *qemu_try_blockalign(BlockDriverState *bs, size_t size);
void *qemu_try_blockalign0(BlockDriverState *bs, size_t size);
bool bdrv_qiov_is_aligned(BlockDriverState *bs, QEMUIOVector *qiov);
-struct HBitmapIter;
typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
+typedef struct BdrvDirtyBitmapIter BdrvDirtyBitmapIter;
BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
uint32_t granularity,
const char *name,
@@ -502,8 +502,11 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
int64_t cur_sector, int nr_sectors);
void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
int64_t cur_sector, int nr_sectors);
-void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, struct HBitmapIter *hbi);
-void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t offset);
+BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
+ uint64_t first_sector);
+void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
+int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
+void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
void bdrv_enable_copy_on_read(BlockDriverState *bs);
--
2.4.3
^ permalink raw reply related [flat|nested] 4+ messages in thread* [Qemu-devel] [PATCH v2 3/3] hbitmap: Drop "granularity"
2015-11-24 5:30 [Qemu-devel] [PATCH v2 0/3] Bitmap clean-up patches for 2.6 Fam Zheng
2015-11-24 5:30 ` [Qemu-devel] [PATCH v2 1/3] backup: Use Bitmap to replace "s->bitmap" Fam Zheng
2015-11-24 5:30 ` [Qemu-devel] [PATCH v2 2/3] block: Hide HBitmap in block dirty bitmap interface Fam Zheng
@ 2015-11-24 5:30 ` Fam Zheng
2 siblings, 0 replies; 4+ messages in thread
From: Fam Zheng @ 2015-11-24 5:30 UTC (permalink / raw)
To: qemu-devel
Cc: Kevin Wolf, vsementsov, qemu-block, Jeff Cody, mreitz, pbonzini,
jsnow
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 <famz@redhat.com>
---
block.c | 4 +-
include/qemu/hbitmap.h | 20 +----
tests/test-hbitmap.c | 206 ++++++++-----------------------------------------
util/hbitmap.c | 64 +++------------
4 files changed, 49 insertions(+), 245 deletions(-)
diff --git a/block.c b/block.c
index e225050..86b32a0 100644
--- a/block.c
+++ b/block.c
@@ -3183,7 +3183,7 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
return NULL;
}
bitmap = g_new0(BdrvDirtyBitmap, 1);
- bitmap->bitmap = hbitmap_alloc(bitmap_size, 0);
+ bitmap->bitmap = hbitmap_alloc(bitmap_size);
bitmap->gran_shift = gran_shift;
bitmap->size = bitmap_size;
bitmap->name = g_strdup(name);
@@ -3453,7 +3453,7 @@ void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap **out)
hbitmap_reset_all(bitmap->bitmap);
} else {
HBitmap *backup = bitmap->bitmap;
- bitmap->bitmap = hbitmap_alloc(bitmap->size, 0);
+ bitmap->bitmap = hbitmap_alloc(bitmap->size);
*out = backup;
}
}
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index bb94a00..0f81483 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -39,9 +39,6 @@ typedef struct HBitmapIter HBitmapIter;
struct HBitmapIter {
const HBitmap *hb;
- /* Copied from hb for access in the inline functions (hb is opaque). */
- int granularity;
-
/* Entry offset into the last-level array of longs. */
size_t pos;
@@ -54,15 +51,10 @@ struct HBitmapIter {
/**
* hbitmap_alloc:
* @size: Number of bits in the bitmap.
- * @granularity: Granularity of the bitmap. Aligned groups of 2^@granularity
- * bits will be represented by a single bit. Each operation on a
- * range of bits first rounds the bits to determine which group they land
- * in, and then affect the entire set; iteration will only visit the first
- * bit of each group.
*
* Allocate a new HBitmap.
*/
-HBitmap *hbitmap_alloc(uint64_t size, int granularity);
+HBitmap *hbitmap_alloc(uint64_t size);
/**
* hbitmap_truncate:
@@ -96,14 +88,6 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b);
bool hbitmap_empty(const HBitmap *hb);
/**
- * hbitmap_granularity:
- * @hb: HBitmap to operate on.
- *
- * Return the granularity of the HBitmap.
- */
-int hbitmap_granularity(const HBitmap *hb);
-
-/**
* hbitmap_count:
* @hb: HBitmap to operate on.
*
@@ -204,7 +188,7 @@ static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
- return item << hbi->granularity;
+ return item;
}
/**
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index abcea0c..dc8485a 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -26,7 +26,6 @@ typedef struct TestHBitmapData {
unsigned long *bits;
size_t size;
size_t old_size;
- int granularity;
} TestHBitmapData;
@@ -70,17 +69,16 @@ static void hbitmap_test_check(TestHBitmapData *data,
}
if (first == 0) {
- g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
+ g_assert_cmpint(count, ==, hbitmap_count(data->hb));
}
}
/* This is provided instead of a test setup function so that the sizes
are kept in the test functions (and not in main()) */
-static void hbitmap_test_init(TestHBitmapData *data,
- uint64_t size, int granularity)
+static void hbitmap_test_init(TestHBitmapData *data, uint64_t size)
{
size_t n;
- data->hb = hbitmap_alloc(size, granularity);
+ data->hb = hbitmap_alloc(size);
n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
if (n == 0) {
@@ -88,7 +86,6 @@ static void hbitmap_test_init(TestHBitmapData *data,
}
data->bits = g_new0(unsigned long, n);
data->size = size;
- data->granularity = granularity;
if (size) {
hbitmap_test_check(data, 0);
}
@@ -158,9 +155,7 @@ static void hbitmap_test_set(TestHBitmapData *data,
data->bits[pos] |= 1UL << bit;
}
- if (data->granularity == 0) {
- hbitmap_test_check(data, 0);
- }
+ hbitmap_test_check(data, 0);
}
/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
@@ -177,9 +172,7 @@ static void hbitmap_test_reset(TestHBitmapData *data,
data->bits[pos] &= ~(1UL << bit);
}
- if (data->granularity == 0) {
- hbitmap_test_check(data, 0);
- }
+ hbitmap_test_check(data, 0);
}
static void hbitmap_test_reset_all(TestHBitmapData *data)
@@ -194,9 +187,7 @@ static void hbitmap_test_reset_all(TestHBitmapData *data)
}
memset(data->bits, 0, n * sizeof(unsigned long));
- if (data->granularity == 0) {
- hbitmap_test_check(data, 0);
- }
+ hbitmap_test_check(data, 0);
}
static void hbitmap_test_check_get(TestHBitmapData *data)
@@ -217,13 +208,13 @@ static void hbitmap_test_check_get(TestHBitmapData *data)
static void test_hbitmap_zero(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, 0, 0);
+ hbitmap_test_init(data, 0);
}
static void test_hbitmap_unaligned(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3 + 23, 0);
+ hbitmap_test_init(data, L3 + 23);
hbitmap_test_set(data, 0, 1);
hbitmap_test_set(data, L3 + 22, 1);
}
@@ -231,13 +222,13 @@ static void test_hbitmap_unaligned(TestHBitmapData *data,
static void test_hbitmap_iter_empty(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L1, 0);
+ hbitmap_test_init(data, L1);
}
static void test_hbitmap_iter_partial(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3, 0);
+ hbitmap_test_init(data, L3);
hbitmap_test_set(data, 0, L3);
hbitmap_test_check(data, 1);
hbitmap_test_check(data, L1 - 1);
@@ -259,14 +250,14 @@ static void test_hbitmap_iter_partial(TestHBitmapData *data,
static void test_hbitmap_set_all(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3, 0);
+ hbitmap_test_init(data, L3);
hbitmap_test_set(data, 0, L3);
}
static void test_hbitmap_get_all(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3, 0);
+ hbitmap_test_init(data, L3);
hbitmap_test_set(data, 0, L3);
hbitmap_test_check_get(data);
}
@@ -274,7 +265,7 @@ static void test_hbitmap_get_all(TestHBitmapData *data,
static void test_hbitmap_get_some(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, 2 * L2, 0);
+ hbitmap_test_init(data, 2 * L2);
hbitmap_test_set(data, 10, 1);
hbitmap_test_check_get(data);
hbitmap_test_set(data, L1 - 1, 1);
@@ -290,7 +281,7 @@ static void test_hbitmap_get_some(TestHBitmapData *data,
static void test_hbitmap_set_one(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, 2 * L2, 0);
+ hbitmap_test_init(data, 2 * L2);
hbitmap_test_set(data, 10, 1);
hbitmap_test_set(data, L1 - 1, 1);
hbitmap_test_set(data, L1, 1);
@@ -301,7 +292,7 @@ static void test_hbitmap_set_one(TestHBitmapData *data,
static void test_hbitmap_set_two_elem(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, 2 * L2, 0);
+ hbitmap_test_init(data, 2 * L2);
hbitmap_test_set(data, L1 - 1, 2);
hbitmap_test_set(data, L1 * 2 - 1, 4);
hbitmap_test_set(data, L1 * 4, L1 + 1);
@@ -315,7 +306,7 @@ static void test_hbitmap_set_two_elem(TestHBitmapData *data,
static void test_hbitmap_set(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3 * 2, 0);
+ hbitmap_test_init(data, L3 * 2);
hbitmap_test_set(data, L1 - 1, L1 + 2);
hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
@@ -330,7 +321,7 @@ static void test_hbitmap_set(TestHBitmapData *data,
static void test_hbitmap_set_twice(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L1 * 3, 0);
+ hbitmap_test_init(data, L1 * 3);
hbitmap_test_set(data, 0, L1 * 3);
hbitmap_test_set(data, L1, 1);
}
@@ -338,7 +329,7 @@ static void test_hbitmap_set_twice(TestHBitmapData *data,
static void test_hbitmap_set_overlap(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3 * 2, 0);
+ hbitmap_test_init(data, L3 * 2);
hbitmap_test_set(data, L1 - 1, L1 + 2);
hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
hbitmap_test_set(data, 0, L1 * 3);
@@ -354,14 +345,14 @@ static void test_hbitmap_set_overlap(TestHBitmapData *data,
static void test_hbitmap_reset_empty(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3, 0);
+ hbitmap_test_init(data, L3);
hbitmap_test_reset(data, 0, L3);
}
static void test_hbitmap_reset(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3 * 2, 0);
+ hbitmap_test_init(data, L3 * 2);
hbitmap_test_set(data, L1 - 1, L1 + 2);
hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
hbitmap_test_set(data, 0, L1 * 3);
@@ -382,7 +373,7 @@ static void test_hbitmap_reset(TestHBitmapData *data,
static void test_hbitmap_reset_all(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_init(data, L3 * 2, 0);
+ hbitmap_test_init(data, L3 * 2);
hbitmap_test_set(data, L1 - 1, L1 + 2);
hbitmap_test_reset_all(data);
hbitmap_test_set(data, 0, L1 * 3);
@@ -399,52 +390,6 @@ static void test_hbitmap_reset_all(TestHBitmapData *data,
hbitmap_test_reset_all(data);
}
-static void test_hbitmap_granularity(TestHBitmapData *data,
- const void *unused)
-{
- /* Note that hbitmap_test_check has to be invoked manually in this test. */
- hbitmap_test_init(data, L1, 1);
- hbitmap_test_set(data, 0, 1);
- g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
- hbitmap_test_check(data, 0);
- hbitmap_test_set(data, 2, 1);
- g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
- hbitmap_test_check(data, 0);
- hbitmap_test_set(data, 0, 3);
- g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
- hbitmap_test_reset(data, 0, 1);
- g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
-}
-
-static void test_hbitmap_iter_granularity(TestHBitmapData *data,
- const void *unused)
-{
- HBitmapIter hbi;
-
- /* Note that hbitmap_test_check has to be invoked manually in this test. */
- hbitmap_test_init(data, 131072 << 7, 7);
- hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
-
- hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
- hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
-
- hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
-
- hbitmap_test_set(data, (131072 << 7) - 8, 8);
- hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
-
- hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
-}
-
static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
{
size_t size = data->size;
@@ -460,40 +405,21 @@ static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
}
/* Last bit */
hbitmap_test_set(data, size - 1, 1);
- if (data->granularity == 0) {
- hbitmap_test_check_get(data);
- }
+ hbitmap_test_check_get(data);
}
static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
{
- size_t size = MIN(data->size, data->old_size);
-
- if (data->granularity == 0) {
- hbitmap_test_check_get(data);
- hbitmap_test_check(data, 0);
- } else {
- /* If a granularity was set, note that every distinct
- * (bit >> granularity) value that was set will increase
- * the bit pop count by 2^granularity, not just 1.
- *
- * The hbitmap_test_check facility does not currently tolerate
- * non-zero granularities, so test the boundaries and the population
- * count manually.
- */
- g_assert(hbitmap_get(data->hb, 0));
- g_assert(hbitmap_get(data->hb, size - 1));
- g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
- }
+ hbitmap_test_check_get(data);
+ hbitmap_test_check(data, 0);
}
/* Generic truncate test. */
static void hbitmap_test_truncate(TestHBitmapData *data,
size_t size,
- ssize_t diff,
- int granularity)
+ ssize_t diff)
{
- hbitmap_test_init(data, size, granularity);
+ hbitmap_test_init(data, size);
hbitmap_test_set_boundary_bits(data, diff);
hbitmap_test_truncate_impl(data, size + diff);
hbitmap_test_check_boundary_bits(data);
@@ -502,63 +428,7 @@ static void hbitmap_test_truncate(TestHBitmapData *data,
static void test_hbitmap_truncate_nop(TestHBitmapData *data,
const void *unused)
{
- hbitmap_test_truncate(data, L2, 0, 0);
-}
-
-/**
- * Grow by an amount smaller than the granularity, without crossing
- * a granularity alignment boundary. Effectively a NOP.
- */
-static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
- const void *unused)
-{
- size_t size = L2 - 1;
- size_t diff = 1;
- int granularity = 1;
-
- hbitmap_test_truncate(data, size, diff, granularity);
-}
-
-/**
- * Shrink by an amount smaller than the granularity, without crossing
- * a granularity alignment boundary. Effectively a NOP.
- */
-static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
- const void *unused)
-{
- size_t size = L2;
- ssize_t diff = -1;
- int granularity = 1;
-
- hbitmap_test_truncate(data, size, diff, granularity);
-}
-
-/**
- * Grow by an amount smaller than the granularity, but crossing over
- * a granularity alignment boundary.
- */
-static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
- const void *unused)
-{
- size_t size = L2 - 2;
- ssize_t diff = 1;
- int granularity = 1;
-
- hbitmap_test_truncate(data, size, diff, granularity);
-}
-
-/**
- * Shrink by an amount smaller than the granularity, but crossing over
- * a granularity alignment boundary.
- */
-static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
- const void *unused)
-{
- size_t size = L2 - 1;
- ssize_t diff = -1;
- int granularity = 1;
-
- hbitmap_test_truncate(data, size, diff, granularity);
+ hbitmap_test_truncate(data, L2, 0);
}
/**
@@ -571,7 +441,7 @@ static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
size_t size = L2 + 1;
size_t diff = sizeof(long) / 2;
- hbitmap_test_truncate(data, size, diff, 0);
+ hbitmap_test_truncate(data, size, diff);
}
/**
@@ -584,7 +454,7 @@ static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
size_t size = L2;
size_t diff = sizeof(long) / 2;
- hbitmap_test_truncate(data, size, -diff, 0);
+ hbitmap_test_truncate(data, size, -diff);
}
/**
@@ -597,7 +467,7 @@ static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
size_t size = L2 - 1;
size_t diff = sizeof(long) / 2;
- hbitmap_test_truncate(data, size, diff, 0);
+ hbitmap_test_truncate(data, size, diff);
}
/**
@@ -610,7 +480,7 @@ static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
size_t size = L2 + 1;
size_t diff = sizeof(long) / 2;
- hbitmap_test_truncate(data, size, -diff, 0);
+ hbitmap_test_truncate(data, size, -diff);
}
/**
@@ -622,7 +492,7 @@ static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
size_t size = L2;
size_t diff = 8 * sizeof(long);
- hbitmap_test_truncate(data, size, diff, 0);
+ hbitmap_test_truncate(data, size, diff);
}
/**
@@ -634,7 +504,7 @@ static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
size_t size = L2;
size_t diff = 8 * sizeof(long);
- hbitmap_test_truncate(data, size, -diff, 0);
+ hbitmap_test_truncate(data, size, -diff);
}
static void hbitmap_test_add(const char *testpath,
@@ -651,7 +521,6 @@ int main(int argc, char **argv)
hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
- hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
@@ -663,17 +532,8 @@ int main(int argc, char **argv)
hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
- hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
- hbitmap_test_add("/hbitmap/truncate/grow/negligible",
- test_hbitmap_truncate_grow_negligible);
- hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
- test_hbitmap_truncate_shrink_negligible);
- hbitmap_test_add("/hbitmap/truncate/grow/tiny",
- test_hbitmap_truncate_grow_tiny);
- hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
- test_hbitmap_truncate_shrink_tiny);
hbitmap_test_add("/hbitmap/truncate/grow/small",
test_hbitmap_truncate_grow_small);
hbitmap_test_add("/hbitmap/truncate/shrink/small",
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 50b888f..31df7c0 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -61,26 +61,6 @@ struct HBitmap {
/* Number of set bits in the bottom level. */
uint64_t count;
- /* A scaling factor. Given a granularity of G, each bit in the bitmap will
- * will actually represent a group of 2^G elements. Each operation on a
- * range of bits first rounds the bits to determine which group they land
- * in, and then affect the entire page; iteration will only visit the first
- * bit of each group. Here is an example of operations in a size-16,
- * granularity-1 HBitmap:
- *
- * initial state 00000000
- * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
- * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
- * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
- * reset(start=5, count=5) 00000000
- *
- * From an implementation point of view, when setting or resetting bits,
- * the bitmap will scale bit numbers right by this amount of bits. When
- * iterating, the bitmap will scale bit numbers left by this amount of
- * bits.
- */
- int granularity;
-
/* A number of progressively less coarse bitmaps (i.e. level 0 is the
* coarsest). Each bit in level N represents a word in level N+1 that
* has a set bit, except the last level where each bit represents the
@@ -145,10 +125,9 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
uint64_t pos;
hbi->hb = hb;
- pos = first >> hb->granularity;
+ pos = first;
assert(pos < hb->size);
hbi->pos = pos >> BITS_PER_LEVEL;
- hbi->granularity = hb->granularity;
for (i = HBITMAP_LEVELS; i-- > 0; ) {
bit = pos & (BITS_PER_LONG - 1);
@@ -171,18 +150,13 @@ bool hbitmap_empty(const HBitmap *hb)
return hb->count == 0;
}
-int hbitmap_granularity(const HBitmap *hb)
-{
- return hb->granularity;
-}
-
uint64_t hbitmap_count(const HBitmap *hb)
{
- return hb->count << hb->granularity;
+ return hb->count;
}
-/* Count the number of set bits between start and end, not accounting for
- * the granularity. Also an example of how to use hbitmap_iter_next_word.
+/* Count the number of set bits between start and end.
+ * Also an example of how to use hbitmap_iter_next_word.
*/
static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
{
@@ -192,7 +166,7 @@ static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
unsigned long cur;
size_t pos;
- hbitmap_iter_init(&hbi, hb, start << hb->granularity);
+ hbitmap_iter_init(&hbi, hb, start);
for (;;) {
pos = hbitmap_iter_next_word(&hbi, &cur);
if (pos >= (end >> BITS_PER_LEVEL)) {
@@ -266,11 +240,8 @@ void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
/* Compute range in the last layer. */
uint64_t last = start + count - 1;
- trace_hbitmap_set(hb, start, count,
- start >> hb->granularity, last >> hb->granularity);
+ trace_hbitmap_set(hb, start, count, start, last);
- start >>= hb->granularity;
- last >>= hb->granularity;
count = last - start + 1;
hb->count += count - hb_count_between(hb, start, last);
@@ -346,11 +317,7 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
/* Compute range in the last layer. */
uint64_t last = start + count - 1;
- trace_hbitmap_reset(hb, start, count,
- start >> hb->granularity, last >> hb->granularity);
-
- start >>= hb->granularity;
- last >>= hb->granularity;
+ trace_hbitmap_reset(hb, start, count, start, last);
hb->count -= hb_count_between(hb, start, last);
hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
@@ -372,7 +339,7 @@ void hbitmap_reset_all(HBitmap *hb)
bool hbitmap_get(const HBitmap *hb, uint64_t item)
{
/* Compute position and bit in the last layer. */
- uint64_t pos = item >> hb->granularity;
+ uint64_t pos = item;
unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
@@ -387,17 +354,14 @@ void hbitmap_free(HBitmap *hb)
g_free(hb);
}
-HBitmap *hbitmap_alloc(uint64_t size, int granularity)
+HBitmap *hbitmap_alloc(uint64_t size)
{
HBitmap *hb = g_new0(struct HBitmap, 1);
unsigned i;
- assert(granularity >= 0 && granularity < 64);
- size = (size + (1ULL << granularity) - 1) >> granularity;
assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
hb->size = size;
- hb->granularity = granularity;
for (i = HBITMAP_LEVELS; i-- > 0; ) {
size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
hb->sizes[i] = size;
@@ -420,8 +384,6 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
uint64_t num_elements = size;
uint64_t old;
- /* Size comes in as logical elements, adjust for granularity. */
- size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
shrink = size < hb->size;
@@ -435,10 +397,8 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
* us from carrying around garbage bits beyond the end of the map.
*/
if (shrink) {
- /* Don't clear partial granularity groups;
- * start at the first full one. */
- uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
- uint64_t fix_count = (hb->size << hb->granularity) - start;
+ uint64_t start = num_elements;
+ uint64_t fix_count = hb->size - start;
assert(fix_count);
hbitmap_reset(hb, start, fix_count);
@@ -473,7 +433,7 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
int i;
uint64_t j;
- if ((a->size != b->size) || (a->granularity != b->granularity)) {
+ if (a->size != b->size) {
return false;
}
--
2.4.3
^ permalink raw reply related [flat|nested] 4+ messages in thread