/*-
* SPDX-License-Identifier: BSD-2-Clause
*
* Copyright (c) 2019 Google LLC
* Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
* Copyright (c) 1995 Martin Husemann
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <sys/cdefs.h>
#ifndef lint
__RCSID("$NetBSD: fat.c,v 1.18 2006/06/05 16:51:18 christos Exp $");
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>
#include <stdio.h>
#include <unistd.h>
#include "ext.h"
#include "fsutil.h"
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:
*
* 31...... ........ ........ .......0
* rrrr1111 11111111 11111111 mmmmmmmm FAT32 entry 0
* rrrrsh11 11111111 11111111 11111xxx FAT32 entry 1
*
* 11111111 mmmmmmmm FAT16 entry 0
* sh111111 11111xxx FAT16 entry 1
*
* r = reserved
* m = BPB media ID byte
* s = clean flag (1 = dismounted; 0 = still mounted)
* h = hard error flag (1 = ok; 0 = I/O error)
* x = any value ok
*/
int
checkdirty(int fs, struct bootblock *boot)
{
off_t off;
u_char *buffer;
int ret = 0;
size_t len;
if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK)
return 0;
off = boot->bpbResSectors;
off *= boot->bpbBytesPerSec;
buffer = malloc(len = boot->bpbBytesPerSec);
if (buffer == NULL) {
perr("No space for FAT sectors (%zu)", len);
return 1;
}
if (lseek(fs, off, SEEK_SET) != off) {
perr("Unable to read FAT");
goto err;
}
if ((size_t)read(fs, buffer, boot->bpbBytesPerSec) !=
boot->bpbBytesPerSec) {
perr("Unable to read FAT");
goto err;
}
/*
* If we don't understand the FAT, then the file system must be
* assumed to be unclean.
*/
if (buffer[0] != boot->bpbMedia || buffer[1] != 0xff)
goto err;
if (boot->ClustMask == CLUST16_MASK) {
if ((buffer[2] & 0xf8) != 0xf8 || (buffer[3] & 0x3f) != 0x3f)
goto err;
} else {
if (buffer[2] != 0xff || (buffer[3] & 0x0f) != 0x0f
|| (buffer[4] & 0xf8) != 0xf8 || buffer[5] != 0xff
|| buffer[6] != 0xff || (buffer[7] & 0x03) != 0x03)
goto err;
}
/*
* Now check the actual clean flag (and the no-error flag).
*/
if (boot->ClustMask == CLUST16_MASK) {
if ((buffer[3] & 0xc0) == 0xc0)
ret = 1;
} else {
if ((buffer[7] & 0x0c) == 0x0c)
ret = 1;
}
err:
free(buffer);
return ret;
}
int
cleardirty(struct fat_descriptor *fat)
{
int fd, ret = FSERROR;
struct bootblock *boot;
u_char *buffer;
size_t len;
off_t off;
boot = boot_of_(fat);
fd = fd_of_(fat);
if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK)
return 0;
off = boot->bpbResSectors;
off *= boot->bpbBytesPerSec;
buffer = malloc(len = boot->bpbBytesPerSec);
if (buffer == NULL) {
perr("No memory for FAT sectors (%zu)", len);
return 1;
}
if ((size_t)pread(fd, buffer, len, off) != len) {
perr("Unable to read FAT");
goto err;
}
if (boot->ClustMask == CLUST16_MASK) {
buffer[3] |= 0x80;
} else {
buffer[7] |= 0x08;
}
if ((size_t)pwrite(fd, buffer, len, off) != len) {
perr("Unable to write FAT");
goto err;
}
ret = FSOK;
err:
free(buffer);
return ret;
}
/*
* Read a FAT from disk. Returns 1 if successful, 0 otherwise.
*/
static int
_readfat(struct fat_descriptor *fat)
{
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;
}
}
/*
* 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;
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;
}
if (lseek(fd, off, SEEK_SET) != off) {
perr("Unable to read FAT");
goto err;
}
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(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 or map a FAT and populate head bitmap
*/
int
readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
{
struct fat_descriptor *fat;
u_char *buffer, *p;
cl_t cl, nextcl;
int ret = FSOK;
boot->NumFree = boot->NumBad = 0;
fat = calloc(1, sizeof(struct fat_descriptor));
if (fat == NULL) {
perr("No space for FAT descriptor");
return FSFATAL;
}
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);
releasefat(fat);
free(fat);
return FSFATAL;
}
if (buffer[0] != boot->bpbMedia
|| buffer[1] != 0xff || buffer[2] != 0xff
|| (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
|| (boot->ClustMask == CLUST32_MASK
&& ((buffer[3]&0x0f) != 0x0f
|| buffer[4] != 0xff || buffer[5] != 0xff
|| buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
/* Windows 95 OSR2 (and possibly any later) changes
* the FAT signature to 0xXXffff7f for FAT16 and to
* 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
* file system is dirty if it doesn't reboot cleanly.
* Check this special condition before errorring out.
*/
if (buffer[0] == boot->bpbMedia && buffer[1] == 0xff
&& buffer[2] == 0xff
&& ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
|| (boot->ClustMask == CLUST32_MASK
&& buffer[3] == 0x0f && buffer[4] == 0xff
&& buffer[5] == 0xff && buffer[6] == 0xff
&& buffer[7] == 0x07)))
ret |= FSDIRTY;
else {
/* just some odd byte sequence in FAT */
switch (boot->ClustMask) {
case CLUST32_MASK:
pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
"FAT starts with odd byte sequence",
buffer[0], buffer[1], buffer[2], buffer[3],
buffer[4], buffer[5], buffer[6], buffer[7]);
break;
case CLUST16_MASK:
pwarn("%s (%02x%02x%02x%02x)\n",
"FAT starts with odd byte sequence",
buffer[0], buffer[1], buffer[2], buffer[3]);
break;
default:
pwarn("%s (%02x%02x%02x)\n",
"FAT starts with odd byte sequence",
buffer[0], buffer[1], buffer[2]);
break;
}
if (ask(1, "Correct")) {
ret |= FSFATMOD;
p = buffer;
*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;
}
}
}
}
/*
* 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_RSRVD) {
pwarn("Cluster %u continues with out of range "
"cluster number %u\n",
cl,
nextcl & boot->ClustMask);
if (ask(0, "Truncate")) {
ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
ret |= FSFATMOD;
}
} else if (valid_cl(fat, nextcl)) {
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;
}
}
}
}
if (ret & FSFATAL) {
releasefat(fat);
free(fat);
*fp = NULL;
} else
*fp = fat;
return ret;
}
/*
* Get type of reserved cluster
*/
const char *
rsrvdcltype(cl_t cl)
{
if (cl == CLUST_FREE)
return "free";
if (cl < CLUST_BAD)
return "reserved";
if (cl > CLUST_BAD)
return "as EOF";
return "bad";
}
/*
* Examine a cluster chain for errors and count its size.
*/
int
checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
{
cl_t prev_cl, current_cl, next_cl;
const char *op;
/*
* 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;
prev_cl = current_cl = head;
for (next_cl = fat_get_cl_next(fat, current_cl);
valid_cl(fat, next_cl);
prev_cl = current_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.
*
* If the current node is e.g. CLUST_FREE, CLUST_BAD, etc.,
* it should not be present in a chain and we has to truncate
* at the previous node.
*
* If the current cluster points to an invalid cluster, the
* current cluster might have useful data and we truncate at
* the current cluster instead.
*/
if (next_cl == CLUST_FREE || next_cl >= CLUST_RSRVD) {
pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
head, rsrvdcltype(next_cl));
current_cl = prev_cl;
} else {
pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
head,
next_cl & boot_of_(fat)->ClustMask);
(*chainsize)++;
}
if (*chainsize > 0) {
op = "Truncate";
next_cl = CLUST_EOF;
} else {
op = "Clear";
next_cl = CLUST_FREE;
}
if (ask(0, "%s", op)) {
return (fat_set_cl_next(fat, current_cl, next_cl) | FSFATMOD);
} else {
return (FSERROR);
}
}
/*
* Clear cluster chain from head.
*/
void
clearchain(struct fat_descriptor *fat, cl_t head)
{
cl_t current_cl, next_cl;
struct bootblock *boot = boot_of_(fat);
current_cl = head;
while (valid_cl(fat, current_cl)) {
next_cl = fat_get_cl_next(fat, current_cl);
(void)fat_set_cl_next(fat, current_cl, CLUST_FREE);
boot->NumFree++;
current_cl = next_cl;
}
}
/*
* Overwrite the n-th FAT with FAT0
*/
static int
copyfat(struct fat_descriptor *fat, int n)
{
size_t rwsize, tailsize, blobs, i;
off_t dst_off, src_off;
struct bootblock *boot;
int ret, fd;
ret = FSOK;
fd = fd_of_(fat);
boot = boot_of_(fat);
blobs = howmany(fat->fatsize, fat32_cache_size);
tailsize = fat->fatsize % fat32_cache_size;
if (tailsize == 0) {
tailsize = fat32_cache_size;
}
rwsize = fat32_cache_size;
src_off = fat->fat32_offset;
dst_off = boot->bpbResSectors + n * boot->FATsecs;
dst_off *= boot->bpbBytesPerSec;
for (i = 0; i < blobs;
i++, src_off += fat32_cache_size, dst_off += fat32_cache_size) {
if (i == blobs - 1) {
rwsize = tailsize;
}
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;
}
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;
}
}
return (ret);
}
/*
* Write out FAT
*/
int
writefat(struct fat_descriptor *fat)
{
u_int i;
size_t writesz;
off_t dst_base;
int ret = FSOK, fd;
struct bootblock *boot;
struct fat32_cache_entry *entry;
boot = boot_of_(fat);
fd = fd_of_(fat);
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);
/* Update backup copies of FAT, error is not fatal */
for (i = 1; i < boot->bpbFATs; i++) {
if (copyfat(fat, i) != FSOK)
ret = FSERROR;
}
} 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);
}
}
}
return ret;
}
/*
* Check a complete in-memory FAT for lost cluster chains
*/
int
checklost(struct fat_descriptor *fat)
{
cl_t head;
int mod = FSOK;
int dosfs, ret;
size_t chains, chainlength;
struct bootblock *boot;
dosfs = fd_of_(fat);
boot = boot_of_(fat);
/*
* 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 && chainlength > 0) {
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) {
ret = 0;
if (boot->FSFree != 0xffffffffU &&
boot->FSFree != boot->NumFree) {
pwarn("Free space in FSInfo block (%u) not correct (%u)\n",
boot->FSFree, boot->NumFree);
if (ask(1, "Fix")) {
boot->FSFree = boot->NumFree;
ret = 1;
}
}
if (boot->FSNext != 0xffffffffU &&
(boot->FSNext >= boot->NumClusters ||
(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"))
for (head = CLUST_FIRST; head < boot->NumClusters; head++)
if (fat_get_cl_next(fat, head) == CLUST_FREE) {
boot->FSNext = head;
ret = 1;
break;
}
}
if (ret)
mod |= writefsinfo(dosfs, boot);
}
return mod;
}
