Quelle  cpumap.c   Sprache: C

// SPDX-License-Identifier: GPL-2.0
/* cpumap.c: used for optimizing CPU assignment
 *
 * Copyright (C) 2009 Hong H. Pham <hong.pham@windriver.com>
 */

#include <linux/export.h>
#include <linux/slab.h>
#include <linux/kernel.h>
#include <linux/cpumask.h>
#include <linux/spinlock.h>
#include <asm/cpudata.h>
#include "cpumap.h"


enum {
 CPUINFO_LVL_ROOT = 0,
 CPUINFO_LVL_NODE,
 CPUINFO_LVL_CORE,
 CPUINFO_LVL_PROC,
 CPUINFO_LVL_MAX,
};

enum {
 ROVER_NO_OP              = 0,
 /* Increment rover every time level is visited */
 ROVER_INC_ON_VISIT       = 1 << 0,
 /* Increment parent's rover every time rover wraps around */
 ROVER_INC_PARENT_ON_LOOP = 1 << 1,
};

struct cpuinfo_node {
 int id;
 int level;
 int num_cpus;    /* Number of CPUs in this hierarchy */
 int parent_index;
 int child_start; /* Array index of the first child node */
 int child_end;   /* Array index of the last child node */
 int rover;       /* Child node iterator */
};

struct cpuinfo_level {
 int start_index; /* Index of first node of a level in a cpuinfo tree */
 int end_index;   /* Index of last node of a level in a cpuinfo tree */
 int num_nodes;   /* Number of nodes in a level in a cpuinfo tree */
};

struct cpuinfo_tree {
 int total_nodes;

 /* Offsets into nodes[] for each level of the tree */
 struct cpuinfo_level level[CPUINFO_LVL_MAX];
 struct cpuinfo_node  nodes[] __counted_by(total_nodes);
};


static struct cpuinfo_tree *cpuinfo_tree;

static u16 cpu_distribution_map[NR_CPUS];
static DEFINE_SPINLOCK(cpu_map_lock);


/* Niagara optimized cpuinfo tree traversal. */
static const int niagara_iterate_method[] = {
 [CPUINFO_LVL_ROOT] = ROVER_NO_OP,

 /* Strands (or virtual CPUs) within a core may not run concurrently
 * on the Niagara, as instruction pipeline(s) are shared.  Distribute
 * work to strands in different cores first for better concurrency.
 * Go to next NUMA node when all cores are used.
 */
 [CPUINFO_LVL_NODE] = ROVER_INC_ON_VISIT|ROVER_INC_PARENT_ON_LOOP,

 /* Strands are grouped together by proc_id in cpuinfo_sparc, i.e.
 * a proc_id represents an instruction pipeline.  Distribute work to
 * strands in different proc_id groups if the core has multiple
 * instruction pipelines (e.g. the Niagara 2/2+ has two).
 */
 [CPUINFO_LVL_CORE] = ROVER_INC_ON_VISIT,

 /* Pick the next strand in the proc_id group. */
 [CPUINFO_LVL_PROC] = ROVER_INC_ON_VISIT,
};

/* Generic cpuinfo tree traversal.  Distribute work round robin across NUMA
 * nodes.
 */
static const int generic_iterate_method[] = {
 [CPUINFO_LVL_ROOT] = ROVER_INC_ON_VISIT,
 [CPUINFO_LVL_NODE] = ROVER_NO_OP,
 [CPUINFO_LVL_CORE] = ROVER_INC_PARENT_ON_LOOP,
 [CPUINFO_LVL_PROC] = ROVER_INC_ON_VISIT|ROVER_INC_PARENT_ON_LOOP,
};


static int cpuinfo_id(int cpu, int level)
{
 int id;

 switch (level) {
 case CPUINFO_LVL_ROOT:
  id = 0;
  break;
 case CPUINFO_LVL_NODE:
  id = cpu_to_node(cpu);
  break;
 case CPUINFO_LVL_CORE:
  id = cpu_data(cpu).core_id;
  break;
 case CPUINFO_LVL_PROC:
  id = cpu_data(cpu).proc_id;
  break;
 default:
  id = -EINVAL;
 }
 return id;
}

/*
 * Enumerate the CPU information in __cpu_data to determine the start index,
 * end index, and number of nodes for each level in the cpuinfo tree.  The
 * total number of cpuinfo nodes required to build the tree is returned.
 */
