kernel/irq/matrix.c

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