This source file includes following definitions.
- irq_timings_enable
- irq_timings_disable
- irq_timings_ema_new
- irq_timings_next_event_index
- __irq_timings_next_event
- irq_timings_interval_index
- __irq_timings_store
- irq_timings_store
- irq_timings_next_event
- irq_timings_free
- irq_timings_alloc
- irq_timings_test_next_index
- irq_timings_next_index_selftest
- irq_timings_test_irqs
- irq_timings_irqs_selftest
- irq_timings_test_irqts
- irq_timings_irqts_selftest
- irq_timings_selftest
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
20 DEFINE_STATIC_KEY_FALSE(irq_timing_enabled);
21
22 DEFINE_PER_CPU(struct irq_timings, irq_timings);
23
24 static DEFINE_IDR(irqt_stats);
25
26 void irq_timings_enable(void)
27 {
28 static_branch_enable(&irq_timing_enabled);
29 }
30
31 void 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
289 struct 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
300 static 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
317 static 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
382 static 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
435 static __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
446 static __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
457
458
459
460 irqs->circ_timings[irqs->count & IRQ_TIMINGS_MASK] = index;
461
462 irqs->ema_time[index] = irq_timings_ema_new(interval,
463 irqs->ema_time[index]);
464
465 irqs->count++;
466 }
467
468 static inline void irq_timings_store(int irq, struct irqt_stat *irqs, u64 ts)
469 {
470 u64 old_ts = irqs->last_ts;
471 u64 interval;
472
473
474
475
476
477 irqs->last_ts = ts;
478
479
480
481
482
483
484 interval = ts - old_ts;
485
486
487
488
489
490
491
492
493
494
495
496
497 if (interval >= NSEC_PER_SEC) {
498 irqs->count = 0;
499 return;
500 }
501
502 __irq_timings_store(irq, irqs, interval);
503 }
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531 u64 irq_timings_next_event(u64 now)
532 {
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;
537 int i, irq = 0;
538
539
540
541
542
543
544 lockdep_assert_irqs_disabled();
545
546 if (!irqts->count)
547 return next_evt;
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563 for_each_irqts(i, irqts) {
564 irq = irq_timing_decode(irqts->values[i], &ts);
565 s = idr_find(&irqt_stats, irq);
566 if (s)
567 irq_timings_store(irq, this_cpu_ptr(s), ts);
568 }
569
570
571
572
573
574 idr_for_each_entry(&irqt_stats, s, i) {
575
576 irqs = this_cpu_ptr(s);
577
578 ts = __irq_timings_next_event(irqs, i, now);
579 if (ts <= now)
580 return now;
581
582 if (ts < next_evt)
583 next_evt = ts;
584 }
585
586 return next_evt;
587 }
588
589 void irq_timings_free(int irq)
590 {
591 struct irqt_stat __percpu *s;
592
593 s = idr_find(&irqt_stats, irq);
594 if (s) {
595 free_percpu(s);
596 idr_remove(&irqt_stats, irq);
597 }
598 }
599
600 int irq_timings_alloc(int irq)
601 {
602 struct irqt_stat __percpu *s;
603 int id;
604
605
606
607
608
609
610
611 s = idr_find(&irqt_stats, irq);
612 if (s)
613 return 0;
614
615 s = alloc_percpu(*s);
616 if (!s)
617 return -ENOMEM;
618
619 idr_preload(GFP_KERNEL);
620 id = idr_alloc(&irqt_stats, s, irq, irq + 1, GFP_NOWAIT);
621 idr_preload_end();
622
623 if (id < 0) {
624 free_percpu(s);
625 return id;
626 }
627
628 return 0;
629 }
630
631 #ifdef CONFIG_TEST_IRQ_TIMINGS
632 struct timings_intervals {
633 u64 *intervals;
634 size_t count;
635 };
636
637
638
639
640 static u64 intervals0[] __initdata = {
641 10000, 50000, 200000, 500000,
642 10000, 50000, 200000, 500000,
643 10000, 50000, 200000, 500000,
644 10000, 50000, 200000, 500000,
645 10000, 50000, 200000, 500000,
646 10000, 50000, 200000, 500000,
647 10000, 50000, 200000, 500000,
648 10000, 50000, 200000, 500000,
649 10000, 50000, 200000,
650 };
651
652 static u64 intervals1[] __initdata = {
653 223947000, 1240000, 1384000, 1386000, 1386000,
654 217416000, 1236000, 1384000, 1386000, 1387000,
655 214719000, 1241000, 1386000, 1387000, 1384000,
656 213696000, 1234000, 1384000, 1386000, 1388000,
657 219904000, 1240000, 1385000, 1389000, 1385000,
658 212240000, 1240000, 1386000, 1386000, 1386000,
659 214415000, 1236000, 1384000, 1386000, 1387000,
660 214276000, 1234000,
661 };
662
663 static u64 intervals2[] __initdata = {
664 4000, 3000, 5000, 100000,
665 3000, 3000, 5000, 117000,
666 4000, 4000, 5000, 112000,
667 4000, 3000, 4000, 110000,
668 3000, 5000, 3000, 117000,
669 4000, 4000, 5000, 112000,
670 4000, 3000, 4000, 110000,
671 3000, 4000, 5000, 112000,
672 4000,
673 };
674
675 static u64 intervals3[] __initdata = {
676 1385000, 212240000, 1240000,
677 1386000, 214415000, 1236000,
678 1384000, 214276000, 1234000,
679 1386000, 214415000, 1236000,
680 1385000, 212240000, 1240000,
681 1386000, 214415000, 1236000,
682 1384000, 214276000, 1234000,
683 1386000, 214415000, 1236000,
684 1385000, 212240000, 1240000,
685 };
686
687 static u64 intervals4[] __initdata = {
688 10000, 50000, 10000, 50000,
689 10000, 50000, 10000, 50000,
690 10000, 50000, 10000, 50000,
691 10000, 50000, 10000, 50000,
692 10000, 50000, 10000, 50000,
693 10000, 50000, 10000, 50000,
694 10000, 50000, 10000, 50000,
695 10000, 50000, 10000, 50000,
696 10000,
697 };
698
699 static struct timings_intervals tis[] __initdata = {
700 { intervals0, ARRAY_SIZE(intervals0) },
701 { intervals1, ARRAY_SIZE(intervals1) },
702 { intervals2, ARRAY_SIZE(intervals2) },
703 { intervals3, ARRAY_SIZE(intervals3) },
704 { intervals4, ARRAY_SIZE(intervals4) },
705 };
706
707 static int __init irq_timings_test_next_index(struct timings_intervals *ti)
708 {
709 int _buffer[IRQ_TIMINGS_SIZE];
710 int buffer[IRQ_TIMINGS_SIZE];
711 int index, start, i, count, period_max;
712
713 count = ti->count - 1;
714
715 period_max = count > (3 * PREDICTION_PERIOD_MAX) ?
716 PREDICTION_PERIOD_MAX : count / 3;
717
718
719
720
721
722 pr_debug("index suite: ");
723
724 for (i = 0; i < count; i++) {
725 index = irq_timings_interval_index(ti->intervals[i]);
726 _buffer[i & IRQ_TIMINGS_MASK] = index;
727 pr_cont("%d ", index);
728 }
729
730 start = count < IRQ_TIMINGS_SIZE ? 0 :
731 count & IRQ_TIMINGS_MASK;
732
733 count = min_t(int, count, IRQ_TIMINGS_SIZE);
734
735 for (i = 0; i < count; i++) {
736 int index = (start + i) & IRQ_TIMINGS_MASK;
737 buffer[i] = _buffer[index];
738 }
739
740 index = irq_timings_next_event_index(buffer, count, period_max);
741 i = irq_timings_interval_index(ti->intervals[ti->count - 1]);
742
743 if (index != i) {
744 pr_err("Expected (%d) and computed (%d) next indexes differ\n",
745 i, index);
746 return -EINVAL;
747 }
748
749 return 0;
750 }
751
752 static int __init irq_timings_next_index_selftest(void)
753 {
754 int i, ret;
755
756 for (i = 0; i < ARRAY_SIZE(tis); i++) {
757
758 pr_info("---> Injecting intervals number #%d (count=%zd)\n",
759 i, tis[i].count);
760
761 ret = irq_timings_test_next_index(&tis[i]);
762 if (ret)
763 break;
764 }
765
766 return ret;
767 }
768
769 static int __init irq_timings_test_irqs(struct timings_intervals *ti)
770 {
771 struct irqt_stat __percpu *s;
772 struct irqt_stat *irqs;
773 int i, index, ret, irq = 0xACE5;
774
775 ret = irq_timings_alloc(irq);
776 if (ret) {
777 pr_err("Failed to allocate irq timings\n");
778 return ret;
779 }
780
781 s = idr_find(&irqt_stats, irq);
782 if (!s) {
783 ret = -EIDRM;
784 goto out;
785 }
786
787 irqs = this_cpu_ptr(s);
788
789 for (i = 0; i < ti->count; i++) {
790
791 index = irq_timings_interval_index(ti->intervals[i]);
792 pr_debug("%d: interval=%llu ema_index=%d\n",
793 i, ti->intervals[i], index);
794
795 __irq_timings_store(irq, irqs, ti->intervals[i]);
796 if (irqs->circ_timings[i & IRQ_TIMINGS_MASK] != index) {
797 pr_err("Failed to store in the circular buffer\n");
798 goto out;
799 }
800 }
801
802 if (irqs->count != ti->count) {
803 pr_err("Count differs\n");
804 goto out;
805 }
806
807 ret = 0;
808 out:
809 irq_timings_free(irq);
810
811 return ret;
812 }
813
814 static int __init irq_timings_irqs_selftest(void)
815 {
816 int i, ret;
817
818 for (i = 0; i < ARRAY_SIZE(tis); i++) {
819 pr_info("---> Injecting intervals number #%d (count=%zd)\n",
820 i, tis[i].count);
821 ret = irq_timings_test_irqs(&tis[i]);
822 if (ret)
823 break;
824 }
825
826 return ret;
827 }
828
829 static int __init irq_timings_test_irqts(struct irq_timings *irqts,
830 unsigned count)
831 {
832 int start = count >= IRQ_TIMINGS_SIZE ? count - IRQ_TIMINGS_SIZE : 0;
833 int i, irq, oirq = 0xBEEF;
834 u64 ots = 0xDEAD, ts;
835
836
837
838
839 for (i = 0; i < count; i++) {
840 pr_debug("%d: index=%d, ts=%llX irq=%X\n",
841 i, i & IRQ_TIMINGS_MASK, ots + i, oirq + i);
842
843 irq_timings_push(ots + i, oirq + i);
844 }
845
846
847
848
849
850 ots += start;
851 oirq += start;
852
853
854
855
856 pr_debug("---> Checking timings array count (%d) is right\n", count);
857 if (WARN_ON(irqts->count != count))
858 return -EINVAL;
859
860
861
862
863 pr_debug("---> Checking the for_each_irqts() macro\n");
864 for_each_irqts(i, irqts) {
865
866 irq = irq_timing_decode(irqts->values[i], &ts);
867
868 pr_debug("index=%d, ts=%llX / %llX, irq=%X / %X\n",
869 i, ts, ots, irq, oirq);
870
871 if (WARN_ON(ts != ots || irq != oirq))
872 return -EINVAL;
873
874 ots++; oirq++;
875 }
876
877
878
879
880
881 pr_debug("---> Checking timings array is empty after browsing it\n");
882 if (WARN_ON(irqts->count))
883 return -EINVAL;
884
885 return 0;
886 }
887
888 static int __init irq_timings_irqts_selftest(void)
889 {
890 struct irq_timings *irqts = this_cpu_ptr(&irq_timings);
891 int i, ret;
892
893
894
895
896
897
898
899 int count[] = { 0,
900 IRQ_TIMINGS_SIZE >> 1,
901 IRQ_TIMINGS_SIZE,
902 IRQ_TIMINGS_SIZE + (IRQ_TIMINGS_SIZE >> 1),
903 2 * IRQ_TIMINGS_SIZE,
904 (2 * IRQ_TIMINGS_SIZE) + 3,
905 };
906
907 for (i = 0; i < ARRAY_SIZE(count); i++) {
908
909 pr_info("---> Checking the timings with %d/%d values\n",
910 count[i], IRQ_TIMINGS_SIZE);
911
912 ret = irq_timings_test_irqts(irqts, count[i]);
913 if (ret)
914 break;
915 }
916
917 return ret;
918 }
919
920 static int __init irq_timings_selftest(void)
921 {
922 int ret;
923
924 pr_info("------------------- selftest start -----------------\n");
925
926
927
928
929
930 if (static_branch_unlikely(&irq_timing_enabled)) {
931 pr_warn("irq timings already initialized, skipping selftest\n");
932 return 0;
933 }
934
935 ret = irq_timings_irqts_selftest();
936 if (ret)
937 goto out;
938
939 ret = irq_timings_irqs_selftest();
940 if (ret)
941 goto out;
942
943 ret = irq_timings_next_index_selftest();
944 out:
945 pr_info("---------- selftest end with %s -----------\n",
946 ret ? "failure" : "success");
947
948 return ret;
949 }
950 early_initcall(irq_timings_selftest);
951 #endif