linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v3 00/21] DEPT(Dependency Tracker)
@ 2022-02-28  9:56 Byungchul Park
  2022-02-28  9:56 ` [PATCH v3 01/21] llist: Move llist_{head,node} definition to types.h Byungchul Park
                   ` (21 more replies)
  0 siblings, 22 replies; 30+ messages in thread
From: Byungchul Park @ 2022-02-28  9:56 UTC (permalink / raw)
  To: torvalds
  Cc: damien.lemoal, linux-ide, adilger.kernel, linux-ext4, mingo,
	linux-kernel, peterz, will, tglx, rostedt, joel, sashal,
	daniel.vetter, chris, duyuyang, johannes.berg, tj, tytso, willy,
	david, amir73il, bfields, gregkh, kernel-team, linux-mm, akpm,
	mhocko, minchan, hannes, vdavydov.dev, sj, jglisse, dennis, cl,
	penberg, rientjes, vbabka, ngupta, linux-block, paolo.valente,
	josef, linux-fsdevel, viro, jack, jack, jlayton, dan.j.williams,
	hch, djwong, dri-devel, airlied, rodrigosiqueiramelo,
	melissa.srw, hamohammed.sa

I didn't want to bother you so I was planning to send the next spin
after making more progress. However, PATCH v2 reports too many false
positives because Dept tracked the bit_wait_table[] wrong way - I
apologize for that. So I decided to send PATCH v3 first before going
further for those who want to run Dept for now.

There might still be some false positives but not overwhelming.

---

Hi Linus and folks,

I've been developing a tool for detecting deadlock possibilities by
tracking wait/event rather than lock(?) acquisition order to try to
cover all synchonization machanisms. It's done on v5.17-rc1 tag.

https://github.com/lgebyungchulpark/linux-dept/commits/dept1.14_on_v5.17-rc1

Benifit:

	0. Works with all lock primitives.
	1. Works with wait_for_completion()/complete().
	2. Works with 'wait' on PG_locked.
	3. Works with 'wait' on PG_writeback.
	4. Works with swait/wakeup.
	5. Works with waitqueue.
	6. Multiple reports are allowed.
	7. Deduplication control on multiple reports.
	8. Withstand false positives thanks to 6.
	9. Easy to tag any wait/event.

Future work:

	0. To make it more stable.
	1. To separates Dept from Lockdep.
	2. To improves performance in terms of time and space.
	3. To use Dept as a dependency engine for Lockdep.
	4. To add any missing tags of wait/event in the kernel.
	5. To deduplicate stack trace.

How to interpret reports:

	1. E(event) in each context cannot be triggered because of the
	   W(wait) that cannot be woken.
	2. The stack trace helping find the problematic code is located
	   in each conext's detail.

Thanks,
Byungchul

---

Changes from v2:

	1. Disable Dept on bit_wait_table[] in sched/wait_bit.c
	   reporting a lot of false positives, which is my fault.
	   Wait/event for bit_wait_table[] should've been tagged in a
	   higher layer for better work, which is a future work.
	   (feedback from Jan Kara)
	2. Disable Dept on crypto_larval's completion to prevent a false
	   positive.

Changes from v1:

	1. Fix coding style and typo. (feedback from Steven)
	2. Distinguish each work context from another in workqueue.
	3. Skip checking lock acquisition with nest_lock, which is about
	   correct lock usage that should be checked by Lockdep.

Changes from RFC:

	1. Prevent adding a wait tag at prepare_to_wait() but __schedule().
	   (feedback from Linus and Matthew)
	2. Use try version at lockdep_acquire_cpus_lock() annotation.
	3. Distinguish each syscall context from another.

