Merge branch 'timers-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip

* 'timers-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip:
  MAINTAINERS: Update timer related entries
  timers: Use this_cpu_read
  timerqueue: Make timerqueue_getnext() static inline
  hrtimer: fix timerqueue conversion flub
  hrtimers: Convert hrtimers to use timerlist infrastructure
  timers: Fixup allmodconfig build issue
  timers: Rename timerlist infrastructure to timerqueue
  timers: Introduce timerlist infrastructure.
  hrtimer: Remove stale comment on curr_timer
  timer: Warn when del_timer_sync() is called in hardirq context
  timer: Del_timer_sync() can be used in softirq context
  timer: Make try_to_del_timer_sync() the same on SMP and UP
  posix-timers: Annotate lock_timer()
  timer: Permit statically-declared work with deferrable timers
  time: Use ARRAY_SIZE macro in timecompare.c
  timer: Initialize the field slack of timer_list
  timer_list: Remove alignment padding on 64 bit when CONFIG_TIMER_STATS
  time: Compensate for rounding on odd-frequency clocksources

Fix up trivial conflict in MAINTAINERS

4 files changed, 102 insertions, 21 deletions

diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index fd0c1b857d3d..330586ffffbb 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -22,7 +22,7 @@
 #include <linux/wait.h>
 #include <linux/percpu.h>
 #include <linux/timer.h>
-
+#include <linux/timerqueue.h>
 
 struct hrtimer_clock_base;
 struct hrtimer_cpu_base;
