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

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

Version: ~ [ linux-5.8-rc5 ] ~ [ linux-5.7.8 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.51 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.132 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.188 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.230 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.230 ] ~ [ 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 /*
  2  * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
  3  *
  4  * Handle the callchains from the stream in an ad-hoc radix tree and then
  5  * sort them in an rbtree.
  6  *
  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.
  9  *
 10  */
 11 
 12 #include <stdlib.h>
 13 #include <stdio.h>
 14 #include <stdbool.h>
 15 #include <errno.h>
 16 #include <math.h>
 17 
 18 #include "util.h"
 19 #include "callchain.h"
 20 
 21 __thread struct callchain_cursor callchain_cursor;
 22 
 23 bool ip_callchain__valid(struct ip_callchain *chain,
 24                          const union perf_event *event)
 25 {
 26         unsigned int chain_size = event->header.size;
 27         chain_size -= (unsigned long)&event->ip.__more_data - (unsigned long)event;
 28         return chain->nr * sizeof(u64) <= chain_size;
 29 }
 30 
 31 #define chain_for_each_child(child, parent)     \
 32         list_for_each_entry(child, &parent->children, siblings)
 33 
 34 #define chain_for_each_child_safe(child, next, parent)  \
 35         list_for_each_entry_safe(child, next, &parent->children, siblings)
 36 
 37 static void
 38 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
 39                     enum chain_mode mode)
 40 {
 41         struct rb_node **p = &root->rb_node;
 42         struct rb_node *parent = NULL;
 43         struct callchain_node *rnode;
 44         u64 chain_cumul = callchain_cumul_hits(chain);
 45 
 46         while (*p) {
 47                 u64 rnode_cumul;
 48 
 49                 parent = *p;
 50                 rnode = rb_entry(parent, struct callchain_node, rb_node);
 51                 rnode_cumul = callchain_cumul_hits(rnode);
 52 
 53                 switch (mode) {
 54                 case CHAIN_FLAT:
 55                         if (rnode->hit < chain->hit)
 56                                 p = &(*p)->rb_left;
 57                         else
 58                                 p = &(*p)->rb_right;
 59                         break;
 60                 case CHAIN_GRAPH_ABS: /* Falldown */
 61                 case CHAIN_GRAPH_REL:
 62                         if (rnode_cumul < chain_cumul)
 63                                 p = &(*p)->rb_left;
 64                         else
 65                                 p = &(*p)->rb_right;
 66                         break;
 67                 case CHAIN_NONE:
 68                 default:
 69                         break;
 70                 }
 71         }
 72 
 73         rb_link_node(&chain->rb_node, parent, p);
 74         rb_insert_color(&chain->rb_node, root);
 75 }
 76 
 77 static void
 78 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
 79                   u64 min_hit)
 80 {
 81         struct callchain_node *child;
 82 
 83         chain_for_each_child(child, node)
 84                 __sort_chain_flat(rb_root, child, min_hit);
 85 
 86         if (node->hit && node->hit >= min_hit)
 87                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
 88 }
 89 
 90 /*
 91  * Once we get every callchains from the stream, we can now
 92  * sort them by hit
 93  */
 94 static void
 95 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
 96                 u64 min_hit, struct callchain_param *param __maybe_unused)
 97 {
 98         __sort_chain_flat(rb_root, &root->node, min_hit);
 99 }
