疫情之前，娃在周末会去某个才艺班，上课的时间我觉得实在是比较无聊， 于是就带上笔记本坐在星巴克做一些较小规模的代码清理工作。 最终，我利用这些碎块化的时间完成了对 FreeBSD 的 fsck_msdosfs(8) 的核心代码的算法进行了改进，使其需要的内存用量变成了原先的 1/128， 这里稍微记一下当时的一些思路。

背景

fsck_msdosfs(8) 是 FreeBSD 上用来检查和修复 FAT12/16/32 文件系统问题的程序， 此外， Android 也使用了这一实现，并采用它来检查使用 FAT 文件系统，如 SD 卡上的文件系统问题。

众所周知，FAT 是一个结构非常简单的文件系统。它的基本分配单元是簇(clusters)， 每个簇可以包括1-128个逻辑扇区。FAT 文件系统使用单一的中央数据结构——文件分配表 FAT 来表现存储上的所有簇的分配状态，该结构本身是一个线性表，其中每一项均与磁盘上的相对位置的簇一一对应。 这个表上以单链表形式表达文件，链表的表头保存在该文件对应的目录项上，而后续的整个簇链则在 FAT 表上，每一项的内容是下一簇的簇号。FAT 表项如果是 0 则表示目前没有任何文件在使用该簇， 因此可以将作为保存新数据的空间使用，还有一些特殊值表示坏块、保留块，或者文件已经到达了末尾。

fsck_msdosfs(8) 最早是在 NetBSD 中引入的。 最早只支持 FAT12/16。后来，有人为其实现了 FAT32 支持，但核心算法基本保持不变。 结构上，它大致上可以分为四步：

1. 将 FAT 全部的数据结构载入内存，并将其转换为内部表现形式。
2. 扫描 FAT 两遍。第一遍是找到所有的链表表头，第二遍则顺着这些表头逐个遍历这些链表，检查其中是否存在交叉的情况，并在此过程中处理一些其他的异常（例如文件目录中记录的文件长度与簇链长度不一致）并予以纠正
3. 检查目录结构，并将目录引用的簇链进行标记。
4. 所有没有在上一步中被标记为已引用的簇链属于丢失簇链，类似于内存泄漏，因为没有任何文件用到了它们。这些簇链应该恢复为文件，或者释放掉。

上述算法是相当低效的，这一点在 FAT 较大时弊端非常明显。在内存方面，其辅助数据结构是个四元组，每簇需要占用16字节。 计算方面，由于每个簇链都需要遍历数次，考虑交叉的情况，其极端情况的遍历复杂性是 O(N^2)。

之前的算法

为了便于理解，这里用一个非常简单的 FAT 表：

这其中包含了一个簇链：4->3->5->6->7。我们遍历该线性表，首先来到簇3。 顺着这个链条，我们将簇5、6、7标记为以簇3为起点、长度为4（新记录的数据标记为*）。

下一轮我们访问到了下一个簇(4)。簇4指出的下一簇是3（这是个交叉链），于是之前从簇3访问的结果均被改写，标记为+：

在之前采用的算法中，整个FAT都会读到内存里（Next），这样做的原因是早期的FAT主要应用场景是软盘，其寻道、读写都很慢， 另一方面FAT12/16的尺寸非常小，因此完全可以直接载入内存（假设有 2^16 个簇，每个簇用 4 个字节，则上限是 256 kiB，对于现时的系统来说是完全可以接受的）。

对于FAT32，由于最多可以有2^28个簇，这样做的结果便是需要 1 GiB 的内存。而先前的算法还需要保存链头和长度， 这需要2倍的额外内存（=2GiB）。更严重的是，原先的数据结构 fatEntry 还有一个额外的 flags：

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 */
};

这样对于一个较大的文件系统来说，需要的内存将达到 4GiB。对于嵌入式系统来说，这就有点多了。

新算法

考虑之前算法，我们实际上需要达到以下几个目的：

1. 确认每一个簇链均有始有终且互相不交叉。
2. 确认簇链长度与目录项记载的一致。
3. 确认簇链只被引用一次。
4. 找到每一个没有被目录项引用的簇链，以便回收空间或将其转化为文件。

确认链之间不交叉有至少两种方法，一种是类似之前的、逐个遍历每一条链并将节点标记上对应的链头， 容易证明该情况最差情况下我们需要进行O(N^2)量级的扫描。

另一种方法，则是先假定所有的簇都是链头，然后一次遍历整个线性表，将被 next 指针引用的簇标记为不是链头。此方法只需遍历整个线性表，即 O(N)。 由此，我们将获得一个表示对应簇是否是簇链头的位映射图 （headbitmap）。

