qcow2: Check refcount table size (CVE-2014-0144)
[qemu.git] / block / qcow2-refcount.c
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/block_int.h"
27 #include "block/qcow2.h"
28 #include "qemu/range.h"
29 #include "qapi/qmp/types.h"
30
31 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size);
32 static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
33 int64_t offset, int64_t length,
34 int addend, enum qcow2_discard_type type);
35
36
37 /*********************************************************/
38 /* refcount handling */
39
40 int qcow2_refcount_init(BlockDriverState *bs)
41 {
42 BDRVQcowState *s = bs->opaque;
43 unsigned int refcount_table_size2, i;
44 int ret;
45
46 assert(s->refcount_table_size <= INT_MAX / sizeof(uint64_t));
47 refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
48 s->refcount_table = g_malloc(refcount_table_size2);
49 if (s->refcount_table_size > 0) {
50 BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_LOAD);
51 ret = bdrv_pread(bs->file, s->refcount_table_offset,
52 s->refcount_table, refcount_table_size2);
53 if (ret != refcount_table_size2)
54 goto fail;
55 for(i = 0; i < s->refcount_table_size; i++)
56 be64_to_cpus(&s->refcount_table[i]);
57 }
58 return 0;
59 fail:
60 return -ENOMEM;
61 }
62
63 void qcow2_refcount_close(BlockDriverState *bs)
64 {
65 BDRVQcowState *s = bs->opaque;
66 g_free(s->refcount_table);
67 }
68
69
70 static int load_refcount_block(BlockDriverState *bs,
71 int64_t refcount_block_offset,
72 void **refcount_block)
73 {
74 BDRVQcowState *s = bs->opaque;
75 int ret;
76
77 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_LOAD);
78 ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset,
79 refcount_block);
80
81 return ret;
82 }
83
84 /*
85 * Returns the refcount of the cluster given by its index. Any non-negative
86 * return value is the refcount of the cluster, negative values are -errno
87 * and indicate an error.
88 */
89 static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
90 {
91 BDRVQcowState *s = bs->opaque;
92 int refcount_table_index, block_index;
93 int64_t refcount_block_offset;
94 int ret;
95 uint16_t *refcount_block;
96 uint16_t refcount;
97
98 refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
99 if (refcount_table_index >= s->refcount_table_size)
100 return 0;
101 refcount_block_offset =
102 s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK;
103 if (!refcount_block_offset)
104 return 0;
105
106 ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset,
107 (void**) &refcount_block);
108 if (ret < 0) {
109 return ret;
110 }
111
112 block_index = cluster_index &
113 ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
114 refcount = be16_to_cpu(refcount_block[block_index]);
115
116 ret = qcow2_cache_put(bs, s->refcount_block_cache,
117 (void**) &refcount_block);
118 if (ret < 0) {
119 return ret;
120 }
121
122 return refcount;
123 }
124
125 /*
126 * Rounds the refcount table size up to avoid growing the table for each single
127 * refcount block that is allocated.
128 */
129 static unsigned int next_refcount_table_size(BDRVQcowState *s,
130 unsigned int min_size)
131 {
132 unsigned int min_clusters = (min_size >> (s->cluster_bits - 3)) + 1;
133 unsigned int refcount_table_clusters =
134 MAX(1, s->refcount_table_size >> (s->cluster_bits - 3));
135
136 while (min_clusters > refcount_table_clusters) {
137 refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
138 }
139
140 return refcount_table_clusters << (s->cluster_bits - 3);
141 }
142
143
144 /* Checks if two offsets are described by the same refcount block */
145 static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a,
146 uint64_t offset_b)
147 {
148 uint64_t block_a = offset_a >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
149 uint64_t block_b = offset_b >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
150
151 return (block_a == block_b);
152 }
153
154 /*
155 * Loads a refcount block. If it doesn't exist yet, it is allocated first
156 * (including growing the refcount table if needed).
157 *
158 * Returns 0 on success or -errno in error case
159 */
160 static int alloc_refcount_block(BlockDriverState *bs,
161 int64_t cluster_index, uint16_t **refcount_block)
162 {
163 BDRVQcowState *s = bs->opaque;
164 unsigned int refcount_table_index;
165 int ret;
166
167 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC);
168
169 /* Find the refcount block for the given cluster */
170 refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
171
172 if (refcount_table_index < s->refcount_table_size) {
173
174 uint64_t refcount_block_offset =
175 s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK;
176
177 /* If it's already there, we're done */
178 if (refcount_block_offset) {
179 return load_refcount_block(bs, refcount_block_offset,
180 (void**) refcount_block);
181 }
182 }
183
184 /*
185 * If we came here, we need to allocate something. Something is at least
186 * a cluster for the new refcount block. It may also include a new refcount
187 * table if the old refcount table is too small.
188 *
189 * Note that allocating clusters here needs some special care:
190 *
191 * - We can't use the normal qcow2_alloc_clusters(), it would try to
192 * increase the refcount and very likely we would end up with an endless
193 * recursion. Instead we must place the refcount blocks in a way that
194 * they can describe them themselves.
195 *
196 * - We need to consider that at this point we are inside update_refcounts
197 * and doing the initial refcount increase. This means that some clusters
198 * have already been allocated by the caller, but their refcount isn't
199 * accurate yet. free_cluster_index tells us where this allocation ends
200 * as long as we don't overwrite it by freeing clusters.
201 *
202 * - alloc_clusters_noref and qcow2_free_clusters may load a different
203 * refcount block into the cache
204 */
205
206 *refcount_block = NULL;
207
208 /* We write to the refcount table, so we might depend on L2 tables */
209 ret = qcow2_cache_flush(bs, s->l2_table_cache);
210 if (ret < 0) {
211 return ret;
212 }
213
214 /* Allocate the refcount block itself and mark it as used */
215 int64_t new_block = alloc_clusters_noref(bs, s->cluster_size);
216 if (new_block < 0) {
217 return new_block;
218 }
219
220 #ifdef DEBUG_ALLOC2
221 fprintf(stderr, "qcow2: Allocate refcount block %d for %" PRIx64
222 " at %" PRIx64 "\n",
223 refcount_table_index, cluster_index << s->cluster_bits, new_block);
224 #endif
225
226 if (in_same_refcount_block(s, new_block, cluster_index << s->cluster_bits)) {
227 /* Zero the new refcount block before updating it */
228 ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block,
229 (void**) refcount_block);
230 if (ret < 0) {
231 goto fail_block;
232 }
233
234 memset(*refcount_block, 0, s->cluster_size);
235
236 /* The block describes itself, need to update the cache */
237 int block_index = (new_block >> s->cluster_bits) &
238 ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
239 (*refcount_block)[block_index] = cpu_to_be16(1);
240 } else {
241 /* Described somewhere else. This can recurse at most twice before we
242 * arrive at a block that describes itself. */
243 ret = update_refcount(bs, new_block, s->cluster_size, 1,
244 QCOW2_DISCARD_NEVER);
245 if (ret < 0) {
246 goto fail_block;
247 }
248
249 ret = qcow2_cache_flush(bs, s->refcount_block_cache);
250 if (ret < 0) {
251 goto fail_block;
252 }
253
254 /* Initialize the new refcount block only after updating its refcount,
255 * update_refcount uses the refcount cache itself */
256 ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block,
257 (void**) refcount_block);
258 if (ret < 0) {
259 goto fail_block;
260 }
261
262 memset(*refcount_block, 0, s->cluster_size);
263 }
264
265 /* Now the new refcount block needs to be written to disk */
266 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE);
267 qcow2_cache_entry_mark_dirty(s->refcount_block_cache, *refcount_block);
268 ret = qcow2_cache_flush(bs, s->refcount_block_cache);
269 if (ret < 0) {
270 goto fail_block;
271 }
272
273 /* If the refcount table is big enough, just hook the block up there */
274 if (refcount_table_index < s->refcount_table_size) {
275 uint64_t data64 = cpu_to_be64(new_block);
276 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_HOOKUP);
277 ret = bdrv_pwrite_sync(bs->file,
278 s->refcount_table_offset + refcount_table_index * sizeof(uint64_t),
279 &data64, sizeof(data64));
280 if (ret < 0) {
281 goto fail_block;
282 }
283
284 s->refcount_table[refcount_table_index] = new_block;
285 return 0;
286 }
287
288 ret = qcow2_cache_put(bs, s->refcount_block_cache, (void**) refcount_block);
289 if (ret < 0) {
290 goto fail_block;
291 }
292
293 /*
294 * If we come here, we need to grow the refcount table. Again, a new
295 * refcount table needs some space and we can't simply allocate to avoid
296 * endless recursion.
297 *
298 * Therefore let's grab new refcount blocks at the end of the image, which
299 * will describe themselves and the new refcount table. This way we can
300 * reference them only in the new table and do the switch to the new
301 * refcount table at once without producing an inconsistent state in
302 * between.
303 */
304 BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW);
305
306 /* Calculate the number of refcount blocks needed so far */
307 uint64_t refcount_block_clusters = 1 << (s->cluster_bits - REFCOUNT_SHIFT);
308 uint64_t blocks_used = (s->free_cluster_index +
309 refcount_block_clusters - 1) / refcount_block_clusters;
310
311 /* And now we need at least one block more for the new metadata */
312 uint64_t table_size = next_refcount_table_size(s, blocks_used + 1);
313 uint64_t last_table_size;
314 uint64_t blocks_clusters;
315 do {
316 uint64_t table_clusters =
317 size_to_clusters(s, table_size * sizeof(uint64_t));
318 blocks_clusters = 1 +
319 ((table_clusters + refcount_block_clusters - 1)
320 / refcount_block_clusters);
321 uint64_t meta_clusters = table_clusters + blocks_clusters;
322
323 last_table_size = table_size;
324 table_size = next_refcount_table_size(s, blocks_used +
325 ((meta_clusters + refcount_block_clusters - 1)
326 / refcount_block_clusters));
327
328 } while (last_table_size != table_size);
329
330 #ifdef DEBUG_ALLOC2
331 fprintf(stderr, "qcow2: Grow refcount table %" PRId32 " => %" PRId64 "\n",
332 s->refcount_table_size, table_size);
333 #endif
334
335 /* Create the new refcount table and blocks */
336 uint64_t meta_offset = (blocks_used * refcount_block_clusters) *
337 s->cluster_size;
338 uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
339 uint16_t *new_blocks = g_malloc0(blocks_clusters * s->cluster_size);
340 uint64_t *new_table = g_malloc0(table_size * sizeof(uint64_t));
341
342 assert(meta_offset >= (s->free_cluster_index * s->cluster_size));
343
344 /* Fill the new refcount table */
345 memcpy(new_table, s->refcount_table,
346 s->refcount_table_size * sizeof(uint64_t));
347 new_table[refcount_table_index] = new_block;
348
349 int i;
350 for (i = 0; i < blocks_clusters; i++) {
351 new_table[blocks_used + i] = meta_offset + (i * s->cluster_size);
352 }
353
354 /* Fill the refcount blocks */
355 uint64_t table_clusters = size_to_clusters(s, table_size * sizeof(uint64_t));
356 int block = 0;
357 for (i = 0; i < table_clusters + blocks_clusters; i++) {
358 new_blocks[block++] = cpu_to_be16(1);
359 }
360
361 /* Write refcount blocks to disk */
362 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_BLOCKS);
363 ret = bdrv_pwrite_sync(bs->file, meta_offset, new_blocks,
364 blocks_clusters * s->cluster_size);
365 g_free(new_blocks);
366 if (ret < 0) {
367 goto fail_table;
368 }
369
370 /* Write refcount table to disk */
371 for(i = 0; i < table_size; i++) {
372 cpu_to_be64s(&new_table[i]);
373 }
374
375 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_TABLE);
376 ret = bdrv_pwrite_sync(bs->file, table_offset, new_table,
377 table_size * sizeof(uint64_t));
378 if (ret < 0) {
379 goto fail_table;
380 }
381
382 for(i = 0; i < table_size; i++) {
383 be64_to_cpus(&new_table[i]);
384 }
385
386 /* Hook up the new refcount table in the qcow2 header */
387 uint8_t data[12];
388 cpu_to_be64w((uint64_t*)data, table_offset);
389 cpu_to_be32w((uint32_t*)(data + 8), table_clusters);
390 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_SWITCH_TABLE);
391 ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, refcount_table_offset),
392 data, sizeof(data));
393 if (ret < 0) {
394 goto fail_table;
395 }
396
397 /* And switch it in memory */
398 uint64_t old_table_offset = s->refcount_table_offset;
399 uint64_t old_table_size = s->refcount_table_size;
400
401 g_free(s->refcount_table);
402 s->refcount_table = new_table;
403 s->refcount_table_size = table_size;
404 s->refcount_table_offset = table_offset;
405
406 /* Free old table. Remember, we must not change free_cluster_index */
407 uint64_t old_free_cluster_index = s->free_cluster_index;
408 qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t),
409 QCOW2_DISCARD_OTHER);
410 s->free_cluster_index = old_free_cluster_index;
411
412 ret = load_refcount_block(bs, new_block, (void**) refcount_block);
413 if (ret < 0) {
414 return ret;
415 }
416
417 return 0;
418
419 fail_table:
420 g_free(new_table);
421 fail_block:
422 if (*refcount_block != NULL) {
423 qcow2_cache_put(bs, s->refcount_block_cache, (void**) refcount_block);
424 }
425 return ret;
426 }
427
428 void qcow2_process_discards(BlockDriverState *bs, int ret)
429 {
430 BDRVQcowState *s = bs->opaque;
431 Qcow2DiscardRegion *d, *next;
432
433 QTAILQ_FOREACH_SAFE(d, &s->discards, next, next) {
434 QTAILQ_REMOVE(&s->discards, d, next);
435
436 /* Discard is optional, ignore the return value */
437 if (ret >= 0) {
438 bdrv_discard(bs->file,
439 d->offset >> BDRV_SECTOR_BITS,
440 d->bytes >> BDRV_SECTOR_BITS);
441 }
442
443 g_free(d);
444 }
445 }
446
447 static void update_refcount_discard(BlockDriverState *bs,
448 uint64_t offset, uint64_t length)
449 {
450 BDRVQcowState *s = bs->opaque;
451 Qcow2DiscardRegion *d, *p, *next;
452
453 QTAILQ_FOREACH(d, &s->discards, next) {
454 uint64_t new_start = MIN(offset, d->offset);
455 uint64_t new_end = MAX(offset + length, d->offset + d->bytes);
456
457 if (new_end - new_start <= length + d->bytes) {
458 /* There can't be any overlap, areas ending up here have no
459 * references any more and therefore shouldn't get freed another
460 * time. */
461 assert(d->bytes + length == new_end - new_start);
462 d->offset = new_start;
463 d->bytes = new_end - new_start;
464 goto found;
465 }
466 }
467
468 d = g_malloc(sizeof(*d));
469 *d = (Qcow2DiscardRegion) {
470 .bs = bs,
471 .offset = offset,
472 .bytes = length,
473 };
474 QTAILQ_INSERT_TAIL(&s->discards, d, next);
475
476 found:
477 /* Merge discard requests if they are adjacent now */
478 QTAILQ_FOREACH_SAFE(p, &s->discards, next, next) {
479 if (p == d
480 || p->offset > d->offset + d->bytes
481 || d->offset > p->offset + p->bytes)
482 {
483 continue;
484 }
485
486 /* Still no overlap possible */
487 assert(p->offset == d->offset + d->bytes
488 || d->offset == p->offset + p->bytes);
489
490 QTAILQ_REMOVE(&s->discards, p, next);
491 d->offset = MIN(d->offset, p->offset);
492 d->bytes += p->bytes;
493 }
494 }
495
496 /* XXX: cache several refcount block clusters ? */
497 static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
498 int64_t offset, int64_t length, int addend, enum qcow2_discard_type type)
499 {
500 BDRVQcowState *s = bs->opaque;
501 int64_t start, last, cluster_offset;
502 uint16_t *refcount_block = NULL;
503 int64_t old_table_index = -1;
504 int ret;
505
506 #ifdef DEBUG_ALLOC2
507 fprintf(stderr, "update_refcount: offset=%" PRId64 " size=%" PRId64 " addend=%d\n",
508 offset, length, addend);
509 #endif
510 if (length < 0) {
511 return -EINVAL;
512 } else if (length == 0) {
513 return 0;
514 }
515
516 if (addend < 0) {
517 qcow2_cache_set_dependency(bs, s->refcount_block_cache,
518 s->l2_table_cache);
519 }
520
521 start = start_of_cluster(s, offset);
522 last = start_of_cluster(s, offset + length - 1);
523 for(cluster_offset = start; cluster_offset <= last;
524 cluster_offset += s->cluster_size)
525 {
526 int block_index, refcount;
527 int64_t cluster_index = cluster_offset >> s->cluster_bits;
528 int64_t table_index =
529 cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
530
531 /* Load the refcount block and allocate it if needed */
532 if (table_index != old_table_index) {
533 if (refcount_block) {
534 ret = qcow2_cache_put(bs, s->refcount_block_cache,
535 (void**) &refcount_block);
536 if (ret < 0) {
537 goto fail;
538 }
539 }
540
541 ret = alloc_refcount_block(bs, cluster_index, &refcount_block);
542 if (ret < 0) {
543 goto fail;
544 }
545 }
546 old_table_index = table_index;
547
548 qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block);
549
550 /* we can update the count and save it */
551 block_index = cluster_index &
552 ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
553
554 refcount = be16_to_cpu(refcount_block[block_index]);
555 refcount += addend;
556 if (refcount < 0 || refcount > 0xffff) {
557 ret = -EINVAL;
558 goto fail;
559 }
560 if (refcount == 0 && cluster_index < s->free_cluster_index) {
561 s->free_cluster_index = cluster_index;
562 }
563 refcount_block[block_index] = cpu_to_be16(refcount);
564
565 if (refcount == 0 && s->discard_passthrough[type]) {
566 update_refcount_discard(bs, cluster_offset, s->cluster_size);
567 }
568 }
569
570 ret = 0;
571 fail:
572 if (!s->cache_discards) {
573 qcow2_process_discards(bs, ret);
574 }
575
576 /* Write last changed block to disk */
577 if (refcount_block) {
578 int wret;
579 wret = qcow2_cache_put(bs, s->refcount_block_cache,
580 (void**) &refcount_block);
581 if (wret < 0) {
582 return ret < 0 ? ret : wret;
583 }
584 }
585
586 /*
587 * Try do undo any updates if an error is returned (This may succeed in
588 * some cases like ENOSPC for allocating a new refcount block)
589 */
590 if (ret < 0) {
591 int dummy;
592 dummy = update_refcount(bs, offset, cluster_offset - offset, -addend,
593 QCOW2_DISCARD_NEVER);
594 (void)dummy;
595 }
596
597 return ret;
598 }
599
600 /*
601 * Increases or decreases the refcount of a given cluster by one.
602 * addend must be 1 or -1.
603 *
604 * If the return value is non-negative, it is the new refcount of the cluster.
605 * If it is negative, it is -errno and indicates an error.
606 */
607 int qcow2_update_cluster_refcount(BlockDriverState *bs,
608 int64_t cluster_index,
609 int addend,
610 enum qcow2_discard_type type)
611 {
612 BDRVQcowState *s = bs->opaque;
613 int ret;
614
615 ret = update_refcount(bs, cluster_index << s->cluster_bits, 1, addend,
616 type);
617 if (ret < 0) {
618 return ret;
619 }
620
621 return get_refcount(bs, cluster_index);
622 }
623
624
625
626 /*********************************************************/
627 /* cluster allocation functions */
628
629
630
631 /* return < 0 if error */
632 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
633 {
634 BDRVQcowState *s = bs->opaque;
635 int i, nb_clusters, refcount;
636
637 nb_clusters = size_to_clusters(s, size);
638 retry:
639 for(i = 0; i < nb_clusters; i++) {
640 int64_t next_cluster_index = s->free_cluster_index++;
641 refcount = get_refcount(bs, next_cluster_index);
642
643 if (refcount < 0) {
644 return refcount;
645 } else if (refcount != 0) {
646 goto retry;
647 }
648 }
649 #ifdef DEBUG_ALLOC2
650 fprintf(stderr, "alloc_clusters: size=%" PRId64 " -> %" PRId64 "\n",
651 size,
652 (s->free_cluster_index - nb_clusters) << s->cluster_bits);
653 #endif
654 return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
655 }
656
657 int64_t qcow2_alloc_clusters(BlockDriverState *bs, int64_t size)
658 {
659 int64_t offset;
660 int ret;
661
662 BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC);
663 offset = alloc_clusters_noref(bs, size);
664 if (offset < 0) {
665 return offset;
666 }
667
668 ret = update_refcount(bs, offset, size, 1, QCOW2_DISCARD_NEVER);
669 if (ret < 0) {
670 return ret;
671 }
672
673 return offset;
674 }
675
676 int qcow2_alloc_clusters_at(BlockDriverState *bs, uint64_t offset,
677 int nb_clusters)
678 {
679 BDRVQcowState *s = bs->opaque;
680 uint64_t cluster_index;
681 uint64_t old_free_cluster_index;
682 uint64_t i;
683 int refcount, ret;
684
685 assert(nb_clusters >= 0);
686 if (nb_clusters == 0) {
687 return 0;
688 }
689
690 /* Check how many clusters there are free */
691 cluster_index = offset >> s->cluster_bits;
692 for(i = 0; i < nb_clusters; i++) {
693 refcount = get_refcount(bs, cluster_index++);
694
695 if (refcount < 0) {
696 return refcount;
697 } else if (refcount != 0) {
698 break;
699 }
700 }
701
702 /* And then allocate them */
703 old_free_cluster_index = s->free_cluster_index;
704 s->free_cluster_index = cluster_index + i;
705
706 ret = update_refcount(bs, offset, i << s->cluster_bits, 1,
707 QCOW2_DISCARD_NEVER);
708 if (ret < 0) {
709 return ret;
710 }
711
712 s->free_cluster_index = old_free_cluster_index;
713
714 return i;
715 }
716
717 /* only used to allocate compressed sectors. We try to allocate
718 contiguous sectors. size must be <= cluster_size */
719 int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
720 {
721 BDRVQcowState *s = bs->opaque;
722 int64_t offset, cluster_offset;
723 int free_in_cluster;
724
725 BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC_BYTES);
726 assert(size > 0 && size <= s->cluster_size);
727 if (s->free_byte_offset == 0) {
728 offset = qcow2_alloc_clusters(bs, s->cluster_size);
729 if (offset < 0) {
730 return offset;
731 }
732 s->free_byte_offset = offset;
733 }
734 redo:
735 free_in_cluster = s->cluster_size -
736 offset_into_cluster(s, s->free_byte_offset);
737 if (size <= free_in_cluster) {
738 /* enough space in current cluster */
739 offset = s->free_byte_offset;
740 s->free_byte_offset += size;
741 free_in_cluster -= size;
742 if (free_in_cluster == 0)
743 s->free_byte_offset = 0;
744 if (offset_into_cluster(s, offset) != 0)
745 qcow2_update_cluster_refcount(bs, offset >> s->cluster_bits, 1,
746 QCOW2_DISCARD_NEVER);
747 } else {
748 offset = qcow2_alloc_clusters(bs, s->cluster_size);
749 if (offset < 0) {
750 return offset;
751 }
752 cluster_offset = start_of_cluster(s, s->free_byte_offset);
753 if ((cluster_offset + s->cluster_size) == offset) {
754 /* we are lucky: contiguous data */
755 offset = s->free_byte_offset;
756 qcow2_update_cluster_refcount(bs, offset >> s->cluster_bits, 1,
757 QCOW2_DISCARD_NEVER);
758 s->free_byte_offset += size;
759 } else {
760 s->free_byte_offset = offset;
761 goto redo;
762 }
763 }
764
765 /* The cluster refcount was incremented, either by qcow2_alloc_clusters()
766 * or explicitly by qcow2_update_cluster_refcount(). Refcount blocks must
767 * be flushed before the caller's L2 table updates.
768 */
769 qcow2_cache_set_dependency(bs, s->l2_table_cache, s->refcount_block_cache);
770 return offset;
771 }
772
773 void qcow2_free_clusters(BlockDriverState *bs,
774 int64_t offset, int64_t size,
775 enum qcow2_discard_type type)
776 {
777 int ret;
778
779 BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE);
780 ret = update_refcount(bs, offset, size, -1, type);
781 if (ret < 0) {
782 fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
783 /* TODO Remember the clusters to free them later and avoid leaking */
784 }
785 }
786
787 /*
788 * Free a cluster using its L2 entry (handles clusters of all types, e.g.
789 * normal cluster, compressed cluster, etc.)
790 */
791 void qcow2_free_any_clusters(BlockDriverState *bs, uint64_t l2_entry,
792 int nb_clusters, enum qcow2_discard_type type)
793 {
794 BDRVQcowState *s = bs->opaque;
795
796 switch (qcow2_get_cluster_type(l2_entry)) {
797 case QCOW2_CLUSTER_COMPRESSED:
798 {
799 int nb_csectors;
800 nb_csectors = ((l2_entry >> s->csize_shift) &
801 s->csize_mask) + 1;
802 qcow2_free_clusters(bs,
803 (l2_entry & s->cluster_offset_mask) & ~511,
804 nb_csectors * 512, type);
805 }
806 break;
807 case QCOW2_CLUSTER_NORMAL:
808 case QCOW2_CLUSTER_ZERO:
809 if (l2_entry & L2E_OFFSET_MASK) {
810 qcow2_free_clusters(bs, l2_entry & L2E_OFFSET_MASK,
811 nb_clusters << s->cluster_bits, type);
812 }
813 break;
814 case QCOW2_CLUSTER_UNALLOCATED:
815 break;
816 default:
817 abort();
818 }
819 }
820
821
822
823 /*********************************************************/
824 /* snapshots and image creation */
825
826
827
828 /* update the refcounts of snapshots and the copied flag */
829 int qcow2_update_snapshot_refcount(BlockDriverState *bs,
830 int64_t l1_table_offset, int l1_size, int addend)
831 {
832 BDRVQcowState *s = bs->opaque;
833 uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
834 int64_t old_offset, old_l2_offset;
835 int i, j, l1_modified = 0, nb_csectors, refcount;
836 int ret;
837
838 l2_table = NULL;
839 l1_table = NULL;
840 l1_size2 = l1_size * sizeof(uint64_t);
841
842 s->cache_discards = true;
843
844 /* WARNING: qcow2_snapshot_goto relies on this function not using the
845 * l1_table_offset when it is the current s->l1_table_offset! Be careful
846 * when changing this! */
847 if (l1_table_offset != s->l1_table_offset) {
848 l1_table = g_malloc0(align_offset(l1_size2, 512));
849 l1_allocated = 1;
850
851 ret = bdrv_pread(bs->file, l1_table_offset, l1_table, l1_size2);
852 if (ret < 0) {
853 goto fail;
854 }
855
856 for(i = 0;i < l1_size; i++)
857 be64_to_cpus(&l1_table[i]);
858 } else {
859 assert(l1_size == s->l1_size);
860 l1_table = s->l1_table;
861 l1_allocated = 0;
862 }
863
864 for(i = 0; i < l1_size; i++) {
865 l2_offset = l1_table[i];
866 if (l2_offset) {
867 old_l2_offset = l2_offset;
868 l2_offset &= L1E_OFFSET_MASK;
869
870 ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset,
871 (void**) &l2_table);
872 if (ret < 0) {
873 goto fail;
874 }
875
876 for(j = 0; j < s->l2_size; j++) {
877 uint64_t cluster_index;
878
879 offset = be64_to_cpu(l2_table[j]);
880 old_offset = offset;
881 offset &= ~QCOW_OFLAG_COPIED;
882
883 switch (qcow2_get_cluster_type(offset)) {
884 case QCOW2_CLUSTER_COMPRESSED:
885 nb_csectors = ((offset >> s->csize_shift) &
886 s->csize_mask) + 1;
887 if (addend != 0) {
888 ret = update_refcount(bs,
889 (offset & s->cluster_offset_mask) & ~511,
890 nb_csectors * 512, addend,
891 QCOW2_DISCARD_SNAPSHOT);
892 if (ret < 0) {
893 goto fail;
894 }
895 }
896 /* compressed clusters are never modified */
897 refcount = 2;
898 break;
899
900 case QCOW2_CLUSTER_NORMAL:
901 case QCOW2_CLUSTER_ZERO:
902 cluster_index = (offset & L2E_OFFSET_MASK) >> s->cluster_bits;
903 if (!cluster_index) {
904 /* unallocated */
905 refcount = 0;
906 break;
907 }
908 if (addend != 0) {
909 refcount = qcow2_update_cluster_refcount(bs,
910 cluster_index, addend,
911 QCOW2_DISCARD_SNAPSHOT);
912 } else {
913 refcount = get_refcount(bs, cluster_index);
914 }
915
916 if (refcount < 0) {
917 ret = refcount;
918 goto fail;
919 }
920 break;
921
922 case QCOW2_CLUSTER_UNALLOCATED:
923 refcount = 0;
924 break;
925
926 default:
927 abort();
928 }
929
930 if (refcount == 1) {
931 offset |= QCOW_OFLAG_COPIED;
932 }
933 if (offset != old_offset) {
934 if (addend > 0) {
935 qcow2_cache_set_dependency(bs, s->l2_table_cache,
936 s->refcount_block_cache);
937 }
938 l2_table[j] = cpu_to_be64(offset);
939 qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
940 }
941 }
942
943 ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
944 if (ret < 0) {
945 goto fail;
946 }
947
948
949 if (addend != 0) {
950 refcount = qcow2_update_cluster_refcount(bs, l2_offset >>
951 s->cluster_bits, addend, QCOW2_DISCARD_SNAPSHOT);
952 } else {
953 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
954 }
955 if (refcount < 0) {
956 ret = refcount;
957 goto fail;
958 } else if (refcount == 1) {
959 l2_offset |= QCOW_OFLAG_COPIED;
960 }
961 if (l2_offset != old_l2_offset) {
962 l1_table[i] = l2_offset;
963 l1_modified = 1;
964 }
965 }
966 }
967
968 ret = bdrv_flush(bs);
969 fail:
970 if (l2_table) {
971 qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
972 }
973
974 s->cache_discards = false;
975 qcow2_process_discards(bs, ret);
976
977 /* Update L1 only if it isn't deleted anyway (addend = -1) */
978 if (ret == 0 && addend >= 0 && l1_modified) {
979 for (i = 0; i < l1_size; i++) {
980 cpu_to_be64s(&l1_table[i]);
981 }
982
983 ret = bdrv_pwrite_sync(bs->file, l1_table_offset, l1_table, l1_size2);
984
985 for (i = 0; i < l1_size; i++) {
986 be64_to_cpus(&l1_table[i]);
987 }
988 }
989 if (l1_allocated)
990 g_free(l1_table);
991 return ret;
992 }
993
994
995
996
997 /*********************************************************/
998 /* refcount checking functions */
999
1000
1001
1002 /*
1003 * Increases the refcount for a range of clusters in a given refcount table.
1004 * This is used to construct a temporary refcount table out of L1 and L2 tables
1005 * which can be compared the the refcount table saved in the image.
1006 *
1007 * Modifies the number of errors in res.
1008 */
1009 static void inc_refcounts(BlockDriverState *bs,
1010 BdrvCheckResult *res,
1011 uint16_t *refcount_table,
1012 int refcount_table_size,
1013 int64_t offset, int64_t size)
1014 {
1015 BDRVQcowState *s = bs->opaque;
1016 int64_t start, last, cluster_offset;
1017 int k;
1018
1019 if (size <= 0)
1020 return;
1021
1022 start = start_of_cluster(s, offset);
1023 last = start_of_cluster(s, offset + size - 1);
1024 for(cluster_offset = start; cluster_offset <= last;
1025 cluster_offset += s->cluster_size) {
1026 k = cluster_offset >> s->cluster_bits;
1027 if (k < 0) {
1028 fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
1029 cluster_offset);
1030 res->corruptions++;
1031 } else if (k >= refcount_table_size) {
1032 fprintf(stderr, "Warning: cluster offset=0x%" PRIx64 " is after "
1033 "the end of the image file, can't properly check refcounts.\n",
1034 cluster_offset);
1035 res->check_errors++;
1036 } else {
1037 if (++refcount_table[k] == 0) {
1038 fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
1039 "\n", cluster_offset);
1040 res->corruptions++;
1041 }
1042 }
1043 }
1044 }
1045
1046 /* Flags for check_refcounts_l1() and check_refcounts_l2() */
1047 enum {
1048 CHECK_FRAG_INFO = 0x2, /* update BlockFragInfo counters */
1049 };
1050
1051 /*
1052 * Increases the refcount in the given refcount table for the all clusters
1053 * referenced in the L2 table. While doing so, performs some checks on L2
1054 * entries.
1055 *
1056 * Returns the number of errors found by the checks or -errno if an internal
1057 * error occurred.
1058 */
1059 static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res,
1060 uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
1061 int flags)
1062 {
1063 BDRVQcowState *s = bs->opaque;
1064 uint64_t *l2_table, l2_entry;
1065 uint64_t next_contiguous_offset = 0;
1066 int i, l2_size, nb_csectors;
1067
1068 /* Read L2 table from disk */
1069 l2_size = s->l2_size * sizeof(uint64_t);
1070 l2_table = g_malloc(l2_size);
1071
1072 if (bdrv_pread(bs->file, l2_offset, l2_table, l2_size) != l2_size)
1073 goto fail;
1074
1075 /* Do the actual checks */
1076 for(i = 0; i < s->l2_size; i++) {
1077 l2_entry = be64_to_cpu(l2_table[i]);
1078
1079 switch (qcow2_get_cluster_type(l2_entry)) {
1080 case QCOW2_CLUSTER_COMPRESSED:
1081 /* Compressed clusters don't have QCOW_OFLAG_COPIED */
1082 if (l2_entry & QCOW_OFLAG_COPIED) {
1083 fprintf(stderr, "ERROR: cluster %" PRId64 ": "
1084 "copied flag must never be set for compressed "
1085 "clusters\n", l2_entry >> s->cluster_bits);
1086 l2_entry &= ~QCOW_OFLAG_COPIED;
1087 res->corruptions++;
1088 }
1089
1090 /* Mark cluster as used */
1091 nb_csectors = ((l2_entry >> s->csize_shift) &
1092 s->csize_mask) + 1;
1093 l2_entry &= s->cluster_offset_mask;
1094 inc_refcounts(bs, res, refcount_table, refcount_table_size,
1095 l2_entry & ~511, nb_csectors * 512);
1096
1097 if (flags & CHECK_FRAG_INFO) {
1098 res->bfi.allocated_clusters++;
1099 res->bfi.compressed_clusters++;
1100
1101 /* Compressed clusters are fragmented by nature. Since they
1102 * take up sub-sector space but we only have sector granularity
1103 * I/O we need to re-read the same sectors even for adjacent
1104 * compressed clusters.
1105 */
1106 res->bfi.fragmented_clusters++;
1107 }
1108 break;
1109
1110 case QCOW2_CLUSTER_ZERO:
1111 if ((l2_entry & L2E_OFFSET_MASK) == 0) {
1112 break;
1113 }
1114 /* fall through */
1115
1116 case QCOW2_CLUSTER_NORMAL:
1117 {
1118 uint64_t offset = l2_entry & L2E_OFFSET_MASK;
1119
1120 if (flags & CHECK_FRAG_INFO) {
1121 res->bfi.allocated_clusters++;
1122 if (next_contiguous_offset &&
1123 offset != next_contiguous_offset) {
1124 res->bfi.fragmented_clusters++;
1125 }
1126 next_contiguous_offset = offset + s->cluster_size;
1127 }
1128
1129 /* Mark cluster as used */
1130 inc_refcounts(bs, res, refcount_table,refcount_table_size,
1131 offset, s->cluster_size);
1132
1133 /* Correct offsets are cluster aligned */
1134 if (offset_into_cluster(s, offset)) {
1135 fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
1136 "properly aligned; L2 entry corrupted.\n", offset);
1137 res->corruptions++;
1138 }
1139 break;
1140 }
1141
1142 case QCOW2_CLUSTER_UNALLOCATED:
1143 break;
1144
1145 default:
1146 abort();
1147 }
1148 }
1149
1150 g_free(l2_table);
1151 return 0;
1152
1153 fail:
1154 fprintf(stderr, "ERROR: I/O error in check_refcounts_l2\n");
1155 g_free(l2_table);
1156 return -EIO;
1157 }
1158
1159 /*
1160 * Increases the refcount for the L1 table, its L2 tables and all referenced
1161 * clusters in the given refcount table. While doing so, performs some checks
1162 * on L1 and L2 entries.
1163 *
1164 * Returns the number of errors found by the checks or -errno if an internal
1165 * error occurred.
1166 */
1167 static int check_refcounts_l1(BlockDriverState *bs,
1168 BdrvCheckResult *res,
1169 uint16_t *refcount_table,
1170 int refcount_table_size,
1171 int64_t l1_table_offset, int l1_size,
1172 int flags)
1173 {
1174 BDRVQcowState *s = bs->opaque;
1175 uint64_t *l1_table, l2_offset, l1_size2;
1176 int i, ret;
1177
1178 l1_size2 = l1_size * sizeof(uint64_t);
1179
1180 /* Mark L1 table as used */
1181 inc_refcounts(bs, res, refcount_table, refcount_table_size,
1182 l1_table_offset, l1_size2);
1183
1184 /* Read L1 table entries from disk */
1185 if (l1_size2 == 0) {
1186 l1_table = NULL;
1187 } else {
1188 l1_table = g_malloc(l1_size2);
1189 if (bdrv_pread(bs->file, l1_table_offset,
1190 l1_table, l1_size2) != l1_size2)
1191 goto fail;
1192 for(i = 0;i < l1_size; i++)
1193 be64_to_cpus(&l1_table[i]);
1194 }
1195
1196 /* Do the actual checks */
1197 for(i = 0; i < l1_size; i++) {
1198 l2_offset = l1_table[i];
1199 if (l2_offset) {
1200 /* Mark L2 table as used */
1201 l2_offset &= L1E_OFFSET_MASK;
1202 inc_refcounts(bs, res, refcount_table, refcount_table_size,
1203 l2_offset, s->cluster_size);
1204
1205 /* L2 tables are cluster aligned */
1206 if (offset_into_cluster(s, l2_offset)) {
1207 fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
1208 "cluster aligned; L1 entry corrupted\n", l2_offset);
1209 res->corruptions++;
1210 }
1211
1212 /* Process and check L2 entries */
1213 ret = check_refcounts_l2(bs, res, refcount_table,
1214 refcount_table_size, l2_offset, flags);
1215 if (ret < 0) {
1216 goto fail;
1217 }
1218 }
1219 }
1220 g_free(l1_table);
1221 return 0;
1222
1223 fail:
1224 fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
1225 res->check_errors++;
1226 g_free(l1_table);
1227 return -EIO;
1228 }
1229
1230 /*
1231 * Checks the OFLAG_COPIED flag for all L1 and L2 entries.
1232 *
1233 * This function does not print an error message nor does it increment
1234 * check_errors if get_refcount fails (this is because such an error will have
1235 * been already detected and sufficiently signaled by the calling function
1236 * (qcow2_check_refcounts) by the time this function is called).
1237 */
1238 static int check_oflag_copied(BlockDriverState *bs, BdrvCheckResult *res,
1239 BdrvCheckMode fix)
1240 {
1241 BDRVQcowState *s = bs->opaque;
1242 uint64_t *l2_table = qemu_blockalign(bs, s->cluster_size);
1243 int ret;
1244 int refcount;
1245 int i, j;
1246
1247 for (i = 0; i < s->l1_size; i++) {
1248 uint64_t l1_entry = s->l1_table[i];
1249 uint64_t l2_offset = l1_entry & L1E_OFFSET_MASK;
1250 bool l2_dirty = false;
1251
1252 if (!l2_offset) {
1253 continue;
1254 }
1255
1256 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
1257 if (refcount < 0) {
1258 /* don't print message nor increment check_errors */
1259 continue;
1260 }
1261 if ((refcount == 1) != ((l1_entry & QCOW_OFLAG_COPIED) != 0)) {
1262 fprintf(stderr, "%s OFLAG_COPIED L2 cluster: l1_index=%d "
1263 "l1_entry=%" PRIx64 " refcount=%d\n",
1264 fix & BDRV_FIX_ERRORS ? "Repairing" :
1265 "ERROR",
1266 i, l1_entry, refcount);
1267 if (fix & BDRV_FIX_ERRORS) {
1268 s->l1_table[i] = refcount == 1
1269 ? l1_entry | QCOW_OFLAG_COPIED
1270 : l1_entry & ~QCOW_OFLAG_COPIED;
1271 ret = qcow2_write_l1_entry(bs, i);
1272 if (ret < 0) {
1273 res->check_errors++;
1274 goto fail;
1275 }
1276 res->corruptions_fixed++;
1277 } else {
1278 res->corruptions++;
1279 }
1280 }
1281
1282 ret = bdrv_pread(bs->file, l2_offset, l2_table,
1283 s->l2_size * sizeof(uint64_t));
1284 if (ret < 0) {
1285 fprintf(stderr, "ERROR: Could not read L2 table: %s\n",
1286 strerror(-ret));
1287 res->check_errors++;
1288 goto fail;
1289 }
1290
1291 for (j = 0; j < s->l2_size; j++) {
1292 uint64_t l2_entry = be64_to_cpu(l2_table[j]);
1293 uint64_t data_offset = l2_entry & L2E_OFFSET_MASK;
1294 int cluster_type = qcow2_get_cluster_type(l2_entry);
1295
1296 if ((cluster_type == QCOW2_CLUSTER_NORMAL) ||
1297 ((cluster_type == QCOW2_CLUSTER_ZERO) && (data_offset != 0))) {
1298 refcount = get_refcount(bs, data_offset >> s->cluster_bits);
1299 if (refcount < 0) {
1300 /* don't print message nor increment check_errors */
1301 continue;
1302 }
1303 if ((refcount == 1) != ((l2_entry & QCOW_OFLAG_COPIED) != 0)) {
1304 fprintf(stderr, "%s OFLAG_COPIED data cluster: "
1305 "l2_entry=%" PRIx64 " refcount=%d\n",
1306 fix & BDRV_FIX_ERRORS ? "Repairing" :
1307 "ERROR",
1308 l2_entry, refcount);
1309 if (fix & BDRV_FIX_ERRORS) {
1310 l2_table[j] = cpu_to_be64(refcount == 1
1311 ? l2_entry | QCOW_OFLAG_COPIED
1312 : l2_entry & ~QCOW_OFLAG_COPIED);
1313 l2_dirty = true;
1314 res->corruptions_fixed++;
1315 } else {
1316 res->corruptions++;
1317 }
1318 }
1319 }
1320 }
1321
1322 if (l2_dirty) {
1323 ret = qcow2_pre_write_overlap_check(bs, QCOW2_OL_ACTIVE_L2,
1324 l2_offset, s->cluster_size);
1325 if (ret < 0) {
1326 fprintf(stderr, "ERROR: Could not write L2 table; metadata "
1327 "overlap check failed: %s\n", strerror(-ret));
1328 res->check_errors++;
1329 goto fail;
1330 }
1331
1332 ret = bdrv_pwrite(bs->file, l2_offset, l2_table, s->cluster_size);
1333 if (ret < 0) {
1334 fprintf(stderr, "ERROR: Could not write L2 table: %s\n",
1335 strerror(-ret));
1336 res->check_errors++;
1337 goto fail;
1338 }
1339 }
1340 }
1341
1342 ret = 0;
1343
1344 fail:
1345 qemu_vfree(l2_table);
1346 return ret;
1347 }
1348
1349 /*
1350 * Writes one sector of the refcount table to the disk
1351 */
1352 #define RT_ENTRIES_PER_SECTOR (512 / sizeof(uint64_t))
1353 static int write_reftable_entry(BlockDriverState *bs, int rt_index)
1354 {
1355 BDRVQcowState *s = bs->opaque;
1356 uint64_t buf[RT_ENTRIES_PER_SECTOR];
1357 int rt_start_index;
1358 int i, ret;
1359
1360 rt_start_index = rt_index & ~(RT_ENTRIES_PER_SECTOR - 1);
1361 for (i = 0; i < RT_ENTRIES_PER_SECTOR; i++) {
1362 buf[i] = cpu_to_be64(s->refcount_table[rt_start_index + i]);
1363 }
1364
1365 ret = qcow2_pre_write_overlap_check(bs, QCOW2_OL_REFCOUNT_TABLE,
1366 s->refcount_table_offset + rt_start_index * sizeof(uint64_t),
1367 sizeof(buf));
1368 if (ret < 0) {
1369 return ret;
1370 }
1371
1372 BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_UPDATE);
1373 ret = bdrv_pwrite_sync(bs->file, s->refcount_table_offset +
1374 rt_start_index * sizeof(uint64_t), buf, sizeof(buf));
1375 if (ret < 0) {
1376 return ret;
1377 }
1378
1379 return 0;
1380 }
1381
1382 /*
1383 * Allocates a new cluster for the given refcount block (represented by its
1384 * offset in the image file) and copies the current content there. This function
1385 * does _not_ decrement the reference count for the currently occupied cluster.
1386 *
1387 * This function prints an informative message to stderr on error (and returns
1388 * -errno); on success, the offset of the newly allocated cluster is returned.
1389 */
1390 static int64_t realloc_refcount_block(BlockDriverState *bs, int reftable_index,
1391 uint64_t offset)
1392 {
1393 BDRVQcowState *s = bs->opaque;
1394 int64_t new_offset = 0;
1395 void *refcount_block = NULL;
1396 int ret;
1397
1398 /* allocate new refcount block */
1399 new_offset = qcow2_alloc_clusters(bs, s->cluster_size);
1400 if (new_offset < 0) {
1401 fprintf(stderr, "Could not allocate new cluster: %s\n",
1402 strerror(-new_offset));
1403 ret = new_offset;
1404 goto done;
1405 }
1406
1407 /* fetch current refcount block content */
1408 ret = qcow2_cache_get(bs, s->refcount_block_cache, offset, &refcount_block);
1409 if (ret < 0) {
1410 fprintf(stderr, "Could not fetch refcount block: %s\n", strerror(-ret));
1411 goto fail_free_cluster;
1412 }
1413
1414 /* new block has not yet been entered into refcount table, therefore it is
1415 * no refcount block yet (regarding this check) */
1416 ret = qcow2_pre_write_overlap_check(bs, 0, new_offset, s->cluster_size);
1417 if (ret < 0) {
1418 fprintf(stderr, "Could not write refcount block; metadata overlap "
1419 "check failed: %s\n", strerror(-ret));
1420 /* the image will be marked corrupt, so don't even attempt on freeing
1421 * the cluster */
1422 goto done;
1423 }
1424
1425 /* write to new block */
1426 ret = bdrv_write(bs->file, new_offset / BDRV_SECTOR_SIZE, refcount_block,
1427 s->cluster_sectors);
1428 if (ret < 0) {
1429 fprintf(stderr, "Could not write refcount block: %s\n", strerror(-ret));
1430 goto fail_free_cluster;
1431 }
1432
1433 /* update refcount table */
1434 assert(!offset_into_cluster(s, new_offset));
1435 s->refcount_table[reftable_index] = new_offset;
1436 ret = write_reftable_entry(bs, reftable_index);
1437 if (ret < 0) {
1438 fprintf(stderr, "Could not update refcount table: %s\n",
1439 strerror(-ret));
1440 goto fail_free_cluster;
1441 }
1442
1443 goto done;
1444
1445 fail_free_cluster:
1446 qcow2_free_clusters(bs, new_offset, s->cluster_size, QCOW2_DISCARD_OTHER);
1447
1448 done:
1449 if (refcount_block) {
1450 /* This should never fail, as it would only do so if the given refcount
1451 * block cannot be found in the cache. As this is impossible as long as
1452 * there are no bugs, assert the success. */
1453 int tmp = qcow2_cache_put(bs, s->refcount_block_cache, &refcount_block);
1454 assert(tmp == 0);
1455 }
1456
1457 if (ret < 0) {
1458 return ret;
1459 }
1460
1461 return new_offset;
1462 }
1463
1464 /*
1465 * Checks an image for refcount consistency.
1466 *
1467 * Returns 0 if no errors are found, the number of errors in case the image is
1468 * detected as corrupted, and -errno when an internal error occurred.
1469 */
1470 int qcow2_check_refcounts(BlockDriverState *bs, BdrvCheckResult *res,
1471 BdrvCheckMode fix)
1472 {
1473 BDRVQcowState *s = bs->opaque;
1474 int64_t size, i, highest_cluster;
1475 int nb_clusters, refcount1, refcount2;
1476 QCowSnapshot *sn;
1477 uint16_t *refcount_table;
1478 int ret;
1479
1480 size = bdrv_getlength(bs->file);
1481 nb_clusters = size_to_clusters(s, size);
1482 refcount_table = g_malloc0(nb_clusters * sizeof(uint16_t));
1483
1484 res->bfi.total_clusters =
1485 size_to_clusters(s, bs->total_sectors * BDRV_SECTOR_SIZE);
1486
1487 /* header */
1488 inc_refcounts(bs, res, refcount_table, nb_clusters,
1489 0, s->cluster_size);
1490
1491 /* current L1 table */
1492 ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1493 s->l1_table_offset, s->l1_size, CHECK_FRAG_INFO);
1494 if (ret < 0) {
1495 goto fail;
1496 }
1497
1498 /* snapshots */
1499 for(i = 0; i < s->nb_snapshots; i++) {
1500 sn = s->snapshots + i;
1501 ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1502 sn->l1_table_offset, sn->l1_size, 0);
1503 if (ret < 0) {
1504 goto fail;
1505 }
1506 }
1507 inc_refcounts(bs, res, refcount_table, nb_clusters,
1508 s->snapshots_offset, s->snapshots_size);
1509
1510 /* refcount data */
1511 inc_refcounts(bs, res, refcount_table, nb_clusters,
1512 s->refcount_table_offset,
1513 s->refcount_table_size * sizeof(uint64_t));
1514
1515 for(i = 0; i < s->refcount_table_size; i++) {
1516 uint64_t offset, cluster;
1517 offset = s->refcount_table[i];
1518 cluster = offset >> s->cluster_bits;
1519
1520 /* Refcount blocks are cluster aligned */
1521 if (offset_into_cluster(s, offset)) {
1522 fprintf(stderr, "ERROR refcount block %" PRId64 " is not "
1523 "cluster aligned; refcount table entry corrupted\n", i);
1524 res->corruptions++;
1525 continue;
1526 }
1527
1528 if (cluster >= nb_clusters) {
1529 fprintf(stderr, "ERROR refcount block %" PRId64
1530 " is outside image\n", i);
1531 res->corruptions++;
1532 continue;
1533 }
1534
1535 if (offset != 0) {
1536 inc_refcounts(bs, res, refcount_table, nb_clusters,
1537 offset, s->cluster_size);
1538 if (refcount_table[cluster] != 1) {
1539 fprintf(stderr, "%s refcount block %" PRId64
1540 " refcount=%d\n",
1541 fix & BDRV_FIX_ERRORS ? "Repairing" :
1542 "ERROR",
1543 i, refcount_table[cluster]);
1544
1545 if (fix & BDRV_FIX_ERRORS) {
1546 int64_t new_offset;
1547
1548 new_offset = realloc_refcount_block(bs, i, offset);
1549 if (new_offset < 0) {
1550 res->corruptions++;
1551 continue;
1552 }
1553
1554 /* update refcounts */
1555 if ((new_offset >> s->cluster_bits) >= nb_clusters) {
1556 /* increase refcount_table size if necessary */
1557 int old_nb_clusters = nb_clusters;
1558 nb_clusters = (new_offset >> s->cluster_bits) + 1;
1559 refcount_table = g_realloc(refcount_table,
1560 nb_clusters * sizeof(uint16_t));
1561 memset(&refcount_table[old_nb_clusters], 0, (nb_clusters
1562 - old_nb_clusters) * sizeof(uint16_t));
1563 }
1564 refcount_table[cluster]--;
1565 inc_refcounts(bs, res, refcount_table, nb_clusters,
1566 new_offset, s->cluster_size);
1567
1568 res->corruptions_fixed++;
1569 } else {
1570 res->corruptions++;
1571 }
1572 }
1573 }
1574 }
1575
1576 /* compare ref counts */
1577 for (i = 0, highest_cluster = 0; i < nb_clusters; i++) {
1578 refcount1 = get_refcount(bs, i);
1579 if (refcount1 < 0) {
1580 fprintf(stderr, "Can't get refcount for cluster %" PRId64 ": %s\n",
1581 i, strerror(-refcount1));
1582 res->check_errors++;
1583 continue;
1584 }
1585
1586 refcount2 = refcount_table[i];
1587
1588 if (refcount1 > 0 || refcount2 > 0) {
1589 highest_cluster = i;
1590 }
1591
1592 if (refcount1 != refcount2) {
1593
1594 /* Check if we're allowed to fix the mismatch */
1595 int *num_fixed = NULL;
1596 if (refcount1 > refcount2 && (fix & BDRV_FIX_LEAKS)) {
1597 num_fixed = &res->leaks_fixed;
1598 } else if (refcount1 < refcount2 && (fix & BDRV_FIX_ERRORS)) {
1599 num_fixed = &res->corruptions_fixed;
1600 }
1601
1602 fprintf(stderr, "%s cluster %" PRId64 " refcount=%d reference=%d\n",
1603 num_fixed != NULL ? "Repairing" :
1604 refcount1 < refcount2 ? "ERROR" :
1605 "Leaked",
1606 i, refcount1, refcount2);
1607
1608 if (num_fixed) {
1609 ret = update_refcount(bs, i << s->cluster_bits, 1,
1610 refcount2 - refcount1,
1611 QCOW2_DISCARD_ALWAYS);
1612 if (ret >= 0) {
1613 (*num_fixed)++;
1614 continue;
1615 }
1616 }
1617
1618 /* And if we couldn't, print an error */
1619 if (refcount1 < refcount2) {
1620 res->corruptions++;
1621 } else {
1622 res->leaks++;
1623 }
1624 }
1625 }
1626
1627 /* check OFLAG_COPIED */
1628 ret = check_oflag_copied(bs, res, fix);
1629 if (ret < 0) {
1630 goto fail;
1631 }
1632
1633 res->image_end_offset = (highest_cluster + 1) * s->cluster_size;
1634 ret = 0;
1635
1636 fail:
1637 g_free(refcount_table);
1638
1639 return ret;
1640 }
1641
1642 #define overlaps_with(ofs, sz) \
1643 ranges_overlap(offset, size, ofs, sz)
1644
1645 /*
1646 * Checks if the given offset into the image file is actually free to use by
1647 * looking for overlaps with important metadata sections (L1/L2 tables etc.),
1648 * i.e. a sanity check without relying on the refcount tables.
1649 *
1650 * The ign parameter specifies what checks not to perform (being a bitmask of
1651 * QCow2MetadataOverlap values), i.e., what sections to ignore.
1652 *
1653 * Returns:
1654 * - 0 if writing to this offset will not affect the mentioned metadata
1655 * - a positive QCow2MetadataOverlap value indicating one overlapping section
1656 * - a negative value (-errno) indicating an error while performing a check,
1657 * e.g. when bdrv_read failed on QCOW2_OL_INACTIVE_L2
1658 */
1659 int qcow2_check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
1660 int64_t size)
1661 {
1662 BDRVQcowState *s = bs->opaque;
1663 int chk = s->overlap_check & ~ign;
1664 int i, j;
1665
1666 if (!size) {
1667 return 0;
1668 }
1669
1670 if (chk & QCOW2_OL_MAIN_HEADER) {
1671 if (offset < s->cluster_size) {
1672 return QCOW2_OL_MAIN_HEADER;
1673 }
1674 }
1675
1676 /* align range to test to cluster boundaries */
1677 size = align_offset(offset_into_cluster(s, offset) + size, s->cluster_size);
1678 offset = start_of_cluster(s, offset);
1679
1680 if ((chk & QCOW2_OL_ACTIVE_L1) && s->l1_size) {
1681 if (overlaps_with(s->l1_table_offset, s->l1_size * sizeof(uint64_t))) {
1682 return QCOW2_OL_ACTIVE_L1;
1683 }
1684 }
1685
1686 if ((chk & QCOW2_OL_REFCOUNT_TABLE) && s->refcount_table_size) {
1687 if (overlaps_with(s->refcount_table_offset,
1688 s->refcount_table_size * sizeof(uint64_t))) {
1689 return QCOW2_OL_REFCOUNT_TABLE;
1690 }
1691 }
1692
1693 if ((chk & QCOW2_OL_SNAPSHOT_TABLE) && s->snapshots_size) {
1694 if (overlaps_with(s->snapshots_offset, s->snapshots_size)) {
1695 return QCOW2_OL_SNAPSHOT_TABLE;
1696 }
1697 }
1698
1699 if ((chk & QCOW2_OL_INACTIVE_L1) && s->snapshots) {
1700 for (i = 0; i < s->nb_snapshots; i++) {
1701 if (s->snapshots[i].l1_size &&
1702 overlaps_with(s->snapshots[i].l1_table_offset,
1703 s->snapshots[i].l1_size * sizeof(uint64_t))) {
1704 return QCOW2_OL_INACTIVE_L1;
1705 }
1706 }
1707 }
1708
1709 if ((chk & QCOW2_OL_ACTIVE_L2) && s->l1_table) {
1710 for (i = 0; i < s->l1_size; i++) {
1711 if ((s->l1_table[i] & L1E_OFFSET_MASK) &&
1712 overlaps_with(s->l1_table[i] & L1E_OFFSET_MASK,
1713 s->cluster_size)) {
1714 return QCOW2_OL_ACTIVE_L2;
1715 }
1716 }
1717 }
1718
1719 if ((chk & QCOW2_OL_REFCOUNT_BLOCK) && s->refcount_table) {
1720 for (i = 0; i < s->refcount_table_size; i++) {
1721 if ((s->refcount_table[i] & REFT_OFFSET_MASK) &&
1722 overlaps_with(s->refcount_table[i] & REFT_OFFSET_MASK,
1723 s->cluster_size)) {
1724 return QCOW2_OL_REFCOUNT_BLOCK;
1725 }
1726 }
1727 }
1728
1729 if ((chk & QCOW2_OL_INACTIVE_L2) && s->snapshots) {
1730 for (i = 0; i < s->nb_snapshots; i++) {
1731 uint64_t l1_ofs = s->snapshots[i].l1_table_offset;
1732 uint32_t l1_sz = s->snapshots[i].l1_size;
1733 uint64_t l1_sz2 = l1_sz * sizeof(uint64_t);
1734 uint64_t *l1 = g_malloc(l1_sz2);
1735 int ret;
1736
1737 ret = bdrv_pread(bs->file, l1_ofs, l1, l1_sz2);
1738 if (ret < 0) {
1739 g_free(l1);
1740 return ret;
1741 }
1742
1743 for (j = 0; j < l1_sz; j++) {
1744 uint64_t l2_ofs = be64_to_cpu(l1[j]) & L1E_OFFSET_MASK;
1745 if (l2_ofs && overlaps_with(l2_ofs, s->cluster_size)) {
1746 g_free(l1);
1747 return QCOW2_OL_INACTIVE_L2;
1748 }
1749 }
1750
1751 g_free(l1);
1752 }
1753 }
1754
1755 return 0;
1756 }
1757
1758 static const char *metadata_ol_names[] = {
1759 [QCOW2_OL_MAIN_HEADER_BITNR] = "qcow2_header",
1760 [QCOW2_OL_ACTIVE_L1_BITNR] = "active L1 table",
1761 [QCOW2_OL_ACTIVE_L2_BITNR] = "active L2 table",
1762 [QCOW2_OL_REFCOUNT_TABLE_BITNR] = "refcount table",
1763 [QCOW2_OL_REFCOUNT_BLOCK_BITNR] = "refcount block",
1764 [QCOW2_OL_SNAPSHOT_TABLE_BITNR] = "snapshot table",
1765 [QCOW2_OL_INACTIVE_L1_BITNR] = "inactive L1 table",
1766 [QCOW2_OL_INACTIVE_L2_BITNR] = "inactive L2 table",
1767 };
1768
1769 /*
1770 * First performs a check for metadata overlaps (through
1771 * qcow2_check_metadata_overlap); if that fails with a negative value (error
1772 * while performing a check), that value is returned. If an impending overlap
1773 * is detected, the BDS will be made unusable, the qcow2 file marked corrupt
1774 * and -EIO returned.
1775 *
1776 * Returns 0 if there were neither overlaps nor errors while checking for
1777 * overlaps; or a negative value (-errno) on error.
1778 */
1779 int qcow2_pre_write_overlap_check(BlockDriverState *bs, int ign, int64_t offset,
1780 int64_t size)
1781 {
1782 int ret = qcow2_check_metadata_overlap(bs, ign, offset, size);
1783
1784 if (ret < 0) {
1785 return ret;
1786 } else if (ret > 0) {
1787 int metadata_ol_bitnr = ffs(ret) - 1;
1788 char *message;
1789 QObject *data;
1790
1791 assert(metadata_ol_bitnr < QCOW2_OL_MAX_BITNR);
1792
1793 fprintf(stderr, "qcow2: Preventing invalid write on metadata (overlaps "
1794 "with %s); image marked as corrupt.\n",
1795 metadata_ol_names[metadata_ol_bitnr]);
1796 message = g_strdup_printf("Prevented %s overwrite",
1797 metadata_ol_names[metadata_ol_bitnr]);
1798 data = qobject_from_jsonf("{ 'device': %s, 'msg': %s, 'offset': %"
1799 PRId64 ", 'size': %" PRId64 " }", bs->device_name, message,
1800 offset, size);
1801 monitor_protocol_event(QEVENT_BLOCK_IMAGE_CORRUPTED, data);
1802 g_free(message);
1803 qobject_decref(data);
1804
1805 qcow2_mark_corrupt(bs);
1806 bs->drv = NULL; /* make BDS unusable */
1807 return -EIO;
1808 }
1809
1810 return 0;
1811 }