File: | src/usr.sbin/btrace/map.c |
Warning: | line 341, column 2 Value stored to 'bprev' is never read |
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; |
Value stored to 'bprev' is never read | |
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 | } |