[PATCH] fuse: replace passthrough backing-id IDR with IDA plus hashtable

[PATCH] fuse: replace passthrough backing-id IDR with IDA plus hashtable

[Mahad Ibrahim]

The passthrough code maps an integer backing id to a struct fuse_backing
using an IDR. idr_alloc_cyclic() stores the fuse_backing pointer at the
id's index, so the IDR keeps one populated radix-tree slot per live id. A
comment flags the cost:

	/* FIXME: xarray might be space inefficient */

Replace the IDR with an IDA for id allocation and a separate hashtable for
the id-to-pointer lookup. The IDA needs far less memory per id; the
hashtable adds a fixed per-connection cost. The net effect is a space win
that grows with the number of live backings, as quantified below.

Both IDR and IDA are built on the xarray and walk the same xa_node
(XA_CHUNK_SIZE is 64 slots per node, and an xa_node is about 576 bytes on
64-bit). The difference is what fills those slots. The IDR stores one
fuse_backing pointer per id, so N live ids occupy N slots and need roughly
N/64 leaf nodes. The IDA stores a 128-byte bitmap that covers 1024 ids
(IDA_BITMAP_BITS), so the same N ids occupy about N/1024 slots. The id
space is the same; the IDA represents it far more densely.

In the dense limit the IDR costs about nine bytes per id (a 576-byte node
over 64 slots), while the IDA costs about 0.13 bytes per id (a 128-byte
bitmap over 1024 ids). 4096 live ids would occupy 65 xa_nodes in the IDR
(about 37 KB) versus roughly 3 KB for the IDA plus the 2 KB hashtable.
The fixed hashtable makes the new scheme slightly larger below a couple
hundred backings; above that it uses progressively less memory than the
IDR, and the gap widens as the count grows.

These figures assume dense, low-numbered ids, which is the most favorable
case for the IDR. Cyclic allocation drives ids upward and leaves holes as
backings are closed, spreading the IDR's live entries across more,
less-full leaf nodes; each IDA chunk still covers 1024 ids however they are
spread, so it degrades more slowly. The dense case is therefore the
smallest the gain gets; sparser ids only widen it.

The new fields in struct fuse_backing (an int id and a struct hlist_node)
add 24 bytes on x86-64, keeping the structure within the kmalloc-64 slab,
so per-object allocation should remain unchanged.

The hashtable has a fixed 256 buckets (DECLARE_HASHTABLE order 8), so
lookup time grows with the chain length, about N/256 on average, which is
O(N) in complexity. At a few thousand backings the chains hold one or two
entries; at a very large count (for example 100000 backings, about 390
per chain) this is slower than the IDR's bounded radix walk (at most six
levels for 31-bit ids, effectively O(1)). fuse_backing_lookup() runs once
when a passthrough file open attaches its backing, not on each read or
write, since passthrough I/O goes directly to the backing file, so the
cost stays off the data path. An rhashtable would keep lookup flat as the
count grows at the cost of more complexity; the fixed table was chosen
for simplicity.

The hashtable is 2 KB. Embedding it in struct fuse_conn would charge that
to every connection, including the majority that never enable passthrough,
so fc->backing_htable is a pointer allocated lazily by
fuse_backing_htable_alloc() when passthrough is negotiated in
process_init_reply(). The IDA itself stays embedded, since it is small. If
the allocation fails, passthrough is left disabled and init continues,
matching how the other negotiated features in process_init_reply() behave.
This preserves the invariant that fc->backing_htable is non-NULL exactly
when fc->passthrough is set. Every dereference of the table is in
fuse_backing_id_alloc(), fuse_backing_id_remove() or fuse_backing_lookup(),
all reached only through the BACKING_OPEN and BACKING_CLOSE ioctls, which
check fc->passthrough first. A connection that fails the allocation
therefore behaves like any non-passthrough connection, and the lookup paths
need no NULL checks.

The IDA has no cyclic allocator, so an explicit cursor
(backing_files_next_id) is kept: ida_alloc_range() searches from the cursor
to INT_MAX, and on -ENOSPC the cursor resets to 1 and the allocation is
retried exactly once. The cursor is accessed with READ_ONCE/WRITE_ONCE; two
concurrent allocators may read the same value, but the IDA still returns
distinct ids, so the cursor is only a hint to avoid immediate reuse.

Tested with KCSAN and with KASAN in separate builds, as the two are
mutually exclusive. KCSAN with lockdep and PROVE_RCU reported no data races
in fs/fuse under a passthrough workload. Under KASAN, a passthrough server
drove fuse_backing_lookup() and fuse_backing_id_remove() concurrently on
the same ids; a temporary udelay() in the lookup, not part of this series,
widened the window between the hashtable match and fuse_backing_get() so
the concurrent free reliably overlapped it. No KASAN, RCU-debug, or
kmemleak reports resulted. fio (16 jobs, io_uring, randrw 4k, 300s) over a
passthrough mount showed no significant throughput change against the IDR
version.

