Bug Summary

File:src/usr.sbin/btrace/map.c
Warning:line 312, column 2
Value stored to 'bprev' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.4 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name map.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/btrace/obj -resource-dir /usr/local/llvm16/lib/clang/16 -D PTRACE -D KTRACE -D ACCOUNTING -D NFSCLIENT -D SYSVSHM -D SYSVSEM -D SYSVMSG -I /usr/src/usr.sbin/btrace -internal-isystem /usr/local/llvm16/lib/clang/16/include -internal-externc-isystem /usr/include -O2 -Wno-unused -fdebug-compilation-dir=/usr/src/usr.sbin/btrace/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fcf-protection=branch -fno-jump-tables -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/scan/2024-01-11-140451-98009-1 -x c /usr/src/usr.sbin/btrace/map.c
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
36RB_HEAD(map, mentry)struct map { struct mentry *rbh_root; };
37
38struct 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
44int mcmp(const struct mentry *, const struct mentry *);
45struct mentry *mget(struct map *, const char *);
46
47RB_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
49int
50mcmp(const struct mentry *me0, const struct mentry *me1)
51{
52 return strncmp(me0->mkey, me1->mkey, KLEN1024 - 1);
53}
54
55struct mentry *
56mget(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
74struct map *
75map_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
86void
87map_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
100void
101map_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
113struct bt_arg *
114map_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
125void
126map_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
135static int
136map_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. */
149void
150map_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
180void
181map_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 */
194struct hist {
195 struct map hmap;
196 int hstep;
197};
198
199struct hist *
200hist_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
212void
213hist_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
226long
227hist_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 */
268static inline int
269hist_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
300void
301hist_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;
Value stored to 'bprev' is never read
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}