cpumap.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439
  1. // SPDX-License-Identifier: GPL-2.0
  2. /* cpumap.c: used for optimizing CPU assignment
  3. *
  4. * Copyright (C) 2009 Hong H. Pham <[email protected]>
  5. */
  6. #include <linux/export.h>
  7. #include <linux/slab.h>
  8. #include <linux/kernel.h>
  9. #include <linux/cpumask.h>
  10. #include <linux/spinlock.h>
  11. #include <asm/cpudata.h>
  12. #include "cpumap.h"
  13. enum {
  14. CPUINFO_LVL_ROOT = 0,
  15. CPUINFO_LVL_NODE,
  16. CPUINFO_LVL_CORE,
  17. CPUINFO_LVL_PROC,
  18. CPUINFO_LVL_MAX,
  19. };
  20. enum {
  21. ROVER_NO_OP = 0,
  22. /* Increment rover every time level is visited */
  23. ROVER_INC_ON_VISIT = 1 << 0,
  24. /* Increment parent's rover every time rover wraps around */
  25. ROVER_INC_PARENT_ON_LOOP = 1 << 1,
  26. };
  27. struct cpuinfo_node {
  28. int id;
  29. int level;
  30. int num_cpus; /* Number of CPUs in this hierarchy */
  31. int parent_index;
  32. int child_start; /* Array index of the first child node */
  33. int child_end; /* Array index of the last child node */
  34. int rover; /* Child node iterator */
  35. };
  36. struct cpuinfo_level {
  37. int start_index; /* Index of first node of a level in a cpuinfo tree */
  38. int end_index; /* Index of last node of a level in a cpuinfo tree */
  39. int num_nodes; /* Number of nodes in a level in a cpuinfo tree */
  40. };
  41. struct cpuinfo_tree {
  42. int total_nodes;
  43. /* Offsets into nodes[] for each level of the tree */
  44. struct cpuinfo_level level[CPUINFO_LVL_MAX];
  45. struct cpuinfo_node nodes[];
  46. };
  47. static struct cpuinfo_tree *cpuinfo_tree;
  48. static u16 cpu_distribution_map[NR_CPUS];
  49. static DEFINE_SPINLOCK(cpu_map_lock);
  50. /* Niagara optimized cpuinfo tree traversal. */
  51. static const int niagara_iterate_method[] = {
  52. [CPUINFO_LVL_ROOT] = ROVER_NO_OP,
  53. /* Strands (or virtual CPUs) within a core may not run concurrently
  54. * on the Niagara, as instruction pipeline(s) are shared. Distribute
  55. * work to strands in different cores first for better concurrency.
  56. * Go to next NUMA node when all cores are used.
  57. */
  58. [CPUINFO_LVL_NODE] = ROVER_INC_ON_VISIT|ROVER_INC_PARENT_ON_LOOP,
  59. /* Strands are grouped together by proc_id in cpuinfo_sparc, i.e.
  60. * a proc_id represents an instruction pipeline. Distribute work to
  61. * strands in different proc_id groups if the core has multiple
  62. * instruction pipelines (e.g. the Niagara 2/2+ has two).
  63. */
  64. [CPUINFO_LVL_CORE] = ROVER_INC_ON_VISIT,
  65. /* Pick the next strand in the proc_id group. */
  66. [CPUINFO_LVL_PROC] = ROVER_INC_ON_VISIT,
  67. };
  68. /* Generic cpuinfo tree traversal. Distribute work round robin across NUMA
  69. * nodes.
  70. */
  71. static const int generic_iterate_method[] = {
  72. [CPUINFO_LVL_ROOT] = ROVER_INC_ON_VISIT,
  73. [CPUINFO_LVL_NODE] = ROVER_NO_OP,
  74. [CPUINFO_LVL_CORE] = ROVER_INC_PARENT_ON_LOOP,
  75. [CPUINFO_LVL_PROC] = ROVER_INC_ON_VISIT|ROVER_INC_PARENT_ON_LOOP,
  76. };
  77. static int cpuinfo_id(int cpu, int level)
  78. {
  79. int id;
  80. switch (level) {
  81. case CPUINFO_LVL_ROOT:
  82. id = 0;
  83. break;
  84. case CPUINFO_LVL_NODE:
  85. id = cpu_to_node(cpu);
  86. break;
  87. case CPUINFO_LVL_CORE:
  88. id = cpu_data(cpu).core_id;
  89. break;
  90. case CPUINFO_LVL_PROC:
  91. id = cpu_data(cpu).proc_id;
  92. break;
  93. default:
  94. id = -EINVAL;
  95. }
  96. return id;
  97. }
  98. /*
  99. * Enumerate the CPU information in __cpu_data to determine the start index,
  100. * end index, and number of nodes for each level in the cpuinfo tree. The
  101. * total number of cpuinfo nodes required to build the tree is returned.
  102. */
  103. static int enumerate_cpuinfo_nodes(struct cpuinfo_level *tree_level)
  104. {
  105. int prev_id[CPUINFO_LVL_MAX];
  106. int i, n, num_nodes;
  107. for (i = CPUINFO_LVL_ROOT; i < CPUINFO_LVL_MAX; i++) {
  108. struct cpuinfo_level *lv = &tree_level[i];
  109. prev_id[i] = -1;
  110. lv->start_index = lv->end_index = lv->num_nodes = 0;
  111. }
  112. num_nodes = 1; /* Include the root node */
  113. for (i = 0; i < num_possible_cpus(); i++) {
  114. if (!cpu_online(i))
  115. continue;
  116. n = cpuinfo_id(i, CPUINFO_LVL_NODE);
  117. if (n > prev_id[CPUINFO_LVL_NODE]) {
  118. tree_level[CPUINFO_LVL_NODE].num_nodes++;
  119. prev_id[CPUINFO_LVL_NODE] = n;
  120. num_nodes++;
  121. }
  122. n = cpuinfo_id(i, CPUINFO_LVL_CORE);
  123. if (n > prev_id[CPUINFO_LVL_CORE]) {
  124. tree_level[CPUINFO_LVL_CORE].num_nodes++;
  125. prev_id[CPUINFO_LVL_CORE] = n;
  126. num_nodes++;
  127. }
  128. n = cpuinfo_id(i, CPUINFO_LVL_PROC);
  129. if (n > prev_id[CPUINFO_LVL_PROC]) {
  130. tree_level[CPUINFO_LVL_PROC].num_nodes++;
  131. prev_id[CPUINFO_LVL_PROC] = n;
  132. num_nodes++;
  133. }
  134. }
  135. tree_level[CPUINFO_LVL_ROOT].num_nodes = 1;
  136. n = tree_level[CPUINFO_LVL_NODE].num_nodes;
  137. tree_level[CPUINFO_LVL_NODE].start_index = 1;
  138. tree_level[CPUINFO_LVL_NODE].end_index = n;
  139. n++;
  140. tree_level[CPUINFO_LVL_CORE].start_index = n;
  141. n += tree_level[CPUINFO_LVL_CORE].num_nodes;
  142. tree_level[CPUINFO_LVL_CORE].end_index = n - 1;
  143. tree_level[CPUINFO_LVL_PROC].start_index = n;
  144. n += tree_level[CPUINFO_LVL_PROC].num_nodes;
  145. tree_level[CPUINFO_LVL_PROC].end_index = n - 1;
  146. return num_nodes;
  147. }
  148. /* Build a tree representation of the CPU hierarchy using the per CPU
  149. * information in __cpu_data. Entries in __cpu_data[0..NR_CPUS] are
  150. * assumed to be sorted in ascending order based on node, core_id, and
  151. * proc_id (in order of significance).
  152. */
  153. static struct cpuinfo_tree *build_cpuinfo_tree(void)
  154. {
  155. struct cpuinfo_tree *new_tree;
  156. struct cpuinfo_node *node;
  157. struct cpuinfo_level tmp_level[CPUINFO_LVL_MAX];
  158. int num_cpus[CPUINFO_LVL_MAX];
  159. int level_rover[CPUINFO_LVL_MAX];
  160. int prev_id[CPUINFO_LVL_MAX];
  161. int n, id, cpu, prev_cpu, last_cpu, level;
  162. n = enumerate_cpuinfo_nodes(tmp_level);
  163. new_tree = kzalloc(struct_size(new_tree, nodes, n), GFP_ATOMIC);
  164. if (!new_tree)
  165. return NULL;
  166. new_tree->total_nodes = n;
  167. memcpy(&new_tree->level, tmp_level, sizeof(tmp_level));
  168. prev_cpu = cpu = cpumask_first(cpu_online_mask);
  169. /* Initialize all levels in the tree with the first CPU */
  170. for (level = CPUINFO_LVL_PROC; level >= CPUINFO_LVL_ROOT; level--) {
  171. n = new_tree->level[level].start_index;
  172. level_rover[level] = n;
  173. node = &new_tree->nodes[n];
  174. id = cpuinfo_id(cpu, level);
  175. if (unlikely(id < 0)) {
  176. kfree(new_tree);
  177. return NULL;
  178. }
  179. node->id = id;
  180. node->level = level;
  181. node->num_cpus = 1;
  182. node->parent_index = (level > CPUINFO_LVL_ROOT)
  183. ? new_tree->level[level - 1].start_index : -1;
  184. node->child_start = node->child_end = node->rover =
  185. (level == CPUINFO_LVL_PROC)
  186. ? cpu : new_tree->level[level + 1].start_index;
  187. prev_id[level] = node->id;
  188. num_cpus[level] = 1;
  189. }
  190. for (last_cpu = (num_possible_cpus() - 1); last_cpu >= 0; last_cpu--) {
  191. if (cpu_online(last_cpu))
  192. break;
  193. }
  194. while (++cpu <= last_cpu) {
  195. if (!cpu_online(cpu))
  196. continue;
  197. for (level = CPUINFO_LVL_PROC; level >= CPUINFO_LVL_ROOT;
  198. level--) {
  199. id = cpuinfo_id(cpu, level);
  200. if (unlikely(id < 0)) {
  201. kfree(new_tree);
  202. return NULL;
  203. }
  204. if ((id != prev_id[level]) || (cpu == last_cpu)) {
  205. prev_id[level] = id;
  206. node = &new_tree->nodes[level_rover[level]];
  207. node->num_cpus = num_cpus[level];
  208. num_cpus[level] = 1;
  209. if (cpu == last_cpu)
  210. node->num_cpus++;
  211. /* Connect tree node to parent */
  212. if (level == CPUINFO_LVL_ROOT)
  213. node->parent_index = -1;
  214. else
  215. node->parent_index =
  216. level_rover[level - 1];
  217. if (level == CPUINFO_LVL_PROC) {
  218. node->child_end =
  219. (cpu == last_cpu) ? cpu : prev_cpu;
  220. } else {
  221. node->child_end =
  222. level_rover[level + 1] - 1;
  223. }
  224. /* Initialize the next node in the same level */
  225. n = ++level_rover[level];
  226. if (n <= new_tree->level[level].end_index) {
  227. node = &new_tree->nodes[n];
  228. node->id = id;
  229. node->level = level;
  230. /* Connect node to child */
  231. node->child_start = node->child_end =
  232. node->rover =
  233. (level == CPUINFO_LVL_PROC)
  234. ? cpu : level_rover[level + 1];
  235. }
  236. } else
  237. num_cpus[level]++;
  238. }
  239. prev_cpu = cpu;
  240. }
  241. return new_tree;
  242. }
  243. static void increment_rover(struct cpuinfo_tree *t, int node_index,
  244. int root_index, const int *rover_inc_table)
  245. {
  246. struct cpuinfo_node *node = &t->nodes[node_index];
  247. int top_level, level;
  248. top_level = t->nodes[root_index].level;
  249. for (level = node->level; level >= top_level; level--) {
  250. node->rover++;
  251. if (node->rover <= node->child_end)
  252. return;
  253. node->rover = node->child_start;
  254. /* If parent's rover does not need to be adjusted, stop here. */
  255. if ((level == top_level) ||
  256. !(rover_inc_table[level] & ROVER_INC_PARENT_ON_LOOP))
  257. return;
  258. node = &t->nodes[node->parent_index];
  259. }
  260. }
  261. static int iterate_cpu(struct cpuinfo_tree *t, unsigned int root_index)
  262. {
  263. const int *rover_inc_table;
  264. int level, new_index, index = root_index;
  265. switch (sun4v_chip_type) {
  266. case SUN4V_CHIP_NIAGARA1:
  267. case SUN4V_CHIP_NIAGARA2:
  268. case SUN4V_CHIP_NIAGARA3:
  269. case SUN4V_CHIP_NIAGARA4:
  270. case SUN4V_CHIP_NIAGARA5:
  271. case SUN4V_CHIP_SPARC_M6:
  272. case SUN4V_CHIP_SPARC_M7:
  273. case SUN4V_CHIP_SPARC_M8:
  274. case SUN4V_CHIP_SPARC_SN:
  275. case SUN4V_CHIP_SPARC64X:
  276. rover_inc_table = niagara_iterate_method;
  277. break;
  278. default:
  279. rover_inc_table = generic_iterate_method;
  280. }
  281. for (level = t->nodes[root_index].level; level < CPUINFO_LVL_MAX;
  282. level++) {
  283. new_index = t->nodes[index].rover;
  284. if (rover_inc_table[level] & ROVER_INC_ON_VISIT)
  285. increment_rover(t, index, root_index, rover_inc_table);
  286. index = new_index;
  287. }
  288. return index;
  289. }
  290. static void _cpu_map_rebuild(void)
  291. {
  292. int i;
  293. if (cpuinfo_tree) {
  294. kfree(cpuinfo_tree);
  295. cpuinfo_tree = NULL;
  296. }
  297. cpuinfo_tree = build_cpuinfo_tree();
  298. if (!cpuinfo_tree)
  299. return;
  300. /* Build CPU distribution map that spans all online CPUs. No need
  301. * to check if the CPU is online, as that is done when the cpuinfo
  302. * tree is being built.
  303. */
  304. for (i = 0; i < cpuinfo_tree->nodes[0].num_cpus; i++)
  305. cpu_distribution_map[i] = iterate_cpu(cpuinfo_tree, 0);
  306. }
  307. /* Fallback if the cpuinfo tree could not be built. CPU mapping is linear
  308. * round robin.
  309. */
  310. static int simple_map_to_cpu(unsigned int index)
  311. {
  312. int i, end, cpu_rover;
  313. cpu_rover = 0;
  314. end = index % num_online_cpus();
  315. for (i = 0; i < num_possible_cpus(); i++) {
  316. if (cpu_online(cpu_rover)) {
  317. if (cpu_rover >= end)
  318. return cpu_rover;
  319. cpu_rover++;
  320. }
  321. }
  322. /* Impossible, since num_online_cpus() <= num_possible_cpus() */
  323. return cpumask_first(cpu_online_mask);
  324. }
  325. static int _map_to_cpu(unsigned int index)
  326. {
  327. struct cpuinfo_node *root_node;
  328. if (unlikely(!cpuinfo_tree)) {
  329. _cpu_map_rebuild();
  330. if (!cpuinfo_tree)
  331. return simple_map_to_cpu(index);
  332. }
  333. root_node = &cpuinfo_tree->nodes[0];
  334. #ifdef CONFIG_HOTPLUG_CPU
  335. if (unlikely(root_node->num_cpus != num_online_cpus())) {
  336. _cpu_map_rebuild();
  337. if (!cpuinfo_tree)
  338. return simple_map_to_cpu(index);
  339. }
  340. #endif
  341. return cpu_distribution_map[index % root_node->num_cpus];
  342. }
  343. int map_to_cpu(unsigned int index)
  344. {
  345. int mapped_cpu;
  346. unsigned long flag;
  347. spin_lock_irqsave(&cpu_map_lock, flag);
  348. mapped_cpu = _map_to_cpu(index);
  349. #ifdef CONFIG_HOTPLUG_CPU
  350. while (unlikely(!cpu_online(mapped_cpu)))
  351. mapped_cpu = _map_to_cpu(index);
  352. #endif
  353. spin_unlock_irqrestore(&cpu_map_lock, flag);
  354. return mapped_cpu;
  355. }
  356. EXPORT_SYMBOL(map_to_cpu);
  357. void cpu_map_rebuild(void)
  358. {
  359. unsigned long flag;
  360. spin_lock_irqsave(&cpu_map_lock, flag);
  361. _cpu_map_rebuild();
  362. spin_unlock_irqrestore(&cpu_map_lock, flag);
  363. }