Implement linear and power-of-two histograms: hist() and lhist() keywords.

This is built on top of maps which are currently built on top of RB-trees.
Improvements are welcome!  For example the use of a hashing table as pointed
by espie@.

The following one-liner produce an histogram of power-of-two values returned
by the read(2) syscall:

btrace 'syscall:read:return { @bytes = hist(retval); }'
^C
@bytes:
[0]               19 |@@@@@@@@@@@@@@@@@@@@@@@@@@                          |
[1]               26 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                |
[1, 2)             1 |@                                                   |
[2, 4)            13 |@@@@@@@@@@@@@@@@@@                                  |
[4, 8)             4 |@@@@@                                               |
[8, 16)            3 |@@@@                                                |
[16, 32)           1 |@                                                   |
[32, 64)           8 |@@@@@@@@@@@                                         |
[64, 128)         14 |@@@@@@@@@@@@@@@@@@@                                 |
[128, 256)         7 |@@@@@@@@@                                           |
[256, 512)        37 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[512, 1K)          1 |@                                                   |
[1K, 2K)          10 |@@@@@@@@@@@@@@                                      |
[2K, 4K)          11 |@@@@@@@@@@@@@@@                                     |
[8K, 16K)          1 |@                                                   |

7 files changed, 359 insertions, 37 deletions

diff --git a/usr.sbin/btrace/TODO b/usr.sbin/btrace/TODO
index bd583eee7b2..f2e8b2de46f 100644
--- a/usr.sbin/btrace/TODO
+++ b/usr.sbin/btrace/TODO
@@ -8,8 +8,6 @@ Missing language features:
 - scratch variable ($name)
 - `args', tracepoint arguments support (requires kernel work)
 - str(args->buf, args->count)
-- @ = hist(x)
-- @ = lhist(x, min, max, step)
 - 'argv'
 - $1 support
 
diff --git a/usr.sbin/btrace/bt.5 b/usr.sbin/btrace/bt.5
index acef0d08400..2672a3d1bc2 100644
--- a/usr.sbin/btrace/bt.5
+++ b/usr.sbin/btrace/bt.5
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: bt.5,v 1.5 2020/04/23 18:36:51 mpi Exp $
+.\"	$OpenBSD: bt.5,v 1.6 2020/07/11 14:52:14 mpi Exp $
 .\"
 .\" Copyright (c) 2019 Martin Pieuchot <mpi@openbsd.org>
 .\"
@@ -14,7 +14,7 @@
 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 .\"
-.Dd $Mdocdate: April 23 2020 $
+.Dd $Mdocdate: July 11 2020 $
 .Dt BT 5
 .Os
 .Sh NAME
@@ -111,7 +111,7 @@ Thread ID of the current thread
 .Pp
 Functions:
 .Pp
-.Bl -tag -width "delete(@map[key])" -compact
+.Bl -tag -width "lhist(value, min, max, step)"
 .It Fn clear "@map"
 Delete all (key, value) pairs from
 .Va @map
@@ -122,6 +122,20 @@ from
 .Va @map
 .It Fn exit
 Terminate execution with exit code 0
+.It Fn hist "value"
+Increment the bucket corresponding  to
+.Va value
+in a power-of-two histogram
+.It Fn lhist "value" "min" "max" "step"
+Increment the bucket corresponding  to
+.Va value
+in the linear histogram spawning between the positive value
+.Va min
+and
+.Va max
+with buckets of
+.Va step
+size.
 .It Fn print "@map"
 Print all pairs from
 .Va @map
diff --git a/usr.sbin/btrace/bt_parse.y b/usr.sbin/btrace/bt_parse.y
index e8530fd1615..52962cd1ff0 100644
--- a/usr.sbin/btrace/bt_parse.y
+++ b/usr.sbin/btrace/bt_parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bt_parse.y,v 1.15 2020/07/03 17:58:09 mpi Exp $	*/
+/*	$OpenBSD: bt_parse.y,v 1.16 2020/07/11 14:52:14 mpi Exp $	*/
 
 /*
  * Copyright (c) 2019 - 2020 Martin Pieuchot <mpi@openbsd.org>
@@ -69,6 +69,8 @@ struct bt_arg	*bm_get(const char *, struct bt_arg *);
 struct bt_stmt	*bm_set(const char *, struct bt_arg *, struct bt_arg *);
 struct bt_stmt	*bm_op(enum bt_action, struct bt_arg *, struct bt_arg *);
 
+struct bt_stmt	*bh_inc(const char *, struct bt_arg *, struct bt_arg *);
+
 /*
  * Lexer
  */
@@ -102,13 +104,13 @@ static int	 yylex(void);
 /* Builtins */
 %token	BUILTIN PID TID
 /* Functions and Map operators */
-%token  F_DELETE FUNC0 FUNC1 FUNCN MOP0 MOP1
+%token  F_DELETE FUNC0 FUNC1 FUNCN OP1 OP4 MOP0 MOP1
 %token	<v.string>	STRING CSTRING
 %token	<v.number>	NUMBER
 
 %type	<v.string>	gvar
 %type	<v.i>		filterval oper builtin
-%type	<v.i>		BUILTIN F_DELETE FUNC0 FUNC1 FUNCN MOP0 MOP1
+%type	<v.i>		BUILTIN F_DELETE FUNC0 FUNC1 FUNCN OP1 OP4 MOP0 MOP1
 %type	<v.probe>	probe
 %type	<v.filter>	predicate
 %type	<v.stmt>	action stmt stmtlist
@@ -196,6 +198,8 @@ stmt		: ';' NL			{ $$ = NULL; }
 		| FUNC1 '(' expr ')'		{ $$ = bs_new($1, $3, NULL); }
 		| FUNC0 '(' ')'			{ $$ = bs_new($1, NULL, NULL); }
 		| F_DELETE '(' map ')'		{ $$ = bm_op($1, $3, NULL); }
+		| gvar '=' OP1 '(' expr ')'	{ $$ = bh_inc($1, $5, NULL); }
+		| gvar '=' OP4 '(' expr ',' vargs ')' {$$ = bh_inc($1, $5, $7);}
 		;
 
 stmtlist	: stmt
@@ -467,6 +471,60 @@ bm_get(const char *mname, struct bt_arg *mkey)
 	return ba;
 }
 
+/*
+ * Histograms implemented using associative arrays (maps).  In the case
+ * of linear histograms `ba_key' points to a list of (min, max, step)
+ * necessary to "bucketize" any value.
+ */
+struct bt_stmt *
+bh_inc(const char *hname, struct bt_arg *hval, struct bt_arg *hrange)
+{
+	struct bt_arg *ba;
+	struct bt_var *bv;
+
+	if (hrange == NULL) {
+		/* Power-of-2 histogram */
+	} else {
+		long min, max;
+		int count = 0;
+
+		/* Linear histogram */
+		for (ba = hrange; ba != NULL; ba = SLIST_NEXT(ba, ba_next)) {
+			if (++count > 3)
+				yyerror("too many arguments");
+			if (ba->ba_type != B_AT_LONG)
+				yyerror("type invalid");
+
+			switch (count) {
+			case 1:
+				min = (long)ba->ba_value;
+				if (min >= 0)
+					break;
+				yyerror("negative minium");
+			case 2:
+				max = (long)ba->ba_value;
+				if (max > min)
+					break;
+				yyerror("maximum smaller than minium (%d < %d)",
+				    max,  min);
+			case 3:
+				break;
+			default:
+				assert(0);
+			}
+		}
+		if (count < 3)
+			yyerror("%d missing arguments", 3 - count);
+	}
+
+	bv = bv_find(hname);
+	if (bv == NULL)
+		bv = bv_new(hname);
+	ba = ba_new(bv, B_AT_HIST);
+	ba->ba_key = hrange;
+	return bs_new(B_AC_BUCKETIZE, ba, (struct bt_var *)hval);
+}
+
 struct keyword {
 	const char	*word;
 	int		 token;
@@ -503,13 +561,15 @@ lookup(char *s)
 		{ "cpu",	BUILTIN,	B_AT_BI_CPU },
 		{ "delete",	F_DELETE,	B_AC_DELETE },
 		{ "exit",	FUNC0,		B_AC_EXIT },
+		{ "hist",	OP1,		0 },
 		{ "hz",		HZ,		0 },
 		{ "kstack",	BUILTIN,	B_AT_BI_KSTACK },
+		{ "lhist",	OP4,		0 },
 		{ "max",	MOP1,		B_AT_MF_MAX },
 		{ "min",	MOP1,		B_AT_MF_MIN },
 		{ "nsecs",	BUILTIN,	B_AT_BI_NSECS },
 		{ "pid",	PID,		0 /*B_AT_BI_PID*/ },
-		{ "print",	FUNCN,	B_AC_PRINT },
+		{ "print",	FUNCN,		B_AC_PRINT },
 		{ "printf",	FUNCN,		B_AC_PRINTF },
 		{ "retval",	BUILTIN,	B_AT_BI_RETVAL },
 		{ "sum",	MOP1,		B_AT_MF_SUM },
diff --git a/usr.sbin/btrace/bt_parser.h b/usr.sbin/btrace/bt_parser.h
index 3ad26b76309..0eaa65a07eb 100644
--- a/usr.sbin/btrace/bt_parser.h
+++ b/usr.sbin/btrace/bt_parser.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bt_parser.h,v 1.7 2020/04/23 18:36:51 mpi Exp $	*/
+/*	$OpenBSD: bt_parser.h,v 1.8 2020/07/11 14:52:14 mpi Exp $	*/
 
 /*
  * Copyright (c) 2019-2020 Martin Pieuchot <mpi@openbsd.org>
@@ -101,12 +101,13 @@ struct bt_var {
 struct bt_arg {
 	SLIST_ENTRY(bt_arg)	 ba_next;
 	void			*ba_value;
-	struct bt_arg		*ba_key;	/* key for maps */
+	struct bt_arg		*ba_key;	/* key for maps/histograms */
 	enum  bt_argtype {
 		B_AT_STR = 1,			/* C-style string */
 		B_AT_LONG,			/* Number (integer) */
 		B_AT_VAR,			/* global variable (@var) */
 		B_AT_MAP,			/* global map (@map[]) */
+		B_AT_HIST,			/* histogram */
 
 		B_AT_BI_PID,
 		B_AT_BI_TID,
@@ -140,6 +141,8 @@ struct bt_arg {
 	}			 ba_type;
 };
 
+#define BA_INITIALIZER(v, t)	{ { NULL }, (void *)(v), NULL, (t) }
+
 /*
  * Statements define what should be done with each event recorded
  * by the corresponding probe.
@@ -149,13 +152,14 @@ struct bt_stmt {
 	struct bt_var		*bs_var;	/* for STOREs */
 	SLIST_HEAD(, bt_arg)	 bs_args;
 	enum bt_action {
-		B_AC_STORE = 1,			/* @a = 3 */
-		B_AC_INSERT,			/* @map[key] = 42 */
+		B_AC_BUCKETIZE,			/* @h = hist(42) */
 		B_AC_CLEAR,			/* clear(@map) */
 		B_AC_DELETE,			/* delete(@map[key]) */
 		B_AC_EXIT,			/* exit() */
+		B_AC_INSERT,			/* @map[key] = 42 */
 		B_AC_PRINT,			/* print(@map, 10) */
 		B_AC_PRINTF,			/* printf("hello!\n") */
+		B_AC_STORE,			/* @a = 3 */
 		B_AC_TIME,			/* time("%H:%M:%S  ") */
 		B_AC_ZERO,			/* zero(@map) */
 	}			 bs_act;
diff --git a/usr.sbin/btrace/btrace.c b/usr.sbin/btrace/btrace.c
index 3f14d54a6cf..63fa20db2a2 100644
--- a/usr.sbin/btrace/btrace.c
+++ b/usr.sbin/btrace/btrace.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: btrace.c,v 1.20 2020/07/04 10:16:15 mpi Exp $ */
+/*	$OpenBSD: btrace.c,v 1.21 2020/07/11 14:52:14 mpi Exp $ */
 
 /*
  * Copyright (c) 2019 - 2020 Martin Pieuchot <mpi@openbsd.org>
@@ -40,6 +40,9 @@
 #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.
@@ -77,6 +80,7 @@ void			 rule_printmaps(struct bt_rule *);
 uint64_t		 builtin_nsecs(struct dt_evt *);
 const char		*builtin_kstack(struct dt_evt *);
 const char		*builtin_arg(struct dt_evt *, enum bt_argtype);
+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 *);
@@ -86,6 +90,8 @@ 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 *);
+const char		*ba2bucket(struct bt_arg *, struct bt_arg *,
+			     struct dt_evt *, long *);
 int			 ba2dtflags(struct bt_arg *);
 
 /*
@@ -330,8 +336,10 @@ rules_do(int fd)
 
 		rlen = read(fd, devtbuf, sizeof(devtbuf) - 1);
 		if (rlen == -1) {
-			if (errno == EINTR && quit_pending)
+			if (errno == EINTR && quit_pending) {
+				printf("\n");
 				break;
+			}
 			err(1, "read");
 		}
 
@@ -515,11 +523,8 @@ rule_eval(struct bt_rule *r, struct dt_evt *dtev)
 
 	SLIST_FOREACH(bs, &r->br_action, bs_next) {
 		switch (bs->bs_act) {
-		case B_AC_STORE:
-			stmt_store(bs, dtev);
-			break;
-		case B_AC_INSERT:
-			stmt_insert(bs, dtev);
+		case B_AC_BUCKETIZE:
+			stmt_bucketize(bs, dtev);
 			break;
 		case B_AC_CLEAR:
 			stmt_clear(bs);
@@ -530,12 +535,18 @@ rule_eval(struct bt_rule *r, struct dt_evt *dtev)
 		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_TIME:
 			stmt_time(bs, dtev);
 			break;
@@ -559,13 +570,16 @@ rule_printmaps(struct bt_rule *r)
 		SLIST_FOREACH(ba, &bs->bs_args, ba_next) {
 			struct bt_var *bv = ba->ba_value;
 
-			if (ba->ba_type != B_AT_MAP)
+			if (ba->ba_type != B_AT_MAP && ba->ba_type != B_AT_HIST)
 				continue;
 
 			if (bv->bv_value != NULL) {
 				struct map *map = (struct map *)bv->bv_value;
 
-				map_print(map, SIZE_T_MAX, bv_name(bv));
+				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;
 			}
@@ -633,6 +647,37 @@ builtin_arg(struct dt_evt *dtev, enum bt_argtype dat)
 	return buf;
 }
 
+/*
+ * 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);
+}
+
 
 /*
  * Empty a map:		{ clear(@map); }
@@ -698,7 +743,7 @@ stmt_insert(struct bt_stmt *bs, struct dt_evt *dtev)
 	    bv_name(bv), bkey, hash, bval);
 
 	bv->bv_value = (struct bt_arg *)map_insert((struct map *)bv->bv_value,
-	    hash, bval, ba2long(bval, dtev));
+	    hash, bval, dtev);
 }
 
 /*
@@ -840,6 +885,63 @@ ba2hash(struct bt_arg *ba, struct dt_evt *dtev)
 	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[256];
+	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;
+	}
+
+	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;
+}
+
 /*
  * Helper to evaluate the operation encoded in `ba' and return its
  * result.
@@ -906,7 +1008,7 @@ ba2long(struct bt_arg *ba, struct dt_evt *dtev)
 		val = builtin_nsecs(dtev);
 		break;
 	case B_AT_BI_RETVAL:
-		val = (long)dtev->dtev_sysretval[0];
+		val = dtev->dtev_sysretval[0];
 		break;
 	case B_AT_OP_ADD ... B_AT_OP_DIVIDE:
 		val = baexpr2long(ba, dtev);
@@ -1010,6 +1112,7 @@ ba2dtflags(struct bt_arg *ba)
 		case B_AT_STR:
 		case B_AT_LONG:
 		case B_AT_VAR:
+	    	case B_AT_HIST:
 			break;
 		case B_AT_BI_KSTACK:
 			flags |= DTEVT_KSTACK;
@@ -1029,7 +1132,6 @@ ba2dtflags(struct bt_arg *ba)
 			flags |= DTEVT_FUNCARGS;
 			break;
 		case B_AT_BI_RETVAL:
-			flags |= DTEVT_RETVAL;
 			break;
 		case B_AT_MF_COUNT:
 		case B_AT_MF_MAX:
diff --git a/usr.sbin/btrace/btrace.h b/usr.sbin/btrace/btrace.h
index 27f4de57843..cd9001a44d8 100644
--- a/usr.sbin/btrace/btrace.h
+++ b/usr.sbin/btrace/btrace.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: btrace.h,v 1.5 2020/07/04 10:16:15 mpi Exp $ */
+/*	$OpenBSD: btrace.h,v 1.6 2020/07/11 14:52:14 mpi Exp $ */
 
 /*
  * Copyright (c) 2019 - 2020 Martin Pieuchot <mpi@openbsd.org>
@@ -40,13 +40,16 @@ int			 kelf_snprintsym(char *, size_t, unsigned long);
 
 /* map.c */
 struct map;
+struct hist;
 void			 map_clear(struct map *);
 void			 map_delete(struct map *, const char *);
 struct bt_arg		*map_get(struct map *, const char *);
 struct map		*map_insert(struct map *, const char *, struct bt_arg *,
-			    long);
+			    struct dt_evt *);
 void			 map_print(struct map *, size_t, const char *);
 void			 map_zero(struct map *);
