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 list_head *prev = &base->pending;
 318         struct rb_node *parent = NULL;
 319         struct hrtimer *entry;
 320
 321         /*
 322          * Find the right place in the rbtree:
 323          */
 324         while (*link) {
 325                 parent = *link;
 326                 entry = rb_entry(parent, struct hrtimer, node);
 327                 /*
 328                  * We dont care about collisions. Nodes with
 329                  * the same expiry time stay together.
 330                  */
 331                 if (timer->expires.tv64 < entry->expires.tv64)
 332                         link = &(*link)->rb_left;
 333                 else {
 334                         link = &(*link)->rb_right;
 335                         prev = &entry->list;
 336                 }
 337         }
 338
 339         /*
 340          * Insert the timer to the rbtree and to the sorted list:
 341          */
 342         rb_link_node(&timer->node, parent, link);
 343         rb_insert_color(&timer->node, &base->active);
 344         list_add(&timer->list, prev);
 345
 346         timer->state = HRTIMER_PENDING;
 347 }
 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 sorted list and from the rbtree:
 359          */
 360         list_del(&timer->list);
 361         rb_erase(&timer->node, &base->active);
 362 }
 363
 364 /*
 365  * remove hrtimer, called with base lock held
 366  */
 367 static inline int
 368 remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
 369 {
 370         if (hrtimer_active(timer)) {
 371                 __remove_hrtimer(timer, base);
 372                 timer->state = HRTIMER_INACTIVE;
 373                 return 1;
 374         }
 375         return 0;
 376 }
 377
 378 /**
 379  * hrtimer_start - (re)start an relative timer on the current CPU
 380  *
 381  * @timer:      the timer to be added
 382  * @tim:        expiry time
 383  * @mode:       expiry mode: absolute (HRTIMER_ABS) or relative (HRTIMER_REL)
 384  *
 385  * Returns:
 386  *  0 on success
 387  *  1 when the timer was active
 388  */
 389 int
 390 hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode)
 391 {
 392         struct hrtimer_base *base, *new_base;
 393         unsigned long flags;
 394         int ret;
 395
 396         base = lock_hrtimer_base(timer, &flags);
 397
 398         /* Remove an active timer from the queue: */
 399         ret = remove_hrtimer(timer, base);
 400
 401         /* Switch the timer base, if necessary: */
 402         new_base = switch_hrtimer_base(timer, base);
 403
 404         if (mode == HRTIMER_REL)
 405                 tim = ktime_add(tim, new_base->get_time());
 406         timer->expires = tim;
 407
 408         enqueue_hrtimer(timer, new_base);
 409
 410         unlock_hrtimer_base(timer, &flags);
 411
 412         return ret;
 413 }
 414
 415 /**
 416  * hrtimer_try_to_cancel - try to deactivate a timer
 417  *
 418  * @timer:      hrtimer to stop
 419  *
 420  * Returns:
 421  *  0 when the timer was not active
 422  *  1 when the timer was active
 423  * -1 when the timer is currently excuting the callback function and
 424  *    can not be stopped
 425  */
 426 int hrtimer_try_to_cancel(struct hrtimer *timer)
 427 {
 428         struct hrtimer_base *base;
 429         unsigned long flags;
 430         int ret = -1;
 431
 432         base = lock_hrtimer_base(timer, &flags);
 433
 434         if (base->curr_timer != timer)
 435                 ret = remove_hrtimer(timer, base);
 436
 437         unlock_hrtimer_base(timer, &flags);
 438
 439         return ret;
 440
 441 }
 442
 443 /**
 444  * hrtimer_cancel - cancel a timer and wait for the handler to finish.
 445  *
 446  * @timer:      the timer to be cancelled
 447  *
 448  * Returns:
 449  *  0 when the timer was not active
 450  *  1 when the timer was active
 451  */
 452 int hrtimer_cancel(struct hrtimer *timer)
 453 {
 454         for (;;) {
 455                 int ret = hrtimer_try_to_cancel(timer);
 456
 457                 if (ret >= 0)
 458                         return ret;
 459         }
 460 }
 461
 462 /**
 463  * hrtimer_get_remaining - get remaining time for the timer
 464  *
 465  * @timer:      the timer to read
 466  */
 467 ktime_t hrtimer_get_remaining(const struct hrtimer *timer)
 468 {
 469         struct hrtimer_base *base;
 470         unsigned long flags;
 471         ktime_t rem;
 472
 473         base = lock_hrtimer_base(timer, &flags);
 474         rem = ktime_sub(timer->expires, timer->base->get_time());
 475         unlock_hrtimer_base(timer, &flags);
 476
 477         return rem;
 478 }
 479
 480 /**
 481  * hrtimer_rebase - rebase an initialized hrtimer to a different base
 482  *
 483  * @timer:      the timer to be rebased
 484  * @clock_id:   the clock to be used
 485  */
 486 void hrtimer_rebase(struct hrtimer *timer, const clockid_t clock_id)
 487 {
 488         struct hrtimer_base *bases;
 489
 490         bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
 491         timer->base = &bases[clock_id];
 492 }
 493
 494 /**
 495  * hrtimer_init - initialize a timer to the given clock
 496  *
 497  * @timer:      the timer to be initialized
 498  * @clock_id:   the clock to be used
 499  */
 500 void hrtimer_init(struct hrtimer *timer, const clockid_t clock_id)
 501 {
 502         memset(timer, 0, sizeof(struct hrtimer));
 503         hrtimer_rebase(timer, clock_id);
 504 }
 505
 506 /**
 507  * hrtimer_get_res - get the timer resolution for a clock
 508  *
 509  * @which_clock: which clock to query
 510  * @tp:          pointer to timespec variable to store the resolution
 511  *
 512  * Store the resolution of the clock selected by which_clock in the
 513  * variable pointed to by tp.
 514  */
 515 int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp)
 516 {
 517         struct hrtimer_base *bases;
 518
 519         tp->tv_sec = 0;
 520         bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
 521         tp->tv_nsec = bases[which_clock].resolution;
 522
 523         return 0;
 524 }
 525
 526 /*
 527  * Expire the per base hrtimer-queue:
 528  */
 529 static inline void run_hrtimer_queue(struct hrtimer_base *base)
 530 {
 531         ktime_t now = base->get_time();
 532
 533         spin_lock_irq(&base->lock);
 534
 535         while (!list_empty(&base->pending)) {
 536                 struct hrtimer *timer;
 537                 int (*fn)(void *);
 538                 int restart;
 539                 void *data;
 540
 541                 timer = list_entry(base->pending.next, struct hrtimer, list);
 542                 if (now.tv64 <= timer->expires.tv64)
 543                         break;
 544
 545                 fn = timer->function;
 546                 data = timer->data;
 547                 set_curr_timer(base, timer);
 548                 __remove_hrtimer(timer, base);
 549                 spin_unlock_irq(&base->lock);
 550
 551                 /*
 552                  * fn == NULL is special case for the simplest timer
 553                  * variant - wake up process and do not restart:
 554                  */
 555                 if (!fn) {
 556                         wake_up_process(data);
 557                         restart = HRTIMER_NORESTART;
 558                 } else
 559                         restart = fn(data);
 560
 561                 spin_lock_irq(&base->lock);
 562
 563                 if (restart == HRTIMER_RESTART)
 564                         enqueue_hrtimer(timer, base);
 565                 else
 566                         timer->state = HRTIMER_EXPIRED;
 567         }
 568         set_curr_timer(base, NULL);
 569         spin_unlock_irq(&base->lock);
 570 }
 571
 572 /*
 573  * Called from timer softirq every jiffy, expire hrtimers:
 574  */
 575 void hrtimer_run_queues(void)
 576 {
 577         struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
 578         int i;
 579
 580         for (i = 0; i < MAX_HRTIMER_BASES; i++)
 581                 run_hrtimer_queue(&base[i]);
 582 }
 583
 584 /*
 585  * Sleep related functions:
 586  */
 587
 588 /**
 589  * schedule_hrtimer - sleep until timeout
 590  *
 591  * @timer:      hrtimer variable initialized with the correct clock base
 592  * @mode:       timeout value is abs/rel
 593  *
 594  * Make the current task sleep until @timeout is
 595  * elapsed.
 596  *
 597  * You can set the task state as follows -
 598  *
 599  * %TASK_UNINTERRUPTIBLE - at least @timeout is guaranteed to
 600  * pass before the routine returns. The routine will return 0
 601  *
 602  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
 603  * delivered to the current task. In this case the remaining time
 604  * will be returned
 605  *
 606  * The current task state is guaranteed to be TASK_RUNNING when this
 607  * routine returns.
 608  */
 609 static ktime_t __sched
 610 schedule_hrtimer(struct hrtimer *timer, const enum hrtimer_mode mode)
 611 {
 612         /* fn stays NULL, meaning single-shot wakeup: */
 613         timer->data = current;
 614
 615         hrtimer_start(timer, timer->expires, mode);
 616
 617         schedule();
 618         hrtimer_cancel(timer);
 619
 620         /* Return the remaining time: */
 621         if (timer->state != HRTIMER_EXPIRED)
 622                 return ktime_sub(timer->expires, timer->base->get_time());
 623         else
 624                 return (ktime_t) {.tv64 = 0 };
 625 }
 626
 627 static inline ktime_t __sched
 628 schedule_hrtimer_interruptible(struct hrtimer *timer,
 629                                const enum hrtimer_mode mode)
 630 {
 631         set_current_state(TASK_INTERRUPTIBLE);
 632
 633         return schedule_hrtimer(timer, mode);
 634 }
 635
 636 static long __sched
 637 nanosleep_restart(struct restart_block *restart, clockid_t clockid)
 638 {
 639         struct timespec __user *rmtp, tu;
 640         void *rfn_save = restart->fn;
 641         struct hrtimer timer;
 642         ktime_t rem;
 643
 644         restart->fn = do_no_restart_syscall;
 645
 646         hrtimer_init(&timer, clockid);
 647
 648         timer.expires.tv64 = ((u64)restart->arg1 << 32) | (u64) restart->arg0;
 649
 650         rem = schedule_hrtimer_interruptible(&timer, HRTIMER_ABS);
 651
 652         if (rem.tv64 <= 0)
 653                 return 0;
 654
 655         rmtp = (struct timespec __user *) restart->arg2;
 656         tu = ktime_to_timespec(rem);
 657         if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
 658                 return -EFAULT;
 659
 660         restart->fn = rfn_save;
 661
 662         /* The other values in restart are already filled in */
 663         return -ERESTART_RESTARTBLOCK;
 664 }
 665
 666 static long __sched nanosleep_restart_mono(struct restart_block *restart)
 667 {
 668         return nanosleep_restart(restart, CLOCK_MONOTONIC);
 669 }
 670
 671 static long __sched nanosleep_restart_real(struct restart_block *restart)
 672 {
 673         return nanosleep_restart(restart, CLOCK_REALTIME);
 674 }
 675
 676 long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
 677                        const enum hrtimer_mode mode, const clockid_t clockid)
 678 {
 679         struct restart_block *restart;
 680         struct hrtimer timer;
 681         struct timespec tu;
 682         ktime_t rem;
 683
 684         hrtimer_init(&timer, clockid);
 685
 686         timer.expires = timespec_to_ktime(*rqtp);
 687
 688         rem = schedule_hrtimer_interruptible(&timer, mode);
 689         if (rem.tv64 <= 0)
 690                 return 0;
 691
 692         /* Absolute timers do not update the rmtp value: */
 693         if (mode == HRTIMER_ABS)
 694                 return -ERESTARTNOHAND;
 695
 696         tu = ktime_to_timespec(rem);
 697
 698         if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
 699                 return -EFAULT;
 700
 701         restart = &current_thread_info()->restart_block;
 702         restart->fn = (clockid == CLOCK_MONOTONIC) ?
 703                 nanosleep_restart_mono : nanosleep_restart_real;
 704         restart->arg0 = timer.expires.tv64 & 0xFFFFFFFF;
 705         restart->arg1 = timer.expires.tv64 >> 32;
 706         restart->arg2 = (unsigned long) rmtp;
 707
 708         return -ERESTART_RESTARTBLOCK;
 709 }
 710
 711 asmlinkage long
 712 sys_nanosleep(struct timespec __user *rqtp, struct timespec __user *rmtp)
 713 {
 714         struct timespec tu;
 715
 716         if (copy_from_user(&tu, rqtp, sizeof(tu)))
 717                 return -EFAULT;
 718
 719         if (!timespec_valid(&tu))
 720                 return -EINVAL;
 721
 722         return hrtimer_nanosleep(&tu, rmtp, HRTIMER_REL, CLOCK_MONOTONIC);
 723 }
 724
 725 /*
 726  * Functions related to boot-time initialization:
 727  */
 728 static void __devinit init_hrtimers_cpu(int cpu)
 729 {
 730         struct hrtimer_base *base = per_cpu(hrtimer_bases, cpu);
 731         int i;
 732
 733         for (i = 0; i < MAX_HRTIMER_BASES; i++) {
 734                 spin_lock_init(&base->lock);
 735                 INIT_LIST_HEAD(&base->pending);
 736                 base++;
 737         }
 738 }
 739
 740 #ifdef CONFIG_HOTPLUG_CPU
 741
 742 static void migrate_hrtimer_list(struct hrtimer_base *old_base,
 743                                 struct hrtimer_base *new_base)
 744 {
 745         struct hrtimer *timer;
 746         struct rb_node *node;
 747
 748         while ((node = rb_first(&old_base->active))) {
 749                 timer = rb_entry(node, struct hrtimer, node);
 750                 __remove_hrtimer(timer, old_base);
 751                 timer->base = new_base;
 752                 enqueue_hrtimer(timer, new_base);
 753         }
 754 }
 755
 756 static void migrate_hrtimers(int cpu)
 757 {
 758         struct hrtimer_base *old_base, *new_base;
 759         int i;
 760
 761         BUG_ON(cpu_online(cpu));
 762         old_base = per_cpu(hrtimer_bases, cpu);
 763         new_base = get_cpu_var(hrtimer_bases);
 764
 765         local_irq_disable();
 766
 767         for (i = 0; i < MAX_HRTIMER_BASES; i++) {
 768
 769                 spin_lock(&new_base->lock);
 770                 spin_lock(&old_base->lock);
 771
 772                 BUG_ON(old_base->curr_timer);
 773
 774                 migrate_hrtimer_list(old_base, new_base);
 775
 776                 spin_unlock(&old_base->lock);
 777                 spin_unlock(&new_base->lock);
 778                 old_base++;
 779                 new_base++;
 780         }
 781
 782         local_irq_enable();
 783         put_cpu_var(hrtimer_bases);
 784 }
 785 #endif /* CONFIG_HOTPLUG_CPU */
 786
 787 static int __devinit hrtimer_cpu_notify(struct notifier_block *self,
 788                                         unsigned long action, void *hcpu)
 789 {
 790         long cpu = (long)hcpu;
 791
 792         switch (action) {
 793
 794         case CPU_UP_PREPARE:
 795                 init_hrtimers_cpu(cpu);
 796                 break;
 797
 798 #ifdef CONFIG_HOTPLUG_CPU
 799         case CPU_DEAD:
 800                 migrate_hrtimers(cpu);
 801                 break;
 802 #endif
 803
 804         default:
 805                 break;
 806         }
 807
 808         return NOTIFY_OK;
 809 }
 810
 811 static struct notifier_block __devinitdata hrtimers_nb = {
 812         .notifier_call = hrtimer_cpu_notify,
 813 };
 814
 815 void __init hrtimers_init(void)
 816 {
 817         hrtimer_cpu_notify(&hrtimers_nb, (unsigned long)CPU_UP_PREPARE,
 818                           (void *)(long)smp_processor_id());
 819         register_cpu_notifier(&hrtimers_nb);
 820 }
 821