From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:52554) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d0Tdj-00041Q-UW for qemu-devel@nongnu.org; Tue, 18 Apr 2017 09:57:57 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d0Tdi-00089R-NG for qemu-devel@nongnu.org; Tue, 18 Apr 2017 09:57:56 -0400 Received: from mx1.redhat.com ([209.132.183.28]:55356) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1d0Tdi-000894-9t for qemu-devel@nongnu.org; Tue, 18 Apr 2017 09:57:54 -0400 From: Stefan Hajnoczi Date: Tue, 18 Apr 2017 14:57:21 +0100 Message-Id: <20170418135726.28022-5-stefanha@redhat.com> In-Reply-To: <20170418135726.28022-1-stefanha@redhat.com> References: <20170418135726.28022-1-stefanha@redhat.com> Subject: [Qemu-devel] [PATCH v5 4/9] qcow2: make refcount size calculation conservative List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: Eric Blake , Kevin Wolf , Maor Lipchuk , "Daniel P. Berrange" , Nir Soffer , Alberto Garcia , John Snow , 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 --- block/qcow2.c | 82 ++++++++++++++++++++++++++++++----------------------------- 1 file changed, 42 insertions(+), 40 deletions(-) diff --git a/block/qcow2.c b/block/qcow2.c index 7c702f4..ffc529e 100644 --- a/block/qcow2.c +++ b/block/qcow2.c @@ -2095,6 +2095,43 @@ static int preallocate(BlockDriverState *bs) return 0; } +/* qcow2_refcount_metadata_size: + * @clusters: number of clusters to refcount (including data and L1/L2 tables) + * @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 metadata. + */ +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 difficult + * to derive. An easier method of calculation is finding the fixed point + * where no further refcount blocks or table clusters are required to + * reference count every cluster. + */ + int64_t blocks_per_table_cluster = cluster_size / sizeof(uint64_t); + int64_t refcounts_per_block = cluster_size * 8 / (1 << refcount_order); + int64_t table = 0; /* number of refcount table clusters */ + int64_t blocks = 0; /* number of refcount block clusters */ + int64_t last; + int64_t n = 0; + + do { + last = n; + blocks = DIV_ROUND_UP(clusters + table + blocks, refcounts_per_block); + table = DIV_ROUND_UP(blocks, blocks_per_table_cluster); + n = clusters + blocks + table; + } while (n != last); + + return (blocks + table) * cluster_size; +} + /** * qcow2_calc_prealloc_size: * @total_size: virtual disk size in bytes @@ -2108,22 +2145,9 @@ static int64_t qcow2_calc_prealloc_size(int64_t total_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 = 0; - uint64_t nreftablee, nrefblocke, nl1e, nl2e; + uint64_t nl1e, nl2e; int64_t aligned_total_size = align_offset(total_size, cluster_size); - int cluster_bits = ctz32(cluster_size); - int refblock_bits, refblock_size; - /* refcount entry size in bytes */ - double rces = (1 << refcount_order) / 8.; - - /* see qcow2_open() */ - refblock_bits = cluster_bits - (refcount_order - 3); - refblock_size = 1 << refblock_bits; /* header: 1 cluster */ meta_size += cluster_size; @@ -2138,32 +2162,10 @@ static int64_t qcow2_calc_prealloc_size(int64_t total_size, nl1e = align_offset(nl1e, cluster_size / sizeof(uint64_t)); meta_size += nl1e * sizeof(uint64_t); - /* total size of refcount blocks - * - * note: every host cluster is reference-counted, including metadata - * (even refcount blocks are recursively included). - * Let: - * a = total_size (this is the guest disk size) - * m = meta size not including refcount blocks and refcount tables - * c = cluster size - * y1 = number of refcount blocks entries - * y2 = meta size including everything - * rces = refcount entry size in bytes - * then, - * y1 = (y2 + a)/c - * y2 = y1 * rces + y1 * rces * sizeof(u64) / c + m - * we can get y1: - * y1 = (a + m) / (c - rces - rces * sizeof(u64) / c) - */ - nrefblocke = (aligned_total_size + meta_size + cluster_size) - / (cluster_size - rces - rces * sizeof(uint64_t) - / cluster_size); - meta_size += DIV_ROUND_UP(nrefblocke, refblock_size) * cluster_size; - - /* total size of refcount tables */ - nreftablee = nrefblocke / refblock_size; - nreftablee = align_offset(nreftablee, cluster_size / sizeof(uint64_t)); - meta_size += nreftablee * sizeof(uint64_t); + /* total size of refcount table and blocks */ + meta_size += qcow2_refcount_metadata_size( + (meta_size + aligned_total_size) / cluster_size, + cluster_size, refcount_order); return meta_size + aligned_total_size; } -- 2.9.3