public inbox for linux-crypto@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH RFC 00/24] Compiler-Based Capability- and Locking-Analysis
@ 2025-02-06 18:09 Marco Elver
  2025-02-06 18:09 ` [PATCH RFC 01/24] compiler_types: Move lock checking attributes to compiler-capability-analysis.h Marco Elver
                   ` (24 more replies)
  0 siblings, 25 replies; 51+ messages in thread
From: Marco Elver @ 2025-02-06 18:09 UTC (permalink / raw)
  To: elver
  Cc: Paul E. McKenney, Alexander Potapenko, Bart Van Assche,
	Bill Wendling, Boqun Feng, Dmitry Vyukov, Frederic Weisbecker,
	Greg Kroah-Hartman, Ingo Molnar, Jann Horn, Joel Fernandes,
	Jonathan Corbet, Josh Triplett, Justin Stitt, Kees Cook,
	Mark Rutland, Mathieu Desnoyers, Miguel Ojeda, Nathan Chancellor,
	Neeraj Upadhyay, Nick Desaulniers, Peter Zijlstra, Steven Rostedt,
	Thomas Gleixner, Uladzislau Rezki, Waiman Long, Will Deacon,
	kasan-dev, linux-kernel, llvm, rcu, linux-crypto

[ Note: Bart and I had concurrently been working on bringing Clang's
  -Wthread-safety to the kernel:
    https://lore.kernel.org/all/20250206175114.1974171-1-bvanassche@acm.org/
  Having both RFCs out should hopefully provide a good picture on these
  design points and trade-offs - the approaches differ significantly. ]

Capability analysis is a C language extension, which enables statically
checking that user-definable "capabilities" are acquired and released where
required. An obvious application is lock-safety checking for the kernel's
various synchronization primitives (each of which represents a "capability"),
and checking that locking rules are not violated.

Clang originally called the feature "Thread Safety Analysis" [1], with
some terminology still using the thread-safety-analysis-only names. This
was later changed and the feature became more flexible, gaining the
ability to define custom "capabilities". Its foundations can be found in
"capability systems", used to specify the permissibility of operations
to depend on some capability being held (or not held).

[1] https://clang.llvm.org/docs/ThreadSafetyAnalysis.html
[2] https://www.cs.cornell.edu/talc/papers/capabilities.pdf

Because the feature is not just able to express capabilities related to
synchronization primitives, the naming chosen for the kernel departs
from Clang's initial "Thread Safety" nomenclature and refers to the
feature as "Capability Analysis" to avoid confusion. The implementation
still makes references to the older terminology in some places, such as
`-Wthread-safety` being the warning enabled option that also still
appears in diagnostic messages.

Enabling capability analysis can be seen as enabling a dialect of Linux
C with a Capability System.

Additional details can be found in the added kernel-doc documentation.

=== Development Approach ===

Prior art exists in the form of Sparse's context tracking. Locking
annotations on functions exist, so the concept of analyzing locking rules
is not foreign to the kernel's codebase.

However, Clang's analysis is more complete vs. Sparse's, with the
typical trade-offs in static analysis: improved completeness is
sacrificed for more possible false positives or additional annotations
required by the programmer. Numerous options exist to disable or opt out
certain code from analysis.

This series aims to retain compatibility with Sparse, which can provide
tree-wide analysis of a subset of the capability analysis introduced.
For the most part, the new (and old) keywords used for annotations are
shared between Sparse and Clang.

One big question is how to enable this feature, given we end up with a
new dialect of C - 2 approaches have been considered:


	A. Tree-wide all-or-nothing approach. This approach requires
	   tree-wide changes, adding annotations or selective opt-outs.
	   Making additional primitives capability-enabled increases
	   churn, esp. where maintainers are unaware of the feature's
	   existence and how to use it.

Because we can't change the programming language (even if from one C
dialect to another) of the kernel overnight, a different approach might
cause less friction.

	B. A selective, incremental, and much less intrusive approach.
	   Maintainers of subsystems opt in their modules or directories
	   into "capability analysis" (via Makefile):

	     CAPABILITY_ANALYSIS_foo.o := y	# foo.o only
	     CAPABILITY_ANALYSIS := y  		# all TUs

	   Most (eventually all) synchronization primitives and more
	   capabilities (including ones that could track "irq disabled",
	   "preemption" disabled, etc.) could be supported.

The approach taken by this series if B. This ensures that only
subsystems where maintainers are willing to deal with any warnings one
way or another. Introducing the feature can be done incrementally,
without large tree-wide changes and adding numerous opt-outs and
annotations to the majority of code.

=== Initial Uses ===

With this initial series, the following synchronization primitives are
supported: `raw_spinlock_t`, `spinlock_t`, `rwlock_t`, `mutex`,
`seqlock_t`, `bit_spinlock`, RCU, SRCU (`srcu_struct`), `rw_semaphore`,
`local_lock_t`.

As an initial proof-of-concept, this series also enables capability
analysis for the following subsystems: kfence, kcov, stackdepot,
rhashtable. (Those subsystems were chosen because I am familiar with
their locking rules; rhashtable was chosen semi-randomly as a test
because it combines a bunch of things: RCU, mutex, bit_spinlock.)

