[Qemu-devel] [PATCH for 2.6 0/3] Bitmap clean-up patches for 2.6

[Qemu-devel] [PATCH for 2.6 0/3] Bitmap clean-up patches for 2.6

[Fam Zheng]

This makes a cleaner base for more dirty bitmap work. "granularity" appearing
with different representations have always been mind twisting, remove it from
HBitmap to make the interface and implementation simpler. Upon this, it is
a bit easier to add persistent dirty bitmap functionalities.

Block dirty bitmap is not unit-tested, so the removal of HBitmap test code
looks like a loss, but the overall test coverage is barely affected as we also
have various mirror, commit and backup iotest cases, and they do catch various
bugs when I wrote the patches.

Please review!

Fam

Fam Zheng (3):
  backup: Use Bitmap to replace "s->bitmap"
  block: Hide HBitmap in block dirty bitmap interface
  hbitmap: Drop "granularity"

 block.c                |  79 ++++++++++++++-----
 block/backup.c         |  25 +++---
 block/mirror.c         |  14 ++--
 include/block/block.h  |   9 ++-
 include/qemu/hbitmap.h |  20 +----
 tests/test-hbitmap.c   | 206 ++++++++-----------------------------------------
 util/hbitmap.c         |  64 +++------------
 7 files changed, 135 insertions(+), 282 deletions(-)

-- 
2.4.3

[Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Fam Zheng]

"s->bitmap" tracks done sectors, we only check bit states without using any
iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
more memory efficient.

Meanwhile, rename it to done_bitmap, to reflect the intention.

Signed-off-by: Fam Zheng <famz@redhat.com>
---
 block/backup.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/block/backup.c b/block/backup.c
index 3b39119..d408f98 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -22,6 +22,7 @@
 #include "qapi/qmp/qerror.h"
 #include "qemu/ratelimit.h"
 #include "sysemu/block-backend.h"
+#include "qemu/bitmap.h"
 
 #define BACKUP_CLUSTER_BITS 16
 #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
@@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
     BlockdevOnError on_target_error;
     CoRwlock flush_rwlock;
     uint64_t sectors_read;
-    HBitmap *bitmap;
+    unsigned long *done_bitmap;
     QLIST_HEAD(, CowRequest) inflight_reqs;
 } BackupBlockJob;
 
