sbin/fsck_msdosfs/fat.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause
   3  *
   4  * Copyright (c) 2019 Google LLC
   5  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
   6  * Copyright (c) 1995 Martin Husemann
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29
  30 #include <sys/cdefs.h>
  31 #ifndef lint
  32 __RCSID("$NetBSD: fat.c,v 1.18 2006/06/05 16:51:18 christos Exp $");
  33 static const char rcsid[] =
  34   "$FreeBSD$";
  35 #endif /* not lint */
  36
  37 #include <sys/endian.h>
  38 #include <sys/queue.h>
  39 #include <sys/limits.h>
  40 #include <sys/mman.h>
  41 #include <sys/param.h>
  42
  43 #include <assert.h>
  44 #include <stdbool.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <ctype.h>
  48 #include <stdio.h>
  49 #include <unistd.h>
  50
  51 #include "ext.h"
  52 #include "fsutil.h"
  53
  54 static int _readfat(struct fat_descriptor *);
  55 static inline struct bootblock* boot_of_(struct fat_descriptor *);
  56 static inline int fd_of_(struct fat_descriptor *);
  57 static inline bool valid_cl(struct fat_descriptor *, cl_t);
  58
  59
  60 /*
  61  * Head bitmap for FAT scanning.
  62  *
  63  * FAT32 have up to 2^28 = 256M entries, and FAT16/12 have much less.
  64  * For each cluster, we use 1 bit to represent if it's a head cluster
  65  * (the first cluster of a cluster chain).
  66  *
  67  * Head bitmap
  68  * ===========
  69  * Initially, we set all bits to 1.  In readfat(), we traverse the
  70  * whole FAT and mark each cluster identified as "next" cluster as
  71  * 0.  After the scan, we have a bitmap with 1's to indicate the
  72  * corresponding cluster was a "head" cluster.
  73  *
  74  * We use head bitmap to identify lost chains: a head cluster that was
  75  * not being claimed by any file or directories is the head cluster of
  76  * a lost chain.
  77  *
  78  * Handle of lost chains
  79  * =====================
  80  * At the end of scanning, we can easily find all lost chain's heads
  81  * by finding out the 1's in the head bitmap.
  82  */
  83
  84 typedef struct long_bitmap {
  85         unsigned long   *map;
  86         size_t           count;         /* Total set bits in the map */
  87 } long_bitmap_t;
  88
  89 static inline void
  90 bitmap_clear(long_bitmap_t *lbp, cl_t cl)
  91 {
  92         cl_t i = cl / LONG_BIT;
  93         unsigned long clearmask = ~(1UL << (cl % LONG_BIT));
  94
  95         assert((lbp->map[i] & ~clearmask) != 0);
  96         lbp->map[i] &= clearmask;
  97         lbp->count--;
  98 }
  99
 100 static inline bool
 101 bitmap_get(long_bitmap_t *lbp, cl_t cl)
 102 {
 103         cl_t i = cl / LONG_BIT;
 104         unsigned long usedbit = 1UL << (cl % LONG_BIT);
 105
 106         return ((lbp->map[i] & usedbit) == usedbit);
 107 }
 108
 109 static inline bool
 110 bitmap_none_in_range(long_bitmap_t *lbp, cl_t cl)
 111 {
 112         cl_t i = cl / LONG_BIT;
 113
 114         return (lbp->map[i] == 0);
 115 }
 116
 117 static inline size_t
 118 bitmap_count(long_bitmap_t *lbp)
 119 {
 120         return (lbp->count);
 121 }
 122
 123 static int
 124 bitmap_ctor(long_bitmap_t *lbp, size_t bits, bool allone)
 125 {
 126         size_t bitmap_size = roundup2(bits, LONG_BIT) / (LONG_BIT / 8);
 127
 128         free(lbp->map);
 129         lbp->map = calloc(1, bitmap_size);
 130         if (lbp->map == NULL)
 131                 return FSFATAL;
 132
 133         if (allone) {
 134                 memset(lbp->map, 0xff, bitmap_size);
 135                 lbp->count = bits;
 136         } else {
 137                 lbp->count = 0;
 138         }
 139         return FSOK;
 140 }
 141
 142 static void
 143 bitmap_dtor(long_bitmap_t *lbp)
 144 {
 145         free(lbp->map);
 146         lbp->map = NULL;
 147 }
 148
 149 /*
 150  * FAT32 can be as big as 256MiB (2^26 entries * 4 bytes), when we
 151  * can not ask the kernel to manage the access, use a simple LRU
 152  * cache with chunk size of 128 KiB to manage it.
 153  */
 154 struct fat32_cache_entry {
 155         TAILQ_ENTRY(fat32_cache_entry)  entries;
 156         uint8_t                 *chunk;         /* pointer to chunk */
 157         off_t                    addr;          /* offset */
 158         bool                     dirty;         /* dirty bit */
 159 };
 160
 161 static const size_t     fat32_cache_chunk_size = 131072; /* MAXPHYS */
 162 static const size_t     fat32_cache_size = 4194304;
 163 static const size_t     fat32_cache_entries = 32; /* XXXgcc: cache_size / cache_chunk_size */
 164
 165 /*
 166  * FAT table descriptor, represents a FAT table that is already loaded
 167  * into memory.
 168  */
 169 struct fat_descriptor {
 170         struct bootblock        *boot;
 171         uint8_t                 *fatbuf;
 172         cl_t                    (*get)(struct fat_descriptor *, cl_t);
 173         int                     (*set)(struct fat_descriptor *, cl_t, cl_t);
 174         long_bitmap_t            headbitmap;
 175         int                      fd;
 176         bool                     is_mmapped;
 177         bool                     use_cache;
 178         size_t                   fatsize;
 179
 180         size_t                   fat32_cached_chunks;
 181         TAILQ_HEAD(cachehead, fat32_cache_entry)        fat32_cache_head;
 182         struct fat32_cache_entry        *fat32_cache_allentries;
 183         off_t                    fat32_offset;
 184         off_t                    fat32_lastaddr;
 185 };
 186
 187 void
 188 fat_clear_cl_head(struct fat_descriptor *fat, cl_t cl)
 189 {
 190         bitmap_clear(&fat->headbitmap, cl);
 191 }
 192
 193 bool
 194 fat_is_cl_head(struct fat_descriptor *fat, cl_t cl)
 195 {
 196         return (bitmap_get(&fat->headbitmap, cl));
 197 }
 198
 199 static inline bool
 200 fat_is_cl_head_in_range(struct fat_descriptor *fat, cl_t cl)
 201 {
 202         return (!(bitmap_none_in_range(&fat->headbitmap, cl)));
 203 }
 204
 205 static size_t
 206 fat_get_head_count(struct fat_descriptor *fat)
 207 {
 208         return (bitmap_count(&fat->headbitmap));
 209 }
 210
 211 /*
 212  * FAT12 accessors.
 213  *
 214  * FAT12s are sufficiently small, expect it to always fit in the RAM.
 215  */
 216 static inline uint8_t *
 217 fat_get_fat12_ptr(struct fat_descriptor *fat, cl_t cl)
 218 {
 219         return (fat->fatbuf + ((cl + (cl >> 1))));
 220 }
 221
 222 static cl_t
 223 fat_get_fat12_next(struct fat_descriptor *fat, cl_t cl)
 224 {
 225         const uint8_t   *p;
 226         cl_t    retval;
 227
 228         p = fat_get_fat12_ptr(fat, cl);
 229         retval = le16dec(p);
 230         /* Odd cluster: lower 4 bits belongs to the subsequent cluster */
 231         if ((cl & 1) == 1)
 232                 retval >>= 4;
 233         retval &= CLUST12_MASK;
 234
 235         if (retval >= (CLUST_BAD & CLUST12_MASK))
 236                 retval |= ~CLUST12_MASK;
 237
 238         return (retval);
 239 }
 240
 241 static int
 242 fat_set_fat12_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
 243 {
 244         uint8_t *p;
 245
 246         /* Truncate 'nextcl' value, if needed */
 247         nextcl &= CLUST12_MASK;
 248
 249         p = fat_get_fat12_ptr(fat, cl);
 250
 251         /*
 252          * Read in the 4 bits from the subsequent (for even clusters)
 253          * or the preceding (for odd clusters) cluster and combine
 254          * it to the nextcl value for encoding
 255          */
 256         if ((cl & 1) == 0) {
 257                 nextcl |= ((p[1] & 0xf0) << 8);
 258         } else {
 259                 nextcl <<= 4;
 260                 nextcl |= (p[0] & 0x0f);
 261         }
 262
 263         le16enc(p, (uint16_t)nextcl);
 264
 265         return (0);
 266 }
 267
 268 /*
 269  * FAT16 accessors.
 270  *
 271  * FAT16s are sufficiently small, expect it to always fit in the RAM.
 272  */
 273 static inline uint8_t *
 274 fat_get_fat16_ptr(struct fat_descriptor *fat, cl_t cl)
 275 {
 276         return (fat->fatbuf + (cl << 1));
 277 }
 278
 279 static cl_t
 280 fat_get_fat16_next(struct fat_descriptor *fat, cl_t cl)
 281 {
 282         const uint8_t   *p;
 283         cl_t    retval;
 284
 285         p = fat_get_fat16_ptr(fat, cl);
 286         retval = le16dec(p) & CLUST16_MASK;
 287
 288         if (retval >= (CLUST_BAD & CLUST16_MASK))
 289                 retval |= ~CLUST16_MASK;
 290
 291         return (retval);
 292 }
 293
 294 static int
 295 fat_set_fat16_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
 296 {
 297         uint8_t *p;
 298
 299         /* Truncate 'nextcl' value, if needed */
 300         nextcl &= CLUST16_MASK;
 301
 302         p = fat_get_fat16_ptr(fat, cl);
 303
 304         le16enc(p, (uint16_t)nextcl);
 305
 306         return (0);
 307 }
 308
 309 /*
 310  * FAT32 accessors.
 311  */
 312 static inline uint8_t *
 313 fat_get_fat32_ptr(struct fat_descriptor *fat, cl_t cl)
 314 {
 315         return (fat->fatbuf + (cl << 2));
 316 }
 317
 318 static cl_t
 319 fat_get_fat32_next(struct fat_descriptor *fat, cl_t cl)
 320 {
 321         const uint8_t   *p;
 322         cl_t    retval;
 323
 324         p = fat_get_fat32_ptr(fat, cl);
 325         retval = le32dec(p) & CLUST32_MASK;
 326
 327         if (retval >= (CLUST_BAD & CLUST32_MASK))
 328                 retval |= ~CLUST32_MASK;
 329
 330         return (retval);
 331 }
 332
 333 static int
 334 fat_set_fat32_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
 335 {
 336         uint8_t *p;
 337
 338         /* Truncate 'nextcl' value, if needed */
 339         nextcl &= CLUST32_MASK;
 340
 341         p = fat_get_fat32_ptr(fat, cl);
 342
 343         le32enc(p, (uint32_t)nextcl);
 344
 345         return (0);
 346 }
 347
 348 static inline size_t
 349 fat_get_iosize(struct fat_descriptor *fat, off_t address)
 350 {
 351
 352         if (address == fat->fat32_lastaddr) {
 353                 return (fat->fatsize & ((off_t)fat32_cache_chunk_size - 1));
 354         } else {
 355                 return (fat32_cache_chunk_size);
 356         }
 357 }
 358
 359 static int
 360 fat_flush_fat32_cache_entry(struct fat_descriptor *fat,
 361     struct fat32_cache_entry *entry)
 362 {
 363         int fd;
 364         off_t fat_addr;
 365         size_t writesize;
 366
 367         fd = fd_of_(fat);
 368
 369         if (!entry->dirty)
 370                 return (FSOK);
 371
 372         writesize = fat_get_iosize(fat, entry->addr);
 373
 374         fat_addr = fat->fat32_offset + entry->addr;
 375         if (lseek(fd, fat_addr, SEEK_SET) != fat_addr ||
 376             (size_t)write(fd, entry->chunk, writesize) != writesize) {
 377                         pfatal("Unable to write FAT");
 378                         return (FSFATAL);
 379         }
 380
 381         entry->dirty = false;
 382         return (FSOK);
 383 }
 384
 385 static struct fat32_cache_entry *
 386 fat_get_fat32_cache_entry(struct fat_descriptor *fat, off_t addr,
 387     bool writing)
 388 {
 389         int fd;
 390         struct fat32_cache_entry *entry, *first;
 391         off_t   fat_addr;
 392         size_t  rwsize;
 393
 394         addr &= ~(fat32_cache_chunk_size - 1);
 395
 396         first = TAILQ_FIRST(&fat->fat32_cache_head);
 397
 398         /*
 399          * Cache hit: if we already have the chunk, move it to list head
 400          */
 401         TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) {
 402                 if (entry->addr == addr) {
 403                         if (writing) {
 404                                 entry->dirty = true;
 405                         }
 406                         if (entry != first) {
 407
 408                                 TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries);
 409                                 TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries);
 410                         }
 411                         return (entry);
 412                 }
 413         }
 414
 415         /*
 416          * Cache miss: detach the chunk at tail of list, overwrite with
 417          * the located chunk, and populate with data from disk.
 418          */
 419         entry = TAILQ_LAST(&fat->fat32_cache_head, cachehead);
 420         TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries);
 421         if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) {
 422                 return (NULL);
 423         }
 424
 425         rwsize = fat_get_iosize(fat, addr);
 426         fat_addr = fat->fat32_offset + addr;
 427         entry->addr = addr;
 428         fd = fd_of_(fat);
 429         if (lseek(fd, fat_addr, SEEK_SET) != fat_addr ||
 430                 (size_t)read(fd, entry->chunk, rwsize) != rwsize) {
 431                 pfatal("Unable to read FAT");
 432                 return (NULL);
 433         }
 434         if (writing) {
 435                 entry->dirty = true;
 436         }
 437         TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries);
 438
 439         return (entry);
 440 }
 441
 442 static inline uint8_t *
 443 fat_get_fat32_cached_ptr(struct fat_descriptor *fat, cl_t cl, bool writing)
 444 {
 445         off_t addr, off;
 446         struct fat32_cache_entry *entry;
 447
 448         addr = cl << 2;
 449         entry = fat_get_fat32_cache_entry(fat, addr, writing);
 450
 451         if (entry != NULL) {
 452                 off = addr & (fat32_cache_chunk_size - 1);
 453                 return (entry->chunk + off);
 454         } else {
 455                 return (NULL);
 456         }
 457 }
 458
 459
 460 static cl_t
 461 fat_get_fat32_cached_next(struct fat_descriptor *fat, cl_t cl)
 462 {
 463         const uint8_t   *p;
 464         cl_t    retval;
 465
 466         p = fat_get_fat32_cached_ptr(fat, cl, false);
 467         if (p != NULL) {
 468                 retval = le32dec(p) & CLUST32_MASK;
 469                 if (retval >= (CLUST_BAD & CLUST32_MASK))
 470                         retval |= ~CLUST32_MASK;
 471         } else {
 472                 retval = CLUST_DEAD;
 473         }
 474
 475         return (retval);
 476 }
 477
 478 static int
 479 fat_set_fat32_cached_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
 480 {
 481         uint8_t *p;
 482
 483         /* Truncate 'nextcl' value, if needed */
 484         nextcl &= CLUST32_MASK;
 485
 486         p = fat_get_fat32_cached_ptr(fat, cl, true);
 487         if (p != NULL) {
 488                 le32enc(p, (uint32_t)nextcl);
 489                 return FSOK;
 490         } else {
 491                 return FSFATAL;
 492         }
 493 }
 494
 495 cl_t fat_get_cl_next(struct fat_descriptor *fat, cl_t cl)
 496 {
 497
 498         if (!valid_cl(fat, cl)) {
 499                 pfatal("Invalid cluster: %ud", cl);
 500                 return CLUST_DEAD;
 501         }
 502
 503         return (fat->get(fat, cl));
 504 }
 505
 506 int fat_set_cl_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
 507 {
 508
 509         if (rdonly) {
 510                 pwarn(" (NO WRITE)\n");
 511                 return FSFATAL;
 512         }
 513
 514         if (!valid_cl(fat, cl)) {
 515                 pfatal("Invalid cluster: %ud", cl);
 516                 return FSFATAL;
 517         }
 518
 519         return (fat->set(fat, cl, nextcl));
 520 }
 521
 522 static inline struct bootblock*
 523 boot_of_(struct fat_descriptor *fat) {
 524
 525         return (fat->boot);
 526 }
 527
 528 struct bootblock*
 529 fat_get_boot(struct fat_descriptor *fat) {
 530
 531         return (boot_of_(fat));
 532 }
 533
 534 static inline int
 535 fd_of_(struct fat_descriptor *fat)
 536 {
 537         return (fat->fd);
 538 }
 539
 540 int
 541 fat_get_fd(struct fat_descriptor * fat)
 542 {
 543         return (fd_of_(fat));
 544 }
 545
 546 /*
 547  * Whether a cl is in valid data range.
 548  */
 549 bool
 550 fat_is_valid_cl(struct fat_descriptor *fat, cl_t cl)
 551 {
 552
 553         return (valid_cl(fat, cl));
 554 }
 555
 556 static inline bool
 557 valid_cl(struct fat_descriptor *fat, cl_t cl)
 558 {
 559         const struct bootblock *boot = boot_of_(fat);
 560
 561         return (cl >= CLUST_FIRST && cl < boot->NumClusters);
 562 }
 563
 564 /*
 565  * The first 2 FAT entries contain pseudo-cluster numbers with the following
 566  * layout:
 567  *
 568  * 31...... ........ ........ .......0
 569  * rrrr1111 11111111 11111111 mmmmmmmm         FAT32 entry 0
 570  * rrrrsh11 11111111 11111111 11111xxx         FAT32 entry 1
 571  *
 572  *                   11111111 mmmmmmmm         FAT16 entry 0
 573  *                   sh111111 11111xxx         FAT16 entry 1
 574  *
 575  * r = reserved
 576  * m = BPB media ID byte
 577  * s = clean flag (1 = dismounted; 0 = still mounted)
 578  * h = hard error flag (1 = ok; 0 = I/O error)
 579  * x = any value ok
 580  */
 581
 582 int
 583 checkdirty(int fs, struct bootblock *boot)
 584 {
 585         off_t off;
 586         u_char *buffer;
 587         int ret = 0;
 588         size_t len;
 589
 590         if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK)
 591                 return 0;
 592
 593         off = boot->bpbResSectors;
 594         off *= boot->bpbBytesPerSec;
 595
 596         buffer = malloc(len = boot->bpbBytesPerSec);
 597         if (buffer == NULL) {
 598                 perr("No space for FAT sectors (%zu)", len);
 599                 return 1;
 600         }
 601
 602         if (lseek(fs, off, SEEK_SET) != off) {
 603                 perr("Unable to read FAT");
 604                 goto err;
 605         }
 606
 607         if ((size_t)read(fs, buffer, boot->bpbBytesPerSec) !=
 608             boot->bpbBytesPerSec) {
 609                 perr("Unable to read FAT");
 610                 goto err;
 611         }
 612
 613         /*
 614          * If we don't understand the FAT, then the file system must be
 615          * assumed to be unclean.
 616          */
 617         if (buffer[0] != boot->bpbMedia || buffer[1] != 0xff)
 618                 goto err;
 619         if (boot->ClustMask == CLUST16_MASK) {
 620                 if ((buffer[2] & 0xf8) != 0xf8 || (buffer[3] & 0x3f) != 0x3f)
 621                         goto err;
 622         } else {
 623                 if (buffer[2] != 0xff || (buffer[3] & 0x0f) != 0x0f
 624                     || (buffer[4] & 0xf8) != 0xf8 || buffer[5] != 0xff
 625                     || buffer[6] != 0xff || (buffer[7] & 0x03) != 0x03)
 626                         goto err;
 627         }
 628
 629         /*
 630          * Now check the actual clean flag (and the no-error flag).
 631          */
 632         if (boot->ClustMask == CLUST16_MASK) {
 633                 if ((buffer[3] & 0xc0) == 0xc0)
 634                         ret = 1;
 635         } else {
 636                 if ((buffer[7] & 0x0c) == 0x0c)
 637                         ret = 1;
 638         }
 639
 640 err:
 641         free(buffer);
 642         return ret;
 643 }
 644
 645 /*
 646  * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
 647  */
 648 static int
 649 _readfat(struct fat_descriptor *fat)
 650 {
 651         int fd;
 652         size_t i;
 653         off_t off;
 654         size_t readsize;
 655         struct bootblock *boot;
 656         struct fat32_cache_entry *entry;
 657
 658         boot = boot_of_(fat);
 659         fd = fd_of_(fat);
 660         fat->fatsize = boot->FATsecs * boot->bpbBytesPerSec;
 661
 662         off = boot->bpbResSectors;
 663         off *= boot->bpbBytesPerSec;
 664
 665         fat->is_mmapped = false;
 666         fat->use_cache = false;
 667
 668         /* Attempt to mmap() first */
 669         if (allow_mmap) {
 670                 fat->fatbuf = mmap(NULL, fat->fatsize,
 671                                 PROT_READ | (rdonly ? 0 : PROT_WRITE),
 672                                 MAP_SHARED, fd_of_(fat), off);
 673                 if (fat->fatbuf != MAP_FAILED) {
 674                         fat->is_mmapped = true;
 675                         return 1;
 676                 }
 677         }
 678
 679         /*
 680          * Unfortunately, we were unable to mmap().
 681          *
 682          * Only use the cache manager when it's necessary, that is,
 683          * when the FAT is sufficiently large; in that case, only
 684          * read in the first 4 MiB of FAT into memory, and split the
 685          * buffer into chunks and insert to the LRU queue to populate
 686          * the cache with data.
 687          */
 688         if (boot->ClustMask == CLUST32_MASK &&
 689             fat->fatsize >= fat32_cache_size) {
 690                 readsize = fat32_cache_size;
 691                 fat->use_cache = true;
 692
 693                 fat->fat32_offset = boot->bpbResSectors * boot->bpbBytesPerSec;
 694                 fat->fat32_lastaddr = fat->fatsize & ~(fat32_cache_chunk_size);
 695         } else {
 696                 readsize = fat->fatsize;
 697         }
 698         fat->fatbuf = malloc(readsize);
 699         if (fat->fatbuf == NULL) {
 700                 perr("No space for FAT (%zu)", readsize);
 701                 return 0;
 702         }
 703
 704         if (lseek(fd, off, SEEK_SET) != off) {
 705                 perr("Unable to read FAT");
 706                 goto err;
 707         }
 708         if ((size_t)read(fd, fat->fatbuf, readsize) != readsize) {
 709                 perr("Unable to read FAT");
 710                 goto err;
 711         }
 712
 713         /*
 714          * When cache is used, split the buffer into chunks, and
 715          * connect the buffer into the cache.
 716          */
 717         if (fat->use_cache) {
 718                 TAILQ_INIT(&fat->fat32_cache_head);
 719                 entry = calloc(fat32_cache_entries, sizeof(*entry));
 720                 if (entry == NULL) {
 721                         perr("No space for FAT cache (%zu of %zu)",
 722                             fat32_cache_entries, sizeof(entry));
 723                         goto err;
 724                 }
 725                 for (i = 0; i < fat32_cache_entries; i++) {
 726                         entry[i].addr = fat32_cache_chunk_size * i;
 727                         entry[i].chunk = &fat->fatbuf[entry[i].addr];
 728                         TAILQ_INSERT_TAIL(&fat->fat32_cache_head,
 729                             &entry[i], entries);
 730                 }
 731                 fat->fat32_cache_allentries = entry;
 732         }
 733
 734         return 1;
 735
 736 err:
 737         free(fat->fatbuf);
 738         fat->fatbuf = NULL;
 739         return 0;
 740 }
 741
 742 static void
 743 releasefat(struct fat_descriptor *fat)
 744 {
 745         if (fat->is_mmapped) {
 746                 munmap(fat->fatbuf, fat->fatsize);
 747         } else {
 748                 if (fat->use_cache) {
 749                         free(fat->fat32_cache_allentries);
 750                         fat->fat32_cache_allentries = NULL;
 751                 }
 752                 free(fat->fatbuf);
 753         }
 754         fat->fatbuf = NULL;
 755         bitmap_dtor(&fat->headbitmap);
 756 }
 757
 758 /*
 759  * Read or map a FAT and populate head bitmap
 760  */
 761 int
 762 readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
 763 {
 764         struct fat_descriptor *fat;
 765         u_char *buffer, *p;
 766         cl_t cl, nextcl;
 767         int ret = FSOK;
 768
 769         boot->NumFree = boot->NumBad = 0;
 770
 771         fat = calloc(1, sizeof(struct fat_descriptor));
 772         if (fat == NULL) {
 773                 perr("No space for FAT descriptor");
 774                 return FSFATAL;
 775         }
 776
 777         fat->fd = fs;
 778         fat->boot = boot;
 779
 780         if (!_readfat(fat)) {
 781                 free(fat);
 782                 return FSFATAL;
 783         }
 784         buffer = fat->fatbuf;
 785
 786         /* Populate accessors */
 787         switch(boot->ClustMask) {
 788         case CLUST12_MASK:
 789                 fat->get = fat_get_fat12_next;
 790                 fat->set = fat_set_fat12_next;
 791                 break;
 792         case CLUST16_MASK:
 793                 fat->get = fat_get_fat16_next;
 794                 fat->set = fat_set_fat16_next;
 795                 break;
 796         case CLUST32_MASK:
 797                 if (fat->is_mmapped || !fat->use_cache) {
 798                         fat->get = fat_get_fat32_next;
 799                         fat->set = fat_set_fat32_next;
 800                 } else {
 801                         fat->get = fat_get_fat32_cached_next;
 802                         fat->set = fat_set_fat32_cached_next;
 803                 }
 804                 break;
 805         default:
 806                 pfatal("Invalid ClustMask: %d", boot->ClustMask);
 807                 releasefat(fat);
 808                 free(fat);
 809                 return FSFATAL;
 810         }
 811
 812         if (bitmap_ctor(&fat->headbitmap, boot->NumClusters,
 813             true) != FSOK) {
 814                 perr("No space for head bitmap for FAT clusters (%zu)",
 815                     (size_t)boot->NumClusters);
 816                 releasefat(fat);
 817                 free(fat);
 818                 return FSFATAL;
 819         }
 820
 821         if (buffer[0] != boot->bpbMedia
 822             || buffer[1] != 0xff || buffer[2] != 0xff
 823             || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
 824             || (boot->ClustMask == CLUST32_MASK
 825                 && ((buffer[3]&0x0f) != 0x0f
 826                     || buffer[4] != 0xff || buffer[5] != 0xff
 827                     || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
 828
 829                 /* Windows 95 OSR2 (and possibly any later) changes
 830                  * the FAT signature to 0xXXffff7f for FAT16 and to
 831                  * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
 832                  * file system is dirty if it doesn't reboot cleanly.
 833                  * Check this special condition before errorring out.
 834                  */
 835                 if (buffer[0] == boot->bpbMedia && buffer[1] == 0xff
 836                     && buffer[2] == 0xff
 837                     && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
 838                         || (boot->ClustMask == CLUST32_MASK
 839                             && buffer[3] == 0x0f && buffer[4] == 0xff
 840                             && buffer[5] == 0xff && buffer[6] == 0xff
 841                             && buffer[7] == 0x07)))
 842                         ret |= FSDIRTY;
 843                 else {
 844                         /* just some odd byte sequence in FAT */
 845
 846                         switch (boot->ClustMask) {
 847                         case CLUST32_MASK:
 848                                 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
 849                                       "FAT starts with odd byte sequence",
 850                                       buffer[0], buffer[1], buffer[2], buffer[3],
 851                                       buffer[4], buffer[5], buffer[6], buffer[7]);
 852                                 break;
 853                         case CLUST16_MASK:
 854                                 pwarn("%s (%02x%02x%02x%02x)\n",
 855                                     "FAT starts with odd byte sequence",
 856                                     buffer[0], buffer[1], buffer[2], buffer[3]);
 857                                 break;
 858                         default:
 859                                 pwarn("%s (%02x%02x%02x)\n",
 860                                     "FAT starts with odd byte sequence",
 861                                     buffer[0], buffer[1], buffer[2]);
 862                                 break;
 863                         }
 864
 865                         if (ask(1, "Correct")) {
 866                                 ret |= FSFATMOD;
 867                                 p = buffer;
 868
 869                                 *p++ = (u_char)boot->bpbMedia;
 870                                 *p++ = 0xff;
 871                                 *p++ = 0xff;
 872                                 switch (boot->ClustMask) {
 873                                 case CLUST16_MASK:
 874                                         *p++ = 0xff;
 875                                         break;
 876                                 case CLUST32_MASK:
 877                                         *p++ = 0x0f;
 878                                         *p++ = 0xff;
 879                                         *p++ = 0xff;
 880                                         *p++ = 0xff;
 881                                         *p++ = 0x0f;
 882                                         break;
 883                                 default:
 884                                         break;
 885                                 }
 886                         }
 887                 }
 888         }
 889
 890         /*
 891          * Traverse the FAT table and populate head map.  Initially, we
 892          * consider all clusters as possible head cluster (beginning of
 893          * a file or directory), and traverse the whole allocation table
 894          * by marking every non-head nodes as such (detailed below) and
 895          * fix obvious issues while we walk.
 896          *
 897          * For each "next" cluster, the possible values are:
 898          *
 899          * a) CLUST_FREE or CLUST_BAD.  The *current* cluster can't be a
 900          *    head node.
 901          * b) An out-of-range value. The only fix would be to truncate at
 902          *    the cluster.
 903          * c) A valid cluster.  It means that cluster (nextcl) is not a
 904          *    head cluster.  Note that during the scan, every cluster is
 905          *    expected to be seen for at most once, and when we saw them
 906          *    twice, it means a cross-linked chain which should be
 907          *    truncated at the current cluster.
 908          *
 909          * After scan, the remaining set bits indicates all possible
 910          * head nodes, because they were never claimed by any other
 911          * node as the next node, but we do not know if these chains
 912          * would end with a valid EOF marker.  We will check that in
 913          * checkchain() at a later time when checking directories,
 914          * where these head nodes would be marked as non-head.
 915          *
 916          * In the final pass, all head nodes should be cleared, and if
 917          * there is still head nodes, these would be leaders of lost
 918          * chain.
 919          */
 920         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
 921                 nextcl = fat_get_cl_next(fat, cl);
 922
 923                 /* Check if the next cluster number is valid */
 924                 if (nextcl == CLUST_FREE) {
 925                         /* Save a hint for next free cluster */
 926                         if (boot->FSNext == 0) {
 927                                 boot->FSNext = cl;
 928                         }
 929                         if (fat_is_cl_head(fat, cl)) {
 930                                 fat_clear_cl_head(fat, cl);
 931                         }
 932                         boot->NumFree++;
 933                 } else if (nextcl == CLUST_BAD) {
 934                         if (fat_is_cl_head(fat, cl)) {
 935                                 fat_clear_cl_head(fat, cl);
 936                         }
 937                         boot->NumBad++;
 938                 } else if (!valid_cl(fat, nextcl) && nextcl < CLUST_RSRVD) {
 939                         pwarn("Cluster %u continues with out of range "
 940                             "cluster number %u\n",
 941                             cl,
 942                             nextcl & boot->ClustMask);
 943                         if (ask(0, "Truncate")) {
 944                                 ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
 945                                 ret |= FSFATMOD;
 946                         }
 947                 } else if (valid_cl(fat, nextcl)) {
 948                         if (fat_is_cl_head(fat, nextcl)) {
 949                                 fat_clear_cl_head(fat, nextcl);
 950                         } else {
 951                                 pwarn("Cluster %u crossed another chain at %u\n",
 952                                     cl, nextcl);
 953                                 if (ask(0, "Truncate")) {
 954                                         ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
 955                                         ret |= FSFATMOD;
 956                                 }
 957                         }
 958                 }
 959
 960         }
 961
 962         if (ret & FSFATAL) {
 963                 releasefat(fat);
 964                 free(fat);
 965                 *fp = NULL;
 966         } else
 967                 *fp = fat;
 968         return ret;
 969 }
 970
 971 /*
 972  * Get type of reserved cluster
 973  */
 974 const char *
 975 rsrvdcltype(cl_t cl)
 976 {
 977         if (cl == CLUST_FREE)
 978                 return "free";
 979         if (cl < CLUST_BAD)
 980                 return "reserved";
 981         if (cl > CLUST_BAD)
 982                 return "as EOF";
 983         return "bad";
 984 }
 985
 986 /*
 987  * Examine a cluster chain for errors and count its size.
 988  */
 989 int
 990 checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
 991 {
 992         cl_t prev_cl, current_cl, next_cl;
 993         const char *op;
 994
 995         /*
 996          * We expect that the caller to give us a real, unvisited 'head'
 997          * cluster, and it must be a valid cluster.  While scanning the
 998          * FAT table, we already excluded all clusters that was claimed
 999          * as a "next" cluster.  Assert all the three conditions.
1000          */
1001         assert(valid_cl(fat, head));
1002         assert(fat_is_cl_head(fat, head));
1003
1004         /*
1005          * Immediately mark the 'head' cluster that we are about to visit.
1006          */
1007         fat_clear_cl_head(fat, head);
1008
1009         /*
1010          * The allocation of a non-zero sized file or directory is
1011          * represented as a singly linked list, and the tail node
1012          * would be the EOF marker (>=CLUST_EOFS).
1013          *
1014          * With a valid head node at hand, we expect all subsequent
1015          * cluster to be either a not yet seen and valid cluster (we
1016          * would continue counting), or the EOF marker (we conclude
1017          * the scan of this chain).
1018          *
1019          * For all other cases, the chain is invalid, and the only
1020          * viable fix would be to truncate at the current node (mark
1021          * it as EOF) when the next node violates that.
1022          */
1023         *chainsize = 0;
1024         prev_cl = current_cl = head;
1025         for (next_cl = fat_get_cl_next(fat, current_cl);
1026             valid_cl(fat, next_cl);
1027             prev_cl = current_cl, current_cl = next_cl, next_cl = fat_get_cl_next(fat, current_cl))
1028                 (*chainsize)++;
1029
1030         /* A natural end */
1031         if (next_cl >= CLUST_EOFS) {
1032                 (*chainsize)++;
1033                 return FSOK;
1034         }
1035
1036         /*
1037          * The chain ended with an out-of-range cluster number.
1038          *
1039          * If the current node is e.g. CLUST_FREE, CLUST_BAD, etc.,
1040          * it should not be present in a chain and we has to truncate
1041          * at the previous node.
1042          *
1043          * If the current cluster points to an invalid cluster, the
1044          * current cluster might have useful data and we truncate at
1045          * the current cluster instead.
1046          */
1047         if (next_cl == CLUST_FREE || next_cl >= CLUST_RSRVD) {
1048                 pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
1049                     head, rsrvdcltype(next_cl));
1050                 current_cl = prev_cl;
1051         } else {
1052                 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
1053                     head,
1054                     next_cl & boot_of_(fat)->ClustMask);
1055                 (*chainsize)++;
1056         }
1057
1058         if (*chainsize > 0) {
1059                 op = "Truncate";
1060                 next_cl = CLUST_EOF;
1061         } else {
1062                 op = "Clear";
1063                 next_cl = CLUST_FREE;
1064         }
1065         if (ask(0, "%s", op)) {
1066                 return (fat_set_cl_next(fat, current_cl, next_cl) | FSFATMOD);
1067         } else {
1068                 return (FSERROR);
1069         }
1070 }
1071
1072 /*
1073  * Clear cluster chain from head.
1074  */
1075 void
1076 clearchain(struct fat_descriptor *fat, cl_t head)
1077 {
1078         cl_t current_cl, next_cl;
1079         struct bootblock *boot = boot_of_(fat);
1080
1081         current_cl = head;
1082
1083         while (valid_cl(fat, current_cl)) {
1084                 next_cl = fat_get_cl_next(fat, current_cl);
1085                 (void)fat_set_cl_next(fat, current_cl, CLUST_FREE);
1086                 boot->NumFree++;
1087                 current_cl = next_cl;
1088         }
1089
1090 }
1091
1092 /*
1093  * Overwrite the n-th FAT with FAT0
1094  */
1095 static int
1096 copyfat(struct fat_descriptor *fat, int n)
1097 {
1098         size_t  rwsize, tailsize, blobs, i;
1099         off_t   dst_off, src_off;
1100         struct bootblock *boot;
1101         int ret, fd;
1102
1103         ret = FSOK;
1104         fd = fd_of_(fat);
1105         boot = boot_of_(fat);
1106
1107         blobs = howmany(fat->fatsize, fat32_cache_size);
1108         tailsize = fat->fatsize % fat32_cache_size;
1109         if (tailsize == 0) {
1110                 tailsize = fat32_cache_size;
1111         }
1112         rwsize = fat32_cache_size;
1113
1114         src_off = fat->fat32_offset;
1115         dst_off = boot->bpbResSectors + n * boot->FATsecs;
1116         dst_off *= boot->bpbBytesPerSec;
1117
1118         for (i = 0; i < blobs;
1119             i++, src_off += fat32_cache_size, dst_off += fat32_cache_size) {
1120                 if (i == blobs - 1) {
1121                         rwsize = tailsize;
1122                 }
1123                 if ((lseek(fd, src_off, SEEK_SET) != src_off ||
1124                     (size_t)read(fd, fat->fatbuf, rwsize) != rwsize) &&
1125                     ret == FSOK) {
1126                         perr("Unable to read FAT0");
1127                         ret = FSFATAL;
1128                         continue;
1129                 }
1130                 if ((lseek(fd, dst_off, SEEK_SET) != dst_off ||
1131                         (size_t)write(fd, fat->fatbuf, rwsize) != rwsize) &&
1132                         ret == FSOK) {
1133                         perr("Unable to write FAT %d", n);
1134                         ret = FSERROR;
1135                 }
1136         }
1137         return (ret);
1138 }
1139
1140 /*
1141  * Write out FAT
1142  */
1143 int
1144 writefat(struct fat_descriptor *fat)
1145 {
1146         u_int i;
1147         size_t writesz;
1148         off_t dst_base;
1149         int ret = FSOK, fd;
1150         struct bootblock *boot;
1151         struct fat32_cache_entry *entry;
1152
1153         boot = boot_of_(fat);
1154         fd = fd_of_(fat);
1155
1156         if (fat->use_cache) {
1157                 /*
1158                  * Attempt to flush all in-flight cache, and bail out
1159                  * if we encountered an error (but only emit error
1160                  * message once).  Stop proceeding with copyfat()
1161                  * if any flush failed.
1162                  */
1163                 TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) {
1164                         if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) {
1165                                 if (ret == FSOK) {
1166                                         perr("Unable to write FAT");
1167                                         ret = FSFATAL;
1168                                 }
1169                         }
1170                 }
1171                 if (ret != FSOK)
1172                         return (ret);
1173
1174                 /* Update backup copies of FAT, error is not fatal */
1175                 for (i = 1; i < boot->bpbFATs; i++) {
1176                         if (copyfat(fat, i) != FSOK)
1177                                 ret = FSERROR;
1178                 }
1179         } else {
1180                 writesz = fat->fatsize;
1181
1182                 for (i = fat->is_mmapped ? 1 : 0; i < boot->bpbFATs; i++) {
1183                         dst_base = boot->bpbResSectors + i * boot->FATsecs;
1184                         dst_base *= boot->bpbBytesPerSec;
1185                         if ((lseek(fd, dst_base, SEEK_SET) != dst_base ||
1186                             (size_t)write(fd, fat->fatbuf, writesz) != writesz) &&
1187                             ret == FSOK) {
1188                                 perr("Unable to write FAT %d", i);
1189                                 ret = ((i == 0) ? FSFATAL : FSERROR);
1190                         }
1191                 }
1192         }
1193
1194         return ret;
1195 }
1196
1197 /*
1198  * Check a complete in-memory FAT for lost cluster chains
1199  */
1200 int
1201 checklost(struct fat_descriptor *fat)
1202 {
1203         cl_t head;
1204         int mod = FSOK;
1205         int dosfs, ret;
1206         size_t chains, chainlength;
1207         struct bootblock *boot;
1208
1209         dosfs = fd_of_(fat);
1210         boot = boot_of_(fat);
1211
1212         /*
1213          * At this point, we have already traversed all directories.
1214          * All remaining chain heads in the bitmap are heads of lost
1215          * chains.
1216          */
1217         chains = fat_get_head_count(fat);
1218         for (head = CLUST_FIRST;
1219             chains > 0 && head < boot->NumClusters;
1220             ) {
1221                 /*
1222                  * We expect the bitmap to be very sparse, so skip if
1223                  * the range is full of 0's
1224                  */
1225                 if (head % LONG_BIT == 0 &&
1226                     !fat_is_cl_head_in_range(fat, head)) {
1227                         head += LONG_BIT;
1228                         continue;
1229                 }
1230                 if (fat_is_cl_head(fat, head)) {
1231                         ret = checkchain(fat, head, &chainlength);
1232                         if (ret != FSERROR && chainlength > 0) {
1233                                 pwarn("Lost cluster chain at cluster %u\n"
1234                                     "%zd Cluster(s) lost\n",
1235                                     head, chainlength);
1236                                 mod |= ret = reconnect(fat, head,
1237                                     chainlength);
1238                         }
1239                         if (mod & FSFATAL)
1240                                 break;
1241                         if (ret == FSERROR && ask(0, "Clear")) {
1242                                 clearchain(fat, head);
1243                                 mod |= FSFATMOD;
1244                         }
1245                         chains--;
1246                 }
1247                 head++;
1248         }
1249
1250         finishlf();
1251
1252         if (boot->bpbFSInfo) {
1253                 ret = 0;
1254                 if (boot->FSFree != 0xffffffffU &&
1255                     boot->FSFree != boot->NumFree) {
1256                         pwarn("Free space in FSInfo block (%u) not correct (%u)\n",
1257                               boot->FSFree, boot->NumFree);
1258                         if (ask(1, "Fix")) {
1259                                 boot->FSFree = boot->NumFree;
1260                                 ret = 1;
1261                         }
1262                 }
1263                 if (boot->FSNext != 0xffffffffU &&
1264                     (boot->FSNext >= boot->NumClusters ||
1265                     (boot->NumFree && fat_get_cl_next(fat, boot->FSNext) != CLUST_FREE))) {
1266                         pwarn("Next free cluster in FSInfo block (%u) %s\n",
1267                               boot->FSNext,
1268                               (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
1269                         if (ask(1, "Fix"))
1270                                 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
1271                                         if (fat_get_cl_next(fat, head) == CLUST_FREE) {
1272                                                 boot->FSNext = head;
1273                                                 ret = 1;
1274                                                 break;
1275                                         }
1276                 }
1277                 if (ret)
1278                         mod |= writefsinfo(dosfs, boot);
1279         }
1280
1281         return mod;
1282 }