[PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

change from v2 to v3
- the way to solve it in v2 is racy, so I changed the approach entirely.
- just make semaphore's trylock use spinlock's trylock.

change from v1 to v2
- remove unnecessary overhead by the redundant spin(un)lock.

Since I faced a infinite recursive printk() bug, I've tried to propose
patches the title of which is "lib/spinlock_debug.c: prevent a recursive
cycle in the debug code". But I noticed the root problem cannot be fixed
by that, through some discussion thanks to Sergey and Peter. So I focused
on preventing the deadlock.

-----8<-----
>From 43e029ca920890ac644e30d873be69cf5d01efdb Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park@lge.com>
Date: Wed, 17 Feb 2016 17:22:18 +0900
Subject: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

One of semaphore acquisition functions, down_trylock() is implemented
using raw_spin_lock_irqsave(&sem->lock) even though it's enough to use
raw_spin_trylock_irqsave(). Furthermore, using raw_spin_lock_irqsave()
can cause a unnecessary deadlock as described below. Just make it use
the spinlock trylock to implement the semaphore trylock so that we can
avoid the unnecessary deadlock happened.

The scenario the bad thing can happen is,

printk
  console_trylock
  console_unlock
    up_console_sem
      up
        raw_spin_lock_irqsave(&sem->lock, flags)
        __up
          wake_up_process
            try_to_wake_up
              raw_spin_lock_irqsave(&p->pi_lock)
                __spin_lock_debug
                  spin_dump
                    printk
                      console_trylock
                        raw_spin_lock_irqsave(&sem->lock, flags)
                        >>> DEADLOCK <<<

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/semaphore.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
index b8120ab..6634b68 100644
--- a/kernel/locking/semaphore.c
+++ b/kernel/locking/semaphore.c
@@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
 int down_trylock(struct semaphore *sem)
 {
 	unsigned long flags;
-	int count;
+	int count = -1;
 
-	raw_spin_lock_irqsave(&sem->lock, flags);
-	count = sem->count - 1;
-	if (likely(count >= 0))
-		sem->count = count;
-	raw_spin_unlock_irqrestore(&sem->lock, flags);
+	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
+		count = sem->count - 1;
+		if (likely(count >= 0))
+			sem->count = count;
+		raw_spin_unlock_irqrestore(&sem->lock, flags);
+	}
 
 	return (count < 0);
 }
-- 
1.9.1

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Ingo Molnar]

* Byungchul Park <byungchul.park@lge.com> wrote:

> diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
> index b8120ab..6634b68 100644
> --- a/kernel/locking/semaphore.c
> +++ b/kernel/locking/semaphore.c
> @@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
>  int down_trylock(struct semaphore *sem)
>  {
>  	unsigned long flags;
> -	int count;
> +	int count = -1;
>  
> -	raw_spin_lock_irqsave(&sem->lock, flags);
> -	count = sem->count - 1;
> -	if (likely(count >= 0))
> -		sem->count = count;
> -	raw_spin_unlock_irqrestore(&sem->lock, flags);
> +	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
> +		count = sem->count - 1;
> +		if (likely(count >= 0))
> +			sem->count = count;
> +		raw_spin_unlock_irqrestore(&sem->lock, flags);
> +	}

I still don't really like it: two parallel trylocks will cause one of them to fail 
- while with the previous code they would both succeed.

None of these changes are necessary with all the printk robustification 
changes/enhancements we talked about, right?

Thanks,

	Ingo

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Peter Zijlstra]

On Wed, Feb 17, 2016 at 06:11:51PM +0900, Byungchul Park wrote:
> change from v2 to v3
> - the way to solve it in v2 is racy, so I changed the approach entirely.
> - just make semaphore's trylock use spinlock's trylock.
> 
> change from v1 to v2
> - remove unnecessary overhead by the redundant spin(un)lock.
> 
> Since I faced a infinite recursive printk() bug, I've tried to propose
> patches the title of which is "lib/spinlock_debug.c: prevent a recursive
> cycle in the debug code". But I noticed the root problem cannot be fixed
> by that, through some discussion thanks to Sergey and Peter. So I focused
> on preventing the deadlock.
> 
> -----8<-----
> From 43e029ca920890ac644e30d873be69cf5d01efdb Mon Sep 17 00:00:00 2001
> From: Byungchul Park <byungchul.park@lge.com>
> Date: Wed, 17 Feb 2016 17:22:18 +0900
> Subject: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()
> 
> One of semaphore acquisition functions, down_trylock() is implemented
> using raw_spin_lock_irqsave(&sem->lock) even though it's enough to use
> raw_spin_trylock_irqsave(). Furthermore, using raw_spin_lock_irqsave()
> can cause a unnecessary deadlock as described below. Just make it use
> the spinlock trylock to implement the semaphore trylock so that we can
> avoid the unnecessary deadlock happened.
> 
> The scenario the bad thing can happen is,
> 
> printk
>   console_trylock
>   console_unlock
>     up_console_sem
>       up
>         raw_spin_lock_irqsave(&sem->lock, flags)
>         __up
>           wake_up_process
>             try_to_wake_up
>               raw_spin_lock_irqsave(&p->pi_lock)
>                 __spin_lock_debug
>                   spin_dump
>                     printk
>                       console_trylock
>                         raw_spin_lock_irqsave(&sem->lock, flags)
>                         >>> DEADLOCK <<<
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>