static int enumerate_cpuinfo_nodes(struct cpuinfo_level *tree_level)
{
 int prev_id[CPUINFO_LVL_MAX];
 int i, n, num_nodes;

 for (i = CPUINFO_LVL_ROOT; i < CPUINFO_LVL_MAX; i++) {
  struct cpuinfo_level *lv = &tree_level[i];

  prev_id[i] = -1;
  lv->start_index = lv->end_index = lv->num_nodes = 0;
 }

 num_nodes = 1; /* Include the root node */

 for (i = 0; i < num_possible_cpus(); i++) {
  if (!cpu_online(i))
   continue;

  n = cpuinfo_id(i, CPUINFO_LVL_NODE);
  if (n > prev_id[CPUINFO_LVL_NODE]) {
   tree_level[CPUINFO_LVL_NODE].num_nodes++;
   prev_id[CPUINFO_LVL_NODE] = n;
   num_nodes++;
  }
  n = cpuinfo_id(i, CPUINFO_LVL_CORE);
  if (n > prev_id[CPUINFO_LVL_CORE]) {
   tree_level[CPUINFO_LVL_CORE].num_nodes++;
   prev_id[CPUINFO_LVL_CORE] = n;
   num_nodes++;
  }
  n = cpuinfo_id(i, CPUINFO_LVL_PROC);
  if (n > prev_id[CPUINFO_LVL_PROC]) {
   tree_level[CPUINFO_LVL_PROC].num_nodes++;
   prev_id[CPUINFO_LVL_PROC] = n;
   num_nodes++;
  }
 }

 tree_level[CPUINFO_LVL_ROOT].num_nodes = 1;

 n = tree_level[CPUINFO_LVL_NODE].num_nodes;
 tree_level[CPUINFO_LVL_NODE].start_index = 1;
 tree_level[CPUINFO_LVL_NODE].end_index   = n;

 n++;
 tree_level[CPUINFO_LVL_CORE].start_index = n;
 n += tree_level[CPUINFO_LVL_CORE].num_nodes;
 tree_level[CPUINFO_LVL_CORE].end_index   = n - 1;

 tree_level[CPUINFO_LVL_PROC].start_index = n;
 n += tree_level[CPUINFO_LVL_PROC].num_nodes;
 tree_level[CPUINFO_LVL_PROC].end_index   = n - 1;

 return num_nodes;
}

/* Build a tree representation of the CPU hierarchy using the per CPU
 * information in __cpu_data.  Entries in __cpu_data[0..NR_CPUS] are
 * assumed to be sorted in ascending order based on node, core_id, and
 * proc_id (in order of significance).
 */
static struct cpuinfo_tree *build_cpuinfo_tree(void)
{
 struct cpuinfo_tree *new_tree;
 struct cpuinfo_node *node;
 struct cpuinfo_level tmp_level[CPUINFO_LVL_MAX];
 int num_cpus[CPUINFO_LVL_MAX];
 int level_rover[CPUINFO_LVL_MAX];
 int prev_id[CPUINFO_LVL_MAX];
 int n, id, cpu, prev_cpu, last_cpu, level;

 n = enumerate_cpuinfo_nodes(tmp_level);

 new_tree = kzalloc(struct_size(new_tree, nodes, n), GFP_ATOMIC);
 if (!new_tree)
  return NULL;

 new_tree->total_nodes = n;
 memcpy(&new_tree->level, tmp_level, sizeof(tmp_level));

 prev_cpu = cpu = cpumask_first(cpu_online_mask);

 /* Initialize all levels in the tree with the first CPU */
 for (level = CPUINFO_LVL_PROC; level >= CPUINFO_LVL_ROOT; level--) {
  n = new_tree->level[level].start_index;

  level_rover[level] = n;
  node = &new_tree->nodes[n];

  id = cpuinfo_id(cpu, level);
  if (unlikely(id < 0)) {
   kfree(new_tree);
   return NULL;
  }
  node->id = id;
  node->level = level;
  node->num_cpus = 1;

  node->parent_index = (level > CPUINFO_LVL_ROOT)
      ? new_tree->level[level - 1].start_index : -1;

  node->child_start = node->child_end = node->rover =
      (level == CPUINFO_LVL_PROC)
      ? cpu : new_tree->level[level + 1].start_index;

  prev_id[level] = node->id;
  num_cpus[level] = 1;
 }

 for (last_cpu = (num_possible_cpus() - 1); last_cpu >= 0; last_cpu--) {
  if (cpu_online(last_cpu))
   break;
 }

 while (++cpu <= last_cpu) {
  if (!cpu_online(cpu))
   continue;

  for (level = CPUINFO_LVL_PROC; level >= CPUINFO_LVL_ROOT;
       level--) {
   id = cpuinfo_id(cpu, level);
   if (unlikely(id < 0)) {
    kfree(new_tree);
    return NULL;
   }

   if ((id != prev_id[level]) || (cpu == last_cpu)) {
    prev_id[level] = id;
    node = &new_tree->nodes[level_rover[level]];
    node->num_cpus = num_cpus[level];
    num_cpus[level] = 1;

    if (cpu == last_cpu)
     node->num_cpus++;

    /* Connect tree node to parent */
    if (level == CPUINFO_LVL_ROOT)
     node->parent_index = -1;
    else
     node->parent_index =
         level_rover[level - 1];

    if (level == CPUINFO_LVL_PROC) {
     node->child_end =
         (cpu == last_cpu) ? cpu : prev_cpu;
    } else {
     node->child_end =
         level_rover[level + 1] - 1;
    }

    /* Initialize the next node in the same level */
    n = ++level_rover[level];
    if (n <= new_tree->level[level].end_index) {
     node = &new_tree->nodes[n];
     node->id = id;
     node->level = level;

     /* Connect node to child */
     node->child_start = node->child_end =
     node->rover =
         (level == CPUINFO_LVL_PROC)
         ? cpu : level_rover[level + 1];
    }
   } else
    num_cpus[level]++;
  }
  prev_cpu = cpu;
 }