Signed-off-by: Mahad Ibrahim <mahad.ibrahim.dev@gmail.com>
---
 fs/fuse/backing.c | 96 +++++++++++++++++++++++++++++++++++++----------
 fs/fuse/fuse_i.h  | 27 ++++++++++++-
 fs/fuse/inode.c   |  8 ++--
 3 files changed, 106 insertions(+), 25 deletions(-)

diff --git a/fs/fuse/backing.c b/fs/fuse/backing.c
index 472b6afa7dff..322d676bcc16 100644
--- a/fs/fuse/backing.c
+++ b/fs/fuse/backing.c
@@ -35,49 +35,97 @@ void fuse_backing_put(struct fuse_backing *fb)
 
 void fuse_backing_files_init(struct fuse_conn *fc)
 {
-	idr_init(&fc->backing_files_map);
+	ida_init(&fc->backing_files_map);
+	fc->backing_files_next_id = 1;
+	fc->backing_htable = NULL;
 }
 
 static int fuse_backing_id_alloc(struct fuse_conn *fc, struct fuse_backing *fb)
 {
 	int id;
+	int attempt = 1;
+
+retry:
+
+	id = ida_alloc_range(&fc->backing_files_map,
+			     READ_ONCE(fc->backing_files_next_id), INT_MAX, GFP_KERNEL);
+
+	if (id < 0) {
+		if (id == -ENOSPC && attempt--) {
+			WRITE_ONCE(fc->backing_files_next_id, 1);
+			goto retry;
+		}
+		return id;
+	}
+
+	fb->id = id;
 
-	idr_preload(GFP_KERNEL);
 	spin_lock(&fc->lock);
-	/* FIXME: xarray might be space inefficient */
-	id = idr_alloc_cyclic(&fc->backing_files_map, fb, 1, 0, GFP_ATOMIC);
+	hash_add_rcu(fc->backing_htable->backing_files_ht, &fb->node, id);
+	WRITE_ONCE(fc->backing_files_next_id, (id == INT_MAX) ? 1 : id + 1);
 	spin_unlock(&fc->lock);
-	idr_preload_end();
 
-	WARN_ON_ONCE(id == 0);
 	return id;
 }
 
+int fuse_backing_htable_alloc(struct fuse_conn *fc)
+{
+	struct fuse_backing_htable *ht;
+
+	ht = kzalloc_obj(struct fuse_backing_htable);
+	if (!ht)
+		return -ENOMEM;
+
+	hash_init(ht->backing_files_ht);
+	fc->backing_htable = ht;
+
+	return 0;
+}
+
 static struct fuse_backing *fuse_backing_id_remove(struct fuse_conn *fc,
 						   int id)
 {
-	struct fuse_backing *fb;
+	struct fuse_backing *iterator;
+	struct fuse_backing *fb = NULL;
 
 	spin_lock(&fc->lock);
-	fb = idr_remove(&fc->backing_files_map, id);
+	hash_for_each_possible(fc->backing_htable->backing_files_ht,
+			       iterator, node, id) {
+		if (iterator->id == id) {
+			hash_del_rcu(&iterator->node);
+			fb = iterator;
+			break;
+		}
+	}
 	spin_unlock(&fc->lock);
 
+	if (fb)
+		ida_free(&fc->backing_files_map, id);
+
 	return fb;
 }
 
-static int fuse_backing_id_free(int id, void *p, void *data)
+void fuse_backing_files_free(struct fuse_conn *fc)
 {
-	struct fuse_backing *fb = p;
+	struct fuse_backing *fb;
+	struct hlist_node *tmp;
+	int bkt;
 
-	WARN_ON_ONCE(refcount_read(&fb->count) != 1);
-	fuse_backing_free(fb);
-	return 0;
-}
+	if (!fc->backing_htable)
+		goto out;
 
-void fuse_backing_files_free(struct fuse_conn *fc)
-{
-	idr_for_each(&fc->backing_files_map, fuse_backing_id_free, NULL);
-	idr_destroy(&fc->backing_files_map);
+	hash_for_each_safe(fc->backing_htable->backing_files_ht,
+			   bkt, tmp, fb, node) {
+		hash_del_rcu(&fb->node);
+		WARN_ON_ONCE(refcount_read(&fb->count) != 1);
+		fuse_backing_free(fb);
+	}
+
+	kfree(fc->backing_htable);
+	fc->backing_htable = NULL;
+
+out:
+	ida_destroy(&fc->backing_files_map);
 }
 
 int fuse_backing_open(struct fuse_conn *fc, struct fuse_backing_map *map)
