timer.c 55.7 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3
/*
 *  linux/kernel/timer.c
 *
4
 *  Kernel internal timers
Linus Torvalds's avatar
Linus Torvalds committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
 *
 *  Copyright (C) 1991, 1992  Linus Torvalds
 *
 *  1997-01-28  Modified by Finn Arne Gangstad to make timers scale better.
 *
 *  1997-09-10  Updated NTP code according to technical memorandum Jan '96
 *              "A Kernel Model for Precision Timekeeping" by Dave Mills
 *  1998-12-24  Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
 *              serialize accesses to xtime/lost_ticks).
 *                              Copyright (C) 1998  Andrea Arcangeli
 *  1999-03-10  Improved NTP compatibility by Ulrich Windl
 *  2002-05-31	Move sys_sysinfo here and make its locking sane, Robert Love
 *  2000-10-05  Implemented scalable SMP per-CPU timer handling.
 *                              Copyright (C) 2000, 2001, 2002  Ingo Molnar
 *              Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar
 */

#include <linux/kernel_stat.h>
23
#include <linux/export.h>
Linus Torvalds's avatar
Linus Torvalds committed
24
#include <linux/interrupt.h>
25
#include <linux/ipipe.h>
Linus Torvalds's avatar
Linus Torvalds committed
26 27 28 29
#include <linux/percpu.h>
#include <linux/init.h>
#include <linux/mm.h>
#include <linux/swap.h>
30
#include <linux/pid_namespace.h>
Linus Torvalds's avatar
Linus Torvalds committed
31 32 33 34 35 36 37
#include <linux/notifier.h>
#include <linux/thread_info.h>
#include <linux/time.h>
#include <linux/jiffies.h>
#include <linux/posix-timers.h>
#include <linux/cpu.h>
#include <linux/syscalls.h>
Adrian Bunk's avatar
Adrian Bunk committed
38
#include <linux/delay.h>
39
#include <linux/tick.h>
40
#include <linux/kallsyms.h>
41
#include <linux/irq_work.h>
42
#include <linux/sched/signal.h>
43
#include <linux/sched/sysctl.h>
44
#include <linux/sched/nohz.h>
45
#include <linux/sched/debug.h>
46
#include <linux/slab.h>
47
#include <linux/compat.h>
Linus Torvalds's avatar
Linus Torvalds committed
48

49
#include <linux/uaccess.h>
Linus Torvalds's avatar
Linus Torvalds committed
50 51 52 53 54
#include <asm/unistd.h>
#include <asm/div64.h>
#include <asm/timex.h>
#include <asm/io.h>

55 56
#include "tick-internal.h"

57 58 59
#define CREATE_TRACE_POINTS
#include <trace/events/timer.h>

Andi Kleen's avatar
Andi Kleen committed
60
__visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
Thomas Gleixner's avatar
Thomas Gleixner committed
61 62 63

EXPORT_SYMBOL(jiffies_64);

Linus Torvalds's avatar
Linus Torvalds committed
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
 * The timer wheel has LVL_DEPTH array levels. Each level provides an array of
 * LVL_SIZE buckets. Each level is driven by its own clock and therefor each
 * level has a different granularity.
 *
 * The level granularity is:		LVL_CLK_DIV ^ lvl
 * The level clock frequency is:	HZ / (LVL_CLK_DIV ^ level)
 *
 * The array level of a newly armed timer depends on the relative expiry
 * time. The farther the expiry time is away the higher the array level and
 * therefor the granularity becomes.
 *
 * Contrary to the original timer wheel implementation, which aims for 'exact'
 * expiry of the timers, this implementation removes the need for recascading
 * the timers into the lower array levels. The previous 'classic' timer wheel
 * implementation of the kernel already violated the 'exact' expiry by adding
 * slack to the expiry time to provide batched expiration. The granularity
 * levels provide implicit batching.
 *
 * This is an optimization of the original timer wheel implementation for the
 * majority of the timer wheel use cases: timeouts. The vast majority of
 * timeout timers (networking, disk I/O ...) are canceled before expiry. If
 * the timeout expires it indicates that normal operation is disturbed, so it
 * does not matter much whether the timeout comes with a slight delay.
 *
 * The only exception to this are networking timers with a small expiry
 * time. They rely on the granularity. Those fit into the first wheel level,
 * which has HZ granularity.
 *
 * We don't have cascading anymore. timers with a expiry time above the
 * capacity of the last wheel level are force expired at the maximum timeout
 * value of the last wheel level. From data sampling we know that the maximum
 * value observed is 5 days (network connection tracking), so this should not
 * be an issue.
 *
 * The currently chosen array constants values are a good compromise between
 * array size and granularity.
 *
 * This results in the following granularity and range levels:
 *
 * HZ 1000 steps
 * Level Offset  Granularity            Range
 *  0      0         1 ms                0 ms -         63 ms
 *  1     64         8 ms               64 ms -        511 ms
 *  2    128        64 ms              512 ms -       4095 ms (512ms - ~4s)
 *  3    192       512 ms             4096 ms -      32767 ms (~4s - ~32s)
 *  4    256      4096 ms (~4s)      32768 ms -     262143 ms (~32s - ~4m)
 *  5    320     32768 ms (~32s)    262144 ms -    2097151 ms (~4m - ~34m)
 *  6    384    262144 ms (~4m)    2097152 ms -   16777215 ms (~34m - ~4h)
 *  7    448   2097152 ms (~34m)  16777216 ms -  134217727 ms (~4h - ~1d)
 *  8    512  16777216 ms (~4h)  134217728 ms - 1073741822 ms (~1d - ~12d)
 *
 * HZ  300
 * Level Offset  Granularity            Range
 *  0	   0         3 ms                0 ms -        210 ms
 *  1	  64        26 ms              213 ms -       1703 ms (213ms - ~1s)
 *  2	 128       213 ms             1706 ms -      13650 ms (~1s - ~13s)
 *  3	 192      1706 ms (~1s)      13653 ms -     109223 ms (~13s - ~1m)
 *  4	 256     13653 ms (~13s)    109226 ms -     873810 ms (~1m - ~14m)
 *  5	 320    109226 ms (~1m)     873813 ms -    6990503 ms (~14m - ~1h)
 *  6	 384    873813 ms (~14m)   6990506 ms -   55924050 ms (~1h - ~15h)
 *  7	 448   6990506 ms (~1h)   55924053 ms -  447392423 ms (~15h - ~5d)
 *  8    512  55924053 ms (~15h) 447392426 ms - 3579139406 ms (~5d - ~41d)
 *
 * HZ  250
 * Level Offset  Granularity            Range
 *  0	   0         4 ms                0 ms -        255 ms
 *  1	  64        32 ms              256 ms -       2047 ms (256ms - ~2s)
 *  2	 128       256 ms             2048 ms -      16383 ms (~2s - ~16s)
 *  3	 192      2048 ms (~2s)      16384 ms -     131071 ms (~16s - ~2m)
 *  4	 256     16384 ms (~16s)    131072 ms -    1048575 ms (~2m - ~17m)
 *  5	 320    131072 ms (~2m)    1048576 ms -    8388607 ms (~17m - ~2h)
 *  6	 384   1048576 ms (~17m)   8388608 ms -   67108863 ms (~2h - ~18h)
 *  7	 448   8388608 ms (~2h)   67108864 ms -  536870911 ms (~18h - ~6d)
 *  8    512  67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d)
 *
 * HZ  100
 * Level Offset  Granularity            Range
 *  0	   0         10 ms               0 ms -        630 ms
 *  1	  64         80 ms             640 ms -       5110 ms (640ms - ~5s)
 *  2	 128        640 ms            5120 ms -      40950 ms (~5s - ~40s)
 *  3	 192       5120 ms (~5s)     40960 ms -     327670 ms (~40s - ~5m)
 *  4	 256      40960 ms (~40s)   327680 ms -    2621430 ms (~5m - ~43m)
 *  5	 320     327680 ms (~5m)   2621440 ms -   20971510 ms (~43m - ~5h)
 *  6	 384    2621440 ms (~43m) 20971520 ms -  167772150 ms (~5h - ~1d)
 *  7	 448   20971520 ms (~5h) 167772160 ms - 1342177270 ms (~1d - ~15d)
