[Question] race between spin_lock and spin_unlock

[Question] race between spin_lock and spin_unlock

[Ming Lei]

Hi,

When reading the code of arch_spin_lock(), I think there might be
a race between arch_spin_lock() and arch_spin_unlock():

- arch_spin_unlock() happened just between StoreExcl(lock->next)
and comparing lockval.tickets.next with lockval.tickets.owner inside
arch_spin_lock()

- arch_spin_lock() can't notice the change on lock->owner, so call
wfe(), then just waiting for being waken up, but there isn't corresponding
unlock to send wake event any more.

Maybe the below change may make the race to happen difficultly,
but it still can't avoid it completely.

diff --git a/arch/arm/include/asm/spinlock.h b/arch/arm/include/asm/spinlock.h
index 6220e9f..e1b239c 100644
--- a/arch/arm/include/asm/spinlock.h
+++ b/arch/arm/include/asm/spinlock.h
@@ -87,10 +87,8 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
 	: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
 	: "cc");

-	while (lockval.tickets.next != lockval.tickets.owner) {
+	while (lockval.tickets.next != ACCESS_ONCE(lock->tickets.owner))
 		wfe();
-		lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);
-	}

 	smp_mb();
 }

Any comments on the problem?

Thanks,
-- 
Ming Lei

[Question] race between spin_lock and spin_unlock

[Will Deacon]

On Mon, Jun 24, 2013 at 04:13:38PM +0100, Ming Lei wrote:
> Hi,

Hi Ming Lei,

> When reading the code of arch_spin_lock(), I think there might be
> a race between arch_spin_lock() and arch_spin_unlock():
> 
> - arch_spin_unlock() happened just between StoreExcl(lock->next)
> and comparing lockval.tickets.next with lockval.tickets.owner inside
> arch_spin_lock()
> 
> - arch_spin_lock() can't notice the change on lock->owner, so call
> wfe(), then just waiting for being waken up, but there isn't corresponding
> unlock to send wake event any more.
> 
> Maybe the below change may make the race to happen difficultly,
> but it still can't avoid it completely.
> 
> diff --git a/arch/arm/include/asm/spinlock.h b/arch/arm/include/asm/spinlock.h
> index 6220e9f..e1b239c 100644
> --- a/arch/arm/include/asm/spinlock.h
> +++ b/arch/arm/include/asm/spinlock.h
> @@ -87,10 +87,8 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
>  	: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
>  	: "cc");
> 
> -	while (lockval.tickets.next != lockval.tickets.owner) {
> +	while (lockval.tickets.next != ACCESS_ONCE(lock->tickets.owner))
>  		wfe();
> -		lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);
> -	}
> 
>  	smp_mb();
>  }
> 
> Any comments on the problem?

Not sure I see the problem -- the sev guaranteed by the unlock is pended on
the core doing the lock by setting the event register, so you can't miss it.
The wfe will acknowledge the event (by clearing the event register) but it
won't actually wait.

Will

[Question] race between spin_lock and spin_unlock

[Ming Lei]

On Mon, Jun 24, 2013 at 11:43 PM, Will Deacon <will.deacon@arm.com> wrote:
> On Mon, Jun 24, 2013 at 04:13:38PM +0100, Ming Lei wrote:
>> Hi,
>
> Hi Ming Lei,
>
>> When reading the code of arch_spin_lock(), I think there might be
>> a race between arch_spin_lock() and arch_spin_unlock():
>>
>> - arch_spin_unlock() happened just between StoreExcl(lock->next)
>> and comparing lockval.tickets.next with lockval.tickets.owner inside
>> arch_spin_lock()
>>
>> - arch_spin_lock() can't notice the change on lock->owner, so call
>> wfe(), then just waiting for being waken up, but there isn't corresponding
>> unlock to send wake event any more.
>>
>> Maybe the below change may make the race to happen difficultly,
>> but it still can't avoid it completely.
>>
>> diff --git a/arch/arm/include/asm/spinlock.h b/arch/arm/include/asm/spinlock.h
>> index 6220e9f..e1b239c 100644
>> --- a/arch/arm/include/asm/spinlock.h
>> +++ b/arch/arm/include/asm/spinlock.h
>> @@ -87,10 +87,8 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
>>       : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
>>       : "cc");
>>
>> -     while (lockval.tickets.next != lockval.tickets.owner) {
>> +     while (lockval.tickets.next != ACCESS_ONCE(lock->tickets.owner))
>>               wfe();
>> -             lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);
>> -     }
>>
>>       smp_mb();
>>  }
>>
>> Any comments on the problem?
>
> Not sure I see the problem -- the sev guaranteed by the unlock is pended on
> the core doing the lock by setting the event register, so you can't miss it.
> The wfe will acknowledge the event (by clearing the event register) but it
> won't actually wait.

