[lvc-project] [PATCH v3] Fix srcu_struct node grpmask overflow on 64-bit systems

[Paul E. McKenney]

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?

							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 at vger.kernel.org> # v4.11
> > > 
> > > Sorry, the line above should read:
> > > 
> > > Cc: <stable at vger.kernel.org> # v4.11+
> > > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > > > Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > > 
> > > > Thanks!
> > > > 
> > > > Mathieu
> > > > 
> > > > > 
> > > > > Signed-off-by: Denis Arefev <arefev at swemel.ru>
> > > > > ---
> > > > > v3: Changed the name of the patch, as suggested by
> > > > > Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > > > v2: Added fixes to the srcu_schedule_cbs_snp function as suggested by
> > > > > Mathieu Desnoyers <mathieu.desnoyers at 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
>