Both arches: concurrent ext2 read-park vs write-spin is a livelock shape (root & home filesystems)

[ryanbreen]

Summary

#713 (x86 SPAWN syscall, fix/713-x86-spawn, merged via the #713 fix-round-2)
adds x86's first production path that lets a second userspace process exist
and touch the filesystem while another process's syscall is mid-flight. That
newly makes a pre-existing lock/parking shape on the ext2 filesystems
reachable in x86 production, on the gate's own -smp 1 configuration.

Both arches, both filesystems (widened by PR #744 review B1): the
lock/parking shape below is byte-identical, arch-neutral production code —
kernel/src/fs/ext2/mod.rs carries no #[cfg(target_arch)] anywhere near
it. aarch64 was originally checked and ruled NOT-LIVE on the theory that its
-smp 4+ configs structurally defuse the livelock; that reasoning was
falsified (see the corrected comment below) — the livelock generalizes to N
CPUs given N concurrent ext2 lock acquirers, and aarch64's stock boot
sequence already supplies most of that concurrency (4-5 fire-and-forget
service spawns, each an ext2 read, with no wait between them). What's
missing from today's aarch64 boot workload is one overlapping ext2 write
— a workload fact ("no boot service happens to write today"), not a
structural mitigation. An interactive bssh session doing rm/mkdir/etc.
while anything else reads (any exec, any sys_read) supplies it. This issue
is therefore latent-live on aarch64 too, not merely an x86 -smp 1 gate
artifact.

The same shape also exists on HOME_EXT2
(kernel/src/fs/ext2/mod.rs:1652, home_fs_write()/home_fs_read()) —
identical upgradeable_read().upgrade() / plain .read() construction,
never mentioned in the original filing. Any fix here must cover both
filesystems on both arches.

This is filed per this project's "any failure you find is your problem"
policy — the shape is pre-existing (every ext2 read has always done this),
but #713 is genuinely what makes it collidable on x86: before #713, x86
production booted exactly one userspace process (init) that never raced
itself against the filesystem. aarch64 has had multiprocess userspace for
longer, so the read-side concurrency precondition has been present there for
some time; only the write-side precondition is presently unmet by aarch64's
stock boot workload.

The shape

kernel/src/boot/init_image.rs::read_init_from_ext2 (used by sys_spawn,
kernel/src/syscall/handlers.rs:~2624) on x86; arch_impl/aarch64/syscall_entry.rs::load_elf_from_ext2
(used by sys_exec_aarch64/sys_spawn_aarch64) on aarch64 — same shape on
both:

pub fn read_init_from_ext2(path: &str) -> Result<Vec<u8>, &'static str> {
    let fs_guard = crate::fs::ext2::root_fs_read();   // ROOT_EXT2.read()
    let fs = fs_guard.as_ref().ok_or("ext2 root filesystem not mounted")?;
    let inode_num = fs.resolve_path(path).map_err(|_| "init not found")?;
    let inode = fs.read_inode(inode_num).map_err(|_| "failed to read inode")?;
    if inode.is_dir() { return Err("init is a directory"); }
    let elf_data = fs.read_file_content(&inode).map_err(|_| "failed to read init")?;
    // ^ VirtIO block read; may PARK the caller
    drop(fs_guard);
    Ok(elf_data)
}

ROOT_EXT2.read() (kernel/src/fs/ext2/mod.rs:1470/1573) is held across
fs.read_file_content(&inode), which issues a VirtIO block request and waits
on completion — a genuine scheduler park on both arches (x86:
kernel/src/drivers/virtio/block.rs:122, block_request_gate_can_sleep();
aarch64: block_mmio.rs's wait_for_completion →
Completion::wait_timeout_uninterruptible → block_current_for_io_with_timeout,
same arch-neutral completion.rs).

The write side, root_fs_write() (kernel/src/fs/ext2/mod.rs:1588), and its
HOME_EXT2 twin home_fs_write() (mod.rs:1652):

