Re: [Qemu-block] [Qemu-devel] [PATCH COLO v3 10/14] util/hbitmap: Add an API to reset all set bits in hbitmap

[John Snow]

On 05/06/2015 10:20 PM, Wen Congyang wrote:
> On 05/02/2015 12:47 AM, John Snow wrote:
>>
>>
>> On 04/03/2015 07:05 AM, Paolo Bonzini wrote:
>>>
>>>
>>> On 03/04/2015 12:01, Wen Congyang wrote:
>>>> Signed-off-by: Wen Congyang <address@hidden>
>>>> Signed-off-by: zhanghailiang <address@hidden>
>>>> Signed-off-by: Gonglei <address@hidden>
>>>> ---
>>>>   include/qemu/hbitmap.h |  8 ++++++++
>>>>   tests/test-hbitmap.c   | 39 +++++++++++++++++++++++++++++++++++++++
>>>>   util/hbitmap.c         | 16 ++++++++++++++++
>>>>   3 files changed, 63 insertions(+)
>>>>
>>>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>>>> index 550d7ce..95a55e4 100644
>>>> --- a/include/qemu/hbitmap.h
>>>> +++ b/include/qemu/hbitmap.h
>>>> @@ -109,6 +109,14 @@ void hbitmap_set(HBitmap *hb, uint64_t start, 
>>>> uint64_t count);
>>>>   void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
>>>>
>>>>   /**
>>>> + * hbitmap_reset_all:
>>>> + * @hb: HBitmap to operate on.
>>>> + *
>>>> + * Reset all bits in an HBitmap.
>>>> + */
>>>> +void hbitmap_reset_all(HBitmap *hb);
>>>> +
>>>> +/**
>>>>    * hbitmap_get:
>>>>    * @hb: HBitmap to operate on.
>>>>    * @item: Bit to query (0-based).
>>>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>>>> index 8c902f2..1f0078a 100644
>>>> --- a/tests/test-hbitmap.c
>>>> +++ b/tests/test-hbitmap.c
>>>> @@ -11,6 +11,7 @@
>>>>
>>>>   #include <glib.h>
>>>>   #include <stdarg.h>
>>>> +#include <string.h>
>>>>   #include "qemu/hbitmap.h"
>>>>
>>>>   #define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)
>>>> @@ -143,6 +144,23 @@ static void hbitmap_test_reset(TestHBitmapData *data,
>>>>       }
>>>>   }
>>>>
>>>> +static void hbitmap_test_reset_all(TestHBitmapData *data)
>>>> +{
>>>> +    size_t n;
>>>> +
>>>> +    hbitmap_reset_all(data->hb);
>>>> +
>>>> +    n = (data->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
>>>> +    if (n == 0) {
>>>> +        n = 1;
>>>> +    }
>>>> +    memset(data->bits, 0, n * sizeof(unsigned long));
>>>> +
>>>> +    if (data->granularity == 0) {
>>>> +        hbitmap_test_check(data, 0);
>>>> +    }
>>>> +}
>>>> +
>>>>   static void hbitmap_test_check_get(TestHBitmapData *data)
>>>>   {
>>>>       uint64_t count = 0;
>>>> @@ -323,6 +341,26 @@ static void test_hbitmap_reset(TestHBitmapData *data,
>>>>       hbitmap_test_set(data, L3 / 2, L3);
>>>>   }
>>>>
>>>> +static void test_hbitmap_reset_all(TestHBitmapData *data,
>>>> +                                   const void *unused)
>>>> +{
>>>> +    hbitmap_test_init(data, L3 * 2, 0);
>>>> +    hbitmap_test_set(data, L1 - 1, L1 + 2);
>>>> +    hbitmap_test_reset_all(data);
>>>> +    hbitmap_test_set(data, 0, L1 * 3);
>>>> +    hbitmap_test_reset_all(data);
>>>> +    hbitmap_test_set(data, L2, L1);
>>>> +    hbitmap_test_reset_all(data);
>>>> +    hbitmap_test_set(data, L2, L3 - L2 + 1);
>>>> +    hbitmap_test_reset_all(data);
>>>> +    hbitmap_test_set(data, L3 - 1, 3);
>>>> +    hbitmap_test_reset_all(data);
>>>> +    hbitmap_test_set(data, 0, L3 * 2);
>>>> +    hbitmap_test_reset_all(data);
>>>> +    hbitmap_test_set(data, L3 / 2, L3);
>>>> +    hbitmap_test_reset_all(data);
>>>> +}
>>>> +
>>>>   static void test_hbitmap_granularity(TestHBitmapData *data,
>>>>                                        const void *unused)
>>>>   {
>>>> @@ -394,6 +432,7 @@ int main(int argc, char **argv)
>>>>       hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
>>>>       hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
>>>>       hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
>>>> +    hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
>>>>       hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
>>>>       g_test_run();
>>>>
>>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>>> index ab13971..acce93c 100644
>>>> --- a/util/hbitmap.c
>>>> +++ b/util/hbitmap.c
>>>> @@ -353,6 +353,22 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, 
>>>> uint64_t count)
>>>>       hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
>>>>   }
>>>>
>>>> +void hbitmap_reset_all(HBitmap *hb)
>>>> +{
>>>> +    uint64_t size = hb->size;
>>>> +    unsigned int i;
>>>> +
>>>> +    /* Same as hbitmap_alloc() except memset() */
>>>> +    for (i = HBITMAP_LEVELS; --i >= 1; ) {
>>>> +        size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
>>>> +        memset(hb->levels[i], 0, size * sizeof(unsigned long));
>>>> +    }
>>>> +
>>
>> For what it's worth, I recently added in a hb->sizes[i] cache to store the 
>> size of each array so you don't have to recompute this all the time.
> 
> Yes, will fix it in the next version.
> 
> Thanks
> Wen Congyang
> 

Since the reset stuff is useful all by itself, you can send that patch
by itself, CC me, and I'll review it.

You can update the existing call in block.c:

bdrv_clear_dirty_bitmap() {
    hbitmap_reset(bitmap->bitmap, 0, bitmap->size);
}

to using your faster hbitmap_reset_all call.

Thanks,

--js

>>
>>>> +    assert(size == 1);
>>>> +    hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
>>>> +    hb->count = 0;
>>>> +}
>>>> +
>>>>   bool hbitmap_get(const HBitmap *hb, uint64_t item)
>>>>   {
>>>>       /* Compute position and bit in the last layer.  */
>>>>
>>>
>>> Acked-by: Paolo Bonzini <address@hidden>
>>>
>> .
>>
> 
>