Message-ID: <2613d958-8e8a-c302-8779-8719a10c82e5@efficios.com>
Date:   Tue, 5 Sep 2023 09:43:04 -0400
From:   Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:     paulmck@...nel.org
Cc:     Denis Arefev <arefev@...mel.ru>,
        Lai Jiangshan <jiangshanlai@...il.com>,
        Josh Triplett <josh@...htriplett.org>,
        Steven Rostedt <rostedt@...dmis.org>, rcu@...r.kernel.org,
        lvc-project@...uxtesting.org, linux-kernel@...r.kernel.org,
        trufanov@...mel.ru, vfh@...mel.ru,
        "stable@...r.kernel.org" <stable@...r.kernel.org>
Subject: Re: [PATCH v3] Fix srcu_struct node grpmask overflow on 64-bit
 systems

On 9/5/23 09:38, Paul E. McKenney wrote:
> On Tue, Sep 05, 2023 at 08:57:53AM -0400, Mathieu Desnoyers wrote:
>> On 9/4/23 09:58, Paul E. McKenney wrote:
>>> On Mon, Sep 04, 2023 at 08:58:48AM -0400, Mathieu Desnoyers wrote:
>>>> On 9/4/23 08:42, Mathieu Desnoyers wrote:
>>>>> On 9/4/23 08:21, 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 maximum result of this subtraction is defined by the RCU_FANOUT
>>>>>> or other srcu level-spread values assigned by rcu_init_levelspread(),
>>>>>> which can indeed cause the signed 32-bit integer literal ("1") to
>>>>>> overflow
>>>>>> when shifted by any value greater than 31.
>>>>>
>>>>> We could expand on this:
>>>>>
>>>>> The maximum result of this subtraction is defined by the RCU_FANOUT
>>>>> or other srcu level-spread values assigned by rcu_init_levelspread(),
>>>>> which can indeed cause the signed 32-bit integer literal ("1") to overflow
>>>>> when shifted by any value greater than 31 on a 64-bit system.
>>>>>
>>>>> Moreover, when the subtraction value is 31, the 1 << 31 expression results
>>>>> in 0xffffffff80000000 when the signed integer is promoted to unsigned long
>>>>> on 64-bit systems due to type promotion rules, which is certainly not the
>>>>> intended result.
>>>
>>> Thank you both!  Could you please also add something to the effect of:
>>> "Given default Kconfig options, this bug affects only systems with more
>>> than 512 CPUs."?
>>
>> Hi Paul,
>>
>> I'm trying to understand this "NR_CPUS > 512 CPUs" default Kconfig lower
>> bound from kernel/rcu/Kconfig and rcu_node_tree.h. Is that on a 32-bit or
>> 64-bit architecture ? Also, I suspect that something like x86-64 MAXSMP (or
>> an explicit NR_CPUS) needs to be selected over a default Kconfig to support
>> that many CPUs.
> 
> 64-bit only.  I believe that 32-bit kernels are unaffected by this bug.
> 
> The trick is that RCU reshapes the rcu_node tree in rcu_init_geometry(),
> which is invoked during early boot from rcu_init().  This reshaping is
> based on nr_cpu_ids.  So if NR_CPUS is (say) 4096, there will be enough
> rcu_node structures allocated at build time to accommodate 4096 CPUs
> (259 of them, 256 leaf nodes, four internal nodes, and one root node),
> but only assuming dense numbering of CPUs.  If rcu_init_geometry() sees
> that nr_cpu_ids is (say) 64, it will use only five of them, that is,
> four leaf nodes and one root node.  The leaf nodes will need to shift
> by at most 16, and the root node by at most 4.
> 
> But the possibility of sparse CPU numbering (perhaps to your point)
> means that the bug can occur in 64-bit kernels booted on systems with
> 512 CPUs or fewer if that system has sparse CPU IDs.  For example,
> there have been systems that disable all but one hardware thread per
> core, but leave places in the CPU numbering for those disabled threads.
> Such a system with four hardware threads per core could have a CPU 516
> (and thus be affected by this bug) with as few as 129 CPUs.
> 
> So a better request would be for something like: "Given default Kconfig
> options, this bug affects only 64-bit systems having at least one CPU
> for which smp_processor_id() returns 512 or greater."
> 
> Does that help, or am I missing your point?

This is a good point, although not the one I was trying to make. See my 
explanation about impact of having exactly 512 wrt signed integer type 
promotion in a separate email. So your last phrasing "returns 512 or 
greater" is better. Previously it appeared that only systems with _more 
than_ 512 cpus were affected, which was off-by-one considering that 
systems with exactly 512 cpus are an issue as well.

Thanks,

Mathieu


> 
> 							Thanx, Paul
> 
>> Thanks,
>>
>> Mathieu
>>
>>
>>>
>>> 							Thanx, Paul
>>>
>>>>>> Found by Linux Verification Center (linuxtesting.org) with SVACE.
>>>>>
>>>>> With the commit message updated with my comment above, please also add:
>>>>>
>>>>> Fixes: c7e88067c1 ("srcu: Exact tracking of srcu_data structures
>>>>> containing callbacks")
>>>>> Cc: <stable@...r.kernel.org> # v4.11
>>>>
>>>> Sorry, the line above should read:
>>>>
>>>> Cc: <stable@...r.kernel.org> # v4.11+
>>>>
>>>> Thanks,
>>>>
>>>> Mathieu
>>>>
>>>>> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
>>>>>
>>>>> Thanks!
>>>>>
>>>>> Mathieu
>>>>>
>>>>>>
>>>>>> Signed-off-by: Denis Arefev <arefev@...mel.ru>
>>>>>> ---
>>>>>> v3: Changed the name of the patch, as suggested by
>>>>>> Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
>>>>>> v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
>>>>>> Mathieu Desnoyers <mathieu.desnoyers@...icios.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
>>>>
>>
>> -- 
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com
>>

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

Powered by blists - more mailing lists