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/bootmem.h>
  11 #include <linux/cpumask.h>
  12 #include <linux/list.h>
  13 #include <linux/list_sort.h>
  14 #include <linux/slab.h>
  15 #include <asm/numa.h>
  16
  17 #include "toptree.h"
  18
  19 /**
  20  * toptree_alloc - Allocate and initialize a new tree node.
  21  * @level: The node's vertical level; level 0 contains the leaves.
  22  * @id: ID number, explicitly not unique beyond scope of node's siblings
  23  *
  24  * Allocate a new tree node and initialize it.
  25  *
  26  * RETURNS:
  27  * Pointer to the new tree node or NULL on error
  28  */
  29 struct toptree __ref *toptree_alloc(int level, int id)
  30 {
  31         struct toptree *res;
  32
  33         if (slab_is_available())
  34                 res = kzalloc(sizeof(*res), GFP_KERNEL);
  35         else
  36                 res = memblock_virt_alloc(sizeof(*res), 8);
  37         if (!res)
  38                 return res;
  39
  40         INIT_LIST_HEAD(&res->children);
  41         INIT_LIST_HEAD(&res->sibling);
  42         cpumask_clear(&res->mask);
  43         res->level = level;
  44         res->id = id;
  45         return res;
  46 }
  47
  48 /**
  49  * toptree_remove - Remove a tree node from a tree
  50  * @cand: Pointer to the node to remove
  51  *
  52  * The node is detached from its parent node. The parent node's
  53  * masks will be updated to reflect the loss of the child.
  54  */
  55 static void toptree_remove(struct toptree *cand)
  56 {
  57         struct toptree *oldparent;
  58
  59         list_del_init(&cand->sibling);
  60         oldparent = cand->parent;
  61         cand->parent = NULL;
  62         toptree_update_mask(oldparent);
  63 }
  64
  65 /**
  66  * toptree_free - discard a tree node
  67  * @cand: Pointer to the tree node to discard
  68  *
  69  * Checks if @cand is attached to a parent node. Detaches it
  70  * cleanly using toptree_remove. Possible children are freed
  71  * recursively. In the end @cand itself is freed.
  72  */
  73 void __ref toptree_free(struct toptree *cand)
  74 {
  75         struct toptree *child, *tmp;
  76
  77         if (cand->parent)
  78                 toptree_remove(cand);
  79         toptree_for_each_child_safe(child, tmp, cand)
  80                 toptree_free(child);
  81         if (slab_is_available())
  82                 kfree(cand);
  83         else
  84                 memblock_free_early((unsigned long)cand, sizeof(*cand));
  85 }
  86
  87 /**
  88  * toptree_update_mask - Update node bitmasks
  89  * @cand: Pointer to a tree node
  90  *
  91  * The node's cpumask will be updated by combining all children's
  92  * masks. Then toptree_update_mask is called recursively for the
  93  * parent if applicable.
  94  *
  95  * NOTE:
  96  * This must not be called on leaves. If called on a leaf, its
  97  * CPU mask is cleared and lost.
  98  */
  99 void toptree_update_mask(struct toptree *cand)
 100 {
 101         struct toptree *child;
 102
 103         cpumask_clear(&cand->mask);
 104         list_for_each_entry(child, &cand->children, sibling)
 105                 cpumask_or(&cand->mask, &cand->mask, &child->mask);
 106         if (cand->parent)
 107                 toptree_update_mask(cand->parent);
 108 }
 109
 110 /**
 111  * toptree_insert - Insert a tree node into tree
 112  * @cand: Pointer to the node to insert
 113  * @target: Pointer to the node to which @cand will added as a child
 114  *
 115  * Insert a tree node into a tree. Masks will be updated automatically.
 116  *
 117  * RETURNS:
 118  * 0 on success, -1 if NULL is passed as argument or the node levels
 119  * don't fit.
 120  */
 121 static int toptree_insert(struct toptree *cand, struct toptree *target)
 122 {
 123         if (!cand || !target)
 124                 return -1;
 125         if (target->level != (cand->level + 1))
 126                 return -1;
 127         list_add_tail(&cand->sibling, &target->children);
 128         cand->parent = target;
 129         toptree_update_mask(target);
 130         return 0;
 131 }
 132
 133 /**
 134  * toptree_move_children - Move all child nodes of a node to a new place
 135  * @cand: Pointer to the node whose children are to be moved
 136  * @target: Pointer to the node to which @cand's children will be attached
 137  *
 138  * Take all child nodes of @cand and move them using toptree_move.
 139  */
 140 static void toptree_move_children(struct toptree *cand, struct toptree *target)
 141 {
 142         struct toptree *child, *tmp;
 143
 144         toptree_for_each_child_safe(child, tmp, cand)
 145                 toptree_move(child, target);
 146 }
 147
 148 /**
 149  * toptree_unify - Merge children with same ID
 150  * @cand: Pointer to node whose direct children should be made unique
 151  *
 152  * When mangling the tree it is possible that a node has two or more children
 153  * which have the same ID. This routine merges these children into one and
 154  * moves all children of the merged nodes into the unified node.
 155  */
 156 void toptree_unify(struct toptree *cand)
 157 {
 158         struct toptree *child, *tmp, *cand_copy;
 159
 160         /* Threads cannot be split, cores are not split */
 161         if (cand->level < 2)
 162                 return;
 163
 164         cand_copy = toptree_alloc(cand->level, 0);
 165         toptree_for_each_child_safe(child, tmp, cand) {
 166                 struct toptree *tmpchild;
 167
 168                 if (!cpumask_empty(&child->mask)) {
 169                         tmpchild = toptree_get_child(cand_copy, child->id);
 170                         toptree_move_children(child, tmpchild);
 171                 }
 172                 toptree_free(child);
 173         }
 174         toptree_move_children(cand_copy, cand);
 175         toptree_free(cand_copy);
 176
 177         toptree_for_each_child(child, cand)
 178                 toptree_unify(child);
 179 }
 180
 181 /**
 182  * toptree_move - Move a node to another context
 183  * @cand: Pointer to the node to move
 184  * @target: Pointer to the node where @cand should go
 185  *
 186  * In the easiest case @cand is exactly on the level below @target
 187  * and will be immediately moved to the target.
 188  *
 189  * If @target's level is not the direct parent level of @cand,
 190  * nodes for the missing levels are created and put between
 191  * @cand and @target. The "stacking" nodes' IDs are taken from
 192  * @cand's parents.
 193  *
 194  * After this it is likely to have redundant nodes in the tree
 195  * which are addressed by means of toptree_unify.
 196  */
 197 void toptree_move(struct toptree *cand, struct toptree *target)
 198 {
 199         struct toptree *stack_target, *real_insert_point, *ptr, *tmp;
 200
 201         if (cand->level + 1 == target->level) {
 202                 toptree_remove(cand);
 203                 toptree_insert(cand, target);
 204                 return;
 205         }
 206
 207         real_insert_point = NULL;
 208         ptr = cand;
 209         stack_target = NULL;
 210
 211         do {
 212                 tmp = stack_target;
 213                 stack_target = toptree_alloc(ptr->level + 1,
 214                                              ptr->parent->id);
 215                 toptree_insert(tmp, stack_target);
 216                 if (!real_insert_point)
 217                         real_insert_point = stack_target;
 218                 ptr = ptr->parent;
 219         } while (stack_target->level < (target->level - 1));
 220
 221         toptree_remove(cand);
 222         toptree_insert(cand, real_insert_point);
 223         toptree_insert(stack_target, target);
 224 }
 225
 226 /**
 227  * toptree_get_child - Access a tree node's child by its ID
 228  * @cand: Pointer to tree node whose child is to access
 229  * @id: The desired child's ID
 230  *
 231  * @cand's children are searched for a child with matching ID.
 232  * If no match can be found, a new child with the desired ID
 233  * is created and returned.
 234  */
 235 struct toptree *toptree_get_child(struct toptree *cand, int id)
 236 {
 237         struct toptree *child;
 238
 239         toptree_for_each_child(child, cand)
 240                 if (child->id == id)
 241                         return child;
 242         child = toptree_alloc(cand->level-1, id);
 243         toptree_insert(child, cand);
 244         return child;
 245 }
 246
 247 /**
 248  * toptree_first - Find the first descendant on specified level
 249  * @context: Pointer to tree node whose descendants are to be used
 250  * @level: The level of interest
 251  *
 252  * RETURNS:
 253  * @context's first descendant on the specified level, or NULL
 254  * if there is no matching descendant
 255  */
 256 struct toptree *toptree_first(struct toptree *context, int level)
 257 {
 258         struct toptree *child, *tmp;
 259
 260         if (context->level == level)
 261                 return context;
 262
 263         if (!list_empty(&context->children)) {
 264                 list_for_each_entry(child, &context->children, sibling) {
 265                         tmp = toptree_first(child, level);
 266                         if (tmp)
 267                                 return tmp;
 268                 }
 269         }
 270         return NULL;
 271 }
 272
 273 /**
 274  * toptree_next_sibling - Return next sibling
 275  * @cur: Pointer to a tree node
 276  *
 277  * RETURNS:
 278  * If @cur has a parent and is not the last in the parent's children list,
 279  * the next sibling is returned. Or NULL when there are no siblings left.
 280  */
 281 static struct toptree *toptree_next_sibling(struct toptree *cur)
 282 {
 283         if (cur->parent == NULL)
 284                 return NULL;
 285
 286         if (cur == list_last_entry(&cur->parent->children,
 287                                    struct toptree, sibling))
 288                 return NULL;
 289         return (struct toptree *) list_next_entry(cur, sibling);
 290 }
 291
 292 /**
 293  * toptree_next - Tree traversal function
 294  * @cur: Pointer to current element
 295  * @context: Pointer to the root node of the tree or subtree to
 296  * be traversed.
 297  * @level: The level of interest.
 298  *
 299  * RETURNS:
 300  * Pointer to the next node on level @level
 301  * or NULL when there is no next node.
 302  */
 303 struct toptree *toptree_next(struct toptree *cur, struct toptree *context,
 304                              int level)
 305 {
 306         struct toptree *cur_context, *tmp;
 307
 308         if (!cur)
 309                 return NULL;
 310
 311         if (context->level == level)
 312                 return NULL;
 313
 314         tmp = toptree_next_sibling(cur);
 315         if (tmp != NULL)
 316                 return tmp;
 317
 318         cur_context = cur;
 319         while (cur_context->level < context->level - 1) {
 320                 /* Step up */
 321                 cur_context = cur_context->parent;
 322                 /* Step aside */
 323                 tmp = toptree_next_sibling(cur_context);
 324                 if (tmp != NULL) {
 325                         /* Step down */
 326                         tmp = toptree_first(tmp, level);
 327                         if (tmp != NULL)
 328                                 return tmp;
 329                 }
 330         }
 331         return NULL;
 332 }
 333
 334 /**
 335  * toptree_count - Count descendants on specified level
 336  * @context: Pointer to node whose descendants are to be considered
 337  * @level: Only descendants on the specified level will be counted
 338  *
 339  * RETURNS:
 340  * Number of descendants on the specified level
 341  */
 342 int toptree_count(struct toptree *context, int level)
 343 {
 344         struct toptree *cur;
 345         int cnt = 0;
 346
 347         toptree_for_each(cur, context, level)
 348                 cnt++;
 349         return cnt;
 350 }