~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/irq/matrix.c

Version: ~ [ linux-5.0-rc6 ] ~ [ linux-4.20.10 ] ~ [ linux-4.19.23 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.101 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.158 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.174 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.134 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.63 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp