lockdep: Support deadlock detection for recursive read locks

kernel/locking/lockdep.c +30 -0

@@ -1012,6 +1013,33 @@ static inline bool bfs_error(enum bfs_result res)
 	return res < 0;
 }
 
+#define DEP_NN_BIT 0
+#define DEP_RN_BIT 1
+#define DEP_NR_BIT 2
+#define DEP_RR_BIT 3
+
+#define DEP_NN_MASK (1U << (DEP_NN_BIT))
+#define DEP_RN_MASK (1U << (DEP_RN_BIT))
+#define DEP_NR_MASK (1U << (DEP_NR_BIT))
+#define DEP_RR_MASK (1U << (DEP_RR_BIT))
+
+static inline unsigned int __calc_dep_bit(int prev, int next)
+{
+	if (prev == 2 && next != 2)
+		return DEP_RN_BIT;
+	if (prev != 2 && next == 2)
+		return DEP_NR_BIT;
+	if (prev == 2 && next == 2)
+		return DEP_RR_BIT;
+	else
+		return DEP_NN_BIT;
+}
+
+static inline unsigned int calc_dep(int prev, int next)
+{
+	return 1U << __calc_dep_bit(prev, next);
+}
+
 static enum bfs_result __bfs(struct lock_list *source_entry,
 			     void *data,
 			     int (*match)(struct lock_list *entry, void *data),

@@ -1921,6 +1949,16 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		if (entry->class == hlock_class(next)) {
 			if (distance == 1)
 				entry->distance = 1;
+			entry->dep |= calc_dep(prev->read, next->read);
+		}
+	}

Quoted 41 lines · Boqun Feng

kernel/locking/lockdep.c +30 -0

@@ -1012,6 +1013,33 @@ static inline bool bfs_error(enum bfs_result res)
 	return res < 0;
 }
 
+#define DEP_NN_BIT 0
+#define DEP_RN_BIT 1
+#define DEP_NR_BIT 2
+#define DEP_RR_BIT 3
+
+#define DEP_NN_MASK (1U << (DEP_NN_BIT))
+#define DEP_RN_MASK (1U << (DEP_RN_BIT))
+#define DEP_NR_MASK (1U << (DEP_NR_BIT))
+#define DEP_RR_MASK (1U << (DEP_RR_BIT))
+
+static inline unsigned int __calc_dep_bit(int prev, int next)
+{
+	if (prev == 2 && next != 2)
+		return DEP_RN_BIT;
+	if (prev != 2 && next == 2)
+		return DEP_NR_BIT;
+	if (prev == 2 && next == 2)
+		return DEP_RR_BIT;
+	else
+		return DEP_NN_BIT;
+}
+
+static inline unsigned int calc_dep(int prev, int next)
+{
+	return 1U << __calc_dep_bit(prev, next);
+}
+
 static enum bfs_result __bfs(struct lock_list *source_entry,
 			     void *data,
 			     int (*match)(struct lock_list *entry, void *data),

@@ -1921,6 +1949,16 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		if (entry->class == hlock_class(next)) {
 			if (distance == 1)
 				entry->distance = 1;
+			entry->dep |= calc_dep(prev->read, next->read);
+		}
+	}

kernel/locking/lockdep.c check_prev_add(struct task_struct *curr, struct held_lock *prev, · line 1964

Quoted 10 lines

kernel/locking/lockdep.c +7 -0

+
+	/* Also, update the reverse dependency in @next's ->locks_before list */
+	list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) {
+		if (entry->class == hlock_class(prev)) {
+			if (distance == 1)
+				entry->distance = 1;
+			entry->dep |= calc_dep(next->read, prev->read);
 			return 1;
 		}
 	}

I think it all becomes simpler if you use only 2 bits. Such that:

bit0 is the prev R (0) or N (1) value,
bit1 is the next R (0) or N (1) value.

I think this should work because we don't care about the empty set (currently 0000) and all the complexity in patch 5 is because we can have R bits set when there's also N bits. The concequence of that is that we cannot replace ! with ~ (which is what I kept doing).

But with only 2 bits, we only track the strongest relation in the set, which is exactly what we appear to need.

The above then becomes something like:

static inline u8 __calc_dep(struct held_lock *lock)

{
	return lock->read != 2;
}

static inline u8
calc_dep(struct held_lock *prev, struct held_lock *next)

{
	return (__calc_dep(prev) << 0) | (__calc_dep(next) << 1);
}

	entry->dep |= calc_dep(prev, next);

Then the stuff from 5 can be:

static inline bool is_rx(u8 dep)

{
	return !(dep & 1);
}

static inline bool is_xr(u8 dep)

{
	return !(dep & 2);
}

	if (have_xr && is_rx(entry->dep))
		continue;

	entry->have_xr = is_xr(entry->dep);

Or did I mess that up somewhere?

Quoted 58 lines · Peter Zijlstra

Quoted 41 lines · Boqun Feng

kernel/locking/lockdep.c +30 -0

@@ -1012,6 +1013,33 @@ static inline bool bfs_error(enum bfs_result res)
 	return res < 0;
 }
 
+#define DEP_NN_BIT 0
+#define DEP_RN_BIT 1
+#define DEP_NR_BIT 2
+#define DEP_RR_BIT 3
+
+#define DEP_NN_MASK (1U << (DEP_NN_BIT))
+#define DEP_RN_MASK (1U << (DEP_RN_BIT))
+#define DEP_NR_MASK (1U << (DEP_NR_BIT))
+#define DEP_RR_MASK (1U << (DEP_RR_BIT))
+
+static inline unsigned int __calc_dep_bit(int prev, int next)
+{
+	if (prev == 2 && next != 2)
+		return DEP_RN_BIT;
+	if (prev != 2 && next == 2)
+		return DEP_NR_BIT;
+	if (prev == 2 && next == 2)
+		return DEP_RR_BIT;
+	else
+		return DEP_NN_BIT;
+}
+
+static inline unsigned int calc_dep(int prev, int next)
+{
+	return 1U << __calc_dep_bit(prev, next);
+}
+
 static enum bfs_result __bfs(struct lock_list *source_entry,
 			     void *data,
 			     int (*match)(struct lock_list *entry, void *data),

@@ -1921,6 +1949,16 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		if (entry->class == hlock_class(next)) {
 			if (distance == 1)
 				entry->distance = 1;
+			entry->dep |= calc_dep(prev->read, next->read);
+		}
+	}

kernel/locking/lockdep.c check_prev_add(struct task_struct *curr, struct held_lock *prev, · line 1964

Quoted 10 lines

kernel/locking/lockdep.c +7 -0

+
+	/* Also, update the reverse dependency in @next's ->locks_before list */
+	list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) {
+		if (entry->class == hlock_class(prev)) {
+			if (distance == 1)
+				entry->distance = 1;
+			entry->dep |= calc_dep(next->read, prev->read);
 			return 1;
 		}
 	}

I think it all becomes simpler if you use only 2 bits. Such that:

bit0 is the prev R (0) or N (1) value,
bit1 is the next R (0) or N (1) value.

Quoted 8 lines

I think this should work because we don't care about the empty set (currently 0000) and all the complexity in patch 5 is because we can have R bits set when there's also N bits. The concequence of that is that we cannot replace ! with ~ (which is what I kept doing).

But with only 2 bits, we only track the strongest relation in the set, which is exactly what we appear to need.

But if we only have RN and NR, both bits will be set, we can not check whether we have NN or not. Consider we have:

	A -(RR)-> B
	B -(NR)-> C and B -(RN)-> C
	C -(RN)-> A

this is not a deadlock case, but with "two bits" approach, we can not differ this with:

	A -(RR)-> B
	B -(NN)-> C
	C -(RN)-> A

, which is a deadlock.

But maybe "three bits" (NR, RN and NN bits) approach works, that is if ->dep is 0, we indicates this is only RR, and is_rx() becomes:

	static inline bool is_rx(u8 dep)
	{
		return !(dep & (NR_MASK | NN_MASK));
	}

and is_xr() becomes:

	static inline bool is_xr(u8 dep)
	{
		return !(dep & (RN_MASK | NN_MASK));
	}

, with this I think your simplification with have_xr works, thanks!

Quoted 9 lines

	if (have_xr && is_rx(entry->dep))
		continue;

	entry->have_xr = is_xr(entry->dep);

Or did I mess that up somewhere?

Quoted 92 lines · Boqun Feng

Quoted 58 lines · Peter Zijlstra

Quoted 41 lines · Boqun Feng

kernel/locking/lockdep.c +30 -0

@@ -1012,6 +1013,33 @@ static inline bool bfs_error(enum bfs_result res)
 	return res < 0;
 }
 
