linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
To: Boqun Feng <boqun.feng@gmail.com>
Cc: linux-kernel@vger.kernel.org,
	Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@redhat.com>,
	Andrea Parri <parri.andrea@gmail.com>,
	Lai Jiangshan <jiangshanlai@gmail.com>,
	Josh Triplett <josh@joshtriplett.org>,
	Steven Rostedt <rostedt@goodmis.org>,
	Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Subject: Re: [RFC tip/locking/lockdep v6 19/20] rcu: Equip sleepable RCU with lockdep dependency graph checks
Date: Wed, 11 Apr 2018 11:57:30 -0700	[thread overview]
Message-ID: <20180411185730.GU3948@linux.vnet.ibm.com> (raw)
In-Reply-To: <20180411135647.21496-1-boqun.feng@gmail.com>

On Wed, Apr 11, 2018 at 09:56:44PM +0800, Boqun Feng wrote:
> Although all flavors of RCU are annotated correctly with lockdep
> annotations as recursive read locks, the 'check' parameter for their
> calls to lock_acquire() is unset. Which means RCU read locks are not
> added into the lockdep dependency graph. This is fine for all flavors
> except sleepable RCU, because the deadlock scenarios for them are
> simple: calling synchronize_rcu() and its friends inside their read-side
> critical sections. But for sleepable RCU, as there may be multiple
> instances with multiple classes, there are more deadlock cases.
> Considering the following:
> 
> 	TASK 1				TASK 2
> 	=======				========
> 	i = srcu_read_lock(&sa);	i = srcu_read_lock(&sb);
> 	synchronize_srcu(&sb);		synchronize_srcu(&sa);
> 	srcu_read_unlock(&sa);		srcu_read_unlock(&sb);
> 
> Neither TASK 1 or 2 could go out of the read-side critical sections,
> because they are waiting for each other at synchronize_srcu().
> 
> With the new improvement for lockdep, which allows us to detect
> deadlocks for recursive read locks, we can actually detect this. What we
> need to do are simply: a) mark srcu_read_{,un}lock() as 'check'
> lock_acquire() and b) annotate synchronize_srcu() as a empty
> grab-and-drop for a write lock (because synchronize_srcu() will wait for
> previous srcu_read_lock() to release, and won't block the next
> srcu_read_lock(), just like a empty write lock section).
> 
> This patch adds those to allow we check deadlocks related to sleepable
> RCU with lockdep.
> 
> Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

Very cool!

One question though...  Won't this report a false-positive self-deadlock if
srcu_read_lock() is invoked from an interrupt handler?

							Thanx, Paul

