Re: [Qemu-block] [Qemu-devel] [PATCH COLO v3 10/14] util/hbitmap: Add an API to reset all set bits in hbitmap
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
> Signed-off-by: zhanghailiang
> Signed-off-by: Gonglei
> ---
> 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
> #include
> +#include
> #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_cl
Re: [Qemu-block] [Qemu-devel] [PATCH COLO v3 10/14] util/hbitmap: Add an API to reset all set bits in hbitmap
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
Signed-off-by: zhanghailiang
Signed-off-by: Gonglei
---
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
#include
+#include
#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
