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);
