[PATCH] KCOV: Introduced tracing unique covered PCs

[Alexander Lochmann]

Introduced new tracing mode KCOV_MODE_UNIQUE.
It simply stores the executed PCs.
The execution order is discarded.
Each bit in the shared buffer represents every fourth
byte of the text segment.
Since a call instruction on every supported
architecture is at least four bytes, it is safe
to just store every fourth byte of the text segment.
In contrast to KCOV_MODE_TRACE_PC, the shared buffer
cannot overflow. Thus, all executed PCs are recorded.

Signed-off-by: Alexander Lochmann <in...@alexander-lochmann.de>
---
Documentation/dev-tools/kcov.rst | 80 ++++++++++++++++++++++++++++++++
include/linux/kcov.h | 4 +-
include/uapi/linux/kcov.h | 10 ++++
kernel/kcov.c | 67 ++++++++++++++++++++------
4 files changed, 147 insertions(+), 14 deletions(-)

diff --git a/Documentation/dev-tools/kcov.rst b/Documentation/dev-tools/kcov.rst
index 8548b0b04e43..4712a730a06a 100644
--- a/Documentation/dev-tools/kcov.rst
+++ b/Documentation/dev-tools/kcov.rst
@@ -127,6 +127,86 @@ That is, a parent process opens /sys/kernel/debug/kcov, enables trace mode,
mmaps coverage buffer and then forks child processes in a loop. Child processes
only need to enable coverage (disable happens automatically on thread end).

+If someone is interested in a set of executed PCs, and does not care about
+execution order, he or she can advise KCOV to do so:
+
+.. code-block:: c
+
+ #include <stdio.h>
+ #include <stddef.h>
+ #include <stdint.h>
+ #include <stdlib.h>
+ #include <sys/types.h>
+ #include <sys/stat.h>
+ #include <sys/ioctl.h>
+ #include <sys/mman.h>
+ #include <unistd.h>
+ #include <fcntl.h>
+
+ #define KCOV_INIT_TRACE _IOR('c', 1, unsigned long)
+ #define KCOV_INIT_UNIQUE _IOR('c', 2, unsigned long)
+ #define KCOV_ENABLE _IO('c', 100)
+ #define KCOV_DISABLE _IO('c', 101)
+
+ #define BITS_PER_LONG 64
+ #define KCOV_TRACE_PC 0
+ #define KCOV_TRACE_CMP 1
+ #define KCOV_UNIQUE_PC 2
+ /*
+ * Determine start of text segment via 'nm vmlinux | grep _stext | cut -d " " -f1',
+ * and fill in.
+ */
+ #define STEXT_START 0xffffffff81000000
+
+
+
+ int main(int argc, char **argv)
+ {
+ int fd;
+ unsigned long *cover, n, i;
+
+ /* A single fd descriptor allows coverage collection on a single
+ * thread.
+ */
+ fd = open("/sys/kernel/debug/kcov", O_RDWR);
+ if (fd == -1)
+ perror("open"), exit(1);
+ /* Setup trace mode and trace size. */
+ if ((n = ioctl(fd, KCOV_INIT_UNIQUE, 0)) < 0)
+ perror("ioctl"), exit(1);
+ /* Mmap buffer shared between kernel- and user-space. */
+ cover = (unsigned long*)mmap(NULL, n,
+ PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
+ if ((void*)cover == MAP_FAILED)
+ perror("mmap"), exit(1);
+ /* Enable coverage collection on the current thread. */
+ if (ioctl(fd, KCOV_ENABLE, KCOV_UNIQUE_PC))
+ perror("ioctl"), exit(1);
+ /* That's the target syscal call. */
+ read(-1, NULL, 0);
+ /* Disable coverage collection for the current thread. After this call
+ * coverage can be enabled for a different thread.
+ */
+ if (ioctl(fd, KCOV_DISABLE, 0))
+ perror("ioctl"), exit(1);
+ /* Convert byte size into element size */
+ n /= sizeof(unsigned long);
+ /* Print executed PCs in sorted order */
+ for (i = 0; i < n; i++) {
+ for (int j = 0; j < BITS_PER_LONG; j++) {
+ if (cover[i] & (1L << j)) {
+ printf("0x%jx\n", (uintmax_t)(STEXT_START + (i * BITS_PER_LONG + j) * 4));
+ }
+ }
+ }
+ /* Free resources. */
+ if (munmap(cover, n * sizeof(unsigned long)))
+ perror("munmap"), exit(1);
+ if (close(fd))
+ perror("close"), exit(1);
+ return 0;
+ }
+
Comparison operands collection
------------------------------

diff --git a/include/linux/kcov.h b/include/linux/kcov.h
index a10e84707d82..aa0c8bcf8299 100644
--- a/include/linux/kcov.h
+++ b/include/linux/kcov.h
@@ -19,7 +19,9 @@ enum kcov_mode {
*/
KCOV_MODE_TRACE_PC = 2,
/* Collecting comparison operands mode. */
- KCOV_MODE_TRACE_CMP = 3,
+ KCOV_MODE_TRACE_CMP = 4,
+ /* Collecting unique covered PCs. Execution order is not saved. */
+ KCOV_MODE_UNIQUE_PC = 8,
};

#define KCOV_IN_CTXSW (1 << 30)
diff --git a/include/uapi/linux/kcov.h b/include/uapi/linux/kcov.h
index 1d0350e44ae3..5b99b6d1a1ac 100644
--- a/include/uapi/linux/kcov.h
+++ b/include/uapi/linux/kcov.h
@@ -19,6 +19,7 @@ struct kcov_remote_arg {
#define KCOV_REMOTE_MAX_HANDLES 0x100

#define KCOV_INIT_TRACE _IOR('c', 1, unsigned long)
+#define KCOV_INIT_UNIQUE _IOR('c', 2, unsigned long)
#define KCOV_ENABLE _IO('c', 100)
#define KCOV_DISABLE _IO('c', 101)
#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg)
@@ -35,6 +36,15 @@ enum {
KCOV_TRACE_PC = 0,
/* Collecting comparison operands mode. */
KCOV_TRACE_CMP = 1,
+ /*
+ * Unique coverage collection mode.
+ * Unique covered PCs are collected in a per-task buffer.
+ * De-duplicates the collected PCs. Execution order is *not* saved.
+ * Each bit in the buffer represents every fourth byte of the text segment.
+ * Since a call instruction is at least four bytes on every supported
+ * architecture, storing just every fourth byte is sufficient.
+ */
+ KCOV_UNIQUE_PC = 2,
};

/*
diff --git a/kernel/kcov.c b/kernel/kcov.c
index 6b8368be89c8..8f00ba6e672a 100644
--- a/kernel/kcov.c
+++ b/kernel/kcov.c
@@ -24,6 +24,7 @@
#include <linux/refcount.h>
#include <linux/log2.h>
#include <asm/setup.h>
+#include <asm/sections.h>

#define kcov_debug(fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)

@@ -171,7 +172,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru
* kcov_start().
*/
barrier();
- return mode == needed_mode;
+ return (mode & needed_mode) && !(mode & KCOV_IN_CTXSW);
}

static notrace unsigned long canonicalize_ip(unsigned long ip)
@@ -191,18 +192,26 @@ void notrace __sanitizer_cov_trace_pc(void)
struct task_struct *t;
unsigned long *area;
unsigned long ip = canonicalize_ip(_RET_IP_);
- unsigned long pos;
+ unsigned long pos, idx;

t = current;
- if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))
+ if (!check_kcov_mode(KCOV_MODE_TRACE_PC | KCOV_MODE_UNIQUE_PC, t))
return;

