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  * alloc_cluster_offset
 656  *
 657  * For a given offset of the disk image, return cluster offset in
 658  * qcow2 file.
 659  *
 660  * If the offset is not found, allocate a new cluster.
 661  *
 662  * Return the cluster offset if successful,
 663  * Return 0, otherwise.
 664  *
 665  */
 666
 667 static uint64_t alloc_cluster_offset(BlockDriverState *bs,
 668                                      uint64_t offset,
 669                                      int compressed_size,
 670                                      int n_start, int n_end)
 671 {
 672     BDRVQcowState *s = bs->opaque;
 673     int l1_index, l2_index, ret;
 674     uint64_t l2_offset, *l2_table, cluster_offset;
 675
 676     /* seek the the l2 offset in the l1 table */
 677
 678     l1_index = offset >> (s->l2_bits + s->cluster_bits);
 679     if (l1_index >= s->l1_size) {
 680         ret = grow_l1_table(bs, l1_index + 1);
 681         if (ret < 0)
 682             return 0;
 683     }
 684     l2_offset = s->l1_table[l1_index];
 685
 686     /* seek the l2 table of the given l2 offset */
 687
 688     if (l2_offset & QCOW_OFLAG_COPIED) {
 689         /* load the l2 table in memory */
 690         l2_offset &= ~QCOW_OFLAG_COPIED;
 691         l2_table = l2_load(bs, l2_offset);
 692         if (l2_table == NULL)
 693             return 0;
 694     } else {
 695         if (l2_offset)
 696             free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t));
 697         l2_table = l2_allocate(bs, l1_index);
 698         if (l2_table == NULL)
 699             return 0;
 700         l2_offset = s->l1_table[l1_index] & ~QCOW_OFLAG_COPIED;
 701     }
 702
 703     /* find the cluster offset for the given disk offset */
 704
 705     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);
 706     cluster_offset = be64_to_cpu(l2_table[l2_index]);
 707
 708     if (cluster_offset & QCOW_OFLAG_COPIED)
 709         return cluster_offset & ~QCOW_OFLAG_COPIED;
 710
 711     if (cluster_offset) {
 712         /* free the cluster */
 713         if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
 714             int nb_csectors;
 715             nb_csectors = ((cluster_offset >> s->csize_shift) &
 716                            s->csize_mask) + 1;
 717             free_clusters(bs, (cluster_offset & s->cluster_offset_mask) & ~511,
 718                           nb_csectors * 512);
 719         } else {
 720             free_clusters(bs, cluster_offset, s->cluster_size);
 721         }
 722     }
 723
 724     if (compressed_size) {
 725         int nb_csectors;
 726
 727         cluster_offset = alloc_bytes(bs, compressed_size);
 728         nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -
 729                       (cluster_offset >> 9);
 730
 731         cluster_offset |= QCOW_OFLAG_COMPRESSED |
 732                           ((uint64_t)nb_csectors << s->csize_shift);
 733
 734         /* update L2 table */
 735
 736         /* compressed clusters never have the copied flag */
 737
 738         l2_table[l2_index] = cpu_to_be64(cluster_offset);
 739         if (bdrv_pwrite(s->hd,
 740                         l2_offset + l2_index * sizeof(uint64_t),
 741                         l2_table + l2_index,
 742                         sizeof(uint64_t)) != sizeof(uint64_t))
 743             return 0;
 744
 745         return cluster_offset;
 746     }
 747
 748     /* allocate a new cluster */
 749
 750     cluster_offset = alloc_clusters(bs, s->cluster_size);
 751
 752     /* we must initialize the cluster content which won't be
 753        written */
 754
 755     if ((n_end - n_start) < s->cluster_sectors) {
 756         uint64_t start_sect;
 757
 758         start_sect = (offset & ~(s->cluster_size - 1)) >> 9;
 759         ret = copy_sectors(bs, start_sect,
 760                            cluster_offset, 0, n_start);
 761         if (ret < 0)
 762             return 0;
 763         ret = copy_sectors(bs, start_sect,
 764                            cluster_offset, n_end, s->cluster_sectors);
 765         if (ret < 0)
 766             return 0;
 767     }
 768
 769     /* update L2 table */
 770
 771     l2_table[l2_index] = cpu_to_be64(cluster_offset | QCOW_OFLAG_COPIED);
 772     if (bdrv_pwrite(s->hd,
 773                     l2_offset + l2_index * sizeof(uint64_t),
 774                     l2_table + l2_index,
 775                     sizeof(uint64_t)) != sizeof(uint64_t))
 776         return 0;
 777
 778     return cluster_offset;
 779 }
 780
 781 static int qcow_is_allocated(BlockDriverState *bs, int64_t sector_num,
 782                              int nb_sectors, int *pnum)
 783 {
 784     BDRVQcowState *s = bs->opaque;
 785     int index_in_cluster, n;
 786     uint64_t cluster_offset;
 787
 788     cluster_offset = get_cluster_offset(bs, sector_num << 9);
 789     index_in_cluster = sector_num & (s->cluster_sectors - 1);
 790     n = s->cluster_sectors - index_in_cluster;
 791     if (n > nb_sectors)
 792         n = nb_sectors;
 793     *pnum = n;
 794     return (cluster_offset != 0);
 795 }
 796
 797 static int decompress_buffer(uint8_t *out_buf, int out_buf_size,
 798                              const uint8_t *buf, int buf_size)
 799 {
 800     z_stream strm1, *strm = &strm1;
 801     int ret, out_len;
 802
 803     memset(strm, 0, sizeof(*strm));
 804
 805     strm->next_in = (uint8_t *)buf;
 806     strm->avail_in = buf_size;
 807     strm->next_out = out_buf;
 808     strm->avail_out = out_buf_size;
 809
 810     ret = inflateInit2(strm, -12);
 811     if (ret != Z_OK)
 812         return -1;
 813     ret = inflate(strm, Z_FINISH);
 814     out_len = strm->next_out - out_buf;
 815     if ((ret != Z_STREAM_END && ret != Z_BUF_ERROR) ||
 816         out_len != out_buf_size) {
 817         inflateEnd(strm);
 818         return -1;
 819     }
 820     inflateEnd(strm);
 821     return 0;
 822 }
 823
 824 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset)
 825 {
 826     int ret, csize, nb_csectors, sector_offset;
 827     uint64_t coffset;
 828
 829     coffset = cluster_offset & s->cluster_offset_mask;
 830     if (s->cluster_cache_offset != coffset) {
 831         nb_csectors = ((cluster_offset >> s->csize_shift) & s->csize_mask) + 1;
 832         sector_offset = coffset & 511;
 833         csize = nb_csectors * 512 - sector_offset;
 834         ret = bdrv_read(s->hd, coffset >> 9, s->cluster_data, nb_csectors);
 835         if (ret < 0) {
 836             return -1;
 837         }
 838         if (decompress_buffer(s->cluster_cache, s->cluster_size,
 839                               s->cluster_data + sector_offset, csize) < 0) {
 840             return -1;
 841         }
 842         s->cluster_cache_offset = coffset;
 843     }
 844     return 0;
 845 }
 846
 847 /* handle reading after the end of the backing file */
 848 static int backing_read1(BlockDriverState *bs,
 849                          int64_t sector_num, uint8_t *buf, int nb_sectors)
 850 {
 851     int n1;
 852     if ((sector_num + nb_sectors) <= bs->total_sectors)
 853         return nb_sectors;
 854     if (sector_num >= bs->total_sectors)
 855         n1 = 0;
 856     else
 857         n1 = bs->total_sectors - sector_num;
 858     memset(buf + n1 * 512, 0, 512 * (nb_sectors - n1));
 859     return n1;
 860 }
 861
 862 static int qcow_read(BlockDriverState *bs, int64_t sector_num,
 863                      uint8_t *buf, int nb_sectors)
 864 {
 865     BDRVQcowState *s = bs->opaque;
 866     int ret, index_in_cluster, n, n1;
 867     uint64_t cluster_offset;
 868
 869     while (nb_sectors > 0) {
 870         cluster_offset = get_cluster_offset(bs, sector_num << 9);
 871         index_in_cluster = sector_num & (s->cluster_sectors - 1);
 872         n = s->cluster_sectors - index_in_cluster;
 873         if (n > nb_sectors)
 874             n = nb_sectors;
 875         if (!cluster_offset) {
 876             if (bs->backing_hd) {
 877                 /* read from the base image */
 878                 n1 = backing_read1(bs->backing_hd, sector_num, buf, n);
 879                 if (n1 > 0) {
 880                     ret = bdrv_read(bs->backing_hd, sector_num, buf, n1);
 881                     if (ret < 0)
 882                         return -1;
 883                 }
 884             } else {
 885                 memset(buf, 0, 512 * n);
 886             }
 887         } else if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
 888             if (decompress_cluster(s, cluster_offset) < 0)
 889                 return -1;
 890             memcpy(buf, s->cluster_cache + index_in_cluster * 512, 512 * n);
 891         } else {
 892             ret = bdrv_pread(s->hd, cluster_offset + index_in_cluster * 512, buf, n * 512);
 893             if (ret != n * 512)
 894                 return -1;
 895             if (s->crypt_method) {
 896                 encrypt_sectors(s, sector_num, buf, buf, n, 0,
 897                                 &s->aes_decrypt_key);
 898             }
 899         }
 900         nb_sectors -= n;
 901         sector_num += n;
 902         buf += n * 512;
 903     }
 904     return 0;
 905 }
 906
 907 static int qcow_write(BlockDriverState *bs, int64_t sector_num,
 908                      const uint8_t *buf, int nb_sectors)
 909 {
 910     BDRVQcowState *s = bs->opaque;
 911     int ret, index_in_cluster, n;
 912     uint64_t cluster_offset;
 913
 914     while (nb_sectors > 0) {
 915         index_in_cluster = sector_num & (s->cluster_sectors - 1);
 916         n = s->cluster_sectors - index_in_cluster;
 917         if (n > nb_sectors)
 918             n = nb_sectors;
 919         cluster_offset = alloc_cluster_offset(bs, sector_num << 9, 0,
 920                                               index_in_cluster,
 921                                               index_in_cluster + n);
 922         if (!cluster_offset)
 923             return -1;
 924         if (s->crypt_method) {
 925             encrypt_sectors(s, sector_num, s->cluster_data, buf, n, 1,
 926                             &s->aes_encrypt_key);
 927             ret = bdrv_pwrite(s->hd, cluster_offset + index_in_cluster * 512,
 928                               s->cluster_data, n * 512);
 929         } else {
 930             ret = bdrv_pwrite(s->hd, cluster_offset + index_in_cluster * 512, buf, n * 512);
 931         }
 932         if (ret != n * 512)
 933             return -1;
 934         nb_sectors -= n;
 935         sector_num += n;
 936         buf += n * 512;
 937     }
 938     s->cluster_cache_offset = -1; /* disable compressed cache */
 939     return 0;
 940 }
 941
 942 typedef struct QCowAIOCB {
 943     BlockDriverAIOCB common;
 944     int64_t sector_num;
 945     uint8_t *buf;
 946     int nb_sectors;
 947     int n;
 948     uint64_t cluster_offset;
 949     uint8_t *cluster_data;
 950     BlockDriverAIOCB *hd_aiocb;
 951 } QCowAIOCB;
 952
 953 static void qcow_aio_read_cb(void *opaque, int ret)
 954 {
 955     QCowAIOCB *acb = opaque;
 956     BlockDriverState *bs = acb->common.bs;
 957     BDRVQcowState *s = bs->opaque;
 958     int index_in_cluster, n1;
 959
 960     acb->hd_aiocb = NULL;
 961     if (ret < 0) {
 962     fail:
 963         acb->common.cb(acb->common.opaque, ret);
 964         qemu_aio_release(acb);
 965         return;
 966     }
 967
 968  redo:
 969     /* post process the read buffer */
 970     if (!acb->cluster_offset) {
 971         /* nothing to do */
 972     } else if (acb->cluster_offset & QCOW_OFLAG_COMPRESSED) {
 973         /* nothing to do */
 974     } else {
 975         if (s->crypt_method) {
 976             encrypt_sectors(s, acb->sector_num, acb->buf, acb->buf,
 977                             acb->n, 0,
 978                             &s->aes_decrypt_key);
 979         }
 980     }
 981
 982     acb->nb_sectors -= acb->n;
 983     acb->sector_num += acb->n;
 984     acb->buf += acb->n * 512;
 985
 986     if (acb->nb_sectors == 0) {
 987         /* request completed */
 988         acb->common.cb(acb->common.opaque, 0);
 989         qemu_aio_release(acb);
 990         return;
 991     }
 992
 993     /* prepare next AIO request */
 994     acb->cluster_offset = get_cluster_offset(bs, acb->sector_num << 9);
 995     index_in_cluster = acb->sector_num & (s->cluster_sectors - 1);
 996     acb->n = s->cluster_sectors - index_in_cluster;
 997     if (acb->n > acb->nb_sectors)
 998         acb->n = acb->nb_sectors;
 999
1000     if (!acb->cluster_offset) {
1001         if (bs->backing_hd) {
1002             /* read from the base image */
1003             n1 = backing_read1(bs->backing_hd, acb->sector_num,
1004                                acb->buf, acb->n);
1005             if (n1 > 0) {
1006                 acb->hd_aiocb = bdrv_aio_read(bs->backing_hd, acb->sector_num,
1007                                     acb->buf, acb->n, qcow_aio_read_cb, acb);
1008                 if (acb->hd_aiocb == NULL)
1009                     goto fail;
1010             } else {
1011                 goto redo;
1012             }
1013         } else {
1014             /* Note: in this case, no need to wait */
1015             memset(acb->buf, 0, 512 * acb->n);
1016             goto redo;
1017         }
1018     } else if (acb->cluster_offset & QCOW_OFLAG_COMPRESSED) {
1019         /* add AIO support for compressed blocks ? */
1020         if (decompress_cluster(s, acb->cluster_offset) < 0)
1021             goto fail;
1022         memcpy(acb->buf,
1023                s->cluster_cache + index_in_cluster * 512, 512 * acb->n);
1024         goto redo;
1025     } else {
1026         if ((acb->cluster_offset & 511) != 0) {
1027             ret = -EIO;
1028             goto fail;
1029         }
1030         acb->hd_aiocb = bdrv_aio_read(s->hd,
1031                             (acb->cluster_offset >> 9) + index_in_cluster,
1032                             acb->buf, acb->n, qcow_aio_read_cb, acb);
1033         if (acb->hd_aiocb == NULL)
1034             goto fail;
1035     }
1036 }
1037
1038 static QCowAIOCB *qcow_aio_setup(BlockDriverState *bs,
1039         int64_t sector_num, uint8_t *buf, int nb_sectors,
1040         BlockDriverCompletionFunc *cb, void *opaque)
1041 {
1042     QCowAIOCB *acb;
1043
1044     acb = qemu_aio_get(bs, cb, opaque);
1045     if (!acb)
1046         return NULL;
1047     acb->hd_aiocb = NULL;
1048     acb->sector_num = sector_num;
1049     acb->buf = buf;
1050     acb->nb_sectors = nb_sectors;
1051     acb->n = 0;
1052     acb->cluster_offset = 0;
1053     return acb;
1054 }
1055
1056 static BlockDriverAIOCB *qcow_aio_read(BlockDriverState *bs,
1057         int64_t sector_num, uint8_t *buf, int nb_sectors,
1058         BlockDriverCompletionFunc *cb, void *opaque)
1059 {
1060     QCowAIOCB *acb;
1061
1062     acb = qcow_aio_setup(bs, sector_num, buf, nb_sectors, cb, opaque);
1063     if (!acb)
1064         return NULL;
1065
1066     qcow_aio_read_cb(acb, 0);
1067     return &acb->common;
1068 }
1069
1070 static void qcow_aio_write_cb(void *opaque, int ret)
1071 {
1072     QCowAIOCB *acb = opaque;
1073     BlockDriverState *bs = acb->common.bs;
1074     BDRVQcowState *s = bs->opaque;
1075     int index_in_cluster;
1076     uint64_t cluster_offset;
1077     const uint8_t *src_buf;
1078
1079     acb->hd_aiocb = NULL;
1080
1081     if (ret < 0) {
1082     fail:
1083         acb->common.cb(acb->common.opaque, ret);
1084         qemu_aio_release(acb);
1085         return;
1086     }
1087
1088     acb->nb_sectors -= acb->n;
1089     acb->sector_num += acb->n;
1090     acb->buf += acb->n * 512;
1091
1092     if (acb->nb_sectors == 0) {
1093         /* request completed */
1094         acb->common.cb(acb->common.opaque, 0);
1095         qemu_aio_release(acb);
1096         return;
1097     }
1098
1099     index_in_cluster = acb->sector_num & (s->cluster_sectors - 1);
1100     acb->n = s->cluster_sectors - index_in_cluster;
1101     if (acb->n > acb->nb_sectors)
1102         acb->n = acb->nb_sectors;
1103     cluster_offset = alloc_cluster_offset(bs, acb->sector_num << 9, 0,
1104                                           index_in_cluster,
1105                                           index_in_cluster + acb->n);
1106     if (!cluster_offset || (cluster_offset & 511) != 0) {
1107         ret = -EIO;
1108         goto fail;
1109     }
1110     if (s->crypt_method) {
1111         if (!acb->cluster_data) {
1112             acb->cluster_data = qemu_mallocz(s->cluster_size);
1113             if (!acb->cluster_data) {
1114                 ret = -ENOMEM;
1115                 goto fail;
1116             }
1117         }
1118         encrypt_sectors(s, acb->sector_num, acb->cluster_data, acb->buf,
1119                         acb->n, 1, &s->aes_encrypt_key);
1120         src_buf = acb->cluster_data;
1121     } else {
1122         src_buf = acb->buf;
1123     }
1124     acb->hd_aiocb = bdrv_aio_write(s->hd,
1125                                    (cluster_offset >> 9) + index_in_cluster,
1126                                    src_buf, acb->n,
1127                                    qcow_aio_write_cb, acb);
1128     if (acb->hd_aiocb == NULL)
1129         goto fail;
1130 }
1131
1132 static BlockDriverAIOCB *qcow_aio_write(BlockDriverState *bs,
1133         int64_t sector_num, const uint8_t *buf, int nb_sectors,
1134         BlockDriverCompletionFunc *cb, void *opaque)
1135 {
1136     BDRVQcowState *s = bs->opaque;
1137     QCowAIOCB *acb;
1138
1139     s->cluster_cache_offset = -1; /* disable compressed cache */
1140
1141     acb = qcow_aio_setup(bs, sector_num, (uint8_t*)buf, nb_sectors, cb, opaque);
1142     if (!acb)
1143         return NULL;
1144
1145     qcow_aio_write_cb(acb, 0);
1146     return &acb->common;
1147 }
1148
1149 static void qcow_aio_cancel(BlockDriverAIOCB *blockacb)
1150 {
1151     QCowAIOCB *acb = (QCowAIOCB *)blockacb;
1152     if (acb->hd_aiocb)
1153         bdrv_aio_cancel(acb->hd_aiocb);
1154     qemu_aio_release(acb);
1155 }
1156
1157 static void qcow_close(BlockDriverState *bs)
1158 {
1159     BDRVQcowState *s = bs->opaque;
1160     qemu_free(s->l1_table);
1161     qemu_free(s->l2_cache);
1162     qemu_free(s->cluster_cache);
1163     qemu_free(s->cluster_data);
1164     refcount_close(bs);
1165     bdrv_delete(s->hd);
1166 }
1167
1168 /* XXX: use std qcow open function ? */
1169 typedef struct QCowCreateState {
1170     int cluster_size;
1171     int cluster_bits;
1172     uint16_t *refcount_block;
1173     uint64_t *refcount_table;
1174     int64_t l1_table_offset;
1175     int64_t refcount_table_offset;
1176     int64_t refcount_block_offset;
1177 } QCowCreateState;
1178
1179 static void create_refcount_update(QCowCreateState *s,
1180                                    int64_t offset, int64_t size)
1181 {
1182     int refcount;
1183     int64_t start, last, cluster_offset;
1184     uint16_t *p;
1185
1186     start = offset & ~(s->cluster_size - 1);
1187     last = (offset + size - 1)  & ~(s->cluster_size - 1);
1188     for(cluster_offset = start; cluster_offset <= last;
1189         cluster_offset += s->cluster_size) {
1190         p = &s->refcount_block[cluster_offset >> s->cluster_bits];
1191         refcount = be16_to_cpu(*p);
1192         refcount++;
1193         *p = cpu_to_be16(refcount);
1194     }
1195 }
1196
1197 static int qcow_create(const char *filename, int64_t total_size,
1198                       const char *backing_file, int flags)
1199 {
1200     int fd, header_size, backing_filename_len, l1_size, i, shift, l2_bits;
1201     QCowHeader header;
1202     uint64_t tmp, offset;
1203     QCowCreateState s1, *s = &s1;
1204
1205     memset(s, 0, sizeof(*s));
1206
1207     fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0644);
1208     if (fd < 0)
1209         return -1;
1210     memset(&header, 0, sizeof(header));
1211     header.magic = cpu_to_be32(QCOW_MAGIC);
1212     header.version = cpu_to_be32(QCOW_VERSION);
1213     header.size = cpu_to_be64(total_size * 512);
1214     header_size = sizeof(header);
1215     backing_filename_len = 0;
1216     if (backing_file) {
1217         header.backing_file_offset = cpu_to_be64(header_size);
1218         backing_filename_len = strlen(backing_file);
1219         header.backing_file_size = cpu_to_be32(backing_filename_len);
1220         header_size += backing_filename_len;
1221     }
1222     s->cluster_bits = 12;  /* 4 KB clusters */
1223     s->cluster_size = 1 << s->cluster_bits;
1224     header.cluster_bits = cpu_to_be32(s->cluster_bits);
1225     header_size = (header_size + 7) & ~7;
1226     if (flags & BLOCK_FLAG_ENCRYPT) {
1227         header.crypt_method = cpu_to_be32(QCOW_CRYPT_AES);
1228     } else {
1229         header.crypt_method = cpu_to_be32(QCOW_CRYPT_NONE);
1230     }
1231     l2_bits = s->cluster_bits - 3;
1232     shift = s->cluster_bits + l2_bits;
1233     l1_size = (((total_size * 512) + (1LL << shift) - 1) >> shift);
1234     offset = align_offset(header_size, s->cluster_size);
1235     s->l1_table_offset = offset;
1236     header.l1_table_offset = cpu_to_be64(s->l1_table_offset);
1237     header.l1_size = cpu_to_be32(l1_size);
1238     offset += align_offset(l1_size * sizeof(uint64_t), s->cluster_size);
1239
1240     s->refcount_table = qemu_mallocz(s->cluster_size);
1241     if (!s->refcount_table)
1242         goto fail;
1243     s->refcount_block = qemu_mallocz(s->cluster_size);
1244     if (!s->refcount_block)
1245         goto fail;
1246
1247     s->refcount_table_offset = offset;
1248     header.refcount_table_offset = cpu_to_be64(offset);
1249     header.refcount_table_clusters = cpu_to_be32(1);
1250     offset += s->cluster_size;
1251
1252     s->refcount_table[0] = cpu_to_be64(offset);
1253     s->refcount_block_offset = offset;
1254     offset += s->cluster_size;
1255
1256     /* update refcounts */
1257     create_refcount_update(s, 0, header_size);
1258     create_refcount_update(s, s->l1_table_offset, l1_size * sizeof(uint64_t));
1259     create_refcount_update(s, s->refcount_table_offset, s->cluster_size);
1260     create_refcount_update(s, s->refcount_block_offset, s->cluster_size);
1261
1262     /* write all the data */
1263     write(fd, &header, sizeof(header));
1264     if (backing_file) {
1265         write(fd, backing_file, backing_filename_len);
1266     }
1267     lseek(fd, s->l1_table_offset, SEEK_SET);
1268     tmp = 0;
1269     for(i = 0;i < l1_size; i++) {
1270         write(fd, &tmp, sizeof(tmp));
1271     }
1272     lseek(fd, s->refcount_table_offset, SEEK_SET);
1273     write(fd, s->refcount_table, s->cluster_size);
1274
1275     lseek(fd, s->refcount_block_offset, SEEK_SET);
1276     write(fd, s->refcount_block, s->cluster_size);
1277
1278     qemu_free(s->refcount_table);
1279     qemu_free(s->refcount_block);
1280     close(fd);
1281     return 0;
1282  fail:
1283     qemu_free(s->refcount_table);
1284     qemu_free(s->refcount_block);
1285     close(fd);
1286     return -ENOMEM;
1287 }
1288
1289 static int qcow_make_empty(BlockDriverState *bs)
1290 {
1291 #if 0
1292     /* XXX: not correct */
1293     BDRVQcowState *s = bs->opaque;
1294     uint32_t l1_length = s->l1_size * sizeof(uint64_t);
1295     int ret;
1296
1297     memset(s->l1_table, 0, l1_length);
1298     if (bdrv_pwrite(s->hd, s->l1_table_offset, s->l1_table, l1_length) < 0)
1299         return -1;
1300     ret = bdrv_truncate(s->hd, s->l1_table_offset + l1_length);
1301     if (ret < 0)
1302         return ret;
1303
1304     l2_cache_reset(bs);
1305 #endif
1306     return 0;
1307 }
1308
1309 /* XXX: put compressed sectors first, then all the cluster aligned
1310    tables to avoid losing bytes in alignment */
1311 static int qcow_write_compressed(BlockDriverState *bs, int64_t sector_num,
1312                                  const uint8_t *buf, int nb_sectors)
1313 {
1314     BDRVQcowState *s = bs->opaque;
1315     z_stream strm;
1316     int ret, out_len;
1317     uint8_t *out_buf;
1318     uint64_t cluster_offset;
1319
1320     if (nb_sectors == 0) {
1321         /* align end of file to a sector boundary to ease reading with
1322            sector based I/Os */
1323         cluster_offset = bdrv_getlength(s->hd);
1324         cluster_offset = (cluster_offset + 511) & ~511;
1325         bdrv_truncate(s->hd, cluster_offset);
1326         return 0;
1327     }
1328
1329     if (nb_sectors != s->cluster_sectors)
1330         return -EINVAL;
1331
1332     out_buf = qemu_malloc(s->cluster_size + (s->cluster_size / 1000) + 128);
1333     if (!out_buf)
1334         return -ENOMEM;
1335
1336     /* best compression, small window, no zlib header */
1337     memset(&strm, 0, sizeof(strm));
1338     ret = deflateInit2(&strm, Z_DEFAULT_COMPRESSION,
1339                        Z_DEFLATED, -12,
1340                        9, Z_DEFAULT_STRATEGY);
1341     if (ret != 0) {
1342         qemu_free(out_buf);
1343         return -1;
1344     }
1345
1346     strm.avail_in = s->cluster_size;
1347     strm.next_in = (uint8_t *)buf;
1348     strm.avail_out = s->cluster_size;
1349     strm.next_out = out_buf;
1350
1351     ret = deflate(&strm, Z_FINISH);
1352     if (ret != Z_STREAM_END && ret != Z_OK) {
1353         qemu_free(out_buf);
1354         deflateEnd(&strm);
1355         return -1;
1356     }
1357     out_len = strm.next_out - out_buf;
1358
1359     deflateEnd(&strm);
1360
1361     if (ret != Z_STREAM_END || out_len >= s->cluster_size) {
1362         /* could not compress: write normal cluster */
1363         qcow_write(bs, sector_num, buf, s->cluster_sectors);
1364     } else {
1365         cluster_offset = alloc_cluster_offset(bs, sector_num << 9,
1366                                               out_len, 0, 0);
1367         cluster_offset &= s->cluster_offset_mask;
1368         if (bdrv_pwrite(s->hd, cluster_offset, out_buf, out_len) != out_len) {
1369             qemu_free(out_buf);
1370             return -1;
1371         }
1372     }
1373
1374     qemu_free(out_buf);
1375     return 0;
1376 }
1377
1378 static void qcow_flush(BlockDriverState *bs)
1379 {
1380     BDRVQcowState *s = bs->opaque;
1381     bdrv_flush(s->hd);
1382 }
1383
1384 static int qcow_get_info(BlockDriverState *bs, BlockDriverInfo *bdi)
1385 {
1386     BDRVQcowState *s = bs->opaque;
1387     bdi->cluster_size = s->cluster_size;
1388     bdi->vm_state_offset = (int64_t)s->l1_vm_state_index <<
1389         (s->cluster_bits + s->l2_bits);
1390     return 0;
1391 }
1392
1393 /*********************************************************/
1394 /* snapshot support */
1395
1396 /* update the refcounts of snapshots and the copied flag */
1397 static int update_snapshot_refcount(BlockDriverState *bs,
1398                                     int64_t l1_table_offset,
1399                                     int l1_size,
1400                                     int addend)
1401 {
1402     BDRVQcowState *s = bs->opaque;
1403     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
1404     int64_t old_offset, old_l2_offset;
1405     int l2_size, i, j, l1_modified, l2_modified, nb_csectors, refcount;
1406
1407     l2_cache_reset(bs);
1408
1409     l2_table = NULL;
1410     l1_table = NULL;
1411     l1_size2 = l1_size * sizeof(uint64_t);
1412     l1_allocated = 0;
1413     if (l1_table_offset != s->l1_table_offset) {
1414         l1_table = qemu_malloc(l1_size2);
1415         if (!l1_table)
1416             goto fail;
1417         l1_allocated = 1;
1418         if (bdrv_pread(s->hd, l1_table_offset,
1419                        l1_table, l1_size2) != l1_size2)
1420             goto fail;
1421         for(i = 0;i < l1_size; i++)
1422             be64_to_cpus(&l1_table[i]);
1423     } else {
1424         assert(l1_size == s->l1_size);
1425         l1_table = s->l1_table;
1426         l1_allocated = 0;
1427     }
1428
1429     l2_size = s->l2_size * sizeof(uint64_t);
1430     l2_table = qemu_malloc(l2_size);
1431     if (!l2_table)
1432         goto fail;
1433     l1_modified = 0;
1434     for(i = 0; i < l1_size; i++) {
1435         l2_offset = l1_table[i];
1436         if (l2_offset) {
1437             old_l2_offset = l2_offset;
1438             l2_offset &= ~QCOW_OFLAG_COPIED;
1439             l2_modified = 0;
1440             if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
1441                 goto fail;
1442             for(j = 0; j < s->l2_size; j++) {
1443                 offset = be64_to_cpu(l2_table[j]);
1444                 if (offset != 0) {
1445                     old_offset = offset;
1446                     offset &= ~QCOW_OFLAG_COPIED;
1447                     if (offset & QCOW_OFLAG_COMPRESSED) {
1448                         nb_csectors = ((offset >> s->csize_shift) &
1449                                        s->csize_mask) + 1;
1450                         if (addend != 0)
1451                             update_refcount(bs, (offset & s->cluster_offset_mask) & ~511,
1452                                             nb_csectors * 512, addend);
1453                         /* compressed clusters are never modified */
1454                         refcount = 2;
1455                     } else {
1456                         if (addend != 0) {
1457                             refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
1458                         } else {
1459                             refcount = get_refcount(bs, offset >> s->cluster_bits);
1460                         }
1461                     }
1462
1463                     if (refcount == 1) {
1464                         offset |= QCOW_OFLAG_COPIED;
1465                     }
1466                     if (offset != old_offset) {
1467                         l2_table[j] = cpu_to_be64(offset);
1468                         l2_modified = 1;
1469                     }
1470                 }
1471             }
1472             if (l2_modified) {
1473                 if (bdrv_pwrite(s->hd,
1474                                 l2_offset, l2_table, l2_size) != l2_size)
1475                     goto fail;
1476             }
1477
1478             if (addend != 0) {
1479                 refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
1480             } else {
1481                 refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
1482             }
1483             if (refcount == 1) {
1484                 l2_offset |= QCOW_OFLAG_COPIED;
1485             }
1486             if (l2_offset != old_l2_offset) {
1487                 l1_table[i] = l2_offset;
1488                 l1_modified = 1;
1489             }
1490         }
1491     }
1492     if (l1_modified) {
1493         for(i = 0; i < l1_size; i++)
1494             cpu_to_be64s(&l1_table[i]);
1495         if (bdrv_pwrite(s->hd, l1_table_offset, l1_table,
1496                         l1_size2) != l1_size2)
1497             goto fail;
1498         for(i = 0; i < l1_size; i++)
1499             be64_to_cpus(&l1_table[i]);
1500     }
1501     if (l1_allocated)
1502         qemu_free(l1_table);
1503     qemu_free(l2_table);
1504     return 0;
1505  fail:
1506     if (l1_allocated)
1507         qemu_free(l1_table);
1508     qemu_free(l2_table);
1509     return -EIO;
1510 }
1511
1512 static void qcow_free_snapshots(BlockDriverState *bs)
1513 {
1514     BDRVQcowState *s = bs->opaque;
1515     int i;
1516
1517     for(i = 0; i < s->nb_snapshots; i++) {
1518         qemu_free(s->snapshots[i].name);
1519         qemu_free(s->snapshots[i].id_str);
1520     }
1521     qemu_free(s->snapshots);
1522     s->snapshots = NULL;
1523     s->nb_snapshots = 0;
1524 }
1525
1526 static int qcow_read_snapshots(BlockDriverState *bs)
1527 {
1528     BDRVQcowState *s = bs->opaque;
1529     QCowSnapshotHeader h;
1530     QCowSnapshot *sn;
1531     int i, id_str_size, name_size;
1532     int64_t offset;
1533     uint32_t extra_data_size;
1534
1535     offset = s->snapshots_offset;
1536     s->snapshots = qemu_mallocz(s->nb_snapshots * sizeof(QCowSnapshot));
1537     if (!s->snapshots)
1538         goto fail;
1539     for(i = 0; i < s->nb_snapshots; i++) {
1540         offset = align_offset(offset, 8);
1541         if (bdrv_pread(s->hd, offset, &h, sizeof(h)) != sizeof(h))
1542             goto fail;
1543         offset += sizeof(h);
1544         sn = s->snapshots + i;
1545         sn->l1_table_offset = be64_to_cpu(h.l1_table_offset);
1546         sn->l1_size = be32_to_cpu(h.l1_size);
1547         sn->vm_state_size = be32_to_cpu(h.vm_state_size);
1548         sn->date_sec = be32_to_cpu(h.date_sec);
1549         sn->date_nsec = be32_to_cpu(h.date_nsec);
1550         sn->vm_clock_nsec = be64_to_cpu(h.vm_clock_nsec);
1551         extra_data_size = be32_to_cpu(h.extra_data_size);
1552
1553         id_str_size = be16_to_cpu(h.id_str_size);
1554         name_size = be16_to_cpu(h.name_size);
1555
1556         offset += extra_data_size;
1557
1558         sn->id_str = qemu_malloc(id_str_size + 1);
1559         if (!sn->id_str)
1560             goto fail;
1561         if (bdrv_pread(s->hd, offset, sn->id_str, id_str_size) != id_str_size)
1562             goto fail;
1563         offset += id_str_size;
1564         sn->id_str[id_str_size] = '\0';
1565
1566         sn->name = qemu_malloc(name_size + 1);
1567         if (!sn->name)
1568             goto fail;
1569         if (bdrv_pread(s->hd, offset, sn->name, name_size) != name_size)
1570             goto fail;
1571         offset += name_size;
1572         sn->name[name_size] = '\0';
1573     }
1574     s->snapshots_size = offset - s->snapshots_offset;
1575     return 0;
1576  fail:
1577     qcow_free_snapshots(bs);
1578     return -1;
1579 }
1580
1581 /* add at the end of the file a new list of snapshots */
1582 static int qcow_write_snapshots(BlockDriverState *bs)
1583 {
1584     BDRVQcowState *s = bs->opaque;
1585     QCowSnapshot *sn;
1586     QCowSnapshotHeader h;
1587     int i, name_size, id_str_size, snapshots_size;
1588     uint64_t data64;
1589     uint32_t data32;
1590     int64_t offset, snapshots_offset;
1591
1592     /* compute the size of the snapshots */
1593     offset = 0;
1594     for(i = 0; i < s->nb_snapshots; i++) {
1595         sn = s->snapshots + i;
1596         offset = align_offset(offset, 8);
1597         offset += sizeof(h);
1598         offset += strlen(sn->id_str);
1599         offset += strlen(sn->name);
1600     }
1601     snapshots_size = offset;
1602
1603     snapshots_offset = alloc_clusters(bs, snapshots_size);
1604     offset = snapshots_offset;
1605
1606     for(i = 0; i < s->nb_snapshots; i++) {
1607         sn = s->snapshots + i;
1608         memset(&h, 0, sizeof(h));
1609         h.l1_table_offset = cpu_to_be64(sn->l1_table_offset);
1610         h.l1_size = cpu_to_be32(sn->l1_size);
1611         h.vm_state_size = cpu_to_be32(sn->vm_state_size);
1612         h.date_sec = cpu_to_be32(sn->date_sec);
1613         h.date_nsec = cpu_to_be32(sn->date_nsec);
1614         h.vm_clock_nsec = cpu_to_be64(sn->vm_clock_nsec);
1615
1616         id_str_size = strlen(sn->id_str);
1617         name_size = strlen(sn->name);
1618         h.id_str_size = cpu_to_be16(id_str_size);
1619         h.name_size = cpu_to_be16(name_size);
1620         offset = align_offset(offset, 8);
1621         if (bdrv_pwrite(s->hd, offset, &h, sizeof(h)) != sizeof(h))
1622             goto fail;
1623         offset += sizeof(h);
1624         if (bdrv_pwrite(s->hd, offset, sn->id_str, id_str_size) != id_str_size)
1625             goto fail;
1626         offset += id_str_size;
1627         if (bdrv_pwrite(s->hd, offset, sn->name, name_size) != name_size)
1628             goto fail;
1629         offset += name_size;
1630     }
1631
1632     /* update the various header fields */
1633     data64 = cpu_to_be64(snapshots_offset);
1634     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, snapshots_offset),
1635                     &data64, sizeof(data64)) != sizeof(data64))
1636         goto fail;
1637     data32 = cpu_to_be32(s->nb_snapshots);
1638     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, nb_snapshots),
1639                     &data32, sizeof(data32)) != sizeof(data32))
1640         goto fail;
1641
1642     /* free the old snapshot table */
1643     free_clusters(bs, s->snapshots_offset, s->snapshots_size);
1644     s->snapshots_offset = snapshots_offset;
1645     s->snapshots_size = snapshots_size;
1646     return 0;
1647  fail:
1648     return -1;
1649 }
1650
1651 static void find_new_snapshot_id(BlockDriverState *bs,
1652                                  char *id_str, int id_str_size)
1653 {
1654     BDRVQcowState *s = bs->opaque;
1655     QCowSnapshot *sn;
1656     int i, id, id_max = 0;
1657
1658     for(i = 0; i < s->nb_snapshots; i++) {
1659         sn = s->snapshots + i;
1660         id = strtoul(sn->id_str, NULL, 10);
1661         if (id > id_max)
1662             id_max = id;
1663     }
1664     snprintf(id_str, id_str_size, "%d", id_max + 1);
1665 }
1666
1667 static int find_snapshot_by_id(BlockDriverState *bs, const char *id_str)
1668 {
1669     BDRVQcowState *s = bs->opaque;
1670     int i;
1671
1672     for(i = 0; i < s->nb_snapshots; i++) {
1673         if (!strcmp(s->snapshots[i].id_str, id_str))
1674             return i;
1675     }
1676     return -1;
1677 }
1678
1679 static int find_snapshot_by_id_or_name(BlockDriverState *bs, const char *name)
1680 {
1681     BDRVQcowState *s = bs->opaque;
1682     int i, ret;
1683
1684     ret = find_snapshot_by_id(bs, name);
1685     if (ret >= 0)
1686         return ret;
1687     for(i = 0; i < s->nb_snapshots; i++) {
1688         if (!strcmp(s->snapshots[i].name, name))
1689             return i;
1690     }
1691     return -1;
1692 }
1693
1694 /* if no id is provided, a new one is constructed */
1695 static int qcow_snapshot_create(BlockDriverState *bs,
1696                                 QEMUSnapshotInfo *sn_info)
1697 {
1698     BDRVQcowState *s = bs->opaque;
1699     QCowSnapshot *snapshots1, sn1, *sn = &sn1;
1700     int i, ret;
1701     uint64_t *l1_table = NULL;
1702
1703     memset(sn, 0, sizeof(*sn));
1704
1705     if (sn_info->id_str[0] == '\0') {
1706         /* compute a new id */
1707         find_new_snapshot_id(bs, sn_info->id_str, sizeof(sn_info->id_str));
1708     }
1709
1710     /* check that the ID is unique */
1711     if (find_snapshot_by_id(bs, sn_info->id_str) >= 0)
1712         return -ENOENT;
1713
1714     sn->id_str = qemu_strdup(sn_info->id_str);
1715     if (!sn->id_str)
1716         goto fail;
1717     sn->name = qemu_strdup(sn_info->name);
1718     if (!sn->name)
1719         goto fail;
1720     sn->vm_state_size = sn_info->vm_state_size;
1721     sn->date_sec = sn_info->date_sec;
1722     sn->date_nsec = sn_info->date_nsec;
1723     sn->vm_clock_nsec = sn_info->vm_clock_nsec;
1724
1725     ret = update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 1);
1726     if (ret < 0)
1727         goto fail;
1728
1729     /* create the L1 table of the snapshot */
1730     sn->l1_table_offset = alloc_clusters(bs, s->l1_size * sizeof(uint64_t));
1731     sn->l1_size = s->l1_size;
1732
1733     l1_table = qemu_malloc(s->l1_size * sizeof(uint64_t));
1734     if (!l1_table)
1735         goto fail;
1736     for(i = 0; i < s->l1_size; i++) {
1737         l1_table[i] = cpu_to_be64(s->l1_table[i]);
1738     }
1739     if (bdrv_pwrite(s->hd, sn->l1_table_offset,
1740                     l1_table, s->l1_size * sizeof(uint64_t)) !=
1741         (s->l1_size * sizeof(uint64_t)))
1742         goto fail;
1743     qemu_free(l1_table);
1744     l1_table = NULL;
1745
1746     snapshots1 = qemu_malloc((s->nb_snapshots + 1) * sizeof(QCowSnapshot));
1747     if (!snapshots1)
1748         goto fail;
1749     memcpy(snapshots1, s->snapshots, s->nb_snapshots * sizeof(QCowSnapshot));
1750     s->snapshots = snapshots1;
1751     s->snapshots[s->nb_snapshots++] = *sn;
1752
1753     if (qcow_write_snapshots(bs) < 0)
1754         goto fail;
1755 #ifdef DEBUG_ALLOC
1756     check_refcounts(bs);
1757 #endif
1758     return 0;
1759  fail:
1760     qemu_free(sn->name);
1761     qemu_free(l1_table);
1762     return -1;
1763 }
1764
1765 /* copy the snapshot 'snapshot_name' into the current disk image */
1766 static int qcow_snapshot_goto(BlockDriverState *bs,
1767                               const char *snapshot_id)
1768 {
1769     BDRVQcowState *s = bs->opaque;
1770     QCowSnapshot *sn;
1771     int i, snapshot_index, l1_size2;
1772
1773     snapshot_index = find_snapshot_by_id_or_name(bs, snapshot_id);
1774     if (snapshot_index < 0)
1775         return -ENOENT;
1776     sn = &s->snapshots[snapshot_index];
1777
1778     if (update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, -1) < 0)
1779         goto fail;
1780
1781     if (grow_l1_table(bs, sn->l1_size) < 0)
1782         goto fail;
1783
1784     s->l1_size = sn->l1_size;
1785     l1_size2 = s->l1_size * sizeof(uint64_t);
1786     /* copy the snapshot l1 table to the current l1 table */
1787     if (bdrv_pread(s->hd, sn->l1_table_offset,
1788                    s->l1_table, l1_size2) != l1_size2)
1789         goto fail;
1790     if (bdrv_pwrite(s->hd, s->l1_table_offset,
1791                     s->l1_table, l1_size2) != l1_size2)
1792         goto fail;
1793     for(i = 0;i < s->l1_size; i++) {
1794         be64_to_cpus(&s->l1_table[i]);
1795     }
1796
1797     if (update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 1) < 0)
1798         goto fail;
1799
1800 #ifdef DEBUG_ALLOC
1801     check_refcounts(bs);
1802 #endif
1803     return 0;
1804  fail:
1805     return -EIO;
1806 }
1807
1808 static int qcow_snapshot_delete(BlockDriverState *bs, const char *snapshot_id)
1809 {
1810     BDRVQcowState *s = bs->opaque;
1811     QCowSnapshot *sn;
1812     int snapshot_index, ret;
1813
1814     snapshot_index = find_snapshot_by_id_or_name(bs, snapshot_id);
1815     if (snapshot_index < 0)
1816         return -ENOENT;
1817     sn = &s->snapshots[snapshot_index];
1818
1819     ret = update_snapshot_refcount(bs, sn->l1_table_offset, sn->l1_size, -1);
1820     if (ret < 0)
1821         return ret;
1822     /* must update the copied flag on the current cluster offsets */
1823     ret = update_snapshot_refcount(bs, s->l1_table_offset, s->l1_size, 0);
1824     if (ret < 0)
1825         return ret;
1826     free_clusters(bs, sn->l1_table_offset, sn->l1_size * sizeof(uint64_t));
1827
1828     qemu_free(sn->id_str);
1829     qemu_free(sn->name);
1830     memmove(sn, sn + 1, (s->nb_snapshots - snapshot_index - 1) * sizeof(*sn));
1831     s->nb_snapshots--;
1832     ret = qcow_write_snapshots(bs);
1833     if (ret < 0) {
1834         /* XXX: restore snapshot if error ? */
1835         return ret;
1836     }
1837 #ifdef DEBUG_ALLOC
1838     check_refcounts(bs);
1839 #endif
1840     return 0;
1841 }
1842
1843 static int qcow_snapshot_list(BlockDriverState *bs,
1844                               QEMUSnapshotInfo **psn_tab)
1845 {
1846     BDRVQcowState *s = bs->opaque;
1847     QEMUSnapshotInfo *sn_tab, *sn_info;
1848     QCowSnapshot *sn;
1849     int i;
1850
1851     sn_tab = qemu_mallocz(s->nb_snapshots * sizeof(QEMUSnapshotInfo));
1852     if (!sn_tab)
1853         goto fail;
1854     for(i = 0; i < s->nb_snapshots; i++) {
1855         sn_info = sn_tab + i;
1856         sn = s->snapshots + i;
1857         pstrcpy(sn_info->id_str, sizeof(sn_info->id_str),
1858                 sn->id_str);
1859         pstrcpy(sn_info->name, sizeof(sn_info->name),
1860                 sn->name);
1861         sn_info->vm_state_size = sn->vm_state_size;
1862         sn_info->date_sec = sn->date_sec;
1863         sn_info->date_nsec = sn->date_nsec;
1864         sn_info->vm_clock_nsec = sn->vm_clock_nsec;
1865     }
1866     *psn_tab = sn_tab;
1867     return s->nb_snapshots;
1868  fail:
1869     qemu_free(sn_tab);
1870     *psn_tab = NULL;
1871     return -ENOMEM;
1872 }
1873
1874 /*********************************************************/
1875 /* refcount handling */
1876
1877 static int refcount_init(BlockDriverState *bs)
1878 {
1879     BDRVQcowState *s = bs->opaque;
1880     int ret, refcount_table_size2, i;
1881
1882     s->refcount_block_cache = qemu_malloc(s->cluster_size);
1883     if (!s->refcount_block_cache)
1884         goto fail;
1885     refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
1886     s->refcount_table = qemu_malloc(refcount_table_size2);
1887     if (!s->refcount_table)
1888         goto fail;
1889     if (s->refcount_table_size > 0) {
1890         ret = bdrv_pread(s->hd, s->refcount_table_offset,
1891                          s->refcount_table, refcount_table_size2);
1892         if (ret != refcount_table_size2)
1893             goto fail;
1894         for(i = 0; i < s->refcount_table_size; i++)
1895             be64_to_cpus(&s->refcount_table[i]);
1896     }
1897     return 0;
1898  fail:
1899     return -ENOMEM;
1900 }
1901
1902 static void refcount_close(BlockDriverState *bs)
1903 {
1904     BDRVQcowState *s = bs->opaque;
1905     qemu_free(s->refcount_block_cache);
1906     qemu_free(s->refcount_table);
1907 }
1908
1909
1910 static int load_refcount_block(BlockDriverState *bs,
1911                                int64_t refcount_block_offset)
1912 {
1913     BDRVQcowState *s = bs->opaque;
1914     int ret;
1915     ret = bdrv_pread(s->hd, refcount_block_offset, s->refcount_block_cache,
1916                      s->cluster_size);
1917     if (ret != s->cluster_size)
1918         return -EIO;
1919     s->refcount_block_cache_offset = refcount_block_offset;
1920     return 0;
1921 }
1922
1923 static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
1924 {
1925     BDRVQcowState *s = bs->opaque;
1926     int refcount_table_index, block_index;
1927     int64_t refcount_block_offset;
1928
1929     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
1930     if (refcount_table_index >= s->refcount_table_size)
1931         return 0;
1932     refcount_block_offset = s->refcount_table[refcount_table_index];
1933     if (!refcount_block_offset)
1934         return 0;
1935     if (refcount_block_offset != s->refcount_block_cache_offset) {
1936         /* better than nothing: return allocated if read error */
1937         if (load_refcount_block(bs, refcount_block_offset) < 0)
1938             return 1;
1939     }
1940     block_index = cluster_index &
1941         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
1942     return be16_to_cpu(s->refcount_block_cache[block_index]);
1943 }
1944
1945 /* return < 0 if error */
1946 static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
1947 {
1948     BDRVQcowState *s = bs->opaque;
1949     int i, nb_clusters;
1950
1951     nb_clusters = (size + s->cluster_size - 1) >> s->cluster_bits;
1952     for(;;) {
1953         if (get_refcount(bs, s->free_cluster_index) == 0) {
1954             s->free_cluster_index++;
1955             for(i = 1; i < nb_clusters; i++) {
1956                 if (get_refcount(bs, s->free_cluster_index) != 0)
1957                     goto not_found;
1958                 s->free_cluster_index++;
1959             }
1960 #ifdef DEBUG_ALLOC2
1961             printf("alloc_clusters: size=%lld -> %lld\n",
1962                    size,
1963                    (s->free_cluster_index - nb_clusters) << s->cluster_bits);
1964 #endif
1965             return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
1966         } else {
1967         not_found:
1968             s->free_cluster_index++;
1969         }
1970     }
1971 }
1972
1973 static int64_t alloc_clusters(BlockDriverState *bs, int64_t size)
1974 {
1975     int64_t offset;
1976
1977     offset = alloc_clusters_noref(bs, size);
1978     update_refcount(bs, offset, size, 1);
1979     return offset;
1980 }
1981
1982 /* only used to allocate compressed sectors. We try to allocate
1983    contiguous sectors. size must be <= cluster_size */
1984 static int64_t alloc_bytes(BlockDriverState *bs, int size)
1985 {
1986     BDRVQcowState *s = bs->opaque;
1987     int64_t offset, cluster_offset;
1988     int free_in_cluster;
1989
1990     assert(size > 0 && size <= s->cluster_size);
1991     if (s->free_byte_offset == 0) {
1992         s->free_byte_offset = alloc_clusters(bs, s->cluster_size);
1993     }
1994  redo:
1995     free_in_cluster = s->cluster_size -
1996         (s->free_byte_offset & (s->cluster_size - 1));
1997     if (size <= free_in_cluster) {
1998         /* enough space in current cluster */
1999         offset = s->free_byte_offset;
2000         s->free_byte_offset += size;
2001         free_in_cluster -= size;
2002         if (free_in_cluster == 0)
2003             s->free_byte_offset = 0;
2004         if ((offset & (s->cluster_size - 1)) != 0)
2005             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
2006     } else {
2007         offset = alloc_clusters(bs, s->cluster_size);
2008         cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
2009         if ((cluster_offset + s->cluster_size) == offset) {
2010             /* we are lucky: contiguous data */
2011             offset = s->free_byte_offset;
2012             update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
2013             s->free_byte_offset += size;
2014         } else {
2015             s->free_byte_offset = offset;
2016             goto redo;
2017         }
2018     }
2019     return offset;
2020 }
2021
2022 static void free_clusters(BlockDriverState *bs,
2023                           int64_t offset, int64_t size)
2024 {
2025     update_refcount(bs, offset, size, -1);
2026 }
2027
2028 static int grow_refcount_table(BlockDriverState *bs, int min_size)
2029 {
2030     BDRVQcowState *s = bs->opaque;
2031     int new_table_size, new_table_size2, refcount_table_clusters, i, ret;
2032     uint64_t *new_table;
2033     int64_t table_offset;
2034     uint64_t data64;
2035     uint32_t data32;
2036     int old_table_size;
2037     int64_t old_table_offset;
2038
2039     if (min_size <= s->refcount_table_size)
2040         return 0;
2041     /* compute new table size */
2042     refcount_table_clusters = s->refcount_table_size >> (s->cluster_bits - 3);
2043     for(;;) {
2044         if (refcount_table_clusters == 0) {
2045             refcount_table_clusters = 1;
2046         } else {
2047             refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
2048         }
2049         new_table_size = refcount_table_clusters << (s->cluster_bits - 3);
2050         if (min_size <= new_table_size)
2051             break;
2052     }
2053 #ifdef DEBUG_ALLOC2
2054     printf("grow_refcount_table from %d to %d\n",
2055            s->refcount_table_size,
2056            new_table_size);
2057 #endif
2058     new_table_size2 = new_table_size * sizeof(uint64_t);
2059     new_table = qemu_mallocz(new_table_size2);
2060     if (!new_table)
2061         return -ENOMEM;
2062     memcpy(new_table, s->refcount_table,
2063            s->refcount_table_size * sizeof(uint64_t));
2064     for(i = 0; i < s->refcount_table_size; i++)
2065         cpu_to_be64s(&new_table[i]);
2066     /* Note: we cannot update the refcount now to avoid recursion */
2067     table_offset = alloc_clusters_noref(bs, new_table_size2);
2068     ret = bdrv_pwrite(s->hd, table_offset, new_table, new_table_size2);
2069     if (ret != new_table_size2)
2070         goto fail;
2071     for(i = 0; i < s->refcount_table_size; i++)
2072         be64_to_cpus(&new_table[i]);
2073
2074     data64 = cpu_to_be64(table_offset);
2075     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, refcount_table_offset),
2076                     &data64, sizeof(data64)) != sizeof(data64))
2077         goto fail;
2078     data32 = cpu_to_be32(refcount_table_clusters);
2079     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, refcount_table_clusters),
2080                     &data32, sizeof(data32)) != sizeof(data32))
2081         goto fail;
2082     qemu_free(s->refcount_table);
2083     old_table_offset = s->refcount_table_offset;
2084     old_table_size = s->refcount_table_size;
2085     s->refcount_table = new_table;
2086     s->refcount_table_size = new_table_size;
2087     s->refcount_table_offset = table_offset;
2088
2089     update_refcount(bs, table_offset, new_table_size2, 1);
2090     free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
2091     return 0;
2092  fail:
2093     free_clusters(bs, table_offset, new_table_size2);
2094     qemu_free(new_table);
2095     return -EIO;
2096 }
2097
2098 /* addend must be 1 or -1 */
2099 /* XXX: cache several refcount block clusters ? */
2100 static int update_cluster_refcount(BlockDriverState *bs,
2101                                    int64_t cluster_index,
2102                                    int addend)
2103 {
2104     BDRVQcowState *s = bs->opaque;
2105     int64_t offset, refcount_block_offset;
2106     int ret, refcount_table_index, block_index, refcount;
2107     uint64_t data64;
2108
2109     refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
2110     if (refcount_table_index >= s->refcount_table_size) {
2111         if (addend < 0)
2112             return -EINVAL;
2113         ret = grow_refcount_table(bs, refcount_table_index + 1);
2114         if (ret < 0)
2115             return ret;
2116     }
2117     refcount_block_offset = s->refcount_table[refcount_table_index];
2118     if (!refcount_block_offset) {
2119         if (addend < 0)
2120             return -EINVAL;
2121         /* create a new refcount block */
2122         /* Note: we cannot update the refcount now to avoid recursion */
2123         offset = alloc_clusters_noref(bs, s->cluster_size);
2124         memset(s->refcount_block_cache, 0, s->cluster_size);
2125         ret = bdrv_pwrite(s->hd, offset, s->refcount_block_cache, s->cluster_size);
2126         if (ret != s->cluster_size)
2127             return -EINVAL;
2128         s->refcount_table[refcount_table_index] = offset;
2129         data64 = cpu_to_be64(offset);
2130         ret = bdrv_pwrite(s->hd, s->refcount_table_offset +
2131                           refcount_table_index * sizeof(uint64_t),
2132                           &data64, sizeof(data64));
2133         if (ret != sizeof(data64))
2134             return -EINVAL;
2135
2136         refcount_block_offset = offset;
2137         s->refcount_block_cache_offset = offset;
2138         update_refcount(bs, offset, s->cluster_size, 1);
2139     } else {
2140         if (refcount_block_offset != s->refcount_block_cache_offset) {
2141             if (load_refcount_block(bs, refcount_block_offset) < 0)
2142                 return -EIO;
2143         }
2144     }
2145     /* we can update the count and save it */
2146     block_index = cluster_index &
2147         ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
2148     refcount = be16_to_cpu(s->refcount_block_cache[block_index]);
2149     refcount += addend;
2150     if (refcount < 0 || refcount > 0xffff)
2151         return -EINVAL;
2152     if (refcount == 0 && cluster_index < s->free_cluster_index) {
2153         s->free_cluster_index = cluster_index;
2154     }
2155     s->refcount_block_cache[block_index] = cpu_to_be16(refcount);
2156     if (bdrv_pwrite(s->hd,
2157                     refcount_block_offset + (block_index << REFCOUNT_SHIFT),
2158                     &s->refcount_block_cache[block_index], 2) != 2)
2159         return -EIO;
2160     return refcount;
2161 }
2162
2163 static void update_refcount(BlockDriverState *bs,
2164                             int64_t offset, int64_t length,
2165                             int addend)
2166 {
2167     BDRVQcowState *s = bs->opaque;
2168     int64_t start, last, cluster_offset;
2169
2170 #ifdef DEBUG_ALLOC2
2171     printf("update_refcount: offset=%lld size=%lld addend=%d\n",
2172            offset, length, addend);
2173 #endif
2174     if (length <= 0)
2175         return;
2176     start = offset & ~(s->cluster_size - 1);
2177     last = (offset + length - 1) & ~(s->cluster_size - 1);
2178     for(cluster_offset = start; cluster_offset <= last;
2179         cluster_offset += s->cluster_size) {
2180         update_cluster_refcount(bs, cluster_offset >> s->cluster_bits, addend);
2181     }
2182 }
2183
2184 #ifdef DEBUG_ALLOC
2185 static void inc_refcounts(BlockDriverState *bs,
2186                           uint16_t *refcount_table,
2187                           int refcount_table_size,
2188                           int64_t offset, int64_t size)
2189 {
2190     BDRVQcowState *s = bs->opaque;
2191     int64_t start, last, cluster_offset;
2192     int k;
2193
2194     if (size <= 0)
2195         return;
2196
2197     start = offset & ~(s->cluster_size - 1);
2198     last = (offset + size - 1) & ~(s->cluster_size - 1);
2199     for(cluster_offset = start; cluster_offset <= last;
2200         cluster_offset += s->cluster_size) {
2201         k = cluster_offset >> s->cluster_bits;
2202         if (k < 0 || k >= refcount_table_size) {
2203             printf("ERROR: invalid cluster offset=0x%llx\n", cluster_offset);
2204         } else {
2205             if (++refcount_table[k] == 0) {
2206                 printf("ERROR: overflow cluster offset=0x%llx\n", cluster_offset);
2207             }
2208         }
2209     }
2210 }
2211
2212 static int check_refcounts_l1(BlockDriverState *bs,
2213                               uint16_t *refcount_table,
2214                               int refcount_table_size,
2215                               int64_t l1_table_offset, int l1_size,
2216                               int check_copied)
2217 {
2218     BDRVQcowState *s = bs->opaque;
2219     uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2;
2220     int l2_size, i, j, nb_csectors, refcount;
2221
2222     l2_table = NULL;
2223     l1_size2 = l1_size * sizeof(uint64_t);
2224
2225     inc_refcounts(bs, refcount_table, refcount_table_size,
2226                   l1_table_offset, l1_size2);
2227
2228     l1_table = qemu_malloc(l1_size2);
2229     if (!l1_table)
2230         goto fail;
2231     if (bdrv_pread(s->hd, l1_table_offset,
2232                    l1_table, l1_size2) != l1_size2)
2233         goto fail;
2234     for(i = 0;i < l1_size; i++)
2235         be64_to_cpus(&l1_table[i]);
2236
2237     l2_size = s->l2_size * sizeof(uint64_t);
2238     l2_table = qemu_malloc(l2_size);
2239     if (!l2_table)
2240         goto fail;
2241     for(i = 0; i < l1_size; i++) {
2242         l2_offset = l1_table[i];
2243         if (l2_offset) {
2244             if (check_copied) {
2245                 refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED) >> s->cluster_bits);
2246                 if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
2247                     printf("ERROR OFLAG_COPIED: l2_offset=%llx refcount=%d\n",
2248                            l2_offset, refcount);
2249                 }
2250             }
2251             l2_offset &= ~QCOW_OFLAG_COPIED;
2252             if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
2253                 goto fail;
2254             for(j = 0; j < s->l2_size; j++) {
2255                 offset = be64_to_cpu(l2_table[j]);
2256                 if (offset != 0) {
2257                     if (offset & QCOW_OFLAG_COMPRESSED) {
2258                         if (offset & QCOW_OFLAG_COPIED) {
2259                             printf("ERROR: cluster %lld: copied flag must never be set for compressed clusters\n",
2260                                    offset >> s->cluster_bits);
2261                             offset &= ~QCOW_OFLAG_COPIED;
2262                         }
2263                         nb_csectors = ((offset >> s->csize_shift) &
2264                                        s->csize_mask) + 1;
2265                         offset &= s->cluster_offset_mask;
2266                         inc_refcounts(bs, refcount_table,
2267                                       refcount_table_size,
2268                                       offset & ~511, nb_csectors * 512);
2269                     } else {
2270                         if (check_copied) {
2271                             refcount = get_refcount(bs, (offset & ~QCOW_OFLAG_COPIED) >> s->cluster_bits);
2272                             if ((refcount == 1) != ((offset & QCOW_OFLAG_COPIED) != 0)) {
2273                                 printf("ERROR OFLAG_COPIED: offset=%llx refcount=%d\n",
2274                                        offset, refcount);
2275                             }
2276                         }
2277                         offset &= ~QCOW_OFLAG_COPIED;
2278                         inc_refcounts(bs, refcount_table,
2279                                       refcount_table_size,
2280                                       offset, s->cluster_size);
2281                     }
2282                 }
2283             }
2284             inc_refcounts(bs, refcount_table,
2285                           refcount_table_size,
2286                           l2_offset,
2287                           s->cluster_size);
2288         }
2289     }
2290     qemu_free(l1_table);
2291     qemu_free(l2_table);
2292     return 0;
2293  fail:
2294     printf("ERROR: I/O error in check_refcounts_l1\n");
2295     qemu_free(l1_table);
2296     qemu_free(l2_table);
2297     return -EIO;
2298 }
2299
2300 static void check_refcounts(BlockDriverState *bs)
2301 {
2302     BDRVQcowState *s = bs->opaque;
2303     int64_t size;
2304     int nb_clusters, refcount1, refcount2, i;
2305     QCowSnapshot *sn;
2306     uint16_t *refcount_table;
2307
2308     size = bdrv_getlength(s->hd);
2309     nb_clusters = (size + s->cluster_size - 1) >> s->cluster_bits;
2310     refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
2311
2312     /* header */
2313     inc_refcounts(bs, refcount_table, nb_clusters,
2314                   0, s->cluster_size);
2315
2316     check_refcounts_l1(bs, refcount_table, nb_clusters,
2317                        s->l1_table_offset, s->l1_size, 1);
2318
2319     /* snapshots */
2320     for(i = 0; i < s->nb_snapshots; i++) {
2321         sn = s->snapshots + i;
2322         check_refcounts_l1(bs, refcount_table, nb_clusters,
2323                            sn->l1_table_offset, sn->l1_size, 0);
2324     }
2325     inc_refcounts(bs, refcount_table, nb_clusters,
2326                   s->snapshots_offset, s->snapshots_size);
2327
2328     /* refcount data */
2329     inc_refcounts(bs, refcount_table, nb_clusters,
2330                   s->refcount_table_offset,
2331                   s->refcount_table_size * sizeof(uint64_t));
2332     for(i = 0; i < s->refcount_table_size; i++) {
2333         int64_t offset;
2334         offset = s->refcount_table[i];
2335         if (offset != 0) {
2336             inc_refcounts(bs, refcount_table, nb_clusters,
2337                           offset, s->cluster_size);
2338         }
2339     }
2340
2341     /* compare ref counts */
2342     for(i = 0; i < nb_clusters; i++) {
2343         refcount1 = get_refcount(bs, i);
2344         refcount2 = refcount_table[i];
2345         if (refcount1 != refcount2)
2346             printf("ERROR cluster %d refcount=%d reference=%d\n",
2347                    i, refcount1, refcount2);
2348     }
2349
2350     qemu_free(refcount_table);
2351 }
2352
2353 #if 0
2354 static void dump_refcounts(BlockDriverState *bs)
2355 {
2356     BDRVQcowState *s = bs->opaque;
2357     int64_t nb_clusters, k, k1, size;
2358     int refcount;
2359
2360     size = bdrv_getlength(s->hd);
2361     nb_clusters = (size + s->cluster_size - 1) >> s->cluster_bits;
2362     for(k = 0; k < nb_clusters;) {
2363         k1 = k;
2364         refcount = get_refcount(bs, k);
2365         k++;
2366         while (k < nb_clusters && get_refcount(bs, k) == refcount)
2367             k++;
2368         printf("%lld: refcount=%d nb=%lld\n", k, refcount, k - k1);
2369     }
2370 }
2371 #endif
2372 #endif
2373
2374 BlockDriver bdrv_qcow2 = {
2375     "qcow2",
2376     sizeof(BDRVQcowState),
2377     qcow_probe,
2378     qcow_open,
2379     NULL,
2380     NULL,
2381     qcow_close,
2382     qcow_create,
2383     qcow_flush,
2384     qcow_is_allocated,
2385     qcow_set_key,
2386     qcow_make_empty,
2387
2388     .bdrv_aio_read = qcow_aio_read,
2389     .bdrv_aio_write = qcow_aio_write,
2390     .bdrv_aio_cancel = qcow_aio_cancel,
2391     .aiocb_size = sizeof(QCowAIOCB),
2392     .bdrv_write_compressed = qcow_write_compressed,
2393
2394     .bdrv_snapshot_create = qcow_snapshot_create,
2395     .bdrv_snapshot_goto = qcow_snapshot_goto,
2396     .bdrv_snapshot_delete = qcow_snapshot_delete,
2397     .bdrv_snapshot_list = qcow_snapshot_list,
2398     .bdrv_get_info = qcow_get_info,
2399 };