[PATCH v2] The value may overflow

[PATCH v2] The value may overflow

[Denis Arefev]

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

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

Signed-off-by: Denis Arefev <arefev@swemel.ru>
---
v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by 
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 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 20d7a238d675..6c18e6005ae1 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;
@@ -833,7 +833,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);
 	}
-- 
2.25.1

Re: [PATCH v2] The value may overflow

[Mathieu Desnoyers]

On 9/4/23 05:42, Denis Arefev wrote:
> The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> is subject to overflow due to a failure to cast operands to a larger
> data type before performing arithmetic

The patch title should identify more precisely its context, e.g.:

"srcu: Fix srcu_struct node grpmask overflow on 64-bit systems"

Also, as I stated in my reply to the previous version, the patch commit
message should describe the impact of the bug it fixes.

Thanks,

Mathieu


> 
> Found by Linux Verification Center (linuxtesting.org) with SVACE.
> 
> Signed-off-by: Denis Arefev <arefev@swemel.ru>
> ---
> v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
> Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>   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 20d7a238d675..6c18e6005ae1 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;
> @@ -833,7 +833,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);
>   	}

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

RE: [PATCH v2] The value may overflow

[David Laight]

From: Mathieu Desnoyers
> Sent: 04 September 2023 11:24
> 
> On 9/4/23 05:42, Denis Arefev wrote:
> > The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> > is subject to overflow due to a failure to cast operands to a larger
> > data type before performing arithmetic
> 
> The patch title should identify more precisely its context, e.g.:
> 
> "srcu: Fix srcu_struct node grpmask overflow on 64-bit systems"
> 
> Also, as I stated in my reply to the previous version, the patch commit
> message should describe the impact of the bug it fixes.

And is the analysis complete?
Is 1UL right for 32bit archs??
Is 64 bits even enough??

	David

> 
> Thanks,
> 
> Mathieu
> 
> 
> >
> > Found by Linux Verification Center (linuxtesting.org) with SVACE.
> >
> > Signed-off-by: Denis Arefev <arefev@swemel.ru>
> > ---
> > v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
> > Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >   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 20d7a238d675..6c18e6005ae1 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;
> > @@ -833,7 +833,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);
> >   	}
> 
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [PATCH v2] The value may overflow

[Mathieu Desnoyers]

On 9/5/23 05:31, David Laight wrote:
> From: Mathieu Desnoyers
>> Sent: 04 September 2023 11:24
>>
>> On 9/4/23 05:42, Denis Arefev wrote:
>>> The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
>>> is subject to overflow due to a failure to cast operands to a larger
>>> data type before performing arithmetic
>>
>> The patch title should identify more precisely its context, e.g.:
>>
>> "srcu: Fix srcu_struct node grpmask overflow on 64-bit systems"
>>
>> Also, as I stated in my reply to the previous version, the patch commit
>> message should describe the impact of the bug it fixes.
> 
> And is the analysis complete?
> Is 1UL right for 32bit archs??
> Is 64 bits even enough??

I understand from include/linux/rcu_node_tree.h and kernel/rcu/Kconfig 
RCU_FANOUT and RCU_FANOUT_LEAF ranges that a 32-bit integer is 
sufficient to hold the mask on 32-bit architectures, and a 64-bit 
integer is enough on 64-bit architectures given the current implementation.

At least this appears to be the intent. I did not do a thorough analysis 
of the various parameter limits.

Thanks,

Mathieu

> 
> 	David
> 
>>
>> Thanks,
>>
>> Mathieu
>>
>>
>>>
>>> Found by Linux Verification Center (linuxtesting.org) with SVACE.
>>>
>>> Signed-off-by: Denis Arefev <arefev@swemel.ru>
>>> ---
>>> v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
>>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>>>    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 20d7a238d675..6c18e6005ae1 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;
>>> @@ -833,7 +833,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);
>>>    	}
>>
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 08:26:51AM -0400, Mathieu Desnoyers wrote:
> On 9/5/23 05:31, David Laight wrote:
> > From: Mathieu Desnoyers
> > > Sent: 04 September 2023 11:24
> > > 
> > > On 9/4/23 05:42, Denis Arefev wrote:
> > > > The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> > > > is subject to overflow due to a failure to cast operands to a larger
> > > > data type before performing arithmetic
> > > 
> > > The patch title should identify more precisely its context, e.g.:
> > > 
> > > "srcu: Fix srcu_struct node grpmask overflow on 64-bit systems"
> > > 
> > > Also, as I stated in my reply to the previous version, the patch commit
> > > message should describe the impact of the bug it fixes.
> > 
> > And is the analysis complete?
> > Is 1UL right for 32bit archs??
> > Is 64 bits even enough??
> 
> I understand from include/linux/rcu_node_tree.h and kernel/rcu/Kconfig
> RCU_FANOUT and RCU_FANOUT_LEAF ranges that a 32-bit integer is sufficient to
> hold the mask on 32-bit architectures, and a 64-bit integer is enough on
> 64-bit architectures given the current implementation.
> 
> At least this appears to be the intent. I did not do a thorough analysis of
> the various parameter limits.

Mathieu has it right.

32-bit kernels are unaffected by this bug.

RCU_FANOUT_LEAF defaults to 16, which means that a 64-bit kernel would
need more than 32 leaf rcu_node structures for the parent rcu_node
structure to need more than 32 bit to track its children.  This means
that more than 32*16=512 CPUs are required for this bug to affect 64-bit
systems.  And there really are systems this big, so I am surprised that
this has not shown up long ago.  But it would not be the first time that
objective reality surprised me.  ;-)

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> > 
> > 	David
> > 
> > > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > > 
> > > > 
> > > > Found by Linux Verification Center (linuxtesting.org) with SVACE.
> > > > 
> > > > Signed-off-by: Denis Arefev <arefev@swemel.ru>
> > > > ---
> > > > v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
> > > > Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > >    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 20d7a238d675..6c18e6005ae1 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;
> > > > @@ -833,7 +833,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);
> > > >    	}
> > > 
> > > --
> > > Mathieu Desnoyers
> > > EfficiOS Inc.
> > > https://www.efficios.com
> > 
> > -
> > Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> > Registration No: 1397386 (Wales)
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
> 

Re: [PATCH v2] The value may overflow

[Mathieu Desnoyers]

On 9/5/23 09:26, Paul E. McKenney wrote:
> On Tue, Sep 05, 2023 at 08:26:51AM -0400, Mathieu Desnoyers wrote:
>> On 9/5/23 05:31, David Laight wrote:
>>> From: Mathieu Desnoyers
>>>> Sent: 04 September 2023 11:24
>>>>
>>>> On 9/4/23 05:42, Denis Arefev wrote:
>>>>> The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
>>>>> is subject to overflow due to a failure to cast operands to a larger
>>>>> data type before performing arithmetic
>>>>
>>>> The patch title should identify more precisely its context, e.g.:
>>>>
>>>> "srcu: Fix srcu_struct node grpmask overflow on 64-bit systems"
>>>>
>>>> Also, as I stated in my reply to the previous version, the patch commit
>>>> message should describe the impact of the bug it fixes.
>>>
>>> And is the analysis complete?
>>> Is 1UL right for 32bit archs??
>>> Is 64 bits even enough??
>>
>> I understand from include/linux/rcu_node_tree.h and kernel/rcu/Kconfig
>> RCU_FANOUT and RCU_FANOUT_LEAF ranges that a 32-bit integer is sufficient to
>> hold the mask on 32-bit architectures, and a 64-bit integer is enough on
>> 64-bit architectures given the current implementation.
>>
>> At least this appears to be the intent. I did not do a thorough analysis of
>> the various parameter limits.
> 
> Mathieu has it right.
> 
> 32-bit kernels are unaffected by this bug.
> 
> RCU_FANOUT_LEAF defaults to 16, which means that a 64-bit kernel would
> need more than 32 leaf rcu_node structures for the parent rcu_node
> structure to need more than 32 bit to track its children.  This means
> that more than 32*16=512 CPUs are required for this bug to affect 64-bit
> systems.  And there really are systems this big, so I am surprised that
> this has not shown up long ago.  But it would not be the first time that
> objective reality surprised me.  ;-)

