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

[John Snow <jsnow@redhat.com>]

On 04/17/2015 11:23 AM, Eric Blake wrote:
> 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.
>

Unfortunately, our bitmaps may indeed be colossal. uint32_t would 
suffice for 32bit, but 64bit bitmaps tolerate up to 2^41 bits, which is 
still a ULL size of 2^35, so just a little bit too big for us.

We will never hit this in practice (for this usage, anyway) but I'd 
rather not nerf the base class unnecessarily, so I'll just expand out 
the index here.

Thanks for the good catch.

--js