The initial benefits are static detection of violations of locking
rules. As more capabilities are added, we would see more static checking
beyond what regular C can provide, all while remaining easy (read quick)
to use via the Clang compiler.

=== Appendix ===

The following pending Clang patch is recommended, but not a strong
dependency:

	https://github.com/llvm/llvm-project/pull/123063

This series is also available at this Git tree:

	https://git.kernel.org/pub/scm/linux/kernel/git/melver/linux.git/log/?h=cap-analysis

Marco Elver (24):
  compiler_types: Move lock checking attributes to
    compiler-capability-analysis.h
  compiler-capability-analysis: Rename __cond_lock() to __cond_acquire()
  compiler-capability-analysis: Add infrastructure for Clang's
    capability analysis
  compiler-capability-analysis: Add test stub
  Documentation: Add documentation for Compiler-Based Capability
    Analysis
  checkpatch: Warn about capability_unsafe() without comment
  cleanup: Basic compatibility with capability analysis
  lockdep: Annotate lockdep assertions for capability analysis
  locking/rwlock, spinlock: Support Clang's capability analysis
  compiler-capability-analysis: Change __cond_acquires to take return
    value
  locking/mutex: Support Clang's capability analysis
  locking/seqlock: Support Clang's capability analysis
  bit_spinlock: Include missing <asm/processor.h>
  bit_spinlock: Support Clang's capability analysis
  rcu: Support Clang's capability analysis
  srcu: Support Clang's capability analysis
  kref: Add capability-analysis annotations
  locking/rwsem: Support Clang's capability analysis
  locking/local_lock: Support Clang's capability analysis
  debugfs: Make debugfs_cancellation a capability struct
  kfence: Enable capability analysis
  kcov: Enable capability analysis
  stackdepot: Enable capability analysis
  rhashtable: Enable capability analysis

 .../dev-tools/capability-analysis.rst         | 149 ++++++
 Documentation/dev-tools/index.rst             |   1 +
 Documentation/dev-tools/sparse.rst            |   4 +
 Makefile                                      |   1 +
 .../net/wireless/intel/iwlwifi/iwl-trans.h    |   2 +-
 .../wireless/intel/iwlwifi/pcie/internal.h    |   2 +-
 fs/dlm/lock.c                                 |   2 +-
 include/linux/bit_spinlock.h                  |  24 +-
 include/linux/cleanup.h                       |  18 +-
 include/linux/compiler-capability-analysis.h  | 407 +++++++++++++++
 include/linux/compiler_types.h                |  18 +-
 include/linux/debugfs.h                       |  12 +-
 include/linux/kref.h                          |   2 +
 include/linux/list_bl.h                       |   2 +
 include/linux/local_lock.h                    |  18 +-
 include/linux/local_lock_internal.h           |  41 +-
 include/linux/lockdep.h                       |  12 +-
 include/linux/mm.h                            |   6 +-
 include/linux/mutex.h                         |  29 +-
 include/linux/mutex_types.h                   |   4 +-
 include/linux/rcupdate.h                      |  73 ++-
 include/linux/refcount.h                      |   6 +-
 include/linux/rhashtable.h                    |  14 +-
 include/linux/rwlock.h                        |  27 +-
 include/linux/rwlock_api_smp.h                |  29 +-
 include/linux/rwlock_rt.h                     |  37 +-
 include/linux/rwlock_types.h                  |  10 +-
 include/linux/rwsem.h                         |  56 +-
 include/linux/sched/signal.h                  |   2 +-
 include/linux/seqlock.h                       |  24 +
 include/linux/seqlock_types.h                 |   5 +-
 include/linux/spinlock.h                      |  61 ++-
 include/linux/spinlock_api_smp.h              |  14 +-
 include/linux/spinlock_api_up.h               |  71 +--
 include/linux/spinlock_rt.h                   |  27 +-
 include/linux/spinlock_types.h                |  10 +-
 include/linux/spinlock_types_raw.h            |   5 +-
 include/linux/srcu.h                          |  61 ++-
 kernel/Makefile                               |   2 +
 kernel/kcov.c                                 |  40 +-
 kernel/time/posix-timers.c                    |   2 +-
 lib/Kconfig.debug                             |  43 ++
 lib/Makefile                                  |   6 +
 lib/rhashtable.c                              |  12 +-
 lib/stackdepot.c                              |  24 +-
 lib/test_capability-analysis.c                | 481 ++++++++++++++++++
 mm/kfence/Makefile                            |   2 +
 mm/kfence/core.c                              |  24 +-
 mm/kfence/kfence.h                            |  18 +-
 mm/kfence/kfence_test.c                       |   4 +
 mm/kfence/report.c                            |   8 +-
 net/ipv4/tcp_sigpool.c                        |   2 +-
 scripts/Makefile.capability-analysis          |   5 +
 scripts/Makefile.lib                          |  10 +
 scripts/checkpatch.pl                         |   8 +
 tools/include/linux/compiler_types.h          |   4 +-
 56 files changed, 1682 insertions(+), 299 deletions(-)
 create mode 100644 Documentation/dev-tools/capability-analysis.rst
 create mode 100644 include/linux/compiler-capability-analysis.h
 create mode 100644 lib/test_capability-analysis.c
 create mode 100644 scripts/Makefile.capability-analysis

