From nobody Thu May 8 16:03:57 2025 X-Original-To: dev-commits-src-main@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 4ZtcPn2vNqz5vGQZ; Thu, 08 May 2025 16:03:57 +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 4ZtcPn27f5z4Lcf; Thu, 08 May 2025 16:03:57 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1746720237; 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=+rw/R9hkHtUIFczBDKPTOtfhOkcQKtFWfFeA35l9e18=; b=RLGz/F+/Oa+aj6Eg8kQXMyUouayNFVskxMBTMamKyLE/K6HCbO7TTfl0Bg8vYYmKNkg9TK gTzxF317p/L/MuVuFSEBsrFwcKoAIlKtISam4UlBqZzXhMZgUKTYFX8XiArbSlcmfxcaMs uZei5dKy+LnModQj4qJ7E9stEmEUnCD0FtAC1MSv4ecgjFHEHpVT+Yr/5Ip1Ex4LwYSM7E SPe8m0s+IJO2LXEHfohkF5bopojRSlxeKNQEEAKEcpntuQIEcDo2dP87q7hslTh2jrDzBx ftNiLsQojT/WHcrqTiLYVjhKtysSZpAp8uuUoqGwcHcNe7VAWS41zoILIIW0TA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1746720237; 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=+rw/R9hkHtUIFczBDKPTOtfhOkcQKtFWfFeA35l9e18=; b=S/+9xVyVwdwhFQCMx8x5Jo67UmY78pDTi01HO6wvqWAuh7xX+JraF+BC1Llp8qjc0gC93m JYH3wMxFWndpsi38Wz4vDlBR/46IuCS46dGLeQ7ntRPQfbCgpar9IjwtIwpWJpN6nAZ0sL hkNC+InotixcvRWa+AA0TNOxD2wsrQo3YELTdVBKAyZaF6YW5WpvOr8K1cZwa340LVTVSC UFAIbf5NBp6273aJUFyMbToYpyIyOwU4et0dbLisblpRmCeiYaQRmChiwKz/iD3jNU2MTa Uaih2nQU11vGgUMBHiQgjtyw1qgnzxYO8kFcu/6C5RJ1vlRs37G78cRxfnOnFA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1746720237; a=rsa-sha256; cv=none; b=kDNmqfT1ebL590jbrvGKzdzAeU8E/nWQ3uTjDeliiPwdXYdHKRMVoYPdGzAjozrkgBabyn D7PIwx4UQdVhU8TTMn9HwBUUIVmAO4yS3sq3ciuoRtZnweSRp+7ub2VSVzVHtfgwtnxcoo Wu+vjgDMzDsABSYnnJWDbWwhwqYmdrtYE8A613t91+y0QyMa2mlj0Z7E3JgDo1UXSYxYhj F9jUOEq4/qjJFHu3G+CV8DRpbJ2XESc+eOFnmBbP2AsqcPg0RYBNjouV3XiucVi+n8i32Q meq+fyEa4bCk2vtqpkD/ILAfFseCvgPT8/9mwPjx7f4lyq+RPep0Ss75UQwSMQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none 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 4ZtcPn1CSXz5vZ; Thu, 08 May 2025 16:03:57 +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 548G3vRh073393; Thu, 8 May 2025 16:03:57 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 548G3v5u073390; Thu, 8 May 2025 16:03:57 GMT (envelope-from git) Date: Thu, 8 May 2025 16:03:57 GMT Message-Id: <202505081603.548G3v5u073390@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Mark Johnston Subject: git: 31c3ef95ec43 - main - makefs: Make sure that directory entry order is consistent List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@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/main X-Git-Reftype: branch X-Git-Commit: 31c3ef95ec430d130363a664e96135eb7abebd7b Auto-Submitted: auto-generated The branch main has been updated by markj: URL: https://cgit.FreeBSD.org/src/commit/?id=31c3ef95ec430d130363a664e96135eb7abebd7b commit 31c3ef95ec430d130363a664e96135eb7abebd7b Author: Mark Johnston AuthorDate: 2025-05-08 15:50:23 +0000 Commit: Mark Johnston 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 #include #include +#include #include #include #include @@ -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 *