kernel/irq/matrix.c

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