~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/perf/util/hist.c

Version: ~ [ linux-5.8 ] ~ [ linux-5.7.14 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.57 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.138 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.193 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.232 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.232 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 #include "annotate.h"
  2 #include "util.h"
  3 #include "build-id.h"
  4 #include "hist.h"
  5 #include "session.h"
  6 #include "sort.h"
  7 #include "evsel.h"
  8 #include <math.h>
  9 
 10 static bool hists__filter_entry_by_dso(struct hists *hists,
 11                                        struct hist_entry *he);
 12 static bool hists__filter_entry_by_thread(struct hists *hists,
 13                                           struct hist_entry *he);
 14 static bool hists__filter_entry_by_symbol(struct hists *hists,
 15                                           struct hist_entry *he);
 16 
 17 enum hist_filter {
 18         HIST_FILTER__DSO,
 19         HIST_FILTER__THREAD,
 20         HIST_FILTER__PARENT,
 21         HIST_FILTER__SYMBOL,
 22 };
 23 
 24 struct callchain_param  callchain_param = {
 25         .mode   = CHAIN_GRAPH_REL,
 26         .min_percent = 0.5,
 27         .order  = ORDER_CALLEE
 28 };
 29 
 30 u16 hists__col_len(struct hists *hists, enum hist_column col)
 31 {
 32         return hists->col_len[col];
 33 }
 34 
 35 void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len)
 36 {
 37         hists->col_len[col] = len;
 38 }
 39 
 40 bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
 41 {
 42         if (len > hists__col_len(hists, col)) {
 43                 hists__set_col_len(hists, col, len);
 44                 return true;
 45         }
 46         return false;
 47 }
 48 
 49 void hists__reset_col_len(struct hists *hists)
 50 {
 51         enum hist_column col;
 52 
 53         for (col = 0; col < HISTC_NR_COLS; ++col)
 54                 hists__set_col_len(hists, col, 0);
 55 }
 56 
 57 static void hists__set_unres_dso_col_len(struct hists *hists, int dso)
 58 {
 59         const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
 60 
 61         if (hists__col_len(hists, dso) < unresolved_col_width &&
 62             !symbol_conf.col_width_list_str && !symbol_conf.field_sep &&
 63             !symbol_conf.dso_list)
 64                 hists__set_col_len(hists, dso, unresolved_col_width);
 65 }
 66 
 67 void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
 68 {
 69         const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
 70         int symlen;
 71         u16 len;
 72 
 73         /*
 74          * +4 accounts for '[x] ' priv level info
 75          * +2 accounts for 0x prefix on raw addresses
 76          * +3 accounts for ' y ' symtab origin info
 77          */
 78         if (h->ms.sym) {
 79                 symlen = h->ms.sym->namelen + 4;
 80                 if (verbose)
 81                         symlen += BITS_PER_LONG / 4 + 2 + 3;
 82                 hists__new_col_len(hists, HISTC_SYMBOL, symlen);
 83         } else {
 84                 symlen = unresolved_col_width + 4 + 2;
 85                 hists__new_col_len(hists, HISTC_SYMBOL, symlen);
 86                 hists__set_unres_dso_col_len(hists, HISTC_DSO);
 87         }
 88 
 89         len = thread__comm_len(h->thread);
 90         if (hists__new_col_len(hists, HISTC_COMM, len))
 91                 hists__set_col_len(hists, HISTC_THREAD, len + 6);
 92 
 93         if (h->ms.map) {
 94                 len = dso__name_len(h->ms.map->dso);
 95                 hists__new_col_len(hists, HISTC_DSO, len);
 96         }
 97 
 98         if (h->parent)
 99                 hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen);
