Skip to contentSkip to conversation

hrtimer: Only iterate over active bases

PATCH Superseded Viresh Kumar 2 participants 9 messages Apr 2, 2015 – Apr 3, 2015 High-resolution timers, timer wheel, clockevents

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Viresh Kumar

author
#0 lore raw

cover hrtimer: Only iterate over active bases

Hi,

'active_bases' indicates which clock-base have active timers. While it is updated (almost) correctly, it is hardly used.

And so this is an attempt to improve the code that iterates over all clock-bases.

The first patch fixes a bug that only shows up after the second commit, and the second commit creates a macro for_each_active_base() and uses it at multiple places.

Viresh Kumar (2):
hrtimer: update '->active_bases' before calling
hrtimer_force_reprogram()
hrtimer: create for_each_active_base() to iterate over active
clock-bases

 kernel/time/hrtimer.c | 58 ++++++++++++++++++++++++++++-----------------------
 1 file changed, 32 insertions(+), 26 deletions(-)
Signature · 1 line
2.3.0.rc0.44.ga94655d
author
#1 lore raw

PATCH 1/2 hrtimer: update '->active_bases' before calling hrtimer_force_reprogram()

'active_bases' indicates which clock-base have active timers. While it is updated (almost) correctly, it is hardly used. Next commit will start using it to make code more efficient, but before that we need to fix a problem.

While removing hrtimers, in __remove_hrtimer():
- We first remove the hrtimer from the queue.
- Then reprogram clockevent device if required (hrtimer_force_reprogram()).
- And then finally clear 'active_bases', if no more timers are pending on the current clock base (from which we are removing the hrtimer).

hrtimer_force_reprogram() needs to loop over all active clock bases to find the next expiry event, and while doing so it will use 'active_bases' (after next commit). And it will find the current base active, as we haven't cleared it until now, even if current clock base has no more hrtimers queued.

To fix this issue, clear active_bases before calling hrtimer_force_reprogram().

Reviewed-by Preeti U Murthy <[email protected]>
Signed-off-by Viresh Kumar <[email protected]>
---
 kernel/time/hrtimer.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
kernel/time/hrtimer.c +3 -2
index bee0c1f78091..3152f327c988 100644
@@ -879,6 +879,9 @@ static void __remove_hrtimer(struct hrtimer *timer,
 
 	next_timer = timerqueue_getnext(&base->active);
 	timerqueue_del(&base->active, &timer->node);
+	if (!timerqueue_getnext(&base->active))
+		base->cpu_base->active_bases &= ~(1 << base->index);
+
 	if (&timer->node == next_timer) {
 #ifdef CONFIG_HIGH_RES_TIMERS
 		/* Reprogram the clock event device. if enabled */

@@ -892,8 +895,6 @@ static void __remove_hrtimer(struct hrtimer *timer,
 		}
 #endif
 	}
-	if (!timerqueue_getnext(&base->active))
-		base->cpu_base->active_bases &= ~(1 << base->index);
 out:
 	timer->state = newstate;
 }
Signature · 1 line
2.3.0.rc0.44.ga94655d
#2 lore raw

Re: [PATCH 1/2] hrtimer: update '->active_bases' before calling hrtimer_force_reprogram()

Quoted 12 lines · Viresh Kumar

'active_bases' indicates which clock-base have active timers. While it is updated (almost) correctly, it is hardly used. Next commit will start using it to make code more efficient, but before that we need to fix a problem.

While removing hrtimers, in __remove_hrtimer():
- We first remove the hrtimer from the queue.
- Then reprogram clockevent device if required (hrtimer_force_reprogram()).
- And then finally clear 'active_bases', if no more timers are pending on the current clock base (from which we are removing the hrtimer).

Quoted 8 lines

hrtimer_force_reprogram() needs to loop over all active clock bases to find the next expiry event, and while doing so it will use 'active_bases' (after next commit). And it will find the current base active, as we haven't cleared it until now, even if current clock base has no more hrtimers queued.

To fix this issue, clear active_bases before calling hrtimer_force_reprogram().

