/*	$OpenBSD: btrace.c,v 1.61 2021/12/07 22:17:03 guenther Exp $ */

/*
 * Copyright (c) 2019 - 2021 Martin Pieuchot <mpi@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/ioctl.h>
#include <sys/exec_elf.h>
#include <sys/stat.h>
#include <sys/syscall.h>
#include <sys/queue.h>

#include <assert.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <locale.h>
#include <paths.h>
#include <signal.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#include <dev/dt/dtvar.h>

#include "btrace.h"
#include "bt_parser.h"

#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))
#define MAXIMUM(a, b)	(((a) > (b)) ? (a) : (b))

/*
 * Maximum number of operands an arithmetic operation can have.  This
 * is necessary to stop infinite recursion when evaluating expressions.
 */
#define __MAXOPERANDS	5

#define __PATH_DEVDT "/dev/dt"

__dead void		 usage(void);
char			*read_btfile(const char *, size_t *);

/*
 * Retrieve & parse probe information.
 */
void			 dtpi_cache(int);
void			 dtpi_print_list(void);
const char		*dtpi_func(struct dtioc_probe_info *);
int			 dtpi_is_unit(const char *);
struct dtioc_probe_info	*dtpi_get_by_value(const char *, const char *,
			     const char *);

/*
 * Main loop and rule evaluation.
 */
void			 rules_do(int);
void			 rules_setup(int);
void			 rules_apply(struct dt_evt *);
void			 rules_teardown(int);
void			 rule_eval(struct bt_rule *, struct dt_evt *);
void			 rule_printmaps(struct bt_rule *);

/*
 * Language builtins & functions.
 */
uint64_t		 builtin_nsecs(struct dt_evt *);
const char		*builtin_kstack(struct dt_evt *);
const char		*builtin_arg(struct dt_evt *, enum bt_argtype);
struct bt_arg		*fn_str(struct bt_arg *, struct dt_evt *, char *);
void			 stmt_eval(struct bt_stmt *, struct dt_evt *);
void			 stmt_bucketize(struct bt_stmt *, struct dt_evt *);
void			 stmt_clear(struct bt_stmt *);
void			 stmt_delete(struct bt_stmt *, struct dt_evt *);
void			 stmt_insert(struct bt_stmt *, struct dt_evt *);
void			 stmt_print(struct bt_stmt *, struct dt_evt *);
void			 stmt_store(struct bt_stmt *, struct dt_evt *);
bool			 stmt_test(struct bt_stmt *, struct dt_evt *);
void			 stmt_time(struct bt_stmt *, struct dt_evt *);
void			 stmt_zero(struct bt_stmt *);
struct bt_arg		*ba_read(struct bt_arg *);
const char		*ba2hash(struct bt_arg *, struct dt_evt *);
long			 baexpr2long(struct bt_arg *, struct dt_evt *);
const char		*ba2bucket(struct bt_arg *, struct bt_arg *,
			     struct dt_evt *, long *);
int			 ba2dtflags(struct bt_arg *);

/*
 * Debug routines.
 */
__dead void		 xabort(const char *, ...);
void			 debug(const char *, ...);
void			 debugx(const char *, ...);
const char		*debug_probe_name(struct bt_probe *);
void			 debug_dump_term(struct bt_arg *);
void			 debug_dump_expr(struct bt_arg *);
void			 debug_dump_filter(struct bt_rule *);

struct dtioc_probe_info	*dt_dtpis;	/* array of available probes */
size_t			 dt_ndtpi;	/* # of elements in the array */

struct dt_evt		 bt_devt;	/* fake event for BEGIN/END */
uint64_t		 bt_filtered;	/* # of events filtered out */

char			**vargs;
int			 nargs = 0;
int			 verbose = 0;
volatile sig_atomic_t	 quit_pending;

static void
signal_handler(int sig)
{
	quit_pending = sig;
}


int
main(int argc, char *argv[])
{
	int fd = -1, ch, error = 0;
	const char *filename = NULL, *btscript = NULL;
	int showprobes = 0, noaction = 0;
	size_t btslen = 0;

	setlocale(LC_ALL, "");

	while ((ch = getopt(argc, argv, "e:lnp:v")) != -1) {
		switch (ch) {
		case 'e':
			btscript = optarg;
			btslen = strlen(btscript);
			break;
		case 'l':
			showprobes = 1;
			break;
		case 'n':
			noaction = 1;
			break;
		case 'v':
			verbose++;
			break;
		default:
			usage();
		}
	}

	argc -= optind;
	argv += optind;

	if (argc > 0 && btscript == NULL)
		filename = argv[0];

	 /* Cannot pledge due to special ioctl()s */
	if (unveil(__PATH_DEVDT, "r") == -1)
		err(1, "unveil %s", __PATH_DEVDT);
	if (unveil(_PATH_KSYMS, "r") == -1)
		err(1, "unveil %s", _PATH_KSYMS);
	if (filename != NULL) {
		if (unveil(filename, "r") == -1)
			err(1, "unveil %s", filename);
	}
	if (unveil(NULL, NULL) == -1)
		err(1, "unveil");

	if (filename != NULL) {
		btscript = read_btfile(filename, &btslen);
		argc--;
		argv++;
	}

	nargs = argc;
	vargs = argv;

	if (btscript == NULL && !showprobes)
		usage();

	if (btscript != NULL) {
		error = btparse(btscript, btslen, filename, 1);
		if (error)
			return error;
	}

	if (noaction)
		return error;

	if (showprobes || g_nprobes > 0) {
		fd = open(__PATH_DEVDT, O_RDONLY);
		if (fd == -1)
			err(1, "could not open %s", __PATH_DEVDT);
	}

	if (showprobes) {
		dtpi_cache(fd);
		dtpi_print_list();
	}

	if (!TAILQ_EMPTY(&g_rules))
		rules_do(fd);

	if (fd != -1)
		close(fd);

	return error;
}

