[PATCH] libfs: walk offset directories in offset order

[PATCH] libfs: walk offset directories in offset order

[Christian Brauner]

offset_iterate_dir() walks d_children from the head and only uses the
maple tree to map ctx->pos back to a dentry when a getdents64() call
resumes. offset_dir_lookup() finds the entry at ctx->pos, or the one
with the next lower offset if it is gone, and the list walk continues
from there.

That only works if list order and offset order agree and quite often
they don't. A rename over an existing name gives the moved dentry the
offset of the name it replaced but __d_move() puts it at the head of
d_children. RENAME_EXCHANGE does the same to both dentries. And once
the cyclic offset allocator wraps new entries get low offsets at the
head of the list.

So if the entry at ctx->pos is unlinked between two getdents64() calls
we resume at the entry with the next lower offset and that one can sit
anywhere in the list:

(1) If it sits further down the list everything in between is skipped.
    Create y, t, a, b and rename b over t. The list is now t(4) a(5)
    y(3). Stop the listing at t and unlink t. The next call resumes at
    y and a is never returned although nobody touched it.

(2) If there is no lower entry we restart at the head and return the
    whole directory again. Nickolai reported this for the simple case
    of unlinking the oldest entry while a listing is about to reach it.
    Ending the walk there instead turns this into (1): create a, b, c,
    rename c over a, stop the listing at the renamed entry, unlink it,
    and b is lost.

Instead of the list let's walk the maple tree itself in descending
offset order. Then ctx->pos really means that everything above it has
been emitted and resuming at the highest offset at or below it is right
no matter where the dentry sits in d_children. Entries created or
renamed to a new name after the listing started get an offset above
ctx->pos and aren't returned, same as with the list walk which never
went back to the head. So a readdir loop that renames or creates an
entry for each one it reads still terminates.

The maple tree can't change under us as all modifications happen with
the directory's i_rwsem held exclusive and offset_readdir() holds it
shared.

Fixes: b9b588f22a0c ("libfs: Use d_children list to iterate simple_offset directories")
Fixes: f70681e9e606 ("libfs: Fix duplicate directory entry in offset_dir_lookup")
Reported-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
Link: https://patch.msgid.link/20261018024549.798968-1-nickolai@csail.mit.edu
Signed-off-by: Christian Brauner (Amutable) <brauner@kernel.org>
---
 fs/libfs.c | 56 ++++++++++++++++++++++----------------------------------
 1 file changed, 22 insertions(+), 34 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index 96a6e9b1535f..8d5de5f61ffd 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -446,31 +446,11 @@ static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence)
 	return vfs_setpos(file, offset, LONG_MAX);
 }
 
-static struct dentry *find_positive_dentry(struct dentry *parent,
-					   struct dentry *dentry,
-					   bool next)
-{
-	struct dentry *found = NULL;
-
-	spin_lock(&parent->d_lock);
-	if (next)
-		dentry = d_next_sibling(dentry);
-	else if (!dentry)
-		dentry = d_first_child(parent);
-	hlist_for_each_entry_from(dentry, d_sib) {
-		if (!simple_positive(dentry))
-			continue;
-		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
-		if (simple_positive(dentry))
-			found = dget_dlock(dentry);
-		spin_unlock(&dentry->d_lock);
-		if (likely(found))
-			break;
-	}
-	spin_unlock(&parent->d_lock);
-	return found;
-}
-
+/*
+ * Find the entry with the highest offset at or below @offset. Entries are
+ * emitted in descending offset order, so this is the next entry to emit
+ * when resuming at @offset.
+ */
 static noinline_for_stack struct dentry *
 offset_dir_lookup(struct dentry *parent, loff_t offset)
 {
@@ -480,14 +460,19 @@ offset_dir_lookup(struct dentry *parent, loff_t offset)
 
 	MA_STATE(mas, &octx->mt, offset, offset);
 
-	if (offset == DIR_OFFSET_FIRST)
-		found = find_positive_dentry(parent, NULL, false);
-	else {
-		rcu_read_lock();
-		child = mas_find_rev(&mas, DIR_OFFSET_MIN);
-		found = find_positive_dentry(parent, child, false);
-		rcu_read_unlock();
+	if (offset < DIR_OFFSET_MIN)
+		return NULL;
+
+	rcu_read_lock();
+	while ((child = mas_find_rev(&mas, DIR_OFFSET_MIN))) {
+		spin_lock(&child->d_lock);
+		if (simple_positive(child))
+			found = dget_dlock(child);
+		spin_unlock(&child->d_lock);
+		if (found)
+			break;
 	}
+	rcu_read_unlock();
 	return found;
 }
 
@@ -504,7 +489,10 @@ static void offset_iterate_dir(struct file *file, struct dir_context *ctx)
 	struct dentry *dir = file->f_path.dentry;
 	struct dentry *dentry;
 
-	dentry = offset_dir_lookup(dir, ctx->pos);
+	if (ctx->pos == DIR_OFFSET_FIRST)
+		dentry = offset_dir_lookup(dir, DIR_OFFSET_MAX);
+	else
+		dentry = offset_dir_lookup(dir, ctx->pos);
 	if (!dentry)
 		goto out_eod;
 	while (true) {
@@ -514,7 +502,7 @@ static void offset_iterate_dir(struct file *file, struct dir_context *ctx)
 		if (!offset_dir_emit(ctx, dentry))
 			break;
 
-		next = find_positive_dentry(dir, dentry, true);
+		next = offset_dir_lookup(dir, ctx->pos - 1);
 		dput(dentry);
 
 		if (!next)

---
base-commit: b44341e39d856e4cc6ad8ed94ebffd440f39846c
change-id: 20261030-work-libfs-offset_readdir-807d3b774260

Re: [PATCH] libfs: walk offset directories in offset order

[Chuck Lever]

On 10/30/26 11:58 AM, Christian Brauner wrote:
> Instead of the list let's walk the maple tree itself in descending
> offset order. Then ctx->pos really means that everything above it has
> been emitted and resuming at the highest offset at or below it is right
> no matter where the dentry sits in d_children. Entries created or
> renamed to a new name after the listing started get an offset above
> ctx->pos and aren't returned, same as with the list walk which never
> went back to the head. So a readdir loop that renames or creates an
> entry for each one it reads still terminates.

The descending walk is what the 2023 offset-ordered iteration was
missing. That one walked ascending, so every new entry landed ahead
of the cursor, which is how generic/736 broke it. Walking down from
DIR_OFFSET_MAX with cyclic allocation puts new entries behind the
cursor until the offset space wraps. And because the allocator is
unchanged, a cookie an NFS client presents after an unbounded delay
still resolves to a nearby survivor rather than to a recycled entry.
So, OK.

Rename-over comes out better than the list walk too: the surviving
name keeps the victim's offset and now also keeps the victim's
position in the listing, where __d_move() drags it to the head of
d_children today.

Before I want to add an Ack or Reviewed-by:

1. Each emitted entry now costs a fresh MA_STATE and a full tree
   descent in offset_dir_lookup(), where the list walk was one
   pointer chase. Can you time an ls on a tmpfs directory with a
   million entries, before and after? If it is noticeable, carrying
   the mas across the loop is the obvious fix, though dput() and
   dir_emit() interleaving makes that especially fiddly.


> The maple tree can't change under us as all modifications happen with
> the directory's i_rwsem held exclusive and offset_readdir() holds it
> shared.

2. That's true today, but Jon Flynn's RFC from yesterday proposes
   create and unlink with the parent locked shared. The code is
   fine either way: it runs under rcu_read_lock() and takes d_lock
   before dget_dlock(), so the walk does not depend on i_rwsem.
   Should the patch description say that the RCU path is what
   makes the walk safe, and i_rwsem is belt-and-suspenders?

3. Please run generic/736 on tmpfs directly and on a tmpfs export
   over NFS, and Nickolai's reproducer from the Link: above. I used
   a seek-after-closedir case as a regression test for the NFS
   resume case too, but my memory is hazy as to whether it actually
   could demonstrate proper function vs. a bug.


-- 
Chuck Lever (Come to NFS bake-a-thon! https://nfsv4bat.org)