diff mbox series

[09/18] srcu: Fix srcu_struct node grpmask overflow on 64-bit systems

Message ID 20231013115902.1059735-10-frederic@kernel.org (mailing list archive)
State Mainlined
Commit d8d5b7bf6f2105883bbd91bbd4d5b67e4e3dff71
Headers show
Series RCU fixes for v6.7 | expand

Commit Message

Frederic Weisbecker Oct. 13, 2023, 11:58 a.m. UTC 
From: Denis Arefev <arefev@swemel.ru>

The value of a bitwise expression 1 << (cpu - sdp->mynode->grplo)
is subject to overflow due to a failure to cast operands to a larger
data type before performing the bitwise operation.

The maximum result of this subtraction is defined by the RCU_FANOUT_LEAF
Kconfig option, which on 64-bit systems defaults to 16 (resulting in a
maximum shift of 15), but which can be set up as high as 64 (resulting
in a maximum shift of 63).  A value of 31 can result in sign extension,
resulting in 0xffffffff80000000 instead of the desired 0x80000000.
A value of 32 or greater triggers undefined behavior per the C standard.

This bug has not been known to cause issues because almost all kernels
take the default CONFIG_RCU_FANOUT_LEAF=16.  Furthermore, as long as a
given compiler gives a deterministic non-zero result for 1<<N for N>=32,
the code correctly invokes all SRCU callbacks, albeit wasting CPU time
along the way.

This commit therefore substitutes the correct 1UL for the buggy 1.

Found by Linux Verification Center (linuxtesting.org) with SVACE.

Signed-off-by: Denis Arefev <arefev@swemel.ru>
Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
Cc: David Laight <David.Laight@aculab.com>
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
Signed-off-by: Frederic Weisbecker <frederic@kernel.org>
---
 kernel/rcu/srcutree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Comments

David Laight Oct. 13, 2023, 12:54 p.m. UTC | #1 
From: Frederic Weisbecker
> Sent: 13 October 2023 12:59
> 
> The value of a bitwise expression 1 << (cpu - sdp->mynode->grplo)
> is subject to overflow due to a failure to cast operands to a larger
> data type before performing the bitwise operation.
> 
> The maximum result of this subtraction is defined by the RCU_FANOUT_LEAF
> Kconfig option, which on 64-bit systems defaults to 16 (resulting in a
> maximum shift of 15), but which can be set up as high as 64 (resulting
> in a maximum shift of 63).  A value of 31 can result in sign extension,
> resulting in 0xffffffff80000000 instead of the desired 0x80000000.
> A value of 32 or greater triggers undefined behavior per the C standard.
> 
> This bug has not been known to cause issues because almost all kernels
> take the default CONFIG_RCU_FANOUT_LEAF=16.  Furthermore, as long as a
> given compiler gives a deterministic non-zero result for 1<<N for N>=32,
> the code correctly invokes all SRCU callbacks, albeit wasting CPU time
> along the way.
> 
> This commit therefore substitutes the correct 1UL for the buggy 1.
> 
> Found by Linux Verification Center (linuxtesting.org) with SVACE.
> 
> Signed-off-by: Denis Arefev <arefev@swemel.ru>
> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> Cc: David Laight <David.Laight@aculab.com>
> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> Signed-off-by: Frederic Weisbecker <frederic@kernel.org>
> ---
>  kernel/rcu/srcutree.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 833a8f848a90..5602042856b1 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -223,7 +223,7 @@ static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags)
>  				snp->grplo = cpu;
>  			snp->grphi = cpu;
>  		}
> -		sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> +		sdp->grpmask = 1UL << (cpu - sdp->mynode->grplo);
>  	}
>  	smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_WAIT_BARRIER);
>  	return true;
> @@ -835,7 +835,7 @@ static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp
>  	int cpu;
> 
>  	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> -		if (!(mask & (1 << (cpu - snp->grplo))))
> +		if (!(mask & (1UL << (cpu - snp->grplo))))
>  			continue;
>  		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
>  	}