@@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
     cow_request_begin(&cow_request, job, start, end);
 
     for (; start < end; start++) {
-        if (hbitmap_get(job->bitmap, start)) {
+        if (test_bit(start, job->done_bitmap)) {
             trace_backup_do_cow_skip(job, start);
             continue; /* already copied */
         }
@@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
             goto out;
         }
 
-        hbitmap_set(job->bitmap, start, 1);
+        bitmap_set(job->done_bitmap, start, 1);
 
         /* Publish progress, guest I/O counts as progress too.  Note that the
          * offset field is an opaque progress value, it is not a disk offset.
@@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
     start = 0;
     end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
 
-    job->bitmap = hbitmap_alloc(end, 0);
+    job->done_bitmap = bitmap_new(end);
 
     bdrv_set_enable_write_cache(target, true);
     if (target->blk) {
@@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
     /* wait until pending backup_do_cow() calls have completed */
     qemu_co_rwlock_wrlock(&job->flush_rwlock);
     qemu_co_rwlock_unlock(&job->flush_rwlock);
-    hbitmap_free(job->bitmap);
+    g_free(job->done_bitmap);
 
     if (target->blk) {
         blk_iostatus_disable(target->blk);
-- 
2.4.3

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Vladimir Sementsov-Ogievskiy]

On 20.11.2015 12:59, Fam Zheng wrote:
> "s->bitmap" tracks done sectors, we only check bit states without using any
> iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
> more memory efficient.
>
> Meanwhile, rename it to done_bitmap, to reflect the intention.
>
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>   block/backup.c | 11 ++++++-----
>   1 file changed, 6 insertions(+), 5 deletions(-)
>
> diff --git a/block/backup.c b/block/backup.c
> index 3b39119..d408f98 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -22,6 +22,7 @@
>   #include "qapi/qmp/qerror.h"
>   #include "qemu/ratelimit.h"
>   #include "sysemu/block-backend.h"
> +#include "qemu/bitmap.h"
>   
>   #define BACKUP_CLUSTER_BITS 16
>   #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
> @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
>       BlockdevOnError on_target_error;
>       CoRwlock flush_rwlock;
>       uint64_t sectors_read;
> -    HBitmap *bitmap;
> +    unsigned long *done_bitmap;
>       QLIST_HEAD(, CowRequest) inflight_reqs;
>   } BackupBlockJob;
>   
> @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>       cow_request_begin(&cow_request, job, start, end);
>   
>       for (; start < end; start++) {
> -        if (hbitmap_get(job->bitmap, start)) {
> +        if (test_bit(start, job->done_bitmap)) {
>               trace_backup_do_cow_skip(job, start);
>               continue; /* already copied */
>           }
> @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>               goto out;
>           }
>   
> -        hbitmap_set(job->bitmap, start, 1);
> +        bitmap_set(job->done_bitmap, start, 1);
>   
>           /* Publish progress, guest I/O counts as progress too.  Note that the
>            * offset field is an opaque progress value, it is not a disk offset.
> @@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
>       start = 0;
>       end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
>   
> -    job->bitmap = hbitmap_alloc(end, 0);
> +    job->done_bitmap = bitmap_new(end);
>   
>       bdrv_set_enable_write_cache(target, true);
>       if (target->blk) {
> @@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
>       /* wait until pending backup_do_cow() calls have completed */
>       qemu_co_rwlock_wrlock(&job->flush_rwlock);
>       qemu_co_rwlock_unlock(&job->flush_rwlock);
> -    hbitmap_free(job->bitmap);
> +    g_free(job->done_bitmap);
>   
>       if (target->blk) {
>           blk_iostatus_disable(target->blk);

Isn't it better to use hbitmap iterators here to speed up bitmap handling?

trace_backup_do_cow_skip actually do nothing, so

     for (; start < end; start++) {
         if (hbitmap_get(job->bitmap, start)) {
             trace_backup_do_cow_skip(job, start);
             continue; /* already copied */
         }

may efficiently changed by something like:

    hbitmap_iter_init(hbi, start);
    while ((start = hbitmap_iter_next(hbi)) != -1) {


!! in this case bitmap usage should be reverted, as hbitmap_iter_next 
will skip 0 bits, not 1 ones.

-- 
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Fam Zheng]

On Fri, 11/20 18:53, Vladimir Sementsov-Ogievskiy wrote:
> On 20.11.2015 12:59, Fam Zheng wrote:
> >"s->bitmap" tracks done sectors, we only check bit states without using any
> >iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
> >more memory efficient.
> >
> >Meanwhile, rename it to done_bitmap, to reflect the intention.
> >
> >Signed-off-by: Fam Zheng <famz@redhat.com>
> >---
> >  block/backup.c | 11 ++++++-----
> >  1 file changed, 6 insertions(+), 5 deletions(-)
> >
> >diff --git a/block/backup.c b/block/backup.c
> >index 3b39119..d408f98 100644
> >--- a/block/backup.c
> >+++ b/block/backup.c
> >@@ -22,6 +22,7 @@
> >  #include "qapi/qmp/qerror.h"
> >  #include "qemu/ratelimit.h"
> >  #include "sysemu/block-backend.h"
> >+#include "qemu/bitmap.h"
> >  #define BACKUP_CLUSTER_BITS 16
> >  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
> >@@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
> >      BlockdevOnError on_target_error;
> >      CoRwlock flush_rwlock;
> >      uint64_t sectors_read;
> >-    HBitmap *bitmap;
> >+    unsigned long *done_bitmap;
> >      QLIST_HEAD(, CowRequest) inflight_reqs;
> >  } BackupBlockJob;
> >@@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> >      cow_request_begin(&cow_request, job, start, end);
> >      for (; start < end; start++) {
> >-        if (hbitmap_get(job->bitmap, start)) {
> >+        if (test_bit(start, job->done_bitmap)) {
> >              trace_backup_do_cow_skip(job, start);
> >              continue; /* already copied */
> >          }
> >@@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> >              goto out;
> >          }
> >-        hbitmap_set(job->bitmap, start, 1);
> >+        bitmap_set(job->done_bitmap, start, 1);
> >          /* Publish progress, guest I/O counts as progress too.  Note that the
> >           * offset field is an opaque progress value, it is not a disk offset.
> >@@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
> >      start = 0;
> >      end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
> >-    job->bitmap = hbitmap_alloc(end, 0);
> >+    job->done_bitmap = bitmap_new(end);
> >      bdrv_set_enable_write_cache(target, true);
> >      if (target->blk) {
> >@@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
> >      /* wait until pending backup_do_cow() calls have completed */
> >      qemu_co_rwlock_wrlock(&job->flush_rwlock);
> >      qemu_co_rwlock_unlock(&job->flush_rwlock);
> >-    hbitmap_free(job->bitmap);
> >+    g_free(job->done_bitmap);
> >      if (target->blk) {
> >          blk_iostatus_disable(target->blk);
> 
> Isn't it better to use hbitmap iterators here to speed up bitmap handling?
> 
> trace_backup_do_cow_skip actually do nothing, so
> 
>     for (; start < end; start++) {
>         if (hbitmap_get(job->bitmap, start)) {
>             trace_backup_do_cow_skip(job, start);
>             continue; /* already copied */
>         }
> 
> may efficiently changed by something like:
> 
>    hbitmap_iter_init(hbi, start);
>    while ((start = hbitmap_iter_next(hbi)) != -1) {
> 
> 
> !! in this case bitmap usage should be reverted, as
> hbitmap_iter_next will skip 0 bits, not 1 ones.
> 

This is not really necessary because backup iterates sequentially and only goes
for at most one pass. The bitmap is used for write interception.

Fam

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Wen Congyang]

On 11/20/2015 05:59 PM, Fam Zheng wrote:
> "s->bitmap" tracks done sectors, we only check bit states without using any
> iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
> more memory efficient.
> 
> Meanwhile, rename it to done_bitmap, to reflect the intention.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/backup.c | 11 ++++++-----
>  1 file changed, 6 insertions(+), 5 deletions(-)
> 
> diff --git a/block/backup.c b/block/backup.c
> index 3b39119..d408f98 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -22,6 +22,7 @@
>  #include "qapi/qmp/qerror.h"
>  #include "qemu/ratelimit.h"
>  #include "sysemu/block-backend.h"
> +#include "qemu/bitmap.h"
>  
>  #define BACKUP_CLUSTER_BITS 16
>  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
> @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
>      BlockdevOnError on_target_error;
>      CoRwlock flush_rwlock;
>      uint64_t sectors_read;
> -    HBitmap *bitmap;
> +    unsigned long *done_bitmap;
>      QLIST_HEAD(, CowRequest) inflight_reqs;
>  } BackupBlockJob;
>  
> @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>      cow_request_begin(&cow_request, job, start, end);
>  
>      for (; start < end; start++) {
> -        if (hbitmap_get(job->bitmap, start)) {
> +        if (test_bit(start, job->done_bitmap)) {
>              trace_backup_do_cow_skip(job, start);
>              continue; /* already copied */
>          }
> @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>              goto out;
>          }
>  
> -        hbitmap_set(job->bitmap, start, 1);
> +        bitmap_set(job->done_bitmap, start, 1);

You can use set_bit() here.

Thanks
Wen Congyang

>  
>          /* Publish progress, guest I/O counts as progress too.  Note that the
>           * offset field is an opaque progress value, it is not a disk offset.
> @@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
>      start = 0;
>      end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
>  
> -    job->bitmap = hbitmap_alloc(end, 0);
> +    job->done_bitmap = bitmap_new(end);
>  
>      bdrv_set_enable_write_cache(target, true);
>      if (target->blk) {
> @@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
>      /* wait until pending backup_do_cow() calls have completed */
>      qemu_co_rwlock_wrlock(&job->flush_rwlock);
>      qemu_co_rwlock_unlock(&job->flush_rwlock);
> -    hbitmap_free(job->bitmap);
> +    g_free(job->done_bitmap);
>  
>      if (target->blk) {
>          blk_iostatus_disable(target->blk);
> 

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Fam Zheng]

On Mon, 11/23 17:01, Wen Congyang wrote:
> On 11/20/2015 05:59 PM, Fam Zheng wrote:
> > "s->bitmap" tracks done sectors, we only check bit states without using any
> > iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
> > more memory efficient.
> > 
> > Meanwhile, rename it to done_bitmap, to reflect the intention.
> > 
> > Signed-off-by: Fam Zheng <famz@redhat.com>
> > ---
> >  block/backup.c | 11 ++++++-----
> >  1 file changed, 6 insertions(+), 5 deletions(-)
> > 
> > diff --git a/block/backup.c b/block/backup.c
> > index 3b39119..d408f98 100644
> > --- a/block/backup.c
> > +++ b/block/backup.c
> > @@ -22,6 +22,7 @@
> >  #include "qapi/qmp/qerror.h"
> >  #include "qemu/ratelimit.h"
> >  #include "sysemu/block-backend.h"
> > +#include "qemu/bitmap.h"
> >  
> >  #define BACKUP_CLUSTER_BITS 16
> >  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
> > @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
> >      BlockdevOnError on_target_error;
> >      CoRwlock flush_rwlock;
> >      uint64_t sectors_read;
> > -    HBitmap *bitmap;
> > +    unsigned long *done_bitmap;
> >      QLIST_HEAD(, CowRequest) inflight_reqs;
> >  } BackupBlockJob;
> >  
> > @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> >      cow_request_begin(&cow_request, job, start, end);
> >  
> >      for (; start < end; start++) {
> > -        if (hbitmap_get(job->bitmap, start)) {
> > +        if (test_bit(start, job->done_bitmap)) {
> >              trace_backup_do_cow_skip(job, start);
> >              continue; /* already copied */
> >          }
> > @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> >              goto out;
> >          }
> >  
> > -        hbitmap_set(job->bitmap, start, 1);
> > +        bitmap_set(job->done_bitmap, start, 1);
> 
> You can use set_bit() here.

Why? I think bitmap_set is a better match with bitmap_new below.

Fam

> 
> Thanks
> Wen Congyang
> 
> >  
> >          /* Publish progress, guest I/O counts as progress too.  Note that the
> >           * offset field is an opaque progress value, it is not a disk offset.
> > @@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
> >      start = 0;
> >      end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
> >  
> > -    job->bitmap = hbitmap_alloc(end, 0);
> > +    job->done_bitmap = bitmap_new(end);
> >  
> >      bdrv_set_enable_write_cache(target, true);
> >      if (target->blk) {
> > @@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
> >      /* wait until pending backup_do_cow() calls have completed */
> >      qemu_co_rwlock_wrlock(&job->flush_rwlock);
> >      qemu_co_rwlock_unlock(&job->flush_rwlock);
> > -    hbitmap_free(job->bitmap);
> > +    g_free(job->done_bitmap);
> >  
> >      if (target->blk) {
> >          blk_iostatus_disable(target->blk);
> > 
> 

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Wen Congyang]

On 11/23/2015 05:19 PM, Fam Zheng wrote:
> On Mon, 11/23 17:01, Wen Congyang wrote:
>> On 11/20/2015 05:59 PM, Fam Zheng wrote:
>>> "s->bitmap" tracks done sectors, we only check bit states without using any
>>> iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
>>> more memory efficient.
>>>
>>> Meanwhile, rename it to done_bitmap, to reflect the intention.
>>>
>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>> ---
>>>  block/backup.c | 11 ++++++-----
>>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>>
>>> diff --git a/block/backup.c b/block/backup.c
>>> index 3b39119..d408f98 100644
>>> --- a/block/backup.c
>>> +++ b/block/backup.c
>>> @@ -22,6 +22,7 @@
>>>  #include "qapi/qmp/qerror.h"
>>>  #include "qemu/ratelimit.h"
>>>  #include "sysemu/block-backend.h"
>>> +#include "qemu/bitmap.h"
>>>  
>>>  #define BACKUP_CLUSTER_BITS 16
>>>  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
>>> @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
>>>      BlockdevOnError on_target_error;
>>>      CoRwlock flush_rwlock;
>>>      uint64_t sectors_read;
>>> -    HBitmap *bitmap;
>>> +    unsigned long *done_bitmap;
>>>      QLIST_HEAD(, CowRequest) inflight_reqs;
>>>  } BackupBlockJob;
>>>  
>>> @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>>>      cow_request_begin(&cow_request, job, start, end);
>>>  
>>>      for (; start < end; start++) {
>>> -        if (hbitmap_get(job->bitmap, start)) {
>>> +        if (test_bit(start, job->done_bitmap)) {
>>>              trace_backup_do_cow_skip(job, start);
>>>              continue; /* already copied */
>>>          }
>>> @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>>>              goto out;
>>>          }
>>>  
>>> -        hbitmap_set(job->bitmap, start, 1);
>>> +        bitmap_set(job->done_bitmap, start, 1);
>>
>> You can use set_bit() here.
> 
> Why? I think bitmap_set is a better match with bitmap_new below.

set_bit() is quicker than bitmap_set() if you only set one bit.

Thanks
Wen Congyang

> 
> Fam
> 
>>
>> Thanks
>> Wen Congyang
>>
>>>  
>>>          /* Publish progress, guest I/O counts as progress too.  Note that the
>>>           * offset field is an opaque progress value, it is not a disk offset.
>>> @@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
>>>      start = 0;
>>>      end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
>>>  
>>> -    job->bitmap = hbitmap_alloc(end, 0);
>>> +    job->done_bitmap = bitmap_new(end);
>>>  
>>>      bdrv_set_enable_write_cache(target, true);
>>>      if (target->blk) {
>>> @@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
>>>      /* wait until pending backup_do_cow() calls have completed */
>>>      qemu_co_rwlock_wrlock(&job->flush_rwlock);
>>>      qemu_co_rwlock_unlock(&job->flush_rwlock);
>>> -    hbitmap_free(job->bitmap);
>>> +    g_free(job->done_bitmap);
>>>  
>>>      if (target->blk) {
>>>          blk_iostatus_disable(target->blk);
>>>
>>
> .
> 

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Fam Zheng]

On Mon, 11/23 17:24, Wen Congyang wrote:
> On 11/23/2015 05:19 PM, Fam Zheng wrote:
> > On Mon, 11/23 17:01, Wen Congyang wrote:
> >> On 11/20/2015 05:59 PM, Fam Zheng wrote:
> >>> "s->bitmap" tracks done sectors, we only check bit states without using any
> >>> iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
> >>> more memory efficient.
> >>>
> >>> Meanwhile, rename it to done_bitmap, to reflect the intention.
> >>>
> >>> Signed-off-by: Fam Zheng <famz@redhat.com>
> >>> ---
> >>>  block/backup.c | 11 ++++++-----
> >>>  1 file changed, 6 insertions(+), 5 deletions(-)
> >>>
> >>> diff --git a/block/backup.c b/block/backup.c
> >>> index 3b39119..d408f98 100644
> >>> --- a/block/backup.c
> >>> +++ b/block/backup.c
> >>> @@ -22,6 +22,7 @@
> >>>  #include "qapi/qmp/qerror.h"
> >>>  #include "qemu/ratelimit.h"
> >>>  #include "sysemu/block-backend.h"
> >>> +#include "qemu/bitmap.h"
> >>>  
> >>>  #define BACKUP_CLUSTER_BITS 16
> >>>  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
> >>> @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
> >>>      BlockdevOnError on_target_error;
> >>>      CoRwlock flush_rwlock;
> >>>      uint64_t sectors_read;
> >>> -    HBitmap *bitmap;
> >>> +    unsigned long *done_bitmap;
> >>>      QLIST_HEAD(, CowRequest) inflight_reqs;
> >>>  } BackupBlockJob;
> >>>  
> >>> @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> >>>      cow_request_begin(&cow_request, job, start, end);
> >>>  
> >>>      for (; start < end; start++) {
> >>> -        if (hbitmap_get(job->bitmap, start)) {
> >>> +        if (test_bit(start, job->done_bitmap)) {
> >>>              trace_backup_do_cow_skip(job, start);
> >>>              continue; /* already copied */
> >>>          }
> >>> @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> >>>              goto out;
> >>>          }
> >>>  
> >>> -        hbitmap_set(job->bitmap, start, 1);
> >>> +        bitmap_set(job->done_bitmap, start, 1);
> >>
> >> You can use set_bit() here.
> > 
> > Why? I think bitmap_set is a better match with bitmap_new below.
> 
> set_bit() is quicker than bitmap_set() if you only set one bit.
> 

How much quicker is it? This doesn't sound convincing enough for me to lose the
readability.

Fam

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Wen Congyang]

On 11/23/2015 05:55 PM, Fam Zheng wrote:
> On Mon, 11/23 17:24, Wen Congyang wrote:
>> On 11/23/2015 05:19 PM, Fam Zheng wrote:
>>> On Mon, 11/23 17:01, Wen Congyang wrote:
>>>> On 11/20/2015 05:59 PM, Fam Zheng wrote:
>>>>> "s->bitmap" tracks done sectors, we only check bit states without using any
>>>>> iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
>>>>> more memory efficient.
>>>>>
>>>>> Meanwhile, rename it to done_bitmap, to reflect the intention.
>>>>>
>>>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>>>> ---
>>>>>  block/backup.c | 11 ++++++-----
>>>>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>>>>
>>>>> diff --git a/block/backup.c b/block/backup.c
>>>>> index 3b39119..d408f98 100644
>>>>> --- a/block/backup.c
>>>>> +++ b/block/backup.c
>>>>> @@ -22,6 +22,7 @@
>>>>>  #include "qapi/qmp/qerror.h"
>>>>>  #include "qemu/ratelimit.h"
>>>>>  #include "sysemu/block-backend.h"
>>>>> +#include "qemu/bitmap.h"
>>>>>  
>>>>>  #define BACKUP_CLUSTER_BITS 16
>>>>>  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
>>>>> @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
>>>>>      BlockdevOnError on_target_error;
>>>>>      CoRwlock flush_rwlock;
>>>>>      uint64_t sectors_read;
>>>>> -    HBitmap *bitmap;
>>>>> +    unsigned long *done_bitmap;
>>>>>      QLIST_HEAD(, CowRequest) inflight_reqs;
>>>>>  } BackupBlockJob;
>>>>>  
>>>>> @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>>>>>      cow_request_begin(&cow_request, job, start, end);
>>>>>  
>>>>>      for (; start < end; start++) {
>>>>> -        if (hbitmap_get(job->bitmap, start)) {
>>>>> +        if (test_bit(start, job->done_bitmap)) {
>>>>>              trace_backup_do_cow_skip(job, start);
>>>>>              continue; /* already copied */
>>>>>          }
>>>>> @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>>>>>              goto out;
>>>>>          }
>>>>>  
>>>>> -        hbitmap_set(job->bitmap, start, 1);
>>>>> +        bitmap_set(job->done_bitmap, start, 1);
>>>>
>>>> You can use set_bit() here.
>>>
>>> Why? I think bitmap_set is a better match with bitmap_new below.
>>
>> set_bit() is quicker than bitmap_set() if you only set one bit.
>>
> 
> How much quicker is it? This doesn't sound convincing enough for me to lose the
> readability.

I don't test it. It is just a suggestion.

Thanks
Wen Congyang

> 
> Fam
> .
> 

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[Paolo Bonzini]

On 23/11/2015 10:55, Fam Zheng wrote:
>>> Why? I think bitmap_set is a better match with bitmap_new below.
>>
>> set_bit() is quicker than bitmap_set() if you only set one bit.
> 
> How much quicker is it? This doesn't sound convincing enough for me to lose the
> readability.

Substantially.  It's also documented:

/*
 * Also the following operations apply to bitmaps.
 *
 * set_bit(bit, addr)                   *addr |= bit
 * clear_bit(bit, addr)                 *addr &= ~bit
 * change_bit(bit, addr)                *addr ^= bit
 * test_bit(bit, addr)                  Is bit set in *addr?
 * test_and_set_bit(bit, addr)          Set bit and return old value
 * test_and_clear_bit(bit, addr)        Clear bit and return old value
 * test_and_change_bit(bit, addr)       Change bit and return old value
 * find_first_zero_bit(addr, nbits)     Position first zero bit in *addr
 * find_first_bit(addr, nbits)          Position first set bit in *addr
 * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
 * find_next_bit(addr, nbits, bit)      Position next set bit in *addr >= bit
 */

Paolo

Re: [Qemu-devel] [PATCH for 2.6 1/3] backup: Use Bitmap to replace "s->bitmap"

[John Snow]

On 11/20/2015 04:59 AM, Fam Zheng wrote:
> "s->bitmap" tracks done sectors, we only check bit states without using any
> iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
> more memory efficient.
> 
> Meanwhile, rename it to done_bitmap, to reflect the intention.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/backup.c | 11 ++++++-----
>  1 file changed, 6 insertions(+), 5 deletions(-)
> 
> diff --git a/block/backup.c b/block/backup.c
> index 3b39119..d408f98 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -22,6 +22,7 @@
>  #include "qapi/qmp/qerror.h"
>  #include "qemu/ratelimit.h"
>  #include "sysemu/block-backend.h"
> +#include "qemu/bitmap.h"
>  
>  #define BACKUP_CLUSTER_BITS 16
>  #define BACKUP_CLUSTER_SIZE (1 << BACKUP_CLUSTER_BITS)
> @@ -47,7 +48,7 @@ typedef struct BackupBlockJob {
>      BlockdevOnError on_target_error;
>      CoRwlock flush_rwlock;
>      uint64_t sectors_read;
> -    HBitmap *bitmap;
> +    unsigned long *done_bitmap;
>      QLIST_HEAD(, CowRequest) inflight_reqs;
>  } BackupBlockJob;
>  
> @@ -113,7 +114,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>      cow_request_begin(&cow_request, job, start, end);
>  
>      for (; start < end; start++) {
> -        if (hbitmap_get(job->bitmap, start)) {
> +        if (test_bit(start, job->done_bitmap)) {
>              trace_backup_do_cow_skip(job, start);
>              continue; /* already copied */
>          }
> @@ -164,7 +165,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
>              goto out;
>          }
>  
> -        hbitmap_set(job->bitmap, start, 1);
> +        bitmap_set(job->done_bitmap, start, 1);
>  
>          /* Publish progress, guest I/O counts as progress too.  Note that the
>           * offset field is an opaque progress value, it is not a disk offset.
> @@ -394,7 +395,7 @@ static void coroutine_fn backup_run(void *opaque)
>      start = 0;
>      end = DIV_ROUND_UP(job->common.len, BACKUP_CLUSTER_SIZE);
>  
> -    job->bitmap = hbitmap_alloc(end, 0);
> +    job->done_bitmap = bitmap_new(end);
>  
>      bdrv_set_enable_write_cache(target, true);
>      if (target->blk) {
> @@ -475,7 +476,7 @@ static void coroutine_fn backup_run(void *opaque)
>      /* wait until pending backup_do_cow() calls have completed */
>      qemu_co_rwlock_wrlock(&job->flush_rwlock);
>      qemu_co_rwlock_unlock(&job->flush_rwlock);
> -    hbitmap_free(job->bitmap);
> +    g_free(job->done_bitmap);
>  
>      if (target->blk) {
>          blk_iostatus_disable(target->blk);
> 

Replacing the bitmap_set with set_bit, in response to Paolo's comment:

Reviewed-by: John Snow <jsnow@redhat.com>

[Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[Fam Zheng]

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 d408f98..a3f60ff 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

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[Vladimir Sementsov-Ogievskiy]

On 20.11.2015 12:59, Fam Zheng wrote:
> 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 d408f98..a3f60ff 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);

IMO, granularity changes (which are not described in commit msg) should 
be moved to separate patch

-- 
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[Fam Zheng]

On Fri, 11/20 19:08, Vladimir Sementsov-Ogievskiy wrote:
> On 20.11.2015 12:59, Fam Zheng wrote:
> >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 d408f98..a3f60ff 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);
> 
> IMO, granularity changes (which are not described in commit msg)
> should be moved to separate patch

Which granularity changes do you mean? The interface and the callers have to be
changed in the same patch to keep bisectability.

Fam

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[John Snow]

On 11/20/2015 04:59 AM, Fam Zheng wrote:
> 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);

Hmm, what's the idea, here?

This patch does a lot more than just hide hbitmap details from callers
of block_dirty_bitmap functions.

So we're changing the backing hbitmap to always be one where g=0 and the
number of physical bits directly is (now) the same as the number of
'virtual' bits, pre-patch. Then, to compensate, we handle the shift math
to convert the bitmap granularity to sector size and vice-versa in the
Block Dirty Bitmap layer instead of in the hbitmap layer.

What's the benefit? It looks like we just pull all the implementation
details up from hbitmap and into BdrvDirtyBitmap, which I am not
immediately convinced of as being a benefit.

> +    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 d408f98..a3f60ff 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);
> 

-- 
—js

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[Fam Zheng]

On Mon, 11/23 16:34, John Snow wrote:
> Hmm, what's the idea, here?
> 
> This patch does a lot more than just hide hbitmap details from callers
> of block_dirty_bitmap functions.
> 
> So we're changing the backing hbitmap to always be one where g=0 and the
> number of physical bits directly is (now) the same as the number of
> 'virtual' bits, pre-patch. Then, to compensate, we handle the shift math
> to convert the bitmap granularity to sector size and vice-versa in the
> Block Dirty Bitmap layer instead of in the hbitmap layer.
> 
> What's the benefit? It looks like we just pull all the implementation
> details up from hbitmap and into BdrvDirtyBitmap, which I am not
> immediately convinced of as being a benefit.

It feels counter intuitive to me with hbitmap handling granularity, it makes it
more like a HGranularityBitmap rather than HBitmap, and is unnecessarily
complex to work on.

Now it's simplified in that only one BdrvDirtyBitmap needs to care about the
granularity, and which I think is a big benefit when we are going to extend the
dirty bitmap interface, for example to serialize and deserialize for
persistence.

Fam

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[Vladimir Sementsov-Ogievskiy]

On 24.11.2015 05:28, Fam Zheng wrote:
> On Mon, 11/23 16:34, John Snow wrote:
>> Hmm, what's the idea, here?
>>
>> This patch does a lot more than just hide hbitmap details from callers
>> of block_dirty_bitmap functions.
>>
>> So we're changing the backing hbitmap to always be one where g=0 and the
>> number of physical bits directly is (now) the same as the number of
>> 'virtual' bits, pre-patch. Then, to compensate, we handle the shift math
>> to convert the bitmap granularity to sector size and vice-versa in the
>> Block Dirty Bitmap layer instead of in the hbitmap layer.
>>
>> What's the benefit? It looks like we just pull all the implementation
>> details up from hbitmap and into BdrvDirtyBitmap, which I am not
>> immediately convinced of as being a benefit.
> It feels counter intuitive to me with hbitmap handling granularity, it makes it
> more like a HGranularityBitmap rather than HBitmap, and is unnecessarily
> complex to work on.
>
> Now it's simplified in that only one BdrvDirtyBitmap needs to care about the
> granularity, and which I think is a big benefit when we are going to extend the
> dirty bitmap interface, for example to serialize and deserialize for
> persistence.
>
> Fam

But what is the relation from this to adding iterator interface? This 
seems like this patch do two different things:
1) granularity changes, described in quotation above
2) adding iterator related things, described in commit message

-- 
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[Fam Zheng]

On Tue, 11/24 12:12, Vladimir Sementsov-Ogievskiy wrote:
> On 24.11.2015 05:28, Fam Zheng wrote:
> >On Mon, 11/23 16:34, John Snow wrote:
> >>Hmm, what's the idea, here?
> >>
> >>This patch does a lot more than just hide hbitmap details from callers
> >>of block_dirty_bitmap functions.
> >>
> >>So we're changing the backing hbitmap to always be one where g=0 and the
> >>number of physical bits directly is (now) the same as the number of
> >>'virtual' bits, pre-patch. Then, to compensate, we handle the shift math
> >>to convert the bitmap granularity to sector size and vice-versa in the
> >>Block Dirty Bitmap layer instead of in the hbitmap layer.
> >>
> >>What's the benefit? It looks like we just pull all the implementation
> >>details up from hbitmap and into BdrvDirtyBitmap, which I am not
> >>immediately convinced of as being a benefit.
> >It feels counter intuitive to me with hbitmap handling granularity, it makes it
> >more like a HGranularityBitmap rather than HBitmap, and is unnecessarily
> >complex to work on.
> >
> >Now it's simplified in that only one BdrvDirtyBitmap needs to care about the
> >granularity, and which I think is a big benefit when we are going to extend the
> >dirty bitmap interface, for example to serialize and deserialize for
> >persistence.
> >
> >Fam
> 
> But what is the relation from this to adding iterator interface?
> This seems like this patch do two different things:
> 1) granularity changes, described in quotation above
> 2) adding iterator related things, described in commit message
> 