Mucking with the semaphore implementation just because printk() is
terminally broken shite really doesn't fly.

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

On Wed, Feb 17, 2016 at 10:28:29AM +0100, Ingo Molnar wrote:
> 
> * Byungchul Park <byungchul.park@lge.com> wrote:
> 
> > diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
> > index b8120ab..6634b68 100644
> > --- a/kernel/locking/semaphore.c
> > +++ b/kernel/locking/semaphore.c
> > @@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
> >  int down_trylock(struct semaphore *sem)
> >  {
> >  	unsigned long flags;
> > -	int count;
> > +	int count = -1;
> >  
> > -	raw_spin_lock_irqsave(&sem->lock, flags);
> > -	count = sem->count - 1;
> > -	if (likely(count >= 0))
> > -		sem->count = count;
> > -	raw_spin_unlock_irqrestore(&sem->lock, flags);
> > +	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
> > +		count = sem->count - 1;
> > +		if (likely(count >= 0))
> > +			sem->count = count;
> > +		raw_spin_unlock_irqrestore(&sem->lock, flags);
> > +	}
> 
> I still don't really like it: two parallel trylocks will cause one of them to fail 
> - while with the previous code they would both succeed.
> 
> None of these changes are necessary with all the printk robustification 
> changes/enhancements we talked about, right?

Right. I expect that Jan's patch which Sergey informed can make printk
robuster. Actually I'm waiting for the patch done. And I thought that it's
also a problem that a trylock implementation can make a system deadlock.
Don't you think it need to make a trylock only either acquire or fail in
any case? IMHO, waiting something within trylock is wrong. I'm just
curious.

Thanks,
Byungchul

> 
> Thanks,
> 
> 	Ingo

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

On Wed, Feb 17, 2016 at 11:40:49AM +0100, Peter Zijlstra wrote:
> Mucking with the semaphore implementation just because printk() is
> terminally broken shite really doesn't fly.

Jan is currently working on the terminally broken shite, and I expect it
makes printk() robuster. I just tried this patch because I though the
semaphore also need to be fixed and furthermore it can fix a deadlock by
removing the waiting within trylock. I think it's reasonable. Wrong?

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

On Wed, Feb 17, 2016 at 10:28:29AM +0100, Ingo Molnar wrote:
> 
> * Byungchul Park <byungchul.park@lge.com> wrote:
> 
> > diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
> > index b8120ab..6634b68 100644
> > --- a/kernel/locking/semaphore.c
> > +++ b/kernel/locking/semaphore.c
> > @@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
> >  int down_trylock(struct semaphore *sem)
> >  {
> >  	unsigned long flags;
> > -	int count;
> > +	int count = -1;
> >  
> > -	raw_spin_lock_irqsave(&sem->lock, flags);
> > -	count = sem->count - 1;
> > -	if (likely(count >= 0))
> > -		sem->count = count;
> > -	raw_spin_unlock_irqrestore(&sem->lock, flags);
> > +	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
> > +		count = sem->count - 1;
> > +		if (likely(count >= 0))
> > +			sem->count = count;
> > +		raw_spin_unlock_irqrestore(&sem->lock, flags);
> > +	}
> 
> I still don't really like it: two parallel trylocks will cause one of them to fail 
> - while with the previous code they would both succeed.
> 
> None of these changes are necessary with all the printk robustification 
> changes/enhancements we talked about, right?

Not only printk() but any code using a semaphore, mutex and so on, can also
cause a deadlock if wake_up_process() eventually tries to acquire the lock.
There are several ways to solve this problem.

1. ensure wake_up_process() does not try to acquire the locks.
2. ensure wake_up_process() isn't protected by a spinlock of the locks.
3. ensure any kind of trylock stuff never cause waiting and deadlock.
4. and so on..

