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

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

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

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