LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Gregory Haskins <ghaskins@novell.com>
To: mingo@elte.hu, a.p.zijlstra@chello.nl, tglx@linutronix.de,
	rostedt@goodmis.org, linux-rt-users@vger.kernel.org
Cc: linux-kernel@vger.kernel.org, bill.huey@gmail.com,
	kevin@hilman.org, cminyard@mvista.com, dsingleton@mvista.com,
	dwalker@mvista.com, npiggin@suse.de, dsaxena@plexity.net,
	ak@suse.de, pavel@ucw.cz, acme@redhat.com, gregkh@suse.de,
	sdietrich@novell.com, pmorreale@novell.com, mkohari@novell.com,
	ghaskins@novell.com
Subject: [(RT RFC) PATCH v2 1/9] allow rt-mutex lock-stealing to include lateral priority
Date: Mon, 25 Feb 2008 11:00:43 -0500	[thread overview]
Message-ID: <20080225160043.11268.83915.stgit@novell1.haskins.net> (raw)
In-Reply-To: <20080225155959.11268.35541.stgit@novell1.haskins.net>

The current logic only allows lock stealing to occur if the current task
is of higher priority than the pending owner. We can gain signficant
throughput improvements (200%+) by allowing the lock-stealing code to
include tasks of equal priority.  The theory is that the system will make
faster progress by allowing the task already on the CPU to take the lock
rather than waiting for the system to wake-up a different task.

This does add a degree of unfairness, yes.  But also note that the users
of these locks under non -rt environments have already been using unfair
raw spinlocks anyway so the tradeoff is probably worth it.

The way I like to think of this is that higher priority tasks should
clearly preempt, and lower priority tasks should clearly block.  However,
if tasks have an identical priority value, then we can think of the
scheduler decisions as the tie-breaking parameter. (e.g. tasks that the
scheduler picked to run first have a logically higher priority amoung tasks
of the same prio).  This helps to keep the system "primed" with tasks doing
useful work, and the end result is higher throughput.

Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/Kconfig.preempt |   10 ++++++++++
 kernel/rtmutex.c       |   31 +++++++++++++++++++++++--------
 2 files changed, 33 insertions(+), 8 deletions(-)

diff --git a/kernel/Kconfig.preempt b/kernel/Kconfig.preempt
index 41a0d88..e493257 100644
--- a/kernel/Kconfig.preempt
+++ b/kernel/Kconfig.preempt
@@ -196,3 +196,13 @@ config SPINLOCK_BKL
 	  Say Y here if you are building a kernel for a desktop system.
 	  Say N if you are unsure.
 
+config RTLOCK_LATERAL_STEAL
+        bool "Allow equal-priority rtlock stealing"
+        default y
+        depends on PREEMPT_RT
+        help
+          This option alters the rtlock lock-stealing logic to allow
+          equal priority tasks to preempt a pending owner in addition
+          to higher priority tasks.  This allows for a significant
+          boost in throughput under certain circumstances at the expense
+          of strict FIFO lock access.
diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
index a2b00cc..6624c66 100644
--- a/kernel/rtmutex.c
+++ b/kernel/rtmutex.c
@@ -313,12 +313,27 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 	return ret;
 }
 
+static inline int lock_is_stealable(struct task_struct *pendowner, int unfair)
+{
+#ifndef CONFIG_RTLOCK_LATERAL_STEAL
+	if (current->prio >= pendowner->prio)
+#else
+	if (current->prio > pendowner->prio)
+		return 0;
+
+	if (!unfair && (current->prio == pendowner->prio))
+#endif
+		return 0;
+
+	return 1;
+}
+
 /*
  * Optimization: check if we can steal the lock from the
  * assigned pending owner [which might not have taken the
  * lock yet]:
  */
-static inline int try_to_steal_lock(struct rt_mutex *lock)
+static inline int try_to_steal_lock(struct rt_mutex *lock, int unfair)
 {
 	struct task_struct *pendowner = rt_mutex_owner(lock);
 	struct rt_mutex_waiter *next;
@@ -330,7 +345,7 @@ static inline int try_to_steal_lock(struct rt_mutex *lock)
 		return 1;
 
 	spin_lock(&pendowner->pi_lock);
-	if (current->prio >= pendowner->prio) {
+	if (!lock_is_stealable(pendowner, unfair)) {
 		spin_unlock(&pendowner->pi_lock);
 		return 0;
 	}
@@ -383,7 +398,7 @@ static inline int try_to_steal_lock(struct rt_mutex *lock)
  *
  * Must be called with lock->wait_lock held.
  */
-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, int unfair)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are
@@ -406,7 +421,7 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock)
 	 */
 	mark_rt_mutex_waiters(lock);
 
-	if (rt_mutex_owner(lock) && !try_to_steal_lock(lock))
+	if (rt_mutex_owner(lock) && !try_to_steal_lock(lock, unfair))
 		return 0;
 
 	/* We got the lock. */
@@ -707,7 +722,7 @@ rt_spin_lock_slowlock(struct rt_mutex *lock)
 		int saved_lock_depth = current->lock_depth;
 
 		/* Try to acquire the lock */
