Add bytes parameter to the function, to limit searched range.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/block/dirty-bitmap.h |  3 ++-
 include/qemu/hbitmap.h       | 10 ++++++++--
 block/backup.c               |  2 +-
 block/dirty-bitmap.c         |  5 +++--
 nbd/server.c                 |  2 +-
 tests/test-hbitmap.c         |  2 +-
 util/hbitmap.c               | 25 ++++++++++++++++++++-----
 7 files changed, 36 insertions(+), 13 deletions(-)

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 259bd27c40..27f5299c4e 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
 BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
                                         BdrvDirtyBitmap *bitmap);
 char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
+                                    int64_t end);
 BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
                                                   BdrvDirtyBitmap *bitmap,
                                                   Error **errp);
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index ddca52c48e..fe4dfde27a 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 /* hbitmap_next_zero:
  * @hb: The HBitmap to operate on
  * @start: The bit to start from.
+ * @end: End of range to search in. If @end is -1, search up to the bitmap
+ *       end.
  *
- * Find next not dirty bit.
+ * Find next not dirty bit within range [@start, @end), or from
+ * @start to the bitmap end if @end is -1. If not found, return -1.
+ *
+ * @end may be greater than original bitmap size, in this case, search up to
+ * the bitmap end.
  */
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
 
 /* hbitmap_create_meta:
  * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
diff --git a/block/backup.c b/block/backup.c
index 8630d32926..9bfd3f7189 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
             break;
         }
 
-        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
+        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1);
         if (offset == -1) {
             hbitmap_set(job->copy_bitmap, cluster, end - cluster);
             break;
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index c9b8a6fd52..037ae62726 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
     return hbitmap_sha256(bitmap->bitmap, errp);
 }
 
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
+                                    int64_t end)
 {
-    return hbitmap_next_zero(bitmap->bitmap, offset);
+    return hbitmap_next_zero(bitmap->bitmap, offset, end);
 }
 
 void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
diff --git a/nbd/server.c b/nbd/server.c
index ea5fe0eb33..07920d123b 100644
--- a/nbd/server.c
+++ b/nbd/server.c
@@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
     assert(begin < overall_end && nb_extents);
     while (begin < overall_end && i < nb_extents) {
         if (dirty) {
-            end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
+            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1);
         } else {
             bdrv_set_dirty_iter(it, begin);
             end = bdrv_dirty_iter_next(it);
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 5e67ac1d3a..6b6a40bddd 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
 
 static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
 {
-    int64_t ret1 = hbitmap_next_zero(data->hb, start);
+    int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
     int64_t ret2 = start;
     for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
         ;
diff --git a/util/hbitmap.c b/util/hbitmap.c
index bcd304041a..1687372504 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -53,6 +53,9 @@
  */
 
 struct HBitmap {
+    /* Size of the bitmap, as requested in hbitmap_alloc. */
+    uint64_t orig_size;
+
     /* Number of total bits in the bottom level.  */
     uint64_t size;
 
@@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
     }
 }
 
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
 {
     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
     unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
-    uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
     unsigned long cur = last_lev[pos];
-    unsigned start_bit_offset =
-            (start >> hb->granularity) & (BITS_PER_LONG - 1);
+    unsigned start_bit_offset;
+    uint64_t end_bit, sz;
     int64_t res;
 
+    if (start >= hb->orig_size || (end != -1 && end <= start)) {
+        return -1;
+    }
+
+    end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1;
+    sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
+
+    /* There may be some zero bits in @cur before @start. We are not interested
+     * in them, let's set them.
+     */
+    start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
     cur |= (1UL << start_bit_offset) - 1;
     assert((start >> hb->granularity) < hb->size);
 
@@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
     }
 
     res = (pos << BITS_PER_LEVEL) + ctol(cur);