Linus Torvalds's avatar
Linus Torvalds committed
150 151
 */

152 153 154 155 156 157
/* Clock divisor for the next level */
#define LVL_CLK_SHIFT	3
#define LVL_CLK_DIV	(1UL << LVL_CLK_SHIFT)
#define LVL_CLK_MASK	(LVL_CLK_DIV - 1)
#define LVL_SHIFT(n)	((n) * LVL_CLK_SHIFT)
#define LVL_GRAN(n)	(1UL << LVL_SHIFT(n))
Linus Torvalds's avatar
Linus Torvalds committed
158

159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
/*
 * The time start value for each level to select the bucket at enqueue
 * time.
 */
#define LVL_START(n)	((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))

/* Size of each clock level */
#define LVL_BITS	6
#define LVL_SIZE	(1UL << LVL_BITS)
#define LVL_MASK	(LVL_SIZE - 1)
#define LVL_OFFS(n)	((n) * LVL_SIZE)

/* Level depth */
#if HZ > 100
# define LVL_DEPTH	9
# else
# define LVL_DEPTH	8
#endif

/* The cutoff (max. capacity of the wheel) */
#define WHEEL_TIMEOUT_CUTOFF	(LVL_START(LVL_DEPTH))
#define WHEEL_TIMEOUT_MAX	(WHEEL_TIMEOUT_CUTOFF - LVL_GRAN(LVL_DEPTH - 1))

/*
 * The resulting wheel size. If NOHZ is configured we allocate two
 * wheels so we have a separate storage for the deferrable timers.
 */
#define WHEEL_SIZE	(LVL_SIZE * LVL_DEPTH)

#ifdef CONFIG_NO_HZ_COMMON
# define NR_BASES	2
# define BASE_STD	0
# define BASE_DEF	1
#else
# define NR_BASES	1
# define BASE_STD	0
# define BASE_DEF	0
#endif
Linus Torvalds's avatar
Linus Torvalds committed
197

198
struct timer_base {
199
	raw_spinlock_t		lock;
200 201
	struct timer_list	*running_timer;
	unsigned long		clk;
202
	unsigned long		next_expiry;
203 204 205
	unsigned int		cpu;
	bool			migration_enabled;
	bool			nohz_active;
206
	bool			is_idle;
207
	bool			must_forward_clk;
208 209
	DECLARE_BITMAP(pending_map, WHEEL_SIZE);
	struct hlist_head	vectors[WHEEL_SIZE];
210
} ____cacheline_aligned;
211

212
static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
213

214 215 216
#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
unsigned int sysctl_timer_migration = 1;

217
void timers_update_migration(bool update_nohz)
218 219 220 221 222
{
	bool on = sysctl_timer_migration && tick_nohz_active;
	unsigned int cpu;

	/* Avoid the loop, if nothing to update */
223
	if (this_cpu_read(timer_bases[BASE_STD].migration_enabled) == on)
224 225 226
		return;

	for_each_possible_cpu(cpu) {
227 228
		per_cpu(timer_bases[BASE_STD].migration_enabled, cpu) = on;
		per_cpu(timer_bases[BASE_DEF].migration_enabled, cpu) = on;
229
		per_cpu(hrtimer_bases.migration_enabled, cpu) = on;
230 231
		if (!update_nohz)
			continue;
232 233
		per_cpu(timer_bases[BASE_STD].nohz_active, cpu) = true;
		per_cpu(timer_bases[BASE_DEF].nohz_active, cpu) = true;
234
		per_cpu(hrtimer_bases.nohz_active, cpu) = true;
235 236 237 238 239 240 241 242 243 244 245
	}
}

int timer_migration_handler(struct ctl_table *table, int write,
			    void __user *buffer, size_t *lenp,
			    loff_t *ppos)
{
	static DEFINE_MUTEX(mutex);
	int ret;

	mutex_lock(&mutex);
246
	ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
247
	if (!ret && write)
248
		timers_update_migration(false);
249 250 251 252 253
	mutex_unlock(&mutex);
	return ret;
}
#endif

254 255
static unsigned long round_jiffies_common(unsigned long j, int cpu,
		bool force_up)
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276
{
	int rem;
	unsigned long original = j;

	/*
	 * We don't want all cpus firing their timers at once hitting the
	 * same lock or cachelines, so we skew each extra cpu with an extra
	 * 3 jiffies. This 3 jiffies came originally from the mm/ code which
	 * already did this.
	 * The skew is done by adding 3*cpunr, then round, then subtract this
	 * extra offset again.
	 */
	j += cpu * 3;

	rem = j % HZ;

	/*
	 * If the target jiffie is just after a whole second (which can happen
	 * due to delays of the timer irq, long irq off times etc etc) then
	 * we should round down to the whole second, not up. Use 1/4th second
	 * as cutoff for this rounding as an extreme upper bound for this.
277
	 * But never round down if @force_up is set.
278
	 */
279
	if (rem < HZ/4 && !force_up) /* round down */
280 281 282 283 284 285 286
		j = j - rem;
	else /* round up */
		j = j - rem + HZ;

	/* now that we have rounded, subtract the extra skew again */
	j -= cpu * 3;

287 288 289 290 291
	/*
	 * Make sure j is still in the future. Otherwise return the
	 * unmodified value.
	 */
	return time_is_after_jiffies(j) ? j : original;
292
}
293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317

/**
 * __round_jiffies - function to round jiffies to a full second
 * @j: the time in (absolute) jiffies that should be rounded
 * @cpu: the processor number on which the timeout will happen
 *
 * __round_jiffies() rounds an absolute time in the future (in jiffies)
 * up or down to (approximately) full seconds. This is useful for timers
 * for which the exact time they fire does not matter too much, as long as
 * they fire approximately every X seconds.
 *
 * By rounding these timers to whole seconds, all such timers will fire
 * at the same time, rather than at various times spread out. The goal
 * of this is to have the CPU wake up less, which saves power.
 *
 * The exact rounding is skewed for each processor to avoid all
 * processors firing at the exact same time, which could lead
 * to lock contention or spurious cache line bouncing.
 *
 * The return value is the rounded version of the @j parameter.
 */
unsigned long __round_jiffies(unsigned long j, int cpu)
{
	return round_jiffies_common(j, cpu, false);
}
318 319 320 321 322 323 324
EXPORT_SYMBOL_GPL(__round_jiffies);

/**
 * __round_jiffies_relative - function to round jiffies to a full second
 * @j: the time in (relative) jiffies that should be rounded
 * @cpu: the processor number on which the timeout will happen
 *
325
 * __round_jiffies_relative() rounds a time delta  in the future (in jiffies)
326 327 328 329 330 331 332 333 334 335 336 337
 * up or down to (approximately) full seconds. This is useful for timers
 * for which the exact time they fire does not matter too much, as long as
 * they fire approximately every X seconds.
 *
 * By rounding these timers to whole seconds, all such timers will fire
 * at the same time, rather than at various times spread out. The goal
 * of this is to have the CPU wake up less, which saves power.
 *
 * The exact rounding is skewed for each processor to avoid all
 * processors firing at the exact same time, which could lead
 * to lock contention or spurious cache line bouncing.
 *
338
 * The return value is the rounded version of the @j parameter.
339 340 341
 */
unsigned long __round_jiffies_relative(unsigned long j, int cpu)
{
342 343 344 345
	unsigned long j0 = jiffies;

	/* Use j0 because jiffies might change while we run */
	return round_jiffies_common(j + j0, cpu, false) - j0;
346 347 348 349 350 351 352
}
EXPORT_SYMBOL_GPL(__round_jiffies_relative);

/**
 * round_jiffies - function to round jiffies to a full second
 * @j: the time in (absolute) jiffies that should be rounded
 *
353
 * round_jiffies() rounds an absolute time in the future (in jiffies)
354 355 356 357 358 359 360 361
 * up or down to (approximately) full seconds. This is useful for timers
 * for which the exact time they fire does not matter too much, as long as
 * they fire approximately every X seconds.
 *
 * By rounding these timers to whole seconds, all such timers will fire
 * at the same time, rather than at various times spread out. The goal
 * of this is to have the CPU wake up less, which saves power.
 *
362
 * The return value is the rounded version of the @j parameter.
363 364 365
 */
unsigned long round_jiffies(unsigned long j)
{
366
	return round_jiffies_common(j, raw_smp_processor_id(), false);
367 368 369 370 371 372 373
}
EXPORT_SYMBOL_GPL(round_jiffies);

/**
 * round_jiffies_relative - function to round jiffies to a full second
 * @j: the time in (relative) jiffies that should be rounded
 *
374
 * round_jiffies_relative() rounds a time delta  in the future (in jiffies)
375 376 377 378 379 380 381 382
 * up or down to (approximately) full seconds. This is useful for timers
 * for which the exact time they fire does not matter too much, as long as
 * they fire approximately every X seconds.
 *
 * By rounding these timers to whole seconds, all such timers will fire
 * at the same time, rather than at various times spread out. The goal
 * of this is to have the CPU wake up less, which saves power.
 *
383
 * The return value is the rounded version of the @j parameter.
384 385 386 387 388 389 390
 */
