NextBSD unionfs inode-collision fix — design plan Design / proposal

Why distinct headers silently vanish during builds on the NextBSD live root (unknown type name 'GS_EXPORT', 'cups_lang_t', 'OBJC_PUBLIC', encode_NSInteger), why it's a unionfs (device,inode) collision and not a code bug, and a permanent kernel-side fix modelled on Linux overlayfs's xino. Companion to issue #332.

1. The bug, as observed

During make install of the GNUstep stack on the live root, clang fails on different files each layer of the build, always with the same shape — a type or macro that is defined in an included header is reported undefined:

Two tells point away from "broken code": (1) the #include/#import line itself raises no error — the failure surfaces far downstream at first use of the missing symbol; and (2) the identical sources build cleanly on stock FreeBSD. So the variable is the environment — specifically the filesystem — not the code.

1.1 Evidence from the box

$ mount | grep -iE 'union|cow'
<above>:/cow on / (unionfs, local)
tmpfs on /cow (tmpfs, local)

$ stat -f '%d  %N' /System/Library/Headers /usr/include /usr/local/include
1090584323  /System/Library/Headers
1090584323  /usr/include
1090584323  /usr/local/include          # one device id across all three trees

$ stat -f '%d:%i  %N' /usr/local/include/cups/language.h
1090584323:25678  /usr/local/include/cups/language.h   # low inode number → collision-prone

The live root is a unionfs: a writable tmpfs upper layer (/cow) over a read-only uzip/cd9660 lower layer, all presented under a single device id (1090584323). Inode numbers in each layer are allocated independently from low values, so collisions across layers are not just possible — they're likely for the densely-numbered early inodes that system headers occupy.

2. Root cause

Three facts combine into the bug.

2.1 clang identifies files by (device, inode), not path

clang's FileManager uniques files by inode so that two names for one file (symlinks, hardlinks) are treated as a single file. The identity token is llvm::sys::fs::UniqueID — a pair (Device, File) populated on POSIX directly from st_dev and st_ino. Distinct paths that stat to the same pair collapse onto one FileEntry:

// clang/lib/Basic/FileManager.cpp
// "See if we have already opened a file with the same inode.
//  This occurs when one dir is symlinked to another, for example."
FileEntry *&UFE = UniqueRealFiles[Status.getUniqueID()];

All three re-inclusion-skipping mechanisms — the multiple-include optimization (include guards), #pragma once, and Objective-C #import — record their state in a HeaderFileInfo keyed on that FileEntry identity, and consult it in HeaderSearch::ShouldEnterIncludeFile(). None of them is path-based.

2.2 unionfs collapses st_dev and passes inode numbers through

In FreeBSD/NextBSD unionfs (files sys/fs/unionfs/union_subr.c, union_vnops.c):

• One device id for the whole mount. unionfs_mount() calls vfs_getnewfsid(mp), and unionfs_getattr() overwrites every file's va_fsid with the mount's single fsid — so upper and lower files all report the same st_dev.
• Inode numbers pass straight through. unionfs_getattr() calls the underlying upper-or-lower VOP_GETATTR and rewrites only va_fsid; va_fileid (→ st_ino) is whatever the backing tmpfs or cd9660 returned. unionfs_readdir() likewise delegates wholesale to the underlying directory's VOP_READDIR, so each d_fileno is the raw underlying inode number.

Result: two genuinely different files — one upper, one lower — can carry the same (st_dev, st_ino).

2.3 The collision → silent skip

From clang's point of view this is the normal, desired behaviour that makes #pragma once work — it has no way to know the OS handed it two different files under one identity. That's why there is no warning at the include site.

3. Why there is no toolchain-side fix

This exact scenario (a union/FUSE overlay presenting colliding inodes to clang) was raised upstream and adjudicated: clang "determines if two different names refer to the same file based on the inode returned by stat()," and the resolution was that this is a filesystem bug, not a clang bug (the real-world fix there was the FUSE -o use_ino mount option). There is no -fno-… switch that reroutes #pragma once / #import / the multiple-include optimization off UniqueID and onto path strings — the identity key is structural in FileManager/HeaderSearch/Preprocessor, not policy-gated.