-    if (res >= hb->size) {
+    if (res >= end_bit) {
         return -1;
     }
 
@@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
     HBitmap *hb = g_new0(struct HBitmap, 1);
     unsigned i;
 
+    hb->orig_size = size;
+
     assert(granularity >= 0 && granularity < 64);
     size = (size + (1ULL << granularity) - 1) >> granularity;
     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
-- 
2.11.1

On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> Add bytes parameter to the function, to limit searched range.
> 

I'm going to assume that Eric Blake has been through here and commented
on the interface itself.

> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/block/dirty-bitmap.h |  3 ++-
>  include/qemu/hbitmap.h       | 10 ++++++++--
>  block/backup.c               |  2 +-
>  block/dirty-bitmap.c         |  5 +++--
>  nbd/server.c                 |  2 +-
>  tests/test-hbitmap.c         |  2 +-
>  util/hbitmap.c               | 25 ++++++++++++++++++++-----
>  7 files changed, 36 insertions(+), 13 deletions(-)
> 
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 259bd27c40..27f5299c4e 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>  BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>                                          BdrvDirtyBitmap *bitmap);
>  char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
> +                                    int64_t end);
>  BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
>                                                    BdrvDirtyBitmap *bitmap,
>                                                    Error **errp);
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index ddca52c48e..fe4dfde27a 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>  /* hbitmap_next_zero:
>   * @hb: The HBitmap to operate on
>   * @start: The bit to start from.
> + * @end: End of range to search in. If @end is -1, search up to the bitmap
> + *       end.
>   *
> - * Find next not dirty bit.
> + * Find next not dirty bit within range [@start, @end), or from
> + * @start to the bitmap end if @end is -1. If not found, return -1.
> + *
> + * @end may be greater than original bitmap size, in this case, search up to

"original" bitmap size? I think that's just an implementation detail, we
can drop 'original' here, yes?

> + * the bitmap end.
>   */
> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>  

The interface looks weird because we can define a 'start' that's beyond
the 'end'.

I realize that you need a signed integer for 'end' to signify EOF...
should we do a 'bytes' parameter instead? (Did you already do that in an
earlier version and we changed it?)

Well, it's not a big deal to me personally.

