block/qcow2-cluster.c

   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 #include "trace.h"
  31
  32 int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size,
  33                         bool exact_size)
  34 {
  35     BDRVQcowState *s = bs->opaque;
  36     int new_l1_size2, ret, i;
  37     uint64_t *new_l1_table;
  38     int64_t old_l1_table_offset, old_l1_size;
  39     int64_t new_l1_table_offset, new_l1_size;
  40     uint8_t data[12];
  41
  42     if (min_size <= s->l1_size)
  43         return 0;
  44
  45     if (exact_size) {
  46         new_l1_size = min_size;
  47     } else {
  48         /* Bump size up to reduce the number of times we have to grow */
  49         new_l1_size = s->l1_size;
  50         if (new_l1_size == 0) {
  51             new_l1_size = 1;
  52         }
  53         while (min_size > new_l1_size) {
  54             new_l1_size = (new_l1_size * 3 + 1) / 2;
  55         }
  56     }
  57
  58     if (new_l1_size > INT_MAX) {
  59         return -EFBIG;
  60     }
  61
  62 #ifdef DEBUG_ALLOC2
  63     fprintf(stderr, "grow l1_table from %d to %" PRId64 "\n",
  64             s->l1_size, new_l1_size);
  65 #endif
  66
  67     new_l1_size2 = sizeof(uint64_t) * new_l1_size;
  68     new_l1_table = g_malloc0(align_offset(new_l1_size2, 512));
  69     memcpy(new_l1_table, s->l1_table, s->l1_size * sizeof(uint64_t));
  70
  71     /* write new table (align to cluster) */
  72     BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_ALLOC_TABLE);
  73     new_l1_table_offset = qcow2_alloc_clusters(bs, new_l1_size2);
  74     if (new_l1_table_offset < 0) {
  75         g_free(new_l1_table);
  76         return new_l1_table_offset;
  77     }
  78
  79     ret = qcow2_cache_flush(bs, s->refcount_block_cache);
  80     if (ret < 0) {
  81         goto fail;
  82     }
  83
  84     /* the L1 position has not yet been updated, so these clusters must
  85      * indeed be completely free */
  86     ret = qcow2_pre_write_overlap_check(bs, 0, new_l1_table_offset,
  87                                         new_l1_size2);
  88     if (ret < 0) {
  89         goto fail;
  90     }
  91
  92     BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_WRITE_TABLE);
  93     for(i = 0; i < s->l1_size; i++)
  94         new_l1_table[i] = cpu_to_be64(new_l1_table[i]);
  95     ret = bdrv_pwrite_sync(bs->file, new_l1_table_offset, new_l1_table, new_l1_size2);
  96     if (ret < 0)
  97         goto fail;
  98     for(i = 0; i < s->l1_size; i++)
  99         new_l1_table[i] = be64_to_cpu(new_l1_table[i]);
 100
 101     /* set new table */
 102     BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_ACTIVATE_TABLE);
 103     cpu_to_be32w((uint32_t*)data, new_l1_size);
 104     stq_be_p(data + 4, new_l1_table_offset);
 105     ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, l1_size), data,sizeof(data));
 106     if (ret < 0) {
 107         goto fail;
 108     }
 109     g_free(s->l1_table);
 110     old_l1_table_offset = s->l1_table_offset;
 111     s->l1_table_offset = new_l1_table_offset;
 112     s->l1_table = new_l1_table;
 113     old_l1_size = s->l1_size;
 114     s->l1_size = new_l1_size;
 115     qcow2_free_clusters(bs, old_l1_table_offset, old_l1_size * sizeof(uint64_t),
 116                         QCOW2_DISCARD_OTHER);
 117     return 0;
 118  fail:
 119     g_free(new_l1_table);
 120     qcow2_free_clusters(bs, new_l1_table_offset, new_l1_size2,
 121                         QCOW2_DISCARD_OTHER);
 122     return ret;
 123 }
 124
 125 /*
 126  * l2_load
 127  *
 128  * Loads a L2 table into memory. If the table is in the cache, the cache
 129  * is used; otherwise the L2 table is loaded from the image file.
 130  *
 131  * Returns a pointer to the L2 table on success, or NULL if the read from
 132  * the image file failed.
 133  */
 134
 135 static int l2_load(BlockDriverState *bs, uint64_t l2_offset,
 136     uint64_t **l2_table)
 137 {
 138     BDRVQcowState *s = bs->opaque;
 139     int ret;
 140
 141     ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset, (void**) l2_table);
 142
 143     return ret;
 144 }
 145
 146 /*
 147  * Writes one sector of the L1 table to the disk (can't update single entries
 148  * and we really don't want bdrv_pread to perform a read-modify-write)
 149  */
 150 #define L1_ENTRIES_PER_SECTOR (512 / 8)
 151 int qcow2_write_l1_entry(BlockDriverState *bs, int l1_index)
 152 {
 153     BDRVQcowState *s = bs->opaque;
 154     uint64_t buf[L1_ENTRIES_PER_SECTOR];
 155     int l1_start_index;
 156     int i, ret;
 157
 158     l1_start_index = l1_index & ~(L1_ENTRIES_PER_SECTOR - 1);
 159     for (i = 0; i < L1_ENTRIES_PER_SECTOR; i++) {
 160         buf[i] = cpu_to_be64(s->l1_table[l1_start_index + i]);
 161     }
 162
 163     ret = qcow2_pre_write_overlap_check(bs, QCOW2_OL_ACTIVE_L1,
 164             s->l1_table_offset + 8 * l1_start_index, sizeof(buf));
 165     if (ret < 0) {
 166         return ret;
 167     }
 168
 169     BLKDBG_EVENT(bs->file, BLKDBG_L1_UPDATE);
 170     ret = bdrv_pwrite_sync(bs->file, s->l1_table_offset + 8 * l1_start_index,
 171         buf, sizeof(buf));
 172     if (ret < 0) {
 173         return ret;
 174     }
 175
 176     return 0;
 177 }
 178
 179 /*
 180  * l2_allocate
 181  *
 182  * Allocate a new l2 entry in the file. If l1_index points to an already
 183  * used entry in the L2 table (i.e. we are doing a copy on write for the L2
 184  * table) copy the contents of the old L2 table into the newly allocated one.
 185  * Otherwise the new table is initialized with zeros.
 186  *
 187  */
 188
 189 static int l2_allocate(BlockDriverState *bs, int l1_index, uint64_t **table)
 190 {
 191     BDRVQcowState *s = bs->opaque;
 192     uint64_t old_l2_offset;
 193     uint64_t *l2_table = NULL;
 194     int64_t l2_offset;
 195     int ret;
 196
 197     old_l2_offset = s->l1_table[l1_index];
 198
 199     trace_qcow2_l2_allocate(bs, l1_index);
 200
 201     /* allocate a new l2 entry */
 202
 203     l2_offset = qcow2_alloc_clusters(bs, s->l2_size * sizeof(uint64_t));
 204     if (l2_offset < 0) {
 205         ret = l2_offset;
 206         goto fail;
 207     }
 208
 209     ret = qcow2_cache_flush(bs, s->refcount_block_cache);
 210     if (ret < 0) {
 211         goto fail;
 212     }
 213
 214     /* allocate a new entry in the l2 cache */
 215
 216     trace_qcow2_l2_allocate_get_empty(bs, l1_index);
 217     ret = qcow2_cache_get_empty(bs, s->l2_table_cache, l2_offset, (void**) table);
 218     if (ret < 0) {
 219         goto fail;
 220     }
 221
 222     l2_table = *table;
 223
 224     if ((old_l2_offset & L1E_OFFSET_MASK) == 0) {
 225         /* if there was no old l2 table, clear the new table */
 226         memset(l2_table, 0, s->l2_size * sizeof(uint64_t));
 227     } else {
 228         uint64_t* old_table;
 229
 230         /* if there was an old l2 table, read it from the disk */
 231         BLKDBG_EVENT(bs->file, BLKDBG_L2_ALLOC_COW_READ);
 232         ret = qcow2_cache_get(bs, s->l2_table_cache,
 233             old_l2_offset & L1E_OFFSET_MASK,
 234             (void**) &old_table);
 235         if (ret < 0) {
 236             goto fail;
 237         }
 238
 239         memcpy(l2_table, old_table, s->cluster_size);
 240
 241         ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &old_table);
 242         if (ret < 0) {
 243             goto fail;
 244         }
 245     }
 246
 247     /* write the l2 table to the file */
 248     BLKDBG_EVENT(bs->file, BLKDBG_L2_ALLOC_WRITE);
 249
 250     trace_qcow2_l2_allocate_write_l2(bs, l1_index);
 251     qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
 252     ret = qcow2_cache_flush(bs, s->l2_table_cache);
 253     if (ret < 0) {
 254         goto fail;
 255     }
 256
 257     /* update the L1 entry */
 258     trace_qcow2_l2_allocate_write_l1(bs, l1_index);
 259     s->l1_table[l1_index] = l2_offset | QCOW_OFLAG_COPIED;
 260     ret = qcow2_write_l1_entry(bs, l1_index);
 261     if (ret < 0) {
 262         goto fail;
 263     }
 264
 265     *table = l2_table;
 266     trace_qcow2_l2_allocate_done(bs, l1_index, 0);
 267     return 0;
 268
 269 fail:
 270     trace_qcow2_l2_allocate_done(bs, l1_index, ret);
 271     if (l2_table != NULL) {
 272         qcow2_cache_put(bs, s->l2_table_cache, (void**) table);
 273     }
 274     s->l1_table[l1_index] = old_l2_offset;
 275     if (l2_offset > 0) {
 276         qcow2_free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t),
 277                             QCOW2_DISCARD_ALWAYS);
 278     }
 279     return ret;
 280 }
 281
 282 /*
 283  * Checks how many clusters in a given L2 table are contiguous in the image
 284  * file. As soon as one of the flags in the bitmask stop_flags changes compared
 285  * to the first cluster, the search is stopped and the cluster is not counted
 286  * as contiguous. (This allows it, for example, to stop at the first compressed
 287  * cluster which may require a different handling)
 288  */
 289 static int count_contiguous_clusters(uint64_t nb_clusters, int cluster_size,
 290         uint64_t *l2_table, uint64_t stop_flags)
 291 {
 292     int i;
 293     uint64_t mask = stop_flags | L2E_OFFSET_MASK | QCOW_OFLAG_COMPRESSED;
 294     uint64_t first_entry = be64_to_cpu(l2_table[0]);
 295     uint64_t offset = first_entry & mask;
 296
 297     if (!offset)
 298         return 0;
 299
 300     assert(qcow2_get_cluster_type(first_entry) != QCOW2_CLUSTER_COMPRESSED);
 301
 302     for (i = 0; i < nb_clusters; i++) {
 303         uint64_t l2_entry = be64_to_cpu(l2_table[i]) & mask;
 304         if (offset + (uint64_t) i * cluster_size != l2_entry) {
 305             break;
 306         }
 307     }
 308
 309         return i;
 310 }
 311
 312 static int count_contiguous_free_clusters(uint64_t nb_clusters, uint64_t *l2_table)
 313 {
 314     int i;
 315
 316     for (i = 0; i < nb_clusters; i++) {
 317         int type = qcow2_get_cluster_type(be64_to_cpu(l2_table[i]));
 318
 319         if (type != QCOW2_CLUSTER_UNALLOCATED) {
 320             break;
 321         }
 322     }
 323
 324     return i;
 325 }
 326
 327 /* The crypt function is compatible with the linux cryptoloop
 328    algorithm for < 4 GB images. NOTE: out_buf == in_buf is
 329    supported */
 330 void qcow2_encrypt_sectors(BDRVQcowState *s, int64_t sector_num,
 331                            uint8_t *out_buf, const uint8_t *in_buf,
 332                            int nb_sectors, int enc,
 333                            const AES_KEY *key)
 334 {
 335     union {
 336         uint64_t ll[2];
 337         uint8_t b[16];
 338     } ivec;
 339     int i;
 340
 341     for(i = 0; i < nb_sectors; i++) {
 342         ivec.ll[0] = cpu_to_le64(sector_num);
 343         ivec.ll[1] = 0;
 344         AES_cbc_encrypt(in_buf, out_buf, 512, key,
 345                         ivec.b, enc);
 346         sector_num++;
 347         in_buf += 512;
 348         out_buf += 512;
 349     }
 350 }
 351
 352 static int coroutine_fn copy_sectors(BlockDriverState *bs,
 353                                      uint64_t start_sect,
 354                                      uint64_t cluster_offset,
 355                                      int n_start, int n_end)
 356 {
 357     BDRVQcowState *s = bs->opaque;
 358     QEMUIOVector qiov;
 359     struct iovec iov;
 360     int n, ret;
 361
 362     /*
 363      * If this is the last cluster and it is only partially used, we must only
 364      * copy until the end of the image, or bdrv_check_request will fail for the
 365      * bdrv_read/write calls below.
 366      */
 367     if (start_sect + n_end > bs->total_sectors) {
 368         n_end = bs->total_sectors - start_sect;
 369     }
 370
 371     n = n_end - n_start;
 372     if (n <= 0) {
 373         return 0;
 374     }
 375
 376     iov.iov_len = n * BDRV_SECTOR_SIZE;
 377     iov.iov_base = qemu_blockalign(bs, iov.iov_len);
 378
 379     qemu_iovec_init_external(&qiov, &iov, 1);
 380
 381     BLKDBG_EVENT(bs->file, BLKDBG_COW_READ);
 382
 383     if (!bs->drv) {
 384         return -ENOMEDIUM;
 385     }
 386
 387     /* Call .bdrv_co_readv() directly instead of using the public block-layer
 388      * interface.  This avoids double I/O throttling and request tracking,
 389      * which can lead to deadlock when block layer copy-on-read is enabled.
 390      */
 391     ret = bs->drv->bdrv_co_readv(bs, start_sect + n_start, n, &qiov);
 392     if (ret < 0) {
 393         goto out;
 394     }
 395
 396     if (s->crypt_method) {
 397         qcow2_encrypt_sectors(s, start_sect + n_start,
 398                         iov.iov_base, iov.iov_base, n, 1,
 399                         &s->aes_encrypt_key);
 400     }
 401
 402     ret = qcow2_pre_write_overlap_check(bs, 0,
 403             cluster_offset + n_start * BDRV_SECTOR_SIZE, n * BDRV_SECTOR_SIZE);
 404     if (ret < 0) {
 405         goto out;
 406     }
 407
 408     BLKDBG_EVENT(bs->file, BLKDBG_COW_WRITE);
 409     ret = bdrv_co_writev(bs->file, (cluster_offset >> 9) + n_start, n, &qiov);
 410     if (ret < 0) {
 411         goto out;
 412     }
 413
 414     ret = 0;
 415 out:
 416     qemu_vfree(iov.iov_base);
 417     return ret;
 418 }
 419
 420
 421 /*
 422  * get_cluster_offset
 423  *
 424  * For a given offset of the disk image, find the cluster offset in
 425  * qcow2 file. The offset is stored in *cluster_offset.
 426  *
 427  * on entry, *num is the number of contiguous sectors we'd like to
 428  * access following offset.
 429  *
 430  * on exit, *num is the number of contiguous sectors we can read.
 431  *
 432  * Returns the cluster type (QCOW2_CLUSTER_*) on success, -errno in error
 433  * cases.
 434  */
 435 int qcow2_get_cluster_offset(BlockDriverState *bs, uint64_t offset,
 436     int *num, uint64_t *cluster_offset)
 437 {
 438     BDRVQcowState *s = bs->opaque;
 439     unsigned int l2_index;
 440     uint64_t l1_index, l2_offset, *l2_table;
 441     int l1_bits, c;
 442     unsigned int index_in_cluster, nb_clusters;
 443     uint64_t nb_available, nb_needed;
 444     int ret;
 445
 446     index_in_cluster = (offset >> 9) & (s->cluster_sectors - 1);
 447     nb_needed = *num + index_in_cluster;
 448
 449     l1_bits = s->l2_bits + s->cluster_bits;
 450
 451     /* compute how many bytes there are between the offset and
 452      * the end of the l1 entry
 453      */
 454
 455     nb_available = (1ULL << l1_bits) - (offset & ((1ULL << l1_bits) - 1));
 456
 457     /* compute the number of available sectors */
 458
 459     nb_available = (nb_available >> 9) + index_in_cluster;
 460
 461     if (nb_needed > nb_available) {
 462         nb_needed = nb_available;
 463     }
 464
 465     *cluster_offset = 0;
 466
 467     /* seek the the l2 offset in the l1 table */
 468
 469     l1_index = offset >> l1_bits;
 470     if (l1_index >= s->l1_size) {
 471         ret = QCOW2_CLUSTER_UNALLOCATED;
 472         goto out;
 473     }
 474
 475     l2_offset = s->l1_table[l1_index] & L1E_OFFSET_MASK;
 476     if (!l2_offset) {
 477         ret = QCOW2_CLUSTER_UNALLOCATED;
 478         goto out;
 479     }
 480
 481     /* load the l2 table in memory */
 482
 483     ret = l2_load(bs, l2_offset, &l2_table);
 484     if (ret < 0) {
 485         return ret;
 486     }
 487
 488     /* find the cluster offset for the given disk offset */
 489
 490     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 491     *cluster_offset = be64_to_cpu(l2_table[l2_index]);
 492     nb_clusters = size_to_clusters(s, nb_needed << 9);
 493
 494     ret = qcow2_get_cluster_type(*cluster_offset);
 495     switch (ret) {
 496     case QCOW2_CLUSTER_COMPRESSED:
 497         /* Compressed clusters can only be processed one by one */
 498         c = 1;
 499         *cluster_offset &= L2E_COMPRESSED_OFFSET_SIZE_MASK;
 500         break;
 501     case QCOW2_CLUSTER_ZERO:
 502         if (s->qcow_version < 3) {
 503             return -EIO;
 504         }
 505         c = count_contiguous_clusters(nb_clusters, s->cluster_size,
 506                 &l2_table[l2_index], QCOW_OFLAG_ZERO);
 507         *cluster_offset = 0;
 508         break;
 509     case QCOW2_CLUSTER_UNALLOCATED:
 510         /* how many empty clusters ? */
 511         c = count_contiguous_free_clusters(nb_clusters, &l2_table[l2_index]);
 512         *cluster_offset = 0;
 513         break;
 514     case QCOW2_CLUSTER_NORMAL:
 515         /* how many allocated clusters ? */
 516         c = count_contiguous_clusters(nb_clusters, s->cluster_size,
 517                 &l2_table[l2_index], QCOW_OFLAG_ZERO);
 518         *cluster_offset &= L2E_OFFSET_MASK;
 519         break;
 520     default:
 521         abort();
 522     }
 523
 524     qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
 525
 526     nb_available = (c * s->cluster_sectors);
 527
 528 out:
 529     if (nb_available > nb_needed)
 530         nb_available = nb_needed;
 531
 532     *num = nb_available - index_in_cluster;
 533
 534     return ret;
 535 }
 536
 537 /*
 538  * get_cluster_table
 539  *
 540  * for a given disk offset, load (and allocate if needed)
 541  * the l2 table.
 542  *
 543  * the l2 table offset in the qcow2 file and the cluster index
 544  * in the l2 table are given to the caller.
 545  *
 546  * Returns 0 on success, -errno in failure case
 547  */
 548 static int get_cluster_table(BlockDriverState *bs, uint64_t offset,
 549                              uint64_t **new_l2_table,
 550                              int *new_l2_index)
 551 {
 552     BDRVQcowState *s = bs->opaque;
 553     unsigned int l2_index;
 554     uint64_t l1_index, l2_offset;
 555     uint64_t *l2_table = NULL;
 556     int ret;
 557
 558     /* seek the the l2 offset in the l1 table */
 559
 560     l1_index = offset >> (s->l2_bits + s->cluster_bits);
 561     if (l1_index >= s->l1_size) {
 562         ret = qcow2_grow_l1_table(bs, l1_index + 1, false);
 563         if (ret < 0) {
 564             return ret;
 565         }
 566     }
 567
 568     assert(l1_index < s->l1_size);
 569     l2_offset = s->l1_table[l1_index] & L1E_OFFSET_MASK;
 570
 571     /* seek the l2 table of the given l2 offset */
 572
 573     if (s->l1_table[l1_index] & QCOW_OFLAG_COPIED) {
 574         /* load the l2 table in memory */
 575         ret = l2_load(bs, l2_offset, &l2_table);
 576         if (ret < 0) {
 577             return ret;
 578         }
 579     } else {
 580         /* First allocate a new L2 table (and do COW if needed) */
 581         ret = l2_allocate(bs, l1_index, &l2_table);
 582         if (ret < 0) {
 583             return ret;
 584         }
 585
 586         /* Then decrease the refcount of the old table */
 587         if (l2_offset) {
 588             qcow2_free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t),
 589                                 QCOW2_DISCARD_OTHER);
 590         }
 591     }
 592
 593     /* find the cluster offset for the given disk offset */
 594
 595     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 596
 597     *new_l2_table = l2_table;
 598     *new_l2_index = l2_index;
 599
 600     return 0;
 601 }
 602
 603 /*
 604  * alloc_compressed_cluster_offset
 605  *
 606  * For a given offset of the disk image, return cluster offset in
 607  * qcow2 file.
 608  *
 609  * If the offset is not found, allocate a new compressed cluster.
 610  *
 611  * Return the cluster offset if successful,
 612  * Return 0, otherwise.
 613  *
 614  */
 615
 616 uint64_t qcow2_alloc_compressed_cluster_offset(BlockDriverState *bs,
 617                                                uint64_t offset,
 618                                                int compressed_size)
 619 {
 620     BDRVQcowState *s = bs->opaque;
 621     int l2_index, ret;
 622     uint64_t *l2_table;
 623     int64_t cluster_offset;
 624     int nb_csectors;
 625
 626     ret = get_cluster_table(bs, offset, &l2_table, &l2_index);
 627     if (ret < 0) {
 628         return 0;
 629     }
 630
 631     /* Compression can't overwrite anything. Fail if the cluster was already
 632      * allocated. */
 633     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 634     if (cluster_offset & L2E_OFFSET_MASK) {
 635         qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
 636         return 0;
 637     }
 638
 639     cluster_offset = qcow2_alloc_bytes(bs, compressed_size);
 640     if (cluster_offset < 0) {
 641         qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
 642         return 0;
 643     }
 644
 645     nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -
 646                   (cluster_offset >> 9);
 647
 648     cluster_offset |= QCOW_OFLAG_COMPRESSED |
 649                       ((uint64_t)nb_csectors << s->csize_shift);
 650
 651     /* update L2 table */
 652
 653     /* compressed clusters never have the copied flag */
 654
 655     BLKDBG_EVENT(bs->file, BLKDBG_L2_UPDATE_COMPRESSED);
 656     qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
 657     l2_table[l2_index] = cpu_to_be64(cluster_offset);
 658     ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
 659     if (ret < 0) {
 660         return 0;
 661     }
 662
 663     return cluster_offset;
 664 }
 665
 666 static int perform_cow(BlockDriverState *bs, QCowL2Meta *m, Qcow2COWRegion *r)
 667 {
 668     BDRVQcowState *s = bs->opaque;
 669     int ret;
 670
 671     if (r->nb_sectors == 0) {
 672         return 0;
 673     }
 674
 675     qemu_co_mutex_unlock(&s->lock);
 676     ret = copy_sectors(bs, m->offset / BDRV_SECTOR_SIZE, m->alloc_offset,
 677                        r->offset / BDRV_SECTOR_SIZE,
 678                        r->offset / BDRV_SECTOR_SIZE + r->nb_sectors);
 679     qemu_co_mutex_lock(&s->lock);
 680
 681     if (ret < 0) {
 682         return ret;
 683     }
 684
 685     /*
 686      * Before we update the L2 table to actually point to the new cluster, we
 687      * need to be sure that the refcounts have been increased and COW was
 688      * handled.
 689      */
 690     qcow2_cache_depends_on_flush(s->l2_table_cache);
 691
 692     return 0;
 693 }
 694
 695 int qcow2_alloc_cluster_link_l2(BlockDriverState *bs, QCowL2Meta *m)
 696 {
 697     BDRVQcowState *s = bs->opaque;
 698     int i, j = 0, l2_index, ret;
 699     uint64_t *old_cluster, *l2_table;
 700     uint64_t cluster_offset = m->alloc_offset;
 701
 702     trace_qcow2_cluster_link_l2(qemu_coroutine_self(), m->nb_clusters);
 703     assert(m->nb_clusters > 0);
 704
 705     old_cluster = g_malloc(m->nb_clusters * sizeof(uint64_t));
 706
 707     /* copy content of unmodified sectors */
 708     ret = perform_cow(bs, m, &m->cow_start);
 709     if (ret < 0) {
 710         goto err;
 711     }
 712
 713     ret = perform_cow(bs, m, &m->cow_end);
 714     if (ret < 0) {
 715         goto err;
 716     }
 717
 718     /* Update L2 table. */
 719     if (s->use_lazy_refcounts) {
 720         qcow2_mark_dirty(bs);
 721     }
 722     if (qcow2_need_accurate_refcounts(s)) {
 723         qcow2_cache_set_dependency(bs, s->l2_table_cache,
 724                                    s->refcount_block_cache);
 725     }
 726
 727     ret = get_cluster_table(bs, m->offset, &l2_table, &l2_index);
 728     if (ret < 0) {
 729         goto err;
 730     }
 731     qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
 732
 733     assert(l2_index + m->nb_clusters <= s->l2_size);
 734     for (i = 0; i < m->nb_clusters; i++) {
 735         /* if two concurrent writes happen to the same unallocated cluster
 736          * each write allocates separate cluster and writes data concurrently.
 737          * The first one to complete updates l2 table with pointer to its
 738          * cluster the second one has to do RMW (which is done above by
 739          * copy_sectors()), update l2 table with its cluster pointer and free
 740          * old cluster. This is what this loop does */
 741         if(l2_table[l2_index + i] != 0)
 742             old_cluster[j++] = l2_table[l2_index + i];
 743
 744         l2_table[l2_index + i] = cpu_to_be64((cluster_offset +
 745                     (i << s->cluster_bits)) | QCOW_OFLAG_COPIED);
 746      }
 747
 748
 749     ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
 750     if (ret < 0) {
 751         goto err;
 752     }
 753
 754     /*
 755      * If this was a COW, we need to decrease the refcount of the old cluster.
 756      * Also flush bs->file to get the right order for L2 and refcount update.
 757      *
 758      * Don't discard clusters that reach a refcount of 0 (e.g. compressed
 759      * clusters), the next write will reuse them anyway.
 760      */
 761     if (j != 0) {
 762         for (i = 0; i < j; i++) {
 763             qcow2_free_any_clusters(bs, be64_to_cpu(old_cluster[i]), 1,
 764                                     QCOW2_DISCARD_NEVER);
 765         }
 766     }
 767
 768     ret = 0;
 769 err:
 770     g_free(old_cluster);
 771     return ret;
 772  }
 773
 774 /*
 775  * Returns the number of contiguous clusters that can be used for an allocating
 776  * write, but require COW to be performed (this includes yet unallocated space,
 777  * which must copy from the backing file)
 778  */
 779 static int count_cow_clusters(BDRVQcowState *s, int nb_clusters,
 780     uint64_t *l2_table, int l2_index)
 781 {
 782     int i;
 783
 784     for (i = 0; i < nb_clusters; i++) {
 785         uint64_t l2_entry = be64_to_cpu(l2_table[l2_index + i]);
 786         int cluster_type = qcow2_get_cluster_type(l2_entry);
 787
 788         switch(cluster_type) {
 789         case QCOW2_CLUSTER_NORMAL:
 790             if (l2_entry & QCOW_OFLAG_COPIED) {
 791                 goto out;
 792             }
 793             break;
 794         case QCOW2_CLUSTER_UNALLOCATED:
 795         case QCOW2_CLUSTER_COMPRESSED:
 796         case QCOW2_CLUSTER_ZERO:
 797             break;
 798         default:
 799             abort();
 800         }
 801     }
 802
 803 out:
 804     assert(i <= nb_clusters);
 805     return i;
 806 }
 807
 808 /*
 809  * Check if there already is an AIO write request in flight which allocates
 810  * the same cluster. In this case we need to wait until the previous
 811  * request has completed and updated the L2 table accordingly.
 812  *
 813  * Returns:
 814  *   0       if there was no dependency. *cur_bytes indicates the number of
 815  *           bytes from guest_offset that can be read before the next
 816  *           dependency must be processed (or the request is complete)
 817  *
 818  *   -EAGAIN if we had to wait for another request, previously gathered
 819  *           information on cluster allocation may be invalid now. The caller
 820  *           must start over anyway, so consider *cur_bytes undefined.
 821  */
 822 static int handle_dependencies(BlockDriverState *bs, uint64_t guest_offset,
 823     uint64_t *cur_bytes, QCowL2Meta **m)
 824 {
 825     BDRVQcowState *s = bs->opaque;
 826     QCowL2Meta *old_alloc;
 827     uint64_t bytes = *cur_bytes;
 828
 829     QLIST_FOREACH(old_alloc, &s->cluster_allocs, next_in_flight) {
 830
 831         uint64_t start = guest_offset;
 832         uint64_t end = start + bytes;
 833         uint64_t old_start = l2meta_cow_start(old_alloc);
 834         uint64_t old_end = l2meta_cow_end(old_alloc);
 835
 836         if (end <= old_start || start >= old_end) {
 837             /* No intersection */
 838         } else {
 839             if (start < old_start) {
 840                 /* Stop at the start of a running allocation */
 841                 bytes = old_start - start;
 842             } else {
 843                 bytes = 0;
 844             }
 845
 846             /* Stop if already an l2meta exists. After yielding, it wouldn't
 847              * be valid any more, so we'd have to clean up the old L2Metas
 848              * and deal with requests depending on them before starting to
 849              * gather new ones. Not worth the trouble. */
 850             if (bytes == 0 && *m) {
 851                 *cur_bytes = 0;
 852                 return 0;
 853             }
 854
 855             if (bytes == 0) {
 856                 /* Wait for the dependency to complete. We need to recheck
 857                  * the free/allocated clusters when we continue. */
 858                 qemu_co_mutex_unlock(&s->lock);
 859                 qemu_co_queue_wait(&old_alloc->dependent_requests);
 860                 qemu_co_mutex_lock(&s->lock);
 861                 return -EAGAIN;
 862             }
 863         }
 864     }
 865
 866     /* Make sure that existing clusters and new allocations are only used up to
 867      * the next dependency if we shortened the request above */
 868     *cur_bytes = bytes;
 869
 870     return 0;
 871 }
 872
 873 /*
 874  * Checks how many already allocated clusters that don't require a copy on
 875  * write there are at the given guest_offset (up to *bytes). If
 876  * *host_offset is not zero, only physically contiguous clusters beginning at
 877  * this host offset are counted.
 878  *
 879  * Note that guest_offset may not be cluster aligned. In this case, the
 880  * returned *host_offset points to exact byte referenced by guest_offset and
 881  * therefore isn't cluster aligned as well.
 882  *
 883  * Returns:
 884  *   0:     if no allocated clusters are available at the given offset.
 885  *          *bytes is normally unchanged. It is set to 0 if the cluster
 886  *          is allocated and doesn't need COW, but doesn't have the right
 887  *          physical offset.
 888  *
 889  *   1:     if allocated clusters that don't require a COW are available at
 890  *          the requested offset. *bytes may have decreased and describes
 891  *          the length of the area that can be written to.
 892  *
 893  *  -errno: in error cases
 894  */
 895 static int handle_copied(BlockDriverState *bs, uint64_t guest_offset,
 896     uint64_t *host_offset, uint64_t *bytes, QCowL2Meta **m)
 897 {
 898     BDRVQcowState *s = bs->opaque;
 899     int l2_index;
 900     uint64_t cluster_offset;
 901     uint64_t *l2_table;
 902     unsigned int nb_clusters;
 903     unsigned int keep_clusters;
 904     int ret, pret;
 905
 906     trace_qcow2_handle_copied(qemu_coroutine_self(), guest_offset, *host_offset,
 907                               *bytes);
 908
 909     assert(*host_offset == 0 ||    offset_into_cluster(s, guest_offset)
 910                                 == offset_into_cluster(s, *host_offset));
 911
 912     /*
 913      * Calculate the number of clusters to look for. We stop at L2 table
 914      * boundaries to keep things simple.
 915      */
 916     nb_clusters =
 917         size_to_clusters(s, offset_into_cluster(s, guest_offset) + *bytes);
 918
 919     l2_index = offset_to_l2_index(s, guest_offset);
 920     nb_clusters = MIN(nb_clusters, s->l2_size - l2_index);
 921
 922     /* Find L2 entry for the first involved cluster */
 923     ret = get_cluster_table(bs, guest_offset, &l2_table, &l2_index);
 924     if (ret < 0) {
 925         return ret;
 926     }
 927
 928     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 929
 930     /* Check how many clusters are already allocated and don't need COW */
 931     if (qcow2_get_cluster_type(cluster_offset) == QCOW2_CLUSTER_NORMAL
 932         && (cluster_offset & QCOW_OFLAG_COPIED))
 933     {
 934         /* If a specific host_offset is required, check it */
 935         bool offset_matches =
 936             (cluster_offset & L2E_OFFSET_MASK) == *host_offset;
 937
 938         if (*host_offset != 0 && !offset_matches) {
 939             *bytes = 0;
 940             ret = 0;
 941             goto out;
 942         }
 943
 944         /* We keep all QCOW_OFLAG_COPIED clusters */
 945         keep_clusters =
 946             count_contiguous_clusters(nb_clusters, s->cluster_size,
 947                                       &l2_table[l2_index],
 948                                       QCOW_OFLAG_COPIED | QCOW_OFLAG_ZERO);
 949         assert(keep_clusters <= nb_clusters);
 950
 951         *bytes = MIN(*bytes,
 952                  keep_clusters * s->cluster_size
 953                  - offset_into_cluster(s, guest_offset));
 954
 955         ret = 1;
 956     } else {
 957         ret = 0;
 958     }
 959
 960     /* Cleanup */
 961 out:
 962     pret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
 963     if (pret < 0) {
 964         return pret;
 965     }
 966
 967     /* Only return a host offset if we actually made progress. Otherwise we
 968      * would make requirements for handle_alloc() that it can't fulfill */
 969     if (ret) {
 970         *host_offset = (cluster_offset & L2E_OFFSET_MASK)
 971                      + offset_into_cluster(s, guest_offset);
 972     }
 973
 974     return ret;
 975 }
 976
 977 /*
 978  * Allocates new clusters for the given guest_offset.
 979  *
 980  * At most *nb_clusters are allocated, and on return *nb_clusters is updated to
 981  * contain the number of clusters that have been allocated and are contiguous
 982  * in the image file.
 983  *
 984  * If *host_offset is non-zero, it specifies the offset in the image file at
 985  * which the new clusters must start. *nb_clusters can be 0 on return in this
 986  * case if the cluster at host_offset is already in use. If *host_offset is
 987  * zero, the clusters can be allocated anywhere in the image file.
 988  *
 989  * *host_offset is updated to contain the offset into the image file at which
 990  * the first allocated cluster starts.
 991  *
 992  * Return 0 on success and -errno in error cases. -EAGAIN means that the
 993  * function has been waiting for another request and the allocation must be
 994  * restarted, but the whole request should not be failed.
 995  */
 996 static int do_alloc_cluster_offset(BlockDriverState *bs, uint64_t guest_offset,
 997     uint64_t *host_offset, unsigned int *nb_clusters)
 998 {
 999     BDRVQcowState *s = bs->opaque;
1000
1001     trace_qcow2_do_alloc_clusters_offset(qemu_coroutine_self(), guest_offset,
1002                                          *host_offset, *nb_clusters);
1003
1004     /* Allocate new clusters */
1005     trace_qcow2_cluster_alloc_phys(qemu_coroutine_self());
1006     if (*host_offset == 0) {
1007         int64_t cluster_offset =
1008             qcow2_alloc_clusters(bs, *nb_clusters * s->cluster_size);
1009         if (cluster_offset < 0) {
1010             return cluster_offset;
1011         }
1012         *host_offset = cluster_offset;
1013         return 0;
1014     } else {
1015         int ret = qcow2_alloc_clusters_at(bs, *host_offset, *nb_clusters);
1016         if (ret < 0) {
1017             return ret;
1018         }
1019         *nb_clusters = ret;
1020         return 0;
1021     }
1022 }
1023
1024 /*
1025  * Allocates new clusters for an area that either is yet unallocated or needs a
1026  * copy on write. If *host_offset is non-zero, clusters are only allocated if
1027  * the new allocation can match the specified host offset.
1028  *
1029  * Note that guest_offset may not be cluster aligned. In this case, the
1030  * returned *host_offset points to exact byte referenced by guest_offset and
1031  * therefore isn't cluster aligned as well.
1032  *
1033  * Returns:
1034  *   0:     if no clusters could be allocated. *bytes is set to 0,
1035  *          *host_offset is left unchanged.
1036  *
1037  *   1:     if new clusters were allocated. *bytes may be decreased if the
1038  *          new allocation doesn't cover all of the requested area.
1039  *          *host_offset is updated to contain the host offset of the first
1040  *          newly allocated cluster.
1041  *
1042  *  -errno: in error cases
1043  */
1044 static int handle_alloc(BlockDriverState *bs, uint64_t guest_offset,
1045     uint64_t *host_offset, uint64_t *bytes, QCowL2Meta **m)
1046 {
1047     BDRVQcowState *s = bs->opaque;
1048     int l2_index;
1049     uint64_t *l2_table;
1050     uint64_t entry;
1051     unsigned int nb_clusters;
1052     int ret;
1053
1054     uint64_t alloc_cluster_offset;
1055
1056     trace_qcow2_handle_alloc(qemu_coroutine_self(), guest_offset, *host_offset,
1057                              *bytes);
1058     assert(*bytes > 0);
1059
1060     /*
1061      * Calculate the number of clusters to look for. We stop at L2 table
1062      * boundaries to keep things simple.
1063      */
1064     nb_clusters =
1065         size_to_clusters(s, offset_into_cluster(s, guest_offset) + *bytes);
1066
1067     l2_index = offset_to_l2_index(s, guest_offset);
1068     nb_clusters = MIN(nb_clusters, s->l2_size - l2_index);
1069
1070     /* Find L2 entry for the first involved cluster */
1071     ret = get_cluster_table(bs, guest_offset, &l2_table, &l2_index);
1072     if (ret < 0) {
1073         return ret;
1074     }
1075
1076     entry = be64_to_cpu(l2_table[l2_index]);
1077
1078     /* For the moment, overwrite compressed clusters one by one */
1079     if (entry & QCOW_OFLAG_COMPRESSED) {
1080         nb_clusters = 1;
1081     } else {
1082         nb_clusters = count_cow_clusters(s, nb_clusters, l2_table, l2_index);
1083     }
1084
1085     /* This function is only called when there were no non-COW clusters, so if
1086      * we can't find any unallocated or COW clusters either, something is
1087      * wrong with our code. */
1088     assert(nb_clusters > 0);
1089
1090     ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
1091     if (ret < 0) {
1092         return ret;
1093     }
1094
1095     /* Allocate, if necessary at a given offset in the image file */
1096     alloc_cluster_offset = start_of_cluster(s, *host_offset);
1097     ret = do_alloc_cluster_offset(bs, guest_offset, &alloc_cluster_offset,
1098                                   &nb_clusters);
1099     if (ret < 0) {
1100         goto fail;
1101     }
1102
1103     /* Can't extend contiguous allocation */
1104     if (nb_clusters == 0) {
1105         *bytes = 0;
1106         return 0;
1107     }
1108
1109     /*
1110      * Save info needed for meta data update.
1111      *
1112      * requested_sectors: Number of sectors from the start of the first
1113      * newly allocated cluster to the end of the (possibly shortened
1114      * before) write request.
1115      *
1116      * avail_sectors: Number of sectors from the start of the first
1117      * newly allocated to the end of the last newly allocated cluster.
1118      *
1119      * nb_sectors: The number of sectors from the start of the first
1120      * newly allocated cluster to the end of the area that the write
1121      * request actually writes to (excluding COW at the end)
1122      */
1123     int requested_sectors =
1124         (*bytes + offset_into_cluster(s, guest_offset))
1125         >> BDRV_SECTOR_BITS;
1126     int avail_sectors = nb_clusters
1127                         << (s->cluster_bits - BDRV_SECTOR_BITS);
1128     int alloc_n_start = offset_into_cluster(s, guest_offset)
1129                         >> BDRV_SECTOR_BITS;
1130     int nb_sectors = MIN(requested_sectors, avail_sectors);
1131     QCowL2Meta *old_m = *m;
1132
1133     *m = g_malloc0(sizeof(**m));
1134
1135     **m = (QCowL2Meta) {
1136         .next           = old_m,
1137
1138         .alloc_offset   = alloc_cluster_offset,
1139         .offset         = start_of_cluster(s, guest_offset),
1140         .nb_clusters    = nb_clusters,
1141         .nb_available   = nb_sectors,
1142
1143         .cow_start = {
1144             .offset     = 0,
1145             .nb_sectors = alloc_n_start,
1146         },
1147         .cow_end = {
1148             .offset     = nb_sectors * BDRV_SECTOR_SIZE,
1149             .nb_sectors = avail_sectors - nb_sectors,
1150         },
1151     };
1152     qemu_co_queue_init(&(*m)->dependent_requests);
1153     QLIST_INSERT_HEAD(&s->cluster_allocs, *m, next_in_flight);
1154
1155     *host_offset = alloc_cluster_offset + offset_into_cluster(s, guest_offset);
1156     *bytes = MIN(*bytes, (nb_sectors * BDRV_SECTOR_SIZE)
1157                          - offset_into_cluster(s, guest_offset));
1158     assert(*bytes != 0);
1159
1160     return 1;
1161
1162 fail:
1163     if (*m && (*m)->nb_clusters > 0) {
1164         QLIST_REMOVE(*m, next_in_flight);
1165     }
1166     return ret;
1167 }
1168
1169 /*
1170  * alloc_cluster_offset
1171  *
1172  * For a given offset on the virtual disk, find the cluster offset in qcow2
1173  * file. If the offset is not found, allocate a new cluster.
1174  *
1175  * If the cluster was already allocated, m->nb_clusters is set to 0 and
1176  * other fields in m are meaningless.
1177  *
1178  * If the cluster is newly allocated, m->nb_clusters is set to the number of
1179  * contiguous clusters that have been allocated. In this case, the other
1180  * fields of m are valid and contain information about the first allocated
1181  * cluster.
1182  *
1183  * If the request conflicts with another write request in flight, the coroutine
1184  * is queued and will be reentered when the dependency has completed.
1185  *
1186  * Return 0 on success and -errno in error cases
1187  */
1188 int qcow2_alloc_cluster_offset(BlockDriverState *bs, uint64_t offset,
1189     int *num, uint64_t *host_offset, QCowL2Meta **m)
1190 {
1191     BDRVQcowState *s = bs->opaque;
1192     uint64_t start, remaining;
1193     uint64_t cluster_offset;
1194     uint64_t cur_bytes;
1195     int ret;
1196
1197     trace_qcow2_alloc_clusters_offset(qemu_coroutine_self(), offset, *num);
1198
1199     assert((offset & ~BDRV_SECTOR_MASK) == 0);
1200
1201 again:
1202     start = offset;
1203     remaining = *num << BDRV_SECTOR_BITS;
1204     cluster_offset = 0;
1205     *host_offset = 0;
1206     cur_bytes = 0;
1207     *m = NULL;
1208
1209     while (true) {
1210
1211         if (!*host_offset) {
1212             *host_offset = start_of_cluster(s, cluster_offset);
1213         }
1214
1215         assert(remaining >= cur_bytes);
1216
1217         start           += cur_bytes;
1218         remaining       -= cur_bytes;
1219         cluster_offset  += cur_bytes;
1220
1221         if (remaining == 0) {
1222             break;
1223         }
1224
1225         cur_bytes = remaining;
1226
1227         /*
1228          * Now start gathering as many contiguous clusters as possible:
1229          *
1230          * 1. Check for overlaps with in-flight allocations
1231          *
1232          *      a) Overlap not in the first cluster -> shorten this request and
1233          *         let the caller handle the rest in its next loop iteration.
1234          *
1235          *      b) Real overlaps of two requests. Yield and restart the search
1236          *         for contiguous clusters (the situation could have changed
1237          *         while we were sleeping)
1238          *
1239          *      c) TODO: Request starts in the same cluster as the in-flight
1240          *         allocation ends. Shorten the COW of the in-fight allocation,
1241          *         set cluster_offset to write to the same cluster and set up
1242          *         the right synchronisation between the in-flight request and
1243          *         the new one.
1244          */
1245         ret = handle_dependencies(bs, start, &cur_bytes, m);
1246         if (ret == -EAGAIN) {
1247             /* Currently handle_dependencies() doesn't yield if we already had
1248              * an allocation. If it did, we would have to clean up the L2Meta
1249              * structs before starting over. */
1250             assert(*m == NULL);
1251             goto again;
1252         } else if (ret < 0) {
1253             return ret;
1254         } else if (cur_bytes == 0) {
1255             break;
1256         } else {
1257             /* handle_dependencies() may have decreased cur_bytes (shortened
1258              * the allocations below) so that the next dependency is processed
1259              * correctly during the next loop iteration. */
1260         }
1261
1262         /*
1263          * 2. Count contiguous COPIED clusters.
1264          */
1265         ret = handle_copied(bs, start, &cluster_offset, &cur_bytes, m);
1266         if (ret < 0) {
1267             return ret;
1268         } else if (ret) {
1269             continue;
1270         } else if (cur_bytes == 0) {
1271             break;
1272         }
1273
1274         /*
1275          * 3. If the request still hasn't completed, allocate new clusters,
1276          *    considering any cluster_offset of steps 1c or 2.
1277          */
1278         ret = handle_alloc(bs, start, &cluster_offset, &cur_bytes, m);
1279         if (ret < 0) {
1280             return ret;
1281         } else if (ret) {
1282             continue;
1283         } else {
1284             assert(cur_bytes == 0);
1285             break;
1286         }
1287     }
1288
1289     *num -= remaining >> BDRV_SECTOR_BITS;
1290     assert(*num > 0);
1291     assert(*host_offset != 0);
1292
1293     return 0;
1294 }
1295
1296 static int decompress_buffer(uint8_t *out_buf, int out_buf_size,
1297                              const uint8_t *buf, int buf_size)
1298 {
1299     z_stream strm1, *strm = &strm1;
1300     int ret, out_len;
1301
1302     memset(strm, 0, sizeof(*strm));
1303
1304     strm->next_in = (uint8_t *)buf;
1305     strm->avail_in = buf_size;
1306     strm->next_out = out_buf;
1307     strm->avail_out = out_buf_size;
1308
1309     ret = inflateInit2(strm, -12);
1310     if (ret != Z_OK)
1311         return -1;
1312     ret = inflate(strm, Z_FINISH);
1313     out_len = strm->next_out - out_buf;
1314     if ((ret != Z_STREAM_END && ret != Z_BUF_ERROR) ||
1315         out_len != out_buf_size) {
1316         inflateEnd(strm);
1317         return -1;
1318     }
1319     inflateEnd(strm);
1320     return 0;
1321 }
1322
1323 int qcow2_decompress_cluster(BlockDriverState *bs, uint64_t cluster_offset)
1324 {
1325     BDRVQcowState *s = bs->opaque;
1326     int ret, csize, nb_csectors, sector_offset;
1327     uint64_t coffset;
1328
1329     coffset = cluster_offset & s->cluster_offset_mask;
1330     if (s->cluster_cache_offset != coffset) {
1331         nb_csectors = ((cluster_offset >> s->csize_shift) & s->csize_mask) + 1;
1332         sector_offset = coffset & 511;
1333         csize = nb_csectors * 512 - sector_offset;
1334         BLKDBG_EVENT(bs->file, BLKDBG_READ_COMPRESSED);
1335         ret = bdrv_read(bs->file, coffset >> 9, s->cluster_data, nb_csectors);
1336         if (ret < 0) {
1337             return ret;
1338         }
1339         if (decompress_buffer(s->cluster_cache, s->cluster_size,
1340                               s->cluster_data + sector_offset, csize) < 0) {
1341             return -EIO;
1342         }
1343         s->cluster_cache_offset = coffset;
1344     }
1345     return 0;
1346 }
1347
1348 /*
1349  * This discards as many clusters of nb_clusters as possible at once (i.e.
1350  * all clusters in the same L2 table) and returns the number of discarded
1351  * clusters.
1352  */
1353 static int discard_single_l2(BlockDriverState *bs, uint64_t offset,
1354     unsigned int nb_clusters, enum qcow2_discard_type type)
1355 {
1356     BDRVQcowState *s = bs->opaque;
1357     uint64_t *l2_table;
1358     int l2_index;
1359     int ret;
1360     int i;
1361
1362     ret = get_cluster_table(bs, offset, &l2_table, &l2_index);
1363     if (ret < 0) {
1364         return ret;
1365     }
1366
1367     /* Limit nb_clusters to one L2 table */
1368     nb_clusters = MIN(nb_clusters, s->l2_size - l2_index);
1369
1370     for (i = 0; i < nb_clusters; i++) {
1371         uint64_t old_offset;
1372
1373         old_offset = be64_to_cpu(l2_table[l2_index + i]);
1374
1375         /*
1376          * Make sure that a discarded area reads back as zeroes for v3 images
1377          * (we cannot do it for v2 without actually writing a zero-filled
1378          * buffer). We can skip the operation if the cluster is already marked
1379          * as zero, or if it's unallocated and we don't have a backing file.
1380          *
1381          * TODO We might want to use bdrv_get_block_status(bs) here, but we're
1382          * holding s->lock, so that doesn't work today.
1383          */
1384         if (old_offset & QCOW_OFLAG_ZERO) {
1385             continue;
1386         }
1387
1388         if ((old_offset & L2E_OFFSET_MASK) == 0 && !bs->backing_hd) {
1389             continue;
1390         }
1391
1392         /* First remove L2 entries */
1393         qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
1394         if (s->qcow_version >= 3) {
1395             l2_table[l2_index + i] = cpu_to_be64(QCOW_OFLAG_ZERO);
1396         } else {
1397             l2_table[l2_index + i] = cpu_to_be64(0);
1398         }
1399
1400         /* Then decrease the refcount */
1401         qcow2_free_any_clusters(bs, old_offset, 1, type);
1402     }
1403
1404     ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
1405     if (ret < 0) {
1406         return ret;
1407     }
1408
1409     return nb_clusters;
1410 }
1411
1412 int qcow2_discard_clusters(BlockDriverState *bs, uint64_t offset,
1413     int nb_sectors, enum qcow2_discard_type type)
1414 {
1415     BDRVQcowState *s = bs->opaque;
1416     uint64_t end_offset;
1417     unsigned int nb_clusters;
1418     int ret;
1419
1420     end_offset = offset + (nb_sectors << BDRV_SECTOR_BITS);
1421
1422     /* Round start up and end down */
1423     offset = align_offset(offset, s->cluster_size);
1424     end_offset = start_of_cluster(s, end_offset);
1425
1426     if (offset > end_offset) {
1427         return 0;
1428     }
1429
1430     nb_clusters = size_to_clusters(s, end_offset - offset);
1431
1432     s->cache_discards = true;
1433
1434     /* Each L2 table is handled by its own loop iteration */
1435     while (nb_clusters > 0) {
1436         ret = discard_single_l2(bs, offset, nb_clusters, type);
1437         if (ret < 0) {
1438             goto fail;
1439         }
1440
1441         nb_clusters -= ret;
1442         offset += (ret * s->cluster_size);
1443     }
1444
1445     ret = 0;
1446 fail:
1447     s->cache_discards = false;
1448     qcow2_process_discards(bs, ret);
1449
1450     return ret;
1451 }
1452
1453 /*
1454  * This zeroes as many clusters of nb_clusters as possible at once (i.e.
1455  * all clusters in the same L2 table) and returns the number of zeroed
1456  * clusters.
1457  */
1458 static int zero_single_l2(BlockDriverState *bs, uint64_t offset,
1459     unsigned int nb_clusters)
1460 {
1461     BDRVQcowState *s = bs->opaque;
1462     uint64_t *l2_table;
1463     int l2_index;
1464     int ret;
1465     int i;
1466
1467     ret = get_cluster_table(bs, offset, &l2_table, &l2_index);
1468     if (ret < 0) {
1469         return ret;
1470     }
1471
1472     /* Limit nb_clusters to one L2 table */
1473     nb_clusters = MIN(nb_clusters, s->l2_size - l2_index);
1474
1475     for (i = 0; i < nb_clusters; i++) {
1476         uint64_t old_offset;
1477
1478         old_offset = be64_to_cpu(l2_table[l2_index + i]);
1479
1480         /* Update L2 entries */
1481         qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
1482         if (old_offset & QCOW_OFLAG_COMPRESSED) {
1483             l2_table[l2_index + i] = cpu_to_be64(QCOW_OFLAG_ZERO);
1484             qcow2_free_any_clusters(bs, old_offset, 1, QCOW2_DISCARD_REQUEST);
1485         } else {
1486             l2_table[l2_index + i] |= cpu_to_be64(QCOW_OFLAG_ZERO);
1487         }
1488     }
1489
1490     ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
1491     if (ret < 0) {
1492         return ret;
1493     }
1494
1495     return nb_clusters;
1496 }
1497
1498 int qcow2_zero_clusters(BlockDriverState *bs, uint64_t offset, int nb_sectors)
1499 {
1500     BDRVQcowState *s = bs->opaque;
1501     unsigned int nb_clusters;
1502     int ret;
1503
1504     /* The zero flag is only supported by version 3 and newer */
1505     if (s->qcow_version < 3) {
1506         return -ENOTSUP;
1507     }
1508
1509     /* Each L2 table is handled by its own loop iteration */
1510     nb_clusters = size_to_clusters(s, nb_sectors << BDRV_SECTOR_BITS);
1511
1512     s->cache_discards = true;
1513
1514     while (nb_clusters > 0) {
1515         ret = zero_single_l2(bs, offset, nb_clusters);
1516         if (ret < 0) {
1517             goto fail;
1518         }
1519
1520         nb_clusters -= ret;
1521         offset += (ret * s->cluster_size);
1522     }
1523
1524     ret = 0;
1525 fail:
1526     s->cache_discards = false;
1527     qcow2_process_discards(bs, ret);
1528
1529     return ret;
1530 }
1531
1532 /*
1533  * Expands all zero clusters in a specific L1 table (or deallocates them, for
1534  * non-backed non-pre-allocated zero clusters).
1535  *
1536  * expanded_clusters is a bitmap where every bit corresponds to one cluster in
1537  * the image file; a bit gets set if the corresponding cluster has been used for
1538  * zero expansion (i.e., has been filled with zeroes and is referenced from an
1539  * L2 table). nb_clusters contains the total cluster count of the image file,
1540  * i.e., the number of bits in expanded_clusters.
1541  */
1542 static int expand_zero_clusters_in_l1(BlockDriverState *bs, uint64_t *l1_table,
1543                                       int l1_size, uint8_t **expanded_clusters,
1544                                       uint64_t *nb_clusters)
1545 {
1546     BDRVQcowState *s = bs->opaque;
1547     bool is_active_l1 = (l1_table == s->l1_table);
1548     uint64_t *l2_table = NULL;
1549     int ret;
1550     int i, j;
1551
1552     if (!is_active_l1) {
1553         /* inactive L2 tables require a buffer to be stored in when loading
1554          * them from disk */
1555         l2_table = qemu_blockalign(bs, s->cluster_size);
1556     }
1557
1558     for (i = 0; i < l1_size; i++) {
1559         uint64_t l2_offset = l1_table[i] & L1E_OFFSET_MASK;
1560         bool l2_dirty = false;
1561
1562         if (!l2_offset) {
1563             /* unallocated */
1564             continue;
1565         }
1566
1567         if (is_active_l1) {
1568             /* get active L2 tables from cache */
1569             ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset,
1570                     (void **)&l2_table);
1571         } else {
1572             /* load inactive L2 tables from disk */
1573             ret = bdrv_read(bs->file, l2_offset / BDRV_SECTOR_SIZE,
1574                     (void *)l2_table, s->cluster_sectors);
1575         }
1576         if (ret < 0) {
1577             goto fail;
1578         }
1579
1580         for (j = 0; j < s->l2_size; j++) {
1581             uint64_t l2_entry = be64_to_cpu(l2_table[j]);
1582             int64_t offset = l2_entry & L2E_OFFSET_MASK, cluster_index;
1583             int cluster_type = qcow2_get_cluster_type(l2_entry);
1584             bool preallocated = offset != 0;
1585
1586             if (cluster_type == QCOW2_CLUSTER_NORMAL) {
1587                 cluster_index = offset >> s->cluster_bits;
1588                 assert((cluster_index >= 0) && (cluster_index < *nb_clusters));
1589                 if ((*expanded_clusters)[cluster_index / 8] &
1590                     (1 << (cluster_index % 8))) {
1591                     /* Probably a shared L2 table; this cluster was a zero
1592                      * cluster which has been expanded, its refcount
1593                      * therefore most likely requires an update. */
1594                     ret = qcow2_update_cluster_refcount(bs, cluster_index, 1,
1595                                                         QCOW2_DISCARD_NEVER);
1596                     if (ret < 0) {
1597                         goto fail;
1598                     }
1599                     /* Since we just increased the refcount, the COPIED flag may
1600                      * no longer be set. */
1601                     l2_table[j] = cpu_to_be64(l2_entry & ~QCOW_OFLAG_COPIED);
1602                     l2_dirty = true;
1603                 }
1604                 continue;
1605             }
1606             else if (qcow2_get_cluster_type(l2_entry) != QCOW2_CLUSTER_ZERO) {
1607                 continue;
1608             }
1609
1610             if (!preallocated) {
1611                 if (!bs->backing_hd) {
1612                     /* not backed; therefore we can simply deallocate the
1613                      * cluster */
1614                     l2_table[j] = 0;
1615                     l2_dirty = true;
1616                     continue;
1617                 }
1618
1619                 offset = qcow2_alloc_clusters(bs, s->cluster_size);
1620                 if (offset < 0) {
1621                     ret = offset;
1622                     goto fail;
1623                 }
1624             }
1625
1626             ret = qcow2_pre_write_overlap_check(bs, 0, offset, s->cluster_size);
1627             if (ret < 0) {
1628                 if (!preallocated) {
1629                     qcow2_free_clusters(bs, offset, s->cluster_size,
1630                                         QCOW2_DISCARD_ALWAYS);
1631                 }
1632                 goto fail;
1633             }
1634
1635             ret = bdrv_write_zeroes(bs->file, offset / BDRV_SECTOR_SIZE,
1636                                     s->cluster_sectors, 0);
1637             if (ret < 0) {
1638                 if (!preallocated) {
1639                     qcow2_free_clusters(bs, offset, s->cluster_size,
1640                                         QCOW2_DISCARD_ALWAYS);
1641                 }
1642                 goto fail;
1643             }
1644
1645             l2_table[j] = cpu_to_be64(offset | QCOW_OFLAG_COPIED);
1646             l2_dirty = true;
1647
1648             cluster_index = offset >> s->cluster_bits;
1649
1650             if (cluster_index >= *nb_clusters) {
1651                 uint64_t old_bitmap_size = (*nb_clusters + 7) / 8;
1652                 uint64_t new_bitmap_size;
1653                 /* The offset may lie beyond the old end of the underlying image
1654                  * file for growable files only */
1655                 assert(bs->file->growable);
1656                 *nb_clusters = size_to_clusters(s, bs->file->total_sectors *
1657                                                 BDRV_SECTOR_SIZE);
1658                 new_bitmap_size = (*nb_clusters + 7) / 8;
1659                 *expanded_clusters = g_realloc(*expanded_clusters,
1660                                                new_bitmap_size);
1661                 /* clear the newly allocated space */
1662                 memset(&(*expanded_clusters)[old_bitmap_size], 0,
1663                        new_bitmap_size - old_bitmap_size);
1664             }
1665
1666             assert((cluster_index >= 0) && (cluster_index < *nb_clusters));
1667             (*expanded_clusters)[cluster_index / 8] |= 1 << (cluster_index % 8);
1668         }
1669
1670         if (is_active_l1) {
1671             if (l2_dirty) {
1672                 qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
1673                 qcow2_cache_depends_on_flush(s->l2_table_cache);
1674             }
1675             ret = qcow2_cache_put(bs, s->l2_table_cache, (void **)&l2_table);
1676             if (ret < 0) {
1677                 l2_table = NULL;
1678                 goto fail;
1679             }
1680         } else {
1681             if (l2_dirty) {
1682                 ret = qcow2_pre_write_overlap_check(bs,
1683                         QCOW2_OL_INACTIVE_L2 | QCOW2_OL_ACTIVE_L2, l2_offset,
1684                         s->cluster_size);
1685                 if (ret < 0) {
1686                     goto fail;
1687                 }
1688
1689                 ret = bdrv_write(bs->file, l2_offset / BDRV_SECTOR_SIZE,
1690                         (void *)l2_table, s->cluster_sectors);
1691                 if (ret < 0) {
1692                     goto fail;
1693                 }
1694             }
1695         }
1696     }
1697
1698     ret = 0;
1699
1700 fail:
1701     if (l2_table) {
1702         if (!is_active_l1) {
1703             qemu_vfree(l2_table);
1704         } else {
1705             if (ret < 0) {
1706                 qcow2_cache_put(bs, s->l2_table_cache, (void **)&l2_table);
1707             } else {
1708                 ret = qcow2_cache_put(bs, s->l2_table_cache,
1709                         (void **)&l2_table);
1710             }
1711         }
1712     }
1713     return ret;
1714 }
1715
1716 /*
1717  * For backed images, expands all zero clusters on the image. For non-backed
1718  * images, deallocates all non-pre-allocated zero clusters (and claims the
1719  * allocation for pre-allocated ones). This is important for downgrading to a
1720  * qcow2 version which doesn't yet support metadata zero clusters.
1721  */
1722 int qcow2_expand_zero_clusters(BlockDriverState *bs)
1723 {
1724     BDRVQcowState *s = bs->opaque;
1725     uint64_t *l1_table = NULL;
1726     uint64_t nb_clusters;
1727     uint8_t *expanded_clusters;
1728     int ret;
1729     int i, j;
1730
1731     nb_clusters = size_to_clusters(s, bs->file->total_sectors *
1732                                    BDRV_SECTOR_SIZE);
1733     expanded_clusters = g_malloc0((nb_clusters + 7) / 8);
1734
1735     ret = expand_zero_clusters_in_l1(bs, s->l1_table, s->l1_size,
1736                                      &expanded_clusters, &nb_clusters);
1737     if (ret < 0) {
1738         goto fail;
1739     }
1740
1741     /* Inactive L1 tables may point to active L2 tables - therefore it is
1742      * necessary to flush the L2 table cache before trying to access the L2
1743      * tables pointed to by inactive L1 entries (else we might try to expand
1744      * zero clusters that have already been expanded); furthermore, it is also
1745      * necessary to empty the L2 table cache, since it may contain tables which
1746      * are now going to be modified directly on disk, bypassing the cache.
1747      * qcow2_cache_empty() does both for us. */
1748     ret = qcow2_cache_empty(bs, s->l2_table_cache);
1749     if (ret < 0) {
1750         goto fail;
1751     }
1752
1753     for (i = 0; i < s->nb_snapshots; i++) {
1754         int l1_sectors = (s->snapshots[i].l1_size * sizeof(uint64_t) +
1755                 BDRV_SECTOR_SIZE - 1) / BDRV_SECTOR_SIZE;
1756
1757         l1_table = g_realloc(l1_table, l1_sectors * BDRV_SECTOR_SIZE);
1758
1759         ret = bdrv_read(bs->file, s->snapshots[i].l1_table_offset /
1760                 BDRV_SECTOR_SIZE, (void *)l1_table, l1_sectors);
1761         if (ret < 0) {
1762             goto fail;
1763         }
1764
1765         for (j = 0; j < s->snapshots[i].l1_size; j++) {
1766             be64_to_cpus(&l1_table[j]);
1767         }
1768
1769         ret = expand_zero_clusters_in_l1(bs, l1_table, s->snapshots[i].l1_size,
1770                                          &expanded_clusters, &nb_clusters);
1771         if (ret < 0) {
1772             goto fail;
1773         }
1774     }
1775
1776     ret = 0;
1777
1778 fail:
1779     g_free(expanded_clusters);
1780     g_free(l1_table);
1781     return ret;
1782 }