Re: [RFC PATCH] vfs: add rcu-based find_inode variants for iget ops

From: Jan Kara
Date: Thu Jun 06 2024 - 12:31:33 EST

Next message: Friedrich Weber: "Re: [PATCH] block: fix request.queuelist usage in flush"
Previous message: Mudit Sharma: "[PATCH v4 2/2] iio: light: ROHM BH1745 colour sensor"
In reply to: Mateusz Guzik: "[RFC PATCH] vfs: add rcu-based find_inode variants for iget ops"
Next in thread: Mateusz Guzik: "Re: [RFC PATCH] vfs: add rcu-based find_inode variants for iget ops"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Thu 06-06-24 16:05:15, Mateusz Guzik wrote:
> Instantiating a new inode normally takes the global inode hash lock
> twice:
> 1. once to check if it happens to already be present
> 2. once to add it to the hash
>
> The back-to-back lock/unlock pattern is known to degrade performance
> significantly, which is further exacerbated if the hash is heavily
> populated (long chains to walk, extending hold time). Arguably hash
> sizing and hashing algo need to be revisited, but that's beyond the
> scope of this patch.
>
> A long term fix would introduce fine-grained locking, this was attempted
> in [1], but that patchset was already posted several times and appears
> stalled.
>
> A simpler idea which solves majority of the problem and which may be
> good enough for the time being is to use RCU for the initial lookup.
> Basic RCU support is already present in the hash, it is just not being
> used for lookup on inode creation.
>
> iget_locked consumers (notably ext4) get away without any changes
> because inode comparison method is built-in.
>
> iget5_locked and ilookup5_nowait consumers pass a custom callback. Since
> removal of locking adds more problems (inode can be changing) it's not
> safe to assume all filesystems happen to cope. Thus iget5_locked_rcu
> ilookup5_nowait_rcu get added, requiring manual conversion.

BTW, why not ilookup5_rcu() as well? To keep symmetry with non-RCU APIs and
iget5_locked_rcu() could then use ilookup5_rcu(). I presume eventually we'd
like to trasition everything to these RCU based methods?

> In order to reduce code duplication find_inode and find_inode_fast grow
> an argument indicating whether inode hash lock is held, which is passed
> down should sleeping be necessary. They always rcu_read_lock, which is
> redundant but harmless. Doing it conditionally reduces readability for
> no real gain that I can see. RCU-alike restrictions were already put on
> callbacks due to the hash spinlock being held.
>
> Benchmarked with the following: a 32-core vm with 24GB of RAM, a
> dedicated fs partition. 20 separate trees with 1000 directories * 1000
> files. Then walked by 20 processes issuing stat on files, each on a
> dedicated tree. Testcase is at [2].
>
> In this particular workload, mimicking a real-world setup $elsewhere,
> the initial lookup is guaranteed to fail, guaranteeing the 2 lock
> acquires. At the same time RAM is scarce enough enough compared to the
> demand that inodes keep needing to be recycled.
>
> Total real time fluctuates by 1-2s, sample results:
>
> ext4 (needed mkfs.ext4 -N 24000000):
> before: 3.77s user 890.90s system 1939% cpu 46.118 total
> after: 3.24s user 397.73s system 1858% cpu 21.581 total (-53%)
>
> btrfs (s/iget5_locked/iget5_locked_rcu in fs/btrfs/inode.c):
> before: 3.54s user 892.30s system 1966% cpu 45.549 total
> after: 3.28s user 738.66s system 1955% cpu 37.932 total (-16.7%)
>
> btrfs is heavily bottlenecked on its own locks, so the improvement is
> small in comparison.
>
> [1] https://lore.kernel.org/all/20231206060629.2827226-1-david@xxxxxxxxxxxxx/
> [2] https://people.freebsd.org/~mjg/fstree.tgz

Nice results. I've looked through the patch and otherwise I didn't find any
issue.

Honza