>  /* hbitmap_create_meta:
>   * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> diff --git a/block/backup.c b/block/backup.c
> index 8630d32926..9bfd3f7189 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
>              break;
>          }
>  
> -        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
> +        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1);
>          if (offset == -1) {
>              hbitmap_set(job->copy_bitmap, cluster, end - cluster);
>              break;
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index c9b8a6fd52..037ae62726 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
>      return hbitmap_sha256(bitmap->bitmap, errp);
>  }
>  
> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
> +                                    int64_t end)
>  {
> -    return hbitmap_next_zero(bitmap->bitmap, offset);
> +    return hbitmap_next_zero(bitmap->bitmap, offset, end);
>  }
>  
>  void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
> diff --git a/nbd/server.c b/nbd/server.c
> index ea5fe0eb33..07920d123b 100644
> --- a/nbd/server.c
> +++ b/nbd/server.c
> @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
>      assert(begin < overall_end && nb_extents);
>      while (begin < overall_end && i < nb_extents) {
>          if (dirty) {
> -            end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
> +            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1);
>          } else {
>              bdrv_set_dirty_iter(it, begin);
>              end = bdrv_dirty_iter_next(it);
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 5e67ac1d3a..6b6a40bddd 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>  
>  static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
>  {
> -    int64_t ret1 = hbitmap_next_zero(data->hb, start);
> +    int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
>      int64_t ret2 = start;
>      for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
>          ;
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index bcd304041a..1687372504 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -53,6 +53,9 @@
>   */
>  
>  struct HBitmap {
> +    /* Size of the bitmap, as requested in hbitmap_alloc. */
> +    uint64_t orig_size;
> +
>      /* Number of total bits in the bottom level.  */
>      uint64_t size;
>  
> @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>      }
>  }
>  
> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
>  {
>      size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
>      unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
> -    uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
>      unsigned long cur = last_lev[pos];
> -    unsigned start_bit_offset =
> -            (start >> hb->granularity) & (BITS_PER_LONG - 1);
> +    unsigned start_bit_offset;
> +    uint64_t end_bit, sz;
>      int64_t res;
>  
> +    if (start >= hb->orig_size || (end != -1 && end <= start)) {
> +        return -1;
> +    }
> +
> +    end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1;
> +    sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
> +
> +    /* There may be some zero bits in @cur before @start. We are not interested
> +     * in them, let's set them.
> +     */
> +    start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
>      cur |= (1UL << start_bit_offset) - 1;
>      assert((start >> hb->granularity) < hb->size);
>  
> @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
>      }
>  
>      res = (pos << BITS_PER_LEVEL) + ctol(cur);
> -    if (res >= hb->size) {
> +    if (res >= end_bit) {
>          return -1;
>      }
>  
> @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
>      HBitmap *hb = g_new0(struct HBitmap, 1);
>      unsigned i;
>  
> +    hb->orig_size = size;
> +
>      assert(granularity >= 0 && granularity < 64);
>      size = (size + (1ULL << granularity) - 1) >> granularity;
>      assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
> 

Despite my comments, I'm OK with or without changes.

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

08.09.2018 00:49, John Snow wrote:
>
> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
>> Add bytes parameter to the function, to limit searched range.
>>
> I'm going to assume that Eric Blake has been through here and commented
> on the interface itself.
>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/block/dirty-bitmap.h |  3 ++-
>>   include/qemu/hbitmap.h       | 10 ++++++++--
>>   block/backup.c               |  2 +-
>>   block/dirty-bitmap.c         |  5 +++--
>>   nbd/server.c                 |  2 +-
>>   tests/test-hbitmap.c         |  2 +-
>>   util/hbitmap.c               | 25 ++++++++++++++++++++-----
>>   7 files changed, 36 insertions(+), 13 deletions(-)
>>
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 259bd27c40..27f5299c4e 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>>   BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>>                                           BdrvDirtyBitmap *bitmap);
>>   char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
>> +                                    int64_t end);
>>   BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
>>                                                     BdrvDirtyBitmap *bitmap,
>>                                                     Error **errp);
>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>> index ddca52c48e..fe4dfde27a 100644
>> --- a/include/qemu/hbitmap.h
>> +++ b/include/qemu/hbitmap.h
>> @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>>   /* hbitmap_next_zero:
>>    * @hb: The HBitmap to operate on
>>    * @start: The bit to start from.
>> + * @end: End of range to search in. If @end is -1, search up to the bitmap
>> + *       end.
>>    *
>> - * Find next not dirty bit.
>> + * Find next not dirty bit within range [@start, @end), or from
>> + * @start to the bitmap end if @end is -1. If not found, return -1.
>> + *
>> + * @end may be greater than original bitmap size, in this case, search up to
> "original" bitmap size? I think that's just an implementation detail, we
> can drop 'original' here, yes?

hm, no. we have field "size", which is not "original". But it all means 
that this place needs a bit more refactoring.

>
>> + * the bitmap end.
>>    */
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>>   
> The interface looks weird because we can define a 'start' that's beyond
> the 'end'.
>
> I realize that you need a signed integer for 'end' to signify EOF...
> should we do a 'bytes' parameter instead? (Did you already do that in an
> earlier version and we changed it?)
>
> Well, it's not a big deal to me personally.

interface with constant end parameter is more comfortable for loop: we 
don't need to update 'bytes' parameter on each iteration

