block/vvfat.c

   1 /* vim:set shiftwidth=4 ts=4: */
   2 /*
   3  * QEMU Block driver for virtual VFAT (shadows a local directory)
   4  *
   5  * Copyright (c) 2004,2005 Johannes E. Schindelin
   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/osdep.h"
  27 #include <dirent.h>
  28 #include "qapi/error.h"
  29 #include "block/block_int.h"
  30 #include "block/qdict.h"
  31 #include "qemu/module.h"
  32 #include "qemu/option.h"
  33 #include "qemu/bswap.h"
  34 #include "migration/blocker.h"
  35 #include "qapi/qmp/qdict.h"
  36 #include "qapi/qmp/qstring.h"
  37 #include "qemu/cutils.h"
  38 #include "qemu/error-report.h"
  39
  40 #ifndef S_IWGRP
  41 #define S_IWGRP 0
  42 #endif
  43 #ifndef S_IWOTH
  44 #define S_IWOTH 0
  45 #endif
  46
  47 /* TODO: add ":bootsector=blabla.img:" */
  48 /* LATER TODO: add automatic boot sector generation from
  49     BOOTEASY.ASM and Ranish Partition Manager
  50     Note that DOS assumes the system files to be the first files in the
  51     file system (test if the boot sector still relies on that fact)! */
  52 /* MAYBE TODO: write block-visofs.c */
  53 /* TODO: call try_commit() only after a timeout */
  54
  55 /* #define DEBUG */
  56
  57 #ifdef DEBUG
  58
  59 #define DLOG(a) a
  60
  61 static void checkpoint(void);
  62
  63 #else
  64
  65 #define DLOG(a)
  66
  67 #endif
  68
  69 /* bootsector OEM name. see related compatibility problems at:
  70  * https://jdebp.eu/FGA/volume-boot-block-oem-name-field.html
  71  * http://seasip.info/Misc/oemid.html
  72  */
  73 #define BOOTSECTOR_OEM_NAME "MSWIN4.1"
  74
  75 #define DIR_DELETED 0xe5
  76 #define DIR_KANJI DIR_DELETED
  77 #define DIR_KANJI_FAKE 0x05
  78 #define DIR_FREE 0x00
  79
  80 /* dynamic array functions */
  81 typedef struct array_t {
  82     char* pointer;
  83     unsigned int size,next,item_size;
  84 } array_t;
  85
  86 static inline void array_init(array_t* array,unsigned int item_size)
  87 {
  88     array->pointer = NULL;
  89     array->size=0;
  90     array->next=0;
  91     array->item_size=item_size;
  92 }
  93
  94 static inline void array_free(array_t* array)
  95 {
  96     g_free(array->pointer);
  97     array->size=array->next=0;
  98 }
  99
 100 /* does not automatically grow */
 101 static inline void* array_get(array_t* array,unsigned int index) {
 102     assert(index < array->next);
 103     return array->pointer + index * array->item_size;
 104 }
 105
 106 static inline int array_ensure_allocated(array_t* array, int index)
 107 {
 108     if((index + 1) * array->item_size > array->size) {
 109         int new_size = (index + 32) * array->item_size;
 110         array->pointer = g_realloc(array->pointer, new_size);
 111         if (!array->pointer)
 112             return -1;
 113         memset(array->pointer + array->size, 0, new_size - array->size);
 114         array->size = new_size;
 115         array->next = index + 1;
 116     }
 117
 118     return 0;
 119 }
 120
 121 static inline void* array_get_next(array_t* array) {
 122     unsigned int next = array->next;
 123
 124     if (array_ensure_allocated(array, next) < 0)
 125         return NULL;
 126
 127     array->next = next + 1;
 128     return array_get(array, next);
 129 }
 130
 131 static inline void* array_insert(array_t* array,unsigned int index,unsigned int count) {
 132     if((array->next+count)*array->item_size>array->size) {
 133         int increment=count*array->item_size;
 134         array->pointer=g_realloc(array->pointer,array->size+increment);
 135         if(!array->pointer)
 136             return NULL;
 137         array->size+=increment;
 138     }
 139     memmove(array->pointer+(index+count)*array->item_size,
 140                 array->pointer+index*array->item_size,
 141                 (array->next-index)*array->item_size);
 142     array->next+=count;
 143     return array->pointer+index*array->item_size;
 144 }
 145
 146 /* this performs a "roll", so that the element which was at index_from becomes
 147  * index_to, but the order of all other elements is preserved. */
 148 static inline int array_roll(array_t* array,int index_to,int index_from,int count)
 149 {
 150     char* buf;
 151     char* from;
 152     char* to;
 153     int is;
 154
 155     if(!array ||
 156             index_to<0 || index_to>=array->next ||
 157             index_from<0 || index_from>=array->next)
 158         return -1;
 159
 160     if(index_to==index_from)
 161         return 0;
 162
 163     is=array->item_size;
 164     from=array->pointer+index_from*is;
 165     to=array->pointer+index_to*is;
 166     buf=g_malloc(is*count);
 167     memcpy(buf,from,is*count);
 168
 169     if(index_to<index_from)
 170         memmove(to+is*count,to,from-to);
 171     else
 172         memmove(from,from+is*count,to-from);
 173
 174     memcpy(to,buf,is*count);
 175
 176     g_free(buf);
 177
 178     return 0;
 179 }
 180
 181 static inline int array_remove_slice(array_t* array,int index, int count)
 182 {
 183     assert(index >=0);
 184     assert(count > 0);
 185     assert(index + count <= array->next);
 186     if(array_roll(array,array->next-1,index,count))
 187         return -1;
 188     array->next -= count;
 189     return 0;
 190 }
 191
 192 static int array_remove(array_t* array,int index)
 193 {
 194     return array_remove_slice(array, index, 1);
 195 }
 196
 197 /* return the index for a given member */
 198 static int array_index(array_t* array, void* pointer)
 199 {
 200     size_t offset = (char*)pointer - array->pointer;
 201     assert((offset % array->item_size) == 0);
 202     assert(offset/array->item_size < array->next);
 203     return offset/array->item_size;
 204 }
 205
 206 /* These structures are used to fake a disk and the VFAT filesystem.
 207  * For this reason we need to use QEMU_PACKED. */
 208
 209 typedef struct bootsector_t {
 210     uint8_t jump[3];
 211     uint8_t name[8];
 212     uint16_t sector_size;
 213     uint8_t sectors_per_cluster;
 214     uint16_t reserved_sectors;
 215     uint8_t number_of_fats;
 216     uint16_t root_entries;
 217     uint16_t total_sectors16;
 218     uint8_t media_type;
 219     uint16_t sectors_per_fat;
 220     uint16_t sectors_per_track;
 221     uint16_t number_of_heads;
 222     uint32_t hidden_sectors;
 223     uint32_t total_sectors;
 224     union {
 225         struct {
 226             uint8_t drive_number;
 227             uint8_t reserved1;
 228             uint8_t signature;
 229             uint32_t id;
 230             uint8_t volume_label[11];
 231             uint8_t fat_type[8];
 232             uint8_t ignored[0x1c0];
 233         } QEMU_PACKED fat16;
 234         struct {
 235             uint32_t sectors_per_fat;
 236             uint16_t flags;
 237             uint8_t major,minor;
 238             uint32_t first_cluster_of_root_dir;
 239             uint16_t info_sector;
 240             uint16_t backup_boot_sector;
 241             uint8_t reserved[12];
 242             uint8_t drive_number;
 243             uint8_t reserved1;
 244             uint8_t signature;
 245             uint32_t id;
 246             uint8_t volume_label[11];
 247             uint8_t fat_type[8];
 248             uint8_t ignored[0x1a4];
 249         } QEMU_PACKED fat32;
 250     } u;
 251     uint8_t magic[2];
 252 } QEMU_PACKED bootsector_t;
 253
 254 typedef struct {
 255     uint8_t head;
 256     uint8_t sector;
 257     uint8_t cylinder;
 258 } mbr_chs_t;
 259
 260 typedef struct partition_t {
 261     uint8_t attributes; /* 0x80 = bootable */
 262     mbr_chs_t start_CHS;
 263     uint8_t   fs_type; /* 0x1 = FAT12, 0x6 = FAT16, 0xe = FAT16_LBA, 0xb = FAT32, 0xc = FAT32_LBA */
 264     mbr_chs_t end_CHS;
 265     uint32_t start_sector_long;
 266     uint32_t length_sector_long;
 267 } QEMU_PACKED partition_t;
 268
 269 typedef struct mbr_t {
 270     uint8_t ignored[0x1b8];
 271     uint32_t nt_id;
 272     uint8_t ignored2[2];
 273     partition_t partition[4];
 274     uint8_t magic[2];
 275 } QEMU_PACKED mbr_t;
 276
 277 typedef struct direntry_t {
 278     uint8_t name[8 + 3];
 279     uint8_t attributes;
 280     uint8_t reserved[2];
 281     uint16_t ctime;
 282     uint16_t cdate;
 283     uint16_t adate;
 284     uint16_t begin_hi;
 285     uint16_t mtime;
 286     uint16_t mdate;
 287     uint16_t begin;
 288     uint32_t size;
 289 } QEMU_PACKED direntry_t;
 290
 291 /* this structure are used to transparently access the files */
 292
 293 typedef struct mapping_t {
 294     /* begin is the first cluster, end is the last+1 */
 295     uint32_t begin,end;
 296     /* as s->directory is growable, no pointer may be used here */
 297     unsigned int dir_index;
 298     /* the clusters of a file may be in any order; this points to the first */
 299     int first_mapping_index;
 300     union {
 301         /* offset is
 302          * - the offset in the file (in clusters) for a file, or
 303          * - the next cluster of the directory for a directory
 304          */
 305         struct {
 306             uint32_t offset;
 307         } file;
 308         struct {
 309             int parent_mapping_index;
 310             int first_dir_index;
 311         } dir;
 312     } info;
 313     /* path contains the full path, i.e. it always starts with s->path */
 314     char* path;
 315
 316     enum {
 317         MODE_UNDEFINED = 0,
 318         MODE_NORMAL = 1,
 319         MODE_MODIFIED = 2,
 320         MODE_DIRECTORY = 4,
 321         MODE_DELETED = 8,
 322     } mode;
 323     int read_only;
 324 } mapping_t;
 325
 326 #ifdef DEBUG
 327 static void print_direntry(const struct direntry_t*);
 328 static void print_mapping(const struct mapping_t* mapping);
 329 #endif
 330
 331 /* here begins the real VVFAT driver */
 332
 333 typedef struct BDRVVVFATState {
 334     CoMutex lock;
 335     BlockDriverState* bs; /* pointer to parent */
 336     unsigned char first_sectors[0x40*0x200];
 337
 338     int fat_type; /* 16 or 32 */
 339     array_t fat,directory,mapping;
 340     char volume_label[11];
 341
 342     uint32_t offset_to_bootsector; /* 0 for floppy, 0x3f for disk */
 343
 344     unsigned int cluster_size;
 345     unsigned int sectors_per_cluster;
 346     unsigned int sectors_per_fat;
 347     uint32_t last_cluster_of_root_directory;
 348     /* how many entries are available in root directory (0 for FAT32) */
 349     uint16_t root_entries;
 350     uint32_t sector_count; /* total number of sectors of the partition */
 351     uint32_t cluster_count; /* total number of clusters of this partition */
 352     uint32_t max_fat_value;
 353     uint32_t offset_to_fat;
 354     uint32_t offset_to_root_dir;
 355
 356     int current_fd;
 357     mapping_t* current_mapping;
 358     unsigned char* cluster; /* points to current cluster */
 359     unsigned char* cluster_buffer; /* points to a buffer to hold temp data */
 360     unsigned int current_cluster;
 361
 362     /* write support */
 363     char* qcow_filename;
 364     BdrvChild* qcow;
 365     void* fat2;
 366     char* used_clusters;
 367     array_t commits;
 368     const char* path;
 369     int downcase_short_names;
 370
 371     Error *migration_blocker;
 372 } BDRVVVFATState;
 373
 374 /* take the sector position spos and convert it to Cylinder/Head/Sector position
 375  * if the position is outside the specified geometry, fill maximum value for CHS
 376  * and return 1 to signal overflow.
 377  */
 378 static int sector2CHS(mbr_chs_t *chs, int spos, int cyls, int heads, int secs)
 379 {
 380     int head,sector;
 381     sector   = spos % secs;  spos /= secs;
 382     head     = spos % heads; spos /= heads;
 383     if (spos >= cyls) {
 384         /* Overflow,
 385         it happens if 32bit sector positions are used, while CHS is only 24bit.
 386         Windows/Dos is said to take 1023/255/63 as nonrepresentable CHS */
 387         chs->head     = 0xFF;
 388         chs->sector   = 0xFF;
 389         chs->cylinder = 0xFF;
 390         return 1;
 391     }
 392     chs->head     = (uint8_t)head;
 393     chs->sector   = (uint8_t)( (sector+1) | ((spos>>8)<<6) );
 394     chs->cylinder = (uint8_t)spos;
 395     return 0;
 396 }
 397
 398 static void init_mbr(BDRVVVFATState *s, int cyls, int heads, int secs)
 399 {
 400     /* TODO: if the files mbr.img and bootsect.img exist, use them */
 401     mbr_t* real_mbr=(mbr_t*)s->first_sectors;
 402     partition_t* partition = &(real_mbr->partition[0]);
 403     int lba;
 404
 405     memset(s->first_sectors,0,512);
 406
 407     /* Win NT Disk Signature */
 408     real_mbr->nt_id= cpu_to_le32(0xbe1afdfa);
 409
 410     partition->attributes=0x80; /* bootable */
 411
 412     /* LBA is used when partition is outside the CHS geometry */
 413     lba  = sector2CHS(&partition->start_CHS, s->offset_to_bootsector,
 414                      cyls, heads, secs);
 415     lba |= sector2CHS(&partition->end_CHS,   s->bs->total_sectors - 1,
 416                      cyls, heads, secs);
 417
 418     /*LBA partitions are identified only by start/length_sector_long not by CHS*/
 419     partition->start_sector_long  = cpu_to_le32(s->offset_to_bootsector);
 420     partition->length_sector_long = cpu_to_le32(s->bs->total_sectors
 421                                                 - s->offset_to_bootsector);
 422
 423     /* FAT12/FAT16/FAT32 */
 424     /* DOS uses different types when partition is LBA,
 425        probably to prevent older versions from using CHS on them */
 426     partition->fs_type = s->fat_type == 12 ? 0x1 :
 427                          s->fat_type == 16 ? (lba ? 0xe : 0x06) :
 428                        /*s->fat_type == 32*/ (lba ? 0xc : 0x0b);
 429
 430     real_mbr->magic[0]=0x55; real_mbr->magic[1]=0xaa;
 431 }
 432
 433 /* direntry functions */
 434
 435 static direntry_t *create_long_filename(BDRVVVFATState *s, const char *filename)
 436 {
 437     int number_of_entries, i;
 438     glong length;
 439     direntry_t *entry;
 440
 441     gunichar2 *longname = g_utf8_to_utf16(filename, -1, NULL, &length, NULL);
 442     if (!longname) {
 443         fprintf(stderr, "vvfat: invalid UTF-8 name: %s\n", filename);
 444         return NULL;
 445     }
 446
 447     number_of_entries = DIV_ROUND_UP(length * 2, 26);
 448
 449     for(i=0;i<number_of_entries;i++) {
 450         entry=array_get_next(&(s->directory));
 451         entry->attributes=0xf;
 452         entry->reserved[0]=0;
 453         entry->begin=0;
 454         entry->name[0]=(number_of_entries-i)|(i==0?0x40:0);
 455     }
 456     for(i=0;i<26*number_of_entries;i++) {
 457         int offset=(i%26);
 458         if(offset<10) offset=1+offset;
 459         else if(offset<22) offset=14+offset-10;
 460         else offset=28+offset-22;
 461         entry=array_get(&(s->directory),s->directory.next-1-(i/26));
 462         if (i >= 2 * length + 2) {
 463             entry->name[offset] = 0xff;
 464         } else if (i % 2 == 0) {
 465             entry->name[offset] = longname[i / 2] & 0xff;
 466         } else {
 467             entry->name[offset] = longname[i / 2] >> 8;
 468         }
 469     }
 470     g_free(longname);
 471     return array_get(&(s->directory),s->directory.next-number_of_entries);
 472 }
 473
 474 static char is_free(const direntry_t* direntry)
 475 {
 476     return direntry->name[0] == DIR_DELETED || direntry->name[0] == DIR_FREE;
 477 }
 478
 479 static char is_volume_label(const direntry_t* direntry)
 480 {
 481     return direntry->attributes == 0x28;
 482 }
 483
 484 static char is_long_name(const direntry_t* direntry)
 485 {
 486     return direntry->attributes == 0xf;
 487 }
 488
 489 static char is_short_name(const direntry_t* direntry)
 490 {
 491     return !is_volume_label(direntry) && !is_long_name(direntry)
 492         && !is_free(direntry);
 493 }
 494
 495 static char is_directory(const direntry_t* direntry)
 496 {
 497     return direntry->attributes & 0x10 && direntry->name[0] != DIR_DELETED;
 498 }
 499
 500 static inline char is_dot(const direntry_t* direntry)
 501 {
 502     return is_short_name(direntry) && direntry->name[0] == '.';
 503 }
 504
 505 static char is_file(const direntry_t* direntry)
 506 {
 507     return is_short_name(direntry) && !is_directory(direntry);
 508 }
 509
 510 static inline uint32_t begin_of_direntry(const direntry_t* direntry)
 511 {
 512     return le16_to_cpu(direntry->begin)|(le16_to_cpu(direntry->begin_hi)<<16);
 513 }
 514
 515 static inline uint32_t filesize_of_direntry(const direntry_t* direntry)
 516 {
 517     return le32_to_cpu(direntry->size);
 518 }
 519
 520 static void set_begin_of_direntry(direntry_t* direntry, uint32_t begin)
 521 {
 522     direntry->begin = cpu_to_le16(begin & 0xffff);
 523     direntry->begin_hi = cpu_to_le16((begin >> 16) & 0xffff);
 524 }
 525
 526 static uint8_t to_valid_short_char(gunichar c)
 527 {
 528     c = g_unichar_toupper(c);
 529     if ((c >= '0' && c <= '9') ||
 530         (c >= 'A' && c <= 'Z') ||
 531         strchr("$%'-_@~`!(){}^#&", c) != 0) {
 532         return c;
 533     } else {
 534         return 0;
 535     }
 536 }
 537
 538 static direntry_t *create_short_filename(BDRVVVFATState *s,
 539                                          const char *filename,
 540                                          unsigned int directory_start)
 541 {
 542     int i, j = 0;
 543     direntry_t *entry = array_get_next(&(s->directory));
 544     const gchar *p, *last_dot = NULL;
 545     gunichar c;
 546     bool lossy_conversion = false;
 547     char tail[8];
 548
 549     if (!entry) {
 550         return NULL;
 551     }
 552     memset(entry->name, 0x20, sizeof(entry->name));
 553
 554     /* copy filename and search last dot */
 555     for (p = filename; ; p = g_utf8_next_char(p)) {
 556         c = g_utf8_get_char(p);
 557         if (c == '\0') {
 558             break;
 559         } else if (c == '.') {
 560             if (j == 0) {
 561                 /* '.' at start of filename */
 562                 lossy_conversion = true;
 563             } else {
 564                 if (last_dot) {
 565                     lossy_conversion = true;
 566                 }
 567                 last_dot = p;
 568             }
 569         } else if (!last_dot) {
 570             /* first part of the name; copy it */
 571             uint8_t v = to_valid_short_char(c);
 572             if (j < 8 && v) {
 573                 entry->name[j++] = v;
 574             } else {
 575                 lossy_conversion = true;
 576             }
 577         }
 578     }
 579
 580     /* copy extension (if any) */
 581     if (last_dot) {
 582         j = 0;
 583         for (p = g_utf8_next_char(last_dot); ; p = g_utf8_next_char(p)) {
 584             c = g_utf8_get_char(p);
 585             if (c == '\0') {
 586                 break;
 587             } else {
 588                 /* extension; copy it */
 589                 uint8_t v = to_valid_short_char(c);
 590                 if (j < 3 && v) {
 591                     entry->name[8 + (j++)] = v;
 592                 } else {
 593                     lossy_conversion = true;
 594                 }
 595             }
 596         }
 597     }
 598
 599     if (entry->name[0] == DIR_KANJI) {
 600         entry->name[0] = DIR_KANJI_FAKE;
 601     }
 602
 603     /* numeric-tail generation */
 604     for (j = 0; j < 8; j++) {
 605         if (entry->name[j] == ' ') {
 606             break;
 607         }
 608     }
 609     for (i = lossy_conversion ? 1 : 0; i < 999999; i++) {
 610         direntry_t *entry1;
 611         if (i > 0) {
 612             int len = snprintf(tail, sizeof(tail), "~%u", (unsigned)i);
 613             assert(len <= 7);
 614             memcpy(entry->name + MIN(j, 8 - len), tail, len);
 615         }
 616         for (entry1 = array_get(&(s->directory), directory_start);
 617              entry1 < entry; entry1++) {
 618             if (!is_long_name(entry1) &&
 619                 !memcmp(entry1->name, entry->name, 11)) {
 620                 break; /* found dupe */
 621             }
 622         }
 623         if (entry1 == entry) {
 624             /* no dupe found */
 625             return entry;
 626         }
 627     }
 628     return NULL;
 629 }
 630
 631 /* fat functions */
 632
 633 static inline uint8_t fat_chksum(const direntry_t* entry)
 634 {
 635     uint8_t chksum=0;
 636     int i;
 637
 638     for (i = 0; i < ARRAY_SIZE(entry->name); i++) {
 639         chksum = (((chksum & 0xfe) >> 1) |
 640                   ((chksum & 0x01) ? 0x80 : 0)) + entry->name[i];
 641     }
 642
 643     return chksum;
 644 }
 645
 646 /* if return_time==0, this returns the fat_date, else the fat_time */
 647 static uint16_t fat_datetime(time_t time,int return_time) {
 648     struct tm* t;
 649     struct tm t1;
 650     t = &t1;
 651     localtime_r(&time,t);
 652     if(return_time)
 653         return cpu_to_le16((t->tm_sec/2)|(t->tm_min<<5)|(t->tm_hour<<11));
 654     return cpu_to_le16((t->tm_mday)|((t->tm_mon+1)<<5)|((t->tm_year-80)<<9));
 655 }
 656
 657 static inline void fat_set(BDRVVVFATState* s,unsigned int cluster,uint32_t value)
 658 {
 659     if(s->fat_type==32) {
 660         uint32_t* entry=array_get(&(s->fat),cluster);
 661         *entry=cpu_to_le32(value);
 662     } else if(s->fat_type==16) {
 663         uint16_t* entry=array_get(&(s->fat),cluster);
 664         *entry=cpu_to_le16(value&0xffff);
 665     } else {
 666         int offset = (cluster*3/2);
 667         unsigned char* p = array_get(&(s->fat), offset);
 668         switch (cluster&1) {
 669         case 0:
 670                 p[0] = value&0xff;
 671                 p[1] = (p[1]&0xf0) | ((value>>8)&0xf);
 672                 break;
 673         case 1:
 674                 p[0] = (p[0]&0xf) | ((value&0xf)<<4);
 675                 p[1] = (value>>4);
 676                 break;
 677         }
 678     }
 679 }
 680
 681 static inline uint32_t fat_get(BDRVVVFATState* s,unsigned int cluster)
 682 {
 683     if(s->fat_type==32) {
 684         uint32_t* entry=array_get(&(s->fat),cluster);
 685         return le32_to_cpu(*entry);
 686     } else if(s->fat_type==16) {
 687         uint16_t* entry=array_get(&(s->fat),cluster);
 688         return le16_to_cpu(*entry);
 689     } else {
 690         const uint8_t* x=(uint8_t*)(s->fat.pointer)+cluster*3/2;
 691         return ((x[0]|(x[1]<<8))>>(cluster&1?4:0))&0x0fff;
 692     }
 693 }
 694
 695 static inline int fat_eof(BDRVVVFATState* s,uint32_t fat_entry)
 696 {
 697     if(fat_entry>s->max_fat_value-8)
 698         return -1;
 699     return 0;
 700 }
 701
 702 static inline void init_fat(BDRVVVFATState* s)
 703 {
 704     if (s->fat_type == 12) {
 705         array_init(&(s->fat),1);
 706         array_ensure_allocated(&(s->fat),
 707                 s->sectors_per_fat * 0x200 * 3 / 2 - 1);
 708     } else {
 709         array_init(&(s->fat),(s->fat_type==32?4:2));
 710         array_ensure_allocated(&(s->fat),
 711                 s->sectors_per_fat * 0x200 / s->fat.item_size - 1);
 712     }
 713     memset(s->fat.pointer,0,s->fat.size);
 714
 715     switch(s->fat_type) {
 716         case 12: s->max_fat_value=0xfff; break;
 717         case 16: s->max_fat_value=0xffff; break;
 718         case 32: s->max_fat_value=0x0fffffff; break;
 719         default: s->max_fat_value=0; /* error... */
 720     }
 721
 722 }
 723
 724 static inline direntry_t* create_short_and_long_name(BDRVVVFATState* s,
 725         unsigned int directory_start, const char* filename, int is_dot)
 726 {
 727     int long_index = s->directory.next;
 728     direntry_t* entry = NULL;
 729     direntry_t* entry_long = NULL;
 730
 731     if(is_dot) {
 732         entry=array_get_next(&(s->directory));
 733         memset(entry->name, 0x20, sizeof(entry->name));
 734         memcpy(entry->name,filename,strlen(filename));
 735         return entry;
 736     }
 737
 738     entry_long=create_long_filename(s,filename);
 739     entry = create_short_filename(s, filename, directory_start);
 740
 741     /* calculate checksum; propagate to long name */
 742     if(entry_long) {
 743         uint8_t chksum=fat_chksum(entry);
 744
 745         /* calculate anew, because realloc could have taken place */
 746         entry_long=array_get(&(s->directory),long_index);
 747         while(entry_long<entry && is_long_name(entry_long)) {
 748             entry_long->reserved[1]=chksum;
 749             entry_long++;
 750         }
 751     }
 752
 753     return entry;
 754 }
 755
 756 /*
 757  * Read a directory. (the index of the corresponding mapping must be passed).
 758  */
 759 static int read_directory(BDRVVVFATState* s, int mapping_index)
 760 {
 761     mapping_t* mapping = array_get(&(s->mapping), mapping_index);
 762     direntry_t* direntry;
 763     const char* dirname = mapping->path;
 764     int first_cluster = mapping->begin;
 765     int parent_index = mapping->info.dir.parent_mapping_index;
 766     mapping_t* parent_mapping = (mapping_t*)
 767         (parent_index >= 0 ? array_get(&(s->mapping), parent_index) : NULL);
 768     int first_cluster_of_parent = parent_mapping ? parent_mapping->begin : -1;
 769
 770     DIR* dir=opendir(dirname);
 771     struct dirent* entry;
 772     int i;
 773
 774     assert(mapping->mode & MODE_DIRECTORY);
 775
 776     if(!dir) {
 777         mapping->end = mapping->begin;
 778         return -1;
 779     }
 780
 781     i = mapping->info.dir.first_dir_index =
 782             first_cluster == 0 ? 0 : s->directory.next;
 783
 784     if (first_cluster != 0) {
 785         /* create the top entries of a subdirectory */
 786         (void)create_short_and_long_name(s, i, ".", 1);
 787         (void)create_short_and_long_name(s, i, "..", 1);
 788     }
 789
 790     /* actually read the directory, and allocate the mappings */
 791     while((entry=readdir(dir))) {
 792         unsigned int length=strlen(dirname)+2+strlen(entry->d_name);
 793         char* buffer;
 794         direntry_t* direntry;
 795         struct stat st;
 796         int is_dot=!strcmp(entry->d_name,".");
 797         int is_dotdot=!strcmp(entry->d_name,"..");
 798
 799         if (first_cluster == 0 && s->directory.next >= s->root_entries - 1) {
 800             fprintf(stderr, "Too many entries in root directory\n");
 801             closedir(dir);
 802             return -2;
 803         }
 804
 805         if(first_cluster == 0 && (is_dotdot || is_dot))
 806             continue;
 807
 808         buffer = g_malloc(length);
 809         snprintf(buffer,length,"%s/%s",dirname,entry->d_name);
 810
 811         if(stat(buffer,&st)<0) {
 812             g_free(buffer);
 813             continue;
 814         }
 815
 816         /* create directory entry for this file */
 817         if (!is_dot && !is_dotdot) {
 818             direntry = create_short_and_long_name(s, i, entry->d_name, 0);
 819         } else {
 820             direntry = array_get(&(s->directory), is_dot ? i : i + 1);
 821         }
 822         direntry->attributes=(S_ISDIR(st.st_mode)?0x10:0x20);
 823         direntry->reserved[0]=direntry->reserved[1]=0;
 824         direntry->ctime=fat_datetime(st.st_ctime,1);
 825         direntry->cdate=fat_datetime(st.st_ctime,0);
 826         direntry->adate=fat_datetime(st.st_atime,0);
 827         direntry->begin_hi=0;
 828         direntry->mtime=fat_datetime(st.st_mtime,1);
 829         direntry->mdate=fat_datetime(st.st_mtime,0);
 830         if(is_dotdot)
 831             set_begin_of_direntry(direntry, first_cluster_of_parent);
 832         else if(is_dot)
 833             set_begin_of_direntry(direntry, first_cluster);
 834         else
 835             direntry->begin=0; /* do that later */
 836         if (st.st_size > 0x7fffffff) {
 837             fprintf(stderr, "File %s is larger than 2GB\n", buffer);
 838             g_free(buffer);
 839             closedir(dir);
 840             return -2;
 841         }
 842         direntry->size=cpu_to_le32(S_ISDIR(st.st_mode)?0:st.st_size);
 843
 844         /* create mapping for this file */
 845         if(!is_dot && !is_dotdot && (S_ISDIR(st.st_mode) || st.st_size)) {
 846             s->current_mapping = array_get_next(&(s->mapping));
 847             s->current_mapping->begin=0;
 848             s->current_mapping->end=st.st_size;
 849             /*
 850              * we get the direntry of the most recent direntry, which
 851              * contains the short name and all the relevant information.
 852              */
 853             s->current_mapping->dir_index=s->directory.next-1;
 854             s->current_mapping->first_mapping_index = -1;
 855             if (S_ISDIR(st.st_mode)) {
 856                 s->current_mapping->mode = MODE_DIRECTORY;
 857                 s->current_mapping->info.dir.parent_mapping_index =
 858                     mapping_index;
 859             } else {
 860                 s->current_mapping->mode = MODE_UNDEFINED;
 861                 s->current_mapping->info.file.offset = 0;
 862             }
 863             s->current_mapping->path=buffer;
 864             s->current_mapping->read_only =
 865                 (st.st_mode & (S_IWUSR | S_IWGRP | S_IWOTH)) == 0;
 866         } else {
 867             g_free(buffer);
 868         }
 869     }
 870     closedir(dir);
 871
 872     /* fill with zeroes up to the end of the cluster */
 873     while(s->directory.next%(0x10*s->sectors_per_cluster)) {
 874         direntry_t* direntry=array_get_next(&(s->directory));
 875         memset(direntry,0,sizeof(direntry_t));
 876     }
 877
 878     if (s->fat_type != 32 &&
 879         mapping_index == 0 &&
 880         s->directory.next < s->root_entries) {
 881         /* root directory */
 882         int cur = s->directory.next;
 883         array_ensure_allocated(&(s->directory), s->root_entries - 1);
 884         s->directory.next = s->root_entries;
 885         memset(array_get(&(s->directory), cur), 0,
 886                 (s->root_entries - cur) * sizeof(direntry_t));
 887     }
 888
 889     /* re-get the mapping, since s->mapping was possibly realloc()ed */
 890     mapping = array_get(&(s->mapping), mapping_index);
 891     first_cluster += (s->directory.next - mapping->info.dir.first_dir_index)
 892         * 0x20 / s->cluster_size;
 893     mapping->end = first_cluster;
 894
 895     direntry = array_get(&(s->directory), mapping->dir_index);
 896     set_begin_of_direntry(direntry, mapping->begin);
 897
 898     return 0;
 899 }
 900
 901 static inline uint32_t sector2cluster(BDRVVVFATState* s,off_t sector_num)
 902 {
 903     return (sector_num - s->offset_to_root_dir) / s->sectors_per_cluster;
 904 }
 905
 906 static inline off_t cluster2sector(BDRVVVFATState* s, uint32_t cluster_num)
 907 {
 908     return s->offset_to_root_dir + s->sectors_per_cluster * cluster_num;
 909 }
 910
 911 static int init_directories(BDRVVVFATState* s,
 912                             const char *dirname, int heads, int secs,
 913                             Error **errp)
 914 {
 915     bootsector_t* bootsector;
 916     mapping_t* mapping;
 917     unsigned int i;
 918     unsigned int cluster;
 919
 920     memset(&(s->first_sectors[0]),0,0x40*0x200);
 921
 922     s->cluster_size=s->sectors_per_cluster*0x200;
 923     s->cluster_buffer=g_malloc(s->cluster_size);
 924
 925     /*
 926      * The formula: sc = spf+1+spf*spc*(512*8/fat_type),
 927      * where sc is sector_count,
 928      * spf is sectors_per_fat,
 929      * spc is sectors_per_clusters, and
 930      * fat_type = 12, 16 or 32.
 931      */
 932     i = 1+s->sectors_per_cluster*0x200*8/s->fat_type;
 933     s->sectors_per_fat=(s->sector_count+i)/i; /* round up */
 934
 935     s->offset_to_fat = s->offset_to_bootsector + 1;
 936     s->offset_to_root_dir = s->offset_to_fat + s->sectors_per_fat * 2;
 937
 938     array_init(&(s->mapping),sizeof(mapping_t));
 939     array_init(&(s->directory),sizeof(direntry_t));
 940
 941     /* add volume label */
 942     {
 943         direntry_t* entry=array_get_next(&(s->directory));
 944         entry->attributes=0x28; /* archive | volume label */
 945         memcpy(entry->name, s->volume_label, sizeof(entry->name));
 946     }
 947
 948     /* Now build FAT, and write back information into directory */
 949     init_fat(s);
 950
 951     /* TODO: if there are more entries, bootsector has to be adjusted! */
 952     s->root_entries = 0x02 * 0x10 * s->sectors_per_cluster;
 953     s->cluster_count=sector2cluster(s, s->sector_count);
 954
 955     mapping = array_get_next(&(s->mapping));
 956     mapping->begin = 0;
 957     mapping->dir_index = 0;
 958     mapping->info.dir.parent_mapping_index = -1;
 959     mapping->first_mapping_index = -1;
 960     mapping->path = g_strdup(dirname);
 961     i = strlen(mapping->path);
 962     if (i > 0 && mapping->path[i - 1] == '/')
 963         mapping->path[i - 1] = '\0';
 964     mapping->mode = MODE_DIRECTORY;
 965     mapping->read_only = 0;
 966     s->path = mapping->path;
 967
 968     for (i = 0, cluster = 0; i < s->mapping.next; i++) {
 969         /* MS-DOS expects the FAT to be 0 for the root directory
 970          * (except for the media byte). */
 971         /* LATER TODO: still true for FAT32? */
 972         int fix_fat = (i != 0);
 973         mapping = array_get(&(s->mapping), i);
 974
 975         if (mapping->mode & MODE_DIRECTORY) {
 976             char *path = mapping->path;
 977             mapping->begin = cluster;
 978             if(read_directory(s, i)) {
 979                 error_setg(errp, "Could not read directory %s", path);
 980                 return -1;
 981             }
 982             mapping = array_get(&(s->mapping), i);
 983         } else {
 984             assert(mapping->mode == MODE_UNDEFINED);
 985             mapping->mode=MODE_NORMAL;
 986             mapping->begin = cluster;
 987             if (mapping->end > 0) {
 988                 direntry_t* direntry = array_get(&(s->directory),
 989                         mapping->dir_index);
 990
 991                 mapping->end = cluster + 1 + (mapping->end-1)/s->cluster_size;
 992                 set_begin_of_direntry(direntry, mapping->begin);
 993             } else {
 994                 mapping->end = cluster + 1;
 995                 fix_fat = 0;
 996             }
 997         }
 998
 999         assert(mapping->begin < mapping->end);
1000
1001         /* next free cluster */
1002         cluster = mapping->end;
1003
1004         if(cluster > s->cluster_count) {
1005             error_setg(errp,
1006                        "Directory does not fit in FAT%d (capacity %.2f MB)",
1007                        s->fat_type, s->sector_count / 2000.0);
1008             return -1;
1009         }
1010
1011         /* fix fat for entry */
1012         if (fix_fat) {
1013             int j;
1014             for(j = mapping->begin; j < mapping->end - 1; j++)
1015                 fat_set(s, j, j+1);
1016             fat_set(s, mapping->end - 1, s->max_fat_value);
1017         }
1018     }
1019
1020     mapping = array_get(&(s->mapping), 0);
1021     s->last_cluster_of_root_directory = mapping->end;
1022
1023     /* the FAT signature */
1024     fat_set(s,0,s->max_fat_value);
1025     fat_set(s,1,s->max_fat_value);
1026
1027     s->current_mapping = NULL;
1028
1029     bootsector = (bootsector_t *)(s->first_sectors
1030                                   + s->offset_to_bootsector * 0x200);
1031     bootsector->jump[0]=0xeb;
1032     bootsector->jump[1]=0x3e;
1033     bootsector->jump[2]=0x90;
1034     memcpy(bootsector->name, BOOTSECTOR_OEM_NAME, 8);
1035     bootsector->sector_size=cpu_to_le16(0x200);
1036     bootsector->sectors_per_cluster=s->sectors_per_cluster;
1037     bootsector->reserved_sectors=cpu_to_le16(1);
1038     bootsector->number_of_fats=0x2; /* number of FATs */
1039     bootsector->root_entries = cpu_to_le16(s->root_entries);
1040     bootsector->total_sectors16=s->sector_count>0xffff?0:cpu_to_le16(s->sector_count);
1041     /* media descriptor: hard disk=0xf8, floppy=0xf0 */
1042     bootsector->media_type = (s->offset_to_bootsector > 0 ? 0xf8 : 0xf0);
1043     s->fat.pointer[0] = bootsector->media_type;
1044     bootsector->sectors_per_fat=cpu_to_le16(s->sectors_per_fat);
1045     bootsector->sectors_per_track = cpu_to_le16(secs);
1046     bootsector->number_of_heads = cpu_to_le16(heads);
1047     bootsector->hidden_sectors = cpu_to_le32(s->offset_to_bootsector);
1048     bootsector->total_sectors=cpu_to_le32(s->sector_count>0xffff?s->sector_count:0);
1049
1050     /* LATER TODO: if FAT32, this is wrong */
1051     /* drive_number: fda=0, hda=0x80 */
1052     bootsector->u.fat16.drive_number = s->offset_to_bootsector == 0 ? 0 : 0x80;
1053     bootsector->u.fat16.signature=0x29;
1054     bootsector->u.fat16.id=cpu_to_le32(0xfabe1afd);
1055
1056     memcpy(bootsector->u.fat16.volume_label, s->volume_label,
1057            sizeof(bootsector->u.fat16.volume_label));
1058     memcpy(bootsector->u.fat16.fat_type,
1059            s->fat_type == 12 ? "FAT12   " : "FAT16   ", 8);
1060     bootsector->magic[0]=0x55; bootsector->magic[1]=0xaa;
1061
1062     return 0;
1063 }
1064
1065 #ifdef DEBUG
1066 static BDRVVVFATState *vvv = NULL;
1067 #endif
1068
1069 static int enable_write_target(BlockDriverState *bs, Error **errp);
1070 static int is_consistent(BDRVVVFATState *s);
1071
1072 static QemuOptsList runtime_opts = {
1073     .name = "vvfat",
1074     .head = QTAILQ_HEAD_INITIALIZER(runtime_opts.head),
1075     .desc = {
1076         {
1077             .name = "dir",
1078             .type = QEMU_OPT_STRING,
1079             .help = "Host directory to map to the vvfat device",
1080         },
1081         {
1082             .name = "fat-type",
1083             .type = QEMU_OPT_NUMBER,
1084             .help = "FAT type (12, 16 or 32)",
1085         },
1086         {
1087             .name = "floppy",
1088             .type = QEMU_OPT_BOOL,
1089             .help = "Create a floppy rather than a hard disk image",
1090         },
1091         {
1092             .name = "label",
1093             .type = QEMU_OPT_STRING,
1094             .help = "Use a volume label other than QEMU VVFAT",
1095         },
1096         {
1097             .name = "rw",
1098             .type = QEMU_OPT_BOOL,
1099             .help = "Make the image writable",
1100         },
1101         { /* end of list */ }
1102     },
1103 };
1104
1105 static void vvfat_parse_filename(const char *filename, QDict *options,
1106                                  Error **errp)
1107 {
1108     int fat_type = 0;
1109     bool floppy = false;
1110     bool rw = false;
1111     int i;
1112
1113     if (!strstart(filename, "fat:", NULL)) {
1114         error_setg(errp, "File name string must start with 'fat:'");
1115         return;
1116     }
1117
1118     /* Parse options */
1119     if (strstr(filename, ":32:")) {
1120         fat_type = 32;
1121     } else if (strstr(filename, ":16:")) {
1122         fat_type = 16;
1123     } else if (strstr(filename, ":12:")) {
1124         fat_type = 12;
1125     }
1126
1127     if (strstr(filename, ":floppy:")) {
1128         floppy = true;
1129     }
1130
1131     if (strstr(filename, ":rw:")) {
1132         rw = true;
1133     }
1134
1135     /* Get the directory name without options */
1136     i = strrchr(filename, ':') - filename;
1137     assert(i >= 3);
1138     if (filename[i - 2] == ':' && qemu_isalpha(filename[i - 1])) {
1139         /* workaround for DOS drive names */
1140         filename += i - 1;
1141     } else {
1142         filename += i + 1;
1143     }
1144
1145     /* Fill in the options QDict */
1146     qdict_put_str(options, "dir", filename);
1147     qdict_put_int(options, "fat-type", fat_type);
1148     qdict_put_bool(options, "floppy", floppy);
1149     qdict_put_bool(options, "rw", rw);
1150 }
1151
1152 static int vvfat_open(BlockDriverState *bs, QDict *options, int flags,
1153                       Error **errp)
1154 {
1155     BDRVVVFATState *s = bs->opaque;
1156     int cyls, heads, secs;
1157     bool floppy;
1158     const char *dirname, *label;
1159     QemuOpts *opts;
1160     Error *local_err = NULL;
1161     int ret;
1162
1163 #ifdef DEBUG
1164     vvv = s;
1165 #endif
1166
1167     opts = qemu_opts_create(&runtime_opts, NULL, 0, &error_abort);
1168     qemu_opts_absorb_qdict(opts, options, &local_err);
1169     if (local_err) {
1170         error_propagate(errp, local_err);
1171         ret = -EINVAL;
1172         goto fail;
1173     }
1174
1175     dirname = qemu_opt_get(opts, "dir");
1176     if (!dirname) {
1177         error_setg(errp, "vvfat block driver requires a 'dir' option");
1178         ret = -EINVAL;
1179         goto fail;
1180     }
1181
1182     s->fat_type = qemu_opt_get_number(opts, "fat-type", 0);
1183     floppy = qemu_opt_get_bool(opts, "floppy", false);
1184
1185     memset(s->volume_label, ' ', sizeof(s->volume_label));
1186     label = qemu_opt_get(opts, "label");
1187     if (label) {
1188         size_t label_length = strlen(label);
1189         if (label_length > 11) {
1190             error_setg(errp, "vvfat label cannot be longer than 11 bytes");
1191             ret = -EINVAL;
1192             goto fail;
1193         }
1194         memcpy(s->volume_label, label, label_length);
1195     } else {
1196         memcpy(s->volume_label, "QEMU VVFAT", 10);
1197     }
1198
1199     if (floppy) {
1200         /* 1.44MB or 2.88MB floppy.  2.88MB can be FAT12 (default) or FAT16. */
1201         if (!s->fat_type) {
1202             s->fat_type = 12;
1203             secs = 36;
1204             s->sectors_per_cluster = 2;
1205         } else {
1206             secs = s->fat_type == 12 ? 18 : 36;
1207             s->sectors_per_cluster = 1;
1208         }
1209         cyls = 80;
1210         heads = 2;
1211     } else {
1212         /* 32MB or 504MB disk*/
1213         if (!s->fat_type) {
1214             s->fat_type = 16;
1215         }
1216         s->offset_to_bootsector = 0x3f;
1217         cyls = s->fat_type == 12 ? 64 : 1024;
1218         heads = 16;
1219         secs = 63;
1220     }
1221
1222     switch (s->fat_type) {
1223     case 32:
1224         warn_report("FAT32 has not been tested. You are welcome to do so!");
1225         break;
1226     case 16:
1227     case 12:
1228         break;
1229     default:
1230         error_setg(errp, "Valid FAT types are only 12, 16 and 32");
1231         ret = -EINVAL;
1232         goto fail;
1233     }
1234
1235
1236     s->bs = bs;
1237
1238     /* LATER TODO: if FAT32, adjust */
1239     s->sectors_per_cluster=0x10;
1240
1241     s->current_cluster=0xffffffff;
1242
1243     s->qcow = NULL;
1244     s->qcow_filename = NULL;
1245     s->fat2 = NULL;
1246     s->downcase_short_names = 1;
1247
1248     DLOG(fprintf(stderr, "vvfat %s chs %d,%d,%d\n",
1249                  dirname, cyls, heads, secs));
1250
1251     s->sector_count = cyls * heads * secs - s->offset_to_bootsector;
1252
1253     if (qemu_opt_get_bool(opts, "rw", false)) {
1254         if (!bdrv_is_read_only(bs)) {
1255             ret = enable_write_target(bs, errp);
1256             if (ret < 0) {
1257                 goto fail;
1258             }
1259         } else {
1260             ret = -EPERM;
1261             error_setg(errp,
1262                        "Unable to set VVFAT to 'rw' when drive is read-only");
1263             goto fail;
1264         }
1265     } else {
1266         ret = bdrv_apply_auto_read_only(bs, NULL, errp);
1267         if (ret < 0) {
1268             goto fail;
1269         }
1270     }
1271
1272     bs->total_sectors = cyls * heads * secs;
1273
1274     if (init_directories(s, dirname, heads, secs, errp)) {
1275         ret = -EIO;
1276         goto fail;
1277     }
1278
1279     s->sector_count = s->offset_to_root_dir
1280                     + s->sectors_per_cluster * s->cluster_count;
1281
1282     /* Disable migration when vvfat is used rw */
1283     if (s->qcow) {
1284         error_setg(&s->migration_blocker,
1285                    "The vvfat (rw) format used by node '%s' "
1286                    "does not support live migration",
1287                    bdrv_get_device_or_node_name(bs));
1288         ret = migrate_add_blocker(s->migration_blocker, &local_err);
1289         if (local_err) {
1290             error_propagate(errp, local_err);
1291             error_free(s->migration_blocker);
1292             goto fail;
1293         }
1294     }
1295
1296     if (s->offset_to_bootsector > 0) {
1297         init_mbr(s, cyls, heads, secs);
1298     }
1299
1300     qemu_co_mutex_init(&s->lock);
1301
1302     ret = 0;
1303 fail:
1304     qemu_opts_del(opts);
1305     return ret;
1306 }
1307
1308 static void vvfat_refresh_limits(BlockDriverState *bs, Error **errp)
1309 {
1310     bs->bl.request_alignment = BDRV_SECTOR_SIZE; /* No sub-sector I/O */
1311 }
1312
1313 static inline void vvfat_close_current_file(BDRVVVFATState *s)
1314 {
1315     if(s->current_mapping) {
1316         s->current_mapping = NULL;
1317         if (s->current_fd) {
1318                 qemu_close(s->current_fd);
1319                 s->current_fd = 0;
1320         }
1321     }
1322     s->current_cluster = -1;
1323 }
1324
1325 /* mappings between index1 and index2-1 are supposed to be ordered
1326  * return value is the index of the last mapping for which end>cluster_num
1327  */
1328 static inline int find_mapping_for_cluster_aux(BDRVVVFATState* s,int cluster_num,int index1,int index2)
1329 {
1330     while(1) {
1331         int index3;
1332         mapping_t* mapping;
1333         index3=(index1+index2)/2;
1334         mapping=array_get(&(s->mapping),index3);
1335         assert(mapping->begin < mapping->end);
1336         if(mapping->begin>=cluster_num) {
1337             assert(index2!=index3 || index2==0);
1338             if(index2==index3)
1339                 return index1;
1340             index2=index3;
1341         } else {
1342             if(index1==index3)
1343                 return mapping->end<=cluster_num ? index2 : index1;
1344             index1=index3;
1345         }
1346         assert(index1<=index2);
1347         DLOG(mapping=array_get(&(s->mapping),index1);
1348         assert(mapping->begin<=cluster_num);
1349         assert(index2 >= s->mapping.next ||
1350                 ((mapping = array_get(&(s->mapping),index2)) &&
1351                 mapping->end>cluster_num)));
1352     }
1353 }
1354
1355 static inline mapping_t* find_mapping_for_cluster(BDRVVVFATState* s,int cluster_num)
1356 {
1357     int index=find_mapping_for_cluster_aux(s,cluster_num,0,s->mapping.next);
1358     mapping_t* mapping;
1359     if(index>=s->mapping.next)
1360         return NULL;
1361     mapping=array_get(&(s->mapping),index);
1362     if(mapping->begin>cluster_num)
1363         return NULL;
1364     assert(mapping->begin<=cluster_num && mapping->end>cluster_num);
1365     return mapping;
1366 }
1367
1368 static int open_file(BDRVVVFATState* s,mapping_t* mapping)
1369 {
1370     if(!mapping)
1371         return -1;
1372     if(!s->current_mapping ||
1373             strcmp(s->current_mapping->path,mapping->path)) {
1374         /* open file */
1375         int fd = qemu_open(mapping->path, O_RDONLY | O_BINARY | O_LARGEFILE);
1376         if(fd<0)
1377             return -1;
1378         vvfat_close_current_file(s);
1379         s->current_fd = fd;
1380         s->current_mapping = mapping;
1381     }
1382     return 0;
1383 }
1384
1385 static inline int read_cluster(BDRVVVFATState *s,int cluster_num)
1386 {
1387     if(s->current_cluster != cluster_num) {
1388         int result=0;
1389         off_t offset;
1390         assert(!s->current_mapping || s->current_fd || (s->current_mapping->mode & MODE_DIRECTORY));
1391         if(!s->current_mapping
1392                 || s->current_mapping->begin>cluster_num
1393                 || s->current_mapping->end<=cluster_num) {
1394             /* binary search of mappings for file */
1395             mapping_t* mapping=find_mapping_for_cluster(s,cluster_num);
1396
1397             assert(!mapping || (cluster_num>=mapping->begin && cluster_num<mapping->end));
1398
1399             if (mapping && mapping->mode & MODE_DIRECTORY) {
1400                 vvfat_close_current_file(s);
1401                 s->current_mapping = mapping;
1402 read_cluster_directory:
1403                 offset = s->cluster_size*(cluster_num-s->current_mapping->begin);
1404                 s->cluster = (unsigned char*)s->directory.pointer+offset
1405                         + 0x20*s->current_mapping->info.dir.first_dir_index;
1406                 assert(((s->cluster-(unsigned char*)s->directory.pointer)%s->cluster_size)==0);
1407                 assert((char*)s->cluster+s->cluster_size <= s->directory.pointer+s->directory.next*s->directory.item_size);
1408                 s->current_cluster = cluster_num;
1409                 return 0;
1410             }
1411
1412             if(open_file(s,mapping))
1413                 return -2;
1414         } else if (s->current_mapping->mode & MODE_DIRECTORY)
1415             goto read_cluster_directory;
1416
1417         assert(s->current_fd);
1418
1419         offset=s->cluster_size*(cluster_num-s->current_mapping->begin)+s->current_mapping->info.file.offset;
1420         if(lseek(s->current_fd, offset, SEEK_SET)!=offset)
1421             return -3;
1422         s->cluster=s->cluster_buffer;
1423         result=read(s->current_fd,s->cluster,s->cluster_size);
1424         if(result<0) {
1425             s->current_cluster = -1;
1426             return -1;
1427         }
1428         s->current_cluster = cluster_num;
1429     }
1430     return 0;
1431 }
1432
1433 #ifdef DEBUG
1434 static void print_direntry(const direntry_t* direntry)
1435 {
1436     int j = 0;
1437     char buffer[1024];
1438
1439     fprintf(stderr, "direntry %p: ", direntry);
1440     if(!direntry)
1441         return;
1442     if(is_long_name(direntry)) {
1443         unsigned char* c=(unsigned char*)direntry;
1444         int i;
1445         for(i=1;i<11 && c[i] && c[i]!=0xff;i+=2)
1446 #define ADD_CHAR(c) {buffer[j] = (c); if (buffer[j] < ' ') buffer[j] = 0xb0; j++;}
1447             ADD_CHAR(c[i]);
1448         for(i=14;i<26 && c[i] && c[i]!=0xff;i+=2)
1449             ADD_CHAR(c[i]);
1450         for(i=28;i<32 && c[i] && c[i]!=0xff;i+=2)
1451             ADD_CHAR(c[i]);
1452         buffer[j] = 0;
1453         fprintf(stderr, "%s\n", buffer);
1454     } else {
1455         int i;
1456         for(i=0;i<11;i++)
1457             ADD_CHAR(direntry->name[i]);
1458         buffer[j] = 0;
1459         fprintf(stderr,"%s attributes=0x%02x begin=%d size=%d\n",
1460                 buffer,
1461                 direntry->attributes,
1462                 begin_of_direntry(direntry),le32_to_cpu(direntry->size));
1463     }
1464 }
1465
1466 static void print_mapping(const mapping_t* mapping)
1467 {
1468     fprintf(stderr, "mapping (%p): begin, end = %d, %d, dir_index = %d, "
1469         "first_mapping_index = %d, name = %s, mode = 0x%x, " ,
1470         mapping, mapping->begin, mapping->end, mapping->dir_index,
1471         mapping->first_mapping_index, mapping->path, mapping->mode);
1472
1473     if (mapping->mode & MODE_DIRECTORY)
1474         fprintf(stderr, "parent_mapping_index = %d, first_dir_index = %d\n", mapping->info.dir.parent_mapping_index, mapping->info.dir.first_dir_index);
1475     else
1476         fprintf(stderr, "offset = %d\n", mapping->info.file.offset);
1477 }
1478 #endif
1479
1480 static int vvfat_read(BlockDriverState *bs, int64_t sector_num,
1481                     uint8_t *buf, int nb_sectors)
1482 {
1483     BDRVVVFATState *s = bs->opaque;
1484     int i;
1485
1486     for(i=0;i<nb_sectors;i++,sector_num++) {
1487         if (sector_num >= bs->total_sectors)
1488            return -1;
1489         if (s->qcow) {
1490             int64_t n;
1491             int ret;
1492             ret = bdrv_is_allocated(s->qcow->bs, sector_num * BDRV_SECTOR_SIZE,
1493                                     (nb_sectors - i) * BDRV_SECTOR_SIZE, &n);
1494             if (ret < 0) {
1495                 return ret;
1496             }
1497             if (ret) {
1498                 DLOG(fprintf(stderr, "sectors %" PRId64 "+%" PRId64
1499                              " allocated\n", sector_num,
1500                              n >> BDRV_SECTOR_BITS));
1501                 if (bdrv_read(s->qcow, sector_num, buf + i * 0x200,
1502                               n >> BDRV_SECTOR_BITS)) {
1503                     return -1;
1504                 }
1505                 i += (n >> BDRV_SECTOR_BITS) - 1;
1506                 sector_num += (n >> BDRV_SECTOR_BITS) - 1;
1507                 continue;
1508             }
1509             DLOG(fprintf(stderr, "sector %" PRId64 " not allocated\n",
1510                          sector_num));
1511         }
1512         if (sector_num < s->offset_to_root_dir) {
1513             if (sector_num < s->offset_to_fat) {
1514                 memcpy(buf + i * 0x200,
1515                        &(s->first_sectors[sector_num * 0x200]),
1516                        0x200);
1517             } else if (sector_num < s->offset_to_fat + s->sectors_per_fat) {
1518                 memcpy(buf + i * 0x200,
1519                        &(s->fat.pointer[(sector_num
1520                                        - s->offset_to_fat) * 0x200]),
1521                        0x200);
1522             } else if (sector_num < s->offset_to_root_dir) {
1523                 memcpy(buf + i * 0x200,
1524                        &(s->fat.pointer[(sector_num - s->offset_to_fat
1525                                        - s->sectors_per_fat) * 0x200]),
1526                        0x200);
1527             }
1528         } else {
1529             uint32_t sector = sector_num - s->offset_to_root_dir,
1530             sector_offset_in_cluster=(sector%s->sectors_per_cluster),
1531             cluster_num=sector/s->sectors_per_cluster;
1532             if(cluster_num > s->cluster_count || read_cluster(s, cluster_num) != 0) {
1533                 /* LATER TODO: strict: return -1; */
1534                 memset(buf+i*0x200,0,0x200);
1535                 continue;
1536             }
1537             memcpy(buf+i*0x200,s->cluster+sector_offset_in_cluster*0x200,0x200);
1538         }
1539     }
1540     return 0;
1541 }
1542
1543 static int coroutine_fn
1544 vvfat_co_preadv(BlockDriverState *bs, uint64_t offset, uint64_t bytes,
1545                 QEMUIOVector *qiov, int flags)
1546 {
1547     int ret;
1548     BDRVVVFATState *s = bs->opaque;
1549     uint64_t sector_num = offset >> BDRV_SECTOR_BITS;
1550     int nb_sectors = bytes >> BDRV_SECTOR_BITS;
1551     void *buf;
1552
1553     assert((offset & (BDRV_SECTOR_SIZE - 1)) == 0);
1554     assert((bytes & (BDRV_SECTOR_SIZE - 1)) == 0);
1555
1556     buf = g_try_malloc(bytes);
1557     if (bytes && buf == NULL) {
1558         return -ENOMEM;
1559     }
1560
1561     qemu_co_mutex_lock(&s->lock);
1562     ret = vvfat_read(bs, sector_num, buf, nb_sectors);
1563     qemu_co_mutex_unlock(&s->lock);
1564
1565     qemu_iovec_from_buf(qiov, 0, buf, bytes);
1566     g_free(buf);
1567
1568     return ret;
1569 }
1570
1571 /* LATER TODO: statify all functions */
1572
1573 /*
1574  * Idea of the write support (use snapshot):
1575  *
1576  * 1. check if all data is consistent, recording renames, modifications,
1577  *    new files and directories (in s->commits).
1578  *
1579  * 2. if the data is not consistent, stop committing
1580  *
1581  * 3. handle renames, and create new files and directories (do not yet
1582  *    write their contents)
1583  *
1584  * 4. walk the directories, fixing the mapping and direntries, and marking
1585  *    the handled mappings as not deleted
1586  *
1587  * 5. commit the contents of the files
1588  *
1589  * 6. handle deleted files and directories
1590  *
1591  */
1592
1593 typedef struct commit_t {
1594     char* path;
1595     union {
1596         struct { uint32_t cluster; } rename;
1597         struct { int dir_index; uint32_t modified_offset; } writeout;
1598         struct { uint32_t first_cluster; } new_file;
1599         struct { uint32_t cluster; } mkdir;
1600     } param;
1601     /* DELETEs and RMDIRs are handled differently: see handle_deletes() */
1602     enum {
1603         ACTION_RENAME, ACTION_WRITEOUT, ACTION_NEW_FILE, ACTION_MKDIR
1604     } action;
1605 } commit_t;
1606
1607 static void clear_commits(BDRVVVFATState* s)
1608 {
1609     int i;
1610 DLOG(fprintf(stderr, "clear_commits (%d commits)\n", s->commits.next));
1611     for (i = 0; i < s->commits.next; i++) {
1612         commit_t* commit = array_get(&(s->commits), i);
1613         assert(commit->path || commit->action == ACTION_WRITEOUT);
1614         if (commit->action != ACTION_WRITEOUT) {
1615             assert(commit->path);
1616             g_free(commit->path);
1617         } else
1618             assert(commit->path == NULL);
1619     }
1620     s->commits.next = 0;
1621 }
1622
1623 static void schedule_rename(BDRVVVFATState* s,
1624         uint32_t cluster, char* new_path)
1625 {
1626     commit_t* commit = array_get_next(&(s->commits));
1627     commit->path = new_path;
1628     commit->param.rename.cluster = cluster;
1629     commit->action = ACTION_RENAME;
1630 }
1631
1632 static void schedule_writeout(BDRVVVFATState* s,
1633         int dir_index, uint32_t modified_offset)
1634 {
1635     commit_t* commit = array_get_next(&(s->commits));
1636     commit->path = NULL;
1637     commit->param.writeout.dir_index = dir_index;
1638     commit->param.writeout.modified_offset = modified_offset;
1639     commit->action = ACTION_WRITEOUT;
1640 }
1641
1642 static void schedule_new_file(BDRVVVFATState* s,
1643         char* path, uint32_t first_cluster)
1644 {
1645     commit_t* commit = array_get_next(&(s->commits));
1646     commit->path = path;
1647     commit->param.new_file.first_cluster = first_cluster;
1648     commit->action = ACTION_NEW_FILE;
1649 }
1650
1651 static void schedule_mkdir(BDRVVVFATState* s, uint32_t cluster, char* path)
1652 {
1653     commit_t* commit = array_get_next(&(s->commits));
1654     commit->path = path;
1655     commit->param.mkdir.cluster = cluster;
1656     commit->action = ACTION_MKDIR;
1657 }
1658
1659 typedef struct {
1660     /*
1661      * Since the sequence number is at most 0x3f, and the filename
1662      * length is at most 13 times the sequence number, the maximal
1663      * filename length is 0x3f * 13 bytes.
1664      */
1665     unsigned char name[0x3f * 13 + 1];
1666     gunichar2 name2[0x3f * 13 + 1];
1667     int checksum, len;
1668     int sequence_number;
1669 } long_file_name;
1670
1671 static void lfn_init(long_file_name* lfn)
1672 {
1673    lfn->sequence_number = lfn->len = 0;
1674    lfn->checksum = 0x100;
1675 }
1676
1677 /* return 0 if parsed successfully, > 0 if no long name, < 0 if error */
1678 static int parse_long_name(long_file_name* lfn,
1679         const direntry_t* direntry)
1680 {
1681     int i, j, offset;
1682     const unsigned char* pointer = (const unsigned char*)direntry;
1683
1684     if (!is_long_name(direntry))
1685         return 1;
1686
1687     if (pointer[0] & 0x40) {
1688         /* first entry; do some initialization */
1689         lfn->sequence_number = pointer[0] & 0x3f;
1690         lfn->checksum = pointer[13];
1691         lfn->name[0] = 0;
1692         lfn->name[lfn->sequence_number * 13] = 0;
1693     } else if ((pointer[0] & 0x3f) != --lfn->sequence_number) {
1694         /* not the expected sequence number */
1695         return -1;
1696     } else if (pointer[13] != lfn->checksum) {
1697         /* not the expected checksum */
1698         return -2;
1699     } else if (pointer[12] || pointer[26] || pointer[27]) {
1700         /* invalid zero fields */
1701         return -3;
1702     }
1703
1704     offset = 13 * (lfn->sequence_number - 1);
1705     for (i = 0, j = 1; i < 13; i++, j+=2) {
1706         if (j == 11)
1707             j = 14;
1708         else if (j == 26)
1709             j = 28;
1710
1711         if (pointer[j] == 0 && pointer[j + 1] == 0) {
1712             /* end of long file name */
1713             break;
1714         }
1715         gunichar2 c = (pointer[j + 1] << 8) + pointer[j];
1716         lfn->name2[offset + i] = c;
1717     }
1718
1719     if (pointer[0] & 0x40) {
1720         /* first entry; set len */
1721         lfn->len = offset + i;
1722     }
1723     if ((pointer[0] & 0x3f) == 0x01) {
1724         /* last entry; finalize entry */
1725         glong olen;
1726         gchar *utf8 = g_utf16_to_utf8(lfn->name2, lfn->len, NULL, &olen, NULL);
1727         if (!utf8) {
1728             return -4;
1729         }
1730         lfn->len = olen;
1731         memcpy(lfn->name, utf8, olen + 1);
1732         g_free(utf8);
1733     }
1734
1735     return 0;
1736 }
1737
1738 /* returns 0 if successful, >0 if no short_name, and <0 on error */
1739 static int parse_short_name(BDRVVVFATState* s,
1740         long_file_name* lfn, direntry_t* direntry)
1741 {
1742     int i, j;
1743
1744     if (!is_short_name(direntry))
1745         return 1;
1746
1747     for (j = 7; j >= 0 && direntry->name[j] == ' '; j--);
1748     for (i = 0; i <= j; i++) {
1749         uint8_t c = direntry->name[i];
1750         if (c != to_valid_short_char(c)) {
1751             return -1;
1752         } else if (s->downcase_short_names) {
1753             lfn->name[i] = qemu_tolower(direntry->name[i]);
1754         } else {
1755             lfn->name[i] = direntry->name[i];
1756         }
1757     }
1758
1759     for (j = 2; j >= 0 && direntry->name[8 + j] == ' '; j--) {
1760     }
1761     if (j >= 0) {
1762         lfn->name[i++] = '.';
1763         lfn->name[i + j + 1] = '\0';
1764         for (;j >= 0; j--) {
1765             uint8_t c = direntry->name[8 + j];
1766             if (c != to_valid_short_char(c)) {
1767                 return -2;
1768             } else if (s->downcase_short_names) {
1769                 lfn->name[i + j] = qemu_tolower(c);
1770             } else {
1771                 lfn->name[i + j] = c;
1772             }
1773         }
1774     } else
1775         lfn->name[i + j + 1] = '\0';
1776
1777     if (lfn->name[0] == DIR_KANJI_FAKE) {
1778         lfn->name[0] = DIR_KANJI;
1779     }
1780     lfn->len = strlen((char*)lfn->name);
1781
1782     return 0;
1783 }
1784
1785 static inline uint32_t modified_fat_get(BDRVVVFATState* s,
1786         unsigned int cluster)
1787 {
1788     if (cluster < s->last_cluster_of_root_directory) {
1789         if (cluster + 1 == s->last_cluster_of_root_directory)
1790             return s->max_fat_value;
1791         else
1792             return cluster + 1;
1793     }
1794
1795     if (s->fat_type==32) {
1796         uint32_t* entry=((uint32_t*)s->fat2)+cluster;
1797         return le32_to_cpu(*entry);
1798     } else if (s->fat_type==16) {
1799         uint16_t* entry=((uint16_t*)s->fat2)+cluster;
1800         return le16_to_cpu(*entry);
1801     } else {
1802         const uint8_t* x=s->fat2+cluster*3/2;
1803         return ((x[0]|(x[1]<<8))>>(cluster&1?4:0))&0x0fff;
1804     }
1805 }
1806
1807 static inline bool cluster_was_modified(BDRVVVFATState *s,
1808                                         uint32_t cluster_num)
1809 {
1810     int was_modified = 0;
1811     int i;
1812
1813     if (s->qcow == NULL) {
1814         return 0;
1815     }
1816
1817     for (i = 0; !was_modified && i < s->sectors_per_cluster; i++) {
1818         was_modified = bdrv_is_allocated(s->qcow->bs,
1819                                          (cluster2sector(s, cluster_num) +
1820                                           i) * BDRV_SECTOR_SIZE,
1821                                          BDRV_SECTOR_SIZE, NULL);
1822     }
1823
1824     /*
1825      * Note that this treats failures to learn allocation status the
1826      * same as if an allocation has occurred.  It's as safe as
1827      * anything else, given that a failure to learn allocation status
1828      * will probably result in more failures.
1829      */
1830     return !!was_modified;
1831 }
1832
1833 static const char* get_basename(const char* path)
1834 {
1835     char* basename = strrchr(path, '/');
1836     if (basename == NULL)
1837         return path;
1838     else
1839         return basename + 1; /* strip '/' */
1840 }
1841
1842 /*
1843  * The array s->used_clusters holds the states of the clusters. If it is
1844  * part of a file, it has bit 2 set, in case of a directory, bit 1. If it
1845  * was modified, bit 3 is set.
1846  * If any cluster is allocated, but not part of a file or directory, this
1847  * driver refuses to commit.
1848  */
1849 typedef enum {
1850      USED_DIRECTORY = 1, USED_FILE = 2, USED_ANY = 3, USED_ALLOCATED = 4
1851 } used_t;
1852
1853 /*
1854  * get_cluster_count_for_direntry() not only determines how many clusters
1855  * are occupied by direntry, but also if it was renamed or modified.
1856  *
1857  * A file is thought to be renamed *only* if there already was a file with
1858  * exactly the same first cluster, but a different name.
1859  *
1860  * Further, the files/directories handled by this function are
1861  * assumed to be *not* deleted (and *only* those).
1862  */
1863 static uint32_t get_cluster_count_for_direntry(BDRVVVFATState* s,
1864         direntry_t* direntry, const char* path)
1865 {
1866     /*
1867      * This is a little bit tricky:
1868      * IF the guest OS just inserts a cluster into the file chain,
1869      * and leaves the rest alone, (i.e. the original file had clusters
1870      * 15 -> 16, but now has 15 -> 32 -> 16), then the following happens:
1871      *
1872      * - do_commit will write the cluster into the file at the given
1873      *   offset, but
1874      *
1875      * - the cluster which is overwritten should be moved to a later
1876      *   position in the file.
1877      *
1878      * I am not aware that any OS does something as braindead, but this
1879      * situation could happen anyway when not committing for a long time.
1880      * Just to be sure that this does not bite us, detect it, and copy the
1881      * contents of the clusters to-be-overwritten into the qcow.
1882      */
1883     int copy_it = 0;
1884     int was_modified = 0;
1885     int32_t ret = 0;
1886
1887     uint32_t cluster_num = begin_of_direntry(direntry);
1888     uint32_t offset = 0;
1889     int first_mapping_index = -1;
1890     mapping_t* mapping = NULL;
1891     const char* basename2 = NULL;
1892
1893     vvfat_close_current_file(s);
1894
1895     /* the root directory */
1896     if (cluster_num == 0)
1897         return 0;
1898
1899     /* write support */
1900     if (s->qcow) {
1901         basename2 = get_basename(path);
1902
1903         mapping = find_mapping_for_cluster(s, cluster_num);
1904
1905         if (mapping) {
1906             const char* basename;
1907
1908             assert(mapping->mode & MODE_DELETED);
1909             mapping->mode &= ~MODE_DELETED;
1910
1911             basename = get_basename(mapping->path);
1912
1913             assert(mapping->mode & MODE_NORMAL);
1914
1915             /* rename */
1916             if (strcmp(basename, basename2))
1917                 schedule_rename(s, cluster_num, g_strdup(path));
1918         } else if (is_file(direntry))
1919             /* new file */
1920             schedule_new_file(s, g_strdup(path), cluster_num);
1921         else {
1922             abort();
1923             return 0;
1924         }
1925     }
1926
1927     while(1) {
1928         if (s->qcow) {
1929             if (!copy_it && cluster_was_modified(s, cluster_num)) {
1930                 if (mapping == NULL ||
1931                         mapping->begin > cluster_num ||
1932                         mapping->end <= cluster_num)
1933                 mapping = find_mapping_for_cluster(s, cluster_num);
1934
1935
1936                 if (mapping &&
1937                         (mapping->mode & MODE_DIRECTORY) == 0) {
1938
1939                     /* was modified in qcow */
1940                     if (offset != mapping->info.file.offset + s->cluster_size
1941                             * (cluster_num - mapping->begin)) {
1942                         /* offset of this cluster in file chain has changed */
1943                         abort();
1944                         copy_it = 1;
1945                     } else if (offset == 0) {
1946                         const char* basename = get_basename(mapping->path);
1947
1948                         if (strcmp(basename, basename2))
1949                             copy_it = 1;
1950                         first_mapping_index = array_index(&(s->mapping), mapping);
1951                     }
1952
1953                     if (mapping->first_mapping_index != first_mapping_index
1954                             && mapping->info.file.offset > 0) {
1955                         abort();
1956                         copy_it = 1;
1957                     }
1958
1959                     /* need to write out? */
1960                     if (!was_modified && is_file(direntry)) {
1961                         was_modified = 1;
1962                         schedule_writeout(s, mapping->dir_index, offset);
1963                     }
1964                 }
1965             }
1966
1967             if (copy_it) {
1968                 int i;
1969                 /*
1970                  * This is horribly inefficient, but that is okay, since
1971                  * it is rarely executed, if at all.
1972                  */
1973                 int64_t offset = cluster2sector(s, cluster_num);
1974
1975                 vvfat_close_current_file(s);
1976                 for (i = 0; i < s->sectors_per_cluster; i++) {
1977                     int res;
1978
1979                     res = bdrv_is_allocated(s->qcow->bs,
1980                                             (offset + i) * BDRV_SECTOR_SIZE,
1981                                             BDRV_SECTOR_SIZE, NULL);
1982                     if (res < 0) {
1983                         return -1;
1984                     }
1985                     if (!res) {
1986                         res = vvfat_read(s->bs, offset, s->cluster_buffer, 1);
1987                         if (res) {
1988                             return -1;
1989                         }
1990                         res = bdrv_write(s->qcow, offset, s->cluster_buffer, 1);
1991                         if (res) {
1992                             return -2;
1993                         }
1994                     }
1995                 }
1996             }
1997         }
1998
1999         ret++;
2000         if (s->used_clusters[cluster_num] & USED_ANY)
2001             return 0;
2002         s->used_clusters[cluster_num] = USED_FILE;
2003
2004         cluster_num = modified_fat_get(s, cluster_num);
2005
2006         if (fat_eof(s, cluster_num))
2007             return ret;
2008         else if (cluster_num < 2 || cluster_num > s->max_fat_value - 16)
2009             return -1;
2010
2011         offset += s->cluster_size;
2012     }
2013 }
2014
2015 /*
2016  * This function looks at the modified data (qcow).
2017  * It returns 0 upon inconsistency or error, and the number of clusters
2018  * used by the directory, its subdirectories and their files.
2019  */
2020 static int check_directory_consistency(BDRVVVFATState *s,
2021         int cluster_num, const char* path)
2022 {
2023     int ret = 0;
2024     unsigned char* cluster = g_malloc(s->cluster_size);
2025     direntry_t* direntries = (direntry_t*)cluster;
2026     mapping_t* mapping = find_mapping_for_cluster(s, cluster_num);
2027
2028     long_file_name lfn;
2029     int path_len = strlen(path);
2030     char path2[PATH_MAX + 1];
2031
2032     assert(path_len < PATH_MAX); /* len was tested before! */
2033     pstrcpy(path2, sizeof(path2), path);
2034     path2[path_len] = '/';
2035     path2[path_len + 1] = '\0';
2036
2037     if (mapping) {
2038         const char* basename = get_basename(mapping->path);
2039         const char* basename2 = get_basename(path);
2040
2041         assert(mapping->mode & MODE_DIRECTORY);
2042
2043         assert(mapping->mode & MODE_DELETED);
2044         mapping->mode &= ~MODE_DELETED;
2045
2046         if (strcmp(basename, basename2))
2047             schedule_rename(s, cluster_num, g_strdup(path));
2048     } else
2049         /* new directory */
2050         schedule_mkdir(s, cluster_num, g_strdup(path));
2051
2052     lfn_init(&lfn);
2053     do {
2054         int i;
2055         int subret = 0;
2056
2057         ret++;
2058
2059         if (s->used_clusters[cluster_num] & USED_ANY) {
2060             fprintf(stderr, "cluster %d used more than once\n", (int)cluster_num);
2061             goto fail;
2062         }
2063         s->used_clusters[cluster_num] = USED_DIRECTORY;
2064
2065 DLOG(fprintf(stderr, "read cluster %d (sector %d)\n", (int)cluster_num, (int)cluster2sector(s, cluster_num)));
2066         subret = vvfat_read(s->bs, cluster2sector(s, cluster_num), cluster,
2067                 s->sectors_per_cluster);
2068         if (subret) {
2069             fprintf(stderr, "Error fetching direntries\n");
2070         fail:
2071             g_free(cluster);
2072             return 0;
2073         }
2074
2075         for (i = 0; i < 0x10 * s->sectors_per_cluster; i++) {
2076             int cluster_count = 0;
2077
2078 DLOG(fprintf(stderr, "check direntry %d:\n", i); print_direntry(direntries + i));
2079             if (is_volume_label(direntries + i) || is_dot(direntries + i) ||
2080                     is_free(direntries + i))
2081                 continue;
2082
2083             subret = parse_long_name(&lfn, direntries + i);
2084             if (subret < 0) {
2085                 fprintf(stderr, "Error in long name\n");
2086                 goto fail;
2087             }
2088             if (subret == 0 || is_free(direntries + i))
2089                 continue;
2090
2091             if (fat_chksum(direntries+i) != lfn.checksum) {
2092                 subret = parse_short_name(s, &lfn, direntries + i);
2093                 if (subret < 0) {
2094                     fprintf(stderr, "Error in short name (%d)\n", subret);
2095                     goto fail;
2096                 }
2097                 if (subret > 0 || !strcmp((char*)lfn.name, ".")
2098                         || !strcmp((char*)lfn.name, ".."))
2099                     continue;
2100             }
2101             lfn.checksum = 0x100; /* cannot use long name twice */
2102
2103             if (path_len + 1 + lfn.len >= PATH_MAX) {
2104                 fprintf(stderr, "Name too long: %s/%s\n", path, lfn.name);
2105                 goto fail;
2106             }
2107             pstrcpy(path2 + path_len + 1, sizeof(path2) - path_len - 1,
2108                     (char*)lfn.name);
2109
2110             if (is_directory(direntries + i)) {
2111                 if (begin_of_direntry(direntries + i) == 0) {
2112                     DLOG(fprintf(stderr, "invalid begin for directory: %s\n", path2); print_direntry(direntries + i));
2113                     goto fail;
2114                 }
2115                 cluster_count = check_directory_consistency(s,
2116                         begin_of_direntry(direntries + i), path2);
2117                 if (cluster_count == 0) {
2118                     DLOG(fprintf(stderr, "problem in directory %s:\n", path2); print_direntry(direntries + i));
2119                     goto fail;
2120                 }
2121             } else if (is_file(direntries + i)) {
2122                 /* check file size with FAT */
2123                 cluster_count = get_cluster_count_for_direntry(s, direntries + i, path2);
2124                 if (cluster_count !=
2125             DIV_ROUND_UP(le32_to_cpu(direntries[i].size), s->cluster_size)) {
2126                     DLOG(fprintf(stderr, "Cluster count mismatch\n"));
2127                     goto fail;
2128                 }
2129             } else
2130                 abort(); /* cluster_count = 0; */
2131
2132             ret += cluster_count;
2133         }
2134
2135         cluster_num = modified_fat_get(s, cluster_num);
2136     } while(!fat_eof(s, cluster_num));
2137
2138     g_free(cluster);
2139     return ret;
2140 }
2141
2142 /* returns 1 on success */
2143 static int is_consistent(BDRVVVFATState* s)
2144 {
2145     int i, check;
2146     int used_clusters_count = 0;
2147
2148 DLOG(checkpoint());
2149     /*
2150      * - get modified FAT
2151      * - compare the two FATs (TODO)
2152      * - get buffer for marking used clusters
2153      * - recurse direntries from root (using bs->bdrv_read to make
2154      *    sure to get the new data)
2155      *   - check that the FAT agrees with the size
2156      *   - count the number of clusters occupied by this directory and
2157      *     its files
2158      * - check that the cumulative used cluster count agrees with the
2159      *   FAT
2160      * - if all is fine, return number of used clusters
2161      */
2162     if (s->fat2 == NULL) {
2163         int size = 0x200 * s->sectors_per_fat;
2164         s->fat2 = g_malloc(size);
2165         memcpy(s->fat2, s->fat.pointer, size);
2166     }
2167     check = vvfat_read(s->bs,
2168             s->offset_to_fat, s->fat2, s->sectors_per_fat);
2169     if (check) {
2170         fprintf(stderr, "Could not copy fat\n");
2171         return 0;
2172     }
2173     assert (s->used_clusters);
2174     for (i = 0; i < sector2cluster(s, s->sector_count); i++)
2175         s->used_clusters[i] &= ~USED_ANY;
2176
2177     clear_commits(s);
2178
2179     /* mark every mapped file/directory as deleted.
2180      * (check_directory_consistency() will unmark those still present). */
2181     if (s->qcow)
2182         for (i = 0; i < s->mapping.next; i++) {
2183             mapping_t* mapping = array_get(&(s->mapping), i);
2184             if (mapping->first_mapping_index < 0)
2185                 mapping->mode |= MODE_DELETED;
2186         }
2187
2188     used_clusters_count = check_directory_consistency(s, 0, s->path);
2189     if (used_clusters_count <= 0) {
2190         DLOG(fprintf(stderr, "problem in directory\n"));
2191         return 0;
2192     }
2193
2194     check = s->last_cluster_of_root_directory;
2195     for (i = check; i < sector2cluster(s, s->sector_count); i++) {
2196         if (modified_fat_get(s, i)) {
2197             if(!s->used_clusters[i]) {
2198                 DLOG(fprintf(stderr, "FAT was modified (%d), but cluster is not used?\n", i));
2199                 return 0;
2200             }
2201             check++;
2202         }
2203
2204         if (s->used_clusters[i] == USED_ALLOCATED) {
2205             /* allocated, but not used... */
2206             DLOG(fprintf(stderr, "unused, modified cluster: %d\n", i));
2207             return 0;
2208         }
2209     }
2210
2211     if (check != used_clusters_count)
2212         return 0;
2213
2214     return used_clusters_count;
2215 }
2216
2217 static inline void adjust_mapping_indices(BDRVVVFATState* s,
2218         int offset, int adjust)
2219 {
2220     int i;
2221
2222     for (i = 0; i < s->mapping.next; i++) {
2223         mapping_t* mapping = array_get(&(s->mapping), i);
2224
2225 #define ADJUST_MAPPING_INDEX(name) \
2226         if (mapping->name >= offset) \
2227             mapping->name += adjust
2228
2229         ADJUST_MAPPING_INDEX(first_mapping_index);
2230         if (mapping->mode & MODE_DIRECTORY)
2231             ADJUST_MAPPING_INDEX(info.dir.parent_mapping_index);
2232     }
2233 }
2234
2235 /* insert or update mapping */
2236 static mapping_t* insert_mapping(BDRVVVFATState* s,
2237         uint32_t begin, uint32_t end)
2238 {
2239     /*
2240      * - find mapping where mapping->begin >= begin,
2241      * - if mapping->begin > begin: insert
2242      *   - adjust all references to mappings!
2243      * - else: adjust
2244      * - replace name
2245      */
2246     int index = find_mapping_for_cluster_aux(s, begin, 0, s->mapping.next);
2247     mapping_t* mapping = NULL;
2248     mapping_t* first_mapping = array_get(&(s->mapping), 0);
2249
2250     if (index < s->mapping.next && (mapping = array_get(&(s->mapping), index))
2251             && mapping->begin < begin) {
2252         mapping->end = begin;
2253         index++;
2254         mapping = array_get(&(s->mapping), index);
2255     }
2256     if (index >= s->mapping.next || mapping->begin > begin) {
2257         mapping = array_insert(&(s->mapping), index, 1);
2258         mapping->path = NULL;
2259         adjust_mapping_indices(s, index, +1);
2260     }
2261
2262     mapping->begin = begin;
2263     mapping->end = end;
2264
2265 DLOG(mapping_t* next_mapping;
2266 assert(index + 1 >= s->mapping.next ||
2267 ((next_mapping = array_get(&(s->mapping), index + 1)) &&
2268  next_mapping->begin >= end)));
2269
2270     if (s->current_mapping && first_mapping != (mapping_t*)s->mapping.pointer)
2271         s->current_mapping = array_get(&(s->mapping),
2272                 s->current_mapping - first_mapping);
2273
2274     return mapping;
2275 }
2276
2277 static int remove_mapping(BDRVVVFATState* s, int mapping_index)
2278 {
2279     mapping_t* mapping = array_get(&(s->mapping), mapping_index);
2280     mapping_t* first_mapping = array_get(&(s->mapping), 0);
2281
2282     /* free mapping */
2283     if (mapping->first_mapping_index < 0) {
2284         g_free(mapping->path);
2285     }
2286
2287     /* remove from s->mapping */
2288     array_remove(&(s->mapping), mapping_index);
2289
2290     /* adjust all references to mappings */
2291     adjust_mapping_indices(s, mapping_index, -1);
2292
2293     if (s->current_mapping && first_mapping != (mapping_t*)s->mapping.pointer)
2294         s->current_mapping = array_get(&(s->mapping),
2295                 s->current_mapping - first_mapping);
2296
2297     return 0;
2298 }
2299
2300 static void adjust_dirindices(BDRVVVFATState* s, int offset, int adjust)
2301 {
2302     int i;
2303     for (i = 0; i < s->mapping.next; i++) {
2304         mapping_t* mapping = array_get(&(s->mapping), i);
2305         if (mapping->dir_index >= offset)
2306             mapping->dir_index += adjust;
2307         if ((mapping->mode & MODE_DIRECTORY) &&
2308                 mapping->info.dir.first_dir_index >= offset)
2309             mapping->info.dir.first_dir_index += adjust;
2310     }
2311 }
2312
2313 static direntry_t* insert_direntries(BDRVVVFATState* s,
2314         int dir_index, int count)
2315 {
2316     /*
2317      * make room in s->directory,
2318      * adjust_dirindices
2319      */
2320     direntry_t* result = array_insert(&(s->directory), dir_index, count);
2321     if (result == NULL)
2322         return NULL;
2323     adjust_dirindices(s, dir_index, count);
2324     return result;
2325 }
2326
2327 static int remove_direntries(BDRVVVFATState* s, int dir_index, int count)
2328 {
2329     int ret = array_remove_slice(&(s->directory), dir_index, count);
2330     if (ret)
2331         return ret;
2332     adjust_dirindices(s, dir_index, -count);
2333     return 0;
2334 }
2335
2336 /*
2337  * Adapt the mappings of the cluster chain starting at first cluster
2338  * (i.e. if a file starts at first_cluster, the chain is followed according
2339  * to the modified fat, and the corresponding entries in s->mapping are
2340  * adjusted)
2341  */
2342 static int commit_mappings(BDRVVVFATState* s,
2343         uint32_t first_cluster, int dir_index)
2344 {
2345     mapping_t* mapping = find_mapping_for_cluster(s, first_cluster);
2346     direntry_t* direntry = array_get(&(s->directory), dir_index);
2347     uint32_t cluster = first_cluster;
2348
2349     vvfat_close_current_file(s);
2350
2351     assert(mapping);
2352     assert(mapping->begin == first_cluster);
2353     mapping->first_mapping_index = -1;
2354     mapping->dir_index = dir_index;
2355     mapping->mode = (dir_index <= 0 || is_directory(direntry)) ?
2356         MODE_DIRECTORY : MODE_NORMAL;
2357
2358     while (!fat_eof(s, cluster)) {
2359         uint32_t c, c1;
2360
2361         for (c = cluster, c1 = modified_fat_get(s, c); c + 1 == c1;
2362                 c = c1, c1 = modified_fat_get(s, c1));
2363
2364         c++;
2365         if (c > mapping->end) {
2366             int index = array_index(&(s->mapping), mapping);
2367             int i, max_i = s->mapping.next - index;
2368             for (i = 1; i < max_i && mapping[i].begin < c; i++);
2369             while (--i > 0)
2370                 remove_mapping(s, index + 1);
2371         }
2372         assert(mapping == array_get(&(s->mapping), s->mapping.next - 1)
2373                 || mapping[1].begin >= c);
2374         mapping->end = c;
2375
2376         if (!fat_eof(s, c1)) {
2377             int i = find_mapping_for_cluster_aux(s, c1, 0, s->mapping.next);
2378             mapping_t* next_mapping = i >= s->mapping.next ? NULL :
2379                 array_get(&(s->mapping), i);
2380
2381             if (next_mapping == NULL || next_mapping->begin > c1) {
2382                 int i1 = array_index(&(s->mapping), mapping);
2383
2384                 next_mapping = insert_mapping(s, c1, c1+1);
2385
2386                 if (c1 < c)
2387                     i1++;
2388                 mapping = array_get(&(s->mapping), i1);
2389             }
2390
2391             next_mapping->dir_index = mapping->dir_index;
2392             next_mapping->first_mapping_index =
2393                 mapping->first_mapping_index < 0 ?
2394                 array_index(&(s->mapping), mapping) :
2395                 mapping->first_mapping_index;
2396             next_mapping->path = mapping->path;
2397             next_mapping->mode = mapping->mode;
2398             next_mapping->read_only = mapping->read_only;
2399             if (mapping->mode & MODE_DIRECTORY) {
2400                 next_mapping->info.dir.parent_mapping_index =
2401                         mapping->info.dir.parent_mapping_index;
2402                 next_mapping->info.dir.first_dir_index =
2403                         mapping->info.dir.first_dir_index +
2404                         0x10 * s->sectors_per_cluster *
2405                         (mapping->end - mapping->begin);
2406             } else
2407                 next_mapping->info.file.offset = mapping->info.file.offset +
2408                         mapping->end - mapping->begin;
2409
2410             mapping = next_mapping;
2411         }
2412
2413         cluster = c1;
2414     }
2415
2416     return 0;
2417 }
2418
2419 static int commit_direntries(BDRVVVFATState* s,
2420         int dir_index, int parent_mapping_index)
2421 {
2422     direntry_t* direntry = array_get(&(s->directory), dir_index);
2423     uint32_t first_cluster = dir_index == 0 ? 0 : begin_of_direntry(direntry);
2424     mapping_t* mapping = find_mapping_for_cluster(s, first_cluster);
2425
2426     int factor = 0x10 * s->sectors_per_cluster;
2427     int old_cluster_count, new_cluster_count;
2428     int current_dir_index = mapping->info.dir.first_dir_index;
2429     int first_dir_index = current_dir_index;
2430     int ret, i;
2431     uint32_t c;
2432
2433 DLOG(fprintf(stderr, "commit_direntries for %s, parent_mapping_index %d\n", mapping->path, parent_mapping_index));
2434
2435     assert(direntry);
2436     assert(mapping);
2437     assert(mapping->begin == first_cluster);
2438     assert(mapping->info.dir.first_dir_index < s->directory.next);
2439     assert(mapping->mode & MODE_DIRECTORY);
2440     assert(dir_index == 0 || is_directory(direntry));
2441
2442     mapping->info.dir.parent_mapping_index = parent_mapping_index;
2443
2444     if (first_cluster == 0) {
2445         old_cluster_count = new_cluster_count =
2446             s->last_cluster_of_root_directory;
2447     } else {
2448         for (old_cluster_count = 0, c = first_cluster; !fat_eof(s, c);
2449                 c = fat_get(s, c))
2450             old_cluster_count++;
2451
2452         for (new_cluster_count = 0, c = first_cluster; !fat_eof(s, c);
2453                 c = modified_fat_get(s, c))
2454             new_cluster_count++;
2455     }
2456
2457     if (new_cluster_count > old_cluster_count) {
2458         if (insert_direntries(s,
2459                 current_dir_index + factor * old_cluster_count,
2460                 factor * (new_cluster_count - old_cluster_count)) == NULL)
2461             return -1;
2462     } else if (new_cluster_count < old_cluster_count)
2463         remove_direntries(s,
2464                 current_dir_index + factor * new_cluster_count,
2465                 factor * (old_cluster_count - new_cluster_count));
2466
2467     for (c = first_cluster; !fat_eof(s, c); c = modified_fat_get(s, c)) {
2468         direntry_t *first_direntry;
2469         void* direntry = array_get(&(s->directory), current_dir_index);
2470         int ret = vvfat_read(s->bs, cluster2sector(s, c), direntry,
2471                 s->sectors_per_cluster);
2472         if (ret)
2473             return ret;
2474
2475         /* The first directory entry on the filesystem is the volume name */
2476         first_direntry = (direntry_t*) s->directory.pointer;
2477         assert(!memcmp(first_direntry->name, s->volume_label, 11));
2478
2479         current_dir_index += factor;
2480     }
2481
2482     ret = commit_mappings(s, first_cluster, dir_index);
2483     if (ret)
2484         return ret;
2485
2486     /* recurse */
2487     for (i = 0; i < factor * new_cluster_count; i++) {
2488         direntry = array_get(&(s->directory), first_dir_index + i);
2489         if (is_directory(direntry) && !is_dot(direntry)) {
2490             mapping = find_mapping_for_cluster(s, first_cluster);
2491             assert(mapping->mode & MODE_DIRECTORY);
2492             ret = commit_direntries(s, first_dir_index + i,
2493                 array_index(&(s->mapping), mapping));
2494             if (ret)
2495                 return ret;
2496         }
2497     }
2498
2499     return 0;
2500 }
2501
2502 /* commit one file (adjust contents, adjust mapping),
2503    return first_mapping_index */
2504 static int commit_one_file(BDRVVVFATState* s,
2505         int dir_index, uint32_t offset)
2506 {
2507     direntry_t* direntry = array_get(&(s->directory), dir_index);
2508     uint32_t c = begin_of_direntry(direntry);
2509     uint32_t first_cluster = c;
2510     mapping_t* mapping = find_mapping_for_cluster(s, c);
2511     uint32_t size = filesize_of_direntry(direntry);
2512     char* cluster = g_malloc(s->cluster_size);
2513     uint32_t i;
2514     int fd = 0;
2515
2516     assert(offset < size);
2517     assert((offset % s->cluster_size) == 0);
2518
2519     for (i = s->cluster_size; i < offset; i += s->cluster_size)
2520         c = modified_fat_get(s, c);
2521
2522     fd = qemu_open(mapping->path, O_RDWR | O_CREAT | O_BINARY, 0666);
2523     if (fd < 0) {
2524         fprintf(stderr, "Could not open %s... (%s, %d)\n", mapping->path,
2525                 strerror(errno), errno);
2526         g_free(cluster);
2527         return fd;
2528     }
2529     if (offset > 0) {
2530         if (lseek(fd, offset, SEEK_SET) != offset) {
2531             qemu_close(fd);
2532             g_free(cluster);
2533             return -3;
2534         }
2535     }
2536
2537     while (offset < size) {
2538         uint32_t c1;
2539         int rest_size = (size - offset > s->cluster_size ?
2540                 s->cluster_size : size - offset);
2541         int ret;
2542
2543         c1 = modified_fat_get(s, c);
2544
2545         assert((size - offset == 0 && fat_eof(s, c)) ||
2546                 (size > offset && c >=2 && !fat_eof(s, c)));
2547
2548         ret = vvfat_read(s->bs, cluster2sector(s, c),
2549             (uint8_t*)cluster, DIV_ROUND_UP(rest_size, 0x200));
2550
2551         if (ret < 0) {
2552             qemu_close(fd);
2553             g_free(cluster);
2554             return ret;
2555         }
2556
2557         if (write(fd, cluster, rest_size) < 0) {
2558             qemu_close(fd);
2559             g_free(cluster);
2560             return -2;
2561         }
2562
2563         offset += rest_size;
2564         c = c1;
2565     }
2566
2567     if (ftruncate(fd, size)) {
2568         perror("ftruncate()");
2569         qemu_close(fd);
2570         g_free(cluster);
2571         return -4;
2572     }
2573     qemu_close(fd);
2574     g_free(cluster);
2575
2576     return commit_mappings(s, first_cluster, dir_index);
2577 }
2578
2579 #ifdef DEBUG
2580 /* test, if all mappings point to valid direntries */
2581 static void check1(BDRVVVFATState* s)
2582 {
2583     int i;
2584     for (i = 0; i < s->mapping.next; i++) {
2585         mapping_t* mapping = array_get(&(s->mapping), i);
2586         if (mapping->mode & MODE_DELETED) {
2587             fprintf(stderr, "deleted\n");
2588             continue;
2589         }
2590         assert(mapping->dir_index < s->directory.next);
2591         direntry_t* direntry = array_get(&(s->directory), mapping->dir_index);
2592         assert(mapping->begin == begin_of_direntry(direntry) || mapping->first_mapping_index >= 0);
2593         if (mapping->mode & MODE_DIRECTORY) {
2594             assert(mapping->info.dir.first_dir_index + 0x10 * s->sectors_per_cluster * (mapping->end - mapping->begin) <= s->directory.next);
2595             assert((mapping->info.dir.first_dir_index % (0x10 * s->sectors_per_cluster)) == 0);
2596         }
2597     }
2598 }
2599
2600 /* test, if all direntries have mappings */
2601 static void check2(BDRVVVFATState* s)
2602 {
2603     int i;
2604     int first_mapping = -1;
2605
2606     for (i = 0; i < s->directory.next; i++) {
2607         direntry_t* direntry = array_get(&(s->directory), i);
2608
2609         if (is_short_name(direntry) && begin_of_direntry(direntry)) {
2610             mapping_t* mapping = find_mapping_for_cluster(s, begin_of_direntry(direntry));
2611             assert(mapping);
2612             assert(mapping->dir_index == i || is_dot(direntry));
2613             assert(mapping->begin == begin_of_direntry(direntry) || is_dot(direntry));
2614         }
2615
2616         if ((i % (0x10 * s->sectors_per_cluster)) == 0) {
2617             /* cluster start */
2618             int j, count = 0;
2619
2620             for (j = 0; j < s->mapping.next; j++) {
2621                 mapping_t* mapping = array_get(&(s->mapping), j);
2622                 if (mapping->mode & MODE_DELETED)
2623                     continue;
2624                 if (mapping->mode & MODE_DIRECTORY) {
2625                     if (mapping->info.dir.first_dir_index <= i && mapping->info.dir.first_dir_index + 0x10 * s->sectors_per_cluster > i) {
2626                         assert(++count == 1);
2627                         if (mapping->first_mapping_index == -1)
2628                             first_mapping = array_index(&(s->mapping), mapping);
2629                         else
2630                             assert(first_mapping == mapping->first_mapping_index);
2631                         if (mapping->info.dir.parent_mapping_index < 0)
2632                             assert(j == 0);
2633                         else {
2634                             mapping_t* parent = array_get(&(s->mapping), mapping->info.dir.parent_mapping_index);
2635                             assert(parent->mode & MODE_DIRECTORY);
2636                             assert(parent->info.dir.first_dir_index < mapping->info.dir.first_dir_index);
2637                         }
2638                     }
2639                 }
2640             }
2641             if (count == 0)
2642                 first_mapping = -1;
2643         }
2644     }
2645 }
2646 #endif
2647
2648 static int handle_renames_and_mkdirs(BDRVVVFATState* s)
2649 {
2650     int i;
2651
2652 #ifdef DEBUG
2653     fprintf(stderr, "handle_renames\n");
2654     for (i = 0; i < s->commits.next; i++) {
2655         commit_t* commit = array_get(&(s->commits), i);
2656         fprintf(stderr, "%d, %s (%d, %d)\n", i, commit->path ? commit->path : "(null)", commit->param.rename.cluster, commit->action);
2657     }
2658 #endif
2659
2660     for (i = 0; i < s->commits.next;) {
2661         commit_t* commit = array_get(&(s->commits), i);
2662         if (commit->action == ACTION_RENAME) {
2663             mapping_t* mapping = find_mapping_for_cluster(s,
2664                     commit->param.rename.cluster);
2665             char* old_path = mapping->path;
2666
2667             assert(commit->path);
2668             mapping->path = commit->path;
2669             if (rename(old_path, mapping->path))
2670                 return -2;
2671
2672             if (mapping->mode & MODE_DIRECTORY) {
2673                 int l1 = strlen(mapping->path);
2674                 int l2 = strlen(old_path);
2675                 int diff = l1 - l2;
2676                 direntry_t* direntry = array_get(&(s->directory),
2677                         mapping->info.dir.first_dir_index);
2678                 uint32_t c = mapping->begin;
2679                 int i = 0;
2680
2681                 /* recurse */
2682                 while (!fat_eof(s, c)) {
2683                     do {
2684                         direntry_t* d = direntry + i;
2685
2686                         if (is_file(d) || (is_directory(d) && !is_dot(d))) {
2687                             mapping_t* m = find_mapping_for_cluster(s,
2688                                     begin_of_direntry(d));
2689                             int l = strlen(m->path);
2690                             char* new_path = g_malloc(l + diff + 1);
2691
2692                             assert(!strncmp(m->path, mapping->path, l2));
2693
2694                             pstrcpy(new_path, l + diff + 1, mapping->path);
2695                             pstrcpy(new_path + l1, l + diff + 1 - l1,
2696                                     m->path + l2);
2697
2698                             schedule_rename(s, m->begin, new_path);
2699                         }
2700                         i++;
2701                     } while((i % (0x10 * s->sectors_per_cluster)) != 0);
2702                     c = fat_get(s, c);
2703                 }
2704             }
2705
2706             g_free(old_path);
2707             array_remove(&(s->commits), i);
2708             continue;
2709         } else if (commit->action == ACTION_MKDIR) {
2710             mapping_t* mapping;
2711             int j, parent_path_len;
2712
2713 #ifdef __MINGW32__
2714             if (mkdir(commit->path))
2715                 return -5;
2716 #else
2717             if (mkdir(commit->path, 0755))
2718                 return -5;
2719 #endif
2720
2721             mapping = insert_mapping(s, commit->param.mkdir.cluster,
2722                     commit->param.mkdir.cluster + 1);
2723             if (mapping == NULL)
2724                 return -6;
2725
2726             mapping->mode = MODE_DIRECTORY;
2727             mapping->read_only = 0;
2728             mapping->path = commit->path;
2729             j = s->directory.next;
2730             assert(j);
2731             insert_direntries(s, s->directory.next,
2732                     0x10 * s->sectors_per_cluster);
2733             mapping->info.dir.first_dir_index = j;
2734
2735             parent_path_len = strlen(commit->path)
2736                 - strlen(get_basename(commit->path)) - 1;
2737             for (j = 0; j < s->mapping.next; j++) {
2738                 mapping_t* m = array_get(&(s->mapping), j);
2739                 if (m->first_mapping_index < 0 && m != mapping &&
2740                         !strncmp(m->path, mapping->path, parent_path_len) &&
2741                         strlen(m->path) == parent_path_len)
2742                     break;
2743             }
2744             assert(j < s->mapping.next);
2745             mapping->info.dir.parent_mapping_index = j;
2746
2747             array_remove(&(s->commits), i);
2748             continue;
2749         }
2750
2751         i++;
2752     }
2753     return 0;
2754 }
2755
2756 /*
2757  * TODO: make sure that the short name is not matching *another* file
2758  */
2759 static int handle_commits(BDRVVVFATState* s)
2760 {
2761     int i, fail = 0;
2762
2763     vvfat_close_current_file(s);
2764
2765     for (i = 0; !fail && i < s->commits.next; i++) {
2766         commit_t* commit = array_get(&(s->commits), i);
2767         switch(commit->action) {
2768         case ACTION_RENAME: case ACTION_MKDIR:
2769             abort();
2770             fail = -2;
2771             break;
2772         case ACTION_WRITEOUT: {
2773 #ifndef NDEBUG
2774             /* these variables are only used by assert() below */
2775             direntry_t* entry = array_get(&(s->directory),
2776                     commit->param.writeout.dir_index);
2777             uint32_t begin = begin_of_direntry(entry);
2778             mapping_t* mapping = find_mapping_for_cluster(s, begin);
2779 #endif
2780
2781             assert(mapping);
2782             assert(mapping->begin == begin);
2783             assert(commit->path == NULL);
2784
2785             if (commit_one_file(s, commit->param.writeout.dir_index,
2786                         commit->param.writeout.modified_offset))
2787                 fail = -3;
2788
2789             break;
2790         }
2791         case ACTION_NEW_FILE: {
2792             int begin = commit->param.new_file.first_cluster;
2793             mapping_t* mapping = find_mapping_for_cluster(s, begin);
2794             direntry_t* entry;
2795             int i;
2796
2797             /* find direntry */
2798             for (i = 0; i < s->directory.next; i++) {
2799                 entry = array_get(&(s->directory), i);
2800                 if (is_file(entry) && begin_of_direntry(entry) == begin)
2801                     break;
2802             }
2803
2804             if (i >= s->directory.next) {
2805                 fail = -6;
2806                 continue;
2807             }
2808
2809             /* make sure there exists an initial mapping */
2810             if (mapping && mapping->begin != begin) {
2811                 mapping->end = begin;
2812                 mapping = NULL;
2813             }
2814             if (mapping == NULL) {
2815                 mapping = insert_mapping(s, begin, begin+1);
2816             }
2817             /* most members will be fixed in commit_mappings() */
2818             assert(commit->path);
2819             mapping->path = commit->path;
2820             mapping->read_only = 0;
2821             mapping->mode = MODE_NORMAL;
2822             mapping->info.file.offset = 0;
2823
2824             if (commit_one_file(s, i, 0))
2825                 fail = -7;
2826
2827             break;
2828         }
2829         default:
2830             abort();
2831         }
2832     }
2833     if (i > 0 && array_remove_slice(&(s->commits), 0, i))
2834         return -1;
2835     return fail;
2836 }
2837
2838 static int handle_deletes(BDRVVVFATState* s)
2839 {
2840     int i, deferred = 1, deleted = 1;
2841
2842     /* delete files corresponding to mappings marked as deleted */
2843     /* handle DELETEs and unused mappings (modified_fat_get(s, mapping->begin) == 0) */
2844     while (deferred && deleted) {
2845         deferred = 0;
2846         deleted = 0;
2847
2848         for (i = 1; i < s->mapping.next; i++) {
2849             mapping_t* mapping = array_get(&(s->mapping), i);
2850             if (mapping->mode & MODE_DELETED) {
2851                 direntry_t* entry = array_get(&(s->directory),
2852                         mapping->dir_index);
2853
2854                 if (is_free(entry)) {
2855                     /* remove file/directory */
2856                     if (mapping->mode & MODE_DIRECTORY) {
2857                         int j, next_dir_index = s->directory.next,
2858                         first_dir_index = mapping->info.dir.first_dir_index;
2859
2860                         if (rmdir(mapping->path) < 0) {
2861                             if (errno == ENOTEMPTY) {
2862                                 deferred++;
2863                                 continue;
2864                             } else
2865                                 return -5;
2866                         }
2867
2868                         for (j = 1; j < s->mapping.next; j++) {
2869                             mapping_t* m = array_get(&(s->mapping), j);
2870                             if (m->mode & MODE_DIRECTORY &&
2871                                     m->info.dir.first_dir_index >
2872                                     first_dir_index &&
2873                                     m->info.dir.first_dir_index <
2874                                     next_dir_index)
2875                                 next_dir_index =
2876                                     m->info.dir.first_dir_index;
2877                         }
2878                         remove_direntries(s, first_dir_index,
2879                                 next_dir_index - first_dir_index);
2880
2881                         deleted++;
2882                     }
2883                 } else {
2884                     if (unlink(mapping->path))
2885                         return -4;
2886                     deleted++;
2887                 }
2888                 DLOG(fprintf(stderr, "DELETE (%d)\n", i); print_mapping(mapping); print_direntry(entry));
2889                 remove_mapping(s, i);
2890             }
2891         }
2892     }
2893
2894     return 0;
2895 }
2896
2897 /*
2898  * synchronize mapping with new state:
2899  *
2900  * - copy FAT (with bdrv_read)
2901  * - mark all filenames corresponding to mappings as deleted
2902  * - recurse direntries from root (using bs->bdrv_read)
2903  * - delete files corresponding to mappings marked as deleted
2904  */
2905 static int do_commit(BDRVVVFATState* s)
2906 {
2907     int ret = 0;
2908
2909     /* the real meat are the commits. Nothing to do? Move along! */
2910     if (s->commits.next == 0)
2911         return 0;
2912
2913     vvfat_close_current_file(s);
2914
2915     ret = handle_renames_and_mkdirs(s);
2916     if (ret) {
2917         fprintf(stderr, "Error handling renames (%d)\n", ret);
2918         abort();
2919         return ret;
2920     }
2921
2922     /* copy FAT (with bdrv_read) */
2923     memcpy(s->fat.pointer, s->fat2, 0x200 * s->sectors_per_fat);
2924
2925     /* recurse direntries from root (using bs->bdrv_read) */
2926     ret = commit_direntries(s, 0, -1);
2927     if (ret) {
2928         fprintf(stderr, "Fatal: error while committing (%d)\n", ret);
2929         abort();
2930         return ret;
2931     }
2932
2933     ret = handle_commits(s);
2934     if (ret) {
2935         fprintf(stderr, "Error handling commits (%d)\n", ret);
2936         abort();
2937         return ret;
2938     }
2939
2940     ret = handle_deletes(s);
2941     if (ret) {
2942         fprintf(stderr, "Error deleting\n");
2943         abort();
2944         return ret;
2945     }
2946
2947     if (s->qcow->bs->drv && s->qcow->bs->drv->bdrv_make_empty) {
2948         s->qcow->bs->drv->bdrv_make_empty(s->qcow->bs);
2949     }
2950
2951     memset(s->used_clusters, 0, sector2cluster(s, s->sector_count));
2952
2953 DLOG(checkpoint());
2954     return 0;
2955 }
2956
2957 static int try_commit(BDRVVVFATState* s)
2958 {
2959     vvfat_close_current_file(s);
2960 DLOG(checkpoint());
2961     if(!is_consistent(s))
2962         return -1;
2963     return do_commit(s);
2964 }
2965
2966 static int vvfat_write(BlockDriverState *bs, int64_t sector_num,
2967                     const uint8_t *buf, int nb_sectors)
2968 {
2969     BDRVVVFATState *s = bs->opaque;
2970     int i, ret;
2971
2972 DLOG(checkpoint());
2973
2974     /* Check if we're operating in read-only mode */
2975     if (s->qcow == NULL) {
2976         return -EACCES;
2977     }
2978
2979     vvfat_close_current_file(s);
2980
2981     /*
2982      * Some sanity checks:
2983      * - do not allow writing to the boot sector
2984      */
2985
2986     if (sector_num < s->offset_to_fat)
2987         return -1;
2988
2989     for (i = sector2cluster(s, sector_num);
2990             i <= sector2cluster(s, sector_num + nb_sectors - 1);) {
2991         mapping_t* mapping = find_mapping_for_cluster(s, i);
2992         if (mapping) {
2993             if (mapping->read_only) {
2994                 fprintf(stderr, "Tried to write to write-protected file %s\n",
2995                         mapping->path);
2996                 return -1;
2997             }
2998
2999             if (mapping->mode & MODE_DIRECTORY) {
3000                 int begin = cluster2sector(s, i);
3001                 int end = begin + s->sectors_per_cluster, k;
3002                 int dir_index;
3003                 const direntry_t* direntries;
3004                 long_file_name lfn;
3005
3006                 lfn_init(&lfn);
3007
3008                 if (begin < sector_num)
3009                     begin = sector_num;
3010                 if (end > sector_num + nb_sectors)
3011                     end = sector_num + nb_sectors;
3012                 dir_index  = mapping->dir_index +
3013                     0x10 * (begin - mapping->begin * s->sectors_per_cluster);
3014                 direntries = (direntry_t*)(buf + 0x200 * (begin - sector_num));
3015
3016                 for (k = 0; k < (end - begin) * 0x10; k++) {
3017                     /* no access to the direntry of a read-only file */
3018                     if (is_short_name(direntries + k) &&
3019                             (direntries[k].attributes & 1)) {
3020                         if (memcmp(direntries + k,
3021                                     array_get(&(s->directory), dir_index + k),
3022                                     sizeof(direntry_t))) {
3023                             warn_report("tried to write to write-protected "
3024                                         "file");
3025                             return -1;
3026                         }
3027                     }
3028                 }
3029             }
3030             i = mapping->end;
3031         } else
3032             i++;
3033     }
3034
3035     /*
3036      * Use qcow backend. Commit later.
3037      */
3038 DLOG(fprintf(stderr, "Write to qcow backend: %d + %d\n", (int)sector_num, nb_sectors));
3039     ret = bdrv_write(s->qcow, sector_num, buf, nb_sectors);
3040     if (ret < 0) {
3041         fprintf(stderr, "Error writing to qcow backend\n");
3042         return ret;
3043     }
3044
3045     for (i = sector2cluster(s, sector_num);
3046             i <= sector2cluster(s, sector_num + nb_sectors - 1); i++)
3047         if (i >= 0)
3048             s->used_clusters[i] |= USED_ALLOCATED;
3049
3050 DLOG(checkpoint());
3051     /* TODO: add timeout */
3052     try_commit(s);
3053
3054 DLOG(checkpoint());
3055     return 0;
3056 }
3057
3058 static int coroutine_fn
3059 vvfat_co_pwritev(BlockDriverState *bs, uint64_t offset, uint64_t bytes,
3060                  QEMUIOVector *qiov, int flags)
3061 {
3062     int ret;
3063     BDRVVVFATState *s = bs->opaque;
3064     uint64_t sector_num = offset >> BDRV_SECTOR_BITS;
3065     int nb_sectors = bytes >> BDRV_SECTOR_BITS;
3066     void *buf;
3067
3068     assert((offset & (BDRV_SECTOR_SIZE - 1)) == 0);
3069     assert((bytes & (BDRV_SECTOR_SIZE - 1)) == 0);
3070
3071     buf = g_try_malloc(bytes);
3072     if (bytes && buf == NULL) {
3073         return -ENOMEM;
3074     }
3075     qemu_iovec_to_buf(qiov, 0, buf, bytes);
3076
3077     qemu_co_mutex_lock(&s->lock);
3078     ret = vvfat_write(bs, sector_num, buf, nb_sectors);
3079     qemu_co_mutex_unlock(&s->lock);
3080
3081     g_free(buf);
3082
3083     return ret;
3084 }
3085
3086 static int coroutine_fn vvfat_co_block_status(BlockDriverState *bs,
3087                                               bool want_zero, int64_t offset,
3088                                               int64_t bytes, int64_t *n,
3089                                               int64_t *map,
3090                                               BlockDriverState **file)
3091 {
3092     *n = bytes;
3093     return BDRV_BLOCK_DATA;
3094 }
3095
3096 static int coroutine_fn
3097 write_target_commit(BlockDriverState *bs, uint64_t offset, uint64_t bytes,
3098                     QEMUIOVector *qiov, int flags)
3099 {
3100     int ret;
3101
3102     BDRVVVFATState* s = *((BDRVVVFATState**) bs->opaque);
3103     qemu_co_mutex_lock(&s->lock);
3104     ret = try_commit(s);
3105     qemu_co_mutex_unlock(&s->lock);
3106
3107     return ret;
3108 }
3109
3110 static void write_target_close(BlockDriverState *bs) {
3111     BDRVVVFATState* s = *((BDRVVVFATState**) bs->opaque);
3112     bdrv_unref_child(s->bs, s->qcow);
3113     g_free(s->qcow_filename);
3114 }
3115
3116 static BlockDriver vvfat_write_target = {
3117     .format_name        = "vvfat_write_target",
3118     .instance_size      = sizeof(void*),
3119     .bdrv_co_pwritev    = write_target_commit,
3120     .bdrv_close         = write_target_close,
3121 };
3122
3123 static void vvfat_qcow_options(int *child_flags, QDict *child_options,
3124                                int parent_flags, QDict *parent_options)
3125 {
3126     qdict_set_default_str(child_options, BDRV_OPT_READ_ONLY, "off");
3127     qdict_set_default_str(child_options, BDRV_OPT_AUTO_READ_ONLY, "off");
3128     qdict_set_default_str(child_options, BDRV_OPT_CACHE_NO_FLUSH, "on");
3129 }
3130
3131 static const BdrvChildRole child_vvfat_qcow = {
3132     .parent_is_bds      = true,
3133     .inherit_options    = vvfat_qcow_options,
3134 };
3135
3136 static int enable_write_target(BlockDriverState *bs, Error **errp)
3137 {
3138     BDRVVVFATState *s = bs->opaque;
3139     BlockDriver *bdrv_qcow = NULL;
3140     BlockDriverState *backing;
3141     QemuOpts *opts = NULL;
3142     int ret;
3143     int size = sector2cluster(s, s->sector_count);
3144     QDict *options;
3145
3146     s->used_clusters = calloc(size, 1);
3147
3148     array_init(&(s->commits), sizeof(commit_t));
3149
3150     s->qcow_filename = g_malloc(PATH_MAX);
3151     ret = get_tmp_filename(s->qcow_filename, PATH_MAX);
3152     if (ret < 0) {
3153         error_setg_errno(errp, -ret, "can't create temporary file");
3154         goto err;
3155     }
3156
3157     bdrv_qcow = bdrv_find_format("qcow");
3158     if (!bdrv_qcow) {
3159         error_setg(errp, "Failed to locate qcow driver");
3160         ret = -ENOENT;
3161         goto err;
3162     }
3163
3164     opts = qemu_opts_create(bdrv_qcow->create_opts, NULL, 0, &error_abort);
3165     qemu_opt_set_number(opts, BLOCK_OPT_SIZE, s->sector_count * 512,
3166                         &error_abort);
3167     qemu_opt_set(opts, BLOCK_OPT_BACKING_FILE, "fat:", &error_abort);
3168
3169     ret = bdrv_create(bdrv_qcow, s->qcow_filename, opts, errp);
3170     qemu_opts_del(opts);
3171     if (ret < 0) {
3172         goto err;
3173     }
3174
3175     options = qdict_new();
3176     qdict_put_str(options, "write-target.driver", "qcow");
3177     s->qcow = bdrv_open_child(s->qcow_filename, options, "write-target", bs,
3178                               &child_vvfat_qcow, false, errp);
3179     qobject_unref(options);
3180     if (!s->qcow) {
3181         ret = -EINVAL;
3182         goto err;
3183     }
3184
3185 #ifndef _WIN32
3186     unlink(s->qcow_filename);
3187 #endif
3188
3189     backing = bdrv_new_open_driver(&vvfat_write_target, NULL, BDRV_O_ALLOW_RDWR,
3190                                    &error_abort);
3191     *(void**) backing->opaque = s;
3192
3193     bdrv_set_backing_hd(s->bs, backing, &error_abort);
3194     bdrv_unref(backing);
3195
3196     return 0;
3197
3198 err:
3199     g_free(s->qcow_filename);
3200     s->qcow_filename = NULL;
3201     return ret;
3202 }
3203
3204 static void vvfat_child_perm(BlockDriverState *bs, BdrvChild *c,
3205                              const BdrvChildRole *role,
3206                              BlockReopenQueue *reopen_queue,
3207                              uint64_t perm, uint64_t shared,
3208                              uint64_t *nperm, uint64_t *nshared)
3209 {
3210     BDRVVVFATState *s = bs->opaque;
3211
3212     assert(c == s->qcow || role == &child_backing);
3213
3214     if (c == s->qcow) {
3215         /* This is a private node, nobody should try to attach to it */
3216         *nperm = BLK_PERM_CONSISTENT_READ | BLK_PERM_WRITE;
3217         *nshared = BLK_PERM_WRITE_UNCHANGED;
3218     } else {
3219         /* The backing file is there so 'commit' can use it. vvfat doesn't
3220          * access it in any way. */
3221         *nperm = 0;
3222         *nshared = BLK_PERM_ALL;
3223     }
3224 }
3225
3226 static void vvfat_close(BlockDriverState *bs)
3227 {
3228     BDRVVVFATState *s = bs->opaque;
3229
3230     vvfat_close_current_file(s);
3231     array_free(&(s->fat));
3232     array_free(&(s->directory));
3233     array_free(&(s->mapping));
3234     g_free(s->cluster_buffer);
3235
3236     if (s->qcow) {
3237         migrate_del_blocker(s->migration_blocker);
3238         error_free(s->migration_blocker);
3239     }
3240 }
3241
3242 static BlockDriver bdrv_vvfat = {
3243     .format_name            = "vvfat",
3244     .protocol_name          = "fat",
3245     .instance_size          = sizeof(BDRVVVFATState),
3246
3247     .bdrv_parse_filename    = vvfat_parse_filename,
3248     .bdrv_file_open         = vvfat_open,
3249     .bdrv_refresh_limits    = vvfat_refresh_limits,
3250     .bdrv_close             = vvfat_close,
3251     .bdrv_child_perm        = vvfat_child_perm,
3252
3253     .bdrv_co_preadv         = vvfat_co_preadv,
3254     .bdrv_co_pwritev        = vvfat_co_pwritev,
3255     .bdrv_co_block_status   = vvfat_co_block_status,
3256 };
3257
3258 static void bdrv_vvfat_init(void)
3259 {
3260     bdrv_register(&bdrv_vvfat);
3261 }
3262
3263 block_init(bdrv_vvfat_init);
3264
3265 #ifdef DEBUG
3266 static void checkpoint(void)
3267 {
3268     assert(((mapping_t*)array_get(&(vvv->mapping), 0))->end == 2);
3269     check1(vvv);
3270     check2(vvv);
3271     assert(!vvv->current_mapping || vvv->current_fd || (vvv->current_mapping->mode & MODE_DIRECTORY));
3272 }
3273 #endif