tick-sched.c 32.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
/*
 *  linux/kernel/time/tick-sched.c
 *
 *  Copyright(C) 2005-2006, Thomas Gleixner <tglx@linutronix.de>
 *  Copyright(C) 2005-2007, Red Hat, Inc., Ingo Molnar
 *  Copyright(C) 2006-2007  Timesys Corp., Thomas Gleixner
 *
 *  No idle tick implementation for low and high resolution timers
 *
 *  Started by: Thomas Gleixner and Ingo Molnar
 *
P
Pavel Machek 已提交
12
 *  Distribute under GPLv2.
13 14 15 16 17 18 19 20 21
 */
#include <linux/cpu.h>
#include <linux/err.h>
#include <linux/hrtimer.h>
#include <linux/interrupt.h>
#include <linux/kernel_stat.h>
#include <linux/percpu.h>
#include <linux/profile.h>
#include <linux/sched.h>
22
#include <linux/module.h>
23
#include <linux/irq_work.h>
24
#include <linux/posix-timers.h>
25
#include <linux/context_tracking.h>
26

27 28
#include <asm/irq_regs.h>

29 30
#include "tick-internal.h"

F
Frederic Weisbecker 已提交
31 32
#include <trace/events/timer.h>

33 34 35
/*
 * Per cpu nohz control structure
 */
36
static DEFINE_PER_CPU(struct tick_sched, tick_cpu_sched);
37

38 39 40 41 42
struct tick_sched *tick_get_tick_sched(int cpu)
{
	return &per_cpu(tick_cpu_sched, cpu);
}

43 44 45 46 47 48
#if defined(CONFIG_NO_HZ_COMMON) || defined(CONFIG_HIGH_RES_TIMERS)
/*
 * The time, when the last jiffy update happened. Protected by jiffies_lock.
 */
static ktime_t last_jiffies_update;

49 50 51 52 53 54 55 56
/*
 * Must be called with interrupts disabled !
 */
static void tick_do_update_jiffies64(ktime_t now)
{
	unsigned long ticks = 0;
	ktime_t delta;

57
	/*
58
	 * Do a quick check without holding jiffies_lock:
59 60 61 62 63
	 */
	delta = ktime_sub(now, last_jiffies_update);
	if (delta.tv64 < tick_period.tv64)
		return;

64 65
	/* Reevalute with jiffies_lock held */
	write_seqlock(&jiffies_lock);
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

	delta = ktime_sub(now, last_jiffies_update);
	if (delta.tv64 >= tick_period.tv64) {

		delta = ktime_sub(delta, tick_period);
		last_jiffies_update = ktime_add(last_jiffies_update,
						tick_period);

		/* Slow path for long timeouts */
		if (unlikely(delta.tv64 >= tick_period.tv64)) {
			s64 incr = ktime_to_ns(tick_period);

			ticks = ktime_divns(delta, incr);

			last_jiffies_update = ktime_add_ns(last_jiffies_update,
							   incr * ticks);
		}
		do_timer(++ticks);
84 85 86

		/* Keep the tick_next_period variable up to date */
		tick_next_period = ktime_add(last_jiffies_update, tick_period);
87 88 89
	} else {
		write_sequnlock(&jiffies_lock);
		return;
90
	}
91
	write_sequnlock(&jiffies_lock);
92
	update_wall_time();
93 94 95 96 97 98 99 100 101
}

/*
 * Initialize and return retrieve the jiffies update.
 */
static ktime_t tick_init_jiffy_update(void)
{
	ktime_t period;

102
	write_seqlock(&jiffies_lock);
103 104 105 106
	/* Did we start the jiffies update yet ? */
	if (last_jiffies_update.tv64 == 0)
		last_jiffies_update = tick_next_period;
	period = last_jiffies_update;
107
	write_sequnlock(&jiffies_lock);
108 109 110
	return period;
}

111 112 113 114 115

static void tick_sched_do_timer(ktime_t now)
{
	int cpu = smp_processor_id();

116
#ifdef CONFIG_NO_HZ_COMMON
117 118 119 120 121
	/*
	 * Check if the do_timer duty was dropped. We don't care about
	 * concurrency: This happens only when the cpu in charge went
	 * into a long sleep. If two cpus happen to assign themself to
	 * this duty, then the jiffies update is still serialized by
122
	 * jiffies_lock.
123
	 */
124
	if (unlikely(tick_do_timer_cpu == TICK_DO_TIMER_NONE)
125
	    && !tick_nohz_full_cpu(cpu))
126 127 128 129 130 131 132 133
		tick_do_timer_cpu = cpu;
#endif

	/* Check, if the jiffies need an update */
	if (tick_do_timer_cpu == cpu)
		tick_do_update_jiffies64(now);
}

134 135
static void tick_sched_handle(struct tick_sched *ts, struct pt_regs *regs)
{
136
#ifdef CONFIG_NO_HZ_COMMON
137 138 139 140 141 142 143 144 145
	/*
	 * When we are idle and the tick is stopped, we have to touch
	 * the watchdog as we might not schedule for a really long
	 * time. This happens on complete idle SMP systems while
	 * waiting on the login prompt. We also increment the "start of
	 * idle" jiffy stamp so the idle accounting adjustment we do
	 * when we go busy again does not account too much ticks.
	 */
	if (ts->tick_stopped) {
146
		touch_softlockup_watchdog_sched();
147 148 149
		if (is_idle_task(current))
			ts->idle_jiffies++;
	}
150
#endif
151 152 153
	update_process_times(user_mode(regs));
	profile_tick(CPU_PROFILING);
}
154
#endif
155

156
#ifdef CONFIG_NO_HZ_FULL
157
cpumask_var_t tick_nohz_full_mask;
158
cpumask_var_t housekeeping_mask;
159
bool tick_nohz_full_running;
160
static unsigned long tick_dep_mask;
161

