Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero

[Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>]

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

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

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

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

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


-- 
Best regards,
Vladimir