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

2015-05-06 Thread Wen Congyang 
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 we...@cn.fujitsu.com
 Signed-off-by: zhanghailiang zhang.zhanghaili...@huawei.com
 Signed-off-by: Gonglei arei.gong...@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 pbonz...@redhat.com

 .

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

2015-05-01 Thread John Snow 



On 04/03/2015 07:05 AM, Paolo Bonzini wrote:



On 03/04/2015 12:01, Wen Congyang wrote:

Signed-off-by: Wen Congyang we...@cn.fujitsu.com
Signed-off-by: zhanghailiang zhang.zhanghaili...@huawei.com
Signed-off-by: Gonglei arei.gong...@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 pbonz...@redhat.com

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

2015-04-03 Thread Wen Congyang 
Signed-off-by: Wen Congyang we...@cn.fujitsu.com
Signed-off-by: zhanghailiang zhang.zhanghaili...@huawei.com
Signed-off-by: Gonglei arei.gong...@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.  */
-- 
2.1.0