162 163 164
static void trace_tick_dependency(unsigned long dep)
{
	if (dep & TICK_DEP_MASK_POSIX_TIMER) {
165
		trace_tick_stop(0, TICK_DEP_MASK_POSIX_TIMER);
166 167 168 169
		return;
	}

	if (dep & TICK_DEP_MASK_PERF_EVENTS) {
170
		trace_tick_stop(0, TICK_DEP_MASK_PERF_EVENTS);
171 172 173 174
		return;
	}

	if (dep & TICK_DEP_MASK_SCHED) {
175
		trace_tick_stop(0, TICK_DEP_MASK_SCHED);
176 177 178 179
		return;
	}

	if (dep & TICK_DEP_MASK_CLOCK_UNSTABLE)
180
		trace_tick_stop(0, TICK_DEP_MASK_CLOCK_UNSTABLE);
181 182 183
}

static bool can_stop_full_tick(struct tick_sched *ts)
184 185 186
{
	WARN_ON_ONCE(!irqs_disabled());

187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
	if (tick_dep_mask) {
		trace_tick_dependency(tick_dep_mask);
		return false;
	}

	if (ts->tick_dep_mask) {
		trace_tick_dependency(ts->tick_dep_mask);
		return false;
	}

	if (current->tick_dep_mask) {
		trace_tick_dependency(current->tick_dep_mask);
		return false;
	}

	if (current->signal->tick_dep_mask) {
		trace_tick_dependency(current->signal->tick_dep_mask);
		return false;
	}

207 208
#ifdef CONFIG_HAVE_UNSTABLE_SCHED_CLOCK
	/*
209 210
	 * sched_clock_tick() needs us?
	 *
211 212 213
	 * TODO: kick full dynticks CPUs when
	 * sched_clock_stable is set.
	 */
214
	if (!sched_clock_stable()) {
215
		trace_tick_stop(0, TICK_DEP_MASK_CLOCK_UNSTABLE);
216 217 218 219
		/*
		 * Don't allow the user to think they can get
		 * full NO_HZ with this machine.
		 */
220
		WARN_ONCE(tick_nohz_full_running,
221
			  "NO_HZ FULL will not work with unstable sched clock");
222
		return false;
F
Frederic Weisbecker 已提交
223
	}
224 225 226 227 228
#endif

	return true;
}

229
static void nohz_full_kick_func(struct irq_work *work)
230
{
231
	/* Empty, the tick restart happens on tick_nohz_irq_exit() */
232 233 234
}

static DEFINE_PER_CPU(struct irq_work, nohz_full_kick_work) = {
235
	.func = nohz_full_kick_func,
236 237
};

238 239 240 241 242 243
/*
 * Kick this CPU if it's full dynticks in order to force it to
 * re-evaluate its dependency on the tick and restart it if necessary.
 * This kick, unlike tick_nohz_full_kick_cpu() and tick_nohz_full_kick_all(),
 * is NMI safe.
 */
244
static void tick_nohz_full_kick(void)
245 246 247 248
{
	if (!tick_nohz_full_cpu(smp_processor_id()))
		return;

249
	irq_work_queue(this_cpu_ptr(&nohz_full_kick_work));
250 251
}

252
/*
253
 * Kick the CPU if it's full dynticks in order to force it to
254 255
 * re-evaluate its dependency on the tick and restart it if necessary.
 */
256
void tick_nohz_full_kick_cpu(int cpu)
257
{
258 259 260 261
	if (!tick_nohz_full_cpu(cpu))
		return;

	irq_work_queue_on(&per_cpu(nohz_full_kick_work, cpu), cpu);
262 263 264 265 266 267
}

/*
 * Kick all full dynticks CPUs in order to force these to re-evaluate
 * their dependency on the tick and restart it if necessary.
 */
268
static void tick_nohz_full_kick_all(void)
269
{
270 271
	int cpu;

272
	if (!tick_nohz_full_running)
273 274 275
		return;

	preempt_disable();
276 277
	for_each_cpu_and(cpu, tick_nohz_full_mask, cpu_online_mask)
		tick_nohz_full_kick_cpu(cpu);
278 279 280
	preempt_enable();
}

281 282 283 284 285 286 287 288 289 290 291 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 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
static void tick_nohz_dep_set_all(unsigned long *dep,
				  enum tick_dep_bits bit)
{
	unsigned long prev;

	prev = fetch_or(dep, BIT_MASK(bit));
	if (!prev)
		tick_nohz_full_kick_all();
}

/*
 * Set a global tick dependency. Used by perf events that rely on freq and
 * by unstable clock.
 */
void tick_nohz_dep_set(enum tick_dep_bits bit)
{
	tick_nohz_dep_set_all(&tick_dep_mask, bit);
}

void tick_nohz_dep_clear(enum tick_dep_bits bit)
{
	clear_bit(bit, &tick_dep_mask);
}

/*
 * Set per-CPU tick dependency. Used by scheduler and perf events in order to
 * manage events throttling.
 */
void tick_nohz_dep_set_cpu(int cpu, enum tick_dep_bits bit)
{
	unsigned long prev;
	struct tick_sched *ts;

	ts = per_cpu_ptr(&tick_cpu_sched, cpu);

	prev = fetch_or(&ts->tick_dep_mask, BIT_MASK(bit));
	if (!prev) {
		preempt_disable();
		/* Perf needs local kick that is NMI safe */
		if (cpu == smp_processor_id()) {
			tick_nohz_full_kick();
		} else {
			/* Remote irq work not NMI-safe */
			if (!WARN_ON_ONCE(in_nmi()))
				tick_nohz_full_kick_cpu(cpu);
		}
		preempt_enable();
	}
}

void tick_nohz_dep_clear_cpu(int cpu, enum tick_dep_bits bit)
{
	struct tick_sched *ts = per_cpu_ptr(&tick_cpu_sched, cpu);

	clear_bit(bit, &ts->tick_dep_mask);
}

/*
 * Set a per-task tick dependency. Posix CPU timers need this in order to elapse
 * per task timers.
 */
