[PATCH] Move pidmap to pspace.h
[linux-2.6.git] / kernel / hrtimer.c
index e6e8278..d0ba190 100644 (file)
  *  Credits:
  *     based on kernel/timer.c
  *
+ *     Help, testing, suggestions, bugfixes, improvements were
+ *     provided by:
+ *
+ *     George Anzinger, Andrew Morton, Steven Rostedt, Roman Zippel
+ *     et. al.
+ *
  *  For licencing details see kernel-base/COPYING
  */
 
@@ -66,6 +72,12 @@ EXPORT_SYMBOL_GPL(ktime_get_real);
 
 /*
  * The timer bases:
+ *
+ * Note: If we want to add new timer bases, we have to skip the two
+ * clock ids captured by the cpu-timers. We do this by holding empty
+ * entries rather than doing math adjustment of the clock ids.
+ * This ensures that we capture erroneous accesses to these clock ids
+ * rather than moving them into the range of valid clock id's.
  */
 
 #define MAX_HRTIMER_BASES 2
@@ -86,7 +98,6 @@ static DEFINE_PER_CPU(struct hrtimer_base, hrtimer_bases[MAX_HRTIMER_BASES]) =
 
 /**
  * ktime_get_ts - get the monotonic clock in timespec format
- *
  * @ts:                pointer to timespec variable
  *
  * The function calculates the monotonic clock from the realtime
@@ -111,6 +122,26 @@ void ktime_get_ts(struct timespec *ts)
 EXPORT_SYMBOL_GPL(ktime_get_ts);
 
 /*
+ * Get the coarse grained time at the softirq based on xtime and
+ * wall_to_monotonic.
+ */
+static void hrtimer_get_softirq_time(struct hrtimer_base *base)
+{
+       ktime_t xtim, tomono;
+       unsigned long seq;
+
+       do {
+               seq = read_seqbegin(&xtime_lock);
+               xtim = timespec_to_ktime(xtime);
+               tomono = timespec_to_ktime(wall_to_monotonic);
+
+       } while (read_seqretry(&xtime_lock, seq));
+
+       base[CLOCK_REALTIME].softirq_time = xtim;
+       base[CLOCK_MONOTONIC].softirq_time = ktime_add(xtim, tomono);
+}
+
+/*
  * Functions and macros which are different for UP/SMP systems are kept in a
  * single place
  */
