[PATCH] locks: ignore same lock in blocked_lock_hash

[PATCH] locks: ignore same lock in blocked_lock_hash

[Jeff Layton]

Andreas reported that he was seeing the tdbtorture test fail in
some cases with -EDEADLCK when it wasn't before. Some debugging
showed that deadlock detection was sometimes discovering the
caller's lock request itself in a dependency chain.

If posix_locks_deadlock() fails to find a deadlock, the caller_fl
will be passed to __locks_insert_block(), and this wakes up all
locks that are blocked on caller_fl, clearing the fl_blocker link.

So if posix_locks_deadlock() finds caller_fl while searching for
a deadlock, it can be sure that link in the cycle is about to be
broken and it need not treat it as the cause of a deadlock.

More details here: https://bugzilla.kernel.org/show_bug.cgi?id=202975

Cc: stable@vger.kernel.org
Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
Reported-by: Andreas Schneider <asn@redhat.com>
Signed-off-by: Neil Brown <neilb@suse.com>
Signed-off-by: Jeff Layton <jlayton@kernel.org>
---
 fs/locks.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/fs/locks.c b/fs/locks.c
index eaa1cfaf73b0..b074f6d7fd2d 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -1023,6 +1023,10 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
 	while ((block_fl = what_owner_is_waiting_for(block_fl))) {
 		if (i++ > MAX_DEADLK_ITERATIONS)
 			return 0;
+
+		if (caller_fl == block_fl)
+			return 0;
+
 		if (posix_same_owner(caller_fl, block_fl))
 			return 1;
 	}
-- 
2.20.1

Re: [PATCH] locks: ignore same lock in blocked_lock_hash

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 2063 bytes --]

On Thu, Mar 21 2019, Jeff Layton wrote:

> Andreas reported that he was seeing the tdbtorture test fail in
> some cases with -EDEADLCK when it wasn't before. Some debugging
> showed that deadlock detection was sometimes discovering the
> caller's lock request itself in a dependency chain.
>
> If posix_locks_deadlock() fails to find a deadlock, the caller_fl
> will be passed to __locks_insert_block(), and this wakes up all
> locks that are blocked on caller_fl, clearing the fl_blocker link.
>
> So if posix_locks_deadlock() finds caller_fl while searching for
> a deadlock, it can be sure that link in the cycle is about to be
> broken and it need not treat it as the cause of a deadlock.
>
> More details here: https://bugzilla.kernel.org/show_bug.cgi?id=202975

There is a weak pattern of using

URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975

>
> Cc: stable@vger.kernel.org
> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> Reported-by: Andreas Schneider <asn@redhat.com>
> Signed-off-by: Neil Brown <neilb@suse.com>
> Signed-off-by: Jeff Layton <jlayton@kernel.org>
> ---
>  fs/locks.c | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/fs/locks.c b/fs/locks.c
> index eaa1cfaf73b0..b074f6d7fd2d 100644
> --- a/fs/locks.c
> +++ b/fs/locks.c
> @@ -1023,6 +1023,10 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
>  	while ((block_fl = what_owner_is_waiting_for(block_fl))) {
>  		if (i++ > MAX_DEADLK_ITERATIONS)
>  			return 0;
> +
> +		if (caller_fl == block_fl)
> +			return 0;
> +

I would always write this with the value being tested first, and the
value it is being tested against second (and yes, I know that equality
is mathematically symmetric).

 if (block_fl == caller_fl)
    return 0;

But .... whatever.  At least your ordering matches the
posix_same_owner() below, and consistency is a good thing too.

Thanks,
NeilBrown


>  		if (posix_same_owner(caller_fl, block_fl))
>  			return 1;
>  	}
> -- 
> 2.20.1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] locks: ignore same lock in blocked_lock_hash

[J. Bruce Fields]

