Message-ID: <20240905114140.GN4723@noisy.programming.kicks-ass.net>
Date: Thu, 5 Sep 2024 13:41:40 +0200
From: Peter Zijlstra <peterz@...radead.org>
To: Wentao Zhang <wentaoz5@...inois.edu>
Cc: Matt.Kelly2@...ing.com, akpm@...ux-foundation.org,
	andrew.j.oppelt@...ing.com, anton.ivanov@...bridgegreys.com,
	ardb@...nel.org, arnd@...db.de, bhelgaas@...gle.com, bp@...en8.de,
	chuck.wolber@...ing.com, dave.hansen@...ux.intel.com,
	dvyukov@...gle.com, hpa@...or.com, jinghao7@...inois.edu,
	johannes@...solutions.net, jpoimboe@...nel.org,
	justinstitt@...gle.com, kees@...nel.org, kent.overstreet@...ux.dev,
	linux-arch@...r.kernel.org, linux-efi@...r.kernel.org,
	linux-kbuild@...r.kernel.org, linux-kernel@...r.kernel.org,
	linux-trace-kernel@...r.kernel.org, linux-um@...ts.infradead.org,
	llvm@...ts.linux.dev, luto@...nel.org, marinov@...inois.edu,
	masahiroy@...nel.org, maskray@...gle.com,
	mathieu.desnoyers@...icios.com, matthew.l.weber3@...ing.com,
	mhiramat@...nel.org, mingo@...hat.com, morbo@...gle.com,
	nathan@...nel.org, ndesaulniers@...gle.com, oberpar@...ux.ibm.com,
	paulmck@...nel.org, richard@....at, rostedt@...dmis.org,
	samitolvanen@...gle.com, samuel.sarkisian@...ing.com,
	steven.h.vanderleest@...ing.com, tglx@...utronix.de,
	tingxur@...inois.edu, tyxu@...inois.edu, x86@...nel.org
Subject: Re: [PATCH v2 0/4] Enable measuring the kernel's Source-based Code
 Coverage and MC/DC with Clang

