/*
 * Block driver for Connectix / Microsoft Virtual PC images
 *
 * Copyright (c) 2005 Alex Beregszaszi
 * Copyright (c) 2009 Kevin Wolf <kwolf@suse.de>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#include "qemu/osdep.h"
#include "qapi/error.h"
#include "qemu-common.h"
#include "block/block_int.h"
#include "sysemu/block-backend.h"
#include "qemu/module.h"
#include "migration/migration.h"
#if defined(CONFIG_UUID)
#include <uuid/uuid.h>
#endif

/**************************************************************/

#define HEADER_SIZE 512

//#define CACHE

enum vhd_type {
    VHD_FIXED           = 2,
    VHD_DYNAMIC         = 3,
    VHD_DIFFERENCING    = 4,
};

// Seconds since Jan 1, 2000 0:00:00 (UTC)
#define VHD_TIMESTAMP_BASE 946684800

#define VHD_CHS_MAX_C   65535LL
#define VHD_CHS_MAX_H   16
#define VHD_CHS_MAX_S   255

#define VHD_MAX_SECTORS       (65535LL * 255 * 255)
#define VHD_MAX_GEOMETRY      (VHD_CHS_MAX_C * VHD_CHS_MAX_H * VHD_CHS_MAX_S)

#define VPC_OPT_FORCE_SIZE "force_size"

// always big-endian
typedef struct vhd_footer {
    char        creator[8]; // "conectix"
    uint32_t    features;
    uint32_t    version;

    // Offset of next header structure, 0xFFFFFFFF if none
    uint64_t    data_offset;

    // Seconds since Jan 1, 2000 0:00:00 (UTC)
    uint32_t    timestamp;

    char        creator_app[4]; // "vpc "
    uint16_t    major;
    uint16_t    minor;
    char        creator_os[4]; // "Wi2k"

    uint64_t    orig_size;
    uint64_t    current_size;

    uint16_t    cyls;
    uint8_t     heads;
    uint8_t     secs_per_cyl;

    uint32_t    type;

    // Checksum of the Hard Disk Footer ("one's complement of the sum of all
    // the bytes in the footer without the checksum field")
    uint32_t    checksum;

    // UUID used to identify a parent hard disk (backing file)
    uint8_t     uuid[16];

    uint8_t     in_saved_state;
} QEMU_PACKED VHDFooter;

typedef struct vhd_dyndisk_header {
    char        magic[8]; // "cxsparse"

    // Offset of next header structure, 0xFFFFFFFF if none
    uint64_t    data_offset;

    // Offset of the Block Allocation Table (BAT)
    uint64_t    table_offset;

    uint32_t    version;
    uint32_t    max_table_entries; // 32bit/entry

    // 2 MB by default, must be a power of two
    uint32_t    block_size;

    uint32_t    checksum;
    uint8_t     parent_uuid[16];
    uint32_t    parent_timestamp;
    uint32_t    reserved;

    // Backing file name (in UTF-16)
    uint8_t     parent_name[512];

    struct {
        uint32_t    platform;
        uint32_t    data_space;
        uint32_t    data_length;
        uint32_t    reserved;
        uint64_t    data_offset;
    } parent_locator[8];
} QEMU_PACKED VHDDynDiskHeader;

typedef struct BDRVVPCState {
    CoMutex lock;
    uint8_t footer_buf[HEADER_SIZE];
    uint64_t free_data_block_offset;
    int max_table_entries;
    uint32_t *pagetable;
    uint64_t bat_offset;
    uint64_t last_bitmap_offset;

    uint32_t block_size;
    uint32_t bitmap_size;
    bool force_use_chs;
    bool force_use_sz;

#ifdef CACHE
    uint8_t *pageentry_u8;
    uint32_t *pageentry_u32;
    uint16_t *pageentry_u16;

    uint64_t last_bitmap;
#endif

    Error *migration_blocker;
} BDRVVPCState;

#define VPC_OPT_SIZE_CALC "force_size_calc"
static QemuOptsList vpc_runtime_opts = {
    .name = "vpc-runtime-opts",
    .head = QTAILQ_HEAD_INITIALIZER(vpc_runtime_opts.head),
    .desc = {
        {
            .name = VPC_OPT_SIZE_CALC,
            .type = QEMU_OPT_STRING,
            .help = "Force disk size calculation to use either CHS geometry, "
                    "or use the disk current_size specified in the VHD footer. "
                    "{chs, current_size}"
        },
        { /* end of list */ }
    }
};

