1
2
3#define pr_fmt(fmt) "irq_timings: " fmt
4
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>
15
16#include <trace/events/irq.h>
17
18#include "internals.h"
19
20DEFINE_STATIC_KEY_FALSE(irq_timing_enabled);
21
22DEFINE_PER_CPU(struct irq_timings, irq_timings);
23
24static DEFINE_IDR(irqt_stats);
25
26void irq_timings_enable(void)
27{
28 static_branch_enable(&irq_timing_enabled);
29}
30
31void irq_timings_disable(void)
32{
33 static_branch_disable(&irq_timing_enabled);
34}
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263#define EMA_ALPHA_VAL 64
264#define EMA_ALPHA_SHIFT 7
265
266#define PREDICTION_PERIOD_MIN 3
267#define PREDICTION_PERIOD_MAX 5
268#define PREDICTION_FACTOR 4
269#define PREDICTION_MAX 10
270#define PREDICTION_BUFFER_SIZE 16
271
272
273
274
275
276
277
278
279
280
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, \
285 irqts->count); \
286 irqts->count > 0; irqts->count--, \
287 i = (i + 1) & IRQ_TIMINGS_MASK)
288
289struct irqt_stat {
290 u64 last_ts;
291 u64 ema_time[PREDICTION_BUFFER_SIZE];
292 int timings[IRQ_TIMINGS_SIZE];
293 int circ_timings[IRQ_TIMINGS_SIZE];
294 int count;
295};
296
297
298
299
300static u64 irq_timings_ema_new(u64 value, u64 ema_old)
301{
302 s64 diff;
303
304 if (unlikely(!ema_old))
305 return value;
306
307 diff = (value - ema_old) * EMA_ALPHA_VAL;
308
309
310
311
312
313
314 return ema_old + (diff >> EMA_ALPHA_SHIFT);
315}
316
317static int irq_timings_next_event_index(int *buffer, size_t len, int period_max)
318{
319 int period;
320
321
322
323
324
325 buffer = &buffer[len - (period_max * 3)];
326
327
328 len = period_max * 3;
329
330
331
332
333
334
335
336
337 for (period = period_max; period >= PREDICTION_PERIOD_MIN; period--) {
338
339
340
341
342
343
344
345 int idx = period;
346 size_t size = period;
347
348
349
350
351
352
353
354 while (!memcmp(buffer, &buffer[idx], size * sizeof(int))) {
355
356
357
358
359 idx += size;
360
361
362
363
364
365
366 if (idx == len)
367 return buffer[len % period];
368
369
370
371
372
373
374 if (len - idx < period)
375 size = len - idx;
376 }
377 }
378
379 return -1;
380}
381
382static u64 __irq_timings_next_event(struct irqt_stat *irqs, int irq, u64 now)
383{
384 int index, i, period_max, count, start, min = INT_MAX;
385
386 if ((now - irqs->last_ts) >= NSEC_PER_SEC) {
387 irqs->count = irqs->last_ts = 0;
388 return U64_MAX;
389 }
390
391
392
393
394
395
396 period_max = irqs->count > (3 * PREDICTION_PERIOD_MAX) ?
397 PREDICTION_PERIOD_MAX : irqs->count / 3;
398
399
400
401
402
403 if (period_max <= PREDICTION_PERIOD_MIN)
404 return U64_MAX;
405
406
407
408
409 count = irqs->count < IRQ_TIMINGS_SIZE ?
410 irqs->count : IRQ_TIMINGS_SIZE;
411
412 start = irqs->count < IRQ_TIMINGS_SIZE ?
413 0 : (irqs->count & IRQ_TIMINGS_MASK);
414
415
416
417
418
419
420
421 for (i = 0; i < count; i++) {
422 int index = (start + i) & IRQ_TIMINGS_MASK;
423
424 irqs->timings[i] = irqs->circ_timings[index];
425 min = min_t(int, irqs->timings[i], min);
426 }
427
428 index = irq_timings_next_event_index(irqs->timings, count, period_max);
429 if (index < 0)
430 return irqs->last_ts + irqs->ema_time[min];
431
432 return irqs->last_ts + irqs->ema_time[index];
433}
434
435static __always_inline int irq_timings_interval_index(u64 interval)
436{
437
438
439
440
441 u64 interval_us = (interval >> 10) / PREDICTION_FACTOR;
442
443 return likely(interval_us) ? ilog2(interval_us) : 0;
444}
445
446static __always_inline void __irq_timings_store(int irq, struct irqt_stat *irqs,
447 u64 interval)
448{
449 int index;
450
451
452
453
454 index = irq_timings_interval_index(interval);
455
456 if (index > PREDICTION_BUFFER_SIZE - 1) {
457 irqs->count = 0;
458 return;
459 }
460
461
462
463
464
465 irqs->circ_timings[irqs->count & IRQ_TIMINGS_MASK] = index;
466
467 irqs->ema_time[index] = irq_timings_ema_new(interval,
468 irqs->ema_time[index]);
469
470 irqs->count++;
471}
472
473static inline void irq_timings_store(int irq, struct irqt_stat *irqs, u64 ts)
474{
475 u64 old_ts = irqs->last_ts;
476 u64 interval;
477
478
479
480
481
482 irqs->last_ts = ts;
483
484
485
486
487
488
489 interval = ts - old_ts;
490
491
492
493
494
495
496
497
498
499
500
501
502 if (interval >= NSEC_PER_SEC) {
503 irqs->count = 0;
504 return;
505 }
506
507 __irq_timings_store(irq, irqs, interval);
508}
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536u64 irq_timings_next_event(u64 now)
537{
538 struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
539 struct irqt_stat *irqs;
540 struct irqt_stat __percpu *s;
541 u64 ts, next_evt = U64_MAX;
542 int i, irq = 0;
543
544
545
546
547
548
549 lockdep_assert_irqs_disabled();
550
551 if (!irqts->count)
552 return next_evt;
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568 for_each_irqts(i, irqts) {
569 irq = irq_timing_decode(irqts->values[i], &ts);
570 s = idr_find(&irqt_stats, irq);
571 if (s)
572 irq_timings_store(irq, this_cpu_ptr(s), ts);
573 }
574
575
576
577
578
579 idr_for_each_entry(&irqt_stats, s, i) {
580
581 irqs = this_cpu_ptr(s);
582
583 ts = __irq_timings_next_event(irqs, i, now);
584 if (ts <= now)
585 return now;
586
587 if (ts < next_evt)
588 next_evt = ts;
589 }
590
591 return next_evt;
592}
593
594void irq_timings_free(int irq)
595{
596 struct irqt_stat __percpu *s;
597
598 s = idr_find(&irqt_stats, irq);
599 if (s) {
600 free_percpu(s);
601 idr_remove(&irqt_stats, irq);
602 }
603}
604
605int irq_timings_alloc(int irq)
606{
607 struct irqt_stat __percpu *s;
608 int id;
609
610
611
612
613
614
615
616 s = idr_find(&irqt_stats, irq);
617 if (s)
618 return 0;
619
620 s = alloc_percpu(*s);
621 if (!s)
622 return -ENOMEM;
623
624 idr_preload(GFP_KERNEL);
625 id = idr_alloc(&irqt_stats, s, irq, irq + 1, GFP_NOWAIT);
626 idr_preload_end();
627
628 if (id < 0) {
629 free_percpu(s);
630 return id;
631 }
632
633 return 0;
634}
635
636#ifdef CONFIG_TEST_IRQ_TIMINGS
637struct timings_intervals {
638 u64 *intervals;
639 size_t count;
640};
641
642
643
644
645static u64 intervals0[] __initdata = {
646 10000, 50000, 200000, 500000,
647 10000, 50000, 200000, 500000,
648 10000, 50000, 200000, 500000,
649 10000, 50000, 200000, 500000,
650 10000, 50000, 200000, 500000,
651 10000, 50000, 200000, 500000,
652 10000, 50000, 200000, 500000,
653 10000, 50000, 200000, 500000,
654 10000, 50000, 200000,
655};
656
657static u64 intervals1[] __initdata = {
658 223947000, 1240000, 1384000, 1386000, 1386000,
659 217416000, 1236000, 1384000, 1386000, 1387000,
660 214719000, 1241000, 1386000, 1387000, 1384000,
661 213696000, 1234000, 1384000, 1386000, 1388000,
662 219904000, 1240000, 1385000, 1389000, 1385000,
663 212240000, 1240000, 1386000, 1386000, 1386000,
664 214415000, 1236000, 1384000, 1386000, 1387000,
665 214276000, 1234000,
666};
667
668static u64 intervals2[] __initdata = {
669 4000, 3000, 5000, 100000,
670 3000, 3000, 5000, 117000,
671 4000, 4000, 5000, 112000,
672 4000, 3000, 4000, 110000,
673 3000, 5000, 3000, 117000,
674 4000, 4000, 5000, 112000,
675 4000, 3000, 4000, 110000,
676 3000, 4000, 5000, 112000,
677 4000,
678};
679
680static u64 intervals3[] __initdata = {
681 1385000, 212240000, 1240000,
682 1386000, 214415000, 1236000,
683 1384000, 214276000, 1234000,
684 1386000, 214415000, 1236000,
685 1385000, 212240000, 1240000,
686 1386000, 214415000, 1236000,
687 1384000, 214276000, 1234000,
688 1386000, 214415000, 1236000,
689 1385000, 212240000, 1240000,
690};
691
692static u64 intervals4[] __initdata = {
693 10000, 50000, 10000, 50000,
694 10000, 50000, 10000, 50000,
695 10000, 50000, 10000, 50000,
696 10000, 50000, 10000, 50000,
697 10000, 50000, 10000, 50000,
698 10000, 50000, 10000, 50000,
699 10000, 50000, 10000, 50000,
700 10000, 50000, 10000, 50000,
701 10000,
702};
703
704static struct timings_intervals tis[] __initdata = {
705 { intervals0, ARRAY_SIZE(intervals0) },
706 { intervals1, ARRAY_SIZE(intervals1) },
707 { intervals2, ARRAY_SIZE(intervals2) },
708 { intervals3, ARRAY_SIZE(intervals3) },
709 { intervals4, ARRAY_SIZE(intervals4) },
710};
711
712static int __init irq_timings_test_next_index(struct timings_intervals *ti)
713{
714 int _buffer[IRQ_TIMINGS_SIZE];
715 int buffer[IRQ_TIMINGS_SIZE];
716 int index, start, i, count, period_max;
717
718 count = ti->count - 1;
719
720 period_max = count > (3 * PREDICTION_PERIOD_MAX) ?
721 PREDICTION_PERIOD_MAX : count / 3;
722
723
724
725
726
727 pr_debug("index suite: ");
728
729 for (i = 0; i < count; i++) {
730 index = irq_timings_interval_index(ti->intervals[i]);
731 _buffer[i & IRQ_TIMINGS_MASK] = index;
732 pr_cont("%d ", index);
733 }
734
735 start = count < IRQ_TIMINGS_SIZE ? 0 :
736 count & IRQ_TIMINGS_MASK;
737
738 count = min_t(int, count, IRQ_TIMINGS_SIZE);
739
740 for (i = 0; i < count; i++) {
741 int index = (start + i) & IRQ_TIMINGS_MASK;
742 buffer[i] = _buffer[index];
743 }
744
745 index = irq_timings_next_event_index(buffer, count, period_max);
746 i = irq_timings_interval_index(ti->intervals[ti->count - 1]);
747
748 if (index != i) {
749 pr_err("Expected (%d) and computed (%d) next indexes differ\n",
750 i, index);
751 return -EINVAL;
752 }
753
754 return 0;
755}
756
757static int __init irq_timings_next_index_selftest(void)
758{
759 int i, ret;
760
761 for (i = 0; i < ARRAY_SIZE(tis); i++) {
762
763 pr_info("---> Injecting intervals number #%d (count=%zd)\n",
764 i, tis[i].count);
765
766 ret = irq_timings_test_next_index(&tis[i]);
767 if (ret)
768 break;
769 }
770
771 return ret;
772}
773
774static int __init irq_timings_test_irqs(struct timings_intervals *ti)
775{
776 struct irqt_stat __percpu *s;
777 struct irqt_stat *irqs;
778 int i, index, ret, irq = 0xACE5;
779
780 ret = irq_timings_alloc(irq);
781 if (ret) {
782 pr_err("Failed to allocate irq timings\n");
783 return ret;
784 }
785
786 s = idr_find(&irqt_stats, irq);
787 if (!s) {
788 ret = -EIDRM;
789 goto out;
790 }
791
792 irqs = this_cpu_ptr(s);
793
794 for (i = 0; i < ti->count; i++) {
795
796 index = irq_timings_interval_index(ti->intervals[i]);
797 pr_debug("%d: interval=%llu ema_index=%d\n",
798 i, ti->intervals[i], index);
799
800 __irq_timings_store(irq, irqs, ti->intervals[i]);
801 if (irqs->circ_timings[i & IRQ_TIMINGS_MASK] != index) {
802 ret = -EBADSLT;
803 pr_err("Failed to store in the circular buffer\n");
804 goto out;
805 }
806 }
807
808 if (irqs->count != ti->count) {
809 ret = -ERANGE;
810 pr_err("Count differs\n");
811 goto out;
812 }
813
814 ret = 0;
815out:
816 irq_timings_free(irq);
817
818 return ret;
819}
820
821static int __init irq_timings_irqs_selftest(void)
822{
823 int i, ret;
824
825 for (i = 0; i < ARRAY_SIZE(tis); i++) {
826 pr_info("---> Injecting intervals number #%d (count=%zd)\n",
827 i, tis[i].count);
828 ret = irq_timings_test_irqs(&tis[i]);
829 if (ret)
830 break;
831 }
832
833 return ret;
834}
835
836static int __init irq_timings_test_irqts(struct irq_timings *irqts,
837 unsigned count)
838{
839 int start = count >= IRQ_TIMINGS_SIZE ? count - IRQ_TIMINGS_SIZE : 0;
840 int i, irq, oirq = 0xBEEF;
841 u64 ots = 0xDEAD, ts;
842
843
844
845
846 for (i = 0; i < count; i++) {
847 pr_debug("%d: index=%d, ts=%llX irq=%X\n",
848 i, i & IRQ_TIMINGS_MASK, ots + i, oirq + i);
849
850 irq_timings_push(ots + i, oirq + i);
851 }
852
853
854
855
856
857 ots += start;
858 oirq += start;
859
860
861
862
863 pr_debug("---> Checking timings array count (%d) is right\n", count);
864 if (WARN_ON(irqts->count != count))
865 return -EINVAL;
866
867
868
869
870 pr_debug("---> Checking the for_each_irqts() macro\n");
871 for_each_irqts(i, irqts) {
872
873 irq = irq_timing_decode(irqts->values[i], &ts);
874
875 pr_debug("index=%d, ts=%llX / %llX, irq=%X / %X\n",
876 i, ts, ots, irq, oirq);
877
878 if (WARN_ON(ts != ots || irq != oirq))
879 return -EINVAL;
880
881 ots++; oirq++;
882 }
883
884
885
886
887
888 pr_debug("---> Checking timings array is empty after browsing it\n");
889 if (WARN_ON(irqts->count))
890 return -EINVAL;
891
892 return 0;
893}
894
895static int __init irq_timings_irqts_selftest(void)
896{
897 struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
898 int i, ret;
899
900
901
902
903
904
905
906 int count[] = { 0,
907 IRQ_TIMINGS_SIZE >> 1,
908 IRQ_TIMINGS_SIZE,
909 IRQ_TIMINGS_SIZE + (IRQ_TIMINGS_SIZE >> 1),
910 2 * IRQ_TIMINGS_SIZE,
911 (2 * IRQ_TIMINGS_SIZE) + 3,
912 };
913
914 for (i = 0; i < ARRAY_SIZE(count); i++) {
915
916 pr_info("---> Checking the timings with %d/%d values\n",
917 count[i], IRQ_TIMINGS_SIZE);
918
919 ret = irq_timings_test_irqts(irqts, count[i]);
920 if (ret)
921 break;
922 }
923
924 return ret;
925}
926
927static int __init irq_timings_selftest(void)
928{
929 int ret;
930
931 pr_info("------------------- selftest start -----------------\n");
932
933
934
935
936
937 if (static_branch_unlikely(&irq_timing_enabled)) {
938 pr_warn("irq timings already initialized, skipping selftest\n");
939 return 0;
940 }
941
942 ret = irq_timings_irqts_selftest();
943 if (ret)
944 goto out;
945
946 ret = irq_timings_irqs_selftest();
947 if (ret)
948 goto out;
949
950 ret = irq_timings_next_index_selftest();
951out:
952 pr_info("---------- selftest end with %s -----------\n",
953 ret ? "failure" : "success");
954
955 return ret;
956}
957early_initcall(irq_timings_selftest);
958#endif
959