Improve simple directory offset wrap behavior

EBUSY O_EXCL was specified in flags and pathname refers
to a block device that is in use by the system (e.g., it is mounted).

From: Chuck Lever <[email protected]>

The mtree mechanism has been effective at creating directory offsets that are stable over multiple opendir instances. However, it has not been able to handle the subtleties of renames that are concurrent with readdir.

Instead of using the mtree to emit entries in the order of their offset values, use it only to map incoming ctx->pos to a starting entry. Then use the directory's d_children list, which is already maintained properly by the dcache, to find the next child to emit.

One of the sneaky things about this is that when the mtree-allocated offset value wraps (which is very rare), looking up ctx->pos++ is not going to find the next entry; it will return NULL. Instead, by following the d_children list, the offset values can appear in any order but all of the entries in the directory will be visited eventually.

Note also that the readdir() is guaranteed to reach the tail of this list. Entries are added only at the head of d_children, and readdir walks from its current position in that list towards its tail.

Signed-off-by Chuck Lever <[email protected]>

---
  fs/libfs.c | 77 ++++++++++++++++++++++++++++++++++++++++--------------
  1 file changed, 57 insertions(+), 20 deletions(-)

fs/libfs.c +2 -1

index fcb2cdf6e3f3..398eac385094 100644
@@ -243,12 +243,13 @@ EXPORT_SYMBOL(simple_dir_inode_operations);
 
  /* simple_offset_add() allocation range */
  enum {
-	DIR_OFFSET_MIN		= 2,
+	DIR_OFFSET_MIN		= 3,
  	DIR_OFFSET_MAX		= LONG_MAX - 1,
  };
 
  /* simple_offset_add() never assigns these to a dentry */
  enum {
+	DIR_OFFSET_FIRST	= 2,		/* Find first real entry */
  	DIR_OFFSET_EOD		= LONG_MAX,	/* Marks EOD */
 
  };

