[Vm-dev] Clarification needed for sqCompareAndSwapRes

Eliot Miranda eliot.miranda at gmail.com
Wed Apr 23 00:27:19 UTC 2014 

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.


>
>
>>
>>
>>>
>>>
>>>> which I believe matched the spirit of:
>>>>
>>>>  * sqCompareAndSwapRes(var,old,new,res) arranges atomically that if
>>>> var's value
>>>>
>>>>  * is equal to old, then var's value is set to new, and that in any
>>>> case, res
>>>>
>>>>  * is set to the previous value of var.
>>>>
>>>>
>>>> Also consider this, but ensure you have the correct version which I
>>>> don't know
>>>>
>>>>
>>>>
>>>> http://opensource.apple.com/source/Libc/Libc-594.1.4/arm/sys/OSAtomic-v4.c
>>>>
>>>>
>>>>
>>>> As far as I know the old code works as expected on iOS 7 so I"m
>>>> wondering if the story about what this function should do matches the intel
>>>> assembler?
>>>>
>>>>
>>>>>
>>>>>>
>>>>>>   Do you agree with my proposed fix, or have a better idea?
>>>>>>>>
>>>>>>>>
>>>>>>>> I will test it on iPad as soon as I can (busy days)… if that helps
>>>>>>>> :)
>>>>>>>>  can you propose a pull request?
>>>>>>>>
>>>>>>>> cheers,
>>>>>>>> Esteban
>>>>>>>>
>>>>>>>>
>>>>>>>> Thanks
>>>>>>>>
>>>>>>>>
>>>>>>>>>  On 22 Apr 2014, at 11:14, Nicolas Cellier <
>>>>>>>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>>>>>>>>
>>>>>>>>> I want to publicly apologize for sounding harsh toward Esteban.
>>>>>>>>> I think he found a great bug and should be thanked and rewarded
>>>>>>>>> for that, rather than bashed for a maybe incomplete fix.
>>>>>>>>> It was miss-communcation from my part, and I must tell that I wish
>>>>>>>>> we had more Esteban for doing the hard work on pharo-vm branch.
>>>>>>>>>
>>>>>>>>> Nicolas
>>>>>>>>>
>>>>>>>>> 2014-04-22 1:01 GMT+02:00 Nicolas Cellier <
>>>>>>>>> nicolas.cellier.aka.nice at gmail.com>:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> 2014-04-22 1:00 GMT+02:00 Nicolas Cellier <
>>>>>>>>>> nicolas.cellier.aka.nice at gmail.com>:
>>>>>>>>>>
>>>>>>>>>>  2014-04-22 0:48 GMT+02:00 Nicolas Cellier <
>>>>>>>>>>> nicolas.cellier.aka.nice at gmail.com>:
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> 2014-04-22 0:40 GMT+02:00 Nicolas Cellier <
>>>>>>>>>>>> nicolas.cellier.aka.nice at gmail.com>:
>>>>>>>>>>>>
>>>>>>>>>>>> In platforms/Cross/vm/sqAtomicOps.h a comment tells
>>>>>>>>>>>>>
>>>>>>>>>>>>> * sqCompareAndSwapRes(var,old,new,res) arranges atomically
>>>>>>>>>>>>> that if var's value
>>>>>>>>>>>>> * is equal to old, then var's value is set to new, and that in
>>>>>>>>>>>>> any case, res
>>>>>>>>>>>>> * is set to the previous value of var.
>>>>>>>>>>>>>
>>>>>>>>>>>>> But for some implementation, if var==old, res is first set to
>>>>>>>>>>>>> var (old) then to new which is the new value of var:
>>>>>>>>>>>>>
>>>>>>>>>>>>> #if defined(__GNUC__) && (defined(i386) || defined(__i386) || defined(__i386__) || defined(_X86_))
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>  #ifdef TARGET_OS_IS_IPHONE
>>>>>>>>>>>>> # 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)
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Indeed, comparedAndSwap32 will answer true if var==old as
>>>>>>>>>>>>> explained here
>>>>>>>>>>>>> https://www.mikeash.com/pyblog/friday-qa-2011-03-04-a-tour-of-osatomic.html
>>>>>>>>>>>>>
>>>>>>>>>>>>> That is going to be a problem in lockSignalQueue in
>>>>>>>>>>>>> ./platforms/Cross/vm/sqExternalSemaphores.c
>>>>>>>>>>>>> because variable old will then be 1 in all cases and the loop
>>>>>>>>>>>>> won't exit once the lock acquired:
>>>>>>>>>>>>>
>>>>>>>>>>>>> static inline void lockSignalQueue()
>>>>>>>>>>>>> {
>>>>>>>>>>>>>     volatile int old;
>>>>>>>>>>>>>     /* spin to obtain a lock */
>>>>>>>>>>>>>
>>>>>>>>>>>>>     do {
>>>>>>>>>>>>>         sqLowLevelMFence();
>>>>>>>>>>>>>         sqCompareAndSwapRes(sigLock, 0, 1, old );
>>>>>>>>>>>>>     } while (old != 0);
>>>>>>>>>>>>>
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>> Knowing we are on iphone, I would just write it:
>>>>>>>>>>>>>
>>>>>>>>>>>>> static inline void lockSignalQueue()
>>>>>>>>>>>>> {
>>>>>>>>>>>>>     /* spin to obtain a lock */
>>>>>>>>>>>>>     do {
>>>>>>>>>>>>>         sqLowLevelMFence();
>>>>>>>>>>>>>     } while (! OSAtomicCompareInt32(sigLock, 0, 1));
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>> ahem, of course, the arguments are not in the same order:
>>>>>>>>>>>>      while (! OSAtomicCompareInt32( 0, 1, &sigLock))
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>> Esteban "fixed" that by swapping the arguments in the macrosqCompareAndSwapRes
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>> Here is a ref to the "fix":
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> https://github.com/nicolas-cellier-aka-nice/pharo-vm/commit/7f3f991283344d4cf0aa6a50b8615416062ec381
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> argh,
>>>>>>>>>> https://github.com/pharo-project/pharo-vm/commit/7f3f991283344d4cf0aa6a50b8615416062ec381
>>>>>>>>>> those forks are driving me nuts
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>    But IMO, this is wrong, as I understand it, it completely
>>>>>>>>>>>>> desactivates the lock...
>>>>>>>>>>>>>
>>>>>>>>>>>>> I did not know about the problem, but found the diff with
>>>>>>>>>>>>> Eliot's branch very suspicious so I opened
>>>>>>>>>>>>>
>>>>>>>>>>>>> https://pharo.fogbugz.com/f/cases/13199/Stinky-argument-inversion-of-atomic-swap-MACRO-for-iphone-gcc-branch
>>>>>>>>>>>>>
>>>>>>>>>>>>> and pulled a request
>>>>>>>>>>>>> https://github.com/pharo-project/pharo-vm/pull/38 for
>>>>>>>>>>>>> restoring (the supposedly wrong) Eliot's version.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Now I need some guru advice, because this kind of code is
>>>>>>>>>>>>> brainfucking (especially when old in sender is not old in sendee).
>>>>>>>>>>>>>
>>>>>>>>>>>>> Do you agree that TARGET_OS_IS_IPHONE branch is wrong?
>>>>>>>>>>>>> Do you agree that Esteban's fix is wrong?
>>>>>>>>>>>>> What do you suggest for a fix?
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>> maybe
>>>>>>>>>>>>
>>>>>>>>>>>> # define sqCompareAndSwapRes(var,old,new,res) do { res = var; if (OSAtomicCompareAndSwap32(old, new, &var)) res = old; } while (0)
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>> Thanks
>>>>>>>>>>>>>
>>>>>>>>>>>>> Nicolas
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> best,
>>>>>>> Eliot
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> best,
>>>>> Eliot
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>>
>>>> ===========================================================================
>>>> John M. McIntosh <johnmci at smalltalkconsulting.com>
>>>> Corporate Smalltalk Consulting Ltd. Twitter: squeaker68882
>>>>
>>>> ===========================================================================
>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> best,
>>> Eliot
>>>
>>>
>>
>>
>> --
>>
>> ===========================================================================
>> John M. McIntosh <johnmci at smalltalkconsulting.com>
>> Corporate Smalltalk Consulting Ltd. Twitter: squeaker68882
>>
>> ===========================================================================
>>
>>
>>
>
>
> --
> best,
> Eliot
>



-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20140422/e1d2727e/attachment-0001.htm

More information about the Vm-dev mailing list