Difference between atomic operations and memory barriers

Difference between atomic operations and memory barriers

[Leonidas .]

Trying to understand difference between atomic ops and memory barriers.

I was thinking all atomic operations must be using barrier internally,
but I read
somewhere that only some of them use barriers. Sorry for being vague here.

Operations before call to smp_mb() will not be re-ordered and all cpus will see
consistent value after the variable is updated.

E.g.
void * ptr = (void *) str;
smb_mb();

Will this not atomically update ptr? Ptr will be seen by all cpu's in
same state
after it has been assigned str, right?

-Leo.

Re: Difference between atomic operations and memory barriers

[Leonidas .]

On Mon, Oct 26, 2009 at 11:49 PM, Noah Watkins <noah@noahdesu.com> wrote:
>> Trying to understand difference between atomic ops and memory barriers.
>>
> There is a bit of info in:
>    Documentation/atomic_ops.txt
>
> -noah
>
>


Thanks for the pointer, there are no atomic operations for pointers, right?
I guess barrier is what we need in that case.

-Leo.

Re: Difference between atomic operations and memory barriers

[Chris Friesen]

On 10/26/2009 12:22 PM, Leonidas . wrote:
> On Mon, Oct 26, 2009 at 11:49 PM, Noah Watkins <noah@noahdesu.com> wrote:
>>> Trying to understand difference between atomic ops and memory barriers.
>>>
>> There is a bit of info in:
>>    Documentation/atomic_ops.txt

> Thanks for the pointer, there are no atomic operations for pointers, right?
> I guess barrier is what we need in that case.

You need barriers for the atomics too, at least in some cases.  From
that document:

*** WARNING: atomic_read() and atomic_set() DO NOT IMPLY BARRIERS! ***


For simple assignments, I'm fairly sure linux assumes that writes to
individual variables are atomic.  ie, if you're assigning to an int you
won't get half of the assignment completed while the other half isn't.

What the atomic ops buy you is the ability to do increment-and-test,
compare-and-exchange, etc. in an atomic fashion.

Barriers are needed to make sure that operations are visible on other
cpus in the correct order, and to ensure that the compiler doesn't
reorder the operations.

If you use the normal locking mechanisms (mutexes, spinlocks, etc.) the
barriers are implicit in the lock.

Chris

Re: Difference between atomic operations and memory barriers

[Leonidas .]

On Tue, Oct 27, 2009 at 12:24 AM, Chris Friesen <cfriesen@nortel.com> wrote:
> On 10/26/2009 12:22 PM, Leonidas . wrote:
>> On Mon, Oct 26, 2009 at 11:49 PM, Noah Watkins <noah@noahdesu.com> wrote:
>>>> Trying to understand difference between atomic ops and memory barriers.
>>>>
>>> There is a bit of info in:
>>>    Documentation/atomic_ops.txt
>
>> Thanks for the pointer, there are no atomic operations for pointers, right?
>> I guess barrier is what we need in that case.
>
> You need barriers for the atomics too, at least in some cases.  From
> that document:
>
> *** WARNING: atomic_read() and atomic_set() DO NOT IMPLY BARRIERS! ***
>
>
> For simple assignments, I'm fairly sure linux assumes that writes to
> individual variables are atomic.  ie, if you're assigning to an int you
> won't get half of the assignment completed while the other half isn't.
>
> What the atomic ops buy you is the ability to do increment-and-test,
> compare-and-exchange, etc. in an atomic fashion.
>
> Barriers are needed to make sure that operations are visible on other
> cpus in the correct order, and to ensure that the compiler doesn't
> reorder the operations.
>
> If you use the normal locking mechanisms (mutexes, spinlocks, etc.) the
> barriers are implicit in the lock.
>
> Chris
>

This takes it a step further ! Thanks for the info.

But locks are expensive for simpler assignments like integer assignment thats
why there are atomic counter parts, but there is no such things for
pointers right?

So we can safely assume that pointer assignment will be done in an
atomic manner?

-Leo.

Re: Difference between atomic operations and memory barriers

[Noah Watkins]

> So we can safely assume that pointer assignment will be done in an
> atomic manner?

See the the comment above rcu_assign_pointer in
include/linux/rcupdate.h

-noah

> -Leo.

Re: Difference between atomic operations and memory barriers

[Stefan Richter]

Noah Watkins wrote:
>> So we can safely assume that pointer assignment will be done in an
>> atomic manner?
> 
> See the the comment above rcu_assign_pointer in
> include/linux/rcupdate.h

This comment only talks about ordering, not about atomicity.

Again, AFAIR the ISO C spec should explain what is going to be
guaranteed atomic and what might not be atomic.

rcu_assign_pointer() itself does rely on atomicity of pointer
assignments though, like lots of code elsewhere in the kernel.
-- 
Stefan Richter
-=====-==--= =-=- ==-=-
http://arcgraph.de/sr/

Re: Difference between atomic operations and memory barriers

[Noah Watkins]