>
>>   /* hbitmap_create_meta:
>>    * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>> diff --git a/block/backup.c b/block/backup.c
>> index 8630d32926..9bfd3f7189 100644
>> --- a/block/backup.c
>> +++ b/block/backup.c
>> @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
>>               break;
>>           }
>>   
>> -        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
>> +        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1);
>>           if (offset == -1) {
>>               hbitmap_set(job->copy_bitmap, cluster, end - cluster);
>>               break;
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index c9b8a6fd52..037ae62726 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
>>       return hbitmap_sha256(bitmap->bitmap, errp);
>>   }
>>   
>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
>> +                                    int64_t end)
>>   {
>> -    return hbitmap_next_zero(bitmap->bitmap, offset);
>> +    return hbitmap_next_zero(bitmap->bitmap, offset, end);
>>   }
>>   
>>   void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
>> diff --git a/nbd/server.c b/nbd/server.c
>> index ea5fe0eb33..07920d123b 100644
>> --- a/nbd/server.c
>> +++ b/nbd/server.c
>> @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
>>       assert(begin < overall_end && nb_extents);
>>       while (begin < overall_end && i < nb_extents) {
>>           if (dirty) {
>> -            end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
>> +            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1);
>>           } else {
>>               bdrv_set_dirty_iter(it, begin);
>>               end = bdrv_dirty_iter_next(it);
>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>> index 5e67ac1d3a..6b6a40bddd 100644
>> --- a/tests/test-hbitmap.c
>> +++ b/tests/test-hbitmap.c
>> @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>>   
>>   static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
>>   {
>> -    int64_t ret1 = hbitmap_next_zero(data->hb, start);
>> +    int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
>>       int64_t ret2 = start;
>>       for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
>>           ;
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index bcd304041a..1687372504 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -53,6 +53,9 @@
>>    */
>>   
>>   struct HBitmap {
>> +    /* Size of the bitmap, as requested in hbitmap_alloc. */
>> +    uint64_t orig_size;
>> +
>>       /* Number of total bits in the bottom level.  */
>>       uint64_t size;
>>   
>> @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>>       }
>>   }
>>   
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
>>   {
>>       size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
>>       unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
>> -    uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
>>       unsigned long cur = last_lev[pos];
>> -    unsigned start_bit_offset =
>> -            (start >> hb->granularity) & (BITS_PER_LONG - 1);
>> +    unsigned start_bit_offset;
>> +    uint64_t end_bit, sz;
>>       int64_t res;
>>   
>> +    if (start >= hb->orig_size || (end != -1 && end <= start)) {
>> +        return -1;
>> +    }
>> +
>> +    end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1;
>> +    sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
>> +
>> +    /* There may be some zero bits in @cur before @start. We are not interested
>> +     * in them, let's set them.
>> +     */
>> +    start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
>>       cur |= (1UL << start_bit_offset) - 1;
>>       assert((start >> hb->granularity) < hb->size);
>>   
>> @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
>>       }
>>   
>>       res = (pos << BITS_PER_LEVEL) + ctol(cur);
>> -    if (res >= hb->size) {
>> +    if (res >= end_bit) {
>>           return -1;
>>       }
>>   
>> @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
>>       HBitmap *hb = g_new0(struct HBitmap, 1);
>>       unsigned i;
>>   
>> +    hb->orig_size = size;
>> +
>>       assert(granularity >= 0 && granularity < 64);
>>       size = (size + (1ULL << granularity) - 1) >> granularity;
>>       assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
>>
> Despite my comments, I'm OK with or without changes.
>
> Reviewed-by: John Snow <jsnow@redhat.com>


-- 
Best regards,
Vladimir

On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:

>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t 
>>> end);
>> The interface looks weird because we can define a 'start' that's beyond
>> the 'end'.
>>
>> I realize that you need a signed integer for 'end' to signify EOF...
>> should we do a 'bytes' parameter instead? (Did you already do that in an
>> earlier version and we changed it?)
>>
>> Well, it's not a big deal to me personally.
> 
> interface with constant end parameter is more comfortable for loop: we 
> don't need to update 'bytes' parameter on each iteration

But there's still the question of WHO should be calculating end. Your 
interface argues for the caller:

hbitmap_next_zero(start, start + bytes)

int64_t hbitmap_next_zero(...)
{
     while (offset != end) ...
}

while we're asking about a consistent interface for the caller (if most 
callers already have a 'bytes' rather than an 'end' computed):

hbitmap_next_zero(start, bytes)

int64_t hbitmap_next_zero(...)
{
     int64_t end = start + bytes;
     while (offset != end) ...
}

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

