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