Lines Matching +full:container +full:- +full:rules
1 // SPDX-License-Identifier: GPL-2.0
7 * 1997-01-28 Modified by Finn Arne Gangstad to make timers scale better.
9 * 1997-09-10 Updated NTP code according to technical memorandum Jan '96
11 * 1998-12-24 Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
14 * 1999-03-10 Improved NTP compatibility by Ulrich Windl
15 * 2002-05-31 Move sys_sysinfo here and make its locking sane, Robert Love
16 * 2000-10-05 Implemented scalable SMP per-CPU timer handling.
33 #include <linux/posix-timers.h>
54 #include "tick-internal.h"
106 * 0 0 1 ms 0 ms - 63 ms
107 * 1 64 8 ms 64 ms - 511 ms
108 * 2 128 64 ms 512 ms - 4095 ms (512ms - ~4s)
109 * 3 192 512 ms 4096 ms - 32767 ms (~4s - ~32s)
110 * 4 256 4096 ms (~4s) 32768 ms - 262143 ms (~32s - ~4m)
111 * 5 320 32768 ms (~32s) 262144 ms - 2097151 ms (~4m - ~34m)
112 * 6 384 262144 ms (~4m) 2097152 ms - 16777215 ms (~34m - ~4h)
113 * 7 448 2097152 ms (~34m) 16777216 ms - 134217727 ms (~4h - ~1d)
114 * 8 512 16777216 ms (~4h) 134217728 ms - 1073741822 ms (~1d - ~12d)
118 * 0 0 3 ms 0 ms - 210 ms
119 * 1 64 26 ms 213 ms - 1703 ms (213ms - ~1s)
120 * 2 128 213 ms 1706 ms - 13650 ms (~1s - ~13s)
121 * 3 192 1706 ms (~1s) 13653 ms - 109223 ms (~13s - ~1m)
122 * 4 256 13653 ms (~13s) 109226 ms - 873810 ms (~1m - ~14m)
123 * 5 320 109226 ms (~1m) 873813 ms - 6990503 ms (~14m - ~1h)
124 * 6 384 873813 ms (~14m) 6990506 ms - 55924050 ms (~1h - ~15h)
125 * 7 448 6990506 ms (~1h) 55924053 ms - 447392423 ms (~15h - ~5d)
126 * 8 512 55924053 ms (~15h) 447392426 ms - 3579139406 ms (~5d - ~41d)
130 * 0 0 4 ms 0 ms - 255 ms
131 * 1 64 32 ms 256 ms - 2047 ms (256ms - ~2s)
132 * 2 128 256 ms 2048 ms - 16383 ms (~2s - ~16s)
133 * 3 192 2048 ms (~2s) 16384 ms - 131071 ms (~16s - ~2m)
134 * 4 256 16384 ms (~16s) 131072 ms - 1048575 ms (~2m - ~17m)
135 * 5 320 131072 ms (~2m) 1048576 ms - 8388607 ms (~17m - ~2h)
136 * 6 384 1048576 ms (~17m) 8388608 ms - 67108863 ms (~2h - ~18h)
137 * 7 448 8388608 ms (~2h) 67108864 ms - 536870911 ms (~18h - ~6d)
138 * 8 512 67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d)
142 * 0 0 10 ms 0 ms - 630 ms
143 * 1 64 80 ms 640 ms - 5110 ms (640ms - ~5s)
144 * 2 128 640 ms 5120 ms - 40950 ms (~5s - ~40s)
145 * 3 192 5120 ms (~5s) 40960 ms - 327670 ms (~40s - ~5m)
146 * 4 256 40960 ms (~40s) 327680 ms - 2621430 ms (~5m - ~43m)
147 * 5 320 327680 ms (~5m) 2621440 ms - 20971510 ms (~43m - ~5h)
148 * 6 384 2621440 ms (~43m) 20971520 ms - 167772150 ms (~5h - ~1d)
149 * 7 448 20971520 ms (~5h) 167772160 ms - 1342177270 ms (~1d - ~15d)
155 #define LVL_CLK_MASK (LVL_CLK_DIV - 1)
164 #define LVL_START(n) ((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
169 #define LVL_MASK (LVL_SIZE - 1)
181 #define WHEEL_TIMEOUT_MAX (WHEEL_TIMEOUT_CUTOFF - LVL_GRAN(LVL_DEPTH - 1))
206 * struct timer_base - Per CPU timer base (number of base depends on config)
374 j = j - rem;
376 j = j - rem + HZ;
379 j -= cpu * 3;
389 * __round_jiffies_relative - function to round jiffies to a full second
413 return round_jiffies_common(j + j0, cpu, false) - j0;
418 * round_jiffies - function to round jiffies to a full second
439 * round_jiffies_relative - function to round jiffies to a full second
460 * __round_jiffies_up_relative - function to round jiffies up to a full second
474 return round_jiffies_common(j + j0, cpu, true) - j0;
479 * round_jiffies_up - function to round jiffies up to a full second
494 * round_jiffies_up_relative - function to round jiffies up to a full second
511 return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;
516 timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |
531 * - Timer is armed at the edge of a tick
532 * - Truncation of the expiry time in the outer wheel levels
544 unsigned long delta = expires - clk;
574 idx = calc_index(expires, LVL_DEPTH - 1, bucket_expiry);
589 if (!is_timers_nohz_active() || timer->flags & TIMER_DEFERRABLE)
597 * on the way to idle then it can't set base->is_idle as we hold
600 if (base->is_idle) {
601 WARN_ON_ONCE(!(timer->flags & TIMER_PINNED ||
602 tick_nohz_full_cpu(base->cpu)));
603 wake_up_nohz_cpu(base->cpu);
616 hlist_add_head(&timer->entry, base->vectors + idx);
617 __set_bit(idx, base->pending_map);
625 * (bucket_expiry) instead of timer->expires.
627 if (time_before(bucket_expiry, base->next_expiry)) {
632 WRITE_ONCE(base->next_expiry, bucket_expiry);
633 base->timers_pending = true;
634 base->next_expiry_recalc = false;
644 idx = calc_wheel_index(timer->expires, base->clk, &bucket_expiry);
657 #define TIMER_HINT(fn, container, timr, hintfn) \
660 .offset = offsetof(container, hintfn) - \
661 offsetof(container, timr) \
677 if (timer_hints[i].function == timer->function) {
684 return timer->function;
691 return (timer->entry.pprev == NULL &&
692 timer->entry.next == TIMER_ENTRY_STATIC);
697 * - an active object is initialized
721 * - an active object is activated
722 * - an unknown non-static object is activated
743 * - an active object is freed
761 * - an untracked/uninit-ed object is found
856 timer->entry.pprev = NULL;
857 timer->function = func;
860 timer->flags = flags | raw_smp_processor_id();
861 lockdep_init_map(&timer->lockdep_map, name, key, 0);
865 * timer_init_key - initialize a timer
887 struct hlist_node *entry = &timer->entry;
893 entry->pprev = NULL;
894 entry->next = LIST_POISON2;
905 if (hlist_is_singular_node(&timer->entry, base->vectors + idx)) {
906 __clear_bit(idx, base->pending_map);
907 base->next_expiry_recalc = true;
952 * @basej is past base->clk otherwise we might rewind base->clk.
954 if (time_before_eq(basej, base->clk))
961 if (time_after(base->next_expiry, basej)) {
962 base->clk = basej;
964 if (WARN_ON_ONCE(time_before(base->next_expiry, base->clk)))
966 base->clk = base->next_expiry;
982 * be found in the base->vectors array.
989 __acquires(timer->base->lock)
997 * might re-read @tf between the check for TIMER_MIGRATING
1000 tf = READ_ONCE(timer->flags);
1004 raw_spin_lock_irqsave(&base->lock, *flags);
1005 if (timer->flags == tf)
1007 raw_spin_unlock_irqrestore(&base->lock, *flags);
1028 * This is a common optimization triggered by the networking code - if
1029 * the timer is re-modified to have the same timeout or ends up in the
1038 long diff = timer->expires - expires;
1057 if (!timer->function)
1063 time_before_eq(timer->expires, expires)) {
1068 clk = base->clk;
1078 timer->expires = expires;
1079 else if (time_after(timer->expires, expires))
1080 timer->expires = expires;
1091 if (!timer->function)
1101 new_base = get_timer_this_cpu_base(timer->flags);
1111 if (likely(base->running_timer != timer)) {
1113 timer->flags |= TIMER_MIGRATING;
1115 raw_spin_unlock(&base->lock);
1117 raw_spin_lock(&base->lock);
1118 WRITE_ONCE(timer->flags,
1119 (timer->flags & ~TIMER_BASEMASK) | base->cpu);
1126 timer->expires = expires;
1133 if (idx != UINT_MAX && clk == base->clk)
1139 raw_spin_unlock_irqrestore(&base->lock, flags);
1145 * mod_timer_pending - Modify a pending timer's timeout
1152 * If @timer->function == NULL then the start operation is silently
1156 * * %0 - The timer was inactive and not modified or was in
1158 * * %1 - The timer was active and requeued to expire at @expires
1167 * mod_timer - Modify a timer's timeout
1173 * timer_delete(timer); timer->expires = expires; add_timer(timer);
1183 * If @timer->function == NULL then the start operation is silently
1187 * * %0 - The timer was inactive and started or was in shutdown
1189 * * %1 - The timer was active and requeued to expire at @expires or
1200 * timer_reduce - Modify a timer's timeout if it would reduce the timeout
1208 * If @timer->function == NULL then the start operation is silently
1212 * * %0 - The timer was inactive and started or was in shutdown
1214 * * %1 - The timer was active and requeued to expire at @expires or
1226 * add_timer - Start a timer
1229 * Start @timer to expire at @timer->expires in the future. @timer->expires
1231 * timer->function(timer) will be invoked from soft interrupt context.
1233 * The @timer->expires and @timer->function fields must be set prior
1236 * If @timer->function == NULL then the start operation is silently
1239 * If @timer->expires is already in the past @timer will be queued to
1249 __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
1254 * add_timer_local() - Start a timer on the local CPU
1265 timer->flags |= TIMER_PINNED;
1266 __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
1271 * add_timer_global() - Start a timer without TIMER_PINNED flag set
1282 timer->flags &= ~TIMER_PINNED;
1283 __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
1288 * add_timer_on - Start a timer on a particular CPU
1310 timer->flags |= TIMER_PINNED;
1312 new_base = get_timer_cpu_base(timer->flags, cpu);
1324 if (!timer->function)
1328 timer->flags |= TIMER_MIGRATING;
1330 raw_spin_unlock(&base->lock);
1332 raw_spin_lock(&base->lock);
1333 WRITE_ONCE(timer->flags,
1334 (timer->flags & ~TIMER_BASEMASK) | cpu);
1341 raw_spin_unlock_irqrestore(&base->lock, flags);
1346 * __timer_delete - Internal function: Deactivate a timer
1351 * If @shutdown is true then @timer->function is set to NULL under the
1357 * * %0 - The timer was not pending
1358 * * %1 - The timer was pending and deactivated
1374 * timer->function == NULL in the expiry code.
1376 * If timer->function is currently executed, then this makes sure
1383 timer->function = NULL;
1384 raw_spin_unlock_irqrestore(&base->lock, flags);
1391 * timer_delete - Deactivate a timer
1401 * * %0 - The timer was not pending
1402 * * %1 - The timer was pending and deactivated
1411 * timer_shutdown - Deactivate a timer and prevent rearming
1422 * * %0 - The timer was not pending
1423 * * %1 - The timer was pending
1432 * __try_to_del_timer_sync - Internal function: Try to deactivate a timer
1437 * If @shutdown is true then @timer->function is set to NULL under the
1447 * * %0 - The timer was not pending
1448 * * %1 - The timer was pending and deactivated
1449 * * %-1 - The timer callback function is running on a different CPU
1455 int ret = -1;
1461 if (base->running_timer != timer) {
1464 timer->function = NULL;
1467 raw_spin_unlock_irqrestore(&base->lock, flags);
1473 * timer_delete_sync_try - Try to deactivate a timer
1484 * * %0 - The timer was not pending
1485 * * %1 - The timer was pending and deactivated
1486 * * %-1 - The timer callback function is running on a different CPU
1497 spin_lock_init(&base->expiry_lock);
1502 spin_lock(&base->expiry_lock);
1507 spin_unlock(&base->expiry_lock);
1513 * If there is a waiter for base->expiry_lock, then it was waiting for the
1518 __releases(&base->lock) __releases(&base->expiry_lock)
1519 __acquires(&base->expiry_lock) __acquires(&base->lock)
1521 if (atomic_read(&base->timer_waiters)) {
1522 raw_spin_unlock_irq(&base->lock);
1523 spin_unlock(&base->expiry_lock);
1524 spin_lock(&base->expiry_lock);
1525 raw_spin_lock_irq(&base->lock);
1543 tf = READ_ONCE(timer->flags);
1555 atomic_inc(&base->timer_waiters);
1556 spin_lock_bh(&base->expiry_lock);
1557 atomic_dec(&base->timer_waiters);
1558 spin_unlock_bh(&base->expiry_lock);
1570 * __timer_delete_sync - Internal function: Deactivate a timer and wait
1573 * @shutdown: If true, @timer->function will be set to NULL under the
1580 * If @shutdown is set then @timer->function is set to NULL under timer
1588 * * %0 - The timer was not pending
1589 * * %1 - The timer was pending and deactivated
1600 * the synchronization rules above.
1603 lock_map_acquire(&timer->lockdep_map);
1604 lock_map_release(&timer->lockdep_map);
1611 WARN_ON(in_hardirq() && !(timer->flags & TIMER_IRQSAFE));
1617 if (IS_ENABLED(CONFIG_PREEMPT_RT) && !(timer->flags & TIMER_IRQSAFE))
1633 * timer_delete_sync - Deactivate a timer and wait for the handler to finish.
1636 * Synchronization rules: Callers must prevent restarting of the timer,
1648 * ---- ----
1651 * base->running_timer = mytimer;
1656 * while (base->running_timer == mytimer);
1671 * * %0 - The timer was not pending
1672 * * %1 - The timer was pending and deactivated
1681 * timer_shutdown_sync - Shutdown a timer and prevent rearming
1685 * - @timer is not queued
1686 * - The callback function of @timer is not running
1687 * - @timer cannot be enqueued again. Any attempt to rearm
1690 * See timer_delete_sync() for synchronization rules.
1698 * code has conditionals like 'if (mything->in_shutdown)' to prevent that
1704 * timer_shutdown_sync(&mything->timer);
1705 * workqueue_destroy(&mything->workqueue);
1713 * * %0 - The timer was not pending
1714 * * %1 - The timer was pending
1734 * timer->lockdep_map, make a copy and use that here.
1738 lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
1754 WARN_ONCE(1, "timer: %pS preempt leak: %08x -> %08x\n",
1769 * This value is required only for tracing. base->clk was
1771 * is related to the old base->clk value.
1773 unsigned long baseclk = base->clk - 1;
1779 timer = hlist_entry(head->first, struct timer_list, entry);
1781 base->running_timer = timer;
1784 fn = timer->function;
1788 base->running_timer = NULL;
1792 if (timer->flags & TIMER_IRQSAFE) {
1793 raw_spin_unlock(&base->lock);
1795 raw_spin_lock(&base->lock);
1796 base->running_timer = NULL;
1798 raw_spin_unlock_irq(&base->lock);
1800 raw_spin_lock_irq(&base->lock);
1801 base->running_timer = NULL;
1810 unsigned long clk = base->clk = base->next_expiry;
1818 if (__test_and_clear_bit(idx, base->pending_map)) {
1819 vec = base->vectors + idx;
1843 pos = find_next_bit(base->pending_map, end, start);
1845 return pos - start;
1847 pos = find_next_bit(base->pending_map, start, offset);
1848 return pos < start ? pos + LVL_SIZE - start : -1;
1853 * hold base->lock.
1855 * Store next expiry time in base->next_expiry.
1862 next = base->clk + TIMER_NEXT_MAX_DELTA;
1863 clk = base->clk;
1879 if (pos <= ((LVL_CLK_DIV - lvl_clk) & LVL_CLK_MASK))
1886 * next expiring bucket in that level. base->clk is the next
1901 * rules apply:
1923 WRITE_ONCE(base->next_expiry, next);
1924 base->next_expiry_recalc = false;
1925 base->timers_pending = !(next == base->clk + TIMER_NEXT_MAX_DELTA);
1965 if (base->next_expiry_recalc)
1976 if (!base->timers_pending)
1977 WRITE_ONCE(base->next_expiry, basej + TIMER_NEXT_MAX_DELTA);
1979 return base->next_expiry;
2006 tevt->local = basem + (u64)(nextevt - basej) * TICK_NSEC;
2014 * updating tevt->global with the already missed first global
2017 * * The local callers will ignore the tevt->global anyway, when
2021 tevt->global = tevt->local;
2031 if (!local_first && base_global->timers_pending)
2032 tevt->global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
2034 if (base_local->timers_pending)
2035 tevt->local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
2042 * fetch_next_timer_interrupt_remote() - Store next timers into @tevt
2063 tevt->local = tevt->global = KTIME_MAX;
2068 lockdep_assert_held(&base_local->lock);
2069 lockdep_assert_held(&base_global->lock);
2075 * timer_unlock_remote_bases - unlock timer bases of cpu
2081 __releases(timer_bases[BASE_LOCAL]->lock)
2082 __releases(timer_bases[BASE_GLOBAL]->lock)
2089 raw_spin_unlock(&base_global->lock);
2090 raw_spin_unlock(&base_local->lock);
2094 * timer_lock_remote_bases - lock timer bases of cpu
2100 __acquires(timer_bases[BASE_LOCAL]->lock)
2101 __acquires(timer_bases[BASE_GLOBAL]->lock)
2110 raw_spin_lock(&base_local->lock);
2111 raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
2115 * timer_base_is_idle() - Return whether timer base is set idle
2127 * timer_expire_remote() - expire global timers of cpu
2146 next_tmigr = tmigr_cpu_new_timer(tevt->global);
2148 next_tmigr = tmigr_cpu_deactivate(tevt->global);
2150 next_tmigr = tmigr_quick_check(tevt->global);
2157 if (next_tmigr < tevt->local) {
2164 tmp = div_u64(next_tmigr - basem, TICK_NSEC);
2167 tevt->local = next_tmigr;
2176 * Make sure first event is written into tevt->local to not miss a
2179 tevt->local = min_t(u64, tevt->local, tevt->global);
2204 raw_spin_lock(&base_local->lock);
2205 raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
2224 base_local->is_idle, &tevt);
2234 * Set base->is_idle only when caller is timer_base_try_to_set_idle()
2249 if (!base_local->is_idle && time_after(nextevt, basej + 1)) {
2250 base_local->is_idle = true;
2253 * in nohz_full mode need a self-IPI to kick reprogramming
2256 if (tick_nohz_full_cpu(base_local->cpu))
2257 base_global->is_idle = true;
2258 trace_timer_base_idle(true, base_local->cpu);
2260 *idle = base_local->is_idle;
2264 * tmigr_cpu_deactivate() to prevent inconsistent states - active
2270 if (!base_local->is_idle && idle_is_possible)
2274 raw_spin_unlock(&base_global->lock);
2275 raw_spin_unlock(&base_local->lock);
2281 * get_next_timer_interrupt() - return the time (clock mono) of the next timer
2297 * timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
2300 * @idle: pointer to store the value of timer_base->is_idle on return;
2316 * timer_clear_idle - Clear the idle state of the timer base
2334 /* Activate without holding the timer_base->lock */
2340 * __run_timers - run all expired timers (if any) on this CPU.
2348 lockdep_assert_held(&base->lock);
2350 if (base->running_timer)
2353 while (time_after_eq(jiffies, base->clk) &&
2354 time_after_eq(jiffies, base->next_expiry)) {
2363 WARN_ON_ONCE(!levels && !base->next_expiry_recalc
2364 && base->timers_pending);
2366 * While executing timers, base->clk is set 1 offset ahead of
2369 base->clk++;
2372 while (levels--)
2380 if (time_before(jiffies, READ_ONCE(base->next_expiry)))
2384 raw_spin_lock_irq(&base->lock);
2386 raw_spin_unlock_irq(&base->lock);
2398 * This function runs timers and the timer-tq in bottom half context.
2413 * Called by the local, per-CPU timer interrupt on SMP.
2444 * is missed, then the timer would expire one jiffy late -
2455 if (time_after_eq(jiffies, READ_ONCE(base->next_expiry)) ||
2488 int cpu = new_base->cpu;
2491 timer = hlist_entry(head->first, struct timer_list, entry);
2493 timer->flags = (timer->flags & ~TIMER_BASEMASK) | cpu;
2505 base->clk = jiffies;
2506 base->next_expiry = base->clk + TIMER_NEXT_MAX_DELTA;
2507 base->next_expiry_recalc = false;
2508 base->timers_pending = false;
2509 base->is_idle = false;
2527 raw_spin_lock_irq(&new_base->lock);
2528 raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
2536 WARN_ON_ONCE(old_base->running_timer);
2537 old_base->running_timer = NULL;
2540 migrate_timer_list(new_base, old_base->vectors + i);
2542 raw_spin_unlock(&old_base->lock);
2543 raw_spin_unlock_irq(&new_base->lock);
2558 base->cpu = cpu;
2559 raw_spin_lock_init(&base->lock);
2560 base->clk = jiffies;
2561 base->next_expiry = base->clk + TIMER_NEXT_MAX_DELTA;