unsigned long round_jiffies_relative(unsigned long j)
{
	return __round_jiffies_relative(j, raw_smp_processor_id());
}
EXPORT_SYMBOL_GPL(round_jiffies_relative);

391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455
/**
 * __round_jiffies_up - function to round jiffies up to a full second
 * @j: the time in (absolute) jiffies that should be rounded
 * @cpu: the processor number on which the timeout will happen
 *
 * This is the same as __round_jiffies() except that it will never
 * round down.  This is useful for timeouts for which the exact time
 * of firing does not matter too much, as long as they don't fire too
 * early.
 */
unsigned long __round_jiffies_up(unsigned long j, int cpu)
{
	return round_jiffies_common(j, cpu, true);
}
EXPORT_SYMBOL_GPL(__round_jiffies_up);

/**
 * __round_jiffies_up_relative - function to round jiffies up to a full second
 * @j: the time in (relative) jiffies that should be rounded
 * @cpu: the processor number on which the timeout will happen
 *
 * This is the same as __round_jiffies_relative() except that it will never
 * round down.  This is useful for timeouts for which the exact time
 * of firing does not matter too much, as long as they don't fire too
 * early.
 */
unsigned long __round_jiffies_up_relative(unsigned long j, int cpu)
{
	unsigned long j0 = jiffies;

	/* Use j0 because jiffies might change while we run */
	return round_jiffies_common(j + j0, cpu, true) - j0;
}
EXPORT_SYMBOL_GPL(__round_jiffies_up_relative);

/**
 * round_jiffies_up - function to round jiffies up to a full second
 * @j: the time in (absolute) jiffies that should be rounded
 *
 * This is the same as round_jiffies() except that it will never
 * round down.  This is useful for timeouts for which the exact time
 * of firing does not matter too much, as long as they don't fire too
 * early.
 */
unsigned long round_jiffies_up(unsigned long j)
{
	return round_jiffies_common(j, raw_smp_processor_id(), true);
}
EXPORT_SYMBOL_GPL(round_jiffies_up);

/**
 * round_jiffies_up_relative - function to round jiffies up to a full second
 * @j: the time in (relative) jiffies that should be rounded
 *
 * This is the same as round_jiffies_relative() except that it will never
 * round down.  This is useful for timeouts for which the exact time
 * of firing does not matter too much, as long as they don't fire too
 * early.
 */
unsigned long round_jiffies_up_relative(unsigned long j)
{
	return __round_jiffies_up_relative(j, raw_smp_processor_id());
}
EXPORT_SYMBOL_GPL(round_jiffies_up_relative);

456

457
static inline unsigned int timer_get_idx(struct timer_list *timer)
458
{
459
	return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;
460 461
}

462
static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
Linus Torvalds's avatar
Linus Torvalds committed
463
{
464 465 466
	timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |
			idx << TIMER_ARRAYSHIFT;
}
Linus Torvalds's avatar
Linus Torvalds committed
467

468 469 470 471 472 473 474 475 476 477
/*
 * Helper function to calculate the array index for a given expiry
 * time.
 */
static inline unsigned calc_index(unsigned expires, unsigned lvl)
{
	expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
	return LVL_OFFS(lvl) + (expires & LVL_MASK);
}

478
static int calc_wheel_index(unsigned long expires, unsigned long clk)
Linus Torvalds's avatar
Linus Torvalds committed
479
{
480
	unsigned long delta = expires - clk;
481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499
	unsigned int idx;

	if (delta < LVL_START(1)) {
		idx = calc_index(expires, 0);
	} else if (delta < LVL_START(2)) {
		idx = calc_index(expires, 1);
	} else if (delta < LVL_START(3)) {
		idx = calc_index(expires, 2);
	} else if (delta < LVL_START(4)) {
		idx = calc_index(expires, 3);
	} else if (delta < LVL_START(5)) {
		idx = calc_index(expires, 4);
	} else if (delta < LVL_START(6)) {
		idx = calc_index(expires, 5);
	} else if (delta < LVL_START(7)) {
		idx = calc_index(expires, 6);
	} else if (LVL_DEPTH > 8 && delta < LVL_START(8)) {
		idx = calc_index(expires, 7);
	} else if ((long) delta < 0) {
500
		idx = clk & LVL_MASK;
Linus Torvalds's avatar
Linus Torvalds committed
501
	} else {
502 503 504
		/*
		 * Force expire obscene large timeouts to expire at the
		 * capacity limit of the wheel.
Linus Torvalds's avatar
Linus Torvalds committed
505
		 */
506 507
		if (expires >= WHEEL_TIMEOUT_CUTOFF)
			expires = WHEEL_TIMEOUT_MAX;
508

509
		idx = calc_index(expires, LVL_DEPTH - 1);
Linus Torvalds's avatar
Linus Torvalds committed
510
	}
511 512
	return idx;
}
513

514 515 516 517 518 519 520 521
/*
 * Enqueue the timer into the hash bucket, mark it pending in
 * the bitmap and store the index in the timer flags.
 */
static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
			  unsigned int idx)
{
	hlist_add_head(&timer->entry, base->vectors + idx);
522 523
	__set_bit(idx, base->pending_map);
	timer_set_idx(timer, idx);
Linus Torvalds's avatar
Linus Torvalds committed
524 525
}

526 527
static void
__internal_add_timer(struct timer_base *base, struct timer_list *timer)
528
{
529 530 531 532 533
	unsigned int idx;

	idx = calc_wheel_index(timer->expires, base->clk);
	enqueue_timer(base, timer, idx);
}
534