pub fn root_fs_write() -> spin::RwLockWriteGuard<'static, Option<Ext2Fs>> {
    ROOT_EXT2.upgradeable_read().upgrade()
}

is a spin (upgradeable-read-then-upgrade, spin crate's default
RelaxStrategy::Spin = a hardware pause with no OS yield, ever — arch
neutral), called from ordinary write syscalls any userspace process can
trigger — sys_open with O_CREAT, sys_write, unlink, rename,
mkdir, etc. (kernel/src/syscall/fs.rs, ten call sites total across both
filesystems; kernel/src/syscall/handlers.rs).

The collision

Both arches admit the same general shape: whenever one thread holds
WRITER (or has set UPGRADED en route to it) and parks for its own block
I/O, every other thread's attempt to acquire the same RwLock — reader or
upgrader — must spin non-yieldingly (no try_read-then-park fallback exists
at any of these call sites). If enough such spinners exist to occupy every
CPU simultaneously, the original lock-holder, though runnable once its own
I/O completes, has no CPU left to be dispatched on. Work-stealing needs an
idle CPU; there is none. The block-I/O completion timeout does not rescue
it — observing a timeout itself requires being scheduled. Unbounded
livelock.

x86 (-smp 1, the prod-profile gate's own configuration): trivial case,
N=1 — a single spinning writer alone monopolizes the only CPU that could
ever run the parked reader it's waiting on.

aarch64 (-smp 4+, Parallels 8 vCPUs): needs N concurrent ext2 lock
acquirers, N = CPU count. Stock boot already supplies N-1 of them (4-5
services' own spawn-time exec, each an ext2 read, fired with no wait between
launches) — see the corrected analysis in the comment below for exactly why
this is a workload fact today, not a structural mitigation, and what closes
the remaining gap.

This is a real starvation/livelock shape, not merely a slow path. It is
pre-existing (exec() and every ordinary file read do the same
park-while-holding-the-read-lock thing on both arches), but #713 is what
gave x86 production its first second process able to be the collider;
aarch64 has had that precondition for longer via its own multiprocess boot
sequence.

Why not fixed in #713 itself

#713's own diff does not introduce this lock/parking pattern — it only
(indirectly, via sys_spawn) creates the first x86-production scenario where
a second concurrent filesystem-touching process exists. The fix belongs to
the ext2 locking design (kernel/src/fs/ext2/mod.rs), which is out of
#713's diff surface, and is arch-neutral (both ROOT_EXT2 and HOME_EXT2,
both arches). Filing per the review's C5-adjacent finding rather than
silently absorbing it.

Suggested directions (not prescriptive)

• Make root_fs_write()/home_fs_write()'s spin itself parkable/yield-aware
  when preempt_count() > 0, mirroring how the read side already parks
  instead of spinning.
• Or: never hold ROOT_EXT2/HOME_EXT2's read or write guard across a
  block I/O wait at all — copy inode metadata out under the lock, drop it,
  then issue the block read/write against a snapshot, re-validating after
  reacquiring if the filesystem could have changed underneath.

Either direction, applied once, covers both locks and both arches — the
code is shared.

Provenance