So with a 64-bit kernel, RCU_FANOUT_LEAF=16, if we have exactly 32 leaf 
rcu_node structures (exactly 512 CPUs), we end up in the situation where 
the type promotion from signed integer (32-bit) to unsigned long will 
carry the sign, and thus create a mask of 0xffffffff80000000.

So if this weird mask is indeed an issue we should state that 
configurations _starting from 512 CPUs_ are affected, not just those 
with more than 512 CPUs.

Thanks,

Mathieu


> 
> 							Thanx, Paul
> 
>> Thanks,
>>
>> Mathieu
>>
>>>
>>> 	David
>>>
>>>>
>>>> Thanks,
>>>>
>>>> Mathieu
>>>>
>>>>
>>>>>
>>>>> Found by Linux Verification Center (linuxtesting.org) with SVACE.
>>>>>
>>>>> Signed-off-by: Denis Arefev <arefev@swemel.ru>
>>>>> ---
>>>>> v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
>>>>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>>>>>     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 20d7a238d675..6c18e6005ae1 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;
>>>>> @@ -833,7 +833,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);
>>>>>     	}
>>>>
>>>> --
>>>> Mathieu Desnoyers
>>>> EfficiOS Inc.
>>>> https://www.efficios.com
>>>
>>> -
>>> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
>>> Registration No: 1397386 (Wales)
>>
>> -- 
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com
>>

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 09:34:45AM -0400, Mathieu Desnoyers wrote:
> On 9/5/23 09:26, Paul E. McKenney wrote:
> > On Tue, Sep 05, 2023 at 08:26:51AM -0400, Mathieu Desnoyers wrote:
> > > On 9/5/23 05:31, David Laight wrote:
> > > > From: Mathieu Desnoyers
> > > > > Sent: 04 September 2023 11:24
> > > > > 
> > > > > On 9/4/23 05:42, Denis Arefev wrote:
> > > > > > The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> > > > > > is subject to overflow due to a failure to cast operands to a larger
> > > > > > data type before performing arithmetic
> > > > > 
> > > > > The patch title should identify more precisely its context, e.g.:
> > > > > 
> > > > > "srcu: Fix srcu_struct node grpmask overflow on 64-bit systems"
> > > > > 
> > > > > Also, as I stated in my reply to the previous version, the patch commit
> > > > > message should describe the impact of the bug it fixes.
> > > > 
> > > > And is the analysis complete?
> > > > Is 1UL right for 32bit archs??
> > > > Is 64 bits even enough??
> > > 
> > > I understand from include/linux/rcu_node_tree.h and kernel/rcu/Kconfig
> > > RCU_FANOUT and RCU_FANOUT_LEAF ranges that a 32-bit integer is sufficient to
> > > hold the mask on 32-bit architectures, and a 64-bit integer is enough on
> > > 64-bit architectures given the current implementation.
> > > 
> > > At least this appears to be the intent. I did not do a thorough analysis of
> > > the various parameter limits.
> > 
> > Mathieu has it right.
> > 
> > 32-bit kernels are unaffected by this bug.
> > 
> > RCU_FANOUT_LEAF defaults to 16, which means that a 64-bit kernel would
> > need more than 32 leaf rcu_node structures for the parent rcu_node
> > structure to need more than 32 bit to track its children.  This means
> > that more than 32*16=512 CPUs are required for this bug to affect 64-bit
> > systems.  And there really are systems this big, so I am surprised that
> > this has not shown up long ago.  But it would not be the first time that
> > objective reality surprised me.  ;-)
> 
> So with a 64-bit kernel, RCU_FANOUT_LEAF=16, if we have exactly 32 leaf
> rcu_node structures (exactly 512 CPUs), we end up in the situation where the
> type promotion from signed integer (32-bit) to unsigned long will carry the
> sign, and thus create a mask of 0xffffffff80000000.

If there is someplace that does a shift of 1UL, yes, this would be a
problem.  I don't see one, but I might have missed something.  If all
the shifts are from 1, then the top 33 bits would be always set and
cleared as a unit, as if they were one bit.

> So if this weird mask is indeed an issue we should state that configurations
> _starting from 512 CPUs_ are affected, not just those with more than 512
> CPUs.

That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
only require a 31-bit shift, which should be OK, but 497 would require
a 32-bit shift, which would result in sign extension.  If it turns out
that sign extension is OK, then we should get in trouble at 513 CPUs,
which would result in a 33-bit shift (and is that even defined in C?).

But this can be tested.  Let's try setting RCU_FANOUT_LEAF to 2.  Then we
"only" need 64 (maybe 62) CPUs to trigger the bug.  And I happen to
have access to a system with 80 CPUs.  (Those with smaller systems can
try to trigger this bug by changing the current "1 <<" to (say) "4 <<",
which should trigger it on 16-CPU systems.)

I just fired off an 80-CPU test with CONFIG_RCU_FANOUT_LEAF=2 and will
let you know how it goes.

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> 
> > 
> > 							Thanx, Paul
> > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > > > 
> > > > 	David
> > > > 
> > > > > 
> > > > > Thanks,
> > > > > 
> > > > > Mathieu
> > > > > 
> > > > > 
> > > > > > 
> > > > > > Found by Linux Verification Center (linuxtesting.org) with SVACE.
> > > > > > 
> > > > > > Signed-off-by: Denis Arefev <arefev@swemel.ru>
> > > > > > ---
> > > > > > v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
> > > > > > Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > > > >     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 20d7a238d675..6c18e6005ae1 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;
> > > > > > @@ -833,7 +833,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);
> > > > > >     	}
> > > > > 
> > > > > --
> > > > > Mathieu Desnoyers
> > > > > EfficiOS Inc.
> > > > > https://www.efficios.com
> > > > 
> > > > -
> > > > Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> > > > Registration No: 1397386 (Wales)
> > > 
> > > -- 
> > > Mathieu Desnoyers
> > > EfficiOS Inc.
> > > https://www.efficios.com
> > > 
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
> 

RE: [PATCH v2] The value may overflow

[David Laight]

...
> That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
> only require a 31-bit shift, which should be OK, but 497 would require
> a 32-bit shift, which would result in sign extension.  If it turns out
> that sign extension is OK, then we should get in trouble at 513 CPUs,
> which would result in a 33-bit shift (and is that even defined in C?).

Not quite right :-)

(1 << 31) is int and negative, that gets sign extended before
being converted to 'unsigned long' - so has the top 33 bits set.

(1 << 32) is undefined, the current x86 cpu ignore the high
shift bits so it is (1 << 0).

If the mask is being used to optimise a search the code might
just happen to work!

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [PATCH v2] The value may overflow

[Mathieu Desnoyers]

On 9/5/23 10:15, David Laight wrote:
> ...
>> That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
>> only require a 31-bit shift, which should be OK, but 497 would require
>> a 32-bit shift, which would result in sign extension.  If it turns out
>> that sign extension is OK, then we should get in trouble at 513 CPUs,
>> which would result in a 33-bit shift (and is that even defined in C?).
> 
> Not quite right :-)
> 
> (1 << 31) is int and negative, that gets sign extended before
> being converted to 'unsigned long' - so has the top 33 bits set.
> 
> (1 << 32) is undefined, the current x86 cpu ignore the high
> shift bits so it is (1 << 0).

