block/qcow2.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 #include "qemu-common.h"
  25 #include "block_int.h"
  26 #include "module.h"
  27 #include <zlib.h>
  28 #include "aes.h"
  29
  30 /*
  31   Differences with QCOW:
  32
  33   - Support for multiple incremental snapshots.
  34   - Memory management by reference counts.
  35   - Clusters which have a reference count of one have the bit
  36     QCOW_OFLAG_COPIED to optimize write performance.
  37   - Size of compressed clusters is stored in sectors to reduce bit usage
  38     in the cluster offsets.
  39   - Support for storing additional data (such as the VM state) in the
  40     snapshots.
  41   - If a backing store is used, the cluster size is not constrained
  42     (could be backported to QCOW).
  43   - L2 tables have always a size of one cluster.
  44 */
  45
  46 //#define DEBUG_ALLOC
  47 //#define DEBUG_ALLOC2
  48 //#define DEBUG_EXT
  49
  50 #define QCOW_MAGIC (('Q' << 24) | ('F' << 16) | ('I' << 8) | 0xfb)
  51 #define QCOW_VERSION 2
  52
  53 #define QCOW_CRYPT_NONE 0
  54 #define QCOW_CRYPT_AES  1
  55
  56 #define QCOW_MAX_CRYPT_CLUSTERS 32
  57
  58 /* indicate that the refcount of the referenced cluster is exactly one. */
  59 #define QCOW_OFLAG_COPIED     (1LL << 63)
  60 /* indicate that the cluster is compressed (they never have the copied flag) */
  61 #define QCOW_OFLAG_COMPRESSED (1LL << 62)
  62
  63 #define REFCOUNT_SHIFT 1 /* refcount size is 2 bytes */
  64
  65 #define MIN_CLUSTER_BITS 9
  66 #define MAX_CLUSTER_BITS 16
  67
  68 typedef struct QCowHeader {
  69     uint32_t magic;
  70     uint32_t version;
  71     uint64_t backing_file_offset;
  72     uint32_t backing_file_size;
  73     uint32_t cluster_bits;
  74     uint64_t size; /* in bytes */
  75     uint32_t crypt_method;
  76     uint32_t l1_size; /* XXX: save number of clusters instead ? */
  77     uint64_t l1_table_offset;
  78     uint64_t refcount_table_offset;
  79     uint32_t refcount_table_clusters;
  80     uint32_t nb_snapshots;
  81     uint64_t snapshots_offset;
  82 } QCowHeader;
  83
  84
  85 typedef struct {
  86     uint32_t magic;
  87     uint32_t len;
  88 } QCowExtension;
  89 #define  QCOW_EXT_MAGIC_END 0
  90 #define  QCOW_EXT_MAGIC_BACKING_FORMAT 0xE2792ACA
  91
  92
  93 typedef struct __attribute__((packed)) QCowSnapshotHeader {
  94     /* header is 8 byte aligned */
  95     uint64_t l1_table_offset;
  96
  97     uint32_t l1_size;
  98     uint16_t id_str_size;
  99     uint16_t name_size;
 100
 101     uint32_t date_sec;
 102     uint32_t date_nsec;
 103
 104     uint64_t vm_clock_nsec;
 105
 106     uint32_t vm_state_size;
 107     uint32_t extra_data_size; /* for extension */
 108     /* extra data follows */
 109     /* id_str follows */
 110     /* name follows  */
 111 } QCowSnapshotHeader;
 112
 113 #define L2_CACHE_SIZE 16
 114
 115 typedef struct QCowSnapshot {
 116     uint64_t l1_table_offset;
 117     uint32_t l1_size;
 118     char *id_str;
 119     char *name;
 120     uint32_t vm_state_size;
 121     uint32_t date_sec;
 122     uint32_t date_nsec;
 123     uint64_t vm_clock_nsec;
 124 } QCowSnapshot;
 125
 126 typedef struct BDRVQcowState {
 127     BlockDriverState *hd;
 128     int cluster_bits;
 129     int cluster_size;
 130     int cluster_sectors;
 131     int l2_bits;
 132     int l2_size;
 133     int l1_size;
 134     int l1_vm_state_index;
 135     int csize_shift;
 136     int csize_mask;
 137     uint64_t cluster_offset_mask;
 138     uint64_t l1_table_offset;
 139     uint64_t *l1_table;
 140     uint64_t *l2_cache;
 141     uint64_t l2_cache_offsets[L2_CACHE_SIZE];
 142     uint32_t l2_cache_counts[L2_CACHE_SIZE];
 143     uint8_t *cluster_cache;
 144     uint8_t *cluster_data;
 145     uint64_t cluster_cache_offset;
 146
 147     uint64_t *refcount_table;
 148     uint64_t refcount_table_offset;
 149     uint32_t refcount_table_size;
 150     uint64_t refcount_block_cache_offset;
 151     uint16_t *refcount_block_cache;
 152     int64_t free_cluster_index;
 153     int64_t free_byte_offset;
 154
 155     uint32_t crypt_method; /* current crypt method, 0 if no key yet */
 156     uint32_t crypt_method_header;
 157     AES_KEY aes_encrypt_key;
 158     AES_KEY aes_decrypt_key;
 159     uint64_t snapshots_offset;
 160     int snapshots_size;
 161     int nb_snapshots;
 162     QCowSnapshot *snapshots;
 163 } BDRVQcowState;
 164
 165 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset);
 166 static int qcow_read(BlockDriverState *bs, int64_t sector_num,
 167                      uint8_t *buf, int nb_sectors);
 168 static int qcow_read_snapshots(BlockDriverState *bs);
 169 static void qcow_free_snapshots(BlockDriverState *bs);
 170 static int refcount_init(BlockDriverState *bs);
 171 static void refcount_close(BlockDriverState *bs);
 172 static int get_refcount(BlockDriverState *bs, int64_t cluster_index);
 173 static int update_cluster_refcount(BlockDriverState *bs,
 174                                    int64_t cluster_index,
 175                                    int addend);
 176 static void update_refcount(BlockDriverState *bs,
 177                             int64_t offset, int64_t length,
 178                             int addend);
 179 static int64_t alloc_clusters(BlockDriverState *bs, int64_t size);
 180 static int64_t alloc_bytes(BlockDriverState *bs, int size);
 181 static void free_clusters(BlockDriverState *bs,
 182                           int64_t offset, int64_t size);
 183 static int check_refcounts(BlockDriverState *bs);
 184
 185 static int qcow_probe(const uint8_t *buf, int buf_size, const char *filename)
 186 {
 187     const QCowHeader *cow_header = (const void *)buf;
 188
 189     if (buf_size >= sizeof(QCowHeader) &&
 190         be32_to_cpu(cow_header->magic) == QCOW_MAGIC &&
 191         be32_to_cpu(cow_header->version) == QCOW_VERSION)
 192         return 100;
 193     else
 194         return 0;
 195 }
 196
 197
 198 /*
 199  * read qcow2 extension and fill bs
 200  * start reading from start_offset
 201  * finish reading upon magic of value 0 or when end_offset reached
 202  * unknown magic is skipped (future extension this version knows nothing about)
 203  * return 0 upon success, non-0 otherwise
 204  */
 205 static int qcow_read_extensions(BlockDriverState *bs, uint64_t start_offset,
 206                                 uint64_t end_offset)
 207 {
 208     BDRVQcowState *s = bs->opaque;
 209     QCowExtension ext;
 210     uint64_t offset;
 211
 212 #ifdef DEBUG_EXT
 213     printf("qcow_read_extensions: start=%ld end=%ld\n", start_offset, end_offset);
 214 #endif
 215     offset = start_offset;
 216     while (offset < end_offset) {
 217
 218 #ifdef DEBUG_EXT
 219         /* Sanity check */
 220         if (offset > s->cluster_size)
 221             printf("qcow_handle_extension: suspicious offset %lu\n", offset);
 222
 223         printf("attemting to read extended header in offset %lu\n", offset);
 224 #endif
 225
 226         if (bdrv_pread(s->hd, offset, &ext, sizeof(ext)) != sizeof(ext)) {
 227             fprintf(stderr, "qcow_handle_extension: ERROR: pread fail from offset %llu\n",
 228                     (unsigned long long)offset);
 229             return 1;
 230         }
 231         be32_to_cpus(&ext.magic);
 232         be32_to_cpus(&ext.len);
 233         offset += sizeof(ext);
 234 #ifdef DEBUG_EXT
 235         printf("ext.magic = 0x%x\n", ext.magic);
 236 #endif
 237         switch (ext.magic) {
 238         case QCOW_EXT_MAGIC_END:
 239             return 0;
 240
 241         case QCOW_EXT_MAGIC_BACKING_FORMAT:
 242             if (ext.len >= sizeof(bs->backing_format)) {
 243                 fprintf(stderr, "ERROR: ext_backing_format: len=%u too large"
 244                         " (>=%zu)\n",
 245                         ext.len, sizeof(bs->backing_format));
 246                 return 2;
 247             }
 248             if (bdrv_pread(s->hd, offset , bs->backing_format,
 249                            ext.len) != ext.len)
 250                 return 3;
 251             bs->backing_format[ext.len] = '\0';
 252 #ifdef DEBUG_EXT
 253             printf("Qcow2: Got format extension %s\n", bs->backing_format);
 254 #endif
 255             offset += ((ext.len + 7) & ~7);
 256             break;
 257
 258         default:
 259             /* unknown magic -- just skip it */
 260             offset += ((ext.len + 7) & ~7);
 261             break;
 262         }
 263     }
 264
 265     return 0;
 266 }
 267
 268
 269 static int qcow_open(BlockDriverState *bs, const char *filename, int flags)
 270 {
 271     BDRVQcowState *s = bs->opaque;
 272     int len, i, shift, ret;
 273     QCowHeader header;
 274     uint64_t ext_end;
 275
 276     /* Performance is terrible right now with cache=writethrough due mainly
 277      * to reference count updates.  If the user does not explicitly specify
 278      * a caching type, force to writeback caching.
 279      */
 280     if ((flags & BDRV_O_CACHE_DEF)) {
 281         flags |= BDRV_O_CACHE_WB;
 282         flags &= ~BDRV_O_CACHE_DEF;
 283     }
 284     ret = bdrv_file_open(&s->hd, filename, flags);
 285     if (ret < 0)
 286         return ret;
 287     if (bdrv_pread(s->hd, 0, &header, sizeof(header)) != sizeof(header))
 288         goto fail;
 289     be32_to_cpus(&header.magic);
 290     be32_to_cpus(&header.version);
 291     be64_to_cpus(&header.backing_file_offset);
 292     be32_to_cpus(&header.backing_file_size);
 293     be64_to_cpus(&header.size);
 294     be32_to_cpus(&header.cluster_bits);
 295     be32_to_cpus(&header.crypt_method);
 296     be64_to_cpus(&header.l1_table_offset);
 297     be32_to_cpus(&header.l1_size);
 298     be64_to_cpus(&header.refcount_table_offset);
 299     be32_to_cpus(&header.refcount_table_clusters);
 300     be64_to_cpus(&header.snapshots_offset);
 301     be32_to_cpus(&header.nb_snapshots);
 302
 303     if (header.magic != QCOW_MAGIC || header.version != QCOW_VERSION)
 304         goto fail;
 305     if (header.size <= 1 ||
 306         header.cluster_bits < MIN_CLUSTER_BITS ||
 307         header.cluster_bits > MAX_CLUSTER_BITS)
 308         goto fail;
 309     if (header.crypt_method > QCOW_CRYPT_AES)
 310         goto fail;
 311     s->crypt_method_header = header.crypt_method;
 312     if (s->crypt_method_header)
 313         bs->encrypted = 1;
 314     s->cluster_bits = header.cluster_bits;
 315     s->cluster_size = 1 << s->cluster_bits;
 316     s->cluster_sectors = 1 << (s->cluster_bits - 9);
 317     s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */
 318     s->l2_size = 1 << s->l2_bits;
 319     bs->total_sectors = header.size / 512;
 320     s->csize_shift = (62 - (s->cluster_bits - 8));
 321     s->csize_mask = (1 << (s->cluster_bits - 8)) - 1;
 322     s->cluster_offset_mask = (1LL << s->csize_shift) - 1;
 323     s->refcount_table_offset = header.refcount_table_offset;
 324     s->refcount_table_size =
 325         header.refcount_table_clusters << (s->cluster_bits - 3);
 326
 327     s->snapshots_offset = header.snapshots_offset;
 328     s->nb_snapshots = header.nb_snapshots;
 329
 330     /* read the level 1 table */
 331     s->l1_size = header.l1_size;
 332     shift = s->cluster_bits + s->l2_bits;
 333     s->l1_vm_state_index = (header.size + (1LL << shift) - 1) >> shift;
 334     /* the L1 table must contain at least enough entries to put
 335        header.size bytes */
 336     if (s->l1_size < s->l1_vm_state_index)
 337         goto fail;
 338     s->l1_table_offset = header.l1_table_offset;
 339     s->l1_table = qemu_malloc(s->l1_size * sizeof(uint64_t));
 340     if (bdrv_pread(s->hd, s->l1_table_offset, s->l1_table, s->l1_size * sizeof(uint64_t)) !=
 341         s->l1_size * sizeof(uint64_t))
 342         goto fail;
 343     for(i = 0;i < s->l1_size; i++) {
 344         be64_to_cpus(&s->l1_table[i]);
 345     }
 346     /* alloc L2 cache */
 347     s->l2_cache = qemu_malloc(s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t));
 348     s->cluster_cache = qemu_malloc(s->cluster_size);
 349     /* one more sector for decompressed data alignment */
 350     s->cluster_data = qemu_malloc(QCOW_MAX_CRYPT_CLUSTERS * s->cluster_size
 351                                   + 512);
 352     s->cluster_cache_offset = -1;
 353
 354     if (refcount_init(bs) < 0)
 355         goto fail;
 356
 357     /* read qcow2 extensions */
 358     if (header.backing_file_offset)
 359         ext_end = header.backing_file_offset;
 360     else
 361         ext_end = s->cluster_size;
 362     if (qcow_read_extensions(bs, sizeof(header), ext_end))
 363         goto fail;
 364
 365     /* read the backing file name */
 366     if (header.backing_file_offset != 0) {
 367         len = header.backing_file_size;
 368         if (len > 1023)
 369             len = 1023;
 370         if (bdrv_pread(s->hd, header.backing_file_offset, bs->backing_file, len) != len)
 371             goto fail;
 372         bs->backing_file[len] = '\0';
 373     }
 374     if (qcow_read_snapshots(bs) < 0)
 375         goto fail;
 376
 377 #ifdef DEBUG_ALLOC
 378     check_refcounts(bs);
 379 #endif
 380     return 0;
 381
 382  fail:
 383     qcow_free_snapshots(bs);
 384     refcount_close(bs);
 385     qemu_free(s->l1_table);
 386     qemu_free(s->l2_cache);
 387     qemu_free(s->cluster_cache);
 388     qemu_free(s->cluster_data);
 389     bdrv_delete(s->hd);
 390     return -1;
 391 }
 392
 393 static int qcow_set_key(BlockDriverState *bs, const char *key)
 394 {
 395     BDRVQcowState *s = bs->opaque;
 396     uint8_t keybuf[16];
 397     int len, i;
 398
 399     memset(keybuf, 0, 16);
 400     len = strlen(key);
 401     if (len > 16)
 402         len = 16;
 403     /* XXX: we could compress the chars to 7 bits to increase
 404        entropy */
 405     for(i = 0;i < len;i++) {
 406         keybuf[i] = key[i];
 407     }
 408     s->crypt_method = s->crypt_method_header;
 409
 410     if (AES_set_encrypt_key(keybuf, 128, &s->aes_encrypt_key) != 0)
 411         return -1;
 412     if (AES_set_decrypt_key(keybuf, 128, &s->aes_decrypt_key) != 0)
 413         return -1;
 414 #if 0
 415     /* test */
 416     {
 417         uint8_t in[16];
 418         uint8_t out[16];
 419         uint8_t tmp[16];
 420         for(i=0;i<16;i++)
 421             in[i] = i;
 422         AES_encrypt(in, tmp, &s->aes_encrypt_key);
 423         AES_decrypt(tmp, out, &s->aes_decrypt_key);
 424         for(i = 0; i < 16; i++)
 425             printf(" %02x", tmp[i]);
 426         printf("\n");
 427         for(i = 0; i < 16; i++)
 428             printf(" %02x", out[i]);
 429         printf("\n");
 430     }
 431 #endif
 432     return 0;
 433 }
 434
 435 /* The crypt function is compatible with the linux cryptoloop
 436    algorithm for < 4 GB images. NOTE: out_buf == in_buf is
 437    supported */
 438 static void encrypt_sectors(BDRVQcowState *s, int64_t sector_num,
 439                             uint8_t *out_buf, const uint8_t *in_buf,
 440                             int nb_sectors, int enc,
 441                             const AES_KEY *key)
 442 {
 443     union {
 444         uint64_t ll[2];
 445         uint8_t b[16];
 446     } ivec;
 447     int i;
 448
 449     for(i = 0; i < nb_sectors; i++) {
 450         ivec.ll[0] = cpu_to_le64(sector_num);
 451         ivec.ll[1] = 0;
 452         AES_cbc_encrypt(in_buf, out_buf, 512, key,
 453                         ivec.b, enc);
 454         sector_num++;
 455         in_buf += 512;
 456         out_buf += 512;
 457     }
 458 }
 459
 460 static int copy_sectors(BlockDriverState *bs, uint64_t start_sect,
 461                         uint64_t cluster_offset, int n_start, int n_end)
 462 {
 463     BDRVQcowState *s = bs->opaque;
 464     int n, ret;
 465
 466     n = n_end - n_start;
 467     if (n <= 0)
 468         return 0;
 469     ret = qcow_read(bs, start_sect + n_start, s->cluster_data, n);
 470     if (ret < 0)
 471         return ret;
 472     if (s->crypt_method) {
 473         encrypt_sectors(s, start_sect + n_start,
 474                         s->cluster_data,
 475                         s->cluster_data, n, 1,
 476                         &s->aes_encrypt_key);
 477     }
 478     ret = bdrv_write(s->hd, (cluster_offset >> 9) + n_start,
 479                      s->cluster_data, n);
 480     if (ret < 0)
 481         return ret;
 482     return 0;
 483 }
 484
 485 static void l2_cache_reset(BlockDriverState *bs)
 486 {
 487     BDRVQcowState *s = bs->opaque;
 488
 489     memset(s->l2_cache, 0, s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t));
 490     memset(s->l2_cache_offsets, 0, L2_CACHE_SIZE * sizeof(uint64_t));
 491     memset(s->l2_cache_counts, 0, L2_CACHE_SIZE * sizeof(uint32_t));
 492 }
 493
 494 static inline int l2_cache_new_entry(BlockDriverState *bs)
 495 {
 496     BDRVQcowState *s = bs->opaque;
 497     uint32_t min_count;
 498     int min_index, i;
 499
 500     /* find a new entry in the least used one */
 501     min_index = 0;
 502     min_count = 0xffffffff;
 503     for(i = 0; i < L2_CACHE_SIZE; i++) {
 504         if (s->l2_cache_counts[i] < min_count) {
 505             min_count = s->l2_cache_counts[i];
 506             min_index = i;
 507         }
 508     }
 509     return min_index;
 510 }
 511
 512 static int64_t align_offset(int64_t offset, int n)
 513 {
 514     offset = (offset + n - 1) & ~(n - 1);
 515     return offset;
 516 }
 517
 518 static int grow_l1_table(BlockDriverState *bs, int min_size)
 519 {
 520     BDRVQcowState *s = bs->opaque;
 521     int new_l1_size, new_l1_size2, ret, i;
 522     uint64_t *new_l1_table;
 523     uint64_t new_l1_table_offset;
 524     uint8_t data[12];
 525
 526     new_l1_size = s->l1_size;
 527     if (min_size <= new_l1_size)
 528         return 0;
 529     while (min_size > new_l1_size) {
 530         new_l1_size = (new_l1_size * 3 + 1) / 2;
 531     }
 532 #ifdef DEBUG_ALLOC2
 533     printf("grow l1_table from %d to %d\n", s->l1_size, new_l1_size);
 534 #endif
 535
 536     new_l1_size2 = sizeof(uint64_t) * new_l1_size;
 537     new_l1_table = qemu_mallocz(new_l1_size2);
 538     memcpy(new_l1_table, s->l1_table, s->l1_size * sizeof(uint64_t));
 539
 540     /* write new table (align to cluster) */
 541     new_l1_table_offset = alloc_clusters(bs, new_l1_size2);
 542
 543     for(i = 0; i < s->l1_size; i++)
 544         new_l1_table[i] = cpu_to_be64(new_l1_table[i]);
 545     ret = bdrv_pwrite(s->hd, new_l1_table_offset, new_l1_table, new_l1_size2);
 546     if (ret != new_l1_size2)
 547         goto fail;
 548     for(i = 0; i < s->l1_size; i++)
 549         new_l1_table[i] = be64_to_cpu(new_l1_table[i]);
 550
 551     /* set new table */
 552     cpu_to_be32w((uint32_t*)data, new_l1_size);
 553     cpu_to_be64w((uint64_t*)(data + 4), new_l1_table_offset);
 554     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, l1_size), data,
 555                 sizeof(data)) != sizeof(data))
 556         goto fail;
 557     qemu_free(s->l1_table);
 558     free_clusters(bs, s->l1_table_offset, s->l1_size * sizeof(uint64_t));
 559     s->l1_table_offset = new_l1_table_offset;
 560     s->l1_table = new_l1_table;
 561     s->l1_size = new_l1_size;
 562     return 0;
 563  fail:
 564     qemu_free(s->l1_table);
 565     return -EIO;
 566 }
 567
 568 /*
 569  * seek_l2_table
 570  *
 571  * seek l2_offset in the l2_cache table
 572  * if not found, return NULL,
 573  * if found,
 574  *   increments the l2 cache hit count of the entry,
 575  *   if counter overflow, divide by two all counters
 576  *   return the pointer to the l2 cache entry
 577  *
 578  */
 579
 580 static uint64_t *seek_l2_table(BDRVQcowState *s, uint64_t l2_offset)
 581 {
 582     int i, j;
 583
 584     for(i = 0; i < L2_CACHE_SIZE; i++) {
 585         if (l2_offset == s->l2_cache_offsets[i]) {
 586             /* increment the hit count */
 587             if (++s->l2_cache_counts[i] == 0xffffffff) {
 588                 for(j = 0; j < L2_CACHE_SIZE; j++) {
 589                     s->l2_cache_counts[j] >>= 1;
 590                 }
 591             }
 592             return s->l2_cache + (i << s->l2_bits);
 593         }
 594     }
 595     return NULL;
 596 }
 597
 598 /*
 599  * l2_load
 600  *
 601  * Loads a L2 table into memory. If the table is in the cache, the cache
 602  * is used; otherwise the L2 table is loaded from the image file.
 603  *
 604  * Returns a pointer to the L2 table on success, or NULL if the read from
 605  * the image file failed.
 606  */
 607
 608 static uint64_t *l2_load(BlockDriverState *bs, uint64_t l2_offset)
 609 {
 610     BDRVQcowState *s = bs->opaque;
 611     int min_index;
 612     uint64_t *l2_table;
 613
 614     /* seek if the table for the given offset is in the cache */
 615
 616     l2_table = seek_l2_table(s, l2_offset);
 617     if (l2_table != NULL)
 618         return l2_table;
 619
 620     /* not found: load a new entry in the least used one */
 621
 622     min_index = l2_cache_new_entry(bs);
 623     l2_table = s->l2_cache + (min_index << s->l2_bits);
 624     if (bdrv_pread(s->hd, l2_offset, l2_table, s->l2_size * sizeof(uint64_t)) !=
 625         s->l2_size * sizeof(uint64_t))
 626         return NULL;
 627     s->l2_cache_offsets[min_index] = l2_offset;
 628     s->l2_cache_counts[min_index] = 1;
 629
 630     return l2_table;
 631 }
 632
 633 /*
 634  * l2_allocate
 635  *
 636  * Allocate a new l2 entry in the file. If l1_index points to an already
 637  * used entry in the L2 table (i.e. we are doing a copy on write for the L2
 638  * table) copy the contents of the old L2 table into the newly allocated one.
 639  * Otherwise the new table is initialized with zeros.
 640  *
 641  */
 642
 643 static uint64_t *l2_allocate(BlockDriverState *bs, int l1_index)
 644 {
 645     BDRVQcowState *s = bs->opaque;
 646     int min_index;
 647     uint64_t old_l2_offset, tmp;
 648     uint64_t *l2_table, l2_offset;
 649
 650     old_l2_offset = s->l1_table[l1_index];
 651
 652     /* allocate a new l2 entry */
 653
 654     l2_offset = alloc_clusters(bs, s->l2_size * sizeof(uint64_t));
 655
 656     /* update the L1 entry */
 657
 658     s->l1_table[l1_index] = l2_offset | QCOW_OFLAG_COPIED;
 659
 660     tmp = cpu_to_be64(l2_offset | QCOW_OFLAG_COPIED);
 661     if (bdrv_pwrite(s->hd, s->l1_table_offset + l1_index * sizeof(tmp),
 662                     &tmp, sizeof(tmp)) != sizeof(tmp))
 663         return NULL;
 664
 665     /* allocate a new entry in the l2 cache */
 666
 667     min_index = l2_cache_new_entry(bs);
 668     l2_table = s->l2_cache + (min_index << s->l2_bits);
 669
 670     if (old_l2_offset == 0) {
 671         /* if there was no old l2 table, clear the new table */
 672         memset(l2_table, 0, s->l2_size * sizeof(uint64_t));
 673     } else {
 674         /* if there was an old l2 table, read it from the disk */
 675         if (bdrv_pread(s->hd, old_l2_offset,
 676                        l2_table, s->l2_size * sizeof(uint64_t)) !=
 677             s->l2_size * sizeof(uint64_t))
 678             return NULL;
 679     }
 680     /* write the l2 table to the file */
 681     if (bdrv_pwrite(s->hd, l2_offset,
 682                     l2_table, s->l2_size * sizeof(uint64_t)) !=
 683         s->l2_size * sizeof(uint64_t))
 684         return NULL;
 685
 686     /* update the l2 cache entry */
 687
 688     s->l2_cache_offsets[min_index] = l2_offset;
 689     s->l2_cache_counts[min_index] = 1;
 690
 691     return l2_table;
 692 }
 693
 694 static int size_to_clusters(BDRVQcowState *s, int64_t size)
 695 {
 696     return (size + (s->cluster_size - 1)) >> s->cluster_bits;
 697 }
 698
 699 static int count_contiguous_clusters(uint64_t nb_clusters, int cluster_size,
 700         uint64_t *l2_table, uint64_t start, uint64_t mask)
 701 {
 702     int i;
 703     uint64_t offset = be64_to_cpu(l2_table[0]) & ~mask;
 704
 705     if (!offset)
 706         return 0;
 707
 708     for (i = start; i < start + nb_clusters; i++)
 709         if (offset + i * cluster_size != (be64_to_cpu(l2_table[i]) & ~mask))
 710             break;
 711
 712         return (i - start);
 713 }
 714
 715 static int count_contiguous_free_clusters(uint64_t nb_clusters, uint64_t *l2_table)
 716 {
 717     int i = 0;
 718
 719     while(nb_clusters-- && l2_table[i] == 0)
 720         i++;
 721
 722     return i;
 723 }
 724
 725 /*
 726  * get_cluster_offset
 727  *
 728  * For a given offset of the disk image, return cluster offset in
 729  * qcow2 file.
 730  *
 731  * on entry, *num is the number of contiguous clusters we'd like to
 732  * access following offset.
 733  *
 734  * on exit, *num is the number of contiguous clusters we can read.
 735  *
 736  * Return 1, if the offset is found
 737  * Return 0, otherwise.
 738  *
 739  */
 740
 741 static uint64_t get_cluster_offset(BlockDriverState *bs,
 742                                    uint64_t offset, int *num)
 743 {
 744     BDRVQcowState *s = bs->opaque;
 745     int l1_index, l2_index;
 746     uint64_t l2_offset, *l2_table, cluster_offset;
 747     int l1_bits, c;
 748     int index_in_cluster, nb_available, nb_needed, nb_clusters;
 749
 750     index_in_cluster = (offset >> 9) & (s->cluster_sectors - 1);
 751     nb_needed = *num + index_in_cluster;
 752
 753     l1_bits = s->l2_bits + s->cluster_bits;
 754
 755     /* compute how many bytes there are between the offset and
 756      * the end of the l1 entry
 757      */
 758
 759     nb_available = (1 << l1_bits) - (offset & ((1 << l1_bits) - 1));
 760
 761     /* compute the number of available sectors */
 762
 763     nb_available = (nb_available >> 9) + index_in_cluster;
 764
 765     if (nb_needed > nb_available) {
 766         nb_needed = nb_available;
 767     }
 768
 769     cluster_offset = 0;
 770
 771     /* seek the the l2 offset in the l1 table */
 772
 773     l1_index = offset >> l1_bits;
 774     if (l1_index >= s->l1_size)
 775         goto out;
 776
 777     l2_offset = s->l1_table[l1_index];
 778
 779     /* seek the l2 table of the given l2 offset */
 780
 781     if (!l2_offset)
 782         goto out;
 783
 784     /* load the l2 table in memory */
 785
 786     l2_offset &= ~QCOW_OFLAG_COPIED;
 787     l2_table = l2_load(bs, l2_offset);
 788     if (l2_table == NULL)
 789         return 0;
 790
 791     /* find the cluster offset for the given disk offset */
 792
 793     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 794     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 795     nb_clusters = size_to_clusters(s, nb_needed << 9);
 796
 797     if (!cluster_offset) {
 798         /* how many empty clusters ? */
 799         c = count_contiguous_free_clusters(nb_clusters, &l2_table[l2_index]);
 800     } else {
 801         /* how many allocated clusters ? */
 802         c = count_contiguous_clusters(nb_clusters, s->cluster_size,
 803                 &l2_table[l2_index], 0, QCOW_OFLAG_COPIED);
 804     }
 805
 806    nb_available = (c * s->cluster_sectors);
 807 out:
 808     if (nb_available > nb_needed)
 809         nb_available = nb_needed;
 810
 811     *num = nb_available - index_in_cluster;
 812
 813     return cluster_offset & ~QCOW_OFLAG_COPIED;
 814 }
 815
 816 /*
 817  * free_any_clusters
 818  *
 819  * free clusters according to its type: compressed or not
 820  *
 821  */
 822
 823 static void free_any_clusters(BlockDriverState *bs,
 824                               uint64_t cluster_offset, int nb_clusters)
 825 {
 826     BDRVQcowState *s = bs->opaque;
 827
 828     /* free the cluster */
 829
 830     if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
 831         int nb_csectors;
 832         nb_csectors = ((cluster_offset >> s->csize_shift) &
 833                        s->csize_mask) + 1;
 834         free_clusters(bs, (cluster_offset & s->cluster_offset_mask) & ~511,
 835                       nb_csectors * 512);
 836         return;
 837     }
 838
 839     free_clusters(bs, cluster_offset, nb_clusters << s->cluster_bits);
 840
 841     return;
 842 }
 843
 844 /*
 845  * get_cluster_table
 846  *
 847  * for a given disk offset, load (and allocate if needed)
 848  * the l2 table.
 849  *
 850  * the l2 table offset in the qcow2 file and the cluster index
 851  * in the l2 table are given to the caller.
 852  *
 853  */
 854
 855 static int get_cluster_table(BlockDriverState *bs, uint64_t offset,
 856                              uint64_t **new_l2_table,
 857                              uint64_t *new_l2_offset,
 858                              int *new_l2_index)
 859 {
 860     BDRVQcowState *s = bs->opaque;
 861     int l1_index, l2_index, ret;
 862     uint64_t l2_offset, *l2_table;
 863
 864     /* seek the the l2 offset in the l1 table */
 865
 866     l1_index = offset >> (s->l2_bits + s->cluster_bits);
 867     if (l1_index >= s->l1_size) {
 868         ret = grow_l1_table(bs, l1_index + 1);
 869         if (ret < 0)
 870             return 0;
 871     }
 872     l2_offset = s->l1_table[l1_index];
 873
 874     /* seek the l2 table of the given l2 offset */
 875
 876     if (l2_offset & QCOW_OFLAG_COPIED) {
 877         /* load the l2 table in memory */
 878         l2_offset &= ~QCOW_OFLAG_COPIED;
 879         l2_table = l2_load(bs, l2_offset);
 880         if (l2_table == NULL)
 881             return 0;
 882     } else {
 883         if (l2_offset)
 884             free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t));
 885         l2_table = l2_allocate(bs, l1_index);
 886         if (l2_table == NULL)
 887             return 0;
 888         l2_offset = s->l1_table[l1_index] & ~QCOW_OFLAG_COPIED;
 889     }
 890
 891     /* find the cluster offset for the given disk offset */
 892
 893     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 894
 895     *new_l2_table = l2_table;
 896     *new_l2_offset = l2_offset;
 897     *new_l2_index = l2_index;
 898
 899     return 1;
 900 }
 901
 902 /*
 903  * alloc_compressed_cluster_offset
 904  *
 905  * For a given offset of the disk image, return cluster offset in
 906  * qcow2 file.
 907  *
 908  * If the offset is not found, allocate a new compressed cluster.
 909  *
 910  * Return the cluster offset if successful,
 911  * Return 0, otherwise.
 912  *
 913  */
 914
 915 static uint64_t alloc_compressed_cluster_offset(BlockDriverState *bs,
 916                                                 uint64_t offset,
 917                                                 int compressed_size)
 918 {
 919     BDRVQcowState *s = bs->opaque;
 920     int l2_index, ret;
 921     uint64_t l2_offset, *l2_table, cluster_offset;
 922     int nb_csectors;
 923
 924     ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index);
 925     if (ret == 0)
 926         return 0;
 927
 928     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 929     if (cluster_offset & QCOW_OFLAG_COPIED)
 930         return cluster_offset & ~QCOW_OFLAG_COPIED;
 931
 932     if (cluster_offset)
 933         free_any_clusters(bs, cluster_offset, 1);
 934
 935     cluster_offset = alloc_bytes(bs, compressed_size);
 936     nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -
 937                   (cluster_offset >> 9);
 938
 939     cluster_offset |= QCOW_OFLAG_COMPRESSED |
 940                       ((uint64_t)nb_csectors << s->csize_shift);
 941
 942     /* update L2 table */
 943
 944     /* compressed clusters never have the copied flag */
 945
 946     l2_table[l2_index] = cpu_to_be64(cluster_offset);
 947     if (bdrv_pwrite(s->hd,
 948                     l2_offset + l2_index * sizeof(uint64_t),
 949                     l2_table + l2_index,
 950                     sizeof(uint64_t)) != sizeof(uint64_t))
 951         return 0;
 952
 953     return cluster_offset;
 954 }
 955
 956 typedef struct QCowL2Meta
 957 {
 958     uint64_t offset;
 959     int n_start;
 960     int nb_available;
 961     int nb_clusters;
 962 } QCowL2Meta;
 963
 964 static int alloc_cluster_link_l2(BlockDriverState *bs, uint64_t cluster_offset,
 965         QCowL2Meta *m)
 966 {
 967     BDRVQcowState *s = bs->opaque;
 968     int i, j = 0, l2_index, ret;
 969     uint64_t *old_cluster, start_sect, l2_offset, *l2_table;
 970
 971     if (m->nb_clusters == 0)
 972         return 0;
 973
 974     old_cluster = qemu_malloc(m->nb_clusters * sizeof(uint64_t));
 975
 976     /* copy content of unmodified sectors */
 977     start_sect = (m->offset & ~(s->cluster_size - 1)) >> 9;
 978     if (m->n_start) {
 979         ret = copy_sectors(bs, start_sect, cluster_offset, 0, m->n_start);
 980         if (ret < 0)
 981             goto err;
 982     }
 983
 984     if (m->nb_available & (s->cluster_sectors - 1)) {
 985         uint64_t end = m->nb_available & ~(uint64_t)(s->cluster_sectors - 1);
 986         ret = copy_sectors(bs, start_sect + end, cluster_offset + (end << 9),
 987                 m->nb_available - end, s->cluster_sectors);
 988         if (ret < 0)
 989             goto err;
 990     }
 991
 992     ret = -EIO;
 993     /* update L2 table */
 994     if (!get_cluster_table(bs, m->offset, &l2_table, &l2_offset, &l2_index))
 995         goto err;
 996
 997     for (i = 0; i < m->nb_clusters; i++) {
 998         /* if two concurrent writes happen to the same unallocated cluster
 999          * each write allocates separate cluster and writes data concurrently.
1000          * The first one to complete updates l2 table with pointer to its
1001          * cluster the second one has to do RMW (which is done above by
1002          * copy_sectors()), update l2 table with its cluster pointer and free
1003          * old cluster. This is what this loop does */
1004         if(l2_table[l2_index + i] != 0)
1005             old_cluster[j++] = l2_table[l2_index + i];
1006
1007         l2_table[l2_index + i] = cpu_to_be64((cluster_offset +
1008                     (i << s->cluster_bits)) | QCOW_OFLAG_COPIED);
1009      }
1010
1011     if (bdrv_pwrite(s->hd, l2_offset + l2_index * sizeof(uint64_t),
1012                 l2_table + l2_index, m->nb_clusters * sizeof(uint64_t)) !=
1013             m->nb_clusters * sizeof(uint64_t))
1014         goto err;
1015
1016     for (i = 0; i < j; i++)
1017         free_any_clusters(bs, be64_to_cpu(old_cluster[i]) & ~QCOW_OFLAG_COPIED,
1018                           1);
1019
1020     ret = 0;
1021 err:
1022     qemu_free(old_cluster);
1023     return ret;
1024  }
1025
1026 /*
1027  * alloc_cluster_offset
1028  *
1029  * For a given offset of the disk image, return cluster offset in
1030  * qcow2 file.
1031  *
1032  * If the offset is not found, allocate a new cluster.
1033  *
1034  * Return the cluster offset if successful,
1035  * Return 0, otherwise.
1036  *
1037  */
1038
1039 static uint64_t alloc_cluster_offset(BlockDriverState *bs,
1040                                      uint64_t offset,
1041                                      int n_start, int n_end,
1042                                      int *num, QCowL2Meta *m)
1043 {
1044     BDRVQcowState *s = bs->opaque;
1045     int l2_index, ret;
1046     uint64_t l2_offset, *l2_table, cluster_offset;
1047     int nb_clusters, i = 0;
1048
1049     ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index);
1050     if (ret == 0)
1051         return 0;
1052
1053     nb_clusters = size_to_clusters(s, n_end << 9);
1054
1055     nb_clusters = MIN(nb_clusters, s->l2_size - l2_index);
1056
1057     cluster_offset = be64_to_cpu(l2_table[l2_index]);
1058
1059     /* We keep all QCOW_OFLAG_COPIED clusters */
1060
1061     if (cluster_offset & QCOW_OFLAG_COPIED) {
1062         nb_clusters = count_contiguous_clusters(nb_clusters, s->cluster_size,
1063                 &l2_table[l2_index], 0, 0);
1064
1065         cluster_offset &= ~QCOW_OFLAG_COPIED;
1066         m->nb_clusters = 0;
1067
1068         goto out;
1069     }
1070
1071     /* for the moment, multiple compressed clusters are not managed */
1072
1073     if (cluster_offset & QCOW_OFLAG_COMPRESSED)
1074         nb_clusters = 1;
1075
1076     /* how many available clusters ? */
1077
1078     while (i < nb_clusters) {
1079         i += count_contiguous_clusters(nb_clusters - i, s->cluster_size,
1080                 &l2_table[l2_index], i, 0);
1081
1082         if(be64_to_cpu(l2_table[l2_index + i]))
1083             break;
1084
1085         i += count_contiguous_free_clusters(nb_clusters - i,
1086                 &l2_table[l2_index + i]);
1087
1088         cluster_offset = be64_to_cpu(l2_table[l2_index + i]);
1089
1090         if ((cluster_offset & QCOW_OFLAG_COPIED) ||
1091                 (cluster_offset & QCOW_OFLAG_COMPRESSED))
1092             break;
1093     }
1094     nb_clusters = i;
1095
1096     /* allocate a new cluster */
1097
1098     cluster_offset = alloc_clusters(bs, nb_clusters * s->cluster_size);
1099
1100     /* save info needed for meta data update */
1101     m->offset = offset;
1102     m->n_start = n_start;
1103     m->nb_clusters = nb_clusters;
1104
1105 out:
1106     m->nb_available = MIN(nb_clusters << (s->cluster_bits - 9), n_end);
1107
1108     *num = m->nb_available - n_start;
1109
1110     return cluster_offset;
1111 }
1112
1113 static int qcow_is_allocated(BlockDriverState *bs, int64_t sector_num,
1114                              int nb_sectors, int *pnum)
1115 {
1116     uint64_t cluster_offset;
1117
1118     *pnum = nb_sectors;
1119     cluster_offset = get_cluster_offset(bs, sector_num << 9, pnum);
1120
1121     return (cluster_offset != 0);
1122 }
1123
1124 static int decompress_buffer(uint8_t *out_buf, int out_buf_size,
1125                              const uint8_t *buf, int buf_size)
1126 {
1127     z_stream strm1, *strm = &strm1;
1128     int ret, out_len;
1129
1130     memset(strm, 0, sizeof(*strm));
1131
1132     strm->next_in = (uint8_t *)buf;
1133     strm->avail_in = buf_size;
1134     strm->next_out = out_buf;
1135     strm->avail_out = out_buf_size;
1136
1137     ret = inflateInit2(strm, -12);
1138     if (ret != Z_OK)
1139         return -1;
1140     ret = inflate(strm, Z_FINISH);
1141     out_len = strm->next_out - out_buf;
1142     if ((ret != Z_STREAM_END && ret != Z_BUF_ERROR) ||
1143         out_len != out_buf_size) {
1144         inflateEnd(strm);
1145         return -1;
1146     }
1147     inflateEnd(strm);
1148     return 0;
1149 }
1150
1151 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset)
1152 {
1153     int ret, csize, nb_csectors, sector_offset;
1154     uint64_t coffset;
1155
1156     coffset = cluster_offset & s->cluster_offset_mask;
1157     if (s->cluster_cache_offset != coffset) {
1158         nb_csectors = ((cluster_offset >> s->csize_shift) & s->csize_mask) + 1;
1159         sector_offset = coffset & 511;
1160         csize = nb_csectors * 512 - sector_offset;
1161         ret = bdrv_read(s->hd, coffset >> 9, s->cluster_data, nb_csectors);
1162         if (ret < 0) {
1163             return -1;
1164         }
1165         if (decompress_buffer(s->cluster_cache, s->cluster_size,
1166                               s->cluster_data + sector_offset, csize) < 0) {
1167             return -1;
1168         }
1169         s->cluster_cache_offset = coffset;
1170     }
1171     return 0;
1172 }
1173
1174 /* handle reading after the end of the backing file */
1175 static int backing_read1(BlockDriverState *bs,
1176                          int64_t sector_num, uint8_t *buf, int nb_sectors)
1177 {
1178     int n1;
1179     if ((sector_num + nb_sectors) <= bs->total_sectors)
1180         return nb_sectors;
1181     if (sector_num >= bs->total_sectors)
1182         n1 = 0;
1183     else
1184         n1 = bs->total_sectors - sector_num;
1185     memset(buf + n1 * 512, 0, 512 * (nb_sectors - n1));
1186     return n1;
1187 }
1188
1189 static int qcow_read(BlockDriverState *bs, int64_t sector_num,
1190                      uint8_t *buf, int nb_sectors)
1191 {
1192     BDRVQcowState *s = bs->opaque;
1193     int ret, index_in_cluster, n, n1;
1194     uint64_t cluster_offset;
1195
1196     while (nb_sectors > 0) {
1197         n = nb_sectors;
1198         cluster_offset = get_cluster_offset(bs, sector_num << 9, &n);
1199         index_in_cluster = sector_num & (s->cluster_sectors - 1);
1200         if (!cluster_offset) {
1201             if (bs->backing_hd) {
1202                 /* read from the base image */
1203                 n1 = backing_read1(bs->backing_hd, sector_num, buf, n);
1204                 if (n1 > 0) {
1205                     ret = bdrv_read(bs->backing_hd, sector_num, buf, n1);
1206                     if (ret < 0)
1207                         return -1;
1208                 }
1209             } else {
1210                 memset(buf, 0, 512 * n);
1211             }
1212         } else if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
1213             if (decompress_cluster(s, cluster_offset) < 0)
1214                 return -1;
1215             memcpy(buf, s->cluster_cache + index_in_cluster * 512, 512 * n);
1216         } else {
1217             ret = bdrv_pread(s->hd, cluster_offset + index_in_cluster * 512, buf, n * 512);
1218             if (ret != n * 512)
1219                 return -1;
1220             if (s->crypt_method) {
1221                 encrypt_sectors(s, sector_num, buf, buf, n, 0,
1222                                 &s->aes_decrypt_key);
1223             }
1224         }
1225         nb_sectors -= n;
1226         sector_num += n;
1227         buf += n * 512;
1228     }
1229     return 0;
1230 }
1231
1232 typedef struct QCowAIOCB {
1233     BlockDriverAIOCB common;
1234     int64_t sector_num;
1235     QEMUIOVector *qiov;
1236     uint8_t *buf;
1237     void *orig_buf;
1238     int nb_sectors;
1239     int n;
1240     uint64_t cluster_offset;
1241     uint8_t *cluster_data;
1242     BlockDriverAIOCB *hd_aiocb;
1243     struct iovec hd_iov;
1244     QEMUIOVector hd_qiov;
1245     QEMUBH *bh;
1246     QCowL2Meta l2meta;
1247 } QCowAIOCB;
1248
1249 static void qcow_aio_read_cb(void *opaque, int ret);
1250 static void qcow_aio_read_bh(void *opaque)
1251 {
1252     QCowAIOCB *acb = opaque;
1253     qemu_bh_delete(acb->bh);
1254     acb->bh = NULL;
1255     qcow_aio_read_cb(opaque, 0);
1256 }
1257
1258 static int qcow_schedule_bh(QEMUBHFunc *cb, QCowAIOCB *acb)
1259 {
1260     if (acb->bh)
1261         return -EIO;
1262
1263     acb->bh = qemu_bh_new(cb, acb);
1264     if (!acb->bh)
1265         return -EIO;
1266
1267     qemu_bh_schedule(acb->bh);
1268
1269     return 0;
1270 }
1271
1272 static void qcow_aio_read_cb(void *opaque, int ret)
1273 {
1274     QCowAIOCB *acb = opaque;
1275     BlockDriverState *bs = acb->common.bs;
1276     BDRVQcowState *s = bs->opaque;
1277     int index_in_cluster, n1;
1278
1279     acb->hd_aiocb = NULL;
1280     if (ret < 0)
1281         goto done;
1282
1283     /* post process the read buffer */
1284     if (!acb->cluster_offset) {
1285         /* nothing to do */
1286     } else if (acb->cluster_offset & QCOW_OFLAG_COMPRESSED) {
1287         /* nothing to do */
1288     } else {
1289         if (s->crypt_method) {
1290             encrypt_sectors(s, acb->sector_num, acb->buf, acb->buf,
1291                             acb->n, 0,
1292                             &s->aes_decrypt_key);
1293         }
1294     }
1295
1296     acb->nb_sectors -= acb->n;
1297     acb->sector_num += acb->n;
1298     acb->buf += acb->n * 512;
1299
1300     if (acb->nb_sectors == 0) {
1301         /* request completed */
1302         ret = 0;
1303         goto done;
1304     }
1305
1306     /* prepare next AIO request */
1307     acb->n = acb->nb_sectors;
1308     acb->cluster_offset = get_cluster_offset(bs, acb->sector_num << 9, &acb->n);
1309     index_in_cluster = acb->sector_num & (s->cluster_sectors - 1);
1310
1311     if (!acb->cluster_offset) {
1312         if (bs->backing_hd) {
1313             /* read from the base image */
1314             n1 = backing_read1(bs->backing_hd, acb->sector_num,
1315                                acb->buf, acb->n);
1316             if (n1 > 0) {
1317                 acb->hd_iov.iov_base = (void *)acb->buf;
1318                 acb->hd_iov.iov_len = acb->n * 512;
1319                 qemu_iovec_init_external(&acb->hd_qiov, &acb->hd_iov, 1);
1320                 acb->hd_aiocb = bdrv_aio_readv(bs->backing_hd, acb->sector_num,
1321                                     &acb->hd_qiov, acb->n,
1322                                     qcow_aio_read_cb, acb);
1323                 if (acb->hd_aiocb == NULL)
1324                     goto done;
1325             } else {
1326                 ret = qcow_schedule_bh(qcow_aio_read_bh, acb);
1327                 if (ret < 0)
1328                     goto done;
1329             }
1330         } else {
1331             /* Note: in this case, no need to wait */
1332             memset(acb->buf, 0, 512 * acb->n);
1333             ret = qcow_schedule_bh(qcow_aio_read_bh, acb);
1334             if (ret < 0)
1335                 goto done;
1336         }
1337     } else if (acb->cluster_offset & QCOW_OFLAG_COMPRESSED) {
1338         /* add AIO support for compressed blocks ? */
1339         if (decompress_cluster(s, acb->cluster_offset) < 0)
1340             goto done;
1341         memcpy(acb->buf,
1342                s->cluster_cache + index_in_cluster * 512, 512 * acb->n);
1343         ret = qcow_schedule_bh(qcow_aio_read_bh, acb);
1344         if (ret < 0)
1345             goto done;
1346     } else {
1347         if ((acb->cluster_offset & 511) != 0) {
1348             ret = -EIO;
1349             goto done;
1350         }
1351
1352         acb->hd_iov.iov_base = (void *)acb->buf;
1353         acb->hd_iov.iov_len = acb->n * 512;
1354         qemu_iovec_init_external(&acb->hd_qiov, &acb->hd_iov, 1);
1355         acb->hd_aiocb = bdrv_aio_readv(s->hd,
1356                             (acb->cluster_offset >> 9) + index_in_cluster,
1357                             &acb->hd_qiov, acb->n, qcow_aio_read_cb, acb);
1358         if (acb->hd_aiocb == NULL)
1359             goto done;
1360     }
1361
1362     return;
1363 done:
1364     if (acb->qiov->niov > 1) {
1365         qemu_iovec_from_buffer(acb->qiov, acb->orig_buf, acb->qiov->size);
1366         qemu_vfree(acb->orig_buf);
1367     }
1368     acb->common.cb(acb->common.opaque, ret);
1369     qemu_aio_release(acb);
1370 }
1371
1372 static QCowAIOCB *qcow_aio_setup(BlockDriverState *bs,
1373         int64_t sector_num, QEMUIOVector *qiov, int nb_sectors,
1374         BlockDriverCompletionFunc *cb, void *opaque, int is_write)
1375 {
1376     QCowAIOCB *acb;
1377
1378     acb = qemu_aio_get(bs, cb, opaque);
1379     if (!acb)
1380         return NULL;
1381     acb->hd_aiocb = NULL;
1382     acb->sector_num = sector_num;
1383     acb->qiov = qiov;
1384     if (qiov->niov > 1) {
1385         acb->buf = acb->orig_buf = qemu_blockalign(bs, qiov->size);
1386         if (is_write)
1387             qemu_iovec_to_buffer(qiov, acb->buf);
1388     } else {
1389         acb->buf = (uint8_t *)qiov->iov->iov_base;
1390     }
1391     acb->nb_sectors = nb_sectors;
1392     acb->n = 0;
1393     acb->cluster_offset = 0;
1394     acb->l2meta.nb_clusters = 0;
1395     return acb;
1396 }
1397
1398 static BlockDriverAIOCB *qcow_aio_readv(BlockDriverState *bs,
1399         int64_t sector_num, QEMUIOVector *qiov, int nb_sectors,
1400         BlockDriverCompletionFunc *cb, void *opaque)
1401 {
1402     QCowAIOCB *acb;
1403
1404     acb = qcow_aio_setup(bs, sector_num, qiov, nb_sectors, cb, opaque, 0);
1405     if (!acb)
1406         return NULL;
1407
1408     qcow_aio_read_cb(acb, 0);
1409     return &acb->common;
1410 }
1411
1412 static void qcow_aio_write_cb(void *opaque, int ret)
1413 {
1414     QCowAIOCB *acb = opaque;
1415     BlockDriverState *bs = acb->common.bs;
1416     BDRVQcowState *s = bs->opaque;
1417     int index_in_cluster;
1418     const uint8_t *src_buf;
1419     int n_end;
1420
1421     acb->hd_aiocb = NULL;
1422
1423     if (ret < 0)
1424         goto done;
1425
1426     if (alloc_cluster_link_l2(bs, acb->cluster_offset, &acb->l2meta) < 0) {
1427         free_any_clusters(bs, acb->cluster_offset, acb->l2meta.nb_clusters);
1428         goto done;
1429     }
1430
1431     acb->nb_sectors -= acb->n;
1432     acb->sector_num += acb->n;
1433     acb->buf += acb->n * 512;
1434
1435     if (acb->nb_sectors == 0) {
1436         /* request completed */
1437         ret = 0;
1438         goto done;
1439     }
1440
1441     index_in_cluster = acb->sector_num & (s->cluster_sectors - 1);
1442     n_end = index_in_cluster + acb->nb_sectors;
1443     if (s->crypt_method &&
1444         n_end > QCOW_MAX_CRYPT_CLUSTERS * s->cluster_sectors)
1445         n_end = QCOW_MAX_CRYPT_CLUSTERS * s->cluster_sectors;
1446
1447     acb->cluster_offset = alloc_cluster_offset(bs, acb->sector_num << 9,
1448                                           index_in_cluster,
1449                                           n_end, &acb->n, &acb->l2meta);
1450     if (!acb->cluster_offset || (acb->cluster_offset & 511) != 0) {
1451         ret = -EIO;
1452         goto done;
1453     }
1454     if (s->crypt_method) {
1455         if (!acb->cluster_data) {
1456             acb->cluster_data = qemu_mallocz(QCOW_MAX_CRYPT_CLUSTERS *
1457                                              s->cluster_size);
1458         }
1459         encrypt_sectors(s, acb->sector_num, acb->cluster_data, acb->buf,
1460                         acb->n, 1, &s->aes_encrypt_key);
1461         src_buf = acb->cluster_data;
1462     } else {
1463         src_buf = acb->buf;
1464     }
1465     acb->hd_iov.iov_base = (void *)src_buf;
1466     acb->hd_iov.iov_len = acb->n * 512;
1467     qemu_iovec_init_external(&acb->hd_qiov, &acb->hd_iov, 1);
1468     acb->hd_aiocb = bdrv_aio_writev(s->hd,
1469                                     (acb->cluster_offset >> 9) + index_in_cluster,
1470                                     &acb->hd_qiov, acb->n,
1471                                     qcow_aio_write_cb, acb);
1472     if (acb->hd_aiocb == NULL)
1473         goto done;
1474
1475     return;
1476
1477 done:
1478     if (acb->qiov->niov > 1)
1479         qemu_vfree(acb->orig_buf);
1480     acb->common.cb(acb->common.opaque, ret);
1481     qemu_aio_release(acb);
1482 }
1483
1484 static BlockDriverAIOCB *qcow_aio_writev(BlockDriverState *bs,
1485         int64_t sector_num, QEMUIOVector *qiov, int nb_sectors,
1486         BlockDriverCompletionFunc *cb, void *opaque)
1487 {
1488     BDRVQcowState *s = bs->opaque;
1489     QCowAIOCB *acb;
1490
1491     s->cluster_cache_offset = -1; /* disable compressed cache */
1492
1493     acb = qcow_aio_setup(bs, sector_num, qiov, nb_sectors, cb, opaque, 1);
1494     if (!acb)
1495         return NULL;
1496
1497     qcow_aio_write_cb(acb, 0);
1498     return &acb->common;
1499 }
1500
1501 static void qcow_aio_cancel(BlockDriverAIOCB *blockacb)
1502 {
1503     QCowAIOCB *acb = (QCowAIOCB *)blockacb;
1504     if (acb->hd_aiocb)
1505         bdrv_aio_cancel(acb->hd_aiocb);
1506     qemu_aio_release(acb);
1507 }
1508
1509 static void qcow_close(BlockDriverState *bs)
1510 {
1511     BDRVQcowState *s = bs->opaque;
1512     qemu_free(s->l1_table);
1513     qemu_free(s->l2_cache);
1514     qemu_free(s->cluster_cache);
1515     qemu_free(s->cluster_data);
1516     refcount_close(bs);
1517     bdrv_delete(s->hd);
1518 }
1519
1520 /* XXX: use std qcow open function ? */
1521 typedef struct QCowCreateState {
1522     int cluster_size;
1523     int cluster_bits;
1524     uint16_t *refcount_block;
1525     uint64_t *refcount_table;
1526     int64_t l1_table_offset;
1527     int64_t refcount_table_offset;
1528     int64_t refcount_block_offset;
1529 } QCowCreateState;
1530
1531 static void create_refcount_update(QCowCreateState *s,
1532                                    int64_t offset, int64_t size)
1533 {
1534     int refcount;
1535     int64_t start, last, cluster_offset;
1536     uint16_t *p;
1537
1538     start = offset & ~(s->cluster_size - 1);
1539     last = (offset + size - 1)  & ~(s->cluster_size - 1);
1540     for(cluster_offset = start; cluster_offset <= last;
1541         cluster_offset += s->cluster_size) {
1542         p = &s->refcount_block[cluster_offset >> s->cluster_bits];
1543         refcount = be16_to_cpu(*p);
1544         refcount++;
1545         *p = cpu_to_be16(refcount);
1546     }
1547 }
1548
1549 static int get_bits_from_size(size_t size)
1550 {
1551     int res = 0;
1552
1553     if (size == 0) {
1554         return -1;
1555     }
1556
1557     while (size != 1) {
1558         /* Not a power of two */
1559         if (size & 1) {
1560             return -1;
1561         }
1562
1563         size >>= 1;
1564         res++;
1565     }
1566
1567     return res;
1568 }
1569
1570 static int qcow_create2(const char *filename, int64_t total_size,
1571                         const char *backing_file, const char *backing_format,
1572                         int flags, size_t cluster_size)
1573 {
1574
1575     int fd, header_size, backing_filename_len, l1_size, i, shift, l2_bits;
1576     int ref_clusters, backing_format_len = 0;
1577     QCowHeader header;
1578     uint64_t tmp, offset;
1579     QCowCreateState s1, *s = &s1;
1580     QCowExtension ext_bf = {0, 0};
1581
1582
1583     memset(s, 0, sizeof(*s));
1584
1585     fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0644);
1586     if (fd < 0)
1587         return -1;
1588     memset(&header, 0, sizeof(header));
1589     header.magic = cpu_to_be32(QCOW_MAGIC);
1590     header.version = cpu_to_be32(QCOW_VERSION);
1591     header.size = cpu_to_be64(total_size * 512);
1592     header_size = sizeof(header);
1593     backing_filename_len = 0;
1594     if (backing_file) {
1595         if (backing_format) {
1596             ext_bf.magic = QCOW_EXT_MAGIC_BACKING_FORMAT;
1597             backing_format_len = strlen(backing_format);
1598             ext_bf.len = (backing_format_len + 7) & ~7;
1599             header_size += ((sizeof(ext_bf) + ext_bf.len + 7) & ~7);
1600         }
1601         header.backing_file_offset = cpu_to_be64(header_size);
1602         backing_filename_len = strlen(backing_file);
1603         header.backing_file_size = cpu_to_be32(backing_filename_len);
1604         header_size += backing_filename_len;
1605     }
1606
1607     /* Cluster size */
1608     s->cluster_bits = get_bits_from_size(cluster_size);
1609     if (s->cluster_bits < MIN_CLUSTER_BITS ||
1610         s->cluster_bits > MAX_CLUSTER_BITS)
1611     {
1612         fprintf(stderr, "Cluster size must be a power of two between "
1613             "%d and %dk\n",
1614             1 << MIN_CLUSTER_BITS,
1615             1 << (MAX_CLUSTER_BITS - 10));
1616         return -EINVAL;
1617     }
1618     s->cluster_size = 1 << s->cluster_bits;
1619
1620     header.cluster_bits = cpu_to_be32(s->cluster_bits);
1621     header_size = (header_size + 7) & ~7;
1622     if (flags & BLOCK_FLAG_ENCRYPT) {
1623         header.crypt_method = cpu_to_be32(QCOW_CRYPT_AES);
1624     } else {
1625         header.crypt_method = cpu_to_be32(QCOW_CRYPT_NONE);
1626     }
1627     l2_bits = s->cluster_bits - 3;
1628     shift = s->cluster_bits + l2_bits;
1629     l1_size = (((total_size * 512) + (1LL << shift) - 1) >> shift);
1630     offset = align_offset(header_size, s->cluster_size);
1631     s->l1_table_offset = offset;
1632     header.l1_table_offset = cpu_to_be64(s->l1_table_offset);
1633     header.l1_size = cpu_to_be32(l1_size);
1634     offset += align_offset(l1_size * sizeof(uint64_t), s->cluster_size);
1635
1636     s->refcount_table = qemu_mallocz(s->cluster_size);
1637
1638     s->refcount_table_offset = offset;
1639     header.refcount_table_offset = cpu_to_be64(offset);
1640     header.refcount_table_clusters = cpu_to_be32(1);
1641     offset += s->cluster_size;
1642     s->refcount_block_offset = offset;
1643
1644     /* count how many refcount blocks needed */
1645     tmp = offset >> s->cluster_bits;
1646     ref_clusters = (tmp >> (s->cluster_bits - REFCOUNT_SHIFT)) + 1;
1647     for (i=0; i < ref_clusters; i++) {
1648         s->refcount_table[i] = cpu_to_be64(offset);
1649         offset += s->cluster_size;
1650     }
1651
1652     s->refcount_block = qemu_mallocz(ref_clusters * s->cluster_size);
1653
1654     /* update refcounts */
1655     create_refcount_update(s, 0, header_size);
1656     create_refcount_update(s, s->l1_table_offset, l1_size * sizeof(uint64_t));
1657     create_refcount_update(s, s->refcount_table_offset, s->cluster_size);
1658     create_refcount_update(s, s->refcount_block_offset, ref_clusters * s->cluster_size);
1659
1660     /* write all the data */
1661     write(fd, &header, sizeof(header));
1662     if (backing_file) {
1663         if (backing_format_len) {
1664             char zero[16];
1665             int d = ext_bf.len - backing_format_len;
1666
1667             memset(zero, 0, sizeof(zero));
1668             cpu_to_be32s(&ext_bf.magic);
1669             cpu_to_be32s(&ext_bf.len);
1670             write(fd, &ext_bf, sizeof(ext_bf));
1671             write(fd, backing_format, backing_format_len);
1672             if (d>0) {
1673                 write(fd, zero, d);
1674             }
1675         }
1676         write(fd, backing_file, backing_filename_len);
1677     }
1678     lseek(fd, s->l1_table_offset, SEEK_SET);
1679     tmp = 0;
1680     for(i = 0;i < l1_size; i++) {
1681         write(fd, &tmp, sizeof(tmp));
1682     }
1683     lseek(fd, s->refcount_table_offset, SEEK_SET);
1684     write(fd, s->refcount_table, s->cluster_size);
1685
1686     lseek(fd, s->refcount_block_offset, SEEK_SET);
1687     write(fd, s->refcount_block, ref_clusters * s->cluster_size);
1688
1689     qemu_free(s->refcount_table);
1690     qemu_free(s->refcount_block);
1691     close(fd);
1692     return 0;
1693 }
1694
1695 static int qcow_create(const char *filename, QEMUOptionParameter *options)
1696 {
1697     const char *backing_file = NULL;
1698     const char *backing_fmt = NULL;
1699     uint64_t sectors = 0;
1700     int flags = 0;
1701     size_t cluster_size = 4096;
1702
1703     /* Read out options */
1704     while (options && options->name) {
1705         if (!strcmp(options->name, BLOCK_OPT_SIZE)) {
1706             sectors = options->value.n / 512;
1707         } else if (!strcmp(options->name, BLOCK_OPT_BACKING_FILE)) {
1708             backing_file = options->value.s;
1709         } else if (!strcmp(options->name, BLOCK_OPT_BACKING_FMT)) {
1710             backing_fmt = options->value.s;
1711         } else if (!strcmp(options->name, BLOCK_OPT_ENCRYPT)) {
1712             flags |= options->value.n ? BLOCK_FLAG_ENCRYPT : 0;
1713         } else if (!strcmp(options->name, BLOCK_OPT_CLUSTER_SIZE)) {
1714             if (options->value.n) {
1715                 cluster_size = options->value.n;
1716             }
1717         }
1718         options++;
1719     }
1720
1721     return qcow_create2(filename, sectors, backing_file, backing_fmt, flags,
1722         cluster_size);
1723 }
1724
1725 static int qcow_make_empty(BlockDriverState *bs)
1726 {
1727 #if 0
1728     /* XXX: not correct */
1729     BDRVQcowState *s = bs->opaque;
1730     uint32_t l1_length = s->l1_size * sizeof(uint64_t);
1731     int ret;
1732
1733     memset(s->l1_table, 0, l1_length);
1734     if (bdrv_pwrite(s->hd, s->l1_table_offset, s->l1_table, l1_length) < 0)
1735         return -1;
1736     ret = bdrv_truncate(s->hd, s->l1_table_offset + l1_length);
1737     if (ret < 0)
1738         return ret;
1739
1740     l2_cache_reset(bs);
1741 #endif
1742     return 0;
1743 }
1744
1745 /* XXX: put compressed sectors first, then all the cluster aligned
1746    tables to avoid losing bytes in alignment */
1747 static int qcow_write_compressed(BlockDriverState *bs, int64_t sector_num,
1748                                  const uint8_t *buf, int nb_sectors)
1749 {
1750     BDRVQcowState *s = bs->opaque;
1751     z_stream strm;
1752     int ret, out_len;
1753     uint8_t *out_buf;
1754     uint64_t cluster_offset;
1755
1756     if (nb_sectors == 0) {
1757         /* align end of file to a sector boundary to ease reading with
1758            sector based I/Os */
1759         cluster_offset = bdrv_getlength(s->hd);
1760         cluster_offset = (cluster_offset + 511) & ~511;
1761         bdrv_truncate(s->hd, cluster_offset);
1762         return 0;
1763     }
1764
1765     if (nb_sectors != s->cluster_sectors)
1766         return -EINVAL;
1767
1768     out_buf = qemu_malloc(s->cluster_size + (s->cluster_size / 1000) + 128);
1769
1770     /* best compression, small window, no zlib header */
1771     memset(&strm, 0, sizeof(strm));
1772     ret = deflateInit2(&strm, Z_DEFAULT_COMPRESSION,
1773                        Z_DEFLATED, -12,
1774                        9, Z_DEFAULT_STRATEGY);
1775     if (ret != 0) {
1776         qemu_free(out_buf);
1777         return -1;
1778     }
1779
1780     strm.avail_in = s->cluster_size;
1781     strm.next_in = (uint8_t *)buf;
1782     strm.avail_out = s->cluster_size;
1783     strm.next_out = out_buf;
1784
1785     ret = deflate(&strm, Z_FINISH);
1786     if (ret != Z_STREAM_END && ret != Z_OK) {
1787         qemu_free(out_buf);
1788         deflateEnd(&strm);
1789         return -1;
1790     }
1791     out_len = strm.next_out - out_buf;
1792
1793     deflateEnd(&strm);
1794
1795     if (ret != Z_STREAM_END || out_len >= s->cluster_size) {
1796         /* could not compress: write normal cluster */
1797         bdrv_write(bs, sector_num, buf, s->cluster_sectors);
1798     } else {
1799         cluster_offset = alloc_compressed_cluster_offset(bs, sector_num << 9,
1800                                               out_len);
1801         if (!cluster_offset)
1802             return -1;
1803         cluster_offset &= s->cluster_offset_mask;
1804         if (bdrv_pwrite(s->hd, cluster_offset, out_buf, out_len) != out_len) {
1805             qemu_free(out_buf);
1806             return -1;
1807         }
1808     }
1809
1810     qemu_free(out_buf);
1811     return 0;
1812 }
1813
1814 static void qcow_flush(BlockDriverState *bs)
1815 {
1816     BDRVQcowState *s = bs->opaque;
1817     bdrv_flush(s->hd);
1818 }
1819
1820 static int qcow_get_info(BlockDriverState *bs, BlockDriverInfo *bdi)
1821 {
1822     BDRVQcowState *s = bs->opaque;
1823     bdi->cluster_size = s->cluster_size;
1824     bdi->vm_state_offset = (int64_t)s->l1_vm_state_index <<
1825         (s->cluster_bits + s->l2_bits);
1826     return 0;
1827 }
1828
1829 /*********************************************************/
1830 /* snapshot support */
1831
1832 /* update the refcounts of snapshots and the copied flag */
1833 static int update_snapshot_refcount(BlockDriverState *bs,
1834                                     int64_t l1_table_offset,
1835                                     int l1_size,
1836                                     int addend)
1837 {
1838     BDRVQcowState *s = bs->opaque;
1839     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
1840     int64_t old_offset, old_l2_offset;
1841     int l2_size, i, j, l1_modified, l2_modified, nb_csectors, refcount;
1842
1843     l2_cache_reset(bs);
1844
1845     l2_table = NULL;
1846     l1_table = NULL;
1847     l1_size2 = l1_size * sizeof(uint64_t);
1848     l1_allocated = 0;
1849     if (l1_table_offset != s->l1_table_offset) {
1850         l1_table = qemu_malloc(l1_size2);
1851         l1_allocated = 1;
1852         if (bdrv_pread(s->hd, l1_table_offset,
1853                        l1_table, l1_size2) != l1_size2)
1854             goto fail;
1855         for(i = 0;i < l1_size; i++)
1856             be64_to_cpus(&l1_table[i]);
1857     } else {
1858         assert(l1_size == s->l1_size);
1859         l1_table = s->l1_table;
1860         l1_allocated = 0;
1861     }
1862
1863     l2_size = s->l2_size * sizeof(uint64_t);
1864     l2_table = qemu_malloc(l2_size);
1865     l1_modified = 0;
1866     for(i = 0; i < l1_size; i++) {
1867         l2_offset = l1_table[i];
1868         if (l2_offset) {
1869             old_l2_offset = l2_offset;
1870             l2_offset &= ~QCOW_OFLAG_COPIED;
1871             l2_modified = 0;
1872             if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
1873                 goto fail;
1874             for(j = 0; j < s->l2_size; j++) {
1875                 offset = be64_to_cpu(l2_table[j]);
1876                 if (offset != 0) {
1877                     old_offset = offset;
1878                     offset &= ~QCOW_OFLAG_COPIED;
1879                     if (offset & QCOW_OFLAG_COMPRESSED) {
1880                         nb_csectors = ((offset >> s->csize_shift) &
1881                                        s->csize_mask) + 1;
1882                         if (addend != 0)
1883                             update_refcount(bs, (offset & s->cluster_offset_mask) & ~511,
1884                                             nb_csectors * 512, addend);
1885                         /* compressed clusters are never modified */
1886                         refcount = 2;
1887                     } else {
1888                         if (addend != 0) {
1889                             refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
1890                         } else {
1891                             refcount = get_refcount(bs, offset >> s->cluster_bits);
1892                         }
1893                     }
1894
1895                     if (refcount == 1) {
1896                         offset |= QCOW_OFLAG_COPIED;
1897                     }
1898                     if (offset != old_offset) {
1899                         l2_table[j] = cpu_to_be64(offset);
1900                         l2_modified = 1;
1901                     }
1902                 }
1903             }
1904             if (l2_modified) {
1905                 if (bdrv_pwrite(s->hd,
1906                                 l2_offset, l2_table, l2_size) != l2_size)
1907                     goto fail;
1908             }
1909
1910             if (addend != 0) {
1911                 refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
1912             } else {
1913                 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
1914             }
1915             if (refcount == 1) {
1916                 l2_offset |= QCOW_OFLAG_COPIED;
1917             }
1918             if (l2_offset != old_l2_offset) {
1919                 l1_table[i] = l2_offset;
1920                 l1_modified = 1;
1921             }
1922         }
1923     }
1924     if (l1_modified) {
1925         for(i = 0; i < l1_size; i++)
1926             cpu_to_be64s(&l1_table[i]);
1927         if (bdrv_pwrite(s->hd, l1_table_offset, l1_table,
1928                         l1_size2) != l1_size2)
1929             goto fail;
1930         for(i = 0; i < l1_size; i++)
1931             be64_to_cpus(&l1_table[i]);
1932     }
1933     if (l1_allocated)
1934         qemu_free(l1_table);
1935     qemu_free(l2_table);
1936     return 0;
1937  fail:
1938     if (l1_allocated)
1939         qemu_free(l1_table);
1940     qemu_free(l2_table);
1941     return -EIO;
1942 }
1943
1944 static void qcow_free_snapshots(BlockDriverState *bs)
1945 {
1946     BDRVQcowState *s = bs->opaque;
1947     int i;
1948
1949     for(i = 0; i < s->nb_snapshots; i++) {
1950         qemu_free(s->snapshots[i].name);
1951         qemu_free(s->snapshots[i].id_str);
1952     }
1953     qemu_free(s->snapshots);
1954     s->snapshots = NULL;
1955     s->nb_snapshots = 0;
1956 }
1957
1958 static int qcow_read_snapshots(BlockDriverState *bs)
1959 {
1960     BDRVQcowState *s = bs->opaque;
1961     QCowSnapshotHeader h;
1962     QCowSnapshot *sn;
1963     int i, id_str_size, name_size;
1964     int64_t offset;
1965     uint32_t extra_data_size;
1966
1967     if (!s->nb_snapshots) {
1968         s->snapshots = NULL;
1969         s->snapshots_size = 0;
1970         return 0;
1971     }
1972
1973     offset = s->snapshots_offset;
1974     s->snapshots = qemu_mallocz(s->nb_snapshots * sizeof(QCowSnapshot));
1975     for(i = 0; i < s->nb_snapshots; i++) {
1976         offset = align_offset(offset, 8);
1977         if (bdrv_pread(s->hd, offset, &h, sizeof(h)) != sizeof(h))
1978             goto fail;
1979         offset += sizeof(h);
1980         sn = s->snapshots + i;
1981         sn->l1_table_offset = be64_to_cpu(h.l1_table_offset);
1982         sn->l1_size = be32_to_cpu(h.l1_size);
1983         sn->vm_state_size = be32_to_cpu(h.vm_state_size);
1984         sn->date_sec = be32_to_cpu(h.date_sec);
1985         sn->date_nsec = be32_to_cpu(h.date_nsec);
1986         sn->vm_clock_nsec = be64_to_cpu(h.vm_clock_nsec);
1987         extra_data_size = be32_to_cpu(h.extra_data_size);
1988
1989         id_str_size = be16_to_cpu(h.id_str_size);
1990         name_size = be16_to_cpu(h.name_size);
1991
1992         offset += extra_data_size;
1993
1994         sn->id_str = qemu_malloc(id_str_size + 1);
1995         if (bdrv_pread(s->hd, offset, sn->id_str, id_str_size) != id_str_size)
1996             goto fail;
1997         offset += id_str_size;
1998         sn->id_str[id_str_size] = '\0';
1999
2000         sn->name = qemu_malloc(name_size + 1);
2001         if (bdrv_pread(s->hd, offset, sn->name, name_size) != name_size)
2002             goto fail;
2003         offset += name_size;
2004         sn->name[name_size] = '\0';
2005     }
2006     s->snapshots_size = offset - s->snapshots_offset;
2007     return 0;
2008  fail:
2009     qcow_free_snapshots(bs);
2010     return -1;
2011 }
2012
2013 /* add at the end of the file a new list of snapshots */
2014 static int qcow_write_snapshots(BlockDriverState *bs)
2015 {
2016     BDRVQcowState *s = bs->opaque;
2017     QCowSnapshot *sn;
2018     QCowSnapshotHeader h;
2019     int i, name_size, id_str_size, snapshots_size;
2020     uint64_t data64;
2021     uint32_t data32;
2022     int64_t offset, snapshots_offset;
2023
2024     /* compute the size of the snapshots */
2025     offset = 0;
2026     for(i = 0; i < s->nb_snapshots; i++) {
2027         sn = s->snapshots + i;
2028         offset = align_offset(offset, 8);
2029         offset += sizeof(h);
2030         offset += strlen(sn->id_str);
2031         offset += strlen(sn->name);
2032     }
2033     snapshots_size = offset;
2034
2035     snapshots_offset = alloc_clusters(bs, snapshots_size);
2036     offset = snapshots_offset;
2037
2038     for(i = 0; i < s->nb_snapshots; i++) {
2039         sn = s->snapshots + i;
2040         memset(&h, 0, sizeof(h));
2041         h.l1_table_offset = cpu_to_be64(sn->l1_table_offset);
2042         h.l1_size = cpu_to_be32(sn->l1_size);
2043         h.vm_state_size = cpu_to_be32(sn->vm_state_size);
2044         h.date_sec = cpu_to_be32(sn->date_sec);
2045         h.date_nsec = cpu_to_be32(sn->date_nsec);
2046         h.vm_clock_nsec = cpu_to_be64(sn->vm_clock_nsec);
2047
2048         id_str_size = strlen(sn->id_str);
2049         name_size = strlen(sn->name);
2050         h.id_str_size = cpu_to_be16(id_str_size);
2051         h.name_size = cpu_to_be16(name_size);
2052         offset = align_offset(offset, 8);
2053         if (bdrv_pwrite(s->hd, offset, &h, sizeof(h)) != sizeof(h))
2054             goto fail;
2055         offset += sizeof(h);
2056         if (bdrv_pwrite(s->hd, offset, sn->id_str, id_str_size) != id_str_size)
2057             goto fail;
2058         offset += id_str_size;
2059         if (bdrv_pwrite(s->hd, offset, sn->name, name_size) != name_size)
2060             goto fail;
2061         offset += name_size;
2062     }
2063
2064     /* update the various header fields */
2065     data64 = cpu_to_be64(snapshots_offset);
2066     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, snapshots_offset),
2067                     &data64, sizeof(data64)) != sizeof(data64))
2068         goto fail;
2069     data32 = cpu_to_be32(s->nb_snapshots);
2070     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, nb_snapshots),
2071                     &data32, sizeof(data32)) != sizeof(data32))
2072         goto fail;
2073
2074     /* free the old snapshot table */
2075     free_clusters(bs, s->snapshots_offset, s->snapshots_size);
2076     s->snapshots_offset = snapshots_offset;
2077     s->snapshots_size = snapshots_size;
2078     return 0;
2079  fail:
2080     return -1;
2081 }
2082
2083 static void find_new_snapshot_id(BlockDriverState *bs,
2084                                  char *id_str, int id_str_size)
2085 {
2086     BDRVQcowState *s = bs->opaque;
2087     QCowSnapshot *sn;
2088     int i, id, id_max = 0;
2089
2090     for(i = 0; i < s->nb_snapshots; i++) {
2091         sn = s->snapshots + i;
2092         id = strtoul(sn->id_str, NULL, 10);
2093         if (id > id_max)
2094             id_max = id;
2095     }
2096     snprintf(id_str, id_str_size, "%d", id_max + 1);
2097 }
2098
2099 static int find_snapshot_by_id(BlockDriverState *bs, const char *id_str)
2100 {
2101     BDRVQcowState *s = bs->opaque;
2102     int i;
2103
2104     for(i = 0; i < s->nb_snapshots; i++) {
2105         if (!strcmp(s->snapshots[i].id_str, id_str))
2106             return i;
2107     }
2108     return -1;
2109 }
2110
2111 static int find_snapshot_by_id_or_name(BlockDriverState *bs, const char *name)
2112 {
2113     BDRVQcowState *s = bs->opaque;
2114     int i, ret;
2115
2116     ret = find_snapshot_by_id(bs, name);
2117     if (ret >= 0)
2118         return ret;
2119     for(i = 0; i < s->nb_snapshots; i++) {
2120         if (!strcmp(s->snapshots[i].name, name))
2121             return i;
2122     }
2123     return -1;
2124 }
2125
2126 /* if no id is provided, a new one is constructed */
2127 static int qcow_snapshot_create(BlockDriverState *bs,
2128                                 QEMUSnapshotInfo *sn_info)
2129 {
2130     BDRVQcowState *s = bs->opaque;
2131     QCowSnapshot *snapshots1, sn1, *sn = &sn1;
2132     int i, ret;
2133     uint64_t *l1_table = NULL;
2134
2135     memset(sn, 0, sizeof(*sn));
2136
2137     if (sn_info->id_str[0] == '\0') {
2138         /* compute a new id */
2139         find_new_snapshot_id(bs, sn_info->id_str, sizeof(sn_info->id_str));
2140     }
2141
2142     /* check that the ID is unique */
2143     if (find_snapshot_by_id(bs, sn_info->id_str) >= 0)
2144         return -ENOENT;
2145
2146     sn->id_str = qemu_strdup(sn_info->id_str);
2147     if (!sn->id_str)
2148         goto fail;
2149     sn->name = qemu_strdup(sn_info->name);
2150     if (!sn->name)
2151         goto fail;
2152     sn->vm_state_size = sn_info->vm_state_size;
2153     sn->date_sec = sn_info->date_sec;
2154     sn->date_nsec = sn_info->date_nsec;
2155     sn->vm_clock_nsec = sn_info->vm_clock_nsec;
2156
2157     ret = update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 1);
2158     if (ret < 0)
2159         goto fail;
2160
2161     /* create the L1 table of the snapshot */
2162     sn->l1_table_offset = alloc_clusters(bs, s->l1_size * sizeof(uint64_t));
2163     sn->l1_size = s->l1_size;
2164
2165     l1_table = qemu_malloc(s->l1_size * sizeof(uint64_t));
2166     for(i = 0; i < s->l1_size; i++) {
2167         l1_table[i] = cpu_to_be64(s->l1_table[i]);
2168     }
2169     if (bdrv_pwrite(s->hd, sn->l1_table_offset,
2170                     l1_table, s->l1_size * sizeof(uint64_t)) !=
2171         (s->l1_size * sizeof(uint64_t)))
2172         goto fail;
2173     qemu_free(l1_table);
2174     l1_table = NULL;
2175
2176     snapshots1 = qemu_malloc((s->nb_snapshots + 1) * sizeof(QCowSnapshot));
2177     if (s->snapshots) {
2178         memcpy(snapshots1, s->snapshots, s->nb_snapshots * sizeof(QCowSnapshot));
2179         qemu_free(s->snapshots);
2180     }
2181     s->snapshots = snapshots1;
2182     s->snapshots[s->nb_snapshots++] = *sn;
2183
2184     if (qcow_write_snapshots(bs) < 0)
2185         goto fail;
2186 #ifdef DEBUG_ALLOC
2187     check_refcounts(bs);
2188 #endif
2189     return 0;
2190  fail:
2191     qemu_free(sn->name);
2192     qemu_free(l1_table);
2193     return -1;
2194 }
2195
2196 /* copy the snapshot 'snapshot_name' into the current disk image */
2197 static int qcow_snapshot_goto(BlockDriverState *bs,
2198                               const char *snapshot_id)
2199 {
2200     BDRVQcowState *s = bs->opaque;
2201     QCowSnapshot *sn;
2202     int i, snapshot_index, l1_size2;
2203
2204     snapshot_index = find_snapshot_by_id_or_name(bs, snapshot_id);
2205     if (snapshot_index < 0)
2206         return -ENOENT;
2207     sn = &s->snapshots[snapshot_index];
2208
2209     if (update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, -1) < 0)
2210         goto fail;
2211
2212     if (grow_l1_table(bs, sn->l1_size) < 0)
2213         goto fail;
2214
2215     s->l1_size = sn->l1_size;
2216     l1_size2 = s->l1_size * sizeof(uint64_t);
2217     /* copy the snapshot l1 table to the current l1 table */
2218     if (bdrv_pread(s->hd, sn->l1_table_offset,
2219                    s->l1_table, l1_size2) != l1_size2)
2220         goto fail;
2221     if (bdrv_pwrite(s->hd, s->l1_table_offset,
2222                     s->l1_table, l1_size2) != l1_size2)
2223         goto fail;
2224     for(i = 0;i < s->l1_size; i++) {
2225         be64_to_cpus(&s->l1_table[i]);
2226     }
2227
2228     if (update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 1) < 0)
2229         goto fail;
2230
2231 #ifdef DEBUG_ALLOC
2232     check_refcounts(bs);
2233 #endif
2234     return 0;
2235  fail:
2236     return -EIO;
2237 }
2238
2239 static int qcow_snapshot_delete(BlockDriverState *bs, const char *snapshot_id)
2240 {
2241     BDRVQcowState *s = bs->opaque;
2242     QCowSnapshot *sn;
2243     int snapshot_index, ret;
2244
2245     snapshot_index = find_snapshot_by_id_or_name(bs, snapshot_id);
2246     if (snapshot_index < 0)
2247         return -ENOENT;
2248     sn = &s->snapshots[snapshot_index];
2249
2250     ret = update_snapshot_refcount(bs, sn->l1_table_offset, sn->l1_size, -1);
2251     if (ret < 0)
2252         return ret;
2253     /* must update the copied flag on the current cluster offsets */
2254     ret = update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 0);
2255     if (ret < 0)
2256         return ret;
2257     free_clusters(bs, sn->l1_table_offset, sn->l1_size * sizeof(uint64_t));
2258
2259     qemu_free(sn->id_str);
2260     qemu_free(sn->name);
2261     memmove(sn, sn + 1, (s->nb_snapshots - snapshot_index - 1) * sizeof(*sn));
2262     s->nb_snapshots--;
2263     ret = qcow_write_snapshots(bs);
2264     if (ret < 0) {
2265         /* XXX: restore snapshot if error ? */
2266         return ret;
2267     }
2268 #ifdef DEBUG_ALLOC
2269     check_refcounts(bs);
2270 #endif
2271     return 0;
2272 }
2273
2274 static int qcow_snapshot_list(BlockDriverState *bs,
2275                               QEMUSnapshotInfo **psn_tab)
2276 {
2277     BDRVQcowState *s = bs->opaque;
2278     QEMUSnapshotInfo *sn_tab, *sn_info;
2279     QCowSnapshot *sn;
2280     int i;
2281
2282     if (!s->nb_snapshots) {
2283         *psn_tab = NULL;
2284         return s->nb_snapshots;
2285     }
2286
2287     sn_tab = qemu_mallocz(s->nb_snapshots * sizeof(QEMUSnapshotInfo));
2288     for(i = 0; i < s->nb_snapshots; i++) {
2289         sn_info = sn_tab + i;
2290         sn = s->snapshots + i;
2291         pstrcpy(sn_info->id_str, sizeof(sn_info->id_str),
2292                 sn->id_str);
2293         pstrcpy(sn_info->name, sizeof(sn_info->name),
2294                 sn->name);
2295         sn_info->vm_state_size = sn->vm_state_size;
2296         sn_info->date_sec = sn->date_sec;
2297         sn_info->date_nsec = sn->date_nsec;
2298         sn_info->vm_clock_nsec = sn->vm_clock_nsec;
2299     }
2300     *psn_tab = sn_tab;
2301     return s->nb_snapshots;
2302 }
2303
2304 /*********************************************************/
2305 /* refcount handling */
2306
2307 static int refcount_init(BlockDriverState *bs)
2308 {
2309     BDRVQcowState *s = bs->opaque;
2310     int ret, refcount_table_size2, i;
2311
2312     s->refcount_block_cache = qemu_malloc(s->cluster_size);
2313     refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
2314     s->refcount_table = qemu_malloc(refcount_table_size2);
2315     if (s->refcount_table_size > 0) {
2316         ret = bdrv_pread(s->hd, s->refcount_table_offset,
2317                          s->refcount_table, refcount_table_size2);
2318         if (ret != refcount_table_size2)
2319             goto fail;
2320         for(i = 0; i < s->refcount_table_size; i++)
2321             be64_to_cpus(&s->refcount_table[i]);
2322     }
2323     return 0;
2324  fail:
2325     return -ENOMEM;
2326 }
2327
2328 static void refcount_close(BlockDriverState *bs)
2329 {
2330     BDRVQcowState *s = bs->opaque;
2331     qemu_free(s->refcount_block_cache);
2332     qemu_free(s->refcount_table);
2333 }
2334
2335
2336 static int load_refcount_block(BlockDriverState *bs,
2337                                int64_t refcount_block_offset)
2338 {
2339     BDRVQcowState *s = bs->opaque;
2340     int ret;
2341     ret = bdrv_pread(s->hd, refcount_block_offset, s->refcount_block_cache,
2342                      s->cluster_size);
2343     if (ret != s->cluster_size)
2344         return -EIO;
2345     s->refcount_block_cache_offset = refcount_block_offset;
2346     return 0;
2347 }
2348
2349 static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
2350 {
2351     BDRVQcowState *s = bs->opaque;
2352     int refcount_table_index, block_index;
2353     int64_t refcount_block_offset;
2354
2355     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
2356     if (refcount_table_index >= s->refcount_table_size)
2357         return 0;
2358     refcount_block_offset = s->refcount_table[refcount_table_index];
2359     if (!refcount_block_offset)
2360         return 0;
2361     if (refcount_block_offset != s->refcount_block_cache_offset) {
2362         /* better than nothing: return allocated if read error */
2363         if (load_refcount_block(bs, refcount_block_offset) < 0)
2364             return 1;
2365     }
2366     block_index = cluster_index &
2367         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
2368     return be16_to_cpu(s->refcount_block_cache[block_index]);
2369 }
2370
2371 /* return < 0 if error */
2372 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
2373 {
2374     BDRVQcowState *s = bs->opaque;
2375     int i, nb_clusters;
2376
2377     nb_clusters = size_to_clusters(s, size);
2378 retry:
2379     for(i = 0; i < nb_clusters; i++) {
2380         int64_t i = s->free_cluster_index++;
2381         if (get_refcount(bs, i) != 0)
2382             goto retry;
2383     }
2384 #ifdef DEBUG_ALLOC2
2385     printf("alloc_clusters: size=%lld -> %lld\n",
2386             size,
2387             (s->free_cluster_index - nb_clusters) << s->cluster_bits);
2388 #endif
2389     return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
2390 }
2391
2392 static int64_t alloc_clusters(BlockDriverState *bs, int64_t size)
2393 {
2394     int64_t offset;
2395
2396     offset = alloc_clusters_noref(bs, size);
2397     update_refcount(bs, offset, size, 1);
2398     return offset;
2399 }
2400
2401 /* only used to allocate compressed sectors. We try to allocate
2402    contiguous sectors. size must be <= cluster_size */
2403 static int64_t alloc_bytes(BlockDriverState *bs, int size)
2404 {
2405     BDRVQcowState *s = bs->opaque;
2406     int64_t offset, cluster_offset;
2407     int free_in_cluster;
2408
2409     assert(size > 0 && size <= s->cluster_size);
2410     if (s->free_byte_offset == 0) {
2411         s->free_byte_offset = alloc_clusters(bs, s->cluster_size);
2412     }
2413  redo:
2414     free_in_cluster = s->cluster_size -
2415         (s->free_byte_offset & (s->cluster_size - 1));
2416     if (size <= free_in_cluster) {
2417         /* enough space in current cluster */
2418         offset = s->free_byte_offset;
2419         s->free_byte_offset += size;
2420         free_in_cluster -= size;
2421         if (free_in_cluster == 0)
2422             s->free_byte_offset = 0;
2423         if ((offset & (s->cluster_size - 1)) != 0)
2424             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
2425     } else {
2426         offset = alloc_clusters(bs, s->cluster_size);
2427         cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
2428         if ((cluster_offset + s->cluster_size) == offset) {
2429             /* we are lucky: contiguous data */
2430             offset = s->free_byte_offset;
2431             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
2432             s->free_byte_offset += size;
2433         } else {
2434             s->free_byte_offset = offset;
2435             goto redo;
2436         }
2437     }
2438     return offset;
2439 }
2440
2441 static void free_clusters(BlockDriverState *bs,
2442                           int64_t offset, int64_t size)
2443 {
2444     update_refcount(bs, offset, size, -1);
2445 }
2446
2447 static int grow_refcount_table(BlockDriverState *bs, int min_size)
2448 {
2449     BDRVQcowState *s = bs->opaque;
2450     int new_table_size, new_table_size2, refcount_table_clusters, i, ret;
2451     uint64_t *new_table;
2452     int64_t table_offset;
2453     uint8_t data[12];
2454     int old_table_size;
2455     int64_t old_table_offset;
2456
2457     if (min_size <= s->refcount_table_size)
2458         return 0;
2459     /* compute new table size */
2460     refcount_table_clusters = s->refcount_table_size >> (s->cluster_bits - 3);
2461     for(;;) {
2462         if (refcount_table_clusters == 0) {
2463             refcount_table_clusters = 1;
2464         } else {
2465             refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
2466         }
2467         new_table_size = refcount_table_clusters << (s->cluster_bits - 3);
2468         if (min_size <= new_table_size)
2469             break;
2470     }
2471 #ifdef DEBUG_ALLOC2
2472     printf("grow_refcount_table from %d to %d\n",
2473            s->refcount_table_size,
2474            new_table_size);
2475 #endif
2476     new_table_size2 = new_table_size * sizeof(uint64_t);
2477     new_table = qemu_mallocz(new_table_size2);
2478     memcpy(new_table, s->refcount_table,
2479            s->refcount_table_size * sizeof(uint64_t));
2480     for(i = 0; i < s->refcount_table_size; i++)
2481         cpu_to_be64s(&new_table[i]);
2482     /* Note: we cannot update the refcount now to avoid recursion */
2483     table_offset = alloc_clusters_noref(bs, new_table_size2);
2484     ret = bdrv_pwrite(s->hd, table_offset, new_table, new_table_size2);
2485     if (ret != new_table_size2)
2486         goto fail;
2487     for(i = 0; i < s->refcount_table_size; i++)
2488         be64_to_cpus(&new_table[i]);
2489
2490     cpu_to_be64w((uint64_t*)data, table_offset);
2491     cpu_to_be32w((uint32_t*)(data + 8), refcount_table_clusters);
2492     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, refcount_table_offset),
2493                     data, sizeof(data)) != sizeof(data))
2494         goto fail;
2495     qemu_free(s->refcount_table);
2496     old_table_offset = s->refcount_table_offset;
2497     old_table_size = s->refcount_table_size;
2498     s->refcount_table = new_table;
2499     s->refcount_table_size = new_table_size;
2500     s->refcount_table_offset = table_offset;
2501
2502     update_refcount(bs, table_offset, new_table_size2, 1);
2503     free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
2504     return 0;
2505  fail:
2506     free_clusters(bs, table_offset, new_table_size2);
2507     qemu_free(new_table);
2508     return -EIO;
2509 }
2510
2511 /* addend must be 1 or -1 */
2512 /* XXX: cache several refcount block clusters ? */
2513 static int update_cluster_refcount(BlockDriverState *bs,
2514                                    int64_t cluster_index,
2515                                    int addend)
2516 {
2517     BDRVQcowState *s = bs->opaque;
2518     int64_t offset, refcount_block_offset;
2519     int ret, refcount_table_index, block_index, refcount;
2520     uint64_t data64;
2521
2522     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
2523     if (refcount_table_index >= s->refcount_table_size) {
2524         if (addend < 0)
2525             return -EINVAL;
2526         ret = grow_refcount_table(bs, refcount_table_index + 1);
2527         if (ret < 0)
2528             return ret;
2529     }
2530     refcount_block_offset = s->refcount_table[refcount_table_index];
2531     if (!refcount_block_offset) {
2532         if (addend < 0)
2533             return -EINVAL;
2534         /* create a new refcount block */
2535         /* Note: we cannot update the refcount now to avoid recursion */
2536         offset = alloc_clusters_noref(bs, s->cluster_size);
2537         memset(s->refcount_block_cache, 0, s->cluster_size);
2538         ret = bdrv_pwrite(s->hd, offset, s->refcount_block_cache, s->cluster_size);
2539         if (ret != s->cluster_size)
2540             return -EINVAL;
2541         s->refcount_table[refcount_table_index] = offset;
2542         data64 = cpu_to_be64(offset);
2543         ret = bdrv_pwrite(s->hd, s->refcount_table_offset +
2544                           refcount_table_index * sizeof(uint64_t),
2545                           &data64, sizeof(data64));
2546         if (ret != sizeof(data64))
2547             return -EINVAL;
2548
2549         refcount_block_offset = offset;
2550         s->refcount_block_cache_offset = offset;
2551         update_refcount(bs, offset, s->cluster_size, 1);
2552     } else {
2553         if (refcount_block_offset != s->refcount_block_cache_offset) {
2554             if (load_refcount_block(bs, refcount_block_offset) < 0)
2555                 return -EIO;
2556         }
2557     }
2558     /* we can update the count and save it */
2559     block_index = cluster_index &
2560         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
2561     refcount = be16_to_cpu(s->refcount_block_cache[block_index]);
2562     refcount += addend;
2563     if (refcount < 0 || refcount > 0xffff)
2564         return -EINVAL;
2565     if (refcount == 0 && cluster_index < s->free_cluster_index) {
2566         s->free_cluster_index = cluster_index;
2567     }
2568     s->refcount_block_cache[block_index] = cpu_to_be16(refcount);
2569     if (bdrv_pwrite(s->hd,
2570                     refcount_block_offset + (block_index << REFCOUNT_SHIFT),
2571                     &s->refcount_block_cache[block_index], 2) != 2)
2572         return -EIO;
2573     return refcount;
2574 }
2575
2576 static void update_refcount(BlockDriverState *bs,
2577                             int64_t offset, int64_t length,
2578                             int addend)
2579 {
2580     BDRVQcowState *s = bs->opaque;
2581     int64_t start, last, cluster_offset;
2582
2583 #ifdef DEBUG_ALLOC2
2584     printf("update_refcount: offset=%lld size=%lld addend=%d\n",
2585            offset, length, addend);
2586 #endif
2587     if (length <= 0)
2588         return;
2589     start = offset & ~(s->cluster_size - 1);
2590     last = (offset + length - 1) & ~(s->cluster_size - 1);
2591     for(cluster_offset = start; cluster_offset <= last;
2592         cluster_offset += s->cluster_size) {
2593         update_cluster_refcount(bs, cluster_offset >> s->cluster_bits, addend);
2594     }
2595 }
2596
2597 /*
2598  * Increases the refcount for a range of clusters in a given refcount table.
2599  * This is used to construct a temporary refcount table out of L1 and L2 tables
2600  * which can be compared the the refcount table saved in the image.
2601  *
2602  * Returns the number of errors in the image that were found
2603  */
2604 static int inc_refcounts(BlockDriverState *bs,
2605                           uint16_t *refcount_table,
2606                           int refcount_table_size,
2607                           int64_t offset, int64_t size)
2608 {
2609     BDRVQcowState *s = bs->opaque;
2610     int64_t start, last, cluster_offset;
2611     int k;
2612     int errors = 0;
2613
2614     if (size <= 0)
2615         return 0;
2616
2617     start = offset & ~(s->cluster_size - 1);
2618     last = (offset + size - 1) & ~(s->cluster_size - 1);
2619     for(cluster_offset = start; cluster_offset <= last;
2620         cluster_offset += s->cluster_size) {
2621         k = cluster_offset >> s->cluster_bits;
2622         if (k < 0 || k >= refcount_table_size) {
2623             fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
2624                 cluster_offset);
2625             errors++;
2626         } else {
2627             if (++refcount_table[k] == 0) {
2628                 fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
2629                     "\n", cluster_offset);
2630                 errors++;
2631             }
2632         }
2633     }
2634
2635     return errors;
2636 }
2637
2638 /*
2639  * Increases the refcount in the given refcount table for the all clusters
2640  * referenced in the L2 table. While doing so, performs some checks on L2
2641  * entries.
2642  *
2643  * Returns the number of errors found by the checks or -errno if an internal
2644  * error occurred.
2645  */
2646 static int check_refcounts_l2(BlockDriverState *bs,
2647     uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
2648     int check_copied)
2649 {
2650     BDRVQcowState *s = bs->opaque;
2651     uint64_t *l2_table, offset;
2652     int i, l2_size, nb_csectors, refcount;
2653     int errors = 0;
2654
2655     /* Read L2 table from disk */
2656     l2_size = s->l2_size * sizeof(uint64_t);
2657     l2_table = qemu_malloc(l2_size);
2658
2659     if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
2660         goto fail;
2661
2662     /* Do the actual checks */
2663     for(i = 0; i < s->l2_size; i++) {
2664         offset = be64_to_cpu(l2_table[i]);
2665         if (offset != 0) {
2666             if (offset & QCOW_OFLAG_COMPRESSED) {
2667                 /* Compressed clusters don't have QCOW_OFLAG_COPIED */
2668                 if (offset & QCOW_OFLAG_COPIED) {
2669                     fprintf(stderr, "ERROR: cluster %" PRId64 ": "
2670                         "copied flag must never be set for compressed "
2671                         "clusters\n", offset >> s->cluster_bits);
2672                     offset &= ~QCOW_OFLAG_COPIED;
2673                     errors++;
2674                 }
2675
2676                 /* Mark cluster as used */
2677                 nb_csectors = ((offset >> s->csize_shift) &
2678                                s->csize_mask) + 1;
2679                 offset &= s->cluster_offset_mask;
2680                 errors += inc_refcounts(bs, refcount_table,
2681                               refcount_table_size,
2682                               offset & ~511, nb_csectors * 512);
2683             } else {
2684                 /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
2685                 if (check_copied) {
2686                     uint64_t entry = offset;
2687                     offset &= ~QCOW_OFLAG_COPIED;
2688                     refcount = get_refcount(bs, offset >> s->cluster_bits);
2689                     if ((refcount == 1) != ((entry & QCOW_OFLAG_COPIED) != 0)) {
2690                         fprintf(stderr, "ERROR OFLAG_COPIED: offset=%"
2691                             PRIx64 " refcount=%d\n", entry, refcount);
2692                         errors++;
2693                     }
2694                 }
2695
2696                 /* Mark cluster as used */
2697                 offset &= ~QCOW_OFLAG_COPIED;
2698                 errors += inc_refcounts(bs, refcount_table,
2699                               refcount_table_size,
2700                               offset, s->cluster_size);
2701
2702                 /* Correct offsets are cluster aligned */
2703                 if (offset & (s->cluster_size - 1)) {
2704                     fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
2705                         "properly aligned; L2 entry corrupted.\n", offset);
2706                     errors++;
2707                 }
2708             }
2709         }
2710     }
2711
2712     qemu_free(l2_table);
2713     return errors;
2714
2715 fail:
2716     fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
2717     qemu_free(l2_table);
2718     return -EIO;
2719 }
2720
2721 /*
2722  * Increases the refcount for the L1 table, its L2 tables and all referenced
2723  * clusters in the given refcount table. While doing so, performs some checks
2724  * on L1 and L2 entries.
2725  *
2726  * Returns the number of errors found by the checks or -errno if an internal
2727  * error occurred.
2728  */
2729 static int check_refcounts_l1(BlockDriverState *bs,
2730                               uint16_t *refcount_table,
2731                               int refcount_table_size,
2732                               int64_t l1_table_offset, int l1_size,
2733                               int check_copied)
2734 {
2735     BDRVQcowState *s = bs->opaque;
2736     uint64_t *l1_table, l2_offset, l1_size2;
2737     int i, refcount, ret;
2738     int errors = 0;
2739
2740     l1_size2 = l1_size * sizeof(uint64_t);
2741
2742     /* Mark L1 table as used */
2743     errors += inc_refcounts(bs, refcount_table, refcount_table_size,
2744                   l1_table_offset, l1_size2);
2745
2746     /* Read L1 table entries from disk */
2747     l1_table = qemu_malloc(l1_size2);
2748     if (bdrv_pread(s->hd, l1_table_offset,
2749                    l1_table, l1_size2) != l1_size2)
2750         goto fail;
2751     for(i = 0;i < l1_size; i++)
2752         be64_to_cpus(&l1_table[i]);
2753
2754     /* Do the actual checks */
2755     for(i = 0; i < l1_size; i++) {
2756         l2_offset = l1_table[i];
2757         if (l2_offset) {
2758             /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
2759             if (check_copied) {
2760                 refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED)
2761                     >> s->cluster_bits);
2762                 if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
2763                     fprintf(stderr, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
2764                         " refcount=%d\n", l2_offset, refcount);
2765                     errors++;
2766                 }
2767             }
2768
2769             /* Mark L2 table as used */
2770             l2_offset &= ~QCOW_OFLAG_COPIED;
2771             errors += inc_refcounts(bs, refcount_table,
2772                           refcount_table_size,
2773                           l2_offset,
2774                           s->cluster_size);
2775
2776             /* L2 tables are cluster aligned */
2777             if (l2_offset & (s->cluster_size - 1)) {
2778                 fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
2779                     "cluster aligned; L1 entry corrupted\n", l2_offset);
2780                 errors++;
2781             }
2782
2783             /* Process and check L2 entries */
2784             ret = check_refcounts_l2(bs, refcount_table, refcount_table_size,
2785                 l2_offset, check_copied);
2786             if (ret < 0) {
2787                 goto fail;
2788             }
2789             errors += ret;
2790         }
2791     }
2792     qemu_free(l1_table);
2793     return errors;
2794
2795 fail:
2796     fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
2797     qemu_free(l1_table);
2798     return -EIO;
2799 }
2800
2801 /*
2802  * Checks an image for refcount consistency.
2803  *
2804  * Returns 0 if no errors are found, the number of errors in case the image is
2805  * detected as corrupted, and -errno when an internal error occured.
2806  */
2807 static int check_refcounts(BlockDriverState *bs)
2808 {
2809     BDRVQcowState *s = bs->opaque;
2810     int64_t size;
2811     int nb_clusters, refcount1, refcount2, i;
2812     QCowSnapshot *sn;
2813     uint16_t *refcount_table;
2814     int ret, errors = 0;
2815
2816     size = bdrv_getlength(s->hd);
2817     nb_clusters = size_to_clusters(s, size);
2818     refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
2819
2820     /* header */
2821     errors += inc_refcounts(bs, refcount_table, nb_clusters,
2822                   0, s->cluster_size);
2823
2824     /* current L1 table */
2825     ret = check_refcounts_l1(bs, refcount_table, nb_clusters,
2826                        s->l1_table_offset, s->l1_size, 1);
2827     if (ret < 0) {
2828         return ret;
2829     }
2830     errors += ret;
2831
2832     /* snapshots */
2833     for(i = 0; i < s->nb_snapshots; i++) {
2834         sn = s->snapshots + i;
2835         check_refcounts_l1(bs, refcount_table, nb_clusters,
2836                            sn->l1_table_offset, sn->l1_size, 0);
2837     }
2838     errors += inc_refcounts(bs, refcount_table, nb_clusters,
2839                   s->snapshots_offset, s->snapshots_size);
2840
2841     /* refcount data */
2842     errors += inc_refcounts(bs, refcount_table, nb_clusters,
2843                   s->refcount_table_offset,
2844                   s->refcount_table_size * sizeof(uint64_t));
2845     for(i = 0; i < s->refcount_table_size; i++) {
2846         int64_t offset;
2847         offset = s->refcount_table[i];
2848         if (offset != 0) {
2849             errors += inc_refcounts(bs, refcount_table, nb_clusters,
2850                           offset, s->cluster_size);
2851         }
2852     }
2853
2854     /* compare ref counts */
2855     for(i = 0; i < nb_clusters; i++) {
2856         refcount1 = get_refcount(bs, i);
2857         refcount2 = refcount_table[i];
2858         if (refcount1 != refcount2) {
2859             fprintf(stderr, "ERROR cluster %d refcount=%d reference=%d\n",
2860                    i, refcount1, refcount2);
2861             errors++;
2862         }
2863     }
2864
2865     qemu_free(refcount_table);
2866
2867     return errors;
2868 }
2869
2870 static int qcow_check(BlockDriverState *bs)
2871 {
2872     return check_refcounts(bs);
2873 }
2874
2875 #if 0
2876 static void dump_refcounts(BlockDriverState *bs)
2877 {
2878     BDRVQcowState *s = bs->opaque;
2879     int64_t nb_clusters, k, k1, size;
2880     int refcount;
2881
2882     size = bdrv_getlength(s->hd);
2883     nb_clusters = size_to_clusters(s, size);
2884     for(k = 0; k < nb_clusters;) {
2885         k1 = k;
2886         refcount = get_refcount(bs, k);
2887         k++;
2888         while (k < nb_clusters && get_refcount(bs, k) == refcount)
2889             k++;
2890         printf("%lld: refcount=%d nb=%lld\n", k, refcount, k - k1);
2891     }
2892 }
2893 #endif
2894
2895 static int qcow_put_buffer(BlockDriverState *bs, const uint8_t *buf,
2896                            int64_t pos, int size)
2897 {
2898     int growable = bs->growable;
2899
2900     bs->growable = 1;
2901     bdrv_pwrite(bs, pos, buf, size);
2902     bs->growable = growable;
2903
2904     return size;
2905 }
2906
2907 static int qcow_get_buffer(BlockDriverState *bs, uint8_t *buf,
2908                            int64_t pos, int size)
2909 {
2910     int growable = bs->growable;
2911     int ret;
2912
2913     bs->growable = 1;
2914     ret = bdrv_pread(bs, pos, buf, size);
2915     bs->growable = growable;
2916
2917     return ret;
2918 }
2919
2920 static QEMUOptionParameter qcow_create_options[] = {
2921     { BLOCK_OPT_SIZE,           OPT_SIZE },
2922     { BLOCK_OPT_BACKING_FILE,   OPT_STRING },
2923     { BLOCK_OPT_BACKING_FMT,    OPT_STRING },
2924     { BLOCK_OPT_ENCRYPT,        OPT_FLAG },
2925     { BLOCK_OPT_CLUSTER_SIZE,   OPT_SIZE },
2926     { NULL }
2927 };
2928
2929 static BlockDriver bdrv_qcow2 = {
2930     .format_name        = "qcow2",
2931     .instance_size      = sizeof(BDRVQcowState),
2932     .bdrv_probe         = qcow_probe,
2933     .bdrv_open          = qcow_open,
2934     .bdrv_close         = qcow_close,
2935     .bdrv_create        = qcow_create,
2936     .bdrv_flush         = qcow_flush,
2937     .bdrv_is_allocated  = qcow_is_allocated,
2938     .bdrv_set_key       = qcow_set_key,
2939     .bdrv_make_empty    = qcow_make_empty,
2940
2941     .bdrv_aio_readv     = qcow_aio_readv,
2942     .bdrv_aio_writev    = qcow_aio_writev,
2943     .bdrv_aio_cancel    = qcow_aio_cancel,
2944     .aiocb_size         = sizeof(QCowAIOCB),
2945     .bdrv_write_compressed = qcow_write_compressed,
2946
2947     .bdrv_snapshot_create = qcow_snapshot_create,
2948     .bdrv_snapshot_goto = qcow_snapshot_goto,
2949     .bdrv_snapshot_delete = qcow_snapshot_delete,
2950     .bdrv_snapshot_list = qcow_snapshot_list,
2951     .bdrv_get_info      = qcow_get_info,
2952
2953     .bdrv_put_buffer    = qcow_put_buffer,
2954     .bdrv_get_buffer    = qcow_get_buffer,
2955
2956     .create_options = qcow_create_options,
2957     .bdrv_check = qcow_check,
2958 };
2959
2960 static void bdrv_qcow2_init(void)
2961 {
2962     bdrv_register(&bdrv_qcow2);
2963 }
2964
2965 block_init(bdrv_qcow2_init);