-- 
2.48.1.502.g6dc24dfdaf-goog


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

end of thread, other threads:[~2025-02-27  7:00 UTC | newest]

Thread overview: 51+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-02-06 18:09 [PATCH RFC 00/24] Compiler-Based Capability- and Locking-Analysis Marco Elver
2025-02-06 18:09 ` [PATCH RFC 01/24] compiler_types: Move lock checking attributes to compiler-capability-analysis.h Marco Elver
2025-02-06 18:40   ` Bart Van Assche
2025-02-06 18:48     ` Marco Elver
2025-02-07  8:33       ` Peter Zijlstra
2025-02-06 18:09 ` [PATCH RFC 02/24] compiler-capability-analysis: Rename __cond_lock() to __cond_acquire() Marco Elver
2025-02-07  8:28   ` Peter Zijlstra
2025-02-07  9:32     ` Marco Elver
2025-02-07  9:41       ` Peter Zijlstra
2025-02-07  9:50         ` Marco Elver
2025-02-06 18:09 ` [PATCH RFC 03/24] compiler-capability-analysis: Add infrastructure for Clang's capability analysis Marco Elver
2025-02-06 18:09 ` [PATCH RFC 04/24] compiler-capability-analysis: Add test stub Marco Elver
2025-02-06 18:09 ` [PATCH RFC 05/24] Documentation: Add documentation for Compiler-Based Capability Analysis Marco Elver
2025-02-06 18:10 ` [PATCH RFC 06/24] checkpatch: Warn about capability_unsafe() without comment Marco Elver
2025-02-06 18:10 ` [PATCH RFC 07/24] cleanup: Basic compatibility with capability analysis Marco Elver
2025-02-06 21:29   ` Bart Van Assche
2025-02-06 22:01     ` Marco Elver
2025-02-06 18:10 ` [PATCH RFC 08/24] lockdep: Annotate lockdep assertions for " Marco Elver
2025-02-10 18:09   ` Bart Van Assche
2025-02-10 18:23     ` Marco Elver
2025-02-10 18:53       ` Bart Van Assche
2025-02-11 13:55         ` Marco Elver
2025-02-06 18:10 ` [PATCH RFC 09/24] locking/rwlock, spinlock: Support Clang's " Marco Elver
2025-02-06 18:10 ` [PATCH RFC 10/24] compiler-capability-analysis: Change __cond_acquires to take return value Marco Elver
2025-02-06 18:10 ` [PATCH RFC 11/24] locking/mutex: Support Clang's capability analysis Marco Elver
2025-02-07  8:31   ` Peter Zijlstra
2025-02-07 20:58     ` Bart Van Assche
2025-02-06 18:10 ` [PATCH RFC 12/24] locking/seqlock: " Marco Elver
2025-02-06 18:10 ` [PATCH RFC 13/24] bit_spinlock: Include missing <asm/processor.h> Marco Elver
2025-02-06 18:10 ` [PATCH RFC 14/24] bit_spinlock: Support Clang's capability analysis Marco Elver
2025-02-06 18:10 ` [PATCH RFC 15/24] rcu: " Marco Elver
2025-02-20 22:00   ` Paul E. McKenney
2025-02-20 22:11     ` Marco Elver
2025-02-20 22:36       ` Paul E. McKenney
2025-02-21  0:16         ` Marco Elver
2025-02-21  1:26           ` Paul E. McKenney
2025-02-21 17:10             ` Marco Elver
2025-02-21 18:08               ` Paul E. McKenney
2025-02-21 18:52                 ` Peter Zijlstra
2025-02-21 19:46                   ` Marco Elver
2025-02-21 19:57                     ` Peter Zijlstra
2025-02-06 18:10 ` [PATCH RFC 16/24] srcu: " Marco Elver
2025-02-06 18:10 ` [PATCH RFC 17/24] kref: Add capability-analysis annotations Marco Elver
2025-02-06 18:10 ` [PATCH RFC 18/24] locking/rwsem: Support Clang's capability analysis Marco Elver
2025-02-06 18:10 ` [PATCH RFC 19/24] locking/local_lock: " Marco Elver
2025-02-06 18:10 ` [PATCH RFC 20/24] debugfs: Make debugfs_cancellation a capability struct Marco Elver
2025-02-06 18:10 ` [PATCH RFC 21/24] kfence: Enable capability analysis Marco Elver
2025-02-06 18:10 ` [PATCH RFC 22/24] kcov: " Marco Elver
2025-02-06 18:10 ` [PATCH RFC 23/24] stackdepot: " Marco Elver
2025-02-06 18:10 ` [PATCH RFC 24/24] rhashtable: " Marco Elver
2025-02-27  7:00 ` [PATCH RFC 00/24] Compiler-Based Capability- and Locking-Analysis Marco Elver

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox