[PATCH 0/5] RT: adaptive-lock enhancements

[PATCH 0/5] RT: adaptive-lock enhancements

[Gregory Haskins]

Hi Ingo, Steven, Thomas,
  The following series are the scraps from adaptive-locks-v3 that have not yet
  been pulled into RT.  This series applies to 25.4-rt2.

  For the most part, this is the difference between adaptive-v3 and whats in
  the upstream tree, with the following exceptions:

  1) I have fixed an issue in the "optimize-wakeup" patch that went out in v3.
     There was a hunk left-over from when we applied adaptive to both spinlocks
     and mutexes.  We have since dropped mutexes, so that patch needed to be
     refactored to be correct.

  2) I have (for now) dropped the timeout feature.  It needs to be re-worked to
     apply to the current version of adaptive-locks that are in the tree.

  I also moved what was patch 6/8 in v3 to be first, because I believe it has
  the most potential of all the other patches to improve performance.

  I have performed some baseline analysis of these patches compared to
  25.4-rt2, which you can find here:

    ftp://ftp.novell.com/dev/ghaskins/25.4-rt2-adaptive-enhancements.pdf

  I only did hackbench runs for this round of testing, but you can see there is
  a small, but net-positive gain in the results.  I think the results are more
  profound for other benchmarks, but I didnt have the time to re-run them all
  yet.

  As always, comments/questions welcome.

  Regards,
   -Greg

[PATCH 1/5] optimize rt lock wakeup

[Gregory Haskins]

It is redundant to wake the grantee task if it is already running, and 
the call to wake_up_process is relatively expensive.  If we can safely
skip it we can measurably improve the performance of the adaptive-locks.

Credit goes to Peter Morreale for the general idea.

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

 kernel/rtmutex.c |   45 ++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 40 insertions(+), 5 deletions(-)

diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
index 6c1debb..8ae9de3 100644
--- a/kernel/rtmutex.c
+++ b/kernel/rtmutex.c
@@ -522,6 +522,41 @@ static void wakeup_next_waiter(struct rt_mutex *lock, int savestate)
 	pendowner = waiter->task;
 	waiter->task = NULL;
 
+	/*
+	 * Do the wakeup before the ownership change to give any spinning
+	 * waiter grantees a headstart over the other threads that will
+	 * trigger once owner changes.
+	 */
+	if (!savestate)
+		wake_up_process(pendowner);
+	else {
+		/*
+		 * We can skip the actual (expensive) wakeup if the
+		 * waiter is already running, but we have to be careful
+		 * of race conditions because they may be about to sleep.
+		 *
+		 * The waiter-side protocol has the following pattern:
+		 * 1: Set state != RUNNING
+		 * 2: Conditionally sleep if waiter->task != NULL;
+		 *
+		 * And the owner-side has the following:
+		 * A: Set waiter->task = NULL
+		 * B: Conditionally wake if the state != RUNNING
+		 *
+		 * As long as we ensure 1->2 order, and A->B order, we
+		 * will never miss a wakeup.
+		 *
+		 * Therefore, this barrier ensures that waiter->task = NULL
+		 * is visible before we test the pendowner->state.  The
+		 * corresponding barrier is in the sleep logic.
+		 */
+		smp_mb();
+
+		/* If !RUNNING && !RUNNING_MUTEX */
+		if (pendowner->state & ~TASK_RUNNING_MUTEX)
+			wake_up_process_mutex(pendowner);
+	}
+
 	rt_mutex_set_owner(lock, pendowner, RT_MUTEX_OWNER_PENDING);
 
 	spin_unlock(&current->pi_lock);
@@ -548,11 +583,6 @@ static void wakeup_next_waiter(struct rt_mutex *lock, int savestate)
 		plist_add(&next->pi_list_entry, &pendowner->pi_waiters);
 	}
 	spin_unlock(&pendowner->pi_lock);
-
-	if (savestate)
-		wake_up_process_mutex(pendowner);
-	else
-		wake_up_process(pendowner);
 }
 
 /*
@@ -803,6 +833,11 @@ rt_spin_lock_slowlock(struct rt_mutex *lock)
 
 		if (adaptive_wait(&waiter, orig_owner)) {
 			update_current(TASK_UNINTERRUPTIBLE, &saved_state);
+			/*
+			 * The xchg() in update_current() is an implicit
+			 * barrier which we rely upon to ensure current->state
+			 * is visible before we test waiter.task.
+			 */
 			if (waiter.task)
 				schedule_rt_mutex(lock);
 		}

[PATCH 2/5] sched: make task->oncpu available in all configurations

[Gregory Haskins]

We will use this later in the series to eliminate the need for a function
call.

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

 include/linux/sched.h |    2 --
 kernel/sched.c        |   35 ++++++++++++++++++++++++-----------
 2 files changed, 24 insertions(+), 13 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index ec94970..70175e0 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1080,10 +1080,8 @@ struct task_struct {
 	int lock_depth;		/* BKL lock depth */
 
 #ifdef CONFIG_SMP
-#ifdef __ARCH_WANT_UNLOCKED_CTXSW
 	int oncpu;
 #endif
-#endif
 
 	int prio, static_prio, normal_prio;
 #ifdef CONFIG_PREEMPT_RCU_BOOST
diff --git a/kernel/sched.c b/kernel/sched.c
index 4428916..03cb222 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -699,18 +699,39 @@ static inline int task_current(struct rq *rq, struct task_struct *p)
 	return rq->curr == p;
 }
 
-#ifndef __ARCH_WANT_UNLOCKED_CTXSW
 static inline int task_running(struct rq *rq, struct task_struct *p)
 {
+#ifdef CONFIG_SMP
+	return p->oncpu;
+#else
 	return task_current(rq, p);
+#endif
 }
 
+#ifndef __ARCH_WANT_UNLOCKED_CTXSW
 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 {
+#ifdef CONFIG_SMP
+	/*
+	 * We can optimise this out completely for !SMP, because the
+	 * SMP rebalancing from interrupt is the only thing that cares
+	 * here.
+	 */
+	next->oncpu = 1;
+#endif
 }
 
 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 {
+#ifdef CONFIG_SMP
+	/*
+	 * After ->oncpu is cleared, the task can be moved to a different CPU.
+	 * We must ensure this doesn't happen until the switch is completely
+	 * finished.
+	 */
+	smp_wmb();
+	prev->oncpu = 0;
+#endif
 #ifdef CONFIG_DEBUG_SPINLOCK
 	/* this is a valid case when another task releases the spinlock */
 	rq->lock.owner = current;
@@ -726,14 +747,6 @@ static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 }
 
 #else /* __ARCH_WANT_UNLOCKED_CTXSW */
