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