git.oblomov.eu Git - linux-2.6/blob - tools/perf/util/callchain.c

   1 /*
   2  * Copyright (C) 2009, 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
  17 #include "callchain.h"
  18
  19 #define chain_for_each_child(child, parent)     \
  20         list_for_each_entry(child, &parent->children, brothers)
  21
  22
  23 static void
  24 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain)
  25 {
  26         struct rb_node **p = &root->rb_node;
  27         struct rb_node *parent = NULL;
  28         struct callchain_node *rnode;
  29
  30         while (*p) {
  31                 parent = *p;
  32                 rnode = rb_entry(parent, struct callchain_node, rb_node);
  33
  34                 if (rnode->hit < chain->hit)
  35                         p = &(*p)->rb_left;
  36                 else
  37                         p = &(*p)->rb_right;
  38         }
  39
  40         rb_link_node(&chain->rb_node, parent, p);
  41         rb_insert_color(&chain->rb_node, root);
  42 }
  43
  44 /*
  45  * Once we get every callchains from the stream, we can now
  46  * sort them by hit
  47  */
  48 void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node)
  49 {
  50         struct callchain_node *child;
  51
  52         chain_for_each_child(child, node)
  53                 sort_chain_to_rbtree(rb_root, child);
  54
  55         if (node->hit)
  56                 rb_insert_callchain(rb_root, node);
  57 }
  58
  59 /*
  60  * Create a child for a parent. If inherit_children, then the new child
  61  * will become the new parent of it's parent children
  62  */
  63 static struct callchain_node *
  64 create_child(struct callchain_node *parent, bool inherit_children)
  65 {
  66         struct callchain_node *new;
  67
  68         new = malloc(sizeof(*new));
  69         if (!new) {
  70                 perror("not enough memory to create child for code path tree");
  71                 return NULL;
  72         }
  73         new->parent = parent;
  74         INIT_LIST_HEAD(&new->children);
  75         INIT_LIST_HEAD(&new->val);
  76
  77         if (inherit_children) {
  78                 struct callchain_node *next;
  79
  80                 list_splice(&parent->children, &new->children);
  81                 INIT_LIST_HEAD(&parent->children);
  82
  83                 chain_for_each_child(next, new)
  84                         next->parent = new;
  85         }
  86         list_add_tail(&new->brothers, &parent->children);
  87
  88         return new;
  89 }
  90
  91 /*
  92  * Fill the node with callchain values
  93  */
  94 static void
  95 fill_node(struct callchain_node *node, struct ip_callchain *chain,
  96           int start, struct symbol **syms)
  97 {
  98         unsigned int i;
  99
 100         for (i = start; i < chain->nr; i++) {
 101                 struct callchain_list *call;
 102
 103                 call = malloc(sizeof(*call));
 104                 if (!call) {
 105                         perror("not enough memory for the code path tree");
 106                         return;
 107                 }
 108                 call->ip = chain->ips[i];
 109                 call->sym = syms[i];
 110                 list_add_tail(&call->list, &node->val);
 111         }
 112         node->val_nr = chain->nr - start;
 113         if (!node->val_nr)
 114                 printf("Warning: empty node in callchain tree\n");
 115 }
 116
 117 static void
 118 add_child(struct callchain_node *parent, struct ip_callchain *chain,
 119           int start, struct symbol **syms)
 120 {
 121         struct callchain_node *new;
 122
 123         new = create_child(parent, false);
 124         fill_node(new, chain, start, syms);
 125
 126         new->hit = 1;
 127 }
 128
 129 /*
 130  * Split the parent in two parts (a new child is created) and
 131  * give a part of its callchain to the created child.
 132  * Then create another child to host the given callchain of new branch
 133  */
 134 static void
 135 split_add_child(struct callchain_node *parent, struct ip_callchain *chain,
 136                 struct callchain_list *to_split, int idx_parents, int idx_local,
 137                 struct symbol **syms)
 138 {
 139         struct callchain_node *new;
 140         struct list_head *old_tail;
 141         unsigned int idx_total = idx_parents + idx_local;
 142
 143         /* split */
 144         new = create_child(parent, true);
 145
 146         /* split the callchain and move a part to the new child */
 147         old_tail = parent->val.prev;
 148         list_del_range(&to_split->list, old_tail);
 149         new->val.next = &to_split->list;
 150         new->val.prev = old_tail;
 151         to_split->list.prev = &new->val;
 152         old_tail->next = &new->val;
 153
 154         /* split the hits */
 155         new->hit = parent->hit;
 156         new->val_nr = parent->val_nr - idx_local;
 157         parent->val_nr = idx_local;
 158
 159         /* create a new child for the new branch if any */
 160         if (idx_total < chain->nr) {
 161                 parent->hit = 0;
 162                 add_child(parent, chain, idx_total, syms);
 163         } else {
 164                 parent->hit = 1;
 165         }
 166 }
 167
 168 static int
 169 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 170                unsigned int start, struct symbol **syms);
 171
 172 static void
 173 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain,
 174                         struct symbol **syms, unsigned int start)
 175 {
 176         struct callchain_node *rnode;
 177
 178         /* lookup in childrens */
 179         chain_for_each_child(rnode, root) {
 180                 unsigned int ret = __append_chain(rnode, chain, start, syms);
 181
 182                 if (!ret)
 183                         return;
 184         }
 185         /* nothing in children, add to the current node */
 186         add_child(root, chain, start, syms);
 187 }
 188
 189 static int
 190 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 191                unsigned int start, struct symbol **syms)
 192 {
 193         struct callchain_list *cnode;
 194         unsigned int i = start;
 195         bool found = false;
 196
 197         /*
 198          * Lookup in the current node
 199          * If we have a symbol, then compare the start to match
 200          * anywhere inside a function.
 201          */
 202         list_for_each_entry(cnode, &root->val, list) {
 203                 if (i == chain->nr)
 204                         break;
 205                 if (cnode->sym && syms[i]) {
 206                         if (cnode->sym->start != syms[i]->start)
 207                                 break;
 208                 } else if (cnode->ip != chain->ips[i])
 209                         break;
 210                 if (!found)
 211                         found = true;
 212                 i++;
 213         }
 214
 215         /* matches not, relay on the parent */
 216         if (!found)
 217                 return -1;
 218
 219         /* we match only a part of the node. Split it and add the new chain */
 220         if (i - start < root->val_nr) {
 221                 split_add_child(root, chain, cnode, start, i - start, syms);
 222                 return 0;
 223         }
 224
 225         /* we match 100% of the path, increment the hit */
 226         if (i - start == root->val_nr && i == chain->nr) {
 227                 root->hit++;
 228                 return 0;
 229         }
 230
 231         /* We match the node and still have a part remaining */
 232         __append_chain_children(root, chain, syms, i);
 233
 234         return 0;
 235 }
 236
 237 void append_chain(struct callchain_node *root, struct ip_callchain *chain,
 238                   struct symbol **syms)
 239 {
 240         __append_chain_children(root, chain, syms, 0);
 241 }