[PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[Hillf Danton]

The dereference of unreliable owner pointer is unnecessary in owner_running(),
though under RCU protection, because the true result is only determined by
checking the validity of lock owner, as the comment says, due to likely heavy
lock contention, which has little to do with whether owner->on_cpu is false.

If owner->on_cpu is really false, only the owner_running loop is shortened,
but also returns incorrect result, since the lock owner is not changed, though
maybe changed soon.

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---
 kernel/sched.c |   36 +-----------------------------------
 1 files changed, 1 insertions(+), 35 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index fd18f39..2c32616 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -4293,52 +4293,18 @@ EXPORT_SYMBOL(schedule);

 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER

-static inline bool owner_running(struct mutex *lock, struct task_struct *owner)
-{
-	bool ret = false;
-
-	rcu_read_lock();
-	if (lock->owner != owner)
-		goto fail;
-
-	/*
-	 * Ensure we emit the owner->on_cpu, dereference _after_ checking
-	 * lock->owner still matches owner, if that fails, owner might
-	 * point to free()d memory, if it still matches, the rcu_read_lock()
-	 * ensures the memory stays valid.
-	 */
-	barrier();
-
-	ret = owner->on_cpu;
-fail:
-	rcu_read_unlock();
-
-	return ret;
-}
-
-/*
- * Look out! "owner" is an entirely speculative pointer
- * access and not reliable.
- */
 int mutex_spin_on_owner(struct mutex *lock, struct task_struct *owner)
 {
 	if (!sched_feat(OWNER_SPIN))
 		return 0;

-	while (owner_running(lock, owner)) {
+	while (lock->owner != NULL) {
 		if (need_resched())
 			return 0;

 		arch_mutex_cpu_relax();
 	}

-	/*
-	 * If the owner changed to another task there is likely
-	 * heavy contention, stop spinning.
-	 */
-	if (lock->owner)
-		return 0;
-
 	return 1;
 }
 #endif

Re: [PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[Steven Rostedt]

On Wed, Jun 08, 2011 at 08:49:53PM +0800, Hillf Danton wrote:
> The dereference of unreliable owner pointer is unnecessary in owner_running(),
> though under RCU protection, because the true result is only determined by
> checking the validity of lock owner, as the comment says, due to likely heavy
> lock contention, which has little to do with whether owner->on_cpu is false.
> 
> If owner->on_cpu is really false, only the owner_running loop is shortened,
> but also returns incorrect result, since the lock owner is not changed, though
> maybe changed soon.
> 

Hillf, have you read anything that I posted before?

We don't want to spin if the owner of the lock sleeps. If it sleeps,
then the owner's on_cpu will be zero. That's the point of checking it.

The patch you just added would devastate the performance of the system.
Now if we have contention on a lock, and the owner sleeps, we continue
to spin. If the spinner is an RT task, this could also cause a deadlock,
especially if the owner is bound to the same CPU that the RT task is on.

-- Steve


> Signed-off-by: Hillf Danton <dhillf@gmail.com>
> ---
>  kernel/sched.c |   36 +-----------------------------------
>  1 files changed, 1 insertions(+), 35 deletions(-)
> 
> diff --git a/kernel/sched.c b/kernel/sched.c
> index fd18f39..2c32616 100644
> --- a/kernel/sched.c
> +++ b/kernel/sched.c
> @@ -4293,52 +4293,18 @@ EXPORT_SYMBOL(schedule);
> 
>  #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
> 
> -static inline bool owner_running(struct mutex *lock, struct task_struct *owner)
> -{
> -	bool ret = false;
> -
> -	rcu_read_lock();
> -	if (lock->owner != owner)
> -		goto fail;
> -
> -	/*
> -	 * Ensure we emit the owner->on_cpu, dereference _after_ checking
> -	 * lock->owner still matches owner, if that fails, owner might
> -	 * point to free()d memory, if it still matches, the rcu_read_lock()
> -	 * ensures the memory stays valid.
> -	 */
> -	barrier();
> -
> -	ret = owner->on_cpu;
> -fail:
> -	rcu_read_unlock();
> -
> -	return ret;
> -}
> -
> -/*
> - * Look out! "owner" is an entirely speculative pointer
> - * access and not reliable.
> - */
>  int mutex_spin_on_owner(struct mutex *lock, struct task_struct *owner)
>  {
>  	if (!sched_feat(OWNER_SPIN))
>  		return 0;
> 
> -	while (owner_running(lock, owner)) {
> +	while (lock->owner != NULL) {
>  		if (need_resched())
>  			return 0;
> 
>  		arch_mutex_cpu_relax();
>  	}
> 
> -	/*
> -	 * If the owner changed to another task there is likely
> -	 * heavy contention, stop spinning.
> -	 */
> -	if (lock->owner)
> -		return 0;
> -
>  	return 1;
>  }
>  #endif
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[Hillf Danton]

On Wed, Jun 8, 2011 at 8:58 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Wed, Jun 08, 2011 at 08:49:53PM +0800, Hillf Danton wrote:
>> The dereference of unreliable owner pointer is unnecessary in owner_running(),
>> though under RCU protection, because the true result is only determined by
>> checking the validity of lock owner, as the comment says, due to likely heavy
>> lock contention, which has little to do with whether owner->on_cpu is false.
>>
>> If owner->on_cpu is really false, only the owner_running loop is shortened,
>> but also returns incorrect result, since the lock owner is not changed, though
>> maybe changed soon.
>>
>
> Hillf, have you read anything that I posted before?
>

I have, but

> We don't want to spin if the owner of the lock sleeps. If it sleeps,
> then the owner's on_cpu will be zero. That's the point of checking it.
>
not understand the point of checking owner->on_cpu, and the code's
icy beauty blows me down again.

Please thaw another hard to understand in rt_mutex_setprio(),


	if (running)
		p->sched_class->set_curr_task(rq);
	if (on_rq)
-		enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
+		enqueue_task(rq, p, oldprio > prio ? ENQUEUE_HEAD : 0);

	check_class_changed(rq, p, prev_class, oldprio);


thanks
            Hillf

> The patch you just added would devastate the performance of the system.
> Now if we have contention on a lock, and the owner sleeps, we continue
> to spin. If the spinner is an RT task, this could also cause a deadlock,
> especially if the owner is bound to the same CPU that the RT task is on.
>
> -- Steve

Re: [PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[Steven Rostedt]

On Wed, 2011-06-08 at 21:28 +0800, Hillf Danton wrote:

> > We don't want to spin if the owner of the lock sleeps. If it sleeps,
> > then the owner's on_cpu will be zero. That's the point of checking it.
> >
> not understand the point of checking owner->on_cpu, and the code's
> icy beauty blows me down again.

It's better to ask these questions than to send patches. You can send
code changes like below, with a question. But avoid official patches if
you don't understand why the code does what it does. An official patch
(with [PATCH] in subject and a Signed-off-by) states that you basically
know what you are doing, and it will frustrate maintainers if you do
not.

Now, I'll explain the owner->on_cpu.

When a task is running, it's on_cpu (in task_struct) is set to 1. When
it is scheduled away, it is zero. This is important.

A mutex is a lock that a task will schedule out in a sleep state if
there's contention. And the owner will wake up that task when it
releases the lock. This is the basic method of mutexes. But the problem
is, it can be very expensive, especially, if the mutexes are held for a
short period of time.

What happens then, is when there is contention, a process will start to
schedule out, and then be woken up again. But we already went into the
scheduler, and may have even scheduled another task. This can be very
expensive, especially if we flush the TLB in the mean time.

What this code does is to try not to sleep. But we need to very careful
in doing this, because the code that uses the mutex expects that this
may sleep. So, instead of just scheduling away when there's contention,
the task checks if the owner is running on another CPU. If it is, then
there's a good chance that it will soon release the mutex and we can
grab it. Instead of scheduling away, this task now waits and spins,
waiting for the owner to release the mutex. This now acts like the more
efficient (but limited) spin locks.

Because we are now spinning, we must be very careful, as the code that
uses the mutex is not made to handle spinners. The spinning must stop
under certain circumstances. One is, if the task that is spinning should
give up the CPU (which is why we check NEED_RESCEHD for current).

The other time to stop spinning is if the owner of the mutex is no
longer running on the CPU. That is, the owner scheduled away. If the
owner scheduled away, then there's no reason to spin anymore, and it
will be better schedule away the task instead. Why spin? The owner may
not wake up for a long time. No need to wait anymore.

> 
> Please thaw another hard to understand in rt_mutex_setprio(),
> 
> 
> 	if (running)
> 		p->sched_class->set_curr_task(rq);
> 	if (on_rq)
> -		enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
> +		enqueue_task(rq, p, oldprio > prio ? ENQUEUE_HEAD : 0);
> 
> 	check_class_changed(rq, p, prev_class, oldprio);
> 

Now this is a confusing part of the kernel. It still confuses me
sometimes :)

The kernel looks at priorities opposite of how userspace does. In the
kernel, task->prio, the lower the number the higher the priority.

Now the above compares the oldprio with the (new) prio. If the oldprio
is less than the new prio, we just lowered our priority. But because we
were originally a high priority task, we go at the head of the queue.
Now if we upped, our priority, we have no right in jumping ahead of
other tasks of that same priority, so we go to the end of the queue.

Got it?

-- Steve

Re: [PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[Hillf Danton]

On Wed, Jun 8, 2011 at 10:57 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Wed, 2011-06-08 at 21:28 +0800, Hillf Danton wrote:
>
>> > We don't want to spin if the owner of the lock sleeps. If it sleeps,
>> > then the owner's on_cpu will be zero. That's the point of checking it.
>> >
>> not understand the point of checking owner->on_cpu, and the code's
>> icy beauty blows me down again.
>
> It's better to ask these questions than to send patches. You can send
> code changes like below, with a question. But avoid official patches if
> you don't understand why the code does what it does. An official patch
> (with [PATCH] in subject and a Signed-off-by) states that you basically
> know what you are doing, and it will frustrate maintainers if you do
> not.
>
> Now, I'll explain the owner->on_cpu.
>
> When a task is running, it's on_cpu (in task_struct) is set to 1. When
> it is scheduled away, it is zero. This is important.
>
> A mutex is a lock that a task will schedule out in a sleep state if
> there's contention. And the owner will wake up that task when it
> releases the lock. This is the basic method of mutexes. But the problem
> is, it can be very expensive, especially, if the mutexes are held for a
> short period of time.
>
> What happens then, is when there is contention, a process will start to
> schedule out, and then be woken up again. But we already went into the
> scheduler, and may have even scheduled another task. This can be very
> expensive, especially if we flush the TLB in the mean time.
>
> What this code does is to try not to sleep. But we need to very careful
> in doing this, because the code that uses the mutex expects that this
> may sleep. So, instead of just scheduling away when there's contention,
> the task checks if the owner is running on another CPU. If it is, then
> there's a good chance that it will soon release the mutex and we can
> grab it. Instead of scheduling away, this task now waits and spins,
> waiting for the owner to release the mutex. This now acts like the more
> efficient (but limited) spin locks.
>
> Because we are now spinning, we must be very careful, as the code that
> uses the mutex is not made to handle spinners. The spinning must stop
> under certain circumstances. One is, if the task that is spinning should
> give up the CPU (which is why we check NEED_RESCEHD for current).
>
> The other time to stop spinning is if the owner of the mutex is no
> longer running on the CPU. That is, the owner scheduled away. If the
> owner scheduled away, then there's no reason to spin anymore, and it
> will be better schedule away the task instead. Why spin? The owner may
> not wake up for a long time. No need to wait anymore.
>
> Got it?
>

Got, a lot thanks.

Unlike spinner and owner that are well considered, there are waiters, please
see the following homework.

Another question about CONFIG_MUTEX_SPIN_ON_OWNER, from the view angle of
spinners, as you mentioned above, looks like that they are crowding on a bus
as violently as they could, in contrast to the Japanese people in earthquake.

Then the result could be, out of our image, not as optimistic as it is, since
a thread of lower priority could out-compete another of higher priority,
when a bunch of spinners are simultaneously trying hard to acquire the mutex,
though only one is allowed to get award.

thanks   /Hillf
---
 kernel/mutex.c |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/kernel/mutex.c b/kernel/mutex.c
index d607ed5..3a5606c 100644
--- a/kernel/mutex.c
+++ b/kernel/mutex.c
@@ -162,6 +162,10 @@ __mutex_lock_common(struct mutex *lock, long
state, unsigned int subclass,
 	for (;;) {
 		struct task_struct *owner;

+		/* skip over spin if there are pending waiters */
+		if (atomic_cmpxchg(&lock->count, -1, -1) == -1)
+			break;
+
 		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.

Re: [PATCH] sched: remove unreliable pointer in mutex_spin_on_owner()

[Steven Rostedt]

On Sat, 2011-06-11 at 22:37 +0800, Hillf Danton wrote:

> Unlike spinner and owner that are well considered, there are waiters, please
> see the following homework.
> 
> Another question about CONFIG_MUTEX_SPIN_ON_OWNER, from the view angle of
> spinners, as you mentioned above, looks like that they are crowding on a bus
> as violently as they could, in contrast to the Japanese people in earthquake.
> 
> Then the result could be, out of our image, not as optimistic as it is, since
> a thread of lower priority could out-compete another of higher priority,
> when a bunch of spinners are simultaneously trying hard to acquire the mutex,
> though only one is allowed to get award.

Note, we don't care about priorities here. If you care about that, then
use the -rt patched kernel and enable "PREEMPT_RT". Because that changes
the mutex code to be priority driven (uses rt_mutex instead of mutex).
In a year or two (or three ;) the -rt patch will be part of the kernel
and you will be able to get these things for free.

-- Steve