[Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

Patch 2 of my fast lock series actually also contained an attempt to fix
a race I spotted in the code that atomically sets the claimed bit. I
forgot about this fact and even, worse, I only replace the original race
with another one.

So here comes a new attempt to fix the issue that the lock owner and/or
the claimed bit can change between trylock and the cmpxchg under nklock.
Please have a look and cross-check the logic.

The patch applies on top of vanilla SVN, so my series has to be rebased
and the fix has to be ported to native as well - where we just found it
in the field.

Jan

---
 ksrc/skins/posix/mutex.h |   11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

Index: b/ksrc/skins/posix/mutex.h
===================================================================
--- a/ksrc/skins/posix/mutex.h
+++ b/ksrc/skins/posix/mutex.h
@@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
 	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
 	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
 	xnlock_get_irqsave(&nklock, s);
+	owner = xnarch_atomic_intptr_get(mutex->owner);
 	while(!test_claimed(owner)) {
-		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
-						   owner, set_claimed(owner, 1));
-		if (likely(old == owner))
-			break;
-		if (old == NULL) {
+		if (owner == NULL) {
 			/* Owner called fast mutex_unlock
 			   (on another cpu) */
 			xnlock_put_irqrestore(&nklock, s);
 			goto retry_lock;
 		}
+		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
+						   owner, set_claimed(owner, 1));
+		if (likely(old == owner))
+			break;
 		owner = old;
 	}
 

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> Patch 2 of my fast lock series actually also contained an attempt to fix
> a race I spotted in the code that atomically sets the claimed bit. I
> forgot about this fact and even, worse, I only replace the original race
> with another one.
> 
> So here comes a new attempt to fix the issue that the lock owner and/or
> the claimed bit can change between trylock and the cmpxchg under nklock.
> Please have a look and cross-check the logic.
> 
> The patch applies on top of vanilla SVN, so my series has to be rebased
> and the fix has to be ported to native as well - where we just found it
> in the field.

Could you explain the race ?

-- 
                                                 Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> Patch 2 of my fast lock series actually also contained an attempt to fix
>> a race I spotted in the code that atomically sets the claimed bit. I
>> forgot about this fact and even, worse, I only replace the original race
>> with another one.
>>
>> So here comes a new attempt to fix the issue that the lock owner and/or
>> the claimed bit can change between trylock and the cmpxchg under nklock.
>> Please have a look and cross-check the logic.
>>
>> The patch applies on top of vanilla SVN, so my series has to be rebased
>> and the fix has to be ported to native as well - where we just found it
>> in the field.
> 
> Could you explain the race ?

We read the owner in pse51_mutex_trylock_internal. In
pse51_mutex_timedlock_internal under nklock, we check that old value for
the claimed bit. If the old value happened to have it set, we continue
happily without worries. But it may have been cleared meanwhile _before_
we entered the nklock.

I previously tried to fix this by re-reading the lock value, but then I
failed to account for the case that the value may have become NULL
meanwhile. The new version should cover both cases.

Jan

-- 
Siemens AG, Corporate Technology, CT SE 2
Corporate Competence Center Embedded Linux

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> Patch 2 of my fast lock series actually also contained an attempt to fix
> a race I spotted in the code that atomically sets the claimed bit. I
> forgot about this fact and even, worse, I only replace the original race
> with another one.
> 
> So here comes a new attempt to fix the issue that the lock owner and/or
> the claimed bit can change between trylock and the cmpxchg under nklock.
> Please have a look and cross-check the logic.
> 
> The patch applies on top of vanilla SVN, so my series has to be rebased
> and the fix has to be ported to native as well - where we just found it
> in the field.

Ok. Got it.

> 
> Jan
> 
> ---
>  ksrc/skins/posix/mutex.h |   11 ++++++-----
>  1 file changed, 6 insertions(+), 5 deletions(-)
> 
> Index: b/ksrc/skins/posix/mutex.h
> ===================================================================
> --- a/ksrc/skins/posix/mutex.h
> +++ b/ksrc/skins/posix/mutex.h
> @@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
>  	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
>  	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
>  	xnlock_get_irqsave(&nklock, s);
> +	owner = xnarch_atomic_intptr_get(mutex->owner);

Bad, this makes two atomic ops. So, I would rather propose:

>  	while(!test_claimed(owner)) {
- while(!test_claimed(owner)) {
+ do {
> -		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
> -						   owner, set_claimed(owner, 1));
> -		if (likely(old == owner))
> -			break;
> -		if (old == NULL) {
> +		if (owner == NULL) {
>  			/* Owner called fast mutex_unlock
>  			   (on another cpu) */
>  			xnlock_put_irqrestore(&nklock, s);
>  			goto retry_lock;
>  		}
> +		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
> +						   owner, set_claimed(owner, 1));
> +		if (likely(old == owner))
> +			break;
>  		owner = old;
-  	}
+       } while (!test_claimed(owner))
>  
> 
> _______________________________________________
> Xenomai-core mailing list
> Xenomai-core@domain.hid
> https://mail.gna.org/listinfo/xenomai-core


-- 
                                                 Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> Patch 2 of my fast lock series actually also contained an attempt to fix
>> a race I spotted in the code that atomically sets the claimed bit. I
>> forgot about this fact and even, worse, I only replace the original race
>> with another one.
>>
>> So here comes a new attempt to fix the issue that the lock owner and/or
>> the claimed bit can change between trylock and the cmpxchg under nklock.
>> Please have a look and cross-check the logic.
>>
>> The patch applies on top of vanilla SVN, so my series has to be rebased
>> and the fix has to be ported to native as well - where we just found it
>> in the field.
> 
> Ok. Got it.
> 
>> Jan
>>
>> ---
>>  ksrc/skins/posix/mutex.h |   11 ++++++-----
>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>
>> Index: b/ksrc/skins/posix/mutex.h
>> ===================================================================
>> --- a/ksrc/skins/posix/mutex.h
>> +++ b/ksrc/skins/posix/mutex.h
>> @@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
>>  	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
>>  	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
>>  	xnlock_get_irqsave(&nklock, s);
>> +	owner = xnarch_atomic_intptr_get(mutex->owner);
> 
> Bad, this makes two atomic ops. So, I would rather propose:

Err, how many archs perform special dances for atomic_read?

> 
>>  	while(!test_claimed(owner)) {
> - while(!test_claimed(owner)) {
> + do {
>> -		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>> -						   owner, set_claimed(owner, 1));
>> -		if (likely(old == owner))
>> -			break;
>> -		if (old == NULL) {
>> +		if (owner == NULL) {
>>  			/* Owner called fast mutex_unlock
>>  			   (on another cpu) */
>>  			xnlock_put_irqrestore(&nklock, s);
>>  			goto retry_lock;
>>  		}
>> +		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>> +						   owner, set_claimed(owner, 1));
>> +		if (likely(old == owner))
>> +			break;
>>  		owner = old;
> -  	}
> +       } while (!test_claimed(owner))

Your version slows down the contended case by performing redundant
atomic cmpxchgs. My version puts minimal additional overhead in the
!test_claimed case, but introduces no further atomic ops and avoids to
much traffic on mutex->owner's cacheline when there are >1 waiters.

Jan

-- 
Siemens AG, Corporate Technology, CT SE 2
Corporate Competence Center Embedded Linux

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> Gilles Chanteperdrix wrote:
>> Jan Kiszka wrote:
>>> Patch 2 of my fast lock series actually also contained an attempt to fix
>>> a race I spotted in the code that atomically sets the claimed bit. I
>>> forgot about this fact and even, worse, I only replace the original race
>>> with another one.
>>>
>>> So here comes a new attempt to fix the issue that the lock owner and/or
>>> the claimed bit can change between trylock and the cmpxchg under nklock.
>>> Please have a look and cross-check the logic.
>>>
>>> The patch applies on top of vanilla SVN, so my series has to be rebased
>>> and the fix has to be ported to native as well - where we just found it
>>> in the field.
>> Ok. Got it.
>>
>>> Jan
>>>
>>> ---
>>>  ksrc/skins/posix/mutex.h |   11 ++++++-----
>>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>>
>>> Index: b/ksrc/skins/posix/mutex.h
>>> ===================================================================
>>> --- a/ksrc/skins/posix/mutex.h
>>> +++ b/ksrc/skins/posix/mutex.h
>>> @@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
>>>  	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
>>>  	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
>>>  	xnlock_get_irqsave(&nklock, s);
>>> +	owner = xnarch_atomic_intptr_get(mutex->owner);
>> Bad, this makes two atomic ops. So, I would rather propose:
> 
> Err, how many archs perform special dances for atomic_read?

powerpc, arm >= 6