-		if (try_to_take_rt_mutex(lock))
+		if (try_to_take_rt_mutex(lock, 1))
 			break;
 		/*
 		 * waiter.task is NULL the first time we come here and
@@ -947,7 +962,7 @@ rt_mutex_slowlock(struct rt_mutex *lock, int state,
 	init_lists(lock);
 
 	/* Try to acquire the lock again: */
-	if (try_to_take_rt_mutex(lock)) {
+	if (try_to_take_rt_mutex(lock, 0)) {
 		spin_unlock_irqrestore(&lock->wait_lock, flags);
 		return 0;
 	}
@@ -970,7 +985,7 @@ rt_mutex_slowlock(struct rt_mutex *lock, int state,
 		unsigned long saved_flags;
 
 		/* Try to acquire the lock: */
-		if (try_to_take_rt_mutex(lock))
+		if (try_to_take_rt_mutex(lock, 0))
 			break;
 
 		/*
@@ -1078,7 +1093,7 @@ rt_mutex_slowtrylock(struct rt_mutex *lock)
 
 		init_lists(lock);
 
-		ret = try_to_take_rt_mutex(lock);
+		ret = try_to_take_rt_mutex(lock, 0);
 		/*
 		 * try_to_take_rt_mutex() sets the lock waiters
 		 * bit unconditionally. Clean this up.


  reply	other threads:[~2008-02-25 16:29 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-02-25 16:00 [(RT RFC) PATCH v2 0/9] adaptive real-time locks Gregory Haskins
2008-02-25 16:00 ` Gregory Haskins [this message]
2008-03-03 15:13   ` [(RT RFC) PATCH v2 1/9] allow rt-mutex lock-stealing to include lateral priority Steven Rostedt
2008-03-03 15:41     ` [(RT RFC) PATCH v2 1/9] allow rt-mutex lock-stealing to includelateral priority Gregory Haskins
2008-03-03 15:55       ` Steven Rostedt
2008-03-03 15:55         ` [(RT RFC) PATCH v2 1/9] allow rt-mutex lock-stealing toincludelateral priority Gregory Haskins
2008-02-25 16:00 ` [(RT RFC) PATCH v2 2/9] sysctl for runtime-control of lateral mutex stealing Gregory Haskins
2008-02-25 21:53   ` Pavel Machek
2008-02-25 22:57     ` Sven-Thorsten Dietrich
2008-02-25 23:00       ` Pavel Machek
2008-02-25 23:40         ` Sven-Thorsten Dietrich
2008-02-26  1:15       ` Gregory Haskins
2008-02-25 16:00 ` [(RT RFC) PATCH v2 3/9] rearrange rt_spin_lock sleep Gregory Haskins
2008-02-25 21:54   ` Pavel Machek
2008-02-26  0:45     ` Gregory Haskins
2008-02-25 16:00 ` [(RT RFC) PATCH v2 4/9] optimize rt lock wakeup Gregory Haskins
2008-03-03 15:37   ` Steven Rostedt
2008-03-03 15:41     ` Gregory Haskins
2008-02-25 16:01 ` [(RT RFC) PATCH v2 5/9] adaptive real-time lock support Gregory Haskins
2008-02-25 22:03   ` Pavel Machek
2008-02-26  0:48     ` Gregory Haskins
2008-02-26 15:03     ` Gregory Haskins
2008-02-26 18:06       ` Pavel Machek
2008-02-26 18:01         ` Gregory Haskins
2008-02-25 16:01 ` [(RT RFC) PATCH v2 6/9] add a loop counter based timeout mechanism Gregory Haskins
2008-02-25 22:06   ` Pavel Machek
2008-02-25 22:19     ` Greg KH
2008-02-25 22:21       ` Pavel Machek
2008-02-25 22:39     ` Sven-Thorsten Dietrich
2008-02-26 15:09     ` Gregory Haskins
2008-02-25 16:01 ` [(RT RFC) PATCH v2 7/9] adaptive mutexes Gregory Haskins
2008-02-25 22:09   ` Pavel Machek
2008-02-26  0:52     ` Gregory Haskins
2008-02-25 16:01 ` [(RT RFC) PATCH v2 8/9] adjust pi_lock usage in wakeup Gregory Haskins
2008-02-25 22:10   ` Pavel Machek
2008-02-25 16:01 ` [(RT RFC) PATCH v2 9/9] remove the extra call to try_to_take_lock Gregory Haskins

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=20080225160043.11268.83915.stgit@novell1.haskins.net \
    --to=ghaskins@novell.com \
    --cc=a.p.zijlstra@chello.nl \
    --cc=acme@redhat.com \
    --cc=ak@suse.de \
    --cc=bill.huey@gmail.com \
    --cc=cminyard@mvista.com \
    --cc=dsaxena@plexity.net \
    --cc=dsingleton@mvista.com \
    --cc=dwalker@mvista.com \
    --cc=gregkh@suse.de \
    --cc=kevin@hilman.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-rt-users@vger.kernel.org \
    --cc=mingo@elte.hu \
    --cc=mkohari@novell.com \
    --cc=npiggin@suse.de \
    --cc=pavel@ucw.cz \
    --cc=pmorreale@novell.com \
    --cc=rostedt@goodmis.org \
    --cc=sdietrich@novell.com \
    --cc=tglx@linutronix.de \
    --subject='Re: [(RT RFC) PATCH v2 1/9] allow rt-mutex lock-stealing to include lateral priority' \
    /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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).