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