Commit | Line | Data |
---|---|---|
3d1d07ec JK |
1 | #include "hist.h" |
2 | ||
3 | struct rb_root hist; | |
3d1d07ec JK |
4 | int callchain; |
5 | ||
6 | struct callchain_param callchain_param = { | |
7 | .mode = CHAIN_GRAPH_REL, | |
8 | .min_percent = 0.5 | |
9 | }; | |
10 | ||
3d1d07ec JK |
11 | /* |
12 | * histogram, sorted on item, collects counts | |
13 | */ | |
14 | ||
1ed091c4 | 15 | struct hist_entry *__hist_entry__add(struct addr_location *al, |
9735abf1 | 16 | struct symbol *sym_parent, |
1ed091c4 | 17 | u64 count, bool *hit) |
9735abf1 ACM |
18 | { |
19 | struct rb_node **p = &hist.rb_node; | |
20 | struct rb_node *parent = NULL; | |
21 | struct hist_entry *he; | |
22 | struct hist_entry entry = { | |
1ed091c4 ACM |
23 | .thread = al->thread, |
24 | .map = al->map, | |
25 | .sym = al->sym, | |
26 | .ip = al->addr, | |
27 | .level = al->level, | |
9735abf1 ACM |
28 | .count = count, |
29 | .parent = sym_parent, | |
30 | }; | |
31 | int cmp; | |
32 | ||
33 | while (*p != NULL) { | |
34 | parent = *p; | |
35 | he = rb_entry(parent, struct hist_entry, rb_node); | |
36 | ||
37 | cmp = hist_entry__cmp(&entry, he); | |
38 | ||
39 | if (!cmp) { | |
40 | *hit = true; | |
41 | return he; | |
42 | } | |
43 | ||
44 | if (cmp < 0) | |
45 | p = &(*p)->rb_left; | |
46 | else | |
47 | p = &(*p)->rb_right; | |
48 | } | |
49 | ||
50 | he = malloc(sizeof(*he)); | |
51 | if (!he) | |
52 | return NULL; | |
53 | *he = entry; | |
54 | rb_link_node(&he->rb_node, parent, p); | |
55 | rb_insert_color(&he->rb_node, &hist); | |
56 | *hit = false; | |
57 | return he; | |
58 | } | |
59 | ||
3d1d07ec JK |
60 | int64_t |
61 | hist_entry__cmp(struct hist_entry *left, struct hist_entry *right) | |
62 | { | |
63 | struct sort_entry *se; | |
64 | int64_t cmp = 0; | |
65 | ||
66 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
67 | cmp = se->cmp(left, right); | |
68 | if (cmp) | |
69 | break; | |
70 | } | |
71 | ||
72 | return cmp; | |
73 | } | |
74 | ||
75 | int64_t | |
76 | hist_entry__collapse(struct hist_entry *left, struct hist_entry *right) | |
77 | { | |
78 | struct sort_entry *se; | |
79 | int64_t cmp = 0; | |
80 | ||
81 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
82 | int64_t (*f)(struct hist_entry *, struct hist_entry *); | |
83 | ||
84 | f = se->collapse ?: se->cmp; | |
85 | ||
86 | cmp = f(left, right); | |
87 | if (cmp) | |
88 | break; | |
89 | } | |
90 | ||
91 | return cmp; | |
92 | } | |
93 | ||
94 | void hist_entry__free(struct hist_entry *he) | |
95 | { | |
96 | free(he); | |
97 | } | |
98 | ||
99 | /* | |
100 | * collapse the histogram | |
101 | */ | |
102 | ||
b9bf0892 | 103 | static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he) |
3d1d07ec | 104 | { |
b9bf0892 | 105 | struct rb_node **p = &root->rb_node; |
3d1d07ec JK |
106 | struct rb_node *parent = NULL; |
107 | struct hist_entry *iter; | |
108 | int64_t cmp; | |
109 | ||
110 | while (*p != NULL) { | |
111 | parent = *p; | |
112 | iter = rb_entry(parent, struct hist_entry, rb_node); | |
113 | ||
114 | cmp = hist_entry__collapse(iter, he); | |
115 | ||
116 | if (!cmp) { | |
117 | iter->count += he->count; | |
118 | hist_entry__free(he); | |
119 | return; | |
120 | } | |
121 | ||
122 | if (cmp < 0) | |
123 | p = &(*p)->rb_left; | |
124 | else | |
125 | p = &(*p)->rb_right; | |
126 | } | |
127 | ||
128 | rb_link_node(&he->rb_node, parent, p); | |
b9bf0892 | 129 | rb_insert_color(&he->rb_node, root); |
3d1d07ec JK |
130 | } |
131 | ||
132 | void collapse__resort(void) | |
133 | { | |
b9bf0892 | 134 | struct rb_root tmp; |
3d1d07ec JK |
135 | struct rb_node *next; |
136 | struct hist_entry *n; | |
137 | ||
138 | if (!sort__need_collapse) | |
139 | return; | |
140 | ||
b9bf0892 | 141 | tmp = RB_ROOT; |
3d1d07ec | 142 | next = rb_first(&hist); |
b9bf0892 | 143 | |
3d1d07ec JK |
144 | while (next) { |
145 | n = rb_entry(next, struct hist_entry, rb_node); | |
146 | next = rb_next(&n->rb_node); | |
147 | ||
148 | rb_erase(&n->rb_node, &hist); | |
b9bf0892 | 149 | collapse__insert_entry(&tmp, n); |
3d1d07ec | 150 | } |
b9bf0892 ACM |
151 | |
152 | hist = tmp; | |
3d1d07ec JK |
153 | } |
154 | ||
155 | /* | |
156 | * reverse the map, sort on count. | |
157 | */ | |
158 | ||
b9bf0892 ACM |
159 | static void output__insert_entry(struct rb_root *root, struct hist_entry *he, |
160 | u64 min_callchain_hits) | |
3d1d07ec | 161 | { |
b9bf0892 | 162 | struct rb_node **p = &root->rb_node; |
3d1d07ec JK |
163 | struct rb_node *parent = NULL; |
164 | struct hist_entry *iter; | |
165 | ||
166 | if (callchain) | |
167 | callchain_param.sort(&he->sorted_chain, &he->callchain, | |
168 | min_callchain_hits, &callchain_param); | |
169 | ||
170 | while (*p != NULL) { | |
171 | parent = *p; | |
172 | iter = rb_entry(parent, struct hist_entry, rb_node); | |
173 | ||
174 | if (he->count > iter->count) | |
175 | p = &(*p)->rb_left; | |
176 | else | |
177 | p = &(*p)->rb_right; | |
178 | } | |
179 | ||
180 | rb_link_node(&he->rb_node, parent, p); | |
b9bf0892 | 181 | rb_insert_color(&he->rb_node, root); |
3d1d07ec JK |
182 | } |
183 | ||
184 | void output__resort(u64 total_samples) | |
185 | { | |
b9bf0892 | 186 | struct rb_root tmp; |
3d1d07ec JK |
187 | struct rb_node *next; |
188 | struct hist_entry *n; | |
3d1d07ec JK |
189 | u64 min_callchain_hits; |
190 | ||
191 | min_callchain_hits = | |
192 | total_samples * (callchain_param.min_percent / 100); | |
193 | ||
b9bf0892 ACM |
194 | tmp = RB_ROOT; |
195 | next = rb_first(&hist); | |
3d1d07ec JK |
196 | |
197 | while (next) { | |
198 | n = rb_entry(next, struct hist_entry, rb_node); | |
199 | next = rb_next(&n->rb_node); | |
200 | ||
b9bf0892 ACM |
201 | rb_erase(&n->rb_node, &hist); |
202 | output__insert_entry(&tmp, n, min_callchain_hits); | |
3d1d07ec | 203 | } |
b9bf0892 ACM |
204 | |
205 | hist = tmp; | |
3d1d07ec | 206 | } |