This is a small inefficiency right? Not an actual bug or anything.

author
#3 lore raw

Re: [PATCH 1/2] hrtimer: update '->active_bases' before calling hrtimer_force_reprogram()

Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Viresh Kumar

'active_bases' indicates which clock-base have active timers. While it is updated (almost) correctly, it is hardly used. Next commit will start using it to make code more efficient, but before that we need to fix a problem.

While removing hrtimers, in __remove_hrtimer():
- We first remove the hrtimer from the queue.
- Then reprogram clockevent device if required (hrtimer_force_reprogram()).
- And then finally clear 'active_bases', if no more timers are pending on the current clock base (from which we are removing the hrtimer).

hrtimer_force_reprogram() needs to loop over all active clock bases to find the next expiry event, and while doing so it will use 'active_bases' (after next commit). And it will find the current base active, as we haven't cleared it until now, even if current clock base has no more hrtimers queued.

Quoted 4 lines
Quoted 2 lines

To fix this issue, clear active_bases before calling hrtimer_force_reprogram().

This is a small inefficiency right? Not an actual bug or anything.

So, what's explained in this patch is a BUG, which isn't harming us today.

But overall both patches combined are about improving on the small inefficiency :)

Sorry for the political answer :)

#4 lore raw

Re: [PATCH 1/2] hrtimer: update '->active_bases' before calling hrtimer_force_reprogram()

Quoted 20 lines · Viresh Kumar
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Viresh Kumar

'active_bases' indicates which clock-base have active timers. While it is updated (almost) correctly, it is hardly used. Next commit will start using it to make code more efficient, but before that we need to fix a problem.

While removing hrtimers, in __remove_hrtimer():
- We first remove the hrtimer from the queue.
- Then reprogram clockevent device if required (hrtimer_force_reprogram()).
- And then finally clear 'active_bases', if no more timers are pending on the current clock base (from which we are removing the hrtimer).

hrtimer_force_reprogram() needs to loop over all active clock bases to find the next expiry event, and while doing so it will use 'active_bases' (after next commit). And it will find the current base active, as we haven't cleared it until now, even if current clock base has no more hrtimers queued.

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

To fix this issue, clear active_bases before calling hrtimer_force_reprogram().

This is a small inefficiency right? Not an actual bug or anything.

So, what's explained in this patch is a BUG, which isn't harming us today.

So then I'm not seeing how its a bug. Sure __hrtimer_get_next_event() will iterate all the bases again, and it will not skip the just empty one. But I don't see how that is anything but an inefficiency. By virtue of the base being empty it cannot find an event there, so its a pointless check.

What am I missing?

author
#5 lore raw

Re: [PATCH 1/2] hrtimer: update '->active_bases' before calling hrtimer_force_reprogram()

Quoted 7 lines · Peter Zijlstra

So then I'm not seeing how its a bug. Sure __hrtimer_get_next_event() will iterate all the bases again, and it will not skip the just empty one. But I don't see how that is anything but an inefficiency. By virtue of the base being empty it cannot find an event there, so its a pointless check.

What am I missing?

Hmm. It was a bug for me because I was doing this unconditionally:
timer = container_of(timerqueue_getnext(&base->active),
+ struct hrtimer, node);

And this will give a container-of over NULL, as timerqueue_getnext() can return NULL..

And so it will crash in my case.

