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