1
2
3
4
5
6
7
8
9
10#include <linux/kernel.h>
11#include <linux/memblock.h>
12#include <linux/cpumask.h>
13#include <linux/list.h>
14#include <linux/list_sort.h>
15#include <linux/slab.h>
16#include <asm/numa.h>
17
18#include "toptree.h"
19
20
21
22
23
24
25
26
27
28
29
30struct toptree __ref *toptree_alloc(int level, int id)
31{
32 struct toptree *res;
33
34 if (slab_is_available())
35 res = kzalloc(sizeof(*res), GFP_KERNEL);
36 else
37 res = memblock_alloc(sizeof(*res), 8);
38 if (!res)
39 return res;
40
41 INIT_LIST_HEAD(&res->children);
42 INIT_LIST_HEAD(&res->sibling);
43 cpumask_clear(&res->mask);
44 res->level = level;
45 res->id = id;
46 return res;
47}
48
49
50
51
52
53
54
55
56static void toptree_remove(struct toptree *cand)
57{
58 struct toptree *oldparent;
59
60 list_del_init(&cand->sibling);
61 oldparent = cand->parent;
62 cand->parent = NULL;
63 toptree_update_mask(oldparent);
64}
65
66
67
68
69
70
71
72
73
74void __ref toptree_free(struct toptree *cand)
75{
76 struct toptree *child, *tmp;
77
78 if (cand->parent)
79 toptree_remove(cand);
80 toptree_for_each_child_safe(child, tmp, cand)
81 toptree_free(child);
82 if (slab_is_available())
83 kfree(cand);
84 else
85 memblock_free_early((unsigned long)cand, sizeof(*cand));
86}
87
88
89
90
91
92
93
94
95
96
97
98
99
100void toptree_update_mask(struct toptree *cand)
101{
102 struct toptree *child;
103
104 cpumask_clear(&cand->mask);
105 list_for_each_entry(child, &cand->children, sibling)
106 cpumask_or(&cand->mask, &cand->mask, &child->mask);
107 if (cand->parent)
108 toptree_update_mask(cand->parent);
109}
110
111
112
113
114
115
116
117
118
119
120
121
122static int toptree_insert(struct toptree *cand, struct toptree *target)
123{
124 if (!cand || !target)
125 return -1;
126 if (target->level != (cand->level + 1))
127 return -1;
128 list_add_tail(&cand->sibling, &target->children);
129 cand->parent = target;
130 toptree_update_mask(target);
131 return 0;
132}
133
134
135
136
137
138
139
140
141static void toptree_move_children(struct toptree *cand, struct toptree *target)
142{
143 struct toptree *child, *tmp;
144
145 toptree_for_each_child_safe(child, tmp, cand)
146 toptree_move(child, target);
147}
148
149
150
151
152
153
154
155
156
157void toptree_unify(struct toptree *cand)
158{
159 struct toptree *child, *tmp, *cand_copy;
160
161
162 if (cand->level < 2)
163 return;
164
165 cand_copy = toptree_alloc(cand->level, 0);
166 toptree_for_each_child_safe(child, tmp, cand) {
167 struct toptree *tmpchild;
168
169 if (!cpumask_empty(&child->mask)) {
170 tmpchild = toptree_get_child(cand_copy, child->id);
171 toptree_move_children(child, tmpchild);
172 }
173 toptree_free(child);
174 }
175 toptree_move_children(cand_copy, cand);
176 toptree_free(cand_copy);
177
178 toptree_for_each_child(child, cand)
179 toptree_unify(child);
180}
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198void toptree_move(struct toptree *cand, struct toptree *target)
199{
200 struct toptree *stack_target, *real_insert_point, *ptr, *tmp;
201
202 if (cand->level + 1 == target->level) {
203 toptree_remove(cand);
204 toptree_insert(cand, target);
205 return;
206 }
207
208 real_insert_point = NULL;
209 ptr = cand;
210 stack_target = NULL;
211
212 do {
213 tmp = stack_target;
214 stack_target = toptree_alloc(ptr->level + 1,
215 ptr->parent->id);
216 toptree_insert(tmp, stack_target);
217 if (!real_insert_point)
218 real_insert_point = stack_target;
219 ptr = ptr->parent;
220 } while (stack_target->level < (target->level - 1));
221
222 toptree_remove(cand);
223 toptree_insert(cand, real_insert_point);
224 toptree_insert(stack_target, target);
225}
226
227
228
229
230
231
232
233
234
235
236struct toptree *toptree_get_child(struct toptree *cand, int id)
237{
238 struct toptree *child;
239
240 toptree_for_each_child(child, cand)
241 if (child->id == id)
242 return child;
243 child = toptree_alloc(cand->level-1, id);
244 toptree_insert(child, cand);
245 return child;
246}
247
248
249
250
251
252
253
254
255
256
257struct toptree *toptree_first(struct toptree *context, int level)
258{
259 struct toptree *child, *tmp;
260
261 if (context->level == level)
262 return context;
263
264 if (!list_empty(&context->children)) {
265 list_for_each_entry(child, &context->children, sibling) {
266 tmp = toptree_first(child, level);
267 if (tmp)
268 return tmp;
269 }
270 }
271 return NULL;
272}
273
274
275
276
277
278
279
280
281
282static struct toptree *toptree_next_sibling(struct toptree *cur)
283{
284 if (cur->parent == NULL)
285 return NULL;
286
287 if (cur == list_last_entry(&cur->parent->children,
288 struct toptree, sibling))
289 return NULL;
290 return (struct toptree *) list_next_entry(cur, sibling);
291}
292
293
294
295
296
297
298
299
300
301
302
303
304struct toptree *toptree_next(struct toptree *cur, struct toptree *context,
305 int level)
306{
307 struct toptree *cur_context, *tmp;
308
309 if (!cur)
310 return NULL;
311
312 if (context->level == level)
313 return NULL;
314
315 tmp = toptree_next_sibling(cur);
316 if (tmp != NULL)
317 return tmp;
318
319 cur_context = cur;
320 while (cur_context->level < context->level - 1) {
321
322 cur_context = cur_context->parent;
323
324 tmp = toptree_next_sibling(cur_context);
325 if (tmp != NULL) {
326
327 tmp = toptree_first(tmp, level);
328 if (tmp != NULL)
329 return tmp;
330 }
331 }
332 return NULL;
333}
334
335
336
337
338
339
340
341
342
343int toptree_count(struct toptree *context, int level)
344{
345 struct toptree *cur;
346 int cnt = 0;
347
348 toptree_for_each(cur, context, level)
349 cnt++;
350 return cnt;
351}
352