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