makefs: Make sure that directory entry order is consistent
When walking a directory hierarchy (as opposed to reading an mtree),
makefs builds up a tree of file nodes. Within a directory, the order of
the sibling nodes is determined by the order they're returned by
readdir(), which isn't very reproducible (e.g., depends on filesystem,
build parallelism).
Add a routine which sorts entries within a directory after its contents
have been read. This is a bit more expensive, but I wasn't able to
measure a significant runtime cost (and I don't think makefs has been
optimized very much to begin with), and we avoid this cost in mtree mode
anyway. This fixes some sources of reproducibility problems.
In mtree mode, for now we let the ordering of METALOG entries determine
the ordering in the fsnode tree. It might be worth sorting these too,
since with parallel installworld they won't have a consistent ordering,
and single-threaded installworld is pretty slow.
Reviewed by: emaste
MFC after: 1 month
Sponsored by: Klara, Inc.
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D50197