Byungchul Park (21):
  llist: Move llist_{head,node} definition to types.h
  dept: Implement Dept(Dependency Tracker)
  dept: Embed Dept data in Lockdep
  dept: Add a API for skipping dependency check temporarily
  dept: Apply Dept to spinlock
  dept: Apply Dept to mutex families
  dept: Apply Dept to rwlock
  dept: Apply Dept to wait_for_completion()/complete()
  dept: Apply Dept to seqlock
  dept: Apply Dept to rwsem
  dept: Add proc knobs to show stats and dependency graph
  dept: Introduce split map concept and new APIs for them
  dept: Apply Dept to wait/event of PG_{locked,writeback}
  dept: Apply SDT to swait
  dept: Apply SDT to wait(waitqueue)
  locking/lockdep, cpu/hotplus: Use a weaker annotation in AP thread
  dept: Distinguish each syscall context from another
  dept: Distinguish each work from another
  dept: Disable Dept within the wait_bit layer by default
  dept: Add nocheck version of init_completion()
  dept: Disable Dept on struct crypto_larval's completion for now

 crypto/api.c                       |    7 +-
 include/linux/completion.h         |   50 +-
 include/linux/dept.h               |  535 +++++++
 include/linux/dept_page.h          |   78 ++
 include/linux/dept_sdt.h           |   62 +
 include/linux/hardirq.h            |    3 +
 include/linux/irqflags.h           |   33 +-
 include/linux/llist.h              |    8 -
 include/linux/lockdep.h            |  158 ++-
 include/linux/lockdep_types.h      |    3 +
 include/linux/mutex.h              |   33 +
 include/linux/page-flags.h         |   45 +-
 include/linux/pagemap.h            |    7 +-
 include/linux/percpu-rwsem.h       |   10 +-
 include/linux/rtmutex.h            |    7 +
 include/linux/rwlock.h             |   52 +
 include/linux/rwlock_api_smp.h     |    8 +-
 include/linux/rwlock_types.h       |    7 +
 include/linux/rwsem.h              |   33 +
 include/linux/sched.h              |    7 +
 include/linux/seqlock.h            |   59 +-
 include/linux/spinlock.h           |   26 +
 include/linux/spinlock_types_raw.h |   13 +
 include/linux/swait.h              |    4 +
 include/linux/types.h              |    8 +
 include/linux/wait.h               |    6 +-
 init/init_task.c                   |    2 +
 init/main.c                        |    4 +
 kernel/Makefile                    |    1 +
 kernel/cpu.c                       |    2 +-
 kernel/dependency/Makefile         |    4 +
 kernel/dependency/dept.c           | 2712 ++++++++++++++++++++++++++++++++++++
 kernel/dependency/dept_hash.h      |   10 +
 kernel/dependency/dept_internal.h  |   26 +
 kernel/dependency/dept_object.h    |   13 +
 kernel/dependency/dept_proc.c      |   92 ++
 kernel/entry/common.c              |    3 +
 kernel/exit.c                      |    1 +
 kernel/fork.c                      |    2 +
 kernel/locking/lockdep.c           |   12 +-
 kernel/module.c                    |    2 +
 kernel/sched/completion.c          |   12 +-
 kernel/sched/core.c                |    3 +
 kernel/sched/swait.c               |   10 +
 kernel/sched/wait.c                |   16 +
 kernel/sched/wait_bit.c            |    5 +-
 kernel/softirq.c                   |    6 +-
 kernel/trace/trace_preemptirq.c    |   19 +-
 kernel/workqueue.c                 |    3 +
 lib/Kconfig.debug                  |   21 +
 mm/filemap.c                       |   68 +
 mm/page_ext.c                      |    5 +
 52 files changed, 4257 insertions(+), 59 deletions(-)
 create mode 100644 include/linux/dept.h
 create mode 100644 include/linux/dept_page.h
 create mode 100644 include/linux/dept_sdt.h
 create mode 100644 kernel/dependency/Makefile
 create mode 100644 kernel/dependency/dept.c
 create mode 100644 kernel/dependency/dept_hash.h
 create mode 100644 kernel/dependency/dept_internal.h
 create mode 100644 kernel/dependency/dept_object.h
 create mode 100644 kernel/dependency/dept_proc.c

-- 
1.9.1


^ permalink raw reply	[flat|nested] 30+ messages in thread

end of thread, other threads:[~2022-03-04  0:28 UTC | newest]

Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-02-28  9:56 [PATCH v3 00/21] DEPT(Dependency Tracker) Byungchul Park
2022-02-28  9:56 ` [PATCH v3 01/21] llist: Move llist_{head,node} definition to types.h Byungchul Park
2022-02-28  9:56 ` [PATCH v3 02/21] dept: Implement Dept(Dependency Tracker) Byungchul Park
2022-02-28  9:56 ` [PATCH v3 03/21] dept: Embed Dept data in Lockdep Byungchul Park
2022-02-28  9:56 ` [PATCH v3 04/21] dept: Add a API for skipping dependency check temporarily Byungchul Park
2022-02-28  9:56 ` [PATCH v3 05/21] dept: Apply Dept to spinlock Byungchul Park
2022-02-28  9:56 ` [PATCH v3 06/21] dept: Apply Dept to mutex families Byungchul Park
2022-02-28  9:56 ` [PATCH v3 07/21] dept: Apply Dept to rwlock Byungchul Park
2022-02-28  9:56 ` [PATCH v3 08/21] dept: Apply Dept to wait_for_completion()/complete() Byungchul Park
2022-02-28  9:56 ` [PATCH v3 09/21] dept: Apply Dept to seqlock Byungchul Park
2022-02-28  9:56 ` [PATCH v3 10/21] dept: Apply Dept to rwsem Byungchul Park
2022-02-28  9:56 ` [PATCH v3 11/21] dept: Add proc knobs to show stats and dependency graph Byungchul Park
2022-02-28  9:56 ` [PATCH v3 12/21] dept: Introduce split map concept and new APIs for them Byungchul Park
2022-02-28  9:56 ` [PATCH v3 13/21] dept: Apply Dept to wait/event of PG_{locked,writeback} Byungchul Park
2022-02-28  9:56 ` [PATCH v3 14/21] dept: Apply SDT to swait Byungchul Park
2022-02-28  9:56 ` [PATCH v3 15/21] dept: Apply SDT to wait(waitqueue) Byungchul Park
2022-02-28  9:56 ` [PATCH v3 16/21] locking/lockdep, cpu/hotplus: Use a weaker annotation in AP thread Byungchul Park
2022-02-28  9:56 ` [PATCH v3 17/21] dept: Distinguish each syscall context from another Byungchul Park
2022-02-28  9:56 ` [PATCH v3 18/21] dept: Distinguish each work " Byungchul Park
2022-02-28  9:56 ` [PATCH v3 19/21] dept: Disable Dept within the wait_bit layer by default Byungchul Park
2022-02-28  9:56 ` [PATCH v3 20/21] dept: Add nocheck version of init_completion() Byungchul Park
2022-02-28  9:57 ` [PATCH v3 21/21] dept: Disable Dept on struct crypto_larval's completion for now Byungchul Park
2022-03-02  4:36 ` [PATCH v3 00/21] DEPT(Dependency Tracker) Hyeonggon Yoo
2022-03-02  4:53   ` Hyeonggon Yoo
2022-03-03  0:18     ` Byungchul Park
2022-03-03  8:03       ` Hyeonggon Yoo
2022-03-03  9:48         ` Byungchul Park
2022-03-03 12:38           ` Hyeonggon Yoo
2022-03-04  0:28             ` Byungchul Park
2022-03-03  2:22   ` Byungchul Park

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