Release 4.15 kernel/sched/clock.c

Directory: kernel/sched
/*
 * sched_clock for unstable cpu clocks
 *
 *  Copyright (C) 2008 Red Hat, Inc., Peter Zijlstra
 *
 *  Updates and enhancements:
 *    Copyright (C) 2008 Red Hat, Inc. Steven Rostedt <srostedt@redhat.com>
 *
 * Based on code by:
 *   Ingo Molnar <mingo@redhat.com>
 *   Guillaume Chazarain <guichaz@gmail.com>
 *
 *
 * What:
 *
 * cpu_clock(i) provides a fast (execution time) high resolution
 * clock with bounded drift between CPUs. The value of cpu_clock(i)
 * is monotonic for constant i. The timestamp returned is in nanoseconds.
 *
 * ######################### BIG FAT WARNING ##########################
 * # when comparing cpu_clock(i) to cpu_clock(j) for i != j, time can #
 * # go backwards !!                                                  #
 * ####################################################################
 *
 * There is no strict promise about the base, although it tends to start
 * at 0 on boot (but people really shouldn't rely on that).
 *
 * cpu_clock(i)       -- can be used from any context, including NMI.
 * local_clock()      -- is cpu_clock() on the current cpu.
 *
 * sched_clock_cpu(i)
 *
 * How:
 *
 * The implementation either uses sched_clock() when
 * !CONFIG_HAVE_UNSTABLE_SCHED_CLOCK, which means in that case the
 * sched_clock() is assumed to provide these properties (mostly it means
 * the architecture provides a globally synchronized highres time source).
 *
 * Otherwise it tries to create a semi stable clock from a mixture of other
 * clocks, including:
 *
 *  - GTOD (clock monotomic)
 *  - sched_clock()
 *  - explicit idle events
 *
 * We use GTOD as base and use sched_clock() deltas to improve resolution. The
 * deltas are filtered to provide monotonicity and keeping it within an
 * expected window.
 *
 * Furthermore, explicit sleep and wakeup hooks allow us to account for time
 * that is otherwise invisible (TSC gets stopped).
 *
 */
#include <linux/spinlock.h>
#include <linux/hardirq.h>
#include <linux/export.h>
#include <linux/percpu.h>
#include <linux/ktime.h>
#include <linux/sched.h>
#include <linux/nmi.h>
#include <linux/sched/clock.h>
#include <linux/static_key.h>
#include <linux/workqueue.h>
#include <linux/compiler.h>
#include <linux/tick.h>
#include <linux/init.h>

/*
 * Scheduler clock - returns current time in nanosec units.
 * This is default implementation.
 * Architectures and sub-architectures can override this.
 */


unsigned long long __weak sched_clock(void)
{
	return (unsigned long long)(jiffies - INITIAL_JIFFIES)
					* (NSEC_PER_SEC / HZ);
}
Contributors
Person Tokens Prop Commits CommitProp
Hugh Dickins 19 67.86% 1 33.33%
Ron 6 21.43% 1 33.33%
Gideon Israel Dsouza 3 10.71% 1 33.33%
Total 28 100.00% 3 100.00%


EXPORT_SYMBOL_GPL(sched_clock);


__read_mostly int sched_clock_running;



