vault

RCU-Walk and Ref-Walk

17 min read

RCU-Walk and Ref-Walk

Linux walks a pathname in one of two concurrency-management modes, and the same fs/namei.c code runs both. REF-walk (“reference walk”) is the safe, heavy mode: it takes a counted reference and sometimes a spinlock on each dentry and vfsmount as it descends, so nothing it is holding can be freed or renamed out from under it. RCU-walk (“RCU walk,” also called lazy walk) is the fast, optimistic mode: it takes no references and no locks at all, instead reading per-object seqlocks (sequence counters) and checking afterwards that nothing changed. Pathname lookup always starts in RCU-walk, “dances lightly down the cached filesystem image leaving no footprints,” and only drops to REF-walk when it hits something it cannot do losslessly (per path-lookup.rst, v6.12). The payoff is scalability: incrementing a refcount on a hot dentry like / or /usr on every lookup bounces that cache line between every CPU in the system; RCU-walk touches nothing, so thousands of cores can resolve /usr/lib/... in parallel without contending. This note explains how the walk is made safe; its sibling Path Resolution and Name Lookup explains what the walk resolves — they are orthogonal.

This note describes Linux 6.12 LTS (released 2024-11-17), grounded in the in-tree Documentation/filesystems/path-lookup.rst and the fs/namei.c, fs/dcache.c, and lib/lockref.c source at the v6.12 tag. The framing follows Neil Brown’s LWN “RCU-walk” article (2015); where the 2015 prose and the 6.12 source differ, the source is authoritative.

Why Two Modes Exist — The Hot-Dentry Problem

Path lookup is overwhelmingly read-mostly: the directory tree above any given file (/, /usr, /usr/lib) changes almost never, but is traversed by essentially every process constantly. REF-walk’s correctness comes from taking a reference count on each dentry it steps onto — but a reference count is a write to shared memory. When every CPU resolving any path under /usr increments and decrements the refcount on the /usr dentry, that single cache line ping-pongs between all cores, and the atomic operation stalls waiting for exclusive ownership of the line. On a large multi-socket machine this turns a logically read-only traversal into a write-contention bottleneck.

This is the exact problem the lockref primitive (which backs dentry->d_lockref) was created to soften, and that RCU-walk was created to avoid entirely. Lockref fuses a spinlock and a reference count into one 8-byte word so that “lock; increment; unlock” can often execute as a single cmpxchg; Jonathan Corbet reported it gave “a factor of six” improvement on a filesystem benchmark on a large system when it was merged in the 3.12 cycle (Corbet, “Introducing lockref,” LWN, 2013-09-04). But even a single atomic cmpxchg on a shared line is a contended write. RCU-walk’s insight is that for the read-mostly common case you can avoid the write altogether: “the goal when reading a shared data structure that no other process is changing is to avoid writing anything to memory at all. Take no locks, increment no counts, leave no footprints” (path-lookup.rst).

stateDiagram-v2
  [*] --> RCU: filename_lookup starts<br/>with LOOKUP_RCU
  RCU --> RCU: component found in dcache,<br/>seqlocks still valid<br/>(no locks, no refs)
  RCU --> REF: try_to_unlazy() succeeds<br/>(grab refs, validate seqlocks)<br/>e.g. cache miss, must sleep
  RCU --> RESTART: -ECHILD<br/>seqlock changed, or<br/>unlazy failed
  RESTART --> REF: restart from top<br/>in REF-walk mode
  REF --> REF: take ref + d_lock per step;<br/>retry on rename_lock change
  REF --> REVAL: -ESTALE<br/>stale cache entry
  REVAL --> REVAL: restart with LOOKUP_REVAL,<br/>force ->d_revalidate
  REF --> [*]: complete_walk() ok
  REVAL --> [*]: complete_walk() ok

