From patchwork Mon Dec 18 21:08:10 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Cody X-Patchwork-Id: 10121843 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 916D560327 for ; Mon, 18 Dec 2017 21:10:18 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 822C428CC8 for ; Mon, 18 Dec 2017 21:10:18 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7698F28CCD; Mon, 18 Dec 2017 21:10:18 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id E239328CC8 for ; Mon, 18 Dec 2017 21:10:17 +0000 (UTC) Received: from localhost ([::1]:42403 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eR2fx-0003P6-4q for patchwork-qemu-devel@patchwork.kernel.org; Mon, 18 Dec 2017 16:10:17 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59681) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eR2eH-0001nK-Vl for qemu-devel@nongnu.org; Mon, 18 Dec 2017 16:08:36 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eR2eG-0003IC-H2 for qemu-devel@nongnu.org; Mon, 18 Dec 2017 16:08:33 -0500 Received: from mx1.redhat.com ([209.132.183.28]:53278) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eR2eC-0003Df-9s; Mon, 18 Dec 2017 16:08:28 -0500 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 8477F25C38; Mon, 18 Dec 2017 21:08:27 +0000 (UTC) Received: from localhost (ovpn-120-76.rdu2.redhat.com [10.10.120.76]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 549567C802; Mon, 18 Dec 2017 21:08:24 +0000 (UTC) From: Jeff Cody To: qemu-block@nongnu.org Date: Mon, 18 Dec 2017 16:08:10 -0500 Message-Id: <20171218210819.31576-2-jcody@redhat.com> In-Reply-To: <20171218210819.31576-1-jcody@redhat.com> References: <20171218210819.31576-1-jcody@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.30]); Mon, 18 Dec 2017 21:08:27 +0000 (UTC) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 209.132.183.28 Subject: [Qemu-devel] [PULL 01/10] hbitmap: add next_zero function 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, jcody@redhat.com, vsementsov@virtuozzo.com, jsnow@redhat.com, qemu-devel@nongnu.org Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP From: Vladimir Sementsov-Ogievskiy The function searches for next zero bit. Also add interface for BdrvDirtyBitmap and unit test. Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: John Snow Message-id: 20171012135313.227864-2-vsementsov@virtuozzo.com Signed-off-by: Jeff Cody --- block/dirty-bitmap.c | 5 ++++ include/block/dirty-bitmap.h | 1 + include/qemu/hbitmap.h | 8 ++++++ tests/test-hbitmap.c | 61 ++++++++++++++++++++++++++++++++++++++++++++ util/hbitmap.c | 39 ++++++++++++++++++++++++++++ 5 files changed, 114 insertions(+) diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index bd04e99..7879d13 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -715,3 +715,8 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp) { return hbitmap_sha256(bitmap->bitmap, errp); } + +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset) +{ + return hbitmap_next_zero(bitmap->bitmap, offset); +} diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 3579a75..a591c27 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 start); #endif diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 81e7804..6b6490e 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); +/* 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/tests/test-hbitmap.c b/tests/test-hbitmap.c index af41642..9091c63 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -925,6 +925,61 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, hbitmap_iter_next(&hbi); } +static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) +{ + int64_t ret1 = hbitmap_next_zero(data->hb, start); + int64_t ret2 = start; + for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) { + ; + } + if (ret2 == data->size) { + ret2 = -1; + } + + g_assert_cmpint(ret1, ==, ret2); +} + +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); + + 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); + + 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); + + 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); + + hbitmap_set(data->hb, 0, L3); + test_hbitmap_next_zero_check(data, 0); +} + +static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *unused) +{ + test_hbitmap_next_zero_do(data, 0); +} + +static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused) +{ + test_hbitmap_next_zero_do(data, 4); +} + int main(int argc, char **argv) { g_test_init(&argc, &argv, NULL); @@ -985,6 +1040,12 @@ int main(int argc, char **argv) hbitmap_test_add("/hbitmap/iter/iter_and_reset", test_hbitmap_iter_and_reset); + + 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); + g_test_run(); return 0; diff --git a/util/hbitmap.c b/util/hbitmap.c index 2f9d0fd..289778a 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -188,6 +188,45 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) } } +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) +{ + size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; + unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; + uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1]; + unsigned long cur = last_lev[pos]; + unsigned start_bit_offset = + (start >> hb->granularity) & (BITS_PER_LONG - 1); + int64_t res; + + cur |= (1UL << start_bit_offset) - 1; + assert((start >> hb->granularity) < hb->size); + + if (cur == (unsigned long)-1) { + do { + pos++; + } while (pos < sz && last_lev[pos] == (unsigned long)-1); + + if (pos >= sz) { + return -1; + } + + cur = last_lev[pos]; + } + + res = (pos << BITS_PER_LEVEL) + ctol(cur); + if (res >= hb->size) { + return -1; + } + + res = res << hb->granularity; + if (res < start) { + assert(((start - res) >> hb->granularity) == 0); + return start; + } + + return res; +} + bool hbitmap_empty(const HBitmap *hb) { return hb->count == 0;