535 536 537
static void
trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
{
538 539
	if (!IS_ENABLED(CONFIG_NO_HZ_COMMON) || !base->nohz_active)
		return;
540

541
	/*
542 543
	 * TODO: This wants some optimizing similar to the code below, but we
	 * will do that when we switch from push to pull for deferrable timers.
544
	 */
545 546
	if (timer->flags & TIMER_DEFERRABLE) {
		if (tick_nohz_full_cpu(base->cpu))
547
			wake_up_nohz_cpu(base->cpu);
548
		return;
549
	}
550 551

	/*
552 553 554
	 * We might have to IPI the remote CPU if the base is idle and the
	 * timer is not deferrable. If the other CPU is on the way to idle
	 * then it can't set base->is_idle as we hold the base lock:
555
	 */
556 557 558 559 560 561 562 563 564 565 566 567
	if (!base->is_idle)
		return;

	/* Check whether this is the new first expiring timer: */
	if (time_after_eq(timer->expires, base->next_expiry))
		return;

	/*
	 * Set the next expiry time and kick the CPU so it can reevaluate the
	 * wheel:
	 */
	base->next_expiry = timer->expires;
568 569 570 571 572 573 574 575
		wake_up_nohz_cpu(base->cpu);
}

static void
internal_add_timer(struct timer_base *base, struct timer_list *timer)
{
	__internal_add_timer(base, timer);
	trigger_dyntick_cpu(base, timer);
576 577
}

578 579 580 581
#ifdef CONFIG_DEBUG_OBJECTS_TIMERS

static struct debug_obj_descr timer_debug_descr;

582 583 584 585 586
static void *timer_debug_hint(void *addr)
{
	return ((struct timer_list *) addr)->function;
}

587 588 589 590 591 592 593 594
static bool timer_is_static_object(void *addr)
{
	struct timer_list *timer = addr;

	return (timer->entry.pprev == NULL &&
		timer->entry.next == TIMER_ENTRY_STATIC);
}

595 596 597
/*
 * fixup_init is called when:
 * - an active object is initialized
598
 */
599
static bool timer_fixup_init(void *addr, enum debug_obj_state state)
600 601 602 603 604 605 606
{
	struct timer_list *timer = addr;

	switch (state) {
	case ODEBUG_STATE_ACTIVE:
		del_timer_sync(timer);
		debug_object_init(timer, &timer_debug_descr);
607
		return true;
608
	default:
609
		return false;
610 611 612
	}
}

613 614 615 616 617 618
/* Stub timer callback for improperly used timers. */
static void stub_timer(unsigned long data)
{
	WARN_ON(1);
}

619 620 621
/*
 * fixup_activate is called when:
 * - an active object is activated
622
 * - an unknown non-static object is activated
623
 */
624
static bool timer_fixup_activate(void *addr, enum debug_obj_state state)
625 626 627 628 629
{
	struct timer_list *timer = addr;

	switch (state) {
	case ODEBUG_STATE_NOTAVAILABLE:
630 631
		setup_timer(timer, stub_timer, 0);
		return true;
632 633 634 635 636

	case ODEBUG_STATE_ACTIVE:
		WARN_ON(1);

	default:
637
		return false;
638 639 640 641 642 643 644
	}
}

/*
 * fixup_free is called when:
 * - an active object is freed
 */
645
static bool timer_fixup_free(void *addr, enum debug_obj_state state)
646 647 648 649 650 651 652
{
	struct timer_list *timer = addr;

	switch (state) {
	case ODEBUG_STATE_ACTIVE:
		del_timer_sync(timer);
		debug_object_free(timer, &timer_debug_descr);
653
		return true;
654
	default:
655
		return false;
656 657 658
	}
}

659 660 661 662
/*
 * fixup_assert_init is called when:
 * - an untracked/uninit-ed object is found
 */
663
static bool timer_fixup_assert_init(void *addr, enum debug_obj_state state)
664 665 666 667 668
{
	struct timer_list *timer = addr;

	switch (state) {
	case ODEBUG_STATE_NOTAVAILABLE:
669 670
		setup_timer(timer, stub_timer, 0);
		return true;
671
	default:
672
		return false;
673 674 675
	}
}

676
static struct debug_obj_descr timer_debug_descr = {
677 678
	.name			= "timer_list",
	.debug_hint		= timer_debug_hint,
679
	.is_static_object	= timer_is_static_object,
680 681 682 683
	.fixup_init		= timer_fixup_init,
	.fixup_activate		= timer_fixup_activate,
	.fixup_free		= timer_fixup_free,
	.fixup_assert_init	= timer_fixup_assert_init,
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705
};

static inline void debug_timer_init(struct timer_list *timer)
{
	debug_object_init(timer, &timer_debug_descr);
}

static inline void debug_timer_activate(struct timer_list *timer)
{
	debug_object_activate(timer, &timer_debug_descr);
}

static inline void debug_timer_deactivate(struct timer_list *timer)
{
	debug_object_deactivate(timer, &timer_debug_descr);
}

static inline void debug_timer_free(struct timer_list *timer)
{
	debug_object_free(timer, &timer_debug_descr);
}

706 707 708 709 710
static inline void debug_timer_assert_init(struct timer_list *timer)
{
	debug_object_assert_init(timer, &timer_debug_descr);
}

Tejun Heo's avatar
Tejun Heo committed
711 712
static void do_init_timer(struct timer_list *timer, unsigned int flags,
			  const char *name, struct lock_class_key *key);
713

Tejun Heo's avatar
Tejun Heo committed
714 715
void init_timer_on_stack_key(struct timer_list *timer, unsigned int flags,
			     const char *name, struct lock_class_key *key)
716 717
{
	debug_object_init_on_stack(timer, &timer_debug_descr);
Tejun Heo's avatar
Tejun Heo committed
718
	do_init_timer(timer, flags, name, key);
719
}
720
EXPORT_SYMBOL_GPL(init_timer_on_stack_key);
721 722 723 724 725 726 727 728 729 730 731

void destroy_timer_on_stack(struct timer_list *timer)
{
	debug_object_free(timer, &timer_debug_descr);
}
EXPORT_SYMBOL_GPL(destroy_timer_on_stack);