fs/libfs.c +52 -18

  {
-	MA_STATE(mas, &octx->mt, offset, offset);
+	struct dentry *found = NULL;
+
+	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;
+	}
+	return found;
+}
+
+static noinline_for_stack struct dentry *
+offset_dir_lookup(struct file *file, loff_t offset)
+{
+	struct dentry *parent = file->f_path.dentry;
  	struct dentry *child, *found = NULL;
+	struct inode *inode = d_inode(parent);
+	struct offset_ctx *octx = inode->i_op->get_offset_ctx(inode);
+
+	MA_STATE(mas, &octx->mt, offset, offset);
 
  	rcu_read_lock();
  	child = mas_find(&mas, DIR_OFFSET_MAX);
  	if (!child)
  		goto out;
-	spin_lock(&child->d_lock);
-	if (simple_positive(child))
-		found = dget_dlock(child);
-	spin_unlock(&child->d_lock);
+
+	spin_lock(&parent->d_lock);
+	found = find_next_sibling_locked(parent, child);
+	spin_unlock(&parent->d_lock);
  out:
  	rcu_read_unlock();
  	return found;

@@ -477,30 +502,42 @@ static struct dentry *offset_find_next(struct offset_ctx *octx, loff_t offset)
  static bool offset_dir_emit(struct dir_context *ctx, struct dentry *dentry)
  {
  	struct inode *inode = d_inode(dentry);
-	long offset = dentry2offset(dentry);
 
-	return ctx->actor(ctx, dentry->d_name.name, dentry->d_name.len, offset,
-			  inode->i_ino, fs_umode_to_dtype(inode->i_mode));
+	return dir_emit(ctx, dentry->d_name.name, dentry->d_name.len,
+			inode->i_ino, fs_umode_to_dtype(inode->i_mode));
  }
 
-static void offset_iterate_dir(struct inode *inode, struct dir_context *ctx)
+static void offset_iterate_dir(struct file *file, struct dir_context *ctx)
  {
-	struct offset_ctx *octx = inode->i_op->get_offset_ctx(inode);
+	struct dentry *dir = file->f_path.dentry;
  	struct dentry *dentry;
 
+	if (ctx->pos == DIR_OFFSET_FIRST) {
+		spin_lock(&dir->d_lock);
+		dentry = find_next_sibling_locked(dir, d_first_child(dir));
+		spin_unlock(&dir->d_lock);
+	} else
+		dentry = offset_dir_lookup(file, ctx->pos);
+	if (!dentry)
+		goto out_eod;
+
  	while (true) {
-		dentry = offset_find_next(octx, ctx->pos);
-		if (!dentry)
-			goto out_eod;
+		struct dentry *next;
 
-		if (!offset_dir_emit(ctx, dentry)) {
-			dput(dentry);
+		ctx->pos = dentry2offset(dentry);
+		if (!offset_dir_emit(ctx, dentry))
  			break;
-		}
 
-		ctx->pos = dentry2offset(dentry) + 1;
+		spin_lock(&dir->d_lock);
+		next = find_next_sibling_locked(dir, d_next_sibling(dentry));
+		spin_unlock(&dir->d_lock);
  		dput(dentry);
+
+		if (!next)
+			goto out_eod;
+		dentry = next;
  	}
+	dput(dentry);
  	return;
 
  out_eod:

@@ -539,7 +576,7 @@ static int offset_readdir(struct file *file, struct dir_context *ctx)
  	if (!dir_emit_dots(file, ctx))
  		return 0;
  	if (ctx->pos != DIR_OFFSET_EOD)
-		offset_iterate_dir(d_inode(dir), ctx);
+		offset_iterate_dir(file, ctx);
  	return 0;
  }
 

Quoted 45 lines · On 12/4/24 10:52 AM, [email protected] wrote:

From: Chuck Lever <[email protected]>

The mtree mechanism has been effective at creating directory offsets that are stable over multiple opendir instances. However, it has not been able to handle the subtleties of renames that are concurrent with readdir.

Instead of using the mtree to emit entries in the order of their offset values, use it only to map incoming ctx->pos to a starting entry. Then use the directory's d_children list, which is already maintained properly by the dcache, to find the next child to emit.

One of the sneaky things about this is that when the mtree-allocated offset value wraps (which is very rare), looking up ctx->pos++ is not going to find the next entry; it will return NULL. Instead, by following the d_children list, the offset values can appear in any order but all of the entries in the directory will be visited eventually.

Note also that the readdir() is guaranteed to reach the tail of this list. Entries are added only at the head of d_children, and readdir walks from its current position in that list towards its tail.

Signed-off-by Chuck Lever <[email protected]>

---
  fs/libfs.c | 77 ++++++++++++++++++++++++++++++++++++++++--------------

  1 file changed, 57 insertions(+), 20 deletions(-)

fs/libfs.c +2 -1

index fcb2cdf6e3f3..398eac385094 100644
@@ -243,12 +243,13 @@ EXPORT_SYMBOL(simple_dir_inode_operations);
   /* simple_offset_add() allocation range */
   enum {
-    DIR_OFFSET_MIN        = 2,
+    DIR_OFFSET_MIN        = 3,
       DIR_OFFSET_MAX        = LONG_MAX - 1,
   };
   /* simple_offset_add() never assigns these to a dentry */
   enum {
+    DIR_OFFSET_FIRST    = 2,        /* Find first real entry */

      DIR_OFFSET_EOD        = LONG_MAX,    /* Marks EOD */ };

fs/libfs.c static loff_t offset_dir_llseek(struct file · line 463

Quoted 8 lines

fs/libfs.c +3 -1

@@ -456,19 +457,43 @@ static loff_t offset_dir_llseek(struct file 
 *file, loff_t offset, int whence)
       return vfs_setpos(file, offset, LONG_MAX);
   }
-static struct dentry *offset_find_next(struct offset_ctx *octx, 
 loff_t offset)
+/* Cf. find_next_child() */
+static struct dentry *find_next_sibling_locked(struct dentry *parent,
+                           struct dentry *dentry)

There might be a better name for this function.

It looks a lot like find_next_child(), but it acts more like scan_positives(). It starts looking for positive dentries starting at @dentry, thus it can return the dentry that was passed in @dentry.

find_positive_from_locked()  ??

Quoted 77 lines

fs/libfs.c +27 -5

   {
-    MA_STATE(mas, &octx->mt, offset, offset);
+    struct dentry *found = NULL;
+
+    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;
+    }
+    return found;
+}
+
+static noinline_for_stack struct dentry *
+offset_dir_lookup(struct file *file, loff_t offset)
+{
+    struct dentry *parent = file->f_path.dentry;
       struct dentry *child, *found = NULL;
+    struct inode *inode = d_inode(parent);
+    struct offset_ctx *octx = inode->i_op->get_offset_ctx(inode);
+
+    MA_STATE(mas, &octx->mt, offset, offset);
       rcu_read_lock();
       child = mas_find(&mas, DIR_OFFSET_MAX);
       if (!child)
           goto out;
-    spin_lock(&child->d_lock);
-    if (simple_positive(child))
-        found = dget_dlock(child);
-    spin_unlock(&child->d_lock);
+
+    spin_lock(&parent->d_lock);
+    found = find_next_sibling_locked(parent, child);
+    spin_unlock(&parent->d_lock);

  out:
      rcu_read_unlock();
      return found;

fs/libfs.c +14 -10

@@ -477,30 +502,42 @@ static struct dentry *offset_find_next(struct 
 offset_ctx *octx, loff_t offset)
   static bool offset_dir_emit(struct dir_context *ctx, struct dentry *dentry)
   {
       struct inode *inode = d_inode(dentry);
-    long offset = dentry2offset(dentry);
-    return ctx->actor(ctx, dentry->d_name.name, dentry->d_name.len, 
 offset,
-              inode->i_ino, fs_umode_to_dtype(inode->i_mode));
+    return dir_emit(ctx, dentry->d_name.name, dentry->d_name.len,
+            inode->i_ino, fs_umode_to_dtype(inode->i_mode));
   }
-static void offset_iterate_dir(struct inode *inode, struct 
 dir_context *ctx)
+static void offset_iterate_dir(struct file *file, struct dir_context 
 *ctx)
   {
-    struct offset_ctx *octx = inode->i_op->get_offset_ctx(inode);
+    struct dentry *dir = file->f_path.dentry;
       struct dentry *dentry;
+    if (ctx->pos == DIR_OFFSET_FIRST) {
+        spin_lock(&dir->d_lock);
+        dentry = find_next_sibling_locked(dir, d_first_child(dir));
+        spin_unlock(&dir->d_lock);
+    } else
+        dentry = offset_dir_lookup(file, ctx->pos);
+    if (!dentry)
+        goto out_eod;
+
       while (true) {
-        dentry = offset_find_next(octx, ctx->pos);
-        if (!dentry)
-            goto out_eod;
+        struct dentry *next;
-        if (!offset_dir_emit(ctx, dentry)) {
-            dput(dentry);

fs/libfs.c static struct dentry *offset_find_next(struct offset_ctx *octx, loff_t offset) · line 533

Quoted 8 lines

fs/libfs.c +5 -2

+        ctx->pos = dentry2offset(dentry);
+        if (!offset_dir_emit(ctx, dentry))
               break;
-        }
-        ctx->pos = dentry2offset(dentry) + 1;
+        spin_lock(&dir->d_lock);
+        next = find_next_sibling_locked(dir, d_next_sibling(dentry));
+        spin_unlock(&dir->d_lock);

Quoted 18 lines

fs/libfs.c +5 -0

           dput(dentry);
+
+        if (!next)
+            goto out_eod;
+        dentry = next;
       }
+    dput(dentry);
       return;

  out_eod:

fs/libfs.c +1 -1

@@ -539,7 +576,7 @@ static int offset_readdir(struct file *file, 
 struct dir_context *ctx)
       if (!dir_emit_dots(file, ctx))
           return 0;
       if (ctx->pos != DIR_OFFSET_EOD)
-        offset_iterate_dir(d_inode(dir), ctx);
+        offset_iterate_dir(file, ctx);
       return 0;
   }

Quoted 5 lines

fs/libfs.c static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence) · line 462

