Re: [Qemu-devel] [PATCH for-2.8 v2] hbitmap: Fix shifts of constants by granularity

[Fam Zheng <famz@redhat.com>]

On Tue, 11/15 23:47, Max Reitz wrote:
> An hbitmap's granularity may be anything from 0 to 63, so when shifting
> constants by its value, they should not be plain ints.
> 
> Even having changed the types, hbitmap_serialization_granularity() still
> tries to shift 64 to the right by the granularity. This operation is
> undefined if the granularity is greater than 57. Adding an assertion is
> fine for now, because serializing is done only in tests so far, but this
> means that only bitmaps with a granularity below 58 can be serialized
> and we should thus add a hbitmap_is_serializable() function later.
> 
> One of the two places touched in this patch uses
> QEMU_ALIGN_UP(x, 1 << y). We can use ROUND_UP() there, since the second
> parameter is obviously a power of two.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
> v2:
> - Fix the same issue in hbitmap_truncate() [Stefan]
> - Use ROUND_UP() instead of QEMU_ALIGN_UP() there (because we can)
> - Add an assertion to hbitmap_serialization_granularity() guaranteeing
>   that the shift doesn't overflow; we can guarantee this so far because
>   the only place where serialization functions are used in is the
>   hbitmap test
>   (I'll send a follow-up patch to allow users to check whether a certain
>   bitmap can be (de-)serialized)

Thanks, queued.

I'll send a pull request soon.

Fam

> ---
>  util/hbitmap.c | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)
> 
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 5d1a21c..9f691b7 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -399,9 +399,13 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
>  
>  uint64_t hbitmap_serialization_granularity(const HBitmap *hb)
>  {
> +    /* Must hold true so that the shift below is defined
> +     * (ld(64) == 6, i.e. 1 << 6 == 64) */
> +    assert(hb->granularity < 64 - 6);
> +
>      /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit
>       * hosts. */
> -    return 64 << hb->granularity;
> +    return UINT64_C(64) << hb->granularity;
>  }
>  
>  /* Start should be aligned to serialization granularity, chunk size should be
> @@ -594,7 +598,7 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
>      if (shrink) {
>          /* Don't clear partial granularity groups;
>           * start at the first full one. */
> -        uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
> +        uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
>          uint64_t fix_count = (hb->size << hb->granularity) - start;
>  
>          assert(fix_count);
> -- 
> 2.10.2
>