[igt-dev] [PATCH i-g-t 16/17] tools: capture execution pathways

Chris Wilson chris at chris-wilson.co.uk
Mon Jul 2 09:07:26 UTC 2018


igt_kcov edges -o edges.yaml command-to-trace args
...
igt_kcov sort -o sorted.yaml edges.yaml
igt_kcov list --total=30 --single=0.5 sorted.yaml

Requires CONFIG_KCOV

Use LD_PRELOAD to wrap calls to DRM ioctls and capture the execution
trace of all basic blocks invoked directly from the syscall. (Key
limitation!) From the chain of basic blocks, the "edges" are computed
and the number of times each edge is hit is stored in a vector (modulo a
large hash). The goal then is to select a series of tests that execute
the most unique pathways in the sortest amount of time. To do this we
compare the similarity of the coverage vectors between all commands, and
try to preferentially pick those that are dissimilar from the rest.

* Direct execution pathways from syscall is a huge limitation for
evaluating general testing of driver pathways, but is not so huge when
myopically focusing on the ABI as say used by mesa.

** Caveat lector. Hastily thrown together. (Still)
---
 meson.build            |    1 +
 tools/Makefile.am      |   11 +-
 tools/igt_kcov.c       | 1218 ++++++++++++++++++++++++++++++++++++++++
 tools/igt_kcov_edges.c |  145 +++++
 tools/meson.build      |   13 +
 5 files changed, 1387 insertions(+), 1 deletion(-)
 create mode 100644 tools/igt_kcov.c
 create mode 100644 tools/igt_kcov_edges.c

diff --git a/meson.build b/meson.build
index 638c01066..213745954 100644
--- a/meson.build
+++ b/meson.build
@@ -173,6 +173,7 @@ math = cc.find_library('m')
 realtime = cc.find_library('rt')
 dlsym = cc.find_library('dl')
 zlib = cc.find_library('z')
+yaml = cc.find_library('yaml', required: false)
 
 if cc.has_header('linux/kd.h')
 	config.set('HAVE_LINUX_KD_H', 1)
diff --git a/tools/Makefile.am b/tools/Makefile.am
index a0b016ddd..ae70f5a76 100644
--- a/tools/Makefile.am
+++ b/tools/Makefile.am
@@ -1,6 +1,7 @@
 include Makefile.sources
 
-bin_PROGRAMS = $(tools_prog_lists)
+bin_PROGRAMS = $(tools_prog_lists) igt_kcov
+lib_LTLIBRARIES = igt_kcov_edges.la
 
 if HAVE_LIBDRM_INTEL
 bin_PROGRAMS += $(LIBDRM_INTEL_BIN)
@@ -30,6 +31,14 @@ intel_aubdump_la_LIBADD = $(top_builddir)/lib/libintel_tools.la -ldl
 
 intel_gpu_top_LDADD = $(top_builddir)/lib/libigt_perf.la
 
+# XXX FIXME
+igt_kcov_SOURCES = igt_kcov.c
+igt_kcov_LDADD = -lyaml -lz -lrt -lm
+
+igt_kcov_edges_la_SOURCES = igt_kcov_edges.c
+igt_kcov_edges_la_LDFLAGS = -module -no-undefined -avoid-version
+igt_kcov_edges_la_LIBADD = -ldl
+
 bin_SCRIPTS = intel_aubdump
 CLEANFILES = $(bin_SCRIPTS)
 
diff --git a/tools/igt_kcov.c b/tools/igt_kcov.c
new file mode 100644
index 000000000..e9179a4b3
--- /dev/null
+++ b/tools/igt_kcov.c
@@ -0,0 +1,1218 @@
+#include <sys/types.h>
+#include <sys/file.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/wait.h>
+
+#include <ctype.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <getopt.h>
+#include <inttypes.h>
+#include <math.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#include <yaml.h>
+#include <zlib.h>
+
+#define SZ_8 (1 << 16)
+#define SZ_32 (sizeof(uint32_t) * SZ_8)
+
+static pid_t child = 0;
+
+static void sighandler(int sig)
+{
+	kill(sig, child);
+}
+
+static uint64_t gettime(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+
+	return ts.tv_sec * 1000000000 + ts.tv_nsec;
+}
+
+struct exec {
+	const char *preload;
+	int uid;
+	int gid;
+};
+
+static int edges_exec(const struct exec *args, char **argv, uint64_t *elapsed)
+{
+	char buf[10];
+	int status;
+	int kcov;
+	int shm;
+	int ret;
+
+	kcov = open("/sys/kernel/debug/kcov", O_RDWR);
+	if (kcov < 0)
+		return -errno;
+
+	shm = memfd_create("igt_kcov", 0);
+	if (shm == -1) {
+		close(kcov);
+		return -errno;
+	}
+
+	ftruncate(shm, SZ_32);
+
+	switch ((child = fork())) {
+	case 0: /* child */
+		if (args->gid)
+			setgid(args->gid);
+		if (args->uid)
+			setuid(args->uid);
+
+		sprintf(buf, "%d", shm);
+		setenv("IGT_SHM_FD", buf, 1);
+
+		sprintf(buf, "%d", kcov);
+		setenv("IGT_KCOV_FD", buf, 1);
+
+		setenv("LD_PRELOAD", args->preload, 1);
+		exit(execvp(argv[0], argv));
+		break;
+
+	case -1:
+		ret = -errno;
+		break;
+
+	default:
+		signal(SIGINT, sighandler);
+
+		*elapsed = -gettime();
+		do {
+			ret = waitpid(child, &status, 0);
+			if (ret == -1)
+				ret = -errno;
+		} while (ret == -EINTR);
+		*elapsed += gettime();
+
+		signal(SIGINT, SIG_DFL);
+		child = 0;
+	}
+
+	close(kcov);
+	if (ret < 0) {
+		close(shm);
+		shm = ret;
+	}
+
+	return shm;
+}
+
+static inline unsigned long __fls(unsigned long word)
+{
+#if defined(__GNUC__) && (defined(__i386__) || defined(__x86__) || defined(__x86_64__))
+	asm("bsr %1,%0"
+	    : "=r" (word)
+	    : "rm" (word));
+	return word;
+#else
+	unsigned int v = 0;
+
+	while (word >>= 1)
+		v++;
+
+	return v;
+#endif
+}
+
+static uint8_t lower_u32(uint32_t x)
+{
+	if (x < 16)
+		return x;
+	else
+		return (x >> (__fls(x) - 2)) + ((__fls(x) - 1) << 2);
+}
+
+static uint8_t *lower_edges(int shm)
+{
+	uint8_t *lower;
+	uint32_t *tbl;
+	unsigned int n;
+
+	tbl = mmap(NULL, SZ_32, PROT_READ, MAP_SHARED, shm, 0);
+	if (tbl == MAP_FAILED)
+		return NULL;
+
+	if (tbl[0] == 0) /* empty */
+		goto out;
+
+	lower = malloc(SZ_8);
+	if (!lower)
+		goto out;
+
+	for (n = 0; n < 1 << 16; n++)
+		lower[n] = lower_u32(tbl[n]);
+
+out:
+	munmap(tbl, SZ_32);
+	return lower;
+}
+
+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;
+}
+
+static char *edges_to_ascii85(uint8_t *tbl)
+{
+	z_stream zs;
+	uint32_t *p;
+	void *out;
+	char *str, *s;
+	int sz;
+
+	sz = SZ_8 * 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 = tbl;
+	zs.avail_in = SZ_8;
+	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 void edges(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"output", required_argument, 0, 'o'},
+		{"preload", required_argument, 0, 'p'},
+		{"user", required_argument, 0, 'u'},
+		{"group", required_argument, 0, 'g'},
+		{ NULL, 0, NULL, 0 }
+	};
+	struct exec args = {
+		.preload = "/tmp/igt_kcov_edges.so",
+	};
+	FILE *out = stdout;
+	uint64_t elapsed;
+	uint8_t *tbl;
+	char *str, *s;
+	int shm, i;
+
+	while ((i = getopt_long(argc, argv,
+				"+o:g:u:",
+				longopts, NULL)) != -1) {
+		switch (i) {
+		case 'o':
+			if (strcmp(optarg, "-"))
+				out = fopen(optarg, "a");
+			if (!out) {
+				fprintf(stderr,
+					"Unable to open output file '%s'\n",
+					optarg);
+				exit(1);
+			}
+			break;
+		case 'p':
+			args.preload = optarg;
+			break;
+		case 'u':
+			args.uid = atoi(optarg);
+			break;
+		case 'g':
+			args.gid = atoi(optarg);
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	if (argc < 1) {
+		fprintf(stderr,
+			"usage: igt_kcov edges [options] program-to-trace args...\n");
+		exit(1);
+	}
+
+	shm = edges_exec(&args, argv, &elapsed);
+	if (shm < 0) {
+		fprintf(stderr,
+			"Execution of %s failed: err=%d\n",
+			argv[0], shm);
+		exit(1);
+	}
+
+	tbl = lower_edges(shm);
+	close(shm);
+	if (!tbl)
+		exit(1);
+
+	str = edges_to_ascii85(tbl);
+
+	flock(fileno(out), LOCK_EX);
+	fprintf(out, "---\n");
+
+	fprintf(out, "cmd: |  \n");
+	for (i = 0; i < argc; i++) {
+		fprintf(out, " '");
+		for (s = argv[i]; *s; s++) {
+			if (*s == '\'')
+				fprintf(out, "\\\'");
+			else
+				fprintf(out, "%c", *s);
+		}
+		fprintf(out, "'");
+	}
+	fprintf(out, "\n");
+
+	fprintf(out, "elapsed: %"PRIu64" # %.1fms\n", elapsed, 1e-6 * elapsed);
+
+	fprintf(out, "edges: !!ascii85.gz |\n");
+	i = strlen(str);
+	s = str;
+	while (i) {
+		int len = i > 70 ? 70 : i;
+		char tmp;
+
+		tmp = s[len];
+		s[len] = '\0';
+		fprintf(out, "  %s\n", s);
+		s[len] = tmp;
+
+		s += len;
+		i -= len;
+	}
+
+	fflush(out);
+	flock(fileno(out), LOCK_UN);
+
+	free(str);
+}
+
+static unsigned long zlib_inflate(void *in, unsigned long len,
+				  void *ptr, unsigned long max)
+{
+	struct z_stream_s zstream;
+
+	memset(&zstream, 0, sizeof(zstream));
+
+	zstream.next_in = in;
+	zstream.avail_in = len;
+
+	if (inflateInit(&zstream) != Z_OK)
+		return 0;
+
+	zstream.next_out = ptr;
+	zstream.avail_out = max;
+
+	switch (inflate(&zstream, Z_SYNC_FLUSH)) {
+	case Z_STREAM_END:
+	case Z_OK:
+		break;
+	default:
+		zstream.total_out = 0;
+		break;
+	}
+
+	inflateEnd(&zstream);
+	return zstream.total_out;
+}
+
+static unsigned long ascii85_decode(const char *in,
+				    void *ptr, unsigned long max)
+{
+	unsigned long sz = max / sizeof(uint32_t);
+	unsigned long len = 0;
+	uint32_t *out;
+
+	out = malloc(sz * sizeof(uint32_t));
+	if (out == NULL)
+		return 0;
+
+	while (*in) {
+		uint32_t v = 0;
+
+		if (isspace(*in)) {
+			in++;
+			continue;
+		}
+
+		if (*in < '!' || *in > 'z') {
+			fprintf(stderr, "Invalid value in ascii85 block\n");
+			free(out);
+			return 0;
+		}
+
+		if (len == sz) {
+			sz *= 2;
+			out = realloc(out, sz * sizeof(uint32_t));
+			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, max);
+	free(out);
+
+	return len;
+}
+
+static void yaml_print_parser_error(yaml_parser_t *parser, FILE *stream)
+{
+	switch (parser->error) {
+	case YAML_MEMORY_ERROR:
+		fprintf(stderr, "Memory error: Not enough memory for parsing\n");
+		break;
+
+	case YAML_READER_ERROR:
+		if (parser->problem_value != -1) {
+			fprintf(stderr, "Reader error: %s: #%X at %zd\n", parser->problem,
+				parser->problem_value, parser->problem_offset);
+		} else {
+			fprintf(stderr, "Reader error: %s at %zd\n", parser->problem,
+				parser->problem_offset);
+		}
+		break;
+
+	case YAML_SCANNER_ERROR:
+		if (parser->context) {
+			fprintf(stderr, "Scanner error: %s at line %lu, column %lu\n"
+				"%s at line %lu, column %lu\n", parser->context,
+				parser->context_mark.line+1, parser->context_mark.column+1,
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		} else {
+			fprintf(stderr, "Scanner error: %s at line %lu, column %lu\n",
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		}
+		break;
+
+	case YAML_PARSER_ERROR:
+		if (parser->context) {
+			fprintf(stderr, "Parser error: %s at line %lu, column %lu\n"
+				"%s at line %lu, column %lu\n", parser->context,
+				parser->context_mark.line+1, parser->context_mark.column+1,
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		} else {
+			fprintf(stderr, "Parser error: %s at line %lu, column %lu\n",
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		}
+		break;
+
+	default:
+		/* Couldn't happen. */
+		fprintf(stderr, "Internal error\n");
+		break;
+	}
+}
+
+struct edges {
+	struct edges *next;
+
+	char *command;
+	uint64_t elapsed;
+
+	unsigned int weight;
+
+	uint8_t tbl[SZ_8];
+};
+
+struct sort {
+	struct edges *edges;
+	unsigned int count;
+
+	unsigned int max_weight;
+	struct edges *best;
+};
+
+static bool sort_parse_command(struct sort *sort,
+			       struct edges *e,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+	int len;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+
+	s = (const char *)ev.data.scalar.value;
+	len = strlen(s);
+	while (s[len - 1] == '\n')
+		len--;
+	e->command = malloc(len + 1);
+	if (e->command) {
+		memcpy(e->command, s, len);
+		e->command[len] = '\0';
+	}
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool sort_parse_elapsed(struct sort *sort,
+			       struct edges *e,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+	s = (const char *)ev.data.scalar.value;
+	e->elapsed = strtoull(s, NULL, 0);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static unsigned int bitmap_weight(const void *bitmap, unsigned int bits)
+{
+	const uint32_t *b = bitmap;
+	unsigned int k, lim = bits / 32;
+	unsigned int w = 0;
+
+	for (k = 0; k < lim; k++)
+		w += __builtin_popcount(b[k]);
+
+	if (bits % 32)
+		w += __builtin_popcount(b[k] << (32 - bits % 32));
+
+	return w;
+}
+
+static bool sort_parse_edges(struct sort *sort,
+			     struct edges *e,
+			     yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+	s = (const char *)ev.data.scalar.value;
+	if (ascii85_decode(s, e->tbl, sizeof(e->tbl)))
+		e->weight = bitmap_weight(e->tbl, sizeof(e->tbl) * 8);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool edges_valid(const struct edges *e)
+{
+	if (!e->command)
+		return false;
+
+	if (!e->weight)
+		return false;
+
+	if (!e->elapsed)
+		return false;
+
+	return true; /* good enough at least */
+}
+
+static bool sort_add_edges(struct sort *sort, struct edges *e)
+{
+	if (!edges_valid(e))
+		return false;
+
+	e->next = sort->edges;
+	sort->edges = e;
+
+	if (e->weight > sort->max_weight) {
+		sort->max_weight = e->weight;
+		sort->best = e;
+	}
+
+	sort->count++;
+
+	return true;
+}
+
+static bool sort_parse_node(struct sort *sort, yaml_parser_t *parser)
+{
+	struct edges *e;
+	yaml_event_t ev;
+	char *s;
+
+	e = malloc(sizeof(*e));
+	if (!e)
+		return false;
+
+	e->weight = 0;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			goto err;
+
+		switch (ev.type) {
+		case YAML_MAPPING_END_EVENT:
+			if (!sort_add_edges(sort, e))
+				goto err;
+
+			return true;
+
+		case YAML_SCALAR_EVENT:
+			break;
+
+		default:
+			goto err;
+		}
+
+		s = (char *)ev.data.scalar.value;
+		if (!strcmp(s, "cmd")) {
+			sort_parse_command(sort, e, parser);
+		} else if (!strcmp(s, "elapsed")) {
+			sort_parse_elapsed(sort, e, parser);
+		} else if (!strcmp(s, "edges")) {
+			sort_parse_edges(sort, e, parser);
+		} else {
+			fprintf(stderr,
+				"Unknown element in edges file: %s\n",
+				s);
+		}
+
+		yaml_event_delete(&ev);
+	} while (1);
+
+err:
+	free(e);
+	return false;
+}
+
+static bool sort_parse_doc(struct sort *sort, yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_END_EVENT:
+			return true;
+
+		case YAML_MAPPING_START_EVENT:
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+
+		if (!sort_parse_node(sort, parser))
+			return false;
+	} while(1);
+}
+
+static bool sort_add(struct sort *sort, FILE *file)
+{
+	yaml_parser_t parser;
+	bool done = false;
+	yaml_event_t ev;
+
+	yaml_parser_initialize(&parser);
+	yaml_parser_set_input_file(&parser, file);
+
+	memset(&ev, 0, sizeof(ev));
+	yaml_parser_parse(&parser, &ev);
+	if (ev.type != YAML_STREAM_START_EVENT) {
+		fprintf(stderr, "Parser setup failed\n");
+		return false;
+	}
+	yaml_event_delete(&ev);
+
+	do {
+		if (!yaml_parser_parse(&parser, &ev)) {
+			yaml_print_parser_error(&parser, stderr);
+			return false;
+		}
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_START_EVENT:
+			break;
+
+		case YAML_STREAM_END_EVENT:
+			done = true;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+
+		sort_parse_doc(sort, &parser);
+	} while (!done);
+
+	yaml_parser_delete(&parser);
+	return true;
+}
+
+static double edges_similarity(const struct edges *ta, const struct edges *tb)
+{
+	uint64_t sab, saa, sbb;
+	const uint8_t *a, *b;
+
+	if (ta == tb)
+		return 1;
+
+	a = ta->tbl;
+	b = tb->tbl;
+	sab = 0;
+	saa = 0;
+	sbb = 0;
+
+	for (unsigned int i = 0; i < SZ_8; i++) {
+		sab += (uint32_t)a[i] * b[i];
+		saa += (uint32_t)a[i] * a[i];
+		sbb += (uint32_t)b[i] * b[i];
+	}
+
+	return ((long double)sab * sab) / ((long double)saa * sbb);
+}
+
+static void rank_by_dissimilarity(struct sort *sort, FILE *out)
+{
+	const unsigned int count = sort->count;
+	double *M, *dis, *sim;
+	struct edges **edges, **t;
+	bool *used;
+	int last = -1;
+
+	t = edges = malloc(count * sizeof(*edges));
+	for (struct edges *e = sort->edges; e; e = e->next)
+		*t++ = e;
+
+	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 d = 1. - edges_similarity(edges[i], edges[j]);
+			M[i*count + j] = d;
+			dis[i] += d;
+		}
+	}
+
+	fprintf(out, "---\n");
+
+	used = calloc(count, sizeof(bool));
+	for (int rank = 0; rank < count; rank++) {
+		struct edges *e;
+		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;
+			}
+		}
+
+		if (this < 0)
+			break;
+
+		e = edges[this];
+		used[this] = true;
+		last = this;
+
+		fprintf(out, "- cmd: |\n    %s\n", e->command);
+		fprintf(out, "  elapsed: %"PRIu64" # %.1fms\n",
+			e->elapsed, 1e-6 * e->elapsed);
+		fprintf(out, "  dissimilarity: %.4g\n",
+			sqrt(best / (count - rank)));
+	}
+
+	free(M);
+	free(edges);
+}
+
+static void sort(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"output", required_argument, 0, 'o'},
+		{ NULL, 0, NULL, 0 }
+	};
+	FILE *out = stdout;
+	struct sort sort;
+	int i;
+
+	while ((i = getopt_long(argc, argv,
+				"+o:",
+				longopts, NULL)) != -1) {
+		switch (i) {
+		case 'o':
+			if (strcmp(optarg, "-"))
+				out = fopen(optarg, "a");
+			if (!out) {
+				fprintf(stderr,
+					"Unable to open output file '%s'\n",
+					optarg);
+				exit(1);
+			}
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	memset(&sort, 0, sizeof(sort));
+
+	if (argc == 0) {
+		sort_add(&sort, stdin);
+	} else {
+		for (i = 0; i < argc; i++) {
+			FILE *in;
+
+			in = fopen(argv[i], "r");
+			if (!in) {
+				fprintf(stderr, "unable to open input '%s'\n",
+					argv[i]);
+				exit(1);
+			}
+
+			sort_add(&sort, in);
+
+			fclose(in);
+		}
+	}
+
+	if (!sort.count)
+		return;
+
+	rank_by_dissimilarity(&sort, out);
+}
+
+struct list {
+	struct {
+		double single;
+		double total;
+	} limit;
+	double total;
+	FILE *out;
+};
+
+struct list_node {
+	char *cmd;
+	uint64_t elapsed;
+};
+
+static bool list_parse_command(struct list *list,
+			       struct list_node *node,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+	int len;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+
+	s = (const char *)ev.data.scalar.value;
+	len = strlen(s);
+	while (len > 0 && isspace(s[len - 1]))
+		len--;
+
+	node->cmd = strndup(s, len);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool list_parse_elapsed(struct list *list,
+			       struct list_node *node,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+	s = (const char *)ev.data.scalar.value;
+	node->elapsed = strtoull(s, NULL, 0);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool list_parse_node(struct list *list, yaml_parser_t *parser)
+{
+	struct list_node node = {};
+	yaml_event_t ev;
+	char *s;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_MAPPING_END_EVENT:
+			if (list->limit.single &&
+			    1e-9 * node.elapsed > list->limit.single) {
+				free(node.cmd);
+				return true;
+			}
+
+			if (list->limit.total &&
+			    list->total + 1e-9 * node.elapsed > list->limit.total) {
+				free(node.cmd);
+				return true;
+			}
+
+			if (node.cmd) {
+				list->total += 1e-9 * node.elapsed;
+				fprintf(list->out,
+					"%s # %.3fms, total %.1fms\n",
+					node.cmd,
+					1e-6 * node.elapsed,
+					1e3 * list->total);
+				free(node.cmd);
+			}
+			return true;
+
+		case YAML_SCALAR_EVENT:
+			break;
+
+		default:
+			return false;
+		}
+
+		s = (char *)ev.data.scalar.value;
+		if (!strcmp(s, "cmd")) {
+			list_parse_command(list, &node, parser);
+		} else if (!strcmp(s, "elapsed")) {
+			if (!list_parse_elapsed(list, &node,parser))
+				return false;
+		}
+		yaml_event_delete(&ev);
+	} while (1);
+}
+
+static bool list_parse_sequence(struct list *list, yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_SEQUENCE_END_EVENT:
+			return true;
+
+		case YAML_MAPPING_START_EVENT:
+			if (!list_parse_node(list, parser))
+				return false;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+	} while(1);
+}
+
+static bool list_parse_doc(struct list *list, yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_END_EVENT:
+			return true;
+
+		case YAML_MAPPING_START_EVENT:
+			if (!list_parse_node(list, parser))
+				return false;
+			break;
+
+		case YAML_SEQUENCE_START_EVENT:
+			if (!list_parse_sequence(list, parser))
+				return false;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+	} while(1);
+}
+
+static bool list_show(struct list *list, FILE *file)
+{
+	yaml_parser_t parser;
+	bool done = false;
+	yaml_event_t ev;
+
+	yaml_parser_initialize(&parser);
+	yaml_parser_set_input_file(&parser, file);
+
+	memset(&ev, 0, sizeof(ev));
+	yaml_parser_parse(&parser, &ev);
+	if (ev.type != YAML_STREAM_START_EVENT) {
+		fprintf(stderr, "Parser setup failed\n");
+		return false;
+	}
+	yaml_event_delete(&ev);
+
+	do {
+		if (!yaml_parser_parse(&parser, &ev)) {
+			yaml_print_parser_error(&parser, stderr);
+			return false;
+		}
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_START_EVENT:
+			break;
+
+		case YAML_STREAM_END_EVENT:
+			done = true;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+
+		list_parse_doc(list, &parser);
+	} while (!done);
+
+	yaml_parser_delete(&parser);
+	return true;
+}
+
+static void list(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"output", required_argument, 0, 'o'},
+		{"total", required_argument, 0, 't'},
+		{"single", required_argument, 0, 's'},
+		{ NULL, 0, NULL, 0 }
+	};
+	struct list list;
+	int i;
+
+	memset(&list, 0, sizeof(list));
+	list.out = stdout;
+
+	while ((i = getopt_long(argc, argv,
+				"+o:t:",
+				longopts, NULL)) != -1) {
+		switch (i) {
+		case 'o':
+			if (strcmp(optarg, "-"))
+				list.out = fopen(optarg, "a");
+			if (!list.out) {
+				fprintf(stderr,
+					"Unable to open output file '%s'\n",
+					optarg);
+				exit(1);
+			}
+			break;
+		case 's':
+			list.limit.single = atof(optarg);
+			break;
+		case 't':
+			list.limit.total = atof(optarg);
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	if (argc == 0) {
+		list_show(&list, stdin);
+	} else {
+		for (i = 0; i < argc; i++) {
+			FILE *in;
+
+			in = fopen(argv[i], "r");
+			if (!in) {
+				fprintf(stderr, "unable to open input '%s'\n",
+					argv[i]);
+				exit(1);
+			}
+
+			if (!list_show(&list, in))
+				i = argc;
+
+			fclose(in);
+		}
+	}
+}
+
+int main(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"verbose", no_argument, 0, 'v'},
+		{ NULL, 0, NULL, 0 }
+	};
+	int o;
+
+	while ((o = getopt_long(argc, argv,
+				"+v",
+				longopts, NULL)) != -1) {
+		switch (o) {
+		case 'v':
+			break;
+		default:
+			break;
+		}
+	}
+
+	if (optind == argc) {
+		fprintf(stderr, "no subcommand specified\n");
+		exit(1);
+	}
+
+	argc -= optind;
+	argv += optind;
+	optind = 1;
+
+	if (!strcmp(argv[0], "edges")) {
+		edges(argc, argv);
+	} else if (!strcmp(argv[0], "sort")) {
+		sort(argc, argv);
+	} else if (!strcmp(argv[0], "list")) {
+		list(argc, argv);
+	} else {
+		fprintf(stderr, "Unknown command '%s'\n", argv[0]);
+		exit(1);
+	}
+
+	return 0;
+}
diff --git a/tools/igt_kcov_edges.c b/tools/igt_kcov_edges.c
new file mode 100644
index 000000000..750d4f8b5
--- /dev/null
+++ b/tools/igt_kcov_edges.c
@@ -0,0 +1,145 @@
+#include <sys/ioctl.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+
+#include <dlfcn.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <pthread.h>
+
+#include <linux/types.h>
+
+static int (*libc_ioctl)(int fd, unsigned long request, void *argp);
+
+static struct kcov {
+	unsigned long *trace;
+	uint32_t *table;
+	int fd;
+} kcov;
+
+#define KCOV_INIT_TRACE                 _IOR('c', 1, unsigned long)
+#define KCOV_ENABLE                     _IO('c', 100)
+#define   KCOV_TRACE_PC  0
+#define   KCOV_TRACE_CMP 1
+#define KCOV_DISABLE                    _IO('c', 101)
+
+#define DRM_IOCTL_BASE 'd'
+
+#define GOLDEN_RATIO_32 0x61C88647
+#define GOLDEN_RATIO_64 0x61C8864680B583EBull
+
+static inline uint32_t hash_32(uint32_t val, unsigned int bits)
+{
+        return val * GOLDEN_RATIO_32 >> (32 - bits);
+}
+
+static inline uint32_t hash_64(uint64_t val, unsigned int bits)
+{
+        return val * GOLDEN_RATIO_64 >> (64 - bits);
+}
+
+#define hash_long(x, y) hash_64(x, y)
+
+static bool kcov_open(struct kcov *kc, unsigned long count)
+{
+	const char *env;
+	int shm;
+
+	env = getenv("IGT_SHM_FD");
+	if (!env)
+		return false;
+
+	shm = atoi(env);
+	kc->table = mmap(NULL, sizeof(uint32_t) << 16,
+			 PROT_WRITE, MAP_SHARED, shm, 0);
+	close(shm);
+	if (kc->table == (uint32_t *)MAP_FAILED)
+		return false;
+
+	env = getenv("IGT_KCOV_FD");
+	if (!env)
+		goto err_shm;
+
+	kc->fd = atoi(env);
+	if (libc_ioctl(kc->fd, KCOV_INIT_TRACE, (void *)count))
+		goto err_close;
+
+	kc->trace = mmap(NULL, count * sizeof(unsigned long),
+			 PROT_WRITE, MAP_SHARED, kc->fd, 0);
+	if (kc->trace == MAP_FAILED)
+		goto err_close;
+
+	return true;
+
+err_close:
+	close(kc->fd);
+err_shm:
+	munmap(kc->table, sizeof(uint32_t) << 16);
+	return false;
+}
+
+static void kcov_enable(struct kcov *kc)
+{
+	libc_ioctl(kc->fd, KCOV_ENABLE, KCOV_TRACE_PC);
+	__atomic_store_n(&kc->trace[0], 0, __ATOMIC_RELAXED);
+}
+
+static unsigned long kcov_disable(struct kcov *kc)
+{
+	unsigned long depth;
+
+	depth = __atomic_load_n(&kc->trace[0], __ATOMIC_RELAXED);
+	if (libc_ioctl(kc->fd, KCOV_DISABLE, 0))
+		depth = 0;
+
+	return depth;
+}
+
+int ioctl(int fd, unsigned long request, ...)
+{
+	static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
+	unsigned long count, n, prev;
+	va_list args;
+	void *argp;
+	int res;
+
+	va_start(args, request);
+	argp = va_arg(args, void *);
+	va_end(args);
+
+	if (kcov.fd < 0 || _IOC_TYPE(request) != DRM_IOCTL_BASE)
+		return libc_ioctl(fd, request, argp);
+
+	pthread_mutex_lock(&mutex);
+	kcov_enable(&kcov);
+
+	res = libc_ioctl(fd, request, argp);
+
+	count = kcov_disable(&kcov);
+	prev = hash_long(kcov.trace[1], 16);
+	for (n = 2; n <= count; n++) {
+		unsigned long loc = hash_long(kcov.trace[n], 16);
+
+		kcov.table[prev ^ loc]++;
+		prev = loc >> 1;
+	}
+	kcov.table[0] |= 1;
+	pthread_mutex_unlock(&mutex);
+
+	return res;
+}
+
+__attribute__((constructor))
+static void init(void)
+{
+	libc_ioctl = dlsym(RTLD_NEXT, "ioctl");
+
+	if (!kcov_open(&kcov, 64 << 10))
+		kcov.fd = -1;
+}
diff --git a/tools/meson.build b/tools/meson.build
index 8ed1ccf48..d0d9c9c91 100644
--- a/tools/meson.build
+++ b/tools/meson.build
@@ -104,6 +104,19 @@ executable('intel_reg', sources : intel_reg_src,
 	     '-DIGT_DATADIR="@0@"'.format(join_paths(prefix, datadir)),
 	   ])
 
+if yaml.found()
+	executable('igt_kcov',
+		   sources: [ 'igt_kcov.c' ],
+		   dependencies: [ zlib, realtime, math, yaml ],
+		   install: true) # setuid me!
+
+	shared_module('igt_kcov_edges',
+		      sources: [ 'igt_kcov_edges.c' ],
+		      name_prefix: '',
+		      dependencies: [ dlsym ],
+		      install: true) # -version, -Dlibdir
+endif
+
 install_data('intel_gpu_abrt', install_dir : bindir)
 
 install_subdir('registers', install_dir : datadir,
-- 
2.18.0



More information about the igt-dev mailing list