Commit | Line | Data |
---|---|---|
e8054b65 PH |
1 | /* |
2 | * NUMA support for s390 | |
3 | * | |
4 | * A tree structure used for machine topology mangling | |
5 | * | |
6 | * Copyright IBM Corp. 2015 | |
7 | */ | |
8 | ||
9 | #include <linux/kernel.h> | |
10 | #include <linux/cpumask.h> | |
11 | #include <linux/list.h> | |
12 | #include <linux/list_sort.h> | |
13 | #include <linux/slab.h> | |
14 | #include <asm/numa.h> | |
15 | ||
16 | #include "toptree.h" | |
17 | ||
18 | /** | |
19 | * toptree_alloc - Allocate and initialize a new tree node. | |
20 | * @level: The node's vertical level; level 0 contains the leaves. | |
21 | * @id: ID number, explicitly not unique beyond scope of node's siblings | |
22 | * | |
23 | * Allocate a new tree node and initialize it. | |
24 | * | |
25 | * RETURNS: | |
26 | * Pointer to the new tree node or NULL on error | |
27 | */ | |
28 | struct toptree *toptree_alloc(int level, int id) | |
29 | { | |
30 | struct toptree *res = kzalloc(sizeof(struct toptree), GFP_KERNEL); | |
31 | ||
32 | if (!res) | |
33 | return res; | |
34 | ||
35 | INIT_LIST_HEAD(&res->children); | |
36 | INIT_LIST_HEAD(&res->sibling); | |
37 | cpumask_clear(&res->mask); | |
38 | res->level = level; | |
39 | res->id = id; | |
40 | return res; | |
41 | } | |
42 | ||
43 | /** | |
44 | * toptree_remove - Remove a tree node from a tree | |
45 | * @cand: Pointer to the node to remove | |
46 | * | |
47 | * The node is detached from its parent node. The parent node's | |
48 | * masks will be updated to reflect the loss of the child. | |
49 | */ | |
50 | static void toptree_remove(struct toptree *cand) | |
51 | { | |
52 | struct toptree *oldparent; | |
53 | ||
54 | list_del_init(&cand->sibling); | |
55 | oldparent = cand->parent; | |
56 | cand->parent = NULL; | |
57 | toptree_update_mask(oldparent); | |
58 | } | |
59 | ||
60 | /** | |
61 | * toptree_free - discard a tree node | |
62 | * @cand: Pointer to the tree node to discard | |
63 | * | |
64 | * Checks if @cand is attached to a parent node. Detaches it | |
65 | * cleanly using toptree_remove. Possible children are freed | |
66 | * recursively. In the end @cand itself is freed. | |
67 | */ | |
68 | void toptree_free(struct toptree *cand) | |
69 | { | |
70 | struct toptree *child, *tmp; | |
71 | ||
72 | if (cand->parent) | |
73 | toptree_remove(cand); | |
74 | toptree_for_each_child_safe(child, tmp, cand) | |
75 | toptree_free(child); | |
76 | kfree(cand); | |
77 | } | |
78 | ||
79 | /** | |
80 | * toptree_update_mask - Update node bitmasks | |
81 | * @cand: Pointer to a tree node | |
82 | * | |
83 | * The node's cpumask will be updated by combining all children's | |
84 | * masks. Then toptree_update_mask is called recursively for the | |
85 | * parent if applicable. | |
86 | * | |
87 | * NOTE: | |
88 | * This must not be called on leaves. If called on a leaf, its | |
89 | * CPU mask is cleared and lost. | |
90 | */ | |
91 | void toptree_update_mask(struct toptree *cand) | |
92 | { | |
93 | struct toptree *child; | |
94 | ||
95 | cpumask_clear(&cand->mask); | |
96 | list_for_each_entry(child, &cand->children, sibling) | |
97 | cpumask_or(&cand->mask, &cand->mask, &child->mask); | |
98 | if (cand->parent) | |
99 | toptree_update_mask(cand->parent); | |
100 | } | |
101 | ||
102 | /** | |
103 | * toptree_insert - Insert a tree node into tree | |
104 | * @cand: Pointer to the node to insert | |
105 | * @target: Pointer to the node to which @cand will added as a child | |
106 | * | |
107 | * Insert a tree node into a tree. Masks will be updated automatically. | |
108 | * | |
109 | * RETURNS: | |
110 | * 0 on success, -1 if NULL is passed as argument or the node levels | |
111 | * don't fit. | |
112 | */ | |
113 | static int toptree_insert(struct toptree *cand, struct toptree *target) | |
114 | { | |
115 | if (!cand || !target) | |
116 | return -1; | |
117 | if (target->level != (cand->level + 1)) | |
118 | return -1; | |
119 | list_add_tail(&cand->sibling, &target->children); | |
120 | cand->parent = target; | |
121 | toptree_update_mask(target); | |
122 | return 0; | |
123 | } | |
124 | ||
125 | /** | |
126 | * toptree_move_children - Move all child nodes of a node to a new place | |
127 | * @cand: Pointer to the node whose children are to be moved | |
128 | * @target: Pointer to the node to which @cand's children will be attached | |
129 | * | |
130 | * Take all child nodes of @cand and move them using toptree_move. | |
131 | */ | |
132 | static void toptree_move_children(struct toptree *cand, struct toptree *target) | |
133 | { | |
134 | struct toptree *child, *tmp; | |
135 | ||
136 | toptree_for_each_child_safe(child, tmp, cand) | |
137 | toptree_move(child, target); | |
138 | } | |
139 | ||
140 | /** | |
141 | * toptree_unify - Merge children with same ID | |
142 | * @cand: Pointer to node whose direct children should be made unique | |
143 | * | |
144 | * When mangling the tree it is possible that a node has two or more children | |
145 | * which have the same ID. This routine merges these children into one and | |
146 | * moves all children of the merged nodes into the unified node. | |
147 | */ | |
148 | void toptree_unify(struct toptree *cand) | |
149 | { | |
150 | struct toptree *child, *tmp, *cand_copy; | |
151 | ||
152 | /* Threads cannot be split, cores are not split */ | |
153 | if (cand->level < 2) | |
154 | return; | |
155 | ||
156 | cand_copy = toptree_alloc(cand->level, 0); | |
157 | toptree_for_each_child_safe(child, tmp, cand) { | |
158 | struct toptree *tmpchild; | |
159 | ||
160 | if (!cpumask_empty(&child->mask)) { | |
161 | tmpchild = toptree_get_child(cand_copy, child->id); | |
162 | toptree_move_children(child, tmpchild); | |
163 | } | |
164 | toptree_free(child); | |
165 | } | |
166 | toptree_move_children(cand_copy, cand); | |
167 | toptree_free(cand_copy); | |
168 | ||
169 | toptree_for_each_child(child, cand) | |
170 | toptree_unify(child); | |
171 | } | |
172 | ||
173 | /** | |
174 | * toptree_move - Move a node to another context | |
175 | * @cand: Pointer to the node to move | |
176 | * @target: Pointer to the node where @cand should go | |
177 | * | |
178 | * In the easiest case @cand is exactly on the level below @target | |
179 | * and will be immediately moved to the target. | |
180 | * | |
181 | * If @target's level is not the direct parent level of @cand, | |
182 | * nodes for the missing levels are created and put between | |
183 | * @cand and @target. The "stacking" nodes' IDs are taken from | |
184 | * @cand's parents. | |
185 | * | |
186 | * After this it is likely to have redundant nodes in the tree | |
187 | * which are addressed by means of toptree_unify. | |
188 | */ | |
189 | void toptree_move(struct toptree *cand, struct toptree *target) | |
190 | { | |
191 | struct toptree *stack_target, *real_insert_point, *ptr, *tmp; | |
192 | ||
193 | if (cand->level + 1 == target->level) { | |
194 | toptree_remove(cand); | |
195 | toptree_insert(cand, target); | |
196 | return; | |
197 | } | |
198 | ||
199 | real_insert_point = NULL; | |
200 | ptr = cand; | |
201 | stack_target = NULL; | |
202 | ||
203 | do { | |
204 | tmp = stack_target; | |
205 | stack_target = toptree_alloc(ptr->level + 1, | |
206 | ptr->parent->id); | |
207 | toptree_insert(tmp, stack_target); | |
208 | if (!real_insert_point) | |
209 | real_insert_point = stack_target; | |
210 | ptr = ptr->parent; | |
211 | } while (stack_target->level < (target->level - 1)); | |
212 | ||
213 | toptree_remove(cand); | |
214 | toptree_insert(cand, real_insert_point); | |
215 | toptree_insert(stack_target, target); | |
216 | } | |
217 | ||
218 | /** | |
219 | * toptree_get_child - Access a tree node's child by its ID | |
220 | * @cand: Pointer to tree node whose child is to access | |
221 | * @id: The desired child's ID | |
222 | * | |
223 | * @cand's children are searched for a child with matching ID. | |
224 | * If no match can be found, a new child with the desired ID | |
225 | * is created and returned. | |
226 | */ | |
227 | struct toptree *toptree_get_child(struct toptree *cand, int id) | |
228 | { | |
229 | struct toptree *child; | |
230 | ||
231 | toptree_for_each_child(child, cand) | |
232 | if (child->id == id) | |
233 | return child; | |
234 | child = toptree_alloc(cand->level-1, id); | |
235 | toptree_insert(child, cand); | |
236 | return child; | |
237 | } | |
238 | ||
239 | /** | |
240 | * toptree_first - Find the first descendant on specified level | |
241 | * @context: Pointer to tree node whose descendants are to be used | |
242 | * @level: The level of interest | |
243 | * | |
244 | * RETURNS: | |
245 | * @context's first descendant on the specified level, or NULL | |
246 | * if there is no matching descendant | |
247 | */ | |
248 | struct toptree *toptree_first(struct toptree *context, int level) | |
249 | { | |
250 | struct toptree *child, *tmp; | |
251 | ||
252 | if (context->level == level) | |
253 | return context; | |
254 | ||
255 | if (!list_empty(&context->children)) { | |
256 | list_for_each_entry(child, &context->children, sibling) { | |
257 | tmp = toptree_first(child, level); | |
258 | if (tmp) | |
259 | return tmp; | |
260 | } | |
261 | } | |
262 | return NULL; | |
263 | } | |
264 | ||
265 | /** | |
266 | * toptree_next_sibling - Return next sibling | |
267 | * @cur: Pointer to a tree node | |
268 | * | |
269 | * RETURNS: | |
270 | * If @cur has a parent and is not the last in the parent's children list, | |
271 | * the next sibling is returned. Or NULL when there are no siblings left. | |
272 | */ | |
273 | static struct toptree *toptree_next_sibling(struct toptree *cur) | |
274 | { | |
275 | if (cur->parent == NULL) | |
276 | return NULL; | |
277 | ||
278 | if (cur == list_last_entry(&cur->parent->children, | |
279 | struct toptree, sibling)) | |
280 | return NULL; | |
281 | return (struct toptree *) list_next_entry(cur, sibling); | |
282 | } | |
283 | ||
284 | /** | |
285 | * toptree_next - Tree traversal function | |
286 | * @cur: Pointer to current element | |
287 | * @context: Pointer to the root node of the tree or subtree to | |
288 | * be traversed. | |
289 | * @level: The level of interest. | |
290 | * | |
291 | * RETURNS: | |
292 | * Pointer to the next node on level @level | |
293 | * or NULL when there is no next node. | |
294 | */ | |
295 | struct toptree *toptree_next(struct toptree *cur, struct toptree *context, | |
296 | int level) | |
297 | { | |
298 | struct toptree *cur_context, *tmp; | |
299 | ||
300 | if (!cur) | |
301 | return NULL; | |
302 | ||
303 | if (context->level == level) | |
304 | return NULL; | |
305 | ||
306 | tmp = toptree_next_sibling(cur); | |
307 | if (tmp != NULL) | |
308 | return tmp; | |
309 | ||
310 | cur_context = cur; | |
311 | while (cur_context->level < context->level - 1) { | |
312 | /* Step up */ | |
313 | cur_context = cur_context->parent; | |
314 | /* Step aside */ | |
315 | tmp = toptree_next_sibling(cur_context); | |
316 | if (tmp != NULL) { | |
317 | /* Step down */ | |
318 | tmp = toptree_first(tmp, level); | |
319 | if (tmp != NULL) | |
320 | return tmp; | |
321 | } | |
322 | } | |
323 | return NULL; | |
324 | } | |
325 | ||
326 | /** | |
327 | * toptree_count - Count descendants on specified level | |
328 | * @context: Pointer to node whose descendants are to be considered | |
329 | * @level: Only descendants on the specified level will be counted | |
330 | * | |
331 | * RETURNS: | |
332 | * Number of descendants on the specified level | |
333 | */ | |
334 | int toptree_count(struct toptree *context, int level) | |
335 | { | |
336 | struct toptree *cur; | |
337 | int cnt = 0; | |
338 | ||
339 | toptree_for_each(cur, context, level) | |
340 | cnt++; | |
341 | return cnt; | |
342 | } |