#else
static inline void debug_timer_init(struct timer_list *timer) { }
static inline void debug_timer_activate(struct timer_list *timer) { }
static inline void debug_timer_deactivate(struct timer_list *timer) { }
732
static inline void debug_timer_assert_init(struct timer_list *timer) { }
733 734
#endif

735 736 737 738 739 740 741 742 743 744
static inline void debug_init(struct timer_list *timer)
{
	debug_timer_init(timer);
	trace_timer_init(timer);
}

static inline void
debug_activate(struct timer_list *timer, unsigned long expires)
{
	debug_timer_activate(timer);
745
	trace_timer_start(timer, expires, timer->flags);
746 747 748 749 750 751 752 753
}

static inline void debug_deactivate(struct timer_list *timer)
{
	debug_timer_deactivate(timer);
	trace_timer_cancel(timer);
}

754 755 756 757 758
static inline void debug_assert_init(struct timer_list *timer)
{
	debug_timer_assert_init(timer);
}

Tejun Heo's avatar
Tejun Heo committed
759 760
static void do_init_timer(struct timer_list *timer, unsigned int flags,
			  const char *name, struct lock_class_key *key)
761
{
762
	timer->entry.pprev = NULL;
763
	timer->flags = flags | raw_smp_processor_id();
764
	lockdep_init_map(&timer->lockdep_map, name, key, 0);
765
}
766 767

/**
Randy Dunlap's avatar
Randy Dunlap committed
768
 * init_timer_key - initialize a timer
769
 * @timer: the timer to be initialized
Tejun Heo's avatar
Tejun Heo committed
770
 * @flags: timer flags
Randy Dunlap's avatar
Randy Dunlap committed
771 772 773
 * @name: name of the timer
 * @key: lockdep class key of the fake lock used for tracking timer
 *       sync lock dependencies
774
 *
Randy Dunlap's avatar
Randy Dunlap committed
775
 * init_timer_key() must be done to a timer prior calling *any* of the
776 777
 * other timer functions.
 */
Tejun Heo's avatar
Tejun Heo committed
778 779
void init_timer_key(struct timer_list *timer, unsigned int flags,
		    const char *name, struct lock_class_key *key)
780
{
781
	debug_init(timer);
Tejun Heo's avatar
Tejun Heo committed
782
	do_init_timer(timer, flags, name, key);
783
}
784
EXPORT_SYMBOL(init_timer_key);
785

786
static inline void detach_timer(struct timer_list *timer, bool clear_pending)
787
{
788
	struct hlist_node *entry = &timer->entry;
789

790
	debug_deactivate(timer);
791

792
	__hlist_del(entry);
793
	if (clear_pending)
794 795
		entry->pprev = NULL;
	entry->next = LIST_POISON2;
796 797
}

798
static int detach_if_pending(struct timer_list *timer, struct timer_base *base,
799 800
			     bool clear_pending)
{
801 802
	unsigned idx = timer_get_idx(timer);

803 804 805
	if (!timer_pending(timer))
		return 0;

806 807 808
	if (hlist_is_singular_node(&timer->entry, base->vectors + idx))
		__clear_bit(idx, base->pending_map);

809 810 811 812
	detach_timer(timer, clear_pending);
	return 1;
}

813 814 815 816 817
static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
{
	struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_STD], cpu);

	/*
818 819
	 * If the timer is deferrable and NO_HZ_COMMON is set then we need
	 * to use the deferrable base.
820
	 */
821
	if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
822 823 824 825 826 827 828 829 830
		base = per_cpu_ptr(&timer_bases[BASE_DEF], cpu);
	return base;
}

static inline struct timer_base *get_timer_this_cpu_base(u32 tflags)
{
	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);

	/*
831 832
	 * If the timer is deferrable and NO_HZ_COMMON is set then we need
	 * to use the deferrable base.
833
	 */
834
	if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
835 836 837 838 839 840 841 842 843
		base = this_cpu_ptr(&timer_bases[BASE_DEF]);
	return base;
}

static inline struct timer_base *get_timer_base(u32 tflags)
{
	return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
}

844 845
#ifdef CONFIG_NO_HZ_COMMON
static inline struct timer_base *
846
get_target_base(struct timer_base *base, unsigned tflags)
847
{
848
#ifdef CONFIG_SMP
849 850 851 852 853 854 855 856
	if ((tflags & TIMER_PINNED) || !base->migration_enabled)
		return get_timer_this_cpu_base(tflags);
	return get_timer_cpu_base(tflags, get_nohz_timer_target());
#else
	return get_timer_this_cpu_base(tflags);
#endif
}

857 858
static inline void forward_timer_base(struct timer_base *base)
{
859
	unsigned long jnow;
860

861
	/*
862 863 864
	 * We only forward the base when we are idle or have just come out of
	 * idle (must_forward_clk logic), and have a delta between base clock
	 * and jiffies. In the common case, run_timers will take care of it.
865
	 */
866 867 868 869 870 871
	if (likely(!base->must_forward_clk))
		return;

	jnow = READ_ONCE(jiffies);
	base->must_forward_clk = base->is_idle;
	if ((long)(jnow - base->clk) < 2)
872 873 874 875 876 877
		return;

	/*
	 * If the next expiry value is > jiffies, then we fast forward to
	 * jiffies otherwise we forward to the next expiry value.
	 */
878 879
	if (time_after(base->next_expiry, jnow))
		base->clk = jnow;
880 881 882 883 884
	else
		base->clk = base->next_expiry;
}
#else
static inline struct timer_base *
885
get_target_base(struct timer_base *base, unsigned tflags)
886 887 888 889 890 891 892 893
{
	return get_timer_this_cpu_base(tflags);
}

static inline void forward_timer_base(struct timer_base *base) { }
#endif