__dead void
usage(void)
{
	fprintf(stderr, "usage: %s [-lnv] [-e program | file] [argument ...]\n",
	    getprogname());
	exit(1);
}

char *
read_btfile(const char *filename, size_t *len)
{
	FILE *fp;
	char *fcontent;
	struct stat st;
	size_t fsize;

	if (stat(filename, &st))
		err(1, "can't stat '%s'", filename);

	fsize = st.st_size;
	fcontent = malloc(fsize + 1);
	if (fcontent == NULL)
		err(1, "malloc");

	fp = fopen(filename, "r");
	if (fp == NULL)
		err(1, "can't open '%s'", filename);

	if (fread(fcontent, 1, fsize, fp) != fsize)
		err(1, "can't read '%s'", filename);
	fcontent[fsize] = '\0';

	fclose(fp);
	*len = fsize;
	return fcontent;
}

static int
dtpi_cmp(const void *a, const void *b)
{
	const struct dtioc_probe_info *ai = a, *bi = b;

	if (ai->dtpi_pbn > bi->dtpi_pbn)
		return 1;
	if (ai->dtpi_pbn < bi->dtpi_pbn)
		return -1;
	return 0;
}

void
dtpi_cache(int fd)
{
	struct dtioc_probe dtpr;

	if (dt_dtpis != NULL)
		return;

	memset(&dtpr, 0, sizeof(dtpr));
	if (ioctl(fd, DTIOCGPLIST, &dtpr))
		err(1, "DTIOCGPLIST");

	dt_ndtpi = (dtpr.dtpr_size / sizeof(*dt_dtpis));
	dt_dtpis = reallocarray(NULL, dt_ndtpi, sizeof(*dt_dtpis));
	if (dt_dtpis == NULL)
		err(1, "malloc");

	dtpr.dtpr_probes = dt_dtpis;
	if (ioctl(fd, DTIOCGPLIST, &dtpr))
		err(1, "DTIOCGPLIST");

	qsort(dt_dtpis, dt_ndtpi, sizeof(*dt_dtpis), dtpi_cmp);
}

void
dtpi_print_list(void)
{
	struct dtioc_probe_info *dtpi;
	size_t i;

	dtpi = dt_dtpis;
	for (i = 0; i < dt_ndtpi; i++, dtpi++) {
		printf("%s:%s:%s\n", dtpi->dtpi_prov, dtpi_func(dtpi),
		    dtpi->dtpi_name);
	}
}

const char *
dtpi_func(struct dtioc_probe_info *dtpi)
{
	char *sysnb, func[DTNAMESIZE];
	const char *errstr;
	int idx;

	if (strncmp(dtpi->dtpi_prov, "syscall", DTNAMESIZE))
		return dtpi->dtpi_func;

	/* Translate syscall names */
	strlcpy(func, dtpi->dtpi_func, sizeof(func));
	sysnb = func;
	if (strsep(&sysnb, "%") == NULL)
		return dtpi->dtpi_func;

	idx = strtonum(sysnb, 1, SYS_MAXSYSCALL, &errstr);
	if (errstr != NULL)
		return dtpi->dtpi_func;

	return syscallnames[idx];
}

int
dtpi_is_unit(const char *unit)
{
	return !strncmp("hz", unit, sizeof("hz"));
}

struct dtioc_probe_info *
dtpi_get_by_value(const char *prov, const char *func, const char *name)
{
	struct dtioc_probe_info *dtpi;
	size_t i;

	dtpi = dt_dtpis;
	for (i = 0; i < dt_ndtpi; i++, dtpi++) {
		if (prov != NULL &&
		    strncmp(prov, dtpi->dtpi_prov, DTNAMESIZE))
			continue;

		if (func != NULL) {
			if (dtpi_is_unit(func))
				return dtpi;

			if (strncmp(func, dtpi_func(dtpi), DTNAMESIZE))
				continue;
		}

		if (strncmp(name, dtpi->dtpi_name, DTNAMESIZE))
			continue;

		debug("matched probe %s:%s:%s\n", dtpi->dtpi_prov,
		    dtpi_func(dtpi), dtpi->dtpi_name);
		return dtpi;
	}

	return NULL;
}

static struct dtioc_probe_info *
dtpi_get_by_id(unsigned int pbn)
{
	struct dtioc_probe_info d;

	d.dtpi_pbn = pbn;
	return bsearch(&d, dt_dtpis, dt_ndtpi, sizeof(*dt_dtpis), dtpi_cmp);
}

void
rules_do(int fd)
{
	struct sigaction sa;

	memset(&sa, 0, sizeof(sa));
	sigemptyset(&sa.sa_mask);
	sa.sa_flags = 0;
	sa.sa_handler = signal_handler;
	if (sigaction(SIGINT, &sa, NULL))
		err(1, "sigaction");

	rules_setup(fd);

	while (!quit_pending && g_nprobes > 0) {
		static struct dt_evt devtbuf[64];
		ssize_t rlen;
		size_t i;

		rlen = read(fd, devtbuf, sizeof(devtbuf) - 1);
		if (rlen == -1) {
			if (errno == EINTR && quit_pending) {
				printf("\n");
				break;
			}
			err(1, "read");
		}

		if ((rlen % sizeof(struct dt_evt)) != 0)
			err(1, "incorrect read");

		for (i = 0; i < rlen / sizeof(struct dt_evt); i++)
			rules_apply(&devtbuf[i]);
	}

	rules_teardown(fd);

	if (verbose && fd != -1) {
		struct dtioc_stat dtst;

		memset(&dtst, 0, sizeof(dtst));
		if (ioctl(fd, DTIOCGSTATS, &dtst))
			warn("DTIOCGSTATS");

		printf("%llu events read\n", dtst.dtst_readevt);
		printf("%llu events dropped\n", dtst.dtst_dropevt);
		printf("%llu events filtered\n", bt_filtered);
	}
}

