xref: /openbsd/usr.sbin/btrace/map.c (revision 76d0caae) 
1 /*	$OpenBSD: map.c,v 1.19 2021/11/15 14:57:57 claudio 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 GIGA	(MEGA * 1024)
271 #define MEGA	(KILO * 1024)
272 #define KILO	(1024)
273 
274 	*suffix = "";
275 	if (bin >= GIGA) {
276 		bin /= GIGA;
277 		*suffix = "G";
278 	}
279 	if (bin >= MEGA) {
280 		bin /= MEGA;
281 		*suffix = "M";
282 	}
283 	if (bin >= KILO) {
284 		bin /= KILO;
285 		*suffix = "K";
286 	}
287 
288 	return bin;
289 #undef MEGA
290 #undef KILO
291 }
292 
293 /*
294  * Print bucket header where `upb' is the upper bound of the interval
295  * and `hstep' the width of the interval.
296  */
297 static inline int
298 hist_print_bucket(char *buf, size_t buflen, long upb, long hstep)
299 {
300 	int l;
301 
302 	if (hstep != 0) {
303 		/* Linear histogram */
304 		l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb);
305 	} else {
306 		/* Power-of-two histogram */
307 		if (upb < 0) {
308 			l = snprintf(buf, buflen, "(..., 0)");
309 		} else if (upb == 0) {
310 			l = snprintf(buf, buflen, "[%lu]", upb);
311 		} else {
312 			long lob = upb / 2;
313 			char *lsuf, *usuf;
314 
315 			upb = hist_get_bin_suffix(upb, &usuf);
316 			lob = hist_get_bin_suffix(lob, &lsuf);
317 
318 			l = snprintf(buf, buflen, "[%lu%s, %lu%s)",
319 			    lob, lsuf, upb, usuf);
320 		}
321 	}
322 
323 	if (l < 0 || (size_t)l > buflen)
324 		warn("string too long %d > %lu", l, sizeof(buf));
325 
326 	return l;
327 }
328 
329 void
330 hist_print(struct hist *hist, const char *name)
331 {
332 	struct map *map = &hist->hmap;
333 	static char buf[80];
334 	struct mentry *mep, *mcur;
335 	long bmin, bprev, bin, val, max = 0;
336 	int i, l, length = 52;
337 
338 	if (map == NULL)
339 		return;
340 
341 	bprev = 0;
342 	RB_FOREACH(mep, map, map) {
343 		val = ba2long(mep->mval, NULL);
344 		if (val > max)
345 			max = val;
346 	}
347 	printf("@%s:\n", name);
348 
349 	/*
350 	 * Sort by ascending key.
351 	 */
352 	bprev = -1;
353 	for (;;) {
354 		mcur = NULL;
355 		bmin = LONG_MAX;
356 
357 		RB_FOREACH(mep, map, map) {
358 			bin = atol(mep->mkey);
359 			if ((bin <= bmin) && (bin > bprev)) {
360 				mcur = mep;
361 				bmin = bin;
362 			}
363 		}
364 		if (mcur == NULL)
365 			break;
366 
367 		bin = atol(mcur->mkey);
368 		val = ba2long(mcur->mval, NULL);
369 		i = (length * val) / max;
370 		l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep);
371 		snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|",
372 		    20 - l, val,
373 		    i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@",
374 		    length - i, "");
375 		printf("%s\n", buf);
376 
377 		bprev = bin;
378 	}
379 }
380