Yes, I was about to reply the same thing. A shift of 31 is buggy,
because shifting 1 << 31 raises the sign bit, which sets the top 33
bits when cast to unsigned long. A shift of 1 << 32 is undefined,
with for instance x86 choosing to ignore the top bit.

But in order to have a 1 << 31 shift from this expression:

                 sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);

I *think* we need the group to have 32 cpus or more (indexed within
the group from grplo to grplo + 31 (both inclusive)).

So as soon as we have one group with 32 cpus, the problem should show
up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
group of 32 cpus, for:

   15*31 + 32 = 497 cpus.

AFAIU, this would be the minimum value for smp_processor_id()+1 which
triggers this issue.

Thanks,

Mathieu

> 
> If the mask is being used to optimise a search the code might
> just happen to work!
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 10:34:43AM -0400, Mathieu Desnoyers wrote:
> On 9/5/23 10:15, David Laight wrote:
> > ...
> > > That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
> > > only require a 31-bit shift, which should be OK, but 497 would require
> > > a 32-bit shift, which would result in sign extension.  If it turns out
> > > that sign extension is OK, then we should get in trouble at 513 CPUs,
> > > which would result in a 33-bit shift (and is that even defined in C?).
> > 
> > Not quite right :-)
> > 
> > (1 << 31) is int and negative, that gets sign extended before
> > being converted to 'unsigned long' - so has the top 33 bits set.

Good point, thank you for the correction.

> > (1 << 32) is undefined, the current x86 cpu ignore the high
> > shift bits so it is (1 << 0).

Which would cause it to attempt to invoke SRCU callbacks on the
lowest-numbered CPU associated with that srcu_node structure.

> Yes, I was about to reply the same thing. A shift of 31 is buggy,
> because shifting 1 << 31 raises the sign bit, which sets the top 33
> bits when cast to unsigned long. A shift of 1 << 32 is undefined,
> with for instance x86 choosing to ignore the top bit.
> 
> But in order to have a 1 << 31 shift from this expression:
> 
>                 sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> 
> I *think* we need the group to have 32 cpus or more (indexed within
> the group from grplo to grplo + 31 (both inclusive)).
> 
> So as soon as we have one group with 32 cpus, the problem should show
> up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
> group of 32 cpus, for:
> 
>   15*31 + 32 = 497 cpus.
> 
> AFAIU, this would be the minimum value for smp_processor_id()+1 which
> triggers this issue.

By default, there are 16 CPUs per leaf srcu_node structure.  Each leaf
srcu_node structure takes up one bit in the parent srcu_node structures'
srcu_data_have_cbs[] array.  Up to 30 bits is OK, 31 bits is questionable,
and 32 bits and larger erroneous.

This is the situation as I see it (assuming dense CPU numbering):

	# Leaf srcu_node		Largest
	structures	#CPUs		CPU #		Status

	0-30		0-480		479		Good
	31		481-496		495		Questionable
	32-		497-		496+		Bad.

Tree SRCU differs from Tree RCU in its operation, so this bug should
not hold up SRCU grace periods.  It might instead cause SRCU callbacks
to be ignored (which would admittedly look quite similar to the user).

My attempts to cheat the numbering system ran up against the limited
height of the srcu_node tree.

But there is still the question of why this has not been seen in the
wild, given that there really are systems with more than 479 CPUs
out there.  One possibility is the call to srcu_schedule_cbs_sdp()
from srcu_funnel_gp_start().  But it does not seem likely that this
would happen all that often, as it requires back-to-back grace periods
and then some.

Maybe people with large systems boot with srcutree.convert_to_big=0?

Adding Laurent for his thoughts.

Aha!

Here is what makes it work, given David's description of 1<<32:

static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
				  unsigned long mask, unsigned long delay)
{
	int cpu;

	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
		if (!(mask & (1 << (cpu - snp->grplo))))
			continue;
		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
	}
}

As long as at least one bit is set in the result of 1<<N, and as long
as the compiler always does the same thing for a given N, then this loop
will make the right thing happen.

But even that is not relied upon, because the calling code looks like
this:

			spin_lock_irq_rcu_node(snp);
			cbs = false;
			last_lvl = snp >= sup->level[rcu_num_lvls - 1];
			if (last_lvl)
				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
			snp->srcu_have_cbs[idx] = gpseq;
			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
			sgsne = snp->srcu_gp_seq_needed_exp;
			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
			if (ss_state < SRCU_SIZE_BIG)
				mask = ~0;
			else
				mask = snp->srcu_data_have_cbs[idx];
			snp->srcu_data_have_cbs[idx] = 0;
			spin_unlock_irq_rcu_node(snp);
			if (cbs)
				srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);

So that last_lvl check means that the srcu_schedule_cbs_snp() function
is invoked only for leaf srcu_node structures.  Which by default limit
the shift to 16.

So this bug appears to have no effect for default RCU setups, even on very
large 64-bit systems, which is consistent with field experience.  Even if
this is the case, it still should be fixed, to avoid confusion if nothing
else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
Which actually happened the other day due to someone trusting ChatGPT's
opinion about RCU Kconfig options...

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> > 
> > If the mask is being used to optimise a search the code might
> > just happen to work!
> > 
> > 	David
> > 
> > -
> > Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> > Registration No: 1397386 (Wales)
> > 
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
> 

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 09:40:51AM -0700, Paul E. McKenney wrote:
> On Tue, Sep 05, 2023 at 10:34:43AM -0400, Mathieu Desnoyers wrote:
> > On 9/5/23 10:15, David Laight wrote:
> > > ...
> > > > That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
> > > > only require a 31-bit shift, which should be OK, but 497 would require
> > > > a 32-bit shift, which would result in sign extension.  If it turns out
> > > > that sign extension is OK, then we should get in trouble at 513 CPUs,
> > > > which would result in a 33-bit shift (and is that even defined in C?).
> > > 
> > > Not quite right :-)
> > > 
> > > (1 << 31) is int and negative, that gets sign extended before
> > > being converted to 'unsigned long' - so has the top 33 bits set.
> 
> Good point, thank you for the correction.
> 
> > > (1 << 32) is undefined, the current x86 cpu ignore the high
> > > shift bits so it is (1 << 0).
> 
> Which would cause it to attempt to invoke SRCU callbacks on the
> lowest-numbered CPU associated with that srcu_node structure.
> 
> > Yes, I was about to reply the same thing. A shift of 31 is buggy,
> > because shifting 1 << 31 raises the sign bit, which sets the top 33
> > bits when cast to unsigned long. A shift of 1 << 32 is undefined,
> > with for instance x86 choosing to ignore the top bit.
> > 
> > But in order to have a 1 << 31 shift from this expression:
> > 
> >                 sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> > 
> > I *think* we need the group to have 32 cpus or more (indexed within
> > the group from grplo to grplo + 31 (both inclusive)).
> > 
> > So as soon as we have one group with 32 cpus, the problem should show
> > up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
> > group of 32 cpus, for:
> > 
> >   15*31 + 32 = 497 cpus.
> > 
> > AFAIU, this would be the minimum value for smp_processor_id()+1 which
> > triggers this issue.
> 
> By default, there are 16 CPUs per leaf srcu_node structure.  Each leaf
> srcu_node structure takes up one bit in the parent srcu_node structures'
> srcu_data_have_cbs[] array.  Up to 30 bits is OK, 31 bits is questionable,
> and 32 bits and larger erroneous.
> 
> This is the situation as I see it (assuming dense CPU numbering):
> 
> 	# Leaf srcu_node		Largest
> 	structures	#CPUs		CPU #		Status
> 
> 	0-30		0-480		479		Good
> 	31		481-496		495		Questionable
> 	32-		497-		496+		Bad.
> 
> Tree SRCU differs from Tree RCU in its operation, so this bug should
> not hold up SRCU grace periods.  It might instead cause SRCU callbacks
> to be ignored (which would admittedly look quite similar to the user).
> 
> My attempts to cheat the numbering system ran up against the limited
> height of the srcu_node tree.
> 
> But there is still the question of why this has not been seen in the
> wild, given that there really are systems with more than 479 CPUs
> out there.  One possibility is the call to srcu_schedule_cbs_sdp()
> from srcu_funnel_gp_start().  But it does not seem likely that this
> would happen all that often, as it requires back-to-back grace periods
> and then some.
> 
> Maybe people with large systems boot with srcutree.convert_to_big=0?
> 
> Adding Laurent for his thoughts.
> 
> Aha!
> 
> Here is what makes it work, given David's description of 1<<32:
> 
> static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
> 				  unsigned long mask, unsigned long delay)
> {
> 	int cpu;
> 
> 	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> 		if (!(mask & (1 << (cpu - snp->grplo))))
> 			continue;
> 		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
> 	}
> }
> 
> As long as at least one bit is set in the result of 1<<N, and as long
> as the compiler always does the same thing for a given N, then this loop
> will make the right thing happen.
> 
> But even that is not relied upon, because the calling code looks like
> this:
> 
> 			spin_lock_irq_rcu_node(snp);
> 			cbs = false;
> 			last_lvl = snp >= sup->level[rcu_num_lvls - 1];
> 			if (last_lvl)
> 				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> 			snp->srcu_have_cbs[idx] = gpseq;
> 			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> 			sgsne = snp->srcu_gp_seq_needed_exp;
> 			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> 				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> 			if (ss_state < SRCU_SIZE_BIG)
> 				mask = ~0;
> 			else
> 				mask = snp->srcu_data_have_cbs[idx];
> 			snp->srcu_data_have_cbs[idx] = 0;
> 			spin_unlock_irq_rcu_node(snp);
> 			if (cbs)
> 				srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
> 
> So that last_lvl check means that the srcu_schedule_cbs_snp() function
> is invoked only for leaf srcu_node structures.  Which by default limit
> the shift to 16.
> 
> So this bug appears to have no effect for default RCU setups, even on very
> large 64-bit systems, which is consistent with field experience.  Even if
> this is the case, it still should be fixed, to avoid confusion if nothing
> else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
> Which actually happened the other day due to someone trusting ChatGPT's
> opinion about RCU Kconfig options...