@@ -79,8 +79,8 @@ enum hrtimer_restart {
 
 /**
  * struct hrtimer - the basic hrtimer structure
- * @node:       red black tree node for time ordered insertion
- * @_expires:   the absolute expiry time in the hrtimers internal
+ * @node:       timerqueue node, which also manages node.expires,
+ *              the absolute expiry time in the hrtimers internal
  *              representation. The time is related to the clock on
  *              which the timer is based. Is setup by adding
  *              slack to the _softexpires value. For non range timers
@@ -101,8 +101,7 @@ enum hrtimer_restart {
  * The hrtimer structure must be initialized by hrtimer_init()
  */
 struct hrtimer {
-        struct rb_node                  node;
-        ktime_t                         _expires;
+        struct timerqueue_node          node;
         ktime_t                         _softexpires;
         enum hrtimer_restart            (*function)(struct hrtimer *);
         struct hrtimer_clock_base       *base;
@@ -141,8 +140,7 @@ struct hrtimer_sleeper {
 struct hrtimer_clock_base {
         struct hrtimer_cpu_base *cpu_base;
         clockid_t               index;
-        struct rb_root          active;
-        struct rb_node          *first;
+        struct timerqueue_head  active;
         ktime_t                 resolution;
         ktime_t                 (*get_time)(void);
         ktime_t                 softirq_time;
@@ -158,7 +156,6 @@ struct hrtimer_clock_base {
  * @lock:               lock protecting the base and associated clock bases
  *                      and timers
  * @clock_base:         array of clock bases for this cpu
- * @curr_timer:         the timer which is executing a callback right now
  * @expires_next:       absolute time of the next event which was scheduled
  *                      via clock_set_next_event()
  * @hres_active:        State of high resolution mode
@@ -184,43 +181,43 @@ struct hrtimer_cpu_base {
 
 static inline void hrtimer_set_expires(struct hrtimer *timer, ktime_t time)
 {
-        timer->_expires = time;
+        timer->node.expires = time;
         timer->_softexpires = time;
 }
 
 static inline void hrtimer_set_expires_range(struct hrtimer *timer, ktime_t time, ktime_t delta)
 {
         timer->_softexpires = time;
-        timer->_expires = ktime_add_safe(time, delta);
+        timer->node.expires = ktime_add_safe(time, delta);
 }
 
 static inline void hrtimer_set_expires_range_ns(struct hrtimer *timer, ktime_t time, unsigned long delta)
 {
         timer->_softexpires = time;
-        timer->_expires = ktime_add_safe(time, ns_to_ktime(delta));
+        timer->node.expires = ktime_add_safe(time, ns_to_ktime(delta));
 }
 
 static inline void hrtimer_set_expires_tv64(struct hrtimer *timer, s64 tv64)
 {
-        timer->_expires.tv64 = tv64;
+        timer->node.expires.tv64 = tv64;
         timer->_softexpires.tv64 = tv64;
 }
 
 static inline void hrtimer_add_expires(struct hrtimer *timer, ktime_t time)
 {
-        timer->_expires = ktime_add_safe(timer->_expires, time);
+        timer->node.expires = ktime_add_safe(timer->node.expires, time);
         timer->_softexpires = ktime_add_safe(timer->_softexpires, time);
 }
 
 static inline void hrtimer_add_expires_ns(struct hrtimer *timer, u64 ns)
 {
-        timer->_expires = ktime_add_ns(timer->_expires, ns);
+        timer->node.expires = ktime_add_ns(timer->node.expires, ns);
         timer->_softexpires = ktime_add_ns(timer->_softexpires, ns);
 }
 
 static inline ktime_t hrtimer_get_expires(const struct hrtimer *timer)
 {
-        return timer->_expires;
+        return timer->node.expires;
 }
 
 static inline ktime_t hrtimer_get_softexpires(const struct hrtimer *timer)
@@ -230,7 +227,7 @@ static inline ktime_t hrtimer_get_softexpires(const struct hrtimer *timer)
 
 static inline s64 hrtimer_get_expires_tv64(const struct hrtimer *timer)
 {
-        return timer->_expires.tv64;
+        return timer->node.expires.tv64;
 }
 static inline s64 hrtimer_get_softexpires_tv64(const struct hrtimer *timer)
 {
@@ -239,12 +236,12 @@ static inline s64 hrtimer_get_softexpires_tv64(const struct hrtimer *timer)
 
 static inline s64 hrtimer_get_expires_ns(const struct hrtimer *timer)
 {
-        return ktime_to_ns(timer->_expires);
+        return ktime_to_ns(timer->node.expires);
 }
 
 static inline ktime_t hrtimer_expires_remaining(const struct hrtimer *timer)
 {
-    return ktime_sub(timer->_expires, timer->base->get_time());
+        return ktime_sub(timer->node.expires, timer->base->get_time());
 }
 
 #ifdef CONFIG_HIGH_RES_TIMERS
diff --git a/include/linux/timer.h b/include/linux/timer.h
index 38cf093ef62c..6abd9138beda 100644
--- a/include/linux/timer.h
+++ b/include/linux/timer.h
@@ -24,9 +24,9 @@ struct timer_list {
         int slack;
 
 #ifdef CONFIG_TIMER_STATS
+        int start_pid;
         void *start_site;
         char start_comm[16];
-        int start_pid;
 #endif
 #ifdef CONFIG_LOCKDEP
         struct lockdep_map lockdep_map;
@@ -48,12 +48,38 @@ extern struct tvec_base boot_tvec_bases;
 #define __TIMER_LOCKDEP_MAP_INITIALIZER(_kn)
 #endif
 
+/*
+ * Note that all tvec_bases are 2 byte aligned and lower bit of
+ * base in timer_list is guaranteed to be zero. Use the LSB to
+ * indicate whether the timer is deferrable.
+ *
+ * A deferrable timer will work normally when the system is busy, but
+ * will not cause a CPU to come out of idle just to service it; instead,
+ * the timer will be serviced when the CPU eventually wakes up with a
+ * subsequent non-deferrable timer.
+ */
+#define TBASE_DEFERRABLE_FLAG           (0x1)
+
 #define TIMER_INITIALIZER(_function, _expires, _data) {         \
                 .entry = { .prev = TIMER_ENTRY_STATIC },        \
                 .function = (_function),                        \
                 .expires = (_expires),                          \
                 .data = (_data),                                \
                 .base = &boot_tvec_bases,                       \
+                .slack = -1,                                    \
+                __TIMER_LOCKDEP_MAP_INITIALIZER(                \
+                        __FILE__ ":" __stringify(__LINE__))     \
+        }
+
+#define TBASE_MAKE_DEFERRED(ptr) ((struct tvec_base *)          \
+                  ((unsigned char *)(ptr) + TBASE_DEFERRABLE_FLAG))
+
+#define TIMER_DEFERRED_INITIALIZER(_function, _expires, _data) {\
+                .entry = { .prev = TIMER_ENTRY_STATIC },        \
+                .function = (_function),                        \
+                .expires = (_expires),                          \
+                .data = (_data),                                \
+                .base = TBASE_MAKE_DEFERRED(&boot_tvec_bases),  \
                 __TIMER_LOCKDEP_MAP_INITIALIZER(                \
                         __FILE__ ":" __stringify(__LINE__))     \
         }
@@ -248,11 +274,11 @@ static inline void timer_stats_timer_clear_start_info(struct timer_list *timer)
 
 extern void add_timer(struct timer_list *timer);
 
+extern int try_to_del_timer_sync(struct timer_list *timer);
+
 #ifdef CONFIG_SMP
-  extern int try_to_del_timer_sync(struct timer_list *timer);
   extern int del_timer_sync(struct timer_list *timer);
 #else
-# define try_to_del_timer_sync(t)       del_timer(t)
 # define del_timer_sync(t)              del_timer(t)
 #endif
 
diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h
new file mode 100644
index 000000000000..d24aabaca474
--- /dev/null
+++ b/include/linux/timerqueue.h
@@ -0,0 +1,50 @@
+#ifndef _LINUX_TIMERQUEUE_H
+#define _LINUX_TIMERQUEUE_H
+
+#include <linux/rbtree.h>
+#include <linux/ktime.h>
+
+
+struct timerqueue_node {
+        struct rb_node node;
+        ktime_t expires;
+};
+
+struct timerqueue_head {
+        struct rb_root head;
+        struct timerqueue_node *next;
+};
+
+
+extern void timerqueue_add(struct timerqueue_head *head,
+                                struct timerqueue_node *node);
+extern void timerqueue_del(struct timerqueue_head *head,
+                                struct timerqueue_node *node);
+extern struct timerqueue_node *timerqueue_iterate_next(
+                                                struct timerqueue_node *node);
+
+/**
+ * timerqueue_getnext - Returns the timer with the earlies expiration time
+ *
+ * @head: head of timerqueue
+ *
+ * Returns a pointer to the timer node that has the
+ * earliest expiration time.
+ */
+static inline
+struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head)
+{
+        return head->next;
+}
+
+static inline void timerqueue_init(struct timerqueue_node *node)
+{
+        RB_CLEAR_NODE(&node->node);
+}
+
+static inline void timerqueue_init_head(struct timerqueue_head *head)
+{
+        head->head = RB_ROOT;
+        head->next = NULL;
+}
+#endif /* _LINUX_TIMERQUEUE_H */
diff --git a/include/linux/workqueue.h b/include/linux/workqueue.h
index 0c0771f06bfa..bd257fee6031 100644
--- a/include/linux/workqueue.h
+++ b/include/linux/workqueue.h
@@ -127,12 +127,20 @@ struct execute_work {
         .timer = TIMER_INITIALIZER(NULL, 0, 0),                 \
         }
 
+#define __DEFERRED_WORK_INITIALIZER(n, f) {                     \
+        .work = __WORK_INITIALIZER((n).work, (f)),              \
+        .timer = TIMER_DEFERRED_INITIALIZER(NULL, 0, 0),        \
+        }
+
 #define DECLARE_WORK(n, f)                                      \
         struct work_struct n = __WORK_INITIALIZER(n, f)
 
 #define DECLARE_DELAYED_WORK(n, f)                              \
         struct delayed_work n = __DELAYED_WORK_INITIALIZER(n, f)
 
+#define DECLARE_DEFERRED_WORK(n, f)                             \
+        struct delayed_work n = __DEFERRED_WORK_INITIALIZER(n, f)
+
 /*
  * initialize a work item's function pointer
  */