From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:40040) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TK2wP-0004Im-2g for qemu-devel@nongnu.org; Fri, 05 Oct 2012 04:07:30 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TK2wI-0003Vj-UA for qemu-devel@nongnu.org; Fri, 05 Oct 2012 04:07:24 -0400 Received: from mail-bk0-f45.google.com ([209.85.214.45]:44220) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TK2wI-0003Vd-ND for qemu-devel@nongnu.org; Fri, 05 Oct 2012 04:07:18 -0400 Received: by mail-bk0-f45.google.com with SMTP id jf3so643491bkc.4 for ; Fri, 05 Oct 2012 01:07:17 -0700 (PDT) Date: Fri, 5 Oct 2012 10:07:14 +0200 From: Stefan Hajnoczi Message-ID: <20121005080714.GB1399@stefanha-thinkpad.redhat.com> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Subject: Re: [Qemu-devel] Qcow2 allocate and free cluster List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Gaurab Basu Cc: qemu-devel@nongnu.org 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