Index: sbin/fsck_msdosfs/check.c
===================================================================
--- sbin/fsck_msdosfs/check.c
+++ sbin/fsck_msdosfs/check.c
@@ -47,9 +47,8 @@
 {
 	int dosfs;
 	struct bootblock boot;
-	struct fatEntry *fat = NULL;
+	struct fat_descriptor *fat = NULL;
 	int finish_dosdirsection=0;
-	u_int i;
 	int mod = 0;
 	int ret = 8;
 
@@ -88,44 +87,18 @@
 	}
 
 	if (!preen)  {
-		if (boot.ValidFat < 0)
-			printf("** Phase 1 - Read and Compare FATs\n");
-		else
-			printf("** Phase 1 - Read FAT\n");
+		printf("** Phase 1 - Read FAT\n");
 	}
 
-	mod |= readfat(dosfs, &boot, boot.ValidFat >= 0 ? boot.ValidFat : 0, &fat);
+	mod |= readfat(dosfs, &boot, &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");
+		printf("** Phase 2 - Checking Directories\n");
 
-	mod |= checkfat(&boot, fat);
-	if (mod & FSFATAL)
-		goto out;
-	/* delay writing FATs */
-
-	if (!preen)
-		printf("** Phase 3 - Checking Directories\n");
-
 	mod |= resetDosDirSection(&boot, fat);
 	finish_dosdirsection = 1;
 	if (mod & FSFATAL)
@@ -137,7 +110,7 @@
 		goto out;
 
 	if (!preen)
-		printf("** Phase 4 - Checking for Lost Files\n");
+		printf("** Phase 3 - Checking for Lost Files\n");
 
 	mod |= checklost(dosfs, &boot, fat);
 	if (mod & FSFATAL)
@@ -146,7 +119,7 @@
 	/* now write the FATs */
 	if (mod & (FSFATMOD|FSFIXFAT)) {
 		if (ask(1, "Update FATs")) {
-			mod |= writefat(dosfs, &boot, fat, mod & FSFIXFAT);
+			mod |= writefat(dosfs, &boot, fat);
 			if (mod & FSFATAL)
 				goto out;
 		} else
@@ -170,7 +143,7 @@
 
 			if (mod & FSDIRTY) {
 				pwarn("MARKING FILE SYSTEM CLEAN\n");
-				mod |= writefat(dosfs, &boot, fat, 1);
+				mod |= writefat(dosfs, &boot, fat);
 			} else {
 				pwarn("\n***** FILE SYSTEM IS LEFT MARKED AS DIRTY *****\n");
 				mod |= FSERROR; /* file system not clean */
Index: sbin/fsck_msdosfs/dir.c
===================================================================
--- sbin/fsck_msdosfs/dir.c
+++ sbin/fsck_msdosfs/dir.c
@@ -1,6 +1,7 @@
 /*-
  * 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
@@ -95,13 +96,13 @@
 static void freeDirTodo(struct dirTodoNode *);
 static char *fullpath(struct dosDirEntry *);
 static u_char calcShortSum(u_char *);
-static int delete(int, struct bootblock *, struct fatEntry *, cl_t, int,
+static int delete(int, struct bootblock *, struct fat_descriptor *, cl_t, int,
     cl_t, int, int);
-static int removede(int, struct bootblock *, struct fatEntry *, u_char *,
+static int removede(int, struct bootblock *, struct fat_descriptor *, u_char *,
     u_char *, cl_t, cl_t, cl_t, char *, int);
-static int checksize(struct bootblock *, struct fatEntry *, u_char *,
+static int checksize(struct bootblock *, struct fat_descriptor *, u_char *,
     struct dosDirEntry *);
-static int readDosDirSection(int, struct bootblock *, struct fatEntry *,
+static int readDosDirSection(int, struct bootblock *, struct fat_descriptor *,
     struct dosDirEntry *);
 
 /*
@@ -217,7 +218,7 @@
  * Init internal state for a new directory scan.
  */
 int
-resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
+resetDosDirSection(struct bootblock *boot, struct fat_descriptor *fat __unused)
 {
 	int b1, b2;
 	int ret = FSOK;
@@ -252,13 +253,18 @@
 			       boot->bpbRootClust);
 			return FSFATAL;
 		}
-		if (fat[boot->bpbRootClust].head != boot->bpbRootClust) {
+		if (!fat_is_cl_head(boot->bpbRootClust)) {
 			pfatal("Root directory doesn't start a cluster chain");
 			return FSFATAL;
 		}
-
-		fat[boot->bpbRootClust].flags |= FAT_USED;
+		/*
+		 * Mark the chain head as used, and remove it
+		 * from head bitmap because it's claimed by the
+		 * root directory.
+		 */
+		fat_set_cl_used(boot->bpbRootClust);
 		rootDir->head = boot->bpbRootClust;
+		fat_clear_cl_head(boot->bpbRootClust);
 	}
 
 	return ret;
@@ -298,7 +304,7 @@
  * Delete directory entries between startcl, startoff and endcl, endoff.
  */
 static int
-delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
+delete(int f, struct bootblock *boot, struct fat_descriptor *fat, cl_t startcl,
     int startoff, cl_t endcl, int endoff, int notlast)
 {
 	u_char *s, *e;
@@ -337,15 +343,16 @@
 		}
 		if (startcl == endcl)
 			break;
-		startcl = fat[startcl].next;
+		startcl = fat_get_cl_next(fat, startcl);
 		s = delbuf;
 	}
 	return FSOK;
 }
 
 static int
-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)
+removede(int f, struct bootblock *boot, struct fat_descriptor *fat,
+    u_char *start, u_char *end, cl_t startcl, cl_t endcl, cl_t curcl,
+    char *path, int type)
 {
 	switch (type) {
 	case 0:
@@ -368,7 +375,7 @@
 				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;
@@ -381,23 +388,26 @@
  * Check an in-memory file entry
  */
 static int
-checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
+checksize(struct bootblock *boot, struct fat_descriptor *fat, u_char *p,
     struct dosDirEntry *dir)
 {
+	int ret = FSOK;
+
 	/*
 	 * Check size on ordinary files
 	 */
-	u_int32_t physicalSize;
+	size_t physicalSize;
 
 	if (dir->head == CLUST_FREE)
 		physicalSize = 0;
 	else {
 		if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
 			return FSERROR;
-		physicalSize = fat[dir->head].length * boot->ClusterSize;
+		ret |= checkchain(fat, dir->head, &physicalSize);
+		physicalSize *= boot->ClusterSize;
 	}
 	if (physicalSize < dir->size) {
-		pwarn("size of %s is %u, should at most be %u\n",
+		pwarn("size of %s is %u, should at most be %zu\n",
 		      fullpath(dir), dir->size, physicalSize);
 		if (ask(1, "Truncate")) {
 			dir->size = physicalSize;
@@ -417,10 +427,9 @@
 
 			for (cl = dir->head, len = sz = 0;
 			    (sz += boot->ClusterSize) < dir->size; len++)
-				cl = fat[cl].next;
-			clearchain(boot, fat, fat[cl].next);
-			fat[cl].next = CLUST_EOF;
-			fat[dir->head].length = len;
+				cl = fat_get_cl_next(fat, cl);
+			clearchain(boot, fat, fat_get_cl_next(fat, cl));
+			fat_set_cl_next(fat, cl, CLUST_EOF);
 			return FSFATMOD;
 		} else
 			return FSERROR;
@@ -504,14 +513,14 @@
  *   - push directories onto the todo-stack
  */
 static int
-readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
+readDosDirSection(int f, struct bootblock *boot, struct fat_descriptor *fat,
     struct dosDirEntry *dir)
 {
 	struct dosDirEntry dirent, *d;
 	u_char *p, *vallfn, *invlfn, *empty;
 	off_t off;
 	int i, j, k, last;
-	cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
+	cl_t cl, dircl, valcl = ~0, invcl = ~0, empcl = ~0;
 	char *t;
 	u_int lidx = 0;
 	int shortSum;
@@ -752,74 +761,92 @@
 			vallfn = NULL; /* not used any longer */
 			invlfn = NULL;
 
-			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) {
+			if (dirent.flags & ATTR_DIRECTORY &&
+			    (strcmp(dirent.name, ".") == 0 ||
+			    strcmp(dirent.name, "..") == 0)) {
 				/*
-				 *  Do nothing, the parent is the root
+				 * These are already checked when scanning the parent,
+				 * so explicitly skip.
 				 */
-			} 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 (dirent.head >= CLUST_FIRST &&
+				    dirent.head < boot->NumClusters) {
+					dircl = fat_get_cl_next(fat,
+					    dirent.head);
 				} 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;
+					dircl = 0;
 				}
-			}
 
-			if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
-				fat[dirent.head].flags |= FAT_USED;
+				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
+					|| dircl == CLUST_FREE
+					|| (dircl >= CLUST_RSRVD && dircl < CLUST_EOFS)
+					|| (strcmp(dirent.name, ".") != 0 && !fat_is_cl_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 (dircl == CLUST_FREE)
+						pwarn("%s starts with free cluster\n",
+						fullpath(&dirent));
+					else if (dircl >= CLUST_RSRVD && dircl < CLUST_EOFS)
+						pwarn("%s starts with cluster marked %s\n",
+						fullpath(&dirent),
+						rsrvdcltype(dircl));
+					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;
+							dirent.head = 0;
+							mod |= THISMOD|FSDIRMOD;
+						} else
+							mod |= FSERROR;
+					}
+				}
 
+				if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters) {
+					fat_set_cl_used(dirent.head);
+					fat_clear_cl_head(dirent.head);
+				}
+			}
 			if (dirent.flags & ATTR_DIRECTORY) {
 				/*
 				 * gather more info for directories
@@ -958,7 +985,7 @@
 			}
 			mod &= ~THISMOD;
 		}
-	} while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
+	} while ((cl = fat_get_cl_next(fat, cl)) >= CLUST_FIRST && cl < boot->NumClusters);
 	if (invlfn || vallfn)
 		mod |= removede(f, boot, fat,
 				invlfn ? invlfn : vallfn, p,
@@ -981,7 +1008,7 @@
 }
 
 int
-handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
+handleDirTree(int dosfs, struct bootblock *boot, struct fat_descriptor *fat)
 {
 	int mod;
 
@@ -1022,8 +1049,9 @@
 static off_t lfoff;
 
 int
-reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
+reconnect(int dosfs, struct fat_descriptor *fat, cl_t head, size_t length)
 {
+	struct bootblock *boot = fat_get_boot(fat);
 	struct dosDirEntry d;
 	int len;
 	u_char *p;
@@ -1058,7 +1086,7 @@
 					break;
 		if (p && p < lfbuf + boot->ClusterSize)
 			break;
-		lfcl = p ? fat[lfcl].next : lostDir->head;
+		lfcl = p ? fat_get_cl_next(fat, lfcl) : lostDir->head;
 		if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
 			/* Extend LOSTDIR?				XXX */
 			pwarn("No space in %s\n", LOSTDIR);
@@ -1082,7 +1110,7 @@
 	len = snprintf(d.name, sizeof(d.name), "%u", head);
 	d.flags = 0;
 	d.head = head;
-	d.size = fat[head].length * boot->ClusterSize;
+	d.size = length * boot->ClusterSize;
 
 	memcpy(p, d.name, len);
 	memset(p + len, ' ', 11 - len);
@@ -1097,7 +1125,7 @@
 	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;
+	fat_set_cl_used(head);
 	if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
 	    || (size_t)write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
 		perr("could not write LOST.DIR");
Index: sbin/fsck_msdosfs/dosfs.h
===================================================================
--- sbin/fsck_msdosfs/dosfs.h
+++ sbin/fsck_msdosfs/dosfs.h
@@ -83,19 +83,13 @@
 	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
@@ -104,8 +98,6 @@
 #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
@@ -124,6 +116,7 @@
 	uint flags;			/* attributes */
 	cl_t head;			/* cluster no */
 	u_int32_t size;			/* filesize in bytes */
+	u_int32_t psize;		/* physical size in bytes */
 	uint fsckflags;			/* flags during fsck */
 };
 /* Flags in fsckflags: */
Index: sbin/fsck_msdosfs/ext.h
===================================================================
--- sbin/fsck_msdosfs/ext.h
+++ sbin/fsck_msdosfs/ext.h
@@ -32,6 +32,8 @@
 
 #include <sys/types.h>
 
+#include <stdbool.h>
+
 #include "dosfs.h"
 
 #define	LOSTDIR	"LOST.DIR"
@@ -85,46 +87,61 @@
  */
 int writefsinfo(int, struct bootblock *);
 
-/*
- * 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 **);
+/* Mark a cluster as used */
+void fat_set_cl_used(cl_t);
+void fat_clear_cl_used(cl_t cl);
 
+/* Whether a cluster is previously marked as used */
+bool fat_is_cl_used(cl_t);
+
+void fat_clear_cl_head(cl_t);
+bool fat_is_cl_head(cl_t);
+
+/* Opaque type */
+struct fat_descriptor;
+
+cl_t fat_get_cl_next(struct fat_descriptor *, cl_t);
+
+int fat_set_cl_next(struct fat_descriptor *, cl_t, cl_t);
+
+struct bootblock* fat_get_boot(struct fat_descriptor *);
+
 /*
- * Check two FAT copies for consistency and merge changes into the
- * first if necessary.
+ * Read the FAT 0 and return a pointer to the newly allocated
+ * descriptor of it.
  */
-int comparefat(struct bootblock *, struct fatEntry *, struct fatEntry *, u_int);
+int readfat(int, struct bootblock *, struct fat_descriptor **);
 
 /*
  * Check a FAT
  */
-int checkfat(struct bootblock *, struct fatEntry *);
+int checkfat(struct bootblock *, struct fat_descriptor *);
 
 /*
  * Write back FAT entries
  */
-int writefat(int, struct bootblock *, struct fatEntry *, int);
+int writefat(int, struct bootblock *, struct fat_descriptor *);
 
 /*
  * Read a directory
  */
-int resetDosDirSection(struct bootblock *, struct fatEntry *);
+int resetDosDirSection(struct bootblock *, struct fat_descriptor *);
 void finishDosDirSection(void);
-int handleDirTree(int, struct bootblock *, struct fatEntry *);
+int handleDirTree(int, struct bootblock *, struct fat_descriptor *);
 
 /*
  * 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(int, struct bootblock *, struct fatEntry *);
+int checklost(int, struct bootblock *, struct fat_descriptor *);
 /*
  * Try to reconnect a lost cluster chain
  */
-int reconnect(int, struct bootblock *, struct fatEntry *, cl_t);
+int reconnect(int, struct fat_descriptor *, cl_t, size_t);
 void finishlf(void);
 
 /*
@@ -138,6 +155,6 @@
 /*
  * Clear a cluster chain in a FAT
  */
-void clearchain(struct bootblock *, struct fatEntry *, cl_t);
+void clearchain(struct bootblock *, struct fat_descriptor *, cl_t);
 
 #endif
Index: sbin/fsck_msdosfs/fat.c
===================================================================
--- sbin/fsck_msdosfs/fat.c
+++ sbin/fsck_msdosfs/fat.c
@@ -1,6 +1,7 @@
 /*-
  * SPDX-License-Identifier: BSD-2-Clause
  *
+ * Copyright (c) 2019 Google LLC
  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
  * Copyright (c) 1995 Martin Husemann
  *
@@ -33,6 +34,13 @@
   "$FreeBSD$";
 #endif /* not lint */
 
+#include <sys/endian.h>
+#include <sys/limits.h>
+#include <sys/mman.h>
+#include <sys/param.h>
+
+#include <assert.h>
+#include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
@@ -42,12 +50,385 @@
 #include "ext.h"
 #include "fsutil.h"
 
-static int checkclnum(struct bootblock *, u_int, cl_t, cl_t *);
-static int clustdiffer(cl_t, cl_t *, cl_t *, u_int);
-static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *);
-static int _readfat(int, struct bootblock *, u_int, u_char **);
+static int _readfat(int, struct bootblock *, u_char **);
 
-/*-
+static bool is_mmapped;
+
+/*
+ * Used and head bitmaps 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 "used"
+ * (referenced by any file or directory), and another 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.
+ *
+ * Used bitmap
+ * ===========
+ * Initially, we set all bits to 0.  As we traverse the directory
+ * structure, we first check if the head cluster referenced by the
+ * directory entry was a head cluster, and if it was, we mark the
+ * whole chain as being used and clear the head map bit.
+ *
+ * The used bitmap have two purposes: first, we can immediately find
+ * out a cross chain because the node must have been already marked
+ * as used in a previous scan; second, if we do not care about lost
+ * chains, the data can immediately be used for clearing the unclaimed
+ * yet non-zero clusters from the FAT, similar to a "mark and sweep"
+ * garbage collection.
+ *
+ * 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 {
+	size_t		 count;
+	unsigned long	*map;
+} long_bitmap_t;
+static long_bitmap_t	usedbitmap;
+static long_bitmap_t	headbitmap;
+
+static inline void
+bitmap_set(long_bitmap_t *lbp, cl_t cl)
+{
+	cl_t i = cl / LONG_BIT;
+	unsigned long setbit = 1UL << (cl % LONG_BIT);
+
+	assert((lbp->map[i] & setbit) == 0);
+	lbp->map[i] |= setbit;
+	lbp->count++;
+
+}
+
+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;
+}
+
+void
+fat_set_cl_used(cl_t cl)
+{
+	bitmap_set(&usedbitmap, cl);
+}
+
+void
+fat_clear_cl_used(cl_t cl)
+{
+	bitmap_clear(&usedbitmap, cl);
+}
+
+bool
+fat_is_cl_used(cl_t cl)
+{
+	return (bitmap_get(&usedbitmap, cl));
+}
+
+void
+fat_clear_cl_head(cl_t cl)
+{
+	bitmap_clear(&headbitmap, cl);
+}
+
+bool
+fat_is_cl_head(cl_t cl)
+{
+	return (bitmap_get(&headbitmap, cl));
+}
+
+static inline bool
+fat_is_cl_head_in_range(cl_t cl)
+{
+	return (!(bitmap_none_in_range(&headbitmap, cl)));
+}
+
+static size_t
+fat_get_head_count(void)
+{
+	return (bitmap_count(&headbitmap));
+}
+
+/*
+ * FAT table descriptor, represents a FAT table that is already loaded
+ * into memory.
+ */
+struct fat_descriptor {
+	struct bootblock *boot;
+	size_t		  fatsize;
+	uint8_t		 *fatbuf;
+};
+
+/*
+ * FAT12 accessors.
+ *
+ * FAT12s are sufficiently small, expect it to always fit in the RAM.
+ */
+static 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 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.
+ *
+ * TODO(delphij): paging support
+ */
+static uint8_t *
+fat_get_fat32_ptr(struct fat_descriptor *fat, cl_t cl, bool write __unused)
+{
+	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, false);
+	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, true);
+
+	le32enc(p, (uint32_t)nextcl);
+
+	return (0);
+}
+
+/*
+ * Generic accessor interface for FAT
+ */
+cl_t fat_get_cl_next(struct fat_descriptor *fat, cl_t cl)
+{
+	cl_t retval = CLUST_DEAD;
+
+	if (cl < CLUST_FIRST || cl >= fat->boot->NumClusters) {
+		pfatal("Invalid cluster: %ud", cl);
+		return CLUST_DEAD;
+	}
+
+	switch (fat->boot->ClustMask) {
+	case CLUST12_MASK:
+		retval = fat_get_fat12_next(fat, cl);
+		break;
+	case CLUST16_MASK:
+		retval = fat_get_fat16_next(fat, cl);
+		break;
+	case CLUST32_MASK:
+		retval = fat_get_fat32_next(fat, cl);
+		break;
+	default:
+		pfatal("Invalid ClustMask: %d", fat->boot->ClustMask);
+		break;
+	}
+	return (retval);
+}
+
+int fat_set_cl_next(struct fat_descriptor *fat, cl_t cl, cl_t nextcl)
+{
+	int retval = FSFATAL;
+
+	if (rdonly) {
+		pwarn(" (NO WRITE)\n");
+		return FSFATAL;
+	}
+
+	if (cl < CLUST_FIRST || cl >= fat->boot->NumClusters) {
+		pfatal("Invalid cluster: %ud", cl);
+		return FSFATAL;
+	}
+
+	switch (fat->boot->ClustMask) {
+	case CLUST12_MASK:
+		retval = fat_set_fat12_next(fat, cl, nextcl);
+		break;
+	case CLUST16_MASK:
+		retval = fat_set_fat16_next(fat, cl, nextcl);
+		break;
+	case CLUST32_MASK:
+		retval = fat_set_fat32_next(fat, cl, nextcl);
+		break;
+	default:
+		pfatal("Invalid ClustMask: %d", fat->boot->ClustMask);
+		break;
+	}
+	return (retval);
+}
+
+struct bootblock*
+fat_get_boot(struct fat_descriptor *fat) {
+
+	return(fat->boot);
+}
+
+/*
  * The first 2 FAT entries contain pseudo-cluster numbers with the following
  * layout:
  *
@@ -129,61 +510,43 @@
 }
 
 /*
- * Check a cluster number for valid value
- */
-static int
-checkclnum(struct bootblock *boot, u_int fat, cl_t cl, cl_t *next)
-{
-	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;
-}
-
-/*
  * 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)
+_readfat(int fs, struct bootblock *boot, u_char **buffer)
 {
 	off_t off;
+	size_t fatsize;
 
-	*buffer = calloc(boot->FATsecs, boot->bpbBytesPerSec);
+	fatsize = boot->FATsecs * boot->bpbBytesPerSec;
+
+	off = boot->bpbResSectors;
+	off *= boot->bpbBytesPerSec;
+
+	is_mmapped = false;
+
+	/* Attempt to mmap() first */
+	*buffer = mmap(NULL, fatsize, PROT_READ | (rdonly ? 0 : PROT_WRITE),
+	    MAP_SHARED, fs, off);
+	if (*buffer != MAP_FAILED) {
+		is_mmapped = true;
+		return 1;
+	}
+
+	/* mmap failed, create a buffer and read in the FAT table */
+	*buffer = malloc(fatsize);
 	if (*buffer == NULL) {
 		perr("No space for FAT sectors (%zu)",
 		    (size_t)boot->FATsecs);
 		return 0;
 	}
 
-	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(fs, *buffer, boot->FATsecs * boot->bpbBytesPerSec)
-	    != boot->FATsecs * boot->bpbBytesPerSec) {
+	if ((size_t)read(fs, *buffer,fatsize) != fatsize) {
 		perr("Unable to read FAT");
 		goto err;
 	}
@@ -195,30 +558,60 @@
 	return 0;
 }
 
+static void
+releasefat(struct bootblock *boot, u_char **buffer)
+{
+	size_t fatsize;
+
+	if (is_mmapped) {
+		fatsize = boot->FATsecs * boot->bpbBytesPerSec;
+		munmap(*buffer, fatsize);
+	} else {
+		free(*buffer);
+	}
+	*buffer = NULL;
+}
+
 /*
- * Read a FAT and decode it into internal format
+ * Read or map a FAT and populate head bitmap
  */
 int
-readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp)
+readfat(int fs, struct bootblock *boot, struct fat_descriptor **fp)
 {
-	struct fatEntry *fat;
+	struct fat_descriptor *fat;
 	u_char *buffer, *p;
-	cl_t cl;
+	cl_t cl, nextcl;
 	int ret = FSOK;
 
 	boot->NumFree = boot->NumBad = 0;
 
-	if (!_readfat(fs, boot, no, &buffer))
+	if (!_readfat(fs, boot, &buffer))
 		return FSFATAL;
 
-	fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
+	fat = calloc(1, sizeof(struct fat_descriptor));
 	if (fat == NULL) {
-		perr("No space for FAT clusters (%zu)",
+		perr("No space for FAT descriptor");
+		releasefat(boot, &buffer);
+		return FSFATAL;
+	}
+
+	if (bitmap_ctor(&usedbitmap, boot->NumClusters, false) != FSOK) {
+		perr("No space for used bitmap for FAT clusters (%zu)",
 		    (size_t)boot->NumClusters);
-		free(buffer);
+		releasefat(boot, &buffer);
+		free(fat);
 		return FSFATAL;
 	}
 
+	if (bitmap_ctor(&headbitmap, boot->NumClusters, true) != FSOK) {
+		perr("No space for head bitmap for FAT clusters (%zu)",
+		    (size_t)boot->NumClusters);
+		bitmap_dtor(&usedbitmap);
+		releasefat(boot, &buffer);
+		free(fat);
+		return FSFATAL;
+	}
+
 	if (buffer[0] != boot->bpbMedia
 	    || buffer[1] != 0xff || buffer[2] != 0xff
 	    || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
@@ -263,54 +656,75 @@
 				break;
 			}
 
+			if (ask(1, "Correct")) {
+				p = buffer;
 
-			if (ask(1, "Correct"))
-				ret |= FSFIXFAT;
+				*p++ = (u_char)boot->bpbMedia;
+				*p++ = 0xff;
+				*p++ = 0xff;
+				switch (boot->ClustMask) {
+				case CLUST16_MASK:
+					*p++ = 0xff;
+					break;
+				case CLUST32_MASK:
+					*p++ = 0x0f;
+					*p++ = 0xff;
+					*p++ = 0xff;
+					*p++ = 0xff;
+					*p++ = 0x0f;
+					break;
+				default:
+					break;
+				}
+			}
 		}
 	}
-	switch (boot->ClustMask) {
-	case CLUST32_MASK:
-		p = buffer + 8;
-		break;
-	case CLUST16_MASK:
-		p = buffer + 4;
-		break;
-	default:
-		p = buffer + 3;
-		break;
-	}
-	for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
-		switch (boot->ClustMask) {
-		case CLUST32_MASK:
-			fat[cl].next = p[0] + (p[1] << 8)
-				       + (p[2] << 16) + (p[3] << 24);
-			fat[cl].next &= boot->ClustMask;
-			ret |= checkclnum(boot, no, cl, &fat[cl].next);
-			cl++;
-			p += 4;
-			break;
-		case CLUST16_MASK:
-			fat[cl].next = p[0] + (p[1] << 8);
-			ret |= checkclnum(boot, no, cl, &fat[cl].next);
-			cl++;
-			p += 2;
-			break;
-		default:
-			fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
-			ret |= checkclnum(boot, no, cl, &fat[cl].next);
-			cl++;
-			if (cl >= boot->NumClusters)
-				break;
-			fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
-			ret |= checkclnum(boot, no, cl, &fat[cl].next);
-			cl++;
-			p += 3;
-			break;
+
+	fat->fatbuf = buffer;
+	fat->boot = boot;
+
+	/* Traverse the FAT table and populate head map */
+	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) {
+			if (fat_is_cl_head(cl)) {
+				fat_clear_cl_head(cl);
+			}
+			boot->NumFree++;
+		} else if (nextcl == CLUST_BAD) {
+			if (fat_is_cl_head(cl)) {
+				fat_clear_cl_head(cl);
+			}
+			boot->NumBad++;
+		} else if (nextcl < CLUST_FIRST ||
+		    (nextcl >= boot->NumClusters && 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")) {
+				fat_set_cl_next(fat, cl, CLUST_EOF);
+				ret |= FSFATMOD;
+			}
+		} else if (nextcl < boot->NumClusters) {
+			if (fat_is_cl_head(nextcl)) {
+				fat_clear_cl_head(nextcl);
+			} else {
+				/*
+				 * We know cl have crossed another
+				 * chain that we have already visited.
+				 * Ignore this for now.
+				 */
+			}
 		}
+
 	}
 
-	free(buffer);
 	if (ret & FSFATAL) {
+		releasefat(boot, &buffer);
 		free(fat);
 		*fp = NULL;
 	} else
@@ -333,332 +747,99 @@
 	return "bad";
 }
 
