2 * SPDX-License-Identifier: BSD-2-Clause
4 * Copyright (c) 2019 Google LLC
5 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
6 * Copyright (c) 1995 Martin Husemann
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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.
30 #include <sys/cdefs.h>
32 __RCSID("$NetBSD: fat.c,v 1.18 2006/06/05 16:51:18 christos Exp $");
33 static const char rcsid[] =
37 #include <sys/endian.h>
38 #include <sys/queue.h>
39 #include <sys/limits.h>
41 #include <sys/param.h>
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);
61 * Head bitmap for FAT scanning.
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).
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.
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
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.
84 typedef struct long_bitmap {
86 size_t count; /* Total set bits in the map */
90 bitmap_clear(long_bitmap_t *lbp, cl_t cl)
92 cl_t i = cl / LONG_BIT;
93 unsigned long clearmask = ~(1UL << (cl % LONG_BIT));
95 assert((lbp->map[i] & ~clearmask) != 0);
96 lbp->map[i] &= clearmask;
101 bitmap_get(long_bitmap_t *lbp, cl_t cl)
103 cl_t i = cl / LONG_BIT;
104 unsigned long usedbit = 1UL << (cl % LONG_BIT);
106 return ((lbp->map[i] & usedbit) == usedbit);
110 bitmap_none_in_range(long_bitmap_t *lbp, cl_t cl)
112 cl_t i = cl / LONG_BIT;
114 return (lbp->map[i] == 0);
118 bitmap_count(long_bitmap_t *lbp)
124 bitmap_ctor(long_bitmap_t *lbp, size_t bits, bool allone)
126 size_t bitmap_size = roundup2(bits, LONG_BIT) / (LONG_BIT / 8);
129 lbp->map = calloc(1, bitmap_size);
130 if (lbp->map == NULL)
134 memset(lbp->map, 0xff, bitmap_size);
143 bitmap_dtor(long_bitmap_t *lbp)
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.
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 */
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 */
166 * FAT table descriptor, represents a FAT table that is already loaded
169 struct fat_descriptor {
170 struct bootblock *boot;
172 cl_t (*get)(struct fat_descriptor *, cl_t);
173 int (*set)(struct fat_descriptor *, cl_t, cl_t);
174 long_bitmap_t headbitmap;
180 size_t fat32_cached_chunks;
181 TAILQ_HEAD(cachehead, fat32_cache_entry) fat32_cache_head;
182 struct fat32_cache_entry *fat32_cache_allentries;
184 off_t fat32_lastaddr;
188 fat_clear_cl_head(struct fat_descriptor *fat, cl_t cl)
190 bitmap_clear(&fat->headbitmap, cl);
194 fat_is_cl_head(struct fat_descriptor *fat, cl_t cl)
196 return (bitmap_get(&fat->headbitmap, cl));
200 fat_is_cl_head_in_range(struct fat_descriptor *fat, cl_t cl)
202 return (!(bitmap_none_in_range(&fat->headbitmap, cl)));
206 fat_get_head_count(struct fat_descriptor *fat)
208 return (bitmap_count(&fat->headbitmap));
214 * FAT12s are sufficiently small, expect it to always fit in the RAM.
216 static inline uint8_t *
217 fat_get_fat12_ptr(struct fat_descriptor *fat, cl_t cl)
219 return (fat->fatbuf + ((cl + (cl >> 1))));
223 fat_get_fat12_next(struct fat_descriptor *fat, cl_t cl)
228 p = fat_get_fat12_ptr(fat, cl);
230 /* Odd cluster: lower 4 bits belongs to the subsequent cluster */
233 retval &= CLUST12_MASK;
235 if (retval >= (CLUST_BAD & CLUST12_MASK))
236 retval |= ~CLUST12_MASK;
242 fat_set_fat12_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
246 /* Truncate 'nextcl' value, if needed */
247 nextcl &= CLUST12_MASK;
249 p = fat_get_fat12_ptr(fat, cl);
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
257 nextcl |= ((p[1] & 0xf0) << 8);
260 nextcl |= (p[0] & 0x0f);
263 le16enc(p, (uint16_t)nextcl);
271 * FAT16s are sufficiently small, expect it to always fit in the RAM.
273 static inline uint8_t *
274 fat_get_fat16_ptr(struct fat_descriptor *fat, cl_t cl)
276 return (fat->fatbuf + (cl << 1));
280 fat_get_fat16_next(struct fat_descriptor *fat, cl_t cl)
285 p = fat_get_fat16_ptr(fat, cl);
286 retval = le16dec(p) & CLUST16_MASK;
288 if (retval >= (CLUST_BAD & CLUST16_MASK))
289 retval |= ~CLUST16_MASK;
295 fat_set_fat16_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
299 /* Truncate 'nextcl' value, if needed */
300 nextcl &= CLUST16_MASK;
302 p = fat_get_fat16_ptr(fat, cl);
304 le16enc(p, (uint16_t)nextcl);
312 static inline uint8_t *
313 fat_get_fat32_ptr(struct fat_descriptor *fat, cl_t cl)
315 return (fat->fatbuf + (cl << 2));
319 fat_get_fat32_next(struct fat_descriptor *fat, cl_t cl)
324 p = fat_get_fat32_ptr(fat, cl);
325 retval = le32dec(p) & CLUST32_MASK;
327 if (retval >= (CLUST_BAD & CLUST32_MASK))
328 retval |= ~CLUST32_MASK;
334 fat_set_fat32_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
338 /* Truncate 'nextcl' value, if needed */
339 nextcl &= CLUST32_MASK;
341 p = fat_get_fat32_ptr(fat, cl);
343 le32enc(p, (uint32_t)nextcl);
349 fat_get_iosize(struct fat_descriptor *fat, off_t address)
352 if (address == fat->fat32_lastaddr) {
353 return (fat->fatsize & ((off_t)fat32_cache_chunk_size - 1));
355 return (fat32_cache_chunk_size);
360 fat_flush_fat32_cache_entry(struct fat_descriptor *fat,
361 struct fat32_cache_entry *entry)
372 writesize = fat_get_iosize(fat, entry->addr);
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");
381 entry->dirty = false;
385 static struct fat32_cache_entry *
386 fat_get_fat32_cache_entry(struct fat_descriptor *fat, off_t addr,
390 struct fat32_cache_entry *entry, *first;
394 addr &= ~(fat32_cache_chunk_size - 1);
396 first = TAILQ_FIRST(&fat->fat32_cache_head);
399 * Cache hit: if we already have the chunk, move it to list head
401 TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) {
402 if (entry->addr == addr) {
406 if (entry != first) {
408 TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries);
409 TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries);
416 * Cache miss: detach the chunk at tail of list, overwrite with
417 * the located chunk, and populate with data from disk.
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) {
425 rwsize = fat_get_iosize(fat, addr);
426 fat_addr = fat->fat32_offset + addr;
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");
437 TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries);
442 static inline uint8_t *
443 fat_get_fat32_cached_ptr(struct fat_descriptor *fat, cl_t cl, bool writing)
446 struct fat32_cache_entry *entry;
449 entry = fat_get_fat32_cache_entry(fat, addr, writing);
452 off = addr & (fat32_cache_chunk_size - 1);
453 return (entry->chunk + off);
461 fat_get_fat32_cached_next(struct fat_descriptor *fat, cl_t cl)
466 p = fat_get_fat32_cached_ptr(fat, cl, false);
468 retval = le32dec(p) & CLUST32_MASK;
469 if (retval >= (CLUST_BAD & CLUST32_MASK))
470 retval |= ~CLUST32_MASK;
479 fat_set_fat32_cached_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
483 /* Truncate 'nextcl' value, if needed */
484 nextcl &= CLUST32_MASK;
486 p = fat_get_fat32_cached_ptr(fat, cl, true);
488 le32enc(p, (uint32_t)nextcl);
495 cl_t fat_get_cl_next(struct fat_descriptor *fat, cl_t cl)
498 if (!valid_cl(fat, cl)) {
499 pfatal("Invalid cluster: %ud", cl);
503 return (fat->get(fat, cl));
506 int fat_set_cl_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
510 pwarn(" (NO WRITE)\n");
514 if (!valid_cl(fat, cl)) {
515 pfatal("Invalid cluster: %ud", cl);
519 return (fat->set(fat, cl, nextcl));
522 static inline struct bootblock*
523 boot_of_(struct fat_descriptor *fat) {
529 fat_get_boot(struct fat_descriptor *fat) {
531 return (boot_of_(fat));
535 fd_of_(struct fat_descriptor *fat)
541 fat_get_fd(struct fat_descriptor * fat)
543 return (fd_of_(fat));
547 * Whether a cl is in valid data range.
550 fat_is_valid_cl(struct fat_descriptor *fat, cl_t cl)
553 return (valid_cl(fat, cl));
557 valid_cl(struct fat_descriptor *fat, cl_t cl)
559 const struct bootblock *boot = boot_of_(fat);
561 return (cl >= CLUST_FIRST && cl < boot->NumClusters);
565 * The first 2 FAT entries contain pseudo-cluster numbers with the following
568 * 31...... ........ ........ .......0
569 * rrrr1111 11111111 11111111 mmmmmmmm FAT32 entry 0
570 * rrrrsh11 11111111 11111111 11111xxx FAT32 entry 1
572 * 11111111 mmmmmmmm FAT16 entry 0
573 * sh111111 11111xxx FAT16 entry 1
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)
583 checkdirty(int fs, struct bootblock *boot)
590 if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK)
593 off = boot->bpbResSectors;
594 off *= boot->bpbBytesPerSec;
596 buffer = malloc(len = boot->bpbBytesPerSec);
597 if (buffer == NULL) {
598 perr("No space for FAT sectors (%zu)", len);
602 if (lseek(fs, off, SEEK_SET) != off) {
603 perr("Unable to read FAT");
607 if ((size_t)read(fs, buffer, boot->bpbBytesPerSec) !=
608 boot->bpbBytesPerSec) {
609 perr("Unable to read FAT");
614 * If we don't understand the FAT, then the file system must be
615 * assumed to be unclean.
617 if (buffer[0] != boot->bpbMedia || buffer[1] != 0xff)
619 if (boot->ClustMask == CLUST16_MASK) {
620 if ((buffer[2] & 0xf8) != 0xf8 || (buffer[3] & 0x3f) != 0x3f)
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)
630 * Now check the actual clean flag (and the no-error flag).
632 if (boot->ClustMask == CLUST16_MASK) {
633 if ((buffer[3] & 0xc0) == 0xc0)
636 if ((buffer[7] & 0x0c) == 0x0c)
646 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
649 _readfat(struct fat_descriptor *fat)
655 struct bootblock *boot;
656 struct fat32_cache_entry *entry;
658 boot = boot_of_(fat);
660 fat->fatsize = boot->FATsecs * boot->bpbBytesPerSec;
662 off = boot->bpbResSectors;
663 off *= boot->bpbBytesPerSec;
665 fat->is_mmapped = false;
666 fat->use_cache = false;
668 /* Attempt to mmap() first */
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;
680 * Unfortunately, we were unable to mmap().
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.
688 if (boot->ClustMask == CLUST32_MASK &&
689 fat->fatsize >= fat32_cache_size) {
690 readsize = fat32_cache_size;
691 fat->use_cache = true;
693 fat->fat32_offset = boot->bpbResSectors * boot->bpbBytesPerSec;
694 fat->fat32_lastaddr = fat->fatsize & ~(fat32_cache_chunk_size);
696 readsize = fat->fatsize;
698 fat->fatbuf = malloc(readsize);
699 if (fat->fatbuf == NULL) {
700 perr("No space for FAT (%zu)", readsize);
704 if (lseek(fd, off, SEEK_SET) != off) {
705 perr("Unable to read FAT");
708 if ((size_t)read(fd, fat->fatbuf, readsize) != readsize) {
709 perr("Unable to read FAT");
714 * When cache is used, split the buffer into chunks, and
715 * connect the buffer into the cache.
717 if (fat->use_cache) {
718 TAILQ_INIT(&fat->fat32_cache_head);
719 entry = calloc(fat32_cache_entries, sizeof(*entry));
721 perr("No space for FAT cache (%zu of %zu)",
722 fat32_cache_entries, sizeof(entry));
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,
731 fat->fat32_cache_allentries = entry;
743 releasefat(struct fat_descriptor *fat)
745 if (fat->is_mmapped) {
746 munmap(fat->fatbuf, fat->fatsize);
748 if (fat->use_cache) {
749 free(fat->fat32_cache_allentries);
750 fat->fat32_cache_allentries = NULL;
755 bitmap_dtor(&fat->headbitmap);
759 * Read or map a FAT and populate head bitmap
762 readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
764 struct fat_descriptor *fat;
769 boot->NumFree = boot->NumBad = 0;
771 fat = calloc(1, sizeof(struct fat_descriptor));
773 perr("No space for FAT descriptor");
780 if (!_readfat(fat)) {
784 buffer = fat->fatbuf;
786 /* Populate accessors */
787 switch(boot->ClustMask) {
789 fat->get = fat_get_fat12_next;
790 fat->set = fat_set_fat12_next;
793 fat->get = fat_get_fat16_next;
794 fat->set = fat_set_fat16_next;
797 if (fat->is_mmapped || !fat->use_cache) {
798 fat->get = fat_get_fat32_next;
799 fat->set = fat_set_fat32_next;
801 fat->get = fat_get_fat32_cached_next;
802 fat->set = fat_set_fat32_cached_next;
806 pfatal("Invalid ClustMask: %d", boot->ClustMask);
812 if (bitmap_ctor(&fat->headbitmap, boot->NumClusters,
814 perr("No space for head bitmap for FAT clusters (%zu)",
815 (size_t)boot->NumClusters);
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))) {
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.
835 if (buffer[0] == boot->bpbMedia && buffer[1] == 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)))
844 /* just some odd byte sequence in FAT */
846 switch (boot->ClustMask) {
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]);
854 pwarn("%s (%02x%02x%02x%02x)\n",
855 "FAT starts with odd byte sequence",
856 buffer[0], buffer[1], buffer[2], buffer[3]);
859 pwarn("%s (%02x%02x%02x)\n",
860 "FAT starts with odd byte sequence",
861 buffer[0], buffer[1], buffer[2]);
865 if (ask(1, "Correct")) {
869 *p++ = (u_char)boot->bpbMedia;
872 switch (boot->ClustMask) {
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.
897 * For each "next" cluster, the possible values are:
899 * a) CLUST_FREE or CLUST_BAD. The *current* cluster can't be a
901 * b) An out-of-range value. The only fix would be to truncate at
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.
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.
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
920 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
921 nextcl = fat_get_cl_next(fat, cl);
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) {
929 if (fat_is_cl_head(fat, cl)) {
930 fat_clear_cl_head(fat, cl);
933 } else if (nextcl == CLUST_BAD) {
934 if (fat_is_cl_head(fat, cl)) {
935 fat_clear_cl_head(fat, cl);
938 } else if (!valid_cl(fat, nextcl) && nextcl < CLUST_RSRVD) {
939 pwarn("Cluster %u continues with out of range "
940 "cluster number %u\n",
942 nextcl & boot->ClustMask);
943 if (ask(0, "Truncate")) {
944 ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
947 } else if (valid_cl(fat, nextcl)) {
948 if (fat_is_cl_head(fat, nextcl)) {
949 fat_clear_cl_head(fat, nextcl);
951 pwarn("Cluster %u crossed another chain at %u\n",
953 if (ask(0, "Truncate")) {
954 ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
972 * Get type of reserved cluster
977 if (cl == CLUST_FREE)
987 * Examine a cluster chain for errors and count its size.
990 checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
992 cl_t prev_cl, current_cl, next_cl;
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.
1001 assert(valid_cl(fat, head));
1002 assert(fat_is_cl_head(fat, head));
1005 * Immediately mark the 'head' cluster that we are about to visit.
1007 fat_clear_cl_head(fat, head);
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).
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).
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.
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))
1031 if (next_cl >= CLUST_EOFS) {
1037 * The chain ended with an out-of-range cluster number.
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.
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.
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;
1052 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
1054 next_cl & boot_of_(fat)->ClustMask);
1058 if (*chainsize > 0) {
1060 next_cl = CLUST_EOF;
1063 next_cl = CLUST_FREE;
1065 if (ask(0, "%s", op)) {
1066 return (fat_set_cl_next(fat, current_cl, next_cl) | FSFATMOD);
1073 * Clear cluster chain from head.
1076 clearchain(struct fat_descriptor *fat, cl_t head)
1078 cl_t current_cl, next_cl;
1079 struct bootblock *boot = boot_of_(fat);
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);
1087 current_cl = next_cl;
1093 * Overwrite the n-th FAT with FAT0
1096 copyfat(struct fat_descriptor *fat, int n)
1098 size_t rwsize, tailsize, blobs, i;
1099 off_t dst_off, src_off;
1100 struct bootblock *boot;
1105 boot = boot_of_(fat);
1107 blobs = howmany(fat->fatsize, fat32_cache_size);
1108 tailsize = fat->fatsize % fat32_cache_size;
1109 if (tailsize == 0) {
1110 tailsize = fat32_cache_size;
1112 rwsize = fat32_cache_size;
1114 src_off = fat->fat32_offset;
1115 dst_off = boot->bpbResSectors + n * boot->FATsecs;
1116 dst_off *= boot->bpbBytesPerSec;
1118 for (i = 0; i < blobs;
1119 i++, src_off += fat32_cache_size, dst_off += fat32_cache_size) {
1120 if (i == blobs - 1) {
1123 if ((lseek(fd, src_off, SEEK_SET) != src_off ||
1124 (size_t)read(fd, fat->fatbuf, rwsize) != rwsize) &&
1126 perr("Unable to read FAT0");
1130 if ((lseek(fd, dst_off, SEEK_SET) != dst_off ||
1131 (size_t)write(fd, fat->fatbuf, rwsize) != rwsize) &&
1133 perr("Unable to write FAT %d", n);
1144 writefat(struct fat_descriptor *fat)
1150 struct bootblock *boot;
1151 struct fat32_cache_entry *entry;
1153 boot = boot_of_(fat);
1156 if (fat->use_cache) {
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.
1163 TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) {
1164 if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) {
1166 perr("Unable to write FAT");
1174 /* Update backup copies of FAT, error is not fatal */
1175 for (i = 1; i < boot->bpbFATs; i++) {
1176 if (copyfat(fat, i) != FSOK)
1180 writesz = fat->fatsize;
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) &&
1188 perr("Unable to write FAT %d", i);
1189 ret = ((i == 0) ? FSFATAL : FSERROR);
1198 * Check a complete in-memory FAT for lost cluster chains
1201 checklost(struct fat_descriptor *fat)
1206 size_t chains, chainlength;
1207 struct bootblock *boot;
1209 dosfs = fd_of_(fat);
1210 boot = boot_of_(fat);
1213 * At this point, we have already traversed all directories.
1214 * All remaining chain heads in the bitmap are heads of lost
1217 chains = fat_get_head_count(fat);
1218 for (head = CLUST_FIRST;
1219 chains > 0 && head < boot->NumClusters;
1222 * We expect the bitmap to be very sparse, so skip if
1223 * the range is full of 0's
1225 if (head % LONG_BIT == 0 &&
1226 !fat_is_cl_head_in_range(fat, head)) {
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",
1236 mod |= ret = reconnect(fat, head,
1241 if (ret == FSERROR && ask(0, "Clear")) {
1242 clearchain(fat, head);
1252 if (boot->bpbFSInfo) {
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;
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",
1268 (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
1270 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
1271 if (fat_get_cl_next(fat, head) == CLUST_FREE) {
1272 boot->FSNext = head;
1278 mod |= writefsinfo(dosfs, boot);