static uint32_t vpc_checksum(uint8_t* buf, size_t size)
{
    uint32_t res = 0;
    int i;

    for (i = 0; i < size; i++)
        res += buf[i];

    return ~res;
}


static int vpc_probe(const uint8_t *buf, int buf_size, const char *filename)
{
    if (buf_size >= 8 && !strncmp((char *)buf, "conectix", 8))
	return 100;
    return 0;
}

static void vpc_parse_options(BlockDriverState *bs, QemuOpts *opts,
                              Error **errp)
{
    BDRVVPCState *s = bs->opaque;
    const char *size_calc;

    size_calc = qemu_opt_get(opts, VPC_OPT_SIZE_CALC);

    if (!size_calc) {
       /* no override, use autodetect only */
    } else if (!strcmp(size_calc, "current_size")) {
        s->force_use_sz = true;
    } else if (!strcmp(size_calc, "chs")) {
        s->force_use_chs = true;
    } else {
        error_setg(errp, "Invalid size calculation mode: '%s'", size_calc);
    }
}

static int vpc_open(BlockDriverState *bs, QDict *options, int flags,
                    Error **errp)
{
    BDRVVPCState *s = bs->opaque;
    int i;
    VHDFooter *footer;
    VHDDynDiskHeader *dyndisk_header;
    QemuOpts *opts = NULL;
    Error *local_err = NULL;
    bool use_chs;
    uint8_t buf[HEADER_SIZE];
    uint32_t checksum;
    uint64_t computed_size;
    uint64_t pagetable_size;
    int disk_type = VHD_DYNAMIC;
    int ret;

    opts = qemu_opts_create(&vpc_runtime_opts, NULL, 0, &error_abort);
    qemu_opts_absorb_qdict(opts, options, &local_err);
    if (local_err) {
        error_propagate(errp, local_err);
        ret = -EINVAL;
        goto fail;
    }

    vpc_parse_options(bs, opts, &local_err);
    if (local_err) {
        error_propagate(errp, local_err);
        ret = -EINVAL;
        goto fail;
    }

    ret = bdrv_pread(bs->file->bs, 0, s->footer_buf, HEADER_SIZE);
    if (ret < 0) {
        goto fail;
    }

    footer = (VHDFooter *) s->footer_buf;
    if (strncmp(footer->creator, "conectix", 8)) {
        int64_t offset = bdrv_getlength(bs->file->bs);
        if (offset < 0) {
            ret = offset;
            goto fail;
        } else if (offset < HEADER_SIZE) {
            ret = -EINVAL;
            goto fail;
        }

        /* If a fixed disk, the footer is found only at the end of the file */
        ret = bdrv_pread(bs->file->bs, offset-HEADER_SIZE, s->footer_buf,
                         HEADER_SIZE);
        if (ret < 0) {
            goto fail;
        }
        if (strncmp(footer->creator, "conectix", 8)) {
            error_setg(errp, "invalid VPC image");
            ret = -EINVAL;
            goto fail;
        }
        disk_type = VHD_FIXED;
    }

    checksum = be32_to_cpu(footer->checksum);
    footer->checksum = 0;
    if (vpc_checksum(s->footer_buf, HEADER_SIZE) != checksum)
        fprintf(stderr, "block-vpc: The header checksum of '%s' is "
            "incorrect.\n", bs->filename);

    /* Write 'checksum' back to footer, or else will leave it with zero. */
    footer->checksum = cpu_to_be32(checksum);

    // The visible size of a image in Virtual PC depends on the geometry
    // rather than on the size stored in the footer (the size in the footer
    // is too large usually)
    bs->total_sectors = (int64_t)
        be16_to_cpu(footer->cyls) * footer->heads * footer->secs_per_cyl;

    /* Microsoft Virtual PC and Microsoft Hyper-V produce and read
     * VHD image sizes differently.  VPC will rely on CHS geometry,
     * while Hyper-V and disk2vhd use the size specified in the footer.
     *
     * We use a couple of approaches to try and determine the correct method:
     * look at the Creator App field, and look for images that have CHS
     * geometry that is the maximum value.
     *
     * If the CHS geometry is the maximum CHS geometry, then we assume that
     * the size is the footer->current_size to avoid truncation.  Otherwise,
     * we follow the table based on footer->creator_app:
     *
     *  Known creator apps:
     *      'vpc '  :  CHS              Virtual PC (uses disk geometry)
     *      'qemu'  :  CHS              QEMU (uses disk geometry)
     *      'qem2'  :  current_size     QEMU (uses current_size)
     *      'win '  :  current_size     Hyper-V
     *      'd2v '  :  current_size     Disk2vhd
     *
     *  The user can override the table values via drive options, however
     *  even with an override we will still use current_size for images
     *  that have CHS geometry of the maximum size.
     */
    use_chs = (!!strncmp(footer->creator_app, "win ", 4) &&
               !!strncmp(footer->creator_app, "qem2", 4) &&
               !!strncmp(footer->creator_app, "d2v ", 4)) || s->force_use_chs;

    if (!use_chs || bs->total_sectors == VHD_MAX_GEOMETRY || s->force_use_sz) {
        bs->total_sectors = be64_to_cpu(footer->current_size) /
                                        BDRV_SECTOR_SIZE;
    }

    /* Allow a maximum disk size of approximately 2 TB */
    if (bs->total_sectors >= VHD_MAX_SECTORS) {
        ret = -EFBIG;
        goto fail;
    }

    if (disk_type == VHD_DYNAMIC) {
        ret = bdrv_pread(bs->file->bs, be64_to_cpu(footer->data_offset), buf,
                         HEADER_SIZE);
        if (ret < 0) {
            goto fail;
        }

        dyndisk_header = (VHDDynDiskHeader *) buf;

        if (strncmp(dyndisk_header->magic, "cxsparse", 8)) {
            ret = -EINVAL;
            goto fail;
        }

        s->block_size = be32_to_cpu(dyndisk_header->block_size);
        if (!is_power_of_2(s->block_size) || s->block_size < BDRV_SECTOR_SIZE) {
            error_setg(errp, "Invalid block size %" PRIu32, s->block_size);
            ret = -EINVAL;
            goto fail;
        }
        s->bitmap_size = ((s->block_size / (8 * 512)) + 511) & ~511;

        s->max_table_entries = be32_to_cpu(dyndisk_header->max_table_entries);

        if ((bs->total_sectors * 512) / s->block_size > 0xffffffffU) {
            ret = -EINVAL;
            goto fail;
        }
        if (s->max_table_entries > (VHD_MAX_SECTORS * 512) / s->block_size) {
            ret = -EINVAL;
            goto fail;
        }

        computed_size = (uint64_t) s->max_table_entries * s->block_size;
        if (computed_size < bs->total_sectors * 512) {
            ret = -EINVAL;
            goto fail;
        }

        if (s->max_table_entries > SIZE_MAX / 4 ||
            s->max_table_entries > (int) INT_MAX / 4) {
            error_setg(errp, "Max Table Entries too large (%" PRId32 ")",
                        s->max_table_entries);
            ret = -EINVAL;
            goto fail;
        }

        pagetable_size = (uint64_t) s->max_table_entries * 4;

        s->pagetable = qemu_try_blockalign(bs->file->bs, pagetable_size);
        if (s->pagetable == NULL) {
            ret = -ENOMEM;
            goto fail;
        }

        s->bat_offset = be64_to_cpu(dyndisk_header->table_offset);

        ret = bdrv_pread(bs->file->bs, s->bat_offset, s->pagetable,
                         pagetable_size);
        if (ret < 0) {
            goto fail;
        }

        s->free_data_block_offset =
            ROUND_UP(s->bat_offset + pagetable_size, 512);

        for (i = 0; i < s->max_table_entries; i++) {
            be32_to_cpus(&s->pagetable[i]);
            if (s->pagetable[i] != 0xFFFFFFFF) {
                int64_t next = (512 * (int64_t) s->pagetable[i]) +
                    s->bitmap_size + s->block_size;

                if (next > s->free_data_block_offset) {
                    s->free_data_block_offset = next;
                }
            }
        }

        if (s->free_data_block_offset > bdrv_getlength(bs->file->bs)) {
            error_setg(errp, "block-vpc: free_data_block_offset points after "
                             "the end of file. The image has been truncated.");
            ret = -EINVAL;
            goto fail;
        }

        s->last_bitmap_offset = (int64_t) -1;

#ifdef CACHE
        s->pageentry_u8 = g_malloc(512);
        s->pageentry_u32 = s->pageentry_u8;
        s->pageentry_u16 = s->pageentry_u8;
        s->last_pagetable = -1;
#endif
    }

    qemu_co_mutex_init(&s->lock);

    /* Disable migration when VHD images are used */
    error_setg(&s->migration_blocker, "The vpc format used by node '%s' "
               "does not support live migration",
               bdrv_get_device_or_node_name(bs));
    migrate_add_blocker(s->migration_blocker);

    return 0;

fail:
    qemu_vfree(s->pagetable);
#ifdef CACHE
    g_free(s->pageentry_u8);
#endif
    return ret;
}

