LKML Archive on lore.kernel.org
 help / color / Atom feed
From: tip-bot for Anna-Maria Gleixner <tipbot@zytor.com>
To: linux-tip-commits@vger.kernel.org
Cc: linux-kernel@vger.kernel.org, mingo@kernel.org, hpa@zytor.com,
	anna-maria@linutronix.de, tglx@linutronix.de,
	bigeasy@linutronix.de, peterz@infradead.org
Subject: [tip:timers/core] timers: Prepare support for PREEMPT_RT
Date: Tue, 30 Jul 2019 15:17:58 -0700
Message-ID: <tip-51503daaaacd6118d627a0c1b5829191d4fa6f16@git.kernel.org> (raw)
In-Reply-To: <20190726185753.832418500@linutronix.de>

Commit-ID:  51503daaaacd6118d627a0c1b5829191d4fa6f16
Gitweb:     https://git.kernel.org/tip/51503daaaacd6118d627a0c1b5829191d4fa6f16
Author:     Anna-Maria Gleixner <anna-maria@linutronix.de>
AuthorDate: Fri, 26 Jul 2019 20:31:00 +0200
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Tue, 30 Jul 2019 23:57:57 +0200

timers: Prepare support for PREEMPT_RT

When PREEMPT_RT is enabled, the soft interrupt thread can be preempted.  If
the soft interrupt thread is preempted in the middle of a timer callback,
then calling del_timer_sync() can lead to two issues:

  - If the caller is on a remote CPU then it has to spin wait for the timer
    handler to complete. This can result in unbound priority inversion.

  - If the caller originates from the task which preempted the timer
    handler on the same CPU, then spin waiting for the timer handler to
    complete is never going to end.

To avoid these issues, add a new lock to the timer base which is held
around the execution of the timer callbacks. If del_timer_sync() detects
that the timer callback is currently running, it blocks on the expiry
lock. When the callback is finished, the expiry lock is dropped by the
softirq thread which wakes up the waiter and the system makes progress.

This addresses both the priority inversion and the life lock issues.

This mechanism is not used for timers which are marked IRQSAFE as for those
preemption is disabled accross the callback and therefore this situation
cannot happen. The callbacks for such timers need to be individually
audited for RT compliance.

The same issue can happen in virtual machines when the vCPU which runs a
timer callback is scheduled out. If a second vCPU of the same guest calls
del_timer_sync() it will spin wait for the other vCPU to be scheduled back
in. The expiry lock mechanism would avoid that. It'd be trivial to enable
this when paravirt spinlocks are enabled in a guest, but it's not clear
whether this is an actual problem in the wild, so for now it's an RT only
mechanism.

As the softirq thread can be preempted with PREEMPT_RT=y, the SMP variant
of del_timer_sync() needs to be used on UP as well.

[ tglx: Refactored it for mainline ]

Signed-off-by: Anna-Maria Gleixner <anna-maria@linutronix.de>
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://lkml.kernel.org/r/20190726185753.832418500@linutronix.de

---
 include/linux/timer.h |   2 +-
 kernel/time/timer.c   | 103 ++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 96 insertions(+), 9 deletions(-)

diff --git a/include/linux/timer.h b/include/linux/timer.h
index 282e4f2a532a..1e6650ed066d 100644
--- a/include/linux/timer.h
+++ b/include/linux/timer.h
@@ -183,7 +183,7 @@ extern void add_timer(struct timer_list *timer);
 
 extern int try_to_del_timer_sync(struct timer_list *timer);
 
-#ifdef CONFIG_SMP
+#if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT_RT)
   extern int del_timer_sync(struct timer_list *timer);
 #else
 # define del_timer_sync(t)		del_timer(t)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 343c7ba33b1c..673c6a0f0c45 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -196,6 +196,10 @@ EXPORT_SYMBOL(jiffies_64);
 struct timer_base {
 	raw_spinlock_t		lock;
 	struct timer_list	*running_timer;
+#ifdef CONFIG_PREEMPT_RT
+	spinlock_t		expiry_lock;
+	atomic_t		timer_waiters;
+#endif
 	unsigned long		clk;
 	unsigned long		next_expiry;
 	unsigned int		cpu;
@@ -1227,7 +1231,78 @@ int try_to_del_timer_sync(struct timer_list *timer)
 }
 EXPORT_SYMBOL(try_to_del_timer_sync);
 