Quoted 3 lines

fs/libfs.c +3 -0

+/* Cf. find_next_child() */
+static struct dentry *find_next_sibling_locked(struct dentry *parent,
+                           struct dentry *dentry)

There might be a better name for this function.

Quoted 5 lines · Chuck Lever

Quoted 5 lines

fs/libfs.c static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence) · line 462

Quoted 3 lines

fs/libfs.c +3 -0

+/* Cf. find_next_child() */
+static struct dentry *find_next_sibling_locked(struct dentry *parent,
+                           struct dentry *dentry)

There might be a better name for this function.

There might be better calling conventions for it, TBH. AFAICS, all callers are directly surrounded by grabbing/releasing ->d_lock on parent. Why not fold that in, and to hell with any mentionings of "locked" in the name...

Quoted 7 lines · Al Viro

Quoted 5 lines · Chuck Lever

Quoted 5 lines

fs/libfs.c static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence) · line 462

Quoted 3 lines

fs/libfs.c +3 -0

+/* Cf. find_next_child() */
+static struct dentry *find_next_sibling_locked(struct dentry *parent,
+                           struct dentry *dentry)

There might be a better name for this function.

Quoted 4 lines

There might be better calling conventions for it, TBH. AFAICS, all callers are directly surrounded by grabbing/releasing ->d_lock on parent. Why not fold that in, and to hell with any mentionings of "locked" in the name...

