Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
e8054b65 PH |
2 | /* |
3 | * NUMA support for s390 | |
4 | * | |
5 | * A tree structure used for machine topology mangling | |
6 | * | |
7 | * Copyright IBM Corp. 2015 | |
8 | */ | |
9 | ||
10 | #include <linux/kernel.h> | |
8c910580 | 11 | #include <linux/bootmem.h> |
e8054b65 PH |
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 | * toptree_alloc - Allocate and initialize a new tree node. | |
22 | * @level: The node's vertical level; level 0 contains the leaves. | |
23 | * @id: ID number, explicitly not unique beyond scope of node's siblings | |
24 | * | |
25 | * Allocate a new tree node and initialize it. | |
26 | * | |
27 | * RETURNS: | |
28 | * Pointer to the new tree node or NULL on error | |
29 | */ | |
8c910580 | 30 | struct toptree __ref *toptree_alloc(int level, int id) |
e8054b65 | 31 | { |
8c910580 | 32 | struct toptree *res; |
e8054b65 | 33 | |
8c910580 HC |
34 | if (slab_is_available()) |
35 | res = kzalloc(sizeof(*res), GFP_KERNEL); | |
36 | else | |
37 | res = memblock_virt_alloc(sizeof(*res), 8); | |
e8054b65 PH |
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 | * toptree_remove - Remove a tree node from a tree | |
51 | * @cand: Pointer to the node to remove | |
52 | * | |
53 | * The node is detached from its parent node. The parent node's | |
54 | * masks will be updated to reflect the loss of the child. | |
55 | */ | |
56 | static 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 | * toptree_free - discard a tree node | |
68 | * @cand: Pointer to the tree node to discard | |
69 | * | |
70 | * Checks if @cand is attached to a parent node. Detaches it | |
71 | * cleanly using toptree_remove. Possible children are freed | |
72 | * recursively. In the end @cand itself is freed. | |
73 | */ | |
8c910580 | 74 | void __ref toptree_free(struct toptree *cand) |
e8054b65 PH |
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); | |
8c910580 HC |
82 | if (slab_is_available()) |
83 | kfree(cand); | |
84 | else | |
85 | memblock_free_early((unsigned long)cand, sizeof(*cand)); | |
e8054b65 PH |
86 | } |
87 | ||
88 | /** | |
89 | * toptree_update_mask - Update node bitmasks | |
90 | * @cand: Pointer to a tree node | |
91 | * | |
92 | * The node's cpumask will be updated by combining all children's | |
93 | * masks. Then toptree_update_mask is called recursively for the | |
94 | * parent if applicable. | |
95 | * | |
96 | * NOTE: | |
97 | * This must not be called on leaves. If called on a leaf, its | |
98 | * CPU mask is cleared and lost. | |
99 | */ | |
100 | void 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 | * toptree_insert - Insert a tree node into tree | |
113 | * @cand: Pointer to the node to insert | |
114 | * @target: Pointer to the node to which @cand will added as a child | |
115 | * | |
116 | * Insert a tree node into a tree. Masks will be updated automatically. | |
117 | * | |
118 | * RETURNS: | |
119 | * 0 on success, -1 if NULL is passed as argument or the node levels | |
120 | * don't fit. | |
121 | */ | |
122 | static 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 | * toptree_move_children - Move all child nodes of a node to a new place | |
136 | * @cand: Pointer to the node whose children are to be moved | |
137 | * @target: Pointer to the node to which @cand's children will be attached | |
138 | * | |
139 | * Take all child nodes of @cand and move them using toptree_move. | |
140 | */ | |
141 | static 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 | * toptree_unify - Merge children with same ID | |
151 | * @cand: Pointer to node whose direct children should be made unique | |
152 | * | |
153 | * When mangling the tree it is possible that a node has two or more children | |
154 | * which have the same ID. This routine merges these children into one and | |
155 | * moves all children of the merged nodes into the unified node. | |
156 | */ | |
157 | void toptree_unify(struct toptree *cand) | |
158 | { | |
159 | struct toptree *child, *tmp, *cand_copy; | |
160 | ||
161 | /* Threads cannot be split, cores are not split */ | |
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 | * toptree_move - Move a node to another context | |
184 | * @cand: Pointer to the node to move | |
185 | * @target: Pointer to the node where @cand should go | |
186 | * | |
187 | * In the easiest case @cand is exactly on the level below @target | |
188 | * and will be immediately moved to the target. | |
189 | * | |
190 | * If @target's level is not the direct parent level of @cand, | |
191 | * nodes for the missing levels are created and put between | |
192 | * @cand and @target. The "stacking" nodes' IDs are taken from | |
193 | * @cand's parents. | |
194 | * | |
195 | * After this it is likely to have redundant nodes in the tree | |
196 | * which are addressed by means of toptree_unify. | |
197 | */ | |
198 | void 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 | * toptree_get_child - Access a tree node's child by its ID | |
229 | * @cand: Pointer to tree node whose child is to access | |
230 | * @id: The desired child's ID | |
231 | * | |
232 | * @cand's children are searched for a child with matching ID. | |
233 | * If no match can be found, a new child with the desired ID | |
234 | * is created and returned. | |
235 | */ | |
236 | struct 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 | * toptree_first - Find the first descendant on specified level | |
250 | * @context: Pointer to tree node whose descendants are to be used | |
251 | * @level: The level of interest | |
252 | * | |
253 | * RETURNS: | |
254 | * @context's first descendant on the specified level, or NULL | |
255 | * if there is no matching descendant | |
256 | */ | |
257 | struct 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 | * toptree_next_sibling - Return next sibling | |
276 | * @cur: Pointer to a tree node | |
277 | * | |
278 | * RETURNS: | |
279 | * If @cur has a parent and is not the last in the parent's children list, | |
280 | * the next sibling is returned. Or NULL when there are no siblings left. | |
281 | */ | |
282 | static 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 | * toptree_next - Tree traversal function | |
295 | * @cur: Pointer to current element | |
296 | * @context: Pointer to the root node of the tree or subtree to | |
297 | * be traversed. | |
298 | * @level: The level of interest. | |
299 | * | |
300 | * RETURNS: | |
301 | * Pointer to the next node on level @level | |
302 | * or NULL when there is no next node. | |
303 | */ | |
304 | struct 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 | /* Step up */ | |
322 | cur_context = cur_context->parent; | |
323 | /* Step aside */ | |
324 | tmp = toptree_next_sibling(cur_context); | |
325 | if (tmp != NULL) { | |
326 | /* Step down */ | |
327 | tmp = toptree_first(tmp, level); | |
328 | if (tmp != NULL) | |
329 | return tmp; | |
330 | } | |
331 | } | |
332 | return NULL; | |
333 | } | |
334 | ||
335 | /** | |
336 | * toptree_count - Count descendants on specified level | |
337 | * @context: Pointer to node whose descendants are to be considered | |
338 | * @level: Only descendants on the specified level will be counted | |
339 | * | |
340 | * RETURNS: | |
341 | * Number of descendants on the specified level | |
342 | */ | |
343 | int 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 | } |