Message-ID: <aBGJQF8aMfWmz7RI@hu-jiangenj-sha.qualcomm.com>
Date: Wed, 30 Apr 2025 10:21:52 +0800
From: Joey Jiao <quic_jiangenj@...cinc.com>
To: Alexander Potapenko <glider@...gle.com>
CC: <linux-kernel@...r.kernel.org>, <kasan-dev@...glegroups.com>,
        Aleksandr
 Nogikh <nogikh@...gle.com>,
        Andrey Konovalov <andreyknvl@...il.com>,
        Borislav
 Petkov <bp@...en8.de>,
        Dave Hansen <dave.hansen@...ux.intel.com>,
        Dmitry
 Vyukov <dvyukov@...gle.com>, Ingo Molnar <mingo@...hat.com>,
        Josh Poimboeuf
	<jpoimboe@...nel.org>, Marco Elver <elver@...gle.com>,
        Peter Zijlstra
	<peterz@...radead.org>,
        Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [PATCH 5/7] kcov: add ioctl(KCOV_UNIQUE_ENABLE)

On Wed, Apr 16, 2025 at 10:54:43AM +0200, Alexander Potapenko wrote:
> ioctl(KCOV_UNIQUE_ENABLE) enables collection of deduplicated coverage
> in the presence of CONFIG_KCOV_ENABLE_GUARDS.
> 
> The buffer shared with the userspace is divided in two parts, one holding
> a bitmap, and the other one being the trace. The single parameter of
> ioctl(KCOV_UNIQUE_ENABLE) determines the number of words used for the
> bitmap.
> 
> Each __sanitizer_cov_trace_pc_guard() instrumentation hook receives a
> pointer to a unique guard variable. Upon the first call of each hook,
> the guard variable is initialized with a unique integer, which is used to
> map those hooks to bits in the bitmap. In the new coverage collection mode,
> the kernel first checks whether the bit corresponding to a particular hook
> is set, and then, if it is not, the PC is written into the trace buffer,
> and the bit is set.
> 
> 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.
> 
> Signed-off-by: Alexander Potapenko <glider@...gle.com>
> ---
>  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(-)
> 
> diff --git a/Documentation/dev-tools/kcov.rst b/Documentation/dev-tools/kcov.rst
> index 6611434e2dd24..271260642d1a6 100644
> --- a/Documentation/dev-tools/kcov.rst
> +++ b/Documentation/dev-tools/kcov.rst
> @@ -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)
in kcov.h it was defined was _IOR, but _IOW here,
#define KCOV_UNIQUE_ENABLE             _IOR('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
>  ------------------------------
>  
> diff --git a/include/linux/kcov-state.h b/include/linux/kcov-state.h
> index 6e576173fd442..26e275fe90684 100644
> --- a/include/linux/kcov-state.h
> +++ b/include/linux/kcov-state.h
> @@ -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.
> diff --git a/include/linux/kcov.h b/include/linux/kcov.h
> index 7ec2669362fd1..41eebcd3ab335 100644
> --- a/include/linux/kcov.h
> +++ b/include/linux/kcov.h
> @@ -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)
> diff --git a/include/uapi/linux/kcov.h b/include/uapi/linux/kcov.h
> index ed95dba9fa37e..fe1695ddf8a06 100644
> --- a/include/uapi/linux/kcov.h
> +++ b/include/uapi/linux/kcov.h
> @@ -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 {
>  	/*
> diff --git a/kernel/kcov.c b/kernel/kcov.c
> index 7b726fd761c1b..dea25c8a53b52 100644
> --- a/kernel/kcov.c
> +++ b/kernel/kcov.c
> @@ -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;
> -- 
> 2.49.0.604.gff1f9ca942-goog
> 

Powered by blists - more mailing lists