void
rules_setup(int fd)
{
	struct dtioc_probe_info *dtpi;
	struct dtioc_req *dtrq;
	struct bt_rule *r, *rbegin = NULL;
	struct bt_probe *bp;
	struct bt_stmt *bs;
	int dokstack = 0, on = 1;
	uint64_t evtflags;

	TAILQ_FOREACH(r, &g_rules, br_next) {
		evtflags = 0;
		SLIST_FOREACH(bs, &r->br_action, bs_next) {
			struct bt_arg *ba;

			SLIST_FOREACH(ba, &bs->bs_args, ba_next)
				evtflags |= ba2dtflags(ba);

			/* Also check the value for map/hist insertion */
			switch (bs->bs_act) {
			case B_AC_BUCKETIZE:
			case B_AC_INSERT:
				ba = (struct bt_arg *)bs->bs_var;
				evtflags |= ba2dtflags(ba);
				break;
			default:
				break;
			}
		}

		SLIST_FOREACH(bp, &r->br_probes, bp_next) {
			debug("parsed probe '%s'", debug_probe_name(bp));
			debug_dump_filter(r);

			if (bp->bp_type != B_PT_PROBE) {
				if (bp->bp_type == B_PT_BEGIN)
					rbegin = r;
				continue;
			}

			dtpi_cache(fd);
			dtpi = dtpi_get_by_value(bp->bp_prov, bp->bp_func,
			    bp->bp_name);
			if (dtpi == NULL) {
				errx(1, "probe '%s:%s:%s' not found",
				    bp->bp_prov, bp->bp_func, bp->bp_name);
			}

			dtrq = calloc(1, sizeof(*dtrq));
			if (dtrq == NULL)
				err(1, "dtrq: 1alloc");

			bp->bp_pbn = dtpi->dtpi_pbn;
			dtrq->dtrq_pbn = dtpi->dtpi_pbn;
			dtrq->dtrq_rate = bp->bp_rate;
			dtrq->dtrq_evtflags = evtflags;
			if (dtrq->dtrq_evtflags & DTEVT_KSTACK)
				dokstack = 1;
			bp->bp_cookie = dtrq;
		}
	}

	if (dokstack)
		kelf_open();

	/* Initialize "fake" event for BEGIN/END */
	bt_devt.dtev_pbn = -1;
	memcpy(&bt_devt.dtev_comm, getprogname(), sizeof(bt_devt.dtev_comm));
	bt_devt.dtev_pid = getpid();
	bt_devt.dtev_tid = getthrid();
	clock_gettime(CLOCK_REALTIME, &bt_devt.dtev_tsp);

	if (rbegin)
		rule_eval(rbegin, &bt_devt);

	/* Enable all probes */
	TAILQ_FOREACH(r, &g_rules, br_next) {
		SLIST_FOREACH(bp, &r->br_probes, bp_next) {
			if (bp->bp_type != B_PT_PROBE)
				continue;

			dtrq = bp->bp_cookie;
			if (ioctl(fd, DTIOCPRBENABLE, dtrq))
				err(1, "DTIOCPRBENABLE");
		}
	}

	if (g_nprobes > 0) {
		if (ioctl(fd, DTIOCRECORD, &on))
			err(1, "DTIOCRECORD");
	}
}

void
rules_apply(struct dt_evt *dtev)
{
	struct bt_rule *r;
	struct bt_probe *bp;

	TAILQ_FOREACH(r, &g_rules, br_next) {
		SLIST_FOREACH(bp, &r->br_probes, bp_next) {
			if (bp->bp_type != B_PT_PROBE ||
			    bp->bp_pbn != dtev->dtev_pbn)
				continue;

			rule_eval(r, dtev);
		}
	}
}

void
rules_teardown(int fd)
{
	struct dtioc_req *dtrq;
	struct bt_probe *bp;
	struct bt_rule *r, *rend = NULL;
	int dokstack = 0, off = 0;

	if (g_nprobes > 0) {
		if (ioctl(fd, DTIOCRECORD, &off))
			err(1, "DTIOCRECORD");
	}

	TAILQ_FOREACH(r, &g_rules, br_next) {
		SLIST_FOREACH(bp, &r->br_probes, bp_next) {
			if (bp->bp_type != B_PT_PROBE) {
				if (bp->bp_type == B_PT_END)
					rend = r;
				continue;
			}

			dtrq = bp->bp_cookie;
			if (ioctl(fd, DTIOCPRBDISABLE, dtrq))
				err(1, "DTIOCPRBDISABLE");
			if (dtrq->dtrq_evtflags & DTEVT_KSTACK)
				dokstack = 1;
		}
	}

	if (dokstack)
		kelf_close();

	/* Update "fake" event for BEGIN/END */
	clock_gettime(CLOCK_REALTIME, &bt_devt.dtev_tsp);

	if (rend)
		rule_eval(rend, &bt_devt);

	/* Print non-empty map & hist */
	TAILQ_FOREACH(r, &g_rules, br_next)
		rule_printmaps(r);
}

void
rule_eval(struct bt_rule *r, struct dt_evt *dtev)
{
	struct bt_stmt *bs;
	struct bt_probe *bp;

	SLIST_FOREACH(bp, &r->br_probes, bp_next) {
		debug("eval rule '%s'", debug_probe_name(bp));
		debug_dump_filter(r);
	}

	if (r->br_filter != NULL && r->br_filter->bf_condition != NULL) {
		if (stmt_test(r->br_filter->bf_condition, dtev) == false) {
			bt_filtered++;
			return;
		}
	}

	SLIST_FOREACH(bs, &r->br_action, bs_next) {
		if ((bs->bs_act == B_AC_TEST) && stmt_test(bs, dtev) == true)
			stmt_eval((struct bt_stmt *)bs->bs_var, dtev);

		stmt_eval(bs, dtev);
	}
}

