kernel/timer.c

   1 /*
   2  *  linux/kernel/timer.c
   3  *
   4  *  Kernel internal timers, kernel timekeeping, basic process system calls
   5  *
   6  *  Copyright (C) 1991, 1992  Linus Torvalds
   7  *
   8  *  1997-01-28  Modified by Finn Arne Gangstad to make timers scale better.
   9  *
  10  *  1997-09-10  Updated NTP code according to technical memorandum Jan '96
  11  *              "A Kernel Model for Precision Timekeeping" by Dave Mills
  12  *  1998-12-24  Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
  13  *              serialize accesses to xtime/lost_ticks).
  14  *                              Copyright (C) 1998  Andrea Arcangeli
  15  *  1999-03-10  Improved NTP compatibility by Ulrich Windl
  16  *  2002-05-31  Move sys_sysinfo here and make its locking sane, Robert Love
  17  *  2000-10-05  Implemented scalable SMP per-CPU timer handling.
  18  *                              Copyright (C) 2000, 2001, 2002  Ingo Molnar
  19  *              Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar
  20  */
  21
  22 #include <linux/kernel_stat.h>
  23 #include <linux/module.h>
  24 #include <linux/interrupt.h>
  25 #include <linux/percpu.h>
  26 #include <linux/init.h>
  27 #include <linux/mm.h>
  28 #include <linux/swap.h>
  29 #include <linux/notifier.h>
  30 #include <linux/thread_info.h>
  31 #include <linux/time.h>
  32 #include <linux/jiffies.h>
  33 #include <linux/posix-timers.h>
  34 #include <linux/cpu.h>
  35 #include <linux/syscalls.h>
  36 #include <linux/delay.h>
  37 #include <linux/vs_base.h>
  38 #include <linux/vs_cvirt.h>
  39 #include <linux/vserver/sched.h>
  40
  41 #include <asm/uaccess.h>
  42 #include <asm/unistd.h>
  43 #include <asm/div64.h>
  44 #include <asm/timex.h>
  45 #include <asm/io.h>
  46
  47 #ifdef CONFIG_TIME_INTERPOLATION
  48 static void time_interpolator_update(long delta_nsec);
  49 #else
  50 #define time_interpolator_update(x)
  51 #endif
  52
  53 u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
  54
  55 EXPORT_SYMBOL(jiffies_64);
  56
  57 /*
  58  * per-CPU timer vector definitions:
  59  */
  60
  61 #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
  62 #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
  63 #define TVN_SIZE (1 << TVN_BITS)
  64 #define TVR_SIZE (1 << TVR_BITS)
  65 #define TVN_MASK (TVN_SIZE - 1)
  66 #define TVR_MASK (TVR_SIZE - 1)
  67
  68 struct timer_base_s {
  69         spinlock_t lock;
  70         struct timer_list *running_timer;
  71 };
  72
  73 typedef struct tvec_s {
  74         struct list_head vec[TVN_SIZE];
  75 } tvec_t;
  76
  77 typedef struct tvec_root_s {
  78         struct list_head vec[TVR_SIZE];
  79 } tvec_root_t;
  80
  81 struct tvec_t_base_s {
  82         struct timer_base_s t_base;
  83         unsigned long timer_jiffies;
  84         tvec_root_t tv1;
  85         tvec_t tv2;
  86         tvec_t tv3;
  87         tvec_t tv4;
  88         tvec_t tv5;
  89 } ____cacheline_aligned_in_smp;
  90
  91 typedef struct tvec_t_base_s tvec_base_t;
  92 static DEFINE_PER_CPU(tvec_base_t, tvec_bases);
  93
  94 static inline void set_running_timer(tvec_base_t *base,
  95                                         struct timer_list *timer)
  96 {
  97 #ifdef CONFIG_SMP
  98         base->t_base.running_timer = timer;
  99 #endif
 100 }
 101
 102 static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
 103 {
 104         unsigned long expires = timer->expires;
 105         unsigned long idx = expires - base->timer_jiffies;
 106         struct list_head *vec;
 107
 108         if (idx < TVR_SIZE) {
 109                 int i = expires & TVR_MASK;
 110                 vec = base->tv1.vec + i;
 111         } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
 112                 int i = (expires >> TVR_BITS) & TVN_MASK;
 113                 vec = base->tv2.vec + i;
 114         } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
 115                 int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
 116                 vec = base->tv3.vec + i;
 117         } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
 118                 int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
 119                 vec = base->tv4.vec + i;
 120         } else if ((signed long) idx < 0) {
 121                 /*
 122                  * Can happen if you add a timer with expires == jiffies,
 123                  * or you set a timer to go off in the past
 124                  */
 125                 vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
 126         } else {
 127                 int i;
 128                 /* If the timeout is larger than 0xffffffff on 64-bit
 129                  * architectures then we use the maximum timeout:
 130                  */
 131                 if (idx > 0xffffffffUL) {
 132                         idx = 0xffffffffUL;
 133                         expires = idx + base->timer_jiffies;
 134                 }
 135                 i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
 136                 vec = base->tv5.vec + i;
 137         }
 138         /*
 139          * Timers are FIFO:
 140          */
 141         list_add_tail(&timer->entry, vec);
 142 }
 143
 144 typedef struct timer_base_s timer_base_t;
 145 /*
 146  * Used by TIMER_INITIALIZER, we can't use per_cpu(tvec_bases)
 147  * at compile time, and we need timer->base to lock the timer.
 148  */
 149 timer_base_t __init_timer_base
 150         ____cacheline_aligned_in_smp = { .lock = SPIN_LOCK_UNLOCKED };
 151 EXPORT_SYMBOL(__init_timer_base);
 152
 153 /***
 154  * init_timer - initialize a timer.
 155  * @timer: the timer to be initialized
 156  *
 157  * init_timer() must be done to a timer prior calling *any* of the
 158  * other timer functions.
 159  */
 160 void fastcall init_timer(struct timer_list *timer)
 161 {
 162         timer->entry.next = NULL;
 163         timer->base = &per_cpu(tvec_bases, raw_smp_processor_id()).t_base;
 164 }
 165 EXPORT_SYMBOL(init_timer);
 166
 167 static inline void detach_timer(struct timer_list *timer,
 168                                         int clear_pending)
 169 {
 170         struct list_head *entry = &timer->entry;
 171
 172         __list_del(entry->prev, entry->next);
 173         if (clear_pending)
 174                 entry->next = NULL;
 175         entry->prev = LIST_POISON2;
 176 }
 177
 178 /*
 179  * We are using hashed locking: holding per_cpu(tvec_bases).t_base.lock
 180  * means that all timers which are tied to this base via timer->base are
 181  * locked, and the base itself is locked too.
 182  *
 183  * So __run_timers/migrate_timers can safely modify all timers which could
 184  * be found on ->tvX lists.
 185  *
 186  * When the timer's base is locked, and the timer removed from list, it is
 187  * possible to set timer->base = NULL and drop the lock: the timer remains
 188  * locked.
 189  */
 190 static timer_base_t *lock_timer_base(struct timer_list *timer,
 191                                         unsigned long *flags)
 192 {
 193         timer_base_t *base;
 194
 195         for (;;) {
 196                 base = timer->base;
 197                 if (likely(base != NULL)) {
 198                         spin_lock_irqsave(&base->lock, *flags);
 199                         if (likely(base == timer->base))
 200                                 return base;
 201                         /* The timer has migrated to another CPU */
 202                         spin_unlock_irqrestore(&base->lock, *flags);
 203                 }
 204                 cpu_relax();
 205         }
 206 }
 207
 208 int __mod_timer(struct timer_list *timer, unsigned long expires)
 209 {
 210         timer_base_t *base;
 211         tvec_base_t *new_base;
 212         unsigned long flags;
 213         int ret = 0;
 214
 215         BUG_ON(!timer->function);
 216
 217         base = lock_timer_base(timer, &flags);
 218
 219         if (timer_pending(timer)) {
 220                 detach_timer(timer, 0);
 221                 ret = 1;
 222         }
 223
 224         new_base = &__get_cpu_var(tvec_bases);
 225
 226         if (base != &new_base->t_base) {
 227                 /*
 228                  * We are trying to schedule the timer on the local CPU.
 229                  * However we can't change timer's base while it is running,
 230                  * otherwise del_timer_sync() can't detect that the timer's
 231                  * handler yet has not finished. This also guarantees that
 232                  * the timer is serialized wrt itself.
 233                  */
 234                 if (unlikely(base->running_timer == timer)) {
 235                         /* The timer remains on a former base */
 236                         new_base = container_of(base, tvec_base_t, t_base);
 237                 } else {
 238                         /* See the comment in lock_timer_base() */
 239                         timer->base = NULL;
 240                         spin_unlock(&base->lock);
 241                         spin_lock(&new_base->t_base.lock);
 242                         timer->base = &new_base->t_base;
 243                 }
 244         }
 245
 246         timer->expires = expires;
 247         internal_add_timer(new_base, timer);
 248         spin_unlock_irqrestore(&new_base->t_base.lock, flags);
 249
 250         return ret;
 251 }
 252
 253 EXPORT_SYMBOL(__mod_timer);
 254
 255 /***
 256  * add_timer_on - start a timer on a particular CPU
 257  * @timer: the timer to be added
 258  * @cpu: the CPU to start it on
 259  *
 260  * This is not very scalable on SMP. Double adds are not possible.
 261  */
 262 void add_timer_on(struct timer_list *timer, int cpu)
 263 {
 264         tvec_base_t *base = &per_cpu(tvec_bases, cpu);
 265         unsigned long flags;
 266
 267         BUG_ON(timer_pending(timer) || !timer->function);
 268         spin_lock_irqsave(&base->t_base.lock, flags);
 269         timer->base = &base->t_base;
 270         internal_add_timer(base, timer);
 271         spin_unlock_irqrestore(&base->t_base.lock, flags);
 272 }
 273
 274
 275 /***
 276  * mod_timer - modify a timer's timeout
 277  * @timer: the timer to be modified
 278  *
 279  * mod_timer is a more efficient way to update the expire field of an
 280  * active timer (if the timer is inactive it will be activated)
 281  *
 282  * mod_timer(timer, expires) is equivalent to:
 283  *
 284  *     del_timer(timer); timer->expires = expires; add_timer(timer);
 285  *
 286  * Note that if there are multiple unserialized concurrent users of the
 287  * same timer, then mod_timer() is the only safe way to modify the timeout,
 288  * since add_timer() cannot modify an already running timer.
 289  *
 290  * The function returns whether it has modified a pending timer or not.
 291  * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
 292  * active timer returns 1.)
 293  */
 294 int mod_timer(struct timer_list *timer, unsigned long expires)
 295 {
 296         BUG_ON(!timer->function);
 297
 298         /*
 299          * This is a common optimization triggered by the
 300          * networking code - if the timer is re-modified
 301          * to be the same thing then just return:
 302          */
 303         if (timer->expires == expires && timer_pending(timer))
 304                 return 1;
 305
 306         return __mod_timer(timer, expires);
 307 }
 308
 309 EXPORT_SYMBOL(mod_timer);
 310
 311 /***
 312  * del_timer - deactive a timer.
 313  * @timer: the timer to be deactivated
 314  *
 315  * del_timer() deactivates a timer - this works on both active and inactive
 316  * timers.
 317  *
 318  * The function returns whether it has deactivated a pending timer or not.
 319  * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
 320  * active timer returns 1.)
 321  */
 322 int del_timer(struct timer_list *timer)
 323 {
 324         timer_base_t *base;
 325         unsigned long flags;
 326         int ret = 0;
 327
 328         if (timer_pending(timer)) {
 329                 base = lock_timer_base(timer, &flags);
 330                 if (timer_pending(timer)) {
 331                         detach_timer(timer, 1);
 332                         ret = 1;
 333                 }
 334                 spin_unlock_irqrestore(&base->lock, flags);
 335         }
 336
 337         return ret;
 338 }
 339
 340 EXPORT_SYMBOL(del_timer);
 341
 342 #ifdef CONFIG_SMP
 343 /*
 344  * This function tries to deactivate a timer. Upon successful (ret >= 0)
 345  * exit the timer is not queued and the handler is not running on any CPU.
 346  *
 347  * It must not be called from interrupt contexts.
 348  */
 349 int try_to_del_timer_sync(struct timer_list *timer)
 350 {
 351         timer_base_t *base;
 352         unsigned long flags;
 353         int ret = -1;
 354
 355         base = lock_timer_base(timer, &flags);
 356
 357         if (base->running_timer == timer)
 358                 goto out;
 359
 360         ret = 0;
 361         if (timer_pending(timer)) {
 362                 detach_timer(timer, 1);
 363                 ret = 1;
 364         }
 365 out:
 366         spin_unlock_irqrestore(&base->lock, flags);
 367
 368         return ret;
 369 }
 370
 371 /***
 372  * del_timer_sync - deactivate a timer and wait for the handler to finish.
 373  * @timer: the timer to be deactivated
 374  *
 375  * This function only differs from del_timer() on SMP: besides deactivating
 376  * the timer it also makes sure the handler has finished executing on other
 377  * CPUs.
 378  *
 379  * Synchronization rules: callers must prevent restarting of the timer,
 380  * otherwise this function is meaningless. It must not be called from
 381  * interrupt contexts. The caller must not hold locks which would prevent
 382  * completion of the timer's handler. The timer's handler must not call
 383  * add_timer_on(). Upon exit the timer is not queued and the handler is
 384  * not running on any CPU.
 385  *
 386  * The function returns whether it has deactivated a pending timer or not.
 387  */
 388 int del_timer_sync(struct timer_list *timer)
 389 {
 390         for (;;) {
 391                 int ret = try_to_del_timer_sync(timer);
 392                 if (ret >= 0)
 393                         return ret;
 394         }
 395 }
 396
 397 EXPORT_SYMBOL(del_timer_sync);
 398 #endif
 399
 400 static int cascade(tvec_base_t *base, tvec_t *tv, int index)
 401 {
 402         /* cascade all the timers from tv up one level */
 403         struct list_head *head, *curr;
 404
 405         head = tv->vec + index;
 406         curr = head->next;
 407         /*
 408          * We are removing _all_ timers from the list, so we don't  have to
 409          * detach them individually, just clear the list afterwards.
 410          */
 411         while (curr != head) {
 412                 struct timer_list *tmp;
 413
 414                 tmp = list_entry(curr, struct timer_list, entry);
 415                 BUG_ON(tmp->base != &base->t_base);
 416                 curr = curr->next;
 417                 internal_add_timer(base, tmp);
 418         }
 419         INIT_LIST_HEAD(head);
 420
 421         return index;
 422 }
 423
 424 /***
 425  * __run_timers - run all expired timers (if any) on this CPU.
 426  * @base: the timer vector to be processed.
 427  *
 428  * This function cascades all vectors and executes all expired timer
 429  * vectors.
 430  */
 431 #define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
 432
 433 static inline void __run_timers(tvec_base_t *base)
 434 {
 435         struct timer_list *timer;
 436
 437         spin_lock_irq(&base->t_base.lock);
 438         while (time_after_eq(jiffies, base->timer_jiffies)) {
 439                 struct list_head work_list = LIST_HEAD_INIT(work_list);
 440                 struct list_head *head = &work_list;
 441                 int index = base->timer_jiffies & TVR_MASK;
 442
 443                 /*
 444                  * Cascade timers:
 445                  */
 446                 if (!index &&
 447                         (!cascade(base, &base->tv2, INDEX(0))) &&
 448                                 (!cascade(base, &base->tv3, INDEX(1))) &&
 449                                         !cascade(base, &base->tv4, INDEX(2)))
 450                         cascade(base, &base->tv5, INDEX(3));
 451                 ++base->timer_jiffies;
 452                 list_splice_init(base->tv1.vec + index, &work_list);
 453                 while (!list_empty(head)) {
 454                         void (*fn)(unsigned long);
 455                         unsigned long data;
 456
 457                         timer = list_entry(head->next,struct timer_list,entry);
 458                         fn = timer->function;
 459                         data = timer->data;
 460
 461                         set_running_timer(base, timer);
 462                         detach_timer(timer, 1);
 463                         spin_unlock_irq(&base->t_base.lock);
 464                         {
 465                                 int preempt_count = preempt_count();
 466                                 fn(data);
 467                                 if (preempt_count != preempt_count()) {
 468                                         printk(KERN_WARNING "huh, entered %p "
 469                                                "with preempt_count %08x, exited"
 470                                                " with %08x?\n",
 471                                                fn, preempt_count,
 472                                                preempt_count());
 473                                         BUG();
 474                                 }
 475                         }
 476                         spin_lock_irq(&base->t_base.lock);
 477                 }
 478         }
 479         set_running_timer(base, NULL);
 480         spin_unlock_irq(&base->t_base.lock);
 481 }
 482
 483 #ifdef CONFIG_NO_IDLE_HZ
 484 /*
 485  * Find out when the next timer event is due to happen. This
 486  * is used on S/390 to stop all activity when a cpus is idle.
 487  * This functions needs to be called disabled.
 488  */
 489 unsigned long next_timer_interrupt(void)
 490 {
 491         tvec_base_t *base;
 492         struct list_head *list;
 493         struct timer_list *nte;
 494         unsigned long expires;
 495         unsigned long hr_expires = MAX_JIFFY_OFFSET;
 496         ktime_t hr_delta;
 497         tvec_t *varray[4];
 498         int i, j;
 499
 500         hr_delta = hrtimer_get_next_event();
 501         if (hr_delta.tv64 != KTIME_MAX) {
 502                 struct timespec tsdelta;
 503                 tsdelta = ktime_to_timespec(hr_delta);
 504                 hr_expires = timespec_to_jiffies(&tsdelta);
 505                 if (hr_expires < 3)
 506                         return hr_expires + jiffies;
 507         }
 508         hr_expires += jiffies;
 509
 510         base = &__get_cpu_var(tvec_bases);
 511         spin_lock(&base->t_base.lock);
 512         expires = base->timer_jiffies + (LONG_MAX >> 1);
 513         list = NULL;
 514
 515         /* Look for timer events in tv1. */
 516         j = base->timer_jiffies & TVR_MASK;
 517         do {
 518                 list_for_each_entry(nte, base->tv1.vec + j, entry) {
 519                         expires = nte->expires;
 520                         if (j < (base->timer_jiffies & TVR_MASK))
 521                                 list = base->tv2.vec + (INDEX(0));
 522                         goto found;
 523                 }
 524                 j = (j + 1) & TVR_MASK;
 525         } while (j != (base->timer_jiffies & TVR_MASK));
 526
 527         /* Check tv2-tv5. */
 528         varray[0] = &base->tv2;
 529         varray[1] = &base->tv3;
 530         varray[2] = &base->tv4;
 531         varray[3] = &base->tv5;
 532         for (i = 0; i < 4; i++) {
 533                 j = INDEX(i);
 534                 do {
 535                         if (list_empty(varray[i]->vec + j)) {
 536                                 j = (j + 1) & TVN_MASK;
 537                                 continue;
 538                         }
 539                         list_for_each_entry(nte, varray[i]->vec + j, entry)
 540                                 if (time_before(nte->expires, expires))
 541                                         expires = nte->expires;
 542                         if (j < (INDEX(i)) && i < 3)
 543                                 list = varray[i + 1]->vec + (INDEX(i + 1));
 544                         goto found;
 545                 } while (j != (INDEX(i)));
 546         }
 547 found:
 548         if (list) {
 549                 /*
 550                  * The search wrapped. We need to look at the next list
 551                  * from next tv element that would cascade into tv element
 552                  * where we found the timer element.
 553                  */
 554                 list_for_each_entry(nte, list, entry) {
 555                         if (time_before(nte->expires, expires))
 556                                 expires = nte->expires;
 557                 }
 558         }
 559         spin_unlock(&base->t_base.lock);
 560
 561         if (time_before(hr_expires, expires))
 562                 return hr_expires;
 563
 564         return expires;
 565 }
 566 #endif
 567
 568 /******************************************************************/
 569
 570 /*
 571  * Timekeeping variables
 572  */
 573 unsigned long tick_usec = TICK_USEC;            /* USER_HZ period (usec) */
 574 unsigned long tick_nsec = TICK_NSEC;            /* ACTHZ period (nsec) */
 575
 576 /*
 577  * The current time
 578  * wall_to_monotonic is what we need to add to xtime (or xtime corrected
 579  * for sub jiffie times) to get to monotonic time.  Monotonic is pegged
 580  * at zero at system boot time, so wall_to_monotonic will be negative,
 581  * however, we will ALWAYS keep the tv_nsec part positive so we can use
 582  * the usual normalization.
 583  */
 584 struct timespec xtime __attribute__ ((aligned (16)));
 585 struct timespec wall_to_monotonic __attribute__ ((aligned (16)));
 586
 587 EXPORT_SYMBOL(xtime);
 588
 589 /* Don't completely fail for HZ > 500.  */
 590 int tickadj = 500/HZ ? : 1;             /* microsecs */
 591
 592
 593 /*
 594  * phase-lock loop variables
 595  */
 596 /* TIME_ERROR prevents overwriting the CMOS clock */
 597 int time_state = TIME_OK;               /* clock synchronization status */
 598 int time_status = STA_UNSYNC;           /* clock status bits            */
 599 long time_offset;                       /* time adjustment (us)         */
 600 long time_constant = 2;                 /* pll time constant            */
 601 long time_tolerance = MAXFREQ;          /* frequency tolerance (ppm)    */
 602 long time_precision = 1;                /* clock precision (us)         */
 603 long time_maxerror = NTP_PHASE_LIMIT;   /* maximum error (us)           */
 604 long time_esterror = NTP_PHASE_LIMIT;   /* estimated error (us)         */
 605 static long time_phase;                 /* phase offset (scaled us)     */
 606 long time_freq = (((NSEC_PER_SEC + HZ/2) % HZ - HZ/2) << SHIFT_USEC) / NSEC_PER_USEC;
 607                                         /* frequency offset (scaled ppm)*/
 608 static long time_adj;                   /* tick adjust (scaled 1 / HZ)  */
 609 long time_reftime;                      /* time at last adjustment (s)  */
 610 long time_adjust;
 611 long time_next_adjust;
 612
 613 /*
 614  * this routine handles the overflow of the microsecond field
 615  *
 616  * The tricky bits of code to handle the accurate clock support
 617  * were provided by Dave Mills (Mills@UDEL.EDU) of NTP fame.
 618  * They were originally developed for SUN and DEC kernels.
 619  * All the kudos should go to Dave for this stuff.
 620  *
 621  */
 622 static void second_overflow(void)
 623 {
 624         long ltemp;
 625
 626         /* Bump the maxerror field */
 627         time_maxerror += time_tolerance >> SHIFT_USEC;
 628         if (time_maxerror > NTP_PHASE_LIMIT) {
 629                 time_maxerror = NTP_PHASE_LIMIT;
 630                 time_status |= STA_UNSYNC;
 631         }
 632
 633         /*
 634          * Leap second processing. If in leap-insert state at the end of the
 635          * day, the system clock is set back one second; if in leap-delete
 636          * state, the system clock is set ahead one second. The microtime()
 637          * routine or external clock driver will insure that reported time is
 638          * always monotonic. The ugly divides should be replaced.
 639          */
 640         switch (time_state) {
 641         case TIME_OK:
 642                 if (time_status & STA_INS)
 643                         time_state = TIME_INS;
 644                 else if (time_status & STA_DEL)
 645                         time_state = TIME_DEL;
 646                 break;
 647         case TIME_INS:
 648                 if (xtime.tv_sec % 86400 == 0) {
 649                         xtime.tv_sec--;
 650                         wall_to_monotonic.tv_sec++;
 651                         /*
 652                          * The timer interpolator will make time change
 653                          * gradually instead of an immediate jump by one second
 654                          */
 655                         time_interpolator_update(-NSEC_PER_SEC);
 656                         time_state = TIME_OOP;
 657                         clock_was_set();
 658                         printk(KERN_NOTICE "Clock: inserting leap second "
 659                                         "23:59:60 UTC\n");
 660                 }
 661                 break;
 662         case TIME_DEL:
 663                 if ((xtime.tv_sec + 1) % 86400 == 0) {
 664                         xtime.tv_sec++;
 665                         wall_to_monotonic.tv_sec--;
 666                         /*
 667                          * Use of time interpolator for a gradual change of
 668                          * time
 669                          */
 670                         time_interpolator_update(NSEC_PER_SEC);
 671                         time_state = TIME_WAIT;
 672                         clock_was_set();
 673                         printk(KERN_NOTICE "Clock: deleting leap second "
 674                                         "23:59:59 UTC\n");
 675                 }
 676                 break;
 677         case TIME_OOP:
 678                 time_state = TIME_WAIT;
 679                 break;
 680         case TIME_WAIT:
 681                 if (!(time_status & (STA_INS | STA_DEL)))
 682                 time_state = TIME_OK;
 683         }
 684
 685         /*
 686          * Compute the phase adjustment for the next second. In PLL mode, the
 687          * offset is reduced by a fixed factor times the time constant. In FLL
 688          * mode the offset is used directly. In either mode, the maximum phase
 689          * adjustment for each second is clamped so as to spread the adjustment
 690          * over not more than the number of seconds between updates.
 691          */
 692         ltemp = time_offset;
 693         if (!(time_status & STA_FLL))
 694                 ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
 695         ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
 696         ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);
 697         time_offset -= ltemp;
 698         time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
 699
 700         /*
 701          * Compute the frequency estimate and additional phase adjustment due
 702          * to frequency error for the next second. When the PPS signal is
 703          * engaged, gnaw on the watchdog counter and update the frequency
 704          * computed by the pll and the PPS signal.
 705          */
 706         pps_valid++;
 707         if (pps_valid == PPS_VALID) {   /* PPS signal lost */
 708                 pps_jitter = MAXTIME;
 709                 pps_stabil = MAXFREQ;
 710                 time_status &= ~(STA_PPSSIGNAL | STA_PPSJITTER |
 711                                 STA_PPSWANDER | STA_PPSERROR);
 712         }
 713         ltemp = time_freq + pps_freq;
 714         time_adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));
 715
 716 #if HZ == 100
 717         /*
 718          * Compensate for (HZ==100) != (1 << SHIFT_HZ).  Add 25% and 3.125% to
 719          * get 128.125; => only 0.125% error (p. 14)
 720          */
 721         time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
 722 #endif
 723 #if HZ == 250
 724         /*
 725          * Compensate for (HZ==250) != (1 << SHIFT_HZ).  Add 1.5625% and
 726          * 0.78125% to get 255.85938; => only 0.05% error (p. 14)
 727          */
 728         time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 729 #endif
 730 #if HZ == 1000
 731         /*
 732          * Compensate for (HZ==1000) != (1 << SHIFT_HZ).  Add 1.5625% and
 733          * 0.78125% to get 1023.4375; => only 0.05% error (p. 14)
 734          */
 735         time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 736 #endif
 737 }
 738
 739 /*
 740  * Returns how many microseconds we need to add to xtime this tick
 741  * in doing an adjustment requested with adjtime.
 742  */
 743 static long adjtime_adjustment(void)
 744 {
 745         long time_adjust_step;
 746
 747         time_adjust_step = time_adjust;
 748         if (time_adjust_step) {
 749                 /*
 750                  * We are doing an adjtime thing.  Prepare time_adjust_step to
 751                  * be within bounds.  Note that a positive time_adjust means we
 752                  * want the clock to run faster.
 753                  *
 754                  * Limit the amount of the step to be in the range
 755                  * -tickadj .. +tickadj
 756                  */
 757                 time_adjust_step = min(time_adjust_step, (long)tickadj);
 758                 time_adjust_step = max(time_adjust_step, (long)-tickadj);
 759         }
 760         return time_adjust_step;
 761 }
 762
 763 /* in the NTP reference this is called "hardclock()" */
 764 static void update_wall_time_one_tick(void)
 765 {
 766         long time_adjust_step, delta_nsec;
 767
 768         time_adjust_step = adjtime_adjustment();
 769         if (time_adjust_step)
 770                 /* Reduce by this step the amount of time left  */
 771                 time_adjust -= time_adjust_step;
 772         delta_nsec = tick_nsec + time_adjust_step * 1000;
 773         /*
 774          * Advance the phase, once it gets to one microsecond, then
 775          * advance the tick more.
 776          */
 777         time_phase += time_adj;
 778         if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC)) {
 779                 long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
 780                 time_phase -= ltemp << (SHIFT_SCALE - 10);
 781                 delta_nsec += ltemp;
 782         }
 783         xtime.tv_nsec += delta_nsec;
 784         time_interpolator_update(delta_nsec);
 785
 786         /* Changes by adjtime() do not take effect till next tick. */
 787         if (time_next_adjust != 0) {
 788                 time_adjust = time_next_adjust;
 789                 time_next_adjust = 0;
 790         }
 791 }
 792
 793 /*
 794  * Return how long ticks are at the moment, that is, how much time
 795  * update_wall_time_one_tick will add to xtime next time we call it
 796  * (assuming no calls to do_adjtimex in the meantime).
 797  * The return value is in fixed-point nanoseconds with SHIFT_SCALE-10
 798  * bits to the right of the binary point.
 799  * This function has no side-effects.
 800  */
 801 u64 current_tick_length(void)
 802 {
 803         long delta_nsec;
 804
 805         delta_nsec = tick_nsec + adjtime_adjustment() * 1000;
 806         return ((u64) delta_nsec << (SHIFT_SCALE - 10)) + time_adj;
 807 }
 808
 809 /*
 810  * Using a loop looks inefficient, but "ticks" is
 811  * usually just one (we shouldn't be losing ticks,
 812  * we're doing this this way mainly for interrupt
 813  * latency reasons, not because we think we'll
 814  * have lots of lost timer ticks
 815  */
 816 static void update_wall_time(unsigned long ticks)
 817 {
 818         do {
 819                 ticks--;
 820                 update_wall_time_one_tick();
 821                 if (xtime.tv_nsec >= 1000000000) {
 822                         xtime.tv_nsec -= 1000000000;
 823                         xtime.tv_sec++;
 824                         second_overflow();
 825                 }
 826         } while (ticks);
 827 }
 828
 829 /*
 830  * Called from the timer interrupt handler to charge one tick to the current
 831  * process.  user_tick is 1 if the tick is user time, 0 for system.
 832  */
 833 void update_process_times(int user_tick)
 834 {
 835         struct task_struct *p = current;
 836         int cpu = smp_processor_id();
 837
 838         /* Note: this timer irq context must be accounted for as well. */
 839         if (user_tick)
 840                 account_user_time(p, jiffies_to_cputime(1));
 841         else
 842                 account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
 843         run_local_timers();
 844         if (rcu_pending(cpu))
 845                 rcu_check_callbacks(cpu, user_tick);
 846         scheduler_tick();
 847         run_posix_cpu_timers(p);
 848 }
 849
 850 /*
 851  * Nr of active tasks - counted in fixed-point numbers
 852  */
 853 static unsigned long count_active_tasks(void)
 854 {
 855         return (nr_running() + nr_uninterruptible()) * FIXED_1;
 856 }
 857
 858 /*
 859  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
 860  * imply that avenrun[] is the standard name for this kind of thing.
 861  * Nothing else seems to be standardized: the fractional size etc
 862  * all seem to differ on different machines.
 863  *
 864  * Requires xtime_lock to access.
 865  */
 866 unsigned long avenrun[3];
 867
 868 EXPORT_SYMBOL(avenrun);
 869
 870 /*
 871  * calc_load - given tick count, update the avenrun load estimates.
 872  * This is called while holding a write_lock on xtime_lock.
 873  */
 874 static inline void calc_load(unsigned long ticks)
 875 {
 876         unsigned long active_tasks; /* fixed-point */
 877         static int count = LOAD_FREQ;
 878
 879         count -= ticks;
 880         if (count < 0) {
 881                 count += LOAD_FREQ;
 882                 active_tasks = count_active_tasks();
 883                 CALC_LOAD(avenrun[0], EXP_1, active_tasks);
 884                 CALC_LOAD(avenrun[1], EXP_5, active_tasks);
 885                 CALC_LOAD(avenrun[2], EXP_15, active_tasks);
 886         }
 887 }
 888
 889 /* jiffies at the most recent update of wall time */
 890 unsigned long wall_jiffies = INITIAL_JIFFIES;
 891
 892 /*
 893  * This read-write spinlock protects us from races in SMP while
 894  * playing with xtime and avenrun.
 895  */
 896 #ifndef ARCH_HAVE_XTIME_LOCK
 897 seqlock_t xtime_lock __cacheline_aligned_in_smp = SEQLOCK_UNLOCKED;
 898
 899 EXPORT_SYMBOL(xtime_lock);
 900 #endif
 901
 902 /*
 903  * This function runs timers and the timer-tq in bottom half context.
 904  */
 905 static void run_timer_softirq(struct softirq_action *h)
 906 {
 907         tvec_base_t *base = &__get_cpu_var(tvec_bases);
 908
 909         hrtimer_run_queues();
 910         if (time_after_eq(jiffies, base->timer_jiffies))
 911                 __run_timers(base);
 912 }
 913
 914 /*
 915  * Called by the local, per-CPU timer interrupt on SMP.
 916  */
 917 void run_local_timers(void)
 918 {
 919         raise_softirq(TIMER_SOFTIRQ);
 920 }
 921
 922 /*
 923  * Called by the timer interrupt. xtime_lock must already be taken
 924  * by the timer IRQ!
 925  */
 926 static inline void update_times(void)
 927 {
 928         unsigned long ticks;
 929
 930         ticks = jiffies - wall_jiffies;
 931         if (ticks) {
 932                 wall_jiffies += ticks;
 933                 update_wall_time(ticks);
 934         }
 935         calc_load(ticks);
 936 }
 937
 938 /*
 939  * The 64-bit jiffies value is not atomic - you MUST NOT read it
 940  * without sampling the sequence number in xtime_lock.
 941  * jiffies is defined in the linker script...
 942  */
 943
 944 void do_timer(struct pt_regs *regs)
 945 {
 946         jiffies_64++;
 947         /* prevent loading jiffies before storing new jiffies_64 value. */
 948         barrier();
 949         update_times();
 950         softlockup_tick(regs);
 951 }
 952
 953 #ifdef __ARCH_WANT_SYS_ALARM
 954
 955 /*
 956  * For backwards compatibility?  This can be done in libc so Alpha
 957  * and all newer ports shouldn't need it.
 958  */
 959 asmlinkage unsigned long sys_alarm(unsigned int seconds)
 960 {
 961         struct itimerval it_new, it_old;
 962         unsigned int oldalarm;
 963
 964         it_new.it_interval.tv_sec = it_new.it_interval.tv_usec = 0;
 965         it_new.it_value.tv_sec = seconds;
 966         it_new.it_value.tv_usec = 0;
 967         do_setitimer(ITIMER_REAL, &it_new, &it_old);
 968         oldalarm = it_old.it_value.tv_sec;
 969         /* ehhh.. We can't return 0 if we have an alarm pending.. */
 970         /* And we'd better return too much than too little anyway */
 971         if ((!oldalarm && it_old.it_value.tv_usec) || it_old.it_value.tv_usec >= 500000)
 972                 oldalarm++;
 973         return oldalarm;
 974 }
 975
 976 #endif
 977
 978
 979 /**
 980  * sys_getpid - return the thread group id of the current process
 981  *
 982  * Note, despite the name, this returns the tgid not the pid.  The tgid and
 983  * the pid are identical unless CLONE_THREAD was specified on clone() in
 984  * which case the tgid is the same in all threads of the same group.
 985  *
 986  * This is SMP safe as current->tgid does not change.
 987  */
 988 asmlinkage long sys_getpid(void)
 989 {
 990         return vx_map_tgid(current->tgid);
 991 }
 992
 993 /*
 994  * Accessing ->real_parent is not SMP-safe, it could
 995  * change from under us. However, we can use a stale
 996  * value of ->real_parent under rcu_read_lock(), see
 997  * release_task()->call_rcu(delayed_put_task_struct).
 998  */
 999 asmlinkage long sys_getppid(void)
