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 */
 30struct 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 */
 56static 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 */
 74void __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 */
100void 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 */
122static 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 */
141static 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 */
157void 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 */
198void 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 */
236struct 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 */
257struct 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 */
282static 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 */
304struct 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 */
343int 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}