Lines Matching +full:a +full:- +full:8
1 // SPDX-License-Identifier: GPL-2.0
2 // Copyright (C) 2016, Linaro Ltd - Daniel Lezcano <daniel.lezcano@linaro.org>
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.
57 * after the previous next-interrupt-event request.
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
121 * -- The algorithm --
129 * Compute a new_ema(buffer[index], interval)
130 * Store the index in a circular buffer
135 * If the suffix is reverse-found 3 times
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
282 for (i = irqts->count < IRQ_TIMINGS_SIZE ? \
283 0 : irqts->count & IRQ_TIMINGS_MASK, \
284 irqts->count = min(IRQ_TIMINGS_SIZE, \
285 irqts->count); \
286 irqts->count > 0; irqts->count--, \
307 diff = (value - ema_old) * EMA_ALPHA_VAL; in irq_timings_ema_new()
309 * We can use a s64 type variable to be added with the u64 in irq_timings_ema_new()
325 buffer = &buffer[len - (period_max * 3)]; in irq_timings_next_event_index()
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()
337 for (period = period_max; period >= PREDICTION_PERIOD_MIN; period--) { in irq_timings_next_event_index()
341 * suffix is deduced from the first n-period bytes of in irq_timings_next_event_index()
357 * Move the index in a period basis in irq_timings_next_event_index()
374 if (len - idx < period) in irq_timings_next_event_index()
375 size = len - idx; in irq_timings_next_event_index()
379 return -1; in irq_timings_next_event_index()
386 if ((now - irqs->last_ts) >= NSEC_PER_SEC) { in __irq_timings_next_event()
387 irqs->count = irqs->last_ts = 0; in __irq_timings_next_event()
392 * As we want to find three times the repetition, we need a in __irq_timings_next_event()
396 period_max = irqs->count > (3 * PREDICTION_PERIOD_MAX) ? in __irq_timings_next_event()
397 PREDICTION_PERIOD_MAX : irqs->count / 3; in __irq_timings_next_event()
409 count = irqs->count < IRQ_TIMINGS_SIZE ? in __irq_timings_next_event()
410 irqs->count : IRQ_TIMINGS_SIZE; in __irq_timings_next_event()
412 start = irqs->count < IRQ_TIMINGS_SIZE ? in __irq_timings_next_event()
413 0 : (irqs->count & IRQ_TIMINGS_MASK); in __irq_timings_next_event()
424 irqs->timings[i] = irqs->circ_timings[index]; in __irq_timings_next_event()
425 min = min_t(int, irqs->timings[i], min); in __irq_timings_next_event()
428 index = irq_timings_next_event_index(irqs->timings, count, period_max); in __irq_timings_next_event()
430 return irqs->last_ts + irqs->ema_time[min]; in __irq_timings_next_event()
432 return irqs->last_ts + irqs->ema_time[index]; in __irq_timings_next_event()
456 if (index > PREDICTION_BUFFER_SIZE - 1) { in __irq_timings_store()
457 irqs->count = 0; in __irq_timings_store()
465 irqs->circ_timings[irqs->count & IRQ_TIMINGS_MASK] = index; in __irq_timings_store()
467 irqs->ema_time[index] = irq_timings_ema_new(interval, in __irq_timings_store()
468 irqs->ema_time[index]); in __irq_timings_store()
470 irqs->count++; in __irq_timings_store()
475 u64 old_ts = irqs->last_ts; in irq_timings_store()
482 irqs->last_ts = ts; in irq_timings_store()
489 interval = ts - old_ts; in irq_timings_store()
494 * case, assume we have the beginning of a sequence and the in irq_timings_store()
503 irqs->count = 0; in irq_timings_store()
511 * irq_timings_next_event - Return when the next event is supposed to arrive
517 * - know if the index in the table wrapped up:
524 * - have an indication of the interrupts activity on this CPU
533 * Returns a nanosec time based estimation of the earliest interrupt,
551 if (!irqts->count) in irq_timings_next_event()
560 * in a nicer way with the proper circular array structure in irq_timings_next_event()
569 irq = irq_timing_decode(irqts->values[i], &ts); in irq_timings_next_event()
622 return -ENOMEM; in irq_timings_alloc()
718 count = ti->count - 1; in irq_timings_test_next_index()
730 index = irq_timings_interval_index(ti->intervals[i]); in irq_timings_test_next_index()
746 i = irq_timings_interval_index(ti->intervals[ti->count - 1]); in irq_timings_test_next_index()
751 return -EINVAL; in irq_timings_test_next_index()
763 pr_info("---> Injecting intervals number #%d (count=%zd)\n", in irq_timings_next_index_selftest()
788 ret = -EIDRM; in irq_timings_test_irqs()
794 for (i = 0; i < ti->count; i++) { in irq_timings_test_irqs()
796 index = irq_timings_interval_index(ti->intervals[i]); in irq_timings_test_irqs()
798 i, ti->intervals[i], index); in irq_timings_test_irqs()
800 __irq_timings_store(irq, irqs, ti->intervals[i]); in irq_timings_test_irqs()
801 if (irqs->circ_timings[i & IRQ_TIMINGS_MASK] != index) { in irq_timings_test_irqs()
802 ret = -EBADSLT; in irq_timings_test_irqs()
808 if (irqs->count != ti->count) { in irq_timings_test_irqs()
809 ret = -ERANGE; in irq_timings_test_irqs()
826 pr_info("---> Injecting intervals number #%d (count=%zd)\n", in irq_timings_irqs_selftest()
839 int start = count >= IRQ_TIMINGS_SIZE ? count - IRQ_TIMINGS_SIZE : 0; in irq_timings_test_irqts()
863 pr_debug("---> Checking timings array count (%d) is right\n", count); in irq_timings_test_irqts()
864 if (WARN_ON(irqts->count != count)) in irq_timings_test_irqts()
865 return -EINVAL; in irq_timings_test_irqts()
870 pr_debug("---> Checking the for_each_irqts() macro\n"); in irq_timings_test_irqts()
873 irq = irq_timing_decode(irqts->values[i], &ts); in irq_timings_test_irqts()
879 return -EINVAL; in irq_timings_test_irqts()
888 pr_debug("---> Checking timings array is empty after browsing it\n"); in irq_timings_test_irqts()
889 if (WARN_ON(irqts->count)) in irq_timings_test_irqts()
890 return -EINVAL; in irq_timings_test_irqts()
916 pr_info("---> Checking the timings with %d/%d values\n", in irq_timings_irqts_selftest()
931 pr_info("------------------- selftest start -----------------\n"); in irq_timings_selftest()
952 pr_info("---------- selftest end with %s -----------\n", in irq_timings_selftest()