On Wed, Sep 04, 2024 at 11:32:41PM -0500, Wentao Zhang wrote:
> From: Wentao Zhang <zhangwt1997@...il.com>
> 
> This series adds support for building x86-64 kernels with Clang's Source-
> based Code Coverage[1] in order to facilitate Modified Condition/Decision
> Coverage (MC/DC)[2] that provably correlates to source code for all levels
> of compiler optimization.
> 
> The newly added kernel/llvm-cov/ directory complements the existing gcov
> implementation. Gcov works at the object code level which may better
> reflect actual execution. However, Gcov lacks the necessary information to
> correlate coverage measurement with source code location when compiler
> optimization level is non-zero (which is the default when building the
> kernel). In addition, gcov reports are occasionally ambiguous when
> attempting to compare with source code level developer intent.
> 
> In the following gcov example from drivers/firmware/dmi_scan.c, an
> expression with four conditions is reported to have six branch outcomes,
> which is not ideally informative in many safety related use cases, such as
> automotive, medical, and aerospace.
> 
>         5: 1068:	if (s == e || *e != '/' || !month || month > 12) {
> branch  0 taken 5 (fallthrough)
> branch  1 taken 0
> branch  2 taken 5 (fallthrough)
> branch  3 taken 0
> branch  4 taken 0 (fallthrough)
> branch  5 taken 5
> 
> On the other hand, Clang's Source-based Code Coverage instruments at the
> compiler frontend which maintains an accurate mapping from coverage
> measurement to source code location. Coverage reports reflect exactly how
> the code is written regardless of optimization and can present advanced
> metrics like branch coverage and MC/DC in a clearer way. Coverage report
> for the same snippet by llvm-cov would look as follows:
> 
>  1068|      5|	if (s == e || *e != '/' || !month || month > 12) {
>   ------------------
>   |  Branch (1068:6): [True: 0, False: 5]
>   |  Branch (1068:16): [True: 0, False: 5]
>   |  Branch (1068:29): [True: 0, False: 5]
>   |  Branch (1068:39): [True: 0, False: 5]
>   ------------------
> 
> Clang has added MC/DC support as of its 18.1.0 release. MC/DC is a fine-
> grained coverage metric required by many automotive and aviation industrial
> standards for certifying mission-critical software [3].
> 
> In the following example from arch/x86/events/probe.c, 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;
> 
> As the results suggest, during the span of measurement, only condition C2
> (!msr[bit].test(bit, data)) is covered. That means C2 was evaluated to both
> true and false, and in those test vectors C2 affected the decision outcome
> independently. Therefore MC/DC for this decision is 1 out of 2 (50.00%).
> 
> To do a full kernel measurement, instrument the kernel with
> LLVM_COV_KERNEL_MCDC enabled, and optionally set a
> LLVM_COV_KERNEL_MCDC_MAX_CONDITIONS value (the default is six). Run the
> testsuites, and collect the raw profile data under
> /sys/kernel/debug/llvm-cov/profraw. Such raw profile data can be merged and
> indexed, and used for generating coverage reports in various formats.
> 
>   $ cp /sys/kernel/debug/llvm-cov/profraw vmlinux.profraw
>   $ llvm-profdata merge vmlinux.profraw -o vmlinux.profdata
>   $ llvm-cov show --show-mcdc --show-mcdc-summary                         \
>              --format=text --use-color=false -output-dir=coverage_reports \
>              -instr-profile vmlinux.profdata vmlinux
> 
> The first two patches enable the llvm-cov infrastructure, where the first
> enables source based code coverage and the second adds MC/DC support. The
> next patch disables instrumentation for curve25519-x86_64.c for the same
> reason as gcov. The final patch enables coverage for x86-64.
> 
> The choice to use a new Makefile variable LLVM_COV_PROFILE, instead of
> reusing GCOV_PROFILE, was deliberate. More work needs to be done to
> determine if it is appropriate to reuse the same flag. In addition, given
> the fundamentally different approaches to instrumentation and the resulting
> variation in coverage reports, there is a strong likelihood that coverage
> type will need to be managed separately.
> 
> This work reuses code from a previous effort by Sami Tolvanen et al. [4].
> Our aim is for source-based *code coverage* required for high assurance
> (MC/DC) while [4] focused more on performance optimization.
> 
> This initial submission is restricted to x86-64. Support for other
> architectures would need a bit more Makefile & linker script modification.
> Informally we've confirmed that arm64 works and more are being tested.
> 
> Note that Source-based Code Coverage is Clang-specific and isn't compatible
> with Clang's gcov support in kernel/gcov/. Currently, kernel/gcov/ is not
> able to measure MC/DC without modifying CFLAGS_GCOV and it would face the
> same issues in terms of source correlation as gcov in general does.
> 
> Some demo and results can be found in [5]. We will talk about this patch
> series in the Refereed Track at LPC 2024 [6].
> 
> Known Limitations:
> 
> Kernel code with logical expressions exceeding
> LVM_COV_KERNEL_MCDC_MAX_CONDITIONS will produce a compiler warning.
> Expressions with up to 47 conditions are found in the Linux kernel source
> tree (as of v6.11), but 46 seems to be the max value before the build fails
> due to kernel size. As of LLVM 19 the max number of conditions possible is
> 32767.
> 
> As of LLVM 19, certain expressions are still not covered, and will produce
> build warnings when they are encountered:
> 
> "[...] if a boolean expression is embedded in the nest of another boolean
>  expression but separated by a non-logical operator, this is also not
>  supported. For example, in x = (a && b && c && func(d && f)), the d && f
>  case starts a new boolean expression that is separated from the other
>  conditions by the operator func(). When this is encountered, a warning
>  will be generated and the boolean expression will not be
>  instrumented." [7]
> 

What does this actually look like in the generated code?

Where is the modification to noinstr ?

What is the impact on certification of not covering the noinstr code.

Powered by blists - more mailing lists