The branch stable/14 has been updated by markj:
URL:
https://cgit.FreeBSD.org/src/commit/?id=1e3b1b09c3b3f723125ddeb414466c05afa7771d
commit 1e3b1b09c3b3f723125ddeb414466c05afa7771d
Author: Mark Johnston <ma...@freebsd.org>
AuthorDate: 2025-05-08 15:50:23 +0000
Commit: Mark Johnston <ma...@freebsd.org>
CommitDate: 2025-06-20 12:46:09 +0000
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
(cherry picked from commit 31c3ef95ec430d130363a664e96135eb7abebd7b)
---
usr.sbin/makefs/makefs.c | 8 +++++
usr.sbin/makefs/walk.c | 83 ++++++++++++++++++++++++++++++------------------
2 files changed, 60 insertions(+), 31 deletions(-)
diff --git a/usr.sbin/makefs/makefs.c b/usr.sbin/makefs/makefs.c
index e02571f42997..e8e9fbf99bc3 100644
--- a/usr.sbin/makefs/makefs.c
+++ b/usr.sbin/makefs/makefs.c
@@ -44,6 +44,7 @@
#include <ctype.h>
#include <errno.h>
#include <limits.h>
+#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
@@ -104,6 +105,13 @@ main(int argc, char *argv[])
setprogname(argv[0]);
+ /*
+ * Set the locale for collation, so that directory entry sorting is
+ * consistent.
+ */
+ if (setlocale(LC_COLLATE, "C") == NULL)
+ err(1, "setlocale");
+
debug = 0;
if ((fstype = get_fstype(DEFAULT_FSTYPE)) == NULL)
errx(1, "Unknown default fs type `%s'.", DEFAULT_FSTYPE);
diff --git a/usr.sbin/makefs/walk.c b/usr.sbin/makefs/walk.c
index 98ddb53f7917..12164ae78bd4 100644
--- a/usr.sbin/makefs/walk.c
+++ b/usr.sbin/makefs/walk.c
@@ -61,6 +61,50 @@ static void apply_specentry(const char *, NODE *,
fsnode *);
static fsnode *create_fsnode(const char *, const char *, const char *,
struct stat *);
+static int
+cmp(const void *_a, const void *_b)
+{
+ const fsnode * const *a = _a;
+ const fsnode * const *b = _b;
+
+ assert(strcmp((*a)->name, (*b)->name) != 0);
+ if (strcmp((*a)->name, ".") == 0)
+ return (-1);
+ if (strcmp((*b)->name, ".") == 0)
+ return (1);
+ return (strcoll((*a)->name, (*b)->name));
+}
+
+/*
+ * Sort the entries rather than relying on the order given by readdir(3),
+ * which might not be reproducible.
+ */
+static fsnode *
+sort_dir(fsnode *list)
+{
+ fsnode **array;
+ fsnode *cur;
+ size_t nitems, i;
+
+ nitems = 0;
+ for (cur = list; cur != NULL; cur = cur->next)
+ nitems++;
+ assert(nitems > 0);
+
+ array = malloc(nitems * sizeof(fsnode *));
+ if (array == NULL)
+ err(1, "malloc");
+ for (i = 0, cur = list; cur != NULL; i++, cur = cur->next)
+ array[i] = cur;
+ qsort(array, nitems, sizeof(fsnode *), cmp);
+ for (i = 0; i < nitems; i++) {
+ array[i]->first = array[0];
+ array[i]->next = i == nitems - 1 ? NULL : array[i + 1];
+ }
+ cur = array[0];
+ free(array);
+ return (cur);
+}
/*
* walk_dir --
@@ -73,7 +117,7 @@ static fsnode *create_fsnode(const char *, const char
*, const char *,
fsnode *
walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join)
{
- fsnode *first, *cur, *prev, *last;
+ fsnode *first, *cur;
DIR *dirp;
struct dirent *dent;
char path[MAXPATHLEN + 1];
@@ -97,10 +141,8 @@ walk_dir(const char *root, const char *dir, fsnode *parent,
fsnode *join)
first = cur = join;
while (cur->next != NULL)
cur = cur->next;
- prev = cur;
} else
- first = prev = NULL;
- last = prev;
+ first = NULL;
while ((dent = readdir(dirp)) != NULL) {
name = dent->d_name;
dot = 0;
@@ -138,10 +180,6 @@ walk_dir(const char *root, const char *dir, fsnode
*parent, fsnode *join)
for (;;) {
if (cur == NULL || strcmp(cur->name, name) == 0)
break;
- if (cur == last) {
- cur = NULL;
- break;
- }
cur = cur->next;
}
if (cur != NULL) {
@@ -162,24 +200,11 @@ walk_dir(const char *root, const char *dir, fsnode
*parent, fsnode *join)
cur = create_fsnode(root, dir, name, &stbuf);
cur->parent = parent;
- if (dot) {
- /* ensure "." is at the start of the list */
- cur->next = first;
- first = cur;
- if (! prev)
- prev = cur;
- cur->first = first;
- } else { /* not "." */
- if (prev)
- prev->next = cur;
- prev = cur;
- if (!first)
- first = cur;
- cur->first = first;
- if (S_ISDIR(cur->type)) {
- cur->child = walk_dir(root, rp, cur, NULL);
- continue;
- }
+ cur->next = first;
+ first = cur;
+ if (!dot && S_ISDIR(cur->type)) {
+ cur->child = walk_dir(root, rp, cur, NULL);
+ continue;
}
if (stbuf.st_nlink > 1) {
fsinode *curino;
@@ -206,13 +231,9 @@ walk_dir(const char *root, const char *dir, fsnode
*parent, fsnode *join)
cur->symlink = estrdup(slink);
}
}
- assert(first != NULL);
- if (join == NULL)
- for (cur = first->next; cur != NULL; cur = cur->next)
- cur->first = first;
if (closedir(dirp) == -1)
err(1, "Can't closedir `%s/%s'", root, dir);
- return (first);
+ return (sort_dir(first));
}
static fsnode *
