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 }