RFC: coverage deduplication for KCOV
Subsystems (14)
Alexander Potapenko
reviewercover RFC: coverage deduplication for KCOV
As mentioned by Joey Jiao in [1], the current kcov implementation may suffer from certain syscalls overflowing the userspace coverage buffer.
According to our measurements, among 24 syzkaller instances running upstream Linux, 5 had a coverage overflow in at least 50% of executed programs. The median percentage of programs with overflows across those 24 instances was 8.8%.
One way to mitigate this problem is to increase the size of the kcov buffer in the userspace application using kcov. But right now syzkaller already uses 4Mb per each of up to 32 threads to store the coverage, and increasing it further would result in reduction in the number of executors on a single machine. Replaying the same program with an increased buffer size in the case of overflow would also lead to fewer executions being possible.
When executing a single system call, excessive coverage usually stems from loops, which write the same PCs into the output buffer repeatedly. Although collecting precise traces may give us some insights into e.g. the number of loop iterations and the branches being taken, the fuzzing engine does not take advantage of these signals, and recording only unique PCs should be just as practical.
In [1] Joey Jiao suggested using a hash table to deduplicate the coverage signal on the kernel side. While being universally applicable to all types of data collected by kcov, this approach adds another layer of complexity, requiring dynamically growing the map. Another problem is potential hash collisions, which can as well lead to lost coverage. Hash maps are also unavoidably sparse, which potentially requires more memory.
The approach proposed in this patch series is to assign a unique (and almost) sequential ID to each of the coverage callbacks in the kernel. Then we carve out a fixed-sized bitmap from the userspace trace buffer, and on every callback invocation we:
- obtain the callback_ID;
- if bitmap[callback_ID] is set, append the PC to the trace buffer;
- set bitmap[callback_ID] to true.
LLVM's -fsanitize-coverage=trace-pc-guard replaces every coverage callback in the kernel with a call to __sanitizer_cov_trace_pc_guard(&guard_variable) , where guard_variable is a 4-byte global that is unique for the callsite.
This allows us to lazily allocate sequential numbers just for the callbacks that have actually been executed, using a lock-free algorithm.
This patch series implements a new config, CONFIG_KCOV_ENABLE_GUARDS, which utilizes the mentioned LLVM flag for coverage instrumentation. In addition to the existing coverage collection modes, it introduces ioctl(KCOV_UNIQUE_ENABLE), which splits the existing kcov buffer into the bitmap and the trace part for a particular fuzzing session, and collects only unique coverage in the trace buffer.
To reset the coverage between runs, it is now necessary to set trace[0] to 0 AND clear the entire bitmap. This is still considered feasible, based on the experimental results below.
The current design does not address the deduplication of KCOV_TRACE_CMP comparisons; however, the number of kcov overflows during the hints collection process is insignificant compared to the overflows of KCOV_TRACE_PC.
In addition to the mentioned changes, this patch adds support for R_X86_64_REX_GOTPCRELX to objtool and arch/x86/kernel/module.c. It turned out that Clang leaves such relocations in the linked modules for the __start___sancov_guards and __stop___sancov_guards symbols. Because resolving them does not require a .got section, it can be done at module load time.
Experimental results.
We've conducted an experiment running syz-testbed [3] on 10 syzkaller instances for 24 hours. Out of those 10 instances, 5 were enabling the kcov_deduplicate flag from [4], which makes use of the KCOV_UNIQUE_ENABLE ioctl, reserving 4096 words (262144 bits) for the bitmap and leaving 520192 words for the trace collection.
Below are the average stats from the runs.
kcov_deduplicate=false:
corpus: 52176
coverage: 302658
cover overflows: 225288
comps overflows: 491
exec total: 1417829
max signal: 318894
kcov_deduplicate=true:
corpus: 52581
coverage: 304344
cover overflows: 986
comps overflows: 626
exec total: 1484841
max signal: 322455
[1] https://lore.kernel.org/linux-arm-kernel/[email protected]/T/
[2] https://clang.llvm.org/docs/SanitizerCoverage.html
[3] https://github.com/google/syzkaller/tree/master/tools/syz-testbed
[4] https://github.com/ramosian-glider/linux/pull/7
Alexander Potapenko (7):
kcov: apply clang-format to kcov code
kcov: factor out struct kcov_state
kcov: x86: introduce CONFIG_KCOV_ENABLE_GUARDS
kcov: add trace and trace_size to struct kcov_state
kcov: add ioctl(KCOV_UNIQUE_ENABLE)
x86: objtool: add support for R_X86_64_REX_GOTPCRELX mm/kasan: define __asan_before_dynamic_init, __asan_after_dynamic_init
Documentation/dev-tools/kcov.rst | 43 +++ MAINTAINERS | 1 + arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 + arch/x86/kernel/vmlinux.lds.S | 1 + arch/x86/um/asm/elf.h | 1 + include/asm-generic/vmlinux.lds.h | 14 +- include/linux/kcov-state.h | 46 +++ include/linux/kcov.h | 60 ++-- include/linux/sched.h | 16 +- include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 453 +++++++++++++++++++----------- lib/Kconfig.debug | 16 ++ mm/kasan/generic.c | 18 ++ mm/kasan/kasan.h | 2 + scripts/Makefile.kcov | 4 + scripts/module.lds.S | 23 ++ tools/objtool/arch/x86/decode.c | 1 + tools/objtool/check.c | 1 + 19 files changed, 508 insertions(+), 202 deletions(-) create mode 100644 include/linux/kcov-state.h
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerPATCH 1/7 kcov: apply clang-format to kcov code
kcov used to obey clang-format style, but somehow diverged over time. This patch applies clang-format to kernel/kcov.c and include/linux/kcov.h, no functional change.
--- include/linux/kcov.h | 54 +++++++++++------ kernel/kcov.c | 134 ++++++++++++++++++++++--------------------- 2 files changed, 105 insertions(+), 83 deletions(-)
include/linux/kcov.h +36 -18
@@ -25,20 +25,20 @@ enum kcov_mode { KCOV_MODE_REMOTE = 4, }; -#define KCOV_IN_CTXSW (1 << 30) +#define KCOV_IN_CTXSW (1 << 30)void kcov_task_init (struct task_struct *t);void kcov_task_exit (struct task_struct *t); -#define kcov_prepare_switch (t) \ -do { \ - (t)->kcov_mode |= KCOV_IN_CTXSW; \ -} while (0) +#define kcov_prepare_switch (t) \ + do { \ + (t)->kcov_mode |= KCOV_IN_CTXSW; \ + } while (0) -#define kcov_finish_switch (t) \ -do { \ - (t)->kcov_mode &= ~KCOV_IN_CTXSW; \ -} while (0) +#define kcov_finish_switch (t) \ + do { \ + (t)->kcov_mode &= ~KCOV_IN_CTXSW; \ + } while (0)/* See Documentation/dev-tools/kcov.rst for usage details. */ void kcov_remote_start (u64 handle);
@@ -119,23 +119,41 @@ void __sanitizer_cov_trace_switch(kcov_u64 val, void *cases);#else -static inline void kcov_task_init (struct task_struct *t) {} -static inline void kcov_task_exit (struct task_struct *t) {} -static inline void kcov_prepare_switch (struct task_struct *t) {} -static inline void kcov_finish_switch (struct task_struct *t) {} -static inline void kcov_remote_start (u64 handle) {} -static inline void kcov_remote_stop (void ) {} +static inline void kcov_task_init (struct task_struct *t) +{ +} +static inline void kcov_task_exit (struct task_struct *t) +{ +} +static inline void kcov_prepare_switch (struct task_struct *t) +{ +} +static inline void kcov_finish_switch (struct task_struct *t) +{ +} +static inline void kcov_remote_start (u64 handle) +{ +} +static inline void kcov_remote_stop (void ) +{ +}static inline u64 kcov_common_handle (void ) {return 0 ; } -static inline void kcov_remote_start_common (u64 id) {} -static inline void kcov_remote_start_usb (u64 id) {} +static inline void kcov_remote_start_common (u64 id) +{ +} +static inline void kcov_remote_start_usb (u64 id) +{ +}static inline unsigned long kcov_remote_start_usb_softirq (u64 id) {return 0 ; } -static inline void kcov_remote_stop_softirq (unsigned long flags) {} +static inline void kcov_remote_stop_softirq (unsigned long flags) +{ +}#endif /* CONFIG_KCOV */ #endif /* _LINUX_KCOV_H */
kernel/kcov.c +69 -65
303 lines not on this page · raw message
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Re: [PATCH 1/7] kcov: apply clang-format to kcov code
Quoted 63 lines · Alexander Potapenko
kcov used to obey clang-format style, but somehow diverged over time. This patch applies clang-format to
kernel/kcov.candinclude/linux/kcov.h, no functional change.Signed-off-by Alexander Potapenko <[email protected]>--- include/linux/kcov.h | 54 +++++++++++------ kernel/kcov.c | 134 ++++++++++++++++++++++--------------------- 2 files changed, 105 insertions(+), 83 deletions(-)include/linux/kcov.h +17
-15@@ -25,20 +25,20 @@ enum kcov_mode { KCOV_MODE_REMOTE = 4, }; -#define KCOV_IN_CTXSW (1 << 30) +#define KCOV_IN_CTXSW (1 << 30)void kcov_task_init (struct task_struct *t);void kcov_task_exit (struct task_struct *t); -#define kcov_prepare_switch (t) \ -do { \ - (t)->kcov_mode |= KCOV_IN_CTXSW; \ -} while (0) +#define kcov_prepare_switch (t) \ + do { \ + (t)->kcov_mode |= KCOV_IN_CTXSW; \ + } while (0) -#define kcov_finish_switch (t) \ -do { \ - (t)->kcov_mode &= ~KCOV_IN_CTXSW; \ -} while (0) +#define kcov_finish_switch (t) \ + do { \ + (t)->kcov_mode &= ~KCOV_IN_CTXSW; \ + } while (0)/* See Documentation/dev-tools/kcov.rst for usage details. */ void kcov_remote_start (u64 handle);@@ -119,23 +119,41 @@ void __sanitizer_cov_trace_switch(kcov_u64 val, void *cases);#else -static inline void kcov_task_init (struct task_struct *t) {} -static inline void kcov_task_exit (struct task_struct *t) {} -static inline void kcov_prepare_switch (struct task_struct *t) {} -static inline void kcov_finish_switch (struct task_struct *t) {} -static inline void kcov_remote_start (u64 handle) {} -static inline void kcov_remote_stop (void ) {} +static inline void kcov_task_init (struct task_struct *t) +{ +} +static inline void kcov_task_exit (struct task_struct *t) +{ +} +static inline void kcov_prepare_switch (struct task_struct *t) +{
include/linux/kcov.h void __sanitizer_cov_trace_switch(kcov_u64 val, void *cases); · line 139
Quoted 10 lines
include/linux/kcov.h +10
-0+} +static inline void kcov_finish_switch (struct task_struct *t) +{ +} +static inline void kcov_remote_start (u64 handle) +{ +} +static inline void kcov_remote_stop (void ) +{ +}
This excessive-new-line style is not an improvement over previously. But nothing we can do about I guess...
Quoted 245 lines
include/linux/kcov.h +9
-3static inline u64 kcov_common_handle (void ) {return 0 ; } -static inline void kcov_remote_start_common (u64 id) {} -static inline void kcov_remote_start_usb (u64 id) {} +static inline void kcov_remote_start_common (u64 id) +{ +} +static inline void kcov_remote_start_usb (u64 id) +{ +}static inline unsigned long kcov_remote_start_usb_softirq (u64 id) {return 0 ; } -static inline void kcov_remote_stop_softirq (unsigned long flags) {} +static inline void kcov_remote_stop_softirq (unsigned long flags) +{ +}#endif /* CONFIG_KCOV */ #endif /* _LINUX_KCOV_H */ kernel/kcov.c +48
-46@@ -4,27 +4,28 @@#define DISABLE_BRANCH_PROFILING #include <linux/atomic.h> #include <linux/compiler.h> +#include <linux/debugfs.h> #include <linux/errno.h> #include <linux/export.h> -#include <linux/types.h> #include <linux/file.h> #include <linux/fs.h> #include <linux/hashtable.h> #include <linux/init.h> #include <linux/jiffies.h> +#include <linux/kcov.h> #include <linux/kmsan-checks.h> +#include <linux/log2.h> #include <linux/mm.h> #include <linux/preempt.h> #include <linux/printk.h> +#include <linux/refcount.h> #include <linux/sched.h> #include <linux/slab.h> #include <linux/spinlock.h> -#include <linux/vmalloc.h> -#include <linux/debugfs.h> +#include <linux/types.h> #include <linux/uaccess.h> -#include <linux/kcov.h> -#include <linux/refcount.h> -#include <linux/log2.h> +#include <linux/vmalloc.h> +#include <asm/setup.h> #define kcov_debug (fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)@@ -52,36 +53,36 @@ struct kcov {* - task with enabled coverage (we can't unwire it from another task) * - each code section for remote coverage collection */ -refcount_t refcount; +refcount_t refcount;/* The lock protects mode, size, area and t. */ -spinlock_t lock; -enum kcov_mode mode; +spinlock_t lock; +enum kcov_mode mode;/* Size of arena (in long's). */ -unsigned int size; +unsigned int size;/* Coverage buffer shared with user space. */ -void *area; +void *area;/* Task for which we collect coverage, or NULL. */ -struct task_struct *t; +struct task_struct *t;/* Collecting coverage from remote (background) threads. */ -bool remote; +bool remote;/* Size of remote area (in long's). */ -unsigned int remote_size; +unsigned int remote_size;/* * Sequence is incremented each time kcov is reenabled, used by * kcov_remote_stop(), see the comment there. */ -int sequence; +int sequence; };struct kcov_remote_area { -struct list_head list; -unsigned int size; +struct list_head list; +unsigned int size; };struct kcov_remote { -u64 handle; -struct kcov *kcov; -struct hlist_node hnode; +u64 handle; +struct kcov *kcov; +struct hlist_node hnode; };static DEFINE_SPINLOCK (kcov_remote_lock);@@ -89,14 +90,14 @@ static DEFINE_HASHTABLE(kcov_remote_map, 4);static struct list_head kcov_remote_areas =LIST_HEAD_INIT (kcov_remote_areas);struct kcov_percpu_data { -void *irq_area; -local_lock_t lock; - -unsigned int saved_mode; -unsigned int saved_size; -void *saved_area; -struct kcov *saved_kcov; -int saved_sequence; +void *irq_area; +local_lock_t lock; + +unsigned int saved_mode; +unsigned int saved_size; +void *saved_area; +struct kcov *saved_kcov; +int saved_sequence; }; static DEFINE_PER_CPU(struct kcov_percpu_data, kcov_percpu_data) = {@@ -149,7 +150,7 @@ static struct kcov_remote_area *kcov_remote_area_get(unsigned int size)/* Must be called with kcov_remote_lock locked. */ static void kcov_remote_area_put (struct kcov_remote_area *area, -unsigned int size) +unsigned int size) {INIT_LIST_HEAD (&area->list); area->size = size;@@ -171,7 +172,8 @@ static __always_inline bool in_softirq_really(void)return in_serving_softirq () && !in_hardirq () && !in_nmi (); } -static notrace bool check_kcov_mode(enum kcov_mode needed_mode, struct task_struct *t) +static notrace bool check_kcov_mode(enum kcov_mode needed_mode, +struct task_struct *t) {unsigned int mode;@@ -354,8 +356,8 @@ EXPORT_SYMBOL(__sanitizer_cov_trace_switch);#endif /* ifdef CONFIG_KCOV_ENABLE_COMPARISONS */ static void kcov_start (struct task_struct *t,struct kcov *kcov, -unsigned int size,void *area,enum kcov_mode mode, -int sequence) +unsigned int size,void *area,enum kcov_mode mode, +int sequence) {kcov_debug ("t = %px, size = %u, area = %px\n" , t, size, area); t->kcov = kcov;@@ -566,14 +568,14 @@ static void kcov_fault_in_area(struct kcov *kcov) }static inline bool kcov_check_handle (u64 handle,bool common_valid, -bool uncommon_valid,bool zero_valid) +bool uncommon_valid,bool zero_valid) {if (handle & ~(KCOV_SUBSYSTEM_MASK |KCOV_INSTANCE_MASK ))return false;switch (handle &KCOV_SUBSYSTEM_MASK ) {case KCOV_SUBSYSTEM_COMMON : -return (handle &KCOV_INSTANCE_MASK ) ? - common_valid : zero_valid; +return (handle &KCOV_INSTANCE_MASK ) ? common_valid : + zero_valid;case KCOV_SUBSYSTEM_USB :return uncommon_valid;default :@@ -611,7 +613,7 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,kcov_fault_in_area (kcov); kcov->mode = mode;kcov_start (t, kcov, kcov->size, kcov->area, kcov->mode, - kcov->sequence); + kcov->sequence); kcov->t = t;/* Put either in kcov_task_exit() or in KCOV_DISABLE. */ kcov_get (kcov);@@ -642,40 +644,40 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,return -EINVAL ; kcov->mode = mode; t->kcov = kcov; - t->kcov_mode =KCOV_MODE_REMOTE ; + t->kcov_mode =KCOV_MODE_REMOTE ; kcov->t = t; kcov->remote = true; kcov->remote_size = remote_arg->area_size;spin_lock_irqsave (&kcov_remote_lock, flags);for (i =0 ; i < remote_arg->num_handles; i++) { -if (!kcov_check_handle (remote_arg->handles[i], - false, true, false)) { +if (!kcov_check_handle (remote_arg->handles[i], false, + true, false)) {spin_unlock_irqrestore (&kcov_remote_lock, - flags); + flags);kcov_disable (t, kcov);return -EINVAL ; } remote =kcov_remote_add (kcov, remote_arg->handles[i]);if (IS_ERR (remote)) {spin_unlock_irqrestore (&kcov_remote_lock, - flags); + flags);kcov_disable (t, kcov);return PTR_ERR (remote); } }if (remote_arg->common_handle) { -if (!kcov_check_handle (remote_arg->common_handle, - true, false, false)) { +if (!kcov_check_handle (remote_arg->common_handle, true, + false, false)) {spin_unlock_irqrestore (&kcov_remote_lock, - flags); + flags);kcov_disable (t, kcov);return -EINVAL ; } remote =kcov_remote_add (kcov, - remote_arg->common_handle); + remote_arg->common_handle);if (IS_ERR (remote)) {spin_unlock_irqrestore (&kcov_remote_lock, - flags); + flags);kcov_disable (t, kcov);return PTR_ERR (remote); }
kernel/kcov.c static long kcov_ioctl(struct file *filep, unsigned int cmd, unsigned long arg) · line 736
Quoted 9 lines
kernel/kcov.c +4
-2@@ -728,13 +730,15 @@ static long kcov_ioctl(struct file *filep, unsigned int cmd, unsigned long arg)spin_unlock_irqrestore (&kcov->lock, flags);return 0 ;case KCOV_REMOTE_ENABLE : -if (get_user (remote_num_handles, (unsigned __user *)(arg + - offsetof(struct kcov_remote_arg , num_handles)))) +if (get_user (remote_num_handles, + (unsigned __user *)(arg + + offsetof(struct kcov_remote_arg , + num_handles))))
Ouch. Maybe move the address calculation before and assign to temporary to avoid this mess?
Quoted 84 lines
kernel/kcov.c +15
-16return -EFAULT ;if (remote_num_handles >KCOV_REMOTE_MAX_HANDLES )return -EINVAL ; - remote_arg_size =struct_size (remote_arg, handles, - remote_num_handles); + remote_arg_size = +struct_size (remote_arg, handles, remote_num_handles); remote_arg =memdup_user ((void __user *)arg, remote_arg_size);if (IS_ERR (remote_arg))return PTR_ERR (remote_arg);@@ -758,11 +762,11 @@ static long kcov_ioctl(struct file *filep, unsigned int cmd, unsigned long arg) }static const struct file_operations kcov_fops = { - .open = kcov_open, - .unlocked_ioctl = kcov_ioctl, - .compat_ioctl = kcov_ioctl, - .mmap = kcov_mmap, - .release = kcov_close, + .open = kcov_open, + .unlocked_ioctl = kcov_ioctl, + .compat_ioctl = kcov_ioctl, + .mmap = kcov_mmap, + .release = kcov_close, };/* @@ -836,8 +840,8 @@ static void kcov_remote_softirq_stop(struct task_struct *t)if (data->saved_kcov) {kcov_start (t, data->saved_kcov, data->saved_size, - data->saved_area, data->saved_mode, - data->saved_sequence); + data->saved_area, data->saved_mode, + data->saved_sequence); data->saved_mode =0 ; data->saved_size =0 ; data->saved_area =NULL ;@@ -891,7 +895,7 @@ void kcov_remote_start(u64 handle)return ; }kcov_debug ("handle = %llx, context: %s\n" , handle, -in_task () ?"task" :"softirq" ); +in_task () ?"task" :"softirq" ); kcov = remote->kcov;/* Put in kcov_remote_stop(). */ kcov_get (kcov);@@ -931,12 +935,11 @@ void kcov_remote_start(u64 handle)kcov_start (t, kcov, size, area, mode, sequence);local_unlock_irqrestore (&kcov_percpu_data.lock, flags); - }EXPORT_SYMBOL (kcov_remote_start);static void kcov_move_area (enum kcov_mode mode,void *dst_area, -unsigned int dst_area_size,void *src_area) +unsigned int dst_area_size,void *src_area) {u64 word_size =sizeof (unsigned long );u64 count_size, entry_size_log;@@ -944,8 +947,8 @@ static void kcov_move_area(enum kcov_mode mode, void *dst_area,void *dst_entries, *src_entries;u64 dst_occupied, dst_free, bytes_to_move, entries_moved; -kcov_debug ("%px %u <= %px %lu\n" , - dst_area, dst_area_size, src_area, *(unsigned long *)src_area); +kcov_debug ("%px %u <= %px %lu\n" , dst_area, dst_area_size, src_area, + *(unsigned long *)src_area);switch (mode) {case KCOV_MODE_TRACE_PC :@@ -967,8 +970,8 @@ static void kcov_move_area(enum kcov_mode mode, void *dst_area, }/* As arm can't divide u64 integers use log of entry size. */ -if (dst_len > ((dst_area_size * word_size - count_size) >> - entry_size_log)) +if (dst_len > + ((dst_area_size * word_size - count_size) >> entry_size_log))return ; dst_occupied = count_size + (dst_len << entry_size_log); dst_free = dst_area_size * word_size - dst_occupied;
kernel/kcov.c static int __init kcov_init(void) · line 1107
Quoted 6 lines
kernel/kcov.c +2
-1@@ -1100,7 +1103,8 @@ static int __init kcov_init(void)for_each_possible_cpu (cpu) {void *area =vmalloc_node (CONFIG_KCOV_IRQ_AREA_SIZE * -sizeof (unsigned long ),cpu_to_node (cpu)); +sizeof (unsigned long ), +cpu_to_node (cpu));
Ouch.
Alexander Potapenko
reviewerRe: [PATCH 1/7] kcov: apply clang-format to kcov code
Quoted 9 lines
include/linux/kcov.h void __sanitizer_cov_trace_switch(kcov_u64 val, void *cases); · line 139
Quoted 6 lines
include/linux/kcov.h +6
-0+static inline void kcov_remote_start (u64 handle) +{ +} +static inline void kcov_remote_stop (void ) +{ +}This excessive-new-line style is not an improvement over previously. But nothing we can do about I guess...
I think we'd better stick with whatever clang-format gives us.
Quoted 5 lines
Quoted 5 lines
kernel/kcov.c +0
-1@@ -728,13 +730,15 @@ static long kcov_ioctl(struct file *filep, unsigned int cmd, unsigned long arg)spin_unlock_irqrestore (&kcov->lock, flags);return 0 ;case KCOV_REMOTE_ENABLE : - if (get_user(remote_num_handles, (unsigned __user *)(arg +
Quoted 8 lines
kernel/kcov.c static long kcov_ioctl(struct file *filep, unsigned int cmd, unsigned long arg) · line 736
Quoted 5 lines
kernel/kcov.c +4
-1- offsetof(struct kcov_remote_arg, num_handles)))) +if (get_user (remote_num_handles, + (unsigned __user *)(arg + + offsetof(struct kcov_remote_arg , + num_handles))))Ouch. Maybe move the address calculation before and assign to temporary to avoid this mess?
I factored out offsetof(), because the address calculation looked all the same after formatting.
Quoted 7 lines
kernel/kcov.c static int __init kcov_init(void) · line 1107
Quoted 5 lines
kernel/kcov.c +2
-1for_each_possible_cpu (cpu) {void *area =vmalloc_node (CONFIG_KCOV_IRQ_AREA_SIZE * -sizeof (unsigned long ),cpu_to_node (cpu)); +sizeof (unsigned long ), +cpu_to_node (cpu));Ouch.
Someday we'll probably switch clang-format to 100 columns
Alexander Potapenko
reviewerPATCH 2/7 kcov: factor out struct kcov_state
In reply to Alexander PotapenkoGroup several kcov-related fields (area, size, mode, sequence) that are stored in various structures, into struct kcov_state, so that these fields can be easily passed around and manipulated.
This prepares us for the upcoming change that will introduce more kcov state.
Also update the MAINTAINERS entry.
--- MAINTAINERS | 1 + include/linux/kcov-state.h | 31 ++++++++ include/linux/kcov.h | 14 ++-- include/linux/sched.h | 16 +--- kernel/kcov.c | 149 ++++++++++++++++--------------------- 5 files changed, 106 insertions(+), 105 deletions(-) create mode 100644 include/linux/kcov-state.h
MAINTAINERS +1 -0
@@ -12511,6 +12511,7 @@ L: [email protected] S: Maintained B: https://bugzilla.kernel.org/buglist.cgi?component=Sanitizers&product=Memory%20Management F: Documentation/dev-tools/kcov.rst +F: include/linux/kcov-state.h F: include/linux/kcov.h F: include/uapi/linux/kcov.h F: kernel/kcov.c
include/linux/kcov-state.h new file +31 -0
@@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_KCOV_STATE_H +#define _LINUX_KCOV_STATE_H + +#ifdef CONFIG_KCOV +struct kcov_state { +/* See kernel/kcov.c for more details. */ +/* +* Coverage collection mode enabled for this task (0 if disabled). +* This field is used for synchronization, so it is kept outside of +* the below struct. +*/ +unsigned int mode; + +struct { +/* Size of the area (in long's). */ +unsigned int size; + +/* Buffer for coverage collection, shared with the userspace. */ +void *area; + +/* +* KCOV sequence number: incremented each time kcov is +* reenabled, used by kcov_remote_stop(), see the comment there. +*/ +int sequence; + } s; +}; +#endif /* CONFIG_KCOV */ + +#endif /* _LINUX_KCOV_STATE_H */
include/linux/kcov.h +7 -7
@@ -2,7 +2,7 @@#ifndef _LINUX_KCOV_H#define _LINUX_KCOV_H -#include <linux/sched.h> +#include <linux/kcov-state.h> #include <uapi/linux/kcov.h> struct task_struct ;
@@ -30,14 +30,14 @@ enum kcov_mode {void kcov_task_init (struct task_struct *t);void kcov_task_exit (struct task_struct *t); -#define kcov_prepare_switch (t) \ - do { \ - (t)->kcov_mode |= KCOV_IN_CTXSW; \ +#define kcov_prepare_switch (t) \ + do { \ + (t)->kcov_state.mode |= KCOV_IN_CTXSW; \ } while (0) -#define kcov_finish_switch (t) \ - do { \ - (t)->kcov_mode &= ~KCOV_IN_CTXSW; \ +#define kcov_finish_switch (t) \ + do { \ + (t)->kcov_state.mode &= ~KCOV_IN_CTXSW; \ } while (0)/* See Documentation/dev-tools/kcov.rst for usage details. */
include/linux/sched.h +2 -14
@@ -42,6 +42,7 @@#include <linux/restart_block.h> #include <uapi/linux/rseq.h> #include <linux/seqlock_types.h> +#include <linux/kcov-state.h> #include <linux/kcsan.h> #include <linux/rv.h> #include <linux/livepatch_sched.h>
@@ -1485,26 +1486,13 @@ struct task_struct {#endif /* CONFIG_TRACING */ #ifdef CONFIG_KCOV -/* See kernel/kcov.c for more details. */ - -/* Coverage collection mode enabled for this task (0 if disabled): */ -unsigned int kcov_mode; - -/* Size of the kcov_area: */ -unsigned int kcov_size; - -/* Buffer for coverage collection: */ -void *kcov_area; - +struct kcov_state kcov_state;/* KCOV descriptor wired with this task or NULL: */ struct kcov *kcov;/* KCOV common handle for remote coverage collection: */ u64 kcov_handle; -/* KCOV sequence number: */ -int kcov_sequence; -/* Collect coverage from softirq context: */ unsigned int kcov_softirq;#endif
kernel/kcov.c +65 -84
363 lines not on this page · raw message
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Re: [PATCH 2/7] kcov: factor out struct kcov_state
Quoted 8 lines · Alexander Potapenko
Group several kcov-related fields (area, size, mode, sequence) that are stored in various structures, into
struct kcov_state, so that these fields can be easily passed around and manipulated.This prepares us for the upcoming change that will introduce more kcov state.
Quoted 6 lines
Also update the
MAINTAINERSentry.Signed-off-by Alexander Potapenko <[email protected]>--- MAINTAINERS | 1 + include/linux/kcov-state.h | 31 ++++++++
Looking at <linux/sched.h>, a lot of the headers introduced to factor out types are called "foo_types.h", so this probably should be "kcov_types.h".
Quoted 28 lines
include/linux/kcov.h | 14 ++-- include/linux/sched.h | 16 +--- kernel/kcov.c | 149 ++++++++++++++++--------------------- 5 files changed, 106 insertions(+), 105 deletions(-) create mode 100644 include/linux/kcov-state.hMAINTAINERS +1
-0@@ -12511,6 +12511,7 @@ L: [email protected] S: Maintained B: https://bugzilla.kernel.org/buglist.cgi?component=Sanitizers&product=Memory%20Management F: Documentation/dev-tools/kcov.rst +F: include/linux/kcov-state.h F: include/linux/kcov.h F: include/uapi/linux/kcov.h F: kernel/kcov.cinclude/linux/kcov-state.h new file +4
-0@@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_KCOV_STATE_H +#define _LINUX_KCOV_STATE_H +
include/linux/kcov-state.h line 14
Quoted 10 lines
include/linux/kcov-state.h new file +10
-0+#ifdef CONFIG_KCOV +struct kcov_state { + /* See kernel/kcov.c for more details. */ + /* + * Coverage collection mode enabled for this task (0 if disabled). + * This field is used for synchronization, so it is kept outside of + * the below struct. + */ + unsigned int mode; +
It'd be nice to have a comment why the below is in an anon struct "s"
- AFAIK it's to be able to copy it around easily.
However, thinking about it more, why does "mode" have to be in "kcov_state"? Does it logically make sense?
We also have this inconsistency where before we had the instance in "struct kcov" be "enum kcov_mode", and the one in task_struct be "unsigned int". Now they're both unsigned int - which I'm not sure is better.
Could we instead do this:
- keep "mode" outside the struct (a bit more duplication, but I think it's clearer)
- move enum kcov_mode to kcov_types.h
- define all instances of "mode" consistently as "enum kcov_mode"
- make kcov_state just contain what is now in "kcov_state::s", and effectively get rid of the nested "s"
Quoted 104 lines
include/linux/kcov-state.h new file +17
-0+struct { +/* Size of the area (in long's). */ +unsigned int size; + +/* Buffer for coverage collection, shared with the userspace. */ +void *area; + +/* +* KCOV sequence number: incremented each time kcov is +* reenabled, used by kcov_remote_stop(), see the comment there. +*/ +int sequence; + } s; +}; +#endif /* CONFIG_KCOV */ + +#endif /* _LINUX_KCOV_STATE_H */ include/linux/kcov.h +7
-7@@ -2,7 +2,7 @@#ifndef _LINUX_KCOV_H#define _LINUX_KCOV_H -#include <linux/sched.h> +#include <linux/kcov-state.h> #include <uapi/linux/kcov.h> struct task_struct ;@@ -30,14 +30,14 @@ enum kcov_mode {void kcov_task_init (struct task_struct *t);void kcov_task_exit (struct task_struct *t); -#define kcov_prepare_switch (t) \ - do { \ - (t)->kcov_mode |= KCOV_IN_CTXSW; \ +#define kcov_prepare_switch (t) \ + do { \ + (t)->kcov_state.mode |= KCOV_IN_CTXSW; \ } while (0) -#define kcov_finish_switch (t) \ - do { \ - (t)->kcov_mode &= ~KCOV_IN_CTXSW; \ +#define kcov_finish_switch (t) \ + do { \ + (t)->kcov_state.mode &= ~KCOV_IN_CTXSW; \ } while (0)/* See Documentation/dev-tools/kcov.rst for usage details. */ include/linux/sched.h +2
-14@@ -42,6 +42,7 @@#include <linux/restart_block.h> #include <uapi/linux/rseq.h> #include <linux/seqlock_types.h> +#include <linux/kcov-state.h> #include <linux/kcsan.h> #include <linux/rv.h> #include <linux/livepatch_sched.h> @@ -1485,26 +1486,13 @@ struct task_struct {#endif /* CONFIG_TRACING */ #ifdef CONFIG_KCOV -/* See kernel/kcov.c for more details. */ - -/* Coverage collection mode enabled for this task (0 if disabled): */ -unsigned int kcov_mode; - -/* Size of the kcov_area: */ -unsigned int kcov_size; - -/* Buffer for coverage collection: */ -void *kcov_area; - +struct kcov_state kcov_state;/* KCOV descriptor wired with this task or NULL: */ struct kcov *kcov;/* KCOV common handle for remote coverage collection: */ u64 kcov_handle; -/* KCOV sequence number: */ -int kcov_sequence; -/* Collect coverage from softirq context: */ unsigned int kcov_softirq;#endif kernel/kcov.c +1
-0@@ -13,6 +13,7 @@#include <linux/init.h> #include <linux/jiffies.h> #include <linux/kcov.h> +#include <linux/kcov-state.h> #include <linux/kmsan-checks.h> #include <linux/log2.h> #include <linux/mm.h>
kernel/kcov.c struct kcov { · line 58
Quoted 5 lines
kernel/kcov.c +1
-1@@ -54,24 +55,16 @@ struct kcov {* - each code section for remote coverage collection */ refcount_t refcount; -/* The lock protects mode, size, area and t. */ +/* The lock protects state and t. */
Unlike previously, this implies it also protects "s.sequence" now. (Aside: as-is this will also make annotating it with __guarded_by rather difficult.)
Quoted 263 lines
kernel/kcov.c +42
-59spinlock_t lock; -enum kcov_mode mode; -/* Size of arena (in long's). */ -unsigned int size; -/* Coverage buffer shared with user space. */ -void *area; +struct kcov_state state; +/* Task for which we collect coverage, or NULL. */ struct task_struct *t;/* Collecting coverage from remote (background) threads. */ bool remote;/* Size of remote area (in long's). */ unsigned int remote_size; -/* -* Sequence is incremented each time kcov is reenabled, used by -* kcov_remote_stop(), see the comment there. -*/ -int sequence; };struct kcov_remote_area {@@ -92,12 +85,8 @@ static struct list_head kcov_remote_areas = LIST_HEAD_INIT(kcov_remote_areas);struct kcov_percpu_data {void *irq_area;local_lock_t lock; - -unsigned int saved_mode; -unsigned int saved_size; -void *saved_area;struct kcov *saved_kcov; -int saved_sequence; +struct kcov_state saved_state; }; static DEFINE_PER_CPU(struct kcov_percpu_data, kcov_percpu_data) = {@@ -184,7 +173,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode,*/ if (!in_task () && !(in_softirq_really () && t->kcov_softirq))return false; - mode =READ_ONCE (t->kcov_mode); + mode =READ_ONCE (t->kcov_state.mode);/* * There is some code that runs in interrupts but for which * in_interrupt() returns false (e.g. preempt_schedule_irq()). @@ -219,10 +208,10 @@ void notrace __sanitizer_cov_trace_pc(void)if (!check_kcov_mode (KCOV_MODE_TRACE_PC , t))return ; - area = t->kcov_area; + area = t->kcov_state.s.area;/* The first 64-bit word is the number of subsequent PCs. */ pos =READ_ONCE (area[0 ]) +1 ; -if (likely (pos < t->kcov_size)) { +if (likely (pos < t->kcov_state.s.size)) {/* Previously we write pc before updating pos. However, some * early interrupt code could bypass check_kcov_mode() check * and invoke __sanitizer_cov_trace_pc(). If such interrupt is @@ -252,10 +241,10 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)/* * We write all comparison arguments and types as u64. -* The buffer was allocated for t->kcov_size unsigned longs. +* The buffer was allocated for t->kcov_state.size unsigned longs. */ - area = (u64 *)t->kcov_area; - max_pos = t->kcov_size *sizeof (unsigned long ); + area = (u64 *)t->kcov_state.s.area; + max_pos = t->kcov_state.s.size *sizeof (unsigned long ); count =READ_ONCE (area[0 ]);@@ -356,33 +345,31 @@ EXPORT_SYMBOL(__sanitizer_cov_trace_switch);#endif /* ifdef CONFIG_KCOV_ENABLE_COMPARISONS */ static void kcov_start (struct task_struct *t,struct kcov *kcov, -unsigned int size,void *area,enum kcov_mode mode, -int sequence) +struct kcov_state *state) { -kcov_debug ("t = %px, size = %u, area = %px\n" , t, size, area); +kcov_debug ("t = %px, size = %u, area = %px\n" , t, state->s.size, + state->s.area); t->kcov = kcov;/* Cache in task struct for performance. */ - t->kcov_size = size; - t->kcov_area = area; - t->kcov_sequence = sequence; -/* See comment in check_kcov_mode(). */ + t->kcov_state.s = state->s;barrier (); -WRITE_ONCE (t->kcov_mode, mode); +/* See comment in check_kcov_mode(). */ +WRITE_ONCE (t->kcov_state.mode, state->mode); }static void kcov_stop (struct task_struct *t) { -WRITE_ONCE (t->kcov_mode,KCOV_MODE_DISABLED ); +WRITE_ONCE (t->kcov_state.mode,KCOV_MODE_DISABLED );barrier (); t->kcov =NULL ; - t->kcov_size =0 ; - t->kcov_area =NULL ; + t->kcov_state.s.size =0 ; + t->kcov_state.s.area =NULL ; }static void kcov_task_reset (struct task_struct *t) {kcov_stop (t); - t->kcov_sequence =0 ; + t->kcov_state.s.sequence =0 ; t->kcov_handle =0 ; }@@ -395,10 +382,10 @@ void kcov_task_init(struct task_struct *t)static void kcov_reset (struct kcov *kcov) { kcov->t =NULL ; - kcov->mode =KCOV_MODE_INIT ; + kcov->state.mode =KCOV_MODE_INIT ; kcov->remote = false; kcov->remote_size =0 ; - kcov->sequence++; + kcov->state.s.sequence++; }static void kcov_remote_reset (struct kcov *kcov)@@ -438,7 +425,7 @@ static void kcov_put(struct kcov *kcov) {if (refcount_dec_and_test (&kcov->refcount)) {kcov_remote_reset (kcov); -vfree (kcov->area); +vfree (kcov->state.s.area);kfree (kcov); } }@@ -495,8 +482,8 @@ static int kcov_mmap(struct file *filep, struct vm_area_struct *vma)unsigned long flags;spin_lock_irqsave (&kcov->lock, flags); - size = kcov->size *sizeof (unsigned long ); -if (kcov->area ==NULL || vma->vm_pgoff !=0 || + size = kcov->state.s.size *sizeof (unsigned long ); +if (kcov->state.s.area ==NULL || vma->vm_pgoff !=0 || vma->vm_end - vma->vm_start != size) { res = -EINVAL ; goto exit;@@ -504,7 +491,7 @@ static int kcov_mmap(struct file *filep, struct vm_area_struct *vma)spin_unlock_irqrestore (&kcov->lock, flags);vm_flags_set (vma,VM_DONTEXPAND );for (off =0 ; off < size; off +=PAGE_SIZE ) { - page =vmalloc_to_page (kcov->area + off); + page =vmalloc_to_page (kcov->state.s.area + off); res =vm_insert_page (vma, vma->vm_start + off, page);if (res) {pr_warn_once ("kcov: vm_insert_page() failed\n" );@@ -524,8 +511,8 @@ static int kcov_open(struct inode *inode, struct file *filep) kcov =kzalloc (sizeof (*kcov),GFP_KERNEL );if (!kcov)return -ENOMEM ; - kcov->mode =KCOV_MODE_DISABLED ; - kcov->sequence =1 ; + kcov->state.mode =KCOV_MODE_DISABLED ; + kcov->state.s.sequence =1 ;refcount_set (&kcov->refcount,1 );spin_lock_init (&kcov->lock); filep->private_data = kcov;@@ -560,10 +547,10 @@ static int kcov_get_mode(unsigned long arg)static void kcov_fault_in_area (struct kcov *kcov) {unsigned long stride =PAGE_SIZE /sizeof (unsigned long ); -unsigned long *area = kcov->area; +unsigned long *area = kcov->state.s.area;unsigned long offset; -for (offset =0 ; offset < kcov->size; offset += stride) +for (offset =0 ; offset < kcov->state.s.size; offset += stride)READ_ONCE (area[offset]); }@@ -602,7 +589,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->state.mode !=KCOV_MODE_INIT || !kcov->state.s.area)return -EINVAL ; t = current;if (kcov->t !=NULL || t->kcov !=NULL )@@ -611,9 +598,8 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,if (mode <0 )return mode;kcov_fault_in_area (kcov); - kcov->mode = mode; -kcov_start (t, kcov, kcov->size, kcov->area, kcov->mode, - kcov->sequence); + kcov->state.mode = mode; +kcov_start (t, kcov, &kcov->state); kcov->t = t;/* Put either in kcov_task_exit() or in KCOV_DISABLE. */ kcov_get (kcov);@@ -630,7 +616,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->state.mode !=KCOV_MODE_INIT || !kcov->state.s.area)return -EINVAL ; t = current;if (kcov->t !=NULL || t->kcov !=NULL )@@ -642,9 +628,9 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,if ((unsigned long )remote_arg->area_size >LONG_MAX /sizeof (unsigned long ))return -EINVAL ; - kcov->mode = mode; + kcov->state.mode = mode; t->kcov = kcov; - t->kcov_mode =KCOV_MODE_REMOTE ; + t->kcov_state.mode =KCOV_MODE_REMOTE ; kcov->t = t; kcov->remote = true; kcov->remote_size = remote_arg->area_size;@@ -719,14 +705,14 @@ static long kcov_ioctl(struct file *filep, unsigned int cmd, unsigned long arg)if (area ==NULL )return -ENOMEM ;spin_lock_irqsave (&kcov->lock, flags); -if (kcov->mode !=KCOV_MODE_DISABLED ) { +if (kcov->state.mode !=KCOV_MODE_DISABLED ) {spin_unlock_irqrestore (&kcov->lock, flags);vfree (area);return -EBUSY ; } - kcov->area = area; - kcov->size = size; - kcov->mode =KCOV_MODE_INIT ; + kcov->state.s.area = area; + kcov->state.s.size = size; + kcov->state.mode =KCOV_MODE_INIT ;spin_unlock_irqrestore (&kcov->lock, flags);return 0 ;case KCOV_REMOTE_ENABLE :@@ -822,13 +808,11 @@ static void kcov_remote_softirq_start(struct task_struct *t)struct kcov_percpu_data *data =this_cpu_ptr (&kcov_percpu_data);unsigned int mode; - mode =READ_ONCE (t->kcov_mode); + mode =READ_ONCE (t->kcov_state.mode);barrier ();if (kcov_mode_enabled (mode)) { - data->saved_mode = mode; - data->saved_size = t->kcov_size; - data->saved_area = t->kcov_area; - data->saved_sequence = t->kcov_sequence; + data->saved_state.s = t->kcov_state.s; + data->saved_state.mode = mode; data->saved_kcov = t->kcov;kcov_stop (t); }@@ -839,13 +823,8 @@ static void kcov_remote_softirq_stop(struct task_struct *t)struct kcov_percpu_data *data =this_cpu_ptr (&kcov_percpu_data);
kernel/kcov.c static void kcov_remote_softirq_stop(struct task_struct *t) · line 827
Quoted 10 lines
kernel/kcov.c +2
-7if (data->saved_kcov) { -kcov_start (t, data->saved_kcov, data->saved_size, - data->saved_area, data->saved_mode, - data->saved_sequence); - data->saved_mode =0 ; - data->saved_size =0 ; - data->saved_area =NULL ; - data->saved_sequence =0 ; +kcov_start (t, data->saved_kcov, &data->saved_state); + data->saved_state = (struct kcov_state ){0 };
Unsure how the compiler optimizes this (does it create a temporary and then assigns it?). Maybe just memset is clearer.
Quoted 107 lines
kernel/kcov.c +19
-18data->saved_kcov =NULL ; } }@@ -854,12 +833,11 @@ void kcov_remote_start(u64 handle) {struct task_struct *t = current;struct kcov_remote *remote; +struct kcov_state state; +unsigned long flags; +unsigned int size;struct kcov *kcov; -unsigned int mode;void *area; -unsigned int size; -int sequence; -unsigned long flags;if (WARN_ON (!kcov_check_handle (handle, true, true, true)))return ;@@ -872,8 +850,8 @@ void kcov_remote_start(u64 handle)* Check that kcov_remote_start() is not called twice in background * threads nor called by user tasks (with enabled kcov). */ - mode =READ_ONCE (t->kcov_mode); -if (WARN_ON (in_task () &&kcov_mode_enabled (mode))) { + state.mode =READ_ONCE (t->kcov_state.mode); +if (WARN_ON (in_task () &&kcov_mode_enabled (state.mode))) {local_unlock_irqrestore (&kcov_percpu_data.lock, flags);return ; }@@ -903,8 +881,8 @@ void kcov_remote_start(u64 handle)* Read kcov fields before unlock to prevent races with * KCOV_DISABLE / kcov_remote_reset(). */ - mode = kcov->mode; - sequence = kcov->sequence; + state.mode = kcov->state.mode; + state.s.sequence = kcov->state.s.sequence;if (in_task ()) { size = kcov->remote_size; area =kcov_remote_area_get (size);@@ -927,12 +905,14 @@ void kcov_remote_start(u64 handle)/* Reset coverage size. */ *(u64 *)area =0 ; + state.s.area = area; + state.s.size = size;if (in_serving_softirq ()) {kcov_remote_softirq_start (t); t->kcov_softirq =1 ; } -kcov_start (t, kcov, size, area, mode, sequence); +kcov_start (t, kcov, &state);local_unlock_irqrestore (&kcov_percpu_data.lock, flags); }@@ -1009,7 +989,7 @@ void kcov_remote_stop(void)local_lock_irqsave (&kcov_percpu_data.lock, flags); - mode =READ_ONCE (t->kcov_mode); + mode =READ_ONCE (t->kcov_state.mode);barrier ();if (!kcov_mode_enabled (mode)) {local_unlock_irqrestore (&kcov_percpu_data.lock, flags);@@ -1030,9 +1010,9 @@ void kcov_remote_stop(void) } kcov = t->kcov; - area = t->kcov_area; - size = t->kcov_size; - sequence = t->kcov_sequence; + area = t->kcov_state.s.area; + size = t->kcov_state.s.size; + sequence = t->kcov_state.s.sequence;kcov_stop (t);if (in_serving_softirq ()) {@@ -1045,8 +1025,9 @@ void kcov_remote_stop(void)* KCOV_DISABLE could have been called between kcov_remote_start() * and kcov_remote_stop(), hence the sequence check. */ -if (sequence == kcov->sequence && kcov->remote) -kcov_move_area (kcov->mode, kcov->area, kcov->size, area); +if (sequence == kcov->state.s.sequence && kcov->remote) +kcov_move_area (kcov->state.mode, kcov->state.s.area, + kcov->state.s.size, area);spin_unlock (&kcov->lock);if (in_task ()) {@@ -1089,10 +1070,10 @@ static void __init selftest(void)* potentially traced functions in this region. */ start = jiffies; - current->kcov_mode =KCOV_MODE_TRACE_PC ; + current->kcov_state.mode =KCOV_MODE_TRACE_PC ;while ((jiffies - start) *MSEC_PER_SEC /HZ <300 ) ; - current->kcov_mode =0 ; + current->kcov_state.mode =0 ; pr_err("done running self test\n"); }#endif --2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerRe: [PATCH 2/7] kcov: factor out struct kcov_state
Quoted 7 lines
Quoted 3 lines
--- MAINTAINERS | 1 + include/linux/kcov-state.h | 31 ++++++++Looking at <
linux/sched.h>, a lot of the headers introduced to factor out types are called "foo_types.h", so this probably should be "kcov_types.h".
Yeah, it makes sense, thank you!
Quoted 5 lines
Quoted 5 lines
include/linux/kcov-state.h new file +5
-0+ +#ifdef CONFIG_KCOV +struct kcov_state { +/* See kernel/kcov.c for more details. */ +/*
Quoted 8 lines
include/linux/kcov-state.h line 14
Quoted 6 lines
include/linux/kcov-state.h new file +6
-0+* Coverage collection mode enabled for this task (0 if disabled). +* This field is used for synchronization, so it is kept outside of +* the below struct. +*/ +unsigned int mode; +It'd be nice to have a comment why the below is in an anon struct "s"
Ack
Quoted 1 line
- AFAIK it's to be able to copy it around easily.
Yes, correct.
Quoted 2 lines
However, thinking about it more, why does "mode" have to be in "
kcov_state"? Does it logically make sense?
You might be right. Almost everywhere we are accessing mode and kcov_state independently, so there isn't too much profit in keeping them in the same struct.
Logically, they are protected by the same lock, but that lock protects other members of struct kcov anyway.
Quoted 4 lines
We also have this inconsistency where before we had the instance in "struct kcov" be "enum
kcov_mode", and the one intask_structbe "unsigned int". Now they're both unsigned int - which I'm not sure is better.
You are right, this slipped my mind.
Quoted 3 lines
Could we instead do this:
- keep "mode" outside the struct (a bit more duplication, but I think it's clearer)
Ack
Quoted 1 line
- move enum
kcov_modetokcov_types.h
Ack
Quoted 1 line
- define all instances of "mode" consistently as "enum
kcov_mode"
There is one tricky place where kcov_get_mode() handily returns either an enum, or an error value. Not sure we want to change that (and the declaration of "mode" in kcov_ioctl_locked()).
Or otherwise we could define two modes corresponding to -EINVAL and -ENOTSUPP to preserve the existing behavior.
Quoted 2 lines
- make
kcov_statejust contain what is now in "kcov_state::s", and effectively get rid of the nested "s"
Yeah, this is doable.
Quoted 10 lines
kernel/kcov.c struct kcov { · line 58
Quoted 6 lines
kernel/kcov.c +1
-1@@ -54,24 +55,16 @@ struct kcov {* - each code section for remote coverage collection */ refcount_t refcount; -/* The lock protects mode, size, area and t. */ +/* The lock protects state and t. */ Unlike previously, this implies it also protects "s.sequence" now. (Aside: as-is this will also make annotating it with
__guarded_byrather difficult.)
As far as I can see, s.sequence is accessed under the same lock anyway, so it is not too late to make it part of the protected state. Or am I missing something?
Alexander Potapenko
reviewerRe: [PATCH 2/7] kcov: factor out struct kcov_state
In reply to Marco ElverQuoted 11 lines
kernel/kcov.c static void kcov_remote_softirq_stop(struct task_struct *t) · line 827
Quoted 10 lines
if (data->saved_kcov) {kernel/kcov.c +2
-7-kcov_start (t, data->saved_kcov, data->saved_size, - data->saved_area, data->saved_mode, - data->saved_sequence); - data->saved_mode =0 ; - data->saved_size =0 ; - data->saved_area =NULL ; - data->saved_sequence =0 ; +kcov_start (t, data->saved_kcov, &data->saved_state); + data->saved_state = (struct kcov_state ){0 };
Quoted 2 lines
Unsure how the compiler optimizes this (does it create a temporary and then assigns it?). Maybe just memset is clearer.
Missed this one - I am not convinced a memset is clearer, but recent patches mention that '{ }' is preferred over '{ 0 }'.
Alexander Potapenko
reviewerPATCH 3/7 kcov: x86: introduce CONFIG_KCOV_ENABLE_GUARDS
In reply to Alexander PotapenkoThe new config switches coverage instrumentation to using
__sanitizer_cov_trace_pc_guard(u32 *guard)
instead of
__sanitizer_cov_trace_pc(void)
Each callback receives a unique 32-bit guard variable residing in the __sancov_guards section. Those guards can be used by kcov to deduplicate the coverage on the fly.
As a first step, we make the new instrumentation mode 1:1 compatible with the old one.
--- arch/x86/kernel/vmlinux.lds.S | 1 + include/asm-generic/vmlinux.lds.h | 14 ++++++- include/linux/kcov.h | 2 + kernel/kcov.c | 61 +++++++++++++++++++++---------- lib/Kconfig.debug | 16 ++++++++ scripts/Makefile.kcov | 4 ++ scripts/module.lds.S | 23 ++++++++++++ tools/objtool/check.c | 1 + 8 files changed, 101 insertions(+), 21 deletions(-)
arch/x86/kernel/vmlinux.lds.S +1 -0
@@ -390,6 +390,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); __bss_stop = .; } + SANCOV_GUARDS_BSS /* * The memory occupied from _text to here, __end_of_kernel_reserve, is
include/asm-generic/vmlinux.lds.h +13 -1
@@ -102,7 +102,8 @@* sections to be brought in with rodata. */ #if defined(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION ) || defined(CONFIG_LTO_CLANG ) || \ -defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) + defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) || \ + defined(CONFIG_KCOV_ENABLE_GUARDS )#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*#else #define TEXT_MAIN .text
@@ -121,6 +122,17 @@ defined(CONFIG_AUTOFDO_CLANG) || defined(CONFIG_PROPELLER_CLANG)#define SBSS_MAIN .sbss#endif +#if defined(CONFIG_KCOV_ENABLE_GUARDS ) +#define SANCOV_GUARDS_BSS \ + __sancov_guards(NOLOAD) : { \ + __start___sancov_guards = .; \ + *(__sancov_guards); \ + __stop___sancov_guards = .; \ + } +#else +#define SANCOV_GUARDS_BSS +#endif +/* * GCC 4.5 and later have a 32 bytes section alignment for structures. * Except GCC 4.9, that feels the need to align on 64 bytes.
include/linux/kcov.h +2 -0
@@ -107,6 +107,8 @@ typedef unsigned long long kcov_u64;#endif void __sanitizer_cov_trace_pc (void ); +void __sanitizer_cov_trace_pc_guard (u32 *guard); +void __sanitizer_cov_trace_pc_guard_init (uint32_t *start,uint32_t *stop);void __sanitizer_cov_trace_cmp1 (u8 arg1,u8 arg2);void __sanitizer_cov_trace_cmp2 (u16 arg1,u16 arg2);void __sanitizer_cov_trace_cmp4 (u32 arg1,u32 arg2);
kernel/kcov.c +41 -20
82 lines not on this page · raw message
lib/Kconfig.debug +16 -0
@@ -2135,6 +2135,8 @@ config ARCH_HAS_KCOV config CC_HAS_SANCOV_TRACE_PC def_bool $(cc-option,-fsanitize-coverage=trace-pc) +config CC_HAS_SANCOV_TRACE_PC_GUARD + def_bool $(cc-option,-fsanitize-coverage=trace-pc-guard) config KCOV bool "Code coverage for fuzzing"
@@ -2151,6 +2153,20 @@ config KCOV For more details, see Documentation/dev-tools/kcov.rst. +config KCOV_ENABLE_GUARDS + depends on KCOV + depends on CC_HAS_SANCOV_TRACE_PC_GUARD + bool "Use fsanitize-coverage=trace-pc-guard for kcov" + help + Use coverage guards instrumentation for kcov, passing + -fsanitize-coverage=trace-pc-guard to the compiler. + + Every coverage callback is associated with a global variable that + allows to efficiently deduplicate coverage at collection time. + + This comes at a cost of increased binary size (4 bytes of .bss + per basic block, plus 1-2 instructions to pass an extra parameter). + config KCOV_ENABLE_COMPARISONS bool "Enable comparison operands collection by KCOV" depends on KCOV
scripts/Makefile.kcov +4 -0
@@ -1,5 +1,9 @@ # SPDX-License-Identifier: GPL-2.0-only +ifeq ($(CONFIG_KCOV_ENABLE_GUARDS),y) +kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD) += -fsanitize-coverage=trace-pc-guard +else kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC) += -fsanitize-coverage=trace-pc +endif kcov-flags-$(CONFIG_KCOV_ENABLE_COMPARISONS) += -fsanitize-coverage=trace-cmp kcov-flags-$(CONFIG_GCC_PLUGIN_SANCOV) += -fplugin=$(objtree)/scripts/gcc-plugins/sancov_plugin.so
scripts/module.lds.S +23 -0
@@ -64,6 +64,29 @@ SECTIONS { MOD_CODETAG_SECTIONS() } #endif + +#ifdef CONFIG_KCOV_ENABLE_GUARDS + __sancov_guards(NOLOAD) : { + __start___sancov_guards = .; + *(__sancov_guards); + __stop___sancov_guards = .; + } + + .text : { + *(.text .text.[0-9a-zA-Z_]*) + *(.text..L*) + } + + .init.text : { + *(.init.text .init.text.[0-9a-zA-Z_]*) + *(.init.text..L*) + } + .exit.text : { + *(.exit.text .exit.text.[0-9a-zA-Z_]*) + *(.exit.text..L*) + } +#endif + MOD_SEPARATE_CODETAG_SECTIONS() }
tools/objtool/check.c +1 -0
@@ -1149,6 +1149,7 @@ static const char *uaccess_safe_builtin[] = {"write_comp_data" ,"check_kcov_mode" ,"__sanitizer_cov_trace_pc" , +"__sanitizer_cov_trace_pc_guard" ,"__sanitizer_cov_trace_const_cmp1" ,"__sanitizer_cov_trace_const_cmp2" , "__sanitizer_cov_trace_const_cmp4",
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Re: [PATCH 3/7] kcov: x86: introduce CONFIG_KCOV_ENABLE_GUARDS
Quoted 31 lines · Alexander Potapenko
The new config switches coverage instrumentation to using
__sanitizer_cov_trace_pc_guard(u32 *guard)
instead of
__sanitizer_cov_trace_pc(void)Each callback receives a unique 32-bit guard variable residing in the
__sancov_guardssection. Those guards can be used by kcov to deduplicate the coverage on the fly.As a first step, we make the new instrumentation mode 1:1 compatible with the old one.
Signed-off-by Alexander Potapenko <[email protected]>--- arch/x86/kernel/vmlinux.lds.S | 1 + include/asm-generic/vmlinux.lds.h | 14 ++++++- include/linux/kcov.h | 2 + kernel/kcov.c | 61 +++++++++++++++++++++---------- lib/Kconfig.debug | 16 ++++++++ scripts/Makefile.kcov | 4 ++ scripts/module.lds.S | 23 ++++++++++++ tools/objtool/check.c | 1 + 8 files changed, 101 insertions(+), 21 deletions(-)arch/x86/kernel/vmlinux.lds.S +0
-0
arch/x86/kernel/vmlinux.lds.S SECTIONS · line 393
Quoted 4 lines
arch/x86/kernel/vmlinux.lds.S +1
-0@@ -390,6 +390,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); __bss_stop = .; } + SANCOV_GUARDS_BSS
Right now this will be broken on other architectures, right?
Quoted 52 lines
arch/x86/kernel/vmlinux.lds.S +0
-0/* * The memory occupied from _text to here, __end_of_kernel_reserve, isinclude/asm-generic/vmlinux.lds.h +13
-1@@ -102,7 +102,8 @@* sections to be brought in with rodata. */ #if defined(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION ) || defined(CONFIG_LTO_CLANG ) || \ -defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) + defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) || \ + defined(CONFIG_KCOV_ENABLE_GUARDS )#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*#else #define TEXT_MAIN .text@@ -121,6 +122,17 @@ defined(CONFIG_AUTOFDO_CLANG) || defined(CONFIG_PROPELLER_CLANG)#define SBSS_MAIN .sbss#endif +#if defined(CONFIG_KCOV_ENABLE_GUARDS ) +#define SANCOV_GUARDS_BSS \ + __sancov_guards(NOLOAD) : { \ + __start___sancov_guards = .; \ + *(__sancov_guards); \ + __stop___sancov_guards = .; \ + } +#else +#define SANCOV_GUARDS_BSS +#endif +/* * GCC 4.5 and later have a 32 bytes section alignment for structures. * Except GCC 4.9, that feels the need to align on 64 bytes. include/linux/kcov.h +2
-0@@ -107,6 +107,8 @@ typedef unsigned long long kcov_u64;#endif void __sanitizer_cov_trace_pc (void ); +void __sanitizer_cov_trace_pc_guard (u32 *guard); +void __sanitizer_cov_trace_pc_guard_init (uint32_t *start,uint32_t *stop);void __sanitizer_cov_trace_cmp1 (u8 arg1,u8 arg2);void __sanitizer_cov_trace_cmp2 (u16 arg1,u16 arg2);void __sanitizer_cov_trace_cmp4 (u32 arg1,u32 arg2);kernel/kcov.c +0
-0
kernel/kcov.c static notrace unsigned long canonicalize_ip(unsigned long ip) · line 196
Quoted 9 lines
kernel/kcov.c +1
-5@@ -193,27 +193,15 @@ static notrace unsigned long canonicalize_ip(unsigned long ip)return ip; } -/* -* Entry point from instrumented code. -* This is called once per basic-block/edge. -*/ -void notrace __sanitizer_cov_trace_pc(void) +static void sanitizer_cov_write_subsequent(unsigned long *area, int size,
notrace is missing.
Can we give this a more descriptive name? E.g. "kcov_append" ?
Quoted 26 lines
kernel/kcov.c +6
-14+ unsigned long ip) { -struct task_struct *t; -unsigned long *area; -unsigned long ip =canonicalize_ip (_RET_IP_); -unsigned long pos; - - t = current; -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , t)) -return ; - - area = t->kcov_state.s.area;/* The first 64-bit word is the number of subsequent PCs. */ - pos =READ_ONCE (area[0 ]) +1 ; -if (likely (pos < t->kcov_state.s.size)) { -/* Previously we write pc before updating pos. However, some -* early interrupt code could bypass check_kcov_mode() check +unsigned long pos =READ_ONCE (area[0 ]) +1 ; + +if (likely (pos < size)) { +/* +* Some early interrupt code could bypass check_kcov_mode() check * and invoke __sanitizer_cov_trace_pc(). If such interrupt is * raised between writing pc and updating pos, the pc could be * overitten by the recursive __sanitizer_cov_trace_pc().
kernel/kcov.c void notrace __sanitizer_cov_trace_pc(void) · line 220
Quoted 9 lines
kernel/kcov.c +6
-0@@ -224,7 +212,40 @@ void notrace __sanitizer_cov_trace_pc(void) area[pos] = ip; } } + +/* +* Entry point from instrumented code. +* This is called once per basic-block/edge. +*/ +#ifndef CONFIG_KCOV_ENABLE_GUARDS
Negation makes it harder to read - just #ifdef, and swap the branches below.
Quoted 54 lines
kernel/kcov.c +28
-1+void notrace __sanitizer_cov_trace_pc(void) +{ +if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +return ; + +sanitizer_cov_write_subsequent (current->kcov_state.s.area, + current->kcov_state.s.size, +canonicalize_ip (_RET_IP_)); +}EXPORT_SYMBOL (__sanitizer_cov_trace_pc); +#else +void notrace __sanitizer_cov_trace_pc_guard(u32 *guard) +{ +if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +return ; + +sanitizer_cov_write_subsequent (current->kcov_state.s.area, + current->kcov_state.s.size, +canonicalize_ip (_RET_IP_)); +} +EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard); + +void notrace __sanitizer_cov_trace_pc_guard_init(uint32_t *start, +uint32_t *stop) +{ +} +EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard_init); +#endif #ifdef CONFIG_KCOV_ENABLE_COMPARISONS static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)@@ -252,7 +273,7 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip) start_index =1 + count *KCOV_WORDS_PER_CMP ; end_pos = (start_index +KCOV_WORDS_PER_CMP ) *sizeof (u64);if (likely (end_pos <= max_pos)) { -/* See comment in __sanitizer_cov_trace_pc(). */ +/* See comment in sanitizer_cov_write_subsequent(). */ WRITE_ONCE (area[0 ], count +1 );barrier (); area[start_index] = type;lib/Kconfig.debug +2
-0@@ -2135,6 +2135,8 @@ config ARCH_HAS_KCOV config CC_HAS_SANCOV_TRACE_PC def_bool $(cc-option,-fsanitize-coverage=trace-pc) +config CC_HAS_SANCOV_TRACE_PC_GUARD + def_bool $(cc-option,-fsanitize-coverage=trace-pc-guard) config KCOV bool "Code coverage for fuzzing"
lib/Kconfig.debug config KCOV · line 2156
Quoted 4 lines
lib/Kconfig.debug +1
-0@@ -2151,6 +2153,20 @@ config KCOV For more details, see Documentation/dev-tools/kcov.rst. +config KCOV_ENABLE_GUARDS
The "ENABLE" here seems redundant.
Just KCOV_GUARDS should be clear enough.
lib/Kconfig.debug config KCOV · line 2159
Quoted 3 lines
lib/Kconfig.debug +3
-0+ depends on KCOV + depends on CC_HAS_SANCOV_TRACE_PC_GUARD + bool "Use fsanitize-coverage=trace-pc-guard for kcov"
The compiler option is an implementation detail - it might be more helpful to have this say "Use coverage guards for kcov".
Quoted 18 lines
lib/Kconfig.debug +10
-0+ help + Use coverage guards instrumentation for kcov, passing + -fsanitize-coverage=trace-pc-guard to the compiler. + + Every coverage callback is associated with a global variable that + allows to efficiently deduplicate coverage at collection time. + + This comes at a cost of increased binary size (4 bytes of .bss + per basic block, plus 1-2 instructions to pass an extra parameter). + config KCOV_ENABLE_COMPARISONS bool "Enable comparison operands collection by KCOV" depends on KCOVscripts/Makefile.kcov +0
-0
scripts/Makefile.kcov line 3
Quoted 3 lines
scripts/Makefile.kcov +2
-0@@ -1,5 +1,9 @@ # SPDX-License-Identifier: GPL-2.0-only +ifeq ($(CONFIG_KCOV_ENABLE_GUARDS),y) +kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD) += -fsanitize-coverage=trace-pc-guard
This can just be kcov-flags-y, because CONFIG_KCOV_ENABLE_GUARDS implies CONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD.
Quoted 55 lines
scripts/Makefile.kcov +2
-0+else kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC) += -fsanitize-coverage=trace-pc +endif kcov-flags-$(CONFIG_KCOV_ENABLE_COMPARISONS) += -fsanitize-coverage=trace-cmp kcov-flags-$(CONFIG_GCC_PLUGIN_SANCOV) += -fplugin=$(objtree)/scripts/gcc-plugins/sancov_plugin.soscripts/module.lds.S +23
-0@@ -64,6 +64,29 @@ SECTIONS { MOD_CODETAG_SECTIONS() } #endif + +#ifdef CONFIG_KCOV_ENABLE_GUARDS + __sancov_guards(NOLOAD) : { + __start___sancov_guards = .; + *(__sancov_guards); + __stop___sancov_guards = .; + } + + .text : { + *(.text .text.[0-9a-zA-Z_]*) + *(.text..L*) + } + + .init.text : { + *(.init.text .init.text.[0-9a-zA-Z_]*) + *(.init.text..L*) + } + .exit.text : { + *(.exit.text .exit.text.[0-9a-zA-Z_]*) + *(.exit.text..L*) + } +#endif + MOD_SEPARATE_CODETAG_SECTIONS() }tools/objtool/check.c +1
-1@@ -1149,6 +1149,7 @@ static const char *uaccess_safe_builtin[] = {"write_comp_data" ,"check_kcov_mode" ,"__sanitizer_cov_trace_pc" , +"__sanitizer_cov_trace_pc_guard" ,"__sanitizer_cov_trace_const_cmp1" ,"__sanitizer_cov_trace_const_cmp2" , "__sanitizer_cov_trace_const_cmp4", --2.49.0.604.gff1f9ca942-goog
Re: [PATCH 3/7] kcov: x86: introduce CONFIG_KCOV_ENABLE_GUARDS
Quoted 27 lines · Marco Elver
Quoted 26 lines · Alexander Potapenko
The new config switches coverage instrumentation to using
__sanitizer_cov_trace_pc_guard(u32 *guard)
instead of
__sanitizer_cov_trace_pc(void)Each callback receives a unique 32-bit guard variable residing in the
__sancov_guardssection. Those guards can be used by kcov to deduplicate the coverage on the fly.As a first step, we make the new instrumentation mode 1:1 compatible with the old one.
Signed-off-by Alexander Potapenko <[email protected]>--- arch/x86/kernel/vmlinux.lds.S | 1 + include/asm-generic/vmlinux.lds.h | 14 ++++++- include/linux/kcov.h | 2 + kernel/kcov.c | 61 +++++++++++++++++++++---------- lib/Kconfig.debug | 16 ++++++++ scripts/Makefile.kcov | 4 ++ scripts/module.lds.S | 23 ++++++++++++ tools/objtool/check.c | 1 + 8 files changed, 101 insertions(+), 21 deletions(-)
Quoted 11 lines
arch/x86/kernel/vmlinux.lds.S SECTIONS · line 393
Quoted 9 lines
arch/x86/kernel/vmlinux.lds.S +1
-0@@ -390,6 +390,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); __bss_stop = .; } + SANCOV_GUARDS_BSSRight now this will be broken on other architectures, right?
I did a test on arm64, after adding SANCOV_GUARDS_BSS, it reports missing support for R_AARCH64_ADR_GOT_PAGE and R_AARCH64_LD64_GOT_LO12_NC.
Quoted 254 lines
Quoted 53 lines
arch/x86/kernel/vmlinux.lds.S +0
-0/* * The memory occupied from _text to here, __end_of_kernel_reserve, isinclude/asm-generic/vmlinux.lds.h +13
-1@@ -102,7 +102,8 @@* sections to be brought in with rodata. */ #if defined(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION ) || defined(CONFIG_LTO_CLANG ) || \ -defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) + defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) || \ + defined(CONFIG_KCOV_ENABLE_GUARDS )#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*#else #define TEXT_MAIN .text@@ -121,6 +122,17 @@ defined(CONFIG_AUTOFDO_CLANG) || defined(CONFIG_PROPELLER_CLANG)#define SBSS_MAIN .sbss#endif +#if defined(CONFIG_KCOV_ENABLE_GUARDS ) +#define SANCOV_GUARDS_BSS \ + __sancov_guards(NOLOAD) : { \ + __start___sancov_guards = .; \ + *(__sancov_guards); \ + __stop___sancov_guards = .; \ + } +#else +#define SANCOV_GUARDS_BSS +#endif +/* * GCC 4.5 and later have a 32 bytes section alignment for structures. * Except GCC 4.9, that feels the need to align on 64 bytes. include/linux/kcov.h +2
-0@@ -107,6 +107,8 @@ typedef unsigned long long kcov_u64;#endif void __sanitizer_cov_trace_pc (void ); +void __sanitizer_cov_trace_pc_guard (u32 *guard); +void __sanitizer_cov_trace_pc_guard_init (uint32_t *start,uint32_t *stop);void __sanitizer_cov_trace_cmp1 (u8 arg1,u8 arg2);void __sanitizer_cov_trace_cmp2 (u16 arg1,u16 arg2);void __sanitizer_cov_trace_cmp4 (u32 arg1,u32 arg2);kernel/kcov.c +0
-0kernel/kcov.c static notrace unsigned long canonicalize_ip(unsigned long ip) · line 196
Quoted 9 lines
kernel/kcov.c +1
-5@@ -193,27 +193,15 @@ static notrace unsigned long canonicalize_ip(unsigned long ip)return ip; } -/* -* Entry point from instrumented code. -* This is called once per basic-block/edge. -*/ -void notrace __sanitizer_cov_trace_pc(void) +static void sanitizer_cov_write_subsequent(unsigned long *area, int size,notrace is missing.
Can we give this a more descriptive name? E.g. "
kcov_append" ?Quoted 26 lines
kernel/kcov.c +6
-14+ unsigned long ip) { -struct task_struct *t; -unsigned long *area; -unsigned long ip =canonicalize_ip (_RET_IP_); -unsigned long pos; - - t = current; -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , t)) -return ; - - area = t->kcov_state.s.area;/* The first 64-bit word is the number of subsequent PCs. */ - pos =READ_ONCE (area[0 ]) +1 ; -if (likely (pos < t->kcov_state.s.size)) { -/* Previously we write pc before updating pos. However, some -* early interrupt code could bypass check_kcov_mode() check +unsigned long pos =READ_ONCE (area[0 ]) +1 ; + +if (likely (pos < size)) { +/* +* Some early interrupt code could bypass check_kcov_mode() check * and invoke __sanitizer_cov_trace_pc(). If such interrupt is * raised between writing pc and updating pos, the pc could be * overitten by the recursive __sanitizer_cov_trace_pc(). kernel/kcov.c void notrace __sanitizer_cov_trace_pc(void) · line 220
Quoted 9 lines
kernel/kcov.c +6
-0@@ -224,7 +212,40 @@ void notrace __sanitizer_cov_trace_pc(void) area[pos] = ip; } } + +/* +* Entry point from instrumented code. +* This is called once per basic-block/edge. +*/ +#ifndef CONFIG_KCOV_ENABLE_GUARDS Negation makes it harder to read - just #ifdef, and swap the branches below.
Quoted 54 lines
kernel/kcov.c +28
-1+void notrace __sanitizer_cov_trace_pc(void) +{ +if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +return ; + +sanitizer_cov_write_subsequent (current->kcov_state.s.area, + current->kcov_state.s.size, +canonicalize_ip (_RET_IP_)); +}EXPORT_SYMBOL (__sanitizer_cov_trace_pc); +#else +void notrace __sanitizer_cov_trace_pc_guard(u32 *guard) +{ +if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +return ; + +sanitizer_cov_write_subsequent (current->kcov_state.s.area, + current->kcov_state.s.size, +canonicalize_ip (_RET_IP_)); +} +EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard); + +void notrace __sanitizer_cov_trace_pc_guard_init(uint32_t *start, +uint32_t *stop) +{ +} +EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard_init); +#endif #ifdef CONFIG_KCOV_ENABLE_COMPARISONS static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)@@ -252,7 +273,7 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip) start_index =1 + count *KCOV_WORDS_PER_CMP ; end_pos = (start_index +KCOV_WORDS_PER_CMP ) *sizeof (u64);if (likely (end_pos <= max_pos)) { -/* See comment in __sanitizer_cov_trace_pc(). */ +/* See comment in sanitizer_cov_write_subsequent(). */ WRITE_ONCE (area[0 ], count +1 );barrier (); area[start_index] = type;lib/Kconfig.debug +2
-0@@ -2135,6 +2135,8 @@ config ARCH_HAS_KCOV config CC_HAS_SANCOV_TRACE_PC def_bool $(cc-option,-fsanitize-coverage=trace-pc) +config CC_HAS_SANCOV_TRACE_PC_GUARD + def_bool $(cc-option,-fsanitize-coverage=trace-pc-guard) config KCOV bool "Code coverage for fuzzing"lib/Kconfig.debug config KCOV · line 2156
Quoted 4 lines
lib/Kconfig.debug +1
-0@@ -2151,6 +2153,20 @@ config KCOV For more details, see Documentation/dev-tools/kcov.rst. +config KCOV_ENABLE_GUARDSThe "ENABLE" here seems redundant.
JustKCOV_GUARDSshould be clear enough.lib/Kconfig.debug config KCOV · line 2159
Quoted 3 lines
lib/Kconfig.debug +3
-0+ depends on KCOV + depends on CC_HAS_SANCOV_TRACE_PC_GUARD + bool "Use fsanitize-coverage=trace-pc-guard for kcov"The compiler option is an implementation detail - it might be more helpful to have this say "Use coverage guards for kcov".
Quoted 18 lines
lib/Kconfig.debug +10
-0+ help + Use coverage guards instrumentation for kcov, passing + -fsanitize-coverage=trace-pc-guard to the compiler. + + Every coverage callback is associated with a global variable that + allows to efficiently deduplicate coverage at collection time. + + This comes at a cost of increased binary size (4 bytes of .bss + per basic block, plus 1-2 instructions to pass an extra parameter). + config KCOV_ENABLE_COMPARISONS bool "Enable comparison operands collection by KCOV" depends on KCOVscripts/Makefile.kcov +0
-0scripts/Makefile.kcov line 3
Quoted 3 lines
scripts/Makefile.kcov +2
-0@@ -1,5 +1,9 @@ # SPDX-License-Identifier: GPL-2.0-only +ifeq ($(CONFIG_KCOV_ENABLE_GUARDS),y) +kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD) += -fsanitize-coverage=trace-pc-guardThis can just be kcov-flags-y, because
CONFIG_KCOV_ENABLE_GUARDSimpliesCONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD.Quoted 55 lines
scripts/Makefile.kcov +2
-0+else kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC) += -fsanitize-coverage=trace-pc +endif kcov-flags-$(CONFIG_KCOV_ENABLE_COMPARISONS) += -fsanitize-coverage=trace-cmp kcov-flags-$(CONFIG_GCC_PLUGIN_SANCOV) += -fplugin=$(objtree)/scripts/gcc-plugins/sancov_plugin.soscripts/module.lds.S +23
-0@@ -64,6 +64,29 @@ SECTIONS { MOD_CODETAG_SECTIONS() } #endif + +#ifdef CONFIG_KCOV_ENABLE_GUARDS + __sancov_guards(NOLOAD) : { + __start___sancov_guards = .; + *(__sancov_guards); + __stop___sancov_guards = .; + } + + .text : { + *(.text .text.[0-9a-zA-Z_]*) + *(.text..L*) + } + + .init.text : { + *(.init.text .init.text.[0-9a-zA-Z_]*) + *(.init.text..L*) + } + .exit.text : { + *(.exit.text .exit.text.[0-9a-zA-Z_]*) + *(.exit.text..L*) + } +#endif + MOD_SEPARATE_CODETAG_SECTIONS() }tools/objtool/check.c +1
-1@@ -1149,6 +1149,7 @@ static const char *uaccess_safe_builtin[] = {"write_comp_data" ,"check_kcov_mode" ,"__sanitizer_cov_trace_pc" , +"__sanitizer_cov_trace_pc_guard" ,"__sanitizer_cov_trace_const_cmp1" ,"__sanitizer_cov_trace_const_cmp2" , "__sanitizer_cov_trace_const_cmp4", --2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerRe: [PATCH 3/7] kcov: x86: introduce CONFIG_KCOV_ENABLE_GUARDS
In reply to Marco ElverQuoted 9 lines
arch/x86/kernel/vmlinux.lds.S SECTIONS · line 393
Quoted 7 lines
arch/x86/kernel/vmlinux.lds.S +1
-0@@ -390,6 +390,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); __bss_stop = .; } + SANCOV_GUARDS_BSSRight now this will be broken on other architectures, right?
Right. I'm going to make it depend on X86_64 for now.
Quoted 7 lines
arch/x86/kernel/vmlinux.lds.S SECTIONS
Quoted 5 lines
arch/x86/kernel/vmlinux.lds.S +1
-4- * Entry point from instrumented code. - * This is called once per basic-block/edge. - */ -void notrace __sanitizer_cov_trace_pc(void) +static void sanitizer_cov_write_subsequent(unsigned long *area, int size,notrace is missing.
Ack.
Quoted 1 line
Can we give this a more descriptive name? E.g. "
kcov_append" ?
I'll rename it to kcov_append_to_buffer().
Quoted 8 lines
arch/x86/kernel/vmlinux.lds.S
Quoted 6 lines
arch/x86/kernel/vmlinux.lds.S +6
-0+ +/* + * Entry point from instrumented code. + * This is called once per basic-block/edge. + */ +#ifndef CONFIG_KCOV_ENABLE_GUARDSNegation makes it harder to read - just #ifdef, and swap the branches below.
I thought I'd better keep the default hook above, but maybe you are right. Will do in v2.
Quoted 5 lines
Quoted 2 lines
+config
KCOV_ENABLE_GUARDSThe "ENABLE" here seems redundant.
JustKCOV_GUARDSshould be clear enough.
I am already renaming this config to KCOV_UNIQUE per Dmitry's request :)
Quoted 7 lines
arch/x86/kernel/vmlinux.lds.S
Quoted 4 lines
arch/x86/kernel/vmlinux.lds.S +3
-0+ depends on KCOV + depends on CC_HAS_SANCOV_TRACE_PC_GUARD + bool "Use fsanitize-coverage=trace-pc-guard for kcov"The compiler option is an implementation detail - it might be more helpful to have this say "Use coverage guards for kcov".
Ack.
Quoted 10 lines
scripts/Makefile.kcov line 3
Quoted 6 lines
scripts/Makefile.kcov +2
-0@@ -1,5 +1,9 @@ # SPDX-License-Identifier: GPL-2.0-only +ifeq ($(CONFIG_KCOV_ENABLE_GUARDS),y) +kcov-flags-$(CONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD) += -fsanitize-coverage=trace-pc-guardThis can just be kcov-flags-y, because
CONFIG_KCOV_ENABLE_GUARDSimpliesCONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD.
Agreed.
Re: [PATCH 3/7] kcov: x86: introduce CONFIG_KCOV_ENABLE_GUARDS
Quoted 11 lines · Alexander Potapenko
Quoted 10 lines
arch/x86/kernel/vmlinux.lds.S SECTIONS · line 393
Quoted 8 lines
arch/x86/kernel/vmlinux.lds.S +1
-0@@ -390,6 +390,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); __bss_stop = .; } + SANCOV_GUARDS_BSSRight now this will be broken on other architectures, right?
Quoted 1 line
Right. I'm going to make it depend on
X86_64for now.
This needs to be done with a 'select HAVE_KCOV_UNIQUE' or such from arch/x86/Kconfig.
Alexander Potapenko
reviewerPATCH 4/7 kcov: add `trace` and `trace_size` to `struct kcov_state`
In reply to Alexander PotapenkoKeep kcov_state.area as the pointer to the memory buffer used by kcov and shared with the userspace. Store the pointer to the trace (part of the buffer holding sequential events) separately, as we will be splitting that buffer in multiple parts.
No functional change so far.
--- include/linux/kcov-state.h | 9 ++++++- kernel/kcov.c | 54 ++++++++++++++++++++++---------------- 2 files changed, 39 insertions(+), 24 deletions(-)
include/linux/kcov-state.h +8 -1
@@ -15,9 +15,16 @@ struct kcov_state {struct {/* Size of the area (in long's). */ unsigned int size; +/* +* Pointer to user-provided memory used by kcov. This memory may +* contain multiple buffers. +*/ +void *area; +/* Size of the trace (in long's). */ +unsigned int trace_size;/* Buffer for coverage collection, shared with the userspace. */ -void *area; +unsigned long *trace;/* * KCOV sequence number: incremented each time kcov is
kernel/kcov.c +31 -23
139 lines not on this page · raw message
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerPATCH 5/7 kcov: add ioctl(KCOV_UNIQUE_ENABLE)
In reply to Alexander Potapenkoioctl(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.
Note: when CONFIG_KCOV_ENABLE_GUARDS is disabled, ioctl(KCOV_UNIQUE_ENABLE) returns -ENOTSUPP, which is consistent with the existing kcov code.
Also update the documentation.
--- Documentation/dev-tools/kcov.rst | 43 +++++++++++ include/linux/kcov-state.h | 8 ++ include/linux/kcov.h | 2 + include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 129 +++++++++++++++++++++++++++---- 5 files changed, 170 insertions(+), 13 deletions(-)
Documentation/dev-tools/kcov.rst +43 -0
@@ -137,6 +137,49 @@ mmaps coverage buffer, and then forks child processes in a loop. The child processes only need to enable coverage (it gets disabled automatically when a thread exits). +Unique coverage collection +--------------------------- + +Instead of collecting raw PCs, KCOV can deduplicate them on the fly. +This mode is enabled by the ``KCOV_UNIQUE_ENABLE`` ioctl (only available if +``CONFIG_KCOV_ENABLE_GUARDS`` is on). + +.. code-block:: c + + /* Same includes and defines as above. */ + #define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long) + #define BITMAP_SIZE (4<<10) + + /* Instead of KCOV_ENABLE, enable unique coverage collection. */ + if (ioctl(fd, KCOV_UNIQUE_ENABLE, BITMAP_SIZE)) + perror("ioctl"), exit(1); + /* Reset the coverage from the tail of the ioctl() call. */ + __atomic_store_n(&cover[BITMAP_SIZE], 0, __ATOMIC_RELAXED); + memset(cover, 0, BITMAP_SIZE * sizeof(unsigned long)); + + /* Call the target syscall call. */ + /* ... */ + + /* Read the number of collected PCs. */ + n = __atomic_load_n(&cover[BITMAP_SIZE], __ATOMIC_RELAXED); + /* Disable the coverage collection. */ + if (ioctl(fd, KCOV_DISABLE, 0)) + perror("ioctl"), exit(1); + +Calling ``ioctl(fd, KCOV_UNIQUE_ENABLE, bitmap_size)`` carves out ``bitmap_size`` +words from those allocated by ``KCOV_INIT_TRACE`` to keep an opaque bitmap that +prevents the kernel from storing the same PC twice. The remaining part of the +trace is used to collect PCs, like in other modes (this part must contain at +least two words, like when collecting non-unique PCs). + +The mapping between a PC and its position in the bitmap is persistent during the +kernel lifetime, so it is possible for the callers to directly use the bitmap +contents as a coverage signal (like when fuzzing userspace with AFL). + +In order to reset the coverage between the runs, the user needs to rewind the +trace (by writing 0 into the first word past ``bitmap_size``) and wipe the whole +bitmap. + Comparison operands collection ------------------------------
include/linux/kcov-state.h +8 -0
@@ -26,6 +26,14 @@ struct kcov_state {/* Buffer for coverage collection, shared with the userspace. */ unsigned long *trace; +/* Size of the bitmap (in bits). */ +unsigned int bitmap_size; +/* +* Bitmap for coverage deduplication, shared with the +* userspace. +*/ +unsigned long *bitmap; +/* * KCOV sequence number: incremented each time kcov is * reenabled, used by kcov_remote_stop(), see the comment there.
include/linux/kcov.h +2 -0
@@ -10,6 +10,7 @@ struct task_struct;#ifdef CONFIG_KCOV enum kcov_mode { +KCOV_MODE_INVALID =-1 ,/* Coverage collection is not enabled yet. */ KCOV_MODE_DISABLED =0 , /* KCOV was initialized, but tracing mode hasn't been chosen yet. */
@@ -23,6 +24,7 @@ enum kcov_mode {KCOV_MODE_TRACE_CMP =3 ,/* The process owns a KCOV remote reference. */ KCOV_MODE_REMOTE =4 , + KCOV_MODE_TRACE_UNIQUE_PC = 5, };#define KCOV_IN_CTXSW (1 << 30)
include/uapi/linux/kcov.h +1 -0
@@ -22,6 +22,7 @@ struct kcov_remote_arg {#define KCOV_ENABLE _IO('c', 100)#define KCOV_DISABLE _IO('c', 101)#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg) +#define KCOV_UNIQUE_ENABLE _IOR('c', 103, unsigned long)enum {/*
kernel/kcov.c +116 -13
204 lines not on this page · raw message
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Re: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)
Quoted 17 lines · Alexander Potapenko
ioctl(KCOV_UNIQUE_ENABLE)enables collection of deduplicated coverage in the presence ofCONFIG_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.
Quoted 4 lines
Note: when
CONFIG_KCOV_ENABLE_GUARDSis disabled,ioctl(KCOV_UNIQUE_ENABLE)returns-ENOTSUPP, which is consistent with the existing kcov code.Also update the documentation.
Do you have performance measurements (old vs. new mode) that can be included in this commit description?
Quoted 18 lines
Signed-off-by Alexander Potapenko <[email protected]>--- Documentation/dev-tools/kcov.rst | 43 +++++++++++ include/linux/kcov-state.h | 8 ++ include/linux/kcov.h | 2 + include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 129 +++++++++++++++++++++++++++---- 5 files changed, 170 insertions(+), 13 deletions(-)Documentation/dev-tools/kcov.rst +1
-0@@ -137,6 +137,49 @@ mmaps coverage buffer, and then forks child processes in a loop. The child processes only need to enable coverage (it gets disabled automatically when a thread exits). +Unique coverage collection
Documentation/dev-tools/kcov.rst mmaps coverage buffer, and then forks child processes in a loop. The child · line 150
Quoted 10 lines
Documentation/dev-tools/kcov.rst +10
-0+--------------------------- + +Instead of collecting raw PCs, KCOV can deduplicate them on the fly. +This mode is enabled by the ``KCOV_UNIQUE_ENABLE`` ioctl (only available if +``CONFIG_KCOV_ENABLE_GUARDS`` is on). + +.. code-block:: c + + /* Same includes and defines as above. */ + #define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long)
Here it's _IOW.
Quoted 79 lines
Documentation/dev-tools/kcov.rst +32
-0+ #define BITMAP_SIZE (4<<10) + + /* Instead of KCOV_ENABLE, enable unique coverage collection. */ + if (ioctl(fd, KCOV_UNIQUE_ENABLE, BITMAP_SIZE)) + perror("ioctl"), exit(1); + /* Reset the coverage from the tail of the ioctl() call. */ + __atomic_store_n(&cover[BITMAP_SIZE], 0, __ATOMIC_RELAXED); + memset(cover, 0, BITMAP_SIZE * sizeof(unsigned long)); + + /* Call the target syscall call. */ + /* ... */ + + /* Read the number of collected PCs. */ + n = __atomic_load_n(&cover[BITMAP_SIZE], __ATOMIC_RELAXED); + /* Disable the coverage collection. */ + if (ioctl(fd, KCOV_DISABLE, 0)) + perror("ioctl"), exit(1); + +Calling ``ioctl(fd, KCOV_UNIQUE_ENABLE, bitmap_size)`` carves out ``bitmap_size`` +words from those allocated by ``KCOV_INIT_TRACE`` to keep an opaque bitmap that +prevents the kernel from storing the same PC twice. The remaining part of the +trace is used to collect PCs, like in other modes (this part must contain at +least two words, like when collecting non-unique PCs). + +The mapping between a PC and its position in the bitmap is persistent during the +kernel lifetime, so it is possible for the callers to directly use the bitmap +contents as a coverage signal (like when fuzzing userspace with AFL). + +In order to reset the coverage between the runs, the user needs to rewind the +trace (by writing 0 into the first word past ``bitmap_size``) and wipe the whole +bitmap. + Comparison operands collection ------------------------------include/linux/kcov-state.h +8
-0@@ -26,6 +26,14 @@ struct kcov_state {/* Buffer for coverage collection, shared with the userspace. */ unsigned long *trace; +/* Size of the bitmap (in bits). */ +unsigned int bitmap_size; +/* +* Bitmap for coverage deduplication, shared with the +* userspace. +*/ +unsigned long *bitmap; +/* * KCOV sequence number: incremented each time kcov is * reenabled, used by kcov_remote_stop(), see the comment there. include/linux/kcov.h +2
-0@@ -10,6 +10,7 @@ struct task_struct;#ifdef CONFIG_KCOV enum kcov_mode { +KCOV_MODE_INVALID =-1 ,/* Coverage collection is not enabled yet. */ KCOV_MODE_DISABLED =0 , /* KCOV was initialized, but tracing mode hasn't been chosen yet. */@@ -23,6 +24,7 @@ enum kcov_mode {KCOV_MODE_TRACE_CMP =3 ,/* The process owns a KCOV remote reference. */ KCOV_MODE_REMOTE =4 , + KCOV_MODE_TRACE_UNIQUE_PC = 5, };#define KCOV_IN_CTXSW (1 << 30)include/uapi/linux/kcov.h +0
-0
include/uapi/linux/kcov.h struct kcov_remote_arg { · line 25
Quoted 4 lines
include/uapi/linux/kcov.h +1
-0@@ -22,6 +22,7 @@ struct kcov_remote_arg {#define KCOV_ENABLE _IO('c', 100)#define KCOV_DISABLE _IO('c', 101)#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg) +#define KCOV_UNIQUE_ENABLE _IOR('c', 103, unsigned long)
_IOR? The unsigned long arg is copied to the kernel, so this should be _IOW, right?
Quoted 110 lines
include/uapi/linux/kcov.h +0
-0enum {/* kernel/kcov.c +48
-8@@ -29,6 +29,10 @@#include <asm/setup.h> +#ifdef CONFIG_KCOV_ENABLE_GUARDS +atomic_t kcov_guard_max_index =ATOMIC_INIT (1 ); +#endif +#define kcov_debug (fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)/* Number of 64-bit words written per one comparison: */ @@ -161,8 +165,7 @@ static __always_inline bool in_softirq_really(void)return in_serving_softirq () && !in_hardirq () && !in_nmi (); } -static notrace bool check_kcov_mode(enum kcov_mode needed_mode, -struct task_struct *t) +static notrace enum kcov_mode get_kcov_mode(struct task_struct *t) {unsigned int mode;@@ -172,7 +175,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode,* coverage collection section in a softirq. */ if (!in_task () && !(in_softirq_really () && t->kcov_softirq)) -return false; +return KCOV_MODE_INVALID ; mode =READ_ONCE (t->kcov_state.mode);/* * There is some code that runs in interrupts but for which @@ -182,7 +185,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode,* kcov_start(). */ barrier (); -return mode == needed_mode; +return mode; }static notrace unsigned long canonicalize_ip (unsigned long ip)@@ -201,7 +204,7 @@ static void sanitizer_cov_write_subsequent(unsigned long *trace, int size,if (likely (pos < size)) {/* -* Some early interrupt code could bypass check_kcov_mode() check +* Some early interrupt code could bypass get_kcov_mode() check * and invoke __sanitizer_cov_trace_pc(). If such interrupt is * raised between writing pc and updating pos, the pc could be * overitten by the recursive __sanitizer_cov_trace_pc(). @@ -220,7 +223,7 @@ static void sanitizer_cov_write_subsequent(unsigned long *trace, int size,#ifndef CONFIG_KCOV_ENABLE_GUARDS void notrace __sanitizer_cov_trace_pc(void) { -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +if (get_kcov_mode (current) !=KCOV_MODE_TRACE_PC )return ; sanitizer_cov_write_subsequent(current->kcov_state.s.trace,@@ -229,14 +232,73 @@ void notrace __sanitizer_cov_trace_pc(void) }EXPORT_SYMBOL (__sanitizer_cov_trace_pc);#else + +DEFINE_PER_CPU (u32, saved_index); +/* +* Assign an index to a guard variable that does not have one yet. +* For an unlikely case of a race with another task executing the same basic +* block, we store the unused index in a per-cpu variable. +* In an even less likely case the current task may lose a race and get +* rescheduled onto a CPU that already has a saved index, discarding that index. +* This will result in an unused hole in the bitmap, but such events should have +* minor impact on the overall memory consumption. +*/ +static __always_inline u32 init_pc_guard(u32 *guard) +{ +/* If the current CPU has a saved free index, use it. */ +u32 index =this_cpu_xchg (saved_index,0 ); +u32 old_guard; + +if (likely (!index)) +/* +* Allocate a new index. No overflow is possible, because 2**32 +* unique basic blocks will take more space than the max size +* of the kernel text segment. +*/ + index =atomic_inc_return (&kcov_guard_max_index) -1 ; + +/* +* Make sure another task is not initializing the same guard +* concurrently. +*/ + old_guard =cmpxchg (guard,0 , index); +if (unlikely (old_guard)) { +/* We lost the race, save the index for future use. */ +this_cpu_write (saved_index, index); +return old_guard; + } +return index; +} + void notrace __sanitizer_cov_trace_pc_guard(u32 *guard) { -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) -return ; +u32 pc_index;
kernel/kcov.c void notrace __sanitizer_cov_trace_pc(void) · line 282
Quoted 10 lines
kernel/kcov.c +6
-3+enum kcov_mode mode =get_kcov_mode (current); -sanitizer_cov_write_subsequent (current->kcov_state.s.trace, - current->kcov_state.s.trace_size, -canonicalize_ip (_RET_IP_)); +switch (mode) { +case KCOV_MODE_TRACE_UNIQUE_PC : + pc_index =READ_ONCE (*guard); +if (unlikely (!pc_index)) + pc_index =init_pc_guard (guard);
This is an unlikely branch, yet init_pc_guard is __always_inline. Can we somehow make it noinline? I know objtool will complain, but besides the cosmetic issues, doing noinline and just giving it a better name ("kcov_init_pc_guard") and adding that to objtool whilelist will be better for codegen.
Quoted 105 lines
kernel/kcov.c +62
-3+ +/* +* Use the bitmap for coverage deduplication. We assume both +* s.bitmap and s.trace are non-NULL. +*/ +if (likely (pc_index < current->kcov_state.s.bitmap_size)) +if (test_and_set_bit (pc_index, + current->kcov_state.s.bitmap)) +return ; +/* If the PC is new, write it to the trace. */ + fallthrough; +case KCOV_MODE_TRACE_PC : +sanitizer_cov_write_subsequent (current->kcov_state.s.trace, + current->kcov_state.s.trace_size, +canonicalize_ip (_RET_IP_)); +break ; +default : +return ; + } }EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard);@@ -255,7 +317,7 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)u64 *trace; t = current; -if (!check_kcov_mode (KCOV_MODE_TRACE_CMP , t)) +if (get_kcov_mode (t) !=KCOV_MODE_TRACE_CMP )return ; ip =canonicalize_ip (ip);@@ -374,7 +436,7 @@ static void kcov_start(struct task_struct *t, struct kcov *kcov,/* Cache in task struct for performance. */ t->kcov_state.s = state->s;barrier (); -/* See comment in check_kcov_mode(). */ +/* See comment in get_kcov_mode(). */ WRITE_ONCE (t->kcov_state.mode, state->mode); }@@ -408,6 +470,10 @@ static void kcov_reset(struct kcov *kcov) kcov->state.mode =KCOV_MODE_INIT ; kcov->remote = false; kcov->remote_size =0 ; + kcov->state.s.trace = kcov->state.s.area; + kcov->state.s.trace_size = kcov->state.s.size; + kcov->state.s.bitmap =NULL ; + kcov->state.s.bitmap_size =0 ; kcov->state.s.sequence++; }@@ -594,6 +660,41 @@ static inline bool kcov_check_handle(u64 handle, bool common_valid,return false; } +static long kcov_handle_unique_enable (struct kcov *kcov, +unsigned long bitmap_words) +{ +struct task_struct *t = current; + +if (!IS_ENABLED (CONFIG_KCOV_ENABLE_GUARDS )) +return -ENOTSUPP ; +if (kcov->state.mode !=KCOV_MODE_INIT || !kcov->state.s.area) +return -EINVAL ; +if (kcov->t !=NULL || t->kcov !=NULL ) +return -EBUSY ; + +/* +* Cannot use zero-sized bitmap, also the bitmap must leave at least two +* words for the trace. +*/ +if ((!bitmap_words) || (bitmap_words >= (kcov->state.s.size -1 ))) +return -EINVAL ; + + kcov->state.s.bitmap_size = bitmap_words *sizeof (unsigned long ) *8 ; + kcov->state.s.bitmap = kcov->state.s.area; + kcov->state.s.trace_size = kcov->state.s.size - bitmap_words; + kcov->state.s.trace = + ((unsigned long *)kcov->state.s.area + bitmap_words); + +kcov_fault_in_area (kcov); + kcov->state.mode =KCOV_MODE_TRACE_UNIQUE_PC ; +kcov_start (t, kcov, &kcov->state); + kcov->t = t; +/* Put either in kcov_task_exit() or in KCOV_DISABLE. */ +kcov_get (kcov); + +return 0 ; +} +static int kcov_ioctl_locked (struct kcov *kcov,unsigned int cmd,unsigned long arg) {@@ -627,6 +728,8 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,/* Put either in kcov_task_exit() or in KCOV_DISABLE. */ kcov_get (kcov);return 0 ; +case KCOV_UNIQUE_ENABLE : +return kcov_handle_unique_enable (kcov, arg);case KCOV_DISABLE :/* Disable coverage for the current task. */ unused = arg; --2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerRe: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)
Quoted 19 lines · Marco Elver
Quoted 17 lines · Alexander Potapenko
ioctl(KCOV_UNIQUE_ENABLE)enables collection of deduplicated coverage in the presence ofCONFIG_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.
Quoted 7 lines
Quoted 4 lines
Note: when
CONFIG_KCOV_ENABLE_GUARDSis disabled,ioctl(KCOV_UNIQUE_ENABLE)returns-ENOTSUPP, which is consistent with the existing kcov code.Also update the documentation.
Do you have performance measurements (old vs. new mode) that can be included in this commit description?
That's hard to measure.
According to the latest measurements (50 instances x 24h with and without deduplication), if we normalize by pure fuzzing time, exec total goes down by 2.1% with p=0.01.
On the other hand, if we normalize by fuzzer uptime, the reduction is statistically insignificant (-1.0% with p=0.20)
In both cases, we observe a statistically significant (p<0.01) increase in corpus size (+0.6%) and coverage (+0.6) and -99.8% reduction in coverage overflows.
So while there might be a slight slowdown introduced by this patch series, it still positively impacts fuzzing.
I can add something along these lines to the commit description.
Quoted 7 lines
Documentation/dev-tools/kcov.rst mmaps coverage buffer, and then forks child processes in a loop. The child · line 150
Quoted 4 lines
+.. code-block:: c
Documentation/dev-tools/kcov.rst +3
-0+ + /* Same includes and defines as above. */ + #define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long)Here it's
_IOW.
...
Quoted 4 lines
Quoted 4 lines
include/uapi/linux/kcov.h +0
-0
Quoted 8 lines
include/uapi/linux/kcov.h struct kcov_remote_arg { · line 25
Quoted 5 lines
include/uapi/linux/kcov.h +1
-0@@ -22,6 +22,7 @@ struct kcov_remote_arg {#define KCOV_ENABLE _IO('c', 100)#define KCOV_DISABLE _IO('c', 101)#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg) +#define KCOV_UNIQUE_ENABLE _IOR('c', 103, unsigned long)
_IOR? The unsigned long arg is copied to the kernel, so this should be_IOW, right?
Right, thanks for spotting!
This also suggests our declaration of KCOV_INIT_TRACE is incorrect (should also be _IOW), but I don't think we can do much about that now.
Quoted 16 lines
Quoted 5 lines
include/uapi/linux/kcov.h +1
-2void notrace __sanitizer_cov_trace_pc_guard(u32 *guard) { -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) -return ; +u32 pc_index;include/uapi/linux/kcov.h struct kcov_remote_arg {
Quoted 10 lines
include/uapi/linux/kcov.h +6
-3+enum kcov_mode mode =get_kcov_mode (current); -sanitizer_cov_write_subsequent (current->kcov_state.s.trace, - current->kcov_state.s.trace_size, -canonicalize_ip (_RET_IP_)); +switch (mode) { +case KCOV_MODE_TRACE_UNIQUE_PC : + pc_index =READ_ONCE (*guard); +if (unlikely (!pc_index)) + pc_index =init_pc_guard (guard);
Quoted 5 lines
This is an unlikely branch, yet
init_pc_guardis__always_inline. Can we somehow make it noinline? I know objtool will complain, but besides the cosmetic issues, doing noinline and just giving it a better name ("kcov_init_pc_guard") and adding that to objtool whilelist will be better for codegen.
I don't expect it to have a big impact on the performance, but let's check it out.
Alexander Potapenko
reviewerRe: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)
Quoted 16 lines
Quoted 16 lines
Quoted 15 lines
void notrace
__sanitizer_cov_trace_pc_guard(u32 *guard){kernel/kcov.c +7
-5-if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) -return ; +u32 pc_index; +enum kcov_mode mode =get_kcov_mode (current); -sanitizer_cov_write_subsequent (current->kcov_state.s.trace, - current->kcov_state.s.trace_size, -canonicalize_ip (_RET_IP_)); +switch (mode) { +case KCOV_MODE_TRACE_UNIQUE_PC : + pc_index =READ_ONCE (*guard); +if (unlikely (!pc_index)) + pc_index =init_pc_guard (guard);
Quoted 8 lines
Quoted 5 lines
This is an unlikely branch, yet
init_pc_guardis__always_inline. Can we somehow make it noinline? I know objtool will complain, but besides the cosmetic issues, doing noinline and just giving it a better name ("kcov_init_pc_guard") and adding that to objtool whilelist will be better for codegen.I don't expect it to have a big impact on the performance, but let's check it out.
Oh wait, now I remember that when we uninline that function, that introduces a register spill in __sanitizer_cov_trace_pc_guard, which we want to avoid.
Alexander Potapenko
reviewerRe: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)
In reply to Alexander PotapenkoQuoted 12 lines
void notrace
__sanitizer_cov_trace_pc_guard(u32 *guard){kernel/kcov.c +4
-5-if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) -return ; +u32 pc_index; +enum kcov_mode mode =get_kcov_mode (current); -sanitizer_cov_write_subsequent (current->kcov_state.s.trace, - current->kcov_state.s.trace_size, -canonicalize_ip (_RET_IP_)); +switch (mode) { +case KCOV_MODE_TRACE_UNIQUE_PC :
kernel/kcov.c void notrace __sanitizer_cov_trace_pc(void) · line 289
Quoted 10 lines
kernel/kcov.c +10
-0+ pc_index =READ_ONCE (*guard); +if (unlikely (!pc_index)) + pc_index =init_pc_guard (guard); + +/* +* Use the bitmap for coverage deduplication. We assume both +* s.bitmap and s.trace are non-NULL. +*/ +if (likely (pc_index < current->kcov_state.s.bitmap_size)) + if (test_and_set_bit(pc_index,
A promising improvement would be removing the LOCK prefix here by changing test_and_set_bit() to __test_and_set_bit().
Quoted 14 lines
kernel/kcov.c +12
-0+ current->kcov_state.s.bitmap)) +return ; +/* If the PC is new, write it to the trace. */ + fallthrough; +case KCOV_MODE_TRACE_PC : +sanitizer_cov_write_subsequent (current->kcov_state.s.trace, + current->kcov_state.s.trace_size, +canonicalize_ip (_RET_IP_)); +break ; +default : +return ; + } }EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard);
Re: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)
In reply to Alexander PotapenkoQuoted 39 lines · Alexander Potapenko
ioctl(KCOV_UNIQUE_ENABLE)enables collection of deduplicated coverage in the presence ofCONFIG_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.Note: when
CONFIG_KCOV_ENABLE_GUARDSis disabled,ioctl(KCOV_UNIQUE_ENABLE)returns-ENOTSUPP, which is consistent with the existing kcov code.Also update the documentation.
Signed-off-by Alexander Potapenko <[email protected]>--- Documentation/dev-tools/kcov.rst | 43 +++++++++++ include/linux/kcov-state.h | 8 ++ include/linux/kcov.h | 2 + include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 129 +++++++++++++++++++++++++++---- 5 files changed, 170 insertions(+), 13 deletions(-)Documentation/dev-tools/kcov.rst +1
-0@@ -137,6 +137,49 @@ mmaps coverage buffer, and then forks child processes in a loop. The child processes only need to enable coverage (it gets disabled automatically when a thread exits). +Unique coverage collection
Documentation/dev-tools/kcov.rst mmaps coverage buffer, and then forks child processes in a loop. The child · line 150
Quoted 10 lines
Documentation/dev-tools/kcov.rst +10
-0+--------------------------- + +Instead of collecting raw PCs, KCOV can deduplicate them on the fly. +This mode is enabled by the ``KCOV_UNIQUE_ENABLE`` ioctl (only available if +``CONFIG_KCOV_ENABLE_GUARDS`` is on). + +.. code-block:: c + + /* Same includes and defines as above. */ + #define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long)
in kcov.h it was defined was _IOR, but _IOW here,
#define KCOV_UNIQUE_ENABLE _IOR('c', 103, unsigned long)
Quoted 309 lines
Documentation/dev-tools/kcov.rst +32
-0+ #define BITMAP_SIZE (4<<10) + + /* Instead of KCOV_ENABLE, enable unique coverage collection. */ + if (ioctl(fd, KCOV_UNIQUE_ENABLE, BITMAP_SIZE)) + perror("ioctl"), exit(1); + /* Reset the coverage from the tail of the ioctl() call. */ + __atomic_store_n(&cover[BITMAP_SIZE], 0, __ATOMIC_RELAXED); + memset(cover, 0, BITMAP_SIZE * sizeof(unsigned long)); + + /* Call the target syscall call. */ + /* ... */ + + /* Read the number of collected PCs. */ + n = __atomic_load_n(&cover[BITMAP_SIZE], __ATOMIC_RELAXED); + /* Disable the coverage collection. */ + if (ioctl(fd, KCOV_DISABLE, 0)) + perror("ioctl"), exit(1); + +Calling ``ioctl(fd, KCOV_UNIQUE_ENABLE, bitmap_size)`` carves out ``bitmap_size`` +words from those allocated by ``KCOV_INIT_TRACE`` to keep an opaque bitmap that +prevents the kernel from storing the same PC twice. The remaining part of the +trace is used to collect PCs, like in other modes (this part must contain at +least two words, like when collecting non-unique PCs). + +The mapping between a PC and its position in the bitmap is persistent during the +kernel lifetime, so it is possible for the callers to directly use the bitmap +contents as a coverage signal (like when fuzzing userspace with AFL). + +In order to reset the coverage between the runs, the user needs to rewind the +trace (by writing 0 into the first word past ``bitmap_size``) and wipe the whole +bitmap. + Comparison operands collection ------------------------------include/linux/kcov-state.h +8
-0@@ -26,6 +26,14 @@ struct kcov_state {/* Buffer for coverage collection, shared with the userspace. */ unsigned long *trace; +/* Size of the bitmap (in bits). */ +unsigned int bitmap_size; +/* +* Bitmap for coverage deduplication, shared with the +* userspace. +*/ +unsigned long *bitmap; +/* * KCOV sequence number: incremented each time kcov is * reenabled, used by kcov_remote_stop(), see the comment there. include/linux/kcov.h +2
-0@@ -10,6 +10,7 @@ struct task_struct;#ifdef CONFIG_KCOV enum kcov_mode { +KCOV_MODE_INVALID =-1 ,/* Coverage collection is not enabled yet. */ KCOV_MODE_DISABLED =0 , /* KCOV was initialized, but tracing mode hasn't been chosen yet. */@@ -23,6 +24,7 @@ enum kcov_mode {KCOV_MODE_TRACE_CMP =3 ,/* The process owns a KCOV remote reference. */ KCOV_MODE_REMOTE =4 , + KCOV_MODE_TRACE_UNIQUE_PC = 5, };#define KCOV_IN_CTXSW (1 << 30)include/uapi/linux/kcov.h +1
-0@@ -22,6 +22,7 @@ struct kcov_remote_arg {#define KCOV_ENABLE _IO('c', 100)#define KCOV_DISABLE _IO('c', 101)#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg) +#define KCOV_UNIQUE_ENABLE _IOR('c', 103, unsigned long)enum {/* kernel/kcov.c +116
-13@@ -29,6 +29,10 @@#include <asm/setup.h> +#ifdef CONFIG_KCOV_ENABLE_GUARDS +atomic_t kcov_guard_max_index =ATOMIC_INIT (1 ); +#endif +#define kcov_debug (fmt, ...) pr_debug("%s: " fmt, __func__, ##__VA_ARGS__)/* Number of 64-bit words written per one comparison: */ @@ -161,8 +165,7 @@ static __always_inline bool in_softirq_really(void)return in_serving_softirq () && !in_hardirq () && !in_nmi (); } -static notrace bool check_kcov_mode(enum kcov_mode needed_mode, -struct task_struct *t) +static notrace enum kcov_mode get_kcov_mode(struct task_struct *t) {unsigned int mode;@@ -172,7 +175,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode,* coverage collection section in a softirq. */ if (!in_task () && !(in_softirq_really () && t->kcov_softirq)) -return false; +return KCOV_MODE_INVALID ; mode =READ_ONCE (t->kcov_state.mode);/* * There is some code that runs in interrupts but for which @@ -182,7 +185,7 @@ static notrace bool check_kcov_mode(enum kcov_mode needed_mode,* kcov_start(). */ barrier (); -return mode == needed_mode; +return mode; }static notrace unsigned long canonicalize_ip (unsigned long ip)@@ -201,7 +204,7 @@ static void sanitizer_cov_write_subsequent(unsigned long *trace, int size,if (likely (pos < size)) {/* -* Some early interrupt code could bypass check_kcov_mode() check +* Some early interrupt code could bypass get_kcov_mode() check * and invoke __sanitizer_cov_trace_pc(). If such interrupt is * raised between writing pc and updating pos, the pc could be * overitten by the recursive __sanitizer_cov_trace_pc(). @@ -220,7 +223,7 @@ static void sanitizer_cov_write_subsequent(unsigned long *trace, int size,#ifndef CONFIG_KCOV_ENABLE_GUARDS void notrace __sanitizer_cov_trace_pc(void) { -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +if (get_kcov_mode (current) !=KCOV_MODE_TRACE_PC )return ; sanitizer_cov_write_subsequent(current->kcov_state.s.trace,@@ -229,14 +232,73 @@ void notrace __sanitizer_cov_trace_pc(void) }EXPORT_SYMBOL (__sanitizer_cov_trace_pc);#else + +DEFINE_PER_CPU (u32, saved_index); +/* +* Assign an index to a guard variable that does not have one yet. +* For an unlikely case of a race with another task executing the same basic +* block, we store the unused index in a per-cpu variable. +* In an even less likely case the current task may lose a race and get +* rescheduled onto a CPU that already has a saved index, discarding that index. +* This will result in an unused hole in the bitmap, but such events should have +* minor impact on the overall memory consumption. +*/ +static __always_inline u32 init_pc_guard(u32 *guard) +{ +/* If the current CPU has a saved free index, use it. */ +u32 index =this_cpu_xchg (saved_index,0 ); +u32 old_guard; + +if (likely (!index)) +/* +* Allocate a new index. No overflow is possible, because 2**32 +* unique basic blocks will take more space than the max size +* of the kernel text segment. +*/ + index =atomic_inc_return (&kcov_guard_max_index) -1 ; + +/* +* Make sure another task is not initializing the same guard +* concurrently. +*/ + old_guard =cmpxchg (guard,0 , index); +if (unlikely (old_guard)) { +/* We lost the race, save the index for future use. */ +this_cpu_write (saved_index, index); +return old_guard; + } +return index; +} + void notrace __sanitizer_cov_trace_pc_guard(u32 *guard) { -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) -return ; +u32 pc_index; +enum kcov_mode mode =get_kcov_mode (current); -sanitizer_cov_write_subsequent (current->kcov_state.s.trace, - current->kcov_state.s.trace_size, -canonicalize_ip (_RET_IP_)); +switch (mode) { +case KCOV_MODE_TRACE_UNIQUE_PC : + pc_index =READ_ONCE (*guard); +if (unlikely (!pc_index)) + pc_index =init_pc_guard (guard); + +/* +* Use the bitmap for coverage deduplication. We assume both +* s.bitmap and s.trace are non-NULL. +*/ +if (likely (pc_index < current->kcov_state.s.bitmap_size)) +if (test_and_set_bit (pc_index, + current->kcov_state.s.bitmap)) +return ; +/* If the PC is new, write it to the trace. */ + fallthrough; +case KCOV_MODE_TRACE_PC : +sanitizer_cov_write_subsequent (current->kcov_state.s.trace, + current->kcov_state.s.trace_size, +canonicalize_ip (_RET_IP_)); +break ; +default : +return ; + } }EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard);@@ -255,7 +317,7 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)u64 *trace; t = current; -if (!check_kcov_mode (KCOV_MODE_TRACE_CMP , t)) +if (get_kcov_mode (t) !=KCOV_MODE_TRACE_CMP )return ; ip =canonicalize_ip (ip);@@ -374,7 +436,7 @@ static void kcov_start(struct task_struct *t, struct kcov *kcov,/* Cache in task struct for performance. */ t->kcov_state.s = state->s;barrier (); -/* See comment in check_kcov_mode(). */ +/* See comment in get_kcov_mode(). */ WRITE_ONCE (t->kcov_state.mode, state->mode); }@@ -408,6 +470,10 @@ static void kcov_reset(struct kcov *kcov) kcov->state.mode =KCOV_MODE_INIT ; kcov->remote = false; kcov->remote_size =0 ; + kcov->state.s.trace = kcov->state.s.area; + kcov->state.s.trace_size = kcov->state.s.size; + kcov->state.s.bitmap =NULL ; + kcov->state.s.bitmap_size =0 ; kcov->state.s.sequence++; }@@ -594,6 +660,41 @@ static inline bool kcov_check_handle(u64 handle, bool common_valid,return false; } +static long kcov_handle_unique_enable (struct kcov *kcov, +unsigned long bitmap_words) +{ +struct task_struct *t = current; + +if (!IS_ENABLED (CONFIG_KCOV_ENABLE_GUARDS )) +return -ENOTSUPP ; +if (kcov->state.mode !=KCOV_MODE_INIT || !kcov->state.s.area) +return -EINVAL ; +if (kcov->t !=NULL || t->kcov !=NULL ) +return -EBUSY ; + +/* +* Cannot use zero-sized bitmap, also the bitmap must leave at least two +* words for the trace. +*/ +if ((!bitmap_words) || (bitmap_words >= (kcov->state.s.size -1 ))) +return -EINVAL ; + + kcov->state.s.bitmap_size = bitmap_words *sizeof (unsigned long ) *8 ; + kcov->state.s.bitmap = kcov->state.s.area; + kcov->state.s.trace_size = kcov->state.s.size - bitmap_words; + kcov->state.s.trace = + ((unsigned long *)kcov->state.s.area + bitmap_words); + +kcov_fault_in_area (kcov); + kcov->state.mode =KCOV_MODE_TRACE_UNIQUE_PC ; +kcov_start (t, kcov, &kcov->state); + kcov->t = t; +/* Put either in kcov_task_exit() or in KCOV_DISABLE. */ +kcov_get (kcov); + +return 0 ; +} +static int kcov_ioctl_locked (struct kcov *kcov,unsigned int cmd,unsigned long arg) {@@ -627,6 +728,8 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,/* Put either in kcov_task_exit() or in KCOV_DISABLE. */ kcov_get (kcov);return 0 ; +case KCOV_UNIQUE_ENABLE : +return kcov_handle_unique_enable (kcov, arg);case KCOV_DISABLE :/* Disable coverage for the current task. */ unused = arg;Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerRe: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)
Quoted 40 lines · Joey Jiao
Quoted 38 lines · Alexander Potapenko
ioctl(KCOV_UNIQUE_ENABLE)enables collection of deduplicated coverage in the presence ofCONFIG_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.Note: when
CONFIG_KCOV_ENABLE_GUARDSis disabled,ioctl(KCOV_UNIQUE_ENABLE)returns-ENOTSUPP, which is consistent with the existing kcov code.Also update the documentation.
Signed-off-by Alexander Potapenko <[email protected]>--- Documentation/dev-tools/kcov.rst | 43 +++++++++++ include/linux/kcov-state.h | 8 ++ include/linux/kcov.h | 2 + include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 129 +++++++++++++++++++++++++++---- 5 files changed, 170 insertions(+), 13 deletions(-)Documentation/dev-tools/kcov.rst +0
-0@@ -137,6 +137,49 @@ mmaps coverage buffer, and then forks child processes in a loop. The child processes only need to enable coverage (it gets disabled automatically when a thread exits).
Quoted 12 lines
Documentation/dev-tools/kcov.rst mmaps coverage buffer, and then forks child processes in a loop. The child · line 150
Quoted 11 lines
Documentation/dev-tools/kcov.rst +11
-0+Unique coverage collection +--------------------------- + +Instead of collecting raw PCs, KCOV can deduplicate them on the fly. +This mode is enabled by the ``KCOV_UNIQUE_ENABLE`` ioctl (only available if +``CONFIG_KCOV_ENABLE_GUARDS`` is on). + +.. code-block:: c + + /* Same includes and defines as above. */ + #define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long)in
kcov.hit was defined was_IOR, but_IOWhere,
Yeah, Marco spotted this on another patch, I'll fix kcov.h.
Alexander Potapenko
reviewerPATCH 6/7 x86: objtool: add support for R_X86_64_REX_GOTPCRELX
In reply to Alexander PotapenkoWhen compiling modules with -fsanitize-coverage=trace-pc-guard, Clang will emit R_X86_64_REX_GOTPCRELX relocations for the __start___sancov_guards and __stop___sancov_guards symbols. Although these relocations can be resolved within the same binary, they are left over by the linker because of the --emit-relocs flag.
This patch makes it possible to resolve the R_X86_64_REX_GOTPCRELX relocations at runtime, as doing so does not require a .got section. In addition, add a missing overflow check to R_X86_64_PC32/R_X86_64_PLT32.
--- arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 ++++++++ arch/x86/um/asm/elf.h | 1 + tools/objtool/arch/x86/decode.c | 1 + 4 files changed, 11 insertions(+)
arch/x86/include/asm/elf.h +1 -0
@@ -63,6 +63,7 @@ typedef struct user_i387_struct elf_fpregset_t;#define R_X86_64_8 14/* Direct 8 bit sign extended */ #define R_X86_64_PC8 15/* 8 bit sign extended pc relative */ #define R_X86_64_PC64 24/* Place relative 64-bit signed */ +#define R_X86_64_REX_GOTPCRELX 42/* R_X86_64_GOTPCREL with optimizations */ /* * These are used to set parameters in the core dumps.
arch/x86/kernel/module.c +8 -0
@@ -133,6 +133,14 @@ static int __write_relocate_add(Elf64_Shdr *sechdrs,case R_X86_64_PC32 :case R_X86_64_PLT32 : val -= (u64 )loc; +if ((s64 )val != *(s32 *)&val) + goto overflow; + size =4 ; +break ; +case R_X86_64_REX_GOTPCRELX : + val -= (u64 )loc; +if ((s64 )val != *(s32 *)&val) + goto overflow; size =4 ;break ;case R_X86_64_PC64 :
arch/x86/um/asm/elf.h +1 -0
@@ -119,6 +119,7 @@ do { \#define R_X86_64_8 14/* Direct 8 bit sign extended */ #define R_X86_64_PC8 15/* 8 bit sign extended pc relative */ #define R_X86_64_PC64 24/* Place relative 64-bit signed */ +#define R_X86_64_REX_GOTPCRELX 42/* R_X86_64_GOTPCREL with optimizations */ /* * This is used to ensure we don't load something for the wrong architecture.
tools/objtool/arch/x86/decode.c +1 -0
@@ -93,6 +93,7 @@ bool arch_pc_relative_reloc(struct reloc *reloc)case R_X86_64_PLT32 :case R_X86_64_GOTPC32 :case R_X86_64_GOTPCREL : +case R_X86_64_REX_GOTPCRELX :return true;default :
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Re: [PATCH 6/7] x86: objtool: add support for R_X86_64_REX_GOTPCRELX
Quoted 39 lines · Alexander Potapenko
When compiling modules with -fsanitize-coverage=trace-pc-guard, Clang will emit
R_X86_64_REX_GOTPCRELXrelocations for the__start___sancov_guardsand__stop___sancov_guardssymbols. Although these relocations can be resolved within the same binary, they are left over by the linker because of the --emit-relocs flag.This patch makes it possible to resolve the
R_X86_64_REX_GOTPCRELXrelocations at runtime, as doing so does not require a .got section. In addition, add a missing overflow check to R_X86_64_PC32/R_X86_64_PLT32.Signed-off-by Alexander Potapenko <[email protected]>--- arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 ++++++++ arch/x86/um/asm/elf.h | 1 + tools/objtool/arch/x86/decode.c | 1 + 4 files changed, 11 insertions(+)arch/x86/include/asm/elf.h +1
-0@@ -63,6 +63,7 @@ typedef struct user_i387_struct elf_fpregset_t;#define R_X86_64_8 14/* Direct 8 bit sign extended */ #define R_X86_64_PC8 15/* 8 bit sign extended pc relative */ #define R_X86_64_PC64 24/* Place relative 64-bit signed */ +#define R_X86_64_REX_GOTPCRELX 42/* R_X86_64_GOTPCREL with optimizations */ /* * These are used to set parameters in the core dumps. arch/x86/kernel/module.c +0
-0@@ -133,6 +133,14 @@ static int __write_relocate_add(Elf64_Shdr *sechdrs,case R_X86_64_PC32 :case R_X86_64_PLT32 : val -= (u64 )loc;
arch/x86/kernel/module.c static int __write_relocate_add(Elf64_Shdr *sechdrs, · line 145
Quoted 10 lines
arch/x86/kernel/module.c +8
-0+if ((s64 )val != *(s32 *)&val) + goto overflow; + size =4 ; +break ; +case R_X86_64_REX_GOTPCRELX : + val -= (u64 )loc; +if ((s64 )val != *(s32 *)&val) + goto overflow; size =4 ;break ;
These two cases are the same. You probably want:
case R_X86_64_PC32: case R_X86_64_PLT32: case R_X86_64_REX_GOTPCRELX: val -= (u64)loc; if ((s64)val != *(s32 *)&val) goto overflow; size = 4; break;
Uros.
Alexander Potapenko
reviewerRe: [PATCH 6/7] x86: objtool: add support for R_X86_64_REX_GOTPCRELX
Quoted 56 lines · Uros Bizjak
Quoted 39 lines · Alexander Potapenko
When compiling modules with -fsanitize-coverage=trace-pc-guard, Clang will emit
R_X86_64_REX_GOTPCRELXrelocations for the__start___sancov_guardsand__stop___sancov_guardssymbols. Although these relocations can be resolved within the same binary, they are left over by the linker because of the --emit-relocs flag.This patch makes it possible to resolve the
R_X86_64_REX_GOTPCRELXrelocations at runtime, as doing so does not require a .got section. In addition, add a missing overflow check to R_X86_64_PC32/R_X86_64_PLT32.Signed-off-by Alexander Potapenko <[email protected]>--- arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 ++++++++ arch/x86/um/asm/elf.h | 1 + tools/objtool/arch/x86/decode.c | 1 + 4 files changed, 11 insertions(+)arch/x86/include/asm/elf.h +1
-0@@ -63,6 +63,7 @@ typedef struct user_i387_struct elf_fpregset_t;#define R_X86_64_8 14/* Direct 8 bit sign extended */ #define R_X86_64_PC8 15/* 8 bit sign extended pc relative */ #define R_X86_64_PC64 24/* Place relative 64-bit signed */ +#define R_X86_64_REX_GOTPCRELX 42/* R_X86_64_GOTPCREL with optimizations */ /* * These are used to set parameters in the core dumps. arch/x86/kernel/module.c +0
-0@@ -133,6 +133,14 @@ static int __write_relocate_add(Elf64_Shdr *sechdrs,case R_X86_64_PC32 :case R_X86_64_PLT32 : val -= (u64 )loc;arch/x86/kernel/module.c static int __write_relocate_add(Elf64_Shdr *sechdrs, · line 145
Quoted 10 lines
arch/x86/kernel/module.c +8
-0+if ((s64 )val != *(s32 *)&val) + goto overflow; + size =4 ; +break ; +case R_X86_64_REX_GOTPCRELX : + val -= (u64 )loc; +if ((s64 )val != *(s32 *)&val) + goto overflow; size =4 ;break ;These two cases are the same. You probably want:
Quoted 9 lines
case R_X86_64_PC32:
case R_X86_64_PLT32:
case R_X86_64_REX_GOTPCRELX:
val -= (u64)loc;
if ((s64)val != *(s32 *)&val)
goto overflow;
size = 4;
break;You are right, I overlooked this, as well as the other R_X86_64_REX_GOTPCRELX case above.
Ard, do you think we can relax the code handling __stack_chk_guard to accept every R_X86_64_REX_GOTPCRELX relocation?
Re: [PATCH 6/7] x86: objtool: add support for R_X86_64_REX_GOTPCRELX
Hi,
Quoted 5 lines · Alexander Potapenko
Quoted 3 lines · Uros Bizjak
Quoted 7 lines
Quoted 7 lines · Alexander Potapenko
Quoted 6 lines
When compiling modules with -fsanitize-coverage=trace-pc-guard, Clang will emit
R_X86_64_REX_GOTPCRELXrelocations for the__start___sancov_guardsand__stop___sancov_guardssymbols. Although these relocations can be resolved within the same binary, they are left over by the linker because of the --emit-relocs flag.
Not sure what you mean here - --emit-relocs is not used for modules, only for vmlinux.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
This patch makes it possible to resolve the
R_X86_64_REX_GOTPCRELXrelocations at runtime, as doing so does not require a .got section.
Why not? R_X86_64_REX_GOTPCRELX is *not* a PC32 reference to the symbol, it is a PC32 reference to a 64-bit global variable that contains the absolute address of the symbol.
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
In addition, add a missing overflow check to R_X86_64_PC32/R_X86_64_PLT32.
Signed-off-by Alexander Potapenko <[email protected]>--- arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 ++++++++ arch/x86/um/asm/elf.h | 1 + tools/objtool/arch/x86/decode.c | 1 + 4 files changed, 11 insertions(+)
Quoted 10 lines
Quoted 10 lines
arch/x86/include/asm/elf.h typedef struct user_i387_struct elf_fpregset_t; · line 67
Quoted 10 lines
arch/x86/include/asm/elf.h +1
-0@@ -63,6 +63,7 @@ typedef struct user_i387_struct elf_fpregset_t;#define R_X86_64_8 14/* Direct 8 bit sign extended */ #define R_X86_64_PC8 15/* 8 bit sign extended pc relative */ #define R_X86_64_PC64 24/* Place relative 64-bit signed */ +#define R_X86_64_REX_GOTPCRELX 42/* R_X86_64_GOTPCREL with optimizations */
Why do you need this? arch/x86/kernel/module.c already has a reference to R_X86_64_REX_GOTPCRELX so surely it is defined already somewhere.
Quoted 33 lines
Quoted 23 lines
Quoted 10 lines
arch/x86/include/asm/elf.h +0
-0/* * These are used to set parameters in the core dumps. arch/x86/kernel/module.c +0
-0@@ -133,6 +133,14 @@ static int __write_relocate_add(Elf64_Shdr *sechdrs,case R_X86_64_PC32 :case R_X86_64_PLT32 : val -= (u64 )loc;arch/x86/kernel/module.c static int __write_relocate_add(Elf64_Shdr *sechdrs, · line 145
Quoted 10 lines
arch/x86/kernel/module.c +8
-0+if ((s64 )val != *(s32 *)&val) + goto overflow; + size =4 ; +break ; +case R_X86_64_REX_GOTPCRELX : + val -= (u64 )loc; +if ((s64 )val != *(s32 *)&val) + goto overflow; size =4 ;break ;These two cases are the same. You probably want:
Quoted 9 lines
case R_X86_64_PC32: case R_X86_64_PLT32: case R_X86_64_REX_GOTPCRELX: val -= (u64)loc; if ((s64)val != *(s32 *)&val) goto overflow; size = 4; break;
Quoted 2 lines
You are right, I overlooked this, as well as the other
R_X86_64_REX_GOTPCRELXcase above.
They are most definitely *not* the same.
Quoted 2 lines
Ard, do you think we can relax the code handling
__stack_chk_guardto accept everyR_X86_64_REX_GOTPCRELXrelocation?
Isn't it possible to discourage Clang from using R_X86_64_REX_GOTPCRELX? Does -fdirect-access-external-data make any difference here?
In any case, to resolve these relocations correctly, the reference need to be made to point to global variables that carry the absolute addresses of __start___sancov_guards and __stop___sancov_guards. Ideally, these variables would be allocated and populated on the fly, similar to how the linker allocates GOT entries at build time. But this adds a lot of complexity for something that we don't want to see in the first place.
Alternatively, the references could be relaxed, i.e., MOV converted to LEA etc. The x86 ELF psABI describes how this is supposed to work for R_X86_64_REX_GOTPCRELX but it involves rewriting the instructions so it is a bit tedious.
But it would be much better to just fix the compiler.
Alexander Potapenko
reviewerPATCH 7/7 mm/kasan: define __asan_before_dynamic_init, __asan_after_dynamic_init
In reply to Alexander PotapenkoCalls to __asan_before_dynamic_init() and __asan_after_dynamic_init() are inserted by Clang when building with coverage guards. These functions can be used to detect initialization order fiasco bugs in the userspace, but it is fine for them to be no-ops in the kernel.
--- mm/kasan/generic.c | 18 ++++++++++++++++++ mm/kasan/kasan.h | 2 ++ 2 files changed, 20 insertions(+)
mm/kasan/generic.c +18 -0
@@ -238,6 +238,24 @@ void __asan_unregister_globals(void *ptr, ssize_t size) }EXPORT_SYMBOL (__asan_unregister_globals); +#if defined(CONFIG_KCOV_ENABLE_GUARDS ) +/* +* __asan_before_dynamic_init() and __asan_after_dynamic_init() are inserted +* when the user requests building with coverage guards. In the userspace, these +* two functions can be used to detect initialization order fiasco bugs, but in +* the kernel they can be no-ops. +*/ +void __asan_before_dynamic_init (const char *module_name) +{ +} +EXPORT_SYMBOL (__asan_before_dynamic_init); + +void __asan_after_dynamic_init (void ) +{ +} +EXPORT_SYMBOL (__asan_after_dynamic_init); +#endif +#define DEFINE_ASAN_LOAD_STORE (size) \ void __asan_load##size(void *addr) \ { \
mm/kasan/kasan.h +2 -0
@@ -582,6 +582,8 @@ void kasan_restore_multi_shot(bool enabled);void __asan_register_globals (void *globals,ssize_t size);void __asan_unregister_globals (void *globals,ssize_t size); +void __asan_before_dynamic_init (const char *module_name); +void __asan_after_dynamic_init (void );void __asan_handle_no_return (void );void __asan_alloca_poison (void *,ssize_t size);void __asan_allocas_unpoison (void *stack_top,ssize_t stack_bottom);
Signature · 1 line
2.49.0.604.gff1f9ca942-goog
Re: [PATCH 7/7] mm/kasan: define __asan_before_dynamic_init, __asan_after_dynamic_init
Quoted 7 lines · Alexander Potapenko
Calls to
__asan_before_dynamic_init()and__asan_after_dynamic_init()are inserted by Clang when building with coverage guards. These functions can be used to detect initialization order fiasco bugs in the userspace, but it is fine for them to be no-ops in the kernel.Signed-off-by Alexander Potapenko <[email protected]>
This patch should be before the one adding coverage guard instrumentation, otherwise KASAN builds will be broken intermittently, which would break bisection.
Quoted 50 lines
--- mm/kasan/generic.c | 18 ++++++++++++++++++ mm/kasan/kasan.h | 2 ++ 2 files changed, 20 insertions(+)mm/kasan/generic.c +18
-0@@ -238,6 +238,24 @@ void __asan_unregister_globals(void *ptr, ssize_t size) }EXPORT_SYMBOL (__asan_unregister_globals); +#if defined(CONFIG_KCOV_ENABLE_GUARDS ) +/* +* __asan_before_dynamic_init() and __asan_after_dynamic_init() are inserted +* when the user requests building with coverage guards. In the userspace, these +* two functions can be used to detect initialization order fiasco bugs, but in +* the kernel they can be no-ops. +*/ +void __asan_before_dynamic_init (const char *module_name) +{ +} +EXPORT_SYMBOL (__asan_before_dynamic_init); + +void __asan_after_dynamic_init (void ) +{ +} +EXPORT_SYMBOL (__asan_after_dynamic_init); +#endif +#define DEFINE_ASAN_LOAD_STORE (size) \ void __asan_load##size(void *addr) \ { \mm/kasan/kasan.h +2
-1@@ -582,6 +582,8 @@ void kasan_restore_multi_shot(bool enabled);void __asan_register_globals (void *globals,ssize_t size);void __asan_unregister_globals (void *globals,ssize_t size); +void __asan_before_dynamic_init (const char *module_name); +void __asan_after_dynamic_init (void );void __asan_handle_no_return (void );void __asan_alloca_poison (void *,ssize_t size);void __asan_allocas_unpoison (void *stack_top,ssize_t stack_bottom); --2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerRe: [PATCH 7/7] mm/kasan: define __asan_before_dynamic_init, __asan_after_dynamic_init
Quoted 8 lines · Marco Elver
Quoted 6 lines · Alexander Potapenko
Calls to
__asan_before_dynamic_init()and__asan_after_dynamic_init()are inserted by Clang when building with coverage guards. These functions can be used to detect initialization order fiasco bugs in the userspace, but it is fine for them to be no-ops in the kernel.
Quoted 5 lines
Quoted 1 line
Signed-off-by Alexander Potapenko <[email protected]>This patch should be before the one adding coverage guard instrumentation, otherwise KASAN builds will be broken intermittently, which would break bisection.
Right, I'm gonna move it in v2. Thanks!
Dmitry Vyukov
reviewerQuoted 23 lines · Alexander Potapenko
As mentioned by Joey Jiao in [1], the current kcov implementation may suffer from certain syscalls overflowing the userspace coverage buffer.
According to our measurements, among 24 syzkaller instances running upstream Linux, 5 had a coverage overflow in at least 50% of executed programs. The median percentage of programs with overflows across those 24 instances was 8.8%.
One way to mitigate this problem is to increase the size of the kcov buffer in the userspace application using kcov. But right now syzkaller already uses 4Mb per each of up to 32 threads to store the coverage, and increasing it further would result in reduction in the number of executors on a single machine. Replaying the same program with an increased buffer size in the case of overflow would also lead to fewer executions being possible.
When executing a single system call, excessive coverage usually stems from loops, which write the same PCs into the output buffer repeatedly. Although collecting precise traces may give us some insights into e.g. the number of loop iterations and the branches being taken, the fuzzing engine does not take advantage of these signals, and recording only unique PCs should be just as practical.
Quoted 6 lines
In [1] Joey Jiao suggested using a hash table to deduplicate the coverage signal on the kernel side. While being universally applicable to all types of data collected by kcov, this approach adds another layer of complexity, requiring dynamically growing the map. Another problem is potential hash collisions, which can as well lead to lost coverage. Hash maps are also unavoidably sparse, which potentially requires more memory.
The hashmap probably can compare values for equality to avoid losing coverage, but the real problem is that it allocates and can't work in interrupts, etc.
Quoted 106 lines
The approach proposed in this patch series is to assign a unique (and almost) sequential ID to each of the coverage callbacks in the kernel. Then we carve out a fixed-sized bitmap from the userspace trace buffer, and on every callback invocation we:
- obtain the
callback_ID;
- if bitmap[callback_ID] is set, append the PC to the trace buffer;
- set bitmap[callback_ID] to true.LLVM's -fsanitize-coverage=trace-pc-guard replaces every coverage callback in the kernel with a call to
__sanitizer_cov_trace_pc_guard(&guard_variable), whereguard_variableis a 4-byte global that is unique for the callsite.This allows us to lazily allocate sequential numbers just for the callbacks that have actually been executed, using a lock-free algorithm.
This patch series implements a new config,
CONFIG_KCOV_ENABLE_GUARDS, which utilizes the mentioned LLVM flag for coverage instrumentation. In addition to the existing coverage collection modes, it introducesioctl(KCOV_UNIQUE_ENABLE), which splits the existing kcov buffer into the bitmap and the trace part for a particular fuzzing session, and collects only unique coverage in the trace buffer.To reset the coverage between runs, it is now necessary to set trace[0] to 0 AND clear the entire bitmap. This is still considered feasible, based on the experimental results below.
The current design does not address the deduplication of
KCOV_TRACE_CMPcomparisons; however, the number of kcov overflows during the hints collection process is insignificant compared to the overflows ofKCOV_TRACE_PC.In addition to the mentioned changes, this patch adds support for
R_X86_64_REX_GOTPCRELXto objtool andarch/x86/kernel/module.c. It turned out that Clang leaves such relocations in the linked modules for the__start___sancov_guardsand__stop___sancov_guardssymbols. Because resolving them does not require a .got section, it can be done at module load time.Experimental results.
We've conducted an experiment running syz-testbed [3] on 10 syzkaller instances for 24 hours. Out of those 10 instances, 5 were enabling the
kcov_deduplicateflag from [4], which makes use of theKCOV_UNIQUE_ENABLEioctl, reserving 4096 words (262144 bits) for the bitmap and leaving 520192 words for the trace collection.Below are the average stats from the runs.
kcov_deduplicate=false:
corpus: 52176
coverage: 302658
cover overflows: 225288
comps overflows: 491
exec total: 1417829
max signal: 318894kcov_deduplicate=true:
corpus: 52581
coverage: 304344
cover overflows: 986
comps overflows: 626
exec total: 1484841
max signal: 322455[1] https://lore.kernel.org/linux-arm-kernel/[email protected]/T/
[2] https://clang.llvm.org/docs/SanitizerCoverage.html
[3] https://github.com/google/syzkaller/tree/master/tools/syz-testbed
[4] https://github.com/ramosian-glider/linux/pull/7Alexander Potapenko (7):
kcov: apply clang-format to kcov code
kcov: factor out structkcov_state
kcov: x86: introduceCONFIG_KCOV_ENABLE_GUARDS
kcov: addtraceandtrace_sizetostruct kcov_state
kcov: addioctl(KCOV_UNIQUE_ENABLE)
x86: objtool: add support forR_X86_64_REX_GOTPCRELXmm/kasan: define__asan_before_dynamic_init,__asan_after_dynamic_initDocumentation/dev-tools/kcov.rst | 43 +++ MAINTAINERS | 1 + arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 + arch/x86/kernel/vmlinux.lds.S | 1 + arch/x86/um/asm/elf.h | 1 + include/asm-generic/vmlinux.lds.h | 14 +- include/linux/kcov-state.h | 46 +++ include/linux/kcov.h | 60 ++-- include/linux/sched.h | 16 +- include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 453 +++++++++++++++++++----------- lib/Kconfig.debug | 16 ++ mm/kasan/generic.c | 18 ++ mm/kasan/kasan.h | 2 + scripts/Makefile.kcov | 4 + scripts/module.lds.S | 23 ++ tools/objtool/arch/x86/decode.c | 1 + tools/objtool/check.c | 1 + 19 files changed, 508 insertions(+), 202 deletions(-) create mode 100644 include/linux/kcov-state.h--
2.49.0.604.gff1f9ca942-goog
Quoted 71 lines · Alexander Potapenko
As mentioned by Joey Jiao in [1], the current kcov implementation may suffer from certain syscalls overflowing the userspace coverage buffer.
According to our measurements, among 24 syzkaller instances running upstream Linux, 5 had a coverage overflow in at least 50% of executed programs. The median percentage of programs with overflows across those 24 instances was 8.8%.
One way to mitigate this problem is to increase the size of the kcov buffer in the userspace application using kcov. But right now syzkaller already uses 4Mb per each of up to 32 threads to store the coverage, and increasing it further would result in reduction in the number of executors on a single machine. Replaying the same program with an increased buffer size in the case of overflow would also lead to fewer executions being possible.
When executing a single system call, excessive coverage usually stems from loops, which write the same PCs into the output buffer repeatedly. Although collecting precise traces may give us some insights into e.g. the number of loop iterations and the branches being taken, the fuzzing engine does not take advantage of these signals, and recording only unique PCs should be just as practical.
In [1] Joey Jiao suggested using a hash table to deduplicate the coverage signal on the kernel side. While being universally applicable to all types of data collected by kcov, this approach adds another layer of complexity, requiring dynamically growing the map. Another problem is potential hash collisions, which can as well lead to lost coverage. Hash maps are also unavoidably sparse, which potentially requires more memory.
The approach proposed in this patch series is to assign a unique (and almost) sequential ID to each of the coverage callbacks in the kernel. Then we carve out a fixed-sized bitmap from the userspace trace buffer, and on every callback invocation we:
- obtain the
callback_ID;
- if bitmap[callback_ID] is set, append the PC to the trace buffer;
- set bitmap[callback_ID] to true.LLVM's -fsanitize-coverage=trace-pc-guard replaces every coverage callback in the kernel with a call to
__sanitizer_cov_trace_pc_guard(&guard_variable), whereguard_variableis a 4-byte global that is unique for the callsite.This allows us to lazily allocate sequential numbers just for the callbacks that have actually been executed, using a lock-free algorithm.
This patch series implements a new config,
CONFIG_KCOV_ENABLE_GUARDS, which utilizes the mentioned LLVM flag for coverage instrumentation. In addition to the existing coverage collection modes, it introducesioctl(KCOV_UNIQUE_ENABLE), which splits the existing kcov buffer into the bitmap and the trace part for a particular fuzzing session, and collects only unique coverage in the trace buffer.To reset the coverage between runs, it is now necessary to set trace[0] to 0 AND clear the entire bitmap. This is still considered feasible, based on the experimental results below.
The current design does not address the deduplication of
KCOV_TRACE_CMPcomparisons; however, the number of kcov overflows during the hints collection process is insignificant compared to the overflows ofKCOV_TRACE_PC.In addition to the mentioned changes, this patch adds support for
R_X86_64_REX_GOTPCRELXto objtool andarch/x86/kernel/module.c. It turned out that Clang leaves such relocations in the linked modules for the__start___sancov_guardsand__stop___sancov_guardssymbols. Because resolving them does not require a .got section, it can be done at module load time.Experimental results.
Quoted 7 lines
We've conducted an experiment running syz-testbed [3] on 10 syzkaller instances for 24 hours. Out of those 10 instances, 5 were enabling the
kcov_deduplicateflag from [4], which makes use of theKCOV_UNIQUE_ENABLEioctl, reserving 4096 words (262144 bits) for the bitmap and leaving 520192 words for the trace collection.Below are the average stats from the runs.
Is there test without trace collection? Is bitmap only enough?
Quoted 57 lines
kcov_deduplicate=false:
corpus: 52176
coverage: 302658
cover overflows: 225288
comps overflows: 491
exec total: 1417829
max signal: 318894kcov_deduplicate=true:
corpus: 52581
coverage: 304344
cover overflows: 986
comps overflows: 626
exec total: 1484841
max signal: 322455[1] https://lore.kernel.org/linux-arm-kernel/[email protected]/T/
[2] https://clang.llvm.org/docs/SanitizerCoverage.html
[3] https://github.com/google/syzkaller/tree/master/tools/syz-testbed
[4] https://github.com/ramosian-glider/linux/pull/7Alexander Potapenko (7):
kcov: apply clang-format to kcov code
kcov: factor out structkcov_state
kcov: x86: introduceCONFIG_KCOV_ENABLE_GUARDS
kcov: addtraceandtrace_sizetostruct kcov_state
kcov: addioctl(KCOV_UNIQUE_ENABLE)
x86: objtool: add support forR_X86_64_REX_GOTPCRELXmm/kasan: define__asan_before_dynamic_init,__asan_after_dynamic_initDocumentation/dev-tools/kcov.rst | 43 +++ MAINTAINERS | 1 + arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 + arch/x86/kernel/vmlinux.lds.S | 1 + arch/x86/um/asm/elf.h | 1 + include/asm-generic/vmlinux.lds.h | 14 +- include/linux/kcov-state.h | 46 +++ include/linux/kcov.h | 60 ++-- include/linux/sched.h | 16 +- include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 453 +++++++++++++++++++----------- lib/Kconfig.debug | 16 ++ mm/kasan/generic.c | 18 ++ mm/kasan/kasan.h | 2 + scripts/Makefile.kcov | 4 + scripts/module.lds.S | 23 ++ tools/objtool/arch/x86/decode.c | 1 + tools/objtool/check.c | 1 + 19 files changed, 508 insertions(+), 202 deletions(-) create mode 100644 include/linux/kcov-state.hSignature · 1 line
2.49.0.604.gff1f9ca942-goog
Alexander Potapenko
reviewerQuoted 2 lines
Quoted 1 line
Below are the average stats from the runs.
Is there test without trace collection? Is bitmap only enough?
If we bump the bitmap size to ~16K, it should be enough to keep all the fuzzing results from a single run.
We haven't experimented with it much though, because syzkaller currently processes coverage as an array of PCs, not a bitmap. Changing this would require a major rework of syzkaller, given that the positions in the bitmap may differ between different machines, so we'll need to maintain a reverse mapping between bits and PCs in every executor.
Such a mapping could be implemented on the kernel side on top of the proposed patches, once someone proves a need for that.
Alexander Potapenko
reviewerQuoted 24 lines
We've conducted an experiment running syz-testbed [3] on 10 syzkaller instances for 24 hours. Out of those 10 instances, 5 were enabling the
kcov_deduplicateflag from [4], which makes use of theKCOV_UNIQUE_ENABLEioctl, reserving 4096 words (262144 bits) for the bitmap and leaving 520192 words for the trace collection.Below are the average stats from the runs.
kcov_deduplicate=false:
corpus: 52176
coverage: 302658
cover overflows: 225288
comps overflows: 491
exec total: 1417829
max signal: 318894kcov_deduplicate=true:
corpus: 52581
coverage: 304344
cover overflows: 986
comps overflows: 626
exec total: 1484841
max signal: 322455
Quoted 4 lines
[1] https://lore.kernel.org/linux-arm-kernel/[email protected]/T/
[2] https://clang.llvm.org/docs/SanitizerCoverage.html
[3] https://github.com/google/syzkaller/tree/master/tools/syz-testbed
[4] https://github.com/ramosian-glider/linux/pull/7
Ouch, this should have been:
[4] https://github.com/ramosian-glider/syzkaller/tree/kcov_dedup-new
I will update the link in v2.
Quoted 33 lines
Alexander Potapenko (7):
kcov: apply clang-format to kcov code
kcov: factor out structkcov_state
kcov: x86: introduceCONFIG_KCOV_ENABLE_GUARDS
kcov: addtraceandtrace_sizetostruct kcov_state
kcov: addioctl(KCOV_UNIQUE_ENABLE)
x86: objtool: add support forR_X86_64_REX_GOTPCRELXmm/kasan: define__asan_before_dynamic_init,__asan_after_dynamic_initDocumentation/dev-tools/kcov.rst | 43 +++ MAINTAINERS | 1 + arch/x86/include/asm/elf.h | 1 + arch/x86/kernel/module.c | 8 + arch/x86/kernel/vmlinux.lds.S | 1 + arch/x86/um/asm/elf.h | 1 + include/asm-generic/vmlinux.lds.h | 14 +- include/linux/kcov-state.h | 46 +++ include/linux/kcov.h | 60 ++-- include/linux/sched.h | 16 +- include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 453 +++++++++++++++++++----------- lib/Kconfig.debug | 16 ++ mm/kasan/generic.c | 18 ++ mm/kasan/kasan.h | 2 + scripts/Makefile.kcov | 4 + scripts/module.lds.S | 23 ++ tools/objtool/arch/x86/decode.c | 1 + tools/objtool/check.c | 1 + 19 files changed, 508 insertions(+), 202 deletions(-) create mode 100644 include/linux/kcov-state.h
Quoted 3 lines
--
2.49.0.604.gff1f9ca942-goog
--
Alexander Potapenko
Software Engineer
Google Germany GmbH
Erika-Mann-Straße, 33
80636 München
Geschäftsführer: Paul Manicle, Liana Sebastian
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg