Branch data Line data Source code
1 : : #include <unistd.h>
2 : : #include <stdlib.h>
3 : : #include "types.h"
4 : : #include "rbtree.h"
5 : : #include "util.h"
6 : : #include "syscall.h"
7 : : #include "kcmp-ids.h"
8 : :
9 : : /*
10 : : * We track shared files by global rbtree, where each node might
11 : : * be a root for subtree. The reason for that is the nature of data
12 : : * we obtain from operating system.
13 : : *
14 : : * Basically OS provides us two ways to distinguish files
15 : : *
16 : : * - information obtained from fstat call
17 : : * - shiny new sys_kcmp system call (which may compare the file descriptor
18 : : * pointers inside the kernel and provide us order info)
19 : : *
20 : : * So, to speedup procedure of searching for shared file descriptors
21 : : * we use both techniques. From fstat call we get that named general file
22 : : * IDs (genid) which are carried in the main rbtree.
23 : : *
24 : : * In case if two genid are the same -- we need to use a second way and
25 : : * call for sys_kcmp. Thus, if kernel tells us that files have identical
26 : : * genid but in real they are different from kernel point of view -- we assign
27 : : * a second unique key (subid) to such file descriptor and put it into a subtree.
28 : : *
29 : : * So the tree will look like
30 : : *
31 : : * (root)
32 : : * genid-1
33 : : * / \
34 : : * genid-2 genid-3
35 : : * / \ / \
36 : : *
37 : : * Where each genid node might be a sub-rbtree as well
38 : : *
39 : : * (genid-N)
40 : : * / \
41 : : * subid-1 subid-2
42 : : * / \ / \
43 : : *
44 : : * Carrying two rbtree at once allow us to minimize the number
45 : : * of sys_kcmp syscalls, also to collect and dump file descriptors
46 : : * in one pass.
47 : : */
48 : :
49 : : struct kid_entry {
50 : : struct rb_node node;
51 : :
52 : : struct rb_root subtree_root;
53 : : struct rb_node subtree_node;
54 : :
55 : : u32 subid; /* subid is always unique */
56 : : struct kid_elem elem;
57 : : } __aligned(sizeof(long));
58 : :
59 : 820 : static void show_subnode(struct rb_node *node, int self)
60 : : {
61 : 820 : struct kid_entry *this = rb_entry(node, struct kid_entry, subtree_node);
62 : :
63 [ + + ]: 820 : pr_info("\t\t| %#x.%#x %s\n", this->elem.genid, this->subid,
64 : : self ? "(self)" : "");
65 [ + + ]: 820 : if (node->rb_left) {
66 : 2 : pr_info("\t\t| left:\n");
67 : 2 : show_subnode(node->rb_left, 0);
68 : 2 : pr_info("\t\t| --l\n");
69 : : }
70 [ + + ]: 820 : if (node->rb_right) {
71 : 149 : pr_info("\t\t| right:\n");
72 : 149 : show_subnode(node->rb_right, 0);
73 : 149 : pr_info("\t\t| --r\n");
74 : : }
75 : 820 : }
76 : :
77 : 669 : static void show_subtree(struct rb_root *root)
78 : : {
79 : 669 : pr_info("\t\t| SubTree\n");
80 : 669 : show_subnode(root->rb_node, 1);
81 : 669 : }
82 : :
83 : 669 : static void show_node(struct rb_node *node)
84 : : {
85 : 669 : struct kid_entry *this = rb_entry(node, struct kid_entry, node);
86 : :
87 : 669 : pr_info("\t%#x.%#x\n", this->elem.genid, this->subid);
88 [ + + ]: 669 : if (node->rb_left) {
89 : 230 : pr_info("\tleft:\n");
90 : 230 : show_node(node->rb_left);
91 : 230 : pr_info("\t--l\n");
92 : : }
93 [ + + ]: 669 : if (node->rb_right) {
94 : 273 : pr_info("\tright:\n");
95 : 273 : show_node(node->rb_right);
96 : 273 : pr_info("\t--r\n");
97 : : }
98 : :
99 : 669 : show_subtree(&this->subtree_root);
100 : 669 : pr_info("\t--s\n");
101 : 669 : }
102 : :
103 : 166 : void kid_show_tree(struct kid_tree *tree)
104 : : {
105 : 166 : struct rb_root *root = &tree->root;
106 : :
107 : 166 : pr_info("\tTree of %d objects\n", tree->kcmp_type);
108 [ + - ]: 166 : if (root->rb_node)
109 : 166 : show_node(root->rb_node);
110 : 166 : }
111 : :
112 : 2216 : static struct kid_entry *alloc_kid_entry(struct kid_tree *tree, struct kid_elem *elem)
113 : : {
114 : : struct kid_entry *e;
115 : :
116 [ - + ]: 2216 : e = xmalloc(sizeof(*e));
117 [ + - ]: 2216 : if (!e)
118 : : goto err;
119 : :
120 : 2216 : e->subid = tree->subid++;
121 : 2216 : e->elem = *elem;
122 : :
123 : : /* Make sure no overflow here */
124 [ - + ]: 2216 : BUG_ON(!e->subid);
125 : :
126 : 2216 : rb_init_node(&e->node);
127 : 2216 : rb_init_node(&e->subtree_node);
128 : 2216 : e->subtree_root = RB_ROOT;
129 : 2216 : rb_link_and_balance(&e->subtree_root, &e->subtree_node,
130 : : NULL, &e->subtree_root.rb_node);
131 : : err:
132 : 2216 : return e;
133 : : }
134 : :
135 : 1568 : static u32 kid_generate_sub(struct kid_tree *tree, struct kid_entry *e,
136 : : struct kid_elem *elem, int *new_id)
137 : : {
138 : 1568 : struct rb_node *node = e->subtree_root.rb_node;
139 : 1568 : struct kid_entry *sub = NULL;
140 : :
141 : 1568 : struct rb_node **new = &e->subtree_root.rb_node;
142 : 1568 : struct rb_node *parent = NULL;
143 : :
144 [ - + ]: 1568 : BUG_ON(!node);
145 : :
146 [ + + ]: 3267 : while (node) {
147 : 2384 : struct kid_entry *this = rb_entry(node, struct kid_entry, subtree_node);
148 : 2384 : int ret = sys_kcmp(this->elem.pid, elem->pid, tree->kcmp_type,
149 : 4768 : this->elem.idx, elem->idx);
150 : :
151 : 2384 : parent = *new;
152 [ - + ]: 2384 : if (ret < 0)
153 : 0 : node = node->rb_left, new = &((*new)->rb_left);
154 [ + + ]: 2384 : else if (ret > 0)
155 : 1699 : node = node->rb_right, new = &((*new)->rb_right);
156 : : else
157 : 2384 : return this->subid;
158 : : }
159 : :
160 : 883 : sub = alloc_kid_entry(tree, elem);
161 [ + - ]: 883 : if (!sub)
162 : : return 0;
163 : :
164 : 883 : rb_link_and_balance(&e->subtree_root, &sub->subtree_node, parent, new);
165 : 883 : *new_id = 1;
166 : 1568 : return sub->subid;
167 : : }
168 : :
169 : 2901 : u32 kid_generate_gen(struct kid_tree *tree,
170 : : struct kid_elem *elem, int *new_id)
171 : : {
172 : 2901 : struct rb_node *node = tree->root.rb_node;
173 : 2901 : struct kid_entry *e = NULL;
174 : :
175 : 2901 : struct rb_node **new = &tree->root.rb_node;
176 : 2901 : struct rb_node *parent = NULL;
177 : :
178 [ + + ]: 4826 : while (node) {
179 : 3493 : struct kid_entry *this = rb_entry(node, struct kid_entry, node);
180 : :
181 : 3493 : parent = *new;
182 [ + + ]: 3493 : if (elem->genid < this->elem.genid)
183 : 856 : node = node->rb_left, new = &((*new)->rb_left);
184 [ + + ]: 2637 : else if (elem->genid > this->elem.genid)
185 : 1069 : node = node->rb_right, new = &((*new)->rb_right);
186 : : else
187 : 3493 : return kid_generate_sub(tree, this, elem, new_id);
188 : : }
189 : :
190 : 1333 : e = alloc_kid_entry(tree, elem);
191 [ + - ]: 1333 : if (!e)
192 : : return 0;
193 : :
194 : 1333 : rb_link_and_balance(&tree->root, &e->node, parent, new);
195 : 1333 : *new_id = 1;
196 : 2901 : return e->subid;
197 : :
198 : 2216 : }
199 : :
|
