1 /*

     2  * Block driver for the QCOW version 2 format

     3  *

     4  * Copyright (c) 2004-2006 Fabrice Bellard

     5  *

     6  * Permission is hereby granted, free of charge, to any person obtaining a copy

     7  * of this software and associated documentation files (the "Software"), to deal

     8  * in the Software without restriction, including without limitation the rights

     9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

    10  * copies of the Software, and to permit persons to whom the Software is

    11  * furnished to do so, subject to the following conditions:

    12  *

    13  * The above copyright notice and this permission notice shall be included in

    14  * all copies or substantial portions of the Software.

    15  *

    16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

    17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

    18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL

    19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

    20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

    21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

    22  * THE SOFTWARE.

    23  */

    24 #include "qemu-common.h"

    25 #include "block_int.h"

    26 #include <zlib.h>

    27 #include "aes.h"

    28 #include <assert.h>

    29 

    30 /*

    31   Differences with QCOW:

    32 

    33   - Support for multiple incremental snapshots.

    34   - Memory management by reference counts.

    35   - Clusters which have a reference count of one have the bit

    36     QCOW_OFLAG_COPIED to optimize write performance.

    37   - Size of compressed clusters is stored in sectors to reduce bit usage

    38     in the cluster offsets.

    39   - Support for storing additional data (such as the VM state) in the

    40     snapshots.

    41   - If a backing store is used, the cluster size is not constrained

    42     (could be backported to QCOW).

    43   - L2 tables have always a size of one cluster.

    44 */

    45 

    46 //#define DEBUG_ALLOC

    47 //#define DEBUG_ALLOC2

    48 

    49 #define QCOW_MAGIC (('Q' << 24) | ('F' << 16) | ('I' << 8) | 0xfb)

    50 #define QCOW_VERSION 2

    51 

    52 #define QCOW_CRYPT_NONE 0

    53 #define QCOW_CRYPT_AES  1

    54 

    55 #define QCOW_MAX_CRYPT_CLUSTERS 32

    56 

    57 /* indicate that the refcount of the referenced cluster is exactly one. */

    58 #define QCOW_OFLAG_COPIED     (1LL << 63)

    59 /* indicate that the cluster is compressed (they never have the copied flag) */

    60 #define QCOW_OFLAG_COMPRESSED (1LL << 62)

    61 

    62 #define REFCOUNT_SHIFT 1 /* refcount size is 2 bytes */

    63 

    64 typedef struct QCowHeader {

    65     uint32_t magic;

    66     uint32_t version;

    67     uint64_t backing_file_offset;

    68     uint32_t backing_file_size;

    69     uint32_t cluster_bits;

    70     uint64_t size; /* in bytes */

    71     uint32_t crypt_method;

    72     uint32_t l1_size; /* XXX: save number of clusters instead ? */

    73     uint64_t l1_table_offset;

    74     uint64_t refcount_table_offset;

    75     uint32_t refcount_table_clusters;

    76     uint32_t nb_snapshots;

    77     uint64_t snapshots_offset;

    78 } QCowHeader;

    79 

    80 typedef struct __attribute__((packed)) QCowSnapshotHeader {

    81     /* header is 8 byte aligned */

    82     uint64_t l1_table_offset;

    83 

    84     uint32_t l1_size;

    85     uint16_t id_str_size;

    86     uint16_t name_size;

    87 

    88     uint32_t date_sec;

    89     uint32_t date_nsec;

    90 

    91     uint64_t vm_clock_nsec;

    92 

    93     uint32_t vm_state_size;

    94     uint32_t extra_data_size; /* for extension */

    95     /* extra data follows */

    96     /* id_str follows */

    97     /* name follows  */

    98 } QCowSnapshotHeader;

    99 

   100 #define L2_CACHE_SIZE 16

   101 

   102 typedef struct QCowSnapshot {

   103     uint64_t l1_table_offset;

   104     uint32_t l1_size;

   105     char *id_str;

   106     char *name;

   107     uint32_t vm_state_size;

   108     uint32_t date_sec;

   109     uint32_t date_nsec;

   110     uint64_t vm_clock_nsec;

   111 } QCowSnapshot;

   112 

   113 typedef struct BDRVQcowState {

   114     BlockDriverState *hd;

   115     int cluster_bits;

   116     int cluster_size;

   117     int cluster_sectors;

   118     int l2_bits;

   119     int l2_size;

   120     int l1_size;

   121     int l1_vm_state_index;

   122     int csize_shift;

   123     int csize_mask;

   124     uint64_t cluster_offset_mask;

   125     uint64_t l1_table_offset;

   126     uint64_t *l1_table;

   127     uint64_t *l2_cache;

   128     uint64_t l2_cache_offsets[L2_CACHE_SIZE];

   129     uint32_t l2_cache_counts[L2_CACHE_SIZE];

   130     uint8_t *cluster_cache;

   131     uint8_t *cluster_data;

   132     uint64_t cluster_cache_offset;

   133 

   134     uint64_t *refcount_table;

   135     uint64_t refcount_table_offset;

   136     uint32_t refcount_table_size;

   137     uint64_t refcount_block_cache_offset;

   138     uint16_t *refcount_block_cache;

   139     int64_t free_cluster_index;

   140     int64_t free_byte_offset;

   141 

   142     uint32_t crypt_method; /* current crypt method, 0 if no key yet */

   143     uint32_t crypt_method_header;

   144     AES_KEY aes_encrypt_key;

   145     AES_KEY aes_decrypt_key;

   146     uint64_t snapshots_offset;

   147     int snapshots_size;

   148     int nb_snapshots;

   149     QCowSnapshot *snapshots;

   150 } BDRVQcowState;

   151 

   152 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset);

   153 static int qcow_read(BlockDriverState *bs, int64_t sector_num,

   154                      uint8_t *buf, int nb_sectors);

   155 static int qcow_read_snapshots(BlockDriverState *bs);

   156 static void qcow_free_snapshots(BlockDriverState *bs);

   157 static int refcount_init(BlockDriverState *bs);

   158 static void refcount_close(BlockDriverState *bs);

   159 static int get_refcount(BlockDriverState *bs, int64_t cluster_index);

   160 static int update_cluster_refcount(BlockDriverState *bs,

   161                                    int64_t cluster_index,

   162                                    int addend);

   163 static void update_refcount(BlockDriverState *bs,

   164                             int64_t offset, int64_t length,

   165                             int addend);

   166 static int64_t alloc_clusters(BlockDriverState *bs, int64_t size);

   167 static int64_t alloc_bytes(BlockDriverState *bs, int size);

   168 static void free_clusters(BlockDriverState *bs,

   169                           int64_t offset, int64_t size);

   170 #ifdef DEBUG_ALLOC

   171 static void check_refcounts(BlockDriverState *bs);

   172 #endif

   173 

   174 static int qcow_probe(const uint8_t *buf, int buf_size, const char *filename)

   175 {

   176     const QCowHeader *cow_header = (const void *)buf;

   177 

   178     if (buf_size >= sizeof(QCowHeader) &&

   179         be32_to_cpu(cow_header->magic) == QCOW_MAGIC &&

   180         be32_to_cpu(cow_header->version) == QCOW_VERSION)

   181         return 100;

   182     else

   183         return 0;

   184 }

   185 

   186 static int qcow_open(BlockDriverState *bs, const char *filename, int flags)

   187 {

   188     BDRVQcowState *s = bs->opaque;

   189     int len, i, shift, ret;

   190     QCowHeader header;

   191 

   192     /* Performance is terrible right now with cache=writethrough due mainly

   193      * to reference count updates.  If the user does not explicitly specify

   194      * a caching type, force to writeback caching.

   195      */

   196     if ((flags & BDRV_O_CACHE_DEF)) {

   197         flags |= BDRV_O_CACHE_WB;

   198         flags &= ~BDRV_O_CACHE_DEF;

   199     }

   200     ret = bdrv_file_open(&s->hd, filename, flags);

   201     if (ret < 0)

   202         return ret;

   203     if (bdrv_pread(s->hd, 0, &header, sizeof(header)) != sizeof(header))

   204         goto fail;

   205     be32_to_cpus(&header.magic);

   206     be32_to_cpus(&header.version);

   207     be64_to_cpus(&header.backing_file_offset);

   208     be32_to_cpus(&header.backing_file_size);

   209     be64_to_cpus(&header.size);

   210     be32_to_cpus(&header.cluster_bits);

   211     be32_to_cpus(&header.crypt_method);

   212     be64_to_cpus(&header.l1_table_offset);

   213     be32_to_cpus(&header.l1_size);

   214     be64_to_cpus(&header.refcount_table_offset);

   215     be32_to_cpus(&header.refcount_table_clusters);

   216     be64_to_cpus(&header.snapshots_offset);

   217     be32_to_cpus(&header.nb_snapshots);

   218 

   219     if (header.magic != QCOW_MAGIC || header.version != QCOW_VERSION)

   220         goto fail;

   221     if (header.size <= 1 ||

   222         header.cluster_bits < 9 ||

   223         header.cluster_bits > 16)

   224         goto fail;

   225     if (header.crypt_method > QCOW_CRYPT_AES)

   226         goto fail;

   227     s->crypt_method_header = header.crypt_method;

   228     if (s->crypt_method_header)

   229         bs->encrypted = 1;

   230     s->cluster_bits = header.cluster_bits;

   231     s->cluster_size = 1 << s->cluster_bits;

   232     s->cluster_sectors = 1 << (s->cluster_bits - 9);

   233     s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */

   234     s->l2_size = 1 << s->l2_bits;

   235     bs->total_sectors = header.size / 512;

   236     s->csize_shift = (62 - (s->cluster_bits - 8));

   237     s->csize_mask = (1 << (s->cluster_bits - 8)) - 1;

   238     s->cluster_offset_mask = (1LL << s->csize_shift) - 1;

   239     s->refcount_table_offset = header.refcount_table_offset;

   240     s->refcount_table_size =

   241         header.refcount_table_clusters << (s->cluster_bits - 3);

   242 

   243     s->snapshots_offset = header.snapshots_offset;

   244     s->nb_snapshots = header.nb_snapshots;

   245 

   246     /* read the level 1 table */

   247     s->l1_size = header.l1_size;

   248     shift = s->cluster_bits + s->l2_bits;

   249     s->l1_vm_state_index = (header.size + (1LL << shift) - 1) >> shift;

   250     /* the L1 table must contain at least enough entries to put

   251        header.size bytes */

   252     if (s->l1_size < s->l1_vm_state_index)

   253         goto fail;

   254     s->l1_table_offset = header.l1_table_offset;

   255     s->l1_table = qemu_malloc(s->l1_size * sizeof(uint64_t));

   256     if (!s->l1_table)

   257         goto fail;

   258     if (bdrv_pread(s->hd, s->l1_table_offset, s->l1_table, s->l1_size * sizeof(uint64_t)) !=

   259         s->l1_size * sizeof(uint64_t))

   260         goto fail;

   261     for(i = 0;i < s->l1_size; i++) {

   262         be64_to_cpus(&s->l1_table[i]);

   263     }

   264     /* alloc L2 cache */

   265     s->l2_cache = qemu_malloc(s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t));

   266     if (!s->l2_cache)

   267         goto fail;

   268     s->cluster_cache = qemu_malloc(s->cluster_size);

   269     if (!s->cluster_cache)

   270         goto fail;

   271     /* one more sector for decompressed data alignment */

   272     s->cluster_data = qemu_malloc(QCOW_MAX_CRYPT_CLUSTERS * s->cluster_size

   273                                   + 512);

   274     if (!s->cluster_data)

   275         goto fail;

   276     s->cluster_cache_offset = -1;

   277 

   278     if (refcount_init(bs) < 0)

   279         goto fail;

   280 

   281     /* read the backing file name */

   282     if (header.backing_file_offset != 0) {

   283         len = header.backing_file_size;

   284         if (len > 1023)

   285             len = 1023;

   286         if (bdrv_pread(s->hd, header.backing_file_offset, bs->backing_file, len) != len)

   287             goto fail;

   288         bs->backing_file[len] = '\0';

   289     }

   290     if (qcow_read_snapshots(bs) < 0)

   291         goto fail;

   292 

   293 #ifdef DEBUG_ALLOC

   294     check_refcounts(bs);

   295 #endif

   296     return 0;

   297 

   298  fail:

   299     qcow_free_snapshots(bs);

   300     refcount_close(bs);

   301     qemu_free(s->l1_table);

   302     qemu_free(s->l2_cache);

   303     qemu_free(s->cluster_cache);

   304     qemu_free(s->cluster_data);

   305     bdrv_delete(s->hd);

   306     return -1;

   307 }

   308 

   309 static int qcow_set_key(BlockDriverState *bs, const char *key)

   310 {

   311     BDRVQcowState *s = bs->opaque;

   312     uint8_t keybuf[16];

   313     int len, i;

   314 

   315     memset(keybuf, 0, 16);

   316     len = strlen(key);

   317     if (len > 16)

   318         len = 16;

   319     /* XXX: we could compress the chars to 7 bits to increase

   320        entropy */

   321     for(i = 0;i < len;i++) {

   322         keybuf[i] = key[i];

   323     }

   324     s->crypt_method = s->crypt_method_header;

   325 

   326     if (AES_set_encrypt_key(keybuf, 128, &s->aes_encrypt_key) != 0)

   327         return -1;

   328     if (AES_set_decrypt_key(keybuf, 128, &s->aes_decrypt_key) != 0)

   329         return -1;

   330 #if 0

   331     /* test */

   332     {

   333         uint8_t in[16];

   334         uint8_t out[16];

   335         uint8_t tmp[16];

   336         for(i=0;i<16;i++)

   337             in[i] = i;

   338         AES_encrypt(in, tmp, &s->aes_encrypt_key);

   339         AES_decrypt(tmp, out, &s->aes_decrypt_key);

   340         for(i = 0; i < 16; i++)

   341             printf(" %02x", tmp[i]);

   342         printf("\n");

   343         for(i = 0; i < 16; i++)

   344             printf(" %02x", out[i]);

   345         printf("\n");

   346     }

   347 #endif

   348     return 0;

   349 }

   350 

   351 /* The crypt function is compatible with the linux cryptoloop

   352    algorithm for < 4 GB images. NOTE: out_buf == in_buf is

   353    supported */

   354 static void encrypt_sectors(BDRVQcowState *s, int64_t sector_num,

   355                             uint8_t *out_buf, const uint8_t *in_buf,

   356                             int nb_sectors, int enc,

   357                             const AES_KEY *key)

   358 {

   359     union {

   360         uint64_t ll[2];

   361         uint8_t b[16];

   362     } ivec;

   363     int i;

   364 

   365     for(i = 0; i < nb_sectors; i++) {

   366         ivec.ll[0] = cpu_to_le64(sector_num);

   367         ivec.ll[1] = 0;

   368         AES_cbc_encrypt(in_buf, out_buf, 512, key,

   369                         ivec.b, enc);

   370         sector_num++;

   371         in_buf += 512;

   372         out_buf += 512;

   373     }

   374 }

   375 

   376 static int copy_sectors(BlockDriverState *bs, uint64_t start_sect,

   377                         uint64_t cluster_offset, int n_start, int n_end)

   378 {

   379     BDRVQcowState *s = bs->opaque;

   380     int n, ret;

   381 

   382     n = n_end - n_start;

   383     if (n <= 0)

   384         return 0;

   385     ret = qcow_read(bs, start_sect + n_start, s->cluster_data, n);

   386     if (ret < 0)

   387         return ret;

   388     if (s->crypt_method) {

   389         encrypt_sectors(s, start_sect + n_start,

   390                         s->cluster_data,

   391                         s->cluster_data, n, 1,

   392                         &s->aes_encrypt_key);

   393     }

   394     ret = bdrv_write(s->hd, (cluster_offset >> 9) + n_start,

   395                      s->cluster_data, n);

   396     if (ret < 0)

   397         return ret;

   398     return 0;

   399 }

   400 

   401 static void l2_cache_reset(BlockDriverState *bs)

   402 {

   403     BDRVQcowState *s = bs->opaque;

   404 

   405     memset(s->l2_cache, 0, s->l2_size * L2_CACHE_SIZE * sizeof(uint64_t));

   406     memset(s->l2_cache_offsets, 0, L2_CACHE_SIZE * sizeof(uint64_t));

   407     memset(s->l2_cache_counts, 0, L2_CACHE_SIZE * sizeof(uint32_t));

   408 }

   409 

   410 static inline int l2_cache_new_entry(BlockDriverState *bs)

   411 {

   412     BDRVQcowState *s = bs->opaque;

   413     uint32_t min_count;

   414     int min_index, i;

   415 

   416     /* find a new entry in the least used one */

   417     min_index = 0;

   418     min_count = 0xffffffff;

   419     for(i = 0; i < L2_CACHE_SIZE; i++) {

   420         if (s->l2_cache_counts[i] < min_count) {

   421             min_count = s->l2_cache_counts[i];

   422             min_index = i;

   423         }

   424     }

   425     return min_index;

   426 }

   427 

   428 static int64_t align_offset(int64_t offset, int n)

   429 {

   430     offset = (offset + n - 1) & ~(n - 1);

   431     return offset;

   432 }

   433 

   434 static int grow_l1_table(BlockDriverState *bs, int min_size)

   435 {

   436     BDRVQcowState *s = bs->opaque;

   437     int new_l1_size, new_l1_size2, ret, i;

   438     uint64_t *new_l1_table;

   439     uint64_t new_l1_table_offset;

   440     uint8_t data[12];

   441 

   442     new_l1_size = s->l1_size;

   443     if (min_size <= new_l1_size)

   444         return 0;

   445     while (min_size > new_l1_size) {

   446         new_l1_size = (new_l1_size * 3 + 1) / 2;

   447     }

   448 #ifdef DEBUG_ALLOC2

   449     printf("grow l1_table from %d to %d\n", s->l1_size, new_l1_size);

   450 #endif

   451 

   452     new_l1_size2 = sizeof(uint64_t) * new_l1_size;

   453     new_l1_table = qemu_mallocz(new_l1_size2);

   454     if (!new_l1_table)

   455         return -ENOMEM;

   456     memcpy(new_l1_table, s->l1_table, s->l1_size * sizeof(uint64_t));

   457 

   458     /* write new table (align to cluster) */

   459     new_l1_table_offset = alloc_clusters(bs, new_l1_size2);

   460 

   461     for(i = 0; i < s->l1_size; i++)

   462         new_l1_table[i] = cpu_to_be64(new_l1_table[i]);

   463     ret = bdrv_pwrite(s->hd, new_l1_table_offset, new_l1_table, new_l1_size2);

   464     if (ret != new_l1_size2)

   465         goto fail;

   466     for(i = 0; i < s->l1_size; i++)

   467         new_l1_table[i] = be64_to_cpu(new_l1_table[i]);

   468 

   469     /* set new table */

   470     cpu_to_be32w((uint32_t*)data, new_l1_size);

   471     cpu_to_be64w((uint64_t*)(data + 4), new_l1_table_offset);

   472     if (bdrv_pwrite(s->hd, offsetof(QCowHeader, l1_size), data,

   473                 sizeof(data)) != sizeof(data))

   474         goto fail;

   475     qemu_free(s->l1_table);

   476     free_clusters(bs, s->l1_table_offset, s->l1_size * sizeof(uint64_t));

   477     s->l1_table_offset = new_l1_table_offset;

   478     s->l1_table = new_l1_table;

   479     s->l1_size = new_l1_size;

   480     return 0;

   481  fail:

   482     qemu_free(s->l1_table);

   483     return -EIO;

   484 }

   485 

   486 /*

   487  * seek_l2_table

   488  *

   489  * seek l2_offset in the l2_cache table

   490  * if not found, return NULL,

   491  * if found,

   492  *   increments the l2 cache hit count of the entry,

   493  *   if counter overflow, divide by two all counters

   494  *   return the pointer to the l2 cache entry

   495  *

   496  */

   497 

   498 static uint64_t *seek_l2_table(BDRVQcowState *s, uint64_t l2_offset)

   499 {

   500     int i, j;

   501 

   502     for(i = 0; i < L2_CACHE_SIZE; i++) {

   503         if (l2_offset == s->l2_cache_offsets[i]) {

   504             /* increment the hit count */

   505             if (++s->l2_cache_counts[i] == 0xffffffff) {

   506                 for(j = 0; j < L2_CACHE_SIZE; j++) {

   507                     s->l2_cache_counts[j] >>= 1;

   508                 }

   509             }

   510             return s->l2_cache + (i << s->l2_bits);

   511         }

   512     }

   513     return NULL;

   514 }

   515 

   516 /*

   517  * l2_load

   518  *

   519  * Loads a L2 table into memory. If the table is in the cache, the cache

   520  * is used; otherwise the L2 table is loaded from the image file.

   521  *

   522  * Returns a pointer to the L2 table on success, or NULL if the read from

   523  * the image file failed.

   524  */

   525 

   526 static uint64_t *l2_load(BlockDriverState *bs, uint64_t l2_offset)

   527 {

   528     BDRVQcowState *s = bs->opaque;

   529     int min_index;

   530     uint64_t *l2_table;

   531 

   532     /* seek if the table for the given offset is in the cache */

   533 

   534     l2_table = seek_l2_table(s, l2_offset);

   535     if (l2_table != NULL)

   536         return l2_table;

   537 

   538     /* not found: load a new entry in the least used one */

   539 

   540     min_index = l2_cache_new_entry(bs);

   541     l2_table = s->l2_cache + (min_index << s->l2_bits);

   542     if (bdrv_pread(s->hd, l2_offset, l2_table, s->l2_size * sizeof(uint64_t)) !=

   543         s->l2_size * sizeof(uint64_t))

   544         return NULL;

   545     s->l2_cache_offsets[min_index] = l2_offset;

   546     s->l2_cache_counts[min_index] = 1;

   547 

   548     return l2_table;

   549 }

   550 

   551 /*

   552  * l2_allocate

   553  *

   554  * Allocate a new l2 entry in the file. If l1_index points to an already

   555  * used entry in the L2 table (i.e. we are doing a copy on write for the L2

   556  * table) copy the contents of the old L2 table into the newly allocated one.

   557  * Otherwise the new table is initialized with zeros.

   558  *

   559  */

   560 

   561 static uint64_t *l2_allocate(BlockDriverState *bs, int l1_index)

   562 {

   563     BDRVQcowState *s = bs->opaque;

   564     int min_index;

   565     uint64_t old_l2_offset, tmp;

   566     uint64_t *l2_table, l2_offset;

   567 

   568     old_l2_offset = s->l1_table[l1_index];

   569 

   570     /* allocate a new l2 entry */

   571 

   572     l2_offset = alloc_clusters(bs, s->l2_size * sizeof(uint64_t));

   573 

   574     /* update the L1 entry */

   575 

   576     s->l1_table[l1_index] = l2_offset | QCOW_OFLAG_COPIED;

   577 

   578     tmp = cpu_to_be64(l2_offset | QCOW_OFLAG_COPIED);

   579     if (bdrv_pwrite(s->hd, s->l1_table_offset + l1_index * sizeof(tmp),

   580                     &tmp, sizeof(tmp)) != sizeof(tmp))

   581         return NULL;

   582 

   583     /* allocate a new entry in the l2 cache */

   584 

   585     min_index = l2_cache_new_entry(bs);

   586     l2_table = s->l2_cache + (min_index << s->l2_bits);

   587 

   588     if (old_l2_offset == 0) {

   589         /* if there was no old l2 table, clear the new table */

   590         memset(l2_table, 0, s->l2_size * sizeof(uint64_t));

   591     } else {

   592         /* if there was an old l2 table, read it from the disk */

   593         if (bdrv_pread(s->hd, old_l2_offset,

   594                        l2_table, s->l2_size * sizeof(uint64_t)) !=

   595             s->l2_size * sizeof(uint64_t))

   596             return NULL;

   597     }

   598     /* write the l2 table to the file */

   599     if (bdrv_pwrite(s->hd, l2_offset,

   600                     l2_table, s->l2_size * sizeof(uint64_t)) !=

   601         s->l2_size * sizeof(uint64_t))

   602         return NULL;

   603 

   604     /* update the l2 cache entry */

   605 

   606     s->l2_cache_offsets[min_index] = l2_offset;

   607     s->l2_cache_counts[min_index] = 1;

   608 

   609     return l2_table;

   610 }

   611 

   612 static int size_to_clusters(BDRVQcowState *s, int64_t size)

   613 {

   614     return (size + (s->cluster_size - 1)) >> s->cluster_bits;

   615 }

   616 

   617 static int count_contiguous_clusters(uint64_t nb_clusters, int cluster_size,

   618         uint64_t *l2_table, uint64_t mask)

   619 {

   620     int i;

   621     uint64_t offset = be64_to_cpu(l2_table[0]) & ~mask;

   622 

   623     for (i = 0; i < nb_clusters; i++)

   624         if (offset + i * cluster_size != (be64_to_cpu(l2_table[i]) & ~mask))

   625             break;

   626 

   627 	return i;

   628 }

   629 

   630 static int count_contiguous_free_clusters(uint64_t nb_clusters, uint64_t *l2_table)

   631 {

   632     int i = 0;

   633 

   634     while(nb_clusters-- && l2_table[i] == 0)

   635         i++;

   636 

   637     return i;

   638 }

   639 

   640 /*

   641  * get_cluster_offset

   642  *

   643  * For a given offset of the disk image, return cluster offset in

   644  * qcow2 file.

   645  *

   646  * on entry, *num is the number of contiguous clusters we'd like to

   647  * access following offset.

   648  *

   649  * on exit, *num is the number of contiguous clusters we can read.

   650  *

   651  * Return 1, if the offset is found

   652  * Return 0, otherwise.

   653  *

   654  */

   655 

   656 static uint64_t get_cluster_offset(BlockDriverState *bs,

   657                                    uint64_t offset, int *num)

   658 {

   659     BDRVQcowState *s = bs->opaque;

   660     int l1_index, l2_index;

   661     uint64_t l2_offset, *l2_table, cluster_offset;

   662     int l1_bits, c;

   663     int index_in_cluster, nb_available, nb_needed, nb_clusters;

   664 

   665     index_in_cluster = (offset >> 9) & (s->cluster_sectors - 1);

   666     nb_needed = *num + index_in_cluster;

   667 

   668     l1_bits = s->l2_bits + s->cluster_bits;

   669 

   670     /* compute how many bytes there are between the offset and

   671      * the end of the l1 entry

   672      */

   673 

   674     nb_available = (1 << l1_bits) - (offset & ((1 << l1_bits) - 1));

   675 

   676     /* compute the number of available sectors */

   677 

   678     nb_available = (nb_available >> 9) + index_in_cluster;

   679 

   680     cluster_offset = 0;

   681 

   682     /* seek the the l2 offset in the l1 table */

   683 

   684     l1_index = offset >> l1_bits;

   685     if (l1_index >= s->l1_size)

   686         goto out;

   687 

   688     l2_offset = s->l1_table[l1_index];

   689 

   690     /* seek the l2 table of the given l2 offset */

   691 

   692     if (!l2_offset)

   693         goto out;

   694 

   695     /* load the l2 table in memory */

   696 

   697     l2_offset &= ~QCOW_OFLAG_COPIED;

   698     l2_table = l2_load(bs, l2_offset);

   699     if (l2_table == NULL)

   700         return 0;

   701 

   702     /* find the cluster offset for the given disk offset */

   703 

   704     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);

   705     cluster_offset = be64_to_cpu(l2_table[l2_index]);

   706     nb_clusters = size_to_clusters(s, nb_needed << 9);

   707 

   708     if (!cluster_offset) {

   709         /* how many empty clusters ? */

   710         c = count_contiguous_free_clusters(nb_clusters, &l2_table[l2_index]);

   711     } else {

   712         /* how many allocated clusters ? */

   713         c = count_contiguous_clusters(nb_clusters, s->cluster_size,

   714                 &l2_table[l2_index], QCOW_OFLAG_COPIED);

   715     }

   716 

   717    nb_available = (c * s->cluster_sectors);

   718 out:

   719     if (nb_available > nb_needed)

   720         nb_available = nb_needed;

   721 

   722     *num = nb_available - index_in_cluster;

   723 

   724     return cluster_offset & ~QCOW_OFLAG_COPIED;

   725 }

   726 

   727 /*

   728  * free_any_clusters

   729  *

   730  * free clusters according to its type: compressed or not

   731  *

   732  */

   733 

   734 static void free_any_clusters(BlockDriverState *bs,

   735                               uint64_t cluster_offset, int nb_clusters)

   736 {

   737     BDRVQcowState *s = bs->opaque;

   738 

   739     /* free the cluster */

   740 

   741     if (cluster_offset & QCOW_OFLAG_COMPRESSED) {

   742         int nb_csectors;

   743         nb_csectors = ((cluster_offset >> s->csize_shift) &

   744                        s->csize_mask) + 1;

   745         free_clusters(bs, (cluster_offset & s->cluster_offset_mask) & ~511,

   746                       nb_csectors * 512);

   747         return;

   748     }

   749 

   750     free_clusters(bs, cluster_offset, nb_clusters << s->cluster_bits);

   751 

   752     return;

   753 }

   754 

   755 /*

   756  * get_cluster_table

   757  *

   758  * for a given disk offset, load (and allocate if needed)

   759  * the l2 table.

   760  *

   761  * the l2 table offset in the qcow2 file and the cluster index

   762  * in the l2 table are given to the caller.

   763  *

   764  */

   765 

   766 static int get_cluster_table(BlockDriverState *bs, uint64_t offset,

   767                              uint64_t **new_l2_table,

   768                              uint64_t *new_l2_offset,

   769                              int *new_l2_index)

   770 {

   771     BDRVQcowState *s = bs->opaque;

   772     int l1_index, l2_index, ret;

   773     uint64_t l2_offset, *l2_table;

   774 

   775     /* seek the the l2 offset in the l1 table */

   776 

   777     l1_index = offset >> (s->l2_bits + s->cluster_bits);

   778     if (l1_index >= s->l1_size) {

   779         ret = grow_l1_table(bs, l1_index + 1);

   780         if (ret < 0)

   781             return 0;

   782     }

   783     l2_offset = s->l1_table[l1_index];

   784 

   785     /* seek the l2 table of the given l2 offset */

   786 

   787     if (l2_offset & QCOW_OFLAG_COPIED) {

   788         /* load the l2 table in memory */

   789         l2_offset &= ~QCOW_OFLAG_COPIED;

   790         l2_table = l2_load(bs, l2_offset);

   791         if (l2_table == NULL)

   792             return 0;

   793     } else {

   794         if (l2_offset)

   795             free_clusters(bs, l2_offset, s->l2_size * sizeof(uint64_t));

   796         l2_table = l2_allocate(bs, l1_index);

   797         if (l2_table == NULL)

   798             return 0;

   799         l2_offset = s->l1_table[l1_index] & ~QCOW_OFLAG_COPIED;

   800     }

   801 

   802     /* find the cluster offset for the given disk offset */

   803 

   804     l2_index = (offset >> s->cluster_bits) & (s->l2_size - 1);

   805 

   806     *new_l2_table = l2_table;

   807     *new_l2_offset = l2_offset;

   808     *new_l2_index = l2_index;

   809 

   810     return 1;

   811 }

   812 

   813 /*

   814  * alloc_compressed_cluster_offset

   815  *

   816  * For a given offset of the disk image, return cluster offset in

   817  * qcow2 file.

   818  *

   819  * If the offset is not found, allocate a new compressed cluster.

   820  *

   821  * Return the cluster offset if successful,

   822  * Return 0, otherwise.

   823  *

   824  */

   825 

   826 static uint64_t alloc_compressed_cluster_offset(BlockDriverState *bs,

   827                                                 uint64_t offset,

   828                                                 int compressed_size)

   829 {

   830     BDRVQcowState *s = bs->opaque;

   831     int l2_index, ret;

   832     uint64_t l2_offset, *l2_table, cluster_offset;

   833     int nb_csectors;

   834 

   835     ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index);

   836     if (ret == 0)

   837         return 0;

   838 

   839     cluster_offset = be64_to_cpu(l2_table[l2_index]);

   840     if (cluster_offset & QCOW_OFLAG_COPIED)

   841         return cluster_offset & ~QCOW_OFLAG_COPIED;

   842 

   843     if (cluster_offset)

   844         free_any_clusters(bs, cluster_offset, 1);

   845 

   846     cluster_offset = alloc_bytes(bs, compressed_size);

   847     nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -

   848                   (cluster_offset >> 9);

   849 

   850     cluster_offset |= QCOW_OFLAG_COMPRESSED |

   851                       ((uint64_t)nb_csectors << s->csize_shift);

   852 

   853     /* update L2 table */

   854 

   855     /* compressed clusters never have the copied flag */

   856 

   857     l2_table[l2_index] = cpu_to_be64(cluster_offset);

   858     if (bdrv_pwrite(s->hd,

   859                     l2_offset + l2_index * sizeof(uint64_t),

   860                     l2_table + l2_index,

   861                     sizeof(uint64_t)) != sizeof(uint64_t))

   862         return 0;

   863 

   864     return cluster_offset;

   865 }

   866 

   867 typedef struct QCowL2Meta

   868 {

   869     uint64_t offset;

   870     int n_start;

   871     int nb_available;

   872     int nb_clusters;

   873 } QCowL2Meta;

   874 

   875 static int alloc_cluster_link_l2(BlockDriverState *bs, uint64_t cluster_offset,

   876         QCowL2Meta *m)

   877 {

   878     BDRVQcowState *s = bs->opaque;

   879     int i, j = 0, l2_index, ret;

   880     uint64_t *old_cluster, start_sect, l2_offset, *l2_table;

   881 

   882     if (m->nb_clusters == 0)

   883         return 0;

   884 

   885     if (!(old_cluster = qemu_malloc(m->nb_clusters * sizeof(uint64_t))))

   886         return -ENOMEM;

   887 

   888     /* copy content of unmodified sectors */

   889     start_sect = (m->offset & ~(s->cluster_size - 1)) >> 9;

   890     if (m->n_start) {

   891         ret = copy_sectors(bs, start_sect, cluster_offset, 0, m->n_start);

   892         if (ret < 0)

   893             goto err;

   894     }

   895 

   896     if (m->nb_available & (s->cluster_sectors - 1)) {

   897         uint64_t end = m->nb_available & ~(uint64_t)(s->cluster_sectors - 1);

   898         ret = copy_sectors(bs, start_sect + end, cluster_offset + (end << 9),

   899                 m->nb_available - end, s->cluster_sectors);

   900         if (ret < 0)

   901             goto err;

   902     }

   903 

   904     ret = -EIO;

   905     /* update L2 table */

   906     if (!get_cluster_table(bs, m->offset, &l2_table, &l2_offset, &l2_index))

   907         goto err;

   908 

   909     for (i = 0; i < m->nb_clusters; i++) {

   910         if(l2_table[l2_index + i] != 0)

   911             old_cluster[j++] = l2_table[l2_index + i];

   912 

   913         l2_table[l2_index + i] = cpu_to_be64((cluster_offset +

   914                     (i << s->cluster_bits)) | QCOW_OFLAG_COPIED);

   915      }

   916 

   917     if (bdrv_pwrite(s->hd, l2_offset + l2_index * sizeof(uint64_t),

   918                 l2_table + l2_index, m->nb_clusters * sizeof(uint64_t)) !=

   919             m->nb_clusters * sizeof(uint64_t))

   920         goto err;

   921 

   922     for (i = 0; i < j; i++)

   923         free_any_clusters(bs, old_cluster[i], 1);

   924 

   925     ret = 0;

   926 err:

   927     qemu_free(old_cluster);

   928     return ret;

   929  }

   930 

   931 /*

   932  * alloc_cluster_offset

   933  *

   934  * For a given offset of the disk image, return cluster offset in

   935  * qcow2 file.

   936  *

   937  * If the offset is not found, allocate a new cluster.

   938  *

   939  * Return the cluster offset if successful,

   940  * Return 0, otherwise.

   941  *

   942  */

   943 

   944 static uint64_t alloc_cluster_offset(BlockDriverState *bs,

   945                                      uint64_t offset,

   946                                      int n_start, int n_end,

   947                                      int *num, QCowL2Meta *m)

   948 {

   949     BDRVQcowState *s = bs->opaque;

   950     int l2_index, ret;

   951     uint64_t l2_offset, *l2_table, cluster_offset;

   952     int nb_clusters, i = 0;

   953 

   954     ret = get_cluster_table(bs, offset, &l2_table, &l2_offset, &l2_index);

   955     if (ret == 0)

   956         return 0;

   957 

   958     nb_clusters = size_to_clusters(s, n_end << 9);

   959 

   960     nb_clusters = MIN(nb_clusters, s->l2_size - l2_index);

   961 

   962     cluster_offset = be64_to_cpu(l2_table[l2_index]);

   963 

   964     /* We keep all QCOW_OFLAG_COPIED clusters */

   965 

   966     if (cluster_offset & QCOW_OFLAG_COPIED) {

   967         nb_clusters = count_contiguous_clusters(nb_clusters, s->cluster_size,

   968                 &l2_table[l2_index], 0);

   969 

   970         cluster_offset &= ~QCOW_OFLAG_COPIED;

   971         m->nb_clusters = 0;

   972 

   973         goto out;

   974     }

   975 

   976     /* for the moment, multiple compressed clusters are not managed */

   977 

   978     if (cluster_offset & QCOW_OFLAG_COMPRESSED)

   979         nb_clusters = 1;

   980 

   981     /* how many available clusters ? */

   982 

   983     while (i < nb_clusters) {

   984         i += count_contiguous_free_clusters(nb_clusters - i,

   985                 &l2_table[l2_index + i]);

   986 

   987         cluster_offset = be64_to_cpu(l2_table[l2_index + i]);

   988 

   989         if ((cluster_offset & QCOW_OFLAG_COPIED) ||

   990                 (cluster_offset & QCOW_OFLAG_COMPRESSED))

   991             break;

   992 

   993         i += count_contiguous_clusters(nb_clusters - i, s->cluster_size,

   994                 &l2_table[l2_index + i], 0);

   995 

   996         if(be64_to_cpu(l2_table[l2_index + i]))

   997             break;

   998     }

   999     nb_clusters = i;

  1000 

  1001     /* allocate a new cluster */

  1002 

  1003     cluster_offset = alloc_clusters(bs, nb_clusters * s->cluster_size);

  1004 

  1005     /* save info needed for meta data update */

  1006     m->offset = offset;

  1007     m->n_start = n_start;

  1008     m->nb_clusters = nb_clusters;

  1009 

  1010 out:

  1011     m->nb_available = MIN(nb_clusters << (s->cluster_bits - 9), n_end);

  1012 

  1013     *num = m->nb_available - n_start;

  1014 

  1015     return cluster_offset;

  1016 }

  1017 

  1018 static int qcow_is_allocated(BlockDriverState *bs, int64_t sector_num,

  1019                              int nb_sectors, int *pnum)

  1020 {

  1021     uint64_t cluster_offset;

  1022 

  1023     *pnum = nb_sectors;

  1024     cluster_offset = get_cluster_offset(bs, sector_num << 9, pnum);

  1025 

  1026     return (cluster_offset != 0);

  1027 }

  1028 

  1029 static int decompress_buffer(uint8_t *out_buf, int out_buf_size,

  1030                              const uint8_t *buf, int buf_size)

  1031 {

  1032     z_stream strm1, *strm = &strm1;

  1033     int ret, out_len;

  1034 

  1035     memset(strm, 0, sizeof(*strm));

  1036 

  1037     strm->next_in = (uint8_t *)buf;

  1038     strm->avail_in = buf_size;

  1039     strm->next_out = out_buf;

  1040     strm->avail_out = out_buf_size;

  1041 

  1042     ret = inflateInit2(strm, -12);

  1043     if (ret != Z_OK)

  1044         return -1;

  1045     ret = inflate(strm, Z_FINISH);

  1046     out_len = strm->next_out - out_buf;

  1047     if ((ret != Z_STREAM_END && ret != Z_BUF_ERROR) ||

  1048         out_len != out_buf_size) {

  1049         inflateEnd(strm);

  1050         return -1;

  1051     }

  1052     inflateEnd(strm);

  1053     return 0;

  1054 }

  1055 

  1056 static int decompress_cluster(BDRVQcowState *s, uint64_t cluster_offset)

  1057 {

  1058     int ret, csize, nb_csectors, sector_offset;

  1059     uint64_t coffset;

  1060 

  1061     coffset = cluster_offset & s->cluster_offset_mask;

  1062     if (s->cluster_cache_offset != coffset) {

  1063         nb_csectors = ((cluster_offset >> s->csize_shift) & s->csize_mask) + 1;

  1064         sector_offset = coffset & 511;

  1065         csize = nb_csectors * 512 - sector_offset;

  1066         ret = bdrv_read(s->hd, coffset >> 9, s->cluster_data, nb_csectors);

  1067         if (ret < 0) {

  1068             return -1;

  1069         }

  1070         if (decompress_buffer(s->cluster_cache, s->cluster_size,

  1071                               s->cluster_data + sector_offset, csize) < 0) {

  1072             return -1;

  1073         }

  1074         s->cluster_cache_offset = coffset;

  1075     }

  1076     return 0;

  1077 }

  1078 

  1079 /* handle reading after the end of the backing file */

  1080 static int backing_read1(BlockDriverState *bs,

  1081                          int64_t sector_num, uint8_t *buf, int nb_sectors)

  1082 {

  1083     int n1;

  1084     if ((sector_num + nb_sectors) <= bs->total_sectors)

  1085         return nb_sectors;

  1086     if (sector_num >= bs->total_sectors)

  1087         n1 = 0;

  1088     else

  1089         n1 = bs->total_sectors - sector_num;

  1090     memset(buf + n1 * 512, 0, 512 * (nb_sectors - n1));

  1091     return n1;

  1092 }

  1093 

  1094 static int qcow_read(BlockDriverState *bs, int64_t sector_num,

  1095                      uint8_t *buf, int nb_sectors)

  1096 {

  1097     BDRVQcowState *s = bs->opaque;

  1098     int ret, index_in_cluster, n, n1;

  1099     uint64_t cluster_offset;

  1100 

  1101     while (nb_sectors > 0) {

  1102         n = nb_sectors;

  1103         cluster_offset = get_cluster_offset(bs, sector_num << 9, &n);

  1104         index_in_cluster = sector_num & (s->cluster_sectors - 1);

  1105         if (!cluster_offset) {

  1106             if (bs->backing_hd) {

  1107                 /* read from the base image */

  1108                 n1 = backing_read1(bs->backing_hd, sector_num, buf, n);

  1109                 if (n1 > 0) {

  1110                     ret = bdrv_read(bs->backing_hd, sector_num, buf, n1);

  1111                     if (ret < 0)

  1112                         return -1;

  1113                 }

  1114             } else {

  1115                 memset(buf, 0, 512 * n);

  1116             }

  1117         } else if (cluster_offset & QCOW_OFLAG_COMPRESSED) {

  1118             if (decompress_cluster(s, cluster_offset) < 0)

  1119                 return -1;

  1120             memcpy(buf, s->cluster_cache + index_in_cluster * 512, 512 * n);

  1121         } else {

  1122             ret = bdrv_pread(s->hd, cluster_offset + index_in_cluster * 512, buf, n * 512);

  1123             if (ret != n * 512)

  1124                 return -1;

  1125             if (s->crypt_method) {

  1126                 encrypt_sectors(s, sector_num, buf, buf, n, 0,

  1127                                 &s->aes_decrypt_key);

  1128             }

  1129         }

  1130         nb_sectors -= n;

  1131         sector_num += n;

  1132         buf += n * 512;

  1133     }

  1134     return 0;

  1135 }