SAFE public projects git trees. - safe/jmp/linux-2.6/blob - kernel/sched_clock.c

   1 /*
   2  * sched_clock for unstable cpu clocks
   3  *
   4  *  Copyright (C) 2008 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
   5  *
   6  *  Updates and enhancements:
   7  *    Copyright (C) 2008 Red Hat, Inc. Steven Rostedt <srostedt@redhat.com>
   8  *
   9  * Based on code by:
  10  *   Ingo Molnar <mingo@redhat.com>
  11  *   Guillaume Chazarain <guichaz@gmail.com>
  12  *
  13  * Create a semi stable clock from a mixture of other events, including:
  14  *  - gtod
  15  *  - jiffies
  16  *  - sched_clock()
  17  *  - explicit idle events
  18  *
  19  * We use gtod as base and the unstable clock deltas. The deltas are filtered,
  20  * making it monotonic and keeping it within an expected window.  This window
  21  * is set up using jiffies.
  22  *
  23  * Furthermore, explicit sleep and wakeup hooks allow us to account for time
  24  * that is otherwise invisible (TSC gets stopped).
  25  *
  26  * The clock: sched_clock_cpu() is monotonic per cpu, and should be somewhat
  27  * consistent between cpus (never more than 1 jiffies difference).
  28  */
  29 #include <linux/sched.h>
  30 #include <linux/percpu.h>
  31 #include <linux/spinlock.h>
  32 #include <linux/ktime.h>
  33 #include <linux/module.h>
  34
  35 /*
  36  * Scheduler clock - returns current time in nanosec units.
  37  * This is default implementation.
  38  * Architectures and sub-architectures can override this.
  39  */
  40 unsigned long long __attribute__((weak)) sched_clock(void)
  41 {
  42         return (unsigned long long)jiffies * (NSEC_PER_SEC / HZ);
  43 }
  44
  45 #ifdef CONFIG_HAVE_UNSTABLE_SCHED_CLOCK
  46
  47 #define MULTI_SHIFT 15
  48 /* Max is double, Min is 1/2 */
  49 #define MAX_MULTI (2LL << MULTI_SHIFT)
  50 #define MIN_MULTI (1LL << (MULTI_SHIFT-1))
  51
  52 struct sched_clock_data {
  53         /*
  54          * Raw spinlock - this is a special case: this might be called
  55          * from within instrumentation code so we dont want to do any
  56          * instrumentation ourselves.
  57          */
  58         raw_spinlock_t          lock;
  59
  60         unsigned long           tick_jiffies;
  61         u64                     prev_raw;
  62         u64                     tick_raw;
  63         u64                     tick_gtod;
  64         u64                     clock;
  65         s64                     multi;
  66 #ifdef CONFIG_NO_HZ
  67         int                     check_max;
  68 #endif
  69 };
  70
  71 static DEFINE_PER_CPU_SHARED_ALIGNED(struct sched_clock_data, sched_clock_data);
  72
  73 static inline struct sched_clock_data *this_scd(void)
  74 {
  75         return &__get_cpu_var(sched_clock_data);
  76 }
  77
  78 static inline struct sched_clock_data *cpu_sdc(int cpu)
  79 {
  80         return &per_cpu(sched_clock_data, cpu);
  81 }
  82
  83 static __read_mostly int sched_clock_running;
  84
  85 void sched_clock_init(void)
  86 {
  87         u64 ktime_now = ktime_to_ns(ktime_get());
  88         unsigned long now_jiffies = jiffies;
  89         int cpu;
  90
  91         for_each_possible_cpu(cpu) {
  92                 struct sched_clock_data *scd = cpu_sdc(cpu);
  93
  94                 scd->lock = (raw_spinlock_t)__RAW_SPIN_LOCK_UNLOCKED;
  95                 scd->tick_jiffies = now_jiffies;
  96                 scd->prev_raw = 0;
  97                 scd->tick_raw = 0;
  98                 scd->tick_gtod = ktime_now;
  99                 scd->clock = ktime_now;
 100                 scd->multi = 1 << MULTI_SHIFT;
 101 #ifdef CONFIG_NO_HZ
 102                 scd->check_max = 1;
 103 #endif
 104         }
 105
 106         sched_clock_running = 1;
 107 }
 108
 109 #ifdef CONFIG_NO_HZ
 110 /*
 111  * The dynamic ticks makes the delta jiffies inaccurate. This
 112  * prevents us from checking the maximum time update.
 113  * Disable the maximum check during stopped ticks.
 114  */
 115 void sched_clock_tick_stop(int cpu)
 116 {
 117         struct sched_clock_data *scd = cpu_sdc(cpu);
 118
 119         scd->check_max = 0;
 120 }
 121
 122 void sched_clock_tick_start(int cpu)
 123 {
 124         struct sched_clock_data *scd = cpu_sdc(cpu);
 125
 126         scd->check_max = 1;
 127 }
 128
 129 static int check_max(struct sched_clock_data *scd)
 130 {
 131         return scd->check_max;
 132 }
 133 #else
 134 static int check_max(struct sched_clock_data *scd)
 135 {
 136         return 1;
 137 }
 138 #endif /* CONFIG_NO_HZ */
 139
 140 /*
 141  * update the percpu scd from the raw @now value
 142  *
 143  *  - filter out backward motion
 144  *  - use jiffies to generate a min,max window to clip the raw values
 145  */
 146 static void __update_sched_clock(struct sched_clock_data *scd, u64 now, u64 *time)
 147 {
 148         unsigned long now_jiffies = jiffies;
 149         long delta_jiffies = now_jiffies - scd->tick_jiffies;
 150         u64 clock = scd->clock;
 151         u64 min_clock, max_clock;
 152         s64 delta = now - scd->prev_raw;
 153
 154         WARN_ON_ONCE(!irqs_disabled());
 155
 156         /*
 157          * At schedule tick the clock can be just under the gtod. We don't
 158          * want to push it too prematurely.
 159          */
 160         min_clock = scd->tick_gtod + (delta_jiffies * TICK_NSEC);
 161         if (min_clock > TICK_NSEC)
 162                 min_clock -= TICK_NSEC / 2;
 163
 164         if (unlikely(delta < 0)) {
 165                 clock++;
 166                 goto out;
 167         }
 168
 169         /*
 170          * The clock must stay within a jiffie of the gtod.
 171          * But since we may be at the start of a jiffy or the end of one
 172          * we add another jiffy buffer.
 173          */
 174         max_clock = scd->tick_gtod + (2 + delta_jiffies) * TICK_NSEC;
 175
 176         delta *= scd->multi;
 177         delta >>= MULTI_SHIFT;
 178
 179         if (unlikely(clock + delta > max_clock) && check_max(scd)) {
 180                 if (clock < max_clock)
 181                         clock = max_clock;
 182                 else
 183                         clock++;
 184         } else {
 185                 clock += delta;
 186         }
 187
 188  out:
 189         if (unlikely(clock < min_clock))
 190                 clock = min_clock;
 191
 192         if (time)
 193                 *time = clock;
 194         else {
 195                 scd->prev_raw = now;
 196                 scd->clock = clock;
 197         }
 198 }
 199
 200 static void lock_double_clock(struct sched_clock_data *data1,
 201                                 struct sched_clock_data *data2)
 202 {
 203         if (data1 < data2) {
 204                 __raw_spin_lock(&data1->lock);
 205                 __raw_spin_lock(&data2->lock);
 206         } else {
 207                 __raw_spin_lock(&data2->lock);
 208                 __raw_spin_lock(&data1->lock);
 209         }
 210 }
 211
 212 u64 sched_clock_cpu(int cpu)
 213 {
 214         struct sched_clock_data *scd = cpu_sdc(cpu);
 215         u64 now, clock;
 216
 217         if (unlikely(!sched_clock_running))
 218                 return 0ull;
 219
 220         WARN_ON_ONCE(!irqs_disabled());
 221         now = sched_clock();
 222
 223         if (cpu != raw_smp_processor_id()) {
 224                 /*
 225                  * in order to update a remote cpu's clock based on our
 226                  * unstable raw time rebase it against:
 227                  *   tick_raw           (offset between raw counters)
 228                  *   tick_gotd          (tick offset between cpus)
 229                  */
 230                 struct sched_clock_data *my_scd = this_scd();
 231
 232                 lock_double_clock(scd, my_scd);
 233
 234                 now -= my_scd->tick_raw;
 235                 now += scd->tick_raw;
 236
 237                 now += my_scd->tick_gtod;
 238                 now -= scd->tick_gtod;
 239
 240                 __raw_spin_unlock(&my_scd->lock);
 241
 242                 __update_sched_clock(scd, now, &clock);
 243
 244                 __raw_spin_unlock(&scd->lock);
 245
 246         } else {
 247                 __raw_spin_lock(&scd->lock);
 248                 __update_sched_clock(scd, now, NULL);
 249                 clock = scd->clock;
 250                 __raw_spin_unlock(&scd->lock);
 251         }
 252
 253         return clock;
 254 }
 255
 256 void sched_clock_tick(void)
 257 {
 258         struct sched_clock_data *scd = this_scd();
 259         unsigned long now_jiffies = jiffies;
 260         s64 mult, delta_gtod, delta_raw;
 261         u64 now, now_gtod;
 262
 263         if (unlikely(!sched_clock_running))
 264                 return;
 265
 266         WARN_ON_ONCE(!irqs_disabled());
 267
 268         now_gtod = ktime_to_ns(ktime_get());
 269         now = sched_clock();
 270
 271         __raw_spin_lock(&scd->lock);
 272         __update_sched_clock(scd, now, NULL);
 273         /*
 274          * update tick_gtod after __update_sched_clock() because that will
 275          * already observe 1 new jiffy; adding a new tick_gtod to that would
 276          * increase the clock 2 jiffies.
 277          */
 278         delta_gtod = now_gtod - scd->tick_gtod;
 279         delta_raw = now - scd->tick_raw;
 280
 281         if ((long)delta_raw > 0) {
 282                 mult = delta_gtod << MULTI_SHIFT;
 283                 do_div(mult, delta_raw);
 284                 scd->multi = mult;
 285                 if (scd->multi > MAX_MULTI)
 286                         scd->multi = MAX_MULTI;
 287                 else if (scd->multi < MIN_MULTI)
 288                         scd->multi = MIN_MULTI;
 289         } else
 290                 scd->multi = 1 << MULTI_SHIFT;
 291
 292         scd->tick_raw = now;
 293         scd->tick_gtod = now_gtod;
 294         scd->tick_jiffies = now_jiffies;
 295         __raw_spin_unlock(&scd->lock);
 296 }
 297
 298 /*
 299  * We are going deep-idle (irqs are disabled):
 300  */
 301 void sched_clock_idle_sleep_event(void)
 302 {
 303         sched_clock_cpu(smp_processor_id());
 304 }
 305 EXPORT_SYMBOL_GPL(sched_clock_idle_sleep_event);
 306
 307 /*
 308  * We just idled delta nanoseconds (called with irqs disabled):
 309  */
 310 void sched_clock_idle_wakeup_event(u64 delta_ns)
 311 {
 312         struct sched_clock_data *scd = this_scd();
 313         u64 now = sched_clock();
 314
 315         /*
 316          * Override the previous timestamp and ignore all
 317          * sched_clock() deltas that occured while we idled,
 318          * and use the PM-provided delta_ns to advance the
 319          * rq clock:
 320          */
 321         __raw_spin_lock(&scd->lock);
 322         scd->prev_raw = now;
 323         scd->clock += delta_ns;
 324         scd->multi = 1 << MULTI_SHIFT;
 325         __raw_spin_unlock(&scd->lock);
 326
 327         touch_softlockup_watchdog();
 328 }
 329 EXPORT_SYMBOL_GPL(sched_clock_idle_wakeup_event);
 330
 331 #endif
 332
 333 unsigned long long cpu_clock(int cpu)
 334 {
 335         unsigned long long clock;
 336         unsigned long flags;
 337
 338         local_irq_save(flags);
 339         clock = sched_clock_cpu(cpu);
 340         local_irq_restore(flags);
 341
 342         return clock;
 343 }
 344 EXPORT_SYMBOL_GPL(cpu_clock);