kcov

10 files changed, 550 insertions, 2 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index 9c932d6f..814e8182 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -72,5 +72,5 @@ libintel_tools_la_LIBADD = \
 	$(LIBUDEV_LIBS) \
 	$(PIXMAN_LIBS) \
 	$(GLIB_LIBS) \
-	-lm
+	-lz -lm
 
diff --git a/lib/Makefile.sources b/lib/Makefile.sources
index 90ff6468..038544cc 100644
--- a/lib/Makefile.sources
+++ b/lib/Makefile.sources
@@ -18,6 +18,8 @@ lib_source_list =	 	\
 	igt_gt.h		\
 	igt_gvt.c		\
 	igt_gvt.h		\
+	igt_kcov.c		\
+	igt_kcov.h		\
 	igt_primes.c		\
 	igt_primes.h		\
 	igt_rand.c		\
diff --git a/lib/igt_core.c b/lib/igt_core.c
index 2509bc64..e1cab46f 100644
--- a/lib/igt_core.c
+++ b/lib/igt_core.c
@@ -64,6 +64,7 @@
 #include "intel_io.h"
 #include "igt_debugfs.h"
 #include "igt_ftrace.h"
+#include "igt_kcov.h"
 #include "version.h"
 #include "config.h"
 
@@ -287,6 +288,8 @@ enum {
 static int igt_exitcode = IGT_EXIT_SUCCESS;
 static const char *command_str;
 
+static struct igt_kcov kcov = { .fd = -1 };
+
 static char* igt_log_domain_filter;
 static struct {
 	char *entries[256];
@@ -853,6 +856,8 @@ out:
 		exit(ret == -1 ? 0 : IGT_EXIT_INVALID);
 
 	if (!list_subtests) {
+		const char *env;
+
 		kick_fbcon(false);
 		kmsg(KERN_INFO "[IGT] %s: executing\n", command_str);
 		print_version();
@@ -860,6 +865,10 @@ out:
 		oom_adjust_for_doom();
 		low_mem_killer_disable(true);
 
+		env = getenv("IGT_KCOV");
+		if (env)
+			igt_kcov_open(&kcov);
+
 		igt_ftrace_open();
 	}
 
@@ -987,6 +996,9 @@ bool __igt_run_subtest(const char *subtest_name)
 
 	_igt_log_buffer_reset();
 
+	igt_kcov_reset(&kcov);
+	igt_kcov_enable(&kcov);
+
 	gettime(&subtest_time);
 	return (in_subtest = subtest_name);
 }
@@ -1032,6 +1044,7 @@ static void exit_subtest(const char *result)
 {
 	struct timespec now;
 
+	igt_kcov_disable(&kcov);
 	gettime(&now);
 	printf("%sSubtest %s: %s (%.3fs)%s\n",
 	       (!__igt_plain_output) ? "\x1b[1m" : "",
@@ -1039,6 +1052,22 @@ static void exit_subtest(const char *result)
 	       (!__igt_plain_output) ? "\x1b[0m" : "");
 	fflush(stdout);
 
+	if (strcmp(result, "SUCCESS") == 0) {
+		const char *env = getenv("IGT_KCOV");
+		if (env) {
+			FILE *out = fopen(env, "a");
+			if (out) {
+				char *str;
+
+				str = igt_kcov_to_string(&kcov);
+				fprintf(out, "%s: %s\n", in_subtest, str);
+				free(str);
+
+				fclose(out);
+			}
+		}
+	}
+
 	in_subtest = NULL;
 	siglongjmp(igt_subtest_jmpbuf, 1);
 }
diff --git a/lib/igt_kcov.c b/lib/igt_kcov.c
new file mode 100644
index 00000000..d02fe11d
--- /dev/null
+++ b/lib/igt_kcov.c
@@ -0,0 +1,300 @@
+#include <sys/ioctl.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+
+#include <errno.h>
+#include <error.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <unistd.h>
+#include <math.h>
+
+#include <linux/types.h>
+
+#include <zlib.h>
+
+#include "igt_kcov.h"
+
+#define KCOV_INIT_TRACE                 _IOR('c', 1, unsigned long)
+#define KCOV_INIT_TABLE                 _IOR('c', 2, unsigned long)
+#define KCOV_ENABLE                     _IO('c', 100)
+#define KCOV_DISABLE                    _IO('c', 101)
+
+#define SZ (1 << 15)
+
+int igt_kcov_open(struct igt_kcov *kc)
+{
+	kc->fd = open("/sys/kernel/debug/kcov", O_RDWR);
+	if (kc->fd < 0)
+		return kc->fd;
+
+	kc->sz = SZ;
+	if (ioctl(kc->fd, KCOV_INIT_TABLE, kc->sz))
+		return -errno;
+
+	kc->tbl = mmap(NULL, kc->sz * sizeof(unsigned long),
+		       PROT_WRITE, MAP_SHARED, kc->fd, 0);
+	if (kc->tbl == MAP_FAILED) {
+		int err = -errno;
+		close(kc->fd);
+		return err;
+	}
+
+	return 0;
+}
+
+void igt_kcov_reset(struct igt_kcov *kc)
+{
+	if (kc->fd < 0)
+		return;
+
+	memset(kc->tbl, 0, kc->sz * sizeof(unsigned long));
+}
+
+bool igt_kcov_enable(struct igt_kcov *kc)
+{
+	if (kc->fd < 0)
+		return false;
+
+	return ioctl(kc->fd, KCOV_ENABLE, 0) == 0;
+}
+
+bool igt_kcov_disable(struct igt_kcov *kc)
+{
+	if (kc->fd < 0)
+		return false;
+
+	return ioctl(kc->fd, KCOV_DISABLE, 0) == 0;
+}
+
+bool igt_kcov_merge(struct igt_kcov *out, const struct igt_kcov *m)
+{
+	unsigned long *a, *b;
+
+	if (out == m)
+		return true;
+
+	if (out->sz != m->sz)
+		return false;
+
+	a = out->tbl;
+	b = m->tbl;
+	for (unsigned int i = 0; i < out->sz; i++)
+		a[i] += b[i];
+
+	return true;
+}
+
+double igt_kcov_similarity(const struct igt_kcov *ka, const struct igt_kcov *kb)
+{
+	unsigned long *a, *b;
+	__uint128_t sab, saa, sbb;
+
+	if (ka == kb)
+		return 1;
+
+	if (ka->sz != kb->sz)
+		return 0;
+
+	if (ka->sz == 0)
+		return 0;
+
+	a = ka->tbl;
+	b = kb->tbl;
+	sab = 0;
+	saa = 0;
+	sbb = 0;
+
+	for (unsigned int i = 0; i < ka->sz; i++) {
+		sab += (__uint128_t)a[i] * b[i];
+		saa += (__uint128_t)a[i] * a[i];
+		sbb += (__uint128_t)b[i] * b[i];
+	}
+
+	return sab / (sqrtl(saa) * sqrtl(sbb));
+}
+
+static bool ascii85_encode(uint32_t in, char *out)
+{
+	int i;
+
+	if (in == 0)
+		return false;
+
+	for (i = 5; i--; ) {
+		out[i] = '!' + in % 85;
+		in /= 85;
+	}
+
+	return true;
+}
+
+char *igt_kcov_to_string(const struct igt_kcov *kc)
+{
+	z_stream zs;
+	uint32_t *p;
+	void *out;
+	char *str, *s;
+	int sz;
+
+	if (!kc->tbl)
+		return NULL;
+
+	sz = SZ * sizeof(long) * 3 /2;
+	out = malloc(sz);
+	if (!out)
+		return NULL;
+
+	memset(&zs, 0, sizeof(zs));
+	if (deflateInit(&zs, 9)) {
+		free(out);
+		return NULL;
+	}
+
+	zs.next_in = kc->tbl;
+	zs.avail_in = kc->sz * sizeof(unsigned long);
+	zs.total_in = 0;
+	zs.avail_out = sz;
+	zs.total_out = 0;
+	zs.next_out = out;
+
+	deflate(&zs, Z_FINISH);
+	deflateEnd(&zs);
+
+	if (zs.total_out & 3)
+		memset((char *)out + zs.total_out, 0, 4 - (zs.total_out & 3));
+	zs.total_out = (zs.total_out + 3)/4;
+
+	str = malloc(zs.total_out * 5 + 1);
+	if (!str) {
+		free(out);
+		return NULL;
+	}
+
+	p = out;
+	s = str;
+	for (int i = 0; i < zs.total_out; i++) {
+		if (ascii85_encode(*p++, s))
+			s += 5;
+		else
+			*s++ = 'z';
+	}
+	*s++ = '\0';
+	free(out);
+
+	return str;
+}
+
+static unsigned long zlib_inflate(void *in, unsigned long len, void **ptr)
+{
+	struct z_stream_s zstream;
+	unsigned long sz;
+	void *out;
+
+	memset(&zstream, 0, sizeof(zstream));
+
+	zstream.next_in = in;
+	zstream.avail_in = len;
+
+	if (inflateInit(&zstream) != Z_OK)
+		return 0;
+
+	sz = SZ * sizeof(unsigned long); /* approximate obj size */
+	out = malloc(sz);
+	zstream.next_out = out;
+	zstream.avail_out = sz;
+
+	do {
+		switch (inflate(&zstream, Z_SYNC_FLUSH)) {
+			case Z_STREAM_END:
+				goto end;
+			case Z_OK:
+				break;
+			default:
+				inflateEnd(&zstream);
+				return 0;
+		}
+
+		if (zstream.avail_out)
+			break;
+
+		out = realloc(out, 2*zstream.total_out);
+		if (out == NULL) {
+			inflateEnd(&zstream);
+			return 0;
+		}
+
+		zstream.next_out = (unsigned char *)out + zstream.total_out;
+		zstream.avail_out = zstream.total_out;
+	} while (1);
+end:
+	inflateEnd(&zstream);
+	*ptr = out;
+	return zstream.total_out / sizeof(unsigned long);
+}
+
+static unsigned long ascii85_decode(const char *in, void **ptr)
+{
+	unsigned long size = SZ * sizeof(unsigned long) / sizeof(uint32_t);
+	unsigned long len = 0;
+	uint32_t *out;
+
+	out = malloc(sizeof(uint32_t)*size);
+	if (out == NULL)
+		return 0;
+
+	while (*in >= '!' && *in <= 'z') {
+		uint32_t v = 0;
+
+		if (len == size) {
+			size *= 2;
+			out = realloc(out, sizeof(uint32_t)*size);
+			if (out == NULL)
+				return 0;
+		}
+
+		if (*in == 'z') {
+			in++;
+		} else {
+			v += in[0] - 33; v *= 85;
+			v += in[1] - 33; v *= 85;
+			v += in[2] - 33; v *= 85;
+			v += in[3] - 33; v *= 85;
+			v += in[4] - 33;
+			in += 5;
+		}
+		out[len++] = v;
+	}
+
+	len = zlib_inflate(out, len * sizeof(*out), ptr);
+	free(out);
+
+	return len;
+}
+
+int igt_kcov_from_string(struct igt_kcov *kc, const char *str)
+{
+	kc->fd = -1;
+	kc->tbl = NULL;
+
+	kc->sz = ascii85_decode(str, &kc->tbl);
+	if (!kc->sz)
+		return -1;
+
+	return 0;
+}
+
+void igt_kcov_close(struct igt_kcov *kc)
+{
+	if (kc->fd < 0) {
+		free(kc->tbl);
+	} else {
+		munmap(kc->tbl, kc->sz * sizeof(unsigned long));
+		close(kc->fd);
+	}
+	kc->tbl = NULL;
+	kc->fd = -1;
+}
diff --git a/lib/igt_kcov.h b/lib/igt_kcov.h
new file mode 100644
index 00000000..e22982ab
--- /dev/null
+++ b/lib/igt_kcov.h
@@ -0,0 +1,26 @@
+#ifndef IGT_KCOV_H
+#define IGT_KCOV_H
+
+#include <stdbool.h>
+
+struct igt_kcov {
+	void *tbl;
+	int fd;
+	int sz;
+};
+
+int igt_kcov_open(struct igt_kcov *kc);
+void igt_kcov_close(struct igt_kcov *kc);
+
+void igt_kcov_reset(struct igt_kcov *kc);
+bool igt_kcov_enable(struct igt_kcov *kc);
+bool igt_kcov_disable(struct igt_kcov *kc);
+
+bool igt_kcov_merge(struct igt_kcov *out, const struct igt_kcov *m);
+double igt_kcov_similarity(const struct igt_kcov *ka,
+			   const struct igt_kcov *kb);
+
+char *igt_kcov_to_string(const struct igt_kcov *kc);
+int igt_kcov_from_string(struct igt_kcov *kc, const char *str);
+
+#endif /* IGT_KCOV_H */
diff --git a/tests/Makefile.am b/tests/Makefile.am
index f9d11e6c..84f6aba9 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -20,6 +20,8 @@ TESTS_progs += \
 	$(NULL)
 endif
 
+TESTS_progs += kcov_compare kcov_merge
+
 if BUILD_TESTS
 test-list.txt: Makefile.sources
 	@echo TESTLIST > $@
diff --git a/tests/gem_exec_nop.c b/tests/gem_exec_nop.c
index 62a53605..fdb1413e 100644
--- a/tests/gem_exec_nop.c
+++ b/tests/gem_exec_nop.c
@@ -26,6 +26,7 @@
  */
 
 #include "igt.h"
+#include "igt_kcov.h"
 #include "igt_rand.h"
 #include "igt_sysfs.h"
 
diff --git a/tests/gem_spin_batch.c b/tests/gem_spin_batch.c
index 24c5d9b7..89631130 100644
--- a/tests/gem_spin_batch.c
+++ b/tests/gem_spin_batch.c
@@ -48,7 +48,7 @@ static void spin(int fd, unsigned int engine, unsigned int timeout_sec)
 		igt_spin_batch_set_timeout(spin,
 					   timeout_100ms - igt_nsec_elapsed(&itv));
 		gem_sync(fd, spin->handle);
-		igt_debug("loop %d: interval=%fms (target 100ms), elapsed %fms\n",
+		igt_debug("loop %lu: interval=%fms (target 100ms), elapsed %fms\n",
 			  loops,
 			  igt_nsec_elapsed(&itv) * 1e-6,
 			  igt_nsec_elapsed(&tv) * 1e-6);
diff --git a/tests/kcov_compare.c b/tests/kcov_compare.c
new file mode 100644
index 00000000..ed1cfb1c
--- /dev/null
+++ b/tests/kcov_compare.c
@@ -0,0 +1,101 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "igt_kcov.h"
+
+int main(int argc, char **argv)
+{
+	size_t len = 0;
+	char *line = NULL;
+	char **name;
+	struct igt_kcov *kcov;
+	int count = 0;
+	int size = 1024;
+	double *M, *dis, *sim;
+	bool *used;
+	int last = -1;
+
+	name = malloc(size * sizeof(*name));
+	kcov = malloc(size * sizeof(*kcov));
+
+	while (getline(&line, &len, stdin) != -1) {
+		char *colon = strchr(line, ':');
+		if (!colon)
+			continue;
+
+		*colon = '\0';
+		while (isspace(*++colon))
+			;
+
+		if (count == size) {
+			size *= 2;
+			name = realloc(name, size * sizeof(*name));
+			kcov = realloc(kcov, size * sizeof(*kcov));
+		}
+
+		name[count] = strdup(line);
+		igt_kcov_from_string(&kcov[count], colon);
+		count++;
+	}
+	free(line);
+	printf("#%d tests\n", count);
+
+	M = malloc(sizeof(double) * count * (count + 2));
+	dis = M + count * count;
+	sim = dis + count;
+	for (int i = 0; i < count; i++) {
+		dis[i] = 0.;
+		sim[i] = 1.;
+		for (int j = 0; j < i; j++)
+			dis[i] += M[j*count + i];
+		for (int j = i + 1; j < count; j++) {
+			double s = igt_kcov_similarity(&kcov[i], &kcov[j]);
+			s = 1. - s*s;
+			M[i*count + j] = s;
+			dis[i] += s;
+		}
+		igt_kcov_close(&kcov[i]);
+	}
+	free(kcov);
+
+	used = calloc(count, sizeof(bool));
+	for (int rank = 0; rank < count; rank++) {
+		double best = -HUGE_VAL;
+		int this = -1;
+
+		for (int i = 0; i < count; i++) {
+			double d;
+
+			if (used[i])
+				continue;
+
+			d = dis[i];
+			if (last != -1) {
+				double s;
+
+				if (last < i)
+					s = M[last * count + i];
+				else
+					s = M[i * count + last];
+
+				s *= sim[i];
+				sim[i] = s;
+
+				d *= sqrt(s);
+			}
+			if (d > best) {
+				best = d;
+				this = i;
+			}
+		}
+
+		printf("%s #%f\n", name[this], sqrt(best / count));
+		used[this] = true;
+		last = this;
+	}
+
+	return 0;
+}
diff --git a/tests/kcov_merge.c b/tests/kcov_merge.c
new file mode 100644
index 00000000..b9d13542
--- /dev/null
+++ b/tests/kcov_merge.c
@@ -0,0 +1,87 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "igt_kcov.h"
+
+struct trace {
+	char *name;
+	struct igt_kcov kcov;
+	struct trace *next;
+};
+
+#define NUM_BUCKETS 1024
+#define MASK_BUCKETS (NUM_BUCKETS - 1)
+
+static unsigned int hash_str(const char *str)
+{
+	const unsigned int hash_mult = 2654435387U;
+	unsigned int h = 0;
+
+	while (*str)
+		h = (h + (unsigned int) *str++) * hash_mult;
+
+	return h & MASK_BUCKETS;
+}
+
+int main(int argc, char **argv)
+{
+	FILE *file = stdin;
+	size_t len = 0;
+	char *line = NULL;
+	struct trace **ht;
+
+	ht = calloc(NUM_BUCKETS, sizeof(*ht));
+
+	while (getline(&line, &len, file) != -1) {
+		struct trace *t;
+		int bkt;
+		char *colon;
+
+		colon = strchr(line, ':');
+		if (!colon)
+			continue;
+
+		*colon = '\0';
+		while (isspace(*++colon))
+			;
+
+		bkt = hash_str(line);
+		for (t = ht[bkt]; t; t = t->next)
+			if (!strcmp(t->name, line))
+				break;
+		if (t) {
+			struct igt_kcov kcov;
+
+			igt_kcov_from_string(&kcov, colon);
+			igt_kcov_merge(&t->kcov, &kcov);
+			igt_kcov_close(&kcov);
+			continue;
+		}
+
+		t = malloc(sizeof(*t));
+		t->name = strdup(line);
+		if (igt_kcov_from_string(&t->kcov, colon) < 0) {
+			fprintf(stderr, "Failed to parse '%s'\n", line);
+			free(t->name);
+			free(t);
+			continue;
+		}
+
+		t->next = ht[bkt];
+		ht[bkt] = t;
+	}
+	free(line);
+
+	for (int bkt = 0; bkt < NUM_BUCKETS; bkt++) {
+		for (struct trace *t = ht[bkt]; t; t = t->next) {
+			char *str = igt_kcov_to_string(&t->kcov);
+			printf("%s: %s\n", t->name, str);
+			free(str);
+		}
+	}
+
+	return 0;
+}