timings.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958
  1. // SPDX-License-Identifier: GPL-2.0
  2. // Copyright (C) 2016, Linaro Ltd - Daniel Lezcano <daniel.lezcano@linaro.org>
  3. #define pr_fmt(fmt) "irq_timings: " fmt
  4. #include <linux/kernel.h>
  5. #include <linux/percpu.h>
  6. #include <linux/slab.h>
  7. #include <linux/static_key.h>
  8. #include <linux/init.h>
  9. #include <linux/interrupt.h>
  10. #include <linux/idr.h>
  11. #include <linux/irq.h>
  12. #include <linux/math64.h>
  13. #include <linux/log2.h>
  14. #include <trace/events/irq.h>
  15. #include "internals.h"
  16. DEFINE_STATIC_KEY_FALSE(irq_timing_enabled);
  17. DEFINE_PER_CPU(struct irq_timings, irq_timings);
  18. static DEFINE_IDR(irqt_stats);
  19. void irq_timings_enable(void)
  20. {
  21. static_branch_enable(&irq_timing_enabled);
  22. }
  23. void irq_timings_disable(void)
  24. {
  25. static_branch_disable(&irq_timing_enabled);
  26. }
  27. /*
  28. * The main goal of this algorithm is to predict the next interrupt
  29. * occurrence on the current CPU.
  30. *
  31. * Currently, the interrupt timings are stored in a circular array
  32. * buffer every time there is an interrupt, as a tuple: the interrupt
  33. * number and the associated timestamp when the event occurred <irq,
  34. * timestamp>.
  35. *
  36. * For every interrupt occurring in a short period of time, we can
  37. * measure the elapsed time between the occurrences for the same
  38. * interrupt and we end up with a suite of intervals. The experience
  39. * showed the interrupts are often coming following a periodic
  40. * pattern.
  41. *
  42. * The objective of the algorithm is to find out this periodic pattern
  43. * in a fastest way and use its period to predict the next irq event.
  44. *
  45. * When the next interrupt event is requested, we are in the situation
  46. * where the interrupts are disabled and the circular buffer
  47. * containing the timings is filled with the events which happened
  48. * after the previous next-interrupt-event request.
  49. *
  50. * At this point, we read the circular buffer and we fill the irq
  51. * related statistics structure. After this step, the circular array
  52. * containing the timings is empty because all the values are
  53. * dispatched in their corresponding buffers.
  54. *
  55. * Now for each interrupt, we can predict the next event by using the
  56. * suffix array, log interval and exponential moving average
  57. *
  58. * 1. Suffix array
  59. *
  60. * Suffix array is an array of all the suffixes of a string. It is
  61. * widely used as a data structure for compression, text search, ...
  62. * For instance for the word 'banana', the suffixes will be: 'banana'
  63. * 'anana' 'nana' 'ana' 'na' 'a'
  64. *
  65. * Usually, the suffix array is sorted but for our purpose it is
  66. * not necessary and won't provide any improvement in the context of
  67. * the solved problem where we clearly define the boundaries of the
  68. * search by a max period and min period.
  69. *
  70. * The suffix array will build a suite of intervals of different
  71. * length and will look for the repetition of each suite. If the suite
  72. * is repeating then we have the period because it is the length of
  73. * the suite whatever its position in the buffer.
  74. *
  75. * 2. Log interval
  76. *
  77. * We saw the irq timings allow to compute the interval of the
  78. * occurrences for a specific interrupt. We can reasonibly assume the
  79. * longer is the interval, the higher is the error for the next event
  80. * and we can consider storing those interval values into an array
  81. * where each slot in the array correspond to an interval at the power
  82. * of 2 of the index. For example, index 12 will contain values
  83. * between 2^11 and 2^12.
  84. *
  85. * At the end we have an array of values where at each index defines a
  86. * [2^index - 1, 2 ^ index] interval values allowing to store a large
  87. * number of values inside a small array.
  88. *
  89. * For example, if we have the value 1123, then we store it at
  90. * ilog2(1123) = 10 index value.
  91. *
  92. * Storing those value at the specific index is done by computing an
  93. * exponential moving average for this specific slot. For instance,
  94. * for values 1800, 1123, 1453, ... fall under the same slot (10) and
  95. * the exponential moving average is computed every time a new value
  96. * is stored at this slot.
  97. *
  98. * 3. Exponential Moving Average
  99. *
  100. * The EMA is largely used to track a signal for stocks or as a low
  101. * pass filter. The magic of the formula, is it is very simple and the
  102. * reactivity of the average can be tuned with the factors called
  103. * alpha.
  104. *
  105. * The higher the alphas are, the faster the average respond to the
  106. * signal change. In our case, if a slot in the array is a big
  107. * interval, we can have numbers with a big difference between
  108. * them. The impact of those differences in the average computation
  109. * can be tuned by changing the alpha value.
  110. *
  111. *
  112. * -- The algorithm --
  113. *
  114. * We saw the different processing above, now let's see how they are
  115. * used together.
  116. *
  117. * For each interrupt:
  118. * For each interval:
  119. * Compute the index = ilog2(interval)
  120. * Compute a new_ema(buffer[index], interval)
  121. * Store the index in a circular buffer
  122. *
  123. * Compute the suffix array of the indexes
  124. *
  125. * For each suffix:
  126. * If the suffix is reverse-found 3 times
  127. * Return suffix
  128. *
  129. * Return Not found
  130. *
  131. * However we can not have endless suffix array to be build, it won't
  132. * make sense and it will add an extra overhead, so we can restrict
  133. * this to a maximum suffix length of 5 and a minimum suffix length of
  134. * 2. The experience showed 5 is the majority of the maximum pattern
  135. * period found for different devices.
  136. *
  137. * The result is a pattern finding less than 1us for an interrupt.
  138. *
  139. * Example based on real values:
  140. *
  141. * Example 1 : MMC write/read interrupt interval:
  142. *
  143. * 223947, 1240, 1384, 1386, 1386,
  144. * 217416, 1236, 1384, 1386, 1387,
  145. * 214719, 1241, 1386, 1387, 1384,
  146. * 213696, 1234, 1384, 1386, 1388,
  147. * 219904, 1240, 1385, 1389, 1385,
  148. * 212240, 1240, 1386, 1386, 1386,
  149. * 214415, 1236, 1384, 1386, 1387,
  150. * 214276, 1234, 1384, 1388, ?
  151. *
  152. * For each element, apply ilog2(value)
  153. *
  154. * 15, 8, 8, 8, 8,
  155. * 15, 8, 8, 8, 8,
  156. * 15, 8, 8, 8, 8,
  157. * 15, 8, 8, 8, 8,
  158. * 15, 8, 8, 8, 8,
  159. * 15, 8, 8, 8, 8,
  160. * 15, 8, 8, 8, 8,
  161. * 15, 8, 8, 8, ?
  162. *
  163. * Max period of 5, we take the last (max_period * 3) 15 elements as
  164. * we can be confident if the pattern repeats itself three times it is
  165. * a repeating pattern.
  166. *
  167. * 8,
  168. * 15, 8, 8, 8, 8,
  169. * 15, 8, 8, 8, 8,
  170. * 15, 8, 8, 8, ?
  171. *
  172. * Suffixes are:
  173. *
  174. * 1) 8, 15, 8, 8, 8 <- max period
  175. * 2) 8, 15, 8, 8
  176. * 3) 8, 15, 8
  177. * 4) 8, 15 <- min period
  178. *
  179. * From there we search the repeating pattern for each suffix.
  180. *
  181. * buffer: 8, 15, 8, 8, 8, 8, 15, 8, 8, 8, 8, 15, 8, 8, 8
  182. * | | | | | | | | | | | | | | |
  183. * 8, 15, 8, 8, 8 | | | | | | | | | |
  184. * 8, 15, 8, 8, 8 | | | | |
  185. * 8, 15, 8, 8, 8
  186. *
  187. * When moving the suffix, we found exactly 3 matches.
  188. *
  189. * The first suffix with period 5 is repeating.
  190. *
  191. * The next event is (3 * max_period) % suffix_period
  192. *
  193. * In this example, the result 0, so the next event is suffix[0] => 8
  194. *
  195. * However, 8 is the index in the array of exponential moving average
  196. * which was calculated on the fly when storing the values, so the
  197. * interval is ema[8] = 1366
  198. *
  199. *
  200. * Example 2:
  201. *
  202. * 4, 3, 5, 100,
  203. * 3, 3, 5, 117,
  204. * 4, 4, 5, 112,
  205. * 4, 3, 4, 110,
  206. * 3, 5, 3, 117,
  207. * 4, 4, 5, 112,
  208. * 4, 3, 4, 110,
  209. * 3, 4, 5, 112,
  210. * 4, 3, 4, 110
  211. *
  212. * ilog2
  213. *
  214. * 0, 0, 0, 4,
  215. * 0, 0, 0, 4,
  216. * 0, 0, 0, 4,
  217. * 0, 0, 0, 4,
  218. * 0, 0, 0, 4,
  219. * 0, 0, 0, 4,
  220. * 0, 0, 0, 4,
  221. * 0, 0, 0, 4,
  222. * 0, 0, 0, 4
  223. *
  224. * Max period 5:
  225. * 0, 0, 4,
  226. * 0, 0, 0, 4,
  227. * 0, 0, 0, 4,
  228. * 0, 0, 0, 4
  229. *
  230. * Suffixes:
  231. *
  232. * 1) 0, 0, 4, 0, 0
  233. * 2) 0, 0, 4, 0
  234. * 3) 0, 0, 4
  235. * 4) 0, 0
  236. *
  237. * buffer: 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4
  238. * | | | | | | X
  239. * 0, 0, 4, 0, 0, | X
  240. * 0, 0
  241. *
  242. * buffer: 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4
  243. * | | | | | | | | | | | | | | |
  244. * 0, 0, 4, 0, | | | | | | | | | | |
  245. * 0, 0, 4, 0, | | | | | | |
  246. * 0, 0, 4, 0, | | |
  247. * 0 0 4
  248. *
  249. * Pattern is found 3 times, the remaining is 1 which results from
  250. * (max_period * 3) % suffix_period. This value is the index in the
  251. * suffix arrays. The suffix array for a period 4 has the value 4
  252. * at index 1.
  253. */
  254. #define EMA_ALPHA_VAL 64
  255. #define EMA_ALPHA_SHIFT 7
  256. #define PREDICTION_PERIOD_MIN 3
  257. #define PREDICTION_PERIOD_MAX 5
  258. #define PREDICTION_FACTOR 4
  259. #define PREDICTION_MAX 10 /* 2 ^ PREDICTION_MAX useconds */
  260. #define PREDICTION_BUFFER_SIZE 16 /* slots for EMAs, hardly more than 16 */
  261. /*
  262. * Number of elements in the circular buffer: If it happens it was
  263. * flushed before, then the number of elements could be smaller than
  264. * IRQ_TIMINGS_SIZE, so the count is used, otherwise the array size is
  265. * used as we wrapped. The index begins from zero when we did not
  266. * wrap. That could be done in a nicer way with the proper circular
  267. * array structure type but with the cost of extra computation in the
  268. * interrupt handler hot path. We choose efficiency.
  269. */
  270. #define for_each_irqts(i, irqts) \
  271. for (i = irqts->count < IRQ_TIMINGS_SIZE ? \
  272. 0 : irqts->count & IRQ_TIMINGS_MASK, \
  273. irqts->count = min(IRQ_TIMINGS_SIZE, \
  274. irqts->count); \
  275. irqts->count > 0; irqts->count--, \
  276. i = (i + 1) & IRQ_TIMINGS_MASK)
  277. struct irqt_stat {
  278. u64 last_ts;
  279. u64 ema_time[PREDICTION_BUFFER_SIZE];
  280. int timings[IRQ_TIMINGS_SIZE];
  281. int circ_timings[IRQ_TIMINGS_SIZE];
  282. int count;
  283. };
  284. /*
  285. * Exponential moving average computation
  286. */
  287. static u64 irq_timings_ema_new(u64 value, u64 ema_old)
  288. {
  289. s64 diff;
  290. if (unlikely(!ema_old))
  291. return value;
  292. diff = (value - ema_old) * EMA_ALPHA_VAL;
  293. /*
  294. * We can use a s64 type variable to be added with the u64
  295. * ema_old variable as this one will never have its topmost
  296. * bit set, it will be always smaller than 2^63 nanosec
  297. * interrupt interval (292 years).
  298. */
  299. return ema_old + (diff >> EMA_ALPHA_SHIFT);
  300. }
  301. static int irq_timings_next_event_index(int *buffer, size_t len, int period_max)
  302. {
  303. int period;
  304. /*
  305. * Move the beginning pointer to the end minus the max period x 3.
  306. * We are at the point we can begin searching the pattern
  307. */
  308. buffer = &buffer[len - (period_max * 3)];
  309. /* Adjust the length to the maximum allowed period x 3 */
  310. len = period_max * 3;
  311. /*
  312. * The buffer contains the suite of intervals, in a ilog2
  313. * basis, we are looking for a repetition. We point the
  314. * beginning of the search three times the length of the
  315. * period beginning at the end of the buffer. We do that for
  316. * each suffix.
  317. */
  318. for (period = period_max; period >= PREDICTION_PERIOD_MIN; period--) {
  319. /*
  320. * The first comparison always succeed because the
  321. * suffix is deduced from the first n-period bytes of
  322. * the buffer and we compare the initial suffix with
  323. * itself, so we can skip the first iteration.
  324. */
  325. int idx = period;
  326. size_t size = period;
  327. /*
  328. * We look if the suite with period 'i' repeat
  329. * itself. If it is truncated at the end, as it
  330. * repeats we can use the period to find out the next
  331. * element with the modulo.
  332. */
  333. while (!memcmp(buffer, &buffer[idx], size * sizeof(int))) {
  334. /*
  335. * Move the index in a period basis
  336. */
  337. idx += size;
  338. /*
  339. * If this condition is reached, all previous
  340. * memcmp were successful, so the period is
  341. * found.
  342. */
  343. if (idx == len)
  344. return buffer[len % period];
  345. /*
  346. * If the remaining elements to compare are
  347. * smaller than the period, readjust the size
  348. * of the comparison for the last iteration.
  349. */
  350. if (len - idx < period)
  351. size = len - idx;
  352. }
  353. }
  354. return -1;
  355. }
  356. static u64 __irq_timings_next_event(struct irqt_stat *irqs, int irq, u64 now)
  357. {
  358. int index, i, period_max, count, start, min = INT_MAX;
  359. if ((now - irqs->last_ts) >= NSEC_PER_SEC) {
  360. irqs->count = irqs->last_ts = 0;
  361. return U64_MAX;
  362. }
  363. /*
  364. * As we want to find three times the repetition, we need a
  365. * number of intervals greater or equal to three times the
  366. * maximum period, otherwise we truncate the max period.
  367. */
  368. period_max = irqs->count > (3 * PREDICTION_PERIOD_MAX) ?
  369. PREDICTION_PERIOD_MAX : irqs->count / 3;
  370. /*
  371. * If we don't have enough irq timings for this prediction,
  372. * just bail out.
  373. */
  374. if (period_max <= PREDICTION_PERIOD_MIN)
  375. return U64_MAX;
  376. /*
  377. * 'count' will depends if the circular buffer wrapped or not
  378. */
  379. count = irqs->count < IRQ_TIMINGS_SIZE ?
  380. irqs->count : IRQ_TIMINGS_SIZE;
  381. start = irqs->count < IRQ_TIMINGS_SIZE ?
  382. 0 : (irqs->count & IRQ_TIMINGS_MASK);
  383. /*
  384. * Copy the content of the circular buffer into another buffer
  385. * in order to linearize the buffer instead of dealing with
  386. * wrapping indexes and shifted array which will be prone to
  387. * error and extremelly difficult to debug.
  388. */
  389. for (i = 0; i < count; i++) {
  390. int index = (start + i) & IRQ_TIMINGS_MASK;
  391. irqs->timings[i] = irqs->circ_timings[index];
  392. min = min_t(int, irqs->timings[i], min);
  393. }
  394. index = irq_timings_next_event_index(irqs->timings, count, period_max);
  395. if (index < 0)
  396. return irqs->last_ts + irqs->ema_time[min];
  397. return irqs->last_ts + irqs->ema_time[index];
  398. }
  399. static __always_inline int irq_timings_interval_index(u64 interval)
  400. {
  401. /*
  402. * The PREDICTION_FACTOR increase the interval size for the
  403. * array of exponential average.
  404. */
  405. u64 interval_us = (interval >> 10) / PREDICTION_FACTOR;
  406. return likely(interval_us) ? ilog2(interval_us) : 0;
  407. }
  408. static __always_inline void __irq_timings_store(int irq, struct irqt_stat *irqs,
  409. u64 interval)
  410. {
  411. int index;
  412. /*
  413. * Get the index in the ema table for this interrupt.
  414. */
  415. index = irq_timings_interval_index(interval);
  416. if (index > PREDICTION_BUFFER_SIZE - 1) {
  417. irqs->count = 0;
  418. return;
  419. }
  420. /*
  421. * Store the index as an element of the pattern in another
  422. * circular array.
  423. */
  424. irqs->circ_timings[irqs->count & IRQ_TIMINGS_MASK] = index;
  425. irqs->ema_time[index] = irq_timings_ema_new(interval,
  426. irqs->ema_time[index]);
  427. irqs->count++;
  428. }
  429. static inline void irq_timings_store(int irq, struct irqt_stat *irqs, u64 ts)
  430. {
  431. u64 old_ts = irqs->last_ts;
  432. u64 interval;
  433. /*
  434. * The timestamps are absolute time values, we need to compute
  435. * the timing interval between two interrupts.
  436. */
  437. irqs->last_ts = ts;
  438. /*
  439. * The interval type is u64 in order to deal with the same
  440. * type in our computation, that prevent mindfuck issues with
  441. * overflow, sign and division.
  442. */
  443. interval = ts - old_ts;
  444. /*
  445. * The interrupt triggered more than one second apart, that
  446. * ends the sequence as predictible for our purpose. In this
  447. * case, assume we have the beginning of a sequence and the
  448. * timestamp is the first value. As it is impossible to
  449. * predict anything at this point, return.
  450. *
  451. * Note the first timestamp of the sequence will always fall
  452. * in this test because the old_ts is zero. That is what we
  453. * want as we need another timestamp to compute an interval.
  454. */
  455. if (interval >= NSEC_PER_SEC) {
  456. irqs->count = 0;
  457. return;
  458. }
  459. __irq_timings_store(irq, irqs, interval);
  460. }
  461. /**
  462. * irq_timings_next_event - Return when the next event is supposed to arrive
  463. *
  464. * During the last busy cycle, the number of interrupts is incremented
  465. * and stored in the irq_timings structure. This information is
  466. * necessary to:
  467. *
  468. * - know if the index in the table wrapped up:
  469. *
  470. * If more than the array size interrupts happened during the
  471. * last busy/idle cycle, the index wrapped up and we have to
  472. * begin with the next element in the array which is the last one
  473. * in the sequence, otherwise it is a the index 0.
  474. *
  475. * - have an indication of the interrupts activity on this CPU
  476. * (eg. irq/sec)
  477. *
  478. * The values are 'consumed' after inserting in the statistical model,
  479. * thus the count is reinitialized.
  480. *
  481. * The array of values **must** be browsed in the time direction, the
  482. * timestamp must increase between an element and the next one.
  483. *
  484. * Returns a nanosec time based estimation of the earliest interrupt,
  485. * U64_MAX otherwise.
  486. */
  487. u64 irq_timings_next_event(u64 now)
  488. {
  489. struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
  490. struct irqt_stat *irqs;
  491. struct irqt_stat __percpu *s;
  492. u64 ts, next_evt = U64_MAX;
  493. int i, irq = 0;
  494. /*
  495. * This function must be called with the local irq disabled in
  496. * order to prevent the timings circular buffer to be updated
  497. * while we are reading it.
  498. */
  499. lockdep_assert_irqs_disabled();
  500. if (!irqts->count)
  501. return next_evt;
  502. /*
  503. * Number of elements in the circular buffer: If it happens it
  504. * was flushed before, then the number of elements could be
  505. * smaller than IRQ_TIMINGS_SIZE, so the count is used,
  506. * otherwise the array size is used as we wrapped. The index
  507. * begins from zero when we did not wrap. That could be done
  508. * in a nicer way with the proper circular array structure
  509. * type but with the cost of extra computation in the
  510. * interrupt handler hot path. We choose efficiency.
  511. *
  512. * Inject measured irq/timestamp to the pattern prediction
  513. * model while decrementing the counter because we consume the
  514. * data from our circular buffer.
  515. */
  516. for_each_irqts(i, irqts) {
  517. irq = irq_timing_decode(irqts->values[i], &ts);
  518. s = idr_find(&irqt_stats, irq);
  519. if (s)
  520. irq_timings_store(irq, this_cpu_ptr(s), ts);
  521. }
  522. /*
  523. * Look in the list of interrupts' statistics, the earliest
  524. * next event.
  525. */
  526. idr_for_each_entry(&irqt_stats, s, i) {
  527. irqs = this_cpu_ptr(s);
  528. ts = __irq_timings_next_event(irqs, i, now);
  529. if (ts <= now)
  530. return now;
  531. if (ts < next_evt)
  532. next_evt = ts;
  533. }
  534. return next_evt;
  535. }
  536. void irq_timings_free(int irq)
  537. {
  538. struct irqt_stat __percpu *s;
  539. s = idr_find(&irqt_stats, irq);
  540. if (s) {
  541. free_percpu(s);
  542. idr_remove(&irqt_stats, irq);
  543. }
  544. }
  545. int irq_timings_alloc(int irq)
  546. {
  547. struct irqt_stat __percpu *s;
  548. int id;
  549. /*
  550. * Some platforms can have the same private interrupt per cpu,
  551. * so this function may be called several times with the
  552. * same interrupt number. Just bail out in case the per cpu
  553. * stat structure is already allocated.
  554. */
  555. s = idr_find(&irqt_stats, irq);
  556. if (s)
  557. return 0;
  558. s = alloc_percpu(*s);
  559. if (!s)
  560. return -ENOMEM;
  561. idr_preload(GFP_KERNEL);
  562. id = idr_alloc(&irqt_stats, s, irq, irq + 1, GFP_NOWAIT);
  563. idr_preload_end();
  564. if (id < 0) {
  565. free_percpu(s);
  566. return id;
  567. }
  568. return 0;
  569. }
  570. #ifdef CONFIG_TEST_IRQ_TIMINGS
  571. struct timings_intervals {
  572. u64 *intervals;
  573. size_t count;
  574. };
  575. /*
  576. * Intervals are given in nanosecond base
  577. */
  578. static u64 intervals0[] __initdata = {
  579. 10000, 50000, 200000, 500000,
  580. 10000, 50000, 200000, 500000,
  581. 10000, 50000, 200000, 500000,
  582. 10000, 50000, 200000, 500000,
  583. 10000, 50000, 200000, 500000,
  584. 10000, 50000, 200000, 500000,
  585. 10000, 50000, 200000, 500000,
  586. 10000, 50000, 200000, 500000,
  587. 10000, 50000, 200000,
  588. };
  589. static u64 intervals1[] __initdata = {
  590. 223947000, 1240000, 1384000, 1386000, 1386000,
  591. 217416000, 1236000, 1384000, 1386000, 1387000,
  592. 214719000, 1241000, 1386000, 1387000, 1384000,
  593. 213696000, 1234000, 1384000, 1386000, 1388000,
  594. 219904000, 1240000, 1385000, 1389000, 1385000,
  595. 212240000, 1240000, 1386000, 1386000, 1386000,
  596. 214415000, 1236000, 1384000, 1386000, 1387000,
  597. 214276000, 1234000,
  598. };
  599. static u64 intervals2[] __initdata = {
  600. 4000, 3000, 5000, 100000,
  601. 3000, 3000, 5000, 117000,
  602. 4000, 4000, 5000, 112000,
  603. 4000, 3000, 4000, 110000,
  604. 3000, 5000, 3000, 117000,
  605. 4000, 4000, 5000, 112000,
  606. 4000, 3000, 4000, 110000,
  607. 3000, 4000, 5000, 112000,
  608. 4000,
  609. };
  610. static u64 intervals3[] __initdata = {
  611. 1385000, 212240000, 1240000,
  612. 1386000, 214415000, 1236000,
  613. 1384000, 214276000, 1234000,
  614. 1386000, 214415000, 1236000,
  615. 1385000, 212240000, 1240000,
  616. 1386000, 214415000, 1236000,
  617. 1384000, 214276000, 1234000,
  618. 1386000, 214415000, 1236000,
  619. 1385000, 212240000, 1240000,
  620. };
  621. static u64 intervals4[] __initdata = {
  622. 10000, 50000, 10000, 50000,
  623. 10000, 50000, 10000, 50000,
  624. 10000, 50000, 10000, 50000,
  625. 10000, 50000, 10000, 50000,
  626. 10000, 50000, 10000, 50000,
  627. 10000, 50000, 10000, 50000,
  628. 10000, 50000, 10000, 50000,
  629. 10000, 50000, 10000, 50000,
  630. 10000,
  631. };
  632. static struct timings_intervals tis[] __initdata = {
  633. { intervals0, ARRAY_SIZE(intervals0) },
  634. { intervals1, ARRAY_SIZE(intervals1) },
  635. { intervals2, ARRAY_SIZE(intervals2) },
  636. { intervals3, ARRAY_SIZE(intervals3) },
  637. { intervals4, ARRAY_SIZE(intervals4) },
  638. };
  639. static int __init irq_timings_test_next_index(struct timings_intervals *ti)
  640. {
  641. int _buffer[IRQ_TIMINGS_SIZE];
  642. int buffer[IRQ_TIMINGS_SIZE];
  643. int index, start, i, count, period_max;
  644. count = ti->count - 1;
  645. period_max = count > (3 * PREDICTION_PERIOD_MAX) ?
  646. PREDICTION_PERIOD_MAX : count / 3;
  647. /*
  648. * Inject all values except the last one which will be used
  649. * to compare with the next index result.
  650. */
  651. pr_debug("index suite: ");
  652. for (i = 0; i < count; i++) {
  653. index = irq_timings_interval_index(ti->intervals[i]);
  654. _buffer[i & IRQ_TIMINGS_MASK] = index;
  655. pr_cont("%d ", index);
  656. }
  657. start = count < IRQ_TIMINGS_SIZE ? 0 :
  658. count & IRQ_TIMINGS_MASK;
  659. count = min_t(int, count, IRQ_TIMINGS_SIZE);
  660. for (i = 0; i < count; i++) {
  661. int index = (start + i) & IRQ_TIMINGS_MASK;
  662. buffer[i] = _buffer[index];
  663. }
  664. index = irq_timings_next_event_index(buffer, count, period_max);
  665. i = irq_timings_interval_index(ti->intervals[ti->count - 1]);
  666. if (index != i) {
  667. pr_err("Expected (%d) and computed (%d) next indexes differ\n",
  668. i, index);
  669. return -EINVAL;
  670. }
  671. return 0;
  672. }
  673. static int __init irq_timings_next_index_selftest(void)
  674. {
  675. int i, ret;
  676. for (i = 0; i < ARRAY_SIZE(tis); i++) {
  677. pr_info("---> Injecting intervals number #%d (count=%zd)\n",
  678. i, tis[i].count);
  679. ret = irq_timings_test_next_index(&tis[i]);
  680. if (ret)
  681. break;
  682. }
  683. return ret;
  684. }
  685. static int __init irq_timings_test_irqs(struct timings_intervals *ti)
  686. {
  687. struct irqt_stat __percpu *s;
  688. struct irqt_stat *irqs;
  689. int i, index, ret, irq = 0xACE5;
  690. ret = irq_timings_alloc(irq);
  691. if (ret) {
  692. pr_err("Failed to allocate irq timings\n");
  693. return ret;
  694. }
  695. s = idr_find(&irqt_stats, irq);
  696. if (!s) {
  697. ret = -EIDRM;
  698. goto out;
  699. }
  700. irqs = this_cpu_ptr(s);
  701. for (i = 0; i < ti->count; i++) {
  702. index = irq_timings_interval_index(ti->intervals[i]);
  703. pr_debug("%d: interval=%llu ema_index=%d\n",
  704. i, ti->intervals[i], index);
  705. __irq_timings_store(irq, irqs, ti->intervals[i]);
  706. if (irqs->circ_timings[i & IRQ_TIMINGS_MASK] != index) {
  707. ret = -EBADSLT;
  708. pr_err("Failed to store in the circular buffer\n");
  709. goto out;
  710. }
  711. }
  712. if (irqs->count != ti->count) {
  713. ret = -ERANGE;
  714. pr_err("Count differs\n");
  715. goto out;
  716. }
  717. ret = 0;
  718. out:
  719. irq_timings_free(irq);
  720. return ret;
  721. }
  722. static int __init irq_timings_irqs_selftest(void)
  723. {
  724. int i, ret;
  725. for (i = 0; i < ARRAY_SIZE(tis); i++) {
  726. pr_info("---> Injecting intervals number #%d (count=%zd)\n",
  727. i, tis[i].count);
  728. ret = irq_timings_test_irqs(&tis[i]);
  729. if (ret)
  730. break;
  731. }
  732. return ret;
  733. }
  734. static int __init irq_timings_test_irqts(struct irq_timings *irqts,
  735. unsigned count)
  736. {
  737. int start = count >= IRQ_TIMINGS_SIZE ? count - IRQ_TIMINGS_SIZE : 0;
  738. int i, irq, oirq = 0xBEEF;
  739. u64 ots = 0xDEAD, ts;
  740. /*
  741. * Fill the circular buffer by using the dedicated function.
  742. */
  743. for (i = 0; i < count; i++) {
  744. pr_debug("%d: index=%d, ts=%llX irq=%X\n",
  745. i, i & IRQ_TIMINGS_MASK, ots + i, oirq + i);
  746. irq_timings_push(ots + i, oirq + i);
  747. }
  748. /*
  749. * Compute the first elements values after the index wrapped
  750. * up or not.
  751. */
  752. ots += start;
  753. oirq += start;
  754. /*
  755. * Test the circular buffer count is correct.
  756. */
  757. pr_debug("---> Checking timings array count (%d) is right\n", count);
  758. if (WARN_ON(irqts->count != count))
  759. return -EINVAL;
  760. /*
  761. * Test the macro allowing to browse all the irqts.
  762. */
  763. pr_debug("---> Checking the for_each_irqts() macro\n");
  764. for_each_irqts(i, irqts) {
  765. irq = irq_timing_decode(irqts->values[i], &ts);
  766. pr_debug("index=%d, ts=%llX / %llX, irq=%X / %X\n",
  767. i, ts, ots, irq, oirq);
  768. if (WARN_ON(ts != ots || irq != oirq))
  769. return -EINVAL;
  770. ots++; oirq++;
  771. }
  772. /*
  773. * The circular buffer should have be flushed when browsed
  774. * with for_each_irqts
  775. */
  776. pr_debug("---> Checking timings array is empty after browsing it\n");
  777. if (WARN_ON(irqts->count))
  778. return -EINVAL;
  779. return 0;
  780. }
  781. static int __init irq_timings_irqts_selftest(void)
  782. {
  783. struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
  784. int i, ret;
  785. /*
  786. * Test the circular buffer with different number of
  787. * elements. The purpose is to test at the limits (empty, half
  788. * full, full, wrapped with the cursor at the boundaries,
  789. * wrapped several times, etc ...
  790. */
  791. int count[] = { 0,
  792. IRQ_TIMINGS_SIZE >> 1,
  793. IRQ_TIMINGS_SIZE,
  794. IRQ_TIMINGS_SIZE + (IRQ_TIMINGS_SIZE >> 1),
  795. 2 * IRQ_TIMINGS_SIZE,
  796. (2 * IRQ_TIMINGS_SIZE) + 3,
  797. };
  798. for (i = 0; i < ARRAY_SIZE(count); i++) {
  799. pr_info("---> Checking the timings with %d/%d values\n",
  800. count[i], IRQ_TIMINGS_SIZE);
  801. ret = irq_timings_test_irqts(irqts, count[i]);
  802. if (ret)
  803. break;
  804. }
  805. return ret;
  806. }
  807. static int __init irq_timings_selftest(void)
  808. {
  809. int ret;
  810. pr_info("------------------- selftest start -----------------\n");
  811. /*
  812. * At this point, we don't except any subsystem to use the irq
  813. * timings but us, so it should not be enabled.
  814. */
  815. if (static_branch_unlikely(&irq_timing_enabled)) {
  816. pr_warn("irq timings already initialized, skipping selftest\n");
  817. return 0;
  818. }
  819. ret = irq_timings_irqts_selftest();
  820. if (ret)
  821. goto out;
  822. ret = irq_timings_irqs_selftest();
  823. if (ret)
  824. goto out;
  825. ret = irq_timings_next_index_selftest();
  826. out:
  827. pr_info("---------- selftest end with %s -----------\n",
  828. ret ? "failure" : "success");
  829. return ret;
  830. }
  831. early_initcall(irq_timings_selftest);
  832. #endif