Huge directories

[Guy Harris]

>Except on systems that perform directory compaction (rumored to be true
>for 4.nBSD, n >= 2, although I've never seen it happen),

I don't know that I've seen 4.xBSD perform directory compacting, in the
sense of shuffling entries within a block to coalesce several empty
spaces in that block.  Then again, I've never looked for it....

I have, however, seen a system with the 4.3BSD directory *shrinking*
code shrink a directory, i.e. do the moral equivalent of an "truncate"
on it when the last block is empty.  4.2BSD doesn't do that; n must be
>= 3 for that to happen.

Note that directories are compacted when a new entry is made, not when
an entry is removed.  I can think of two reasons why they might have
chosen to do it then, as opposed to doing it when entries are removed:

	1) It may cut down on "hunting", i.e. if a directory is just
	   barely big enough to require N blocks, deleting the last
	   entry and then creating a new entry that goes into the last
	   block won't cause the last block to be deleted and then
	   reallocated.

	2) It was easier that way.  When removing an entry, you stop the
	   directory search when you find the entry, rather than
	   scanning to the end of the directory; in order to decide
	   whether to truncate a directory, you have to scan all the way
	   to the end.  When creating a new directory entry, the
	   directory is scanned all the way to the end (to make sure
	   there isn't already an entry with that name).

I have no idea which, if any, of those is the reason why; there may well
be a third reason.  I currently have no opinion on whether it should be
done when an entry is created or when one is removed.