On Thu, Mar 21, 2019 at 07:27:44AM -0400, Jeff Layton wrote:
> Andreas reported that he was seeing the tdbtorture test fail in
> some cases with -EDEADLCK when it wasn't before. Some debugging
> showed that deadlock detection was sometimes discovering the
> caller's lock request itself in a dependency chain.
> 
> If posix_locks_deadlock() fails to find a deadlock, the caller_fl
> will be passed to __locks_insert_block(), and this wakes up all
> locks that are blocked on caller_fl, clearing the fl_blocker link.
> 
> So if posix_locks_deadlock() finds caller_fl while searching for
> a deadlock,

I'm feeling dense.  Could you step me through the scenario in a little
more detail?

Also, how do we know this catches every such case?

And why aren't we unhashing blocks when we wake them up?

--b.

> it can be sure that link in the cycle is about to be
> broken and it need not treat it as the cause of a deadlock.
> 
> More details here: https://bugzilla.kernel.org/show_bug.cgi?id=202975
> 
> Cc: stable@vger.kernel.org
> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> Reported-by: Andreas Schneider <asn@redhat.com>
> Signed-off-by: Neil Brown <neilb@suse.com>
> Signed-off-by: Jeff Layton <jlayton@kernel.org>
> ---
>  fs/locks.c | 4 ++++
>  1 file changed, 4 insertions(+)
> 
> diff --git a/fs/locks.c b/fs/locks.c
> index eaa1cfaf73b0..b074f6d7fd2d 100644
> --- a/fs/locks.c
> +++ b/fs/locks.c
> @@ -1023,6 +1023,10 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
>  	while ((block_fl = what_owner_is_waiting_for(block_fl))) {
>  		if (i++ > MAX_DEADLK_ITERATIONS)
>  			return 0;
> +
> +		if (caller_fl == block_fl)
> +			return 0;
> +
>  		if (posix_same_owner(caller_fl, block_fl))
>  			return 1;
>  	}
> -- 
> 2.20.1

Re: [PATCH] locks: ignore same lock in blocked_lock_hash

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 3828 bytes --]

On Thu, Mar 21 2019, J. Bruce Fields wrote:

> On Thu, Mar 21, 2019 at 07:27:44AM -0400, Jeff Layton wrote:
>> Andreas reported that he was seeing the tdbtorture test fail in
>> some cases with -EDEADLCK when it wasn't before. Some debugging
>> showed that deadlock detection was sometimes discovering the
>> caller's lock request itself in a dependency chain.
>> 
>> If posix_locks_deadlock() fails to find a deadlock, the caller_fl
>> will be passed to __locks_insert_block(), and this wakes up all
>> locks that are blocked on caller_fl, clearing the fl_blocker link.
>> 
>> So if posix_locks_deadlock() finds caller_fl while searching for
>> a deadlock,
>
> I'm feeling dense.  Could you step me through the scenario in a little
> more detail?

Three processes: A, B, C.  One byte in one file: X

A gets a read lock on X.  Doesn't block, so nothing goes in the hash
  table.

B gets a read lock on X.  Doesn't block.

C tries to get a write lock on X.  It cannot so it can block on either A
  or B.  It chooses B.  It check if this might cause a deadlock, but the
  hash is empty so it doesn't.  It gets added to the hash. "C -> B"

A tries to get a write lock on X. It cannot because B has a read lock,
  so it needs to block on B, or some child.  C is a child and A's
  request conflicts with C's request, so A blocks on C.
  It first checks: Does A->C cause a loop in the hash-table?  No. So
  it proceeds to block and adds  "A->C" to the hash table.

B drops its read lock. This wakes up the first child: C.

C tries (again) to get a write lock on X.  It cannot because A still
  holds a read lock, so it will have to block on A.  First it must
  check if "C->A" will cause a loop in the hash-table ... Yes it will
  because "A->C" is already there - error!

This is a false-positive because the very next thing to be done after
posix_locks_deadlock() (while still holding all spinlocks), is
__locks_insert_block(C->A) which calls __locks_wake_up_blocks(C) which
calls __locks_delete_block() for any pending block ??->C and so will
remove A->C from the hash.

