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