Count used root directory entries in FAT12/16 file systems

[se]

Summary

The msdos file system code in FreeBSD did not count the number of directory slots used/free in the root directory of a FAT12 or FAT16 file system. The number of available DOS-8.3 style directory entries is fetched from the boot block and e.g. displayed by "df -i" as the number of available inodes, but statfs() returns 0 as the number of free entries.
This causes monitoring software to warn about a directory that is 100% full.

This patch set adds free entry accounting to the msdos file system:

• the number of used directory entries is counted when a FAT12 or FAT16 file system is mounted
• the number is adjusted by all operations that affect the count (create, rename, or delete of a file or directory).

The file system code is unchanged except for the initialization and updating of the new msdos mount structure element used to count the number of free directory entries, which can only be queried using statfs().
These patches do not affect FAT32 file systems (which have no limit on the number of files in the root directory and which report 0 for available and free inodes).

Test Plan

Apply the patch and rebuild the msdosfs module or a kernel with options MSDOSFS.
Using this kernel/module mount a FAT12 or FAT16 file system and check that the number of inodes corresponds to the number of directory slots used.
Perform operations on the file system (create, rename, delete files and directories) and check that the number of used/free inodes is correct at all times.

The number of directory slots used is:

• 1 for a disk label (if present)
• 1 entry per each DOS-8.3 file name
• 1 additional entry per 13 characters for each Windows 95 style file name (if not representable as a 8.3 character upper-case only DOS file name).

A single file can use 1 to 7 directory entry slots, depending on the character set used and its length.
Renaming a file can change the number of directory slots required (e.g. "TEST.DAT" needs 1, "test.dat" needs 2).

[se]

sys/fs/msdosfs/msdosfsmount.h

226

The comment is wrong and applies to a prior version of the patch: the number of free entries is counted (here and in the macro below),

[woodsb02]

Hi Stefan,

Thanks for putting this together so quickly.

I think we should update the msdosfs(5) manpage to describe this feature to users - that can be the subject of a separate review.

In the mean time, I’ve suggested a couple of places in the code where some comments might help future developers understand the intent.

sys/fs/msdosfs/msdosfs_vfsops.c

842

Suggest adding a comment above this that describes:

• the intent (can use the free entry accounting description from the summary of this review), and
• the logic (can use the number of disk slots description from the test plan of this review)

1051–1053

Suggest adding a comment that the statfs entries normally used for total/free inodes are instead being used on an msdosfs to show total/free root directory entries. Perhaps also explain that this only applies to FAT12/FAT16, and these entries will both return 0 on a FAT32 file system which does not have a limit for root directory entries.

[mckusick]

This looks like a useful change. How difficult would it be to make it also work for FAT32 filesystems?

[woodsb02]

In D38987#887609, @mckusick wrote:

How difficult would it be to make it also work for FAT32 filesystems?

From discussions on the mailing list so far, I thought the root directory entity limit only existed on FAT12/16, and did not exist on FAT32? Or is it that FAT32 does not have a limit by default, but one can be configured if desired when the file system is created?
(I have next to zero background knowledge on FAT)

[se]

In D38987#887609, @mckusick wrote:

This looks like a useful change. How difficult would it be to make it also work for FAT32 filesystems?

FAT12/16 have a fixed number of directory blocks between the FAT tables and the data area.
FAT32 does away with a fixed root directory and uses kind of a 1st level sub-directory for root directory entries instead (i.e. there is a single block pointer in the boot block which points at the start of a directory "file" of variable length).

Since there is no size limit for the root directory on FAT32, there is no limit on the number of "inodes" as reported by statfs().
Both the number of inodes and of free inodes are reported as 0 and the df command deals with this special case by not reporting a percentage of free inodes.

[se]

sys/fs/msdosfs/msdosfs_vfsops.c

849

While the default size of the root directory is 512 directory slots (16 KB), the upper limit is 65535, which would lead to a dirsize of 2 MB.
If reading 2 MB in such a case is considered excessive (or not supported by the kernel - I have not checked the max. amount bread is willing to read), the amount read could be limited to e.g. 16 KB and an outer loop added.

1051–1053

