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

Groups > linux.kernel > #1600116 > unrolled thread

[PATCH v6 00/15] lockdep: Implement crossrelease feature

Back to article view | Back to linux.kernel

Contents

  [PATCH v6 00/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-03-14 09:30 +0100
    [PATCH v6 02/15] lockdep: Add a function building a chain between two classes Byungchul Park <byungchul.park@lge.com> - 2017-03-14 09:30 +0100
    [PATCH v6 13/15] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked Byungchul Park <byungchul.park@lge.com> - 2017-03-14 09:30 +0100
    [PATCH v6 07/15] lockdep: Avoid adding redundant direct links of crosslocks Byungchul Park <byungchul.park@lge.com> - 2017-03-14 09:30 +0100

#1600116 — [PATCH v6 00/15] lockdep: Implement crossrelease feature

I checked if crossrelease feature works well on my qemu-i386 machine.
There's no problem at all to work on mine. But I wonder if it's still
true on other machines. Especially, on large system. Could you let me
know if it doesn't work on yours or if crossrelease feature is useful?

-----8<-----

Change from v5
	- force XHLOCKS_SIZE to be power of 2 and simplify code
	- remove nmi check
	- separate an optimization using prev_gen_id with a full changelog
	- separate non(multi)-acquisition handling with a full changelog
	- replace vmalloc with kmallock(GFP_KERNEL) for xhlocks
	- select PROVE_LOCKING when choosing CROSSRELEASE
	- clean serveral code (e.g. loose some ifdefferies)
	- enhance several comments and changelogs

Change from v4
	- rebase on vanilla v4.9 tag
	- re-name pend_lock(plock) to hist_lock(xhlock)
	- allow overwriting ring buffer for hist_lock
	- unwind ring buffer instead of tagging id for each irq
	- introduce lockdep_map_cross embedding cross_lock
	- make each work of workqueue distinguishable
	- enhance comments
	(I will update the document at the next spin.)

Change from v3
	- reviced document

Change from v2
	- rebase on vanilla v4.7 tag
	- move lockdep data for page lock from struct page to page_ext
	- allocate plocks buffer via vmalloc instead of in struct task
	- enhanced comments and document
	- optimize performance
	- make reporting function crossrelease-aware

Change from v1
	- enhanced the document
	- removed save_stack_trace() optimizing patch
	- made this based on the seperated save_stack_trace patchset
	  https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1182242.html

Can we detect deadlocks below with original lockdep?

Example 1)

	PROCESS X	PROCESS Y
	--------------	--------------
	mutext_lock A
			lock_page B
	lock_page B
			mutext_lock A // DEADLOCK
	unlock_page B
			mutext_unlock A
	mutex_unlock A
			unlock_page B

where A and B are different lock classes.

No, we cannot.

Example 2)

	PROCESS X	PROCESS Y	PROCESS Z
	--------------	--------------	--------------
			mutex_lock A
	lock_page B
			lock_page B
					mutext_lock A // DEADLOCK
					mutext_unlock A
					unlock_page B
					(B was held by PROCESS X)
			unlock_page B
			mutex_unlock A

where A and B are different lock classes.

No, we cannot.

Example 3)

	PROCESS X	PROCESS Y
	--------------	--------------
			mutex_lock A
	mutex_lock A
			wait_for_complete B // DEADLOCK
	mutex_unlock A
	complete B
			mutex_unlock A

where A is a lock class and B is a completion variable.

No, we cannot.

Not only lock operations, but also any operations causing to wait or
spin for something can cause deadlock unless it's eventually *released*
by someone. The important point here is that the waiting or spinning
must be *released* by someone.

Using crossrelease feature, we can check dependency and detect deadlock
possibility not only for typical lock, but also for lock_page(),
wait_for_xxx() and so on, which might be released in any context.

See the last patch including the document for more information.

