Re: [Qemu-devel] [PATCH v5 07/21] hbitmap: add hbitmap_merge

[Eric Blake <eblake@redhat.com>]

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

On 04/08/2015 04:19 PM, John Snow wrote:
> We add a bitmap merge operation to assist in error cases
> where we wish to combine two bitmaps together.
> 
> This is algorithmically O(bits) provided HBITMAP_LEVELS remains
> constant. For a full bitmap on a 64bit machine:
> sum(bits/64^k, k, 0, HBITMAP_LEVELS) ~= 1.01587 * bits
> 
> We may be able to improve running speed for particularly sparse
> bitmaps by using iterators, but the running time for dense maps
> will be worse.
> 
> We present the simpler solution first, and we can refine it later
> if needed.
> 
> Signed-off-by: John Snow <jsnow@redhat.com>
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
> ---

>  /**
> + * hbitmap_merge:
> + * @a: The bitmap to store the result in.
> + * @b: The bitmap to merge into @a.
> + *
> + * Merge two bitmaps together.
> + * A := A (BITOR) B.
> + * B is left unmodified.
> + */
> +bool hbitmap_merge(HBitmap *a, const HBitmap *b);

No mention of what the return value means.


> +bool hbitmap_merge(HBitmap *a, const HBitmap *b)
> +{
> +    int i, j;
> +
> +    if ((a->size != b->size) || (a->granularity != b->granularity)) {
> +        return false;
> +    }
> +
> +    if (hbitmap_count(b) == 0) {
> +        return true;
> +    }
> +
> +    /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
> +     * It may be possible to improve running times for sparsely populated maps
> +     * by using hbitmap_iter_next, but this is suboptimal for dense maps.
> +     */
> +    for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
> +        for (j = 0; j < a->sizes[i]; j++) {

j is 'int', but a->sizes[i] is uint64_t.  If we can ever have a bitmap
large enough that its size exceeds 2G at the largest level, then we have
an inf-loop due to overflow problem.

I'd feel safer if you make j be uint64_t here; but it might also be
possible to fix 6/21 to store sizes in a smaller data type along with
appropriate assertions that our bitmaps are never big enough to need a
level with more than 2G size.

-- 
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: 604 bytes --]