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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <f6cc79b13ccf471aa275bee88559b6bd@AcuMS.aculab.com>
Date:   Fri, 13 Oct 2023 12:54:32 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Frederic Weisbecker' <frederic@...nel.org>,
        LKML <linux-kernel@...r.kernel.org>
CC:     Denis Arefev <arefev@...mel.ru>, Boqun Feng <boqun.feng@...il.com>,
        "Joel Fernandes" <joel@...lfernandes.org>,
        Josh Triplett <josh@...htriplett.org>,
        Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
        Neeraj Upadhyay <neeraj.upadhyay@....com>,
        "Paul E . McKenney" <paulmck@...nel.org>,
        "Steven Rostedt" <rostedt@...dmis.org>,
        Uladzislau Rezki <urezki@...il.com>, rcu <rcu@...r.kernel.org>
Subject: RE: [PATCH 09/18] srcu: Fix srcu_struct node grpmask overflow on
 64-bit systems

From: Frederic Weisbecker
> Sent: 13 October 2023 12:59
> 
> The value of a bitwise expression 1 << (cpu - sdp->mynode->grplo)
> is subject to overflow due to a failure to cast operands to a larger
> data type before performing the bitwise operation.
> 
> The maximum result of this subtraction is defined by the RCU_FANOUT_LEAF
> Kconfig option, which on 64-bit systems defaults to 16 (resulting in a
> maximum shift of 15), but which can be set up as high as 64 (resulting
> in a maximum shift of 63).  A value of 31 can result in sign extension,
> resulting in 0xffffffff80000000 instead of the desired 0x80000000.
> A value of 32 or greater triggers undefined behavior per the C standard.
> 
> This bug has not been known to cause issues because almost all kernels
> take the default CONFIG_RCU_FANOUT_LEAF=16.  Furthermore, as long as a
> given compiler gives a deterministic non-zero result for 1<<N for N>=32,
> the code correctly invokes all SRCU callbacks, albeit wasting CPU time
> along the way.
> 
> This commit therefore substitutes the correct 1UL for the buggy 1.
> 
> Found by Linux Verification Center (linuxtesting.org) with SVACE.
> 
> Signed-off-by: Denis Arefev <arefev@...mel.ru>
> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
> Reviewed-by: Joel Fernandes (Google) <joel@...lfernandes.org>
> Cc: David Laight <David.Laight@...lab.com>
> Signed-off-by: Paul E. McKenney <paulmck@...nel.org>
> Signed-off-by: Frederic Weisbecker <frederic@...nel.org>
> ---
>  kernel/rcu/srcutree.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 833a8f848a90..5602042856b1 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -223,7 +223,7 @@ static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags)
>  				snp->grplo = cpu;
>  			snp->grphi = cpu;
>  		}
> -		sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
> +		sdp->grpmask = 1UL << (cpu - sdp->mynode->grplo);
>  	}
>  	smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_WAIT_BARRIER);
>  	return true;
> @@ -835,7 +835,7 @@ static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp
>  	int cpu;
> 
>  	for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
> -		if (!(mask & (1 << (cpu - snp->grplo))))
> +		if (!(mask & (1UL << (cpu - snp->grplo))))
>  			continue;
>  		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
>  	}

That loop is entirely horrid.
The compiler almost certainly has to reload snp->grphi every iteration.
Also it looks as though the bottom bit of mask is checked first.
So how about:
	grphi = snp->grphi;
	for (cpu = snp->grplo; cpu <= grphi; cpu++, mask >>= 1) {
		if (!(mask & 1))
			continue;
		srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
	}

	David		

> --
> 2.34.1

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