svn commit: r357568 - stable/12/sbin/fsck_msdosfs

Xin LI delphij at FreeBSD.org
Wed Feb 5 08:55:20 UTC 2020


Author: delphij
Date: Wed Feb  5 08:55:19 2020
New Revision: 357568
URL: https://svnweb.freebsd.org/changeset/base/357568

Log:
  MFC r356249-r356250, r356313, r356434, r356657, r357421
  
  r356249-r356250, r356313:
  Reduce memory footprint of fsck_msdosfs.
  
  This utility was initially written for FAT12/16, which were inherently
  small. When FAT32 support was added, the old data structure and
  algorithms remain used with minimal changes.
  
  With growing size of FAT32 media, the current data structure that
  requires 4 32-bit variables per each FAT32 table entry would consume up
  to 4 GiB of RAM, which can be too big for systems with limited RAM
  available.
  
  Address this by taking a different approach of validating the FAT.
  
  The FAT is essentially a set of linked lists of chains that was
  referenced by directory entries, and the checker needs to make sure that
  the linked chains of clusters do not have cross-linked chains, and every
  chain were referenced by one and only one directory entry.  Instead of
  keeping track of the chain's 'head' cluster number, the size of the
  chain, the used status of the chain and the "next" pointer which is
  content of the FAT table, we create accessors for the FAT table data
  for the "next" pointer, and keep only one bit to indicate if the
  current cluster is a 'head' node of a cluster chain, in a bitmap.
  
  We further overhaul the FAT checker to find out the possible head nodes
  by excluding ones that are not (in other words, nodes that have some
  other nodes claiming them as the next node) instead of marking the head
  nodes for each node on the chain.  This approach greatly reduced the
  complexiety of computation from O(N^2) worst case, to an O(N) scan for
  worst case.  The file (cluster chain) length is not useful for the FAT
  checker, so don't bother to calculate them in the FAT checker and
  instead leave the task to the directory structure check, at which point
  we would have non-crossed cluster chains, and we are guaranteed that
  each cluster will be visited for at most one time.
  
  When checking the directory structures, we use the head node indicator
  to as the visited (used) flag: every cluster chain can only be
  referenced by one directory entry, so we clear them when calculating
  the length of the chain, and we can immediately tell if there are
  anomalies in the directory entry.
  
  As a result, the required RAM size is now 1 bit per each entry of
  the FAT table, plus memory needed to hold the FAT table in memory,
  instead of 16 bytes (=128 bits) per each entry.  For FAT12 and FAT16,
  we will load the whole FAT table into memory as they are smaller than
  128KiB, and for FAT32, we first attempt to mmap() it into memory, and
  when that fails, we would fall back to a simple LRU cache of 4 MiB of
  RAM.
  
  sbin/fsck_msdosfs/boot.c:
  
   - Added additional sanity checks for valid FAT32/FAT16/FAT12 cluster
     number.
   - FAT32: check if root directory starts with a valid cluster number,
     moved from dir.c.  There is no point to proceed if the filesystem
     is already damaged beyond repair.
  
  sbin/fsck_msdosfs/check.c:
  
   - Combine phase 1 and phase 2, now that the readfat() is able to
     detect cross chains.
  
  sbin/fsck_msdosfs/dir.c:
  
   - Refactor code to use FAT accessor instead of accessing the internal
     representation of FAT table.
   - Make use of the cluster chain head bitmap.
   - Clarify and simplify directory entry check, remove unnecessary
     checks that are would be done at a later time (for example, whether
     the directory's second cluster is a valid one, which is examined
     more throughly in a later checkchain() and does not prevent us
     from proceeding further).
  
  sbin/fsck_msdosfs/dosfs.h:
  
   - Remove internal representation of FAT table, which is replaced by
     the head bitmap that is opaque to other code.
   - Added a special CLUST_DEAD cluster type to indicate errors.
  
  sbin/fsck_msdosfs/ext.h:
  
   - Added a flag that overrides mmap(2) setting.  The corresponding
     command line option, -M is intentionally undocumented as we do not
     expect users to need it.
   - Added accessors for FAT table and convert existing interface to use
     it.
  
  sbin/fsck_msdosfs/fat.c:
  
   - Added head bitmap to represent whether a cluster is a head cluster.
   - Converted FAT internal representation to accessors.
   - Implemented a LRU cache for FAT32 when mmap(2) should not or can not
     be used.
   - _readfat: Attempt a mmap(2) and fall back to regular read for
     non-FAT32 file systems; use the LRU cache for FAT32 and prepopulate
     the cache with the first 4MiB of the entries.
   - readfat: Added support of head bitmap and use the population scan to
     detect bogus chains.
   - clusterdiff: removed, FATs are copied from the checked copy via
     writefat()/copyfat().
   - checkchain: calculates the length of a cluster chain and make sure
     that it ends with a valid EOF marker.
   - clearchain: follow and clear a chain and maintain the free cluster
     count.
   - checklost: convert to use head bitmap. At the end of all other scans,
     the remaining 'head' nodes are leaders of lost cluster chains.
  
  sbin/fsck_msdosfs/fat.c:
  
   - Added a new -M option which is intentionally undocumented, to disable
     the use of mmap().
  
  r356434:
  fsck_msdosfs.8: document -M.
  
  r356657:
  Tighten FAT checks and fix off-by-one error in corner case.
  
  sbin/fsck_msdosfs/fat.c:
   - readfat:
      * Only truncate out-of-range cluster pointers (1, or greater than
        NumClusters but smaller than CLUST_RSRVD), as the current cluster
        may contain some data. We can't fix reserved cluster pointers at
        this pass, because we do no know the potential cluster preceding
        it.
      * Accept valid cluster for head bitmap. This is a no-op, and mainly
        to improve code readability, because the 1 is already handled in
        the previous else if block.
   - truncate_at: absorbed into checkchain.
   - checkchain: save the previous node we have traversed in case that we
     have a chain that ends with a special (>= CLUST_RSRVD) cluster, or is
     free. In these cases, we need to truncate at the cluster preceding the
     current cluster, as the current cluster contains a marker instead of
     a next pointer and can not be changed to CLUST_EOF (the else case can
     happen if the user answered "no" at some point in readfat()).
   - clearchain: correct the iterator for next cluster so that we don't
     stop after clearing the first cluster.
   - checklost: If checkchain() thinks the chain have no cluster, it
     doesn't make sense to reconnect it, so don't bother asking.
  
  r357421:
  Diff reduction against NetBSD, no functional change.
  
  Relnotes:	yes