I am not sure which one is the best. But I think 3rd one is the one since
it can be done by a generic way, even though it might decrease the success
ratio as Ingo said, but IMHO it's not a big problem since a trylock user 
only uses the trylock when it doesn't need to be cared whether it succeed
or fail.

Which one among those do you think the best approach? Please let me know,
then I will try to solve this problem by the appoach.

> 
> Thanks,
> 
> 	Ingo

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

On Wed, Mar 09, 2016 at 11:00:37AM +0900, Byungchul Park wrote:
> On Wed, Feb 17, 2016 at 10:28:29AM +0100, Ingo Molnar wrote:
> > 
> > * Byungchul Park <byungchul.park@lge.com> wrote:
> > 
> > > diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
> > > index b8120ab..6634b68 100644
> > > --- a/kernel/locking/semaphore.c
> > > +++ b/kernel/locking/semaphore.c
> > > @@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
> > >  int down_trylock(struct semaphore *sem)
> > >  {
> > >  	unsigned long flags;
> > > -	int count;
> > > +	int count = -1;
> > >  
> > > -	raw_spin_lock_irqsave(&sem->lock, flags);
> > > -	count = sem->count - 1;
> > > -	if (likely(count >= 0))
> > > -		sem->count = count;
> > > -	raw_spin_unlock_irqrestore(&sem->lock, flags);
> > > +	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
> > > +		count = sem->count - 1;
> > > +		if (likely(count >= 0))
> > > +			sem->count = count;
> > > +		raw_spin_unlock_irqrestore(&sem->lock, flags);
> > > +	}
> > 
> > I still don't really like it: two parallel trylocks will cause one of them to fail 
> > - while with the previous code they would both succeed.
> > 
> > None of these changes are necessary with all the printk robustification 
> > changes/enhancements we talked about, right?
> 
> Not only printk() but any code using a semaphore, mutex and so on, can also
> cause a deadlock if wake_up_process() eventually tries to acquire the lock.
> There are several ways to solve this problem.
> 
> 1. ensure wake_up_process() does not try to acquire the locks.
> 2. ensure wake_up_process() isn't protected by a spinlock of the locks.
> 3. ensure any kind of trylock stuff never cause waiting and deadlock.
> 4. and so on..
> 
> I am not sure which one is the best. But I think 3rd one is the one since
> it can be done by a generic way, even though it might decrease the success
> ratio as Ingo said, but IMHO it's not a big problem since a trylock user 
> only uses the trylock when it doesn't need to be cared whether it succeed
> or fail.
> 
> Which one among those do you think the best approach? Please let me know,
> then I will try to solve this problem by the appoach.

Or what do you think about this approach in which I replace the semaphore
with mutex and apply this patch to mutex trylock? Since the parallelism
does not mean that much to mutex trylock.. Right?

> 
> > 
> > Thanks,
> > 
> > 	Ingo

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

On Wed, Mar 09, 2016 at 03:07:01PM +0900, Byungchul Park wrote:
> On Wed, Mar 09, 2016 at 11:00:37AM +0900, Byungchul Park wrote:
> > On Wed, Feb 17, 2016 at 10:28:29AM +0100, Ingo Molnar wrote:
> > > 
> > > * Byungchul Park <byungchul.park@lge.com> wrote:
> > > 
> > > > diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
> > > > index b8120ab..6634b68 100644
> > > > --- a/kernel/locking/semaphore.c
> > > > +++ b/kernel/locking/semaphore.c
> > > > @@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
> > > >  int down_trylock(struct semaphore *sem)
> > > >  {
> > > >  	unsigned long flags;
> > > > -	int count;
> > > > +	int count = -1;
> > > >  
> > > > -	raw_spin_lock_irqsave(&sem->lock, flags);
> > > > -	count = sem->count - 1;
> > > > -	if (likely(count >= 0))
> > > > -		sem->count = count;
> > > > -	raw_spin_unlock_irqrestore(&sem->lock, flags);
> > > > +	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
> > > > +		count = sem->count - 1;
> > > > +		if (likely(count >= 0))
> > > > +			sem->count = count;
> > > > +		raw_spin_unlock_irqrestore(&sem->lock, flags);
> > > > +	}
> > > 
> > > I still don't really like it: two parallel trylocks will cause one of them to fail 
> > > - while with the previous code they would both succeed.
> > > 
> > > None of these changes are necessary with all the printk robustification 
> > > changes/enhancements we talked about, right?
> > 
> > Not only printk() but any code using a semaphore, mutex and so on, can also
> > cause a deadlock if wake_up_process() eventually tries to acquire the lock.
> > There are several ways to solve this problem.
> > 
> > 1. ensure wake_up_process() does not try to acquire the locks.
> > 2. ensure wake_up_process() isn't protected by a spinlock of the locks.
> > 3. ensure any kind of trylock stuff never cause waiting and deadlock.
> > 4. and so on..
> > 
> > I am not sure which one is the best. But I think 3rd one is the one since
> > it can be done by a generic way, even though it might decrease the success
> > ratio as Ingo said, but IMHO it's not a big problem since a trylock user 
> > only uses the trylock when it doesn't need to be cared whether it succeed
> > or fail.
> > 
> > Which one among those do you think the best approach? Please let me know,
> > then I will try to solve this problem by the appoach.
> 
> Or what do you think about this approach in which I replace the semaphore
> with mutex and apply this patch to mutex trylock? Since the parallelism
> does not mean that much to mutex trylock.. Right?

