Skip to contentSkip to conversation

locking/lockdep: Add support for dynamic keys

PATCH Superseded Bart Van Assche 4 participants 50 messages Nov 28, 2018 – Dec 5, 2018

Subsystems (4)

v1 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

cover locking/lockdep: Add support for dynamic keys

Hi Ingo and Peter,

A known shortcoming of the current lockdep implementation is that it requires lock keys to be allocated statically and that this key sharing can cause false positive deadlock reports. This patch series adds support for dynamic keys in the lockdep code. I'm not claiming that this patch series is perfect. However, the code in this patch series survives nontrivial tests so I think it's worth a look. Two unrelated changes in this patch series are:
- Improve the lockdep tests.
- Complain if no name has been assigned to a lock object.

Thanks,

Bart.

Bart Van Assche (27):
lockdep tests: Display compiler warning and error messages lockdep tests: Fix shellcheck warnings
lockdep tests: Improve testing accuracy
lockdep tests: Run lockdep tests a second time under Valgrind
liblockdep: Rename "trywlock" into "trywrlock"
liblockdep: Add dummy print_irqtrace_events() implementation lockdep tests: Test the lockdep_reset_lock() implementation locking/lockdep: Declare local symbols static locking/lockdep: Inline __lockdep_init_map() locking/lockdep: Introduce lock_class_cache_is_registered()
timekeeping: Assign a name to tk_core.seq.dep_map net/core: Assign a name to devnet_rename_seq.dep_map locking/lockdep: Complain if a lock object has no name locking/lockdep: Remove a superfluous INIT_LIST_HEAD() statement locking/lockdep: Make concurrent lockdep_reset_lock() calls safe locking/lockdep: Stop using RCU primitives to access all_lock_classes locking/lockdep: Make zap_class() remove all matching lock order
entries
locking/lockdep: Reorder struct lock_class members locking/lockdep: Retain the class key and name while freeing a lock
class
locking/lockdep: Free lock classes that are no longer in use locking/lockdep: Rename lock_list.entry into
lock_list.lock_order_entry
locking/lockdep: Reuse list entries that are no longer in use locking/lockdep: Check data structure consistency locking/lockdep: Introduce __lockdep_free_key_range() locking/lockdep: Add support for dynamic keys kernel/workqueue: Use dynamic lockdep keys for workqueues lockdep tests: Test dynamic key registration

 include/linux/lockdep.h                       |  45 +-
 include/linux/workqueue.h                     |  28 +-
 kernel/locking/lockdep.c                      | 640 +++++++++++++++---
 kernel/locking/lockdep_proc.c                 |   2 +-
 kernel/time/timekeeping.c                     |   4 +-
 kernel/workqueue.c                            |  60 +-
 net/core/dev.c                                |   2 +-
 tools/lib/lockdep/include/liblockdep/common.h |   3 +
 tools/lib/lockdep/include/liblockdep/mutex.h  |  12 +-
 tools/lib/lockdep/include/liblockdep/rwlock.h |   6 +-
 tools/lib/lockdep/lockdep.c                   |   5 +
 tools/lib/lockdep/run_tests.sh                |  38 +-
 tools/lib/lockdep/tests/AA.sh                 |   2 +
 tools/lib/lockdep/tests/ABA.sh                |   2 +
 tools/lib/lockdep/tests/ABBA.c                |  12 +
 tools/lib/lockdep/tests/ABBA.sh               |   2 +
 tools/lib/lockdep/tests/ABBA_2threads.sh      |   2 +
 tools/lib/lockdep/tests/ABBCCA.c              |   4 +
 tools/lib/lockdep/tests/ABBCCA.sh             |   2 +
 tools/lib/lockdep/tests/ABBCCDDA.c            |   5 +
 tools/lib/lockdep/tests/ABBCCDDA.sh           |   2 +
 tools/lib/lockdep/tests/ABCABC.c              |   4 +
 tools/lib/lockdep/tests/ABCABC.sh             |   2 +
 tools/lib/lockdep/tests/ABCDBCDA.c            |   5 +
 tools/lib/lockdep/tests/ABCDBCDA.sh           |   2 +
 tools/lib/lockdep/tests/ABCDBDDA.c            |   5 +
 tools/lib/lockdep/tests/ABCDBDDA.sh           |   2 +
 tools/lib/lockdep/tests/WW.sh                 |   2 +
 tools/lib/lockdep/tests/unlock_balance.c      |   2 +
 tools/lib/lockdep/tests/unlock_balance.sh     |   2 +
 30 files changed, 726 insertions(+), 178 deletions(-)
 create mode 100755 tools/lib/lockdep/tests/AA.sh
 create mode 100755 tools/lib/lockdep/tests/ABA.sh
 create mode 100755 tools/lib/lockdep/tests/ABBA.sh
 create mode 100755 tools/lib/lockdep/tests/ABBA_2threads.sh
 create mode 100755 tools/lib/lockdep/tests/ABBCCA.sh
 create mode 100755 tools/lib/lockdep/tests/ABBCCDDA.sh
 create mode 100755 tools/lib/lockdep/tests/ABCABC.sh
 create mode 100755 tools/lib/lockdep/tests/ABCDBCDA.sh
 create mode 100755 tools/lib/lockdep/tests/ABCDBDDA.sh
 create mode 100755 tools/lib/lockdep/tests/WW.sh
 create mode 100755 tools/lib/lockdep/tests/unlock_balance.sh
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#1 lore raw

PATCH 1/27 lockdep tests: Display compiler warning and error messages

If compilation of liblockdep fails, display an error message and exit immediately. Display compiler warning and error messages that are generated while building a test. Only run a test if compilation succeeded.

---
 tools/lib/lockdep/run_tests.sh | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)
tools/lib/lockdep/run_tests.sh +8 -5
index 2e570a188f16..eef3fe4a24fe 100755
@@ -1,13 +1,16 @@
 #! /bin/bash
 # SPDX-License-Identifier: GPL-2.0
 
-make &> /dev/null
+if ! make >/dev/null; then
+    echo "Building liblockdep failed."
+    echo "FAILED!"
+fi
 
 for i in `ls tests/*.c`; do
 	testname=$(basename "$i" .c)
-	gcc -o tests/$testname -pthread $i liblockdep.a -Iinclude -D__USE_LIBLOCKDEP &> /dev/null
 	echo -ne "$testname... "
-	if [ $(timeout 1 ./tests/$testname 2>&1 | wc -l) -gt 0 ]; then
+	if gcc -o "tests/$testname" -pthread "$i" liblockdep.a -Iinclude -D__USE_LIBLOCKDEP &&
+		[ "$(timeout 1 "./tests/$testname" 2>&1 | wc -l)" -gt 0 ]; then
 		echo "PASSED!"
 	else
 		echo "FAILED!"
@@ -19,9 +22,9 @@ done
 
 for i in `ls tests/*.c`; do
 	testname=$(basename "$i" .c)
-	gcc -o tests/$testname -pthread -Iinclude $i &> /dev/null
 	echo -ne "(PRELOAD) $testname... "
-	if [ $(timeout 1 ./lockdep ./tests/$testname 2>&1 | wc -l) -gt 0 ]; then
+	if gcc -o "tests/$testname" -pthread -Iinclude "$i" &&
+		[ "$(timeout 1 ./lockdep "./tests/$testname" 2>&1 | wc -l)" -gt 0 ]; then
 		echo "PASSED!"
 	else
 		echo "FAILED!"
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#2 lore raw

PATCH 2/27 lockdep tests: Fix shellcheck warnings

In reply to Bart Van Assche

Use find instead of ls to avoid splitting filenames that contain spaces. Use rm -f instead of if ... then rm ...; fi. This patch addresses all shellcheck complaints about the run_tests.sh shell script.

---
 tools/lib/lockdep/run_tests.sh | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)
tools/lib/lockdep/run_tests.sh +4 -8
index eef3fe4a24fe..e4f41318aa79 100755
@@ -6,7 +6,7 @@ if ! make >/dev/null; then
     echo "FAILED!"
 fi
 
-for i in `ls tests/*.c`; do
+find tests -name '*.c' | sort | while read -r i; do
 	testname=$(basename "$i" .c)
 	echo -ne "$testname... "
 	if gcc -o "tests/$testname" -pthread "$i" liblockdep.a -Iinclude -D__USE_LIBLOCKDEP &&
@@ -15,12 +15,10 @@ for i in `ls tests/*.c`; do
 	else
 		echo "FAILED!"
 	fi
-	if [ -f "tests/$testname" ]; then
-		rm tests/$testname
-	fi
+	rm -f "tests/$testname"
 done
 
-for i in `ls tests/*.c`; do
+find tests -name '*.c' | sort | while read -r i; do
 	testname=$(basename "$i" .c)
 	echo -ne "(PRELOAD) $testname... "
 	if gcc -o "tests/$testname" -pthread -Iinclude "$i" &&
@@ -29,7 +27,5 @@ for i in `ls tests/*.c`; do
 	else
 		echo "FAILED!"
 	fi
-	if [ -f "tests/$testname" ]; then
-		rm tests/$testname
-	fi
+	rm -f "tests/$testname"
 done
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#3 lore raw

PATCH 3/27 lockdep tests: Improve testing accuracy

In reply to Bart Van Assche

Instead of checking whether the tests produced any output, check the output itself. This patch avoids that e.g. debug output causes the message "PASSED!" to be reported for failed tests.

---
 tools/lib/lockdep/run_tests.sh            | 5 +++--
 tools/lib/lockdep/tests/AA.sh             | 2 ++
 tools/lib/lockdep/tests/ABA.sh            | 2 ++
 tools/lib/lockdep/tests/ABBA.sh           | 2 ++
 tools/lib/lockdep/tests/ABBA_2threads.sh  | 2 ++
 tools/lib/lockdep/tests/ABBCCA.sh         | 2 ++
 tools/lib/lockdep/tests/ABBCCDDA.sh       | 2 ++
 tools/lib/lockdep/tests/ABCABC.sh         | 2 ++
 tools/lib/lockdep/tests/ABCDBCDA.sh       | 2 ++
 tools/lib/lockdep/tests/ABCDBDDA.sh       | 2 ++
 tools/lib/lockdep/tests/WW.sh             | 2 ++
 tools/lib/lockdep/tests/unlock_balance.sh | 2 ++
 12 files changed, 25 insertions(+), 2 deletions(-)
 create mode 100755 tools/lib/lockdep/tests/AA.sh
 create mode 100755 tools/lib/lockdep/tests/ABA.sh
 create mode 100755 tools/lib/lockdep/tests/ABBA.sh
 create mode 100755 tools/lib/lockdep/tests/ABBA_2threads.sh
 create mode 100755 tools/lib/lockdep/tests/ABBCCA.sh
 create mode 100755 tools/lib/lockdep/tests/ABBCCDDA.sh
 create mode 100755 tools/lib/lockdep/tests/ABCABC.sh
 create mode 100755 tools/lib/lockdep/tests/ABCDBCDA.sh
 create mode 100755 tools/lib/lockdep/tests/ABCDBDDA.sh
 create mode 100755 tools/lib/lockdep/tests/WW.sh
 create mode 100755 tools/lib/lockdep/tests/unlock_balance.sh
tools/lib/lockdep/run_tests.sh +3 -2
index e4f41318aa79..38b8c9034b8e 100755
@@ -10,7 +10,7 @@ find tests -name '*.c' | sort | while read -r i; do
 	testname=$(basename "$i" .c)
 	echo -ne "$testname... "
 	if gcc -o "tests/$testname" -pthread "$i" liblockdep.a -Iinclude -D__USE_LIBLOCKDEP &&
-		[ "$(timeout 1 "./tests/$testname" 2>&1 | wc -l)" -gt 0 ]; then
+		timeout 1 "tests/$testname" 2>&1 | "tests/${testname}.sh"; then
 		echo "PASSED!"
 	else
 		echo "FAILED!"
@@ -22,7 +22,8 @@ find tests -name '*.c' | sort | while read -r i; do
 	testname=$(basename "$i" .c)
 	echo -ne "(PRELOAD) $testname... "
 	if gcc -o "tests/$testname" -pthread -Iinclude "$i" &&
-		[ "$(timeout 1 ./lockdep "./tests/$testname" 2>&1 | wc -l)" -gt 0 ]; then
+		timeout 1 ./lockdep "tests/$testname" 2>&1 |
+		"tests/${testname}.sh"; then
 		echo "PASSED!"
 	else
 		echo "FAILED!"