10.09.2018 19:55, Eric Blake wrote:
> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>
>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, 
>>>> int64_t end);
>>> The interface looks weird because we can define a 'start' that's beyond
>>> the 'end'.
>>>
>>> I realize that you need a signed integer for 'end' to signify EOF...
>>> should we do a 'bytes' parameter instead? (Did you already do that 
>>> in an
>>> earlier version and we changed it?)
>>>
>>> Well, it's not a big deal to me personally.
>>
>> interface with constant end parameter is more comfortable for loop: 
>> we don't need to update 'bytes' parameter on each iteration
>
> But there's still the question of WHO should be calculating end. Your 
> interface argues for the caller:
>
> hbitmap_next_zero(start, start + bytes)
>
> int64_t hbitmap_next_zero(...)
> {
>     while (offset != end) ...
> }
>
> while we're asking about a consistent interface for the caller (if 
> most callers already have a 'bytes' rather than an 'end' computed):
>
> hbitmap_next_zero(start, bytes)
>
> int64_t hbitmap_next_zero(...)
> {
>     int64_t end = start + bytes;
>     while (offset != end) ...
> }
>

Yes, that's an issue. Ok, if you are not comfortable with start,end, I 
can switch to start,bytes.

-- 
Best regards,
Vladimir

On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
> 10.09.2018 19:55, Eric Blake wrote:
>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>
>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>> int64_t end);
>>>> The interface looks weird because we can define a 'start' that's beyond
>>>> the 'end'.
>>>>
>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>> in an
>>>> earlier version and we changed it?)
>>>>
>>>> Well, it's not a big deal to me personally.
>>>
>>> interface with constant end parameter is more comfortable for loop:
>>> we don't need to update 'bytes' parameter on each iteration
>>
>> But there's still the question of WHO should be calculating end. Your
>> interface argues for the caller:
>>
>> hbitmap_next_zero(start, start + bytes)
>>
>> int64_t hbitmap_next_zero(...)
>> {
>>     while (offset != end) ...
>> }
>>
>> while we're asking about a consistent interface for the caller (if
>> most callers already have a 'bytes' rather than an 'end' computed):
>>
>> hbitmap_next_zero(start, bytes)
>>
>> int64_t hbitmap_next_zero(...)
>> {
>>     int64_t end = start + bytes;
>>     while (offset != end) ...
>> }
>>
> 
> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
> can switch to start,bytes.
> 

The series looks pretty close, I can merge the next version if you think
it's worth changing the interface.

--js

14.09.2018 20:39, John Snow wrote:
>
> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
>> 10.09.2018 19:55, Eric Blake wrote:
>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>>
>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>>> int64_t end);
>>>>> The interface looks weird because we can define a 'start' that's beyond
>>>>> the 'end'.
>>>>>
>>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>>> in an
>>>>> earlier version and we changed it?)
>>>>>
>>>>> Well, it's not a big deal to me personally.
>>>> interface with constant end parameter is more comfortable for loop:
>>>> we don't need to update 'bytes' parameter on each iteration
>>> But there's still the question of WHO should be calculating end. Your
>>> interface argues for the caller:
>>>
>>> hbitmap_next_zero(start, start + bytes)
>>>
>>> int64_t hbitmap_next_zero(...)
>>> {
>>>      while (offset != end) ...
>>> }
>>>
>>> while we're asking about a consistent interface for the caller (if
>>> most callers already have a 'bytes' rather than an 'end' computed):
>>>
>>> hbitmap_next_zero(start, bytes)
>>>
>>> int64_t hbitmap_next_zero(...)
>>> {
>>>      int64_t end = start + bytes;
>>>      while (offset != end) ...
>>> }
>>>
>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
>> can switch to start,bytes.
>>
> The series looks pretty close, I can merge the next version if you think
> it's worth changing the interface.
>
> --js

I've started to change interface and found a bug in bitmap_to_extents 
(patch sent 
https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html). 
So, next version will be based on this patch, which will go through 
Eric's tree..