100 
101 static void __sort_chain_graph_abs(struct callchain_node *node,
102                                    u64 min_hit)
103 {
104         struct callchain_node *child;
105 
106         node->rb_root = RB_ROOT;
107 
108         chain_for_each_child(child, node) {
109                 __sort_chain_graph_abs(child, min_hit);
110                 if (callchain_cumul_hits(child) >= min_hit)
111                         rb_insert_callchain(&node->rb_root, child,
112                                             CHAIN_GRAPH_ABS);
113         }
114 }
115 
116 static void
117 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
118                      u64 min_hit, struct callchain_param *param __maybe_unused)
119 {
120         __sort_chain_graph_abs(&chain_root->node, min_hit);
121         rb_root->rb_node = chain_root->node.rb_root.rb_node;
122 }
123 
124 static void __sort_chain_graph_rel(struct callchain_node *node,
125                                    double min_percent)
126 {
127         struct callchain_node *child;
128         u64 min_hit;
129 
130         node->rb_root = RB_ROOT;
131         min_hit = ceil(node->children_hit * min_percent);
132 
133         chain_for_each_child(child, node) {
134                 __sort_chain_graph_rel(child, min_percent);
135                 if (callchain_cumul_hits(child) >= min_hit)
136                         rb_insert_callchain(&node->rb_root, child,
137                                             CHAIN_GRAPH_REL);
138         }
139 }
140 
141 static void
142 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
143                      u64 min_hit __maybe_unused, struct callchain_param *param)
144 {
145         __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
146         rb_root->rb_node = chain_root->node.rb_root.rb_node;
147 }
148 
149 int callchain_register_param(struct callchain_param *param)
150 {
151         switch (param->mode) {
152         case CHAIN_GRAPH_ABS:
153                 param->sort = sort_chain_graph_abs;
154                 break;
155         case CHAIN_GRAPH_REL:
156                 param->sort = sort_chain_graph_rel;
157                 break;
158         case CHAIN_FLAT:
159                 param->sort = sort_chain_flat;
160                 break;
161         case CHAIN_NONE:
162         default:
163                 return -1;
164         }
165         return 0;
166 }
167 
168 /*
169  * Create a child for a parent. If inherit_children, then the new child
170  * will become the new parent of it's parent children
171  */
172 static struct callchain_node *
173 create_child(struct callchain_node *parent, bool inherit_children)
174 {
175         struct callchain_node *new;
176 
177         new = zalloc(sizeof(*new));
178         if (!new) {
179                 perror("not enough memory to create child for code path tree");
180                 return NULL;
181         }
182         new->parent = parent;
183         INIT_LIST_HEAD(&new->children);
184         INIT_LIST_HEAD(&new->val);
185 
186         if (inherit_children) {
187                 struct callchain_node *next;
188 
189                 list_splice(&parent->children, &new->children);
190                 INIT_LIST_HEAD(&parent->children);
191 
192                 chain_for_each_child(next, new)
193                         next->parent = new;
194         }
195         list_add_tail(&new->siblings, &parent->children);
196 
197         return new;
198 }
199 
200 
201 /*
202  * Fill the node with callchain values
203  */
204 static void
205 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
206 {
207         struct callchain_cursor_node *cursor_node;
208 
209         node->val_nr = cursor->nr - cursor->pos;
210         if (!node->val_nr)
211                 pr_warning("Warning: empty node in callchain tree\n");
212 
213         cursor_node = callchain_cursor_current(cursor);
214 
215         while (cursor_node) {
216                 struct callchain_list *call;
217 
218                 call = zalloc(sizeof(*call));
219                 if (!call) {
220                         perror("not enough memory for the code path tree");
221                         return;
222                 }
223                 call->ip = cursor_node->ip;
224                 call->ms.sym = cursor_node->sym;
225                 call->ms.map = cursor_node->map;
226                 list_add_tail(&call->list, &node->val);
227 
228                 callchain_cursor_advance(cursor);
229                 cursor_node = callchain_cursor_current(cursor);
230         }
231 }
232 
233 static void
234 add_child(struct callchain_node *parent,
235           struct callchain_cursor *cursor,
236           u64 period)
237 {
238         struct callchain_node *new;
239 
240         new = create_child(parent, false);
241         fill_node(new, cursor);
242 
243         new->children_hit = 0;
244         new->hit = period;
245 }
246 
247 /*
248  * Split the parent in two parts (a new child is created) and
249  * give a part of its callchain to the created child.
250  * Then create another child to host the given callchain of new branch
251  */
252 static void
253 split_add_child(struct callchain_node *parent,
254                 struct callchain_cursor *cursor,
255                 struct callchain_list *to_split,
256                 u64 idx_parents, u64 idx_local, u64 period)
257 {
258         struct callchain_node *new;
259         struct list_head *old_tail;
260         unsigned int idx_total = idx_parents + idx_local;
261 
262         /* split */
263         new = create_child(parent, true);
264 
265         /* split the callchain and move a part to the new child */
266         old_tail = parent->val.prev;
267         list_del_range(&to_split->list, old_tail);
268         new->val.next = &to_split->list;
269         new->val.prev = old_tail;
270         to_split->list.prev = &new->val;
271         old_tail->next = &new->val;
272 
273         /* split the hits */
274         new->hit = parent->hit;
275         new->children_hit = parent->children_hit;
276         parent->children_hit = callchain_cumul_hits(new);
277         new->val_nr = parent->val_nr - idx_local;
278         parent->val_nr = idx_local;
279 
280         /* create a new child for the new branch if any */
281         if (idx_total < cursor->nr) {
282                 parent->hit = 0;
283                 add_child(parent, cursor, period);
284                 parent->children_hit += period;
285         } else {
286                 parent->hit = period;
287         }
288 }
289 
290 static int
291 append_chain(struct callchain_node *root,
292              struct callchain_cursor *cursor,
293              u64 period);
294 
295 static void
296 append_chain_children(struct callchain_node *root,
297                       struct callchain_cursor *cursor,
298                       u64 period)
299 {
300         struct callchain_node *rnode;
301 
302         /* lookup in childrens */
303         chain_for_each_child(rnode, root) {
304                 unsigned int ret = append_chain(rnode, cursor, period);
305 
306                 if (!ret)
307                         goto inc_children_hit;
308         }
309         /* nothing in children, add to the current node */
310         add_child(root, cursor, period);
311 
312 inc_children_hit:
313         root->children_hit += period;
314 }
315 
316 static int
317 append_chain(struct callchain_node *root,
318              struct callchain_cursor *cursor,
319              u64 period)
320 {
321         struct callchain_cursor_node *curr_snap = cursor->curr;
322         struct callchain_list *cnode;
323         u64 start = cursor->pos;
324         bool found = false;
325         u64 matches;
326 
327         /*
328          * Lookup in the current node
329          * If we have a symbol, then compare the start to match
330          * anywhere inside a function.
331          */
332         list_for_each_entry(cnode, &root->val, list) {
333                 struct callchain_cursor_node *node;
334                 struct symbol *sym;
335 
336                 node = callchain_cursor_current(cursor);
337                 if (!node)
338                         break;
339 
340                 sym = node->sym;
341 
342                 if (cnode->ms.sym && sym) {
343                         if (cnode->ms.sym->start != sym->start)
344                                 break;
345                 } else if (cnode->ip != node->ip)
346                         break;
347 
348                 if (!found)
349                         found = true;
350 
351                 callchain_cursor_advance(cursor);
352         }
353 
354         /* matches not, relay on the parent */
355         if (!found) {
356                 cursor->curr = curr_snap;
357                 cursor->pos = start;
358                 return -1;
359         }
360 
361         matches = cursor->pos - start;
362 
363         /* we match only a part of the node. Split it and add the new chain */
364         if (matches < root->val_nr) {
365                 split_add_child(root, cursor, cnode, start, matches, period);
366                 return 0;
367         }
368 
369         /* we match 100% of the path, increment the hit */
370         if (matches == root->val_nr && cursor->pos == cursor->nr) {
371                 root->hit += period;
372                 return 0;
373         }
374 
375         /* We match the node and still have a part remaining */
376         append_chain_children(root, cursor, period);
377 
378         return 0;
379 }
380 
381 int callchain_append(struct callchain_root *root,
382                      struct callchain_cursor *cursor,
383                      u64 period)
384 {
385         if (!cursor->nr)
386                 return 0;
387 
388         callchain_cursor_commit(cursor);
389 
390         append_chain_children(&root->node, cursor, period);
391 
392         if (cursor->nr > root->max_depth)
393                 root->max_depth = cursor->nr;
394 
395         return 0;
396 }
397 
398 static int
399 merge_chain_branch(struct callchain_cursor *cursor,
400                    struct callchain_node *dst, struct callchain_node *src)
401 {
402         struct callchain_cursor_node **old_last = cursor->last;
403         struct callchain_node *child, *next_child;
404         struct callchain_list *list, *next_list;
405         int old_pos = cursor->nr;
406         int err = 0;
407 
408         list_for_each_entry_safe(list, next_list, &src->val, list) {
409                 callchain_cursor_append(cursor, list->ip,
410                                         list->ms.map, list->ms.sym);
411                 list_del(&list->list);
412                 free(list);
413         }
414 
415         if (src->hit) {
416                 callchain_cursor_commit(cursor);
417                 append_chain_children(dst, cursor, src->hit);
418         }
419 
420         chain_for_each_child_safe(child, next_child, src) {
421                 err = merge_chain_branch(cursor, dst, child);
422                 if (err)
423                         break;
424 
425                 list_del(&child->siblings);
426                 free(child);
427         }
428 
429         cursor->nr = old_pos;
430         cursor->last = old_last;
431 
432         return err;
433 }
434 
435 int callchain_merge(struct callchain_cursor *cursor,
436                     struct callchain_root *dst, struct callchain_root *src)
437 {
438         return merge_chain_branch(cursor, &dst->node, &src->node);
439 }
440 
441 int callchain_cursor_append(struct callchain_cursor *cursor,
442                             u64 ip, struct map *map, struct symbol *sym)
443 {
444         struct callchain_cursor_node *node = *cursor->last;
445 
446         if (!node) {
447                 node = calloc(1, sizeof(*node));
448                 if (!node)
449                         return -ENOMEM;
450 
451                 *cursor->last = node;
452         }
453 
454         node->ip = ip;
455         node->map = map;
456         node->sym = sym;
457 
458         cursor->nr++;
459 
460         cursor->last = &node->next;
461 
462         return 0;
463 }
464 

~ [ 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