tools/lib/lockdep/tests/AA.sh new file +2 -0
new file mode 100755
index 000000000000..f39b32865074
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible recursive locking detected'
tools/lib/lockdep/tests/ABA.sh new file +2 -0
new file mode 100755
index 000000000000..f39b32865074
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible recursive locking detected'
tools/lib/lockdep/tests/ABBA.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/ABBA_2threads.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/ABBCCA.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/ABBCCDDA.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/ABCABC.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/ABCDBCDA.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/ABCDBDDA.sh new file +2 -0
new file mode 100755
index 000000000000..fc31c607a5a8
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible circular locking dependency detected'
tools/lib/lockdep/tests/WW.sh new file +2 -0
new file mode 100755
index 000000000000..f39b32865074
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: possible recursive locking detected'
tools/lib/lockdep/tests/unlock_balance.sh new file +2 -0
new file mode 100755
index 000000000000..c6e3952303fe
@@ -0,0 +1,2 @@
+#!/bin/bash
+grep -q 'WARNING: bad unlock balance detected'
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#4 lore raw

PATCH 4/27 lockdep tests: Run lockdep tests a second time under Valgrind

In reply to Bart Van Assche

This improves test coverage.

---
 tools/lib/lockdep/run_tests.sh | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
tools/lib/lockdep/run_tests.sh +14 -0
index 38b8c9034b8e..f1b5027925db 100755
@@ -30,3 +30,17 @@ find tests -name '*.c' | sort | while read -r i; do
 	fi
 	rm -f "tests/$testname"
 done
+
+find tests -name '*.c' | sort | while read -r i; do
+	testname=$(basename "$i" .c)
+	echo -ne "(PRELOAD + Valgrind) $testname... "
+	if gcc -o "tests/$testname" -pthread -Iinclude "$i" &&
+		{ timeout 10 valgrind --read-var-info=yes ./lockdep "./tests/$testname" >& "tests/${testname}.vg.out"; true; } &&
+		"tests/${testname}.sh" < "tests/${testname}.vg.out" &&
+		! grep -Eq '(^==[0-9]*== (Invalid |Uninitialised ))|Mismatched free|Source and destination overlap| UME ' "tests/${testname}.vg.out"; then
+		echo "PASSED!"
+	else
+		echo "FAILED!"
+	fi
+	rm -f "tests/$testname"
+done
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#5 lore raw

PATCH 5/27 liblockdep: Rename "trywlock" into "trywrlock"

In reply to Bart Van Assche

This patch avoids that the following compiler warning is reported while compiling the lockdep unit tests:

include/liblockdep/rwlock.h: In function 'liblockdep_pthread_rwlock_trywlock':
include/liblockdep/rwlock.h:66:9: warning: implicit declaration of function 'pthread_rwlock_trywlock'; did you mean 'pthread_rwlock_trywrlock'? [-Wimplicit-function-declaration]

  return pthread_rwlock_trywlock(&lock->rwlock) == 0 ? 1 : 0;
         ^~~~~~~~~~~~~~~~~~~~~~~
         pthread_rwlock_trywrlock
Fixes 5a52c9b480e0 ("liblockdep: Add public headers for pthread_rwlock_t implementation")
Cc Sasha Levin <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 tools/lib/lockdep/include/liblockdep/rwlock.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
tools/lib/lockdep/include/liblockdep/rwlock.h +3 -3
index a96c3bf0fef1..365762e3a1ea 100644
@@ -60,10 +60,10 @@ static inline int liblockdep_pthread_rwlock_tryrdlock(liblockdep_pthread_rwlock_
 	return pthread_rwlock_tryrdlock(&lock->rwlock) == 0 ? 1 : 0;
 }
 
-static inline int liblockdep_pthread_rwlock_trywlock(liblockdep_pthread_rwlock_t *lock)
+static inline int liblockdep_pthread_rwlock_trywrlock(liblockdep_pthread_rwlock_t *lock)
 {
 	lock_acquire(&lock->dep_map, 0, 1, 0, 1, NULL, (unsigned long)_RET_IP_);
-	return pthread_rwlock_trywlock(&lock->rwlock) == 0 ? 1 : 0;
+	return pthread_rwlock_trywrlock(&lock->rwlock) == 0 ? 1 : 0;
 }
 
 static inline int liblockdep_rwlock_destroy(liblockdep_pthread_rwlock_t *lock)
@@ -79,7 +79,7 @@ static inline int liblockdep_rwlock_destroy(liblockdep_pthread_rwlock_t *lock)
 #define pthread_rwlock_unlock		liblockdep_pthread_rwlock_unlock
 #define pthread_rwlock_wrlock		liblockdep_pthread_rwlock_wrlock
 #define pthread_rwlock_tryrdlock	liblockdep_pthread_rwlock_tryrdlock
-#define pthread_rwlock_trywlock		liblockdep_pthread_rwlock_trywlock
+#define pthread_rwlock_trywrlock	liblockdep_pthread_rwlock_trywrlock
 #define pthread_rwlock_destroy		liblockdep_rwlock_destroy
 
 #endif
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#6 lore raw

PATCH 6/27 liblockdep: Add dummy print_irqtrace_events() implementation

In reply to Bart Van Assche

This patch avoids that linking against liblockdep fails due to no print_irqtrace_events() definition being available.

---
 tools/lib/lockdep/lockdep.c | 5 +++++
 1 file changed, 5 insertions(+)
tools/lib/lockdep/lockdep.c +5 -0
index 6002fcf2f9bc..348a9d0fb766 100644
@@ -15,6 +15,11 @@ u32 prandom_u32(void)
 	abort();
 }
 