And I therefore queued Denis's v3 patch with an edited commit log.
Of course, if anyone sees some other way that the bug could manifest
other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
than 30 on a system with at least 31 CPUs, please let me know so that
I can adjust.

							Thanx, Paul

------------------------------------------------------------------------

commit ed083b0e22f1396dee3599896249a3f218845298
Author: Denis Arefev <arefev@swemel.ru>
Date:   Mon Sep 4 15:21:14 2023 +0300

    Fix srcu_struct node grpmask overflow on 64-bit systems
    
    The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
    is subject to overflow due to a failure to cast operands to a larger
    data type before performing arithmetic.
    
    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 31 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 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>
    Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
    Cc: David Laight <David.Laight@aculab.com>
    Signed-off-by: Paul E. McKenney <paulmck@kernel.org>

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

Re: [PATCH v2] The value may overflow

[Mathieu Desnoyers]

On 9/5/23 15:27, Paul E. McKenney wrote:
> On Tue, Sep 05, 2023 at 09:40:51AM -0700, Paul E. McKenney wrote:
>> On Tue, Sep 05, 2023 at 10:34:43AM -0400, Mathieu Desnoyers wrote:
>>> On 9/5/23 10:15, David Laight wrote:
>>>> ...
>>>>> That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
>>>>> only require a 31-bit shift, which should be OK, but 497 would require
>>>>> a 32-bit shift, which would result in sign extension.  If it turns out
>>>>> that sign extension is OK, then we should get in trouble at 513 CPUs,
>>>>> which would result in a 33-bit shift (and is that even defined in C?).
>>>>
>>>> Not quite right :-)
>>>>
>>>> (1 << 31) is int and negative, that gets sign extended before
>>>> being converted to 'unsigned long' - so has the top 33 bits set.
>>
>> Good point, thank you for the correction.
>>
>>>> (1 << 32) is undefined, the current x86 cpu ignore the high
>>>> shift bits so it is (1 << 0).
>>
>> Which would cause it to attempt to invoke SRCU callbacks on the
>> lowest-numbered CPU associated with that srcu_node structure.
>>
>>> Yes, I was about to reply the same thing. A shift of 31 is buggy,
>>> because shifting 1 << 31 raises the sign bit, which sets the top 33
>>> bits when cast to unsigned long. A shift of 1 << 32 is undefined,
>>> with for instance x86 choosing to ignore the top bit.
>>>
>>> But in order to have a 1 << 31 shift from this expression:
>>>
>>>                  sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
>>>
>>> I *think* we need the group to have 32 cpus or more (indexed within
>>> the group from grplo to grplo + 31 (both inclusive)).
>>>
>>> So as soon as we have one group with 32 cpus, the problem should show
>>> up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
>>> group of 32 cpus, for:
>>>
>>>    15*31 + 32 = 497 cpus.
>>>
>>> AFAIU, this would be the minimum value for smp_processor_id()+1 which
>>> triggers this issue.
>>
>> By default, there are 16 CPUs per leaf srcu_node structure.  Each leaf
>> srcu_node structure takes up one bit in the parent srcu_node structures'
>> srcu_data_have_cbs[] array.  Up to 30 bits is OK, 31 bits is questionable,
>> and 32 bits and larger erroneous.
>>
>> This is the situation as I see it (assuming dense CPU numbering):
>>
>> 	# Leaf srcu_node		Largest
>> 	structures	#CPUs		CPU #		Status
>>
>> 	0-30		0-480		479		Good
>> 	31		481-496		495		Questionable
>> 	32-		497-		496+		Bad.
>>
>> Tree SRCU differs from Tree RCU in its operation, so this bug should
>> not hold up SRCU grace periods.  It might instead cause SRCU callbacks
>> to be ignored (which would admittedly look quite similar to the user).
>>
>> My attempts to cheat the numbering system ran up against the limited
>> height of the srcu_node tree.
>>
>> But there is still the question of why this has not been seen in the
>> wild, given that there really are systems with more than 479 CPUs
>> out there.  One possibility is the call to srcu_schedule_cbs_sdp()
>> from srcu_funnel_gp_start().  But it does not seem likely that this
>> would happen all that often, as it requires back-to-back grace periods
>> and then some.
>>
>> Maybe people with large systems boot with srcutree.convert_to_big=0?
>>
>> Adding Laurent for his thoughts.
>>
>> Aha!
>>
>> Here is what makes it work, given David's description of 1<<32:
>>
>> static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
>> 				  unsigned long mask, unsigned long delay)
>> {
>> 	int cpu;
>>
>> 	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
>> 		if (!(mask & (1 << (cpu - snp->grplo))))
>> 			continue;
>> 		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
>> 	}
>> }
>>
>> As long as at least one bit is set in the result of 1<<N, and as long
>> as the compiler always does the same thing for a given N, then this loop
>> will make the right thing happen.
>>
>> But even that is not relied upon, because the calling code looks like
>> this:
>>
>> 			spin_lock_irq_rcu_node(snp);
>> 			cbs = false;
>> 			last_lvl = snp >= sup->level[rcu_num_lvls - 1];
>> 			if (last_lvl)
>> 				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
>> 			snp->srcu_have_cbs[idx] = gpseq;
>> 			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
>> 			sgsne = snp->srcu_gp_seq_needed_exp;
>> 			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
>> 				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
>> 			if (ss_state < SRCU_SIZE_BIG)
>> 				mask = ~0;
>> 			else
>> 				mask = snp->srcu_data_have_cbs[idx];
>> 			snp->srcu_data_have_cbs[idx] = 0;
>> 			spin_unlock_irq_rcu_node(snp);
>> 			if (cbs)
>> 				srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
>>
>> So that last_lvl check means that the srcu_schedule_cbs_snp() function
>> is invoked only for leaf srcu_node structures.  Which by default limit
>> the shift to 16.
>>
>> So this bug appears to have no effect for default RCU setups, even on very
>> large 64-bit systems, which is consistent with field experience.  Even if
>> this is the case, it still should be fixed, to avoid confusion if nothing
>> else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
>> Which actually happened the other day due to someone trusting ChatGPT's
>> opinion about RCU Kconfig options...
> 
> And I therefore queued Denis's v3 patch with an edited commit log.
> Of course, if anyone sees some other way that the bug could manifest
> other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
> than 30 on a system with at least 31 CPUs, please let me know so that
> I can adjust.
> 
> 							Thanx, Paul
> 
> ------------------------------------------------------------------------
> 
> commit ed083b0e22f1396dee3599896249a3f218845298
> Author: Denis Arefev <arefev@swemel.ru>
> Date:   Mon Sep 4 15:21:14 2023 +0300
> 
>      Fix srcu_struct node grpmask overflow on 64-bit systems
>      
>      The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)

