[Vm-dev] Clarification needed for sqCompareAndSwapRes
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Wed Apr 23 23:23:21 UTC 2014
2014-04-23 11:34 GMT+02:00 Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com>:
>
>
>
> 2014-04-23 2:27 GMT+02:00 Eliot Miranda <eliot.miranda at gmail.com>:
>
>>
>>
>>
>>
>> On Tue, Apr 22, 2014 at 5:23 PM, Eliot Miranda <eliot.miranda at gmail.com>wrote:
>>
>>>
>>>
>>>
>>> On Tue, Apr 22, 2014 at 4:43 PM, John McIntosh <
>>> johnmci at smalltalkconsulting.com> wrote:
>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Tue, Apr 22, 2014 at 4:10 PM, Eliot Miranda <
>>>> eliot.miranda at gmail.com> wrote:
>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Apr 22, 2014 at 3:51 PM, John McIntosh <
>>>>> johnmci at smalltalkconsulting.com> wrote:
>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Apr 22, 2014 at 3:21 PM, Eliot Miranda <
>>>>>> eliot.miranda at gmail.com> wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Apr 22, 2014 at 3:18 PM, Nicolas Cellier <
>>>>>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> 2014-04-23 0:12 GMT+02:00 Eliot Miranda <eliot.miranda at gmail.com>:
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Hi Esteban,
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Tue, Apr 22, 2014 at 2:40 PM, Esteban Lorenzano <
>>>>>>>>> estebanlm at gmail.com> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On 22 Apr 2014, at 23:34, Nicolas Cellier <
>>>>>>>>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> 2014-04-22 12:47 GMT+02:00 Esteban Lorenzano <estebanlm at gmail.com
>>>>>>>>>> >:
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> thanks Nicolas for your words.
>>>>>>>>>>> now… let’s go back to our common passion: to help this community
>>>>>>>>>>> on having the best vm possible :)
>>>>>>>>>>>
>>>>>>>>>>> Esteban
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>> Nah, concerning the best vm I feel disqualified, I let Eliot care
>>>>>>>>>> of it ;)
>>>>>>>>>>
>>>>>>>>>> We just want a better VM with a few hacks, corrections and
>>>>>>>>>> support for some specific Pharo libraries/extensions.
>>>>>>>>>> Eliot, do you agree that the sqCompareAndSwapRes provided #ifdefTARGET_OS_IS_IPHONE is buggish (see below)?
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>> To be honest I don't know. I don't have an iPhone development
>>>>>>>>> library handy. John McIntosh write the code and he's more than competent.
>>>>>>>>> I'd rather leave this to others with experience of the platform to check.
>>>>>>>>> I /think/ the desired semantics are clear enough. If they're not I can
>>>>>>>>> fix that. But I want to leave writing the correct code for the iPhone to
>>>>>>>>> those that are actually using the platform. Forgive me.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> OK, thanks Eliot, then I'll trust what the comments say.
>>>>>>>> If John is able to confirm that'll be better, but I think I get a
>>>>>>>> good picture of the problem now.
>>>>>>>> I cannot build either, but once Esteban can test it and if it works
>>>>>>>> OK, then we'll propose a fix for integration in your svn branch, sounds
>>>>>>>> right?
>>>>>>>>
>>>>>>>
>>>>>>> perfect, thanks !
>>>>>>>
>>>>>>
>>>>>> Well this is all very interesting, since the original version I sent
>>>>>> to Eliot dated from July 2010, and it was
>>>>>>
>>>>>> # define sqCompareAndSwapRes(var,old,new,res) res = var;
>>>>>> OSAtomicCompareAndSwap32(old, new, &var)
>>>>>>
>>>>>
>>>>> which I changed to read
>>>>>
>>>>> # define sqCompareAndSwap(var,old,new) OSAtomicCompareAndSwap32(old,
>>>>> new, &var)
>>>>> /* N.B. This is not atomic in fetching var's old value :( */
>>>>> # define sqCompareAndSwapRes(var,old,new,res) do { res = var; if
>>>>> (OSAtomicCompareAndSwap32(old, new, &var)) res = new; } while (0)
>>>>>
>>>>> because e.g.
>>>>>
>>>>> if (expr) sqCompareAndSwap(foo,bar,baz)
>>>>>
>>>>> will /not/ work as intended if written as
>>>>>
>>>>> # define sqCompareAndSwapRes(var,old,new,res) res = var; if
>>>>> (OSAtomicCompareAndSwap32(old, new, &var))
>>>>>
>>>>> But this does seem broken. How is res atomically set to var's
>>>>> previous value? There's a suspension point between "res = var" and
>>>>> OSAtomicCompareAndSwap32, so res could end up being assigned a stale
>>>>> version of var's previous value.
>>>>>
>>>>>
>>>> ? in any case, res
>>>>
>>>> * is set to the previous value of var.
>>>>
>>>> Er so yes res would get the previous value of var. Assuming it's not
>>>> stale, do you mean it could be stale where two processes hit the semaphore
>>>> and res is not atomically set correctly?
>>>>
>>>
>>> Yes. Here's the timeline:
>>>
>>> Var: 0
>>> P1 P2
>>> res := var (res = 0)
>>> (suspended)
>>> res := var (now res = 0)
>>> OSAtomicCompareAndSwap32(0,2,&var) (now var = 2)
>>> OSAtomicCompareAndSwap32(0,2,&var)
>>> (still var = 2)
>>> res = 0, but should = 2
>>>
>>> And of course there are lots of other possible interleavings.
>>>
>>>
>>> Or does the intel assembler match the story?
>>>>
>>>
>>> <blush>no</blush>. It suffers exactly the same flaw.
>>>
>>
>> This should be redefined to answer true if it succeeded, false if it
>> didn't and not load the previous value. The intel instruction can be made
>> to do that. Of course if the intrinsics are available we can simply use
>> them.
>>
>>
>
> Ah, yes, I would prefer that.
> That's what I woud have written for an OS specific lockSignalQueue
>
> static inline void lockSignalQueue()
> {
> /* spin to obtain a lock */
> do {
> sqLowLevelMFence();
> } while (! OSAtomicCompareInt32( 0, 1, &sigLock));
> }
>
> So if we redefine the OS agnostic atomic operation
> sqCompareAndSwap(var,old,new) to just return a bool (= 0 if fail, != 0 if
> succeeded) then we're done.
>
> static inline void lockSignalQueue()
> {
> /* spin to obtain a lock */
> do {
> sqLowLevelMFence();
> } while (! sqCompareAndSwap(sigLock,0,1));
> }
>
>
>
And if we go with this definition to answer true on success, the gcc >= 4.1
intrinsic used by Tim for arm is just fine:
I came up with these solutions:
#if defined TARGET_OS_IS_IPHONE
# define sqCompareAndSwap(var,old,new) OSAtomicCompareAndSwap32(old, new,
&var)
#elif defined _MSC_VER
# include <intrin.h>
# define sqCompareAndSwap(var,old,new) (_InterlockedCompareExchange(ptr,
newval, oldval)==oldval)
#elif defined(__GNUC__) && ( __GNUC__ > 4 || (__GNUC__ == 4 &&
__GNUC_MINOR__ >= 1) )
/* use the gcc inbuilt functions detailed in
http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html */
# define sqCompareAndSwap(var,old,new) __sync_bool_compare_and_swap(&(var),
(old), (new))
#else
/* Dear implementor, you have choices. Google atomic compare and swap and
you will
* find a number of implementations for other architectures.
*/
# error atomic compare/swap of 32-bit variables not yet defined for this
platfom
#endif
I cannot write the asm( ... ) inclusion if ever gcc < 4.1,
this gcc asm macro syntax is above my skills, but maybe Eliot can do it
(it's just a setz al; xor ah,ah; to be added after the lock cmpxchg)
Then, starting at svn rev 2847, I modified the
sqCompareAndSwap/sqCompareAndSwapRes send sites.
Could you check?
===================================================================
--- unix/vm/sqUnixITimerTickerHeartbeat.c (revision 2847)
+++ unix/vm/sqUnixITimerTickerHeartbeat.c (working copy)
@@ -483,14 +483,8 @@
}
#if !defined(SA_NODEFER)
- { int zero = 0;
- int previouslyHandlingHeartbeat;
-
sqCompareAndSwapRes(handling_heartbeat,zero,1,previouslyHandlingHeartbeat);
- if (previouslyHandlingHeartbeat)
+ if( ! sqCompareAndSwapRes(handling_heartbeat,0,1))
return;
- }
-
- handling_heartbeat = 1;
#endif
heartbeat();
===================================================================
--- unix/vm/sqUnixITimerHeartbeat.c (revision 2847)
+++ unix/vm/sqUnixITimerHeartbeat.c (working copy)
@@ -355,14 +355,8 @@
heartbeat_handler(int sig, struct siginfo *sig_info, void *context)
{
#if !defined(SA_NODEFER)
- { int zero = 0;
- int previouslyHandlingHeartbeat;
-
sqCompareAndSwapRes(handling_heartbeat,zero,1,previouslyHandlingHeartbeat);
- if (previouslyHandlingHeartbeat)
+ if (! sqCompareAndSwap(handling_heartbeat,0,1))
return;
- }
-
- handling_heartbeat = 1;
#endif
heartbeat();
===================================================================
--- unix/misc/threadValidate/sqTicker.c (revision 2847)
+++ unix/misc/threadValidate/sqTicker.c (working copy)
@@ -213,9 +213,7 @@
if (async[i].tickee
&& !async[i].inProgress
&& utcMicrosecondClock >= async[i].tickeeDeadlineUsecs) {
- int previousInProgress;
-
sqCompareAndSwapRes(async[i].inProgress,0,1,previousInProgress);
- if (previousInProgress == 0) {
+ if( sqCompareAndSwap(async[i].inProgress,0,1) ) {
assert(async[i].inProgress);
async[i].tickeeDeadlineUsecs +=
async[i].tickeePeriodUsecs;
async[i].tickee();
===================================================================
--- unix/misc/threadValidate/sqUnixHeartbeat.c (revision 2847)
+++ unix/misc/threadValidate/sqUnixHeartbeat.c (working copy)
@@ -412,13 +412,8 @@
}
#if !defined(SA_NODEFER)
- { int zeroAndPreviousHandlingHeartbeat = 0;
-
sqCompareAndSwap(handling_heartbeat,zeroAndPreviousHandlingHeartbeat,1);
- if (zeroAndPreviousHandlingHeartbeat)
+ if( ! sqCompareAndSwap(handling_heartbeat,0,1))
return;
- }
-
- handling_heartbeat = 1;
#endif
heartbeat();
===================================================================
--- Cross/vm/sqTicker.c (revision 2847)
+++ Cross/vm/sqTicker.c (working copy)
@@ -246,9 +246,7 @@
if (async[i].tickee
&& !async[i].inProgress
&& utcMicrosecondClock >= async[i].tickeeDeadlineUsecs) {
- int previousInProgress;
-
sqCompareAndSwapRes(async[i].inProgress,0,1,previousInProgress);
- if (previousInProgress == 0) {
+ if( sqCompareAndSwap(async[i].inProgress,0,1) {
assert(async[i].inProgress);
if (async[i].tickeeDeadlineUsecs +
HiccupThreshold
< utcMicrosecondClock)
===================================================================
--- Cross/vm/sq.h (revision 2847)
+++ Cross/vm/sq.h (working copy)
@@ -276,10 +276,9 @@
* threads after myindex is obtained but before asprintf completes we can
get
* two threads using the same entry. But this is good enough for now.
*/
-#define THRLOG(...) do { int myidx, oldidx; \
+#define THRLOG(...) do { int myidx; \
do { myidx = thrlogidx; \
-
sqCompareAndSwapRes(thrlogidx,myidx,(myidx+1)&(THRLOGSZ-1),oldidx); \
- } while (myidx != oldidx); \
+ } while( !
sqCompareAndSwap(thrlogidx,myidx,(myidx+1)&(THRLOGSZ-1)i)); \
if (thrlog[myidx]) free(thrlog[myidx]); \
asprintf(thrlog + myidx, __VA_ARGS__); \
} while (0)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20140424/de463924/attachment-0001.htm
More information about the Vm-dev
mailing list