@@ -169,10 +217,18 @@ int fuse_backing_close(struct fuse_conn *fc, int backing_id)
 
 struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc, int backing_id)
 {
-	struct fuse_backing *fb;
+	struct fuse_backing *iterator;
+	struct fuse_backing *fb = NULL;
 
 	rcu_read_lock();
-	fb = idr_find(&fc->backing_files_map, backing_id);
+	hash_for_each_possible_rcu(fc->backing_htable->backing_files_ht,
+				   iterator, node, backing_id) {
+		if (iterator->id == backing_id) {
+			fb = iterator;
+			break;
+		}
+	}
+
 	fb = fuse_backing_get(fb);
 	rcu_read_unlock();
 
diff --git a/fs/fuse/fuse_i.h b/fs/fuse/fuse_i.h
index 85f738c53122..7965c1681b58 100644
--- a/fs/fuse/fuse_i.h
+++ b/fs/fuse/fuse_i.h
@@ -30,6 +30,7 @@
 #include <linux/pid_namespace.h>
 #include <linux/refcount.h>
 #include <linux/user_namespace.h>
+#include <linux/hashtable.h>
 
 /** Default max number of pages that can be used in a single read request */
 #define FUSE_DEFAULT_MAX_PAGES_PER_REQ 32
@@ -94,6 +95,10 @@ struct fuse_backing {
 	/* refcount */
 	refcount_t count;
 	struct rcu_head rcu;
+
+	/* ID Allocation */
+	int id;
+	struct hlist_node node;
 };
 
 /**
@@ -407,6 +412,12 @@ struct fuse_sync_bucket {
 	struct rcu_head rcu;
 };
 
+#ifdef CONFIG_FUSE_PASSTHROUGH
+struct fuse_backing_htable {
+	DECLARE_HASHTABLE(backing_files_ht, 8);
+};
+#endif
+
 /**
  * struct fuse_conn - A Fuse connection.
  *
@@ -759,8 +770,14 @@ struct fuse_conn {
 	struct fuse_sync_bucket __rcu *curr_bucket;
 
 #ifdef CONFIG_FUSE_PASSTHROUGH
-	/** @backing_files_map: IDR for backing files ids */
-	struct idr backing_files_map;
+	/** @backing_files_map: IDA for backing files ids */
+	struct ida backing_files_map;
+
+	/** @backing_files_next_id: Cursor for cyclic allocation */
+	unsigned int backing_files_next_id;
+
+	/** @backing_htable: Pointer to external hashtable */
+	struct fuse_backing_htable *backing_htable;
 #endif
 };
 
@@ -1259,6 +1276,7 @@ void fuse_file_release(struct inode *inode, struct fuse_file *ff,
 struct fuse_backing *fuse_backing_get(struct fuse_backing *fb);
 void fuse_backing_put(struct fuse_backing *fb);
 struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc, int backing_id);
+int fuse_backing_htable_alloc(struct fuse_conn *fc);
 #else
 
 static inline struct fuse_backing *fuse_backing_get(struct fuse_backing *fb)
@@ -1274,6 +1292,11 @@ static inline struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc,
 {
 	return NULL;
 }
+
+static inline int fuse_backing_htable_alloc(struct fuse_conn *fc)
+{
+	return -EOPNOTSUPP;
+}
 #endif
 
 void fuse_backing_files_init(struct fuse_conn *fc);
diff --git a/fs/fuse/inode.c b/fs/fuse/inode.c
index d975073c6029..8adb1eb7ff51 100644
--- a/fs/fuse/inode.c
+++ b/fs/fuse/inode.c
@@ -1389,9 +1389,11 @@ static void process_init_reply(struct fuse_args *args, int error)
 			    arg->max_stack_depth > 0 &&
 			    arg->max_stack_depth <= FILESYSTEM_MAX_STACK_DEPTH &&
 			    !(flags & FUSE_WRITEBACK_CACHE))  {
-				fc->passthrough = 1;
-				fc->max_stack_depth = arg->max_stack_depth;
-				fm->sb->s_stack_depth = arg->max_stack_depth;
+				if (!fuse_backing_htable_alloc(fc)) {
+					fc->passthrough = 1;
+					fc->max_stack_depth = arg->max_stack_depth;
+					fm->sb->s_stack_depth = arg->max_stack_depth;
+				}
 			}
 			if (flags & FUSE_NO_EXPORT_SUPPORT)
 				fm->sb->s_export_op = &fuse_export_fid_operations;
-- 
2.54.0

Re: [PATCH] fuse: replace passthrough backing-id IDR with IDA plus hashtable

[Miklos Szeredi]

On Sun, 21 Jun 2026 at 20:32, Mahad Ibrahim <mahad.ibrahim.dev@gmail.com> wrote:

