Merge remote-tracking branch 'remotes/jnsnow/tags/bitmaps-pull-request' into staging

Pull request

# gpg: Signature made Wed 16 Jan 2019 01:00:25 GMT
# gpg:                using RSA key 7DEF8106AAFC390E
# gpg: Good signature from "John Snow (John Huston) <jsnow@redhat.com>"
# Primary key fingerprint: FAEB 9711 A12C F475 812F  18F2 88A9 064D 1835 61EB
#      Subkey fingerprint: F9B7 ABDB BCAC DF95 BE76  CBD0 7DEF 8106 AAFC 390E

* remotes/jnsnow/tags/bitmaps-pull-request:
  Revert "hbitmap: Add @advance param to hbitmap_iter_next()"
  Revert "test-hbitmap: Add non-advancing iter_next tests"
  Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"
  block/mirror: fix and improve do_sync_target_write
  tests: add tests for hbitmap_next_dirty_area
  dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area
  tests: add tests for hbitmap_next_zero with specified end parameter
  dirty-bitmap: improve bdrv_dirty_bitmap_next_zero

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>

1 files changed, 148 insertions, 29 deletions

diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 5e67ac1d3a..592d8219db 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -30,18 +30,6 @@ typedef struct TestHBitmapData {
 } TestHBitmapData;
 
 
-static int64_t check_hbitmap_iter_next(HBitmapIter *hbi)
-{
-    int next0, next1;
-
-    next0 = hbitmap_iter_next(hbi, false);
-    next1 = hbitmap_iter_next(hbi, true);
-
-    g_assert_cmpint(next0, ==, next1);
-
-    return next0;
-}
-
 /* Check that the HBitmap and the shadow bitmap contain the same data,
  * ignoring the same "first" bits.
  */
@@ -58,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
 
     i = first;
     for (;;) {
-        next = check_hbitmap_iter_next(&hbi);
+        next = hbitmap_iter_next(&hbi);
         if (next < 0) {
             next = data->size;
         }
@@ -447,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
     hbitmap_test_init(data, 131072 << 7, 7);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_test_set(data, (131072 << 7) - 8, 8);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 }
 
 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
@@ -905,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
     for (i = 0; i < num_positions; i++) {
         hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
         hbitmap_iter_init(&iter, data->hb, 0);
-        next = check_hbitmap_iter_next(&iter);
+        next = hbitmap_iter_next(&iter);
         if (i == num_positions - 1) {
             g_assert_cmpint(next, ==, -1);
         } else {
@@ -931,37 +919,55 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
 
     hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
 
-    check_hbitmap_iter_next(&hbi);
+    hbitmap_iter_next(&hbi);
 
     hbitmap_reset_all(data->hb);
-    check_hbitmap_iter_next(&hbi);
+    hbitmap_iter_next(&hbi);
 }
 
-static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
+                                               uint64_t start,
+                                               uint64_t count)
 {
-    int64_t ret1 = hbitmap_next_zero(data->hb, start);
+    int64_t ret1 = hbitmap_next_zero(data->hb, start, count);
     int64_t ret2 = start;
-    for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
+    int64_t end = start >= data->size || data->size - start < count ?
+                data->size : start + count;
+
+    for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) {
         ;
     }
-    if (ret2 == data->size) {
+    if (ret2 == end) {
         ret2 = -1;
     }
 
     g_assert_cmpint(ret1, ==, ret2);
 }
 
