| Message ID | 20240824230641.385839-1-wentaoz5@illinois.edu (mailing list archive) |
|---|---|
| Headers | show |
| Series | Enable measuring the kernel's Source-based Code Coverage and MC/DC with Clang | expand |
From: Wentao Zhang <zhangwt1997@gmail.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]
[1] https://clang.llvm.org/docs/SourceBasedCodeCoverage.html
[2] https://en.wikipedia.org/wiki/Modified_condition%2Fdecision_coverage
[3] https://digital-library.theiet.org/content/journals/10.1049/sej.1994.0025
[4] https://lore.kernel.org/lkml/20210407211704.367039-1-morbo@google.com/
[5] https://github.com/xlab-uiuc/linux-mcdc
[6] https://lpc.events/event/18/contributions/1718/
[7] https://clang.llvm.org/docs/SourceBasedCodeCoverage.html#mc-dc-instrumentation
---
v1 -> v2:
* Rebased onto v6.11-rc6 from v6.11-rc4.
* llvm-cov/Kconfig: add CONFIG_LLVM_COV_PROFILE_ALL and be consistent with
GCOV conventions.
* Makefile.lib: let the default of LLVM_COV_PROFILE depend on
CONFIG_LLVM_COV_PROFILE_ALL instead of always being "y", and use
$(is-kernel-object) following 9c2d1328f88a "kbuild: provide reasonable
defaults for tool coverage".
* asm-generic/vmlinux.lds.h: use macro BOUNDED_SECTION_POST_LABEL following
9b351be25360 "vmlinux.lds.h: add BOUNDED_SECTION* macros".
* Makefile.lib: "basetarget" -> "target-stem" following bf48d9b756b9
"kbuild: change tool coverage variables to take the path relative to
$(obj)".
* kernel/trace: remove "LLVM_COV_PROFILE = :n" and let user manually enable
it with LLVM_COV_PROFILE_ALL, if they are sure of the performance impact.
* x86, kbuild: remove "LLVM_COV_PROFILE = :n" instances that have been
taken care of by $is-kernel-object. Also remove the one in
arch/x86/platform/efi/ as llvm-cov doesn't have const propagation issues
as gcov did (ac6119e7f25b "efi/x86: Disable instrumentation in the EFI
runtime handling code").
* modfinal, kbuild: remove "LLVM_COV_PROFILE = :n" as llvm-cov doesn't use
function pointers so it doesn't have CFI-related issues like gcov did
(25a21fbb934a "kbuild: Disable GCOV for *.mod.o").
---
Wentao Zhang (4):
llvm-cov: add Clang's Source-based Code Coverage support
llvm-cov: add Clang's MC/DC support
x86: disable llvm-cov instrumentation
x86: enable llvm-cov support
Makefile | 9 ++
arch/Kconfig | 1 +
arch/x86/Kconfig | 2 +
arch/x86/crypto/Makefile | 3 +-
arch/x86/kernel/vmlinux.lds.S | 2 +
include/asm-generic/vmlinux.lds.h | 36 +++++
kernel/Makefile | 1 +
kernel/llvm-cov/Kconfig | 100 ++++++++++++
kernel/llvm-cov/Makefile | 5 +
kernel/llvm-cov/fs.c | 253 ++++++++++++++++++++++++++++++
kernel/llvm-cov/llvm-cov.h | 156 ++++++++++++++++++
scripts/Makefile.lib | 23 +++
scripts/mod/modpost.c | 2 +
13 files changed, 592 insertions(+), 1 deletion(-)
create mode 100644 kernel/llvm-cov/Kconfig
create mode 100644 kernel/llvm-cov/Makefile
create mode 100644 kernel/llvm-cov/fs.c
create mode 100644 kernel/llvm-cov/llvm-cov.h
On Wed, Sep 04, 2024 at 11:32:41PM -0500, Wentao Zhang wrote: > From: Wentao Zhang <zhangwt1997@gmail.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.
Resending as plain text so that lists can accept. On Thu, Sep 5, 2024 at 8:21 AM Vanderleest (US), Steven H <steven.h.vanderleest@boeing.com> wrote: > > From: Vanderleest (US), Steven H <steven.h.vanderleest@boeing.com> > Date: Thursday, September 5, 2024 at 8:13 AM > To: Peter Zijlstra <peterz@infradead.org>, Wentao Zhang <wentaoz5@illinois.edu> > Cc: Kelly (US), Matt <Matt.Kelly2@boeing.com>, akpm@linux-foundation.org <akpm@linux-foundation.org>, Oppelt (US), Andrew J <andrew.j.oppelt@boeing.com>, anton.ivanov@cambridgegreys.com <anton.ivanov@cambridgegreys.com>, ardb@kernel.org <ardb@kernel.org>, arnd@arndb.de <arnd@arndb.de>, bhelgaas@google.com <bhelgaas@google.com>, bp@alien8.de <bp@alien8.de>, Wolber (US), Chuck <chuck.wolber@boeing.com>, dave.hansen@linux.intel.com <dave.hansen@linux.intel.com>, dvyukov@google.com <dvyukov@google.com>, hpa@zytor.com <hpa@zytor.com>, jinghao7@illinois.edu <jinghao7@illinois.edu>, johannes@sipsolutions.net <johannes@sipsolutions.net>, jpoimboe@kernel.org <jpoimboe@kernel.org>, justinstitt@google.com <justinstitt@google.com>, kees@kernel.org <kees@kernel.org>, kent.overstreet@linux.dev <kent.overstreet@linux.dev>, linux-arch@vger.kernel.org <linux-arch@vger.kernel.org>, linux-efi@vger.kernel.org <linux-efi@vger.kernel.org>, linux-kbuild@vger.kernel.org <linux-kbuild@vger.kernel.org>, linux-kernel@vger.kernel.org <linux-kernel@vger.kernel.org>, linux-trace-kernel@vger.kernel.org <linux-trace-kernel@vger.kernel.org>, linux-um@lists.infradead.org <linux-um@lists.infradead.org>, llvm@lists.linux.dev <llvm@lists.linux.dev>, luto@kernel.org <luto@kernel.org>, marinov@illinois.edu <marinov@illinois.edu>, masahiroy@kernel.org <masahiroy@kernel.org>, maskray@google.com <maskray@google.com>, mathieu.desnoyers@efficios.com <mathieu.desnoyers@efficios.com>, Weber (US), Matthew L <matthew.l.weber3@boeing.com>, mhiramat@kernel.org <mhiramat@kernel.org>, mingo@redhat.com <mingo@redhat.com>, morbo@google.com <morbo@google.com>, nathan@kernel.org <nathan@kernel.org>, ndesaulniers@google.com <ndesaulniers@google.com>, oberpar@linux.ibm.com <oberpar@linux.ibm.com>, paulmck@kernel.org <paulmck@kernel.org>, richard@nod.at <richard@nod.at>, rostedt@goodmis.org <rostedt@goodmis.org>, samitolvanen@google.com <samitolvanen@google.com>, Sarkisian (US), Samuel <samuel.sarkisian@boeing.com>, tglx@linutronix.de <tglx@linutronix.de>, tingxur@illinois.edu <tingxur@illinois.edu>, tyxu@illinois.edu <tyxu@illinois.edu>, x86@kernel.org <x86@kernel.org> > Subject: Re: [EXTERNAL] Re: [PATCH v2 0/4] Enable measuring the kernel's Source-based Code Coverage and MC/DC with Clang > > I’ll answer Peter’s last question: “What is the impact on certification of not covering the noinstr code.” > > > > Any code in the target image that is not executed by a test (and thus not covered) must be analyzed and justified as an exception. For example, defensive code is often impossible to exercise by test, but can be included in the image with a justification to the regulatory authority such as the Federal Aviation Administration (FAA). In practice, this means the number of unique instances of non-instrumented code needs to be manageable. I say “unique instances” because there may be many instances of a particular category, but justified by the same analysis/rationale. Where we specifically mark a section of code with noinstr, it is typically because the instrumentation would change the behavior of the code, perturbing the test results. With some analysis for each distinct category of this issue, we could then write justification(s) to show the overall coverage is sufficient. > > > > Regards, > > Steve > > > > > > From: Peter Zijlstra <peterz@infradead.org> > Date: Thursday, September 5, 2024 at 7:42 AM > To: Wentao Zhang <wentaoz5@illinois.edu> > Cc: Kelly (US), Matt <Matt.Kelly2@boeing.com>, akpm@linux-foundation.org <akpm@linux-foundation.org>, Oppelt (US), Andrew J <andrew.j.oppelt@boeing.com>, anton.ivanov@cambridgegreys.com <anton.ivanov@cambridgegreys.com>, ardb@kernel.org <ardb@kernel.org>, arnd@arndb.de <arnd@arndb.de>, bhelgaas@google.com <bhelgaas@google.com>, bp@alien8.de <bp@alien8.de>, Wolber (US), Chuck <chuck.wolber@boeing.com>, dave.hansen@linux.intel.com <dave.hansen@linux.intel.com>, dvyukov@google.com <dvyukov@google.com>, hpa@zytor.com <hpa@zytor.com>, jinghao7@illinois.edu <jinghao7@illinois.edu>, johannes@sipsolutions.net <johannes@sipsolutions.net>, jpoimboe@kernel.org <jpoimboe@kernel.org>, justinstitt@google.com <justinstitt@google.com>, kees@kernel.org <kees@kernel.org>, kent.overstreet@linux.dev <kent.overstreet@linux.dev>, linux-arch@vger.kernel.org <linux-arch@vger.kernel.org>, linux-efi@vger.kernel.org <linux-efi@vger.kernel.org>, linux-kbuild@vger.kernel.org <linux-kbuild@vger.kernel.org>, linux-kernel@vger.kernel.org <linux-kernel@vger.kernel.org>, linux-trace-kernel@vger.kernel.org <linux-trace-kernel@vger.kernel.org>, linux-um@lists.infradead.org <linux-um@lists.infradead.org>, llvm@lists.linux.dev <llvm@lists.linux.dev>, luto@kernel.org <luto@kernel.org>, marinov@illinois.edu <marinov@illinois.edu>, masahiroy@kernel.org <masahiroy@kernel.org>, maskray@google.com <maskray@google.com>, mathieu.desnoyers@efficios.com <mathieu.desnoyers@efficios.com>, Weber (US), Matthew L <matthew.l.weber3@boeing.com>, mhiramat@kernel.org <mhiramat@kernel.org>, mingo@redhat.com <mingo@redhat.com>, morbo@google.com <morbo@google.com>, nathan@kernel.org <nathan@kernel.org>, ndesaulniers@google.com <ndesaulniers@google.com>, oberpar@linux.ibm.com <oberpar@linux.ibm.com>, paulmck@kernel.org <paulmck@kernel.org>, richard@nod.at <richard@nod.at>, rostedt@goodmis.org <rostedt@goodmis.org>, samitolvanen@google.com <samitolvanen@google.com>, Sarkisian (US), Samuel <samuel.sarkisian@boeing.com>, Vanderleest (US), Steven H <steven.h.vanderleest@boeing.com>, tglx@linutronix.de <tglx@linutronix.de>, tingxur@illinois.edu <tingxur@illinois.edu>, tyxu@illinois.edu <tyxu@illinois.edu>, x86@kernel.org <x86@kernel.org> > Subject: [EXTERNAL] Re: [PATCH v2 0/4] Enable measuring the kernel's Source-based Code Coverage and MC/DC with Clang > > EXT email: be mindful of links/attachments. > > > > On Wed, Sep 04, 2024 at 11:32:41PM -0500, Wentao Zhang wrote: > > From: Wentao Zhang <zhangwt1997@gmail.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.
On 2024-09-05 06:41, Peter Zijlstra wrote: > On Wed, Sep 04, 2024 at 11:32:41PM -0500, Wentao Zhang wrote: >> From: Wentao Zhang <zhangwt1997@gmail.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? > Example 1: https://godbolt.org/z/PT6ssxdv1 (Taken from Message-ID: <20210614153545.GA68749@worktop.programming.kicks-ass.net>) where counter updates look like "inc qword ptr [rip + .L__profc_instr(int)]". Example 2 with MC/DC: https://godbolt.org/z/ronMc578z where bitmap updates look like "or byte ptr [rip + .L__profbm_instr(int)], 8". > Where is the modification to noinstr ? > In both two examples the compiler is respecting "__no_profile_instrument_function__" attribute, which is part of "__no_profile" macro, which is in turn part of "noinstr" macro. > What is the impact on certification of not covering the noinstr code. > > Allow me to reformat Steve's <steven.h.vanderleest@boeing.com> reply below: ------------------------------------------------------------------------- I'll answer Peter's last question: "What is the impact on certification of not covering the noinstr code." Any code in the target image that is not executed by a test (and thus not covered) must be analyzed and justified as an exception. For example, defensive code is often impossible to exercise by test, but can be included in the image with a justification to the regulatory authority such as the Federal Aviation Administration (FAA). In practice, this means the number of unique instances of non-instrumented code needs to be manageable. I say "unique instances" because there may be many instances of a particular category, but justified by the same analysis/rationale. Where we specifically mark a section of code with noinstr, it is typically because the instrumentation would change the behavior of the code, perturbing the test results. With some analysis for each distinct category of this issue, we could then write justification(s) to show the overall coverage is sufficient. Regards, Steve ------------------------------------------------------------------------- Thanks, Wentao
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 patch in this series enables Clang's Source-based Code Coverage in the kernel. The second patch disables instrumentation in the same areas that were disabled for kernel/gcov/. The third patch adds kernel configuration directives to enable MC/DC instrumentation. 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] and would appreciate the community's feedback. Known Limitations: Kernel code with logical expressions exceeding LVM_COV_KERNEL_MCDC_MAX_CONDITIONS will produce a compiler warning. Expressions with up to 45 conditions are found in the Linux kernel source tree, but 44 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] [1] https://clang.llvm.org/docs/SourceBasedCodeCoverage.html [2] https://en.wikipedia.org/wiki/Modified_condition%2Fdecision_coverage [3] https://digital-library.theiet.org/content/journals/10.1049/sej.1994.0025 [4] https://lore.kernel.org/lkml/20210407211704.367039-1-morbo@google.com/ [5] https://github.com/xlab-uiuc/linux-mcdc [6] https://lpc.events/event/18/contributions/1718/ [7] https://clang.llvm.org/docs/SourceBasedCodeCoverage.html#mc-dc-instrumentation Wentao Zhang (3): [RFC PATCH 1/3] llvm-cov: add Clang's Source-based Code Coverage support [RFC PATCH 2/3] kbuild, llvm-cov: disable instrumentation in odd or sensitive code [RFC PATCH 3/3] llvm-cov: add Clang's MC/DC support Makefile | 9 + arch/Kconfig | 1 + arch/x86/Kconfig | 1 + arch/x86/boot/Makefile | 1 + arch/x86/boot/compressed/Makefile | 1 + arch/x86/entry/vdso/Makefile | 1 + arch/x86/kernel/vmlinux.lds.S | 2 + arch/x86/platform/efi/Makefile | 1 + arch/x86/purgatory/Makefile | 1 + arch/x86/realmode/rm/Makefile | 1 + arch/x86/um/vdso/Makefile | 1 + drivers/firmware/efi/libstub/Makefile | 2 + include/asm-generic/vmlinux.lds.h | 38 ++++ kernel/Makefile | 1 + kernel/llvm-cov/Kconfig | 65 +++++++ kernel/llvm-cov/Makefile | 5 + kernel/llvm-cov/fs.c | 253 ++++++++++++++++++++++++++ kernel/llvm-cov/llvm-cov.h | 156 ++++++++++++++++ kernel/trace/Makefile | 1 + scripts/Makefile.lib | 21 +++ scripts/Makefile.modfinal | 1 + scripts/mod/modpost.c | 2 + 22 files changed, 565 insertions(+) create mode 100644 kernel/llvm-cov/Kconfig create mode 100644 kernel/llvm-cov/Makefile create mode 100644 kernel/llvm-cov/fs.c create mode 100644 kernel/llvm-cov/llvm-cov.h