matrix.c 13 KB

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