From nobody Wed Nov 12 10:09:30 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=virtuozzo.com ARC-Seal: i=1; a=rsa-sha256; t=1569857829; cv=none; d=zoho.com; s=zohoarc; b=kxTwfi13gD76HkRa2egwSVwvFwWFgB9osCJjIXF+hO6CF7H/6dSN/lqvuAPT7BwfCNuLcm/SNkCDI/a9TqeaZDPRGp7SoF7JjwOAYnMHLQ8XJUuB2KhHqb6h2W2AnWEwyBelFj4ZIs/qOrnPNEun8vPsRHCtEF4a8RB7hFF8joQ= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1569857829; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To:ARC-Authentication-Results; bh=A3W3hpWBWP5JFl6c6Dj+aY6Poxc6uFiQ0uzGE2ENR3A=; b=Sxn4arDGPZdcf1WDD572WQHd+qU6vXcoxQg2tNUAJjgADaLkbeO6LuOQmkY3HgvIOBIg7Rmabq6SFv5gVgeeaxhQgQUOqbCArro1wtRVayC1Xt2kVONI2zBwp3hItw5Qubay72VT1fEYX96mQjNxww4deCa9+GX0xtQKhVEC2ck= ARC-Authentication-Results: i=1; mx.zoho.com; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 15698578290604.446750088280396; Mon, 30 Sep 2019 08:37:09 -0700 (PDT) Received: from localhost ([::1]:53876 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iExjX-0003LI-LR for importer@patchew.org; Mon, 30 Sep 2019 11:37:07 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:60188) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iExOO-0004gJ-4d for qemu-devel@nongnu.org; Mon, 30 Sep 2019 11:15:17 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iExOM-000602-1h for qemu-devel@nongnu.org; Mon, 30 Sep 2019 11:15:15 -0400 Received: from relay.sw.ru ([185.231.240.75]:46674) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iExOF-0005ou-8Y; Mon, 30 Sep 2019 11:15:07 -0400 Received: from [10.94.3.0] (helo=kvm.qa.sw.ru) by relay.sw.ru with esmtp (Exim 4.92.2) (envelope-from ) id 1iExOC-0005tD-2g; Mon, 30 Sep 2019 18:15:04 +0300 From: Vladimir Sementsov-Ogievskiy To: qemu-block@nongnu.org Subject: [PATCH 06/10] block/dirty-bitmap: add _next_dirty API Date: Mon, 30 Sep 2019 18:14:58 +0300 Message-Id: <20190930151502.7829-7-vsementsov@virtuozzo.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20190930151502.7829-1-vsementsov@virtuozzo.com> References: <20190930151502.7829-1-vsementsov@virtuozzo.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 185.231.240.75 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: kwolf@redhat.com, fam@euphon.net, vsementsov@virtuozzo.com, qemu-devel@nongnu.org, mreitz@redhat.com, den@openvz.org, jsnow@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" Content-Type: text/plain; charset="utf-8" We have bdrv_dirty_bitmap_next_zero, let's add corresponding bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than bitmap iterators in some cases. For test modify test_hbitmap_next_zero_check_range to check both next_zero and next_dirty and add some new checks. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/block/dirty-bitmap.h | 2 + include/qemu/hbitmap.h | 13 ++++ block/dirty-bitmap.c | 6 ++ tests/test-hbitmap.c | 130 ++++++++++++++++++++--------------- util/hbitmap.c | 60 ++++++++-------- 5 files changed, 126 insertions(+), 85 deletions(-) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 96d3cc0800..333e44e793 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -103,6 +103,8 @@ for (bitmap =3D bdrv_dirty_bitmap_first(bs); bitmap; \ bitmap =3D bdrv_dirty_bitmap_next(bitmap)) =20 char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp= ); +int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offs= et, + int64_t bytes); int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offse= t, int64_t bytes); bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 6eb2728a21..eeecd33f01 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -304,6 +304,19 @@ void hbitmap_free(HBitmap *hb); */ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first= ); =20 +/* + * hbitmap_next_dirty: + * + * Find next dirty bit within selected range. If not found, return -1. + * + * @hb: The HBitmap to operate on + * @start: The bit to start from. + * @count: Number of bits to proceed. If @start+@count > bitmap size, the = whole + * bitmap is looked through. You can use UINT64_MAX as @count to search up= to + * the bitmap end. + */ +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count= ); + /* hbitmap_next_zero: * * Find next not dirty bit within selected range. If not found, return -1. diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index 01135f623e..fe2420b297 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -854,6 +854,12 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *= bitmap, Error **errp) return hbitmap_sha256(bitmap->bitmap, errp); } =20 +int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offs= et, + int64_t bytes) +{ + return hbitmap_next_dirty(bitmap->bitmap, offset, bytes); +} + int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offse= t, int64_t bytes) { diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 0e1e5c64dd..e3f1b3f361 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -816,92 +816,108 @@ static void test_hbitmap_iter_and_reset(TestHBitmapD= ata *data, hbitmap_iter_next(&hbi); } =20 -static void test_hbitmap_next_zero_check_range(TestHBitmapData *data, - uint64_t start, - uint64_t count) +static void test_hbitmap_next_x_check_range(TestHBitmapData *data, + uint64_t start, + uint64_t count) { - int64_t ret1 =3D hbitmap_next_zero(data->hb, start, count); - int64_t ret2 =3D start; + int64_t next_zero =3D hbitmap_next_zero(data->hb, start, count); + int64_t next_dirty =3D hbitmap_next_dirty(data->hb, start, count); + int64_t next; int64_t end =3D start >=3D data->size || data->size - start < count ? data->size : start + count; + bool first_bit =3D hbitmap_get(data->hb, start); =20 - for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) { + for (next =3D start; + next < end && hbitmap_get(data->hb, next) =3D=3D first_bit; + next++) + { ; } - if (ret2 =3D=3D end) { - ret2 =3D -1; + + if (next =3D=3D end) { + next =3D -1; } =20 - g_assert_cmpint(ret1, =3D=3D, ret2); + g_assert_cmpint(next_dirty, =3D=3D, first_bit ? start : next); + g_assert_cmpint(next_zero, =3D=3D, first_bit ? next : start); } =20 -static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t st= art) +static void test_hbitmap_next_x_check(TestHBitmapData *data, int64_t start) { - test_hbitmap_next_zero_check_range(data, start, INT64_MAX); + test_hbitmap_next_x_check_range(data, start, INT64_MAX); } =20 -static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granulari= ty) +static void test_hbitmap_next_x_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); + test_hbitmap_next_x_check(data, 0); + test_hbitmap_next_x_check(data, L3 - 1); + test_hbitmap_next_x_check_range(data, 0, 1); + test_hbitmap_next_x_check_range(data, L3 - 1, 1); =20 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); + test_hbitmap_next_x_check(data, 0); + test_hbitmap_next_x_check(data, L2 - 1); + test_hbitmap_next_x_check(data, L2); + test_hbitmap_next_x_check(data, L2 + 1); + test_hbitmap_next_x_check_range(data, 0, 1); + test_hbitmap_next_x_check_range(data, 0, L2); + test_hbitmap_next_x_check_range(data, L2 - 1, 1); + test_hbitmap_next_x_check_range(data, L2 - 1, 2); + test_hbitmap_next_x_check_range(data, L2, 1); + test_hbitmap_next_x_check_range(data, L2 + 1, 1); =20 hbitmap_set(data->hb, L2 + 5, L1); - test_hbitmap_next_zero_check(data, 0); - test_hbitmap_next_zero_check(data, L2 + 1); - test_hbitmap_next_zero_check(data, L2 + 2); - 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); + test_hbitmap_next_x_check(data, 0); + test_hbitmap_next_x_check(data, L2 - L1); + test_hbitmap_next_x_check(data, L2 + 1); + test_hbitmap_next_x_check(data, L2 + 2); + test_hbitmap_next_x_check(data, L2 + 5); + test_hbitmap_next_x_check(data, L2 + L1 - 1); + test_hbitmap_next_x_check(data, L2 + L1); + test_hbitmap_next_x_check(data, L2 + L1 + 1); + test_hbitmap_next_x_check_range(data, L2 - 2, L1); + test_hbitmap_next_x_check_range(data, L2, 4); + test_hbitmap_next_x_check_range(data, L2, 6); + test_hbitmap_next_x_check_range(data, L2 + 1, 3); + test_hbitmap_next_x_check_range(data, L2 + 4, L1); + test_hbitmap_next_x_check_range(data, L2 + 5, L1); + test_hbitmap_next_x_check_range(data, L2 + 5 + L1 - 1, 1); + test_hbitmap_next_x_check_range(data, L2 + 5 + L1, 1); + test_hbitmap_next_x_check_range(data, L2 + 5 + L1 + 1, 1); =20 hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2); - test_hbitmap_next_zero_check(data, L2 * 2 - L1); - test_hbitmap_next_zero_check(data, L2 * 2 - 2); - 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); + test_hbitmap_next_x_check(data, L2 * 2 - L1); + test_hbitmap_next_x_check(data, L2 * 2 - 2); + test_hbitmap_next_x_check(data, L2 * 2 - 1); + test_hbitmap_next_x_check(data, L2 * 2); + test_hbitmap_next_x_check(data, L2 * 2 + 1); + test_hbitmap_next_x_check(data, L2 * 2 + L1); + test_hbitmap_next_x_check(data, L3 - 1); + test_hbitmap_next_x_check_range(data, L2 * 2 - L1, L1 + 1); + test_hbitmap_next_x_check_range(data, L2 * 2, L2); =20 hbitmap_set(data->hb, 0, L3); - test_hbitmap_next_zero_check(data, 0); + test_hbitmap_next_x_check(data, 0); } =20 -static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *un= used) +static void test_hbitmap_next_x_0(TestHBitmapData *data, const void *unuse= d) { - test_hbitmap_next_zero_do(data, 0); + test_hbitmap_next_x_do(data, 0); } =20 -static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *un= used) +static void test_hbitmap_next_x_4(TestHBitmapData *data, const void *unuse= d) { - test_hbitmap_next_zero_do(data, 4); + test_hbitmap_next_x_do(data, 4); } =20 -static void test_hbitmap_next_zero_after_truncate(TestHBitmapData *data, - const void *unused) +static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data, + const void *unused) { hbitmap_test_init(data, L1, 0); hbitmap_test_truncate_impl(data, L1 * 2); hbitmap_set(data->hb, 0, L1); - test_hbitmap_next_zero_check(data, 0); + test_hbitmap_next_x_check(data, 0); } =20 static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data, @@ -1068,12 +1084,12 @@ int main(int argc, char **argv) hbitmap_test_add("/hbitmap/iter/iter_and_reset", test_hbitmap_iter_and_reset); =20 - hbitmap_test_add("/hbitmap/next_zero/next_zero_0", - test_hbitmap_next_zero_0); - hbitmap_test_add("/hbitmap/next_zero/next_zero_4", - test_hbitmap_next_zero_4); - hbitmap_test_add("/hbitmap/next_zero/next_zero_after_truncate", - test_hbitmap_next_zero_after_truncate); + hbitmap_test_add("/hbitmap/next_zero/next_x_0", + test_hbitmap_next_x_0); + hbitmap_test_add("/hbitmap/next_zero/next_x_4", + test_hbitmap_next_x_4); + hbitmap_test_add("/hbitmap/next_zero/next_x_after_truncate", + test_hbitmap_next_x_after_truncate); =20 hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0", test_hbitmap_next_dirty_area_0); diff --git a/util/hbitmap.c b/util/hbitmap.c index 6526d7b6c1..c089020ca3 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -193,6 +193,30 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap= *hb, uint64_t first) } } =20 +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count) +{ + HBitmapIter hbi; + int64_t firt_dirty_off; + uint64_t end; + + assert(start >=3D 0 && count >=3D 0); + + if (start >=3D hb->orig_size || count =3D=3D 0) { + return -1; + } + + end =3D count > hb->orig_size - start ? hb->orig_size : start + count; + + hbitmap_iter_init(&hbi, hb, start); + firt_dirty_off =3D hbitmap_iter_next(&hbi); + + if (firt_dirty_off < 0 || firt_dirty_off >=3D end) { + return -1; + } + + return MAX(start, firt_dirty_off); +} + int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count) { size_t pos =3D (start >> hb->granularity) >> BITS_PER_LEVEL; @@ -248,40 +272,20 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t = start, int64_t count) =20 bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *c= ount) { - HBitmapIter hbi; - int64_t firt_dirty_off, area_end; - uint32_t granularity =3D 1UL << hb->granularity; - uint64_t end; - - assert(*start >=3D 0 && *count >=3D 0); - - if (*start >=3D hb->orig_size || *count =3D=3D 0) { - return false; - } - - end =3D *count > hb->orig_size - *start ? hb->orig_size : *start + *co= unt; - - hbitmap_iter_init(&hbi, hb, *start); - firt_dirty_off =3D hbitmap_iter_next(&hbi); + int64_t area_start, area_end; =20 - if (firt_dirty_off < 0 || firt_dirty_off >=3D end) { + area_start =3D hbitmap_next_dirty(hb, *start, *count); + if (area_start < 0) { return false; } =20 - if (firt_dirty_off + granularity >=3D end) { - area_end =3D end; - } else { - area_end =3D hbitmap_next_zero(hb, firt_dirty_off + granularity, - end - firt_dirty_off - granularity); - if (area_end < 0) { - area_end =3D end; - } + area_end =3D hbitmap_next_zero(hb, area_start, *start + *count - area_= start); + if (area_end < 0) { + area_end =3D MIN(hb->orig_size, *start + *count); } =20 - if (firt_dirty_off > *start) { - *start =3D firt_dirty_off; - } - *count =3D area_end - *start; + *start =3D area_start; + *count =3D area_end - area_start; =20 return true; } --=20 2.21.0