[PATCH v3 00/10] Further bitmaps improvements

[PATCH v3 00/10] Further bitmaps improvements

[Vladimir Sementsov-Ogievskiy]

Hi!

The main feature here is improvement of _next_dirty_area API, which I'm
going to use then for backup / block-copy.

v3: rebase on current master. Mirror don't use _next_dirty_area any
more, so mirror chunks dropped (patches 05 and 07) and 07 commit message
changed.

Vladimir Sementsov-Ogievskiy (10):
  hbitmap: assert that we don't create bitmap larger than INT64_MAX
  hbitmap: move hbitmap_iter_next_word to hbitmap.c
  hbitmap: unpublish hbitmap_iter_skip_words
  hbitmap: drop meta bitmaps as they are unused
  block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t
  block/dirty-bitmap: add _next_dirty API
  block/dirty-bitmap: improve _next_dirty_area API
  nbd/server: introduce NBDExtentArray
  nbd/server: use bdrv_dirty_bitmap_next_dirty_area
  block/qcow2-bitmap: use bdrv_dirty_bitmap_next_dirty

 include/block/dirty-bitmap.h |   9 +-
 include/qemu/hbitmap.h       |  97 +++--------
 block/dirty-bitmap.c         |  16 +-
 block/qcow2-bitmap.c         |  11 +-
 nbd/server.c                 | 242 +++++++++++++--------------
 tests/test-hbitmap.c         | 314 +++++++++++++----------------------
 util/hbitmap.c               | 133 +++++++++------
 7 files changed, 366 insertions(+), 456 deletions(-)

-- 
2.21.0

[PATCH v3 01/10] hbitmap: assert that we don't create bitmap larger than INT64_MAX

[Vladimir Sementsov-Ogievskiy]

We have APIs which returns signed int64_t, to be able to return error.
Therefore we can't handle bitmaps with absolute size larger than
(INT64_MAX+1). Still, keep maximum to be INT64_MAX which is a bit
safer.

Note, that bitmaps are used to represent disk images, which can't
exceed INT64_MAX anyway.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 util/hbitmap.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/util/hbitmap.c b/util/hbitmap.c
index 242c6e519c..7f9b3e0cd7 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -716,6 +716,7 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
     HBitmap *hb = g_new0(struct HBitmap, 1);
     unsigned i;
 
+    assert(size <= INT64_MAX);
     hb->orig_size = size;
 
     assert(granularity >= 0 && granularity < 64);
@@ -746,6 +747,7 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
     uint64_t num_elements = size;
     uint64_t old;
 
+    assert(size <= INT64_MAX);
     hb->orig_size = size;
 
     /* Size comes in as logical elements, adjust for granularity. */
-- 
2.21.0

Re: [PATCH v3 01/10] hbitmap: assert that we don't create bitmap larger than INT64_MAX

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 573 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> We have APIs which returns signed int64_t, to be able to return error.
> Therefore we can't handle bitmaps with absolute size larger than
> (INT64_MAX+1). Still, keep maximum to be INT64_MAX which is a bit
> safer.
> 
> Note, that bitmaps are used to represent disk images, which can't
> exceed INT64_MAX anyway.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  util/hbitmap.c | 2 ++
>  1 file changed, 2 insertions(+)

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH v3 02/10] hbitmap: move hbitmap_iter_next_word to hbitmap.c

[Vladimir Sementsov-Ogievskiy]

The function is definitely internal (it's not used by third party and
it has complicated interface). Move it to .c file.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/qemu/hbitmap.h | 30 ------------------------------
 util/hbitmap.c         | 29 +++++++++++++++++++++++++++++
 2 files changed, 29 insertions(+), 30 deletions(-)

diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 1bf944ca3d..ab227b117f 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -362,34 +362,4 @@ void hbitmap_free_meta(HBitmap *hb);
  */
 int64_t hbitmap_iter_next(HBitmapIter *hbi);
 
-/**
- * hbitmap_iter_next_word:
- * @hbi: HBitmapIter to operate on.
- * @p_cur: Location where to store the next non-zero word.
- *
- * Return the index of the next nonzero word that is set in @hbi's
- * associated HBitmap, and set *p_cur to the content of that word
- * (bits before the index that was passed to hbitmap_iter_init are
- * trimmed on the first call).  Return -1, and set *p_cur to zero,
- * if all remaining words are zero.
- */
-static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
-{
-    unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
-
-    if (cur == 0) {
-        cur = hbitmap_iter_skip_words(hbi);
-        if (cur == 0) {
-            *p_cur = 0;
-            return -1;
-        }
-    }
-
-    /* The next call will resume work from the next word.  */
-    hbi->cur[HBITMAP_LEVELS - 1] = 0;
-    *p_cur = cur;
-    return hbi->pos;
-}
-
-
 #endif
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 7f9b3e0cd7..a368dc5ef7 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -298,6 +298,35 @@ uint64_t hbitmap_count(const HBitmap *hb)
     return hb->count << hb->granularity;
 }
 
+/**
+ * hbitmap_iter_next_word:
+ * @hbi: HBitmapIter to operate on.
+ * @p_cur: Location where to store the next non-zero word.
+ *
+ * Return the index of the next nonzero word that is set in @hbi's
+ * associated HBitmap, and set *p_cur to the content of that word
+ * (bits before the index that was passed to hbitmap_iter_init are
+ * trimmed on the first call).  Return -1, and set *p_cur to zero,
+ * if all remaining words are zero.
+ */
+static size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
+{
+    unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
+
+    if (cur == 0) {
+        cur = hbitmap_iter_skip_words(hbi);
+        if (cur == 0) {
+            *p_cur = 0;
+            return -1;
+        }
+    }
+
+    /* The next call will resume work from the next word.  */
+    hbi->cur[HBITMAP_LEVELS - 1] = 0;
+    *p_cur = cur;
+    return hbi->pos;
+}
+
 /* 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.
  */
-- 
2.21.0

Re: [PATCH v3 02/10] hbitmap: move hbitmap_iter_next_word to hbitmap.c

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 624 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> The function is definitely internal (it's not used by third party and
> it has complicated interface). Move it to .c file.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/qemu/hbitmap.h | 30 ------------------------------
>  util/hbitmap.c         | 29 +++++++++++++++++++++++++++++
>  2 files changed, 29 insertions(+), 30 deletions(-)

I wonder why you removed the “inline”, but then again we should probably
trust the compiler more than our intuition anyway.

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 02/10] hbitmap: move hbitmap_iter_next_word to hbitmap.c

[Vladimir Sementsov-Ogievskiy]

20.01.2020 13:55, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> The function is definitely internal (it's not used by third party and
>> it has complicated interface). Move it to .c file.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/qemu/hbitmap.h | 30 ------------------------------
>>   util/hbitmap.c         | 29 +++++++++++++++++++++++++++++
>>   2 files changed, 29 insertions(+), 30 deletions(-)
> 
> I wonder why you removed the “inline”, but then again we should probably
> trust the compiler more than our intuition anyway.

Hmm, somehow, I was sure, that defining "static inline" functions in .c file is
equal to defining them just "static", as compiler will decide inline it or not
it on its own anyway.. May be I'm wrong. At least it's claimed that compiler may
ignore "inline", so it's a hing, and on the other hand it may inline not "inline"
function.

And even if I'm wrong, I agree that in non-critical cases we should trust the
compiler optimization strategy.

> 
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> 


-- 
Best regards,
Vladimir

[PATCH v3 03/10] hbitmap: unpublish hbitmap_iter_skip_words

[Vladimir Sementsov-Ogievskiy]

Function is internal and even commented as internal. Drop its
definition from .h file.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/qemu/hbitmap.h | 7 -------
 util/hbitmap.c         | 2 +-
 2 files changed, 1 insertion(+), 8 deletions(-)

diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index ab227b117f..15837a0e2d 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -297,13 +297,6 @@ void hbitmap_free(HBitmap *hb);
  */
 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 
-/* hbitmap_iter_skip_words:
- * @hbi: HBitmapIter to operate on.
- *
- * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
- */
-unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
-
 /* hbitmap_next_zero:
  *
  * Find next not dirty bit within selected range. If not found, return -1.
diff --git a/util/hbitmap.c b/util/hbitmap.c
index a368dc5ef7..26145d4b9e 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -104,7 +104,7 @@ struct HBitmap {
 /* Advance hbi to the next nonzero word and return it.  hbi->pos
  * is updated.  Returns zero if we reach the end of the bitmap.
  */
-unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
+static unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
 {
     size_t pos = hbi->pos;
     const HBitmap *hb = hbi->hb;
-- 
2.21.0

Re: [PATCH v3 03/10] hbitmap: unpublish hbitmap_iter_skip_words

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 407 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> Function is internal and even commented as internal. Drop its
> definition from .h file.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/qemu/hbitmap.h | 7 -------
>  util/hbitmap.c         | 2 +-
>  2 files changed, 1 insertion(+), 8 deletions(-)

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Vladimir Sementsov-Ogievskiy]

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/qemu/hbitmap.h |  21 --------
 tests/test-hbitmap.c   | 115 -----------------------------------------
 util/hbitmap.c         |  16 ------
 3 files changed, 152 deletions(-)

diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 15837a0e2d..df922d8517 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -325,27 +325,6 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
 bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start,
                              uint64_t *count);
 
-/* hbitmap_create_meta:
- * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
- * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
- * free it.
- *
- * Currently, we only guarantee that if a bit in the hbitmap is changed it
- * will be reflected in the meta bitmap, but we do not yet guarantee the
- * opposite.
- *
- * @hb: The HBitmap to operate on.
- * @chunk_size: How many bits in @hb does one bit in the meta track.
- */
-HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size);
-
-/* hbitmap_free_meta:
- * Free the meta bitmap of @hb.
- *
- * @hb: The HBitmap whose meta bitmap should be freed.
- */
-void hbitmap_free_meta(HBitmap *hb);
-
 /**
  * hbitmap_iter_next:
  * @hbi: HBitmapIter to operate on.
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index e1f867085f..aeaa0b3f22 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -22,7 +22,6 @@
 
 typedef struct TestHBitmapData {
     HBitmap       *hb;
-    HBitmap       *meta;
     unsigned long *bits;
     size_t         size;
     size_t         old_size;
@@ -94,14 +93,6 @@ static void hbitmap_test_init(TestHBitmapData *data,
     }
 }
 
-static void hbitmap_test_init_meta(TestHBitmapData *data,
-                                   uint64_t size, int granularity,
-                                   int meta_chunk)
-{
-    hbitmap_test_init(data, size, granularity);
-    data->meta = hbitmap_create_meta(data->hb, meta_chunk);
-}
-
 static inline size_t hbitmap_test_array_size(size_t bits)
 {
     size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
@@ -144,9 +135,6 @@ static void hbitmap_test_teardown(TestHBitmapData *data,
                                   const void *unused)
 {
     if (data->hb) {
-        if (data->meta) {
-            hbitmap_free_meta(data->hb);
-        }
         hbitmap_free(data->hb);
         data->hb = NULL;
     }
@@ -648,96 +636,6 @@ static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
     hbitmap_test_truncate(data, size, -diff, 0);
 }
 
-static void hbitmap_check_meta(TestHBitmapData *data,
-                               int64_t start, int count)
-{
-    int64_t i;
-
-    for (i = 0; i < data->size; i++) {
-        if (i >= start && i < start + count) {
-            g_assert(hbitmap_get(data->meta, i));
-        } else {
-            g_assert(!hbitmap_get(data->meta, i));
-        }
-    }
-}
-
-static void hbitmap_test_meta(TestHBitmapData *data,
-                              int64_t start, int count,
-                              int64_t check_start, int check_count)
-{
-    hbitmap_reset_all(data->hb);
-    hbitmap_reset_all(data->meta);
-
-    /* Test "unset" -> "unset" will not update meta. */
-    hbitmap_reset(data->hb, start, count);
-    hbitmap_check_meta(data, 0, 0);
-
-    /* Test "unset" -> "set" will update meta */
-    hbitmap_set(data->hb, start, count);
-    hbitmap_check_meta(data, check_start, check_count);
-
-    /* Test "set" -> "set" will not update meta */
-    hbitmap_reset_all(data->meta);
-    hbitmap_set(data->hb, start, count);
-    hbitmap_check_meta(data, 0, 0);
-
-    /* Test "set" -> "unset" will update meta */
-    hbitmap_reset_all(data->meta);
-    hbitmap_reset(data->hb, start, count);
-    hbitmap_check_meta(data, check_start, check_count);
-}
-
-static void hbitmap_test_meta_do(TestHBitmapData *data, int chunk_size)
-{
-    uint64_t size = chunk_size * 100;
-    hbitmap_test_init_meta(data, size, 0, chunk_size);
-
-    hbitmap_test_meta(data, 0, 1, 0, chunk_size);
-    hbitmap_test_meta(data, 0, chunk_size, 0, chunk_size);
-    hbitmap_test_meta(data, chunk_size - 1, 1, 0, chunk_size);
-    hbitmap_test_meta(data, chunk_size - 1, 2, 0, chunk_size * 2);
-    hbitmap_test_meta(data, chunk_size - 1, chunk_size + 1, 0, chunk_size * 2);
-    hbitmap_test_meta(data, chunk_size - 1, chunk_size + 2, 0, chunk_size * 3);
-    hbitmap_test_meta(data, 7 * chunk_size - 1, chunk_size + 2,
-                      6 * chunk_size, chunk_size * 3);
-    hbitmap_test_meta(data, size - 1, 1, size - chunk_size, chunk_size);
-    hbitmap_test_meta(data, 0, size, 0, size);
-}
-
-static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused)
-{
-    hbitmap_test_meta_do(data, BITS_PER_BYTE);
-}
-
-static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused)
-{
-    hbitmap_test_meta_do(data, BITS_PER_LONG);
-}
-
-static void test_hbitmap_meta_sector(TestHBitmapData *data, const void *unused)
-{
-    hbitmap_test_meta_do(data, BDRV_SECTOR_SIZE * BITS_PER_BYTE);
-}
-
-/**
- * Create an HBitmap and test set/unset.
- */
-static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused)
-{
-    int i;
-    int64_t offsets[] = {
-        0, 1, L1 - 1, L1, L1 + 1, L2 - 1, L2, L2 + 1, L3 - 1, L3, L3 + 1
-    };
-
-    hbitmap_test_init_meta(data, L3 * 2, 0, 1);
-    for (i = 0; i < ARRAY_SIZE(offsets); i++) {
-        hbitmap_test_meta(data, offsets[i], 1, offsets[i], 1);
-        hbitmap_test_meta(data, offsets[i], L1, offsets[i], L1);
-        hbitmap_test_meta(data, offsets[i], L2, offsets[i], L2);
-    }
-}
-
 static void test_hbitmap_serialize_align(TestHBitmapData *data,
                                          const void *unused)
 {
@@ -750,13 +648,6 @@ static void test_hbitmap_serialize_align(TestHBitmapData *data,
     g_assert_cmpint(r, ==, 64 << 3);
 }
 
-static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
-{
-    hbitmap_test_init_meta(data, 0, 0, 1);
-
-    hbitmap_check_meta(data, 0, 0);
-}
-
 static void hbitmap_test_serialize_range(TestHBitmapData *data,
                                          uint8_t *buf, size_t buf_size,
                                          uint64_t pos, uint64_t count)
@@ -1165,12 +1056,6 @@ int main(int argc, char **argv)
     hbitmap_test_add("/hbitmap/truncate/shrink/large",
                      test_hbitmap_truncate_shrink_large);
 
-    hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero);
-    hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one);
-    hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte);
-    hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word);
-    hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector);
-
     hbitmap_test_add("/hbitmap/serialize/align",
                      test_hbitmap_serialize_align);
     hbitmap_test_add("/hbitmap/serialize/basic",
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 26145d4b9e..b6d4b99a06 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -905,22 +905,6 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
     return true;
 }
 
-HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size)
-{
-    assert(!(chunk_size & (chunk_size - 1)));
-    assert(!hb->meta);
-    hb->meta = hbitmap_alloc(hb->size << hb->granularity,
-                             hb->granularity + ctz32(chunk_size));
-    return hb->meta;
-}
-
-void hbitmap_free_meta(HBitmap *hb)
-{
-    assert(hb->meta);
-    hbitmap_free(hb->meta);
-    hb->meta = NULL;
-}
-
 char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
 {
     size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
-- 
2.21.0

Re: [PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 703 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/qemu/hbitmap.h |  21 --------
>  tests/test-hbitmap.c   | 115 -----------------------------------------
>  util/hbitmap.c         |  16 ------
>  3 files changed, 152 deletions(-)

Er, hrm, well.

Reviewed-by: Max Reitz <mreitz@redhat.com>

git log me the only commits that touched anything to the regard of
'*create_meta*' were the ones that introduced it and your commit that
dropped it.

Soo, er, well, okay.  Why did we introduce these again?  (I suppose I
should know since they have my S-o-b on them.  But I actually don’t.)

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Vladimir Sementsov-Ogievskiy]

20.01.2020 14:13, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/qemu/hbitmap.h |  21 --------
>>   tests/test-hbitmap.c   | 115 -----------------------------------------
>>   util/hbitmap.c         |  16 ------
>>   3 files changed, 152 deletions(-)
> 
> Er, hrm, well.
> 
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> 
> git log me the only commits that touched anything to the regard of
> '*create_meta*' were the ones that introduced it and your commit that
> dropped it.
> 
> Soo, er, well, okay.  Why did we introduce these again?  (I suppose I
> should know since they have my S-o-b on them.  But I actually don’t.)
> 
> Max
> 

I'm a bit not follow what you mean. I can just note, that dirty-bitmap.c
part of meta bitmaps was recently removed, and hbitmap.c part I forgot to
remove...

Meta bitmaps were intended to control live migration of bitmaps and to
implement something like partial sync of bitmaps (write to qcow2 only
changed part of bitmap), but migration implemented in other way
(postcopy) and the second thing was not implemented.

-- 
Best regards,
Vladimir

Re: [PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 1492 bytes --]

On 20.01.20 17:20, Vladimir Sementsov-Ogievskiy wrote:
> 20.01.2020 14:13, Max Reitz wrote:
>> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>   include/qemu/hbitmap.h |  21 --------
>>>   tests/test-hbitmap.c   | 115 -----------------------------------------
>>>   util/hbitmap.c         |  16 ------
>>>   3 files changed, 152 deletions(-)
>>
>> Er, hrm, well.
>>
>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>>
>> git log me the only commits that touched anything to the regard of
>> '*create_meta*' were the ones that introduced it and your commit that
>> dropped it.
>>
>> Soo, er, well, okay.  Why did we introduce these again?  (I suppose I
>> should know since they have my S-o-b on them.  But I actually don’t.)
>>
>> Max
>>
> 
> I'm a bit not follow what you mean. I can just note, that dirty-bitmap.c
> part of meta bitmaps was recently removed, and hbitmap.c part I forgot to
> remove...

Yes, but who used that dirty-bitmap.c interface?  As far as I can tell,
nobody.

> Meta bitmaps were intended to control live migration of bitmaps and to
> implement something like partial sync of bitmaps (write to qcow2 only
> changed part of bitmap), but migration implemented in other way
> (postcopy) and the second thing was not implemented.

OK.  I was wondering why they were implemented without ever having been
used (as far as I can tell).

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Vladimir Sementsov-Ogievskiy]

20.01.2020 20:05, Max Reitz wrote:
> On 20.01.20 17:20, Vladimir Sementsov-Ogievskiy wrote:
>> 20.01.2020 14:13, Max Reitz wrote:
>>> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>>> ---
>>>>    include/qemu/hbitmap.h |  21 --------
>>>>    tests/test-hbitmap.c   | 115 -----------------------------------------
>>>>    util/hbitmap.c         |  16 ------
>>>>    3 files changed, 152 deletions(-)
>>>
>>> Er, hrm, well.
>>>
>>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>>>
>>> git log me the only commits that touched anything to the regard of
>>> '*create_meta*' were the ones that introduced it and your commit that
>>> dropped it.
>>>
>>> Soo, er, well, okay.  Why did we introduce these again?  (I suppose I
>>> should know since they have my S-o-b on them.  But I actually don’t.)
>>>
>>> Max
>>>
>>
>> I'm a bit not follow what you mean. I can just note, that dirty-bitmap.c
>> part of meta bitmaps was recently removed, and hbitmap.c part I forgot to
>> remove...
> 
> Yes, but who used that dirty-bitmap.c interface?  As far as I can tell,
> nobody.

Yes, as far as I know, nobody and never.

> 
>> Meta bitmaps were intended to control live migration of bitmaps and to
>> implement something like partial sync of bitmaps (write to qcow2 only
>> changed part of bitmap), but migration implemented in other way
>> (postcopy) and the second thing was not implemented.
> 
> OK.  I was wondering why they were implemented without ever having been
> used (as far as I can tell).
> 

It was too optimistic preparatory series.

(I can never finally understand, series - who a they or what is it?
  Plural or singular? They were too optimistic series? Sounds weird..
  And if one series is series, than what about several serieses?
  OK, let's say, it was too optimistic preparatory patch set :)


-- 
Best regards,
Vladimir

Re: [PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Eric Blake]

On 1/20/20 11:28 AM, Vladimir Sementsov-Ogievskiy wrote:

>>> I'm a bit not follow what you mean. I can just note, that dirty-bitmap.c
>>> part of meta bitmaps was recently removed, and hbitmap.c part I forgot to
>>> remove...
>>
>> Yes, but who used that dirty-bitmap.c interface?  As far as I can tell,
>> nobody.
> 
> Yes, as far as I know, nobody and never.
> 
>>
>>> Meta bitmaps were intended to control live migration of bitmaps and to
>>> implement something like partial sync of bitmaps (write to qcow2 only
>>> changed part of bitmap), but migration implemented in other way
>>> (postcopy) and the second thing was not implemented.
>>
>> OK.  I was wondering why they were implemented without ever having been
>> used (as far as I can tell).
>>
> 
> It was too optimistic preparatory series.

Matches my recollection (we had several ideas about how to tackle it; 
meta-bitmaps was proposed as one idea and this code landed, but we never 
actually finished that idea before a better one was actually coded, so 
this has always been dead code).

> 
> (I can never finally understand, series - who a they or what is it?
>    Plural or singular?

English is funny; "series" is one of the few words that works as both 
singular and plural (another example is "sheep").

> They were too optimistic series? Sounds weird..

My spin: "The original series was too optimistic."

>    And if one series is series, than what about several serieses?
>    OK, let's say, it was too optimistic preparatory patch set :)
> 
> 

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

Re: [PATCH v3 04/10] hbitmap: drop meta bitmaps as they are unused

[Vladimir Sementsov-Ogievskiy]

20.01.2020 22:53, Eric Blake wrote:
> On 1/20/20 11:28 AM, Vladimir Sementsov-Ogievskiy wrote:
> 
>>>> I'm a bit not follow what you mean. I can just note, that dirty-bitmap.c
>>>> part of meta bitmaps was recently removed, and hbitmap.c part I forgot to
>>>> remove...
>>>
>>> Yes, but who used that dirty-bitmap.c interface?  As far as I can tell,
>>> nobody.
>>
>> Yes, as far as I know, nobody and never.
>>
>>>
>>>> Meta bitmaps were intended to control live migration of bitmaps and to
>>>> implement something like partial sync of bitmaps (write to qcow2 only
>>>> changed part of bitmap), but migration implemented in other way
>>>> (postcopy) and the second thing was not implemented.
>>>
>>> OK.  I was wondering why they were implemented without ever having been
>>> used (as far as I can tell).
>>>
>>
>> It was too optimistic preparatory series.
> 
> Matches my recollection (we had several ideas about how to tackle it; meta-bitmaps was proposed as one idea and this code landed, but we never actually finished that idea before a better one was actually coded, so this has always been dead code).
> 
>>
>> (I can never finally understand, series - who a they or what is it?
>>    Plural or singular?
> 
> English is funny; "series" is one of the few words that works as both singular and plural (another example is "sheep").

OK, thanks) Actually, Russian has such words too (штаны=pants, ножницы=scissors, interesting that first examples
which came in my mind has same feature in English too).

> 
>> They were too optimistic series? Sounds weird..
> 
> My spin: "The original series was too optimistic."
> 
>>    And if one series is series, than what about several serieses?
>>    OK, let's say, it was too optimistic preparatory patch set :)
>>
>>
> 


-- 
Best regards,
Vladimir

[PATCH v3 05/10] block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t

[Vladimir Sementsov-Ogievskiy]

We are going to introduce bdrv_dirty_bitmap_next_dirty so that same
variable may be used to store its return value and to be its parameter,
so it would int64_t.

Similarly, we are going to refactor hbitmap_next_dirty_area to use
hbitmap_next_dirty together with hbitmap_next_zero, therefore we want
hbitmap_next_zero parameter type to be int64_t too.

So, for convenience update all parameters of *_next_zero and
*_next_dirty_area to be int64_t.

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

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index e2b20ecab9..27c72cc56a 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -105,10 +105,10 @@ for (bitmap = bdrv_dirty_bitmap_first(bs); bitmap; \
      bitmap = bdrv_dirty_bitmap_next(bitmap))
 
 char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
-                                    uint64_t bytes);
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset,
+                                    int64_t bytes);
 bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
-                                       uint64_t *offset, uint64_t *bytes);
+                                       int64_t *offset, int64_t *bytes);
 BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
                                                   Error **errp);
 
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index df922d8517..b6e85f3d5d 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -304,10 +304,10 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
  * @hb: The HBitmap to operate on
  * @start: The bit to start from.
  * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole
- * bitmap is looked through. You can use UINT64_MAX as @count to search up to
+ * bitmap is looked through. You can use INT64_MAX as @count to search up to
  * the bitmap end.
  */
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
+int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count);
 
 /* hbitmap_next_dirty_area:
  * @hb: The HBitmap to operate on
@@ -322,8 +322,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
  * @offset and @bytes appropriately. Otherwise returns false and leaves @offset
  * and @bytes unchanged.
  */
-bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start,
-                             uint64_t *count);
+bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count);
 
 /**
  * hbitmap_iter_next:
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 7039e82520..af9f5411a6 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -860,14 +860,14 @@ 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,
-                                    uint64_t bytes)
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset,
+                                    int64_t bytes)
 {
     return hbitmap_next_zero(bitmap->bitmap, offset, bytes);
 }
 
 bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
-                                       uint64_t *offset, uint64_t *bytes)
+                                       int64_t *offset, int64_t *bytes)
 {
     return hbitmap_next_dirty_area(bitmap->bitmap, offset, bytes);
 }
diff --git a/nbd/server.c b/nbd/server.c
index 24ebc1a805..a4b348eb32 100644
--- a/nbd/server.c
+++ b/nbd/server.c
@@ -2055,7 +2055,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
         bool next_dirty = !dirty;
 
         if (dirty) {
-            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, UINT64_MAX);
+            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, INT64_MAX);
         } 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 aeaa0b3f22..0e1e5c64dd 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -837,7 +837,7 @@ static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
 
 static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
 {
-    test_hbitmap_next_zero_check_range(data, start, UINT64_MAX);
+    test_hbitmap_next_zero_check_range(data, start, INT64_MAX);
 }
 
 static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
@@ -905,11 +905,11 @@ static void test_hbitmap_next_zero_after_truncate(TestHBitmapData *data,
 }
 
 static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
-                                               uint64_t offset,
-                                               uint64_t count)
+                                               int64_t offset,
+                                               int64_t count)
 {
-    uint64_t off1, off2;
-    uint64_t len1 = 0, len2;
+    int64_t off1, off2;
+    int64_t len1 = 0, len2;
     bool ret1, ret2;
     int64_t end;
 
@@ -945,24 +945,24 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
                                             int granularity)
 {
     hbitmap_test_init(data, L3, granularity);
-    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, 0, 1);
     test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
 
     hbitmap_set(data->hb, L2, 1);
     test_hbitmap_next_dirty_area_check(data, 0, 1);
     test_hbitmap_next_dirty_area_check(data, 0, L2);
-    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
-    test_hbitmap_next_dirty_area_check(data, L2 - 1, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 - 1, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, L2 - 1, 1);
     test_hbitmap_next_dirty_area_check(data, L2 - 1, 2);
     test_hbitmap_next_dirty_area_check(data, L2 - 1, 3);
-    test_hbitmap_next_dirty_area_check(data, L2, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, L2, 1);
     test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
 
     hbitmap_set(data->hb, L2 + 5, L1);
-    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, L2 - 2, 8);
     test_hbitmap_next_dirty_area_check(data, L2 + 1, 5);
     test_hbitmap_next_dirty_area_check(data, L2 + 1, 3);
@@ -974,16 +974,16 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
     test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
 
     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
-    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
-    test_hbitmap_next_dirty_area_check(data, L2, UINT64_MAX);
-    test_hbitmap_next_dirty_area_check(data, L2 + 1, UINT64_MAX);
-    test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 + 1, INT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
     test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
     test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
 
     hbitmap_set(data->hb, 0, L3);
-    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
 }
 
 static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
@@ -1010,7 +1010,7 @@ static void test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData *data,
     hbitmap_test_init(data, L1, 0);
     hbitmap_test_truncate_impl(data, L1 * 2);
     hbitmap_set(data->hb, L1 + 1, 1);
-    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
 }
 
 int main(int argc, char **argv)
diff --git a/util/hbitmap.c b/util/hbitmap.c
index b6d4b99a06..df22f06be6 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -193,7 +193,7 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
     }
 }
 
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
+int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
 {
     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
     unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
@@ -202,6 +202,8 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
     uint64_t end_bit, sz;
     int64_t res;
 
+    assert(start >= 0 && count >= 0);
+
     if (start >= hb->orig_size || count == 0) {
         return -1;
     }
@@ -244,14 +246,15 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
     return res;
 }
 
-bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start,
-                             uint64_t *count)
+bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count)
 {
     HBitmapIter hbi;
     int64_t firt_dirty_off, area_end;
     uint32_t granularity = 1UL << hb->granularity;
     uint64_t end;
 
+    assert(*start >= 0 && *count >= 0);
+
     if (*start >= hb->orig_size || *count == 0) {
         return false;
     }
@@ -834,8 +837,8 @@ bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
  */
 static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
 {
-    uint64_t offset = 0;
-    uint64_t count = src->orig_size;
+    int64_t offset = 0;
+    int64_t count = src->orig_size;
 
     while (hbitmap_next_dirty_area(src, &offset, &count)) {
         hbitmap_set(dst, offset, count);
-- 
2.21.0

Re: [PATCH v3 05/10] block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 2492 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> We are going to introduce bdrv_dirty_bitmap_next_dirty so that same
> variable may be used to store its return value and to be its parameter,
> so it would int64_t.
> 
> Similarly, we are going to refactor hbitmap_next_dirty_area to use
> hbitmap_next_dirty together with hbitmap_next_zero, therefore we want
> hbitmap_next_zero parameter type to be int64_t too.
> 
> So, for convenience update all parameters of *_next_zero and
> *_next_dirty_area to be int64_t.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/block/dirty-bitmap.h |  6 +++---
>  include/qemu/hbitmap.h       |  7 +++----
>  block/dirty-bitmap.c         |  6 +++---
>  nbd/server.c                 |  2 +-
>  tests/test-hbitmap.c         | 32 ++++++++++++++++----------------
>  util/hbitmap.c               | 13 ++++++++-----
>  6 files changed, 34 insertions(+), 32 deletions(-)

[...]

> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index b6d4b99a06..df22f06be6 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -193,7 +193,7 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>      }
>  }
>  
> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
> +int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
>  {
>      size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
>      unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
> @@ -202,6 +202,8 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
>      uint64_t end_bit, sz;
>      int64_t res;
>  
> +    assert(start >= 0 && count >= 0);
> +
>      if (start >= hb->orig_size || count == 0) {
>          return -1;
>      }
As far as I can see, NBD just passes NBDRequest.from (which is a
uint64_t) to this function (on NBD_CMD_BLOCK_STATUS).  Would this allow
a malicious client to send a value > INT64_MAX, thus provoking an
overflow and killing the server with this new assertion?

On second thought, we have this problem already everywhere in
nbd_handle_request().  I don’t see it or its caller ever checking
whether the received values are in bounds, it just passes them to all
kind of block layer functions that sometimes even just accept plain
ints.  Well, I suppose all other functions just error out, so it
probably isn’t an actual problem in practice so far...

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 05/10] block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t

