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