16  *  2000-10-05  Implemented scalable SMP per-CPU timer handling.
57 #include <trace/events/timer.h>
64  * The timer wheel has LVL_DEPTH array levels. Each level provides an array of
71  * The array level of a newly armed timer depends on the relative expiry
75  * Contrary to the original timer wheel implementation, which aims for 'exact'
77  * the timers into the lower array levels. The previous 'classic' timer wheel
82  * This is an optimization of the original timer wheel implementation for the
83  * majority of the timer wheel use cases: timeouts. The vast majority of
295 	 * due to delays of the timer irq, long irq off times etc etc) then  in round_jiffies_common()
478 static inline unsigned int timer_get_idx(struct timer_list *timer)  in timer_get_idx()  argument
480 	return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;  in timer_get_idx()
483 static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)  in timer_set_idx()  argument
485 	timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |  in timer_set_idx()
498 	 * The timer wheel has to guarantee that a timer does not fire  in calc_index()
500 	 * - Timer is armed at the edge of a tick  in calc_index()
549 trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)  in trigger_dyntick_cpu()  argument
558 	if (timer->flags & TIMER_DEFERRABLE) {  in trigger_dyntick_cpu()
566 	 * timer is not deferrable. If the other CPU is on the way to idle  in trigger_dyntick_cpu()
574  * Enqueue the timer into the hash bucket, mark it pending in
575  * the bitmap, store the index in the timer flags then wake up
578 static void enqueue_timer(struct timer_base *base, struct timer_list *timer,  in enqueue_timer()  argument
582 	hlist_add_head(&timer->entry, base->vectors + idx);  in enqueue_timer()
584 	timer_set_idx(timer, idx);  in enqueue_timer()
586 	trace_timer_start(timer, timer->expires, timer->flags);  in enqueue_timer()
589 	 * Check whether this is the new first expiring timer. The  in enqueue_timer()
590 	 * effective expiry time of the timer is required here  in enqueue_timer()
591 	 * (bucket_expiry) instead of timer->expires.  in enqueue_timer()
601 		trigger_dyntick_cpu(base, timer);  in enqueue_timer()
605 static void internal_add_timer(struct timer_base *base, struct timer_list *timer)  in internal_add_timer()  argument
610 	idx = calc_wheel_index(timer->expires, base->clk, &bucket_expiry);  in internal_add_timer()
611 	enqueue_timer(base, timer, idx, bucket_expiry);  in internal_add_timer()
625 	struct timer_list *timer = addr;  in timer_is_static_object()  local
627 	return (timer->entry.pprev == NULL &&  in timer_is_static_object()
628 		timer->entry.next == TIMER_ENTRY_STATIC);  in timer_is_static_object()
637 	struct timer_list *timer = addr;  in timer_fixup_init()  local
641 		del_timer_sync(timer);  in timer_fixup_init()
642 		debug_object_init(timer, &timer_debug_descr);  in timer_fixup_init()
649 /* Stub timer callback for improperly used timers. */
662 	struct timer_list *timer = addr;  in timer_fixup_activate()  local
666 		timer_setup(timer, stub_timer, 0);  in timer_fixup_activate()
683 	struct timer_list *timer = addr;  in timer_fixup_free()  local
687 		del_timer_sync(timer);  in timer_fixup_free()
688 		debug_object_free(timer, &timer_debug_descr);  in timer_fixup_free()
701 	struct timer_list *timer = addr;  in timer_fixup_assert_init()  local
705 		timer_setup(timer, stub_timer, 0);  in timer_fixup_assert_init()
722 static inline void debug_timer_init(struct timer_list *timer)  in debug_timer_init()  argument
724 	debug_object_init(timer, &timer_debug_descr);  in debug_timer_init()
727 static inline void debug_timer_activate(struct timer_list *timer)  in debug_timer_activate()  argument
729 	debug_object_activate(timer, &timer_debug_descr);  in debug_timer_activate()
732 static inline void debug_timer_deactivate(struct timer_list *timer)  in debug_timer_deactivate()  argument
734 	debug_object_deactivate(timer, &timer_debug_descr);  in debug_timer_deactivate()
737 static inline void debug_timer_assert_init(struct timer_list *timer)  in debug_timer_assert_init()  argument
739 	debug_object_assert_init(timer, &timer_debug_descr);  in debug_timer_assert_init()
742 static void do_init_timer(struct timer_list *timer,
747 void init_timer_on_stack_key(struct timer_list *timer,  in init_timer_on_stack_key()  argument
752 	debug_object_init_on_stack(timer, &timer_debug_descr);  in init_timer_on_stack_key()
753 	do_init_timer(timer, func, flags, name, key);  in init_timer_on_stack_key()
757 void destroy_timer_on_stack(struct timer_list *timer)  in destroy_timer_on_stack()  argument
759 	debug_object_free(timer, &timer_debug_descr);  in destroy_timer_on_stack()
764 static inline void debug_timer_init(struct timer_list *timer) { }  in debug_timer_init()  argument
765 static inline void debug_timer_activate(struct timer_list *timer) { }  in debug_timer_activate()  argument
766 static inline void debug_timer_deactivate(struct timer_list *timer) { }  in debug_timer_deactivate()  argument
767 static inline void debug_timer_assert_init(struct timer_list *timer) { }  in debug_timer_assert_init()  argument
770 static inline void debug_init(struct timer_list *timer)  in debug_init()  argument
772 	debug_timer_init(timer);  in debug_init()
773 	trace_timer_init(timer);  in debug_init()
776 static inline void debug_deactivate(struct timer_list *timer)  in debug_deactivate()  argument
778 	debug_timer_deactivate(timer);  in debug_deactivate()
779 	trace_timer_cancel(timer);  in debug_deactivate()
782 static inline void debug_assert_init(struct timer_list *timer)  in debug_assert_init()  argument
784 	debug_timer_assert_init(timer);  in debug_assert_init()
787 static void do_init_timer(struct timer_list *timer,  in do_init_timer()  argument
792 	timer->entry.pprev = NULL;  in do_init_timer()
793 	timer->function = func;  in do_init_timer()
796 	timer->flags = flags | raw_smp_processor_id();  in do_init_timer()
797 	lockdep_init_map(&timer->lockdep_map, name, key, 0);  in do_init_timer()
801  * init_timer_key - initialize a timer
802  * @timer: the timer to be initialized
803  * @func: timer callback function
804  * @flags: timer flags
805  * @name: name of the timer
806  * @key: lockdep class key of the fake lock used for tracking timer
809  * init_timer_key() must be done to a timer prior calling *any* of the
810  * other timer functions.
812 void init_timer_key(struct timer_list *timer,  in init_timer_key()  argument
816 	debug_init(timer);  in init_timer_key()
817 	do_init_timer(timer, func, flags, name, key);  in init_timer_key()
821 static inline void detach_timer(struct timer_list *timer, bool clear_pending)  in detach_timer()  argument
823 	struct hlist_node *entry = &timer->entry;  in detach_timer()
825 	debug_deactivate(timer);  in detach_timer()
833 static int detach_if_pending(struct timer_list *timer, struct timer_base *base,  in detach_if_pending()  argument
836 	unsigned idx = timer_get_idx(timer);  in detach_if_pending()
838 	if (!timer_pending(timer))  in detach_if_pending()
841 	if (hlist_is_singular_node(&timer->entry, base->vectors + idx)) {  in detach_if_pending()
846 	detach_timer(timer, clear_pending);  in detach_if_pending()
855 	 * If the timer is deferrable and NO_HZ_COMMON is set then we need  in get_timer_cpu_base()
868 	 * If the timer is deferrable and NO_HZ_COMMON is set then we need  in get_timer_this_cpu_base()
926  * When a timer is migrating then the TIMER_MIGRATING flag is set and we need
929 static struct timer_base *lock_timer_base(struct timer_list *timer,  in lock_timer_base()  argument
931 	__acquires(timer->base->lock)  in lock_timer_base()
942 		tf = READ_ONCE(timer->flags);  in lock_timer_base()
947 			if (timer->flags == tf)  in lock_timer_base()
960 __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int options)  in __mod_timer()  argument
967 	BUG_ON(!timer->function);  in __mod_timer()
971 	 * the timer is re-modified to have the same timeout or ends up in the  in __mod_timer()
974 	if (!(options & MOD_TIMER_NOTPENDING) && timer_pending(timer)) {  in __mod_timer()
978 		 * timer with this expiry.  in __mod_timer()
980 		long diff = timer->expires - expires;  in __mod_timer()
988 		 * We lock timer base and calculate the bucket index right  in __mod_timer()
989 		 * here. If the timer ends up in the same bucket, then we  in __mod_timer()
993 		base = lock_timer_base(timer, &flags);  in __mod_timer()
996 		if (timer_pending(timer) && (options & MOD_TIMER_REDUCE) &&  in __mod_timer()
997 		    time_before_eq(timer->expires, expires)) {  in __mod_timer()
1007 		 * timer. If it matches set the expiry to the new value so a  in __mod_timer()
1010 		if (idx == timer_get_idx(timer)) {  in __mod_timer()
1012 				timer->expires = expires;  in __mod_timer()
1013 			else if (time_after(timer->expires, expires))  in __mod_timer()
1014 				timer->expires = expires;  in __mod_timer()
1019 		base = lock_timer_base(timer, &flags);  in __mod_timer()
1023 	ret = detach_if_pending(timer, base, false);  in __mod_timer()
1027 	new_base = get_target_base(base, timer->flags);  in __mod_timer()
1031 		 * We are trying to schedule the timer on the new base.  in __mod_timer()
1032 		 * However we can't change timer's base while it is running,  in __mod_timer()
1033 		 * otherwise del_timer_sync() can't detect that the timer's  in __mod_timer()
1035 		 * timer is serialized wrt itself.  in __mod_timer()
1037 		if (likely(base->running_timer != timer)) {  in __mod_timer()
1039 			timer->flags |= TIMER_MIGRATING;  in __mod_timer()
1044 			WRITE_ONCE(timer->flags,  in __mod_timer()
1045 				   (timer->flags & ~TIMER_BASEMASK) | base->cpu);  in __mod_timer()
1050 	debug_timer_activate(timer);  in __mod_timer()
1052 	timer->expires = expires;  in __mod_timer()
1060 		enqueue_timer(base, timer, idx, bucket_expiry);  in __mod_timer()
1062 		internal_add_timer(base, timer);  in __mod_timer()
1071  * mod_timer_pending - modify a pending timer's timeout
1072  * @timer: the pending timer to be modified
1080 int mod_timer_pending(struct timer_list *timer, unsigned long expires)  in mod_timer_pending()  argument
1082 	return __mod_timer(timer, expires, MOD_TIMER_PENDING_ONLY);  in mod_timer_pending()
1087  * mod_timer - modify a timer's timeout
1088  * @timer: the timer to be modified
1092  * active timer (if the timer is inactive it will be activated)
1094  * mod_timer(timer, expires) is equivalent to:
1096  *     del_timer(timer); timer->expires = expires; add_timer(timer);
1099  * same timer, then mod_timer() is the only safe way to modify the timeout,
1100  * since add_timer() cannot modify an already running timer.
1102  * The function returns whether it has modified a pending timer or not.
1103  * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
1104  * active timer returns 1.)
1106 int mod_timer(struct timer_list *timer, unsigned long expires)  in mod_timer()  argument
1108 	return __mod_timer(timer, expires, 0);  in mod_timer()
1113  * timer_reduce - Modify a timer's timeout if it would reduce the timeout
1114  * @timer:	The timer to be modified
1118  * modify a running timer if that would reduce the expiration time (it will
1119  * start a timer that isn't running).
1121 int timer_reduce(struct timer_list *timer, unsigned long expires)  in timer_reduce()  argument
1123 	return __mod_timer(timer, expires, MOD_TIMER_REDUCE);  in timer_reduce()
1128  * add_timer - start a timer
1129  * @timer: the timer to be added
1131  * The kernel will do a ->function(@timer) callback from the
1132  * timer interrupt at the ->expires point in the future. The
1135  * The timer's ->expires, ->function fields must be set prior calling this
1139  * timer tick.
1141 void add_timer(struct timer_list *timer)  in add_timer()  argument
1143 	BUG_ON(timer_pending(timer));  in add_timer()
1144 	__mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);  in add_timer()
1149  * add_timer_on - start a timer on a particular CPU
1150  * @timer: the timer to be added
1155 void add_timer_on(struct timer_list *timer, int cpu)  in add_timer_on()  argument
1160 	BUG_ON(timer_pending(timer) || !timer->function);  in add_timer_on()
1162 	new_base = get_timer_cpu_base(timer->flags, cpu);  in add_timer_on()
1165 	 * If @timer was on a different CPU, it should be migrated with the  in add_timer_on()
1169 	base = lock_timer_base(timer, &flags);  in add_timer_on()
1171 		timer->flags |= TIMER_MIGRATING;  in add_timer_on()
1176 		WRITE_ONCE(timer->flags,  in add_timer_on()
1177 			   (timer->flags & ~TIMER_BASEMASK) | cpu);  in add_timer_on()
1181 	debug_timer_activate(timer);  in add_timer_on()
1182 	internal_add_timer(base, timer);  in add_timer_on()
1188  * del_timer - deactivate a timer.
1189  * @timer: the timer to be deactivated
1191  * del_timer() deactivates a timer - this works on both active and inactive
1194  * The function returns whether it has deactivated a pending timer or not.
1195  * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
1196  * active timer returns 1.)
1198 int del_timer(struct timer_list *timer)  in del_timer()  argument
1204 	debug_assert_init(timer);  in del_timer()
1206 	if (timer_pending(timer)) {  in del_timer()
1207 		base = lock_timer_base(timer, &flags);  in del_timer()
1208 		ret = detach_if_pending(timer, base, true);  in del_timer()
1217  * try_to_del_timer_sync - Try to deactivate a timer
1218  * @timer: timer to delete
1220  * This function tries to deactivate a timer. Upon successful (ret >= 0)
1221  * exit the timer is not queued and the handler is not running on any CPU.
1223 int try_to_del_timer_sync(struct timer_list *timer)  in try_to_del_timer_sync()  argument
1229 	debug_assert_init(timer);  in try_to_del_timer_sync()
1231 	base = lock_timer_base(timer, &flags);  in try_to_del_timer_sync()
1233 	if (base->running_timer != timer)  in try_to_del_timer_sync()
1234 		ret = detach_if_pending(timer, base, true);  in try_to_del_timer_sync()
1262  * timer callback to finish. Drop expiry_lock and reacquire it. That allows
1277  * deletion of a timer failed because the timer callback function was
1282  * delete a timer preempted the softirq thread running the timer callback
1285 static void del_timer_wait_running(struct timer_list *timer)  in del_timer_wait_running()  argument
1289 	tf = READ_ONCE(timer->flags);  in del_timer_wait_running()
1295 		 * which is held by the softirq across the timer  in del_timer_wait_running()
1297 		 * expire the next timer. In theory the timer could already  in del_timer_wait_running()
1312 static inline void del_timer_wait_running(struct timer_list *timer) { }  in del_timer_wait_running()  argument
1317  * del_timer_sync - deactivate a timer and wait for the handler to finish.
1318  * @timer: the timer to be deactivated
1321  * the timer it also makes sure the handler has finished executing on other
1324  * Synchronization rules: Callers must prevent restarting of the timer,
1326  * interrupt contexts unless the timer is an irqsafe one. The caller must
1327  * not hold locks which would prevent completion of the timer's
1328  * handler. The timer's handler must not call add_timer_on(). Upon exit the
1329  * timer is not queued and the handler is not running on any CPU.
1333  *   nothing to do with the timer in question.  Here's why::
1350  * The function returns whether it has deactivated a pending timer or not.
1352 int del_timer_sync(struct timer_list *timer)  in del_timer_sync()  argument
1364 	lock_map_acquire(&timer->lockdep_map);  in del_timer_sync()
1365 	lock_map_release(&timer->lockdep_map);  in del_timer_sync()
1372 	WARN_ON(in_irq() && !(timer->flags & TIMER_IRQSAFE));  in del_timer_sync()
1378 	if (IS_ENABLED(CONFIG_PREEMPT_RT) && !(timer->flags & TIMER_IRQSAFE))  in del_timer_sync()
1382 		ret = try_to_del_timer_sync(timer);  in del_timer_sync()
1385 			del_timer_wait_running(timer);  in del_timer_sync()
1395 static void call_timer_fn(struct timer_list *timer,  in call_timer_fn()  argument
1403 	 * It is permissible to free the timer from inside the  in call_timer_fn()
1407 	 * timer->lockdep_map, make a copy and use that here.  in call_timer_fn()
1411 	lockdep_copy_map(&lockdep_map, &timer->lockdep_map);  in call_timer_fn()
1420 	trace_timer_expire_entry(timer, baseclk);  in call_timer_fn()
1421 	fn(timer);  in call_timer_fn()
1422 	trace_timer_expire_exit(timer);  in call_timer_fn()
1427 		WARN_ONCE(1, "timer: %pS preempt leak: %08x -> %08x\n",  in call_timer_fn()
1449 		struct timer_list *timer;  in expire_timers()  local
1452 		timer = hlist_entry(head->first, struct timer_list, entry);  in expire_timers()
1454 		base->running_timer = timer;  in expire_timers()
1455 		detach_timer(timer, true);  in expire_timers()
1457 		fn = timer->function;  in expire_timers()
1459 		if (timer->flags & TIMER_IRQSAFE) {  in expire_timers()
1461 			call_timer_fn(timer, fn, baseclk);  in expire_timers()
1466 			call_timer_fn(timer, fn, baseclk);  in expire_timers()
1519  * Search the first expiring timer in the various clock levels. Caller must
1596  * Check, if the next hrtimer event is before the next timer wheel
1611 	 * If the next timer is already expired, return the tick base  in cmp_next_hrtimer_event()
1620 	 * make sure that this tick really expires the timer to avoid  in cmp_next_hrtimer_event()
1629  * get_next_timer_interrupt - return the time (clock mono) of the next timer
1634  * timer or KTIME_MAX if no timer is pending.
1643 	 * Pretend that there is no timer pending if the cpu is offline.  in get_next_timer_interrupt()
1674 		 * Also the tick is stopped so any added timer must forward  in get_next_timer_interrupt()
1688  * timer_clear_idle - Clear the idle state of the timer base
1708  * @base: the timer vector to be processed.
1726 		 * timer at this clk is that all matching timers have been  in __run_timers()
1741  * This function runs timers and the timer-tq in bottom half context.
1753  * Called by the local, per-CPU timer interrupt on SMP.
1773  * Called from the timer interrupt handler to charge one tick to the current
1782 	/* Note: this timer irq context must be accounted for as well. */  in update_process_times()
1796  * Since schedule_timeout()'s timer is defined on the stack, it must store
1800 	struct timer_list timer;  member
1806 	struct process_timer *timeout = from_timer(timeout, t, timer);  in process_timeout()
1838  * Returns 0 when the timer has expired otherwise the remaining time in
1844 	struct process_timer timer;  in schedule_timeout()  local
1878 	timer.task = current;  in schedule_timeout()
1879 	timer_setup_on_stack(&timer.timer, process_timeout, 0);  in schedule_timeout()
1880 	__mod_timer(&timer.timer, expire, MOD_TIMER_NOTPENDING);  in schedule_timeout()
1882 	del_singleshot_timer_sync(&timer.timer);  in schedule_timeout()
1884 	/* Remove the timer from the object tracker */  in schedule_timeout()
1885 	destroy_timer_on_stack(&timer.timer);  in schedule_timeout()
1933 	struct timer_list *timer;  in migrate_timer_list()  local
1937 		timer = hlist_entry(head->first, struct timer_list, entry);  in migrate_timer_list()
1938 		detach_timer(timer, false);  in migrate_timer_list()
1939 		timer->flags = (timer->flags & ~TIMER_BASEMASK) | cpu;  in migrate_timer_list()
1940 		internal_add_timer(new_base, timer);  in migrate_timer_list()