> Noah Watkins wrote:
>>> So we can safely assume that pointer assignment will be done in an
>>> atomic manner?
>>
>> See the the comment above rcu_assign_pointer in
>> include/linux/rcupdate.h
>
> This comment only talks about ordering, not about atomicity.
Ahh, yeh that's true.

>
> Again, AFAIR the ISO C spec should explain what is going to be
> guaranteed atomic and what might not be atomic.
This seems likely. I wonder if there are any strange architectures
out there that have some insane implementation.

>

Re: Difference between atomic operations and memory barriers

[Valdis.Kletnieks]

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

On Tue, 27 Oct 2009 00:30:45 +0530, "Leonidas ." said:

> So we can safely assume that pointer assignment will be done in an
> atomic manner?

Has anybody ever actually made a *production* CPU that had non-atomic
pointer assignments?  And how long before the crazed programmers lynched
and burned the offending CPU designer at the stake? ;)

Non-atomic pointer assignments are the CPU design equivalent of Vogon poetry.
Just Say No. With a shotgun if needed.

[-- Attachment #2: Type: application/pgp-signature, Size: 227 bytes --]

Re: Difference between atomic operations and memory barriers

[Boaz Harrosh]

On 10/27/2009 01:51 PM, Valdis.Kletnieks@vt.edu wrote:
> On Tue, 27 Oct 2009 00:30:45 +0530, "Leonidas ." said:
> 
>> So we can safely assume that pointer assignment will be done in an
>> atomic manner?
> 
> Has anybody ever actually made a *production* CPU that had non-atomic
> pointer assignments?  And how long before the crazed programmers lynched
> and burned the offending CPU designer at the stake? ;)
> 
> Non-atomic pointer assignments are the CPU design equivalent of Vogon poetry.
> Just Say No. With a shotgun if needed.

What don't you know? the CPU that started it all was like that, the x86 16-bit
"large" and "huge" model had a double register seg:offset set, also in-memory
was double-ints(2*16) even the i386 was running 16 bit modes for a long time.

Kernel still have 16-bit dosemu mode supported until today, no?

About the shotguns lynching and burning I'm not sure, but Intel survived
just fine.

Boaz

Re: Difference between atomic operations and memory barriers

[Valdis.Kletnieks]

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

On Wed, 28 Oct 2009 12:00:05 +0200, Boaz Harrosh said:

> What don't you know? the CPU that started it all was like that, the x86 16-bit
> "large" and "huge" model had a double register seg:offset set, also in-memory
> was double-ints(2*16) even the i386 was running 16 bit modes for a long time.

Yes, but there were instructions to load segment registers, and those were
atomic, and there were instructions to compute effective addresses based on the
segment registers, and those were basically atomic. But you never had a chance
to see a partly loaded segment register (just like in today's virtual memory
equivalents, a PTE's effect is basically atomic - you never see half the
address bits of a PTE take effect and not the other half).

Yes, if a segment register wasn't set right, you'd load/store from the wrong
place in memory (we *still* have that, playing with %fs and %gs).  But that's
different than an actual load or store only half-happening, or happening partly
to an old place and partly to a new one, because a segment register is only
half-finished laoding.


[-- Attachment #2: Type: application/pgp-signature, Size: 227 bytes --]

Re: Difference between atomic operations and memory barriers

[Stefan Richter]

Leonidas . wrote:
> On Mon, Oct 26, 2009 at 11:49 PM, Noah Watkins <noah@noahdesu.com> wrote:
>>> Trying to understand difference between atomic ops and memory barriers.

Atomic accesses and barriers are different concepts.

The former means that there won't be intermediary values visible (to
another CPU or to a DMA capable device) at any time; there will only be
either the old value or the new value, but nothing half-done.

The latter means that an order between two (or more) separate accesses
is enforced.

You cannot use barriers to make intrinsically non-atomic accesses look
atomically; you need a lock for such a purpose.  (Or RCU.)

>>> I was thinking all atomic operations must be using barrier internally, but I read
>>> somewhere that only some of them use barriers. Sorry for being vague here.
>>> 
>>> Operations before call to smp_mb() will not be re-ordered and all cpus will see
>>> consistent value after the variable is updated.
>>> 
>>> E.g.
>>> void * ptr = (void *) str;
>>> smb_mb();
>>> 
>>> Will this not atomically update ptr? Ptr will be seen by all cpu's in same state
>>> after it has been assigned str, right?
>> 
>> There is a bit of info in:
>>    Documentation/atomic_ops.txt
>>
>> -noah
>>
>>
> 
> 
> Thanks for the pointer, there are no atomic operations for pointers, right?
> I guess barrier is what we need in that case.

There are more atomic accesses than those which deal with atomic_t.  For
example,
	any_t *ptr = something;
is definitely atomic, and we rely on this atomicity in the kernel at
many places.

I guess these things can be found somewhere in the C language specification.
-- 
Stefan Richter
-=====-==--= =-=- ==-=-
http://arcgraph.de/sr/

Re: Difference between atomic operations and memory barriers

[Leonidas .]