@@ -156,7 +187,7 @@ switch_hrtimer_base(struct hrtimer *timer, struct hrtimer_base *base)
 {
        struct hrtimer_base *new_base;
 
-       new_base = &__get_cpu_var(hrtimer_bases[base->index]);
+       new_base = &__get_cpu_var(hrtimer_bases)[base->index];
 
        if (base != new_base) {
                /*
@@ -206,7 +237,6 @@ lock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
 # ifndef CONFIG_KTIME_SCALAR
 /**
  * ktime_add_ns - Add a scalar nanoseconds value to a ktime_t variable
- *
  * @kt:                addend
  * @nsec:      the scalar nsec value to add
  *
@@ -234,7 +264,7 @@ ktime_t ktime_add_ns(const ktime_t kt, u64 nsec)
 /*
  * Divide a ktime value by a nanosecond value
  */
-static unsigned long ktime_divns(const ktime_t kt, nsec_t div)
+static unsigned long ktime_divns(const ktime_t kt, s64 div)
 {
        u64 dclc, inc, dns;
        int sft = 0;
@@ -267,28 +297,29 @@ void unlock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
 
 /**
  * hrtimer_forward - forward the timer expiry
- *
  * @timer:     hrtimer to forward
+ * @now:       forward past this time
  * @interval:  the interval to forward
  *
  * Forward the timer expiry so it will expire in the future.
- * The number of overruns is added to the overrun field.
+ * Returns the number of overruns.
  */
 unsigned long
-hrtimer_forward(struct hrtimer *timer, const ktime_t interval)
+hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval)
 {
        unsigned long orun = 1;
-       ktime_t delta, now;
-
-       now = timer->base->get_time();
+       ktime_t delta;
 
        delta = ktime_sub(now, timer->expires);
 
        if (delta.tv64 < 0)
                return 0;
 
+       if (interval.tv64 < timer->base->resolution.tv64)
+               interval.tv64 = timer->base->resolution.tv64;
+
        if (unlikely(delta.tv64 >= interval.tv64)) {
-               nsec_t incr = ktime_to_ns(interval);
+               s64 incr = ktime_to_ns(interval);
 
                orun = ktime_divns(delta, incr);
                timer->expires = ktime_add_ns(timer->expires, incr * orun);
@@ -340,8 +371,6 @@ static void enqueue_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
        rb_link_node(&timer->node, parent, link);
        rb_insert_color(&timer->node, &base->active);
 
-       timer->state = HRTIMER_PENDING;
-
        if (!base->first || timer->expires.tv64 <
            rb_entry(base->first, struct hrtimer, node)->expires.tv64)
                base->first = &timer->node;
@@ -361,6 +390,7 @@ static void __remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
        if (base->first == &timer->node)
                base->first = rb_next(&timer->node);
        rb_erase(&timer->node, &base->active);
+       rb_set_parent(&timer->node, &timer->node);
 }
 
 /*
@@ -371,7 +401,6 @@ remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
 {
        if (hrtimer_active(timer)) {
                __remove_hrtimer(timer, base);
-               timer->state = HRTIMER_INACTIVE;
                return 1;
        }
        return 0;
@@ -379,7 +408,6 @@ remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
 
 /**
  * hrtimer_start - (re)start an relative timer on the current CPU
- *
  * @timer:     the timer to be added
  * @tim:       expiry time
  * @mode:      expiry mode: absolute (HRTIMER_ABS) or relative (HRTIMER_REL)
@@ -403,8 +431,19 @@ hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode)
        /* Switch the timer base, if necessary: */
        new_base = switch_hrtimer_base(timer, base);
 
-       if (mode == HRTIMER_REL)
+       if (mode == HRTIMER_REL) {
                tim = ktime_add(tim, new_base->get_time());
+               /*
+                * CONFIG_TIME_LOW_RES is a temporary way for architectures
+                * to signal that they simply return xtime in
+                * do_gettimeoffset(). In this case we want to round up by
+                * resolution when starting a relative timer, to avoid short
+                * timeouts. This will go away with the GTOD framework.
+                */
+#ifdef CONFIG_TIME_LOW_RES
+               tim = ktime_add(tim, base->resolution);
+#endif
+       }
        timer->expires = tim;
 
        enqueue_hrtimer(timer, new_base);
@@ -413,17 +452,17 @@ hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode)
 
        return ret;
 }
+EXPORT_SYMBOL_GPL(hrtimer_start);
 
 /**
  * hrtimer_try_to_cancel - try to deactivate a timer
- *
  * @timer:     hrtimer to stop
  *
  * Returns:
  *  0 when the timer was not active
  *  1 when the timer was active
  * -1 when the timer is currently excuting the callback function and
- *    can not be stopped
+ *    cannot be stopped
  */
 int hrtimer_try_to_cancel(struct hrtimer *timer)
 {
@@ -441,10 +480,10 @@ int hrtimer_try_to_cancel(struct hrtimer *timer)
        return ret;
 
 }
+EXPORT_SYMBOL_GPL(hrtimer_try_to_cancel);
 
 /**
  * hrtimer_cancel - cancel a timer and wait for the handler to finish.
- *
  * @timer:     the timer to be cancelled
  *
  * Returns:
@@ -458,12 +497,13 @@ int hrtimer_cancel(struct hrtimer *timer)
 
                if (ret >= 0)
                        return ret;
+               cpu_relax();
        }
 }
+EXPORT_SYMBOL_GPL(hrtimer_cancel);
 
 /**
  * hrtimer_get_remaining - get remaining time for the timer
- *
  * @timer:     the timer to read
  */
 ktime_t hrtimer_get_remaining(const struct hrtimer *timer)
@@ -478,36 +518,68 @@ ktime_t hrtimer_get_remaining(const struct hrtimer *timer)
 
        return rem;
 }
+EXPORT_SYMBOL_GPL(hrtimer_get_remaining);
 
+#ifdef CONFIG_NO_IDLE_HZ
 /**
- * hrtimer_rebase - rebase an initialized hrtimer to a different base
+ * hrtimer_get_next_event - get the time until next expiry event
  *
- * @timer:     the timer to be rebased
- * @clock_id:  the clock to be used
+ * Returns the delta to the next expiry event or KTIME_MAX if no timer
+ * is pending.
  */
