Commit | Line | Data |
---|---|---|
451db126 CP |
1 | /* |
2 | * call-path.h: Manipulate a tree data structure containing function call paths | |
3 | * Copyright (c) 2014, Intel Corporation. | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify it | |
6 | * under the terms and conditions of the GNU General Public License, | |
7 | * version 2, as published by the Free Software Foundation. | |
8 | * | |
9 | * This program is distributed in the hope it will be useful, but WITHOUT | |
10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for | |
12 | * more details. | |
13 | * | |
14 | */ | |
15 | ||
16 | #include <linux/rbtree.h> | |
17 | #include <linux/list.h> | |
18 | ||
19 | #include "util.h" | |
20 | #include "call-path.h" | |
21 | ||
22 | static void call_path__init(struct call_path *cp, struct call_path *parent, | |
23 | struct symbol *sym, u64 ip, bool in_kernel) | |
24 | { | |
25 | cp->parent = parent; | |
26 | cp->sym = sym; | |
27 | cp->ip = sym ? 0 : ip; | |
28 | cp->db_id = 0; | |
29 | cp->in_kernel = in_kernel; | |
30 | RB_CLEAR_NODE(&cp->rb_node); | |
31 | cp->children = RB_ROOT; | |
32 | } | |
33 | ||
34 | struct call_path_root *call_path_root__new(void) | |
35 | { | |
36 | struct call_path_root *cpr; | |
37 | ||
38 | cpr = zalloc(sizeof(struct call_path_root)); | |
39 | if (!cpr) | |
40 | return NULL; | |
41 | call_path__init(&cpr->call_path, NULL, NULL, 0, false); | |
42 | INIT_LIST_HEAD(&cpr->blocks); | |
43 | return cpr; | |
44 | } | |
45 | ||
46 | void call_path_root__free(struct call_path_root *cpr) | |
47 | { | |
48 | struct call_path_block *pos, *n; | |
49 | ||
50 | list_for_each_entry_safe(pos, n, &cpr->blocks, node) { | |
51 | list_del(&pos->node); | |
52 | free(pos); | |
53 | } | |
54 | free(cpr); | |
55 | } | |
56 | ||
57 | static struct call_path *call_path__new(struct call_path_root *cpr, | |
58 | struct call_path *parent, | |
59 | struct symbol *sym, u64 ip, | |
60 | bool in_kernel) | |
61 | { | |
62 | struct call_path_block *cpb; | |
63 | struct call_path *cp; | |
64 | size_t n; | |
65 | ||
66 | if (cpr->next < cpr->sz) { | |
67 | cpb = list_last_entry(&cpr->blocks, struct call_path_block, | |
68 | node); | |
69 | } else { | |
70 | cpb = zalloc(sizeof(struct call_path_block)); | |
71 | if (!cpb) | |
72 | return NULL; | |
73 | list_add_tail(&cpb->node, &cpr->blocks); | |
74 | cpr->sz += CALL_PATH_BLOCK_SIZE; | |
75 | } | |
76 | ||
77 | n = cpr->next++ & CALL_PATH_BLOCK_MASK; | |
78 | cp = &cpb->cp[n]; | |
79 | ||
80 | call_path__init(cp, parent, sym, ip, in_kernel); | |
81 | ||
82 | return cp; | |
83 | } | |
84 | ||
85 | struct call_path *call_path__findnew(struct call_path_root *cpr, | |
86 | struct call_path *parent, | |
87 | struct symbol *sym, u64 ip, u64 ks) | |
88 | { | |
89 | struct rb_node **p; | |
90 | struct rb_node *node_parent = NULL; | |
91 | struct call_path *cp; | |
92 | bool in_kernel = ip >= ks; | |
93 | ||
94 | if (sym) | |
95 | ip = 0; | |
96 | ||
97 | if (!parent) | |
98 | return call_path__new(cpr, parent, sym, ip, in_kernel); | |
99 | ||
100 | p = &parent->children.rb_node; | |
101 | while (*p != NULL) { | |
102 | node_parent = *p; | |
103 | cp = rb_entry(node_parent, struct call_path, rb_node); | |
104 | ||
105 | if (cp->sym == sym && cp->ip == ip) | |
106 | return cp; | |
107 | ||
108 | if (sym < cp->sym || (sym == cp->sym && ip < cp->ip)) | |
109 | p = &(*p)->rb_left; | |
110 | else | |
111 | p = &(*p)->rb_right; | |
112 | } | |
113 | ||
114 | cp = call_path__new(cpr, parent, sym, ip, in_kernel); | |
115 | if (!cp) | |
116 | return NULL; | |
117 | ||
118 | rb_link_node(&cp->rb_node, node_parent, p); | |
119 | rb_insert_color(&cp->rb_node, &parent->children); | |
120 | ||
121 | return cp; | |
122 | } |