void
rule_printmaps(struct bt_rule *r)
{
	struct bt_stmt *bs;

	SLIST_FOREACH(bs, &r->br_action, bs_next) {
		struct bt_arg *ba;

		SLIST_FOREACH(ba, &bs->bs_args, ba_next) {
			struct bt_var *bv = ba->ba_value;
			struct map *map;

			if (ba->ba_type != B_AT_MAP && ba->ba_type != B_AT_HIST)
				continue;

			map = (struct map *)bv->bv_value;
			if (map == NULL)
				continue;

			if (ba->ba_type == B_AT_MAP)
				map_print(map, SIZE_T_MAX, bv_name(bv));
			else
				hist_print((struct hist *)map, bv_name(bv));
			map_clear(map);
			bv->bv_value = NULL;
		}
	}
}

time_t
builtin_gettime(struct dt_evt *dtev)
{
	struct timespec ts;

	if (dtev == NULL) {
		clock_gettime(CLOCK_REALTIME, &ts);
		return ts.tv_sec;
	}

	return dtev->dtev_tsp.tv_sec;
}

static inline uint64_t
TIMESPEC_TO_NSEC(struct timespec *ts)
{
	return (ts->tv_sec * 1000000000L + ts->tv_nsec);
}

uint64_t
builtin_nsecs(struct dt_evt *dtev)
{
	struct timespec ts;

	if (dtev == NULL) {
		clock_gettime(CLOCK_REALTIME, &ts);
		return TIMESPEC_TO_NSEC(&ts);
	}

	return TIMESPEC_TO_NSEC(&dtev->dtev_tsp);
}

const char *
builtin_stack(struct dt_evt *dtev, int kernel)
{
	struct stacktrace *st = &dtev->dtev_kstack;
	static char buf[4096], *bp;
	size_t i;
	int sz;

	if (!kernel)
		return "";
	if (st->st_count == 0)
		return "\nuserland\n";

	buf[0] = '\0';
	bp = buf;
	sz = sizeof(buf);
	for (i = 0; i < st->st_count; i++) {
		int l;

		l = kelf_snprintsym(bp, sz - 1, st->st_pc[i]);
		if (l < 0)
			break;
		if (l >= sz - 1) {
			bp += sz - 1;
			sz = 1;
			break;
		}
		bp += l;
		sz -= l;
	}
	snprintf(bp, sz, "\nkernel\n");

	return buf;
}

const char *
builtin_arg(struct dt_evt *dtev, enum bt_argtype dat)
{
	static char buf[sizeof("18446744073709551615")]; /* UINT64_MAX */

	snprintf(buf, sizeof(buf), "%lu",
	    dtev->dtev_args[dat - B_AT_BI_ARG0]);

	return buf;
}

void
stmt_eval(struct bt_stmt *bs, struct dt_evt *dtev)
{
	switch (bs->bs_act) {
	case B_AC_BUCKETIZE:
		stmt_bucketize(bs, dtev);
		break;
	case B_AC_CLEAR:
		stmt_clear(bs);
		break;
	case B_AC_DELETE:
		stmt_delete(bs, dtev);
		break;
	case B_AC_EXIT:
		exit(0);
		break;
	case B_AC_INSERT:
		stmt_insert(bs, dtev);
		break;
	case B_AC_PRINT:
		stmt_print(bs, dtev);
		break;
	case B_AC_PRINTF:
		stmt_printf(bs, dtev);
		break;
	case B_AC_STORE:
		stmt_store(bs, dtev);
		break;
	case B_AC_TEST:
		/* done before */
		break;
	case B_AC_TIME:
		stmt_time(bs, dtev);
		break;
	case B_AC_ZERO:
		stmt_zero(bs);
		break;
	default:
		xabort("no handler for action type %d", bs->bs_act);
	}
}

/*
 * Increment a bucket:	{ @h = hist(v); } or { @h = lhist(v, min, max, step); }
 *
 * In this case 'h' is represented by `bv' and '(min, max, step)' by `brange'.
 */
void
stmt_bucketize(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *brange, *bhist = SLIST_FIRST(&bs->bs_args);
	struct bt_arg *bval = (struct bt_arg *)bs->bs_var;
	struct bt_var *bv = bhist->ba_value;
	const char *bucket;
	long step = 0;

	assert(bhist->ba_type == B_AT_HIST);
	assert(SLIST_NEXT(bval, ba_next) == NULL);

	brange = bhist->ba_key;
	bucket = ba2bucket(bval, brange, dtev, &step);
	if (bucket == NULL) {
		debug("hist=%p '%s' value=%lu out of range\n", bv->bv_value,
		    bv_name(bv), ba2long(bval, dtev));
		return;
	}
	debug("hist=%p '%s' increment bucket '%s'\n", bv->bv_value,
	    bv_name(bv), bucket);

	bv->bv_value = (struct bt_arg *)
	    hist_increment((struct hist *)bv->bv_value, bucket, step);
	bv->bv_type = B_VT_HIST;
}


/*
 * Empty a map:		{ clear(@map); }
 */
void
stmt_clear(struct bt_stmt *bs)
{
	struct bt_arg *ba = SLIST_FIRST(&bs->bs_args);
	struct bt_var *bv = ba->ba_value;
	struct map *map;

	assert(bs->bs_var == NULL);
	assert(ba->ba_type == B_AT_VAR);

	map = (struct map *)bv->bv_value;
	if (map == NULL)
		return;

	if (bv->bv_type != B_VT_MAP && bv->bv_type != B_VT_HIST)
		errx(1, "invalid variable type for clear(%s)", ba_name(ba));

	map_clear(map);
	bv->bv_value = NULL;

	debug("map=%p '%s' clear\n", map, bv_name(bv));
}

/*
 * Map delete:	 	{ delete(@map[key]); }
 *
 * In this case 'map' is represented by `bv' and 'key' by `bkey'.
 */
void
stmt_delete(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *bkey, *bmap = SLIST_FIRST(&bs->bs_args);
	struct bt_var *bv = bmap->ba_value;
	struct map *map;
	const char *hash;

	assert(bmap->ba_type == B_AT_MAP);
	assert(bs->bs_var == NULL);

	map = (struct map *)bv->bv_value;
	if (map == NULL)
		return;

	bkey = bmap->ba_key;
	hash = ba2hash(bkey, dtev);
	debug("map=%p '%s' delete key=%p '%s'\n", map, bv_name(bv), bkey, hash);

	map_delete(map, hash);
}