4. Prior art — Linux overlayfs xino

overlayfs hit this identical bug (it broke tar's hardlink detector, du -x, yum, and the same cpp include-once class) and fixed it in Linux 4.17 with the xino feature. The design is the template for our fix:

• One st_dev, tagged st_ino. Keep a single device id for the overlay mount and steal the high bits of st_ino to encode a per-layer fsid (upper = 0), partitioning one inode-number space across layers. The high bits are used "because the underlying filesystems rarely use the high inode number bits."
• Tag width scales with layer count. overlayfs uses ilog2(numfs - 1) + 2 bits, capped so it never exceeds 30, with one low bit of the tag region reserved for an overflow-mapping range. Layout: [ fsid tag | 1 reserved bit | real inode number ].
• Modes off/on/auto. on force-enables and warns (rate-limited) on overflow; auto enables when persistent st_ino is achievable and stays silent on the overflow fallback.
• Overflow is per-inode, never a hard failure. If a real inode number is too large to coexist with the tag, overlayfs keeps the pair unique by other means — real ino + a unique pseudo st_dev for non-dirs, or a non-persistent overlay ino for dirs — rather than colliding.
• Identity stability across copy-up is handled separately via the trusted.overlay.origin xattr / index, so a file's st_ino doesn't change when it's written and copied to the upper layer.
• 64-bit only. Setting high bits yields large inode numbers; on 32-bit ino_t, stat() returns EOVERFLOW rather than silently truncating (which would reintroduce collisions).

NextBSD's unionfs is simpler than overlayfs — exactly two layers (one upper, one lower), not an arbitrary stack — so a single tag bit suffices and the bit-budget arithmetic collapses to "set bit 63 for upper."

5. The fix — layer-tagged fileid in unionfs

5.1 Source layout & touch points

NextBSD builds against the FreeBSD tree (fork nextbsd-redux/freebsd-src) plus a thin patch series in nextbsd-kernel/patches/; no unionfs inode logic is currently patched out-of-tree. Note the FreeBSD file names are union.h / union_subr.c / union_vnops.c (functions are unionfs_*):

5.2 The helper

/* union.h */
#define UNIONFS_FILEID_UPPER_BIT  (1ULL << 63)

static __inline uint64_t
unionfs_remap_fileid(bool upper, uint64_t id)
{
    return (upper ? (id | UNIONFS_FILEID_UPPER_BIT)
                  : (id & ~UNIONFS_FILEID_UPPER_BIT));
}
/* upper = (unp->un_uppervp != NULLVP) — the existing layer predicate */

5.3 unionfs_getattr()

Adjacent to the two existing va_fsid assignments (upper and lower return paths), after the underlying VOP_GETATTR succeeds:

/* upper path */
ap->a_vap->va_fsid   = ap->a_vp->v_mount->mnt_stat.f_fsid.val[0];
ap->a_vap->va_fileid |= UNIONFS_FILEID_UPPER_BIT;        /* NEW */

/* lower path */
ap->a_vap->va_fsid    = ap->a_vp->v_mount->mnt_stat.f_fsid.val[0];
ap->a_vap->va_fileid &= ~UNIONFS_FILEID_UPPER_BIT;       /* NEW (defensive) */

5.4 unionfs_readdir() — the hard half

Because VOP_READDIR writes struct dirent records (with d_fileno) directly into the caller's uio, the tag has to be applied after the underlying readdir but before the data reaches userspace. Route the three call sites through a helper that reads into a kernel bounce buffer, walks the dirents, tags each d_fileno, then uiomoves the rewritten block:

for (struct dirent *dp = kbuf; (char *)dp < kbuf + nbytes;
     dp = (struct dirent *)((char *)dp + dp->d_reclen)) {
    if (dp->d_reclen == 0) break;
    dp->d_fileno = unionfs_remap_fileid(upper, dp->d_fileno);
}
/* then uiomove(kbuf, nbytes, uio); preserve d_off / NFS cookie merge */

The upper flag is per source directory, not per entry: in the merged case the upper pass tags upper=true, the lower pass upper=false — correct, because each entry's fileid belongs to the layer whose directory produced it. This must agree with getattr or stat(2) and readdir(3) disagree, which breaks find, fts(3), and tar.

6. Alternatives considered

7. Risks & implications of the fix

The change is small in lines but touches core VFS paths (getattr, readdir) and changes a user-visible value (st_ino). The risks, with mitigations:

8. Testing & validation

8.1 Collision detector (run before & after)

FreeBSD stat -f: %d = st_dev, %i = st_ino. Distinct paths sharing a dev:ino are exactly what clang mis-dedups:

#!/bin/sh
# collide.sh — report DISTINCT regular-file paths sharing (st_dev, st_ino).
# Usage: ./collide.sh /usr/include /usr/local/include /System/Library/Headers /Developer
set -eu
tmp=$(mktemp /tmp/collide.XXXXXX); trap 'rm -f "$tmp"' EXIT
find "$@" -type f -print0 | xargs -0 stat -f '%d:%i	%N' | sort > "$tmp"
awk -F'\t' '{ if ($1==pk && $2!=pp){ if(!s[$1]++) print "COLLISION "$1"\n  "pp; print "  "$2 }
              pk=$1; pp=$2 }' "$tmp"
