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
5 #include <linux/kernel.h>
6 #include <linux/percpu.h>
7 #include <linux/slab.h>
8 #include <linux/static_key.h>
9 #include <linux/init.h>
10 #include <linux/interrupt.h>
11 #include <linux/idr.h>
12 #include <linux/irq.h>
13 #include <linux/math64.h>
14 #include <linux/log2.h>
16 #include <trace/events/irq.h>
18 #include "internals.h"
20 DEFINE_STATIC_KEY_FALSE(irq_timing_enabled);
22 DEFINE_PER_CPU(struct irq_timings, irq_timings);
24 static DEFINE_IDR(irqt_stats);
26 void irq_timings_enable(void)
28 static_branch_enable(&irq_timing_enabled);
31 void irq_timings_disable(void)
33 static_branch_disable(&irq_timing_enabled);
37 * The main goal of this algorithm is to predict the next interrupt
38 * occurrence on the current CPU.
40 * Currently, the interrupt timings are stored in a circular array
41 * buffer every time there is an interrupt, as a tuple: the interrupt
42 * number and the associated timestamp when the event occurred <irq,
45 * For every interrupt occurring in a short period of time, we can
46 * measure the elapsed time between the occurrences for the same
47 * interrupt and we end up with a suite of intervals. The experience
48 * showed the interrupts are often coming following a periodic
51 * The objective of the algorithm is to find out this periodic pattern
52 * in a fastest way and use its period to predict the next irq event.
54 * When the next interrupt event is requested, we are in the situation
55 * where the interrupts are disabled and the circular buffer
56 * containing the timings is filled with the events which happened
57 * after the previous next-interrupt-event request.
59 * At this point, we read the circular buffer and we fill the irq
60 * related statistics structure. After this step, the circular array
61 * containing the timings is empty because all the values are
62 * dispatched in their corresponding buffers.
64 * Now for each interrupt, we can predict the next event by using the
65 * suffix array, log interval and exponential moving average
69 * Suffix array is an array of all the suffixes of a string. It is
70 * widely used as a data structure for compression, text search, ...
71 * For instance for the word 'banana', the suffixes will be: 'banana'
72 * 'anana' 'nana' 'ana' 'na' 'a'
74 * Usually, the suffix array is sorted but for our purpose it is
75 * not necessary and won't provide any improvement in the context of
76 * the solved problem where we clearly define the boundaries of the
77 * search by a max period and min period.
79 * The suffix array will build a suite of intervals of different
80 * length and will look for the repetition of each suite. If the suite
81 * is repeating then we have the period because it is the length of
82 * the suite whatever its position in the buffer.
86 * We saw the irq timings allow to compute the interval of the
87 * occurrences for a specific interrupt. We can reasonibly assume the
88 * longer is the interval, the higher is the error for the next event
89 * and we can consider storing those interval values into an array
90 * where each slot in the array correspond to an interval at the power
91 * of 2 of the index. For example, index 12 will contain values
92 * between 2^11 and 2^12.
94 * At the end we have an array of values where at each index defines a
95 * [2^index - 1, 2 ^ index] interval values allowing to store a large
96 * number of values inside a small array.
98 * For example, if we have the value 1123, then we store it at
99 * ilog2(1123) = 10 index value.
101 * Storing those value at the specific index is done by computing an
102 * exponential moving average for this specific slot. For instance,
103 * for values 1800, 1123, 1453, ... fall under the same slot (10) and
104 * the exponential moving average is computed every time a new value
105 * is stored at this slot.
107 * 3. Exponential Moving Average
109 * The EMA is largely used to track a signal for stocks or as a low
110 * pass filter. The magic of the formula, is it is very simple and the
111 * reactivity of the average can be tuned with the factors called
114 * The higher the alphas are, the faster the average respond to the
115 * signal change. In our case, if a slot in the array is a big
116 * interval, we can have numbers with a big difference between
117 * them. The impact of those differences in the average computation
118 * can be tuned by changing the alpha value.
121 * -- The algorithm --
123 * We saw the different processing above, now let's see how they are
126 * For each interrupt:
128 * Compute the index = ilog2(interval)
129 * Compute a new_ema(buffer[index], interval)
130 * Store the index in a circular buffer
132 * Compute the suffix array of the indexes
135 * If the suffix is reverse-found 3 times
140 * However we can not have endless suffix array to be build, it won't
141 * make sense and it will add an extra overhead, so we can restrict
142 * this to a maximum suffix length of 5 and a minimum suffix length of
143 * 2. The experience showed 5 is the majority of the maximum pattern
144 * period found for different devices.
146 * The result is a pattern finding less than 1us for an interrupt.
148 * Example based on real values:
150 * Example 1 : MMC write/read interrupt interval:
152 * 223947, 1240, 1384, 1386, 1386,
153 * 217416, 1236, 1384, 1386, 1387,
154 * 214719, 1241, 1386, 1387, 1384,
155 * 213696, 1234, 1384, 1386, 1388,
156 * 219904, 1240, 1385, 1389, 1385,
157 * 212240, 1240, 1386, 1386, 1386,
158 * 214415, 1236, 1384, 1386, 1387,
159 * 214276, 1234, 1384, 1388, ?
161 * For each element, apply ilog2(value)
172 * Max period of 5, we take the last (max_period * 3) 15 elements as
173 * we can be confident if the pattern repeats itself three times it is
174 * a repeating pattern.
183 * 1) 8, 15, 8, 8, 8 <- max period
186 * 4) 8, 15 <- min period
188 * From there we search the repeating pattern for each suffix.
190 * buffer: 8, 15, 8, 8, 8, 8, 15, 8, 8, 8, 8, 15, 8, 8, 8
191 * | | | | | | | | | | | | | | |
192 * 8, 15, 8, 8, 8 | | | | | | | | | |
193 * 8, 15, 8, 8, 8 | | | | |
196 * When moving the suffix, we found exactly 3 matches.
198 * The first suffix with period 5 is repeating.
200 * The next event is (3 * max_period) % suffix_period
202 * In this example, the result 0, so the next event is suffix[0] => 8
204 * However, 8 is the index in the array of exponential moving average
205 * which was calculated on the fly when storing the values, so the
206 * interval is ema[8] = 1366
246 * buffer: 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4
251 * buffer: 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4
252 * | | | | | | | | | | | | | | |
253 * 0, 0, 4, 0, | | | | | | | | | | |
254 * 0, 0, 4, 0, | | | | | | |
258 * Pattern is found 3 times, the remaining is 1 which results from
259 * (max_period * 3) % suffix_period. This value is the index in the
260 * suffix arrays. The suffix array for a period 4 has the value 4
263 #define EMA_ALPHA_VAL 64
264 #define EMA_ALPHA_SHIFT 7
266 #define PREDICTION_PERIOD_MIN 3
267 #define PREDICTION_PERIOD_MAX 5
268 #define PREDICTION_FACTOR 4
269 #define PREDICTION_MAX 10 /* 2 ^ PREDICTION_MAX useconds */
270 #define PREDICTION_BUFFER_SIZE 16 /* slots for EMAs, hardly more than 16 */
273 * Number of elements in the circular buffer: If it happens it was
274 * flushed before, then the number of elements could be smaller than
275 * IRQ_TIMINGS_SIZE, so the count is used, otherwise the array size is
276 * used as we wrapped. The index begins from zero when we did not
277 * wrap. That could be done in a nicer way with the proper circular
278 * array structure type but with the cost of extra computation in the
279 * interrupt handler hot path. We choose efficiency.
281 #define for_each_irqts(i, irqts) \
282 for (i = irqts->count < IRQ_TIMINGS_SIZE ? \
283 0 : irqts->count & IRQ_TIMINGS_MASK, \
284 irqts->count = min(IRQ_TIMINGS_SIZE, \
286 irqts->count > 0; irqts->count--, \
287 i = (i + 1) & IRQ_TIMINGS_MASK)
291 u64 ema_time[PREDICTION_BUFFER_SIZE];
292 int timings[IRQ_TIMINGS_SIZE];
293 int circ_timings[IRQ_TIMINGS_SIZE];
298 * Exponential moving average computation
300 static u64 irq_timings_ema_new(u64 value, u64 ema_old)
304 if (unlikely(!ema_old))
307 diff = (value - ema_old) * EMA_ALPHA_VAL;
309 * We can use a s64 type variable to be added with the u64
310 * ema_old variable as this one will never have its topmost
311 * bit set, it will be always smaller than 2^63 nanosec
312 * interrupt interval (292 years).
314 return ema_old + (diff >> EMA_ALPHA_SHIFT);
317 static int irq_timings_next_event_index(int *buffer, size_t len, int period_max)
322 * Move the beginning pointer to the end minus the max period x 3.
323 * We are at the point we can begin searching the pattern
325 buffer = &buffer[len - (period_max * 3)];
327 /* Adjust the length to the maximum allowed period x 3 */
328 len = period_max * 3;
331 * The buffer contains the suite of intervals, in a ilog2
332 * basis, we are looking for a repetition. We point the
333 * beginning of the search three times the length of the
334 * period beginning at the end of the buffer. We do that for
337 for (period = period_max; period >= PREDICTION_PERIOD_MIN; period--) {
340 * The first comparison always succeed because the
341 * suffix is deduced from the first n-period bytes of
342 * the buffer and we compare the initial suffix with
343 * itself, so we can skip the first iteration.
346 size_t size = period;
349 * We look if the suite with period 'i' repeat
350 * itself. If it is truncated at the end, as it
351 * repeats we can use the period to find out the next
352 * element with the modulo.
354 while (!memcmp(buffer, &buffer[idx], size * sizeof(int))) {
357 * Move the index in a period basis
362 * If this condition is reached, all previous
363 * memcmp were successful, so the period is
367 return buffer[len % period];
370 * If the remaining elements to compare are
371 * smaller than the period, readjust the size
372 * of the comparison for the last iteration.
374 if (len - idx < period)
382 static u64 __irq_timings_next_event(struct irqt_stat *irqs, int irq, u64 now)
384 int index, i, period_max, count, start, min = INT_MAX;
386 if ((now - irqs->last_ts) >= NSEC_PER_SEC) {
387 irqs->count = irqs->last_ts = 0;
392 * As we want to find three times the repetition, we need a
393 * number of intervals greater or equal to three times the
394 * maximum period, otherwise we truncate the max period.
396 period_max = irqs->count > (3 * PREDICTION_PERIOD_MAX) ?
397 PREDICTION_PERIOD_MAX : irqs->count / 3;
400 * If we don't have enough irq timings for this prediction,
403 if (period_max <= PREDICTION_PERIOD_MIN)
407 * 'count' will depends if the circular buffer wrapped or not
409 count = irqs->count < IRQ_TIMINGS_SIZE ?
410 irqs->count : IRQ_TIMINGS_SIZE;
412 start = irqs->count < IRQ_TIMINGS_SIZE ?
413 0 : (irqs->count & IRQ_TIMINGS_MASK);
416 * Copy the content of the circular buffer into another buffer
417 * in order to linearize the buffer instead of dealing with
418 * wrapping indexes and shifted array which will be prone to
419 * error and extremelly difficult to debug.
421 for (i = 0; i < count; i++) {
422 int index = (start + i) & IRQ_TIMINGS_MASK;
424 irqs->timings[i] = irqs->circ_timings[index];
425 min = min_t(int, irqs->timings[i], min);
428 index = irq_timings_next_event_index(irqs->timings, count, period_max);
430 return irqs->last_ts + irqs->ema_time[min];
432 return irqs->last_ts + irqs->ema_time[index];
435 static __always_inline int irq_timings_interval_index(u64 interval)
438 * The PREDICTION_FACTOR increase the interval size for the
439 * array of exponential average.
441 u64 interval_us = (interval >> 10) / PREDICTION_FACTOR;
443 return likely(interval_us) ? ilog2(interval_us) : 0;
446 static __always_inline void __irq_timings_store(int irq, struct irqt_stat *irqs,
452 * Get the index in the ema table for this interrupt.
454 index = irq_timings_interval_index(interval);
457 * Store the index as an element of the pattern in another
460 irqs->circ_timings[irqs->count & IRQ_TIMINGS_MASK] = index;
462 irqs->ema_time[index] = irq_timings_ema_new(interval,
463 irqs->ema_time[index]);
468 static inline void irq_timings_store(int irq, struct irqt_stat *irqs, u64 ts)
470 u64 old_ts = irqs->last_ts;
474 * The timestamps are absolute time values, we need to compute
475 * the timing interval between two interrupts.
480 * The interval type is u64 in order to deal with the same
481 * type in our computation, that prevent mindfuck issues with
482 * overflow, sign and division.
484 interval = ts - old_ts;
487 * The interrupt triggered more than one second apart, that
488 * ends the sequence as predictible for our purpose. In this
489 * case, assume we have the beginning of a sequence and the
490 * timestamp is the first value. As it is impossible to
491 * predict anything at this point, return.
493 * Note the first timestamp of the sequence will always fall
494 * in this test because the old_ts is zero. That is what we
495 * want as we need another timestamp to compute an interval.
497 if (interval >= NSEC_PER_SEC) {
502 __irq_timings_store(irq, irqs, interval);
506 * irq_timings_next_event - Return when the next event is supposed to arrive
508 * During the last busy cycle, the number of interrupts is incremented
509 * and stored in the irq_timings structure. This information is
512 * - know if the index in the table wrapped up:
514 * If more than the array size interrupts happened during the
515 * last busy/idle cycle, the index wrapped up and we have to
516 * begin with the next element in the array which is the last one
517 * in the sequence, otherwise it is a the index 0.
519 * - have an indication of the interrupts activity on this CPU
522 * The values are 'consumed' after inserting in the statistical model,
523 * thus the count is reinitialized.
525 * The array of values **must** be browsed in the time direction, the
526 * timestamp must increase between an element and the next one.
528 * Returns a nanosec time based estimation of the earliest interrupt,
531 u64 irq_timings_next_event(u64 now)
533 struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
534 struct irqt_stat *irqs;
535 struct irqt_stat __percpu *s;
536 u64 ts, next_evt = U64_MAX;
540 * This function must be called with the local irq disabled in
541 * order to prevent the timings circular buffer to be updated
542 * while we are reading it.
544 lockdep_assert_irqs_disabled();
550 * Number of elements in the circular buffer: If it happens it
551 * was flushed before, then the number of elements could be
552 * smaller than IRQ_TIMINGS_SIZE, so the count is used,
553 * otherwise the array size is used as we wrapped. The index
554 * begins from zero when we did not wrap. That could be done
555 * in a nicer way with the proper circular array structure
556 * type but with the cost of extra computation in the
557 * interrupt handler hot path. We choose efficiency.
559 * Inject measured irq/timestamp to the pattern prediction
560 * model while decrementing the counter because we consume the
561 * data from our circular buffer.
563 for_each_irqts(i, irqts) {
564 irq = irq_timing_decode(irqts->values[i], &ts);
565 s = idr_find(&irqt_stats, irq);
567 irq_timings_store(irq, this_cpu_ptr(s), ts);
571 * Look in the list of interrupts' statistics, the earliest
574 idr_for_each_entry(&irqt_stats, s, i) {
576 irqs = this_cpu_ptr(s);
578 ts = __irq_timings_next_event(irqs, i, now);
589 void irq_timings_free(int irq)
591 struct irqt_stat __percpu *s;
593 s = idr_find(&irqt_stats, irq);
596 idr_remove(&irqt_stats, irq);
600 int irq_timings_alloc(int irq)
602 struct irqt_stat __percpu *s;
606 * Some platforms can have the same private interrupt per cpu,
607 * so this function may be be called several times with the
608 * same interrupt number. Just bail out in case the per cpu
609 * stat structure is already allocated.
611 s = idr_find(&irqt_stats, irq);
615 s = alloc_percpu(*s);
619 idr_preload(GFP_KERNEL);
620 id = idr_alloc(&irqt_stats, s, irq, irq + 1, GFP_NOWAIT);
631 #ifdef CONFIG_TEST_IRQ_TIMINGS
632 static int __init irq_timings_test_irqts(struct irq_timings *irqts,
635 int start = count >= IRQ_TIMINGS_SIZE ? count - IRQ_TIMINGS_SIZE : 0;
636 int i, irq, oirq = 0xBEEF;
637 u64 ots = 0xDEAD, ts;
640 * Fill the circular buffer by using the dedicated function.
642 for (i = 0; i < count; i++) {
643 pr_debug("%d: index=%d, ts=%llX irq=%X\n",
644 i, i & IRQ_TIMINGS_MASK, ots + i, oirq + i);
646 irq_timings_push(ots + i, oirq + i);
650 * Compute the first elements values after the index wrapped
657 * Test the circular buffer count is correct.
659 pr_debug("---> Checking timings array count (%d) is right\n", count);
660 if (WARN_ON(irqts->count != count))
664 * Test the macro allowing to browse all the irqts.
666 pr_debug("---> Checking the for_each_irqts() macro\n");
667 for_each_irqts(i, irqts) {
669 irq = irq_timing_decode(irqts->values[i], &ts);
671 pr_debug("index=%d, ts=%llX / %llX, irq=%X / %X\n",
672 i, ts, ots, irq, oirq);
674 if (WARN_ON(ts != ots || irq != oirq))
681 * The circular buffer should have be flushed when browsed
682 * with for_each_irqts
684 pr_debug("---> Checking timings array is empty after browsing it\n");
685 if (WARN_ON(irqts->count))
691 static int __init irq_timings_irqts_selftest(void)
693 struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
697 * Test the circular buffer with different number of
698 * elements. The purpose is to test at the limits (empty, half
699 * full, full, wrapped with the cursor at the boundaries,
700 * wrapped several times, etc ...
703 IRQ_TIMINGS_SIZE >> 1,
705 IRQ_TIMINGS_SIZE + (IRQ_TIMINGS_SIZE >> 1),
706 2 * IRQ_TIMINGS_SIZE,
707 (2 * IRQ_TIMINGS_SIZE) + 3,
710 for (i = 0; i < ARRAY_SIZE(count); i++) {
712 pr_info("---> Checking the timings with %d/%d values\n",
713 count[i], IRQ_TIMINGS_SIZE);
715 ret = irq_timings_test_irqts(irqts, count[i]);
723 static int __init irq_timings_selftest(void)
727 pr_info("------------------- selftest start -----------------\n");
730 * At this point, we don't except any subsystem to use the irq
731 * timings but us, so it should not be enabled.
733 if (static_branch_unlikely(&irq_timing_enabled)) {
734 pr_warn("irq timings already initialized, skipping selftest\n");
738 ret = irq_timings_irqts_selftest();
740 pr_info("---------- selftest end with %s -----------\n",
741 ret ? "failure" : "success");
745 early_initcall(irq_timings_selftest);