+struct hist		*hist_increment(struct hist *, const char *, long);
+void			 hist_print(struct hist *, const char *);
 
 /* printf.c */
 int			 stmt_printf(struct bt_stmt *, struct dt_evt *);
diff --git a/usr.sbin/btrace/map.c b/usr.sbin/btrace/map.c
index a897e6322fb..86dca1bc86c 100644
--- a/usr.sbin/btrace/map.c
+++ b/usr.sbin/btrace/map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: map.c,v 1.7 2020/07/04 10:16:15 mpi Exp $ */
+/*	$OpenBSD: map.c,v 1.8 2020/07/11 14:52:14 mpi Exp $ */
 
 /*
  * Copyright (c) 2020 Martin Pieuchot <mpi@openbsd.org>
@@ -121,9 +121,11 @@ map_get(struct map *map, const char *key)
 }
 
 struct map *
-map_insert(struct map *map, const char *key, struct bt_arg *bval, long val)
+map_insert(struct map *map, const char *key, struct bt_arg *bval,
+    struct dt_evt *dtev)
 {
 	struct mentry *mep;
+	long val;
 
 	if (map == NULL) {
 		map = calloc(1, sizeof(struct map));
@@ -140,7 +142,7 @@ map_insert(struct map *map, const char *key, struct bt_arg *bval, long val)
 		break;
 	case B_AT_BI_RETVAL:
 		free(mep->mval);
-		mep->mval = ba_new(val, B_AT_LONG);
+		mep->mval = ba_new(ba2long(bval, dtev), B_AT_LONG);
 		break;
 	case B_AT_MF_COUNT:
 		if (mep->mval == NULL)
@@ -153,21 +155,21 @@ map_insert(struct map *map, const char *key, struct bt_arg *bval, long val)
 		if (mep->mval == NULL)
 			mep->mval = ba_new(0, B_AT_LONG);
 		val = (long)mep->mval->ba_value;
-		val = MAX(val, ba2long(bval->ba_value, NULL));
+		val = MAX(val, ba2long(bval->ba_value, dtev));
 		mep->mval->ba_value = (void *)val;
 		break;
 	case B_AT_MF_MIN:
 		if (mep->mval == NULL)
 			mep->mval = ba_new(0, B_AT_LONG);
 		val = (long)mep->mval->ba_value;
-		val = MIN(val, ba2long(bval->ba_value, NULL));
+		val = MIN(val, ba2long(bval->ba_value, dtev));
 		mep->mval->ba_value = (void *)val;
 		break;
 	case B_AT_MF_SUM:
 		if (mep->mval == NULL)
 			mep->mval = ba_new(0, B_AT_LONG);
 		val = (long)mep->mval->ba_value;
-		val += ba2long(bval->ba_value, NULL);
+		val += ba2long(bval->ba_value, dtev);
 		mep->mval->ba_value = (void *)val;
 		break;
 	default:
@@ -177,12 +179,12 @@ map_insert(struct map *map, const char *key, struct bt_arg *bval, long val)
 	return map;
 }
 
-static struct bt_arg nullba = { {NULL }, (void *)0, NULL, B_AT_LONG };
-static struct bt_arg maxba = { { NULL }, (void *)LONG_MAX, NULL, B_AT_LONG };
+static struct bt_arg nullba = BA_INITIALIZER(0, B_AT_LONG);
+static struct bt_arg maxba = BA_INITIALIZER(LONG_MAX, B_AT_LONG);
 
 /* Print at most `top' entries of the map ordered by value. */
 void
-map_print(struct map *map, size_t top, const char *mapname)
+map_print(struct map *map, size_t top, const char *name)
 {
 	struct mentry *mep, *mcur;
 	struct bt_arg *bhigh, *bprev;
@@ -205,7 +207,7 @@ map_print(struct map *map, size_t top, const char *mapname)
 		}
 		if (mcur == NULL)
 			break;
-		printf("@%s[%s]: %s\n", mapname, mcur->mkey,
+		printf("@%s[%s]: %s\n", name, mcur->mkey,
 		    ba2str(mcur->mval, NULL));
 		bprev = mcur->mval;
 	}
@@ -221,3 +223,142 @@ map_zero(struct map *map)
 		mep->mval->ba_type = B_AT_LONG;
 	}
 }
+
+/*
+ * Histogram implemmented with map.
+ */
+
+struct hist {
+	struct map	hmap;
+	int		hstep;
+};
+
+struct hist *
+hist_increment(struct hist *hist, const char *key, long step)
+{
+	static struct bt_arg incba = BA_INITIALIZER(NULL, B_AT_MF_COUNT);
+
+	if (hist == NULL) {
+		hist = calloc(1, sizeof(struct hist));
+		if (hist == NULL)
+			err(1, "hist: calloc");
+		hist->hstep = step;
+	}
+	assert(hist->hstep == step);
+
+	return (struct hist *)map_insert(&hist->hmap, key, &incba, NULL);
+}
+
+long
+hist_get_bin_suffix(long bin, char **suffix)
+{
+#define GIGA	(MEGA * 1024)
+#define MEGA	(KILO * 1024)
+#define KILO	(1024)
+
+	*suffix = "";
+	if (bin >= GIGA) {
+		bin /= GIGA;
+		*suffix = "G";
+	}
+	if (bin >= MEGA) {
+		bin /= MEGA;
+		*suffix = "M";
+	}
+	if (bin >= KILO) {
+		bin /= KILO;
+		*suffix = "K";
+	}
+
+	return bin;
+#undef MEGA
+#undef KILO
+}
+
+/*
+ * Print bucket header where `upb' is the upper bound of the interval
+ * and `hstep' the width of the interval.
+ */
+static inline int
+hist_print_bucket(char *buf, size_t buflen, long upb, long hstep)
+{
+	int l;
+
+	if (hstep != 0) {
+		/* Linear histogram */
+		l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb);
+	} else {
+		/* Power-of-two histogram */
+		if (upb < 0) {
+			l = snprintf(buf, buflen, "(..., 0)");
+		} else if (upb < 2) {
+			l = snprintf(buf, buflen, "[%lu]", upb);
+		} else {
+			long lob = upb / 2;
+			char *lsuf, *usuf;
+
+			upb = hist_get_bin_suffix(upb, &usuf);
+			lob = hist_get_bin_suffix(lob, &lsuf);
+
+			l = snprintf(buf, buflen, "[%lu%s, %lu%s)",
+			    lob, lsuf, upb, usuf);
+		}
+	}
+
+	if (l < 0 || (size_t)l > buflen)
+		warn("string too long %d > %lu", l, sizeof(buf));
+
+	return l;
+}
+
+void
+hist_print(struct hist *hist, const char *name)
+{
+	struct map *map = &hist->hmap;
+	static char buf[80];
+	struct mentry *mep, *mcur;
+	long bmin, bprev, bin, val, max = 0;
+	int i, l, length = 52;
+
+	if (map == NULL)
+		return;
+
+	bprev = 0;
+	RB_FOREACH(mep, map, map) {
+		val = ba2long(mep->mval, NULL);
+		if (val > max)
+			max = val;
+	}
+	printf("@%s:\n", name);
+
+	/*
+	 * Sort by ascending key.
+	 */
+	bprev = -1;
+	for (;;) {
+		mcur = NULL;
+		bmin = LONG_MAX;
+
+		RB_FOREACH(mep, map, map) {
+			bin = atol(mep->mkey);
+			if ((bin <= bmin) && (bin > bprev)) {
+				mcur = mep;
+				bmin = bin;
+			}
+		}
+		if (mcur == NULL)
+			break;
+
+		bin = atol(mcur->mkey);
+		val = ba2long(mcur->mval, NULL);
+		i = (length * val) / max;
+		l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep);
+		snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|",
+		    20 - l, val,
+		    i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@",
+		    length - i, "");
+		printf("%s\n", buf);
+
+		bprev = bin;
+	}
+}