Introduce timerlist infrastructure.
Subsystems (2)
RFC PATCH 1/3 Introduce timerlist infrastructure.
Just wanted to send this out for comments. I'm working to split up my posix CLOCK_RTC proof of concept and this is one of the stepping stones to be merged sometime later.
Richard's recent patch queue looks like it could use this functionality, so I wanted to get some comments on it before trying to build much further upon it.
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.
Suggestions or feedback would be appreciated.
--- include/linux/timerlist.h | 37 ++++++++++++++ lib/Makefile | 2 +- lib/timerlist.c | 115 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 153 insertions(+), 1 deletions(-) create mode 100644 include/linux/timerlist.h create mode 100644 lib/timerlist.c
include/linux/timerlist.h new file +37 -0
@@ -0,0 +1,37 @@ +#ifndef _LINUX_TIMERLIST_H +#define _LINUX_TIMERLIST_H + +#include <linux/rbtree.h> +#include <linux/ktime.h> + + +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 */
lib/Makefile +1 -1
@@ -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 \
lib/timerlist.c new file +115 -0
115 lines not on this page · raw message
Signature · 1 line
1.6.0.4
RFC PATCH 2/3 Convert hrtimers to use timerlist infrastructure
Converts the hrtimer code to use the timerlist infrastructure
Survived some light testing, but there may still be bugs.
--- include/linux/hrtimer.h | 32 ++++++++--------- kernel/hrtimer.c | 86 ++++++++++++++++------------------------------ kernel/time/timer_list.c | 8 ++-- 3 files changed, 49 insertions(+), 77 deletions(-)
include/linux/hrtimer.h +15 -17
@@ -22,7 +22,7 @@#include <linux/wait.h> #include <linux/percpu.h> #include <linux/timer.h> - +#include <linux/timerlist.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: timerlist 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 timerlist_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 timerlist_head active;ktime_t resolution;ktime_t (*get_time)(void );ktime_t softirq_time;
@@ -184,43 +182,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 +228,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 +237,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
kernel/hrtimer.c +30 -56
182 lines not on this page · raw message
kernel/time/timer_list.c +4 -4
@@ -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 timerlist_node *curr;unsigned long flags; next_one: i =0 ;raw_spin_lock_irqsave (&base->cpu_base->lock, flags); - curr = base->first; + curr =timerlist_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 =timerlist_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);
Signature · 1 line
1.6.0.4
Quoted 3 lines · John Stultz
Just wanted to send this out for comments. I'm working to split up my posix
CLOCK_RTCproof of concept and this is one of the stepping stones to be merged sometime later.
Oh bah! Forgot to checkout at the end of the patch queue, instead of in my dev branch.
So this is really 1/2. There is no 3rd patch in this series (well, none that's ready to send out, yet).
Sorry for the confusion.
-john