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