area = t->kcov_area;
- /* The first 64-bit word is the number of subsequent PCs. */
- pos = READ_ONCE(area[0]) + 1;
- if (likely(pos < t->kcov_size)) {
- area[pos] = ip;
- WRITE_ONCE(area[0], pos);
+ if (likely(t->kcov_mode == KCOV_MODE_TRACE_PC)) {
+ /* The first 64-bit word is the number of subsequent PCs. */
+ pos = READ_ONCE(area[0]) + 1;
+ if (likely(pos < t->kcov_size)) {
+ area[pos] = ip;
+ WRITE_ONCE(area[0], pos);
+ }
+ } else {
+ idx = (ip - canonicalize_ip((unsigned long)&_stext)) / 4;
+ pos = idx % BITS_PER_LONG;
+ idx /= BITS_PER_LONG;
+ if (likely(idx < t->kcov_size))
+ WRITE_ONCE(area[idx], READ_ONCE(area[idx]) | 1L << pos);
}
}
EXPORT_SYMBOL(__sanitizer_cov_trace_pc);
@@ -474,6 +483,7 @@ static int kcov_mmap(struct file *filep, struct vm_area_struct *vma)
goto exit;
}
if (!kcov->area) {
+ kcov_debug("mmap(): Allocating 0x%lx bytes\n", size);
kcov->area = area;
vma->vm_flags |= VM_DONTEXPAND;
spin_unlock_irqrestore(&kcov->lock, flags);
@@ -515,6 +525,8 @@ static int kcov_get_mode(unsigned long arg)
{
if (arg == KCOV_TRACE_PC)
return KCOV_MODE_TRACE_PC;
+ else if (arg == KCOV_UNIQUE_PC)
+ return KCOV_MODE_UNIQUE_PC;
else if (arg == KCOV_TRACE_CMP)
#ifdef CONFIG_KCOV_ENABLE_COMPARISONS
return KCOV_MODE_TRACE_CMP;
@@ -562,12 +574,13 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
{
struct task_struct *t;
unsigned long size, unused;
- int mode, i;
+ int mode, i, text_size, ret = 0;
struct kcov_remote_arg *remote_arg;
struct kcov_remote *remote;
unsigned long flags;

switch (cmd) {
+ case KCOV_INIT_UNIQUE:
case KCOV_INIT_TRACE:
/*
* Enable kcov in trace mode and setup buffer size.
@@ -581,11 +594,39 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
* that must not overflow.
*/
size = arg;
- if (size < 2 || size > INT_MAX / sizeof(unsigned long))
- return -EINVAL;
- kcov->size = size;
+ if (cmd == KCOV_INIT_UNIQUE) {
+ if (size != 0)
+ return -EINVAL;
+ text_size = (canonicalize_ip((unsigned long)&_etext) - canonicalize_ip((unsigned long)&_stext));
+ /**
+ * A call instr is at least four bytes on every supported architecture.
+ * Hence, just every fourth instruction can potentially be a call.
+ */
+ text_size /= 4;
+ /*
+ * Round up size of text segment to multiple of BITS_PER_LONG.
+ * Otherwise, we cannot track
+ * the last (text_size % BITS_PER_LONG) addresses.
+ */
+ text_size = roundup(text_size, BITS_PER_LONG);
+ /* Get the amount of bytes needed */
+ text_size = text_size / 8;
+ /* mmap() requires size to be a multiple of PAGE_SIZE */
+ text_size = roundup(text_size, PAGE_SIZE);
+ /* Get the cover size (= amount of longs stored) */
+ ret = text_size;
+ kcov->size = text_size / sizeof(unsigned long);
+ kcov_debug("text size = 0x%lx, roundup = 0x%x, kcov->size = 0x%x\n",
+ ((unsigned long)&_etext) - ((unsigned long)&_stext),
+ text_size,
+ kcov->size);
+ } else {
+ if (size < 2 || size > INT_MAX / sizeof(unsigned long))
+ return -EINVAL;
+ kcov->size = size;
+ }
kcov->mode = KCOV_MODE_INIT;
- return 0;
+ return ret;
case KCOV_ENABLE:
/*
* Enable coverage for the current task.
--
2.30.0

[Dmitry Vyukov]

I see this produces an additional check and branch:

void foo1(unsigned mode) {
if ((mode & 10) && !(mode & (1<<30)))
foo();
}

0: 40 f6 c7 0a test $0xa,%dil
4: 74 0f je 15 <foo1+0x15>
6: 81 e7 00 00 00 40 and $0x40000000,%edi
c: 75 07 jne 15 <foo1+0x15>
e: 31 c0 xor %eax,%eax
10: e9 00 00 00 00 jmpq 15 <foo1+0x15>

I think we could make KCOV_IN_CTXSW sign bit and then express the check as:

void foo2(unsigned mode) {
if (((int)(mode & 0x8000000a)) > 0)
foo();
}

0000000000000020 <foo2>:
20: 81 e7 0a 00 00 80 and $0x8000000a,%edi
26: 7f 08 jg 30 <foo2+0x10>
28: c3 retq

> }
>
> static notrace unsigned long canonicalize_ip(unsigned long ip)
> @@ -191,18 +192,26 @@ void notrace __sanitizer_cov_trace_pc(void)
> struct task_struct *t;
> unsigned long *area;
> unsigned long ip = canonicalize_ip(_RET_IP_);
> - unsigned long pos;
> + unsigned long pos, idx;
>
> t = current;
> - if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))
> + if (!check_kcov_mode(KCOV_MODE_TRACE_PC | KCOV_MODE_UNIQUE_PC, t))
> return;
>
> area = t->kcov_area;
> - /* The first 64-bit word is the number of subsequent PCs. */
> - pos = READ_ONCE(area[0]) + 1;
> - if (likely(pos < t->kcov_size)) {
> - area[pos] = ip;
> - WRITE_ONCE(area[0], pos);
> + if (likely(t->kcov_mode == KCOV_MODE_TRACE_PC)) {

Does this introduce an additional real of t->kcov_mode?
If yes, please reuse the value read in check_kcov_mode.

As far as I understand, users can first do KCOV_INIT_UNIQUE and then
enable KCOV_TRACE_PC, or vice versa.
It looks somewhat strange. Is it intentional? It's not possible to
specify buffer size for KCOV_INIT_UNIQUE, so most likely the buffer
will be either too large or too small for a trace.

> else if (arg == KCOV_TRACE_CMP)
> #ifdef CONFIG_KCOV_ENABLE_COMPARISONS
> return KCOV_MODE_TRACE_CMP;
> @@ -562,12 +574,13 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
> {
> struct task_struct *t;
> unsigned long size, unused;
> - int mode, i;
> + int mode, i, text_size, ret = 0;
> struct kcov_remote_arg *remote_arg;
> struct kcov_remote *remote;
> unsigned long flags;
>
> switch (cmd) {
> + case KCOV_INIT_UNIQUE:

I think nowadays you need some annotation like fallthrough here.

> case KCOV_INIT_TRACE:
> /*
> * Enable kcov in trace mode and setup buffer size.
> @@ -581,11 +594,39 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
> * that must not overflow.
> */
> size = arg;
> - if (size < 2 || size > INT_MAX / sizeof(unsigned long))
> - return -EINVAL;
> - kcov->size = size;
> + if (cmd == KCOV_INIT_UNIQUE) {
> + if (size != 0)
> + return -EINVAL;
> + text_size = (canonicalize_ip((unsigned long)&_etext) - canonicalize_ip((unsigned long)&_stext));
> + /**
> + * A call instr is at least four bytes on every supported architecture.
> + * Hence, just every fourth instruction can potentially be a call.
> + */
> + text_size /= 4;

Strictly saying, we need to round up text_size to 4 before dividing by
4. Otherwise we potentially don't cover up to the last 3 bytes.

> + /*
> + * Round up size of text segment to multiple of BITS_PER_LONG.
> + * Otherwise, we cannot track
> + * the last (text_size % BITS_PER_LONG) addresses.
> + */
> + text_size = roundup(text_size, BITS_PER_LONG);
> + /* Get the amount of bytes needed */
> + text_size = text_size / 8;
> + /* mmap() requires size to be a multiple of PAGE_SIZE */
> + text_size = roundup(text_size, PAGE_SIZE);
> + /* Get the cover size (= amount of longs stored) */

s/longs/bytes/

[Alexander Lochmann]

On 12.02.21 13:54, Dmitry Vyukov wrote:
>
> I think we could make KCOV_IN_CTXSW sign bit and then express the check as:
>
> void foo2(unsigned mode) {
> if (((int)(mode & 0x8000000a)) > 0)
> foo();
> }
>
> 0000000000000020 <foo2>:
> 20: 81 e7 0a 00 00 80 and $0x8000000a,%edi
> 26: 7f 08 jg 30 <foo2+0x10>
> 28: c3 retq
>

So ((int)(mode & (KCOV_IN_CTXSW | needed_mode))) > 0?

>
>
>
>> }
>>
>> static notrace unsigned long canonicalize_ip(unsigned long ip)
>> @@ -191,18 +192,26 @@ void notrace __sanitizer_cov_trace_pc(void)
>> struct task_struct *t;
>> unsigned long *area;
>> unsigned long ip = canonicalize_ip(_RET_IP_);
>> - unsigned long pos;
>> + unsigned long pos, idx;
>>
>> t = current;
>> - if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))
>> + if (!check_kcov_mode(KCOV_MODE_TRACE_PC | KCOV_MODE_UNIQUE_PC, t))
>> return;
>>
>> area = t->kcov_area;
>> - /* The first 64-bit word is the number of subsequent PCs. */
>> - pos = READ_ONCE(area[0]) + 1;
>> - if (likely(pos < t->kcov_size)) {
>> - area[pos] = ip;
>> - WRITE_ONCE(area[0], pos);
>> + if (likely(t->kcov_mode == KCOV_MODE_TRACE_PC)) {
>
> Does this introduce an additional real of t->kcov_mode?
> If yes, please reuse the value read in check_kcov_mode.

Okay. How do I get that value from check_kcov_mode() to the caller?
Shall I add an additional parameter to check_kcov_mode()?

I'll fix that.

It's not possible to
> specify buffer size for KCOV_INIT_UNIQUE, so most likely the buffer
> will be either too large or too small for a trace.

No, the buffer will be calculated by KCOV_INIT_UNIQUE based on the size
of the text segment.

- Alex

--
Alexander Lochmann PGP key: 0xBC3EF6FD
Heiliger Weg 72 phone: +49.231.28053964
D-44141 Dortmund mobile: +49.151.15738323

[Dmitry Vyukov]

On Sun, Mar 14, 2021 at 10:29 PM Alexander Lochmann
<in...@alexander-lochmann.de> wrote:
> On 12.02.21 13:54, Dmitry Vyukov wrote:
> >
> > I think we could make KCOV_IN_CTXSW sign bit and then express the check as:
> >
> > void foo2(unsigned mode) {
> > if (((int)(mode & 0x8000000a)) > 0)
> > foo();
> > }
> >
> > 0000000000000020 <foo2>:
> > 20: 81 e7 0a 00 00 80 and $0x8000000a,%edi
> > 26: 7f 08 jg 30 <foo2+0x10>
> > 28: c3 retq
> >
> So ((int)(mode & (KCOV_IN_CTXSW | needed_mode))) > 0?

Frankly I lost all context now. If it results in optimal code, then, yes.

> >> }
> >>
> >> static notrace unsigned long canonicalize_ip(unsigned long ip)
> >> @@ -191,18 +192,26 @@ void notrace __sanitizer_cov_trace_pc(void)
> >> struct task_struct *t;
> >> unsigned long *area;
> >> unsigned long ip = canonicalize_ip(_RET_IP_);
> >> - unsigned long pos;
> >> + unsigned long pos, idx;
> >>
> >> t = current;
> >> - if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))
> >> + if (!check_kcov_mode(KCOV_MODE_TRACE_PC | KCOV_MODE_UNIQUE_PC, t))
> >> return;
> >>
> >> area = t->kcov_area;
> >> - /* The first 64-bit word is the number of subsequent PCs. */
> >> - pos = READ_ONCE(area[0]) + 1;
> >> - if (likely(pos < t->kcov_size)) {
> >> - area[pos] = ip;
> >> - WRITE_ONCE(area[0], pos);
> >> + if (likely(t->kcov_mode == KCOV_MODE_TRACE_PC)) {
> >
> > Does this introduce an additional real of t->kcov_mode?
> > If yes, please reuse the value read in check_kcov_mode.
> Okay. How do I get that value from check_kcov_mode() to the caller?
> Shall I add an additional parameter to check_kcov_mode()?

Yes, I would try to add an additional pointer parameter for mode. I
think after inlining the compiler should be able to regestrize it.

Yes, which will be either too large or too small for KCOV_TRACE_PC
enabled later.

[Alexander Lochmann]

Should kcov->mode be written directly to that ptr?
Otherwise, it must be written to the already present variable mode, and
than copied to the ptr (if not NULL).

[Dmitry Vyukov]

I would expect that after inlining it won't make difference in
generated code. Is so, both options are fine. Whatever leads to a
cleaner code.

[Alexander Lochmann]

On 15.03.21 09:02, Dmitry Vyukov wrote:

>>> Does this introduce an additional real of t->kcov_mode?
>>> If yes, please reuse the value read in check_kcov_mode.
>> Okay. How do I get that value from check_kcov_mode() to the caller?
>> Shall I add an additional parameter to check_kcov_mode()?
>
> Yes, I would try to add an additional pointer parameter for mode. I
> think after inlining the compiler should be able to regestrize it.

First, I'll go for the extra argument. However, the compiler doesn't
seem to inline check_kcov_mode(). Can I enforce inlining?
I'm using GCC 9.3 on Debian Testing.

[Dmitry Vyukov]

On Wed, Mar 17, 2021 at 10:10 PM Alexander Lochmann
<in...@alexander-lochmann.de> wrote:
> On 15.03.21 09:02, Dmitry Vyukov wrote:
> >>> Does this introduce an additional real of t->kcov_mode?
> >>> If yes, please reuse the value read in check_kcov_mode.
> >> Okay. How do I get that value from check_kcov_mode() to the caller?
> >> Shall I add an additional parameter to check_kcov_mode()?
> >
> > Yes, I would try to add an additional pointer parameter for mode. I
> > think after inlining the compiler should be able to regestrize it.
> First, I'll go for the extra argument. However, the compiler doesn't
> seem to inline check_kcov_mode(). Can I enforce inlining?
> I'm using GCC 9.3 on Debian Testing.

That's very strange and wrong. Maybe you use something like
CONFIG_CC_OPTIMIZE_FOR_SIZE=y?

With gcc-10 I am getting:

ffffffff81529ba0 <__sanitizer_cov_trace_pc>:
ffffffff81529ba0: 65 8b 05 59 53 af 7e mov
%gs:0x7eaf5359(%rip),%eax # 1ef00 <__preempt_count>
ffffffff81529ba7: 89 c1 mov %eax,%ecx
ffffffff81529ba9: 48 8b 34 24 mov (%rsp),%rsi
ffffffff81529bad: 81 e1 00 01 00 00 and $0x100,%ecx
ffffffff81529bb3: 65 48 8b 14 25 40 ef mov %gs:0x1ef40,%rdx
ffffffff81529bba: 01 00
ffffffff81529bbc: a9 00 01 ff 00 test $0xff0100,%eax
ffffffff81529bc1: 74 0e je
ffffffff81529bd1 <__sanitizer_cov_trace_pc+0x31>
ffffffff81529bc3: 85 c9 test %ecx,%ecx
ffffffff81529bc5: 74 35 je
ffffffff81529bfc <__sanitizer_cov_trace_pc+0x5c>
ffffffff81529bc7: 8b 82 d4 14 00 00 mov 0x14d4(%rdx),%eax
ffffffff81529bcd: 85 c0 test %eax,%eax
ffffffff81529bcf: 74 2b je
ffffffff81529bfc <__sanitizer_cov_trace_pc+0x5c>
ffffffff81529bd1: 8b 82 b0 14 00 00 mov 0x14b0(%rdx),%eax
ffffffff81529bd7: 83 f8 02 cmp $0x2,%eax
ffffffff81529bda: 75 20 jne
ffffffff81529bfc <__sanitizer_cov_trace_pc+0x5c>
ffffffff81529bdc: 48 8b 8a b8 14 00 00 mov 0x14b8(%rdx),%rcx
ffffffff81529be3: 8b 92 b4 14 00 00 mov 0x14b4(%rdx),%edx
ffffffff81529be9: 48 8b 01 mov (%rcx),%rax
ffffffff81529bec: 48 83 c0 01 add $0x1,%rax
ffffffff81529bf0: 48 39 c2 cmp %rax,%rdx
ffffffff81529bf3: 76 07 jbe
ffffffff81529bfc <__sanitizer_cov_trace_pc+0x5c>
ffffffff81529bf5: 48 89 34 c1 mov %rsi,(%rcx,%rax,8)
ffffffff81529bf9: 48 89 01 mov %rax,(%rcx)
ffffffff81529bfc: c3 retq

Oh, wait gcc-9 indeed does not inline:

0000000000000070 <__sanitizer_cov_trace_pc>:
70: 65 48 8b 0c 25 00 00 mov %gs:0x0,%rcx
77: 00 00
79: bf 02 00 00 00 mov $0x2,%edi
7e: 48 89 ce mov %rcx,%rsi
81: 4c 8b 04 24 mov (%rsp),%r8
85: e8 76 ff ff ff callq 0 <check_kcov_mode>
8a: 84 c0 test %al,%al
8c: 74 20 je ae
<__sanitizer_cov_trace_pc+0x3e>
8e: 48 8b 91 b8 14 00 00 mov 0x14b8(%rcx),%rdx
95: 8b 89 b4 14 00 00 mov 0x14b4(%rcx),%ecx
9b: 48 8b 02 mov (%rdx),%rax
9e: 48 83 c0 01 add $0x1,%rax
a2: 48 39 c1 cmp %rax,%rcx
a5: 76 07 jbe ae
<__sanitizer_cov_trace_pc+0x3e>
a7: 4c 89 04 c2 mov %r8,(%rdx,%rax,8)
ab: 48 89 02 mov %rax,(%rdx)
ae: c3 retq

This looks like a bug in gcc-8/9. gcc-6 inlines again as well as
clang-11/12 inline.

Please add __always_inline for check_kcov_mode.

[Alexander Lochmann]

It simply stores the executed PCs.
The execution order is discarded.
Each bit in the shared buffer represents every fourth
byte of the text segment.
Since a call instruction on every supported
architecture is at least four bytes, it is safe
to just store every fourth byte of the text segment.
In contrast to KCOV_MODE_TRACE_PC, the shared buffer
cannot overflow. Thus, all executed PCs are recorded.

Signed-off-by: Alexander Lochmann <in...@alexander-lochmann.de>
---
Documentation/dev-tools/kcov.rst | 80 +++++++++++++++++++++++++++

include/linux/kcov.h | 12 ++--
include/uapi/linux/kcov.h | 10 ++++
kernel/kcov.c | 94 ++++++++++++++++++++++++--------
4 files changed, 169 insertions(+), 27 deletions(-)

diff --git a/Documentation/dev-tools/kcov.rst b/Documentation/dev-tools/kcov.rst
index d2c4c27e1702..e105ffe6b6e3 100644

index 4e3037dc1204..d72dd73388d1 100644
--- a/include/linux/kcov.h
+++ b/include/linux/kcov.h
@@ -12,17 +12,21 @@ enum kcov_mode {
/* Coverage collection is not enabled yet. */
KCOV_MODE_DISABLED = 0,
/* KCOV was initialized, but tracing mode hasn't been chosen yet. */
- KCOV_MODE_INIT = 1,
+ KCOV_MODE_INIT_TRACE = 1,
+ /* KCOV was initialized, but recording of unique PCs hasn't been chosen yet. */
+ KCOV_MODE_INIT_UNQIUE = 2,
/*
* Tracing coverage collection mode.
* Covered PCs are collected in a per-task buffer.
*/
- KCOV_MODE_TRACE_PC = 2,
+ KCOV_MODE_TRACE_PC = 4,

/* Collecting comparison operands mode. */
- KCOV_MODE_TRACE_CMP = 3,

+ KCOV_MODE_TRACE_CMP = 8,

+ /* Collecting unique covered PCs. Execution order is not saved. */

+ KCOV_MODE_UNIQUE_PC = 16,
};

-#define KCOV_IN_CTXSW (1 << 30)
+#define KCOV_IN_CTXSW (1 << 31)

void kcov_task_init(struct task_struct *t);
void kcov_task_exit(struct task_struct *t);

index 80bfe71bbe13..1f727043146a 100644

--- a/kernel/kcov.c
+++ b/kernel/kcov.c
@@ -24,6 +24,7 @@
#include <linux/refcount.h>
#include <linux/log2.h>
#include <asm/setup.h>
+#include <asm/sections.h>

#define kcov_debug(fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)

@@ -151,10 +152,8 @@ static void kcov_remote_area_put(struct kcov_remote_area *area,
list_add(&area->list, &kcov_remote_areas);
}

-static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_struct *t)
+static __always_inline notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_struct *t, unsigned int *mode)
{
- unsigned int mode;
-
/*
* We are interested in code coverage as a function of a syscall inputs,
* so we ignore code executed in interrupts, unless we are in a remote
@@ -162,7 +161,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru
*/
if (!in_task() && !(in_serving_softirq() && t->kcov_softirq))
return false;
- mode = READ_ONCE(t->kcov_mode);
+ *mode = READ_ONCE(t->kcov_mode);
/*
* There is some code that runs in interrupts but for which
* in_interrupt() returns false (e.g. preempt_schedule_irq()).
@@ -171,7 +170,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru

* kcov_start().
*/
barrier();
- return mode == needed_mode;

+ return ((int)(*mode & (KCOV_IN_CTXSW | needed_mode))) > 0;

}

static notrace unsigned long canonicalize_ip(unsigned long ip)

@@ -191,18 +190,27 @@ void notrace __sanitizer_cov_trace_pc(void)

struct task_struct *t;
unsigned long *area;
unsigned long ip = canonicalize_ip(_RET_IP_);
- unsigned long pos;
+ unsigned long pos, idx;

+ unsigned int mode;

t = current;
- if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))

+ if (!check_kcov_mode(KCOV_MODE_TRACE_PC | KCOV_MODE_UNIQUE_PC, t, &mode))

return;

area = t->kcov_area;
- /* The first 64-bit word is the number of subsequent PCs. */
- pos = READ_ONCE(area[0]) + 1;
- if (likely(pos < t->kcov_size)) {
- area[pos] = ip;
- WRITE_ONCE(area[0], pos);

+ if (likely(mode == KCOV_MODE_TRACE_PC)) {

+ /* The first 64-bit word is the number of subsequent PCs. */
+ pos = READ_ONCE(area[0]) + 1;
+ if (likely(pos < t->kcov_size)) {
+ area[pos] = ip;

+ WRITE_ONCE(area[0], pos);
+ }

+ } else {
+ idx = (ip - canonicalize_ip((unsigned long)&_stext)) / 4;
+ pos = idx % BITS_PER_LONG;
+ idx /= BITS_PER_LONG;
+ if (likely(idx < t->kcov_size))
+ WRITE_ONCE(area[idx], READ_ONCE(area[idx]) | 1L << pos);
}
}
EXPORT_SYMBOL(__sanitizer_cov_trace_pc);

@@ -213,9 +221,10 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)
struct task_struct *t;
u64 *area;
u64 count, start_index, end_pos, max_pos;
+ unsigned int mode;

t = current;
- if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t))
+ if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t, &mode))
return;

