1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#include <linux/kernel_stat.h>
23#include <linux/export.h>
24#include <linux/interrupt.h>
25#include <linux/percpu.h>
26#include <linux/init.h>
27#include <linux/mm.h>
28#include <linux/swap.h>
29#include <linux/pid_namespace.h>
30#include <linux/notifier.h>
31#include <linux/thread_info.h>
32#include <linux/time.h>
33#include <linux/jiffies.h>
34#include <linux/posix-timers.h>
35#include <linux/cpu.h>
36#include <linux/syscalls.h>
37#include <linux/delay.h>
38#include <linux/tick.h>
39#include <linux/kallsyms.h>
40#include <linux/irq_work.h>
41#include <linux/sched/signal.h>
42#include <linux/sched/sysctl.h>
43#include <linux/sched/nohz.h>
44#include <linux/sched/debug.h>
45#include <linux/slab.h>
46#include <linux/compat.h>
47
48#include <linux/uaccess.h>
49#include <asm/unistd.h>
50#include <asm/div64.h>
51#include <asm/timex.h>
52#include <asm/io.h>
53
54#include "tick-internal.h"
55
56#define CREATE_TRACE_POINTS
57#include <trace/events/timer.h>
58
59__visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
60
61EXPORT_SYMBOL(jiffies_64);
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#define LVL_CLK_SHIFT 3
153#define LVL_CLK_DIV (1UL << LVL_CLK_SHIFT)
154#define LVL_CLK_MASK (LVL_CLK_DIV - 1)
155#define LVL_SHIFT(n) ((n) * LVL_CLK_SHIFT)
156#define LVL_GRAN(n) (1UL << LVL_SHIFT(n))
157
158
159
160
161
162#define LVL_START(n) ((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
163
164
165#define LVL_BITS 6
166#define LVL_SIZE (1UL << LVL_BITS)
167#define LVL_MASK (LVL_SIZE - 1)
168#define LVL_OFFS(n) ((n) * LVL_SIZE)
169
170
171#if HZ > 100
172# define LVL_DEPTH 9
173# else
174# define LVL_DEPTH 8
175#endif
176
177
178#define WHEEL_TIMEOUT_CUTOFF (LVL_START(LVL_DEPTH))
179#define WHEEL_TIMEOUT_MAX (WHEEL_TIMEOUT_CUTOFF - LVL_GRAN(LVL_DEPTH - 1))
180
181
182
183
184
185#define WHEEL_SIZE (LVL_SIZE * LVL_DEPTH)
186
187#ifdef CONFIG_NO_HZ_COMMON
188# define NR_BASES 2
189# define BASE_STD 0
190# define BASE_DEF 1
191#else
192# define NR_BASES 1
193# define BASE_STD 0
194# define BASE_DEF 0
195#endif
196
197struct timer_base {
198 raw_spinlock_t lock;
199 struct timer_list *running_timer;
200 unsigned long clk;
201 unsigned long next_expiry;
202 unsigned int cpu;
203 bool is_idle;
204 bool must_forward_clk;
205 DECLARE_BITMAP(pending_map, WHEEL_SIZE);
206 struct hlist_head vectors[WHEEL_SIZE];
207} ____cacheline_aligned;
208
209static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
210
211#ifdef CONFIG_NO_HZ_COMMON
212
213static DEFINE_STATIC_KEY_FALSE(timers_nohz_active);
214static DEFINE_MUTEX(timer_keys_mutex);
215
216static void timer_update_keys(struct work_struct *work);
217static DECLARE_WORK(timer_update_work, timer_update_keys);
218
219#ifdef CONFIG_SMP
220unsigned int sysctl_timer_migration = 1;
221
222DEFINE_STATIC_KEY_FALSE(timers_migration_enabled);
223
224static void timers_update_migration(void)
225{
226 if (sysctl_timer_migration && tick_nohz_active)
227 static_branch_enable(&timers_migration_enabled);
228 else
229 static_branch_disable(&timers_migration_enabled);
230}
231#else
232static inline void timers_update_migration(void) { }
233#endif
234
235static void timer_update_keys(struct work_struct *work)
236{
237 mutex_lock(&timer_keys_mutex);
238 timers_update_migration();
239 static_branch_enable(&timers_nohz_active);
240 mutex_unlock(&timer_keys_mutex);
241}
242
243void timers_update_nohz(void)
244{
245 schedule_work(&timer_update_work);
246}
247
248int timer_migration_handler(struct ctl_table *table, int write,
249 void __user *buffer, size_t *lenp,
250 loff_t *ppos)
251{
252 int ret;
253
254 mutex_lock(&timer_keys_mutex);
255 ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
256 if (!ret && write)
257 timers_update_migration();
258 mutex_unlock(&timer_keys_mutex);
259 return ret;
260}
261
262static inline bool is_timers_nohz_active(void)
263{
264 return static_branch_unlikely(&timers_nohz_active);
265}
266#else
267static inline bool is_timers_nohz_active(void) { return false; }
268#endif
269
270static unsigned long round_jiffies_common(unsigned long j, int cpu,
271 bool force_up)
272{
273 int rem;
274 unsigned long original = j;
275
276
277
278
279
280
281
282
283
284 j += cpu * 3;
285
286 rem = j % HZ;
287
288
289
290
291
292
293
294
295 if (rem < HZ/4 && !force_up)
296 j = j - rem;
297 else
298 j = j - rem + HZ;
299
300
301 j -= cpu * 3;
302
303
304
305
306
307 return time_is_after_jiffies(j) ? j : original;
308}
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330unsigned long __round_jiffies(unsigned long j, int cpu)
331{
332 return round_jiffies_common(j, cpu, false);
333}
334EXPORT_SYMBOL_GPL(__round_jiffies);
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356unsigned long __round_jiffies_relative(unsigned long j, int cpu)
357{
358 unsigned long j0 = jiffies;
359
360
361 return round_jiffies_common(j + j0, cpu, false) - j0;
362}
363EXPORT_SYMBOL_GPL(__round_jiffies_relative);
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380unsigned long round_jiffies(unsigned long j)
381{
382 return round_jiffies_common(j, raw_smp_processor_id(), false);
383}
384EXPORT_SYMBOL_GPL(round_jiffies);
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401unsigned long round_jiffies_relative(unsigned long j)
402{
403 return __round_jiffies_relative(j, raw_smp_processor_id());
404}
405EXPORT_SYMBOL_GPL(round_jiffies_relative);
406
407
408
409
410
411
412
413
414
415
416
417unsigned long __round_jiffies_up(unsigned long j, int cpu)
418{
419 return round_jiffies_common(j, cpu, true);
420}
421EXPORT_SYMBOL_GPL(__round_jiffies_up);
422
423
424
425
426
427
428
429
430
431
432
433unsigned long __round_jiffies_up_relative(unsigned long j, int cpu)
434{
435 unsigned long j0 = jiffies;
436
437
438 return round_jiffies_common(j + j0, cpu, true) - j0;
439}
440EXPORT_SYMBOL_GPL(__round_jiffies_up_relative);
441
442
443
444
445
446
447
448
449
450
451unsigned long round_jiffies_up(unsigned long j)
452{
453 return round_jiffies_common(j, raw_smp_processor_id(), true);
454}
455EXPORT_SYMBOL_GPL(round_jiffies_up);
456
457
458
459
460
461
462
463
464
465
466unsigned long round_jiffies_up_relative(unsigned long j)
467{
468 return __round_jiffies_up_relative(j, raw_smp_processor_id());
469}
470EXPORT_SYMBOL_GPL(round_jiffies_up_relative);
471
472
473static inline unsigned int timer_get_idx(struct timer_list *timer)
474{
475 return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;
476}
477
478static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
479{
480 timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |
481 idx << TIMER_ARRAYSHIFT;
482}
483
484
485
486
487
488static inline unsigned calc_index(unsigned expires, unsigned lvl)
489{
490 expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
491 return LVL_OFFS(lvl) + (expires & LVL_MASK);
492}
493
494static int calc_wheel_index(unsigned long expires, unsigned long clk)
495{
496 unsigned long delta = expires - clk;
497 unsigned int idx;
498
499 if (delta < LVL_START(1)) {
500 idx = calc_index(expires, 0);
501 } else if (delta < LVL_START(2)) {
502 idx = calc_index(expires, 1);
503 } else if (delta < LVL_START(3)) {
504 idx = calc_index(expires, 2);
505 } else if (delta < LVL_START(4)) {
506 idx = calc_index(expires, 3);
507 } else if (delta < LVL_START(5)) {
508 idx = calc_index(expires, 4);
509 } else if (delta < LVL_START(6)) {
510 idx = calc_index(expires, 5);
511 } else if (delta < LVL_START(7)) {
512 idx = calc_index(expires, 6);
513 } else if (LVL_DEPTH > 8 && delta < LVL_START(8)) {
514 idx = calc_index(expires, 7);
515 } else if ((long) delta < 0) {
516 idx = clk & LVL_MASK;
517 } else {
518
519
520
521
522 if (expires >= WHEEL_TIMEOUT_CUTOFF)
523 expires = WHEEL_TIMEOUT_MAX;
524
525 idx = calc_index(expires, LVL_DEPTH - 1);
526 }
527 return idx;
528}
529
530
531
532
533
534static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
535 unsigned int idx)
536{
537 hlist_add_head(&timer->entry, base->vectors + idx);
538 __set_bit(idx, base->pending_map);
539 timer_set_idx(timer, idx);
540}
541
542static void
543__internal_add_timer(struct timer_base *base, struct timer_list *timer)
544{
545 unsigned int idx;
546
547 idx = calc_wheel_index(timer->expires, base->clk);
548 enqueue_timer(base, timer, idx);
549}
550
551static void
552trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
553{
554 if (!is_timers_nohz_active())
555 return;
556
557
558
559
560
561 if (timer->flags & TIMER_DEFERRABLE) {
562 if (tick_nohz_full_cpu(base->cpu))
563 wake_up_nohz_cpu(base->cpu);
564 return;
565 }
566
567
568
569
570
571
572 if (!base->is_idle)
573 return;
574
575
576 if (time_after_eq(timer->expires, base->next_expiry))
577 return;
578
579
580
581
582
583 base->next_expiry = timer->expires;
584 wake_up_nohz_cpu(base->cpu);
585}
586
587static void
588internal_add_timer(struct timer_base *base, struct timer_list *timer)
589{
590 __internal_add_timer(base, timer);
591 trigger_dyntick_cpu(base, timer);
592}
593
594#ifdef CONFIG_DEBUG_OBJECTS_TIMERS
595
596static struct debug_obj_descr timer_debug_descr;
597
598static void *timer_debug_hint(void *addr)
599{
600 return ((struct timer_list *) addr)->function;
601}
602
603static bool timer_is_static_object(void *addr)
604{
605 struct timer_list *timer = addr;
606
607 return (timer->entry.pprev == NULL &&
608 timer->entry.next == TIMER_ENTRY_STATIC);
609}
610
611
612
613
614
615static bool timer_fixup_init(void *addr, enum debug_obj_state state)
616{
617 struct timer_list *timer = addr;
618
619 switch (state) {
620 case ODEBUG_STATE_ACTIVE:
621 del_timer_sync(timer);
622 debug_object_init(timer, &timer_debug_descr);
623 return true;
624 default:
625 return false;
626 }
627}
628
629
630static void stub_timer(struct timer_list *unused)
631{
632 WARN_ON(1);
633}
634
635
636
637
638
639
640static bool timer_fixup_activate(void *addr, enum debug_obj_state state)
641{
642 struct timer_list *timer = addr;
643
644 switch (state) {
645 case ODEBUG_STATE_NOTAVAILABLE:
646 timer_setup(timer, stub_timer, 0);
647 return true;
648
649 case ODEBUG_STATE_ACTIVE:
650 WARN_ON(1);
651
652 default:
653 return false;
654 }
655}
656
657
658
659
660
661static bool timer_fixup_free(void *addr, enum debug_obj_state state)
662{
663 struct timer_list *timer = addr;
664
665 switch (state) {
666 case ODEBUG_STATE_ACTIVE:
667 del_timer_sync(timer);
668 debug_object_free(timer, &timer_debug_descr);
669 return true;
670 default:
671 return false;
672 }
673}
674
675
676
677
678
679static bool timer_fixup_assert_init(void *addr, enum debug_obj_state state)
680{
681 struct timer_list *timer = addr;
682
683 switch (state) {
684 case ODEBUG_STATE_NOTAVAILABLE:
685 timer_setup(timer, stub_timer, 0);
686 return true;
687 default:
688 return false;
689 }
690}
691
692static struct debug_obj_descr timer_debug_descr = {
693 .name = "timer_list",
694 .debug_hint = timer_debug_hint,
695 .is_static_object = timer_is_static_object,
696 .fixup_init = timer_fixup_init,
697 .fixup_activate = timer_fixup_activate,
698 .fixup_free = timer_fixup_free,
699 .fixup_assert_init = timer_fixup_assert_init,
700};
701
702static inline void debug_timer_init(struct timer_list *timer)
703{
704 debug_object_init(timer, &timer_debug_descr);
705}
706
707static inline void debug_timer_activate(struct timer_list *timer)
708{
709 debug_object_activate(timer, &timer_debug_descr);
710}
711
712static inline void debug_timer_deactivate(struct timer_list *timer)
713{
714 debug_object_deactivate(timer, &timer_debug_descr);
715}
716
717static inline void debug_timer_free(struct timer_list *timer)
718{
719 debug_object_free(timer, &timer_debug_descr);
720}
721
722static inline void debug_timer_assert_init(struct timer_list *timer)
723{
724 debug_object_assert_init(timer, &timer_debug_descr);
725}
726
727static void do_init_timer(struct timer_list *timer,
728 void (*func)(struct timer_list *),
729 unsigned int flags,
730 const char *name, struct lock_class_key *key);
731
732void init_timer_on_stack_key(struct timer_list *timer,
733 void (*func)(struct timer_list *),
734 unsigned int flags,
735 const char *name, struct lock_class_key *key)
736{
737 debug_object_init_on_stack(timer, &timer_debug_descr);
738 do_init_timer(timer, func, flags, name, key);
739}
740EXPORT_SYMBOL_GPL(init_timer_on_stack_key);
741
742void destroy_timer_on_stack(struct timer_list *timer)
743{
744 debug_object_free(timer, &timer_debug_descr);
745}
746EXPORT_SYMBOL_GPL(destroy_timer_on_stack);
747
748#else
749static inline void debug_timer_init(struct timer_list *timer) { }
750static inline void debug_timer_activate(struct timer_list *timer) { }
751static inline void debug_timer_deactivate(struct timer_list *timer) { }
752static inline void debug_timer_assert_init(struct timer_list *timer) { }
753#endif
754
755static inline void debug_init(struct timer_list *timer)
756{
757 debug_timer_init(timer);
758 trace_timer_init(timer);
759}
760
761static inline void
762debug_activate(struct timer_list *timer, unsigned long expires)
763{
764 debug_timer_activate(timer);
765 trace_timer_start(timer, expires, timer->flags);
766}
767
768static inline void debug_deactivate(struct timer_list *timer)
769{
770 debug_timer_deactivate(timer);
771 trace_timer_cancel(timer);
772}
773
774static inline void debug_assert_init(struct timer_list *timer)
775{
776 debug_timer_assert_init(timer);
777}
778
779static void do_init_timer(struct timer_list *timer,
780 void (*func)(struct timer_list *),
781 unsigned int flags,
782 const char *name, struct lock_class_key *key)
783{
784 timer->entry.pprev = NULL;
785 timer->function = func;
786 timer->flags = flags | raw_smp_processor_id();
787 lockdep_init_map(&timer->lockdep_map, name, key, 0);
788}
789
790
791
792
793
794
795
796
797
798
799
800
801
802void init_timer_key(struct timer_list *timer,
803 void (*func)(struct timer_list *), unsigned int flags,
804 const char *name, struct lock_class_key *key)
805{
806 debug_init(timer);
807 do_init_timer(timer, func, flags, name, key);
808}
809EXPORT_SYMBOL(init_timer_key);
810
811static inline void detach_timer(struct timer_list *timer, bool clear_pending)
812{
813 struct hlist_node *entry = &timer->entry;
814
815 debug_deactivate(timer);
816
817 __hlist_del(entry);
818 if (clear_pending)
819 entry->pprev = NULL;
820 entry->next = LIST_POISON2;
821}
822
823static int detach_if_pending(struct timer_list *timer, struct timer_base *base,
824 bool clear_pending)
825{
826 unsigned idx = timer_get_idx(timer);
827
828 if (!timer_pending(timer))
829 return 0;
830
831 if (hlist_is_singular_node(&timer->entry, base->vectors + idx))
832 __clear_bit(idx, base->pending_map);
833
834 detach_timer(timer, clear_pending);
835 return 1;
836}
837
838static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
839{
840 struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_STD], cpu);
841
842
843
844
845
846 if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
847 base = per_cpu_ptr(&timer_bases[BASE_DEF], cpu);
848 return base;
849}
850
851static inline struct timer_base *get_timer_this_cpu_base(u32 tflags)
852{
853 struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
854
855
856
857
858
859 if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
860 base = this_cpu_ptr(&timer_bases[BASE_DEF]);
861 return base;
862}
863
864static inline struct timer_base *get_timer_base(u32 tflags)
865{
866 return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
867}
868
869static inline struct timer_base *
870get_target_base(struct timer_base *base, unsigned tflags)
871{
872#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
873 if (static_branch_likely(&timers_migration_enabled) &&
874 !(tflags & TIMER_PINNED))
875 return get_timer_cpu_base(tflags, get_nohz_timer_target());
876#endif
877 return get_timer_this_cpu_base(tflags);
878}
879
880static inline void forward_timer_base(struct timer_base *base)
881{
882#ifdef CONFIG_NO_HZ_COMMON
883 unsigned long jnow;
884
885
886
887
888
889
890 if (likely(!base->must_forward_clk))
891 return;
892
893 jnow = READ_ONCE(jiffies);
894 base->must_forward_clk = base->is_idle;
895 if ((long)(jnow - base->clk) < 2)
896 return;
897
898
899
900
901
902 if (time_after(base->next_expiry, jnow))
903 base->clk = jnow;
904 else
905 base->clk = base->next_expiry;
906#endif
907}
908
909
910
911
912
913
914
915
916
917
918
919
920
921static struct timer_base *lock_timer_base(struct timer_list *timer,
922 unsigned long *flags)
923 __acquires(timer->base->lock)
924{
925 for (;;) {
926 struct timer_base *base;
927 u32 tf;
928
929
930
931
932
933
934 tf = READ_ONCE(timer->flags);
935
936 if (!(tf & TIMER_MIGRATING)) {
937 base = get_timer_base(tf);
938 raw_spin_lock_irqsave(&base->lock, *flags);
939 if (timer->flags == tf)
940 return base;
941 raw_spin_unlock_irqrestore(&base->lock, *flags);
942 }
943 cpu_relax();
944 }
945}
946
947#define MOD_TIMER_PENDING_ONLY 0x01
948#define MOD_TIMER_REDUCE 0x02
949
950static inline int
951__mod_timer(struct timer_list *timer, unsigned long expires, unsigned int options)
952{
953 struct timer_base *base, *new_base;
954 unsigned int idx = UINT_MAX;
955 unsigned long clk = 0, flags;
956 int ret = 0;
957
958 BUG_ON(!timer->function);
959
960
961
962
963
964
965 if (timer_pending(timer)) {
966
967
968
969
970
971 long diff = timer->expires - expires;
972
973 if (!diff)
974 return 1;
975 if (options & MOD_TIMER_REDUCE && diff <= 0)
976 return 1;
977
978
979
980
981
982
983
984 base = lock_timer_base(timer, &flags);
985 forward_timer_base(base);
986
987 if (timer_pending(timer) && (options & MOD_TIMER_REDUCE) &&
988 time_before_eq(timer->expires, expires)) {
989 ret = 1;
990 goto out_unlock;
991 }
992
993 clk = base->clk;
994 idx = calc_wheel_index(expires, clk);
995
996
997
998
999
1000
1001 if (idx == timer_get_idx(timer)) {
1002 if (!(options & MOD_TIMER_REDUCE))
1003 timer->expires = expires;
1004 else if (time_after(timer->expires, expires))
1005 timer->expires = expires;
1006 ret = 1;
1007 goto out_unlock;
1008 }
1009 } else {
1010 base = lock_timer_base(timer, &flags);
1011 forward_timer_base(base);
1012 }
1013
1014 ret = detach_if_pending(timer, base, false);
1015 if (!ret && (options & MOD_TIMER_PENDING_ONLY))
1016 goto out_unlock;
1017
1018 new_base = get_target_base(base, timer->flags);
1019
1020 if (base != new_base) {
1021
1022
1023
1024
1025
1026
1027
1028 if (likely(base->running_timer != timer)) {
1029
1030 timer->flags |= TIMER_MIGRATING;
1031
1032 raw_spin_unlock(&base->lock);
1033 base = new_base;
1034 raw_spin_lock(&base->lock);
1035 WRITE_ONCE(timer->flags,
1036 (timer->flags & ~TIMER_BASEMASK) | base->cpu);
1037 forward_timer_base(base);
1038 }
1039 }
1040
1041 debug_activate(timer, expires);
1042
1043 timer->expires = expires;
1044
1045
1046
1047
1048
1049
1050
1051 if (idx != UINT_MAX && clk == base->clk) {
1052 enqueue_timer(base, timer, idx);
1053 trigger_dyntick_cpu(base, timer);
1054 } else {
1055 internal_add_timer(base, timer);
1056 }
1057
1058out_unlock:
1059 raw_spin_unlock_irqrestore(&base->lock, flags);
1060
1061 return ret;
1062}
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074int mod_timer_pending(struct timer_list *timer, unsigned long expires)
1075{
1076 return __mod_timer(timer, expires, MOD_TIMER_PENDING_ONLY);
1077}
1078EXPORT_SYMBOL(mod_timer_pending);
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100int mod_timer(struct timer_list *timer, unsigned long expires)
1101{
1102 return __mod_timer(timer, expires, 0);
1103}
1104EXPORT_SYMBOL(mod_timer);
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115int timer_reduce(struct timer_list *timer, unsigned long expires)
1116{
1117 return __mod_timer(timer, expires, MOD_TIMER_REDUCE);
1118}
1119EXPORT_SYMBOL(timer_reduce);
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135void add_timer(struct timer_list *timer)
1136{
1137 BUG_ON(timer_pending(timer));
1138 mod_timer(timer, timer->expires);
1139}
1140EXPORT_SYMBOL(add_timer);
1141
1142
1143
1144
1145
1146
1147
1148
1149void add_timer_on(struct timer_list *timer, int cpu)
1150{
1151 struct timer_base *new_base, *base;
1152 unsigned long flags;
1153
1154 BUG_ON(timer_pending(timer) || !timer->function);
1155
1156 new_base = get_timer_cpu_base(timer->flags, cpu);
1157
1158
1159
1160
1161
1162
1163 base = lock_timer_base(timer, &flags);
1164 if (base != new_base) {
1165 timer->flags |= TIMER_MIGRATING;
1166
1167 raw_spin_unlock(&base->lock);
1168 base = new_base;
1169 raw_spin_lock(&base->lock);
1170 WRITE_ONCE(timer->flags,
1171 (timer->flags & ~TIMER_BASEMASK) | cpu);
1172 }
1173 forward_timer_base(base);
1174
1175 debug_activate(timer, timer->expires);
1176 internal_add_timer(base, timer);
1177 raw_spin_unlock_irqrestore(&base->lock, flags);
1178}
1179EXPORT_SYMBOL_GPL(add_timer_on);
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192int del_timer(struct timer_list *timer)
1193{
1194 struct timer_base *base;
1195 unsigned long flags;
1196 int ret = 0;
1197
1198 debug_assert_init(timer);
1199
1200 if (timer_pending(timer)) {
1201 base = lock_timer_base(timer, &flags);
1202 ret = detach_if_pending(timer, base, true);
1203 raw_spin_unlock_irqrestore(&base->lock, flags);
1204 }
1205
1206 return ret;
1207}
1208EXPORT_SYMBOL(del_timer);
1209
1210
1211
1212
1213
1214
1215
1216
1217int try_to_del_timer_sync(struct timer_list *timer)
1218{
1219 struct timer_base *base;
1220 unsigned long flags;
1221 int ret = -1;
1222
1223 debug_assert_init(timer);
1224
1225 base = lock_timer_base(timer, &flags);
1226
1227 if (base->running_timer != timer)
1228 ret = detach_if_pending(timer, base, true);
1229
1230 raw_spin_unlock_irqrestore(&base->lock, flags);
1231
1232 return ret;
1233}
1234EXPORT_SYMBOL(try_to_del_timer_sync);
1235
1236#ifdef CONFIG_SMP
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273int del_timer_sync(struct timer_list *timer)
1274{
1275#ifdef CONFIG_LOCKDEP
1276 unsigned long flags;
1277
1278
1279
1280
1281
1282 local_irq_save(flags);
1283 lock_map_acquire(&timer->lockdep_map);
1284 lock_map_release(&timer->lockdep_map);
1285 local_irq_restore(flags);
1286#endif
1287
1288
1289
1290
1291 WARN_ON(in_irq() && !(timer->flags & TIMER_IRQSAFE));
1292 for (;;) {
1293 int ret = try_to_del_timer_sync(timer);
1294 if (ret >= 0)
1295 return ret;
1296 cpu_relax();
1297 }
1298}
1299EXPORT_SYMBOL(del_timer_sync);
1300#endif
1301
1302static void call_timer_fn(struct timer_list *timer, void (*fn)(struct timer_list *))
1303{
1304 int count = preempt_count();
1305
1306#ifdef CONFIG_LOCKDEP
1307
1308
1309
1310
1311
1312
1313
1314 struct lockdep_map lockdep_map;
1315
1316 lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
1317#endif
1318
1319
1320
1321
1322
1323 lock_map_acquire(&lockdep_map);
1324
1325 trace_timer_expire_entry(timer);
1326 fn(timer);
1327 trace_timer_expire_exit(timer);
1328
1329 lock_map_release(&lockdep_map);
1330
1331 if (count != preempt_count()) {
1332 WARN_ONCE(1, "timer: %pF preempt leak: %08x -> %08x\n",
1333 fn, count, preempt_count());
1334
1335
1336
1337
1338
1339
1340 preempt_count_set(count);
1341 }
1342}
1343
1344static void expire_timers(struct timer_base *base, struct hlist_head *head)
1345{
1346 while (!hlist_empty(head)) {
1347 struct timer_list *timer;
1348 void (*fn)(struct timer_list *);
1349
1350 timer = hlist_entry(head->first, struct timer_list, entry);
1351
1352 base->running_timer = timer;
1353 detach_timer(timer, true);
1354
1355 fn = timer->function;
1356
1357 if (timer->flags & TIMER_IRQSAFE) {
1358 raw_spin_unlock(&base->lock);
1359 call_timer_fn(timer, fn);
1360 raw_spin_lock(&base->lock);
1361 } else {
1362 raw_spin_unlock_irq(&base->lock);
1363 call_timer_fn(timer, fn);
1364 raw_spin_lock_irq(&base->lock);
1365 }
1366 }
1367}
1368
1369static int __collect_expired_timers(struct timer_base *base,
1370 struct hlist_head *heads)
1371{
1372 unsigned long clk = base->clk;
1373 struct hlist_head *vec;
1374 int i, levels = 0;
1375 unsigned int idx;
1376
1377 for (i = 0; i < LVL_DEPTH; i++) {
1378 idx = (clk & LVL_MASK) + i * LVL_SIZE;
1379
1380 if (__test_and_clear_bit(idx, base->pending_map)) {
1381 vec = base->vectors + idx;
1382 hlist_move_list(vec, heads++);
1383 levels++;
1384 }
1385
1386 if (clk & LVL_CLK_MASK)
1387 break;
1388
1389 clk >>= LVL_CLK_SHIFT;
1390 }
1391 return levels;
1392}
1393
1394#ifdef CONFIG_NO_HZ_COMMON
1395
1396
1397
1398
1399
1400static int next_pending_bucket(struct timer_base *base, unsigned offset,
1401 unsigned clk)
1402{
1403 unsigned pos, start = offset + clk;
1404 unsigned end = offset + LVL_SIZE;
1405
1406 pos = find_next_bit(base->pending_map, end, start);
1407 if (pos < end)
1408 return pos - start;
1409
1410 pos = find_next_bit(base->pending_map, start, offset);
1411 return pos < start ? pos + LVL_SIZE - start : -1;
1412}
1413
1414
1415
1416
1417
1418static unsigned long __next_timer_interrupt(struct timer_base *base)
1419{
1420 unsigned long clk, next, adj;
1421 unsigned lvl, offset = 0;
1422
1423 next = base->clk + NEXT_TIMER_MAX_DELTA;
1424 clk = base->clk;
1425 for (lvl = 0; lvl < LVL_DEPTH; lvl++, offset += LVL_SIZE) {
1426 int pos = next_pending_bucket(base, offset, clk & LVL_MASK);
1427
1428 if (pos >= 0) {
1429 unsigned long tmp = clk + (unsigned long) pos;
1430
1431 tmp <<= LVL_SHIFT(lvl);
1432 if (time_before(tmp, next))
1433 next = tmp;
1434 }
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471 adj = clk & LVL_CLK_MASK ? 1 : 0;
1472 clk >>= LVL_CLK_SHIFT;
1473 clk += adj;
1474 }
1475 return next;
1476}
1477
1478
1479
1480
1481
1482static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
1483{
1484 u64 nextevt = hrtimer_get_next_event();
1485
1486
1487
1488
1489
1490 if (expires <= nextevt)
1491 return expires;
1492
1493
1494
1495
1496
1497 if (nextevt <= basem)
1498 return basem;
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508 return DIV_ROUND_UP_ULL(nextevt, TICK_NSEC) * TICK_NSEC;
1509}
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
1520{
1521 struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
1522 u64 expires = KTIME_MAX;
1523 unsigned long nextevt;
1524 bool is_max_delta;
1525
1526
1527
1528
1529
1530 if (cpu_is_offline(smp_processor_id()))
1531 return expires;
1532
1533 raw_spin_lock(&base->lock);
1534 nextevt = __next_timer_interrupt(base);
1535 is_max_delta = (nextevt == base->clk + NEXT_TIMER_MAX_DELTA);
1536 base->next_expiry = nextevt;
1537
1538
1539
1540
1541
1542 if (time_after(basej, base->clk)) {
1543 if (time_after(nextevt, basej))
1544 base->clk = basej;
1545 else if (time_after(nextevt, base->clk))
1546 base->clk = nextevt;
1547 }
1548
1549 if (time_before_eq(nextevt, basej)) {
1550 expires = basem;
1551 base->is_idle = false;
1552 } else {
1553 if (!is_max_delta)
1554 expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
1555
1556
1557
1558
1559
1560
1561
1562 if ((expires - basem) > TICK_NSEC) {
1563 base->must_forward_clk = true;
1564 base->is_idle = true;
1565 }
1566 }
1567 raw_spin_unlock(&base->lock);
1568
1569 return cmp_next_hrtimer_event(basem, expires);
1570}
1571
1572
1573
1574
1575
1576
1577void timer_clear_idle(void)
1578{
1579 struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
1580
1581
1582
1583
1584
1585
1586
1587 base->is_idle = false;
1588}
1589
1590static int collect_expired_timers(struct timer_base *base,
1591 struct hlist_head *heads)
1592{
1593
1594
1595
1596
1597
1598 if ((long)(jiffies - base->clk) > 2) {
1599 unsigned long next = __next_timer_interrupt(base);
1600
1601
1602
1603
1604
1605 if (time_after(next, jiffies)) {
1606
1607
1608
1609
1610 base->clk = jiffies;
1611 return 0;
1612 }
1613 base->clk = next;
1614 }
1615 return __collect_expired_timers(base, heads);
1616}
1617#else
1618static inline int collect_expired_timers(struct timer_base *base,
1619 struct hlist_head *heads)
1620{
1621 return __collect_expired_timers(base, heads);
1622}
1623#endif
1624
1625
1626
1627
1628
1629void update_process_times(int user_tick)
1630{
1631 struct task_struct *p = current;
1632
1633
1634 account_process_tick(p, user_tick);
1635 run_local_timers();
1636 rcu_check_callbacks(user_tick);
1637#ifdef CONFIG_IRQ_WORK
1638 if (in_irq())
1639 irq_work_tick();
1640#endif
1641 scheduler_tick();
1642 if (IS_ENABLED(CONFIG_POSIX_TIMERS))
1643 run_posix_cpu_timers(p);
1644}
1645
1646
1647
1648
1649
1650static inline void __run_timers(struct timer_base *base)
1651{
1652 struct hlist_head heads[LVL_DEPTH];
1653 int levels;
1654
1655 if (!time_after_eq(jiffies, base->clk))
1656 return;
1657
1658 raw_spin_lock_irq(&base->lock);
1659
1660 while (time_after_eq(jiffies, base->clk)) {
1661
1662 levels = collect_expired_timers(base, heads);
1663 base->clk++;
1664
1665 while (levels--)
1666 expire_timers(base, heads + levels);
1667 }
1668 base->running_timer = NULL;
1669 raw_spin_unlock_irq(&base->lock);
1670}
1671
1672
1673
1674
1675static __latent_entropy void run_timer_softirq(struct softirq_action *h)
1676{
1677 struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690 base->must_forward_clk = false;
1691
1692 __run_timers(base);
1693 if (IS_ENABLED(CONFIG_NO_HZ_COMMON))
1694 __run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
1695}
1696
1697
1698
1699
1700void run_local_timers(void)
1701{
1702 struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
1703
1704 hrtimer_run_queues();
1705
1706 if (time_before(jiffies, base->clk)) {
1707 if (!IS_ENABLED(CONFIG_NO_HZ_COMMON))
1708 return;
1709
1710 base++;
1711 if (time_before(jiffies, base->clk))
1712 return;
1713 }
1714 raise_softirq(TIMER_SOFTIRQ);
1715}
1716
1717
1718
1719
1720
1721struct process_timer {
1722 struct timer_list timer;
1723 struct task_struct *task;
1724};
1725
1726static void process_timeout(struct timer_list *t)
1727{
1728 struct process_timer *timeout = from_timer(timeout, t, timer);
1729
1730 wake_up_process(timeout->task);
1731}
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762signed long __sched schedule_timeout(signed long timeout)
1763{
1764 struct process_timer timer;
1765 unsigned long expire;
1766
1767 switch (timeout)
1768 {
1769 case MAX_SCHEDULE_TIMEOUT:
1770
1771
1772
1773
1774
1775
1776
1777 schedule();
1778 goto out;
1779 default:
1780
1781
1782
1783
1784
1785
1786
1787 if (timeout < 0) {
1788 printk(KERN_ERR "schedule_timeout: wrong timeout "
1789 "value %lx\n", timeout);
1790 dump_stack();
1791 current->state = TASK_RUNNING;
1792 goto out;
1793 }
1794 }
1795
1796 expire = timeout + jiffies;
1797
1798 timer.task = current;
1799 timer_setup_on_stack(&timer.timer, process_timeout, 0);
1800 __mod_timer(&timer.timer, expire, 0);
1801 schedule();
1802 del_singleshot_timer_sync(&timer.timer);
1803
1804
1805 destroy_timer_on_stack(&timer.timer);
1806
1807 timeout = expire - jiffies;
1808
1809 out:
1810 return timeout < 0 ? 0 : timeout;
1811}
1812EXPORT_SYMBOL(schedule_timeout);
1813
1814
1815
1816
1817
1818signed long __sched schedule_timeout_interruptible(signed long timeout)
1819{
1820 __set_current_state(TASK_INTERRUPTIBLE);
1821 return schedule_timeout(timeout);
1822}
1823EXPORT_SYMBOL(schedule_timeout_interruptible);
1824
1825signed long __sched schedule_timeout_killable(signed long timeout)
1826{
1827 __set_current_state(TASK_KILLABLE);
1828 return schedule_timeout(timeout);
1829}
1830EXPORT_SYMBOL(schedule_timeout_killable);
1831
1832signed long __sched schedule_timeout_uninterruptible(signed long timeout)
1833{
1834 __set_current_state(TASK_UNINTERRUPTIBLE);
1835 return schedule_timeout(timeout);
1836}
1837EXPORT_SYMBOL(schedule_timeout_uninterruptible);
1838
1839
1840
1841
1842
1843signed long __sched schedule_timeout_idle(signed long timeout)
1844{
1845 __set_current_state(TASK_IDLE);
1846 return schedule_timeout(timeout);
1847}
1848EXPORT_SYMBOL(schedule_timeout_idle);
1849
1850#ifdef CONFIG_HOTPLUG_CPU
1851static void migrate_timer_list(struct timer_base *new_base, struct hlist_head *head)
1852{
1853 struct timer_list *timer;
1854 int cpu = new_base->cpu;
1855
1856 while (!hlist_empty(head)) {
1857 timer = hlist_entry(head->first, struct timer_list, entry);
1858 detach_timer(timer, false);
1859 timer->flags = (timer->flags & ~TIMER_BASEMASK) | cpu;
1860 internal_add_timer(new_base, timer);
1861 }
1862}
1863
1864int timers_prepare_cpu(unsigned int cpu)
1865{
1866 struct timer_base *base;
1867 int b;
1868
1869 for (b = 0; b < NR_BASES; b++) {
1870 base = per_cpu_ptr(&timer_bases[b], cpu);
1871 base->clk = jiffies;
1872 base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
1873 base->is_idle = false;
1874 base->must_forward_clk = true;
1875 }
1876 return 0;
1877}
1878
1879int timers_dead_cpu(unsigned int cpu)
1880{
1881 struct timer_base *old_base;
1882 struct timer_base *new_base;
1883 int b, i;
1884
1885 BUG_ON(cpu_online(cpu));
1886
1887 for (b = 0; b < NR_BASES; b++) {
1888 old_base = per_cpu_ptr(&timer_bases[b], cpu);
1889 new_base = get_cpu_ptr(&timer_bases[b]);
1890
1891
1892
1893
1894 raw_spin_lock_irq(&new_base->lock);
1895 raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
1896
1897
1898
1899
1900
1901 forward_timer_base(new_base);
1902
1903 BUG_ON(old_base->running_timer);
1904
1905 for (i = 0; i < WHEEL_SIZE; i++)
1906 migrate_timer_list(new_base, old_base->vectors + i);
1907
1908 raw_spin_unlock(&old_base->lock);
1909 raw_spin_unlock_irq(&new_base->lock);
1910 put_cpu_ptr(&timer_bases);
1911 }
1912 return 0;
1913}
1914
1915#endif
1916
1917static void __init init_timer_cpu(int cpu)
1918{
1919 struct timer_base *base;
1920 int i;
1921
1922 for (i = 0; i < NR_BASES; i++) {
1923 base = per_cpu_ptr(&timer_bases[i], cpu);
1924 base->cpu = cpu;
1925 raw_spin_lock_init(&base->lock);
1926 base->clk = jiffies;
1927 }
1928}
1929
1930static void __init init_timer_cpus(void)
1931{
1932 int cpu;
1933
1934 for_each_possible_cpu(cpu)
1935 init_timer_cpu(cpu);
1936}
1937
1938void __init init_timers(void)
1939{
1940 init_timer_cpus();
1941 open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
1942}
1943
1944
1945
1946
1947
1948void msleep(unsigned int msecs)
1949{
1950 unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1951
1952 while (timeout)
1953 timeout = schedule_timeout_uninterruptible(timeout);
1954}
1955
1956EXPORT_SYMBOL(msleep);
1957
1958
1959
1960
1961
1962unsigned long msleep_interruptible(unsigned int msecs)
1963{
1964 unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1965
1966 while (timeout && !signal_pending(current))
1967 timeout = schedule_timeout_interruptible(timeout);
1968 return jiffies_to_msecs(timeout);
1969}
1970
1971EXPORT_SYMBOL(msleep_interruptible);
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984void __sched usleep_range(unsigned long min, unsigned long max)
1985{
1986 ktime_t exp = ktime_add_us(ktime_get(), min);
1987 u64 delta = (u64)(max - min) * NSEC_PER_USEC;
1988
1989 for (;;) {
1990 __set_current_state(TASK_UNINTERRUPTIBLE);
1991
1992 if (!schedule_hrtimeout_range(&exp, delta, HRTIMER_MODE_ABS))
1993 break;
1994 }
1995}
1996EXPORT_SYMBOL(usleep_range);
1997