Maybe we could call __locks_wake_up_block() *before* calling
posix_locks_deadlock().  That *might* make more sense. 
  

>
> Also, how do we know this catches every such case?

The only links in the hash table that are about to be removed are those
that record that something is blocked by C (the lock we are trying to
get).  So these are the only ones that it is reasonable to special-case
in posix_locks_deadlock().

>
> And why aren't we unhashing blocks when we wake them up?

We do - that is exactly when we unhash them.  The problem is they we
wake them up *after* we check for errors, rather than before.

Thanks,
NeilBrown


>
> --b.
>
>> it can be sure that link in the cycle is about to be
>> broken and it need not treat it as the cause of a deadlock.
>> 
>> More details here: https://bugzilla.kernel.org/show_bug.cgi?id=202975
>> 
>> Cc: stable@vger.kernel.org
>> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
>> Reported-by: Andreas Schneider <asn@redhat.com>
>> Signed-off-by: Neil Brown <neilb@suse.com>
>> Signed-off-by: Jeff Layton <jlayton@kernel.org>
>> ---
>>  fs/locks.c | 4 ++++
>>  1 file changed, 4 insertions(+)
>> 
>> diff --git a/fs/locks.c b/fs/locks.c
>> index eaa1cfaf73b0..b074f6d7fd2d 100644
>> --- a/fs/locks.c
>> +++ b/fs/locks.c
>> @@ -1023,6 +1023,10 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
>>  	while ((block_fl = what_owner_is_waiting_for(block_fl))) {
>>  		if (i++ > MAX_DEADLK_ITERATIONS)
>>  			return 0;
>> +
>> +		if (caller_fl == block_fl)
>> +			return 0;
>> +
>>  		if (posix_same_owner(caller_fl, block_fl))
>>  			return 1;
>>  	}
>> -- 
>> 2.20.1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] locks: ignore same lock in blocked_lock_hash

[J. Bruce Fields]

On Fri, Mar 22, 2019 at 12:58:47PM +1100, NeilBrown wrote:
> On Thu, Mar 21 2019, J. Bruce Fields wrote:
> 
> > On Thu, Mar 21, 2019 at 07:27:44AM -0400, Jeff Layton wrote:
> >> Andreas reported that he was seeing the tdbtorture test fail in
> >> some cases with -EDEADLCK when it wasn't before. Some debugging
> >> showed that deadlock detection was sometimes discovering the
> >> caller's lock request itself in a dependency chain.
> >> 
> >> If posix_locks_deadlock() fails to find a deadlock, the caller_fl
> >> will be passed to __locks_insert_block(), and this wakes up all
> >> locks that are blocked on caller_fl, clearing the fl_blocker link.
> >> 
> >> So if posix_locks_deadlock() finds caller_fl while searching for
> >> a deadlock,
> >
> > I'm feeling dense.  Could you step me through the scenario in a little
> > more detail?
> 
> Three processes: A, B, C.  One byte in one file: X
> 
> A gets a read lock on X.  Doesn't block, so nothing goes in the hash
>   table.
> 
> B gets a read lock on X.  Doesn't block.
> 
> C tries to get a write lock on X.  It cannot so it can block on either A
>   or B.  It chooses B.  It check if this might cause a deadlock, but the
>   hash is empty so it doesn't.  It gets added to the hash. "C -> B"
> 
> A tries to get a write lock on X. It cannot because B has a read lock,
>   so it needs to block on B, or some child.  C is a child and A's
>   request conflicts with C's request, so A blocks on C.
>   It first checks: Does A->C cause a loop in the hash-table?  No. So
>   it proceeds to block and adds  "A->C" to the hash table.
> 
> B drops its read lock. This wakes up the first child: C.
> 
> C tries (again) to get a write lock on X.  It cannot because A still
>   holds a read lock, so it will have to block on A.  First it must
>   check if "C->A" will cause a loop in the hash-table ... Yes it will
>   because "A->C" is already there - error!
> 
> This is a false-positive because the very next thing to be done after
> posix_locks_deadlock() (while still holding all spinlocks), is
> __locks_insert_block(C->A) which calls __locks_wake_up_blocks(C) which
> calls __locks_delete_block() for any pending block ??->C and so will
> remove A->C from the hash.
> 
> Maybe we could call __locks_wake_up_block() *before* calling
> posix_locks_deadlock().  That *might* make more sense. 
>   
> 
> >
> > Also, how do we know this catches every such case?
> 
> The only links in the hash table that are about to be removed are those
> that record that something is blocked by C (the lock we are trying to
> get).  So these are the only ones that it is reasonable to special-case
> in posix_locks_deadlock().
> 
> >
> > And why aren't we unhashing blocks when we wake them up?
> 
> We do - that is exactly when we unhash them.  The problem is they we
> wake them up *after* we check for errors, rather than before.

