Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1651530 > unrolled thread

[PATCH] Revert "timers: Don't wake ktimersoftd on every tick"

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH] Revert "timers: Don't wake ktimersoftd on every tick" Anna-Maria Gleixner <anna-maria@linutronix.de> - 2017-05-26 19:20 +0200
    Re: [PATCH] Revert "timers: Don't wake ktimersoftd on every tick" Thomas Gleixner <tglx@linutronix.de> - 2017-05-26 21:50 +0200
      Re: [PATCH] Revert "timers: Don't wake ktimersoftd on every tick" Thomas Gleixner <tglx@linutronix.de> - 2017-05-27 03:40 +0200
        Re: [PATCH] Revert "timers: Don't wake ktimersoftd on every tick" Thomas Gleixner <tglx@linutronix.de> - 2017-06-04 16:20 +0200
    Re: [PATCH] Revert "timers: Don't wake ktimersoftd on every tick" Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2017-05-27 09:50 +0200

#1651530 — [PATCH] Revert "timers: Don't wake ktimersoftd on every tick"

This reverts commit 032f93cae150a.

The problem is that the look ahead optimization from the tick timer
interrupt context can race with the softirq thread expiring timer. As
a consequence the temporary hlist heads which hold the to expire
timers are overwritten and the timers which are already removed from
the wheel bucket for expiry are now dangling w/o a list head.

That means those timers never get expired. If one of those timers is
canceled the removal operation will result in a hlist corruption.

Signed-off-by: Anna-Maria Gleixner <anna-maria@linutronix.de>
---
 kernel/time/timer.c | 96 ++++++++++++++++-------------------------------------
 1 file changed, 29 insertions(+), 67 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index cdff4411f8f6..08a5ab762495 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -206,8 +206,6 @@ struct timer_base {
 	bool			is_idle;
 	DECLARE_BITMAP(pending_map, WHEEL_SIZE);
 	struct hlist_head	vectors[WHEEL_SIZE];
-	struct hlist_head	expired_lists[LVL_DEPTH];
-	int			expired_count;
 } ____cacheline_aligned;
 
 static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
@@ -1355,8 +1353,7 @@ static void call_timer_fn(struct timer_list *timer, void (*fn)(unsigned long),
 	}
 }
 
-static inline void __expire_timers(struct timer_base *base,
-				   struct hlist_head *head)
+static void expire_timers(struct timer_base *base, struct hlist_head *head)
 {
 	while (!hlist_empty(head)) {
 		struct timer_list *timer;
@@ -1387,38 +1384,21 @@ static inline void __expire_timers(struct timer_base *base,
 	}
 }
 
-static void expire_timers(struct timer_base *base)
-{
-	struct hlist_head *head;
-
-	while (base->expired_count--) {
-		head = base->expired_lists + base->expired_count;
-		__expire_timers(base, head);
-	}
-	base->expired_count = 0;
-}
-
-static void __collect_expired_timers(struct timer_base *base)
+static int __collect_expired_timers(struct timer_base *base,
+				    struct hlist_head *heads)
 {
 	unsigned long clk = base->clk;
 	struct hlist_head *vec;
-	int i;
+	int i, levels = 0;
 	unsigned int idx;
 
-	/*
-	 * expire_timers() must be called at least once before we can
-	 * collect more timers
-	 */
-	if (WARN_ON(base->expired_count))
-		return;
-
 	for (i = 0; i < LVL_DEPTH; i++) {
 		idx = (clk & LVL_MASK) + i * LVL_SIZE;
 
 		if (__test_and_clear_bit(idx, base->pending_map)) {
 			vec = base->vectors + idx;
-			hlist_move_list(vec,
-				&base->expired_lists[base->expired_count++]);
+			hlist_move_list(vec, heads++);
+			levels++;
 		}
 		/* Is it time to look at the next level? */
 		if (clk & LVL_CLK_MASK)
@@ -1426,6 +1406,7 @@ static void __collect_expired_timers(struct timer_base *base)
 		/* Shift clock for the next level granularity */
 		clk >>= LVL_CLK_SHIFT;
 	}
+	return levels;
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
@@ -1618,7 +1599,8 @@ void timer_clear_idle(void)
 	base->is_idle = false;
 }
 
-static void collect_expired_timers(struct timer_base *base)
+static int collect_expired_timers(struct timer_base *base,
+				  struct hlist_head *heads)
 {
 	/*
 	 * NOHZ optimization. After a long idle sleep we need to forward the
@@ -1635,49 +1617,20 @@ static void collect_expired_timers(struct timer_base *base)
 		if (time_after(next, jiffies)) {
 			/* The call site will increment clock! */
 			base->clk = jiffies - 1;
-			return;
+			return 0;
 		}
 		base->clk = next;
 	}
-	__collect_expired_timers(base);
+	return __collect_expired_timers(base, heads);
 }
 #else
-static inline void collect_expired_timers(struct timer_base *base)
+static inline int collect_expired_timers(struct timer_base *base,
+					 struct hlist_head *heads)
 {
-	__collect_expired_timers(base);
+	return __collect_expired_timers(base, heads);
 }
 #endif
 
-static int find_expired_timers(struct timer_base *base)
-{
-	const unsigned long int end_clk = jiffies;
-
-	while (!base->expired_count && time_after_eq(end_clk, base->clk)) {
-		collect_expired_timers(base);
-		base->clk++;
-	}
-
-	return base->expired_count;
-}
-
-/* Called from CPU tick routine to quickly collect expired timers */
-static int tick_find_expired(struct timer_base *base)
-{
-	int count;
-
-	raw_spin_lock(&base->lock);
-
-	if (unlikely(time_after(jiffies, base->clk + HZ))) {
-		/* defer to ktimersoftd; don't spend too long in irq context */
-		count = -1;
-	} else
-		count = find_expired_timers(base);
-
-	raw_spin_unlock(&base->lock);
-
-	return count;
-}
-
 /*
  * Called from the timer interrupt handler to charge one tick to the current
  * process.  user_tick is 1 if the tick is user time, 0 for system.
@@ -1704,11 +1657,22 @@ void update_process_times(int user_tick)
  */
 static inline void __run_timers(struct timer_base *base)
 {
+	struct hlist_head heads[LVL_DEPTH];
+	int levels;
+
+	if (!time_after_eq(jiffies, base->clk))
+		return;
+
 	raw_spin_lock_irq(&base->lock);
 
-	while (find_expired_timers(base))
-		expire_timers(base);
+	while (time_after_eq(jiffies, base->clk)) {
+
+		levels = collect_expired_timers(base, heads);
+		base->clk++;
 
+		while (levels--)
+			expire_timers(base, heads + levels);
+	}
 	raw_spin_unlock_irq(&base->lock);
 	wakeup_timer_waiters(base);
 }
@@ -1736,12 +1700,12 @@ void run_local_timers(void)
 
 	hrtimer_run_queues();
 	/* Raise the softirq only if required. */
-	if (time_before(jiffies, base->clk) || !tick_find_expired(base)) {
+	if (time_before(jiffies, base->clk)) {
 		if (!IS_ENABLED(CONFIG_NO_HZ_COMMON) || !base->nohz_active)
 			return;
 		/* CPU is awake, so check the deferrable base. */
 		base++;
-		if (time_before(jiffies, base->clk) || !tick_find_expired(base))
+		if (time_before(jiffies, base->clk))
 			return;
 	}
 	raise_softirq(TIMER_SOFTIRQ);
@@ -1911,7 +1875,6 @@ int timers_dead_cpu(unsigned int cpu)
 		raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
 
 		BUG_ON(old_base->running_timer);
-		BUG_ON(old_base->expired_count);
 
 		for (i = 0; i < WHEEL_SIZE; i++)
 			migrate_timer_list(new_base, old_base->vectors + i);
@@ -1938,7 +1901,6 @@ static void __init init_timer_cpu(int cpu)
 #ifdef CONFIG_PREEMPT_RT_FULL
 		init_swait_queue_head(&base->wait_for_running_timer);
 #endif
-		base->expired_count = 0;
 	}
 }
 
-- 
2.11.0

[toc] | [next] | [standalone]

#1651593

On Fri, 26 May 2017, Haris Okanovic wrote:

> Anna-Maria,
> 
> Look-ahead is implemented by tick_find_expired() and expiry by __run_timers(),
> both of which hold timer_base::lock (raw spin lock) while running. Those two
> routines shouldn't be able to run simultaneously on the same timer_base. Are
> you sure the race isn't in another code path?

It happens when softirq runs and drops the spinlock to call the timer
function. And from there stuff goes down the drain.

Anna-Maria will send you the test case on monday.

Thanks,

	tglx

	

[toc] | [prev] | [next] | [standalone]

#1651701

On Fri, 26 May 2017, Haris Okanovic wrote:

> Oh crap. I think I see the problem. I decrement expired_count before
> processing the list. Dropping the lock permits another run of
> tick_find_expired()->find_expired_timers() in the middle of __expire_timers()
> since it uses expired_count==0 as a condition.
> 
> This should fix it, but I'll wait for Anna-Maria's test next week before
> submitting a patch.
> 
> >  static void expire_timers(struct timer_base *base)
> >  {
> >         struct hlist_head *head;
> > +       int expCount = base->expired_count;

No camel case for heavens sake!

And this requires:

   	 cnt = READ_ONCE(base->expired_count);

> > -       while (base->expired_count--) {
> > -               head = base->expired_lists + base->expired_count;
> > +       while (expCount--) {
> > +               head = base->expired_lists + expCount;
> >                 __expire_timers(base, head);
> >         }

Plus a comment.

> >         base->expired_count = 0;

Anna-Maria spotted the same issue, but I voted for the revert right now
because I was worried about the consistency of base->clk under all
circumstances.

The other thing I noticed was this weird condition which does not do the
look ahead when base->clk is back for some time. Why don't you use the
existing optimization which uses the bitmap for fast forward?

The other issue I have is that this can race at all. If you raised the
softirq in the look ahead then you should not go into that function until
the softirq has actually completed. There is no point in wasting time in
the hrtimer interrupt if the softirq is running anyway.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1657078

On Fri, 2 Jun 2017, Haris Okanovic wrote:
> On 05/26/2017 03:50 PM, Thomas Gleixner wrote:
> > > >  static void expire_timers(struct timer_base *base)
> > > >  {
> > > >         struct hlist_head *head;
> > > > +       int expCount = base->expired_count;
> > 
> > No camel case for heavens sake!
> > 
> > And this requires:
> > 
> >    	 cnt = READ_ONCE(base->expired_count);
> > 
> > > > -       while (base->expired_count--) {
> > > > -               head = base->expired_lists + base->expired_count;
> > > > +       while (expCount--) {
> > > > +               head = base->expired_lists + expCount;
> > > >                 __expire_timers(base, head);
> > > >         }
> > 
> > Plus a comment.
> 
> Fixed, thanks.
> 
> Are your recommending READ_ONCE() purely for documentation purposes?

Yes.

> > The other thing I noticed was this weird condition which does not do the
> > look ahead when base->clk is back for some time.
> 
> The soft interrupt fires unconditionally if base->clk hasn't advanced in some
> time to limit how long cpu spends in hard interrupt context.

That makes no sense.

> > Why don't you use the
> > existing optimization which uses the bitmap for fast forward?
> > 
> 
> Are you referring to forward_timer_base()/base->next_expiry? I think it's only
> updated in the nohz case. Can you share function name/line number(s) if you're
> thinking of something else.

I think just using collect_expired_timers() should be enough. In the !NOHZ
case the base shouldn't be that far back, right?

> > The other issue I have is that this can race at all. If you raised the
> > softirq in the look ahead then you should not go into that function until
> > the softirq has actually completed. There is no point in wasting time in
> > the hrtimer interrupt if the softirq is running anyway.
> > 
> 
> Makes sense. Skipping the large `if` block in run_local_timers() when
> `local_softirq_pending() & TIMER_SOFTIRQ`.

No. You need your own state tracking. The TIMER_SOFTIRQ bit is cleared when
the softirq is invoked, but that does not mean that it finished running.

run_local_timers()
{
	lock(base->lock);
	if (!base->softirq_activated)
		if (base_has_timers_to_expire()) {
			base->softirq_activated = true;
			raise_softirq(TIMER_SOFTIRQ);
		}
	}
	unlock(base->lock);
}

timer_softirq()
{
	lock(base->lock);
	expire_timers();
	base->softirq_activated = false;
	unlock(base->lock);
}

That way you avoid any operation in the tick interrupt as long as the soft
interrupt processing has not completed.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1651794

On 2017-05-26 19:16:07 [+0200], Anna-Maria Gleixner wrote:
> This reverts commit 032f93cae150a.
> 
> The problem is that the look ahead optimization from the tick timer
> interrupt context can race with the softirq thread expiring timer. As
> a consequence the temporary hlist heads which hold the to expire
> timers are overwritten and the timers which are already removed from
> the wheel bucket for expiry are now dangling w/o a list head.
> 
> That means those timers never get expired. If one of those timers is
> canceled the removal operation will result in a hlist corruption.
> 
> Signed-off-by: Anna-Maria Gleixner <anna-maria@linutronix.de>

Applied

Sebastian

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web