Byungchul Park (15):
  lockdep: Refactor lookup_chain_cache()
  lockdep: Add a function building a chain between two classes
  lockdep: Change the meaning of check_prev_add()'s return value
  lockdep: Make check_prev_add() able to handle external stack_trace
  lockdep: Implement crossrelease feature
  lockdep: Handle non(or multi)-acquisition of a crosslock
  lockdep: Avoid adding redundant direct links of crosslocks
  lockdep: Fix incorrect condition to print bug msgs for
    MAX_LOCKDEP_CHAIN_HLOCKS
  lockdep: Make print_circular_bug() aware of crossrelease
  lockdep: Apply crossrelease to completions
  pagemap.h: Remove trailing white space
  lockdep: Apply crossrelease to PG_locked locks
  lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked
  lockdep: Move data of CONFIG_LOCKDEP_PAGELOCK from page to page_ext
  lockdep: Crossrelease feature documentation

 Documentation/locking/crossrelease.txt | 874 +++++++++++++++++++++++++++++++++
 include/linux/completion.h             | 118 ++++-
 include/linux/irqflags.h               |  24 +-
 include/linux/lockdep.h                | 147 +++++-
 include/linux/mm_types.h               |   4 +
 include/linux/page-flags.h             |  43 +-
 include/linux/page_ext.h               |   4 +
 include/linux/pagemap.h                | 125 ++++-
 include/linux/sched.h                  |   8 +
 kernel/exit.c                          |   1 +
 kernel/fork.c                          |   3 +
 kernel/locking/lockdep.c               | 789 +++++++++++++++++++++++++----
 kernel/sched/completion.c              |  54 +-
 kernel/workqueue.c                     |   1 +
 lib/Kconfig.debug                      |  29 ++
 mm/filemap.c                           |  73 ++-
 mm/page_ext.c                          |   4 +
 17 files changed, 2149 insertions(+), 152 deletions(-)
 create mode 100644 Documentation/locking/crossrelease.txt

-- 
1.9.1

[toc] | [next] | [standalone]

#1600117 — [PATCH v6 02/15] lockdep: Add a function building a chain between two classes