AFAIU, the overflow resides in the "bitwise expression" and not
the arithmetic expression.

Other than this, please add my

Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>


>      is subject to overflow due to a failure to cast operands to a larger
>      data type before performing arithmetic.
>      
>      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 31 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 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>
>      Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>      Cc: David Laight <David.Laight@aculab.com>
>      Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> 
> 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);
>   	}

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 03:36:40PM -0400, Mathieu Desnoyers wrote:
> On 9/5/23 15:27, Paul E. McKenney wrote:
> > On Tue, Sep 05, 2023 at 09:40:51AM -0700, Paul E. McKenney wrote:
> > > On Tue, Sep 05, 2023 at 10:34:43AM -0400, Mathieu Desnoyers wrote:
> > > > On 9/5/23 10:15, David Laight wrote:
> > > > > ...
> > > > > > That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
> > > > > > only require a 31-bit shift, which should be OK, but 497 would require
> > > > > > a 32-bit shift, which would result in sign extension.  If it turns out
> > > > > > that sign extension is OK, then we should get in trouble at 513 CPUs,
> > > > > > which would result in a 33-bit shift (and is that even defined in C?).
> > > > > 
> > > > > Not quite right :-)
> > > > > 
> > > > > (1 << 31) is int and negative, that gets sign extended before
> > > > > being converted to 'unsigned long' - so has the top 33 bits set.
> > > 
> > > Good point, thank you for the correction.
> > > 
> > > > > (1 << 32) is undefined, the current x86 cpu ignore the high
> > > > > shift bits so it is (1 << 0).
> > > 
> > > Which would cause it to attempt to invoke SRCU callbacks on the
> > > lowest-numbered CPU associated with that srcu_node structure.
> > > 
> > > > Yes, I was about to reply the same thing. A shift of 31 is buggy,
> > > > because shifting 1 << 31 raises the sign bit, which sets the top 33
> > > > bits when cast to unsigned long. A shift of 1 << 32 is undefined,
> > > > with for instance x86 choosing to ignore the top bit.
> > > > 
> > > > But in order to have a 1 << 31 shift from this expression:
> > > > 
> > > >                  sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> > > > 
> > > > I *think* we need the group to have 32 cpus or more (indexed within
> > > > the group from grplo to grplo + 31 (both inclusive)).
> > > > 
> > > > So as soon as we have one group with 32 cpus, the problem should show
> > > > up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
> > > > group of 32 cpus, for:
> > > > 
> > > >    15*31 + 32 = 497 cpus.
> > > > 
> > > > AFAIU, this would be the minimum value for smp_processor_id()+1 which
> > > > triggers this issue.
> > > 
> > > By default, there are 16 CPUs per leaf srcu_node structure.  Each leaf
> > > srcu_node structure takes up one bit in the parent srcu_node structures'
> > > srcu_data_have_cbs[] array.  Up to 30 bits is OK, 31 bits is questionable,
> > > and 32 bits and larger erroneous.
> > > 
> > > This is the situation as I see it (assuming dense CPU numbering):
> > > 
> > > 	# Leaf srcu_node		Largest
> > > 	structures	#CPUs		CPU #		Status
> > > 
> > > 	0-30		0-480		479		Good
> > > 	31		481-496		495		Questionable
> > > 	32-		497-		496+		Bad.
> > > 
> > > Tree SRCU differs from Tree RCU in its operation, so this bug should
> > > not hold up SRCU grace periods.  It might instead cause SRCU callbacks
> > > to be ignored (which would admittedly look quite similar to the user).
> > > 
> > > My attempts to cheat the numbering system ran up against the limited
> > > height of the srcu_node tree.
> > > 
> > > But there is still the question of why this has not been seen in the
> > > wild, given that there really are systems with more than 479 CPUs
> > > out there.  One possibility is the call to srcu_schedule_cbs_sdp()
> > > from srcu_funnel_gp_start().  But it does not seem likely that this
> > > would happen all that often, as it requires back-to-back grace periods
> > > and then some.
> > > 
> > > Maybe people with large systems boot with srcutree.convert_to_big=0?
> > > 
> > > Adding Laurent for his thoughts.
> > > 
> > > Aha!
> > > 
> > > Here is what makes it work, given David's description of 1<<32:
> > > 
> > > static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
> > > 				  unsigned long mask, unsigned long delay)
> > > {
> > > 	int cpu;
> > > 
> > > 	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> > > 		if (!(mask & (1 << (cpu - snp->grplo))))
> > > 			continue;
> > > 		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
> > > 	}
> > > }
> > > 
> > > As long as at least one bit is set in the result of 1<<N, and as long
> > > as the compiler always does the same thing for a given N, then this loop
> > > will make the right thing happen.
> > > 
> > > But even that is not relied upon, because the calling code looks like
> > > this:
> > > 
> > > 			spin_lock_irq_rcu_node(snp);
> > > 			cbs = false;
> > > 			last_lvl = snp >= sup->level[rcu_num_lvls - 1];
> > > 			if (last_lvl)
> > > 				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > > 			snp->srcu_have_cbs[idx] = gpseq;
> > > 			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> > > 			sgsne = snp->srcu_gp_seq_needed_exp;
> > > 			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> > > 				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > > 			if (ss_state < SRCU_SIZE_BIG)
> > > 				mask = ~0;
> > > 			else
> > > 				mask = snp->srcu_data_have_cbs[idx];
> > > 			snp->srcu_data_have_cbs[idx] = 0;
> > > 			spin_unlock_irq_rcu_node(snp);
> > > 			if (cbs)
> > > 				srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
> > > 
> > > So that last_lvl check means that the srcu_schedule_cbs_snp() function
> > > is invoked only for leaf srcu_node structures.  Which by default limit
> > > the shift to 16.
> > > 
> > > So this bug appears to have no effect for default RCU setups, even on very
> > > large 64-bit systems, which is consistent with field experience.  Even if
> > > this is the case, it still should be fixed, to avoid confusion if nothing
> > > else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
> > > Which actually happened the other day due to someone trusting ChatGPT's
> > > opinion about RCU Kconfig options...
> > 
> > And I therefore queued Denis's v3 patch with an edited commit log.
> > Of course, if anyone sees some other way that the bug could manifest
> > other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
> > than 30 on a system with at least 31 CPUs, please let me know so that
> > I can adjust.
> > 
> > 							Thanx, Paul
> > 
> > ------------------------------------------------------------------------
> > 
> > commit ed083b0e22f1396dee3599896249a3f218845298
> > Author: Denis Arefev <arefev@swemel.ru>
> > Date:   Mon Sep 4 15:21:14 2023 +0300
> > 
> >      Fix srcu_struct node grpmask overflow on 64-bit systems
> >      The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> 
> AFAIU, the overflow resides in the "bitwise expression" and not
> the arithmetic expression.