> 
>>>  	while(!test_claimed(owner)) {
>> - while(!test_claimed(owner)) {
>> + do {
>>> -		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>> -						   owner, set_claimed(owner, 1));
>>> -		if (likely(old == owner))
>>> -			break;
>>> -		if (old == NULL) {
>>> +		if (owner == NULL) {
>>>  			/* Owner called fast mutex_unlock
>>>  			   (on another cpu) */
>>>  			xnlock_put_irqrestore(&nklock, s);
>>>  			goto retry_lock;
>>>  		}
>>> +		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>> +						   owner, set_claimed(owner, 1));
>>> +		if (likely(old == owner))
>>> +			break;
>>>  		owner = old;
>> -  	}
>> +       } while (!test_claimed(owner))
> 
> Your version slows down the contended case by performing redundant
> atomic cmpxchgs. My version puts minimal additional overhead in the
> !test_claimed case, but introduces no further atomic ops and avoids to
> much traffic on mutex->owner's cacheline when there are >1 waiters.

But your version slows down the common case where the owner will not
have changed... I do not care for making the uncommon case slower as
long as the common case is fast.

-- 
                                                 Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> Gilles Chanteperdrix wrote:
>>> Jan Kiszka wrote:
>>>> Patch 2 of my fast lock series actually also contained an attempt to fix
>>>> a race I spotted in the code that atomically sets the claimed bit. I
>>>> forgot about this fact and even, worse, I only replace the original race
>>>> with another one.
>>>>
>>>> So here comes a new attempt to fix the issue that the lock owner and/or
>>>> the claimed bit can change between trylock and the cmpxchg under nklock.
>>>> Please have a look and cross-check the logic.
>>>>
>>>> The patch applies on top of vanilla SVN, so my series has to be rebased
>>>> and the fix has to be ported to native as well - where we just found it
>>>> in the field.
>>> Ok. Got it.
>>>
>>>> Jan
>>>>
>>>> ---
>>>>  ksrc/skins/posix/mutex.h |   11 ++++++-----
>>>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>>>
>>>> Index: b/ksrc/skins/posix/mutex.h
>>>> ===================================================================
>>>> --- a/ksrc/skins/posix/mutex.h
>>>> +++ b/ksrc/skins/posix/mutex.h
>>>> @@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
>>>>  	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
>>>>  	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
>>>>  	xnlock_get_irqsave(&nklock, s);
>>>> +	owner = xnarch_atomic_intptr_get(mutex->owner);
>>> Bad, this makes two atomic ops. So, I would rather propose:
>> Err, how many archs perform special dances for atomic_read?
> 
> powerpc, arm >= 6

Actually arm >= 6 has a special atomic_set but no special atomic_read,
the problem comes rather from arm <= 5 where the owner is stored on an
uncached area.

-- 
                                                 Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> Gilles Chanteperdrix wrote:
>>> Jan Kiszka wrote:
>>>> Patch 2 of my fast lock series actually also contained an attempt to fix
>>>> a race I spotted in the code that atomically sets the claimed bit. I
>>>> forgot about this fact and even, worse, I only replace the original race
>>>> with another one.
>>>>
>>>> So here comes a new attempt to fix the issue that the lock owner and/or
>>>> the claimed bit can change between trylock and the cmpxchg under nklock.
>>>> Please have a look and cross-check the logic.
>>>>
>>>> The patch applies on top of vanilla SVN, so my series has to be rebased
>>>> and the fix has to be ported to native as well - where we just found it
>>>> in the field.
>>> Ok. Got it.
>>>
>>>> Jan
>>>>
>>>> ---
>>>>  ksrc/skins/posix/mutex.h |   11 ++++++-----
>>>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>>>
>>>> Index: b/ksrc/skins/posix/mutex.h
>>>> ===================================================================
>>>> --- a/ksrc/skins/posix/mutex.h
>>>> +++ b/ksrc/skins/posix/mutex.h
>>>> @@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
>>>>  	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
>>>>  	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
>>>>  	xnlock_get_irqsave(&nklock, s);
>>>> +	owner = xnarch_atomic_intptr_get(mutex->owner);
>>> Bad, this makes two atomic ops. So, I would rather propose:
>> Err, how many archs perform special dances for atomic_read?
> 
> powerpc, arm >= 6

None of both. All atomic_read for arm use plain ((v)->counter), powerpc
simply uses assembly to avoid volatile atomic_t types. Do you happen to
confuse atomic_read and set here?