-static int
-clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, u_int fatnum)
-{
-	if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
-		if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
-			if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
-			     && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD)
-			    || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) {
-				pwarn("Cluster %u is marked %s with different indicators\n",
-				      cl, rsrvdcltype(*cp1));
-				if (ask(1, "Fix")) {
-					*cp2 = *cp1;
-					return FSFATMOD;
-				}
-				return FSFATAL;
-			}
-			pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %u\n",
-			      cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
-			if (ask(0, "Use FAT 0's entry")) {
-				*cp2 = *cp1;
-				return FSFATMOD;
-			}
-			if (ask(0, "Use FAT %u's entry", fatnum)) {
-				*cp1 = *cp2;
-				return FSFATMOD;
-			}
-			return FSFATAL;
-		}
-		pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
-		      cl, rsrvdcltype(*cp1), *cp2, fatnum);
-		if (ask(0, "Use continuation from FAT %u", fatnum)) {
-			*cp1 = *cp2;
-			return FSFATMOD;
-		}
-		if (ask(0, "Use mark from FAT 0")) {
-			*cp2 = *cp1;
-			return FSFATMOD;
-		}
-		return FSFATAL;
-	}
-	if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
-		pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %u\n",
-		      cl, *cp1, rsrvdcltype(*cp2), fatnum);
-		if (ask(0, "Use continuation from FAT 0")) {
-			*cp2 = *cp1;
-			return FSFATMOD;
-		}
-		if (ask(0, "Use mark from FAT %d", fatnum)) {
-			*cp1 = *cp2;
-			return FSFATMOD;
-		}
-		return FSERROR;
-	}
-	pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %u\n",
-	      cl, *cp1, *cp2, fatnum);
-	if (ask(0, "Use continuation from FAT 0")) {
-		*cp2 = *cp1;
-		return FSFATMOD;
-	}
-	if (ask(0, "Use continuation from FAT %u", fatnum)) {
-		*cp1 = *cp2;
-		return FSFATMOD;
-	}
-	return FSERROR;
-}
-
 /*
- * Compare two FAT copies in memory. Resolve any conflicts and merge them
- * into the first one.
+ * Examine a cluster chain for errors
  */
 int
-comparefat(struct bootblock *boot, struct fatEntry *first,
-    struct fatEntry *second, u_int fatnum)
+checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
 {
-	cl_t cl;
-	int ret = FSOK;
+	cl_t current_cl, next_cl;
+	struct bootblock *boot = fat_get_boot(fat);
 
-	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;
-}
+	*chainsize = 0;
 
-void
-clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head)
-{
-	cl_t p, q;
-
-	for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
-		if (fat[p].head != head)
+	current_cl = head;
+	for (current_cl = head; ; current_cl = next_cl) {
+		next_cl = fat_get_cl_next(fat, current_cl);
+		if (next_cl < CLUST_FIRST || next_cl > boot->NumClusters)
 			break;
-		q = fat[p].next;
-		fat[p].next = fat[p].head = CLUST_FREE;
-		fat[p].length = 0;
+		if (fat_is_cl_used(next_cl)) {
+			/* We have seen this CL in somewhere else */
+			pwarn("Cluster %u crossed a chain at %u with %u\n",
+			    head, current_cl, next_cl);
+			if (ask(0, "Truncate")) {
+				fat_set_cl_next(fat, current_cl, CLUST_EOF);
+				return FSFATMOD;
+			} else {
+				return FSERROR;
+			}
+
+		}
+		(*chainsize)++;
+		fat_set_cl_used(next_cl);
 	}
-}
 
-int
-tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *truncp)
-{
-	if (ask(0, "Clear chain starting at %u", head)) {
-		clearchain(boot, fat, head);
-		return FSFATMOD;
-	} else if (ask(0, "Truncate")) {
-		uint32_t len;
-		cl_t p;
+	/* A natural end */
+	if (next_cl > CLUST_EOFS) {
+		(*chainsize)++;
+		return FSOK;
+	}
 
-		for (p = head, len = 0;
-		    p >= CLUST_FIRST && p < boot->NumClusters;
-		    p = fat[p].next, len++)
-			continue;
-		*truncp = CLUST_EOF;
-		fat[head].length = len;
+	pwarn("Cluster %u continues with %s cluster number %u\n",
+	    current_cl,
+	    next_cl < CLUST_RSRVD ? "out of range" : "reserved",
+	    next_cl & fat->boot->ClustMask);
+	if (ask(0, "Truncate")) {
+		fat_set_cl_next(fat, current_cl, CLUST_EOF);
+		(*chainsize)++;
 		return FSFATMOD;
-	} else
+	} else {
 		return FSERROR;
+	}
 }
 
 /*
- * Check a complete FAT in-memory for crosslinks
+ * Clear cluster chain from head.
  */
