Revert r356249 for now as it broke GCC builds.

7 files changed, 638 insertions, 1217 deletions

diff --git a/sbin/fsck_msdosfs/boot.c b/sbin/fsck_msdosfs/boot.c
index a3ba7abccb9a..61920e68af52 100644
--- a/sbin/fsck_msdosfs/boot.c
+++ b/sbin/fsck_msdosfs/boot.c
@@ -152,6 +152,9 @@ readboot(int dosfs, struct bootblock *boot)
 		boot->NumSectors = boot->bpbHugeSectors;
 	}
 
+
+
+
 	if (boot->flags & FAT32) {
 		/* If the OEM Name field is EXFAT, it's not FAT32, so bail */
 		if (!memcmp(&block[3], "EXFAT   ", 8)) {
@@ -269,30 +272,13 @@ readboot(int dosfs, struct bootblock *boot)
 	boot->NumClusters = (boot->NumSectors - boot->FirstCluster) / boot->bpbSecPerClust +
 	    CLUST_FIRST;
 
-	if (boot->flags & FAT32) {
-		if (boot->NumClusters > (CLUST_RSRVD & CLUST32_MASK)) {
-			pfatal("Filesystem too big (%u clusters) for FAT32 partition",
-			    boot->NumClusters);
-			return FSFATAL;
-		}
-		if (boot->NumClusters < (CLUST_RSRVD & CLUST16_MASK)) {
-			pfatal("Filesystem too small (%u clusters) for FAT32 partition",
-			    boot->NumClusters);
-			return FSFATAL;
-		}
+	if (boot->flags & FAT32)
 		boot->ClustMask = CLUST32_MASK;
-
-		if (boot->bpbRootClust < CLUST_FIRST ||
-		    boot->bpbRootClust >= boot->NumClusters) {
-			pfatal("Root directory starts with cluster out of range(%u)",
-			       boot->bpbRootClust);
-			return FSFATAL;
-		}
-	} else if (boot->NumClusters < (CLUST_RSRVD&CLUST12_MASK)) {
+	else if (boot->NumClusters < (CLUST_RSRVD&CLUST12_MASK))
 		boot->ClustMask = CLUST12_MASK;
-	} else if (boot->NumClusters < (CLUST_RSRVD&CLUST16_MASK)) {
+	else if (boot->NumClusters < (CLUST_RSRVD&CLUST16_MASK))
 		boot->ClustMask = CLUST16_MASK;
-	} else {
+	else {
 		pfatal("Filesystem too big (%u clusters) for non-FAT32 partition",
 		       boot->NumClusters);
 		return FSFATAL;
diff --git a/sbin/fsck_msdosfs/check.c b/sbin/fsck_msdosfs/check.c
index 2c3866223a71..2431bd38dd66 100644
--- a/sbin/fsck_msdosfs/check.c
+++ b/sbin/fsck_msdosfs/check.c
@@ -47,8 +47,9 @@ checkfilesys(const char *fname)
 {
 	int dosfs;
 	struct bootblock boot;
-	struct fat_descriptor *fat = NULL;
+	struct fatEntry *fat = NULL;
 	int finish_dosdirsection=0;
+	u_int i;
 	int mod = 0;
 	int ret = 8;
 
@@ -87,39 +88,65 @@ checkfilesys(const char *fname)
 	}
 
 	if (!preen)  {
-		printf("** Phase 1 - Read FAT and checking connectivity\n");
+		if (boot.ValidFat < 0)
+			printf("** Phase 1 - Read and Compare FATs\n");
+		else
+			printf("** Phase 1 - Read FAT\n");
 	}
 
-	mod |= readfat(dosfs, &boot, &fat);
+	mod |= readfat(dosfs, &boot, boot.ValidFat >= 0 ? boot.ValidFat : 0, &fat);
 	if (mod & FSFATAL) {
 		close(dosfs);
 		return 8;
 	}
 
+	if (boot.ValidFat < 0)
+		for (i = 1; i < boot.bpbFATs; i++) {
+			struct fatEntry *currentFat;
+
+			mod |= readfat(dosfs, &boot, i, &currentFat);
+
+			if (mod & FSFATAL)
+				goto out;
+
+			mod |= comparefat(&boot, fat, currentFat, i);
+			free(currentFat);
+			if (mod & FSFATAL)
+				goto out;
+		}
+
+	if (!preen)
+		printf("** Phase 2 - Check Cluster Chains\n");
+
+	mod |= checkfat(&boot, fat);
+	if (mod & FSFATAL)
+		goto out;
+	/* delay writing FATs */
+
 	if (!preen)
-		printf("** Phase 2 - Checking Directories\n");
+		printf("** Phase 3 - Checking Directories\n");
 
-	mod |= resetDosDirSection(fat);
+	mod |= resetDosDirSection(&boot, fat);
 	finish_dosdirsection = 1;
 	if (mod & FSFATAL)
 		goto out;
 	/* delay writing FATs */
 
-	mod |= handleDirTree(fat);
+	mod |= handleDirTree(dosfs, &boot, fat);
 	if (mod & FSFATAL)
 		goto out;
 
 	if (!preen)
-		printf("** Phase 3 - Checking for Lost Files\n");
+		printf("** Phase 4 - Checking for Lost Files\n");
 
-	mod |= checklost(fat);
+	mod |= checklost(dosfs, &boot, fat);
 	if (mod & FSFATAL)
 		goto out;
 
 	/* now write the FATs */
-	if (mod & FSFATMOD) {
+	if (mod & (FSFATMOD|FSFIXFAT)) {
 		if (ask(1, "Update FATs")) {
-			mod |= writefat(fat);
+			mod |= writefat(dosfs, &boot, fat, mod & FSFIXFAT);
 			if (mod & FSFATAL)
 				goto out;
 		} else
@@ -143,7 +170,7 @@ checkfilesys(const char *fname)
 
 			if (mod & FSDIRTY) {
 				pwarn("MARKING FILE SYSTEM CLEAN\n");
-				mod |= writefat(fat);
+				mod |= writefat(dosfs, &boot, fat, 1);
 			} else {
 				pwarn("\n***** FILE SYSTEM IS LEFT MARKED AS DIRTY *****\n");
 				mod |= FSERROR; /* file system not clean */
diff --git a/sbin/fsck_msdosfs/dir.c b/sbin/fsck_msdosfs/dir.c
index 6bdc3b4d0f94..7e459c75d4ff 100644
--- a/sbin/fsck_msdosfs/dir.c
+++ b/sbin/fsck_msdosfs/dir.c
@@ -1,7 +1,6 @@
 /*-
  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
  *
- * Copyright (c) 2019 Google LLC
  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
  * Copyright (c) 1995 Martin Husemann
  * Some structure declaration borrowed from Paul Popelka
@@ -96,11 +95,14 @@ static struct dirTodoNode *newDirTodo(void);
 static void freeDirTodo(struct dirTodoNode *);
 static char *fullpath(struct dosDirEntry *);
 static u_char calcShortSum(u_char *);
-static int delete(struct fat_descriptor *, cl_t, int, cl_t, int, int);
-static int removede(struct fat_descriptor *, u_char *, u_char *,
-    cl_t, cl_t, cl_t, char *, int);
-static int checksize(struct fat_descriptor *, u_char *, struct dosDirEntry *);
-static int readDosDirSection(struct fat_descriptor *, struct dosDirEntry *);
+static int delete(int, struct bootblock *, struct fatEntry *, cl_t, int,
+    cl_t, int, int);
+static int removede(int, struct bootblock *, struct fatEntry *, u_char *,
+    u_char *, cl_t, cl_t, cl_t, char *, int);
+static int checksize(struct bootblock *, struct fatEntry *, u_char *,
+    struct dosDirEntry *);
+static int readDosDirSection(int, struct bootblock *, struct fatEntry *,
+    struct dosDirEntry *);
 
 /*
  * Manage free dosDirEntry structures.
@@ -114,7 +116,7 @@ newDosDirEntry(void)
 
 	if (!(de = freede)) {
 		if (!(de = malloc(sizeof *de)))
-			return (NULL);
+			return 0;
 	} else
 		freede = de->next;
 	return de;
@@ -191,7 +193,7 @@ fullpath(struct dosDirEntry *dir)
 /*
  * Calculate a checksum over an 8.3 alias name
  */
-static inline u_char
+static u_char
 calcShortSum(u_char *p)
 {
 	u_char sum = 0;
@@ -219,24 +221,21 @@ static struct dosDirEntry *lostDir;
  * Init internal state for a new directory scan.
  */
 int
-resetDosDirSection(struct fat_descriptor *fat)
+resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
 {
-	int rootdir_size, cluster_size;
+	int b1, b2;
 	int ret = FSOK;
 	size_t len;
-	struct bootblock *boot;
-
-	boot = fat_get_boot(fat);
 
-	rootdir_size = boot->bpbRootDirEnts * 32;
-	cluster_size = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+	b1 = boot->bpbRootDirEnts * 32;
+	b2 = boot->bpbSecPerClust * boot->bpbBytesPerSec;
 
-	if ((buffer = malloc(len = MAX(rootdir_size, cluster_size))) == NULL) {
+	if ((buffer = malloc(len = MAX(b1, b2))) == NULL) {
 		perr("No space for directory buffer (%zu)", len);
 		return FSFATAL;
 	}
 
-	if ((delbuf = malloc(len = cluster_size)) == NULL) {
+	if ((delbuf = malloc(len = b2)) == NULL) {
 		free(buffer);
 		perr("No space for directory delbuf (%zu)", len);
 		return FSFATAL;
@@ -251,10 +250,18 @@ resetDosDirSection(struct fat_descriptor *fat)
 
 	memset(rootDir, 0, sizeof *rootDir);
 	if (boot->flags & FAT32) {
-		if (!fat_is_cl_head(fat, boot->bpbRootClust)) {
+		if (boot->bpbRootClust < CLUST_FIRST ||
+		    boot->bpbRootClust >= boot->NumClusters) {
+			pfatal("Root directory starts with cluster out of range(%u)",
+			       boot->bpbRootClust);
+			return FSFATAL;
+		}
+		if (fat[boot->bpbRootClust].head != boot->bpbRootClust) {
 			pfatal("Root directory doesn't start a cluster chain");
 			return FSFATAL;
 		}
+
+		fat[boot->bpbRootClust].flags |= FAT_USED;
 		rootDir->head = boot->bpbRootClust;
 	}
 
@@ -295,21 +302,16 @@ finishDosDirSection(void)
  * Delete directory entries between startcl, startoff and endcl, endoff.
  */
 static int
-delete(struct fat_descriptor *fat, cl_t startcl,
+delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
     int startoff, cl_t endcl, int endoff, int notlast)
 {
 	u_char *s, *e;
 	off_t off;
-	int clsz, fd;
-	struct bootblock *boot;
-
-	boot = fat_get_boot(fat);
-	fd = fat_get_fd(fat);
-	clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+	int clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;
 
 	s = delbuf + startoff;
 	e = delbuf + clsz;
-	while (fat_is_valid_cl(fat, startcl)) {
+	while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
 		if (startcl == endcl) {
 			if (notlast)
 				break;
@@ -318,11 +320,11 @@ delete(struct fat_descriptor *fat, cl_t startcl,
 		off = (startcl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 
 		off *= boot->bpbBytesPerSec;
-		if (lseek(fd, off, SEEK_SET) != off) {
+		if (lseek(f, off, SEEK_SET) != off) {
 			perr("Unable to lseek to %" PRId64, off);
 			return FSFATAL;
 		}
-		if (read(fd, delbuf, clsz) != clsz) {
+		if (read(f, delbuf, clsz) != clsz) {
 			perr("Unable to read directory");
 			return FSFATAL;
 		}
@@ -330,26 +332,25 @@ delete(struct fat_descriptor *fat, cl_t startcl,
 			*s = SLOT_DELETED;
 			s += 32;
 		}
-		if (lseek(fd, off, SEEK_SET) != off) {
+		if (lseek(f, off, SEEK_SET) != off) {
 			perr("Unable to lseek to %" PRId64, off);
 			return FSFATAL;
 		}
-		if (write(fd, delbuf, clsz) != clsz) {
+		if (write(f, delbuf, clsz) != clsz) {
 			perr("Unable to write directory");
 			return FSFATAL;
 		}
 		if (startcl == endcl)
 			break;
-		startcl = fat_get_cl_next(fat, startcl);
+		startcl = fat[startcl].next;
 		s = delbuf;
 	}
 	return FSOK;
 }
 
 static int
-removede(struct fat_descriptor *fat, u_char *start,
-    u_char *end, cl_t startcl, cl_t endcl, cl_t curcl,
-    char *path, int type)
+removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
+    u_char *end, cl_t startcl, cl_t endcl, cl_t curcl, char *path, int type)
 {
 	switch (type) {
 	case 0:
@@ -365,14 +366,14 @@ removede(struct fat_descriptor *fat, u_char *start,
 	}
 	if (ask(0, "Remove")) {
 		if (startcl != curcl) {
-			if (delete(fat,
+			if (delete(f, boot, fat,
 				   startcl, start - buffer,
 				   endcl, end - buffer,
 				   endcl == curcl) == FSFATAL)
 				return FSFATAL;
 			start = buffer;
 		}
-		/* startcl is < CLUST_FIRST for !FAT32 root */
+		/* startcl is < CLUST_FIRST for !fat32 root */
 		if ((endcl == curcl) || (startcl < CLUST_FIRST))
 			for (; start < end; start += 32)
 				*start = SLOT_DELETED;
@@ -385,37 +386,23 @@ removede(struct fat_descriptor *fat, u_char *start,
  * Check an in-memory file entry
  */
 static int
-checksize(struct fat_descriptor *fat, u_char *p, struct dosDirEntry *dir)
+checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
+    struct dosDirEntry *dir)
 {
-	int ret = FSOK;
-	size_t physicalSize;
-	struct bootblock *boot;
-
-	boot = fat_get_boot(fat);
-
 	/*
 	 * Check size on ordinary files
 	 */
-	if (dir->head == CLUST_FREE) {
+	u_int32_t physicalSize;
+
+	if (dir->head == CLUST_FREE)
 		physicalSize = 0;
-	} else {
-		if (!fat_is_valid_cl(fat, dir->head))
+	else {
+		if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
 			return FSERROR;
-		ret = checkchain(fat, dir->head, &physicalSize);
-		/*
-		 * Upon return, physicalSize would hold the chain length
-		 * that checkchain() was able to validate, but if the user
-		 * refused the proposed repair, it would be unsafe to
-		 * proceed with directory entry fix, so bail out in that
-		 * case.
-		 */
-		if (ret == FSERROR) {
-			return (FSERROR);
-		}
-		physicalSize *= boot->ClusterSize;
+		physicalSize = fat[dir->head].length * boot->ClusterSize;
 	}
 	if (physicalSize < dir->size) {
-		pwarn("size of %s is %u, should at most be %zu\n",
+		pwarn("size of %s is %u, should at most be %u\n",
 		      fullpath(dir), dir->size, physicalSize);
 		if (ask(1, "Truncate")) {
 			dir->size = physicalSize;
@@ -435,10 +422,11 @@ checksize(struct fat_descriptor *fat, u_char *p, struct dosDirEntry *dir)
 
 			for (cl = dir->head, len = sz = 0;
 			    (sz += boot->ClusterSize) < dir->size; len++)
-				cl = fat_get_cl_next(fat, cl);
-			clearchain(fat, fat_get_cl_next(fat, cl));
-			ret = fat_set_cl_next(fat, cl, CLUST_EOF);
-			return (FSFATMOD | ret);
+				cl = fat[cl].next;
+			clearchain(boot, fat, fat[cl].next);
+			fat[cl].next = CLUST_EOF;
+			fat[dir->head].length = len;
+			return FSFATMOD;
 		} else
 			return FSERROR;
 	}
@@ -454,20 +442,15 @@ static const u_char dotdot_name[11] = "..         ";
  * when we traverse into it.
  */
 static int
-check_subdirectory(struct fat_descriptor *fat, struct dosDirEntry *dir)
+check_subdirectory(int f, struct bootblock *boot, struct dosDirEntry *dir)
 {
 	u_char *buf, *cp;
 	off_t off;
 	cl_t cl;
 	int retval = FSOK;
-	int fd;
-	struct bootblock *boot;
-
-	boot = fat_get_boot(fat);
-	fd = fat_get_fd(fat);
 
 	cl = dir->head;
-	if (dir->parent && !fat_is_valid_cl(fat, cl)) {
+	if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
 		return FSERROR;
 	}
 
@@ -491,8 +474,8 @@ check_subdirectory(struct fat_descriptor *fat, struct dosDirEntry *dir)
 	}
 
 	off *= boot->bpbBytesPerSec;
-	if (lseek(fd, off, SEEK_SET) != off ||
-	    read(fd, buf, boot->bpbBytesPerSec) != (ssize_t)boot->bpbBytesPerSec) {
+	if (lseek(f, off, SEEK_SET) != off ||
+	    read(f, buf, boot->bpbBytesPerSec) != (ssize_t)boot->bpbBytesPerSec) {
 		perr("Unable to read directory");
 		free(buf);
 		return FSFATAL;
@@ -526,27 +509,22 @@ check_subdirectory(struct fat_descriptor *fat, struct dosDirEntry *dir)
  *   - push directories onto the todo-stack
  */
 static int
-readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
+readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
+    struct dosDirEntry *dir)
 {
-	struct bootblock *boot;
 	struct dosDirEntry dirent, *d;
 	u_char *p, *vallfn, *invlfn, *empty;
 	off_t off;
-	int fd, i, j, k, iosize, entries;
-	bool is_legacyroot;
+	int i, j, k, last;
 	cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
 	char *t;
 	u_int lidx = 0;
 	int shortSum;
 	int mod = FSOK;
-	size_t dirclusters;
 #define	THISMOD	0x8000			/* Only used within this routine */
 
-	boot = fat_get_boot(fat);
-	fd = fat_get_fd(fat);
-
 	cl = dir->head;
-	if (dir->parent && (!fat_is_valid_cl(fat, cl))) {
+	if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
 		/*
 		 * Already handled somewhere else.
 		 */
@@ -554,50 +532,24 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 	}
 	shortSum = -1;
 	vallfn = invlfn = empty = NULL;
-
-	/*
-	 * If we are checking the legacy root (for FAT12/FAT16),
-	 * we will operate on the whole directory; otherwise, we
-	 * will operate on one cluster at a time, and also take
-	 * this opportunity to examine the chain.
-	 *
-	 * Derive how many entries we are going to encounter from
-	 * the I/O size.
-	 */
-	is_legacyroot = (dir->parent == NULL && !(boot->flags & FAT32));
-	if (is_legacyroot) {
-		iosize = boot->bpbRootDirEnts * 32;
-		entries = boot->bpbRootDirEnts;
-	} else {
-		iosize = boot->bpbSecPerClust * boot->bpbBytesPerSec;
-		entries = iosize / 32;
-		mod |= checkchain(fat, dir->head, &dirclusters);
-	}
-
 	do {
-		if (is_legacyroot) {
-			/*
-			 * Special case for FAT12/FAT16 root -- read
-			 * in the whole root directory.
-			 */
+		if (!(boot->flags & FAT32) && !dir->parent) {
+			last = boot->bpbRootDirEnts * 32;
 			off = boot->bpbResSectors + boot->bpbFATs *
 			    boot->FATsecs;
 		} else {
-			/*
-			 * Otherwise, read in a cluster of the
-			 * directory.
-			 */
+			last = boot->bpbSecPerClust * boot->bpbBytesPerSec;
 			off = (cl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 		}
 
 		off *= boot->bpbBytesPerSec;
-		if (lseek(fd, off, SEEK_SET) != off ||
-		    read(fd, buffer, iosize) != iosize) {
+		if (lseek(f, off, SEEK_SET) != off
+		    || read(f, buffer, last) != last) {
 			perr("Unable to read directory");
 			return FSFATAL;
 		}
-
-		for (p = buffer, i = 0; i < entries; i++, p += 32) {
+		last /= 32;
+		for (p = buffer, i = 0; i < last; i++, p += 32) {
 			if (dir->fsckflags & DIREMPWARN) {
 				*p = SLOT_EMPTY;
 				continue;
@@ -620,7 +572,7 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 						u_char *q;
 
 						dir->fsckflags &= ~DIREMPTY;
-						if (delete(fat,
+						if (delete(f, boot, fat,
 							   empcl, empty - buffer,
 							   cl, p - buffer, 1) == FSFATAL)
 							return FSFATAL;
@@ -749,7 +701,7 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 
 			if (dirent.flags & ATTR_VOLUME) {
 				if (vallfn || invlfn) {
-					mod |= removede(fat,
+					mod |= removede(f, boot, fat,
 							invlfn ? invlfn : vallfn, p,
 							invlfn ? invcl : valcl, -1, 0,
 							fullpath(dir), 2);
@@ -789,7 +741,7 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 			dirent.next = dir->child;
 
 			if (invlfn) {
-				mod |= k = removede(fat,
+				mod |= k = removede(f, boot, fat,
 						    invlfn, vallfn ? vallfn : p,
 						    invcl, vallfn ? valcl : cl, cl,
 						    fullpath(&dirent), 0);
@@ -805,61 +757,74 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 			vallfn = NULL; /* not used any longer */
 			invlfn = NULL;
 
-			/*
-			 * Check if the directory entry is sane.
-			 *
-			 * '.' and '..' are skipped, their sanity is
-			 * checked somewhere else.
-			 *
-			 * For everything else, check if we have a new,
-			 * valid cluster chain (beginning of a file or
-			 * directory that was never previously claimed
-			 * by another file) when it's a non-empty file
-			 * or a directory. The sanity of the cluster
-			 * chain is checked at a later time when we
-			 * traverse into the directory, or examine the
-			 * file's directory entry.
-			 *
-			 * The only possible fix is to delete the entry
-			 * if it's a directory; for file, we have to
-			 * truncate the size to 0.
-			 */
-			if (!(dirent.flags & ATTR_DIRECTORY) ||
-			    (strcmp(dirent.name, ".") != 0 &&
-			    strcmp(dirent.name, "..") != 0)) {
-				if ((dirent.size != 0 || (dirent.flags & ATTR_DIRECTORY)) &&
-				    ((!fat_is_valid_cl(fat, dirent.head) ||
-				    !fat_is_cl_head(fat, dirent.head)))) {
-					if (!fat_is_valid_cl(fat, dirent.head)) {
-						pwarn("%s starts with cluster out of range(%u)\n",
-						    fullpath(&dirent),
-						    dirent.head);
-					} else {
-						pwarn("%s doesn't start a new cluster chain\n",
-						    fullpath(&dirent));
-					}
-
-					if (dirent.flags & ATTR_DIRECTORY) {
-						if (ask(0, "Remove")) {
-							*p = SLOT_DELETED;
-							mod |= THISMOD|FSDIRMOD;
-						} else
-							mod |= FSERROR;
-						continue;
-					} else {
-						if (ask(1, "Truncate")) {
-							p[28] = p[29] = p[30] = p[31] = 0;
-							p[26] = p[27] = 0;
-							if (boot->ClustMask == CLUST32_MASK)
-								p[20] = p[21] = 0;
-							dirent.size = 0;
-							dirent.head = 0;
-							mod |= THISMOD|FSDIRMOD;
-						} else
-							mod |= FSERROR;
-					}
+			if (dirent.size == 0 && !(dirent.flags & ATTR_DIRECTORY)) {
+				if (dirent.head != 0) {
+					pwarn("%s has clusters, but size 0\n",
+					      fullpath(&dirent));
+					if (ask(1, "Drop allocated clusters")) {
+						p[26] = p[27] = 0;
+						if (boot->ClustMask == CLUST32_MASK)
+							p[20] = p[21] = 0;
+						clearchain(boot, fat, dirent.head);
+						dirent.head = 0;
+						mod |= THISMOD|FSDIRMOD|FSFATMOD;
+					} else
+						mod |= FSERROR;
+				}
+			} else if (dirent.head == 0
+				   && !strcmp(dirent.name, "..")
+				   && dir->parent			/* XXX */
+				   && !dir->parent->parent) {
+				/*
+				 *  Do nothing, the parent is the root
+				 */
+			} else if (dirent.head < CLUST_FIRST
+				   || dirent.head >= boot->NumClusters
+				   || fat[dirent.head].next == CLUST_FREE
+				   || (fat[dirent.head].next >= CLUST_RSRVD
+				       && fat[dirent.head].next < CLUST_EOFS)
+				   || fat[dirent.head].head != dirent.head) {
+				if (dirent.head == 0)
+					pwarn("%s has no clusters\n",
+					      fullpath(&dirent));
+				else if (dirent.head < CLUST_FIRST
+					 || dirent.head >= boot->NumClusters)
+					pwarn("%s starts with cluster out of range(%u)\n",
+					      fullpath(&dirent),
+					      dirent.head);
+				else if (fat[dirent.head].next == CLUST_FREE)
+					pwarn("%s starts with free cluster\n",
+					      fullpath(&dirent));
+				else if (fat[dirent.head].next >= CLUST_RSRVD)
+					pwarn("%s starts with cluster marked %s\n",
+					      fullpath(&dirent),
+					      rsrvdcltype(fat[dirent.head].next));
+				else
+					pwarn("%s doesn't start a cluster chain\n",
+					      fullpath(&dirent));
+				if (dirent.flags & ATTR_DIRECTORY) {
+					if (ask(0, "Remove")) {
+						*p = SLOT_DELETED;
+						mod |= THISMOD|FSDIRMOD;
+					} else
+						mod |= FSERROR;
+					continue;
+				} else {
+					if (ask(1, "Truncate")) {
+						p[28] = p[29] = p[30] = p[31] = 0;
+						p[26] = p[27] = 0;
+						if (boot->ClustMask == CLUST32_MASK)
+							p[20] = p[21] = 0;
+						dirent.size = 0;
+						mod |= THISMOD|FSDIRMOD;
+					} else
+						mod |= FSERROR;
 				}
 			}
+
+			if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
+				fat[dirent.head].flags |= FAT_USED;
+
 			if (dirent.flags & ATTR_DIRECTORY) {
 				/*
 				 * gather more info for directories
@@ -896,7 +861,8 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 							mod |= FSERROR;
 					}
 					continue;
-				} else if (strcmp(dirent.name, "..") == 0) {
+				}
+				if (strcmp(dirent.name, "..") == 0) {
 					if (dir->parent) {		/* XXX */
 						if (!dir->parent->parent) {
 							if (dirent.head) {
@@ -942,7 +908,7 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 						} else
 							mod |= FSERROR;
 						continue;
-					} else if ((check_subdirectory(fat,
+					} else if ((check_subdirectory(f, boot,
 					    &dirent) & FSERROR) == FSERROR) {
 						/*
 						 * A subdirectory should have
@@ -978,43 +944,39 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 				n->dir = d;
 				pendingDirectories = n;
 			} else {
-				mod |= k = checksize(fat, p, &dirent);
+				mod |= k = checksize(boot, fat, p, &dirent);
 				if (k & FSDIRMOD)
 					mod |= THISMOD;
 			}
 			boot->NumFiles++;
 		}
 
-		if (is_legacyroot) {
-			/*
-			 * Don't bother to write back right now because
-			 * we may continue to make modification to the
-			 * non-FAT32 root directory below.
-			 */
+		if (!(boot->flags & FAT32) && !dir->parent)
 			break;
-		} else if (mod & THISMOD) {
-			if (lseek(fd, off, SEEK_SET) != off
-			    || write(fd, buffer, iosize) != iosize) {
+
+		if (mod & THISMOD) {
+			last *= 32;
+			if (lseek(f, off, SEEK_SET) != off
+			    || write(f, buffer, last) != last) {
 				perr("Unable to write directory");
 				return FSFATAL;
 			}
 			mod &= ~THISMOD;
 		}
-	} while (fat_is_valid_cl(fat, (cl = fat_get_cl_next(fat, cl))));
+	} while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
 	if (invlfn || vallfn)
-		mod |= removede(fat,
+		mod |= removede(f, boot, fat,
 				invlfn ? invlfn : vallfn, p,
 				invlfn ? invcl : valcl, -1, 0,
 				fullpath(dir), 1);
 
-	/*
-	 * The root directory of non-FAT32 filesystems is in a special
-	 * area and may have been modified above removede() without
-	 * being written out.
+	/* The root directory of non fat32 filesystems is in a special
+	 * area and may have been modified above without being written out.
 	 */
-	if ((mod & FSDIRMOD) && is_legacyroot) {
-		if (lseek(fd, off, SEEK_SET) != off
-		    || write(fd, buffer, iosize) != iosize) {
+	if ((mod & FSDIRMOD) && !(boot->flags & FAT32) && !dir->parent) {
+		last *= 32;
+		if (lseek(f, off, SEEK_SET) != off
+		    || write(f, buffer, last) != last) {
 			perr("Unable to write directory");
 			return FSFATAL;
 		}
@@ -1024,11 +986,11 @@ readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 }
 
 int
-handleDirTree(struct fat_descriptor *fat)
+handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
 {
 	int mod;
 
-	mod = readDosDirSection(fat, rootDir);
+	mod = readDosDirSection(dosfs, boot, fat, rootDir);
 	if (mod & FSFATAL)
 		return FSFATAL;
 
@@ -1049,7 +1011,7 @@ handleDirTree(struct fat_descriptor *fat)
 		/*
 		 * handle subdirectory
 		 */
-		mod |= readDosDirSection(fat, dir);
+		mod |= readDosDirSection(dosfs, boot, fat, dir);
 		if (mod & FSFATAL)
 			return FSFATAL;
 	}
@@ -1065,15 +1027,12 @@ static cl_t lfcl;
 static off_t lfoff;
 
 int
-reconnect(struct fat_descriptor *fat, cl_t head, size_t length)
+reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
 {
-	struct bootblock *boot = fat_get_boot(fat);
 	struct dosDirEntry d;
-	int len, dosfs;
+	int len;
 	u_char *p;
 
-	dosfs = fat_get_fd(fat);
-
 	if (!ask(1, "Reconnect"))
 		return FSERROR;
 
@@ -1104,7 +1063,7 @@ reconnect(struct fat_descriptor *fat, cl_t head, size_t length)
 					break;
 		if (p && p < lfbuf + boot->ClusterSize)
 			break;
-		lfcl = p ? fat_get_cl_next(fat, lfcl) : lostDir->head;
+		lfcl = p ? fat[lfcl].next : lostDir->head;
 		if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
 			/* Extend LOSTDIR?				XXX */
 			pwarn("No space in %s\n", LOSTDIR);
@@ -1129,7 +1088,7 @@ reconnect(struct fat_descriptor *fat, cl_t head, size_t length)
 	len = snprintf(d.name, sizeof(d.name), "%u", head);
 	d.flags = 0;
 	d.head = head;
-	d.size = length * boot->ClusterSize;
+	d.size = fat[head].length * boot->ClusterSize;
 
 	memcpy(p, d.name, len);
 	memset(p + len, ' ', 11 - len);
@@ -1144,6 +1103,7 @@ reconnect(struct fat_descriptor *fat, cl_t head, size_t length)
 	p[29] = (u_char)(d.size >> 8);
 	p[30] = (u_char)(d.size >> 16);
 	p[31] = (u_char)(d.size >> 24);
+	fat[head].flags |= FAT_USED;
 	if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
 	    || (size_t)write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
 		perr("could not write LOST.DIR");
diff --git a/sbin/fsck_msdosfs/dosfs.h b/sbin/fsck_msdosfs/dosfs.h
index d89a08689825..9f1480f17b00 100644
--- a/sbin/fsck_msdosfs/dosfs.h
+++ b/sbin/fsck_msdosfs/dosfs.h
@@ -83,13 +83,19 @@ struct bootblock {
 	u_int	NumBad;			/* # of bad clusters */
 };
 
+struct fatEntry {
+	cl_t	next;			/* pointer to next cluster */
+	cl_t	head;			/* pointer to start of chain */
+	u_int32_t length;		/* number of clusters on chain */
+	int	flags;			/* see below */
+};
+
 #define	CLUST_FREE	0		/* 0 means cluster is free */
 #define	CLUST_FIRST	2		/* 2 is the minimum valid cluster number */
 #define	CLUST_RSRVD	0xfffffff6	/* start of reserved clusters */
 #define	CLUST_BAD	0xfffffff7	/* a cluster with a defect */
 #define	CLUST_EOFS	0xfffffff8	/* start of EOF indicators */
 #define	CLUST_EOF	0xffffffff	/* standard value for last cluster */
-#define	CLUST_DEAD	0xfdeadc0d	/* error encountered */
 
 /*
  * Masks for cluster values
@@ -98,6 +104,8 @@ struct bootblock {
 #define	CLUST16_MASK	0xffff
 #define	CLUST32_MASK	0xfffffff
 
+#define	FAT_USED	1		/* This fat chain is used in a file */
+
 #define	DOSLONGNAMELEN	256		/* long name maximal length */
 #define LRFIRST		0x40		/* first long name record */
 #define	LRNOMASK	0x1f		/* mask to extract long record
diff --git a/sbin/fsck_msdosfs/ext.h b/sbin/fsck_msdosfs/ext.h
index 6e9ba7f56b3a..ebc94677b9b3 100644
--- a/sbin/fsck_msdosfs/ext.h
+++ b/sbin/fsck_msdosfs/ext.h
@@ -32,8 +32,6 @@
 
 #include <sys/types.h>
 
-#include <stdbool.h>
-
 #include "dosfs.h"
 
 #define	LOSTDIR	"LOST.DIR"
@@ -46,7 +44,6 @@ extern int alwaysyes;	/* assume "yes" for all questions */
 extern int preen;	/* we are preening */
 extern int rdonly;	/* device is opened read only (supersedes above) */
 extern int skipclean;	/* skip clean file systems if preening */
-extern int allow_mmap;  /* allow the use of mmap() */
 
 /*
  * function declarations
@@ -75,6 +72,7 @@ int checkfilesys(const char *);
 #define	FSERROR		8		/* Some unrecovered error remains */
 #define	FSFATAL		16		/* Some unrecoverable error occurred */
 #define	FSDIRTY		32		/* File system is dirty */
+#define	FSFIXFAT	64		/* Fix file system FAT */
 
 /*
  * read a boot block in a machine independent fashion and translate
@@ -87,53 +85,46 @@ int readboot(int, struct bootblock *);
  */
 int writefsinfo(int, struct bootblock *);
 
-/* Opaque type */
-struct fat_descriptor;
-
-void fat_clear_cl_head(struct fat_descriptor *, cl_t);
-bool fat_is_cl_head(struct fat_descriptor *, cl_t);
-
-cl_t fat_get_cl_next(struct fat_descriptor *, cl_t);
-
-int fat_set_cl_next(struct fat_descriptor *, cl_t, cl_t);
-
-cl_t fat_allocate_cluster(struct fat_descriptor *fat);
+/*
+ * Read one of the FAT copies and return a pointer to the new
+ * allocated array holding our description of it.
+ */
+int readfat(int, struct bootblock *, u_int, struct fatEntry **);
 
-struct bootblock* fat_get_boot(struct fat_descriptor *);
-int fat_get_fd(struct fat_descriptor *);
-bool fat_is_valid_cl(struct fat_descriptor *, cl_t);
+/*
+ * Check two FAT copies for consistency and merge changes into the
+ * first if necessary.
+ */
+int comparefat(struct bootblock *, struct fatEntry *, struct fatEntry *, u_int);
 
 /*
- * Read the FAT 0 and return a pointer to the newly allocated
- * descriptor of it.
+ * Check a FAT
  */
-int readfat(int, struct bootblock *, struct fat_descriptor **);
+int checkfat(struct bootblock *, struct fatEntry *);
 
 /*
  * Write back FAT entries
  */
-int writefat(struct fat_descriptor *);
+int writefat(int, struct bootblock *, struct fatEntry *, int);
 
 /*
  * Read a directory
  */
-int resetDosDirSection(struct fat_descriptor *);
+int resetDosDirSection(struct bootblock *, struct fatEntry *);
 void finishDosDirSection(void);
-int handleDirTree(struct fat_descriptor *);
+int handleDirTree(int, struct bootblock *, struct fatEntry *);
 
 /*
  * Cross-check routines run after everything is completely in memory
  */
-int checkchain(struct fat_descriptor *, cl_t, size_t *);
-
 /*
  * Check for lost cluster chains
  */
-int checklost(struct fat_descriptor *);
+int checklost(int, struct bootblock *, struct fatEntry *);
 /*
  * Try to reconnect a lost cluster chain
  */
-int reconnect(struct fat_descriptor *, cl_t, size_t);
+int reconnect(int, struct bootblock *, struct fatEntry *, cl_t);
 void finishlf(void);
 
 /*
@@ -147,6 +138,6 @@ const char *rsrvdcltype(cl_t);
 /*
  * Clear a cluster chain in a FAT
  */
-void clearchain(struct fat_descriptor *, cl_t);
+void clearchain(struct bootblock *, struct fatEntry *, cl_t);
 
 #endif
diff --git a/sbin/fsck_msdosfs/fat.c b/sbin/fsck_msdosfs/fat.c
index 1fa2238bda29..7ca81ab115ef 100644
--- a/sbin/fsck_msdosfs/fat.c
+++ b/sbin/fsck_msdosfs/fat.c
@@ -1,7 +1,6 @@
 /*-
  * SPDX-License-Identifier: BSD-2-Clause
  *
- * Copyright (c) 2019 Google LLC
  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
  * Copyright (c) 1995 Martin Husemann
  *
@@ -34,14 +33,6 @@ 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>
@@ -51,517 +42,12 @@ static const char rcsid[] =
 #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 MAXPHYS (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 = MAXPHYS;
-static const size_t fat32_cache_size = 4 * 1024 * 1024;	/* 4MiB */
-static const size_t fat32_cache_entries = howmany(fat32_cache_size, fat32_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)MAXPHYS - 1));
-	} else {
-		return (MAXPHYS);
-	}
-}
-
-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) {
+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 **);
 
-	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:
  *
@@ -643,178 +129,93 @@ err:
 }
 
 /*
- * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
+ * Check a cluster number for valid value
  */
 static int
-_readfat(struct fat_descriptor *fat)
+checkclnum(struct bootblock *boot, u_int fat, cl_t cl, cl_t *next)
 {
-	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;
+	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;
 		}
+		return FSERROR;
 	}
+	return FSOK;
+}
 
-	/*
-	 * 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;
+/*
+ * 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;
 
-		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);
+	*buffer = calloc(boot->FATsecs, boot->bpbBytesPerSec);
+	if (*buffer == NULL) {
+		perr("No space for FAT sectors (%zu)",
+		    (size_t)boot->FATsecs);
 		return 0;
 	}
 
-	if (lseek(fd, off, SEEK_SET) != off) {
+	off = boot->bpbResSectors + no * boot->FATsecs;
+	off *= boot->bpbBytesPerSec;
+
+	if (lseek(fs, off, SEEK_SET) != off) {
 		perr("Unable to read FAT");
 		goto err;
 	}
-	if ((size_t)read(fd, fat->fatbuf, readsize) != readsize) {
+
+	if ((size_t)read(fs, *buffer, boot->FATsecs * boot->bpbBytesPerSec)
+	    != boot->FATsecs * boot->bpbBytesPerSec) {
 		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;
+    err:
+	free(*buffer);
 	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
+ * Read a FAT and decode it into internal format
  */
 int
-readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
+readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp)
 {
-	struct fat_descriptor *fat;
+	struct fatEntry *fat;
 	u_char *buffer, *p;
-	cl_t cl, nextcl;
+	cl_t cl;
 	int ret = FSOK;
 
 	boot->NumFree = boot->NumBad = 0;
 
-	fat = calloc(1, sizeof(struct fat_descriptor));
-	if (fat == NULL) {
-		perr("No space for FAT descriptor");
+	if (!_readfat(fs, boot, no, &buffer))
 		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)",
+	fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
+	if (fat == NULL) {
+		perr("No space for FAT clusters (%zu)",
 		    (size_t)boot->NumClusters);
-		releasefat(fat);
-		free(fat);
+		free(buffer);
 		return FSFATAL;
 	}
 
@@ -862,106 +263,54 @@ readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
 				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;
-				}
-			}
+			if (ask(1, "Correct"))
+				ret |= FSFIXFAT;
 		}
 	}
-
-	/*
-	 * 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;
-				}
-			}
+	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;
 		}
-
 	}
 
+	free(buffer);
 	if (ret & FSFATAL) {
-		releasefat(fat);
 		free(fat);
 		*fp = NULL;
 	} else
@@ -984,202 +333,332 @@ rsrvdcltype(cl_t cl)
 	return "bad";
 }
 
-/*
- * 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 {
+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;
+		}
 		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;
 }
 
 /*
- * Examine a cluster chain for errors and count its size.
+ * Compare two FAT copies in memory. Resolve any conflicts and merge them
+ * into the first one.
  */
 int
-checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
+comparefat(struct bootblock *boot, struct fatEntry *first,
+    struct fatEntry *second, u_int fatnum)
 {
-	cl_t current_cl, next_cl;
-
-	/*
-	 * 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;
-	}
+	cl_t cl;
+	int ret = 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));
+	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;
 }
 
-/*
- * Clear cluster chain from head.
- */
 void
-clearchain(struct fat_descriptor *fat, cl_t head)
+clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head)
 {
-	cl_t current_cl, next_cl;
-	struct bootblock *boot = boot_of_(fat);
-
-	current_cl = head;
+	cl_t p, q;
 
-	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;
+	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;
 	}
+}
 
+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;
 }
 
 /*
- * Overwrite the n-th FAT with FAT0
+ * Check a complete FAT in-memory for crosslinks
  */
-static int
-copyfat(struct fat_descriptor *fat, int n)
+int
+checkfat(struct bootblock *boot, struct fatEntry *fat)
 {
-	size_t	rwsize, tailsize, blobs, i;
-	off_t	dst_off, src_off;
-	struct bootblock *boot;
-	int ret, fd;
+	cl_t head, p, h, n;
+	u_int len;
+	int ret = 0;
+	int conf;
 
-	ret = FSOK;
-	fd = fd_of_(fat);
-	boot = boot_of_(fat);
+	/*
+	 * 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++;
+		}
 
-	blobs = howmany(fat->fatsize, fat32_cache_size);
-	tailsize = fat->fatsize % fat32_cache_size;
-	if (tailsize == 0) {
-		tailsize = fat32_cache_size;
+		/* the head record gets the length */
+		fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
 	}
-	rwsize = fat32_cache_size;
 
-	src_off = fat->fat32_offset;
-	dst_off = boot->bpbResSectors + n * boot->FATsecs;
-	dst_off *= boot->bpbBytesPerSec;
+	/*
+	 * 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;
 
-	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;
+		/* 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;
 		}
-		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;
+		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;
+		}
+		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;
 		}
+		ret |= conf;
 	}
-	return (ret);
+
+	return ret;
 }
 
 /*
- * Write out FAT
+ * Write out FATs encoding them from the internal format
  */
 int
-writefat(struct fat_descriptor *fat)
+writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
 {
+	u_char *buffer, *p;
+	cl_t cl;
 	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);
+	size_t fatsz;
+	off_t off;
+	int ret = FSOK;
 
-		/* Update backup copies of FAT, error is not fatal */
-		for (i = 1; i < boot->bpbFATs; i++) {
-			if (copyfat(fat, i) != FSOK)
-				ret = FSERROR;
+	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 {
-		writesz = fat->fatsize;
+		/* 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;
+		}
 
-		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);
-			}
+		if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0,
+					 &old_fat)) {
+			free(buffer);
+			return FSFATAL;
 		}
+
+		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;
+		}
+	}
+	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 */
+		}
+	}
+	free(buffer);
 	return ret;
 }
 
@@ -1187,55 +666,31 @@ writefat(struct fat_descriptor *fat)
  * Check a complete in-memory FAT for lost cluster chains
  */
 int
-checklost(struct fat_descriptor *fat)
+checklost(int dosfs, struct bootblock *boot, struct fatEntry *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;
+	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;
+
+		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;
 		}
-		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) {
@@ -1251,13 +706,13 @@ checklost(struct fat_descriptor *fat)
 		}
 		if (boot->FSNext != 0xffffffffU &&
 		    (boot->FSNext >= boot->NumClusters ||
-		    (boot->NumFree && fat_get_cl_next(fat, boot->FSNext) != CLUST_FREE))) {
+		    (boot->NumFree && fat[boot->FSNext].next != 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_get_cl_next(fat, head) == CLUST_FREE) {
+					if (fat[head].next == CLUST_FREE) {
 						boot->FSNext = head;
 						ret = 1;
 						break;
diff --git a/sbin/fsck_msdosfs/main.c b/sbin/fsck_msdosfs/main.c
index de54cd18eae7..6802afcefc46 100644
--- a/sbin/fsck_msdosfs/main.c
+++ b/sbin/fsck_msdosfs/main.c
@@ -48,7 +48,6 @@ int alwaysyes;		/* assume "yes" for all questions */
 int preen;		/* set when preening */
 int rdonly;		/* device is opened read only (supersedes above) */
 int skipclean;		/* skip clean file systems if preening */
-int allow_mmap;		/* Allow the use of mmap(), if possible */
 
 static void usage(void) __dead2;
 
@@ -69,8 +68,7 @@ main(int argc, char **argv)
 	int ch;
 
 	skipclean = 1;
-	allow_mmap = 1;
-	while ((ch = getopt(argc, argv, "CfFnpyM")) != -1) {
+	while ((ch = getopt(argc, argv, "CfFnpy")) != -1) {
 		switch (ch) {
 		case 'C': /* for fsck_ffs compatibility */
 			break;
@@ -100,10 +98,6 @@ main(int argc, char **argv)
 			preen = 1;
 			break;
 
-		case 'M':
-			allow_mmap = 0;
-			break;
-
 		default:
 			usage();
 			break;