> 
>>>>  	while(!test_claimed(owner)) {
>>> - while(!test_claimed(owner)) {
>>> + do {
>>>> -		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>>> -						   owner, set_claimed(owner, 1));
>>>> -		if (likely(old == owner))
>>>> -			break;
>>>> -		if (old == NULL) {
>>>> +		if (owner == NULL) {
>>>>  			/* Owner called fast mutex_unlock
>>>>  			   (on another cpu) */
>>>>  			xnlock_put_irqrestore(&nklock, s);
>>>>  			goto retry_lock;
>>>>  		}
>>>> +		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>>> +						   owner, set_claimed(owner, 1));
>>>> +		if (likely(old == owner))
>>>> +			break;
>>>>  		owner = old;
>>> -  	}
>>> +       } while (!test_claimed(owner))
>> Your version slows down the contended case by performing redundant
>> atomic cmpxchgs. My version puts minimal additional overhead in the
>> !test_claimed case, but introduces no further atomic ops and avoids to
>> much traffic on mutex->owner's cacheline when there are >1 waiters.
> 
> But your version slows down the common case where the owner will not
> have changed... I do not care for making the uncommon case slower as
> long as the common case is fast.

The tiny slowdown (a simple, typically cached read and test) is
negligible compared to the full slow path, even if there is only one
waiter. Atomic ops are heavier, sleeping is much heavier.

Jan

-- 
Siemens AG, Corporate Technology, CT SE 2
Corporate Competence Center Embedded Linux

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

Jan Kiszka wrote:
> Gilles Chanteperdrix wrote:
>> Jan Kiszka wrote:
>>> Gilles Chanteperdrix wrote:
>>>> Jan Kiszka wrote:
>>>>> Patch 2 of my fast lock series actually also contained an attempt to fix
>>>>> a race I spotted in the code that atomically sets the claimed bit. I
>>>>> forgot about this fact and even, worse, I only replace the original race
>>>>> with another one.
>>>>>
>>>>> So here comes a new attempt to fix the issue that the lock owner and/or
>>>>> the claimed bit can change between trylock and the cmpxchg under nklock.
>>>>> Please have a look and cross-check the logic.
>>>>>
>>>>> The patch applies on top of vanilla SVN, so my series has to be rebased
>>>>> and the fix has to be ported to native as well - where we just found it
>>>>> in the field.
>>>> Ok. Got it.
>>>>
>>>>> Jan
>>>>>
>>>>> ---
>>>>>  ksrc/skins/posix/mutex.h |   11 ++++++-----
>>>>>  1 file changed, 6 insertions(+), 5 deletions(-)
>>>>>
>>>>> Index: b/ksrc/skins/posix/mutex.h
>>>>> ===================================================================
>>>>> --- a/ksrc/skins/posix/mutex.h
>>>>> +++ b/ksrc/skins/posix/mutex.h
>>>>> @@ -134,17 +134,18 @@ static inline int pse51_mutex_timedlock_
>>>>>  	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
>>>>>  	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
>>>>>  	xnlock_get_irqsave(&nklock, s);
>>>>> +	owner = xnarch_atomic_intptr_get(mutex->owner);
>>>> Bad, this makes two atomic ops. So, I would rather propose:
>>> Err, how many archs perform special dances for atomic_read?
>> powerpc, arm >= 6
> 
> None of both. All atomic_read for arm use plain ((v)->counter), powerpc
> simply uses assembly to avoid volatile atomic_t types. Do you happen to
> confuse atomic_read and set here?
> 
>>>>>  	while(!test_claimed(owner)) {
>>>> - while(!test_claimed(owner)) {
>>>> + do {
>>>>> -		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>>>> -						   owner, set_claimed(owner, 1));
>>>>> -		if (likely(old == owner))
>>>>> -			break;
>>>>> -		if (old == NULL) {
>>>>> +		if (owner == NULL) {
>>>>>  			/* Owner called fast mutex_unlock
>>>>>  			   (on another cpu) */
>>>>>  			xnlock_put_irqrestore(&nklock, s);
>>>>>  			goto retry_lock;
>>>>>  		}
>>>>> +		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>>>> +						   owner, set_claimed(owner, 1));
>>>>> +		if (likely(old == owner))
>>>>> +			break;
>>>>>  		owner = old;
>>>> -  	}
>>>> +       } while (!test_claimed(owner))
>>> Your version slows down the contended case by performing redundant
>>> atomic cmpxchgs. My version puts minimal additional overhead in the
>>> !test_claimed case, but introduces no further atomic ops and avoids to
>>> much traffic on mutex->owner's cacheline when there are >1 waiters.
>> But your version slows down the common case where the owner will not
>> have changed... I do not care for making the uncommon case slower as
>> long as the common case is fast.
> 
> The tiny slowdown (a simple, typically cached read and test) is

