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