xref: /openbsd/usr.sbin/btrace/map.c (revision 3cab2bb3) 
1 /*	$OpenBSD: map.c,v 1.9 2020/08/07 14:04:59 mpi Exp $ */
2 
3 /*
4  * Copyright (c) 2020 Martin Pieuchot <mpi@openbsd.org>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 
19 /*
20  * Associative array implemented with RB-Tree.
21  */
22 
23 #include <sys/queue.h>
24 #include <sys/tree.h>
25 
26 #include <assert.h>
27 #include <err.h>
28 #include <limits.h>
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32 
33 #include "bt_parser.h"
34 #include "btrace.h"
35 
36 #ifndef MIN
37 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
38 #endif
39 
40 #ifndef MAX
41 #define	MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
42 #endif
43 
44 RB_HEAD(map, mentry);
45 
46 struct mentry {
47 	RB_ENTRY(mentry)	 mlink;
48 	char			 mkey[KLEN];
49 	struct bt_arg		*mval;
50 };
51 
52 int		 mcmp(struct mentry *, struct mentry *);
53 struct mentry	*mget(struct map *, const char *);
54 
55 RB_GENERATE(map, mentry, mlink, mcmp);
56 
57 int
58 mcmp(struct mentry *me0, struct mentry *me1)
59 {
60 	return strncmp(me0->mkey, me1->mkey, KLEN - 1);
61 }
62 
63 struct mentry *
64 mget(struct map *map, const char *key)
65 {
66 	struct mentry me, *mep;
67 
68 	strlcpy(me.mkey, key, KLEN);
69 	mep = RB_FIND(map, map, &me);
70 	if (mep == NULL) {
71 		mep = calloc(1, sizeof(struct mentry));
72 		if (mep == NULL)
73 			err(1, "mentry: calloc");
74 
75 		strlcpy(mep->mkey, key, KLEN);
76 		RB_INSERT(map, map, mep);
77 	}
78 
79 	return mep;
80 }
81 
82 void
83 map_clear(struct map *map)
84 {
85 	struct mentry *mep;
86 
87 	while ((mep = RB_MIN(map, map)) != NULL) {
88 		RB_REMOVE(map, map, mep);
89 		free(mep);
90 	}
91 
92 	assert(RB_EMPTY(map));
93 	free(map);
94 }
95 
96 void
97 map_delete(struct map *map, const char *key)
98 {
99 	struct mentry me, *mep;
100 
101 	strlcpy(me.mkey, key, KLEN);
102 	mep = RB_FIND(map, map, &me);
103 	if (mep != NULL) {
104 		RB_REMOVE(map, map, mep);
105 		free(mep);
106 	}
107 }
108 
109 struct bt_arg *
110 map_get(struct map *map, const char *key)
111 {
112 	struct mentry *mep;
113 
114 	mep = mget(map, key);
115 	if (mep->mval == NULL)
116 		mep->mval = ba_new(0, B_AT_LONG);
117 
118 	return mep->mval;
119 }
120 
121 struct map *
122 map_insert(struct map *map, const char *key, struct bt_arg *bval,
123     struct dt_evt *dtev)
124 {
125 	struct mentry *mep;
126 	long val;
127 
128 	if (map == NULL) {
129 		map = calloc(1, sizeof(struct map));
130 		if (map == NULL)
131 			err(1, "map: calloc");
132 	}
133 
134 	mep = mget(map, key);
135 	switch (bval->ba_type) {
136 	case B_AT_STR:
137 	case B_AT_LONG:
138 		free(mep->mval);
139 		mep->mval = bval;
140 		break;
141 	case B_AT_BI_RETVAL:
142 		free(mep->mval);
143 		mep->mval = ba_new(ba2long(bval, dtev), B_AT_LONG);
144 		break;
145 	case B_AT_MF_COUNT:
146 		if (mep->mval == NULL)
147 			mep->mval = ba_new(0, B_AT_LONG);
148 		val = (long)mep->mval->ba_value;
149 		val++;
150 		mep->mval->ba_value = (void *)val;
151 		break;
152 	case B_AT_MF_MAX:
153 		if (mep->mval == NULL)
154 			mep->mval = ba_new(0, B_AT_LONG);
155 		val = (long)mep->mval->ba_value;
156 		val = MAX(val, ba2long(bval->ba_value, dtev));
157 		mep->mval->ba_value = (void *)val;
158 		break;
159 	case B_AT_MF_MIN:
160 		if (mep->mval == NULL)
161 			mep->mval = ba_new(0, B_AT_LONG);
162 		val = (long)mep->mval->ba_value;
163 		val = MIN(val, ba2long(bval->ba_value, dtev));
164 		mep->mval->ba_value = (void *)val;
165 		break;
166 	case B_AT_MF_SUM:
167 		if (mep->mval == NULL)
168 			mep->mval = ba_new(0, B_AT_LONG);
169 		val = (long)mep->mval->ba_value;
170 		val += ba2long(bval->ba_value, dtev);
171 		mep->mval->ba_value = (void *)val;
172 		break;
173 	default:
174 		errx(1, "no insert support for type %d", bval->ba_type);
175 	}
176 
177 	return map;
178 }
179 
180 static struct bt_arg nullba = BA_INITIALIZER(0, B_AT_LONG);
181 static struct bt_arg maxba = BA_INITIALIZER(LONG_MAX, B_AT_LONG);
182 
183 /* Print at most `top' entries of the map ordered by value. */
184 void
185 map_print(struct map *map, size_t top, const char *name)
186 {
187 	struct mentry *mep, *mcur;
188 	struct bt_arg *bhigh, *bprev;
189 	size_t i;
190 
191 	if (map == NULL)
192 		return;
193 
194 	bprev = &maxba;
195 	for (i = 0; i < top; i++) {
196 		mcur = NULL;
197 		bhigh = &nullba;
198 		RB_FOREACH(mep, map, map) {
199 			if (bacmp(mep->mval, bhigh) >= 0 &&
200 			    bacmp(mep->mval, bprev) < 0 &&
201 			    mep->mval != bprev) {
202 				mcur = mep;
203 				bhigh = mcur->mval;
204 			}
205 		}
206 		if (mcur == NULL)
207 			break;
208 		printf("@%s[%s]: %s\n", name, mcur->mkey,
209 		    ba2str(mcur->mval, NULL));
210 		bprev = mcur->mval;
211 	}
212 }
213 
214 void
215 map_zero(struct map *map)
216 {
217 	struct mentry *mep;
218 
219 	RB_FOREACH(mep, map, map) {
220 		mep->mval->ba_value = 0;
221 		mep->mval->ba_type = B_AT_LONG;
222 	}
223 }
224 
225 /*
226  * Histogram implemmented with map.
227  */
228 
229 struct hist {
230 	struct map	hmap;
231 	int		hstep;
232 };
233 
234 struct hist *
235 hist_increment(struct hist *hist, const char *key, long step)
236 {
237 	static struct bt_arg incba = BA_INITIALIZER(NULL, B_AT_MF_COUNT);
238 
239 	if (hist == NULL) {
240 		hist = calloc(1, sizeof(struct hist));
241 		if (hist == NULL)
242 			err(1, "hist: calloc");
243 		hist->hstep = step;
244 	}
245 	assert(hist->hstep == step);
246 
247 	return (struct hist *)map_insert(&hist->hmap, key, &incba, NULL);
248 }
249 
250 long
251 hist_get_bin_suffix(long bin, char **suffix)
252 {
253 #define GIGA	(MEGA * 1024)
254 #define MEGA	(KILO * 1024)
255 #define KILO	(1024)
256 
257 	*suffix = "";
258 	if (bin >= GIGA) {
259 		bin /= GIGA;
260 		*suffix = "G";
261 	}
262 	if (bin >= MEGA) {
263 		bin /= MEGA;
264 		*suffix = "M";
265 	}
266 	if (bin >= KILO) {
267 		bin /= KILO;
268 		*suffix = "K";
269 	}
270 
271 	return bin;
272 #undef MEGA
273 #undef KILO
274 }
275 
276 /*
277  * Print bucket header where `upb' is the upper bound of the interval
278  * and `hstep' the width of the interval.
279  */
280 static inline int
281 hist_print_bucket(char *buf, size_t buflen, long upb, long hstep)
282 {
283 	int l;
284 
285 	if (hstep != 0) {
286 		/* Linear histogram */
287 		l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb);
288 	} else {
289 		/* Power-of-two histogram */
290 		if (upb < 0) {
291 			l = snprintf(buf, buflen, "(..., 0)");
292 		} else if (upb < 2) {
293 			l = snprintf(buf, buflen, "[%lu]", upb);
294 		} else {
295 			long lob = upb / 2;
296 			char *lsuf, *usuf;
297 
298 			upb = hist_get_bin_suffix(upb, &usuf);
299 			lob = hist_get_bin_suffix(lob, &lsuf);
300 
301 			l = snprintf(buf, buflen, "[%lu%s, %lu%s)",
302 			    lob, lsuf, upb, usuf);
303 		}
304 	}
305 
306 	if (l < 0 || (size_t)l > buflen)
307 		warn("string too long %d > %lu", l, sizeof(buf));
308 
309 	return l;
310 }
311 
312 void
313 hist_print(struct hist *hist, const char *name)
314 {
315 	struct map *map = &hist->hmap;
316 	static char buf[80];
317 	struct mentry *mep, *mcur;
318 	long bmin, bprev, bin, val, max = 0;
319 	int i, l, length = 52;
320 
321 	if (map == NULL)
322 		return;
323 
324 	bprev = 0;
325 	RB_FOREACH(mep, map, map) {
326 		val = ba2long(mep->mval, NULL);
327 		if (val > max)
328 			max = val;
329 	}
330 	printf("@%s:\n", name);
331 
332 	/*
333 	 * Sort by ascending key.
334 	 */
335 	bprev = -1;
336 	for (;;) {
337 		mcur = NULL;
338 		bmin = LONG_MAX;
339 
340 		RB_FOREACH(mep, map, map) {
341 			bin = atol(mep->mkey);
342 			if ((bin <= bmin) && (bin > bprev)) {
343 				mcur = mep;
344 				bmin = bin;
345 			}
346 		}
347 		if (mcur == NULL)
348 			break;
349 
350 		bin = atol(mcur->mkey);
351 		val = ba2long(mcur->mval, NULL);
352 		i = (length * val) / max;
353 		l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep);
354 		snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|",
355 		    20 - l, val,
356 		    i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@",
357 		    length - i, "");
358 		printf("%s\n", buf);
359 
360 		bprev = bin;
361 	}
362 }
363