+#define DEP_NN_BIT 0
+#define DEP_RN_BIT 1
+#define DEP_NR_BIT 2
+#define DEP_RR_BIT 3
+
+#define DEP_NN_MASK (1U << (DEP_NN_BIT))
+#define DEP_RN_MASK (1U << (DEP_RN_BIT))
+#define DEP_NR_MASK (1U << (DEP_NR_BIT))
+#define DEP_RR_MASK (1U << (DEP_RR_BIT))
+
+static inline unsigned int __calc_dep_bit(int prev, int next)
+{
+	if (prev == 2 && next != 2)
+		return DEP_RN_BIT;
+	if (prev != 2 && next == 2)
+		return DEP_NR_BIT;
+	if (prev == 2 && next == 2)
+		return DEP_RR_BIT;
+	else
+		return DEP_NN_BIT;
+}
+
+static inline unsigned int calc_dep(int prev, int next)
+{
+	return 1U << __calc_dep_bit(prev, next);
+}
+
 static enum bfs_result __bfs(struct lock_list *source_entry,
 			     void *data,
 			     int (*match)(struct lock_list *entry, void *data),

@@ -1921,6 +1949,16 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		if (entry->class == hlock_class(next)) {
 			if (distance == 1)
 				entry->distance = 1;
+			entry->dep |= calc_dep(prev->read, next->read);
+		}
+	}

kernel/locking/lockdep.c check_prev_add(struct task_struct *curr, struct held_lock *prev, · line 1964

Quoted 10 lines

kernel/locking/lockdep.c +7 -0

+
+	/* Also, update the reverse dependency in @next's ->locks_before list */
+	list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) {
+		if (entry->class == hlock_class(prev)) {
+			if (distance == 1)
+				entry->distance = 1;
+			entry->dep |= calc_dep(next->read, prev->read);
 			return 1;
 		}
 	}

I think it all becomes simpler if you use only 2 bits. Such that:

bit0 is the prev R (0) or N (1) value,
bit1 is the next R (0) or N (1) value.

Quoted 8 lines

I think this should work because we don't care about the empty set (currently 0000) and all the complexity in patch 5 is because we can have R bits set when there's also N bits. The concequence of that is that we cannot replace ! with ~ (which is what I kept doing).

But with only 2 bits, we only track the strongest relation in the set, which is exactly what we appear to need.

But if we only have RN and NR, both bits will be set, we can not check whether we have NN or not. Consider we have:

	A -(RR)-> B
	B -(NR)-> C and B -(RN)-> C
	C -(RN)-> A

this is not a deadlock case, but with "two bits" approach, we can not differ this with:

	A -(RR)-> B
	B -(NN)-> C
	C -(RN)-> A

, which is a deadlock.

But maybe "three bits" (NR, RN and NN bits) approach works, that is if ->dep is 0, we indicates this is only RR, and is_rx() becomes:

	static inline bool is_rx(u8 dep)
	{
		return !(dep & (NR_MASK | NN_MASK));
	}

Quoted 9 lines

and is_xr() becomes:

	static inline bool is_xr(u8 dep)
	{
		return !(dep & (RN_MASK | NN_MASK));
	}

, with this I think your simplification with have_xr works, thanks!