/*
 * Map insert:	 	{ @map[key] = 42; }
 *
 * In this case 'map' is represented by `bv', 'key' by `bkey' and
 * '42' by `bval'.
 */
void
stmt_insert(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *bkey, *bmap = SLIST_FIRST(&bs->bs_args);
	struct bt_arg *bval = (struct bt_arg *)bs->bs_var;
	struct bt_var *bv = bmap->ba_value;
	struct map *map;
	const char *hash;

	assert(bmap->ba_type == B_AT_MAP);
	assert(SLIST_NEXT(bval, ba_next) == NULL);

	bkey = bmap->ba_key;
	hash = ba2hash(bkey, dtev);

	/* map is NULL before first insert or after clear() */
	map = (struct map *)bv->bv_value;
	map = map_insert(map, hash, bval, dtev);

	debug("map=%p '%s' insert key=%p '%s' bval=%p\n", map,
	    bv_name(bv), bkey, hash, bval);

	bv->bv_value = (struct bt_arg *)map;
	bv->bv_type = B_VT_MAP;
}

/*
 * Print variables:	{ print(890); print(@map[, 8]); print(comm); }
 *
 * In this case the global variable 'map' is pointed at by `ba'
 * and '8' is represented by `btop'.
 */
void
stmt_print(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *btop, *ba = SLIST_FIRST(&bs->bs_args);
	struct bt_var *bv = ba->ba_value;
	struct map *map;
	size_t top = SIZE_T_MAX;

	assert(bs->bs_var == NULL);

	/* Parse optional `top' argument. */
	btop = SLIST_NEXT(ba, ba_next);
	if (btop != NULL) {
		assert(SLIST_NEXT(btop, ba_next) == NULL);
		top = ba2long(btop, dtev);
	}

	/* Static argument. */
	if (ba->ba_type != B_AT_VAR) {
		assert(btop == NULL);
		printf("%s\n", ba2str(ba, dtev));
		return;
	}

	map = (struct map *)bv->bv_value;
	if (map == NULL)
		return;

	debug("map=%p '%s' print (top=%d)\n", bv->bv_value, bv_name(bv), top);

	if (bv->bv_type == B_VT_MAP)
		map_print(map, top, bv_name(bv));
	else if (bv->bv_type == B_VT_HIST)
		hist_print((struct hist *)map, bv_name(bv));
	else
		printf("%s\n", ba2str(ba, dtev));
}

/*
 * Variable store: 	{ @var = 3; }
 *
 * In this case '3' is represented by `ba', the argument of a STORE
 * action.
 *
 * If the argument depends of the value of an event (builtin) or is
 * the result of an operation, its evaluation is stored in a new `ba'.
 */
void
stmt_store(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *ba = SLIST_FIRST(&bs->bs_args);
	struct bt_var *bv = bs->bs_var;

	assert(SLIST_NEXT(ba, ba_next) == NULL);

	switch (ba->ba_type) {
	case B_AT_STR:
		bv->bv_value = ba;
		bv->bv_type = B_VT_STR;
		break;
	case B_AT_LONG:
		bv->bv_value = ba;
		bv->bv_type = B_VT_LONG;
		break;
	case B_AT_BI_NSECS:
		bv->bv_value = ba_new(builtin_nsecs(dtev), B_AT_LONG);
		bv->bv_type = B_VT_LONG;
		break;
	case B_AT_OP_PLUS ... B_AT_OP_LOR:
		bv->bv_value = ba_new(ba2long(ba, dtev), B_AT_LONG);
		bv->bv_type = B_VT_LONG;
		break;
	case B_AT_FN_STR:
		bv->bv_value = ba_new(ba2str(ba, dtev), B_AT_STR);
		bv->bv_type = B_VT_STR;
		break;
	default:
		xabort("store not implemented for type %d", ba->ba_type);
	}

	debug("bv=%p var '%s' store (%p)\n", bv, bv_name(bv), bv->bv_value);
}

/*
 * String conversion	{ str($1); string($1, 3); }
 *
 * Since fn_str is currently only called in ba2str, *buf should be a pointer
 * to the static buffer provided by ba2str.
 */
struct bt_arg *
fn_str(struct bt_arg *ba, struct dt_evt *dtev, char *buf)
{
	struct bt_arg *arg, *index;
	ssize_t len = STRLEN;

	assert(ba->ba_type == B_AT_FN_STR);

	arg = (struct bt_arg*)ba->ba_value;
	assert(arg != NULL);

	index = SLIST_NEXT(arg, ba_next);
	if (index != NULL) {
		/* Should have only 1 optional argument. */
		assert(SLIST_NEXT(index, ba_next) == NULL);
		len = MINIMUM(ba2long(index, dtev) + 1, STRLEN);
	}

	/* All negative lengths behave the same as a zero length. */
	if (len < 1)
		return ba_new("", B_AT_STR);

	strlcpy(buf, ba2str(arg, dtev), len);
	return ba_new(buf, B_AT_STR);
}

/*
 * Expression test:	{ if (expr) stmt; }
 */
bool
stmt_test(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *ba;

	if (bs == NULL)
		return true;

	ba = SLIST_FIRST(&bs->bs_args);

	return baexpr2long(ba, dtev) != 0;
}

/*
 * Print time: 		{ time("%H:%M:%S"); }
 */
void
stmt_time(struct bt_stmt *bs, struct dt_evt *dtev)
{
	struct bt_arg *ba = SLIST_FIRST(&bs->bs_args);
	time_t time;
	struct tm *tm;
	char buf[64];

	assert(bs->bs_var == NULL);
	assert(ba->ba_type == B_AT_STR);
	assert(strlen(ba2str(ba, dtev)) < (sizeof(buf) - 1));

	time = builtin_gettime(dtev);
	tm = localtime(&time);
	strftime(buf, sizeof(buf), ba2str(ba, dtev), tm);
	printf("%s", buf);
}

