aboutsummaryrefslogtreecommitdiffstats
path: root/tools/perf/util
diff options
context:
space:
mode:
Diffstat (limited to 'tools/perf/util')
-rw-r--r--tools/perf/util/callchain.c51
-rw-r--r--tools/perf/util/callchain.h11
2 files changed, 51 insertions, 11 deletions
diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 3c4a91fea622..a9873aafcd92 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -19,9 +19,9 @@
19#define chain_for_each_child(child, parent) \ 19#define chain_for_each_child(child, parent) \
20 list_for_each_entry(child, &parent->children, brothers) 20 list_for_each_entry(child, &parent->children, brothers)
21 21
22
23static void 22static void
24rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) 23rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
24 enum chain_mode mode)
25{ 25{
26 struct rb_node **p = &root->rb_node; 26 struct rb_node **p = &root->rb_node;
27 struct rb_node *parent = NULL; 27 struct rb_node *parent = NULL;
@@ -31,10 +31,22 @@ rb_insert_callchain(struct rb_root *root, struct callchain_node *chain)
31 parent = *p; 31 parent = *p;
32 rnode = rb_entry(parent, struct callchain_node, rb_node); 32 rnode = rb_entry(parent, struct callchain_node, rb_node);
33 33
34 if (rnode->hit < chain->hit) 34 switch (mode) {
35 p = &(*p)->rb_left; 35 case FLAT:
36 else 36 if (rnode->hit < chain->hit)
37 p = &(*p)->rb_right; 37 p = &(*p)->rb_left;
38 else
39 p = &(*p)->rb_right;
40 break;
41 case GRAPH:
42 if (rnode->cumul_hit < chain->cumul_hit)
43 p = &(*p)->rb_left;
44 else
45 p = &(*p)->rb_right;
46 break;
47 default:
48 break;
49 }
38 } 50 }
39 51
40 rb_link_node(&chain->rb_node, parent, p); 52 rb_link_node(&chain->rb_node, parent, p);
@@ -45,15 +57,36 @@ rb_insert_callchain(struct rb_root *root, struct callchain_node *chain)
45 * Once we get every callchains from the stream, we can now 57 * Once we get every callchains from the stream, we can now
46 * sort them by hit 58 * sort them by hit
47 */ 59 */
48void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node) 60void sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node)
49{ 61{
50 struct callchain_node *child; 62 struct callchain_node *child;
51 63
52 chain_for_each_child(child, node) 64 chain_for_each_child(child, node)
53 sort_chain_to_rbtree(rb_root, child); 65 sort_chain_flat(rb_root, child);
54 66
55 if (node->hit) 67 if (node->hit)
56 rb_insert_callchain(rb_root, node); 68 rb_insert_callchain(rb_root, node, FLAT);
69}
70
71static void __sort_chain_graph(struct callchain_node *node)
72{
73 struct callchain_node *child;
74
75 node->rb_root = RB_ROOT;
76 node->cumul_hit = node->hit;
77
78 chain_for_each_child(child, node) {
79 __sort_chain_graph(child);
80 rb_insert_callchain(&node->rb_root, child, GRAPH);
81 node->cumul_hit += child->cumul_hit;
82 }
83}
84
85void
86sort_chain_graph(struct rb_root *rb_root, struct callchain_node *chain_root)
87{
88 __sort_chain_graph(chain_root);
89 rb_root->rb_node = chain_root->rb_root.rb_node;
57} 90}
58 91
59/* 92/*
diff --git a/tools/perf/util/callchain.h b/tools/perf/util/callchain.h
index e9bd5e882f38..dfa56008d9ad 100644
--- a/tools/perf/util/callchain.h
+++ b/tools/perf/util/callchain.h
@@ -6,15 +6,21 @@
6#include <linux/rbtree.h> 6#include <linux/rbtree.h>
7#include "symbol.h" 7#include "symbol.h"
8 8
9enum chain_mode {
10 FLAT,
11 GRAPH
12};
9 13
10struct callchain_node { 14struct callchain_node {
11 struct callchain_node *parent; 15 struct callchain_node *parent;
12 struct list_head brothers; 16 struct list_head brothers;
13 struct list_head children; 17 struct list_head children;
14 struct list_head val; 18 struct list_head val;
15 struct rb_node rb_node; 19 struct rb_node rb_node; /* to sort nodes in an rbtree */
20 struct rb_root rb_root; /* sorted tree of children */
16 unsigned int val_nr; 21 unsigned int val_nr;
17 u64 hit; 22 u64 hit;
23 u64 cumul_hit; /* hit + hits of children */
18}; 24};
19 25
20struct callchain_list { 26struct callchain_list {
@@ -32,5 +38,6 @@ static inline void callchain_init(struct callchain_node *node)
32 38
33void append_chain(struct callchain_node *root, struct ip_callchain *chain, 39void append_chain(struct callchain_node *root, struct ip_callchain *chain,
34 struct symbol **syms); 40 struct symbol **syms);
35void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node); 41void sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node);
42void sort_chain_graph(struct rb_root *rb_root, struct callchain_node *node);
36#endif 43#endif