Thanks!

OK, somehow I overlooked
__locks_wake_up_blocks->__locks_delete_block->locks_delete_global_block.

And I missed that all this was happening while still under the
blocked_lock_lock, so we don't have to worry about other tasks leaving
locks in this state.

It's possible I'm still being a little dense, but the new check could
really use a careful comment (maybe even as detailed as the above).

--b.

[PATCH v2] locks: ignore same lock in blocked_lock_hash

[Jeff Layton]

Andreas reported that he was seeing the tdbtorture test fail in
some cases with -EDEADLCK when it wasn't before. Some debugging
showed that deadlock detection was sometimes discovering the
caller's lock request itself in a dependency chain.

If posix_locks_deadlock() fails to find a deadlock, the caller_fl
will be passed to __locks_insert_block(), and this wakes up all
locks that are blocked on caller_fl, clearing the fl_blocker link.

So if posix_locks_deadlock() finds caller_fl while searching for
a deadlock, it can be sure that link in the cycle is about to be
broken and it need not treat it as the cause of a deadlock.

URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975
Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
Cc: stable@vger.kernel.org
Reported-by: Andreas Schneider <asn@redhat.com>
Signed-off-by: Neil Brown <neilb@suse.com>
Signed-off-by: Jeff Layton <jlayton@kernel.org>
---
 fs/locks.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)

diff --git a/fs/locks.c b/fs/locks.c
index eaa1cfaf73b0..a939a274dc71 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -1023,6 +1023,19 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
 	while ((block_fl = what_owner_is_waiting_for(block_fl))) {
 		if (i++ > MAX_DEADLK_ITERATIONS)
 			return 0;
+
+		/*
+		 * It's possible that we're retrying this lock request after
+		 * another task is has blocked on it. A lock request can't
+		 * block itself, and any locks that are blocked on it will
+		 * also be awoken soon (and have their fl_blocker pointer
+		 * cleared). Any dependency chain that contains the request
+		 * itself is therefore about to be broken, so we can safely
+		 * ignore it.
+		 */
+		if (block_fl == caller_fl)
+			return 0;
+
 		if (posix_same_owner(caller_fl, block_fl))
 			return 1;
 	}
-- 
2.20.1

Re: [PATCH v2] locks: ignore same lock in blocked_lock_hash

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 2355 bytes --]


The patch title
   locks: ignore same lock in blocked_lock_hash

is a bit misleading the lock isn't in the hash, but it is linked from
something that is.  Maybe

   locks: ignore same lock in posix_locks_deadlock()

??

On Sat, Mar 23 2019, Jeff Layton wrote:

