[PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Oleg Nesterov]

It is a bit annoying that do_exit() takes ->pi_lock to set PF_EXITING.
All we need is to synchronize with lookup_pi_state() which saw this task
without PF_EXITING under ->pi_lock.

Change do_exit() to use spin_unlock_wait().

Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>

--- t/kernel/exit.c~PF_EXIT	2007-06-19 17:09:15.000000000 +0400
+++ t/kernel/exit.c	2007-07-21 15:34:13.000000000 +0400
@@ -908,13 +908,13 @@ fastcall NORET_TYPE void do_exit(long co
 		schedule();
 	}
 
+	tsk->flags |= PF_EXITING;
 	/*
 	 * tsk->flags are checked in the futex code to protect against
 	 * an exiting task cleaning up the robust pi futexes.
 	 */
-	spin_lock_irq(&tsk->pi_lock);
-	tsk->flags |= PF_EXITING;
-	spin_unlock_irq(&tsk->pi_lock);
+	smp_mb();
+	spin_unlock_wait(&tsk->pi_lock);
 
 	if (unlikely(in_atomic()))
 		printk(KERN_INFO "note: %s[%d] exited with preempt_count %d\n",

Re: [PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Ingo Molnar]

* Oleg Nesterov <oleg@tv-sign.ru> wrote:

> It is a bit annoying that do_exit() takes ->pi_lock to set PF_EXITING.
> All we need is to synchronize with lookup_pi_state() which saw this task
> without PF_EXITING under ->pi_lock.
> 
> Change do_exit() to use spin_unlock_wait().
> 
> Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>

Acked-by: Ingo Molnar <mingo@elte.hu>

> -	spin_lock_irq(&tsk->pi_lock);
> -	tsk->flags |= PF_EXITING;
> -	spin_unlock_irq(&tsk->pi_lock);
> +	smp_mb();
> +	spin_unlock_wait(&tsk->pi_lock);

hm, isnt spin_unlock_wait() an SMP barrier in itself? (if not then it 
should be.)

	Ingo

Re: [PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Oleg Nesterov]

On 07/21, Ingo Molnar wrote:
> 
> * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > It is a bit annoying that do_exit() takes ->pi_lock to set PF_EXITING.
> > All we need is to synchronize with lookup_pi_state() which saw this task
> > without PF_EXITING under ->pi_lock.
> > 
> > Change do_exit() to use spin_unlock_wait().
> > 
> > Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> 
> Acked-by: Ingo Molnar <mingo@elte.hu>

Thanks!

> > -	spin_lock_irq(&tsk->pi_lock);
> > -	tsk->flags |= PF_EXITING;
> > -	spin_unlock_irq(&tsk->pi_lock);
> > +	smp_mb();
> > +	spin_unlock_wait(&tsk->pi_lock);
> 
> hm, isnt spin_unlock_wait() an SMP barrier in itself?

no, only barrier() due to cpu_relax()

> (if not then it should be.)

I think you are right, I can't imagine a valid usage of spin_unlock_wait()
without a barrier.

For example, from net/dccp/ccid.c

	static void ccids_write_lock(void)
	{
		spin_lock(&ccids_lock);
		while (atomic_read(&ccids_lockct) != 0) {
			spin_unlock(&ccids_lock);
			yield();
			spin_lock(&ccids_lock);
		}
	}

	static inline void ccids_read_lock(void)
	{
		atomic_inc(&ccids_lockct);
		spin_unlock_wait(&ccids_lock);
	}

This looks racy, in theory atomic_inc() and spin_unlock_wait() could be
re-ordered. However, in this particular case we have an "optimized"
smp_mb_after_atomic_inc(), perhaps it is good that the caller can choose
the "right" barrier by hand.

Oleg.

[PATCH] fix theoretical ccids_{read,write}_lock() race

[Oleg Nesterov]

Make sure that spin_unlock_wait() is properly ordered wrt atomic_inc().

Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>

--- t/net/dccp/ccid.c~ccid	2006-12-18 18:17:31.000000000 +0300
+++ t/net/dccp/ccid.c	2007-07-21 18:29:21.000000000 +0400
@@ -40,6 +40,7 @@ static inline void ccids_write_unlock(vo
 static inline void ccids_read_lock(void)
 {
 	atomic_inc(&ccids_lockct);
+	smp_mb__after_atomic_inc();
 	spin_unlock_wait(&ccids_lock);
 }
 

Re: [PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Ingo Molnar]

* Oleg Nesterov <oleg@tv-sign.ru> wrote:

> 	static inline void ccids_read_lock(void)
> 	{
> 		atomic_inc(&ccids_lockct);
> 		spin_unlock_wait(&ccids_lock);
> 	}
> 
> This looks racy, in theory atomic_inc() and spin_unlock_wait() could 
> be re-ordered. However, in this particular case we have an "optimized" 
> smp_mb_after_atomic_inc(), perhaps it is good that the caller can 
> choose the "right" barrier by hand.

_all_ default locking and atomic APIs should be barrier-safe i believe. 
(and that includes atomic_inc() too) Most people dont have barriers on 
their mind when their code. _If_ someone is barrier-conscious then we 
should have barrier-less APIs too for that purpose of squeezing the last 
half cycle out of the code, but it should be a non-default choice. The 
reason: nobody notices an unnecessary barrier, but a missing barrier can 
be nasty.

	Ingo

Re: [PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Oleg Nesterov]

On 07/21, Ingo Molnar wrote:
> 
> * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > 	static inline void ccids_read_lock(void)
> > 	{
> > 		atomic_inc(&ccids_lockct);
> > 		spin_unlock_wait(&ccids_lock);
> > 	}
> > 
> > This looks racy, in theory atomic_inc() and spin_unlock_wait() could 
> > be re-ordered. However, in this particular case we have an "optimized" 
> > smp_mb_after_atomic_inc(), perhaps it is good that the caller can 
> > choose the "right" barrier by hand.
> 
> _all_ default locking and atomic APIs should be barrier-safe i believe. 
> (and that includes atomic_inc() too) Most people dont have barriers on 
> their mind when their code. _If_ someone is barrier-conscious then we 
> should have barrier-less APIs too for that purpose of squeezing the last 
> half cycle out of the code, but it should be a non-default choice. The 
> reason: nobody notices an unnecessary barrier, but a missing barrier can 
> be nasty.

Personally, I agree (but I am not sure the idea to make atomic_inc()
barrier-safe would be very popular).

Question: should we make spinlock_t barrier-safe?

Suppose that the task "p" does

	current->state = TASK_INTERRUPIBLE;
	mb();

	if (CONDITION)
		break;

	schedule();

and another CPU does

	CONDITION = 1;
	try_to_wake_up(p);


This is commonly used, but not correct _in theory_. If wake_up() happens
when p->array != NULL, we have

	CONDITION = 1;			// [1]
	spin_lock(rq->lock);
	task->state = TASK_RUNNING;	// [2]

and we can miss an event. Because in theory [1] may leak into the critical
section, and could be re-ordered with [2].

Another problem is that try_to_wake_up() first checks task->state and does
nothing if it is TASK_RUNNING, so we need a full mb(), not just wmb().

Should we change spin_lock(), or introduce smp_mb_before_spinlock(), or I
missed something?

NOTE: I do not pretend to know what kind of barrier spin_lock() provides
in practice, but according to the documentation lock() is only a one-way
barrier.

(I am glad I have an opportunity to raise this issue again :)

Oleg.

Re: [PATCH] fix theoretical ccids_{read,write}_lock() race

[Andrew Morton]

On Sat, 21 Jul 2007 19:02:06 +0400 Oleg Nesterov <oleg@tv-sign.ru> wrote:

> Make sure that spin_unlock_wait() is properly ordered wrt atomic_inc().
> 
> Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> 
> --- t/net/dccp/ccid.c~ccid	2006-12-18 18:17:31.000000000 +0300
> +++ t/net/dccp/ccid.c	2007-07-21 18:29:21.000000000 +0400
> @@ -40,6 +40,7 @@ static inline void ccids_write_unlock(vo
>  static inline void ccids_read_lock(void)
>  {
>  	atomic_inc(&ccids_lockct);
> +	smp_mb__after_atomic_inc();
>  	spin_unlock_wait(&ccids_lock);
>  }
>  

Why not just use standard rwlocks in there?

(This is probably an FAQ, but it should be).

Re: [PATCH] fix theoretical ccids_{read,write}_lock() race

[Oleg Nesterov]

On 07/21, Andrew Morton wrote:
>
> On Sat, 21 Jul 2007 19:02:06 +0400 Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > Make sure that spin_unlock_wait() is properly ordered wrt atomic_inc().
> > 
> > Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> > 
> > --- t/net/dccp/ccid.c~ccid	2006-12-18 18:17:31.000000000 +0300
> > +++ t/net/dccp/ccid.c	2007-07-21 18:29:21.000000000 +0400
> > @@ -40,6 +40,7 @@ static inline void ccids_write_unlock(vo
> >  static inline void ccids_read_lock(void)
> >  {
> >  	atomic_inc(&ccids_lockct);
> > +	smp_mb__after_atomic_inc();
> >  	spin_unlock_wait(&ccids_lock);
> >  }
> >  
> 
> Why not just use standard rwlocks in there?
> 
> (This is probably an FAQ, but it should be).

Perhaps because read_lock() doesn't allow to sleep?

Oleg.

Re: [PATCH] fix theoretical ccids_{read,write}_lock() race

[Andrew Morton]

On Sat, 21 Jul 2007 23:11:04 +0400 Oleg Nesterov <oleg@tv-sign.ru> wrote:

> On 07/21, Andrew Morton wrote:
> >
> > On Sat, 21 Jul 2007 19:02:06 +0400 Oleg Nesterov <oleg@tv-sign.ru> wrote:
> > 
> > > Make sure that spin_unlock_wait() is properly ordered wrt atomic_inc().
> > > 
> > > Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> > > 
> > > --- t/net/dccp/ccid.c~ccid	2006-12-18 18:17:31.000000000 +0300
> > > +++ t/net/dccp/ccid.c	2007-07-21 18:29:21.000000000 +0400
> > > @@ -40,6 +40,7 @@ static inline void ccids_write_unlock(vo
> > >  static inline void ccids_read_lock(void)
> > >  {
> > >  	atomic_inc(&ccids_lockct);
> > > +	smp_mb__after_atomic_inc();
> > >  	spin_unlock_wait(&ccids_lock);
> > >  }
> > >  
> > 
> > Why not just use standard rwlocks in there?
> > 
> > (This is probably an FAQ, but it should be).
> 
> Perhaps because read_lock() doesn't allow to sleep?
> 

down_read() does.

afaict the code doesn't sleep while holding that lock anwyay.

Re: [PATCH] fix theoretical ccids_{read,write}_lock() race

[Oleg Nesterov]

On 07/21, Andrew Morton wrote:
>
> On Sat, 21 Jul 2007 23:11:04 +0400 Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > On 07/21, Andrew Morton wrote:
> > >
> > > On Sat, 21 Jul 2007 19:02:06 +0400 Oleg Nesterov <oleg@tv-sign.ru> wrote:
> > > 
> > > > Make sure that spin_unlock_wait() is properly ordered wrt atomic_inc().
> > > > 
> > > > Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> > > > 
> > > > --- t/net/dccp/ccid.c~ccid	2006-12-18 18:17:31.000000000 +0300
> > > > +++ t/net/dccp/ccid.c	2007-07-21 18:29:21.000000000 +0400
> > > > @@ -40,6 +40,7 @@ static inline void ccids_write_unlock(vo
> > > >  static inline void ccids_read_lock(void)
> > > >  {
> > > >  	atomic_inc(&ccids_lockct);
> > > > +	smp_mb__after_atomic_inc();
> > > >  	spin_unlock_wait(&ccids_lock);
> > > >  }
> > > >  
> > > 
> > > Why not just use standard rwlocks in there?
> > > 
> > > (This is probably an FAQ, but it should be).
> > 
> > Perhaps because read_lock() doesn't allow to sleep?
> > 
> 
> down_read() does.
> 
> afaict the code doesn't sleep while holding that lock anwyay.

Ah yes, it doesn't call kmem_cache_alloc() under ccids_read_lock().

So, really, why not read_lock/write_lock ?

Oleg.

Re: [PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Paul Mackerras]

Ingo Molnar writes:

> 
> * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > 	static inline void ccids_read_lock(void)
> > 	{
> > 		atomic_inc(&ccids_lockct);
> > 		spin_unlock_wait(&ccids_lock);
> > 	}
> > 
> > This looks racy, in theory atomic_inc() and spin_unlock_wait() could 
> > be re-ordered. However, in this particular case we have an "optimized" 
> > smp_mb_after_atomic_inc(), perhaps it is good that the caller can 
> > choose the "right" barrier by hand.
> 
> _all_ default locking and atomic APIs should be barrier-safe i believe. 
> (and that includes atomic_inc() too) Most people dont have barriers on 
> their mind when their code. _If_ someone is barrier-conscious then we 
> should have barrier-less APIs too for that purpose of squeezing the last 
> half cycle out of the code, but it should be a non-default choice. The 
> reason: nobody notices an unnecessary barrier, but a missing barrier can 
> be nasty.

The approach we have taken on powerpc is that the atomic_*_test and
atomic_*_return functions have a barrier, but the straight atomic_inc
etc. don't.

As for putting barriers in, it's not a half cycle, it's more like 50
to 100 on some processors.  Added to that, what I think you are
actually advocating is *two* full barriers - one before the increment
and one after.  That seems like an enormous penalty to pay just
because some people want to roll their own lock primitives instead of
using the standard ones.

Why is ccids_read_lock trying to implement a rwlock without using an
rwlock?  Could it be converted to an ordinary rwlock?  Or an rwsem?

Paul.

Re: [PATCH] pi-futex: set PF_EXITING without taking ->pi_lock

[Ingo Molnar]

* Oleg Nesterov <oleg@tv-sign.ru> wrote:

> Question: should we make spinlock_t barrier-safe?
> 
> Suppose that the task "p" does
> 
> 	current->state = TASK_INTERRUPIBLE;
> 	mb();
> 
> 	if (CONDITION)
> 		break;
> 
> 	schedule();
> 
> and another CPU does
> 
> 	CONDITION = 1;
> 	try_to_wake_up(p);
> 
> 
> This is commonly used, but not correct _in theory_. If wake_up() happens
> when p->array != NULL, we have
> 
> 	CONDITION = 1;			// [1]
> 	spin_lock(rq->lock);
> 	task->state = TASK_RUNNING;	// [2]
> 
> and we can miss an event. Because in theory [1] may leak into the critical
> section, and could be re-ordered with [2].
> 
> Another problem is that try_to_wake_up() first checks task->state and does
> nothing if it is TASK_RUNNING, so we need a full mb(), not just wmb().
> 
> Should we change spin_lock(), or introduce smp_mb_before_spinlock(), or I
> missed something?
> 
> NOTE: I do not pretend to know what kind of barrier spin_lock() provides
> in practice, but according to the documentation lock() is only a one-way
> barrier.

i think your worry is legitimate.

spin_lock() provides a full barrier on most platforms (certainly so on 
x86). But ... ia64 might have it as a one-way barrier?

	Ingo