From d0959024d8fb6555ba8bfdc6624cc7b7c2e675fd Mon Sep 17 00:00:00 2001 From: Richard Kennedy Date: Wed, 20 Oct 2010 15:57:30 -0700 Subject: timer_list: Remove alignment padding on 64 bit when CONFIG_TIMER_STATS Reorder struct timer_list to remove 8 bytes of alignment padding on 64 bit builds when CONFIG_TIMER_STATS is selected. timer_list is widely used across the kernel so many structures will benefit and shrink in size. For example, with my config on x86_64 per_cpu_dm_data shrinks from 136 to 128 bytes and ahci_port_priv shrinks from 1032 to 968 bytes. Signed-off-by: Richard Kennedy Cc: Ingo Molnar Signed-off-by: Andrew Morton Signed-off-by: Thomas Gleixner --- include/linux/timer.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/timer.h b/include/linux/timer.h index 38cf093ef62c..f3dccdb44f95 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; -- cgit v1.2.3 From aaabe31c25a439b92cc281b14ca18b85bae7e7a6 Mon Sep 17 00:00:00 2001 From: Changli Gao Date: Wed, 20 Oct 2010 15:57:30 -0700 Subject: timer: Initialize the field slack of timer_list TIMER_INITIALIZER() should initialize the field slack of timer_list as __init_timer() does. Signed-off-by: Changli Gao Cc: Arjan van de Ven Signed-off-by: Andrew Morton Signed-off-by: Thomas Gleixner --- include/linux/timer.h | 1 + 1 file changed, 1 insertion(+) (limited to 'include/linux') diff --git a/include/linux/timer.h b/include/linux/timer.h index f3dccdb44f95..1794674c1a52 100644 --- a/include/linux/timer.h +++ b/include/linux/timer.h @@ -54,6 +54,7 @@ extern struct tvec_base boot_tvec_bases; .expires = (_expires), \ .data = (_data), \ .base = &boot_tvec_bases, \ + .slack = -1, \ __TIMER_LOCKDEP_MAP_INITIALIZER( \ __FILE__ ":" __stringify(__LINE__)) \ } -- cgit v1.2.3 From dd6414b50fa2b1cd247a8aa8f8bd42414b7453e1 Mon Sep 17 00:00:00 2001 From: Phil Carmody Date: Wed, 20 Oct 2010 15:57:33 -0700 Subject: timer: Permit statically-declared work with deferrable timers Currently, you have to just define a delayed_work uninitialised, and then initialise it before first use. That's a tad clumsy. At risk of playing mind-games with the compiler, fooling it into doing pointer arithmetic with compile-time-constants, this lets clients properly initialise delayed work with deferrable timers statically. This patch was inspired by the issues which lead Artem Bityutskiy to commit 8eab945c5616fc984 ("sunrpc: make the cache cleaner workqueue deferrable"). Signed-off-by: Phil Carmody Acked-by: Artem Bityutskiy Cc: Arjan van de Ven Signed-off-by: Andrew Morton Signed-off-by: Thomas Gleixner --- include/linux/timer.h | 25 +++++++++++++++++++++++++ include/linux/workqueue.h | 8 ++++++++ kernel/timer.c | 15 +-------------- 3 files changed, 34 insertions(+), 14 deletions(-) (limited to 'include/linux') diff --git a/include/linux/timer.h b/include/linux/timer.h index 1794674c1a52..cbfb7a355d30 100644 --- a/include/linux/timer.h +++ b/include/linux/timer.h @@ -48,6 +48,18 @@ 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), \ @@ -59,6 +71,19 @@ extern struct tvec_base boot_tvec_bases; __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__)) \ + } + #define DEFINE_TIMER(_name, _function, _expires, _data) \ struct timer_list _name = \ TIMER_INITIALIZER(_function, _expires, _data) diff --git a/include/linux/workqueue.h b/include/linux/workqueue.h index f11100f96482..88238c15ec3e 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 */ diff --git a/kernel/timer.c b/kernel/timer.c index 97bf05baade7..72853b256ff2 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -88,18 +88,6 @@ struct tvec_base boot_tvec_bases; EXPORT_SYMBOL(boot_tvec_bases); static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases; -/* - * 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) - /* Functions below help us manage 'deferrable' flag */ static inline unsigned int tbase_get_deferrable(struct tvec_base *base) { @@ -113,8 +101,7 @@ static inline struct tvec_base *tbase_get_base(struct tvec_base *base) static inline void timer_set_deferrable(struct timer_list *timer) { - timer->base = ((struct tvec_base *)((unsigned long)(timer->base) | - TBASE_DEFERRABLE_FLAG)); + timer->base = TBASE_MAKE_DEFERRED(timer->base); } static inline void -- cgit v1.2.3 From 6f1bc451e6a79470b122a37ee1fc6bbca450f444 Mon Sep 17 00:00:00 2001 From: Yong Zhang Date: Wed, 20 Oct 2010 15:57:31 -0700 Subject: timer: Make try_to_del_timer_sync() the same on SMP and UP On UP try_to_del_timer_sync() is mapped to del_timer() which does not take the running timer callback into account, so it has different semantics. Remove the SMP dependency of try_to_del_timer_sync() by using base->running_timer in the UP case as well. [ tglx: Removed set_running_timer() inline and tweaked the changelog ] Signed-off-by: Yong Zhang Cc: Ingo Molnar Cc: Peter Zijlstra Acked-by: Oleg Nesterov Signed-off-by: Andrew Morton Signed-off-by: Thomas Gleixner --- include/linux/timer.h | 4 ++-- kernel/timer.c | 17 +++-------------- 2 files changed, 5 insertions(+), 16 deletions(-) (limited to 'include/linux') diff --git a/include/linux/timer.h b/include/linux/timer.h index cbfb7a355d30..6abd9138beda 100644 --- a/include/linux/timer.h +++ b/include/linux/timer.h @@ -274,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/kernel/timer.c b/kernel/timer.c index 72853b256ff2..47b86c1e3226 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -330,15 +330,6 @@ void set_timer_slack(struct timer_list *timer, int slack_hz) } EXPORT_SYMBOL_GPL(set_timer_slack); - -static inline void set_running_timer(struct tvec_base *base, - struct timer_list *timer) -{ -#ifdef CONFIG_SMP - base->running_timer = timer; -#endif -} - static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) { unsigned long expires = timer->expires; @@ -923,15 +914,12 @@ int del_timer(struct timer_list *timer) } EXPORT_SYMBOL(del_timer); -#ifdef CONFIG_SMP /** * try_to_del_timer_sync - Try to deactivate a timer * @timer: timer do del * * This function tries to deactivate a timer. Upon successful (ret >= 0) * exit the timer is not queued and the handler is not running on any CPU. - * - * It must not be called from interrupt contexts. */ int try_to_del_timer_sync(struct timer_list *timer) { @@ -960,6 +948,7 @@ out: } EXPORT_SYMBOL(try_to_del_timer_sync); +#ifdef CONFIG_SMP /** * del_timer_sync - deactivate a timer and wait for the handler to finish. * @timer: the timer to be deactivated @@ -1098,7 +1087,7 @@ static inline void __run_timers(struct tvec_base *base) timer_stats_account_timer(timer); - set_running_timer(base, timer); + base->running_timer = timer; detach_timer(timer, 1); spin_unlock_irq(&base->lock); @@ -1106,7 +1095,7 @@ static inline void __run_timers(struct tvec_base *base) spin_lock_irq(&base->lock); } } - set_running_timer(base, NULL); + base->running_timer = NULL; spin_unlock_irq(&base->lock); } -- cgit v1.2.3 From 5e4f083f78d03e9f8d2e327daccde16976f9bb00 Mon Sep 17 00:00:00 2001 From: Yong Zhang Date: Sun, 24 Oct 2010 11:50:53 +0800 Subject: hrtimer: Remove stale comment on curr_timer curr_timer doesn't resident in struct hrtimer_cpu_base anymore. Signed-off-by: Yong Zhang LKML-Reference: <1287892253-2587-1-git-send-email-yong.zhang0@gmail.com> Signed-off-by: Thomas Gleixner --- include/linux/hrtimer.h | 1 - 1 file changed, 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h index fd0c1b857d3d..dd9954b79342 100644 --- a/include/linux/hrtimer.h +++ b/include/linux/hrtimer.h @@ -158,7 +158,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 -- cgit v1.2.3 From 87de5ac782761a3ebf806e434e8c9cc205a87274 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Mon, 20 Sep 2010 17:42:46 -0700 Subject: timers: Introduce timerlist infrastructure. The timerlist infrastructure is a thin layer over the rbtree code that implements a simple list of timers sorted by an expires value, and a getnext function that provides a pointer to the earliest timer. This infrastructure allows drivers and other kernel infrastructure to easily implement timers without duplicating code. Signed-off-by: John Stultz LKML Reference: <1290136329-18291-2-git-send-email-john.stultz@linaro.org> Reviewed-by: Thomas Gleixner CC: Alessandro Zummo CC: Thomas Gleixner CC: Richard Cochran --- include/linux/timerlist.h | 37 +++++++++++++++ lib/Makefile | 2 +- lib/timerlist.c | 118 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 156 insertions(+), 1 deletion(-) create mode 100644 include/linux/timerlist.h create mode 100644 lib/timerlist.c (limited to 'include/linux') diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h new file mode 100644 index 000000000000..c46b28ae6e4d --- /dev/null +++ b/include/linux/timerlist.h @@ -0,0 +1,37 @@ +#ifndef _LINUX_TIMERLIST_H +#define _LINUX_TIMERLIST_H + +#include +#include + + +struct timerlist_node { + struct rb_node node; + ktime_t expires; +}; + +struct timerlist_head { + struct rb_root head; + struct timerlist_node *next; +}; + + +extern void timerlist_add(struct timerlist_head *head, + struct timerlist_node *node); +extern void timerlist_del(struct timerlist_head *head, + struct timerlist_node *node); +extern struct timerlist_node *timerlist_getnext(struct timerlist_head *head); +extern struct timerlist_node *timerlist_iterate_next( + struct timerlist_node *node); + +static inline void timerlist_init(struct timerlist_node *node) +{ + RB_CLEAR_NODE(&node->node); +} + +static inline void timerlist_init_head(struct timerlist_head *head) +{ + head->head = RB_ROOT; + head->next = NULL; +} +#endif /* _LINUX_TIMERLIST_H */ diff --git a/lib/Makefile b/lib/Makefile index e6a3763b8212..8b475cfb8195 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS)) endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ - rbtree.o radix-tree.o dump_stack.o \ + rbtree.o radix-tree.o dump_stack.o timerlist.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ diff --git a/lib/timerlist.c b/lib/timerlist.c new file mode 100644 index 000000000000..9101b42fd13d --- /dev/null +++ b/lib/timerlist.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-list + * + * Manages a simple list of timers, ordered by expiration time. + * Uses rbtrees for quick list adds and expiration. + * + * NOTE: All of the following functions need to be serialized + * to avoid races. No locking is done by this libary code. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include + +/** + * timerlist_add - Adds timer to timerlist. + * + * @head: head of timerlist + * @node: timer node to be added + * + * Adds the timer node to the timerlist, sorted by the + * node's expires value. + */ +void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerlist_node *ptr; + + /* Make sure we don't add nodes that are already added */ + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); + + while (*p) { + parent = *p; + ptr = rb_entry(parent, struct timerlist_node, node); + if (node->expires.tv64 < ptr->expires.tv64) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + rb_link_node(&node->node, parent, p); + rb_insert_color(&node->node, &head->head); + + if (!head->next || node->expires.tv64 < head->next->expires.tv64) + head->next = node; +} + +/** + * timerlist_del - Removes a timer from the timerlist. + * + * @head: head of timerlist + * @node: timer node to be removed + * + * Removes the timer node from the timerlist. + */ +void timerlist_del(struct timerlist_head *head, struct timerlist_node *node) +{ + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); + + /* update next pointer */ + if (head->next == node) { + struct rb_node *rbn = rb_next(&node->node); + + head->next = rbn ? + rb_entry(rbn, struct timerlist_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&node->node); +} + + +/** + * timerlist_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerlist + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +struct timerlist_node *timerlist_getnext(struct timerlist_head *head) +{ + return head->next; +} + + +/** + * timerlist_iterate_next - Returns the timer after the provided timer + * + * @node: Pointer to a timer. + * + * Provides the timer that is after the given node. This is used, when + * necessary, to iterate through the list of timers in a timer list + * without modifying the list. + */ +struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerlist_node, node); +} -- cgit v1.2.3 From 1f5a24794a54588ea3a9efd521be31d826e0b9d7 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Thu, 9 Dec 2010 12:02:18 -0800 Subject: timers: Rename timerlist infrastructure to timerqueue Thomas pointed out a namespace collision between the new timerlist infrastructure I introduced and the existing timer_list.c So to avoid confusion, I've renamed the timerlist infrastructure to timerqueue. Reported-by: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/timerlist.h | 37 -------------- include/linux/timerqueue.h | 37 ++++++++++++++ lib/Makefile | 2 +- lib/timerlist.c | 118 --------------------------------------------- lib/timerqueue.c | 118 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 156 insertions(+), 156 deletions(-) delete mode 100644 include/linux/timerlist.h create mode 100644 include/linux/timerqueue.h delete mode 100644 lib/timerlist.c create mode 100644 lib/timerqueue.c (limited to 'include/linux') diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h deleted file mode 100644 index c46b28ae6e4d..000000000000 --- a/include/linux/timerlist.h +++ /dev/null @@ -1,37 +0,0 @@ -#ifndef _LINUX_TIMERLIST_H -#define _LINUX_TIMERLIST_H - -#include -#include - - -struct timerlist_node { - struct rb_node node; - ktime_t expires; -}; - -struct timerlist_head { - struct rb_root head; - struct timerlist_node *next; -}; - - -extern void timerlist_add(struct timerlist_head *head, - struct timerlist_node *node); -extern void timerlist_del(struct timerlist_head *head, - struct timerlist_node *node); -extern struct timerlist_node *timerlist_getnext(struct timerlist_head *head); -extern struct timerlist_node *timerlist_iterate_next( - struct timerlist_node *node); - -static inline void timerlist_init(struct timerlist_node *node) -{ - RB_CLEAR_NODE(&node->node); -} - -static inline void timerlist_init_head(struct timerlist_head *head) -{ - head->head = RB_ROOT; - head->next = NULL; -} -#endif /* _LINUX_TIMERLIST_H */ diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h new file mode 100644 index 000000000000..406b103894bd --- /dev/null +++ b/include/linux/timerqueue.h @@ -0,0 +1,37 @@ +#ifndef _LINUX_TIMERQUEUE_H +#define _LINUX_TIMERQUEUE_H + +#include +#include + + +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_getnext(struct timerqueue_head *head); +extern struct timerqueue_node *timerqueue_iterate_next( + struct timerqueue_node *node); + +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/lib/Makefile b/lib/Makefile index 8b475cfb8195..9e2db72d128e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS)) endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ - rbtree.o radix-tree.o dump_stack.o timerlist.o\ + rbtree.o radix-tree.o dump_stack.o timerqueue.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ diff --git a/lib/timerlist.c b/lib/timerlist.c deleted file mode 100644 index 9101b42fd13d..000000000000 --- a/lib/timerlist.c +++ /dev/null @@ -1,118 +0,0 @@ -/* - * Generic Timer-list - * - * Manages a simple list of timers, ordered by expiration time. - * Uses rbtrees for quick list adds and expiration. - * - * NOTE: All of the following functions need to be serialized - * to avoid races. No locking is done by this libary code. - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include -#include - -/** - * timerlist_add - Adds timer to timerlist. - * - * @head: head of timerlist - * @node: timer node to be added - * - * Adds the timer node to the timerlist, sorted by the - * node's expires value. - */ -void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) -{ - struct rb_node **p = &head->head.rb_node; - struct rb_node *parent = NULL; - struct timerlist_node *ptr; - - /* Make sure we don't add nodes that are already added */ - WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); - - while (*p) { - parent = *p; - ptr = rb_entry(parent, struct timerlist_node, node); - if (node->expires.tv64 < ptr->expires.tv64) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } - rb_link_node(&node->node, parent, p); - rb_insert_color(&node->node, &head->head); - - if (!head->next || node->expires.tv64 < head->next->expires.tv64) - head->next = node; -} - -/** - * timerlist_del - Removes a timer from the timerlist. - * - * @head: head of timerlist - * @node: timer node to be removed - * - * Removes the timer node from the timerlist. - */ -void timerlist_del(struct timerlist_head *head, struct timerlist_node *node) -{ - WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); - - /* update next pointer */ - if (head->next == node) { - struct rb_node *rbn = rb_next(&node->node); - - head->next = rbn ? - rb_entry(rbn, struct timerlist_node, node) : NULL; - } - rb_erase(&node->node, &head->head); - RB_CLEAR_NODE(&node->node); -} - - -/** - * timerlist_getnext - Returns the timer with the earlies expiration time - * - * @head: head of timerlist - * - * Returns a pointer to the timer node that has the - * earliest expiration time. - */ -struct timerlist_node *timerlist_getnext(struct timerlist_head *head) -{ - return head->next; -} - - -/** - * timerlist_iterate_next - Returns the timer after the provided timer - * - * @node: Pointer to a timer. - * - * Provides the timer that is after the given node. This is used, when - * necessary, to iterate through the list of timers in a timer list - * without modifying the list. - */ -struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node) -{ - struct rb_node *next; - - if (!node) - return NULL; - next = rb_next(&node->node); - if (!next) - return NULL; - return container_of(next, struct timerlist_node, node); -} diff --git a/lib/timerqueue.c b/lib/timerqueue.c new file mode 100644 index 000000000000..f46de84d9467 --- /dev/null +++ b/lib/timerqueue.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-queue + * + * Manages a simple queue of timers, ordered by expiration time. + * Uses rbtrees for quick list adds and expiration. + * + * NOTE: All of the following functions need to be serialized + * to avoid races. No locking is done by this libary code. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include + +/** + * timerqueue_add - Adds timer to timerqueue. + * + * @head: head of timerqueue + * @node: timer node to be added + * + * Adds the timer node to the timerqueue, sorted by the + * node's expires value. + */ +void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerqueue_node *ptr; + + /* Make sure we don't add nodes that are already added */ + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); + + while (*p) { + parent = *p; + ptr = rb_entry(parent, struct timerqueue_node, node); + if (node->expires.tv64 < ptr->expires.tv64) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + rb_link_node(&node->node, parent, p); + rb_insert_color(&node->node, &head->head); + + if (!head->next || node->expires.tv64 < head->next->expires.tv64) + head->next = node; +} + +/** + * timerqueue_del - Removes a timer from the timerqueue. + * + * @head: head of timerqueue + * @node: timer node to be removed + * + * Removes the timer node from the timerqueue. + */ +void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) +{ + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); + + /* update next pointer */ + if (head->next == node) { + struct rb_node *rbn = rb_next(&node->node); + + head->next = rbn ? + rb_entry(rbn, struct timerqueue_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&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. + */ +struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) +{ + return head->next; +} + + +/** + * timerqueue_iterate_next - Returns the timer after the provided timer + * + * @node: Pointer to a timer. + * + * Provides the timer that is after the given node. This is used, when + * necessary, to iterate through the list of timers in a timer list + * without modifying the list. + */ +struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerqueue_node, node); +} -- cgit v1.2.3 From 998adc3dda59f811966b3ccb21eb223680b25ec4 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Mon, 20 Sep 2010 19:19:17 -0700 Subject: hrtimers: Convert hrtimers to use timerlist infrastructure Converts the hrtimer code to use the new timerlist infrastructure Signed-off-by: John Stultz LKML Reference: <1290136329-18291-3-git-send-email-john.stultz@linaro.org> Reviewed-by: Thomas Gleixner CC: Alessandro Zummo CC: Thomas Gleixner CC: Richard Cochran --- include/linux/hrtimer.h | 32 +++++++++--------- kernel/hrtimer.c | 86 +++++++++++++++++------------------------------- kernel/time/timer_list.c | 8 ++--- 3 files changed, 49 insertions(+), 77 deletions(-) (limited to 'include/linux') diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h index dd9954b79342..330586ffffbb 100644 --- a/include/linux/hrtimer.h +++ b/include/linux/hrtimer.h @@ -22,7 +22,7 @@ #include #include #include - +#include 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; @@ -183,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) @@ -229,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) { @@ -238,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/kernel/hrtimer.c b/kernel/hrtimer.c index ce669174f355..93976ad42f5a 100644 --- a/kernel/hrtimer.c +++ b/kernel/hrtimer.c @@ -516,10 +516,13 @@ hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base, int skip_equal) for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) { struct hrtimer *timer; + struct timerqueue_node *next; - if (!base->first) + next = timerqueue_getnext(&base->active); + if (!next) continue; - timer = rb_entry(base->first, struct hrtimer, node); + timer = container_of(next, struct hrtimer, node); + expires = ktime_sub(hrtimer_get_expires(timer), base->offset); /* * clock_was_set() has changed base->offset so the @@ -840,48 +843,17 @@ EXPORT_SYMBOL_GPL(hrtimer_forward); static int enqueue_hrtimer(struct hrtimer *timer, struct hrtimer_clock_base *base) { - struct rb_node **link = &base->active.rb_node; - struct rb_node *parent = NULL; - struct hrtimer *entry; - int leftmost = 1; - debug_activate(timer); - /* - * Find the right place in the rbtree: - */ - while (*link) { - parent = *link; - entry = rb_entry(parent, struct hrtimer, node); - /* - * We dont care about collisions. Nodes with - * the same expiry time stay together. - */ - if (hrtimer_get_expires_tv64(timer) < - hrtimer_get_expires_tv64(entry)) { - link = &(*link)->rb_left; - } else { - link = &(*link)->rb_right; - leftmost = 0; - } - } + timerqueue_add(&base->active, &timer->node); - /* - * Insert the timer to the rbtree and check whether it - * replaces the first pending timer - */ - if (leftmost) - base->first = &timer->node; - - rb_link_node(&timer->node, parent, link); - rb_insert_color(&timer->node, &base->active); /* * HRTIMER_STATE_ENQUEUED is or'ed to the current state to preserve the * state of a possibly running callback. */ timer->state |= HRTIMER_STATE_ENQUEUED; - return leftmost; + return (&timer->node == base->active.next); } /* @@ -901,12 +873,7 @@ static void __remove_hrtimer(struct hrtimer *timer, if (!(timer->state & HRTIMER_STATE_ENQUEUED)) goto out; - /* - * Remove the timer from the rbtree and replace the first - * entry pointer if necessary. - */ - if (base->first == &timer->node) { - base->first = rb_next(&timer->node); + if (&timer->node == timerqueue_getnext(&base->active)) { #ifdef CONFIG_HIGH_RES_TIMERS /* Reprogram the clock event device. if enabled */ if (reprogram && hrtimer_hres_active()) { @@ -919,7 +886,7 @@ static void __remove_hrtimer(struct hrtimer *timer, } #endif } - rb_erase(&timer->node, &base->active); + timerqueue_del(&base->active, &timer->node); out: timer->state = newstate; } @@ -1123,11 +1090,13 @@ ktime_t hrtimer_get_next_event(void) if (!hrtimer_hres_active()) { for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) { struct hrtimer *timer; + struct timerqueue_node *next; - if (!base->first) + next = timerqueue_getnext(&base->active); + if (!next) continue; - timer = rb_entry(base->first, struct hrtimer, node); + timer = container_of(next, struct hrtimer, node); delta.tv64 = hrtimer_get_expires_tv64(timer); delta = ktime_sub(delta, base->get_time()); if (delta.tv64 < mindelta.tv64) @@ -1157,6 +1126,7 @@ static void __hrtimer_init(struct hrtimer *timer, clockid_t clock_id, timer->base = &cpu_base->clock_base[clock_id]; hrtimer_init_timer_hres(timer); + timerqueue_init(&timer->node); #ifdef CONFIG_TIMER_STATS timer->start_site = NULL; @@ -1270,14 +1240,14 @@ retry: for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) { ktime_t basenow; - struct rb_node *node; + struct timerqueue_node *node; basenow = ktime_add(now, base->offset); - while ((node = base->first)) { + while ((node = timerqueue_getnext(&base->active))) { struct hrtimer *timer; - timer = rb_entry(node, struct hrtimer, node); + timer = container_of(node, struct hrtimer, node); /* * The immediate goal for using the softexpires is @@ -1433,7 +1403,7 @@ void hrtimer_run_pending(void) */ void hrtimer_run_queues(void) { - struct rb_node *node; + struct timerqueue_node *node; struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases); struct hrtimer_clock_base *base; int index, gettime = 1; @@ -1442,9 +1412,11 @@ void hrtimer_run_queues(void) return; for (index = 0; index < HRTIMER_MAX_CLOCK_BASES; index++) { - base = &cpu_base->clock_base[index]; + struct timerqueue_node *next; - if (!base->first) + base = &cpu_base->clock_base[index]; + next = timerqueue_getnext(&base->active); + if (!next) continue; if (gettime) { @@ -1454,10 +1426,10 @@ void hrtimer_run_queues(void) raw_spin_lock(&cpu_base->lock); - while ((node = base->first)) { + while ((node = next)) { struct hrtimer *timer; - timer = rb_entry(node, struct hrtimer, node); + timer = container_of(node, struct hrtimer, node); if (base->softirq_time.tv64 <= hrtimer_get_expires_tv64(timer)) break; @@ -1622,8 +1594,10 @@ static void __cpuinit init_hrtimers_cpu(int cpu) raw_spin_lock_init(&cpu_base->lock); - for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) + for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) { cpu_base->clock_base[i].cpu_base = cpu_base; + timerqueue_init_head(&cpu_base->clock_base[i].active); + } hrtimer_init_hres(cpu_base); } @@ -1634,10 +1608,10 @@ static void migrate_hrtimer_list(struct hrtimer_clock_base *old_base, struct hrtimer_clock_base *new_base) { struct hrtimer *timer; - struct rb_node *node; + struct timerqueue_node *node; - while ((node = rb_first(&old_base->active))) { - timer = rb_entry(node, struct hrtimer, node); + while ((node = timerqueue_getnext(&old_base->active))) { + timer = container_of(node, struct hrtimer, node); BUG_ON(hrtimer_callback_running(timer)); debug_deactivate(timer); diff --git a/kernel/time/timer_list.c b/kernel/time/timer_list.c index ab8f5e33fa92..32a19f9397fc 100644 --- a/kernel/time/timer_list.c +++ b/kernel/time/timer_list.c @@ -79,26 +79,26 @@ print_active_timers(struct seq_file *m, struct hrtimer_clock_base *base, { struct hrtimer *timer, tmp; unsigned long next = 0, i; - struct rb_node *curr; + struct timerqueue_node *curr; unsigned long flags; next_one: i = 0; raw_spin_lock_irqsave(&base->cpu_base->lock, flags); - curr = base->first; + curr = timerqueue_getnext(&base->active); /* * Crude but we have to do this O(N*N) thing, because * we have to unlock the base when printing: */ while (curr && i < next) { - curr = rb_next(curr); + curr = timerqueue_iterate_next(curr); i++; } if (curr) { - timer = rb_entry(curr, struct hrtimer, node); + timer = container_of(curr, struct hrtimer, node); tmp = *timer; raw_spin_unlock_irqrestore(&base->cpu_base->lock, flags); -- cgit v1.2.3 From 45f74264e18449cf3c93cccaf098ee6e9524ab78 Mon Sep 17 00:00:00 2001 From: Thomas Gleixner Date: Sat, 11 Dec 2010 12:34:34 +0100 Subject: timerqueue: Make timerqueue_getnext() static inline No point in calling a function just to dereference a pointer. Signed-off-by: Thomas Gleixner Cc: John Stultz --- include/linux/timerqueue.h | 15 ++++++++++++++- lib/timerqueue.c | 14 -------------- 2 files changed, 14 insertions(+), 15 deletions(-) (limited to 'include/linux') diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index 406b103894bd..d24aabaca474 100644 --- a/include/linux/timerqueue.h +++ b/include/linux/timerqueue.h @@ -20,10 +20,23 @@ 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_getnext(struct timerqueue_head *head); 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); diff --git a/lib/timerqueue.c b/lib/timerqueue.c index 444b0934af92..e3a1050e6820 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -84,20 +84,6 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) } EXPORT_SYMBOL_GPL(timerqueue_del); -/** - * 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. - */ -struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) -{ - return head->next; -} -EXPORT_SYMBOL_GPL(timerqueue_getnext); - /** * timerqueue_iterate_next - Returns the timer after the provided timer * -- cgit v1.2.3