-int
-checkfat(struct bootblock *boot, struct fatEntry *fat)
+void
+clearchain(struct bootblock *boot, struct fat_descriptor *fat, cl_t head)
 {
-	cl_t head, p, h, n;
-	u_int len;
-	int ret = 0;
-	int conf;
+	cl_t current_cl, next_cl;
 
-	/*
-	 * 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++;
+	for (current_cl = head;
+	    current_cl >= CLUST_FIRST && current_cl < boot->NumClusters;
+	    current_cl = next_cl) {
+		next_cl = fat_get_cl_next(fat, current_cl);
+		fat_set_cl_next(fat, current_cl, CLUST_FREE);
+		boot->NumFree++;
+		if (fat_is_cl_used(current_cl)) {
+			fat_clear_cl_used(current_cl);
 		}
-
-		/* the head record gets the length */
-		fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
 	}
-
-	/*
-	 * 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;
-
-		/* 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 (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;
 }
 
 /*
- * Write out FATs encoding them from the internal format
+ * Write out FAT
  */
 int
-writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
+writefat(int fs, struct bootblock *boot, struct fat_descriptor *fat)
 {
-	u_char *buffer, *p;
-	cl_t cl;
 	u_int i;
 	size_t fatsz;
 	off_t off;
 	int ret = FSOK;
 
-	fatsz = boot->FATsecs * boot->bpbBytesPerSec;
-	buffer = calloc(boot->FATsecs, boot->bpbBytesPerSec);
-	if (buffer == NULL) {
-		perr("No space for FAT sectors (%zu)",
-		    (size_t)boot->FATsecs);
-		return FSFATAL;
-	}
-	boot->NumFree = 0;
-	p = buffer;
-	if (correct_fat) {
-		*p++ = (u_char)boot->bpbMedia;
-		*p++ = 0xff;
-		*p++ = 0xff;
-		switch (boot->ClustMask) {
-		case CLUST16_MASK:
-			*p++ = 0xff;
-			break;
-		case CLUST32_MASK:
-			*p++ = 0x0f;
-			*p++ = 0xff;
-			*p++ = 0xff;
-			*p++ = 0xff;
-			*p++ = 0x0f;
-			break;
-		}
-	} else {
-		/* use same FAT signature as the old FAT has */
-		int count;
-		u_char *old_fat;
-
-		switch (boot->ClustMask) {
-		case CLUST32_MASK:
-			count = 8;
-			break;
-		case CLUST16_MASK:
-			count = 4;
-			break;
-		default:
-			count = 3;
-			break;
-		}
-
-		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++) {
+	fatsz = fat->fatsize;
+	for (i = is_mmapped ? 1 : 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) {
+		    || (size_t)write(fs, fat->fatbuf, fatsz) != fatsz) {
 			perr("Unable to write FAT");
 			ret = FSFATAL; /* Return immediately?		XXX */
 		}
 	}
-	free(buffer);
+
 	return ret;
 }
 
@@ -666,31 +847,50 @@
  * Check a complete in-memory FAT for lost cluster chains
  */
 int
-checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
+checklost(int dosfs, struct bootblock *boot, struct fat_descriptor *fat)
 {
 	cl_t head;
 	int mod = FSOK;
 	int ret;
+	size_t chains, chainlength;
 
-	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))
+	/*
+	 * 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();
+	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(head)) {
+			head += LONG_BIT;
 			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(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(dosfs, fat, head,
+				    chainlength);
+			}
+			if (mod & FSFATAL)
+				break;
+			if (ret == FSERROR && ask(0, "Clear")) {
+				clearchain(boot, fat, head);
+				mod |= FSFATMOD;
+			}
+			chains--;
+		}
+		head++;
 	}
+
 	finishlf();
 
 	if (boot->bpbFSInfo) {
@@ -706,13 +906,13 @@
 		}
 		if (boot->FSNext != 0xffffffffU &&
 		    (boot->FSNext >= boot->NumClusters ||
-		    (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE))) {
+		    (boot->NumFree && fat_get_cl_next(fat, boot->FSNext) != CLUST_FREE))) {
 			pwarn("Next free cluster in FSInfo block (%u) %s\n",
 			      boot->FSNext,
 			      (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
 			if (ask(1, "fix"))
 				for (head = CLUST_FIRST; head < boot->NumClusters; head++)
-					if (fat[head].next == CLUST_FREE) {
+					if (fat_get_cl_next(fat, head) == CLUST_FREE) {
 						boot->FSNext = head;
 						ret = 1;
 						break;
@@ -722,5 +922,6 @@
 			mod |= writefsinfo(dosfs, boot);
 	}
 
+	bitmap_dtor(&usedbitmap);
 	return mod;
 }