diff options
Diffstat (limited to 'tools/perf/util')
-rw-r--r-- | tools/perf/util/callchain.c | 51 | ||||
-rw-r--r-- | tools/perf/util/callchain.h | 11 |
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 | |||
23 | static void | 22 | static void |
24 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) | 23 | rb_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 | */ |
48 | void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node) | 60 | void 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 | |||
71 | static 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 | |||
85 | void | ||
86 | sort_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 | ||
9 | enum chain_mode { | ||
10 | FLAT, | ||
11 | GRAPH | ||
12 | }; | ||
9 | 13 | ||
10 | struct callchain_node { | 14 | struct 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 | ||
20 | struct callchain_list { | 26 | struct callchain_list { |
@@ -32,5 +38,6 @@ static inline void callchain_init(struct callchain_node *node) | |||
32 | 38 | ||
33 | void append_chain(struct callchain_node *root, struct ip_callchain *chain, | 39 | void append_chain(struct callchain_node *root, struct ip_callchain *chain, |
34 | struct symbol **syms); | 40 | struct symbol **syms); |
35 | void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node); | 41 | void sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node); |
42 | void sort_chain_graph(struct rb_root *rb_root, struct callchain_node *node); | ||
36 | #endif | 43 | #endif |