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 were 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. The file (cluster chain) lengith 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 anomolies 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 LRU cache that would use
approximately 4MiB 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.
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 which is used 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.
- 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().