-- 
Best regards,
Vladimir

On 09/14/2018 01:51 PM, Vladimir Sementsov-Ogievskiy wrote:
> 14.09.2018 20:39, John Snow wrote:
>>
>> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
>>> 10.09.2018 19:55, Eric Blake wrote:
>>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>>>
>>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>>>> int64_t end);
>>>>>> The interface looks weird because we can define a 'start' that's
>>>>>> beyond
>>>>>> the 'end'.
>>>>>>
>>>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>>>> in an
>>>>>> earlier version and we changed it?)
>>>>>>
>>>>>> Well, it's not a big deal to me personally.
>>>>> interface with constant end parameter is more comfortable for loop:
>>>>> we don't need to update 'bytes' parameter on each iteration
>>>> But there's still the question of WHO should be calculating end. Your
>>>> interface argues for the caller:
>>>>
>>>> hbitmap_next_zero(start, start + bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>>      while (offset != end) ...
>>>> }
>>>>
>>>> while we're asking about a consistent interface for the caller (if
>>>> most callers already have a 'bytes' rather than an 'end' computed):
>>>>
>>>> hbitmap_next_zero(start, bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>>      int64_t end = start + bytes;
>>>>      while (offset != end) ...
>>>> }
>>>>
>>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
>>> can switch to start,bytes.
>>>
>> The series looks pretty close, I can merge the next version if you think
>> it's worth changing the interface.
>>
>> --js
> 
> I've started to change interface and found a bug in bitmap_to_extents
> (patch sent
> https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html).
> So, next version will be based on this patch, which will go through
> Eric's tree..
> 

OK, I spoke with Eric and if you resend and I R-B & ACK the patches,
he'll stage them through NBD.

Thanks,
--js

On 09/14/2018 01:51 PM, Vladimir Sementsov-Ogievskiy wrote:
> 14.09.2018 20:39, John Snow wrote:
>>
>> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
>>> 10.09.2018 19:55, Eric Blake wrote:
>>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>>>
>>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>>>> int64_t end);
>>>>>> The interface looks weird because we can define a 'start' that's
>>>>>> beyond
>>>>>> the 'end'.
>>>>>>
>>>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>>>> in an
>>>>>> earlier version and we changed it?)
>>>>>>
>>>>>> Well, it's not a big deal to me personally.
>>>>> interface with constant end parameter is more comfortable for loop:
>>>>> we don't need to update 'bytes' parameter on each iteration
>>>> But there's still the question of WHO should be calculating end. Your
>>>> interface argues for the caller:
>>>>
>>>> hbitmap_next_zero(start, start + bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>>      while (offset != end) ...
>>>> }
>>>>
>>>> while we're asking about a consistent interface for the caller (if
>>>> most callers already have a 'bytes' rather than an 'end' computed):
>>>>
>>>> hbitmap_next_zero(start, bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>>      int64_t end = start + bytes;
>>>>      while (offset != end) ...
>>>> }
>>>>
>>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
>>> can switch to start,bytes.
>>>
>> The series looks pretty close, I can merge the next version if you think
>> it's worth changing the interface.
>>
>> --js
> 
> I've started to change interface and found a bug in bitmap_to_extents
> (patch sent
> https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html).
> So, next version will be based on this patch, which will go through
> Eric's tree..
> 

ah, I see. you can send it to the list anyway with the requires: header
and I can have Eric stage it to make the eventual merge easier for Peter.

--js

On 9/7/18 4:49 PM, John Snow wrote:
> 
> 
> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
>> Add bytes parameter to the function, to limit searched range.
>>
> 
> I'm going to assume that Eric Blake has been through here and commented
> on the interface itself.

Actually, I haven't had time to look at this series in depth. Do you 
need me to?

