diff options
Diffstat (limited to 'tools/perf/util/hist.c')
| -rw-r--r-- | tools/perf/util/hist.c | 1894 |
1 files changed, 1065 insertions, 829 deletions
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c index 2022e874099..30df6187ee0 100644 --- a/tools/perf/util/hist.c +++ b/tools/perf/util/hist.c @@ -3,111 +3,348 @@ #include "hist.h" #include "session.h" #include "sort.h" +#include "evsel.h" +#include "annotate.h" #include <math.h> -enum hist_filter { - HIST_FILTER__DSO, - HIST_FILTER__THREAD, - HIST_FILTER__PARENT, -}; +static bool hists__filter_entry_by_dso(struct hists *hists, + struct hist_entry *he); +static bool hists__filter_entry_by_thread(struct hists *hists, + struct hist_entry *he); +static bool hists__filter_entry_by_symbol(struct hists *hists, + struct hist_entry *he); struct callchain_param callchain_param = { .mode = CHAIN_GRAPH_REL, - .min_percent = 0.5 + .min_percent = 0.5, + .order = ORDER_CALLEE, + .key = CCKEY_FUNCTION }; -u16 hists__col_len(struct hists *self, enum hist_column col) +u16 hists__col_len(struct hists *hists, enum hist_column col) { - return self->col_len[col]; + return hists->col_len[col]; } -void hists__set_col_len(struct hists *self, enum hist_column col, u16 len) +void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len) { - self->col_len[col] = len; + hists->col_len[col] = len; } -bool hists__new_col_len(struct hists *self, enum hist_column col, u16 len) +bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len) { - if (len > hists__col_len(self, col)) { - hists__set_col_len(self, col, len); + if (len > hists__col_len(hists, col)) { + hists__set_col_len(hists, col, len); return true; } return false; } -static void hists__reset_col_len(struct hists *self) +void hists__reset_col_len(struct hists *hists) { enum hist_column col; for (col = 0; col < HISTC_NR_COLS; ++col) - hists__set_col_len(self, col, 0); + hists__set_col_len(hists, col, 0); +} + +static void hists__set_unres_dso_col_len(struct hists *hists, int dso) +{ + const unsigned int unresolved_col_width = BITS_PER_LONG / 4; + + if (hists__col_len(hists, dso) < unresolved_col_width && + !symbol_conf.col_width_list_str && !symbol_conf.field_sep && + !symbol_conf.dso_list) + hists__set_col_len(hists, dso, unresolved_col_width); } -static void hists__calc_col_len(struct hists *self, struct hist_entry *h) +void hists__calc_col_len(struct hists *hists, struct hist_entry *h) { + const unsigned int unresolved_col_width = BITS_PER_LONG / 4; + int symlen; u16 len; - if (h->ms.sym) - hists__new_col_len(self, HISTC_SYMBOL, h->ms.sym->namelen); + /* + * +4 accounts for '[x] ' priv level info + * +2 accounts for 0x prefix on raw addresses + * +3 accounts for ' y ' symtab origin info + */ + if (h->ms.sym) { + symlen = h->ms.sym->namelen + 4; + if (verbose) + symlen += BITS_PER_LONG / 4 + 2 + 3; + hists__new_col_len(hists, HISTC_SYMBOL, symlen); + } else { + symlen = unresolved_col_width + 4 + 2; + hists__new_col_len(hists, HISTC_SYMBOL, symlen); + hists__set_unres_dso_col_len(hists, HISTC_DSO); + } len = thread__comm_len(h->thread); - if (hists__new_col_len(self, HISTC_COMM, len)) - hists__set_col_len(self, HISTC_THREAD, len + 6); + if (hists__new_col_len(hists, HISTC_COMM, len)) + hists__set_col_len(hists, HISTC_THREAD, len + 6); if (h->ms.map) { len = dso__name_len(h->ms.map->dso); - hists__new_col_len(self, HISTC_DSO, len); + hists__new_col_len(hists, HISTC_DSO, len); } + + if (h->parent) + hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen); + + if (h->branch_info) { + if (h->branch_info->from.sym) { + symlen = (int)h->branch_info->from.sym->namelen + 4; + if (verbose) + symlen += BITS_PER_LONG / 4 + 2 + 3; + hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen); + + symlen = dso__name_len(h->branch_info->from.map->dso); + hists__new_col_len(hists, HISTC_DSO_FROM, symlen); + } else { + symlen = unresolved_col_width + 4 + 2; + hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen); + hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM); + } + + if (h->branch_info->to.sym) { + symlen = (int)h->branch_info->to.sym->namelen + 4; + if (verbose) + symlen += BITS_PER_LONG / 4 + 2 + 3; + hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen); + + symlen = dso__name_len(h->branch_info->to.map->dso); + hists__new_col_len(hists, HISTC_DSO_TO, symlen); + } else { + symlen = unresolved_col_width + 4 + 2; + hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen); + hists__set_unres_dso_col_len(hists, HISTC_DSO_TO); + } + } + + if (h->mem_info) { + if (h->mem_info->daddr.sym) { + symlen = (int)h->mem_info->daddr.sym->namelen + 4 + + unresolved_col_width + 2; + hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, + symlen); + hists__new_col_len(hists, HISTC_MEM_DCACHELINE, + symlen + 1); + } else { + symlen = unresolved_col_width + 4 + 2; + hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, + symlen); + } + if (h->mem_info->daddr.map) { + symlen = dso__name_len(h->mem_info->daddr.map->dso); + hists__new_col_len(hists, HISTC_MEM_DADDR_DSO, + symlen); + } else { + symlen = unresolved_col_width + 4 + 2; + hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO); + } + } else { + symlen = unresolved_col_width + 4 + 2; + hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, symlen); + hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO); + } + + hists__new_col_len(hists, HISTC_MEM_LOCKED, 6); + hists__new_col_len(hists, HISTC_MEM_TLB, 22); + hists__new_col_len(hists, HISTC_MEM_SNOOP, 12); + hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3); + hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12); + hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12); + + if (h->transaction) + hists__new_col_len(hists, HISTC_TRANSACTION, + hist_entry__transaction_len()); } -static void hist_entry__add_cpumode_period(struct hist_entry *self, - unsigned int cpumode, u64 period) +void hists__output_recalc_col_len(struct hists *hists, int max_rows) +{ + struct rb_node *next = rb_first(&hists->entries); + struct hist_entry *n; + int row = 0; + + hists__reset_col_len(hists); + + while (next && row++ < max_rows) { + n = rb_entry(next, struct hist_entry, rb_node); + if (!n->filtered) + hists__calc_col_len(hists, n); + next = rb_next(&n->rb_node); + } +} + +static void he_stat__add_cpumode_period(struct he_stat *he_stat, + unsigned int cpumode, u64 period) { switch (cpumode) { case PERF_RECORD_MISC_KERNEL: - self->period_sys += period; + he_stat->period_sys += period; break; case PERF_RECORD_MISC_USER: - self->period_us += period; + he_stat->period_us += period; break; case PERF_RECORD_MISC_GUEST_KERNEL: - self->period_guest_sys += period; + he_stat->period_guest_sys += period; break; case PERF_RECORD_MISC_GUEST_USER: - self->period_guest_us += period; + he_stat->period_guest_us += period; break; default: break; } } +static void he_stat__add_period(struct he_stat *he_stat, u64 period, + u64 weight) +{ + + he_stat->period += period; + he_stat->weight += weight; + he_stat->nr_events += 1; +} + +static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src) +{ + dest->period += src->period; + dest->period_sys += src->period_sys; + dest->period_us += src->period_us; + dest->period_guest_sys += src->period_guest_sys; + dest->period_guest_us += src->period_guest_us; + dest->nr_events += src->nr_events; + dest->weight += src->weight; +} + +static void he_stat__decay(struct he_stat *he_stat) +{ + he_stat->period = (he_stat->period * 7) / 8; + he_stat->nr_events = (he_stat->nr_events * 7) / 8; + /* XXX need decay for weight too? */ +} + +static bool hists__decay_entry(struct hists *hists, struct hist_entry *he) +{ + u64 prev_period = he->stat.period; + u64 diff; + + if (prev_period == 0) + return true; + + he_stat__decay(&he->stat); + if (symbol_conf.cumulate_callchain) + he_stat__decay(he->stat_acc); + + diff = prev_period - he->stat.period; + + hists->stats.total_period -= diff; + if (!he->filtered) + hists->stats.total_non_filtered_period -= diff; + + return he->stat.period == 0; +} + +void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel) +{ + struct rb_node *next = rb_first(&hists->entries); + struct hist_entry *n; + + while (next) { + n = rb_entry(next, struct hist_entry, rb_node); + next = rb_next(&n->rb_node); + /* + * We may be annotating this, for instance, so keep it here in + * case some it gets new samples, we'll eventually free it when + * the user stops browsing and it agains gets fully decayed. + */ + if (((zap_user && n->level == '.') || + (zap_kernel && n->level != '.') || + hists__decay_entry(hists, n)) && + !n->used) { + rb_erase(&n->rb_node, &hists->entries); + + if (sort__need_collapse) + rb_erase(&n->rb_node_in, &hists->entries_collapsed); + + --hists->nr_entries; + if (!n->filtered) + --hists->nr_non_filtered_entries; + + hist_entry__free(n); + } + } +} + /* * histogram, sorted on item, collects periods */ -static struct hist_entry *hist_entry__new(struct hist_entry *template) +static struct hist_entry *hist_entry__new(struct hist_entry *template, + bool sample_self) { - size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_root) : 0; - struct hist_entry *self = malloc(sizeof(*self) + callchain_size); + size_t callchain_size = 0; + struct hist_entry *he; - if (self != NULL) { - *self = *template; - self->nr_events = 1; - if (self->ms.map) - self->ms.map->referenced = true; - if (symbol_conf.use_callchain) - callchain_init(self->callchain); - } + if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain) + callchain_size = sizeof(struct callchain_root); - return self; -} + he = zalloc(sizeof(*he) + callchain_size); -static void hists__inc_nr_entries(struct hists *self, struct hist_entry *h) -{ - if (!h->filtered) { - hists__calc_col_len(self, h); - ++self->nr_entries; + if (he != NULL) { + *he = *template; + + if (symbol_conf.cumulate_callchain) { + he->stat_acc = malloc(sizeof(he->stat)); + if (he->stat_acc == NULL) { + free(he); + return NULL; + } + memcpy(he->stat_acc, &he->stat, sizeof(he->stat)); + if (!sample_self) + memset(&he->stat, 0, sizeof(he->stat)); + } + + if (he->ms.map) + he->ms.map->referenced = true; + + if (he->branch_info) { + /* + * This branch info is (a part of) allocated from + * sample__resolve_bstack() and will be freed after + * adding new entries. So we need to save a copy. + */ + he->branch_info = malloc(sizeof(*he->branch_info)); + if (he->branch_info == NULL) { + free(he->stat_acc); + free(he); + return NULL; + } + + memcpy(he->branch_info, template->branch_info, + sizeof(*he->branch_info)); + + if (he->branch_info->from.map) + he->branch_info->from.map->referenced = true; + if (he->branch_info->to.map) + he->branch_info->to.map->referenced = true; + } + + if (he->mem_info) { + if (he->mem_info->iaddr.map) + he->mem_info->iaddr.map->referenced = true; + if (he->mem_info->daddr.map) + he->mem_info->daddr.map->referenced = true; + } + + if (symbol_conf.use_callchain) + callchain_init(he->callchain); + + INIT_LIST_HEAD(&he->pairs.node); } + + return he; } static u8 symbol__parent_filter(const struct symbol *parent) @@ -117,37 +354,55 @@ static u8 symbol__parent_filter(const struct symbol *parent) return 0; } -struct hist_entry *__hists__add_entry(struct hists *self, - struct addr_location *al, - struct symbol *sym_parent, u64 period) +static struct hist_entry *add_hist_entry(struct hists *hists, + struct hist_entry *entry, + struct addr_location *al, + bool sample_self) { - struct rb_node **p = &self->entries.rb_node; + struct rb_node **p; struct rb_node *parent = NULL; struct hist_entry *he; - struct hist_entry entry = { - .thread = al->thread, - .ms = { - .map = al->map, - .sym = al->sym, - }, - .cpu = al->cpu, - .ip = al->addr, - .level = al->level, - .period = period, - .parent = sym_parent, - .filtered = symbol__parent_filter(sym_parent), - }; - int cmp; + int64_t cmp; + u64 period = entry->stat.period; + u64 weight = entry->stat.weight; + + p = &hists->entries_in->rb_node; while (*p != NULL) { parent = *p; - he = rb_entry(parent, struct hist_entry, rb_node); + he = rb_entry(parent, struct hist_entry, rb_node_in); - cmp = hist_entry__cmp(&entry, he); + /* + * Make sure that it receives arguments in a same order as + * hist_entry__collapse() so that we can use an appropriate + * function when searching an entry regardless which sort + * keys were used. + */ + cmp = hist_entry__cmp(he, entry); if (!cmp) { - he->period += period; - ++he->nr_events; + if (sample_self) + he_stat__add_period(&he->stat, period, weight); + if (symbol_conf.cumulate_callchain) + he_stat__add_period(he->stat_acc, period, weight); + + /* + * This mem info was allocated from sample__resolve_mem + * and will not be used anymore. + */ + zfree(&entry->mem_info); + + /* If the map of an existing hist_entry has + * become out-of-date due to an exec() or + * similar, update it. Otherwise we will + * mis-adjust symbol addresses when computing + * the history counter to increment. + */ + if (he->ms.map != entry->ms.map) { + he->ms.map = entry->ms.map; + if (he->ms.map) + he->ms.map->referenced = true; + } goto out; } @@ -157,1022 +412,1003 @@ struct hist_entry *__hists__add_entry(struct hists *self, p = &(*p)->rb_right; } - he = hist_entry__new(&entry); + he = hist_entry__new(entry, sample_self); if (!he) return NULL; - rb_link_node(&he->rb_node, parent, p); - rb_insert_color(&he->rb_node, &self->entries); - hists__inc_nr_entries(self, he); + + rb_link_node(&he->rb_node_in, parent, p); + rb_insert_color(&he->rb_node_in, hists->entries_in); out: - hist_entry__add_cpumode_period(he, al->cpumode, period); + if (sample_self) + he_stat__add_cpumode_period(&he->stat, al->cpumode, period); + if (symbol_conf.cumulate_callchain) + he_stat__add_cpumode_period(he->stat_acc, al->cpumode, period); return he; } -int64_t -hist_entry__cmp(struct hist_entry *left, struct hist_entry *right) +struct hist_entry *__hists__add_entry(struct hists *hists, + struct addr_location *al, + struct symbol *sym_parent, + struct branch_info *bi, + struct mem_info *mi, + u64 period, u64 weight, u64 transaction, + bool sample_self) { - struct sort_entry *se; - int64_t cmp = 0; - - list_for_each_entry(se, &hist_entry__sort_list, list) { - cmp = se->se_cmp(left, right); - if (cmp) - break; - } + struct hist_entry entry = { + .thread = al->thread, + .comm = thread__comm(al->thread), + .ms = { + .map = al->map, + .sym = al->sym, + }, + .cpu = al->cpu, + .cpumode = al->cpumode, + .ip = al->addr, + .level = al->level, + .stat = { + .nr_events = 1, + .period = period, + .weight = weight, + }, + .parent = sym_parent, + .filtered = symbol__parent_filter(sym_parent) | al->filtered, + .hists = hists, + .branch_info = bi, + .mem_info = mi, + .transaction = transaction, + }; - return cmp; + return add_hist_entry(hists, &entry, al, sample_self); } -int64_t -hist_entry__collapse(struct hist_entry *left, struct hist_entry *right) +static int +iter_next_nop_entry(struct hist_entry_iter *iter __maybe_unused, + struct addr_location *al __maybe_unused) { - struct sort_entry *se; - int64_t cmp = 0; + return 0; +} - list_for_each_entry(se, &hist_entry__sort_list, list) { - int64_t (*f)(struct hist_entry *, struct hist_entry *); +static int +iter_add_next_nop_entry(struct hist_entry_iter *iter __maybe_unused, + struct addr_location *al __maybe_unused) +{ + return 0; +} - f = se->se_collapse ?: se->se_cmp; +static int +iter_prepare_mem_entry(struct hist_entry_iter *iter, struct addr_location *al) +{ + struct perf_sample *sample = iter->sample; + struct mem_info *mi; - cmp = f(left, right); - if (cmp) - break; - } + mi = sample__resolve_mem(sample, al); + if (mi == NULL) + return -ENOMEM; - return cmp; + iter->priv = mi; + return 0; } -void hist_entry__free(struct hist_entry *he) +static int +iter_add_single_mem_entry(struct hist_entry_iter *iter, struct addr_location *al) { - free(he); -} + u64 cost; + struct mem_info *mi = iter->priv; + struct hist_entry *he; -/* - * collapse the histogram - */ + if (mi == NULL) + return -EINVAL; + + cost = iter->sample->weight; + if (!cost) + cost = 1; + + /* + * must pass period=weight in order to get the correct + * sorting from hists__collapse_resort() which is solely + * based on periods. We want sorting be done on nr_events * weight + * and this is indirectly achieved by passing period=weight here + * and the he_stat__add_period() function. + */ + he = __hists__add_entry(&iter->evsel->hists, al, iter->parent, NULL, mi, + cost, cost, 0, true); + if (!he) + return -ENOMEM; + + iter->he = he; + return 0; +} -static bool collapse__insert_entry(struct rb_root *root, struct hist_entry *he) +static int +iter_finish_mem_entry(struct hist_entry_iter *iter, + struct addr_location *al __maybe_unused) { - struct rb_node **p = &root->rb_node; - struct rb_node *parent = NULL; - struct hist_entry *iter; - int64_t cmp; + struct perf_evsel *evsel = iter->evsel; + struct hist_entry *he = iter->he; + int err = -EINVAL; - while (*p != NULL) { - parent = *p; - iter = rb_entry(parent, struct hist_entry, rb_node); + if (he == NULL) + goto out; - cmp = hist_entry__collapse(iter, he); + hists__inc_nr_samples(&evsel->hists, he->filtered); - if (!cmp) { - iter->period += he->period; - if (symbol_conf.use_callchain) - callchain_merge(iter->callchain, he->callchain); - hist_entry__free(he); - return false; - } + err = hist_entry__append_callchain(he, iter->sample); - if (cmp < 0) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } +out: + /* + * We don't need to free iter->priv (mem_info) here since + * the mem info was either already freed in add_hist_entry() or + * passed to a new hist entry by hist_entry__new(). + */ + iter->priv = NULL; - rb_link_node(&he->rb_node, parent, p); - rb_insert_color(&he->rb_node, root); - return true; + iter->he = NULL; + return err; } -void hists__collapse_resort(struct hists *self) +static int +iter_prepare_branch_entry(struct hist_entry_iter *iter, struct addr_location *al) { - struct rb_root tmp; - struct rb_node *next; - struct hist_entry *n; + struct branch_info *bi; + struct perf_sample *sample = iter->sample; - if (!sort__need_collapse) - return; + bi = sample__resolve_bstack(sample, al); + if (!bi) + return -ENOMEM; - tmp = RB_ROOT; - next = rb_first(&self->entries); - self->nr_entries = 0; - hists__reset_col_len(self); + iter->curr = 0; + iter->total = sample->branch_stack->nr; - while (next) { - n = rb_entry(next, struct hist_entry, rb_node); - next = rb_next(&n->rb_node); + iter->priv = bi; + return 0; +} - rb_erase(&n->rb_node, &self->entries); - if (collapse__insert_entry(&tmp, n)) - hists__inc_nr_entries(self, n); - } +static int +iter_add_single_branch_entry(struct hist_entry_iter *iter __maybe_unused, + struct addr_location *al __maybe_unused) +{ + /* to avoid calling callback function */ + iter->he = NULL; - self->entries = tmp; + return 0; } -/* - * reverse the map, sort on period. - */ - -static void __hists__insert_output_entry(struct rb_root *entries, - struct hist_entry *he, - u64 min_callchain_hits) +static int +iter_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al) { - struct rb_node **p = &entries->rb_node; - struct rb_node *parent = NULL; - struct hist_entry *iter; - - if (symbol_conf.use_callchain) - callchain_param.sort(&he->sorted_chain, he->callchain, - min_callchain_hits, &callchain_param); + struct branch_info *bi = iter->priv; + int i = iter->curr; - while (*p != NULL) { - parent = *p; - iter = rb_entry(parent, struct hist_entry, rb_node); + if (bi == NULL) + return 0; - if (he->period > iter->period) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } + if (iter->curr >= iter->total) + return 0; - rb_link_node(&he->rb_node, parent, p); - rb_insert_color(&he->rb_node, entries); + al->map = bi[i].to.map; + al->sym = bi[i].to.sym; + al->addr = bi[i].to.addr; + return 1; } -void hists__output_resort(struct hists *self) +static int +iter_add_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al) { - struct rb_root tmp; - struct rb_node *next; - struct hist_entry *n; - u64 min_callchain_hits; + struct branch_info *bi; + struct perf_evsel *evsel = iter->evsel; + struct hist_entry *he = NULL; + int i = iter->curr; + int err = 0; - min_callchain_hits = self->stats.total_period * (callchain_param.min_percent / 100); + bi = iter->priv; - tmp = RB_ROOT; - next = rb_first(&self->entries); + if (iter->hide_unresolved && !(bi[i].from.sym && bi[i].to.sym)) + goto out; - self->nr_entries = 0; - hists__reset_col_len(self); + /* + * The report shows the percentage of total branches captured + * and not events sampled. Thus we use a pseudo period of 1. + */ + he = __hists__add_entry(&evsel->hists, al, iter->parent, &bi[i], NULL, + 1, 1, 0, true); + if (he == NULL) + return -ENOMEM; - while (next) { - n = rb_entry(next, struct hist_entry, rb_node); - next = rb_next(&n->rb_node); + hists__inc_nr_samples(&evsel->hists, he->filtered); - rb_erase(&n->rb_node, &self->entries); - __hists__insert_output_entry(&tmp, n, min_callchain_hits); - hists__inc_nr_entries(self, n); - } +out: + iter->he = he; + iter->curr++; + return err; +} + +static int +iter_finish_branch_entry(struct hist_entry_iter *iter, + struct addr_location *al __maybe_unused) +{ + zfree(&iter->priv); + iter->he = NULL; - self->entries = tmp; + return iter->curr >= iter->total ? 0 : -1; } -static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin) +static int +iter_prepare_normal_entry(struct hist_entry_iter *iter __maybe_unused, + struct addr_location *al __maybe_unused) { - int i; - int ret = fprintf(fp, " "); + return 0; +} + +static int +iter_add_single_normal_entry(struct hist_entry_iter *iter, struct addr_location *al) +{ + struct perf_evsel *evsel = iter->evsel; + struct perf_sample *sample = iter->sample; + struct hist_entry *he; - for (i = 0; i < left_margin; i++) - ret += fprintf(fp, " "); + he = __hists__add_entry(&evsel->hists, al, iter->parent, NULL, NULL, + sample->period, sample->weight, + sample->transaction, true); + if (he == NULL) + return -ENOMEM; - return ret; + iter->he = he; + return 0; } -static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask, - int left_margin) +static int +iter_finish_normal_entry(struct hist_entry_iter *iter, + struct addr_location *al __maybe_unused) { - int i; - size_t ret = callchain__fprintf_left_margin(fp, left_margin); + struct hist_entry *he = iter->he; + struct perf_evsel *evsel = iter->evsel; + struct perf_sample *sample = iter->sample; - for (i = 0; i < depth; i++) - if (depth_mask & (1 << i)) - ret += fprintf(fp, "| "); - else - ret += fprintf(fp, " "); + if (he == NULL) + return 0; + + iter->he = NULL; - ret += fprintf(fp, "\n"); + hists__inc_nr_samples(&evsel->hists, he->filtered); - return ret; + return hist_entry__append_callchain(he, sample); } -static size_t ipchain__fprintf_graph(FILE *fp, struct callchain_list *chain, - int depth, int depth_mask, int period, - u64 total_samples, int hits, - int left_margin) +static int +iter_prepare_cumulative_entry(struct hist_entry_iter *iter __maybe_unused, + struct addr_location *al __maybe_unused) { - int i; - size_t ret = 0; + struct hist_entry **he_cache; - ret += callchain__fprintf_left_margin(fp, left_margin); - for (i = 0; i < depth; i++) { - if (depth_mask & (1 << i)) - ret += fprintf(fp, "|"); - else - ret += fprintf(fp, " "); - if (!period && i == depth - 1) { - double percent; - - percent = hits * 100.0 / total_samples; - ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent); - } else - ret += fprintf(fp, "%s", " "); - } - if (chain->ms.sym) - ret += fprintf(fp, "%s\n", chain->ms.sym->name); - else - ret += fprintf(fp, "%p\n", (void *)(long)chain->ip); + callchain_cursor_commit(&callchain_cursor); - return ret; -} + /* + * This is for detecting cycles or recursions so that they're + * cumulated only one time to prevent entries more than 100% + * overhead. + */ + he_cache = malloc(sizeof(*he_cache) * (PERF_MAX_STACK_DEPTH + 1)); + if (he_cache == NULL) + return -ENOMEM; -static struct symbol *rem_sq_bracket; -static struct callchain_list rem_hits; + iter->priv = he_cache; + iter->curr = 0; + + return 0; +} -static void init_rem_hits(void) +static int +iter_add_single_cumulative_entry(struct hist_entry_iter *iter, + struct addr_location *al) { - rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6); - if (!rem_sq_bracket) { - fprintf(stderr, "Not enough memory to display remaining hits\n"); - return; - } + struct perf_evsel *evsel = iter->evsel; + struct perf_sample *sample = iter->sample; + struct hist_entry **he_cache = iter->priv; + struct hist_entry *he; + int err = 0; + + he = __hists__add_entry(&evsel->hists, al, iter->parent, NULL, NULL, + sample->period, sample->weight, + sample->transaction, true); + if (he == NULL) + return -ENOMEM; + + iter->he = he; + he_cache[iter->curr++] = he; + + callchain_append(he->callchain, &callchain_cursor, sample->period); + + /* + * We need to re-initialize the cursor since callchain_append() + * advanced the cursor to the end. + */ + callchain_cursor_commit(&callchain_cursor); + + hists__inc_nr_samples(&evsel->hists, he->filtered); - strcpy(rem_sq_bracket->name, "[...]"); - rem_hits.ms.sym = rem_sq_bracket; + return err; } -static size_t __callchain__fprintf_graph(FILE *fp, struct callchain_node *self, - u64 total_samples, int depth, - int depth_mask, int left_margin) +static int +iter_next_cumulative_entry(struct hist_entry_iter *iter, + struct addr_location *al) { - struct rb_node *node, *next; - struct callchain_node *child; - struct callchain_list *chain; - int new_depth_mask = depth_mask; - u64 new_total; - u64 remaining; - size_t ret = 0; - int i; - uint entries_printed = 0; + struct callchain_cursor_node *node; - if (callchain_param.mode == CHAIN_GRAPH_REL) - new_total = self->children_hit; - else - new_total = total_samples; + node = callchain_cursor_current(&callchain_cursor); + if (node == NULL) + return 0; - remaining = new_total; + return fill_callchain_info(al, node, iter->hide_unresolved); +} - node = rb_first(&self->rb_root); - while (node) { - u64 cumul; +static int +iter_add_next_cumulative_entry(struct hist_entry_iter *iter, + struct addr_location *al) +{ + struct perf_evsel *evsel = iter->evsel; + struct perf_sample *sample = iter->sample; + struct hist_entry **he_cache = iter->priv; + struct hist_entry *he; + struct hist_entry he_tmp = { + .cpu = al->cpu, + .thread = al->thread, + .comm = thread__comm(al->thread), + .ip = al->addr, + .ms = { + .map = al->map, + .sym = al->sym, + }, + .parent = iter->parent, + }; + int i; + struct callchain_cursor cursor; - child = rb_entry(node, struct callchain_node, rb_node); - cumul = cumul_hits(child); - remaining -= cumul; + callchain_cursor_snapshot(&cursor, &callchain_cursor); - /* - * The depth mask manages the output of pipes that show - * the depth. We don't want to keep the pipes of the current - * level for the last child of this depth. - * Except if we have remaining filtered hits. They will - * supersede the last child - */ - next = rb_next(node); - if (!next && (callchain_param.mode != CHAIN_GRAPH_REL || !remaining)) - new_depth_mask &= ~(1 << (depth - 1)); + callchain_cursor_advance(&callchain_cursor); - /* - * But we keep the older depth mask for the line separator - * to keep the level link until we reach the last child - */ - ret += ipchain__fprintf_graph_line(fp, depth, depth_mask, - left_margin); - i = 0; - list_for_each_entry(chain, &child->val, list) { - ret += ipchain__fprintf_graph(fp, chain, depth, - new_depth_mask, i++, - new_total, - cumul, - left_margin); + /* + * Check if there's duplicate entries in the callchain. + * It's possible that it has cycles or recursive calls. + */ + for (i = 0; i < iter->curr; i++) { + if (hist_entry__cmp(he_cache[i], &he_tmp) == 0) { + /* to avoid calling callback function */ + iter->he = NULL; + return 0; } - ret += __callchain__fprintf_graph(fp, child, new_total, - depth + 1, - new_depth_mask | (1 << depth), - left_margin); - node = next; - if (++entries_printed == callchain_param.print_limit) - break; } - if (callchain_param.mode == CHAIN_GRAPH_REL && - remaining && remaining != new_total) { + he = __hists__add_entry(&evsel->hists, al, iter->parent, NULL, NULL, + sample->period, sample->weight, + sample->transaction, false); + if (he == NULL) + return -ENOMEM; - if (!rem_sq_bracket) - return ret; + iter->he = he; + he_cache[iter->curr++] = he; - new_depth_mask &= ~(1 << (depth - 1)); + callchain_append(he->callchain, &cursor, sample->period); + return 0; +} - ret += ipchain__fprintf_graph(fp, &rem_hits, depth, - new_depth_mask, 0, new_total, - remaining, left_margin); - } +static int +iter_finish_cumulative_entry(struct hist_entry_iter *iter, + struct addr_location *al __maybe_unused) +{ + zfree(&iter->priv); + iter->he = NULL; - return ret; + return 0; } -static size_t callchain__fprintf_graph(FILE *fp, struct callchain_node *self, - u64 total_samples, int left_margin) +const struct hist_iter_ops hist_iter_mem = { + .prepare_entry = iter_prepare_mem_entry, + .add_single_entry = iter_add_single_mem_entry, + .next_entry = iter_next_nop_entry, + .add_next_entry = iter_add_next_nop_entry, + .finish_entry = iter_finish_mem_entry, +}; + +const struct hist_iter_ops hist_iter_branch = { + .prepare_entry = iter_prepare_branch_entry, + .add_single_entry = iter_add_single_branch_entry, + .next_entry = iter_next_branch_entry, + .add_next_entry = iter_add_next_branch_entry, + .finish_entry = iter_finish_branch_entry, +}; + +const struct hist_iter_ops hist_iter_normal = { + .prepare_entry = iter_prepare_normal_entry, + .add_single_entry = iter_add_single_normal_entry, + .next_entry = iter_next_nop_entry, + .add_next_entry = iter_add_next_nop_entry, + .finish_entry = iter_finish_normal_entry, +}; + +const struct hist_iter_ops hist_iter_cumulative = { + .prepare_entry = iter_prepare_cumulative_entry, + .add_single_entry = iter_add_single_cumulative_entry, + .next_entry = iter_next_cumulative_entry, + .add_next_entry = iter_add_next_cumulative_entry, + .finish_entry = iter_finish_cumulative_entry, +}; + +int hist_entry_iter__add(struct hist_entry_iter *iter, struct addr_location *al, + struct perf_evsel *evsel, struct perf_sample *sample, + int max_stack_depth, void *arg) { - struct callchain_list *chain; - bool printed = false; - int i = 0; - int ret = 0; - u32 entries_printed = 0; + int err, err2; - list_for_each_entry(chain, &self->val, list) { - if (!i++ && sort__first_dimension == SORT_SYM) - continue; + err = sample__resolve_callchain(sample, &iter->parent, evsel, al, + max_stack_depth); + if (err) + return err; - if (!printed) { - ret += callchain__fprintf_left_margin(fp, left_margin); - ret += fprintf(fp, "|\n"); - ret += callchain__fprintf_left_margin(fp, left_margin); - ret += fprintf(fp, "---"); + iter->evsel = evsel; + iter->sample = sample; - left_margin += 3; - printed = true; - } else - ret += callchain__fprintf_left_margin(fp, left_margin); + err = iter->ops->prepare_entry(iter, al); + if (err) + goto out; - if (chain->ms.sym) - ret += fprintf(fp, " %s\n", chain->ms.sym->name); - else - ret += fprintf(fp, " %p\n", (void *)(long)chain->ip); + err = iter->ops->add_single_entry(iter, al); + if (err) + goto out; - if (++entries_printed == callchain_param.print_limit) + if (iter->he && iter->add_entry_cb) { + err = iter->add_entry_cb(iter, al, true, arg); + if (err) + goto out; + } + + while (iter->ops->next_entry(iter, al)) { + err = iter->ops->add_next_entry(iter, al); + if (err) break; + + if (iter->he && iter->add_entry_cb) { + err = iter->add_entry_cb(iter, al, false, arg); + if (err) + goto out; + } } - ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin); +out: + err2 = iter->ops->finish_entry(iter, al); + if (!err) + err = err2; - return ret; + return err; } -static size_t callchain__fprintf_flat(FILE *fp, struct callchain_node *self, - u64 total_samples) +int64_t +hist_entry__cmp(struct hist_entry *left, struct hist_entry *right) { - struct callchain_list *chain; - size_t ret = 0; - - if (!self) - return 0; - - ret += callchain__fprintf_flat(fp, self->parent, total_samples); - + struct perf_hpp_fmt *fmt; + int64_t cmp = 0; - list_for_each_entry(chain, &self->val, list) { - if (chain->ip >= PERF_CONTEXT_MAX) + perf_hpp__for_each_sort_list(fmt) { + if (perf_hpp__should_skip(fmt)) continue; - if (chain->ms.sym) - ret += fprintf(fp, " %s\n", chain->ms.sym->name); - else - ret += fprintf(fp, " %p\n", - (void *)(long)chain->ip); + + cmp = fmt->cmp(left, right); + if (cmp) + break; } - return ret; + return cmp; } -static size_t hist_entry_callchain__fprintf(FILE *fp, struct hist_entry *self, - u64 total_samples, int left_margin) +int64_t +hist_entry__collapse(struct hist_entry *left, struct hist_entry *right) { - struct rb_node *rb_node; - struct callchain_node *chain; - size_t ret = 0; - u32 entries_printed = 0; + struct perf_hpp_fmt *fmt; + int64_t cmp = 0; - rb_node = rb_first(&self->sorted_chain); - while (rb_node) { - double percent; + perf_hpp__for_each_sort_list(fmt) { + if (perf_hpp__should_skip(fmt)) + continue; - chain = rb_entry(rb_node, struct callchain_node, rb_node); - percent = chain->hit * 100.0 / total_samples; - switch (callchain_param.mode) { - case CHAIN_FLAT: - ret += percent_color_fprintf(fp, " %6.2f%%\n", - percent); - ret += callchain__fprintf_flat(fp, chain, total_samples); - break; - case CHAIN_GRAPH_ABS: /* Falldown */ - case CHAIN_GRAPH_REL: - ret += callchain__fprintf_graph(fp, chain, total_samples, - left_margin); - case CHAIN_NONE: - default: - break; - } - ret += fprintf(fp, "\n"); - if (++entries_printed == callchain_param.print_limit) + cmp = fmt->collapse(left, right); + if (cmp) break; - rb_node = rb_next(rb_node); } - return ret; + return cmp; } -int hist_entry__snprintf(struct hist_entry *self, char *s, size_t size, - struct hists *hists, struct hists *pair_hists, - bool show_displacement, long displacement, - bool color, u64 session_total) +void hist_entry__free(struct hist_entry *he) { - struct sort_entry *se; - u64 period, total, period_sys, period_us, period_guest_sys, period_guest_us; - const char *sep = symbol_conf.field_sep; - int ret; + zfree(&he->branch_info); + zfree(&he->mem_info); + zfree(&he->stat_acc); + free_srcline(he->srcline); + free(he); +} - if (symbol_conf.exclude_other && !self->parent) - return 0; +/* + * collapse the histogram + */ - if (pair_hists) { - period = self->pair ? self->pair->period : 0; - total = pair_hists->stats.total_period; - period_sys = self->pair ? self->pair->period_sys : 0; - period_us = self->pair ? self->pair->period_us : 0; - period_guest_sys = self->pair ? self->pair->period_guest_sys : 0; - period_guest_us = self->pair ? self->pair->period_guest_us : 0; - } else { - period = self->period; - total = session_total; - period_sys = self->period_sys; - period_us = self->period_us; - period_guest_sys = self->period_guest_sys; - period_guest_us = self->period_guest_us; - } +static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused, + struct rb_root *root, + struct hist_entry *he) +{ + struct rb_node **p = &root->rb_node; + struct rb_node *parent = NULL; + struct hist_entry *iter; + int64_t cmp; - if (total) { - if (color) - ret = percent_color_snprintf(s, size, - sep ? "%.2f" : " %6.2f%%", - (period * 100.0) / total); - else - ret = snprintf(s, size, sep ? "%.2f" : " %6.2f%%", - (period * 100.0) / total); - if (symbol_conf.show_cpu_utilization) { - ret += percent_color_snprintf(s + ret, size - ret, - sep ? "%.2f" : " %6.2f%%", - (period_sys * 100.0) / total); - ret += percent_color_snprintf(s + ret, size - ret, - sep ? "%.2f" : " %6.2f%%", - (period_us * 100.0) / total); - if (perf_guest) { - ret += percent_color_snprintf(s + ret, - size - ret, - sep ? "%.2f" : " %6.2f%%", - (period_guest_sys * 100.0) / - total); - ret += percent_color_snprintf(s + ret, - size - ret, - sep ? "%.2f" : " %6.2f%%", - (period_guest_us * 100.0) / - total); + while (*p != NULL) { + parent = *p; + iter = rb_entry(parent, struct hist_entry, rb_node_in); + + cmp = hist_entry__collapse(iter, he); + + if (!cmp) { + he_stat__add_stat(&iter->stat, &he->stat); + if (symbol_conf.cumulate_callchain) + he_stat__add_stat(iter->stat_acc, he->stat_acc); + + if (symbol_conf.use_callchain) { + callchain_cursor_reset(&callchain_cursor); + callchain_merge(&callchain_cursor, + iter->callchain, + he->callchain); } + hist_entry__free(he); + return false; } - } else - ret = snprintf(s, size, sep ? "%lld" : "%12lld ", period); - if (symbol_conf.show_nr_samples) { - if (sep) - ret += snprintf(s + ret, size - ret, "%c%lld", *sep, period); + if (cmp < 0) + p = &(*p)->rb_left; else - ret += snprintf(s + ret, size - ret, "%11lld", period); + p = &(*p)->rb_right; } - if (pair_hists) { - char bf[32]; - double old_percent = 0, new_percent = 0, diff; - - if (total > 0) - old_percent = (period * 100.0) / total; - if (session_total > 0) - new_percent = (self->period * 100.0) / session_total; - - diff = new_percent - old_percent; + rb_link_node(&he->rb_node_in, parent, p); + rb_insert_color(&he->rb_node_in, root); + return true; +} - if (fabs(diff) >= 0.01) - snprintf(bf, sizeof(bf), "%+4.2F%%", diff); - else - snprintf(bf, sizeof(bf), " "); +static struct rb_root *hists__get_rotate_entries_in(struct hists *hists) +{ + struct rb_root *root; - if (sep) - ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf); - else - ret += snprintf(s + ret, size - ret, "%11.11s", bf); - - if (show_displacement) { - if (displacement) - snprintf(bf, sizeof(bf), "%+4ld", displacement); - else - snprintf(bf, sizeof(bf), " "); - - if (sep) - ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf); - else - ret += snprintf(s + ret, size - ret, "%6.6s", bf); - } - } + pthread_mutex_lock(&hists->lock); - list_for_each_entry(se, &hist_entry__sort_list, list) { - if (se->elide) - continue; + root = hists->entries_in; + if (++hists->entries_in > &hists->entries_in_array[1]) + hists->entries_in = &hists->entries_in_array[0]; - ret += snprintf(s + ret, size - ret, "%s", sep ?: " "); - ret += se->se_snprintf(self, s + ret, size - ret, - hists__col_len(hists, se->se_width_idx)); - } + pthread_mutex_unlock(&hists->lock); - return ret; + return root; } -int hist_entry__fprintf(struct hist_entry *self, struct hists *hists, - struct hists *pair_hists, bool show_displacement, - long displacement, FILE *fp, u64 session_total) +static void hists__apply_filters(struct hists *hists, struct hist_entry *he) { - char bf[512]; - hist_entry__snprintf(self, bf, sizeof(bf), hists, pair_hists, - show_displacement, displacement, - true, session_total); - return fprintf(fp, "%s\n", bf); + hists__filter_entry_by_dso(hists, he); + hists__filter_entry_by_thread(hists, he); + hists__filter_entry_by_symbol(hists, he); } -static size_t hist_entry__fprintf_callchain(struct hist_entry *self, - struct hists *hists, FILE *fp, - u64 session_total) +void hists__collapse_resort(struct hists *hists, struct ui_progress *prog) { - int left_margin = 0; + struct rb_root *root; + struct rb_node *next; + struct hist_entry *n; - if (sort__first_dimension == SORT_COMM) { - struct sort_entry *se = list_first_entry(&hist_entry__sort_list, - typeof(*se), list); - left_margin = hists__col_len(hists, se->se_width_idx); - left_margin -= thread__comm_len(self->thread); - } + if (!sort__need_collapse) + return; + + root = hists__get_rotate_entries_in(hists); + next = rb_first(root); - return hist_entry_callchain__fprintf(fp, self, session_total, - left_margin); + while (next) { + if (session_done()) + break; + n = rb_entry(next, struct hist_entry, rb_node_in); + next = rb_next(&n->rb_node_in); + + rb_erase(&n->rb_node_in, root); + if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) { + /* + * If it wasn't combined with one of the entries already + * collapsed, we need to apply the filters that may have + * been set by, say, the hist_browser. + */ + hists__apply_filters(hists, n); + } + if (prog) + ui_progress__update(prog, 1); + } } -size_t hists__fprintf(struct hists *self, struct hists *pair, - bool show_displacement, FILE *fp) +static int hist_entry__sort(struct hist_entry *a, struct hist_entry *b) { - struct sort_entry *se; - struct rb_node *nd; - size_t ret = 0; - unsigned long position = 1; - long displacement = 0; - unsigned int width; - const char *sep = symbol_conf.field_sep; - const char *col_width = symbol_conf.col_width_list_str; - - init_rem_hits(); + struct perf_hpp_fmt *fmt; + int64_t cmp = 0; - fprintf(fp, "# %s", pair ? "Baseline" : "Overhead"); + perf_hpp__for_each_sort_list(fmt) { + if (perf_hpp__should_skip(fmt)) + continue; - if (symbol_conf.show_nr_samples) { - if (sep) - fprintf(fp, "%cSamples", *sep); - else - fputs(" Samples ", fp); + cmp = fmt->sort(a, b); + if (cmp) + break; } - if (symbol_conf.show_cpu_utilization) { - if (sep) { - ret += fprintf(fp, "%csys", *sep); - ret += fprintf(fp, "%cus", *sep); - if (perf_guest) { - ret += fprintf(fp, "%cguest sys", *sep); - ret += fprintf(fp, "%cguest us", *sep); - } - } else { - ret += fprintf(fp, " sys "); - ret += fprintf(fp, " us "); - if (perf_guest) { - ret += fprintf(fp, " guest sys "); - ret += fprintf(fp, " guest us "); - } - } - } + return cmp; +} - if (pair) { - if (sep) - ret += fprintf(fp, "%cDelta", *sep); - else - ret += fprintf(fp, " Delta "); +static void hists__reset_filter_stats(struct hists *hists) +{ + hists->nr_non_filtered_entries = 0; + hists->stats.total_non_filtered_period = 0; +} - if (show_displacement) { - if (sep) - ret += fprintf(fp, "%cDisplacement", *sep); - else - ret += fprintf(fp, " Displ"); - } - } +void hists__reset_stats(struct hists *hists) +{ + hists->nr_entries = 0; + hists->stats.total_period = 0; - list_for_each_entry(se, &hist_entry__sort_list, list) { - if (se->elide) - continue; - if (sep) { - fprintf(fp, "%c%s", *sep, se->se_header); - continue; - } - width = strlen(se->se_header); - if (symbol_conf.col_width_list_str) { - if (col_width) { - hists__set_col_len(self, se->se_width_idx, - atoi(col_width)); - col_width = strchr(col_width, ','); - if (col_width) - ++col_width; - } - } - if (!hists__new_col_len(self, se->se_width_idx, width)) - width = hists__col_len(self, se->se_width_idx); - fprintf(fp, " %*s", width, se->se_header); - } - fprintf(fp, "\n"); - - if (sep) - goto print_entries; - - fprintf(fp, "# ........"); - if (symbol_conf.show_nr_samples) - fprintf(fp, " .........."); - if (pair) { - fprintf(fp, " .........."); - if (show_displacement) - fprintf(fp, " ....."); - } - list_for_each_entry(se, &hist_entry__sort_list, list) { - unsigned int i; + hists__reset_filter_stats(hists); +} - if (se->elide) - continue; +static void hists__inc_filter_stats(struct hists *hists, struct hist_entry *h) +{ + hists->nr_non_filtered_entries++; + hists->stats.total_non_filtered_period += h->stat.period; +} - fprintf(fp, " "); - width = hists__col_len(self, se->se_width_idx); - if (width == 0) - width = strlen(se->se_header); - for (i = 0; i < width; i++) - fprintf(fp, "."); - } +void hists__inc_stats(struct hists *hists, struct hist_entry *h) +{ + if (!h->filtered) + hists__inc_filter_stats(hists, h); - fprintf(fp, "\n#\n"); + hists->nr_entries++; + hists->stats.total_period += h->stat.period; +} -print_entries: - for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) { - struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); +static void __hists__insert_output_entry(struct rb_root *entries, + struct hist_entry *he, + u64 min_callchain_hits) +{ + struct rb_node **p = &entries->rb_node; + struct rb_node *parent = NULL; + struct hist_entry *iter; - if (show_displacement) { - if (h->pair != NULL) - displacement = ((long)h->pair->position - - (long)position); - else - displacement = 0; - ++position; - } - ret += hist_entry__fprintf(h, self, pair, show_displacement, - displacement, fp, self->stats.total_period); + if (symbol_conf.use_callchain) + callchain_param.sort(&he->sorted_chain, he->callchain, + min_callchain_hits, &callchain_param); - if (symbol_conf.use_callchain) - ret += hist_entry__fprintf_callchain(h, self, fp, - self->stats.total_period); - if (h->ms.map == NULL && verbose > 1) { - __map_groups__fprintf_maps(&h->thread->mg, - MAP__FUNCTION, verbose, fp); - fprintf(fp, "%.10s end\n", graph_dotted_line); - } - } + while (*p != NULL) { + parent = *p; + iter = rb_entry(parent, struct hist_entry, rb_node); - free(rem_sq_bracket); + if (hist_entry__sort(he, iter) > 0) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } - return ret; + rb_link_node(&he->rb_node, parent, p); + rb_insert_color(&he->rb_node, entries); } -/* - * See hists__fprintf to match the column widths - */ -unsigned int hists__sort_list_width(struct hists *self) +void hists__output_resort(struct hists *hists) { - struct sort_entry *se; - int ret = 9; /* total % */ + struct rb_root *root; + struct rb_node *next; + struct hist_entry *n; + u64 min_callchain_hits; - if (symbol_conf.show_cpu_utilization) { - ret += 7; /* count_sys % */ - ret += 6; /* count_us % */ - if (perf_guest) { - ret += 13; /* count_guest_sys % */ - ret += 12; /* count_guest_us % */ - } - } + min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100); + + if (sort__need_collapse) + root = &hists->entries_collapsed; + else + root = hists->entries_in; - if (symbol_conf.show_nr_samples) - ret += 11; + next = rb_first(root); + hists->entries = RB_ROOT; - list_for_each_entry(se, &hist_entry__sort_list, list) - if (!se->elide) - ret += 2 + hists__col_len(self, se->se_width_idx); + hists__reset_stats(hists); + hists__reset_col_len(hists); - if (verbose) /* Addr + origin */ - ret += 3 + BITS_PER_LONG / 4; + while (next) { + n = rb_entry(next, struct hist_entry, rb_node_in); + next = rb_next(&n->rb_node_in); + + __hists__insert_output_entry(&hists->entries, n, min_callchain_hits); + hists__inc_stats(hists, n); - return ret; + if (!n->filtered) + hists__calc_col_len(hists, n); + } } -static void hists__remove_entry_filter(struct hists *self, struct hist_entry *h, +static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h, enum hist_filter filter) { h->filtered &= ~(1 << filter); if (h->filtered) return; - ++self->nr_entries; - if (h->ms.unfolded) - self->nr_entries += h->nr_rows; + /* force fold unfiltered entry for simplicity */ + h->ms.unfolded = false; h->row_offset = 0; - self->stats.total_period += h->period; - self->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events; - hists__calc_col_len(self, h); + hists->stats.nr_non_filtered_samples += h->stat.nr_events; + + hists__inc_filter_stats(hists, h); + hists__calc_col_len(hists, h); } -void hists__filter_by_dso(struct hists *self, const struct dso *dso) + +static bool hists__filter_entry_by_dso(struct hists *hists, + struct hist_entry *he) +{ + if (hists->dso_filter != NULL && + (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) { + he->filtered |= (1 << HIST_FILTER__DSO); + return true; + } + + return false; +} + +void hists__filter_by_dso(struct hists *hists) { struct rb_node *nd; - self->nr_entries = self->stats.total_period = 0; - self->stats.nr_events[PERF_RECORD_SAMPLE] = 0; - hists__reset_col_len(self); + hists->stats.nr_non_filtered_samples = 0; + + hists__reset_filter_stats(hists); + hists__reset_col_len(hists); - for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) { + for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) { struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); if (symbol_conf.exclude_other && !h->parent) continue; - if (dso != NULL && (h->ms.map == NULL || h->ms.map->dso != dso)) { - h->filtered |= (1 << HIST_FILTER__DSO); + if (hists__filter_entry_by_dso(hists, h)) continue; - } - hists__remove_entry_filter(self, h, HIST_FILTER__DSO); + hists__remove_entry_filter(hists, h, HIST_FILTER__DSO); + } +} + +static bool hists__filter_entry_by_thread(struct hists *hists, + struct hist_entry *he) +{ + if (hists->thread_filter != NULL && + he->thread != hists->thread_filter) { + he->filtered |= (1 << HIST_FILTER__THREAD); + return true; } + + return false; } -void hists__filter_by_thread(struct hists *self, const struct thread *thread) +void hists__filter_by_thread(struct hists *hists) { struct rb_node *nd; - self->nr_entries = self->stats.total_period = 0; - self->stats.nr_events[PERF_RECORD_SAMPLE] = 0; - hists__reset_col_len(self); + hists->stats.nr_non_filtered_samples = 0; - for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) { + hists__reset_filter_stats(hists); + hists__reset_col_len(hists); + + for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) { struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); - if (thread != NULL && h->thread != thread) { - h->filtered |= (1 << HIST_FILTER__THREAD); + if (hists__filter_entry_by_thread(hists, h)) continue; - } - hists__remove_entry_filter(self, h, HIST_FILTER__THREAD); + hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD); } } -static int symbol__alloc_hist(struct symbol *self) +static bool hists__filter_entry_by_symbol(struct hists *hists, + struct hist_entry *he) { - struct sym_priv *priv = symbol__priv(self); - const int size = (sizeof(*priv->hist) + - (self->end - self->start) * sizeof(u64)); + if (hists->symbol_filter_str != NULL && + (!he->ms.sym || strstr(he->ms.sym->name, + hists->symbol_filter_str) == NULL)) { + he->filtered |= (1 << HIST_FILTER__SYMBOL); + return true; + } - priv->hist = zalloc(size); - return priv->hist == NULL ? -1 : 0; + return false; } -int hist_entry__inc_addr_samples(struct hist_entry *self, u64 ip) +void hists__filter_by_symbol(struct hists *hists) { - unsigned int sym_size, offset; - struct symbol *sym = self->ms.sym; - struct sym_priv *priv; - struct sym_hist *h; - - if (!sym || !self->ms.map) - return 0; - - priv = symbol__priv(sym); - if (priv->hist == NULL && symbol__alloc_hist(sym) < 0) - return -ENOMEM; - - sym_size = sym->end - sym->start; - offset = ip - sym->start; - - pr_debug3("%s: ip=%#Lx\n", __func__, self->ms.map->unmap_ip(self->ms.map, ip)); + struct rb_node *nd; - if (offset >= sym_size) - return 0; + hists->stats.nr_non_filtered_samples = 0; - h = priv->hist; - h->sum++; - h->ip[offset]++; + hists__reset_filter_stats(hists); + hists__reset_col_len(hists); - pr_debug3("%#Lx %s: period++ [ip: %#Lx, %#Lx] => %Ld\n", self->ms.sym->start, - self->ms.sym->name, ip, ip - self->ms.sym->start, h->ip[offset]); - return 0; -} + for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) { + struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); -static struct objdump_line *objdump_line__new(s64 offset, char *line, size_t privsize) -{ - struct objdump_line *self = malloc(sizeof(*self) + privsize); + if (hists__filter_entry_by_symbol(hists, h)) + continue; - if (self != NULL) { - self->offset = offset; - self->line = line; + hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL); } - - return self; } -void objdump_line__free(struct objdump_line *self) +void events_stats__inc(struct events_stats *stats, u32 type) { - free(self->line); - free(self); + ++stats->nr_events[0]; + ++stats->nr_events[type]; } -static void objdump__add_line(struct list_head *head, struct objdump_line *line) +void hists__inc_nr_events(struct hists *hists, u32 type) { - list_add_tail(&line->node, head); + events_stats__inc(&hists->stats, type); } -struct objdump_line *objdump__get_next_ip_line(struct list_head *head, - struct objdump_line *pos) +void hists__inc_nr_samples(struct hists *hists, bool filtered) { - list_for_each_entry_continue(pos, head, node) - if (pos->offset >= 0) - return pos; - - return NULL; + events_stats__inc(&hists->stats, PERF_RECORD_SAMPLE); + if (!filtered) + hists->stats.nr_non_filtered_samples++; } -static int hist_entry__parse_objdump_line(struct hist_entry *self, FILE *file, - struct list_head *head, size_t privsize) +static struct hist_entry *hists__add_dummy_entry(struct hists *hists, + struct hist_entry *pair) { - struct symbol *sym = self->ms.sym; - struct objdump_line *objdump_line; - char *line = NULL, *tmp, *tmp2, *c; - size_t line_len; - s64 line_ip, offset = -1; + struct rb_root *root; + struct rb_node **p; + struct rb_node *parent = NULL; + struct hist_entry *he; + int64_t cmp; - if (getline(&line, &line_len, file) < 0) - return -1; + if (sort__need_collapse) + root = &hists->entries_collapsed; + else + root = hists->entries_in; - if (!line) - return -1; + p = &root->rb_node; - while (line_len != 0 && isspace(line[line_len - 1])) - line[--line_len] = '\0'; + while (*p != NULL) { + parent = *p; + he = rb_entry(parent, struct hist_entry, rb_node_in); - c = strchr(line, '\n'); - if (c) - *c = 0; + cmp = hist_entry__collapse(he, pair); - line_ip = -1; + if (!cmp) + goto out; - /* - * Strip leading spaces: - */ - tmp = line; - while (*tmp) { - if (*tmp != ' ') - break; - tmp++; + if (cmp < 0) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; } - if (*tmp) { - /* - * Parse hexa addresses followed by ':' - */ - line_ip = strtoull(tmp, &tmp2, 16); - if (*tmp2 != ':' || tmp == tmp2 || tmp2[1] == '\0') - line_ip = -1; + he = hist_entry__new(pair, true); + if (he) { + memset(&he->stat, 0, sizeof(he->stat)); + he->hists = hists; + rb_link_node(&he->rb_node_in, parent, p); + rb_insert_color(&he->rb_node_in, root); + hists__inc_stats(hists, he); + he->dummy = true; } +out: + return he; +} - if (line_ip != -1) { - u64 start = map__rip_2objdump(self->ms.map, sym->start), - end = map__rip_2objdump(self->ms.map, sym->end); +static struct hist_entry *hists__find_entry(struct hists *hists, + struct hist_entry *he) +{ + struct rb_node *n; - offset = line_ip - start; - if (offset < 0 || (u64)line_ip > end) - offset = -1; - } + if (sort__need_collapse) + n = hists->entries_collapsed.rb_node; + else + n = hists->entries_in->rb_node; - objdump_line = objdump_line__new(offset, line, privsize); - if (objdump_line == NULL) { - free(line); - return -1; + while (n) { + struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in); + int64_t cmp = hist_entry__collapse(iter, he); + + if (cmp < 0) + n = n->rb_left; + else if (cmp > 0) + n = n->rb_right; + else + return iter; } - objdump__add_line(head, objdump_line); - return 0; + return NULL; } -int hist_entry__annotate(struct hist_entry *self, struct list_head *head, - size_t privsize) +/* + * Look for pairs to link to the leader buckets (hist_entries): + */ +void hists__match(struct hists *leader, struct hists *other) { - struct symbol *sym = self->ms.sym; - struct map *map = self->ms.map; - struct dso *dso = map->dso; - char *filename = dso__build_id_filename(dso, NULL, 0); - bool free_filename = true; - char command[PATH_MAX * 2]; - FILE *file; - int err = 0; - u64 len; - - if (filename == NULL) { - if (dso->has_build_id) { - pr_err("Can't annotate %s: not enough memory\n", - sym->name); - return -ENOMEM; - } - goto fallback; - } else if (readlink(filename, command, sizeof(command)) < 0 || - strstr(command, "[kernel.kallsyms]") || - access(filename, R_OK)) { - free(filename); -fallback: - /* - * If we don't have build-ids or the build-id file isn't in the - * cache, or is just a kallsyms file, well, lets hope that this - * DSO is the same as when 'perf record' ran. - */ - filename = dso->long_name; - free_filename = false; - } - - if (dso->origin == DSO__ORIG_KERNEL) { - if (dso->annotate_warned) - goto out_free_filename; - err = -ENOENT; - dso->annotate_warned = 1; - pr_err("Can't annotate %s: No vmlinux file was found in the " - "path\n", sym->name); - goto out_free_filename; - } + struct rb_root *root; + struct rb_node *nd; + struct hist_entry *pos, *pair; - pr_debug("%s: filename=%s, sym=%s, start=%#Lx, end=%#Lx\n", __func__, - filename, sym->name, map->unmap_ip(map, sym->start), - map->unmap_ip(map, sym->end)); + if (sort__need_collapse) + root = &leader->entries_collapsed; + else + root = leader->entries_in; - len = sym->end - sym->start; + for (nd = rb_first(root); nd; nd = rb_next(nd)) { + pos = rb_entry(nd, struct hist_entry, rb_node_in); + pair = hists__find_entry(other, pos); - pr_debug("annotating [%p] %30s : [%p] %30s\n", - dso, dso->long_name, sym, sym->name); + if (pair) + hist_entry__add_pair(pair, pos); + } +} - snprintf(command, sizeof(command), - "objdump --start-address=0x%016Lx --stop-address=0x%016Lx -dS -C %s|grep -v %s|expand", - map__rip_2objdump(map, sym->start), - map__rip_2objdump(map, sym->end), - filename, filename); +/* + * Look for entries in the other hists that are not present in the leader, if + * we find them, just add a dummy entry on the leader hists, with period=0, + * nr_events=0, to serve as the list header. + */ +int hists__link(struct hists *leader, struct hists *other) +{ + struct rb_root *root; + struct rb_node *nd; + struct hist_entry *pos, *pair; - pr_debug("Executing: %s\n", command); + if (sort__need_collapse) + root = &other->entries_collapsed; + else + root = other->entries_in; - file = popen(command, "r"); - if (!file) - goto out_free_filename; + for (nd = rb_first(root); nd; nd = rb_next(nd)) { + pos = rb_entry(nd, struct hist_entry, rb_node_in); - while (!feof(file)) - if (hist_entry__parse_objdump_line(self, file, head, privsize) < 0) - break; + if (!hist_entry__has_pairs(pos)) { + pair = hists__add_dummy_entry(leader, pos); + if (pair == NULL) + return -1; + hist_entry__add_pair(pos, pair); + } + } - pclose(file); -out_free_filename: - if (free_filename) - free(filename); - return err; + return 0; } -void hists__inc_nr_events(struct hists *self, u32 type) +u64 hists__total_period(struct hists *hists) { - ++self->stats.nr_events[0]; - ++self->stats.nr_events[type]; + return symbol_conf.filter_relative ? hists->stats.total_non_filtered_period : + hists->stats.total_period; } -size_t hists__fprintf_nr_events(struct hists *self, FILE *fp) +int parse_filter_percentage(const struct option *opt __maybe_unused, + const char *arg, int unset __maybe_unused) { - int i; - size_t ret = 0; + if (!strcmp(arg, "relative")) + symbol_conf.filter_relative = true; + else if (!strcmp(arg, "absolute")) + symbol_conf.filter_relative = false; + else + return -1; - for (i = 0; i < PERF_RECORD_HEADER_MAX; ++i) { - if (!event__name[i]) - continue; - ret += fprintf(fp, "%10s events: %10d\n", - event__name[i], self->stats.nr_events[i]); - } + return 0; +} + +int perf_hist_config(const char *var, const char *value) +{ + if (!strcmp(var, "hist.percentage")) + return parse_filter_percentage(NULL, value, 0); - return ret; + return 0; } |