From fff421580f512fc044cc7421fdff31a7a6997350 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Tue, 14 Jan 2014 20:20:43 -0800 Subject: timers: Track total number of timers in list Currently, the tvec_base structure's ->active_timers field tracks only the non-deferrable timers, which means that even if ->active_timers is zero, there might well be deferrable timers in the list. This commit therefore adds an ->all_timers field to track all the timers, whether deferrable or not. Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Acked-by: Peter Zijlstra Reviewed-by: Oleg Nesterov Reviewed-by: Steven Rostedt Tested-by: Mike Galbraith --- kernel/timer.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'kernel/timer.c') diff --git a/kernel/timer.c b/kernel/timer.c index accfd241b9e..fdc43834f3a 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -81,6 +81,7 @@ struct tvec_base { unsigned long timer_jiffies; unsigned long next_timer; unsigned long active_timers; + unsigned long all_timers; struct tvec_root tv1; struct tvec tv2; struct tvec tv3; @@ -392,6 +393,7 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) base->next_timer = timer->expires; base->active_timers++; } + base->all_timers++; } #ifdef CONFIG_TIMER_STATS @@ -671,6 +673,7 @@ detach_expired_timer(struct timer_list *timer, struct tvec_base *base) detach_timer(timer, true); if (!tbase_get_deferrable(timer->base)) base->active_timers--; + base->all_timers--; } static int detach_if_pending(struct timer_list *timer, struct tvec_base *base, @@ -685,6 +688,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base, if (timer->expires == base->next_timer) base->next_timer = base->timer_jiffies; } + base->all_timers--; return 1; } @@ -1559,6 +1563,7 @@ static int init_timers_cpu(int cpu) base->timer_jiffies = jiffies; base->next_timer = base->timer_jiffies; base->active_timers = 0; + base->all_timers = 0; return 0; } -- cgit v1.2.3 From d550e81dc0ddc04f1b417c179c214103a28e0ee8 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Mon, 16 Dec 2013 05:57:10 -0800 Subject: timers: Reduce __run_timers() latency for empty list The __run_timers() function currently steps through the list one jiffy at a time in order to update the timer wheel. However, if the timer wheel is empty, no adjustment is needed other than updating ->timer_jiffies. In this case, which is likely to be common for NO_HZ_FULL kernels, the kernel currently incurs a large latency for no good reason. This commit therefore short-circuits this case. Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Acked-by: Peter Zijlstra Reviewed-by: Oleg Nesterov Reviewed-by: Steven Rostedt Tested-by: Mike Galbraith --- kernel/timer.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'kernel/timer.c') diff --git a/kernel/timer.c b/kernel/timer.c index fdc43834f3a..c8bc7091d8f 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -338,6 +338,20 @@ void set_timer_slack(struct timer_list *timer, int slack_hz) } EXPORT_SYMBOL_GPL(set_timer_slack); +/* + * If the list is empty, catch up ->timer_jiffies to the current time. + * The caller must hold the tvec_base lock. Returns true if the list + * was empty and therefore ->timer_jiffies was updated. + */ +static bool catchup_timer_jiffies(struct tvec_base *base) +{ + if (!base->all_timers) { + base->timer_jiffies = jiffies; + return true; + } + return false; +} + static void __internal_add_timer(struct tvec_base *base, struct timer_list *timer) { @@ -1150,6 +1164,10 @@ static inline void __run_timers(struct tvec_base *base) struct timer_list *timer; spin_lock_irq(&base->lock); + if (catchup_timer_jiffies(base)) { + spin_unlock_irq(&base->lock); + return; + } while (time_after_eq(jiffies, base->timer_jiffies)) { struct list_head work_list; struct list_head *head = &work_list; -- cgit v1.2.3 From 16d937f880312e3f47157d4d6d6ebf7e61523378 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Mon, 16 Dec 2013 10:32:01 -0800 Subject: timers: Reduce future __run_timers() latency for newly emptied list The __run_timers() function currently steps through the list one jiffy at a time in order to update the timer wheel. However, if the timer wheel is empty, no adjustment is needed other than updating ->timer_jiffies. Therefore, if we just emptied the timer wheel, for example, by deleting the last timer, we should mark the timer wheel as being up to date. This marking will reduce (and perhaps eliminate) the jiffy-stepping that a future __run_timers() call will need to do in response to some future timer posting or migration. This commit therefore catches ->timer_jiffies for this case. Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Acked-by: Peter Zijlstra Reviewed-by: Oleg Nesterov Reviewed-by: Steven Rostedt Tested-by: Mike Galbraith --- kernel/timer.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'kernel/timer.c') diff --git a/kernel/timer.c b/kernel/timer.c index c8bc7091d8f..dfac34f7186 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -688,6 +688,7 @@ detach_expired_timer(struct timer_list *timer, struct tvec_base *base) if (!tbase_get_deferrable(timer->base)) base->active_timers--; base->all_timers--; + (void)catchup_timer_jiffies(base); } static int detach_if_pending(struct timer_list *timer, struct tvec_base *base, @@ -703,6 +704,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base, base->next_timer = base->timer_jiffies; } base->all_timers--; + (void)catchup_timer_jiffies(base); return 1; } -- cgit v1.2.3 From 18d8cb64c9c074cbe2bd677ab10fff8283abdb62 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Mon, 16 Dec 2013 10:41:50 -0800 Subject: timers: Reduce future __run_timers() latency for first add to empty list The __run_timers() function currently steps through the list one jiffy at a time in order to update the timer wheel. However, if the timer wheel is empty, no adjustment is needed other than updating ->timer_jiffies. Therefore, just before we add a timer to an empty timer wheel, we should mark the timer wheel as being up to date. This marking will reduce (and perhaps eliminate) the jiffy-stepping that a future __run_timers() call will need to do in response to some future timer posting or migration. This commit therefore updates ->timer_jiffies for this case. Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Acked-by: Peter Zijlstra Reviewed-by: Oleg Nesterov Reviewed-by: Steven Rostedt Tested-by: Mike Galbraith --- kernel/timer.c | 1 + 1 file changed, 1 insertion(+) (limited to 'kernel/timer.c') diff --git a/kernel/timer.c b/kernel/timer.c index dfac34f7186..0c638cf3d9d 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -398,6 +398,7 @@ __internal_add_timer(struct tvec_base *base, struct timer_list *timer) static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) { + (void)catchup_timer_jiffies(base); __internal_add_timer(base, timer); /* * Update base->active_timers and base->next_timer -- cgit v1.2.3 From aea369b959bef10d235cd0714789cd8b0fe170b8 Mon Sep 17 00:00:00 2001 From: Oleg Nesterov Date: Wed, 15 Jan 2014 16:19:27 -0800 Subject: timers: Make internal_add_timer() update ->next_timer if ->active_timers == 0 The internal_add_timer() function updates base->next_timer only if timer->expires < base->next_timer. This is correct, but it also makes sense to do the same if we add the first non-deferrable timer. Signed-off-by: Oleg Nesterov Reviewed-by: Steven Rostedt Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Acked-by: Peter Zijlstra Tested-by: Mike Galbraith --- kernel/timer.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'kernel/timer.c') diff --git a/kernel/timer.c b/kernel/timer.c index 0c638cf3d9d..c0d8898fed9 100644 --- a/kernel/timer.c +++ b/kernel/timer.c @@ -404,9 +404,9 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) * Update base->active_timers and base->next_timer */ if (!tbase_get_deferrable(timer->base)) { - if (time_before(timer->expires, base->next_timer)) + if (!base->active_timers++ || + time_before(timer->expires, base->next_timer)) base->next_timer = timer->expires; - base->active_timers++; } base->all_timers++; } -- cgit v1.2.3