2 * Block driver for the QCOW version 2 format
4 * Copyright (c) 2004-2006 Fabrice Bellard
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:
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
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
25 #include "qemu-common.h"
26 #include "block/block_int.h"
27 #include "block/qcow2.h"
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
,
35 /*********************************************************/
36 /* refcount handling */
38 int qcow2_refcount_init(BlockDriverState
*bs
)
40 BDRVQcowState
*s
= bs
->opaque
;
41 int ret
, refcount_table_size2
, i
;
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
)
51 for(i
= 0; i
< s
->refcount_table_size
; i
++)
52 be64_to_cpus(&s
->refcount_table
[i
]);
59 void qcow2_refcount_close(BlockDriverState
*bs
)
61 BDRVQcowState
*s
= bs
->opaque
;
62 g_free(s
->refcount_table
);
66 static int load_refcount_block(BlockDriverState
*bs
,
67 int64_t refcount_block_offset
,
68 void **refcount_block
)
70 BDRVQcowState
*s
= bs
->opaque
;
73 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_LOAD
);
74 ret
= qcow2_cache_get(bs
, s
->refcount_block_cache
, refcount_block_offset
,
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.
85 static int get_refcount(BlockDriverState
*bs
, int64_t cluster_index
)
87 BDRVQcowState
*s
= bs
->opaque
;
88 int refcount_table_index
, block_index
;
89 int64_t refcount_block_offset
;
91 uint16_t *refcount_block
;
94 refcount_table_index
= cluster_index
>> (s
->cluster_bits
- REFCOUNT_SHIFT
);
95 if (refcount_table_index
>= s
->refcount_table_size
)
97 refcount_block_offset
= s
->refcount_table
[refcount_table_index
];
98 if (!refcount_block_offset
)
101 ret
= qcow2_cache_get(bs
, s
->refcount_block_cache
, refcount_block_offset
,
102 (void**) &refcount_block
);
107 block_index
= cluster_index
&
108 ((1 << (s
->cluster_bits
- REFCOUNT_SHIFT
)) - 1);
109 refcount
= be16_to_cpu(refcount_block
[block_index
]);
111 ret
= qcow2_cache_put(bs
, s
->refcount_block_cache
,
112 (void**) &refcount_block
);
121 * Rounds the refcount table size up to avoid growing the table for each single
122 * refcount block that is allocated.
124 static unsigned int next_refcount_table_size(BDRVQcowState
*s
,
125 unsigned int min_size
)
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));
131 while (min_clusters
> refcount_table_clusters
) {
132 refcount_table_clusters
= (refcount_table_clusters
* 3 + 1) / 2;
135 return refcount_table_clusters
<< (s
->cluster_bits
- 3);
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
,
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
);
146 return (block_a
== block_b
);
150 * Loads a refcount block. If it doesn't exist yet, it is allocated first
151 * (including growing the refcount table if needed).
153 * Returns 0 on success or -errno in error case
155 static int alloc_refcount_block(BlockDriverState
*bs
,
156 int64_t cluster_index
, uint16_t **refcount_block
)
158 BDRVQcowState
*s
= bs
->opaque
;
159 unsigned int refcount_table_index
;
162 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_ALLOC
);
164 /* Find the refcount block for the given cluster */
165 refcount_table_index
= cluster_index
>> (s
->cluster_bits
- REFCOUNT_SHIFT
);
167 if (refcount_table_index
< s
->refcount_table_size
) {
169 uint64_t refcount_block_offset
=
170 s
->refcount_table
[refcount_table_index
] & REFT_OFFSET_MASK
;
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
);
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.
184 * Note that allocating clusters here needs some special care:
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.
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.
197 * - alloc_clusters_noref and qcow2_free_clusters may load a different
198 * refcount block into the cache
201 *refcount_block
= NULL
;
203 /* We write to the refcount table, so we might depend on L2 tables */
204 ret
= qcow2_cache_flush(bs
, s
->l2_table_cache
);
209 /* Allocate the refcount block itself and mark it as used */
210 int64_t new_block
= alloc_clusters_noref(bs
, s
->cluster_size
);
216 fprintf(stderr
, "qcow2: Allocate refcount block %d for %" PRIx64
218 refcount_table_index
, cluster_index
<< s
->cluster_bits
, new_block
);
221 if (in_same_refcount_block(s
, new_block
, cluster_index
<< s
->cluster_bits
)) {
222 /* Zero the new refcount block before updating it */
223 ret
= qcow2_cache_get_empty(bs
, s
->refcount_block_cache
, new_block
,
224 (void**) refcount_block
);
229 memset(*refcount_block
, 0, s
->cluster_size
);
231 /* The block describes itself, need to update the cache */
232 int block_index
= (new_block
>> s
->cluster_bits
) &
233 ((1 << (s
->cluster_bits
- REFCOUNT_SHIFT
)) - 1);
234 (*refcount_block
)[block_index
] = cpu_to_be16(1);
236 /* Described somewhere else. This can recurse at most twice before we
237 * arrive at a block that describes itself. */
238 ret
= update_refcount(bs
, new_block
, s
->cluster_size
, 1);
243 ret
= qcow2_cache_flush(bs
, s
->refcount_block_cache
);
248 /* Initialize the new refcount block only after updating its refcount,
249 * update_refcount uses the refcount cache itself */
250 ret
= qcow2_cache_get_empty(bs
, s
->refcount_block_cache
, new_block
,
251 (void**) refcount_block
);
256 memset(*refcount_block
, 0, s
->cluster_size
);
259 /* Now the new refcount block needs to be written to disk */
260 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_ALLOC_WRITE
);
261 qcow2_cache_entry_mark_dirty(s
->refcount_block_cache
, *refcount_block
);
262 ret
= qcow2_cache_flush(bs
, s
->refcount_block_cache
);
267 /* If the refcount table is big enough, just hook the block up there */
268 if (refcount_table_index
< s
->refcount_table_size
) {
269 uint64_t data64
= cpu_to_be64(new_block
);
270 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_ALLOC_HOOKUP
);
271 ret
= bdrv_pwrite_sync(bs
->file
,
272 s
->refcount_table_offset
+ refcount_table_index
* sizeof(uint64_t),
273 &data64
, sizeof(data64
));
278 s
->refcount_table
[refcount_table_index
] = new_block
;
282 ret
= qcow2_cache_put(bs
, s
->refcount_block_cache
, (void**) refcount_block
);
288 * If we come here, we need to grow the refcount table. Again, a new
289 * refcount table needs some space and we can't simply allocate to avoid
292 * Therefore let's grab new refcount blocks at the end of the image, which
293 * will describe themselves and the new refcount table. This way we can
294 * reference them only in the new table and do the switch to the new
295 * refcount table at once without producing an inconsistent state in
298 BLKDBG_EVENT(bs
->file
, BLKDBG_REFTABLE_GROW
);
300 /* Calculate the number of refcount blocks needed so far */
301 uint64_t refcount_block_clusters
= 1 << (s
->cluster_bits
- REFCOUNT_SHIFT
);
302 uint64_t blocks_used
= (s
->free_cluster_index
+
303 refcount_block_clusters
- 1) / refcount_block_clusters
;
305 /* And now we need at least one block more for the new metadata */
306 uint64_t table_size
= next_refcount_table_size(s
, blocks_used
+ 1);
307 uint64_t last_table_size
;
308 uint64_t blocks_clusters
;
310 uint64_t table_clusters
=
311 size_to_clusters(s
, table_size
* sizeof(uint64_t));
312 blocks_clusters
= 1 +
313 ((table_clusters
+ refcount_block_clusters
- 1)
314 / refcount_block_clusters
);
315 uint64_t meta_clusters
= table_clusters
+ blocks_clusters
;
317 last_table_size
= table_size
;
318 table_size
= next_refcount_table_size(s
, blocks_used
+
319 ((meta_clusters
+ refcount_block_clusters
- 1)
320 / refcount_block_clusters
));
322 } while (last_table_size
!= table_size
);
325 fprintf(stderr
, "qcow2: Grow refcount table %" PRId32
" => %" PRId64
"\n",
326 s
->refcount_table_size
, table_size
);
329 /* Create the new refcount table and blocks */
330 uint64_t meta_offset
= (blocks_used
* refcount_block_clusters
) *
332 uint64_t table_offset
= meta_offset
+ blocks_clusters
* s
->cluster_size
;
333 uint16_t *new_blocks
= g_malloc0(blocks_clusters
* s
->cluster_size
);
334 uint64_t *new_table
= g_malloc0(table_size
* sizeof(uint64_t));
336 assert(meta_offset
>= (s
->free_cluster_index
* s
->cluster_size
));
338 /* Fill the new refcount table */
339 memcpy(new_table
, s
->refcount_table
,
340 s
->refcount_table_size
* sizeof(uint64_t));
341 new_table
[refcount_table_index
] = new_block
;
344 for (i
= 0; i
< blocks_clusters
; i
++) {
345 new_table
[blocks_used
+ i
] = meta_offset
+ (i
* s
->cluster_size
);
348 /* Fill the refcount blocks */
349 uint64_t table_clusters
= size_to_clusters(s
, table_size
* sizeof(uint64_t));
351 for (i
= 0; i
< table_clusters
+ blocks_clusters
; i
++) {
352 new_blocks
[block
++] = cpu_to_be16(1);
355 /* Write refcount blocks to disk */
356 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_ALLOC_WRITE_BLOCKS
);
357 ret
= bdrv_pwrite_sync(bs
->file
, meta_offset
, new_blocks
,
358 blocks_clusters
* s
->cluster_size
);
364 /* Write refcount table to disk */
365 for(i
= 0; i
< table_size
; i
++) {
366 cpu_to_be64s(&new_table
[i
]);
369 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_ALLOC_WRITE_TABLE
);
370 ret
= bdrv_pwrite_sync(bs
->file
, table_offset
, new_table
,
371 table_size
* sizeof(uint64_t));
376 for(i
= 0; i
< table_size
; i
++) {
377 be64_to_cpus(&new_table
[i
]);
380 /* Hook up the new refcount table in the qcow2 header */
382 cpu_to_be64w((uint64_t*)data
, table_offset
);
383 cpu_to_be32w((uint32_t*)(data
+ 8), table_clusters
);
384 BLKDBG_EVENT(bs
->file
, BLKDBG_REFBLOCK_ALLOC_SWITCH_TABLE
);
385 ret
= bdrv_pwrite_sync(bs
->file
, offsetof(QCowHeader
, refcount_table_offset
),
391 /* And switch it in memory */
392 uint64_t old_table_offset
= s
->refcount_table_offset
;
393 uint64_t old_table_size
= s
->refcount_table_size
;
395 g_free(s
->refcount_table
);
396 s
->refcount_table
= new_table
;
397 s
->refcount_table_size
= table_size
;
398 s
->refcount_table_offset
= table_offset
;
400 /* Free old table. Remember, we must not change free_cluster_index */
401 uint64_t old_free_cluster_index
= s
->free_cluster_index
;
402 qcow2_free_clusters(bs
, old_table_offset
, old_table_size
* sizeof(uint64_t));
403 s
->free_cluster_index
= old_free_cluster_index
;
405 ret
= load_refcount_block(bs
, new_block
, (void**) refcount_block
);
415 if (*refcount_block
!= NULL
) {
416 qcow2_cache_put(bs
, s
->refcount_block_cache
, (void**) refcount_block
);
421 /* XXX: cache several refcount block clusters ? */
422 static int QEMU_WARN_UNUSED_RESULT
update_refcount(BlockDriverState
*bs
,
423 int64_t offset
, int64_t length
, int addend
)
425 BDRVQcowState
*s
= bs
->opaque
;
426 int64_t start
, last
, cluster_offset
;
427 uint16_t *refcount_block
= NULL
;
428 int64_t old_table_index
= -1;
432 fprintf(stderr
, "update_refcount: offset=%" PRId64
" size=%" PRId64
" addend=%d\n",
433 offset
, length
, addend
);
437 } else if (length
== 0) {
442 qcow2_cache_set_dependency(bs
, s
->refcount_block_cache
,
446 start
= offset
& ~(s
->cluster_size
- 1);
447 last
= (offset
+ length
- 1) & ~(s
->cluster_size
- 1);
448 for(cluster_offset
= start
; cluster_offset
<= last
;
449 cluster_offset
+= s
->cluster_size
)
451 int block_index
, refcount
;
452 int64_t cluster_index
= cluster_offset
>> s
->cluster_bits
;
453 int64_t table_index
=
454 cluster_index
>> (s
->cluster_bits
- REFCOUNT_SHIFT
);
456 /* Load the refcount block and allocate it if needed */
457 if (table_index
!= old_table_index
) {
458 if (refcount_block
) {
459 ret
= qcow2_cache_put(bs
, s
->refcount_block_cache
,
460 (void**) &refcount_block
);
466 ret
= alloc_refcount_block(bs
, cluster_index
, &refcount_block
);
471 old_table_index
= table_index
;
473 qcow2_cache_entry_mark_dirty(s
->refcount_block_cache
, refcount_block
);
475 /* we can update the count and save it */
476 block_index
= cluster_index
&
477 ((1 << (s
->cluster_bits
- REFCOUNT_SHIFT
)) - 1);
479 refcount
= be16_to_cpu(refcount_block
[block_index
]);
481 if (refcount
< 0 || refcount
> 0xffff) {
485 if (refcount
== 0 && cluster_index
< s
->free_cluster_index
) {
486 s
->free_cluster_index
= cluster_index
;
488 refcount_block
[block_index
] = cpu_to_be16(refcount
);
493 /* Write last changed block to disk */
494 if (refcount_block
) {
496 wret
= qcow2_cache_put(bs
, s
->refcount_block_cache
,
497 (void**) &refcount_block
);
499 return ret
< 0 ? ret
: wret
;
504 * Try do undo any updates if an error is returned (This may succeed in
505 * some cases like ENOSPC for allocating a new refcount block)
509 dummy
= update_refcount(bs
, offset
, cluster_offset
- offset
, -addend
);
517 * Increases or decreases the refcount of a given cluster by one.
518 * addend must be 1 or -1.
520 * If the return value is non-negative, it is the new refcount of the cluster.
521 * If it is negative, it is -errno and indicates an error.
523 static int update_cluster_refcount(BlockDriverState
*bs
,
524 int64_t cluster_index
,
527 BDRVQcowState
*s
= bs
->opaque
;
530 ret
= update_refcount(bs
, cluster_index
<< s
->cluster_bits
, 1, addend
);
535 bdrv_flush(bs
->file
);
537 return get_refcount(bs
, cluster_index
);
542 /*********************************************************/
543 /* cluster allocation functions */
547 /* return < 0 if error */
548 static int64_t alloc_clusters_noref(BlockDriverState
*bs
, int64_t size
)
550 BDRVQcowState
*s
= bs
->opaque
;
551 int i
, nb_clusters
, refcount
;
553 nb_clusters
= size_to_clusters(s
, size
);
555 for(i
= 0; i
< nb_clusters
; i
++) {
556 int64_t next_cluster_index
= s
->free_cluster_index
++;
557 refcount
= get_refcount(bs
, next_cluster_index
);
561 } else if (refcount
!= 0) {
566 fprintf(stderr
, "alloc_clusters: size=%" PRId64
" -> %" PRId64
"\n",
568 (s
->free_cluster_index
- nb_clusters
) << s
->cluster_bits
);
570 return (s
->free_cluster_index
- nb_clusters
) << s
->cluster_bits
;
573 int64_t qcow2_alloc_clusters(BlockDriverState
*bs
, int64_t size
)
578 BLKDBG_EVENT(bs
->file
, BLKDBG_CLUSTER_ALLOC
);
579 offset
= alloc_clusters_noref(bs
, size
);
584 ret
= update_refcount(bs
, offset
, size
, 1);
592 int qcow2_alloc_clusters_at(BlockDriverState
*bs
, uint64_t offset
,
595 BDRVQcowState
*s
= bs
->opaque
;
596 uint64_t cluster_index
;
597 uint64_t old_free_cluster_index
;
598 int i
, refcount
, ret
;
600 /* Check how many clusters there are free */
601 cluster_index
= offset
>> s
->cluster_bits
;
602 for(i
= 0; i
< nb_clusters
; i
++) {
603 refcount
= get_refcount(bs
, cluster_index
++);
607 } else if (refcount
!= 0) {
612 /* And then allocate them */
613 old_free_cluster_index
= s
->free_cluster_index
;
614 s
->free_cluster_index
= cluster_index
+ i
;
616 ret
= update_refcount(bs
, offset
, i
<< s
->cluster_bits
, 1);
621 s
->free_cluster_index
= old_free_cluster_index
;
626 /* only used to allocate compressed sectors. We try to allocate
627 contiguous sectors. size must be <= cluster_size */
628 int64_t qcow2_alloc_bytes(BlockDriverState
*bs
, int size
)
630 BDRVQcowState
*s
= bs
->opaque
;
631 int64_t offset
, cluster_offset
;
634 BLKDBG_EVENT(bs
->file
, BLKDBG_CLUSTER_ALLOC_BYTES
);
635 assert(size
> 0 && size
<= s
->cluster_size
);
636 if (s
->free_byte_offset
== 0) {
637 offset
= qcow2_alloc_clusters(bs
, s
->cluster_size
);
641 s
->free_byte_offset
= offset
;
644 free_in_cluster
= s
->cluster_size
-
645 (s
->free_byte_offset
& (s
->cluster_size
- 1));
646 if (size
<= free_in_cluster
) {
647 /* enough space in current cluster */
648 offset
= s
->free_byte_offset
;
649 s
->free_byte_offset
+= size
;
650 free_in_cluster
-= size
;
651 if (free_in_cluster
== 0)
652 s
->free_byte_offset
= 0;
653 if ((offset
& (s
->cluster_size
- 1)) != 0)
654 update_cluster_refcount(bs
, offset
>> s
->cluster_bits
, 1);
656 offset
= qcow2_alloc_clusters(bs
, s
->cluster_size
);
660 cluster_offset
= s
->free_byte_offset
& ~(s
->cluster_size
- 1);
661 if ((cluster_offset
+ s
->cluster_size
) == offset
) {
662 /* we are lucky: contiguous data */
663 offset
= s
->free_byte_offset
;
664 update_cluster_refcount(bs
, offset
>> s
->cluster_bits
, 1);
665 s
->free_byte_offset
+= size
;
667 s
->free_byte_offset
= offset
;
672 /* The cluster refcount was incremented, either by qcow2_alloc_clusters()
673 * or explicitly by update_cluster_refcount(). Refcount blocks must be
674 * flushed before the caller's L2 table updates.
676 qcow2_cache_set_dependency(bs
, s
->l2_table_cache
, s
->refcount_block_cache
);
680 void qcow2_free_clusters(BlockDriverState
*bs
,
681 int64_t offset
, int64_t size
)
685 BLKDBG_EVENT(bs
->file
, BLKDBG_CLUSTER_FREE
);
686 ret
= update_refcount(bs
, offset
, size
, -1);
688 fprintf(stderr
, "qcow2_free_clusters failed: %s\n", strerror(-ret
));
689 /* TODO Remember the clusters to free them later and avoid leaking */
694 * Free a cluster using its L2 entry (handles clusters of all types, e.g.
695 * normal cluster, compressed cluster, etc.)
697 void qcow2_free_any_clusters(BlockDriverState
*bs
,
698 uint64_t l2_entry
, int nb_clusters
)
700 BDRVQcowState
*s
= bs
->opaque
;
702 switch (qcow2_get_cluster_type(l2_entry
)) {
703 case QCOW2_CLUSTER_COMPRESSED
:
706 nb_csectors
= ((l2_entry
>> s
->csize_shift
) &
708 qcow2_free_clusters(bs
,
709 (l2_entry
& s
->cluster_offset_mask
) & ~511,
713 case QCOW2_CLUSTER_NORMAL
:
714 qcow2_free_clusters(bs
, l2_entry
& L2E_OFFSET_MASK
,
715 nb_clusters
<< s
->cluster_bits
);
717 case QCOW2_CLUSTER_UNALLOCATED
:
718 case QCOW2_CLUSTER_ZERO
:
727 /*********************************************************/
728 /* snapshots and image creation */
732 /* update the refcounts of snapshots and the copied flag */
733 int qcow2_update_snapshot_refcount(BlockDriverState
*bs
,
734 int64_t l1_table_offset
, int l1_size
, int addend
)
736 BDRVQcowState
*s
= bs
->opaque
;
737 uint64_t *l1_table
, *l2_table
, l2_offset
, offset
, l1_size2
, l1_allocated
;
738 int64_t old_offset
, old_l2_offset
;
739 int i
, j
, l1_modified
= 0, nb_csectors
, refcount
;
744 l1_size2
= l1_size
* sizeof(uint64_t);
746 /* WARNING: qcow2_snapshot_goto relies on this function not using the
747 * l1_table_offset when it is the current s->l1_table_offset! Be careful
748 * when changing this! */
749 if (l1_table_offset
!= s
->l1_table_offset
) {
750 l1_table
= g_malloc0(align_offset(l1_size2
, 512));
752 if (bdrv_pread(bs
->file
, l1_table_offset
,
753 l1_table
, l1_size2
) != l1_size2
)
759 for(i
= 0;i
< l1_size
; i
++)
760 be64_to_cpus(&l1_table
[i
]);
762 assert(l1_size
== s
->l1_size
);
763 l1_table
= s
->l1_table
;
767 for(i
= 0; i
< l1_size
; i
++) {
768 l2_offset
= l1_table
[i
];
770 old_l2_offset
= l2_offset
;
771 l2_offset
&= L1E_OFFSET_MASK
;
773 ret
= qcow2_cache_get(bs
, s
->l2_table_cache
, l2_offset
,
779 for(j
= 0; j
< s
->l2_size
; j
++) {
780 offset
= be64_to_cpu(l2_table
[j
]);
783 offset
&= ~QCOW_OFLAG_COPIED
;
784 if (offset
& QCOW_OFLAG_COMPRESSED
) {
785 nb_csectors
= ((offset
>> s
->csize_shift
) &
789 ret
= update_refcount(bs
,
790 (offset
& s
->cluster_offset_mask
) & ~511,
791 nb_csectors
* 512, addend
);
796 /* TODO Flushing once for the whole function should
798 bdrv_flush(bs
->file
);
800 /* compressed clusters are never modified */
803 uint64_t cluster_index
= (offset
& L2E_OFFSET_MASK
) >> s
->cluster_bits
;
805 refcount
= update_cluster_refcount(bs
, cluster_index
, addend
);
807 refcount
= get_refcount(bs
, cluster_index
);
817 offset
|= QCOW_OFLAG_COPIED
;
819 if (offset
!= old_offset
) {
821 qcow2_cache_set_dependency(bs
, s
->l2_table_cache
,
822 s
->refcount_block_cache
);
824 l2_table
[j
] = cpu_to_be64(offset
);
825 qcow2_cache_entry_mark_dirty(s
->l2_table_cache
, l2_table
);
830 ret
= qcow2_cache_put(bs
, s
->l2_table_cache
, (void**) &l2_table
);
837 refcount
= update_cluster_refcount(bs
, l2_offset
>> s
->cluster_bits
, addend
);
839 refcount
= get_refcount(bs
, l2_offset
>> s
->cluster_bits
);
844 } else if (refcount
== 1) {
845 l2_offset
|= QCOW_OFLAG_COPIED
;
847 if (l2_offset
!= old_l2_offset
) {
848 l1_table
[i
] = l2_offset
;
857 qcow2_cache_put(bs
, s
->l2_table_cache
, (void**) &l2_table
);
860 /* Update L1 only if it isn't deleted anyway (addend = -1) */
861 if (addend
>= 0 && l1_modified
) {
862 for(i
= 0; i
< l1_size
; i
++)
863 cpu_to_be64s(&l1_table
[i
]);
864 if (bdrv_pwrite_sync(bs
->file
, l1_table_offset
, l1_table
,
867 for(i
= 0; i
< l1_size
; i
++)
868 be64_to_cpus(&l1_table
[i
]);
878 /*********************************************************/
879 /* refcount checking functions */
884 * Increases the refcount for a range of clusters in a given refcount table.
885 * This is used to construct a temporary refcount table out of L1 and L2 tables
886 * which can be compared the the refcount table saved in the image.
888 * Modifies the number of errors in res.
890 static void inc_refcounts(BlockDriverState
*bs
,
891 BdrvCheckResult
*res
,
892 uint16_t *refcount_table
,
893 int refcount_table_size
,
894 int64_t offset
, int64_t size
)
896 BDRVQcowState
*s
= bs
->opaque
;
897 int64_t start
, last
, cluster_offset
;
903 start
= offset
& ~(s
->cluster_size
- 1);
904 last
= (offset
+ size
- 1) & ~(s
->cluster_size
- 1);
905 for(cluster_offset
= start
; cluster_offset
<= last
;
906 cluster_offset
+= s
->cluster_size
) {
907 k
= cluster_offset
>> s
->cluster_bits
;
909 fprintf(stderr
, "ERROR: invalid cluster offset=0x%" PRIx64
"\n",
912 } else if (k
>= refcount_table_size
) {
913 fprintf(stderr
, "Warning: cluster offset=0x%" PRIx64
" is after "
914 "the end of the image file, can't properly check refcounts.\n",
918 if (++refcount_table
[k
] == 0) {
919 fprintf(stderr
, "ERROR: overflow cluster offset=0x%" PRIx64
920 "\n", cluster_offset
);
927 /* Flags for check_refcounts_l1() and check_refcounts_l2() */
929 CHECK_OFLAG_COPIED
= 0x1, /* check QCOW_OFLAG_COPIED matches refcount */
930 CHECK_FRAG_INFO
= 0x2, /* update BlockFragInfo counters */
934 * Increases the refcount in the given refcount table for the all clusters
935 * referenced in the L2 table. While doing so, performs some checks on L2
938 * Returns the number of errors found by the checks or -errno if an internal
941 static int check_refcounts_l2(BlockDriverState
*bs
, BdrvCheckResult
*res
,
942 uint16_t *refcount_table
, int refcount_table_size
, int64_t l2_offset
,
945 BDRVQcowState
*s
= bs
->opaque
;
946 uint64_t *l2_table
, l2_entry
;
947 uint64_t next_contiguous_offset
= 0;
948 int i
, l2_size
, nb_csectors
, refcount
;
950 /* Read L2 table from disk */
951 l2_size
= s
->l2_size
* sizeof(uint64_t);
952 l2_table
= g_malloc(l2_size
);
954 if (bdrv_pread(bs
->file
, l2_offset
, l2_table
, l2_size
) != l2_size
)
957 /* Do the actual checks */
958 for(i
= 0; i
< s
->l2_size
; i
++) {
959 l2_entry
= be64_to_cpu(l2_table
[i
]);
961 switch (qcow2_get_cluster_type(l2_entry
)) {
962 case QCOW2_CLUSTER_COMPRESSED
:
963 /* Compressed clusters don't have QCOW_OFLAG_COPIED */
964 if (l2_entry
& QCOW_OFLAG_COPIED
) {
965 fprintf(stderr
, "ERROR: cluster %" PRId64
": "
966 "copied flag must never be set for compressed "
967 "clusters\n", l2_entry
>> s
->cluster_bits
);
968 l2_entry
&= ~QCOW_OFLAG_COPIED
;
972 /* Mark cluster as used */
973 nb_csectors
= ((l2_entry
>> s
->csize_shift
) &
975 l2_entry
&= s
->cluster_offset_mask
;
976 inc_refcounts(bs
, res
, refcount_table
, refcount_table_size
,
977 l2_entry
& ~511, nb_csectors
* 512);
979 if (flags
& CHECK_FRAG_INFO
) {
980 res
->bfi
.allocated_clusters
++;
981 res
->bfi
.compressed_clusters
++;
983 /* Compressed clusters are fragmented by nature. Since they
984 * take up sub-sector space but we only have sector granularity
985 * I/O we need to re-read the same sectors even for adjacent
986 * compressed clusters.
988 res
->bfi
.fragmented_clusters
++;
992 case QCOW2_CLUSTER_ZERO
:
993 if ((l2_entry
& L2E_OFFSET_MASK
) == 0) {
998 case QCOW2_CLUSTER_NORMAL
:
1000 /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
1001 uint64_t offset
= l2_entry
& L2E_OFFSET_MASK
;
1003 if (flags
& CHECK_OFLAG_COPIED
) {
1004 refcount
= get_refcount(bs
, offset
>> s
->cluster_bits
);
1006 fprintf(stderr
, "Can't get refcount for offset %"
1007 PRIx64
": %s\n", l2_entry
, strerror(-refcount
));
1010 if ((refcount
== 1) != ((l2_entry
& QCOW_OFLAG_COPIED
) != 0)) {
1011 fprintf(stderr
, "ERROR OFLAG_COPIED: offset=%"
1012 PRIx64
" refcount=%d\n", l2_entry
, refcount
);
1017 if (flags
& CHECK_FRAG_INFO
) {
1018 res
->bfi
.allocated_clusters
++;
1019 if (next_contiguous_offset
&&
1020 offset
!= next_contiguous_offset
) {
1021 res
->bfi
.fragmented_clusters
++;
1023 next_contiguous_offset
= offset
+ s
->cluster_size
;
1026 /* Mark cluster as used */
1027 inc_refcounts(bs
, res
, refcount_table
,refcount_table_size
,
1028 offset
, s
->cluster_size
);
1030 /* Correct offsets are cluster aligned */
1031 if (offset
& (s
->cluster_size
- 1)) {
1032 fprintf(stderr
, "ERROR offset=%" PRIx64
": Cluster is not "
1033 "properly aligned; L2 entry corrupted.\n", offset
);
1039 case QCOW2_CLUSTER_UNALLOCATED
:
1051 fprintf(stderr
, "ERROR: I/O error in check_refcounts_l2\n");
1057 * Increases the refcount for the L1 table, its L2 tables and all referenced
1058 * clusters in the given refcount table. While doing so, performs some checks
1059 * on L1 and L2 entries.
1061 * Returns the number of errors found by the checks or -errno if an internal
1064 static int check_refcounts_l1(BlockDriverState
*bs
,
1065 BdrvCheckResult
*res
,
1066 uint16_t *refcount_table
,
1067 int refcount_table_size
,
1068 int64_t l1_table_offset
, int l1_size
,
1071 BDRVQcowState
*s
= bs
->opaque
;
1072 uint64_t *l1_table
, l2_offset
, l1_size2
;
1073 int i
, refcount
, ret
;
1075 l1_size2
= l1_size
* sizeof(uint64_t);
1077 /* Mark L1 table as used */
1078 inc_refcounts(bs
, res
, refcount_table
, refcount_table_size
,
1079 l1_table_offset
, l1_size2
);
1081 /* Read L1 table entries from disk */
1082 if (l1_size2
== 0) {
1085 l1_table
= g_malloc(l1_size2
);
1086 if (bdrv_pread(bs
->file
, l1_table_offset
,
1087 l1_table
, l1_size2
) != l1_size2
)
1089 for(i
= 0;i
< l1_size
; i
++)
1090 be64_to_cpus(&l1_table
[i
]);
1093 /* Do the actual checks */
1094 for(i
= 0; i
< l1_size
; i
++) {
1095 l2_offset
= l1_table
[i
];
1097 /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
1098 if (flags
& CHECK_OFLAG_COPIED
) {
1099 refcount
= get_refcount(bs
, (l2_offset
& ~QCOW_OFLAG_COPIED
)
1100 >> s
->cluster_bits
);
1102 fprintf(stderr
, "Can't get refcount for l2_offset %"
1103 PRIx64
": %s\n", l2_offset
, strerror(-refcount
));
1106 if ((refcount
== 1) != ((l2_offset
& QCOW_OFLAG_COPIED
) != 0)) {
1107 fprintf(stderr
, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
1108 " refcount=%d\n", l2_offset
, refcount
);
1113 /* Mark L2 table as used */
1114 l2_offset
&= L1E_OFFSET_MASK
;
1115 inc_refcounts(bs
, res
, refcount_table
, refcount_table_size
,
1116 l2_offset
, s
->cluster_size
);
1118 /* L2 tables are cluster aligned */
1119 if (l2_offset
& (s
->cluster_size
- 1)) {
1120 fprintf(stderr
, "ERROR l2_offset=%" PRIx64
": Table is not "
1121 "cluster aligned; L1 entry corrupted\n", l2_offset
);
1125 /* Process and check L2 entries */
1126 ret
= check_refcounts_l2(bs
, res
, refcount_table
,
1127 refcount_table_size
, l2_offset
, flags
);
1137 fprintf(stderr
, "ERROR: I/O error in check_refcounts_l1\n");
1138 res
->check_errors
++;
1144 * Checks an image for refcount consistency.
1146 * Returns 0 if no errors are found, the number of errors in case the image is
1147 * detected as corrupted, and -errno when an internal error occurred.
1149 int qcow2_check_refcounts(BlockDriverState
*bs
, BdrvCheckResult
*res
,
1152 BDRVQcowState
*s
= bs
->opaque
;
1153 int64_t size
, i
, highest_cluster
;
1154 int nb_clusters
, refcount1
, refcount2
;
1156 uint16_t *refcount_table
;
1159 size
= bdrv_getlength(bs
->file
);
1160 nb_clusters
= size_to_clusters(s
, size
);
1161 res
->bfi
.total_clusters
= nb_clusters
;
1162 refcount_table
= g_malloc0(nb_clusters
* sizeof(uint16_t));
1165 inc_refcounts(bs
, res
, refcount_table
, nb_clusters
,
1166 0, s
->cluster_size
);
1168 /* current L1 table */
1169 ret
= check_refcounts_l1(bs
, res
, refcount_table
, nb_clusters
,
1170 s
->l1_table_offset
, s
->l1_size
,
1171 CHECK_OFLAG_COPIED
| CHECK_FRAG_INFO
);
1177 for(i
= 0; i
< s
->nb_snapshots
; i
++) {
1178 sn
= s
->snapshots
+ i
;
1179 ret
= check_refcounts_l1(bs
, res
, refcount_table
, nb_clusters
,
1180 sn
->l1_table_offset
, sn
->l1_size
, 0);
1185 inc_refcounts(bs
, res
, refcount_table
, nb_clusters
,
1186 s
->snapshots_offset
, s
->snapshots_size
);
1189 inc_refcounts(bs
, res
, refcount_table
, nb_clusters
,
1190 s
->refcount_table_offset
,
1191 s
->refcount_table_size
* sizeof(uint64_t));
1193 for(i
= 0; i
< s
->refcount_table_size
; i
++) {
1194 uint64_t offset
, cluster
;
1195 offset
= s
->refcount_table
[i
];
1196 cluster
= offset
>> s
->cluster_bits
;
1198 /* Refcount blocks are cluster aligned */
1199 if (offset
& (s
->cluster_size
- 1)) {
1200 fprintf(stderr
, "ERROR refcount block %" PRId64
" is not "
1201 "cluster aligned; refcount table entry corrupted\n", i
);
1206 if (cluster
>= nb_clusters
) {
1207 fprintf(stderr
, "ERROR refcount block %" PRId64
1208 " is outside image\n", i
);
1214 inc_refcounts(bs
, res
, refcount_table
, nb_clusters
,
1215 offset
, s
->cluster_size
);
1216 if (refcount_table
[cluster
] != 1) {
1217 fprintf(stderr
, "ERROR refcount block %" PRId64
1219 i
, refcount_table
[cluster
]);
1225 /* compare ref counts */
1226 for (i
= 0, highest_cluster
= 0; i
< nb_clusters
; i
++) {
1227 refcount1
= get_refcount(bs
, i
);
1228 if (refcount1
< 0) {
1229 fprintf(stderr
, "Can't get refcount for cluster %" PRId64
": %s\n",
1230 i
, strerror(-refcount1
));
1231 res
->check_errors
++;
1235 refcount2
= refcount_table
[i
];
1237 if (refcount1
> 0 || refcount2
> 0) {
1238 highest_cluster
= i
;
1241 if (refcount1
!= refcount2
) {
1243 /* Check if we're allowed to fix the mismatch */
1244 int *num_fixed
= NULL
;
1245 if (refcount1
> refcount2
&& (fix
& BDRV_FIX_LEAKS
)) {
1246 num_fixed
= &res
->leaks_fixed
;
1247 } else if (refcount1
< refcount2
&& (fix
& BDRV_FIX_ERRORS
)) {
1248 num_fixed
= &res
->corruptions_fixed
;
1251 fprintf(stderr
, "%s cluster %" PRId64
" refcount=%d reference=%d\n",
1252 num_fixed
!= NULL
? "Repairing" :
1253 refcount1
< refcount2
? "ERROR" :
1255 i
, refcount1
, refcount2
);
1258 ret
= update_refcount(bs
, i
<< s
->cluster_bits
, 1,
1259 refcount2
- refcount1
);
1266 /* And if we couldn't, print an error */
1267 if (refcount1
< refcount2
) {
1275 res
->image_end_offset
= (highest_cluster
+ 1) * s
->cluster_size
;
1279 g_free(refcount_table
);