void tick_nohz_dep_set_task(struct task_struct *tsk, enum tick_dep_bits bit)
{
	/*
	 * We could optimize this with just kicking the target running the task
	 * if that noise matters for nohz full users.
	 */
	tick_nohz_dep_set_all(&tsk->tick_dep_mask, bit);
}

void tick_nohz_dep_clear_task(struct task_struct *tsk, enum tick_dep_bits bit)
{
	clear_bit(bit, &tsk->tick_dep_mask);
}

/*
 * Set a per-taskgroup tick dependency. Posix CPU timers need this in order to elapse
 * per process timers.
 */
void tick_nohz_dep_set_signal(struct signal_struct *sig, enum tick_dep_bits bit)
{
	tick_nohz_dep_set_all(&sig->tick_dep_mask, bit);
}

void tick_nohz_dep_clear_signal(struct signal_struct *sig, enum tick_dep_bits bit)
{
	clear_bit(bit, &sig->tick_dep_mask);
}

370 371 372 373 374
/*
 * Re-evaluate the need for the tick as we switch the current task.
 * It might need the tick due to per task/process properties:
 * perf events, posix cpu timers, ...
 */
375
void __tick_nohz_task_switch(void)
376 377
{
	unsigned long flags;
378
	struct tick_sched *ts;
379 380 381

	local_irq_save(flags);

382 383 384
	if (!tick_nohz_full_cpu(smp_processor_id()))
		goto out;

385
	ts = this_cpu_ptr(&tick_cpu_sched);
386

387 388 389 390
	if (ts->tick_stopped) {
		if (current->tick_dep_mask || current->signal->tick_dep_mask)
			tick_nohz_full_kick();
	}
391
out:
392 393 394
	local_irq_restore(flags);
}

395
/* Parse the boot-time nohz CPU list from the kernel parameters. */
396
static int __init tick_nohz_full_setup(char *str)
397
{
398 399
	alloc_bootmem_cpumask_var(&tick_nohz_full_mask);
	if (cpulist_parse(str, tick_nohz_full_mask) < 0) {
400
		pr_warning("NOHZ: Incorrect nohz_full cpumask\n");
401
		free_bootmem_cpumask_var(tick_nohz_full_mask);
402 403
		return 1;
	}
404
	tick_nohz_full_running = true;
405

406 407
	return 1;
}
408
__setup("nohz_full=", tick_nohz_full_setup);
409

410
static int tick_nohz_cpu_down_callback(struct notifier_block *nfb,
411 412
				       unsigned long action,
				       void *hcpu)
413 414 415 416 417 418
{
	unsigned int cpu = (unsigned long)hcpu;

	switch (action & ~CPU_TASKS_FROZEN) {
	case CPU_DOWN_PREPARE:
		/*
419 420 421
		 * The boot CPU handles housekeeping duty (unbound timers,
		 * workqueues, timekeeping, ...) on behalf of full dynticks
		 * CPUs. It must remain online when nohz full is enabled.
422
		 */
423
		if (tick_nohz_full_running && tick_do_timer_cpu == cpu)
424
			return NOTIFY_BAD;
425 426 427 428 429
		break;
	}
	return NOTIFY_OK;
}

430 431 432 433 434
static int tick_nohz_init_all(void)
{
	int err = -1;

#ifdef CONFIG_NO_HZ_FULL_ALL
435
	if (!alloc_cpumask_var(&tick_nohz_full_mask, GFP_KERNEL)) {
436
		WARN(1, "NO_HZ: Can't allocate full dynticks cpumask\n");
437 438
		return err;
	}
439
	err = 0;
440 441
	cpumask_setall(tick_nohz_full_mask);
	tick_nohz_full_running = true;
442 443 444 445
#endif
	return err;
}

446
void __init tick_nohz_init(void)
447
{
448 449
	int cpu;

450
	if (!tick_nohz_full_running) {
451 452 453
		if (tick_nohz_init_all() < 0)
			return;
	}
454

455 456 457 458 459 460 461
	if (!alloc_cpumask_var(&housekeeping_mask, GFP_KERNEL)) {
		WARN(1, "NO_HZ: Can't allocate not-full dynticks cpumask\n");
		cpumask_clear(tick_nohz_full_mask);
		tick_nohz_full_running = false;
		return;
	}

462 463 464 465 466 467 468 469 470 471 472 473 474 475
	/*
	 * Full dynticks uses irq work to drive the tick rescheduling on safe
	 * locking contexts. But then we need irq work to raise its own
	 * interrupts to avoid circular dependency on the tick
	 */
	if (!arch_irq_work_has_interrupt()) {
		pr_warning("NO_HZ: Can't run full dynticks because arch doesn't "
			   "support irq work self-IPIs\n");
		cpumask_clear(tick_nohz_full_mask);
		cpumask_copy(housekeeping_mask, cpu_possible_mask);
		tick_nohz_full_running = false;
		return;
	}

476 477 478 479 480 481 482 483 484 485
	cpu = smp_processor_id();

	if (cpumask_test_cpu(cpu, tick_nohz_full_mask)) {
		pr_warning("NO_HZ: Clearing %d from nohz_full range for timekeeping\n", cpu);
		cpumask_clear_cpu(cpu, tick_nohz_full_mask);
	}

	cpumask_andnot(housekeeping_mask,
		       cpu_possible_mask, tick_nohz_full_mask);

486
	for_each_cpu(cpu, tick_nohz_full_mask)
487 488
		context_tracking_cpu_set(cpu);

489
	cpu_notifier(tick_nohz_cpu_down_callback, 0);
490 491
	pr_info("NO_HZ: Full dynticks CPUs: %*pbl.\n",
		cpumask_pr_args(tick_nohz_full_mask));
492 493 494 495 496 497

	/*
	 * We need at least one CPU to handle housekeeping work such
	 * as timekeeping, unbound timers, workqueues, ...
	 */
	WARN_ON_ONCE(cpumask_empty(housekeeping_mask));
498 499 500
}
#endif

501 502 503
/*
 * NOHZ - aka dynamic tick functionality
 */
504
#ifdef CONFIG_NO_HZ_COMMON
505 506 507
/*
 * NO HZ enabled ?
 */