static int vpc_reopen_prepare(BDRVReopenState *state,
                              BlockReopenQueue *queue, Error **errp)
{
    return 0;
}

/*
 * Returns the absolute byte offset of the given sector in the image file.
 * If the sector is not allocated, -1 is returned instead.
 *
 * The parameter write must be 1 if the offset will be used for a write
 * operation (the block bitmaps is updated then), 0 otherwise.
 */
static inline int64_t get_sector_offset(BlockDriverState *bs,
    int64_t sector_num, int write)
{
    BDRVVPCState *s = bs->opaque;
    uint64_t offset = sector_num * 512;
    uint64_t bitmap_offset, block_offset;
    uint32_t pagetable_index, pageentry_index;

    pagetable_index = offset / s->block_size;
    pageentry_index = (offset % s->block_size) / 512;

    if (pagetable_index >= s->max_table_entries || s->pagetable[pagetable_index] == 0xffffffff)
        return -1; // not allocated

    bitmap_offset = 512 * (uint64_t) s->pagetable[pagetable_index];
    block_offset = bitmap_offset + s->bitmap_size + (512 * pageentry_index);

    // We must ensure that we don't write to any sectors which are marked as
    // unused in the bitmap. We get away with setting all bits in the block
    // bitmap each time we write to a new block. This might cause Virtual PC to
    // miss sparse read optimization, but it's not a problem in terms of
    // correctness.
    if (write && (s->last_bitmap_offset != bitmap_offset)) {
        uint8_t bitmap[s->bitmap_size];

        s->last_bitmap_offset = bitmap_offset;
        memset(bitmap, 0xff, s->bitmap_size);
        bdrv_pwrite_sync(bs->file->bs, bitmap_offset, bitmap, s->bitmap_size);
    }

    return block_offset;
}

