xref: /openbmc/qemu/block/qcow2-refcount.c (revision 01afdadc)
1 /*
2  * Block driver for the QCOW version 2 format
3  *
4  * Copyright (c) 2004-2006 Fabrice Bellard
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22  * THE SOFTWARE.
23  */
24 
25 #include "qemu-common.h"
26 #include "block_int.h"
27 #include "block/qcow2.h"
28 
29 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size);
30 static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
31                             int64_t offset, int64_t length,
32                             int addend);
33 
34 
35 /*********************************************************/
36 /* refcount handling */
37 
38 int qcow2_refcount_init(BlockDriverState *bs)
39 {
40     BDRVQcowState *s = bs->opaque;
41     int ret, refcount_table_size2, i;
42 
43     refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
44     s->refcount_table = g_malloc(refcount_table_size2);
45     if (s->refcount_table_size > 0) {
46         BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_LOAD);
47         ret = bdrv_pread(bs->file, s->refcount_table_offset,
48                          s->refcount_table, refcount_table_size2);
49         if (ret != refcount_table_size2)
50             goto fail;
51         for(i = 0; i < s->refcount_table_size; i++)
52             be64_to_cpus(&s->refcount_table[i]);
53     }
54     return 0;
55  fail:
56     return -ENOMEM;
57 }
58 
59 void qcow2_refcount_close(BlockDriverState *bs)
60 {
61     BDRVQcowState *s = bs->opaque;
62     g_free(s->refcount_table);
63 }
64 
65 
66 static int load_refcount_block(BlockDriverState *bs,
67                                int64_t refcount_block_offset,
68                                void **refcount_block)
69 {
70     BDRVQcowState *s = bs->opaque;
71     int ret;
72 
73     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_LOAD);
74     ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset,
75         refcount_block);
76 
77     return ret;
78 }
79 
80 /*
81  * Returns the refcount of the cluster given by its index. Any non-negative
82  * return value is the refcount of the cluster, negative values are -errno
83  * and indicate an error.
84  */
85 static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
86 {
87     BDRVQcowState *s = bs->opaque;
88     int refcount_table_index, block_index;
89     int64_t refcount_block_offset;
90     int ret;
91     uint16_t *refcount_block;
92     uint16_t refcount;
93 
94     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
95     if (refcount_table_index >= s->refcount_table_size)
96         return 0;
97     refcount_block_offset = s->refcount_table[refcount_table_index];
98     if (!refcount_block_offset)
99         return 0;
100 
101     ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset,
102         (void**) &refcount_block);
103     if (ret < 0) {
104         return ret;
105     }
106 
107     block_index = cluster_index &
108         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
109     refcount = be16_to_cpu(refcount_block[block_index]);
110 
111     ret = qcow2_cache_put(bs, s->refcount_block_cache,
112         (void**) &refcount_block);
113     if (ret < 0) {
114         return ret;
115     }
116 
117     return refcount;
118 }
119 
120 /*
121  * Rounds the refcount table size up to avoid growing the table for each single
122  * refcount block that is allocated.
123  */
124 static unsigned int next_refcount_table_size(BDRVQcowState *s,
125     unsigned int min_size)
126 {
127     unsigned int min_clusters = (min_size >> (s->cluster_bits - 3)) + 1;
128     unsigned int refcount_table_clusters =
129         MAX(1, s->refcount_table_size >> (s->cluster_bits - 3));
130 
131     while (min_clusters > refcount_table_clusters) {
132         refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
133     }
134 
135     return refcount_table_clusters << (s->cluster_bits - 3);
136 }
137 
138 
139 /* Checks if two offsets are described by the same refcount block */
140 static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a,
141     uint64_t offset_b)
142 {
143     uint64_t block_a = offset_a >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
144     uint64_t block_b = offset_b >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
145 
146     return (block_a == block_b);
147 }
148 
149 /*
150  * Loads a refcount block. If it doesn't exist yet, it is allocated first
151  * (including growing the refcount table if needed).
152  *
153  * Returns 0 on success or -errno in error case
154  */
155 static int alloc_refcount_block(BlockDriverState *bs,
156     int64_t cluster_index, uint16_t **refcount_block)
157 {
158     BDRVQcowState *s = bs->opaque;
159     unsigned int refcount_table_index;
160     int ret;
161 
162     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC);
163 
164     /* Find the refcount block for the given cluster */
165     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
166 
167     if (refcount_table_index < s->refcount_table_size) {
168 
169         uint64_t refcount_block_offset =
170             s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK;
171 
172         /* If it's already there, we're done */
173         if (refcount_block_offset) {
174              return load_refcount_block(bs, refcount_block_offset,
175                  (void**) refcount_block);
176         }
177     }
178 
179     /*
180      * If we came here, we need to allocate something. Something is at least
181      * a cluster for the new refcount block. It may also include a new refcount
182      * table if the old refcount table is too small.
183      *
184      * Note that allocating clusters here needs some special care:
185      *
186      * - We can't use the normal qcow2_alloc_clusters(), it would try to
187      *   increase the refcount and very likely we would end up with an endless
188      *   recursion. Instead we must place the refcount blocks in a way that
189      *   they can describe them themselves.
190      *
191      * - We need to consider that at this point we are inside update_refcounts
192      *   and doing the initial refcount increase. This means that some clusters
193      *   have already been allocated by the caller, but their refcount isn't
194      *   accurate yet. free_cluster_index tells us where this allocation ends
195      *   as long as we don't overwrite it by freeing clusters.
196      *
197      * - alloc_clusters_noref and qcow2_free_clusters may load a different
198      *   refcount block into the cache
199      */
200 
201     *refcount_block = NULL;
202 
203     /* We write to the refcount table, so we might depend on L2 tables */
204     qcow2_cache_flush(bs, s->l2_table_cache);
205 
206     /* Allocate the refcount block itself and mark it as used */
207     int64_t new_block = alloc_clusters_noref(bs, s->cluster_size);
208     if (new_block < 0) {
209         return new_block;
210     }
211 
212 #ifdef DEBUG_ALLOC2
213     fprintf(stderr, "qcow2: Allocate refcount block %d for %" PRIx64
214         " at %" PRIx64 "\n",
215         refcount_table_index, cluster_index << s->cluster_bits, new_block);
216 #endif
217 
218     if (in_same_refcount_block(s, new_block, cluster_index << s->cluster_bits)) {
219         /* Zero the new refcount block before updating it */
220         ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block,
221             (void**) refcount_block);
222         if (ret < 0) {
223             goto fail_block;
224         }
225 
226         memset(*refcount_block, 0, s->cluster_size);
227 
228         /* The block describes itself, need to update the cache */
229         int block_index = (new_block >> s->cluster_bits) &
230             ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
231         (*refcount_block)[block_index] = cpu_to_be16(1);
232     } else {
233         /* Described somewhere else. This can recurse at most twice before we
234          * arrive at a block that describes itself. */
235         ret = update_refcount(bs, new_block, s->cluster_size, 1);
236         if (ret < 0) {
237             goto fail_block;
238         }
239 
240         bdrv_flush(bs->file);
241 
242         /* Initialize the new refcount block only after updating its refcount,
243          * update_refcount uses the refcount cache itself */
244         ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block,
245             (void**) refcount_block);
246         if (ret < 0) {
247             goto fail_block;
248         }
249 
250         memset(*refcount_block, 0, s->cluster_size);
251     }
252 
253     /* Now the new refcount block needs to be written to disk */
254     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE);
255     qcow2_cache_entry_mark_dirty(s->refcount_block_cache, *refcount_block);
256     ret = qcow2_cache_flush(bs, s->refcount_block_cache);
257     if (ret < 0) {
258         goto fail_block;
259     }
260 
261     /* If the refcount table is big enough, just hook the block up there */
262     if (refcount_table_index < s->refcount_table_size) {
263         uint64_t data64 = cpu_to_be64(new_block);
264         BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_HOOKUP);
265         ret = bdrv_pwrite_sync(bs->file,
266             s->refcount_table_offset + refcount_table_index * sizeof(uint64_t),
267             &data64, sizeof(data64));
268         if (ret < 0) {
269             goto fail_block;
270         }
271 
272         s->refcount_table[refcount_table_index] = new_block;
273         return 0;
274     }
275 
276     ret = qcow2_cache_put(bs, s->refcount_block_cache, (void**) refcount_block);
277     if (ret < 0) {
278         goto fail_block;
279     }
280 
281     /*
282      * If we come here, we need to grow the refcount table. Again, a new
283      * refcount table needs some space and we can't simply allocate to avoid
284      * endless recursion.
285      *
286      * Therefore let's grab new refcount blocks at the end of the image, which
287      * will describe themselves and the new refcount table. This way we can
288      * reference them only in the new table and do the switch to the new
289      * refcount table at once without producing an inconsistent state in
290      * between.
291      */
292     BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW);
293 
294     /* Calculate the number of refcount blocks needed so far */
295     uint64_t refcount_block_clusters = 1 << (s->cluster_bits - REFCOUNT_SHIFT);
296     uint64_t blocks_used = (s->free_cluster_index +
297         refcount_block_clusters - 1) / refcount_block_clusters;
298 
299     /* And now we need at least one block more for the new metadata */
300     uint64_t table_size = next_refcount_table_size(s, blocks_used + 1);
301     uint64_t last_table_size;
302     uint64_t blocks_clusters;
303     do {
304         uint64_t table_clusters = size_to_clusters(s, table_size);
305         blocks_clusters = 1 +
306             ((table_clusters + refcount_block_clusters - 1)
307             / refcount_block_clusters);
308         uint64_t meta_clusters = table_clusters + blocks_clusters;
309 
310         last_table_size = table_size;
311         table_size = next_refcount_table_size(s, blocks_used +
312             ((meta_clusters + refcount_block_clusters - 1)
313             / refcount_block_clusters));
314 
315     } while (last_table_size != table_size);
316 
317 #ifdef DEBUG_ALLOC2
318     fprintf(stderr, "qcow2: Grow refcount table %" PRId32 " => %" PRId64 "\n",
319         s->refcount_table_size, table_size);
320 #endif
321 
322     /* Create the new refcount table and blocks */
323     uint64_t meta_offset = (blocks_used * refcount_block_clusters) *
324         s->cluster_size;
325     uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
326     uint16_t *new_blocks = g_malloc0(blocks_clusters * s->cluster_size);
327     uint64_t *new_table = g_malloc0(table_size * sizeof(uint64_t));
328 
329     assert(meta_offset >= (s->free_cluster_index * s->cluster_size));
330 
331     /* Fill the new refcount table */
332     memcpy(new_table, s->refcount_table,
333         s->refcount_table_size * sizeof(uint64_t));
334     new_table[refcount_table_index] = new_block;
335 
336     int i;
337     for (i = 0; i < blocks_clusters; i++) {
338         new_table[blocks_used + i] = meta_offset + (i * s->cluster_size);
339     }
340 
341     /* Fill the refcount blocks */
342     uint64_t table_clusters = size_to_clusters(s, table_size * sizeof(uint64_t));
343     int block = 0;
344     for (i = 0; i < table_clusters + blocks_clusters; i++) {
345         new_blocks[block++] = cpu_to_be16(1);
346     }
347 
348     /* Write refcount blocks to disk */
349     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_BLOCKS);
350     ret = bdrv_pwrite_sync(bs->file, meta_offset, new_blocks,
351         blocks_clusters * s->cluster_size);
352     g_free(new_blocks);
353     if (ret < 0) {
354         goto fail_table;
355     }
356 
357     /* Write refcount table to disk */
358     for(i = 0; i < table_size; i++) {
359         cpu_to_be64s(&new_table[i]);
360     }
361 
362     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_TABLE);
363     ret = bdrv_pwrite_sync(bs->file, table_offset, new_table,
364         table_size * sizeof(uint64_t));
365     if (ret < 0) {
366         goto fail_table;
367     }
368 
369     for(i = 0; i < table_size; i++) {
370         be64_to_cpus(&new_table[i]);
371     }
372 
373     /* Hook up the new refcount table in the qcow2 header */
374     uint8_t data[12];
375     cpu_to_be64w((uint64_t*)data, table_offset);
376     cpu_to_be32w((uint32_t*)(data + 8), table_clusters);
377     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_SWITCH_TABLE);
378     ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, refcount_table_offset),
379         data, sizeof(data));
380     if (ret < 0) {
381         goto fail_table;
382     }
383 
384     /* And switch it in memory */
385     uint64_t old_table_offset = s->refcount_table_offset;
386     uint64_t old_table_size = s->refcount_table_size;
387 
388     g_free(s->refcount_table);
389     s->refcount_table = new_table;
390     s->refcount_table_size = table_size;
391     s->refcount_table_offset = table_offset;
392 
393     /* Free old table. Remember, we must not change free_cluster_index */
394     uint64_t old_free_cluster_index = s->free_cluster_index;
395     qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
396     s->free_cluster_index = old_free_cluster_index;
397 
398     ret = load_refcount_block(bs, new_block, (void**) refcount_block);
399     if (ret < 0) {
400         return ret;
401     }
402 
403     return 0;
404 
405 fail_table:
406     g_free(new_table);
407 fail_block:
408     if (*refcount_block != NULL) {
409         qcow2_cache_put(bs, s->refcount_block_cache, (void**) refcount_block);
410     }
411     return ret;
412 }
413 
414 /* XXX: cache several refcount block clusters ? */
415 static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
416     int64_t offset, int64_t length, int addend)
417 {
418     BDRVQcowState *s = bs->opaque;
419     int64_t start, last, cluster_offset;
420     uint16_t *refcount_block = NULL;
421     int64_t old_table_index = -1;
422     int ret;
423 
424 #ifdef DEBUG_ALLOC2
425     fprintf(stderr, "update_refcount: offset=%" PRId64 " size=%" PRId64 " addend=%d\n",
426            offset, length, addend);
427 #endif
428     if (length < 0) {
429         return -EINVAL;
430     } else if (length == 0) {
431         return 0;
432     }
433 
434     if (addend < 0) {
435         qcow2_cache_set_dependency(bs, s->refcount_block_cache,
436             s->l2_table_cache);
437     }
438 
439     start = offset & ~(s->cluster_size - 1);
440     last = (offset + length - 1) & ~(s->cluster_size - 1);
441     for(cluster_offset = start; cluster_offset <= last;
442         cluster_offset += s->cluster_size)
443     {
444         int block_index, refcount;
445         int64_t cluster_index = cluster_offset >> s->cluster_bits;
446         int64_t table_index =
447             cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
448 
449         /* Load the refcount block and allocate it if needed */
450         if (table_index != old_table_index) {
451             if (refcount_block) {
452                 ret = qcow2_cache_put(bs, s->refcount_block_cache,
453                     (void**) &refcount_block);
454                 if (ret < 0) {
455                     goto fail;
456                 }
457             }
458 
459             ret = alloc_refcount_block(bs, cluster_index, &refcount_block);
460             if (ret < 0) {
461                 goto fail;
462             }
463         }
464         old_table_index = table_index;
465 
466         qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block);
467 
468         /* we can update the count and save it */
469         block_index = cluster_index &
470             ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
471 
472         refcount = be16_to_cpu(refcount_block[block_index]);
473         refcount += addend;
474         if (refcount < 0 || refcount > 0xffff) {
475             ret = -EINVAL;
476             goto fail;
477         }
478         if (refcount == 0 && cluster_index < s->free_cluster_index) {
479             s->free_cluster_index = cluster_index;
480         }
481         refcount_block[block_index] = cpu_to_be16(refcount);
482     }
483 
484     ret = 0;
485 fail:
486     /* Write last changed block to disk */
487     if (refcount_block) {
488         int wret;
489         wret = qcow2_cache_put(bs, s->refcount_block_cache,
490             (void**) &refcount_block);
491         if (wret < 0) {
492             return ret < 0 ? ret : wret;
493         }
494     }
495 
496     /*
497      * Try do undo any updates if an error is returned (This may succeed in
498      * some cases like ENOSPC for allocating a new refcount block)
499      */
500     if (ret < 0) {
501         int dummy;
502         dummy = update_refcount(bs, offset, cluster_offset - offset, -addend);
503         (void)dummy;
504     }
505 
506     return ret;
507 }
508 
509 /*
510  * Increases or decreases the refcount of a given cluster by one.
511  * addend must be 1 or -1.
512  *
513  * If the return value is non-negative, it is the new refcount of the cluster.
514  * If it is negative, it is -errno and indicates an error.
515  */
516 static int update_cluster_refcount(BlockDriverState *bs,
517                                    int64_t cluster_index,
518                                    int addend)
519 {
520     BDRVQcowState *s = bs->opaque;
521     int ret;
522 
523     ret = update_refcount(bs, cluster_index << s->cluster_bits, 1, addend);
524     if (ret < 0) {
525         return ret;
526     }
527 
528     bdrv_flush(bs->file);
529 
530     return get_refcount(bs, cluster_index);
531 }
532 
533 
534 
535 /*********************************************************/
536 /* cluster allocation functions */
537 
538 
539 
540 /* return < 0 if error */
541 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
542 {
543     BDRVQcowState *s = bs->opaque;
544     int i, nb_clusters, refcount;
545 
546     nb_clusters = size_to_clusters(s, size);
547 retry:
548     for(i = 0; i < nb_clusters; i++) {
549         int64_t next_cluster_index = s->free_cluster_index++;
550         refcount = get_refcount(bs, next_cluster_index);
551 
552         if (refcount < 0) {
553             return refcount;
554         } else if (refcount != 0) {
555             goto retry;
556         }
557     }
558 #ifdef DEBUG_ALLOC2
559     fprintf(stderr, "alloc_clusters: size=%" PRId64 " -> %" PRId64 "\n",
560             size,
561             (s->free_cluster_index - nb_clusters) << s->cluster_bits);
562 #endif
563     return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
564 }
565 
566 int64_t qcow2_alloc_clusters(BlockDriverState *bs, int64_t size)
567 {
568     int64_t offset;
569     int ret;
570 
571     BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC);
572     offset = alloc_clusters_noref(bs, size);
573     if (offset < 0) {
574         return offset;
575     }
576 
577     ret = update_refcount(bs, offset, size, 1);
578     if (ret < 0) {
579         return ret;
580     }
581 
582     return offset;
583 }
584 
585 int qcow2_alloc_clusters_at(BlockDriverState *bs, uint64_t offset,
586     int nb_clusters)
587 {
588     BDRVQcowState *s = bs->opaque;
589     uint64_t cluster_index;
590     uint64_t old_free_cluster_index;
591     int i, refcount, ret;
592 
593     /* Check how many clusters there are free */
594     cluster_index = offset >> s->cluster_bits;
595     for(i = 0; i < nb_clusters; i++) {
596         refcount = get_refcount(bs, cluster_index++);
597 
598         if (refcount < 0) {
599             return refcount;
600         } else if (refcount != 0) {
601             break;
602         }
603     }
604 
605     /* And then allocate them */
606     old_free_cluster_index = s->free_cluster_index;
607     s->free_cluster_index = cluster_index + i;
608 
609     ret = update_refcount(bs, offset, i << s->cluster_bits, 1);
610     if (ret < 0) {
611         return ret;
612     }
613 
614     s->free_cluster_index = old_free_cluster_index;
615 
616     return i;
617 }
618 
619 /* only used to allocate compressed sectors. We try to allocate
620    contiguous sectors. size must be <= cluster_size */
621 int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
622 {
623     BDRVQcowState *s = bs->opaque;
624     int64_t offset, cluster_offset;
625     int free_in_cluster;
626 
627     BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC_BYTES);
628     assert(size > 0 && size <= s->cluster_size);
629     if (s->free_byte_offset == 0) {
630         offset = qcow2_alloc_clusters(bs, s->cluster_size);
631         if (offset < 0) {
632             return offset;
633         }
634         s->free_byte_offset = offset;
635     }
636  redo:
637     free_in_cluster = s->cluster_size -
638         (s->free_byte_offset & (s->cluster_size - 1));
639     if (size <= free_in_cluster) {
640         /* enough space in current cluster */
641         offset = s->free_byte_offset;
642         s->free_byte_offset += size;
643         free_in_cluster -= size;
644         if (free_in_cluster == 0)
645             s->free_byte_offset = 0;
646         if ((offset & (s->cluster_size - 1)) != 0)
647             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
648     } else {
649         offset = qcow2_alloc_clusters(bs, s->cluster_size);
650         if (offset < 0) {
651             return offset;
652         }
653         cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
654         if ((cluster_offset + s->cluster_size) == offset) {
655             /* we are lucky: contiguous data */
656             offset = s->free_byte_offset;
657             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
658             s->free_byte_offset += size;
659         } else {
660             s->free_byte_offset = offset;
661             goto redo;
662         }
663     }
664 
665     bdrv_flush(bs->file);
666     return offset;
667 }
668 
669 void qcow2_free_clusters(BlockDriverState *bs,
670                           int64_t offset, int64_t size)
671 {
672     int ret;
673 
674     BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE);
675     ret = update_refcount(bs, offset, size, -1);
676     if (ret < 0) {
677         fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
678         /* TODO Remember the clusters to free them later and avoid leaking */
679     }
680 }
681 
682 /*
683  * Free a cluster using its L2 entry (handles clusters of all types, e.g.
684  * normal cluster, compressed cluster, etc.)
685  */
686 void qcow2_free_any_clusters(BlockDriverState *bs,
687     uint64_t l2_entry, int nb_clusters)
688 {
689     BDRVQcowState *s = bs->opaque;
690 
691     switch (qcow2_get_cluster_type(l2_entry)) {
692     case QCOW2_CLUSTER_COMPRESSED:
693         {
694             int nb_csectors;
695             nb_csectors = ((l2_entry >> s->csize_shift) &
696                            s->csize_mask) + 1;
697             qcow2_free_clusters(bs,
698                 (l2_entry & s->cluster_offset_mask) & ~511,
699                 nb_csectors * 512);
700         }
701         break;
702     case QCOW2_CLUSTER_NORMAL:
703         qcow2_free_clusters(bs, l2_entry & L2E_OFFSET_MASK,
704                             nb_clusters << s->cluster_bits);
705         break;
706     case QCOW2_CLUSTER_UNALLOCATED:
707     case QCOW2_CLUSTER_ZERO:
708         break;
709     default:
710         abort();
711     }
712 }
713 
714 
715 
716 /*********************************************************/
717 /* snapshots and image creation */
718 
719 
720 
721 /* update the refcounts of snapshots and the copied flag */
722 int qcow2_update_snapshot_refcount(BlockDriverState *bs,
723     int64_t l1_table_offset, int l1_size, int addend)
724 {
725     BDRVQcowState *s = bs->opaque;
726     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
727     int64_t old_offset, old_l2_offset;
728     int i, j, l1_modified = 0, nb_csectors, refcount;
729     int ret;
730 
731     l2_table = NULL;
732     l1_table = NULL;
733     l1_size2 = l1_size * sizeof(uint64_t);
734 
735     /* WARNING: qcow2_snapshot_goto relies on this function not using the
736      * l1_table_offset when it is the current s->l1_table_offset! Be careful
737      * when changing this! */
738     if (l1_table_offset != s->l1_table_offset) {
739         if (l1_size2 != 0) {
740             l1_table = g_malloc0(align_offset(l1_size2, 512));
741         } else {
742             l1_table = NULL;
743         }
744         l1_allocated = 1;
745         if (bdrv_pread(bs->file, l1_table_offset,
746                        l1_table, l1_size2) != l1_size2)
747         {
748             ret = -EIO;
749             goto fail;
750         }
751 
752         for(i = 0;i < l1_size; i++)
753             be64_to_cpus(&l1_table[i]);
754     } else {
755         assert(l1_size == s->l1_size);
756         l1_table = s->l1_table;
757         l1_allocated = 0;
758     }
759 
760     for(i = 0; i < l1_size; i++) {
761         l2_offset = l1_table[i];
762         if (l2_offset) {
763             old_l2_offset = l2_offset;
764             l2_offset &= L1E_OFFSET_MASK;
765 
766             ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset,
767                 (void**) &l2_table);
768             if (ret < 0) {
769                 goto fail;
770             }
771 
772             for(j = 0; j < s->l2_size; j++) {
773                 offset = be64_to_cpu(l2_table[j]);
774                 if (offset != 0) {
775                     old_offset = offset;
776                     offset &= ~QCOW_OFLAG_COPIED;
777                     if (offset & QCOW_OFLAG_COMPRESSED) {
778                         nb_csectors = ((offset >> s->csize_shift) &
779                                        s->csize_mask) + 1;
780                         if (addend != 0) {
781                             int ret;
782                             ret = update_refcount(bs,
783                                 (offset & s->cluster_offset_mask) & ~511,
784                                 nb_csectors * 512, addend);
785                             if (ret < 0) {
786                                 goto fail;
787                             }
788 
789                             /* TODO Flushing once for the whole function should
790                              * be enough */
791                             bdrv_flush(bs->file);
792                         }
793                         /* compressed clusters are never modified */
794                         refcount = 2;
795                     } else {
796                         uint64_t cluster_index = (offset & L2E_OFFSET_MASK) >> s->cluster_bits;
797                         if (addend != 0) {
798                             refcount = update_cluster_refcount(bs, cluster_index, addend);
799                         } else {
800                             refcount = get_refcount(bs, cluster_index);
801                         }
802 
803                         if (refcount < 0) {
804                             ret = -EIO;
805                             goto fail;
806                         }
807                     }
808 
809                     if (refcount == 1) {
810                         offset |= QCOW_OFLAG_COPIED;
811                     }
812                     if (offset != old_offset) {
813                         if (addend > 0) {
814                             qcow2_cache_set_dependency(bs, s->l2_table_cache,
815                                 s->refcount_block_cache);
816                         }
817                         l2_table[j] = cpu_to_be64(offset);
818                         qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
819                     }
820                 }
821             }
822 
823             ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
824             if (ret < 0) {
825                 goto fail;
826             }
827 
828 
829             if (addend != 0) {
830                 refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
831             } else {
832                 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
833             }
834             if (refcount < 0) {
835                 ret = -EIO;
836                 goto fail;
837             } else if (refcount == 1) {
838                 l2_offset |= QCOW_OFLAG_COPIED;
839             }
840             if (l2_offset != old_l2_offset) {
841                 l1_table[i] = l2_offset;
842                 l1_modified = 1;
843             }
844         }
845     }
846 
847     ret = 0;
848 fail:
849     if (l2_table) {
850         qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
851     }
852 
853     /* Update L1 only if it isn't deleted anyway (addend = -1) */
854     if (addend >= 0 && l1_modified) {
855         for(i = 0; i < l1_size; i++)
856             cpu_to_be64s(&l1_table[i]);
857         if (bdrv_pwrite_sync(bs->file, l1_table_offset, l1_table,
858                         l1_size2) < 0)
859             goto fail;
860         for(i = 0; i < l1_size; i++)
861             be64_to_cpus(&l1_table[i]);
862     }
863     if (l1_allocated)
864         g_free(l1_table);
865     return ret;
866 }
867 
868 
869 
870 
871 /*********************************************************/
872 /* refcount checking functions */
873 
874 
875 
876 /*
877  * Increases the refcount for a range of clusters in a given refcount table.
878  * This is used to construct a temporary refcount table out of L1 and L2 tables
879  * which can be compared the the refcount table saved in the image.
880  *
881  * Modifies the number of errors in res.
882  */
883 static void inc_refcounts(BlockDriverState *bs,
884                           BdrvCheckResult *res,
885                           uint16_t *refcount_table,
886                           int refcount_table_size,
887                           int64_t offset, int64_t size)
888 {
889     BDRVQcowState *s = bs->opaque;
890     int64_t start, last, cluster_offset;
891     int k;
892 
893     if (size <= 0)
894         return;
895 
896     start = offset & ~(s->cluster_size - 1);
897     last = (offset + size - 1) & ~(s->cluster_size - 1);
898     for(cluster_offset = start; cluster_offset <= last;
899         cluster_offset += s->cluster_size) {
900         k = cluster_offset >> s->cluster_bits;
901         if (k < 0) {
902             fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
903                 cluster_offset);
904             res->corruptions++;
905         } else if (k >= refcount_table_size) {
906             fprintf(stderr, "Warning: cluster offset=0x%" PRIx64 " is after "
907                 "the end of the image file, can't properly check refcounts.\n",
908                 cluster_offset);
909             res->check_errors++;
910         } else {
911             if (++refcount_table[k] == 0) {
912                 fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
913                     "\n", cluster_offset);
914                 res->corruptions++;
915             }
916         }
917     }
918 }
919 
920 /*
921  * Increases the refcount in the given refcount table for the all clusters
922  * referenced in the L2 table. While doing so, performs some checks on L2
923  * entries.
924  *
925  * Returns the number of errors found by the checks or -errno if an internal
926  * error occurred.
927  */
928 static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res,
929     uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
930     int check_copied)
931 {
932     BDRVQcowState *s = bs->opaque;
933     uint64_t *l2_table, l2_entry;
934     int i, l2_size, nb_csectors, refcount;
935 
936     /* Read L2 table from disk */
937     l2_size = s->l2_size * sizeof(uint64_t);
938     l2_table = g_malloc(l2_size);
939 
940     if (bdrv_pread(bs->file, l2_offset, l2_table, l2_size) != l2_size)
941         goto fail;
942 
943     /* Do the actual checks */
944     for(i = 0; i < s->l2_size; i++) {
945         l2_entry = be64_to_cpu(l2_table[i]);
946 
947         switch (qcow2_get_cluster_type(l2_entry)) {
948         case QCOW2_CLUSTER_COMPRESSED:
949             /* Compressed clusters don't have QCOW_OFLAG_COPIED */
950             if (l2_entry & QCOW_OFLAG_COPIED) {
951                 fprintf(stderr, "ERROR: cluster %" PRId64 ": "
952                     "copied flag must never be set for compressed "
953                     "clusters\n", l2_entry >> s->cluster_bits);
954                 l2_entry &= ~QCOW_OFLAG_COPIED;
955                 res->corruptions++;
956             }
957 
958             /* Mark cluster as used */
959             nb_csectors = ((l2_entry >> s->csize_shift) &
960                            s->csize_mask) + 1;
961             l2_entry &= s->cluster_offset_mask;
962             inc_refcounts(bs, res, refcount_table, refcount_table_size,
963                 l2_entry & ~511, nb_csectors * 512);
964             break;
965 
966         case QCOW2_CLUSTER_ZERO:
967             if ((l2_entry & L2E_OFFSET_MASK) == 0) {
968                 break;
969             }
970             /* fall through */
971 
972         case QCOW2_CLUSTER_NORMAL:
973         {
974             /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
975             uint64_t offset = l2_entry & L2E_OFFSET_MASK;
976 
977             if (check_copied) {
978                 refcount = get_refcount(bs, offset >> s->cluster_bits);
979                 if (refcount < 0) {
980                     fprintf(stderr, "Can't get refcount for offset %"
981                         PRIx64 ": %s\n", l2_entry, strerror(-refcount));
982                     goto fail;
983                 }
984                 if ((refcount == 1) != ((l2_entry & QCOW_OFLAG_COPIED) != 0)) {
985                     fprintf(stderr, "ERROR OFLAG_COPIED: offset=%"
986                         PRIx64 " refcount=%d\n", l2_entry, refcount);
987                     res->corruptions++;
988                 }
989             }
990 
991             /* Mark cluster as used */
992             inc_refcounts(bs, res, refcount_table,refcount_table_size,
993                 offset, s->cluster_size);
994 
995             /* Correct offsets are cluster aligned */
996             if (offset & (s->cluster_size - 1)) {
997                 fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
998                     "properly aligned; L2 entry corrupted.\n", offset);
999                 res->corruptions++;
1000             }
1001             break;
1002         }
1003 
1004         case QCOW2_CLUSTER_UNALLOCATED:
1005             break;
1006 
1007         default:
1008             abort();
1009         }
1010     }
1011 
1012     g_free(l2_table);
1013     return 0;
1014 
1015 fail:
1016     fprintf(stderr, "ERROR: I/O error in check_refcounts_l2\n");
1017     g_free(l2_table);
1018     return -EIO;
1019 }
1020 
1021 /*
1022  * Increases the refcount for the L1 table, its L2 tables and all referenced
1023  * clusters in the given refcount table. While doing so, performs some checks
1024  * on L1 and L2 entries.
1025  *
1026  * Returns the number of errors found by the checks or -errno if an internal
1027  * error occurred.
1028  */
1029 static int check_refcounts_l1(BlockDriverState *bs,
1030                               BdrvCheckResult *res,
1031                               uint16_t *refcount_table,
1032                               int refcount_table_size,
1033                               int64_t l1_table_offset, int l1_size,
1034                               int check_copied)
1035 {
1036     BDRVQcowState *s = bs->opaque;
1037     uint64_t *l1_table, l2_offset, l1_size2;
1038     int i, refcount, ret;
1039 
1040     l1_size2 = l1_size * sizeof(uint64_t);
1041 
1042     /* Mark L1 table as used */
1043     inc_refcounts(bs, res, refcount_table, refcount_table_size,
1044         l1_table_offset, l1_size2);
1045 
1046     /* Read L1 table entries from disk */
1047     if (l1_size2 == 0) {
1048         l1_table = NULL;
1049     } else {
1050         l1_table = g_malloc(l1_size2);
1051         if (bdrv_pread(bs->file, l1_table_offset,
1052                        l1_table, l1_size2) != l1_size2)
1053             goto fail;
1054         for(i = 0;i < l1_size; i++)
1055             be64_to_cpus(&l1_table[i]);
1056     }
1057 
1058     /* Do the actual checks */
1059     for(i = 0; i < l1_size; i++) {
1060         l2_offset = l1_table[i];
1061         if (l2_offset) {
1062             /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
1063             if (check_copied) {
1064                 refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED)
1065                     >> s->cluster_bits);
1066                 if (refcount < 0) {
1067                     fprintf(stderr, "Can't get refcount for l2_offset %"
1068                         PRIx64 ": %s\n", l2_offset, strerror(-refcount));
1069                     goto fail;
1070                 }
1071                 if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
1072                     fprintf(stderr, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
1073                         " refcount=%d\n", l2_offset, refcount);
1074                     res->corruptions++;
1075                 }
1076             }
1077 
1078             /* Mark L2 table as used */
1079             l2_offset &= L1E_OFFSET_MASK;
1080             inc_refcounts(bs, res, refcount_table, refcount_table_size,
1081                 l2_offset, s->cluster_size);
1082 
1083             /* L2 tables are cluster aligned */
1084             if (l2_offset & (s->cluster_size - 1)) {
1085                 fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
1086                     "cluster aligned; L1 entry corrupted\n", l2_offset);
1087                 res->corruptions++;
1088             }
1089 
1090             /* Process and check L2 entries */
1091             ret = check_refcounts_l2(bs, res, refcount_table,
1092                 refcount_table_size, l2_offset, check_copied);
1093             if (ret < 0) {
1094                 goto fail;
1095             }
1096         }
1097     }
1098     g_free(l1_table);
1099     return 0;
1100 
1101 fail:
1102     fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
1103     res->check_errors++;
1104     g_free(l1_table);
1105     return -EIO;
1106 }
1107 
1108 /*
1109  * Checks an image for refcount consistency.
1110  *
1111  * Returns 0 if no errors are found, the number of errors in case the image is
1112  * detected as corrupted, and -errno when an internal error occurred.
1113  */
1114 int qcow2_check_refcounts(BlockDriverState *bs, BdrvCheckResult *res,
1115                           BdrvCheckMode fix)
1116 {
1117     BDRVQcowState *s = bs->opaque;
1118     int64_t size, i;
1119     int nb_clusters, refcount1, refcount2;
1120     QCowSnapshot *sn;
1121     uint16_t *refcount_table;
1122     int ret;
1123 
1124     size = bdrv_getlength(bs->file);
1125     nb_clusters = size_to_clusters(s, size);
1126     refcount_table = g_malloc0(nb_clusters * sizeof(uint16_t));
1127 
1128     /* header */
1129     inc_refcounts(bs, res, refcount_table, nb_clusters,
1130         0, s->cluster_size);
1131 
1132     /* current L1 table */
1133     ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1134                        s->l1_table_offset, s->l1_size, 1);
1135     if (ret < 0) {
1136         goto fail;
1137     }
1138 
1139     /* snapshots */
1140     for(i = 0; i < s->nb_snapshots; i++) {
1141         sn = s->snapshots + i;
1142         ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1143             sn->l1_table_offset, sn->l1_size, 0);
1144         if (ret < 0) {
1145             goto fail;
1146         }
1147     }
1148     inc_refcounts(bs, res, refcount_table, nb_clusters,
1149         s->snapshots_offset, s->snapshots_size);
1150 
1151     /* refcount data */
1152     inc_refcounts(bs, res, refcount_table, nb_clusters,
1153         s->refcount_table_offset,
1154         s->refcount_table_size * sizeof(uint64_t));
1155 
1156     for(i = 0; i < s->refcount_table_size; i++) {
1157         uint64_t offset, cluster;
1158         offset = s->refcount_table[i];
1159         cluster = offset >> s->cluster_bits;
1160 
1161         /* Refcount blocks are cluster aligned */
1162         if (offset & (s->cluster_size - 1)) {
1163             fprintf(stderr, "ERROR refcount block %" PRId64 " is not "
1164                 "cluster aligned; refcount table entry corrupted\n", i);
1165             res->corruptions++;
1166             continue;
1167         }
1168 
1169         if (cluster >= nb_clusters) {
1170             fprintf(stderr, "ERROR refcount block %" PRId64
1171                     " is outside image\n", i);
1172             res->corruptions++;
1173             continue;
1174         }
1175 
1176         if (offset != 0) {
1177             inc_refcounts(bs, res, refcount_table, nb_clusters,
1178                 offset, s->cluster_size);
1179             if (refcount_table[cluster] != 1) {
1180                 fprintf(stderr, "ERROR refcount block %" PRId64
1181                     " refcount=%d\n",
1182                     i, refcount_table[cluster]);
1183                 res->corruptions++;
1184             }
1185         }
1186     }
1187 
1188     /* compare ref counts */
1189     for(i = 0; i < nb_clusters; i++) {
1190         refcount1 = get_refcount(bs, i);
1191         if (refcount1 < 0) {
1192             fprintf(stderr, "Can't get refcount for cluster %" PRId64 ": %s\n",
1193                 i, strerror(-refcount1));
1194             res->check_errors++;
1195             continue;
1196         }
1197 
1198         refcount2 = refcount_table[i];
1199         if (refcount1 != refcount2) {
1200 
1201             /* Check if we're allowed to fix the mismatch */
1202             int *num_fixed = NULL;
1203             if (refcount1 > refcount2 && (fix & BDRV_FIX_LEAKS)) {
1204                 num_fixed = &res->leaks_fixed;
1205             } else if (refcount1 < refcount2 && (fix & BDRV_FIX_ERRORS)) {
1206                 num_fixed = &res->corruptions_fixed;
1207             }
1208 
1209             fprintf(stderr, "%s cluster %" PRId64 " refcount=%d reference=%d\n",
1210                    num_fixed != NULL     ? "Repairing" :
1211                    refcount1 < refcount2 ? "ERROR" :
1212                                            "Leaked",
1213                    i, refcount1, refcount2);
1214 
1215             if (num_fixed) {
1216                 ret = update_refcount(bs, i << s->cluster_bits, 1,
1217                                       refcount2 - refcount1);
1218                 if (ret >= 0) {
1219                     (*num_fixed)++;
1220                     continue;
1221                 }
1222             }
1223 
1224             /* And if we couldn't, print an error */
1225             if (refcount1 < refcount2) {
1226                 res->corruptions++;
1227             } else {
1228                 res->leaks++;
1229             }
1230         }
1231     }
1232 
1233     ret = 0;
1234 
1235 fail:
1236     g_free(refcount_table);
1237 
1238     return ret;
1239 }
1240 
1241