-void hrtimer_rebase(struct hrtimer *timer, const clockid_t clock_id)
+ktime_t hrtimer_get_next_event(void)
 {
-       struct hrtimer_base *bases;
+       struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
+       ktime_t delta, mindelta = { .tv64 = KTIME_MAX };
+       unsigned long flags;
+       int i;
 
-       bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
-       timer->base = &bases[clock_id];
+       for (i = 0; i < MAX_HRTIMER_BASES; i++, base++) {
+               struct hrtimer *timer;
+
+               spin_lock_irqsave(&base->lock, flags);
+               if (!base->first) {
+                       spin_unlock_irqrestore(&base->lock, flags);
+                       continue;
+               }
+               timer = rb_entry(base->first, struct hrtimer, node);
+               delta.tv64 = timer->expires.tv64;
+               spin_unlock_irqrestore(&base->lock, flags);
+               delta = ktime_sub(delta, base->get_time());
+               if (delta.tv64 < mindelta.tv64)
+                       mindelta.tv64 = delta.tv64;
+       }
+       if (mindelta.tv64 < 0)
+               mindelta.tv64 = 0;
+       return mindelta;
 }
+#endif
 
 /**
  * hrtimer_init - initialize a timer to the given clock
- *
  * @timer:     the timer to be initialized
  * @clock_id:  the clock to be used
+ * @mode:      timer mode abs/rel
  */
-void hrtimer_init(struct hrtimer *timer, const clockid_t clock_id)
+void hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
+                 enum hrtimer_mode mode)
 {
+       struct hrtimer_base *bases;
+
        memset(timer, 0, sizeof(struct hrtimer));
-       hrtimer_rebase(timer, clock_id);
+
+       bases = __raw_get_cpu_var(hrtimer_bases);
+
+       if (clock_id == CLOCK_REALTIME && mode != HRTIMER_ABS)
+               clock_id = CLOCK_MONOTONIC;
+
+       timer->base = &bases[clock_id];
+       rb_set_parent(&timer->node, &timer->node);
 }
+EXPORT_SYMBOL_GPL(hrtimer_init);
 
 /**
  * hrtimer_get_res - get the timer resolution for a clock
- *
  * @which_clock: which clock to query
  * @tp:                 pointer to timespec variable to store the resolution
  *
@@ -518,55 +590,50 @@ int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp)
 {
        struct hrtimer_base *bases;
 
-       tp->tv_sec = 0;
-       bases = per_cpu(hrtimer_bases, raw_smp_processor_id());
-       tp->tv_nsec = bases[which_clock].resolution;
+       bases = __raw_get_cpu_var(hrtimer_bases);
+       *tp = ktime_to_timespec(bases[which_clock].resolution);
 
        return 0;
 }
+EXPORT_SYMBOL_GPL(hrtimer_get_res);
 
 /*
  * Expire the per base hrtimer-queue:
  */
 static inline void run_hrtimer_queue(struct hrtimer_base *base)
 {
-       ktime_t now = base->get_time();
        struct rb_node *node;
 
+       if (!base->first)
+               return;
+
+       if (base->get_softirq_time)
+               base->softirq_time = base->get_softirq_time();
+
        spin_lock_irq(&base->lock);
 
        while ((node = base->first)) {
                struct hrtimer *timer;
-               int (*fn)(void *);
+               int (*fn)(struct hrtimer *);
                int restart;
-               void *data;
 
                timer = rb_entry(node, struct hrtimer, node);
-               if (now.tv64 <= timer->expires.tv64)
+               if (base->softirq_time.tv64 <= timer->expires.tv64)
                        break;
 
                fn = timer->function;
-               data = timer->data;
                set_curr_timer(base, timer);
                __remove_hrtimer(timer, base);
                spin_unlock_irq(&base->lock);
 
-               /*
-                * fn == NULL is special case for the simplest timer
-                * variant - wake up process and do not restart:
-                */
-               if (!fn) {
-                       wake_up_process(data);
-                       restart = HRTIMER_NORESTART;
-               } else
-                       restart = fn(data);
+               restart = fn(timer);
 
                spin_lock_irq(&base->lock);
 
-               if (restart == HRTIMER_RESTART)
+               if (restart != HRTIMER_NORESTART) {
+                       BUG_ON(hrtimer_active(timer));
                        enqueue_hrtimer(timer, base);
-               else
-                       timer->state = HRTIMER_EXPIRED;
+               }
        }
        set_curr_timer(base, NULL);
        spin_unlock_irq(&base->lock);
@@ -580,6 +647,8 @@ void hrtimer_run_queues(void)
        struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
        int i;
 
+       hrtimer_get_softirq_time(base);
+
        for (i = 0; i < MAX_HRTIMER_BASES; i++)
                run_hrtimer_queue(&base[i]);
 }
