1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (C) 2018 The FreeBSD Foundation. All rights reserved.
5 * Copyright (C) 2018, 2019 Andrew Turner
6 *
7 * This software was developed by Mitchell Horne under sponsorship of
8 * the FreeBSD Foundation.
9 *
10 * This software was developed by SRI International and the University of
11 * Cambridge Computer Laboratory under DARPA/AFRL contract FA8750-10-C-0237
12 * ("CTSRD"), as part of the DARPA CRASH research programme.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions
16 * are met:
17 * 1. Redistributions of source code must retain the above copyright
18 *    notice, this list of conditions and the following disclaimer.
19 * 2. Redistributions in binary form must reproduce the above copyright
20 *    notice, this list of conditions and the following disclaimer in the
21 *    documentation and/or other materials provided with the distribution.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36/* Interceptors are required for KMSAN. */
37#if defined(KASAN) || defined(KCSAN)
38#define	SAN_RUNTIME
39#endif
40
41#include <sys/param.h>
42#include <sys/systm.h>
43#include <sys/conf.h>
44#include <sys/eventhandler.h>
45#include <sys/kcov.h>
46#include <sys/kernel.h>
47#include <sys/limits.h>
48#include <sys/lock.h>
49#include <sys/malloc.h>
50#include <sys/mman.h>
51#include <sys/mutex.h>
52#include <sys/proc.h>
53#include <sys/rwlock.h>
54#include <sys/sysctl.h>
55
56#include <vm/vm.h>
57#include <vm/pmap.h>
58#include <vm/vm_extern.h>
59#include <vm/vm_object.h>
60#include <vm/vm_page.h>
61#include <vm/vm_pager.h>
62#include <vm/vm_param.h>
63
64MALLOC_DEFINE(M_KCOV_INFO, "kcovinfo", "KCOV info type");
65
66#define	KCOV_ELEMENT_SIZE	sizeof(uint64_t)
67
68/*
69 * To know what the code can safely perform at any point in time we use a
70 * state machine. In the normal case the state transitions are:
71 *
72 * OPEN -> READY -> RUNNING -> DYING
73 *  |       | ^        |        ^ ^
74 *  |       | +--------+        | |
75 *  |       +-------------------+ |
76 *  +-----------------------------+
77 *
78 * The states are:
79 *  OPEN:   The kcov fd has been opened, but no buffer is available to store
80 *          coverage data.
81 *  READY:  The buffer to store coverage data has been allocated. Userspace
82 *          can set this by using ioctl(fd, KIOSETBUFSIZE, entries);. When
83 *          this has been set the buffer can be written to by the kernel,
84 *          and mmaped by userspace.
85 * RUNNING: The coverage probes are able to store coverage data in the buffer.
86 *          This is entered with ioctl(fd, KIOENABLE, mode);. The READY state
87 *          can be exited by ioctl(fd, KIODISABLE); or exiting the thread to
88 *          return to the READY state to allow tracing to be reused, or by
89 *          closing the kcov fd to enter the DYING state.
90 * DYING:   The fd has been closed. All states can enter into this state when
91 *          userspace closes the kcov fd.
92 *
93 * We need to be careful when moving into and out of the RUNNING state. As
94 * an interrupt may happen while this is happening the ordering of memory
95 * operations is important so struct kcov_info is valid for the tracing
96 * functions.
97 *
98 * When moving into the RUNNING state prior stores to struct kcov_info need
99 * to be observed before the state is set. This allows for interrupts that
100 * may call into one of the coverage functions to fire at any point while
101 * being enabled and see a consistent struct kcov_info.
102 *
103 * When moving out of the RUNNING state any later stores to struct kcov_info
104 * need to be observed after the state is set. As with entering this is to
105 * present a consistent struct kcov_info to interrupts.
106 */
107typedef enum {
108	KCOV_STATE_INVALID,
109	KCOV_STATE_OPEN,	/* The device is open, but with no buffer */
110	KCOV_STATE_READY,	/* The buffer has been allocated */
111	KCOV_STATE_RUNNING,	/* Recording trace data */
112	KCOV_STATE_DYING,	/* The fd was closed */
113} kcov_state_t;
114
115/*
116 * (l) Set while holding the kcov_lock mutex and not in the RUNNING state.
117 * (o) Only set once while in the OPEN state. Cleaned up while in the DYING
118 *     state, and with no thread associated with the struct kcov_info.
119 * (s) Set atomically to enter or exit the RUNNING state, non-atomically
120 *     otherwise. See above for a description of the other constraints while
121 *     moving into or out of the RUNNING state.
122 */
123struct kcov_info {
124	struct thread	*thread;	/* (l) */
125	vm_object_t	bufobj;		/* (o) */
126	vm_offset_t	kvaddr;		/* (o) */
127	size_t		entries;	/* (o) */
128	size_t		bufsize;	/* (o) */
129	kcov_state_t	state;		/* (s) */
130	int		mode;		/* (l) */
131};
132
133/* Prototypes */
134static d_open_t		kcov_open;
135static d_close_t	kcov_close;
136static d_mmap_single_t	kcov_mmap_single;
137static d_ioctl_t	kcov_ioctl;
138
139static int  kcov_alloc(struct kcov_info *info, size_t entries);
140static void kcov_free(struct kcov_info *info);
141static void kcov_init(const void *unused);
142
143static struct cdevsw kcov_cdevsw = {
144	.d_version =	D_VERSION,
145	.d_open =	kcov_open,
146	.d_close =	kcov_close,
147	.d_mmap_single = kcov_mmap_single,
148	.d_ioctl =	kcov_ioctl,
149	.d_name =	"kcov",
150};
151
152SYSCTL_NODE(_kern, OID_AUTO, kcov, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
153    "Kernel coverage");
154
155static u_int kcov_max_entries = KCOV_MAXENTRIES;
156SYSCTL_UINT(_kern_kcov, OID_AUTO, max_entries, CTLFLAG_RW,
157    &kcov_max_entries, 0,
158    "Maximum number of entries in the kcov buffer");
159
160static struct mtx kcov_lock;
161static int active_count;
162
163static struct kcov_info * __nosanitizeaddress __nosanitizememory
164get_kinfo(struct thread *td)
165{
166	struct kcov_info *info;
167
168	/* We might have a NULL thread when releasing the secondary CPUs */
169	if (td == NULL)
170		return (NULL);
171
172	/*
173	 * We are in an interrupt, stop tracing as it is not explicitly
174	 * part of a syscall.
175	 */
176	if (td->td_intr_nesting_level > 0 || td->td_intr_frame != NULL)
177		return (NULL);
178
179	/*
180	 * If info is NULL or the state is not running we are not tracing.
181	 */
182	info = td->td_kcov_info;
183	if (info == NULL ||
184	    atomic_load_acq_int(&info->state) != KCOV_STATE_RUNNING)
185		return (NULL);
186
187	return (info);
188}
189
190static void __nosanitizeaddress __nosanitizememory
191trace_pc(uintptr_t ret)
192{
193	struct thread *td;
194	struct kcov_info *info;
195	uint64_t *buf, index;
196
197	td = curthread;
198	info = get_kinfo(td);
199	if (info == NULL)
200		return;
201
202	/*
203	 * Check we are in the PC-trace mode.
204	 */
205	if (info->mode != KCOV_MODE_TRACE_PC)
206		return;
207
208	KASSERT(info->kvaddr != 0, ("%s: NULL buf while running", __func__));
209
210	buf = (uint64_t *)info->kvaddr;
211
212	/* The first entry of the buffer holds the index */
213	index = buf[0];
214	if (index + 2 > info->entries)
215		return;
216
217	buf[index + 1] = ret;
218	buf[0] = index + 1;
219}
220
221static bool __nosanitizeaddress __nosanitizememory
222trace_cmp(uint64_t type, uint64_t arg1, uint64_t arg2, uint64_t ret)
223{
224	struct thread *td;
225	struct kcov_info *info;
226	uint64_t *buf, index;
227
228	td = curthread;
229	info = get_kinfo(td);
230	if (info == NULL)
231		return (false);
232
233	/*
234	 * Check we are in the comparison-trace mode.
235	 */
236	if (info->mode != KCOV_MODE_TRACE_CMP)
237		return (false);
238
239	KASSERT(info->kvaddr != 0, ("%s: NULL buf while running", __func__));
240
241	buf = (uint64_t *)info->kvaddr;
242
243	/* The first entry of the buffer holds the index */
244	index = buf[0];
245
246	/* Check we have space to store all elements */
247	if (index * 4 + 4 + 1 > info->entries)
248		return (false);
249
250	while (1) {
251		buf[index * 4 + 1] = type;
252		buf[index * 4 + 2] = arg1;
253		buf[index * 4 + 3] = arg2;
254		buf[index * 4 + 4] = ret;
255
256		if (atomic_cmpset_64(&buf[0], index, index + 1))
257			break;
258		buf[0] = index;
259	}
260
261	return (true);
262}
263
264/*
265 * The fd is being closed, cleanup everything we can.
266 */
267static void
268kcov_mmap_cleanup(void *arg)
269{
270	struct kcov_info *info = arg;
271	struct thread *thread;
272
273	mtx_lock_spin(&kcov_lock);
274	/*
275	 * Move to KCOV_STATE_DYING to stop adding new entries.
276	 *
277	 * If the thread is running we need to wait until thread exit to
278	 * clean up as it may currently be adding a new entry. If this is
279	 * the case being in KCOV_STATE_DYING will signal that the buffer
280	 * needs to be cleaned up.
281	 */
282	atomic_store_int(&info->state, KCOV_STATE_DYING);
283	atomic_thread_fence_seq_cst();
284	thread = info->thread;
285	mtx_unlock_spin(&kcov_lock);
286
287	if (thread != NULL)
288		return;
289
290	/*
291	 * We can safely clean up the info struct as it is in the
292	 * KCOV_STATE_DYING state with no thread associated.
293	 *
294	 * The KCOV_STATE_DYING stops new threads from using it.
295	 * The lack of a thread means nothing is currently using the buffers.
296	 */
297	kcov_free(info);
298}
299
300static int
301kcov_open(struct cdev *dev, int oflags, int devtype, struct thread *td)
302{
303	struct kcov_info *info;
304	int error;
305
306	info = malloc(sizeof(struct kcov_info), M_KCOV_INFO, M_ZERO | M_WAITOK);
307	info->state = KCOV_STATE_OPEN;
308	info->thread = NULL;
309	info->mode = -1;
310
311	if ((error = devfs_set_cdevpriv(info, kcov_mmap_cleanup)) != 0)
312		kcov_mmap_cleanup(info);
313
314	return (error);
315}
316
317static int
318kcov_close(struct cdev *dev, int fflag, int devtype, struct thread *td)
319{
320	struct kcov_info *info;
321	int error;
322
323	if ((error = devfs_get_cdevpriv((void **)&info)) != 0)
324		return (error);
325
326	KASSERT(info != NULL, ("kcov_close with no kcov_info structure"));
327
328	/* Trying to close, but haven't disabled */
329	if (info->state == KCOV_STATE_RUNNING)
330		return (EBUSY);
331
332	return (0);
333}
334
335static int
336kcov_mmap_single(struct cdev *dev, vm_ooffset_t *offset, vm_size_t size,
337    struct vm_object **object, int nprot)
338{
339	struct kcov_info *info;
340	int error;
341
342	if ((nprot & (PROT_EXEC | PROT_READ | PROT_WRITE)) !=
343	    (PROT_READ | PROT_WRITE))
344		return (EINVAL);
345
346	if ((error = devfs_get_cdevpriv((void **)&info)) != 0)
347		return (error);
348
349	if (info->kvaddr == 0 || size / KCOV_ELEMENT_SIZE != info->entries)
350		return (EINVAL);
351
352	vm_object_reference(info->bufobj);
353	*offset = 0;
354	*object = info->bufobj;
355	return (0);
356}
357
358static int
359kcov_alloc(struct kcov_info *info, size_t entries)
360{
361	size_t n, pages;
362	vm_page_t m;
363
364	KASSERT(info->kvaddr == 0, ("kcov_alloc: Already have a buffer"));
365	KASSERT(info->state == KCOV_STATE_OPEN,
366	    ("kcov_alloc: Not in open state (%x)", info->state));
367
368	if (entries < 2 || entries > kcov_max_entries)
369		return (EINVAL);
370
371	/* Align to page size so mmap can't access other kernel memory */
372	info->bufsize = roundup2(entries * KCOV_ELEMENT_SIZE, PAGE_SIZE);
373	pages = info->bufsize / PAGE_SIZE;
374
375	if ((info->kvaddr = kva_alloc(info->bufsize)) == 0)
376		return (ENOMEM);
377
378	info->bufobj = vm_pager_allocate(OBJT_PHYS, 0, info->bufsize,
379	    PROT_READ | PROT_WRITE, 0, curthread->td_ucred);
380
381	VM_OBJECT_WLOCK(info->bufobj);
382	for (n = 0; n < pages; n++) {
383		m = vm_page_grab(info->bufobj, n,
384		    VM_ALLOC_ZERO | VM_ALLOC_WIRED);
385		vm_page_valid(m);
386		vm_page_xunbusy(m);
387		pmap_qenter(info->kvaddr + n * PAGE_SIZE, &m, 1);
388	}
389	VM_OBJECT_WUNLOCK(info->bufobj);
390
391	info->entries = entries;
392
393	return (0);
394}
395
396static void
397kcov_free(struct kcov_info *info)
398{
399	vm_page_t m;
400	size_t i;
401
402	if (info->kvaddr != 0) {
403		pmap_qremove(info->kvaddr, info->bufsize / PAGE_SIZE);
404		kva_free(info->kvaddr, info->bufsize);
405	}
406	if (info->bufobj != NULL) {
407		VM_OBJECT_WLOCK(info->bufobj);
408		m = vm_page_lookup(info->bufobj, 0);
409		for (i = 0; i < info->bufsize / PAGE_SIZE; i++) {
410			vm_page_unwire_noq(m);
411			m = vm_page_next(m);
412		}
413		VM_OBJECT_WUNLOCK(info->bufobj);
414		vm_object_deallocate(info->bufobj);
415	}
416	free(info, M_KCOV_INFO);
417}
418
419static int
420kcov_ioctl(struct cdev *dev, u_long cmd, caddr_t data, int fflag __unused,
421    struct thread *td)
422{
423	struct kcov_info *info;
424	int mode, error;
425
426	if ((error = devfs_get_cdevpriv((void **)&info)) != 0)
427		return (error);
428
429	if (cmd == KIOSETBUFSIZE) {
430		/*
431		 * Set the size of the coverage buffer. Should be called
432		 * before enabling coverage collection for that thread.
433		 */
434		if (info->state != KCOV_STATE_OPEN) {
435			return (EBUSY);
436		}
437		error = kcov_alloc(info, *(u_int *)data);
438		if (error == 0)
439			info->state = KCOV_STATE_READY;
440		return (error);
441	}
442
443	mtx_lock_spin(&kcov_lock);
444	switch (cmd) {
445	case KIOENABLE:
446		if (info->state != KCOV_STATE_READY) {
447			error = EBUSY;
448			break;
449		}
450		if (td->td_kcov_info != NULL) {
451			error = EINVAL;
452			break;
453		}
454		mode = *(int *)data;
455		if (mode != KCOV_MODE_TRACE_PC && mode != KCOV_MODE_TRACE_CMP) {
456			error = EINVAL;
457			break;
458		}
459
460		/* Lets hope nobody opens this 2 billion times */
461		KASSERT(active_count < INT_MAX,
462		    ("%s: Open too many times", __func__));
463		active_count++;
464		if (active_count == 1) {
465			cov_register_pc(&trace_pc);
466			cov_register_cmp(&trace_cmp);
467		}
468
469		KASSERT(info->thread == NULL,
470		    ("Enabling kcov when already enabled"));
471		info->thread = td;
472		info->mode = mode;
473		/*
474		 * Ensure the mode has been set before starting coverage
475		 * tracing.
476		 */
477		atomic_store_rel_int(&info->state, KCOV_STATE_RUNNING);
478		td->td_kcov_info = info;
479		break;
480	case KIODISABLE:
481		/* Only the currently enabled thread may disable itself */
482		if (info->state != KCOV_STATE_RUNNING ||
483		    info != td->td_kcov_info) {
484			error = EINVAL;
485			break;
486		}
487		KASSERT(active_count > 0, ("%s: Open count is zero", __func__));
488		active_count--;
489		if (active_count == 0) {
490			cov_unregister_pc();
491			cov_unregister_cmp();
492		}
493
494		td->td_kcov_info = NULL;
495		atomic_store_int(&info->state, KCOV_STATE_READY);
496		/*
497		 * Ensure we have exited the READY state before clearing the
498		 * rest of the info struct.
499		 */
500		atomic_thread_fence_rel();
501		info->mode = -1;
502		info->thread = NULL;
503		break;
504	default:
505		error = EINVAL;
506		break;
507	}
508	mtx_unlock_spin(&kcov_lock);
509
510	return (error);
511}
512
513static void
514kcov_thread_dtor(void *arg __unused, struct thread *td)
515{
516	struct kcov_info *info;
517
518	info = td->td_kcov_info;
519	if (info == NULL)
520		return;
521
522	mtx_lock_spin(&kcov_lock);
523	KASSERT(active_count > 0, ("%s: Open count is zero", __func__));
524	active_count--;
525	if (active_count == 0) {
526		cov_unregister_pc();
527		cov_unregister_cmp();
528	}
529	td->td_kcov_info = NULL;
530	if (info->state != KCOV_STATE_DYING) {
531		/*
532		 * The kcov file is still open. Mark it as unused and
533		 * wait for it to be closed before cleaning up.
534		 */
535		atomic_store_int(&info->state, KCOV_STATE_READY);
536		atomic_thread_fence_seq_cst();
537		/* This info struct is unused */
538		info->thread = NULL;
539		mtx_unlock_spin(&kcov_lock);
540		return;
541	}
542	mtx_unlock_spin(&kcov_lock);
543
544	/*
545	 * We can safely clean up the info struct as it is in the
546	 * KCOV_STATE_DYING state where the info struct is associated with
547	 * the current thread that's about to exit.
548	 *
549	 * The KCOV_STATE_DYING stops new threads from using it.
550	 * It also stops the current thread from trying to use the info struct.
551	 */
552	kcov_free(info);
553}
554
555static void
556kcov_init(const void *unused)
557{
558	struct make_dev_args args;
559	struct cdev *dev;
560
561	mtx_init(&kcov_lock, "kcov lock", NULL, MTX_SPIN);
562
563	make_dev_args_init(&args);
564	args.mda_devsw = &kcov_cdevsw;
565	args.mda_uid = UID_ROOT;
566	args.mda_gid = GID_WHEEL;
567	args.mda_mode = 0600;
568	if (make_dev_s(&args, &dev, "kcov") != 0) {
569		printf("%s", "Failed to create kcov device");
570		return;
571	}
572
573	EVENTHANDLER_REGISTER(thread_dtor, kcov_thread_dtor, NULL,
574	    EVENTHANDLER_PRI_ANY);
575}
576
577SYSINIT(kcovdev, SI_SUB_LAST, SI_ORDER_ANY, kcov_init, NULL);
578