I'll add a comment, but this is a topic that might need to be documented in other places, too (man-pages of msdosfs and statfs?).
It might be confusing for users that 1 free inode displayed by df allows to create another DOS-8.3 named file in the root directory, but no file that needs a Win95 style long file name (which would need at least 2 free directory entries).
And it could be considered irritating that the DOS disk label takes up one "inode", too. A completely empty root directory will be listed with 1 used inode.
Additionally, 0 free inodes reported on a FAT12/16 file system will not prevent the creation of files in sub-directories.

This is all confusing and I consider FAT12/16 such a special case, that it should not need so much attention in the documentation of a Unix O.
But use of FAT12/16 for the UEFI partition makes them relevant on most amd64 and some aarch64 systems (even though mostly invisible to users unless mounted for updating).

sys/fs/msdosfs/msdosfsmount.h

118

This could also be an int or u:_int. The acceptable range is 0..65535.

[mckusick]

In D38987#887669, @se wrote:

In D38987#887609, @mckusick wrote:

This looks like a useful change. How difficult would it be to make it also work for FAT32 filesystems?

FAT12/16 have a fixed number of directory blocks between the FAT tables and the data area.
FAT32 does away with a fixed root directory and uses kind of a 1st level sub-directory for root directory entries instead (i.e. there is a single block pointer in the boot block which points at the start of a directory "file" of variable length).

Since there is no size limit for the root directory on FAT32, there is no limit on the number of "inodes" as reported by statfs().
Both the number of inodes and of free inodes are reported as 0 and the df command deals with this special case by not reporting a percentage of free inodes.

Thanks for the clarification. I concur that leaving FAT32 in its current form and just improving FAT 12/16 is the right thing to do.

sys/fs/msdosfs/msdosfs_vfsops.c

849

The maximum size that one can bread() is MAXBCACHEBUF which by default is MAXBSIZE (64KB). Given the size and usage of msdos filesystems, I think it is entirely reasonable that our implementation limit the root directory to a size of 64KB. This limit should be noted in a comment here and perhaps in the documentation of newfs_msdos(8).

1051–1053

The details of how the numbers change is low-level enough that I concur it is not worth documenting in detail. Most users just care to know if they have the ability to create more files and whether they are "close" to running out. This commit fulfills that need.

[mckusick]

In email to me Stefan Esser writes:

I'm not happy with the choice of function names for the increment/decrement macros, and I think that the exact location of their invocation should be reviewed with regard to error cases.

I could see spelling out the names a bit more, say rootdirentry_alloced and rootdirentry_freed.

In looking through the error cases, they are rare I/O failures and it would be quite a bit more code to clean them up. Since the numbers are not critical, I am inclined to not deal with getting them right in this code, but rather letting them get cleaned up by fsck_msdosfs(8) which will likely have to run anyway once the filesystem has experienced I/O failures. But this does highlight the need to have this patch also include the changes needed for fsck_msdosfs(8) to calculate and correct these numbers which it should default to doing when running in -p (preen) mode. The fsck_msdosfs(8) change is particularly neeed when this is committed so that all the existing FAT 12/16 filesystems will start providing the file information in statfs(2) and df(1).

[se]

sys/fs/msdosfs/msdosfs_vfsops.c

849

I'm working on a version that reads the directory in smaller chunks and that works correctly for arbitrary numbers of root directory entries. I prefer to support all theoretically allowed values instead of documenting arbitrary (albeit sensible) limits.

1051–1053

I plan to add comments regarding the inodes reported to the msdos(5) man page and in the description of the "-i" option in the df(1) man page.

[se]

Updated directory scan code, tested with different sector sizes and directory sizes (up to 65534 entries), including uncommon "odd" numbers of directory entries that do not fill complete disk blocks.

[mckusick]

Improvements so far look good.
Several places already noted still need new or updated comments.
Should add updates to msdos(5) and df(1) manual pages.

sys/fs/msdosfs/msdosfs_vfsops.c

411–502

A comment on what this function does would be good.

429

Unless you plan to delete this debugging information, it needs to be readjusted to fit in 80-column lines.

[se]

In D38987#888159, @mckusick wrote:

Improvements so far look good.
Several places already noted still need new or updated comments.
Should add updates to msdos(5) and df(1) manual pages.

Thank you for the review!
I'm going to address all your comments in an updated patch. I first wanted to get the functionality complete and tested, then work on documentation, comments, style.
Since I'll be traveling for one week without good Internet access, I'll probably not be able upload the updated patch before 2023-03-20, though.

[mckusick]