[Vladimir Sementsov-Ogievskiy]

20.01.2020 14:59, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> We are going to introduce bdrv_dirty_bitmap_next_dirty so that same
>> variable may be used to store its return value and to be its parameter,
>> so it would int64_t.
>>
>> Similarly, we are going to refactor hbitmap_next_dirty_area to use
>> hbitmap_next_dirty together with hbitmap_next_zero, therefore we want
>> hbitmap_next_zero parameter type to be int64_t too.
>>
>> So, for convenience update all parameters of *_next_zero and
>> *_next_dirty_area to be int64_t.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/block/dirty-bitmap.h |  6 +++---
>>   include/qemu/hbitmap.h       |  7 +++----
>>   block/dirty-bitmap.c         |  6 +++---
>>   nbd/server.c                 |  2 +-
>>   tests/test-hbitmap.c         | 32 ++++++++++++++++----------------
>>   util/hbitmap.c               | 13 ++++++++-----
>>   6 files changed, 34 insertions(+), 32 deletions(-)
> 
> [...]
> 
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index b6d4b99a06..df22f06be6 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -193,7 +193,7 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>>       }
>>   }
>>   
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
>> +int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
>>   {
>>       size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
>>       unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
>> @@ -202,6 +202,8 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
>>       uint64_t end_bit, sz;
>>       int64_t res;
>>   
>> +    assert(start >= 0 && count >= 0);
>> +
>>       if (start >= hb->orig_size || count == 0) {
>>           return -1;
>>       }
> As far as I can see, NBD just passes NBDRequest.from (which is a
> uint64_t) to this function (on NBD_CMD_BLOCK_STATUS).  Would this allow
> a malicious client to send a value > INT64_MAX, thus provoking an
> overflow and killing the server with this new assertion?


in nbd_co_receive_request() we have


     if (request->from > client->exp->size ||
         request->len > client->exp->size - request->from) {


So, we check that from is <= exp->size. and exp->size cant be greater than INT64_MAX,
as it derived from bdrv_getlength, which returns int64_t.



Interesting, should we be more strict in server:?

--- a/nbd/server.c
+++ b/nbd/server.c
@@ -2178,7 +2178,7 @@ static int nbd_co_receive_request(NBDRequestData *req, NBDRequest *request,
          error_setg(errp, "Export is read-only");
          return -EROFS;
      }
-    if (request->from > client->exp->size ||
+    if (request->from >= client->exp->size ||
          request->len > client->exp->size - request->from) {
          error_setg(errp, "operation past EOF; From: %" PRIu64 ", Len: %" PRIu32
                     ", Size: %" PRIu64, request->from, request->len,

Or is it intentional? Looking through NBD spec I found only

    client MUST NOT use a length ... or which, when added to offset, would exceed the export size.

So, formally pair offset=<export size>, len=0 is valid...

> 
> On second thought, we have this problem already everywhere in
> nbd_handle_request().  I don’t see it or its caller ever checking
> whether the received values are in bounds, it just passes them to all
> kind of block layer functions that sometimes even just accept plain
> ints.  Well, I suppose all other functions just error out, so it
> probably isn’t an actual problem in practice so far...
> 
> Max
> 


-- 
Best regards,
Vladimir

Re: [PATCH v3 05/10] block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 3612 bytes --]

On 20.01.20 13:28, Vladimir Sementsov-Ogievskiy wrote:
> 20.01.2020 14:59, Max Reitz wrote:
>> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>>> We are going to introduce bdrv_dirty_bitmap_next_dirty so that same
>>> variable may be used to store its return value and to be its parameter,
>>> so it would int64_t.
>>>
>>> Similarly, we are going to refactor hbitmap_next_dirty_area to use
>>> hbitmap_next_dirty together with hbitmap_next_zero, therefore we want
>>> hbitmap_next_zero parameter type to be int64_t too.
>>>
>>> So, for convenience update all parameters of *_next_zero and
>>> *_next_dirty_area to be int64_t.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>   include/block/dirty-bitmap.h |  6 +++---
>>>   include/qemu/hbitmap.h       |  7 +++----
>>>   block/dirty-bitmap.c         |  6 +++---
>>>   nbd/server.c                 |  2 +-
>>>   tests/test-hbitmap.c         | 32 ++++++++++++++++----------------
>>>   util/hbitmap.c               | 13 ++++++++-----
>>>   6 files changed, 34 insertions(+), 32 deletions(-)
>>
>> [...]
>>
>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>> index b6d4b99a06..df22f06be6 100644
>>> --- a/util/hbitmap.c
>>> +++ b/util/hbitmap.c
>>> @@ -193,7 +193,7 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>>>       }
>>>   }
>>>   
>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
>>> +int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
>>>   {
>>>       size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
>>>       unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
>>> @@ -202,6 +202,8 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
>>>       uint64_t end_bit, sz;
>>>       int64_t res;
>>>   
>>> +    assert(start >= 0 && count >= 0);
>>> +
>>>       if (start >= hb->orig_size || count == 0) {
>>>           return -1;
>>>       }
>> As far as I can see, NBD just passes NBDRequest.from (which is a
>> uint64_t) to this function (on NBD_CMD_BLOCK_STATUS).  Would this allow
>> a malicious client to send a value > INT64_MAX, thus provoking an
>> overflow and killing the server with this new assertion?
> 
> 
> in nbd_co_receive_request() we have
> 
> 
>      if (request->from > client->exp->size ||
>          request->len > client->exp->size - request->from) {
> 
> 
> So, we check that from is <= exp->size. and exp->size cant be greater than INT64_MAX,
> as it derived from bdrv_getlength, which returns int64_t.

Ah, OK, so I just overlooked that.

> Interesting, should we be more strict in server:?
> 
> --- a/nbd/server.c
> +++ b/nbd/server.c
> @@ -2178,7 +2178,7 @@ static int nbd_co_receive_request(NBDRequestData *req, NBDRequest *request,
>           error_setg(errp, "Export is read-only");
>           return -EROFS;
>       }
> -    if (request->from > client->exp->size ||
> +    if (request->from >= client->exp->size ||
>           request->len > client->exp->size - request->from) {
>           error_setg(errp, "operation past EOF; From: %" PRIu64 ", Len: %" PRIu32
>                      ", Size: %" PRIu64, request->from, request->len,
> 
> Or is it intentional? Looking through NBD spec I found only
> 
>     client MUST NOT use a length ... or which, when added to offset, would exceed the export size.
> 
> So, formally pair offset=<export size>, len=0 is valid...

Sounds valid, yes.

In any case:

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 05/10] block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t

[Eric Blake]

On 1/20/20 6:28 AM, Vladimir Sementsov-Ogievskiy wrote:

>> As far as I can see, NBD just passes NBDRequest.from (which is a
>> uint64_t) to this function (on NBD_CMD_BLOCK_STATUS).  Would this allow
>> a malicious client to send a value > INT64_MAX, thus provoking an
>> overflow and killing the server with this new assertion?
> 
> 
> in nbd_co_receive_request() we have
> 
> 
>       if (request->from > client->exp->size ||
>           request->len > client->exp->size - request->from) {
> 
> 
> So, we check that from is <= exp->size. and exp->size cant be greater than INT64_MAX,
> as it derived from bdrv_getlength, which returns int64_t.
> 
> 
> 
> Interesting, should we be more strict in server:?

I think we're okay based on the existing bounds checks.

> 
> --- a/nbd/server.c
> +++ b/nbd/server.c
> @@ -2178,7 +2178,7 @@ static int nbd_co_receive_request(NBDRequestData *req, NBDRequest *request,
>            error_setg(errp, "Export is read-only");
>            return -EROFS;
>        }
> -    if (request->from > client->exp->size ||
> +    if (request->from >= client->exp->size ||
>            request->len > client->exp->size - request->from) {
>            error_setg(errp, "operation past EOF; From: %" PRIu64 ", Len: %" PRIu32
>                       ", Size: %" PRIu64, request->from, request->len,
> 
> Or is it intentional? Looking through NBD spec I found only
> 
>      client MUST NOT use a length ... or which, when added to offset, would exceed the export size.
> 
> So, formally pair offset=<export size>, len=0 is valid...

Except that the spec also says that len=0 is generally unspecified 
behavior (whether it is a no-op, or means special handling, or whatever 
else, is up to the server, but clients shouldn't be sending it - thus a 
server that rejects it instead of handling it as a no-op is no worse for 
the wear).

> 
>>
>> On second thought, we have this problem already everywhere in
>> nbd_handle_request().  I don’t see it or its caller ever checking
>> whether the received values are in bounds, it just passes them to all
>> kind of block layer functions that sometimes even just accept plain
>> ints.  Well, I suppose all other functions just error out, so it
>> probably isn’t an actual problem in practice so far...
>>
>> Max
>>
> 
> 

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

[PATCH v3 06/10] block/dirty-bitmap: add _next_dirty API

[Vladimir Sementsov-Ogievskiy]

We have bdrv_dirty_bitmap_next_zero, let's add corresponding
bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than
bitmap iterators in some cases.

For test modify test_hbitmap_next_zero_check_range to check both
next_zero and next_dirty and add some new checks.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/block/dirty-bitmap.h |   2 +
 include/qemu/hbitmap.h       |  13 ++++
 block/dirty-bitmap.c         |   6 ++
 tests/test-hbitmap.c         | 130 ++++++++++++++++++++---------------
 util/hbitmap.c               |  60 ++++++++--------
 5 files changed, 126 insertions(+), 85 deletions(-)

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 27c72cc56a..b1f0de12db 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -105,6 +105,8 @@ for (bitmap = bdrv_dirty_bitmap_first(bs); bitmap; \
      bitmap = bdrv_dirty_bitmap_next(bitmap))
 
 char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
+int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offset,
+                                     int64_t bytes);
 int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset,
                                     int64_t bytes);
 bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index b6e85f3d5d..a4b032b270 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -297,6 +297,19 @@ void hbitmap_free(HBitmap *hb);
  */
 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 
+/*
+ * hbitmap_next_dirty:
+ *
+ * Find next dirty bit within selected range. If not found, return -1.
+ *
+ * @hb: The HBitmap to operate on
+ * @start: The bit to start from.
+ * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole
+ * bitmap is looked through. You can use UINT64_MAX as @count to search up to
+ * the bitmap end.
+ */
+int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count);
+
 /* hbitmap_next_zero:
  *
  * Find next not dirty bit within selected range. If not found, return -1.
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index af9f5411a6..1b14c8eb26 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -860,6 +860,12 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
     return hbitmap_sha256(bitmap->bitmap, errp);
 }
 
+int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offset,
+                                     int64_t bytes)
+{
+    return hbitmap_next_dirty(bitmap->bitmap, offset, bytes);
+}
+
 int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset,
                                     int64_t bytes)
 {
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 0e1e5c64dd..e3f1b3f361 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -816,92 +816,108 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
     hbitmap_iter_next(&hbi);
 }
 
-static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
-                                               uint64_t start,
-                                               uint64_t count)
+static void test_hbitmap_next_x_check_range(TestHBitmapData *data,
+                                            uint64_t start,
+                                            uint64_t count)
 {
-    int64_t ret1 = hbitmap_next_zero(data->hb, start, count);
-    int64_t ret2 = start;
+    int64_t next_zero = hbitmap_next_zero(data->hb, start, count);
+    int64_t next_dirty = hbitmap_next_dirty(data->hb, start, count);
+    int64_t next;
     int64_t end = start >= data->size || data->size - start < count ?
                 data->size : start + count;
+    bool first_bit = hbitmap_get(data->hb, start);
 
-    for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) {
+    for (next = start;
+         next < end && hbitmap_get(data->hb, next) == first_bit;
+         next++)
+    {
         ;
     }
-    if (ret2 == end) {
-        ret2 = -1;
+
+    if (next == end) {
+        next = -1;
     }
 
-    g_assert_cmpint(ret1, ==, ret2);
+    g_assert_cmpint(next_dirty, ==, first_bit ? start : next);
+    g_assert_cmpint(next_zero, ==, first_bit ? next : start);
 }
 
-static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+static void test_hbitmap_next_x_check(TestHBitmapData *data, int64_t start)
 {
-    test_hbitmap_next_zero_check_range(data, start, INT64_MAX);
+    test_hbitmap_next_x_check_range(data, start, INT64_MAX);
 }
 
-static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
+static void test_hbitmap_next_x_do(TestHBitmapData *data, int granularity)
 {
     hbitmap_test_init(data, L3, granularity);
-    test_hbitmap_next_zero_check(data, 0);
-    test_hbitmap_next_zero_check(data, L3 - 1);
-    test_hbitmap_next_zero_check_range(data, 0, 1);
-    test_hbitmap_next_zero_check_range(data, L3 - 1, 1);
+    test_hbitmap_next_x_check(data, 0);
+    test_hbitmap_next_x_check(data, L3 - 1);
+    test_hbitmap_next_x_check_range(data, 0, 1);
+    test_hbitmap_next_x_check_range(data, L3 - 1, 1);
 
     hbitmap_set(data->hb, L2, 1);
-    test_hbitmap_next_zero_check(data, 0);
-    test_hbitmap_next_zero_check(data, L2 - 1);
-    test_hbitmap_next_zero_check(data, L2);
-    test_hbitmap_next_zero_check(data, L2 + 1);
-    test_hbitmap_next_zero_check_range(data, 0, 1);
-    test_hbitmap_next_zero_check_range(data, 0, L2);
-    test_hbitmap_next_zero_check_range(data, L2 - 1, 1);
-    test_hbitmap_next_zero_check_range(data, L2 - 1, 2);
-    test_hbitmap_next_zero_check_range(data, L2, 1);
-    test_hbitmap_next_zero_check_range(data, L2 + 1, 1);
+    test_hbitmap_next_x_check(data, 0);
+    test_hbitmap_next_x_check(data, L2 - 1);
+    test_hbitmap_next_x_check(data, L2);
+    test_hbitmap_next_x_check(data, L2 + 1);
+    test_hbitmap_next_x_check_range(data, 0, 1);
+    test_hbitmap_next_x_check_range(data, 0, L2);
+    test_hbitmap_next_x_check_range(data, L2 - 1, 1);
+    test_hbitmap_next_x_check_range(data, L2 - 1, 2);
+    test_hbitmap_next_x_check_range(data, L2, 1);
+    test_hbitmap_next_x_check_range(data, L2 + 1, 1);
 
     hbitmap_set(data->hb, L2 + 5, L1);
-    test_hbitmap_next_zero_check(data, 0);
-    test_hbitmap_next_zero_check(data, L2 + 1);
-    test_hbitmap_next_zero_check(data, L2 + 2);
-    test_hbitmap_next_zero_check(data, L2 + 5);
-    test_hbitmap_next_zero_check(data, L2 + L1 - 1);
-    test_hbitmap_next_zero_check(data, L2 + L1);
-    test_hbitmap_next_zero_check_range(data, L2, 6);
-    test_hbitmap_next_zero_check_range(data, L2 + 1, 3);
-    test_hbitmap_next_zero_check_range(data, L2 + 4, L1);
-    test_hbitmap_next_zero_check_range(data, L2 + 5, L1);
+    test_hbitmap_next_x_check(data, 0);
+    test_hbitmap_next_x_check(data, L2 - L1);
+    test_hbitmap_next_x_check(data, L2 + 1);
+    test_hbitmap_next_x_check(data, L2 + 2);
+    test_hbitmap_next_x_check(data, L2 + 5);
+    test_hbitmap_next_x_check(data, L2 + L1 - 1);
+    test_hbitmap_next_x_check(data, L2 + L1);
+    test_hbitmap_next_x_check(data, L2 + L1 + 1);
+    test_hbitmap_next_x_check_range(data, L2 - 2, L1);
+    test_hbitmap_next_x_check_range(data, L2, 4);
+    test_hbitmap_next_x_check_range(data, L2, 6);
+    test_hbitmap_next_x_check_range(data, L2 + 1, 3);
+    test_hbitmap_next_x_check_range(data, L2 + 4, L1);
+    test_hbitmap_next_x_check_range(data, L2 + 5, L1);
+    test_hbitmap_next_x_check_range(data, L2 + 5 + L1 - 1, 1);
+    test_hbitmap_next_x_check_range(data, L2 + 5 + L1, 1);
+    test_hbitmap_next_x_check_range(data, L2 + 5 + L1 + 1, 1);
 
     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
-    test_hbitmap_next_zero_check(data, L2 * 2 - L1);
-    test_hbitmap_next_zero_check(data, L2 * 2 - 2);
-    test_hbitmap_next_zero_check(data, L2 * 2 - 1);
-    test_hbitmap_next_zero_check(data, L2 * 2);
-    test_hbitmap_next_zero_check(data, L3 - 1);
-    test_hbitmap_next_zero_check_range(data, L2 * 2 - L1, L1 + 1);
-    test_hbitmap_next_zero_check_range(data, L2 * 2, L2);
+    test_hbitmap_next_x_check(data, L2 * 2 - L1);
+    test_hbitmap_next_x_check(data, L2 * 2 - 2);
+    test_hbitmap_next_x_check(data, L2 * 2 - 1);
+    test_hbitmap_next_x_check(data, L2 * 2);
+    test_hbitmap_next_x_check(data, L2 * 2 + 1);
+    test_hbitmap_next_x_check(data, L2 * 2 + L1);
+    test_hbitmap_next_x_check(data, L3 - 1);
+    test_hbitmap_next_x_check_range(data, L2 * 2 - L1, L1 + 1);
+    test_hbitmap_next_x_check_range(data, L2 * 2, L2);
 
     hbitmap_set(data->hb, 0, L3);
-    test_hbitmap_next_zero_check(data, 0);
+    test_hbitmap_next_x_check(data, 0);
 }
 
-static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *unused)
+static void test_hbitmap_next_x_0(TestHBitmapData *data, const void *unused)
 {
-    test_hbitmap_next_zero_do(data, 0);
+    test_hbitmap_next_x_do(data, 0);
 }
 
-static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
+static void test_hbitmap_next_x_4(TestHBitmapData *data, const void *unused)
 {
-    test_hbitmap_next_zero_do(data, 4);
+    test_hbitmap_next_x_do(data, 4);
 }
 
-static void test_hbitmap_next_zero_after_truncate(TestHBitmapData *data,
-                                                  const void *unused)
+static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data,
+                                               const void *unused)
 {
     hbitmap_test_init(data, L1, 0);
     hbitmap_test_truncate_impl(data, L1 * 2);
     hbitmap_set(data->hb, 0, L1);
-    test_hbitmap_next_zero_check(data, 0);
+    test_hbitmap_next_x_check(data, 0);
 }
 
 static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
@@ -1068,12 +1084,12 @@ int main(int argc, char **argv)
     hbitmap_test_add("/hbitmap/iter/iter_and_reset",
                      test_hbitmap_iter_and_reset);
 
-    hbitmap_test_add("/hbitmap/next_zero/next_zero_0",
-                     test_hbitmap_next_zero_0);
-    hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
-                     test_hbitmap_next_zero_4);
-    hbitmap_test_add("/hbitmap/next_zero/next_zero_after_truncate",
-                     test_hbitmap_next_zero_after_truncate);
+    hbitmap_test_add("/hbitmap/next_zero/next_x_0",
+                     test_hbitmap_next_x_0);
+    hbitmap_test_add("/hbitmap/next_zero/next_x_4",
+                     test_hbitmap_next_x_4);
+    hbitmap_test_add("/hbitmap/next_zero/next_x_after_truncate",
+                     test_hbitmap_next_x_after_truncate);
 
     hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0",
                      test_hbitmap_next_dirty_area_0);
diff --git a/util/hbitmap.c b/util/hbitmap.c
index df22f06be6..d23f4b9678 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -193,6 +193,30 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
     }
 }
 
+int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count)
+{
+    HBitmapIter hbi;
+    int64_t firt_dirty_off;
+    uint64_t end;
+
+    assert(start >= 0 && count >= 0);
+
+    if (start >= hb->orig_size || count == 0) {
+        return -1;
+    }
+
+    end = count > hb->orig_size - start ? hb->orig_size : start + count;
+
+    hbitmap_iter_init(&hbi, hb, start);
+    firt_dirty_off = hbitmap_iter_next(&hbi);
+
+    if (firt_dirty_off < 0 || firt_dirty_off >= end) {
+        return -1;
+    }
+
+    return MAX(start, firt_dirty_off);
+}
+
 int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
 {
     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
@@ -248,40 +272,20 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
 
 bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count)
 {
-    HBitmapIter hbi;
-    int64_t firt_dirty_off, area_end;
-    uint32_t granularity = 1UL << hb->granularity;
-    uint64_t end;
-
-    assert(*start >= 0 && *count >= 0);
-
-    if (*start >= hb->orig_size || *count == 0) {
-        return false;
-    }
-
-    end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count;
-
-    hbitmap_iter_init(&hbi, hb, *start);
-    firt_dirty_off = hbitmap_iter_next(&hbi);
+    int64_t area_start, area_end;
 
-    if (firt_dirty_off < 0 || firt_dirty_off >= end) {
+    area_start = hbitmap_next_dirty(hb, *start, *count);
+    if (area_start < 0) {
         return false;
     }
 
-    if (firt_dirty_off + granularity >= end) {
-        area_end = end;
-    } else {
-        area_end = hbitmap_next_zero(hb, firt_dirty_off + granularity,
-                                     end - firt_dirty_off - granularity);
-        if (area_end < 0) {
-            area_end = end;
-        }
+    area_end = hbitmap_next_zero(hb, area_start, *start + *count - area_start);
+    if (area_end < 0) {
+        area_end = MIN(hb->orig_size, *start + *count);
     }
 
-    if (firt_dirty_off > *start) {
-        *start = firt_dirty_off;
-    }
-    *count = area_end - *start;
+    *start = area_start;
+    *count = area_end - area_start;
 
     return true;
 }
-- 
2.21.0

Re: [PATCH v3 06/10] block/dirty-bitmap: add _next_dirty API

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 3408 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> We have bdrv_dirty_bitmap_next_zero, let's add corresponding
> bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than
> bitmap iterators in some cases.
> 
> For test modify test_hbitmap_next_zero_check_range to check both
> next_zero and next_dirty and add some new checks.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/block/dirty-bitmap.h |   2 +
>  include/qemu/hbitmap.h       |  13 ++++
>  block/dirty-bitmap.c         |   6 ++
>  tests/test-hbitmap.c         | 130 ++++++++++++++++++++---------------
>  util/hbitmap.c               |  60 ++++++++--------
>  5 files changed, 126 insertions(+), 85 deletions(-)

[...]

> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index b6e85f3d5d..a4b032b270 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -297,6 +297,19 @@ void hbitmap_free(HBitmap *hb);
>   */
>  void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>  
> +/*
> + * hbitmap_next_dirty:
> + *
> + * Find next dirty bit within selected range. If not found, return -1.
> + *
> + * @hb: The HBitmap to operate on
> + * @start: The bit to start from.
> + * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole
> + * bitmap is looked through. You can use UINT64_MAX as @count to search up to

I would’ve said s/looked through/scanned/, but it matches
hbitmap_next_zero()’s documentation, so it’s fine.

But definitely s/UINT64_MAX/INT64_MAX/.

> + * the bitmap end.
> + */
> +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count);
> +
>  /* hbitmap_next_zero:
>   *
>   * Find next not dirty bit within selected range. If not found, return -1.

[...]

> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 0e1e5c64dd..e3f1b3f361 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -816,92 +816,108 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>      hbitmap_iter_next(&hbi);
>  }
>  
> -static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
> -                                               uint64_t start,
> -                                               uint64_t count)
> +static void test_hbitmap_next_x_check_range(TestHBitmapData *data,
> +                                            uint64_t start,
> +                                            uint64_t count)

Why not change the parameters to be signed while we’re already here?

[...]

> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index df22f06be6..d23f4b9678 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -193,6 +193,30 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>      }
>  }
>  
> +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count)
> +{
> +    HBitmapIter hbi;
> +    int64_t firt_dirty_off;

Pre-existing, but isn’t this just a typo that you could fix here?  (i.e.
s/firt/first/)

Apart from this minor things:

Reviewed-by: Max Reitz <mreitz@redhat.com>

> +    uint64_t end;
> +
> +    assert(start >= 0 && count >= 0);
> +
> +    if (start >= hb->orig_size || count == 0) {
> +        return -1;
> +    }
> +
> +    end = count > hb->orig_size - start ? 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 06/10] block/dirty-bitmap: add _next_dirty API

[Vladimir Sementsov-Ogievskiy]

20.01.2020 16:14, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> We have bdrv_dirty_bitmap_next_zero, let's add corresponding
>> bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than
>> bitmap iterators in some cases.
>>
>> For test modify test_hbitmap_next_zero_check_range to check both
>> next_zero and next_dirty and add some new checks.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/block/dirty-bitmap.h |   2 +
>>   include/qemu/hbitmap.h       |  13 ++++
>>   block/dirty-bitmap.c         |   6 ++
>>   tests/test-hbitmap.c         | 130 ++++++++++++++++++++---------------
>>   util/hbitmap.c               |  60 ++++++++--------
>>   5 files changed, 126 insertions(+), 85 deletions(-)
> 
> [...]
> 
>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>> index b6e85f3d5d..a4b032b270 100644
>> --- a/include/qemu/hbitmap.h
>> +++ b/include/qemu/hbitmap.h
>> @@ -297,6 +297,19 @@ void hbitmap_free(HBitmap *hb);
>>    */
>>   void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>>   
>> +/*
>> + * hbitmap_next_dirty:
>> + *
>> + * Find next dirty bit within selected range. If not found, return -1.
>> + *
>> + * @hb: The HBitmap to operate on
>> + * @start: The bit to start from.
>> + * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole
>> + * bitmap is looked through. You can use UINT64_MAX as @count to search up to
> 
> I would’ve said s/looked through/scanned/, but it matches
> hbitmap_next_zero()’s documentation, so it’s fine.
> 
> But definitely s/UINT64_MAX/INT64_MAX/.
> 
>> + * the bitmap end.
>> + */
>> +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count);
>> +
>>   /* hbitmap_next_zero:
>>    *
>>    * Find next not dirty bit within selected range. If not found, return -1.
> 
> [...]
> 
>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>> index 0e1e5c64dd..e3f1b3f361 100644
>> --- a/tests/test-hbitmap.c
>> +++ b/tests/test-hbitmap.c
>> @@ -816,92 +816,108 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>>       hbitmap_iter_next(&hbi);
>>   }
>>   
>> -static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
>> -                                               uint64_t start,
>> -                                               uint64_t count)
>> +static void test_hbitmap_next_x_check_range(TestHBitmapData *data,
>> +                                            uint64_t start,
>> +                                            uint64_t count)
> 
> Why not change the parameters to be signed while we’re already here?
> 
> [...]
> 
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index df22f06be6..d23f4b9678 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -193,6 +193,30 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>>       }
>>   }
>>   
>> +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count)
>> +{
>> +    HBitmapIter hbi;
>> +    int64_t firt_dirty_off;
> 
> Pre-existing, but isn’t this just a typo that you could fix here?  (i.e.
> s/firt/first/)
> 
> Apart from this minor things:

Agree with them.

> 
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> 
>> +    uint64_t end;
>> +
>> +    assert(start >= 0 && count >= 0);
>> +
>> +    if (start >= hb->orig_size || count == 0) {
>> +        return -1;
>> +    }
>> +
>> +    end = count > hb->orig_size - start ?
> 


-- 
Best regards,
Vladimir

Re: [PATCH v3 06/10] block/dirty-bitmap: add _next_dirty API

[Vladimir Sementsov-Ogievskiy]

20.01.2020 19:30, Vladimir Sementsov-Ogievskiy wrote:
> 20.01.2020 16:14, Max Reitz wrote:
>> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>>> We have bdrv_dirty_bitmap_next_zero, let's add corresponding
>>> bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than
>>> bitmap iterators in some cases.
>>>
>>> For test modify test_hbitmap_next_zero_check_range to check both
>>> next_zero and next_dirty and add some new checks.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>   include/block/dirty-bitmap.h |   2 +
>>>   include/qemu/hbitmap.h       |  13 ++++
>>>   block/dirty-bitmap.c         |   6 ++
>>>   tests/test-hbitmap.c         | 130 ++++++++++++++++++++---------------
>>>   util/hbitmap.c               |  60 ++++++++--------
>>>   5 files changed, 126 insertions(+), 85 deletions(-)
>>
>> [...]
>>
>>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>>> index b6e85f3d5d..a4b032b270 100644
>>> --- a/include/qemu/hbitmap.h
>>> +++ b/include/qemu/hbitmap.h
>>> @@ -297,6 +297,19 @@ void hbitmap_free(HBitmap *hb);
>>>    */
>>>   void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>>> +/*
>>> + * hbitmap_next_dirty:
>>> + *
>>> + * Find next dirty bit within selected range. If not found, return -1.
>>> + *
>>> + * @hb: The HBitmap to operate on
>>> + * @start: The bit to start from.
>>> + * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole
>>> + * bitmap is looked through. You can use UINT64_MAX as @count to search up to
>>
>> I would’ve said s/looked through/scanned/, but it matches
>> hbitmap_next_zero()’s documentation, so it’s fine.
>>
>> But definitely s/UINT64_MAX/INT64_MAX/.
>>
>>> + * the bitmap end.
>>> + */
>>> +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count);
>>> +
>>>   /* hbitmap_next_zero:
>>>    *
>>>    * Find next not dirty bit within selected range. If not found, return -1.
>>
>> [...]
>>
>>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>>> index 0e1e5c64dd..e3f1b3f361 100644
>>> --- a/tests/test-hbitmap.c
>>> +++ b/tests/test-hbitmap.c
>>> @@ -816,92 +816,108 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>>>       hbitmap_iter_next(&hbi);
>>>   }
>>> -static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
>>> -                                               uint64_t start,
>>> -                                               uint64_t count)
>>> +static void test_hbitmap_next_x_check_range(TestHBitmapData *data,
>>> +                                            uint64_t start,
>>> +                                            uint64_t count)
>>
>> Why not change the parameters to be signed while we’re already here?

Now I think that better to do it in previous patch.

>>
>> [...]
>>
>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>> index df22f06be6..d23f4b9678 100644
>>> --- a/util/hbitmap.c
>>> +++ b/util/hbitmap.c
>>> @@ -193,6 +193,30 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>>>       }
>>>   }
>>> +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count)
>>> +{
>>> +    HBitmapIter hbi;
>>> +    int64_t firt_dirty_off;
>>
>> Pre-existing, but isn’t this just a typo that you could fix here?  (i.e.
>> s/firt/first/)
>>
>> Apart from this minor things:
> 
> Agree with them.
> 
>>
>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>>
>>> +    uint64_t end;
>>> +
>>> +    assert(start >= 0 && count >= 0);
>>> +
>>> +    if (start >= hb->orig_size || count == 0) {
>>> +        return -1;
>>> +    }
>>> +
>>> +    end = count > hb->orig_size - start ?
>>
> 
> 


-- 
Best regards,
Vladimir

[PATCH v3 07/10] block/dirty-bitmap: improve _next_dirty_area API

[Vladimir Sementsov-Ogievskiy]

Firstly, _next_dirty_area is for scenarios when we may contiguously
search for next dirty area inside some limited region, so it is more
comfortable to specify "end" which should not be recalculated on each
iteration.

Secondly, let's add a possibility to limit resulting area size, not
limiting searching area. This will be used in NBD code in further
commit. (Note that now bdrv_dirty_bitmap_next_dirty_area is unused)

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/block/dirty-bitmap.h |  3 ++-
 include/qemu/hbitmap.h       | 25 ++++++++++++---------
 block/dirty-bitmap.c         |  6 +++--
 tests/test-hbitmap.c         | 43 +++++++++++++++++++++++-------------
 util/hbitmap.c               | 41 +++++++++++++++++++++-------------
 5 files changed, 74 insertions(+), 44 deletions(-)

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index b1f0de12db..8a10029418 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -110,7 +110,8 @@ int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offset,
 int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset,
                                     int64_t bytes);
 bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
-                                       int64_t *offset, int64_t *bytes);
+        int64_t start, int64_t end, int64_t max_dirty_count,
+        int64_t *dirty_start, int64_t *dirty_count);
 BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
                                                   Error **errp);
 
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index a4b032b270..4e7a6e72ef 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -324,18 +324,21 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count);
 
 /* hbitmap_next_dirty_area:
  * @hb: The HBitmap to operate on
- * @start: in-out parameter.
- *         in: the offset to start from
- *         out: (if area found) start of found area
- * @count: in-out parameter.
- *         in: length of requested region
- *         out: length of found area
- *
- * If dirty area found within [@start, @start + @count), returns true and sets
- * @offset and @bytes appropriately. Otherwise returns false and leaves @offset
- * and @bytes unchanged.
+ * @start: the offset to start from
+ * @end: end of requested area
+ * @max_dirty_count: limit for out parameter dirty_count
+ * @dirty_start: on success: start of found area
+ * @dirty_count: on success: length of found area
+ *
+ * If dirty area found within [@start, @end), returns true and sets
+ * @dirty_start and @dirty_count appropriately. @dirty_count will not exceed
+ * @max_dirty_count.
+ * If dirty area was not found, returns false and leaves @dirty_start and
+ * @dirty_count unchanged.
  */
-bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count);
+bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end,
+                             int64_t max_dirty_count,
+                             int64_t *dirty_start, int64_t *dirty_count);
 
 /**
  * hbitmap_iter_next:
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 1b14c8eb26..063793e316 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -873,9 +873,11 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset,
 }
 
 bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
-                                       int64_t *offset, int64_t *bytes)
+        int64_t start, int64_t end, int64_t max_dirty_count,
+        int64_t *dirty_start, int64_t *dirty_count)
 {
-    return hbitmap_next_dirty_area(bitmap->bitmap, offset, bytes);
+    return hbitmap_next_dirty_area(bitmap->bitmap, start, end, max_dirty_count,
+                                   dirty_start, dirty_count);
 }
 
 /**
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index e3f1b3f361..d75e84a76a 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -920,18 +920,19 @@ static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data,
     test_hbitmap_next_x_check(data, 0);
 }
 
-static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
-                                               int64_t offset,
-                                               int64_t count)
+static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *data,
+                                                       int64_t offset,
+                                                       int64_t count,
+                                                       int64_t max_dirty)
 {
     int64_t off1, off2;
     int64_t len1 = 0, len2;
     bool ret1, ret2;
     int64_t end;
 
-    off1 = offset;
-    len1 = count;
-    ret1 = hbitmap_next_dirty_area(data->hb, &off1, &len1);
+    ret1 = hbitmap_next_dirty_area(data->hb,
+            offset, count == INT64_MAX ? INT64_MAX : offset + count, max_dirty,
+            &off1, &len1);
 
     end = offset > data->size || data->size - offset < count ? data->size :
                                                                offset + count;
@@ -940,21 +941,25 @@ static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
         ;
     }
 
-    for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
-         len2++) {
+    for (len2 = 1; (off2 + len2 < end && len2 < max_dirty &&
+                    hbitmap_get(data->hb, off2 + len2)); len2++)
+    {
         ;
     }
 
     ret2 = off2 < end;
-    if (!ret2) {
-        /* leave unchanged */
-        off2 = offset;
-        len2 = count;
+    g_assert_cmpint(ret1, ==, ret2);
+
+    if (ret2) {
+        g_assert_cmpint(off1, ==, off2);
+        g_assert_cmpint(len1, ==, len2);
     }
+}
 
-    g_assert_cmpint(ret1, ==, ret2);
-    g_assert_cmpint(off1, ==, off2);
-    g_assert_cmpint(len1, ==, len2);
+static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
+                                               int64_t offset, int64_t count)
+{
+    test_hbitmap_next_dirty_area_check_limited(data, offset, count, INT64_MAX);
 }
 
 static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
