From patchwork Tue Aug 14 12:14:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957475 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWpV07Ghz9sBZ for ; Tue, 14 Aug 2018 22:18:26 +1000 (AEST) Received: from localhost ([::1]:44040 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYHH-00068N-Mx for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:18:23 -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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" 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 start); +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start, + 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 *hbi); /* 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); /* 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(BackupBlockJob *job) break; } - offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset); + offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1); if (offset == -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); } -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset) +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset, + int64_t end) { - return hbitmap_next_zero(bitmap->bitmap, offset); + return hbitmap_next_zero(bitmap->bitmap, offset, end); } 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 = bdrv_dirty_bitmap_next_zero(bitmap, begin); + end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1); } else { bdrv_set_dirty_iter(it, begin); end = 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, static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) { - int64_t ret1 = hbitmap_next_zero(data->hb, start); + int64_t ret1 = hbitmap_next_zero(data->hb, start, -1); int64_t ret2 = 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 @@ */ 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; @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) } } -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 = (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); + unsigned start_bit_offset; + uint64_t end_bit, sz; int64_t res; + if (start >= hb->orig_size || (end != -1 && end <= start)) { + return -1; + } + + end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1; + sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; + + /* There may be some zero bits in @cur before @start. We are not interested + * in them, let's set them. + */ + start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); cur |= (1UL << start_bit_offset) - 1; assert((start >> hb->granularity) < hb->size); @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) } res = (pos << BITS_PER_LEVEL) + ctol(cur); - if (res >= hb->size) { + if (res >= end_bit) { return -1; } @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity) HBitmap *hb = g_new0(struct HBitmap, 1); unsigned i; + hb->orig_size = size; + assert(granularity >= 0 && granularity < 64); size = (size + (1ULL << granularity) - 1) >> granularity; assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); From patchwork Tue Aug 14 12:14:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957481 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWvl3wZkz9s0n for ; Tue, 14 Aug 2018 22:22:59 +1000 (AEST) Received: from localhost ([::1]:44068 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYLh-0002Cp-6o for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:22:57 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37588) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002eC-Un 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-00052b-TR for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51086) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-000515-HN; 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-Aa; 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:37 +0300 Message-Id: <20180814121443.33114-3-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 2/8] tests: add tests for hbitmap_next_zero with specified end parameter 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" Signed-off-by: Vladimir Sementsov-Ogievskiy --- tests/test-hbitmap.c | 32 ++++++++++++++++++++++++++++---- 1 file changed, 28 insertions(+), 4 deletions(-) diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 6b6a40bddd..dddb67c3c5 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -937,31 +937,49 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, check_hbitmap_iter_next(&hbi); } -static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) +static void test_hbitmap_next_zero_check_range(TestHBitmapData *data, + int64_t start, + int64_t count) { - int64_t ret1 = hbitmap_next_zero(data->hb, start, -1); + int64_t ret1 = hbitmap_next_zero(data->hb, start, + count == -1 ? -1 : start + count); int64_t ret2 = start; - for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) { + int64_t end = count == -1 ? data->size : start + count; + + for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) { ; } - if (ret2 == data->size) { + if (ret2 == end) { ret2 = -1; } g_assert_cmpint(ret1, ==, ret2); } +static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) +{ + test_hbitmap_next_zero_check_range(data, start, 0); +} + 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); + test_hbitmap_next_zero_check_range(data, 0, 1); + test_hbitmap_next_zero_check_range(data, L3 - 1, 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); + 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); hbitmap_set(data->hb, L2 + 5, L1); test_hbitmap_next_zero_check(data, 0); @@ -970,6 +988,10 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity) 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); hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2); test_hbitmap_next_zero_check(data, L2 * 2 - L1); @@ -977,6 +999,8 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity) 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); hbitmap_set(data->hb, 0, L3); test_hbitmap_next_zero_check(data, 0); From patchwork Tue Aug 14 12:14:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957480 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWsR4Qz4z9s9l for ; Tue, 14 Aug 2018 22:20:59 +1000 (AEST) Received: from localhost ([::1]:44058 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYJl-00010x-AF for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:20:57 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37586) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002eA-UN 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-00052W-SE for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51106) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-000519-HK; 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-D1; 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:38 +0300 Message-Id: <20180814121443.33114-4-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 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" The function alters bdrv_dirty_iter_next_area(), which is wrong and less efficient (see further commit "block/mirror: fix and improve do_sync_target_write" for description). Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: John Snow --- include/block/dirty-bitmap.h | 3 +++ include/qemu/hbitmap.h | 15 +++++++++++++++ block/dirty-bitmap.c | 7 +++++++ util/hbitmap.c | 38 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 63 insertions(+) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 27f5299c4e..cb9162fa7e 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -100,6 +100,9 @@ BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs, char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp); int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start, int64_t end); +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, + uint64_t *offset, uint64_t end, + uint64_t *length); 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 fe4dfde27a..7800317bf3 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -306,6 +306,21 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); */ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end); +/* hbitmap_next_dirty_area: + * @hb: The HBitmap to operate on + * @offset: in-out parameter. + * in: the offset to start from + * out: (if area found) start of found area + * @end: end of requested region. (*@offset + *@length) will be <= @end + * @length: length of found area + * + * If dirty area found within [@offset, @end), returns true and sets @offset + * and @length appropriately. Otherwise returns true and leaves @offset and + * @length unchanged. + */ +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset, + uint64_t end, uint64_t *length); + /* 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 037ae62726..4af20a1beb 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -791,6 +791,13 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset, return hbitmap_next_zero(bitmap->bitmap, offset, end); } +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, + uint64_t *offset, uint64_t end, + uint64_t *length) +{ + return hbitmap_next_dirty_area(bitmap->bitmap, offset, end, length); +} + void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src, Error **errp) { diff --git a/util/hbitmap.c b/util/hbitmap.c index 1687372504..bf88c1223e 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -244,6 +244,44 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end) return res; } +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset, + uint64_t end, uint64_t *length) +{ + HBitmapIter hbi; + int64_t off1, off0; + uint32_t granularity = 1UL << hb->granularity; + + if (end == 0) { + end = hb->orig_size; + } + + hbitmap_iter_init(&hbi, hb, *offset); + off1 = hbitmap_iter_next(&hbi, true); + + if (off1 < 0 || off1 >= end) { + return false; + } + + if (off1 + granularity >= end) { + if (off1 > *offset) { + *offset = off1; + } + *length = end - *offset; + return true; + } + + off0 = hbitmap_next_zero(hb, off1 + granularity, end); + if (off0 < 0) { + off0 = end; + } + + if (off1 > *offset) { + *offset = off1; + } + *length = off0 - *offset; + return true; +} + bool hbitmap_empty(const HBitmap *hb) { return hb->count == 0; From patchwork Tue Aug 14 12:14:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957479 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWsQ4P6lz9sBZ for ; Tue, 14 Aug 2018 22:20:57 +1000 (AEST) Received: from localhost ([::1]:44056 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYJh-0000yM-5c for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:20:53 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37592) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002eF-V8 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-00052K-RF for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51108) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-00051B-HT; 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-Eg; 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:39 +0300 Message-Id: <20180814121443.33114-5-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 4/8] tests: add tests for hbitmap_next_dirty_area 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" Signed-off-by: Vladimir Sementsov-Ogievskiy Tested-by: John Snow --- tests/test-hbitmap.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index dddb67c3c5..af5142b481 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -1016,6 +1016,105 @@ static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused) test_hbitmap_next_zero_do(data, 4); } +static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data, + uint64_t offset, + uint64_t count) +{ + uint64_t off1, off2; + uint64_t len1 = 0, len2 = 0; + bool ret1, ret2; + int64_t end; + + off1 = offset; + end = count ? offset + count : 0; + ret1 = hbitmap_next_dirty_area(data->hb, &off1, end, &len1); + + end = count ? offset + count : data->size; + + for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) { + ; + } + + for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2); + len2++) + { + } + + ret2 = off2 < end; + if (!ret2) { + /* leave unchanged */ + off2 = offset; + len2 = 0; + } + + g_assert_cmpint(ret1, ==, ret2); + g_assert_cmpint(off1, ==, off2); + g_assert_cmpint(len1, ==, len2); +} + +static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data, + int granularity) +{ + hbitmap_test_init(data, L3, granularity); + test_hbitmap_next_dirty_area_check(data, 0, 0); + test_hbitmap_next_dirty_area_check(data, 0, 1); + test_hbitmap_next_dirty_area_check(data, L3 - 1, 1); + + hbitmap_set(data->hb, L2, 1); + test_hbitmap_next_dirty_area_check(data, 0, 1); + test_hbitmap_next_dirty_area_check(data, 0, L2); + test_hbitmap_next_dirty_area_check(data, 0, 0); + test_hbitmap_next_dirty_area_check(data, L2 - 1, 0); + test_hbitmap_next_dirty_area_check(data, L2 - 1, 1); + test_hbitmap_next_dirty_area_check(data, L2 - 1, 2); + test_hbitmap_next_dirty_area_check(data, L2 - 1, 3); + test_hbitmap_next_dirty_area_check(data, L2, 0); + test_hbitmap_next_dirty_area_check(data, L2, 1); + test_hbitmap_next_dirty_area_check(data, L2 + 1, 1); + + hbitmap_set(data->hb, L2 + 5, L1); + test_hbitmap_next_dirty_area_check(data, 0, 0); + test_hbitmap_next_dirty_area_check(data, L2 - 2, 8); + test_hbitmap_next_dirty_area_check(data, L2 + 1, 5); + test_hbitmap_next_dirty_area_check(data, L2 + 1, 3); + test_hbitmap_next_dirty_area_check(data, L2 + 4, L1); + test_hbitmap_next_dirty_area_check(data, L2 + 5, L1); + test_hbitmap_next_dirty_area_check(data, L2 + 7, L1); + test_hbitmap_next_dirty_area_check(data, L2 + L1, L1); + test_hbitmap_next_dirty_area_check(data, L2, 0); + test_hbitmap_next_dirty_area_check(data, L2 + 1, 0); + + hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2); + test_hbitmap_next_dirty_area_check(data, 0, 0); + test_hbitmap_next_dirty_area_check(data, L2, 0); + test_hbitmap_next_dirty_area_check(data, L2 + 1, 0); + test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, 0); + test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5); + test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1); + test_hbitmap_next_dirty_area_check(data, L2 * 2, L2); + + hbitmap_set(data->hb, 0, L3); + test_hbitmap_next_dirty_area_check(data, 0, 0); +} + +static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data, + const void *unused) +{ + test_hbitmap_next_dirty_area_do(data, 0); +} + +static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data, + const void *unused) +{ + test_hbitmap_next_dirty_area_do(data, 1); +} + +static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data, + const void *unused) +{ + test_hbitmap_next_dirty_area_do(data, 4); +} + int main(int argc, char **argv) { g_test_init(&argc, &argv, NULL); @@ -1082,6 +1181,13 @@ int main(int argc, char **argv) hbitmap_test_add("/hbitmap/next_zero/next_zero_4", test_hbitmap_next_zero_4); + hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0", + test_hbitmap_next_dirty_area_0); + hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_1", + test_hbitmap_next_dirty_area_1); + hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_4", + test_hbitmap_next_dirty_area_4); + g_test_run(); return 0; From patchwork Tue Aug 14 12:14:40 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957468 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWlN12Mqz9sBJ for ; Tue, 14 Aug 2018 22:15:42 +1000 (AEST) Received: from localhost ([::1]:44022 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYEe-0002f1-Cw for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:15:40 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37590) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002eD-Uq 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-000528-Ri for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51088) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-000516-HB; 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-Ga; 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:40 +0300 Message-Id: <20180814121443.33114-6-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 5/8] block/mirror: fix and improve do_sync_target_write 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" Use bdrv_dirty_bitmap_next_dirty_area() instead of bdrv_dirty_iter_next_area(), because of the following problems of bdrv_dirty_iter_next_area(): 1. Using HBitmap iterators we should carefully handle unaligned offset, as first call to hbitmap_iter_next() may return a value less than original offset (actually, it will be original offset rounded down to bitmap granularity). This handling is not done in do_sync_target_write(). 2. bdrv_dirty_iter_next_area() handles unaligned max_offset incorrectly: look at the code: if (max_offset == iter->bitmap->size) { /* If max_offset points to the image end, round it up by the * bitmap granularity */ gran_max_offset = ROUND_UP(max_offset, granularity); } else { gran_max_offset = max_offset; } ret = hbitmap_iter_next(&iter->hbi, false); if (ret < 0 || ret + granularity > gran_max_offset) { return false; } and assume that max_offset != iter->bitmap->size but still unaligned. if 0 < ret < max_offset we found dirty area, but the function can return false in this case (if ret + granularity > max_offset). 3. bdrv_dirty_iter_next_area() uses inefficient loop to find the end of the dirty area. Let's use more efficient hbitmap_next_zero instead (bdrv_dirty_bitmap_next_dirty_area() do so) Signed-off-by: Vladimir Sementsov-Ogievskiy --- block/mirror.c | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/block/mirror.c b/block/mirror.c index b48c3f8cf5..d2806812c8 100644 --- a/block/mirror.c +++ b/block/mirror.c @@ -1167,25 +1167,22 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method, uint64_t offset, uint64_t bytes, QEMUIOVector *qiov, int flags) { - BdrvDirtyBitmapIter *iter; QEMUIOVector target_qiov; - uint64_t dirty_offset; - int dirty_bytes; + uint64_t dirty_offset = offset; + uint64_t dirty_bytes; if (qiov) { qemu_iovec_init(&target_qiov, qiov->niov); } - iter = bdrv_dirty_iter_new(job->dirty_bitmap); - bdrv_set_dirty_iter(iter, offset); - while (true) { bool valid_area; int ret; bdrv_dirty_bitmap_lock(job->dirty_bitmap); - valid_area = bdrv_dirty_iter_next_area(iter, offset + bytes, - &dirty_offset, &dirty_bytes); + valid_area = bdrv_dirty_bitmap_next_dirty_area( + job->dirty_bitmap, &dirty_offset, + MIN(offset + bytes, dirty_offset + INT_MAX), &dirty_bytes); if (!valid_area) { bdrv_dirty_bitmap_unlock(job->dirty_bitmap); break; @@ -1241,9 +1238,10 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method, break; } } + + dirty_offset += dirty_bytes; } - bdrv_dirty_iter_free(iter); if (qiov) { qemu_iovec_destroy(&target_qiov); } From patchwork Tue Aug 14 12:14:41 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957470 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWlN11pLz9s0n for ; Tue, 14 Aug 2018 22:15:42 +1000 (AEST) Received: from localhost ([::1]:44020 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYEd-0002ev-Ui for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:15:39 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37583) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002e8-TS 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-00052R-SA for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51114) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-00051C-HD; 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-JA; 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:41 +0300 Message-Id: <20180814121443.33114-7-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 6/8] Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area" 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" This reverts commit 72d10a94213a954ad569095cb4491f2ae0853c40. The function is unused now. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/block/dirty-bitmap.h | 2 -- block/dirty-bitmap.c | 55 -------------------------------------------- 2 files changed, 57 deletions(-) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index cb9162fa7e..20e1d86cb1 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -83,8 +83,6 @@ void bdrv_set_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap, void bdrv_reset_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap, int64_t offset, int64_t bytes); int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter); -bool bdrv_dirty_iter_next_area(BdrvDirtyBitmapIter *iter, uint64_t max_offset, - uint64_t *offset, int *bytes); void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t offset); int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap); int64_t bdrv_get_meta_dirty_count(BdrvDirtyBitmap *bitmap); diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index 4af20a1beb..d9333175b3 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -528,61 +528,6 @@ int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter) return hbitmap_iter_next(&iter->hbi, true); } -/** - * Return the next consecutively dirty area in the dirty bitmap - * belonging to the given iterator @iter. - * - * @max_offset: Maximum value that may be returned for - * *offset + *bytes - * @offset: Will contain the start offset of the next dirty area - * @bytes: Will contain the length of the next dirty area - * - * Returns: True if a dirty area could be found before max_offset - * (which means that *offset and *bytes then contain valid - * values), false otherwise. - * - * Note that @iter is never advanced if false is returned. If an area - * is found (which means that true is returned), it will be advanced - * past that area. - */ -bool bdrv_dirty_iter_next_area(BdrvDirtyBitmapIter *iter, uint64_t max_offset, - uint64_t *offset, int *bytes) -{ - uint32_t granularity = bdrv_dirty_bitmap_granularity(iter->bitmap); - uint64_t gran_max_offset; - int64_t ret; - int size; - - if (max_offset == iter->bitmap->size) { - /* If max_offset points to the image end, round it up by the - * bitmap granularity */ - gran_max_offset = ROUND_UP(max_offset, granularity); - } else { - gran_max_offset = max_offset; - } - - ret = hbitmap_iter_next(&iter->hbi, false); - if (ret < 0 || ret + granularity > gran_max_offset) { - return false; - } - - *offset = ret; - size = 0; - - assert(granularity <= INT_MAX); - - do { - /* Advance iterator */ - ret = hbitmap_iter_next(&iter->hbi, true); - size += granularity; - } while (ret + granularity <= gran_max_offset && - hbitmap_iter_next(&iter->hbi, false) == ret + granularity && - size <= INT_MAX - granularity); - - *bytes = MIN(size, max_offset - *offset); - return true; -} - /* Called within bdrv_dirty_bitmap_lock..unlock */ void bdrv_set_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap, int64_t offset, int64_t bytes) From patchwork Tue Aug 14 12:14:42 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957474 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWpV2B3Kz9s0n for ; Tue, 14 Aug 2018 22:18:26 +1000 (AEST) Received: from localhost ([::1]:44041 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYHH-00068d-TB for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:18:23 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37595) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002eG-WA 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-000529-S1 for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51102) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-000518-Gj; 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-L6; 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:42 +0300 Message-Id: <20180814121443.33114-8-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 7/8] Revert "test-hbitmap: Add non-advancing iter_next tests" 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" This reverts commit 269576848ec3d57d2d958cf5ac69b08c44adf816. The functionality is unused. Drop tests. Signed-off-by: Vladimir Sementsov-Ogievskiy --- tests/test-hbitmap.c | 36 ++++++++++++------------------------ 1 file changed, 12 insertions(+), 24 deletions(-) diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index af5142b481..5e43056970 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -30,18 +30,6 @@ typedef struct TestHBitmapData { } TestHBitmapData; -static int64_t check_hbitmap_iter_next(HBitmapIter *hbi) -{ - int next0, next1; - - next0 = hbitmap_iter_next(hbi, false); - next1 = hbitmap_iter_next(hbi, true); - - g_assert_cmpint(next0, ==, next1); - - return next0; -} - /* Check that the HBitmap and the shadow bitmap contain the same data, * ignoring the same "first" bits. */ @@ -58,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data, i = first; for (;;) { - next = check_hbitmap_iter_next(&hbi); + next = hbitmap_iter_next(&hbi, true); if (next < 0) { next = data->size; } @@ -447,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data, /* Note that hbitmap_test_check has to be invoked manually in this test. */ hbitmap_test_init(data, 131072 << 7, 7); hbitmap_iter_init(&hbi, data->hb, 0); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8); hbitmap_iter_init(&hbi, data->hb, 0); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7); g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); hbitmap_test_set(data, (131072 << 7) - 8, 8); hbitmap_iter_init(&hbi, data->hb, 0); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7); - g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); } static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff) @@ -905,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data, for (i = 0; i < num_positions; i++) { hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true); hbitmap_iter_init(&iter, data->hb, 0); - next = check_hbitmap_iter_next(&iter); + next = hbitmap_iter_next(&iter, true); if (i == num_positions - 1) { g_assert_cmpint(next, ==, -1); } else { @@ -931,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1); - check_hbitmap_iter_next(&hbi); + hbitmap_iter_next(&hbi, true); hbitmap_reset_all(data->hb); - check_hbitmap_iter_next(&hbi); + hbitmap_iter_next(&hbi, true); } static void test_hbitmap_next_zero_check_range(TestHBitmapData *data, From patchwork Tue Aug 14 12:14:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 957476 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=2001:4830:134:3::11; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=virtuozzo.com Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41qWpV6RJdz9sBq for ; Tue, 14 Aug 2018 22:18:26 +1000 (AEST) Received: from localhost ([::1]:44042 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYHI-000699-GB for incoming@patchwork.ozlabs.org; Tue, 14 Aug 2018 08:18:24 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37584) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fpYDs-0002e9-TU 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-00052I-Rh for qemu-devel@nongnu.org; Tue, 14 Aug 2018 08:14:52 -0400 Received: from relay.sw.ru ([185.231.240.75]:51094) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fpYDn-000517-Gf; 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-NU; 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:43 +0300 Message-Id: <20180814121443.33114-9-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 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()" 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" This reverts commit a33fbb4f8b64226becf502a123733776ce319b24. The functionality is unused. Note: in addition to automatic revert, drop second parameter in hbitmap_iter_next() call from hbitmap_next_dirty_area() too. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/qemu/hbitmap.h | 5 +---- block/backup.c | 2 +- block/dirty-bitmap.c | 2 +- tests/test-hbitmap.c | 26 +++++++++++++------------- util/hbitmap.c | 12 ++++-------- 5 files changed, 20 insertions(+), 27 deletions(-) diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 7800317bf3..6d205167ce 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -345,14 +345,11 @@ void hbitmap_free_meta(HBitmap *hb); /** * hbitmap_iter_next: * @hbi: HBitmapIter to operate on. - * @advance: If true, advance the iterator. Otherwise, the next call - * of this function will return the same result (if that - * position is still dirty). * * Return the next bit that is set in @hbi's associated HBitmap, * or -1 if all remaining bits are zero. */ -int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance); +int64_t hbitmap_iter_next(HBitmapIter *hbi); /** * hbitmap_iter_next_word: diff --git a/block/backup.c b/block/backup.c index 9bfd3f7189..f033148f21 100644 --- a/block/backup.c +++ b/block/backup.c @@ -421,7 +421,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job) HBitmapIter hbi; hbitmap_iter_init(&hbi, job->copy_bitmap, 0); - while ((cluster = hbitmap_iter_next(&hbi, true)) != -1) { + while ((cluster = hbitmap_iter_next(&hbi)) != -1) { do { if (yield_and_check(job)) { return 0; diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index d9333175b3..d0d602ff52 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -525,7 +525,7 @@ void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter) int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter) { - return hbitmap_iter_next(&iter->hbi, true); + return hbitmap_iter_next(&iter->hbi); } /* Called within bdrv_dirty_bitmap_lock..unlock */ diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 5e43056970..17a3c807de 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -46,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data, i = first; for (;;) { - next = hbitmap_iter_next(&hbi, true); + next = hbitmap_iter_next(&hbi); if (next < 0) { next = data->size; } @@ -435,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data, /* Note that hbitmap_test_check has to be invoked manually in this test. */ hbitmap_test_init(data, 131072 << 7, 7); hbitmap_iter_init(&hbi, data->hb, 0); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0); hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8); hbitmap_iter_init(&hbi, data->hb, 0); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0); hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0); hbitmap_test_set(data, (131072 << 7) - 8, 8); hbitmap_iter_init(&hbi, data->hb, 0); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0); hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7); - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0); + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7); + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0); } static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff) @@ -893,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data, for (i = 0; i < num_positions; i++) { hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true); hbitmap_iter_init(&iter, data->hb, 0); - next = hbitmap_iter_next(&iter, true); + next = hbitmap_iter_next(&iter); if (i == num_positions - 1) { g_assert_cmpint(next, ==, -1); } else { @@ -919,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1); - hbitmap_iter_next(&hbi, true); + hbitmap_iter_next(&hbi); hbitmap_reset_all(data->hb); - hbitmap_iter_next(&hbi, true); + hbitmap_iter_next(&hbi); } static void test_hbitmap_next_zero_check_range(TestHBitmapData *data, diff --git a/util/hbitmap.c b/util/hbitmap.c index bf88c1223e..b00e05a85b 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -144,7 +144,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) return cur; } -int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance) +int64_t hbitmap_iter_next(HBitmapIter *hbi) { unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] & hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos]; @@ -157,12 +157,8 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance) } } - if (advance) { - /* The next call will resume work from the next bit. */ - hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); - } else { - hbi->cur[HBITMAP_LEVELS - 1] = cur; - } + /* The next call will resume work from the next bit. */ + hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur); return item << hbi->granularity; @@ -256,7 +252,7 @@ bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset, } hbitmap_iter_init(&hbi, hb, *offset); - off1 = hbitmap_iter_next(&hbi, true); + off1 = hbitmap_iter_next(&hbi); if (off1 < 0 || off1 >= end) { return false;