• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // SPDX-License-Identifier: GPL-2.0
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>
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  * 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  */
toptree_alloc(int level,int id)30 struct 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  * 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  */
toptree_remove(struct toptree * cand)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  */
toptree_free(struct toptree * cand)74 void __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  * 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  */
toptree_update_mask(struct toptree * cand)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  */
toptree_insert(struct toptree * cand,struct toptree * target)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  */
toptree_move_children(struct toptree * cand,struct toptree * target)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  */
toptree_unify(struct toptree * cand)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  */
toptree_move(struct toptree * cand,struct toptree * target)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  */
toptree_get_child(struct toptree * cand,int id)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  */
toptree_first(struct toptree * context,int level)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  */
toptree_next_sibling(struct toptree * cur)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  */
toptree_next(struct toptree * cur,struct toptree * context,int level)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  */
toptree_count(struct toptree * context,int level)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 }
352