894
/*
895 896 897
 * We are using hashed locking: Holding per_cpu(timer_bases[x]).lock means
 * that all timers which are tied to this base are locked, and the base itself
 * is locked too.
898 899
 *
 * So __run_timers/migrate_timers can safely modify all timers which could
900
 * be found in the base->vectors array.
901
 *
902 903
 * When a timer is migrating then the TIMER_MIGRATING flag is set and we need
 * to wait until the migration is done.
904
 */
905
static struct timer_base *lock_timer_base(struct timer_list *timer,
906
					  unsigned long *flags)
907
	__acquires(timer->base->lock)
908 909
{
	for (;;) {
910
		struct timer_base *base;
911 912 913 914 915 916 917 918
		u32 tf;

		/*
		 * We need to use READ_ONCE() here, otherwise the compiler
		 * might re-read @tf between the check for TIMER_MIGRATING
		 * and spin_lock().
		 */
		tf = READ_ONCE(timer->flags);
919 920

		if (!(tf & TIMER_MIGRATING)) {
921
			base = get_timer_base(tf);
922
			raw_spin_lock_irqsave(&base->lock, *flags);
923
			if (timer->flags == tf)
924
				return base;
925
			raw_spin_unlock_irqrestore(&base->lock, *flags);
926 927 928 929 930
		}
		cpu_relax();
	}
}

