From nobody Mon Feb 9 10:28:29 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of redhat.com designates 63.128.21.74 as permitted sender) client-ip=63.128.21.74; envelope-from=libvir-list-bounces@redhat.com; helo=us-smtp-delivery-74.mimecast.com; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of redhat.com designates 63.128.21.74 as permitted sender) smtp.mailfrom=libvir-list-bounces@redhat.com; dmarc=pass(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1584420076; cv=none; d=zohomail.com; s=zohoarc; b=VRgp6cfj4b9i7AxvmkoWbheXwarKseWeOBuhmGNyriHGVztjNR9ssm4zNn6RZf9S2puBomKGZiWEshdIIb6EXPk4Ab21oQ2hEuw3+kVSN7yWRomNDsXlyUq/LjavdRRcn7iryWBzkzmJhR8/CPLC7IW3roJNwMoW0aoa2fX/D8g= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1584420076; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=hJmvqTqXqTMPCSVQr1qy1e1SoPh13NTfRknUTlZehjg=; b=MeuT0HxYmdne1jfkUqJo3tBD3S8nIBu6xdf0Gqixf5aGhfMQnc7a9o6QLxY2+xsbNoPet4UgCbVMnaSLJUIVqzbjv6TnWuQatbmFa+TQF3iHf4sTLFtSqNRAZV2XWjRytZP3owseGcuMGngSwtsYYzbNV1Xxoxhyc0x4J3c0OgU= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of redhat.com designates 63.128.21.74 as permitted sender) smtp.mailfrom=libvir-list-bounces@redhat.com; dmarc=pass header.from= (p=none dis=none) header.from= Return-Path: Received: from us-smtp-delivery-74.mimecast.com (us-smtp-delivery-74.mimecast.com [63.128.21.74]) by mx.zohomail.com with SMTPS id 1584420076304242.02825849526687; Mon, 16 Mar 2020 21:41:16 -0700 (PDT) Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-104-jYo68iLeOgq3YxTzs1_aXQ-1; Tue, 17 Mar 2020 00:39:13 -0400 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id CCF6A8010EC; Tue, 17 Mar 2020 04:39:04 +0000 (UTC) Received: from colo-mx.corp.redhat.com (colo-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.20]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 92DC95D9C9; Tue, 17 Mar 2020 04:39:04 +0000 (UTC) Received: from lists01.pubmisc.prod.ext.phx2.redhat.com (lists01.pubmisc.prod.ext.phx2.redhat.com [10.5.19.33]) by colo-mx.corp.redhat.com (Postfix) with ESMTP id 2946718089D8; Tue, 17 Mar 2020 04:39:04 +0000 (UTC) Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by lists01.pubmisc.prod.ext.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id 02H4cmYS012375 for ; Tue, 17 Mar 2020 00:38:48 -0400 Received: by smtp.corp.redhat.com (Postfix) id 83D201036B47; Tue, 17 Mar 2020 04:38:48 +0000 (UTC) Received: from probe.redhat.com (ovpn-112-191.rdu2.redhat.com [10.10.112.191]) by smtp.corp.redhat.com (Postfix) with ESMTP id 911EB10016EB; Tue, 17 Mar 2020 04:38:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1584420075; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:list-id:list-help: list-unsubscribe:list-subscribe:list-post; bh=hJmvqTqXqTMPCSVQr1qy1e1SoPh13NTfRknUTlZehjg=; b=EfN7wkRh7PKVDwbeQUfU75ru3L+qneb/NmanwMtQbf9N4yeMsX902Uw2NG7q/j+NW+Lv8E LpPrU6cOUX9JxrdPE9ZWy6Sko8sQuxdD8Cn6HiujNPFNKZCB9GLLCX7FLnSz6BZ/Qtxsuz FqrvyuHP5PZtbzYggdFcx3kjhTGWZjI= X-MC-Unique: jYo68iLeOgq3YxTzs1_aXQ-1 From: John Snow To: qemu-devel@nongnu.org, Peter Maydell , jsnow@redhat.com Subject: [PULL 07/10] block/dirty-bitmap: improve _next_dirty_area API Date: Tue, 17 Mar 2020 00:38:16 -0400 Message-Id: <20200317043819.20197-8-jsnow@redhat.com> In-Reply-To: <20200317043819.20197-1-jsnow@redhat.com> References: <20200317043819.20197-1-jsnow@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-loop: libvir-list@redhat.com Cc: Kevin Wolf , Fam Zheng , Vladimir Sementsov-Ogievskiy , qemu-block@nongnu.org, Juan Quintela , libvir-list@redhat.com, "Dr. David Alan Gilbert" , Stefan Hajnoczi , Max Reitz X-BeenThere: libvir-list@redhat.com X-Mailman-Version: 2.1.12 Precedence: junk List-Id: Development discussions about the libvirt library & tools List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: libvir-list-bounces@redhat.com Errors-To: libvir-list-bounces@redhat.com X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @redhat.com) Content-Type: text/plain; charset="utf-8" From: Vladimir Sementsov-Ogievskiy Firstly, _next_dirty_area is for scenarios when we may contiguously search for next dirty area inside some limited region, so it is more comfortable to specify "end" which should not be recalculated on each iteration. Secondly, let's add a possibility to limit resulting area size, not limiting searching area. This will be used in NBD code in further commit. (Note that now bdrv_dirty_bitmap_next_dirty_area is unused) Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: Max Reitz Reviewed-by: John Snow Message-id: 20200205112041.6003-8-vsementsov@virtuozzo.com Signed-off-by: John Snow --- include/block/dirty-bitmap.h | 3 ++- include/qemu/hbitmap.h | 23 ++++++++++-------- block/dirty-bitmap.c | 6 +++-- tests/test-hbitmap.c | 45 +++++++++++++++++++++++------------- util/hbitmap.c | 44 +++++++++++++++++++++-------------- 5 files changed, 75 insertions(+), 46 deletions(-) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index b1f0de12db..8a10029418 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -110,7 +110,8 @@ int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *b= itmap, int64_t offset, int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offse= t, int64_t bytes); bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, - int64_t *offset, int64_t *bytes); + int64_t start, int64_t end, int64_t max_dirty_count, + int64_t *dirty_start, int64_t *dirty_count); BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap, Error **errp); =20 diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 6e9ae51ed3..5e71b6d6f7 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -324,18 +324,21 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t = start, int64_t count); =20 /* hbitmap_next_dirty_area: * @hb: The HBitmap to operate on - * @start: in-out parameter. - * in: the offset to start from - * out: (if area found) start of found area - * @count: in-out parameter. - * in: length of requested region - * out: length of found area + * @start: the offset to start from + * @end: end of requested area + * @max_dirty_count: limit for out parameter dirty_count + * @dirty_start: on success: start of found area + * @dirty_count: on success: length of found area * - * If dirty area found within [@start, @start + @count), returns true and = sets - * @offset and @bytes appropriately. Otherwise returns false and leaves @o= ffset - * and @bytes unchanged. + * If dirty area found within [@start, @end), returns true and sets + * @dirty_start and @dirty_count appropriately. @dirty_count will not exce= ed + * @max_dirty_count. + * If dirty area was not found, returns false and leaves @dirty_start and + * @dirty_count unchanged. */ -bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *c= ount); +bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end, + int64_t max_dirty_count, + int64_t *dirty_start, int64_t *dirty_count); =20 /** * hbitmap_iter_next: diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index 1b14c8eb26..063793e316 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -873,9 +873,11 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *b= itmap, int64_t offset, } =20 bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, - int64_t *offset, int64_t *bytes) + int64_t start, int64_t end, int64_t max_dirty_count, + int64_t *dirty_start, int64_t *dirty_count) { - return hbitmap_next_dirty_area(bitmap->bitmap, offset, bytes); + return hbitmap_next_dirty_area(bitmap->bitmap, start, end, max_dirty_c= ount, + dirty_start, dirty_count); } =20 /** diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 8905b8a351..b6726cf76b 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -920,18 +920,19 @@ static void test_hbitmap_next_x_after_truncate(TestHB= itmapData *data, test_hbitmap_next_x_check(data, 0); } =20 -static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data, - int64_t offset, - int64_t count) +static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *da= ta, + int64_t offset, + int64_t count, + int64_t max_dirty) { int64_t off1, off2; int64_t len1 =3D 0, len2; bool ret1, ret2; int64_t end; =20 - off1 =3D offset; - len1 =3D count; - ret1 =3D hbitmap_next_dirty_area(data->hb, &off1, &len1); + ret1 =3D hbitmap_next_dirty_area(data->hb, + offset, count =3D=3D INT64_MAX ? INT64_MAX : offset + count, m= ax_dirty, + &off1, &len1); =20 end =3D offset > data->size || data->size - offset < count ? data->siz= e : offset + co= unt; @@ -940,21 +941,25 @@ static void test_hbitmap_next_dirty_area_check(TestHB= itmapData *data, ; } =20 - for (len2 =3D 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len= 2); - len2++) { + for (len2 =3D 1; (off2 + len2 < end && len2 < max_dirty && + hbitmap_get(data->hb, off2 + len2)); len2++) + { ; } =20 ret2 =3D off2 < end; - if (!ret2) { - /* leave unchanged */ - off2 =3D offset; - len2 =3D count; - } - g_assert_cmpint(ret1, =3D=3D, ret2); - g_assert_cmpint(off1, =3D=3D, off2); - g_assert_cmpint(len1, =3D=3D, len2); + + if (ret2) { + g_assert_cmpint(off1, =3D=3D, off2); + g_assert_cmpint(len1, =3D=3D, len2); + } +} + +static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data, + int64_t offset, int64_t cou= nt) +{ + test_hbitmap_next_dirty_area_check_limited(data, offset, count, INT64_= MAX); } =20 static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data, @@ -964,6 +969,7 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmap= Data *data, test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); test_hbitmap_next_dirty_area_check(data, 0, 1); test_hbitmap_next_dirty_area_check(data, L3 - 1, 1); + test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1); =20 hbitmap_set(data->hb, L2, 1); test_hbitmap_next_dirty_area_check(data, 0, 1); @@ -976,6 +982,8 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmap= Data *data, test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX); test_hbitmap_next_dirty_area_check(data, L2, 1); test_hbitmap_next_dirty_area_check(data, L2 + 1, 1); + test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1); + test_hbitmap_next_dirty_area_check_limited(data, L2 - 1, 2, 1); =20 hbitmap_set(data->hb, L2 + 5, L1); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); @@ -988,6 +996,8 @@ static void test_hbitmap_next_dirty_area_do(TestHBitmap= Data *data, 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); + test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, INT64_MAX, 3); + test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, 7, 10); =20 hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); @@ -997,6 +1007,9 @@ static void test_hbitmap_next_dirty_area_do(TestHBitma= pData *data, 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); + test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, INT64_MAX= , 5); + test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 10, 5); + test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 2, 5); =20 hbitmap_set(data->hb, 0, L3); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); diff --git a/util/hbitmap.c b/util/hbitmap.c index 883ca48fa6..305b894a63 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -270,22 +270,33 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t = start, int64_t count) return res; } =20 -bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *c= ount) +bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end, + int64_t max_dirty_count, + int64_t *dirty_start, int64_t *dirty_count) { - int64_t area_start, area_end; + int64_t next_zero; =20 - area_start =3D hbitmap_next_dirty(hb, *start, *count); - if (area_start < 0) { + assert(start >=3D 0 && end >=3D 0 && max_dirty_count > 0); + + end =3D MIN(end, hb->orig_size); + if (start >=3D end) { return false; } =20 - area_end =3D hbitmap_next_zero(hb, area_start, *start + *count - area_= start); - if (area_end < 0) { - area_end =3D MIN(hb->orig_size, *start + *count); + start =3D hbitmap_next_dirty(hb, start, end - start); + if (start < 0) { + return false; + } + + end =3D start + MIN(end - start, max_dirty_count); + + next_zero =3D hbitmap_next_zero(hb, start, end - start); + if (next_zero >=3D 0) { + end =3D next_zero; } =20 - *start =3D area_start; - *count =3D area_end - area_start; + *dirty_start =3D start; + *dirty_count =3D end - start; =20 return true; } @@ -841,16 +852,15 @@ bool hbitmap_can_merge(const HBitmap *a, const HBitma= p *b) */ static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src) { - int64_t offset =3D 0; - int64_t count =3D src->orig_size; + int64_t offset; + int64_t count; =20 - while (hbitmap_next_dirty_area(src, &offset, &count)) { + for (offset =3D 0; + hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX, + &offset, &count); + offset +=3D count) + { hbitmap_set(dst, offset, count); - offset +=3D count; - if (offset >=3D src->orig_size) { - break; - } - count =3D src->orig_size - offset; } } =20 --=20 2.21.1