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

[Frederic Weisbecker]

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@xxxxxxxxx>
> > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
> > Reviewed-by: Joel Fernandes (Google) <joel@xxxxxxxxxxxxxxxxx>
> > Cc: David Laight <David.Laight@xxxxxxxxxx>
> > Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxx>
> > Signed-off-by: Frederic Weisbecker <frederic@xxxxxxxxxx>
> > ---
> >  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)
>