/*
 * Writes the footer to the end of the image file. This is needed when the
 * file grows as it overwrites the old footer
 *
 * Returns 0 on success and < 0 on error
 */
static int rewrite_footer(BlockDriverState* bs)
{
    int ret;
    BDRVVPCState *s = bs->opaque;
    int64_t offset = s->free_data_block_offset;

    ret = bdrv_pwrite_sync(bs->file->bs, offset, s->footer_buf, HEADER_SIZE);
    if (ret < 0)
        return ret;

    return 0;
}

/*
 * Allocates a new block. This involves writing a new footer and updating
 * the Block Allocation Table to use the space at the old end of the image
 * file (overwriting the old footer)
 *
 * Returns the sectors' offset in the image file on success and < 0 on error
 */
static int64_t alloc_block(BlockDriverState* bs, int64_t sector_num)
{
    BDRVVPCState *s = bs->opaque;
    int64_t bat_offset;
    uint32_t index, bat_value;
    int ret;
    uint8_t bitmap[s->bitmap_size];

    // Check if sector_num is valid
    if ((sector_num < 0) || (sector_num > bs->total_sectors))
        return -1;

    // Write entry into in-memory BAT
    index = (sector_num * 512) / s->block_size;
    if (s->pagetable[index] != 0xFFFFFFFF)
        return -1;

    s->pagetable[index] = s->free_data_block_offset / 512;

    // Initialize the block's bitmap
    memset(bitmap, 0xff, s->bitmap_size);
    ret = bdrv_pwrite_sync(bs->file->bs, s->free_data_block_offset, bitmap,
        s->bitmap_size);
    if (ret < 0) {
        return ret;
    }

    // Write new footer (the old one will be overwritten)
    s->free_data_block_offset += s->block_size + s->bitmap_size;
    ret = rewrite_footer(bs);
    if (ret < 0)
        goto fail;

    // Write BAT entry to disk
    bat_offset = s->bat_offset + (4 * index);
    bat_value = cpu_to_be32(s->pagetable[index]);
    ret = bdrv_pwrite_sync(bs->file->bs, bat_offset, &bat_value, 4);
    if (ret < 0)
        goto fail;

    return get_sector_offset(bs, sector_num, 0);

fail:
    s->free_data_block_offset -= (s->block_size + s->bitmap_size);
    return -1;
}

