| Message ID | 20180814121443.33114-2-vsementsov@virtuozzo.com |
|---|---|
| State | New |
| Headers | show |
| Series | dirty-bitmap: rewrite bdrv_dirty_iter_next_area | expand |
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote: > Add bytes parameter to the function, to limit searched range. > I'm going to assume that Eric Blake has been through here and commented on the interface itself. > Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> > --- > include/block/dirty-bitmap.h | 3 ++- > include/qemu/hbitmap.h | 10 ++++++++-- > block/backup.c | 2 +- > block/dirty-bitmap.c | 5 +++-- > nbd/server.c | 2 +- > tests/test-hbitmap.c | 2 +- > util/hbitmap.c | 25 ++++++++++++++++++++----- > 7 files changed, 36 insertions(+), 13 deletions(-) > > diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h > index 259bd27c40..27f5299c4e 100644 > --- a/include/block/dirty-bitmap.h > +++ b/include/block/dirty-bitmap.h > @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs); > BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, > BdrvDirtyBitmap *bitmap); > char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp); > -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start); > +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start, > + int64_t end); > BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs, > BdrvDirtyBitmap *bitmap, > Error **errp); > diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h > index ddca52c48e..fe4dfde27a 100644 > --- a/include/qemu/hbitmap.h > +++ b/include/qemu/hbitmap.h > @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); > /* hbitmap_next_zero: > * @hb: The HBitmap to operate on > * @start: The bit to start from. > + * @end: End of range to search in. If @end is -1, search up to the bitmap > + * end. > * > - * Find next not dirty bit. > + * Find next not dirty bit within range [@start, @end), or from > + * @start to the bitmap end if @end is -1. If not found, return -1. > + * > + * @end may be greater than original bitmap size, in this case, search up to "original" bitmap size? I think that's just an implementation detail, we can drop 'original' here, yes? > + * the bitmap end. > */ > -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); > +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end); > The interface looks weird because we can define a 'start' that's beyond the 'end'. I realize that you need a signed integer for 'end' to signify EOF... should we do a 'bytes' parameter instead? (Did you already do that in an earlier version and we changed it?) Well, it's not a big deal to me personally. > /* hbitmap_create_meta: > * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. > diff --git a/block/backup.c b/block/backup.c > index 8630d32926..9bfd3f7189 100644 > --- a/block/backup.c > +++ b/block/backup.c > @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job) > break; > } > > - offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset); > + offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1); > if (offset == -1) { > hbitmap_set(job->copy_bitmap, cluster, end - cluster); > break; > diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c > index c9b8a6fd52..037ae62726 100644 > --- a/block/dirty-bitmap.c > +++ b/block/dirty-bitmap.c > @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp) > return hbitmap_sha256(bitmap->bitmap, errp); > } > > -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset) > +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset, > + int64_t end) > { > - return hbitmap_next_zero(bitmap->bitmap, offset); > + return hbitmap_next_zero(bitmap->bitmap, offset, end); > } > > void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src, > diff --git a/nbd/server.c b/nbd/server.c > index ea5fe0eb33..07920d123b 100644 > --- a/nbd/server.c > +++ b/nbd/server.c > @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, > assert(begin < overall_end && nb_extents); > while (begin < overall_end && i < nb_extents) { > if (dirty) { > - end = bdrv_dirty_bitmap_next_zero(bitmap, begin); > + end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1); > } else { > bdrv_set_dirty_iter(it, begin); > end = bdrv_dirty_iter_next(it); > diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c > index 5e67ac1d3a..6b6a40bddd 100644 > --- a/tests/test-hbitmap.c > +++ b/tests/test-hbitmap.c > @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, > > static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) > { > - int64_t ret1 = hbitmap_next_zero(data->hb, start); > + int64_t ret1 = hbitmap_next_zero(data->hb, start, -1); > int64_t ret2 = start; > for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) { > ; > diff --git a/util/hbitmap.c b/util/hbitmap.c > index bcd304041a..1687372504 100644 > --- a/util/hbitmap.c > +++ b/util/hbitmap.c > @@ -53,6 +53,9 @@ > */ > > struct HBitmap { > + /* Size of the bitmap, as requested in hbitmap_alloc. */ > + uint64_t orig_size; > + > /* Number of total bits in the bottom level. */ > uint64_t size; > > @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) > } > } > > -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) > +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end) > { > size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; > unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; > - uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1]; > unsigned long cur = last_lev[pos]; > - unsigned start_bit_offset = > - (start >> hb->granularity) & (BITS_PER_LONG - 1); > + unsigned start_bit_offset; > + uint64_t end_bit, sz; > int64_t res; > > + if (start >= hb->orig_size || (end != -1 && end <= start)) { > + return -1; > + } > + > + end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1; > + sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; > + > + /* There may be some zero bits in @cur before @start. We are not interested > + * in them, let's set them. > + */ > + start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); > cur |= (1UL << start_bit_offset) - 1; > assert((start >> hb->granularity) < hb->size); > > @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) > } > > res = (pos << BITS_PER_LEVEL) + ctol(cur); > - if (res >= hb->size) { > + if (res >= end_bit) { > return -1; > } > > @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity) > HBitmap *hb = g_new0(struct HBitmap, 1); > unsigned i; > > + hb->orig_size = size; > + > assert(granularity >= 0 && granularity < 64); > size = (size + (1ULL << granularity) - 1) >> granularity; > assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); > Despite my comments, I'm OK with or without changes. Reviewed-by: John Snow <jsnow@redhat.com>
On 9/7/18 4:49 PM, John Snow wrote: > > > On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote: >> Add bytes parameter to the function, to limit searched range. >> > > I'm going to assume that Eric Blake has been through here and commented > on the interface itself. Actually, I haven't had time to look at this series in depth. Do you need me to? > >> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> >> --- >> include/block/dirty-bitmap.h | 3 ++- >> include/qemu/hbitmap.h | 10 ++++++++-- >> block/backup.c | 2 +- >> block/dirty-bitmap.c | 5 +++-- >> nbd/server.c | 2 +- >> tests/test-hbitmap.c | 2 +- >> util/hbitmap.c | 25 ++++++++++++++++++++----- >> 7 files changed, 36 insertions(+), 13 deletions(-) >> >> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h >> index 259bd27c40..27f5299c4e 100644 >> --- a/include/block/dirty-bitmap.h >> +++ b/include/block/dirty-bitmap.h >> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs); >> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, >> BdrvDirtyBitmap *bitmap); >> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp); >> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start); >> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start, >> + int64_t end); It's already seeming a bit odd to mix uint64_t AND int64_t for the two parameters. Is the intent to allow -1 to mean "end of the bitmap instead of a specific end range"? But you can get that with UINT64_MAX just as easily, and still get away with spelling it -1 in the source. >> + * the bitmap end. >> */ >> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end); >> > > The interface looks weird because we can define a 'start' that's beyond > the 'end'. > > I realize that you need a signed integer for 'end' to signify EOF... > should we do a 'bytes' parameter instead? (Did you already do that in an > earlier version and we changed it?) > > Well, it's not a big deal to me personally. It should always be possible to convert in either direction between [start,end) and [start,start+bytes); it boils down to a question of convenience (which form is easier for the majority of callers) and consistency (which form do we use more frequently in the block layer). I haven't checked closely, but I think start+bytes is more common than end in our public block layer APIs.
On 09/10/2018 10:59 AM, Eric Blake wrote: > On 9/7/18 4:49 PM, John Snow wrote: >> >> >> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote: >>> Add bytes parameter to the function, to limit searched range. >>> >> >> I'm going to assume that Eric Blake has been through here and commented >> on the interface itself. > > Actually, I haven't had time to look at this series in depth. Do you > need me to? > Not necessarily, it's just that I didn't read v1 or v2 so I was just being cautious against recommending changes that maybe we already recommended against in a different direction. Historically you've cared the most about start/end/offset/bytes naming and conventions, so I just made an assumption. --js >> >>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> >>> --- >>> include/block/dirty-bitmap.h | 3 ++- >>> include/qemu/hbitmap.h | 10 ++++++++-- >>> block/backup.c | 2 +- >>> block/dirty-bitmap.c | 5 +++-- >>> nbd/server.c | 2 +- >>> tests/test-hbitmap.c | 2 +- >>> util/hbitmap.c | 25 ++++++++++++++++++++----- >>> 7 files changed, 36 insertions(+), 13 deletions(-) >>> >>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h >>> index 259bd27c40..27f5299c4e 100644 >>> --- a/include/block/dirty-bitmap.h >>> +++ b/include/block/dirty-bitmap.h >>> @@ -98,7 +98,8 @@ bool >>> bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs); >>> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, >>> BdrvDirtyBitmap *bitmap); >>> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error >>> **errp); >>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, >>> uint64_t start); >>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, >>> uint64_t start, >>> + int64_t end); > > It's already seeming a bit odd to mix uint64_t AND int64_t for the two > parameters. Is the intent to allow -1 to mean "end of the bitmap > instead of a specific end range"? But you can get that with UINT64_MAX > just as easily, and still get away with spelling it -1 in the source. > > >>> + * the bitmap end. >>> */ >>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t >>> end); >>> >> >> The interface looks weird because we can define a 'start' that's beyond >> the 'end'. >> >> I realize that you need a signed integer for 'end' to signify EOF... >> should we do a 'bytes' parameter instead? (Did you already do that in an >> earlier version and we changed it?) >> >> Well, it's not a big deal to me personally. > > It should always be possible to convert in either direction between > [start,end) and [start,start+bytes); it boils down to a question of > convenience (which form is easier for the majority of callers) and > consistency (which form do we use more frequently in the block layer). I > haven't checked closely, but I think start+bytes is more common than end > in our public block layer APIs. >
08.09.2018 00:49, John Snow wrote: > > On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote: >> Add bytes parameter to the function, to limit searched range. >> > I'm going to assume that Eric Blake has been through here and commented > on the interface itself. > >> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> >> --- >> include/block/dirty-bitmap.h | 3 ++- >> include/qemu/hbitmap.h | 10 ++++++++-- >> block/backup.c | 2 +- >> block/dirty-bitmap.c | 5 +++-- >> nbd/server.c | 2 +- >> tests/test-hbitmap.c | 2 +- >> util/hbitmap.c | 25 ++++++++++++++++++++----- >> 7 files changed, 36 insertions(+), 13 deletions(-) >> >> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h >> index 259bd27c40..27f5299c4e 100644 >> --- a/include/block/dirty-bitmap.h >> +++ b/include/block/dirty-bitmap.h >> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs); >> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, >> BdrvDirtyBitmap *bitmap); >> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp); >> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start); >> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start, >> + int64_t end); >> BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs, >> BdrvDirtyBitmap *bitmap, >> Error **errp); >> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h >> index ddca52c48e..fe4dfde27a 100644 >> --- a/include/qemu/hbitmap.h >> +++ b/include/qemu/hbitmap.h >> @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); >> /* hbitmap_next_zero: >> * @hb: The HBitmap to operate on >> * @start: The bit to start from. >> + * @end: End of range to search in. If @end is -1, search up to the bitmap >> + * end. >> * >> - * Find next not dirty bit. >> + * Find next not dirty bit within range [@start, @end), or from >> + * @start to the bitmap end if @end is -1. If not found, return -1. >> + * >> + * @end may be greater than original bitmap size, in this case, search up to > "original" bitmap size? I think that's just an implementation detail, we > can drop 'original' here, yes? hm, no. we have field "size", which is not "original". But it all means that this place needs a bit more refactoring. > >> + * the bitmap end. >> */ >> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end); >> > The interface looks weird because we can define a 'start' that's beyond > the 'end'. > > I realize that you need a signed integer for 'end' to signify EOF... > should we do a 'bytes' parameter instead? (Did you already do that in an > earlier version and we changed it?) > > Well, it's not a big deal to me personally. interface with constant end parameter is more comfortable for loop: we don't need to update 'bytes' parameter on each iteration > >> /* hbitmap_create_meta: >> * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. >> diff --git a/block/backup.c b/block/backup.c >> index 8630d32926..9bfd3f7189 100644 >> --- a/block/backup.c >> +++ b/block/backup.c >> @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job) >> break; >> } >> >> - offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset); >> + offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1); >> if (offset == -1) { >> hbitmap_set(job->copy_bitmap, cluster, end - cluster); >> break; >> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c >> index c9b8a6fd52..037ae62726 100644 >> --- a/block/dirty-bitmap.c >> +++ b/block/dirty-bitmap.c >> @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp) >> return hbitmap_sha256(bitmap->bitmap, errp); >> } >> >> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset) >> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset, >> + int64_t end) >> { >> - return hbitmap_next_zero(bitmap->bitmap, offset); >> + return hbitmap_next_zero(bitmap->bitmap, offset, end); >> } >> >> void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src, >> diff --git a/nbd/server.c b/nbd/server.c >> index ea5fe0eb33..07920d123b 100644 >> --- a/nbd/server.c >> +++ b/nbd/server.c >> @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, >> assert(begin < overall_end && nb_extents); >> while (begin < overall_end && i < nb_extents) { >> if (dirty) { >> - end = bdrv_dirty_bitmap_next_zero(bitmap, begin); >> + end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1); >> } else { >> bdrv_set_dirty_iter(it, begin); >> end = bdrv_dirty_iter_next(it); >> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c >> index 5e67ac1d3a..6b6a40bddd 100644 >> --- a/tests/test-hbitmap.c >> +++ b/tests/test-hbitmap.c >> @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, >> >> static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) >> { >> - int64_t ret1 = hbitmap_next_zero(data->hb, start); >> + int64_t ret1 = hbitmap_next_zero(data->hb, start, -1); >> int64_t ret2 = start; >> for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) { >> ; >> diff --git a/util/hbitmap.c b/util/hbitmap.c >> index bcd304041a..1687372504 100644 >> --- a/util/hbitmap.c >> +++ b/util/hbitmap.c >> @@ -53,6 +53,9 @@ >> */ >> >> struct HBitmap { >> + /* Size of the bitmap, as requested in hbitmap_alloc. */ >> + uint64_t orig_size; >> + >> /* Number of total bits in the bottom level. */ >> uint64_t size; >> >> @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) >> } >> } >> >> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) >> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end) >> { >> size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; >> unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; >> - uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1]; >> unsigned long cur = last_lev[pos]; >> - unsigned start_bit_offset = >> - (start >> hb->granularity) & (BITS_PER_LONG - 1); >> + unsigned start_bit_offset; >> + uint64_t end_bit, sz; >> int64_t res; >> >> + if (start >= hb->orig_size || (end != -1 && end <= start)) { >> + return -1; >> + } >> + >> + end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1; >> + sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; >> + >> + /* There may be some zero bits in @cur before @start. We are not interested >> + * in them, let's set them. >> + */ >> + start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); >> cur |= (1UL << start_bit_offset) - 1; >> assert((start >> hb->granularity) < hb->size); >> >> @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) >> } >> >> res = (pos << BITS_PER_LEVEL) + ctol(cur); >> - if (res >= hb->size) { >> + if (res >= end_bit) { >> return -1; >> } >> >> @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity) >> HBitmap *hb = g_new0(struct HBitmap, 1); >> unsigned i; >> >> + hb->orig_size = size; >> + >> assert(granularity >= 0 && granularity < 64); >> size = (size + (1ULL << granularity) - 1) >> granularity; >> assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); >> > Despite my comments, I'm OK with or without changes. > > Reviewed-by: John Snow <jsnow@redhat.com>
On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote: >>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t >>> end); >> The interface looks weird because we can define a 'start' that's beyond >> the 'end'. >> >> I realize that you need a signed integer for 'end' to signify EOF... >> should we do a 'bytes' parameter instead? (Did you already do that in an >> earlier version and we changed it?) >> >> Well, it's not a big deal to me personally. > > interface with constant end parameter is more comfortable for loop: we > don't need to update 'bytes' parameter on each iteration But there's still the question of WHO should be calculating end. Your interface argues for the caller: hbitmap_next_zero(start, start + bytes) int64_t hbitmap_next_zero(...) { while (offset != end) ... } while we're asking about a consistent interface for the caller (if most callers already have a 'bytes' rather than an 'end' computed): hbitmap_next_zero(start, bytes) int64_t hbitmap_next_zero(...) { int64_t end = start + bytes; while (offset != end) ... }
10.09.2018 19:55, Eric Blake wrote: > On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote: > >>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, >>>> int64_t end); >>> The interface looks weird because we can define a 'start' that's beyond >>> the 'end'. >>> >>> I realize that you need a signed integer for 'end' to signify EOF... >>> should we do a 'bytes' parameter instead? (Did you already do that >>> in an >>> earlier version and we changed it?) >>> >>> Well, it's not a big deal to me personally. >> >> interface with constant end parameter is more comfortable for loop: >> we don't need to update 'bytes' parameter on each iteration > > But there's still the question of WHO should be calculating end. Your > interface argues for the caller: > > hbitmap_next_zero(start, start + bytes) > > int64_t hbitmap_next_zero(...) > { > while (offset != end) ... > } > > while we're asking about a consistent interface for the caller (if > most callers already have a 'bytes' rather than an 'end' computed): > > hbitmap_next_zero(start, bytes) > > int64_t hbitmap_next_zero(...) > { > int64_t end = start + bytes; > while (offset != end) ... > } > Yes, that's an issue. Ok, if you are not comfortable with start,end, I can switch to start,bytes.
On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote: > 10.09.2018 19:55, Eric Blake wrote: >> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote: >> >>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, >>>>> int64_t end); >>>> The interface looks weird because we can define a 'start' that's beyond >>>> the 'end'. >>>> >>>> I realize that you need a signed integer for 'end' to signify EOF... >>>> should we do a 'bytes' parameter instead? (Did you already do that >>>> in an >>>> earlier version and we changed it?) >>>> >>>> Well, it's not a big deal to me personally. >>> >>> interface with constant end parameter is more comfortable for loop: >>> we don't need to update 'bytes' parameter on each iteration >> >> But there's still the question of WHO should be calculating end. Your >> interface argues for the caller: >> >> hbitmap_next_zero(start, start + bytes) >> >> int64_t hbitmap_next_zero(...) >> { >> while (offset != end) ... >> } >> >> while we're asking about a consistent interface for the caller (if >> most callers already have a 'bytes' rather than an 'end' computed): >> >> hbitmap_next_zero(start, bytes) >> >> int64_t hbitmap_next_zero(...) >> { >> int64_t end = start + bytes; >> while (offset != end) ... >> } >> > > Yes, that's an issue. Ok, if you are not comfortable with start,end, I > can switch to start,bytes. > The series looks pretty close, I can merge the next version if you think it's worth changing the interface. --js
14.09.2018 20:39, John Snow wrote: > > On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote: >> 10.09.2018 19:55, Eric Blake wrote: >>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote: >>> >>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, >>>>>> int64_t end); >>>>> The interface looks weird because we can define a 'start' that's beyond >>>>> the 'end'. >>>>> >>>>> I realize that you need a signed integer for 'end' to signify EOF... >>>>> should we do a 'bytes' parameter instead? (Did you already do that >>>>> in an >>>>> earlier version and we changed it?) >>>>> >>>>> Well, it's not a big deal to me personally. >>>> interface with constant end parameter is more comfortable for loop: >>>> we don't need to update 'bytes' parameter on each iteration >>> But there's still the question of WHO should be calculating end. Your >>> interface argues for the caller: >>> >>> hbitmap_next_zero(start, start + bytes) >>> >>> int64_t hbitmap_next_zero(...) >>> { >>> while (offset != end) ... >>> } >>> >>> while we're asking about a consistent interface for the caller (if >>> most callers already have a 'bytes' rather than an 'end' computed): >>> >>> hbitmap_next_zero(start, bytes) >>> >>> int64_t hbitmap_next_zero(...) >>> { >>> int64_t end = start + bytes; >>> while (offset != end) ... >>> } >>> >> Yes, that's an issue. Ok, if you are not comfortable with start,end, I >> can switch to start,bytes. >> > The series looks pretty close, I can merge the next version if you think > it's worth changing the interface. > > --js I've started to change interface and found a bug in bitmap_to_extents (patch sent https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html). So, next version will be based on this patch, which will go through Eric's tree..
On 09/14/2018 01:51 PM, Vladimir Sementsov-Ogievskiy wrote: > 14.09.2018 20:39, John Snow wrote: >> >> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote: >>> 10.09.2018 19:55, Eric Blake wrote: >>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote: >>>> >>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, >>>>>>> int64_t end); >>>>>> The interface looks weird because we can define a 'start' that's >>>>>> beyond >>>>>> the 'end'. >>>>>> >>>>>> I realize that you need a signed integer for 'end' to signify EOF... >>>>>> should we do a 'bytes' parameter instead? (Did you already do that >>>>>> in an >>>>>> earlier version and we changed it?) >>>>>> >>>>>> Well, it's not a big deal to me personally. >>>>> interface with constant end parameter is more comfortable for loop: >>>>> we don't need to update 'bytes' parameter on each iteration >>>> But there's still the question of WHO should be calculating end. Your >>>> interface argues for the caller: >>>> >>>> hbitmap_next_zero(start, start + bytes) >>>> >>>> int64_t hbitmap_next_zero(...) >>>> { >>>> while (offset != end) ... >>>> } >>>> >>>> while we're asking about a consistent interface for the caller (if >>>> most callers already have a 'bytes' rather than an 'end' computed): >>>> >>>> hbitmap_next_zero(start, bytes) >>>> >>>> int64_t hbitmap_next_zero(...) >>>> { >>>> int64_t end = start + bytes; >>>> while (offset != end) ... >>>> } >>>> >>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I >>> can switch to start,bytes. >>> >> The series looks pretty close, I can merge the next version if you think >> it's worth changing the interface. >> >> --js > > I've started to change interface and found a bug in bitmap_to_extents > (patch sent > https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html). > So, next version will be based on this patch, which will go through > Eric's tree.. > ah, I see. you can send it to the list anyway with the requires: header and I can have Eric stage it to make the eventual merge easier for Peter. --js
On 09/14/2018 01:51 PM, Vladimir Sementsov-Ogievskiy wrote: > 14.09.2018 20:39, John Snow wrote: >> >> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote: >>> 10.09.2018 19:55, Eric Blake wrote: >>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote: >>>> >>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); >>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, >>>>>>> int64_t end); >>>>>> The interface looks weird because we can define a 'start' that's >>>>>> beyond >>>>>> the 'end'. >>>>>> >>>>>> I realize that you need a signed integer for 'end' to signify EOF... >>>>>> should we do a 'bytes' parameter instead? (Did you already do that >>>>>> in an >>>>>> earlier version and we changed it?) >>>>>> >>>>>> Well, it's not a big deal to me personally. >>>>> interface with constant end parameter is more comfortable for loop: >>>>> we don't need to update 'bytes' parameter on each iteration >>>> But there's still the question of WHO should be calculating end. Your >>>> interface argues for the caller: >>>> >>>> hbitmap_next_zero(start, start + bytes) >>>> >>>> int64_t hbitmap_next_zero(...) >>>> { >>>> while (offset != end) ... >>>> } >>>> >>>> while we're asking about a consistent interface for the caller (if >>>> most callers already have a 'bytes' rather than an 'end' computed): >>>> >>>> hbitmap_next_zero(start, bytes) >>>> >>>> int64_t hbitmap_next_zero(...) >>>> { >>>> int64_t end = start + bytes; >>>> while (offset != end) ... >>>> } >>>> >>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I >>> can switch to start,bytes. >>> >> The series looks pretty close, I can merge the next version if you think >> it's worth changing the interface. >> >> --js > > I've started to change interface and found a bug in bitmap_to_extents > (patch sent > https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html). > So, next version will be based on this patch, which will go through > Eric's tree.. > OK, I spoke with Eric and if you resend and I R-B & ACK the patches, he'll stage them through NBD. Thanks, --js
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 259bd27c40..27f5299c4e 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs); BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, BdrvDirtyBitmap *bitmap); char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp); -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start); +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start, + int64_t end); BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs, BdrvDirtyBitmap *bitmap, Error **errp); diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index ddca52c48e..fe4dfde27a 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); /* hbitmap_next_zero: * @hb: The HBitmap to operate on * @start: The bit to start from. + * @end: End of range to search in. If @end is -1, search up to the bitmap + * end. * - * Find next not dirty bit. + * Find next not dirty bit within range [@start, @end), or from + * @start to the bitmap end if @end is -1. If not found, return -1. + * + * @end may be greater than original bitmap size, in this case, search up to + * the bitmap end. */ -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end); /* hbitmap_create_meta: * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. diff --git a/block/backup.c b/block/backup.c index 8630d32926..9bfd3f7189 100644 --- a/block/backup.c +++ b/block/backup.c @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job) break; } - offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset); + offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1); if (offset == -1) { hbitmap_set(job->copy_bitmap, cluster, end - cluster); break; diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index c9b8a6fd52..037ae62726 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp) return hbitmap_sha256(bitmap->bitmap, errp); } -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset) +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset, + int64_t end) { - return hbitmap_next_zero(bitmap->bitmap, offset); + return hbitmap_next_zero(bitmap->bitmap, offset, end); } void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src, diff --git a/nbd/server.c b/nbd/server.c index ea5fe0eb33..07920d123b 100644 --- a/nbd/server.c +++ b/nbd/server.c @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, assert(begin < overall_end && nb_extents); while (begin < overall_end && i < nb_extents) { if (dirty) { - end = bdrv_dirty_bitmap_next_zero(bitmap, begin); + end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1); } else { bdrv_set_dirty_iter(it, begin); end = bdrv_dirty_iter_next(it); diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 5e67ac1d3a..6b6a40bddd 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) { - int64_t ret1 = hbitmap_next_zero(data->hb, start); + int64_t ret1 = hbitmap_next_zero(data->hb, start, -1); int64_t ret2 = start; for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) { ; diff --git a/util/hbitmap.c b/util/hbitmap.c index bcd304041a..1687372504 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -53,6 +53,9 @@ */ struct HBitmap { + /* Size of the bitmap, as requested in hbitmap_alloc. */ + uint64_t orig_size; + /* Number of total bits in the bottom level. */ uint64_t size; @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) } } -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end) { size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; - uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1]; unsigned long cur = last_lev[pos]; - unsigned start_bit_offset = - (start >> hb->granularity) & (BITS_PER_LONG - 1); + unsigned start_bit_offset; + uint64_t end_bit, sz; int64_t res; + if (start >= hb->orig_size || (end != -1 && end <= start)) { + return -1; + } + + end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1; + sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; + + /* There may be some zero bits in @cur before @start. We are not interested + * in them, let's set them. + */ + start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); cur |= (1UL << start_bit_offset) - 1; assert((start >> hb->granularity) < hb->size); @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) } res = (pos << BITS_PER_LEVEL) + ctol(cur); - if (res >= hb->size) { + if (res >= end_bit) { return -1; } @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity) HBitmap *hb = g_new0(struct HBitmap, 1); unsigned i; + hb->orig_size = size; + assert(granularity >= 0 && granularity < 64); size = (size + (1ULL << granularity) - 1) >> granularity; assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
Add bytes parameter to the function, to limit searched range. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> --- include/block/dirty-bitmap.h | 3 ++- include/qemu/hbitmap.h | 10 ++++++++-- block/backup.c | 2 +- block/dirty-bitmap.c | 5 +++-- nbd/server.c | 2 +- tests/test-hbitmap.c | 2 +- util/hbitmap.c | 25 ++++++++++++++++++++----- 7 files changed, 36 insertions(+), 13 deletions(-)