Two tests, in fact, when reordering the alternative code a bit.

> negligible compared to the full slow path, even if there is only one
> waiter. Atomic ops are heavier, sleeping is much heavier.

OTOH, we can safe some text size which is precious as well. So I'm
convinced to go your way (with a modification):

---
 ksrc/skins/posix/mutex.h |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Index: b/ksrc/skins/posix/mutex.h
===================================================================
--- a/ksrc/skins/posix/mutex.h
+++ b/ksrc/skins/posix/mutex.h
@@ -134,7 +134,7 @@ static inline int pse51_mutex_timedlock_
 	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
 	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
 	xnlock_get_irqsave(&nklock, s);
-	while(!test_claimed(owner)) {
+	do {
 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
 						   owner, set_claimed(owner, 1));
 		if (likely(old == owner))
@@ -146,7 +146,7 @@ static inline int pse51_mutex_timedlock_
 			goto retry_lock;
 		}
 		owner = old;
-	}
+	} while (!test_claimed(owner));
 
 	xnsynch_set_owner(&mutex->synchbase, clear_claimed(owner));
 	++mutex->sleepers;

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> OTOH, we can safe some text size which is precious as well. So I'm
> convinced to go your way (with a modification):

My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
claimed, which is as least as much a common case as a currently
unclaimed mutex. Need to think a bit. But I think a good solution is to
re-read only if the mutex has been seen as already claimed.

-- 
                                                 Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> OTOH, we can safe some text size which is precious as well. So I'm
>> convinced to go your way (with a modification):
> 
> My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
> claimed, which is as least as much a common case as a currently
> unclaimed mutex. Need to think a bit. But I think a good solution is to
> re-read only if the mutex has been seen as already claimed.

That makes no difference as then we will go through the cmpxchg path anyway.

There is _no_ way around re-reading under nklock, all we can avoid is
atomic cmpxchg in the case of >1 waiters. But that would come at the
price of more complexity for all waiter.

However, let's find some solution. I bet things will look different
again when we start fiddling with a generic lock + the additional bit to
replace XNWAKEN.

Jan

-- 
Siemens AG, Corporate Technology, CT SE 2
Corporate Competence Center Embedded Linux

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> Gilles Chanteperdrix wrote:
>> Jan Kiszka wrote:
>>> OTOH, we can safe some text size which is precious as well. So I'm
>>> convinced to go your way (with a modification):
>> My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
>> claimed, which is as least as much a common case as a currently
>> unclaimed mutex. Need to think a bit. But I think a good solution is to
>> re-read only if the mutex has been seen as already claimed.
> 
> That makes no difference as then we will go through the cmpxchg path anyway.
> 
> There is _no_ way around re-reading under nklock, all we can avoid is
> atomic cmpxchg in the case of >1 waiters. But that would come at the
> price of more complexity for all waiter.
> 
> However, let's find some solution. I bet things will look different
> again when we start fiddling with a generic lock + the additional bit to
> replace XNWAKEN.

What I meant is that if the claimed bit is already set, we can avoid the
cmpxchg altogether, which was the intent of the original code. So I propose
the following version:

	if(test_claimed(owner))
		owner = xnarch_atomic_intptr_get(mutex->owner);
	while(!test_claimed(owner)) {
		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
						   owner, set_claimed(owner, 1));
		if (likely(old == owner))
			break;
		if (old == NULL) {
			/* Owner called fast mutex_unlock
			   (on another cpu) */
			xnlock_put_irqrestore(&nklock, s);
			goto retry_lock;
		}
		owner = old;
	}

The compiler rearranges things correctly (at least on ARM), and avoids the
redundant test.

-- 
					    Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

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

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> Gilles Chanteperdrix wrote:
>>> Jan Kiszka wrote:
>>>> OTOH, we can safe some text size which is precious as well. So I'm
>>>> convinced to go your way (with a modification):
>>> My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
>>> claimed, which is as least as much a common case as a currently
>>> unclaimed mutex. Need to think a bit. But I think a good solution is to
>>> re-read only if the mutex has been seen as already claimed.
>> That makes no difference as then we will go through the cmpxchg path anyway.
>>
>> There is _no_ way around re-reading under nklock, all we can avoid is
>> atomic cmpxchg in the case of >1 waiters. But that would come at the
>> price of more complexity for all waiter.
>>
>> However, let's find some solution. I bet things will look different
>> again when we start fiddling with a generic lock + the additional bit to
>> replace XNWAKEN.
> 
> What I meant is that if the claimed bit is already set, we can avoid the
> cmpxchg altogether, which was the intent of the original code. So I propose
> the following version:
> 
> 	if(test_claimed(owner))
> 		owner = xnarch_atomic_intptr_get(mutex->owner);