ip = canonicalize_ip(ip);
@@ -362,7 +371,7 @@ void kcov_task_init(struct task_struct *t)
static void kcov_reset(struct kcov *kcov)
{
kcov->t = NULL;
- kcov->mode = KCOV_MODE_INIT;
+ kcov->mode = KCOV_MODE_INIT_TRACE;
kcov->remote = false;
kcov->remote_size = 0;
kcov->sequence++;
@@ -468,12 +477,13 @@ static int kcov_mmap(struct file *filep, struct vm_area_struct *vma)

spin_lock_irqsave(&kcov->lock, flags);
size = kcov->size * sizeof(unsigned long);
- if (kcov->mode != KCOV_MODE_INIT || vma->vm_pgoff != 0 ||
+ if (kcov->mode & ~(KCOV_INIT_TRACE | KCOV_INIT_UNIQUE) || vma->vm_pgoff != 0 ||
vma->vm_end - vma->vm_start != size) {
res = -EINVAL;

goto exit;
}
if (!kcov->area) {
+ kcov_debug("mmap(): Allocating 0x%lx bytes\n", size);
kcov->area = area;
vma->vm_flags |= VM_DONTEXPAND;
spin_unlock_irqrestore(&kcov->lock, flags);
@@ -515,6 +525,8 @@ static int kcov_get_mode(unsigned long arg)
{
if (arg == KCOV_TRACE_PC)
return KCOV_MODE_TRACE_PC;
+ else if (arg == KCOV_UNIQUE_PC)
+ return KCOV_MODE_UNIQUE_PC;

else if (arg == KCOV_TRACE_CMP)
#ifdef CONFIG_KCOV_ENABLE_COMPARISONS
return KCOV_MODE_TRACE_CMP;

@@ -562,12 +574,14 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
{
struct task_struct *t;

unsigned long size, unused;
- int mode, i;
+ int mode, i, text_size, ret = 0;
struct kcov_remote_arg *remote_arg;
struct kcov_remote *remote;
unsigned long flags;

switch (cmd) {
+ case KCOV_INIT_UNIQUE:

+ /* fallthrough here */

case KCOV_INIT_TRACE:
/*
* Enable kcov in trace mode and setup buffer size.

@@ -581,11 +595,41 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

* that must not overflow.
*/
size = arg;
- if (size < 2 || size > INT_MAX / sizeof(unsigned long))
- return -EINVAL;
- kcov->size = size;

- kcov->mode = KCOV_MODE_INIT;
- return 0;

+ if (cmd == KCOV_INIT_UNIQUE) {
+ if (size != 0)
+ return -EINVAL;
+ text_size = (canonicalize_ip((unsigned long)&_etext) - canonicalize_ip((unsigned long)&_stext));
+ /**
+ * A call instr is at least four bytes on every supported architecture.
+ * Hence, just every fourth instruction can potentially be a call.
+ */

+ text_size = roundup(text_size, 4);
+ text_size /= 4;

+ /*
+ * Round up size of text segment to multiple of BITS_PER_LONG.
+ * Otherwise, we cannot track
+ * the last (text_size % BITS_PER_LONG) addresses.
+ */
+ text_size = roundup(text_size, BITS_PER_LONG);
+ /* Get the amount of bytes needed */
+ text_size = text_size / 8;
+ /* mmap() requires size to be a multiple of PAGE_SIZE */
+ text_size = roundup(text_size, PAGE_SIZE);

+ /* Get the cover size (= amount of bytes stored) */

+ ret = text_size;
+ kcov->size = text_size / sizeof(unsigned long);
+ kcov_debug("text size = 0x%lx, roundup = 0x%x, kcov->size = 0x%x\n",
+ ((unsigned long)&_etext) - ((unsigned long)&_stext),
+ text_size,
+ kcov->size);

+ kcov->mode = KCOV_INIT_UNIQUE;

+ } else {
+ if (size < 2 || size > INT_MAX / sizeof(unsigned long))
+ return -EINVAL;
+ kcov->size = size;

+ kcov->mode = KCOV_INIT_TRACE;
+ }

+ return ret;
case KCOV_ENABLE:
/*
* Enable coverage for the current task.

@@ -594,7 +638,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
* at task exit or voluntary by KCOV_DISABLE. After that it can
* be enabled for another task.
*/
- if (kcov->mode != KCOV_MODE_INIT || !kcov->area)
+ if (!kcov->area)
return -EINVAL;
t = current;
if (kcov->t != NULL || t->kcov != NULL)
@@ -602,6 +646,10 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
mode = kcov_get_mode(arg);
if (mode < 0)
return mode;
+ if (kcov->mode == KCOV_INIT_TRACE && mode == KCOV_MODE_UNIQUE_PC)
+ return -EINVAL;
+ if (kcov->mode == KCOV_INIT_UNIQUE && (mode & (KCOV_MODE_TRACE_PC | KCOV_MODE_TRACE_CMP)))
+ return -EINVAL;
kcov_fault_in_area(kcov);
kcov->mode = mode;
kcov_start(t, kcov, kcov->size, kcov->area, kcov->mode,
@@ -622,7 +670,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
kcov_put(kcov);
return 0;
case KCOV_REMOTE_ENABLE:
- if (kcov->mode != KCOV_MODE_INIT || !kcov->area)
+ if (kcov->mode != KCOV_MODE_INIT_TRACE || !kcov->area)
return -EINVAL;
t = current;
if (kcov->t != NULL || t->kcov != NULL)
--
2.30.2

[Miguel Ojeda]

Hi Alexander,

On Sun, Mar 21, 2021 at 8:14 PM Alexander Lochmann
<in...@alexander-lochmann.de> wrote:
>
> diff --git a/Documentation/dev-tools/kcov.rst b/Documentation/dev-tools/kcov.rst
> index d2c4c27e1702..e105ffe6b6e3 100644
> --- a/Documentation/dev-tools/kcov.rst
> +++ b/Documentation/dev-tools/kcov.rst
> @@ -127,6 +127,86 @@ That is, a parent process opens /sys/kernel/debug/kcov, enables trace mode,
> mmaps coverage buffer and then forks child processes in a loop. Child processes
> only need to enable coverage (disable happens automatically on thread end).
>
> +If someone is interested in a set of executed PCs, and does not care about
> +execution order, he or she can advise KCOV to do so:

Please mention explicitly that KCOV_INIT_UNIQUE should be used for
that, i.e. readers of the example shouldn't need to read every line to
figure it out.

> + #define KCOV_INIT_TRACE _IOR('c', 1, unsigned long)

Trace is not used in the example.

> + /* KCOV was initialized, but recording of unique PCs hasn't been chosen yet. */
> + KCOV_MODE_INIT_UNQIUE = 2,

Typo? It isn't used?

PS: not sure why I was Cc'd, but I hope that helps.

Cheers,
Miguel

[Alexander Lochmann]

It is a typo. It should be used...

>
> PS: not sure why I was Cc'd, but I hope that helps.

Thx for your feedback. get_maintainer.pl told me to include you in Cc.

Cheers,
Alex
>
> Cheers,
> Miguel

[Dmitry Vyukov]

Is this for __always_inline?
__always_inline is defined in include/linux/compiler_types.h.

This logic and the rest of the patch looks good to me.

Thanks

Looking at "git log --grep fallthrough", it seems that the modern way
to say this is to use the fallthrough keyword.

Please run checkpatch, it shows a bunch of other warnings as well:

git diff HEAD^ | scripts/checkpatch.pl -

[Alexander Lochmann]

On 23.03.21 08:23, Dmitry Vyukov wrote:
>> diff --git a/kernel/kcov.c b/kernel/kcov.c
>> index 80bfe71bbe13..1f727043146a 100644
>> --- a/kernel/kcov.c
>> +++ b/kernel/kcov.c
>> @@ -24,6 +24,7 @@
>> #include <linux/refcount.h>
>> #include <linux/log2.h>
>> #include <asm/setup.h>
>> +#include <asm/sections.h>
>
> Is this for __always_inline?
> __always_inline is defined in include/linux/compiler_types.h.
>

This is for the symbols marking start and end of the text segment
(_stext/_etext).

Thx.

Yeah. I'll do that.

[Alexander Lochmann]

It simply stores the executed PCs.
The execution order is discarded.
Each bit in the shared buffer represents every fourth
byte of the text segment.
Since a call instruction on every supported
architecture is at least four bytes, it is safe
to just store every fourth byte of the text segment.
In contrast to KCOV_MODE_TRACE_PC, the shared buffer
cannot overflow. Thus, all executed PCs are recorded.

Signed-off-by: Alexander Lochmann <in...@alexander-lochmann.de>
---

Documentation/dev-tools/kcov.rst | 79 +++++++++++++++++++++++++

include/linux/kcov.h | 12 ++--
include/uapi/linux/kcov.h | 10 ++++

kernel/kcov.c | 98 ++++++++++++++++++++++++--------
4 files changed, 172 insertions(+), 27 deletions(-)

diff --git a/Documentation/dev-tools/kcov.rst b/Documentation/dev-tools/kcov.rst
index d2c4c27e1702..9b0df2f8474c 100644
--- a/Documentation/dev-tools/kcov.rst
+++ b/Documentation/dev-tools/kcov.rst
@@ -127,6 +127,85 @@ That is, a parent process opens /sys/kernel/debug/kcov, enables trace mode,

mmaps coverage buffer and then forks child processes in a loop. Child processes
only need to enable coverage (disable happens automatically on thread end).

+If someone is interested in a set of executed PCs, and does not care about

+execution order, he or she can use KCOV_INIT_UNIQUE to do so:

+
+.. code-block:: c
+
+ #include <stdio.h>
+ #include <stddef.h>
+ #include <stdint.h>
+ #include <stdlib.h>
+ #include <sys/types.h>
+ #include <sys/stat.h>
+ #include <sys/ioctl.h>
+ #include <sys/mman.h>
+ #include <unistd.h>
+ #include <fcntl.h>
+

index 4e3037dc1204..99c309b3a53b 100644

--- a/include/linux/kcov.h
+++ b/include/linux/kcov.h
@@ -12,17 +12,21 @@ enum kcov_mode {
/* Coverage collection is not enabled yet. */
KCOV_MODE_DISABLED = 0,
/* KCOV was initialized, but tracing mode hasn't been chosen yet. */
- KCOV_MODE_INIT = 1,
+ KCOV_MODE_INIT_TRACE = 1,
+ /* KCOV was initialized, but recording of unique PCs hasn't been chosen yet. */

+ KCOV_MODE_INIT_UNIQUE = 2,

diff --git a/kernel/kcov.c b/kernel/kcov.c
index 80bfe71bbe13..9d64d672a5dc 100644

--- a/kernel/kcov.c
+++ b/kernel/kcov.c
@@ -24,6 +24,7 @@
#include <linux/refcount.h>
#include <linux/log2.h>
#include <asm/setup.h>
+#include <asm/sections.h>

#define kcov_debug(fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)

@@ -151,10 +152,10 @@ static void kcov_remote_area_put(struct kcov_remote_area *area,

list_add(&area->list, &kcov_remote_areas);
}

-static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_struct *t)
+static __always_inline notrace bool check_kcov_mode(enum kcov_mode needed_mode,

+ struct task_struct *t,
+ unsigned int *mode)

{
- unsigned int mode;
-
/*
* We are interested in code coverage as a function of a syscall inputs,
* so we ignore code executed in interrupts, unless we are in a remote

@@ -162,7 +163,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru

*/
if (!in_task() && !(in_serving_softirq() && t->kcov_softirq))
return false;
- mode = READ_ONCE(t->kcov_mode);
+ *mode = READ_ONCE(t->kcov_mode);
/*
* There is some code that runs in interrupts but for which
* in_interrupt() returns false (e.g. preempt_schedule_irq()).

@@ -171,7 +172,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru

* kcov_start().
*/
barrier();
- return mode == needed_mode;
+ return ((int)(*mode & (KCOV_IN_CTXSW | needed_mode))) > 0;
}

static notrace unsigned long canonicalize_ip(unsigned long ip)

@@ -191,18 +192,27 @@ void notrace __sanitizer_cov_trace_pc(void)

@@ -213,9 +223,10 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)

struct task_struct *t;
u64 *area;
u64 count, start_index, end_pos, max_pos;
+ unsigned int mode;

t = current;
- if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t))
+ if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t, &mode))
return;

ip = canonicalize_ip(ip);

@@ -362,7 +373,7 @@ void kcov_task_init(struct task_struct *t)

static void kcov_reset(struct kcov *kcov)
{
kcov->t = NULL;
- kcov->mode = KCOV_MODE_INIT;
+ kcov->mode = KCOV_MODE_INIT_TRACE;
kcov->remote = false;
kcov->remote_size = 0;
kcov->sequence++;

@@ -468,12 +479,13 @@ static int kcov_mmap(struct file *filep, struct vm_area_struct *vma)

spin_lock_irqsave(&kcov->lock, flags);
size = kcov->size * sizeof(unsigned long);
- if (kcov->mode != KCOV_MODE_INIT || vma->vm_pgoff != 0 ||

+ if (kcov->mode & ~(KCOV_MODE_INIT_TRACE | KCOV_MODE_INIT_UNIQUE) || vma->vm_pgoff != 0 ||

vma->vm_end - vma->vm_start != size) {
res = -EINVAL;
goto exit;
}
if (!kcov->area) {
+ kcov_debug("mmap(): Allocating 0x%lx bytes\n", size);
kcov->area = area;
vma->vm_flags |= VM_DONTEXPAND;
spin_unlock_irqrestore(&kcov->lock, flags);

@@ -515,6 +527,8 @@ static int kcov_get_mode(unsigned long arg)

{
if (arg == KCOV_TRACE_PC)
return KCOV_MODE_TRACE_PC;
+ else if (arg == KCOV_UNIQUE_PC)
+ return KCOV_MODE_UNIQUE_PC;
else if (arg == KCOV_TRACE_CMP)
#ifdef CONFIG_KCOV_ENABLE_COMPARISONS
return KCOV_MODE_TRACE_CMP;

@@ -562,12 +576,14 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

{
struct task_struct *t;
unsigned long size, unused;
- int mode, i;
+ int mode, i, text_size, ret = 0;
struct kcov_remote_arg *remote_arg;
struct kcov_remote *remote;
unsigned long flags;

switch (cmd) {
+ case KCOV_INIT_UNIQUE:

+ fallthrough;

case KCOV_INIT_TRACE:
/*
* Enable kcov in trace mode and setup buffer size.

@@ -581,11 +597,42 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

* that must not overflow.
*/
size = arg;
- if (size < 2 || size > INT_MAX / sizeof(unsigned long))
- return -EINVAL;
- kcov->size = size;

- kcov->mode = KCOV_MODE_INIT;

- return 0;
+ if (cmd == KCOV_INIT_UNIQUE) {
+ if (size != 0)
+ return -EINVAL;
+ text_size = (canonicalize_ip((unsigned long)&_etext)

+ - canonicalize_ip((unsigned long)&_stext));

+ /**
+ * A call instr is at least four bytes on every supported architecture.
+ * Hence, just every fourth instruction can potentially be a call.
+ */
+ text_size = roundup(text_size, 4);
+ text_size /= 4;
+ /*
+ * Round up size of text segment to multiple of BITS_PER_LONG.
+ * Otherwise, we cannot track
+ * the last (text_size % BITS_PER_LONG) addresses.
+ */
+ text_size = roundup(text_size, BITS_PER_LONG);
+ /* Get the amount of bytes needed */
+ text_size = text_size / 8;
+ /* mmap() requires size to be a multiple of PAGE_SIZE */
+ text_size = roundup(text_size, PAGE_SIZE);
+ /* Get the cover size (= amount of bytes stored) */
+ ret = text_size;
+ kcov->size = text_size / sizeof(unsigned long);
+ kcov_debug("text size = 0x%lx, roundup = 0x%x, kcov->size = 0x%x\n",
+ ((unsigned long)&_etext) - ((unsigned long)&_stext),
+ text_size,
+ kcov->size);

+ kcov->mode = KCOV_MODE_INIT_UNIQUE;

+ } else {
+ if (size < 2 || size > INT_MAX / sizeof(unsigned long))
+ return -EINVAL;
+ kcov->size = size;

+ kcov->mode = KCOV_MODE_INIT_TRACE;

+ }
+ return ret;
case KCOV_ENABLE:
/*
* Enable coverage for the current task.

@@ -594,7 +641,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

* at task exit or voluntary by KCOV_DISABLE. After that it can
* be enabled for another task.
*/
- if (kcov->mode != KCOV_MODE_INIT || !kcov->area)
+ if (!kcov->area)
return -EINVAL;
t = current;
if (kcov->t != NULL || t->kcov != NULL)

@@ -602,6 +649,11 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

mode = kcov_get_mode(arg);
if (mode < 0)
return mode;

+ if (kcov->mode == KCOV_MODE_INIT_TRACE && mode == KCOV_MODE_UNIQUE_PC)
+ return -EINVAL;
+ if (kcov->mode == KCOV_MODE_INIT_UNIQUE &&
+ (mode & (KCOV_MODE_TRACE_PC | KCOV_MODE_TRACE_CMP)))

+ return -EINVAL;
kcov_fault_in_area(kcov);
kcov->mode = mode;
kcov_start(t, kcov, kcov->size, kcov->area, kcov->mode,

@@ -622,7 +674,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

[Greg Kroah-Hartman]

On Fri, Mar 26, 2021 at 09:51:28PM +0100, Alexander Lochmann wrote:
> It simply stores the executed PCs.
> The execution order is discarded.
> Each bit in the shared buffer represents every fourth
> byte of the text segment.
> Since a call instruction on every supported
> architecture is at least four bytes, it is safe
> to just store every fourth byte of the text segment.
> In contrast to KCOV_MODE_TRACE_PC, the shared buffer
> cannot overflow. Thus, all executed PCs are recorded.

Odd line-wrapping :(

Anyway, this describes _what_ this does, but I have no idea _why_ we
want this at all. What does this do that you can not do today? Why is
this needed? Who will use this? What tools have been modified to work
with it to prove it works properly?

thanks,

greg k-h

[Andrey Konovalov]

On Fri, Mar 26, 2021 at 9:52 PM Alexander Lochmann
<in...@alexander-lochmann.de> wrote:
>

Hi Alexander,

> It simply stores the executed PCs.
> The execution order is discarded.
> Each bit in the shared buffer represents every fourth
> byte of the text segment.
> Since a call instruction on every supported
> architecture is at least four bytes, it is safe
> to just store every fourth byte of the text segment.

What about jumps?

[...]

> -#define KCOV_IN_CTXSW (1 << 30)
> +#define KCOV_IN_CTXSW (1 << 31)

This change needs to be mentioned and explained in the changelog.

> -static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_struct *t)
> +static __always_inline notrace bool check_kcov_mode(enum kcov_mode needed_mode,
> + struct task_struct *t,
> + unsigned int *mode)
> {
> - unsigned int mode;
> -
> /*
> * We are interested in code coverage as a function of a syscall inputs,
> * so we ignore code executed in interrupts, unless we are in a remote
> @@ -162,7 +163,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru
> */
> if (!in_task() && !(in_serving_softirq() && t->kcov_softirq))
> return false;
> - mode = READ_ONCE(t->kcov_mode);
> + *mode = READ_ONCE(t->kcov_mode);
> /*
> * There is some code that runs in interrupts but for which
> * in_interrupt() returns false (e.g. preempt_schedule_irq()).
> @@ -171,7 +172,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru
> * kcov_start().
> */
> barrier();
> - return mode == needed_mode;
> + return ((int)(*mode & (KCOV_IN_CTXSW | needed_mode))) > 0;

This change needs to be mentioned and explained in the changelog.

[...]

This is confusing: for KCOV_MODE_TRACE_PC, pos is used to index area,
and for else, idx is used to index area. You should swap idx and pos.

[...]

> @@ -213,9 +223,10 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)
> struct task_struct *t;
> u64 *area;
> u64 count, start_index, end_pos, max_pos;
> + unsigned int mode;
>
> t = current;
> - if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t))
> + if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t, &mode))
> return;

mode isn't used here, right? No need for it then.

> @@ -562,12 +576,14 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
> {
> struct task_struct *t;
> unsigned long size, unused;
> - int mode, i;
> + int mode, i, text_size, ret = 0;
> struct kcov_remote_arg *remote_arg;
> struct kcov_remote *remote;
> unsigned long flags;
>
> switch (cmd) {
> + case KCOV_INIT_UNIQUE:
> + fallthrough;
> case KCOV_INIT_TRACE:
> /*
> * Enable kcov in trace mode and setup buffer size.
> @@ -581,11 +597,42 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,
> * that must not overflow.
> */
> size = arg;
> - if (size < 2 || size > INT_MAX / sizeof(unsigned long))
> - return -EINVAL;
> - kcov->size = size;
> - kcov->mode = KCOV_MODE_INIT;
> - return 0;
> + if (cmd == KCOV_INIT_UNIQUE) {

Let's put this code under KCOV_INIT_UNIQUE in the switch. This
internal if only saves duplicating two lines of code, which isn't
worth it.

Thanks!

[Dmitry Vyukov]

On Sat, Mar 27, 2021 at 3:56 PM Andrey Konovalov <andre...@gmail.com> wrote:
>
> On Fri, Mar 26, 2021 at 9:52 PM Alexander Lochmann
> <in...@alexander-lochmann.de> wrote:
> >
>
> Hi Alexander,
>
> > It simply stores the executed PCs.
> > The execution order is discarded.
> > Each bit in the shared buffer represents every fourth
> > byte of the text segment.
> > Since a call instruction on every supported
> > architecture is at least four bytes, it is safe
> > to just store every fourth byte of the text segment.
>
> What about jumps?

KCOV adds call __sanitizer_cov_trace_pc per coverage point. So besides
the instructions in the original code, we also always have this call.

> --
> You received this message because you are subscribed to the Google Groups "kasan-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kasan-dev+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kasan-dev/CA%2BfCnZcTi%3DQLGC_LCdhs%2BfMrxkqX66kXEuM5ewOmjVjifKzUrw%40mail.gmail.com.

[Andrey Konovalov]

On Fri, Apr 16, 2021 at 10:42 AM Dmitry Vyukov <dvy...@google.com> wrote:
>
> On Sat, Mar 27, 2021 at 3:56 PM Andrey Konovalov <andre...@gmail.com> wrote:
> >
> > On Fri, Mar 26, 2021 at 9:52 PM Alexander Lochmann
> > <in...@alexander-lochmann.de> wrote:
> > >
> >
> > Hi Alexander,
> >
> > > It simply stores the executed PCs.
> > > The execution order is discarded.
> > > Each bit in the shared buffer represents every fourth
> > > byte of the text segment.
> > > Since a call instruction on every supported
> > > architecture is at least four bytes, it is safe
> > > to just store every fourth byte of the text segment.
> >
> > What about jumps?
>
> KCOV adds call __sanitizer_cov_trace_pc per coverage point. So besides
> the instructions in the original code, we also always have this call.

Ah, I see. This should be explained in the changelog.

This means that a KCOV user will need the kernel binary to recover the
actual PCs that were covered, as the information about the lower two
bits is lost, right? This needs to be explained as well.

Thanks!

[Alexander Lochmann]

On 27.03.21 15:56, Andrey Konovalov wrote:
>
>> @@ -213,9 +223,10 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)
>> struct task_struct *t;
>> u64 *area;
>> u64 count, start_index, end_pos, max_pos;
>> + unsigned int mode;
>>
>> t = current;
>> - if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t))
>> + if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t, &mode))
>> return;
>
> mode isn't used here, right? No need for it then.
>

No, it's not. However, check_kcov_mode() needs it. Dmitry suggested
passing a pointer to check_kcov_mode(), and let the optimizer do the rest.

So. Shall I skip the fallthrough and move 'my' code upwards?

[Alexander Lochmann]

The existing trace mode stores PCs in execution order. This could lead
to a buffer overflow if sufficient amonut of kernel code is executed.
Thus, a user might not see all executed PCs. KCOV_MODE_UNIQUE favors
completeness over execution order. While ignoring the execution order,
it marks a PC as exectued by setting a bit representing that PC. Each

bit in the shared buffer represents every fourth byte of the text
segment. Since a call instruction on every supported architecture is
at least four bytes, it is safe to just store every fourth byte of the
text segment.

Prior to above changes, a comparison of the current kcov mode with
KCOV_IN_CTXSW set would evaluate to false, and tracing does not take
place. Since the kcov mode is now a bit mask, simply setting
KCOV_IN_CTXSW isn't sufficient anymore for the comparison to turn
false. With KCOV_IN_CTXSW being the MSB, the following comparison will
be less than zero:

((int)(*mode & (KCOV_IN_CTXSW | needed_mode))) > 0

This restores the previous semantics: When KCOV_IN_CTXSW is set,
tracing does not take place.

We have used this mode so far to perform coverage analysis on the Linux
Test Project: http://dx.doi.org/10.18420/fgbs2020h-01. Since LTP's
testsuites are considerably large, we experienced buffer overflows with
KCOVE_MODE_TRACE_PC.

Signed-off-by: Alexander Lochmann <in...@alexander-lochmann.de>
---

Documentation/dev-tools/kcov.rst | 79 +++++++++++++++++++++++++++
include/linux/kcov.h | 12 +++--
include/uapi/linux/kcov.h | 10 ++++
kernel/kcov.c | 93 +++++++++++++++++++++++++-------
4 files changed, 171 insertions(+), 23 deletions(-)

index 55dc338f6bcd..e2c0f7cc16a1 100644
--- a/include/linux/kcov.h
+++ b/include/linux/kcov.h
@@ -13,17 +13,21 @@ enum kcov_mode {

/* Coverage collection is not enabled yet. */
KCOV_MODE_DISABLED = 0,
/* KCOV was initialized, but tracing mode hasn't been chosen yet. */
- KCOV_MODE_INIT = 1,
+ KCOV_MODE_INIT_TRACE = 1,
+ /* KCOV was initialized, but recording of unique PCs hasn't been chosen yet. */
+ KCOV_MODE_INIT_UNIQUE = 2,
/*
* Tracing coverage collection mode.
* Covered PCs are collected in a per-task buffer.
*/
- KCOV_MODE_TRACE_PC = 2,
+ KCOV_MODE_TRACE_PC = 4,
/* Collecting comparison operands mode. */
- KCOV_MODE_TRACE_CMP = 3,
+ KCOV_MODE_TRACE_CMP = 8,
+ /* Collecting unique covered PCs. Execution order is not saved. */
+ KCOV_MODE_UNIQUE_PC = 16,
};

-#define KCOV_IN_CTXSW (1 << 30)
+#define KCOV_IN_CTXSW (1 << 31)

index 80bfe71bbe13..578f07f28428 100644

--- a/kernel/kcov.c
+++ b/kernel/kcov.c
@@ -24,6 +24,7 @@
#include <linux/refcount.h>
#include <linux/log2.h>
#include <asm/setup.h>
+#include <asm/sections.h>

#define kcov_debug(fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)

@@ -151,10 +152,10 @@ static void kcov_remote_area_put(struct kcov_remote_area *area,
list_add(&area->list, &kcov_remote_areas);
}

-static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_struct *t)
+static __always_inline notrace bool check_kcov_mode(enum kcov_mode needed_mode,
+ struct task_struct *t,
+ unsigned int *mode)
{
- unsigned int mode;
-
/*
* We are interested in code coverage as a function of a syscall inputs,
* so we ignore code executed in interrupts, unless we are in a remote
@@ -162,7 +163,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru
*/
if (!in_task() && !(in_serving_softirq() && t->kcov_softirq))
return false;
- mode = READ_ONCE(t->kcov_mode);
+ *mode = READ_ONCE(t->kcov_mode);
/*
* There is some code that runs in interrupts but for which
* in_interrupt() returns false (e.g. preempt_schedule_irq()).
@@ -171,7 +172,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_stru
* kcov_start().
*/
barrier();
- return mode == needed_mode;
+ return ((int)(*mode & (KCOV_IN_CTXSW | needed_mode))) > 0;
}

static notrace unsigned long canonicalize_ip(unsigned long ip)
@@ -191,18 +192,27 @@ void notrace __sanitizer_cov_trace_pc(void)

struct task_struct *t;

unsigned long *area;
unsigned long ip = canonicalize_ip(_RET_IP_);
- unsigned long pos;
+ unsigned long pos, idx;

+ unsigned int mode;

t = current;

- if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))
+ if (!check_kcov_mode(KCOV_MODE_TRACE_PC | KCOV_MODE_UNIQUE_PC, t, &mode))
return;