But I understand your point, its inefficiency only :(

author
#6 lore raw

PATCH 2/2 hrtimer: create for_each_active_base() to iterate over active clock-bases

In reply to Viresh Kumar

At several instances we iterate over all possible clock-bases for a particular cpu-base. Whereas, we only need to iterate over active bases.

We already have per cpu-base 'active_bases' field, which is updated on addition/removal of hrtimers.

This patch creates for_each_active_base(), which uses 'active_bases' to iterate only over active bases.

This also updates code which iterates over clock-bases.

Reviewed-by Preeti U Murthy <[email protected]>
Signed-off-by Viresh Kumar <[email protected]>
---
 kernel/time/hrtimer.c | 53 ++++++++++++++++++++++++++++-----------------------
 1 file changed, 29 insertions(+), 24 deletions(-)
kernel/time/hrtimer.c +29 -24
index 3152f327c988..dad8274623a0 100644
@@ -111,6 +111,19 @@ static inline int hrtimer_clockid_to_base(clockid_t clock_id)
 
 
 /*
+ * for_each_active_base: iterate over all active clock bases
+ * @_index: 'int' variable for internal purpose
+ * @_base: holds pointer to a active clock base
+ * @_cpu_base: cpu base to iterate on
+ * @_active_bases: 'unsigned int' variable for internal purpose
+ */
+#define for_each_active_base(_index, _base, _cpu_base, _active_bases)	\
+	for ((_active_bases) = (_cpu_base)->active_bases;		\
+		(_index) = ffs(_active_bases),				\
+		(_base) = (_cpu_base)->clock_base + (_index) - 1, (_index); \
+		(_active_bases) &= ~(1 << ((_index) - 1)))
+
+/*
  * Get the coarse grained time at the softirq based on xtime and
  * wall_to_monotonic.
  */

@@ -443,19 +456,15 @@ static inline void debug_deactivate(struct hrtimer *timer)
 #if defined(CONFIG_NO_HZ_COMMON) || defined(CONFIG_HIGH_RES_TIMERS)
 static ktime_t __hrtimer_get_next_event(struct hrtimer_cpu_base *cpu_base)
 {
-	struct hrtimer_clock_base *base = cpu_base->clock_base;
+	struct hrtimer_clock_base *base;
 	ktime_t expires, expires_next = { .tv64 = KTIME_MAX };
+	struct hrtimer *timer;
+	unsigned int active_bases;
 	int i;
 
-	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
-		struct timerqueue_node *next;
-		struct hrtimer *timer;
-
-		next = timerqueue_getnext(&base->active);
-		if (!next)
-			continue;
-
-		timer = container_of(next, struct hrtimer, node);
+	for_each_active_base(i, base, cpu_base, active_bases) {
+		timer = container_of(timerqueue_getnext(&base->active),
+				     struct hrtimer, node);
 		expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
 		if (expires.tv64 < expires_next.tv64)
 			expires_next = expires;

@@ -1245,6 +1254,8 @@ void hrtimer_interrupt(struct clock_event_device *dev)
 {
 	struct hrtimer_cpu_base *cpu_base = this_cpu_ptr(&hrtimer_bases);
 	ktime_t expires_next, now, entry_time, delta;
+	struct hrtimer_clock_base *base;
+	unsigned int active_bases;
 	int i, retries = 0;
 
 	BUG_ON(!cpu_base->hres_active);

@@ -1264,15 +1275,10 @@ void hrtimer_interrupt(struct clock_event_device *dev)
 	 */
 	cpu_base->expires_next.tv64 = KTIME_MAX;
 
-	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {
-		struct hrtimer_clock_base *base;
+	for_each_active_base(i, base, cpu_base, active_bases) {
 		struct timerqueue_node *node;
 		ktime_t basenow;
 
-		if (!(cpu_base->active_bases & (1 << i)))
-			continue;
-
-		base = cpu_base->clock_base + i;
 		basenow = ktime_add(now, base->offset);
 
 		while ((node = timerqueue_getnext(&base->active))) {

@@ -1435,16 +1441,13 @@ void hrtimer_run_queues(void)
 	struct timerqueue_node *node;
 	struct hrtimer_cpu_base *cpu_base = this_cpu_ptr(&hrtimer_bases);
 	struct hrtimer_clock_base *base;
+	unsigned int active_bases;
 	int index, gettime = 1;
 
 	if (hrtimer_hres_active())
 		return;
 
-	for (index = 0; index < HRTIMER_MAX_CLOCK_BASES; index++) {
-		base = &cpu_base->clock_base[index];
-		if (!timerqueue_getnext(&base->active))
-			continue;
-
+	for_each_active_base(index, base, cpu_base, active_bases) {
 		if (gettime) {
 			hrtimer_get_softirq_time(cpu_base);
 			gettime = 0;

@@ -1665,6 +1668,8 @@ static void migrate_hrtimer_list(struct hrtimer_clock_base *old_base,
 static void migrate_hrtimers(int scpu)
 {
 	struct hrtimer_cpu_base *old_base, *new_base;
+	struct hrtimer_clock_base *clock_base;
+	unsigned int active_bases;
 	int i;
 
 	BUG_ON(cpu_online(scpu));

@@ -1680,9 +1685,9 @@ static void migrate_hrtimers(int scpu)
 	raw_spin_lock(&new_base->lock);
 	raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
 
-	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {
-		migrate_hrtimer_list(&old_base->clock_base[i],
-				     &new_base->clock_base[i]);
+	for_each_active_base(i, clock_base, old_base, active_bases) {
+		migrate_hrtimer_list(clock_base,
+				     &new_base->clock_base[clock_base->index]);
 	}
 
 	raw_spin_unlock(&old_base->lock);
Signature · 1 line
2.3.0.rc0.44.ga94655d
#7 lore raw

Re: [PATCH 2/2] hrtimer: create for_each_active_base() to iterate over active clock-bases

kernel/time/hrtimer.c static inline int hrtimer_clockid_to_base(clockid_t clock_id) · line 124

Quoted 5 lines · Viresh Kumar
kernel/time/hrtimer.c +5 -0
+#define for_each_active_base(_index, _base, _cpu_base, _active_bases)	\
+	for ((_active_bases) = (_cpu_base)->active_bases;		\
+		(_index) = ffs(_active_bases),				\
+		(_base) = (_cpu_base)->clock_base + (_index) - 1, (_index); \
+		(_active_bases) &= ~(1 << ((_index) - 1)))

Can't use ffs here, some people end up using asm-generic/bitops/ffs.h and that sucks.

Esp for small vectors like here, the unconditional iteration is faster.

author
#8 lore raw

Re: [PATCH 2/2] hrtimer: create for_each_active_base() to iterate over active clock-bases

Quoted 11 lines · Peter Zijlstra

kernel/time/hrtimer.c static inline int hrtimer_clockid_to_base(clockid_t clock_id) · line 124

Quoted 5 lines · Viresh Kumar
kernel/time/hrtimer.c +5 -0
+#define for_each_active_base(_index, _base, _cpu_base, _active_bases)        \
+     for ((_active_bases) = (_cpu_base)->active_bases;               \
+             (_index) = ffs(_active_bases),                          \
+             (_base) = (_cpu_base)->clock_base + (_index) - 1, (_index); \
+             (_active_bases) &= ~(1 << ((_index) - 1)))

Can't use ffs here, some people end up using asm-generic/bitops/ffs.h and that sucks.

Esp for small vectors like here, the unconditional iteration is faster.

Okay what about this instead (This is the best I could write :).) ?

+static inline int __next_bit(unsigned int active_bases, int bit) +{
+ do {
+ if (active_bases & (1 << bit))
+ return bit;
+ } while (++bit < HRTIMER_MAX_CLOCK_BASES);
+
+ /* We should never reach here */
+ return 0;
+}
+/*
+ * for_each_active_base: iterate over all active clock bases
+ * @_bit: 'int' variable for internal purpose
+ * @_base: holds pointer to a active clock base
+ * @_cpu_base: cpu base to iterate on
+ * @_active_bases: 'unsigned int' variable for internal purpose
+ */

+#define for_each_active_base(_bit, _base, _cpu_base, _active_bases)    \
+       for ((_active_bases) = (_cpu_base)->active_bases, (_bit) = -1;  \
+               (_active_bases) &&                                      \
+               ((_bit) = __next_bit(_active_bases, ++_bit),            \
+               (_base) = (_cpu_base)->clock_base + _bit);              \

+ (_active_bases) &= ~(1 << (_bit)))
+

Tested it well with the help of: http://pastebin.com/cYyB513D, with inputs from 0 to 15.

I will send it formally if it looks fine to you ..