From nobody Mon Feb 9 23:01:14 2026 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@gnu.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@gnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 1506955506420173.36079051817615; Mon, 2 Oct 2017 07:45:06 -0700 (PDT) Received: from localhost ([::1]:52665 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dz1xq-0006BZ-PG for importer@patchew.org; Mon, 02 Oct 2017 10:44:58 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:52143) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dz1sX-0001YG-Hw for qemu-devel@nongnu.org; Mon, 02 Oct 2017 10:39:33 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dz1sT-00030e-JN for qemu-devel@nongnu.org; Mon, 02 Oct 2017 10:39:29 -0400 Received: from mailhub.sw.ru ([195.214.232.25]:5764 helo=relay.sw.ru) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1dz1sT-0002ys-7C for qemu-devel@nongnu.org; Mon, 02 Oct 2017 10:39:25 -0400 Received: from kvm.sw.ru (msk-vpn.virtuozzo.com [195.214.232.6]) by relay.sw.ru (8.13.4/8.13.4) with ESMTP id v92EdJQ5007920; Mon, 2 Oct 2017 17:39:20 +0300 (MSK) From: Vladimir Sementsov-Ogievskiy To: qemu-block@nongnu.org, qemu-devel@nongnu.org Date: Mon, 2 Oct 2017 17:39:15 +0300 Message-Id: <20171002143919.207741-2-vsementsov@virtuozzo.com> X-Mailer: git-send-email 2.11.1 In-Reply-To: <20171002143919.207741-1-vsementsov@virtuozzo.com> References: <20171002143919.207741-1-vsementsov@virtuozzo.com> X-detected-operating-system: by eggs.gnu.org: OpenBSD 3.x [fuzzy] X-Received-From: 195.214.232.25 Subject: [Qemu-devel] [PATCH 1/5] hbitmap: add next_zero function X-BeenThere: qemu-devel@gnu.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, stefanha@redhat.com, den@openvz.org, jsnow@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@gnu.org Sender: "Qemu-devel" X-ZohoMail: RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" The function searches for next zero bit. Also add interface for BdrvDirtyBitmap. Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: John Snow --- include/block/dirty-bitmap.h | 1 + include/qemu/hbitmap.h | 8 ++++++++ block/dirty-bitmap.c | 5 +++++ util/hbitmap.c | 29 +++++++++++++++++++++++++++++ 4 files changed, 43 insertions(+) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 3579a7597c..a591c27213 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -91,5 +91,6 @@ 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); =20 #endif diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 81e78043d1..6b6490ecad 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -292,6 +292,14 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap= *hb, uint64_t first); */ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); =20 +/* hbitmap_next_zero: + * @hb: The HBitmap to operate on + * @start: The bit to start from. + * + * Find next not dirty bit. + */ +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); + /* hbitmap_create_meta: * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. * The caller owns the created bitmap and must call hbitmap_free_meta(hb) = to diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index bd04e991b1..7879d13ddb 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -715,3 +715,8 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *b= itmap, Error **errp) { return hbitmap_sha256(bitmap->bitmap, errp); } + +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offs= et) +{ + return hbitmap_next_zero(bitmap->bitmap, offset); +} diff --git a/util/hbitmap.c b/util/hbitmap.c index 2f9d0fdbd0..ffcdbc5587 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -188,6 +188,35 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap= *hb, uint64_t first) } } =20 +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) +{ + 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); + int64_t res; + cur |=3D (1UL << start_bit_offset) - 1; + assert((start >> hb->granularity) < hb->size); + + if (cur =3D=3D (unsigned long)-1) { + do { + pos++; + } while (pos < sz && last_lev[pos] =3D=3D (unsigned long)-1); + + if (pos >=3D sz) { + return -1; + } + + cur =3D last_lev[pos]; + } + + res =3D (pos << BITS_PER_LEVEL) + ctol(cur); + + return res < hb->size ? (res << hb->granularity) : -1; +} + bool hbitmap_empty(const HBitmap *hb) { return hb->count =3D=3D 0; --=20 2.11.1