Ah! I see. Actually your very first approach works, except the definitions of is_rx() and ir_xr() are wrong. In that approach, you define

	static inline bool is_rx(u8 dep)
	{
		return !!(dep & (DEP_RR_MASK | DEP_RN_MASK);
	}

, which means "whether we have a R* dependency?". But in fact, what we need to check is "whether we _only_ have R* dependencies?", if so and have_xr is true, that means we could only have a -(*R)-> A -(R*)-> if we pick the next dependency, and that means we should skip. So my new definition above works, and I think we better name it as only_rx() to avoid confusion? Ditto for is_xr().

I also reorder bit number for each kind of dependency, so that we have a simple __calc_dep_bit(), see the following:

	/*
	 * DEP_*_BIT in lock_list::dep
	 *
	 * For dependency @prev -> @next:
	 *
	 *   RR: both @prev and @next are recursive read locks, i.e. ->read == 2.
	 *   RN: @prev is recursive and @next is non-recursive.
	 *   NR: @prev is a not recursive and @next is recursive.
	 *   NN: both @prev and @next are non-recursive.
	 * 
	 * Note that we define the value of DEP_*_BITs so that:
	 * 	bit0 is prev->read != 2
	 * 	bit1 is next->read != 2
	 */
	#define DEP_RR_BIT 0
	#define DEP_RN_BIT 1
	#define DEP_NR_BIT 2
	#define DEP_NN_BIT 3

	#define DEP_RR_MASK (1U << (DEP_RR_BIT))
	#define DEP_RN_MASK (1U << (DEP_RN_BIT))
	#define DEP_NR_MASK (1U << (DEP_NR_BIT))
	#define DEP_NN_MASK (1U << (DEP_NN_BIT))

	static inline unsigned int
	__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
	{
		return (prev->read != 2) + ((next->read != 2) << 1)
	}

	static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
	{
		return 1U << __calc_dep_bit(prev, next);
	}

(quoted diff) +0 -0

 	static inline bool only_rx(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}
 
 	static inline bool only_xr(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}

Note that we actually don't need DEP_RR_BIT, but I leave it there for implementation simplicity. With this, your check and set below works.

Thoughts?

Regards,
Boqun

Quoted 7 lines

Quoted 7 lines

	if (have_xr && is_rx(entry->dep))
		continue;

	entry->have_xr = is_xr(entry->dep);

Quoted 2 lines

Quoted 2 lines

Or did I mess that up somewhere?

Quoted 46 lines · Boqun Feng

	/*
	 * DEP_*_BIT in lock_list::dep
	 *
	 * For dependency @prev -> @next:
	 *
	 *   RR: both @prev and @next are recursive read locks, i.e. ->read == 2.
	 *   RN: @prev is recursive and @next is non-recursive.
	 *   NR: @prev is a not recursive and @next is recursive.
	 *   NN: both @prev and @next are non-recursive.
	 * 
	 * Note that we define the value of DEP_*_BITs so that:
	 * 	bit0 is prev->read != 2
	 * 	bit1 is next->read != 2
	 */
	#define DEP_RR_BIT 0
	#define DEP_RN_BIT 1
	#define DEP_NR_BIT 2
	#define DEP_NN_BIT 3

	#define DEP_RR_MASK (1U << (DEP_RR_BIT))
	#define DEP_RN_MASK (1U << (DEP_RN_BIT))
	#define DEP_NR_MASK (1U << (DEP_NR_BIT))
	#define DEP_NN_MASK (1U << (DEP_NN_BIT))

	static inline unsigned int
	__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
	{
		return (prev->read != 2) + ((next->read != 2) << 1)
	}

	static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
	{
		return 1U << __calc_dep_bit(prev, next);
	}

(quoted diff) +0 -0

 	static inline bool only_rx(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}
 
 	static inline bool only_xr(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

	if (have_xr && is_rx(entry->dep))
		continue;

	entry->have_xr = is_xr(entry->dep);

Hmm.. I think this part also needs some tweak:

	/* if -> prev is *R, and we only have R* for prev -> this, * skip*/
	if (have_xr && only_rx(entry->dep))
		continue;
	
	/*
	 * we pick a *R for prev -> this only if:
	 *     prev -> this dependencies are all *R 
	 * or
	 *     -> prev is *R, and we don't have NN for prev -> this
	 */
	entry->have_xr = only_xr(entry->dep) || (have_xr && !is_nn(entry->dep));

otherwise, we will wrongly set entry->have_xr to false if have_xr is true and we have RN for prev -> this.

Quoted 68 lines · Boqun Feng

Quoted 46 lines · Boqun Feng

	/*
	 * DEP_*_BIT in lock_list::dep
	 *
	 * For dependency @prev -> @next:
	 *
	 *   RR: both @prev and @next are recursive read locks, i.e. ->read == 2.
	 *   RN: @prev is recursive and @next is non-recursive.
	 *   NR: @prev is a not recursive and @next is recursive.
	 *   NN: both @prev and @next are non-recursive.
	 * 
	 * Note that we define the value of DEP_*_BITs so that:
	 * 	bit0 is prev->read != 2
	 * 	bit1 is next->read != 2
	 */
	#define DEP_RR_BIT 0
	#define DEP_RN_BIT 1
	#define DEP_NR_BIT 2
	#define DEP_NN_BIT 3

	#define DEP_RR_MASK (1U << (DEP_RR_BIT))
	#define DEP_RN_MASK (1U << (DEP_RN_BIT))
	#define DEP_NR_MASK (1U << (DEP_NR_BIT))
	#define DEP_NN_MASK (1U << (DEP_NN_BIT))

	static inline unsigned int
	__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
	{
		return (prev->read != 2) + ((next->read != 2) << 1)
	}

	static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
	{
		return 1U << __calc_dep_bit(prev, next);
	}

(quoted diff) +0 -0

 	static inline bool only_rx(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}
 
 	static inline bool only_xr(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

	if (have_xr && is_rx(entry->dep))
		continue;

	entry->have_xr = is_xr(entry->dep);

Hmm.. I think this part also needs some tweak:

	/* if -> prev is *R, and we only have R* for prev -> this, * skip*/
	if (have_xr && only_rx(entry->dep))
		continue;
	
	/*
	 * we pick a *R for prev -> this only if:
	 *     prev -> this dependencies are all *R 
	 * or
	 *     -> prev is *R, and we don't have NN for prev -> this
	 */
	entry->have_xr = only_xr(entry->dep) || (have_xr && !is_nn(entry->dep));

Quoted 2 lines

otherwise, we will wrongly set entry->have_xr to false if have_xr is true and we have RN for prev -> this.

OK, so its saturday morning and such, but what? Why should we set have_xr true when we have RN? Note that if we only had RN we'd already have bailed on the continue due to only_rx().

So can you elaborate a bit?

Quoted 69 lines · Peter Zijlstra

Quoted 68 lines · Boqun Feng

Quoted 46 lines · Boqun Feng

	/*
	 * DEP_*_BIT in lock_list::dep
	 *
	 * For dependency @prev -> @next:
	 *
	 *   RR: both @prev and @next are recursive read locks, i.e. ->read == 2.
	 *   RN: @prev is recursive and @next is non-recursive.
	 *   NR: @prev is a not recursive and @next is recursive.
	 *   NN: both @prev and @next are non-recursive.
	 * 
	 * Note that we define the value of DEP_*_BITs so that:
	 * 	bit0 is prev->read != 2
	 * 	bit1 is next->read != 2
	 */
	#define DEP_RR_BIT 0
	#define DEP_RN_BIT 1
	#define DEP_NR_BIT 2
	#define DEP_NN_BIT 3

	#define DEP_RR_MASK (1U << (DEP_RR_BIT))
	#define DEP_RN_MASK (1U << (DEP_RN_BIT))
	#define DEP_NR_MASK (1U << (DEP_NR_BIT))
	#define DEP_NN_MASK (1U << (DEP_NN_BIT))

	static inline unsigned int
	__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
	{
		return (prev->read != 2) + ((next->read != 2) << 1)
	}

	static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
	{
		return 1U << __calc_dep_bit(prev, next);
	}

(quoted diff) +0 -0

 	static inline bool only_rx(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}
 
 	static inline bool only_xr(u8 dep)
 	{
 		return !(dep & (DEP_NR_MASK | DEP_NN_MASK));
 	}

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

	if (have_xr && is_rx(entry->dep))
		continue;

	entry->have_xr = is_xr(entry->dep);

Hmm.. I think this part also needs some tweak:

	/* if -> prev is *R, and we only have R* for prev -> this, * skip*/
	if (have_xr && only_rx(entry->dep))
		continue;
	
	/*
	 * we pick a *R for prev -> this only if:
	 *     prev -> this dependencies are all *R 
	 * or
	 *     -> prev is *R, and we don't have NN for prev -> this
	 */
	entry->have_xr = only_xr(entry->dep) || (have_xr && !is_nn(entry->dep));

Quoted 7 lines

Quoted 2 lines

otherwise, we will wrongly set entry->have_xr to false if have_xr is true and we have RN for prev -> this.

OK, so its saturday morning and such, but what? Why should we set have_xr true when we have RN? Note that if we only had RN we'd already have bailed on the continue due to only_rx().

But what if we have RN and NR? only_rx() will return false, but due to have_xr is true, we can not pick RN, so entry->have_xr should be set to true (due to we have to pick NR), however only_xr() is false becuase we have RN, so if we set entry->have_xr to only_xr(), we set it as false.

This is for case like:

	TASK1:
		read_lock(A);
		read_lock(B);
	
	TASK2:
		write_lock(B);
		read_lock(C);
	
	TASK3:
		read_lock(B);
		write_lock(C);

	TASK4:
		read_lock(C);
		write_lock(A);

, which is not a deadlock.

Am I missing something sublte?

Regards,
Boqun

Quoted 1 line

So can you elaborate a bit?

Quoted 18 lines

This is for case like:

	TASK1:
		read_lock(A);
		read_lock(B);
	
	TASK2:
		write_lock(B);
		read_lock(C);
	
	TASK3:
		read_lock(B);
		write_lock(C);

	TASK4:
		read_lock(C);
		write_lock(A);

Quoted 2 lines

, which is not a deadlock.

After TASK 1,2,3 have executed, we have A -(RR)-> B, B -(RN/NR)-> C, and when TASK4 executed, we will try to add C -(RN)-> A into the graph. Before that we need to check whether we have a A -> ... -(*N)-> C path in the graph already, so we search from A (@prev is C and @this is A):

* we set A->have_xr to false, because the dependency we are adding
is a RN.

* we find A -(RR)-> B, and since have_xr (= A->have_xr) is false,

	we can pick this dependency, and since for A -> B, we only have
	RR, so we set B->have_xr to true.

* we then find B -(RN/NR)-> C, and since have_xr (= B->have_xr) is

	true, we will pick it only only_rx(C->dep) return false,
	otherwise we skip. Because we have RN and NR for B -> C,
	therefore we won't skip B -> C.

* Now we try to set C->have_xr, if we set it to only_xr(C->dep),

	we will set it to false, right? Because B -> C has RN.

* Since we now find a entry equal to @prev, we go into the
hlock_conflict() logic and for expression

hlock->read != 2 || !entry->have_xr

@hlock is the C in TASK4, so hlock->read == 2, and @entry is the C whose ->have_xr we just set, so entry->have_xr is false. Therefore hlock_conflict() returns true. And that indicates we find a deadlock in the search. But the above senario can not introduce a deadlock.

Could this help you, or I miss something?

Quoted 52 lines · Boqun Feng

Quoted 18 lines

This is for case like:

	TASK1:
		read_lock(A);
		read_lock(B);
	
	TASK2:
		write_lock(B);
		read_lock(C);
	
	TASK3:
		read_lock(B);
		write_lock(C);

	TASK4:
		read_lock(C);
		write_lock(A);

Quoted 2 lines

, which is not a deadlock.

After TASK 1,2,3 have executed, we have A -(RR)-> B, B -(RN/NR)-> C, and when TASK4 executed, we will try to add C -(RN)-> A into the graph. Before that we need to check whether we have a A -> ... -(*N)-> C path in the graph already, so we search from A (@prev is C and @this is A):

* we set A->have_xr to false, because the dependency we are adding
is a RN.

* we find A -(RR)-> B, and since have_xr (= A->have_xr) is false,

	we can pick this dependency, and since for A -> B, we only have
	RR, so we set B->have_xr to true.

* we then find B -(RN/NR)-> C, and since have_xr (= B->have_xr) is

	true, we will pick it only only_rx(C->dep) return false,
	otherwise we skip. Because we have RN and NR for B -> C,
	therefore we won't skip B -> C.

* Now we try to set C->have_xr, if we set it to only_xr(C->dep),

	we will set it to false, right? Because B -> C has RN.

* Since we now find a entry equal to @prev, we go into the
hlock_conflict() logic and for expression

hlock->read != 2 || !entry->have_xr

@hlock is the C in TASK4, so hlock->read == 2, and @entry is the C whose ->have_xr we just set, so entry->have_xr is false. Therefore hlock_conflict() returns true. And that indicates we find a deadlock in the search. But the above senario can not introduce a deadlock.

Quoted 1 line

Could this help you, or I miss something?

Yes, although it took me forever to grasp because I have snot for brains atm :-(

Would something like:

	dep = entry->dep;

	/* Mask out all *R -> R* relations. */
	if (have_xr)
		dep &= ~(RR_MASK | RN_MASK);

	/* If nothing left, we're done. */
	if (!dep)
		continue;

	/* If there are (only) *R left, set that for the next step. */
	entry->have_xr = !(dep & (RN_MASK | NN_MASK));

Work? I think that reads fairly simple.

Quoted 53 lines · Peter Zijlstra

Quoted 52 lines · Boqun Feng

Quoted 18 lines

This is for case like:

	TASK1:
		read_lock(A);
		read_lock(B);
	
	TASK2:
		write_lock(B);
		read_lock(C);
	
	TASK3:
		read_lock(B);
		write_lock(C);

	TASK4:
		read_lock(C);
		write_lock(A);

Quoted 2 lines

, which is not a deadlock.

After TASK 1,2,3 have executed, we have A -(RR)-> B, B -(RN/NR)-> C, and when TASK4 executed, we will try to add C -(RN)-> A into the graph. Before that we need to check whether we have a A -> ... -(*N)-> C path in the graph already, so we search from A (@prev is C and @this is A):

* we set A->have_xr to false, because the dependency we are adding
is a RN.

* we find A -(RR)-> B, and since have_xr (= A->have_xr) is false,

	we can pick this dependency, and since for A -> B, we only have
	RR, so we set B->have_xr to true.

* we then find B -(RN/NR)-> C, and since have_xr (= B->have_xr) is

	true, we will pick it only only_rx(C->dep) return false,
	otherwise we skip. Because we have RN and NR for B -> C,
	therefore we won't skip B -> C.

* Now we try to set C->have_xr, if we set it to only_xr(C->dep),

	we will set it to false, right? Because B -> C has RN.

* Since we now find a entry equal to @prev, we go into the
hlock_conflict() logic and for expression

hlock->read != 2 || !entry->have_xr

@hlock is the C in TASK4, so hlock->read == 2, and @entry is the C whose ->have_xr we just set, so entry->have_xr is false. Therefore hlock_conflict() returns true. And that indicates we find a deadlock in the search. But the above senario can not introduce a deadlock.

Quoted 5 lines

Quoted 1 line

Could this help you, or I miss something?

Yes, although it took me forever to grasp because I have snot for brains atm :-(

Take care!

Quoted 13 lines

Would something like:

	dep = entry->dep;

	/* Mask out all *R -> R* relations. */
	if (have_xr)
		dep &= ~(RR_MASK | RN_MASK);

	/* If nothing left, we're done. */
	if (!dep)
		continue;

Quoted 5 lines

	/* If there are (only) *R left, set that for the next step. */
	entry->have_xr = !(dep & (RN_MASK | NN_MASK));

Work? I think that reads fairly simple.

I think that works, will apply this simplification to see whether the self tests agree.

Btw, given the comments in the code, I think it's better to name "have_xr" as "only_xr"? I have a feeling that my comment-less code somehow misled you to that name ;-(

Regards,
Boqun

I also reorder bit number for each kind of dependency, so that we have a simple __calc_dep_bit(), see the following:

/*
* DEP_*_BIT in lock_list::dep
*
* For dependency @prev -> @next:
*
* RR: both @prev and @next are recursive read locks, i.e. ->read == 2.
* RN: @prev is recursive and @next is non-recursive.
* NR: @prev is a not recursive and @next is recursive.
* NN: both @prev and @next are non-recursive.

*
* Note that we define the value of DEP_*_BITs so that:
* bit0 is prev->read != 2
* bit1 is next->read != 2
*/
#define DEP_RR_BIT 0
#define DEP_RN_BIT 1
#define DEP_NR_BIT 2

	#define DEP_NN_BIT 3

	#define DEP_RR_MASK (1U << (DEP_RR_BIT))
	#define DEP_RN_MASK (1U << (DEP_RN_BIT))
	#define DEP_NR_MASK (1U << (DEP_NR_BIT))
	#define DEP_NN_MASK (1U << (DEP_NN_BIT))

	static inline unsigned int
	__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
	{
		return (prev->read != 2) + ((next->read != 2) << 1)
	}

	static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
	{
		return 1U << __calc_dep_bit(prev, next);
	}

Now we have four kinds of dependencies in the dependency graph, and not all the pathes carry strong dependencies, for example:

	Given lock A, B, C, if we have:

	CPU1			CPU2
	=============		==============
	write_lock(A);		read_lock(B);
	read_lock(B);		write_lock(C);

	then we have dependencies A--(NR)-->B, and B--(RN)-->C, (NR and
	RN are to indicate the dependency kind), A actually doesn't have
	strong dependency to C(IOW, C doesn't depend on A), to see this,

	let's say we have a third CPU3 doing:

	CPU3:
	=============

	write_lock(C);
	write_lock(A);

	, this is not a deadlock. However if we change the read_lock()
	on CPU2 to a write_lock(), it's a deadlock then.

	So A --(NR)--> B --(RN)--> C is not a strong dependency path but
	A --(NR)--> B --(NN)-->C is a strong dependency path.

We can generalize this as: If a path of dependencies doesn't have two adjacent dependencies as (*R)--L-->(R*), where L is some lock, it is a strong dependency path, otherwise it's not.

Now our mission is to make __bfs() traverse only the strong dependency paths, which is simple: we record whether we have -(*R)-> at the current tail of the path in lock_list::is_rr, and whenever we pick a dependency in the traverse, we 1) make sure we don't pick a -(R*)-> dependency if our current tail is -(*R)-> and 2) greedily pick a -(*N)-> as hard as possible.

With this extension for __bfs(), we now need to initialize the root of __bfs() properly(with a correct ->is_rr), to do so, we introduce some

kernel/locking/lockdep.c +9 -0

+/*
+ * return -1 if no proper dependency could be picked
+ * return 0 if a -(*N)-> dependency could be picked
+ * return 1 if only a -(*R)-> dependency could be picked
+ *
+ * N: non-recursive lock
+ * R: recursive read lock
+ */
+static inline int pick_dep(u16 is_rr, u16 cap_dep)

kernel/locking/lockdep.c +1 -0

@@ -1095,11 +1179,18 @@ static enum bfs_result __bfs(struct lock_list *source_entry,
 		else
 			head = &lock->class->locks_before;
 
+		is_rr = lock->is_rr;

kernel/locking/lockdep.c +1 -0

+
 			visit_lock_entry(entry, lock);
 			if (match(entry, data)) {
 				*target_entry = entry;

Quoted 10 lines · Boqun Feng

Now we have four kinds of dependencies in the dependency graph, and not all the pathes carry strong dependencies, for example:

	Given lock A, B, C, if we have:

	CPU1			CPU2
	=============		==============
	write_lock(A);		read_lock(B);
	read_lock(B);		write_lock(C);

Quoted 3 lines

then we have dependencies A--(NR)-->B, and B--(RN)-->C, (NR and RN are to indicate the dependency kind), A actually doesn't have strong dependency to C(IOW, C doesn't depend on A), to see this,

^ missing space

You're fairly consistent with not putting spaces before opening braces in text, please don't do this, this is not a C function call. Also

double check all your braces are matched, IIRC there's at least one that isn't closed in the previous patches.

Quoted 7 lines

	let's say we have a third CPU3 doing:

	CPU3:
	=============
	write_lock(C);
	write_lock(A);

Quoted 5 lines

	, this is not a deadlock. However if we change the read_lock()
	on CPU2 to a write_lock(), it's a deadlock then.

	So A --(NR)--> B --(RN)--> C is not a strong dependency path but
	A --(NR)--> B --(NN)-->C is a strong dependency path.

I'm not really satisfied with the above reasoning. I don't disagree, but if possible it would be nice to have something a little more solid.

Quoted 12 lines

We can generalize this as: If a path of dependencies doesn't have two adjacent dependencies as (*R)--L-->(R*), where L is some lock, it is a strong dependency path, otherwise it's not.

Now our mission is to make __bfs() traverse only the strong dependency paths, which is simple: we record whether we have -(*R)-> at the current tail of the path in lock_list::is_rr, and whenever we pick a dependency in the traverse, we 1) make sure we don't pick a -(R*)-> dependency if our current tail is -(*R)-> and 2) greedily pick a -(*N)-> as hard as possible.

Quoted 2 lines

With this extension for __bfs(), we now need to initialize the root of __bfs() properly(with a correct ->is_rr), to do so, we introduce some

^ another missing space

Also, I don't like is_rr as a name, have_xr might be better.

Only if we combine *R with R* do we have RR.

Quoted 13 lines

kernel/locking/lockdep.c +13 -0

+/*
+ * return -1 if no proper dependency could be picked
+ * return 0 if a -(*N)-> dependency could be picked
+ * return 1 if only a -(*R)-> dependency could be picked
+ *
+ * N: non-recursive lock
+ * R: recursive read lock
+ */
+static inline int pick_dep(u16 is_rr, u16 cap_dep)
+{
+	if (is_rr) { /* could only pick -(N*)-> */
+		if (cap_dep & DEP_NN_MASK)
+			return 0;

kernel/locking/lockdep.c static inline unsigned int calc_dep(int prev, int next) · line 1061

Quoted 6 lines

kernel/locking/lockdep.c +6 -0

+		else if (cap_dep & DEP_NR_MASK)
+			return 1;
+		else
+			return -1;
+	} else {
+		if (cap_dep & DEP_NN_MASK || cap_dep & DEP_RN_MASK)

	if (cap_dep & (DEP_NN_MASK | DEP_RN_MASK))

kernel/locking/lockdep.c static inline unsigned int calc_dep(int prev, int next) · line 1066

Quoted 6 lines

kernel/locking/lockdep.c +5 -0

+			return 0;
+		else
+			return 1;
+	}
+}

However, I would suggest:

static inline bool is_xr(u16 dep)

{
	return !!(dep & (DEP_NR_MASK | DEP_RR_MASK));
}

static inline bool is_rx(u16 dep)

{
	return !!(dep & (DEP_RN_MASK | DEP_RR_MASK));
}

Quoted 11 lines

kernel/locking/lockdep.c +2 -0

@@ -1095,11 +1179,18 @@ static enum bfs_result __bfs(struct lock_list *source_entry,
 		else
 			head = &lock->class->locks_before;
 
+		is_rr = lock->is_rr;
+
 		DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
 		list_for_each_entry_rcu(entry, head, entry) {
 			unsigned int cq_depth;
 

kernel/locking/lockdep.c static enum bfs_result __bfs(struct lock_list *source_entry, · line 1192

Quoted 4 lines

kernel/locking/lockdep.c +4 -0

+			next_is_rr = pick_dep(is_rr, entry->dep);
+			if (next_is_rr < 0)
+				continue;
+			entry->is_rr = next_is_rr;

		/* Skip *R -> R* relations */
		if (have_xr && is_rx(entry->dep))
			continue;

		entry->have_xr = is_xr(entry->dep);

Which to me is a much simpler construct, hmm?

Quoted 4 lines

kernel/locking/lockdep.c +1 -0

+
 			visit_lock_entry(entry, lock);
 			if (match(entry, data)) {
 				*target_entry = entry;

Quoted 24 lines · Peter Zijlstra

However, I would suggest:

static inline bool is_xr(u16 dep)

{
	return !!(dep & (DEP_NR_MASK | DEP_RR_MASK));
}

static inline bool is_rx(u16 dep)

{
	return !!(dep & (DEP_RN_MASK | DEP_RR_MASK));
}

Quoted 11 lines

kernel/locking/lockdep.c +2 -0

@@ -1095,11 +1179,18 @@ static enum bfs_result __bfs(struct lock_list *source_entry,
 		else
 			head = &lock->class->locks_before;
 
+		is_rr = lock->is_rr;
+
 		DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
 		list_for_each_entry_rcu(entry, head, entry) {
 			unsigned int cq_depth;
 

Quoted 8 lines

kernel/locking/lockdep.c static enum bfs_result __bfs(struct lock_list *source_entry, · line 1192

Quoted 4 lines

kernel/locking/lockdep.c +4 -0

+			next_is_rr = pick_dep(is_rr, entry->dep);
+			if (next_is_rr < 0)
+				continue;
+			entry->is_rr = next_is_rr;

		/* Skip *R -> R* relations */
		if (have_xr && is_rx(entry->dep))
			continue;

I don't think this works, if we pick a *R for previous entry, and for current entry, we have RR, NN and NR, your approach will skip the current entry, but actually we can pick NN or NR (of course, in __bfs(), we can greedily pick NN, because if NR causes a deadlock, so does NN).

Quoted 4 lines

		entry->have_xr = is_xr(entry->dep);

Which to me is a much simpler construct, hmm?

Quoted 14 lines · Boqun Feng

Quoted 12 lines · Peter Zijlstra

However, I would suggest:

static inline bool is_xr(u16 dep)

{
	return !!(dep & (DEP_NR_MASK | DEP_RR_MASK));
}

static inline bool is_rx(u16 dep)

{
	return !!(dep & (DEP_RN_MASK | DEP_RR_MASK));
}

Quoted 8 lines

Quoted 3 lines

		/* Skip *R -> R* relations */
		if (have_xr && is_rx(entry->dep))
			continue;

I don't think this works, if we pick a *R for previous entry, and for current entry, we have RR, NN and NR, your approach will skip the current entry, but actually we can pick NN or NR (of course, in __bfs(), we can greedily pick NN, because if NR causes a deadlock, so does NN).

I don't get it, afaict my suggestion is identical.

You skip condition: pick_dep() < 0, evaluates to:

	is_rr && (!NN_MASK && !NR_MASK) :=
	is_rr && (RN_MASK | RR_MASK)

Which is exactly what I have.

If that is satisfied, you set entry->is_rr to pick_dep(), which his harder to evaluate, but is something like:

	is_rr && NR_MASK || !(NN_MASK | RN_MASK) :=
	is_rr && NR_MASK || (NR_MASK | RR_MASK) :=
	(NR_MASK | RR_MASK)

(because is_rr && RR_MASK will have been skipped)

Quoted 2 lines

Quoted 2 lines

		entry->have_xr = is_xr(entry->dep);

Quoted 31 lines · Peter Zijlstra

Quoted 14 lines · Boqun Feng

Quoted 12 lines · Peter Zijlstra

However, I would suggest:

static inline bool is_xr(u16 dep)

{
	return !!(dep & (DEP_NR_MASK | DEP_RR_MASK));
}

static inline bool is_rx(u16 dep)

{
	return !!(dep & (DEP_RN_MASK | DEP_RR_MASK));
}

Quoted 8 lines

Quoted 3 lines

		/* Skip *R -> R* relations */
		if (have_xr && is_rx(entry->dep))
			continue;

I don't think this works, if we pick a *R for previous entry, and for current entry, we have RR, NN and NR, your approach will skip the current entry, but actually we can pick NN or NR (of course, in __bfs(), we can greedily pick NN, because if NR causes a deadlock, so does NN).

I don't get it, afaict my suggestion is identical.

You skip condition: pick_dep() < 0, evaluates to:

	is_rr && (!NN_MASK && !NR_MASK) :=
	is_rr && (RN_MASK | RR_MASK)

Quoted 1 line

Which is exactly what I have.

Ooh, I think I see what I did wrong, would something like:

	if (have_xr && !is_nx(entry-dep))

work? That's a lot harder to argue about though, still much better than

that tri-state pick thing.

Quoted 4 lines

If that is satisfied, you set entry->is_rr to pick_dep(), which his harder to evaluate, but is something like:

	is_rr && NR_MASK || !(NN_MASK | RN_MASK) :=

Quoted 7 lines

	is_rr && NR_MASK || (NR_MASK | RR_MASK) :=
	(NR_MASK | RR_MASK)

(because is_rr && RR_MASK will have been skipped)

Quoted 2 lines

Quoted 2 lines

		entry->have_xr = is_xr(entry->dep);

This one I think is still correct though.

Quoted 32 lines · Peter Zijlstra

Quoted 31 lines · Peter Zijlstra

Quoted 14 lines · Boqun Feng

Quoted 12 lines · Peter Zijlstra

However, I would suggest:

static inline bool is_xr(u16 dep)

{
	return !!(dep & (DEP_NR_MASK | DEP_RR_MASK));
}

static inline bool is_rx(u16 dep)

{
	return !!(dep & (DEP_RN_MASK | DEP_RR_MASK));
}

Quoted 8 lines

Quoted 3 lines

		/* Skip *R -> R* relations */
		if (have_xr && is_rx(entry->dep))
			continue;

I don't think this works, if we pick a *R for previous entry, and for current entry, we have RR, NN and NR, your approach will skip the current entry, but actually we can pick NN or NR (of course, in __bfs(), we can greedily pick NN, because if NR causes a deadlock, so does NN).

I don't get it, afaict my suggestion is identical.

You skip condition: pick_dep() < 0, evaluates to:

	is_rr && (!NN_MASK && !NR_MASK) :=
	is_rr && (RN_MASK | RR_MASK)

Quoted 7 lines

Quoted 1 line

Which is exactly what I have.

Ooh, I think I see what I did wrong, would something like:

	if (have_xr && !is_nx(entry-dep))

work? That's a lot harder to argue about though, still much better than

I think it works. Although I prefer use name "has_nx" for the fucntion.

Quoted 2 lines

that tri-state pick thing.

Agree.

Quoted 4 lines

Quoted 4 lines

If that is satisfied, you set entry->is_rr to pick_dep(), which his harder to evaluate, but is something like:

	is_rr && NR_MASK || !(NN_MASK | RN_MASK) :=

If is_rr is true and NN_MASK is true, pick_dep() will return 0, however, your expression will return NR_MASK.

	entry->have_xr = !(has_nn(entry->dep) || (!is_rr && has_rn(entry->dep)));
	              := !has_nn(entry->dep) && (is_rr || !has_rn(entry->dep))

Regards,
Boqun

Quoted 9 lines

Quoted 7 lines

	is_rr && NR_MASK || (NR_MASK | RR_MASK) :=
	(NR_MASK | RR_MASK)

(because is_rr && RR_MASK will have been skipped)

Quoted 2 lines

Quoted 2 lines

		entry->have_xr = is_xr(entry->dep);

This one I think is still correct though.

Quoted 3 lines

	entry->have_xr = !(has_nn(entry->dep) || (!is_rr && has_rn(entry->dep)));
	              := !has_nn(entry->dep) && (is_rr || !has_rn(entry->dep))

so it seems that we have to introduce is_{nn,rn,nx}(), I'm not sure introducing three one-off helpers is a good direction to go. One benefit of using pick_dep() is that we can keep the whole logic in one function. Thoughts?

Quoted 27 lines · Peter Zijlstra

Quoted 25 lines · Boqun Feng

Now we have four kinds of dependencies in the dependency graph, and not all the pathes carry strong dependencies, for example:

	Given lock A, B, C, if we have:

	CPU1			CPU2
	=============		==============
	write_lock(A);		read_lock(B);
	read_lock(B);		write_lock(C);

	then we have dependencies A--(NR)-->B, and B--(RN)-->C, (NR and
	RN are to indicate the dependency kind), A actually doesn't have
	strong dependency to C(IOW, C doesn't depend on A), to see this,
	let's say we have a third CPU3 doing:

	CPU3:
	=============
	write_lock(C);
	write_lock(A);

	, this is not a deadlock. However if we change the read_lock()
	on CPU2 to a write_lock(), it's a deadlock then.

	So A --(NR)--> B --(RN)--> C is not a strong dependency path but
	A --(NR)--> B --(NN)-->C is a strong dependency path.

Quoted 3 lines

I'm not really satisfied with the above reasoning. I don't disagree, but if possible it would be nice to have something a little more solid.

What do you mean by "solid"? You mean "A --(NR)--> B --(NN)-->C" is too abstract, and want something like the below instead:

Quoted 32 lines · Boqun Feng

Quoted 30 lines · Peter Zijlstra

Quoted 17 lines · Boqun Feng

Now we have four kinds of dependencies in the dependency graph, and not all the pathes carry strong dependencies, for example:

	Given lock A, B, C, if we have:

	CPU1			CPU2
	=============		==============
	write_lock(A);		read_lock(B);
	read_lock(B);		write_lock(C);

	then we have dependencies A--(NR)-->B, and B--(RN)-->C, (NR and
	RN are to indicate the dependency kind), A actually doesn't have
	strong dependency to C(IOW, C doesn't depend on A), to see this,
	let's say we have a third CPU3 doing:

	CPU3:
	=============

Quoted 8 lines

	write_lock(C);
	write_lock(A);

	, this is not a deadlock. However if we change the read_lock()
	on CPU2 to a write_lock(), it's a deadlock then.

	So A --(NR)--> B --(RN)--> C is not a strong dependency path but
	A --(NR)--> B --(NN)-->C is a strong dependency path.

I'm not really satisfied with the above reasoning. I don't disagree, but if possible it would be nice to have something a little more solid.

Quoted 2 lines

What do you mean by "solid"? You mean "A --(NR)--> B --(NN)-->C" is too abstract, and want something like the below instead:

The above description mostly leaves it as an exercise to the reader to 'proof' ignoring *R -> R* is both safe and complete while that is the main argument.

OK, so I have some 'proof' in patch #16. I could move that proof in the commit log or merge that patch with this one?

kernel/locking/lockdep.c static inline int class_equal(struct lock_list *entry, void *data) · line 1352

Quoted 7 lines · Boqun Feng

kernel/locking/lockdep.c +7 -0

+static inline int hlock_conflict(struct lock_list *entry, void *data)
+{
+	struct held_lock *hlock = (struct held_lock *)data;
+
+	return hlock_class(hlock) == entry->class &&
+	       (hlock->read != 2 || !entry->is_rr);
+}

Bah, brain hurts.

So before we add prev -> this, relation, we check if there's a this -> prev relation already in the graph -- if so that would be a problem.

The above function has @data == @prev (__bfs_forward starts at @this, looking for @prev), and the above patch augments the 'class_equal' test with @prev not having read==2 or @entry not having xr;

This is because.... (insert brain hurt)

Quoted 12 lines · Peter Zijlstra

kernel/locking/lockdep.c static inline int class_equal(struct lock_list *entry, void *data) · line 1352

Quoted 7 lines · Boqun Feng

kernel/locking/lockdep.c +7 -0

+static inline int hlock_conflict(struct lock_list *entry, void *data)
+{
+	struct held_lock *hlock = (struct held_lock *)data;
+
+	return hlock_class(hlock) == entry->class &&
+	       (hlock->read != 2 || !entry->is_rr);
+}

Bah, brain hurts.

Quoted 8 lines

So before we add prev -> this, relation, we check if there's a this -> prev relation already in the graph -- if so that would be a problem.

The above function has @data == @prev (__bfs_forward starts at @this, looking for @prev), and the above patch augments the 'class_equal' test with @prev not having read==2 or @entry not having xr;

This is because.... (insert brain hurt)

(hlock->read != 2 || !entry->have_xr) := !(hlock->read == 2 && entry->have_xr)

hlock->read == 2 := prev->read == 2 entry->have_xr means the last fwd link has read==2.

Together this gives that:

@prev (Rx) ---> X ---> @entry (xR)

does not form a cycle, because:

@enrty (xR) -> @prev (Rx)

is not strong and can be ignored.

Did I get that right? If so, the Changelog needs serious help and code

does too.

As we have four kinds of dependencies now, check_redundant() should only report redundant if we have a dependency path which is equal or _stronger_ than the current dependency. For example if in check_prev_add() we have:

	prev->read == 2 && next->read != 2

, we should only report redundant if we find a path like:

	prev--(RN)-->....--(*N)-->next

and if we have:

	prev->read == 2 && next->read == 2

, we could report redundant if we find a path like:

	prev--(RN)-->....--(*N)-->next

or

	prev--(RN)-->....--(*R)-->next

To do so, we need to pass the recursive-read status of @next into check_redundant().

Signed-off-by Boqun Feng <[email protected]>

---
 kernel/locking/lockdep.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

kernel/locking/lockdep.c +0 -0

index e1be088a34c4..0b0ad3db78b4 100644
@@ -1338,9 +1338,12 @@ print_circular_bug_header(struct lock_list *entry, unsigned int depth,
 	return 0;
 }

Quoted 19 lines · Boqun Feng

As we have four kinds of dependencies now, check_redundant() should only report redundant if we have a dependency path which is equal or _stronger_ than the current dependency. For example if in check_prev_add() we have:

	prev->read == 2 && next->read != 2

, we should only report redundant if we find a path like:

	prev--(RN)-->....--(*N)-->next

and if we have:

	prev->read == 2 && next->read == 2

, we could report redundant if we find a path like:

	prev--(RN)-->....--(*N)-->next

Quoted 6 lines

or

	prev--(RN)-->....--(*R)-->next

To do so, we need to pass the recursive-read status of @next into check_redundant().

Very hard to read that.

Quoted 12 lines

Signed-off-by Boqun Feng <[email protected]>

---
 kernel/locking/lockdep.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

kernel/locking/lockdep.c +0 -0

index e1be088a34c4..0b0ad3db78b4 100644
@@ -1338,9 +1338,12 @@ print_circular_bug_header(struct lock_list *entry, unsigned int depth,
 	return 0;
 }

kernel/locking/lockdep.c print_circular_bug_header(struct lock_list *entry, unsigned int depth, · line 1347

Quoted 10 lines

kernel/locking/lockdep.c +5 -2

 
-static inline int class_equal(struct lock_list *entry, void *data)
+static inline int hlock_equal(struct lock_list *entry, void *data)
 {
-	return entry->class == data;
+	struct held_lock *hlock = (struct held_lock *)data;
+
+	return hlock_class(hlock) == entry->class &&
+	       (hlock->read == 2 || !entry->is_rr);
 }

So I guess @data = @next, and we're checking if @prev -> @next already exists.

Since we only care about forward dependencies, @next->read==2 means *R and if so, any existing link is equal or stronger. If @next->read!=2, it means *N and we must regard *R as weaker and not match.

OK, that seems to be fine, but again, that function _really_ could do with a comment.

There are four cases for recursive read lock realted deadlocks:

(--(X..Y)--> means a strong dependency path starts with a --(X*)--> dependency and ends with a --(*Y)-- dependency.)

1. An irq-safe lock L1 has a dependency --(*..*)--> to an
irq-unsafe lock L2.

2. An irq-read-safe lock L1 has a dependency --(N..*)--> to an
irq-unsafe lock L2.

3. An irq-safe lock L1 has a dependency --(*..N)--> to an
irq-read-unsafe lock L2.

4. An irq-read-safe lock L1 has a dependency --(N..N)--> to an
irq-read-unsafe lock L2.

The current check_usage() only checks 1) and 2), so this patch adds checks for 3) and 4) and makes sure when find_usage_{back,for}wards find an irq-read-{,un}safe lock, the traverse path should ends at a dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates a real dependency --(N*)-->.

Signed-off-by Boqun Feng <[email protected]>

---
 kernel/locking/lockdep.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

kernel/locking/lockdep.c +0 -0

index 0b0ad3db78b4..bd3eef664f9d 100644
@@ -1504,7 +1504,14 @@ check_redundant(struct lock_list *root, struct held_lock *target,
 
 static inline int usage_match(struct lock_list *entry, void *bit)
 {

There are four cases for recursive read lock realted deadlocks:

(--(X..Y)--> means a strong dependency path starts with a --(X*)--> dependency and ends with a --(*Y)-- dependency.)

1. An irq-safe lock L1 has a dependency --(*..*)--> to an
irq-unsafe lock L2.

2. An irq-read-safe lock L1 has a dependency --(N..*)--> to an
irq-unsafe lock L2.

3. An irq-safe lock L1 has a dependency --(*..N)--> to an
irq-read-unsafe lock L2.

4. An irq-read-safe lock L1 has a dependency --(N..N)--> to an
irq-read-unsafe lock L2.

The current check_usage() only checks 1) and 2), so this patch adds checks for 3) and 4) and makes sure when find_usage_{back,for}wards find an irq-read-{,un}safe lock, the traverse path should ends at a dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates a real dependency --(N*)-->.

Quoted 14 lines · Boqun Feng

There are four cases for recursive read lock realted deadlocks:

(--(X..Y)--> means a strong dependency path starts with a --(X*)--> dependency and ends with a --(*Y)-- dependency.)

1. An irq-safe lock L1 has a dependency --(*..*)--> to an
irq-unsafe lock L2.

2. An irq-read-safe lock L1 has a dependency --(N..*)--> to an
irq-unsafe lock L2.

3. An irq-safe lock L1 has a dependency --(*..N)--> to an
irq-read-unsafe lock L2.

Quoted 8 lines

4. An irq-read-safe lock L1 has a dependency --(N..N)--> to an
irq-read-unsafe lock L2.

The current check_usage() only checks 1) and 2), so this patch adds checks for 3) and 4) and makes sure when find_usage_{back,for}wards find an irq-read-{,un}safe lock, the traverse path should ends at a dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates a real dependency --(N*)-->.

This adds 4 __bfs() searches for every new link.

Can't we make the existing traversals smarter?

Quoted 24 lines · Peter Zijlstra

Quoted 22 lines · Boqun Feng

There are four cases for recursive read lock realted deadlocks:

(--(X..Y)--> means a strong dependency path starts with a --(X*)--> dependency and ends with a --(*Y)-- dependency.)

1. An irq-safe lock L1 has a dependency --(*..*)--> to an
irq-unsafe lock L2.

2. An irq-read-safe lock L1 has a dependency --(N..*)--> to an
irq-unsafe lock L2.

3. An irq-safe lock L1 has a dependency --(*..N)--> to an
irq-read-unsafe lock L2.

4. An irq-read-safe lock L1 has a dependency --(N..N)--> to an
irq-read-unsafe lock L2.

The current check_usage() only checks 1) and 2), so this patch adds checks for 3) and 4) and makes sure when find_usage_{back,for}wards find an irq-read-{,un}safe lock, the traverse path should ends at a dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates a real dependency --(N*)-->.

Quoted 3 lines

This adds 4 __bfs() searches for every new link.

Can't we make the existing traversals smarter?

Haven't really thought this one through, I will try. But as you said, we

only need to do more searchs for _new_ links, so I think it's the slow path, would the performance matter that much?

Regards,
Boqun

Hmm... think again, maybe I can combine case 1 with 3, and case 2 with 4, because each of them could share the same find_usage_backwards(), and find_usage_forwards() uses a usage_match_forwards() as follow for the match function:

	static inline int usage_match_forwards(struct lock_list *entry, void *bit)
	{
		enum lock_usage_bit ub = (enum lock_usage_bit)bit;
		unsigned long mask;
		unsigned long read_mask;

		/* mask out the read bit */
		ub &= ~1;

		mask = 1ULL << ub;
		read_mask = 1ULL << (ub + 1);

		return (entry->class->usage_mask & mask) ||  // *-> L2 and L2 is an irq-unsafe lock
		       ((entry->class->usage_mask & read_mask) && !entry->is_rr); // N-> L2 and L2 is an irq-read-unsafe lock
	}

Got a bus to catch, I can explain this later, if you need ;-)

