From nobody Wed Apr 16 04:33:52 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 Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 1499791849818591.6571606900243; Tue, 11 Jul 2017 09:50:49 -0700 (PDT) Received: from localhost ([::1]:47561 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dUyN3-00032H-5i for importer@patchew.org; Tue, 11 Jul 2017 12:50:45 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:46753) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dUxm0-0001lJ-Qy for qemu-devel@nongnu.org; Tue, 11 Jul 2017 12:12:32 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dUxlu-000723-9r for qemu-devel@nongnu.org; Tue, 11 Jul 2017 12:12:23 -0400 Received: from mx1.redhat.com ([209.132.183.28]:52702) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1dUxlm-0006zZ-7N; Tue, 11 Jul 2017 12:12:14 -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 mx1.redhat.com (Postfix) with ESMTPS id 11DFC4E34E; Tue, 11 Jul 2017 16:12:13 +0000 (UTC) Received: from localhost (ovpn-204-123.brq.redhat.com [10.40.204.123]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 8C0E45D9C8; Tue, 11 Jul 2017 16:12:12 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 11DFC4E34E Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=mreitz@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 11DFC4E34E From: Max Reitz To: qemu-block@nongnu.org Date: Tue, 11 Jul 2017 18:07:53 +0200 Message-Id: <20170711160814.20941-65-mreitz@redhat.com> In-Reply-To: <20170711160814.20941-1-mreitz@redhat.com> References: <20170711160814.20941-1-mreitz@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.38]); Tue, 11 Jul 2017 16:12:13 +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 64/85] qcow2: make refcount size calculation conservative 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: qemu-devel@nongnu.org, Max Reitz Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.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" From: Stefan Hajnoczi The refcount metadata size calculation is inaccurate and can produce numbers that are too small. This is bad because we should calculate a conservative number - one that is guaranteed to be large enough. This patch switches the approach to a fixed point calculation because the existing equation is hard to solve when inaccuracies are taken care of. Signed-off-by: Stefan Hajnoczi Reviewed-by: Alberto Garcia Message-id: 20170705125738.8777-5-stefanha@redhat.com Signed-off-by: Max Reitz --- block/qcow2.c | 83 ++++++++++++++++++++++++++++++-------------------------= ---- 1 file changed, 42 insertions(+), 41 deletions(-) diff --git a/block/qcow2.c b/block/qcow2.c index 0506c7e..eb57013 100644 --- a/block/qcow2.c +++ b/block/qcow2.c @@ -2537,6 +2537,43 @@ static int preallocate(BlockDriverState *bs) return 0; } =20 +/* qcow2_refcount_metadata_size: + * @clusters: number of clusters to refcount (including data and L1/L2 tab= les) + * @cluster_size: size of a cluster, in bytes + * @refcount_order: refcount bits power-of-2 exponent + * + * Returns: Number of bytes required for refcount blocks and table metadat= a. + */ +static int64_t qcow2_refcount_metadata_size(int64_t clusters, + size_t cluster_size, + int refcount_order) +{ + /* + * Every host cluster is reference-counted, including metadata (even + * refcount metadata is recursively included). + * + * An accurate formula for the size of refcount metadata size is diffi= cult + * to derive. An easier method of calculation is finding the fixed po= int + * where no further refcount blocks or table clusters are required to + * reference count every cluster. + */ + int64_t blocks_per_table_cluster =3D cluster_size / sizeof(uint64_t); + int64_t refcounts_per_block =3D cluster_size * 8 / (1 << refcount_orde= r); + int64_t table =3D 0; /* number of refcount table clusters */ + int64_t blocks =3D 0; /* number of refcount block clusters */ + int64_t last; + int64_t n =3D 0; + + do { + last =3D n; + blocks =3D DIV_ROUND_UP(clusters + table + blocks, refcounts_per_b= lock); + table =3D DIV_ROUND_UP(blocks, blocks_per_table_cluster); + n =3D clusters + blocks + table; + } while (n !=3D last); + + return (blocks + table) * cluster_size; +} + /** * qcow2_calc_prealloc_size: * @total_size: virtual disk size in bytes @@ -2550,22 +2587,9 @@ static int64_t qcow2_calc_prealloc_size(int64_t tota= l_size, size_t cluster_size, int refcount_order) { - /* Note: The following calculation does not need to be exact; if it is= a - * bit off, either some bytes will be "leaked" (which is fine) or we - * will need to increase the file size by some bytes (which is fine, - * too, as long as the bulk is allocated here). Therefore, using - * floating point arithmetic is fine. */ int64_t meta_size =3D 0; - uint64_t nreftablee, nrefblocke, nl1e, nl2e, refblock_count; + uint64_t nl1e, nl2e; int64_t aligned_total_size =3D align_offset(total_size, cluster_size); - int cluster_bits =3D ctz32(cluster_size); - int refblock_bits, refblock_size; - /* refcount entry size in bytes */ - double rces =3D (1 << refcount_order) / 8.; - - /* see qcow2_open() */ - refblock_bits =3D cluster_bits - (refcount_order - 3); - refblock_size =3D 1 << refblock_bits; =20 /* header: 1 cluster */ meta_size +=3D cluster_size; @@ -2580,33 +2604,10 @@ static int64_t qcow2_calc_prealloc_size(int64_t tot= al_size, nl1e =3D align_offset(nl1e, cluster_size / sizeof(uint64_t)); meta_size +=3D nl1e * sizeof(uint64_t); =20 - /* total size of refcount blocks - * - * note: every host cluster is reference-counted, including metadata - * (even refcount blocks are recursively included). - * Let: - * a =3D total_size (this is the guest disk size) - * m =3D meta size not including refcount blocks and refcount tables - * c =3D cluster size - * y1 =3D number of refcount blocks entries - * y2 =3D meta size including everything - * rces =3D refcount entry size in bytes - * then, - * y1 =3D (y2 + a)/c - * y2 =3D y1 * rces + y1 * rces * sizeof(u64) / c + m - * we can get y1: - * y1 =3D (a + m) / (c - rces - rces * sizeof(u64) / c) - */ - nrefblocke =3D (aligned_total_size + meta_size + cluster_size) - / (cluster_size - rces - rces * sizeof(uint64_t) - / cluster_size); - refblock_count =3D DIV_ROUND_UP(nrefblocke, refblock_size); - meta_size +=3D refblock_count * cluster_size; - - /* total size of refcount tables */ - nreftablee =3D align_offset(refblock_count, - cluster_size / sizeof(uint64_t)); - meta_size +=3D nreftablee * sizeof(uint64_t); + /* total size of refcount table and blocks */ + meta_size +=3D qcow2_refcount_metadata_size( + (meta_size + aligned_total_size) / cluster_size, + cluster_size, refcount_order); =20 return meta_size + aligned_total_size; } --=20 2.9.4