> Andreas reported that he was seeing the tdbtorture test fail in
> some cases with -EDEADLCK when it wasn't before. Some debugging
> showed that deadlock detection was sometimes discovering the
> caller's lock request itself in a dependency chain.
>
> If posix_locks_deadlock() fails to find a deadlock, the caller_fl
> will be passed to __locks_insert_block(), and this wakes up all
> locks that are blocked on caller_fl, clearing the fl_blocker link.
>
> So if posix_locks_deadlock() finds caller_fl while searching for
> a deadlock, it can be sure that link in the cycle is about to be
> broken and it need not treat it as the cause of a deadlock.
>
> URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975
> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> Cc: stable@vger.kernel.org
> Reported-by: Andreas Schneider <asn@redhat.com>
> Signed-off-by: Neil Brown <neilb@suse.com>
> Signed-off-by: Jeff Layton <jlayton@kernel.org>
> ---
>  fs/locks.c | 13 +++++++++++++
>  1 file changed, 13 insertions(+)
>
> diff --git a/fs/locks.c b/fs/locks.c
> index eaa1cfaf73b0..a939a274dc71 100644
> --- a/fs/locks.c
> +++ b/fs/locks.c
> @@ -1023,6 +1023,19 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
>  	while ((block_fl = what_owner_is_waiting_for(block_fl))) {
>  		if (i++ > MAX_DEADLK_ITERATIONS)
>  			return 0;
> +
> +		/*
> +		 * It's possible that we're retrying this lock request after
> +		 * another task is has blocked on it. A lock request can't
> +		 * block itself, and any locks that are blocked on it will
> +		 * also be awoken soon (and have their fl_blocker pointer
> +		 * cleared). Any dependency chain that contains the request
> +		 * itself is therefore about to be broken, so we can safely
> +		 * ignore it.

That first sentence isn't working for me .... maybe remove the "is" ??

Thanks,
NeilBrown


> +		 */
> +		if (block_fl == caller_fl)
> +			return 0;
> +
>  		if (posix_same_owner(caller_fl, block_fl))
>  			return 1;
>  	}
> -- 
> 2.20.1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH v2] locks: ignore same lock in blocked_lock_hash

[Jeff Layton]

On Sat, Mar 23, 2019 at 8:51 PM NeilBrown <neilb@suse.com> wrote:
>
>
> The patch title
>    locks: ignore same lock in blocked_lock_hash
>
> is a bit misleading the lock isn't in the hash, but it is linked from
> something that is.  Maybe
>
>    locks: ignore same lock in posix_locks_deadlock()
>
> ??
>
> On Sat, Mar 23 2019, Jeff Layton wrote:
>
> > Andreas reported that he was seeing the tdbtorture test fail in
> > some cases with -EDEADLCK when it wasn't before. Some debugging
> > showed that deadlock detection was sometimes discovering the
> > caller's lock request itself in a dependency chain.
> >
> > If posix_locks_deadlock() fails to find a deadlock, the caller_fl
> > will be passed to __locks_insert_block(), and this wakes up all
> > locks that are blocked on caller_fl, clearing the fl_blocker link.
> >
> > So if posix_locks_deadlock() finds caller_fl while searching for
> > a deadlock, it can be sure that link in the cycle is about to be
> > broken and it need not treat it as the cause of a deadlock.
> >
> > URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975
> > Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> > Cc: stable@vger.kernel.org
> > Reported-by: Andreas Schneider <asn@redhat.com>
> > Signed-off-by: Neil Brown <neilb@suse.com>
> > Signed-off-by: Jeff Layton <jlayton@kernel.org>
> > ---
> >  fs/locks.c | 13 +++++++++++++
> >  1 file changed, 13 insertions(+)
> >
> > diff --git a/fs/locks.c b/fs/locks.c
> > index eaa1cfaf73b0..a939a274dc71 100644
> > --- a/fs/locks.c
> > +++ b/fs/locks.c
> > @@ -1023,6 +1023,19 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
> >       while ((block_fl = what_owner_is_waiting_for(block_fl))) {
> >               if (i++ > MAX_DEADLK_ITERATIONS)
> >                       return 0;
> > +
> > +             /*
> > +              * It's possible that we're retrying this lock request after
> > +              * another task is has blocked on it. A lock request can't
> > +              * block itself, and any locks that are blocked on it will
> > +              * also be awoken soon (and have their fl_blocker pointer
> > +              * cleared). Any dependency chain that contains the request
> > +              * itself is therefore about to be broken, so we can safely
> > +              * ignore it.
>
> That first sentence isn't working for me .... maybe remove the "is" ??
>
> Thanks,
> NeilBrown
>
>
> > +              */
> > +             if (block_fl == caller_fl)
> > +                     return 0;
> > +
> >               if (posix_same_owner(caller_fl, block_fl))
> >                       return 1;
> >       }
> > --
> > 2.20.1

