File: | src/usr.sbin/btrace/map.c |
Warning: | line 167, column 17 Use of memory allocated with size zero |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: map.c,v 1.24 2023/09/11 19:01:26 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 | RB_HEAD(map, mentry)struct map { struct mentry *rbh_root; }; | |||
37 | ||||
38 | struct mentry { | |||
39 | RB_ENTRY(mentry)struct { struct mentry *rbe_left; struct mentry *rbe_right; struct mentry *rbe_parent; int rbe_color; } mlink; | |||
40 | char mkey[KLEN1024]; | |||
41 | struct bt_arg *mval; | |||
42 | }; | |||
43 | ||||
44 | int mcmp(const struct mentry *, const struct mentry *); | |||
45 | struct mentry *mget(struct map *, const char *); | |||
46 | ||||
47 | 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); }; | |||
48 | ||||
49 | int | |||
50 | mcmp(const struct mentry *me0, const struct mentry *me1) | |||
51 | { | |||
52 | return strncmp(me0->mkey, me1->mkey, KLEN1024 - 1); | |||
53 | } | |||
54 | ||||
55 | struct mentry * | |||
56 | mget(struct map *map, const char *key) | |||
57 | { | |||
58 | struct mentry me, *mep; | |||
59 | ||||
60 | strlcpy(me.mkey, key, KLEN1024); | |||
61 | mep = RB_FIND(map, map, &me)map_RB_FIND(map, &me); | |||
62 | if (mep == NULL((void *)0)) { | |||
63 | mep = calloc(1, sizeof(struct mentry)); | |||
64 | if (mep == NULL((void *)0)) | |||
65 | err(1, "mentry: calloc"); | |||
66 | ||||
67 | strlcpy(mep->mkey, key, KLEN1024); | |||
68 | RB_INSERT(map, map, mep)map_RB_INSERT(map, mep); | |||
69 | } | |||
70 | ||||
71 | return mep; | |||
72 | } | |||
73 | ||||
74 | struct map * | |||
75 | map_new(void) | |||
76 | { | |||
77 | struct map *map; | |||
78 | ||||
79 | map = calloc(1, sizeof(struct map)); | |||
80 | if (map == NULL((void *)0)) | |||
81 | err(1, "map: calloc"); | |||
82 | ||||
83 | return map; | |||
84 | } | |||
85 | ||||
86 | void | |||
87 | map_clear(struct map *map) | |||
88 | { | |||
89 | struct mentry *mep; | |||
90 | ||||
91 | while ((mep = RB_MIN(map, map)map_RB_MINMAX(map, -1)) != NULL((void *)0)) { | |||
92 | RB_REMOVE(map, map, mep)map_RB_REMOVE(map, mep); | |||
93 | free(mep); | |||
94 | } | |||
95 | ||||
96 | assert(RB_EMPTY(map))((((map)->rbh_root == ((void *)0))) ? (void)0 : __assert2( "/usr/src/usr.sbin/btrace/map.c", 96, __func__, "RB_EMPTY(map)" )); | |||
97 | free(map); | |||
98 | } | |||
99 | ||||
100 | void | |||
101 | map_delete(struct map *map, const char *key) | |||
102 | { | |||
103 | struct mentry me, *mep; | |||
104 | ||||
105 | strlcpy(me.mkey, key, KLEN1024); | |||
106 | mep = RB_FIND(map, map, &me)map_RB_FIND(map, &me); | |||
107 | if (mep != NULL((void *)0)) { | |||
108 | RB_REMOVE(map, map, mep)map_RB_REMOVE(map, mep); | |||
109 | free(mep); | |||
110 | } | |||
111 | } | |||
112 | ||||
113 | struct bt_arg * | |||
114 | map_get(struct map *map, const char *key) | |||
115 | { | |||
116 | struct mentry *mep; | |||
117 | ||||
118 | mep = mget(map, key); | |||
119 | if (mep->mval == NULL((void *)0)) | |||
120 | mep->mval = ba_new(0, B_AT_LONG)ba_new0((void *)(0), (B_AT_LONG)); | |||
121 | ||||
122 | return mep->mval; | |||
123 | } | |||
124 | ||||
125 | void | |||
126 | map_insert(struct map *map, const char *key, void *cookie) | |||
127 | { | |||
128 | struct mentry *mep; | |||
129 | ||||
130 | mep = mget(map, key); | |||
131 | free(mep->mval); | |||
132 | mep->mval = cookie; | |||
133 | } | |||
134 | ||||
135 | static int | |||
136 | map_cmp(const void *a, const void *b) | |||
137 | { | |||
138 | const struct mentry *ma = *(const struct mentry **)a; | |||
139 | const struct mentry *mb = *(const struct mentry **)b; | |||
140 | long rv; | |||
141 | ||||
142 | rv = bacmp(ma->mval, mb->mval); | |||
143 | if (rv != 0) | |||
144 | return (rv > 0 ? -1 : 1); | |||
145 | return mcmp(ma, mb); | |||
146 | } | |||
147 | ||||
148 | /* Print at most `top' entries of the map ordered by value. */ | |||
149 | void | |||
150 | map_print(struct map *map, size_t top, const char *name) | |||
151 | { | |||
152 | struct mentry **elms, *mep; | |||
153 | size_t i, count = 0; | |||
154 | ||||
155 | if (map == NULL((void *)0)) | |||
| ||||
156 | return; | |||
157 | ||||
158 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) | |||
159 | count++; | |||
160 | ||||
161 | elms = calloc(count, sizeof(*elms)); | |||
162 | if (elms == NULL((void *)0)) | |||
163 | err(1, NULL((void *)0)); | |||
164 | ||||
165 | count = 0; | |||
166 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) | |||
167 | elms[count++] = mep; | |||
| ||||
168 | ||||
169 | qsort(elms, count, sizeof(*elms), map_cmp); | |||
170 | ||||
171 | for (i = 0; i < top && i < count; i++) { | |||
172 | mep = elms[i]; | |||
173 | printf("@%s[%s]: %s\n", name, mep->mkey, | |||
174 | ba2str(mep->mval, NULL((void *)0))); | |||
175 | } | |||
176 | ||||
177 | free(elms); | |||
178 | } | |||
179 | ||||
180 | void | |||
181 | map_zero(struct map *map) | |||
182 | { | |||
183 | struct mentry *mep; | |||
184 | ||||
185 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) { | |||
186 | mep->mval->ba_value = 0; | |||
187 | mep->mval->ba_type = B_AT_LONG; | |||
188 | } | |||
189 | } | |||
190 | ||||
191 | /* | |||
192 | * Histogram implemented with map. | |||
193 | */ | |||
194 | struct hist { | |||
195 | struct map hmap; | |||
196 | int hstep; | |||
197 | }; | |||
198 | ||||
199 | struct hist * | |||
200 | hist_new(long step) | |||
201 | { | |||
202 | struct hist *hist; | |||
203 | ||||
204 | hist = calloc(1, sizeof(struct hist)); | |||
205 | if (hist == NULL((void *)0)) | |||
206 | err(1, "hist: calloc"); | |||
207 | hist->hstep = step; | |||
208 | ||||
209 | return hist; | |||
210 | } | |||
211 | ||||
212 | void | |||
213 | hist_increment(struct hist *hist, const char *bucket) | |||
214 | { | |||
215 | struct bt_arg *ba; | |||
216 | long val; | |||
217 | ||||
218 | ba = map_get(&hist->hmap, bucket); | |||
219 | ||||
220 | assert(ba->ba_type == B_AT_LONG)((ba->ba_type == B_AT_LONG) ? (void)0 : __assert2("/usr/src/usr.sbin/btrace/map.c" , 220, __func__, "ba->ba_type == B_AT_LONG")); | |||
221 | val = (long)ba->ba_value; | |||
222 | val++; | |||
223 | ba->ba_value = (void *)val; | |||
224 | } | |||
225 | ||||
226 | long | |||
227 | hist_get_bin_suffix(long bin, char **suffix) | |||
228 | { | |||
229 | #define EXA((((((1024LL) * 1024) * 1024) * 1024) * 1024) * 1024) (PETA(((((1024LL) * 1024) * 1024) * 1024) * 1024) * 1024) | |||
230 | #define PETA(((((1024LL) * 1024) * 1024) * 1024) * 1024) (TERA((((1024LL) * 1024) * 1024) * 1024) * 1024) | |||
231 | #define TERA((((1024LL) * 1024) * 1024) * 1024) (GIGA(((1024LL) * 1024) * 1024) * 1024) | |||
232 | #define GIGA(((1024LL) * 1024) * 1024) (MEGA((1024LL) * 1024) * 1024) | |||
233 | #define MEGA((1024LL) * 1024) (KILO(1024LL) * 1024) | |||
234 | #define KILO(1024LL) (1024LL) | |||
235 | ||||
236 | *suffix = ""; | |||
237 | if (bin >= EXA((((((1024LL) * 1024) * 1024) * 1024) * 1024) * 1024)) { | |||
238 | bin /= EXA((((((1024LL) * 1024) * 1024) * 1024) * 1024) * 1024); | |||
239 | *suffix = "E"; | |||
240 | } | |||
241 | if (bin >= PETA(((((1024LL) * 1024) * 1024) * 1024) * 1024)) { | |||
242 | bin /= PETA(((((1024LL) * 1024) * 1024) * 1024) * 1024); | |||
243 | *suffix = "P"; | |||
244 | } | |||
245 | if (bin >= TERA((((1024LL) * 1024) * 1024) * 1024)) { | |||
246 | bin /= TERA((((1024LL) * 1024) * 1024) * 1024); | |||
247 | *suffix = "T"; | |||
248 | } | |||
249 | if (bin >= GIGA(((1024LL) * 1024) * 1024)) { | |||
250 | bin /= GIGA(((1024LL) * 1024) * 1024); | |||
251 | *suffix = "G"; | |||
252 | } | |||
253 | if (bin >= MEGA((1024LL) * 1024)) { | |||
254 | bin /= MEGA((1024LL) * 1024); | |||
255 | *suffix = "M"; | |||
256 | } | |||
257 | if (bin >= KILO(1024LL)) { | |||
258 | bin /= KILO(1024LL); | |||
259 | *suffix = "K"; | |||
260 | } | |||
261 | return bin; | |||
262 | } | |||
263 | ||||
264 | /* | |||
265 | * Print bucket header where `upb' is the upper bound of the interval | |||
266 | * and `hstep' the width of the interval. | |||
267 | */ | |||
268 | static inline int | |||
269 | hist_print_bucket(char *buf, size_t buflen, long upb, long hstep) | |||
270 | { | |||
271 | int l; | |||
272 | ||||
273 | if (hstep != 0) { | |||
274 | /* Linear histogram */ | |||
275 | l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb); | |||
276 | } else { | |||
277 | /* Power-of-two histogram */ | |||
278 | if (upb < 0) { | |||
279 | l = snprintf(buf, buflen, "(..., 0)"); | |||
280 | } else if (upb == 0) { | |||
281 | l = snprintf(buf, buflen, "[%lu]", upb); | |||
282 | } else { | |||
283 | long lob = upb / 2; | |||
284 | char *lsuf, *usuf; | |||
285 | ||||
286 | upb = hist_get_bin_suffix(upb, &usuf); | |||
287 | lob = hist_get_bin_suffix(lob, &lsuf); | |||
288 | ||||
289 | l = snprintf(buf, buflen, "[%lu%s, %lu%s)", | |||
290 | lob, lsuf, upb, usuf); | |||
291 | } | |||
292 | } | |||
293 | ||||
294 | if (l < 0 || (size_t)l > buflen) | |||
295 | warn("string too long %d > %lu", l, sizeof(buf)); | |||
296 | ||||
297 | return l; | |||
298 | } | |||
299 | ||||
300 | void | |||
301 | hist_print(struct hist *hist, const char *name) | |||
302 | { | |||
303 | struct map *map = &hist->hmap; | |||
304 | static char buf[80]; | |||
305 | struct mentry *mep, *mcur; | |||
306 | long bmin, bprev, bin, val, max = 0; | |||
307 | int i, l, length = 52; | |||
308 | ||||
309 | if (map == NULL((void *)0)) | |||
310 | return; | |||
311 | ||||
312 | bprev = 0; | |||
313 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) { | |||
314 | val = ba2long(mep->mval, NULL((void *)0)); | |||
315 | if (val > max) | |||
316 | max = val; | |||
317 | } | |||
318 | printf("@%s:\n", name); | |||
319 | ||||
320 | /* | |||
321 | * Sort by ascending key. | |||
322 | */ | |||
323 | bprev = -1; | |||
324 | for (;;) { | |||
325 | mcur = NULL((void *)0); | |||
326 | bmin = LONG_MAX0x7fffffffffffffffL; | |||
327 | ||||
328 | RB_FOREACH(mep, map, map)for ((mep) = map_RB_MINMAX(map, -1); (mep) != ((void *)0); (mep ) = map_RB_NEXT(mep)) { | |||
329 | bin = atol(mep->mkey); | |||
330 | if ((bin <= bmin) && (bin > bprev)) { | |||
331 | mcur = mep; | |||
332 | bmin = bin; | |||
333 | } | |||
334 | } | |||
335 | if (mcur == NULL((void *)0)) | |||
336 | break; | |||
337 | ||||
338 | bin = atol(mcur->mkey); | |||
339 | val = ba2long(mcur->mval, NULL((void *)0)); | |||
340 | i = (length * val) / max; | |||
341 | l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep); | |||
342 | snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|", | |||
343 | 20 - l, val, | |||
344 | i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@", | |||
345 | length - i, ""); | |||
346 | printf("%s\n", buf); | |||
347 | ||||
348 | bprev = bin; | |||
349 | } | |||
350 | } |