Re: [Qemu-devel] Qcow2 allocate and free cluster

[Stefan Hajnoczi]

On Fri, Sep 21, 2012 at 11:15:42AM +0530, Gaurab Basu wrote:
> My question is how the clusters are allocated. What I have understood, it
> maintains a free_cluster_index to manage which host clusters are free.
> In the function update_refcount(), if a cluster is freed it makes the
> free_cluster_index point to that cluster. (if cluster_index <
> free_cluster_index )
> For allocating, in the function alloc_clusters_noref(), it uses the
> free_cluster_index to search for free clusters.
> 
> So, suppose I have 1000 clusters which are all allocated, then while
> freeing, the 2nd cluster gets freed, so the free_cluster_index points to
> 2nd cluster.
> Now, if want to allocate 5 contiguous clusters, i have to search all the
> way from 2 to 1000 before getting the 5 clusters.
> Am I right in interpreting the mechanism?. If so, isn't it very slow to
> search for all the clusters everytime.

free_cluster_index is just a "last freed cluster" index.  The real allocation
map is the refcount data, which records whether each image file cluster is in
use or not.

The refcount data needs to be searched if free_cluster_index doesn't point to a
location with enough free space.  Fancier data structures could be used to
track free space but this potential performance bottleneck is needs a benchmark
so that optimization can be done scientifically.

Do you have a case where finding free clusters is a bottleneck?

Stefan