diff options
Diffstat (limited to 'sbin/fsck_msdosfs/fat.c')
| -rw-r--r-- | sbin/fsck_msdosfs/fat.c | 1351 |
1 files changed, 948 insertions, 403 deletions
diff --git a/sbin/fsck_msdosfs/fat.c b/sbin/fsck_msdosfs/fat.c index 7ca81ab115ef..12050c2591d4 100644 --- a/sbin/fsck_msdosfs/fat.c +++ b/sbin/fsck_msdosfs/fat.c @@ -1,6 +1,7 @@ /*- * SPDX-License-Identifier: BSD-2-Clause * + * Copyright (c) 2019 Google LLC * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank * Copyright (c) 1995 Martin Husemann * @@ -33,6 +34,14 @@ static const char rcsid[] = "$FreeBSD$"; #endif /* not lint */ +#include <sys/endian.h> +#include <sys/queue.h> +#include <sys/limits.h> +#include <sys/mman.h> +#include <sys/param.h> + +#include <assert.h> +#include <stdbool.h> #include <stdlib.h> #include <string.h> #include <ctype.h> @@ -42,12 +51,517 @@ static const char rcsid[] = #include "ext.h" #include "fsutil.h" -static int checkclnum(struct bootblock *, u_int, cl_t, cl_t *); -static int clustdiffer(cl_t, cl_t *, cl_t *, u_int); -static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *); -static int _readfat(int, struct bootblock *, u_int, u_char **); +static int _readfat(struct fat_descriptor *); +static inline struct bootblock* boot_of_(struct fat_descriptor *); +static inline int fd_of_(struct fat_descriptor *); +static inline bool valid_cl(struct fat_descriptor *, cl_t); -/*- + +/* + * Head bitmap for FAT scanning. + * + * FAT32 have up to 2^28 = 256M entries, and FAT16/12 have much less. + * For each cluster, we use 1 bit to represent if it's a head cluster + * (the first cluster of a cluster chain). + * + * Head bitmap + * =========== + * Initially, we set all bits to 1. In readfat(), we traverse the + * whole FAT and mark each cluster identified as "next" cluster as + * 0. After the scan, we have a bitmap with 1's to indicate the + * corresponding cluster was a "head" cluster. + * + * We use head bitmap to identify lost chains: a head cluster that was + * not being claimed by any file or directories is the head cluster of + * a lost chain. + * + * Handle of lost chains + * ===================== + * At the end of scanning, we can easily find all lost chain's heads + * by finding out the 1's in the head bitmap. + */ + +typedef struct long_bitmap { + unsigned long *map; + size_t count; /* Total set bits in the map */ +} long_bitmap_t; + +static inline void +bitmap_clear(long_bitmap_t *lbp, cl_t cl) +{ + cl_t i = cl / LONG_BIT; + unsigned long clearmask = ~(1UL << (cl % LONG_BIT)); + + assert((lbp->map[i] & ~clearmask) != 0); + lbp->map[i] &= clearmask; + lbp->count--; +} + +static inline bool +bitmap_get(long_bitmap_t *lbp, cl_t cl) +{ + cl_t i = cl / LONG_BIT; + unsigned long usedbit = 1UL << (cl % LONG_BIT); + + return ((lbp->map[i] & usedbit) == usedbit); +} + +static inline bool +bitmap_none_in_range(long_bitmap_t *lbp, cl_t cl) +{ + cl_t i = cl / LONG_BIT; + + return (lbp->map[i] == 0); +} + +static inline size_t +bitmap_count(long_bitmap_t *lbp) +{ + return (lbp->count); +} + +static int +bitmap_ctor(long_bitmap_t *lbp, size_t bits, bool allone) +{ + size_t bitmap_size = roundup2(bits, LONG_BIT) / (LONG_BIT / 8); + + free(lbp->map); + lbp->map = calloc(1, bitmap_size); + if (lbp->map == NULL) + return FSFATAL; + + if (allone) { + memset(lbp->map, 0xff, bitmap_size); + lbp->count = bits; + } else { + lbp->count = 0; + } + return FSOK; +} + +static void +bitmap_dtor(long_bitmap_t *lbp) +{ + free(lbp->map); + lbp->map = NULL; +} + +/* + * FAT32 can be as big as 256MiB (2^26 entries * 4 bytes), when we + * can not ask the kernel to manage the access, use a simple LRU + * cache with chunk size of 128 KiB to manage it. + */ +struct fat32_cache_entry { + TAILQ_ENTRY(fat32_cache_entry) entries; + uint8_t *chunk; /* pointer to chunk */ + off_t addr; /* offset */ + bool dirty; /* dirty bit */ +}; + +static const size_t fat32_cache_chunk_size = 131072; /* MAXPHYS */ +static const size_t fat32_cache_size = 4194304; +static const size_t fat32_cache_entries = 32; /* XXXgcc: cache_size / cache_chunk_size */ + +/* + * FAT table descriptor, represents a FAT table that is already loaded + * into memory. + */ +struct fat_descriptor { + struct bootblock *boot; + uint8_t *fatbuf; + cl_t (*get)(struct fat_descriptor *, cl_t); + int (*set)(struct fat_descriptor *, cl_t, cl_t); + long_bitmap_t headbitmap; + int fd; + bool is_mmapped; + bool use_cache; + size_t fatsize; + + size_t fat32_cached_chunks; + TAILQ_HEAD(cachehead, fat32_cache_entry) fat32_cache_head; + struct fat32_cache_entry *fat32_cache_allentries; + off_t fat32_offset; + off_t fat32_lastaddr; +}; + +void +fat_clear_cl_head(struct fat_descriptor *fat, cl_t cl) +{ + bitmap_clear(&fat->headbitmap, cl); +} + +bool +fat_is_cl_head(struct fat_descriptor *fat, cl_t cl) +{ + return (bitmap_get(&fat->headbitmap, cl)); +} + +static inline bool +fat_is_cl_head_in_range(struct fat_descriptor *fat, cl_t cl) +{ + return (!(bitmap_none_in_range(&fat->headbitmap, cl))); +} + +static size_t +fat_get_head_count(struct fat_descriptor *fat) +{ + return (bitmap_count(&fat->headbitmap)); +} + +/* + * FAT12 accessors. + * + * FAT12s are sufficiently small, expect it to always fit in the RAM. + */ +static inline uint8_t * +fat_get_fat12_ptr(struct fat_descriptor *fat, cl_t cl) +{ + return (fat->fatbuf + ((cl + (cl >> 1)))); +} + +static cl_t +fat_get_fat12_next(struct fat_descriptor *fat, cl_t cl) +{ + const uint8_t *p; + cl_t retval; + + p = fat_get_fat12_ptr(fat, cl); + retval = le16dec(p); + /* Odd cluster: lower 4 bits belongs to the subsequent cluster */ + if ((cl & 1) == 1) + retval >>= 4; + retval &= CLUST12_MASK; + + if (retval >= (CLUST_BAD & CLUST12_MASK)) + retval |= ~CLUST12_MASK; + + return (retval); +} + +static int +fat_set_fat12_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl) +{ + uint8_t *p; + + /* Truncate 'nextcl' value, if needed */ + nextcl &= CLUST12_MASK; + + p = fat_get_fat12_ptr(fat, cl); + + /* + * Read in the 4 bits from the subsequent (for even clusters) + * or the preceding (for odd clusters) cluster and combine + * it to the nextcl value for encoding + */ + if ((cl & 1) == 0) { + nextcl |= ((p[1] & 0xf0) << 8); + } else { + nextcl <<= 4; + nextcl |= (p[0] & 0x0f); + } + + le16enc(p, (uint16_t)nextcl); + + return (0); +} + +/* + * FAT16 accessors. + * + * FAT16s are sufficiently small, expect it to always fit in the RAM. + */ +static inline uint8_t * +fat_get_fat16_ptr(struct fat_descriptor *fat, cl_t cl) +{ + return (fat->fatbuf + (cl << 1)); +} + +static cl_t +fat_get_fat16_next(struct fat_descriptor *fat, cl_t cl) +{ + const uint8_t *p; + cl_t retval; + + p = fat_get_fat16_ptr(fat, cl); + retval = le16dec(p) & CLUST16_MASK; + + if (retval >= (CLUST_BAD & CLUST16_MASK)) + retval |= ~CLUST16_MASK; + + return (retval); +} + +static int +fat_set_fat16_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl) +{ + uint8_t *p; + + /* Truncate 'nextcl' value, if needed */ + nextcl &= CLUST16_MASK; + + p = fat_get_fat16_ptr(fat, cl); + + le16enc(p, (uint16_t)nextcl); + + return (0); +} + +/* + * FAT32 accessors. + */ +static inline uint8_t * +fat_get_fat32_ptr(struct fat_descriptor *fat, cl_t cl) +{ + return (fat->fatbuf + (cl << 2)); +} + +static cl_t +fat_get_fat32_next(struct fat_descriptor *fat, cl_t cl) +{ + const uint8_t *p; + cl_t retval; + + p = fat_get_fat32_ptr(fat, cl); + retval = le32dec(p) & CLUST32_MASK; + + if (retval >= (CLUST_BAD & CLUST32_MASK)) + retval |= ~CLUST32_MASK; + + return (retval); +} + +static int +fat_set_fat32_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl) +{ + uint8_t *p; + + /* Truncate 'nextcl' value, if needed */ + nextcl &= CLUST32_MASK; + + p = fat_get_fat32_ptr(fat, cl); + + le32enc(p, (uint32_t)nextcl); + + return (0); +} + +static inline size_t +fat_get_iosize(struct fat_descriptor *fat, off_t address) +{ + + if (address == fat->fat32_lastaddr) { + return (fat->fatsize & ((off_t)fat32_cache_chunk_size - 1)); + } else { + return (fat32_cache_chunk_size); + } +} + +static int +fat_flush_fat32_cache_entry(struct fat_descriptor *fat, + struct fat32_cache_entry *entry) +{ + int fd; + off_t fat_addr; + size_t writesize; + + fd = fd_of_(fat); + + if (!entry->dirty) + return (FSOK); + + writesize = fat_get_iosize(fat, entry->addr); + + fat_addr = fat->fat32_offset + entry->addr; + if (lseek(fd, fat_addr, SEEK_SET) != fat_addr || + (size_t)write(fd, entry->chunk, writesize) != writesize) { + pfatal("Unable to write FAT"); + return (FSFATAL); + } + + entry->dirty = false; + return (FSOK); +} + +static struct fat32_cache_entry * +fat_get_fat32_cache_entry(struct fat_descriptor *fat, off_t addr, + bool writing) +{ + int fd; + struct fat32_cache_entry *entry, *first; + off_t fat_addr; + size_t rwsize; + + addr &= ~(fat32_cache_chunk_size - 1); + + first = TAILQ_FIRST(&fat->fat32_cache_head); + + /* + * Cache hit: if we already have the chunk, move it to list head + */ + TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) { + if (entry->addr == addr) { + if (writing) { + entry->dirty = true; + } + if (entry != first) { + + TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries); + TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries); + } + return (entry); + } + } + + /* + * Cache miss: detach the chunk at tail of list, overwrite with + * the located chunk, and populate with data from disk. + */ + entry = TAILQ_LAST(&fat->fat32_cache_head, cachehead); + TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries); + if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) { + return (NULL); + } + + rwsize = fat_get_iosize(fat, addr); + fat_addr = fat->fat32_offset + addr; + entry->addr = addr; + fd = fd_of_(fat); + if (lseek(fd, fat_addr, SEEK_SET) != fat_addr || + (size_t)read(fd, entry->chunk, rwsize) != rwsize) { + pfatal("Unable to read FAT"); + return (NULL); + } + if (writing) { + entry->dirty = true; + } + TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries); + + return (entry); +} + +static inline uint8_t * +fat_get_fat32_cached_ptr(struct fat_descriptor *fat, cl_t cl, bool writing) +{ + off_t addr, off; + struct fat32_cache_entry *entry; + + addr = cl << 2; + entry = fat_get_fat32_cache_entry(fat, addr, writing); + + if (entry != NULL) { + off = addr & (fat32_cache_chunk_size - 1); + return (entry->chunk + off); + } else { + return (NULL); + } +} + + +static cl_t +fat_get_fat32_cached_next(struct fat_descriptor *fat, cl_t cl) +{ + const uint8_t *p; + cl_t retval; + + p = fat_get_fat32_cached_ptr(fat, cl, false); + if (p != NULL) { + retval = le32dec(p) & CLUST32_MASK; + if (retval >= (CLUST_BAD & CLUST32_MASK)) + retval |= ~CLUST32_MASK; + } else { + retval = CLUST_DEAD; + } + + return (retval); +} + +static int +fat_set_fat32_cached_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl) +{ + uint8_t *p; + + /* Truncate 'nextcl' value, if needed */ + nextcl &= CLUST32_MASK; + + p = fat_get_fat32_cached_ptr(fat, cl, true); + if (p != NULL) { + le32enc(p, (uint32_t)nextcl); + return FSOK; + } else { + return FSFATAL; + } +} + +cl_t fat_get_cl_next(struct fat_descriptor *fat, cl_t cl) +{ + + if (!valid_cl(fat, cl)) { + pfatal("Invalid cluster: %ud", cl); + return CLUST_DEAD; + } + + return (fat->get(fat, cl)); +} + +int fat_set_cl_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl) +{ + + if (rdonly) { + pwarn(" (NO WRITE)\n"); + return FSFATAL; + } + + if (!valid_cl(fat, cl)) { + pfatal("Invalid cluster: %ud", cl); + return FSFATAL; + } + + return (fat->set(fat, cl, nextcl)); +} + +static inline struct bootblock* +boot_of_(struct fat_descriptor *fat) { + + return (fat->boot); +} + +struct bootblock* +fat_get_boot(struct fat_descriptor *fat) { + + return (boot_of_(fat)); +} + +static inline int +fd_of_(struct fat_descriptor *fat) +{ + return (fat->fd); +} + +int +fat_get_fd(struct fat_descriptor * fat) +{ + return (fd_of_(fat)); +} + +/* + * Whether a cl is in valid data range. + */ +bool +fat_is_valid_cl(struct fat_descriptor *fat, cl_t cl) +{ + + return (valid_cl(fat, cl)); +} + +static inline bool +valid_cl(struct fat_descriptor *fat, cl_t cl) +{ + const struct bootblock *boot = boot_of_(fat); + + return (cl >= CLUST_FIRST && cl < boot->NumClusters); +} + +/* * The first 2 FAT entries contain pseudo-cluster numbers with the following * layout: * @@ -129,93 +643,178 @@ err: } /* - * Check a cluster number for valid value + * Read a FAT from disk. Returns 1 if successful, 0 otherwise. */ static int -checkclnum(struct bootblock *boot, u_int fat, cl_t cl, cl_t *next) +_readfat(struct fat_descriptor *fat) { - if (*next >= (CLUST_RSRVD&boot->ClustMask)) - *next |= ~boot->ClustMask; - if (*next == CLUST_FREE) { - boot->NumFree++; - return FSOK; - } - if (*next == CLUST_BAD) { - boot->NumBad++; - return FSOK; - } - if (*next < CLUST_FIRST - || (*next >= boot->NumClusters && *next < CLUST_EOFS)) { - pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n", - cl, fat, - *next < CLUST_RSRVD ? "out of range" : "reserved", - *next&boot->ClustMask); - if (ask(0, "Truncate")) { - *next = CLUST_EOF; - return FSFATMOD; + int fd; + size_t i; + off_t off; + size_t readsize; + struct bootblock *boot; + struct fat32_cache_entry *entry; + + boot = boot_of_(fat); + fd = fd_of_(fat); + fat->fatsize = boot->FATsecs * boot->bpbBytesPerSec; + + off = boot->bpbResSectors; + off *= boot->bpbBytesPerSec; + + fat->is_mmapped = false; + fat->use_cache = false; + + /* Attempt to mmap() first */ + if (allow_mmap) { + fat->fatbuf = mmap(NULL, fat->fatsize, + PROT_READ | (rdonly ? 0 : PROT_WRITE), + MAP_SHARED, fd_of_(fat), off); + if (fat->fatbuf != MAP_FAILED) { + fat->is_mmapped = true; + return 1; } - return FSERROR; } - return FSOK; -} -/* - * Read a FAT from disk. Returns 1 if successful, 0 otherwise. - */ -static int -_readfat(int fs, struct bootblock *boot, u_int no, u_char **buffer) -{ - off_t off; + /* + * Unfortunately, we were unable to mmap(). + * + * Only use the cache manager when it's necessary, that is, + * when the FAT is sufficiently large; in that case, only + * read in the first 4 MiB of FAT into memory, and split the + * buffer into chunks and insert to the LRU queue to populate + * the cache with data. + */ + if (boot->ClustMask == CLUST32_MASK && + fat->fatsize >= fat32_cache_size) { + readsize = fat32_cache_size; + fat->use_cache = true; - *buffer = calloc(boot->FATsecs, boot->bpbBytesPerSec); - if (*buffer == NULL) { - perr("No space for FAT sectors (%zu)", - (size_t)boot->FATsecs); + fat->fat32_offset = boot->bpbResSectors * boot->bpbBytesPerSec; + fat->fat32_lastaddr = fat->fatsize & ~(fat32_cache_chunk_size); + } else { + readsize = fat->fatsize; + } + fat->fatbuf = malloc(readsize); + if (fat->fatbuf == NULL) { + perr("No space for FAT (%zu)", readsize); return 0; } - off = boot->bpbResSectors + no * boot->FATsecs; - off *= boot->bpbBytesPerSec; - - if (lseek(fs, off, SEEK_SET) != off) { + if (lseek(fd, off, SEEK_SET) != off) { perr("Unable to read FAT"); goto err; } - - if ((size_t)read(fs, *buffer, boot->FATsecs * boot->bpbBytesPerSec) - != boot->FATsecs * boot->bpbBytesPerSec) { + if ((size_t)read(fd, fat->fatbuf, readsize) != readsize) { perr("Unable to read FAT"); goto err; } + /* + * When cache is used, split the buffer into chunks, and + * connect the buffer into the cache. + */ + if (fat->use_cache) { + TAILQ_INIT(&fat->fat32_cache_head); + entry = calloc(fat32_cache_entries, sizeof(*entry)); + if (entry == NULL) { + perr("No space for FAT cache (%zu of %zu)", + fat32_cache_entries, sizeof(entry)); + goto err; + } + for (i = 0; i < fat32_cache_entries; i++) { + entry[i].addr = fat32_cache_chunk_size * i; + entry[i].chunk = &fat->fatbuf[entry[i].addr]; + TAILQ_INSERT_TAIL(&fat->fat32_cache_head, + &entry[i], entries); + } + fat->fat32_cache_allentries = entry; + } + return 1; - err: - free(*buffer); +err: + free(fat->fatbuf); + fat->fatbuf = NULL; return 0; } +static void +releasefat(struct fat_descriptor *fat) +{ + if (fat->is_mmapped) { + munmap(fat->fatbuf, fat->fatsize); + } else { + if (fat->use_cache) { + free(fat->fat32_cache_allentries); + fat->fat32_cache_allentries = NULL; + } + free(fat->fatbuf); + } + fat->fatbuf = NULL; + bitmap_dtor(&fat->headbitmap); +} + /* - * Read a FAT and decode it into internal format + * Read or map a FAT and populate head bitmap */ int -readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp) +readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp) { - struct fatEntry *fat; + struct fat_descriptor *fat; u_char *buffer, *p; - cl_t cl; + cl_t cl, nextcl; int ret = FSOK; boot->NumFree = boot->NumBad = 0; - if (!_readfat(fs, boot, no, &buffer)) + fat = calloc(1, sizeof(struct fat_descriptor)); + if (fat == NULL) { + perr("No space for FAT descriptor"); return FSFATAL; + } - fat = calloc(boot->NumClusters, sizeof(struct fatEntry)); - if (fat == NULL) { - perr("No space for FAT clusters (%zu)", + fat->fd = fs; + fat->boot = boot; + + if (!_readfat(fat)) { + free(fat); + return FSFATAL; + } + buffer = fat->fatbuf; + + /* Populate accessors */ + switch(boot->ClustMask) { + case CLUST12_MASK: + fat->get = fat_get_fat12_next; + fat->set = fat_set_fat12_next; + break; + case CLUST16_MASK: + fat->get = fat_get_fat16_next; + fat->set = fat_set_fat16_next; + break; + case CLUST32_MASK: + if (fat->is_mmapped || !fat->use_cache) { + fat->get = fat_get_fat32_next; + fat->set = fat_set_fat32_next; + } else { + fat->get = fat_get_fat32_cached_next; + fat->set = fat_set_fat32_cached_next; + } + break; + default: + pfatal("Invalid ClustMask: %d", boot->ClustMask); + releasefat(fat); + free(fat); + return FSFATAL; + } + + if (bitmap_ctor(&fat->headbitmap, boot->NumClusters, + true) != FSOK) { + perr("No space for head bitmap for FAT clusters (%zu)", (size_t)boot->NumClusters); - free(buffer); + releasefat(fat); + free(fat); return FSFATAL; } @@ -263,54 +862,106 @@ readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp) break; } + if (ask(1, "Correct")) { + ret |= FSFATMOD; + p = buffer; - if (ask(1, "Correct")) - ret |= FSFIXFAT; + *p++ = (u_char)boot->bpbMedia; + *p++ = 0xff; + *p++ = 0xff; + switch (boot->ClustMask) { + case CLUST16_MASK: + *p++ = 0xff; + break; + case CLUST32_MASK: + *p++ = 0x0f; + *p++ = 0xff; + *p++ = 0xff; + *p++ = 0xff; + *p++ = 0x0f; + break; + default: + break; + } + } } } - switch (boot->ClustMask) { - case CLUST32_MASK: - p = buffer + 8; - break; - case CLUST16_MASK: - p = buffer + 4; - break; - default: - p = buffer + 3; - break; - } - for (cl = CLUST_FIRST; cl < boot->NumClusters;) { - switch (boot->ClustMask) { - case CLUST32_MASK: - fat[cl].next = p[0] + (p[1] << 8) - + (p[2] << 16) + (p[3] << 24); - fat[cl].next &= boot->ClustMask; - ret |= checkclnum(boot, no, cl, &fat[cl].next); - cl++; - p += 4; - break; - case CLUST16_MASK: - fat[cl].next = p[0] + (p[1] << 8); - ret |= checkclnum(boot, no, cl, &fat[cl].next); - cl++; - p += 2; - break; - default: - fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff; - ret |= checkclnum(boot, no, cl, &fat[cl].next); - cl++; - if (cl >= boot->NumClusters) - break; - fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff; - ret |= checkclnum(boot, no, cl, &fat[cl].next); - cl++; - p += 3; - break; + + /* + * Traverse the FAT table and populate head map. Initially, we + * consider all clusters as possible head cluster (beginning of + * a file or directory), and traverse the whole allocation table + * by marking every non-head nodes as such (detailed below) and + * fix obvious issues while we walk. + * + * For each "next" cluster, the possible values are: + * + * a) CLUST_FREE or CLUST_BAD. The *current* cluster can't be a + * head node. + * b) An out-of-range value. The only fix would be to truncate at + * the cluster. + * c) A valid cluster. It means that cluster (nextcl) is not a + * head cluster. Note that during the scan, every cluster is + * expected to be seen for at most once, and when we saw them + * twice, it means a cross-linked chain which should be + * truncated at the current cluster. + * + * After scan, the remaining set bits indicates all possible + * head nodes, because they were never claimed by any other + * node as the next node, but we do not know if these chains + * would end with a valid EOF marker. We will check that in + * checkchain() at a later time when checking directories, + * where these head nodes would be marked as non-head. + * + * In the final pass, all head nodes should be cleared, and if + * there is still head nodes, these would be leaders of lost + * chain. + */ + for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) { + nextcl = fat_get_cl_next(fat, cl); + + /* Check if the next cluster number is valid */ + if (nextcl == CLUST_FREE) { + /* Save a hint for next free cluster */ + if (boot->FSNext == 0) { + boot->FSNext = cl; + } + if (fat_is_cl_head(fat, cl)) { + fat_clear_cl_head(fat, cl); + } + boot->NumFree++; + } else if (nextcl == CLUST_BAD) { + if (fat_is_cl_head(fat, cl)) { + fat_clear_cl_head(fat, cl); + } + boot->NumBad++; + } else if (!valid_cl(fat, nextcl) && nextcl < CLUST_EOFS) { + pwarn("Cluster %u continues with %s " + "cluster number %u\n", + cl, (nextcl < CLUST_RSRVD) ? + "out of range" : "reserved", + nextcl & boot->ClustMask); + if (ask(0, "Truncate")) { + ret |= fat_set_cl_next(fat, cl, CLUST_EOF); + ret |= FSFATMOD; + } + } else if (nextcl < boot->NumClusters) { + if (fat_is_cl_head(fat, nextcl)) { + fat_clear_cl_head(fat, nextcl); + } else { + pwarn("Cluster %u crossed another chain at %u\n", + cl, nextcl); + if (ask(0, "Truncate")) { + ret |= fat_set_cl_next(fat, cl, CLUST_EOF); + ret |= FSFATMOD; + } + } } + } - free(buffer); if (ret & FSFATAL) { + releasefat(fat); free(fat); *fp = NULL; } else @@ -333,332 +984,202 @@ rsrvdcltype(cl_t cl) return "bad"; } -static int -clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, u_int fatnum) -{ - if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) { - if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) { - if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD - && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD) - || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) { - pwarn("Cluster %u is marked %s with different indicators\n", - cl, rsrvdcltype(*cp1)); - if (ask(1, "Fix")) { - *cp2 = *cp1; - return FSFATMOD; - } - return FSFATAL; - } - pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %u\n", - cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum); - if (ask(0, "Use FAT 0's entry")) { - *cp2 = *cp1; - return FSFATMOD; - } - if (ask(0, "Use FAT %u's entry", fatnum)) { - *cp1 = *cp2; - return FSFATMOD; - } - return FSFATAL; - } - pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n", - cl, rsrvdcltype(*cp1), *cp2, fatnum); - if (ask(0, "Use continuation from FAT %u", fatnum)) { - *cp1 = *cp2; - return FSFATMOD; - } - if (ask(0, "Use mark from FAT 0")) { - *cp2 = *cp1; - return FSFATMOD; - } - return FSFATAL; - } - if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) { - pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %u\n", - cl, *cp1, rsrvdcltype(*cp2), fatnum); - if (ask(0, "Use continuation from FAT 0")) { - *cp2 = *cp1; - return FSFATMOD; - } - if (ask(0, "Use mark from FAT %d", fatnum)) { - *cp1 = *cp2; - return FSFATMOD; - } +/* + * Offer to truncate a chain at the specified CL, called by checkchain(). + */ +static inline int +truncate_at(struct fat_descriptor *fat, cl_t current_cl, size_t *chainsize) +{ + int ret = 0; + + if (ask(0, "Truncate")) { + ret = fat_set_cl_next(fat, current_cl, CLUST_EOF); + (*chainsize)++; + return (ret | FSFATMOD); + } else { return FSERROR; } - pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %u\n", - cl, *cp1, *cp2, fatnum); - if (ask(0, "Use continuation from FAT 0")) { - *cp2 = *cp1; - return FSFATMOD; - } - if (ask(0, "Use continuation from FAT %u", fatnum)) { - *cp1 = *cp2; - return FSFATMOD; - } - return FSERROR; } /* - * Compare two FAT copies in memory. Resolve any conflicts and merge them - * into the first one. + * Examine a cluster chain for errors and count its size. */ int -comparefat(struct bootblock *boot, struct fatEntry *first, - struct fatEntry *second, u_int fatnum) +checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize) { - cl_t cl; - int ret = FSOK; + cl_t current_cl, next_cl; - for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) - if (first[cl].next != second[cl].next) - ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum); - return ret; + /* + * We expect that the caller to give us a real, unvisited 'head' + * cluster, and it must be a valid cluster. While scanning the + * FAT table, we already excluded all clusters that was claimed + * as a "next" cluster. Assert all the three conditions. + */ + assert(valid_cl(fat, head)); + assert(fat_is_cl_head(fat, head)); + + /* + * Immediately mark the 'head' cluster that we are about to visit. + */ + fat_clear_cl_head(fat, head); + + /* + * The allocation of a non-zero sized file or directory is + * represented as a singly linked list, and the tail node + * would be the EOF marker (>=CLUST_EOFS). + * + * With a valid head node at hand, we expect all subsequent + * cluster to be either a not yet seen and valid cluster (we + * would continue counting), or the EOF marker (we conclude + * the scan of this chain). + * + * For all other cases, the chain is invalid, and the only + * viable fix would be to truncate at the current node (mark + * it as EOF) when the next node violates that. + */ + *chainsize = 0; + current_cl = head; + for (next_cl = fat_get_cl_next(fat, current_cl); + valid_cl(fat, next_cl); + current_cl = next_cl, next_cl = fat_get_cl_next(fat, current_cl)) + (*chainsize)++; + + /* A natural end */ + if (next_cl >= CLUST_EOFS) { + (*chainsize)++; + return FSOK; + } + + /* The chain ended with an out-of-range cluster number. */ + pwarn("Cluster %u continues with %s cluster number %u\n", + current_cl, + next_cl < CLUST_RSRVD ? "out of range" : "reserved", + next_cl & boot_of_(fat)->ClustMask); + return (truncate_at(fat, current_cl, chainsize)); } +/* + * Clear cluster chain from head. + */ void -clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head) +clearchain(struct fat_descriptor *fat, cl_t head) { - cl_t p, q; + cl_t current_cl, next_cl; + struct bootblock *boot = boot_of_(fat); + + current_cl = head; - for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) { - if (fat[p].head != head) - break; - q = fat[p].next; - fat[p].next = fat[p].head = CLUST_FREE; - fat[p].length = 0; + while (valid_cl(fat, current_cl)) { + next_cl = fat_get_cl_next(fat, head); + (void)fat_set_cl_next(fat, current_cl, CLUST_FREE); + boot->NumFree++; + current_cl = next_cl; } -} -int -tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *truncp) -{ - if (ask(0, "Clear chain starting at %u", head)) { - clearchain(boot, fat, head); - return FSFATMOD; - } else if (ask(0, "Truncate")) { - uint32_t len; - cl_t p; - - for (p = head, len = 0; - p >= CLUST_FIRST && p < boot->NumClusters; - p = fat[p].next, len++) - continue; - *truncp = CLUST_EOF; - fat[head].length = len; - return FSFATMOD; - } else - return FSERROR; } /* - * Check a complete FAT in-memory for crosslinks + * Overwrite the n-th FAT with FAT0 */ -int -checkfat(struct bootblock *boot, struct fatEntry *fat) +static int +copyfat(struct fat_descriptor *fat, int n) { - cl_t head, p, h, n; - u_int len; - int ret = 0; - int conf; + size_t rwsize, tailsize, blobs, i; + off_t dst_off, src_off; + struct bootblock *boot; + int ret, fd; - /* - * pass 1: figure out the cluster chains. - */ - for (head = CLUST_FIRST; head < boot->NumClusters; head++) { - /* find next untravelled chain */ - if (fat[head].head != 0 /* cluster already belongs to some chain */ - || fat[head].next == CLUST_FREE - || fat[head].next == CLUST_BAD) - continue; /* skip it. */ - - /* follow the chain and mark all clusters on the way */ - for (len = 0, p = head; - p >= CLUST_FIRST && p < boot->NumClusters && - fat[p].head != head; - p = fat[p].next) { - fat[p].head = head; - len++; - } + ret = FSOK; + fd = fd_of_(fat); + boot = boot_of_(fat); - /* the head record gets the length */ - fat[head].length = fat[head].next == CLUST_FREE ? 0 : len; + blobs = howmany(fat->fatsize, fat32_cache_size); + tailsize = fat->fatsize % fat32_cache_size; + if (tailsize == 0) { + tailsize = fat32_cache_size; } + rwsize = fat32_cache_size; - /* - * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because - * we didn't know the real start of the chain then - would have treated partial - * chains as interlinked with their main chain) - */ - for (head = CLUST_FIRST; head < boot->NumClusters; head++) { - /* find next untravelled chain */ - if (fat[head].head != head) - continue; + src_off = fat->fat32_offset; + dst_off = boot->bpbResSectors + n * boot->FATsecs; + dst_off *= boot->bpbBytesPerSec; - /* follow the chain to its end (hopefully) */ - for (len = fat[head].length, p = head; - (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters; - p = n) - if (fat[n].head != head || len-- < 2) - break; - if (n >= CLUST_EOFS) - continue; - - if (n == CLUST_FREE || n >= CLUST_RSRVD) { - pwarn("Cluster chain starting at %u ends with cluster marked %s\n", - head, rsrvdcltype(n)); -clear: - ret |= tryclear(boot, fat, head, &fat[p].next); - continue; + for (i = 0; i < blobs; + i++, src_off += fat32_cache_size, dst_off += fat32_cache_size) { + if (i == blobs - 1) { + rwsize = tailsize; } - if (n < CLUST_FIRST || n >= boot->NumClusters) { - pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n", - head, n); - goto clear; - } - if (head == fat[n].head) { - pwarn("Cluster chain starting at %u loops at cluster %u\n", - head, p); - goto clear; + if ((lseek(fd, src_off, SEEK_SET) != src_off || + (size_t)read(fd, fat->fatbuf, rwsize) != rwsize) && + ret == FSOK) { + perr("Unable to read FAT0"); + ret = FSFATAL; + continue; } - pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n", - head, fat[n].head, n); - conf = tryclear(boot, fat, head, &fat[p].next); - if (ask(0, "Clear chain starting at %u", h = fat[n].head)) { - if (conf == FSERROR) { - /* - * Transfer the common chain to the one not cleared above. - */ - for (p = n; - p >= CLUST_FIRST && p < boot->NumClusters; - p = fat[p].next) { - if (h != fat[p].head) { - /* - * Have to reexamine this chain. - */ - head--; - break; - } - fat[p].head = head; - } - } - clearchain(boot, fat, h); - conf |= FSFATMOD; + if ((lseek(fd, dst_off, SEEK_SET) != dst_off || + (size_t)write(fd, fat->fatbuf, rwsize) != rwsize) && + ret == FSOK) { + perr("Unable to write FAT %d", n); + ret = FSERROR; } - ret |= conf; } - - return ret; + return (ret); } /* - * Write out FATs encoding them from the internal format + * Write out FAT */ int -writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat) +writefat(struct fat_descriptor *fat) { - u_char *buffer, *p; - cl_t cl; u_int i; - size_t fatsz; - off_t off; - int ret = FSOK; + size_t writesz; + off_t dst_base; + int ret = FSOK, fd; + struct bootblock *boot; + struct fat32_cache_entry *entry; - fatsz = boot->FATsecs * boot->bpbBytesPerSec; - buffer = calloc(boot->FATsecs, boot->bpbBytesPerSec); - if (buffer == NULL) { - perr("No space for FAT sectors (%zu)", - (size_t)boot->FATsecs); - return FSFATAL; - } - boot->NumFree = 0; - p = buffer; - if (correct_fat) { - *p++ = (u_char)boot->bpbMedia; - *p++ = 0xff; - *p++ = 0xff; - switch (boot->ClustMask) { - case CLUST16_MASK: - *p++ = 0xff; - break; - case CLUST32_MASK: - *p++ = 0x0f; - *p++ = 0xff; - *p++ = 0xff; - *p++ = 0xff; - *p++ = 0x0f; - break; - } - } else { - /* use same FAT signature as the old FAT has */ - int count; - u_char *old_fat; - - switch (boot->ClustMask) { - case CLUST32_MASK: - count = 8; - break; - case CLUST16_MASK: - count = 4; - break; - default: - count = 3; - break; - } + boot = boot_of_(fat); + fd = fd_of_(fat); - if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0, - &old_fat)) { - free(buffer); - return FSFATAL; + if (fat->use_cache) { + /* + * Attempt to flush all in-flight cache, and bail out + * if we encountered an error (but only emit error + * message once). Stop proceeding with copyfat() + * if any flush failed. + */ + TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) { + if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) { + if (ret == FSOK) { + perr("Unable to write FAT"); + ret = FSFATAL; + } + } } + if (ret != FSOK) + return (ret); - memcpy(p, old_fat, count); - free(old_fat); - p += count; - } - - for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) { - switch (boot->ClustMask) { - case CLUST32_MASK: - if (fat[cl].next == CLUST_FREE) - boot->NumFree++; - *p++ = (u_char)fat[cl].next; - *p++ = (u_char)(fat[cl].next >> 8); - *p++ = (u_char)(fat[cl].next >> 16); - *p &= 0xf0; - *p++ |= (fat[cl].next >> 24)&0x0f; - break; - case CLUST16_MASK: - if (fat[cl].next == CLUST_FREE) - boot->NumFree++; - *p++ = (u_char)fat[cl].next; - *p++ = (u_char)(fat[cl].next >> 8); - break; - default: - if (fat[cl].next == CLUST_FREE) - boot->NumFree++; - *p++ = (u_char)fat[cl].next; - *p = (u_char)((fat[cl].next >> 8) & 0xf); - cl++; - if (cl >= boot->NumClusters) - break; - if (fat[cl].next == CLUST_FREE) - boot->NumFree++; - *p++ |= (u_char)(fat[cl].next << 4); - *p++ = (u_char)(fat[cl].next >> 4); - break; + /* Update backup copies of FAT, error is not fatal */ + for (i = 1; i < boot->bpbFATs; i++) { + if (copyfat(fat, i) != FSOK) + ret = FSERROR; } - } - for (i = 0; i < boot->bpbFATs; i++) { - off = boot->bpbResSectors + i * boot->FATsecs; - off *= boot->bpbBytesPerSec; - if (lseek(fs, off, SEEK_SET) != off - || (size_t)write(fs, buffer, fatsz) != fatsz) { - perr("Unable to write FAT"); - ret = FSFATAL; /* Return immediately? XXX */ + } else { + writesz = fat->fatsize; + + for (i = fat->is_mmapped ? 1 : 0; i < boot->bpbFATs; i++) { + dst_base = boot->bpbResSectors + i * boot->FATsecs; + dst_base *= boot->bpbBytesPerSec; + if ((lseek(fd, dst_base, SEEK_SET) != dst_base || + (size_t)write(fd, fat->fatbuf, writesz) != writesz) && + ret == FSOK) { + perr("Unable to write FAT %d", i); + ret = ((i == 0) ? FSFATAL : FSERROR); + } } } - free(buffer); + return ret; } @@ -666,31 +1187,55 @@ writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat) * Check a complete in-memory FAT for lost cluster chains */ int -checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat) +checklost(struct fat_descriptor *fat) { cl_t head; int mod = FSOK; - int ret; - - for (head = CLUST_FIRST; head < boot->NumClusters; head++) { - /* find next untravelled chain */ - if (fat[head].head != head - || fat[head].next == CLUST_FREE - || (fat[head].next >= CLUST_RSRVD - && fat[head].next < CLUST_EOFS) - || (fat[head].flags & FAT_USED)) - continue; + int dosfs, ret; + size_t chains, chainlength; + struct bootblock *boot; + + dosfs = fd_of_(fat); + boot = boot_of_(fat); - pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n", - head, fat[head].length); - mod |= ret = reconnect(dosfs, boot, fat, head); - if (mod & FSFATAL) - break; - if (ret == FSERROR && ask(0, "Clear")) { - clearchain(boot, fat, head); - mod |= FSFATMOD; + /* + * At this point, we have already traversed all directories. + * All remaining chain heads in the bitmap are heads of lost + * chains. + */ + chains = fat_get_head_count(fat); + for (head = CLUST_FIRST; + chains > 0 && head < boot->NumClusters; + ) { + /* + * We expect the bitmap to be very sparse, so skip if + * the range is full of 0's + */ + if (head % LONG_BIT == 0 && + !fat_is_cl_head_in_range(fat, head)) { + head += LONG_BIT; + continue; + } + if (fat_is_cl_head(fat, head)) { + ret = checkchain(fat, head, &chainlength); + if (ret != FSERROR) { + pwarn("Lost cluster chain at cluster %u\n" + "%zd Cluster(s) lost\n", + head, chainlength); + mod |= ret = reconnect(fat, head, + chainlength); + } + if (mod & FSFATAL) + break; + if (ret == FSERROR && ask(0, "Clear")) { + clearchain(fat, head); + mod |= FSFATMOD; + } + chains--; } + head++; } + finishlf(); if (boot->bpbFSInfo) { @@ -706,13 +1251,13 @@ checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat) } if (boot->FSNext != 0xffffffffU && (boot->FSNext >= boot->NumClusters || - (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE))) { + (boot->NumFree && fat_get_cl_next(fat, boot->FSNext) != CLUST_FREE))) { pwarn("Next free cluster in FSInfo block (%u) %s\n", boot->FSNext, (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free"); - if (ask(1, "fix")) + if (ask(1, "Fix")) for (head = CLUST_FIRST; head < boot->NumClusters; head++) - if (fat[head].next == CLUST_FREE) { + if (fat_get_cl_next(fat, head) == CLUST_FREE) { boot->FSNext = head; ret = 1; break; |