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  */
   8
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include <stdbool.h>
  12 #include <errno.h>
  13
  14 #include "callchain.h"
  15
  16
  17 static void rb_insert_callchain(struct rb_root *root, struct callchain_node *chain)
  18 {
  19         struct rb_node **p = &root->rb_node;
  20         struct rb_node *parent = NULL;
  21         struct callchain_node *rnode;
  22
  23         while (*p) {
  24                 parent = *p;
  25                 rnode = rb_entry(parent, struct callchain_node, rb_node);
  26
  27                 if (rnode->hit < chain->hit)
  28                         p = &(*p)->rb_left;
  29                 else
  30                         p = &(*p)->rb_right;
  31         }
  32
  33         rb_link_node(&chain->rb_node, parent, p);
  34         rb_insert_color(&chain->rb_node, root);
  35 }
  36
  37 /*
  38  * Once we get every callchains from the stream, we can now
  39  * sort them by hit
  40  */
  41 void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node)
  42 {
  43         struct callchain_node *child;
  44
  45         list_for_each_entry(child, &node->children, brothers)
  46                 sort_chain_to_rbtree(rb_root, child);
  47
  48         if (node->hit)
  49                 rb_insert_callchain(rb_root, node);
  50 }
  51
  52 static struct callchain_node *create_child(struct callchain_node *parent)
  53 {
  54         struct callchain_node *new;
  55
  56         new = malloc(sizeof(*new));
  57         if (!new) {
  58                 perror("not enough memory to create child for code path tree");
  59                 return NULL;
  60         }
  61         new->parent = parent;
  62         INIT_LIST_HEAD(&new->children);
  63         INIT_LIST_HEAD(&new->val);
  64         list_add_tail(&new->brothers, &parent->children);
  65
  66         return new;
  67 }
  68
  69 static void
  70 fill_node(struct callchain_node *node, struct ip_callchain *chain, int start)
  71 {
  72         int i;
  73
  74         for (i = start; i < chain->nr; i++) {
  75                 struct callchain_list *call;
  76
  77                 call = malloc(sizeof(*chain));
  78                 if (!call) {
  79                         perror("not enough memory for the code path tree");
  80                         return;
  81                 }
  82                 call->ip = chain->ips[i];
  83                 list_add_tail(&call->list, &node->val);
  84         }
  85         node->val_nr = i - start;
  86 }
  87
  88 static void add_child(struct callchain_node *parent, struct ip_callchain *chain)
  89 {
  90         struct callchain_node *new;
  91
  92         new = create_child(parent);
  93         fill_node(new, chain, parent->val_nr);
  94
  95         new->hit = 1;
  96 }
  97
  98 static void
  99 split_add_child(struct callchain_node *parent, struct ip_callchain *chain,
 100                 struct callchain_list *to_split, int idx)
 101 {
 102         struct callchain_node *new;
 103
 104         /* split */
 105         new = create_child(parent);
 106         list_move_tail(&to_split->list, &new->val);
 107         new->hit = parent->hit;
 108         parent->hit = 0;
 109         parent->val_nr = idx;
 110
 111         /* create the new one */
 112         add_child(parent, chain);
 113 }
 114
 115 static int
 116 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 117                 int start);
 118
 119 static int
 120 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain)
 121 {
 122         struct callchain_node *rnode;
 123
 124         /* lookup in childrens */
 125         list_for_each_entry(rnode, &root->children, brothers) {
 126                 int ret = __append_chain(rnode, chain, root->val_nr);
 127                 if (!ret)
 128                         return 0;
 129         }
 130         return -1;
 131 }
 132
 133 static int
 134 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 135                 int start)
 136 {
 137         struct callchain_list *cnode;
 138         int i = start;
 139         bool found = false;
 140
 141         /* lookup in the current node */
 142         list_for_each_entry(cnode, &root->val, list) {
 143                 if (cnode->ip != chain->ips[i++])
 144                         break;
 145                 if (!found)
 146                         found = true;
 147                 if (i == chain->nr)
 148                         break;
 149         }
 150
 151         /* matches not, relay on the parent */
 152         if (!found)
 153                 return -1;
 154
 155         /* we match only a part of the node. Split it and add the new chain */
 156         if (i < root->val_nr) {
 157                 split_add_child(root, chain, cnode, i);
 158                 return 0;
 159         }
 160
 161         /* we match 100% of the path, increment the hit */
 162         if (i == root->val_nr) {
 163                 root->hit++;
 164                 return 0;
 165         }
 166
 167         return __append_chain_children(root, chain);
 168 }
 169
 170 void append_chain(struct callchain_node *root, struct ip_callchain *chain)
 171 {
 172         if (__append_chain_children(root, chain) == -1)
 173                 add_child(root, chain);
 174 }