makefs: Make sure that directory entry order is consistent

[markj]

Summary

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). This fixes some sources of
reproducibility problems.

In mtree mode, for now I 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.

Sponsored by: Klara, Inc.
Sponsored by: The FreeBSD Foundation

[emaste]

In mtree mode, for now I let the ordering of METALOG entries determine
the ordering in the fsnode tree.

Certainly OK for now, especially as we can also address it outside of makefs (by sorting the METALOG before calling makefs).

[markj]

In D50197#1144980, @emaste wrote:

In mtree mode, for now I let the ordering of METALOG entries determine
the ordering in the fsnode tree.

Certainly OK for now, especially as we can also address it outside of makefs (by sorting the METALOG before calling makefs).

Yeah, that was my thinking too. There are some other sources of ordering differences which go away with such a change, e.g., from certctl -U, which in turn depends on the order of files printed by find(1). Using find -s works around that particular problem, but it's probably better to sort the METALOG than to play whack-a-mole.

[emaste]

usr.sbin/makefs/makefs.c

111

Interesting -- we often do this in the script/Makefile/etc. that invokes a tool like this, rather than in the tool itself.

For makefs though this is probably reasonable and appropriate, given that the current behaviour is effectively an arbitrarily sorted list today.

usr.sbin/makefs/walk.c

69–72

Probably worth a comment on these entries

95

minor nit, but i and cur are in opposite order in the 1st and 2nd case making it a bit more confusing

[markj]

usr.sbin/makefs/walk.c

95

Sorry, what do you mean by the first and second cases?

[emaste]

usr.sbin/makefs/walk.c

95

Oh, apparently I need my eyesight checked :)

I read it as i = 0, cur = list and cur != NULL, i++ which of course doesn't make sense.

[emaste]

Once committed I'll add an entry to https://salsa.debian.org/reproducible-builds/reproducible-website