LXR linux/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
  13static 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
  25struct 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
  37void 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
  48static 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
  76struct 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}
 114