> Replace the IDR with an IDA for id allocation and a separate hashtable for
> the id-to-pointer lookup. The IDA needs far less memory per id; the
> hashtable adds a fixed per-connection cost. The net effect is a space win
> that grows with the number of live backings, as quantified below.

But why use IDA at all?  A simple cyclic counter should be sufficient.
Collisions (which should be rare) can be avoided via hash table
lookup.

Thanks,
Miklos

Re: [PATCH] fuse: replace passthrough backing-id IDR with IDA plus hashtable

[Amir Goldstein]

On Mon, Jun 22, 2026 at 9:25 AM Miklos Szeredi <miklos@szeredi.hu> wrote:
>
> On Sun, 21 Jun 2026 at 20:32, Mahad Ibrahim <mahad.ibrahim.dev@gmail.com> wrote:
>
> > Replace the IDR with an IDA for id allocation and a separate hashtable for
> > the id-to-pointer lookup. The IDA needs far less memory per id; the
> > hashtable adds a fixed per-connection cost. The net effect is a space win
> > that grows with the number of live backings, as quantified below.
>
> But why use IDA at all?  A simple cyclic counter should be sufficient.
> Collisions (which should be rare) can be avoided via hash table
> lookup.
>

Also, we were considering widening backing_id to 64bit and allow for
user assigned id's, so if we are dropping IDR/IDA it's a good opportunity
to remove the INT_MAX limit, but we'd still need a 32bit allocator mode
for the legacy backing id.

Thanks,
Amir.

Re: [PATCH] fuse: replace passthrough backing-id IDR with IDA plus hashtable

[Mahad Ibrahim]

Thanks, both

You're right, the hashtable keys already are the set of live ids, so the IDA is redundant. v2 will drop it and use the cyclic counter with the collision check as you suggested.

I'll keep this patch 32-bit and kernel-allocated to preserve current behaviour. Thank you for the heads-up on the 64-bit and user-assigned id plans, Amir. I'll keep that in mind so this doesn't get in the way of it.

Thanks,
Mahad

[PATCH v2] fuse: replace passthrough backing-id IDR with a counter and hashtable

[Mahad Ibrahim]

The passthrough backing-id IDR carries a /* FIXME: xarray might be space
inefficient */ on its idr_alloc_cyclic() call. Replace it with a cyclic
counter for allocation and a hashtable for lookup.

The hashtable keys are already the set of live ids, so allocation needs
only a counter: it takes the next value, skipping any already present,
all under fc->lock. A live-id count makes it return -ENOSPC when full.

The hashtable is allocated lazily when passthrough is negotiated, so it is
present whenever passthrough is enabled; every dereference is already gated
on fc->passthrough, so no NULL checks are added. On allocation failure
passthrough is left off and the mount continues.

Lookup is now O(chain) rather than the IDR's bounded walk, but runs only at
backing setup, off the read/write path.

Testing

Tested under KASAN and KCSAN in separate builds, since the two cannot be
enabled together. The workload was passthrough_hp under fio with parallel
open/close churn; ftrace confirmed concurrent allocation, lookup, and
removal across CPUs. No KASAN use-after-free and no KCSAN data race in
fs/fuse/backing.c.

Signed-off-by: Mahad Ibrahim <mahad.ibrahim.dev@gmail.com>

---

v2:
 - drop the IDA; allocate with a cyclic counter and resolve collisions
   via the hashtable's membership check under fc->lock (Miklos)
 - add a live-id count to bound allocation and return -ENOSPC when full

Uniqueness now comes from the hashtable rather than an allocator that owns
the id space, so this should stay clear of any future 64-bit or
user-assigned-id work. The id is kept 32-bit and kernel-allocated here.

Lookup uses 256 fixed buckets, so chains lengthen at very high backing
counts; an rhashtable would keep it flat but adds complexity. The fixed
table seemed simpler for the expected counts - happy to switch if you'd
prefer.

 fs/fuse/backing.c | 98 +++++++++++++++++++++++++++++++++++++----------
 fs/fuse/fuse_i.h  | 31 +++++++++++++--
 fs/fuse/inode.c   |  8 ++--
 3 files changed, 111 insertions(+), 26 deletions(-)

