blob: a1b823f8c17fc30da79ca63ba3b71404ea092b47 [file] [log] [blame]
Arnaldo Carvalho de Melo78f7def2011-02-04 09:45:46 -02001#include "annotate.h"
Frederic Weisbecker8a0ecfb2010-05-13 19:47:16 +02002#include "util.h"
Frederic Weisbecker598357e2010-05-21 12:48:39 +02003#include "build-id.h"
John Kacur3d1d07e2009-09-28 15:32:55 +02004#include "hist.h"
Arnaldo Carvalho de Melo4e4f06e2009-12-14 13:10:39 -02005#include "session.h"
6#include "sort.h"
Arnaldo Carvalho de Melo9b338272009-12-16 14:31:49 -02007#include <math.h>
John Kacur3d1d07e2009-09-28 15:32:55 +02008
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -02009static bool hists__filter_entry_by_dso(struct hists *hists,
10 struct hist_entry *he);
11static bool hists__filter_entry_by_thread(struct hists *hists,
12 struct hist_entry *he);
Namhyung Kime94d53e2012-03-16 17:50:51 +090013static bool hists__filter_entry_by_symbol(struct hists *hists,
14 struct hist_entry *he);
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -020015
Arnaldo Carvalho de Melo7a007ca2010-07-21 09:19:41 -030016enum hist_filter {
17 HIST_FILTER__DSO,
18 HIST_FILTER__THREAD,
19 HIST_FILTER__PARENT,
Namhyung Kime94d53e2012-03-16 17:50:51 +090020 HIST_FILTER__SYMBOL,
Arnaldo Carvalho de Melo7a007ca2010-07-21 09:19:41 -030021};
22
John Kacur3d1d07e2009-09-28 15:32:55 +020023struct callchain_param callchain_param = {
24 .mode = CHAIN_GRAPH_REL,
Sam Liaod797fdc2011-06-07 23:49:46 +080025 .min_percent = 0.5,
26 .order = ORDER_CALLEE
John Kacur3d1d07e2009-09-28 15:32:55 +020027};
28
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030029u16 hists__col_len(struct hists *hists, enum hist_column col)
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030030{
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030031 return hists->col_len[col];
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030032}
33
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030034void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len)
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030035{
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030036 hists->col_len[col] = len;
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030037}
38
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030039bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030040{
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030041 if (len > hists__col_len(hists, col)) {
42 hists__set_col_len(hists, col, len);
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030043 return true;
44 }
45 return false;
46}
47
Namhyung Kim7ccf4f92012-08-20 13:52:05 +090048void hists__reset_col_len(struct hists *hists)
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030049{
50 enum hist_column col;
51
52 for (col = 0; col < HISTC_NR_COLS; ++col)
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030053 hists__set_col_len(hists, col, 0);
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030054}
55
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +010056static void hists__set_unres_dso_col_len(struct hists *hists, int dso)
57{
58 const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
59
60 if (hists__col_len(hists, dso) < unresolved_col_width &&
61 !symbol_conf.col_width_list_str && !symbol_conf.field_sep &&
62 !symbol_conf.dso_list)
63 hists__set_col_len(hists, dso, unresolved_col_width);
64}
65
Namhyung Kim7ccf4f92012-08-20 13:52:05 +090066void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030067{
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +010068 const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030069 u16 len;
70
71 if (h->ms.sym)
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +010072 hists__new_col_len(hists, HISTC_SYMBOL, h->ms.sym->namelen + 4);
73 else
74 hists__set_unres_dso_col_len(hists, HISTC_DSO);
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030075
76 len = thread__comm_len(h->thread);
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030077 if (hists__new_col_len(hists, HISTC_COMM, len))
78 hists__set_col_len(hists, HISTC_THREAD, len + 6);
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030079
80 if (h->ms.map) {
81 len = dso__name_len(h->ms.map->dso);
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -030082 hists__new_col_len(hists, HISTC_DSO, len);
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -030083 }
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +010084
85 if (h->branch_info) {
86 int symlen;
87 /*
88 * +4 accounts for '[x] ' priv level info
89 * +2 account of 0x prefix on raw addresses
90 */
91 if (h->branch_info->from.sym) {
92 symlen = (int)h->branch_info->from.sym->namelen + 4;
93 hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
94
95 symlen = dso__name_len(h->branch_info->from.map->dso);
96 hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
97 } else {
98 symlen = unresolved_col_width + 4 + 2;
99 hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
100 hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
101 }
102
103 if (h->branch_info->to.sym) {
104 symlen = (int)h->branch_info->to.sym->namelen + 4;
105 hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
106
107 symlen = dso__name_len(h->branch_info->to.map->dso);
108 hists__new_col_len(hists, HISTC_DSO_TO, symlen);
109 } else {
110 symlen = unresolved_col_width + 4 + 2;
111 hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
112 hists__set_unres_dso_col_len(hists, HISTC_DSO_TO);
113 }
114 }
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -0300115}
116
Namhyung Kim7ccf4f92012-08-20 13:52:05 +0900117void hists__output_recalc_col_len(struct hists *hists, int max_rows)
118{
119 struct rb_node *next = rb_first(&hists->entries);
120 struct hist_entry *n;
121 int row = 0;
122
123 hists__reset_col_len(hists);
124
125 while (next && row++ < max_rows) {
126 n = rb_entry(next, struct hist_entry, rb_node);
127 if (!n->filtered)
128 hists__calc_col_len(hists, n);
129 next = rb_next(&n->rb_node);
130 }
131}
132
Arnaldo Carvalho de Melo12c14272012-01-04 12:27:03 -0200133static void hist_entry__add_cpumode_period(struct hist_entry *he,
Arnaldo Carvalho de Meloc82ee822010-05-14 14:19:35 -0300134 unsigned int cpumode, u64 period)
Zhang, Yanmina1645ce2010-04-19 13:32:50 +0800135{
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300136 switch (cpumode) {
Zhang, Yanmina1645ce2010-04-19 13:32:50 +0800137 case PERF_RECORD_MISC_KERNEL:
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900138 he->stat.period_sys += period;
Zhang, Yanmina1645ce2010-04-19 13:32:50 +0800139 break;
140 case PERF_RECORD_MISC_USER:
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900141 he->stat.period_us += period;
Zhang, Yanmina1645ce2010-04-19 13:32:50 +0800142 break;
143 case PERF_RECORD_MISC_GUEST_KERNEL:
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900144 he->stat.period_guest_sys += period;
Zhang, Yanmina1645ce2010-04-19 13:32:50 +0800145 break;
146 case PERF_RECORD_MISC_GUEST_USER:
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900147 he->stat.period_guest_us += period;
Zhang, Yanmina1645ce2010-04-19 13:32:50 +0800148 break;
149 default:
150 break;
151 }
152}
153
Namhyung Kim139c0812012-10-04 21:49:43 +0900154static void he_stat__add_period(struct he_stat *he_stat, u64 period)
155{
156 he_stat->period += period;
157 he_stat->nr_events += 1;
158}
159
160static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src)
161{
162 dest->period += src->period;
163 dest->period_sys += src->period_sys;
164 dest->period_us += src->period_us;
165 dest->period_guest_sys += src->period_guest_sys;
166 dest->period_guest_us += src->period_guest_us;
167 dest->nr_events += src->nr_events;
168}
169
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300170static void hist_entry__decay(struct hist_entry *he)
171{
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900172 he->stat.period = (he->stat.period * 7) / 8;
173 he->stat.nr_events = (he->stat.nr_events * 7) / 8;
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300174}
175
176static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
177{
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900178 u64 prev_period = he->stat.period;
Arnaldo Carvalho de Meloc64550c2011-10-20 06:45:44 -0200179
180 if (prev_period == 0)
Arnaldo Carvalho de Melodf71d952011-10-13 08:01:33 -0300181 return true;
Arnaldo Carvalho de Meloc64550c2011-10-20 06:45:44 -0200182
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300183 hist_entry__decay(he);
Arnaldo Carvalho de Meloc64550c2011-10-20 06:45:44 -0200184
185 if (!he->filtered)
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900186 hists->stats.total_period -= prev_period - he->stat.period;
Arnaldo Carvalho de Meloc64550c2011-10-20 06:45:44 -0200187
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900188 return he->stat.period == 0;
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300189}
190
Arnaldo Carvalho de Melob079d4e2011-10-17 09:05:04 -0200191static void __hists__decay_entries(struct hists *hists, bool zap_user,
192 bool zap_kernel, bool threaded)
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300193{
194 struct rb_node *next = rb_first(&hists->entries);
195 struct hist_entry *n;
196
197 while (next) {
198 n = rb_entry(next, struct hist_entry, rb_node);
199 next = rb_next(&n->rb_node);
Arnaldo Carvalho de Melodf71d952011-10-13 08:01:33 -0300200 /*
201 * We may be annotating this, for instance, so keep it here in
202 * case some it gets new samples, we'll eventually free it when
203 * the user stops browsing and it agains gets fully decayed.
204 */
Arnaldo Carvalho de Melob079d4e2011-10-17 09:05:04 -0200205 if (((zap_user && n->level == '.') ||
206 (zap_kernel && n->level != '.') ||
207 hists__decay_entry(hists, n)) &&
208 !n->used) {
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300209 rb_erase(&n->rb_node, &hists->entries);
210
Arnaldo Carvalho de Meloe345fa12011-10-13 09:06:54 -0300211 if (sort__need_collapse || threaded)
Arnaldo Carvalho de Meloab81f3fd2011-10-05 19:16:15 -0300212 rb_erase(&n->rb_node_in, &hists->entries_collapsed);
213
214 hist_entry__free(n);
215 --hists->nr_entries;
216 }
217 }
218}
219
Arnaldo Carvalho de Melob079d4e2011-10-17 09:05:04 -0200220void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
Arnaldo Carvalho de Meloe345fa12011-10-13 09:06:54 -0300221{
Arnaldo Carvalho de Melob079d4e2011-10-17 09:05:04 -0200222 return __hists__decay_entries(hists, zap_user, zap_kernel, false);
Arnaldo Carvalho de Meloe345fa12011-10-13 09:06:54 -0300223}
224
Arnaldo Carvalho de Melob079d4e2011-10-17 09:05:04 -0200225void hists__decay_entries_threaded(struct hists *hists,
226 bool zap_user, bool zap_kernel)
Arnaldo Carvalho de Meloe345fa12011-10-13 09:06:54 -0300227{
Arnaldo Carvalho de Melob079d4e2011-10-17 09:05:04 -0200228 return __hists__decay_entries(hists, zap_user, zap_kernel, true);
Arnaldo Carvalho de Meloe345fa12011-10-13 09:06:54 -0300229}
230
John Kacur3d1d07e2009-09-28 15:32:55 +0200231/*
Arnaldo Carvalho de Meloc82ee822010-05-14 14:19:35 -0300232 * histogram, sorted on item, collects periods
John Kacur3d1d07e2009-09-28 15:32:55 +0200233 */
234
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300235static struct hist_entry *hist_entry__new(struct hist_entry *template)
236{
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200237 size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_root) : 0;
Arnaldo Carvalho de Melo12c14272012-01-04 12:27:03 -0200238 struct hist_entry *he = malloc(sizeof(*he) + callchain_size);
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300239
Arnaldo Carvalho de Melo12c14272012-01-04 12:27:03 -0200240 if (he != NULL) {
241 *he = *template;
Namhyung Kimc4b35352012-10-04 21:49:42 +0900242
Arnaldo Carvalho de Melo12c14272012-01-04 12:27:03 -0200243 if (he->ms.map)
244 he->ms.map->referenced = true;
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300245 if (symbol_conf.use_callchain)
Arnaldo Carvalho de Melo12c14272012-01-04 12:27:03 -0200246 callchain_init(he->callchain);
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300247 }
248
Arnaldo Carvalho de Melo12c14272012-01-04 12:27:03 -0200249 return he;
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300250}
251
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300252static void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h)
Arnaldo Carvalho de Melofefb0b92010-05-10 13:57:51 -0300253{
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -0300254 if (!h->filtered) {
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300255 hists__calc_col_len(hists, h);
256 ++hists->nr_entries;
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900257 hists->stats.total_period += h->stat.period;
Arnaldo Carvalho de Melo8a6c5b22010-07-20 14:42:52 -0300258 }
Arnaldo Carvalho de Melofefb0b92010-05-10 13:57:51 -0300259}
260
Arnaldo Carvalho de Melo7a007ca2010-07-21 09:19:41 -0300261static u8 symbol__parent_filter(const struct symbol *parent)
262{
263 if (symbol_conf.exclude_other && parent == NULL)
264 return 1 << HIST_FILTER__PARENT;
265 return 0;
266}
267
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100268static struct hist_entry *add_hist_entry(struct hists *hists,
269 struct hist_entry *entry,
Arnaldo Carvalho de Melo1c02c4d2010-05-10 13:04:11 -0300270 struct addr_location *al,
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100271 u64 period)
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300272{
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300273 struct rb_node **p;
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300274 struct rb_node *parent = NULL;
275 struct hist_entry *he;
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300276 int cmp;
277
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300278 pthread_mutex_lock(&hists->lock);
279
280 p = &hists->entries_in->rb_node;
281
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300282 while (*p != NULL) {
283 parent = *p;
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300284 he = rb_entry(parent, struct hist_entry, rb_node_in);
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300285
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100286 cmp = hist_entry__cmp(entry, he);
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300287
288 if (!cmp) {
Namhyung Kim139c0812012-10-04 21:49:43 +0900289 he_stat__add_period(&he->stat, period);
David Miller63fa4712012-03-27 03:14:18 -0400290
291 /* If the map of an existing hist_entry has
292 * become out-of-date due to an exec() or
293 * similar, update it. Otherwise we will
294 * mis-adjust symbol addresses when computing
295 * the history counter to increment.
296 */
297 if (he->ms.map != entry->ms.map) {
298 he->ms.map = entry->ms.map;
299 if (he->ms.map)
300 he->ms.map->referenced = true;
301 }
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300302 goto out;
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300303 }
304
305 if (cmp < 0)
306 p = &(*p)->rb_left;
307 else
308 p = &(*p)->rb_right;
309 }
310
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100311 he = hist_entry__new(entry);
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300312 if (!he)
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300313 goto out_unlock;
314
315 rb_link_node(&he->rb_node_in, parent, p);
316 rb_insert_color(&he->rb_node_in, hists->entries_in);
Arnaldo Carvalho de Melo28e2a102010-05-09 13:02:23 -0300317out:
Arnaldo Carvalho de Meloc82ee822010-05-14 14:19:35 -0300318 hist_entry__add_cpumode_period(he, al->cpumode, period);
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300319out_unlock:
320 pthread_mutex_unlock(&hists->lock);
Arnaldo Carvalho de Melo9735abf2009-10-03 10:42:45 -0300321 return he;
322}
323
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100324struct hist_entry *__hists__add_branch_entry(struct hists *self,
325 struct addr_location *al,
326 struct symbol *sym_parent,
327 struct branch_info *bi,
328 u64 period)
329{
330 struct hist_entry entry = {
331 .thread = al->thread,
332 .ms = {
333 .map = bi->to.map,
334 .sym = bi->to.sym,
335 },
336 .cpu = al->cpu,
337 .ip = bi->to.addr,
338 .level = al->level,
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900339 .stat = {
340 .period = period,
Namhyung Kimc4b35352012-10-04 21:49:42 +0900341 .nr_events = 1,
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900342 },
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100343 .parent = sym_parent,
344 .filtered = symbol__parent_filter(sym_parent),
345 .branch_info = bi,
Jiri Olsaae359f12012-10-04 21:49:35 +0900346 .hists = self,
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100347 };
348
349 return add_hist_entry(self, &entry, al, period);
350}
351
352struct hist_entry *__hists__add_entry(struct hists *self,
353 struct addr_location *al,
354 struct symbol *sym_parent, u64 period)
355{
356 struct hist_entry entry = {
357 .thread = al->thread,
358 .ms = {
359 .map = al->map,
360 .sym = al->sym,
361 },
362 .cpu = al->cpu,
363 .ip = al->addr,
364 .level = al->level,
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900365 .stat = {
366 .period = period,
Namhyung Kimc4b35352012-10-04 21:49:42 +0900367 .nr_events = 1,
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900368 },
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100369 .parent = sym_parent,
370 .filtered = symbol__parent_filter(sym_parent),
Jiri Olsaae359f12012-10-04 21:49:35 +0900371 .hists = self,
Roberto Agostino Vitillob5387522012-02-09 23:21:01 +0100372 };
373
374 return add_hist_entry(self, &entry, al, period);
375}
376
John Kacur3d1d07e2009-09-28 15:32:55 +0200377int64_t
378hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
379{
380 struct sort_entry *se;
381 int64_t cmp = 0;
382
383 list_for_each_entry(se, &hist_entry__sort_list, list) {
Frederic Weisbeckerfcd14982010-04-14 19:11:29 +0200384 cmp = se->se_cmp(left, right);
John Kacur3d1d07e2009-09-28 15:32:55 +0200385 if (cmp)
386 break;
387 }
388
389 return cmp;
390}
391
392int64_t
393hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
394{
395 struct sort_entry *se;
396 int64_t cmp = 0;
397
398 list_for_each_entry(se, &hist_entry__sort_list, list) {
399 int64_t (*f)(struct hist_entry *, struct hist_entry *);
400
Frederic Weisbeckerfcd14982010-04-14 19:11:29 +0200401 f = se->se_collapse ?: se->se_cmp;
John Kacur3d1d07e2009-09-28 15:32:55 +0200402
403 cmp = f(left, right);
404 if (cmp)
405 break;
406 }
407
408 return cmp;
409}
410
411void hist_entry__free(struct hist_entry *he)
412{
Namhyung Kim580e3382012-11-07 16:27:14 +0900413 free(he->branch_info);
John Kacur3d1d07e2009-09-28 15:32:55 +0200414 free(he);
415}
416
417/*
418 * collapse the histogram
419 */
420
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300421static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100422 struct rb_root *root,
423 struct hist_entry *he)
John Kacur3d1d07e2009-09-28 15:32:55 +0200424{
Arnaldo Carvalho de Melob9bf0892009-12-14 11:37:11 -0200425 struct rb_node **p = &root->rb_node;
John Kacur3d1d07e2009-09-28 15:32:55 +0200426 struct rb_node *parent = NULL;
427 struct hist_entry *iter;
428 int64_t cmp;
429
430 while (*p != NULL) {
431 parent = *p;
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300432 iter = rb_entry(parent, struct hist_entry, rb_node_in);
John Kacur3d1d07e2009-09-28 15:32:55 +0200433
434 cmp = hist_entry__collapse(iter, he);
435
436 if (!cmp) {
Namhyung Kim139c0812012-10-04 21:49:43 +0900437 he_stat__add_stat(&iter->stat, &he->stat);
Namhyung Kim9ec60972012-09-26 16:47:28 +0900438
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100439 if (symbol_conf.use_callchain) {
Namhyung Kim47260642012-05-31 14:43:26 +0900440 callchain_cursor_reset(&callchain_cursor);
441 callchain_merge(&callchain_cursor,
442 iter->callchain,
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100443 he->callchain);
444 }
John Kacur3d1d07e2009-09-28 15:32:55 +0200445 hist_entry__free(he);
Arnaldo Carvalho de Melofefb0b92010-05-10 13:57:51 -0300446 return false;
John Kacur3d1d07e2009-09-28 15:32:55 +0200447 }
448
449 if (cmp < 0)
450 p = &(*p)->rb_left;
451 else
452 p = &(*p)->rb_right;
453 }
454
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300455 rb_link_node(&he->rb_node_in, parent, p);
456 rb_insert_color(&he->rb_node_in, root);
Arnaldo Carvalho de Melofefb0b92010-05-10 13:57:51 -0300457 return true;
John Kacur3d1d07e2009-09-28 15:32:55 +0200458}
459
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300460static struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
461{
462 struct rb_root *root;
463
464 pthread_mutex_lock(&hists->lock);
465
466 root = hists->entries_in;
467 if (++hists->entries_in > &hists->entries_in_array[1])
468 hists->entries_in = &hists->entries_in_array[0];
469
470 pthread_mutex_unlock(&hists->lock);
471
472 return root;
473}
474
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200475static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
476{
477 hists__filter_entry_by_dso(hists, he);
478 hists__filter_entry_by_thread(hists, he);
Namhyung Kime94d53e2012-03-16 17:50:51 +0900479 hists__filter_entry_by_symbol(hists, he);
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200480}
481
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300482static void __hists__collapse_resort(struct hists *hists, bool threaded)
483{
484 struct rb_root *root;
485 struct rb_node *next;
486 struct hist_entry *n;
487
488 if (!sort__need_collapse && !threaded)
489 return;
490
491 root = hists__get_rotate_entries_in(hists);
492 next = rb_first(root);
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300493
494 while (next) {
495 n = rb_entry(next, struct hist_entry, rb_node_in);
496 next = rb_next(&n->rb_node_in);
497
498 rb_erase(&n->rb_node_in, root);
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200499 if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
500 /*
501 * If it wasn't combined with one of the entries already
502 * collapsed, we need to apply the filters that may have
503 * been set by, say, the hist_browser.
504 */
505 hists__apply_filters(hists, n);
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200506 }
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300507 }
508}
509
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300510void hists__collapse_resort(struct hists *hists)
John Kacur3d1d07e2009-09-28 15:32:55 +0200511{
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300512 return __hists__collapse_resort(hists, false);
513}
John Kacur3d1d07e2009-09-28 15:32:55 +0200514
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300515void hists__collapse_resort_threaded(struct hists *hists)
516{
517 return __hists__collapse_resort(hists, true);
John Kacur3d1d07e2009-09-28 15:32:55 +0200518}
519
520/*
Arnaldo Carvalho de Meloc82ee822010-05-14 14:19:35 -0300521 * reverse the map, sort on period.
John Kacur3d1d07e2009-09-28 15:32:55 +0200522 */
523
Arnaldo Carvalho de Melo1c02c4d2010-05-10 13:04:11 -0300524static void __hists__insert_output_entry(struct rb_root *entries,
525 struct hist_entry *he,
526 u64 min_callchain_hits)
John Kacur3d1d07e2009-09-28 15:32:55 +0200527{
Arnaldo Carvalho de Melo1c02c4d2010-05-10 13:04:11 -0300528 struct rb_node **p = &entries->rb_node;
John Kacur3d1d07e2009-09-28 15:32:55 +0200529 struct rb_node *parent = NULL;
530 struct hist_entry *iter;
531
Arnaldo Carvalho de Melod599db32009-12-15 20:04:42 -0200532 if (symbol_conf.use_callchain)
Arnaldo Carvalho de Melob9fb9302010-04-02 09:50:42 -0300533 callchain_param.sort(&he->sorted_chain, he->callchain,
John Kacur3d1d07e2009-09-28 15:32:55 +0200534 min_callchain_hits, &callchain_param);
535
536 while (*p != NULL) {
537 parent = *p;
538 iter = rb_entry(parent, struct hist_entry, rb_node);
539
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900540 if (he->stat.period > iter->stat.period)
John Kacur3d1d07e2009-09-28 15:32:55 +0200541 p = &(*p)->rb_left;
542 else
543 p = &(*p)->rb_right;
544 }
545
546 rb_link_node(&he->rb_node, parent, p);
Arnaldo Carvalho de Melo1c02c4d2010-05-10 13:04:11 -0300547 rb_insert_color(&he->rb_node, entries);
John Kacur3d1d07e2009-09-28 15:32:55 +0200548}
549
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300550static void __hists__output_resort(struct hists *hists, bool threaded)
John Kacur3d1d07e2009-09-28 15:32:55 +0200551{
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300552 struct rb_root *root;
John Kacur3d1d07e2009-09-28 15:32:55 +0200553 struct rb_node *next;
554 struct hist_entry *n;
John Kacur3d1d07e2009-09-28 15:32:55 +0200555 u64 min_callchain_hits;
556
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300557 min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100);
John Kacur3d1d07e2009-09-28 15:32:55 +0200558
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300559 if (sort__need_collapse || threaded)
560 root = &hists->entries_collapsed;
561 else
562 root = hists->entries_in;
563
564 next = rb_first(root);
565 hists->entries = RB_ROOT;
John Kacur3d1d07e2009-09-28 15:32:55 +0200566
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300567 hists->nr_entries = 0;
Arnaldo Carvalho de Melo79286312011-10-27 09:19:48 -0200568 hists->stats.total_period = 0;
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300569 hists__reset_col_len(hists);
Arnaldo Carvalho de Melofefb0b92010-05-10 13:57:51 -0300570
John Kacur3d1d07e2009-09-28 15:32:55 +0200571 while (next) {
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300572 n = rb_entry(next, struct hist_entry, rb_node_in);
573 next = rb_next(&n->rb_node_in);
John Kacur3d1d07e2009-09-28 15:32:55 +0200574
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300575 __hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300576 hists__inc_nr_entries(hists, n);
John Kacur3d1d07e2009-09-28 15:32:55 +0200577 }
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300578}
Arnaldo Carvalho de Melob9bf0892009-12-14 11:37:11 -0200579
Arnaldo Carvalho de Melo1980c2eb2011-10-05 17:50:23 -0300580void hists__output_resort(struct hists *hists)
581{
582 return __hists__output_resort(hists, false);
583}
584
585void hists__output_resort_threaded(struct hists *hists)
586{
587 return __hists__output_resort(hists, true);
John Kacur3d1d07e2009-09-28 15:32:55 +0200588}
Arnaldo Carvalho de Melo4ecf84d02009-12-16 12:27:09 -0200589
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300590static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
Arnaldo Carvalho de Melocc5edb02010-07-16 12:35:07 -0300591 enum hist_filter filter)
592{
593 h->filtered &= ~(1 << filter);
594 if (h->filtered)
595 return;
596
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300597 ++hists->nr_entries;
Arnaldo Carvalho de Melo0f0cbf72010-07-26 17:13:40 -0300598 if (h->ms.unfolded)
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300599 hists->nr_entries += h->nr_rows;
Arnaldo Carvalho de Melo0f0cbf72010-07-26 17:13:40 -0300600 h->row_offset = 0;
Namhyung Kimb24c28f2012-10-04 21:49:41 +0900601 hists->stats.total_period += h->stat.period;
602 hists->stats.nr_events[PERF_RECORD_SAMPLE] += h->stat.nr_events;
Arnaldo Carvalho de Melocc5edb02010-07-16 12:35:07 -0300603
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300604 hists__calc_col_len(hists, h);
Arnaldo Carvalho de Melocc5edb02010-07-16 12:35:07 -0300605}
606
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200607
608static bool hists__filter_entry_by_dso(struct hists *hists,
609 struct hist_entry *he)
610{
611 if (hists->dso_filter != NULL &&
612 (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) {
613 he->filtered |= (1 << HIST_FILTER__DSO);
614 return true;
615 }
616
617 return false;
618}
619
Arnaldo Carvalho de Melod7b76f02011-10-18 19:07:34 -0200620void hists__filter_by_dso(struct hists *hists)
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300621{
622 struct rb_node *nd;
623
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300624 hists->nr_entries = hists->stats.total_period = 0;
625 hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
626 hists__reset_col_len(hists);
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300627
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300628 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300629 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
630
631 if (symbol_conf.exclude_other && !h->parent)
632 continue;
633
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200634 if (hists__filter_entry_by_dso(hists, h))
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300635 continue;
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300636
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300637 hists__remove_entry_filter(hists, h, HIST_FILTER__DSO);
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300638 }
639}
640
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200641static bool hists__filter_entry_by_thread(struct hists *hists,
642 struct hist_entry *he)
643{
644 if (hists->thread_filter != NULL &&
645 he->thread != hists->thread_filter) {
646 he->filtered |= (1 << HIST_FILTER__THREAD);
647 return true;
648 }
649
650 return false;
651}
652
Arnaldo Carvalho de Melod7b76f02011-10-18 19:07:34 -0200653void hists__filter_by_thread(struct hists *hists)
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300654{
655 struct rb_node *nd;
656
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300657 hists->nr_entries = hists->stats.total_period = 0;
658 hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
659 hists__reset_col_len(hists);
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300660
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300661 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300662 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
663
Arnaldo Carvalho de Melo90cf1fb2011-10-19 13:09:10 -0200664 if (hists__filter_entry_by_thread(hists, h))
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300665 continue;
Arnaldo Carvalho de Melocc5edb02010-07-16 12:35:07 -0300666
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300667 hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD);
Arnaldo Carvalho de Melob09e0192010-05-11 11:10:15 -0300668 }
669}
Arnaldo Carvalho de Meloef7b93a2010-05-11 23:18:06 -0300670
Namhyung Kime94d53e2012-03-16 17:50:51 +0900671static bool hists__filter_entry_by_symbol(struct hists *hists,
672 struct hist_entry *he)
673{
674 if (hists->symbol_filter_str != NULL &&
675 (!he->ms.sym || strstr(he->ms.sym->name,
676 hists->symbol_filter_str) == NULL)) {
677 he->filtered |= (1 << HIST_FILTER__SYMBOL);
678 return true;
679 }
680
681 return false;
682}
683
684void hists__filter_by_symbol(struct hists *hists)
685{
686 struct rb_node *nd;
687
688 hists->nr_entries = hists->stats.total_period = 0;
689 hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
690 hists__reset_col_len(hists);
691
692 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
693 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
694
695 if (hists__filter_entry_by_symbol(hists, h))
696 continue;
697
698 hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL);
699 }
700}
701
Arnaldo Carvalho de Melo2f525d02011-02-04 13:43:24 -0200702int hist_entry__inc_addr_samples(struct hist_entry *he, int evidx, u64 ip)
Arnaldo Carvalho de Meloef7b93a2010-05-11 23:18:06 -0300703{
Arnaldo Carvalho de Melo2f525d02011-02-04 13:43:24 -0200704 return symbol__inc_addr_samples(he->ms.sym, he->ms.map, evidx, ip);
Arnaldo Carvalho de Meloef7b93a2010-05-11 23:18:06 -0300705}
706
Arnaldo Carvalho de Meloce6f4fa2011-02-08 13:27:39 -0200707int hist_entry__annotate(struct hist_entry *he, size_t privsize)
Arnaldo Carvalho de Meloef7b93a2010-05-11 23:18:06 -0300708{
Arnaldo Carvalho de Meloce6f4fa2011-02-08 13:27:39 -0200709 return symbol__annotate(he->ms.sym, he->ms.map, privsize);
Arnaldo Carvalho de Meloef7b93a2010-05-11 23:18:06 -0300710}
Arnaldo Carvalho de Meloc8446b92010-05-14 10:36:42 -0300711
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300712void hists__inc_nr_events(struct hists *hists, u32 type)
Arnaldo Carvalho de Meloc8446b92010-05-14 10:36:42 -0300713{
Arnaldo Carvalho de Melo42b28ac2011-09-26 12:33:28 -0300714 ++hists->stats.nr_events[0];
715 ++hists->stats.nr_events[type];
Arnaldo Carvalho de Meloc8446b92010-05-14 10:36:42 -0300716}