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

[Eric Blake]

On 08/03/2018 12:46 PM, Vladimir Sementsov-Ogievskiy wrote:
> Add bytes parameter to the function, to limit searched range.
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <address@hidden>
> ---
>   include/block/dirty-bitmap.h |  3 ++-
>   include/qemu/hbitmap.h       |  7 +++++--
>   block/backup.c               |  2 +-
>   block/dirty-bitmap.c         |  5 +++--
>   nbd/server.c                 |  2 +-
>   util/hbitmap.c               | 13 ++++++++++---
>   6 files changed, 22 insertions(+), 10 deletions(-)

> +++ b/include/qemu/hbitmap.h
> @@ -295,10 +295,13 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>   /* hbitmap_next_zero:
>    * @hb: The HBitmap to operate on
>    * @start: The bit to start from.
> + * @bytes: Range length to search in. If @bytes is zero, search up to the 
> bitmap
> + *         end.
>    *
> - * Find next not dirty bit.
> + * Find next not dirty bit within range address@hidden, @start + @bytes), or 
> from
> + * @start to the bitmap end if @bytes is zero.

Can @bytes (or rather, @start + @bytes) exceed the remaining bitmap 
length (in which case it is silently truncated to the remaining length)?

> +++ b/util/hbitmap.c
> @@ -192,16 +192,23 @@ 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, uint64_t bytes)
>   {
>       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];
> +    uint64_t end_bit =
> +            bytes ? ((start + bytes - 1) >> hb->granularity) + 1 : hb->size;

This computation can overflow if bytes is too large...

> +    uint64_t sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
>       unsigned long cur = last_lev[pos];
>       unsigned start_bit_offset =
>               (start >> hb->granularity) & (BITS_PER_LONG - 1);
>       int64_t res;
>   
> +    assert(!bytes || start + bytes <= (hb->size << hb->granularity));

and only now are you asserting that bytes was in range.  You should at 
least document that bytes must be in range, and while I don't see any 
memory dereferences dependent on a potentially bogus end_bit value, it 
may also be worth hoisting the assert sooner in the function.


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