@@ -587,126 +656,106 @@ void hrtimer_run_queues(void)
 /*
  * Sleep related functions:
  */
-
-/**
- * schedule_hrtimer - sleep until timeout
- *
- * @timer:     hrtimer variable initialized with the correct clock base
- * @mode:      timeout value is abs/rel
- *
- * Make the current task sleep until @timeout is
- * elapsed.
- *
- * You can set the task state as follows -
- *
- * %TASK_UNINTERRUPTIBLE - at least @timeout is guaranteed to
- * pass before the routine returns. The routine will return 0
- *
- * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
- * delivered to the current task. In this case the remaining time
- * will be returned
- *
- * The current task state is guaranteed to be TASK_RUNNING when this
- * routine returns.
- */
-static ktime_t __sched
-schedule_hrtimer(struct hrtimer *timer, const enum hrtimer_mode mode)
+static int hrtimer_wakeup(struct hrtimer *timer)
 {
-       /* fn stays NULL, meaning single-shot wakeup: */
-       timer->data = current;
+       struct hrtimer_sleeper *t =
+               container_of(timer, struct hrtimer_sleeper, timer);
+       struct task_struct *task = t->task;
 
-       hrtimer_start(timer, timer->expires, mode);
+       t->task = NULL;
+       if (task)
+               wake_up_process(task);
 
-       schedule();
-       hrtimer_cancel(timer);
+       return HRTIMER_NORESTART;
+}
 
-       /* Return the remaining time: */
-       if (timer->state != HRTIMER_EXPIRED)
-               return ktime_sub(timer->expires, timer->base->get_time());
-       else
-               return (ktime_t) {.tv64 = 0 };
+void hrtimer_init_sleeper(struct hrtimer_sleeper *sl, struct task_struct *task)
+{
+       sl->timer.function = hrtimer_wakeup;
+       sl->task = task;
 }
 
-static inline ktime_t __sched
-schedule_hrtimer_interruptible(struct hrtimer *timer,
-                              const enum hrtimer_mode mode)
+static int __sched do_nanosleep(struct hrtimer_sleeper *t, enum hrtimer_mode mode)
 {
-       set_current_state(TASK_INTERRUPTIBLE);
+       hrtimer_init_sleeper(t, current);
 
-       return schedule_hrtimer(timer, mode);
+       do {
+               set_current_state(TASK_INTERRUPTIBLE);
+               hrtimer_start(&t->timer, t->timer.expires, mode);
+
+               schedule();
+
+               hrtimer_cancel(&t->timer);
+               mode = HRTIMER_ABS;
+
+       } while (t->task && !signal_pending(current));
+
+       return t->task == NULL;
 }
 
-static long __sched
-nanosleep_restart(struct restart_block *restart, clockid_t clockid)
+long __sched hrtimer_nanosleep_restart(struct restart_block *restart)
 {
-       struct timespec __user *rmtp, tu;
-       void *rfn_save = restart->fn;
-       struct hrtimer timer;
-       ktime_t rem;
+       struct hrtimer_sleeper t;
+       struct timespec __user *rmtp;
+       struct timespec tu;
+       ktime_t time;
 
        restart->fn = do_no_restart_syscall;
 
-       hrtimer_init(&timer, clockid);
+       hrtimer_init(&t.timer, restart->arg0, HRTIMER_ABS);
+       t.timer.expires.tv64 = ((u64)restart->arg3 << 32) | (u64) restart->arg2;
 
-       timer.expires.tv64 = ((u64)restart->arg1 << 32) | (u64) restart->arg0;
-
-       rem = schedule_hrtimer_interruptible(&timer, HRTIMER_ABS);
-
-       if (rem.tv64 <= 0)
+       if (do_nanosleep(&t, HRTIMER_ABS))
                return 0;
 
-       rmtp = (struct timespec __user *) restart->arg2;
-       tu = ktime_to_timespec(rem);
-       if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
-               return -EFAULT;
+       rmtp = (struct timespec __user *) restart->arg1;
+       if (rmtp) {
+               time = ktime_sub(t.timer.expires, t.timer.base->get_time());
+               if (time.tv64 <= 0)
+                       return 0;
+               tu = ktime_to_timespec(time);
+               if (copy_to_user(rmtp, &tu, sizeof(tu)))
+                       return -EFAULT;
+       }
 
-       restart->fn = rfn_save;
+       restart->fn = hrtimer_nanosleep_restart;
 
        /* The other values in restart are already filled in */
        return -ERESTART_RESTARTBLOCK;
 }
 
