linux-kernel - Re: [PATCH] srcu: Ensure snp nodes tree is fully initialized before traversal

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: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date:   Tue, 22 Feb 2022 08:59:00 -0800
From:   "Paul E. McKenney" <paulmck@...nel.org>
To:     Neeraj Upadhyay <quic_neeraju@...cinc.com>
Cc:     josh@...htriplett.org, rostedt@...dmis.org,
        mathieu.desnoyers@...icios.com, jiangshanlai@...il.com,
        joel@...lfernandes.org, rcu@...r.kernel.org,
        linux-kernel@...r.kernel.org, urezki@...il.com,
        frederic@...nel.org, boqun.feng@...il.com
Subject: Re: [PATCH] srcu: Ensure snp nodes tree is fully initialized before
 traversal

On Tue, Feb 22, 2022 at 11:39:01AM +0530, Neeraj Upadhyay wrote:
> For configurations where snp node tree is not initialized at
> init time (SRCU_SIZING_IS_INIT() is false), srcu_funnel_gp_start()
> and srcu_funnel_exp_start() can potential traverse and observe
> the snp nodes' transient (uninitialized) states. This can potentially
> happen, when init_srcu_struct_nodes() initialization of sdp->mynode
> races with srcu_funnel_gp_start() and srcu_funnel_exp_start()
> 
> Consider the case below where srcu_funnel_gp_start() observes
> sdp->mynode to be not NULL and uses an uninitialized sdp->grpmask
> 
>           P1                                  P2
> 
> init_srcu_struct_nodes()           void srcu_funnel_gp_start(...)
> {
> for_each_possible_cpu(cpu) {
>   ...
>   sdp->mynode = &snp_first[...];
>   for (snp = sdp->mynode;...)       struct srcu_node *snp_leaf =
>                                        smp_load_acquire(&sdp->mynode)
>     ...                             if (snp_leaf) {
>                                       for (snp = snp_leaf; ...)
>                                         ...
> 					if (snp == snp_leaf)
>                                          snp->srcu_data_have_cbs[idx] |=
>                                            sdp->grpmask;
>     sdp->grpmask =
>       1 << (cpu - sdp->mynode->grplo);
>   }
> }
> 
> Similarly, init_srcu_struct_nodes() and srcu_funnel_exp_start() can
> race, where srcu_funnel_exp_start() could observe state of snp lock
> before spin_lock_init().
> 
>           P1                                      P2
> 
> init_srcu_struct_nodes()               void srcu_funnel_exp_start(...)
> {
>   srcu_for_each_node_breadth_first(ssp, snp) {      for (; ...) {
>                                                       spin_lock_...(snp, )
> 	spin_lock_init(&ACCESS_PRIVATE(snp, lock));
>     ...
>   }
>   for_each_possible_cpu(cpu) {
>     ...
>     sdp->mynode = &snp_first[...];
> 
> To avoid these issues, ensure that snp node tree initialization is
> complete i.e. after SRCU_SIZE_WAIT_BARRIER srcu_size_state is reached,
> before traversing the tree. Given that srcu_funnel_gp_start() and
> srcu_funnel_exp_start() are called within SRCU read side critical
> sections, this check is safe, in the sense that all callbacks are
> enqueued on CPU0 srcu_cblist until SRCU_SIZE_WAIT_CALL is entered,
> and these read side critical sections (containing srcu_funnel_gp_start()
> and srcu_funnel_exp_start()) need to complete, before SRCU_SIZE_WAIT_CALL
> is reached.
> 
> Signed-off-by: Neeraj Upadhyay <quic_neeraju@...cinc.com>

Good catch, and a hard one to hit!  Thank you for chasing this down!!!

I have queued this for testing and review.  I am beginning to suspect
that the SRCU branch might not be ready for mainline, so I will also redo
the merge to pull it in separately.  This allows deferring the decision
on whether it goes into the upcoming merge window or the next one.

After all, although the size of the srcu_struct can be annoying, random
bugs can be even more annoying.

							Thanx, Paul

> ---
>  kernel/rcu/srcutree.c | 18 ++++++++++++++++--
>  1 file changed, 16 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index e3cb84649b2a..c6ba40370c2c 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -818,9 +818,15 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  	int idx = rcu_seq_ctr(s) % ARRAY_SIZE(sdp->mynode->srcu_have_cbs);
>  	unsigned long sgsne;
>  	struct srcu_node *snp;
> -	struct srcu_node *snp_leaf = smp_load_acquire(&sdp->mynode);
> +	struct srcu_node *snp_leaf;
>  	unsigned long snp_seq;
>  
> +	/* Ensure that snp node tree is fully initialized before traversing it */
> +	if (smp_load_acquire(&ssp->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER)
> +		snp_leaf = NULL;
> +	else
> +		snp_leaf = sdp->mynode;
> +
>  	if (snp_leaf)
>  		/* Each pass through the loop does one level of the srcu_node tree. */
>  		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
> @@ -1008,6 +1014,7 @@ static unsigned long srcu_gp_start_if_needed(struct srcu_struct *ssp,
>  	bool needgp = false;
>  	unsigned long s;
>  	struct srcu_data *sdp;
> +	struct srcu_node *sdp_mynode;
>  
>  	check_init_srcu_struct(ssp);
>  	idx = srcu_read_lock(ssp);
> @@ -1031,10 +1038,17 @@ static unsigned long srcu_gp_start_if_needed(struct srcu_struct *ssp,
>  		needexp = true;
>  	}
>  	spin_unlock_irqrestore_rcu_node(sdp, flags);
> +
> +	/* Ensure that snp node tree is fully initialized before traversing it */
> +	if (smp_load_acquire(&ssp->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER)
> +		sdp_mynode = NULL;
> +	else
> +		sdp_mynode = sdp->mynode;
> +
>  	if (needgp)
>  		srcu_funnel_gp_start(ssp, sdp, s, do_norm);
>  	else if (needexp)
> -		srcu_funnel_exp_start(ssp, smp_load_acquire(&sdp->mynode), s);
> +		srcu_funnel_exp_start(ssp, sdp_mynode, s);
>  	srcu_read_unlock(ssp, idx);
>  	return s;
>  }
> -- 
> 2.17.1
>