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(cp: &cpr->call_path, NULL, NULL, ip: 0, in_kernel: false); |
34 | INIT_LIST_HEAD(list: &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(entry: &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(new: &cpb->node, head: &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(node: &cp->rb_node, parent: node_parent, rb_link: p); |
111 | rb_insert_color(&cp->rb_node, &parent->children); |
112 | |
113 | return cp; |
114 | } |
115 | |