tools/perf/util/call-path.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * call-path.h: Manipulate a tree data structure containing function call paths
   4  * Copyright (c) 2014, Intel Corporation.
   5  */
   6
   7 #include <linux/rbtree.h>
   8 #include <linux/list.h>
   9
  10 #include "util.h"
  11 #include "call-path.h"
  12
  13 static void call_path__init(struct call_path *cp, struct call_path *parent,
  14                             struct symbol *sym, u64 ip, bool in_kernel)
  15 {
  16         cp->parent = parent;
  17         cp->sym = sym;
  18         cp->ip = sym ? 0 : ip;
  19         cp->db_id = 0;
  20         cp->in_kernel = in_kernel;
  21         RB_CLEAR_NODE(&cp->rb_node);
  22         cp->children = RB_ROOT;
  23 }
  24
  25 struct call_path_root *call_path_root__new(void)
  26 {
  27         struct call_path_root *cpr;
  28
  29         cpr = zalloc(sizeof(struct call_path_root));
  30         if (!cpr)
  31                 return NULL;
  32         call_path__init(&cpr->call_path, NULL, NULL, 0, false);
  33         INIT_LIST_HEAD(&cpr->blocks);
  34         return cpr;
  35 }
  36
  37 void call_path_root__free(struct call_path_root *cpr)
  38 {
  39         struct call_path_block *pos, *n;
  40
  41         list_for_each_entry_safe(pos, n, &cpr->blocks, node) {
  42                 list_del(&pos->node);
  43                 free(pos);
  44         }
  45         free(cpr);
  46 }
  47
  48 static struct call_path *call_path__new(struct call_path_root *cpr,
  49                                         struct call_path *parent,
  50                                         struct symbol *sym, u64 ip,
  51                                         bool in_kernel)
  52 {
  53         struct call_path_block *cpb;
  54         struct call_path *cp;
  55         size_t n;
  56
  57         if (cpr->next < cpr->sz) {
  58                 cpb = list_last_entry(&cpr->blocks, struct call_path_block,
  59                                       node);
  60         } else {
  61                 cpb = zalloc(sizeof(struct call_path_block));
  62                 if (!cpb)
  63                         return NULL;
  64                 list_add_tail(&cpb->node, &cpr->blocks);
  65                 cpr->sz += CALL_PATH_BLOCK_SIZE;
  66         }
  67
  68         n = cpr->next++ & CALL_PATH_BLOCK_MASK;
  69         cp = &cpb->cp[n];
  70
  71         call_path__init(cp, parent, sym, ip, in_kernel);
  72
  73         return cp;
  74 }
  75
  76 struct call_path *call_path__findnew(struct call_path_root *cpr,
  77                                      struct call_path *parent,
  78                                      struct symbol *sym, u64 ip, u64 ks)
  79 {
  80         struct rb_node **p;
  81         struct rb_node *node_parent = NULL;
  82         struct call_path *cp;
  83         bool in_kernel = ip >= ks;
  84
  85         if (sym)
  86                 ip = 0;
  87
  88         if (!parent)
  89                 return call_path__new(cpr, parent, sym, ip, in_kernel);
  90
  91         p = &parent->children.rb_node;
  92         while (*p != NULL) {
  93                 node_parent = *p;
  94                 cp = rb_entry(node_parent, struct call_path, rb_node);
  95
  96                 if (cp->sym == sym && cp->ip == ip)
  97                         return cp;
  98
  99                 if (sym < cp->sym || (sym == cp->sym && ip < cp->ip))
 100                         p = &(*p)->rb_left;
 101                 else
 102                         p = &(*p)->rb_right;
 103         }
 104
 105         cp = call_path__new(cpr, parent, sym, ip, in_kernel);
 106         if (!cp)
 107                 return NULL;
 108
 109         rb_link_node(&cp->rb_node, node_parent, p);
 110         rb_insert_color(&cp->rb_node, &parent->children);
 111
 112         return cp;
 113 }