include/linux/lockdep.h +0 -0

index a1f91f8680bd..3fce8dbf5091 100644
@@ -186,11 +186,11 @@ struct lock_list {
 	struct list_head		entry;

Quoted 12 lines · Boqun Feng

include/linux/lockdep.h +1 -2

index a1f91f8680bd..3fce8dbf5091 100644
@@ -186,11 +186,11 @@ struct lock_list {
 	struct list_head		entry;
 	struct lock_class		*class;
 	struct stack_trace		trace;
-	int				distance;
+	u16				distance;
 	/* bitmap of different dependencies from head to this */
-	u16				dep;

include/linux/lockdep.h struct lock_list { · line 193

Quoted 4 lines

include/linux/lockdep.h +2 -1

+	u8				dep;
 	/* used by BFS to record whether this is picked as a recursive read */
-	u16				is_rr;
+	bool				is_rr;

Don't use bool, use u8 if you want a single byte. sizeof(_Bool) is part of the architecture ABI and can be up to 4 bytes (well really anything, but I've not seen it bigger than 4 bytes for any sane implementation).

As now we support recursive read lock deadlock detection, add related explanation in the Documentation/lockdep/lockdep-desgin.txt:

* Definition of recursive read locks, non-recursive locks, strong

	dependency path and notions of -(**)->.

* Lockdep's assumption.

* Informal proof of recursive read lock deadlock detection.

Signed-off-by Boqun Feng <[email protected]>

Cc Randy Dunlap <[email protected]>

---
 Documentation/locking/lockdep-design.txt | 170 +++++++++++++++++++++++++++++++
 1 file changed, 170 insertions(+)

Documentation/locking/lockdep-design.txt +132 -0

index 382bc25589c2..fd8a8d97ce58 100644
@@ -284,3 +284,173 @@ Run the command and save the output, then compare against the output from
 a later run of this command to identify the leakers.  This same output
 can also help you find situations where runtime lock initialization has
 been omitted.
+
+Recursive Read Deadlock Detection:
+----------------------------------
+Lockdep now is equipped with deadlock detection for recursive read locks.
+
+Recursive read locks, as their name indicates, are the locks able to be
+acquired recursively. Unlike non-recursive read locks, recursive read locks
+only get blocked by current write lock *holders* other than write lock
+*waiters*, for example:
+
+	TASK A:			TASK B:
+
+	read_lock(X);
+
+				write_lock(X);
+
+	read_lock(X);
+
+is not a deadlock for recursive read locks, as while the task B is waiting for
+the lock X, the second read_lock() doesn't need to wait because it's a recursive
+read lock.
+
+Note that a lock can be a write lock(exclusive lock), a non-recursive read lock
+(non-recursive shared lock) or a recursive read lock(recursive shared lock),
+depending on the API used to acquire it(more specifically, the value of the
+'read' parameter for lock_acquire(...)). In other words, a single lock instance
+has three types of acquisition depending on the acquisition functions:
+exclusive, non-recursive read, and recursive read.
+
+That said, recursive read locks could introduce deadlocks too, considering the
+following:
+
+	TASK A:			TASK B:
+
+	read_lock(X);
+				read_lock(Y);
+	write_lock(Y);
+				write_lock(X);
+
+, neither task could get the write locks because the corresponding read locks
+are held by each other.
+
+Lockdep could detect recursive read lock related deadlocks. The dependencies(edges)
+in the lockdep graph are classified into four categories:
+
+1) -(NN)->: non-recursive to non-recursive dependency, non-recursive locks include
+            non-recursive read locks, write locks and exclusive locks(e.g. spinlock_t).
+	    They are treated equally in deadlock detection. "X -(NN)-> Y" means
+            X -> Y and both X and Y are non-recursive locks.
+
+2) -(RN)->: recursive to non-recursive dependency, recursive locks means recursive read
+	    locks. "X -(RN)-> Y" means X -> Y and X is recursive read lock and
+            Y is non-recursive lock.
+
+3) -(NR)->: non-recursive to recursive dependency, "X -(NR)-> Y" means X -> Y and X is
+            non-recursive lock and Y is recursive lock.
+
+4) -(RR)->: recursive to recursive dependency, "X -(RR)-> Y" means X -> Y and both X
+            and Y are recursive locks.
+
+Note that given two locks, they may have multiple dependencies between them, for example:
+
+	TASK A:
+
+	read_lock(X);
+	write_lock(Y);
+	...
+
+	TASK B:
+
+	write_lock(X);
+	write_lock(Y);
+
+, we have both X -(RN)-> Y and X -(NN)-> Y in the dependency graph.
+
+And obviously a non-recursive lock can block the corresponding recursive lock,
+and vice versa. Besides a non-recursive lock may block the other non-recursive
+lock of the same instance(e.g. a write lock may block a corresponding
+non-recursive read lock and vice versa).
+
+We use -(*N)-> for edges that is either -(RN)-> or -(NN)->, the similar for -(N*)->,
+-(*R)-> and -(R*)->
+
+A "path" is a series of conjunct dependency edges in the graph. And we define a
+"strong" path, which indicates the strong dependency throughout each dependency
+in the path, as the path that doesn't have two conjunct edges(dependencies) as
+-(*R)-> and -(R*)->. IOW, a "strong" path is a path from a lock walking to another
+through the lock dependencies, and if X -> Y -> Z in the path(where X, Y, Z are
+locks), if the walk from X to Y is through a -(NR)-> or -(RR)-> dependency, the
+walk from Y to Z must not be through a -(RN)-> or -(RR)-> dependency, otherwise
+it's not a strong path.
+
+We now prove that if a strong path forms a circle, then we have a potential deadlock.
+By "forms a circle", it means for a set of locks A0,A1...An, there is a path from
+A0 to An:
+
+	A0 -> A1 -> ... -> An
+
+and there is also a dependency An->A0. And as the circle is formed by a strong path,
+so there are no two conjunct dependency edges as -(*R)-> and -(R*)->.
+
+
+To understand the actual proof, let's look into lockdep's assumption:
+
+For each lockdep dependency A -> B, there may exist a case where someone is
+trying to acquire B with A held, and the existence of such a case is
+independent to the existences of cases for other lockdep dependencies.
+
+For example if we have two functions func1 and func2:
+
+	void func1(...) {
+		lock(A);
+		lock(B);
+		unlock(A);
+		unlock(B);
+
+		lock(C);
+		lock(A);
+		unlock(A);
+		unlock(C);
+	}
+
+	void func2(...) {
+		lock(B);
+		lock(C);
+		unlock(C);
+		unlock(B);
+	}
+
+lockdep will generate dependencies: A->B, B->C and C->A, and assume that:
+
+	there may exist a case where someone is trying to acquire B with A held,