Makes sense. That said, I think I'm starting to like your earlier idea
of just waking up any locks blocked on this request prior to the
deadlock check. I've tested that and it also fixes this, and may be a
bit more efficient. I'll follow up with a v3 patch that does that.

Thanks,
-- 
Jeff Layton <jlayton@poochiereds.net>

[PATCH v3] locks: wake any locks blocked on request before deadlock check

[Jeff Layton]

Andreas reported that he was seeing the tdbtorture test fail in some
cases with -EDEADLCK when it wasn't before. Some debugging showed that
deadlock detection was sometimes discovering the caller's lock request
itself in a dependency chain.

While we remove the request from the blocked_lock_hash prior to
reattempting to acquire it, any locks that are blocked on that request
will still be present in the hash and will still have their fl_blocker
pointer set to the current request.

This causes posix_locks_deadlock to find a deadlock dependency chain
when it shouldn't, as a lock request cannot block itself.

We are going to end up waking all of those blocked locks anyway when we
go to reinsert the request back into the blocked_lock_hash, so just do
it prior to checking for deadlocks. This ensures that any lock blocked
on the current request will no longer be part of any blocked request
chain.

URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975
Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
Cc: stable@vger.kernel.org
Reported-by: Andreas Schneider <asn@redhat.com>
Signed-off-by: Neil Brown <neilb@suse.com>
Signed-off-by: Jeff Layton <jlayton@kernel.org>
---
 fs/locks.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/fs/locks.c b/fs/locks.c
index eaa1cfaf73b0..71d0c6c2aac5 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -1160,6 +1160,11 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
 			 */
 			error = -EDEADLK;
 			spin_lock(&blocked_lock_lock);