If so, looks I am afraid too much, :-)

Also I have another question, if two sev() comes from two cores, then the
wfe() in one core will acknowledge both the two sev()? or one wfe() only
acks one sev()?

If the wfe() in one core may acknowledge two sev(), the above problem
might still exists.


Thanks,
-- 
Ming Lei

[Question] race between spin_lock and spin_unlock

[Will Deacon]

On Mon, Jun 24, 2013 at 05:04:37PM +0100, Ming Lei wrote:
> On Mon, Jun 24, 2013 at 11:43 PM, Will Deacon <will.deacon@arm.com> wrote:
> >> Any comments on the problem?
> >
> > Not sure I see the problem -- the sev guaranteed by the unlock is pended on
> > the core doing the lock by setting the event register, so you can't miss it.
> > The wfe will acknowledge the event (by clearing the event register) but it
> > won't actually wait.
> 
> If so, looks I am afraid too much, :-)
> 
> Also I have another question, if two sev() comes from two cores, then the
> wfe() in one core will acknowledge both the two sev()? or one wfe() only
> acks one sev()?

Events do not compose, so you can only have one event pending at a time,
which the wfe will clear.

> If the wfe() in one core may acknowledge two sev(), the above problem
> might still exists.

You mean, if you had two CPUs spinning on a lock held by a third CPU? In
this case, the third CPU would have to release the lock, then one of the
waiters would have to acquire it, complete its critical section and finally
release it before the other waiter had executed its wfe (about three
instructions)...

I don't think we need to worry about that in practice, unless you have
another example?

Will

[Question] race between spin_lock and spin_unlock

[Ming Lei]

On Tue, Jun 25, 2013 at 12:37 AM, Will Deacon <will.deacon@arm.com> wrote:
> On Mon, Jun 24, 2013 at 05:04:37PM +0100, Ming Lei wrote:
>> On Mon, Jun 24, 2013 at 11:43 PM, Will Deacon <will.deacon@arm.com> wrote:
>> >> Any comments on the problem?
>> >
>> > Not sure I see the problem -- the sev guaranteed by the unlock is pended on
>> > the core doing the lock by setting the event register, so you can't miss it.
>> > The wfe will acknowledge the event (by clearing the event register) but it
>> > won't actually wait.
>>
>> If so, looks I am afraid too much, :-)
>>
>> Also I have another question, if two sev() comes from two cores, then the
>> wfe() in one core will acknowledge both the two sev()? or one wfe() only
>> acks one sev()?
>
> Events do not compose, so you can only have one event pending at a time,
> which the wfe will clear.

I understand two processors can run sev() independently, so another
processor may see two event coming, then I am wondering if the later
wfe may clear the two previous sev().

>
>> If the wfe() in one core may acknowledge two sev(), the above problem
>> might still exists.
>
> You mean, if you had two CPUs spinning on a lock held by a third CPU? In
> this case, the third CPU would have to release the lock, then one of the
> waiters would have to acquire it, complete its critical section and finally
> release it before the other waiter had executed its wfe (about three
> instructions)...

I mean the below situation:

CPU0										CPU1

spin_lock(&A)
	StoreExcl(lock->next)
											spin_unlock(&A)
												Store(&lock->owner)
												dsb_sev()
	interrupt comes
		- wfe() called in the
		irq handler
		- the sev() from CPU1
		is acked
	
	while(tickets.next != tickets.owner) {
		wfe();
		...
	}



>
> I don't think we need to worry about that in practice, unless you have
> another example?

No, I don't, and it is just in theory.


Thanks,
-- 
Ming Lei

[Question] race between spin_lock and spin_unlock

[Will Deacon]

On Tue, Jun 25, 2013 at 05:31:44AM +0100, Ming Lei wrote:
> On Tue, Jun 25, 2013 at 12:37 AM, Will Deacon <will.deacon@arm.com> wrote:
> > You mean, if you had two CPUs spinning on a lock held by a third CPU? In
> > this case, the third CPU would have to release the lock, then one of the
> > waiters would have to acquire it, complete its critical section and finally
> > release it before the other waiter had executed its wfe (about three
> > instructions)...
> 
> I mean the below situation:
> 
> CPU0										CPU1
> 
> spin_lock(&A)
> 	StoreExcl(lock->next)
> 											spin_unlock(&A)
> 												Store(&lock->owner)
> 												dsb_sev()
> 	interrupt comes
> 		- wfe() called in the
> 		irq handler

