2 — `open()`: the path walk

How does open("/etc/hosts") turn a string into a struct file, and why is the second call so much faster than the first?

Requirements: the machine from chapter 0, with an ext4 root. Confirm with findmnt /, because an overlay root changes everything here.

The path

Step 1: get a file descriptor. __x64_sys_openat calls do_sys_openat2 (fs/open.c), which runs build_open_flags, reserves a free fd with get_unused_fd_flags, and calls do_filp_open.

Step 2: try the optimistic walk. do_filp_open calls path_openat (fs/namei.c), which allocates the struct file with alloc_empty_file and starts walking in RCU-walk mode: no locks, no reference counts, just sequence counters.

Step 3: walk each component. link_path_walk loops over the path’s components. For each one it hashes the name with hash_name and calls walk_component, which tries lookup_fast. That searches the dentry cache (__d_lookup_rcu): hash, bucket, compare the parent and name.

On a hit, move on to the next component.
On a miss, the walk doesn’t start over. It converts to ref-walk in place through try_to_unlazy, then calls lookup_slow. That takes the parent’s inode lock, allocates a dentry with d_alloc_parallel, and asks the filesystem through inode->i_op->lookup. On ext4 that’s ext4_lookup, which reads the directory and may hit disk. This is why the first call is slow.

Step 4: handle the special cases. Mountpoints are crossed in traverse_mounts and __follow_mount_rcu. Symlinks go through pick_link, and MAXSYMLINKS (40) is a running total for the whole walk (namei.c).

Step 5: open the last component. open_last_lookups and do_open finish the job. may_open calls inode_permission, which checks mode bits and ACLs, plus security_inode_permission for the LSM.

Step 6: connect it. vfs_open calls do_dentry_open (fs/open.c), which sets f_op = inode->i_fop, runs security_file_open, and calls f_op->open(). Finally fd_install publishes the fd. It comes last so a racing read() on that number can’t see a half-built file.

Hands-on: trace it

Check the names on your build:

cd /sys/kernel/tracing
grep -E -w 'lookup_fast|__lookup_slow|lookup_slow|path_openat|do_dentry_open|ext4_lookup' available_filter_functions

lookup_slow is inlined on some builds, so use __lookup_slow.

Count real dcache misses for a minute. The argument is a struct qstr:

bpftrace -e 'kprobe:__lookup_slow { @[comm, str(((struct qstr *)arg0)->name)] = count(); }'

Compare cold and warm. sync first, so dirty data can be dropped:

sync; echo 3 > /proc/sys/vm/drop_caches
echo path_openat > set_graph_function
echo 12 > max_graph_depth
echo function_graph > current_tracer
cat /etc/hosts > /dev/null          # cold
cp trace /tmp/cold.txt; echo > trace
cat /etc/hosts > /dev/null          # warm
cp trace /tmp/warm.txt
echo nop > current_tracer; echo > set_graph_function
grep -c -E 'lookup_slow|ext4_lookup' /tmp/cold.txt /tmp/warm.txt

Look for: __lookup_slow and ext4_lookup in the cold trace, and none for that path in the warm one. cat also opens libraries, so read the context rather than the total.
Compare echo 2 with echo 3. Both force lookups, but only echo 3 should reliably add block reads. Add tracepoint:block:block_rq_issue to confirm.

Hands-on: change it

Part 1: find the symlink limit

mkdir /tmp/l && cd /tmp/l && touch f
ln -s f l1; for i in $(seq 2 41); do ln -s l$((i-1)) l$i; done
cat l40; echo rc=$?
cat l41; echo rc=$?

Expected: l40 works and l41 fails with “Too many levels of symbolic links”.

Part 2: patch the kernel

Add a log line to the slow path:

--- a/fs/namei.c
+++ b/fs/namei.c
@@ static struct dentry *lookup_slow(const struct qstr *name,
 	struct inode *inode = dir->d_inode;
 	struct dentry *res;
+	pr_info_ratelimited("lookup_slow: %.*s\n", name->len, name->name);
 	inode_lock_shared(inode);

This diff is illustrative, so apply it by hand. Rebuild, boot, and run dmesg | grep lookup_slow.

Expected: you should recognize the names from early boot. This shows what the system looks up when everything is cold.

If it fails

kprobe:lookup_slow says no such function: it’s inlined. Use __lookup_slow.
No slow path at all: the path is already cached. Drop caches first.
Odd results everywhere: check findmnt / for an overlay root.

The takeaway

Optimistic first, pessimistic on conflict. RCU-walk assumes nothing will change under it and verifies with sequence counters; only on contention does it fall back to locking. The dcache turns an O(path-length × disk) operation into O(path-length) hash lookups. Both are the same idea: make the common case lock-free and cheap, and make the rare case correct. Your systems have a dcache-shaped problem somewhere; this is the reference design.

2 — open(): the path walk