+			/*
+			 * Ensure that we don't find any locks blocked on this
+			 * request during deadlock detection.
+			 */
+			__locks_wake_up_blocks(request);
 			if (likely(!posix_locks_deadlock(request, fl))) {
 				error = FILE_LOCK_DEFERRED;
 				__locks_insert_block(fl, request,
-- 
2.20.1

Re: [PATCH v3] locks: wake any locks blocked on request before deadlock check

[J. Bruce Fields]

On Mon, Mar 25, 2019 at 08:32:52AM -0400, Jeff Layton wrote:
> Andreas reported that he was seeing the tdbtorture test fail in some
> cases with -EDEADLCK when it wasn't before. Some debugging showed that
> deadlock detection was sometimes discovering the caller's lock request
> itself in a dependency chain.
> 
> While we remove the request from the blocked_lock_hash prior to
> reattempting to acquire it, any locks that are blocked on that request
> will still be present in the hash and will still have their fl_blocker
> pointer set to the current request.

This description is a lot easier for me to follow, thanks!

> This causes posix_locks_deadlock to find a deadlock dependency chain
> when it shouldn't, as a lock request cannot block itself.
> 
> We are going to end up waking all of those blocked locks anyway when we
> go to reinsert the request back into the blocked_lock_hash, so just do
> it prior to checking for deadlocks. This ensures that any lock blocked
> on the current request will no longer be part of any blocked request
> chain.

Looks right to me.

--b.

> 
> URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975
> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> Cc: stable@vger.kernel.org
> Reported-by: Andreas Schneider <asn@redhat.com>
> Signed-off-by: Neil Brown <neilb@suse.com>
> Signed-off-by: Jeff Layton <jlayton@kernel.org>
> ---
>  fs/locks.c | 5 +++++
>  1 file changed, 5 insertions(+)
> 
> diff --git a/fs/locks.c b/fs/locks.c
> index eaa1cfaf73b0..71d0c6c2aac5 100644
> --- a/fs/locks.c
> +++ b/fs/locks.c
> @@ -1160,6 +1160,11 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
>  			 */
>  			error = -EDEADLK;
>  			spin_lock(&blocked_lock_lock);
> +			/*
> +			 * Ensure that we don't find any locks blocked on this
> +			 * request during deadlock detection.
> +			 */
> +			__locks_wake_up_blocks(request);
>  			if (likely(!posix_locks_deadlock(request, fl))) {
>  				error = FILE_LOCK_DEFERRED;
>  				__locks_insert_block(fl, request,
> -- 
> 2.20.1

Re: [PATCH v3] locks: wake any locks blocked on request before deadlock check

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 2141 bytes --]

On Mon, Mar 25 2019, Jeff Layton wrote:

> Andreas reported that he was seeing the tdbtorture test fail in some
> cases with -EDEADLCK when it wasn't before. Some debugging showed that
> deadlock detection was sometimes discovering the caller's lock request
> itself in a dependency chain.
>
> While we remove the request from the blocked_lock_hash prior to
> reattempting to acquire it, any locks that are blocked on that request
> will still be present in the hash and will still have their fl_blocker
> pointer set to the current request.
>
> This causes posix_locks_deadlock to find a deadlock dependency chain
> when it shouldn't, as a lock request cannot block itself.
>
> We are going to end up waking all of those blocked locks anyway when we
> go to reinsert the request back into the blocked_lock_hash, so just do
> it prior to checking for deadlocks. This ensures that any lock blocked
> on the current request will no longer be part of any blocked request
> chain.
>
> URL: https://bugzilla.kernel.org/show_bug.cgi?id=202975
> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> Cc: stable@vger.kernel.org
> Reported-by: Andreas Schneider <asn@redhat.com>
> Signed-off-by: Neil Brown <neilb@suse.com>
> Signed-off-by: Jeff Layton <jlayton@kernel.org>

Yes, I'm happy with this patch and description.
It is more "obviously correct" than the other patch.

Thanks,
NeilBrown


> ---
>  fs/locks.c | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git a/fs/locks.c b/fs/locks.c
> index eaa1cfaf73b0..71d0c6c2aac5 100644
> --- a/fs/locks.c
> +++ b/fs/locks.c
> @@ -1160,6 +1160,11 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
>  			 */
>  			error = -EDEADLK;
>  			spin_lock(&blocked_lock_lock);
> +			/*
> +			 * Ensure that we don't find any locks blocked on this
> +			 * request during deadlock detection.
> +			 */
> +			__locks_wake_up_blocks(request);
>  			if (likely(!posix_locks_deadlock(request, fl))) {
>  				error = FILE_LOCK_DEFERRED;
>  				__locks_insert_block(fl, request,
> -- 
> 2.20.1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] locks: ignore same lock in blocked_lock_hash

[Jeff Layton]

On Thu, Mar 21, 2019 at 8:58 PM NeilBrown <neilb@suse.com> wrote:
>
> On Thu, Mar 21 2019, J. Bruce Fields wrote:
>
> > On Thu, Mar 21, 2019 at 07:27:44AM -0400, Jeff Layton wrote:
> >> Andreas reported that he was seeing the tdbtorture test fail in
> >> some cases with -EDEADLCK when it wasn't before. Some debugging
> >> showed that deadlock detection was sometimes discovering the
> >> caller's lock request itself in a dependency chain.
> >>
> >> If posix_locks_deadlock() fails to find a deadlock, the caller_fl
> >> will be passed to __locks_insert_block(), and this wakes up all
> >> locks that are blocked on caller_fl, clearing the fl_blocker link.
> >>
> >> So if posix_locks_deadlock() finds caller_fl while searching for
> >> a deadlock,
> >
> > I'm feeling dense.  Could you step me through the scenario in a little
> > more detail?
>
> Three processes: A, B, C.  One byte in one file: X
>
> A gets a read lock on X.  Doesn't block, so nothing goes in the hash
>   table.
>
> B gets a read lock on X.  Doesn't block.
>
> C tries to get a write lock on X.  It cannot so it can block on either A
>   or B.  It chooses B.  It check if this might cause a deadlock, but the
>   hash is empty so it doesn't.  It gets added to the hash. "C -> B"
>
> A tries to get a write lock on X. It cannot because B has a read lock,
>   so it needs to block on B, or some child.  C is a child and A's
>   request conflicts with C's request, so A blocks on C.
>   It first checks: Does A->C cause a loop in the hash-table?  No. So
>   it proceeds to block and adds  "A->C" to the hash table.
>
> B drops its read lock. This wakes up the first child: C.
>
> C tries (again) to get a write lock on X.  It cannot because A still
>   holds a read lock, so it will have to block on A.  First it must
>   check if "C->A" will cause a loop in the hash-table ... Yes it will
>   because "A->C" is already there - error!
>
> This is a false-positive because the very next thing to be done after
> posix_locks_deadlock() (while still holding all spinlocks), is
> __locks_insert_block(C->A) which calls __locks_wake_up_blocks(C) which
> calls __locks_delete_block() for any pending block ??->C and so will
> remove A->C from the hash.
>
> Maybe we could call __locks_wake_up_block() *before* calling
> posix_locks_deadlock().  That *might* make more sense.
>
>

It might. The only downside that I can see to doing that is that
waking up blocks earlier might mean that they end up spinning for
longer on the spinlocks that the waking task still holds. Maybe the
difference is not enough to matter though.

> >
> > Also, how do we know this catches every such case?
>
> The only links in the hash table that are about to be removed are those
> that record that something is blocked by C (the lock we are trying to
> get).  So these are the only ones that it is reasonable to special-case
> in posix_locks_deadlock().
>
> >
> > And why aren't we unhashing blocks when we wake them up?
>
> We do - that is exactly when we unhash them.  The problem is they we
> wake them up *after* we check for errors, rather than before.
>
> Thanks,
> NeilBrown
>
>
> >
> > --b.
> >
> >> it can be sure that link in the cycle is about to be
> >> broken and it need not treat it as the cause of a deadlock.
> >>
> >> More details here: https://bugzilla.kernel.org/show_bug.cgi?id=202975
> >>
> >> Cc: stable@vger.kernel.org
> >> Fixes: 5946c4319ebb ("fs/locks: allow a lock request to block other requests.")
> >> Reported-by: Andreas Schneider <asn@redhat.com>
> >> Signed-off-by: Neil Brown <neilb@suse.com>
> >> Signed-off-by: Jeff Layton <jlayton@kernel.org>
> >> ---
> >>  fs/locks.c | 4 ++++
> >>  1 file changed, 4 insertions(+)
> >>
> >> diff --git a/fs/locks.c b/fs/locks.c
> >> index eaa1cfaf73b0..b074f6d7fd2d 100644
> >> --- a/fs/locks.c
> >> +++ b/fs/locks.c
> >> @@ -1023,6 +1023,10 @@ static int posix_locks_deadlock(struct file_lock *caller_fl,
> >>      while ((block_fl = what_owner_is_waiting_for(block_fl))) {
> >>              if (i++ > MAX_DEADLK_ITERATIONS)
> >>                      return 0;
> >> +
> >> +            if (caller_fl == block_fl)
> >> +                    return 0;
> >> +
> >>              if (posix_same_owner(caller_fl, block_fl))
> >>                      return 1;
> >>      }
> >> --
> >> 2.20.1



-- 
Jeff Layton <jlayton@poochiereds.net>