Modified:
  stable/12/sbin/fsck_msdosfs/boot.c
  stable/12/sbin/fsck_msdosfs/check.c
  stable/12/sbin/fsck_msdosfs/dir.c
  stable/12/sbin/fsck_msdosfs/dosfs.h
  stable/12/sbin/fsck_msdosfs/ext.h
  stable/12/sbin/fsck_msdosfs/fat.c
  stable/12/sbin/fsck_msdosfs/fsck_msdosfs.8
  stable/12/sbin/fsck_msdosfs/main.c
Directory Properties:
  stable/12/   (props changed)

Modified: stable/12/sbin/fsck_msdosfs/boot.c
==============================================================================
--- stable/12/sbin/fsck_msdosfs/boot.c	Wed Feb  5 05:42:42 2020	(r357567)
+++ stable/12/sbin/fsck_msdosfs/boot.c	Wed Feb  5 08:55:19 2020	(r357568)
@@ -28,7 +28,7 @@
 
 #include <sys/cdefs.h>
 #ifndef lint
-__RCSID("$NetBSD: boot.c,v 1.21 2018/02/08 09:05:17 dholland Exp $");
+__RCSID("$NetBSD: boot.c,v 1.22 2020/01/11 16:29:07 christos Exp $");
 static const char rcsid[] =
   "$FreeBSD$";
 #endif /* not lint */
@@ -152,9 +152,6 @@ 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)) {
@@ -270,18 +267,36 @@ readboot(int dosfs, struct bootblock *boot)
 	}
 
 	/*
-	 * The number of clusters is derived from available data sectors, divided
-	 * by sectors per cluster.
+	 * The number of clusters is derived from available data sectors,
+	 * divided by sectors per cluster.
 	 */