Documentation/locking/lockdep-design.txt +28 -0

+
+For a strong dependency circle like:
+
+	A0 -> A1 -> ... -> An
+	^                  |
+	|                  |
+	+------------------+
+, lockdep assumes that
+
+	there may exist a case where someone is trying to acquire A1 with A0 held
+	there may exist a case where someone is trying to acquire A2 with A1 held
+	...
+	there may exist a case where someone is trying to acquire An with An-1 held
+	there may exist a case where someone is trying to acquire A0 with An held
+
+, and because it's a *strong* dependency circle for every Ai (0<=i<=n), Ai is either
+held as a non-recursive lock or someone is trying to acquire Ai as a non-recursive lock,
+which gives:
+
+*	If Ai is held as a non-recursive lock, then trying to acquire it,
+	whether as a recursive lock or not, will get blocked.
+
+*	If Ai is held as a recursive lock, then there must be someone is trying to acquire
+	it as a non-recursive lock, and because recursive locks blocks non-recursive locks,
+	then it(the "someone") will get blocked.
+
+So all the holders of A0, A1...An are blocked with A0, A1...An held by each other,
+no one can progress, therefore deadlock.

Signature · 1 line

2.16.1

Quoted 3 lines · Boqun Feng

As now we support recursive read lock deadlock detection, add related explanation in the Documentation/lockdep/lockdep-desgin.txt:

Quoted 6 lines

* Definition of recursive read locks, non-recursive locks, strong

	dependency path and notions of -(**)->.

* Lockdep's assumption.

* Informal proof of recursive read lock deadlock detection.

Once again... much appreciated!!, thanks for sharing.

Quoted 148 lines

Signed-off-by Boqun Feng <[email protected]>

Cc Randy Dunlap <[email protected]>

---
 Documentation/locking/lockdep-design.txt | 170 +++++++++++++++++++++++++++++++
 1 file changed, 170 insertions(+)

Documentation/locking/lockdep-design.txt +132 -0

index 382bc25589c2..fd8a8d97ce58 100644
@@ -284,3 +284,173 @@ Run the command and save the output, then compare against the output from
 a later run of this command to identify the leakers.  This same output
 can also help you find situations where runtime lock initialization has
 been omitted.
+
+Recursive Read Deadlock Detection:
+----------------------------------
+Lockdep now is equipped with deadlock detection for recursive read locks.
+
+Recursive read locks, as their name indicates, are the locks able to be
+acquired recursively. Unlike non-recursive read locks, recursive read locks
+only get blocked by current write lock *holders* other than write lock
+*waiters*, for example:
+
+	TASK A:			TASK B:
+
+	read_lock(X);
+
+				write_lock(X);
+
+	read_lock(X);
+
+is not a deadlock for recursive read locks, as while the task B is waiting for
+the lock X, the second read_lock() doesn't need to wait because it's a recursive
+read lock.
+
+Note that a lock can be a write lock(exclusive lock), a non-recursive read lock
+(non-recursive shared lock) or a recursive read lock(recursive shared lock),
+depending on the API used to acquire it(more specifically, the value of the
+'read' parameter for lock_acquire(...)). In other words, a single lock instance
+has three types of acquisition depending on the acquisition functions:
+exclusive, non-recursive read, and recursive read.
+
+That said, recursive read locks could introduce deadlocks too, considering the
+following:
+
+	TASK A:			TASK B:
+
+	read_lock(X);
+				read_lock(Y);
+	write_lock(Y);
+				write_lock(X);
+
+, neither task could get the write locks because the corresponding read locks
+are held by each other.
+
+Lockdep could detect recursive read lock related deadlocks. The dependencies(edges)
+in the lockdep graph are classified into four categories:
+
+1) -(NN)->: non-recursive to non-recursive dependency, non-recursive locks include
+            non-recursive read locks, write locks and exclusive locks(e.g. spinlock_t).
+	    They are treated equally in deadlock detection. "X -(NN)-> Y" means
+            X -> Y and both X and Y are non-recursive locks.
+
+2) -(RN)->: recursive to non-recursive dependency, recursive locks means recursive read
+	    locks. "X -(RN)-> Y" means X -> Y and X is recursive read lock and
+            Y is non-recursive lock.
+
+3) -(NR)->: non-recursive to recursive dependency, "X -(NR)-> Y" means X -> Y and X is
+            non-recursive lock and Y is recursive lock.
+
+4) -(RR)->: recursive to recursive dependency, "X -(RR)-> Y" means X -> Y and both X
+            and Y are recursive locks.
+
+Note that given two locks, they may have multiple dependencies between them, for example:
+
+	TASK A:
+
+	read_lock(X);
+	write_lock(Y);
+	...
+
+	TASK B:
+
+	write_lock(X);
+	write_lock(Y);
+
+, we have both X -(RN)-> Y and X -(NN)-> Y in the dependency graph.
+
+And obviously a non-recursive lock can block the corresponding recursive lock,
+and vice versa. Besides a non-recursive lock may block the other non-recursive
+lock of the same instance(e.g. a write lock may block a corresponding
+non-recursive read lock and vice versa).
+
+We use -(*N)-> for edges that is either -(RN)-> or -(NN)->, the similar for -(N*)->,
+-(*R)-> and -(R*)->
+
+A "path" is a series of conjunct dependency edges in the graph. And we define a
+"strong" path, which indicates the strong dependency throughout each dependency
+in the path, as the path that doesn't have two conjunct edges(dependencies) as
+-(*R)-> and -(R*)->. IOW, a "strong" path is a path from a lock walking to another
+through the lock dependencies, and if X -> Y -> Z in the path(where X, Y, Z are
+locks), if the walk from X to Y is through a -(NR)-> or -(RR)-> dependency, the
+walk from Y to Z must not be through a -(RN)-> or -(RR)-> dependency, otherwise
+it's not a strong path.
+
+We now prove that if a strong path forms a circle, then we have a potential deadlock.
+By "forms a circle", it means for a set of locks A0,A1...An, there is a path from
+A0 to An:
+
+	A0 -> A1 -> ... -> An
+
+and there is also a dependency An->A0. And as the circle is formed by a strong path,
+so there are no two conjunct dependency edges as -(*R)-> and -(R*)->.
+
+
+To understand the actual proof, let's look into lockdep's assumption:
+
+For each lockdep dependency A -> B, there may exist a case where someone is
+trying to acquire B with A held, and the existence of such a case is
+independent to the existences of cases for other lockdep dependencies.
+
+For example if we have two functions func1 and func2:
+
+	void func1(...) {
+		lock(A);
+		lock(B);
+		unlock(A);
+		unlock(B);
+
+		lock(C);
+		lock(A);
+		unlock(A);
+		unlock(C);
+	}
+
+	void func2(...) {
+		lock(B);
+		lock(C);
+		unlock(C);
+		unlock(B);
+	}
+
+lockdep will generate dependencies: A->B, B->C and C->A, and assume that:
+
+	there may exist a case where someone is trying to acquire B with A held,

