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 $");
35 #include <sys/endian.h>
36 #include <sys/queue.h>
37 #include <sys/limits.h>
39 #include <sys/param.h>
52 static int _readfat(struct fat_descriptor *);
53 static inline struct bootblock* boot_of_(struct fat_descriptor *);
54 static inline int fd_of_(struct fat_descriptor *);
55 static inline bool valid_cl(struct fat_descriptor *, cl_t);
59 * Head bitmap for FAT scanning.
61 * FAT32 have up to 2^28 = 256M entries, and FAT16/12 have much less.
62 * For each cluster, we use 1 bit to represent if it's a head cluster
63 * (the first cluster of a cluster chain).
67 * Initially, we set all bits to 1. In readfat(), we traverse the
68 * whole FAT and mark each cluster identified as "next" cluster as
69 * 0. After the scan, we have a bitmap with 1's to indicate the
70 * corresponding cluster was a "head" cluster.
72 * We use head bitmap to identify lost chains: a head cluster that was
73 * not being claimed by any file or directories is the head cluster of
76 * Handle of lost chains
77 * =====================
78 * At the end of scanning, we can easily find all lost chain's heads
79 * by finding out the 1's in the head bitmap.
82 typedef struct long_bitmap {
84 size_t count; /* Total set bits in the map */
88 bitmap_clear(long_bitmap_t *lbp, cl_t cl)
90 cl_t i = cl / LONG_BIT;
91 unsigned long clearmask = ~(1UL << (cl % LONG_BIT));
93 assert((lbp->map[i] & ~clearmask) != 0);
94 lbp->map[i] &= clearmask;
99 bitmap_get(long_bitmap_t *lbp, cl_t cl)
101 cl_t i = cl / LONG_BIT;
102 unsigned long usedbit = 1UL << (cl % LONG_BIT);
104 return ((lbp->map[i] & usedbit) == usedbit);
108 bitmap_none_in_range(long_bitmap_t *lbp, cl_t cl)
110 cl_t i = cl / LONG_BIT;
112 return (lbp->map[i] == 0);
116 bitmap_count(long_bitmap_t *lbp)
122 bitmap_ctor(long_bitmap_t *lbp, size_t bits, bool allone)
124 size_t bitmap_size = roundup2(bits, LONG_BIT) / (LONG_BIT / 8);
127 lbp->map = calloc(1, bitmap_size);
128 if (lbp->map == NULL)
132 memset(lbp->map, 0xff, bitmap_size);
141 bitmap_dtor(long_bitmap_t *lbp)
148 * FAT32 can be as big as 256MiB (2^26 entries * 4 bytes), when we
149 * can not ask the kernel to manage the access, use a simple LRU
150 * cache with chunk size of 128 KiB to manage it.
152 struct fat32_cache_entry {
153 TAILQ_ENTRY(fat32_cache_entry) entries;
154 uint8_t *chunk; /* pointer to chunk */
155 off_t addr; /* offset */
156 bool dirty; /* dirty bit */
159 static const size_t fat32_cache_chunk_size = 131072; /* MAXPHYS */
160 static const size_t fat32_cache_size = 4194304;
161 static const size_t fat32_cache_entries = 32; /* XXXgcc: cache_size / cache_chunk_size */
164 * FAT table descriptor, represents a FAT table that is already loaded
167 struct fat_descriptor {
168 struct bootblock *boot;
170 cl_t (*get)(struct fat_descriptor *, cl_t);
171 int (*set)(struct fat_descriptor *, cl_t, cl_t);
172 long_bitmap_t headbitmap;
178 size_t fat32_cached_chunks;
179 TAILQ_HEAD(cachehead, fat32_cache_entry) fat32_cache_head;
180 struct fat32_cache_entry *fat32_cache_allentries;
182 off_t fat32_lastaddr;
186 fat_clear_cl_head(struct fat_descriptor *fat, cl_t cl)
188 bitmap_clear(&fat->headbitmap, cl);
192 fat_is_cl_head(struct fat_descriptor *fat, cl_t cl)
194 return (bitmap_get(&fat->headbitmap, cl));
198 fat_is_cl_head_in_range(struct fat_descriptor *fat, cl_t cl)
200 return (!(bitmap_none_in_range(&fat->headbitmap, cl)));
204 fat_get_head_count(struct fat_descriptor *fat)
206 return (bitmap_count(&fat->headbitmap));
212 * FAT12s are sufficiently small, expect it to always fit in the RAM.
214 static inline uint8_t *
215 fat_get_fat12_ptr(struct fat_descriptor *fat, cl_t cl)
217 return (fat->fatbuf + ((cl + (cl >> 1))));
221 fat_get_fat12_next(struct fat_descriptor *fat, cl_t cl)
226 p = fat_get_fat12_ptr(fat, cl);
228 /* Odd cluster: lower 4 bits belongs to the subsequent cluster */
231 retval &= CLUST12_MASK;
233 if (retval >= (CLUST_BAD & CLUST12_MASK))
234 retval |= ~CLUST12_MASK;
240 fat_set_fat12_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
244 /* Truncate 'nextcl' value, if needed */
245 nextcl &= CLUST12_MASK;
247 p = fat_get_fat12_ptr(fat, cl);
250 * Read in the 4 bits from the subsequent (for even clusters)
251 * or the preceding (for odd clusters) cluster and combine
252 * it to the nextcl value for encoding
255 nextcl |= ((p[1] & 0xf0) << 8);
258 nextcl |= (p[0] & 0x0f);
261 le16enc(p, (uint16_t)nextcl);
269 * FAT16s are sufficiently small, expect it to always fit in the RAM.
271 static inline uint8_t *
272 fat_get_fat16_ptr(struct fat_descriptor *fat, cl_t cl)
274 return (fat->fatbuf + (cl << 1));
278 fat_get_fat16_next(struct fat_descriptor *fat, cl_t cl)
283 p = fat_get_fat16_ptr(fat, cl);
284 retval = le16dec(p) & CLUST16_MASK;
286 if (retval >= (CLUST_BAD & CLUST16_MASK))
287 retval |= ~CLUST16_MASK;
293 fat_set_fat16_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
297 /* Truncate 'nextcl' value, if needed */
298 nextcl &= CLUST16_MASK;
300 p = fat_get_fat16_ptr(fat, cl);
302 le16enc(p, (uint16_t)nextcl);
310 static inline uint8_t *
311 fat_get_fat32_ptr(struct fat_descriptor *fat, cl_t cl)
313 return (fat->fatbuf + (cl << 2));
317 fat_get_fat32_next(struct fat_descriptor *fat, cl_t cl)
322 p = fat_get_fat32_ptr(fat, cl);
323 retval = le32dec(p) & CLUST32_MASK;
325 if (retval >= (CLUST_BAD & CLUST32_MASK))
326 retval |= ~CLUST32_MASK;
332 fat_set_fat32_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
336 /* Truncate 'nextcl' value, if needed */
337 nextcl &= CLUST32_MASK;
339 p = fat_get_fat32_ptr(fat, cl);
341 le32enc(p, (uint32_t)nextcl);
347 fat_get_iosize(struct fat_descriptor *fat, off_t address)
350 if (address == fat->fat32_lastaddr) {
351 return (fat->fatsize & ((off_t)fat32_cache_chunk_size - 1));
353 return (fat32_cache_chunk_size);
358 fat_flush_fat32_cache_entry(struct fat_descriptor *fat,
359 struct fat32_cache_entry *entry)
370 writesize = fat_get_iosize(fat, entry->addr);
372 fat_addr = fat->fat32_offset + entry->addr;
373 if (lseek(fd, fat_addr, SEEK_SET) != fat_addr ||
374 (size_t)write(fd, entry->chunk, writesize) != writesize) {
375 pfatal("Unable to write FAT");
379 entry->dirty = false;
383 static struct fat32_cache_entry *
384 fat_get_fat32_cache_entry(struct fat_descriptor *fat, off_t addr,
388 struct fat32_cache_entry *entry, *first;
392 addr &= ~(fat32_cache_chunk_size - 1);
394 first = TAILQ_FIRST(&fat->fat32_cache_head);
397 * Cache hit: if we already have the chunk, move it to list head
399 TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) {
400 if (entry->addr == addr) {
404 if (entry != first) {
406 TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries);
407 TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries);
414 * Cache miss: detach the chunk at tail of list, overwrite with
415 * the located chunk, and populate with data from disk.
417 entry = TAILQ_LAST(&fat->fat32_cache_head, cachehead);
418 TAILQ_REMOVE(&fat->fat32_cache_head, entry, entries);
419 if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) {
423 rwsize = fat_get_iosize(fat, addr);
424 fat_addr = fat->fat32_offset + addr;
427 if (lseek(fd, fat_addr, SEEK_SET) != fat_addr ||
428 (size_t)read(fd, entry->chunk, rwsize) != rwsize) {
429 pfatal("Unable to read FAT");
435 TAILQ_INSERT_HEAD(&fat->fat32_cache_head, entry, entries);
440 static inline uint8_t *
441 fat_get_fat32_cached_ptr(struct fat_descriptor *fat, cl_t cl, bool writing)
444 struct fat32_cache_entry *entry;
447 entry = fat_get_fat32_cache_entry(fat, addr, writing);
450 off = addr & (fat32_cache_chunk_size - 1);
451 return (entry->chunk + off);
459 fat_get_fat32_cached_next(struct fat_descriptor *fat, cl_t cl)
464 p = fat_get_fat32_cached_ptr(fat, cl, false);
466 retval = le32dec(p) & CLUST32_MASK;
467 if (retval >= (CLUST_BAD & CLUST32_MASK))
468 retval |= ~CLUST32_MASK;
477 fat_set_fat32_cached_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
481 /* Truncate 'nextcl' value, if needed */
482 nextcl &= CLUST32_MASK;
484 p = fat_get_fat32_cached_ptr(fat, cl, true);
486 le32enc(p, (uint32_t)nextcl);
493 cl_t fat_get_cl_next(struct fat_descriptor *fat, cl_t cl)
496 if (!valid_cl(fat, cl)) {
497 pfatal("Invalid cluster: %ud", cl);
501 return (fat->get(fat, cl));
504 int fat_set_cl_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
508 pwarn(" (NO WRITE)\n");
512 if (!valid_cl(fat, cl)) {
513 pfatal("Invalid cluster: %ud", cl);
517 return (fat->set(fat, cl, nextcl));
520 static inline struct bootblock*
521 boot_of_(struct fat_descriptor *fat) {
527 fat_get_boot(struct fat_descriptor *fat) {
529 return (boot_of_(fat));
533 fd_of_(struct fat_descriptor *fat)
539 fat_get_fd(struct fat_descriptor * fat)
541 return (fd_of_(fat));
545 * Whether a cl is in valid data range.
548 fat_is_valid_cl(struct fat_descriptor *fat, cl_t cl)
551 return (valid_cl(fat, cl));
555 valid_cl(struct fat_descriptor *fat, cl_t cl)
557 const struct bootblock *boot = boot_of_(fat);
559 return (cl >= CLUST_FIRST && cl < boot->NumClusters);
563 * The first 2 FAT entries contain pseudo-cluster numbers with the following
566 * 31...... ........ ........ .......0
567 * rrrr1111 11111111 11111111 mmmmmmmm FAT32 entry 0
568 * rrrrsh11 11111111 11111111 11111xxx FAT32 entry 1
570 * 11111111 mmmmmmmm FAT16 entry 0
571 * sh111111 11111xxx FAT16 entry 1
574 * m = BPB media ID byte
575 * s = clean flag (1 = dismounted; 0 = still mounted)
576 * h = hard error flag (1 = ok; 0 = I/O error)
580 checkdirty(int fs, struct bootblock *boot)
587 if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK)
590 off = boot->bpbResSectors;
591 off *= boot->bpbBytesPerSec;
593 buffer = malloc(len = boot->bpbBytesPerSec);
594 if (buffer == NULL) {
595 perr("No space for FAT sectors (%zu)", len);
599 if (lseek(fs, off, SEEK_SET) != off) {
600 perr("Unable to read FAT");
604 if ((size_t)read(fs, buffer, boot->bpbBytesPerSec) !=
605 boot->bpbBytesPerSec) {
606 perr("Unable to read FAT");
611 * If we don't understand the FAT, then the file system must be
612 * assumed to be unclean.
614 if (buffer[0] != boot->bpbMedia || buffer[1] != 0xff)
616 if (boot->ClustMask == CLUST16_MASK) {
617 if ((buffer[2] & 0xf8) != 0xf8 || (buffer[3] & 0x3f) != 0x3f)
620 if (buffer[2] != 0xff || (buffer[3] & 0x0f) != 0x0f
621 || (buffer[4] & 0xf8) != 0xf8 || buffer[5] != 0xff
622 || buffer[6] != 0xff || (buffer[7] & 0x03) != 0x03)
627 * Now check the actual clean flag (and the no-error flag).
629 if (boot->ClustMask == CLUST16_MASK) {
630 if ((buffer[3] & 0xc0) == 0xc0)
633 if ((buffer[7] & 0x0c) == 0x0c)
643 cleardirty(struct fat_descriptor *fat)
645 int fd, ret = FSERROR;
646 struct bootblock *boot;
651 boot = boot_of_(fat);
654 if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK)
657 off = boot->bpbResSectors;
658 off *= boot->bpbBytesPerSec;
660 buffer = malloc(len = boot->bpbBytesPerSec);
661 if (buffer == NULL) {
662 perr("No memory for FAT sectors (%zu)", len);
666 if ((size_t)pread(fd, buffer, len, off) != len) {
667 perr("Unable to read FAT");
671 if (boot->ClustMask == CLUST16_MASK) {
677 if ((size_t)pwrite(fd, buffer, len, off) != len) {
678 perr("Unable to write FAT");
690 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
693 _readfat(struct fat_descriptor *fat)
699 struct bootblock *boot;
700 struct fat32_cache_entry *entry;
702 boot = boot_of_(fat);
704 fat->fatsize = boot->FATsecs * boot->bpbBytesPerSec;
706 off = boot->bpbResSectors;
707 off *= boot->bpbBytesPerSec;
709 fat->is_mmapped = false;
710 fat->use_cache = false;
712 /* Attempt to mmap() first */
714 fat->fatbuf = mmap(NULL, fat->fatsize,
715 PROT_READ | (rdonly ? 0 : PROT_WRITE),
716 MAP_SHARED, fd_of_(fat), off);
717 if (fat->fatbuf != MAP_FAILED) {
718 fat->is_mmapped = true;
724 * Unfortunately, we were unable to mmap().
726 * Only use the cache manager when it's necessary, that is,
727 * when the FAT is sufficiently large; in that case, only
728 * read in the first 4 MiB of FAT into memory, and split the
729 * buffer into chunks and insert to the LRU queue to populate
730 * the cache with data.
732 if (boot->ClustMask == CLUST32_MASK &&
733 fat->fatsize >= fat32_cache_size) {
734 readsize = fat32_cache_size;
735 fat->use_cache = true;
737 fat->fat32_offset = boot->bpbResSectors * boot->bpbBytesPerSec;
738 fat->fat32_lastaddr = fat->fatsize & ~(fat32_cache_chunk_size);
740 readsize = fat->fatsize;
742 fat->fatbuf = malloc(readsize);
743 if (fat->fatbuf == NULL) {
744 perr("No space for FAT (%zu)", readsize);
748 if (lseek(fd, off, SEEK_SET) != off) {
749 perr("Unable to read FAT");
752 if ((size_t)read(fd, fat->fatbuf, readsize) != readsize) {
753 perr("Unable to read FAT");
758 * When cache is used, split the buffer into chunks, and
759 * connect the buffer into the cache.
761 if (fat->use_cache) {
762 TAILQ_INIT(&fat->fat32_cache_head);
763 entry = calloc(fat32_cache_entries, sizeof(*entry));
765 perr("No space for FAT cache (%zu of %zu)",
766 fat32_cache_entries, sizeof(entry));
769 for (i = 0; i < fat32_cache_entries; i++) {
770 entry[i].addr = fat32_cache_chunk_size * i;
771 entry[i].chunk = &fat->fatbuf[entry[i].addr];
772 TAILQ_INSERT_TAIL(&fat->fat32_cache_head,
775 fat->fat32_cache_allentries = entry;
787 releasefat(struct fat_descriptor *fat)
789 if (fat->is_mmapped) {
790 munmap(fat->fatbuf, fat->fatsize);
792 if (fat->use_cache) {
793 free(fat->fat32_cache_allentries);
794 fat->fat32_cache_allentries = NULL;
799 bitmap_dtor(&fat->headbitmap);
803 * Read or map a FAT and populate head bitmap
806 readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
808 struct fat_descriptor *fat;
813 boot->NumFree = boot->NumBad = 0;
815 fat = calloc(1, sizeof(struct fat_descriptor));
817 perr("No space for FAT descriptor");
824 if (!_readfat(fat)) {
828 buffer = fat->fatbuf;
830 /* Populate accessors */
831 switch(boot->ClustMask) {
833 fat->get = fat_get_fat12_next;
834 fat->set = fat_set_fat12_next;
837 fat->get = fat_get_fat16_next;
838 fat->set = fat_set_fat16_next;
841 if (fat->is_mmapped || !fat->use_cache) {
842 fat->get = fat_get_fat32_next;
843 fat->set = fat_set_fat32_next;
845 fat->get = fat_get_fat32_cached_next;
846 fat->set = fat_set_fat32_cached_next;
850 pfatal("Invalid ClustMask: %d", boot->ClustMask);
856 if (bitmap_ctor(&fat->headbitmap, boot->NumClusters,
858 perr("No space for head bitmap for FAT clusters (%zu)",
859 (size_t)boot->NumClusters);
865 if (buffer[0] != boot->bpbMedia
866 || buffer[1] != 0xff || buffer[2] != 0xff
867 || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
868 || (boot->ClustMask == CLUST32_MASK
869 && ((buffer[3]&0x0f) != 0x0f
870 || buffer[4] != 0xff || buffer[5] != 0xff
871 || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
873 /* Windows 95 OSR2 (and possibly any later) changes
874 * the FAT signature to 0xXXffff7f for FAT16 and to
875 * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
876 * file system is dirty if it doesn't reboot cleanly.
877 * Check this special condition before errorring out.
879 if (buffer[0] == boot->bpbMedia && buffer[1] == 0xff
881 && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
882 || (boot->ClustMask == CLUST32_MASK
883 && buffer[3] == 0x0f && buffer[4] == 0xff
884 && buffer[5] == 0xff && buffer[6] == 0xff
885 && buffer[7] == 0x07)))
888 /* just some odd byte sequence in FAT */
890 switch (boot->ClustMask) {
892 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
893 "FAT starts with odd byte sequence",
894 buffer[0], buffer[1], buffer[2], buffer[3],
895 buffer[4], buffer[5], buffer[6], buffer[7]);
898 pwarn("%s (%02x%02x%02x%02x)\n",
899 "FAT starts with odd byte sequence",
900 buffer[0], buffer[1], buffer[2], buffer[3]);
903 pwarn("%s (%02x%02x%02x)\n",
904 "FAT starts with odd byte sequence",
905 buffer[0], buffer[1], buffer[2]);
909 if (ask(1, "Correct")) {
913 *p++ = (u_char)boot->bpbMedia;
916 switch (boot->ClustMask) {
935 * Traverse the FAT table and populate head map. Initially, we
936 * consider all clusters as possible head cluster (beginning of
937 * a file or directory), and traverse the whole allocation table
938 * by marking every non-head nodes as such (detailed below) and
939 * fix obvious issues while we walk.
941 * For each "next" cluster, the possible values are:
943 * a) CLUST_FREE or CLUST_BAD. The *current* cluster can't be a
945 * b) An out-of-range value. The only fix would be to truncate at
947 * c) A valid cluster. It means that cluster (nextcl) is not a
948 * head cluster. Note that during the scan, every cluster is
949 * expected to be seen for at most once, and when we saw them
950 * twice, it means a cross-linked chain which should be
951 * truncated at the current cluster.
953 * After scan, the remaining set bits indicates all possible
954 * head nodes, because they were never claimed by any other
955 * node as the next node, but we do not know if these chains
956 * would end with a valid EOF marker. We will check that in
957 * checkchain() at a later time when checking directories,
958 * where these head nodes would be marked as non-head.
960 * In the final pass, all head nodes should be cleared, and if
961 * there is still head nodes, these would be leaders of lost
964 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
965 nextcl = fat_get_cl_next(fat, cl);
967 /* Check if the next cluster number is valid */
968 if (nextcl == CLUST_FREE) {
969 /* Save a hint for next free cluster */
970 if (boot->FSNext == 0) {
973 if (fat_is_cl_head(fat, cl)) {
974 fat_clear_cl_head(fat, cl);
977 } else if (nextcl == CLUST_BAD) {
978 if (fat_is_cl_head(fat, cl)) {
979 fat_clear_cl_head(fat, cl);
982 } else if (!valid_cl(fat, nextcl) && nextcl < CLUST_RSRVD) {
983 pwarn("Cluster %u continues with out of range "
984 "cluster number %u\n",
986 nextcl & boot->ClustMask);
987 if (ask(0, "Truncate")) {
988 ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
991 } else if (valid_cl(fat, nextcl)) {
992 if (fat_is_cl_head(fat, nextcl)) {
993 fat_clear_cl_head(fat, nextcl);
995 pwarn("Cluster %u crossed another chain at %u\n",
997 if (ask(0, "Truncate")) {
998 ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
1006 if (ret & FSFATAL) {
1016 * Get type of reserved cluster
1019 rsrvdcltype(cl_t cl)
1021 if (cl == CLUST_FREE)
1031 * Examine a cluster chain for errors and count its size.
1034 checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
1036 cl_t prev_cl, current_cl, next_cl;
1040 * We expect that the caller to give us a real, unvisited 'head'
1041 * cluster, and it must be a valid cluster. While scanning the
1042 * FAT table, we already excluded all clusters that was claimed
1043 * as a "next" cluster. Assert all the three conditions.
1045 assert(valid_cl(fat, head));
1046 assert(fat_is_cl_head(fat, head));
1049 * Immediately mark the 'head' cluster that we are about to visit.
1051 fat_clear_cl_head(fat, head);
1054 * The allocation of a non-zero sized file or directory is
1055 * represented as a singly linked list, and the tail node
1056 * would be the EOF marker (>=CLUST_EOFS).
1058 * With a valid head node at hand, we expect all subsequent
1059 * cluster to be either a not yet seen and valid cluster (we
1060 * would continue counting), or the EOF marker (we conclude
1061 * the scan of this chain).
1063 * For all other cases, the chain is invalid, and the only
1064 * viable fix would be to truncate at the current node (mark
1065 * it as EOF) when the next node violates that.
1068 prev_cl = current_cl = head;
1069 for (next_cl = fat_get_cl_next(fat, current_cl);
1070 valid_cl(fat, next_cl);
1071 prev_cl = current_cl, current_cl = next_cl, next_cl = fat_get_cl_next(fat, current_cl))
1075 if (next_cl >= CLUST_EOFS) {
1081 * The chain ended with an out-of-range cluster number.
1083 * If the current node is e.g. CLUST_FREE, CLUST_BAD, etc.,
1084 * it should not be present in a chain and we has to truncate
1085 * at the previous node.
1087 * If the current cluster points to an invalid cluster, the
1088 * current cluster might have useful data and we truncate at
1089 * the current cluster instead.
1091 if (next_cl == CLUST_FREE || next_cl >= CLUST_RSRVD) {
1092 pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
1093 head, rsrvdcltype(next_cl));
1094 current_cl = prev_cl;
1096 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
1098 next_cl & boot_of_(fat)->ClustMask);
1102 if (*chainsize > 0) {
1104 next_cl = CLUST_EOF;
1107 next_cl = CLUST_FREE;
1109 if (ask(0, "%s", op)) {
1110 return (fat_set_cl_next(fat, current_cl, next_cl) | FSFATMOD);
1117 * Clear cluster chain from head.
1120 clearchain(struct fat_descriptor *fat, cl_t head)
1122 cl_t current_cl, next_cl;
1123 struct bootblock *boot = boot_of_(fat);
1127 while (valid_cl(fat, current_cl)) {
1128 next_cl = fat_get_cl_next(fat, current_cl);
1129 (void)fat_set_cl_next(fat, current_cl, CLUST_FREE);
1131 current_cl = next_cl;
1137 * Overwrite the n-th FAT with FAT0
1140 copyfat(struct fat_descriptor *fat, int n)
1142 size_t rwsize, tailsize, blobs, i;
1143 off_t dst_off, src_off;
1144 struct bootblock *boot;
1149 boot = boot_of_(fat);
1151 blobs = howmany(fat->fatsize, fat32_cache_size);
1152 tailsize = fat->fatsize % fat32_cache_size;
1153 if (tailsize == 0) {
1154 tailsize = fat32_cache_size;
1156 rwsize = fat32_cache_size;
1158 src_off = fat->fat32_offset;
1159 dst_off = boot->bpbResSectors + n * boot->FATsecs;
1160 dst_off *= boot->bpbBytesPerSec;
1162 for (i = 0; i < blobs;
1163 i++, src_off += fat32_cache_size, dst_off += fat32_cache_size) {
1164 if (i == blobs - 1) {
1167 if ((lseek(fd, src_off, SEEK_SET) != src_off ||
1168 (size_t)read(fd, fat->fatbuf, rwsize) != rwsize) &&
1170 perr("Unable to read FAT0");
1174 if ((lseek(fd, dst_off, SEEK_SET) != dst_off ||
1175 (size_t)write(fd, fat->fatbuf, rwsize) != rwsize) &&
1177 perr("Unable to write FAT %d", n);
1188 writefat(struct fat_descriptor *fat)
1194 struct bootblock *boot;
1195 struct fat32_cache_entry *entry;
1197 boot = boot_of_(fat);
1200 if (fat->use_cache) {
1202 * Attempt to flush all in-flight cache, and bail out
1203 * if we encountered an error (but only emit error
1204 * message once). Stop proceeding with copyfat()
1205 * if any flush failed.
1207 TAILQ_FOREACH(entry, &fat->fat32_cache_head, entries) {
1208 if (fat_flush_fat32_cache_entry(fat, entry) != FSOK) {
1210 perr("Unable to write FAT");
1218 /* Update backup copies of FAT, error is not fatal */
1219 for (i = 1; i < boot->bpbFATs; i++) {
1220 if (copyfat(fat, i) != FSOK)
1224 writesz = fat->fatsize;
1226 for (i = fat->is_mmapped ? 1 : 0; i < boot->bpbFATs; i++) {
1227 dst_base = boot->bpbResSectors + i * boot->FATsecs;
1228 dst_base *= boot->bpbBytesPerSec;
1229 if ((lseek(fd, dst_base, SEEK_SET) != dst_base ||
1230 (size_t)write(fd, fat->fatbuf, writesz) != writesz) &&
1232 perr("Unable to write FAT %d", i);
1233 ret = ((i == 0) ? FSFATAL : FSERROR);
1242 * Check a complete in-memory FAT for lost cluster chains
1245 checklost(struct fat_descriptor *fat)
1250 size_t chains, chainlength;
1251 struct bootblock *boot;
1253 dosfs = fd_of_(fat);
1254 boot = boot_of_(fat);
1257 * At this point, we have already traversed all directories.
1258 * All remaining chain heads in the bitmap are heads of lost
1261 chains = fat_get_head_count(fat);
1262 for (head = CLUST_FIRST;
1263 chains > 0 && head < boot->NumClusters;
1266 * We expect the bitmap to be very sparse, so skip if
1267 * the range is full of 0's
1269 if (head % LONG_BIT == 0 &&
1270 !fat_is_cl_head_in_range(fat, head)) {
1274 if (fat_is_cl_head(fat, head)) {
1275 ret = checkchain(fat, head, &chainlength);
1276 if (ret != FSERROR && chainlength > 0) {
1277 pwarn("Lost cluster chain at cluster %u\n"
1278 "%zd Cluster(s) lost\n",
1280 mod |= ret = reconnect(fat, head,
1285 if (ret == FSERROR && ask(0, "Clear")) {
1286 clearchain(fat, head);
1296 if (boot->bpbFSInfo) {
1298 if (boot->FSFree != 0xffffffffU &&
1299 boot->FSFree != boot->NumFree) {
1300 pwarn("Free space in FSInfo block (%u) not correct (%u)\n",
1301 boot->FSFree, boot->NumFree);
1302 if (ask(1, "Fix")) {
1303 boot->FSFree = boot->NumFree;
1307 if (boot->FSNext != 0xffffffffU &&
1308 (boot->FSNext >= boot->NumClusters ||
1309 (boot->NumFree && fat_get_cl_next(fat, boot->FSNext) != CLUST_FREE))) {
1310 pwarn("Next free cluster in FSInfo block (%u) %s\n",
1312 (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
1314 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
1315 if (fat_get_cl_next(fat, head) == CLUST_FREE) {
1316 boot->FSNext = head;
1322 mod |= writefsinfo(dosfs, boot);