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