Rather than quibble about exactly what constitutes arithmetic, I
updated the first paragraph and added your Reviewed-by as shown
below.  ;-)

> Other than this, please add my
> 
> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Thank you all!!!

------------------------------------------------------------------------

commit 50477ff756ab99402b1523b7c6be8b5d790d05e7
Author: Denis Arefev <arefev@swemel.ru>
Date:   Mon Sep 4 15:21:14 2023 +0300

    Fix srcu_struct node grpmask overflow on 64-bit systems
    
    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 31 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 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>
    Cc: David Laight <David.Laight@aculab.com>
    Signed-off-by: Paul E. McKenney <paulmck@kernel.org>

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

Re: [PATCH v2] The value may overflow

[Joel Fernandes]

On Tue, Sep 5, 2023 at 4:13 PM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Tue, Sep 05, 2023 at 03:36:40PM -0400, Mathieu Desnoyers wrote:
> > On 9/5/23 15:27, Paul E. McKenney wrote:
> > > On Tue, Sep 05, 2023 at 09:40:51AM -0700, Paul E. McKenney wrote:
> > > > On Tue, Sep 05, 2023 at 10:34:43AM -0400, Mathieu Desnoyers wrote:
> > > > > On 9/5/23 10:15, David Laight wrote:
> > > > > > ...
> > > > > > > That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
> > > > > > > only require a 31-bit shift, which should be OK, but 497 would require
> > > > > > > a 32-bit shift, which would result in sign extension.  If it turns out
> > > > > > > that sign extension is OK, then we should get in trouble at 513 CPUs,
> > > > > > > which would result in a 33-bit shift (and is that even defined in C?).
> > > > > >
> > > > > > Not quite right :-)
> > > > > >
> > > > > > (1 << 31) is int and negative, that gets sign extended before
> > > > > > being converted to 'unsigned long' - so has the top 33 bits set.
> > > >
> > > > Good point, thank you for the correction.
> > > >
> > > > > > (1 << 32) is undefined, the current x86 cpu ignore the high
> > > > > > shift bits so it is (1 << 0).
> > > >
> > > > Which would cause it to attempt to invoke SRCU callbacks on the
> > > > lowest-numbered CPU associated with that srcu_node structure.
> > > >
> > > > > Yes, I was about to reply the same thing. A shift of 31 is buggy,
> > > > > because shifting 1 << 31 raises the sign bit, which sets the top 33
> > > > > bits when cast to unsigned long. A shift of 1 << 32 is undefined,
> > > > > with for instance x86 choosing to ignore the top bit.
> > > > >
> > > > > But in order to have a 1 << 31 shift from this expression:
> > > > >
> > > > >                  sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> > > > >
> > > > > I *think* we need the group to have 32 cpus or more (indexed within
> > > > > the group from grplo to grplo + 31 (both inclusive)).
> > > > >
> > > > > So as soon as we have one group with 32 cpus, the problem should show
> > > > > up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
> > > > > group of 32 cpus, for:
> > > > >
> > > > >    15*31 + 32 = 497 cpus.
> > > > >
> > > > > AFAIU, this would be the minimum value for smp_processor_id()+1 which
> > > > > triggers this issue.
> > > >
> > > > By default, there are 16 CPUs per leaf srcu_node structure.  Each leaf
> > > > srcu_node structure takes up one bit in the parent srcu_node structures'
> > > > srcu_data_have_cbs[] array.  Up to 30 bits is OK, 31 bits is questionable,
> > > > and 32 bits and larger erroneous.
> > > >
> > > > This is the situation as I see it (assuming dense CPU numbering):
> > > >
> > > >   # Leaf srcu_node                Largest
> > > >   structures      #CPUs           CPU #           Status
> > > >
> > > >   0-30            0-480           479             Good
> > > >   31              481-496         495             Questionable
> > > >   32-             497-            496+            Bad.
> > > >
> > > > Tree SRCU differs from Tree RCU in its operation, so this bug should
> > > > not hold up SRCU grace periods.  It might instead cause SRCU callbacks
> > > > to be ignored (which would admittedly look quite similar to the user).
> > > >
> > > > My attempts to cheat the numbering system ran up against the limited
> > > > height of the srcu_node tree.
> > > >
> > > > But there is still the question of why this has not been seen in the
> > > > wild, given that there really are systems with more than 479 CPUs
> > > > out there.  One possibility is the call to srcu_schedule_cbs_sdp()
> > > > from srcu_funnel_gp_start().  But it does not seem likely that this
> > > > would happen all that often, as it requires back-to-back grace periods
> > > > and then some.
> > > >
> > > > Maybe people with large systems boot with srcutree.convert_to_big=0?
> > > >
> > > > Adding Laurent for his thoughts.
> > > >
> > > > Aha!
> > > >
> > > > Here is what makes it work, given David's description of 1<<32:
> > > >
> > > > static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
> > > >                             unsigned long mask, unsigned long delay)
> > > > {
> > > >   int cpu;
> > > >
> > > >   for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> > > >           if (!(mask & (1 << (cpu - snp->grplo))))
> > > >                   continue;
> > > >           srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
> > > >   }
> > > > }
> > > >
> > > > As long as at least one bit is set in the result of 1<<N, and as long
> > > > as the compiler always does the same thing for a given N, then this loop
> > > > will make the right thing happen.
> > > >
> > > > But even that is not relied upon, because the calling code looks like
> > > > this:
> > > >
> > > >                   spin_lock_irq_rcu_node(snp);
> > > >                   cbs = false;
> > > >                   last_lvl = snp >= sup->level[rcu_num_lvls - 1];
> > > >                   if (last_lvl)
> > > >                           cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > > >                   snp->srcu_have_cbs[idx] = gpseq;
> > > >                   rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> > > >                   sgsne = snp->srcu_gp_seq_needed_exp;
> > > >                   if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> > > >                           WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > > >                   if (ss_state < SRCU_SIZE_BIG)
> > > >                           mask = ~0;
> > > >                   else
> > > >                           mask = snp->srcu_data_have_cbs[idx];
> > > >                   snp->srcu_data_have_cbs[idx] = 0;
> > > >                   spin_unlock_irq_rcu_node(snp);
> > > >                   if (cbs)
> > > >                           srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
> > > >
> > > > So that last_lvl check means that the srcu_schedule_cbs_snp() function
> > > > is invoked only for leaf srcu_node structures.  Which by default limit
> > > > the shift to 16.
> > > >
> > > > So this bug appears to have no effect for default RCU setups, even on very
> > > > large 64-bit systems, which is consistent with field experience.  Even if
> > > > this is the case, it still should be fixed, to avoid confusion if nothing
> > > > else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
> > > > Which actually happened the other day due to someone trusting ChatGPT's
> > > > opinion about RCU Kconfig options...
> > >
> > > And I therefore queued Denis's v3 patch with an edited commit log.
> > > Of course, if anyone sees some other way that the bug could manifest
> > > other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
> > > than 30 on a system with at least 31 CPUs, please let me know so that
> > > I can adjust.
> > >
> > >                                                     Thanx, Paul
> > >
> > > ------------------------------------------------------------------------
> > >
> > > commit ed083b0e22f1396dee3599896249a3f218845298
> > > Author: Denis Arefev <arefev@swemel.ru>
> > > Date:   Mon Sep 4 15:21:14 2023 +0300
> > >
> > >      Fix srcu_struct node grpmask overflow on 64-bit systems
> > >      The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> >
> > AFAIU, the overflow resides in the "bitwise expression" and not
> > the arithmetic expression.
>
> Rather than quibble about exactly what constitutes arithmetic, I
> updated the first paragraph and added your Reviewed-by as shown
> below.  ;-)
>
> > Other than this, please add my
> >
> > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>
> Thank you all!!!
>
> ------------------------------------------------------------------------
>
> commit 50477ff756ab99402b1523b7c6be8b5d790d05e7
> Author: Denis Arefev <arefev@swemel.ru>
> Date:   Mon Sep 4 15:21:14 2023 +0300
>
>     Fix srcu_struct node grpmask overflow on 64-bit systems
>
>     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 31 or greater triggers undefined behavior per the C standard.

