From nobody Wed Nov 5 13:11:57 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.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 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=virtuozzo.com Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 1534249181808927.4605745745739; Tue, 14 Aug 2018 05:19:41 -0700 (PDT) Received: from localhost ([::1]:44044 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYIW-00071z-Jf for importer@patchew.org; Tue, 14 Aug 2018 08:19:40 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37591) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002eE-Ux for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:54 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fpYDn-00051y-Rf for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51118) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-00051D-Gu; Tue, 14 Aug 2018 08:14:47 -0400 Received: from vz-out.virtuozzo.com ([185.231.240.5] helo=kvm.sw.ru) by relay.sw.ru with esmtp (Exim 4.90_1) (envelope-from ) id 1fpYDk-0007K0-8i; Tue, 14 Aug 2018 15:14:44 +0300 From: Vladimir Sementsov-Ogievskiy To: qemu-devel@nongnu.org, qemu-block@nongnu.org Date: Tue, 14 Aug 2018 15:14:36 +0300 Message-Id: <20180814121443.33114-2-vsementsov@virtuozzo.com> X-Mailer: git-send-email 2.11.1 In-Reply-To: <20180814121443.33114-1-vsementsov@virtuozzo.com> References: <20180814121443.33114-1-vsementsov@virtuozzo.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 185.231.240.75 Subject: [Qemu-devel] [PATCH v3 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: kwolf@redhat.com, vsementsov@virtuozzo.com, famz@redhat.com, jcody@redhat.com, mreitz@redhat.com, den@openvz.org, pbonzini@redhat.com, jsnow@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail: RDMRC_1 RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Add bytes parameter to the function, to limit searched range. Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: John Snow --- include/block/dirty-bitmap.h | 3 ++- include/qemu/hbitmap.h | 10 ++++++++-- block/backup.c | 2 +- block/dirty-bitmap.c | 5 +++-- nbd/server.c | 2 +- tests/test-hbitmap.c | 2 +- util/hbitmap.c | 25 ++++++++++++++++++++----- 7 files changed, 36 insertions(+), 13 deletions(-) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 259bd27c40..27f5299c4e 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -98,7 +98,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 star= t, + int64_t end); 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 ddca52c48e..fe4dfde27a 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hb= i); /* hbitmap_next_zero: * @hb: The HBitmap to operate on * @start: The bit to start from. + * @end: End of range to search in. If @end is -1, search up to the bitmap + * end. * - * Find next not dirty bit. + * Find next not dirty bit within range [@start, @end), or from + * @start to the bitmap end if @end is -1. If not found, return -1. + * + * @end may be greater than original bitmap size, in this case, 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, int64_t end); =20 /* hbitmap_create_meta: * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. diff --git a/block/backup.c b/block/backup.c index 8630d32926..9bfd3f7189 100644 --- a/block/backup.c +++ b/block/backup.c @@ -458,7 +458,7 @@ 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, -= 1); 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 c9b8a6fd52..037ae62726 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -785,9 +785,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, + int64_t end) { - return hbitmap_next_zero(bitmap->bitmap, offset); + return hbitmap_next_zero(bitmap->bitmap, offset, end); } =20 void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap = *src, diff --git a/nbd/server.c b/nbd/server.c index ea5fe0eb33..07920d123b 100644 --- a/nbd/server.c +++ b/nbd/server.c @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap= *bitmap, uint64_t offset, assert(begin < overall_end && nb_extents); while (begin < overall_end && i < nb_extents) { if (dirty) { - end =3D bdrv_dirty_bitmap_next_zero(bitmap, begin); + end =3D bdrv_dirty_bitmap_next_zero(bitmap, begin, -1); } 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..6b6a40bddd 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, -1); 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 bcd304041a..1687372504 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,26 @@ 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, int64_t end) { 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 || (end !=3D -1 && end <=3D start)) { + return -1; + } + + end_bit =3D end =3D=3D -1 ? hb->size : ((end - 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 +231,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 +665,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.11.1