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