static int vpc_get_info(BlockDriverState *bs, BlockDriverInfo *bdi)
{
    BDRVVPCState *s = (BDRVVPCState *)bs->opaque;
    VHDFooter *footer = (VHDFooter *) s->footer_buf;

    if (be32_to_cpu(footer->type) != VHD_FIXED) {
        bdi->cluster_size = s->block_size;
    }

    bdi->unallocated_blocks_are_zero = true;
    return 0;
}

static int vpc_read(BlockDriverState *bs, int64_t sector_num,
                    uint8_t *buf, int nb_sectors)
{
    BDRVVPCState *s = bs->opaque;
    int ret;
    int64_t offset;
    int64_t sectors, sectors_per_block;
    VHDFooter *footer = (VHDFooter *) s->footer_buf;

    if (be32_to_cpu(footer->type) == VHD_FIXED) {
        return bdrv_read(bs->file->bs, sector_num, buf, nb_sectors);
    }
    while (nb_sectors > 0) {
        offset = get_sector_offset(bs, sector_num, 0);

        sectors_per_block = s->block_size >> BDRV_SECTOR_BITS;
        sectors = sectors_per_block - (sector_num % sectors_per_block);
        if (sectors > nb_sectors) {
            sectors = nb_sectors;
        }

        if (offset == -1) {
            memset(buf, 0, sectors * BDRV_SECTOR_SIZE);
        } else {
            ret = bdrv_pread(bs->file->bs, offset, buf,
                sectors * BDRV_SECTOR_SIZE);
            if (ret != sectors * BDRV_SECTOR_SIZE) {
                return -1;
            }
        }

        nb_sectors -= sectors;
        sector_num += sectors;
        buf += sectors * BDRV_SECTOR_SIZE;
    }
    return 0;
}

static coroutine_fn int vpc_co_read(BlockDriverState *bs, int64_t sector_num,
                                    uint8_t *buf, int nb_sectors)
{
    int ret;
    BDRVVPCState *s = bs->opaque;
    qemu_co_mutex_lock(&s->lock);
    ret = vpc_read(bs, sector_num, buf, nb_sectors);
    qemu_co_mutex_unlock(&s->lock);
    return ret;
}

static int vpc_write(BlockDriverState *bs, int64_t sector_num,
    const uint8_t *buf, int nb_sectors)
{
    BDRVVPCState *s = bs->opaque;
    int64_t offset;
    int64_t sectors, sectors_per_block;
    int ret;
    VHDFooter *footer =  (VHDFooter *) s->footer_buf;

    if (be32_to_cpu(footer->type) == VHD_FIXED) {
        return bdrv_write(bs->file->bs, sector_num, buf, nb_sectors);
    }
    while (nb_sectors > 0) {
        offset = get_sector_offset(bs, sector_num, 1);

        sectors_per_block = s->block_size >> BDRV_SECTOR_BITS;
        sectors = sectors_per_block - (sector_num % sectors_per_block);
        if (sectors > nb_sectors) {
            sectors = nb_sectors;
        }

        if (offset == -1) {
            offset = alloc_block(bs, sector_num);
            if (offset < 0)
                return -1;
        }

        ret = bdrv_pwrite(bs->file->bs, offset, buf,
                          sectors * BDRV_SECTOR_SIZE);
        if (ret != sectors * BDRV_SECTOR_SIZE) {
            return -1;
        }

        nb_sectors -= sectors;
        sector_num += sectors;
        buf += sectors * BDRV_SECTOR_SIZE;
    }

    return 0;
}

static coroutine_fn int vpc_co_write(BlockDriverState *bs, int64_t sector_num,
                                     const uint8_t *buf, int nb_sectors)
{
    int ret;
    BDRVVPCState *s = bs->opaque;
    qemu_co_mutex_lock(&s->lock);
    ret = vpc_write(bs, sector_num, buf, nb_sectors);
    qemu_co_mutex_unlock(&s->lock);
    return ret;
}

