xref: /illumos-kvm-cmd/block/qcow2-refcount.c (revision 68396ea9)
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 
qcow2_refcount_init(BlockDriverState * bs)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 = qemu_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 
qcow2_refcount_close(BlockDriverState * bs)59 void qcow2_refcount_close(BlockDriverState *bs)
60 {
61     BDRVQcowState *s = bs->opaque;
62     qemu_free(s->refcount_table);
63 }
64 
65 
load_refcount_block(BlockDriverState * bs,int64_t refcount_block_offset,void ** refcount_block)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  */
get_refcount(BlockDriverState * bs,int64_t cluster_index)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  */
next_refcount_table_size(BDRVQcowState * s,unsigned int min_size)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 */
in_same_refcount_block(BDRVQcowState * s,uint64_t offset_a,uint64_t offset_b)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  */
alloc_refcount_block(BlockDriverState * bs,int64_t cluster_index,uint16_t ** refcount_block)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];
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 = qemu_mallocz(blocks_clusters * s->cluster_size);
327     uint64_t *new_table = qemu_mallocz(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     qemu_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         cpu_to_be64s(&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     qemu_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 new_block;
404 
405 fail_table:
406     qemu_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 ? */
update_refcount(BlockDriverState * bs,int64_t offset,int64_t length,int addend)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     printf("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  */
update_cluster_refcount(BlockDriverState * bs,int64_t cluster_index,int addend)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 */
alloc_clusters_noref(BlockDriverState * bs,int64_t size)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     printf("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 
qcow2_alloc_clusters(BlockDriverState * bs,int64_t size)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 /* only used to allocate compressed sectors. We try to allocate
586    contiguous sectors. size must be <= cluster_size */
qcow2_alloc_bytes(BlockDriverState * bs,int size)587 int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
588 {
589     BDRVQcowState *s = bs->opaque;
590     int64_t offset, cluster_offset;
591     int free_in_cluster;
592 
593     BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC_BYTES);
594     assert(size > 0 && size <= s->cluster_size);
595     if (s->free_byte_offset == 0) {
596         s->free_byte_offset = qcow2_alloc_clusters(bs, s->cluster_size);
597         if (s->free_byte_offset < 0) {
598             return s->free_byte_offset;
599         }
600     }
601  redo:
602     free_in_cluster = s->cluster_size -
603         (s->free_byte_offset & (s->cluster_size - 1));
604     if (size <= free_in_cluster) {
605         /* enough space in current cluster */
606         offset = s->free_byte_offset;
607         s->free_byte_offset += size;
608         free_in_cluster -= size;
609         if (free_in_cluster == 0)
610             s->free_byte_offset = 0;
611         if ((offset & (s->cluster_size - 1)) != 0)
612             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
613     } else {
614         offset = qcow2_alloc_clusters(bs, s->cluster_size);
615         if (offset < 0) {
616             return offset;
617         }
618         cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
619         if ((cluster_offset + s->cluster_size) == offset) {
620             /* we are lucky: contiguous data */
621             offset = s->free_byte_offset;
622             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
623             s->free_byte_offset += size;
624         } else {
625             s->free_byte_offset = offset;
626             goto redo;
627         }
628     }
629 
630     bdrv_flush(bs->file);
631     return offset;
632 }
633 
qcow2_free_clusters(BlockDriverState * bs,int64_t offset,int64_t size)634 void qcow2_free_clusters(BlockDriverState *bs,
635                           int64_t offset, int64_t size)
636 {
637     int ret;
638 
639     BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE);
640     ret = update_refcount(bs, offset, size, -1);
641     if (ret < 0) {
642         fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
643         /* TODO Remember the clusters to free them later and avoid leaking */
644     }
645 }
646 
647 /*
648  * free_any_clusters
649  *
650  * free clusters according to its type: compressed or not
651  *
652  */
653 
qcow2_free_any_clusters(BlockDriverState * bs,uint64_t cluster_offset,int nb_clusters)654 void qcow2_free_any_clusters(BlockDriverState *bs,
655     uint64_t cluster_offset, int nb_clusters)
656 {
657     BDRVQcowState *s = bs->opaque;
658 
659     /* free the cluster */
660 
661     if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
662         int nb_csectors;
663         nb_csectors = ((cluster_offset >> s->csize_shift) &
664                        s->csize_mask) + 1;
665         qcow2_free_clusters(bs,
666             (cluster_offset & s->cluster_offset_mask) & ~511,
667             nb_csectors * 512);
668         return;
669     }
670 
671     qcow2_free_clusters(bs, cluster_offset, nb_clusters << s->cluster_bits);
672 
673     return;
674 }
675 
676 
677 
678 /*********************************************************/
679 /* snapshots and image creation */
680 
681 
682 
qcow2_create_refcount_update(QCowCreateState * s,int64_t offset,int64_t size)683 void qcow2_create_refcount_update(QCowCreateState *s, int64_t offset,
684     int64_t size)
685 {
686     int refcount;
687     int64_t start, last, cluster_offset;
688     uint16_t *p;
689 
690     start = offset & ~(s->cluster_size - 1);
691     last = (offset + size - 1)  & ~(s->cluster_size - 1);
692     for(cluster_offset = start; cluster_offset <= last;
693         cluster_offset += s->cluster_size) {
694         p = &s->refcount_block[cluster_offset >> s->cluster_bits];
695         refcount = be16_to_cpu(*p);
696         refcount++;
697         *p = cpu_to_be16(refcount);
698     }
699 }
700 
701 /* update the refcounts of snapshots and the copied flag */
qcow2_update_snapshot_refcount(BlockDriverState * bs,int64_t l1_table_offset,int l1_size,int addend)702 int qcow2_update_snapshot_refcount(BlockDriverState *bs,
703     int64_t l1_table_offset, int l1_size, int addend)
704 {
705     BDRVQcowState *s = bs->opaque;
706     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
707     int64_t old_offset, old_l2_offset;
708     int i, j, l1_modified, nb_csectors, refcount;
709     int ret;
710 
711     l2_table = NULL;
712     l1_table = NULL;
713     l1_size2 = l1_size * sizeof(uint64_t);
714     if (l1_table_offset != s->l1_table_offset) {
715         if (l1_size2 != 0) {
716             l1_table = qemu_mallocz(align_offset(l1_size2, 512));
717         } else {
718             l1_table = NULL;
719         }
720         l1_allocated = 1;
721         if (bdrv_pread(bs->file, l1_table_offset,
722                        l1_table, l1_size2) != l1_size2)
723             goto fail;
724         for(i = 0;i < l1_size; i++)
725             be64_to_cpus(&l1_table[i]);
726     } else {
727         assert(l1_size == s->l1_size);
728         l1_table = s->l1_table;
729         l1_allocated = 0;
730     }
731 
732     l1_modified = 0;
733     for(i = 0; i < l1_size; i++) {
734         l2_offset = l1_table[i];
735         if (l2_offset) {
736             old_l2_offset = l2_offset;
737             l2_offset &= ~QCOW_OFLAG_COPIED;
738 
739             ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset,
740                 (void**) &l2_table);
741             if (ret < 0) {
742                 goto fail;
743             }
744 
745             for(j = 0; j < s->l2_size; j++) {
746                 offset = be64_to_cpu(l2_table[j]);
747                 if (offset != 0) {
748                     old_offset = offset;
749                     offset &= ~QCOW_OFLAG_COPIED;
750                     if (offset & QCOW_OFLAG_COMPRESSED) {
751                         nb_csectors = ((offset >> s->csize_shift) &
752                                        s->csize_mask) + 1;
753                         if (addend != 0) {
754                             int ret;
755                             ret = update_refcount(bs,
756                                 (offset & s->cluster_offset_mask) & ~511,
757                                 nb_csectors * 512, addend);
758                             if (ret < 0) {
759                                 goto fail;
760                             }
761 
762                             /* TODO Flushing once for the whole function should
763                              * be enough */
764                             bdrv_flush(bs->file);
765                         }
766                         /* compressed clusters are never modified */
767                         refcount = 2;
768                     } else {
769                         if (addend != 0) {
770                             refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
771                         } else {
772                             refcount = get_refcount(bs, offset >> s->cluster_bits);
773                         }
774 
775                         if (refcount < 0) {
776                             goto fail;
777                         }
778                     }
779 
780                     if (refcount == 1) {
781                         offset |= QCOW_OFLAG_COPIED;
782                     }
783                     if (offset != old_offset) {
784                         if (addend > 0) {
785                             qcow2_cache_set_dependency(bs, s->l2_table_cache,
786                                 s->refcount_block_cache);
787                         }
788                         l2_table[j] = cpu_to_be64(offset);
789                         qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
790                     }
791                 }
792             }
793 
794             ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
795             if (ret < 0) {
796                 goto fail;
797             }
798 
799 
800             if (addend != 0) {
801                 refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
802             } else {
803                 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
804             }
805             if (refcount < 0) {
806                 goto fail;
807             } else if (refcount == 1) {
808                 l2_offset |= QCOW_OFLAG_COPIED;
809             }
810             if (l2_offset != old_l2_offset) {
811                 l1_table[i] = l2_offset;
812                 l1_modified = 1;
813             }
814         }
815     }
816     if (l1_modified) {
817         for(i = 0; i < l1_size; i++)
818             cpu_to_be64s(&l1_table[i]);
819         if (bdrv_pwrite_sync(bs->file, l1_table_offset, l1_table,
820                         l1_size2) < 0)
821             goto fail;
822         for(i = 0; i < l1_size; i++)
823             be64_to_cpus(&l1_table[i]);
824     }
825     if (l1_allocated)
826         qemu_free(l1_table);
827     return 0;
828  fail:
829     if (l2_table) {
830         qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
831     }
832 
833     if (l1_allocated)
834         qemu_free(l1_table);
835     return -EIO;
836 }
837 
838 
839 
840 
841 /*********************************************************/
842 /* refcount checking functions */
843 
844 
845 
846 /*
847  * Increases the refcount for a range of clusters in a given refcount table.
848  * This is used to construct a temporary refcount table out of L1 and L2 tables
849  * which can be compared the the refcount table saved in the image.
850  *
851  * Modifies the number of errors in res.
852  */
inc_refcounts(BlockDriverState * bs,BdrvCheckResult * res,uint16_t * refcount_table,int refcount_table_size,int64_t offset,int64_t size)853 static void inc_refcounts(BlockDriverState *bs,
854                           BdrvCheckResult *res,
855                           uint16_t *refcount_table,
856                           int refcount_table_size,
857                           int64_t offset, int64_t size)
858 {
859     BDRVQcowState *s = bs->opaque;
860     int64_t start, last, cluster_offset;
861     int k;
862 
863     if (size <= 0)
864         return;
865 
866     start = offset & ~(s->cluster_size - 1);
867     last = (offset + size - 1) & ~(s->cluster_size - 1);
868     for(cluster_offset = start; cluster_offset <= last;
869         cluster_offset += s->cluster_size) {
870         k = cluster_offset >> s->cluster_bits;
871         if (k < 0) {
872             fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
873                 cluster_offset);
874             res->corruptions++;
875         } else if (k >= refcount_table_size) {
876             fprintf(stderr, "Warning: cluster offset=0x%" PRIx64 " is after "
877                 "the end of the image file, can't properly check refcounts.\n",
878                 cluster_offset);
879             res->check_errors++;
880         } else {
881             if (++refcount_table[k] == 0) {
882                 fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
883                     "\n", cluster_offset);
884                 res->corruptions++;
885             }
886         }
887     }
888 }
889 
890 /*
891  * Increases the refcount in the given refcount table for the all clusters
892  * referenced in the L2 table. While doing so, performs some checks on L2
893  * entries.
894  *
895  * Returns the number of errors found by the checks or -errno if an internal
896  * error occurred.
897  */
check_refcounts_l2(BlockDriverState * bs,BdrvCheckResult * res,uint16_t * refcount_table,int refcount_table_size,int64_t l2_offset,int check_copied)898 static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res,
899     uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
900     int check_copied)
901 {
902     BDRVQcowState *s = bs->opaque;
903     uint64_t *l2_table, offset;
904     int i, l2_size, nb_csectors, refcount;
905 
906     /* Read L2 table from disk */
907     l2_size = s->l2_size * sizeof(uint64_t);
908     l2_table = qemu_malloc(l2_size);
909 
910     if (bdrv_pread(bs->file, l2_offset, l2_table, l2_size) != l2_size)
911         goto fail;
912 
913     /* Do the actual checks */
914     for(i = 0; i < s->l2_size; i++) {
915         offset = be64_to_cpu(l2_table[i]);
916         if (offset != 0) {
917             if (offset & QCOW_OFLAG_COMPRESSED) {
918                 /* Compressed clusters don't have QCOW_OFLAG_COPIED */
919                 if (offset & QCOW_OFLAG_COPIED) {
920                     fprintf(stderr, "ERROR: cluster %" PRId64 ": "
921                         "copied flag must never be set for compressed "
922                         "clusters\n", offset >> s->cluster_bits);
923                     offset &= ~QCOW_OFLAG_COPIED;
924                     res->corruptions++;
925                 }
926 
927                 /* Mark cluster as used */
928                 nb_csectors = ((offset >> s->csize_shift) &
929                                s->csize_mask) + 1;
930                 offset &= s->cluster_offset_mask;
931                 inc_refcounts(bs, res, refcount_table, refcount_table_size,
932                     offset & ~511, nb_csectors * 512);
933             } else {
934                 /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
935                 if (check_copied) {
936                     uint64_t entry = offset;
937                     offset &= ~QCOW_OFLAG_COPIED;
938                     refcount = get_refcount(bs, offset >> s->cluster_bits);
939                     if (refcount < 0) {
940                         fprintf(stderr, "Can't get refcount for offset %"
941                             PRIx64 ": %s\n", entry, strerror(-refcount));
942                         goto fail;
943                     }
944                     if ((refcount == 1) != ((entry & QCOW_OFLAG_COPIED) != 0)) {
945                         fprintf(stderr, "ERROR OFLAG_COPIED: offset=%"
946                             PRIx64 " refcount=%d\n", entry, refcount);
947                         res->corruptions++;
948                     }
949                 }
950 
951                 /* Mark cluster as used */
952                 offset &= ~QCOW_OFLAG_COPIED;
953                 inc_refcounts(bs, res, refcount_table,refcount_table_size,
954                     offset, s->cluster_size);
955 
956                 /* Correct offsets are cluster aligned */
957                 if (offset & (s->cluster_size - 1)) {
958                     fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
959                         "properly aligned; L2 entry corrupted.\n", offset);
960                     res->corruptions++;
961                 }
962             }
963         }
964     }
965 
966     qemu_free(l2_table);
967     return 0;
968 
969 fail:
970     fprintf(stderr, "ERROR: I/O error in check_refcounts_l2\n");
971     qemu_free(l2_table);
972     return -EIO;
973 }
974 
975 /*
976  * Increases the refcount for the L1 table, its L2 tables and all referenced
977  * clusters in the given refcount table. While doing so, performs some checks
978  * on L1 and L2 entries.
979  *
980  * Returns the number of errors found by the checks or -errno if an internal
981  * error occurred.
982  */
check_refcounts_l1(BlockDriverState * bs,BdrvCheckResult * res,uint16_t * refcount_table,int refcount_table_size,int64_t l1_table_offset,int l1_size,int check_copied)983 static int check_refcounts_l1(BlockDriverState *bs,
984                               BdrvCheckResult *res,
985                               uint16_t *refcount_table,
986                               int refcount_table_size,
987                               int64_t l1_table_offset, int l1_size,
988                               int check_copied)
989 {
990     BDRVQcowState *s = bs->opaque;
991     uint64_t *l1_table, l2_offset, l1_size2;
992     int i, refcount, ret;
993 
994     l1_size2 = l1_size * sizeof(uint64_t);
995 
996     /* Mark L1 table as used */
997     inc_refcounts(bs, res, refcount_table, refcount_table_size,
998         l1_table_offset, l1_size2);
999 
1000     /* Read L1 table entries from disk */
1001     if (l1_size2 == 0) {
1002         l1_table = NULL;
1003     } else {
1004         l1_table = qemu_malloc(l1_size2);
1005         if (bdrv_pread(bs->file, l1_table_offset,
1006                        l1_table, l1_size2) != l1_size2)
1007             goto fail;
1008         for(i = 0;i < l1_size; i++)
1009             be64_to_cpus(&l1_table[i]);
1010     }
1011 
1012     /* Do the actual checks */
1013     for(i = 0; i < l1_size; i++) {
1014         l2_offset = l1_table[i];
1015         if (l2_offset) {
1016             /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
1017             if (check_copied) {
1018                 refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED)
1019                     >> s->cluster_bits);
1020                 if (refcount < 0) {
1021                     fprintf(stderr, "Can't get refcount for l2_offset %"
1022                         PRIx64 ": %s\n", l2_offset, strerror(-refcount));
1023                     goto fail;
1024                 }
1025                 if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
1026                     fprintf(stderr, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
1027                         " refcount=%d\n", l2_offset, refcount);
1028                     res->corruptions++;
1029                 }
1030             }
1031 
1032             /* Mark L2 table as used */
1033             l2_offset &= ~QCOW_OFLAG_COPIED;
1034             inc_refcounts(bs, res, refcount_table, refcount_table_size,
1035                 l2_offset, s->cluster_size);
1036 
1037             /* L2 tables are cluster aligned */
1038             if (l2_offset & (s->cluster_size - 1)) {
1039                 fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
1040                     "cluster aligned; L1 entry corrupted\n", l2_offset);
1041                 res->corruptions++;
1042             }
1043 
1044             /* Process and check L2 entries */
1045             ret = check_refcounts_l2(bs, res, refcount_table,
1046                 refcount_table_size, l2_offset, check_copied);
1047             if (ret < 0) {
1048                 goto fail;
1049             }
1050         }
1051     }
1052     qemu_free(l1_table);
1053     return 0;
1054 
1055 fail:
1056     fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
1057     res->check_errors++;
1058     qemu_free(l1_table);
1059     return -EIO;
1060 }
1061 
1062 /*
1063  * Checks an image for refcount consistency.
1064  *
1065  * Returns 0 if no errors are found, the number of errors in case the image is
1066  * detected as corrupted, and -errno when an internal error occured.
1067  */
qcow2_check_refcounts(BlockDriverState * bs,BdrvCheckResult * res)1068 int qcow2_check_refcounts(BlockDriverState *bs, BdrvCheckResult *res)
1069 {
1070     BDRVQcowState *s = bs->opaque;
1071     int64_t size;
1072     int nb_clusters, refcount1, refcount2, i;
1073     QCowSnapshot *sn;
1074     uint16_t *refcount_table;
1075     int ret;
1076 
1077     size = bdrv_getlength(bs->file);
1078     nb_clusters = size_to_clusters(s, size);
1079     refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
1080 
1081     /* header */
1082     inc_refcounts(bs, res, refcount_table, nb_clusters,
1083         0, s->cluster_size);
1084 
1085     /* current L1 table */
1086     ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1087                        s->l1_table_offset, s->l1_size, 1);
1088     if (ret < 0) {
1089         return ret;
1090     }
1091 
1092     /* snapshots */
1093     for(i = 0; i < s->nb_snapshots; i++) {
1094         sn = s->snapshots + i;
1095         ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1096             sn->l1_table_offset, sn->l1_size, 0);
1097         if (ret < 0) {
1098             return ret;
1099         }
1100     }
1101     inc_refcounts(bs, res, refcount_table, nb_clusters,
1102         s->snapshots_offset, s->snapshots_size);
1103 
1104     /* refcount data */
1105     inc_refcounts(bs, res, refcount_table, nb_clusters,
1106         s->refcount_table_offset,
1107         s->refcount_table_size * sizeof(uint64_t));
1108 
1109     for(i = 0; i < s->refcount_table_size; i++) {
1110         uint64_t offset, cluster;
1111         offset = s->refcount_table[i];
1112         cluster = offset >> s->cluster_bits;
1113 
1114         /* Refcount blocks are cluster aligned */
1115         if (offset & (s->cluster_size - 1)) {
1116             fprintf(stderr, "ERROR refcount block %d is not "
1117                 "cluster aligned; refcount table entry corrupted\n", i);
1118             res->corruptions++;
1119             continue;
1120         }
1121 
1122         if (cluster >= nb_clusters) {
1123             fprintf(stderr, "ERROR refcount block %d is outside image\n", i);
1124             res->corruptions++;
1125             continue;
1126         }
1127 
1128         if (offset != 0) {
1129             inc_refcounts(bs, res, refcount_table, nb_clusters,
1130                 offset, s->cluster_size);
1131             if (refcount_table[cluster] != 1) {
1132                 fprintf(stderr, "ERROR refcount block %d refcount=%d\n",
1133                     i, refcount_table[cluster]);
1134                 res->corruptions++;
1135             }
1136         }
1137     }
1138 
1139     /* compare ref counts */
1140     for(i = 0; i < nb_clusters; i++) {
1141         refcount1 = get_refcount(bs, i);
1142         if (refcount1 < 0) {
1143             fprintf(stderr, "Can't get refcount for cluster %d: %s\n",
1144                 i, strerror(-refcount1));
1145             res->check_errors++;
1146             continue;
1147         }
1148 
1149         refcount2 = refcount_table[i];
1150         if (refcount1 != refcount2) {
1151             fprintf(stderr, "%s cluster %d refcount=%d reference=%d\n",
1152                    refcount1 < refcount2 ? "ERROR" : "Leaked",
1153                    i, refcount1, refcount2);
1154             if (refcount1 < refcount2) {
1155                 res->corruptions++;
1156             } else {
1157                 res->leaks++;
1158             }
1159         }
1160     }
1161 
1162     qemu_free(refcount_table);
1163 
1164     return 0;
1165 }
1166 
1167