xref: /openbsd-src/usr.sbin/btrace/map.c (revision fc405d53b73a2d73393cb97f684863d17b583e38) 
1 /*	$OpenBSD: map.c,v 1.20 2022/04/30 01:29:05 tedu 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(const struct mentry *, const struct mentry *);
53 struct mentry	*mget(struct map *, const char *);
54 
55 RB_GENERATE(map, mentry, mlink, mcmp);
56 
57 int
58 mcmp(const struct mentry *me0, const 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_PID:
142 	case B_AT_BI_TID:
143 	case B_AT_BI_CPU:
144 	case B_AT_BI_NSECS:
145 	case B_AT_BI_ARG0 ... B_AT_BI_ARG9:
146 	case B_AT_BI_RETVAL:
147 	case B_AT_BI_PROBE:
148 		free(mep->mval);
149 		mep->mval = ba_new(ba2long(bval, dtev), B_AT_LONG);
150 		break;
151 	case B_AT_MF_COUNT:
152 		if (mep->mval == NULL)
153 			mep->mval = ba_new(0, B_AT_LONG);
154 		val = (long)mep->mval->ba_value;
155 		val++;
156 		mep->mval->ba_value = (void *)val;
157 		break;
158 	case B_AT_MF_MAX:
159 		if (mep->mval == NULL)
160 			mep->mval = ba_new(0, B_AT_LONG);
161 		val = (long)mep->mval->ba_value;
162 		val = MAX(val, ba2long(bval->ba_value, dtev));
163 		mep->mval->ba_value = (void *)val;
164 		break;
165 	case B_AT_MF_MIN:
166 		if (mep->mval == NULL)
167 			mep->mval = ba_new(0, B_AT_LONG);
168 		val = (long)mep->mval->ba_value;
169 		val = MIN(val, ba2long(bval->ba_value, dtev));
170 		mep->mval->ba_value = (void *)val;
171 		break;
172 	case B_AT_MF_SUM:
173 		if (mep->mval == NULL)
174 			mep->mval = ba_new(0, B_AT_LONG);
175 		val = (long)mep->mval->ba_value;
176 		val += ba2long(bval->ba_value, dtev);
177 		mep->mval->ba_value = (void *)val;
178 		break;
179 	default:
180 		errx(1, "no insert support for type %d", bval->ba_type);
181 	}
182 
183 	return map;
184 }
185 
186 static int
187 map_cmp(const void *a, const void *b)
188 {
189 	const struct mentry *ma = *(const struct mentry **)a;
190 	const struct mentry *mb = *(const struct mentry **)b;
191 	long rv;
192 
193 	rv = bacmp(ma->mval, mb->mval);
194 	if (rv != 0)
195 		return (rv > 0 ? -1 : 1);
196 	return mcmp(ma, mb);
197 }
198 
199 /* Print at most `top' entries of the map ordered by value. */
200 void
201 map_print(struct map *map, size_t top, const char *name)
202 {
203 	struct mentry **elms, *mep;
204 	size_t i, count = 0;
205 
206 	if (map == NULL)
207 		return;
208 
209 	RB_FOREACH(mep, map, map)
210 		count++;
211 
212 	elms = calloc(count, sizeof(*elms));
213 	if (elms == NULL)
214 		err(1, NULL);
215 
216 	count = 0;
217 	RB_FOREACH(mep, map, map)
218 		elms[count++] = mep;
219 
220 	qsort(elms, count, sizeof(*elms), map_cmp);
221 
222 	for (i = 0; i < top && i < count; i++) {
223 		mep = elms[i];
224 		printf("@%s[%s]: %s\n", name, mep->mkey,
225 		    ba2str(mep->mval, NULL));
226 	}
227 
228 	free(elms);
229 }
230 
231 void
232 map_zero(struct map *map)
233 {
234 	struct mentry *mep;
235 
236 	RB_FOREACH(mep, map, map) {
237 		mep->mval->ba_value = 0;
238 		mep->mval->ba_type = B_AT_LONG;
239 	}
240 }
241 
242 /*
243  * Histogram implemented with map.
244  */
245 
246 struct hist {
247 	struct map	hmap;
248 	int		hstep;
249 };
250 
251 struct hist *
252 hist_increment(struct hist *hist, const char *key, long step)
253 {
254 	static struct bt_arg incba = BA_INITIALIZER(NULL, B_AT_MF_COUNT);
255 
256 	if (hist == NULL) {
257 		hist = calloc(1, sizeof(struct hist));
258 		if (hist == NULL)
259 			err(1, "hist: calloc");
260 		hist->hstep = step;
261 	}
262 	assert(hist->hstep == step);
263 
264 	return (struct hist *)map_insert(&hist->hmap, key, &incba, NULL);
265 }
266 
267 long
268 hist_get_bin_suffix(long bin, char **suffix)
269 {
270 #define EXA	(PETA * 1024)
271 #define PETA	(TERA * 1024)
272 #define TERA	(GIGA * 1024)
273 #define GIGA	(MEGA * 1024)
274 #define MEGA	(KILO * 1024)
275 #define KILO	(1024LL)
276 
277 	*suffix = "";
278 	if (bin >= EXA) {
279 		bin /= EXA;
280 		*suffix = "E";
281 	}
282 	if (bin >= PETA) {
283 		bin /= PETA;
284 		*suffix = "P";
285 	}
286 	if (bin >= TERA) {
287 		bin /= TERA;
288 		*suffix = "T";
289 	}
290 	if (bin >= GIGA) {
291 		bin /= GIGA;
292 		*suffix = "G";
293 	}
294 	if (bin >= MEGA) {
295 		bin /= MEGA;
296 		*suffix = "M";
297 	}
298 	if (bin >= KILO) {
299 		bin /= KILO;
300 		*suffix = "K";
301 	}
302 	return bin;
303 }
304 
305 /*
306  * Print bucket header where `upb' is the upper bound of the interval
307  * and `hstep' the width of the interval.
308  */
309 static inline int
310 hist_print_bucket(char *buf, size_t buflen, long upb, long hstep)
311 {
312 	int l;
313 
314 	if (hstep != 0) {
315 		/* Linear histogram */
316 		l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb);
317 	} else {
318 		/* Power-of-two histogram */
319 		if (upb < 0) {
320 			l = snprintf(buf, buflen, "(..., 0)");
321 		} else if (upb == 0) {
322 			l = snprintf(buf, buflen, "[%lu]", upb);
323 		} else {
324 			long lob = upb / 2;
325 			char *lsuf, *usuf;
326 
327 			upb = hist_get_bin_suffix(upb, &usuf);
328 			lob = hist_get_bin_suffix(lob, &lsuf);
329 
330 			l = snprintf(buf, buflen, "[%lu%s, %lu%s)",
331 			    lob, lsuf, upb, usuf);
332 		}
333 	}
334 
335 	if (l < 0 || (size_t)l > buflen)
336 		warn("string too long %d > %lu", l, sizeof(buf));
337 
338 	return l;
339 }
340 
341 void
342 hist_print(struct hist *hist, const char *name)
343 {
344 	struct map *map = &hist->hmap;
345 	static char buf[80];
346 	struct mentry *mep, *mcur;
347 	long bmin, bprev, bin, val, max = 0;
348 	int i, l, length = 52;
349 
350 	if (map == NULL)
351 		return;
352 
353 	bprev = 0;
354 	RB_FOREACH(mep, map, map) {
355 		val = ba2long(mep->mval, NULL);
356 		if (val > max)
357 			max = val;
358 	}
359 	printf("@%s:\n", name);
360 
361 	/*
362 	 * Sort by ascending key.
363 	 */
364 	bprev = -1;
365 	for (;;) {
366 		mcur = NULL;
367 		bmin = LONG_MAX;
368 
369 		RB_FOREACH(mep, map, map) {
370 			bin = atol(mep->mkey);
371 			if ((bin <= bmin) && (bin > bprev)) {
372 				mcur = mep;
373 				bmin = bin;
374 			}
375 		}
376 		if (mcur == NULL)
377 			break;
378 
379 		bin = atol(mcur->mkey);
380 		val = ba2long(mcur->mval, NULL);
381 		i = (length * val) / max;
382 		l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep);
383 		snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|",
384 		    20 - l, val,
385 		    i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@",
386 		    length - i, "");
387 		printf("%s\n", buf);
388 
389 		bprev = bin;
390 	}
391 }
392