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 */
toptree_alloc(int level,int id)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 */
toptree_remove(struct toptree * cand)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 */
toptree_free(struct toptree * cand)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 */
toptree_update_mask(struct toptree * cand)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 */
toptree_insert(struct toptree * cand,struct toptree * target)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 */
toptree_move_children(struct toptree * cand,struct toptree * target)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 */
toptree_unify(struct toptree * cand)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 */
toptree_move(struct toptree * cand,struct toptree * target)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 */
toptree_get_child(struct toptree * cand,int id)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 */
toptree_first(struct toptree * context,int level)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 */
toptree_next_sibling(struct toptree * cur)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 */
toptree_next(struct toptree * cur,struct toptree * context,int level)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 */
toptree_count(struct toptree * context,int level)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 }
343