git.maemo.org Git - qemu/blob - 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 <zlib.h>
  27 #include "aes.h"
  28 #include <assert.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
  49 #define QCOW_MAGIC (('Q' << 24) | ('F' << 16) | ('I' << 8) | 0xfb)
  50 #define QCOW_VERSION 2
  51
  52 #define QCOW_CRYPT_NONE 0
  53 #define QCOW_CRYPT_AES  1
  54
  55 /* indicate that the refcount of the referenced cluster is exactly one. */
  56 #define QCOW_OFLAG_COPIED     (1LL << 63)
  57 /* indicate that the cluster is compressed (they never have the copied flag) */
  58 #define QCOW_OFLAG_COMPRESSED (1LL << 62)
  59
  60 #define REFCOUNT_SHIFT 1 /* refcount size is 2 bytes */
  61
  62 #ifndef offsetof
  63 #define offsetof(type, field) ((size_t) &((type *)0)->field)
  64 #endif
  65
  66 typedef struct QCowHeader {
  67     uint32_t magic;
  68     uint32_t version;
  69     uint64_t backing_file_offset;
  70     uint32_t backing_file_size;
  71     uint32_t cluster_bits;
  72     uint64_t size; /* in bytes */
  73     uint32_t crypt_method;
  74     uint32_t l1_size; /* XXX: save number of clusters instead ? */
  75     uint64_t l1_table_offset;
  76     uint64_t refcount_table_offset;
  77     uint32_t refcount_table_clusters;
  78     uint32_t nb_snapshots;
  79     uint64_t snapshots_offset;
  80 } QCowHeader;
  81
  82 typedef struct __attribute__((packed)) QCowSnapshotHeader {
  83     /* header is 8 byte aligned */
  84     uint64_t l1_table_offset;
  85
  86     uint32_t l1_size;
  87     uint16_t id_str_size;
  88     uint16_t name_size;
  89
  90     uint32_t date_sec;
  91     uint32_t date_nsec;
  92
  93     uint64_t vm_clock_nsec;
  94
  95     uint32_t vm_state_size;
  96     uint32_t extra_data_size; /* for extension */
  97     /* extra data follows */
  98     /* id_str follows */
  99     /* name follows  */
 100 } QCowSnapshotHeader;
 101
 102 #define L2_CACHE_SIZE 16
 103
 104 typedef struct QCowSnapshot {
 105     uint64_t l1_table_offset;
 106     uint32_t l1_size;
 107     char *id_str;
 108     char *name;
 109     uint32_t vm_state_size;
 110     uint32_t date_sec;
 111     uint32_t date_nsec;
 112     uint64_t vm_clock_nsec;
 113 } QCowSnapshot;
 114
 115 typedef struct BDRVQcowState {
 116     BlockDriverState *hd;
 117     int cluster_bits;
 118     int cluster_size;
 119     int cluster_sectors;
 120     int l2_bits;
 121     int l2_size;
 122     int l1_size;
 123     int l1_vm_state_index;
 124     int csize_shift;
 125     int csize_mask;
 126     uint64_t cluster_offset_mask;
 127     uint64_t l1_table_offset;
 128     uint64_t *l1_table;
 129     uint64_t *l2_cache;
 130     uint64_t l2_cache_offsets[L2_CACHE_SIZE];
 131     uint32_t l2_cache_counts[L2_CACHE_SIZE];
 132     uint8_t *cluster_cache;
 133     uint8_t *cluster_data;
 134     uint64_t cluster_cache_offset;
 135
 136     uint64_t *refcount_table;
 137     uint64_t refcount_table_offset;
 138     uint32_t refcount_table_size;
 139     uint64_t refcount_block_cache_offset;
 140     uint16_t *refcount_block_cache;
 141     int64_t free_cluster_index;
 142     int64_t free_byte_offset;
 143
 144     uint32_t crypt_method; /* current crypt method, 0 if no key yet */
 145     uint32_t crypt_method_header;
 146     AES_KEY aes_encrypt_key;
 147     AES_KEY aes_decrypt_key;
 148     uint64_t snapshots_offset;
 149     int snapshots_size;
 150     int nb_snapshots;
 151     QCowSnapshot *snapshots;
 152 } BDRVQcowState;
 153
 154 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset);
 155 static int qcow_read(BlockDriverState *bs, int64_t sector_num,
 156                      uint8_t *buf, int nb_sectors);
 157 static int qcow_read_snapshots(BlockDriverState *bs);
 158 static void qcow_free_snapshots(BlockDriverState *bs);
 159 static int refcount_init(BlockDriverState *bs);
 160 static void refcount_close(BlockDriverState *bs);
 161 static int get_refcount(BlockDriverState *bs, int64_t cluster_index);
 162 static int update_cluster_refcount(BlockDriverState *bs,
 163                                    int64_t cluster_index,
 164                                    int addend);
 165 static void update_refcount(BlockDriverState *bs,
 166                             int64_t offset, int64_t length,
 167                             int addend);
 168 static int64_t alloc_clusters(BlockDriverState *bs, int64_t size);
 169 static int64_t alloc_bytes(BlockDriverState *bs, int size);
 170 static void free_clusters(BlockDriverState *bs,
 171                           int64_t offset, int64_t size);
 172 #ifdef DEBUG_ALLOC
 173 static void check_refcounts(BlockDriverState *bs);
 174 #endif
 175
 176 static int qcow_probe(const uint8_t *buf, int buf_size, const char *filename)
 177 {
 178     const QCowHeader *cow_header = (const void *)buf;
 179
 180     if (buf_size >= sizeof(QCowHeader) &&
 181         be32_to_cpu(cow_header->magic) == QCOW_MAGIC &&
 182         be32_to_cpu(cow_header->version) == QCOW_VERSION)
 183         return 100;
 184     else
 185         return 0;
 186 }
 187
 188 static int qcow_open(BlockDriverState *bs, const char *filename, int flags)
 189 {
 190     BDRVQcowState *s = bs->opaque;
 191     int len, i, shift, ret;
 192     QCowHeader header;
 193
 194     ret = bdrv_file_open(&s->hd, filename, flags);
 195     if (ret < 0)
 196         return ret;
 197     if (bdrv_pread(s->hd, 0, &header, sizeof(header)) != sizeof(header))
 198         goto fail;
 199     be32_to_cpus(&header.magic);
 200     be32_to_cpus(&header.version);
 201     be64_to_cpus(&header.backing_file_offset);
 202     be32_to_cpus(&header.backing_file_size);
 203     be64_to_cpus(&header.size);
 204     be32_to_cpus(&header.cluster_bits);
 205     be32_to_cpus(&header.crypt_method);
 206     be64_to_cpus(&header.l1_table_offset);
 207     be32_to_cpus(&header.l1_size);
 208     be64_to_cpus(&header.refcount_table_offset);
 209     be32_to_cpus(&header.refcount_table_clusters);
 210     be64_to_cpus(&header.snapshots_offset);
 211     be32_to_cpus(&header.nb_snapshots);
 212
 213     if (header.magic != QCOW_MAGIC || header.version != QCOW_VERSION)
 214         goto fail;
 215     if (header.size <= 1 ||
 216         header.cluster_bits < 9 ||
 217         header.cluster_bits > 16)
 218         goto fail;
 219     if (header.crypt_method > QCOW_CRYPT_AES)
 220         goto fail;
 221     s->crypt_method_header = header.crypt_method;
 222     if (s->crypt_method_header)
 223         bs->encrypted = 1;
 224     s->cluster_bits = header.cluster_bits;
 225     s->cluster_size = 1 << s->cluster_bits;
 226     s->cluster_sectors = 1 << (s->cluster_bits - 9);
 227     s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */
 228     s->l2_size = 1 << s->l2_bits;
 229     bs->total_sectors = header.size / 512;
 230     s->csize_shift = (62 - (s->cluster_bits - 8));
 231     s->csize_mask = (1 << (s->cluster_bits - 8)) - 1;
 232     s->cluster_offset_mask = (1LL << s->csize_shift) - 1;
 233     s->refcount_table_offset = header.refcount_table_offset;
 234     s->refcount_table_size =
 235         header.refcount_table_clusters << (s->cluster_bits - 3);
 236
 237     s->snapshots_offset = header.snapshots_offset;
 238     s->nb_snapshots = header.nb_snapshots;
 239
 240     /* read the level 1 table */
 241     s->l1_size = header.l1_size;
 242     shift = s->cluster_bits + s->l2_bits;
 243     s->l1_vm_state_index = (header.size + (1LL << shift) - 1) >> shift;
 244     /* the L1 table must contain at least enough entries to put
 245        header.size bytes */
 246     if (s->l1_size < s->l1_vm_state_index)
 247         goto fail;
 248     s->l1_table_offset = header.l1_table_offset;
 249     s->l1_table = qemu_malloc(s->l1_size * sizeof(uint64_t));
 250     if (!s->l1_table)
 251         goto fail;
 252     if (bdrv_pread(s->hd, s->l1_table_offset, s->l1_table, s->l1_size * sizeof(uint64_t)) !=
 253         s->l1_size * sizeof(uint64_t))
 254         goto fail;
 255     for(i = 0;i < s->l1_size; i++) {
 256         be64_to_cpus(&s->l1_table[i]);
 257     }
 258     /* alloc L2 cache */
 259     s->l2_cache = qemu_malloc(s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t));
 260     if (!s->l2_cache)
 261         goto fail;
 262     s->cluster_cache = qemu_malloc(s->cluster_size);
 263     if (!s->cluster_cache)
 264         goto fail;
 265     /* one more sector for decompressed data alignment */
 266     s->cluster_data = qemu_malloc(s->cluster_size + 512);
 267     if (!s->cluster_data)
 268         goto fail;
 269     s->cluster_cache_offset = -1;
 270
 271     if (refcount_init(bs) < 0)
 272         goto fail;
 273
 274     /* read the backing file name */
 275     if (header.backing_file_offset != 0) {
 276         len = header.backing_file_size;
 277         if (len > 1023)
 278             len = 1023;
 279         if (bdrv_pread(s->hd, header.backing_file_offset, bs->backing_file, len) != len)
 280             goto fail;
 281         bs->backing_file[len] = '\0';
 282     }
 283     if (qcow_read_snapshots(bs) < 0)
 284         goto fail;
 285
 286 #ifdef DEBUG_ALLOC
 287     check_refcounts(bs);
 288 #endif
 289     return 0;
 290
 291  fail:
 292     qcow_free_snapshots(bs);
 293     refcount_close(bs);
 294     qemu_free(s->l1_table);
 295     qemu_free(s->l2_cache);
 296     qemu_free(s->cluster_cache);
 297     qemu_free(s->cluster_data);
 298     bdrv_delete(s->hd);
 299     return -1;
 300 }
 301
 302 static int qcow_set_key(BlockDriverState *bs, const char *key)
 303 {
 304     BDRVQcowState *s = bs->opaque;
 305     uint8_t keybuf[16];
 306     int len, i;
 307
 308     memset(keybuf, 0, 16);
 309     len = strlen(key);
 310     if (len > 16)
 311         len = 16;
 312     /* XXX: we could compress the chars to 7 bits to increase
 313        entropy */
 314     for(i = 0;i < len;i++) {
 315         keybuf[i] = key[i];
 316     }
 317     s->crypt_method = s->crypt_method_header;
 318
 319     if (AES_set_encrypt_key(keybuf, 128, &s->aes_encrypt_key) != 0)
 320         return -1;
 321     if (AES_set_decrypt_key(keybuf, 128, &s->aes_decrypt_key) != 0)
 322         return -1;
 323 #if 0
 324     /* test */
 325     {
 326         uint8_t in[16];
 327         uint8_t out[16];
 328         uint8_t tmp[16];
 329         for(i=0;i<16;i++)
 330             in[i] = i;
 331         AES_encrypt(in, tmp, &s->aes_encrypt_key);
 332         AES_decrypt(tmp, out, &s->aes_decrypt_key);
 333         for(i = 0; i < 16; i++)
 334             printf(" %02x", tmp[i]);
 335         printf("\n");
 336         for(i = 0; i < 16; i++)
 337             printf(" %02x", out[i]);
 338         printf("\n");
 339     }
 340 #endif
 341     return 0;
 342 }
 343
 344 /* The crypt function is compatible with the linux cryptoloop
 345    algorithm for < 4 GB images. NOTE: out_buf == in_buf is
 346    supported */
 347 static void encrypt_sectors(BDRVQcowState *s, int64_t sector_num,
 348                             uint8_t *out_buf, const uint8_t *in_buf,
 349                             int nb_sectors, int enc,
 350                             const AES_KEY *key)
 351 {
 352     union {
 353         uint64_t ll[2];
 354         uint8_t b[16];
 355     } ivec;
 356     int i;
 357
 358     for(i = 0; i < nb_sectors; i++) {
 359         ivec.ll[0] = cpu_to_le64(sector_num);
 360         ivec.ll[1] = 0;
 361         AES_cbc_encrypt(in_buf, out_buf, 512, key,
 362                         ivec.b, enc);
 363         sector_num++;
 364         in_buf += 512;
 365         out_buf += 512;
 366     }
 367 }
 368
 369 static int copy_sectors(BlockDriverState *bs, uint64_t start_sect,
 370                         uint64_t cluster_offset, int n_start, int n_end)
 371 {
 372     BDRVQcowState *s = bs->opaque;
 373     int n, ret;
 374
 375     n = n_end - n_start;
 376     if (n <= 0)
 377         return 0;
 378     ret = qcow_read(bs, start_sect + n_start, s->cluster_data, n);
 379     if (ret < 0)
 380         return ret;
 381     if (s->crypt_method) {
 382         encrypt_sectors(s, start_sect + n_start,
 383                         s->cluster_data,
 384                         s->cluster_data, n, 1,
 385                         &s->aes_encrypt_key);
 386     }
 387     ret = bdrv_write(s->hd, (cluster_offset >> 9) + n_start,
 388                      s->cluster_data, n);
 389     if (ret < 0)
 390         return ret;
 391     return 0;
 392 }
 393
 394 static void l2_cache_reset(BlockDriverState *bs)
 395 {
 396     BDRVQcowState *s = bs->opaque;
 397
 398     memset(s->l2_cache, 0, s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t));
 399     memset(s->l2_cache_offsets, 0, L2_CACHE_SIZE * sizeof(uint64_t));
 400     memset(s->l2_cache_counts, 0, L2_CACHE_SIZE * sizeof(uint32_t));
 401 }
 402
 403 static inline int l2_cache_new_entry(BlockDriverState *bs)
 404 {
 405     BDRVQcowState *s = bs->opaque;
 406     uint32_t min_count;
 407     int min_index, i;
 408
 409     /* find a new entry in the least used one */
 410     min_index = 0;
 411     min_count = 0xffffffff;
 412     for(i = 0; i < L2_CACHE_SIZE; i++) {
 413         if (s->l2_cache_counts[i] < min_count) {
 414             min_count = s->l2_cache_counts[i];
 415             min_index = i;
 416         }
 417     }
 418     return min_index;
 419 }
 420
 421 static int64_t align_offset(int64_t offset, int n)
 422 {
 423     offset = (offset + n - 1) & ~(n - 1);
 424     return offset;
 425 }
 426
 427 static int grow_l1_table(BlockDriverState *bs, int min_size)
 428 {
 429     BDRVQcowState *s = bs->opaque;
 430     int new_l1_size, new_l1_size2, ret, i;
 431     uint64_t *new_l1_table;
 432     uint64_t new_l1_table_offset;
 433     uint64_t data64;
 434     uint32_t data32;
 435
 436     new_l1_size = s->l1_size;
 437     if (min_size <= new_l1_size)
 438         return 0;
 439     while (min_size > new_l1_size) {
 440         new_l1_size = (new_l1_size * 3 + 1) / 2;
 441     }
 442 #ifdef DEBUG_ALLOC2
 443     printf("grow l1_table from %d to %d\n", s->l1_size, new_l1_size);
 444 #endif
 445
 446     new_l1_size2 = sizeof(uint64_t) * new_l1_size;
 447     new_l1_table = qemu_mallocz(new_l1_size2);
 448     if (!new_l1_table)
 449         return -ENOMEM;
 450     memcpy(new_l1_table, s->l1_table, s->l1_size * sizeof(uint64_t));
 451
 452     /* write new table (align to cluster) */
 453     new_l1_table_offset = alloc_clusters(bs, new_l1_size2);
 454
 455     for(i = 0; i < s->l1_size; i++)
 456         new_l1_table[i] = cpu_to_be64(new_l1_table[i]);
 457     ret = bdrv_pwrite(s->hd, new_l1_table_offset, new_l1_table, new_l1_size2);
 458     if (ret != new_l1_size2)
 459         goto fail;
 460     for(i = 0; i < s->l1_size; i++)
 461         new_l1_table[i] = be64_to_cpu(new_l1_table[i]);
 462
 463     /* set new table */
 464     data64 = cpu_to_be64(new_l1_table_offset);
 465     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, l1_table_offset),
 466                     &data64, sizeof(data64)) != sizeof(data64))
 467         goto fail;
 468     data32 = cpu_to_be32(new_l1_size);
 469     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, l1_size),
 470                     &data32, sizeof(data32)) != sizeof(data32))
 471         goto fail;
 472     qemu_free(s->l1_table);
 473     free_clusters(bs, s->l1_table_offset, s->l1_size * sizeof(uint64_t));
 474     s->l1_table_offset = new_l1_table_offset;
 475     s->l1_table = new_l1_table;
 476     s->l1_size = new_l1_size;
 477     return 0;
 478  fail:
 479     qemu_free(s->l1_table);
 480     return -EIO;
 481 }
 482
 483 /*
 484  * seek_l2_table
 485  *
 486  * seek l2_offset in the l2_cache table
 487  * if not found, return NULL,
 488  * if found,
 489  *   increments the l2 cache hit count of the entry,
 490  *   if counter overflow, divide by two all counters
 491  *   return the pointer to the l2 cache entry
 492  *
 493  */
 494
 495 static uint64_t *seek_l2_table(BDRVQcowState *s, uint64_t l2_offset)
 496 {
 497     int i, j;
 498
 499     for(i = 0; i < L2_CACHE_SIZE; i++) {
 500         if (l2_offset == s->l2_cache_offsets[i]) {
 501             /* increment the hit count */
 502             if (++s->l2_cache_counts[i] == 0xffffffff) {
 503                 for(j = 0; j < L2_CACHE_SIZE; j++) {
 504                     s->l2_cache_counts[j] >>= 1;
 505                 }
 506             }
 507             return s->l2_cache + (i << s->l2_bits);
 508         }
 509     }
 510     return NULL;
 511 }
 512
 513 /*
 514  * l2_load
 515  *
 516  * Loads a L2 table into memory. If the table is in the cache, the cache
 517  * is used; otherwise the L2 table is loaded from the image file.
 518  *
 519  * Returns a pointer to the L2 table on success, or NULL if the read from
 520  * the image file failed.
 521  */
 522
 523 static uint64_t *l2_load(BlockDriverState *bs, uint64_t l2_offset)
 524 {
 525     BDRVQcowState *s = bs->opaque;
 526     int min_index;
 527     uint64_t *l2_table;
 528
 529     /* seek if the table for the given offset is in the cache */
 530
 531     l2_table = seek_l2_table(s, l2_offset);
 532     if (l2_table != NULL)
 533         return l2_table;
 534
 535     /* not found: load a new entry in the least used one */
 536
 537     min_index = l2_cache_new_entry(bs);
 538     l2_table = s->l2_cache + (min_index << s->l2_bits);
 539     if (bdrv_pread(s->hd, l2_offset, l2_table, s->l2_size * sizeof(uint64_t)) !=
 540         s->l2_size * sizeof(uint64_t))
 541         return NULL;
 542     s->l2_cache_offsets[min_index] = l2_offset;
 543     s->l2_cache_counts[min_index] = 1;
 544
 545     return l2_table;
 546 }
 547
 548 /*
 549  * l2_allocate
 550  *
 551  * Allocate a new l2 entry in the file. If l1_index points to an already
 552  * used entry in the L2 table (i.e. we are doing a copy on write for the L2
 553  * table) copy the contents of the old L2 table into the newly allocated one.
 554  * Otherwise the new table is initialized with zeros.
 555  *
 556  */
 557
 558 static uint64_t *l2_allocate(BlockDriverState *bs, int l1_index)
 559 {
 560     BDRVQcowState *s = bs->opaque;
 561     int min_index;
 562     uint64_t old_l2_offset, tmp;
 563     uint64_t *l2_table, l2_offset;
 564
 565     old_l2_offset = s->l1_table[l1_index];
 566
 567     /* allocate a new l2 entry */
 568
 569     l2_offset = alloc_clusters(bs, s->l2_size * sizeof(uint64_t));
 570
 571     /* update the L1 entry */
 572
 573     s->l1_table[l1_index] = l2_offset | QCOW_OFLAG_COPIED;
 574
 575     tmp = cpu_to_be64(l2_offset | QCOW_OFLAG_COPIED);
 576     if (bdrv_pwrite(s->hd, s->l1_table_offset + l1_index * sizeof(tmp),
 577                     &tmp, sizeof(tmp)) != sizeof(tmp))
 578         return NULL;
 579
 580     /* allocate a new entry in the l2 cache */
 581
 582     min_index = l2_cache_new_entry(bs);
 583     l2_table = s->l2_cache + (min_index << s->l2_bits);
 584
 585     if (old_l2_offset == 0) {
 586         /* if there was no old l2 table, clear the new table */
 587         memset(l2_table, 0, s->l2_size * sizeof(uint64_t));
 588     } else {
 589         /* if there was an old l2 table, read it from the disk */
 590         if (bdrv_pread(s->hd, old_l2_offset,
 591                        l2_table, s->l2_size * sizeof(uint64_t)) !=
 592             s->l2_size * sizeof(uint64_t))
 593             return NULL;
 594     }
 595     /* write the l2 table to the file */
 596     if (bdrv_pwrite(s->hd, l2_offset,
 597                     l2_table, s->l2_size * sizeof(uint64_t)) !=
 598         s->l2_size * sizeof(uint64_t))
 599         return NULL;
 600
 601     /* update the l2 cache entry */
 602
 603     s->l2_cache_offsets[min_index] = l2_offset;
 604     s->l2_cache_counts[min_index] = 1;
 605
 606     return l2_table;
 607 }
 608
 609 /*
 610  * get_cluster_offset
 611  *
 612  * For a given offset of the disk image, return cluster offset in
 613  * qcow2 file.
 614  *
 615  * Return 1, if the offset is found
 616  * Return 0, otherwise.
 617  *
 618  */
 619
 620 static uint64_t get_cluster_offset(BlockDriverState *bs, uint64_t offset)
 621 {
 622     BDRVQcowState *s = bs->opaque;
 623     int l1_index, l2_index;
 624     uint64_t l2_offset, *l2_table, cluster_offset;
 625
 626     /* seek the the l2 offset in the l1 table */
 627
 628     l1_index = offset >> (s->l2_bits + s->cluster_bits);
 629     if (l1_index >= s->l1_size)
 630         return 0;
 631
 632     l2_offset = s->l1_table[l1_index];
 633
 634     /* seek the l2 table of the given l2 offset */
 635
 636     if (!l2_offset)
 637         return 0;
 638
 639     /* load the l2 table in memory */
 640
 641     l2_offset &= ~QCOW_OFLAG_COPIED;
 642     l2_table = l2_load(bs, l2_offset);
 643     if (l2_table == NULL)
 644         return 0;
 645
 646     /* find the cluster offset for the given disk offset */
 647
 648     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 649     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 650
 651     return cluster_offset & ~QCOW_OFLAG_COPIED;
 652 }
 653
 654 /*
 655  * free_any_clusters
 656  *
 657  * free clusters according to its type: compressed or not
 658  *
 659  */
 660
 661 static void free_any_clusters(BlockDriverState *bs,
 662                               uint64_t cluster_offset)
 663 {
 664     BDRVQcowState *s = bs->opaque;
 665
 666     if (cluster_offset == 0)
 667         return;
 668
 669     /* free the cluster */
 670
 671     if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
 672         int nb_csectors;
 673         nb_csectors = ((cluster_offset >> s->csize_shift) &
 674                        s->csize_mask) + 1;
 675         free_clusters(bs, (cluster_offset & s->cluster_offset_mask) & ~511,
 676                       nb_csectors * 512);
 677         return;
 678     }
 679
 680     free_clusters(bs, cluster_offset, s->cluster_size);
 681 }
 682
 683 /*
 684  * get_cluster_table
 685  *
 686  * for a given disk offset, load (and allocate if needed)
 687  * the l2 table.
 688  *
 689  * the l2 table offset in the qcow2 file and the cluster index
 690  * in the l2 table are given to the caller.
 691  *
 692  */
 693
 694 static int get_cluster_table(BlockDriverState *bs, uint64_t offset,
 695                              uint64_t **new_l2_table,
 696                              uint64_t *new_l2_offset,
 697                              int *new_l2_index)
 698 {
 699     BDRVQcowState *s = bs->opaque;
 700     int l1_index, l2_index, ret;
 701     uint64_t l2_offset, *l2_table;
 702
 703     /* seek the the l2 offset in the l1 table */
 704
 705     l1_index = offset >> (s->l2_bits + s->cluster_bits);
 706     if (l1_index >= s->l1_size) {
 707         ret = grow_l1_table(bs, l1_index + 1);
 708         if (ret < 0)
 709             return 0;
 710     }
 711     l2_offset = s->l1_table[l1_index];
 712
 713     /* seek the l2 table of the given l2 offset */
 714
 715     if (l2_offset & QCOW_OFLAG_COPIED) {
 716         /* load the l2 table in memory */
 717         l2_offset &= ~QCOW_OFLAG_COPIED;
 718         l2_table = l2_load(bs, l2_offset);
 719         if (l2_table == NULL)
 720             return 0;
 721     } else {
 722         if (l2_offset)
 723             free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t));
 724         l2_table = l2_allocate(bs, l1_index);
 725         if (l2_table == NULL)
 726             return 0;
 727         l2_offset = s->l1_table[l1_index] & ~QCOW_OFLAG_COPIED;
 728     }
 729
 730     /* find the cluster offset for the given disk offset */
 731
 732     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 733
 734     *new_l2_table = l2_table;
 735     *new_l2_offset = l2_offset;
 736     *new_l2_index = l2_index;
 737
 738     return 1;
 739 }
 740
 741 /*
 742  * alloc_compressed_cluster_offset
 743  *
 744  * For a given offset of the disk image, return cluster offset in
 745  * qcow2 file.
 746  *
 747  * If the offset is not found, allocate a new compressed cluster.
 748  *
 749  * Return the cluster offset if successful,
 750  * Return 0, otherwise.
 751  *
 752  */
 753
 754 static uint64_t alloc_compressed_cluster_offset(BlockDriverState *bs,
 755                                                 uint64_t offset,
 756                                                 int compressed_size)
 757 {
 758     BDRVQcowState *s = bs->opaque;
 759     int l2_index, ret;
 760     uint64_t l2_offset, *l2_table, cluster_offset;
 761     int nb_csectors;
 762
 763     ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index);
 764     if (ret == 0)
 765         return 0;
 766
 767     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 768     if (cluster_offset & QCOW_OFLAG_COPIED)
 769         return cluster_offset & ~QCOW_OFLAG_COPIED;
 770
 771     free_any_clusters(bs, cluster_offset);
 772
 773     cluster_offset = alloc_bytes(bs, compressed_size);
 774     nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -
 775                   (cluster_offset >> 9);
 776
 777     cluster_offset |= QCOW_OFLAG_COMPRESSED |
 778                       ((uint64_t)nb_csectors << s->csize_shift);
 779
 780     /* update L2 table */
 781
 782     /* compressed clusters never have the copied flag */
 783
 784     l2_table[l2_index] = cpu_to_be64(cluster_offset);
 785     if (bdrv_pwrite(s->hd,
 786                     l2_offset + l2_index * sizeof(uint64_t),
 787                     l2_table + l2_index,
 788                     sizeof(uint64_t)) != sizeof(uint64_t))
 789         return 0;
 790
 791     return cluster_offset;
 792 }
 793
 794 /*
 795  * alloc_cluster_offset
 796  *
 797  * For a given offset of the disk image, return cluster offset in
 798  * qcow2 file.
 799  *
 800  * If the offset is not found, allocate a new cluster.
 801  *
 802  * Return the cluster offset if successful,
 803  * Return 0, otherwise.
 804  *
 805  */
 806
 807 static uint64_t alloc_cluster_offset(BlockDriverState *bs,
 808                                      uint64_t offset,
 809                                      int n_start, int n_end)
 810 {
 811     BDRVQcowState *s = bs->opaque;
 812     int l2_index, ret;
 813     uint64_t l2_offset, *l2_table, cluster_offset;
 814
 815     ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index);
 816     if (ret == 0)
 817         return 0;
 818
 819     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 820     if (cluster_offset & QCOW_OFLAG_COPIED)
 821         return cluster_offset & ~QCOW_OFLAG_COPIED;
 822
 823     free_any_clusters(bs, cluster_offset);
 824
 825     /* allocate a new cluster */
 826
 827     cluster_offset = alloc_clusters(bs, s->cluster_size);
 828
 829     /* we must initialize the cluster content which won't be
 830        written */
 831
 832     if ((n_end - n_start) < s->cluster_sectors) {
 833         uint64_t start_sect;
 834
 835         start_sect = (offset & ~(s->cluster_size - 1)) >> 9;
 836         ret = copy_sectors(bs, start_sect,
 837                            cluster_offset, 0, n_start);
 838         if (ret < 0)
 839             return 0;
 840         ret = copy_sectors(bs, start_sect,
 841                            cluster_offset, n_end, s->cluster_sectors);
 842         if (ret < 0)
 843             return 0;
 844     }
 845
 846     /* update L2 table */
 847
 848     l2_table[l2_index] = cpu_to_be64(cluster_offset | QCOW_OFLAG_COPIED);
 849     if (bdrv_pwrite(s->hd,
 850                     l2_offset + l2_index * sizeof(uint64_t),
 851                     l2_table + l2_index,
 852                     sizeof(uint64_t)) != sizeof(uint64_t))
 853         return 0;
 854
 855     return cluster_offset;
 856 }
 857
 858 static int qcow_is_allocated(BlockDriverState *bs, int64_t sector_num,
 859                              int nb_sectors, int *pnum)
 860 {
 861     BDRVQcowState *s = bs->opaque;
 862     int index_in_cluster, n;
 863     uint64_t cluster_offset;
 864
 865     cluster_offset = get_cluster_offset(bs, sector_num << 9);
 866     index_in_cluster = sector_num & (s->cluster_sectors - 1);
 867     n = s->cluster_sectors - index_in_cluster;
 868     if (n > nb_sectors)
 869         n = nb_sectors;
 870     *pnum = n;
 871     return (cluster_offset != 0);
 872 }
 873
 874 static int decompress_buffer(uint8_t *out_buf, int out_buf_size,
 875                              const uint8_t *buf, int buf_size)
 876 {
 877     z_stream strm1, *strm = &strm1;
 878     int ret, out_len;
 879
 880     memset(strm, 0, sizeof(*strm));
 881
 882     strm->next_in = (uint8_t *)buf;
 883     strm->avail_in = buf_size;
 884     strm->next_out = out_buf;
 885     strm->avail_out = out_buf_size;
 886
 887     ret = inflateInit2(strm, -12);
 888     if (ret != Z_OK)
 889         return -1;
 890     ret = inflate(strm, Z_FINISH);
 891     out_len = strm->next_out - out_buf;
 892     if ((ret != Z_STREAM_END && ret != Z_BUF_ERROR) ||
 893         out_len != out_buf_size) {
 894         inflateEnd(strm);
 895         return -1;
 896     }
 897     inflateEnd(strm);
 898     return 0;
 899 }
 900
 901 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset)
 902 {
 903     int ret, csize, nb_csectors, sector_offset;
 904     uint64_t coffset;
 905
 906     coffset = cluster_offset & s->cluster_offset_mask;
 907     if (s->cluster_cache_offset != coffset) {
 908         nb_csectors = ((cluster_offset >> s->csize_shift) & s->csize_mask) + 1;
 909         sector_offset = coffset & 511;
 910         csize = nb_csectors * 512 - sector_offset;
 911         ret = bdrv_read(s->hd, coffset >> 9, s->cluster_data, nb_csectors);
 912         if (ret < 0) {
 913             return -1;
 914         }
 915         if (decompress_buffer(s->cluster_cache, s->cluster_size,
 916                               s->cluster_data + sector_offset, csize) < 0) {
 917             return -1;
 918         }
 919         s->cluster_cache_offset = coffset;
 920     }
 921     return 0;
 922 }
 923
 924 /* handle reading after the end of the backing file */
 925 static int backing_read1(BlockDriverState *bs,
 926                          int64_t sector_num, uint8_t *buf, int nb_sectors)
 927 {
 928     int n1;
 929     if ((sector_num + nb_sectors) <= bs->total_sectors)
 930         return nb_sectors;
 931     if (sector_num >= bs->total_sectors)
 932         n1 = 0;
 933     else
 934         n1 = bs->total_sectors - sector_num;
 935     memset(buf + n1 * 512, 0, 512 * (nb_sectors - n1));
 936     return n1;
 937 }
 938
 939 static int qcow_read(BlockDriverState *bs, int64_t sector_num,
 940                      uint8_t *buf, int nb_sectors)
 941 {
 942     BDRVQcowState *s = bs->opaque;
 943     int ret, index_in_cluster, n, n1;
 944     uint64_t cluster_offset;
 945
 946     while (nb_sectors > 0) {
 947         cluster_offset = get_cluster_offset(bs, sector_num << 9);
 948         index_in_cluster = sector_num & (s->cluster_sectors - 1);
 949         n = s->cluster_sectors - index_in_cluster;
 950         if (n > nb_sectors)
 951             n = nb_sectors;
 952         if (!cluster_offset) {
 953             if (bs->backing_hd) {
 954                 /* read from the base image */
 955                 n1 = backing_read1(bs->backing_hd, sector_num, buf, n);
 956                 if (n1 > 0) {
 957                     ret = bdrv_read(bs->backing_hd, sector_num, buf, n1);
 958                     if (ret < 0)
 959                         return -1;
 960                 }
 961             } else {
 962                 memset(buf, 0, 512 * n);
 963             }
 964         } else if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
 965             if (decompress_cluster(s, cluster_offset) < 0)
 966                 return -1;
 967             memcpy(buf, s->cluster_cache + index_in_cluster * 512, 512 * n);
 968         } else {
 969             ret = bdrv_pread(s->hd, cluster_offset + index_in_cluster * 512, buf, n * 512);
 970             if (ret != n * 512)
 971                 return -1;
 972             if (s->crypt_method) {
 973                 encrypt_sectors(s, sector_num, buf, buf, n, 0,
 974                                 &s->aes_decrypt_key);
 975             }
 976         }
 977         nb_sectors -= n;
 978         sector_num += n;
 979         buf += n * 512;
 980     }
 981     return 0;
 982 }
 983
 984 static int qcow_write(BlockDriverState *bs, int64_t sector_num,
 985                      const uint8_t *buf, int nb_sectors)
 986 {
 987     BDRVQcowState *s = bs->opaque;
 988     int ret, index_in_cluster, n;
 989     uint64_t cluster_offset;
 990
 991     while (nb_sectors > 0) {
 992         index_in_cluster = sector_num & (s->cluster_sectors - 1);
 993         n = s->cluster_sectors - index_in_cluster;
 994         if (n > nb_sectors)
 995             n = nb_sectors;
 996         cluster_offset = alloc_cluster_offset(bs, sector_num << 9,
 997                                               index_in_cluster,
 998                                               index_in_cluster + n);
 999         if (!cluster_offset)
1000             return -1;
1001         if (s->crypt_method) {
1002             encrypt_sectors(s, sector_num, s->cluster_data, buf, n, 1,
1003                             &s->aes_encrypt_key);
1004             ret = bdrv_pwrite(s->hd, cluster_offset + index_in_cluster * 512,
1005                               s->cluster_data, n * 512);
1006         } else {
1007             ret = bdrv_pwrite(s->hd, cluster_offset + index_in_cluster * 512, buf, n * 512);
1008         }
1009         if (ret != n * 512)
1010             return -1;
1011         nb_sectors -= n;
1012         sector_num += n;
1013         buf += n * 512;
1014     }
1015     s->cluster_cache_offset = -1; /* disable compressed cache */
1016     return 0;
1017 }
1018
1019 typedef struct QCowAIOCB {
1020     BlockDriverAIOCB common;
1021     int64_t sector_num;
1022     uint8_t *buf;
1023     int nb_sectors;
1024     int n;
1025     uint64_t cluster_offset;
1026     uint8_t *cluster_data;
1027     BlockDriverAIOCB *hd_aiocb;
1028 } QCowAIOCB;
1029
1030 static void qcow_aio_read_cb(void *opaque, int ret)
1031 {
1032     QCowAIOCB *acb = opaque;
1033     BlockDriverState *bs = acb->common.bs;
1034     BDRVQcowState *s = bs->opaque;
1035     int index_in_cluster, n1;
1036
1037     acb->hd_aiocb = NULL;
1038     if (ret < 0) {
1039     fail:
1040         acb->common.cb(acb->common.opaque, ret);
1041         qemu_aio_release(acb);
1042         return;
1043     }
1044
1045  redo:
1046     /* post process the read buffer */
1047     if (!acb->cluster_offset) {
1048         /* nothing to do */
1049     } else if (acb->cluster_offset & QCOW_OFLAG_COMPRESSED) {
1050         /* nothing to do */
1051     } else {
1052         if (s->crypt_method) {
1053             encrypt_sectors(s, acb->sector_num, acb->buf, acb->buf,
1054                             acb->n, 0,
1055                             &s->aes_decrypt_key);
1056         }
1057     }
1058
1059     acb->nb_sectors -= acb->n;
1060     acb->sector_num += acb->n;
1061     acb->buf += acb->n * 512;
1062
1063     if (acb->nb_sectors == 0) {
1064         /* request completed */
1065         acb->common.cb(acb->common.opaque, 0);
1066         qemu_aio_release(acb);
1067         return;
1068     }
1069
1070     /* prepare next AIO request */
1071     acb->cluster_offset = get_cluster_offset(bs, acb->sector_num << 9);
1072     index_in_cluster = acb->sector_num & (s->cluster_sectors - 1);
1073     acb->n = s->cluster_sectors - index_in_cluster;
1074     if (acb->n > acb->nb_sectors)
1075         acb->n = acb->nb_sectors;
1076
1077     if (!acb->cluster_offset) {
1078         if (bs->backing_hd) {
1079             /* read from the base image */
1080             n1 = backing_read1(bs->backing_hd, acb->sector_num,
1081                                acb->buf, acb->n);
1082             if (n1 > 0) {
1083                 acb->hd_aiocb = bdrv_aio_read(bs->backing_hd, acb->sector_num,
1084                                     acb->buf, acb->n, qcow_aio_read_cb, acb);
1085                 if (acb->hd_aiocb == NULL)
1086                     goto fail;
1087             } else {
1088                 goto redo;
1089             }
1090         } else {
1091             /* Note: in this case, no need to wait */
1092             memset(acb->buf, 0, 512 * acb->n);
1093             goto redo;
1094         }
1095     } else if (acb->cluster_offset & QCOW_OFLAG_COMPRESSED) {
1096         /* add AIO support for compressed blocks ? */
1097         if (decompress_cluster(s, acb->cluster_offset) < 0)
1098             goto fail;
1099         memcpy(acb->buf,
1100                s->cluster_cache + index_in_cluster * 512, 512 * acb->n);
1101         goto redo;
1102     } else {
1103         if ((acb->cluster_offset & 511) != 0) {
1104             ret = -EIO;
1105             goto fail;
1106         }
1107         acb->hd_aiocb = bdrv_aio_read(s->hd,
1108                             (acb->cluster_offset >> 9) + index_in_cluster,
1109                             acb->buf, acb->n, qcow_aio_read_cb, acb);
1110         if (acb->hd_aiocb == NULL)
1111             goto fail;
1112     }
1113 }
1114
1115 static QCowAIOCB *qcow_aio_setup(BlockDriverState *bs,
1116         int64_t sector_num, uint8_t *buf, int nb_sectors,
1117         BlockDriverCompletionFunc *cb, void *opaque)
1118 {
1119     QCowAIOCB *acb;
1120
1121     acb = qemu_aio_get(bs, cb, opaque);
1122     if (!acb)
1123         return NULL;
1124     acb->hd_aiocb = NULL;
1125     acb->sector_num = sector_num;
1126     acb->buf = buf;
1127     acb->nb_sectors = nb_sectors;
1128     acb->n = 0;
1129     acb->cluster_offset = 0;
1130     return acb;
1131 }
1132
1133 static BlockDriverAIOCB *qcow_aio_read(BlockDriverState *bs,
1134         int64_t sector_num, uint8_t *buf, int nb_sectors,
1135         BlockDriverCompletionFunc *cb, void *opaque)
1136 {
1137     QCowAIOCB *acb;
1138
1139     acb = qcow_aio_setup(bs, sector_num, buf, nb_sectors, cb, opaque);
1140     if (!acb)
1141         return NULL;
1142
1143     qcow_aio_read_cb(acb, 0);
1144     return &acb->common;
1145 }
1146
1147 static void qcow_aio_write_cb(void *opaque, int ret)
1148 {
1149     QCowAIOCB *acb = opaque;
1150     BlockDriverState *bs = acb->common.bs;
1151     BDRVQcowState *s = bs->opaque;
1152     int index_in_cluster;
1153     uint64_t cluster_offset;
1154     const uint8_t *src_buf;
1155
1156     acb->hd_aiocb = NULL;
1157
1158     if (ret < 0) {
1159     fail:
1160         acb->common.cb(acb->common.opaque, ret);
1161         qemu_aio_release(acb);
1162         return;
1163     }
1164
1165     acb->nb_sectors -= acb->n;
1166     acb->sector_num += acb->n;
1167     acb->buf += acb->n * 512;
1168
1169     if (acb->nb_sectors == 0) {
1170         /* request completed */
1171         acb->common.cb(acb->common.opaque, 0);
1172         qemu_aio_release(acb);
1173         return;
1174     }
1175
1176     index_in_cluster = acb->sector_num & (s->cluster_sectors - 1);
1177     acb->n = s->cluster_sectors - index_in_cluster;
1178     if (acb->n > acb->nb_sectors)
1179         acb->n = acb->nb_sectors;
1180     cluster_offset = alloc_cluster_offset(bs, acb->sector_num << 9,
1181                                           index_in_cluster,
1182                                           index_in_cluster + acb->n);
1183     if (!cluster_offset || (cluster_offset & 511) != 0) {
1184         ret = -EIO;
1185         goto fail;
1186     }
1187     if (s->crypt_method) {
1188         if (!acb->cluster_data) {
1189             acb->cluster_data = qemu_mallocz(s->cluster_size);
1190             if (!acb->cluster_data) {
1191                 ret = -ENOMEM;
1192                 goto fail;
1193             }
1194         }
1195         encrypt_sectors(s, acb->sector_num, acb->cluster_data, acb->buf,
1196                         acb->n, 1, &s->aes_encrypt_key);
1197         src_buf = acb->cluster_data;
1198     } else {
1199         src_buf = acb->buf;
1200     }
1201     acb->hd_aiocb = bdrv_aio_write(s->hd,
1202                                    (cluster_offset >> 9) + index_in_cluster,
1203                                    src_buf, acb->n,
1204                                    qcow_aio_write_cb, acb);
1205     if (acb->hd_aiocb == NULL)
1206         goto fail;
1207 }
1208
1209 static BlockDriverAIOCB *qcow_aio_write(BlockDriverState *bs,
1210         int64_t sector_num, const uint8_t *buf, int nb_sectors,
1211         BlockDriverCompletionFunc *cb, void *opaque)
1212 {
1213     BDRVQcowState *s = bs->opaque;
1214     QCowAIOCB *acb;
1215
1216     s->cluster_cache_offset = -1; /* disable compressed cache */
1217
1218     acb = qcow_aio_setup(bs, sector_num, (uint8_t*)buf, nb_sectors, cb, opaque);
1219     if (!acb)
1220         return NULL;
1221
1222     qcow_aio_write_cb(acb, 0);
1223     return &acb->common;
1224 }
1225
1226 static void qcow_aio_cancel(BlockDriverAIOCB *blockacb)
1227 {
1228     QCowAIOCB *acb = (QCowAIOCB *)blockacb;
1229     if (acb->hd_aiocb)
1230         bdrv_aio_cancel(acb->hd_aiocb);
1231     qemu_aio_release(acb);
1232 }
1233
1234 static void qcow_close(BlockDriverState *bs)
1235 {
1236     BDRVQcowState *s = bs->opaque;
1237     qemu_free(s->l1_table);
1238     qemu_free(s->l2_cache);
1239     qemu_free(s->cluster_cache);
1240     qemu_free(s->cluster_data);
1241     refcount_close(bs);
1242     bdrv_delete(s->hd);
1243 }
1244
1245 /* XXX: use std qcow open function ? */
1246 typedef struct QCowCreateState {
1247     int cluster_size;
1248     int cluster_bits;
1249     uint16_t *refcount_block;
1250     uint64_t *refcount_table;
1251     int64_t l1_table_offset;
1252     int64_t refcount_table_offset;
1253     int64_t refcount_block_offset;
1254 } QCowCreateState;
1255
1256 static void create_refcount_update(QCowCreateState *s,
1257                                    int64_t offset, int64_t size)
1258 {
1259     int refcount;
1260     int64_t start, last, cluster_offset;
1261     uint16_t *p;
1262
1263     start = offset & ~(s->cluster_size - 1);
1264     last = (offset + size - 1)  & ~(s->cluster_size - 1);
1265     for(cluster_offset = start; cluster_offset <= last;
1266         cluster_offset += s->cluster_size) {
1267         p = &s->refcount_block[cluster_offset >> s->cluster_bits];
1268         refcount = be16_to_cpu(*p);
1269         refcount++;
1270         *p = cpu_to_be16(refcount);
1271     }
1272 }
1273
1274 static int qcow_create(const char *filename, int64_t total_size,
1275                       const char *backing_file, int flags)
1276 {
1277     int fd, header_size, backing_filename_len, l1_size, i, shift, l2_bits;
1278     QCowHeader header;
1279     uint64_t tmp, offset;
1280     QCowCreateState s1, *s = &s1;
1281
1282     memset(s, 0, sizeof(*s));
1283
1284     fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0644);
1285     if (fd < 0)
1286         return -1;
1287     memset(&header, 0, sizeof(header));
1288     header.magic = cpu_to_be32(QCOW_MAGIC);
1289     header.version = cpu_to_be32(QCOW_VERSION);
1290     header.size = cpu_to_be64(total_size * 512);
1291     header_size = sizeof(header);
1292     backing_filename_len = 0;
1293     if (backing_file) {
1294         header.backing_file_offset = cpu_to_be64(header_size);
1295         backing_filename_len = strlen(backing_file);
1296         header.backing_file_size = cpu_to_be32(backing_filename_len);
1297         header_size += backing_filename_len;
1298     }
1299     s->cluster_bits = 12;  /* 4 KB clusters */
1300     s->cluster_size = 1 << s->cluster_bits;
1301     header.cluster_bits = cpu_to_be32(s->cluster_bits);
1302     header_size = (header_size + 7) & ~7;
1303     if (flags & BLOCK_FLAG_ENCRYPT) {
1304         header.crypt_method = cpu_to_be32(QCOW_CRYPT_AES);
1305     } else {
1306         header.crypt_method = cpu_to_be32(QCOW_CRYPT_NONE);
1307     }
1308     l2_bits = s->cluster_bits - 3;
1309     shift = s->cluster_bits + l2_bits;
1310     l1_size = (((total_size * 512) + (1LL << shift) - 1) >> shift);
1311     offset = align_offset(header_size, s->cluster_size);
1312     s->l1_table_offset = offset;
1313     header.l1_table_offset = cpu_to_be64(s->l1_table_offset);
1314     header.l1_size = cpu_to_be32(l1_size);
1315     offset += align_offset(l1_size * sizeof(uint64_t), s->cluster_size);
1316
1317     s->refcount_table = qemu_mallocz(s->cluster_size);
1318     if (!s->refcount_table)
1319         goto fail;
1320     s->refcount_block = qemu_mallocz(s->cluster_size);
1321     if (!s->refcount_block)
1322         goto fail;
1323
1324     s->refcount_table_offset = offset;
1325     header.refcount_table_offset = cpu_to_be64(offset);
1326     header.refcount_table_clusters = cpu_to_be32(1);
1327     offset += s->cluster_size;
1328
1329     s->refcount_table[0] = cpu_to_be64(offset);
1330     s->refcount_block_offset = offset;
1331     offset += s->cluster_size;
1332
1333     /* update refcounts */
1334     create_refcount_update(s, 0, header_size);
1335     create_refcount_update(s, s->l1_table_offset, l1_size * sizeof(uint64_t));
1336     create_refcount_update(s, s->refcount_table_offset, s->cluster_size);
1337     create_refcount_update(s, s->refcount_block_offset, s->cluster_size);
1338
1339     /* write all the data */
1340     write(fd, &header, sizeof(header));
1341     if (backing_file) {
1342         write(fd, backing_file, backing_filename_len);
1343     }
1344     lseek(fd, s->l1_table_offset, SEEK_SET);
1345     tmp = 0;
1346     for(i = 0;i < l1_size; i++) {
1347         write(fd, &tmp, sizeof(tmp));
1348     }
1349     lseek(fd, s->refcount_table_offset, SEEK_SET);
1350     write(fd, s->refcount_table, s->cluster_size);
1351
1352     lseek(fd, s->refcount_block_offset, SEEK_SET);
1353     write(fd, s->refcount_block, s->cluster_size);
1354
1355     qemu_free(s->refcount_table);
1356     qemu_free(s->refcount_block);
1357     close(fd);
1358     return 0;
1359  fail:
1360     qemu_free(s->refcount_table);
1361     qemu_free(s->refcount_block);
1362     close(fd);
1363     return -ENOMEM;
1364 }
1365
1366 static int qcow_make_empty(BlockDriverState *bs)
1367 {
1368 #if 0
1369     /* XXX: not correct */
1370     BDRVQcowState *s = bs->opaque;
1371     uint32_t l1_length = s->l1_size * sizeof(uint64_t);
1372     int ret;
1373
1374     memset(s->l1_table, 0, l1_length);
1375     if (bdrv_pwrite(s->hd, s->l1_table_offset, s->l1_table, l1_length) < 0)
1376         return -1;
1377     ret = bdrv_truncate(s->hd, s->l1_table_offset + l1_length);
1378     if (ret < 0)
1379         return ret;
1380
1381     l2_cache_reset(bs);
1382 #endif
1383     return 0;
1384 }
1385
1386 /* XXX: put compressed sectors first, then all the cluster aligned
1387    tables to avoid losing bytes in alignment */
1388 static int qcow_write_compressed(BlockDriverState *bs, int64_t sector_num,
1389                                  const uint8_t *buf, int nb_sectors)
1390 {
1391     BDRVQcowState *s = bs->opaque;
1392     z_stream strm;
1393     int ret, out_len;
1394     uint8_t *out_buf;
1395     uint64_t cluster_offset;
1396
1397     if (nb_sectors == 0) {
1398         /* align end of file to a sector boundary to ease reading with
1399            sector based I/Os */
1400         cluster_offset = bdrv_getlength(s->hd);
1401         cluster_offset = (cluster_offset + 511) & ~511;
1402         bdrv_truncate(s->hd, cluster_offset);
1403         return 0;
1404     }
1405
1406     if (nb_sectors != s->cluster_sectors)
1407         return -EINVAL;
1408
1409     out_buf = qemu_malloc(s->cluster_size + (s->cluster_size / 1000) + 128);
1410     if (!out_buf)
1411         return -ENOMEM;
1412
1413     /* best compression, small window, no zlib header */
1414     memset(&strm, 0, sizeof(strm));
1415     ret = deflateInit2(&strm, Z_DEFAULT_COMPRESSION,
1416                        Z_DEFLATED, -12,
1417                        9, Z_DEFAULT_STRATEGY);
1418     if (ret != 0) {
1419         qemu_free(out_buf);
1420         return -1;
1421     }
1422
1423     strm.avail_in = s->cluster_size;
1424     strm.next_in = (uint8_t *)buf;
1425     strm.avail_out = s->cluster_size;
1426     strm.next_out = out_buf;
1427
1428     ret = deflate(&strm, Z_FINISH);
1429     if (ret != Z_STREAM_END && ret != Z_OK) {
1430         qemu_free(out_buf);
1431         deflateEnd(&strm);
1432         return -1;
1433     }
1434     out_len = strm.next_out - out_buf;
1435
1436     deflateEnd(&strm);
1437
1438     if (ret != Z_STREAM_END || out_len >= s->cluster_size) {
1439         /* could not compress: write normal cluster */
1440         qcow_write(bs, sector_num, buf, s->cluster_sectors);
1441     } else {
1442         cluster_offset = alloc_compressed_cluster_offset(bs, sector_num << 9,
1443                                               out_len);
1444         if (!cluster_offset)
1445             return -1;
1446         cluster_offset &= s->cluster_offset_mask;
1447         if (bdrv_pwrite(s->hd, cluster_offset, out_buf, out_len) != out_len) {
1448             qemu_free(out_buf);
1449             return -1;
1450         }
1451     }
1452
1453     qemu_free(out_buf);
1454     return 0;
1455 }
1456
1457 static void qcow_flush(BlockDriverState *bs)
1458 {
1459     BDRVQcowState *s = bs->opaque;
1460     bdrv_flush(s->hd);
1461 }
1462
1463 static int qcow_get_info(BlockDriverState *bs, BlockDriverInfo *bdi)
1464 {
1465     BDRVQcowState *s = bs->opaque;
1466     bdi->cluster_size = s->cluster_size;
1467     bdi->vm_state_offset = (int64_t)s->l1_vm_state_index <<
1468         (s->cluster_bits + s->l2_bits);
1469     return 0;
1470 }
1471
1472 /*********************************************************/
1473 /* snapshot support */
1474
1475 /* update the refcounts of snapshots and the copied flag */
1476 static int update_snapshot_refcount(BlockDriverState *bs,
1477                                     int64_t l1_table_offset,
1478                                     int l1_size,
1479                                     int addend)
1480 {
1481     BDRVQcowState *s = bs->opaque;
1482     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
1483     int64_t old_offset, old_l2_offset;
1484     int l2_size, i, j, l1_modified, l2_modified, nb_csectors, refcount;
1485
1486     l2_cache_reset(bs);
1487
1488     l2_table = NULL;
1489     l1_table = NULL;
1490     l1_size2 = l1_size * sizeof(uint64_t);
1491     l1_allocated = 0;
1492     if (l1_table_offset != s->l1_table_offset) {
1493         l1_table = qemu_malloc(l1_size2);
1494         if (!l1_table)
1495             goto fail;
1496         l1_allocated = 1;
1497         if (bdrv_pread(s->hd, l1_table_offset,
1498                        l1_table, l1_size2) != l1_size2)
1499             goto fail;
1500         for(i = 0;i < l1_size; i++)
1501             be64_to_cpus(&l1_table[i]);
1502     } else {
1503         assert(l1_size == s->l1_size);
1504         l1_table = s->l1_table;
1505         l1_allocated = 0;
1506     }
1507
1508     l2_size = s->l2_size * sizeof(uint64_t);
1509     l2_table = qemu_malloc(l2_size);
1510     if (!l2_table)
1511         goto fail;
1512     l1_modified = 0;
1513     for(i = 0; i < l1_size; i++) {
1514         l2_offset = l1_table[i];
1515         if (l2_offset) {
1516             old_l2_offset = l2_offset;
1517             l2_offset &= ~QCOW_OFLAG_COPIED;
1518             l2_modified = 0;
1519             if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
1520                 goto fail;
1521             for(j = 0; j < s->l2_size; j++) {
1522                 offset = be64_to_cpu(l2_table[j]);
1523                 if (offset != 0) {
1524                     old_offset = offset;
1525                     offset &= ~QCOW_OFLAG_COPIED;
1526                     if (offset & QCOW_OFLAG_COMPRESSED) {
1527                         nb_csectors = ((offset >> s->csize_shift) &
1528                                        s->csize_mask) + 1;
1529                         if (addend != 0)
1530                             update_refcount(bs, (offset & s->cluster_offset_mask) & ~511,
1531                                             nb_csectors * 512, addend);
1532                         /* compressed clusters are never modified */
1533                         refcount = 2;
1534                     } else {
1535                         if (addend != 0) {
1536                             refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
1537                         } else {
1538                             refcount = get_refcount(bs, offset >> s->cluster_bits);
1539                         }
1540                     }
1541
1542                     if (refcount == 1) {
1543                         offset |= QCOW_OFLAG_COPIED;
1544                     }
1545                     if (offset != old_offset) {
1546                         l2_table[j] = cpu_to_be64(offset);
1547                         l2_modified = 1;
1548                     }
1549                 }
1550             }
1551             if (l2_modified) {
1552                 if (bdrv_pwrite(s->hd,
1553                                 l2_offset, l2_table, l2_size) != l2_size)
1554                     goto fail;
1555             }
1556
1557             if (addend != 0) {
1558                 refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
1559             } else {
1560                 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
1561             }
1562             if (refcount == 1) {
1563                 l2_offset |= QCOW_OFLAG_COPIED;
1564             }
1565             if (l2_offset != old_l2_offset) {
1566                 l1_table[i] = l2_offset;
1567                 l1_modified = 1;
1568             }
1569         }
1570     }
1571     if (l1_modified) {
1572         for(i = 0; i < l1_size; i++)
1573             cpu_to_be64s(&l1_table[i]);
1574         if (bdrv_pwrite(s->hd, l1_table_offset, l1_table,
1575                         l1_size2) != l1_size2)
1576             goto fail;
1577         for(i = 0; i < l1_size; i++)
1578             be64_to_cpus(&l1_table[i]);
1579     }
1580     if (l1_allocated)
1581         qemu_free(l1_table);
1582     qemu_free(l2_table);
1583     return 0;
1584  fail:
1585     if (l1_allocated)
1586         qemu_free(l1_table);
1587     qemu_free(l2_table);
1588     return -EIO;
1589 }
1590
1591 static void qcow_free_snapshots(BlockDriverState *bs)
1592 {
1593     BDRVQcowState *s = bs->opaque;
1594     int i;
1595
1596     for(i = 0; i < s->nb_snapshots; i++) {
1597         qemu_free(s->snapshots[i].name);
1598         qemu_free(s->snapshots[i].id_str);
1599     }
1600     qemu_free(s->snapshots);
1601     s->snapshots = NULL;
1602     s->nb_snapshots = 0;
1603 }
1604
1605 static int qcow_read_snapshots(BlockDriverState *bs)
1606 {
1607     BDRVQcowState *s = bs->opaque;
1608     QCowSnapshotHeader h;
1609     QCowSnapshot *sn;
1610     int i, id_str_size, name_size;
1611     int64_t offset;
1612     uint32_t extra_data_size;
1613
1614     offset = s->snapshots_offset;
1615     s->snapshots = qemu_mallocz(s->nb_snapshots * sizeof(QCowSnapshot));
1616     if (!s->snapshots)
1617         goto fail;
1618     for(i = 0; i < s->nb_snapshots; i++) {
1619         offset = align_offset(offset, 8);
1620         if (bdrv_pread(s->hd, offset, &h, sizeof(h)) != sizeof(h))
1621             goto fail;
1622         offset += sizeof(h);
1623         sn = s->snapshots + i;
1624         sn->l1_table_offset = be64_to_cpu(h.l1_table_offset);
1625         sn->l1_size = be32_to_cpu(h.l1_size);
1626         sn->vm_state_size = be32_to_cpu(h.vm_state_size);
1627         sn->date_sec = be32_to_cpu(h.date_sec);
1628         sn->date_nsec = be32_to_cpu(h.date_nsec);
1629         sn->vm_clock_nsec = be64_to_cpu(h.vm_clock_nsec);
1630         extra_data_size = be32_to_cpu(h.extra_data_size);
1631
1632         id_str_size = be16_to_cpu(h.id_str_size);
1633         name_size = be16_to_cpu(h.name_size);
1634
1635         offset += extra_data_size;
1636
1637         sn->id_str = qemu_malloc(id_str_size + 1);
1638         if (!sn->id_str)
1639             goto fail;
1640         if (bdrv_pread(s->hd, offset, sn->id_str, id_str_size) != id_str_size)
1641             goto fail;
1642         offset += id_str_size;
1643         sn->id_str[id_str_size] = '\0';
1644
1645         sn->name = qemu_malloc(name_size + 1);
1646         if (!sn->name)
1647             goto fail;
1648         if (bdrv_pread(s->hd, offset, sn->name, name_size) != name_size)
1649             goto fail;
1650         offset += name_size;
1651         sn->name[name_size] = '\0';
1652     }
1653     s->snapshots_size = offset - s->snapshots_offset;
1654     return 0;
1655  fail:
1656     qcow_free_snapshots(bs);
1657     return -1;
1658 }
1659
1660 /* add at the end of the file a new list of snapshots */
1661 static int qcow_write_snapshots(BlockDriverState *bs)
1662 {
1663     BDRVQcowState *s = bs->opaque;
1664     QCowSnapshot *sn;
1665     QCowSnapshotHeader h;
1666     int i, name_size, id_str_size, snapshots_size;
1667     uint64_t data64;
1668     uint32_t data32;
1669     int64_t offset, snapshots_offset;
1670
1671     /* compute the size of the snapshots */
1672     offset = 0;
1673     for(i = 0; i < s->nb_snapshots; i++) {
1674         sn = s->snapshots + i;
1675         offset = align_offset(offset, 8);
1676         offset += sizeof(h);
1677         offset += strlen(sn->id_str);
1678         offset += strlen(sn->name);
1679     }
1680     snapshots_size = offset;
1681
1682     snapshots_offset = alloc_clusters(bs, snapshots_size);
1683     offset = snapshots_offset;
1684
1685     for(i = 0; i < s->nb_snapshots; i++) {
1686         sn = s->snapshots + i;
1687         memset(&h, 0, sizeof(h));
1688         h.l1_table_offset = cpu_to_be64(sn->l1_table_offset);
1689         h.l1_size = cpu_to_be32(sn->l1_size);
1690         h.vm_state_size = cpu_to_be32(sn->vm_state_size);
1691         h.date_sec = cpu_to_be32(sn->date_sec);
1692         h.date_nsec = cpu_to_be32(sn->date_nsec);
1693         h.vm_clock_nsec = cpu_to_be64(sn->vm_clock_nsec);
1694
1695         id_str_size = strlen(sn->id_str);
1696         name_size = strlen(sn->name);
1697         h.id_str_size = cpu_to_be16(id_str_size);
1698         h.name_size = cpu_to_be16(name_size);
1699         offset = align_offset(offset, 8);
1700         if (bdrv_pwrite(s->hd, offset, &h, sizeof(h)) != sizeof(h))
1701             goto fail;
1702         offset += sizeof(h);
1703         if (bdrv_pwrite(s->hd, offset, sn->id_str, id_str_size) != id_str_size)
1704             goto fail;
1705         offset += id_str_size;
1706         if (bdrv_pwrite(s->hd, offset, sn->name, name_size) != name_size)
1707             goto fail;
1708         offset += name_size;
1709     }
1710
1711     /* update the various header fields */
1712     data64 = cpu_to_be64(snapshots_offset);
1713     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, snapshots_offset),
1714                     &data64, sizeof(data64)) != sizeof(data64))
1715         goto fail;
1716     data32 = cpu_to_be32(s->nb_snapshots);
1717     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, nb_snapshots),
1718                     &data32, sizeof(data32)) != sizeof(data32))
1719         goto fail;
1720
1721     /* free the old snapshot table */
1722     free_clusters(bs, s->snapshots_offset, s->snapshots_size);
1723     s->snapshots_offset = snapshots_offset;
1724     s->snapshots_size = snapshots_size;
1725     return 0;
1726  fail:
1727     return -1;
1728 }
1729
1730 static void find_new_snapshot_id(BlockDriverState *bs,
1731                                  char *id_str, int id_str_size)
1732 {
1733     BDRVQcowState *s = bs->opaque;
1734     QCowSnapshot *sn;
1735     int i, id, id_max = 0;
1736
1737     for(i = 0; i < s->nb_snapshots; i++) {
1738         sn = s->snapshots + i;
1739         id = strtoul(sn->id_str, NULL, 10);
1740         if (id > id_max)
1741             id_max = id;
1742     }
1743     snprintf(id_str, id_str_size, "%d", id_max + 1);
1744 }
1745
1746 static int find_snapshot_by_id(BlockDriverState *bs, const char *id_str)
1747 {
1748     BDRVQcowState *s = bs->opaque;
1749     int i;
1750
1751     for(i = 0; i < s->nb_snapshots; i++) {
1752         if (!strcmp(s->snapshots[i].id_str, id_str))
1753             return i;
1754     }
1755     return -1;
1756 }
1757
1758 static int find_snapshot_by_id_or_name(BlockDriverState *bs, const char *name)
1759 {
1760     BDRVQcowState *s = bs->opaque;
1761     int i, ret;
1762
1763     ret = find_snapshot_by_id(bs, name);
1764     if (ret >= 0)
1765         return ret;
1766     for(i = 0; i < s->nb_snapshots; i++) {
1767         if (!strcmp(s->snapshots[i].name, name))
1768             return i;
1769     }
1770     return -1;
1771 }
1772
1773 /* if no id is provided, a new one is constructed */
1774 static int qcow_snapshot_create(BlockDriverState *bs,
1775                                 QEMUSnapshotInfo *sn_info)
1776 {
1777     BDRVQcowState *s = bs->opaque;
1778     QCowSnapshot *snapshots1, sn1, *sn = &sn1;
1779     int i, ret;
1780     uint64_t *l1_table = NULL;
1781
1782     memset(sn, 0, sizeof(*sn));
1783
1784     if (sn_info->id_str[0] == '\0') {
1785         /* compute a new id */
1786         find_new_snapshot_id(bs, sn_info->id_str, sizeof(sn_info->id_str));
1787     }
1788
1789     /* check that the ID is unique */
1790     if (find_snapshot_by_id(bs, sn_info->id_str) >= 0)
1791         return -ENOENT;
1792
1793     sn->id_str = qemu_strdup(sn_info->id_str);
1794     if (!sn->id_str)
1795         goto fail;
1796     sn->name = qemu_strdup(sn_info->name);
1797     if (!sn->name)
1798         goto fail;
1799     sn->vm_state_size = sn_info->vm_state_size;
1800     sn->date_sec = sn_info->date_sec;
1801     sn->date_nsec = sn_info->date_nsec;
1802     sn->vm_clock_nsec = sn_info->vm_clock_nsec;
1803
1804     ret = update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 1);
1805     if (ret < 0)
1806         goto fail;
1807
1808     /* create the L1 table of the snapshot */
1809     sn->l1_table_offset = alloc_clusters(bs, s->l1_size * sizeof(uint64_t));
1810     sn->l1_size = s->l1_size;
1811
1812     l1_table = qemu_malloc(s->l1_size * sizeof(uint64_t));
1813     if (!l1_table)
1814         goto fail;
1815     for(i = 0; i < s->l1_size; i++) {
1816         l1_table[i] = cpu_to_be64(s->l1_table[i]);
1817     }
1818     if (bdrv_pwrite(s->hd, sn->l1_table_offset,
1819                     l1_table, s->l1_size * sizeof(uint64_t)) !=
1820         (s->l1_size * sizeof(uint64_t)))
1821         goto fail;
1822     qemu_free(l1_table);
1823     l1_table = NULL;
1824
1825     snapshots1 = qemu_malloc((s->nb_snapshots + 1) * sizeof(QCowSnapshot));
1826     if (!snapshots1)
1827         goto fail;
1828     memcpy(snapshots1, s->snapshots, s->nb_snapshots * sizeof(QCowSnapshot));
1829     s->snapshots = snapshots1;
1830     s->snapshots[s->nb_snapshots++] = *sn;
1831
1832     if (qcow_write_snapshots(bs) < 0)
1833         goto fail;
1834 #ifdef DEBUG_ALLOC
1835     check_refcounts(bs);
1836 #endif
1837     return 0;
1838  fail:
1839     qemu_free(sn->name);
1840     qemu_free(l1_table);
1841     return -1;
1842 }
1843
1844 /* copy the snapshot 'snapshot_name' into the current disk image */
1845 static int qcow_snapshot_goto(BlockDriverState *bs,
1846                               const char *snapshot_id)
1847 {
1848     BDRVQcowState *s = bs->opaque;
1849     QCowSnapshot *sn;
1850     int i, snapshot_index, l1_size2;
1851
1852     snapshot_index = find_snapshot_by_id_or_name(bs, snapshot_id);
1853     if (snapshot_index < 0)
1854         return -ENOENT;
1855     sn = &s->snapshots[snapshot_index];
1856
1857     if (update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, -1) < 0)
1858         goto fail;
1859
1860     if (grow_l1_table(bs, sn->l1_size) < 0)
1861         goto fail;
1862
1863     s->l1_size = sn->l1_size;
1864     l1_size2 = s->l1_size * sizeof(uint64_t);
1865     /* copy the snapshot l1 table to the current l1 table */
1866     if (bdrv_pread(s->hd, sn->l1_table_offset,
1867                    s->l1_table, l1_size2) != l1_size2)
1868         goto fail;
1869     if (bdrv_pwrite(s->hd, s->l1_table_offset,
1870                     s->l1_table, l1_size2) != l1_size2)
1871         goto fail;
1872     for(i = 0;i < s->l1_size; i++) {
1873         be64_to_cpus(&s->l1_table[i]);
1874     }
1875
1876     if (update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 1) < 0)
1877         goto fail;
1878
1879 #ifdef DEBUG_ALLOC
1880     check_refcounts(bs);
1881 #endif
1882     return 0;
1883  fail:
1884     return -EIO;
1885 }
1886
1887 static int qcow_snapshot_delete(BlockDriverState *bs, const char *snapshot_id)
1888 {
1889     BDRVQcowState *s = bs->opaque;
1890     QCowSnapshot *sn;
1891     int snapshot_index, ret;
1892
1893     snapshot_index = find_snapshot_by_id_or_name(bs, snapshot_id);
1894     if (snapshot_index < 0)
1895         return -ENOENT;
1896     sn = &s->snapshots[snapshot_index];
1897
1898     ret = update_snapshot_refcount(bs, sn->l1_table_offset, sn->l1_size, -1);
1899     if (ret < 0)
1900         return ret;
1901     /* must update the copied flag on the current cluster offsets */
1902     ret = update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 0);
1903     if (ret < 0)
1904         return ret;
1905     free_clusters(bs, sn->l1_table_offset, sn->l1_size * sizeof(uint64_t));
1906
1907     qemu_free(sn->id_str);
1908     qemu_free(sn->name);
1909     memmove(sn, sn + 1, (s->nb_snapshots - snapshot_index - 1) * sizeof(*sn));
1910     s->nb_snapshots--;
1911     ret = qcow_write_snapshots(bs);
1912     if (ret < 0) {
1913         /* XXX: restore snapshot if error ? */
1914         return ret;
1915     }
1916 #ifdef DEBUG_ALLOC
1917     check_refcounts(bs);
1918 #endif
1919     return 0;
1920 }
1921
1922 static int qcow_snapshot_list(BlockDriverState *bs,
1923                               QEMUSnapshotInfo **psn_tab)
1924 {
1925     BDRVQcowState *s = bs->opaque;
1926     QEMUSnapshotInfo *sn_tab, *sn_info;
1927     QCowSnapshot *sn;
1928     int i;
1929
1930     sn_tab = qemu_mallocz(s->nb_snapshots * sizeof(QEMUSnapshotInfo));
1931     if (!sn_tab)
1932         goto fail;
1933     for(i = 0; i < s->nb_snapshots; i++) {
1934         sn_info = sn_tab + i;
1935         sn = s->snapshots + i;
1936         pstrcpy(sn_info->id_str, sizeof(sn_info->id_str),
1937                 sn->id_str);
1938         pstrcpy(sn_info->name, sizeof(sn_info->name),
1939                 sn->name);
1940         sn_info->vm_state_size = sn->vm_state_size;
1941         sn_info->date_sec = sn->date_sec;
1942         sn_info->date_nsec = sn->date_nsec;
1943         sn_info->vm_clock_nsec = sn->vm_clock_nsec;
1944     }
1945     *psn_tab = sn_tab;
1946     return s->nb_snapshots;
1947  fail:
1948     qemu_free(sn_tab);
1949     *psn_tab = NULL;
1950     return -ENOMEM;
1951 }
1952
1953 /*********************************************************/
1954 /* refcount handling */
1955
1956 static int refcount_init(BlockDriverState *bs)
1957 {
1958     BDRVQcowState *s = bs->opaque;
1959     int ret, refcount_table_size2, i;
1960
1961     s->refcount_block_cache = qemu_malloc(s->cluster_size);
1962     if (!s->refcount_block_cache)
1963         goto fail;
1964     refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
1965     s->refcount_table = qemu_malloc(refcount_table_size2);
1966     if (!s->refcount_table)
1967         goto fail;
1968     if (s->refcount_table_size > 0) {
1969         ret = bdrv_pread(s->hd, s->refcount_table_offset,
1970                          s->refcount_table, refcount_table_size2);
1971         if (ret != refcount_table_size2)
1972             goto fail;
1973         for(i = 0; i < s->refcount_table_size; i++)
1974             be64_to_cpus(&s->refcount_table[i]);
1975     }
1976     return 0;
1977  fail:
1978     return -ENOMEM;
1979 }
1980
1981 static void refcount_close(BlockDriverState *bs)
1982 {
1983     BDRVQcowState *s = bs->opaque;
1984     qemu_free(s->refcount_block_cache);
1985     qemu_free(s->refcount_table);
1986 }
1987
1988
1989 static int load_refcount_block(BlockDriverState *bs,
1990                                int64_t refcount_block_offset)
1991 {
1992     BDRVQcowState *s = bs->opaque;
1993     int ret;
1994     ret = bdrv_pread(s->hd, refcount_block_offset, s->refcount_block_cache,
1995                      s->cluster_size);
1996     if (ret != s->cluster_size)
1997         return -EIO;
1998     s->refcount_block_cache_offset = refcount_block_offset;
1999     return 0;
2000 }
2001
2002 static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
2003 {
2004     BDRVQcowState *s = bs->opaque;
2005     int refcount_table_index, block_index;
2006     int64_t refcount_block_offset;
2007
2008     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
2009     if (refcount_table_index >= s->refcount_table_size)
2010         return 0;
2011     refcount_block_offset = s->refcount_table[refcount_table_index];
2012     if (!refcount_block_offset)
2013         return 0;
2014     if (refcount_block_offset != s->refcount_block_cache_offset) {
2015         /* better than nothing: return allocated if read error */
2016         if (load_refcount_block(bs, refcount_block_offset) < 0)
2017             return 1;
2018     }
2019     block_index = cluster_index &
2020         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
2021     return be16_to_cpu(s->refcount_block_cache[block_index]);
2022 }
2023
2024 /* return < 0 if error */
2025 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
2026 {
2027     BDRVQcowState *s = bs->opaque;
2028     int i, nb_clusters;
2029
2030     nb_clusters = (size + s->cluster_size - 1) >> s->cluster_bits;
2031     for(;;) {
2032         if (get_refcount(bs, s->free_cluster_index) == 0) {
2033             s->free_cluster_index++;
2034             for(i = 1; i < nb_clusters; i++) {
2035                 if (get_refcount(bs, s->free_cluster_index) != 0)
2036                     goto not_found;
2037                 s->free_cluster_index++;
2038             }
2039 #ifdef DEBUG_ALLOC2
2040             printf("alloc_clusters: size=%lld -> %lld\n",
2041                    size,
2042                    (s->free_cluster_index - nb_clusters) << s->cluster_bits);
2043 #endif
2044             return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
2045         } else {
2046         not_found:
2047             s->free_cluster_index++;
2048         }
2049     }
2050 }
2051
2052 static int64_t alloc_clusters(BlockDriverState *bs, int64_t size)
2053 {
2054     int64_t offset;
2055
2056     offset = alloc_clusters_noref(bs, size);
2057     update_refcount(bs, offset, size, 1);
2058     return offset;
2059 }
2060
2061 /* only used to allocate compressed sectors. We try to allocate
2062    contiguous sectors. size must be <= cluster_size */
2063 static int64_t alloc_bytes(BlockDriverState *bs, int size)
2064 {
2065     BDRVQcowState *s = bs->opaque;
2066     int64_t offset, cluster_offset;
2067     int free_in_cluster;
2068
2069     assert(size > 0 && size <= s->cluster_size);
2070     if (s->free_byte_offset == 0) {
2071         s->free_byte_offset = alloc_clusters(bs, s->cluster_size);
2072     }
2073  redo:
2074     free_in_cluster = s->cluster_size -
2075         (s->free_byte_offset & (s->cluster_size - 1));
2076     if (size <= free_in_cluster) {
2077         /* enough space in current cluster */
2078         offset = s->free_byte_offset;
2079         s->free_byte_offset += size;
2080         free_in_cluster -= size;
2081         if (free_in_cluster == 0)
2082             s->free_byte_offset = 0;
2083         if ((offset & (s->cluster_size - 1)) != 0)
2084             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
2085     } else {
2086         offset = alloc_clusters(bs, s->cluster_size);
2087         cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
2088         if ((cluster_offset + s->cluster_size) == offset) {
2089             /* we are lucky: contiguous data */
2090             offset = s->free_byte_offset;
2091             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
2092             s->free_byte_offset += size;
2093         } else {
2094             s->free_byte_offset = offset;
2095             goto redo;
2096         }
2097     }
2098     return offset;
2099 }
2100
2101 static void free_clusters(BlockDriverState *bs,
2102                           int64_t offset, int64_t size)
2103 {
2104     update_refcount(bs, offset, size, -1);
2105 }
2106
2107 static int grow_refcount_table(BlockDriverState *bs, int min_size)
2108 {
2109     BDRVQcowState *s = bs->opaque;
2110     int new_table_size, new_table_size2, refcount_table_clusters, i, ret;
2111     uint64_t *new_table;
2112     int64_t table_offset;
2113     uint64_t data64;
2114     uint32_t data32;
2115     int old_table_size;
2116     int64_t old_table_offset;
2117
2118     if (min_size <= s->refcount_table_size)
2119         return 0;
2120     /* compute new table size */
2121     refcount_table_clusters = s->refcount_table_size >> (s->cluster_bits - 3);
2122     for(;;) {
2123         if (refcount_table_clusters == 0) {
2124             refcount_table_clusters = 1;
2125         } else {
2126             refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
2127         }
2128         new_table_size = refcount_table_clusters << (s->cluster_bits - 3);
2129         if (min_size <= new_table_size)
2130             break;
2131     }
2132 #ifdef DEBUG_ALLOC2
2133     printf("grow_refcount_table from %d to %d\n",
2134            s->refcount_table_size,
2135            new_table_size);
2136 #endif
2137     new_table_size2 = new_table_size * sizeof(uint64_t);
2138     new_table = qemu_mallocz(new_table_size2);
2139     if (!new_table)
2140         return -ENOMEM;
2141     memcpy(new_table, s->refcount_table,
2142            s->refcount_table_size * sizeof(uint64_t));
2143     for(i = 0; i < s->refcount_table_size; i++)
2144         cpu_to_be64s(&new_table[i]);
2145     /* Note: we cannot update the refcount now to avoid recursion */
2146     table_offset = alloc_clusters_noref(bs, new_table_size2);
2147     ret = bdrv_pwrite(s->hd, table_offset, new_table, new_table_size2);
2148     if (ret != new_table_size2)
2149         goto fail;
2150     for(i = 0; i < s->refcount_table_size; i++)
2151         be64_to_cpus(&new_table[i]);
2152
2153     data64 = cpu_to_be64(table_offset);
2154     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, refcount_table_offset),
2155                     &data64, sizeof(data64)) != sizeof(data64))
2156         goto fail;
2157     data32 = cpu_to_be32(refcount_table_clusters);
2158     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, refcount_table_clusters),
2159                     &data32, sizeof(data32)) != sizeof(data32))
2160         goto fail;
2161     qemu_free(s->refcount_table);
2162     old_table_offset = s->refcount_table_offset;
2163     old_table_size = s->refcount_table_size;
2164     s->refcount_table = new_table;
2165     s->refcount_table_size = new_table_size;
2166     s->refcount_table_offset = table_offset;
2167
2168     update_refcount(bs, table_offset, new_table_size2, 1);
2169     free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
2170     return 0;
2171  fail:
2172     free_clusters(bs, table_offset, new_table_size2);
2173     qemu_free(new_table);
2174     return -EIO;
2175 }
2176
2177 /* addend must be 1 or -1 */
2178 /* XXX: cache several refcount block clusters ? */
2179 static int update_cluster_refcount(BlockDriverState *bs,
2180                                    int64_t cluster_index,
2181                                    int addend)
2182 {
2183     BDRVQcowState *s = bs->opaque;
2184     int64_t offset, refcount_block_offset;
2185     int ret, refcount_table_index, block_index, refcount;
2186     uint64_t data64;
2187
2188     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
2189     if (refcount_table_index >= s->refcount_table_size) {
2190         if (addend < 0)
2191             return -EINVAL;
2192         ret = grow_refcount_table(bs, refcount_table_index + 1);
2193         if (ret < 0)
2194             return ret;
2195     }
2196     refcount_block_offset = s->refcount_table[refcount_table_index];
2197     if (!refcount_block_offset) {
2198         if (addend < 0)
2199             return -EINVAL;
2200         /* create a new refcount block */
2201         /* Note: we cannot update the refcount now to avoid recursion */
2202         offset = alloc_clusters_noref(bs, s->cluster_size);
2203         memset(s->refcount_block_cache, 0, s->cluster_size);
2204         ret = bdrv_pwrite(s->hd, offset, s->refcount_block_cache, s->cluster_size);
2205         if (ret != s->cluster_size)
2206             return -EINVAL;
2207         s->refcount_table[refcount_table_index] = offset;
2208         data64 = cpu_to_be64(offset);
2209         ret = bdrv_pwrite(s->hd, s->refcount_table_offset +
2210                           refcount_table_index * sizeof(uint64_t),
2211                           &data64, sizeof(data64));
2212         if (ret != sizeof(data64))
2213             return -EINVAL;
2214
2215         refcount_block_offset = offset;
2216         s->refcount_block_cache_offset = offset;
2217         update_refcount(bs, offset, s->cluster_size, 1);
2218     } else {
2219         if (refcount_block_offset != s->refcount_block_cache_offset) {
2220             if (load_refcount_block(bs, refcount_block_offset) < 0)
2221                 return -EIO;
2222         }
2223     }
2224     /* we can update the count and save it */
2225     block_index = cluster_index &
2226         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
2227     refcount = be16_to_cpu(s->refcount_block_cache[block_index]);
2228     refcount += addend;
2229     if (refcount < 0 || refcount > 0xffff)
2230         return -EINVAL;
2231     if (refcount == 0 && cluster_index < s->free_cluster_index) {
2232         s->free_cluster_index = cluster_index;
2233     }
2234     s->refcount_block_cache[block_index] = cpu_to_be16(refcount);
2235     if (bdrv_pwrite(s->hd,
2236                     refcount_block_offset + (block_index << REFCOUNT_SHIFT),
2237                     &s->refcount_block_cache[block_index], 2) != 2)
2238         return -EIO;
2239     return refcount;
2240 }
2241
2242 static void update_refcount(BlockDriverState *bs,
2243                             int64_t offset, int64_t length,
2244                             int addend)
2245 {
2246     BDRVQcowState *s = bs->opaque;
2247     int64_t start, last, cluster_offset;
2248
2249 #ifdef DEBUG_ALLOC2
2250     printf("update_refcount: offset=%lld size=%lld addend=%d\n",
2251            offset, length, addend);
2252 #endif
2253     if (length <= 0)
2254         return;
2255     start = offset & ~(s->cluster_size - 1);
2256     last = (offset + length - 1) & ~(s->cluster_size - 1);
2257     for(cluster_offset = start; cluster_offset <= last;
2258         cluster_offset += s->cluster_size) {
2259         update_cluster_refcount(bs, cluster_offset >> s->cluster_bits, addend);
2260     }
2261 }
2262
2263 #ifdef DEBUG_ALLOC
2264 static void inc_refcounts(BlockDriverState *bs,
2265                           uint16_t *refcount_table,
2266                           int refcount_table_size,
2267                           int64_t offset, int64_t size)
2268 {
2269     BDRVQcowState *s = bs->opaque;
2270     int64_t start, last, cluster_offset;
2271     int k;
2272
2273     if (size <= 0)
2274         return;
2275
2276     start = offset & ~(s->cluster_size - 1);
2277     last = (offset + size - 1) & ~(s->cluster_size - 1);
2278     for(cluster_offset = start; cluster_offset <= last;
2279         cluster_offset += s->cluster_size) {
2280         k = cluster_offset >> s->cluster_bits;
2281         if (k < 0 || k >= refcount_table_size) {
2282             printf("ERROR: invalid cluster offset=0x%llx\n", cluster_offset);
2283         } else {
2284             if (++refcount_table[k] == 0) {
2285                 printf("ERROR: overflow cluster offset=0x%llx\n", cluster_offset);
2286             }
2287         }
2288     }
2289 }
2290
2291 static int check_refcounts_l1(BlockDriverState *bs,
2292                               uint16_t *refcount_table,
2293                               int refcount_table_size,
2294                               int64_t l1_table_offset, int l1_size,
2295                               int check_copied)
2296 {
2297     BDRVQcowState *s = bs->opaque;
2298     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2;
2299     int l2_size, i, j, nb_csectors, refcount;
2300
2301     l2_table = NULL;
2302     l1_size2 = l1_size * sizeof(uint64_t);
2303
2304     inc_refcounts(bs, refcount_table, refcount_table_size,
2305                   l1_table_offset, l1_size2);
2306
2307     l1_table = qemu_malloc(l1_size2);
2308     if (!l1_table)
2309         goto fail;
2310     if (bdrv_pread(s->hd, l1_table_offset,
2311                    l1_table, l1_size2) != l1_size2)
2312         goto fail;
2313     for(i = 0;i < l1_size; i++)
2314         be64_to_cpus(&l1_table[i]);
2315
2316     l2_size = s->l2_size * sizeof(uint64_t);
2317     l2_table = qemu_malloc(l2_size);
2318     if (!l2_table)
2319         goto fail;
2320     for(i = 0; i < l1_size; i++) {
2321         l2_offset = l1_table[i];
2322         if (l2_offset) {
2323             if (check_copied) {
2324                 refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED) >> s->cluster_bits);
2325                 if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
2326                     printf("ERROR OFLAG_COPIED: l2_offset=%llx refcount=%d\n",
2327                            l2_offset, refcount);
2328                 }
2329             }
2330             l2_offset &= ~QCOW_OFLAG_COPIED;
2331             if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
2332                 goto fail;
2333             for(j = 0; j < s->l2_size; j++) {
2334                 offset = be64_to_cpu(l2_table[j]);
2335                 if (offset != 0) {
2336                     if (offset & QCOW_OFLAG_COMPRESSED) {
2337                         if (offset & QCOW_OFLAG_COPIED) {
2338                             printf("ERROR: cluster %lld: copied flag must never be set for compressed clusters\n",
2339                                    offset >> s->cluster_bits);
2340                             offset &= ~QCOW_OFLAG_COPIED;
2341                         }
2342                         nb_csectors = ((offset >> s->csize_shift) &
2343                                        s->csize_mask) + 1;
2344                         offset &= s->cluster_offset_mask;
2345                         inc_refcounts(bs, refcount_table,
2346                                       refcount_table_size,
2347                                       offset & ~511, nb_csectors * 512);
2348                     } else {
2349                         if (check_copied) {
2350                             refcount = get_refcount(bs, (offset & ~QCOW_OFLAG_COPIED) >> s->cluster_bits);
2351                             if ((refcount == 1) != ((offset & QCOW_OFLAG_COPIED) != 0)) {
2352                                 printf("ERROR OFLAG_COPIED: offset=%llx refcount=%d\n",
2353                                        offset, refcount);
2354                             }
2355                         }
2356                         offset &= ~QCOW_OFLAG_COPIED;
2357                         inc_refcounts(bs, refcount_table,
2358                                       refcount_table_size,
2359                                       offset, s->cluster_size);
2360                     }
2361                 }
2362             }
2363             inc_refcounts(bs, refcount_table,
2364                           refcount_table_size,
2365                           l2_offset,
2366                           s->cluster_size);
2367         }
2368     }
2369     qemu_free(l1_table);
2370     qemu_free(l2_table);
2371     return 0;
2372  fail:
2373     printf("ERROR: I/O error in check_refcounts_l1\n");
2374     qemu_free(l1_table);
2375     qemu_free(l2_table);
2376     return -EIO;
2377 }
2378
2379 static void check_refcounts(BlockDriverState *bs)
2380 {
2381     BDRVQcowState *s = bs->opaque;
2382     int64_t size;
2383     int nb_clusters, refcount1, refcount2, i;
2384     QCowSnapshot *sn;
2385     uint16_t *refcount_table;
2386
2387     size = bdrv_getlength(s->hd);
2388     nb_clusters = (size + s->cluster_size - 1) >> s->cluster_bits;
2389     refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
2390
2391     /* header */
2392     inc_refcounts(bs, refcount_table, nb_clusters,
2393                   0, s->cluster_size);
2394
2395     check_refcounts_l1(bs, refcount_table, nb_clusters,
2396                        s->l1_table_offset, s->l1_size, 1);
2397
2398     /* snapshots */
2399     for(i = 0; i < s->nb_snapshots; i++) {
2400         sn = s->snapshots + i;
2401         check_refcounts_l1(bs, refcount_table, nb_clusters,
2402                            sn->l1_table_offset, sn->l1_size, 0);
2403     }
2404     inc_refcounts(bs, refcount_table, nb_clusters,
2405                   s->snapshots_offset, s->snapshots_size);
2406
2407     /* refcount data */
2408     inc_refcounts(bs, refcount_table, nb_clusters,
2409                   s->refcount_table_offset,
2410                   s->refcount_table_size * sizeof(uint64_t));
2411     for(i = 0; i < s->refcount_table_size; i++) {
2412         int64_t offset;
2413         offset = s->refcount_table[i];
2414         if (offset != 0) {
2415             inc_refcounts(bs, refcount_table, nb_clusters,
2416                           offset, s->cluster_size);
2417         }
2418     }
2419
2420     /* compare ref counts */
2421     for(i = 0; i < nb_clusters; i++) {
2422         refcount1 = get_refcount(bs, i);
2423         refcount2 = refcount_table[i];
2424         if (refcount1 != refcount2)
2425             printf("ERROR cluster %d refcount=%d reference=%d\n",
2426                    i, refcount1, refcount2);
2427     }
2428
2429     qemu_free(refcount_table);
2430 }
2431
2432 #if 0
2433 static void dump_refcounts(BlockDriverState *bs)
2434 {
2435     BDRVQcowState *s = bs->opaque;
2436     int64_t nb_clusters, k, k1, size;
2437     int refcount;
2438
2439     size = bdrv_getlength(s->hd);
2440     nb_clusters = (size + s->cluster_size - 1) >> s->cluster_bits;
2441     for(k = 0; k < nb_clusters;) {
2442         k1 = k;
2443         refcount = get_refcount(bs, k);
2444         k++;
2445         while (k < nb_clusters && get_refcount(bs, k) == refcount)
2446             k++;
2447         printf("%lld: refcount=%d nb=%lld\n", k, refcount, k - k1);
2448     }
2449 }
2450 #endif
2451 #endif
2452
2453 BlockDriver bdrv_qcow2 = {
2454     "qcow2",
2455     sizeof(BDRVQcowState),
2456     qcow_probe,
2457     qcow_open,
2458     NULL,
2459     NULL,
2460     qcow_close,
2461     qcow_create,
2462     qcow_flush,
2463     qcow_is_allocated,
2464     qcow_set_key,
2465     qcow_make_empty,
2466
2467     .bdrv_aio_read = qcow_aio_read,
2468     .bdrv_aio_write = qcow_aio_write,
2469     .bdrv_aio_cancel = qcow_aio_cancel,
2470     .aiocb_size = sizeof(QCowAIOCB),
2471     .bdrv_write_compressed = qcow_write_compressed,
2472
2473     .bdrv_snapshot_create = qcow_snapshot_create,
2474     .bdrv_snapshot_goto = qcow_snapshot_goto,
2475     .bdrv_snapshot_delete = qcow_snapshot_delete,
2476     .bdrv_snapshot_list = qcow_snapshot_list,
2477     .bdrv_get_info = qcow_get_info,
2478 };