 return new_tree;
}

static void increment_rover(struct cpuinfo_tree *t, int node_index,
                            int root_index, const int *rover_inc_table)
{
 struct cpuinfo_node *node = &t->nodes[node_index];
 int top_level, level;

 top_level = t->nodes[root_index].level;
 for (level = node->level; level >= top_level; level--) {
  node->rover++;
  if (node->rover <= node->child_end)
   return;

  node->rover = node->child_start;
  /* If parent's rover does not need to be adjusted, stop here. */
  if ((level == top_level) ||
      !(rover_inc_table[level] & ROVER_INC_PARENT_ON_LOOP))
   return;

  node = &t->nodes[node->parent_index];
 }
}

static int iterate_cpu(struct cpuinfo_tree *t, unsigned int root_index)
{
 const int *rover_inc_table;
 int level, new_index, index = root_index;

 switch (sun4v_chip_type) {
 case SUN4V_CHIP_NIAGARA1:
 case SUN4V_CHIP_NIAGARA2:
 case SUN4V_CHIP_NIAGARA3:
 case SUN4V_CHIP_NIAGARA4:
 case SUN4V_CHIP_NIAGARA5:
 case SUN4V_CHIP_SPARC_M6:
 case SUN4V_CHIP_SPARC_M7:
 case SUN4V_CHIP_SPARC_M8:
 case SUN4V_CHIP_SPARC_SN:
 case SUN4V_CHIP_SPARC64X:
  rover_inc_table = niagara_iterate_method;
  break;
 default:
  rover_inc_table = generic_iterate_method;
 }

 for (level = t->nodes[root_index].level; level < CPUINFO_LVL_MAX;
      level++) {
  new_index = t->nodes[index].rover;
  if (rover_inc_table[level] & ROVER_INC_ON_VISIT)
   increment_rover(t, index, root_index, rover_inc_table);

  index = new_index;
 }
 return index;
}

static void _cpu_map_rebuild(void)
{
 int i;

 if (cpuinfo_tree) {
  kfree(cpuinfo_tree);
  cpuinfo_tree = NULL;
 }

 cpuinfo_tree = build_cpuinfo_tree();
 if (!cpuinfo_tree)
  return;

 /* Build CPU distribution map that spans all online CPUs.  No need
 * to check if the CPU is online, as that is done when the cpuinfo
 * tree is being built.
 */
 for (i = 0; i < cpuinfo_tree->nodes[0].num_cpus; i++)
  cpu_distribution_map[i] = iterate_cpu(cpuinfo_tree, 0);
}

/* Fallback if the cpuinfo tree could not be built.  CPU mapping is linear
 * round robin.
 */
static int simple_map_to_cpu(unsigned int index)
{
 int i, end, cpu_rover;

 cpu_rover = 0;
 end = index % num_online_cpus();
 for (i = 0; i < num_possible_cpus(); i++) {
  if (cpu_online(cpu_rover)) {
   if (cpu_rover >= end)
    return cpu_rover;

   cpu_rover++;
  }
 }

 /* Impossible, since num_online_cpus() <= num_possible_cpus() */
 return cpumask_first(cpu_online_mask);
}

static int _map_to_cpu(unsigned int index)
{
 struct cpuinfo_node *root_node;

 if (unlikely(!cpuinfo_tree)) {
  _cpu_map_rebuild();
  if (!cpuinfo_tree)
   return simple_map_to_cpu(index);
 }

 root_node = &cpuinfo_tree->nodes[0];
#ifdef CONFIG_HOTPLUG_CPU
 if (unlikely(root_node->num_cpus != num_online_cpus())) {
  _cpu_map_rebuild();
  if (!cpuinfo_tree)
   return simple_map_to_cpu(index);
 }
#endif
 return cpu_distribution_map[index % root_node->num_cpus];
}

int map_to_cpu(unsigned int index)
{
 int mapped_cpu;
 unsigned long flag;

 spin_lock_irqsave(&cpu_map_lock, flag);
 mapped_cpu = _map_to_cpu(index);

#ifdef CONFIG_HOTPLUG_CPU
 while (unlikely(!cpu_online(mapped_cpu)))
  mapped_cpu = _map_to_cpu(index);
#endif
 spin_unlock_irqrestore(&cpu_map_lock, flag);
 return mapped_cpu;
}
EXPORT_SYMBOL(map_to_cpu);

void cpu_map_rebuild(void)
{
 unsigned long flag;

 spin_lock_irqsave(&cpu_map_lock, flag);
 _cpu_map_rebuild();
 spin_unlock_irqrestore(&cpu_map_lock, flag);
}