OK, let's try to split this so we still have the BdrvDirtyBitmapIter change
even if the granularity movement is rejected.

Fam

Re: [Qemu-devel] [PATCH for 2.6 2/3] block: Hide HBitmap in block dirty bitmap interface

[John Snow]

On 11/23/2015 09:28 PM, Fam Zheng wrote:
> On Mon, 11/23 16:34, John Snow wrote:
>> Hmm, what's the idea, here?
>>
>> This patch does a lot more than just hide hbitmap details from callers
>> of block_dirty_bitmap functions.
>>
>> So we're changing the backing hbitmap to always be one where g=0 and the
>> number of physical bits directly is (now) the same as the number of
>> 'virtual' bits, pre-patch. Then, to compensate, we handle the shift math
>> to convert the bitmap granularity to sector size and vice-versa in the
>> Block Dirty Bitmap layer instead of in the hbitmap layer.
>>
>> What's the benefit? It looks like we just pull all the implementation
>> details up from hbitmap and into BdrvDirtyBitmap, which I am not
>> immediately convinced of as being a benefit.
> 
> It feels counter intuitive to me with hbitmap handling granularity, it makes it
> more like a HGranularityBitmap rather than HBitmap, and is unnecessarily
> complex to work on.
> 

I guess it's a matter of personal taste on where to try to hide the
complexity. Since hbitmap can and already does manage it for us, inertia
leaves me satisfied with this option.

