From nobody Sun Sep 28 11:11:18 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=redhat.com Return-Path: Received: from lists.gnu.org (209.51.188.17 [209.51.188.17]) by mx.zohomail.com with SMTPS id 1547600622983539.8269591404529; Tue, 15 Jan 2019 17:03:42 -0800 (PST) Received: from localhost ([127.0.0.1]:36699 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gjZc9-0003o1-Dq for importer@patchew.org; Tue, 15 Jan 2019 20:03:29 -0500 Received: from eggs.gnu.org ([209.51.188.92]:57795) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gjZaC-0002j0-Bj for qemu-devel@nongnu.org; Tue, 15 Jan 2019 20:01:29 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gjZa4-0004X1-PJ for qemu-devel@nongnu.org; Tue, 15 Jan 2019 20:01:24 -0500 Received: from mx1.redhat.com ([209.132.183.28]:56510) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1gjZa3-0004Qt-88 for qemu-devel@nongnu.org; Tue, 15 Jan 2019 20:01:19 -0500 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 9221BC0528B9; Wed, 16 Jan 2019 01:01:10 +0000 (UTC) Received: from probe.bos.redhat.com (dhcp-17-221.bos.redhat.com [10.18.17.221]) by smtp.corp.redhat.com (Postfix) with ESMTP id 039EA19C7C; Wed, 16 Jan 2019 01:01:09 +0000 (UTC) From: John Snow To: qemu-devel@nongnu.org Date: Tue, 15 Jan 2019 20:00:59 -0500 Message-Id: <20190116010106.27626-2-jsnow@redhat.com> In-Reply-To: <20190116010106.27626-1-jsnow@redhat.com> References: <20190116010106.27626-1-jsnow@redhat.com> X-Scanned-By: MIMEDefang 2.84 on 10.5.11.23 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.31]); Wed, 16 Jan 2019 01:01:10 +0000 (UTC) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 209.132.183.28 Subject: [Qemu-devel] [PULL 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: peter.maydell@linaro.org, Vladimir Sementsov-Ogievskiy , jsnow@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" From: Vladimir Sementsov-Ogievskiy Add bytes parameter to the function, to limit searched range. Signed-off-by: Vladimir Sementsov-Ogievskiy Signed-off-by: John Snow --- block/backup.c | 3 ++- block/dirty-bitmap.c | 5 +++-- include/block/dirty-bitmap.h | 3 ++- include/qemu/hbitmap.h | 10 +++++++--- nbd/server.c | 2 +- tests/test-hbitmap.c | 2 +- util/hbitmap.c | 27 ++++++++++++++++++++++----- 7 files changed, 38 insertions(+), 14 deletions(-) diff --git a/block/backup.c b/block/backup.c index b829b251eb..9ffce5c183 100644 --- a/block/backup.c +++ b/block/backup.c @@ -422,7 +422,8 @@ static void backup_incremental_init_copy_bitmap(BackupB= lockJob *job) break; } =20 - offset =3D bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset); + offset =3D bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, + UINT64_MAX); if (offset =3D=3D -1) { hbitmap_set(job->copy_bitmap, cluster, end - cluster); break; diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index 6b688394e4..b162f4ac22 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -781,9 +781,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *= bitmap, Error **errp) return hbitmap_sha256(bitmap->bitmap, errp); } =20 -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offs= et) +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offs= et, + uint64_t bytes) { - return hbitmap_next_zero(bitmap->bitmap, offset); + return hbitmap_next_zero(bitmap->bitmap, offset, bytes); } =20 void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap = *src, diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 8f38a3dec1..102ccdda32 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -99,7 +99,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState= *bs); BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, BdrvDirtyBitmap *bitmap); char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp= ); -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t star= t); +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offs= et, + uint64_t bytes); BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs, BdrvDirtyBitmap *bitmap, Error **errp); diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index a7cb780592..135975530f 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -300,12 +300,16 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitma= p *hb, uint64_t first); unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); =20 /* hbitmap_next_zero: + * + * Find next not dirty bit within selected range. If not found, return -1. + * * @hb: The HBitmap to operate on * @start: The bit to start from. - * - * Find next not dirty bit. + * @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_zero(const HBitmap *hb, uint64_t start); +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t coun= t); =20 /* hbitmap_create_meta: * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. diff --git a/nbd/server.c b/nbd/server.c index e8c56607ef..6b136019f8 100644 --- a/nbd/server.c +++ b/nbd/server.c @@ -2014,7 +2014,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap= *bitmap, uint64_t offset, bool next_dirty =3D !dirty; =20 if (dirty) { - end =3D bdrv_dirty_bitmap_next_zero(bitmap, begin); + end =3D bdrv_dirty_bitmap_next_zero(bitmap, begin, UINT64_MAX); } else { bdrv_set_dirty_iter(it, begin); end =3D bdrv_dirty_iter_next(it); diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 5e67ac1d3a..b04a45a2de 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData= *data, =20 static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t st= art) { - int64_t ret1 =3D hbitmap_next_zero(data->hb, start); + int64_t ret1 =3D hbitmap_next_zero(data->hb, start, UINT64_MAX); int64_t ret2 =3D start; for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) { ; diff --git a/util/hbitmap.c b/util/hbitmap.c index 8d402c59d9..09b3719e44 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -53,6 +53,9 @@ */ =20 struct HBitmap { + /* Size of the bitmap, as requested in hbitmap_alloc. */ + uint64_t orig_size; + /* Number of total bits in the bottom level. */ uint64_t size; =20 @@ -192,16 +195,28 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitma= p *hb, uint64_t first) } } =20 -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t coun= t) { size_t pos =3D (start >> hb->granularity) >> BITS_PER_LEVEL; unsigned long *last_lev =3D hb->levels[HBITMAP_LEVELS - 1]; - uint64_t sz =3D hb->sizes[HBITMAP_LEVELS - 1]; unsigned long cur =3D last_lev[pos]; - unsigned start_bit_offset =3D - (start >> hb->granularity) & (BITS_PER_LONG - 1); + unsigned start_bit_offset; + uint64_t end_bit, sz; int64_t res; =20 + if (start >=3D hb->orig_size || count =3D=3D 0) { + return -1; + } + + end_bit =3D count > hb->orig_size - start ? + hb->size : + ((start + count - 1) >> hb->granularity) + 1; + sz =3D (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; + + /* There may be some zero bits in @cur before @start. We are not inter= ested + * in them, let's set them. + */ + start_bit_offset =3D (start >> hb->granularity) & (BITS_PER_LONG - 1); cur |=3D (1UL << start_bit_offset) - 1; assert((start >> hb->granularity) < hb->size); =20 @@ -218,7 +233,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t s= tart) } =20 res =3D (pos << BITS_PER_LEVEL) + ctol(cur); - if (res >=3D hb->size) { + if (res >=3D end_bit) { return -1; } =20 @@ -652,6 +667,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity) HBitmap *hb =3D g_new0(struct HBitmap, 1); unsigned i; =20 + hb->orig_size =3D size; + assert(granularity >=3D 0 && granularity < 64); size =3D (size + (1ULL << granularity) - 1) >> granularity; assert(size <=3D ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); --=20 2.17.2