/*
 * Set entries to 0:	{ zero(@map); }
 */
void
stmt_zero(struct bt_stmt *bs)
{
	struct bt_arg *ba = SLIST_FIRST(&bs->bs_args);
	struct bt_var *bv = ba->ba_value;
	struct map *map;

	assert(bs->bs_var == NULL);
	assert(ba->ba_type == B_AT_VAR);

	map = (struct map *)bv->bv_value;
	if (map == NULL)
		return;

	if (bv->bv_type != B_VT_MAP && bv->bv_type != B_VT_HIST)
		errx(1, "invalid variable type for zero(%s)", ba_name(ba));

	map_zero(map);

	debug("map=%p '%s' zero\n", map, bv_name(bv));
}

struct bt_arg *
ba_read(struct bt_arg *ba)
{
	struct bt_var *bv = ba->ba_value;

	assert(ba->ba_type == B_AT_VAR);

	debug("bv=%p read '%s' (%p)\n", bv, bv_name(bv), bv->bv_value);

	/* Handle map/hist access after clear(). */
	if (bv->bv_value == NULL)
		return &g_nullba;

	return bv->bv_value;
}

const char *
ba2hash(struct bt_arg *ba, struct dt_evt *dtev)
{
	static char buf[KLEN];
	char *hash;
	int l, len;

	buf[0] = '\0';
	l = snprintf(buf, sizeof(buf), "%s", ba2str(ba, dtev));
	if (l < 0 || (size_t)l > sizeof(buf)) {
		warn("string too long %d > %lu", l, sizeof(buf));
		return buf;
	}

	len = 0;
	while ((ba = SLIST_NEXT(ba, ba_next)) != NULL) {
		len += l;
		hash = buf + len;

		l = snprintf(hash, sizeof(buf) - len, ", %s", ba2str(ba, dtev));
		if (l < 0 || (size_t)l > (sizeof(buf) - len)) {
			warn("hash too long %d > %lu", l + len, sizeof(buf));
			break;
		}
	}

	return buf;
}

static unsigned long
next_pow2(unsigned long x)
{
	size_t i;

	x--;
	for (i = 0; i < (sizeof(x)  * 8) - 1; i++)
		x |= (x >> 1);

	return x + 1;
}

/*
 * Return the ceiling value the interval holding `ba' or NULL if it is
 * out of the (min, max) values.
 */
const char *
ba2bucket(struct bt_arg *ba, struct bt_arg *brange, struct dt_evt *dtev,
    long *pstep)
{
	static char buf[KLEN];
	long val, bucket;
	int l;

	val = ba2long(ba, dtev);
	if (brange == NULL)
		bucket = next_pow2(val);
	else {
		long min, max, step;

		assert(brange->ba_type == B_AT_LONG);
		min = ba2long(brange, NULL);

		brange = SLIST_NEXT(brange, ba_next);
		assert(brange->ba_type == B_AT_LONG);
		max = ba2long(brange, NULL);

		if ((val < min) || (val > max))
			return NULL;

		brange = SLIST_NEXT(brange, ba_next);
		assert(brange->ba_type == B_AT_LONG);
		step = ba2long(brange, NULL);

		bucket = ((val / step) + 1) * step;
		*pstep = step;
	}

	buf[0] = '\0';
	l = snprintf(buf, sizeof(buf), "%lu", bucket);
	if (l < 0 || (size_t)l > sizeof(buf)) {
		warn("string too long %d > %lu", l, sizeof(buf));
		return buf;
	}

	return buf;
}

/*
 * Evaluate the operation encoded in `ba' and return its result.
 */
long
baexpr2long(struct bt_arg *ba, struct dt_evt *dtev)
{
	static long recursions;
	struct bt_arg *lhs, *rhs;
	long lval, rval, result;

	if (++recursions >= __MAXOPERANDS)
		errx(1, "too many operands (>%d) in expression", __MAXOPERANDS);

	lhs = ba->ba_value;
	rhs = SLIST_NEXT(lhs, ba_next);

	lval = ba2long(lhs, dtev);
	if (rhs == NULL) {
		rval = 0;
	} else {
		assert(SLIST_NEXT(rhs, ba_next) == NULL);
		rval = ba2long(rhs, dtev);
	}

	switch (ba->ba_type) {
	case B_AT_OP_PLUS:
		result = lval + rval;
		break;
	case B_AT_OP_MINUS:
		result = lval - rval;
		break;
	case B_AT_OP_MULT:
		result = lval * rval;
		break;
	case B_AT_OP_DIVIDE:
		result = lval / rval;
		break;
	case B_AT_OP_BAND:
		result = lval & rval;
		break;
	case B_AT_OP_XOR:
		result = lval ^ rval;
		break;
	case B_AT_OP_BOR:
		result = lval | rval;
		break;
	case B_AT_OP_EQ:
		result = (lval == rval);
		break;
	case B_AT_OP_NE:
		result = (lval != rval);
		break;
	case B_AT_OP_LE:
		result = (lval <= rval);
		break;
	case B_AT_OP_LT:
		result = (lval < rval);
		break;
	case B_AT_OP_GE:
		result = (lval >= rval);
		break;
	case B_AT_OP_GT:
		result = (lval > rval);
		break;
	case B_AT_OP_LAND:
		result = (lval && rval);
		break;
	case B_AT_OP_LOR:
		result = (lval || rval);
		break;
	default:
		xabort("unsuported operation %d", ba->ba_type);
	}

	debug("ba=%p eval '%ld %s %ld = %d'\n", ba, lval, ba_name(ba),
	   rval, result);

	--recursions;

	return result;
}