area = t->kcov_area;
- /* The first 64-bit word is the number of subsequent PCs. */
- pos = READ_ONCE(area[0]) + 1;
- if (likely(pos < t->kcov_size)) {
- area[pos] = ip;
- WRITE_ONCE(area[0], pos);
+ if (likely(mode == KCOV_MODE_TRACE_PC)) {
+ /* The first 64-bit word is the number of subsequent PCs. */
+ pos = READ_ONCE(area[0]) + 1;
+ if (likely(pos < t->kcov_size)) {
+ area[pos] = ip;
+ WRITE_ONCE(area[0], pos);
+ }
+ } else {

+ pos = (ip - canonicalize_ip((unsigned long)&_stext)) / 4;
+ idx = pos % BITS_PER_LONG;
+ pos /= BITS_PER_LONG;

+ if (likely(pos < t->kcov_size))

+ WRITE_ONCE(area[pos], READ_ONCE(area[pos]) | 1L << idx);
}
}
EXPORT_SYMBOL(__sanitizer_cov_trace_pc);

@@ -213,9 +223,10 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)
struct task_struct *t;
u64 *area;
u64 count, start_index, end_pos, max_pos;
+ unsigned int mode;

t = current;
- if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t))
+ if (!check_kcov_mode(KCOV_MODE_TRACE_CMP, t, &mode))
return;