-#ifdef CONFIG_SMP
+#ifdef CONFIG_PREEMPT_RT
+static __init void timer_base_init_expiry_lock(struct timer_base *base)
+{
+	spin_lock_init(&base->expiry_lock);
+}
+
+static inline void timer_base_lock_expiry(struct timer_base *base)
+{
+	spin_lock(&base->expiry_lock);
+}
+
+static inline void timer_base_unlock_expiry(struct timer_base *base)
+{
+	spin_unlock(&base->expiry_lock);
+}
+
+/*
+ * The counterpart to del_timer_wait_running().
+ *
+ * If there is a waiter for base->expiry_lock, then it was waiting for the
+ * timer callback to finish. Drop expiry_lock and reaquire it. That allows
+ * the waiter to acquire the lock and make progress.
+ */
+static void timer_sync_wait_running(struct timer_base *base)
+{
+	if (atomic_read(&base->timer_waiters)) {
+		spin_unlock(&base->expiry_lock);
+		spin_lock(&base->expiry_lock);
+	}
+}
+
+/*
+ * This function is called on PREEMPT_RT kernels when the fast path
+ * deletion of a timer failed because the timer callback function was
+ * running.
+ *
+ * This prevents priority inversion, if the softirq thread on a remote CPU
+ * got preempted, and it prevents a life lock when the task which tries to
+ * delete a timer preempted the softirq thread running the timer callback
+ * function.
+ */
+static void del_timer_wait_running(struct timer_list *timer)
+{
+	u32 tf;
+
+	tf = READ_ONCE(timer->flags);
+	if (!(tf & TIMER_MIGRATING)) {
+		struct timer_base *base = get_timer_base(tf);
+
+		/*
+		 * Mark the base as contended and grab the expiry lock,
+		 * which is held by the softirq across the timer
+		 * callback. Drop the lock immediately so the softirq can
+		 * expire the next timer. In theory the timer could already
+		 * be running again, but that's more than unlikely and just
+		 * causes another wait loop.
+		 */
+		atomic_inc(&base->timer_waiters);
+		spin_lock_bh(&base->expiry_lock);
+		atomic_dec(&base->timer_waiters);
+		spin_unlock_bh(&base->expiry_lock);
+	}
+}
+#else
+static inline void timer_base_init_expiry_lock(struct timer_base *base) { }
+static inline void timer_base_lock_expiry(struct timer_base *base) { }
+static inline void timer_base_unlock_expiry(struct timer_base *base) { }
+static inline void timer_sync_wait_running(struct timer_base *base) { }
+static inline void del_timer_wait_running(struct timer_list *timer) { }
+#endif
+
+#if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT_RT)
 /**
  * del_timer_sync - deactivate a timer and wait for the handler to finish.
  * @timer: the timer to be deactivated
@@ -1266,6 +1341,8 @@ EXPORT_SYMBOL(try_to_del_timer_sync);
  */
 int del_timer_sync(struct timer_list *timer)
 {
+	int ret;
+
 #ifdef CONFIG_LOCKDEP
 	unsigned long flags;
 
@@ -1283,12 +1360,17 @@ int del_timer_sync(struct timer_list *timer)
 	 * could lead to deadlock.
 	 */
 	WARN_ON(in_irq() && !(timer->flags & TIMER_IRQSAFE));
-	for (;;) {
-		int ret = try_to_del_timer_sync(timer);
-		if (ret >= 0)
-			return ret;
-		cpu_relax();
-	}
+
+	do {
+		ret = try_to_del_timer_sync(timer);
+
+		if (unlikely(ret < 0)) {
+			del_timer_wait_running(timer);
+			cpu_relax();
+		}
+	} while (ret < 0);
+
+	return ret;
 }
 EXPORT_SYMBOL(del_timer_sync);
 #endif
@@ -1360,10 +1442,13 @@ static void expire_timers(struct timer_base *base, struct hlist_head *head)
 		if (timer->flags & TIMER_IRQSAFE) {
 			raw_spin_unlock(&base->lock);
 			call_timer_fn(timer, fn, baseclk);
+			base->running_timer = NULL;
 			raw_spin_lock(&base->lock);
 		} else {
 			raw_spin_unlock_irq(&base->lock);
 			call_timer_fn(timer, fn, baseclk);
+			base->running_timer = NULL;
+			timer_sync_wait_running(base);
 			raw_spin_lock_irq(&base->lock);
 		}
 	}
@@ -1658,6 +1743,7 @@ static inline void __run_timers(struct timer_base *base)
 	if (!time_after_eq(jiffies, base->clk))
 		return;
 
