From nobody Fri Jun 20 13:52:17 2025 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4bNzS22MNbz5y44B; Fri, 20 Jun 2025 13:52:18 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R11" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4bNzS166dkz3XYK; Fri, 20 Jun 2025 13:52:17 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750427537; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=R2NkSLTNbupRDwe3gbLSEJMz2H7m9CVCJijl9wv2Z6s=; b=yPVY4lhJrx12zGBBvYDJB7jSXfV59lW6PSqZgKwjPVy6oVIManZHN9zZ3ER+FMV7i/VksI u6G1zO42HnfWU38GFT6YLiJvCTzB+PCOOZSS8CV+ifjYJcUuhy/gfFig9BxsFCbS94Jb9y sKdULGIyqUbCmGWVk4wHtiEgcfeNUMgvLdB3+QRrT0qY9wgW3YW9KjGAoZ8+lwtBK7AGiN u+gaRhMPfbg2/Zqqq6lrEMzEpeZY3hICoOiMmynBuICDko7QVwi50469cpOfLfXqgBouGa ljnUbjg53ttxey6ujHig5fB0cAmosJ2EpS9Lja66wEL1YOkkuvfBKgOto2Y/UA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750427537; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=R2NkSLTNbupRDwe3gbLSEJMz2H7m9CVCJijl9wv2Z6s=; b=qHbPrR9jmP9miSGDHMfX7vI7NbjLe3gpLFMddXFxAoNvSZAYjZ6Lgal7peUTDDME6ycNVV MaEz95WmjkrjZbY43PqjJheCGg5XqsIWgVsLEsf7xElsa//m1NRIs0ScFil9fTgySwNhBJ +JcbTMnKpxuUGBKLVZ5MAFFyMXVytu5pCa/rxzI/mCW/ZNe6C3Ezra5U8dxkY2YoxuNBPl 0affORPRQtA3UhWSeATQ05m2QnKwxH0Ni6D9RqqN44gkQ9pvBgzD2PixwPfr3Xi8fWbcri 4+Sb/phtDqngOrQS6v1cLwZlwVydGUqC7uAnfn9c94NIcMdgquO0wn1fR5wLFQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1750427537; a=rsa-sha256; cv=none; b=inhVhdI7gPqUsAgOu2Qfs/mhZboQ9OkH5yCqDeJCtA9RX/2Z2C+vEsXiLxnBs7aoioKHH4 4MP2EBLoz0MbbU4IDGEEXoPbwfSsq+t9K0FboPlQrpJtwOeWPyYOJy0iH2zCDYXM3nNytA 1Ri032HVrOsTtOdZZYXCms1pTgV0mIXcGkwv3iyNFNcAF+G0fY+cJtxroEE7YWl+096IIQ C/KV7nhlZdPijOTTB6hNu29qe5rOSmMSfsMz+UFp5cd1LKxXttG2vsBYOn5bN/3dhRZKUT r6NBhUmI2Dk1sNnoY6uJzYyxhMGgXDVsMZsvpXBt7nFi1AlhBWTNp5UZw8MhbA== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4bNzS15kdJznCq; Fri, 20 Jun 2025 13:52:17 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.18.1/8.18.1) with ESMTP id 55KDqHso057882; Fri, 20 Jun 2025 13:52:17 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 55KDqHFI057879; Fri, 20 Jun 2025 13:52:17 GMT (envelope-from git) Date: Fri, 20 Jun 2025 13:52:17 GMT Message-Id: <202506201352.55KDqHFI057879@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Mark Johnston Subject: git: 1e3b1b09c3b3 - stable/14 - makefs: Make sure that directory entry order is consistent List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-all@freebsd.org Sender: owner-dev-commits-src-all@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: markj X-Git-Repository: src X-Git-Refname: refs/heads/stable/14 X-Git-Reftype: branch X-Git-Commit: 1e3b1b09c3b3f723125ddeb414466c05afa7771d Auto-Submitted: auto-generated The branch stable/14 has been updated by markj: URL: https://cgit.FreeBSD.org/src/commit/?id=1e3b1b09c3b3f723125ddeb414466c05afa7771d commit 1e3b1b09c3b3f723125ddeb414466c05afa7771d Author: Mark Johnston AuthorDate: 2025-05-08 15:50:23 +0000 Commit: Mark Johnston 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 #include #include +#include #include #include #include @@ -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 *