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 30 static int64_t alloc_clusters_noref(BlockDriverState *bs, uint64_t size); 31 static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs, 32 int64_t offset, int64_t length, uint64_t addend, 33 bool decrease, enum qcow2_discard_type type); 34 35 static uint64_t get_refcount_ro0(const void *refcount_array, uint64_t index); 36 static uint64_t get_refcount_ro1(const void *refcount_array, uint64_t index); 37 static uint64_t get_refcount_ro2(const void *refcount_array, uint64_t index); 38 static uint64_t get_refcount_ro3(const void *refcount_array, uint64_t index); 39 static uint64_t get_refcount_ro4(const void *refcount_array, uint64_t index); 40 static uint64_t get_refcount_ro5(const void *refcount_array, uint64_t index); 41 static uint64_t get_refcount_ro6(const void *refcount_array, uint64_t index); 42 43 static void set_refcount_ro0(void *refcount_array, uint64_t index, 44 uint64_t value); 45 static void set_refcount_ro1(void *refcount_array, uint64_t index, 46 uint64_t value); 47 static void set_refcount_ro2(void *refcount_array, uint64_t index, 48 uint64_t value); 49 static void set_refcount_ro3(void *refcount_array, uint64_t index, 50 uint64_t value); 51 static void set_refcount_ro4(void *refcount_array, uint64_t index, 52 uint64_t value); 53 static void set_refcount_ro5(void *refcount_array, uint64_t index, 54 uint64_t value); 55 static void set_refcount_ro6(void *refcount_array, uint64_t index, 56 uint64_t value); 57 58 59 static Qcow2GetRefcountFunc *const get_refcount_funcs[] = { 60 &get_refcount_ro0, 61 &get_refcount_ro1, 62 &get_refcount_ro2, 63 &get_refcount_ro3, 64 &get_refcount_ro4, 65 &get_refcount_ro5, 66 &get_refcount_ro6 67 }; 68 69 static Qcow2SetRefcountFunc *const set_refcount_funcs[] = { 70 &set_refcount_ro0, 71 &set_refcount_ro1, 72 &set_refcount_ro2, 73 &set_refcount_ro3, 74 &set_refcount_ro4, 75 &set_refcount_ro5, 76 &set_refcount_ro6 77 }; 78 79 80 /*********************************************************/ 81 /* refcount handling */ 82 83 int qcow2_refcount_init(BlockDriverState *bs) 84 { 85 BDRVQcowState *s = bs->opaque; 86 unsigned int refcount_table_size2, i; 87 int ret; 88 89 assert(s->refcount_order >= 0 && s->refcount_order <= 6); 90 91 s->get_refcount = get_refcount_funcs[s->refcount_order]; 92 s->set_refcount = set_refcount_funcs[s->refcount_order]; 93 94 assert(s->refcount_table_size <= INT_MAX / sizeof(uint64_t)); 95 refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t); 96 s->refcount_table = g_try_malloc(refcount_table_size2); 97 98 if (s->refcount_table_size > 0) { 99 if (s->refcount_table == NULL) { 100 ret = -ENOMEM; 101 goto fail; 102 } 103 BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_LOAD); 104 ret = bdrv_pread(bs->file, s->refcount_table_offset, 105 s->refcount_table, refcount_table_size2); 106 if (ret < 0) { 107 goto fail; 108 } 109 for(i = 0; i < s->refcount_table_size; i++) 110 be64_to_cpus(&s->refcount_table[i]); 111 } 112 return 0; 113 fail: 114 return ret; 115 } 116 117 void qcow2_refcount_close(BlockDriverState *bs) 118 { 119 BDRVQcowState *s = bs->opaque; 120 g_free(s->refcount_table); 121 } 122 123 124 static uint64_t get_refcount_ro0(const void *refcount_array, uint64_t index) 125 { 126 return (((const uint8_t *)refcount_array)[index / 8] >> (index % 8)) & 0x1; 127 } 128 129 static void set_refcount_ro0(void *refcount_array, uint64_t index, 130 uint64_t value) 131 { 132 assert(!(value >> 1)); 133 ((uint8_t *)refcount_array)[index / 8] &= ~(0x1 << (index % 8)); 134 ((uint8_t *)refcount_array)[index / 8] |= value << (index % 8); 135 } 136 137 static uint64_t get_refcount_ro1(const void *refcount_array, uint64_t index) 138 { 139 return (((const uint8_t *)refcount_array)[index / 4] >> (2 * (index % 4))) 140 & 0x3; 141 } 142 143 static void set_refcount_ro1(void *refcount_array, uint64_t index, 144 uint64_t value) 145 { 146 assert(!(value >> 2)); 147 ((uint8_t *)refcount_array)[index / 4] &= ~(0x3 << (2 * (index % 4))); 148 ((uint8_t *)refcount_array)[index / 4] |= value << (2 * (index % 4)); 149 } 150 151 static uint64_t get_refcount_ro2(const void *refcount_array, uint64_t index) 152 { 153 return (((const uint8_t *)refcount_array)[index / 2] >> (4 * (index % 2))) 154 & 0xf; 155 } 156 157 static void set_refcount_ro2(void *refcount_array, uint64_t index, 158 uint64_t value) 159 { 160 assert(!(value >> 4)); 161 ((uint8_t *)refcount_array)[index / 2] &= ~(0xf << (4 * (index % 2))); 162 ((uint8_t *)refcount_array)[index / 2] |= value << (4 * (index % 2)); 163 } 164 165 static uint64_t get_refcount_ro3(const void *refcount_array, uint64_t index) 166 { 167 return ((const uint8_t *)refcount_array)[index]; 168 } 169 170 static void set_refcount_ro3(void *refcount_array, uint64_t index, 171 uint64_t value) 172 { 173 assert(!(value >> 8)); 174 ((uint8_t *)refcount_array)[index] = value; 175 } 176 177 static uint64_t get_refcount_ro4(const void *refcount_array, uint64_t index) 178 { 179 return be16_to_cpu(((const uint16_t *)refcount_array)[index]); 180 } 181 182 static void set_refcount_ro4(void *refcount_array, uint64_t index, 183 uint64_t value) 184 { 185 assert(!(value >> 16)); 186 ((uint16_t *)refcount_array)[index] = cpu_to_be16(value); 187 } 188 189 static uint64_t get_refcount_ro5(const void *refcount_array, uint64_t index) 190 { 191 return be32_to_cpu(((const uint32_t *)refcount_array)[index]); 192 } 193 194 static void set_refcount_ro5(void *refcount_array, uint64_t index, 195 uint64_t value) 196 { 197 assert(!(value >> 32)); 198 ((uint32_t *)refcount_array)[index] = cpu_to_be32(value); 199 } 200 201 static uint64_t get_refcount_ro6(const void *refcount_array, uint64_t index) 202 { 203 return be64_to_cpu(((const uint64_t *)refcount_array)[index]); 204 } 205 206 static void set_refcount_ro6(void *refcount_array, uint64_t index, 207 uint64_t value) 208 { 209 ((uint64_t *)refcount_array)[index] = cpu_to_be64(value); 210 } 211 212 213 static int load_refcount_block(BlockDriverState *bs, 214 int64_t refcount_block_offset, 215 void **refcount_block) 216 { 217 BDRVQcowState *s = bs->opaque; 218 int ret; 219 220 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_LOAD); 221 ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset, 222 refcount_block); 223 224 return ret; 225 } 226 227 /* 228 * Retrieves the refcount of the cluster given by its index and stores it in 229 * *refcount. Returns 0 on success and -errno on failure. 230 */ 231 int qcow2_get_refcount(BlockDriverState *bs, int64_t cluster_index, 232 uint64_t *refcount) 233 { 234 BDRVQcowState *s = bs->opaque; 235 uint64_t refcount_table_index, block_index; 236 int64_t refcount_block_offset; 237 int ret; 238 void *refcount_block; 239 240 refcount_table_index = cluster_index >> s->refcount_block_bits; 241 if (refcount_table_index >= s->refcount_table_size) { 242 *refcount = 0; 243 return 0; 244 } 245 refcount_block_offset = 246 s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK; 247 if (!refcount_block_offset) { 248 *refcount = 0; 249 return 0; 250 } 251 252 if (offset_into_cluster(s, refcount_block_offset)) { 253 qcow2_signal_corruption(bs, true, -1, -1, "Refblock offset %#" PRIx64 254 " unaligned (reftable index: %#" PRIx64 ")", 255 refcount_block_offset, refcount_table_index); 256 return -EIO; 257 } 258 259 ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset, 260 &refcount_block); 261 if (ret < 0) { 262 return ret; 263 } 264 265 block_index = cluster_index & (s->refcount_block_size - 1); 266 *refcount = s->get_refcount(refcount_block, block_index); 267 268 ret = qcow2_cache_put(bs, s->refcount_block_cache, &refcount_block); 269 if (ret < 0) { 270 return ret; 271 } 272 273 return 0; 274 } 275 276 /* 277 * Rounds the refcount table size up to avoid growing the table for each single 278 * refcount block that is allocated. 279 */ 280 static unsigned int next_refcount_table_size(BDRVQcowState *s, 281 unsigned int min_size) 282 { 283 unsigned int min_clusters = (min_size >> (s->cluster_bits - 3)) + 1; 284 unsigned int refcount_table_clusters = 285 MAX(1, s->refcount_table_size >> (s->cluster_bits - 3)); 286 287 while (min_clusters > refcount_table_clusters) { 288 refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2; 289 } 290 291 return refcount_table_clusters << (s->cluster_bits - 3); 292 } 293 294 295 /* Checks if two offsets are described by the same refcount block */ 296 static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a, 297 uint64_t offset_b) 298 { 299 uint64_t block_a = offset_a >> (s->cluster_bits + s->refcount_block_bits); 300 uint64_t block_b = offset_b >> (s->cluster_bits + s->refcount_block_bits); 301 302 return (block_a == block_b); 303 } 304 305 /* 306 * Loads a refcount block. If it doesn't exist yet, it is allocated first 307 * (including growing the refcount table if needed). 308 * 309 * Returns 0 on success or -errno in error case 310 */ 311 static int alloc_refcount_block(BlockDriverState *bs, 312 int64_t cluster_index, void **refcount_block) 313 { 314 BDRVQcowState *s = bs->opaque; 315 unsigned int refcount_table_index; 316 int ret; 317 318 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC); 319 320 /* Find the refcount block for the given cluster */ 321 refcount_table_index = cluster_index >> s->refcount_block_bits; 322 323 if (refcount_table_index < s->refcount_table_size) { 324 325 uint64_t refcount_block_offset = 326 s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK; 327 328 /* If it's already there, we're done */ 329 if (refcount_block_offset) { 330 if (offset_into_cluster(s, refcount_block_offset)) { 331 qcow2_signal_corruption(bs, true, -1, -1, "Refblock offset %#" 332 PRIx64 " unaligned (reftable index: " 333 "%#x)", refcount_block_offset, 334 refcount_table_index); 335 return -EIO; 336 } 337 338 return load_refcount_block(bs, refcount_block_offset, 339 refcount_block); 340 } 341 } 342 343 /* 344 * If we came here, we need to allocate something. Something is at least 345 * a cluster for the new refcount block. It may also include a new refcount 346 * table if the old refcount table is too small. 347 * 348 * Note that allocating clusters here needs some special care: 349 * 350 * - We can't use the normal qcow2_alloc_clusters(), it would try to 351 * increase the refcount and very likely we would end up with an endless 352 * recursion. Instead we must place the refcount blocks in a way that 353 * they can describe them themselves. 354 * 355 * - We need to consider that at this point we are inside update_refcounts 356 * and potentially doing an initial refcount increase. This means that 357 * some clusters have already been allocated by the caller, but their 358 * refcount isn't accurate yet. If we allocate clusters for metadata, we 359 * need to return -EAGAIN to signal the caller that it needs to restart 360 * the search for free clusters. 361 * 362 * - alloc_clusters_noref and qcow2_free_clusters may load a different 363 * refcount block into the cache 364 */ 365 366 *refcount_block = NULL; 367 368 /* We write to the refcount table, so we might depend on L2 tables */ 369 ret = qcow2_cache_flush(bs, s->l2_table_cache); 370 if (ret < 0) { 371 return ret; 372 } 373 374 /* Allocate the refcount block itself and mark it as used */ 375 int64_t new_block = alloc_clusters_noref(bs, s->cluster_size); 376 if (new_block < 0) { 377 return new_block; 378 } 379 380 #ifdef DEBUG_ALLOC2 381 fprintf(stderr, "qcow2: Allocate refcount block %d for %" PRIx64 382 " at %" PRIx64 "\n", 383 refcount_table_index, cluster_index << s->cluster_bits, new_block); 384 #endif 385 386 if (in_same_refcount_block(s, new_block, cluster_index << s->cluster_bits)) { 387 /* Zero the new refcount block before updating it */ 388 ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block, 389 refcount_block); 390 if (ret < 0) { 391 goto fail_block; 392 } 393 394 memset(*refcount_block, 0, s->cluster_size); 395 396 /* The block describes itself, need to update the cache */ 397 int block_index = (new_block >> s->cluster_bits) & 398 (s->refcount_block_size - 1); 399 s->set_refcount(*refcount_block, block_index, 1); 400 } else { 401 /* Described somewhere else. This can recurse at most twice before we 402 * arrive at a block that describes itself. */ 403 ret = update_refcount(bs, new_block, s->cluster_size, 1, false, 404 QCOW2_DISCARD_NEVER); 405 if (ret < 0) { 406 goto fail_block; 407 } 408 409 ret = qcow2_cache_flush(bs, s->refcount_block_cache); 410 if (ret < 0) { 411 goto fail_block; 412 } 413 414 /* Initialize the new refcount block only after updating its refcount, 415 * update_refcount uses the refcount cache itself */ 416 ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block, 417 refcount_block); 418 if (ret < 0) { 419 goto fail_block; 420 } 421 422 memset(*refcount_block, 0, s->cluster_size); 423 } 424 425 /* Now the new refcount block needs to be written to disk */ 426 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE); 427 qcow2_cache_entry_mark_dirty(s->refcount_block_cache, *refcount_block); 428 ret = qcow2_cache_flush(bs, s->refcount_block_cache); 429 if (ret < 0) { 430 goto fail_block; 431 } 432 433 /* If the refcount table is big enough, just hook the block up there */ 434 if (refcount_table_index < s->refcount_table_size) { 435 uint64_t data64 = cpu_to_be64(new_block); 436 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_HOOKUP); 437 ret = bdrv_pwrite_sync(bs->file, 438 s->refcount_table_offset + refcount_table_index * sizeof(uint64_t), 439 &data64, sizeof(data64)); 440 if (ret < 0) { 441 goto fail_block; 442 } 443 444 s->refcount_table[refcount_table_index] = new_block; 445 446 /* The new refcount block may be where the caller intended to put its 447 * data, so let it restart the search. */ 448 return -EAGAIN; 449 } 450 451 ret = qcow2_cache_put(bs, s->refcount_block_cache, refcount_block); 452 if (ret < 0) { 453 goto fail_block; 454 } 455 456 /* 457 * If we come here, we need to grow the refcount table. Again, a new 458 * refcount table needs some space and we can't simply allocate to avoid 459 * endless recursion. 460 * 461 * Therefore let's grab new refcount blocks at the end of the image, which 462 * will describe themselves and the new refcount table. This way we can 463 * reference them only in the new table and do the switch to the new 464 * refcount table at once without producing an inconsistent state in 465 * between. 466 */ 467 BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW); 468 469 /* Calculate the number of refcount blocks needed so far; this will be the 470 * basis for calculating the index of the first cluster used for the 471 * self-describing refcount structures which we are about to create. 472 * 473 * Because we reached this point, there cannot be any refcount entries for 474 * cluster_index or higher indices yet. However, because new_block has been 475 * allocated to describe that cluster (and it will assume this role later 476 * on), we cannot use that index; also, new_block may actually have a higher 477 * cluster index than cluster_index, so it needs to be taken into account 478 * here (and 1 needs to be added to its value because that cluster is used). 479 */ 480 uint64_t blocks_used = DIV_ROUND_UP(MAX(cluster_index + 1, 481 (new_block >> s->cluster_bits) + 1), 482 s->refcount_block_size); 483 484 if (blocks_used > QCOW_MAX_REFTABLE_SIZE / sizeof(uint64_t)) { 485 return -EFBIG; 486 } 487 488 /* And now we need at least one block more for the new metadata */ 489 uint64_t table_size = next_refcount_table_size(s, blocks_used + 1); 490 uint64_t last_table_size; 491 uint64_t blocks_clusters; 492 do { 493 uint64_t table_clusters = 494 size_to_clusters(s, table_size * sizeof(uint64_t)); 495 blocks_clusters = 1 + 496 ((table_clusters + s->refcount_block_size - 1) 497 / s->refcount_block_size); 498 uint64_t meta_clusters = table_clusters + blocks_clusters; 499 500 last_table_size = table_size; 501 table_size = next_refcount_table_size(s, blocks_used + 502 ((meta_clusters + s->refcount_block_size - 1) 503 / s->refcount_block_size)); 504 505 } while (last_table_size != table_size); 506 507 #ifdef DEBUG_ALLOC2 508 fprintf(stderr, "qcow2: Grow refcount table %" PRId32 " => %" PRId64 "\n", 509 s->refcount_table_size, table_size); 510 #endif 511 512 /* Create the new refcount table and blocks */ 513 uint64_t meta_offset = (blocks_used * s->refcount_block_size) * 514 s->cluster_size; 515 uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size; 516 uint64_t *new_table = g_try_new0(uint64_t, table_size); 517 void *new_blocks = g_try_malloc0(blocks_clusters * s->cluster_size); 518 519 assert(table_size > 0 && blocks_clusters > 0); 520 if (new_table == NULL || new_blocks == NULL) { 521 ret = -ENOMEM; 522 goto fail_table; 523 } 524 525 /* Fill the new refcount table */ 526 memcpy(new_table, s->refcount_table, 527 s->refcount_table_size * sizeof(uint64_t)); 528 new_table[refcount_table_index] = new_block; 529 530 int i; 531 for (i = 0; i < blocks_clusters; i++) { 532 new_table[blocks_used + i] = meta_offset + (i * s->cluster_size); 533 } 534 535 /* Fill the refcount blocks */ 536 uint64_t table_clusters = size_to_clusters(s, table_size * sizeof(uint64_t)); 537 int block = 0; 538 for (i = 0; i < table_clusters + blocks_clusters; i++) { 539 s->set_refcount(new_blocks, block++, 1); 540 } 541 542 /* Write refcount blocks to disk */ 543 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_BLOCKS); 544 ret = bdrv_pwrite_sync(bs->file, meta_offset, new_blocks, 545 blocks_clusters * s->cluster_size); 546 g_free(new_blocks); 547 new_blocks = NULL; 548 if (ret < 0) { 549 goto fail_table; 550 } 551 552 /* Write refcount table to disk */ 553 for(i = 0; i < table_size; i++) { 554 cpu_to_be64s(&new_table[i]); 555 } 556 557 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_TABLE); 558 ret = bdrv_pwrite_sync(bs->file, table_offset, new_table, 559 table_size * sizeof(uint64_t)); 560 if (ret < 0) { 561 goto fail_table; 562 } 563 564 for(i = 0; i < table_size; i++) { 565 be64_to_cpus(&new_table[i]); 566 } 567 568 /* Hook up the new refcount table in the qcow2 header */ 569 uint8_t data[12]; 570 cpu_to_be64w((uint64_t*)data, table_offset); 571 cpu_to_be32w((uint32_t*)(data + 8), table_clusters); 572 BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_SWITCH_TABLE); 573 ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, refcount_table_offset), 574 data, sizeof(data)); 575 if (ret < 0) { 576 goto fail_table; 577 } 578 579 /* And switch it in memory */ 580 uint64_t old_table_offset = s->refcount_table_offset; 581 uint64_t old_table_size = s->refcount_table_size; 582 583 g_free(s->refcount_table); 584 s->refcount_table = new_table; 585 s->refcount_table_size = table_size; 586 s->refcount_table_offset = table_offset; 587 588 /* Free old table. */ 589 qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t), 590 QCOW2_DISCARD_OTHER); 591 592 ret = load_refcount_block(bs, new_block, refcount_block); 593 if (ret < 0) { 594 return ret; 595 } 596 597 /* If we were trying to do the initial refcount update for some cluster 598 * allocation, we might have used the same clusters to store newly 599 * allocated metadata. Make the caller search some new space. */ 600 return -EAGAIN; 601 602 fail_table: 603 g_free(new_blocks); 604 g_free(new_table); 605 fail_block: 606 if (*refcount_block != NULL) { 607 qcow2_cache_put(bs, s->refcount_block_cache, refcount_block); 608 } 609 return ret; 610 } 611 612 void qcow2_process_discards(BlockDriverState *bs, int ret) 613 { 614 BDRVQcowState *s = bs->opaque; 615 Qcow2DiscardRegion *d, *next; 616 617 QTAILQ_FOREACH_SAFE(d, &s->discards, next, next) { 618 QTAILQ_REMOVE(&s->discards, d, next); 619 620 /* Discard is optional, ignore the return value */ 621 if (ret >= 0) { 622 bdrv_discard(bs->file, 623 d->offset >> BDRV_SECTOR_BITS, 624 d->bytes >> BDRV_SECTOR_BITS); 625 } 626 627 g_free(d); 628 } 629 } 630 631 static void update_refcount_discard(BlockDriverState *bs, 632 uint64_t offset, uint64_t length) 633 { 634 BDRVQcowState *s = bs->opaque; 635 Qcow2DiscardRegion *d, *p, *next; 636 637 QTAILQ_FOREACH(d, &s->discards, next) { 638 uint64_t new_start = MIN(offset, d->offset); 639 uint64_t new_end = MAX(offset + length, d->offset + d->bytes); 640 641 if (new_end - new_start <= length + d->bytes) { 642 /* There can't be any overlap, areas ending up here have no 643 * references any more and therefore shouldn't get freed another 644 * time. */ 645 assert(d->bytes + length == new_end - new_start); 646 d->offset = new_start; 647 d->bytes = new_end - new_start; 648 goto found; 649 } 650 } 651 652 d = g_malloc(sizeof(*d)); 653 *d = (Qcow2DiscardRegion) { 654 .bs = bs, 655 .offset = offset, 656 .bytes = length, 657 }; 658 QTAILQ_INSERT_TAIL(&s->discards, d, next); 659 660 found: 661 /* Merge discard requests if they are adjacent now */ 662 QTAILQ_FOREACH_SAFE(p, &s->discards, next, next) { 663 if (p == d 664 || p->offset > d->offset + d->bytes 665 || d->offset > p->offset + p->bytes) 666 { 667 continue; 668 } 669 670 /* Still no overlap possible */ 671 assert(p->offset == d->offset + d->bytes 672 || d->offset == p->offset + p->bytes); 673 674 QTAILQ_REMOVE(&s->discards, p, next); 675 d->offset = MIN(d->offset, p->offset); 676 d->bytes += p->bytes; 677 g_free(p); 678 } 679 } 680 681 /* XXX: cache several refcount block clusters ? */ 682 /* @addend is the absolute value of the addend; if @decrease is set, @addend 683 * will be subtracted from the current refcount, otherwise it will be added */ 684 static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs, 685 int64_t offset, 686 int64_t length, 687 uint64_t addend, 688 bool decrease, 689 enum qcow2_discard_type type) 690 { 691 BDRVQcowState *s = bs->opaque; 692 int64_t start, last, cluster_offset; 693 void *refcount_block = NULL; 694 int64_t old_table_index = -1; 695 int ret; 696 697 #ifdef DEBUG_ALLOC2 698 fprintf(stderr, "update_refcount: offset=%" PRId64 " size=%" PRId64 699 " addend=%s%" PRIu64 "\n", offset, length, decrease ? "-" : "", 700 addend); 701 #endif 702 if (length < 0) { 703 return -EINVAL; 704 } else if (length == 0) { 705 return 0; 706 } 707 708 if (decrease) { 709 qcow2_cache_set_dependency(bs, s->refcount_block_cache, 710 s->l2_table_cache); 711 } 712 713 start = start_of_cluster(s, offset); 714 last = start_of_cluster(s, offset + length - 1); 715 for(cluster_offset = start; cluster_offset <= last; 716 cluster_offset += s->cluster_size) 717 { 718 int block_index; 719 uint64_t refcount; 720 int64_t cluster_index = cluster_offset >> s->cluster_bits; 721 int64_t table_index = cluster_index >> s->refcount_block_bits; 722 723 /* Load the refcount block and allocate it if needed */ 724 if (table_index != old_table_index) { 725 if (refcount_block) { 726 ret = qcow2_cache_put(bs, s->refcount_block_cache, 727 &refcount_block); 728 if (ret < 0) { 729 goto fail; 730 } 731 } 732 733 ret = alloc_refcount_block(bs, cluster_index, &refcount_block); 734 if (ret < 0) { 735 goto fail; 736 } 737 } 738 old_table_index = table_index; 739 740 qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block); 741 742 /* we can update the count and save it */ 743 block_index = cluster_index & (s->refcount_block_size - 1); 744 745 refcount = s->get_refcount(refcount_block, block_index); 746 if (decrease ? (refcount - addend > refcount) 747 : (refcount + addend < refcount || 748 refcount + addend > s->refcount_max)) 749 { 750 ret = -EINVAL; 751 goto fail; 752 } 753 if (decrease) { 754 refcount -= addend; 755 } else { 756 refcount += addend; 757 } 758 if (refcount == 0 && cluster_index < s->free_cluster_index) { 759 s->free_cluster_index = cluster_index; 760 } 761 s->set_refcount(refcount_block, block_index, refcount); 762 763 if (refcount == 0 && s->discard_passthrough[type]) { 764 update_refcount_discard(bs, cluster_offset, s->cluster_size); 765 } 766 } 767 768 ret = 0; 769 fail: 770 if (!s->cache_discards) { 771 qcow2_process_discards(bs, ret); 772 } 773 774 /* Write last changed block to disk */ 775 if (refcount_block) { 776 int wret; 777 wret = qcow2_cache_put(bs, s->refcount_block_cache, &refcount_block); 778 if (wret < 0) { 779 return ret < 0 ? ret : wret; 780 } 781 } 782 783 /* 784 * Try do undo any updates if an error is returned (This may succeed in 785 * some cases like ENOSPC for allocating a new refcount block) 786 */ 787 if (ret < 0) { 788 int dummy; 789 dummy = update_refcount(bs, offset, cluster_offset - offset, addend, 790 !decrease, QCOW2_DISCARD_NEVER); 791 (void)dummy; 792 } 793 794 return ret; 795 } 796 797 /* 798 * Increases or decreases the refcount of a given cluster. 799 * 800 * @addend is the absolute value of the addend; if @decrease is set, @addend 801 * will be subtracted from the current refcount, otherwise it will be added. 802 * 803 * On success 0 is returned; on failure -errno is returned. 804 */ 805 int qcow2_update_cluster_refcount(BlockDriverState *bs, 806 int64_t cluster_index, 807 uint64_t addend, bool decrease, 808 enum qcow2_discard_type type) 809 { 810 BDRVQcowState *s = bs->opaque; 811 int ret; 812 813 ret = update_refcount(bs, cluster_index << s->cluster_bits, 1, addend, 814 decrease, type); 815 if (ret < 0) { 816 return ret; 817 } 818 819 return 0; 820 } 821 822 823 824 /*********************************************************/ 825 /* cluster allocation functions */ 826 827 828 829 /* return < 0 if error */ 830 static int64_t alloc_clusters_noref(BlockDriverState *bs, uint64_t size) 831 { 832 BDRVQcowState *s = bs->opaque; 833 uint64_t i, nb_clusters, refcount; 834 int ret; 835 836 nb_clusters = size_to_clusters(s, size); 837 retry: 838 for(i = 0; i < nb_clusters; i++) { 839 uint64_t next_cluster_index = s->free_cluster_index++; 840 ret = qcow2_get_refcount(bs, next_cluster_index, &refcount); 841 842 if (ret < 0) { 843 return ret; 844 } else if (refcount != 0) { 845 goto retry; 846 } 847 } 848 849 /* Make sure that all offsets in the "allocated" range are representable 850 * in an int64_t */ 851 if (s->free_cluster_index > 0 && 852 s->free_cluster_index - 1 > (INT64_MAX >> s->cluster_bits)) 853 { 854 return -EFBIG; 855 } 856 857 #ifdef DEBUG_ALLOC2 858 fprintf(stderr, "alloc_clusters: size=%" PRId64 " -> %" PRId64 "\n", 859 size, 860 (s->free_cluster_index - nb_clusters) << s->cluster_bits); 861 #endif 862 return (s->free_cluster_index - nb_clusters) << s->cluster_bits; 863 } 864 865 int64_t qcow2_alloc_clusters(BlockDriverState *bs, uint64_t size) 866 { 867 int64_t offset; 868 int ret; 869 870 BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC); 871 do { 872 offset = alloc_clusters_noref(bs, size); 873 if (offset < 0) { 874 return offset; 875 } 876 877 ret = update_refcount(bs, offset, size, 1, false, QCOW2_DISCARD_NEVER); 878 } while (ret == -EAGAIN); 879 880 if (ret < 0) { 881 return ret; 882 } 883 884 return offset; 885 } 886 887 int qcow2_alloc_clusters_at(BlockDriverState *bs, uint64_t offset, 888 int nb_clusters) 889 { 890 BDRVQcowState *s = bs->opaque; 891 uint64_t cluster_index, refcount; 892 uint64_t i; 893 int ret; 894 895 assert(nb_clusters >= 0); 896 if (nb_clusters == 0) { 897 return 0; 898 } 899 900 do { 901 /* Check how many clusters there are free */ 902 cluster_index = offset >> s->cluster_bits; 903 for(i = 0; i < nb_clusters; i++) { 904 ret = qcow2_get_refcount(bs, cluster_index++, &refcount); 905 if (ret < 0) { 906 return ret; 907 } else if (refcount != 0) { 908 break; 909 } 910 } 911 912 /* And then allocate them */ 913 ret = update_refcount(bs, offset, i << s->cluster_bits, 1, false, 914 QCOW2_DISCARD_NEVER); 915 } while (ret == -EAGAIN); 916 917 if (ret < 0) { 918 return ret; 919 } 920 921 return i; 922 } 923 924 /* only used to allocate compressed sectors. We try to allocate 925 contiguous sectors. size must be <= cluster_size */ 926 int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size) 927 { 928 BDRVQcowState *s = bs->opaque; 929 int64_t offset; 930 size_t free_in_cluster; 931 int ret; 932 933 BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC_BYTES); 934 assert(size > 0 && size <= s->cluster_size); 935 assert(!s->free_byte_offset || offset_into_cluster(s, s->free_byte_offset)); 936 937 offset = s->free_byte_offset; 938 939 if (offset) { 940 uint64_t refcount; 941 ret = qcow2_get_refcount(bs, offset >> s->cluster_bits, &refcount); 942 if (ret < 0) { 943 return ret; 944 } 945 946 if (refcount == s->refcount_max) { 947 offset = 0; 948 } 949 } 950 951 free_in_cluster = s->cluster_size - offset_into_cluster(s, offset); 952 if (!offset || free_in_cluster < size) { 953 int64_t new_cluster = alloc_clusters_noref(bs, s->cluster_size); 954 if (new_cluster < 0) { 955 return new_cluster; 956 } 957 958 if (!offset || ROUND_UP(offset, s->cluster_size) != new_cluster) { 959 offset = new_cluster; 960 } 961 } 962 963 assert(offset); 964 ret = update_refcount(bs, offset, size, 1, false, QCOW2_DISCARD_NEVER); 965 if (ret < 0) { 966 return ret; 967 } 968 969 /* The cluster refcount was incremented; refcount blocks must be flushed 970 * before the caller's L2 table updates. */ 971 qcow2_cache_set_dependency(bs, s->l2_table_cache, s->refcount_block_cache); 972 973 s->free_byte_offset = offset + size; 974 if (!offset_into_cluster(s, s->free_byte_offset)) { 975 s->free_byte_offset = 0; 976 } 977 978 return offset; 979 } 980 981 void qcow2_free_clusters(BlockDriverState *bs, 982 int64_t offset, int64_t size, 983 enum qcow2_discard_type type) 984 { 985 int ret; 986 987 BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE); 988 ret = update_refcount(bs, offset, size, 1, true, type); 989 if (ret < 0) { 990 fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret)); 991 /* TODO Remember the clusters to free them later and avoid leaking */ 992 } 993 } 994 995 /* 996 * Free a cluster using its L2 entry (handles clusters of all types, e.g. 997 * normal cluster, compressed cluster, etc.) 998 */ 999 void qcow2_free_any_clusters(BlockDriverState *bs, uint64_t l2_entry, 1000 int nb_clusters, enum qcow2_discard_type type) 1001 { 1002 BDRVQcowState *s = bs->opaque; 1003 1004 switch (qcow2_get_cluster_type(l2_entry)) { 1005 case QCOW2_CLUSTER_COMPRESSED: 1006 { 1007 int nb_csectors; 1008 nb_csectors = ((l2_entry >> s->csize_shift) & 1009 s->csize_mask) + 1; 1010 qcow2_free_clusters(bs, 1011 (l2_entry & s->cluster_offset_mask) & ~511, 1012 nb_csectors * 512, type); 1013 } 1014 break; 1015 case QCOW2_CLUSTER_NORMAL: 1016 case QCOW2_CLUSTER_ZERO: 1017 if (l2_entry & L2E_OFFSET_MASK) { 1018 if (offset_into_cluster(s, l2_entry & L2E_OFFSET_MASK)) { 1019 qcow2_signal_corruption(bs, false, -1, -1, 1020 "Cannot free unaligned cluster %#llx", 1021 l2_entry & L2E_OFFSET_MASK); 1022 } else { 1023 qcow2_free_clusters(bs, l2_entry & L2E_OFFSET_MASK, 1024 nb_clusters << s->cluster_bits, type); 1025 } 1026 } 1027 break; 1028 case QCOW2_CLUSTER_UNALLOCATED: 1029 break; 1030 default: 1031 abort(); 1032 } 1033 } 1034 1035 1036 1037 /*********************************************************/ 1038 /* snapshots and image creation */ 1039 1040 1041 1042 /* update the refcounts of snapshots and the copied flag */ 1043 int qcow2_update_snapshot_refcount(BlockDriverState *bs, 1044 int64_t l1_table_offset, int l1_size, int addend) 1045 { 1046 BDRVQcowState *s = bs->opaque; 1047 uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, refcount; 1048 bool l1_allocated = false; 1049 int64_t old_offset, old_l2_offset; 1050 int i, j, l1_modified = 0, nb_csectors; 1051 int ret; 1052 1053 assert(addend >= -1 && addend <= 1); 1054 1055 l2_table = NULL; 1056 l1_table = NULL; 1057 l1_size2 = l1_size * sizeof(uint64_t); 1058 1059 s->cache_discards = true; 1060 1061 /* WARNING: qcow2_snapshot_goto relies on this function not using the 1062 * l1_table_offset when it is the current s->l1_table_offset! Be careful 1063 * when changing this! */ 1064 if (l1_table_offset != s->l1_table_offset) { 1065 l1_table = g_try_malloc0(align_offset(l1_size2, 512)); 1066 if (l1_size2 && l1_table == NULL) { 1067 ret = -ENOMEM; 1068 goto fail; 1069 } 1070 l1_allocated = true; 1071 1072 ret = bdrv_pread(bs->file, l1_table_offset, l1_table, l1_size2); 1073 if (ret < 0) { 1074 goto fail; 1075 } 1076 1077 for(i = 0;i < l1_size; i++) 1078 be64_to_cpus(&l1_table[i]); 1079 } else { 1080 assert(l1_size == s->l1_size); 1081 l1_table = s->l1_table; 1082 l1_allocated = false; 1083 } 1084 1085 for(i = 0; i < l1_size; i++) { 1086 l2_offset = l1_table[i]; 1087 if (l2_offset) { 1088 old_l2_offset = l2_offset; 1089 l2_offset &= L1E_OFFSET_MASK; 1090 1091 if (offset_into_cluster(s, l2_offset)) { 1092 qcow2_signal_corruption(bs, true, -1, -1, "L2 table offset %#" 1093 PRIx64 " unaligned (L1 index: %#x)", 1094 l2_offset, i); 1095 ret = -EIO; 1096 goto fail; 1097 } 1098 1099 ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset, 1100 (void**) &l2_table); 1101 if (ret < 0) { 1102 goto fail; 1103 } 1104 1105 for(j = 0; j < s->l2_size; j++) { 1106 uint64_t cluster_index; 1107 1108 offset = be64_to_cpu(l2_table[j]); 1109 old_offset = offset; 1110 offset &= ~QCOW_OFLAG_COPIED; 1111 1112 switch (qcow2_get_cluster_type(offset)) { 1113 case QCOW2_CLUSTER_COMPRESSED: 1114 nb_csectors = ((offset >> s->csize_shift) & 1115 s->csize_mask) + 1; 1116 if (addend != 0) { 1117 ret = update_refcount(bs, 1118 (offset & s->cluster_offset_mask) & ~511, 1119 nb_csectors * 512, abs(addend), addend < 0, 1120 QCOW2_DISCARD_SNAPSHOT); 1121 if (ret < 0) { 1122 goto fail; 1123 } 1124 } 1125 /* compressed clusters are never modified */ 1126 refcount = 2; 1127 break; 1128 1129 case QCOW2_CLUSTER_NORMAL: 1130 case QCOW2_CLUSTER_ZERO: 1131 if (offset_into_cluster(s, offset & L2E_OFFSET_MASK)) { 1132 qcow2_signal_corruption(bs, true, -1, -1, "Data " 1133 "cluster offset %#llx " 1134 "unaligned (L2 offset: %#" 1135 PRIx64 ", L2 index: %#x)", 1136 offset & L2E_OFFSET_MASK, 1137 l2_offset, j); 1138 ret = -EIO; 1139 goto fail; 1140 } 1141 1142 cluster_index = (offset & L2E_OFFSET_MASK) >> s->cluster_bits; 1143 if (!cluster_index) { 1144 /* unallocated */ 1145 refcount = 0; 1146 break; 1147 } 1148 if (addend != 0) { 1149 ret = qcow2_update_cluster_refcount(bs, 1150 cluster_index, abs(addend), addend < 0, 1151 QCOW2_DISCARD_SNAPSHOT); 1152 if (ret < 0) { 1153 goto fail; 1154 } 1155 } 1156 1157 ret = qcow2_get_refcount(bs, cluster_index, &refcount); 1158 if (ret < 0) { 1159 goto fail; 1160 } 1161 break; 1162 1163 case QCOW2_CLUSTER_UNALLOCATED: 1164 refcount = 0; 1165 break; 1166 1167 default: 1168 abort(); 1169 } 1170 1171 if (refcount == 1) { 1172 offset |= QCOW_OFLAG_COPIED; 1173 } 1174 if (offset != old_offset) { 1175 if (addend > 0) { 1176 qcow2_cache_set_dependency(bs, s->l2_table_cache, 1177 s->refcount_block_cache); 1178 } 1179 l2_table[j] = cpu_to_be64(offset); 1180 qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table); 1181 } 1182 } 1183 1184 ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table); 1185 if (ret < 0) { 1186 goto fail; 1187 } 1188 1189 1190 if (addend != 0) { 1191 ret = qcow2_update_cluster_refcount(bs, l2_offset >> 1192 s->cluster_bits, 1193 abs(addend), addend < 0, 1194 QCOW2_DISCARD_SNAPSHOT); 1195 if (ret < 0) { 1196 goto fail; 1197 } 1198 } 1199 ret = qcow2_get_refcount(bs, l2_offset >> s->cluster_bits, 1200 &refcount); 1201 if (ret < 0) { 1202 goto fail; 1203 } else if (refcount == 1) { 1204 l2_offset |= QCOW_OFLAG_COPIED; 1205 } 1206 if (l2_offset != old_l2_offset) { 1207 l1_table[i] = l2_offset; 1208 l1_modified = 1; 1209 } 1210 } 1211 } 1212 1213 ret = bdrv_flush(bs); 1214 fail: 1215 if (l2_table) { 1216 qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table); 1217 } 1218 1219 s->cache_discards = false; 1220 qcow2_process_discards(bs, ret); 1221 1222 /* Update L1 only if it isn't deleted anyway (addend = -1) */ 1223 if (ret == 0 && addend >= 0 && l1_modified) { 1224 for (i = 0; i < l1_size; i++) { 1225 cpu_to_be64s(&l1_table[i]); 1226 } 1227 1228 ret = bdrv_pwrite_sync(bs->file, l1_table_offset, l1_table, l1_size2); 1229 1230 for (i = 0; i < l1_size; i++) { 1231 be64_to_cpus(&l1_table[i]); 1232 } 1233 } 1234 if (l1_allocated) 1235 g_free(l1_table); 1236 return ret; 1237 } 1238 1239 1240 1241 1242 /*********************************************************/ 1243 /* refcount checking functions */ 1244 1245 1246 static size_t refcount_array_byte_size(BDRVQcowState *s, uint64_t entries) 1247 { 1248 /* This assertion holds because there is no way we can address more than 1249 * 2^(64 - 9) clusters at once (with cluster size 512 = 2^9, and because 1250 * offsets have to be representable in bytes); due to every cluster 1251 * corresponding to one refcount entry, we are well below that limit */ 1252 assert(entries < (UINT64_C(1) << (64 - 9))); 1253 1254 /* Thanks to the assertion this will not overflow, because 1255 * s->refcount_order < 7. 1256 * (note: x << s->refcount_order == x * s->refcount_bits) */ 1257 return DIV_ROUND_UP(entries << s->refcount_order, 8); 1258 } 1259 1260 /** 1261 * Reallocates *array so that it can hold new_size entries. *size must contain 1262 * the current number of entries in *array. If the reallocation fails, *array 1263 * and *size will not be modified and -errno will be returned. If the 1264 * reallocation is successful, *array will be set to the new buffer, *size 1265 * will be set to new_size and 0 will be returned. The size of the reallocated 1266 * refcount array buffer will be aligned to a cluster boundary, and the newly 1267 * allocated area will be zeroed. 1268 */ 1269 static int realloc_refcount_array(BDRVQcowState *s, void **array, 1270 int64_t *size, int64_t new_size) 1271 { 1272 size_t old_byte_size, new_byte_size; 1273 void *new_ptr; 1274 1275 /* Round to clusters so the array can be directly written to disk */ 1276 old_byte_size = size_to_clusters(s, refcount_array_byte_size(s, *size)) 1277 * s->cluster_size; 1278 new_byte_size = size_to_clusters(s, refcount_array_byte_size(s, new_size)) 1279 * s->cluster_size; 1280 1281 if (new_byte_size == old_byte_size) { 1282 *size = new_size; 1283 return 0; 1284 } 1285 1286 assert(new_byte_size > 0); 1287 1288 new_ptr = g_try_realloc(*array, new_byte_size); 1289 if (!new_ptr) { 1290 return -ENOMEM; 1291 } 1292 1293 if (new_byte_size > old_byte_size) { 1294 memset((void *)((uintptr_t)new_ptr + old_byte_size), 0, 1295 new_byte_size - old_byte_size); 1296 } 1297 1298 *array = new_ptr; 1299 *size = new_size; 1300 1301 return 0; 1302 } 1303 1304 /* 1305 * Increases the refcount for a range of clusters in a given refcount table. 1306 * This is used to construct a temporary refcount table out of L1 and L2 tables 1307 * which can be compared the the refcount table saved in the image. 1308 * 1309 * Modifies the number of errors in res. 1310 */ 1311 static int inc_refcounts(BlockDriverState *bs, 1312 BdrvCheckResult *res, 1313 void **refcount_table, 1314 int64_t *refcount_table_size, 1315 int64_t offset, int64_t size) 1316 { 1317 BDRVQcowState *s = bs->opaque; 1318 uint64_t start, last, cluster_offset, k, refcount; 1319 int ret; 1320 1321 if (size <= 0) { 1322 return 0; 1323 } 1324 1325 start = start_of_cluster(s, offset); 1326 last = start_of_cluster(s, offset + size - 1); 1327 for(cluster_offset = start; cluster_offset <= last; 1328 cluster_offset += s->cluster_size) { 1329 k = cluster_offset >> s->cluster_bits; 1330 if (k >= *refcount_table_size) { 1331 ret = realloc_refcount_array(s, refcount_table, 1332 refcount_table_size, k + 1); 1333 if (ret < 0) { 1334 res->check_errors++; 1335 return ret; 1336 } 1337 } 1338 1339 refcount = s->get_refcount(*refcount_table, k); 1340 if (refcount == s->refcount_max) { 1341 fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64 1342 "\n", cluster_offset); 1343 res->corruptions++; 1344 continue; 1345 } 1346 s->set_refcount(*refcount_table, k, refcount + 1); 1347 } 1348 1349 return 0; 1350 } 1351 1352 /* Flags for check_refcounts_l1() and check_refcounts_l2() */ 1353 enum { 1354 CHECK_FRAG_INFO = 0x2, /* update BlockFragInfo counters */ 1355 }; 1356 1357 /* 1358 * Increases the refcount in the given refcount table for the all clusters 1359 * referenced in the L2 table. While doing so, performs some checks on L2 1360 * entries. 1361 * 1362 * Returns the number of errors found by the checks or -errno if an internal 1363 * error occurred. 1364 */ 1365 static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res, 1366 void **refcount_table, 1367 int64_t *refcount_table_size, int64_t l2_offset, 1368 int flags) 1369 { 1370 BDRVQcowState *s = bs->opaque; 1371 uint64_t *l2_table, l2_entry; 1372 uint64_t next_contiguous_offset = 0; 1373 int i, l2_size, nb_csectors, ret; 1374 1375 /* Read L2 table from disk */ 1376 l2_size = s->l2_size * sizeof(uint64_t); 1377 l2_table = g_malloc(l2_size); 1378 1379 ret = bdrv_pread(bs->file, l2_offset, l2_table, l2_size); 1380 if (ret < 0) { 1381 fprintf(stderr, "ERROR: I/O error in check_refcounts_l2\n"); 1382 res->check_errors++; 1383 goto fail; 1384 } 1385 1386 /* Do the actual checks */ 1387 for(i = 0; i < s->l2_size; i++) { 1388 l2_entry = be64_to_cpu(l2_table[i]); 1389 1390 switch (qcow2_get_cluster_type(l2_entry)) { 1391 case QCOW2_CLUSTER_COMPRESSED: 1392 /* Compressed clusters don't have QCOW_OFLAG_COPIED */ 1393 if (l2_entry & QCOW_OFLAG_COPIED) { 1394 fprintf(stderr, "ERROR: cluster %" PRId64 ": " 1395 "copied flag must never be set for compressed " 1396 "clusters\n", l2_entry >> s->cluster_bits); 1397 l2_entry &= ~QCOW_OFLAG_COPIED; 1398 res->corruptions++; 1399 } 1400 1401 /* Mark cluster as used */ 1402 nb_csectors = ((l2_entry >> s->csize_shift) & 1403 s->csize_mask) + 1; 1404 l2_entry &= s->cluster_offset_mask; 1405 ret = inc_refcounts(bs, res, refcount_table, refcount_table_size, 1406 l2_entry & ~511, nb_csectors * 512); 1407 if (ret < 0) { 1408 goto fail; 1409 } 1410 1411 if (flags & CHECK_FRAG_INFO) { 1412 res->bfi.allocated_clusters++; 1413 res->bfi.compressed_clusters++; 1414 1415 /* Compressed clusters are fragmented by nature. Since they 1416 * take up sub-sector space but we only have sector granularity 1417 * I/O we need to re-read the same sectors even for adjacent 1418 * compressed clusters. 1419 */ 1420 res->bfi.fragmented_clusters++; 1421 } 1422 break; 1423 1424 case QCOW2_CLUSTER_ZERO: 1425 if ((l2_entry & L2E_OFFSET_MASK) == 0) { 1426 break; 1427 } 1428 /* fall through */ 1429 1430 case QCOW2_CLUSTER_NORMAL: 1431 { 1432 uint64_t offset = l2_entry & L2E_OFFSET_MASK; 1433 1434 if (flags & CHECK_FRAG_INFO) { 1435 res->bfi.allocated_clusters++; 1436 if (next_contiguous_offset && 1437 offset != next_contiguous_offset) { 1438 res->bfi.fragmented_clusters++; 1439 } 1440 next_contiguous_offset = offset + s->cluster_size; 1441 } 1442 1443 /* Mark cluster as used */ 1444 ret = inc_refcounts(bs, res, refcount_table, refcount_table_size, 1445 offset, s->cluster_size); 1446 if (ret < 0) { 1447 goto fail; 1448 } 1449 1450 /* Correct offsets are cluster aligned */ 1451 if (offset_into_cluster(s, offset)) { 1452 fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not " 1453 "properly aligned; L2 entry corrupted.\n", offset); 1454 res->corruptions++; 1455 } 1456 break; 1457 } 1458 1459 case QCOW2_CLUSTER_UNALLOCATED: 1460 break; 1461 1462 default: 1463 abort(); 1464 } 1465 } 1466 1467 g_free(l2_table); 1468 return 0; 1469 1470 fail: 1471 g_free(l2_table); 1472 return ret; 1473 } 1474 1475 /* 1476 * Increases the refcount for the L1 table, its L2 tables and all referenced 1477 * clusters in the given refcount table. While doing so, performs some checks 1478 * on L1 and L2 entries. 1479 * 1480 * Returns the number of errors found by the checks or -errno if an internal 1481 * error occurred. 1482 */ 1483 static int check_refcounts_l1(BlockDriverState *bs, 1484 BdrvCheckResult *res, 1485 void **refcount_table, 1486 int64_t *refcount_table_size, 1487 int64_t l1_table_offset, int l1_size, 1488 int flags) 1489 { 1490 BDRVQcowState *s = bs->opaque; 1491 uint64_t *l1_table = NULL, l2_offset, l1_size2; 1492 int i, ret; 1493 1494 l1_size2 = l1_size * sizeof(uint64_t); 1495 1496 /* Mark L1 table as used */ 1497 ret = inc_refcounts(bs, res, refcount_table, refcount_table_size, 1498 l1_table_offset, l1_size2); 1499 if (ret < 0) { 1500 goto fail; 1501 } 1502 1503 /* Read L1 table entries from disk */ 1504 if (l1_size2 > 0) { 1505 l1_table = g_try_malloc(l1_size2); 1506 if (l1_table == NULL) { 1507 ret = -ENOMEM; 1508 res->check_errors++; 1509 goto fail; 1510 } 1511 ret = bdrv_pread(bs->file, l1_table_offset, l1_table, l1_size2); 1512 if (ret < 0) { 1513 fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n"); 1514 res->check_errors++; 1515 goto fail; 1516 } 1517 for(i = 0;i < l1_size; i++) 1518 be64_to_cpus(&l1_table[i]); 1519 } 1520 1521 /* Do the actual checks */ 1522 for(i = 0; i < l1_size; i++) { 1523 l2_offset = l1_table[i]; 1524 if (l2_offset) { 1525 /* Mark L2 table as used */ 1526 l2_offset &= L1E_OFFSET_MASK; 1527 ret = inc_refcounts(bs, res, refcount_table, refcount_table_size, 1528 l2_offset, s->cluster_size); 1529 if (ret < 0) { 1530 goto fail; 1531 } 1532 1533 /* L2 tables are cluster aligned */ 1534 if (offset_into_cluster(s, l2_offset)) { 1535 fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not " 1536 "cluster aligned; L1 entry corrupted\n", l2_offset); 1537 res->corruptions++; 1538 } 1539 1540 /* Process and check L2 entries */ 1541 ret = check_refcounts_l2(bs, res, refcount_table, 1542 refcount_table_size, l2_offset, flags); 1543 if (ret < 0) { 1544 goto fail; 1545 } 1546 } 1547 } 1548 g_free(l1_table); 1549 return 0; 1550 1551 fail: 1552 g_free(l1_table); 1553 return ret; 1554 } 1555 1556 /* 1557 * Checks the OFLAG_COPIED flag for all L1 and L2 entries. 1558 * 1559 * This function does not print an error message nor does it increment 1560 * check_errors if qcow2_get_refcount fails (this is because such an error will 1561 * have been already detected and sufficiently signaled by the calling function 1562 * (qcow2_check_refcounts) by the time this function is called). 1563 */ 1564 static int check_oflag_copied(BlockDriverState *bs, BdrvCheckResult *res, 1565 BdrvCheckMode fix) 1566 { 1567 BDRVQcowState *s = bs->opaque; 1568 uint64_t *l2_table = qemu_blockalign(bs, s->cluster_size); 1569 int ret; 1570 uint64_t refcount; 1571 int i, j; 1572 1573 for (i = 0; i < s->l1_size; i++) { 1574 uint64_t l1_entry = s->l1_table[i]; 1575 uint64_t l2_offset = l1_entry & L1E_OFFSET_MASK; 1576 bool l2_dirty = false; 1577 1578 if (!l2_offset) { 1579 continue; 1580 } 1581 1582 ret = qcow2_get_refcount(bs, l2_offset >> s->cluster_bits, 1583 &refcount); 1584 if (ret < 0) { 1585 /* don't print message nor increment check_errors */ 1586 continue; 1587 } 1588 if ((refcount == 1) != ((l1_entry & QCOW_OFLAG_COPIED) != 0)) { 1589 fprintf(stderr, "%s OFLAG_COPIED L2 cluster: l1_index=%d " 1590 "l1_entry=%" PRIx64 " refcount=%" PRIu64 "\n", 1591 fix & BDRV_FIX_ERRORS ? "Repairing" : 1592 "ERROR", 1593 i, l1_entry, refcount); 1594 if (fix & BDRV_FIX_ERRORS) { 1595 s->l1_table[i] = refcount == 1 1596 ? l1_entry | QCOW_OFLAG_COPIED 1597 : l1_entry & ~QCOW_OFLAG_COPIED; 1598 ret = qcow2_write_l1_entry(bs, i); 1599 if (ret < 0) { 1600 res->check_errors++; 1601 goto fail; 1602 } 1603 res->corruptions_fixed++; 1604 } else { 1605 res->corruptions++; 1606 } 1607 } 1608 1609 ret = bdrv_pread(bs->file, l2_offset, l2_table, 1610 s->l2_size * sizeof(uint64_t)); 1611 if (ret < 0) { 1612 fprintf(stderr, "ERROR: Could not read L2 table: %s\n", 1613 strerror(-ret)); 1614 res->check_errors++; 1615 goto fail; 1616 } 1617 1618 for (j = 0; j < s->l2_size; j++) { 1619 uint64_t l2_entry = be64_to_cpu(l2_table[j]); 1620 uint64_t data_offset = l2_entry & L2E_OFFSET_MASK; 1621 int cluster_type = qcow2_get_cluster_type(l2_entry); 1622 1623 if ((cluster_type == QCOW2_CLUSTER_NORMAL) || 1624 ((cluster_type == QCOW2_CLUSTER_ZERO) && (data_offset != 0))) { 1625 ret = qcow2_get_refcount(bs, 1626 data_offset >> s->cluster_bits, 1627 &refcount); 1628 if (ret < 0) { 1629 /* don't print message nor increment check_errors */ 1630 continue; 1631 } 1632 if ((refcount == 1) != ((l2_entry & QCOW_OFLAG_COPIED) != 0)) { 1633 fprintf(stderr, "%s OFLAG_COPIED data cluster: " 1634 "l2_entry=%" PRIx64 " refcount=%" PRIu64 "\n", 1635 fix & BDRV_FIX_ERRORS ? "Repairing" : 1636 "ERROR", 1637 l2_entry, refcount); 1638 if (fix & BDRV_FIX_ERRORS) { 1639 l2_table[j] = cpu_to_be64(refcount == 1 1640 ? l2_entry | QCOW_OFLAG_COPIED 1641 : l2_entry & ~QCOW_OFLAG_COPIED); 1642 l2_dirty = true; 1643 res->corruptions_fixed++; 1644 } else { 1645 res->corruptions++; 1646 } 1647 } 1648 } 1649 } 1650 1651 if (l2_dirty) { 1652 ret = qcow2_pre_write_overlap_check(bs, QCOW2_OL_ACTIVE_L2, 1653 l2_offset, s->cluster_size); 1654 if (ret < 0) { 1655 fprintf(stderr, "ERROR: Could not write L2 table; metadata " 1656 "overlap check failed: %s\n", strerror(-ret)); 1657 res->check_errors++; 1658 goto fail; 1659 } 1660 1661 ret = bdrv_pwrite(bs->file, l2_offset, l2_table, s->cluster_size); 1662 if (ret < 0) { 1663 fprintf(stderr, "ERROR: Could not write L2 table: %s\n", 1664 strerror(-ret)); 1665 res->check_errors++; 1666 goto fail; 1667 } 1668 } 1669 } 1670 1671 ret = 0; 1672 1673 fail: 1674 qemu_vfree(l2_table); 1675 return ret; 1676 } 1677 1678 /* 1679 * Checks consistency of refblocks and accounts for each refblock in 1680 * *refcount_table. 1681 */ 1682 static int check_refblocks(BlockDriverState *bs, BdrvCheckResult *res, 1683 BdrvCheckMode fix, bool *rebuild, 1684 void **refcount_table, int64_t *nb_clusters) 1685 { 1686 BDRVQcowState *s = bs->opaque; 1687 int64_t i, size; 1688 int ret; 1689 1690 for(i = 0; i < s->refcount_table_size; i++) { 1691 uint64_t offset, cluster; 1692 offset = s->refcount_table[i]; 1693 cluster = offset >> s->cluster_bits; 1694 1695 /* Refcount blocks are cluster aligned */ 1696 if (offset_into_cluster(s, offset)) { 1697 fprintf(stderr, "ERROR refcount block %" PRId64 " is not " 1698 "cluster aligned; refcount table entry corrupted\n", i); 1699 res->corruptions++; 1700 *rebuild = true; 1701 continue; 1702 } 1703 1704 if (cluster >= *nb_clusters) { 1705 fprintf(stderr, "%s refcount block %" PRId64 " is outside image\n", 1706 fix & BDRV_FIX_ERRORS ? "Repairing" : "ERROR", i); 1707 1708 if (fix & BDRV_FIX_ERRORS) { 1709 int64_t new_nb_clusters; 1710 1711 if (offset > INT64_MAX - s->cluster_size) { 1712 ret = -EINVAL; 1713 goto resize_fail; 1714 } 1715 1716 ret = bdrv_truncate(bs->file, offset + s->cluster_size); 1717 if (ret < 0) { 1718 goto resize_fail; 1719 } 1720 size = bdrv_getlength(bs->file); 1721 if (size < 0) { 1722 ret = size; 1723 goto resize_fail; 1724 } 1725 1726 new_nb_clusters = size_to_clusters(s, size); 1727 assert(new_nb_clusters >= *nb_clusters); 1728 1729 ret = realloc_refcount_array(s, refcount_table, 1730 nb_clusters, new_nb_clusters); 1731 if (ret < 0) { 1732 res->check_errors++; 1733 return ret; 1734 } 1735 1736 if (cluster >= *nb_clusters) { 1737 ret = -EINVAL; 1738 goto resize_fail; 1739 } 1740 1741 res->corruptions_fixed++; 1742 ret = inc_refcounts(bs, res, refcount_table, nb_clusters, 1743 offset, s->cluster_size); 1744 if (ret < 0) { 1745 return ret; 1746 } 1747 /* No need to check whether the refcount is now greater than 1: 1748 * This area was just allocated and zeroed, so it can only be 1749 * exactly 1 after inc_refcounts() */ 1750 continue; 1751 1752 resize_fail: 1753 res->corruptions++; 1754 *rebuild = true; 1755 fprintf(stderr, "ERROR could not resize image: %s\n", 1756 strerror(-ret)); 1757 } else { 1758 res->corruptions++; 1759 } 1760 continue; 1761 } 1762 1763 if (offset != 0) { 1764 ret = inc_refcounts(bs, res, refcount_table, nb_clusters, 1765 offset, s->cluster_size); 1766 if (ret < 0) { 1767 return ret; 1768 } 1769 if (s->get_refcount(*refcount_table, cluster) != 1) { 1770 fprintf(stderr, "ERROR refcount block %" PRId64 1771 " refcount=%" PRIu64 "\n", i, 1772 s->get_refcount(*refcount_table, cluster)); 1773 res->corruptions++; 1774 *rebuild = true; 1775 } 1776 } 1777 } 1778 1779 return 0; 1780 } 1781 1782 /* 1783 * Calculates an in-memory refcount table. 1784 */ 1785 static int calculate_refcounts(BlockDriverState *bs, BdrvCheckResult *res, 1786 BdrvCheckMode fix, bool *rebuild, 1787 void **refcount_table, int64_t *nb_clusters) 1788 { 1789 BDRVQcowState *s = bs->opaque; 1790 int64_t i; 1791 QCowSnapshot *sn; 1792 int ret; 1793 1794 if (!*refcount_table) { 1795 int64_t old_size = 0; 1796 ret = realloc_refcount_array(s, refcount_table, 1797 &old_size, *nb_clusters); 1798 if (ret < 0) { 1799 res->check_errors++; 1800 return ret; 1801 } 1802 } 1803 1804 /* header */ 1805 ret = inc_refcounts(bs, res, refcount_table, nb_clusters, 1806 0, s->cluster_size); 1807 if (ret < 0) { 1808 return ret; 1809 } 1810 1811 /* current L1 table */ 1812 ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters, 1813 s->l1_table_offset, s->l1_size, CHECK_FRAG_INFO); 1814 if (ret < 0) { 1815 return ret; 1816 } 1817 1818 /* snapshots */ 1819 for (i = 0; i < s->nb_snapshots; i++) { 1820 sn = s->snapshots + i; 1821 ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters, 1822 sn->l1_table_offset, sn->l1_size, 0); 1823 if (ret < 0) { 1824 return ret; 1825 } 1826 } 1827 ret = inc_refcounts(bs, res, refcount_table, nb_clusters, 1828 s->snapshots_offset, s->snapshots_size); 1829 if (ret < 0) { 1830 return ret; 1831 } 1832 1833 /* refcount data */ 1834 ret = inc_refcounts(bs, res, refcount_table, nb_clusters, 1835 s->refcount_table_offset, 1836 s->refcount_table_size * sizeof(uint64_t)); 1837 if (ret < 0) { 1838 return ret; 1839 } 1840 1841 return check_refblocks(bs, res, fix, rebuild, refcount_table, nb_clusters); 1842 } 1843 1844 /* 1845 * Compares the actual reference count for each cluster in the image against the 1846 * refcount as reported by the refcount structures on-disk. 1847 */ 1848 static void compare_refcounts(BlockDriverState *bs, BdrvCheckResult *res, 1849 BdrvCheckMode fix, bool *rebuild, 1850 int64_t *highest_cluster, 1851 void *refcount_table, int64_t nb_clusters) 1852 { 1853 BDRVQcowState *s = bs->opaque; 1854 int64_t i; 1855 uint64_t refcount1, refcount2; 1856 int ret; 1857 1858 for (i = 0, *highest_cluster = 0; i < nb_clusters; i++) { 1859 ret = qcow2_get_refcount(bs, i, &refcount1); 1860 if (ret < 0) { 1861 fprintf(stderr, "Can't get refcount for cluster %" PRId64 ": %s\n", 1862 i, strerror(-ret)); 1863 res->check_errors++; 1864 continue; 1865 } 1866 1867 refcount2 = s->get_refcount(refcount_table, i); 1868 1869 if (refcount1 > 0 || refcount2 > 0) { 1870 *highest_cluster = i; 1871 } 1872 1873 if (refcount1 != refcount2) { 1874 /* Check if we're allowed to fix the mismatch */ 1875 int *num_fixed = NULL; 1876 if (refcount1 == 0) { 1877 *rebuild = true; 1878 } else if (refcount1 > refcount2 && (fix & BDRV_FIX_LEAKS)) { 1879 num_fixed = &res->leaks_fixed; 1880 } else if (refcount1 < refcount2 && (fix & BDRV_FIX_ERRORS)) { 1881 num_fixed = &res->corruptions_fixed; 1882 } 1883 1884 fprintf(stderr, "%s cluster %" PRId64 " refcount=%" PRIu64 1885 " reference=%" PRIu64 "\n", 1886 num_fixed != NULL ? "Repairing" : 1887 refcount1 < refcount2 ? "ERROR" : 1888 "Leaked", 1889 i, refcount1, refcount2); 1890 1891 if (num_fixed) { 1892 ret = update_refcount(bs, i << s->cluster_bits, 1, 1893 refcount_diff(refcount1, refcount2), 1894 refcount1 > refcount2, 1895 QCOW2_DISCARD_ALWAYS); 1896 if (ret >= 0) { 1897 (*num_fixed)++; 1898 continue; 1899 } 1900 } 1901 1902 /* And if we couldn't, print an error */ 1903 if (refcount1 < refcount2) { 1904 res->corruptions++; 1905 } else { 1906 res->leaks++; 1907 } 1908 } 1909 } 1910 } 1911 1912 /* 1913 * Allocates clusters using an in-memory refcount table (IMRT) in contrast to 1914 * the on-disk refcount structures. 1915 * 1916 * On input, *first_free_cluster tells where to start looking, and need not 1917 * actually be a free cluster; the returned offset will not be before that 1918 * cluster. On output, *first_free_cluster points to the first gap found, even 1919 * if that gap was too small to be used as the returned offset. 1920 * 1921 * Note that *first_free_cluster is a cluster index whereas the return value is 1922 * an offset. 1923 */ 1924 static int64_t alloc_clusters_imrt(BlockDriverState *bs, 1925 int cluster_count, 1926 void **refcount_table, 1927 int64_t *imrt_nb_clusters, 1928 int64_t *first_free_cluster) 1929 { 1930 BDRVQcowState *s = bs->opaque; 1931 int64_t cluster = *first_free_cluster, i; 1932 bool first_gap = true; 1933 int contiguous_free_clusters; 1934 int ret; 1935 1936 /* Starting at *first_free_cluster, find a range of at least cluster_count 1937 * continuously free clusters */ 1938 for (contiguous_free_clusters = 0; 1939 cluster < *imrt_nb_clusters && 1940 contiguous_free_clusters < cluster_count; 1941 cluster++) 1942 { 1943 if (!s->get_refcount(*refcount_table, cluster)) { 1944 contiguous_free_clusters++; 1945 if (first_gap) { 1946 /* If this is the first free cluster found, update 1947 * *first_free_cluster accordingly */ 1948 *first_free_cluster = cluster; 1949 first_gap = false; 1950 } 1951 } else if (contiguous_free_clusters) { 1952 contiguous_free_clusters = 0; 1953 } 1954 } 1955 1956 /* If contiguous_free_clusters is greater than zero, it contains the number 1957 * of continuously free clusters until the current cluster; the first free 1958 * cluster in the current "gap" is therefore 1959 * cluster - contiguous_free_clusters */ 1960 1961 /* If no such range could be found, grow the in-memory refcount table 1962 * accordingly to append free clusters at the end of the image */ 1963 if (contiguous_free_clusters < cluster_count) { 1964 /* contiguous_free_clusters clusters are already empty at the image end; 1965 * we need cluster_count clusters; therefore, we have to allocate 1966 * cluster_count - contiguous_free_clusters new clusters at the end of 1967 * the image (which is the current value of cluster; note that cluster 1968 * may exceed old_imrt_nb_clusters if *first_free_cluster pointed beyond 1969 * the image end) */ 1970 ret = realloc_refcount_array(s, refcount_table, imrt_nb_clusters, 1971 cluster + cluster_count 1972 - contiguous_free_clusters); 1973 if (ret < 0) { 1974 return ret; 1975 } 1976 } 1977 1978 /* Go back to the first free cluster */ 1979 cluster -= contiguous_free_clusters; 1980 for (i = 0; i < cluster_count; i++) { 1981 s->set_refcount(*refcount_table, cluster + i, 1); 1982 } 1983 1984 return cluster << s->cluster_bits; 1985 } 1986 1987 /* 1988 * Creates a new refcount structure based solely on the in-memory information 1989 * given through *refcount_table. All necessary allocations will be reflected 1990 * in that array. 1991 * 1992 * On success, the old refcount structure is leaked (it will be covered by the 1993 * new refcount structure). 1994 */ 1995 static int rebuild_refcount_structure(BlockDriverState *bs, 1996 BdrvCheckResult *res, 1997 void **refcount_table, 1998 int64_t *nb_clusters) 1999 { 2000 BDRVQcowState *s = bs->opaque; 2001 int64_t first_free_cluster = 0, reftable_offset = -1, cluster = 0; 2002 int64_t refblock_offset, refblock_start, refblock_index; 2003 uint32_t reftable_size = 0; 2004 uint64_t *on_disk_reftable = NULL; 2005 void *on_disk_refblock; 2006 int ret = 0; 2007 struct { 2008 uint64_t reftable_offset; 2009 uint32_t reftable_clusters; 2010 } QEMU_PACKED reftable_offset_and_clusters; 2011 2012 qcow2_cache_empty(bs, s->refcount_block_cache); 2013 2014 write_refblocks: 2015 for (; cluster < *nb_clusters; cluster++) { 2016 if (!s->get_refcount(*refcount_table, cluster)) { 2017 continue; 2018 } 2019 2020 refblock_index = cluster >> s->refcount_block_bits; 2021 refblock_start = refblock_index << s->refcount_block_bits; 2022 2023 /* Don't allocate a cluster in a refblock already written to disk */ 2024 if (first_free_cluster < refblock_start) { 2025 first_free_cluster = refblock_start; 2026 } 2027 refblock_offset = alloc_clusters_imrt(bs, 1, refcount_table, 2028 nb_clusters, &first_free_cluster); 2029 if (refblock_offset < 0) { 2030 fprintf(stderr, "ERROR allocating refblock: %s\n", 2031 strerror(-refblock_offset)); 2032 res->check_errors++; 2033 ret = refblock_offset; 2034 goto fail; 2035 } 2036 2037 if (reftable_size <= refblock_index) { 2038 uint32_t old_reftable_size = reftable_size; 2039 uint64_t *new_on_disk_reftable; 2040 2041 reftable_size = ROUND_UP((refblock_index + 1) * sizeof(uint64_t), 2042 s->cluster_size) / sizeof(uint64_t); 2043 new_on_disk_reftable = g_try_realloc(on_disk_reftable, 2044 reftable_size * 2045 sizeof(uint64_t)); 2046 if (!new_on_disk_reftable) { 2047 res->check_errors++; 2048 ret = -ENOMEM; 2049 goto fail; 2050 } 2051 on_disk_reftable = new_on_disk_reftable; 2052 2053 memset(on_disk_reftable + old_reftable_size, 0, 2054 (reftable_size - old_reftable_size) * sizeof(uint64_t)); 2055 2056 /* The offset we have for the reftable is now no longer valid; 2057 * this will leak that range, but we can easily fix that by running 2058 * a leak-fixing check after this rebuild operation */ 2059 reftable_offset = -1; 2060 } 2061 on_disk_reftable[refblock_index] = refblock_offset; 2062 2063 /* If this is apparently the last refblock (for now), try to squeeze the 2064 * reftable in */ 2065 if (refblock_index == (*nb_clusters - 1) >> s->refcount_block_bits && 2066 reftable_offset < 0) 2067 { 2068 uint64_t reftable_clusters = size_to_clusters(s, reftable_size * 2069 sizeof(uint64_t)); 2070 reftable_offset = alloc_clusters_imrt(bs, reftable_clusters, 2071 refcount_table, nb_clusters, 2072 &first_free_cluster); 2073 if (reftable_offset < 0) { 2074 fprintf(stderr, "ERROR allocating reftable: %s\n", 2075 strerror(-reftable_offset)); 2076 res->check_errors++; 2077 ret = reftable_offset; 2078 goto fail; 2079 } 2080 } 2081 2082 ret = qcow2_pre_write_overlap_check(bs, 0, refblock_offset, 2083 s->cluster_size); 2084 if (ret < 0) { 2085 fprintf(stderr, "ERROR writing refblock: %s\n", strerror(-ret)); 2086 goto fail; 2087 } 2088 2089 /* The size of *refcount_table is always cluster-aligned, therefore the 2090 * write operation will not overflow */ 2091 on_disk_refblock = (void *)((char *) *refcount_table + 2092 refblock_index * s->cluster_size); 2093 2094 ret = bdrv_write(bs->file, refblock_offset / BDRV_SECTOR_SIZE, 2095 on_disk_refblock, s->cluster_sectors); 2096 if (ret < 0) { 2097 fprintf(stderr, "ERROR writing refblock: %s\n", strerror(-ret)); 2098 goto fail; 2099 } 2100 2101 /* Go to the end of this refblock */ 2102 cluster = refblock_start + s->refcount_block_size - 1; 2103 } 2104 2105 if (reftable_offset < 0) { 2106 uint64_t post_refblock_start, reftable_clusters; 2107 2108 post_refblock_start = ROUND_UP(*nb_clusters, s->refcount_block_size); 2109 reftable_clusters = size_to_clusters(s, 2110 reftable_size * sizeof(uint64_t)); 2111 /* Not pretty but simple */ 2112 if (first_free_cluster < post_refblock_start) { 2113 first_free_cluster = post_refblock_start; 2114 } 2115 reftable_offset = alloc_clusters_imrt(bs, reftable_clusters, 2116 refcount_table, nb_clusters, 2117 &first_free_cluster); 2118 if (reftable_offset < 0) { 2119 fprintf(stderr, "ERROR allocating reftable: %s\n", 2120 strerror(-reftable_offset)); 2121 res->check_errors++; 2122 ret = reftable_offset; 2123 goto fail; 2124 } 2125 2126 goto write_refblocks; 2127 } 2128 2129 assert(on_disk_reftable); 2130 2131 for (refblock_index = 0; refblock_index < reftable_size; refblock_index++) { 2132 cpu_to_be64s(&on_disk_reftable[refblock_index]); 2133 } 2134 2135 ret = qcow2_pre_write_overlap_check(bs, 0, reftable_offset, 2136 reftable_size * sizeof(uint64_t)); 2137 if (ret < 0) { 2138 fprintf(stderr, "ERROR writing reftable: %s\n", strerror(-ret)); 2139 goto fail; 2140 } 2141 2142 assert(reftable_size < INT_MAX / sizeof(uint64_t)); 2143 ret = bdrv_pwrite(bs->file, reftable_offset, on_disk_reftable, 2144 reftable_size * sizeof(uint64_t)); 2145 if (ret < 0) { 2146 fprintf(stderr, "ERROR writing reftable: %s\n", strerror(-ret)); 2147 goto fail; 2148 } 2149 2150 /* Enter new reftable into the image header */ 2151 cpu_to_be64w(&reftable_offset_and_clusters.reftable_offset, 2152 reftable_offset); 2153 cpu_to_be32w(&reftable_offset_and_clusters.reftable_clusters, 2154 size_to_clusters(s, reftable_size * sizeof(uint64_t))); 2155 ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, 2156 refcount_table_offset), 2157 &reftable_offset_and_clusters, 2158 sizeof(reftable_offset_and_clusters)); 2159 if (ret < 0) { 2160 fprintf(stderr, "ERROR setting reftable: %s\n", strerror(-ret)); 2161 goto fail; 2162 } 2163 2164 for (refblock_index = 0; refblock_index < reftable_size; refblock_index++) { 2165 be64_to_cpus(&on_disk_reftable[refblock_index]); 2166 } 2167 s->refcount_table = on_disk_reftable; 2168 s->refcount_table_offset = reftable_offset; 2169 s->refcount_table_size = reftable_size; 2170 2171 return 0; 2172 2173 fail: 2174 g_free(on_disk_reftable); 2175 return ret; 2176 } 2177 2178 /* 2179 * Checks an image for refcount consistency. 2180 * 2181 * Returns 0 if no errors are found, the number of errors in case the image is 2182 * detected as corrupted, and -errno when an internal error occurred. 2183 */ 2184 int qcow2_check_refcounts(BlockDriverState *bs, BdrvCheckResult *res, 2185 BdrvCheckMode fix) 2186 { 2187 BDRVQcowState *s = bs->opaque; 2188 BdrvCheckResult pre_compare_res; 2189 int64_t size, highest_cluster, nb_clusters; 2190 void *refcount_table = NULL; 2191 bool rebuild = false; 2192 int ret; 2193 2194 size = bdrv_getlength(bs->file); 2195 if (size < 0) { 2196 res->check_errors++; 2197 return size; 2198 } 2199 2200 nb_clusters = size_to_clusters(s, size); 2201 if (nb_clusters > INT_MAX) { 2202 res->check_errors++; 2203 return -EFBIG; 2204 } 2205 2206 res->bfi.total_clusters = 2207 size_to_clusters(s, bs->total_sectors * BDRV_SECTOR_SIZE); 2208 2209 ret = calculate_refcounts(bs, res, fix, &rebuild, &refcount_table, 2210 &nb_clusters); 2211 if (ret < 0) { 2212 goto fail; 2213 } 2214 2215 /* In case we don't need to rebuild the refcount structure (but want to fix 2216 * something), this function is immediately called again, in which case the 2217 * result should be ignored */ 2218 pre_compare_res = *res; 2219 compare_refcounts(bs, res, 0, &rebuild, &highest_cluster, refcount_table, 2220 nb_clusters); 2221 2222 if (rebuild && (fix & BDRV_FIX_ERRORS)) { 2223 BdrvCheckResult old_res = *res; 2224 int fresh_leaks = 0; 2225 2226 fprintf(stderr, "Rebuilding refcount structure\n"); 2227 ret = rebuild_refcount_structure(bs, res, &refcount_table, 2228 &nb_clusters); 2229 if (ret < 0) { 2230 goto fail; 2231 } 2232 2233 res->corruptions = 0; 2234 res->leaks = 0; 2235 2236 /* Because the old reftable has been exchanged for a new one the 2237 * references have to be recalculated */ 2238 rebuild = false; 2239 memset(refcount_table, 0, refcount_array_byte_size(s, nb_clusters)); 2240 ret = calculate_refcounts(bs, res, 0, &rebuild, &refcount_table, 2241 &nb_clusters); 2242 if (ret < 0) { 2243 goto fail; 2244 } 2245 2246 if (fix & BDRV_FIX_LEAKS) { 2247 /* The old refcount structures are now leaked, fix it; the result 2248 * can be ignored, aside from leaks which were introduced by 2249 * rebuild_refcount_structure() that could not be fixed */ 2250 BdrvCheckResult saved_res = *res; 2251 *res = (BdrvCheckResult){ 0 }; 2252 2253 compare_refcounts(bs, res, BDRV_FIX_LEAKS, &rebuild, 2254 &highest_cluster, refcount_table, nb_clusters); 2255 if (rebuild) { 2256 fprintf(stderr, "ERROR rebuilt refcount structure is still " 2257 "broken\n"); 2258 } 2259 2260 /* Any leaks accounted for here were introduced by 2261 * rebuild_refcount_structure() because that function has created a 2262 * new refcount structure from scratch */ 2263 fresh_leaks = res->leaks; 2264 *res = saved_res; 2265 } 2266 2267 if (res->corruptions < old_res.corruptions) { 2268 res->corruptions_fixed += old_res.corruptions - res->corruptions; 2269 } 2270 if (res->leaks < old_res.leaks) { 2271 res->leaks_fixed += old_res.leaks - res->leaks; 2272 } 2273 res->leaks += fresh_leaks; 2274 } else if (fix) { 2275 if (rebuild) { 2276 fprintf(stderr, "ERROR need to rebuild refcount structures\n"); 2277 res->check_errors++; 2278 ret = -EIO; 2279 goto fail; 2280 } 2281 2282 if (res->leaks || res->corruptions) { 2283 *res = pre_compare_res; 2284 compare_refcounts(bs, res, fix, &rebuild, &highest_cluster, 2285 refcount_table, nb_clusters); 2286 } 2287 } 2288 2289 /* check OFLAG_COPIED */ 2290 ret = check_oflag_copied(bs, res, fix); 2291 if (ret < 0) { 2292 goto fail; 2293 } 2294 2295 res->image_end_offset = (highest_cluster + 1) * s->cluster_size; 2296 ret = 0; 2297 2298 fail: 2299 g_free(refcount_table); 2300 2301 return ret; 2302 } 2303 2304 #define overlaps_with(ofs, sz) \ 2305 ranges_overlap(offset, size, ofs, sz) 2306 2307 /* 2308 * Checks if the given offset into the image file is actually free to use by 2309 * looking for overlaps with important metadata sections (L1/L2 tables etc.), 2310 * i.e. a sanity check without relying on the refcount tables. 2311 * 2312 * The ign parameter specifies what checks not to perform (being a bitmask of 2313 * QCow2MetadataOverlap values), i.e., what sections to ignore. 2314 * 2315 * Returns: 2316 * - 0 if writing to this offset will not affect the mentioned metadata 2317 * - a positive QCow2MetadataOverlap value indicating one overlapping section 2318 * - a negative value (-errno) indicating an error while performing a check, 2319 * e.g. when bdrv_read failed on QCOW2_OL_INACTIVE_L2 2320 */ 2321 int qcow2_check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset, 2322 int64_t size) 2323 { 2324 BDRVQcowState *s = bs->opaque; 2325 int chk = s->overlap_check & ~ign; 2326 int i, j; 2327 2328 if (!size) { 2329 return 0; 2330 } 2331 2332 if (chk & QCOW2_OL_MAIN_HEADER) { 2333 if (offset < s->cluster_size) { 2334 return QCOW2_OL_MAIN_HEADER; 2335 } 2336 } 2337 2338 /* align range to test to cluster boundaries */ 2339 size = align_offset(offset_into_cluster(s, offset) + size, s->cluster_size); 2340 offset = start_of_cluster(s, offset); 2341 2342 if ((chk & QCOW2_OL_ACTIVE_L1) && s->l1_size) { 2343 if (overlaps_with(s->l1_table_offset, s->l1_size * sizeof(uint64_t))) { 2344 return QCOW2_OL_ACTIVE_L1; 2345 } 2346 } 2347 2348 if ((chk & QCOW2_OL_REFCOUNT_TABLE) && s->refcount_table_size) { 2349 if (overlaps_with(s->refcount_table_offset, 2350 s->refcount_table_size * sizeof(uint64_t))) { 2351 return QCOW2_OL_REFCOUNT_TABLE; 2352 } 2353 } 2354 2355 if ((chk & QCOW2_OL_SNAPSHOT_TABLE) && s->snapshots_size) { 2356 if (overlaps_with(s->snapshots_offset, s->snapshots_size)) { 2357 return QCOW2_OL_SNAPSHOT_TABLE; 2358 } 2359 } 2360 2361 if ((chk & QCOW2_OL_INACTIVE_L1) && s->snapshots) { 2362 for (i = 0; i < s->nb_snapshots; i++) { 2363 if (s->snapshots[i].l1_size && 2364 overlaps_with(s->snapshots[i].l1_table_offset, 2365 s->snapshots[i].l1_size * sizeof(uint64_t))) { 2366 return QCOW2_OL_INACTIVE_L1; 2367 } 2368 } 2369 } 2370 2371 if ((chk & QCOW2_OL_ACTIVE_L2) && s->l1_table) { 2372 for (i = 0; i < s->l1_size; i++) { 2373 if ((s->l1_table[i] & L1E_OFFSET_MASK) && 2374 overlaps_with(s->l1_table[i] & L1E_OFFSET_MASK, 2375 s->cluster_size)) { 2376 return QCOW2_OL_ACTIVE_L2; 2377 } 2378 } 2379 } 2380 2381 if ((chk & QCOW2_OL_REFCOUNT_BLOCK) && s->refcount_table) { 2382 for (i = 0; i < s->refcount_table_size; i++) { 2383 if ((s->refcount_table[i] & REFT_OFFSET_MASK) && 2384 overlaps_with(s->refcount_table[i] & REFT_OFFSET_MASK, 2385 s->cluster_size)) { 2386 return QCOW2_OL_REFCOUNT_BLOCK; 2387 } 2388 } 2389 } 2390 2391 if ((chk & QCOW2_OL_INACTIVE_L2) && s->snapshots) { 2392 for (i = 0; i < s->nb_snapshots; i++) { 2393 uint64_t l1_ofs = s->snapshots[i].l1_table_offset; 2394 uint32_t l1_sz = s->snapshots[i].l1_size; 2395 uint64_t l1_sz2 = l1_sz * sizeof(uint64_t); 2396 uint64_t *l1 = g_try_malloc(l1_sz2); 2397 int ret; 2398 2399 if (l1_sz2 && l1 == NULL) { 2400 return -ENOMEM; 2401 } 2402 2403 ret = bdrv_pread(bs->file, l1_ofs, l1, l1_sz2); 2404 if (ret < 0) { 2405 g_free(l1); 2406 return ret; 2407 } 2408 2409 for (j = 0; j < l1_sz; j++) { 2410 uint64_t l2_ofs = be64_to_cpu(l1[j]) & L1E_OFFSET_MASK; 2411 if (l2_ofs && overlaps_with(l2_ofs, s->cluster_size)) { 2412 g_free(l1); 2413 return QCOW2_OL_INACTIVE_L2; 2414 } 2415 } 2416 2417 g_free(l1); 2418 } 2419 } 2420 2421 return 0; 2422 } 2423 2424 static const char *metadata_ol_names[] = { 2425 [QCOW2_OL_MAIN_HEADER_BITNR] = "qcow2_header", 2426 [QCOW2_OL_ACTIVE_L1_BITNR] = "active L1 table", 2427 [QCOW2_OL_ACTIVE_L2_BITNR] = "active L2 table", 2428 [QCOW2_OL_REFCOUNT_TABLE_BITNR] = "refcount table", 2429 [QCOW2_OL_REFCOUNT_BLOCK_BITNR] = "refcount block", 2430 [QCOW2_OL_SNAPSHOT_TABLE_BITNR] = "snapshot table", 2431 [QCOW2_OL_INACTIVE_L1_BITNR] = "inactive L1 table", 2432 [QCOW2_OL_INACTIVE_L2_BITNR] = "inactive L2 table", 2433 }; 2434 2435 /* 2436 * First performs a check for metadata overlaps (through 2437 * qcow2_check_metadata_overlap); if that fails with a negative value (error 2438 * while performing a check), that value is returned. If an impending overlap 2439 * is detected, the BDS will be made unusable, the qcow2 file marked corrupt 2440 * and -EIO returned. 2441 * 2442 * Returns 0 if there were neither overlaps nor errors while checking for 2443 * overlaps; or a negative value (-errno) on error. 2444 */ 2445 int qcow2_pre_write_overlap_check(BlockDriverState *bs, int ign, int64_t offset, 2446 int64_t size) 2447 { 2448 int ret = qcow2_check_metadata_overlap(bs, ign, offset, size); 2449 2450 if (ret < 0) { 2451 return ret; 2452 } else if (ret > 0) { 2453 int metadata_ol_bitnr = ffs(ret) - 1; 2454 assert(metadata_ol_bitnr < QCOW2_OL_MAX_BITNR); 2455 2456 qcow2_signal_corruption(bs, true, offset, size, "Preventing invalid " 2457 "write on metadata (overlaps with %s)", 2458 metadata_ol_names[metadata_ol_bitnr]); 2459 return -EIO; 2460 } 2461 2462 return 0; 2463 } 2464