[RFC PATCH v1] fuse: add periodic task to invalidate expired dentries

[Luis Henriques]

dentries may stay around for a long time, and a mechanism to invalidate
them if they have expired is desirable.  This patch adds a task that will
periodically check if there are dentries which have expired and need to be
invalidated.

Signed-off-by: Luis Henriques <luis@xxxxxxxxxx>
---
Hi Miklos,

I know the 'epoch' patch discussion hasn't yet finished[1], but here's a
follow-up patch.  It's still WIP, it hasn't gone through a lot of testing
yet, but it may help with the whole discussion.

As you suggested, this patch keeps track of all the dentries in a tree
sorted by expiry time.  The workqueue will walk through the expired dentries
and invalidate them.  If the epoch has been incremented, then *all* dentries
are invalidated.

I still have a few questions:

1. Should we have a mount option to enable this task?
2. Should the period (not really 'period', but yeah) be configurable?

Any feedback is welcome.

[1] https://lore.kernel.org/all/20250226091451.11899-1-luis@xxxxxxxxxx/

 fs/fuse/dir.c    | 138 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/fuse/fuse_i.h |  11 ++++
 fs/fuse/inode.c  |   4 ++
 3 files changed, 153 insertions(+)

diff --git a/fs/fuse/dir.c b/fs/fuse/dir.c
index 1f578f455364..e51a7340fa5a 100644
--- a/fs/fuse/dir.c
+++ b/fs/fuse/dir.c
@@ -62,6 +62,142 @@ static inline u64 fuse_dentry_time(const struct dentry *entry)
 }
 #endif
 
+struct dentry_node {
+	struct rb_node node;
+	struct dentry *dentry;
+};
+
+static void fuse_dentry_tree_add_node(struct dentry *dentry)
+{
+	struct fuse_conn *fc = get_fuse_conn_super(dentry->d_sb);
+	struct dentry_node *dn, *cur;
+	struct rb_node **p, *parent;
+	bool start_work = false;
+
+	dn = kmalloc(sizeof(*dn), GFP_KERNEL);
+	if (!dn)
+		return;
+	dn->dentry = dget(dentry);
+	spin_lock(&fc->dentry_tree_lock);
+	start_work = RB_EMPTY_ROOT(&fc->dentry_tree);
+	p = &fc->dentry_tree.rb_node;
+	while (*p) {
+		parent = *p;
+		cur = rb_entry(*p, struct dentry_node, node);
+		if (fuse_dentry_time(dn->dentry) >
+		    fuse_dentry_time(cur->dentry))
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+	rb_link_node(&dn->node, parent, p);
+	rb_insert_color(&dn->node, &fc->dentry_tree);
+	spin_unlock(&fc->dentry_tree_lock);
+	if (start_work)
+		schedule_delayed_work(&fc->dentry_tree_work,
+				      secs_to_jiffies(5));
+}
+
+static void fuse_dentry_tree_del_node(struct dentry *dentry)
+{
+	struct fuse_conn *fc = get_fuse_conn_super(dentry->d_sb);
+	struct dentry_node *cur;
+	struct rb_node **p, *parent;
+
+	spin_lock(&fc->dentry_tree_lock);
+	p = &fc->dentry_tree.rb_node;
+	while (*p) {
+		parent = *p;
+		cur = rb_entry(*p, struct dentry_node, node);
+		if (fuse_dentry_time(dentry) > fuse_dentry_time(cur->dentry))
+			p = &(*p)->rb_left;
+		else if (fuse_dentry_time(dentry) <
+			 fuse_dentry_time(cur->dentry))
+			p = &(*p)->rb_right;
+		else {
+			rb_erase(*p, &fc->dentry_tree);
+			dput(cur->dentry);
+			kfree(cur);
+			break;
+		}
+	}
+	spin_unlock(&fc->dentry_tree_lock);
+}
+
+void fuse_dentry_tree_prune(struct fuse_conn *fc)
+{
+	struct rb_node *n;
+	struct dentry_node *dn;
+
+	cancel_delayed_work_sync(&fc->dentry_tree_work);
+
+	spin_lock(&fc->dentry_tree_lock);
+	while (!RB_EMPTY_ROOT(&fc->dentry_tree)) {
+		n = rb_first(&fc->dentry_tree);
+		dn = rb_entry(n, struct dentry_node, node);
+		rb_erase(n, &fc->dentry_tree);
+		dput(dn->dentry);
+		kfree(dn);
+	}
+	spin_unlock(&fc->dentry_tree_lock);
+}
+
+/*
+ * Global workqueue task that will periodically check for expired dentries in
+ * the dentries tree.
+ *
+ * A dentry has expired if:
+ *   1) it has been around for too long or
+ *   2) the connection epoch has been incremented
+ * For this second case, all dentries will be expired.
+ *
+ * The task will be rescheduled as long as the dentries tree is not empty.
+ */
+void fuse_dentry_tree_work(struct work_struct *work)
+{
+	struct fuse_conn *fc = container_of(work, struct fuse_conn,
+					    dentry_tree_work.work);
+	struct dentry_node *dn;
+	struct rb_node *node;
+	struct dentry *entry;
+	u64 now;
+	int epoch;
+	bool expire_all = false;
+	bool is_first = true;
+	bool reschedule;
+
+	spin_lock(&fc->dentry_tree_lock);
+	now = get_jiffies_64();
+	epoch = atomic_read(&fc->epoch);
+
+	node = rb_first(&fc->dentry_tree);
+
+	while (node) {
+		dn = rb_entry(node, struct dentry_node, node);
+		node = rb_next(node);
+		entry = dn->dentry;
+		if (is_first) {
+			/* expire all entries if epoch was incremented */
+			if (entry->d_time < epoch)
+				expire_all = true;
+			is_first = false;
+		}
+		if (expire_all || (fuse_dentry_time(entry) < now)) {
+			rb_erase(&dn->node, &fc->dentry_tree);
+			d_invalidate(entry);
+			dput(entry);
+			kfree(dn);
+		} else
+			break;
+	}
+	reschedule = !RB_EMPTY_ROOT(&fc->dentry_tree);
+	spin_unlock(&fc->dentry_tree_lock);
+
+	if (reschedule)
+		schedule_delayed_work(&fc->dentry_tree_work,
+				      FUSE_DENTRY_TREE_WORK_INTERVAL);
+}
+
 static void fuse_dentry_settime(struct dentry *dentry, u64 time)
 {
 	struct fuse_conn *fc = get_fuse_conn_super(dentry->d_sb);
@@ -81,6 +217,7 @@ static void fuse_dentry_settime(struct dentry *dentry, u64 time)
 	}
 
 	__fuse_dentry_settime(dentry, time);
+	fuse_dentry_tree_add_node(dentry);
 }
 
 /*
@@ -280,6 +417,7 @@ static int fuse_dentry_revalidate(struct inode *dir, const struct qstr *name,
 
 invalid:
 	ret = 0;
+	fuse_dentry_tree_del_node(entry);
 	goto out;
 }
 
diff --git a/fs/fuse/fuse_i.h b/fs/fuse/fuse_i.h
index 06eecc125f89..942a3098111f 100644
--- a/fs/fuse/fuse_i.h
+++ b/fs/fuse/fuse_i.h
@@ -938,6 +938,13 @@ struct fuse_conn {
 	/**  uring connection information*/
 	struct fuse_ring *ring;
 #endif