> ---
>  include/linux/srcu.h  | 51 +++++++++++++++++++++++++++++++++++++++++++++++++--
>  kernel/rcu/srcutiny.c |  2 ++
>  kernel/rcu/srcutree.c |  2 ++
>  3 files changed, 53 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> index 33c1c698df09..23f397bd192c 100644
> --- a/include/linux/srcu.h
> +++ b/include/linux/srcu.h
> @@ -99,6 +99,49 @@ static inline int srcu_read_lock_held(const struct srcu_struct *sp)
>  	return lock_is_held(&sp->dep_map);
>  }
> 
> +/**
> + * lockdep annotations for srcu_read_{un,}lock, and synchronize_srcu():
> + *
> + * srcu_read_lock() and srcu_read_unlock() are similar to rcu_read_lock() and
> + * rcu_read_unlock(), they are recursive read locks. But we mark them as
> + * "check", they will be added into lockdep dependency graph for deadlock
> + * detection. And we also annotate synchronize_srcu() as a
> + * write_lock()+write_unlock(), because synchronize_srcu() will wait for any
> + * corresponding previous srcu_read_lock() to release, and that acts like a
> + * empty grab-and-drop write lock.
> + *
> + * We do so because multiple sleepable rcu instances may cause deadlock as
> + * follow:
> + *
> + *   Task 1:
> + *     ia = srcu_read_lock(&srcu_A);
> + *     synchronize_srcu(&srcu_B);
> + *     srcu_read_unlock(&srcu_A, ia);
> + *
> + *   Task 2:
> + *     ib = srcu_read_lock(&srcu_B);
> + *     synchronize_srcu(&srcu_A);
> + *     srcu_read_unlock(&srcu_B, ib);
> + *
> + * And we want lockdep to detect this or more complicated deadlock with SRCU
> + * involved.
> + */
> +static inline void srcu_lock_acquire(struct lockdep_map *map)
> +{
> +	lock_map_acquire_read(map);
> +}
> +
> +static inline void srcu_lock_release(struct lockdep_map *map)
> +{
> +	lock_map_release(map);
> +}
> +
> +static inline void srcu_lock_sync(struct lockdep_map *map)
> +{
> +	lock_map_acquire(map);
> +	lock_map_release(map);
> +}
> +
>  #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
> 
>  static inline int srcu_read_lock_held(const struct srcu_struct *sp)
> @@ -106,6 +149,10 @@ static inline int srcu_read_lock_held(const struct srcu_struct *sp)
>  	return 1;
>  }
> 
> +#define srcu_lock_acquire(m)	do { } while (0)
> +#define srcu_lock_release(m)	do { } while (0)
> +#define srcu_lock_sync(m)	do { } while (0)
> +
>  #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
> 
>  /**
> @@ -157,7 +204,7 @@ static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
>  	int retval;
> 
>  	retval = __srcu_read_lock(sp);
> -	rcu_lock_acquire(&(sp)->dep_map);
> +	srcu_lock_acquire(&(sp)->dep_map);
>  	return retval;
>  }
> 
> @@ -171,7 +218,7 @@ static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
>  static inline void srcu_read_unlock(struct srcu_struct *sp, int idx)
>  	__releases(sp)
>  {
> -	rcu_lock_release(&(sp)->dep_map);
> +	srcu_lock_release(&(sp)->dep_map);
>  	__srcu_read_unlock(sp, idx);
>  }
> 
> diff --git a/kernel/rcu/srcutiny.c b/kernel/rcu/srcutiny.c
> index 76ac5f50b2c7..bc89cb48d800 100644
> --- a/kernel/rcu/srcutiny.c
> +++ b/kernel/rcu/srcutiny.c
> @@ -188,6 +188,8 @@ void synchronize_srcu(struct srcu_struct *sp)
>  {
>  	struct rcu_synchronize rs;
> 
> +	srcu_lock_sync(&sp->dep_map);
> +
>  	init_rcu_head_on_stack(&rs.head);
>  	init_completion(&rs.completion);
>  	call_srcu(sp, &rs.head, wakeme_after_rcu);
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index d5cea81378cc..e2628e9275b9 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -997,6 +997,8 @@ EXPORT_SYMBOL_GPL(synchronize_srcu_expedited);
>   */
>  void synchronize_srcu(struct srcu_struct *sp)
>  {
> +	srcu_lock_sync(&sp->dep_map);
> +
>  	if (srcu_might_be_idle(sp) || rcu_gp_is_expedited())
>  		synchronize_srcu_expedited(sp);
>  	else
> -- 
> 2.16.2
> 

  reply	other threads:[~2018-04-11 20:00 UTC|newest]

Thread overview: 28+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-11 13:50 [RFC tip/locking/lockdep v6 00/20] lockdep: Support deadlock detection for recursive read locks Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 01/20] lockdep/Documention: Recursive read lock detection reasoning Boqun Feng
2018-04-15  0:38   ` Randy Dunlap
2018-04-16  6:29     ` Boqun Feng
2018-04-27 13:50   ` Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 02/20] lockdep: Demagic the return value of BFS Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 03/20] lockdep: Make __bfs() visit every dependency until a match Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 04/20] lockdep: Redefine LOCK_*_STATE* bits Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 05/20] lockdep: Reduce the size of lock_list::distance Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 06/20] lockdep: Introduce lock_list::dep Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 07/20] lockdep: Extend __bfs() to work with multiple types of dependencies Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 08/20] lockdep: Make __bfs(.match) return bool Boqun Feng
2018-04-11 13:50 ` [RFC tip/locking/lockdep v6 09/20] lockdep: Support deadlock detection for recursive read locks in check_noncircular() Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 10/20] lockdep: Adjust check_redundant() for recursive read change Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 11/20] lockdep: Fix recursive read lock related safe->unsafe detection Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 12/20] lockdep: Add recursive read locks into dependency graph Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 13/20] lockdep/selftest: Add a R-L/L-W test case specific to chain cache behavior Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 14/20] lockdep: Take read/write status in consideration when generate chainkey Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 15/20] lockdep/selftest: Unleash irq_read_recursion2 and add more Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 16/20] lockdep/selftest: Add more recursive read related test cases Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 17/20] Revert "locking/lockdep/selftests: Fix mixed read-write ABBA tests" Boqun Feng
2018-04-11 13:51 ` [RFC tip/locking/lockdep v6 18/20] MAINTAINERS: Add myself as a LOCKING PRIMITIVES reviewer Boqun Feng
2018-04-11 13:56 ` [RFC tip/locking/lockdep v6 19/20] rcu: Equip sleepable RCU with lockdep dependency graph checks Boqun Feng
2018-04-11 18:57   ` Paul E. McKenney [this message]
2018-04-12  2:12     ` Boqun Feng
2018-04-12  9:12       ` Peter Zijlstra
2018-04-13 13:24         ` Boqun Feng
2018-04-11 13:57 ` [RFC tip/locking/lockdep v6 20/20] lockdep/selftest: Add a test case for SRCU Boqun Feng

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180411185730.GU3948@linux.vnet.ibm.com \
    --to=paulmck@linux.vnet.ibm.com \
    --cc=boqun.feng@gmail.com \
    --cc=jiangshanlai@gmail.com \
    --cc=josh@joshtriplett.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mathieu.desnoyers@efficios.com \
    --cc=mingo@redhat.com \
    --cc=parri.andrea@gmail.com \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --subject='Re: [RFC tip/locking/lockdep v6 19/20] rcu: Equip sleepable RCU with lockdep dependency graph checks' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).