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