I've tried it both ways, couldn't make up my mind. I'll try it again.

From: Chuck Lever <[email protected]>

The purpose of this series is to construct a set of upstream fixes that can be backported to v6.6 to address CVE-2024-46701.

My original plan was to add a cursor dentry. However, I've found a solution that does not need one. In fact, most or all of the reported issues are gone with 4/5. Thus I'm not sure 5/5 is necessary, but it seems like a robust improvement.

[...]

From: Chuck Lever <[email protected]>

The purpose of this series is to construct a set of upstream fixes that can be backported to v6.6 to address CVE-2024-46701.

My original plan was to add a cursor dentry. However, I've found a solution that does not need one. In fact, most or all of the reported issues are gone with 4/5. Thus I'm not sure 5/5 is necessary, but it seems like a robust improvement.

Changes since v3:
- Series is no longer RFC
- Series passes xfstests locally and via NFS export
- Patch 2/5 was replaced; it now removes simple_offset_empty()
- 4/5 and 5/5 were rewritten based on test results
- Patch descriptions have been clarified

This series (still against v6.12) has been pushed to:

https://git.kernel.org/pub/scm/linux/kernel/git/cel/linux.git/log/?h=tmpfs-fixes

Next step is to try backporting these to v6.6 to see if anything else is needed.

Chuck Lever (5):
libfs: Return ENOSPC when the directory offset range is exhausted Revert "libfs: Add simple_offset_empty()"
Revert "libfs: fix infinite directory reads for offset dir"
libfs: Replace simple_offset end-of-directory detection
libfs: Use d_children list to iterate simple_offset directories

  fs/libfs.c         | 158 ++++++++++++++++++++++-----------------------
  include/linux/fs.h |   1 -
  mm/shmem.c         |   4 +-
  3 files changed, 81 insertions(+), 82 deletions(-)