The two-mode walk as a state machine. What it shows: every lookup begins in RCU-walk and stays there as long as each component is in the dcache and the seqlocks it sampled remain unchanged. When it must do something RCU-walk cannot (sleep, take i_rwsem, allocate, follow a hard case), it tries try_to_unlazy() to convert in place to REF-walk; if that conversion fails because something changed, it returns -ECHILD and the whole walk restarts from the top in REF-walk. A stale entry in REF-walk triggers one more restart with forced revalidation. The insight to take: RCU-walk never converts back to RCU once it leaves, and a failed conversion is cheap because the lost work is just re-walking a tree that is almost entirely in cache.

RCU-Walk’s Two Guarantees: RCU for Existence, Seqlocks for Consistency

RCU-walk rests on a precise division of labor. The rcu_read_lock() is held for the entire descent, and it provides exactly one guarantee: the key objects — dentries, inodes, superblocks, and mounts — will not be freed while the lock is held. They may be unlinked, renamed, or invalidated, but their memory will not be repurposed, so reading their fields will not fault or return garbage from an unrelated object (path-lookup.rst). This works because dentries and inodes are freed via kfree_rcu() (or an RCU callback), which defers the actual free until all CPUs have left their RCU read-side critical sections.

RCU alone is not enough, because an object can still change (be renamed, have its inode swapped) while you read it. Consistency is handled by seqlocks (sequence locks). A seqlock is a counter that a writer increments before and after every modification; a reader samples it before reading (read_seqcount_begin), does its read, and re-samples after (read_seqcount_retry). If the counter changed, a write was in progress and the read must be retried or abandoned. Crucially, read_seqcount_retry() also imposes a memory barrier, so that no read instruction issued before the retry can be reordered to after it — without this, the CPU could speculatively read a field, then the seqcheck would pass, but the field value would be from after a concurrent write. The places where REF-walk takes a reference or a lock are exactly the places where RCU-walk samples and checks a seqlock; this is what preserves the invariant that RCU-walk only ever makes a decision that REF-walk could also have made at the same instant.

There are three seqlocks in play, each stored as a sample in the nameidata:

  • mount_lock / nd->m_seq — a global seqlock over the entire mount table. RCU-walk samples it once at the start (m_seq) and re-checks it on every mount crossing and at the end. Any mount or unmount anywhere bumps it, forcing a fallback. Because mounts change rarely, one global counter for all vfsmount accesses is a fine trade (Mount Point Traversal During Lookup).
  • dentry->d_seq / nd->seq — a per-dentry seqlock (seqcount_spinlock_t d_seq in struct dentry). nd->seq always holds the sampled sequence of the current dentry; it must be re-validated before trusting the dentry’s name, parent, or inode. This is the workhorse that catches a d_move() (rename) racing with the walk.
  • rename_lock / nd->r_seq — a global rename seqlock. REF-walk uses it to retry hash-chain scans that a rename disturbed; RCU-walk samples it (r_seq) but mostly uses it only for the scoped-lookup .. attack checks (see below), since a missed dentry in RCU-walk already triggers a fallback.

The inode pointer gets special treatment: it is needed at least twice (to test for NULL and to check permissions), so rather than re-validate on each touch, RCU-walk copies dentry->d_inode into nd->inode once and then reads the copy freely.

The Lockless dcache Lookup — __d_lookup_rcu vs __d_lookup

The clearest place to see the two modes side by side is the dentry-cache hash lookup, where both modes scan the same RCU-protected hash chain but defend themselves differently. The RCU version (fs/dcache.c, v6.12):

hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
	unsigned seq;
	seq = raw_seqcount_begin(&dentry->d_seq);   /* sample this dentry's seqlock */
	if (dentry->d_parent != parent)  continue;
	if (d_unhashed(dentry))          continue;
	if (dentry->d_name.hash_len != hashlen) continue;
	if (dentry_cmp(dentry, str, hashlen_len(hashlen)) != 0) continue;
	*seqp = seq;                                 /* hand the seq back to the caller */
	return dentry;
}

It reads each candidate’s d_seq, compares parent/name optimistically, and returns the sequence number to the caller — which must itself do a read_seqcount_retry before doing anything meaningful with the dentry. No lock is taken on any candidate. Contrast the REF version, __d_lookup:

hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
	if (dentry->d_name.hash != hash) continue;
	spin_lock(&dentry->d_lock);                  /* take d_lock on this candidate */
	if (dentry->d_parent != parent)  goto next;
	if (d_unhashed(dentry))          goto next;
	if (!d_same_name(dentry, parent, name)) goto next;
	dentry->d_lockref.count++;                   /* take a counted reference */
	found = dentry;
	spin_unlock(&dentry->d_lock);
	break;
next:
	spin_unlock(&dentry->d_lock);
}

Same chain, same comparisons — but __d_lookup takes d_lock on each candidate it examines and, on a match, increments d_lockref.count to pin the result. The RCU version writes nothing; the REF version writes a spinlock acquisition per candidate and a refcount increment on the winner. That write traffic is precisely what RCU-walk eliminates on the hot path. (Both scan an RCU-protected list, hence both sit inside rcu_read_lock() — note that “RCU-protected hash list” and “RCU-walk” are different uses of RCU; __d_lookup is the REF-walk lookup despite using rcu_read_lock to walk the list safely.)

lookup_fast() is the only lookup routine RCU-walk uses (lookup_slow() requires i_rwsem and can sleep, both forbidden under rcu_read_lock). Inside lookup_fast’s RCU branch you can see the hand-over-hand seqlock dance that mirrors REF-walk’s hand-over-hand refcounting:

dentry = __d_lookup_rcu(parent, &nd->last, &nd->next_seq); /* get child + its seq */
...
if (read_seqcount_retry(&parent->d_seq, nd->seq))          /* re-validate the *parent* */
	return ERR_PTR(-ECHILD);

It samples the new child’s seq (next_seq), then re-validates the old parent’s seq one last time — exactly as REF-walk grabs a reference on the new dentry before dropping the reference on the old one. If the parent’s seq changed, something moved mid-step and it bails with -ECHILD.

Dropping Out — unlazy_walk / try_to_unlazy

RCU-walk cannot do everything. When the next step needs something only REF-walk can provide — a cache miss requiring lookup_slow (which sleeps), a permission check on a network filesystem that must contact a server, an automount, an atime update, certain symlinks — the walk tries to convert in place from RCU-walk to REF-walk rather than throw away the descent it has already done. This conversion is unlazy_walk(), named because RCU-walk is “lazy walk”; in 6.12 the function is try_to_unlazy() (and try_to_unlazy_next() when a next dentry has already been picked).

The conversion’s job is to retroactively take all the references RCU-walk skipped, then verify that nothing changed while it was lazy. From fs/namei.c (v6.12):

static bool try_to_unlazy(struct nameidata *nd)
{
	struct dentry *parent = nd->path.dentry;
	BUG_ON(!(nd->flags & LOOKUP_RCU));
	if (unlikely(!legitimize_links(nd)))  goto out1;   /* refs on stacked symlinks */
	if (unlikely(!legitimize_path(nd, &nd->path, nd->seq))) goto out; /* ref on current */
	if (unlikely(!legitimize_root(nd)))   goto out;    /* ref on the pinned root */
	leave_rcu(nd);                                      /* drop rcu_read_lock, clear LOOKUP_RCU */
	BUG_ON(nd->inode != parent->d_inode);
	return true;
out1:
	nd->path.mnt = NULL;  nd->path.dentry = NULL;
out:
	leave_rcu(nd);
	return false;
}

legitimize_path() is where “take a reference and check it was safe” happens. It takes a reference on the vfsmount (validated against m_seq) and on the dentry, then re-checks the dentry’s d_seq:

static bool __legitimize_path(struct path *path, unsigned seq, unsigned mseq)
{
	int res = __legitimize_mnt(path->mnt, mseq);            /* ref the mount, check mount_lock */
	if (unlikely(res)) { ... return false; }
	if (unlikely(!lockref_get_not_dead(&path->dentry->d_lockref)))  /* ref the dentry... */
		{ path->dentry = NULL; return false; }
	return !read_seqcount_retry(&path->dentry->d_seq, seq);  /* ...iff its seq is unchanged */
}

Two subtleties make this harder than a plain refcount bump:

  1. lockref_get_not_dead, not a bare increment. You can only safely increment a refcount you can prove is still alive. A dentry being torn down has its d_lockref.count set to the sentinel -128 by lockref_mark_dead() (lib/lockref.c, v6.12); lockref_get_not_dead() increments only if the count is >= 0, returning 0 (failure) for a dead dentry. So RCU-walk can grab a reference on a live dentry but correctly fails to grab one on a dying dentry, falling back to a full restart.
  2. The mount reference may be unsafe to drop normally. If __legitimize_mnt got a reference but mount_lock validation then fails, an unmount may have progressed past the point of no return. Dropping that reference with a normal mnt_put() could be wrong, so legitimize_mnt() checks the MNT_SYNC_UMOUNT flag to decide whether to mnt_put() or just silently decrement and “pretend none of this ever happened” (path-lookup.rst).

If any legitimize step fails, try_to_unlazy returns false, the caller propagates -ECHILD, and the entire lookup restarts from the top in REF-walk. If it succeeds, leave_rcu() drops the RCU read lock and clears LOOKUP_RCU, and the walk continues from where it was, now in REF-walk. RCU-walk never re-enters once it has left — the in-tree doc notes the trip-up points are usually near the leaves, so there is little benefit in switching back.

There are also cases that bail without try_to_unlazy: when mount_lock or a d_seq already shows a change, the function simply returns -ECHILD directly, because there is nothing to legitimize — the state is already known-inconsistent. complete_walk(), called at the end of every lookup, also calls try_to_unlazy() to finish an RCU-walk by legitimizing the final result before returning it to the caller.

The Three-Attempt Escalation

The mode machinery is visible at the top level in filename_lookup() / do_filp_open(), which call path_lookupat() (or path_openat()) up to three times:

retval = path_lookupat(&nd, flags | LOOKUP_RCU, path);            /* 1. RCU-walk */
if (unlikely(retval == -ECHILD))
	retval = path_lookupat(&nd, flags, path);                /* 2. REF-walk */
if (unlikely(retval == -ESTALE))
	retval = path_lookupat(&nd, flags | LOOKUP_REVAL, path);  /* 3. REF + force revalidate */

The error codes are the signaling channel between the modes:

  • -ECHILD (“child,” the historical errno reused here) means “RCU-walk could not proceed losslessly — retry in REF-walk.” It is not surfaced to userspace; it triggers attempt 2.
  • -ESTALE means a cached dentry turned out to be stale (typically a network filesystem whose ->d_revalidate rejected it). It triggers attempt 3 with LOOKUP_REVAL, which forces ->d_revalidate to “trust no cache” and re-check every entry against the server.

Because attempt 1 covers the overwhelming common case (everything cached, nothing changing), the expensive attempts 2 and 3 are rare. This is the same optimistic-first structure described from the algorithm side in Path Resolution and Name Lookup.

Filesystem Cooperation Under RCU-Walk

RCU-walk usually never calls into the concrete filesystem at all — it lives in cached data. But three filesystem hooks can run during RCU-walk and must be written to tolerate it:

  • i_op->permission — for filesystems with non-standard permission checks (e.g. a network FS that consults a server). Under RCU-walk it is passed an extra MAY_NOT_BLOCK flag and must return -ECHILD if it cannot answer without sleeping. It receives only the inode pointer, so it needs no further consistency checks, but any other structures it touches must be RCU-safe.
  • d_op->d_revalidate — for filesystems that revalidate cached dentries (NFS, etc.). Under RCU-walk it gets the dentry but not the inode or seq, so it must use READ_ONCE() on fields and check for NULL (see nfs_lookup_revalidate), or return -ECHILD to force a fallback.
  • i_op->get_link — for symlinks. Under RCU-walk the dentry* argument is NULL; the filesystem may use GFP_ATOMIC to grab the link content without sleeping, or return -ECHILD to fall back. See Symlink Resolution and Loop Detection.

Uncertain

Verify: the claim that RCU-walk only follows symlinks whose body is stored inline in the inode (so ext4’s inline symlinks work in RCU-walk but page-cache-backed symlinks on XFS/Btrfs/NFS force a drop to REF-walk). Reason: the in-tree path-lookup.rst makes this statement but appends “That support is not likely to be long delayed,” and that sentence is inherited verbatim from Neil Brown’s 2015 LWN article — it is a 2015 prediction, not a checked 6.12 fact. To resolve: trace i_op->get_link for ext4, xfs, and btrfs symlinks at the v6.12 tag and confirm which return -ECHILD under RCU (dentry == NULL). uncertain

Why REF-Walk Still Needs rename_lock (and RCU-Walk Does Not)

REF-walk searches a dcache hash chain by computing a hash from (name, parent), indexing the table, and scanning the chain. A concurrent d_move() (rename) can change a dentry’s name and parent, moving it to a different chain mid-scan — so a scan could follow a dentry onto the wrong chain and miss the entry it wanted. d_lookup() does not prevent this; it detects it with the rename_lock seqlock and simply retries the scan. RCU-walk does not bother with rename_lock: when __d_lookup_rcu fails to find a name (whether truly absent or missed due to a racing rename), RCU-walk already drops to REF-walk and retries with proper locking, which handles the case correctly anyway. Adding rename_lock checks to RCU-walk would add cost for no benefit (path-lookup.rst).

The one place RCU-walk does consult rename_lock (and mount_lock) is the scoped-lookup .. security check: under LOOKUP_BENEATH/LOOKUP_IN_ROOT (RESOLVE_BENEATH/RESOLVE_IN_ROOT), an attacker who renames or moves a directory mid-walk could make .. jump above the intended root, bypassing the path_equal() confinement check. handle_dots() re-checks both seqlocks after a .. and bails with -EAGAIN if either changed, defeating the race (man openat2).

Failure Modes and How to Observe Them

  • Persistent -ECHILD fallback (RCU-walk “not sticking”). A workload constantly modifying a directory in the lookup path (rapid create/unlink in a hot directory) bumps d_seq so often that RCU-walk repeatedly bails to REF-walk, losing the scalability win and adding the cost of the failed RCU attempt on top of the REF-walk. Symptom: high d_lock/d_lockref contention in perf top (look for lockref_get, __d_lookup, d_lock) despite paths being cached. The fix is usually structural (spread the churn across more directories).
  • -ESTALE storms on network filesystems. A server-side change invalidating many cached dentries drives repeated attempt-3 LOOKUP_REVAL walks; visible as elevated ->d_revalidate and round-trips in NFS tracing.
  • Subtle: the memory-barrier requirement. A filesystem ->d_revalidate or ->permission that reads dentry fields without READ_ONCE/NULL-checks under RCU-walk can dereference a field that is being concurrently overwritten. This is not a “performance” bug but a correctness one; the symptom is rare, hard-to-reproduce oopses under load on a networked FS.

Alternatives and Trade-offs

RCU-walk is not free everywhere — it is a read-mostly optimization. For a directory under heavy modification, the seqlock retries can cost more than just doing REF-walk from the start, but the kernel cannot know that in advance, so it always tries RCU first. The historical alternative — pre-2.6.38 lookup that took the dcache_lock global spinlock — was a notorious scalability bottleneck; the RCU-walk work (Nick Piggin’s dcache scalability series, merged 2.6.38, 2011) removed it. Lockref (3.12, 2013) then made the REF-walk fallback itself far cheaper, so the two together give a graceful curve: lockless on the hot path, cheap fused lock/refcount on the warm path, full locking only on the cold path (Corbet, LWN 2013).

Uncertain

Verify: the kernel version that first merged RCU-walk (cited above as 2.6.38, 2011, Nick Piggin’s dcache-scalability series) and lockref (3.12, 2013). Reason: these historical merge versions are from secondary recollection and the LWN lockref article, not re-confirmed against the merge commits at this writing. To resolve: check git log --oneline for the __d_lookup_rcu/LOOKUP_RCU introduction and the lockref introduction commit tags. The 6.12 behavior described above is grounded in the v6.12 source; only the historical “introduced in” versions are flagged. uncertain

See Also

Graph View

Backlinks