SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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         tp->tv_sec = 0;
 522         bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
 523         tp->tv_nsec = bases[which_clock].resolution;
 524
 525         return 0;
 526 }
 527
 528 /*
 529  * Expire the per base hrtimer-queue:
 530  */
 531 static inline void run_hrtimer_queue(struct hrtimer_base *base)
 532 {
 533         ktime_t now = base->get_time();
 534         struct rb_node *node;
 535
 536         spin_lock_irq(&base->lock);
 537
 538         while ((node = base->first)) {
 539                 struct hrtimer *timer;
 540                 int (*fn)(void *);
 541                 int restart;
 542                 void *data;
 543
 544                 timer = rb_entry(node, struct hrtimer, node);
 545                 if (now.tv64 <= timer->expires.tv64)
 546                         break;
 547
 548                 fn = timer->function;
 549                 data = timer->data;
 550                 set_curr_timer(base, timer);
 551                 __remove_hrtimer(timer, base);
 552                 spin_unlock_irq(&base->lock);
 553
 554                 /*
 555                  * fn == NULL is special case for the simplest timer
 556                  * variant - wake up process and do not restart:
 557                  */
 558                 if (!fn) {
 559                         wake_up_process(data);
 560                         restart = HRTIMER_NORESTART;
 561                 } else
 562                         restart = fn(data);
 563
 564                 spin_lock_irq(&base->lock);
 565
 566                 if (restart == HRTIMER_RESTART)
 567                         enqueue_hrtimer(timer, base);
 568                 else
 569                         timer->state = HRTIMER_EXPIRED;
 570         }
 571         set_curr_timer(base, NULL);
 572         spin_unlock_irq(&base->lock);
 573 }
 574
 575 /*
 576  * Called from timer softirq every jiffy, expire hrtimers:
 577  */
 578 void hrtimer_run_queues(void)
 579 {
 580         struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
 581         int i;
 582
 583         for (i = 0; i < MAX_HRTIMER_BASES; i++)
 584                 run_hrtimer_queue(&base[i]);
 585 }
 586
 587 /*
 588  * Sleep related functions:
 589  */
 590
 591 /**
 592  * schedule_hrtimer - sleep until timeout
 593  *
 594  * @timer:      hrtimer variable initialized with the correct clock base
 595  * @mode:       timeout value is abs/rel
 596  *
 597  * Make the current task sleep until @timeout is
 598  * elapsed.
 599  *
 600  * You can set the task state as follows -
 601  *
 602  * %TASK_UNINTERRUPTIBLE - at least @timeout is guaranteed to
 603  * pass before the routine returns. The routine will return 0
 604  *
 605  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
 606  * delivered to the current task. In this case the remaining time
 607  * will be returned
 608  *
 609  * The current task state is guaranteed to be TASK_RUNNING when this
 610  * routine returns.
 611  */
 612 static ktime_t __sched
 613 schedule_hrtimer(struct hrtimer *timer, const enum hrtimer_mode mode)
 614 {
 615         /* fn stays NULL, meaning single-shot wakeup: */
 616         timer->data = current;
 617
 618         hrtimer_start(timer, timer->expires, mode);
 619
 620         schedule();
 621         hrtimer_cancel(timer);
 622
 623         /* Return the remaining time: */
 624         if (timer->state != HRTIMER_EXPIRED)
 625                 return ktime_sub(timer->expires, timer->base->get_time());
 626         else
 627                 return (ktime_t) {.tv64 = 0 };
 628 }
 629
 630 static inline ktime_t __sched
 631 schedule_hrtimer_interruptible(struct hrtimer *timer,
 632                                const enum hrtimer_mode mode)
 633 {
 634         set_current_state(TASK_INTERRUPTIBLE);
 635
 636         return schedule_hrtimer(timer, mode);
 637 }
 638
 639 static long __sched
 640 nanosleep_restart(struct restart_block *restart, clockid_t clockid)
 641 {
 642         struct timespec __user *rmtp, tu;
 643         void *rfn_save = restart->fn;
 644         struct hrtimer timer;
 645         ktime_t rem;
 646
 647         restart->fn = do_no_restart_syscall;
 648
 649         hrtimer_init(&timer, clockid);
 650
 651         timer.expires.tv64 = ((u64)restart->arg1 << 32) | (u64) restart->arg0;
 652
 653         rem = schedule_hrtimer_interruptible(&timer, HRTIMER_ABS);
 654
 655         if (rem.tv64 <= 0)
 656                 return 0;
 657
 658         rmtp = (struct timespec __user *) restart->arg2;
 659         tu = ktime_to_timespec(rem);
 660         if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
 661                 return -EFAULT;
 662
 663         restart->fn = rfn_save;
 664
 665         /* The other values in restart are already filled in */
 666         return -ERESTART_RESTARTBLOCK;
 667 }
 668
 669 static long __sched nanosleep_restart_mono(struct restart_block *restart)
 670 {
 671         return nanosleep_restart(restart, CLOCK_MONOTONIC);
 672 }
 673
 674 static long __sched nanosleep_restart_real(struct restart_block *restart)
 675 {
 676         return nanosleep_restart(restart, CLOCK_REALTIME);
 677 }
 678
 679 long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
 680                        const enum hrtimer_mode mode, const clockid_t clockid)
 681 {
 682         struct restart_block *restart;
 683         struct hrtimer timer;
 684         struct timespec tu;
 685         ktime_t rem;
 686
 687         hrtimer_init(&timer, clockid);
 688
 689         timer.expires = timespec_to_ktime(*rqtp);
 690
 691         rem = schedule_hrtimer_interruptible(&timer, mode);
 692         if (rem.tv64 <= 0)
 693                 return 0;
 694
 695         /* Absolute timers do not update the rmtp value: */
 696         if (mode == HRTIMER_ABS)
 697                 return -ERESTARTNOHAND;
 698
 699         tu = ktime_to_timespec(rem);
 700
 701         if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
 702                 return -EFAULT;
 703
 704         restart = &current_thread_info()->restart_block;
 705         restart->fn = (clockid == CLOCK_MONOTONIC) ?
 706                 nanosleep_restart_mono : nanosleep_restart_real;
 707         restart->arg0 = timer.expires.tv64 & 0xFFFFFFFF;
 708         restart->arg1 = timer.expires.tv64 >> 32;
 709         restart->arg2 = (unsigned long) rmtp;
 710
 711         return -ERESTART_RESTARTBLOCK;
 712 }
 713
 714 asmlinkage long
 715 sys_nanosleep(struct timespec __user *rqtp, struct timespec __user *rmtp)
 716 {
 717         struct timespec tu;
 718
 719         if (copy_from_user(&tu, rqtp, sizeof(tu)))
 720                 return -EFAULT;
 721
 722         if (!timespec_valid(&tu))
 723                 return -EINVAL;
 724
 725         return hrtimer_nanosleep(&tu, rmtp, HRTIMER_REL, CLOCK_MONOTONIC);
 726 }
 727
 728 /*
 729  * Functions related to boot-time initialization:
 730  */
 731 static void __devinit init_hrtimers_cpu(int cpu)
 732 {
 733         struct hrtimer_base *base = per_cpu(hrtimer_bases, cpu);
 734         int i;
 735
 736         for (i = 0; i < MAX_HRTIMER_BASES; i++) {
 737                 spin_lock_init(&base->lock);
 738                 base++;
 739         }
 740 }
 741
 742 #ifdef CONFIG_HOTPLUG_CPU
 743
 744 static void migrate_hrtimer_list(struct hrtimer_base *old_base,
 745                                 struct hrtimer_base *new_base)
 746 {
 747         struct hrtimer *timer;
 748         struct rb_node *node;
 749
 750         while ((node = rb_first(&old_base->active))) {
 751                 timer = rb_entry(node, struct hrtimer, node);
 752                 __remove_hrtimer(timer, old_base);
 753                 timer->base = new_base;
 754                 enqueue_hrtimer(timer, new_base);
 755         }
 756 }
 757
 758 static void migrate_hrtimers(int cpu)
 759 {
 760         struct hrtimer_base *old_base, *new_base;
 761         int i;
 762
 763         BUG_ON(cpu_online(cpu));
 764         old_base = per_cpu(hrtimer_bases, cpu);
 765         new_base = get_cpu_var(hrtimer_bases);
 766
 767         local_irq_disable();
 768
 769         for (i = 0; i < MAX_HRTIMER_BASES; i++) {
 770
 771                 spin_lock(&new_base->lock);
 772                 spin_lock(&old_base->lock);
 773
 774                 BUG_ON(old_base->curr_timer);
 775
 776                 migrate_hrtimer_list(old_base, new_base);
 777
 778                 spin_unlock(&old_base->lock);
 779                 spin_unlock(&new_base->lock);
 780                 old_base++;
 781                 new_base++;
 782         }
 783
 784         local_irq_enable();
 785         put_cpu_var(hrtimer_bases);
 786 }
 787 #endif /* CONFIG_HOTPLUG_CPU */
 788
 789 static int __devinit hrtimer_cpu_notify(struct notifier_block *self,
 790                                         unsigned long action, void *hcpu)
 791 {
 792         long cpu = (long)hcpu;
 793
 794         switch (action) {
 795
 796         case CPU_UP_PREPARE:
 797                 init_hrtimers_cpu(cpu);
 798                 break;
 799
 800 #ifdef CONFIG_HOTPLUG_CPU
 801         case CPU_DEAD:
 802                 migrate_hrtimers(cpu);
 803                 break;
 804 #endif
 805
 806         default:
 807                 break;
 808         }
 809
 810         return NOTIFY_OK;
 811 }
 812
 813 static struct notifier_block __devinitdata hrtimers_nb = {
 814         .notifier_call = hrtimer_cpu_notify,
 815 };
 816
 817 void __init hrtimers_init(void)
 818 {
 819         hrtimer_cpu_notify(&hrtimers_nb, (unsigned long)CPU_UP_PREPARE,
 820                           (void *)(long)smp_processor_id());
 821         register_cpu_notifier(&hrtimers_nb);
 822 }
 823