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 <zlib.h> 26 27 #include "qemu-common.h" 28 #include "block/block_int.h" 29 #include "block/qcow2.h" 30 31 int qcow2_grow_l1_table(BlockDriverState *bs, int min_size) 32 { 33 BDRVQcowState *s = bs->opaque; 34 int new_l1_size, new_l1_size2, ret, i; 35 uint64_t *new_l1_table; 36 int64_t new_l1_table_offset; 37 uint8_t data[12]; 38 39 new_l1_size = s->l1_size; 40 if (min_size <= new_l1_size) 41 return 0; 42 if (new_l1_size == 0) { 43 new_l1_size = 1; 44 } 45 while (min_size > new_l1_size) { 46 new_l1_size = (new_l1_size * 3 + 1) / 2; 47 } 48 #ifdef DEBUG_ALLOC2 49 printf("grow l1_table from %d to %d\n", s->l1_size, new_l1_size); 50 #endif 51 52 new_l1_size2 = sizeof(uint64_t) * new_l1_size; 53 new_l1_table = g_malloc0(align_offset(new_l1_size2, 512)); 54 memcpy(new_l1_table, s->l1_table, s->l1_size * sizeof(uint64_t)); 55 56 /* write new table (align to cluster) */ 57 BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_ALLOC_TABLE); 58 new_l1_table_offset = qcow2_alloc_clusters(bs, new_l1_size2); 59 if (new_l1_table_offset < 0) { 60 g_free(new_l1_table); 61 return new_l1_table_offset; 62 } 63 64 BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_WRITE_TABLE); 65 for(i = 0; i < s->l1_size; i++) 66 new_l1_table[i] = cpu_to_be64(new_l1_table[i]); 67 ret = bdrv_pwrite_sync(bs->file, new_l1_table_offset, new_l1_table, new_l1_size2); 68 if (ret < 0) 69 goto fail; 70 for(i = 0; i < s->l1_size; i++) 71 new_l1_table[i] = be64_to_cpu(new_l1_table[i]); 72 73 /* set new table */ 74 BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_ACTIVATE_TABLE); 75 cpu_to_be32w((uint32_t*)data, new_l1_size); 76 cpu_to_be64w((uint64_t*)(data + 4), new_l1_table_offset); 77 ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, l1_size), data,sizeof(data)); 78 if (ret < 0) { 79 goto fail; 80 } 81 g_free(s->l1_table); 82 qcow2_free_clusters(bs, s->l1_table_offset, s->l1_size * sizeof(uint64_t)); 83 s->l1_table_offset = new_l1_table_offset; 84 s->l1_table = new_l1_table; 85 s->l1_size = new_l1_size; 86 return 0; 87 fail: 88 g_free(new_l1_table); 89 qcow2_free_clusters(bs, new_l1_table_offset, new_l1_size2); 90 return ret; 91 } 92 93 void qcow2_l2_cache_reset(BlockDriverState *bs) 94 { 95 BDRVQcowState *s = bs->opaque; 96 97 memset(s->l2_cache, 0, s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t)); 98 memset(s->l2_cache_offsets, 0, L2_CACHE_SIZE * sizeof(uint64_t)); 99 memset(s->l2_cache_counts, 0, L2_CACHE_SIZE * sizeof(uint32_t)); 100 } 101 102 static inline int l2_cache_new_entry(BlockDriverState *bs) 103 { 104 BDRVQcowState *s = bs->opaque; 105 uint32_t min_count; 106 int min_index, i; 107 108 /* find a new entry in the least used one */ 109 min_index = 0; 110 min_count = 0xffffffff; 111 for(i = 0; i < L2_CACHE_SIZE; i++) { 112 if (s->l2_cache_counts[i] < min_count) { 113 min_count = s->l2_cache_counts[i]; 114 min_index = i; 115 } 116 } 117 return min_index; 118 } 119 120 /* 121 * seek_l2_table 122 * 123 * seek l2_offset in the l2_cache table 124 * if not found, return NULL, 125 * if found, 126 * increments the l2 cache hit count of the entry, 127 * if counter overflow, divide by two all counters 128 * return the pointer to the l2 cache entry 129 * 130 */ 131 132 static uint64_t *seek_l2_table(BDRVQcowState *s, uint64_t l2_offset) 133 { 134 int i, j; 135 136 for(i = 0; i < L2_CACHE_SIZE; i++) { 137 if (l2_offset == s->l2_cache_offsets[i]) { 138 /* increment the hit count */ 139 if (++s->l2_cache_counts[i] == 0xffffffff) { 140 for(j = 0; j < L2_CACHE_SIZE; j++) { 141 s->l2_cache_counts[j] >>= 1; 142 } 143 } 144 return s->l2_cache + (i << s->l2_bits); 145 } 146 } 147 return NULL; 148 } 149 150 /* 151 * l2_load 152 * 153 * Loads a L2 table into memory. If the table is in the cache, the cache 154 * is used; otherwise the L2 table is loaded from the image file. 155 * 156 * Returns a pointer to the L2 table on success, or NULL if the read from 157 * the image file failed. 158 */ 159 160 static int l2_load(BlockDriverState *bs, uint64_t l2_offset, 161 uint64_t **l2_table) 162 { 163 BDRVQcowState *s = bs->opaque; 164 int min_index; 165 int ret; 166 167 /* seek if the table for the given offset is in the cache */ 168 169 *l2_table = seek_l2_table(s, l2_offset); 170 if (*l2_table != NULL) { 171 return 0; 172 } 173 174 /* not found: load a new entry in the least used one */ 175 176 min_index = l2_cache_new_entry(bs); 177 *l2_table = s->l2_cache + (min_index << s->l2_bits); 178 179 BLKDBG_EVENT(bs->file, BLKDBG_L2_LOAD); 180 ret = bdrv_pread(bs->file, l2_offset, *l2_table, 181 s->l2_size * sizeof(uint64_t)); 182 if (ret < 0) { 183 return ret; 184 } 185 186 s->l2_cache_offsets[min_index] = l2_offset; 187 s->l2_cache_counts[min_index] = 1; 188 189 return 0; 190 } 191 192 /* 193 * Writes one sector of the L1 table to the disk (can't update single entries 194 * and we really don't want bdrv_pread to perform a read-modify-write) 195 */ 196 #define L1_ENTRIES_PER_SECTOR (512 / 8) 197 static int write_l1_entry(BlockDriverState *bs, int l1_index) 198 { 199 BDRVQcowState *s = bs->opaque; 200 uint64_t buf[L1_ENTRIES_PER_SECTOR]; 201 int l1_start_index; 202 int i, ret; 203 204 l1_start_index = l1_index & ~(L1_ENTRIES_PER_SECTOR - 1); 205 for (i = 0; i < L1_ENTRIES_PER_SECTOR; i++) { 206 buf[i] = cpu_to_be64(s->l1_table[l1_start_index + i]); 207 } 208 209 BLKDBG_EVENT(bs->file, BLKDBG_L1_UPDATE); 210 ret = bdrv_pwrite_sync(bs->file, s->l1_table_offset + 8 * l1_start_index, 211 buf, sizeof(buf)); 212 if (ret < 0) { 213 return ret; 214 } 215 216 return 0; 217 } 218 219 /* 220 * l2_allocate 221 * 222 * Allocate a new l2 entry in the file. If l1_index points to an already 223 * used entry in the L2 table (i.e. we are doing a copy on write for the L2 224 * table) copy the contents of the old L2 table into the newly allocated one. 225 * Otherwise the new table is initialized with zeros. 226 * 227 */ 228 229 static int l2_allocate(BlockDriverState *bs, int l1_index, uint64_t **table) 230 { 231 BDRVQcowState *s = bs->opaque; 232 int min_index; 233 uint64_t old_l2_offset; 234 uint64_t *l2_table; 235 int64_t l2_offset; 236 int ret; 237 238 old_l2_offset = s->l1_table[l1_index]; 239 240 /* allocate a new l2 entry */ 241 242 l2_offset = qcow2_alloc_clusters(bs, s->l2_size * sizeof(uint64_t)); 243 if (l2_offset < 0) { 244 return l2_offset; 245 } 246 247 /* allocate a new entry in the l2 cache */ 248 249 min_index = l2_cache_new_entry(bs); 250 l2_table = s->l2_cache + (min_index << s->l2_bits); 251 252 if (old_l2_offset == 0) { 253 /* if there was no old l2 table, clear the new table */ 254 memset(l2_table, 0, s->l2_size * sizeof(uint64_t)); 255 } else { 256 /* if there was an old l2 table, read it from the disk */ 257 BLKDBG_EVENT(bs->file, BLKDBG_L2_ALLOC_COW_READ); 258 ret = bdrv_pread(bs->file, old_l2_offset, l2_table, 259 s->l2_size * sizeof(uint64_t)); 260 if (ret < 0) { 261 goto fail; 262 } 263 } 264 /* write the l2 table to the file */ 265 BLKDBG_EVENT(bs->file, BLKDBG_L2_ALLOC_WRITE); 266 ret = bdrv_pwrite_sync(bs->file, l2_offset, l2_table, 267 s->l2_size * sizeof(uint64_t)); 268 if (ret < 0) { 269 goto fail; 270 } 271 272 /* update the L1 entry */ 273 s->l1_table[l1_index] = l2_offset | QCOW_OFLAG_COPIED; 274 ret = write_l1_entry(bs, l1_index); 275 if (ret < 0) { 276 goto fail; 277 } 278 279 /* update the l2 cache entry */ 280 281 s->l2_cache_offsets[min_index] = l2_offset; 282 s->l2_cache_counts[min_index] = 1; 283 284 *table = l2_table; 285 return 0; 286 287 fail: 288 s->l1_table[l1_index] = old_l2_offset; 289 qcow2_l2_cache_reset(bs); 290 return ret; 291 } 292 293 static int count_contiguous_clusters(uint64_t nb_clusters, int cluster_size, 294 uint64_t *l2_table, uint64_t start, uint64_t mask) 295 { 296 int i; 297 uint64_t offset = be64_to_cpu(l2_table[0]) & ~mask; 298 299 if (!offset) 300 return 0; 301 302 for (i = start; i < start + nb_clusters; i++) 303 if (offset + (uint64_t) i * cluster_size != (be64_to_cpu(l2_table[i]) & ~mask)) 304 break; 305 306 return (i - start); 307 } 308 309 static int count_contiguous_free_clusters(uint64_t nb_clusters, uint64_t *l2_table) 310 { 311 int i = 0; 312 313 while(nb_clusters-- && l2_table[i] == 0) 314 i++; 315 316 return i; 317 } 318 319 /* The crypt function is compatible with the linux cryptoloop 320 algorithm for < 4 GB images. NOTE: out_buf == in_buf is 321 supported */ 322 void qcow2_encrypt_sectors(BDRVQcowState *s, int64_t sector_num, 323 uint8_t *out_buf, const uint8_t *in_buf, 324 int nb_sectors, int enc, 325 const AES_KEY *key) 326 { 327 union { 328 uint64_t ll[2]; 329 uint8_t b[16]; 330 } ivec; 331 int i; 332 333 for(i = 0; i < nb_sectors; i++) { 334 ivec.ll[0] = cpu_to_le64(sector_num); 335 ivec.ll[1] = 0; 336 AES_cbc_encrypt(in_buf, out_buf, 512, key, 337 ivec.b, enc); 338 sector_num++; 339 in_buf += 512; 340 out_buf += 512; 341 } 342 } 343 344 345 static int qcow_read(BlockDriverState *bs, int64_t sector_num, 346 uint8_t *buf, int nb_sectors) 347 { 348 BDRVQcowState *s = bs->opaque; 349 int ret, index_in_cluster, n, n1; 350 uint64_t cluster_offset; 351 352 while (nb_sectors > 0) { 353 n = nb_sectors; 354 355 ret = qcow2_get_cluster_offset(bs, sector_num << 9, &n, 356 &cluster_offset); 357 if (ret < 0) { 358 return ret; 359 } 360 361 index_in_cluster = sector_num & (s->cluster_sectors - 1); 362 if (!cluster_offset) { 363 if (bs->backing_hd) { 364 /* read from the base image */ 365 n1 = qcow2_backing_read1(bs->backing_hd, sector_num, buf, n); 366 if (n1 > 0) { 367 BLKDBG_EVENT(bs->file, BLKDBG_READ_BACKING); 368 ret = bdrv_read(bs->backing_hd, sector_num, buf, n1); 369 if (ret < 0) 370 return -1; 371 } 372 } else { 373 memset(buf, 0, 512 * n); 374 } 375 } else if (cluster_offset & QCOW_OFLAG_COMPRESSED) { 376 if (qcow2_decompress_cluster(bs, cluster_offset) < 0) 377 return -1; 378 memcpy(buf, s->cluster_cache + index_in_cluster * 512, 512 * n); 379 } else { 380 BLKDBG_EVENT(bs->file, BLKDBG_READ); 381 ret = bdrv_pread(bs->file, cluster_offset + index_in_cluster * 512, buf, n * 512); 382 if (ret != n * 512) 383 return -1; 384 if (s->crypt_method) { 385 qcow2_encrypt_sectors(s, sector_num, buf, buf, n, 0, 386 &s->aes_decrypt_key); 387 } 388 } 389 nb_sectors -= n; 390 sector_num += n; 391 buf += n * 512; 392 } 393 return 0; 394 } 395 396 static int copy_sectors(BlockDriverState *bs, uint64_t start_sect, 397 uint64_t cluster_offset, int n_start, int n_end) 398 { 399 BDRVQcowState *s = bs->opaque; 400 int n, ret; 401 402 n = n_end - n_start; 403 if (n <= 0) 404 return 0; 405 BLKDBG_EVENT(bs->file, BLKDBG_COW_READ); 406 ret = qcow_read(bs, start_sect + n_start, s->cluster_data, n); 407 if (ret < 0) 408 return ret; 409 if (s->crypt_method) { 410 qcow2_encrypt_sectors(s, start_sect + n_start, 411 s->cluster_data, 412 s->cluster_data, n, 1, 413 &s->aes_encrypt_key); 414 } 415 BLKDBG_EVENT(bs->file, BLKDBG_COW_WRITE); 416 ret = bdrv_write_sync(bs->file, (cluster_offset >> 9) + n_start, 417 s->cluster_data, n); 418 if (ret < 0) 419 return ret; 420 return 0; 421 } 422 423 424 /* 425 * get_cluster_offset 426 * 427 * For a given offset of the disk image, find the cluster offset in 428 * qcow2 file. The offset is stored in *cluster_offset. 429 * 430 * on entry, *num is the number of contiguous clusters we'd like to 431 * access following offset. 432 * 433 * on exit, *num is the number of contiguous clusters we can read. 434 * 435 * Return 0, if the offset is found 436 * Return -errno, otherwise. 437 * 438 */ 439 440 int qcow2_get_cluster_offset(BlockDriverState *bs, uint64_t offset, 441 int *num, uint64_t *cluster_offset) 442 { 443 BDRVQcowState *s = bs->opaque; 444 unsigned int l1_index, l2_index; 445 uint64_t l2_offset, *l2_table; 446 int l1_bits, c; 447 unsigned int index_in_cluster, nb_clusters; 448 uint64_t nb_available, nb_needed; 449 int ret; 450 451 index_in_cluster = (offset >> 9) & (s->cluster_sectors - 1); 452 nb_needed = *num + index_in_cluster; 453 454 l1_bits = s->l2_bits + s->cluster_bits; 455 456 /* compute how many bytes there are between the offset and 457 * the end of the l1 entry 458 */ 459 460 nb_available = (1ULL << l1_bits) - (offset & ((1ULL << l1_bits) - 1)); 461 462 /* compute the number of available sectors */ 463 464 nb_available = (nb_available >> 9) + index_in_cluster; 465 466 if (nb_needed > nb_available) { 467 nb_needed = nb_available; 468 } 469 470 *cluster_offset = 0; 471 472 /* seek the the l2 offset in the l1 table */ 473 474 l1_index = offset >> l1_bits; 475 if (l1_index >= s->l1_size) 476 goto out; 477 478 l2_offset = s->l1_table[l1_index]; 479 480 /* seek the l2 table of the given l2 offset */ 481 482 if (!l2_offset) 483 goto out; 484 485 /* load the l2 table in memory */ 486 487 l2_offset &= ~QCOW_OFLAG_COPIED; 488 ret = l2_load(bs, l2_offset, &l2_table); 489 if (ret < 0) { 490 return ret; 491 } 492 493 /* find the cluster offset for the given disk offset */ 494 495 l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1); 496 *cluster_offset = be64_to_cpu(l2_table[l2_index]); 497 nb_clusters = size_to_clusters(s, nb_needed << 9); 498 499 if (!*cluster_offset) { 500 /* how many empty clusters ? */ 501 c = count_contiguous_free_clusters(nb_clusters, &l2_table[l2_index]); 502 } else { 503 /* how many allocated clusters ? */ 504 c = count_contiguous_clusters(nb_clusters, s->cluster_size, 505 &l2_table[l2_index], 0, QCOW_OFLAG_COPIED); 506 } 507 508 nb_available = (c * s->cluster_sectors); 509 out: 510 if (nb_available > nb_needed) 511 nb_available = nb_needed; 512 513 *num = nb_available - index_in_cluster; 514 515 *cluster_offset &=~QCOW_OFLAG_COPIED; 516 return 0; 517 } 518 519 /* 520 * get_cluster_table 521 * 522 * for a given disk offset, load (and allocate if needed) 523 * the l2 table. 524 * 525 * the l2 table offset in the qcow2 file and the cluster index 526 * in the l2 table are given to the caller. 527 * 528 * Returns 0 on success, -errno in failure case 529 */ 530 static int get_cluster_table(BlockDriverState *bs, uint64_t offset, 531 uint64_t **new_l2_table, 532 uint64_t *new_l2_offset, 533 int *new_l2_index) 534 { 535 BDRVQcowState *s = bs->opaque; 536 unsigned int l1_index, l2_index; 537 uint64_t l2_offset; 538 uint64_t *l2_table = NULL; 539 int ret; 540 541 /* seek the the l2 offset in the l1 table */ 542 543 l1_index = offset >> (s->l2_bits + s->cluster_bits); 544 if (l1_index >= s->l1_size) { 545 ret = qcow2_grow_l1_table(bs, l1_index + 1); 546 if (ret < 0) { 547 return ret; 548 } 549 } 550 l2_offset = s->l1_table[l1_index]; 551 552 /* seek the l2 table of the given l2 offset */ 553 554 if (l2_offset & QCOW_OFLAG_COPIED) { 555 /* load the l2 table in memory */ 556 l2_offset &= ~QCOW_OFLAG_COPIED; 557 ret = l2_load(bs, l2_offset, &l2_table); 558 if (ret < 0) { 559 return ret; 560 } 561 } else { 562 if (l2_offset) 563 qcow2_free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t)); 564 ret = l2_allocate(bs, l1_index, &l2_table); 565 if (ret < 0) { 566 return ret; 567 } 568 l2_offset = s->l1_table[l1_index] & ~QCOW_OFLAG_COPIED; 569 } 570 571 /* find the cluster offset for the given disk offset */ 572 573 l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1); 574 575 *new_l2_table = l2_table; 576 *new_l2_offset = l2_offset; 577 *new_l2_index = l2_index; 578 579 return 0; 580 } 581 582 /* 583 * alloc_compressed_cluster_offset 584 * 585 * For a given offset of the disk image, return cluster offset in 586 * qcow2 file. 587 * 588 * If the offset is not found, allocate a new compressed cluster. 589 * 590 * Return the cluster offset if successful, 591 * Return 0, otherwise. 592 * 593 */ 594 595 uint64_t qcow2_alloc_compressed_cluster_offset(BlockDriverState *bs, 596 uint64_t offset, 597 int compressed_size) 598 { 599 BDRVQcowState *s = bs->opaque; 600 int l2_index, ret; 601 uint64_t l2_offset, *l2_table; 602 int64_t cluster_offset; 603 int nb_csectors; 604 605 ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index); 606 if (ret < 0) { 607 return 0; 608 } 609 610 cluster_offset = be64_to_cpu(l2_table[l2_index]); 611 if (cluster_offset & QCOW_OFLAG_COPIED) 612 return cluster_offset & ~QCOW_OFLAG_COPIED; 613 614 if (cluster_offset) 615 qcow2_free_any_clusters(bs, cluster_offset, 1); 616 617 cluster_offset = qcow2_alloc_bytes(bs, compressed_size); 618 if (cluster_offset < 0) { 619 return 0; 620 } 621 622 nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) - 623 (cluster_offset >> 9); 624 625 cluster_offset |= QCOW_OFLAG_COMPRESSED | 626 ((uint64_t)nb_csectors << s->csize_shift); 627 628 /* update L2 table */ 629 630 /* compressed clusters never have the copied flag */ 631 632 BLKDBG_EVENT(bs->file, BLKDBG_L2_UPDATE_COMPRESSED); 633 l2_table[l2_index] = cpu_to_be64(cluster_offset); 634 if (bdrv_pwrite_sync(bs->file, 635 l2_offset + l2_index * sizeof(uint64_t), 636 l2_table + l2_index, 637 sizeof(uint64_t)) < 0) 638 return 0; 639 640 return cluster_offset; 641 } 642 643 /* 644 * Write L2 table updates to disk, writing whole sectors to avoid a 645 * read-modify-write in bdrv_pwrite 646 */ 647 #define L2_ENTRIES_PER_SECTOR (512 / 8) 648 static int write_l2_entries(BlockDriverState *bs, uint64_t *l2_table, 649 uint64_t l2_offset, int l2_index, int num) 650 { 651 int l2_start_index = l2_index & ~(L1_ENTRIES_PER_SECTOR - 1); 652 int start_offset = (8 * l2_index) & ~511; 653 int end_offset = (8 * (l2_index + num) + 511) & ~511; 654 size_t len = end_offset - start_offset; 655 int ret; 656 657 BLKDBG_EVENT(bs->file, BLKDBG_L2_UPDATE); 658 ret = bdrv_pwrite_sync(bs->file, l2_offset + start_offset, 659 &l2_table[l2_start_index], len); 660 if (ret < 0) { 661 return ret; 662 } 663 664 return 0; 665 } 666 667 int qcow2_alloc_cluster_link_l2(BlockDriverState *bs, QCowL2Meta *m) 668 { 669 BDRVQcowState *s = bs->opaque; 670 int i, j = 0, l2_index, ret; 671 uint64_t *old_cluster, start_sect, l2_offset, *l2_table; 672 uint64_t cluster_offset = m->cluster_offset; 673 674 if (m->nb_clusters == 0) 675 return 0; 676 677 old_cluster = g_malloc(m->nb_clusters * sizeof(uint64_t)); 678 679 /* copy content of unmodified sectors */ 680 start_sect = (m->offset & ~(s->cluster_size - 1)) >> 9; 681 if (m->n_start) { 682 ret = copy_sectors(bs, start_sect, cluster_offset, 0, m->n_start); 683 if (ret < 0) 684 goto err; 685 } 686 687 if (m->nb_available & (s->cluster_sectors - 1)) { 688 uint64_t end = m->nb_available & ~(uint64_t)(s->cluster_sectors - 1); 689 ret = copy_sectors(bs, start_sect + end, cluster_offset + (end << 9), 690 m->nb_available - end, s->cluster_sectors); 691 if (ret < 0) 692 goto err; 693 } 694 695 /* update L2 table */ 696 ret = get_cluster_table(bs, m->offset, &l2_table, &l2_offset, &l2_index); 697 if (ret < 0) { 698 goto err; 699 } 700 701 for (i = 0; i < m->nb_clusters; i++) { 702 /* if two concurrent writes happen to the same unallocated cluster 703 * each write allocates separate cluster and writes data concurrently. 704 * The first one to complete updates l2 table with pointer to its 705 * cluster the second one has to do RMW (which is done above by 706 * copy_sectors()), update l2 table with its cluster pointer and free 707 * old cluster. This is what this loop does */ 708 if(l2_table[l2_index + i] != 0) 709 old_cluster[j++] = l2_table[l2_index + i]; 710 711 l2_table[l2_index + i] = cpu_to_be64((cluster_offset + 712 (i << s->cluster_bits)) | QCOW_OFLAG_COPIED); 713 } 714 715 ret = write_l2_entries(bs, l2_table, l2_offset, l2_index, m->nb_clusters); 716 if (ret < 0) { 717 qcow2_l2_cache_reset(bs); 718 goto err; 719 } 720 721 for (i = 0; i < j; i++) 722 qcow2_free_any_clusters(bs, 723 be64_to_cpu(old_cluster[i]) & ~QCOW_OFLAG_COPIED, 1); 724 725 ret = 0; 726 err: 727 g_free(old_cluster); 728 return ret; 729 } 730 731 /* 732 * alloc_cluster_offset 733 * 734 * For a given offset of the disk image, return cluster offset in qcow2 file. 735 * If the offset is not found, allocate a new cluster. 736 * 737 * If the cluster was already allocated, m->nb_clusters is set to 0, 738 * m->depends_on is set to NULL and the other fields in m are meaningless. 739 * 740 * If the cluster is newly allocated, m->nb_clusters is set to the number of 741 * contiguous clusters that have been allocated. This may be 0 if the request 742 * conflict with another write request in flight; in this case, m->depends_on 743 * is set and the remaining fields of m are meaningless. 744 * 745 * If m->nb_clusters is non-zero, the other fields of m are valid and contain 746 * information about the first allocated cluster. 747 * 748 * Return 0 on success and -errno in error cases 749 */ 750 int qcow2_alloc_cluster_offset(BlockDriverState *bs, uint64_t offset, 751 int n_start, int n_end, int *num, QCowL2Meta *m) 752 { 753 BDRVQcowState *s = bs->opaque; 754 int l2_index, ret; 755 uint64_t l2_offset, *l2_table; 756 int64_t cluster_offset; 757 unsigned int nb_clusters, i = 0; 758 QCowL2Meta *old_alloc; 759 760 ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index); 761 if (ret < 0) { 762 return ret; 763 } 764 765 nb_clusters = size_to_clusters(s, n_end << 9); 766 767 nb_clusters = MIN(nb_clusters, s->l2_size - l2_index); 768 769 cluster_offset = be64_to_cpu(l2_table[l2_index]); 770 771 /* We keep all QCOW_OFLAG_COPIED clusters */ 772 773 if (cluster_offset & QCOW_OFLAG_COPIED) { 774 nb_clusters = count_contiguous_clusters(nb_clusters, s->cluster_size, 775 &l2_table[l2_index], 0, 0); 776 777 cluster_offset &= ~QCOW_OFLAG_COPIED; 778 m->nb_clusters = 0; 779 m->depends_on = NULL; 780 781 goto out; 782 } 783 784 /* for the moment, multiple compressed clusters are not managed */ 785 786 if (cluster_offset & QCOW_OFLAG_COMPRESSED) 787 nb_clusters = 1; 788 789 /* how many available clusters ? */ 790 791 while (i < nb_clusters) { 792 i += count_contiguous_clusters(nb_clusters - i, s->cluster_size, 793 &l2_table[l2_index], i, 0); 794 if ((i >= nb_clusters) || be64_to_cpu(l2_table[l2_index + i])) { 795 break; 796 } 797 798 i += count_contiguous_free_clusters(nb_clusters - i, 799 &l2_table[l2_index + i]); 800 if (i >= nb_clusters) { 801 break; 802 } 803 804 cluster_offset = be64_to_cpu(l2_table[l2_index + i]); 805 806 if ((cluster_offset & QCOW_OFLAG_COPIED) || 807 (cluster_offset & QCOW_OFLAG_COMPRESSED)) 808 break; 809 } 810 assert(i <= nb_clusters); 811 nb_clusters = i; 812 813 /* 814 * Check if there already is an AIO write request in flight which allocates 815 * the same cluster. In this case we need to wait until the previous 816 * request has completed and updated the L2 table accordingly. 817 */ 818 QLIST_FOREACH(old_alloc, &s->cluster_allocs, next_in_flight) { 819 820 uint64_t end_offset = offset + nb_clusters * s->cluster_size; 821 uint64_t old_offset = old_alloc->offset; 822 uint64_t old_end_offset = old_alloc->offset + 823 old_alloc->nb_clusters * s->cluster_size; 824 825 if (end_offset < old_offset || offset > old_end_offset) { 826 /* No intersection */ 827 } else { 828 if (offset < old_offset) { 829 /* Stop at the start of a running allocation */ 830 nb_clusters = (old_offset - offset) >> s->cluster_bits; 831 } else { 832 nb_clusters = 0; 833 } 834 835 if (nb_clusters == 0) { 836 /* Set dependency and wait for a callback */ 837 m->depends_on = old_alloc; 838 m->nb_clusters = 0; 839 *num = 0; 840 return 0; 841 } 842 } 843 } 844 845 if (!nb_clusters) { 846 abort(); 847 } 848 849 QLIST_INSERT_HEAD(&s->cluster_allocs, m, next_in_flight); 850 851 /* allocate a new cluster */ 852 853 cluster_offset = qcow2_alloc_clusters(bs, nb_clusters * s->cluster_size); 854 if (cluster_offset < 0) { 855 QLIST_REMOVE(m, next_in_flight); 856 return cluster_offset; 857 } 858 859 /* save info needed for meta data update */ 860 m->offset = offset; 861 m->n_start = n_start; 862 m->nb_clusters = nb_clusters; 863 864 out: 865 m->nb_available = MIN(nb_clusters << (s->cluster_bits - 9), n_end); 866 m->cluster_offset = cluster_offset; 867 868 *num = m->nb_available - n_start; 869 870 return 0; 871 } 872 873 static int decompress_buffer(uint8_t *out_buf, int out_buf_size, 874 const uint8_t *buf, int buf_size) 875 { 876 z_stream strm1, *strm = &strm1; 877 int ret, out_len; 878 879 memset(strm, 0, sizeof(*strm)); 880 881 strm->next_in = (uint8_t *)buf; 882 strm->avail_in = buf_size; 883 strm->next_out = out_buf; 884 strm->avail_out = out_buf_size; 885 886 ret = inflateInit2(strm, -12); 887 if (ret != Z_OK) 888 return -1; 889 ret = inflate(strm, Z_FINISH); 890 out_len = strm->next_out - out_buf; 891 if ((ret != Z_STREAM_END && ret != Z_BUF_ERROR) || 892 out_len != out_buf_size) { 893 inflateEnd(strm); 894 return -1; 895 } 896 inflateEnd(strm); 897 return 0; 898 } 899 900 int qcow2_decompress_cluster(BlockDriverState *bs, uint64_t cluster_offset) 901 { 902 BDRVQcowState *s = bs->opaque; 903 int ret, csize, nb_csectors, sector_offset; 904 uint64_t coffset; 905 906 coffset = cluster_offset & s->cluster_offset_mask; 907 if (s->cluster_cache_offset != coffset) { 908 nb_csectors = ((cluster_offset >> s->csize_shift) & s->csize_mask) + 1; 909 sector_offset = coffset & 511; 910 csize = nb_csectors * 512 - sector_offset; 911 BLKDBG_EVENT(bs->file, BLKDBG_READ_COMPRESSED); 912 ret = bdrv_read(bs->file, coffset >> 9, s->cluster_data, nb_csectors); 913 if (ret < 0) { 914 return -1; 915 } 916 if (decompress_buffer(s->cluster_cache, s->cluster_size, 917 s->cluster_data + sector_offset, csize) < 0) { 918 return -1; 919 } 920 s->cluster_cache_offset = coffset; 921 } 922 return 0; 923 } 924