static int64_t coroutine_fn vpc_co_get_block_status(BlockDriverState *bs,
        int64_t sector_num, int nb_sectors, int *pnum, BlockDriverState **file)
{
    BDRVVPCState *s = bs->opaque;
    VHDFooter *footer = (VHDFooter*) s->footer_buf;
    int64_t start, offset;
    bool allocated;
    int n;

    if (be32_to_cpu(footer->type) == VHD_FIXED) {
        *pnum = nb_sectors;
        *file = bs->file->bs;
        return BDRV_BLOCK_RAW | BDRV_BLOCK_OFFSET_VALID | BDRV_BLOCK_DATA |
               (sector_num << BDRV_SECTOR_BITS);
    }

    offset = get_sector_offset(bs, sector_num, 0);
    start = offset;
    allocated = (offset != -1);
    *pnum = 0;

    do {
        /* All sectors in a block are contiguous (without using the bitmap) */
        n = ROUND_UP(sector_num + 1, s->block_size / BDRV_SECTOR_SIZE)
          - sector_num;
        n = MIN(n, nb_sectors);

        *pnum += n;
        sector_num += n;
        nb_sectors -= n;
        /* *pnum can't be greater than one block for allocated
         * sectors since there is always a bitmap in between. */
        if (allocated) {
            *file = bs->file->bs;
            return BDRV_BLOCK_DATA | BDRV_BLOCK_OFFSET_VALID | start;
        }
        if (nb_sectors == 0) {
            break;
        }
        offset = get_sector_offset(bs, sector_num, 0);
    } while (offset == -1);

    return 0;
}

/*
 * Calculates the number of cylinders, heads and sectors per cylinder
 * based on a given number of sectors. This is the algorithm described
 * in the VHD specification.
 *
 * Note that the geometry doesn't always exactly match total_sectors but
 * may round it down.
 *
 * Returns 0 on success, -EFBIG if the size is larger than ~2 TB. Override
 * the hardware EIDE and ATA-2 limit of 16 heads (max disk size of 127 GB)
 * and instead allow up to 255 heads.
 */
static int calculate_geometry(int64_t total_sectors, uint16_t* cyls,
    uint8_t* heads, uint8_t* secs_per_cyl)
{
    uint32_t cyls_times_heads;

    total_sectors = MIN(total_sectors, VHD_MAX_GEOMETRY);

    if (total_sectors >= 65535LL * 16 * 63) {
        *secs_per_cyl = 255;
        *heads = 16;
        cyls_times_heads = total_sectors / *secs_per_cyl;
    } else {
        *secs_per_cyl = 17;
        cyls_times_heads = total_sectors / *secs_per_cyl;
        *heads = (cyls_times_heads + 1023) / 1024;

        if (*heads < 4) {
            *heads = 4;
        }

        if (cyls_times_heads >= (*heads * 1024) || *heads > 16) {
            *secs_per_cyl = 31;
            *heads = 16;
            cyls_times_heads = total_sectors / *secs_per_cyl;
        }

        if (cyls_times_heads >= (*heads * 1024)) {
            *secs_per_cyl = 63;
            *heads = 16;
            cyls_times_heads = total_sectors / *secs_per_cyl;
        }
    }

    *cyls = cyls_times_heads / *heads;

    return 0;
}

static int create_dynamic_disk(BlockBackend *blk, uint8_t *buf,
                               int64_t total_sectors)
{
    VHDDynDiskHeader *dyndisk_header =
        (VHDDynDiskHeader *) buf;
    size_t block_size, num_bat_entries;
    int i;
    int ret;
    int64_t offset = 0;

    // Write the footer (twice: at the beginning and at the end)
    block_size = 0x200000;
    num_bat_entries = (total_sectors + block_size / 512) / (block_size / 512);

    ret = blk_pwrite(blk, offset, buf, HEADER_SIZE);
    if (ret) {
        goto fail;
    }

    offset = 1536 + ((num_bat_entries * 4 + 511) & ~511);
    ret = blk_pwrite(blk, offset, buf, HEADER_SIZE);
    if (ret < 0) {
        goto fail;
    }

    // Write the initial BAT
    offset = 3 * 512;

    memset(buf, 0xFF, 512);
    for (i = 0; i < (num_bat_entries * 4 + 511) / 512; i++) {
        ret = blk_pwrite(blk, offset, buf, 512);
        if (ret < 0) {
            goto fail;
        }
        offset += 512;
    }

    // Prepare the Dynamic Disk Header
    memset(buf, 0, 1024);

    memcpy(dyndisk_header->magic, "cxsparse", 8);

    /*
     * Note: The spec is actually wrong here for data_offset, it says
     * 0xFFFFFFFF, but MS tools expect all 64 bits to be set.
     */
    dyndisk_header->data_offset = cpu_to_be64(0xFFFFFFFFFFFFFFFFULL);
    dyndisk_header->table_offset = cpu_to_be64(3 * 512);
    dyndisk_header->version = cpu_to_be32(0x00010000);
    dyndisk_header->block_size = cpu_to_be32(block_size);
    dyndisk_header->max_table_entries = cpu_to_be32(num_bat_entries);

    dyndisk_header->checksum = cpu_to_be32(vpc_checksum(buf, 1024));

    // Write the header
    offset = 512;

    ret = blk_pwrite(blk, offset, buf, 1024);
    if (ret < 0) {
        goto fail;
    }

 fail:
    return ret;
}