Since I'll be traveling for one week without good Internet access, I'll probably not be able upload the updated patch before 2023-03-20, though.

No rush. I hope some of your travel will be for fun.

[woodsb02]

My testing seems to show this is working correctly
I've tested this by building a new FreeBSD-CURRENT disc1.iso, installing it into a bhyve VM that was booted with UEFI and installing with the default ZFS installer.
Upon reboot, the /boot/efi folder is automatically mounted by default with the FAT16 file system from /dev/gpt/efiboot0.
If I create files in the root directory with upper case names, the output of "df -i" increases by 1. If I use lower case names, it increases by 2. If I use long names, it increases by bigger increments depending on the length of the name.
Once I create enough files that I am no longer able to create more files in the root directory (error is "No space left on device"), then "df -i" shows the inodes are 100% full.

[se]

Read directory in units of the file system cluster size instead of MAXBSIZE since the latter caused kernel panics in some tests.
If a FAT file system has been created with an "odd" number of directory entries that is not a multiple of 16, the msdosfs code allows to fill the sector containing the last directory sector. Therefore the configured number of directory entries is rounded up to a multiple of 16.
Add comments that describe the new function that counts the used directory entries when a FAT12 or FAT16 file system is mounted.
A test script has been added to PR #270053 - msdosfs with the latest patches passes this test for all file system parameters defined in this script.

[se]

sys/fs/msdosfs/msdosfs_vfsops.c

411–502

Additional information could be added to the man-pages of mount_msdosfs and/or statfs and possibly also df.

842

I'm not sure that the information about the different types of entries should be added here. Except for the debug output, only the value 0xE5 is used in the free entry count logic - it is not relevant what non-free entries are used for.

849

Reading MAXBSIZE chunks lead to problems (apparently random kernel panics unmounting such file systems, I have not been able to determine the exact cause). Therefore the limit has been set to the file system cluster size (which should be smaller than MAXBSIZE, but this is not enforced in the code - I might have to add another check to enforce that limit for oversize cluster sizes).

sys/fs/msdosfs/msdosfsmount.h

118

The type of pm_rootdirfree should be int to allow -1 to be returned as an error indicator.

226

The comment needs to be fixed - has been forgotten when I prepared the latest patch.

[mckusick]

These changes look good. I recommend adding the changes to the df(1) and msdos(5) man pages here so it all gets checked in together.

[se]

Final set of patches, including suggested additions to the man pages of df(1) and statfs(2).
The man pages will be committed with updated revision dates (not included in this review).

Testing with the script attached to PR 270053 (https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=270053) resulted in no errors.
But it seems that there are several issues in the msdosfs code, for which I'll open a new PR.

One interesting detail relevant for this patch is that the msdosfs code ignores the number of configured root directory entries, but uses a value that is rounded up to the next multiple of 16 (e.g. 129 would be rounded up to 144 entries), independently of the sector and cluster size. While the maximum number of root directory entries that can specified is 65535, this allows 65536 entries to be used. (I have no idea whether this is actually the behavior of FAT12/FAT16 on DOS or Windows, too.)

There are other issues, e.g. "newfs_msdos -F 12 -e 1024 -S 512" should create a file system that has 4084 clusters of 4 KB (or roughly 16 MB), but df shows its size as only 12288 KB (12 MB) and trying to write a file of size 12 MB results in an error since apparently 8 KB have already been allocated (for the "." entry?), but "ls -lask /mnt" shows a "." entry with an apparent size of 32 KB (which actually is synthetic and does not really exist on disk).

None of these values are consistent with each other and with what newfs_msdos has reported ...

Testing and trying to understand these details of the msdosfs implementation took much longer than I had anticipated, but I think the current implementation has the correct semantics with regard to the existing behavior and quirks of msdosfs.

[mckusick]

This looks ready to go to me. I concur with putting off your other issues for another change later.

One tiny nit which is not worth creating a whole new diff. Just do it at as part of your commit along with manual page date updates.

sys/fs/msdosfs/msdosfs_vfsops.c

413

These => file

[woodsb02]

lib/libc/sys/statfs.2

242

I just noticed the typo here - s/FAT13/FAT16/

[se]

lib/libc/sys/statfs.2

242

Thanks for reporting - this typo had already been reported and a fix has been committed as 9d33a9d96f5 within 2 hour of the commit of this typo ...