const char *
ba_name(struct bt_arg *ba)
{
	switch (ba->ba_type) {
	case B_AT_NIL:
		return "0";
	case B_AT_VAR:
	case B_AT_MAP:
		break;
	case B_AT_BI_PID:
		return "pid";
	case B_AT_BI_TID:
		return "tid";
	case B_AT_BI_COMM:
		return "comm";
	case B_AT_BI_CPU:
		return "cpu";
	case B_AT_BI_NSECS:
		return "nsecs";
	case B_AT_BI_KSTACK:
		return "kstack";
	case B_AT_BI_USTACK:
		return "ustack";
	case B_AT_BI_ARG0:
		return "arg0";
	case B_AT_BI_ARG1:
		return "arg1";
	case B_AT_BI_ARG2:
		return "arg2";
	case B_AT_BI_ARG3:
		return "arg3";
	case B_AT_BI_ARG4:
		return "arg4";
	case B_AT_BI_ARG5:
		return "arg5";
	case B_AT_BI_ARG6:
		return "arg6";
	case B_AT_BI_ARG7:
		return "arg7";
	case B_AT_BI_ARG8:
		return "arg8";
	case B_AT_BI_ARG9:
		return "arg9";
	case B_AT_BI_ARGS:
		return "args";
	case B_AT_BI_RETVAL:
		return "retval";
	case B_AT_BI_PROBE:
		return "probe";
	case B_AT_FN_STR:
		return "str";
	case B_AT_OP_PLUS:
		return "+";
	case B_AT_OP_MINUS:
		return "-";
	case B_AT_OP_MULT:
		return "*";
	case B_AT_OP_DIVIDE:
		return "/";
	case B_AT_OP_BAND:
		return "&";
	case B_AT_OP_XOR:
		return "^";
	case B_AT_OP_BOR:
		return "|";
	case B_AT_OP_EQ:
		return "==";
	case B_AT_OP_NE:
		return "!=";
	case B_AT_OP_LE:
		return "<=";
	case B_AT_OP_LT:
		return "<";
	case B_AT_OP_GE:
		return ">=";
	case B_AT_OP_GT:
		return ">";
	case B_AT_OP_LAND:
		return "&&";
	case B_AT_OP_LOR:
		return "||";
	default:
		xabort("unsuported type %d", ba->ba_type);
	}

	assert(ba->ba_type == B_AT_VAR || ba->ba_type == B_AT_MAP);

	static char buf[64];
	size_t sz;
	int l;

	buf[0] = '@';
	buf[1] = '\0';
	sz = sizeof(buf) - 1;
	l = snprintf(buf+1, sz, "%s", bv_name(ba->ba_value));
	if (l < 0 || (size_t)l > sz) {
		warn("string too long %d > %zu", l, sz);
		return buf;
	}

	if (ba->ba_type == B_AT_MAP) {
		sz -= l;
		l = snprintf(buf+1+l, sz, "[%s]", ba_name(ba->ba_key));
		if (l < 0 || (size_t)l > sz) {
			warn("string too long %d > %zu", l, sz);
			return buf;
		}
	}

	return buf;
}

/*
 * Return the representation of `ba' as long.
 */
long
ba2long(struct bt_arg *ba, struct dt_evt *dtev)
{
	struct bt_var *bv;
	long val;

	switch (ba->ba_type) {
	case B_AT_LONG:
		val = (long)ba->ba_value;
		break;
	case B_AT_VAR:
		ba = ba_read(ba);
		val = (long)ba->ba_value;
		break;
	case B_AT_MAP:
		bv = ba->ba_value;
		/* Unitialized map */
		if (bv->bv_value == NULL)
			return 0;
		val = ba2long(map_get((struct map *)bv->bv_value,
		    ba2str(ba->ba_key, dtev)), dtev);
		break;
	case B_AT_NIL:
		val = 0L;
		break;
	case B_AT_BI_PID:
		val = dtev->dtev_pid;
		break;
	case B_AT_BI_TID:
		val = dtev->dtev_tid;
		break;
	case B_AT_BI_CPU:
		val = dtev->dtev_cpu;
		break;
	case B_AT_BI_NSECS:
		val = builtin_nsecs(dtev);
		break;
	case B_AT_BI_ARG0 ... B_AT_BI_ARG9:
		val = dtev->dtev_args[ba->ba_type - B_AT_BI_ARG0];
		break;
	case B_AT_BI_RETVAL:
		val = dtev->dtev_retval[0];
		break;
	case B_AT_BI_PROBE:
		val = dtev->dtev_pbn;
		break;
	case B_AT_OP_PLUS ... B_AT_OP_LOR:
		val = baexpr2long(ba, dtev);
		break;
	default:
		xabort("no long conversion for type %d", ba->ba_type);
	}

	return  val;
}

/*
 * Return the representation of `ba' as string.
 */