@@ -964,6 +969,7 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
     test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, 0, 1);
     test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
+    test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1);
 
     hbitmap_set(data->hb, L2, 1);
     test_hbitmap_next_dirty_area_check(data, 0, 1);
@@ -976,6 +982,8 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
     test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX);
     test_hbitmap_next_dirty_area_check(data, L2, 1);
     test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
+    test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1);
+    test_hbitmap_next_dirty_area_check_limited(data, L2 - 1, 2, 1);
 
     hbitmap_set(data->hb, L2 + 5, L1);
     test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
@@ -988,6 +996,8 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
     test_hbitmap_next_dirty_area_check(data, L2 + L1, L1);
     test_hbitmap_next_dirty_area_check(data, L2, 0);
     test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
+    test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, INT64_MAX, 3);
+    test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, 7, 10);
 
     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
     test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
@@ -997,6 +1007,9 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
     test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
     test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
     test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
+    test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, INT64_MAX, 5);
+    test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 10, 5);
+    test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 2, 5);
 
     hbitmap_set(data->hb, 0, L3);
     test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
diff --git a/util/hbitmap.c b/util/hbitmap.c
index d23f4b9678..2a1661ec1d 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -270,22 +270,34 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
     return res;
 }
 
-bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count)
+bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end,
+                             int64_t max_dirty_count,
+                             int64_t *dirty_start, int64_t *dirty_count)
 {
-    int64_t area_start, area_end;
+    int64_t next_zero;
 
-    area_start = hbitmap_next_dirty(hb, *start, *count);
-    if (area_start < 0) {
+    assert(start >= 0 && end >= 0 && max_dirty_count > 0);
+
+    if (start >= hb->orig_size || end <= start) {
+        return false;
+    }
+
+    end = MIN(end, hb->orig_size);
+
+    start = hbitmap_next_dirty(hb, start, end - start);
+    if (start < 0) {
         return false;
     }
 
-    area_end = hbitmap_next_zero(hb, area_start, *start + *count - area_start);
-    if (area_end < 0) {
-        area_end = MIN(hb->orig_size, *start + *count);
+    end = start + MIN(end - start, max_dirty_count);
+
+    next_zero = hbitmap_next_zero(hb, start, end - start);
+    if (next_zero >= 0) {
+        end = next_zero;
     }
 
-    *start = area_start;
-    *count = area_end - area_start;
+    *dirty_start = start;
+    *dirty_count = end - start;
 
     return true;
 }
@@ -844,13 +856,12 @@ static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
     int64_t offset = 0;
     int64_t count = src->orig_size;
 
-    while (hbitmap_next_dirty_area(src, &offset, &count)) {
+    for (offset = 0;
+         hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,
+                                 &offset, &count);
+         offset += count)
+    {
         hbitmap_set(dst, offset, count);
-        offset += count;
-        if (offset >= src->orig_size) {
-            break;
-        }
-        count = src->orig_size - offset;
     }
 }
 
-- 
2.21.0

Re: [PATCH v3 07/10] block/dirty-bitmap: improve _next_dirty_area API

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 4935 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> Firstly, _next_dirty_area is for scenarios when we may contiguously
> search for next dirty area inside some limited region, so it is more
> comfortable to specify "end" which should not be recalculated on each
> iteration.
> 
> Secondly, let's add a possibility to limit resulting area size, not
> limiting searching area. This will be used in NBD code in further
> commit. (Note that now bdrv_dirty_bitmap_next_dirty_area is unused)
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/block/dirty-bitmap.h |  3 ++-
>  include/qemu/hbitmap.h       | 25 ++++++++++++---------
>  block/dirty-bitmap.c         |  6 +++--
>  tests/test-hbitmap.c         | 43 +++++++++++++++++++++++-------------
>  util/hbitmap.c               | 41 +++++++++++++++++++++-------------
>  5 files changed, 74 insertions(+), 44 deletions(-)

[...]

>  /**
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index e3f1b3f361..d75e84a76a 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -920,18 +920,19 @@ static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data,
>      test_hbitmap_next_x_check(data, 0);
>  }
>  
> -static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
> -                                               int64_t offset,
> -                                               int64_t count)
> +static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *data,
> +                                                       int64_t offset,
> +                                                       int64_t count,
> +                                                       int64_t max_dirty)
>  {
>      int64_t off1, off2;
>      int64_t len1 = 0, len2;
>      bool ret1, ret2;
>      int64_t end;
>  
> -    off1 = offset;
> -    len1 = count;
> -    ret1 = hbitmap_next_dirty_area(data->hb, &off1, &len1);
> +    ret1 = hbitmap_next_dirty_area(data->hb,
> +            offset, count == INT64_MAX ? INT64_MAX : offset + count, max_dirty,
> +            &off1, &len1);
>  
>      end = offset > data->size || data->size - offset < count ? data->size :
>                                                                 offset + count;
> @@ -940,21 +941,25 @@ static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
>          ;

These empty statements look a bit weird to me.  But they’re
pre-existing, obviously.

>      }
>  
> -    for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
> -         len2++) {
> +    for (len2 = 1; (off2 + len2 < end && len2 < max_dirty &&
> +                    hbitmap_get(data->hb, off2 + len2)); len2++)
> +    {
>          ;
>      }

[...]

> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index d23f4b9678..2a1661ec1d 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -270,22 +270,34 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
>      return res;
>  }
>  
> -bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count)
> +bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end,
> +                             int64_t max_dirty_count,
> +                             int64_t *dirty_start, int64_t *dirty_count)
>  {
> -    int64_t area_start, area_end;
> +    int64_t next_zero;
>  
> -    area_start = hbitmap_next_dirty(hb, *start, *count);
> -    if (area_start < 0) {
> +    assert(start >= 0 && end >= 0 && max_dirty_count > 0);
> +
> +    if (start >= hb->orig_size || end <= start) {
> +        return false;
> +    }
> +
> +    end = MIN(end, hb->orig_size);

You could put this assignment before the if () and then drop the “start”
check from the condition.  (But that’s mostly me itching to do
optimizations.  I don’t think it’d make the code easier to read.)

[...]

> @@ -844,13 +856,12 @@ static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
>      int64_t offset = 0;
>      int64_t count = src->orig_size;

These initializations are now unnecessary.  I’d drop them because I find
at least the one for @count a tiny bit confusing now.  (Because as a
reader, I’d wonder where this value is used.)

With that done (or maybe not because you disagree):

Reviewed-by: Max Reitz <mreitz@redhat.com>

>  
> -    while (hbitmap_next_dirty_area(src, &offset, &count)) {
> +    for (offset = 0;
> +         hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,
> +                                 &offset, &count);
> +         offset += count)
> +    {
>          hbitmap_set(dst, offset, count);
> -        offset += count;
> -        if (offset >= src->orig_size) {
> -            break;
> -        }
> -        count = src->orig_size - offset;
>      }
>  }
>  
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 07/10] block/dirty-bitmap: improve _next_dirty_area API

[Vladimir Sementsov-Ogievskiy]

20.01.2020 16:58, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> Firstly, _next_dirty_area is for scenarios when we may contiguously
>> search for next dirty area inside some limited region, so it is more
>> comfortable to specify "end" which should not be recalculated on each
>> iteration.
>>
>> Secondly, let's add a possibility to limit resulting area size, not
>> limiting searching area. This will be used in NBD code in further
>> commit. (Note that now bdrv_dirty_bitmap_next_dirty_area is unused)
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/block/dirty-bitmap.h |  3 ++-
>>   include/qemu/hbitmap.h       | 25 ++++++++++++---------
>>   block/dirty-bitmap.c         |  6 +++--
>>   tests/test-hbitmap.c         | 43 +++++++++++++++++++++++-------------
>>   util/hbitmap.c               | 41 +++++++++++++++++++++-------------
>>   5 files changed, 74 insertions(+), 44 deletions(-)
> 
> [...]
> 
>>   /**
>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>> index e3f1b3f361..d75e84a76a 100644
>> --- a/tests/test-hbitmap.c
>> +++ b/tests/test-hbitmap.c
>> @@ -920,18 +920,19 @@ static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data,
>>       test_hbitmap_next_x_check(data, 0);
>>   }
>>   
>> -static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
>> -                                               int64_t offset,
>> -                                               int64_t count)
>> +static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *data,
>> +                                                       int64_t offset,
>> +                                                       int64_t count,
>> +                                                       int64_t max_dirty)
>>   {
>>       int64_t off1, off2;
>>       int64_t len1 = 0, len2;
>>       bool ret1, ret2;
>>       int64_t end;
>>   
>> -    off1 = offset;
>> -    len1 = count;
>> -    ret1 = hbitmap_next_dirty_area(data->hb, &off1, &len1);
>> +    ret1 = hbitmap_next_dirty_area(data->hb,
>> +            offset, count == INT64_MAX ? INT64_MAX : offset + count, max_dirty,
>> +            &off1, &len1);
>>   
>>       end = offset > data->size || data->size - offset < count ? data->size :
>>                                                                  offset + count;
>> @@ -940,21 +941,25 @@ static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
>>           ;
> 
> These empty statements look a bit weird to me.  But they’re
> pre-existing, obviously.
> 
>>       }
>>   
>> -    for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
>> -         len2++) {
>> +    for (len2 = 1; (off2 + len2 < end && len2 < max_dirty &&
>> +                    hbitmap_get(data->hb, off2 + len2)); len2++)
>> +    {
>>           ;
>>       }
> 
> [...]
> 
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index d23f4b9678..2a1661ec1d 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -270,22 +270,34 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
>>       return res;
>>   }
>>   
>> -bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count)
>> +bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end,
>> +                             int64_t max_dirty_count,
>> +                             int64_t *dirty_start, int64_t *dirty_count)
>>   {
>> -    int64_t area_start, area_end;
>> +    int64_t next_zero;
>>   
>> -    area_start = hbitmap_next_dirty(hb, *start, *count);
>> -    if (area_start < 0) {
>> +    assert(start >= 0 && end >= 0 && max_dirty_count > 0);
>> +
>> +    if (start >= hb->orig_size || end <= start) {
>> +        return false;
>> +    }
>> +
>> +    end = MIN(end, hb->orig_size);
> 
> You could put this assignment before the if () and then drop the “start”
> check from the condition.  (But that’s mostly me itching to do
> optimizations.  I don’t think it’d make the code easier to read.)
> 
> [...]
> 
>> @@ -844,13 +856,12 @@ static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
>>       int64_t offset = 0;
>>       int64_t count = src->orig_size;
> 
> These initializations are now unnecessary.  I’d drop them because I find
> at least the one for @count a tiny bit confusing now.  (Because as a
> reader, I’d wonder where this value is used.)
> 
> With that done (or maybe not because you disagree):


I agree)

> 
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> 
>>   
>> -    while (hbitmap_next_dirty_area(src, &offset, &count)) {
>> +    for (offset = 0;
>> +         hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,
>> +                                 &offset, &count);
>> +         offset += count)
>> +    {
>>           hbitmap_set(dst, offset, count);
>> -        offset += count;
>> -        if (offset >= src->orig_size) {
>> -            break;
>> -        }
>> -        count = src->orig_size - offset;
>>       }
>>   }
>>   
>>
> 


-- 
Best regards,
Vladimir

[PATCH v3 08/10] nbd/server: introduce NBDExtentArray

[Vladimir Sementsov-Ogievskiy]

Introduce NBDExtentArray class, to handle extents list creation in more
controlled way and with less OUT parameters in functions.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 nbd/server.c | 201 ++++++++++++++++++++++++++++-----------------------
 1 file changed, 109 insertions(+), 92 deletions(-)

diff --git a/nbd/server.c b/nbd/server.c
index a4b348eb32..cc722adc31 100644
--- a/nbd/server.c
+++ b/nbd/server.c
@@ -1909,27 +1909,89 @@ static int coroutine_fn nbd_co_send_sparse_read(NBDClient *client,
     return ret;
 }
 
+typedef struct NBDExtentArray {
+    NBDExtent *extents;
+    unsigned int nb_alloc;
+    unsigned int count;
+    uint64_t total_length;
+    bool converted; /* extents are converted to BE, no more changes allowed */
+} NBDExtentArray;
+
+static NBDExtentArray *nbd_extent_array_new(unsigned int nb_alloc)
+{
+    NBDExtentArray *ea = g_new0(NBDExtentArray, 1);
+
+    ea->nb_alloc = nb_alloc;
+    ea->extents = g_new(NBDExtent, nb_alloc);
+
+    return ea;
+}
+
+static void nbd_extent_array_free(NBDExtentArray *ea)
+{
+    g_free(ea->extents);
+    g_free(ea);
+}
+G_DEFINE_AUTOPTR_CLEANUP_FUNC(NBDExtentArray, nbd_extent_array_free);
+
+/* Further modifications of the array after conversion are abandoned */
+static void nbd_extent_array_convert_to_be(NBDExtentArray *ea)
+{
+    int i;
+
+    if (ea->converted) {
+        return;
+    }
+    ea->converted = true;
+
+    for (i = 0; i < ea->count; i++) {
+        ea->extents[i].flags = cpu_to_be32(ea->extents[i].flags);
+        ea->extents[i].length = cpu_to_be32(ea->extents[i].length);
+    }
+}
+
 /*
- * Populate @extents from block status. Update @bytes to be the actual
- * length encoded (which may be smaller than the original), and update
- * @nb_extents to the number of extents used.
- *
- * Returns zero on success and -errno on bdrv_block_status_above failure.
+ * Add extent to NBDExtentArray. If extent can't be added (no available space),
+ * return -1.
+ * For safety, when returning -1 for the first time, the array is converted
+ * to BE and further modifications are abandoned.
  */