static int create_fixed_disk(BlockBackend *blk, uint8_t *buf,
                             int64_t total_size)
{
    int ret;

    /* Add footer to total size */
    total_size += HEADER_SIZE;

    ret = blk_truncate(blk, total_size);
    if (ret < 0) {
        return ret;
    }

    ret = blk_pwrite(blk, total_size - HEADER_SIZE, buf, HEADER_SIZE);
    if (ret < 0) {
        return ret;
    }

    return ret;
}

static int vpc_create(const char *filename, QemuOpts *opts, Error **errp)
{
    uint8_t buf[1024];
    VHDFooter *footer = (VHDFooter *) buf;
    char *disk_type_param;
    int i;
    uint16_t cyls = 0;
    uint8_t heads = 0;
    uint8_t secs_per_cyl = 0;
    int64_t total_sectors;
    int64_t total_size;
    int disk_type;
    int ret = -EIO;
    bool force_size;
    Error *local_err = NULL;
    BlockBackend *blk = NULL;

    /* Read out options */
    total_size = ROUND_UP(qemu_opt_get_size_del(opts, BLOCK_OPT_SIZE, 0),
                          BDRV_SECTOR_SIZE);
    disk_type_param = qemu_opt_get_del(opts, BLOCK_OPT_SUBFMT);
    if (disk_type_param) {
        if (!strcmp(disk_type_param, "dynamic")) {
            disk_type = VHD_DYNAMIC;
        } else if (!strcmp(disk_type_param, "fixed")) {
            disk_type = VHD_FIXED;
        } else {
            ret = -EINVAL;
            goto out;
        }
    } else {
        disk_type = VHD_DYNAMIC;
    }

    force_size = qemu_opt_get_bool_del(opts, VPC_OPT_FORCE_SIZE, false);

    ret = bdrv_create_file(filename, opts, &local_err);
    if (ret < 0) {
        error_propagate(errp, local_err);
        goto out;
    }

    blk = blk_new_open(filename, NULL, NULL,
                       BDRV_O_RDWR | BDRV_O_PROTOCOL, &local_err);
    if (blk == NULL) {
        error_propagate(errp, local_err);
        ret = -EIO;
        goto out;
    }

    blk_set_allow_write_beyond_eof(blk, true);

    /*
     * Calculate matching total_size and geometry. Increase the number of
     * sectors requested until we get enough (or fail). This ensures that
     * qemu-img convert doesn't truncate images, but rather rounds up.
     *
     * If the image size can't be represented by a spec conformant CHS geometry,
     * we set the geometry to 65535 x 16 x 255 (CxHxS) sectors and use
     * the image size from the VHD footer to calculate total_sectors.
     */
    if (force_size) {
        /* This will force the use of total_size for sector count, below */
        cyls         = VHD_CHS_MAX_C;
        heads        = VHD_CHS_MAX_H;
        secs_per_cyl = VHD_CHS_MAX_S;
    } else {
        total_sectors = MIN(VHD_MAX_GEOMETRY, total_size / BDRV_SECTOR_SIZE);
        for (i = 0; total_sectors > (int64_t)cyls * heads * secs_per_cyl; i++) {
            calculate_geometry(total_sectors + i, &cyls, &heads, &secs_per_cyl);
        }
    }

    if ((int64_t)cyls * heads * secs_per_cyl == VHD_MAX_GEOMETRY) {
        total_sectors = total_size / BDRV_SECTOR_SIZE;
        /* Allow a maximum disk size of approximately 2 TB */
        if (total_sectors > VHD_MAX_SECTORS) {
            ret = -EFBIG;
            goto out;
        }
    } else {
        total_sectors = (int64_t)cyls * heads * secs_per_cyl;
        total_size = total_sectors * BDRV_SECTOR_SIZE;
    }

    /* Prepare the Hard Disk Footer */
    memset(buf, 0, 1024);

    memcpy(footer->creator, "conectix", 8);
    if (force_size) {
        memcpy(footer->creator_app, "qem2", 4);
    } else {
        memcpy(footer->creator_app, "qemu", 4);
    }
    memcpy(footer->creator_os, "Wi2k", 4);

    footer->features = cpu_to_be32(0x02);
    footer->version = cpu_to_be32(0x00010000);
    if (disk_type == VHD_DYNAMIC) {
        footer->data_offset = cpu_to_be64(HEADER_SIZE);
    } else {
        footer->data_offset = cpu_to_be64(0xFFFFFFFFFFFFFFFFULL);
    }
    footer->timestamp = cpu_to_be32(time(NULL) - VHD_TIMESTAMP_BASE);

    /* Version of Virtual PC 2007 */
    footer->major = cpu_to_be16(0x0005);
    footer->minor = cpu_to_be16(0x0003);
    footer->orig_size = cpu_to_be64(total_size);
    footer->current_size = cpu_to_be64(total_size);
    footer->cyls = cpu_to_be16(cyls);
    footer->heads = heads;
    footer->secs_per_cyl = secs_per_cyl;

    footer->type = cpu_to_be32(disk_type);

#if defined(CONFIG_UUID)
    uuid_generate(footer->uuid);
#endif

    footer->checksum = cpu_to_be32(vpc_checksum(buf, HEADER_SIZE));

    if (disk_type == VHD_DYNAMIC) {
        ret = create_dynamic_disk(blk, buf, total_sectors);
    } else {
        ret = create_fixed_disk(blk, buf, total_size);
    }

out:
    blk_unref(blk);
    g_free(disk_type_param);
    return ret;
}

