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