-static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
-                                  uint64_t *bytes, NBDExtent *extents,
-                                  unsigned int *nb_extents)
+static int nbd_extent_array_add(NBDExtentArray *ea,
+                                uint32_t length, uint32_t flags)
 {
-    uint64_t remaining_bytes = *bytes;
-    NBDExtent *extent = extents, *extents_end = extents + *nb_extents;
-    bool first_extent = true;
+    assert(!ea->converted);
+
+    if (!length) {
+        return 0;
+    }
+
+    /* Extend previous extent if flags are the same */
+    if (ea->count > 0 && flags == ea->extents[ea->count - 1].flags) {
+        ea->extents[ea->count - 1].length += length;
+        ea->total_length += length;
+        return 0;
+    }
+
+    if (ea->count >= ea->nb_alloc) {
+        nbd_extent_array_convert_to_be(ea);
+        return -1;
+    }
+
+    ea->total_length += length;
+    ea->extents[ea->count] = (NBDExtent) {.length = length, .flags = flags};
+    ea->count++;
 
-    assert(*nb_extents);
-    while (remaining_bytes) {
+    return 0;
+}
+
+static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
+                                  uint64_t bytes, NBDExtentArray *ea)
+{
+    while (bytes) {
         uint32_t flags;
         int64_t num;
-        int ret = bdrv_block_status_above(bs, NULL, offset, remaining_bytes,
-                                          &num, NULL, NULL);
+        int ret = bdrv_block_status_above(bs, NULL, offset, bytes, &num,
+                                          NULL, NULL);
 
         if (ret < 0) {
             return ret;
@@ -1938,60 +2000,37 @@ static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
         flags = (ret & BDRV_BLOCK_ALLOCATED ? 0 : NBD_STATE_HOLE) |
                 (ret & BDRV_BLOCK_ZERO      ? NBD_STATE_ZERO : 0);
 
-        if (first_extent) {
-            extent->flags = flags;
-            extent->length = num;
-            first_extent = false;
-        } else if (flags == extent->flags) {
-            /* extend current extent */
-            extent->length += num;
-        } else {
-            if (extent + 1 == extents_end) {
-                break;
-            }
-
-            /* start new extent */
-            extent++;
-            extent->flags = flags;
-            extent->length = num;
+        if (nbd_extent_array_add(ea, num, flags) < 0) {
+            return 0;
         }
-        offset += num;
-        remaining_bytes -= num;
-    }
-
-    extents_end = extent + 1;
 
-    for (extent = extents; extent < extents_end; extent++) {
-        extent->flags = cpu_to_be32(extent->flags);
-        extent->length = cpu_to_be32(extent->length);
+        offset += num;
+        bytes -= num;
     }
 
-    *bytes -= remaining_bytes;
-    *nb_extents = extents_end - extents;
-
     return 0;
 }
 
-/* nbd_co_send_extents
+/*
+ * nbd_co_send_extents
  *
- * @length is only for tracing purposes (and may be smaller or larger
- * than the client's original request). @last controls whether
- * NBD_REPLY_FLAG_DONE is sent. @extents should already be in
- * big-endian format.
+ * @ea is converted to BE by the function
+ * @last controls whether NBD_REPLY_FLAG_DONE is sent.
  */
 static int nbd_co_send_extents(NBDClient *client, uint64_t handle,
-                               NBDExtent *extents, unsigned int nb_extents,
-                               uint64_t length, bool last,
-                               uint32_t context_id, Error **errp)
+                               NBDExtentArray *ea,
+                               bool last, uint32_t context_id, Error **errp)
 {
     NBDStructuredMeta chunk;
-
     struct iovec iov[] = {
         {.iov_base = &chunk, .iov_len = sizeof(chunk)},
-        {.iov_base = extents, .iov_len = nb_extents * sizeof(extents[0])}
+        {.iov_base = ea->extents, .iov_len = ea->count * sizeof(ea->extents[0])}
     };
 
-    trace_nbd_co_send_extents(handle, nb_extents, context_id, length, last);
+    nbd_extent_array_convert_to_be(ea);
+
+    trace_nbd_co_send_extents(handle, ea->count, context_id, ea->total_length,
+                              last);
     set_be_chunk(&chunk.h, last ? NBD_REPLY_FLAG_DONE : 0,
                  NBD_REPLY_TYPE_BLOCK_STATUS,
                  handle, sizeof(chunk) - sizeof(chunk.h) + iov[1].iov_len);
@@ -2009,39 +2048,27 @@ static int nbd_co_send_block_status(NBDClient *client, uint64_t handle,
 {
     int ret;
     unsigned int nb_extents = dont_fragment ? 1 : NBD_MAX_BLOCK_STATUS_EXTENTS;
-    NBDExtent *extents = g_new(NBDExtent, nb_extents);
-    uint64_t final_length = length;
+    g_autoptr(NBDExtentArray) ea = nbd_extent_array_new(nb_extents);
 
-    ret = blockstatus_to_extents(bs, offset, &final_length, extents,
-                                 &nb_extents);
+    ret = blockstatus_to_extents(bs, offset, length, ea);
     if (ret < 0) {
-        g_free(extents);
         return nbd_co_send_structured_error(
                 client, handle, -ret, "can't get block status", errp);
     }
 
-    ret = nbd_co_send_extents(client, handle, extents, nb_extents,
-                              final_length, last, context_id, errp);
-
-    g_free(extents);
-
-    return ret;
+    return nbd_co_send_extents(client, handle, ea, last, context_id, errp);
 }
 
 /*
- * Populate @extents from a dirty bitmap. Unless @dont_fragment, the
- * final extent may exceed the original @length. Store in @length the
- * byte length encoded (which may be smaller or larger than the
- * original), and return the number of extents used.
+ * Populate @ea from a dirty bitmap. Unless @dont_fragment, the
+ * final extent may exceed the original @length.
  */
-static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
-                                      uint64_t *length, NBDExtent *extents,
-                                      unsigned int nb_extents,
-                                      bool dont_fragment)
+static void bitmap_to_extents(BdrvDirtyBitmap *bitmap,
+                              uint64_t offset, uint64_t length,
+                              NBDExtentArray *ea, bool dont_fragment)
 {
     uint64_t begin = offset, end = offset;
-    uint64_t overall_end = offset + *length;
-    unsigned int i = 0;
+    uint64_t overall_end = offset + length;
     BdrvDirtyBitmapIter *it;
     bool dirty;
 
@@ -2050,8 +2077,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
     it = bdrv_dirty_iter_new(bitmap);
     dirty = bdrv_dirty_bitmap_get_locked(bitmap, offset);
 
-    assert(begin < overall_end && nb_extents);
-    while (begin < overall_end && i < nb_extents) {
+    while (begin < overall_end) {
         bool next_dirty = !dirty;
 
         if (dirty) {
@@ -2071,9 +2097,10 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
             end = overall_end;
         }
 
-        extents[i].length = cpu_to_be32(end - begin);
-        extents[i].flags = cpu_to_be32(dirty ? NBD_STATE_DIRTY : 0);
-        i++;
+        if (nbd_extent_array_add(ea, end - begin,
+                                 dirty ? NBD_STATE_DIRTY : 0) < 0) {
+            break;
+        }
         begin = end;
         dirty = next_dirty;
     }
@@ -2083,8 +2110,6 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
     bdrv_dirty_bitmap_unlock(bitmap);
 
     assert(offset < end);
-    *length = end - offset;
-    return i;
 }
 
 static int nbd_co_send_bitmap(NBDClient *client, uint64_t handle,
@@ -2092,20 +2117,12 @@ static int nbd_co_send_bitmap(NBDClient *client, uint64_t handle,
                               uint32_t length, bool dont_fragment, bool last,
                               uint32_t context_id, Error **errp)
 {
-    int ret;
     unsigned int nb_extents = dont_fragment ? 1 : NBD_MAX_BLOCK_STATUS_EXTENTS;
-    NBDExtent *extents = g_new(NBDExtent, nb_extents);
-    uint64_t final_length = length;
+    g_autoptr(NBDExtentArray) ea = nbd_extent_array_new(nb_extents);
 
-    nb_extents = bitmap_to_extents(bitmap, offset, &final_length, extents,
-                                   nb_extents, dont_fragment);
+    bitmap_to_extents(bitmap, offset, length, ea, dont_fragment);
 
-    ret = nbd_co_send_extents(client, handle, extents, nb_extents,
-                              final_length, last, context_id, errp);
-
-    g_free(extents);
-
-    return ret;
+    return nbd_co_send_extents(client, handle, ea, last, context_id, errp);
 }
 
 /* nbd_co_receive_request
-- 
2.21.0

Re: [PATCH v3 08/10] nbd/server: introduce NBDExtentArray

[Eric Blake]

On 12/19/19 4:03 AM, Vladimir Sementsov-Ogievskiy wrote:
> Introduce NBDExtentArray class, to handle extents list creation in more
> controlled way and with less OUT parameters in functions.

s/less/fewer/

> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>   nbd/server.c | 201 ++++++++++++++++++++++++++++-----------------------
>   1 file changed, 109 insertions(+), 92 deletions(-)
> 
> diff --git a/nbd/server.c b/nbd/server.c
> index a4b348eb32..cc722adc31 100644
> --- a/nbd/server.c
> +++ b/nbd/server.c
> @@ -1909,27 +1909,89 @@ static int coroutine_fn nbd_co_send_sparse_read(NBDClient *client,
>       return ret;
>   }
>   
> +typedef struct NBDExtentArray {
> +    NBDExtent *extents;
> +    unsigned int nb_alloc;
> +    unsigned int count;
> +    uint64_t total_length;
> +    bool converted; /* extents are converted to BE, no more changes allowed */
> +} NBDExtentArray;
> +

Looks good.

> +static NBDExtentArray *nbd_extent_array_new(unsigned int nb_alloc)
> +{
> +    NBDExtentArray *ea = g_new0(NBDExtentArray, 1);
> +
> +    ea->nb_alloc = nb_alloc;
> +    ea->extents = g_new(NBDExtent, nb_alloc);

I guess g_new() is okay rather tahn g_new0, as long as we are careful 
not to read that uninitialized memory.

> +
> +    return ea;
> +}
> +
> +static void nbd_extent_array_free(NBDExtentArray *ea)
> +{
> +    g_free(ea->extents);
> +    g_free(ea);
> +}
> +G_DEFINE_AUTOPTR_CLEANUP_FUNC(NBDExtentArray, nbd_extent_array_free);
> +
> +/* Further modifications of the array after conversion are abandoned */
> +static void nbd_extent_array_convert_to_be(NBDExtentArray *ea)
> +{
> +    int i;
> +
> +    if (ea->converted) {
> +        return;
> +    }

Would this be better as assert(!ea->converted), to ensure we aren't 
buggy in our usage? ...

> +    ea->converted = true;
> +
> +    for (i = 0; i < ea->count; i++) {
> +        ea->extents[i].flags = cpu_to_be32(ea->extents[i].flags);
> +        ea->extents[i].length = cpu_to_be32(ea->extents[i].length);
> +    }
> +}
> +
>   /*
> - * Populate @extents from block status. Update @bytes to be the actual
> - * length encoded (which may be smaller than the original), and update
> - * @nb_extents to the number of extents used.
> - *
> - * Returns zero on success and -errno on bdrv_block_status_above failure.
> + * Add extent to NBDExtentArray. If extent can't be added (no available space),
> + * return -1.
> + * For safety, when returning -1 for the first time, the array is converted
> + * to BE and further modifications are abandoned.
>    */
> -static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
> -                                  uint64_t *bytes, NBDExtent *extents,
> -                                  unsigned int *nb_extents)
> +static int nbd_extent_array_add(NBDExtentArray *ea,
> +                                uint32_t length, uint32_t flags)
>   {
> -    uint64_t remaining_bytes = *bytes;
> -    NBDExtent *extent = extents, *extents_end = extents + *nb_extents;
> -    bool first_extent = true;
> +    assert(!ea->converted);

...especially since you assert here.

> +
> +    if (!length) {
> +        return 0;
> +    }
> +
> +    /* Extend previous extent if flags are the same */
> +    if (ea->count > 0 && flags == ea->extents[ea->count - 1].flags) {
> +        ea->extents[ea->count - 1].length += length;
> +        ea->total_length += length;
> +        return 0;
> +    }

The NBD spec states that NBD_CMD_BLOCK_STATUS with flag 
NBD_CMD_FLAG_REQ_ONE must not exceed the original length of the client's 
request, but that when the flag is not present, the final extent may 
indeed go beyond the client's request.  I see two potential problems here:

1) I don't see any check that extending .length does not exceed the 
client's request if NBD_CMD_FLAG_REQ_ONE was set (we can sort of tell if 
that is the case based on whether nb_alloc is 1 or greater than 1, but 
not directly here, and it seems like this is a better place to do a 
common check than to make each caller repeat it).

2) I don't see any check that extending .length does not exceed 32 bits. 
  If the client requested status of 3.5G, but the caller divides that 
