]>
Commit | Line | Data |
---|---|---|
8cb76d99 FW |
1 | /* |
2 | * Copyright (C) 2009, Frederic Weisbecker <fweisbec@gmail.com> | |
3 | * | |
4 | * Handle the callchains from the stream in an ad-hoc radix tree and then | |
5 | * sort them in an rbtree. | |
6 | * | |
7 | */ | |
8 | ||
9 | #include <stdlib.h> | |
10 | #include <stdio.h> | |
11 | #include <stdbool.h> | |
12 | #include <errno.h> | |
13 | ||
14 | #include "callchain.h" | |
15 | ||
16 | ||
17 | static void rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) | |
18 | { | |
19 | struct rb_node **p = &root->rb_node; | |
20 | struct rb_node *parent = NULL; | |
21 | struct callchain_node *rnode; | |
22 | ||
23 | while (*p) { | |
24 | parent = *p; | |
25 | rnode = rb_entry(parent, struct callchain_node, rb_node); | |
26 | ||
27 | if (rnode->hit < chain->hit) | |
28 | p = &(*p)->rb_left; | |
29 | else | |
30 | p = &(*p)->rb_right; | |
31 | } | |
32 | ||
33 | rb_link_node(&chain->rb_node, parent, p); | |
34 | rb_insert_color(&chain->rb_node, root); | |
35 | } | |
36 | ||
37 | /* | |
38 | * Once we get every callchains from the stream, we can now | |
39 | * sort them by hit | |
40 | */ | |
41 | void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node) | |
42 | { | |
43 | struct callchain_node *child; | |
44 | ||
45 | list_for_each_entry(child, &node->children, brothers) | |
46 | sort_chain_to_rbtree(rb_root, child); | |
47 | ||
48 | if (node->hit) | |
49 | rb_insert_callchain(rb_root, node); | |
50 | } | |
51 | ||
52 | static struct callchain_node *create_child(struct callchain_node *parent) | |
53 | { | |
54 | struct callchain_node *new; | |
55 | ||
56 | new = malloc(sizeof(*new)); | |
57 | if (!new) { | |
58 | perror("not enough memory to create child for code path tree"); | |
59 | return NULL; | |
60 | } | |
61 | new->parent = parent; | |
62 | INIT_LIST_HEAD(&new->children); | |
63 | INIT_LIST_HEAD(&new->val); | |
64 | list_add_tail(&new->brothers, &parent->children); | |
65 | ||
66 | return new; | |
67 | } | |
68 | ||
69 | static void | |
70 | fill_node(struct callchain_node *node, struct ip_callchain *chain, int start) | |
71 | { | |
72 | int i; | |
73 | ||
74 | for (i = start; i < chain->nr; i++) { | |
75 | struct callchain_list *call; | |
76 | ||
77 | call = malloc(sizeof(*chain)); | |
78 | if (!call) { | |
79 | perror("not enough memory for the code path tree"); | |
80 | return; | |
81 | } | |
82 | call->ip = chain->ips[i]; | |
83 | list_add_tail(&call->list, &node->val); | |
84 | } | |
85 | node->val_nr = i - start; | |
86 | } | |
87 | ||
88 | static void add_child(struct callchain_node *parent, struct ip_callchain *chain) | |
89 | { | |
90 | struct callchain_node *new; | |
91 | ||
92 | new = create_child(parent); | |
93 | fill_node(new, chain, parent->val_nr); | |
94 | ||
95 | new->hit = 1; | |
96 | } | |
97 | ||
98 | static void | |
99 | split_add_child(struct callchain_node *parent, struct ip_callchain *chain, | |
100 | struct callchain_list *to_split, int idx) | |
101 | { | |
102 | struct callchain_node *new; | |
103 | ||
104 | /* split */ | |
105 | new = create_child(parent); | |
106 | list_move_tail(&to_split->list, &new->val); | |
107 | new->hit = parent->hit; | |
108 | parent->hit = 0; | |
109 | parent->val_nr = idx; | |
110 | ||
111 | /* create the new one */ | |
112 | add_child(parent, chain); | |
113 | } | |
114 | ||
115 | static int | |
116 | __append_chain(struct callchain_node *root, struct ip_callchain *chain, | |
117 | int start); | |
118 | ||
119 | static int | |
120 | __append_chain_children(struct callchain_node *root, struct ip_callchain *chain) | |
121 | { | |
122 | struct callchain_node *rnode; | |
123 | ||
124 | /* lookup in childrens */ | |
125 | list_for_each_entry(rnode, &root->children, brothers) { | |
126 | int ret = __append_chain(rnode, chain, root->val_nr); | |
127 | if (!ret) | |
128 | return 0; | |
129 | } | |
130 | return -1; | |
131 | } | |
132 | ||
133 | static int | |
134 | __append_chain(struct callchain_node *root, struct ip_callchain *chain, | |
135 | int start) | |
136 | { | |
137 | struct callchain_list *cnode; | |
138 | int i = start; | |
139 | bool found = false; | |
140 | ||
141 | /* lookup in the current node */ | |
142 | list_for_each_entry(cnode, &root->val, list) { | |
143 | if (cnode->ip != chain->ips[i++]) | |
144 | break; | |
145 | if (!found) | |
146 | found = true; | |
147 | if (i == chain->nr) | |
148 | break; | |
149 | } | |
150 | ||
151 | /* matches not, relay on the parent */ | |
152 | if (!found) | |
153 | return -1; | |
154 | ||
155 | /* we match only a part of the node. Split it and add the new chain */ | |
156 | if (i < root->val_nr) { | |
157 | split_add_child(root, chain, cnode, i); | |
158 | return 0; | |
159 | } | |
160 | ||
161 | /* we match 100% of the path, increment the hit */ | |
162 | if (i == root->val_nr) { | |
163 | root->hit++; | |
164 | return 0; | |
165 | } | |
166 | ||
167 | return __append_chain_children(root, chain); | |
168 | } | |
169 | ||
170 | void append_chain(struct callchain_node *root, struct ip_callchain *chain) | |
171 | { | |
172 | if (__append_chain_children(root, chain) == -1) | |
173 | add_child(root, chain); | |
174 | } |