1 | // SPDX-License-Identifier: GPL-2.0 |
2 | // Copyright (C) 2017 Thomas Gleixner <tglx@linutronix.de> |
3 | |
4 | #include <linux/spinlock.h> |
5 | #include <linux/seq_file.h> |
6 | #include <linux/bitmap.h> |
7 | #include <linux/percpu.h> |
8 | #include <linux/cpu.h> |
9 | #include <linux/irq.h> |
10 | |
11 | struct cpumap { |
12 | unsigned int available; |
13 | unsigned int allocated; |
14 | unsigned int managed; |
15 | unsigned int managed_allocated; |
16 | bool initialized; |
17 | bool online; |
18 | unsigned long *managed_map; |
19 | unsigned long alloc_map[]; |
20 | }; |
21 | |
22 | struct irq_matrix { |
23 | unsigned int matrix_bits; |
24 | unsigned int alloc_start; |
25 | unsigned int alloc_end; |
26 | unsigned int alloc_size; |
27 | unsigned int global_available; |
28 | unsigned int global_reserved; |
29 | unsigned int systembits_inalloc; |
30 | unsigned int total_allocated; |
31 | unsigned int online_maps; |
32 | struct cpumap __percpu *maps; |
33 | unsigned long *system_map; |
34 | unsigned long scratch_map[]; |
35 | }; |
36 | |
37 | #define CREATE_TRACE_POINTS |
38 | #include <trace/events/irq_matrix.h> |
39 | |
40 | /** |
41 | * irq_alloc_matrix - Allocate a irq_matrix structure and initialize it |
42 | * @matrix_bits: Number of matrix bits must be <= IRQ_MATRIX_BITS |
43 | * @alloc_start: From which bit the allocation search starts |
44 | * @alloc_end: At which bit the allocation search ends, i.e first |
45 | * invalid bit |
46 | */ |
47 | __init struct irq_matrix *irq_alloc_matrix(unsigned int matrix_bits, |
48 | unsigned int alloc_start, |
49 | unsigned int alloc_end) |
50 | { |
51 | unsigned int cpu, matrix_size = BITS_TO_LONGS(matrix_bits); |
52 | struct irq_matrix *m; |
53 | |
54 | m = kzalloc(struct_size(m, scratch_map, matrix_size * 2), GFP_KERNEL); |
55 | if (!m) |
56 | return NULL; |
57 | |
58 | m->system_map = &m->scratch_map[matrix_size]; |
59 | |
60 | m->matrix_bits = matrix_bits; |
61 | m->alloc_start = alloc_start; |
62 | m->alloc_end = alloc_end; |
63 | m->alloc_size = alloc_end - alloc_start; |
64 | m->maps = __alloc_percpu(struct_size(m->maps, alloc_map, matrix_size * 2), |
65 | align: __alignof__(*m->maps)); |
66 | if (!m->maps) { |
67 | kfree(objp: m); |
68 | return NULL; |
69 | } |
70 | |
71 | for_each_possible_cpu(cpu) { |
72 | struct cpumap *cm = per_cpu_ptr(m->maps, cpu); |
73 | |
74 | cm->managed_map = &cm->alloc_map[matrix_size]; |
75 | } |
76 | |
77 | return m; |
78 | } |
79 | |
80 | /** |
81 | * irq_matrix_online - Bring the local CPU matrix online |
82 | * @m: Matrix pointer |
83 | */ |
84 | void irq_matrix_online(struct irq_matrix *m) |
85 | { |
86 | struct cpumap *cm = this_cpu_ptr(m->maps); |
87 | |
88 | BUG_ON(cm->online); |
89 | |
90 | if (!cm->initialized) { |
91 | cm->available = m->alloc_size; |
92 | cm->available -= cm->managed + m->systembits_inalloc; |
93 | cm->initialized = true; |
94 | } |
95 | m->global_available += cm->available; |
96 | cm->online = true; |
97 | m->online_maps++; |
98 | trace_irq_matrix_online(matrix: m); |
99 | } |
100 | |
101 | /** |
102 | * irq_matrix_offline - Bring the local CPU matrix offline |
103 | * @m: Matrix pointer |
104 | */ |
105 | void irq_matrix_offline(struct irq_matrix *m) |
106 | { |
107 | struct cpumap *cm = this_cpu_ptr(m->maps); |
108 | |
109 | /* Update the global available size */ |
110 | m->global_available -= cm->available; |
111 | cm->online = false; |
112 | m->online_maps--; |
113 | trace_irq_matrix_offline(matrix: m); |
114 | } |
115 | |
116 | static unsigned int matrix_alloc_area(struct irq_matrix *m, struct cpumap *cm, |
117 | unsigned int num, bool managed) |
118 | { |
119 | unsigned int area, start = m->alloc_start; |
120 | unsigned int end = m->alloc_end; |
121 | |
122 | bitmap_or(dst: m->scratch_map, src1: cm->managed_map, src2: m->system_map, nbits: end); |
123 | bitmap_or(dst: m->scratch_map, src1: m->scratch_map, src2: cm->alloc_map, nbits: end); |
124 | area = bitmap_find_next_zero_area(map: m->scratch_map, size: end, start, nr: num, align_mask: 0); |
125 | if (area >= end) |
126 | return area; |
127 | if (managed) |
128 | bitmap_set(map: cm->managed_map, start: area, nbits: num); |
129 | else |
130 | bitmap_set(map: cm->alloc_map, start: area, nbits: num); |
131 | return area; |
132 | } |
133 | |
134 | /* Find the best CPU which has the lowest vector allocation count */ |
135 | static unsigned int matrix_find_best_cpu(struct irq_matrix *m, |
136 | const struct cpumask *msk) |
137 | { |
138 | unsigned int cpu, best_cpu, maxavl = 0; |
139 | struct cpumap *cm; |
140 | |
141 | best_cpu = UINT_MAX; |
142 | |
143 | for_each_cpu(cpu, msk) { |
144 | cm = per_cpu_ptr(m->maps, cpu); |
145 | |
146 | if (!cm->online || cm->available <= maxavl) |
147 | continue; |
148 | |
149 | best_cpu = cpu; |
150 | maxavl = cm->available; |
151 | } |
152 | return best_cpu; |
153 | } |
154 | |
155 | /* Find the best CPU which has the lowest number of managed IRQs allocated */ |
156 | static unsigned int matrix_find_best_cpu_managed(struct irq_matrix *m, |
157 | const struct cpumask *msk) |
158 | { |
159 | unsigned int cpu, best_cpu, allocated = UINT_MAX; |
160 | struct cpumap *cm; |
161 | |
162 | best_cpu = UINT_MAX; |
163 | |
164 | for_each_cpu(cpu, msk) { |
165 | cm = per_cpu_ptr(m->maps, cpu); |
166 | |
167 | if (!cm->online || cm->managed_allocated > allocated) |
168 | continue; |
169 | |
170 | best_cpu = cpu; |
171 | allocated = cm->managed_allocated; |
172 | } |
173 | return best_cpu; |
174 | } |
175 | |
176 | /** |
177 | * irq_matrix_assign_system - Assign system wide entry in the matrix |
178 | * @m: Matrix pointer |
179 | * @bit: Which bit to reserve |
180 | * @replace: Replace an already allocated vector with a system |
181 | * vector at the same bit position. |
182 | * |
183 | * The BUG_ON()s below are on purpose. If this goes wrong in the |
184 | * early boot process, then the chance to survive is about zero. |
185 | * If this happens when the system is life, it's not much better. |
186 | */ |
187 | void irq_matrix_assign_system(struct irq_matrix *m, unsigned int bit, |
188 | bool replace) |
189 | { |
190 | struct cpumap *cm = this_cpu_ptr(m->maps); |
191 | |
192 | BUG_ON(bit > m->matrix_bits); |
193 | BUG_ON(m->online_maps > 1 || (m->online_maps && !replace)); |
194 | |
195 | set_bit(nr: bit, addr: m->system_map); |
196 | if (replace) { |
197 | BUG_ON(!test_and_clear_bit(bit, cm->alloc_map)); |
198 | cm->allocated--; |
199 | m->total_allocated--; |
200 | } |
201 | if (bit >= m->alloc_start && bit < m->alloc_end) |
202 | m->systembits_inalloc++; |
203 | |
204 | trace_irq_matrix_assign_system(bit, matrix: m); |
205 | } |
206 | |
207 | /** |
208 | * irq_matrix_reserve_managed - Reserve a managed interrupt in a CPU map |
209 | * @m: Matrix pointer |
210 | * @msk: On which CPUs the bits should be reserved. |
211 | * |
212 | * Can be called for offline CPUs. Note, this will only reserve one bit |
213 | * on all CPUs in @msk, but it's not guaranteed that the bits are at the |
214 | * same offset on all CPUs |
215 | */ |
216 | int irq_matrix_reserve_managed(struct irq_matrix *m, const struct cpumask *msk) |
217 | { |
218 | unsigned int cpu, failed_cpu; |
219 | |
220 | for_each_cpu(cpu, msk) { |
221 | struct cpumap *cm = per_cpu_ptr(m->maps, cpu); |
222 | unsigned int bit; |
223 | |
224 | bit = matrix_alloc_area(m, cm, num: 1, managed: true); |
225 | if (bit >= m->alloc_end) |
226 | goto cleanup; |
227 | cm->managed++; |
228 | if (cm->online) { |
229 | cm->available--; |
230 | m->global_available--; |
231 | } |
232 | trace_irq_matrix_reserve_managed(bit, cpu, matrix: m, cmap: cm); |
233 | } |
234 | return 0; |
235 | cleanup: |
236 | failed_cpu = cpu; |
237 | for_each_cpu(cpu, msk) { |
238 | if (cpu == failed_cpu) |
239 | break; |
240 | irq_matrix_remove_managed(m, cpumask_of(cpu)); |
241 | } |
242 | return -ENOSPC; |
243 | } |
244 | |
245 | /** |
246 | * irq_matrix_remove_managed - Remove managed interrupts in a CPU map |
247 | * @m: Matrix pointer |
248 | * @msk: On which CPUs the bits should be removed |
249 | * |
250 | * Can be called for offline CPUs |
251 | * |
252 | * This removes not allocated managed interrupts from the map. It does |
253 | * not matter which one because the managed interrupts free their |
254 | * allocation when they shut down. If not, the accounting is screwed, |
255 | * but all what can be done at this point is warn about it. |
256 | */ |
257 | void irq_matrix_remove_managed(struct irq_matrix *m, const struct cpumask *msk) |
258 | { |
259 | unsigned int cpu; |
260 | |
261 | for_each_cpu(cpu, msk) { |
262 | struct cpumap *cm = per_cpu_ptr(m->maps, cpu); |
263 | unsigned int bit, end = m->alloc_end; |
264 | |
265 | if (WARN_ON_ONCE(!cm->managed)) |
266 | continue; |
267 | |
268 | /* Get managed bit which are not allocated */ |
269 | bitmap_andnot(dst: m->scratch_map, src1: cm->managed_map, src2: cm->alloc_map, nbits: end); |
270 | |
271 | bit = find_first_bit(addr: m->scratch_map, size: end); |
272 | if (WARN_ON_ONCE(bit >= end)) |
273 | continue; |
274 | |
275 | clear_bit(nr: bit, addr: cm->managed_map); |
276 | |
277 | cm->managed--; |
278 | if (cm->online) { |
279 | cm->available++; |
280 | m->global_available++; |
281 | } |
282 | trace_irq_matrix_remove_managed(bit, cpu, matrix: m, cmap: cm); |
283 | } |
284 | } |
285 | |
286 | /** |
287 | * irq_matrix_alloc_managed - Allocate a managed interrupt in a CPU map |
288 | * @m: Matrix pointer |
289 | * @msk: Which CPUs to search in |
290 | * @mapped_cpu: Pointer to store the CPU for which the irq was allocated |
291 | */ |
292 | int irq_matrix_alloc_managed(struct irq_matrix *m, const struct cpumask *msk, |
293 | unsigned int *mapped_cpu) |
294 | { |
295 | unsigned int bit, cpu, end; |
296 | struct cpumap *cm; |
297 | |
298 | if (cpumask_empty(srcp: msk)) |
299 | return -EINVAL; |
300 | |
301 | cpu = matrix_find_best_cpu_managed(m, msk); |
302 | if (cpu == UINT_MAX) |
303 | return -ENOSPC; |
304 | |
305 | cm = per_cpu_ptr(m->maps, cpu); |
306 | end = m->alloc_end; |
307 | /* Get managed bit which are not allocated */ |
308 | bitmap_andnot(dst: m->scratch_map, src1: cm->managed_map, src2: cm->alloc_map, nbits: end); |
309 | bit = find_first_bit(addr: m->scratch_map, size: end); |
310 | if (bit >= end) |
311 | return -ENOSPC; |
312 | set_bit(nr: bit, addr: cm->alloc_map); |
313 | cm->allocated++; |
314 | cm->managed_allocated++; |
315 | m->total_allocated++; |
316 | *mapped_cpu = cpu; |
317 | trace_irq_matrix_alloc_managed(bit, cpu, matrix: m, cmap: cm); |
318 | return bit; |
319 | } |
320 | |
321 | /** |
322 | * irq_matrix_assign - Assign a preallocated interrupt in the local CPU map |
323 | * @m: Matrix pointer |
324 | * @bit: Which bit to mark |
325 | * |
326 | * This should only be used to mark preallocated vectors |
327 | */ |
328 | void irq_matrix_assign(struct irq_matrix *m, unsigned int bit) |
329 | { |
330 | struct cpumap *cm = this_cpu_ptr(m->maps); |
331 | |
332 | if (WARN_ON_ONCE(bit < m->alloc_start || bit >= m->alloc_end)) |
333 | return; |
334 | if (WARN_ON_ONCE(test_and_set_bit(bit, cm->alloc_map))) |
335 | return; |
336 | cm->allocated++; |
337 | m->total_allocated++; |
338 | cm->available--; |
339 | m->global_available--; |
340 | trace_irq_matrix_assign(bit, smp_processor_id(), matrix: m, cmap: cm); |
341 | } |
342 | |
343 | /** |
344 | * irq_matrix_reserve - Reserve interrupts |
345 | * @m: Matrix pointer |
346 | * |
347 | * This is merely a book keeping call. It increments the number of globally |
348 | * reserved interrupt bits w/o actually allocating them. This allows to |
349 | * setup interrupt descriptors w/o assigning low level resources to it. |
350 | * The actual allocation happens when the interrupt gets activated. |
351 | */ |
352 | void irq_matrix_reserve(struct irq_matrix *m) |
353 | { |
354 | if (m->global_reserved == m->global_available) |
355 | pr_warn("Interrupt reservation exceeds available resources\n" ); |
356 | |
357 | m->global_reserved++; |
358 | trace_irq_matrix_reserve(matrix: m); |
359 | } |
360 | |
361 | /** |
362 | * irq_matrix_remove_reserved - Remove interrupt reservation |
363 | * @m: Matrix pointer |
364 | * |
365 | * This is merely a book keeping call. It decrements the number of globally |
366 | * reserved interrupt bits. This is used to undo irq_matrix_reserve() when the |
367 | * interrupt was never in use and a real vector allocated, which undid the |
368 | * reservation. |
369 | */ |
370 | void irq_matrix_remove_reserved(struct irq_matrix *m) |
371 | { |
372 | m->global_reserved--; |
373 | trace_irq_matrix_remove_reserved(matrix: m); |
374 | } |
375 | |
376 | /** |
377 | * irq_matrix_alloc - Allocate a regular interrupt in a CPU map |
378 | * @m: Matrix pointer |
379 | * @msk: Which CPUs to search in |
380 | * @reserved: Allocate previously reserved interrupts |
381 | * @mapped_cpu: Pointer to store the CPU for which the irq was allocated |
382 | */ |
383 | int irq_matrix_alloc(struct irq_matrix *m, const struct cpumask *msk, |
384 | bool reserved, unsigned int *mapped_cpu) |
385 | { |
386 | unsigned int cpu, bit; |
387 | struct cpumap *cm; |
388 | |
389 | /* |
390 | * Not required in theory, but matrix_find_best_cpu() uses |
391 | * for_each_cpu() which ignores the cpumask on UP . |
392 | */ |
393 | if (cpumask_empty(srcp: msk)) |
394 | return -EINVAL; |
395 | |
396 | cpu = matrix_find_best_cpu(m, msk); |
397 | if (cpu == UINT_MAX) |
398 | return -ENOSPC; |
399 | |
400 | cm = per_cpu_ptr(m->maps, cpu); |
401 | bit = matrix_alloc_area(m, cm, num: 1, managed: false); |
402 | if (bit >= m->alloc_end) |
403 | return -ENOSPC; |
404 | cm->allocated++; |
405 | cm->available--; |
406 | m->total_allocated++; |
407 | m->global_available--; |
408 | if (reserved) |
409 | m->global_reserved--; |
410 | *mapped_cpu = cpu; |
411 | trace_irq_matrix_alloc(bit, cpu, matrix: m, cmap: cm); |
412 | return bit; |
413 | |
414 | } |
415 | |
416 | /** |
417 | * irq_matrix_free - Free allocated interrupt in the matrix |
418 | * @m: Matrix pointer |
419 | * @cpu: Which CPU map needs be updated |
420 | * @bit: The bit to remove |
421 | * @managed: If true, the interrupt is managed and not accounted |
422 | * as available. |
423 | */ |
424 | void irq_matrix_free(struct irq_matrix *m, unsigned int cpu, |
425 | unsigned int bit, bool managed) |
426 | { |
427 | struct cpumap *cm = per_cpu_ptr(m->maps, cpu); |
428 | |
429 | if (WARN_ON_ONCE(bit < m->alloc_start || bit >= m->alloc_end)) |
430 | return; |
431 | |
432 | if (WARN_ON_ONCE(!test_and_clear_bit(bit, cm->alloc_map))) |
433 | return; |
434 | |
435 | cm->allocated--; |
436 | if(managed) |
437 | cm->managed_allocated--; |
438 | |
439 | if (cm->online) |
440 | m->total_allocated--; |
441 | |
442 | if (!managed) { |
443 | cm->available++; |
444 | if (cm->online) |
445 | m->global_available++; |
446 | } |
447 | trace_irq_matrix_free(bit, cpu, matrix: m, cmap: cm); |
448 | } |
449 | |
450 | /** |
451 | * irq_matrix_available - Get the number of globally available irqs |
452 | * @m: Pointer to the matrix to query |
453 | * @cpudown: If true, the local CPU is about to go down, adjust |
454 | * the number of available irqs accordingly |
455 | */ |
456 | unsigned int irq_matrix_available(struct irq_matrix *m, bool cpudown) |
457 | { |
458 | struct cpumap *cm = this_cpu_ptr(m->maps); |
459 | |
460 | if (!cpudown) |
461 | return m->global_available; |
462 | return m->global_available - cm->available; |
463 | } |
464 | |
465 | /** |
466 | * irq_matrix_reserved - Get the number of globally reserved irqs |
467 | * @m: Pointer to the matrix to query |
468 | */ |
469 | unsigned int irq_matrix_reserved(struct irq_matrix *m) |
470 | { |
471 | return m->global_reserved; |
472 | } |
473 | |
474 | /** |
475 | * irq_matrix_allocated - Get the number of allocated non-managed irqs on the local CPU |
476 | * @m: Pointer to the matrix to search |
477 | * |
478 | * This returns number of allocated non-managed interrupts. |
479 | */ |
480 | unsigned int irq_matrix_allocated(struct irq_matrix *m) |
481 | { |
482 | struct cpumap *cm = this_cpu_ptr(m->maps); |
483 | |
484 | return cm->allocated - cm->managed_allocated; |
485 | } |
486 | |
487 | #ifdef CONFIG_GENERIC_IRQ_DEBUGFS |
488 | /** |
489 | * irq_matrix_debug_show - Show detailed allocation information |
490 | * @sf: Pointer to the seq_file to print to |
491 | * @m: Pointer to the matrix allocator |
492 | * @ind: Indentation for the print format |
493 | * |
494 | * Note, this is a lockless snapshot. |
495 | */ |
496 | void irq_matrix_debug_show(struct seq_file *sf, struct irq_matrix *m, int ind) |
497 | { |
498 | unsigned int nsys = bitmap_weight(src: m->system_map, nbits: m->matrix_bits); |
499 | int cpu; |
500 | |
501 | seq_printf(m: sf, fmt: "Online bitmaps: %6u\n" , m->online_maps); |
502 | seq_printf(m: sf, fmt: "Global available: %6u\n" , m->global_available); |
503 | seq_printf(m: sf, fmt: "Global reserved: %6u\n" , m->global_reserved); |
504 | seq_printf(m: sf, fmt: "Total allocated: %6u\n" , m->total_allocated); |
505 | seq_printf(m: sf, fmt: "System: %u: %*pbl\n" , nsys, m->matrix_bits, |
506 | m->system_map); |
507 | seq_printf(m: sf, fmt: "%*s| CPU | avl | man | mac | act | vectors\n" , ind, " " ); |
508 | cpus_read_lock(); |
509 | for_each_online_cpu(cpu) { |
510 | struct cpumap *cm = per_cpu_ptr(m->maps, cpu); |
511 | |
512 | seq_printf(m: sf, fmt: "%*s %4d %4u %4u %4u %4u %*pbl\n" , ind, " " , |
513 | cpu, cm->available, cm->managed, |
514 | cm->managed_allocated, cm->allocated, |
515 | m->matrix_bits, cm->alloc_map); |
516 | } |
517 | cpus_read_unlock(); |
518 | } |
519 | #endif |
520 | |