-	boot->NumClusters = (boot->NumSectors - boot->FirstCluster) / boot->bpbSecPerClust;
+	boot->NumClusters =
+	    (boot->NumSectors - boot->FirstCluster) / boot->bpbSecPerClust;
 
-	if (boot->flags & FAT32)
+	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;
+		}
 		boot->ClustMask = CLUST32_MASK;
-	else if (boot->NumClusters < (CLUST_RSRVD&CLUST12_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)) {
 		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;
@@ -306,8 +321,8 @@ readboot(int dosfs, struct bootblock *boot)
 	}
 
 	/*
-	 * There are two reserved clusters.  To avoid adding CLUST_FIRST every time
-	 * when we perform boundary checks, we increment the NumClusters by 2,
+	 * There are two reserved clusters. To avoid adding CLUST_FIRST every
+	 * time we perform boundary checks, we increment the NumClusters by 2,
 	 * which is CLUST_FIRST to denote the first out-of-range cluster number.
 	 */
 	boot->NumClusters += CLUST_FIRST;

Modified: stable/12/sbin/fsck_msdosfs/check.c
==============================================================================
--- stable/12/sbin/fsck_msdosfs/check.c	Wed Feb  5 05:42:42 2020	(r357567)
+++ stable/12/sbin/fsck_msdosfs/check.c	Wed Feb  5 08:55:19 2020	(r357568)
@@ -47,9 +47,8 @@ checkfilesys(const char *fname)
 {
 	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,65 +87,39 @@ checkfilesys(const char *fname)
 	}
 
 	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 and checking connectivity\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);
+	mod |= resetDosDirSection(fat);
 	finish_dosdirsection = 1;
 	if (mod & FSFATAL)
 		goto out;
 	/* delay writing FATs */
 
-	mod |= handleDirTree(dosfs, &boot, fat);
+	mod |= handleDirTree(fat);
 	if (mod & FSFATAL)
 		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);
+	mod |= checklost(fat);
 	if (mod & FSFATAL)
 		goto out;
 
 	/* now write the FATs */
