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