[RFC PATCH 16/20] coverage: add MC/DC measurement

[Sasha Levin <sashal@kernel.org>]

Add CONFIG_COVERAGE_MCDC to measure Modified Condition/Decision
Coverage (MC/DC) [1], which is required by several automotive and
aviation standards for certifying safety critical software [2]. Start
with Clang's source-based code coverage, which supports it since Clang
18 [3].

In the following example from arch/x86/events/probe.c, measured on
v6.11, llvm-cov gives the MC/DC measurement for the compound logic
decision at line 43:

   43|     12|			if (msr[bit].test && !msr[bit].test(bit, data))
  ------------------
  |---> MC/DC Decision Region (43:8) to (43:50)
  |
  |  Number of Conditions: 2
  |     Condition C1 --> (43:8)
  |     Condition C2 --> (43:25)
  |
  |  Executed MC/DC Test Vectors:
  |
  |     C1, C2    Result
  |  1 { T,  F  = F      }
  |  2 { T,  T  = T      }
  |
  |  C1-Pair: not covered
  |  C2-Pair: covered: (1,2)
  |  MC/DC Coverage for Decision: 50.00%
  |
  ------------------
   44|      5|				continue;

Only condition C2 was shown to independently affect the outcome of the
decision, so the MC/DC of this decision is 1 out of 2.

MC/DC uses bitmaps to track the executed test vectors, which grow
quickly with the number of conditions. CONFIG_LLVM_COV_MCDC_MAX_CONDITIONS
sets the largest decision to instrument, through -fmcdc-max-conditions.
Larger decisions, and decisions the compiler can't instrument, produce
warnings. Starting with Clang 22 they are kept from becoming errors
with CONFIG_WERROR; older versions can't be used together with it.

Link: https://en.wikipedia.org/wiki/Modified_condition%2Fdecision_coverage [1]
Link: https://digital-library.theiet.org/content/journals/10.1049/sej.1994.0025 [2]
Link: https://clang.llvm.org/docs/SourceBasedCodeCoverage.html#mc-dc-instrumentation [3]
Originally-by: Wentao Zhang <wentaoz5@illinois.edu>
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
 kernel/coverage/Kconfig   | 26 ++++++++++++++++++++++++++
 kernel/coverage/llvm/fs.c |  5 +++--
 scripts/Makefile.llvm-cov |  5 +++++
 3 files changed, 34 insertions(+), 2 deletions(-)

diff --git a/kernel/coverage/Kconfig b/kernel/coverage/Kconfig
index acfcce23e4c97..fab3da51305bb 100644
--- a/kernel/coverage/Kconfig
+++ b/kernel/coverage/Kconfig
@@ -106,6 +106,32 @@ config COVERAGE_PROFILE_ALL
 	  larger and run slower. Also be sure to exclude files from profiling
 	  which are not linked to the kernel image to prevent linker errors.
 
+config COVERAGE_MCDC
+	bool "Measure modified condition/decision coverage (MC/DC)"
+	depends on LLVM_COV_KERNEL
+	depends on CLANG_VERSION >= 220000 || !WERROR
+	help
+	  MC/DC verifies that each condition of a boolean decision has been
+	  shown to independently affect the outcome of the decision. It is
+	  required for certification by safety standards such as DO-178C
+	  (avionics) and ISO 26262 (automotive).
+
+	  Decisions that the compiler can't instrument produce build warnings
+	  and are not measured.
+
+	  If unsure, say N.
+
+config LLVM_COV_MCDC_MAX_CONDITIONS
+	int "Maximum number of conditions in a decision to instrument"
+	range 6 32767
+	depends on COVERAGE_MCDC && LLVM_COV_KERNEL
+	default 6
+	help
+	  This value is passed to the "-fmcdc-max-conditions" option of Clang.
+	  Decisions with more conditions produce warnings and are not
+	  instrumented. MC/DC uses bitmaps to track the executed test vectors,
+	  which grow quickly with the number of conditions.
+
 # The per-subsystem COVERAGE_PROFILE_* options used to be GCOV_PROFILE_*.
 config GCOV_PROFILE_AMDGPU
 	bool
diff --git a/kernel/coverage/llvm/fs.c b/kernel/coverage/llvm/fs.c
index e90c325daeba3..16ada19650d07 100644
--- a/kernel/coverage/llvm/fs.c
+++ b/kernel/coverage/llvm/fs.c
@@ -184,8 +184,9 @@ static void llvm_cov_reset(void)
 }
 
 static const struct coverage_backend llvm_cov_backend = {
-	.name	= "llvm",
-	.reset	= llvm_cov_reset,
+	.name		= "llvm",
+	.features	= IS_ENABLED(CONFIG_COVERAGE_MCDC) ? "mcdc" : NULL,
+	.reset		= llvm_cov_reset,
 };
 
 static int __init llvm_cov_init(void)
diff --git a/scripts/Makefile.llvm-cov b/scripts/Makefile.llvm-cov
index 5babb09b6d3e6..771a033a92669 100644
--- a/scripts/Makefile.llvm-cov
+++ b/scripts/Makefile.llvm-cov
@@ -3,4 +3,9 @@
 CFLAGS_COVERAGE	:= -fprofile-instr-generate -fcoverage-mapping \
 		   -fprofile-update=atomic
 
+ifdef CONFIG_COVERAGE_MCDC
+CFLAGS_COVERAGE	+= -fcoverage-mcdc $(call cc-option,-Wno-error=pgo-coverage) \
+		   -Xclang -fmcdc-max-conditions=$(CONFIG_LLVM_COV_MCDC_MAX_CONDITIONS)
+endif
+
 export CFLAGS_COVERAGE
-- 
2.53.0