1 /* $OpenBSD: map.c,v 1.16 2021/09/01 08:06:49 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 if (map == NULL) 88 return; 89 90 while ((mep = RB_MIN(map, map)) != NULL) { 91 RB_REMOVE(map, map, mep); 92 free(mep); 93 } 94 95 assert(RB_EMPTY(map)); 96 free(map); 97 } 98 99 void 100 map_delete(struct map *map, const char *key) 101 { 102 struct mentry me, *mep; 103 104 strlcpy(me.mkey, key, KLEN); 105 mep = RB_FIND(map, map, &me); 106 if (mep != NULL) { 107 RB_REMOVE(map, map, mep); 108 free(mep); 109 } 110 } 111 112 struct bt_arg * 113 map_get(struct map *map, const char *key) 114 { 115 struct mentry *mep; 116 117 mep = mget(map, key); 118 if (mep->mval == NULL) 119 mep->mval = ba_new(0, B_AT_LONG); 120 121 return mep->mval; 122 } 123 124 struct map * 125 map_insert(struct map *map, const char *key, struct bt_arg *bval, 126 struct dt_evt *dtev) 127 { 128 struct mentry *mep; 129 long val; 130 131 if (map == NULL) { 132 map = calloc(1, sizeof(struct map)); 133 if (map == NULL) 134 err(1, "map: calloc"); 135 } 136 137 mep = mget(map, key); 138 switch (bval->ba_type) { 139 case B_AT_STR: 140 case B_AT_LONG: 141 free(mep->mval); 142 mep->mval = bval; 143 break; 144 case B_AT_BI_PID: 145 case B_AT_BI_TID: 146 case B_AT_BI_CPU: 147 case B_AT_BI_NSECS: 148 case B_AT_BI_ARG0 ... B_AT_BI_ARG9: 149 case B_AT_BI_RETVAL: 150 free(mep->mval); 151 mep->mval = ba_new(ba2long(bval, dtev), B_AT_LONG); 152 break; 153 case B_AT_MF_COUNT: 154 if (mep->mval == NULL) 155 mep->mval = ba_new(0, B_AT_LONG); 156 val = (long)mep->mval->ba_value; 157 val++; 158 mep->mval->ba_value = (void *)val; 159 break; 160 case B_AT_MF_MAX: 161 if (mep->mval == NULL) 162 mep->mval = ba_new(0, B_AT_LONG); 163 val = (long)mep->mval->ba_value; 164 val = MAX(val, ba2long(bval->ba_value, dtev)); 165 mep->mval->ba_value = (void *)val; 166 break; 167 case B_AT_MF_MIN: 168 if (mep->mval == NULL) 169 mep->mval = ba_new(0, B_AT_LONG); 170 val = (long)mep->mval->ba_value; 171 val = MIN(val, ba2long(bval->ba_value, dtev)); 172 mep->mval->ba_value = (void *)val; 173 break; 174 case B_AT_MF_SUM: 175 if (mep->mval == NULL) 176 mep->mval = ba_new(0, B_AT_LONG); 177 val = (long)mep->mval->ba_value; 178 val += ba2long(bval->ba_value, dtev); 179 mep->mval->ba_value = (void *)val; 180 break; 181 default: 182 errx(1, "no insert support for type %d", bval->ba_type); 183 } 184 185 return map; 186 } 187 188 /* Print at most `top' entries of the map ordered by value. */ 189 void 190 map_print(struct map *map, size_t top, const char *name) 191 { 192 struct mentry *mep, *mcur; 193 struct bt_arg *bhigh, *bprev; 194 size_t i; 195 196 if (map == NULL) 197 return; 198 199 bprev = &g_maxba; 200 for (i = 0; i < top; i++) { 201 mcur = NULL; 202 bhigh = &g_nullba; 203 RB_FOREACH(mep, map, map) { 204 if (bacmp(mep->mval, bhigh) >= 0 && 205 bacmp(mep->mval, bprev) < 0 && 206 mep->mval != bprev) { 207 mcur = mep; 208 bhigh = mcur->mval; 209 } 210 } 211 if (mcur == NULL) 212 break; 213 printf("@%s[%s]: %s\n", name, mcur->mkey, 214 ba2str(mcur->mval, NULL)); 215 bprev = mcur->mval; 216 } 217 } 218 219 void 220 map_zero(struct map *map) 221 { 222 struct mentry *mep; 223 224 RB_FOREACH(mep, map, map) { 225 mep->mval->ba_value = 0; 226 mep->mval->ba_type = B_AT_LONG; 227 } 228 } 229 230 /* 231 * Histogram implemented with map. 232 */ 233 234 struct hist { 235 struct map hmap; 236 int hstep; 237 }; 238 239 struct hist * 240 hist_increment(struct hist *hist, const char *key, long step) 241 { 242 static struct bt_arg incba = BA_INITIALIZER(NULL, B_AT_MF_COUNT); 243 244 if (hist == NULL) { 245 hist = calloc(1, sizeof(struct hist)); 246 if (hist == NULL) 247 err(1, "hist: calloc"); 248 hist->hstep = step; 249 } 250 assert(hist->hstep == step); 251 252 return (struct hist *)map_insert(&hist->hmap, key, &incba, NULL); 253 } 254 255 long 256 hist_get_bin_suffix(long bin, char **suffix) 257 { 258 #define GIGA (MEGA * 1024) 259 #define MEGA (KILO * 1024) 260 #define KILO (1024) 261 262 *suffix = ""; 263 if (bin >= GIGA) { 264 bin /= GIGA; 265 *suffix = "G"; 266 } 267 if (bin >= MEGA) { 268 bin /= MEGA; 269 *suffix = "M"; 270 } 271 if (bin >= KILO) { 272 bin /= KILO; 273 *suffix = "K"; 274 } 275 276 return bin; 277 #undef MEGA 278 #undef KILO 279 } 280 281 /* 282 * Print bucket header where `upb' is the upper bound of the interval 283 * and `hstep' the width of the interval. 284 */ 285 static inline int 286 hist_print_bucket(char *buf, size_t buflen, long upb, long hstep) 287 { 288 int l; 289 290 if (hstep != 0) { 291 /* Linear histogram */ 292 l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb); 293 } else { 294 /* Power-of-two histogram */ 295 if (upb < 0) { 296 l = snprintf(buf, buflen, "(..., 0)"); 297 } else if (upb == 0) { 298 l = snprintf(buf, buflen, "[%lu]", upb); 299 } else { 300 long lob = upb / 2; 301 char *lsuf, *usuf; 302 303 upb = hist_get_bin_suffix(upb, &usuf); 304 lob = hist_get_bin_suffix(lob, &lsuf); 305 306 l = snprintf(buf, buflen, "[%lu%s, %lu%s)", 307 lob, lsuf, upb, usuf); 308 } 309 } 310 311 if (l < 0 || (size_t)l > buflen) 312 warn("string too long %d > %lu", l, sizeof(buf)); 313 314 return l; 315 } 316 317 void 318 hist_print(struct hist *hist, const char *name) 319 { 320 struct map *map = &hist->hmap; 321 static char buf[80]; 322 struct mentry *mep, *mcur; 323 long bmin, bprev, bin, val, max = 0; 324 int i, l, length = 52; 325 326 if (map == NULL) 327 return; 328 329 bprev = 0; 330 RB_FOREACH(mep, map, map) { 331 val = ba2long(mep->mval, NULL); 332 if (val > max) 333 max = val; 334 } 335 printf("@%s:\n", name); 336 337 /* 338 * Sort by ascending key. 339 */ 340 bprev = -1; 341 for (;;) { 342 mcur = NULL; 343 bmin = LONG_MAX; 344 345 RB_FOREACH(mep, map, map) { 346 bin = atol(mep->mkey); 347 if ((bin <= bmin) && (bin > bprev)) { 348 mcur = mep; 349 bmin = bin; 350 } 351 } 352 if (mcur == NULL) 353 break; 354 355 bin = atol(mcur->mkey); 356 val = ba2long(mcur->mval, NULL); 357 i = (length * val) / max; 358 l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep); 359 snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|", 360 20 - l, val, 361 i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@", 362 length - i, ""); 363 printf("%s\n", buf); 364 365 bprev = bin; 366 } 367 } 368