arch/s390/numa/toptree.c

   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  */
  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  */
  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  */
  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  */
 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 }