Date: Thu, 8 May 2025 16:03:57 GMT From: Mark Johnston <markj@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 31c3ef95ec43 - main - makefs: Make sure that directory entry order is consistent Message-ID: <202505081603.548G3v5u073390@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by markj: URL: https://cgit.FreeBSD.org/src/commit/?id=31c3ef95ec430d130363a664e96135eb7abebd7b commit 31c3ef95ec430d130363a664e96135eb7abebd7b Author: Mark Johnston <markj@FreeBSD.org> AuthorDate: 2025-05-08 15:50:23 +0000 Commit: Mark Johnston <markj@FreeBSD.org> CommitDate: 2025-05-08 15:50:23 +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 --- 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 7646c1c0f6be..d85b9c2668e7 100644 --- a/usr.sbin/makefs/makefs.c +++ b/usr.sbin/makefs/makefs.c @@ -43,6 +43,7 @@ #include <ctype.h> #include <errno.h> #include <limits.h> +#include <locale.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -103,6 +104,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 b2afa9e78094..dc03a16cf2c6 100644 --- a/usr.sbin/makefs/walk.c +++ b/usr.sbin/makefs/walk.c @@ -59,6 +59,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 -- @@ -71,7 +115,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]; @@ -95,10 +139,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; @@ -136,10 +178,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) { @@ -160,24 +198,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; @@ -204,13 +229,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 *
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202505081603.548G3v5u073390>