+void print_irqtrace_events(struct task_struct *curr)
+{
+	abort();
+}
+
 static struct new_utsname *init_utsname(void)
 {
 	static struct new_utsname n = (struct new_utsname) {
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#7 lore raw

PATCH 7/27 lockdep tests: Test the lockdep_reset_lock() implementation

In reply to Bart Van Assche

This patch makes sure that the lockdep_reset_lock() function gets tested.

---
 tools/lib/lockdep/include/liblockdep/common.h | 1 +
 tools/lib/lockdep/include/liblockdep/mutex.h  | 1 +
 tools/lib/lockdep/tests/ABBA.c                | 3 +++
 tools/lib/lockdep/tests/ABBCCA.c              | 4 ++++
 tools/lib/lockdep/tests/ABBCCDDA.c            | 5 +++++
 tools/lib/lockdep/tests/ABCABC.c              | 4 ++++
 tools/lib/lockdep/tests/ABCDBCDA.c            | 5 +++++
 tools/lib/lockdep/tests/ABCDBDDA.c            | 5 +++++
 tools/lib/lockdep/tests/unlock_balance.c      | 2 ++
 9 files changed, 30 insertions(+)
tools/lib/lockdep/include/liblockdep/common.h +1 -0
index 8862da80995a..d640a9761f09 100644
@@ -44,6 +44,7 @@ void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 			struct lockdep_map *nest_lock, unsigned long ip);
 void lock_release(struct lockdep_map *lock, int nested,
 			unsigned long ip);
+void lockdep_reset_lock(struct lockdep_map *lock);
 extern void debug_check_no_locks_freed(const void *from, unsigned long len);
 
 #define STATIC_LOCKDEP_MAP_INIT(_name, _key) \
tools/lib/lockdep/include/liblockdep/mutex.h +1 -0
index a80ac39f966e..2073d4e1f2f0 100644
@@ -54,6 +54,7 @@ static inline int liblockdep_pthread_mutex_trylock(liblockdep_pthread_mutex_t *l
 
 static inline int liblockdep_pthread_mutex_destroy(liblockdep_pthread_mutex_t *lock)
 {
+	lockdep_reset_lock(&lock->dep_map);
 	return pthread_mutex_destroy(&lock->mutex);
 }
 
tools/lib/lockdep/tests/ABBA.c +3 -0
index 1460afd33d71..623313f54720 100644
@@ -11,4 +11,7 @@ void main(void)
 
 	LOCK_UNLOCK_2(a, b);
 	LOCK_UNLOCK_2(b, a);
+
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
tools/lib/lockdep/tests/ABBCCA.c +4 -0
index a54c1b2af118..48446129d496 100644
@@ -13,4 +13,8 @@ void main(void)
 	LOCK_UNLOCK_2(a, b);
 	LOCK_UNLOCK_2(b, c);
 	LOCK_UNLOCK_2(c, a);
+
+	pthread_mutex_destroy(&c);
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
tools/lib/lockdep/tests/ABBCCDDA.c +5 -0
index aa5d194e8869..3570bf7b3804 100644
@@ -15,4 +15,9 @@ void main(void)
 	LOCK_UNLOCK_2(b, c);
 	LOCK_UNLOCK_2(c, d);
 	LOCK_UNLOCK_2(d, a);
+
+	pthread_mutex_destroy(&d);
+	pthread_mutex_destroy(&c);
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
tools/lib/lockdep/tests/ABCABC.c +4 -0
index b54a08e60416..a1c4659894cd 100644
@@ -13,4 +13,8 @@ void main(void)
 	LOCK_UNLOCK_2(a, b);
 	LOCK_UNLOCK_2(c, a);
 	LOCK_UNLOCK_2(b, c);
+
+	pthread_mutex_destroy(&c);
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
tools/lib/lockdep/tests/ABCDBCDA.c +5 -0
index a56742250d86..335af1c90ab5 100644
@@ -15,4 +15,9 @@ void main(void)
 	LOCK_UNLOCK_2(c, d);
 	LOCK_UNLOCK_2(b, c);
 	LOCK_UNLOCK_2(d, a);
+
+	pthread_mutex_destroy(&d);
+	pthread_mutex_destroy(&c);
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
tools/lib/lockdep/tests/ABCDBDDA.c +5 -0
index 238a3353f3c3..3c5972863049 100644
@@ -15,4 +15,9 @@ void main(void)
 	LOCK_UNLOCK_2(c, d);
 	LOCK_UNLOCK_2(b, d);
 	LOCK_UNLOCK_2(d, a);
+
+	pthread_mutex_destroy(&d);
+	pthread_mutex_destroy(&c);
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
tools/lib/lockdep/tests/unlock_balance.c +2 -0
index 34cf32f689de..dba25064b50a 100644
@@ -10,4 +10,6 @@ void main(void)
 	pthread_mutex_lock(&a);
 	pthread_mutex_unlock(&a);
 	pthread_mutex_unlock(&a);
+
+	pthread_mutex_destroy(&a);
 }
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#8 lore raw

PATCH 8/27 locking/lockdep: Declare local symbols static

In reply to Bart Van Assche

This patch avoids that sparse complains about a missing declaration for the lock_classes array.

---
 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/locking/lockdep.c +1 -1
index 1efada2dd9dd..46b67b7467b4 100644
@@ -138,7 +138,7 @@ static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
  * get freed - this significantly simplifies the debugging code.
  */
 unsigned long nr_lock_classes;
-struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
+static struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
 
 static inline struct lock_class *hlock_class(struct held_lock *hlock)
 {
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#9 lore raw

PATCH 9/27 locking/lockdep: Inline __lockdep_init_map()

In reply to Bart Van Assche

Since the function __lockdep_init_map() only has one caller, inline it into its caller. This patch does not change any functionality.

---
 kernel/locking/lockdep.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
kernel/locking/lockdep.c +1 -7
index 46b67b7467b4..58205b6ac5ed 100644
@@ -3088,7 +3088,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 /*
  * Initialize a lock instance's lock-class mapping info:
  */
-static void __lockdep_init_map(struct lockdep_map *lock, const char *name,
+void lockdep_init_map(struct lockdep_map *lock, const char *name,
 		      struct lock_class_key *key, int subclass)
 {
 	int i;
@@ -3144,12 +3144,6 @@ static void __lockdep_init_map(struct lockdep_map *lock, const char *name,
 		raw_local_irq_restore(flags);
 	}
 }
-
-void lockdep_init_map(struct lockdep_map *lock, const char *name,
-		      struct lock_class_key *key, int subclass)
-{
-	__lockdep_init_map(lock, name, key, subclass);
-}
 EXPORT_SYMBOL_GPL(lockdep_init_map);
 
 struct lock_class_key __lockdep_no_validate__;
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#10 lore raw

PATCH 10/27 locking/lockdep: Introduce lock_class_cache_is_registered()

In reply to Bart Van Assche

This patch does not change any functionality but makes the lockdep_reset_lock() function easier to read.

---
 kernel/locking/lockdep.c | 50 ++++++++++++++++++++++++----------------
 1 file changed, 30 insertions(+), 20 deletions(-)
kernel/locking/lockdep.c +30 -20
index 58205b6ac5ed..8177a8de1e1d 100644
@@ -4198,13 +4198,33 @@ void lockdep_free_key_range(void *start, unsigned long size)
 	 */
 }
 
-void lockdep_reset_lock(struct lockdep_map *lock)
+/*
+ * Check whether any element of the @lock->class_cache[] array refers to a
+ * registered lock class. The caller must hold either the graph lock or the
+ * RCU read lock.
+ */
+static bool lock_class_cache_is_registered(struct lockdep_map *lock)
 {
 	struct lock_class *class;
 	struct hlist_head *head;
-	unsigned long flags;
 	int i, j;
-	int locked;
+
+	for (i = 0; i < CLASSHASH_SIZE; i++) {
+		head = classhash_table + i;
+		hlist_for_each_entry_rcu(class, head, hash_entry) {
+			for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
+				if (lock->class_cache[j] == class)
+					return true;
+		}
+	}
+	return false;
+}
+
+void lockdep_reset_lock(struct lockdep_map *lock)
+{
+	struct lock_class *class;
+	unsigned long flags;
+	int j, locked;
 
 	raw_local_irq_save(flags);
 
@@ -4224,24 +4244,14 @@ void lockdep_reset_lock(struct lockdep_map *lock)
 	 * be gone.
 	 */
 	locked = graph_lock();
-	for (i = 0; i < CLASSHASH_SIZE; i++) {
-		head = classhash_table + i;
-		hlist_for_each_entry_rcu(class, head, hash_entry) {
-			int match = 0;
-
-			for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
-				match |= class == lock->class_cache[j];
-
-			if (unlikely(match)) {
-				if (debug_locks_off_graph_unlock()) {
-					/*
-					 * We all just reset everything, how did it match?
-					 */
-					WARN_ON(1);
-				}
-				goto out_restore;
-			}
+	if (unlikely(lock_class_cache_is_registered(lock))) {
+		if (debug_locks_off_graph_unlock()) {
+			/*
+			 * We all just reset everything, how did it match?
+			 */
+			WARN_ON(1);
 		}
+		goto out_restore;
 	}
 	if (locked)
 		graph_unlock();
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#11 lore raw

PATCH 11/27 timekeeping: Assign a name to tk_core.seq.dep_map

In reply to Bart Van Assche

This patch makes lockdep reports that refer to tk_core.seq more informative.

---
 kernel/time/timekeeping.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
kernel/time/timekeeping.c +3 -1
index 2d110c948805..6c9493495538 100644
@@ -50,7 +50,9 @@ enum timekeeping_adv_mode {
 static struct {
 	seqcount_t		seq;
 	struct timekeeper	timekeeper;
-} tk_core ____cacheline_aligned;
+} tk_core ____cacheline_aligned = {
+	.seq = SEQCNT_ZERO(tk_core.seq),
+};
 
 static DEFINE_RAW_SPINLOCK(timekeeper_lock);
 static struct timekeeper shadow_timekeeper;
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#12 lore raw

[tip:timers/core] timekeeping: Use proper seqcount initializer

timekeeping: Use proper seqcount initializer
Commit-ID:  ce10a5b3954f2514af726beb78ed8d7350c5e41c
Gitweb:     https://git.kernel.org/tip/ce10a5b3954f2514af726beb78ed8d7350c5e41c
Author:     Bart Van Assche <[email protected]>
AuthorDate: Wed, 28 Nov 2018 15:43:09 -0800
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Wed, 5 Dec 2018 11:00:09 +0100

timekeeping: Use proper seqcount initializer

tk_core.seq is initialized open coded, but that misses to initialize the lockdep map when lockdep is enabled. Lockdep splats involving tk_core seq consequently lack a name and are hard to read.

Use the proper initializer which takes care of the lockdep map initialization.

[ tglx: Massaged changelog ]

---
 kernel/time/timekeeping.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
kernel/time/timekeeping.c +3 -1
index cd02bd38cf2d..c801e25875a3 100644
@@ -45,7 +45,9 @@ enum timekeeping_adv_mode {
 static struct {
 	seqcount_t		seq;
 	struct timekeeper	timekeeper;
-} tk_core ____cacheline_aligned;
+} tk_core ____cacheline_aligned = {
+	.seq = SEQCNT_ZERO(tk_core.seq),
+};
 
 static DEFINE_RAW_SPINLOCK(timekeeper_lock);
 static struct timekeeper shadow_timekeeper;
#13 lore raw

PATCH 12/27 net/core: Assign a name to devnet_rename_seq.dep_map

In reply to Bart Van Assche

This patch makes lockdep reports about devnet_rename_seq more informative.

---
 net/core/dev.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/core/dev.c +1 -1
index ddc551f24ba2..8c109a1624ba 100644
@@ -194,7 +194,7 @@ static DEFINE_SPINLOCK(napi_hash_lock);
 static unsigned int napi_gen_id = NR_CPUS;
 static DEFINE_READ_MOSTLY_HASHTABLE(napi_hash, 8);
 
-static seqcount_t devnet_rename_seq;
+static seqcount_t devnet_rename_seq = SEQCNT_ZERO(devnet_rename_seq);
 
 static inline void dev_base_seq_inc(struct net *net)
 {
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#15 lore raw

PATCH 13/27 locking/lockdep: Complain if a lock object has no name

In reply to Bart Van Assche

Lockdep reports about lock objects that do not have a name are hard to interpret. Hence complain if no name has been assigned to a lock object.

---
 kernel/locking/lockdep.c | 1 +
 1 file changed, 1 insertion(+)
kernel/locking/lockdep.c +1 -0
index 8177a8de1e1d..41fd3b279220 100644
@@ -743,6 +743,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	struct hlist_head *hash_head;
 	struct lock_class *class;
 
+	WARN_ON_ONCE(!lock->name);
 	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
 	class = look_up_lock_class(lock, subclass);
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#16 lore raw

PATCH 14/27 locking/lockdep: Remove a superfluous INIT_LIST_HEAD() statement

In reply to Bart Van Assche

Initializing a list entry just before it is passed to list_add_tail_rcu() is not necessary because list_add_tail_rcu() overwrites the next and prev pointers anyway. Hence remove the INIT_LIST_HEAD() statement.

---
 kernel/locking/lockdep.c | 1 -
 1 file changed, 1 deletion(-)
kernel/locking/lockdep.c +0 -1
index 41fd3b279220..83ffcc7f1ced 100644
@@ -790,7 +790,6 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	class->key = key;
 	class->name = lock->name;
 	class->subclass = subclass;
-	INIT_LIST_HEAD(&class->lock_entry);
 	INIT_LIST_HEAD(&class->locks_before);
 	INIT_LIST_HEAD(&class->locks_after);
 	class->name_version = count_matching_names(class);
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#17 lore raw

PATCH 15/27 locking/lockdep: Make concurrent lockdep_reset_lock() calls safe

In reply to Bart Van Assche

Since zap_class() removes items from the all_lock_classes list and the classhash_table, protect all zap_class() calls with the graph lock.

---
 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/locking/lockdep.c +1 -1
index 83ffcc7f1ced..ab6abe52e974 100644
@@ -4227,6 +4227,7 @@ void lockdep_reset_lock(struct lockdep_map *lock)
 	int j, locked;
 
 	raw_local_irq_save(flags);
+	locked = graph_lock();
 
 	/*
 	 * Remove all classes this lock might have:
@@ -4243,7 +4244,6 @@ void lockdep_reset_lock(struct lockdep_map *lock)
 	 * Debug check: in the end all mapped classes should
 	 * be gone.
 	 */
-	locked = graph_lock();
 	if (unlikely(lock_class_cache_is_registered(lock))) {
 		if (debug_locks_off_graph_unlock()) {
 			/*
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#18 lore raw

PATCH 16/27 locking/lockdep: Stop using RCU primitives to access all_lock_classes

In reply to Bart Van Assche

Due to the previous patch all code that accesses the 'all_lock_classes' list holds the graph lock. Hence use regular list primitives instead of their RCU variants to access this list.

---
 kernel/locking/lockdep.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)
kernel/locking/lockdep.c +8 -4
index ab6abe52e974..96fc8e92c2a6 100644
@@ -626,7 +626,8 @@ static int static_obj(void *obj)
 
 /*
  * To make lock name printouts unique, we calculate a unique
- * class->name_version generation counter:
+ * class->name_version generation counter. The caller must hold the graph
+ * lock.
  */
 static int count_matching_names(struct lock_class *new_class)
 {
@@ -636,7 +637,7 @@ static int count_matching_names(struct lock_class *new_class)
 	if (!new_class->name)
 		return 0;
 
-	list_for_each_entry_rcu(class, &all_lock_classes, lock_entry) {
+	list_for_each_entry(class, &all_lock_classes, lock_entry) {
 		if (new_class->key - new_class->subclass == class->key)
 			return class->name_version;
 		if (class->name && !strcmp(class->name, new_class->name))
@@ -801,7 +802,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	/*
 	 * Add it to the global list of classes:
 	 */
-	list_add_tail_rcu(&class->lock_entry, &all_lock_classes);
+	list_add_tail(&class->lock_entry, &all_lock_classes);
 
 	if (verbose(class)) {
 		graph_unlock();
@@ -4120,6 +4121,9 @@ void lockdep_reset(void)
 	raw_local_irq_restore(flags);
 }
 
+/*
+ * Remove all references to a lock class. The caller must hold the graph lock.
+ */
 static void zap_class(struct lock_class *class)
 {
 	int i;
@@ -4136,7 +4140,7 @@ static void zap_class(struct lock_class *class)
 	 * Unhash the class and remove it from the all_lock_classes list:
 	 */
 	hlist_del_rcu(&class->hash_entry);
-	list_del_rcu(&class->lock_entry);
+	list_del(&class->lock_entry);
 
 	RCU_INIT_POINTER(class->key, NULL);
 	RCU_INIT_POINTER(class->name, NULL);
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#19 lore raw

PATCH 17/27 locking/lockdep: Make zap_class() remove all matching lock order entries

In reply to Bart Van Assche

Make sure that all entries that refer to a class are removed from the list_entries[] array when a kernel module is unloaded.

---
 include/linux/lockdep.h  |  1 +
 kernel/locking/lockdep.c | 17 +++++++++++------
 2 files changed, 12 insertions(+), 6 deletions(-)
include/linux/lockdep.h +1 -0
index 1fd82ff99c65..6d0f8d1c2bee 100644
@@ -180,6 +180,7 @@ static inline void lockdep_copy_map(struct lockdep_map *to,
 struct lock_list {
 	struct list_head		entry;
 	struct lock_class		*class;
+	struct lock_class		*links_to;
 	struct stack_trace		trace;
 	int				distance;
 
kernel/locking/lockdep.c +11 -6
index 96fc8e92c2a6..fc10302d34fd 100644
@@ -857,7 +857,8 @@ static struct lock_list *alloc_list_entry(void)
 /*
  * Add a new dependency to the head of the list:
  */
-static int add_lock_to_list(struct lock_class *this, struct list_head *head,
+static int add_lock_to_list(struct lock_class *this,
+			    struct lock_class *links_to, struct list_head *head,
 			    unsigned long ip, int distance,
 			    struct stack_trace *trace)
 {
@@ -870,7 +871,9 @@ static int add_lock_to_list(struct lock_class *this, struct list_head *head,
 	if (!entry)
 		return 0;
 
+	WARN_ON_ONCE(this == links_to);
 	entry->class = this;
+	entry->links_to = links_to;
 	entry->distance = distance;
 	entry->trace = *trace;
 	/*
@@ -1916,14 +1919,14 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	 * Ok, all validations passed, add the new lock
 	 * to the previous lock's dependency list:
 	 */
-	ret = add_lock_to_list(hlock_class(next),
+	ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
 			       &hlock_class(prev)->locks_after,
 			       next->acquire_ip, distance, trace);
 
 	if (!ret)
 		return 0;
 
-	ret = add_lock_to_list(hlock_class(prev),
+	ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
 			       &hlock_class(next)->locks_before,
 			       next->acquire_ip, distance, trace);
 	if (!ret)
@@ -4126,15 +4129,17 @@ void lockdep_reset(void)
  */
 static void zap_class(struct lock_class *class)
 {
+	struct lock_list *entry;
 	int i;
 
 	/*
 	 * Remove all dependencies this lock is
 	 * involved in:
 	 */
-	for (i = 0; i < nr_list_entries; i++) {
-		if (list_entries[i].class == class)
-			list_del_rcu(&list_entries[i].entry);
+	for (i = 0, entry = list_entries; i < nr_list_entries; i++, entry++) {
+		if (entry->class != class && entry->links_to != class)
+			continue;
+		list_del_rcu(&entry->entry);
 	}
 	/*
 	 * Unhash the class and remove it from the all_lock_classes list:
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#20 lore raw

PATCH 18/27 locking/lockdep: Reorder struct lock_class members

In reply to Bart Van Assche

This patch does not change any functionality but makes the patch that frees lock classes that are no longer in use easier to read.

---
 include/linux/lockdep.h | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)
include/linux/lockdep.h +7 -7
index 6d0f8d1c2bee..9421f028c26c 100644
@@ -76,6 +76,13 @@ struct lock_class {
 	 */
 	struct list_head		lock_entry;
 
+	/*
+	 * These fields represent a directed graph of lock dependencies,
+	 * to every node we attach a list of "forward" and a list of
+	 * "backward" graph nodes.
+	 */
+	struct list_head		locks_after, locks_before;
+
 	struct lockdep_subclass_key	*key;
 	unsigned int			subclass;
 	unsigned int			dep_gen_id;
@@ -86,13 +93,6 @@ struct lock_class {
 	unsigned long			usage_mask;
 	struct stack_trace		usage_traces[XXX_LOCK_USAGE_STATES];
 
-	/*
-	 * These fields represent a directed graph of lock dependencies,
-	 * to every node we attach a list of "forward" and a list of
-	 * "backward" graph nodes.
-	 */
-	struct list_head		locks_after, locks_before;
-
 	/*
 	 * Generation counter, when doing certain classes of graph walking,
 	 * to ensure that we check one node only once:
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#21 lore raw

PATCH 19/27 locking/lockdep: Retain the class key and name while freeing a lock class

In reply to Bart Van Assche

The next patch in this series uses the class name in code that detects lock class use-after-free. Hence retain the class name for lock classes that are being freed.

---
 kernel/locking/lockdep.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
kernel/locking/lockdep.c +1 -3
index fc10302d34fd..4610f3c4f3db 100644
@@ -4145,10 +4145,8 @@ static void zap_class(struct lock_class *class)
 	 * Unhash the class and remove it from the all_lock_classes list:
 	 */
 	hlist_del_rcu(&class->hash_entry);
+	class->hash_entry.pprev = NULL;
 	list_del(&class->lock_entry);
-
-	RCU_INIT_POINTER(class->key, NULL);
-	RCU_INIT_POINTER(class->name, NULL);
 }
 
 static inline int within(const void *addr, void *start, unsigned long size)
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#22 lore raw

PATCH 20/27 locking/lockdep: Free lock classes that are no longer in use

In reply to Bart Van Assche

Instead of leaving lock classes that are no longer in use in the lock_classes array, reuse entries from that array that are no longer in use. Maintain a linked list of free lock classes with list head 'free_lock_class'. Initialize that list from inside register_lock_class() instead of from inside lockdep_init() because register_lock_class() can be called before lockdep_init() has been called. Only add freed lock classes to the free_lock_classes list after a grace period to avoid that a lock_classes[] element would be reused while an RCU reader is accessing it.

---
 include/linux/lockdep.h  |   9 +-
 kernel/locking/lockdep.c | 233 +++++++++++++++++++++++++++++++--------
 2 files changed, 195 insertions(+), 47 deletions(-)
include/linux/lockdep.h +6 -3
index 9421f028c26c..02a1469c46e1 100644
@@ -63,7 +63,8 @@ extern struct lock_class_key __lockdep_no_validate__;
 #define LOCKSTAT_POINTS		4
 
 /*
- * The lock-class itself:
+ * The lock-class itself. The order of the structure members matters.
+ * reinit_class() zeroes the key member and all subsequent members.
  */
 struct lock_class {
 	/*
@@ -72,7 +73,9 @@ struct lock_class {
 	struct hlist_node		hash_entry;
 
 	/*
-	 * global list of all lock-classes:
+	 * Entry in all_lock_classes when in use. Entry in free_lock_classes
+	 * when not in use. Instances that are being freed are briefly on
+	 * neither list.
 	 */
 	struct list_head		lock_entry;
 
@@ -106,7 +109,7 @@ struct lock_class {
 	unsigned long			contention_point[LOCKSTAT_POINTS];
 	unsigned long			contending_point[LOCKSTAT_POINTS];
 #endif
-};
+} __no_randomize_layout;
 
 #ifdef CONFIG_LOCK_STAT
 struct lock_time {
kernel/locking/lockdep.c +189 -44

367 lines not on this page · raw message

Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
maintainer
#23 lore raw

Re: [PATCH 20/27] locking/lockdep: Free lock classes that are no longer in use

Quoted 45 lines · Bart Van Assche
kernel/locking/lockdep.c +45 -0
+/* Must be called with the graph lock held. */
+static void remove_class_from_lock_chain(struct lock_chain *chain,
+					 struct lock_class *class)
+{
+	u64 chain_key;
+	int i;
+
+	for (i = chain->base; i < chain->base + chain->depth; i++) {
+		if (chain_hlocks[i] != class - lock_classes)
+			continue;
+		if (--chain->depth == 0)
+			break;
+		memmove(&chain_hlocks[i], &chain_hlocks[i + 1],
+			(chain->base + chain->depth - i) *
+			sizeof(chain_hlocks[0]));
+		/*
+		 * Each lock class occurs at most once in a
+		 * lock chain so once we found a match we can
+		 * break out of this loop.
+		 */
+		break;
+	}
+	/*
+	 * Note: calling hlist_del_rcu() from inside a
+	 * hlist_for_each_entry_rcu() loop is safe.
+	 */
+	if (chain->depth == 0) {
+		/* To do: decrease chain count. See also inc_chains(). */
+		hlist_del_rcu(&chain->entry);
+		return;
+	}
+	chain_key = 0;
+	for (i = chain->base; i < chain->base + chain->depth; i++)
+		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+	if (chain->chain_key == chain_key)
+		return;
+	hlist_del_rcu(&chain->entry);
+	chain->chain_key = chain_key;
+	hlist_add_head_rcu(&chain->entry, chainhashentry(chain_key));
+}
+
+/* Must be called with the graph lock held. */
+static void remove_class_from_lock_chains(struct lock_class *class)
+{
+	struct lock_chain *chain;

kernel/locking/lockdep.c void lockdep_reset(void) · line 4210

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+	struct hlist_head *head;
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
+		head = chainhash_table + i;
+		hlist_for_each_entry_rcu(chain, head, entry) {
+			remove_class_from_lock_chain(chain, class);
+		}
+	}
+}

*shudder*, I suppose that is the reason I never went there.

I suoppose that if you don't do this too often it doesn't matter it is horribly epxneisve.

#24 lore raw

PATCH 21/27 locking/lockdep: Rename lock_list.entry into lock_list.lock_order_entry

In reply to Bart Van Assche

The next patch in this series will add a new list entry member to struct lock_list. Rename the existing "entry" member to keep the lockdep source code readable.

---
 include/linux/lockdep.h       | 3 ++-
 kernel/locking/lockdep.c      | 9 +++++----
 kernel/locking/lockdep_proc.c | 2 +-
 3 files changed, 8 insertions(+), 6 deletions(-)
include/linux/lockdep.h +2 -1
index 02a1469c46e1..43327a1dd488 100644
@@ -181,7 +181,8 @@ static inline void lockdep_copy_map(struct lockdep_map *to,
  * We only grow the list, never remove from it:
  */
 struct lock_list {
-	struct list_head		entry;
+	/* Entry in locks_after or locks_before. */
+	struct list_head		lock_order_entry;
 	struct lock_class		*class;
 	struct lock_class		*links_to;
 	struct stack_trace		trace;
kernel/locking/lockdep.c +5 -4
index 53d8daa8d0dc..038377d67410 100644
@@ -900,7 +900,7 @@ static int add_lock_to_list(struct lock_class *this,
 	 * iteration is under RCU-sched; see look_up_lock_class() and
 	 * lockdep_free_key_range().
 	 */
-	list_add_tail_rcu(&entry->entry, head);
+	list_add_tail_rcu(&entry->lock_order_entry, head);
 
 	return 1;
 }
@@ -1051,7 +1051,7 @@ static int __bfs(struct lock_list *source_entry,
 
 		DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
-		list_for_each_entry_rcu(entry, head, entry) {
+		list_for_each_entry_rcu(entry, head, lock_order_entry) {
 			if (!lock_accessed(entry)) {
 				unsigned int cq_depth;
 				mark_lock_accessed(entry, lock);
@@ -1916,7 +1916,8 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	 *  chains - the second one will be new, but L1 already has
 	 *  L2 added to its dependency list, due to the first chain.)
 	 */
-	list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) {
+	list_for_each_entry(entry, &hlock_class(prev)->locks_after,
+			    lock_order_entry) {
 		if (entry->class == hlock_class(next)) {
 			if (distance == 1)
 				entry->distance = 1;
@@ -4246,7 +4247,7 @@ static void zap_class(struct list_head *zapped_classes,
 			continue;
 		links_to = entry->links_to;
 		WARN_ON_ONCE(entry->class == links_to);
-		list_del_rcu(&entry->entry);
+		list_del_rcu(&entry->lock_order_entry);
 		entry->class = NULL;
 		entry->links_to = NULL;
 		check_free_class(zapped_classes, class);
kernel/locking/lockdep_proc.c +1 -1
index 3d31f9b0059e..17460b412927 100644
@@ -82,7 +82,7 @@ static int l_show(struct seq_file *m, void *v)
 	print_name(m, class);
 	seq_puts(m, "\n");
 
-	list_for_each_entry(entry, &class->locks_after, entry) {
+	list_for_each_entry(entry, &class->locks_after, lock_order_entry) {
 		if (entry->distance == 1) {
 			seq_printf(m, " -> [%p] ", entry->class->key);
 			print_name(m, entry->class);
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#25 lore raw

PATCH 22/27 locking/lockdep: Reuse list entries that are no longer in use

In reply to Bart Van Assche

Instead of abandoning elements of list_entries[] that are no longer in use, make alloc_list_entry() reuse array elements that have been freed.

---
 include/linux/lockdep.h  |  5 +++++
 kernel/locking/lockdep.c | 23 ++++++++++++++++-------
 2 files changed, 21 insertions(+), 7 deletions(-)
include/linux/lockdep.h +5 -0
index 43327a1dd488..01e55fca7c2c 100644
@@ -183,6 +183,11 @@ static inline void lockdep_copy_map(struct lockdep_map *to,
 struct lock_list {
 	/* Entry in locks_after or locks_before. */
 	struct list_head		lock_order_entry;
+	/*
+	 * Entry in all_list_entries when in use and entry in
+	 * free_list_entries when not in use.
+	 */
+	struct list_head		alloc_entry;
 	struct lock_class		*class;
 	struct lock_class		*links_to;
 	struct stack_trace		trace;
kernel/locking/lockdep.c +16 -7
index 038377d67410..288a2f6fd0ef 100644
@@ -130,6 +130,8 @@ static inline int debug_locks_off_graph_unlock(void)
 
 unsigned long nr_list_entries;
 static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
+static LIST_HEAD(all_list_entries);
+static LIST_HEAD(free_list_entries);
 
 /*
  * All data structures here are protected by the global debug_lock.
@@ -743,6 +745,9 @@ static void init_lists(void)
 		INIT_LIST_HEAD(&lock_classes[i].locks_after);
 		INIT_LIST_HEAD(&lock_classes[i].locks_before);
 	}
+
+	for (i = 0; i < ARRAY_SIZE(list_entries); i++)
+		list_add_tail(&list_entries[i].alloc_entry, &free_list_entries);
 }
 
 /*
@@ -862,7 +867,10 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
  */
 static struct lock_list *alloc_list_entry(void)
 {
-	if (nr_list_entries >= MAX_LOCKDEP_ENTRIES) {
+	struct lock_list *e = list_first_entry_or_null(&free_list_entries,
+						       typeof(*e), alloc_entry);
+
+	if (!e) {
 		if (!debug_locks_off_graph_unlock())
 			return NULL;
 
@@ -870,7 +878,8 @@ static struct lock_list *alloc_list_entry(void)
 		dump_stack();
 		return NULL;
 	}
-	return list_entries + nr_list_entries++;
+	list_move_tail(&e->alloc_entry, &all_list_entries);
+	return e;
 }
 
 /*
@@ -975,7 +984,7 @@ static inline void mark_lock_accessed(struct lock_list *lock,
 	unsigned long nr;
 
 	nr = lock - list_entries;
-	WARN_ON(nr >= nr_list_entries); /* Out-of-bounds, input fail */
+	WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
 	lock->parent = parent;
 	lock->class->dep_gen_id = lockdep_dependency_gen_id;
 }
@@ -985,7 +994,7 @@ static inline unsigned long lock_accessed(struct lock_list *lock)
 	unsigned long nr;
 
 	nr = lock - list_entries;
-	WARN_ON(nr >= nr_list_entries); /* Out-of-bounds, input fail */
+	WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
 	return lock->class->dep_gen_id == lockdep_dependency_gen_id;
 }
 
@@ -4235,19 +4244,19 @@ static void zap_class(struct list_head *zapped_classes,
 		      struct lock_class *class)
 {
 	struct lock_class *links_to;
-	struct lock_list *entry;
-	int i;
+	struct lock_list *entry, *tmp;
 
 	/*
 	 * Remove all dependencies this lock is
 	 * involved in:
 	 */
-	for (i = 0, entry = list_entries; i < nr_list_entries; i++, entry++) {
+	list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {
 		if (entry->class != class && entry->links_to != class)
 			continue;
 		links_to = entry->links_to;
 		WARN_ON_ONCE(entry->class == links_to);
 		list_del_rcu(&entry->lock_order_entry);
+		list_move(&entry->alloc_entry, &free_list_entries);
 		entry->class = NULL;
 		entry->links_to = NULL;
 		check_free_class(zapped_classes, class);
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
maintainer
#26 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 55 lines · Bart Van Assche

Instead of abandoning elements of list_entries[] that are no longer in use, make alloc_list_entry() reuse array elements that have been freed.

include/linux/lockdep.h +14 -2
index 43327a1dd488..01e55fca7c2c 100644
@@ -183,6 +183,11 @@ static inline void lockdep_copy_map(struct lockdep_map *to,
 struct lock_list {
 	/* Entry in locks_after or locks_before. */
 	struct list_head		lock_order_entry;
+	/*
+	 * Entry in all_list_entries when in use and entry in
+	 * free_list_entries when not in use.
+	 */
+	struct list_head		alloc_entry;
 	struct lock_class		*class;
 	struct lock_class		*links_to;
 	struct stack_trace		trace;
 
+static LIST_HEAD(all_list_entries);
+static LIST_HEAD(free_list_entries);
@@ -862,7 +867,10 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
  */
 static struct lock_list *alloc_list_entry(void)
 {
-	if (nr_list_entries >= MAX_LOCKDEP_ENTRIES) {
+	struct lock_list *e = list_first_entry_or_null(&free_list_entries,
+						       typeof(*e), alloc_entry);
+
+	if (!e) {
 		if (!debug_locks_off_graph_unlock())
 			return NULL;
 
@@ -870,7 +878,8 @@ static struct lock_list *alloc_list_entry(void)
 		dump_stack();
 		return NULL;
 	}
-	return list_entries + nr_list_entries++;
+	list_move_tail(&e->alloc_entry, &all_list_entries);
+	return e;
 }
 
@@ -4235,19 +4244,19 @@ static void zap_class(struct list_head *zapped_classes,
 		      struct lock_class *class)
 {
 	struct lock_class *links_to;
+	struct lock_list *entry, *tmp;
 
 	/*
 	 * Remove all dependencies this lock is
 	 * involved in:
 	 */

include/linux/lockdep.h static void zap_class(struct list_head *zapped_classes, · line 4262

Quoted 10 lines
include/linux/lockdep.h +2 -0
+	list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {
 		if (entry->class != class && entry->links_to != class)
 			continue;
 		links_to = entry->links_to;
 		WARN_ON_ONCE(entry->class == links_to);
 		list_del_rcu(&entry->lock_order_entry);
+		list_move(&entry->alloc_entry, &free_list_entries);
 		entry->class = NULL;
 		entry->links_to = NULL;
 		check_free_class(zapped_classes, class);

Hurm.. I'm confused here.

The reason you cannot re-use lock_order_entry for the free list is because list_del_rcu(), right? But if so, then what ensures the list_entry is not re-used before it's grace-period?

maintainer
#27 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 69 lines · Peter Zijlstra
Quoted 55 lines · Bart Van Assche

Instead of abandoning elements of list_entries[] that are no longer in use, make alloc_list_entry() reuse array elements that have been freed.

include/linux/lockdep.h +14 -2
index 43327a1dd488..01e55fca7c2c 100644
@@ -183,6 +183,11 @@ static inline void lockdep_copy_map(struct lockdep_map *to,
 struct lock_list {
 	/* Entry in locks_after or locks_before. */
 	struct list_head		lock_order_entry;
+	/*
+	 * Entry in all_list_entries when in use and entry in
+	 * free_list_entries when not in use.
+	 */
+	struct list_head		alloc_entry;
 	struct lock_class		*class;
 	struct lock_class		*links_to;
 	struct stack_trace		trace;
 
+static LIST_HEAD(all_list_entries);
+static LIST_HEAD(free_list_entries);
@@ -862,7 +867,10 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
  */
 static struct lock_list *alloc_list_entry(void)
 {
-	if (nr_list_entries >= MAX_LOCKDEP_ENTRIES) {
+	struct lock_list *e = list_first_entry_or_null(&free_list_entries,
+						       typeof(*e), alloc_entry);
+
+	if (!e) {
 		if (!debug_locks_off_graph_unlock())
 			return NULL;
 
@@ -870,7 +878,8 @@ static struct lock_list *alloc_list_entry(void)
 		dump_stack();
 		return NULL;
 	}
-	return list_entries + nr_list_entries++;
+	list_move_tail(&e->alloc_entry, &all_list_entries);
+	return e;
 }
 
@@ -4235,19 +4244,19 @@ static void zap_class(struct list_head *zapped_classes,
 		      struct lock_class *class)
 {
 	struct lock_class *links_to;
+	struct lock_list *entry, *tmp;
 
 	/*
 	 * Remove all dependencies this lock is
 	 * involved in:
 	 */

include/linux/lockdep.h static void zap_class(struct list_head *zapped_classes, · line 4262

Quoted 10 lines
include/linux/lockdep.h +2 -0
+	list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {
 		if (entry->class != class && entry->links_to != class)
 			continue;
 		links_to = entry->links_to;
 		WARN_ON_ONCE(entry->class == links_to);
 		list_del_rcu(&entry->lock_order_entry);
+		list_move(&entry->alloc_entry, &free_list_entries);
 		entry->class = NULL;
 		entry->links_to = NULL;
 		check_free_class(zapped_classes, class);

Hurm.. I'm confused here.

Quoted 3 lines

The reason you cannot re-use lock_order_entry for the free list is because list_del_rcu(), right? But if so, then what ensures the list_entry is not re-used before it's grace-period?

Also; if you have to grow lock_list by 16 bytes just to be able to free it, a bitmap allocator is much cheaper, space wise.

Some people seem to really care about the static image size, and lockdep's .data section does matter to them.

#28 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Peter Zijlstra
Quoted 5 lines · Bart Van Assche
	/*>>> 	 *Remove all dependencies this lock is
	 *involved in:
	 */
+-	list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {>>> 		if (entry->class !=class &&entry->links_to !=class)
			continue;>>> 		links_to =entry->links_to;>>> 		WARN_ON_ONCE(entry->class ==links_to);>>> 		list_del_rcu(&entry->lock_order_entry);>>>+-		list_move(&entry->alloc_entry, &free_list_entries);>>> 		entry->class =NULL;>>> 		entry->links_to =NULL;>>> 		check_free_class(zapped_classes, class);>>

Hurm.. I'm confused here.

The reason you cannot re-use lock_order_entry for the free list is because list_del_rcu(), right? But if so, then what ensures the list_entry is not re-used before it's grace-period?

Quoted 5 lines

Also;if you have to grow lock_list by 16 bytes just to be able to free it, a bitmap allocator is much cheaper, space wise.

Some people seem to really care about the static image size, and lockdep's .data section does matter to them.

How about addressing this by moving removed list entries to a "zapped_entries"list and only moving list entries from the zapped_entries list to the free_list_entries list after an RCU grace period? I'm not sure that it is
possible to implement that approach without introducing a new list_head in
struct lock_list.

Thanks,

Bart.

maintainer
#29 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 27 lines · Bart Van Assche
Quoted 26 lines · Peter Zijlstra
Quoted 18 lines · Peter Zijlstra
Quoted 4 lines · Bart Van Assche
kernel/locking/lockdep.c +0 -0
 	/*
 	 * Remove all dependencies this lock is
 	 * involved in:
 	 */

kernel/locking/lockdep.c static void zap_class(struct list_head *zapped_classes, · line 4262

Quoted 10 lines
kernel/locking/lockdep.c +2 -0
+	list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {
 		if (entry->class != class && entry->links_to != class)
 			continue;
 		links_to = entry->links_to;
 		WARN_ON_ONCE(entry->class == links_to);
 		list_del_rcu(&entry->lock_order_entry);
+		list_move(&entry->alloc_entry, &free_list_entries);
 		entry->class = NULL;
 		entry->links_to = NULL;
 		check_free_class(zapped_classes, class);

Hurm.. I'm confused here.

Quoted 3 lines

The reason you cannot re-use lock_order_entry for the free list is because list_del_rcu(), right? But if so, then what ensures the list_entry is not re-used before it's grace-period?

Also; if you have to grow lock_list by 16 bytes just to be able to free it, a bitmap allocator is much cheaper, space wise.

Quoted 8 lines
Quoted 2 lines

Some people seem to really care about the static image size, and lockdep's .data section does matter to them.

How about addressing this by moving removed list entries to a "zapped_entries" list and only moving list entries from the zapped_entries list to the free_list_entries list after an RCU grace period? I'm not sure that it is possible to implement that approach without introducing a new list_head in struct lock_list.

I think we can do this with a free bitmap and an array of 2 pending bitmaps and an index. Add newly freed entries to the pending bitmap indicated by the current index, when complete flip the index -- such that further new bits go to the other pending bitmap -- and call_rcu().

Then, on the call_rcu() callback, ie. after a GP has happened, OR our pending bitmap into the free bitmap, and when the other pending bitmap isn't empty, flip the index again and start it all again.

This ensures there is at least one full GP between setting a bit and it landing in the free mask.

#30 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 31 lines · Peter Zijlstra
Quoted 17 lines · Bart Van Assche
Quoted 16 lines · Peter Zijlstra
Quoted 11 lines · Peter Zijlstra
Quoted 5 lines · Bart Van Assche
	/*>>>>> 	 *Remove all dependencies this lock is
	 *involved in:
	 */
+-	list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {>>>>> 		if (entry->class !=class &&entry->links_to !=class)
			continue;>>>>> 		links_to =entry->links_to;>>>>> 		WARN_ON_ONCE(entry->class ==links_to);>>>>> 		list_del_rcu(&entry->lock_order_entry);>>>>>+-		list_move(&entry->alloc_entry, &free_list_entries);>>>>> 		entry->class =NULL;>>>>> 		entry->links_to =NULL;>>>>> 		check_free_class(zapped_classes, class);>>>>

Hurm.. I'm confused here.

The reason you cannot re-use lock_order_entry for the free list is because list_del_rcu(), right? But if so, then what ensures the list_entry is not re-used before it's grace-period?

Also;if you have to grow lock_list by 16 bytes just to be able to free it, a bitmap allocator is much cheaper, space wise.

Quoted 7 lines
Quoted 2 lines

Some people seem to really care about the static image size, and lockdep's .data section does matter to them.

How about addressing this by moving removed list entries to a "zapped_entries">>list and only moving list entries from the zapped_entries list to the free_list_entries list after an RCU grace period? I'm not sure that it is
possible to implement that approach without introducing a new list_head in
struct lock_list.

I think we can do this with a free bitmap and an array of 2 pending bitmaps and an index. Add newly freed entries to the pending bitmap indicated by the current index, when complete flip the index -- such that further new bits go to the other pending bitmap -- and call_rcu().

Quoted 6 lines

Then, on the call_rcu() callback, ie. after a GP has happened, OR our pending bitmap into the free bitmap, and when the other pending bitmap isn't empty, flip the index again and start it all again.

This ensures there is at least one full GP between setting a bit and it landing in the free mask.

Hi Peter,

How about the following alternative which requires only two bitmaps instead of three:
- Maintain two bitmaps, one for the free entries and one for the entries that are being freed.
- Protect all accesses to both bitmaps with the graph lock.
- zap_class() sets a bit in the "being freed"bitmap for the entries that should be freed after a GP.
- Instead of making free_zapped_classes() wait for a grace period by calling synchronize_sched(), use call_rcu() and do the freeing work from inside the RCU callback.
- From inside the RCU callback, set a bit in the "free"bitmap for all entries that have a bit set in the "being freed"bitmap and clears the "being freed" bitmap.

Thanks,

Bart.

maintainer
#31 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 14 lines · Bart Van Assche
Quoted 11 lines

I think we can do this with a free bitmap and an array of 2 pending bitmaps and an index. Add newly freed entries to the pending bitmap indicated by the current index, when complete flip the index -- such that further new bits go to the other pending bitmap -- and call_rcu().

Then, on the call_rcu() callback, ie. after a GP has happened, OR our pending bitmap into the free bitmap, and when the other pending bitmap isn't empty, flip the index again and start it all again.

This ensures there is at least one full GP between setting a bit and it landing in the free mask.

Hi Peter,

Quoted 14 lines

How about the following alternative which requires only two bitmaps instead of three:
- Maintain two bitmaps, one for the free entries and one for the entries that are being freed.
- Protect all accesses to both bitmaps with the graph lock.
- zap_class() sets a bit in the "being freed" bitmap for the entries that should be freed after a GP.
- Instead of making free_zapped_classes() wait for a grace period by calling synchronize_sched(), use call_rcu() and do the freeing work from inside the RCU callback.
- From inside the RCU callback, set a bit in the "free" bitmap for all entries that have a bit set in the "being freed" bitmap and clears the "being freed" bitmap.

What happens when another unreg happens while the rcu_call thing is still pending?

#32 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 29 lines · Peter Zijlstra
Quoted 14 lines · Bart Van Assche
Quoted 11 lines

I think we can do this with a free bitmap and an array of 2 pending bitmaps and an index. Add newly freed entries to the pending bitmap indicated by the current index, when complete flip the index -- such that further new bits go to the other pending bitmap -- and call_rcu().

Then, on the call_rcu() callback, ie. after a GP has happened, OR our pending bitmap into the free bitmap, and when the other pending bitmap isn't empty, flip the index again and start it all again.

This ensures there is at least one full GP between setting a bit and it landing in the free mask.

Hi Peter,

Quoted 12 lines

How about the following alternative which requires only two bitmaps instead of three:
- Maintain two bitmaps, one for the free entries and one for the entries that are being freed.
- Protect all accesses to both bitmaps with the graph lock.
- zap_class() sets a bit in the "being freed"bitmap for the entries that should be freed after a GP.
- Instead of making free_zapped_classes() wait for a grace period by calling synchronize_sched(), use call_rcu() and do the freeing work from inside the RCU callback.
- From inside the RCU callback, set a bit in the "free"bitmap for all entries that have a bit set in the "being freed"bitmap and clears the "being freed">> bitmap.

Quoted 2 lines

What happens when another unreg happens while the rcu_call thing is still pending?

A new flag will have to keep track of whether or not an RCU callback has already been scheduled via rcu_call() but not yet executed to avoid double RCU call complaints. In other code a possible alternative would be to allocate the RCU head data structure dynamically. However, I don't think that alternative is appropriate inside the lockdep code - I don't want to introduce a circular dependency between the lockdep code and the memory allocator.

Bart.

maintainer
#33 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 31 lines · Bart Van Assche
Quoted 30 lines · Peter Zijlstra
Quoted 27 lines · Bart Van Assche
Quoted 11 lines

I think we can do this with a free bitmap and an array of 2 pending bitmaps and an index. Add newly freed entries to the pending bitmap indicated by the current index, when complete flip the index -- such that further new bits go to the other pending bitmap -- and call_rcu().

Then, on the call_rcu() callback, ie. after a GP has happened, OR our pending bitmap into the free bitmap, and when the other pending bitmap isn't empty, flip the index again and start it all again.

This ensures there is at least one full GP between setting a bit and it landing in the free mask.

Hi Peter,

How about the following alternative which requires only two bitmaps instead of three:
- Maintain two bitmaps, one for the free entries and one for the entries that are being freed.
- Protect all accesses to both bitmaps with the graph lock.
- zap_class() sets a bit in the "being freed" bitmap for the entries that should be freed after a GP.
- Instead of making free_zapped_classes() wait for a grace period by calling synchronize_sched(), use call_rcu() and do the freeing work from inside the RCU callback.
- From inside the RCU callback, set a bit in the "free" bitmap for all entries that have a bit set in the "being freed" bitmap and clears the "being freed" bitmap.

Quoted 6 lines
Quoted 2 lines

What happens when another unreg happens while the rcu_call thing is still pending?

A new flag will have to keep track of whether or not an RCU callback has already been scheduled via rcu_call() but not yet executed to avoid double RCU call complaints.

That's not the only problem there. You either then have to synchronously wait for that flag / rcu_call to complete, or, if you modify the bitmap, ensure it re-queues itself for another GP before committing, which is starvation prone.

Quoted 5 lines

In other code a possible alternative would be to
allocate the RCU head data structure dynamically. However, I don't think that alternative is appropriate inside the lockdep code - I don't want to introduce a circular dependency between the lockdep code and the memory allocator.

Yes, that's a trainwreck waiting to happen ;-)

#34 lore raw

Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Bart Van Assche
Quoted 16 lines · Peter Zijlstra
Quoted 4 lines · Bart Van Assche

How about the following alternative which requires only two bitmaps instead of three:
- Maintain two bitmaps, one for the free entries and one for the entries that are being freed.

Quoted 8 lines

- Protect all accesses to both bitmaps with the graph lock.
- zap_class() sets a bit in the "being freed"bitmap for the entries that should be freed after a GP.
- Instead of making free_zapped_classes() wait for a grace period by calling synchronize_sched(), use call_rcu() and do the freeing work from inside the RCU callback.
- From inside the RCU callback, set a bit in the "free"bitmap for all entries that have a bit set in the "being freed"bitmap and clears the "being freed">>>> bitmap.

What happens when another unreg happens while the rcu_call thing is still pending?

Quoted 7 lines
Quoted 4 lines

A new flag will have to keep track of whether or not an RCU callback has already been scheduled via rcu_call() but not yet executed to avoid double RCU call complaints.
That's not the only problem there. You either then have to synchronously

wait for that flag / rcu_call to complete, or, if you modify the bitmap, ensure it re-queues itself for another GP before committing, which is starvation prone.

Can you have a look at free_zapped_classes() and schedule_free_zapped_classes() in v2 of this patch series? In v2 the call_rcu(), manipulation of the boolean and processing of the bitmaps are all protected by the graph
lock to avoid the issues that you described. See also
*[PATCH v2 17/24]locking/lockdep: Free lock classes that are no longer in use
(https://lore.kernel.org/lkml/[email protected]/).
*[PATCH v2 18/24]locking/lockdep: Reuse list entries that are no longer in use
(https://lore.kernel.org/lkml/[email protected]/).

Thanks,

Bart.

#35 lore raw

PATCH 23/27 locking/lockdep: Check data structure consistency

In reply to Bart Van Assche

Debugging lockdep data structure inconsistencies is challenging. Add disabled code that verifies data structure consistency at runtime.

---
 kernel/locking/lockdep.c | 142 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 142 insertions(+)
kernel/locking/lockdep.c +142 -0
index 288a2f6fd0ef..141bb0662ff5 100644
@@ -72,6 +72,8 @@ module_param(lock_stat, int, 0644);
 #define lock_stat 0
 #endif
 
+static bool check_data_structure_consistency;
+
 /*
  * lockdep_lock: protects the lockdep graph, the hashes and the
  *               class/list/hash allocators.
@@ -736,6 +738,135 @@ static bool assign_lock_key(struct lockdep_map *lock)
 	return true;
 }
 
+/* Check whether element @e occurs in list @h */
+static bool in_list(struct list_head *e, struct list_head *h)
+{
+	struct list_head *f;
+
+	list_for_each(f, h)
+		if (e == f)
+			return true;
+
+	return false;
+}
+
+/*
+ * Check whether entry @e occurs in any of the locks_after or locks_before
+ * lists.
+ */
+static bool in_any_class_list(struct list_head *e)
+{
+	struct lock_class *class;
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+		class = &lock_classes[i];
+		if (in_list(e, &class->locks_after) ||
+		    in_list(e, &class->locks_before))
+			return true;
+	}
+	return false;
+}
+
+static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
+{
+	struct lock_list *e;
+
+	list_for_each_entry(e, h, lock_order_entry) {
+		if (e->links_to != c) {
+			printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
+			       c->name ? : "(?)", e - list_entries,
+			       e->links_to && e->links_to->name ?
+			       e->links_to->name : "(?)",
+			       e->class && e->class->name ? e->class->name :
+			       "(?)");
+			return false;
+		}
+	}
+	return true;
+}
+
+static u16 chain_hlocks[];
+
+static bool check_lock_chain_key(struct lock_chain *chain)
+{
+	u64 chain_key = 0;
+	int i;
+
+	for (i = chain->base; i < chain->base + chain->depth; i++)
+		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+	/*
+	 * The 'unsigned long long' casts avoid that a compiler warning
+	 * is reported when building tools/lib/lockdep.
+	 */
+	if (chain->chain_key != chain_key)
+		printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
+		       (unsigned long long)(chain - lock_chains),
+		       (unsigned long long)chain->chain_key,
+		       (unsigned long long)chain_key);
+	return chain->chain_key == chain_key;
+}
+
+static bool check_data_structures(void)
+{
+	struct lock_class *class;
+	struct lock_chain *chain;
+	struct hlist_head *head;
+	struct lock_list *e;
+	int i;
+
+	/*
+	 * Check whether all list entries that are in use occur in a class
+	 * lock list.
+	 */
+	list_for_each_entry(e, &all_list_entries, alloc_entry) {
+		if (!in_any_class_list(&e->lock_order_entry)) {
+			printk(KERN_INFO "list entry %ld is not in any class list; class %s <> %s\n",
+			       e - list_entries,
+			       e->class->name ? : "(?)",
+			       e->links_to->name ? : "(?)");
+			return false;
+		}
+	}
+
+	/*
+	 * Check whether all list entries that are not in use do not occur in
+	 * a class lock list.
+	 */
+	list_for_each_entry(e, &free_list_entries, alloc_entry) {
+		if (in_any_class_list(&e->lock_order_entry)) {
+			printk(KERN_INFO "list entry %ld occurs in a class list; class %s <> %s\n",
+			       e - list_entries,
+			       e->class && e->class->name ? e->class->name :
+			       "(?)",
+			       e->links_to && e->links_to->name ?
+			       e->links_to->name : "(?)");
+			return false;
+		}
+	}
+
+	/* Check whether all classes have valid lock lists. */
+	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+		class = &lock_classes[i];
+		if (!class->locks_before.next)
+			continue;
+		if (!class_lock_list_valid(class, &class->locks_before))
+			return false;
+		if (!class_lock_list_valid(class, &class->locks_after))
+			return false;
+	}
+
+	/* Check the chain_key of all lock chains. */
+	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
+		head = chainhash_table + i;
+		hlist_for_each_entry_rcu(chain, head, entry)
+			if (!check_lock_chain_key(chain))
+				return false;
+	}
+
+	return true;
+}
+
 static void init_lists(void)
 {
 	int i;
@@ -4294,6 +4425,14 @@ static void free_zapped_classes(struct list_head *zapped_classes)
 	unsigned long flags;
 	int locked;
 
+	raw_local_irq_save(flags);
+	locked = graph_lock();
+	if (check_data_structure_consistency)
+		WARN_ON_ONCE(!check_data_structures());
+	if (locked)
+		graph_unlock();
+	raw_local_irq_restore(flags);
+
 	if (list_empty(zapped_classes))
 		return;
 
@@ -4314,6 +4453,9 @@ static void free_zapped_classes(struct list_head *zapped_classes)
 	if (locked)
 		graph_unlock();
 	raw_local_irq_restore(flags);
+
+	if (check_data_structure_consistency)
+		WARN_ON_ONCE(!check_data_structures());
 }
 
 /*
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
maintainer
#36 lore raw

Re: [PATCH 23/27] locking/lockdep: Check data structure consistency

kernel/locking/lockdep.c static bool assign_lock_key(struct lockdep_map *lock) · line 748

Quoted 7 lines · Bart Van Assche
kernel/locking/lockdep.c +7 -0
+static bool in_list(struct list_head *e, struct list_head *h)
+{
+	struct list_head *f;
+
+	list_for_each(f, h)
+		if (e == f)
+			return true;

Coding style wants { } around any multi line block, even if C doesn't strictly require it.

Quoted 10 lines
kernel/locking/lockdep.c +9 -0
+
+	return false;
+}
 
+static bool check_lock_chain_key(struct lock_chain *chain)
+{
+	u64 chain_key = 0;
+	int i;
+
+	for (i = chain->base; i < chain->base + chain->depth; i++)

kernel/locking/lockdep.c static bool assign_lock_key(struct lockdep_map *lock) · line 806

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+	/*
+	 * The 'unsigned long long' casts avoid that a compiler warning
+	 * is reported when building tools/lib/lockdep.
+	 */
+	if (chain->chain_key != chain_key)
+		printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
+		       (unsigned long long)(chain - lock_chains),
+		       (unsigned long long)chain->chain_key,
+		       (unsigned long long)chain_key);

Idem on the { }

Quoted 48 lines
kernel/locking/lockdep.c +48 -0
+	return chain->chain_key == chain_key;
+}
+
+static bool check_data_structures(void)
+{
+	struct lock_class *class;
+	struct lock_chain *chain;
+	struct hlist_head *head;
+	struct lock_list *e;
+	int i;
+
+	/*
+	 * Check whether all list entries that are in use occur in a class
+	 * lock list.
+	 */
+	list_for_each_entry(e, &all_list_entries, alloc_entry) {
+		if (!in_any_class_list(&e->lock_order_entry)) {
+			printk(KERN_INFO "list entry %ld is not in any class list; class %s <> %s\n",
+			       e - list_entries,
+			       e->class->name ? : "(?)",
+			       e->links_to->name ? : "(?)");
+			return false;
+		}
+	}
+
+	/*
+	 * Check whether all list entries that are not in use do not occur in
+	 * a class lock list.
+	 */
+	list_for_each_entry(e, &free_list_entries, alloc_entry) {
+		if (in_any_class_list(&e->lock_order_entry)) {
+			printk(KERN_INFO "list entry %ld occurs in a class list; class %s <> %s\n",
+			       e - list_entries,
+			       e->class && e->class->name ? e->class->name :
+			       "(?)",
+			       e->links_to && e->links_to->name ?
+			       e->links_to->name : "(?)");
+			return false;
+		}
+	}
+
+	/* Check whether all classes have valid lock lists. */
+	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+		class = &lock_classes[i];
+		if (!class->locks_before.next)
+			continue;
+		if (!class_lock_list_valid(class, &class->locks_before))
+			return false;

kernel/locking/lockdep.c static bool assign_lock_key(struct lockdep_map *lock) · line 864

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+		if (!class_lock_list_valid(class, &class->locks_after))
+			return false;
+	}
+
+	/* Check the chain_key of all lock chains. */
+	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
+		head = chainhash_table + i;
+		hlist_for_each_entry_rcu(chain, head, entry)
+			if (!check_lock_chain_key(chain))
+				return false;

And again.

kernel/locking/lockdep.c static bool assign_lock_key(struct lockdep_map *lock) · line 767

Quoted 4 lines
kernel/locking/lockdep.c +4 -0
+	}
+
+	return true;
+}

IIRC there were a few other sites in the series, please check them all.

#37 lore raw

Re: [PATCH 23/27] locking/lockdep: Check data structure consistency

Quoted 1 line · Peter Zijlstra

IIRC there were a few other sites in the series, please check them all.

OK, I will add braces around multi-line statement blocks. You may want to know that checkpatch didn't complain about missing braces.

Bart.

maintainer
#38 lore raw

Re: [PATCH 23/27] locking/lockdep: Check data structure consistency

Quoted 5 lines · Bart Van Assche
Quoted 1 line · Peter Zijlstra

IIRC there were a few other sites in the series, please check them all.

OK, I will add braces around multi-line statement blocks. You may want to know that checkpatch didn't complain about missing braces.

Yeah, checkpatch is far from perfect. I think this recently got documented somewhere though. Lets see if I can find that.

https://lkml.kernel.org/r/[email protected]

Not sure what the status of that all is, but there goes.

#39 lore raw

PATCH 24/27 locking/lockdep: Introduce __lockdep_free_key_range()

In reply to Bart Van Assche

This patch does not change any functionality but makes the next patch in this series easier to read.

---
 kernel/locking/lockdep.c | 35 +++++++++++++++++++++++------------
 1 file changed, 23 insertions(+), 12 deletions(-)
kernel/locking/lockdep.c +23 -12
index 141bb0662ff5..0e273731d028 100644
@@ -4459,18 +4459,16 @@ static void free_zapped_classes(struct list_head *zapped_classes)
 }
 
 /*
- * Used in module.c to remove lock classes from memory that is going to be
- * freed; and possibly re-used by other modules.
- *
- * We will have had one sync_sched() before getting here, so we're guaranteed
- * nobody will look up these exact classes -- they're properly dead but still
- * allocated.
+ * Remove all lock classes from the class hash table and from the
+ * all_lock_classes list whose key or name is in the address range
+ * [start, start + size). Move these lock classes to the
+ * @zapped_classes list.
  */
-void lockdep_free_key_range(void *start, unsigned long size)
+static void __lockdep_free_key_range(struct list_head *zapped_classes,
+				     void *start, unsigned long size)
 {
 	struct lock_class *class;
 	struct hlist_head *head;
-	LIST_HEAD(zapped_classes);
 	unsigned long flags;
 	int i;
 	int locked;
@@ -4478,9 +4476,8 @@ void lockdep_free_key_range(void *start, unsigned long size)
 	raw_local_irq_save(flags);
 	locked = graph_lock();
 
-	/*
-	 * Unhash all classes that were created by this module:
-	 */
+	INIT_LIST_HEAD(zapped_classes);
+
 	for (i = 0; i < CLASSHASH_SIZE; i++) {
 		head = classhash_table + i;
 		hlist_for_each_entry_rcu(class, head, hash_entry) {
@@ -4488,14 +4485,28 @@ void lockdep_free_key_range(void *start, unsigned long size)
 			    (!within(class->key, start, size) &&
 			     !within(class->name, start, size)))
 				continue;
-			zap_class(&zapped_classes, class);
+			zap_class(zapped_classes, class);
 		}
 	}
 
 	if (locked)
 		graph_unlock();
 	raw_local_irq_restore(flags);
+}
+
+/*
+ * Used in module.c to remove lock classes from memory that is going to be
+ * freed; and possibly re-used by other modules.
+ *
+ * We will have had one sync_sched() before getting here, so we're guaranteed
+ * nobody will look up these exact classes -- they're properly dead but still
+ * allocated.
+ */
+void lockdep_free_key_range(void *start, unsigned long size)
+{
+	LIST_HEAD(zapped_classes);
 
+	__lockdep_free_key_range(&zapped_classes, start, size);
 	free_zapped_classes(&zapped_classes);
 }
 
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
maintainer
#40 lore raw

Re: [PATCH 24/27] locking/lockdep: Introduce __lockdep_free_key_range()

Quoted 2 lines · Bart Van Assche

This patch does not change any functionality but makes the next patch in this series easier to read.

Ooh, I completely forgot about commit:

35a9393c95b3 ("lockdep: Fix the module unload key range freeing logic")

I was still thinking that all was broken... yes, I think I see where you're going.

#41 lore raw

PATCH 25/27 locking/lockdep: Add support for dynamic keys

In reply to Bart Van Assche

A shortcoming of the current lockdep implementation is that it requires lock keys to be allocated statically. That forces certain lock objects to share lock keys. Since lock dependency analysis groups lock objects per key sharing lock keys can cause false positive lockdep reports. Make it possible to avoid such false positive reports by allowing lock keys to be allocated dynamically. Require that dynamically allocated lock keys are registered before use by calling lockdep_register_key(). Complain about attempts to register the same lock key pointer twice without calling lockdep_unregister_key() between successive registration calls.

---
 include/linux/lockdep.h  |  13 ++++-
 kernel/locking/lockdep.c | 121 ++++++++++++++++++++++++++++++++++++---
 2 files changed, 123 insertions(+), 11 deletions(-)
include/linux/lockdep.h +10 -3
index 01e55fca7c2c..bd6bfad66382 100644
@@ -46,15 +46,19 @@ extern int lock_stat;
 #define NR_LOCKDEP_CACHING_CLASSES	2
 
 /*
- * Lock-classes are keyed via unique addresses, by embedding the
- * lockclass-key into the kernel (or module) .data section. (For
- * static locks we use the lock address itself as the key.)
+ * A lockdep key is associated with each lock object. For static locks we use
+ * the lock address itself as the key. Dynamically allocated lock objects can
+ * have a statically or dynamically allocated key. Dynamically allocated lock
+ * keys must be registered before being used and must be unregistered before
+ * the key memory is freed.
  */
 struct lockdep_subclass_key {
 	char __one_byte;
 } __attribute__ ((__packed__));
 
+/* hash_entry is used to keep track of dynamically allocated keys. */
 struct lock_class_key {
+	struct hlist_node		hash_entry;
 	struct lockdep_subclass_key	subkeys[MAX_LOCKDEP_SUBCLASSES];
 };
 
@@ -280,6 +284,9 @@ extern asmlinkage void lockdep_sys_exit(void);
 extern void lockdep_off(void);
 extern void lockdep_on(void);
 
+extern void lockdep_register_key(struct lock_class_key *key);
+extern void lockdep_unregister_key(struct lock_class_key *key);
+
 /*
  * These methods are used by specific locking variants (spinlocks,
  * rwlocks, mutexes and rwsems) to pass init/acquire/release events
kernel/locking/lockdep.c +113 -8

158 lines not on this page · raw message

Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
maintainer
#42 lore raw

include/linux/lockdep.h extern int lock_stat; · line 63

Quoted 5 lines · Bart Van Assche
include/linux/lockdep.h +2 -0
+/* hash_entry is used to keep track of dynamically allocated keys. */
 struct lock_class_key {
+	struct hlist_node		hash_entry;
 	struct lockdep_subclass_key	subkeys[MAX_LOCKDEP_SUBCLASSES];
 };

One consideration; and maybe we should have a BUILD_BUG for that, is that this object should be no larger than the smallest lock primitive.

That typically is raw_spinlock_t, which normally is 4 bytes, but with lockdep on that at least also includes struct lockdep_map.

So what we want is:

sizeof(lock_class_key) <= sizeof(raw_spinlock_t)

Otherwise, two consecutive spinlocks could end up with key overlap in their subclass range.

Now, I think that is still valid after this patch, but it is something that gave me pause.

#43 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 2 lines · Bart Van Assche

+-/*hash_entry is used to keep track of dynamically allocated keys. */
struct lock_class_key {>>+- struct hlist_node hash_entry;>> struct lockdep_subclass_key subkeys[MAX_LOCKDEP_SUBCLASSES];>> };>

One consideration;and maybe we should have a BUILD_BUG for that, is that this object should be no larger than the smallest lock primitive.

That typically is raw_spinlock_t, which normally is 4 bytes, but with lockdep on that at least also includes struct lockdep_map.

So what we want is:

Quoted 7 lines

sizeof(lock_class_key) <=sizeof(raw_spinlock_t)

Otherwise, two consecutive spinlocks could end up with key overlap in their subclass range.

Now, I think that is still valid after this patch, but it is something that gave me pause.

How about adding this as an additional patch before patch 25/27?

kernel/locking/lockdep.c +0 -0
index 9a7cca6dc3d4..ce05b9b419f4 100644

--- a/kernel/locking/lockdep.c
+-+-+- b/kernel/locking/lockdep.c
@@-725,6 +-725,15 @@static bool assign_lock_key(struct lockdep_map *lock)
{ unsigned long can_addr, addr =(unsigned long)lock;

+-	/*+-	 *lockdep_free_key_range() assumes that struct lock_class_key
+-	 *objects do not overlap. Since we use the address of lock
+-	 *objects as class key for static objects, check whether the
+-	 *size of lock_class_key objects does not exceed the size of
+-	 *the smallest lock object.
+-	 */
+-	BUILD_BUG_ON(sizeof(struct lock_class_key) >sizeof(raw_spinlock_t));+-

if (__is_kernel_percpu_address(addr, &can_addr))
lock->key =(void *can_addr; else if (__is_module_percpu_address(addr, &can_addr))

Thanks,

Bart.

maintainer
#44 lore raw
Quoted 1 line · Bart Van Assche

How about adding this as an additional patch before patch 25/27?

Excellent, thanks!

Quoted 24 lines
kernel/locking/lockdep.c +9 -0
index 9a7cca6dc3d4..ce05b9b419f4 100644
@@ -725,6 +725,15 @@ static bool assign_lock_key(struct lockdep_map *lock)
 {
 	unsigned long can_addr, addr = (unsigned long)lock;
 
+	/*
+	 * lockdep_free_key_range() assumes that struct lock_class_key
+	 * objects do not overlap. Since we use the address of lock
+	 * objects as class key for static objects, check whether the
+	 * size of lock_class_key objects does not exceed the size of
+	 * the smallest lock object.
+	 */
+	BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t));
+
 	if (__is_kernel_percpu_address(addr, &can_addr))
 		lock->key = (void *)can_addr;
 	else if (__is_module_percpu_address(addr, &can_addr))

Thanks,

Bart.

maintainer
#45 lore raw
In reply to Bart Van Assche
Quoted 12 lines · Bart Van Assche

A shortcoming of the current lockdep implementation is that it requires lock keys to be allocated statically. That forces certain lock objects to share lock keys. Since lock dependency analysis groups lock objects per key sharing lock keys can cause false positive lockdep reports. Make it possible to avoid such false positive reports by allowing lock keys to be allocated dynamically. Require that dynamically allocated lock keys are registered before use by calling lockdep_register_key(). Complain about attempts to register the same lock key pointer twice without calling lockdep_unregister_key() between successive registration calls.

struct lock_class_key {

include/linux/lockdep.h extern int lock_stat; · line 63

Quoted 3 lines
include/linux/lockdep.h +1 -0
+	struct hlist_node		hash_entry;
 	struct lockdep_subclass_key	subkeys[MAX_LOCKDEP_SUBCLASSES];
 };

That hash_entry is purely for that double-register warning, right? I wonder if we can do that differently; by always doing register_lock_class(), and checking that state.

#46 lore raw
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Bart Van Assche

A shortcoming of the current lockdep implementation is that it requires lock keys to be allocated statically. That forces certain lock objects to share lock keys. Since lock dependency analysis groups lock objects per key sharing lock keys can cause false positive lockdep reports. Make it possible to avoid such false positive reports by allowing lock keys to be allocated dynamically. Require that dynamically allocated lock keys are registered before use by calling lockdep_register_key(). Complain about attempts to register the same lock key pointer twice without calling lockdep_unregister_key() between successive registration calls.
struct lock_class_key {>>+- struct hlist_node hash_entry;>> struct lockdep_subclass_key subkeys[MAX_LOCKDEP_SUBCLASSES];>> };>

Quoted 3 lines

That hash_entry is purely for that double-register warning, right? I wonder if we can do that differently;by always doing register_lock_class(), and checking that state.

Hi Peter,

The hash_entry serves two purposes. One purpose is to verify whether the lockdep_register_key() and lockdep_unregister_key() functions are used correctly. A second purpose is to avoid that lockdep_init_map() complains when encountering a dynamically allocated key. I'm not sure how always doing register_lock_class() would help?

Thanks,

Bart.

#47 lore raw

PATCH 26/27 kernel/workqueue: Use dynamic lockdep keys for workqueues

In reply to Bart Van Assche

Commit 87915adc3f0a ("workqueue: re-add lockdep dependencies for flushing") improved deadlock checking in the workqueue implementation. Unfortunately that patch also introduced a few false positive lockdep complaints. This patch suppresses these false positives by allocating the workqueue mutex lockdep key dynamically. An example of a false positive lockdep complaint suppressed by this report can be found below. The root cause of the lockdep complaint shown below is that the direct I/O code can call alloc_workqueue() from inside a work item created by another alloc_workqueue() call and that both workqueues share the same lockdep key. This patch avoids that that lockdep complaint is triggered by allocating the work queue lockdep keys dynamically. In other words, this patch guarantees that a unique lockdep key is associated with each work queue mutex.

======================================================
WARNING: possible circular locking dependency detected
4.19.0-dbg+ #1 Not tainted
------------------------------------------------------
fio/4129 is trying to acquire lock:
00000000a01cfe1a ((wq_completion)"dio/%s"sb->s_id){+.+.}, at: flush_workqueue+0xd0/0x970

but task is already holding lock:
00000000a0acecf9 (&sb->s_type->i_mutex_key#14){+.+.}, at: ext4_file_write_iter+0x154/0x710

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (&sb->s_type->i_mutex_key#14){+.+.}:

       down_write+0x3d/0x80
       __generic_file_fsync+0x77/0xf0
       ext4_sync_file+0x3c9/0x780
       vfs_fsync_range+0x66/0x100
       dio_complete+0x2f5/0x360
       dio_aio_complete_work+0x1c/0x20
       process_one_work+0x481/0x9f0
       worker_thread+0x63/0x5a0
       kthread+0x1cf/0x1f0
       ret_from_fork+0x24/0x30

-> #1 ((work_completion)(&dio->complete_work)){+.+.}:

       process_one_work+0x447/0x9f0
       worker_thread+0x63/0x5a0
       kthread+0x1cf/0x1f0
       ret_from_fork+0x24/0x30

-> #0 ((wq_completion)"dio/%s"sb->s_id){+.+.}:

       lock_acquire+0xc5/0x200
       flush_workqueue+0xf3/0x970
       drain_workqueue+0xec/0x220
       destroy_workqueue+0x23/0x350
       sb_init_dio_done_wq+0x6a/0x80
       do_blockdev_direct_IO+0x1f33/0x4be0
       __blockdev_direct_IO+0x79/0x86
       ext4_direct_IO+0x5df/0xbb0
       generic_file_direct_write+0x119/0x220
       __generic_file_write_iter+0x131/0x2d0
       ext4_file_write_iter+0x3fa/0x710
       aio_write+0x235/0x330
       io_submit_one+0x510/0xeb0
       __x64_sys_io_submit+0x122/0x340
       do_syscall_64+0x71/0x220
       entry_SYSCALL_64_after_hwframe+0x49/0xbe

other info that might help us debug this:

Chain exists of:
  (wq_completion)"dio/%s"sb->s_id --> (work_completion)(&dio->complete_work) --> &sb->s_type->i_mutex_key#14

 Possible unsafe locking scenario:
       CPU0                    CPU1
       ----                    ----
  lock(&sb->s_type->i_mutex_key#14);
                               lock((work_completion)(&dio->complete_work));
                               lock(&sb->s_type->i_mutex_key#14);

lock((wq_completion)"dio/%s"sb->s_id);

*** DEADLOCK ***

1 lock held by fio/4129:
#0: 00000000a0acecf9 (&sb->s_type->i_mutex_key#14){+.+.}, at: ext4_file_write_iter+0x154/0x710

stack backtrace:
CPU: 3 PID: 4129 Comm: fio Not tainted 4.19.0-dbg+ #1
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.10.2-1 04/01/2014
Call Trace:
 dump_stack+0x86/0xc5
 print_circular_bug.isra.32+0x20a/0x218
 __lock_acquire+0x1c68/0x1cf0
 lock_acquire+0xc5/0x200
 flush_workqueue+0xf3/0x970
 drain_workqueue+0xec/0x220
 destroy_workqueue+0x23/0x350
 sb_init_dio_done_wq+0x6a/0x80
 do_blockdev_direct_IO+0x1f33/0x4be0
 __blockdev_direct_IO+0x79/0x86
 ext4_direct_IO+0x5df/0xbb0
 generic_file_direct_write+0x119/0x220
 __generic_file_write_iter+0x131/0x2d0
 ext4_file_write_iter+0x3fa/0x710
 aio_write+0x235/0x330
 io_submit_one+0x510/0xeb0
 __x64_sys_io_submit+0x122/0x340
 do_syscall_64+0x71/0x220
 entry_SYSCALL_64_after_hwframe+0x49/0xbe
Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Will Deacon <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Johannes Berg <[email protected]>
---
 include/linux/workqueue.h | 28 +++---------------
 kernel/workqueue.c        | 60 +++++++++++++++++++++++++++++++++------
 2 files changed, 55 insertions(+), 33 deletions(-)
include/linux/workqueue.h +4 -24
index 60d673e15632..d9a1a480e920 100644
@@ -390,43 +390,23 @@ extern struct workqueue_struct *system_freezable_wq;
 extern struct workqueue_struct *system_power_efficient_wq;
 extern struct workqueue_struct *system_freezable_power_efficient_wq;
 
-extern struct workqueue_struct *
-__alloc_workqueue_key(const char *fmt, unsigned int flags, int max_active,
-	struct lock_class_key *key, const char *lock_name, ...) __printf(1, 6);
-
 /**
  * alloc_workqueue - allocate a workqueue
  * @fmt: printf format for the name of the workqueue
  * @flags: WQ_* flags
  * @max_active: max in-flight work items, 0 for default
- * @args...: args for @fmt
+ * remaining args: args for @fmt
  *
  * Allocate a workqueue with the specified parameters.  For detailed
  * information on WQ_* flags, please refer to
  * Documentation/core-api/workqueue.rst.
  *
- * The __lock_name macro dance is to guarantee that single lock_class_key
- * doesn't end up with different namesm, which isn't allowed by lockdep.
- *
  * RETURNS:
  * Pointer to the allocated workqueue on success, %NULL on failure.
  */
-#ifdef CONFIG_LOCKDEP
-#define alloc_workqueue(fmt, flags, max_active, args...)		\
-({									\
-	static struct lock_class_key __key;				\
-	const char *__lock_name;					\
-									\
-	__lock_name = "(wq_completion)"#fmt#args;			\
-									\
-	__alloc_workqueue_key((fmt), (flags), (max_active),		\
-			      &__key, __lock_name, ##args);		\
-})
-#else
-#define alloc_workqueue(fmt, flags, max_active, args...)		\
-	__alloc_workqueue_key((fmt), (flags), (max_active),		\
-			      NULL, NULL, ##args)
-#endif
+struct workqueue_struct *alloc_workqueue(const char *fmt,
+					 unsigned int flags,
+					 int max_active, ...);
 
 /**
  * alloc_ordered_workqueue - allocate an ordered workqueue
kernel/workqueue.c +51 -9

114 lines not on this page · raw message

Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
#48 lore raw

PATCH 27/27 lockdep tests: Test dynamic key registration

In reply to Bart Van Assche

Make sure that the lockdep_register_key() and lockdep_unregister_key() code is tested when running the lockdep tests.

---
 tools/lib/lockdep/include/liblockdep/common.h |  2 ++
 tools/lib/lockdep/include/liblockdep/mutex.h  | 11 ++++++-----
 tools/lib/lockdep/tests/ABBA.c                |  9 +++++++++
 3 files changed, 17 insertions(+), 5 deletions(-)
tools/lib/lockdep/include/liblockdep/common.h +2 -0
index d640a9761f09..a81d91d4fc78 100644
@@ -45,6 +45,8 @@ void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 void lock_release(struct lockdep_map *lock, int nested,
 			unsigned long ip);
 void lockdep_reset_lock(struct lockdep_map *lock);
+void lockdep_register_key(struct lock_class_key *key);
+void lockdep_unregister_key(struct lock_class_key *key);
 extern void debug_check_no_locks_freed(const void *from, unsigned long len);
 
 #define STATIC_LOCKDEP_MAP_INIT(_name, _key) \
tools/lib/lockdep/include/liblockdep/mutex.h +6 -5
index 2073d4e1f2f0..783dd0df06f9 100644
@@ -7,6 +7,7 @@
 
 struct liblockdep_pthread_mutex {
 	pthread_mutex_t mutex;
+	struct lock_class_key key;
 	struct lockdep_map dep_map;
 };
 
@@ -27,11 +28,10 @@ static inline int __mutex_init(liblockdep_pthread_mutex_t *lock,
 	return pthread_mutex_init(&lock->mutex, __mutexattr);
 }
 
-#define liblockdep_pthread_mutex_init(mutex, mutexattr)		\
-({								\
-	static struct lock_class_key __key;			\
-								\
-	__mutex_init((mutex), #mutex, &__key, (mutexattr));	\
+#define liblockdep_pthread_mutex_init(mutex, mutexattr)			\
+({									\
+	lockdep_register_key(&(mutex)->key);				\
+	__mutex_init((mutex), #mutex, &(mutex)->key, (mutexattr));	\
 })
 
 static inline int liblockdep_pthread_mutex_lock(liblockdep_pthread_mutex_t *lock)
@@ -55,6 +55,7 @@ static inline int liblockdep_pthread_mutex_trylock(liblockdep_pthread_mutex_t *l
 static inline int liblockdep_pthread_mutex_destroy(liblockdep_pthread_mutex_t *lock)
 {
 	lockdep_reset_lock(&lock->dep_map);
+	lockdep_unregister_key(&lock->key);
 	return pthread_mutex_destroy(&lock->mutex);
 }
 
tools/lib/lockdep/tests/ABBA.c +9 -0
index 623313f54720..543789bc3e37 100644
@@ -14,4 +14,13 @@ void main(void)
 
 	pthread_mutex_destroy(&b);
 	pthread_mutex_destroy(&a);
+
+	pthread_mutex_init(&a, NULL);
+	pthread_mutex_init(&b, NULL);
+
+	LOCK_UNLOCK_2(a, b);
+	LOCK_UNLOCK_2(b, a);
+
+	pthread_mutex_destroy(&b);
+	pthread_mutex_destroy(&a);
 }
Signature · 1 line
2.20.0.rc0.387.gc7a69e6b6c-goog
maintainer
#49 lore raw
In reply to Bart Van Assche
Quoted 10 lines · Bart Van Assche

Hi Ingo and Peter,

A known shortcoming of the current lockdep implementation is that it requires lock keys to be allocated statically and that this key sharing can cause false positive deadlock reports. This patch series adds support for dynamic keys in the lockdep code. I'm not claiming that this patch series is perfect. However, the code in this patch series survives nontrivial tests so I think it's worth a look. Two unrelated changes in this patch series are:
- Improve the lockdep tests.
- Complain if no name has been assigned to a lock object.

Looks very good mostly, and it improves the lives of people that like modules too.

Thanks for doing all that.