into two extent additions of 3G each and with the same flags, we could 
end up overflowing the 32-bit reply field (not necessarily fatal except 
when the overflow is exactly at 4G, because as long as the server is 
making progress, the client will eventually get all data; it is only 
when the overflow wraps to exactly 0 that we quit making progress). 
32-bit overflow is one case where the server HAS to return back-to-back 
extents with the same flags (if it is going to return information on 
that many bytes, rather than truncating its reply to just the first 
extent < 4G).

> +
> +    if (ea->count >= ea->nb_alloc) {
> +        nbd_extent_array_convert_to_be(ea);
> +        return -1;
> +    }
> +
> +    ea->total_length += length;
> +    ea->extents[ea->count] = (NBDExtent) {.length = length, .flags = flags};
> +    ea->count++;
>   
> -    assert(*nb_extents);
> -    while (remaining_bytes) {
> +    return 0;
> +}
> +
> +static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
> +                                  uint64_t bytes, NBDExtentArray *ea)
> +{
> +    while (bytes) {
>           uint32_t flags;
>           int64_t num;
> -        int ret = bdrv_block_status_above(bs, NULL, offset, remaining_bytes,
> -                                          &num, NULL, NULL);
> +        int ret = bdrv_block_status_above(bs, NULL, offset, bytes, &num,
> +                                          NULL, NULL);
>   
>           if (ret < 0) {
>               return ret;
> @@ -1938,60 +2000,37 @@ static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
>           flags = (ret & BDRV_BLOCK_ALLOCATED ? 0 : NBD_STATE_HOLE) |
>                   (ret & BDRV_BLOCK_ZERO      ? NBD_STATE_ZERO : 0);
>   
> -        if (first_extent) {
> -            extent->flags = flags;
> -            extent->length = num;
> -            first_extent = false;
> -        } else if (flags == extent->flags) {
> -            /* extend current extent */
> -            extent->length += num;
> -        } else {
> -            if (extent + 1 == extents_end) {
> -                break;
> -            }
> -
> -            /* start new extent */
> -            extent++;
> -            extent->flags = flags;
> -            extent->length = num;
> +        if (nbd_extent_array_add(ea, num, flags) < 0) {
> +            return 0;
>           }
> -        offset += num;
> -        remaining_bytes -= num;
> -    }

However, I _do_ like the refactoring on making the rest of the code 
easier to read.

> -
> -    extents_end = extent + 1;
>   
> -    for (extent = extents; extent < extents_end; extent++) {
> -        extent->flags = cpu_to_be32(extent->flags);
> -        extent->length = cpu_to_be32(extent->length);
> +        offset += num;
> +        bytes -= num;
>       }
>   
> -    *bytes -= remaining_bytes;
> -    *nb_extents = extents_end - extents;
> -
>       return 0;
>   }
>   

I think this needs v4 to fix the boundary cases, but I like where it is 
headed.

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

Re: [PATCH v3 08/10] nbd/server: introduce NBDExtentArray

[Vladimir Sementsov-Ogievskiy]

20.01.2020 23:20, Eric Blake wrote:
> On 12/19/19 4:03 AM, Vladimir Sementsov-Ogievskiy wrote:
>> Introduce NBDExtentArray class, to handle extents list creation in more
>> controlled way and with less OUT parameters in functions.
> 
> s/less/fewer/
> 
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   nbd/server.c | 201 ++++++++++++++++++++++++++++-----------------------
>>   1 file changed, 109 insertions(+), 92 deletions(-)
>>
>> diff --git a/nbd/server.c b/nbd/server.c
>> index a4b348eb32..cc722adc31 100644
>> --- a/nbd/server.c
>> +++ b/nbd/server.c
>> @@ -1909,27 +1909,89 @@ static int coroutine_fn nbd_co_send_sparse_read(NBDClient *client,
>>       return ret;
>>   }
>> +typedef struct NBDExtentArray {
>> +    NBDExtent *extents;
>> +    unsigned int nb_alloc;
>> +    unsigned int count;
>> +    uint64_t total_length;
>> +    bool converted; /* extents are converted to BE, no more changes allowed */
>> +} NBDExtentArray;
>> +
> 
> Looks good.
> 
>> +static NBDExtentArray *nbd_extent_array_new(unsigned int nb_alloc)
>> +{
>> +    NBDExtentArray *ea = g_new0(NBDExtentArray, 1);
>> +
>> +    ea->nb_alloc = nb_alloc;
>> +    ea->extents = g_new(NBDExtent, nb_alloc);
> 
> I guess g_new() is okay rather tahn g_new0, as long as we are careful not to read that uninitialized memory.
> 
>> +
>> +    return ea;
>> +}
>> +
>> +static void nbd_extent_array_free(NBDExtentArray *ea)
>> +{
>> +    g_free(ea->extents);
>> +    g_free(ea);
>> +}
>> +G_DEFINE_AUTOPTR_CLEANUP_FUNC(NBDExtentArray, nbd_extent_array_free);
>> +
>> +/* Further modifications of the array after conversion are abandoned */
>> +static void nbd_extent_array_convert_to_be(NBDExtentArray *ea)
>> +{
>> +    int i;
>> +
>> +    if (ea->converted) {
>> +        return;
>> +    }
> 
> Would this be better as assert(!ea->converted), to ensure we aren't buggy in our usage? ...

No, as array may be already automatically converted by nbd_extent_array_add, or may be not.

But your question stress that my design is weird. Now I think it's better to add separate
boolean ea field for nbd_extent_array_add() safety, instead of reusing .converted.

> 
>> +    ea->converted = true;
>> +
>> +    for (i = 0; i < ea->count; i++) {
>> +        ea->extents[i].flags = cpu_to_be32(ea->extents[i].flags);
>> +        ea->extents[i].length = cpu_to_be32(ea->extents[i].length);
>> +    }
>> +}
>> +
>>   /*
>> - * Populate @extents from block status. Update @bytes to be the actual
>> - * length encoded (which may be smaller than the original), and update
>> - * @nb_extents to the number of extents used.
>> - *
>> - * Returns zero on success and -errno on bdrv_block_status_above failure.
>> + * Add extent to NBDExtentArray. If extent can't be added (no available space),
>> + * return -1.
>> + * For safety, when returning -1 for the first time, the array is converted
>> + * to BE and further modifications are abandoned.
>>    */
>> -static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
>> -                                  uint64_t *bytes, NBDExtent *extents,
>> -                                  unsigned int *nb_extents)
>> +static int nbd_extent_array_add(NBDExtentArray *ea,
>> +                                uint32_t length, uint32_t flags)
>>   {
>> -    uint64_t remaining_bytes = *bytes;
>> -    NBDExtent *extent = extents, *extents_end = extents + *nb_extents;
>> -    bool first_extent = true;
>> +    assert(!ea->converted);
> 
> ...especially since you assert here.
> 
>> +
>> +    if (!length) {
>> +        return 0;
>> +    }
>> +
>> +    /* Extend previous extent if flags are the same */
>> +    if (ea->count > 0 && flags == ea->extents[ea->count - 1].flags) {
>> +        ea->extents[ea->count - 1].length += length;
>> +        ea->total_length += length;
>> +        return 0;
>> +    }
> 
> The NBD spec states that NBD_CMD_BLOCK_STATUS with flag NBD_CMD_FLAG_REQ_ONE must not exceed the original length of the client's request, but that when the flag is not present, the final extent may indeed go beyond the client's request.  I see two potential problems here:
> 
> 1) I don't see any check that extending .length does not exceed the client's request if NBD_CMD_FLAG_REQ_ONE was set (we can sort of tell if that is the case based on whether nb_alloc is 1 or greater than 1, but not directly here, and it seems like this is a better place to do a common check than to make each caller repeat it).

we have two callers. blockstatus_to_extents can't exceed the requested range, and bitmaps_to_extents has own check. If we want to move the check into nbd_extent_array_add, we need to enhance its interface to allow it to add only "part" of extent.. And how to handle it?
Mark the array "closed" after first partly applied extent, but return success? Then we'll have to change assertion at start of _add s/assert(ea->can_add)/if (!ea->can_add) {return -1}/..  Or return count of really applied bytes to the caller?

I doubt that this is a good idea, it seems simpler to keep nbd extent array not knowing about length limitation, keeping in mind that the following patch will drop any exceeding of the requested range.

> 
> 2) I don't see any check that extending .length does not exceed 32 bits.  If the client requested status of 3.5G, but the caller divides that into two extent additions of 3G each and with the same flags, we could end up overflowing the 32-bit reply field (not necessarily fatal except when the overflow is exactly at 4G, because as long as the server is making progress, the client will eventually get all data; it is only when the overflow wraps to exactly 0 that we quit making progress). 32-bit overflow is one case where the server HAS to return back-to-back extents with the same flags (if it is going to return information on that many bytes, rather than truncating its reply to just the first extent < 4G).