-	if (mod & (FSFATMOD|FSFIXFAT)) {
+	if (mod & FSFATMOD) {
 		if (ask(1, "Update FATs")) {
-			mod |= writefat(dosfs, &boot, fat, mod & FSFIXFAT);
+			mod |= writefat(fat);
 			if (mod & FSFATAL)
 				goto out;
 		} else
@@ -170,7 +143,7 @@ checkfilesys(const char *fname)
 
 			if (mod & FSDIRTY) {
 				pwarn("MARKING FILE SYSTEM CLEAN\n");
-				mod |= writefat(dosfs, &boot, fat, 1);
+				mod |= writefat(fat);
 			} else {
 				pwarn("\n***** FILE SYSTEM IS LEFT MARKED AS DIRTY *****\n");
 				mod |= FSERROR; /* file system not clean */

Modified: stable/12/sbin/fsck_msdosfs/dir.c
==============================================================================
--- stable/12/sbin/fsck_msdosfs/dir.c	Wed Feb  5 05:42:42 2020	(r357567)
+++ stable/12/sbin/fsck_msdosfs/dir.c	Wed Feb  5 08:55:19 2020	(r357568)
@@ -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,14 +96,11 @@ static struct dirTodoNode *newDirTodo(void);
 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,
-    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 *);
+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 *);
 
 /*
  * Manage free dosDirEntry structures.
@@ -116,7 +114,7 @@ newDosDirEntry(void)
 
 	if (!(de = freede)) {
 		if (!(de = malloc(sizeof *de)))
-			return 0;
+			return (NULL);
 	} else
 		freede = de->next;
 	return de;
@@ -193,7 +191,7 @@ fullpath(struct dosDirEntry *dir)
 /*
  * Calculate a checksum over an 8.3 alias name
  */
-static u_char
+static inline u_char
 calcShortSum(u_char *p)
 {
 	u_char sum = 0;
@@ -221,21 +219,24 @@ static struct dosDirEntry *lostDir;
  * Init internal state for a new directory scan.
  */
 int
-resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
+resetDosDirSection(struct fat_descriptor *fat)
 {
-	int b1, b2;
+	int rootdir_size, cluster_size;
 	int ret = FSOK;
 	size_t len;
+	struct bootblock *boot;
 
-	b1 = boot->bpbRootDirEnts * 32;
-	b2 = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+	boot = fat_get_boot(fat);
 
-	if ((buffer = malloc(len = MAX(b1, b2))) == NULL) {
+	rootdir_size = boot->bpbRootDirEnts * 32;
+	cluster_size = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+
+	if ((buffer = malloc(len = MAX(rootdir_size, cluster_size))) == NULL) {
 		perr("No space for directory buffer (%zu)", len);
 		return FSFATAL;
 	}
 
-	if ((delbuf = malloc(len = b2)) == NULL) {
+	if ((delbuf = malloc(len = cluster_size)) == NULL) {
 		free(buffer);
 		perr("No space for directory delbuf (%zu)", len);
 		return FSFATAL;
@@ -250,18 +251,10 @@ resetDosDirSection(struct bootblock *boot, struct fatE
 
 	memset(rootDir, 0, sizeof *rootDir);
 	if (boot->flags & FAT32) {
-		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) {
+		if (!fat_is_cl_head(fat, boot->bpbRootClust)) {
 			pfatal("Root directory doesn't start a cluster chain");
 			return FSFATAL;
 		}
-
-		fat[boot->bpbRootClust].flags |= FAT_USED;
 		rootDir->head = boot->bpbRootClust;
 	}
 
@@ -302,16 +295,21 @@ finishDosDirSection(void)
  * Delete directory entries between startcl, startoff and endcl, endoff.
  */
 static int
-delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
+delete(struct fat_descriptor *fat, cl_t startcl,
     int startoff, cl_t endcl, int endoff, int notlast)
 {
 	u_char *s, *e;
 	off_t off;
-	int clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+	int clsz, fd;
+	struct bootblock *boot;
 
+	boot = fat_get_boot(fat);
+	fd = fat_get_fd(fat);
+	clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+
 	s = delbuf + startoff;
 	e = delbuf + clsz;
-	while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
+	while (fat_is_valid_cl(fat, startcl)) {
 		if (startcl == endcl) {
 			if (notlast)
 				break;
@@ -320,11 +318,11 @@ delete(int f, struct bootblock *boot, struct fatEntry 
 		off = (startcl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 
 		off *= boot->bpbBytesPerSec;
-		if (lseek(f, off, SEEK_SET) != off) {
+		if (lseek(fd, off, SEEK_SET) != off) {
 			perr("Unable to lseek to %" PRId64, off);
 			return FSFATAL;
 		}
-		if (read(f, delbuf, clsz) != clsz) {
+		if (read(fd, delbuf, clsz) != clsz) {
 			perr("Unable to read directory");
 			return FSFATAL;
 		}
@@ -332,25 +330,26 @@ delete(int f, struct bootblock *boot, struct fatEntry 
 			*s = SLOT_DELETED;
 			s += 32;
 		}
-		if (lseek(f, off, SEEK_SET) != off) {
+		if (lseek(fd, off, SEEK_SET) != off) {
 			perr("Unable to lseek to %" PRId64, off);
 			return FSFATAL;
 		}
-		if (write(f, delbuf, clsz) != clsz) {
+		if (write(fd, delbuf, clsz) != clsz) {
 			perr("Unable to write directory");
 			return FSFATAL;
 		}
 		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(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:
@@ -366,14 +365,14 @@ removede(int f, struct bootblock *boot, struct fatEntr
 	}
 	if (ask(0, "Remove")) {
 		if (startcl != curcl) {
-			if (delete(f, boot, fat,
+			if (delete(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;
@@ -386,23 +385,37 @@ removede(int f, struct bootblock *boot, struct fatEntr
  * Check an in-memory file entry
  */
 static int
-checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
-    struct dosDirEntry *dir)
+checksize(struct fat_descriptor *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
 	 */
-	u_int32_t physicalSize;
-
-	if (dir->head == CLUST_FREE)
+	if (dir->head == CLUST_FREE) {
 		physicalSize = 0;
-	else {
-		if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
+	} else {
+		if (!fat_is_valid_cl(fat, dir->head))
 			return FSERROR;
-		physicalSize = fat[dir->head].length * boot->ClusterSize;
+		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;
 	}
 	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;
@@ -422,11 +435,10 @@ checksize(struct bootblock *boot, struct fatEntry *fat
 
 			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;
-			return FSFATMOD;
+				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);
 		} else
 			return FSERROR;
 	}
@@ -442,15 +454,20 @@ static const u_char dotdot_name[11] = "..         ";
  * when we traverse into it.
  */
 static int
-check_subdirectory(int f, struct bootblock *boot, struct dosDirEntry *dir)
+check_subdirectory(struct fat_descriptor *fat, 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 && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
+	if (dir->parent && !fat_is_valid_cl(fat, cl)) {
 		return FSERROR;
 	}
 
@@ -474,8 +491,8 @@ check_subdirectory(int f, struct bootblock *boot, stru
 	}
 
 	off *= boot->bpbBytesPerSec;
-	if (lseek(f, off, SEEK_SET) != off ||
-	    read(f, buf, boot->bpbBytesPerSec) != (ssize_t)boot->bpbBytesPerSec) {
+	if (lseek(fd, off, SEEK_SET) != off ||
+	    read(fd, buf, boot->bpbBytesPerSec) != (ssize_t)boot->bpbBytesPerSec) {
 		perr("Unable to read directory");
 		free(buf);
 		return FSFATAL;
@@ -509,22 +526,27 @@ check_subdirectory(int f, struct bootblock *boot, stru
  *   - push directories onto the todo-stack
  */
 static int
-readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
-    struct dosDirEntry *dir)
+readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
 {
+	struct bootblock *boot;
 	struct dosDirEntry dirent, *d;
 	u_char *p, *vallfn, *invlfn, *empty;
 	off_t off;
-	int i, j, k, last;
+	int fd, i, j, k, iosize, entries;
+	bool is_legacyroot;
 	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 && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
+	if (dir->parent && (!fat_is_valid_cl(fat, cl))) {
 		/*
 		 * Already handled somewhere else.
 		 */
@@ -532,24 +554,50 @@ readDosDirSection(int f, struct bootblock *boot, struc
 	}
 	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 (!(boot->flags & FAT32) && !dir->parent) {
-			last = boot->bpbRootDirEnts * 32;
+		if (is_legacyroot) {
+			/*
+			 * Special case for FAT12/FAT16 root -- read
+			 * in the whole root directory.
+			 */
 			off = boot->bpbResSectors + boot->bpbFATs *
 			    boot->FATsecs;
 		} else {
-			last = boot->bpbSecPerClust * boot->bpbBytesPerSec;
+			/*
+			 * Otherwise, read in a cluster of the
+			 * directory.
+			 */
 			off = (cl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 		}
 
 		off *= boot->bpbBytesPerSec;
-		if (lseek(f, off, SEEK_SET) != off
-		    || read(f, buffer, last) != last) {
+		if (lseek(fd, off, SEEK_SET) != off ||
+		    read(fd, buffer, iosize) != iosize) {
 			perr("Unable to read directory");
 			return FSFATAL;
 		}
-		last /= 32;
-		for (p = buffer, i = 0; i < last; i++, p += 32) {
+
+		for (p = buffer, i = 0; i < entries; i++, p += 32) {
 			if (dir->fsckflags & DIREMPWARN) {
 				*p = SLOT_EMPTY;
 				continue;
@@ -572,7 +620,7 @@ readDosDirSection(int f, struct bootblock *boot, struc
 						u_char *q;
 
 						dir->fsckflags &= ~DIREMPTY;
-						if (delete(f, boot, fat,
+						if (delete(fat,
 							   empcl, empty - buffer,
 							   cl, p - buffer, 1) == FSFATAL)
 							return FSFATAL;
@@ -701,7 +749,7 @@ readDosDirSection(int f, struct bootblock *boot, struc
 
 			if (dirent.flags & ATTR_VOLUME) {
 				if (vallfn || invlfn) {
-					mod |= removede(f, boot, fat,
+					mod |= removede(fat,
 							invlfn ? invlfn : vallfn, p,
 							invlfn ? invcl : valcl, -1, 0,
 							fullpath(dir), 2);
@@ -741,7 +789,7 @@ readDosDirSection(int f, struct bootblock *boot, struc
 			dirent.next = dir->child;
 
 			if (invlfn) {
-				mod |= k = removede(f, boot, fat,
+				mod |= k = removede(fat,
 						    invlfn, vallfn ? vallfn : p,
 						    invcl, vallfn ? valcl : cl, cl,
 						    fullpath(&dirent), 0);
@@ -757,74 +805,61 @@ readDosDirSection(int f, struct bootblock *boot, struc
 			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;
+			/*
+			 * 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;
+					}
 				}
-			} 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
@@ -861,8 +896,7 @@ readDosDirSection(int f, struct bootblock *boot, struc
 							mod |= FSERROR;
 					}
 					continue;
-				}
-				if (strcmp(dirent.name, "..") == 0) {
+				} else if (strcmp(dirent.name, "..") == 0) {
 					if (dir->parent) {		/* XXX */
 						if (!dir->parent->parent) {
 							if (dirent.head) {
@@ -908,7 +942,7 @@ readDosDirSection(int f, struct bootblock *boot, struc
 						} else
 							mod |= FSERROR;
 						continue;
-					} else if ((check_subdirectory(f, boot,
+					} else if ((check_subdirectory(fat,
 					    &dirent) & FSERROR) == FSERROR) {
 						/*
 						 * A subdirectory should have
@@ -944,39 +978,43 @@ readDosDirSection(int f, struct bootblock *boot, struc
 				n->dir = d;
 				pendingDirectories = n;
 			} else {
-				mod |= k = checksize(boot, fat, p, &dirent);
+				mod |= k = checksize(fat, p, &dirent);
 				if (k & FSDIRMOD)
 					mod |= THISMOD;
 			}
 			boot->NumFiles++;
 		}
 
-		if (!(boot->flags & FAT32) && !dir->parent)
+		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.
+			 */
 			break;
-
-		if (mod & THISMOD) {
-			last *= 32;
-			if (lseek(f, off, SEEK_SET) != off
-			    || write(f, buffer, last) != last) {
+		} else if (mod & THISMOD) {
+			if (lseek(fd, off, SEEK_SET) != off
+			    || write(fd, buffer, iosize) != iosize) {
 				perr("Unable to write directory");
 				return FSFATAL;
 			}
 			mod &= ~THISMOD;
 		}
-	} while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
+	} while (fat_is_valid_cl(fat, (cl = fat_get_cl_next(fat, cl))));
 	if (invlfn || vallfn)
-		mod |= removede(f, boot, fat,
+		mod |= removede(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 without being written out.
+	/*
+	 * The root directory of non-FAT32 filesystems is in a special
+	 * area and may have been modified above removede() without
+	 * being written out.
 	 */
-	if ((mod & FSDIRMOD) && !(boot->flags & FAT32) && !dir->parent) {
-		last *= 32;
-		if (lseek(f, off, SEEK_SET) != off
-		    || write(f, buffer, last) != last) {
+	if ((mod & FSDIRMOD) && is_legacyroot) {
+		if (lseek(fd, off, SEEK_SET) != off
+		    || write(fd, buffer, iosize) != iosize) {
 			perr("Unable to write directory");
 			return FSFATAL;
 		}
@@ -986,11 +1024,11 @@ readDosDirSection(int f, struct bootblock *boot, struc
 }
 
 int
-handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
+handleDirTree(struct fat_descriptor *fat)
 {
 	int mod;
 
-	mod = readDosDirSection(dosfs, boot, fat, rootDir);
+	mod = readDosDirSection(fat, rootDir);
 	if (mod & FSFATAL)
 		return FSFATAL;
 
@@ -1011,7 +1049,7 @@ handleDirTree(int dosfs, struct bootblock *boot, struc
 		/*
 		 * handle subdirectory
 		 */
-		mod |= readDosDirSection(dosfs, boot, fat, dir);
+		mod |= readDosDirSection(fat, dir);
 		if (mod & FSFATAL)
 			return FSFATAL;
 	}
@@ -1027,12 +1065,15 @@ static cl_t lfcl;
 static off_t lfoff;
 
 int
-reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
+reconnect(struct fat_descriptor *fat, cl_t head, size_t length)
 {
+	struct bootblock *boot = fat_get_boot(fat);
 	struct dosDirEntry d;
-	int len;
+	int len, dosfs;
 	u_char *p;
 
+	dosfs = fat_get_fd(fat);
+
 	if (!ask(1, "Reconnect"))
 		return FSERROR;
 
@@ -1063,7 +1104,7 @@ reconnect(int dosfs, struct bootblock *boot, struct fa
 					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);
@@ -1088,7 +1129,7 @@ reconnect(int dosfs, struct bootblock *boot, struct fa
 	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);
@@ -1103,7 +1144,6 @@ reconnect(int dosfs, struct bootblock *boot, struct fa
 	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");

Modified: stable/12/sbin/fsck_msdosfs/dosfs.h
==============================================================================
--- stable/12/sbin/fsck_msdosfs/dosfs.h	Wed Feb  5 05:42:42 2020	(r357567)
+++ stable/12/sbin/fsck_msdosfs/dosfs.h	Wed Feb  5 08:55:19 2020	(r357568)
@@ -83,19 +83,13 @@ 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
@@ -103,8 +97,6 @@ struct fatEntry {
 #define	CLUST12_MASK	0xfff
 #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 */

Modified: stable/12/sbin/fsck_msdosfs/ext.h
==============================================================================
--- stable/12/sbin/fsck_msdosfs/ext.h	Wed Feb  5 05:42:42 2020	(r357567)
+++ stable/12/sbin/fsck_msdosfs/ext.h	Wed Feb  5 08:55:19 2020	(r357568)
@@ -32,6 +32,8 @@
 
 #include <sys/types.h>
 
+#include <stdbool.h>
+
 #include "dosfs.h"
 
 #define	LOSTDIR	"LOST.DIR"
@@ -44,6 +46,7 @@ extern int alwaysyes;	/* assume "yes" for all question
 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
@@ -72,7 +75,6 @@ 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
@@ -85,46 +87,53 @@ int readboot(int, struct bootblock *);
  */
 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 **);
+/* Opaque type */
+struct fat_descriptor;
 
-/*
- * Check two FAT copies for consistency and merge changes into the
- * first if necessary.
- */
-int comparefat(struct bootblock *, struct fatEntry *, struct fatEntry *, u_int);
+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);
+
+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 a FAT
+ * Read the FAT 0 and return a pointer to the newly allocated
+ * descriptor of it.
  */
-int checkfat(struct bootblock *, struct fatEntry *);
+int readfat(int, struct bootblock *, struct fat_descriptor **);
 
 /*
  * Write back FAT entries
  */
-int writefat(int, struct bootblock *, struct fatEntry *, int);
+int writefat(struct fat_descriptor *);
 
 /*
  * Read a directory
  */
-int resetDosDirSection(struct bootblock *, struct fatEntry *);
+int resetDosDirSection(struct fat_descriptor *);
 void finishDosDirSection(void);
-int handleDirTree(int, struct bootblock *, struct fatEntry *);
+int handleDirTree(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(struct fat_descriptor *);
 /*
  * Try to reconnect a lost cluster chain
  */
-int reconnect(int, struct bootblock *, struct fatEntry *, cl_t);
+int reconnect(struct fat_descriptor *, cl_t, size_t);
 void finishlf(void);
 
 /*
@@ -138,6 +147,6 @@ const char *rsrvdcltype(cl_t);
 /*
  * Clear a cluster chain in a FAT
  */
-void clearchain(struct bootblock *, struct fatEntry *, cl_t);
+void clearchain(struct fat_descriptor *, cl_t);
 
 #endif

Modified: stable/12/sbin/fsck_msdosfs/fat.c
==============================================================================
--- stable/12/sbin/fsck_msdosfs/fat.c	Wed Feb  5 05:42:42 2020	(r357567)
+++ stable/12/sbin/fsck_msdosfs/fat.c	Wed Feb  5 08:55:19 2020	(r357568)
@@ -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,14 @@ static const char rcsid[] =
   "$FreeBSD$";
 #endif /* not lint */
 
+#include <sys/endian.h>

*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***


More information about the svn-src-all mailing list