Ingo Molnar's avatar
Ingo Molnar committed
931
static inline int
932
__mod_timer(struct timer_list *timer, unsigned long expires, bool pending_only)
Linus Torvalds's avatar
Linus Torvalds committed
933
{
934
	struct timer_base *base, *new_base;
935 936
	unsigned int idx = UINT_MAX;
	unsigned long clk = 0, flags;
937
	int ret = 0;
Linus Torvalds's avatar
Linus Torvalds committed
938

939 940
	BUG_ON(!timer->function);

941
	/*
942 943 944
	 * This is a common optimization triggered by the networking code - if
	 * the timer is re-modified to have the same timeout or ends up in the
	 * same array bucket then just return:
945 946
	 */
	if (timer_pending(timer)) {
947 948 949 950 951
		/*
		 * The downside of this optimization is that it can result in
		 * larger granularity than you would get from adding a new
		 * timer with this expiry.
		 */
952 953
		if (timer->expires == expires)
			return 1;
954

955
		/*
956 957 958 959
		 * We lock timer base and calculate the bucket index right
		 * here. If the timer ends up in the same bucket, then we
		 * just update the expiry time and avoid the whole
		 * dequeue/enqueue dance.
960
		 */
961
		base = lock_timer_base(timer, &flags);
962
		forward_timer_base(base);
963

964
		clk = base->clk;
965 966 967 968 969 970 971 972 973
		idx = calc_wheel_index(expires, clk);

		/*
		 * Retrieve and compare the array index of the pending
		 * timer. If it matches set the expiry to the new value so a
		 * subsequent call will exit in the expires check above.
		 */
		if (idx == timer_get_idx(timer)) {
			timer->expires = expires;
974 975
			ret = 1;
			goto out_unlock;
976
		}
977 978
	} else {
		base = lock_timer_base(timer, &flags);
979
		forward_timer_base(base);
980 981
	}

982 983 984
	ret = detach_if_pending(timer, base, false);
	if (!ret && pending_only)
		goto out_unlock;
985

986
	new_base = get_target_base(base, timer->flags);
987

988
	if (base != new_base) {
Linus Torvalds's avatar
Linus Torvalds committed
989
		/*
990
		 * We are trying to schedule the timer on the new base.
991 992
		 * However we can't change timer's base while it is running,
		 * otherwise del_timer_sync() can't detect that the timer's
993 994
		 * handler yet has not finished. This also guarantees that the
		 * timer is serialized wrt itself.
Linus Torvalds's avatar
Linus Torvalds committed
995
		 */
996
		if (likely(base->running_timer != timer)) {
997
			/* See the comment in lock_timer_base() */
998 999
			timer->flags |= TIMER_MIGRATING;

1000
			raw_spin_unlock(&base->lock);
1001
			base = new_base;
1002
			raw_spin_lock(&base->lock);
1003 1004
			WRITE_ONCE(timer->flags,
				   (timer->flags & ~TIMER_BASEMASK) | base->cpu);
1005
			forward_timer_base(base);
Linus Torvalds's avatar
Linus Torvalds committed
1006 1007 1008
		}
	}

1009 1010
	debug_activate(timer, expires);

Linus Torvalds's avatar
Linus Torvalds committed
1011
	timer->expires = expires;
1012 1013
	/*
	 * If 'idx' was calculated above and the base time did not advance
1014 1015 1016 1017
	 * between calculating 'idx' and possibly switching the base, only
	 * enqueue_timer() and trigger_dyntick_cpu() is required. Otherwise
	 * we need to (re)calculate the wheel index via
	 * internal_add_timer().
1018 1019 1020 1021 1022 1023 1024
	 */
	if (idx != UINT_MAX && clk == base->clk) {
		enqueue_timer(base, timer, idx);
		trigger_dyntick_cpu(base, timer);
	} else {
		internal_add_timer(base, timer);
	}
Ingo Molnar's avatar
Ingo Molnar committed
1025 1026

out_unlock:
1027
	raw_spin_unlock_irqrestore(&base->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
1028 1029 1030 1031

	return ret;
}

1032
/**
Ingo Molnar's avatar
Ingo Molnar committed
1033 1034 1035
 * mod_timer_pending - modify a pending timer's timeout
 * @timer: the pending timer to be modified
 * @expires: new timeout in jiffies
Linus Torvalds's avatar
Linus Torvalds committed
1036
 *
Ingo Molnar's avatar
Ingo Molnar committed
1037 1038 1039 1040
 * mod_timer_pending() is the same for pending timers as mod_timer(),
 * but will not re-activate and modify already deleted timers.
 *
 * It is useful for unserialized use of timers.
Linus Torvalds's avatar
Linus Torvalds committed
1041
 */
Ingo Molnar's avatar
Ingo Molnar committed
1042
int mod_timer_pending(struct timer_list *timer, unsigned long expires)
Linus Torvalds's avatar
Linus Torvalds committed
1043
{
1044
	return __mod_timer(timer, expires, true);
Linus Torvalds's avatar
Linus Torvalds committed
1045
}
Ingo Molnar's avatar
Ingo Molnar committed
1046
EXPORT_SYMBOL(mod_timer_pending);
Linus Torvalds's avatar
Linus Torvalds committed
1047

1048
/**
Linus Torvalds's avatar
Linus Torvalds committed
1049 1050
 * mod_timer - modify a timer's timeout
 * @timer: the timer to be modified
1051
 * @expires: new timeout in jiffies
Linus Torvalds's avatar
Linus Torvalds committed
1052
 *
1053
 * mod_timer() is a more efficient way to update the expire field of an
Linus Torvalds's avatar
Linus Torvalds committed
1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
 * active timer (if the timer is inactive it will be activated)
 *
 * mod_timer(timer, expires) is equivalent to:
 *
 *     del_timer(timer); timer->expires = expires; add_timer(timer);
 *
 * Note that if there are multiple unserialized concurrent users of the
 * same timer, then mod_timer() is the only safe way to modify the timeout,
 * since add_timer() cannot modify an already running timer.
 *
 * The function returns whether it has modified a pending timer or not.
 * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
 * active timer returns 1.)
 */
int mod_timer(struct timer_list *timer, unsigned long expires)
{
1070
	return __mod_timer(timer, expires, false);
Linus Torvalds's avatar
Linus Torvalds committed
1071 1072 1073
}
EXPORT_SYMBOL(mod_timer);

Ingo Molnar's avatar
Ingo Molnar committed
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103
/**
 * add_timer - start a timer
 * @timer: the timer to be added
 *
 * The kernel will do a ->function(->data) callback from the
 * timer interrupt at the ->expires point in the future. The
 * current time is 'jiffies'.
 *
 * The timer's ->expires, ->function (and if the handler uses it, ->data)
 * fields must be set prior calling this function.
 *
 * Timers with an ->expires field in the past will be executed in the next
 * timer tick.
 */
void add_timer(struct timer_list *timer)
{
	BUG_ON(timer_pending(timer));
	mod_timer(timer, timer->expires);
}
EXPORT_SYMBOL(add_timer);

/**
 * add_timer_on - start a timer on a particular CPU
 * @timer: the timer to be added
 * @cpu: the CPU to start it on
 *
 * This is not very scalable on SMP. Double adds are not possible.
 */
void add_timer_on(struct timer_list *timer, int cpu)
{
1104
	struct timer_base *new_base, *base;
Ingo Molnar's avatar
Ingo Molnar committed
1105 1106 1107
	unsigned long flags;

	BUG_ON(timer_pending(timer) || !timer->function);
1108

1109 1110
	new_base = get_timer_cpu_base(timer->flags, cpu);

1111 1112 1113 1114 1115 1116 1117 1118 1119
	/*
	 * If @timer was on a different CPU, it should be migrated with the
	 * old base locked to prevent other operations proceeding with the
	 * wrong base locked.  See lock_timer_base().
	 */
	base = lock_timer_base(timer, &flags);
	if (base != new_base) {
		timer->flags |= TIMER_MIGRATING;

1120
		raw_spin_unlock(&base->lock);
1121
		base = new_base;
1122
		raw_spin_lock(&base->lock);
1123 1124 1125
		WRITE_ONCE(timer->flags,
			   (timer->flags & ~TIMER_BASEMASK) | cpu);
	}
1126
	forward_timer_base(base);
1127

1128
	debug_activate(timer, timer->expires);
Ingo Molnar's avatar
Ingo Molnar committed
1129
	internal_add_timer(base, timer);
1130
	raw_spin_unlock_irqrestore(&base->lock, flags);
Ingo Molnar's avatar
Ingo Molnar committed
1131
}
Andi Kleen's avatar
Andi Kleen committed
1132
EXPORT_SYMBOL_GPL(add_timer_on);
Ingo Molnar's avatar
Ingo Molnar committed
1133

1134
/**
1135
 * del_timer - deactivate a timer.
Linus Torvalds's avatar
Linus Torvalds committed
1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146
 * @timer: the timer to be deactivated
 *
 * del_timer() deactivates a timer - this works on both active and inactive
 * timers.
 *
 * The function returns whether it has deactivated a pending timer or not.
 * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
 * active timer returns 1.)
 */
int del_timer(struct timer_list *timer)
{
1147
	struct timer_base *base;
Linus Torvalds's avatar
Linus Torvalds committed
1148
	unsigned long flags;
1149
	int ret = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1150

1151 1152
	debug_assert_init(timer);

1153 1154
	if (timer_pending(timer)) {
		base = lock_timer_base(timer, &flags);
1155
		ret = detach_if_pending(timer, base, true);
1156
		raw_spin_unlock_irqrestore(&base->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
1157 1158
	}

1159
	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1160 1161 1162
}
EXPORT_SYMBOL(del_timer);

1163 1164
/**
 * try_to_del_timer_sync - Try to deactivate a timer
1165
 * @timer: timer to delete
1166
 *
1167 1168 1169 1170 1171
 * This function tries to deactivate a timer. Upon successful (ret >= 0)
 * exit the timer is not queued and the handler is not running on any CPU.
 */
int try_to_del_timer_sync(struct timer_list *timer)
{
1172
	struct timer_base *base;
1173 1174 1175
	unsigned long flags;
	int ret = -1;

1176 1177
	debug_assert_init(timer);

1178 1179
	base = lock_timer_base(timer, &flags);

Kees Cook's avatar
Kees Cook committed
1180
	if (base->running_timer != timer)
Thomas Gleixner's avatar