Crossrelease needs to build a chain between two classes regardless of
their contexts. However, add_chain_cache() cannot be used for that
purpose since it assumes that it's called in the acquisition context
of the hlock. So this patch introduces a new function doing it.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/lockdep.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 0c6e6b7..eb39474 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2110,6 +2110,76 @@ static int check_no_collision(struct task_struct *curr,
 }
 
 /*
+ * This is for building a chain between just two different classes,
+ * instead of adding a new hlock upon current, which is done by
+ * add_chain_cache().
+ *
+ * This can be called in any context with two classes, while
+ * add_chain_cache() must be done within the lock owener's context
+ * since it uses hlock which might be racy in another context.
+ */
+static inline int add_chain_cache_classes(unsigned int prev,
+					  unsigned int next,
+					  unsigned int irq_context,
+					  u64 chain_key)
+{
+	struct hlist_head *hash_head = chainhashentry(chain_key);
+	struct lock_chain *chain;
+
+	/*
+	 * Allocate a new chain entry from the static array, and add
+	 * it to the hash:
+	 */
+
+	/*
+	 * We might need to take the graph lock, ensure we've got IRQs
+	 * disabled to make this an IRQ-safe lock.. for recursion reasons
+	 * lockdep won't complain about its own locking errors.
+	 */
+	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
+		return 0;
+
+	if (unlikely(nr_lock_chains >= MAX_LOCKDEP_CHAINS)) {
+		if (!debug_locks_off_graph_unlock())
+			return 0;
+
+		print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
+		dump_stack();
+		return 0;
+	}
+
+	chain = lock_chains + nr_lock_chains++;
+	chain->chain_key = chain_key;
+	chain->irq_context = irq_context;
+	chain->depth = 2;
+	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
+		chain->base = nr_chain_hlocks;
+		nr_chain_hlocks += chain->depth;
+		chain_hlocks[chain->base] = prev - 1;
+		chain_hlocks[chain->base + 1] = next -1;
+	}
+#ifdef CONFIG_DEBUG_LOCKDEP
+	/*
+	 * Important for check_no_collision().
+	 */
+	else {
+		if (!debug_locks_off_graph_unlock())
+			return 0;
+
+		print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
+		dump_stack();
+		return 0;
+	}
+#endif
+
+	hlist_add_head_rcu(&chain->entry, hash_head);
+	debug_atomic_inc(chain_lookup_misses);
+	inc_chains();
+
+	return 1;
+}
+
+/*
  * Adds a dependency chain into chain hashtable. And must be called with
  * graph_lock held.
  *
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1600118 — [PATCH v6 13/15] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked

Usually PG_locked bit is updated by lock_page() or unlock_page().
However, it can be also updated through __SetPageLocked() or
__ClearPageLockded(). They have to be considered, to get paired between
acquire and release.

Furthermore, e.g. __SetPageLocked() in add_to_page_cache_lru() is called
frequently. We might miss many chances to check deadlock if we ignore it.
Make __Set(__Clear)PageLockded considered as well.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/page-flags.h | 30 +++++++++++++++++++++++++++++-
 1 file changed, 29 insertions(+), 1 deletion(-)

diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h
index 74e4dda..9d5f79d 100644
--- a/include/linux/page-flags.h
+++ b/include/linux/page-flags.h
@@ -252,7 +252,6 @@ static __always_inline int PageCompound(struct page *page)
 #define TESTSCFLAG_FALSE(uname)						\
 	TESTSETFLAG_FALSE(uname) TESTCLEARFLAG_FALSE(uname)
 
-__PAGEFLAG(Locked, locked, PF_NO_TAIL)
 PAGEFLAG(Error, error, PF_NO_COMPOUND) TESTCLEARFLAG(Error, error, PF_NO_COMPOUND)
 PAGEFLAG(Referenced, referenced, PF_HEAD)
 	TESTCLEARFLAG(Referenced, referenced, PF_HEAD)
@@ -354,6 +353,35 @@ static __always_inline int PageCompound(struct page *page)
 PAGEFLAG(Idle, idle, PF_ANY)
 #endif
 
+#ifdef CONFIG_LOCKDEP_PAGELOCK
+#include <linux/lockdep.h>
+
+TESTPAGEFLAG(Locked, locked, PF_NO_TAIL)
+
+static __always_inline void __SetPageLocked(struct page *page)
+{
+	__set_bit(PG_locked, &PF_NO_TAIL(page, 1)->flags);
+
+	page = compound_head(page);
+	lock_acquire_exclusive((struct lockdep_map *)&page->map, 0, 1, NULL, _RET_IP_);
+}
+
+static __always_inline void __ClearPageLocked(struct page *page)
+{
+	__clear_bit(PG_locked, &PF_NO_TAIL(page, 1)->flags);
+
+	page = compound_head(page);
+	/*
+	 * lock_commit_crosslock() is necessary for crosslock
+	 * when the lock is released, before lock_release().
+	 */
+	lock_commit_crosslock((struct lockdep_map *)&page->map);
+	lock_release((struct lockdep_map *)&page->map, 0, _RET_IP_);
+}
+#else
+__PAGEFLAG(Locked, locked, PF_NO_TAIL)
+#endif
+
 /*
  * On an anonymous page mapped into a user virtual memory area,
  * page->mapping points to its anon_vma, not to a struct address_space;
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1600119 — [PATCH v6 07/15] lockdep: Avoid adding redundant direct links of crosslocks

On my machine (QEMU x86_64, 4 core, mem 512M, enable-kvm), this patch
does not make different between before/after in lockdep_stats. So this
patch looks unnecessary. However, I wonder if it's still true in other
systems. Could anybody check lockdep_stats in your system?

Before (apply all crossrelease patches except this patch):

 lock-classes:                          988 [max: 8191]
 direct dependencies:                  5814 [max: 32768]
 indirect dependencies:               18915
 all direct dependencies:            119802
 dependency chains:                    6350 [max: 65536]
 dependency chain hlocks:             20771 [max: 327680]
 in-hardirq chains:                      52
 in-softirq chains:                     361
 in-process chains:                    5937
 stack-trace entries:                 80396 [max: 524288]
 combined max dependencies:       113926468
 hardirq-safe locks:                     42
 hardirq-unsafe locks:                  644
 softirq-safe locks:                    129
 softirq-unsafe locks:                  561
 irq-safe locks:                        135
 irq-unsafe locks:                      644
 hardirq-read-safe locks:                 2
 hardirq-read-unsafe locks:             127
 softirq-read-safe locks:                11
 softirq-read-unsafe locks:             119
 irq-read-safe locks:                    12
 irq-read-unsafe locks:                 127
 uncategorized locks:                   165
 unused locks:                            1
 max locking depth:                      14
 max bfs queue depth:                   168
 debug_locks:                             1

After (apply all crossrelease patches without exception):

 lock-classes:                          980 [max: 8191]
 direct dependencies:                  5604 [max: 32768]
 indirect dependencies:               18517
 all direct dependencies:            112620
 dependency chains:                    6215 [max: 65536]
 dependency chain hlocks:             20401 [max: 327680]
 in-hardirq chains:                      51
 in-softirq chains:                     298
 in-process chains:                    5866
 stack-trace entries:                 78707 [max: 524288]
 combined max dependencies:        91220116
 hardirq-safe locks:                     42
 hardirq-unsafe locks:                  637
 softirq-safe locks:                    117
 softirq-unsafe locks:                  561
 irq-safe locks:                        126
 irq-unsafe locks:                      637
 hardirq-read-safe locks:                 2
 hardirq-read-unsafe locks:             127
 softirq-read-safe locks:                10
 softirq-read-unsafe locks:             119
 irq-read-safe locks:                    11
 irq-read-unsafe locks:                 127
 uncategorized locks:                   165
 unused locks:                            1
 max locking depth:                      15
 max bfs queue depth:                   168
 debug_locks:                             1

-----8<-----
From 803e905a4cbf6c10b776a9e272a3bda9e3ffaa95 Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park@lge.com>
Date: Tue, 14 Mar 2017 14:59:54 +0900
Subject: [PATCH v6 07/15] lockdep: Avoid adding redundant direct links of
 crosslocks

We can skip adding a dependency 'AX -> B', in case that we ensure 'AX ->
the previous of B in hlocks' to be created, where AX is a crosslock and
B is a typical lock. Remember that two adjacent locks in hlocks generate
a dependency like 'prev -> next', that is, 'the previous of B in hlocks
-> B' in this case.

For example:

             in hlocks[]
             ------------
          ^  A (gen_id: 4) --+
          |                  | previous gen_id
          |  B (gen_id: 3) <-+
          |  C (gen_id: 3)
          |  D (gen_id: 2)
   oldest |  E (gen_id: 1)

             in xhlocks[]
             ------------
          ^  A (gen_id: 4, prev_gen_id: 3(B's gen id))
          |  B (gen_id: 3, prev_gen_id: 3(C's gen id))
          |  C (gen_id: 3, prev_gen_id: 2(D's gen id))
          |  D (gen_id: 2, prev_gen_id: 1(E's gen id))
   oldest |  E (gen_id: 1, prev_gen_id: NA)

On commit for a crosslock AX(gen_id = 3), it's engough to add 'AX -> C',
but adding 'AX -> B' and 'AX -> A' is unnecessary since 'AX -> C', 'C ->
B' and 'B -> A' cover them, which are guaranteed to be generated.

This patch intoduces a variable, prev_gen_id, to avoid adding this kind
of redundant dependencies. In other words, the previous in hlocks will
anyway handle it if the previous's gen_id >= the crosslock's gen_id.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/lockdep.h  | 11 +++++++++++
 kernel/locking/lockdep.c | 30 ++++++++++++++++++++++++++++--
 2 files changed, 39 insertions(+), 2 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 5356f71..31c6289 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,6 +284,17 @@ struct held_lock {
  */
 struct hist_lock {
 	/*
+	 * We can skip adding a dependency 'a target crosslock -> this
+	 * lock', in case that we ensure 'the target crosslock -> the
+	 * previous lock in held_locks' to be created. Remember that
+	 * 'the previous lock in held_locks -> this lock' is guaranteed
+	 * to be created, and 'A -> B' and 'B -> C' cover 'A -> C'.
+	 *
+	 * Keep the previous's gen_id to make the decision.
+	 */
+	unsigned int		prev_gen_id;
+
+	/*
 	 * Each work of workqueue might run in a different context,
 	 * thanks to concurrency support of workqueue. So we have to
 	 * distinguish each work to avoid false positive.
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index ec4f6af..c78dd9d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4716,13 +4716,18 @@ static inline int xhlock_used(struct hist_lock *xhlock)
 /*
  * Only access local task's data, so irq disable is only required.
  */
-static void add_xhlock(struct held_lock *hlock)
+static void add_xhlock(struct held_lock *hlock, unsigned int prev_gen_id)
 {
 	unsigned int idx = current->xhlock_idx++;
 	struct hist_lock *xhlock = &xhlock(idx);
 
 	/* Initialize hist_lock's members */
 	xhlock->hlock = *hlock;
+	/*
+	 * prev_gen_id is used to skip adding redundant dependencies,
+	 * which can be covered by the previous lock in held_locks.
+	 */
+	xhlock->prev_gen_id = prev_gen_id;
 	xhlock->work_id = current->work_id;
 
 	xhlock->trace.nr_entries = 0;
@@ -4761,10 +4766,30 @@ static int same_context_xhlock(struct hist_lock *xhlock)
  */
 static void check_add_xhlock(struct held_lock *hlock)
 {
+	struct held_lock *prev;
+	struct held_lock *start;
+	unsigned int gen_id;
+	unsigned int gen_id_invalid;
+
 	if (!current->xhlocks || !depend_before(hlock))
 		return;
 
-	add_xhlock(hlock);
+	gen_id = (unsigned int)atomic_read(&cross_gen_id);
+	/*
+	 * gen_id_invalid should be old enough to be invalid.
+	 * Current gen_id - (UINIT_MAX / 4) would be a good
+	 * value to meet it.
+	 */
+	gen_id_invalid = gen_id - (UINT_MAX / 4);
+	start = current->held_locks;
+
+	for (prev = hlock - 1; prev >= start &&
+			!depend_before(prev); prev--);
+
+	if (prev < start)
+		add_xhlock(hlock, gen_id_invalid);
+	else if (prev->gen_id != gen_id)
+		add_xhlock(hlock, prev->gen_id);
 }
 
 /*
@@ -4902,6 +4927,7 @@ static int commit_xhlocks(struct cross_lock *xlock)
 				break;
 
 			if (same_context_xhlock(xhlock) &&
+			    before(xhlock->prev_gen_id, xlock->hlock.gen_id) &&
 			    !commit_xhlock(xlock, xhlock))
 				return 0;
 		}
-- 
1.9.1

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web