This version lacks a test for owner == 0 here, otherwise you re-create
my old bug that bite me today.

> 	while(!test_claimed(owner)) {
> 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
> 						   owner, set_claimed(owner, 1));
> 		if (likely(old == owner))
> 			break;
> 		if (old == NULL) {
> 			/* Owner called fast mutex_unlock
> 			   (on another cpu) */
> 			xnlock_put_irqrestore(&nklock, s);
> 			goto retry_lock;
> 		}
> 		owner = old;
> 	}
> 
> The compiler rearranges things correctly (at least on ARM), and avoids the
> redundant test.
> 

My latest concern remains: Is all this additional complexity, are all
these conditional branches and the text size increase worth the effort?
How much cycles or micoseconds would be gain on the most suffering
architecture?

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 258 bytes --]

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> Gilles Chanteperdrix wrote:
>> Jan Kiszka wrote:
>>> Gilles Chanteperdrix wrote:
>>>> Jan Kiszka wrote:
>>>>> OTOH, we can safe some text size which is precious as well. So I'm
>>>>> convinced to go your way (with a modification):
>>>> My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
>>>> claimed, which is as least as much a common case as a currently
>>>> unclaimed mutex. Need to think a bit. But I think a good solution is to
>>>> re-read only if the mutex has been seen as already claimed.
>>> That makes no difference as then we will go through the cmpxchg path anyway.
>>>
>>> There is _no_ way around re-reading under nklock, all we can avoid is
>>> atomic cmpxchg in the case of >1 waiters. But that would come at the
>>> price of more complexity for all waiter.
>>>
>>> However, let's find some solution. I bet things will look different
>>> again when we start fiddling with a generic lock + the additional bit to
>>> replace XNWAKEN.
>> What I meant is that if the claimed bit is already set, we can avoid the
>> cmpxchg altogether, which was the intent of the original code. So I propose
>> the following version:
>>
>> 	if(test_claimed(owner))
>> 		owner = xnarch_atomic_intptr_get(mutex->owner);
> 
> This version lacks a test for owner == 0 here, otherwise you re-create
> my old bug that bite me today.

Ok, so jumping in the middle of the loop is the best thing to do then.

> 
>> 	while(!test_claimed(owner)) {
>> 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>> 						   owner, set_claimed(owner, 1));
>> 		if (likely(old == owner))
>> 			break;
>> 		if (old == NULL) {
>> 			/* Owner called fast mutex_unlock
>> 			   (on another cpu) */
>> 			xnlock_put_irqrestore(&nklock, s);
>> 			goto retry_lock;
>> 		}
>> 		owner = old;
>> 	}
>>
>> The compiler rearranges things correctly (at least on ARM), and avoids the
>> redundant test.
>>
> 
> My latest concern remains: Is all this additional complexity, are all
> these conditional branches and the text size increase worth the effort?
> How much cycles or micoseconds would be gain on the most suffering
> architecture?

Since the else and the while are folded together and the loop becomes
post-tested, and with the help of conditional instructions, I do not
think there is much more conditional branch (we need to to jump over
the while loop anyway). However avoiding the cmpxchg is a real gain,
since it is implemented as irq save/irq restore on an old arm.

	if(test_claimed(owner)) {
		old = xnarch_atomic_intptr_get(mutex->owner);
		goto test_old;
	}
	while(!test_claimed(owner)) {
		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
						   owner, set_claimed(owner, 1));
		if (likely(old == owner))
			break;
	test_old:
		if (old == NULL) {
			/* Owner called fast mutex_unlock
			   (on another cpu) */
			xnlock_put_irqrestore(&nklock, s);
			goto retry_lock;
		}
		owner = old;
	}


-- 
					    Gilles.

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Jan Kiszka]

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

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>> Gilles Chanteperdrix wrote:
>>> Jan Kiszka wrote:
>>>> Gilles Chanteperdrix wrote:
>>>>> Jan Kiszka wrote:
>>>>>> OTOH, we can safe some text size which is precious as well. So I'm
>>>>>> convinced to go your way (with a modification):
>>>>> My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
>>>>> claimed, which is as least as much a common case as a currently
>>>>> unclaimed mutex. Need to think a bit. But I think a good solution is to
>>>>> re-read only if the mutex has been seen as already claimed.
>>>> That makes no difference as then we will go through the cmpxchg path anyway.
>>>>
>>>> There is _no_ way around re-reading under nklock, all we can avoid is
>>>> atomic cmpxchg in the case of >1 waiters. But that would come at the
>>>> price of more complexity for all waiter.
>>>>
>>>> However, let's find some solution. I bet things will look different
>>>> again when we start fiddling with a generic lock + the additional bit to
>>>> replace XNWAKEN.
>>> What I meant is that if the claimed bit is already set, we can avoid the
>>> cmpxchg altogether, which was the intent of the original code. So I propose
>>> the following version:
>>>
>>> 	if(test_claimed(owner))
>>> 		owner = xnarch_atomic_intptr_get(mutex->owner);
>> This version lacks a test for owner == 0 here, otherwise you re-create
>> my old bug that bite me today.
> 
> Ok, so jumping in the middle of the loop is the best thing to do then.
> 
>>> 	while(!test_claimed(owner)) {
>>> 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>> 						   owner, set_claimed(owner, 1));
>>> 		if (likely(old == owner))
>>> 			break;
>>> 		if (old == NULL) {
>>> 			/* Owner called fast mutex_unlock
>>> 			   (on another cpu) */
>>> 			xnlock_put_irqrestore(&nklock, s);
>>> 			goto retry_lock;
>>> 		}
>>> 		owner = old;
>>> 	}
>>>
>>> The compiler rearranges things correctly (at least on ARM), and avoids the
>>> redundant test.
>>>
>> My latest concern remains: Is all this additional complexity, are all
>> these conditional branches and the text size increase worth the effort?
>> How much cycles or micoseconds would be gain on the most suffering
>> architecture?
> 
> Since the else and the while are folded together and the loop becomes
> post-tested, and with the help of conditional instructions, I do not
> think there is much more conditional branch (we need to to jump over
> the while loop anyway). However avoiding the cmpxchg is a real gain,
> since it is implemented as irq save/irq restore on an old arm.
> 
> 	if(test_claimed(owner)) {
> 		old = xnarch_atomic_intptr_get(mutex->owner);
> 		goto test_old;
> 	}
> 	while(!test_claimed(owner)) {
> 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
> 						   owner, set_claimed(owner, 1));
> 		if (likely(old == owner))
> 			break;
> 	test_old:
> 		if (old == NULL) {
> 			/* Owner called fast mutex_unlock
> 			   (on another cpu) */
> 			xnlock_put_irqrestore(&nklock, s);
> 			goto retry_lock;
> 		}
> 		owner = old;
> 	}

Should work now, but the beautifulness of the code suffers a bit...