diff --git a/fs/fuse/backing.c b/fs/fuse/backing.c
index 472b6afa7dff..77f4d4b00bf4 100644
--- a/fs/fuse/backing.c
+++ b/fs/fuse/backing.c
@@ -35,49 +35,99 @@ void fuse_backing_put(struct fuse_backing *fb)
 
 void fuse_backing_files_init(struct fuse_conn *fc)
 {
-	idr_init(&fc->backing_files_map);
+	fc->backing_ids_count = 0;
+	fc->backing_files_next_id = 1;
+	fc->backing_htable = NULL;
 }
 
 static int fuse_backing_id_alloc(struct fuse_conn *fc, struct fuse_backing *fb)
 {
 	int id;
+	struct fuse_backing *iterator;
 
-	idr_preload(GFP_KERNEL);
 	spin_lock(&fc->lock);
-	/* FIXME: xarray might be space inefficient */
-	id = idr_alloc_cyclic(&fc->backing_files_map, fb, 1, 0, GFP_ATOMIC);
+
+	if (fc->backing_ids_count == INT_MAX) {
+		id = -ENOSPC;
+		goto out;
+	}
+
+retry:
+	id = fc->backing_files_next_id;
+	fc->backing_files_next_id = (id == INT_MAX) ? 1 : id + 1;
+
+	hash_for_each_possible(fc->backing_htable->backing_files_ht,
+			       iterator, node, id) {
+		if (iterator->id == id)
+			goto retry;
+	}
+
+	fb->id = id;
+	hash_add_rcu(fc->backing_htable->backing_files_ht, &fb->node, id);
+	fc->backing_ids_count++;
+
+out:
 	spin_unlock(&fc->lock);
-	idr_preload_end();
 
-	WARN_ON_ONCE(id == 0);
 	return id;
 }
 
+int fuse_backing_htable_alloc(struct fuse_conn *fc)
+{
+	struct fuse_backing_htable *ht;
+
+	ht = kzalloc_obj(struct fuse_backing_htable);
+	if (!ht)
+		return -ENOMEM;
+
+	hash_init(ht->backing_files_ht);
+	fc->backing_htable = ht;
+
+	return 0;
+}
+
 static struct fuse_backing *fuse_backing_id_remove(struct fuse_conn *fc,
 						   int id)
 {
-	struct fuse_backing *fb;
+	struct fuse_backing *iterator;
+	struct fuse_backing *fb = NULL;
 
 	spin_lock(&fc->lock);
-	fb = idr_remove(&fc->backing_files_map, id);
+	hash_for_each_possible(fc->backing_htable->backing_files_ht,
+			       iterator, node, id) {
+		if (iterator->id == id) {
+			hash_del_rcu(&iterator->node);
+			fb = iterator;
+			break;
+		}
+	}
+
+	if (fb)
+		fc->backing_ids_count--;
+
 	spin_unlock(&fc->lock);
 
 	return fb;
 }
 
-static int fuse_backing_id_free(int id, void *p, void *data)
+void fuse_backing_files_free(struct fuse_conn *fc)
 {
-	struct fuse_backing *fb = p;
+	struct fuse_backing *fb;
+	struct hlist_node *tmp;
+	int bkt;
 
-	WARN_ON_ONCE(refcount_read(&fb->count) != 1);
-	fuse_backing_free(fb);
-	return 0;
-}
+	if (!fc->backing_htable)
+		return;
 
-void fuse_backing_files_free(struct fuse_conn *fc)
-{
-	idr_for_each(&fc->backing_files_map, fuse_backing_id_free, NULL);
-	idr_destroy(&fc->backing_files_map);
+	hash_for_each_safe(fc->backing_htable->backing_files_ht,
+			   bkt, tmp, fb, node) {
+		hash_del_rcu(&fb->node);
+		WARN_ON_ONCE(refcount_read(&fb->count) != 1);
+		fuse_backing_free(fb);
+	}
+
+	kfree(fc->backing_htable);
+	fc->backing_htable = NULL;
 }
 
 int fuse_backing_open(struct fuse_conn *fc, struct fuse_backing_map *map)
@@ -169,10 +219,18 @@ int fuse_backing_close(struct fuse_conn *fc, int backing_id)
 
 struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc, int backing_id)
 {
-	struct fuse_backing *fb;
+	struct fuse_backing *iterator;
+	struct fuse_backing *fb = NULL;
 
 	rcu_read_lock();
-	fb = idr_find(&fc->backing_files_map, backing_id);
+	hash_for_each_possible_rcu(fc->backing_htable->backing_files_ht,
+				   iterator, node, backing_id) {
+		if (iterator->id == backing_id) {
+			fb = iterator;
+			break;
+		}
+	}
+
 	fb = fuse_backing_get(fb);
 	rcu_read_unlock();
 
diff --git a/fs/fuse/fuse_i.h b/fs/fuse/fuse_i.h
index 85f738c53122..db4c07a496f0 100644
--- a/fs/fuse/fuse_i.h
+++ b/fs/fuse/fuse_i.h
@@ -30,6 +30,7 @@
 #include <linux/pid_namespace.h>
 #include <linux/refcount.h>
 #include <linux/user_namespace.h>
+#include <linux/hashtable.h>
 
 /** Default max number of pages that can be used in a single read request */
 #define FUSE_DEFAULT_MAX_PAGES_PER_REQ 32
@@ -94,6 +95,10 @@ struct fuse_backing {
 	/* refcount */
 	refcount_t count;
 	struct rcu_head rcu;
+
+	/* ID Allocation */
+	int id;
+	struct hlist_node node;
 };
 
 /**
@@ -407,6 +412,12 @@ struct fuse_sync_bucket {
 	struct rcu_head rcu;
 };
 
+#ifdef CONFIG_FUSE_PASSTHROUGH
+struct fuse_backing_htable {
+	DECLARE_HASHTABLE(backing_files_ht, 8);
+};
+#endif
+
 /**
  * struct fuse_conn - A Fuse connection.
  *
@@ -418,7 +429,9 @@ struct fuse_conn {
 	/**
 	 * @lock: Lock protecting:
 	 * - polled_files
-	 * - backing_files_map
+	 * - backing_files_next_id
+	 * - backing_ids_count
+	 * - backing_htable (modifications)
 	 * - curr_bucket
 	 */
 	spinlock_t lock;
@@ -759,8 +772,14 @@ struct fuse_conn {
 	struct fuse_sync_bucket __rcu *curr_bucket;
 
 #ifdef CONFIG_FUSE_PASSTHROUGH
-	/** @backing_files_map: IDR for backing files ids */
-	struct idr backing_files_map;
+	/** @backing_ids_count: Count of total allocated IDs */
+	unsigned int backing_ids_count;
+
+	/** @backing_files_next_id: Cursor for cyclic allocation */
+	unsigned int backing_files_next_id;
+
+	/** @backing_htable: Pointer to external hashtable */
+	struct fuse_backing_htable *backing_htable;
 #endif
 };
 
@@ -1259,6 +1278,7 @@ void fuse_file_release(struct inode *inode, struct fuse_file *ff,
 struct fuse_backing *fuse_backing_get(struct fuse_backing *fb);
 void fuse_backing_put(struct fuse_backing *fb);
 struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc, int backing_id);
+int fuse_backing_htable_alloc(struct fuse_conn *fc);
 #else
 
 static inline struct fuse_backing *fuse_backing_get(struct fuse_backing *fb)
@@ -1274,6 +1294,11 @@ static inline struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc,
 {
 	return NULL;
 }
+
+static inline int fuse_backing_htable_alloc(struct fuse_conn *fc)
+{
+	return -EOPNOTSUPP;
+}
 #endif
 
 void fuse_backing_files_init(struct fuse_conn *fc);
diff --git a/fs/fuse/inode.c b/fs/fuse/inode.c
index d975073c6029..8adb1eb7ff51 100644
--- a/fs/fuse/inode.c
+++ b/fs/fuse/inode.c
@@ -1389,9 +1389,11 @@ static void process_init_reply(struct fuse_args *args, int error)
 			    arg->max_stack_depth > 0 &&
 			    arg->max_stack_depth <= FILESYSTEM_MAX_STACK_DEPTH &&
 			    !(flags & FUSE_WRITEBACK_CACHE))  {
-				fc->passthrough = 1;
-				fc->max_stack_depth = arg->max_stack_depth;
-				fm->sb->s_stack_depth = arg->max_stack_depth;
+				if (!fuse_backing_htable_alloc(fc)) {
+					fc->passthrough = 1;
+					fc->max_stack_depth = arg->max_stack_depth;
+					fm->sb->s_stack_depth = arg->max_stack_depth;
+				}
 			}
 			if (flags & FUSE_NO_EXPORT_SUPPORT)
 				fm->sb->s_export_op = &fuse_export_fid_operations;
-- 
2.54.0

Re: [PATCH v2] fuse: replace passthrough backing-id IDR with a counter and hashtable

[Amir Goldstein]

