kernel/hrtimer.c

   1 /*
   2  *  linux/kernel/hrtimer.c
   3  *
   4  *  Copyright(C) 2005, Thomas Gleixner <tglx@linutronix.de>
   5  *  Copyright(C) 2005, Red Hat, Inc., Ingo Molnar
   6  *
   7  *  High-resolution kernel timers
   8  *
   9  *  In contrast to the low-resolution timeout API implemented in
  10  *  kernel/timer.c, hrtimers provide finer resolution and accuracy
  11  *  depending on system configuration and capabilities.
  12  *
  13  *  These timers are currently used for:
  14  *   - itimers
  15  *   - POSIX timers
  16  *   - nanosleep
  17  *   - precise in-kernel timing
  18  *
  19  *  Started by: Thomas Gleixner and Ingo Molnar
  20  *
  21  *  Credits:
  22  *      based on kernel/timer.c
  23  *
  24  *  For licencing details see kernel-base/COPYING
  25  */
  26
  27 #include <linux/cpu.h>
  28 #include <linux/module.h>
  29 #include <linux/percpu.h>
  30 #include <linux/hrtimer.h>
  31 #include <linux/notifier.h>
  32 #include <linux/syscalls.h>
  33 #include <linux/interrupt.h>
  34
  35 #include <asm/uaccess.h>
  36
  37 /**
  38  * ktime_get - get the monotonic time in ktime_t format
  39  *
  40  * returns the time in ktime_t format
  41  */
  42 static ktime_t ktime_get(void)
  43 {
  44         struct timespec now;
  45
  46         ktime_get_ts(&now);
  47
  48         return timespec_to_ktime(now);
  49 }
  50
  51 /**
  52  * ktime_get_real - get the real (wall-) time in ktime_t format
  53  *
  54  * returns the time in ktime_t format
  55  */
  56 static ktime_t ktime_get_real(void)
  57 {
  58         struct timespec now;
  59
  60         getnstimeofday(&now);
  61
  62         return timespec_to_ktime(now);
  63 }
  64
  65 EXPORT_SYMBOL_GPL(ktime_get_real);
  66
  67 /*
  68  * The timer bases:
  69  */
  70
  71 #define MAX_HRTIMER_BASES 2
  72
  73 static DEFINE_PER_CPU(struct hrtimer_base, hrtimer_bases[MAX_HRTIMER_BASES]) =
  74 {
  75         {
  76                 .index = CLOCK_REALTIME,
  77                 .get_time = &ktime_get_real,
  78                 .resolution = KTIME_REALTIME_RES,
  79         },
  80         {
  81                 .index = CLOCK_MONOTONIC,
  82                 .get_time = &ktime_get,
  83                 .resolution = KTIME_MONOTONIC_RES,
  84         },
  85 };
  86
  87 /**
  88  * ktime_get_ts - get the monotonic clock in timespec format
  89  *
  90  * @ts:         pointer to timespec variable
  91  *
  92  * The function calculates the monotonic clock from the realtime
  93  * clock and the wall_to_monotonic offset and stores the result
  94  * in normalized timespec format in the variable pointed to by ts.
  95  */
  96 void ktime_get_ts(struct timespec *ts)
  97 {
  98         struct timespec tomono;
  99         unsigned long seq;
 100
 101         do {
 102                 seq = read_seqbegin(&xtime_lock);
 103                 getnstimeofday(ts);
 104                 tomono = wall_to_monotonic;
 105
 106         } while (read_seqretry(&xtime_lock, seq));
 107
 108         set_normalized_timespec(ts, ts->tv_sec + tomono.tv_sec,
 109                                 ts->tv_nsec + tomono.tv_nsec);
 110 }
 111 EXPORT_SYMBOL_GPL(ktime_get_ts);
 112
 113 /*
 114  * Functions and macros which are different for UP/SMP systems are kept in a
 115  * single place
 116  */
 117 #ifdef CONFIG_SMP
 118
 119 #define set_curr_timer(b, t)            do { (b)->curr_timer = (t); } while (0)
 120
 121 /*
 122  * We are using hashed locking: holding per_cpu(hrtimer_bases)[n].lock
 123  * means that all timers which are tied to this base via timer->base are
 124  * locked, and the base itself is locked too.
 125  *
 126  * So __run_timers/migrate_timers can safely modify all timers which could
 127  * be found on the lists/queues.
 128  *
 129  * When the timer's base is locked, and the timer removed from list, it is
 130  * possible to set timer->base = NULL and drop the lock: the timer remains
 131  * locked.
 132  */
 133 static struct hrtimer_base *lock_hrtimer_base(const struct hrtimer *timer,
 134                                               unsigned long *flags)
 135 {
 136         struct hrtimer_base *base;
 137
 138         for (;;) {
 139                 base = timer->base;
 140                 if (likely(base != NULL)) {
 141                         spin_lock_irqsave(&base->lock, *flags);
 142                         if (likely(base == timer->base))
 143                                 return base;
 144                         /* The timer has migrated to another CPU: */
 145                         spin_unlock_irqrestore(&base->lock, *flags);
 146                 }
 147                 cpu_relax();
 148         }
 149 }
 150
 151 /*
 152  * Switch the timer base to the current CPU when possible.
 153  */
 154 static inline struct hrtimer_base *
 155 switch_hrtimer_base(struct hrtimer *timer, struct hrtimer_base *base)
 156 {
 157         struct hrtimer_base *new_base;
 158
 159         new_base = &__get_cpu_var(hrtimer_bases[base->index]);
 160
 161         if (base != new_base) {
 162                 /*
 163                  * We are trying to schedule the timer on the local CPU.
 164                  * However we can't change timer's base while it is running,
 165                  * so we keep it on the same CPU. No hassle vs. reprogramming
 166                  * the event source in the high resolution case. The softirq
 167                  * code will take care of this when the timer function has
 168                  * completed. There is no conflict as we hold the lock until
 169                  * the timer is enqueued.
 170                  */
 171                 if (unlikely(base->curr_timer == timer))
 172                         return base;
 173
 174                 /* See the comment in lock_timer_base() */
 175                 timer->base = NULL;
 176                 spin_unlock(&base->lock);
 177                 spin_lock(&new_base->lock);
 178                 timer->base = new_base;
 179         }
 180         return new_base;
 181 }
 182
 183 #else /* CONFIG_SMP */
 184
 185 #define set_curr_timer(b, t)            do { } while (0)
 186
 187 static inline struct hrtimer_base *
 188 lock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
 189 {
 190         struct hrtimer_base *base = timer->base;
 191
 192         spin_lock_irqsave(&base->lock, *flags);
 193
 194         return base;
 195 }
 196
 197 #define switch_hrtimer_base(t, b)       (b)
 198
 199 #endif  /* !CONFIG_SMP */
 200
 201 /*
 202  * Functions for the union type storage format of ktime_t which are
 203  * too large for inlining:
 204  */
 205 #if BITS_PER_LONG < 64
 206 # ifndef CONFIG_KTIME_SCALAR
 207 /**
 208  * ktime_add_ns - Add a scalar nanoseconds value to a ktime_t variable
 209  *
 210  * @kt:         addend
 211  * @nsec:       the scalar nsec value to add
 212  *
 213  * Returns the sum of kt and nsec in ktime_t format
 214  */
 215 ktime_t ktime_add_ns(const ktime_t kt, u64 nsec)
 216 {
 217         ktime_t tmp;
 218
 219         if (likely(nsec < NSEC_PER_SEC)) {
 220                 tmp.tv64 = nsec;
 221         } else {
 222                 unsigned long rem = do_div(nsec, NSEC_PER_SEC);
 223
 224                 tmp = ktime_set((long)nsec, rem);
 225         }
 226
 227         return ktime_add(kt, tmp);
 228 }
 229
 230 #else /* CONFIG_KTIME_SCALAR */
 231
 232 # endif /* !CONFIG_KTIME_SCALAR */
 233
 234 /*
 235  * Divide a ktime value by a nanosecond value
 236  */
 237 static unsigned long ktime_divns(const ktime_t kt, nsec_t div)
 238 {
 239         u64 dclc, inc, dns;
 240         int sft = 0;
 241
 242         dclc = dns = ktime_to_ns(kt);
 243         inc = div;
 244         /* Make sure the divisor is less than 2^32: */
 245         while (div >> 32) {
 246                 sft++;
 247                 div >>= 1;
 248         }
 249         dclc >>= sft;
 250         do_div(dclc, (unsigned long) div);
 251
 252         return (unsigned long) dclc;
 253 }
 254
 255 #else /* BITS_PER_LONG < 64 */
 256 # define ktime_divns(kt, div)           (unsigned long)((kt).tv64 / (div))
 257 #endif /* BITS_PER_LONG >= 64 */
 258
 259 /*
 260  * Counterpart to lock_timer_base above:
 261  */
 262 static inline
 263 void unlock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
 264 {
 265         spin_unlock_irqrestore(&timer->base->lock, *flags);
 266 }
 267
 268 /**
 269  * hrtimer_forward - forward the timer expiry
 270  *
 271  * @timer:      hrtimer to forward
 272  * @interval:   the interval to forward
 273  *
 274  * Forward the timer expiry so it will expire in the future.
 275  * The number of overruns is added to the overrun field.
 276  */
 277 unsigned long
 278 hrtimer_forward(struct hrtimer *timer, const ktime_t interval)
 279 {
 280         unsigned long orun = 1;
 281         ktime_t delta, now;
 282
 283         now = timer->base->get_time();
 284
 285         delta = ktime_sub(now, timer->expires);
 286
 287         if (delta.tv64 < 0)
 288                 return 0;
 289
 290         if (unlikely(delta.tv64 >= interval.tv64)) {
 291                 nsec_t incr = ktime_to_ns(interval);
 292
 293                 orun = ktime_divns(delta, incr);
 294                 timer->expires = ktime_add_ns(timer->expires, incr * orun);
 295                 if (timer->expires.tv64 > now.tv64)
 296                         return orun;
 297                 /*
 298                  * This (and the ktime_add() below) is the
 299                  * correction for exact:
 300                  */
 301                 orun++;
 302         }
 303         timer->expires = ktime_add(timer->expires, interval);
 304
 305         return orun;
 306 }
 307
 308 /*
 309  * enqueue_hrtimer - internal function to (re)start a timer
 310  *
 311  * The timer is inserted in expiry order. Insertion into the
 312  * red black tree is O(log(n)). Must hold the base lock.
 313  */
 314 static void enqueue_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
 315 {
 316         struct rb_node **link = &base->active.rb_node;
 317         struct rb_node *parent = NULL;
 318         struct hrtimer *entry;
 319
 320         /*
 321          * Find the right place in the rbtree:
 322          */
 323         while (*link) {
 324                 parent = *link;
 325                 entry = rb_entry(parent, struct hrtimer, node);
 326                 /*
 327                  * We dont care about collisions. Nodes with
 328                  * the same expiry time stay together.
 329                  */
 330                 if (timer->expires.tv64 < entry->expires.tv64)
 331                         link = &(*link)->rb_left;
 332                 else
 333                         link = &(*link)->rb_right;
 334         }
 335
 336         /*
 337          * Insert the timer to the rbtree and check whether it
 338          * replaces the first pending timer
 339          */
 340         rb_link_node(&timer->node, parent, link);
 341         rb_insert_color(&timer->node, &base->active);
 342
 343         timer->state = HRTIMER_PENDING;
 344
 345         if (!base->first || timer->expires.tv64 <
 346             rb_entry(base->first, struct hrtimer, node)->expires.tv64)
 347                 base->first = &timer->node;
 348 }
 349
 350 /*
 351  * __remove_hrtimer - internal function to remove a timer
 352  *
 353  * Caller must hold the base lock.
 354  */
 355 static void __remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
 356 {
 357         /*
 358          * Remove the timer from the rbtree and replace the
 359          * first entry pointer if necessary.
 360          */
 361         if (base->first == &timer->node)
 362                 base->first = rb_next(&timer->node);
 363         rb_erase(&timer->node, &base->active);
 364 }
 365
 366 /*
 367  * remove hrtimer, called with base lock held
 368  */
 369 static inline int
 370 remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
 371 {
 372         if (hrtimer_active(timer)) {
 373                 __remove_hrtimer(timer, base);
 374                 timer->state = HRTIMER_INACTIVE;
 375                 return 1;
 376         }
 377         return 0;
 378 }
 379
 380 /**
 381  * hrtimer_start - (re)start an relative timer on the current CPU
 382  *
 383  * @timer:      the timer to be added
 384  * @tim:        expiry time
 385  * @mode:       expiry mode: absolute (HRTIMER_ABS) or relative (HRTIMER_REL)
 386  *
 387  * Returns:
 388  *  0 on success
 389  *  1 when the timer was active
 390  */
 391 int
 392 hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode)
 393 {
 394         struct hrtimer_base *base, *new_base;
 395         unsigned long flags;
 396         int ret;
 397
 398         base = lock_hrtimer_base(timer, &flags);
 399
 400         /* Remove an active timer from the queue: */
 401         ret = remove_hrtimer(timer, base);
 402
 403         /* Switch the timer base, if necessary: */
 404         new_base = switch_hrtimer_base(timer, base);
 405
 406         if (mode == HRTIMER_REL)
 407                 tim = ktime_add(tim, new_base->get_time());
 408         timer->expires = tim;
 409
 410         enqueue_hrtimer(timer, new_base);
 411
 412         unlock_hrtimer_base(timer, &flags);
 413
 414         return ret;
 415 }
 416
 417 /**
 418  * hrtimer_try_to_cancel - try to deactivate a timer
 419  *
 420  * @timer:      hrtimer to stop
 421  *
 422  * Returns:
 423  *  0 when the timer was not active
 424  *  1 when the timer was active
 425  * -1 when the timer is currently excuting the callback function and
 426  *    can not be stopped
 427  */
 428 int hrtimer_try_to_cancel(struct hrtimer *timer)
 429 {
 430         struct hrtimer_base *base;
 431         unsigned long flags;
 432         int ret = -1;
 433
 434         base = lock_hrtimer_base(timer, &flags);
 435
 436         if (base->curr_timer != timer)
 437                 ret = remove_hrtimer(timer, base);
 438
 439         unlock_hrtimer_base(timer, &flags);
 440
 441         return ret;
 442
 443 }
 444
 445 /**
 446  * hrtimer_cancel - cancel a timer and wait for the handler to finish.
 447  *
 448  * @timer:      the timer to be cancelled
 449  *
 450  * Returns:
 451  *  0 when the timer was not active
 452  *  1 when the timer was active
 453  */
 454 int hrtimer_cancel(struct hrtimer *timer)
 455 {
 456         for (;;) {
 457                 int ret = hrtimer_try_to_cancel(timer);
 458
 459                 if (ret >= 0)
 460                         return ret;
 461         }
 462 }
 463
 464 /**
 465  * hrtimer_get_remaining - get remaining time for the timer
 466  *
 467  * @timer:      the timer to read
 468  */
 469 ktime_t hrtimer_get_remaining(const struct hrtimer *timer)
 470 {
 471         struct hrtimer_base *base;
 472         unsigned long flags;
 473         ktime_t rem;
 474
 475         base = lock_hrtimer_base(timer, &flags);
 476         rem = ktime_sub(timer->expires, timer->base->get_time());
 477         unlock_hrtimer_base(timer, &flags);
 478
 479         return rem;
 480 }
 481
 482 /**
 483  * hrtimer_rebase - rebase an initialized hrtimer to a different base
 484  *
 485  * @timer:      the timer to be rebased
 486  * @clock_id:   the clock to be used
 487  */
 488 void hrtimer_rebase(struct hrtimer *timer, const clockid_t clock_id)
 489 {
 490         struct hrtimer_base *bases;
 491
 492         bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
 493         timer->base = &bases[clock_id];
 494 }
 495
 496 /**
 497  * hrtimer_init - initialize a timer to the given clock
 498  *
 499  * @timer:      the timer to be initialized
 500  * @clock_id:   the clock to be used
 501  */
 502 void hrtimer_init(struct hrtimer *timer, const clockid_t clock_id)
 503 {
 504         memset(timer, 0, sizeof(struct hrtimer));
 505         hrtimer_rebase(timer, clock_id);
 506 }
 507
 508 /**
 509  * hrtimer_get_res - get the timer resolution for a clock
 510  *
 511  * @which_clock: which clock to query
 512  * @tp:          pointer to timespec variable to store the resolution
 513  *
 514  * Store the resolution of the clock selected by which_clock in the
 515  * variable pointed to by tp.
 516  */
 517 int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp)
 518 {
 519         struct hrtimer_base *bases;
 520
 521         bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
 522         *tp = ktime_to_timespec(bases[which_clock].resolution);
 523
 524         return 0;
 525 }
 526
 527 /*
 528  * Expire the per base hrtimer-queue:
 529  */
 530 static inline void run_hrtimer_queue(struct hrtimer_base *base)
 531 {
 532         ktime_t now = base->get_time();
 533         struct rb_node *node;
 534
 535         spin_lock_irq(&base->lock);
 536
 537         while ((node = base->first)) {
 538                 struct hrtimer *timer;
 539                 int (*fn)(void *);
 540                 int restart;
 541                 void *data;
 542
 543                 timer = rb_entry(node, struct hrtimer, node);
 544                 if (now.tv64 <= timer->expires.tv64)
 545                         break;
 546
 547                 fn = timer->function;
 548                 data = timer->data;
 549                 set_curr_timer(base, timer);
 550                 __remove_hrtimer(timer, base);
 551                 spin_unlock_irq(&base->lock);
 552
 553                 /*
 554                  * fn == NULL is special case for the simplest timer
 555                  * variant - wake up process and do not restart:
 556                  */
 557                 if (!fn) {
 558                         wake_up_process(data);
 559                         restart = HRTIMER_NORESTART;
 560                 } else
 561                         restart = fn(data);
 562
 563                 spin_lock_irq(&base->lock);
 564
 565                 if (restart == HRTIMER_RESTART)
 566                         enqueue_hrtimer(timer, base);
 567                 else
 568                         timer->state = HRTIMER_EXPIRED;
 569         }
 570         set_curr_timer(base, NULL);
 571         spin_unlock_irq(&base->lock);
 572 }
 573
 574 /*
 575  * Called from timer softirq every jiffy, expire hrtimers:
 576  */
 577 void hrtimer_run_queues(void)
 578 {
 579         struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
 580         int i;
 581
 582         for (i = 0; i < MAX_HRTIMER_BASES; i++)
 583                 run_hrtimer_queue(&base[i]);
 584 }
 585
 586 /*
 587  * Sleep related functions:
 588  */
 589
 590 /**
 591  * schedule_hrtimer - sleep until timeout
 592  *
 593  * @timer:      hrtimer variable initialized with the correct clock base
 594  * @mode:       timeout value is abs/rel
 595  *
 596  * Make the current task sleep until @timeout is
 597  * elapsed.
 598  *
 599  * You can set the task state as follows -
 600  *
 601  * %TASK_UNINTERRUPTIBLE - at least @timeout is guaranteed to
 602  * pass before the routine returns. The routine will return 0
 603  *
 604  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
 605  * delivered to the current task. In this case the remaining time
 606  * will be returned
 607  *
 608  * The current task state is guaranteed to be TASK_RUNNING when this
 609  * routine returns.
 610  */
 611 static ktime_t __sched
 612 schedule_hrtimer(struct hrtimer *timer, const enum hrtimer_mode mode)
 613 {
 614         /* fn stays NULL, meaning single-shot wakeup: */
 615         timer->data = current;
 616
 617         hrtimer_start(timer, timer->expires, mode);
 618
 619         schedule();
 620         hrtimer_cancel(timer);
 621
 622         /* Return the remaining time: */
 623         if (timer->state != HRTIMER_EXPIRED)
 624                 return ktime_sub(timer->expires, timer->base->get_time());
 625         else
 626                 return (ktime_t) {.tv64 = 0 };
 627 }
 628
 629 static inline ktime_t __sched
 630 schedule_hrtimer_interruptible(struct hrtimer *timer,
 631                                const enum hrtimer_mode mode)
 632 {
 633         set_current_state(TASK_INTERRUPTIBLE);
 634
 635         return schedule_hrtimer(timer, mode);
 636 }
 637
 638 static long __sched
 639 nanosleep_restart(struct restart_block *restart, clockid_t clockid)
 640 {
 641         struct timespec __user *rmtp, tu;
 642         void *rfn_save = restart->fn;
 643         struct hrtimer timer;
 644         ktime_t rem;
 645
 646         restart->fn = do_no_restart_syscall;
 647
 648         hrtimer_init(&timer, clockid);
 649
 650         timer.expires.tv64 = ((u64)restart->arg1 << 32) | (u64) restart->arg0;
 651
 652         rem = schedule_hrtimer_interruptible(&timer, HRTIMER_ABS);
 653
 654         if (rem.tv64 <= 0)
 655                 return 0;
 656
 657         rmtp = (struct timespec __user *) restart->arg2;
 658         tu = ktime_to_timespec(rem);
 659         if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
 660                 return -EFAULT;
 661
 662         restart->fn = rfn_save;
 663
 664         /* The other values in restart are already filled in */
 665         return -ERESTART_RESTARTBLOCK;
 666 }
 667
 668 static long __sched nanosleep_restart_mono(struct restart_block *restart)
 669 {
 670         return nanosleep_restart(restart, CLOCK_MONOTONIC);
 671 }
 672
 673 static long __sched nanosleep_restart_real(struct restart_block *restart)
 674 {
 675         return nanosleep_restart(restart, CLOCK_REALTIME);
 676 }
 677
 678 long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
 679                        const enum hrtimer_mode mode, const clockid_t clockid)
 680 {
 681         struct restart_block *restart;
 682         struct hrtimer timer;
 683         struct timespec tu;
 684         ktime_t rem;
 685
 686         hrtimer_init(&timer, clockid);
 687
 688         timer.expires = timespec_to_ktime(*rqtp);
 689
 690         rem = schedule_hrtimer_interruptible(&timer, mode);
 691         if (rem.tv64 <= 0)
 692                 return 0;
 693
 694         /* Absolute timers do not update the rmtp value: */
 695         if (mode == HRTIMER_ABS)
 696                 return -ERESTARTNOHAND;
 697
 698         tu = ktime_to_timespec(rem);
 699
 700         if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
 701                 return -EFAULT;
 702
 703         restart = &current_thread_info()->restart_block;
 704         restart->fn = (clockid == CLOCK_MONOTONIC) ?
 705                 nanosleep_restart_mono : nanosleep_restart_real;
 706         restart->arg0 = timer.expires.tv64 & 0xFFFFFFFF;
 707         restart->arg1 = timer.expires.tv64 >> 32;
 708         restart->arg2 = (unsigned long) rmtp;
 709
 710         return -ERESTART_RESTARTBLOCK;
 711 }
 712
 713 asmlinkage long
 714 sys_nanosleep(struct timespec __user *rqtp, struct timespec __user *rmtp)
 715 {
 716         struct timespec tu;
 717
 718         if (copy_from_user(&tu, rqtp, sizeof(tu)))
 719                 return -EFAULT;
 720
 721         if (!timespec_valid(&tu))
 722                 return -EINVAL;
 723
 724         return hrtimer_nanosleep(&tu, rmtp, HRTIMER_REL, CLOCK_MONOTONIC);
 725 }
 726
 727 /*
 728  * Functions related to boot-time initialization:
 729  */
 730 static void __devinit init_hrtimers_cpu(int cpu)
 731 {
 732         struct hrtimer_base *base = per_cpu(hrtimer_bases, cpu);
 733         int i;
 734
 735         for (i = 0; i < MAX_HRTIMER_BASES; i++) {
 736                 spin_lock_init(&base->lock);
 737                 base++;
 738         }
 739 }
 740
 741 #ifdef CONFIG_HOTPLUG_CPU
 742
 743 static void migrate_hrtimer_list(struct hrtimer_base *old_base,
 744                                 struct hrtimer_base *new_base)
 745 {
 746         struct hrtimer *timer;
 747         struct rb_node *node;
 748
 749         while ((node = rb_first(&old_base->active))) {
 750                 timer = rb_entry(node, struct hrtimer, node);
 751                 __remove_hrtimer(timer, old_base);
 752                 timer->base = new_base;
 753                 enqueue_hrtimer(timer, new_base);
 754         }
 755 }
 756
 757 static void migrate_hrtimers(int cpu)
 758 {
 759         struct hrtimer_base *old_base, *new_base;
 760         int i;
 761
 762         BUG_ON(cpu_online(cpu));
 763         old_base = per_cpu(hrtimer_bases, cpu);
 764         new_base = get_cpu_var(hrtimer_bases);
 765
 766         local_irq_disable();
 767
 768         for (i = 0; i < MAX_HRTIMER_BASES; i++) {
 769
 770                 spin_lock(&new_base->lock);
 771                 spin_lock(&old_base->lock);
 772
 773                 BUG_ON(old_base->curr_timer);
 774
 775                 migrate_hrtimer_list(old_base, new_base);
 776
 777                 spin_unlock(&old_base->lock);
 778                 spin_unlock(&new_base->lock);
 779                 old_base++;
 780                 new_base++;
 781         }
 782
 783         local_irq_enable();
 784         put_cpu_var(hrtimer_bases);
 785 }
 786 #endif /* CONFIG_HOTPLUG_CPU */
 787
 788 static int __devinit hrtimer_cpu_notify(struct notifier_block *self,
 789                                         unsigned long action, void *hcpu)
 790 {
 791         long cpu = (long)hcpu;
 792
 793         switch (action) {
 794
 795         case CPU_UP_PREPARE:
 796                 init_hrtimers_cpu(cpu);
 797                 break;
 798
 799 #ifdef CONFIG_HOTPLUG_CPU
 800         case CPU_DEAD:
 801                 migrate_hrtimers(cpu);
 802                 break;
 803 #endif
 804
 805         default:
 806                 break;
 807         }
 808
 809         return NOTIFY_OK;
 810 }
 811
 812 static struct notifier_block __devinitdata hrtimers_nb = {
 813         .notifier_call = hrtimer_cpu_notify,
 814 };
 815
 816 void __init hrtimers_init(void)
 817 {
 818         hrtimer_cpu_notify(&hrtimers_nb, (unsigned long)CPU_UP_PREPARE,
 819                           (void *)(long)smp_processor_id());
 820         register_cpu_notifier(&hrtimers_nb);
 821 }
 822