Found during the #713 x86 SPAWN review (fix/713-x86-spawn), citing the
review's own N5 analysis. Not independently reproduced with a live hang in
this pass (the 25+ boot batteries never collided two real processes on
-smp 1 this way — spawn_smoke_target exits before bsshd starts a
client) — filed as a structural risk with exact file:line evidence, not a
reproduced incident. The aarch64/HOME_EXT2 scope was added by a follow-up
verification pass (PR #744 review B1) after an initial aarch64-specific
check incorrectly concluded NOT-LIVE; see the corrected comment below for
the full aarch64 analysis and what it superseded.

[ryanbreen]

CORRECTION (PR #744 review B1): the aarch64 NOT-LIVE reasoning below was falsified — the livelock is latent-live on both arches, not -smp 1-specific

The verdict below originally read "NOT-LIVE, x86-scoped as filed" and rested on three claims that do not hold up against the kernel's own source. This edit corrects the mechanism and the disposition; #728 itself is being re-scoped to both arches (see the issue title/body).

The three false claims, and what's actually true

1. "a writer spinning on upgrade() occupies only one CPU" — true only for the upgrade-spin itself (upgradeable_read() is exclusive against other upgraders, so at most one thread is ever mid-upgrade() for ROOT_EXT2 at a time). It does not follow that the livelock needs only one CPU. Once a write-family syscall actually becomes the WRITER and then parks for its own block I/O — the shape this issue itself describes (sys_unlink/sys_write/mkdir/etc., ten root_fs_write() call sites in kernel/src/syscall/fs.rs) — any other thread calling ROOT_EXT2.read() while WRITER is held must spin at acquisition: root_fs_read() is literally ROOT_EXT2.read(), no try_read fallback, and spin 0.9.8's read() loop is R::relax() (core::hint::spin_loop_hint()) — a hardware pause with no OS yield, ever. Each such reader is its own non-yielding spinner, on its own CPU.

2. (implicit) that ordinary readers park rather than spin — false whenever they attempt acquisition while WRITER (or UPGRADED) is already set. The kernel's own doc comment on the exact function this issue cites states the design intent outright: "The upgradeable guard sets the UPGRADED bit, which causes try_read() to reject new readers" (kernel/src/fs/ext2/mod.rs:1580-1589). A reader that already holds its guard before the writer starts genuinely parks across its own I/O — that half of the original analysis was right — but a new acquisition attempt made during the writer's window spins, not parks.

3. "a real, verifiable structural property of aarch64's actual configs ... not an 'it hasn't happened yet' coincidence" — this was the load-bearing overclaim, and it is exactly an "it hasn't happened yet" property. Stock aarch64 boot already fires 4-5 processes whose own spawn-time exec is a concurrent ROOT_EXT2.read() with no wait between launches (heartbeat, bsshd, then xhci_counters/bwm/telnetd fired in a loop with no wait) — i.e. "3+ concurrent readers beyond the writer" is the normal aarch64 boot shape, not a contrived edge case. The only missing ingredient is one of those concurrent windows overlapping an ext2 write — nothing in stock boot issues one today, but any interactive shell doing rm/mkdir/mv/etc. while anything else reads (any exec, any sys_read) supplies it.

Corrected mechanism (aarch64, -smp 4, no -smp 1 needed, no 4-way write pressure needed)

1. One write-family syscall takes root_fs_write() and then parks for block I/O while holding WRITER (e.g. sys_unlink → fs.unlink_file() under the guard, kernel/src/syscall/fs.rs:1472; the same holds for the other nine root_fs_write() call sites).
2. Every concurrent ext2 reader (exec/spawn's load_elf_from_ext2, or sys_read) hard-spins in ROOT_EXT2.read(), inside its own preempt-disabled syscall dispatch bracket (kernel/src/arch_impl/aarch64/syscall_entry.rs:83..184 brackets the whole dispatch in preempt_disable()/preempt_enable(), exactly like x86).
3. Four such readers pin all four CPUs. The parked writer is runnable (its own I/O has completed) but has no CPU to be dispatched on — work-stealing needs an idle CPU, and there is none. The 5s BLOCK_MMIO_COMPLETION_TIMEOUT_NS does not rescue it: observing a timeout requires being scheduled. Unbounded livelock.

This generalizes cleanly: the livelock needs N non-yielding spinners — readers spinning in ROOT_EXT2.read(), or the mirror image of a writer spinning in upgradeable_read() — occupying all N CPUs, plus one further thread that already holds the opposing guard and has parked for its own I/O (a writer holding WRITER, or the mirror image: a reader that already holds its guard) — it is not -smp 1-specific in any way. A parked thread occupies no CPU, so it is never one of the N; it is the (N+1)th participant whose CPU never comes free. -smp 1 is simply the trivial case, N=1: a single spinning reader already occupies the only CPU that the parked writer would otherwise be dispatched on.

What's still correctly true from the original pass (unchanged by this correction)

The read side genuinely parks once it holds its own guard (syscall_sleep_path_available() is true in aarch64 syscall context, completion.rs:131-139); every aarch64 QEMU config really is -smp 4+ (Parallels: 8 vCPUs), and none runs -smp 1; aarch64's scheduler has real cross-CPU work-stealing (scheduler.rs:1895-1937); and the per-CPU-stack steal decline does not pin an ordinary parked reader (percpu_stack_home_cpu returns None for heap-backed kernel stacks, scheduler.rs:2634).

Corrected disposition

• #728 is being re-scoped to cover both arches (title/body updated) — the lock/parking shape is byte-identical production code on aarch64, and aarch64's boot workload already supplies the concurrent-reader half of the collision; only a concurrent write is missing from today's stock boot sequence, which is a workload fact, not a structural mitigation.
• The true remaining basis for this not firing in current aarch64 gates: no aarch64 boot service issues an ext2 write during the window where 3+ other services are mid-spawn-exec — heartbeat/xhci_counters/bsshd/bwm/telnetd only touch procfs/devfs there. That basis breaks the moment a write-capable interactive session (bssh) overlaps any concurrent read, which is an ordinary, expected usage pattern, not a contrived one.
• HOME_EXT2 (kernel/src/fs/ext2/mod.rs:1652, home_fs_write()/home_fs_read()) has the identical upgradeable_read().upgrade() / plain .read() shape and was never mentioned in the original analysis — any fix to this issue must cover both filesystems, not just ROOT_EXT2.
• No fix attempted here — the lock-discipline change (park-aware upgrade, or never holding the lock across block I/O) is its own arc, tracked by this issue's existing "Suggested directions" section.

---

(This comment previously cited an ephemeral session-local scratchpad path as its supporting analysis. That is not a durable citation for a public issue; the full corrected reasoning is now inlined above instead.)

[ryanbreen]

OBSERVED reproduction of the corrected livelock shape (unattributed)

While re-verifying mmap.rs's F7/F8 edits during PR #744's review-fix round, a full boot beyond the required gates stalled indefinitely at sys_mkdir("/var").

Command: ./docker/qemu/run-boot-parallel.sh 1

Config: the script's own default — x86_64, -machine pc,accel=tcg -cpu qemu64 -smp 1 -m 512 (docker/qemu/run-boot-parallel.sh:93,115) — the exact -smp 1 configuration this issue originally filed against.

Stall marker: the kernel serial log's last line, with no further output for 8.5+ minutes (900s harness timeout) before the run was killed by hand:

[DEBUG] kernel::syscall::fs: sys_mkdir: path="/var", mode=0o755

sys_mkdir is a root_fs_write() call site. At the point of the stall, bwm/blog/bounce/bcheck/blogd had all already been spawned (each spawn's own exec is a concurrent ROOT_EXT2.read()), with active concurrent syscall dispatch visible immediately beforehand across multiple threads — the shape this issue (as corrected) describes, at the trivial N=1 case.

Honest note: this was not attributed to the branch it was observed on (fix/742-743-mmap-census, PR #744). That branch's diff touches no kernel/src/fs/ext2/ code, no locking primitive, and no scheduler code (layout.rs comment-only; mmap.rs's MAP_FIXED doc comment and sys_munmap's checked_add) — by inspection it cannot be the producer. It was a single occurrence, not reproduced a second time or bisected to identify which concurrent reader collided with the mkdir.

Full kernel/user serial logs and the harness's own runner output are preserved in-repo: docs/planning/green-program/nic-bus/serials/728-live-repro/ — offered as a possible repro path for whoever picks up this issue's actual fix, not as evidence about how reliably it reproduces.