Do you mean here "A value of 32 or greater"?

Only N >= 32 throws warning for:
unsigned long foo = (1 << N);

N=31 does undesirable sign extension but no warning.

thanks,

 - Joel

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 04:40:46PM -0400, Joel Fernandes wrote:
> On Tue, Sep 5, 2023 at 4:13 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> >
> > On Tue, Sep 05, 2023 at 03:36:40PM -0400, Mathieu Desnoyers wrote:
> > > On 9/5/23 15:27, Paul E. McKenney wrote:
> > > > On Tue, Sep 05, 2023 at 09:40:51AM -0700, Paul E. McKenney wrote:
> > > > > On Tue, Sep 05, 2023 at 10:34:43AM -0400, Mathieu Desnoyers wrote:
> > > > > > On 9/5/23 10:15, David Laight wrote:
> > > > > > > ...
> > > > > > > > That would instead be more than 512-16=496 CPUs, correct?  496 CPUs would
> > > > > > > > only require a 31-bit shift, which should be OK, but 497 would require
> > > > > > > > a 32-bit shift, which would result in sign extension.  If it turns out
> > > > > > > > that sign extension is OK, then we should get in trouble at 513 CPUs,
> > > > > > > > which would result in a 33-bit shift (and is that even defined in C?).
> > > > > > >
> > > > > > > Not quite right :-)
> > > > > > >
> > > > > > > (1 << 31) is int and negative, that gets sign extended before
> > > > > > > being converted to 'unsigned long' - so has the top 33 bits set.
> > > > >
> > > > > Good point, thank you for the correction.
> > > > >
> > > > > > > (1 << 32) is undefined, the current x86 cpu ignore the high
> > > > > > > shift bits so it is (1 << 0).
> > > > >
> > > > > Which would cause it to attempt to invoke SRCU callbacks on the
> > > > > lowest-numbered CPU associated with that srcu_node structure.
> > > > >
> > > > > > Yes, I was about to reply the same thing. A shift of 31 is buggy,
> > > > > > because shifting 1 << 31 raises the sign bit, which sets the top 33
> > > > > > bits when cast to unsigned long. A shift of 1 << 32 is undefined,
> > > > > > with for instance x86 choosing to ignore the top bit.
> > > > > >
> > > > > > But in order to have a 1 << 31 shift from this expression:
> > > > > >
> > > > > >                  sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> > > > > >
> > > > > > I *think* we need the group to have 32 cpus or more (indexed within
> > > > > > the group from grplo to grplo + 31 (both inclusive)).
> > > > > >
> > > > > > So as soon as we have one group with 32 cpus, the problem should show
> > > > > > up. With FANOUT_LEAF=16, we can have 15 groups of 31 cpus and 1
> > > > > > group of 32 cpus, for:
> > > > > >
> > > > > >    15*31 + 32 = 497 cpus.
> > > > > >
> > > > > > AFAIU, this would be the minimum value for smp_processor_id()+1 which
> > > > > > triggers this issue.
> > > > >
> > > > > By default, there are 16 CPUs per leaf srcu_node structure.  Each leaf
> > > > > srcu_node structure takes up one bit in the parent srcu_node structures'
> > > > > srcu_data_have_cbs[] array.  Up to 30 bits is OK, 31 bits is questionable,
> > > > > and 32 bits and larger erroneous.
> > > > >
> > > > > This is the situation as I see it (assuming dense CPU numbering):
> > > > >
> > > > >   # Leaf srcu_node                Largest
> > > > >   structures      #CPUs           CPU #           Status
> > > > >
> > > > >   0-30            0-480           479             Good
> > > > >   31              481-496         495             Questionable
> > > > >   32-             497-            496+            Bad.
> > > > >
> > > > > Tree SRCU differs from Tree RCU in its operation, so this bug should
> > > > > not hold up SRCU grace periods.  It might instead cause SRCU callbacks
> > > > > to be ignored (which would admittedly look quite similar to the user).
> > > > >
> > > > > My attempts to cheat the numbering system ran up against the limited
> > > > > height of the srcu_node tree.
> > > > >
> > > > > But there is still the question of why this has not been seen in the
> > > > > wild, given that there really are systems with more than 479 CPUs
> > > > > out there.  One possibility is the call to srcu_schedule_cbs_sdp()
> > > > > from srcu_funnel_gp_start().  But it does not seem likely that this
> > > > > would happen all that often, as it requires back-to-back grace periods
> > > > > and then some.
> > > > >
> > > > > Maybe people with large systems boot with srcutree.convert_to_big=0?
> > > > >
> > > > > Adding Laurent for his thoughts.
> > > > >
> > > > > Aha!
> > > > >
> > > > > Here is what makes it work, given David's description of 1<<32:
> > > > >
> > > > > static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
> > > > >                             unsigned long mask, unsigned long delay)
> > > > > {
> > > > >   int cpu;
> > > > >
> > > > >   for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> > > > >           if (!(mask & (1 << (cpu - snp->grplo))))
> > > > >                   continue;
> > > > >           srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
> > > > >   }
> > > > > }
> > > > >
> > > > > As long as at least one bit is set in the result of 1<<N, and as long
> > > > > as the compiler always does the same thing for a given N, then this loop
> > > > > will make the right thing happen.
> > > > >
> > > > > But even that is not relied upon, because the calling code looks like
> > > > > this:
> > > > >
> > > > >                   spin_lock_irq_rcu_node(snp);
> > > > >                   cbs = false;
> > > > >                   last_lvl = snp >= sup->level[rcu_num_lvls - 1];
> > > > >                   if (last_lvl)
> > > > >                           cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > > > >                   snp->srcu_have_cbs[idx] = gpseq;
> > > > >                   rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> > > > >                   sgsne = snp->srcu_gp_seq_needed_exp;
> > > > >                   if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> > > > >                           WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > > > >                   if (ss_state < SRCU_SIZE_BIG)
> > > > >                           mask = ~0;
> > > > >                   else
> > > > >                           mask = snp->srcu_data_have_cbs[idx];
> > > > >                   snp->srcu_data_have_cbs[idx] = 0;
> > > > >                   spin_unlock_irq_rcu_node(snp);
> > > > >                   if (cbs)
> > > > >                           srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
> > > > >
> > > > > So that last_lvl check means that the srcu_schedule_cbs_snp() function
> > > > > is invoked only for leaf srcu_node structures.  Which by default limit
> > > > > the shift to 16.
> > > > >
> > > > > So this bug appears to have no effect for default RCU setups, even on very
> > > > > large 64-bit systems, which is consistent with field experience.  Even if
> > > > > this is the case, it still should be fixed, to avoid confusion if nothing
> > > > > else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
> > > > > Which actually happened the other day due to someone trusting ChatGPT's
> > > > > opinion about RCU Kconfig options...
> > > >
> > > > And I therefore queued Denis's v3 patch with an edited commit log.
> > > > Of course, if anyone sees some other way that the bug could manifest
> > > > other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
> > > > than 30 on a system with at least 31 CPUs, please let me know so that
> > > > I can adjust.
> > > >
> > > >                                                     Thanx, Paul
> > > >
> > > > ------------------------------------------------------------------------
> > > >
> > > > commit ed083b0e22f1396dee3599896249a3f218845298
> > > > Author: Denis Arefev <arefev@swemel.ru>
> > > > Date:   Mon Sep 4 15:21:14 2023 +0300
> > > >
> > > >      Fix srcu_struct node grpmask overflow on 64-bit systems
> > > >      The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> > >
> > > AFAIU, the overflow resides in the "bitwise expression" and not
> > > the arithmetic expression.
> >
> > Rather than quibble about exactly what constitutes arithmetic, I
> > updated the first paragraph and added your Reviewed-by as shown
> > below.  ;-)
> >
> > > Other than this, please add my
> > >
> > > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >
> > Thank you all!!!
> >
> > ------------------------------------------------------------------------
> >
> > commit 50477ff756ab99402b1523b7c6be8b5d790d05e7
> > Author: Denis Arefev <arefev@swemel.ru>
> > Date:   Mon Sep 4 15:21:14 2023 +0300
> >
> >     Fix srcu_struct node grpmask overflow on 64-bit systems
> >
> >     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 31 or greater triggers undefined behavior per the C standard.
> 
> Do you mean here "A value of 32 or greater"?
> 
> Only N >= 32 throws warning for:
> unsigned long foo = (1 << N);
> 
> N=31 does undesirable sign extension but no warning.

