[PATCH tip/core/rcu 3/3] rcu: Correctly handle non-empty Tiny RCU callback list with none ready

[PATCH tip/core/rcu 3/3] rcu: Correctly handle non-empty Tiny RCU callback list with none ready

[Paul E. McKenney]

From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

If, at the time __rcu_process_callbacks() is invoked,  there are callbacks
in Tiny RCU's callback list, but none of them are ready to be invoked,
the current list-management code will knit the non-ready callbacks out
of the list.  This can result in hangs and possibly worse.  This commit
therefore inserts a check for there being no callbacks that can be
invoked immediately.

This bug is unlikely to occur -- you have to get a new callback between
the time rcu_sched_qs() or rcu_bh_qs() was called, but before we get to
__rcu_process_callbacks().  It was detected by the addition of RCU-bh
testing to rcutorture, which in turn was instigated by Iftekhar Ahmed's
mutation testing.  Although this bug was made much more likely by
915e8a4fe45e (rcu: Remove fastpath from __rcu_process_callbacks()), this
did not cause the bug, but rather made it much more probable.   That
said, it takes more than 40 hours of rcutorture testing, on average,
for this bug to appear, so this fix cannot be considered an emergency.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: <stable@vger.kernel.org>
---
 kernel/rcu/tiny.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/kernel/rcu/tiny.c b/kernel/rcu/tiny.c
index a501b4ab9b1c..591af0cb7b9f 100644
--- a/kernel/rcu/tiny.c
+++ b/kernel/rcu/tiny.c
@@ -137,6 +137,11 @@ static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
 
 	/* Move the ready-to-invoke callbacks to a local list. */
 	local_irq_save(flags);
+	if (rcp->donetail == &rcp->rcucblist) {
+		/* No callbacks ready, so just leave. */
+		local_irq_restore(flags);
+		return;
+	}
 	RCU_TRACE(trace_rcu_batch_start(rcp->name, 0, rcp->qlen, -1));
 	list = rcp->rcucblist;
 	rcp->rcucblist = *rcp->donetail;
-- 
1.8.1.5

Re: [PATCH tip/core/rcu 3/3] rcu: Correctly handle non-empty Tiny RCU callback list with none ready

[josh]

On Tue, May 12, 2015 at 03:49:13PM -0700, Paul E. McKenney wrote:
> From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> 
> If, at the time __rcu_process_callbacks() is invoked,  there are callbacks
> in Tiny RCU's callback list, but none of them are ready to be invoked,
> the current list-management code will knit the non-ready callbacks out
> of the list.  This can result in hangs and possibly worse.  This commit
> therefore inserts a check for there being no callbacks that can be
> invoked immediately.
> 
> This bug is unlikely to occur -- you have to get a new callback between
> the time rcu_sched_qs() or rcu_bh_qs() was called, but before we get to
> __rcu_process_callbacks().  It was detected by the addition of RCU-bh
> testing to rcutorture, which in turn was instigated by Iftekhar Ahmed's
> mutation testing.  Although this bug was made much more likely by
> 915e8a4fe45e (rcu: Remove fastpath from __rcu_process_callbacks()), this
> did not cause the bug, but rather made it much more probable.   That
> said, it takes more than 40 hours of rcutorture testing, on average,
> for this bug to appear, so this fix cannot be considered an emergency.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Cc: <stable@vger.kernel.org>

Ouch, subtle.

Reviewed-by: Josh Triplett <josh@joshtriplett.org>

>  kernel/rcu/tiny.c | 5 +++++
>  1 file changed, 5 insertions(+)
> 
> diff --git a/kernel/rcu/tiny.c b/kernel/rcu/tiny.c
> index a501b4ab9b1c..591af0cb7b9f 100644
> --- a/kernel/rcu/tiny.c
> +++ b/kernel/rcu/tiny.c
> @@ -137,6 +137,11 @@ static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
>  
>  	/* Move the ready-to-invoke callbacks to a local list. */
>  	local_irq_save(flags);
> +	if (rcp->donetail == &rcp->rcucblist) {
> +		/* No callbacks ready, so just leave. */
> +		local_irq_restore(flags);
> +		return;
> +	}
>  	RCU_TRACE(trace_rcu_batch_start(rcp->name, 0, rcp->qlen, -1));
>  	list = rcp->rcucblist;
>  	rcp->rcucblist = *rcp->donetail;
> -- 
> 1.8.1.5
> 

Re: [PATCH tip/core/rcu 3/3] rcu: Correctly handle non-empty Tiny RCU callback list with none ready

[Paul E. McKenney]

On Tue, May 12, 2015 at 05:58:21PM -0700, josh@joshtriplett.org wrote:
> On Tue, May 12, 2015 at 03:49:13PM -0700, Paul E. McKenney wrote:
> > From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > 
> > If, at the time __rcu_process_callbacks() is invoked,  there are callbacks
> > in Tiny RCU's callback list, but none of them are ready to be invoked,
> > the current list-management code will knit the non-ready callbacks out
> > of the list.  This can result in hangs and possibly worse.  This commit
> > therefore inserts a check for there being no callbacks that can be
> > invoked immediately.
> > 
> > This bug is unlikely to occur -- you have to get a new callback between
> > the time rcu_sched_qs() or rcu_bh_qs() was called, but before we get to
> > __rcu_process_callbacks().  It was detected by the addition of RCU-bh
> > testing to rcutorture, which in turn was instigated by Iftekhar Ahmed's
> > mutation testing.  Although this bug was made much more likely by
> > 915e8a4fe45e (rcu: Remove fastpath from __rcu_process_callbacks()), this
> > did not cause the bug, but rather made it much more probable.   That
> > said, it takes more than 40 hours of rcutorture testing, on average,
> > for this bug to appear, so this fix cannot be considered an emergency.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Cc: <stable@vger.kernel.org>
> 
> Ouch, subtle.

Indeed!  A bit of a cautionary tale for those who believe that bugs occur
only in concurrent code.  Of course, they could respond that this bug
was in fact due to a concurrent interrupt handler.  Still, I must confess
that this bug is a bit embarrassing.  ;-)

> Reviewed-by: Josh Triplett <josh@joshtriplett.org>

Thank you, applied!

								Thanx, Paul

> >  kernel/rcu/tiny.c | 5 +++++
> >  1 file changed, 5 insertions(+)
> > 
> > diff --git a/kernel/rcu/tiny.c b/kernel/rcu/tiny.c
> > index a501b4ab9b1c..591af0cb7b9f 100644
> > --- a/kernel/rcu/tiny.c
> > +++ b/kernel/rcu/tiny.c
> > @@ -137,6 +137,11 @@ static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
> >  
> >  	/* Move the ready-to-invoke callbacks to a local list. */
> >  	local_irq_save(flags);
> > +	if (rcp->donetail == &rcp->rcucblist) {
> > +		/* No callbacks ready, so just leave. */
> > +		local_irq_restore(flags);
> > +		return;
> > +	}
> >  	RCU_TRACE(trace_rcu_batch_start(rcp->name, 0, rcp->qlen, -1));
> >  	list = rcp->rcucblist;
> >  	rcp->rcucblist = *rcp->donetail;
> > -- 
> > 1.8.1.5
> > 
>