+
+	/** Cache dentries tree */
+	struct rb_root dentry_tree;
+	/** Look to protect dentry_tree access */
+	spinlock_t dentry_tree_lock;
+	/** Periodic delayed work to invalidate expired dentries */
+	struct delayed_work dentry_tree_work;
 };
 
 /*
@@ -1219,6 +1226,10 @@ void fuse_request_end(struct fuse_req *req);
 void fuse_abort_conn(struct fuse_conn *fc);
 void fuse_wait_aborted(struct fuse_conn *fc);
 
+#define FUSE_DENTRY_TREE_WORK_INTERVAL	secs_to_jiffies(5)
+void fuse_dentry_tree_prune(struct fuse_conn *fc);
+void fuse_dentry_tree_work(struct work_struct *work);
+
 /**
  * Invalidate inode attributes
  */
diff --git a/fs/fuse/inode.c b/fs/fuse/inode.c
index 5d2d29fad658..8984b7868c62 100644
--- a/fs/fuse/inode.c
+++ b/fs/fuse/inode.c
@@ -956,15 +956,18 @@ void fuse_conn_init(struct fuse_conn *fc, struct fuse_mount *fm,
 	memset(fc, 0, sizeof(*fc));
 	spin_lock_init(&fc->lock);
 	spin_lock_init(&fc->bg_lock);
+	spin_lock_init(&fc->dentry_tree_lock);
 	init_rwsem(&fc->killsb);
 	refcount_set(&fc->count, 1);
 	atomic_set(&fc->dev_count, 1);
 	atomic_set(&fc->epoch, 1);
 	init_waitqueue_head(&fc->blocked_waitq);
 	fuse_iqueue_init(&fc->iq, fiq_ops, fiq_priv);
+	INIT_DELAYED_WORK(&fc->dentry_tree_work, fuse_dentry_tree_work);
 	INIT_LIST_HEAD(&fc->bg_queue);
 	INIT_LIST_HEAD(&fc->entry);
 	INIT_LIST_HEAD(&fc->devices);
+	fc->dentry_tree = RB_ROOT;
 	atomic_set(&fc->num_waiting, 0);
 	fc->max_background = FUSE_DEFAULT_MAX_BACKGROUND;
 	fc->congestion_threshold = FUSE_DEFAULT_CONGESTION_THRESHOLD;
@@ -1999,6 +2002,7 @@ void fuse_conn_destroy(struct fuse_mount *fm)
 
 	fuse_abort_conn(fc);
 	fuse_wait_aborted(fc);
+	fuse_dentry_tree_prune(fc);
 
 	if (!list_empty(&fc->entry)) {
 		mutex_lock(&fuse_mutex);