Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1721736 > unrolled thread

[RFC RESEND tip 0/5] lockdep: Support deadlock detection for recursive read locks

Back to article view | Back to linux.kernel

Contents

  [RFC RESEND tip 0/5] lockdep: Support deadlock detection for recursive read locks Boqun Feng <boqun.feng@gmail.com> - 2017-08-28 17:20 +0200
    [RFC RESEND tip 5/5] lockdep: Take read/write status in consideration when generate chainkey Boqun Feng <boqun.feng@gmail.com> - 2017-08-28 17:20 +0200

#1721736 — [RFC RESEND tip 0/5] lockdep: Support deadlock detection for recursive read locks

(Resend because getting weird reject, Sorry)

Hi Ingo and Peter,

As Peter pointed out:

	https://marc.info/?l=linux-kernel&m=150349072023540

The lockdep current has a limit support for recursive read locks, the
deadlock case as follow could not be detected:

	read_lock(A);
				lock(B);
	lock(B);
				write_lock(A);

I got some inspiration from Gautham R Shenoy:

	https://lwn.net/Articles/332801/

, and came up with this series.

The basic idea is:

*	Add recursive read locks into the graph

*	Classify dependencies into R->R, N->R, R->N, N->N, where R
	stands for recursive read lock, N stands for other locks.

*	Extend __bfs() to go through all kinds of dependencies and the
	read/write status could be changed in the traverse(i.e. with
	dependency N(A)->R(B) and N(B)->R(C), BFS could go from A to B
	and then to C).

*	But don't allow use a lock B as a transfer station if B only has
	*->R dependencies to the previous lock and R->* dependencies to
	the next lock. This is because if a BFS traverse has such a B as
	a transfer station, the following exists:

		CPU0		CPU1		CPU2		CPU3
		lock(X);
		lock(Y);   	lock(Y);
				rlock(B);	rlock(B);
						lock(P);   	lock(P);
								lock(Q);
	
	The lock dependency breaks between CPU1 and CPU2, no deadlock.
		
In this way, we can reflect the real dependencies while taking recursive
read locks into considerations.

This is readlly an RFC, as I'm 100% sure I cover all the cases related
to read recursive locks, but I do add two sets of self testcases, and
they did pass ;-)

This series consists of 5 patches:

Patch #1 introduces a new test case to test chain cache behavior on the
recursive read deadlock detection.

Patch #2 introduces more complex cases for recursive read deadlock
detection.

Patch #3 does a little bit clean-up on the return value of __bfs() and
its friends.

Patch #4 adds recursive locks into dependency graph and extends BFS to
allow deadlock detection for recursive read locks.

Patch #5 fixes the problem that lock chains and chainkeys don't treat
read/write locks differently, which could miss the chance to detect a
deadlock because a lock chain cache hit.

I plan to write more tests and play about this in next weeks, just send
out for suggestions and comments.

Reviews and tests are welcome!

Regards,
Boqun

[toc] | [next] | [standalone]

#1721739 — [RFC RESEND tip 5/5] lockdep: Take read/write status in consideration when generate chainkey

Currently, the chainkey of a lock chain is a hash sum of the class_idx
of all the held locks, the read/write status are not taken in to
consideration while generating the chainkey. This could result into a
problem, if we have:

	P1()
	{
		read_lock(B);
		lock(A);
	}

	P2()
	{
		lock(A);
		read_lock(B);
	}

	P3()
	{
		lock(A);
		write_lock(B);
	}

, and P1(), P2(), P3() run one by one, when running P2(), it's detected
such a lock chain A -> B is not a deadlock, then it's added in the chain
cache, and then when running P3(), even if it's a deadlock, we could
miss it because of the hit of chain cache. This could be confirmed by
self testcase "chain cached mixed R-L/L-W ".

To resolve this, we use "hlock_id" to generate the chainkey, the
hlock_id is a tuple (hlock->class_idx, hlock->read), which fits in a u16
type. With this, the chainkeys are different is the lock sequences have
the same locks but different read/write status.

Besides, since we use "hlock_id" to generate chainkeys, the chain_hlocks
now store the "hlock_id"s rather than lock_class indexes.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/locking/lockdep.c | 60 ++++++++++++++++++++++++++++++------------------
 1 file changed, 38 insertions(+), 22 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 245324c59706..c7c430e46b4b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -311,6 +311,21 @@ static struct hlist_head classhash_table[CLASSHASH_SIZE];
 
 static struct hlist_head chainhash_table[CHAINHASH_SIZE];
 
+/*
+ * the id  chain_hlocks
+ */
+static inline u16 hlock_id(struct held_lock *hlock)
+{
+	BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS + 2 > 16);
+
+	return (hlock->class_idx | (hlock->read << MAX_LOCKDEP_KEYS_BITS));
+}
+
+static inline unsigned int chain_hlock_class_idx(u16 hlock_id)
+{
+	return hlock_id & MAX_LOCKDEP_KEYS;
+}
+
 /*
  * The hash key of the lock dependency chains is a hash itself too:
  * it's a hash of all locks taken up to that lock, including that lock.
@@ -2159,7 +2174,10 @@ static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
 
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 {
-	return lock_classes + chain_hlocks[chain->base + i];
+	u16 chain_hlock = chain_hlocks[chain->base + i];
+	unsigned int class_idx = chain_hlock_class_idx(chain_hlock);
+
+	return lock_classes + class_idx - 1;
 }
 
 /*
@@ -2185,12 +2203,12 @@ static inline int get_first_held_lock(struct task_struct *curr,
 /*
  * Returns the next chain_key iteration
  */
