/* XXX need decay for weight too? */
}
+static void hists__delete_entry(struct hists *hists, struct hist_entry *he);
+
static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
{
u64 prev_period = he->stat.period;
diff = prev_period - he->stat.period;
- hists->stats.total_period -= diff;
- if (!he->filtered)
- hists->stats.total_non_filtered_period -= diff;
+ if (!he->depth) {
+ hists->stats.total_period -= diff;
+ if (!he->filtered)
+ hists->stats.total_non_filtered_period -= diff;
+ }
+
+ if (!he->leaf) {
+ struct hist_entry *child;
+ struct rb_node *node = rb_first(&he->hroot_out);
+ while (node) {
+ child = rb_entry(node, struct hist_entry, rb_node);
+ node = rb_next(node);
+
+ if (hists__decay_entry(hists, child))
+ hists__delete_entry(hists, child);
+ }
+ }
return he->stat.period == 0;
}
static void hists__delete_entry(struct hists *hists, struct hist_entry *he)
{
- rb_erase(&he->rb_node, &hists->entries);
+ struct rb_root *root_in;
+ struct rb_root *root_out;
- if (sort__need_collapse)
- rb_erase(&he->rb_node_in, &hists->entries_collapsed);
- else
- rb_erase(&he->rb_node_in, hists->entries_in);
+ if (he->parent_he) {
+ root_in = &he->parent_he->hroot_in;
+ root_out = &he->parent_he->hroot_out;
+ } else {
+ if (sort__need_collapse)
+ root_in = &hists->entries_collapsed;
+ else
+ root_in = hists->entries_in;
+ root_out = &hists->entries;
+ }
+
+ rb_erase(&he->rb_node_in, root_in);
+ rb_erase(&he->rb_node, root_out);
--hists->nr_entries;
if (!he->filtered)
}
INIT_LIST_HEAD(&he->pairs.node);
thread__get(he->thread);
+
+ if (!symbol_conf.report_hierarchy)
+ he->leaf = true;
}
return he;
int64_t cmp = 0;
hists__for_each_sort_list(hists, fmt) {
+ if (perf_hpp__is_dynamic_entry(fmt) &&
+ !perf_hpp__defined_dynamic_entry(fmt, hists))
+ continue;
+
cmp = fmt->cmp(fmt, left, right);
if (cmp)
break;
int64_t cmp = 0;
hists__for_each_sort_list(hists, fmt) {
+ if (perf_hpp__is_dynamic_entry(fmt) &&
+ !perf_hpp__defined_dynamic_entry(fmt, hists))
+ continue;
+
cmp = fmt->collapse(fmt, left, right);
if (cmp)
break;
* collapse the histogram
*/
+static void hists__apply_filters(struct hists *hists, struct hist_entry *he);
+
+static struct hist_entry *hierarchy_insert_entry(struct hists *hists,
+ struct rb_root *root,
+ struct hist_entry *he,
+ struct perf_hpp_list *hpp_list)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct hist_entry *iter, *new;
+ struct perf_hpp_fmt *fmt;
+ int64_t cmp;
+
+ while (*p != NULL) {
+ parent = *p;
+ iter = rb_entry(parent, struct hist_entry, rb_node_in);
+
+ cmp = 0;
+ perf_hpp_list__for_each_sort_list(hpp_list, fmt) {
+ cmp = fmt->collapse(fmt, iter, he);
+ if (cmp)
+ break;
+ }
+
+ if (!cmp) {
+ he_stat__add_stat(&iter->stat, &he->stat);
+ return iter;
+ }
+
+ if (cmp < 0)
+ p = &parent->rb_left;
+ else
+ p = &parent->rb_right;
+ }
+
+ new = hist_entry__new(he, true);
+ if (new == NULL)
+ return NULL;
+
+ hists__apply_filters(hists, new);
+ hists->nr_entries++;
+
+ /* save related format list for output */
+ new->hpp_list = hpp_list;
+
+ /* some fields are now passed to 'new' */
+ perf_hpp_list__for_each_sort_list(hpp_list, fmt) {
+ if (perf_hpp__is_trace_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
+ he->trace_output = NULL;
+ else
+ new->trace_output = NULL;
+
+ if (perf_hpp__is_srcline_entry(fmt))
+ he->srcline = NULL;
+ else
+ new->srcline = NULL;
+
+ if (perf_hpp__is_srcfile_entry(fmt))
+ he->srcfile = NULL;
+ else
+ new->srcfile = NULL;
+ }
+
+ rb_link_node(&new->rb_node_in, parent, p);
+ rb_insert_color(&new->rb_node_in, root);
+ return new;
+}
+
+static int hists__hierarchy_insert_entry(struct hists *hists,
+ struct rb_root *root,
+ struct hist_entry *he)
+{
+ struct perf_hpp_list_node *node;
+ struct hist_entry *new_he = NULL;
+ struct hist_entry *parent = NULL;
+ int depth = 0;
+ int ret = 0;
+
+ list_for_each_entry(node, &hists->hpp_formats, list) {
+ /* skip period (overhead) and elided columns */
+ if (node->level == 0 || node->skip)
+ continue;
+
+ /* insert copy of 'he' for each fmt into the hierarchy */
+ new_he = hierarchy_insert_entry(hists, root, he, &node->hpp);
+ if (new_he == NULL) {
+ ret = -1;
+ break;
+ }
+
+ root = &new_he->hroot_in;
+ new_he->parent_he = parent;
+ new_he->depth = depth++;
+ parent = new_he;
+ }
+
+ if (new_he) {
+ new_he->leaf = true;
+
+ if (symbol_conf.use_callchain) {
+ callchain_cursor_reset(&callchain_cursor);
+ if (callchain_merge(&callchain_cursor,
+ new_he->callchain,
+ he->callchain) < 0)
+ ret = -1;
+ }
+ }
+
+ /* 'he' is no longer used */
+ hist_entry__delete(he);
+
+ /* return 0 (or -1) since it already applied filters */
+ return ret;
+}
+
int hists__collapse_insert_entry(struct hists *hists, struct rb_root *root,
struct hist_entry *he)
{
struct hist_entry *iter;
int64_t cmp;
+ if (symbol_conf.report_hierarchy)
+ return hists__hierarchy_insert_entry(hists, root, he);
+
while (*p != NULL) {
parent = *p;
iter = rb_entry(parent, struct hist_entry, rb_node_in);
hists->stats.total_period += h->stat.period;
}
+static void hierarchy_insert_output_entry(struct rb_root *root,
+ struct hist_entry *he)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct hist_entry *iter;
+ struct perf_hpp_fmt *fmt;
+
+ while (*p != NULL) {
+ parent = *p;
+ iter = rb_entry(parent, struct hist_entry, rb_node);
+
+ if (hist_entry__sort(he, iter) > 0)
+ p = &parent->rb_left;
+ else
+ p = &parent->rb_right;
+ }
+
+ rb_link_node(&he->rb_node, parent, p);
+ rb_insert_color(&he->rb_node, root);
+
+ /* update column width of dynamic entry */
+ perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
+ if (perf_hpp__is_dynamic_entry(fmt))
+ fmt->sort(fmt, he, NULL);
+ }
+}
+
+static void hists__hierarchy_output_resort(struct hists *hists,
+ struct ui_progress *prog,
+ struct rb_root *root_in,
+ struct rb_root *root_out,
+ u64 min_callchain_hits,
+ bool use_callchain)
+{
+ struct rb_node *node;
+ struct hist_entry *he;
+
+ *root_out = RB_ROOT;
+ node = rb_first(root_in);
+
+ while (node) {
+ he = rb_entry(node, struct hist_entry, rb_node_in);
+ node = rb_next(node);
+
+ hierarchy_insert_output_entry(root_out, he);
+
+ if (prog)
+ ui_progress__update(prog, 1);
+
+ if (!he->leaf) {
+ hists__hierarchy_output_resort(hists, prog,
+ &he->hroot_in,
+ &he->hroot_out,
+ min_callchain_hits,
+ use_callchain);
+ hists->nr_entries++;
+ if (!he->filtered) {
+ hists->nr_non_filtered_entries++;
+ hists__calc_col_len(hists, he);
+ }
+
+ continue;
+ }
+
+ /* only update stat for leaf entries to avoid duplication */
+ hists__inc_stats(hists, he);
+ if (!he->filtered)
+ hists__calc_col_len(hists, he);
+
+ if (!use_callchain)
+ continue;
+
+ if (callchain_param.mode == CHAIN_GRAPH_REL) {
+ u64 total = he->stat.period;
+
+ if (symbol_conf.cumulate_callchain)
+ total = he->stat_acc->period;
+
+ min_callchain_hits = total * (callchain_param.min_percent / 100);
+ }
+
+ callchain_param.sort(&he->sorted_chain, he->callchain,
+ min_callchain_hits, &callchain_param);
+ }
+}
+
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;
+ struct perf_hpp_fmt *fmt;
if (use_callchain) {
if (callchain_param.mode == CHAIN_GRAPH_REL) {
rb_link_node(&he->rb_node, parent, p);
rb_insert_color(&he->rb_node, entries);
+
+ perf_hpp_list__for_each_sort_list(&perf_hpp_list, fmt) {
+ if (perf_hpp__is_dynamic_entry(fmt) &&
+ perf_hpp__defined_dynamic_entry(fmt, he->hists))
+ fmt->sort(fmt, he, NULL); /* update column width */
+ }
}
static void output_resort(struct hists *hists, struct ui_progress *prog,
min_callchain_hits = callchain_total * (callchain_param.min_percent / 100);
+ hists__reset_stats(hists);
+ hists__reset_col_len(hists);
+
+ if (symbol_conf.report_hierarchy) {
+ return hists__hierarchy_output_resort(hists, prog,
+ &hists->entries_collapsed,
+ &hists->entries,
+ min_callchain_hits,
+ use_callchain);
+ }
+
if (sort__need_collapse)
root = &hists->entries_collapsed;
else
next = rb_first(root);
hists->entries = RB_ROOT;
- hists__reset_stats(hists);
- hists__reset_col_len(hists);
-
while (next) {
n = rb_entry(next, struct hist_entry, rb_node_in);
next = rb_next(&n->rb_node_in);
output_resort(hists, prog, symbol_conf.use_callchain);
}
+static bool can_goto_child(struct hist_entry *he, enum hierarchy_move_dir hmd)
+{
+ if (he->leaf || hmd == HMD_FORCE_SIBLING)
+ return false;
+
+ if (he->unfolded || hmd == HMD_FORCE_CHILD)
+ return true;
+
+ return false;
+}
+
+struct rb_node *rb_hierarchy_last(struct rb_node *node)
+{
+ struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
+
+ while (can_goto_child(he, HMD_NORMAL)) {
+ node = rb_last(&he->hroot_out);
+ he = rb_entry(node, struct hist_entry, rb_node);
+ }
+ return node;
+}
+
+struct rb_node *__rb_hierarchy_next(struct rb_node *node, enum hierarchy_move_dir hmd)
+{
+ struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
+
+ if (can_goto_child(he, hmd))
+ node = rb_first(&he->hroot_out);
+ else
+ node = rb_next(node);
+
+ while (node == NULL) {
+ he = he->parent_he;
+ if (he == NULL)
+ break;
+
+ node = rb_next(&he->rb_node);
+ }
+ return node;
+}
+
+struct rb_node *rb_hierarchy_prev(struct rb_node *node)
+{
+ struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
+
+ node = rb_prev(node);
+ if (node)
+ return rb_hierarchy_last(node);
+
+ he = he->parent_he;
+ if (he == NULL)
+ return NULL;
+
+ return &he->rb_node;
+}
+
+bool hist_entry__has_hierarchy_children(struct hist_entry *he, float limit)
+{
+ struct rb_node *node;
+ struct hist_entry *child;
+ float percent;
+
+ if (he->leaf)
+ return false;
+
+ node = rb_first(&he->hroot_out);
+ child = rb_entry(node, struct hist_entry, rb_node);
+
+ while (node && child->filtered) {
+ node = rb_next(node);
+ child = rb_entry(node, struct hist_entry, rb_node);
+ }
+
+ if (node)
+ percent = hist_entry__get_percent_limit(child);
+ else
+ percent = 0;
+
+ return node && percent >= limit;
+}
+
static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
enum hist_filter filter)
{
h->filtered &= ~(1 << filter);
+
+ if (symbol_conf.report_hierarchy) {
+ struct hist_entry *parent = h->parent_he;
+
+ while (parent) {
+ he_stat__add_stat(&parent->stat, &h->stat);
+
+ parent->filtered &= ~(1 << filter);
+
+ if (parent->filtered)
+ goto next;
+
+ /* force fold unfiltered entry for simplicity */
+ parent->unfolded = false;
+ parent->has_no_entry = false;
+ parent->row_offset = 0;
+ parent->nr_rows = 0;
+next:
+ parent = parent->parent_he;
+ }
+ }
+
if (h->filtered)
return;
/* force fold unfiltered entry for simplicity */
h->unfolded = false;
+ h->has_no_entry = false;
h->row_offset = 0;
h->nr_rows = 0;
}
}
+static void resort_filtered_entry(struct rb_root *root, struct hist_entry *he)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct hist_entry *iter;
+ struct rb_root new_root = RB_ROOT;
+ struct rb_node *nd;
+
+ while (*p != NULL) {
+ parent = *p;
+ iter = rb_entry(parent, struct hist_entry, rb_node);
+
+ if (hist_entry__sort(he, iter) > 0)
+ p = &(*p)->rb_left;
+ else
+ p = &(*p)->rb_right;
+ }
+
+ rb_link_node(&he->rb_node, parent, p);
+ rb_insert_color(&he->rb_node, root);
+
+ if (he->leaf || he->filtered)
+ return;
+
+ nd = rb_first(&he->hroot_out);
+ while (nd) {
+ struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+
+ nd = rb_next(nd);
+ rb_erase(&h->rb_node, &he->hroot_out);
+
+ resort_filtered_entry(&new_root, h);
+ }
+
+ he->hroot_out = new_root;
+}
+
+static void hists__filter_hierarchy(struct hists *hists, int type, const void *arg)
+{
+ struct rb_node *nd;
+ struct rb_root new_root = RB_ROOT;
+
+ hists->stats.nr_non_filtered_samples = 0;
+
+ hists__reset_filter_stats(hists);
+ hists__reset_col_len(hists);
+
+ nd = rb_first(&hists->entries);
+ while (nd) {
+ struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+ int ret;
+
+ ret = hist_entry__filter(h, type, arg);
+
+ /*
+ * case 1. non-matching type
+ * zero out the period, set filter marker and move to child
+ */
+ if (ret < 0) {
+ memset(&h->stat, 0, sizeof(h->stat));
+ h->filtered |= (1 << type);
+
+ nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_CHILD);
+ }
+ /*
+ * case 2. matched type (filter out)
+ * set filter marker and move to next
+ */
+ else if (ret == 1) {
+ h->filtered |= (1 << type);
+
+ nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
+ }
+ /*
+ * case 3. ok (not filtered)
+ * add period to hists and parents, erase the filter marker
+ * and move to next sibling
+ */
+ else {
+ hists__remove_entry_filter(hists, h, type);
+
+ nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
+ }
+ }
+
+ /*
+ * resort output after applying a new filter since filter in a lower
+ * hierarchy can change periods in a upper hierarchy.
+ */
+ nd = rb_first(&hists->entries);
+ while (nd) {
+ struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+
+ nd = rb_next(nd);
+ rb_erase(&h->rb_node, &hists->entries);
+
+ resort_filtered_entry(&new_root, h);
+ }
+
+ hists->entries = new_root;
+}
+
void hists__filter_by_thread(struct hists *hists)
{
- hists__filter_by_type(hists, HIST_FILTER__THREAD,
- hists__filter_entry_by_thread);
+ if (symbol_conf.report_hierarchy)
+ hists__filter_hierarchy(hists, HIST_FILTER__THREAD,
+ hists->thread_filter);
+ else
+ hists__filter_by_type(hists, HIST_FILTER__THREAD,
+ hists__filter_entry_by_thread);
}
void hists__filter_by_dso(struct hists *hists)
{
- hists__filter_by_type(hists, HIST_FILTER__DSO,
- hists__filter_entry_by_dso);
+ if (symbol_conf.report_hierarchy)
+ hists__filter_hierarchy(hists, HIST_FILTER__DSO,
+ hists->dso_filter);
+ else
+ hists__filter_by_type(hists, HIST_FILTER__DSO,
+ hists__filter_entry_by_dso);
}
void hists__filter_by_symbol(struct hists *hists)
{
- hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
- hists__filter_entry_by_symbol);
+ if (symbol_conf.report_hierarchy)
+ hists__filter_hierarchy(hists, HIST_FILTER__SYMBOL,
+ hists->symbol_filter_str);
+ else
+ hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
+ hists__filter_entry_by_symbol);
}
void hists__filter_by_socket(struct hists *hists)
{
- hists__filter_by_type(hists, HIST_FILTER__SOCKET,
- hists__filter_entry_by_socket);
+ if (symbol_conf.report_hierarchy)
+ hists__filter_hierarchy(hists, HIST_FILTER__SOCKET,
+ &hists->socket_filter);
+ else
+ hists__filter_by_type(hists, HIST_FILTER__SOCKET,
+ hists__filter_entry_by_socket);
}
void events_stats__inc(struct events_stats *stats, u32 type)
pthread_mutex_init(&hists->lock, NULL);
hists->socket_filter = -1;
hists->hpp_list = hpp_list;
+ INIT_LIST_HEAD(&hists->hpp_formats);
return 0;
}
static void hists_evsel__exit(struct perf_evsel *evsel)
{
struct hists *hists = evsel__hists(evsel);
+ struct perf_hpp_fmt *fmt, *pos;
+ struct perf_hpp_list_node *node, *tmp;
hists__delete_all_entries(hists);
+
+ list_for_each_entry_safe(node, tmp, &hists->hpp_formats, list) {
+ perf_hpp_list__for_each_format_safe(&node->hpp, fmt, pos) {
+ list_del(&fmt->list);
+ free(fmt);
+ }
+ list_del(&node->list);
+ free(node);
+ }
}
static int hists_evsel__init(struct perf_evsel *evsel)
projects / deliverable / linux.git / blobdiff