UFS Subdirectory limit.

[David Malone]

There was a discussion on comp.unix.bsd.freebsd.misc about two weeks
ago, where someone had an application that used about 150K
subdirectories of a single directory. They wanted to move this
application to FreeBSD, but discovered that UFS is limited to 32K
subdirectories, because UFS's link count field is a signed 16 bit
quantity. Rewriting the application wasn't an option for them.

I had a look at how hard it would be to fix this. The obvious route
of increasing the size of the link count field is trickly because
it means changing the struct stat, which has a 16 bit link count
field. This would imply ABI breakage, though it might be worth it.

I had a think about other ways to fix this problem. One way around
this limitation is to change the link count semantics so that ".."
doesn't contribute to a directories link count (this may seem silly,
but I've included a bit of a rational below). I've produced a patch
at:

	http://www.maths.tcd.ie/~dwmalone/dircount_hack

which adds options to newfs (-D) and tunefs (-d) that set a new
flag in the filesystem making it use this new link counting scheme.
(If you enable the flag with tunefs you should run fsck to recalculate
the link count.) The patch also makes filesystems with this flag
be of type "wfs", so that fts knows not to use the link-count-stat
shortcut.

I'd appreciate any feedback on this patch. Please don't use it on
important filesystems, as it may chew your files! I've done some
basic testing, including making a directory with 70K subdirectories,
and it seems to work.

	David.

---

Originally, I guess the link count was used to decide when you can
free the blocks belonging to a file. As directories are basically
implemented as files, they inherit link counts. However today, the
real test for "can you deallocate a directory" is "is it empty".
Thus the link count for directories isn't authoritative for
deallocation, though it does provide a shortcut (nlink > 2 => not
empty).

The link count also provides some extra consistency that fsck can
check. However, as far as I can tell, the link count doesn't provide
any extra information that can actually be used to fix inconsistencies.

The other place that directory link counts are used is as a short
cut in userland when estimating the number of subdirectories that
a directory has. This is used in the fts code to avoid stating
things. Since this shortcut only works for ufs-like filesystems,
we already have code for dealing with this.