1000 {
1001         int pid;
1002
1003         rcu_read_lock();
1004         pid = rcu_dereference(current->real_parent)->tgid;
1005         rcu_read_unlock();
1006
1007         return vx_map_pid(pid);
1008 }
1009
1010 #ifdef __alpha__
1011
1012 /*
1013  * The Alpha uses getxpid, getxuid, and getxgid instead.
1014  */
1015
1016 asmlinkage long do_getxpid(long *ppid)
1017 {
1018         *ppid = sys_getppid();
1019         return sys_getpid();
1020 }
1021
1022 #else /* _alpha_ */
1023
1024 asmlinkage long sys_getuid(void)
1025 {
1026         /* Only we change this so SMP safe */
1027         return current->uid;
1028 }
1029
1030 asmlinkage long sys_geteuid(void)
1031 {
1032         /* Only we change this so SMP safe */
1033         return current->euid;
1034 }
1035
1036 asmlinkage long sys_getgid(void)
1037 {
1038         /* Only we change this so SMP safe */
1039         return current->gid;
1040 }
1041
1042 asmlinkage long sys_getegid(void)
1043 {
1044         /* Only we change this so SMP safe */
1045         return  current->egid;
1046 }
1047
1048 #endif
1049
1050 static void process_timeout(unsigned long __data)
1051 {
1052         wake_up_process((task_t *)__data);
1053 }
1054
1055 /**
1056  * schedule_timeout - sleep until timeout
1057  * @timeout: timeout value in jiffies
1058  *
1059  * Make the current task sleep until @timeout jiffies have
1060  * elapsed. The routine will return immediately unless
1061  * the current task state has been set (see set_current_state()).
1062  *
1063  * You can set the task state as follows -
1064  *
1065  * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
1066  * pass before the routine returns. The routine will return 0
1067  *
1068  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
1069  * delivered to the current task. In this case the remaining time
1070  * in jiffies will be returned, or 0 if the timer expired in time
1071  *
1072  * The current task state is guaranteed to be TASK_RUNNING when this
1073  * routine returns.
1074  *
1075  * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
1076  * the CPU away without a bound on the timeout. In this case the return
1077  * value will be %MAX_SCHEDULE_TIMEOUT.
1078  *
1079  * In all cases the return value is guaranteed to be non-negative.
1080  */
1081 fastcall signed long __sched schedule_timeout(signed long timeout)
1082 {
1083         struct timer_list timer;
1084         unsigned long expire;
1085
1086         switch (timeout)
1087         {
1088         case MAX_SCHEDULE_TIMEOUT:
1089                 /*
1090                  * These two special cases are useful to be comfortable
1091                  * in the caller. Nothing more. We could take
1092                  * MAX_SCHEDULE_TIMEOUT from one of the negative value
1093                  * but I' d like to return a valid offset (>=0) to allow
1094                  * the caller to do everything it want with the retval.
1095                  */
1096                 schedule();
1097                 goto out;
1098         default:
1099                 /*
1100                  * Another bit of PARANOID. Note that the retval will be
1101                  * 0 since no piece of kernel is supposed to do a check
1102                  * for a negative retval of schedule_timeout() (since it
1103                  * should never happens anyway). You just have the printk()
1104                  * that will tell you if something is gone wrong and where.
1105                  */
1106                 if (timeout < 0)
1107                 {
1108                         printk(KERN_ERR "schedule_timeout: wrong timeout "
1109                                 "value %lx from %p\n", timeout,
1110                                 __builtin_return_address(0));
1111                         current->state = TASK_RUNNING;
1112                         goto out;
1113                 }
1114         }
1115
1116         expire = timeout + jiffies;
1117
1118         setup_timer(&timer, process_timeout, (unsigned long)current);
1119         __mod_timer(&timer, expire);
1120         schedule();
1121         del_singleshot_timer_sync(&timer);
1122
1123         timeout = expire - jiffies;
1124
1125  out:
1126         return timeout < 0 ? 0 : timeout;
1127 }
1128 EXPORT_SYMBOL(schedule_timeout);
1129
1130 /*
1131  * We can use __set_current_state() here because schedule_timeout() calls
1132  * schedule() unconditionally.
1133  */
1134 signed long __sched schedule_timeout_interruptible(signed long timeout)
1135 {
1136         __set_current_state(TASK_INTERRUPTIBLE);
1137         return schedule_timeout(timeout);
1138 }
1139 EXPORT_SYMBOL(schedule_timeout_interruptible);
1140
1141 signed long __sched schedule_timeout_uninterruptible(signed long timeout)
1142 {
1143         __set_current_state(TASK_UNINTERRUPTIBLE);
1144         return schedule_timeout(timeout);
1145 }
1146 EXPORT_SYMBOL(schedule_timeout_uninterruptible);
1147
1148 /* Thread ID - the internal kernel "pid" */
1149 asmlinkage long sys_gettid(void)
1150 {
1151         return current->pid;
1152 }
1153
1154 /*
1155  * sys_sysinfo - fill in sysinfo struct
1156  */
1157 asmlinkage long sys_sysinfo(struct sysinfo __user *info)
1158 {
1159         struct sysinfo val;
1160         unsigned long mem_total, sav_total;
1161         unsigned int mem_unit, bitcount;
1162         unsigned long seq;
1163
1164         memset((char *)&val, 0, sizeof(struct sysinfo));
1165
1166         do {
1167                 struct timespec tp;
1168                 seq = read_seqbegin(&xtime_lock);
1169
1170                 /*
1171                  * This is annoying.  The below is the same thing
1172                  * posix_get_clock_monotonic() does, but it wants to
1173                  * take the lock which we want to cover the loads stuff
1174                  * too.
1175                  */
1176
1177                 getnstimeofday(&tp);
1178                 tp.tv_sec += wall_to_monotonic.tv_sec;
1179                 tp.tv_nsec += wall_to_monotonic.tv_nsec;
1180                 if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
1181                         tp.tv_nsec = tp.tv_nsec - NSEC_PER_SEC;
1182                         tp.tv_sec++;
1183                 }
1184                 if (vx_flags(VXF_VIRT_UPTIME, 0))
1185                         vx_vsi_uptime(&tp, NULL);
1186                 val.uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
1187
1188                 val.loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
1189                 val.loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
1190                 val.loads[2] = avenrun[2] << (SI_LOAD_SHIFT - FSHIFT);
1191
1192                 val.procs = nr_threads;
1193         } while (read_seqretry(&xtime_lock, seq));
1194
1195         si_meminfo(&val);
1196         si_swapinfo(&val);
1197
1198         /*
1199          * If the sum of all the available memory (i.e. ram + swap)
1200          * is less than can be stored in a 32 bit unsigned long then
1201          * we can be binary compatible with 2.2.x kernels.  If not,
1202          * well, in that case 2.2.x was broken anyways...
1203          *
1204          *  -Erik Andersen <andersee@debian.org>
1205          */
1206
1207         mem_total = val.totalram + val.totalswap;
1208         if (mem_total < val.totalram || mem_total < val.totalswap)
1209                 goto out;
1210         bitcount = 0;
1211         mem_unit = val.mem_unit;
1212         while (mem_unit > 1) {
1213                 bitcount++;
1214                 mem_unit >>= 1;
1215                 sav_total = mem_total;
1216                 mem_total <<= 1;
1217                 if (mem_total < sav_total)
1218                         goto out;
1219         }
1220
1221         /*
1222          * If mem_total did not overflow, multiply all memory values by
1223          * val.mem_unit and set it to 1.  This leaves things compatible
1224          * with 2.2.x, and also retains compatibility with earlier 2.4.x
1225          * kernels...
1226          */
1227
1228         val.mem_unit = 1;
1229         val.totalram <<= bitcount;
1230         val.freeram <<= bitcount;
1231         val.sharedram <<= bitcount;
1232         val.bufferram <<= bitcount;
1233         val.totalswap <<= bitcount;
1234         val.freeswap <<= bitcount;
1235         val.totalhigh <<= bitcount;
1236         val.freehigh <<= bitcount;
1237
1238  out:
1239         if (copy_to_user(info, &val, sizeof(struct sysinfo)))
1240                 return -EFAULT;
1241
1242         return 0;
1243 }
1244
1245 static void __devinit init_timers_cpu(int cpu)
1246 {
1247         int j;
1248         tvec_base_t *base;
1249
1250         base = &per_cpu(tvec_bases, cpu);
1251         spin_lock_init(&base->t_base.lock);
1252         for (j = 0; j < TVN_SIZE; j++) {
1253                 INIT_LIST_HEAD(base->tv5.vec + j);
1254                 INIT_LIST_HEAD(base->tv4.vec + j);
1255                 INIT_LIST_HEAD(base->tv3.vec + j);
1256                 INIT_LIST_HEAD(base->tv2.vec + j);
1257         }
1258         for (j = 0; j < TVR_SIZE; j++)
1259                 INIT_LIST_HEAD(base->tv1.vec + j);
1260
1261         base->timer_jiffies = jiffies;
1262 }
1263
1264 #ifdef CONFIG_HOTPLUG_CPU
1265 static void migrate_timer_list(tvec_base_t *new_base, struct list_head *head)
1266 {
1267         struct timer_list *timer;
1268
1269         while (!list_empty(head)) {
1270                 timer = list_entry(head->next, struct timer_list, entry);
1271                 detach_timer(timer, 0);
1272                 timer->base = &new_base->t_base;
1273                 internal_add_timer(new_base, timer);
1274         }
1275 }
1276
1277 static void __devinit migrate_timers(int cpu)
1278 {
1279         tvec_base_t *old_base;
1280         tvec_base_t *new_base;
1281         int i;
1282
1283         BUG_ON(cpu_online(cpu));
1284         old_base = &per_cpu(tvec_bases, cpu);
1285         new_base = &get_cpu_var(tvec_bases);
1286
1287         local_irq_disable();
1288         spin_lock(&new_base->t_base.lock);
1289         spin_lock(&old_base->t_base.lock);
1290
1291         if (old_base->t_base.running_timer)
1292                 BUG();
1293         for (i = 0; i < TVR_SIZE; i++)
1294                 migrate_timer_list(new_base, old_base->tv1.vec + i);
1295         for (i = 0; i < TVN_SIZE; i++) {
1296                 migrate_timer_list(new_base, old_base->tv2.vec + i);
1297                 migrate_timer_list(new_base, old_base->tv3.vec + i);
1298                 migrate_timer_list(new_base, old_base->tv4.vec + i);
1299                 migrate_timer_list(new_base, old_base->tv5.vec + i);
1300         }
1301
1302         spin_unlock(&old_base->t_base.lock);
1303         spin_unlock(&new_base->t_base.lock);
1304         local_irq_enable();
1305         put_cpu_var(tvec_bases);
1306 }
1307 #endif /* CONFIG_HOTPLUG_CPU */
1308
1309 static int __devinit timer_cpu_notify(struct notifier_block *self,
1310                                 unsigned long action, void *hcpu)
1311 {
1312         long cpu = (long)hcpu;
1313         switch(action) {
1314         case CPU_UP_PREPARE:
1315                 init_timers_cpu(cpu);
1316                 break;
1317 #ifdef CONFIG_HOTPLUG_CPU
1318         case CPU_DEAD:
1319                 migrate_timers(cpu);
1320                 break;
1321 #endif
1322         default:
1323                 break;
1324         }
1325         return NOTIFY_OK;
1326 }
1327
1328 static struct notifier_block __devinitdata timers_nb = {
1329         .notifier_call  = timer_cpu_notify,
1330 };
1331
1332
1333 void __init init_timers(void)
1334 {
1335         timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
1336                                 (void *)(long)smp_processor_id());
1337         register_cpu_notifier(&timers_nb);
1338         open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
1339 }
1340
1341 #ifdef CONFIG_TIME_INTERPOLATION
1342
1343 struct time_interpolator *time_interpolator __read_mostly;
1344 static struct time_interpolator *time_interpolator_list __read_mostly;
1345 static DEFINE_SPINLOCK(time_interpolator_lock);
1346
1347 static inline u64 time_interpolator_get_cycles(unsigned int src)
1348 {
1349         unsigned long (*x)(void);
1350
1351         switch (src)
1352         {
1353                 case TIME_SOURCE_FUNCTION:
1354                         x = time_interpolator->addr;
1355                         return x();
1356
1357                 case TIME_SOURCE_MMIO64 :
1358                         return readq_relaxed((void __iomem *)time_interpolator->addr);
1359
1360                 case TIME_SOURCE_MMIO32 :
1361                         return readl_relaxed((void __iomem *)time_interpolator->addr);
1362
1363                 default: return get_cycles();
1364         }
1365 }
1366
1367 static inline u64 time_interpolator_get_counter(int writelock)
1368 {
1369         unsigned int src = time_interpolator->source;
1370
1371         if (time_interpolator->jitter)
1372         {
1373                 u64 lcycle;
1374                 u64 now;
1375
1376                 do {
1377                         lcycle = time_interpolator->last_cycle;
1378                         now = time_interpolator_get_cycles(src);
1379                         if (lcycle && time_after(lcycle, now))
1380                                 return lcycle;
1381
1382                         /* When holding the xtime write lock, there's no need
1383                          * to add the overhead of the cmpxchg.  Readers are
1384                          * force to retry until the write lock is released.
1385                          */
1386                         if (writelock) {
1387                                 time_interpolator->last_cycle = now;
1388                                 return now;
1389                         }
1390                         /* Keep track of the last timer value returned. The use of cmpxchg here
1391                          * will cause contention in an SMP environment.
1392                          */
1393                 } while (unlikely(cmpxchg(&time_interpolator->last_cycle, lcycle, now) != lcycle));
1394                 return now;
1395         }
1396         else
1397                 return time_interpolator_get_cycles(src);
1398 }
1399
1400 void time_interpolator_reset(void)
1401 {
1402         time_interpolator->offset = 0;
1403         time_interpolator->last_counter = time_interpolator_get_counter(1);
1404 }
1405
1406 #define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)
1407
1408 unsigned long time_interpolator_get_offset(void)
1409 {
1410         /* If we do not have a time interpolator set up then just return zero */
1411         if (!time_interpolator)
1412                 return 0;
1413
1414         return time_interpolator->offset +
1415                 GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
1416 }
1417
1418 #define INTERPOLATOR_ADJUST 65536
1419 #define INTERPOLATOR_MAX_SKIP 10*INTERPOLATOR_ADJUST
1420
1421 static void time_interpolator_update(long delta_nsec)
1422 {
1423         u64 counter;
1424         unsigned long offset;
1425
1426         /* If there is no time interpolator set up then do nothing */
1427         if (!time_interpolator)
1428                 return;
1429
1430         /*
1431          * The interpolator compensates for late ticks by accumulating the late
1432          * time in time_interpolator->offset. A tick earlier than expected will
1433          * lead to a reset of the offset and a corresponding jump of the clock
1434          * forward. Again this only works if the interpolator clock is running
1435          * slightly slower than the regular clock and the tuning logic insures
1436          * that.
1437          */
1438
1439         counter = time_interpolator_get_counter(1);
1440         offset = time_interpolator->offset +
1441                         GET_TI_NSECS(counter, time_interpolator);
1442
1443         if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)
1444                 time_interpolator->offset = offset - delta_nsec;
1445         else {
1446                 time_interpolator->skips++;
1447                 time_interpolator->ns_skipped += delta_nsec - offset;
1448                 time_interpolator->offset = 0;
1449         }
1450         time_interpolator->last_counter = counter;
1451
1452         /* Tuning logic for time interpolator invoked every minute or so.
1453          * Decrease interpolator clock speed if no skips occurred and an offset is carried.
1454          * Increase interpolator clock speed if we skip too much time.
1455          */
1456         if (jiffies % INTERPOLATOR_ADJUST == 0)
1457         {
1458                 if (time_interpolator->skips == 0 && time_interpolator->offset > TICK_NSEC)
1459                         time_interpolator->nsec_per_cyc--;
1460                 if (time_interpolator->ns_skipped > INTERPOLATOR_MAX_SKIP && time_interpolator->offset == 0)
1461                         time_interpolator->nsec_per_cyc++;
1462                 time_interpolator->skips = 0;
1463                 time_interpolator->ns_skipped = 0;
1464         }
1465 }
1466
1467 static inline int
1468 is_better_time_interpolator(struct time_interpolator *new)
1469 {
1470         if (!time_interpolator)
1471                 return 1;
1472         return new->frequency > 2*time_interpolator->frequency ||
1473             (unsigned long)new->drift < (unsigned long)time_interpolator->drift;
1474 }
1475
1476 void
1477 register_time_interpolator(struct time_interpolator *ti)
1478 {
1479         unsigned long flags;
1480
1481         /* Sanity check */
1482         if (ti->frequency == 0 || ti->mask == 0)
1483                 BUG();
1484
1485         ti->nsec_per_cyc = ((u64)NSEC_PER_SEC << ti->shift) / ti->frequency;
1486         spin_lock(&time_interpolator_lock);
1487         write_seqlock_irqsave(&xtime_lock, flags);
1488         if (is_better_time_interpolator(ti)) {
1489                 time_interpolator = ti;
1490                 time_interpolator_reset();
1491         }
1492         write_sequnlock_irqrestore(&xtime_lock, flags);
1493
1494         ti->next = time_interpolator_list;
1495         time_interpolator_list = ti;
1496         spin_unlock(&time_interpolator_lock);
1497 }
1498
1499 void
1500 unregister_time_interpolator(struct time_interpolator *ti)
1501 {
1502         struct time_interpolator *curr, **prev;
1503         unsigned long flags;
1504
1505         spin_lock(&time_interpolator_lock);
1506         prev = &time_interpolator_list;
1507         for (curr = *prev; curr; curr = curr->next) {
1508                 if (curr == ti) {
1509                         *prev = curr->next;
1510                         break;
1511                 }
1512                 prev = &curr->next;
1513         }
1514
1515         write_seqlock_irqsave(&xtime_lock, flags);
1516         if (ti == time_interpolator) {
1517                 /* we lost the best time-interpolator: */
1518                 time_interpolator = NULL;
1519                 /* find the next-best interpolator */
1520                 for (curr = time_interpolator_list; curr; curr = curr->next)
1521                         if (is_better_time_interpolator(curr))
1522                                 time_interpolator = curr;
1523                 time_interpolator_reset();
1524         }
1525         write_sequnlock_irqrestore(&xtime_lock, flags);
1526         spin_unlock(&time_interpolator_lock);
1527 }
1528 #endif /* CONFIG_TIME_INTERPOLATION */
1529
1530 /**
1531  * msleep - sleep safely even with waitqueue interruptions
1532  * @msecs: Time in milliseconds to sleep for
1533  */
1534 void msleep(unsigned int msecs)
1535 {
1536         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1537
1538         while (timeout)
1539                 timeout = schedule_timeout_uninterruptible(timeout);
1540 }
1541
1542 EXPORT_SYMBOL(msleep);
1543
1544 /**
1545  * msleep_interruptible - sleep waiting for signals
1546  * @msecs: Time in milliseconds to sleep for
1547  */
1548 unsigned long msleep_interruptible(unsigned int msecs)
1549 {
1550         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1551
1552         while (timeout && !signal_pending(current))
1553                 timeout = schedule_timeout_interruptible(timeout);
1554         return jiffies_to_msecs(timeout);
1555 }
1556
1557 EXPORT_SYMBOL(msleep_interruptible);