508
int tick_nohz_enabled __read_mostly = 1;
509
unsigned long tick_nohz_active  __read_mostly;
510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525
/*
 * Enable / Disable tickless mode
 */
static int __init setup_tick_nohz(char *str)
{
	if (!strcmp(str, "off"))
		tick_nohz_enabled = 0;
	else if (!strcmp(str, "on"))
		tick_nohz_enabled = 1;
	else
		return 0;
	return 1;
}

__setup("nohz=", setup_tick_nohz);

526 527 528 529 530
int tick_nohz_tick_stopped(void)
{
	return __this_cpu_read(tick_cpu_sched.tick_stopped);
}

531 532 533 534 535 536 537 538 539 540
/**
 * tick_nohz_update_jiffies - update jiffies when idle was interrupted
 *
 * Called from interrupt entry when the CPU was idle
 *
 * In case the sched_tick was stopped on this CPU, we have to check if jiffies
 * must be updated. Otherwise an interrupt handler could use a stale jiffy
 * value. We do this unconditionally on any cpu, as we don't know whether the
 * cpu, which has the update task assigned is in a long sleep.
 */
541
static void tick_nohz_update_jiffies(ktime_t now)
542 543 544
{
	unsigned long flags;

545
	__this_cpu_write(tick_cpu_sched.idle_waketime, now);
546 547 548 549

	local_irq_save(flags);
	tick_do_update_jiffies64(now);
	local_irq_restore(flags);
550

551
	touch_softlockup_watchdog_sched();
552 553
}

554 555 556
/*
 * Updates the per cpu time idle statistics counters
 */
557
static void
558
update_ts_time_stats(int cpu, struct tick_sched *ts, ktime_t now, u64 *last_update_time)
559
{
560
	ktime_t delta;
561

562 563
	if (ts->idle_active) {
		delta = ktime_sub(now, ts->idle_entrytime);
564
		if (nr_iowait_cpu(cpu) > 0)
565
			ts->iowait_sleeptime = ktime_add(ts->iowait_sleeptime, delta);
566 567
		else
			ts->idle_sleeptime = ktime_add(ts->idle_sleeptime, delta);
568
		ts->idle_entrytime = now;
569
	}
570

571
	if (last_update_time)
572 573
		*last_update_time = ktime_to_us(now);

574 575
}

576
static void tick_nohz_stop_idle(struct tick_sched *ts, ktime_t now)
577
{
578
	update_ts_time_stats(smp_processor_id(), ts, now, NULL);
579
	ts->idle_active = 0;
580

581
	sched_clock_idle_wakeup_event(0);
582 583
}

584
static ktime_t tick_nohz_start_idle(struct tick_sched *ts)
585
{
586
	ktime_t now = ktime_get();
587

588 589
	ts->idle_entrytime = now;
	ts->idle_active = 1;
590
	sched_clock_idle_sleep_event();
591 592 593
	return now;
}

594 595 596
/**
 * get_cpu_idle_time_us - get the total idle time of a cpu
 * @cpu: CPU number to query
597 598
 * @last_update_time: variable to store update time in. Do not update
 * counters if NULL.
599 600
 *
 * Return the cummulative idle time (since boot) for a given
601
 * CPU, in microseconds.
602 603 604 605 606 607
 *
 * This time is measured via accounting rather than sampling,
 * and is as accurate as ktime_get() is.
 *
 * This function returns -1 if NOHZ is not enabled.
 */
608 609 610
u64 get_cpu_idle_time_us(int cpu, u64 *last_update_time)
{
	struct tick_sched *ts = &per_cpu(tick_cpu_sched, cpu);
611
	ktime_t now, idle;
612

613
	if (!tick_nohz_active)
614 615
		return -1;

616 617 618 619 620 621 622 623 624 625 626 627 628 629 630
	now = ktime_get();
	if (last_update_time) {
		update_ts_time_stats(cpu, ts, now, last_update_time);
		idle = ts->idle_sleeptime;
	} else {
		if (ts->idle_active && !nr_iowait_cpu(cpu)) {
			ktime_t delta = ktime_sub(now, ts->idle_entrytime);

			idle = ktime_add(ts->idle_sleeptime, delta);
		} else {
			idle = ts->idle_sleeptime;
		}
	}

	return ktime_to_us(idle);
631

632
}
633
EXPORT_SYMBOL_GPL(get_cpu_idle_time_us);
634

635
/**
636 637
 * get_cpu_iowait_time_us - get the total iowait time of a cpu
 * @cpu: CPU number to query
638 639
 * @last_update_time: variable to store update time in. Do not update
 * counters if NULL.
640 641 642 643 644 645 646 647 648 649 650 651
 *
 * Return the cummulative iowait time (since boot) for a given
 * CPU, in microseconds.
 *
 * This time is measured via accounting rather than sampling,
 * and is as accurate as ktime_get() is.
 *
 * This function returns -1 if NOHZ is not enabled.
 */
u64 get_cpu_iowait_time_us(int cpu, u64 *last_update_time)
{
	struct tick_sched *ts = &per_cpu(tick_cpu_sched, cpu);
652
	ktime_t now, iowait;
653

654
	if (!tick_nohz_active)
655 656
		return -1;

657 658 659 660 661 662 663
	now = ktime_get();
	if (last_update_time) {
		update_ts_time_stats(cpu, ts, now, last_update_time);
		iowait = ts->iowait_sleeptime;
	} else {
		if (ts->idle_active && nr_iowait_cpu(cpu) > 0) {
			ktime_t delta = ktime_sub(now, ts->idle_entrytime);
664

665 666 667 668 669
			iowait = ktime_add(ts->iowait_sleeptime, delta);
		} else {
			iowait = ts->iowait_sleeptime;
		}
	}
670

671
	return ktime_to_us(iowait);
672 673 674
}
EXPORT_SYMBOL_GPL(get_cpu_iowait_time_us);

