GNU Linux-libre 4.9.288-gnu1
[releases.git] / arch / s390 / numa / toptree.c
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 }