Documentation/locking/lockdep-design.txt Run the command and save the output, then compare against the output from · line 428

Quoted 10 lines

Documentation/locking/lockdep-design.txt +10 -0

+	there may exist a case where someone is trying to acquire C with B held,
+	and there may exist a case where someone is trying to acquire A with C held,
+
+and those three cases exist *independently*, meaning they can happen at the
+same time(which requires func1() being called simultaneously by two CPUs or
+tasks, which may be impossible due to other constraints in the real life)
+
+
+With this assumption, we can prove that if a strong dependency path forms a circle,
+then it indicates a deadlock as far as lockdep is concerned.

As mentioned in a private communication, I would recommend the adoption of a "more impersonal" style. Here, for instance, the expression:

"indicates a deadlock as far as lockdep is concerned"

would be replaced with:

"indicates a deadlock as (informally) defined in Sect. ?.?";

similarly (from the proof):

"For a strong dependency [...], lockdep assumes that [...]"

would be replaced with:

"For a strong dependency [...], from assumption/notation ?.?,
we have/we can conclude [...]".

This could mean that additional text/content would need to be added to the present doc./.txt; OTOH, this could help to make this doc. self-contained/ more accessible to "non-lockdep-experts".

Andrea

Quoted 31 lines

Documentation/locking/lockdep-design.txt +28 -0

+
+For a strong dependency circle like:
+
+	A0 -> A1 -> ... -> An
+	^                  |
+	|                  |
+	+------------------+
+, lockdep assumes that
+
+	there may exist a case where someone is trying to acquire A1 with A0 held
+	there may exist a case where someone is trying to acquire A2 with A1 held
+	...
+	there may exist a case where someone is trying to acquire An with An-1 held
+	there may exist a case where someone is trying to acquire A0 with An held
+
+, and because it's a *strong* dependency circle for every Ai (0<=i<=n), Ai is either
+held as a non-recursive lock or someone is trying to acquire Ai as a non-recursive lock,
+which gives:
+
+*	If Ai is held as a non-recursive lock, then trying to acquire it,
+	whether as a recursive lock or not, will get blocked.
+
+*	If Ai is held as a recursive lock, then there must be someone is trying to acquire
+	it as a non-recursive lock, and because recursive locks blocks non-recursive locks,
+	then it(the "someone") will get blocked.
+
+So all the holders of A0, A1...An are blocked with A0, A1...An held by each other,
+no one can progress, therefore deadlock.

Signature · 1 line

2.16.1