Re: [Qemu-devel] [PATCH 14/20] hbitmap: add hbitmap_alloc_with_data and hbitmap_required_size

[Eric Blake <eblake@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 2452 bytes --]

On 12/12/2012 06:46 AM, Paolo Bonzini wrote:
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
> ---
>  hbitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++----------
>  hbitmap.h | 25 +++++++++++++++++++++++++
>  2 files changed, 72 insertions(+), 10 deletions(-)

When using hbitmap_alloc_with_data, must the user pass in all 0 data, or
do you do a one-time slow pass over the passed-in data to populate the
remaining layers of the hbitmap to allow faster traversal later?

> +HBitmap *hbitmap_alloc_with_data(uint64_t size, int granularity, void *data)
> +{
> +    HBitmap *hb = g_malloc0(sizeof(struct HBitmap));
> +    unsigned i;
> +
> +    hb->size = hbitmap_round_size(size, granularity);
>      hb->granularity = granularity;
> +    hb->last_level_allocated = (data == NULL);
> +
>      for (i = HBITMAP_LEVELS; i-- > 0; ) {
> -        size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
> -        hb->levels[i] = g_malloc0(size * sizeof(unsigned long));
> +        if (data == NULL) {
> +            data = g_malloc0(hbitmap_required_size(size, granularity));
> +        }
> +        hb->levels[i] = data;
> +        data = NULL;
> +        granularity += BITS_PER_LEVEL;
>      }
>  
>      /* We necessarily have free bits in level 0 due to the definition
>       * of HBITMAP_LEVELS, so use one for a sentinel.  This speeds up
>       * hbitmap_iter_skip_words.
>       */
> -    assert(size == 1);
> +    assert(hbitmap_required_size(size, granularity) == sizeof(unsigned long));
>      hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
>      return hb;
>  }

Based on the implementation, you aren't inspecting the contents of data.

> +/**
> + * hbitmap_alloc_with_data:
> + * @size: Number of bits in the bitmap.
> + * @granularity: Granularity of the bitmap.
> + * @data: Pointer to a data block that will be used for the bottom level
> + * of the HBitmap.
> + *
> + * Allocate a new HBitmap, using a client-provided data block for the
> + * actual bitmap and allocating memory only for the compressed levels.
> + * If @data is NULL, this function is equivalent to @hbitmap_alloc.
> + */
> +HBitmap *hbitmap_alloc_with_data(uint64_t size, int granularity, void *data);

But this documentation didn't mention that the caller must pass in all 0s.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]