-static inline int task_running(struct rq *rq, struct task_struct *p)
-{
-#ifdef CONFIG_SMP
-	return p->oncpu;
-#else
-	return task_current(rq, p);
-#endif
-}
 
 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 {
@@ -2082,7 +2095,7 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	if (likely(sched_info_on()))
 		memset(&p->sched_info, 0, sizeof(p->sched_info));
 #endif
-#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
+#if defined(CONFIG_SMP)
 	p->oncpu = 0;
 #endif
 #ifdef CONFIG_PREEMPT
@@ -5684,7 +5697,7 @@ void __cpuinit init_idle(struct task_struct *idle, int cpu)
 
 	spin_lock_irqsave(&rq->lock, flags);
 	rq->curr = rq->idle = idle;
-#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
+#if defined(CONFIG_SMP)
 	idle->oncpu = 1;
 #endif
 	spin_unlock_irqrestore(&rq->lock, flags);

[PATCH 3/5] rtmutex: use task->oncpu to save a call

[Gregory Haskins]

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

 kernel/rtmutex.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
index 8ae9de3..b6ff1eb 100644
--- a/kernel/rtmutex.c
+++ b/kernel/rtmutex.c
@@ -738,7 +738,7 @@ static int adaptive_wait(struct rt_mutex_waiter *waiter,
 		}
 
 		/* Owner went to bed, so should we */
-		if (!task_is_current(orig_owner)) {
+		if (!orig_owner->oncpu) {
 			sleep = 1;
 			rcu_read_unlock();
 			break;

[PATCH 4/5] adjust pi_lock usage in wakeup

[Gregory Haskins]

From: Peter W.Morreale <pmorreale@novell.com>

In wakeup_next_waiter(), we take the pi_lock, and then find out whether
we have another waiter to add to the pending owner.  We can reduce
contention on the pi_lock for the pending owner if we first obtain the
pointer to the next waiter outside of the pi_lock.

Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/rtmutex.c |   14 +++++++++-----
 1 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
index b6ff1eb..ec1f7d4 100644
--- a/kernel/rtmutex.c
+++ b/kernel/rtmutex.c
@@ -506,6 +506,7 @@ static void wakeup_next_waiter(struct rt_mutex *lock, int savestate)
 {
 	struct rt_mutex_waiter *waiter;
 	struct task_struct *pendowner;
+	struct rt_mutex_waiter *next;
 
 	spin_lock(&current->pi_lock);
 
@@ -568,6 +569,12 @@ static void wakeup_next_waiter(struct rt_mutex *lock, int savestate)
 	 * waiter with higher priority than pending-owner->normal_prio
 	 * is blocked on the unboosted (pending) owner.
 	 */
+
+	if (rt_mutex_has_waiters(lock))
+		next = rt_mutex_top_waiter(lock);
+	else
+		next = NULL;
+
 	spin_lock(&pendowner->pi_lock);
 
 	WARN_ON(!pendowner->pi_blocked_on);
@@ -576,12 +583,9 @@ static void wakeup_next_waiter(struct rt_mutex *lock, int savestate)
 
 	pendowner->pi_blocked_on = NULL;
 
-	if (rt_mutex_has_waiters(lock)) {
-		struct rt_mutex_waiter *next;
-
-		next = rt_mutex_top_waiter(lock);
+	if (next)
 		plist_add(&next->pi_list_entry, &pendowner->pi_waiters);
-	}
+
 	spin_unlock(&pendowner->pi_lock);
 }
 

[PATCH 5/5] remove the extra call to try_to_take_lock

[Gregory Haskins]

From: Peter W. Morreale <pmorreale@novell.com>

Remove the redundant attempt to get the lock.  While it is true that the
exit path with this patch adds an un-necessary xchg (in the event the
lock is granted without further traversal in the loop) experimentation
shows that we almost never encounter this situation.

Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/rtmutex.c |    6 ------
 1 files changed, 0 insertions(+), 6 deletions(-)

diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
index ec1f7d4..1da7813 100644
--- a/kernel/rtmutex.c
+++ b/kernel/rtmutex.c
@@ -785,12 +785,6 @@ rt_spin_lock_slowlock(struct rt_mutex *lock)
 	spin_lock_irqsave(&lock->wait_lock, flags);
 	init_lists(lock);
 
-	/* Try to acquire the lock again: */
-	if (do_try_to_take_rt_mutex(lock, STEAL_LATERAL)) {
-		spin_unlock_irqrestore(&lock->wait_lock, flags);
-		return;
-	}
-
 	BUG_ON(rt_mutex_owner(lock) == current);
 
 	/*

Re: [PATCH 5/5] remove the extra call to try_to_take_lock

[Steven Rostedt]

On Tue, 20 May 2008, Gregory Haskins wrote:

> From: Peter W. Morreale <pmorreale@novell.com>
>
> Remove the redundant attempt to get the lock.  While it is true that the
> exit path with this patch adds an un-necessary xchg (in the event the
> lock is granted without further traversal in the loop) experimentation
> shows that we almost never encounter this situation.
>
> Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
> Signed-off-by: Gregory Haskins <ghaskins@novell.com>
> ---
>
>  kernel/rtmutex.c |    6 ------
>  1 files changed, 0 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
> index ec1f7d4..1da7813 100644
> --- a/kernel/rtmutex.c
> +++ b/kernel/rtmutex.c
> @@ -785,12 +785,6 @@ rt_spin_lock_slowlock(struct rt_mutex *lock)
>  	spin_lock_irqsave(&lock->wait_lock, flags);
>  	init_lists(lock);
>
> -	/* Try to acquire the lock again: */
> -	if (do_try_to_take_rt_mutex(lock, STEAL_LATERAL)) {
> -		spin_unlock_irqrestore(&lock->wait_lock, flags);
> -		return;
> -	}
> -

This would suggested that lock stealing doesn't happen. On lock stealing,
this is the condition that is triggered and we have a nice quick exit.

-- Steve



>  	BUG_ON(rt_mutex_owner(lock) == current);
>
>  	/*
>

Re: [PATCH 5/5] remove the extra call to try_to_take_lock

[Gregory Haskins]

>>> On Fri, May 23, 2008 at 11:02 PM, in message
<Pine.LNX.4.58.0805232301080.12686@gandalf.stny.rr.com>, Steven Rostedt
<rostedt@goodmis.org> wrote: 

> On Tue, 20 May 2008, Gregory Haskins wrote:
> 
>> From: Peter W. Morreale <pmorreale@novell.com>
>>
>> Remove the redundant attempt to get the lock.  While it is true that the
>> exit path with this patch adds an un-necessary xchg (in the event the
>> lock is granted without further traversal in the loop) experimentation
>> shows that we almost never encounter this situation.
>>
>> Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
>> Signed-off-by: Gregory Haskins <ghaskins@novell.com>
>> ---
>>
>>  kernel/rtmutex.c |    6 ------
>>  1 files changed, 0 insertions(+), 6 deletions(-)
>>
>> diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
>> index ec1f7d4..1da7813 100644
>> --- a/kernel/rtmutex.c
>> +++ b/kernel/rtmutex.c
>> @@ -785,12 +785,6 @@ rt_spin_lock_slowlock(struct rt_mutex *lock)
>>  	spin_lock_irqsave(&lock->wait_lock, flags);
>>  	init_lists(lock);
>>
>> -	/* Try to acquire the lock again: */
>> -	if (do_try_to_take_rt_mutex(lock, STEAL_LATERAL)) {
>> -		spin_unlock_irqrestore(&lock->wait_lock, flags);
>> -		return;
>> -	}
>> -
> 
> This would suggested that lock stealing doesn't happen. On lock stealing,
> this is the condition that is triggered and we have a nice quick exit.

Its not that we are saying it doesn't happen.  Rather, we are saying the overhead of exiting from the second call (and only remaining call after this patch) is not as significant as it would seem on paper (based on empirical data).  In essence, it adds an xchg to the steal-case which is not "great", but....

..conversely, if the first test fails, the second test will *always* fail (since the lock->wait_lock is held across both).  This extra overhead actually *does* result in a measurable degradation of performance in our testing.

Another way to write the patch is to do more of a "do/while" style with the try_to_take is done later in the loop.  You could then retain the fast-path exit in that case.  I actually wrote a patch like that at one point, but I think Peter's here was faster.  I don't recall the reason why that was off the top of my head, but I remember I dropped my patch in favor of his because of the difference.

Regards,
-Greg

> 
> -- Steve
> 
> 
> 
>>  	BUG_ON(rt_mutex_owner(lock) == current);
>>
>>  	/*
>>

Re: [PATCH 5/5] remove the extra call to try_to_take_lock

[Peter W. Morreale]

On Fri, 2008-05-23 at 23:30 -0400, Gregory Haskins wrote:
> >>> On Fri, May 23, 2008 at 11:02 PM, in message
> <Pine.LNX.4.58.0805232301080.12686@gandalf.stny.rr.com>, Steven Rostedt
> <rostedt@goodmis.org> wrote: 
> 
> > On Tue, 20 May 2008, Gregory Haskins wrote:
> > 
> >> From: Peter W. Morreale <pmorreale@novell.com>
> >>
> >> Remove the redundant attempt to get the lock.  While it is true that the
> >> exit path with this patch adds an un-necessary xchg (in the event the
> >> lock is granted without further traversal in the loop) experimentation
> >> shows that we almost never encounter this situation.
> >>

I should have made this more descriptive to eliminate the confusion. 

Lock stealing, upon entry to *slowlock(), almost never happens.  By
almost I mean out of ~2+M locks, only 10s of locks were granted from the
original redundant attempt. (From manual instrumentation)  I do not have
exact numbers.

Best,
-PWM
   
> >> Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
> >> Signed-off-by: Gregory Haskins <ghaskins@novell.com>
> >> ---
> >>
> >>  kernel/rtmutex.c |    6 ------
> >>  1 files changed, 0 insertions(+), 6 deletions(-)
> >>
> >> diff --git a/kernel/rtmutex.c b/kernel/rtmutex.c
> >> index ec1f7d4..1da7813 100644
> >> --- a/kernel/rtmutex.c
> >> +++ b/kernel/rtmutex.c
> >> @@ -785,12 +785,6 @@ rt_spin_lock_slowlock(struct rt_mutex *lock)
> >>  	spin_lock_irqsave(&lock->wait_lock, flags);
> >>  	init_lists(lock);
> >>
> >> -	/* Try to acquire the lock again: */
> >> -	if (do_try_to_take_rt_mutex(lock, STEAL_LATERAL)) {
> >> -		spin_unlock_irqrestore(&lock->wait_lock, flags);
> >> -		return;
> >> -	}
> >> -
> > 
> > This would suggested that lock stealing doesn't happen. On lock stealing,
> > this is the condition that is triggered and we have a nice quick exit.
> 
> Its not that we are saying it doesn't happen.  Rather, we are saying the overhead of exiting from the second call (and only remaining call after this patch) is not as significant as it would seem on paper (based on empirical data).  In essence, it adds an xchg to the steal-case which is not "great", but....
> 
> ..conversely, if the first test fails, the second test will *always* fail (since the lock->wait_lock is held across both).  This extra overhead actually *does* result in a measurable degradation of performance in our testing.
> 
> Another way to write the patch is to do more of a "do/while" style with the try_to_take is done later in the loop.  You could then retain the fast-path exit in that case.  I actually wrote a patch like that at one point, but I think Peter's here was faster.  I don't recall the reason why that was off the top of my head, but I remember I dropped my patch in favor of his because of the difference.
> 
> Regards,
> -Greg
> 
> > 
> > -- Steve
> > 
> > 
> > 
> >>  	BUG_ON(rt_mutex_owner(lock) == current);
> >>
> >>  	/*
> >>
> 
>