[PATCH] futex: Improve get_inode_sequence_number()

[PATCH] futex: Improve get_inode_sequence_number()

[Uros Bizjak]

Rewrite FOR loop to a DO-WHILE loop where returns are moved out of
the loop. Use atomic64_inc_return() instead of atomic64_add_return().

Use !atomic64_try_cmpxchg_relaxed(*ptr, &old, new) instead of
atomic64_cmpxchg_relaxed (*ptr, old, new) != old.  x86 CMPXCHG
instruction returns success in ZF flag, so this change saves
a compare after CMPXCHG..

Note that due to early return, "old" equals to 0 before
atomic64_cmpxchg_relaxed(), so initialization of variable to 0
is not needed.

Signed-off-by: Uros Bizjak <ubizjak@gmail.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Darren Hart <dvhart@infradead.org>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: "André Almeida" <andrealmeid@igalia.com>
---
 kernel/futex/core.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)

diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index 136768ae2637..665501c885d0 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -173,23 +173,20 @@ futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,
 static u64 get_inode_sequence_number(struct inode *inode)
 {
 	static atomic64_t i_seq;
-	u64 old;
+	u64 old, new;
 
 	/* Does the inode already have a sequence number? */
 	old = atomic64_read(&inode->i_sequence);
 	if (likely(old))
 		return old;
 
-	for (;;) {
-		u64 new = atomic64_add_return(1, &i_seq);
-		if (WARN_ON_ONCE(!new))
-			continue;
+	do {
+		new = atomic64_inc_return(&i_seq);
+	} while	(WARN_ON_ONCE(!new));
 
-		old = atomic64_cmpxchg_relaxed(&inode->i_sequence, 0, new);
-		if (old)
-			return old;
-		return new;
-	}
+	if (!atomic64_try_cmpxchg_relaxed(&inode->i_sequence, &old, new))
+		return old;
+	return new;
 }
 
 /**
-- 
2.46.2

Re: [PATCH] futex: Improve get_inode_sequence_number()

[André Almeida]

Hi Uros,

Em 03/10/2024 09:18, Uros Bizjak escreveu:
> Rewrite FOR loop to a DO-WHILE loop where returns are moved out of
> the loop. Use atomic64_inc_return() instead of atomic64_add_return().
> 
> Use !atomic64_try_cmpxchg_relaxed(*ptr, &old, new) instead of
> atomic64_cmpxchg_relaxed (*ptr, old, new) != old.  x86 CMPXCHG
> instruction returns success in ZF flag, so this change saves
> a compare after CMPXCHG..
> 
> Note that due to early return, "old" equals to 0 before
> atomic64_cmpxchg_relaxed(), so initialization of variable to 0
> is not needed.
> 

Despite the implicitly `old = 0`, I think it makes people life easier to 
know explicitly that `old = 0` in the cmpxchg() call.

Also, please state in the commit message the motivation of doing this 
change. Is to make the code simpler or to try to save some instructions? 
The compiler might be already saving such instructions for us :)

> Signed-off-by: Uros Bizjak <ubizjak@gmail.com>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Darren Hart <dvhart@infradead.org>
> Cc: Davidlohr Bueso <dave@stgolabs.net>
> Cc: "André Almeida" <andrealmeid@igalia.com>
> ---
>   kernel/futex/core.c | 17 +++++++----------
>   1 file changed, 7 insertions(+), 10 deletions(-)
> 
> diff --git a/kernel/futex/core.c b/kernel/futex/core.c
> index 136768ae2637..665501c885d0 100644
> --- a/kernel/futex/core.c
> +++ b/kernel/futex/core.c
> @@ -173,23 +173,20 @@ futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,
>   static u64 get_inode_sequence_number(struct inode *inode)
>   {
>   	static atomic64_t i_seq;
> -	u64 old;
> +	u64 old, new;
>   
>   	/* Does the inode already have a sequence number? */
>   	old = atomic64_read(&inode->i_sequence);
>   	if (likely(old))
>   		return old;
>   
> -	for (;;) {
> -		u64 new = atomic64_add_return(1, &i_seq);
> -		if (WARN_ON_ONCE(!new))
> -			continue;
> +	do {
> +		new = atomic64_inc_return(&i_seq);
> +	} while	(WARN_ON_ONCE(!new));
>   
> -		old = atomic64_cmpxchg_relaxed(&inode->i_sequence, 0, new);
> -		if (old)
> -			return old;
> -		return new;
> -	}
> +	if (!atomic64_try_cmpxchg_relaxed(&inode->i_sequence, &old, new))
> +		return old;
> +	return new;
>   }
>   
>   /**

Re: [PATCH] futex: Improve get_inode_sequence_number()

[Uros Bizjak]

On Thu, Oct 3, 2024 at 3:29 PM André Almeida <andrealmeid@igalia.com> wrote:
>
> Hi Uros,
>
> Em 03/10/2024 09:18, Uros Bizjak escreveu:
> > Rewrite FOR loop to a DO-WHILE loop where returns are moved out of
> > the loop. Use atomic64_inc_return() instead of atomic64_add_return().
> >
> > Use !atomic64_try_cmpxchg_relaxed(*ptr, &old, new) instead of
> > atomic64_cmpxchg_relaxed (*ptr, old, new) != old.  x86 CMPXCHG
> > instruction returns success in ZF flag, so this change saves
> > a compare after CMPXCHG..
> >
> > Note that due to early return, "old" equals to 0 before
> > atomic64_cmpxchg_relaxed(), so initialization of variable to 0
> > is not needed.
> >
>
> Despite the implicitly `old = 0`, I think it makes people life easier to
> know explicitly that `old = 0` in the cmpxchg() call.

No problem; in this place the compiler is smart enough that explicit
initialization doesn't make a difference.

> Also, please state in the commit message the motivation of doing this
> change. Is to make the code simpler or to try to save some instructions?

I tried to modernize the usage of cmpxchg with try_cmpxchg, but then I
noticed the opportunity to make the code simpler (please see the
"continue" in the for loop that creates some kind of degenerated for
loop). So, the motivation is to simplify and modernize the code.

> The compiler might be already saving such instructions for us :)

That would be nice, but unfortunately, the case of cmpxchg() vs.
try_cmpxchg() is too hard for the compiler to optimize.

I will prepare a v2 that incorporates all your suggestions.

Thanks,
Uros.