-static long __sched nanosleep_restart_mono(struct restart_block *restart)
-{
-       return nanosleep_restart(restart, CLOCK_MONOTONIC);
-}
-
-static long __sched nanosleep_restart_real(struct restart_block *restart)
-{
-       return nanosleep_restart(restart, CLOCK_REALTIME);
-}
-
 long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
                       const enum hrtimer_mode mode, const clockid_t clockid)
 {
        struct restart_block *restart;
-       struct hrtimer timer;
+       struct hrtimer_sleeper t;
        struct timespec tu;
        ktime_t rem;
 
-       hrtimer_init(&timer, clockid);
-
-       timer.expires = timespec_to_ktime(*rqtp);
-
-       rem = schedule_hrtimer_interruptible(&timer, mode);
-       if (rem.tv64 <= 0)
+       hrtimer_init(&t.timer, clockid, mode);
+       t.timer.expires = timespec_to_ktime(*rqtp);
+       if (do_nanosleep(&t, mode))
                return 0;
 
-       /* Absolute timers do not update the rmtp value: */
+       /* Absolute timers do not update the rmtp value and restart: */
        if (mode == HRTIMER_ABS)
                return -ERESTARTNOHAND;
 
-       tu = ktime_to_timespec(rem);
-
-       if (rmtp && copy_to_user(rmtp, &tu, sizeof(tu)))
-               return -EFAULT;
+       if (rmtp) {
+               rem = ktime_sub(t.timer.expires, t.timer.base->get_time());
+               if (rem.tv64 <= 0)
+                       return 0;
+               tu = ktime_to_timespec(rem);
+               if (copy_to_user(rmtp, &tu, sizeof(tu)))
+                       return -EFAULT;
+       }
 
        restart = &current_thread_info()->restart_block;
-       restart->fn = (clockid == CLOCK_MONOTONIC) ?
-               nanosleep_restart_mono : nanosleep_restart_real;
-       restart->arg0 = timer.expires.tv64 & 0xFFFFFFFF;
-       restart->arg1 = timer.expires.tv64 >> 32;
-       restart->arg2 = (unsigned long) rmtp;
+       restart->fn = hrtimer_nanosleep_restart;
+       restart->arg0 = (unsigned long) t.timer.base->index;
+       restart->arg1 = (unsigned long) rmtp;
+       restart->arg2 = t.timer.expires.tv64 & 0xFFFFFFFF;
+       restart->arg3 = t.timer.expires.tv64 >> 32;
 
        return -ERESTART_RESTARTBLOCK;
 }
@@ -733,9 +782,9 @@ static void __devinit init_hrtimers_cpu(int cpu)
        struct hrtimer_base *base = per_cpu(hrtimer_bases, cpu);
        int i;
 
-       for (i = 0; i < MAX_HRTIMER_BASES; i++) {
+       for (i = 0; i < MAX_HRTIMER_BASES; i++, base++) {
                spin_lock_init(&base->lock);
-               base++;
+               lockdep_set_class(&base->lock, &base->lock_key);
        }
 }
 
@@ -786,7 +835,7 @@ static void migrate_hrtimers(int cpu)
 }
 #endif /* CONFIG_HOTPLUG_CPU */
 
-static int __devinit hrtimer_cpu_notify(struct notifier_block *self,
+static int __cpuinit hrtimer_cpu_notify(struct notifier_block *self,
                                        unsigned long action, void *hcpu)
 {
        long cpu = (long)hcpu;
@@ -810,7 +859,7 @@ static int __devinit hrtimer_cpu_notify(struct notifier_block *self,
        return NOTIFY_OK;
 }
 
-static struct notifier_block __devinitdata hrtimers_nb = {
+static struct notifier_block __cpuinitdata hrtimers_nb = {
        .notifier_call = hrtimer_cpu_notify,
 };