>
> Signed-off-by: Mateusz Guzik <mjguzik@xxxxxxxxx>
> ---
>
> This is an initial submission to gauge interest.
>
> I do claim this provides great bang for the buck, I don't claim it
> solves the problem overall. *something* finer-grained will need to
> land.
>
> I wanted to add bcachefs to the list, but I ran into memory reclamation
> issues again (first time here:
> https://lore.kernel.org/all/CAGudoHGenxzk0ZqPXXi1_QDbfqQhGHu+wUwzyS6WmfkUZ1HiXA@xxxxxxxxxxxxxx/),
> did not have time to mess with diagnostic to write a report yet.
>
> I'll post a patchset with this (+ tidy ups to comments and whatnot) +
> btrfs + bcachefs conversion after the above gets reported and sorted
> out.
>
> Also interestingly things improved since last year, when Linux needed
> about a minute.
>
> fs/inode.c | 106 +++++++++++++++++++++++++++++++++++++--------
> include/linux/fs.h | 10 ++++-
> 2 files changed, 98 insertions(+), 18 deletions(-)
>
> diff --git a/fs/inode.c b/fs/inode.c
> index 3a41f83a4ba5..f40b868f491f 100644
> --- a/fs/inode.c
> +++ b/fs/inode.c
> @@ -886,36 +886,43 @@ long prune_icache_sb(struct super_block *sb, struct shrink_control *sc)
> return freed;
> }
>
> -static void __wait_on_freeing_inode(struct inode *inode);
> +static void __wait_on_freeing_inode(struct inode *inode, bool locked);
> /*
> * Called with the inode lock held.
> */
> static struct inode *find_inode(struct super_block *sb,
> struct hlist_head *head,
> int (*test)(struct inode *, void *),
> - void *data)
> + void *data, bool locked)
> {
> struct inode *inode = NULL;
>
> + if (locked)
> + lockdep_assert_held(&inode_hash_lock);
> +
> + rcu_read_lock();
> repeat:
> - hlist_for_each_entry(inode, head, i_hash) {
> + hlist_for_each_entry_rcu(inode, head, i_hash) {
> if (inode->i_sb != sb)
> continue;
> if (!test(inode, data))
> continue;
> spin_lock(&inode->i_lock);
> if (inode->i_state & (I_FREEING|I_WILL_FREE)) {
> - __wait_on_freeing_inode(inode);
> + __wait_on_freeing_inode(inode, locked);
> goto repeat;
> }
> if (unlikely(inode->i_state & I_CREATING)) {
> spin_unlock(&inode->i_lock);
> + rcu_read_unlock();
> return ERR_PTR(-ESTALE);
> }
> __iget(inode);
> spin_unlock(&inode->i_lock);
> + rcu_read_unlock();
> return inode;
> }
> + rcu_read_unlock();
> return NULL;
> }
>
> @@ -924,29 +931,37 @@ static struct inode *find_inode(struct super_block *sb,
> * iget_locked for details.
> */
> static struct inode *find_inode_fast(struct super_block *sb,
> - struct hlist_head *head, unsigned long ino)
> + struct hlist_head *head, unsigned long ino,
> + bool locked)
> {
> struct inode *inode = NULL;
>
> + if (locked)
> + lockdep_assert_held(&inode_hash_lock);
> +
> + rcu_read_lock();
> repeat:
> - hlist_for_each_entry(inode, head, i_hash) {
> + hlist_for_each_entry_rcu(inode, head, i_hash) {
> if (inode->i_ino != ino)
> continue;
> if (inode->i_sb != sb)
> continue;
> spin_lock(&inode->i_lock);
> if (inode->i_state & (I_FREEING|I_WILL_FREE)) {
> - __wait_on_freeing_inode(inode);
> + __wait_on_freeing_inode(inode, locked);
> goto repeat;
> }
> if (unlikely(inode->i_state & I_CREATING)) {
> spin_unlock(&inode->i_lock);
> + rcu_read_unlock();
> return ERR_PTR(-ESTALE);
> }
> __iget(inode);
> spin_unlock(&inode->i_lock);
> + rcu_read_unlock();
> return inode;
> }
> + rcu_read_unlock();
> return NULL;
> }
>
> @@ -1161,7 +1176,7 @@ struct inode *inode_insert5(struct inode *inode, unsigned long hashval,
>
> again:
> spin_lock(&inode_hash_lock);
> - old = find_inode(inode->i_sb, head, test, data);
> + old = find_inode(inode->i_sb, head, test, data, true);
> if (unlikely(old)) {
> /*
> * Uhhuh, somebody else created the same inode under us.
> @@ -1245,6 +1260,43 @@ struct inode *iget5_locked(struct super_block *sb, unsigned long hashval,
> }
> EXPORT_SYMBOL(iget5_locked);
>
> +/**
> + * iget5_locked_rcu - obtain an inode from a mounted file system
> + *
> + * This is equivalent to iget5_locked, except the @test callback must
> + * tolerate inode not being stable, including being mid-teardown.
> + */
> +struct inode *iget5_locked_rcu(struct super_block *sb, unsigned long hashval,
> + int (*test)(struct inode *, void *),
> + int (*set)(struct inode *, void *), void *data)
> +{
> + struct hlist_head *head = inode_hashtable + hash(sb, hashval);
> + struct inode *inode, *new;
> +
> +again:
> + inode = find_inode(sb, head, test, data, false);
> + if (inode) {
> + if (IS_ERR(inode))
> + return NULL;
> + wait_on_inode(inode);
> + if (unlikely(inode_unhashed(inode))) {
> + iput(inode);
> + goto again;
> + }
> + return inode;
> + }
> +
> + new = alloc_inode(sb);
> + if (new) {
> + new->i_state = 0;
> + inode = inode_insert5(new, hashval, test, set, data);
> + if (unlikely(inode != new))
> + destroy_inode(new);
> + }
> + return inode;
> +}
> +EXPORT_SYMBOL(iget5_locked_rcu);
> +
> /**
> * iget_locked - obtain an inode from a mounted file system
> * @sb: super block of file system
> @@ -1263,9 +1315,7 @@ struct inode *iget_locked(struct super_block *sb, unsigned long ino)
> struct hlist_head *head = inode_hashtable + hash(sb, ino);
> struct inode *inode;
> again:
> - spin_lock(&inode_hash_lock);
> - inode = find_inode_fast(sb, head, ino);
> - spin_unlock(&inode_hash_lock);
> + inode = find_inode_fast(sb, head, ino, false);
> if (inode) {
> if (IS_ERR(inode))
> return NULL;
> @@ -1283,7 +1333,7 @@ struct inode *iget_locked(struct super_block *sb, unsigned long ino)
>
> spin_lock(&inode_hash_lock);
> /* We released the lock, so.. */
> - old = find_inode_fast(sb, head, ino);
> + old = find_inode_fast(sb, head, ino, true);
> if (!old) {
> inode->i_ino = ino;
> spin_lock(&inode->i_lock);
> @@ -1419,13 +1469,31 @@ struct inode *ilookup5_nowait(struct super_block *sb, unsigned long hashval,
> struct inode *inode;
>
> spin_lock(&inode_hash_lock);
> - inode = find_inode(sb, head, test, data);
> + inode = find_inode(sb, head, test, data, true);
> spin_unlock(&inode_hash_lock);
>
> return IS_ERR(inode) ? NULL : inode;
> }
> EXPORT_SYMBOL(ilookup5_nowait);
>
> +/**
> + * ilookup5_nowait_rcu - search for an inode in the inode cache
> + *
> + * This is equivalent to ilookup5_nowait, except the @test callback must
> + * tolerate inode not being stable, including being mid-teardown.
> + */
> +struct inode *ilookup5_nowait_rcu(struct super_block *sb, unsigned long hashval,
> + int (*test)(struct inode *, void *), void *data)
> +{
> + struct hlist_head *head = inode_hashtable + hash(sb, hashval);
> + struct inode *inode;
> +
> + inode = find_inode(sb, head, test, data, false);
> +
> + return IS_ERR(inode) ? NULL : inode;
> +}
> +EXPORT_SYMBOL(ilookup5_nowait_rcu);
> +
> /**
> * ilookup5 - search for an inode in the inode cache
> * @sb: super block of file system to search
> @@ -1474,7 +1542,7 @@ struct inode *ilookup(struct super_block *sb, unsigned long ino)
> struct inode *inode;
> again:
> spin_lock(&inode_hash_lock);
> - inode = find_inode_fast(sb, head, ino);
> + inode = find_inode_fast(sb, head, ino, true);
> spin_unlock(&inode_hash_lock);
>
> if (inode) {
> @@ -2235,17 +2303,21 @@ EXPORT_SYMBOL(inode_needs_sync);
> * wake_up_bit(&inode->i_state, __I_NEW) after removing from the hash list
> * will DTRT.
> */
> -static void __wait_on_freeing_inode(struct inode *inode)
> +static void __wait_on_freeing_inode(struct inode *inode, bool locked)
> {
> wait_queue_head_t *wq;
> DEFINE_WAIT_BIT(wait, &inode->i_state, __I_NEW);
> wq = bit_waitqueue(&inode->i_state, __I_NEW);
> prepare_to_wait(wq, &wait.wq_entry, TASK_UNINTERRUPTIBLE);
> spin_unlock(&inode->i_lock);
> - spin_unlock(&inode_hash_lock);
> + rcu_read_unlock();
> + if (locked)
> + spin_unlock(&inode_hash_lock);
> schedule();
> finish_wait(wq, &wait.wq_entry);
> - spin_lock(&inode_hash_lock);
> + if (locked)
> + spin_lock(&inode_hash_lock);
> + rcu_read_lock();
> }
>
> static __initdata unsigned long ihash_entries;
> diff --git a/include/linux/fs.h b/include/linux/fs.h
> index 0283cf366c2a..2817c915d355 100644
> --- a/include/linux/fs.h
> +++ b/include/linux/fs.h
> @@ -3021,6 +3021,9 @@ extern void d_mark_dontcache(struct inode *inode);
> extern struct inode *ilookup5_nowait(struct super_block *sb,
> unsigned long hashval, int (*test)(struct inode *, void *),
> void *data);
> +extern struct inode *ilookup5_nowait_rcu(struct super_block *sb,
> + unsigned long hashval, int (*test)(struct inode *, void *),
> + void *data);
> extern struct inode *ilookup5(struct super_block *sb, unsigned long hashval,
> int (*test)(struct inode *, void *), void *data);
> extern struct inode *ilookup(struct super_block *sb, unsigned long ino);
> @@ -3029,7 +3032,12 @@ extern struct inode *inode_insert5(struct inode *inode, unsigned long hashval,
> int (*test)(struct inode *, void *),
> int (*set)(struct inode *, void *),
> void *data);
> -extern struct inode * iget5_locked(struct super_block *, unsigned long, int (*test)(struct inode *, void *), int (*set)(struct inode *, void *), void *);
> +extern struct inode * iget5_locked(struct super_block *, unsigned long,
> + int (*test)(struct inode *, void *),
> + int (*set)(struct inode *, void *), void *);
> +extern struct inode * iget5_locked_rcu(struct super_block *, unsigned long,
> + int (*test)(struct inode *, void *),
> + int (*set)(struct inode *, void *), void *);
> extern struct inode * iget_locked(struct super_block *, unsigned long);
> extern struct inode *find_inode_nowait(struct super_block *,
> unsigned long,
> --
> 2.43.0
>
--
Jan Kara <jack@xxxxxxxx>
SUSE Labs, CR

Next message: Friedrich Weber: "Re: [PATCH] block: fix request.queuelist usage in flush"
Previous message: Mudit Sharma: "[PATCH v4 2/2] iio: light: ROHM BH1745 colour sensor"
In reply to: Mateusz Guzik: "[RFC PATCH] vfs: add rcu-based find_inode variants for iget ops"
Next in thread: Mateusz Guzik: "Re: [RFC PATCH] vfs: add rcu-based find_inode variants for iget ops"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]