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#include <linux/zalloc.h>
  10#include <stdlib.h>
  11
  12#include "call-path.h"
  13
  14static 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
  26struct 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
  38void 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
  49static 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
  77struct 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}
 115