static int vpc_has_zero_init(BlockDriverState *bs)
{
    BDRVVPCState *s = bs->opaque;
    VHDFooter *footer =  (VHDFooter *) s->footer_buf;

    if (be32_to_cpu(footer->type) == VHD_FIXED) {
        return bdrv_has_zero_init(bs->file->bs);
    } else {
        return 1;
    }
}

static void vpc_close(BlockDriverState *bs)
{
    BDRVVPCState *s = bs->opaque;
    qemu_vfree(s->pagetable);
#ifdef CACHE
    g_free(s->pageentry_u8);
#endif

    migrate_del_blocker(s->migration_blocker);
    error_free(s->migration_blocker);
}

static QemuOptsList vpc_create_opts = {
    .name = "vpc-create-opts",
    .head = QTAILQ_HEAD_INITIALIZER(vpc_create_opts.head),
    .desc = {
        {
            .name = BLOCK_OPT_SIZE,
            .type = QEMU_OPT_SIZE,
            .help = "Virtual disk size"
        },
        {
            .name = BLOCK_OPT_SUBFMT,
            .type = QEMU_OPT_STRING,
            .help =
                "Type of virtual hard disk format. Supported formats are "
                "{dynamic (default) | fixed} "
        },
        {
            .name = VPC_OPT_FORCE_SIZE,
            .type = QEMU_OPT_BOOL,
            .help = "Force disk size calculation to use the actual size "
                    "specified, rather than using the nearest CHS-based "
                    "calculation"
        },
        { /* end of list */ }
    }
};

static BlockDriver bdrv_vpc = {
    .format_name    = "vpc",
    .instance_size  = sizeof(BDRVVPCState),

    .bdrv_probe             = vpc_probe,
    .bdrv_open              = vpc_open,
    .bdrv_close             = vpc_close,
    .bdrv_reopen_prepare    = vpc_reopen_prepare,
    .bdrv_create            = vpc_create,

    .bdrv_read                  = vpc_co_read,
    .bdrv_write                 = vpc_co_write,
    .bdrv_co_get_block_status   = vpc_co_get_block_status,

    .bdrv_get_info          = vpc_get_info,

    .create_opts            = &vpc_create_opts,
    .bdrv_has_zero_init     = vpc_has_zero_init,
};

static void bdrv_vpc_init(void)
{
    bdrv_register(&bdrv_vpc);
}

block_init(bdrv_vpc_init);