+	timer_base_lock_expiry(base);
 	raw_spin_lock_irq(&base->lock);
 
 	/*
@@ -1684,8 +1770,8 @@ static inline void __run_timers(struct timer_base *base)
 		while (levels--)
 			expire_timers(base, heads + levels);
 	}
-	base->running_timer = NULL;
 	raw_spin_unlock_irq(&base->lock);
+	timer_base_unlock_expiry(base);
 }
 
 /*
@@ -1930,6 +2016,7 @@ static void __init init_timer_cpu(int cpu)
 		base->cpu = cpu;
 		raw_spin_lock_init(&base->lock);
 		base->clk = jiffies;
+		timer_base_init_expiry_lock(base);
 	}
 }
 

  reply index

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-07-26 18:30 [patch 00/12] (hr)timers: Prepare for PREEMPT_RT support Thomas Gleixner
2019-07-26 18:30 ` [patch 01/12] hrtimer: Remove task argument from hrtimer_init_sleeper() Thomas Gleixner
2019-07-26 19:57   ` Steven Rostedt
2019-07-26 20:01     ` Thomas Gleixner
2019-07-30 22:07   ` [tip:timers/core] " tip-bot for Thomas Gleixner
2019-07-26 18:30 ` [patch 02/12] hrtimer: Consolidate hrtimer_init() + hrtimer_init_sleeper() calls Thomas Gleixner
2019-07-30 22:08   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:49   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 03/12] hrtimer: Introduce HARD expiry mode Thomas Gleixner
2019-07-30 22:10   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:52   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 04/12] sched: Mark hrtimers to expire in hard interrupt context Thomas Gleixner
2019-07-30 22:11   ` [tip:timers/core] " tip-bot for Thomas Gleixner
2019-08-01 15:53   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 18:58   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 05/12] perf/core: " Thomas Gleixner
2019-07-30 22:12   ` [tip:timers/core] " tip-bot for Thomas Gleixner
2019-08-01 15:54   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 18:59   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 06/12] watchdog: Mark watchdog_hrtimer " Thomas Gleixner
2019-07-30 22:13   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:55   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 19:00   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 07/12] KVM: LAPIC: Mark hrtimer " Thomas Gleixner
2019-07-26 19:41   ` Paolo Bonzini
2019-07-30 22:14   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:55   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 19:01   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 08/12] tick: Mark tick related hrtimers to expiry " Thomas Gleixner
2019-07-30 22:14   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:56   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 19:01   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 09/12] hrtimer: Move unmarked hrtimers to soft interrupt expiry on RT Thomas Gleixner
2019-07-30 22:15   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:57   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 19:02   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 10/12] hrtimer: Determine hard/soft expiry mode for hrtimer sleepers " Thomas Gleixner
2019-07-26 20:44   ` Steven Rostedt
2019-07-26 20:52     ` Thomas Gleixner
2019-07-26 20:56       ` Steven Rostedt
2019-07-26 21:16   ` Julia Cartwright
2019-07-26 21:30     ` Steven Rostedt
2019-07-26 21:35     ` Thomas Gleixner
2019-07-30 22:16   ` [tip:timers/core] " tip-bot for Sebastian Andrzej Siewior
2019-08-01 15:58   ` tip-bot for Sebastian Andrzej Siewior
2019-08-01 19:03   ` tip-bot for Sebastian Andrzej Siewior
2019-07-26 18:30 ` [patch 11/12] hrtimer: Prepare support for PREEMPT_RT Thomas Gleixner
2019-07-28  9:06   ` Juergen Gross
2019-07-29 15:08     ` Steven Rostedt
2019-07-29 17:30       ` Paolo Bonzini
2019-07-31  8:45         ` Juergen Gross
2019-07-30 22:17   ` [tip:timers/core] " tip-bot for Anna-Maria Gleixner
2019-08-01 15:58   ` tip-bot for Anna-Maria Gleixner
2019-08-01 19:04   ` tip-bot for Anna-Maria Gleixner
2019-08-20 13:26     ` Frederic Weisbecker
2019-08-23  2:12       ` [tip: timers/core] hrtimer: Improve comments on handling priority inversion against softirq kthread tip-bot2 for Frederic Weisbecker
2019-07-26 18:31 ` [patch 12/12] timers: Prepare support for PREEMPT_RT Thomas Gleixner
2019-07-30 22:17   ` tip-bot for Anna-Maria Gleixner [this message]
2019-08-01 15:59   ` [tip:timers/core] " tip-bot for Anna-Maria Gleixner
2019-08-01 19:04   ` tip-bot for Anna-Maria Gleixner
2019-07-29 19:45 ` [patch 00/12] (hr)timers: Prepare for PREEMPT_RT support Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=tip-51503daaaacd6118d627a0c1b5829191d4fa6f16@git.kernel.org \
    --to=tipbot@zytor.com \
    --cc=anna-maria@linutronix.de \
    --cc=bigeasy@linutronix.de \
    --cc=hpa@zytor.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-tip-commits@vger.kernel.org \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=tglx@linutronix.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lore.kernel.org/lkml/8 lkml/git/8.git
	git clone --mirror https://lore.kernel.org/lkml/9 lkml/git/9.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git