-static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
+static u64 print_chain_key_iteration(u16 hlock_id, u64 chain_key)
 {
-	u64 new_chain_key = iterate_chain_key(chain_key, class_idx);
+	u64 new_chain_key = iterate_chain_key(chain_key, hlock_id);
 
-	printk(" class_idx:%d -> chain_key:%016Lx",
-		class_idx,
+	printk(" hlock_id:%d -> chain_key:%016Lx",
+		(unsigned int)hlock_id,
 		(unsigned long long)new_chain_key);
 	return new_chain_key;
 }
@@ -2206,12 +2224,12 @@ print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_ne
 	printk("depth: %u\n", depth + 1);
 	for (i = get_first_held_lock(curr, hlock_next); i < depth; i++) {
 		hlock = curr->held_locks + i;
-		chain_key = print_chain_key_iteration(hlock->class_idx, chain_key);
+		chain_key = print_chain_key_iteration(hlock_id(hlock), chain_key);
 
 		print_lock(hlock);
 	}
 
-	print_chain_key_iteration(hlock_next->class_idx, chain_key);
+	print_chain_key_iteration(hlock_id(hlock_next), chain_key);
 	print_lock(hlock_next);
 }
 
@@ -2219,14 +2237,14 @@ static void print_chain_keys_chain(struct lock_chain *chain)
 {
 	int i;
 	u64 chain_key = 0;
-	int class_id;
+	u16 hlock_id;
 
 	printk("depth: %u\n", chain->depth);
 	for (i = 0; i < chain->depth; i++) {
-		class_id = chain_hlocks[chain->base + i];
-		chain_key = print_chain_key_iteration(class_id + 1, chain_key);
+		hlock_id = chain_hlocks[chain->base + i];
+		chain_key = print_chain_key_iteration(hlock_id, chain_key);
 
-		print_lock_name(lock_classes + class_id);
+		print_lock_name(lock_classes + chain_hlock_class_idx(hlock_id) - 1);
 		printk("\n");
 	}
 }
@@ -2275,7 +2293,7 @@ static int check_no_collision(struct task_struct *curr,
 	}
 
 	for (j = 0; j < chain->depth - 1; j++, i++) {
-		id = curr->held_locks[i].class_idx - 1;
+		id = hlock_id(&curr->held_locks[i]);
 
 		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
 			print_collision(curr, hlock, chain);
@@ -2332,8 +2350,8 @@ static inline int add_chain_cache_classes(unsigned int prev,
 	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
 		chain->base = nr_chain_hlocks;
 		nr_chain_hlocks += chain->depth;
-		chain_hlocks[chain->base] = prev - 1;
-		chain_hlocks[chain->base + 1] = next -1;
+		chain_hlocks[chain->base] = prev;
+		chain_hlocks[chain->base + 1] = next;
 	}
 #ifdef CONFIG_DEBUG_LOCKDEP
 	/*
@@ -2367,7 +2385,6 @@ static inline int add_chain_cache(struct task_struct *curr,
 				  struct held_lock *hlock,
 				  u64 chain_key)
 {
-	struct lock_class *class = hlock_class(hlock);
 	struct hlist_head *hash_head = chainhashentry(chain_key);
 	struct lock_chain *chain;
 	int i, j;
@@ -2406,10 +2423,9 @@ static inline int add_chain_cache(struct task_struct *curr,
 	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
 		chain->base = nr_chain_hlocks;
 		for (j = 0; j < chain->depth - 1; j++, i++) {
-			int lock_id = curr->held_locks[i].class_idx - 1;
-			chain_hlocks[chain->base + j] = lock_id;
+			chain_hlocks[chain->base + j] = hlock_id(&curr->held_locks[i]);
 		}
-		chain_hlocks[chain->base + j] = class - lock_classes;
+		chain_hlocks[chain->base + j] = hlock_id(hlock);
 	}
 
 	if (nr_chain_hlocks < MAX_LOCKDEP_CHAIN_HLOCKS)
@@ -2607,7 +2623,7 @@ static void check_chain_key(struct task_struct *curr)
 		if (prev_hlock && (prev_hlock->irq_context !=
 							hlock->irq_context))
 			chain_key = 0;
-		chain_key = iterate_chain_key(chain_key, hlock->class_idx);
+		chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
 		prev_hlock = hlock;
 	}
 	if (chain_key != curr->curr_chain_key) {
@@ -3575,7 +3591,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		chain_key = 0;
 		chain_head = 1;
 	}
-	chain_key = iterate_chain_key(chain_key, class_idx);
+	chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
 
 	if (nest_lock && !__lock_is_held(nest_lock, -1))
 		return print_lock_nested_lock_not_held(curr, hlock, ip);
@@ -5088,9 +5104,9 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
 	unsigned int xid, pid;
 	u64 chain_key;
 
-	xid = xlock_class(xlock) - lock_classes;
+	xid = xlock_class(xlock) - lock_classes + 1;
 	chain_key = iterate_chain_key((u64)0, xid);
-	pid = xhlock_class(xhlock) - lock_classes;
+	pid = xhlock_class(xhlock) - lock_classes + 1;
 	chain_key = iterate_chain_key(chain_key, pid);
 
 	if (lookup_chain_cache(chain_key))
-- 
2.14.1

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web