good catch. I'll write it like

      /* Extend previous extent if flags are the same */
      if (ea->count > 0 && flags == ea->extents[ea->count - 1].flags) {
          uint64_t sum = (uint64_t)length + ea->extents[ea->count - 1].length;

          if (sum <= UINT32_MAX) {
              ea->extents[ea->count - 1].length = sum;
              ea->total_length += length;
              return 0;
          }
      }

> 
>> +
>> +    if (ea->count >= ea->nb_alloc) {
>> +        nbd_extent_array_convert_to_be(ea);
>> +        return -1;
>> +    }
>> +
>> +    ea->total_length += length;
>> +    ea->extents[ea->count] = (NBDExtent) {.length = length, .flags = flags};
>> +    ea->count++;
>> -    assert(*nb_extents);
>> -    while (remaining_bytes) {
>> +    return 0;
>> +}
>> +
>> +static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
>> +                                  uint64_t bytes, NBDExtentArray *ea)
>> +{
>> +    while (bytes) {
>>           uint32_t flags;
>>           int64_t num;
>> -        int ret = bdrv_block_status_above(bs, NULL, offset, remaining_bytes,
>> -                                          &num, NULL, NULL);
>> +        int ret = bdrv_block_status_above(bs, NULL, offset, bytes, &num,
>> +                                          NULL, NULL);
>>           if (ret < 0) {
>>               return ret;
>> @@ -1938,60 +2000,37 @@ static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset,
>>           flags = (ret & BDRV_BLOCK_ALLOCATED ? 0 : NBD_STATE_HOLE) |
>>                   (ret & BDRV_BLOCK_ZERO      ? NBD_STATE_ZERO : 0);
>> -        if (first_extent) {
>> -            extent->flags = flags;
>> -            extent->length = num;
>> -            first_extent = false;
>> -        } else if (flags == extent->flags) {
>> -            /* extend current extent */
>> -            extent->length += num;
>> -        } else {
>> -            if (extent + 1 == extents_end) {
>> -                break;
>> -            }
>> -
>> -            /* start new extent */
>> -            extent++;
>> -            extent->flags = flags;
>> -            extent->length = num;
>> +        if (nbd_extent_array_add(ea, num, flags) < 0) {
>> +            return 0;
>>           }
>> -        offset += num;
>> -        remaining_bytes -= num;
>> -    }
> 
> However, I _do_ like the refactoring on making the rest of the code easier to read.
> 
>> -
>> -    extents_end = extent + 1;
>> -    for (extent = extents; extent < extents_end; extent++) {
>> -        extent->flags = cpu_to_be32(extent->flags);
>> -        extent->length = cpu_to_be32(extent->length);
>> +        offset += num;
>> +        bytes -= num;
>>       }
>> -    *bytes -= remaining_bytes;
>> -    *nb_extents = extents_end - extents;
>> -
>>       return 0;
>>   }
> 
> I think this needs v4 to fix the boundary cases, but I like where it is headed.
> 


-- 
Best regards,
Vladimir

[PATCH v3 09/10] nbd/server: use bdrv_dirty_bitmap_next_dirty_area

[Vladimir Sementsov-Ogievskiy]

Use bdrv_dirty_bitmap_next_dirty_area for bitmap_to_extents. Since
bdrv_dirty_bitmap_next_dirty_area is very accurate in its interface,
we'll never exceed requested region with last chunk. So, we don't need
dont_fragment, and bitmap_to_extents() interface becomes clean enough
to not require any comment.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 nbd/server.c | 59 +++++++++++++++++-----------------------------------
 1 file changed, 19 insertions(+), 40 deletions(-)

diff --git a/nbd/server.c b/nbd/server.c
index cc722adc31..461566a051 100644
--- a/nbd/server.c
+++ b/nbd/server.c
@@ -2059,57 +2059,36 @@ static int nbd_co_send_block_status(NBDClient *client, uint64_t handle,
     return nbd_co_send_extents(client, handle, ea, last, context_id, errp);
 }
 
-/*
- * Populate @ea from a dirty bitmap. Unless @dont_fragment, the
- * final extent may exceed the original @length.
- */
+/* Populate @ea from a dirty bitmap. */
 static void bitmap_to_extents(BdrvDirtyBitmap *bitmap,
                               uint64_t offset, uint64_t length,
-                              NBDExtentArray *ea, bool dont_fragment)
+                              NBDExtentArray *es)
 {
-    uint64_t begin = offset, end = offset;
-    uint64_t overall_end = offset + length;
-    BdrvDirtyBitmapIter *it;
-    bool dirty;
+    int64_t start, dirty_start, dirty_count;
+    int64_t end = offset + length;
+    bool full = false;
 
     bdrv_dirty_bitmap_lock(bitmap);
 
-    it = bdrv_dirty_iter_new(bitmap);
-    dirty = bdrv_dirty_bitmap_get_locked(bitmap, offset);
-
-    while (begin < overall_end) {
-        bool next_dirty = !dirty;
-
-        if (dirty) {
-            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, INT64_MAX);
-        } else {
-            bdrv_set_dirty_iter(it, begin);
-            end = bdrv_dirty_iter_next(it);
-        }
-        if (end == -1 || end - begin > UINT32_MAX) {
-            /* Cap to an aligned value < 4G beyond begin. */
-            end = MIN(bdrv_dirty_bitmap_size(bitmap),
-                      begin + UINT32_MAX + 1 -
-                      bdrv_dirty_bitmap_granularity(bitmap));
-            next_dirty = dirty;
-        }
-        if (dont_fragment && end > overall_end) {
-            end = overall_end;
-        }
-
-        if (nbd_extent_array_add(ea, end - begin,
-                                 dirty ? NBD_STATE_DIRTY : 0) < 0) {
+    for (start = offset;
+         bdrv_dirty_bitmap_next_dirty_area(bitmap, start, end, INT32_MAX,
+                                           &dirty_start, &dirty_count);
+         start = dirty_start + dirty_count)
+    {
+        if ((nbd_extent_array_add(es, dirty_start - start, 0) < 0) ||
+            (nbd_extent_array_add(es, dirty_count, NBD_STATE_DIRTY) < 0))
+        {
+            full = true;
             break;
         }
-        begin = end;
-        dirty = next_dirty;
     }
 
-    bdrv_dirty_iter_free(it);
+    if (!full) {
+        /* last non dirty extent */
+        nbd_extent_array_add(es, end - start, 0);
+    }
 
     bdrv_dirty_bitmap_unlock(bitmap);
-
-    assert(offset < end);
 }
 
 static int nbd_co_send_bitmap(NBDClient *client, uint64_t handle,
@@ -2120,7 +2099,7 @@ static int nbd_co_send_bitmap(NBDClient *client, uint64_t handle,
     unsigned int nb_extents = dont_fragment ? 1 : NBD_MAX_BLOCK_STATUS_EXTENTS;
     g_autoptr(NBDExtentArray) ea = nbd_extent_array_new(nb_extents);
 
-    bitmap_to_extents(bitmap, offset, length, ea, dont_fragment);
+    bitmap_to_extents(bitmap, offset, length, ea);
 
     return nbd_co_send_extents(client, handle, ea, last, context_id, errp);
 }
-- 
2.21.0

Re: [PATCH v3 09/10] nbd/server: use bdrv_dirty_bitmap_next_dirty_area

[Eric Blake]

On 12/19/19 4:03 AM, Vladimir Sementsov-Ogievskiy wrote:
> Use bdrv_dirty_bitmap_next_dirty_area for bitmap_to_extents. Since
> bdrv_dirty_bitmap_next_dirty_area is very accurate in its interface,
> we'll never exceed requested region with last chunk. So, we don't need
> dont_fragment, and bitmap_to_extents() interface becomes clean enough
> to not require any comment.

Not exceeding the requested region means we are giving the client less 
information than what we already have freely available.  I don't know if 
that will (slightly) pessimize any client that would have otherwise been 
able to handle the fact that we reported beyond the request (only 
matters for clients which do not use NBD_CMD_FLAG_REQ_ONE).

> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> Reviewed-by: Eric Blake <eblake@redhat.com>

But since I've already reviewed it, my R-b still stands.

> ---
>   nbd/server.c | 59 +++++++++++++++++-----------------------------------
>   1 file changed, 19 insertions(+), 40 deletions(-)
> 

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

[PATCH v3 10/10] block/qcow2-bitmap: use bdrv_dirty_bitmap_next_dirty

[Vladimir Sementsov-Ogievskiy]

store_bitmap_data() loop does bdrv_set_dirty_iter() on each iteration,
which means that we actually don't need iterator itself and we can use
simpler bitmap API.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 block/qcow2-bitmap.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/block/qcow2-bitmap.c b/block/qcow2-bitmap.c
index c6c8ebbe89..015f5d18d2 100644
--- a/block/qcow2-bitmap.c
+++ b/block/qcow2-bitmap.c
@@ -1289,7 +1289,6 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs,
     uint64_t bm_size = bdrv_dirty_bitmap_size(bitmap);
     const char *bm_name = bdrv_dirty_bitmap_name(bitmap);
     uint8_t *buf = NULL;
-    BdrvDirtyBitmapIter *dbi;
     uint64_t *tb;
     uint64_t tb_size =
             size_to_clusters(s,
@@ -1308,12 +1307,14 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs,
         return NULL;
     }
 
-    dbi = bdrv_dirty_iter_new(bitmap);
     buf = g_malloc(s->cluster_size);
     limit = bytes_covered_by_bitmap_cluster(s, bitmap);
     assert(DIV_ROUND_UP(bm_size, limit) == tb_size);
 
-    while ((offset = bdrv_dirty_iter_next(dbi)) >= 0) {
+    offset = 0;
+    while ((offset = bdrv_dirty_bitmap_next_dirty(bitmap, offset, INT64_MAX))
+           >= 0)
+    {
         uint64_t cluster = offset / limit;
         uint64_t end, write_size;
         int64_t off;
@@ -1360,19 +1361,17 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs,
             break;
         }
 
-        bdrv_set_dirty_iter(dbi, end);
+        offset = end;
     }
 
     *bitmap_table_size = tb_size;
     g_free(buf);
-    bdrv_dirty_iter_free(dbi);
 
     return tb;
 
 fail:
     clear_bitmap_table(bs, tb, tb_size);
     g_free(buf);
-    bdrv_dirty_iter_free(dbi);
     g_free(tb);
 
     return NULL;
-- 
2.21.0

Re: [PATCH v3 10/10] block/qcow2-bitmap: use bdrv_dirty_bitmap_next_dirty

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 953 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> store_bitmap_data() loop does bdrv_set_dirty_iter() on each iteration,
> which means that we actually don't need iterator itself and we can use
> simpler bitmap API.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  block/qcow2-bitmap.c | 11 +++++------
>  1 file changed, 5 insertions(+), 6 deletions(-)
> 
> diff --git a/block/qcow2-bitmap.c b/block/qcow2-bitmap.c
> index c6c8ebbe89..015f5d18d2 100644
> --- a/block/qcow2-bitmap.c
> +++ b/block/qcow2-bitmap.c

[...]

> @@ -1360,19 +1361,17 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs,

(One line more context:)

>          if (end >= bm_size) 
>              break;
>          }

Can we drop this now?

If so, and with that done:

Reviewed-by: Max Reitz <mreitz@redhat.com>

>  
> -        bdrv_set_dirty_iter(dbi, end);
> +        offset = end;
>      }


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 10/10] block/qcow2-bitmap: use bdrv_dirty_bitmap_next_dirty