That loop is entirely horrid.
The compiler almost certainly has to reload snp->grphi every iteration.
Also it looks as though the bottom bit of mask is checked first.
So how about:
	grphi = snp->grphi;
	for (cpu = snp->grplo; cpu <= grphi; cpu++, mask >>= 1) {
		if (!(mask & 1))
			continue;
		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
	}

	David		

> --
> 2.34.1

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
Frederic Weisbecker Oct. 13, 2023, 2:11 p.m. UTC | #2 
On Fri, Oct 13, 2023 at 12:54:32PM +0000, David Laight wrote:
> From: Frederic Weisbecker
> > Sent: 13 October 2023 12:59
> > 
> > The value of a bitwise expression 1 << (cpu - sdp->mynode->grplo)
> > is subject to overflow due to a failure to cast operands to a larger
> > data type before performing the bitwise operation.
> > 
> > The maximum result of this subtraction is defined by the RCU_FANOUT_LEAF
> > Kconfig option, which on 64-bit systems defaults to 16 (resulting in a
> > maximum shift of 15), but which can be set up as high as 64 (resulting
> > in a maximum shift of 63).  A value of 31 can result in sign extension,
> > resulting in 0xffffffff80000000 instead of the desired 0x80000000.
> > A value of 32 or greater triggers undefined behavior per the C standard.
> > 
> > This bug has not been known to cause issues because almost all kernels
> > take the default CONFIG_RCU_FANOUT_LEAF=16.  Furthermore, as long as a
> > given compiler gives a deterministic non-zero result for 1<<N for N>=32,
> > the code correctly invokes all SRCU callbacks, albeit wasting CPU time
> > along the way.
> > 
> > This commit therefore substitutes the correct 1UL for the buggy 1.
> > 
> > Found by Linux Verification Center (linuxtesting.org) with SVACE.
> > 
> > Signed-off-by: Denis Arefev <arefev@swemel.ru>
> > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > Cc: David Laight <David.Laight@aculab.com>
> > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > Signed-off-by: Frederic Weisbecker <frederic@kernel.org>
> > ---
> >  kernel/rcu/srcutree.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > index 833a8f848a90..5602042856b1 100644
> > --- a/kernel/rcu/srcutree.c
> > +++ b/kernel/rcu/srcutree.c
> > @@ -223,7 +223,7 @@ static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags)
> >  				snp->grplo = cpu;
> >  			snp->grphi = cpu;
> >  		}
> > -		sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> > +		sdp->grpmask = 1UL << (cpu - sdp->mynode->grplo);
> >  	}
> >  	smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_WAIT_BARRIER);
> >  	return true;
> > @@ -835,7 +835,7 @@ static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp
> >  	int cpu;
> > 
> >  	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> > -		if (!(mask & (1 << (cpu - snp->grplo))))
> > +		if (!(mask & (1UL << (cpu - snp->grplo))))
> >  			continue;
> >  		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
> >  	}
> 
> That loop is entirely horrid.
> The compiler almost certainly has to reload snp->grphi every iteration.
> Also it looks as though the bottom bit of mask is checked first.
> So how about:
> 	grphi = snp->grphi;
> 	for (cpu = snp->grplo; cpu <= grphi; cpu++, mask >>= 1) {
> 		if (!(mask & 1))
> 			continue;
> 		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
> 	}

Well, it's cache-hot and RCU update side is not really a fast-path.
Not sure it's worth optimizing...

Thanks.

> 
> 	David		
> 
> > --
> > 2.34.1
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
>
diff mbox series

Patch

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 833a8f848a90..5602042856b1 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -223,7 +223,7 @@  static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags)
 				snp->grplo = cpu;
 			snp->grphi = cpu;
 		}
-		sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
+		sdp->grpmask = 1UL << (cpu - sdp->mynode->grplo);
 	}
 	smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_WAIT_BARRIER);
 	return true;
@@ -835,7 +835,7 @@  static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp
 	int cpu;
 
 	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
-		if (!(mask & (1 << (cpu - snp->grplo))))
+		if (!(mask & (1UL << (cpu - snp->grplo))))
 			continue;
 		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
 	}