ip = canonicalize_ip(ip);
@@ -362,7 +373,7 @@ void kcov_task_init(struct task_struct *t)
static void kcov_reset(struct kcov *kcov)
{
kcov->t = NULL;

- kcov->mode = KCOV_MODE_INIT;

+ kcov->mode = KCOV_MODE_INIT_TRACE;

kcov->remote = false;
kcov->remote_size = 0;
kcov->sequence++;
@@ -468,12 +479,13 @@ static int kcov_mmap(struct file *filep, struct vm_area_struct *vma)

spin_lock_irqsave(&kcov->lock, flags);
size = kcov->size * sizeof(unsigned long);
- if (kcov->mode != KCOV_MODE_INIT || vma->vm_pgoff != 0 ||
+ if (kcov->mode & ~(KCOV_MODE_INIT_TRACE | KCOV_MODE_INIT_UNIQUE) || vma->vm_pgoff != 0 ||
vma->vm_end - vma->vm_start != size) {
res = -EINVAL;
goto exit;
}
if (!kcov->area) {
+ kcov_debug("mmap(): Allocating 0x%lx bytes\n", size);
kcov->area = area;
vma->vm_flags |= VM_DONTEXPAND;
spin_unlock_irqrestore(&kcov->lock, flags);
@@ -515,6 +527,8 @@ static int kcov_get_mode(unsigned long arg)
{
if (arg == KCOV_TRACE_PC)
return KCOV_MODE_TRACE_PC;
+ else if (arg == KCOV_UNIQUE_PC)
+ return KCOV_MODE_UNIQUE_PC;
else if (arg == KCOV_TRACE_CMP)
#ifdef CONFIG_KCOV_ENABLE_COMPARISONS
return KCOV_MODE_TRACE_CMP;

@@ -562,12 +576,48 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

{
struct task_struct *t;
unsigned long size, unused;
- int mode, i;

+ int mode, i, text_size;

struct kcov_remote_arg *remote_arg;
struct kcov_remote *remote;
unsigned long flags;

switch (cmd) {
+ case KCOV_INIT_UNIQUE:

+ /*
+ * Enable kcov in trace mode and setup buffer size.
+ * Must happen before anything else.
+ */
+ if (kcov->mode != KCOV_MODE_DISABLED)
+ return -EBUSY;
+ size = arg;

+ if (size != 0)
+ return -EINVAL;
+ text_size = (canonicalize_ip((unsigned long)&_etext)
+ - canonicalize_ip((unsigned long)&_stext));
+ /**
+ * A call instr is at least four bytes on every supported architecture.
+ * Hence, just every fourth instruction can potentially be a call.
+ */
+ text_size = roundup(text_size, 4);
+ text_size /= 4;
+ /*
+ * Round up size of text segment to multiple of BITS_PER_LONG.
+ * Otherwise, we cannot track
+ * the last (text_size % BITS_PER_LONG) addresses.
+ */
+ text_size = roundup(text_size, BITS_PER_LONG);
+ /* Get the amount of bytes needed */
+ text_size = text_size / 8;
+ /* mmap() requires size to be a multiple of PAGE_SIZE */
+ text_size = roundup(text_size, PAGE_SIZE);
+ /* Get the cover size (= amount of bytes stored) */

+ kcov->size = text_size / sizeof(unsigned long);
+ kcov_debug("text size = 0x%lx, roundup = 0x%x, kcov->size = 0x%x\n",
+ ((unsigned long)&_etext) - ((unsigned long)&_stext),
+ text_size,
+ kcov->size);
+ kcov->mode = KCOV_MODE_INIT_UNIQUE;

+ return text_size;

case KCOV_INIT_TRACE:
/*
* Enable kcov in trace mode and setup buffer size.

@@ -584,7 +634,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

if (size < 2 || size > INT_MAX / sizeof(unsigned long))

return -EINVAL;

kcov->size = size;
- kcov->mode = KCOV_MODE_INIT;

+ kcov->mode = KCOV_MODE_INIT_TRACE;

return 0;
case KCOV_ENABLE:
/*
@@ -594,7 +644,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

* at task exit or voluntary by KCOV_DISABLE. After that it can
* be enabled for another task.
*/
- if (kcov->mode != KCOV_MODE_INIT || !kcov->area)
+ if (!kcov->area)
return -EINVAL;
t = current;
if (kcov->t != NULL || t->kcov != NULL)

@@ -602,6 +652,11 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

mode = kcov_get_mode(arg);
if (mode < 0)
return mode;
+ if (kcov->mode == KCOV_MODE_INIT_TRACE && mode == KCOV_MODE_UNIQUE_PC)
+ return -EINVAL;
+ if (kcov->mode == KCOV_MODE_INIT_UNIQUE &&
+ (mode & (KCOV_MODE_TRACE_PC | KCOV_MODE_TRACE_CMP)))
+ return -EINVAL;
kcov_fault_in_area(kcov);
kcov->mode = mode;
kcov_start(t, kcov, kcov->size, kcov->area, kcov->mode,

@@ -622,7 +677,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,

kcov_put(kcov);
return 0;
case KCOV_REMOTE_ENABLE:
- if (kcov->mode != KCOV_MODE_INIT || !kcov->area)
+ if (kcov->mode != KCOV_MODE_INIT_TRACE || !kcov->area)
return -EINVAL;
t = current;
if (kcov->t != NULL || t->kcov != NULL)
--

2.33.0

[Peter Zijlstra]

On Mon, Sep 27, 2021 at 07:33:40PM +0200, Alexander Lochmann wrote:
> The existing trace mode stores PCs in execution order. This could lead
> to a buffer overflow if sufficient amonut of kernel code is executed.
> Thus, a user might not see all executed PCs. KCOV_MODE_UNIQUE favors
> completeness over execution order. While ignoring the execution order,
> it marks a PC as exectued by setting a bit representing that PC. Each
> bit in the shared buffer represents every fourth byte of the text
> segment. Since a call instruction on every supported architecture is
> at least four bytes, it is safe to just store every fourth byte of the
> text segment.

I'm still trying to wake up, but why are call instruction more important
than other instructions? Specifically, I'd think any branch instruction
matters for coverage.

More specifically, x86 can do a tail call with just 2 bytes.

[Alexander Lochmann]

Maybe Dmitry can shed some light on this. He actually suggested that
optimization.

- Alex

[Dmitry Vyukov]

On Sat, 23 Oct 2021 at 00:03, Alexander Lochmann
<in...@alexander-lochmann.de> wrote:
>
> Maybe Dmitry can shed some light on this. He actually suggested that
> optimization.
>
> - Alex
>
> On 29.09.21 10:33, Peter Zijlstra wrote:
> > On Mon, Sep 27, 2021 at 07:33:40PM +0200, Alexander Lochmann wrote:
> >> The existing trace mode stores PCs in execution order. This could lead
> >> to a buffer overflow if sufficient amonut of kernel code is executed.
> >> Thus, a user might not see all executed PCs. KCOV_MODE_UNIQUE favors
> >> completeness over execution order. While ignoring the execution order,
> >> it marks a PC as exectued by setting a bit representing that PC. Each
> >> bit in the shared buffer represents every fourth byte of the text
> >> segment. Since a call instruction on every supported architecture is
> >> at least four bytes, it is safe to just store every fourth byte of the
> >> text segment.
> >
> > I'm still trying to wake up, but why are call instruction more important
> > than other instructions? Specifically, I'd think any branch instruction

> > matters for coverage.,

> >
> > More specifically, x86 can do a tail call with just 2 bytes.

Hi Peter, Alex,

The calls are important here because we only use PCs that are return
PCs from a callback emitted by the compiler. These PCs point to the
call of the callback.

I don't remember exactly what's the story for tail calls of the
callback for both compilers, ideally they should not use tail calls
for this call, and I think at least one of them does not use tail
calls.

But even with tail calls, the callback is emitted into every basic
block of code. So it should be (call, some other instructions, call)
and at least the first call is not a tail call.