On Fri, Jun 26, 2026 at 2:51 PM Mahad Ibrahim
<mahad.ibrahim.dev@gmail.com> wrote:
>
> The passthrough backing-id IDR carries a /* FIXME: xarray might be space
> inefficient */ on its idr_alloc_cyclic() call. Replace it with a cyclic
> counter for allocation and a hashtable for lookup.
>
> The hashtable keys are already the set of live ids, so allocation needs
> only a counter: it takes the next value, skipping any already present,
> all under fc->lock. A live-id count makes it return -ENOSPC when full.
>
> The hashtable is allocated lazily when passthrough is negotiated, so it is
> present whenever passthrough is enabled; every dereference is already gated
> on fc->passthrough, so no NULL checks are added. On allocation failure
> passthrough is left off and the mount continues.
>
> Lookup is now O(chain) rather than the IDR's bounded walk, but runs only at
> backing setup, off the read/write path.
>
> Testing
>
> Tested under KASAN and KCSAN in separate builds, since the two cannot be
> enabled together. The workload was passthrough_hp under fio with parallel
> open/close churn; ftrace confirmed concurrent allocation, lookup, and
> removal across CPUs. No KASAN use-after-free and no KCSAN data race in
> fs/fuse/backing.c.
>
> Signed-off-by: Mahad Ibrahim <mahad.ibrahim.dev@gmail.com>
>
> ---
>
> v2:
>  - drop the IDA; allocate with a cyclic counter and resolve collisions
>    via the hashtable's membership check under fc->lock (Miklos)
>  - add a live-id count to bound allocation and return -ENOSPC when full
>
> Uniqueness now comes from the hashtable rather than an allocator that owns
> the id space, so this should stay clear of any future 64-bit or
> user-assigned-id work. The id is kept 32-bit and kernel-allocated here.
>
> Lookup uses 256 fixed buckets, so chains lengthen at very high backing
> counts; an rhashtable would keep it flat but adds complexity. The fixed
> table seemed simpler for the expected counts - happy to switch if you'd
> prefer.
>
>  fs/fuse/backing.c | 98 +++++++++++++++++++++++++++++++++++++----------
>  fs/fuse/fuse_i.h  | 31 +++++++++++++--
>  fs/fuse/inode.c   |  8 ++--
>  3 files changed, 111 insertions(+), 26 deletions(-)
>
> diff --git a/fs/fuse/backing.c b/fs/fuse/backing.c
> index 472b6afa7dff..77f4d4b00bf4 100644
> --- a/fs/fuse/backing.c
> +++ b/fs/fuse/backing.c
> @@ -35,49 +35,99 @@ void fuse_backing_put(struct fuse_backing *fb)
>
>  void fuse_backing_files_init(struct fuse_conn *fc)
>  {
> -       idr_init(&fc->backing_files_map);
> +       fc->backing_ids_count = 0;
> +       fc->backing_files_next_id = 1;

looks like your first alloc will be 2.

> +       fc->backing_htable = NULL;
>  }
>
>  static int fuse_backing_id_alloc(struct fuse_conn *fc, struct fuse_backing *fb)
>  {
>         int id;
> +       struct fuse_backing *iterator;
>
> -       idr_preload(GFP_KERNEL);
>         spin_lock(&fc->lock);
> -       /* FIXME: xarray might be space inefficient */
> -       id = idr_alloc_cyclic(&fc->backing_files_map, fb, 1, 0, GFP_ATOMIC);
> +
> +       if (fc->backing_ids_count == INT_MAX) {
> +               id = -ENOSPC;
> +               goto out;
> +       }
> +
> +retry:
> +       id = fc->backing_files_next_id;
> +       fc->backing_files_next_id = (id == INT_MAX) ? 1 : id + 1;
> +
> +       hash_for_each_possible(fc->backing_htable->backing_files_ht,
> +                              iterator, node, id) {
> +               if (iterator->id == id)
> +                       goto retry;
> +       }

The hash table change is good but this allocator I really hate.
I know that Miklos proposed this, but the way it is implemented can
cause soft lockup and in general if you are implementing an allocator
you are probably doing it wrong.

Also I am concerned that with Joanne's backing inode patches,
backing id maps may be a lot more dense and backing id's a lot more
long lived than with backing id's for open/close lifecycle.

I think it was a mistake to provide a kernel allocator for backing ids -
the server is responsible for every other aspect of managing backing files.

Can we still salvage this UAPI?

Maybe:
1. Do not goto retry, instead return -EAGAIN let userspace retry
2. fuse_passthrough_open() can implement the retry loop
3. At least until INT_MAX, EAGAIN is not expected and for existing servers
    with short file open/close lifecycles, EAGAIN should be rare
4. Server/libfuse know exactly which backing ids are allocated,
    so they can use whatever algorithm they like for efficient allocation
5. All we need to do is support server allocated backing id
    and check it against the hash table lookup

+#define FUSE_BACKING_FLAG_SERVER_ID 1
+
 struct fuse_backing_map {
        int32_t         fd;
        uint32_t        flags;
-       uint64_t        padding;
+       uint64_t        id;
 };

It should be a very minimal addition to implement this.
BTW, we make it 64bit for future extensions (such as backing stripe)
although OPEN response still supports only 32bit backing ids.

Will this cause regressions?

Maybe, but I think that the existing users of fuse passthrough are
still pretty close to upstream and not yet in distributed servers (?)
so I hope this will be fine - if not, there are solutions.

Miklos, do you agree?

> +
> +       fb->id = id;
> +       hash_add_rcu(fc->backing_htable->backing_files_ht, &fb->node, id);
> +       fc->backing_ids_count++;
> +
> +out:
>         spin_unlock(&fc->lock);
> -       idr_preload_end();
>
> -       WARN_ON_ONCE(id == 0);
>         return id;
>  }
>
> +int fuse_backing_htable_alloc(struct fuse_conn *fc)
> +{
> +       struct fuse_backing_htable *ht;
> +
> +       ht = kzalloc_obj(struct fuse_backing_htable);
> +       if (!ht)
> +               return -ENOMEM;
> +
> +       hash_init(ht->backing_files_ht);
> +       fc->backing_htable = ht;
> +
> +       return 0;
> +}
> +
>  static struct fuse_backing *fuse_backing_id_remove(struct fuse_conn *fc,
>                                                    int id)
>  {
> -       struct fuse_backing *fb;
> +       struct fuse_backing *iterator;
> +       struct fuse_backing *fb = NULL;
>
>         spin_lock(&fc->lock);
> -       fb = idr_remove(&fc->backing_files_map, id);
> +       hash_for_each_possible(fc->backing_htable->backing_files_ht,
> +                              iterator, node, id) {
> +               if (iterator->id == id) {
> +                       hash_del_rcu(&iterator->node);
> +                       fb = iterator;
> +                       break;

This fb may very likely be alive and referenced by an open
file, so the very least is to set fb->id = 0, to make it anonymous,
so debug prints won't show different fb's with the same id.

> +               }
> +       }
> +
> +       if (fb)
> +               fc->backing_ids_count--;
> +
>         spin_unlock(&fc->lock);
>
>         return fb;
>  }
>
> -static int fuse_backing_id_free(int id, void *p, void *data)
> +void fuse_backing_files_free(struct fuse_conn *fc)
>  {
> -       struct fuse_backing *fb = p;
> +       struct fuse_backing *fb;
> +       struct hlist_node *tmp;
> +       int bkt;
>
> -       WARN_ON_ONCE(refcount_read(&fb->count) != 1);
> -       fuse_backing_free(fb);
> -       return 0;
> -}
> +       if (!fc->backing_htable)
> +               return;
>
> -void fuse_backing_files_free(struct fuse_conn *fc)
> -{
> -       idr_for_each(&fc->backing_files_map, fuse_backing_id_free, NULL);
> -       idr_destroy(&fc->backing_files_map);
> +       hash_for_each_safe(fc->backing_htable->backing_files_ht,
> +                          bkt, tmp, fb, node) {
> +               hash_del_rcu(&fb->node);
> +               WARN_ON_ONCE(refcount_read(&fb->count) != 1);
> +               fuse_backing_free(fb);
> +       }
> +
> +       kfree(fc->backing_htable);
> +       fc->backing_htable = NULL;
>  }
>
>  int fuse_backing_open(struct fuse_conn *fc, struct fuse_backing_map *map)
> @@ -169,10 +219,18 @@ int fuse_backing_close(struct fuse_conn *fc, int backing_id)
>
>  struct fuse_backing *fuse_backing_lookup(struct fuse_conn *fc, int backing_id)
>  {
> -       struct fuse_backing *fb;
> +       struct fuse_backing *iterator;
> +       struct fuse_backing *fb = NULL;
>
>         rcu_read_lock();
> -       fb = idr_find(&fc->backing_files_map, backing_id);
> +       hash_for_each_possible_rcu(fc->backing_htable->backing_files_ht,
> +                                  iterator, node, backing_id) {
> +               if (iterator->id == backing_id) {
> +                       fb = iterator;
> +                       break;
> +               }
> +       }
> +
>         fb = fuse_backing_get(fb);
>         rcu_read_unlock();
>
> diff --git a/fs/fuse/fuse_i.h b/fs/fuse/fuse_i.h
> index 85f738c53122..db4c07a496f0 100644
> --- a/fs/fuse/fuse_i.h
> +++ b/fs/fuse/fuse_i.h
> @@ -30,6 +30,7 @@
>  #include <linux/pid_namespace.h>
>  #include <linux/refcount.h>
>  #include <linux/user_namespace.h>
> +#include <linux/hashtable.h>
>
>  /** Default max number of pages that can be used in a single read request */
>  #define FUSE_DEFAULT_MAX_PAGES_PER_REQ 32
> @@ -94,6 +95,10 @@ struct fuse_backing {
>         /* refcount */
>         refcount_t count;
>         struct rcu_head rcu;
> +
> +       /* ID Allocation */
> +       int id;

move this to the hole next to count.

Mahad,

I am guessing that you are a student doing a summer project?
and you picked up on the FIXME comment?
It's fine, no complaints about that, but TBH, I don't know that there
is huge value to real life users
from making this change, because the measurements were not done on
real life workloads.

However, I do know that there are real users who would benefit from moving the
allocator to userspace, so by slightly changing your plan you could also help
real users and learn how real upstream development works.

Thanks,
Amir.