void sched_clock_init(void)
{
	sched_clock_running = 1;
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 11 100.00% 1 100.00%
Total 11 100.00% 1 100.00%

#ifdef CONFIG_HAVE_UNSTABLE_SCHED_CLOCK
/*
 * We must start with !__sched_clock_stable because the unstable -> stable
 * transition is accurate, while the stable -> unstable transition is not.
 *
 * Similarly we start with __sched_clock_stable_early, thereby assuming we
 * will become stable, such that there's only a single 1 -> 0 transition.
 */
static DEFINE_STATIC_KEY_FALSE(__sched_clock_stable);

static int __sched_clock_stable_early = 1;

/*
 * We want: ktime_get_ns() + __gtod_offset == sched_clock() + __sched_clock_offset
 */

__read_mostly u64 __sched_clock_offset;

static __read_mostly u64 __gtod_offset;


struct sched_clock_data {
	
u64			tick_raw;
	
u64			tick_gtod;
	
u64			clock;
};

static DEFINE_PER_CPU_SHARED_ALIGNED(struct sched_clock_data, sched_clock_data);



static inline struct sched_clock_data *this_scd(void)
{
	return this_cpu_ptr(&sched_clock_data);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 18 100.00% 1 100.00%
Total 18 100.00% 1 100.00%



static inline struct sched_clock_data *cpu_sdc(int cpu)
{
	return &per_cpu(sched_clock_data, cpu);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 21 100.00% 1 100.00%
Total 21 100.00% 1 100.00%



int sched_clock_stable(void)
{
	return static_branch_likely(&__sched_clock_stable);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 14 100.00% 3 100.00%
Total 14 100.00% 3 100.00%



static void __scd_stamp(struct sched_clock_data *scd)
{
	scd->tick_gtod = ktime_get_ns();
	scd->tick_raw = sched_clock();
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 25 100.00% 1 100.00%
Total 25 100.00% 1 100.00%



static void __set_sched_clock_stable(void)
{
	struct sched_clock_data *scd;

	/*
         * Since we're still unstable and the tick is already running, we have
         * to disable IRQs in order to get a consistent scd->tick* reading.
         */
	local_irq_disable();
	scd = this_scd();
	/*
         * Attempt to make the (initial) unstable->stable transition continuous.
         */
	__sched_clock_offset = (scd->tick_gtod + __gtod_offset) - (scd->tick_raw);
	local_irq_enable();

	printk(KERN_INFO "sched_clock: Marking stable (%lld, %lld)->(%lld, %lld)\n",
			scd->tick_gtod, __gtod_offset,
			scd->tick_raw,  __sched_clock_offset);

	static_branch_enable(&__sched_clock_stable);
	tick_dep_clear(TICK_DEP_BIT_CLOCK_UNSTABLE);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 66 92.96% 6 85.71%
Frédéric Weisbecker 5 7.04% 1 14.29%
Total 71 100.00% 7 100.00%

/*
 * If we ever get here, we're screwed, because we found out -- typically after
 * the fact -- that TSC wasn't good. This means all our clocksources (including
 * ktime) could have reported wrong values.
 *
 * What we do here is an attempt to fix up and continue sort of where we left
 * off in a coherent manner.
 *
 * The only way to fully avoid random clock jumps is to boot with:
 * "tsc=unstable".
 */


static void __sched_clock_work(struct work_struct *work)
{
	struct sched_clock_data *scd;
	int cpu;

	/* take a current timestamp and set 'now' */
	preempt_disable();
	scd = this_scd();
	__scd_stamp(scd);
	scd->clock = scd->tick_gtod + __gtod_offset;
	preempt_enable();

	/* clone to all CPUs */
	for_each_possible_cpu(cpu)
		per_cpu(sched_clock_data, cpu) = *scd;

	printk(KERN_WARNING "TSC found unstable after boot, most likely due to broken BIOS. Use 'tsc=unstable'.\n");
	printk(KERN_INFO "sched_clock: Marking unstable (%lld, %lld)<-(%lld, %lld)\n",
			scd->tick_gtod, __gtod_offset,
			scd->tick_raw,  __sched_clock_offset);

	static_branch_disable(&__sched_clock_stable);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 88 96.70% 7 87.50%
Frédéric Weisbecker 3 3.30% 1 12.50%
Total 91 100.00% 8 100.00%

static DECLARE_WORK(sched_clock_work, __sched_clock_work);



static void __clear_sched_clock_stable(void)
{
	if (!sched_clock_stable())
		return;

	tick_dep_set(TICK_DEP_BIT_CLOCK_UNSTABLE);
	schedule_work(&sched_clock_work);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 26 100.00% 3 100.00%
Total 26 100.00% 3 100.00%



void clear_sched_clock_stable(void)
{
	__sched_clock_stable_early = 0;

	smp_mb(); /* matches sched_clock_init_late() */

	if (sched_clock_running == 2)
		__clear_sched_clock_stable();
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 24 100.00% 4 100.00%
Total 24 100.00% 4 100.00%

/*
 * We run this as late_initcall() such that it runs after all built-in drivers,
 * notably: acpi_processor and intel_idle, which can mark the TSC as unstable.
 */


static int __init sched_clock_init_late(void)
{
	sched_clock_running = 2;
	/*
         * Ensure that it is impossible to not do a static_key update.
         *
         * Either {set,clear}_sched_clock_stable() must see sched_clock_running
         * and do the update, or we must see their __sched_clock_stable_early
         * and do the update, or both.
         */
	smp_mb(); /* matches {set,clear}_sched_clock_stable() */

	if (__sched_clock_stable_early)
		__set_sched_clock_stable();

	return 0;
}
Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 28 100.00% 5 100.00%
Total 28 100.00% 5 100.00%


late_initcall(sched_clock_init_late);

/*
 * min, max except they take wrapping into account
 */



static inline u64 wrap_min(u64 x, u64 y)
{
	return (s64)(x - y) < 0 ? x : y;
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 29 100.00% 1 100.00%
Total 29 100.00% 1 100.00%



static inline u64 wrap_max(u64 x, u64 y)
{
	return (s64)(x - y) > 0 ? x : y;
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 29 100.00% 1 100.00%
Total 29 100.00% 1 100.00%

/*
 * update the percpu scd from the raw @now value
 *
 *  - filter out backward motion
 *  - use the GTOD tick value to create a window to filter crazy TSC values
 */


static u64 sched_clock_local(struct sched_clock_data *scd)
{
	u64 now, clock, old_clock, min_clock, max_clock, gtod;
	s64 delta;

again:
	now = sched_clock();
	delta = now - scd->tick_raw;
	if (unlikely(delta < 0))
		delta = 0;

	old_clock = scd->clock;

	/*
         * scd->clock = clamp(scd->tick_gtod + delta,
         *                    max(scd->tick_gtod, scd->clock),
         *                    scd->tick_gtod + TICK_NSEC);
         */

	gtod = scd->tick_gtod + __gtod_offset;
	clock = gtod + delta;
	min_clock = wrap_max(gtod, old_clock);
	max_clock = wrap_max(old_clock, gtod + TICK_NSEC);

	clock = wrap_max(clock, min_clock);
	clock = wrap_min(clock, max_clock);

	if (cmpxchg64(&scd->clock, old_clock, clock) != old_clock)
		goto again;

	return clock;
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 113 83.09% 5 45.45%
Pavel Tatashin 9 6.62% 1 9.09%
Ingo Molnar 9 6.62% 3 27.27%
Thomas Gleixner 4 2.94% 1 9.09%
Eric Dumazet 1 0.74% 1 9.09%
Total 136 100.00% 11 100.00%



static u64 sched_clock_remote(struct sched_clock_data *scd)
{
	struct sched_clock_data *my_scd = this_scd();
	u64 this_clock, remote_clock;
	u64 *ptr, old_val, val;

#if BITS_PER_LONG != 64
again:
	/*
         * Careful here: The local and the remote clock values need to
         * be read out atomic as we need to compare the values and
         * then update either the local or the remote side. So the
         * cmpxchg64 below only protects one readout.
         *
         * We must reread via sched_clock_local() in the retry case on
         * 32bit as an NMI could use sched_clock_local() via the
         * tracer and hit between the readout of
         * the low32bit and the high 32bit portion.
         */
	this_clock = sched_clock_local(my_scd);
	/*
         * We must enforce atomic readout on 32bit, otherwise the
         * update on the remote cpu can hit inbetween the readout of
         * the low32bit and the high 32bit portion.
         */
	remote_clock = cmpxchg64(&scd->clock, 0, 0);
#else
	/*
         * On 64bit the read of [my]scd->clock is atomic versus the
         * update, so we can avoid the above 32bit dance.
         */
	sched_clock_local(my_scd);
again:
	this_clock = my_scd->clock;
	remote_clock = scd->clock;
#endif

	/*
         * Use the opportunity that we have both locks
         * taken to couple the two clocks: we take the
         * larger time as the latest time for both
         * runqueues. (this creates monotonic movement)
         */
	if (likely((s64)(remote_clock - this_clock) < 0)) {
		ptr = &scd->clock;
		old_val = remote_clock;
		val = this_clock;
	} else {
		/*
                 * Should be rare, but possible:
                 */
		ptr = &my_scd->clock;
		old_val = this_clock;
		val = remote_clock;
	}

	if (cmpxchg64(ptr, old_val, val) != old_val)
		goto again;

	return val;
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 87 55.06% 3 37.50%
Ingo Molnar 35 22.15% 3 37.50%
Thomas Gleixner 35 22.15% 1 12.50%
Eric Dumazet 1 0.63% 1 12.50%
Total 158 100.00% 8 100.00%

/*
 * Similar to cpu_clock(), but requires local IRQs to be disabled.
 *
 * See cpu_clock().
 */


u64 sched_clock_cpu(int cpu)
{
	struct sched_clock_data *scd;
	u64 clock;

	if (sched_clock_stable())
		return sched_clock() + __sched_clock_offset;

	if (unlikely(!sched_clock_running))
		return 0ull;

	preempt_disable_notrace();
	scd = cpu_sdc(cpu);

	if (cpu != smp_processor_id())
		clock = sched_clock_remote(scd);
	else
		clock = sched_clock_local(scd);
	preempt_enable_notrace();

	return clock;
}
Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 72 94.74% 6 75.00%
Fernando Luis Vázquez Cao 2 2.63% 1 12.50%
Ingo Molnar 2 2.63% 1 12.50%
Total 76 100.00% 8 100.00%


EXPORT_SYMBOL_GPL(sched_clock_cpu);



void sched_clock_tick(void)
{
	struct sched_clock_data *scd;

	if (sched_clock_stable())
		return;

	if (unlikely(!sched_clock_running))
		return;

	lockdep_assert_irqs_disabled();

	scd = this_scd();
	__scd_stamp(scd);
	sched_clock_local(scd);
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 44 97.78% 4 80.00%
Frédéric Weisbecker 1 2.22% 1 20.00%
Total 45 100.00% 5 100.00%



void sched_clock_tick_stable(void)
{
	u64 gtod, clock;

	if (!sched_clock_stable())
		return;

	/*
         * Called under watchdog_lock.
         *
         * The watchdog just found this TSC to (still) be stable, so now is a
         * good moment to update our __gtod_offset. Because once we find the
         * TSC to be unstable, any computation will be computing crap.
         */
	local_irq_disable();
	gtod = ktime_get_ns();
	clock = sched_clock();
	__gtod_offset = (clock + __sched_clock_offset) - gtod;
	local_irq_enable();
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 46 100.00% 3 100.00%
Total 46 100.00% 3 100.00%

/*
 * We are going deep-idle (irqs are disabled):
 */


void sched_clock_idle_sleep_event(void)
{
	sched_clock_cpu(smp_processor_id());
}
Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 13 100.00% 1 100.00%
Total 13 100.00% 1 100.00%


EXPORT_SYMBOL_GPL(sched_clock_idle_sleep_event);

/*
 * We just idled; resync with ktime.
 */


void sched_clock_idle_wakeup_event(void)
{
	unsigned long flags;

	if (sched_clock_stable())
		return;

	if (unlikely(timekeeping_suspended))
		return;

	local_irq_save(flags);
	sched_clock_tick();
	local_irq_restore(flags);
}
Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 33 86.84% 4 80.00%
Thomas Gleixner 5 13.16% 1 20.00%
Total 38 100.00% 5 100.00%


EXPORT_SYMBOL_GPL(sched_clock_idle_wakeup_event);

#else /* CONFIG_HAVE_UNSTABLE_SCHED_CLOCK */



u64 sched_clock_cpu(int cpu)
{
	if (unlikely(!sched_clock_running))
		return 0;

	return sched_clock();
}

Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 23 100.00% 1 100.00%
Total 23 100.00% 1 100.00%

#endif /* CONFIG_HAVE_UNSTABLE_SCHED_CLOCK */

/*
 * Running clock - returns the time that has elapsed while a guest has been
 * running.
 * On a guest this value should be local_clock minus the time the guest was
 * suspended by the hypervisor (for any reason).
 * On bare metal this function should return the same as local_clock.
 * Architectures and sub-architectures can override this.
 */


u64 __weak running_clock(void)
{
	return local_clock();
}
Contributors
Person Tokens Prop Commits CommitProp
Cyril Bur 12 100.00% 1 100.00%
Total 12 100.00% 1 100.00%

Overall Contributors
Person Tokens Prop Commits CommitProp
Peter Zijlstra 918 83.23% 25 52.08%
Ingo Molnar 57 5.17% 8 16.67%
Thomas Gleixner 44 3.99% 2 4.17%
Hugh Dickins 20 1.81% 1 2.08%
Cyril Bur 13 1.18% 1 2.08%
Frédéric Weisbecker 12 1.09% 2 4.17%
Pavel Tatashin 9 0.82% 1 2.08%
Gideon Israel Dsouza 6 0.54% 1 2.08%
Ron 6 0.54% 1 2.08%
Divyesh Shah 5 0.45% 1 2.08%
Daniel Lezcano 5 0.45% 1 2.08%
David S. Miller 3 0.27% 1 2.08%
Eric Dumazet 2 0.18% 1 2.08%
Fernando Luis Vázquez Cao 2 0.18% 1 2.08%
Paul Gortmaker 1 0.09% 1 2.08%
Total 1103 100.00% 48 100.00%
Directory: kernel/sched

Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
Created with cregit.
Person	Tokens	Prop	Commits	CommitProp
Hugh Dickins	19	67.86%	1	33.33%
Ron	6	21.43%	1	33.33%
Gideon Israel Dsouza	3	10.71%	1	33.33%
Total	28	100.00%	3	100.00%
cregit-Linux how code gets into the kernel

Release 4.15 kernel/sched/clock.c

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Overall Contributors
