Message-ID: <CAG_fn=Utve6zTW9kxwVbqpbQTRMtJPbvtyV3QkQ3yuinizF44Q@mail.gmail.com>
Date: Fri, 27 Jun 2025 15:58:59 +0200
From: Alexander Potapenko <glider@...gle.com>
To: Peter Zijlstra <peterz@...radead.org>
Cc: quic_jiangenj@...cinc.com, linux-kernel@...r.kernel.org, 
	kasan-dev@...glegroups.com, Aleksandr Nogikh <nogikh@...gle.com>, 
	Andrey Konovalov <andreyknvl@...il.com>, Borislav Petkov <bp@...en8.de>, 
	Dave Hansen <dave.hansen@...ux.intel.com>, Dmitry Vyukov <dvyukov@...gle.com>, 
	Ingo Molnar <mingo@...hat.com>, Josh Poimboeuf <jpoimboe@...nel.org>, Marco Elver <elver@...gle.com>, 
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [PATCH v2 08/11] kcov: add ioctl(KCOV_UNIQUE_ENABLE)

On Fri, Jun 27, 2025 at 10:27 AM Peter Zijlstra <peterz@...radead.org> wrote:
>
> On Thu, Jun 26, 2025 at 03:41:55PM +0200, Alexander Potapenko wrote:
> > ioctl(KCOV_UNIQUE_ENABLE) enables collection of deduplicated coverage
> > in the presence of CONFIG_KCOV_ENABLE_GUARDS.
> >
> > The buffer shared with the userspace is divided in two parts, one holding
> > a bitmap, and the other one being the trace. The single parameter of
> > ioctl(KCOV_UNIQUE_ENABLE) determines the number of words used for the
> > bitmap.
> >
> > Each __sanitizer_cov_trace_pc_guard() instrumentation hook receives a
> > pointer to a unique guard variable. Upon the first call of each hook,
> > the guard variable is initialized with a unique integer, which is used to
> > map those hooks to bits in the bitmap. In the new coverage collection mode,
> > the kernel first checks whether the bit corresponding to a particular hook
> > is set, and then, if it is not, the PC is written into the trace buffer,
> > and the bit is set.
>
> I am somewhat confused; the clang documentation states that every edge
> will have a guard variable.

There are two modes, -fsanitize-coverage=edge and
-fsanitize-coverage=bb, with edge being the default one.

When instrumenting basic blocks, the compiler inserts a call to
__sanitizer_cov_trace_pc at the beginning of every basic block in the
LLVM IR (well, not exactly, because some basic blocks are considered
redundant; this behavior can be disabled by passing
-fsanitize-coverage=no-prune).

Now, instrumenting the edges is actually very similar to basic blocks:
we just find critical edges of the callgraph, add a new basic block in
the middle of those edges, then instrument basic blocks like we did
before.
For what it's worth, the number of coverage hooks does not usually
become quadratic when instrumenting edges, we only add a handful of
new basic blocks.

>
> So if I have code like:
>
> foo:    Jcc     foobar
> ...
> bar:    Jcc     foobar
> ...
> foobar:
>
> Then we get two guard variables for the one foobar target?

Correct.
Note that in this sense coverage guards behave exactly similar to
-fsanitize-coverage=trace-pc that we used before.

Consider the following example (also available at
https://godbolt.org/z/TcMT8W45o):

void bar();
void foo(int *a) {
  if (a)
    *a = 0;
  bar();
}

Compiling it with different coverage options may give an idea of how
{trace-pc,trace-pc-guard}x{bb,edge} relate to each other:

# Coverage we use today, instrumenting edges:
$ clang -fsanitize-coverage=trace-pc -S -O2
# Guard coverage proposed in the patch, instrumenting edges
$ clang -fsanitize-coverage=trace-pc-guard -S -O2
# PC coverage with basic block instrumentation
$ clang -fsanitize-coverage=trace-pc,bb -S -O2
# Guard coverage with basic block instrumentation
$ clang -fsanitize-coverage=trace-pc-guard,bb -S -O2

The number of coverage calls doesn't change if I change trace-pc to
trace-pc-guard.
-fsanitize-coverage=bb produces one call less than
-fsanitize-coverage=edge (aka the default mode).

>
> But from a coverage PoV you don't particularly care about the edges; you
> only care you hit the instruction.

Fuzzing engines care about various signals of program state, not just
basic block coverage.
There's a tradeoff between precisely distinguishing between two states
(e.g. "last time I called a()-->b()->c() to get to this line, now this
is a()->d()->e()->f()-c(), let's treat it differently") and bloating
the fuzzing corpus with redundant information.
Our experience shows that using such makeshift edge coverage produces
better results than just instrumenting basic blocks, but collecting
longer traces of basic blocks is unnecessary.

> Combined with the naming of the hook:
> 'trace_pc_guard', which reads to me like: program-counter guard, suggesting
> the guard is in fact per PC or target node, not per edge.
>
> So which is it?

The same hook is used in both the BB and the edge modes, because in
both cases we are actually instrumenting basic blocks.

>
> Also, dynamic edges are very hard to allocate guard variables for, while
> target guards are trivial, even in the face of dynamic edges.

All edges are known statically, because they are within the same
function - calls between functions are not considered edges.

> A further consideration is that the number of edges can vastly outnumber
> the number of nodes, again suggesting that node guards might be better.
>

For the above reason, this isn't a problem.
In the current setup (with edges, without guards), the number of
instrumentation points in vmlinux is on the order of single-digit
millions.

Powered by blists - more mailing lists