clock.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * sched_clock() for unstable CPU clocks
  4. *
  5. * Copyright (C) 2008 Red Hat, Inc., Peter Zijlstra
  6. *
  7. * Updates and enhancements:
  8. * Copyright (C) 2008 Red Hat, Inc. Steven Rostedt <srostedt@redhat.com>
  9. *
  10. * Based on code by:
  11. * Ingo Molnar <mingo@redhat.com>
  12. * Guillaume Chazarain <guichaz@gmail.com>
  13. *
  14. *
  15. * What this file implements:
  16. *
  17. * cpu_clock(i) provides a fast (execution time) high resolution
  18. * clock with bounded drift between CPUs. The value of cpu_clock(i)
  19. * is monotonic for constant i. The timestamp returned is in nanoseconds.
  20. *
  21. * ######################### BIG FAT WARNING ##########################
  22. * # when comparing cpu_clock(i) to cpu_clock(j) for i != j, time can #
  23. * # go backwards !! #
  24. * ####################################################################
  25. *
  26. * There is no strict promise about the base, although it tends to start
  27. * at 0 on boot (but people really shouldn't rely on that).
  28. *
  29. * cpu_clock(i) -- can be used from any context, including NMI.
  30. * local_clock() -- is cpu_clock() on the current CPU.
  31. *
  32. * sched_clock_cpu(i)
  33. *
  34. * How it is implemented:
  35. *
  36. * The implementation either uses sched_clock() when
  37. * !CONFIG_HAVE_UNSTABLE_SCHED_CLOCK, which means in that case the
  38. * sched_clock() is assumed to provide these properties (mostly it means
  39. * the architecture provides a globally synchronized highres time source).
  40. *
  41. * Otherwise it tries to create a semi stable clock from a mixture of other
  42. * clocks, including:
  43. *
  44. * - GTOD (clock monotomic)
  45. * - sched_clock()
  46. * - explicit idle events
  47. *
  48. * We use GTOD as base and use sched_clock() deltas to improve resolution. The
  49. * deltas are filtered to provide monotonicity and keeping it within an
  50. * expected window.
  51. *
  52. * Furthermore, explicit sleep and wakeup hooks allow us to account for time
  53. * that is otherwise invisible (TSC gets stopped).
  54. *
  55. */
  56. #include "sched.h"
  57. #include <linux/sched_clock.h>
  58. /*
  59. * Scheduler clock - returns current time in nanosec units.
  60. * This is default implementation.
  61. * Architectures and sub-architectures can override this.
  62. */
  63. unsigned long long __weak sched_clock(void)
  64. {
  65. return (unsigned long long)(jiffies - INITIAL_JIFFIES)
  66. * (NSEC_PER_SEC / HZ);
  67. }
  68. EXPORT_SYMBOL_GPL(sched_clock);
  69. static DEFINE_STATIC_KEY_FALSE(sched_clock_running);
  70. #ifdef CONFIG_HAVE_UNSTABLE_SCHED_CLOCK
  71. /*
  72. * We must start with !__sched_clock_stable because the unstable -> stable
  73. * transition is accurate, while the stable -> unstable transition is not.
  74. *
  75. * Similarly we start with __sched_clock_stable_early, thereby assuming we
  76. * will become stable, such that there's only a single 1 -> 0 transition.
  77. */
  78. static DEFINE_STATIC_KEY_FALSE(__sched_clock_stable);
  79. static int __sched_clock_stable_early = 1;
  80. /*
  81. * We want: ktime_get_ns() + __gtod_offset == sched_clock() + __sched_clock_offset
  82. */
  83. __read_mostly u64 __sched_clock_offset;
  84. static __read_mostly u64 __gtod_offset;
  85. struct sched_clock_data {
  86. u64 tick_raw;
  87. u64 tick_gtod;
  88. u64 clock;
  89. };
  90. static DEFINE_PER_CPU_SHARED_ALIGNED(struct sched_clock_data, sched_clock_data);
  91. static inline struct sched_clock_data *this_scd(void)
  92. {
  93. return this_cpu_ptr(&sched_clock_data);
  94. }
  95. static inline struct sched_clock_data *cpu_sdc(int cpu)
  96. {
  97. return &per_cpu(sched_clock_data, cpu);
  98. }
  99. int sched_clock_stable(void)
  100. {
  101. return static_branch_likely(&__sched_clock_stable);
  102. }
  103. static void __scd_stamp(struct sched_clock_data *scd)
  104. {
  105. scd->tick_gtod = ktime_get_ns();
  106. scd->tick_raw = sched_clock();
  107. }
  108. static void __set_sched_clock_stable(void)
  109. {
  110. struct sched_clock_data *scd;
  111. /*
  112. * Since we're still unstable and the tick is already running, we have
  113. * to disable IRQs in order to get a consistent scd->tick* reading.
  114. */
  115. local_irq_disable();
  116. scd = this_scd();
  117. /*
  118. * Attempt to make the (initial) unstable->stable transition continuous.
  119. */
  120. __sched_clock_offset = (scd->tick_gtod + __gtod_offset) - (scd->tick_raw);
  121. local_irq_enable();
  122. printk(KERN_INFO "sched_clock: Marking stable (%lld, %lld)->(%lld, %lld)\n",
  123. scd->tick_gtod, __gtod_offset,
  124. scd->tick_raw, __sched_clock_offset);
  125. static_branch_enable(&__sched_clock_stable);
  126. tick_dep_clear(TICK_DEP_BIT_CLOCK_UNSTABLE);
  127. }
  128. /*
  129. * If we ever get here, we're screwed, because we found out -- typically after
  130. * the fact -- that TSC wasn't good. This means all our clocksources (including
  131. * ktime) could have reported wrong values.
  132. *
  133. * What we do here is an attempt to fix up and continue sort of where we left
  134. * off in a coherent manner.
  135. *
  136. * The only way to fully avoid random clock jumps is to boot with:
  137. * "tsc=unstable".
  138. */
  139. static void __sched_clock_work(struct work_struct *work)
  140. {
  141. struct sched_clock_data *scd;
  142. int cpu;
  143. /* take a current timestamp and set 'now' */
  144. preempt_disable();
  145. scd = this_scd();
  146. __scd_stamp(scd);
  147. scd->clock = scd->tick_gtod + __gtod_offset;
  148. preempt_enable();
  149. /* clone to all CPUs */
  150. for_each_possible_cpu(cpu)
  151. per_cpu(sched_clock_data, cpu) = *scd;
  152. printk(KERN_WARNING "TSC found unstable after boot, most likely due to broken BIOS. Use 'tsc=unstable'.\n");
  153. printk(KERN_INFO "sched_clock: Marking unstable (%lld, %lld)<-(%lld, %lld)\n",
  154. scd->tick_gtod, __gtod_offset,
  155. scd->tick_raw, __sched_clock_offset);
  156. static_branch_disable(&__sched_clock_stable);
  157. }
  158. static DECLARE_WORK(sched_clock_work, __sched_clock_work);
  159. static void __clear_sched_clock_stable(void)
  160. {
  161. if (!sched_clock_stable())
  162. return;
  163. tick_dep_set(TICK_DEP_BIT_CLOCK_UNSTABLE);
  164. schedule_work(&sched_clock_work);
  165. }
  166. void clear_sched_clock_stable(void)
  167. {
  168. __sched_clock_stable_early = 0;
  169. smp_mb(); /* matches sched_clock_init_late() */
  170. if (static_key_count(&sched_clock_running.key) == 2)
  171. __clear_sched_clock_stable();
  172. }
  173. static void __sched_clock_gtod_offset(void)
  174. {
  175. struct sched_clock_data *scd = this_scd();
  176. __scd_stamp(scd);
  177. __gtod_offset = (scd->tick_raw + __sched_clock_offset) - scd->tick_gtod;
  178. }
  179. void __init sched_clock_init(void)
  180. {
  181. /*
  182. * Set __gtod_offset such that once we mark sched_clock_running,
  183. * sched_clock_tick() continues where sched_clock() left off.
  184. *
  185. * Even if TSC is buggered, we're still UP at this point so it
  186. * can't really be out of sync.
  187. */
  188. local_irq_disable();
  189. __sched_clock_gtod_offset();
  190. local_irq_enable();
  191. static_branch_inc(&sched_clock_running);
  192. }
  193. /*
  194. * We run this as late_initcall() such that it runs after all built-in drivers,
  195. * notably: acpi_processor and intel_idle, which can mark the TSC as unstable.
  196. */
  197. static int __init sched_clock_init_late(void)
  198. {
  199. static_branch_inc(&sched_clock_running);
  200. /*
  201. * Ensure that it is impossible to not do a static_key update.
  202. *
  203. * Either {set,clear}_sched_clock_stable() must see sched_clock_running
  204. * and do the update, or we must see their __sched_clock_stable_early
  205. * and do the update, or both.
  206. */
  207. smp_mb(); /* matches {set,clear}_sched_clock_stable() */
  208. if (__sched_clock_stable_early)
  209. __set_sched_clock_stable();
  210. return 0;
  211. }
  212. late_initcall(sched_clock_init_late);
  213. /*
  214. * min, max except they take wrapping into account
  215. */
  216. static inline u64 wrap_min(u64 x, u64 y)
  217. {
  218. return (s64)(x - y) < 0 ? x : y;
  219. }
  220. static inline u64 wrap_max(u64 x, u64 y)
  221. {
  222. return (s64)(x - y) > 0 ? x : y;
  223. }
  224. /*
  225. * update the percpu scd from the raw @now value
  226. *
  227. * - filter out backward motion
  228. * - use the GTOD tick value to create a window to filter crazy TSC values
  229. */
  230. static u64 sched_clock_local(struct sched_clock_data *scd)
  231. {
  232. u64 now, clock, old_clock, min_clock, max_clock, gtod;
  233. s64 delta;
  234. again:
  235. now = sched_clock();
  236. delta = now - scd->tick_raw;
  237. if (unlikely(delta < 0))
  238. delta = 0;
  239. old_clock = scd->clock;
  240. /*
  241. * scd->clock = clamp(scd->tick_gtod + delta,
  242. * max(scd->tick_gtod, scd->clock),
  243. * scd->tick_gtod + TICK_NSEC);
  244. */
  245. gtod = scd->tick_gtod + __gtod_offset;
  246. clock = gtod + delta;
  247. min_clock = wrap_max(gtod, old_clock);
  248. max_clock = wrap_max(old_clock, gtod + TICK_NSEC);
  249. clock = wrap_max(clock, min_clock);
  250. clock = wrap_min(clock, max_clock);
  251. if (cmpxchg64(&scd->clock, old_clock, clock) != old_clock)
  252. goto again;
  253. return clock;
  254. }
  255. static u64 sched_clock_remote(struct sched_clock_data *scd)
  256. {
  257. struct sched_clock_data *my_scd = this_scd();
  258. u64 this_clock, remote_clock;
  259. u64 *ptr, old_val, val;
  260. #if BITS_PER_LONG != 64
  261. again:
  262. /*
  263. * Careful here: The local and the remote clock values need to
  264. * be read out atomic as we need to compare the values and
  265. * then update either the local or the remote side. So the
  266. * cmpxchg64 below only protects one readout.
  267. *
  268. * We must reread via sched_clock_local() in the retry case on
  269. * 32-bit kernels as an NMI could use sched_clock_local() via the
  270. * tracer and hit between the readout of
  271. * the low 32-bit and the high 32-bit portion.
  272. */
  273. this_clock = sched_clock_local(my_scd);
  274. /*
  275. * We must enforce atomic readout on 32-bit, otherwise the
  276. * update on the remote CPU can hit inbetween the readout of
  277. * the low 32-bit and the high 32-bit portion.
  278. */
  279. remote_clock = cmpxchg64(&scd->clock, 0, 0);
  280. #else
  281. /*
  282. * On 64-bit kernels the read of [my]scd->clock is atomic versus the
  283. * update, so we can avoid the above 32-bit dance.
  284. */
  285. sched_clock_local(my_scd);
  286. again:
  287. this_clock = my_scd->clock;
  288. remote_clock = scd->clock;
  289. #endif
  290. /*
  291. * Use the opportunity that we have both locks
  292. * taken to couple the two clocks: we take the
  293. * larger time as the latest time for both
  294. * runqueues. (this creates monotonic movement)
  295. */
  296. if (likely((s64)(remote_clock - this_clock) < 0)) {
  297. ptr = &scd->clock;
  298. old_val = remote_clock;
  299. val = this_clock;
  300. } else {
  301. /*
  302. * Should be rare, but possible:
  303. */
  304. ptr = &my_scd->clock;
  305. old_val = this_clock;
  306. val = remote_clock;
  307. }
  308. if (cmpxchg64(ptr, old_val, val) != old_val)
  309. goto again;
  310. return val;
  311. }
  312. /*
  313. * Similar to cpu_clock(), but requires local IRQs to be disabled.
  314. *
  315. * See cpu_clock().
  316. */
  317. u64 sched_clock_cpu(int cpu)
  318. {
  319. struct sched_clock_data *scd;
  320. u64 clock;
  321. if (sched_clock_stable())
  322. return sched_clock() + __sched_clock_offset;
  323. if (!static_branch_likely(&sched_clock_running))
  324. return sched_clock();
  325. preempt_disable_notrace();
  326. scd = cpu_sdc(cpu);
  327. if (cpu != smp_processor_id())
  328. clock = sched_clock_remote(scd);
  329. else
  330. clock = sched_clock_local(scd);
  331. preempt_enable_notrace();
  332. return clock;
  333. }
  334. EXPORT_SYMBOL_GPL(sched_clock_cpu);
  335. void sched_clock_tick(void)
  336. {
  337. struct sched_clock_data *scd;
  338. if (sched_clock_stable())
  339. return;
  340. if (!static_branch_likely(&sched_clock_running))
  341. return;
  342. lockdep_assert_irqs_disabled();
  343. scd = this_scd();
  344. __scd_stamp(scd);
  345. sched_clock_local(scd);
  346. }
  347. void sched_clock_tick_stable(void)
  348. {
  349. if (!sched_clock_stable())
  350. return;
  351. /*
  352. * Called under watchdog_lock.
  353. *
  354. * The watchdog just found this TSC to (still) be stable, so now is a
  355. * good moment to update our __gtod_offset. Because once we find the
  356. * TSC to be unstable, any computation will be computing crap.
  357. */
  358. local_irq_disable();
  359. __sched_clock_gtod_offset();
  360. local_irq_enable();
  361. }
  362. /*
  363. * We are going deep-idle (irqs are disabled):
  364. */
  365. void sched_clock_idle_sleep_event(void)
  366. {
  367. sched_clock_cpu(smp_processor_id());
  368. }
  369. EXPORT_SYMBOL_GPL(sched_clock_idle_sleep_event);
  370. /*
  371. * We just idled; resync with ktime.
  372. */
  373. void sched_clock_idle_wakeup_event(void)
  374. {
  375. unsigned long flags;
  376. if (sched_clock_stable())
  377. return;
  378. if (unlikely(timekeeping_suspended))
  379. return;
  380. local_irq_save(flags);
  381. sched_clock_tick();
  382. local_irq_restore(flags);
  383. }
  384. EXPORT_SYMBOL_GPL(sched_clock_idle_wakeup_event);
  385. #else /* CONFIG_HAVE_UNSTABLE_SCHED_CLOCK */
  386. void __init sched_clock_init(void)
  387. {
  388. static_branch_inc(&sched_clock_running);
  389. local_irq_disable();
  390. generic_sched_clock_init();
  391. local_irq_enable();
  392. }
  393. u64 sched_clock_cpu(int cpu)
  394. {
  395. if (!static_branch_likely(&sched_clock_running))
  396. return 0;
  397. return sched_clock();
  398. }
  399. #endif /* CONFIG_HAVE_UNSTABLE_SCHED_CLOCK */
  400. /*
  401. * Running clock - returns the time that has elapsed while a guest has been
  402. * running.
  403. * On a guest this value should be local_clock minus the time the guest was
  404. * suspended by the hypervisor (for any reason).
  405. * On bare metal this function should return the same as local_clock.
  406. * Architectures and sub-architectures can override this.
  407. */
  408. u64 __weak running_clock(void)
  409. {
  410. return local_clock();
  411. }