block/vmdk.c

   1 /*
   2  * Block driver for the VMDK format
   3  *
   4  * Copyright (c) 2004 Fabrice Bellard
   5  * Copyright (c) 2005 Filip Navara
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  20  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  */
  25
  26 #include "qemu-common.h"
  27 #include "block_int.h"
  28 #include "module.h"
  29
  30 #define VMDK3_MAGIC (('C' << 24) | ('O' << 16) | ('W' << 8) | 'D')
  31 #define VMDK4_MAGIC (('K' << 24) | ('D' << 16) | ('M' << 8) | 'V')
  32
  33 typedef struct {
  34     uint32_t version;
  35     uint32_t flags;
  36     uint32_t disk_sectors;
  37     uint32_t granularity;
  38     uint32_t l1dir_offset;
  39     uint32_t l1dir_size;
  40     uint32_t file_sectors;
  41     uint32_t cylinders;
  42     uint32_t heads;
  43     uint32_t sectors_per_track;
  44 } VMDK3Header;
  45
  46 typedef struct {
  47     uint32_t version;
  48     uint32_t flags;
  49     int64_t capacity;
  50     int64_t granularity;
  51     int64_t desc_offset;
  52     int64_t desc_size;
  53     int32_t num_gtes_per_gte;
  54     int64_t rgd_offset;
  55     int64_t gd_offset;
  56     int64_t grain_offset;
  57     char filler[1];
  58     char check_bytes[4];
  59 } __attribute__((packed)) VMDK4Header;
  60
  61 #define L2_CACHE_SIZE 16
  62
  63 typedef struct VmdkExtent {
  64     BlockDriverState *file;
  65     bool flat;
  66     int64_t sectors;
  67     int64_t end_sector;
  68     int64_t l1_table_offset;
  69     int64_t l1_backup_table_offset;
  70     uint32_t *l1_table;
  71     uint32_t *l1_backup_table;
  72     unsigned int l1_size;
  73     uint32_t l1_entry_sectors;
  74
  75     unsigned int l2_size;
  76     uint32_t *l2_cache;
  77     uint32_t l2_cache_offsets[L2_CACHE_SIZE];
  78     uint32_t l2_cache_counts[L2_CACHE_SIZE];
  79
  80     unsigned int cluster_sectors;
  81 } VmdkExtent;
  82
  83 typedef struct BDRVVmdkState {
  84     uint32_t parent_cid;
  85     int num_extents;
  86     /* Extent array with num_extents entries, ascend ordered by address */
  87     VmdkExtent *extents;
  88 } BDRVVmdkState;
  89
  90 typedef struct VmdkMetaData {
  91     uint32_t offset;
  92     unsigned int l1_index;
  93     unsigned int l2_index;
  94     unsigned int l2_offset;
  95     int valid;
  96 } VmdkMetaData;
  97
  98 static int vmdk_probe(const uint8_t *buf, int buf_size, const char *filename)
  99 {
 100     uint32_t magic;
 101
 102     if (buf_size < 4)
 103         return 0;
 104     magic = be32_to_cpu(*(uint32_t *)buf);
 105     if (magic == VMDK3_MAGIC ||
 106         magic == VMDK4_MAGIC) {
 107         return 100;
 108     } else {
 109         const char *p = (const char *)buf;
 110         const char *end = p + buf_size;
 111         while (p < end) {
 112             if (*p == '#') {
 113                 /* skip comment line */
 114                 while (p < end && *p != '\n') {
 115                     p++;
 116                 }
 117                 p++;
 118                 continue;
 119             }
 120             if (*p == ' ') {
 121                 while (p < end && *p == ' ') {
 122                     p++;
 123                 }
 124                 /* skip '\r' if windows line endings used. */
 125                 if (p < end && *p == '\r') {
 126                     p++;
 127                 }
 128                 /* only accept blank lines before 'version=' line */
 129                 if (p == end || *p != '\n') {
 130                     return 0;
 131                 }
 132                 p++;
 133                 continue;
 134             }
 135             if (end - p >= strlen("version=X\n")) {
 136                 if (strncmp("version=1\n", p, strlen("version=1\n")) == 0 ||
 137                     strncmp("version=2\n", p, strlen("version=2\n")) == 0) {
 138                     return 100;
 139                 }
 140             }
 141             if (end - p >= strlen("version=X\r\n")) {
 142                 if (strncmp("version=1\r\n", p, strlen("version=1\r\n")) == 0 ||
 143                     strncmp("version=2\r\n", p, strlen("version=2\r\n")) == 0) {
 144                     return 100;
 145                 }
 146             }
 147             return 0;
 148         }
 149         return 0;
 150     }
 151 }
 152
 153 #define CHECK_CID 1
 154
 155 #define SECTOR_SIZE 512
 156 #define DESC_SIZE 20*SECTOR_SIZE        // 20 sectors of 512 bytes each
 157 #define HEADER_SIZE 512                         // first sector of 512 bytes
 158
 159 static void vmdk_free_extents(BlockDriverState *bs)
 160 {
 161     int i;
 162     BDRVVmdkState *s = bs->opaque;
 163
 164     for (i = 0; i < s->num_extents; i++) {
 165         qemu_free(s->extents[i].l1_table);
 166         qemu_free(s->extents[i].l2_cache);
 167         qemu_free(s->extents[i].l1_backup_table);
 168     }
 169     qemu_free(s->extents);
 170 }
 171
 172 static uint32_t vmdk_read_cid(BlockDriverState *bs, int parent)
 173 {
 174     char desc[DESC_SIZE];
 175     uint32_t cid;
 176     const char *p_name, *cid_str;
 177     size_t cid_str_size;
 178
 179     /* the descriptor offset = 0x200 */
 180     if (bdrv_pread(bs->file, 0x200, desc, DESC_SIZE) != DESC_SIZE)
 181         return 0;
 182
 183     if (parent) {
 184         cid_str = "parentCID";
 185         cid_str_size = sizeof("parentCID");
 186     } else {
 187         cid_str = "CID";
 188         cid_str_size = sizeof("CID");
 189     }
 190
 191     if ((p_name = strstr(desc,cid_str)) != NULL) {
 192         p_name += cid_str_size;
 193         sscanf(p_name,"%x",&cid);
 194     }
 195
 196     return cid;
 197 }
 198
 199 static int vmdk_write_cid(BlockDriverState *bs, uint32_t cid)
 200 {
 201     char desc[DESC_SIZE], tmp_desc[DESC_SIZE];
 202     char *p_name, *tmp_str;
 203
 204     /* the descriptor offset = 0x200 */
 205     if (bdrv_pread(bs->file, 0x200, desc, DESC_SIZE) != DESC_SIZE)
 206         return -1;
 207
 208     tmp_str = strstr(desc,"parentCID");
 209     pstrcpy(tmp_desc, sizeof(tmp_desc), tmp_str);
 210     if ((p_name = strstr(desc,"CID")) != NULL) {
 211         p_name += sizeof("CID");
 212         snprintf(p_name, sizeof(desc) - (p_name - desc), "%x\n", cid);
 213         pstrcat(desc, sizeof(desc), tmp_desc);
 214     }
 215
 216     if (bdrv_pwrite_sync(bs->file, 0x200, desc, DESC_SIZE) < 0)
 217         return -1;
 218     return 0;
 219 }
 220
 221 static int vmdk_is_cid_valid(BlockDriverState *bs)
 222 {
 223 #ifdef CHECK_CID
 224     BDRVVmdkState *s = bs->opaque;
 225     BlockDriverState *p_bs = bs->backing_hd;
 226     uint32_t cur_pcid;
 227
 228     if (p_bs) {
 229         cur_pcid = vmdk_read_cid(p_bs,0);
 230         if (s->parent_cid != cur_pcid)
 231             // CID not valid
 232             return 0;
 233     }
 234 #endif
 235     // CID valid
 236     return 1;
 237 }
 238
 239 static int vmdk_snapshot_create(const char *filename, const char *backing_file)
 240 {
 241     int snp_fd, p_fd;
 242     int ret;
 243     uint32_t p_cid;
 244     char *p_name, *gd_buf, *rgd_buf;
 245     const char *real_filename, *temp_str;
 246     VMDK4Header header;
 247     uint32_t gde_entries, gd_size;
 248     int64_t gd_offset, rgd_offset, capacity, gt_size;
 249     char p_desc[DESC_SIZE], s_desc[DESC_SIZE], hdr[HEADER_SIZE];
 250     static const char desc_template[] =
 251     "# Disk DescriptorFile\n"
 252     "version=1\n"
 253     "CID=%x\n"
 254     "parentCID=%x\n"
 255     "createType=\"monolithicSparse\"\n"
 256     "parentFileNameHint=\"%s\"\n"
 257     "\n"
 258     "# Extent description\n"
 259     "RW %u SPARSE \"%s\"\n"
 260     "\n"
 261     "# The Disk Data Base \n"
 262     "#DDB\n"
 263     "\n";
 264
 265     snp_fd = open(filename, O_RDWR | O_CREAT | O_TRUNC | O_BINARY | O_LARGEFILE, 0644);
 266     if (snp_fd < 0)
 267         return -errno;
 268     p_fd = open(backing_file, O_RDONLY | O_BINARY | O_LARGEFILE);
 269     if (p_fd < 0) {
 270         close(snp_fd);
 271         return -errno;
 272     }
 273
 274     /* read the header */
 275     if (lseek(p_fd, 0x0, SEEK_SET) == -1) {
 276         ret = -errno;
 277         goto fail;
 278     }
 279     if (read(p_fd, hdr, HEADER_SIZE) != HEADER_SIZE) {
 280         ret = -errno;
 281         goto fail;
 282     }
 283
 284     /* write the header */
 285     if (lseek(snp_fd, 0x0, SEEK_SET) == -1) {
 286         ret = -errno;
 287         goto fail;
 288     }
 289     if (write(snp_fd, hdr, HEADER_SIZE) == -1) {
 290         ret = -errno;
 291         goto fail;
 292     }
 293
 294     memset(&header, 0, sizeof(header));
 295     memcpy(&header,&hdr[4], sizeof(header)); // skip the VMDK4_MAGIC
 296
 297     if (ftruncate(snp_fd, header.grain_offset << 9)) {
 298         ret = -errno;
 299         goto fail;
 300     }
 301     /* the descriptor offset = 0x200 */
 302     if (lseek(p_fd, 0x200, SEEK_SET) == -1) {
 303         ret = -errno;
 304         goto fail;
 305     }
 306     if (read(p_fd, p_desc, DESC_SIZE) != DESC_SIZE) {
 307         ret = -errno;
 308         goto fail;
 309     }
 310
 311     if ((p_name = strstr(p_desc,"CID")) != NULL) {
 312         p_name += sizeof("CID");
 313         sscanf(p_name,"%x",&p_cid);
 314     }
 315
 316     real_filename = filename;
 317     if ((temp_str = strrchr(real_filename, '\\')) != NULL)
 318         real_filename = temp_str + 1;
 319     if ((temp_str = strrchr(real_filename, '/')) != NULL)
 320         real_filename = temp_str + 1;
 321     if ((temp_str = strrchr(real_filename, ':')) != NULL)
 322         real_filename = temp_str + 1;
 323
 324     snprintf(s_desc, sizeof(s_desc), desc_template, p_cid, p_cid, backing_file,
 325              (uint32_t)header.capacity, real_filename);
 326
 327     /* write the descriptor */
 328     if (lseek(snp_fd, 0x200, SEEK_SET) == -1) {
 329         ret = -errno;
 330         goto fail;
 331     }
 332     if (write(snp_fd, s_desc, strlen(s_desc)) == -1) {
 333         ret = -errno;
 334         goto fail;
 335     }
 336
 337     gd_offset = header.gd_offset * SECTOR_SIZE;     // offset of GD table
 338     rgd_offset = header.rgd_offset * SECTOR_SIZE;   // offset of RGD table
 339     capacity = header.capacity * SECTOR_SIZE;       // Extent size
 340     /*
 341      * Each GDE span 32M disk, means:
 342      * 512 GTE per GT, each GTE points to grain
 343      */
 344     gt_size = (int64_t)header.num_gtes_per_gte * header.granularity * SECTOR_SIZE;
 345     if (!gt_size) {
 346         ret = -EINVAL;
 347         goto fail;
 348     }
 349     gde_entries = (uint32_t)(capacity / gt_size);  // number of gde/rgde
 350     gd_size = gde_entries * sizeof(uint32_t);
 351
 352     /* write RGD */
 353     rgd_buf = qemu_malloc(gd_size);
 354     if (lseek(p_fd, rgd_offset, SEEK_SET) == -1) {
 355         ret = -errno;
 356         goto fail_rgd;
 357     }
 358     if (read(p_fd, rgd_buf, gd_size) != gd_size) {
 359         ret = -errno;
 360         goto fail_rgd;
 361     }
 362     if (lseek(snp_fd, rgd_offset, SEEK_SET) == -1) {
 363         ret = -errno;
 364         goto fail_rgd;
 365     }
 366     if (write(snp_fd, rgd_buf, gd_size) == -1) {
 367         ret = -errno;
 368         goto fail_rgd;
 369     }
 370
 371     /* write GD */
 372     gd_buf = qemu_malloc(gd_size);
 373     if (lseek(p_fd, gd_offset, SEEK_SET) == -1) {
 374         ret = -errno;
 375         goto fail_gd;
 376     }
 377     if (read(p_fd, gd_buf, gd_size) != gd_size) {
 378         ret = -errno;
 379         goto fail_gd;
 380     }
 381     if (lseek(snp_fd, gd_offset, SEEK_SET) == -1) {
 382         ret = -errno;
 383         goto fail_gd;
 384     }
 385     if (write(snp_fd, gd_buf, gd_size) == -1) {
 386         ret = -errno;
 387         goto fail_gd;
 388     }
 389     ret = 0;
 390
 391 fail_gd:
 392     qemu_free(gd_buf);
 393 fail_rgd:
 394     qemu_free(rgd_buf);
 395 fail:
 396     close(p_fd);
 397     close(snp_fd);
 398     return ret;
 399 }
 400
 401 static int vmdk_parent_open(BlockDriverState *bs)
 402 {
 403     char *p_name;
 404     char desc[DESC_SIZE];
 405
 406     /* the descriptor offset = 0x200 */
 407     if (bdrv_pread(bs->file, 0x200, desc, DESC_SIZE) != DESC_SIZE)
 408         return -1;
 409
 410     if ((p_name = strstr(desc,"parentFileNameHint")) != NULL) {
 411         char *end_name;
 412
 413         p_name += sizeof("parentFileNameHint") + 1;
 414         if ((end_name = strchr(p_name,'\"')) == NULL)
 415             return -1;
 416         if ((end_name - p_name) > sizeof (bs->backing_file) - 1)
 417             return -1;
 418
 419         pstrcpy(bs->backing_file, end_name - p_name + 1, p_name);
 420     }
 421
 422     return 0;
 423 }
 424
 425 /* Create and append extent to the extent array. Return the added VmdkExtent
 426  * address. return NULL if allocation failed. */
 427 static VmdkExtent *vmdk_add_extent(BlockDriverState *bs,
 428                            BlockDriverState *file, bool flat, int64_t sectors,
 429                            int64_t l1_offset, int64_t l1_backup_offset,
 430                            uint32_t l1_size,
 431                            int l2_size, unsigned int cluster_sectors)
 432 {
 433     VmdkExtent *extent;
 434     BDRVVmdkState *s = bs->opaque;
 435
 436     s->extents = qemu_realloc(s->extents,
 437                               (s->num_extents + 1) * sizeof(VmdkExtent));
 438     extent = &s->extents[s->num_extents];
 439     s->num_extents++;
 440
 441     memset(extent, 0, sizeof(VmdkExtent));
 442     extent->file = file;
 443     extent->flat = flat;
 444     extent->sectors = sectors;
 445     extent->l1_table_offset = l1_offset;
 446     extent->l1_backup_table_offset = l1_backup_offset;
 447     extent->l1_size = l1_size;
 448     extent->l1_entry_sectors = l2_size * cluster_sectors;
 449     extent->l2_size = l2_size;
 450     extent->cluster_sectors = cluster_sectors;
 451
 452     if (s->num_extents > 1) {
 453         extent->end_sector = (*(extent - 1)).end_sector + extent->sectors;
 454     } else {
 455         extent->end_sector = extent->sectors;
 456     }
 457     bs->total_sectors = extent->end_sector;
 458     return extent;
 459 }
 460
 461 static int vmdk_init_tables(BlockDriverState *bs, VmdkExtent *extent)
 462 {
 463     int ret;
 464     int l1_size, i;
 465
 466     /* read the L1 table */
 467     l1_size = extent->l1_size * sizeof(uint32_t);
 468     extent->l1_table = qemu_malloc(l1_size);
 469     ret = bdrv_pread(extent->file,
 470                     extent->l1_table_offset,
 471                     extent->l1_table,
 472                     l1_size);
 473     if (ret < 0) {
 474         goto fail_l1;
 475     }
 476     for (i = 0; i < extent->l1_size; i++) {
 477         le32_to_cpus(&extent->l1_table[i]);
 478     }
 479
 480     if (extent->l1_backup_table_offset) {
 481         extent->l1_backup_table = qemu_malloc(l1_size);
 482         ret = bdrv_pread(extent->file,
 483                         extent->l1_backup_table_offset,
 484                         extent->l1_backup_table,
 485                         l1_size);
 486         if (ret < 0) {
 487             goto fail_l1b;
 488         }
 489         for (i = 0; i < extent->l1_size; i++) {
 490             le32_to_cpus(&extent->l1_backup_table[i]);
 491         }
 492     }
 493
 494     extent->l2_cache =
 495         qemu_malloc(extent->l2_size * L2_CACHE_SIZE * sizeof(uint32_t));
 496     return 0;
 497  fail_l1b:
 498     qemu_free(extent->l1_backup_table);
 499  fail_l1:
 500     qemu_free(extent->l1_table);
 501     return ret;
 502 }
 503
 504 static int vmdk_open_vmdk3(BlockDriverState *bs, int flags)
 505 {
 506     int ret;
 507     uint32_t magic;
 508     VMDK3Header header;
 509     VmdkExtent *extent;
 510
 511     ret = bdrv_pread(bs->file, sizeof(magic), &header, sizeof(header));
 512     if (ret < 0) {
 513         goto fail;
 514     }
 515     extent = vmdk_add_extent(bs,
 516                              bs->file, false,
 517                              le32_to_cpu(header.disk_sectors),
 518                              le32_to_cpu(header.l1dir_offset) << 9,
 519                              0, 1 << 6, 1 << 9,
 520                              le32_to_cpu(header.granularity));
 521     ret = vmdk_init_tables(bs, extent);
 522     if (ret) {
 523         /* vmdk_init_tables cleans up on fail, so only free allocation of
 524          * vmdk_add_extent here. */
 525         goto fail;
 526     }
 527     return 0;
 528  fail:
 529     vmdk_free_extents(bs);
 530     return ret;
 531 }
 532
 533 static int vmdk_open_vmdk4(BlockDriverState *bs, int flags)
 534 {
 535     int ret;
 536     uint32_t magic;
 537     uint32_t l1_size, l1_entry_sectors;
 538     VMDK4Header header;
 539     BDRVVmdkState *s = bs->opaque;
 540     VmdkExtent *extent;
 541
 542     ret = bdrv_pread(bs->file, sizeof(magic), &header, sizeof(header));
 543     if (ret < 0) {
 544         goto fail;
 545     }
 546     l1_entry_sectors = le32_to_cpu(header.num_gtes_per_gte)
 547                         * le64_to_cpu(header.granularity);
 548     l1_size = (le64_to_cpu(header.capacity) + l1_entry_sectors - 1)
 549                 / l1_entry_sectors;
 550     extent = vmdk_add_extent(bs, bs->file, false,
 551                           le64_to_cpu(header.capacity),
 552                           le64_to_cpu(header.gd_offset) << 9,
 553                           le64_to_cpu(header.rgd_offset) << 9,
 554                           l1_size,
 555                           le32_to_cpu(header.num_gtes_per_gte),
 556                           le64_to_cpu(header.granularity));
 557     if (extent->l1_entry_sectors <= 0) {
 558         ret = -EINVAL;
 559         goto fail;
 560     }
 561     /* try to open parent images, if exist */
 562     ret = vmdk_parent_open(bs);
 563     if (ret) {
 564         goto fail;
 565     }
 566     s->parent_cid = vmdk_read_cid(bs, 1);
 567     ret = vmdk_init_tables(bs, extent);
 568     if (ret) {
 569         goto fail;
 570     }
 571     return 0;
 572  fail:
 573     vmdk_free_extents(bs);
 574     return ret;
 575 }
 576
 577 static int vmdk_open(BlockDriverState *bs, int flags)
 578 {
 579     uint32_t magic;
 580
 581     if (bdrv_pread(bs->file, 0, &magic, sizeof(magic)) != sizeof(magic)) {
 582         return -EIO;
 583     }
 584
 585     magic = be32_to_cpu(magic);
 586     if (magic == VMDK3_MAGIC) {
 587         return vmdk_open_vmdk3(bs, flags);
 588     } else if (magic == VMDK4_MAGIC) {
 589         return vmdk_open_vmdk4(bs, flags);
 590     } else {
 591         return -EINVAL;
 592     }
 593 }
 594
 595 static int get_whole_cluster(BlockDriverState *bs,
 596                 VmdkExtent *extent,
 597                 uint64_t cluster_offset,
 598                 uint64_t offset,
 599                 bool allocate)
 600 {
 601     /* 128 sectors * 512 bytes each = grain size 64KB */
 602     uint8_t  whole_grain[extent->cluster_sectors * 512];
 603
 604     /* we will be here if it's first write on non-exist grain(cluster).
 605      * try to read from parent image, if exist */
 606     if (bs->backing_hd) {
 607         int ret;
 608
 609         if (!vmdk_is_cid_valid(bs))
 610             return -1;
 611
 612         /* floor offset to cluster */
 613         offset -= offset % (extent->cluster_sectors * 512);
 614         ret = bdrv_read(bs->backing_hd, offset >> 9, whole_grain,
 615                 extent->cluster_sectors);
 616         if (ret < 0) {
 617             return -1;
 618         }
 619
 620         /* Write grain only into the active image */
 621         ret = bdrv_write(extent->file, cluster_offset, whole_grain,
 622                 extent->cluster_sectors);
 623         if (ret < 0) {
 624             return -1;
 625         }
 626     }
 627     return 0;
 628 }
 629
 630 static int vmdk_L2update(VmdkExtent *extent, VmdkMetaData *m_data)
 631 {
 632     /* update L2 table */
 633     if (bdrv_pwrite_sync(
 634                 extent->file,
 635                 ((int64_t)m_data->l2_offset * 512)
 636                     + (m_data->l2_index * sizeof(m_data->offset)),
 637                 &(m_data->offset),
 638                 sizeof(m_data->offset)
 639             ) < 0) {
 640         return -1;
 641     }
 642     /* update backup L2 table */
 643     if (extent->l1_backup_table_offset != 0) {
 644         m_data->l2_offset = extent->l1_backup_table[m_data->l1_index];
 645         if (bdrv_pwrite_sync(
 646                     extent->file,
 647                     ((int64_t)m_data->l2_offset * 512)
 648                         + (m_data->l2_index * sizeof(m_data->offset)),
 649                     &(m_data->offset), sizeof(m_data->offset)
 650                 ) < 0) {
 651             return -1;
 652         }
 653     }
 654
 655     return 0;
 656 }
 657
 658 static uint64_t get_cluster_offset(BlockDriverState *bs,
 659                                     VmdkExtent *extent,
 660                                     VmdkMetaData *m_data,
 661                                     uint64_t offset, int allocate)
 662 {
 663     unsigned int l1_index, l2_offset, l2_index;
 664     int min_index, i, j;
 665     uint32_t min_count, *l2_table, tmp = 0;
 666     uint64_t cluster_offset;
 667
 668     if (m_data)
 669         m_data->valid = 0;
 670
 671     l1_index = (offset >> 9) / extent->l1_entry_sectors;
 672     if (l1_index >= extent->l1_size) {
 673         return 0;
 674     }
 675     l2_offset = extent->l1_table[l1_index];
 676     if (!l2_offset) {
 677         return 0;
 678     }
 679     for (i = 0; i < L2_CACHE_SIZE; i++) {
 680         if (l2_offset == extent->l2_cache_offsets[i]) {
 681             /* increment the hit count */
 682             if (++extent->l2_cache_counts[i] == 0xffffffff) {
 683                 for (j = 0; j < L2_CACHE_SIZE; j++) {
 684                     extent->l2_cache_counts[j] >>= 1;
 685                 }
 686             }
 687             l2_table = extent->l2_cache + (i * extent->l2_size);
 688             goto found;
 689         }
 690     }
 691     /* not found: load a new entry in the least used one */
 692     min_index = 0;
 693     min_count = 0xffffffff;
 694     for (i = 0; i < L2_CACHE_SIZE; i++) {
 695         if (extent->l2_cache_counts[i] < min_count) {
 696             min_count = extent->l2_cache_counts[i];
 697             min_index = i;
 698         }
 699     }
 700     l2_table = extent->l2_cache + (min_index * extent->l2_size);
 701     if (bdrv_pread(
 702                 extent->file,
 703                 (int64_t)l2_offset * 512,
 704                 l2_table,
 705                 extent->l2_size * sizeof(uint32_t)
 706             ) != extent->l2_size * sizeof(uint32_t)) {
 707         return 0;
 708     }
 709
 710     extent->l2_cache_offsets[min_index] = l2_offset;
 711     extent->l2_cache_counts[min_index] = 1;
 712  found:
 713     l2_index = ((offset >> 9) / extent->cluster_sectors) % extent->l2_size;
 714     cluster_offset = le32_to_cpu(l2_table[l2_index]);
 715
 716     if (!cluster_offset) {
 717         if (!allocate)
 718             return 0;
 719
 720         // Avoid the L2 tables update for the images that have snapshots.
 721         cluster_offset = bdrv_getlength(extent->file);
 722         bdrv_truncate(
 723             extent->file,
 724             cluster_offset + (extent->cluster_sectors << 9)
 725         );
 726
 727         cluster_offset >>= 9;
 728         tmp = cpu_to_le32(cluster_offset);
 729         l2_table[l2_index] = tmp;
 730
 731         /* First of all we write grain itself, to avoid race condition
 732          * that may to corrupt the image.
 733          * This problem may occur because of insufficient space on host disk
 734          * or inappropriate VM shutdown.
 735          */
 736         if (get_whole_cluster(
 737                 bs, extent, cluster_offset, offset, allocate) == -1)
 738             return 0;
 739
 740         if (m_data) {
 741             m_data->offset = tmp;
 742             m_data->l1_index = l1_index;
 743             m_data->l2_index = l2_index;
 744             m_data->l2_offset = l2_offset;
 745             m_data->valid = 1;
 746         }
 747     }
 748     cluster_offset <<= 9;
 749     return cluster_offset;
 750 }
 751
 752 static VmdkExtent *find_extent(BDRVVmdkState *s,
 753                                 int64_t sector_num, VmdkExtent *start_hint)
 754 {
 755     VmdkExtent *extent = start_hint;
 756
 757     if (!extent) {
 758         extent = &s->extents[0];
 759     }
 760     while (extent < &s->extents[s->num_extents]) {
 761         if (sector_num < extent->end_sector) {
 762             return extent;
 763         }
 764         extent++;
 765     }
 766     return NULL;
 767 }
 768
 769 static int vmdk_is_allocated(BlockDriverState *bs, int64_t sector_num,
 770                              int nb_sectors, int *pnum)
 771 {
 772     BDRVVmdkState *s = bs->opaque;
 773
 774     int64_t index_in_cluster, n, ret;
 775     uint64_t offset;
 776     VmdkExtent *extent;
 777
 778     extent = find_extent(s, sector_num, NULL);
 779     if (!extent) {
 780         return 0;
 781     }
 782     if (extent->flat) {
 783         n = extent->end_sector - sector_num;
 784         ret = 1;
 785     } else {
 786         offset = get_cluster_offset(bs, extent, NULL, sector_num * 512, 0);
 787         index_in_cluster = sector_num % extent->cluster_sectors;
 788         n = extent->cluster_sectors - index_in_cluster;
 789         ret = offset ? 1 : 0;
 790     }
 791     if (n > nb_sectors)
 792         n = nb_sectors;
 793     *pnum = n;
 794     return ret;
 795 }
 796
 797 static int vmdk_read(BlockDriverState *bs, int64_t sector_num,
 798                     uint8_t *buf, int nb_sectors)
 799 {
 800     BDRVVmdkState *s = bs->opaque;
 801     int ret;
 802     uint64_t n, index_in_cluster;
 803     VmdkExtent *extent = NULL;
 804     uint64_t cluster_offset;
 805
 806     while (nb_sectors > 0) {
 807         extent = find_extent(s, sector_num, extent);
 808         if (!extent) {
 809             return -EIO;
 810         }
 811         cluster_offset = get_cluster_offset(
 812                             bs, extent, NULL, sector_num << 9, 0);
 813         index_in_cluster = sector_num % extent->cluster_sectors;
 814         n = extent->cluster_sectors - index_in_cluster;
 815         if (n > nb_sectors)
 816             n = nb_sectors;
 817         if (!cluster_offset) {
 818             // try to read from parent image, if exist
 819             if (bs->backing_hd) {
 820                 if (!vmdk_is_cid_valid(bs))
 821                     return -1;
 822                 ret = bdrv_read(bs->backing_hd, sector_num, buf, n);
 823                 if (ret < 0)
 824                     return -1;
 825             } else {
 826                 memset(buf, 0, 512 * n);
 827             }
 828         } else {
 829             if(bdrv_pread(bs->file, cluster_offset + index_in_cluster * 512, buf, n * 512) != n * 512)
 830                 return -1;
 831         }
 832         nb_sectors -= n;
 833         sector_num += n;
 834         buf += n * 512;
 835     }
 836     return 0;
 837 }
 838
 839 static int vmdk_write(BlockDriverState *bs, int64_t sector_num,
 840                      const uint8_t *buf, int nb_sectors)
 841 {
 842     BDRVVmdkState *s = bs->opaque;
 843     VmdkExtent *extent = NULL;
 844     int n;
 845     int64_t index_in_cluster;
 846     uint64_t cluster_offset;
 847     static int cid_update = 0;
 848     VmdkMetaData m_data;
 849
 850     if (sector_num > bs->total_sectors) {
 851         fprintf(stderr,
 852                 "(VMDK) Wrong offset: sector_num=0x%" PRIx64
 853                 " total_sectors=0x%" PRIx64 "\n",
 854                 sector_num, bs->total_sectors);
 855         return -1;
 856     }
 857
 858     while (nb_sectors > 0) {
 859         extent = find_extent(s, sector_num, extent);
 860         if (!extent) {
 861             return -EIO;
 862         }
 863         cluster_offset = get_cluster_offset(
 864                                 bs,
 865                                 extent,
 866                                 &m_data,
 867                                 sector_num << 9, 1);
 868         if (!cluster_offset) {
 869             return -1;
 870         }
 871         index_in_cluster = sector_num % extent->cluster_sectors;
 872         n = extent->cluster_sectors - index_in_cluster;
 873         if (n > nb_sectors) {
 874             n = nb_sectors;
 875         }
 876
 877         if (bdrv_pwrite(bs->file,
 878                         cluster_offset + index_in_cluster * 512,
 879                         buf, n * 512)
 880                 != n * 512) {
 881             return -1;
 882         }
 883         if (m_data.valid) {
 884             /* update L2 tables */
 885             if (vmdk_L2update(extent, &m_data) == -1) {
 886                 return -1;
 887             }
 888         }
 889         nb_sectors -= n;
 890         sector_num += n;
 891         buf += n * 512;
 892
 893         // update CID on the first write every time the virtual disk is opened
 894         if (!cid_update) {
 895             vmdk_write_cid(bs, time(NULL));
 896             cid_update++;
 897         }
 898     }
 899     return 0;
 900 }
 901
 902 static int vmdk_create(const char *filename, QEMUOptionParameter *options)
 903 {
 904     int fd, i;
 905     VMDK4Header header;
 906     uint32_t tmp, magic, grains, gd_size, gt_size, gt_count;
 907     static const char desc_template[] =
 908         "# Disk DescriptorFile\n"
 909         "version=1\n"
 910         "CID=%x\n"
 911         "parentCID=ffffffff\n"
 912         "createType=\"monolithicSparse\"\n"
 913         "\n"
 914         "# Extent description\n"
 915         "RW %" PRId64 " SPARSE \"%s\"\n"
 916         "\n"
 917         "# The Disk Data Base \n"
 918         "#DDB\n"
 919         "\n"
 920         "ddb.virtualHWVersion = \"%d\"\n"
 921         "ddb.geometry.cylinders = \"%" PRId64 "\"\n"
 922         "ddb.geometry.heads = \"16\"\n"
 923         "ddb.geometry.sectors = \"63\"\n"
 924         "ddb.adapterType = \"ide\"\n";
 925     char desc[1024];
 926     const char *real_filename, *temp_str;
 927     int64_t total_size = 0;
 928     const char *backing_file = NULL;
 929     int flags = 0;
 930     int ret;
 931
 932     // Read out options
 933     while (options && options->name) {
 934         if (!strcmp(options->name, BLOCK_OPT_SIZE)) {
 935             total_size = options->value.n / 512;
 936         } else if (!strcmp(options->name, BLOCK_OPT_BACKING_FILE)) {
 937             backing_file = options->value.s;
 938         } else if (!strcmp(options->name, BLOCK_OPT_COMPAT6)) {
 939             flags |= options->value.n ? BLOCK_FLAG_COMPAT6: 0;
 940         }
 941         options++;
 942     }
 943
 944     /* XXX: add support for backing file */
 945     if (backing_file) {
 946         return vmdk_snapshot_create(filename, backing_file);
 947     }
 948
 949     fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC | O_BINARY | O_LARGEFILE,
 950               0644);
 951     if (fd < 0)
 952         return -errno;
 953     magic = cpu_to_be32(VMDK4_MAGIC);
 954     memset(&header, 0, sizeof(header));
 955     header.version = 1;
 956     header.flags = 3; /* ?? */
 957     header.capacity = total_size;
 958     header.granularity = 128;
 959     header.num_gtes_per_gte = 512;
 960
 961     grains = (total_size + header.granularity - 1) / header.granularity;
 962     gt_size = ((header.num_gtes_per_gte * sizeof(uint32_t)) + 511) >> 9;
 963     gt_count = (grains + header.num_gtes_per_gte - 1) / header.num_gtes_per_gte;
 964     gd_size = (gt_count * sizeof(uint32_t) + 511) >> 9;
 965
 966     header.desc_offset = 1;
 967     header.desc_size = 20;
 968     header.rgd_offset = header.desc_offset + header.desc_size;
 969     header.gd_offset = header.rgd_offset + gd_size + (gt_size * gt_count);
 970     header.grain_offset =
 971        ((header.gd_offset + gd_size + (gt_size * gt_count) +
 972          header.granularity - 1) / header.granularity) *
 973         header.granularity;
 974
 975     /* swap endianness for all header fields */
 976     header.version = cpu_to_le32(header.version);
 977     header.flags = cpu_to_le32(header.flags);
 978     header.capacity = cpu_to_le64(header.capacity);
 979     header.granularity = cpu_to_le64(header.granularity);
 980     header.num_gtes_per_gte = cpu_to_le32(header.num_gtes_per_gte);
 981     header.desc_offset = cpu_to_le64(header.desc_offset);
 982     header.desc_size = cpu_to_le64(header.desc_size);
 983     header.rgd_offset = cpu_to_le64(header.rgd_offset);
 984     header.gd_offset = cpu_to_le64(header.gd_offset);
 985     header.grain_offset = cpu_to_le64(header.grain_offset);
 986
 987     header.check_bytes[0] = 0xa;
 988     header.check_bytes[1] = 0x20;
 989     header.check_bytes[2] = 0xd;
 990     header.check_bytes[3] = 0xa;
 991
 992     /* write all the data */
 993     ret = qemu_write_full(fd, &magic, sizeof(magic));
 994     if (ret != sizeof(magic)) {
 995         ret = -errno;
 996         goto exit;
 997     }
 998     ret = qemu_write_full(fd, &header, sizeof(header));
 999     if (ret != sizeof(header)) {
1000         ret = -errno;
1001         goto exit;
1002     }
1003
1004     ret = ftruncate(fd, le64_to_cpu(header.grain_offset) << 9);
1005     if (ret < 0) {
1006         ret = -errno;
1007         goto exit;
1008     }
1009
1010     /* write grain directory */
1011     lseek(fd, le64_to_cpu(header.rgd_offset) << 9, SEEK_SET);
1012     for (i = 0, tmp = le64_to_cpu(header.rgd_offset) + gd_size;
1013          i < gt_count; i++, tmp += gt_size) {
1014         ret = qemu_write_full(fd, &tmp, sizeof(tmp));
1015         if (ret != sizeof(tmp)) {
1016             ret = -errno;
1017             goto exit;
1018         }
1019     }
1020
1021     /* write backup grain directory */
1022     lseek(fd, le64_to_cpu(header.gd_offset) << 9, SEEK_SET);
1023     for (i = 0, tmp = le64_to_cpu(header.gd_offset) + gd_size;
1024          i < gt_count; i++, tmp += gt_size) {
1025         ret = qemu_write_full(fd, &tmp, sizeof(tmp));
1026         if (ret != sizeof(tmp)) {
1027             ret = -errno;
1028             goto exit;
1029         }
1030     }
1031
1032     /* compose the descriptor */
1033     real_filename = filename;
1034     if ((temp_str = strrchr(real_filename, '\\')) != NULL)
1035         real_filename = temp_str + 1;
1036     if ((temp_str = strrchr(real_filename, '/')) != NULL)
1037         real_filename = temp_str + 1;
1038     if ((temp_str = strrchr(real_filename, ':')) != NULL)
1039         real_filename = temp_str + 1;
1040     snprintf(desc, sizeof(desc), desc_template, (unsigned int)time(NULL),
1041              total_size, real_filename,
1042              (flags & BLOCK_FLAG_COMPAT6 ? 6 : 4),
1043              total_size / (int64_t)(63 * 16));
1044
1045     /* write the descriptor */
1046     lseek(fd, le64_to_cpu(header.desc_offset) << 9, SEEK_SET);
1047     ret = qemu_write_full(fd, desc, strlen(desc));
1048     if (ret != strlen(desc)) {
1049         ret = -errno;
1050         goto exit;
1051     }
1052
1053     ret = 0;
1054 exit:
1055     close(fd);
1056     return ret;
1057 }
1058
1059 static void vmdk_close(BlockDriverState *bs)
1060 {
1061     vmdk_free_extents(bs);
1062 }
1063
1064 static int vmdk_flush(BlockDriverState *bs)
1065 {
1066     return bdrv_flush(bs->file);
1067 }
1068
1069
1070 static QEMUOptionParameter vmdk_create_options[] = {
1071     {
1072         .name = BLOCK_OPT_SIZE,
1073         .type = OPT_SIZE,
1074         .help = "Virtual disk size"
1075     },
1076     {
1077         .name = BLOCK_OPT_BACKING_FILE,
1078         .type = OPT_STRING,
1079         .help = "File name of a base image"
1080     },
1081     {
1082         .name = BLOCK_OPT_COMPAT6,
1083         .type = OPT_FLAG,
1084         .help = "VMDK version 6 image"
1085     },
1086     { NULL }
1087 };
1088
1089 static BlockDriver bdrv_vmdk = {
1090     .format_name        = "vmdk",
1091     .instance_size      = sizeof(BDRVVmdkState),
1092     .bdrv_probe         = vmdk_probe,
1093     .bdrv_open      = vmdk_open,
1094     .bdrv_read          = vmdk_read,
1095     .bdrv_write         = vmdk_write,
1096     .bdrv_close         = vmdk_close,
1097     .bdrv_create        = vmdk_create,
1098     .bdrv_flush         = vmdk_flush,
1099     .bdrv_is_allocated  = vmdk_is_allocated,
1100
1101     .create_options = vmdk_create_options,
1102 };
1103
1104 static void bdrv_vmdk_init(void)
1105 {
1106     bdrv_register(&bdrv_vmdk);
1107 }
1108
1109 block_init(bdrv_vmdk_init);