> 
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/block/dirty-bitmap.h |  3 ++-
>>   include/qemu/hbitmap.h       | 10 ++++++++--
>>   block/backup.c               |  2 +-
>>   block/dirty-bitmap.c         |  5 +++--
>>   nbd/server.c                 |  2 +-
>>   tests/test-hbitmap.c         |  2 +-
>>   util/hbitmap.c               | 25 ++++++++++++++++++++-----
>>   7 files changed, 36 insertions(+), 13 deletions(-)
>>
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 259bd27c40..27f5299c4e 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>>   BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>>                                           BdrvDirtyBitmap *bitmap);
>>   char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
>> +                                    int64_t end);

It's already seeming a bit odd to mix uint64_t AND int64_t for the two 
parameters.  Is the intent to allow -1 to mean "end of the bitmap 
instead of a specific end range"? But you can get that with UINT64_MAX 
just as easily, and still get away with spelling it -1 in the source.


>> + * the bitmap end.
>>    */
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>>   
> 
> The interface looks weird because we can define a 'start' that's beyond
> the 'end'.
> 
> I realize that you need a signed integer for 'end' to signify EOF...
> should we do a 'bytes' parameter instead? (Did you already do that in an
> earlier version and we changed it?)
> 
> Well, it's not a big deal to me personally.

It should always be possible to convert in either direction between 
[start,end) and [start,start+bytes); it boils down to a question of 
convenience (which form is easier for the majority of callers) and 
consistency (which form do we use more frequently in the block layer). I 
haven't checked closely, but I think start+bytes is more common than end 
in our public block layer APIs.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

On 09/10/2018 10:59 AM, Eric Blake wrote:
> On 9/7/18 4:49 PM, John Snow wrote:
>>
>>
>> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
>>> Add bytes parameter to the function, to limit searched range.
>>>
>>
>> I'm going to assume that Eric Blake has been through here and commented
>> on the interface itself.
> 
> Actually, I haven't had time to look at this series in depth. Do you
> need me to?
> 

Not necessarily, it's just that I didn't read v1 or v2 so I was just
being cautious against recommending changes that maybe we already
recommended against in a different direction.

Historically you've cared the most about start/end/offset/bytes naming
and conventions, so I just made an assumption.

--js

>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>   include/block/dirty-bitmap.h |  3 ++-
>>>   include/qemu/hbitmap.h       | 10 ++++++++--
>>>   block/backup.c               |  2 +-
>>>   block/dirty-bitmap.c         |  5 +++--
>>>   nbd/server.c                 |  2 +-
>>>   tests/test-hbitmap.c         |  2 +-
>>>   util/hbitmap.c               | 25 ++++++++++++++++++++-----
>>>   7 files changed, 36 insertions(+), 13 deletions(-)
>>>
>>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>>> index 259bd27c40..27f5299c4e 100644
>>> --- a/include/block/dirty-bitmap.h
>>> +++ b/include/block/dirty-bitmap.h
>>> @@ -98,7 +98,8 @@ bool
>>> bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>>>   BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>>>                                           BdrvDirtyBitmap *bitmap);
>>>   char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error
>>> **errp);
>>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap,
>>> uint64_t start);
>>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap,
>>> uint64_t start,
>>> +                                    int64_t end);
> 
> It's already seeming a bit odd to mix uint64_t AND int64_t for the two
> parameters.  Is the intent to allow -1 to mean "end of the bitmap
> instead of a specific end range"? But you can get that with UINT64_MAX
> just as easily, and still get away with spelling it -1 in the source.
> 
> 
>>> + * the bitmap end.
>>>    */
>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t
>>> end);
>>>   
>>
>> The interface looks weird because we can define a 'start' that's beyond
>> the 'end'.
>>
>> I realize that you need a signed integer for 'end' to signify EOF...
>> should we do a 'bytes' parameter instead? (Did you already do that in an
>> earlier version and we changed it?)
>>
>> Well, it's not a big deal to me personally.
> 
> It should always be possible to convert in either direction between
> [start,end) and [start,start+bytes); it boils down to a question of
> convenience (which form is easier for the majority of callers) and
> consistency (which form do we use more frequently in the block layer). I
> haven't checked closely, but I think start+bytes is more common than end
> in our public block layer APIs.
>