Re: [Qemu-devel] [PATCH v6 4/9] qcow2: make refcount size calculation conservative

[Max Reitz]

On 08.05.2017 16:15, Stefan Hajnoczi wrote:
> 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 <address@hidden>
> Reviewed-by: Alberto Garcia <address@hidden>
> ---
>  block/qcow2.c | 82 
> ++++++++++++++++++++++++++++++-----------------------------
>  1 file changed, 42 insertions(+), 40 deletions(-)
> 
> diff --git a/block/qcow2.c b/block/qcow2.c
> index 5569b63..ff0d825 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.

Oh, by the way:

https://lists.nongnu.org/archive/html/qemu-devel/2014-04/msg04820.html

*cough* *cough*

(No, this is not the formula that was used for this preallocation.
Otherwise, it would have been correct. O:-))

Max

>                     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

signature.asc
Description: OpenPGP digital signature