I don't know if pulling the granularity out of hbitmap and into
BdrvDirtyBitmap (so now we have granularity management code in two
objects) is a significant gain, but I wouldn't NACK this over that
specifically ... I'll let Vladimir et al decide if this does make e.g.
his migration/persistence patches easier to write or not.

I agree that the new iterator object for BdrvDirtyBitmap is good,
though, and wouldn't mind seeing this split up into its two parts:

(1) Hiding the hbitmap implementation detail entirely from users of
BdrvDirtyBitmap, by adding new BdrvDirtyBitmap iterators

(2) Moving the granularity logic up into BdrvDirtyBitmap

> Now it's simplified in that only one BdrvDirtyBitmap needs to care about the
> granularity, and which I think is a big benefit when we are going to extend the
> dirty bitmap interface, for example to serialize and deserialize for
> persistence.
> 
> Fam
> 

[Qemu-devel] [PATCH for 2.6 3/3] hbitmap: Drop "granularity"

[Fam Zheng]

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

Re: [Qemu-devel] [PATCH for 2.6 3/3] hbitmap: Drop "granularity"

[Vladimir Sementsov-Ogievskiy]

On 20.11.2015 12:59, Fam Zheng wrote:
> Sometimes confused with the granularity with coarse levels in HBitmap, the
> granularity in the hbitmap_alloc is not an essential concept of a bitmap.  Now
> that all callers except the test code use zero, it's possible to drop the
> parameter to make the interface cleaner and more intuitive.
>
> Test code of hbitmap granularity is removed together.
>
> Signed-off-by: Fam Zheng <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;
>       }
>   

