xref: /linux/kernel/irq/matrix.c (revision 79790b6818e96c58fe2bffee1b418c16e64e7b80)
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  */
irq_alloc_matrix(unsigned int matrix_bits,unsigned int alloc_start,unsigned int alloc_end)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 				 __alignof__(*m->maps));
66 	if (!m->maps) {
67 		kfree(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  */
irq_matrix_online(struct irq_matrix * m)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(m);
99 }
100 
101 /**
102  * irq_matrix_offline - Bring the local CPU matrix offline
103  * @m:		Matrix pointer
104  */
irq_matrix_offline(struct irq_matrix * m)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(m);
114 }
115 
matrix_alloc_area(struct irq_matrix * m,struct cpumap * cm,unsigned int num,bool managed)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(m->scratch_map, cm->managed_map, m->system_map, end);
123 	bitmap_or(m->scratch_map, m->scratch_map, cm->alloc_map, end);
124 	area = bitmap_find_next_zero_area(m->scratch_map, end, start, num, 0);
125 	if (area >= end)
126 		return area;
127 	if (managed)
128 		bitmap_set(cm->managed_map, area, num);
129 	else
130 		bitmap_set(cm->alloc_map, area, num);
131 	return area;
132 }
133 
134 /* Find the best CPU which has the lowest vector allocation count */
matrix_find_best_cpu(struct irq_matrix * m,const struct cpumask * msk)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 */
matrix_find_best_cpu_managed(struct irq_matrix * m,const struct cpumask * msk)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  */
irq_matrix_assign_system(struct irq_matrix * m,unsigned int bit,bool replace)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(bit, 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, 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  */
irq_matrix_reserve_managed(struct irq_matrix * m,const struct cpumask * msk)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, 1, 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, m, 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  */
irq_matrix_remove_managed(struct irq_matrix * m,const struct cpumask * msk)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(m->scratch_map, cm->managed_map, cm->alloc_map, end);
270 
271 		bit = find_first_bit(m->scratch_map, end);
272 		if (WARN_ON_ONCE(bit >= end))
273 			continue;
274 
275 		clear_bit(bit, 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, m, 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  */
irq_matrix_alloc_managed(struct irq_matrix * m,const struct cpumask * msk,unsigned int * mapped_cpu)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(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(m->scratch_map, cm->managed_map, cm->alloc_map, end);
309 	bit = find_first_bit(m->scratch_map, end);
310 	if (bit >= end)
311 		return -ENOSPC;
312 	set_bit(bit, 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, m, 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  */
irq_matrix_assign(struct irq_matrix * m,unsigned int bit)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(), m, 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  */
irq_matrix_reserve(struct irq_matrix * m)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(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  */
irq_matrix_remove_reserved(struct irq_matrix * m)370 void irq_matrix_remove_reserved(struct irq_matrix *m)
371 {
372 	m->global_reserved--;
373 	trace_irq_matrix_remove_reserved(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  */
irq_matrix_alloc(struct irq_matrix * m,const struct cpumask * msk,bool reserved,unsigned int * mapped_cpu)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(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, 1, 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, m, 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  */
irq_matrix_free(struct irq_matrix * m,unsigned int cpu,unsigned int bit,bool managed)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, m, 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  */
irq_matrix_available(struct irq_matrix * m,bool cpudown)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  */
irq_matrix_reserved(struct irq_matrix * m)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  */
irq_matrix_allocated(struct irq_matrix * m)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  */
irq_matrix_debug_show(struct seq_file * sf,struct irq_matrix * m,int ind)496 void irq_matrix_debug_show(struct seq_file *sf, struct irq_matrix *m, int ind)
497 {
498 	unsigned int nsys = bitmap_weight(m->system_map, m->matrix_bits);
499 	int cpu;
500 
501 	seq_printf(sf, "Online bitmaps:   %6u\n", m->online_maps);
502 	seq_printf(sf, "Global available: %6u\n", m->global_available);
503 	seq_printf(sf, "Global reserved:  %6u\n", m->global_reserved);
504 	seq_printf(sf, "Total allocated:  %6u\n", m->total_allocated);
505 	seq_printf(sf, "System: %u: %*pbl\n", nsys, m->matrix_bits,
506 		   m->system_map);
507 	seq_printf(sf, "%*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(sf, "%*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