kernel/irq/timings.c

40  * Currently, the interrupt timings are stored in a circular array
41  * buffer every time there is an interrupt, as a tuple: the interrupt
45  * For every interrupt occurring in a short period of time, we can
47  * interrupt and we end up with a suite of intervals. The experience
48  * showed the interrupts are often coming following a periodic
52  * in a fastest way and use its period to predict the next irq event.
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, ...
72  * 'anana' 'nana' 'ana' 'na' 'a'
77  * search by a max period and min period.
79  * The suffix array will build a suite of intervals of different
87  * occurrences for a specific interrupt. We can reasonably assume the
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.
104  * the exponential moving average is computed every time a new value
109  * The EMA is largely used to track a signal for stocks or as a low
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
129  *		Compute a new_ema(buffer[index], interval)
130  *		Store the index in a circular buffer
142  * this to a maximum suffix length of 5 and a minimum suffix length of
146  * The result is a pattern finding less than 1us for an interrupt.
163  *	15, 8, 8, 8, 8,
164  *	15, 8, 8, 8, 8,
165  *	15, 8, 8, 8, 8,
166  *	15, 8, 8, 8, 8,
167  *	15, 8, 8, 8, 8,
168  *	15, 8, 8, 8, 8,
169  *	15, 8, 8, 8, 8,
170  *	15, 8, 8, 8, ?
174  * a repeating pattern.
176  *	             8,
177  *	15, 8, 8, 8, 8,
178  *	15, 8, 8, 8, 8,
179  *	15, 8, 8, 8, ?
183  *  1) 8, 15, 8, 8, 8  <- max period
184  *  2) 8, 15, 8, 8
185  *  3) 8, 15, 8
186  *  4) 8, 15           <- min period
190  * buffer: 8, 15, 8, 8, 8, 8, 15, 8, 8, 8, 8, 15, 8, 8, 8
192  *         8, 15, 8, 8, 8  |   |  |  |  |  |   |  |  |  |
193  *                         8, 15, 8, 8, 8  |   |  |  |  |
194  *                                         8, 15, 8, 8, 8
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
206  * interval is ema[8] = 1366
260  * suffix arrays. The suffix array for a period 4 has the value 4
277  * wrap. That could be done in a nicer way with the proper circular
309 	 * We can use a s64 type variable to be added with the u64  in irq_timings_ema_new()
331 	 * The buffer contains the suite of intervals, in a ilog2  in irq_timings_next_event_index()
332 	 * basis, we are looking for a repetition. We point the  in irq_timings_next_event_index()
357 			 * Move the index in a period basis  in irq_timings_next_event_index()
392 	 * As we want to find three times the repetition, we need a  in __irq_timings_next_event()
494 	 * case, assume we have the beginning of a sequence and the  in irq_timings_store()
533  * Returns a nanosec time based estimation of the earliest interrupt,
560 	 * in a nicer way with the proper circular array structure  in irq_timings_next_event()