Re: [Qemu-devel] [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate

[John Snow <jsnow@redhat.com>]

On 04/07/2015 08:57 AM, Stefan Hajnoczi wrote:
> On Thu, Apr 02, 2015 at 11:57:59AM -0400, John Snow wrote:
>>
>>
>> On 04/02/2015 09:37 AM, Stefan Hajnoczi wrote:
>>> On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote:
>>>> +void hbitmap_truncate(HBitmap *hb, uint64_t size)
>>>> +{
>>>> +    bool shrink;
>>>> +    unsigned i;
>>>> +    uint64_t num_elements = size;
>>>> +    uint64_t old;
>>>> +
>>>> +    /* Size comes in as logical elements, adjust for granularity. */
>>>> +    size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
>>>> +    assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
>>>> +    shrink = size < hb->size;
>>>> +
>>>> +    /* bit sizes are identical; nothing to do. */
>>>> +    if (size == hb->size) {
>>>> +        return;
>>>> +    }
>>>> +
>>>> +    /* If we're losing bits, let's clear those bits before we invalidate all of
>>>> +     * our invariants. This helps keep the bitcount consistent, and will prevent
>>>> +     * us from carrying around garbage bits beyond the end of the map.
>>>> +     *
>>>> +     * Because clearing bits past the end of map might reset bits we care about
>>>> +     * within the array, record the current value of the last bit we're keeping.
>>>> +     */
>>>> +    if (shrink) {
>>>> +        bool set = hbitmap_get(hb, num_elements - 1);
>>>> +        uint64_t fix_count = (hb->size << hb->granularity) - num_elements;
>>>> +
>>>> +        assert(fix_count);
>>>> +        hbitmap_reset(hb, num_elements, fix_count);
>>>> +        if (set) {
>>>> +            hbitmap_set(hb, num_elements - 1, 1);
>>>> +        }
>>>
>>> Why is it necessary to set the last bit (if it was set)?  The comment
>>> isn't clear to me.
>>>
>>
>> Sure. The granularity of the bitmap provides us with virtual bit groups. for
>> a granularity of say g=2, we have 2^2 virtual bits per every real bit:
>>
>> 101 in memory is treated, virtually, as 1111 0000 1111.
>>
>> The get/set calls operate on virtual bits, not concrete ones, so if we were
>> to reset virtual bits 2-11:
>> 11|11 0000 1111
>>
>> We'd set the real bits to '000', because we clear or set the entire virtual
>> group.
>>
>> This is probably not what we really want, so as a shortcut I just read and
>> then re-set the final bit.
>>
>> It is programmatically avoidable (Are we truncating into a granularity
>> group?) but in the case that we are, I'd need to read/reset the bit anyway,
>> so it seemed fine to just unconditionally apply the fix.
>
> I see.  This is equivalent to:
>
> uint64_t start = QEMU_ALIGN_UP(num_elements, hb->granularity);

Probably you mean QEMU_ALIGN_UP(num_elements, 1 << hb->granularity)

> uint64_t fix_count = (hb->size << hb->granularity) - start;
> hbitmap_reset(hb, start, fix_count);
>
> The explicit QEMU_ALIGN_UP(num_elements, hb->granularity) calculation
> shows that we're working around the granularity.  I find this easier to
> understand.
>
> If you keep the get/set version, please extend the comment to explain
> that clearing the first bit could destroy up to granularity - 1 bits
> that must be preserved.
>

Your solution will read more nicely, so I'll just adopt that, thanks.

> Stefan
>