Ok for me, one question:

Is it ok, that you are deleting some test cases, where granularity = 1? 
Shouldn't they be tuned to test bitmap with granularity = 0, or they 
just tests granularity itself?


-- 
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.

Re: [Qemu-devel] [PATCH for 2.6 3/3] hbitmap: Drop "granularity"

[Fam Zheng]

On Fri, 11/20 19:22, Vladimir Sementsov-Ogievskiy wrote:
> On 20.11.2015 12:59, Fam Zheng wrote:
> >Sometimes confused with the granularity with coarse levels in HBitmap, the
> >granularity in the hbitmap_alloc is not an essential concept of a bitmap.  Now
> >that all callers except the test code use zero, it's possible to drop the
> >parameter to make the interface cleaner and more intuitive.
> >
> >Test code of hbitmap granularity is removed together.
> >
> >Signed-off-by: Fam Zheng <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;
> >      }
> 
> Ok for me, one question:
> 
> Is it ok, that you are deleting some test cases, where granularity =
> 1? Shouldn't they be tuned to test bitmap with granularity = 0, or
> they just tests granularity itself?

"Granularity = 0" is the "1:1" case, while "granularity = 1" is the "1 bit for
2 items" scaling. So I deleted those and only left the "0" cases.

Fam

Re: [Qemu-devel] [PATCH for 2.6 0/3] Bitmap clean-up patches for 2.6