Is this just a vanilla wfe, or as part of a spin_lock? If it's part of a
spin_lock, then we'll do a sev when we unlock it. An opencoded wfe in an
interrupt handler sounds like a really bad idea anyway!

> 		- the sev() from CPU1
> 		is acked
> 	
> 	while(tickets.next != tickets.owner) {
> 		wfe();
> 		...
> 	}

Will

[Question] race between spin_lock and spin_unlock

[Ming Lei]

On Tue, Jun 25, 2013 at 4:48 PM, Will Deacon <will.deacon@arm.com> wrote:
> On Tue, Jun 25, 2013 at 05:31:44AM +0100, Ming Lei wrote:
>> On Tue, Jun 25, 2013 at 12:37 AM, Will Deacon <will.deacon@arm.com> wrote:
>> > You mean, if you had two CPUs spinning on a lock held by a third CPU? In
>> > this case, the third CPU would have to release the lock, then one of the
>> > waiters would have to acquire it, complete its critical section and finally
>> > release it before the other waiter had executed its wfe (about three
>> > instructions)...
>>
>> I mean the below situation:
>>
>> CPU0                                                                          CPU1
>>
>> spin_lock(&A)
>>       StoreExcl(lock->next)
>>                                                                                       spin_unlock(&A)
>>                                                                                               Store(&lock->owner)
>>                                                                                               dsb_sev()
>>       interrupt comes
>>               - wfe() called in the
>>               irq handler
>
> Is this just a vanilla wfe, or as part of a spin_lock? If it's part of a
> spin_lock, then we'll do a sev when we unlock it. An opencoded wfe in an

Suppose it is part of spin_lock(&B), and the sev in spin_unlock(&B) may happen
in CPU2 or CPU3, then two sev() will come in CPU0.

My question is that if the wfe in spin_lock(&B) called from irq
handler may clear
the two sev().

If yes, the wfe() in spin_lock(&A) may still wait for later sev, right?  If not,
it should be fine.

Thanks,
-- 
Ming Lei

[Question] race between spin_lock and spin_unlock

[Will Deacon]

On Tue, Jun 25, 2013 at 11:54:23AM +0100, Ming Lei wrote:
> On Tue, Jun 25, 2013 at 4:48 PM, Will Deacon <will.deacon@arm.com> wrote:
> > On Tue, Jun 25, 2013 at 05:31:44AM +0100, Ming Lei wrote:
> >> On Tue, Jun 25, 2013 at 12:37 AM, Will Deacon <will.deacon@arm.com> wrote:
> >> > You mean, if you had two CPUs spinning on a lock held by a third CPU? In
> >> > this case, the third CPU would have to release the lock, then one of the
> >> > waiters would have to acquire it, complete its critical section and finally
> >> > release it before the other waiter had executed its wfe (about three
> >> > instructions)...
> >>
> >> I mean the below situation:
> >>
> >> CPU0                                                                          CPU1
> >>
> >> spin_lock(&A)
> >>       StoreExcl(lock->next)
> >>                                                                                       spin_unlock(&A)
> >>                                                                                               Store(&lock->owner)
> >>                                                                                               dsb_sev()
> >>       interrupt comes
> >>               - wfe() called in the
> >>               irq handler
> >
> > Is this just a vanilla wfe, or as part of a spin_lock? If it's part of a
> > spin_lock, then we'll do a sev when we unlock it. An opencoded wfe in an
> 
> Suppose it is part of spin_lock(&B), and the sev in spin_unlock(&B) may happen
> in CPU2 or CPU3, then two sev() will come in CPU0.
> 
> My question is that if the wfe in spin_lock(&B) called from irq
> handler may clear
> the two sev().

Yes, as I said before, the events don't accumulate.

> If yes, the wfe() in spin_lock(&A) may still wait for later sev, right?  If not,
> it should be fine.

There's no problem, because spin_unlock(&B) in the interrupt handler on CPU0
(which must happen before it returns from the interrupt) will send a further
event and the wfe encountered when resuming spin_lock(&A) will not wait.

Will

[Question] race between spin_lock and spin_unlock

[Ming Lei]

On Tue, Jun 25, 2013 at 6:59 PM, Will Deacon <will.deacon@arm.com> wrote:
>
> There's no problem, because spin_unlock(&B) in the interrupt handler on CPU0
> (which must happen before it returns from the interrupt) will send a further
> event and the wfe encountered when resuming spin_lock(&A) will not wait.

Got it, thanks for your explanation.


Thanks,
-- 
Ming Lei