[RFC 00/14] DEPT(DEPendency Tracker)

[Byungchul Park]

+cc

linux-mm at kvack.org
akpm at linux-foundation.org
mhocko at kernel.org
minchan at kernel.org
hannes at cmpxchg.org
vdavydov.dev at gmail.com
sj at kernel.org
jglisse at redhat.com
dennis at kernel.org
cl at linux.com
penberg at kernel.org
rientjes at google.com
vbabka at suse.cz
ngupta at vflare.org
linux-block at vger.kernel.org
axboe at kernel.dk
paolo.valente at linaro.org
josef at toxicpanda.com
linux-fsdevel at vger.kernel.org
viro at zeniv.linux.org.uk
jack at suse.cz
jlayton at kernel.org
dan.j.williams at intel.com
hch at infradead.org
djwong at kernel.org
dri-devel at lists.freedesktop.org
airlied at linux.ie
rodrigosiqueiramelo at gmail.com
melissa.srw at gmail.com
hamohammed.sa at gmail.com

--->8---
>From 68ee7ab996fc7d67b6b506f48da106493ca2546a Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park at lge.com>
Date: Tue, 25 Jan 2022 10:12:54 +0900
Subject: [RFC 00/14] DEPT(DEPendency Tracker)

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