100 
101         if (h->branch_info) {
102                 if (h->branch_info->from.sym) {
103                         symlen = (int)h->branch_info->from.sym->namelen + 4;
104                         if (verbose)
105                                 symlen += BITS_PER_LONG / 4 + 2 + 3;
106                         hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
107 
108                         symlen = dso__name_len(h->branch_info->from.map->dso);
109                         hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
110                 } else {
111                         symlen = unresolved_col_width + 4 + 2;
112                         hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
113                         hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
114                 }
115 
116                 if (h->branch_info->to.sym) {
117                         symlen = (int)h->branch_info->to.sym->namelen + 4;
118                         if (verbose)
119                                 symlen += BITS_PER_LONG / 4 + 2 + 3;
120                         hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
121 
122                         symlen = dso__name_len(h->branch_info->to.map->dso);
123                         hists__new_col_len(hists, HISTC_DSO_TO, symlen);
124                 } else {
125                         symlen = unresolved_col_width + 4 + 2;
126                         hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
127                         hists__set_unres_dso_col_len(hists, HISTC_DSO_TO);
128                 }
129         }
130 
131         if (h->mem_info) {
132                 if (h->mem_info->daddr.sym) {
133                         symlen = (int)h->mem_info->daddr.sym->namelen + 4
134                                + unresolved_col_width + 2;
135                         hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
136                                            symlen);
137                 } else {
138                         symlen = unresolved_col_width + 4 + 2;
139                         hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
140                                            symlen);
141                 }
142                 if (h->mem_info->daddr.map) {
143                         symlen = dso__name_len(h->mem_info->daddr.map->dso);
144                         hists__new_col_len(hists, HISTC_MEM_DADDR_DSO,
145                                            symlen);
146                 } else {
147                         symlen = unresolved_col_width + 4 + 2;
148                         hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
149                 }
150         } else {
151                 symlen = unresolved_col_width + 4 + 2;
152                 hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, symlen);
153                 hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
154         }
155 
156         hists__new_col_len(hists, HISTC_MEM_LOCKED, 6);
157         hists__new_col_len(hists, HISTC_MEM_TLB, 22);
158         hists__new_col_len(hists, HISTC_MEM_SNOOP, 12);
159         hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3);
160         hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12);
161         hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12);
162 }
163 
164 void hists__output_recalc_col_len(struct hists *hists, int max_rows)
165 {
166         struct rb_node *next = rb_first(&hists->entries);
167         struct hist_entry *n;
168         int row = 0;
169 
170         hists__reset_col_len(hists);
171 
172         while (next && row++ < max_rows) {
173                 n = rb_entry(next, struct hist_entry, rb_node);
174                 if (!n->filtered)
175                         hists__calc_col_len(hists, n);
176                 next = rb_next(&n->rb_node);
177         }
178 }
179 
180 static void hist_entry__add_cpumode_period(struct hist_entry *he,
181                                            unsigned int cpumode, u64 period)
182 {
183         switch (cpumode) {
184         case PERF_RECORD_MISC_KERNEL:
185                 he->stat.period_sys += period;
186                 break;
187         case PERF_RECORD_MISC_USER:
188                 he->stat.period_us += period;
189                 break;
190         case PERF_RECORD_MISC_GUEST_KERNEL:
191                 he->stat.period_guest_sys += period;
192                 break;
193         case PERF_RECORD_MISC_GUEST_USER:
194                 he->stat.period_guest_us += period;
195                 break;
196         default:
197                 break;
198         }
199 }
200 
201 static void he_stat__add_period(struct he_stat *he_stat, u64 period,
202                                 u64 weight)
203 {
204 
205         he_stat->period         += period;
206         he_stat->weight         += weight;
207         he_stat->nr_events      += 1;
208 }
209 
210 static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src)
211 {
212         dest->period            += src->period;
213         dest->period_sys        += src->period_sys;
214         dest->period_us         += src->period_us;
215         dest->period_guest_sys  += src->period_guest_sys;
216         dest->period_guest_us   += src->period_guest_us;
217         dest->nr_events         += src->nr_events;
218         dest->weight            += src->weight;
219 }
220 
221 static void hist_entry__decay(struct hist_entry *he)
222 {
223         he->stat.period = (he->stat.period * 7) / 8;
224         he->stat.nr_events = (he->stat.nr_events * 7) / 8;
225         /* XXX need decay for weight too? */
226 }
227 
228 static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
229 {
230         u64 prev_period = he->stat.period;
231 
232         if (prev_period == 0)
233                 return true;
234 
235         hist_entry__decay(he);
236 
237         if (!he->filtered)
238                 hists->stats.total_period -= prev_period - he->stat.period;
239 
240         return he->stat.period == 0;
241 }
242 
243 void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
244 {
245         struct rb_node *next = rb_first(&hists->entries);
246         struct hist_entry *n;
247 
248         while (next) {
249                 n = rb_entry(next, struct hist_entry, rb_node);
250                 next = rb_next(&n->rb_node);
251                 /*
252                  * We may be annotating this, for instance, so keep it here in
253                  * case some it gets new samples, we'll eventually free it when
254                  * the user stops browsing and it agains gets fully decayed.
255                  */
256                 if (((zap_user && n->level == '.') ||
257                      (zap_kernel && n->level != '.') ||
258                      hists__decay_entry(hists, n)) &&
259                     !n->used) {
260                         rb_erase(&n->rb_node, &hists->entries);
261 
262                         if (sort__need_collapse)
263                                 rb_erase(&n->rb_node_in, &hists->entries_collapsed);
264 
265                         hist_entry__free(n);
266                         --hists->nr_entries;
267                 }
268         }
269 }
270 
271 /*
272  * histogram, sorted on item, collects periods
273  */
274 
275 static struct hist_entry *hist_entry__new(struct hist_entry *template)
276 {
277         size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_root) : 0;
278         struct hist_entry *he = zalloc(sizeof(*he) + callchain_size);
279 
280         if (he != NULL) {
281                 *he = *template;
282 
283                 if (he->ms.map)
284                         he->ms.map->referenced = true;
285 
286                 if (he->branch_info) {
287                         /*
288                          * This branch info is (a part of) allocated from
289                          * machine__resolve_bstack() and will be freed after
290                          * adding new entries.  So we need to save a copy.
291                          */
292                         he->branch_info = malloc(sizeof(*he->branch_info));
293                         if (he->branch_info == NULL) {
294                                 free(he);
295                                 return NULL;
296                         }
297 
298                         memcpy(he->branch_info, template->branch_info,
299                                sizeof(*he->branch_info));
300 
301                         if (he->branch_info->from.map)
302                                 he->branch_info->from.map->referenced = true;
303                         if (he->branch_info->to.map)
304                                 he->branch_info->to.map->referenced = true;
305                 }
306 
307                 if (he->mem_info) {
308                         if (he->mem_info->iaddr.map)
309                                 he->mem_info->iaddr.map->referenced = true;
310                         if (he->mem_info->daddr.map)
311                                 he->mem_info->daddr.map->referenced = true;
312                 }
313 
314                 if (symbol_conf.use_callchain)
315                         callchain_init(he->callchain);
316 
317                 INIT_LIST_HEAD(&he->pairs.node);
318         }
319 
320         return he;
321 }
322 
323 void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h)
324 {
325         if (!h->filtered) {
326                 hists__calc_col_len(hists, h);
327                 ++hists->nr_entries;
328                 hists->stats.total_period += h->stat.period;
329         }
330 }
331 
332 static u8 symbol__parent_filter(const struct symbol *parent)
333 {
334         if (symbol_conf.exclude_other && parent == NULL)
335                 return 1 << HIST_FILTER__PARENT;
336         return 0;
337 }
338 
339 static struct hist_entry *add_hist_entry(struct hists *hists,
340                                       struct hist_entry *entry,
341                                       struct addr_location *al,
342                                       u64 period,
343                                       u64 weight)
344 {
345         struct rb_node **p;
346         struct rb_node *parent = NULL;
347         struct hist_entry *he;
348         int cmp;
349 
350         p = &hists->entries_in->rb_node;
351 
352         while (*p != NULL) {
353                 parent = *p;
354                 he = rb_entry(parent, struct hist_entry, rb_node_in);
355 
356                 /*
357                  * Make sure that it receives arguments in a same order as
358                  * hist_entry__collapse() so that we can use an appropriate
359                  * function when searching an entry regardless which sort
360                  * keys were used.
361                  */
362                 cmp = hist_entry__cmp(he, entry);
363 
364                 if (!cmp) {
365                         he_stat__add_period(&he->stat, period, weight);
366 
367                         /*
368                          * This mem info was allocated from machine__resolve_mem
369                          * and will not be used anymore.
370                          */
371                         free(entry->mem_info);
372 
373                         /* If the map of an existing hist_entry has
374                          * become out-of-date due to an exec() or
375                          * similar, update it.  Otherwise we will
376                          * mis-adjust symbol addresses when computing
377                          * the history counter to increment.
378                          */
379                         if (he->ms.map != entry->ms.map) {
380                                 he->ms.map = entry->ms.map;
381                                 if (he->ms.map)
382                                         he->ms.map->referenced = true;
383                         }
384                         goto out;
385                 }
386 
387                 if (cmp < 0)
388                         p = &(*p)->rb_left;
389                 else
390                         p = &(*p)->rb_right;
391         }
392 
393         he = hist_entry__new(entry);
394         if (!he)
395                 return NULL;
396 
397         rb_link_node(&he->rb_node_in, parent, p);
398         rb_insert_color(&he->rb_node_in, hists->entries_in);
399 out:
400         hist_entry__add_cpumode_period(he, al->cpumode, period);
401         return he;
402 }
403 
404 struct hist_entry *__hists__add_mem_entry(struct hists *self,
405                                           struct addr_location *al,
406                                           struct symbol *sym_parent,
407                                           struct mem_info *mi,
408                                           u64 period,
409                                           u64 weight)
410 {
411         struct hist_entry entry = {
412                 .thread = al->thread,
413                 .ms = {
414                         .map    = al->map,
415                         .sym    = al->sym,
416                 },
417                 .stat = {
418                         .period = period,
419                         .weight = weight,
420                         .nr_events = 1,
421                 },
422                 .cpu    = al->cpu,
423                 .ip     = al->addr,
424                 .level  = al->level,
425                 .parent = sym_parent,
426                 .filtered = symbol__parent_filter(sym_parent),
427                 .hists = self,
428                 .mem_info = mi,
429                 .branch_info = NULL,
430         };
431         return add_hist_entry(self, &entry, al, period, weight);
432 }
433 
434 struct hist_entry *__hists__add_branch_entry(struct hists *self,
435                                              struct addr_location *al,
436                                              struct symbol *sym_parent,
437                                              struct branch_info *bi,
438                                              u64 period,
439                                              u64 weight)
440 {
441         struct hist_entry entry = {
442                 .thread = al->thread,
443                 .ms = {
444                         .map    = bi->to.map,
445                         .sym    = bi->to.sym,
446                 },
447                 .cpu    = al->cpu,
448                 .ip     = bi->to.addr,
449                 .level  = al->level,
450                 .stat = {
451                         .period = period,
452                         .nr_events = 1,
453                         .weight = weight,
454                 },
455                 .parent = sym_parent,
456                 .filtered = symbol__parent_filter(sym_parent),
457                 .branch_info = bi,
458                 .hists  = self,
459                 .mem_info = NULL,
460         };
461 
462         return add_hist_entry(self, &entry, al, period, weight);
463 }
464 
465 struct hist_entry *__hists__add_entry(struct hists *self,
466                                       struct addr_location *al,
467                                       struct symbol *sym_parent, u64 period,
468                                       u64 weight)
469 {
470         struct hist_entry entry = {
471                 .thread = al->thread,
472                 .ms = {
473                         .map    = al->map,
474                         .sym    = al->sym,
475                 },
476                 .cpu    = al->cpu,
477                 .ip     = al->addr,
478                 .level  = al->level,
479                 .stat = {
480                         .period = period,
481                         .nr_events = 1,
482                         .weight = weight,
483                 },
484                 .parent = sym_parent,
485                 .filtered = symbol__parent_filter(sym_parent),
486                 .hists  = self,
487                 .branch_info = NULL,
488                 .mem_info = NULL,
489         };
490 
491         return add_hist_entry(self, &entry, al, period, weight);
492 }
493 
494 int64_t
495 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
496 {
497         struct sort_entry *se;
498         int64_t cmp = 0;
499 
500         list_for_each_entry(se, &hist_entry__sort_list, list) {
501                 cmp = se->se_cmp(left, right);
502                 if (cmp)
503                         break;
504         }
505 
506         return cmp;
507 }
508 
509 int64_t
510 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
511 {
512         struct sort_entry *se;
513         int64_t cmp = 0;
514 
515         list_for_each_entry(se, &hist_entry__sort_list, list) {
516                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
517 
518                 f = se->se_collapse ?: se->se_cmp;
519 
520                 cmp = f(left, right);
521                 if (cmp)
522                         break;
523         }
524 
525         return cmp;
526 }
527 
528 void hist_entry__free(struct hist_entry *he)
529 {
530         free(he->branch_info);
531         free(he->mem_info);
532         free(he);
533 }
534 
535 /*
536  * collapse the histogram
537  */
538 
539 static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
540                                          struct rb_root *root,
541                                          struct hist_entry *he)
542 {
543         struct rb_node **p = &root->rb_node;
544         struct rb_node *parent = NULL;
545         struct hist_entry *iter;
546         int64_t cmp;
547 
548         while (*p != NULL) {
549                 parent = *p;
550                 iter = rb_entry(parent, struct hist_entry, rb_node_in);
551 
552                 cmp = hist_entry__collapse(iter, he);
553 
554                 if (!cmp) {
555                         he_stat__add_stat(&iter->stat, &he->stat);
556 
557                         if (symbol_conf.use_callchain) {
558                                 callchain_cursor_reset(&callchain_cursor);
559                                 callchain_merge(&callchain_cursor,
560                                                 iter->callchain,
561                                                 he->callchain);
562                         }
563                         hist_entry__free(he);
564                         return false;
565                 }
566 
567                 if (cmp < 0)
568                         p = &(*p)->rb_left;
569                 else
570                         p = &(*p)->rb_right;
571         }
572 
573         rb_link_node(&he->rb_node_in, parent, p);
574         rb_insert_color(&he->rb_node_in, root);
575         return true;
576 }
577 
578 static struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
579 {
580         struct rb_root *root;
581 
582         pthread_mutex_lock(&hists->lock);
583 
584         root = hists->entries_in;
585         if (++hists->entries_in > &hists->entries_in_array[1])
586                 hists->entries_in = &hists->entries_in_array[0];
587 
588         pthread_mutex_unlock(&hists->lock);
589 
590         return root;
591 }
592 
593 static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
594 {
595         hists__filter_entry_by_dso(hists, he);
596         hists__filter_entry_by_thread(hists, he);
597         hists__filter_entry_by_symbol(hists, he);
598 }
599 
600 void hists__collapse_resort(struct hists *hists)
601 {
602         struct rb_root *root;
603         struct rb_node *next;
604         struct hist_entry *n;
605 
606         if (!sort__need_collapse)
607                 return;
608 
609         root = hists__get_rotate_entries_in(hists);
610         next = rb_first(root);
611 
612         while (next) {
613                 n = rb_entry(next, struct hist_entry, rb_node_in);
614                 next = rb_next(&n->rb_node_in);
615 
616                 rb_erase(&n->rb_node_in, root);
617                 if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
618                         /*
619                          * If it wasn't combined with one of the entries already
620                          * collapsed, we need to apply the filters that may have
621                          * been set by, say, the hist_browser.
622                          */
623                         hists__apply_filters(hists, n);
624                 }
625         }
626 }
627 
628 /*
629  * reverse the map, sort on period.
630  */
631 
632 static int period_cmp(u64 period_a, u64 period_b)
633 {
634         if (period_a > period_b)
635                 return 1;
636         if (period_a < period_b)
637                 return -1;
638         return 0;
639 }
640 
641 static int hist_entry__sort_on_period(struct hist_entry *a,
642                                       struct hist_entry *b)
643 {
644         int ret;
645         int i, nr_members;
646         struct perf_evsel *evsel;
647         struct hist_entry *pair;
648         u64 *periods_a, *periods_b;
649 
650         ret = period_cmp(a->stat.period, b->stat.period);
651         if (ret || !symbol_conf.event_group)
652                 return ret;
653 
654         evsel = hists_to_evsel(a->hists);
655         nr_members = evsel->nr_members;
656         if (nr_members <= 1)
657                 return ret;
658 
659         periods_a = zalloc(sizeof(periods_a) * nr_members);
660         periods_b = zalloc(sizeof(periods_b) * nr_members);
661 
662         if (!periods_a || !periods_b)
663                 goto out;
664 
665         list_for_each_entry(pair, &a->pairs.head, pairs.node) {
666                 evsel = hists_to_evsel(pair->hists);
667                 periods_a[perf_evsel__group_idx(evsel)] = pair->stat.period;
668         }
669 
670         list_for_each_entry(pair, &b->pairs.head, pairs.node) {
671                 evsel = hists_to_evsel(pair->hists);
672                 periods_b[perf_evsel__group_idx(evsel)] = pair->stat.period;
673         }
674 
675         for (i = 1; i < nr_members; i++) {
676                 ret = period_cmp(periods_a[i], periods_b[i]);
677                 if (ret)
678                         break;
679         }
680 
681 out:
682         free(periods_a);
683         free(periods_b);
684 
685         return ret;
686 }
687 
688 static void __hists__insert_output_entry(struct rb_root *entries,
689                                          struct hist_entry *he,
690                                          u64 min_callchain_hits)
691 {
692         struct rb_node **p = &entries->rb_node;
693         struct rb_node *parent = NULL;
694         struct hist_entry *iter;
695 
696         if (symbol_conf.use_callchain)
697                 callchain_param.sort(&he->sorted_chain, he->callchain,
698                                       min_callchain_hits, &callchain_param);
699 
700         while (*p != NULL) {
701                 parent = *p;
702                 iter = rb_entry(parent, struct hist_entry, rb_node);
703 
704                 if (hist_entry__sort_on_period(he, iter) > 0)
705                         p = &(*p)->rb_left;
706                 else
707                         p = &(*p)->rb_right;
708         }
709 
710         rb_link_node(&he->rb_node, parent, p);
711         rb_insert_color(&he->rb_node, entries);
712 }
713 
714 void hists__output_resort(struct hists *hists)
715 {
716         struct rb_root *root;
717         struct rb_node *next;
718         struct hist_entry *n;
719         u64 min_callchain_hits;
720 
721         min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100);
722 
723         if (sort__need_collapse)
724                 root = &hists->entries_collapsed;
725         else
726                 root = hists->entries_in;
727 
728         next = rb_first(root);
729         hists->entries = RB_ROOT;
730 
731         hists->nr_entries = 0;
732         hists->stats.total_period = 0;
733         hists__reset_col_len(hists);
734 
735         while (next) {
736                 n = rb_entry(next, struct hist_entry, rb_node_in);
737                 next = rb_next(&n->rb_node_in);
738 
739                 __hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
740                 hists__inc_nr_entries(hists, n);
741         }
742 }
743 
744 static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
745                                        enum hist_filter filter)
746 {
747         h->filtered &= ~(1 << filter);
748         if (h->filtered)
749                 return;
750 
751         ++hists->nr_entries;
752         if (h->ms.unfolded)
753                 hists->nr_entries += h->nr_rows;
754         h->row_offset = 0;
755         hists->stats.total_period += h->stat.period;
756         hists->stats.nr_events[PERF_RECORD_SAMPLE] += h->stat.nr_events;
757 
758         hists__calc_col_len(hists, h);
759 }
760 
761 
762 static bool hists__filter_entry_by_dso(struct hists *hists,
763                                        struct hist_entry *he)
764 {
765         if (hists->dso_filter != NULL &&
766             (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) {
767                 he->filtered |= (1 << HIST_FILTER__DSO);
768                 return true;
769         }
770 
771         return false;
772 }
773 
774 void hists__filter_by_dso(struct hists *hists)
775 {
776         struct rb_node *nd;
777 
778         hists->nr_entries = hists->stats.total_period = 0;
779         hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
780         hists__reset_col_len(hists);
781 
782         for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
783                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
784 
785                 if (symbol_conf.exclude_other && !h->parent)
786                         continue;
787 
788                 if (hists__filter_entry_by_dso(hists, h))
789                         continue;
790 
791                 hists__remove_entry_filter(hists, h, HIST_FILTER__DSO);
792         }
793 }
794 
795 static bool hists__filter_entry_by_thread(struct hists *hists,
796                                           struct hist_entry *he)
797 {
798         if (hists->thread_filter != NULL &&
799             he->thread != hists->thread_filter) {
800                 he->filtered |= (1 << HIST_FILTER__THREAD);
801                 return true;
802         }
803 
804         return false;
805 }
806 
807 void hists__filter_by_thread(struct hists *hists)
808 {
809         struct rb_node *nd;
810 
811         hists->nr_entries = hists->stats.total_period = 0;
812         hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
813         hists__reset_col_len(hists);
814 
815         for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
816                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
817 
818                 if (hists__filter_entry_by_thread(hists, h))
819                         continue;
820 
821                 hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD);
822         }
823 }
824 
825 static bool hists__filter_entry_by_symbol(struct hists *hists,
826                                           struct hist_entry *he)
827 {
828         if (hists->symbol_filter_str != NULL &&
829             (!he->ms.sym || strstr(he->ms.sym->name,
830                                    hists->symbol_filter_str) == NULL)) {
831                 he->filtered |= (1 << HIST_FILTER__SYMBOL);
832                 return true;
833         }
834 
835         return false;
836 }
837 
838 void hists__filter_by_symbol(struct hists *hists)
839 {
840         struct rb_node *nd;
841 
842         hists->nr_entries = hists->stats.total_period = 0;
843         hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
844         hists__reset_col_len(hists);
845 
846         for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
847                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
848 
849                 if (hists__filter_entry_by_symbol(hists, h))
850                         continue;
851 
852                 hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL);
853         }
854 }
855 
856 int hist_entry__inc_addr_samples(struct hist_entry *he, int evidx, u64 ip)
857 {
858         return symbol__inc_addr_samples(he->ms.sym, he->ms.map, evidx, ip);
859 }
860 
861 int hist_entry__annotate(struct hist_entry *he, size_t privsize)
862 {
863         return symbol__annotate(he->ms.sym, he->ms.map, privsize);
864 }
865 
866 void events_stats__inc(struct events_stats *stats, u32 type)
867 {
868         ++stats->nr_events[0];
869         ++stats->nr_events[type];
870 }
871 
872 void hists__inc_nr_events(struct hists *hists, u32 type)
873 {
874         events_stats__inc(&hists->stats, type);
875 }
876 
877 static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
878                                                  struct hist_entry *pair)
879 {
880         struct rb_root *root;
881         struct rb_node **p;
882         struct rb_node *parent = NULL;
883         struct hist_entry *he;
884         int cmp;
885 
886         if (sort__need_collapse)
887                 root = &hists->entries_collapsed;
888         else
889                 root = hists->entries_in;
890 
891         p = &root->rb_node;
892 
893         while (*p != NULL) {
894                 parent = *p;
895                 he = rb_entry(parent, struct hist_entry, rb_node_in);
896 
897                 cmp = hist_entry__collapse(he, pair);
898 
899                 if (!cmp)
900                         goto out;
901 
902                 if (cmp < 0)
903                         p = &(*p)->rb_left;
904                 else
905                         p = &(*p)->rb_right;
906         }
907 
908         he = hist_entry__new(pair);
909         if (he) {
910                 memset(&he->stat, 0, sizeof(he->stat));
911                 he->hists = hists;
912                 rb_link_node(&he->rb_node_in, parent, p);
913                 rb_insert_color(&he->rb_node_in, root);
914                 hists__inc_nr_entries(hists, he);
915         }
916 out:
917         return he;
918 }
919 
920 static struct hist_entry *hists__find_entry(struct hists *hists,
921                                             struct hist_entry *he)
922 {
923         struct rb_node *n;
924 
925         if (sort__need_collapse)
926                 n = hists->entries_collapsed.rb_node;
927         else
928                 n = hists->entries_in->rb_node;
929 
930         while (n) {
931                 struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
932                 int64_t cmp = hist_entry__collapse(iter, he);
933 
934                 if (cmp < 0)
935                         n = n->rb_left;
936                 else if (cmp > 0)
937                         n = n->rb_right;
938                 else
939                         return iter;
940         }
941 
942         return NULL;
943 }
944 
945 /*
946  * Look for pairs to link to the leader buckets (hist_entries):
947  */
948 void hists__match(struct hists *leader, struct hists *other)
949 {
950         struct rb_root *root;
951         struct rb_node *nd;
952         struct hist_entry *pos, *pair;
953 
954         if (sort__need_collapse)
955                 root = &leader->entries_collapsed;
956         else
957                 root = leader->entries_in;
958 
959         for (nd = rb_first(root); nd; nd = rb_next(nd)) {
960                 pos  = rb_entry(nd, struct hist_entry, rb_node_in);
961                 pair = hists__find_entry(other, pos);
962 
963                 if (pair)
964                         hist_entry__add_pair(pair, pos);
965         }
966 }
967 
968 /*
969  * Look for entries in the other hists that are not present in the leader, if
970  * we find them, just add a dummy entry on the leader hists, with period=0,
971  * nr_events=0, to serve as the list header.
972  */
973 int hists__link(struct hists *leader, struct hists *other)
974 {
975         struct rb_root *root;
976         struct rb_node *nd;
977         struct hist_entry *pos, *pair;
978 
979         if (sort__need_collapse)
980                 root = &other->entries_collapsed;
981         else
982                 root = other->entries_in;
983 
984         for (nd = rb_first(root); nd; nd = rb_next(nd)) {
985                 pos = rb_entry(nd, struct hist_entry, rb_node_in);
986 
987                 if (!hist_entry__has_pairs(pos)) {
988                         pair = hists__add_dummy_entry(leader, pos);
989                         if (pair == NULL)
990                                 return -1;
991                         hist_entry__add_pair(pos, pair);
992                 }
993         }
994 
995         return 0;
996 }
997 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp