rwlock and per-cpu rwlock recursive?

rwlock and per-cpu rwlock recursive?

[Julien Grall]

Hi,

On Arm, we made the (wrong?) assumption that the rwlock was recursive. 
We have a couple of places where the read lock can be nested (mostly the 
memaccess code).

I found out today that it can actually deadlock in the following case:
	1) CPU A -> Ask for the read lock
		=> Succeed
	2) CPU B -> Ask for the write lock
		=> Already taken by CPU A so go to the slowpath
		=> Take the internal lock (lock->lock)
		=> Wait until the lock is released.
	3) CPU A -> Ask for the read lock recursively
		=> A writer is waiting so go to the slowpath
		=> Try to take the internal lock (lock->lock)
			=> Blocking because CPU B already has it

So we end up in a deadlock case. Can someone confirm whether whether 
rwlock was meant to be recursive?

Similarly, I was thinking to move the p2m code to the per-cpu rwlock as 
x86 does. From what I gathered by reading the x86 code, this lock could 
be taken recursively. Am I right?

Lastly, the x86 p2m code seemed to use rwlock before hand. How did the 
p2m code was handling recursive locking?

Cheers,

-- 
Julien Grall

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: rwlock and per-cpu rwlock recursive?

[Andrew Cooper]

On 27/02/18 19:18, Julien Grall wrote:
> Hi,
>
> On Arm, we made the (wrong?) assumption that the rwlock was recursive.
> We have a couple of places where the read lock can be nested (mostly
> the memaccess code).
>
> I found out today that it can actually deadlock in the following case:
>     1) CPU A -> Ask for the read lock
>         => Succeed
>     2) CPU B -> Ask for the write lock
>         => Already taken by CPU A so go to the slowpath
>         => Take the internal lock (lock->lock)
>         => Wait until the lock is released.
>     3) CPU A -> Ask for the read lock recursively
>         => A writer is waiting so go to the slowpath
>         => Try to take the internal lock (lock->lock)
>             => Blocking because CPU B already has it
>
> So we end up in a deadlock case. Can someone confirm whether whether
> rwlock was meant to be recursive?

rwlocks are not recursive, but probably will appear to be in the common
case.

When uncontended, an effectively-arbitrary number of read_lock()'s can
complete, but when contended, readers and writers use a regular spinlock
(which is a ticketlock under the hood) to ensure fairness.

> Similarly, I was thinking to move the p2m code to the per-cpu rwlock
> as x86 does. From what I gathered by reading the x86 code, this lock
> could be taken recursively. Am I right?

No - what gives you the impression that it can be taken recursively?  In
the case where we detect taking a second percpu_rwlock, we fall back to
the slowpath of a real read_lock() call.

> Lastly, the x86 p2m code seemed to use rwlock before hand. How did the
> p2m code was handling recursive locking?

Plain spinlocks (when using the recursive helpers), and x86
mm_{rw,}lock_t's can be taken recursively.  A call to spin_lock() will
deadlock if the lock is already taken and you meant to use
spin_lock_recursive().

You probably want to see about reading xen/arch/x86/mm/mm-locks.h

~Andrew

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: rwlock and per-cpu rwlock recursive?

[Julien Grall]

Hi Andrew,

On 02/27/2018 07:57 PM, Andrew Cooper wrote:
> On 27/02/18 19:18, Julien Grall wrote:
>> On Arm, we made the (wrong?) assumption that the rwlock was recursive.
>> We have a couple of places where the read lock can be nested (mostly
>> the memaccess code).
>>
>> I found out today that it can actually deadlock in the following case:
>>      1) CPU A -> Ask for the read lock
>>          => Succeed
>>      2) CPU B -> Ask for the write lock
>>          => Already taken by CPU A so go to the slowpath
>>          => Take the internal lock (lock->lock)
>>          => Wait until the lock is released.
>>      3) CPU A -> Ask for the read lock recursively
>>          => A writer is waiting so go to the slowpath
>>          => Try to take the internal lock (lock->lock)
>>              => Blocking because CPU B already has it
>>
>> So we end up in a deadlock case. Can someone confirm whether whether
>> rwlock was meant to be recursive?
> 
> rwlocks are not recursive, but probably will appear to be in the common
> case.
> 
> When uncontended, an effectively-arbitrary number of read_lock()'s can
> complete, but when contended, readers and writers use a regular spinlock
> (which is a ticketlock under the hood) to ensure fairness.

Thank you for the explanation. I will have to rework the Arm code then.

> 
>> Similarly, I was thinking to move the p2m code to the per-cpu rwlock
>> as x86 does. From what I gathered by reading the x86 code, this lock
>> could be taken recursively. Am I right?
> 
> No - what gives you the impression that it can be taken recursively?  In
> the case where we detect taking a second percpu_rwlock, we fall back to
> the slowpath of a real read_lock() call.

I knew the p2m lock could be taken recursively but I was not sure how 
this was achieved. So I assumed it was thanks to the percpu_rwlock.

> 
>> Lastly, the x86 p2m code seemed to use rwlock before hand. How did the
>> p2m code was handling recursive locking?
> 
> Plain spinlocks (when using the recursive helpers), and x86
> mm_{rw,}lock_t's can be taken recursively.  A call to spin_lock() will
> deadlock if the lock is already taken and you meant to use
> spin_lock_recursive().
> 
> You probably want to see about reading xen/arch/x86/mm/mm-locks.h

Looking at the implementation, I see recursion handling for 
mm_write_lock but not for mm_read_lock. Can you confirm that only the 
write lock can be taken recursively?

Cheers,

-- 
Julien Grall

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: rwlock and per-cpu rwlock recursive?

[Jan Beulich]

>>> On 28.02.18 at 11:28, <julien.grall@arm.com> wrote:
> Looking at the implementation, I see recursion handling for 
> mm_write_lock but not for mm_read_lock. Can you confirm that only the 
> write lock can be taken recursively?

If by "write lock" you mean an arbitrary one, then the answer of
course is no. The mm write lock machinery adds recursiveness
around percpu_write_lock(). See e.g. _mm_write_lock().

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: rwlock and per-cpu rwlock recursive?

[Julien Grall]

Hi,

On 02/28/2018 11:18 AM, Jan Beulich wrote:
>>>> On 28.02.18 at 11:28, <julien.grall@arm.com> wrote:
>> Looking at the implementation, I see recursion handling for
>> mm_write_lock but not for mm_read_lock. Can you confirm that only the
>> write lock can be taken recursively?
> 
> If by "write lock" you mean an arbitrary one, then the answer of
> course is no. The mm write lock machinery adds recursiveness
> around percpu_write_lock(). See e.g. _mm_write_lock().

By "write lock", I meant mm_write_lock(). Thank you for the 
confirmation, so mm_read_lock() is not recursive.

Cheers,

-- 
Julien Grall

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel