[PATCH] libfs: walk offset directories in offset order

[Christian Brauner <brauner@kernel.org>]

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