[Vladimir Sementsov-Ogievskiy]

Hi Fam!

Thanks for it, I really like the idea about dropping granularity from 
hbitmap. I've waste lots of time understanding the code about bitmaps. 
Keeping in mind what units are in what granularity and what granularity 
is in what units is more than inconvenient)

On 20.11.2015 12:59, Fam Zheng wrote:
> This makes a cleaner base for more dirty bitmap work. "granularity" appearing
> with different representations have always been mind twisting, remove it from
> HBitmap to make the interface and implementation simpler. Upon this, it is
> a bit easier to add persistent dirty bitmap functionalities.
>
> Block dirty bitmap is not unit-tested, so the removal of HBitmap test code
> looks like a loss, but the overall test coverage is barely affected as we also
> have various mirror, commit and backup iotest cases, and they do catch various
> bugs when I wrote the patches.
>
> Please review!
>
> Fam
>
> Fam Zheng (3):
>    backup: Use Bitmap to replace "s->bitmap"
>    block: Hide HBitmap in block dirty bitmap interface
>    hbitmap: Drop "granularity"
>
>   block.c                |  79 ++++++++++++++-----
>   block/backup.c         |  25 +++---
>   block/mirror.c         |  14 ++--
>   include/block/block.h  |   9 ++-
>   include/qemu/hbitmap.h |  20 +----
>   tests/test-hbitmap.c   | 206 ++++++++-----------------------------------------
>   util/hbitmap.c         |  64 +++------------
>   7 files changed, 135 insertions(+), 282 deletions(-)
>


-- 
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.