awk -F'\t' 'k[$1]++{c=1} END{exit !c}' "$tmp" && { echo "FAIL: dup (dev,ino)"; exit 1; }
echo "OK: every path has a unique (st_dev, st_ino)"

(True hardlinks legitimately share a pair; on the union root you expect zero shared keys between distinct logical files, so any hit is suspect — optionally cmp flagged pairs and only fail when contents differ.)

8.2 Kernel regression test (deliberate overlap)

Construct the pathological condition on purpose with two fresh backing FSes whose first files share a low inode number, union-mount, then assert every presented file has a distinct identity:

mdconfig -a -t swap -s 16m -u 0; newfs -U /dev/md0; mount /dev/md0 /mnt/lower
mdconfig -a -t swap -s 16m -u 1; newfs -U /dev/md1; mount /dev/md1 /mnt/upper
: > /mnt/lower/a.h        # first file on md0 → ino X
: > /mnt/upper/b.h        # first file on md1 → same ino X, different backing dev
mount_unionfs /mnt/upper /mnt/lower
n=$(find /mnt/lower -type f | wc -l)
u=$(find /mnt/lower -type f -print0 | xargs -0 stat -f '%d:%i' | sort -u | wc -l)
[ "$n" -eq "$u" ] || { echo "FAIL: union presents colliding (dev,ino)"; exit 1; }

A correct fix makes n == u. Wire it in as a kyua/ATF test so it runs on every kernel build. Add a companion test asserting stat ↔ d_fileno agreement (R5), including ./...

8.3 End-to-end

Clean-rebuild the real workload in dependency order on the union root and grep the logs for the collision signatures:

for p in libs-base libs-gui libs-back; do ( cd /Developer/Library/Sources/$p && gmake clean && gmake 2>&1 | tee /tmp/$p.log ); done
! grep -E 'unknown type name|undeclared|undefined macro|implicit declaration' /tmp/libs-*.log
./collide.sh /usr/include /usr/local/include /System/Library/Headers /Developer

Pass = all three link, zero collision-signature errors, and the detector reports a clean sweep.

9. Implementation checklist & rollout

1. Add UNIONFS_FILEID_UPPER_BIT + unionfs_remap_fileid() to union.h.
2. Tag va_fileid in both unionfs_getattr() return paths.
3. Bounce-buffer + tag d_fileno in unionfs_readdir()'s three call sites; preserve d_off/cookie merge.
4. Mount-time guard (R4): refuse/῾fallback if a backing FS can emit inode numbers ≥ 2⁶³.
5. kyua/ATF tests: deliberate-overlap uniqueness, stat↔readdir agreement, copy-up inode change.
6. Carry as nextbsd-kernel/patches/0007-unionfs-layer-tagged-fileid.patch + series entry; gate behind mount_unionfs -o xino if you want it opt-in initially.
7. Benchmark readdir-heavy paths (R2) before/after.
8. Retire the inode-bust sweep from the build scripts once CI is green on the patched kernel.
9. Propose upstream to FreeBSD (R9).

