Bug Summary

File:src/usr.sbin/btrace/map.c
Warning:line 369, column 22
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name map.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -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/lib/clang/13.0.0 -D PTRACE -D KTRACE -D ACCOUNTING -D NFSCLIENT -D SYSVSHM -D SYSVSEM -D SYSVMSG -I /usr/src/usr.sbin/btrace -internal-isystem /usr/local/lib/clang/13.0.0/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 -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/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/btrace/map.c
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
44RB_HEAD(map, mentry)struct map { struct mentry *rbh_root; };
45
46struct 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
52int mcmp(const struct mentry *, const struct mentry *);
53struct mentry *mget(struct map *, const char *);
54
55RB_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
57int
58mcmp(const struct mentry *me0, const struct mentry *me1)
59{
60 return strncmp(me0->mkey, me1->mkey, KLEN512 - 1);
61}
62
63struct mentry *
64mget(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
82void
83map_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
96void
97map_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
109struct bt_arg *
110map_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
121struct map *
122map_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
186static int
187map_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. */
200void
201map_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
231void
232map_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
246struct hist {
247 struct map hmap;
248 int hstep;
249};
250
251struct hist *
252hist_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
267long
268hist_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 */
297static inline int
298hist_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
329void
330hist_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;
1
'max' initialized to 0
→
336 int i, l, length = 52;
337
338 if (map == NULL((void *)0))
2
←
Assuming 'map' is not equal to NULL
→
3
←
Taking false branch
→
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)) {
4
←
Assuming 'mep' is equal to null
→
5
←
Loop condition is false. Execution continues on line 347
→
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 (;;) {
6
←
Loop condition is true. Entering loop body
→
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)) {
7
←
Assuming 'mep' is not equal to null
→
8
←
Loop condition is true. Entering loop body
→
11
←
Assuming 'mep' is equal to null
→
12
←
Loop condition is false. Execution continues on line 364
→
358 bin = atol(mep->mkey);
359 if ((bin
8.1
'bin' is <= 'bmin'
 <= bmin) && (bin > bprev)) {
9
←
Assuming 'bin' is > 'bprev'
→
10
←
Taking true branch
→
360 mcur = mep;
361 bmin = bin;
362 }
363 }
364 if (mcur
12.1
'mcur' is not equal to NULL
 == NULL((void *)0))
13
←
Taking false branch
→
365 break;
366
367 bin = atol(mcur->mkey);
368 val = ba2long(mcur->mval, NULL((void *)0));
369 i = (length * val) / max;
14
←
Division by zero
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}