I am sorry for bothering you. I found that mutex trylock can be used in
interrupt context. Let me think more.

> 
> > 
> > > 
> > > Thanks,
> > > 
> > > 	Ingo

Re: [PATCH v3] lock/semaphore: Avoid an unnecessary deadlock within up()

[Byungchul Park]

On Thu, Mar 10, 2016 at 09:38:34AM +0900, Byungchul Park wrote:
> On Wed, Mar 09, 2016 at 03:07:01PM +0900, Byungchul Park wrote:
> > On Wed, Mar 09, 2016 at 11:00:37AM +0900, Byungchul Park wrote:
> > > On Wed, Feb 17, 2016 at 10:28:29AM +0100, Ingo Molnar wrote:
> > > > 
> > > > * Byungchul Park <byungchul.park@lge.com> wrote:
> > > > 
> > > > > diff --git a/kernel/locking/semaphore.c b/kernel/locking/semaphore.c
> > > > > index b8120ab..6634b68 100644
> > > > > --- a/kernel/locking/semaphore.c
> > > > > +++ b/kernel/locking/semaphore.c
> > > > > @@ -130,13 +130,14 @@ EXPORT_SYMBOL(down_killable);
> > > > >  int down_trylock(struct semaphore *sem)
> > > > >  {
> > > > >  	unsigned long flags;
> > > > > -	int count;
> > > > > +	int count = -1;
> > > > >  
> > > > > -	raw_spin_lock_irqsave(&sem->lock, flags);
> > > > > -	count = sem->count - 1;
> > > > > -	if (likely(count >= 0))
> > > > > -		sem->count = count;
> > > > > -	raw_spin_unlock_irqrestore(&sem->lock, flags);
> > > > > +	if (raw_spin_trylock_irqsave(&sem->lock, flags)) {
> > > > > +		count = sem->count - 1;
> > > > > +		if (likely(count >= 0))
> > > > > +			sem->count = count;
> > > > > +		raw_spin_unlock_irqrestore(&sem->lock, flags);
> > > > > +	}
> > > > 
> > > > I still don't really like it: two parallel trylocks will cause one of them to fail 
> > > > - while with the previous code they would both succeed.
> > > > 
> > > > None of these changes are necessary with all the printk robustification 
> > > > changes/enhancements we talked about, right?
> > > 
> > > Not only printk() but any code using a semaphore, mutex and so on, can also
> > > cause a deadlock if wake_up_process() eventually tries to acquire the lock.
> > > There are several ways to solve this problem.
> > > 
> > > 1. ensure wake_up_process() does not try to acquire the locks.
> > > 2. ensure wake_up_process() isn't protected by a spinlock of the locks.
> > > 3. ensure any kind of trylock stuff never cause waiting and deadlock.
> > > 4. and so on..
> > > 
> > > I am not sure which one is the best. But I think 3rd one is the one since
> > > it can be done by a generic way, even though it might decrease the success
> > > ratio as Ingo said, but IMHO it's not a big problem since a trylock user 
> > > only uses the trylock when it doesn't need to be cared whether it succeed
> > > or fail.
> > > 
> > > Which one among those do you think the best approach? Please let me know,
> > > then I will try to solve this problem by the appoach.
> > 
> > Or what do you think about this approach in which I replace the semaphore
> > with mutex and apply this patch to mutex trylock? Since the parallelism
> > does not mean that much to mutex trylock.. Right?
> 
> I am sorry for bothering you. I found that mutex trylock can be used in
                                                           ^^^
                                                           cannot
> interrupt context. Let me think more.
> 
> > 
> > > 
> > > > 
> > > > Thanks,
> > > > 
> > > > 	Ingo