Commit | Line | Data |
---|---|---|
2025cf9e | 1 | // SPDX-License-Identifier: GPL-2.0-only |
451db126 CP |
2 | /* |
3 | * call-path.h: Manipulate a tree data structure containing function call paths | |
4 | * Copyright (c) 2014, Intel Corporation. | |
451db126 CP |
5 | */ |
6 | ||
7 | #include <linux/rbtree.h> | |
8 | #include <linux/list.h> | |
7f7c536f ACM |
9 | #include <linux/zalloc.h> |
10 | #include <stdlib.h> | |
451db126 | 11 | |
451db126 CP |
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) { | |
e56fbc9d | 43 | list_del_init(&pos->node); |
451db126 CP |
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 | } |