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