Messages in this thread | | | Date | Tue, 5 Sep 2023 09:43:04 -0400 | Subject | Re: [PATCH v3] Fix srcu_struct node grpmask overflow on 64-bit systems | From | Mathieu Desnoyers <> |
| |
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@vger.kernel.org> # v4.11 >>>> >>>> Sorry, the line above should read: >>>> >>>> Cc: <stable@vger.kernel.org> # v4.11+ >>>> >>>> Thanks, >>>> >>>> Mathieu >>>> >>>>> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> >>>>> >>>>> Thanks! >>>>> >>>>> Mathieu >>>>> >>>>>> >>>>>> Signed-off-by: Denis Arefev <arefev@swemel.ru> >>>>>> --- >>>>>> v3: Changed the name of the patch, as suggested by >>>>>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> >>>>>> 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 >>>> >> >> -- >> Mathieu Desnoyers >> EfficiOS Inc. >> https://www.efficios.com >>
-- Mathieu Desnoyers EfficiOS Inc. https://www.efficios.com
| |