需要注意的是，这个方法标记的是每个节点是否是链头，而并不知道该节点对应的链头是谁， 自然也就无从立即知晓簇链的长度。该任务可以延后到检查目录项完整性的部分来进行， 因为目录项中保存了链簇头节点的位置，故而只需判断该簇是否是链头，如果是， 则沿着该簇链逐个遍历直到找到链尾并计算长度。

以下是略为精简的伪代码：

	/*
	 * 遍历 FAT 表并创建簇链头位图。
	 * 首先假定每一个簇都是一个簇链的头，然后遍历整个 FAT 表，
	 * 并将其中不是簇链头，即那些有其他簇将其指为后继节点的那些簇从该位图中删去，
         * 在此过程中修复一些明显的问题。
	 *
	 * 每个 "next" 簇的可能取值如下：
         *
	 * a) CLUST_FREE 或 CLUST_BAD。当前簇不可能是簇链起点。
	 * b) 超出范围的值。此时必须将簇链在此处切断。
	 * c) 有效簇。这说明此簇 (nextcl) 不可能是簇链起点。
	 *    在遍历过程中，每个簇最多只能被一个其他簇指为下一簇，
	 *    因此若该簇已经被标记为不是簇起点，则表示出现了链交叉的情况，
	 *    此时只能在当前簇切断。
	 *
	 * 完成此扫描之后，簇链头位图中仍然为1的就是所有潜在的簇链头了。
	 * 不过我们暂时还不知道它们是否以正确的EOF终结，也不知道它们的长度。
         * 这将在检查目录结构时由 checkchain() 进行，
         * 由于簇链只能属于一个文件，因此检查过的簇链头也将从位图中清除。
	 *
	 * 最终，位图中余下的簇链头即为丢失簇链头。
	 */
	for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
		nextcl = fat_get_cl_next(fat, cl);

		/* 检查 nextcl 是否在有效范围 */
		if (nextcl == CLUST_FREE) {
			/* 如果尚不知道最后一个未分配簇在哪，保存该簇号 */
			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_RSRVD) {
                        /* 无效簇号，切断 */
			pwarn("Cluster %u continues with out of range "
			    "cluster number %u\n",
			    cl,
			    nextcl & boot->ClustMask);
			if (ask(0, "Truncate")) {
				ret |= fat_set_cl_next(fat, cl, CLUST_EOF);
				ret |= FSFATMOD;
			}
		} else if (valid_cl(fat, nextcl)) {
                        /* 有效簇号，如果没有其他簇链引用过，则该簇一定不是簇链头 */
			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;
				}
			}
		}

	}

仍然按照刚才的例子：

初始状态：

扫描到3(next = 5)：

扫描到4(next = 3)：

完成扫描后：

这样一来，每一个簇只需要使用1 bit的辅助空间来表达就可以了。

缓存

前面提到，FAT32最多可以有 2^28 个簇，这需要占用 1GiB 的空间。第一遍扫描时我们是把 FAT 作为一个线性表来做线性扫描的，完全没有任何必要将其整个载入内存。之后检查目录项时， 在极端情况（文件系统非常碎块化）时，我们可能会需要反复访问FAT的不同区域。

综合以上考虑，一个显然的解决方案就是增加一个缓存层，并将原先实现中直接读写 FAT 内部表现形式的部分改写为直接使用一个抽象的访问函数来进行操作，并将缓存的问题交给缓存层来进行。 操作系统已经为我们提供了一个很好的缓存实现，因此如果能用的话直接 mmap(2) 是最佳策略； 如果不能，则退而求其次，自己实现一个 LRU 队列。

前面提到 FAT12 和 FAT16 的最大尺寸都足够小，因此可以直接将其放进内存。FAT32 则分两种情况， 对于能使用操作系统的缓存系统的情况，我们只需把整个 FAT 映射到内存中并当作一个大数组访问即可； 对于自行实现 LRU 队列的情况，则创建一个 LRU 缓存池（尺寸是拍脑门定的 4MiB， 每个缓存块是 128kiB）。

LRU 的实现过于简单且并无特别，再次不再赘述，淘汰时如果缓存块发生过写操作，则将其写回磁盘原位置。

总结

经过 这次重构 之后， fsck_msdosfs(8) 的内存需求减少到了原来的 1/128，并且原先的两步扫描合并成了一步完成。 该项改进已在去年随 FreeBSD 12.2 / 11.4、 Android 11 发布。