Re: how atomic is the atomic set instruction?

["Ali Günhan Akyürek" <aliakyurek@xxxxxxxxx>]

Oh thanks Mr.Gatliff, and Mr. King.

I think i've lost myself in the big picture, I had a trouble with a small
atomic set.
How i came to this point is that i want to implement a lock-free
algorithm in armv5 architecture.
Since i couldn't find an compare and swap instruction to use in lock-free
code, I've delved into kernel code.
Then i forget what actually i want to do and stucked to atomic_set.

I thought:

v->counter = i;
is compiled as something like that:

load r1, [i]
// hımm!!, what if switching occurs here and another thread changes the
value "i". It is a wrong behaviour.
store r,1[counter]

Then i saw it in my nightmares till i ask it here.

Anyway, i now understand, the atomicity depends on your code design.
"atomic" in atomic_set is just a kind of hint to help developers. Thanks a
lot again, I've learnt more than i asked.

So, then let me come to the actual point.What i want to do is similar like
the following: a lock-free stack

Push(T item)
{
  Node<T> *oldHead;
  Node<T> * newHead =  new Node<T>(item);

  do
  {
     oldhead = Head;
     newHead->next = oldHead;
  } while
    (!CompAndSwap(&Head, oldHead, newHead));
}

What do you advice me for CompAndSwap? I think something like this is not
possible without disabling interrupts and reenabling interrupts as in
atomic_cmpxchg.
Thanks again.





On Mon, Nov 10, 2008 at 4:14 AM, Bill Gatliff <bgat@xxxxxxxxxxxxxxx> wrote:

> Russell King - ARM Linux wrote:
>
> >
> > Actually, that's not correct.  As I've already said:
> >
> >       val = atomic_read(&foo);
> >       manipulate val
> >       atomic_set(val, &foo);
> >
> > is _not_ atomic, and never will be.  Just because something's called
> > "atomic" does not make it overall atomic.
>
> Correct.  That's the same thing I said.  Well, almost.
>
> The atomic_read() is guaranteed uninterruptible per the API
> definition, as is the atomic_set().  But we agree that your three-line
> snippet of code is _not_ uninterruptible in total, and there is no
> (proper) way to make it uninterruptible using any atomic_*() facility,
> because that's not what the facility is for.
>
> If what you are after is an uninterruptible read-modify-write
> sequence, then you need to implement the whole sequence of
> instructions inside of a _critical_section_--- at which point that
> sequence might be described as "atomic".  Which facility you choose to
> implement the critical section depends on what you need protection
> from, but the choices include mutexes and spinlocks--- but not
> anything from atomic_*().
>
> (However, I can see some utility from an atomic_modify() function.  It
> would be a convenience function, just like condition variables, but
> one that when implemented manually might be more error-prone.
> Something to think about).
>
> > No.  The "store to memory" operation is always atomic if it can be only
> > viewed from elsewhere in the system as being either not committed or
> > fully committed.  That is generally the case with ARMs 'STR' instruction.
>
> Correct.
>
> > But... why use atomic_set() just to store a value?  Wouldn't using a
> > standard pointer be sufficient?  It'll generate the same code.
>
> On ARM, yes.  But not in the general case.
>
> Think about an 8-bit machine that implements 32-bit ints using four
> consecutive bytes--- maybe an H8/300, for example.  Such a machine
> would probably not have an instruction to do even an atomic_t assignment.
>
> So in the general case, if what you are doing absolutely depends on
> the ability to do an uninterruptible assignment, etc. then you really
> need to use the atomic_*() functions--- even if today you are working
> on a machine that provides for atomic assignments via normal C
> expressions.  The use of atomic_*() tells the developers who come
> along after you that you _require_ that operation to be atomic for
> some reason, so if they port the code elsewhere they need to preserve
> that behavior.
>
> Where might an example like that show up?  A lock-less ring buffer of
> bytes is one that readily comes to mind.  Without an atomic_t, you
> have to implement the head/tail index updates manually, perhaps inside
> of critical sections provided by spinlocks.  That's unnecessary on
> ARM, or course, because that machine can do atomic reads and writes
> via STR--- and the compiler tends to use that instruction.  But you
> absolutely have to do it on other processors, so it's nice when the
> details are all hidden inside the atomic_*() API.  The same source
> code works properly everywhere.
>
> In other words, in this situation you really do want to forget about
> the host CPU.  If the operation has to be atomic, use atomic_*() and
> let the compiler and kernel do the work on your behalf when necessary.
>
> > And that's my point - if you're trying to use atomic_set() to make
> > something "atomic" then you're being silly.  atomic_set() is just a
> > plain CPU store - it has no overall guaranteed atomicity apart from
> > the fact that it'll issue a store.
>
> Right.  Weeeeelllll, almost right.  On CPUs that can't do a "plain
> store" to an atomic_t object, then atomic_set() does more.  ARM's
> "plain store" instruction is atomic, however, because that's how the
> CPU and compiler work.  (Except in the packed structure case, perhaps,
> but I digress).
>
> > It doesn't make the surrounding operations somehow magically atomic.
>
> Put another way, atomic_*() functions don't magically create
> uninterruptible sections of code beyond what is minimally necessary to
> implement the atomic_*() function itself.
>
> > So, the original question asking about "how atomic atomic_set is"
> > rings very loud alarm bells to me, bringing up big concerns about
> > what the OP wants to do.  If you need to know how atomic atomic_set
> > is, you ARE doing something wrong.
>
> Actually, I think it's a fairly interesting and important question---
> though I agree that you have to answer it very carefully.
>
> If what you want (perhaps without realizing it) is a critical section
> of code, then there's nothing in atomic_*() for you.  If you don't
> realize that and proceed anyway, then we end up with broken code.  I
> prefer to avoid that outcome, and one way to do that is through
> education about what the term "atomic" might mean.
>
> At least the OP put forth the effort to go look at the implementation
> of atomic_set()--- that's more than we get here most days!
>
>
>
> b.g.
> --
> Bill Gatliff
> bgat@xxxxxxxxxxxxxxx
>
-------------------------------------------------------------------
List admin: http://lists.arm.linux.org.uk/mailman/listinfo/linux-arm
FAQ:        http://www.arm.linux.org.uk/mailinglists/faq.php
Etiquette:  http://www.arm.linux.org.uk/mailinglists/etiquette.php