]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - tools/perf/util/callchain.c
2 * Copyright (C) 2009, Frederic Weisbecker <fweisbec@gmail.com>
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
7 * Using a radix for code path provides a fast retrieval and factorizes
8 * memory use. Also that lets us use the paths in a hierarchical graph view.
17 #include "callchain.h"
21 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
)
23 struct rb_node
**p
= &root
->rb_node
;
24 struct rb_node
*parent
= NULL
;
25 struct callchain_node
*rnode
;
29 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
31 if (rnode
->hit
< chain
->hit
)
37 rb_link_node(&chain
->rb_node
, parent
, p
);
38 rb_insert_color(&chain
->rb_node
, root
);
42 * Once we get every callchains from the stream, we can now
45 void sort_chain_to_rbtree(struct rb_root
*rb_root
, struct callchain_node
*node
)
47 struct callchain_node
*child
;
49 list_for_each_entry(child
, &node
->children
, brothers
)
50 sort_chain_to_rbtree(rb_root
, child
);
53 rb_insert_callchain(rb_root
, node
);
57 * Create a child for a parent. If inherit_children, then the new child
58 * will become the new parent of it's parent children
60 static struct callchain_node
*
61 create_child(struct callchain_node
*parent
, bool inherit_children
)
63 struct callchain_node
*new;
65 new = malloc(sizeof(*new));
67 perror("not enough memory to create child for code path tree");
71 INIT_LIST_HEAD(&new->children
);
72 INIT_LIST_HEAD(&new->val
);
74 if (inherit_children
) {
75 struct callchain_node
*next
;
77 list_splice(&parent
->children
, &new->children
);
78 INIT_LIST_HEAD(&parent
->children
);
80 list_for_each_entry(next
, &new->children
, brothers
)
83 list_add_tail(&new->brothers
, &parent
->children
);
89 * Fill the node with callchain values
92 fill_node(struct callchain_node
*node
, struct ip_callchain
*chain
,
93 int start
, struct symbol
**syms
)
97 for (i
= start
; i
< chain
->nr
; i
++) {
98 struct callchain_list
*call
;
100 call
= malloc(sizeof(*call
));
102 perror("not enough memory for the code path tree");
105 call
->ip
= chain
->ips
[i
];
107 list_add_tail(&call
->list
, &node
->val
);
109 node
->val_nr
= chain
->nr
- start
;
111 printf("Warning: empty node in callchain tree\n");
115 add_child(struct callchain_node
*parent
, struct ip_callchain
*chain
,
116 int start
, struct symbol
**syms
)
118 struct callchain_node
*new;
120 new = create_child(parent
, false);
121 fill_node(new, chain
, start
, syms
);
127 * Split the parent in two parts (a new child is created) and
128 * give a part of its callchain to the created child.
129 * Then create another child to host the given callchain of new branch
132 split_add_child(struct callchain_node
*parent
, struct ip_callchain
*chain
,
133 struct callchain_list
*to_split
, int idx_parents
, int idx_local
,
134 struct symbol
**syms
)
136 struct callchain_node
*new;
137 struct list_head
*old_tail
;
138 unsigned int idx_total
= idx_parents
+ idx_local
;
141 new = create_child(parent
, true);
143 /* split the callchain and move a part to the new child */
144 old_tail
= parent
->val
.prev
;
145 list_del_range(&to_split
->list
, old_tail
);
146 new->val
.next
= &to_split
->list
;
147 new->val
.prev
= old_tail
;
148 to_split
->list
.prev
= &new->val
;
149 old_tail
->next
= &new->val
;
152 new->hit
= parent
->hit
;
153 new->val_nr
= parent
->val_nr
- idx_local
;
154 parent
->val_nr
= idx_local
;
156 /* create a new child for the new branch if any */
157 if (idx_total
< chain
->nr
) {
159 add_child(parent
, chain
, idx_total
, syms
);
166 __append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
167 unsigned int start
, struct symbol
**syms
);
170 __append_chain_children(struct callchain_node
*root
, struct ip_callchain
*chain
,
171 struct symbol
**syms
, unsigned int start
)
173 struct callchain_node
*rnode
;
175 /* lookup in childrens */
176 list_for_each_entry(rnode
, &root
->children
, brothers
) {
177 unsigned int ret
= __append_chain(rnode
, chain
, start
, syms
);
182 /* nothing in children, add to the current node */
183 add_child(root
, chain
, start
, syms
);
187 __append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
188 unsigned int start
, struct symbol
**syms
)
190 struct callchain_list
*cnode
;
191 unsigned int i
= start
;
195 * Lookup in the current node
196 * If we have a symbol, then compare the start to match
197 * anywhere inside a function.
199 list_for_each_entry(cnode
, &root
->val
, list
) {
202 if (cnode
->sym
&& syms
[i
]) {
203 if (cnode
->sym
->start
!= syms
[i
]->start
)
205 } else if (cnode
->ip
!= chain
->ips
[i
])
212 /* matches not, relay on the parent */
216 /* we match only a part of the node. Split it and add the new chain */
217 if (i
- start
< root
->val_nr
) {
218 split_add_child(root
, chain
, cnode
, start
, i
- start
, syms
);
222 /* we match 100% of the path, increment the hit */
223 if (i
- start
== root
->val_nr
&& i
== chain
->nr
) {
228 /* We match the node and still have a part remaining */
229 __append_chain_children(root
, chain
, syms
, i
);
234 void append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
235 struct symbol
**syms
)
237 __append_chain_children(root
, chain
, syms
, 0);