What about making the expected compiler optimizations explicit?

	if (test_claimed(owner)) {
		old = xnarch_atomic_intptr_get(mutex->owner);
		goto test_no_owner;
	}
	do {
		old = xnarch_atomic_intptr_cmpxchg(mutex->owner, owner,
						   set_claimed(owner, 1));
		if (likely(old == owner))
			break;
	test_no_owner:
		if (old == NULL) {
			/* Owner called fast mutex_unlock
			   (on another cpu) */
			xnlock_put_irqrestore(&nklock, s);
			goto retry_lock;
		}
		owner = old;
	} while (!test_claimed(owner));

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 257 bytes --]

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> Gilles Chanteperdrix wrote:
>> Jan Kiszka wrote:
>>> Gilles Chanteperdrix wrote:
>>>> Jan Kiszka wrote:
>>>>> Gilles Chanteperdrix wrote:
>>>>>> Jan Kiszka wrote:
>>>>>>> OTOH, we can safe some text size which is precious as well. So I'm
>>>>>>> convinced to go your way (with a modification):
>>>>>> My approach sucks: we get a silly atomic_cmpxchg if the mutex is already
>>>>>> claimed, which is as least as much a common case as a currently
>>>>>> unclaimed mutex. Need to think a bit. But I think a good solution is to
>>>>>> re-read only if the mutex has been seen as already claimed.
>>>>> That makes no difference as then we will go through the cmpxchg path anyway.
>>>>>
>>>>> There is _no_ way around re-reading under nklock, all we can avoid is
>>>>> atomic cmpxchg in the case of >1 waiters. But that would come at the
>>>>> price of more complexity for all waiter.
>>>>>
>>>>> However, let's find some solution. I bet things will look different
>>>>> again when we start fiddling with a generic lock + the additional bit to
>>>>> replace XNWAKEN.
>>>> What I meant is that if the claimed bit is already set, we can avoid the
>>>> cmpxchg altogether, which was the intent of the original code. So I propose
>>>> the following version:
>>>>
>>>> 	if(test_claimed(owner))
>>>> 		owner = xnarch_atomic_intptr_get(mutex->owner);
>>> This version lacks a test for owner == 0 here, otherwise you re-create
>>> my old bug that bite me today.
>> Ok, so jumping in the middle of the loop is the best thing to do then.
>>
>>>> 	while(!test_claimed(owner)) {
>>>> 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>>>> 						   owner, set_claimed(owner, 1));
>>>> 		if (likely(old == owner))
>>>> 			break;
>>>> 		if (old == NULL) {
>>>> 			/* Owner called fast mutex_unlock
>>>> 			   (on another cpu) */
>>>> 			xnlock_put_irqrestore(&nklock, s);
>>>> 			goto retry_lock;
>>>> 		}
>>>> 		owner = old;
>>>> 	}
>>>>
>>>> The compiler rearranges things correctly (at least on ARM), and avoids the
>>>> redundant test.
>>>>
>>> My latest concern remains: Is all this additional complexity, are all
>>> these conditional branches and the text size increase worth the effort?
>>> How much cycles or micoseconds would be gain on the most suffering
>>> architecture?
>> Since the else and the while are folded together and the loop becomes
>> post-tested, and with the help of conditional instructions, I do not
>> think there is much more conditional branch (we need to to jump over
>> the while loop anyway). However avoiding the cmpxchg is a real gain,
>> since it is implemented as irq save/irq restore on an old arm.
>>
>> 	if(test_claimed(owner)) {
>> 		old = xnarch_atomic_intptr_get(mutex->owner);
>> 		goto test_old;
>> 	}
>> 	while(!test_claimed(owner)) {
>> 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
>> 						   owner, set_claimed(owner, 1));
>> 		if (likely(old == owner))
>> 			break;
>> 	test_old:
>> 		if (old == NULL) {
>> 			/* Owner called fast mutex_unlock
>> 			   (on another cpu) */
>> 			xnlock_put_irqrestore(&nklock, s);
>> 			goto retry_lock;
>> 		}
>> 		owner = old;
>> 	}
> 
> Should work now, but the beautifulness of the code suffers a bit...
> 
> What about making the expected compiler optimizations explicit?

Yes, of course.

-- 
                                                 Gilles.

[Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit - v2

[Jan Kiszka]

[ The refactored version according to our discussion. ]

This patch fixes the race when the claimed bit changes between the lock
less check an the entry of the nklock-protected section.

---
 ksrc/skins/posix/mutex.h |    9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

Index: b/ksrc/skins/posix/mutex.h
===================================================================
--- a/ksrc/skins/posix/mutex.h
+++ b/ksrc/skins/posix/mutex.h
@@ -134,11 +134,16 @@ static inline int pse51_mutex_timedlock_
 	/* Set bit 0, so that mutex_unlock will know that the mutex is claimed.
 	   Hold the nklock, for mutual exclusion with slow mutex_unlock. */
 	xnlock_get_irqsave(&nklock, s);
-	while(!test_claimed(owner)) {
+	if (test_claimed(owner)) {
+		old = xnarch_atomic_intptr_get(mutex->owner);
+		goto test_no_owner;
+	}
+	do {
 		old = xnarch_atomic_intptr_cmpxchg(mutex->owner,
 						   owner, set_claimed(owner, 1));
 		if (likely(old == owner))
 			break;
+	  test_no_owner:
 		if (old == NULL) {
 			/* Owner called fast mutex_unlock
 			   (on another cpu) */
@@ -146,7 +151,7 @@ static inline int pse51_mutex_timedlock_
 			goto retry_lock;
 		}
 		owner = old;
-	}
+	} while (!test_claimed(owner));
 
 	xnsynch_set_owner(&mutex->synchbase, clear_claimed(owner));
 	++mutex->sleepers;

Re: [Xenomai-core] [PATCH] POSIX: Fix race when setting claimed bit - v2

[Gilles Chanteperdrix]

Jan Kiszka wrote:
> [ The refactored version according to our discussion. ]
> 
> This patch fixes the race when the claimed bit changes between the lock
> less check an the entry of the nklock-protected section.

Applied, thanks.

-- 
					    Gilles.