675 676 677 678 679 680 681 682 683 684 685 686 687 688
static void tick_nohz_restart(struct tick_sched *ts, ktime_t now)
{
	hrtimer_cancel(&ts->sched_timer);
	hrtimer_set_expires(&ts->sched_timer, ts->last_tick);

	/* Forward the time to expire in the future */
	hrtimer_forward(&ts->sched_timer, now, tick_period);

	if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
		hrtimer_start_expires(&ts->sched_timer, HRTIMER_MODE_ABS_PINNED);
	else
		tick_program_event(hrtimer_get_expires(&ts->sched_timer), 1);
}

689 690
static ktime_t tick_nohz_stop_sched_tick(struct tick_sched *ts,
					 ktime_t now, int cpu)
691
{
692
	struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
693 694 695
	u64 basemono, next_tick, next_tmr, next_rcu, delta, expires;
	unsigned long seq, basejiff;
	ktime_t	tick;
696

697 698
	/* Read jiffies and the time when jiffies were updated last */
	do {
699
		seq = read_seqbegin(&jiffies_lock);
700 701
		basemono = last_jiffies_update.tv64;
		basejiff = jiffies;
702
	} while (read_seqretry(&jiffies_lock, seq));
703
	ts->last_jiffies = basejiff;
704

705
	if (rcu_needs_cpu(basemono, &next_rcu) ||
706
	    arch_needs_cpu() || irq_work_needs_cpu()) {
707
		next_tick = basemono + TICK_NSEC;
708
	} else {
709 710 711 712 713 714 715 716 717 718 719
		/*
		 * Get the next pending timer. If high resolution
		 * timers are enabled this only takes the timer wheel
		 * timers into account. If high resolution timers are
		 * disabled this also looks at the next expiring
		 * hrtimer.
		 */
		next_tmr = get_next_timer_interrupt(basejiff, basemono);
		ts->next_timer = next_tmr;
		/* Take the next rcu event into account */
		next_tick = next_rcu < next_tmr ? next_rcu : next_tmr;
720
	}
721

722 723
	/*
	 * If the tick is due in the next period, keep it ticking or
724
	 * force prod the timer.
725 726 727 728
	 */
	delta = next_tick - basemono;
	if (delta <= (u64)TICK_NSEC) {
		tick.tv64 = 0;
729 730 731 732
		/*
		 * We've not stopped the tick yet, and there's a timer in the
		 * next period, so no point in stopping it either, bail.
		 */
T
Thomas Gleixner 已提交
733 734
		if (!ts->tick_stopped)
			goto out;
735 736 737 738 739 740 741 742 743 744 745 746 747

		/*
		 * If, OTOH, we did stop it, but there's a pending (expired)
		 * timer reprogram the timer hardware to fire now.
		 *
		 * We will not restart the tick proper, just prod the timer
		 * hardware into firing an interrupt to process the pending
		 * timers. Just like tick_irq_exit() will not restart the tick
		 * for 'normal' interrupts.
		 *
		 * Only once we exit the idle loop will we re-enable the tick,
		 * see tick_nohz_idle_exit().
		 */
748
		if (delta == 0) {
T
Thomas Gleixner 已提交
749 750 751 752 753
			tick_nohz_restart(ts, now);
			goto out;
		}
	}

754
	/*
T
Thomas Gleixner 已提交
755 756 757 758 759 760 761
	 * If this cpu is the one which updates jiffies, then give up
	 * the assignment and let it be taken by the cpu which runs
	 * the tick timer next, which might be this cpu as well. If we
	 * don't drop this here the jiffies might be stale and
	 * do_timer() never invoked. Keep track of the fact that it
	 * was the one which had the do_timer() duty last. If this cpu
	 * is the one which had the do_timer() duty last, we limit the
762 763
	 * sleep time to the timekeeping max_deferement value.
	 * Otherwise we can sleep as long as we want.
764
	 */
765
	delta = timekeeping_max_deferment();
T
Thomas Gleixner 已提交
766 767 768 769
	if (cpu == tick_do_timer_cpu) {
		tick_do_timer_cpu = TICK_DO_TIMER_NONE;
		ts->do_timer_last = 1;
	} else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
770
		delta = KTIME_MAX;
T
Thomas Gleixner 已提交
771 772
		ts->do_timer_last = 0;
	} else if (!ts->do_timer_last) {
773
		delta = KTIME_MAX;
T
Thomas Gleixner 已提交
774
	}
T
Thomas Gleixner 已提交
775

776
#ifdef CONFIG_NO_HZ_FULL
777
	/* Limit the tick delta to the maximum scheduler deferment */
T
Thomas Gleixner 已提交
778
	if (!ts->inidle)
779
		delta = min(delta, scheduler_tick_max_deferment());
780 781
#endif

782 783 784
	/* Calculate the next expiry time */
	if (delta < (KTIME_MAX - basemono))
		expires = basemono + delta;
T
Thomas Gleixner 已提交
785
	else
786 787 788 789
		expires = KTIME_MAX;

	expires = min_t(u64, expires, next_tick);
	tick.tv64 = expires;
790

T
Thomas Gleixner 已提交
791
	/* Skip reprogram of event if its not changed */
792
	if (ts->tick_stopped && (expires == dev->next_event.tv64))
T
Thomas Gleixner 已提交
793
		goto out;
794

T
Thomas Gleixner 已提交
795 796 797 798 799 800 801 802 803 804
	/*
	 * nohz_stop_sched_tick can be called several times before
	 * the nohz_restart_sched_tick is called. This happens when
	 * interrupts arrive which do not cause a reschedule. In the
	 * first call we save the current tick time, so we can restart
	 * the scheduler tick in nohz_restart_sched_tick.
	 */
	if (!ts->tick_stopped) {
		nohz_balance_enter_idle(cpu);
		calc_load_enter_idle();
805

T
Thomas Gleixner 已提交
806 807
		ts->last_tick = hrtimer_get_expires(&ts->sched_timer);
		ts->tick_stopped = 1;
808
		trace_tick_stop(1, TICK_DEP_MASK_NONE);
T
Thomas Gleixner 已提交
809
	}
