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 --- lib/Makefile | 2 +- lib/timerlist.c | 118 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 119 insertions(+), 1 deletion(-) create mode 100644 lib/timerlist.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index e6a3763b821..8b475cfb819 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 00000000000..9101b42fd13 --- /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 'lib') diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h deleted file mode 100644 index c46b28ae6e4..00000000000 --- 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 00000000000..406b103894b --- /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 8b475cfb819..9e2db72d128 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 9101b42fd13..00000000000 --- 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 00000000000..f46de84d946 --- /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 9bb99b147018945366c763b3d4d7008927dc8557 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Mon, 6 Dec 2010 13:32:12 -0800 Subject: timers: Fixup allmodconfig build issue Adds missed EXPORT_SYMBOL lines that cause the following build failures with allmodconfig: ERROR: "timerqueue_add" [drivers/rtc/rtc-core.ko] undefined! ERROR: "timerqueue_getnext" [drivers/rtc/rtc-core.ko] undefined! ERROR: "timerqueue_del" [drivers/rtc/rtc-core.ko] undefined! Reported-by: Ingo Molnar Reported-by: Thomas Gleixner Signed-off-by: John Stultz --- lib/timerqueue.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/timerqueue.c b/lib/timerqueue.c index f46de84d946..444b0934af9 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -24,6 +24,7 @@ #include #include +#include /** * timerqueue_add - Adds timer to timerqueue. @@ -57,6 +58,7 @@ void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) if (!head->next || node->expires.tv64 < head->next->expires.tv64) head->next = node; } +EXPORT_SYMBOL_GPL(timerqueue_add); /** * timerqueue_del - Removes a timer from the timerqueue. @@ -80,7 +82,7 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) rb_erase(&node->node, &head->head); RB_CLEAR_NODE(&node->node); } - +EXPORT_SYMBOL_GPL(timerqueue_del); /** * timerqueue_getnext - Returns the timer with the earlies expiration time @@ -94,7 +96,7 @@ 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 @@ -116,3 +118,4 @@ struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) return NULL; return container_of(next, struct timerqueue_node, node); } +EXPORT_SYMBOL_GPL(timerqueue_iterate_next); -- 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 'lib') diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index 406b103894b..d24aabaca47 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 444b0934af9..e3a1050e682 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