Good catch, thank you, and I will update this on my next rebase.

							Thanx, Paul

Re: [PATCH v2] The value may overflow

[Joel Fernandes]

On Tue, Sep 5, 2023 at 4:52 PM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Tue, Sep 05, 2023 at 04:40:46PM -0400, Joel Fernandes wrote:
[...]
> > > > > > So this bug appears to have no effect for default RCU setups, even on very
> > > > > > large 64-bit systems, which is consistent with field experience.  Even if
> > > > > > this is the case, it still should be fixed, to avoid confusion if nothing
> > > > > > else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
> > > > > > Which actually happened the other day due to someone trusting ChatGPT's
> > > > > > opinion about RCU Kconfig options...
> > > > >
> > > > > And I therefore queued Denis's v3 patch with an edited commit log.
> > > > > Of course, if anyone sees some other way that the bug could manifest
> > > > > other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
> > > > > than 30 on a system with at least 31 CPUs, please let me know so that
> > > > > I can adjust.
> > > > >
> > > > >                                                     Thanx, Paul
> > > > >
> > > > > ------------------------------------------------------------------------
> > > > >
> > > > > commit ed083b0e22f1396dee3599896249a3f218845298
> > > > > Author: Denis Arefev <arefev@swemel.ru>
> > > > > Date:   Mon Sep 4 15:21:14 2023 +0300
> > > > >
> > > > >      Fix srcu_struct node grpmask overflow on 64-bit systems
> > > > >      The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> > > >
> > > > AFAIU, the overflow resides in the "bitwise expression" and not
> > > > the arithmetic expression.
> > >
> > > Rather than quibble about exactly what constitutes arithmetic, I
> > > updated the first paragraph and added your Reviewed-by as shown
> > > below.  ;-)
> > >
> > > > Other than this, please add my
> > > >
> > > > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > >
> > > Thank you all!!!
> > >
> > > ------------------------------------------------------------------------
> > >
> > > commit 50477ff756ab99402b1523b7c6be8b5d790d05e7
> > > Author: Denis Arefev <arefev@swemel.ru>
> > > Date:   Mon Sep 4 15:21:14 2023 +0300
> > >
> > >     Fix srcu_struct node grpmask overflow on 64-bit systems
> > >
> > >     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 31 or greater triggers undefined behavior per the C standard.
> >
> > Do you mean here "A value of 32 or greater"?
> >
> > Only N >= 32 throws warning for:
> > unsigned long foo = (1 << N);
> >
> > N=31 does undesirable sign extension but no warning.
>
> Good catch, thank you, and I will update this on my next rebase.

Thanks, and with that the patch looks good to me:
Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>

 - Joel

Re: [PATCH v2] The value may overflow

[Paul E. McKenney]

On Tue, Sep 05, 2023 at 04:56:12PM -0400, Joel Fernandes wrote:
> On Tue, Sep 5, 2023 at 4:52 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> >
> > On Tue, Sep 05, 2023 at 04:40:46PM -0400, Joel Fernandes wrote:
> [...]
> > > > > > > So this bug appears to have no effect for default RCU setups, even on very
> > > > > > > large 64-bit systems, which is consistent with field experience.  Even if
> > > > > > > this is the case, it still should be fixed, to avoid confusion if nothing
> > > > > > > else.  Or just in case someone decides to set CONFIG_RCU_FANOUT_LEAF=32.
> > > > > > > Which actually happened the other day due to someone trusting ChatGPT's
> > > > > > > opinion about RCU Kconfig options...
> > > > > >
> > > > > > And I therefore queued Denis's v3 patch with an edited commit log.
> > > > > > Of course, if anyone sees some other way that the bug could manifest
> > > > > > other than in a 64-bit kernel built with CONFIG_RCU_FANOUT_LEAF greater
> > > > > > than 30 on a system with at least 31 CPUs, please let me know so that
> > > > > > I can adjust.
> > > > > >
> > > > > >                                                     Thanx, Paul
> > > > > >
> > > > > > ------------------------------------------------------------------------
> > > > > >
> > > > > > commit ed083b0e22f1396dee3599896249a3f218845298
> > > > > > Author: Denis Arefev <arefev@swemel.ru>
> > > > > > Date:   Mon Sep 4 15:21:14 2023 +0300
> > > > > >
> > > > > >      Fix srcu_struct node grpmask overflow on 64-bit systems
> > > > > >      The value of an arithmetic expression 1 << (cpu - sdp->mynode->grplo)
> > > > >
> > > > > AFAIU, the overflow resides in the "bitwise expression" and not
> > > > > the arithmetic expression.
> > > >
> > > > Rather than quibble about exactly what constitutes arithmetic, I
> > > > updated the first paragraph and added your Reviewed-by as shown
> > > > below.  ;-)
> > > >
> > > > > Other than this, please add my
> > > > >
> > > > > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > >
> > > > Thank you all!!!
> > > >
> > > > ------------------------------------------------------------------------
> > > >
> > > > commit 50477ff756ab99402b1523b7c6be8b5d790d05e7
> > > > Author: Denis Arefev <arefev@swemel.ru>
> > > > Date:   Mon Sep 4 15:21:14 2023 +0300
> > > >
> > > >     Fix srcu_struct node grpmask overflow on 64-bit systems
> > > >
> > > >     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 31 or greater triggers undefined behavior per the C standard.
> > >
> > > Do you mean here "A value of 32 or greater"?
> > >
> > > Only N >= 32 throws warning for:
> > > unsigned long foo = (1 << N);
> > >
> > > N=31 does undesirable sign extension but no warning.
> >
> > Good catch, thank you, and I will update this on my next rebase.
> 
> Thanks, and with that the patch looks good to me:
> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>

Thank you very much, and I will apply this on the next rebase.

							Thanx, Paul