10. Open questions

Appendix A — inodes, df, and the "2.1G ifree" question

Background for reading the live root's storage state, and a units gotcha worth pinning down because it looks alarming and isn't.

A.1 What an inode is

An inode ("index node") is the structure that stores everything about one file except its name: type, permissions, owner, timestamps, size, link count, and pointers to the data blocks. The name lives separately, in the directory entry that points at the inode. Every file, directory, and symlink consumes exactly one inode — and the (st_dev, st_ino) pair from that inode is the very identity clang keys include-once on (§2.1), which is what this whole plan is about.

A filesystem therefore has two independent capacity limits, and either can be exhausted alone:

• Bytes — data-block space (df's Size/Used/Avail).
• Inodes — how many files, regardless of size (df's iused/ifree/%iused).

A million tiny files can use every inode while gigabytes of bytes sit free; one huge file can fill the bytes with inodes to spare.

A.2 The inode columns — and the units gotcha

A.3 Sample from the live root

$ df -h
Filesystem            Size   Used  Avail Capacity iused  ifree %iused  Mounted on
<above>:/cow           13G   6.9G   6.1G    53%    143k   2.1G    0%   /
/dev/md0             7.1M   3.5M   3.0M    54%      31    991    3%   /
/dev/md1.uzip        6.3G   5.6G   173M    98%    115k   9.7k   92%   /rofs
tmpfs                6.7G   606M   6.1G     9%     18k   2.1G    0%   /cow

A.4 Why ~2.1G, and why it isn't the RAM number

2.1G is right around 2³¹ (≈ 2,147,483,648) — the signed-32-bit max. That's tmpfs's default way of saying "don't meaningfully cap by inode count." It is a default ceiling, not anything derived from physical memory.

The limit that is memory-derived is the byte size: tmpfs is RAM-backed, so FreeBSD defaults its Size to roughly available memory (≈ 6.7 G of an 8 GB box, the rest reserved for the kernel). The 6.1 G Avail on /cow is the real build budget, and it's the ceiling that actually binds — every file also costs memory, so you'd exhaust those 6.1 GB (file data + inode structures) long before creating 2 billion files. Inode count: effectively infinite. Byte size: the one to watch.

A.5 Reading the rest of the rows

Bottom line: 0% inodes used and 6.1 G of byte-space free — the live root is neither inode- nor space-constrained for builds.

A.6 Tie-back to the collision bug

The huge ifree count and the inode numbering are unrelated. tmpfs hands out inode numbers sequentially from low values as files are created (hence language.h = 25678, GSVersionMacros.h = 14323), which is exactly why they collide with the low-numbered system headers on the lower layer (§2.2). Having billions of free inodes does nothing to spread the numbers apart — only the high-bit layer tag in §5 does that.

11. References

• Issue: nextbsd-redux/nextbsd#332 — COW overlay inode collisions cause Clang to silently skip source headers
• FreeBSD unionfs source: sys/fs/unionfs (union.h, union_subr.c, union_vnops.c, union_vfsops.c)
• clang file identity: FileManager · UniqueID.h · HeaderSearch.cpp · PPDirectives.cpp
• "filesystem bug, not clang bug": cfe-dev — using clang on unionfs (the -o use_ino precedent)
• overlayfs xino: Documentation/filesystems/overlayfs.rst · ovl_map_dev_ino · commit 926e94d7 (auto-enable + overflow fallback)
• 32-bit overflow: stat(2) — EOVERFLOW · FreeBSD stat(1) (%d/%i)
• Companion plans: live-root overlay, livecd unionfs