+static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+{
+    test_hbitmap_next_zero_check_range(data, start, UINT64_MAX);
+}
+
 static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
 {
     hbitmap_test_init(data, L3, granularity);
     test_hbitmap_next_zero_check(data, 0);
     test_hbitmap_next_zero_check(data, L3 - 1);
+    test_hbitmap_next_zero_check_range(data, 0, 1);
+    test_hbitmap_next_zero_check_range(data, L3 - 1, 1);
 
     hbitmap_set(data->hb, L2, 1);
     test_hbitmap_next_zero_check(data, 0);
     test_hbitmap_next_zero_check(data, L2 - 1);
     test_hbitmap_next_zero_check(data, L2);
     test_hbitmap_next_zero_check(data, L2 + 1);
+    test_hbitmap_next_zero_check_range(data, 0, 1);
+    test_hbitmap_next_zero_check_range(data, 0, L2);
+    test_hbitmap_next_zero_check_range(data, L2 - 1, 1);
+    test_hbitmap_next_zero_check_range(data, L2 - 1, 2);
+    test_hbitmap_next_zero_check_range(data, L2, 1);
+    test_hbitmap_next_zero_check_range(data, L2 + 1, 1);
 
     hbitmap_set(data->hb, L2 + 5, L1);
     test_hbitmap_next_zero_check(data, 0);
@@ -970,6 +976,10 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
     test_hbitmap_next_zero_check(data, L2 + 5);
     test_hbitmap_next_zero_check(data, L2 + L1 - 1);
     test_hbitmap_next_zero_check(data, L2 + L1);
+    test_hbitmap_next_zero_check_range(data, L2, 6);
+    test_hbitmap_next_zero_check_range(data, L2 + 1, 3);
+    test_hbitmap_next_zero_check_range(data, L2 + 4, L1);
+    test_hbitmap_next_zero_check_range(data, L2 + 5, L1);
 
     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
     test_hbitmap_next_zero_check(data, L2 * 2 - L1);
@@ -977,6 +987,8 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
     test_hbitmap_next_zero_check(data, L2 * 2 - 1);
     test_hbitmap_next_zero_check(data, L2 * 2);
     test_hbitmap_next_zero_check(data, L3 - 1);
+    test_hbitmap_next_zero_check_range(data, L2 * 2 - L1, L1 + 1);
+    test_hbitmap_next_zero_check_range(data, L2 * 2, L2);
 
     hbitmap_set(data->hb, 0, L3);
     test_hbitmap_next_zero_check(data, 0);
@@ -992,6 +1004,106 @@ static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
     test_hbitmap_next_zero_do(data, 4);
 }
 
+static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
+                                               uint64_t offset,
+                                               uint64_t count)
+{
+    uint64_t off1, off2;
+    uint64_t len1 = 0, len2;
+    bool ret1, ret2;
+    int64_t end;
+
+    off1 = offset;
+    len1 = count;
+    ret1 = hbitmap_next_dirty_area(data->hb, &off1, &len1);
+
+    end = offset > data->size || data->size - offset < count ? data->size :
+                                                               offset + count;
+
+    for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) {
+        ;
+    }
+
+    for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
+         len2++) {
+        ;
+    }
+
+    ret2 = off2 < end;
+    if (!ret2) {
+        /* leave unchanged */
+        off2 = offset;
+        len2 = count;
+    }
+
+    g_assert_cmpint(ret1, ==, ret2);
+    g_assert_cmpint(off1, ==, off2);
+    g_assert_cmpint(len1, ==, len2);
+}
+
+static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
+                                            int granularity)
+{
+    hbitmap_test_init(data, L3, granularity);
+    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, 0, 1);
+    test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
+
+    hbitmap_set(data->hb, L2, 1);
+    test_hbitmap_next_dirty_area_check(data, 0, 1);
+    test_hbitmap_next_dirty_area_check(data, 0, L2);
+    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 - 1, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 - 1, 1);
+    test_hbitmap_next_dirty_area_check(data, L2 - 1, 2);
+    test_hbitmap_next_dirty_area_check(data, L2 - 1, 3);
+    test_hbitmap_next_dirty_area_check(data, L2, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2, 1);
+    test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
+
+    hbitmap_set(data->hb, L2 + 5, L1);
+    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 - 2, 8);
+    test_hbitmap_next_dirty_area_check(data, L2 + 1, 5);
+    test_hbitmap_next_dirty_area_check(data, L2 + 1, 3);
+    test_hbitmap_next_dirty_area_check(data, L2 + 4, L1);
+    test_hbitmap_next_dirty_area_check(data, L2 + 5, L1);
+    test_hbitmap_next_dirty_area_check(data, L2 + 7, L1);
+    test_hbitmap_next_dirty_area_check(data, L2 + L1, L1);
+    test_hbitmap_next_dirty_area_check(data, L2, 0);
+    test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
+
+    hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
+    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 + 1, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, UINT64_MAX);
+    test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
+    test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
+    test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
+
+    hbitmap_set(data->hb, 0, L3);
+    test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
+}
+
+static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
+                                           const void *unused)
+{
+    test_hbitmap_next_dirty_area_do(data, 0);
+}
+
+static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data,
+                                           const void *unused)
+{
+    test_hbitmap_next_dirty_area_do(data, 1);
+}
+
+static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data,
+                                           const void *unused)
+{
+    test_hbitmap_next_dirty_area_do(data, 4);
+}
+
 int main(int argc, char **argv)
 {
     g_test_init(&argc, &argv, NULL);
@@ -1058,6 +1170,13 @@ int main(int argc, char **argv)
     hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
                      test_hbitmap_next_zero_4);
 
+    hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0",
+                     test_hbitmap_next_dirty_area_0);
+    hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_1",
+                     test_hbitmap_next_dirty_area_1);
+    hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_4",
+                     test_hbitmap_next_dirty_area_4);
+
     g_test_run();
 
     return 0;