| Message ID | 20191219100348.24827-8-vsementsov@virtuozzo.com |
|---|---|
| State | New |
| Headers | show |
| Series | [v3,01/10] hbitmap: assert that we don't create bitmap larger than INT64_MAX | expand |
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; > } > } > >
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; >> } >> } >> >> >
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; } }
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(-)