810

T
Thomas Gleixner 已提交
811
	/*
812 813
	 * If the expiration time == KTIME_MAX, then we simply stop
	 * the tick timer.
T
Thomas Gleixner 已提交
814
	 */
815
	if (unlikely(expires == KTIME_MAX)) {
T
Thomas Gleixner 已提交
816 817 818
		if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
			hrtimer_cancel(&ts->sched_timer);
		goto out;
819
	}
820

T
Thomas Gleixner 已提交
821
	if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
822
		hrtimer_start(&ts->sched_timer, tick, HRTIMER_MODE_ABS_PINNED);
T
Thomas Gleixner 已提交
823
	else
824
		tick_program_event(tick, 1);
825
out:
826
	/* Update the estimated sleep length */
827
	ts->sleep_length = ktime_sub(dev->next_event, now);
828
	return tick;
829 830
}

831
static void tick_nohz_restart_sched_tick(struct tick_sched *ts, ktime_t now, int active)
832 833 834
{
	/* Update jiffies first */
	tick_do_update_jiffies64(now);
835
	update_cpu_load_nohz(active);
836 837

	calc_load_exit_idle();
838
	touch_softlockup_watchdog_sched();
839 840 841 842 843 844 845 846
	/*
	 * Cancel the scheduled timer and restore the tick
	 */
	ts->tick_stopped  = 0;
	ts->idle_exittime = now;

	tick_nohz_restart(ts, now);
}
847 848

static void tick_nohz_full_update_tick(struct tick_sched *ts)
849 850
{
#ifdef CONFIG_NO_HZ_FULL
851
	int cpu = smp_processor_id();
852

853
	if (!tick_nohz_full_cpu(cpu))
854
		return;
855

856 857
	if (!ts->tick_stopped && ts->nohz_mode == NOHZ_MODE_INACTIVE)
		return;
858

859
	if (can_stop_full_tick(ts))
860 861
		tick_nohz_stop_sched_tick(ts, ktime_get(), cpu);
	else if (ts->tick_stopped)
862
		tick_nohz_restart_sched_tick(ts, ktime_get(), 1);
863 864 865
#endif
}

866 867 868 869 870 871 872 873 874 875 876 877
static bool can_stop_idle_tick(int cpu, struct tick_sched *ts)
{
	/*
	 * If this cpu is offline and it is the one which updates
	 * jiffies, then give up the assignment and let it be taken by
	 * the cpu which runs the tick timer next. If we don't drop
	 * this here the jiffies might be stale and do_timer() never
	 * invoked.
	 */
	if (unlikely(!cpu_online(cpu))) {
		if (cpu == tick_do_timer_cpu)
			tick_do_timer_cpu = TICK_DO_TIMER_NONE;
878
		return false;
879 880
	}

881 882
	if (unlikely(ts->nohz_mode == NOHZ_MODE_INACTIVE)) {
		ts->sleep_length = (ktime_t) { .tv64 = NSEC_PER_SEC/HZ };
883
		return false;
884
	}
885 886 887 888 889 890 891

	if (need_resched())
		return false;

	if (unlikely(local_softirq_pending() && cpu_online(cpu))) {
		static int ratelimit;

892 893
		if (ratelimit < 10 &&
		    (local_softirq_pending() & SOFTIRQ_STOP_IDLE_MASK)) {
894 895
			pr_warn("NOHZ: local_softirq_pending %02x\n",
				(unsigned int) local_softirq_pending());
896 897 898 899 900
			ratelimit++;
		}
		return false;
	}

901
	if (tick_nohz_full_enabled()) {
902 903 904 905 906 907 908 909 910 911 912 913 914 915
		/*
		 * Keep the tick alive to guarantee timekeeping progression
		 * if there are full dynticks CPUs around
		 */
		if (tick_do_timer_cpu == cpu)
			return false;
		/*
		 * Boot safety: make sure the timekeeping duty has been
		 * assigned before entering dyntick-idle mode,
		 */
		if (tick_do_timer_cpu == TICK_DO_TIMER_NONE)
			return false;
	}

916 917 918
	return true;
}

919 920
static void __tick_nohz_idle_enter(struct tick_sched *ts)
{
921
	ktime_t now, expires;
922
	int cpu = smp_processor_id();
923

924
	now = tick_nohz_start_idle(ts);
925

926 927 928 929
	if (can_stop_idle_tick(cpu, ts)) {
		int was_stopped = ts->tick_stopped;

		ts->idle_calls++;
930 931 932 933 934 935

		expires = tick_nohz_stop_sched_tick(ts, now, cpu);
		if (expires.tv64 > 0LL) {
			ts->idle_sleeps++;
			ts->idle_expires = expires;
		}
936 937 938 939

		if (!was_stopped && ts->tick_stopped)
			ts->idle_jiffies = ts->last_jiffies;
	}
940 941 942 943 944 945 946
}

/**
 * tick_nohz_idle_enter - stop the idle tick from the idle task
 *
 * When the next event is more than a tick into the future, stop the idle tick
 * Called when we start the idle loop.
947
 *
948
 * The arch is responsible of calling:
949 950 951 952
 *
 * - rcu_idle_enter() after its last use of RCU before the CPU is put
 *  to sleep.
 * - rcu_idle_exit() before the first use of RCU after the CPU is woken up.
953
 */
954
void tick_nohz_idle_enter(void)
955 956 957
{
	struct tick_sched *ts;

958 959
	WARN_ON_ONCE(irqs_disabled());

960 961 962 963 964 965 966 967
	/*
 	 * Update the idle state in the scheduler domain hierarchy
 	 * when tick_nohz_stop_sched_tick() is called from the idle loop.
 	 * State will be updated to busy during the first busy tick after
 	 * exiting idle.
 	 */
	set_cpu_sd_state_idle();

968 969
	local_irq_disable();

970
	ts = this_cpu_ptr(&tick_cpu_sched);
971
	ts->inidle = 1;
972
	__tick_nohz_idle_enter(ts);
973 974

	local_irq_enable();
975 976 977 978 979 980 981 982 983 984 985 986
}

