linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC 00/14] DEPT(DEPendency Tracker)
@ 2022-01-25  2:36 Byungchul Park
  2022-01-25  2:36 ` [RFC 01/14] llist: Move llist_{head,node} definition to types.h Byungchul Park
                   ` (15 more replies)
  0 siblings, 16 replies; 31+ messages in thread
From: Byungchul Park @ 2022-01-25  2:36 UTC (permalink / raw)
  To: torvalds, mingo, linux-kernel
  Cc: peterz, will, tglx, rostedt, joel, sashal, daniel.vetter, chris,
	duyuyang, johannes.berg, tj, tytso, willy, david, amir73il,
	bfields, gregkh, kernel-team

Hi forks,

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.10 tag. I bet
it would work great! Try it and see what's gonna happen.

Now that there's a porting issue, I made Dept rely on Lockdep. But it
should be separated from Lockdep once it's considered worth having.

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. Multiple reports are allowed.
	6. Deduplication control on multiple reports.
	7. Withstand false positives thanks to 5.
	8. 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.

I hope you guys are gonna be satisfied with Dept. Don't hesitate to
give any feedback. I will adopt any feedbacks if reasonable.

Thanks,
Byungchul

Byungchul Park (14):
  llist: Move llist_{head,node} definition to types.h
  dept: Implement Dept(Dependency Tracker)
  dept: Embed Dept data in Lockdep
  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: Separate out SDT(Single-event Dependency Tracker) header
  dept: Apply SDT to swait

 include/linux/completion.h        |   48 +-
 include/linux/dept.h              |  541 ++++++++
 include/linux/dept_page.h         |   71 +
 include/linux/dept_sdt.h          |   53 +
 include/linux/hardirq.h           |    3 +
 include/linux/irqflags.h          |   33 +-
 include/linux/llist.h             |    9 +-
 include/linux/lockdep.h           |  156 ++-
 include/linux/lockdep_types.h     |    3 +
 include/linux/mutex.h             |   31 +
 include/linux/page-flags.h        |   26 +-
 include/linux/pagemap.h           |    7 +-
 include/linux/percpu-rwsem.h      |   10 +-
 include/linux/rtmutex.h           |   11 +-
 include/linux/rwlock.h            |   48 +
 include/linux/rwlock_api_smp.h    |    8 +-
 include/linux/rwlock_types.h      |    7 +
 include/linux/rwsem.h             |   31 +
 include/linux/sched.h             |    3 +
 include/linux/seqlock.h           |   19 +-
 include/linux/spinlock.h          |   24 +
 include/linux/spinlock_types.h    |   10 +
 include/linux/swait.h             |    4 +
 include/linux/types.h             |    8 +
 init/init_task.c                  |    2 +
 init/main.c                       |    4 +
 kernel/Makefile                   |    1 +
 kernel/dependency/Makefile        |    5 +
 kernel/dependency/dept.c          | 2593 +++++++++++++++++++++++++++++++++++++
 kernel/dependency/dept_hash.h     |   11 +
 kernel/dependency/dept_internal.h |   26 +
 kernel/dependency/dept_object.h   |   14 +
 kernel/dependency/dept_proc.c     |   97 ++
 kernel/exit.c                     |    1 +
 kernel/fork.c                     |    2 +
 kernel/locking/lockdep.c          |   12 +-
 kernel/module.c                   |    2 +
 kernel/sched/completion.c         |   12 +-
 kernel/sched/swait.c              |    8 +
 kernel/softirq.c                  |    6 +-
 kernel/trace/trace_preemptirq.c   |   19 +-
 lib/Kconfig.debug                 |   21 +
 mm/filemap.c                      |   62 +
 mm/page_ext.c                     |    5 +
 44 files changed, 4009 insertions(+), 58 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] 31+ messages in thread

end of thread, other threads:[~2022-01-27  1:12 UTC | newest]

Thread overview: 31+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-01-25  2:36 [RFC 00/14] DEPT(DEPendency Tracker) Byungchul Park
2022-01-25  2:36 ` [RFC 01/14] llist: Move llist_{head,node} definition to types.h Byungchul Park
2022-01-25  2:36 ` [RFC 02/14] dept: Implement Dept(Dependency Tracker) Byungchul Park
2022-01-25  2:36 ` [RFC 03/14] dept: Embed Dept data in Lockdep Byungchul Park
2022-01-25  2:36 ` [RFC 04/14] dept: Apply Dept to spinlock Byungchul Park
2022-01-25  2:36 ` [RFC 05/14] dept: Apply Dept to mutex families Byungchul Park
2022-01-25  2:36 ` [RFC 06/14] dept: Apply Dept to rwlock Byungchul Park
2022-01-25  2:36 ` [RFC 07/14] dept: Apply Dept to wait_for_completion()/complete() Byungchul Park
2022-01-25  2:36 ` [RFC 08/14] dept: Apply Dept to seqlock Byungchul Park
2022-01-25  2:36 ` [RFC 09/14] dept: Apply Dept to rwsem Byungchul Park
2022-01-25  2:36 ` [RFC 10/14] dept: Add proc knobs to show stats and dependency graph Byungchul Park
2022-01-25  2:36 ` [RFC 11/14] dept: Introduce split map concept and new APIs for them Byungchul Park
2022-01-25  2:36 ` [RFC 12/14] dept: Apply Dept to wait/event of PG_{locked,writeback} Byungchul Park
2022-01-25  2:36 ` [RFC 13/14] dept: Separate out SDT(Single-event Dependency Tracker) header Byungchul Park
2022-01-25  2:36 ` [RFC 14/14] dept: Apply SDT to swait Byungchul Park
2022-01-27  1:00 ` [RFC 00/14] DEPT(DEPendency Tracker) Byungchul Park
2022-01-27  1:08 ` Patches(Dept) for v5.17-rc1 Byungchul Park
2022-01-27  1:10   ` [PATCH on v5.17-rc1 01/14] llist: Move llist_{head,node} definition to types.h Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 02/14] dept: Implement Dept(Dependency Tracker) Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 03/14] dept: Embed Dept data in Lockdep Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 04/14] dept: Apply Dept to spinlock Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 05/14] dept: Apply Dept to mutex families Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 06/14] dept: Apply Dept to rwlock Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 07/14] dept: Apply Dept to wait_for_completion()/complete() Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 08/14] dept: Apply Dept to seqlock Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 09/14] dept: Apply Dept to rwsem Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 10/14] dept: Add proc knobs to show stats and dependency graph Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 11/14] dept: Introduce split map concept and new APIs for them Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 12/14] dept: Apply Dept to wait/event of PG_{locked,writeback} Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 13/14] dept: Separate out SDT(Single-event Dependency Tracker) header Byungchul Park
2022-01-27  1:11     ` [PATCH on v5.17-rc1 14/14] dept: Apply SDT to swait 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).