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 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                                  __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  */
  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  */
 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
 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 */
 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(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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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(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