git.maemo.org Git - qemu/blob - block-qcow2.c

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