On 3/15/07, Johnny Billquist <bqt@softjar.se> wrote:
> Bang Jun-Young wrote:
> > On 3/15/07, Johnny Billquist <bqt@softjar.se> wrote:
> >
> >> Bang Jun-Young wrote:
> >> > On 3/15/07, Johnny Billquist <bqt@softjar.se> wrote:
> >> >
> >> >> Isn't the whole point of a function called "atomic_compare_and_store"
> >> >> that it would be atomic? Otherwise I would say that it was misnamed.
> >> >> So, it should not be possible for *target to be modified withing the
> >> >> atomic_compare_and_store by some other entity, or the function isn't
> >> >> atomic.
> >> >
> >> > The atomic function means "a function that performs an atomic
> >> > operation", not
> >> > "a funtion that is atomic itself."
> >>
> >> Then I think the name is stupid, and furthermore, that means that the
> >> return value of the function is meaningless. It will not tell you
> >> anything. Instead you will always have to check after the operation
> >> wether it performed the swap or not. But that in itself will not answer
> >> the question wether the swap was performed or not either, since the
> >> value that you were supposed to write in case of a match might be the
> >> value that was already there.
> >
> > The return value _is_ very important, indeed. It's used to determine if
> > *target has been overwritten by another thread before the cas operation was
> > peformed. If it has, you should load the new value to *target and call
> > atomic_cas() again. This time if no other thread overwrites *target, the
> > call succeeds (and returns with the expected 'old' value).
>
> You are missing my point.
> Your suggested implementation is the problem, since it isn't atomic, and
> (as you yourself admitted), the *target might not be the same as when
> the compare_and_store part is executed.

There's no C function you describe as atomic as a whole, since every function
in C requires at least a few instructions to deal with arguments. Imagine a
single atomic CPU instruction consisting of mov+mov+mov+..+cmpxchg+ret.
It _is_ simply impossible.

>
> My point was that, as I pointed out, if the return value don't really
> tell wether the store was performed or not, then the return value is
> meaningless. If, however, you were to be sure that the return value
> would tell this information, then the rest of your argument is valid.
> But this requires that the whole function is performed atomically, and
> not just parts of it.

Nobody can write such a function in C, or in any other languages. Use
mutexes or something else.

>
> Basically, I'm trying to say that your suggested implementation of cas
> will not work, and any code you present the would use the cas function
> is really depending on the cas function to be atomic, in the full
> meaning of the word.

It's 99% identical to the Solaris/Windows implementations. You know
Solaris/Windows have been running for more than 10 years. :-)

>
> I don't know if I just am bad at explaining what I'm saying, but I don't
> have any problems understanding how to use an atomic_cas(), nor the need
> for it. My problem was that your implementation of the atomic_cas()
> isn't atomic, and the breaks everything, including your example use of
> the function.
>
> You have said it yourself several times that *target can return
> unexpected values. These values are then returned by your atomic_cas()
> function. Now, if this function can return "unexpected values", how can
> you then say that it is usable?
>
> The whole point is that is must return correct values, otherwise it is
> unusable. So therefore, between the readout of the old value, and the
> writing of a new value, no other processor can be allowed to modify the
> *target, or it is unusable and meaningless. Ie. it really needs to be
> atomic all the way, and not just a single step of it. :-)

That's what CMPXCHG instruction does as part of atomic_cas().

Jun-Young