const char *
ba2str(struct bt_arg *ba, struct dt_evt *dtev)
{
	static char buf[STRLEN];
	struct bt_var *bv;
	struct dtioc_probe_info *dtpi;
	const char *str;

	buf[0] = '\0';
	switch (ba->ba_type) {
	case B_AT_STR:
		str = (const char *)ba->ba_value;
		break;
	case B_AT_LONG:
		snprintf(buf, sizeof(buf), "%ld",(long)ba->ba_value);
		str = buf;
		break;
	case B_AT_NIL:
		str = "";
		break;
	case B_AT_BI_KSTACK:
		str = builtin_stack(dtev, 1);
		break;
	case B_AT_BI_USTACK:
		str = builtin_stack(dtev, 0);
		break;
	case B_AT_BI_COMM:
		str = dtev->dtev_comm;
		break;
	case B_AT_BI_CPU:
		snprintf(buf, sizeof(buf), "%u", dtev->dtev_cpu);
		str = buf;
		break;
	case B_AT_BI_PID:
		snprintf(buf, sizeof(buf), "%d", dtev->dtev_pid);
		str = buf;
		break;
	case B_AT_BI_TID:
		snprintf(buf, sizeof(buf), "%d", dtev->dtev_tid);
		str = buf;
		break;
	case B_AT_BI_NSECS:
		snprintf(buf, sizeof(buf), "%llu", builtin_nsecs(dtev));
		str = buf;
		break;
	case B_AT_BI_ARG0 ... B_AT_BI_ARG9:
		str = builtin_arg(dtev, ba->ba_type);
		break;
	case B_AT_BI_RETVAL:
		snprintf(buf, sizeof(buf), "%ld", (long)dtev->dtev_retval[0]);
		str = buf;
		break;
	case B_AT_BI_PROBE:
		dtpi = dtpi_get_by_id(dtev->dtev_pbn);
		if (dtpi != NULL)
			snprintf(buf, sizeof(buf), "%s:%s:%s",
			    dtpi->dtpi_prov, dtpi_func(dtpi), dtpi->dtpi_name);
		else
			snprintf(buf, sizeof(buf), "%u", dtev->dtev_pbn);
		str = buf;
		break;
	case B_AT_MAP:
		bv = ba->ba_value;
		/* Unitialized map */
		if (bv->bv_value == NULL) {
			str = buf;
			break;
		}
		str = ba2str(map_get((struct map *)bv->bv_value,
		    ba2str(ba->ba_key, dtev)), dtev);
		break;
	case B_AT_VAR:
		str = ba2str(ba_read(ba), dtev);
		break;
	case B_AT_FN_STR:
		str = (const char*)(fn_str(ba, dtev, buf))->ba_value;
		break;
	case B_AT_OP_PLUS ... B_AT_OP_LOR:
		snprintf(buf, sizeof(buf), "%ld", ba2long(ba, dtev));
		str = buf;
		break;
	case B_AT_MF_COUNT:
	case B_AT_MF_MAX:
	case B_AT_MF_MIN:
	case B_AT_MF_SUM:
		assert(0);
		break;
	default:
		xabort("no string conversion for type %d", ba->ba_type);
	}

	return str;
}

/*
 * Return dt(4) flags indicating which data should be recorded by the
 * kernel, if any, for a given `ba'.
 */
int
ba2dtflags(struct bt_arg *ba)
{
	struct bt_arg *bval;
	int flags = 0;

	do {
		if (ba->ba_type == B_AT_MAP)
			bval = ba->ba_key;
		else
			bval = ba;

		switch (bval->ba_type) {
		case B_AT_STR:
		case B_AT_LONG:
		case B_AT_VAR:
	    	case B_AT_HIST:
		case B_AT_NIL:
			break;
		case B_AT_BI_KSTACK:
			flags |= DTEVT_KSTACK;
			break;
		case B_AT_BI_USTACK:
			flags |= DTEVT_USTACK;
			break;
		case B_AT_BI_COMM:
			flags |= DTEVT_EXECNAME;
			break;
		case B_AT_BI_CPU:
		case B_AT_BI_PID:
		case B_AT_BI_TID:
		case B_AT_BI_NSECS:
			break;
		case B_AT_BI_ARG0 ... B_AT_BI_ARG9:
			flags |= DTEVT_FUNCARGS;
			break;
		case B_AT_BI_RETVAL:
		case B_AT_BI_PROBE:
			break;
		case B_AT_MF_COUNT:
		case B_AT_MF_MAX:
		case B_AT_MF_MIN:
		case B_AT_MF_SUM:
		case B_AT_FN_STR:
		case B_AT_OP_PLUS ... B_AT_OP_LOR:
			break;
		default:
			xabort("invalid argument type %d", bval->ba_type);
		}
	} while ((ba = SLIST_NEXT(ba, ba_next)) != NULL);

	return flags;
}

long
bacmp(struct bt_arg *a, struct bt_arg *b)
{
	assert(a->ba_type == b->ba_type);
	assert(a->ba_type == B_AT_LONG);

	return ba2long(a, NULL) - ba2long(b, NULL);
}

__dead void
xabort(const char *fmt, ...)
{
	va_list ap;

	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);

	fprintf(stderr, "\n");
	abort();
}

void
debug(const char *fmt, ...)
{
	va_list ap;

	if (verbose < 2)
		return;

	fprintf(stderr, "debug: ");

	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);
}

void
debugx(const char *fmt, ...)
{
	va_list ap;

	if (verbose < 2)
		return;

	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);
}

void
debug_dump_term(struct bt_arg *ba)
{
	switch (ba->ba_type) {
	case B_AT_LONG:
		debugx("%s", ba2str(ba, NULL));
		break;
	case B_AT_OP_PLUS ... B_AT_OP_LOR:
		debug_dump_expr(ba);
		break;
	default:
		debugx("%s", ba_name(ba));
	}
}

void
debug_dump_expr(struct bt_arg *ba)
{
	struct bt_arg *lhs, *rhs;

	lhs = ba->ba_value;
	rhs = SLIST_NEXT(lhs, ba_next);

	/* Left */
	debug_dump_term(lhs);

	/* Right */
	if (rhs != NULL) {
		debugx(" %s ", ba_name(ba));
		debug_dump_term(rhs);
	} else {
		if (ba->ba_type != B_AT_OP_NE)
			debugx(" %s NULL", ba_name(ba));
	}
}

void
debug_dump_filter(struct bt_rule *r)
{
	struct bt_stmt *bs;

	if (verbose < 2)
		return;

	if (r->br_filter == NULL) {
		debugx("\n");
		return;
	}

	bs = r->br_filter->bf_condition;

	debugx(" /");
	debug_dump_expr(SLIST_FIRST(&bs->bs_args));
	debugx("/\n");
}

const char *
debug_probe_name(struct bt_probe *bp)
{
	static char buf[64];

	if (verbose < 2)
		return "";

	if (bp->bp_type == B_PT_BEGIN)
		return "BEGIN";

	if (bp->bp_type == B_PT_END)
		return "END";

	assert(bp->bp_type == B_PT_PROBE);

	if (bp->bp_rate) {
		snprintf(buf, sizeof(buf), "%s:%s:%u", bp->bp_prov,
		    bp->bp_unit, bp->bp_rate);
	} else {
		snprintf(buf, sizeof(buf), "%s:%s:%s", bp->bp_prov,
		    bp->bp_unit, bp->bp_name);
	}

	return buf;
}