[Vladimir Sementsov-Ogievskiy]

20.01.2020 17:18, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> store_bitmap_data() loop does bdrv_set_dirty_iter() on each iteration,
>> which means that we actually don't need iterator itself and we can use
>> simpler bitmap API.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   block/qcow2-bitmap.c | 11 +++++------
>>   1 file changed, 5 insertions(+), 6 deletions(-)
>>
>> diff --git a/block/qcow2-bitmap.c b/block/qcow2-bitmap.c
>> index c6c8ebbe89..015f5d18d2 100644
>> --- a/block/qcow2-bitmap.c
>> +++ b/block/qcow2-bitmap.c
> 
> [...]
> 
>> @@ -1360,19 +1361,17 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs,
> 
> (One line more context:)
> 
>>           if (end >= bm_size)
>>               break;
>>           }
> 
> Can we drop this now?

Yes, we can, as hbitmap_next_dirty returns -1 in this case.

> 
> If so, and with that done:
> 
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> 
>>   
>> -        bdrv_set_dirty_iter(dbi, end);
>> +        offset = end;
>>       }
> 


-- 
Best regards,
Vladimir

Re: [PATCH v3 00/10] Further bitmaps improvements

[Vladimir Sementsov-Ogievskiy]

ping

19.12.2019 13:03, Vladimir Sementsov-Ogievskiy wrote:
> Hi!
> 
> The main feature here is improvement of _next_dirty_area API, which I'm
> going to use then for backup / block-copy.
> 
> v3: rebase on current master. Mirror don't use _next_dirty_area any
> more, so mirror chunks dropped (patches 05 and 07) and 07 commit message
> changed.
> 
> Vladimir Sementsov-Ogievskiy (10):
>    hbitmap: assert that we don't create bitmap larger than INT64_MAX
>    hbitmap: move hbitmap_iter_next_word to hbitmap.c
>    hbitmap: unpublish hbitmap_iter_skip_words
>    hbitmap: drop meta bitmaps as they are unused
>    block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_t
>    block/dirty-bitmap: add _next_dirty API
>    block/dirty-bitmap: improve _next_dirty_area API
>    nbd/server: introduce NBDExtentArray
>    nbd/server: use bdrv_dirty_bitmap_next_dirty_area
>    block/qcow2-bitmap: use bdrv_dirty_bitmap_next_dirty
> 
>   include/block/dirty-bitmap.h |   9 +-
>   include/qemu/hbitmap.h       |  97 +++--------
>   block/dirty-bitmap.c         |  16 +-
>   block/qcow2-bitmap.c         |  11 +-
>   nbd/server.c                 | 242 +++++++++++++--------------
>   tests/test-hbitmap.c         | 314 +++++++++++++----------------------
>   util/hbitmap.c               | 133 +++++++++------
>   7 files changed, 366 insertions(+), 456 deletions(-)
> 


-- 
Best regards,
Vladimir

Re: [PATCH v3 00/10] Further bitmaps improvements

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 389 bytes --]

On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
> Hi!
> 
> The main feature here is improvement of _next_dirty_area API, which I'm
> going to use then for backup / block-copy.

Looks good to me overall, with a few minor changes.  I’d rather leave
patches 8 and 9 to Eric, though.  (Even though I’m not exactly the
maintainer for the rest of the patches either...)

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v3 00/10] Further bitmaps improvements

[Vladimir Sementsov-Ogievskiy]

20.01.2020 17:20, Max Reitz wrote:
> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>> Hi!
>>
>> The main feature here is improvement of _next_dirty_area API, which I'm
>> going to use then for backup / block-copy.
> 
> Looks good to me overall, with a few minor changes.  I’d rather leave
> patches 8 and 9 to Eric, though.  (Even though I’m not exactly the
> maintainer for the rest of the patches either...)
> 
> Max
> 

Thanks for reviewing! Let's wait for Eric.

-- 
Best regards,
Vladimir

Re: [PATCH v3 00/10] Further bitmaps improvements

[Eric Blake]

On 1/20/20 10:33 AM, Vladimir Sementsov-Ogievskiy wrote:
> 20.01.2020 17:20, Max Reitz wrote:
>> On 19.12.19 11:03, Vladimir Sementsov-Ogievskiy wrote:
>>> Hi!
>>>
>>> The main feature here is improvement of _next_dirty_area API, which I'm
>>> going to use then for backup / block-copy.
>>
>> Looks good to me overall, with a few minor changes.  I’d rather leave
>> patches 8 and 9 to Eric, though.  (Even though I’m not exactly the
>> maintainer for the rest of the patches either...)
>>
>> Max
>>
> 
> Thanks for reviewing! Let's wait for Eric.

I had enough concerns over 8/10 to probably warrant a v4; but I'm also 
fine taking the entire series through my NBD tree once everyone is happy 
with it.

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