On Tue, Oct 27, 2009 at 12:30 AM, Stefan Richter
<stefanr@s5r6.in-berlin.de> wrote:
> Leonidas . wrote:
>> On Mon, Oct 26, 2009 at 11:49 PM, Noah Watkins <noah@noahdesu.com> wrote:
>>>> Trying to understand difference between atomic ops and memory barriers.
>
> Atomic accesses and barriers are different concepts.
>
> The former means that there won't be intermediary values visible (to
> another CPU or to a DMA capable device) at any time; there will only be
> either the old value or the new value, but nothing half-done.
>
> The latter means that an order between two (or more) separate accesses
> is enforced.
>
> You cannot use barriers to make intrinsically non-atomic accesses look
> atomically; you need a lock for such a purpose.  (Or RCU.)
>
>>>> I was thinking all atomic operations must be using barrier internally, but I read
>>>> somewhere that only some of them use barriers. Sorry for being vague here.
>>>>
>>>> Operations before call to smp_mb() will not be re-ordered and all cpus will see
>>>> consistent value after the variable is updated.
>>>>
>>>> E.g.
>>>> void * ptr = (void *) str;
>>>> smb_mb();
>>>>
>>>> Will this not atomically update ptr? Ptr will be seen by all cpu's in same state
>>>> after it has been assigned str, right?
>>>
>>> There is a bit of info in:
>>>    Documentation/atomic_ops.txt
>>>
>>> -noah
>>>
>>>
>>
>>
>> Thanks for the pointer, there are no atomic operations for pointers, right?
>> I guess barrier is what we need in that case.
>
> There are more atomic accesses than those which deal with atomic_t.  For
> example,
>        any_t *ptr = something;
> is definitely atomic, and we rely on this atomicity in the kernel at
> many places.
>
> I guess these things can be found somewhere in the C language specification.
> --
> Stefan Richter
> -=====-==--= =-=- ==-=-
> http://arcgraph.de/sr/
>

If your answer matches my inference that,

any_t *ptr = something;

is always atomic even on SMPs without using locks, barriers then my
doubt is cleared. Thanks.

-Leo.

Re: Difference between atomic operations and memory barriers

[Michael Schnell]

Leonidas . wrote:
> 
> any_t *ptr = something;
> 
> is always atomic even on SMPs without using locks, barriers then my
> doubt is cleared. Thanks.

I assume that this only holds if the pointer (not the thing it points
to) is denoted as volatile.

-Michael

Re: Difference between atomic operations and memory barriers

[Leonidas .]

On Tue, Oct 27, 2009 at 3:21 AM, Michael Schnell <mschnell@lumino.de> wrote:
> Leonidas . wrote:
>>
>> any_t *ptr = something;
>>
>> is always atomic even on SMPs without using locks, barriers then my
>> doubt is cleared. Thanks.
>
> I assume that this only holds if the pointer (not the thing it points
> to) is denoted as volatile.
>
> -Michael
>

I dont think so,  volatile would only ensure no caching, so some cpus
might see the cached
pointer (this is where you would want to use barriers), but pointer
assignment would still be atomic.


-Leo.

Re: Difference between atomic operations and memory barriers

[Michael Schnell]

Leonidas . wrote:
> but pointer
> assignment would still be atomic.
> 

Yep. bit maybe the assignment to the memory cell that holds the pointer
just would be optimized out and be done at all. This my be considered
atomic but of course not desired for anything atomicness is considered for.

-Michael

Re: Difference between atomic operations and memory barriers

[Stefan Richter]

Leonidas . wrote:
> On Tue, Oct 27, 2009 at 3:21 AM, Michael Schnell <mschnell@lumino.de> wrote:
>> Leonidas . wrote:
>>>
>>> any_t *ptr = something;
>>>
>>> is always atomic even on SMPs without using locks, barriers then my
>>> doubt is cleared. Thanks.
>>
>> I assume that this only holds if the pointer (not the thing it points
>> to) is denoted as volatile.

  - Atomic access (either old or new value is visible to CPUs or
    devices, but never any intermediary, half-baked value),
  - memory barrier (enforced order of accesses),
  - volatile qualifier (disabled compiler optimization of accesses)

are three different concepts.

We rely on atomic pointer load and store all over the kernel, yet never
qualify them as "volatile".  (A look into the C language spec might
bring clarity here.  I don't have the spec at hand alas.)

> I dont think so,  volatile would only ensure no caching, so some cpus
> might see the cached pointer (this is where you would want to use
> barriers), but pointer assignment would still be atomic.

What "volatile" ensures or not ensures is not that well defined in the C
language specification as far as I recall prior discussion.  Its precise
effects are compiler dependent.  You are right in so far as volatile
(given or missing) does not change whether an access is guaranteed
atomic or not.  Since it affects compiler optimizations, I think it
could possibly affect atomicity of accesses which were never guaranteed
to be atomic.  But this should not be interesting to 99.99% of all
kernel coders because they better use guaranteed atomic accesses when
they really need them.  (E.g. <linux/atomic.h> or pointer load/ store.)
-- 
Stefan Richter
-=====-==--= =-=- ==-==
http://arcgraph.de/sr/