File: | src/usr.sbin/btrace/map.c |
Warning: | line 218, column 17 Use of zero-allocated memory |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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)) ((_a) < (_b) ? (_a) : (_b)) | |||
38 | #endif | |||
39 | ||||
40 | #ifndef MAX | |||
41 | #define MAX(_a,_b)((_a) > (_b) ? (_a) : (_b)) ((_a) > (_b) ? (_a) : (_b)) | |||
42 | #endif | |||
43 | ||||
44 | RB_HEAD(map, mentry)struct map { struct mentry *rbh_root; }; | |||
45 | ||||
46 | struct mentry { | |||
47 | RB_ENTRY(mentry)struct { struct mentry *rbe_left; struct mentry *rbe_right; struct mentry *rbe_parent; int rbe_color; } mlink; | |||
48 | char mkey[KLEN512]; | |||
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)void map_RB_INSERT_COLOR(struct map *head, struct mentry *elm ) { struct mentry *parent, *gparent, *tmp; while ((parent = ( elm)->mlink.rbe_parent) && (parent)->mlink.rbe_color == 1) { gparent = (parent)->mlink.rbe_parent; if (parent == (gparent)->mlink.rbe_left) { tmp = (gparent)->mlink.rbe_right ; if (tmp && (tmp)->mlink.rbe_color == 1) { (tmp)-> mlink.rbe_color = 0; do { (parent)->mlink.rbe_color = 0; ( gparent)->mlink.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->mlink.rbe_right == elm) { do { ( tmp) = (parent)->mlink.rbe_right; if (((parent)->mlink. rbe_right = (tmp)->mlink.rbe_left)) { ((tmp)->mlink.rbe_left )->mlink.rbe_parent = (parent); } do {} while (0); if (((tmp )->mlink.rbe_parent = (parent)->mlink.rbe_parent)) { if ((parent) == ((parent)->mlink.rbe_parent)->mlink.rbe_left ) ((parent)->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((parent)->mlink.rbe_parent)->mlink.rbe_right = ( tmp); } else (head)->rbh_root = (tmp); (tmp)->mlink.rbe_left = (parent); (parent)->mlink.rbe_parent = (tmp); do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> mlink.rbe_color = 0; (gparent)->mlink.rbe_color = 1; } while (0); do { (tmp) = (gparent)->mlink.rbe_left; if (((gparent )->mlink.rbe_left = (tmp)->mlink.rbe_right)) { ((tmp)-> mlink.rbe_right)->mlink.rbe_parent = (gparent); } do {} while (0); if (((tmp)->mlink.rbe_parent = (gparent)->mlink.rbe_parent )) { if ((gparent) == ((gparent)->mlink.rbe_parent)->mlink .rbe_left) ((gparent)->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((gparent)->mlink.rbe_parent)->mlink.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->mlink .rbe_right = (gparent); (gparent)->mlink.rbe_parent = (tmp ); do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); } else { tmp = (gparent)->mlink.rbe_left ; if (tmp && (tmp)->mlink.rbe_color == 1) { (tmp)-> mlink.rbe_color = 0; do { (parent)->mlink.rbe_color = 0; ( gparent)->mlink.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->mlink.rbe_left == elm) { do { ( tmp) = (parent)->mlink.rbe_left; if (((parent)->mlink.rbe_left = (tmp)->mlink.rbe_right)) { ((tmp)->mlink.rbe_right)-> mlink.rbe_parent = (parent); } do {} while (0); if (((tmp)-> mlink.rbe_parent = (parent)->mlink.rbe_parent)) { if ((parent ) == ((parent)->mlink.rbe_parent)->mlink.rbe_left) ((parent )->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((parent )->mlink.rbe_parent)->mlink.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->mlink.rbe_right = (parent ); (parent)->mlink.rbe_parent = (tmp); do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->mlink .rbe_color = 0; (gparent)->mlink.rbe_color = 1; } while (0 ); do { (tmp) = (gparent)->mlink.rbe_right; if (((gparent) ->mlink.rbe_right = (tmp)->mlink.rbe_left)) { ((tmp)-> mlink.rbe_left)->mlink.rbe_parent = (gparent); } do {} while (0); if (((tmp)->mlink.rbe_parent = (gparent)->mlink.rbe_parent )) { if ((gparent) == ((gparent)->mlink.rbe_parent)->mlink .rbe_left) ((gparent)->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((gparent)->mlink.rbe_parent)->mlink.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->mlink .rbe_left = (gparent); (gparent)->mlink.rbe_parent = (tmp) ; do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); } } (head->rbh_root)->mlink.rbe_color = 0; } void map_RB_REMOVE_COLOR(struct map *head, struct mentry *parent, struct mentry *elm) { struct mentry *tmp; while ((elm == ((void *)0) || (elm)->mlink.rbe_color == 0) && elm != (head)->rbh_root) { if ((parent)->mlink.rbe_left == elm) { tmp = (parent)->mlink.rbe_right; if ((tmp)-> mlink.rbe_color == 1) { do { (tmp)->mlink.rbe_color = 0; ( parent)->mlink.rbe_color = 1; } while (0); do { (tmp) = (parent )->mlink.rbe_right; if (((parent)->mlink.rbe_right = (tmp )->mlink.rbe_left)) { ((tmp)->mlink.rbe_left)->mlink .rbe_parent = (parent); } do {} while (0); if (((tmp)->mlink .rbe_parent = (parent)->mlink.rbe_parent)) { if ((parent) == ((parent)->mlink.rbe_parent)->mlink.rbe_left) ((parent )->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((parent )->mlink.rbe_parent)->mlink.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->mlink.rbe_left = (parent ); (parent)->mlink.rbe_parent = (tmp); do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->mlink.rbe_right; } if (((tmp)->mlink.rbe_left == ((void *)0) || ((tmp)->mlink.rbe_left)->mlink.rbe_color == 0) && ((tmp)->mlink.rbe_right == ((void *)0) || ((tmp)->mlink.rbe_right)->mlink.rbe_color == 0)) { (tmp )->mlink.rbe_color = 1; elm = parent; parent = (elm)->mlink .rbe_parent; } else { if ((tmp)->mlink.rbe_right == ((void *)0) || ((tmp)->mlink.rbe_right)->mlink.rbe_color == 0 ) { struct mentry *oleft; if ((oleft = (tmp)->mlink.rbe_left )) (oleft)->mlink.rbe_color = 0; (tmp)->mlink.rbe_color = 1; do { (oleft) = (tmp)->mlink.rbe_left; if (((tmp)-> mlink.rbe_left = (oleft)->mlink.rbe_right)) { ((oleft)-> mlink.rbe_right)->mlink.rbe_parent = (tmp); } do {} while ( 0); if (((oleft)->mlink.rbe_parent = (tmp)->mlink.rbe_parent )) { if ((tmp) == ((tmp)->mlink.rbe_parent)->mlink.rbe_left ) ((tmp)->mlink.rbe_parent)->mlink.rbe_left = (oleft); else ((tmp)->mlink.rbe_parent)->mlink.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (oleft)->mlink.rbe_right = (tmp); (tmp)->mlink.rbe_parent = (oleft); do {} while ( 0); if (((oleft)->mlink.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->mlink.rbe_right; } (tmp)->mlink.rbe_color = (parent)->mlink.rbe_color; (parent)->mlink.rbe_color = 0; if ((tmp)->mlink.rbe_right) ((tmp)->mlink.rbe_right )->mlink.rbe_color = 0; do { (tmp) = (parent)->mlink.rbe_right ; if (((parent)->mlink.rbe_right = (tmp)->mlink.rbe_left )) { ((tmp)->mlink.rbe_left)->mlink.rbe_parent = (parent ); } do {} while (0); if (((tmp)->mlink.rbe_parent = (parent )->mlink.rbe_parent)) { if ((parent) == ((parent)->mlink .rbe_parent)->mlink.rbe_left) ((parent)->mlink.rbe_parent )->mlink.rbe_left = (tmp); else ((parent)->mlink.rbe_parent )->mlink.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->mlink.rbe_left = (parent); (parent)->mlink .rbe_parent = (tmp); do {} while (0); if (((tmp)->mlink.rbe_parent )) do {} while (0); } while (0); elm = (head)->rbh_root; break ; } } else { tmp = (parent)->mlink.rbe_left; if ((tmp)-> mlink.rbe_color == 1) { do { (tmp)->mlink.rbe_color = 0; ( parent)->mlink.rbe_color = 1; } while (0); do { (tmp) = (parent )->mlink.rbe_left; if (((parent)->mlink.rbe_left = (tmp )->mlink.rbe_right)) { ((tmp)->mlink.rbe_right)->mlink .rbe_parent = (parent); } do {} while (0); if (((tmp)->mlink .rbe_parent = (parent)->mlink.rbe_parent)) { if ((parent) == ((parent)->mlink.rbe_parent)->mlink.rbe_left) ((parent )->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((parent )->mlink.rbe_parent)->mlink.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->mlink.rbe_right = (parent ); (parent)->mlink.rbe_parent = (tmp); do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->mlink.rbe_left; } if (((tmp)->mlink.rbe_left == ((void *)0) || ((tmp)->mlink.rbe_left)->mlink.rbe_color == 0) && ((tmp)->mlink.rbe_right == ((void *)0) || ((tmp)->mlink.rbe_right)->mlink.rbe_color == 0)) { (tmp )->mlink.rbe_color = 1; elm = parent; parent = (elm)->mlink .rbe_parent; } else { if ((tmp)->mlink.rbe_left == ((void * )0) || ((tmp)->mlink.rbe_left)->mlink.rbe_color == 0) { struct mentry *oright; if ((oright = (tmp)->mlink.rbe_right )) (oright)->mlink.rbe_color = 0; (tmp)->mlink.rbe_color = 1; do { (oright) = (tmp)->mlink.rbe_right; if (((tmp)-> mlink.rbe_right = (oright)->mlink.rbe_left)) { ((oright)-> mlink.rbe_left)->mlink.rbe_parent = (tmp); } do {} while ( 0); if (((oright)->mlink.rbe_parent = (tmp)->mlink.rbe_parent )) { if ((tmp) == ((tmp)->mlink.rbe_parent)->mlink.rbe_left ) ((tmp)->mlink.rbe_parent)->mlink.rbe_left = (oright); else ((tmp)->mlink.rbe_parent)->mlink.rbe_right = (oright ); } else (head)->rbh_root = (oright); (oright)->mlink. rbe_left = (tmp); (tmp)->mlink.rbe_parent = (oright); do { } while (0); if (((oright)->mlink.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->mlink.rbe_left; } (tmp) ->mlink.rbe_color = (parent)->mlink.rbe_color; (parent) ->mlink.rbe_color = 0; if ((tmp)->mlink.rbe_left) ((tmp )->mlink.rbe_left)->mlink.rbe_color = 0; do { (tmp) = ( parent)->mlink.rbe_left; if (((parent)->mlink.rbe_left = (tmp)->mlink.rbe_right)) { ((tmp)->mlink.rbe_right)-> mlink.rbe_parent = (parent); } do {} while (0); if (((tmp)-> mlink.rbe_parent = (parent)->mlink.rbe_parent)) { if ((parent ) == ((parent)->mlink.rbe_parent)->mlink.rbe_left) ((parent )->mlink.rbe_parent)->mlink.rbe_left = (tmp); else ((parent )->mlink.rbe_parent)->mlink.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->mlink.rbe_right = (parent ); (parent)->mlink.rbe_parent = (tmp); do {} while (0); if (((tmp)->mlink.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } } if (elm) (elm)->mlink .rbe_color = 0; } struct mentry * map_RB_REMOVE(struct map *head , struct mentry *elm) { struct mentry *child, *parent, *old = elm; int color; if ((elm)->mlink.rbe_left == ((void *)0)) child = (elm)->mlink.rbe_right; else if ((elm)->mlink. rbe_right == ((void *)0)) child = (elm)->mlink.rbe_left; else { struct mentry *left; elm = (elm)->mlink.rbe_right; while ((left = (elm)->mlink.rbe_left)) elm = left; child = (elm )->mlink.rbe_right; parent = (elm)->mlink.rbe_parent; color = (elm)->mlink.rbe_color; if (child) (child)->mlink.rbe_parent = parent; if (parent) { if ((parent)->mlink.rbe_left == elm ) (parent)->mlink.rbe_left = child; else (parent)->mlink .rbe_right = child; do {} while (0); } else (head)->rbh_root = child; if ((elm)->mlink.rbe_parent == old) parent = elm ; (elm)->mlink = (old)->mlink; if ((old)->mlink.rbe_parent ) { if (((old)->mlink.rbe_parent)->mlink.rbe_left == old ) ((old)->mlink.rbe_parent)->mlink.rbe_left = elm; else ((old)->mlink.rbe_parent)->mlink.rbe_right = elm; do { } while (0); } else (head)->rbh_root = elm; ((old)->mlink .rbe_left)->mlink.rbe_parent = elm; if ((old)->mlink.rbe_right ) ((old)->mlink.rbe_right)->mlink.rbe_parent = elm; if ( parent) { left = parent; do { do {} while (0); } while ((left = (left)->mlink.rbe_parent)); } goto color; } parent = (elm )->mlink.rbe_parent; color = (elm)->mlink.rbe_color; if (child) (child)->mlink.rbe_parent = parent; if (parent) { if ((parent)->mlink.rbe_left == elm) (parent)->mlink.rbe_left = child; else (parent)->mlink.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; color: if (color == 0) map_RB_REMOVE_COLOR(head, parent, child); return (old); } struct mentry * map_RB_INSERT(struct map *head, struct mentry *elm) { struct mentry *tmp; struct mentry *parent = ((void * )0); int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (mcmp)(elm, parent); if (comp < 0) tmp = (tmp )->mlink.rbe_left; else if (comp > 0) tmp = (tmp)->mlink .rbe_right; else return (tmp); } do { (elm)->mlink.rbe_parent = parent; (elm)->mlink.rbe_left = (elm)->mlink.rbe_right = ((void *)0); (elm)->mlink.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0) (parent)->mlink .rbe_left = elm; else (parent)->mlink.rbe_right = elm; do { } while (0); } else (head)->rbh_root = elm; map_RB_INSERT_COLOR (head, elm); return (((void *)0)); } struct mentry * map_RB_FIND (struct map *head, struct mentry *elm) { struct mentry *tmp = (head)->rbh_root; int comp; while (tmp) { comp = mcmp(elm , tmp); if (comp < 0) tmp = (tmp)->mlink.rbe_left; else if (comp > 0) tmp = (tmp)->mlink.rbe_right; else return (tmp); } return (((void *)0)); } struct mentry * map_RB_NFIND (struct map *head, struct mentry *elm) { struct mentry *tmp = (head)->rbh_root; struct mentry *res = ((void *)0); int comp ; while (tmp) { comp = mcmp(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->mlink.rbe_left; } else if (comp > 0 ) tmp = (tmp)->mlink.rbe_right; else return (tmp); } return (res); } struct mentry * map_RB_NEXT(struct mentry *elm) { if ((elm)->mlink.rbe_right) { elm = (elm)->mlink.rbe_right ; while ((elm)->mlink.rbe_left) elm = (elm)->mlink.rbe_left ; } else { if ((elm)->mlink.rbe_parent && (elm == ( (elm)->mlink.rbe_parent)->mlink.rbe_left)) elm = (elm)-> mlink.rbe_parent; else { while ((elm)->mlink.rbe_parent && (elm == ((elm)->mlink.rbe_parent)->mlink.rbe_right)) elm = (elm)->mlink.rbe_parent; elm = (elm)->mlink.rbe_parent ; } } return (elm); } struct mentry * map_RB_PREV(struct mentry *elm) { if ((elm)->mlink.rbe_left) { elm = (elm)->mlink .rbe_left; while ((elm)->mlink.rbe_right) elm = (elm)-> mlink.rbe_right; } else { if ((elm)->mlink.rbe_parent && (elm == ((elm)->mlink.rbe_parent)->mlink.rbe_right)) elm = (elm)->mlink.rbe_parent; else { while ((elm)->mlink. rbe_parent && (elm == ((elm)->mlink.rbe_parent)-> mlink.rbe_left)) elm = (elm)->mlink.rbe_parent; elm = (elm )->mlink.rbe_parent; } } return (elm); } struct mentry * map_RB_MINMAX (struct map *head, int val) { struct mentry *tmp = (head)-> rbh_root; struct mentry *parent = ((void *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->mlink.rbe_left; else tmp = (tmp)->mlink.rbe_right; } return (parent); }; | |||
56 | ||||
57 | int | |||
58 | mcmp(const struct mentry *me0, const struct mentry *me1) | |||
59 | { | |||
60 | return strncmp(me0->mkey, me1->mkey, KLEN512 - 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, KLEN512); | |||
69 | mep = RB_FIND(map, map, &me)map_RB_FIND(map, &me); | |||
70 | if (mep == NULL((void *)0)) { | |||
71 | mep = calloc(1, sizeof(struct mentry)); | |||
72 | if (mep == NULL((void *)0)) | |||
73 | err(1, "mentry: calloc"); | |||
74 | ||||
75 | strlcpy(mep->mkey, key, KLEN512); | |||
76 | RB_INSERT(map, map, mep)map_RB_INSERT(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)map_RB_MINMAX(map, -1)) != NULL((void *)0)) { | |||
88 | RB_REMOVE(map, map, mep)map_RB_REMOVE(map, mep); | |||
89 | free(mep); | |||
90 | } | |||
91 | ||||
92 | assert(RB_EMPTY(map))((((map)->rbh_root == ((void *)0))) ? (void)0 : __assert2( "/usr/src/usr.sbin/btrace/map.c", 92, __func__, "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, KLEN512); | |||
102 | mep = RB_FIND(map, map, &me)map_RB_FIND(map, &me); | |||
103 | if (mep != NULL((void *)0)) { | |||
104 | RB_REMOVE(map, map, mep)map_RB_REMOVE(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((void *)0)) | |||
116 | mep->mval = ba_new(0, B_AT_LONG)ba_new0((void *)(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((void *)0)) { | |||
129 | map = calloc(1, sizeof(struct map)); | |||
130 | if (map == NULL((void *)0)) | |||
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)ba_new0((void *)(ba2long(bval, dtev)), (B_AT_LONG)); | |||
150 | break; | |||
151 | case B_AT_MF_COUNT: | |||
152 | if (mep->mval == NULL((void *)0)) | |||
153 | mep->mval = ba_new(0, B_AT_LONG)ba_new0((void *)(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((void *)0)) | |||
160 | mep->mval = ba_new(0, B_AT_LONG)ba_new0((void *)(0), (B_AT_LONG)); | |||
161 | val = (long)mep->mval->ba_value; | |||
162 | val = MAX(val, ba2long(bval->ba_value, dtev))((val) > (ba2long(bval->ba_value, dtev)) ? (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((void *)0)) | |||
167 | mep->mval = ba_new(0, B_AT_LONG)ba_new0((void *)(0), (B_AT_LONG)); | |||
168 | val = (long)mep->mval->ba_value; | |||
169 | val = MIN(val, ba2long(bval->ba_value, dtev))((val) < (ba2long(bval->ba_value, dtev)) ? (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((void *)0)) | |||
174 | mep->mval = ba_new(0, B_AT_LONG)ba_new0((void *)(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((void *)0)) | |||
| ||||
207 | return; | |||
208 | ||||
209 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) | |||
210 | count++; | |||
211 | ||||
212 | elms = calloc(count, sizeof(*elms)); | |||
213 | if (elms == NULL((void *)0)) | |||
214 | err(1, NULL((void *)0)); | |||
215 | ||||
216 | count = 0; | |||
217 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) | |||
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((void *)0))); | |||
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)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) { | |||
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){ { ((void *)0) }, (void *)(((void *)0)), ((void *)0), (B_AT_MF_COUNT ) }; | |||
255 | ||||
256 | if (hist == NULL((void *)0)) { | |||
257 | hist = calloc(1, sizeof(struct hist)); | |||
258 | if (hist == NULL((void *)0)) | |||
259 | err(1, "hist: calloc"); | |||
260 | hist->hstep = step; | |||
261 | } | |||
262 | assert(hist->hstep == step)((hist->hstep == step) ? (void)0 : __assert2("/usr/src/usr.sbin/btrace/map.c" , 262, __func__, "hist->hstep == step")); | |||
263 | ||||
264 | return (struct hist *)map_insert(&hist->hmap, key, &incba, NULL((void *)0)); | |||
265 | } | |||
266 | ||||
267 | long | |||
268 | hist_get_bin_suffix(long bin, char **suffix) | |||
269 | { | |||
270 | #define GIGA(MEGA * 1024) (MEGA * 1024) | |||
271 | #define MEGA (KILO * 1024) | |||
272 | #define KILO (1024) | |||
273 | ||||
274 | *suffix = ""; | |||
275 | if (bin >= GIGA(MEGA * 1024)) { | |||
276 | bin /= GIGA(MEGA * 1024); | |||
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((void *)0)) | |||
339 | return; | |||
340 | ||||
341 | bprev = 0; | |||
342 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) { | |||
343 | val = ba2long(mep->mval, NULL((void *)0)); | |||
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((void *)0); | |||
355 | bmin = LONG_MAX9223372036854775807L; | |||
356 | ||||
357 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) { | |||
358 | bin = atol(mep->mkey); | |||
359 | if ((bin <= bmin) && (bin > bprev)) { | |||
360 | mcur = mep; | |||
361 | bmin = bin; | |||
362 | } | |||
363 | } | |||
364 | if (mcur == NULL((void *)0)) | |||
365 | break; | |||
366 | ||||
367 | bin = atol(mcur->mkey); | |||
368 | val = ba2long(mcur->mval, NULL((void *)0)); | |||
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 | } |