| Message ID | 1428055280-12015-11-git-send-email-wency@cn.fujitsu.com |
|---|---|
| State | New |
| Headers | show |
On 03/04/2015 12:01, Wen Congyang wrote: > Signed-off-by: Wen Congyang <wency@cn.fujitsu.com> > Signed-off-by: zhanghailiang <zhang.zhanghailiang@huawei.com> > Signed-off-by: Gonglei <arei.gonglei@huawei.com> > --- > 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)); > + } > + > + 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 <pbonzini@redhat.com>
On 04/03/2015 07:05 AM, Paolo Bonzini wrote: > > > On 03/04/2015 12:01, Wen Congyang wrote: >> Signed-off-by: Wen Congyang <wency@cn.fujitsu.com> >> Signed-off-by: zhanghailiang <zhang.zhanghailiang@huawei.com> >> Signed-off-by: Gonglei <arei.gonglei@huawei.com> >> --- >> 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. >> + 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 <pbonzini@redhat.com> >
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 <wency@cn.fujitsu.com> >>> Signed-off-by: zhanghailiang <zhang.zhanghailiang@huawei.com> >>> Signed-off-by: Gonglei <arei.gonglei@huawei.com> >>> --- >>> 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 > >>> + 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 <pbonzini@redhat.com> >> > . >
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 <wency@cn.fujitsu.com> >>>> Signed-off-by: zhanghailiang <zhang.zhanghailiang@huawei.com> >>>> Signed-off-by: Gonglei <arei.gonglei@huawei.com> >>>> --- >>>> 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 <pbonzini@redhat.com> >>> >> . >> > >
On 05/08/2015 02:32 AM, John Snow wrote: > > > 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 <wency@cn.fujitsu.com> >>>>> Signed-off-by: zhanghailiang <zhang.zhanghailiang@huawei.com> >>>>> Signed-off-by: Gonglei <arei.gonglei@huawei.com> >>>>> --- >>>>> 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. OK, I will do it. Thanks Wen Congyang > > 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 <pbonzini@redhat.com> >>>> >>> . >>> >> >> > . >
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)); + } + + 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. */