/**
 * tick_nohz_irq_exit - update next tick event from interrupt exit
 *
 * When an interrupt fires while we are idle and it doesn't cause
 * a reschedule, it may still add, modify or delete a timer, enqueue
 * an RCU callback, etc...
 * So we need to re-calculate and reprogram the next tick event.
 */
void tick_nohz_irq_exit(void)
{
987
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
988

989
	if (ts->inidle)
990
		__tick_nohz_idle_enter(ts);
991
	else
992
		tick_nohz_full_update_tick(ts);
993 994
}

995 996 997 998 999 1000 1001
/**
 * tick_nohz_get_sleep_length - return the length of the current sleep
 *
 * Called from power state control code with interrupts disabled
 */
ktime_t tick_nohz_get_sleep_length(void)
{
1002
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1003 1004 1005 1006

	return ts->sleep_length;
}

1007 1008
static void tick_nohz_account_idle_ticks(struct tick_sched *ts)
{
1009
#ifndef CONFIG_VIRT_CPU_ACCOUNTING_NATIVE
1010
	unsigned long ticks;
1011

1012
	if (vtime_accounting_cpu_enabled())
1013
		return;
1014 1015 1016 1017 1018 1019 1020 1021 1022
	/*
	 * We stopped the tick in idle. Update process times would miss the
	 * time we slept as update_process_times does only a 1 tick
	 * accounting. Enforce that this is accounted to idle !
	 */
	ticks = jiffies - ts->idle_jiffies;
	/*
	 * We might be one off. Do not randomly account a huge number of ticks!
	 */
1023 1024 1025
	if (ticks && ticks < LONG_MAX)
		account_idle_ticks(ticks);
#endif
1026 1027
}

1028
/**
1029
 * tick_nohz_idle_exit - restart the idle tick from the idle task
1030 1031
 *
 * Restart the idle tick when the CPU is woken up from idle
1032 1033
 * This also exit the RCU extended quiescent state. The CPU
 * can use RCU again after this function is called.
1034
 */
1035
void tick_nohz_idle_exit(void)
1036
{
1037
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1038
	ktime_t now;
1039

1040
	local_irq_disable();
1041

1042 1043 1044 1045 1046
	WARN_ON_ONCE(!ts->inidle);

	ts->inidle = 0;

	if (ts->idle_active || ts->tick_stopped)
1047 1048 1049
		now = ktime_get();

	if (ts->idle_active)
1050
		tick_nohz_stop_idle(ts, now);
1051

1052
	if (ts->tick_stopped) {
1053
		tick_nohz_restart_sched_tick(ts, now, 0);
1054
		tick_nohz_account_idle_ticks(ts);
1055
	}
1056 1057 1058 1059 1060 1061 1062 1063 1064

	local_irq_enable();
}

/*
 * The nohz low res interrupt handler
 */
static void tick_nohz_handler(struct clock_event_device *dev)
{
1065
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1066 1067 1068 1069 1070
	struct pt_regs *regs = get_irq_regs();
	ktime_t now = ktime_get();

	dev->next_event.tv64 = KTIME_MAX;

1071
	tick_sched_do_timer(now);
1072
	tick_sched_handle(ts, regs);
1073

1074 1075 1076 1077
	/* No need to reprogram if we are running tickless  */
	if (unlikely(ts->tick_stopped))
		return;

1078 1079
	hrtimer_forward(&ts->sched_timer, now, tick_period);
	tick_program_event(hrtimer_get_expires(&ts->sched_timer), 1);
1080 1081
}

1082 1083 1084 1085 1086 1087 1088
static inline void tick_nohz_activate(struct tick_sched *ts, int mode)
{
	if (!tick_nohz_enabled)
		return;
	ts->nohz_mode = mode;
	/* One update is enough */
	if (!test_and_set_bit(0, &tick_nohz_active))
1089
		timers_update_migration(true);
1090 1091
}

1092 1093 1094 1095 1096
/**
 * tick_nohz_switch_to_nohz - switch to nohz mode
 */
static void tick_nohz_switch_to_nohz(void)
{
1097
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1098 1099
	ktime_t next;

1100
	if (!tick_nohz_enabled)
1101 1102
		return;

1103
	if (tick_switch_to_oneshot(tick_nohz_handler))
1104
		return;
1105

1106 1107 1108 1109 1110 1111 1112 1113
	/*
	 * Recycle the hrtimer in ts, so we can share the
	 * hrtimer_forward with the highres code.
	 */
	hrtimer_init(&ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
	/* Get the next period */
	next = tick_init_jiffy_update();

1114
	hrtimer_set_expires(&ts->sched_timer, next);
1115 1116
	hrtimer_forward_now(&ts->sched_timer, tick_period);
	tick_program_event(hrtimer_get_expires(&ts->sched_timer), 1);
1117
	tick_nohz_activate(ts, NOHZ_MODE_LOWRES);
1118 1119
}

1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130
/*
 * When NOHZ is enabled and the tick is stopped, we need to kick the
 * tick timer from irq_enter() so that the jiffies update is kept
 * alive during long running softirqs. That's ugly as hell, but
 * correctness is key even if we need to fix the offending softirq in
 * the first place.
 *
 * Note, this is different to tick_nohz_restart. We just kick the
 * timer and do not touch the other magic bits which need to be done
 * when idle is left.
 */
1131
static void tick_nohz_kick_tick(struct tick_sched *ts, ktime_t now)
1132
{
1133 1134
#if 0
	/* Switch back to 2.6.27 behaviour */
1135
	ktime_t delta;
1136

1137 1138 1139 1140
	/*
	 * Do not touch the tick device, when the next expiry is either
	 * already reached or less/equal than the tick period.
	 */
1141
	delta =	ktime_sub(hrtimer_get_expires(&ts->sched_timer), now);
1142 1143 1144 1145
	if (delta.tv64 <= tick_period.tv64)
		return;

	tick_nohz_restart(ts, now);
1146
#endif
1147 1148
}

1149
static inline void tick_nohz_irq_enter(void)
1150
{
1151
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1152 1153 1154 1155 1156 1157
	ktime_t now;

	if (!ts->idle_active && !ts->tick_stopped)
		return;
	now = ktime_get();
	if (ts->idle_active)
1158
		tick_nohz_stop_idle(ts, now);
1159 1160
	if (ts->tick_stopped) {
		tick_nohz_update_jiffies(now);
1161
		tick_nohz_kick_tick(ts, now);
1162 1163 1164
	}
}

1165 1166 1167
#else

static inline void tick_nohz_switch_to_nohz(void) { }
1168
static inline void tick_nohz_irq_enter(void) { }
1169
static inline void tick_nohz_activate(struct tick_sched *ts, int mode) { }
1170

1171
#endif /* CONFIG_NO_HZ_COMMON */
1172

1173 1174 1175
/*
 * Called from irq_enter to notify about the possible interruption of idle()
 */
1176
void tick_irq_enter(void)
1177
{
1178
	tick_check_oneshot_broadcast_this_cpu();
1179
	tick_nohz_irq_enter();
1180 1181
}

1182 1183 1184 1185 1186
/*
 * High resolution timer specific code
 */
#ifdef CONFIG_HIGH_RES_TIMERS
/*
P
Pavel Machek 已提交
1187
 * We rearm the timer until we get disabled by the idle code.
1188
 * Called with interrupts disabled.
1189 1190 1191 1192 1193 1194 1195
 */
static enum hrtimer_restart tick_sched_timer(struct hrtimer *timer)
{
	struct tick_sched *ts =
		container_of(timer, struct tick_sched, sched_timer);
	struct pt_regs *regs = get_irq_regs();
	ktime_t now = ktime_get();
1196

1197
	tick_sched_do_timer(now);
1198 1199 1200 1201 1202

	/*
	 * Do not call, when we are not in irq context and have
	 * no valid regs pointer
	 */
1203 1204
	if (regs)
		tick_sched_handle(ts, regs);
1205

1206 1207 1208 1209
	/* No need to reprogram if we are in idle or full dynticks mode */
	if (unlikely(ts->tick_stopped))
		return HRTIMER_NORESTART;

1210 1211 1212 1213 1214
	hrtimer_forward(timer, now, tick_period);

	return HRTIMER_RESTART;
}

M
Mike Galbraith 已提交
1215 1216
static int sched_skew_tick;

1217 1218 1219 1220 1221 1222 1223 1224
static int __init skew_tick(char *str)
{
	get_option(&str, &sched_skew_tick);

	return 0;
}
early_param("skew_tick", skew_tick);

1225 1226 1227 1228 1229
/**
 * tick_setup_sched_timer - setup the tick emulation timer
 */
void tick_setup_sched_timer(void)
{
1230
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1231 1232 1233 1234 1235 1236 1237 1238
	ktime_t now = ktime_get();

	/*
	 * Emulate tick processing via per-CPU hrtimers:
	 */
	hrtimer_init(&ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
	ts->sched_timer.function = tick_sched_timer;

1239
	/* Get the next period (per cpu) */
1240
	hrtimer_set_expires(&ts->sched_timer, tick_init_jiffy_update());
1241

1242
	/* Offset the tick to avert jiffies_lock contention. */
M
Mike Galbraith 已提交
1243 1244 1245 1246 1247 1248 1249
	if (sched_skew_tick) {
		u64 offset = ktime_to_ns(tick_period) >> 1;
		do_div(offset, num_possible_cpus());
		offset *= smp_processor_id();
		hrtimer_add_expires_ns(&ts->sched_timer, offset);
	}

1250 1251
	hrtimer_forward(&ts->sched_timer, now, tick_period);
	hrtimer_start_expires(&ts->sched_timer, HRTIMER_MODE_ABS_PINNED);
1252
	tick_nohz_activate(ts, NOHZ_MODE_HIGHRES);
1253
}
1254
#endif /* HIGH_RES_TIMERS */
1255

1256
#if defined CONFIG_NO_HZ_COMMON || defined CONFIG_HIGH_RES_TIMERS
1257 1258 1259 1260
void tick_cancel_sched_timer(int cpu)
{
	struct tick_sched *ts = &per_cpu(tick_cpu_sched, cpu);

1261
# ifdef CONFIG_HIGH_RES_TIMERS
1262 1263
	if (ts->sched_timer.base)
		hrtimer_cancel(&ts->sched_timer);
1264
# endif
1265

1266
	memset(ts, 0, sizeof(*ts));
1267
}
1268
#endif
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285

/**
 * Async notification about clocksource changes
 */
void tick_clock_notify(void)
{
	int cpu;

	for_each_possible_cpu(cpu)
		set_bit(0, &per_cpu(tick_cpu_sched, cpu).check_clocks);
}

/*
 * Async notification about clock event changes
 */
void tick_oneshot_notify(void)
{
1286
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1287 1288 1289 1290 1291 1292 1293 1294 1295 1296

	set_bit(0, &ts->check_clocks);
}

/**
 * Check, if a change happened, which makes oneshot possible.
 *
 * Called cyclic from the hrtimer softirq (driven by the timer
 * softirq) allow_nohz signals, that we can switch into low-res nohz
 * mode, because high resolution timers are disabled (either compile
1297
 * or runtime). Called with interrupts disabled.
1298 1299 1300
 */
int tick_check_oneshot_change(int allow_nohz)
{
1301
	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
1302 1303 1304 1305 1306 1307 1308

	if (!test_and_clear_bit(0, &ts->check_clocks))
		return 0;

	if (ts->nohz_mode != NOHZ_MODE_INACTIVE)
		return 0;

1309
	if (!timekeeping_valid_for_hres() || !tick_is_oneshot_available())
1310 1311 1312 1313 1314 1315 1316 1317
		return 0;

	if (!allow_nohz)
		return 1;

	tick_nohz_switch_to_nohz();
	return 0;
}