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