6 ms·

Making Sense of Acquire-Release Semantics

159 points by sph 3y ago

catlifeonmars 3y ago
Minor quibble: you can linearize small amounts of memory using atomic access. You just need to ensure that your memory fits within the size of a single atomic access. For example, storing two uint32 as a uint64 when there is atomic access to uint64 available.
- mevric 3y ago
  I am curious to understand how the following is achieved? Is there a material on this? "storing two uint32 as a uint64"
  - JonChesterfield 3y ago
    Put them next to each other, 8 byte align the first one, use a compiler mechanism to disable alias analysis, do the uint64 store. Attribute((may_alias)) is the local override, fno-strict-aliasing the global one. I think C++ can now do "these bytes are now that type", called something like start_lifetime_as. C probably can't, though using a union might be legitimate. The language rules in this area are a mess.
    - mevric 3y ago
      Thank you!!
    - gpderetta 3y ago
      Note that writing 64 bits and reading 32 (or viceversa) is not a way to get around fences on x86. It is explicitly documented as begin undefined. In most cases it will fail to store-forward that will stall and act as an implicit fence, but in some cases the CPU can do partial store forwarding, breaking it. AFAIK this trick does work on SPARC though.
      - moonchild 3y ago
        It's not documented as being undefined; it's simply not documented at all. Intel's latest uarch does partial store forwarding. There was a paper from a few years ago trying to define semantics for mixed-size accesses (not for x86 though) https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf I don't think the parent was talking about this, though; they were just talking about using a single large physical location, which logically contains multiple smaller values. Accesses to a single location happen order, so there is indeed no need for fencing between accesses to it. Usually you get a full 128 bits (at least amd64/aarch64/ppc64; not riscv yet but I expect they will get there). That said—mixed-size can be useful despite the lack of semantics (I think linux uses them in a few places?). sooo
        gpderetta 2y ago
        Ah, right, it was about guaranteed total order on all stores in a single memory location. Re colocation and x86, IIRC the intel memory model has wordings regarding read and writes to a a memory location having to be of the same size to take advantage of the memory model guarantees.
        moonchild 2y ago
        total order on all accesses to a given location—loads from a single location can't be reordered w.r.t. each other either i don't remember seeing any wording relating to mixed-size accesses in the intel manual (not withstanding that the official models are ... ambiguous, to say the least, compared with what 3rd-party researchers have done)
        gpderetta 2y ago
        For a total store order to be meaningful of course it implies that loads are also non visibly reordered. If a store falls in the forest but nobody is around to load it, was it really ordered :)
    - MaxBarraclough 2y ago
      There's no need to flirt with undefined behaviour and non-standard compiler flags. Just convert both uint32_t values to uint64_t type, then combine them into a single uint64_t value using bitwise shift then bitwise inclusive OR. Rob Pike has blogged about this kind of thing. [0] Perhaps also of interest: both C and C++ provide a (portable and standard) means of determining whether atomic operations on uint64_t are assured to be lock-free. [1][2] (Assuming of course that the uint64_t type exists - it's in the standard but it's optional.) [0] https://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html https://commandcenter.blogspot.com/2012/04/byte-order-fallac... ( discussion: https://news.ycombinator.com/item?id=3796378 https://news.ycombinator.com/item?id=3796378 ) [1] https://en.cppreference.com/w/c/atomic/atomic_is_lock_free https://en.cppreference.com/w/c/atomic/atomic_is_lock_free [2] https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free
      - JonChesterfield 2y ago
        If you do the loads as uint32, you lose the single atomic operations on two different values which was the whole point of this exercise. Using a single uint64 as the memory type works, but you no longer have two different names fields and have to pack/unpack them by hand. There's no ub if you use the compiler extension, just totally clear code that does the right thing
        MaxBarraclough 2y ago
        > If you do the loads as uint32, you lose the single atomic operations on two different values which was the whole point of this exercise. There's no need for any flirting with undefined behaviour through type-punning. When doing the atomic write, you prepare the uint64_t value to write by using bitwise operations, and then perform the atomic write of the resultant uint64_t value. When doing the atomic read, you atomically read the uint64_t value, then use bitwise operations to unpack the original pair of uint32_t values. Put differently, writing is done by pack-then-atomically-write, and reading is done by atomically-read-then-unpack. Turns out we're both overthinking it though, there's a more direct way: use a struct containing an array of 2 uint32_t elements, or declare a struct with 2 uint32_t members. Both C and C++ support atomic reads and writes of user-defined types. For a C++ example showing this see [0]. This will be atomic and, presumably, should be lock-free where possible (hard to imagine the compiler would introduce padding in the struct type that would sabotage this). > Using a single uint64 as the memory type works, but you no longer have two different names fields and have to pack/unpack them by hand. Yes, the stored variable would hold 2 different meaningful values, which is a little ugly. > There's no ub if you use the compiler extension, just totally clear code that does the right thing Anyone with a deep knowledge of the language will quickly recognise it as incorrect per the language standard. I wouldn't call that totally clear code that does the right thing. Your proposed solution is only assured to behave as expected if the correct compiler-specific flags are used, otherwise it will introduce undefined behaviour. There's no guarantee that a compiler will even offer such a flag. It's also likely to trigger compiler warnings. [0] https://en.cppreference.com/w/cpp/atomic/atomic https://en.cppreference.com/w/cpp/atomic/atomic
zevv 3y ago
Well written article, nice and to the point. Do recommend. Decades ago I declared myself too stupid to use shared memory with threading; I have learned to avoid this whenever possible, or abstract away the memory access under a safe layer as soon as possible. One of the greatest decisions of my career. Memory model semantics is one of the parts of systems programming that is generally poorly understood; I have had long discussions with senior programmers who have spent their careers carelessly threading their code without realizing what is happening under the hood. Not only did some of them not properly understand the acquire/release model, but they were not even aware of its existence. For a more in-depth explanation, I recommend Sutter's excellent talk "Atomic <> weapons": https://www.youtube.com/watch?v=A8eCGOqgvH4 https://www.youtube.com/watch?v=A8eCGOqgvH4. It is a two hour lecture, but it will be worth your time.
- toast0 3y ago
  > Decades ago I declared myself too stupid to use shared memory with threading; I have learned to avoid this whenever possible, or abstract away the memory access under a safe layer as soon as possible. One of the greatest decisions of my career. This probably qualifies you to do shared memory threading, when it is needed. Such as debugging those abstraction layers. Knowing you don't understand it puts you in the right frame of mind to carefully do the work.
  - deleted 2y ago
    [deleted]
- ratmeadow 3y ago
  That atomics talk by Sutter is a superbly high quality explanation, albeit long. He addresses the topic with exceptional rigor and plenty of examples that show what can and can't happen. It for sure took me from 0 to 100 knowledge on thread safety.
- eru 3y ago
  I agree. Btw, shared memory by itself is fine, even shared memory with threading. The really dangerous ingredient is mutability. And mutability is already toxic waste on its own, and concurrency amplifies the danger.
newpavlov 3y ago
For a more in-depth understanding, I recommend reading "Rust Atomics and Locks": https://marabos.nl/atomics/ https://marabos.nl/atomics/ It uses Rust for examples, but it more or less applicable to C/C++ as well.
chrisaycock 3y ago
The first explanation that really clarified memory barriers for me was from Paul E. McKenney: http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2...
- JonChesterfield 3y ago
  That one plus the kernel notes at https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt did the trick for me.
king_geedorah 3y ago
No matter how many times I read about these, I'm always left just slightly confused. Acquire/release is about the ordering of instructions within a thread of execution. So if I have a writer writing X, then writing Y, then I need write-release to make sure that the compiler actually puts the instructions for Y after the instructions for X in the machine code. If I want to guarantee that the results of those writes are visible to another thread, then I need a memory fence to force flushing of the caches out to main memory basically? The author mentions the queue as originally written is technically correct for x86/x86_64. This is true only in the sense that neither the producer or consumer can experience partial reads / partial writes, right? It is still possible that if, say, the consumer were busy waiting for an item to be available then it will spin for as long as it takes for the CPU to decide to flush the producer's writes out to main memory? Whenever I see these concepts discussed, it is in the context of the C++ stdatomic library. If I were writing a program in C99, I would assume it would still be possible to communicate the same intent / restrictions to the compiler, but I'm not sure because I haven't been able to find any resources that discuss doing so. How might one communicate that to the compiler, assuming they are on x86/x86_64 where in theory the CPU should just do the right thing with the right machine code? Finally, does target architecture influence the compiler's behavior in this regard at all? For example, if we take x86/x86_64 as having acquire/release semantics without any further work, does telling the compiler that my target architecture is x86/x86_64 imply that those semantics should be used throughout the program?
- gpderetta 3y ago
  > Acquire/release is about the ordering of instructions within a thread of execution acquire/release is about visibility. Acquire and release always go in pair. You can't really reason purely about a release and an acquire in isolation and that's why simply thinking about instruction reordering is not enough. > So if I have a writer writing X, then writing Y, then I need write-release to make sure that the compiler actually puts the instructions for Y after the instructions for X in the machine code. If I want to guarantee that the results of those writes are visible to another thread, then I need a memory fence to force flushing of the caches out to main memory basically Whether an explicit memory fence is needed or not depends on the architecture (for example you do not need them on x86). But you do not need to care, if you use the atomic operation with the correct semantic, the compiler will insert any required fence for you. As an aside, typically fences have nothing to do with caches. One a store or a load operation hits the cache, the coherence system takes care that everything works correctly. If fences had to flush the cache, they would be orders of magnitude slower. Instead fences (explicit or otherwise) make sure that either memory operations commit (i.e. are visible at the cache layer) in the expected order or that an application can't tell otherwise, i.e. reordering is still permitted across fences as long as conflicts can be detected and repaired, typically this can only happen for loads that can be retried without side effects. > Whenever I see these concepts discussed, it is in the context of the C++ stdatomic library. If I were writing a program in C99, I would assume it would still be possible to communicate the same intent / restrictions to the compiler formally in C99 multithreaded programs are UB. Of course other standards (POSIX, openmp) and implementations (the old GCC __sync_builtins) could give additional guarantees; but only C11 gave a model defined well enough to reason in depth about the overall CPU+compiler system; before that people just had to make a lot of assumptions. > Finally, does target architecture influence the compiler's behavior in this regard at all? For example, if we take x86/x86_64 as having acquire/release semantics without any further work, does telling the compiler that my target architecture is x86/x86_64 imply that those semantics should be used throughout the program? It does, but note that the compiler will only respect acquire/release semantics for atomic objects operations with the required ordering, not normal load and stores.
ajross 3y ago
This bit isn't quite correct: > Acquire and release semantics don’t have any meaning on Intel- and AMD-brand processors. On x86 CPUs, which is to say, on just about any Intel- or AMD-brand CPU you can buy right now, memory operations on a single CPU core happen in program order. In fact x86 CPUs do allow themselves to reorder reads around other reads[1]. The rule is that no memory access is allowed to cross a write operation[2]. The distinction isn't important to traditional critical section analysis like the article is doing, but there are lockless algorithms out there that depend on fully-ordered reads. Dekker's famous (but mostly useless in practice) algorithm for mutual exclusion is one. [1] Note here I'm using the more traditional and frankly much clearer terminology about actual hardware behavior and not the frustrating abstractions embraced by the language design community. [2] Or one of a handful of "serializing instructions", the most commonly relied on being LOCK CMPXCHG
- moonchild 3y ago
  > x86 CPUs do allow themselves to reorder reads around other reads. The rule is that no memory access is allowed to cross a write operation That's not correct. Intel manual, vol 3, sec. 9.2.2: > Reads are not reordered with other reads > Writes are not reordered with older reads. > Writes to memory are not reordered with other writes A read may be reordered w.r.t. an older write (and hence tfa is incorrect that po=ppo on x86), but reads are not ordered with other reads. You can see in the c/c++ processor mappings here https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html that load acquire/store release can be mapped to plain loads and stores on x86.
  - ajross 3y ago
    Oops, indeed. Must be a bit flip error in my memory.
- moonchild 3y ago
  > more traditional and frankly much clearer terminology about actual hardware behavior and not the frustrating abstractions embraced by the language design community Axiomatic memory models were pushed as much from the hardware world as from the software world if not more so, and they exist for a reason. Overfitting obligatorily abstract models to the behaviour of a particular microarchitecture benefits neither hardware nor software writers
ratmeadow 3y ago
The article says a lot about CPUs reordering memory instructions - is this actually the main cause of the issues with the shown code? Speaking of x86 specifically, instructions are aggressively reordered but as far as I understood it, the results are generally committed in order. The ISA has rules about what memory reorderings can occur, and looks like most reorderings are forbidden. This stackoverflow explains it well: https://stackoverflow.com/a/50310563/7064452 https://stackoverflow.com/a/50310563/7064452 In this queue example I'd say the elephant in the room is the compiler, not the CPU. The code has no language-level synchronisation, therefore the compiler is free to do whatever - it's not surprising memory ops get reordered. If you want to be pedantic, the code is UB with no synchronisation present. Perhaps besides the point to discuss CPU behaviour in this light.
- gpderetta 3y ago
  The article does mention in the end that a trivial translation of the queue code to x86 will work. It is broken on other architectures though (aside of the obvious UB because of races).
- dbcurtis 3y ago
  Yes, having worked on one of the out-of-order Intel CPU's, I can tell you that you are correct. Instructions may be "complete", as in their results can be forwarded to later operations, but the instruction isn't "retired" until it is known that it can not raise an exception, or be cancelled because of branch mis-predict, etc. Programmer-visible architectural state as defined in the ISA is not written until instruction retirement. CPU re-ordering instructions is not going to change semantics (in X86 and similar architectures... there are some archs that relax that guarantee). Compilers are notorious for doing dumb things around locks.... the gnu C for AVR architecture, for instance, looks at the SEI instruction (SEt Interrupt mask bit) and notices that it doesn't modify memory or registers, so hoists it to the top of functions. Eh.. No, SEI; CLI; <code> <critical section> <code> is not what I intended... Also... CPU's with data caches can to smart things with architecturally-defined locking instructions such as "test-and-set' or 'compare-and-exchange' such that the instructions are always cache-coherent across CPU's. If you try to roll-your-own locking code, you had best understand how the cache invalidation mechanism works in your chosen CPU or you are going to have a bad day.
alfiedotwtf 3y ago
I’ve read so much through the years on this, and I feel like it’s our Emperor’s Clothes - people pretend to understand, but does anyone actually understand this magic? Like not theoretically-superficially but in practice, or am I just too dumb to see the King’s new attire?
- spacechild1 3y ago
  I do understand it to the extent that I can write correct lock-free data structures. For me that's enough, I don't need to know what happens exactly in the CPU for each architecture (altough I have some understanding).
- klabb3 2y ago
  Mozilla had this famous sign 8ft up on the wall that said “you must be this tall to write multi-threaded code”[1]. A lot of people will claim to be able to master it. The track record shows that even the superhuman domain experts make mistakes frequently, as it’s almost impossible to reason about, verify, debug and importantly maintain the invariants as code evolves. And good luck predicting performance implications on different CPUs and workloads. In either case, for software development it doesn’t really matter if there is such a hypothetical person: because nobody else is. In practice it’s similar to protecting against crypto vulns: don’t roll your own, use trusted libs with very few hard-to-misuse data structures and operations, sometimes rely on lang/compiler features, and runtime analysis tooling. Personally I think we eventually need an overhaul in language design, perhaps new concurrent control flow constructs and operations. Just look at the C code shown.. it’s not even “code” in the sense that one line does some logical operation scoped to the current function. No, it’s “markers” that tells compiler and CPU to flush internal caches, change their optimizations as a thread-global “operation”. And the post is introductory, SPSC which is much simpler, doesn’t cover thread parking, MESI, compiler reordering etc. It’s a red flashing sign that the abstractions are all whack, frankly. It’s the anti-thesis of a neat, modularized Russian dolls we typically enjoy with single threaded code, including C. Now, these things are still critical, they work and it’s the best we got. It’s a genuinely hard-hard problem, which is quite humbling given how prevalent, studied and important concurrency is to virtually every programming domain. [1]: https://bholley.net/blog/2015/must-be-this-tall-to-write-multi-threaded-code.html https://bholley.net/blog/2015/must-be-this-tall-to-write-mul...
cryptonector 3y ago
Solaris/Illumos has a better name for this: `membar_producer()` and `membar_consumer()`. The first is release semantics, and it's what a producer must do before it finishes publishing some memory to a consumer. The second is what a consumer must do before it starts consuming what the producer gave it. I find that naming convention much more intuitive than release/acquire, though release/acquire is more general.
liblfds-temp 3y ago
> See how we added a new fence() call to put()? That fixes the reordering problem we’ve described at length. Now if the CPU gets bored waiting for entries[i] to be read into the cache, and tries to pull up the tail++ line so it happens sooner, bonk!, the tail++ line hits that fence and stops moving. We’ve forced the entry to be written before the tail is bumped. Problem solved! I may be completely wrong, it's a complicated subject, but I think the wording here is potentially misleading. As I understand it (and I may be wrong!), a full fence does the following : "all reads and all writes prior to the fence must occur before any reads or writes after the fence". What I'm concerned about is people thinking this is a blocking behaviour, i.e. when we hit the fence, then at that point all prior reads and writes occur. This is not the case. The reads and writes prior to the fence can occur at any time - they could occur LONG AFTER we pass the fence - but what we do get from the fence is that the reads and writes prior to the fence WILL occur BEFORE any reads or writes after the fence. So, to put it another way, the code is executing, we come to the fence - and absolutely nothing happens. The processor just keeps going. No reads occur, no writes occur. Then at some point later on, both in time and in code, the process comes to another (say) read. NOW, finally, the processor MUST complete all reads and writes which were issued prior to the fence.
- liblfds-temp 2y ago
  A thread which performs a write, has a fence, and then performs another write, will at the time of the second write due to the fence guarantee the first write has completed. However, "completed" is misleading. The write will still not be seen by readers. "Complete" really means "the writer has done all the work he can do, which is necessary but insufficient". For a reader to see the write, the readers must issue a read memory barrier before reading the value. All of this is due to store buffers and cache invalidation requests. In short, in principle, a write is known about only by the processor it occurred upon; if there are any other processors in the system, then unless special magic is performed (fences and so on), any writes they see from other processors are seen purely by chance and can happen in any order (including going backwards in time), or not happen at all. I once read an article which framed all this in terms of source control. Memory is like SVN, or Git. You make local changes (on your processor, which has its local copy of memory). You then commit (write fence/atomic operation). No one else can see your changes until they update from source control and get the latest version (read fence).

159 points by sph 3y ago

Minor quibble: you can linearize small amounts of memory using atomic access. You just need to ensure that your memory fits within the size of a single atomic access. For example, storing two uint32 as a uint64 when there is atomic access to uint64 available.

mevric 3y ago
I am curious to understand how the following is achieved? Is there a material on this? "storing two uint32 as a uint64"
- JonChesterfield 3y ago
  Put them next to each other, 8 byte align the first one, use a compiler mechanism to disable alias analysis, do the uint64 store. Attribute((may_alias)) is the local override, fno-strict-aliasing the global one. I think C++ can now do "these bytes are now that type", called something like start_lifetime_as. C probably can't, though using a union might be legitimate. The language rules in this area are a mess.
  - mevric 3y ago
    Thank you!!
  - gpderetta 3y ago
    Note that writing 64 bits and reading 32 (or viceversa) is not a way to get around fences on x86. It is explicitly documented as begin undefined. In most cases it will fail to store-forward that will stall and act as an implicit fence, but in some cases the CPU can do partial store forwarding, breaking it. AFAIK this trick does work on SPARC though.
    - moonchild 3y ago
      It's not documented as being undefined; it's simply not documented at all. Intel's latest uarch does partial store forwarding. There was a paper from a few years ago trying to define semantics for mixed-size accesses (not for x86 though) https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf I don't think the parent was talking about this, though; they were just talking about using a single large physical location, which logically contains multiple smaller values. Accesses to a single location happen order, so there is indeed no need for fencing between accesses to it. Usually you get a full 128 bits (at least amd64/aarch64/ppc64; not riscv yet but I expect they will get there). That said—mixed-size can be useful despite the lack of semantics (I think linux uses them in a few places?). sooo
      - gpderetta 2y ago
        Ah, right, it was about guaranteed total order on all stores in a single memory location. Re colocation and x86, IIRC the intel memory model has wordings regarding read and writes to a a memory location having to be of the same size to take advantage of the memory model guarantees.
        moonchild 2y ago
        total order on all accesses to a given location—loads from a single location can't be reordered w.r.t. each other either i don't remember seeing any wording relating to mixed-size accesses in the intel manual (not withstanding that the official models are ... ambiguous, to say the least, compared with what 3rd-party researchers have done)
        gpderetta 2y ago
        For a total store order to be meaningful of course it implies that loads are also non visibly reordered. If a store falls in the forest but nobody is around to load it, was it really ordered :)
  - MaxBarraclough 2y ago
    There's no need to flirt with undefined behaviour and non-standard compiler flags. Just convert both uint32_t values to uint64_t type, then combine them into a single uint64_t value using bitwise shift then bitwise inclusive OR. Rob Pike has blogged about this kind of thing. [0] Perhaps also of interest: both C and C++ provide a (portable and standard) means of determining whether atomic operations on uint64_t are assured to be lock-free. [1][2] (Assuming of course that the uint64_t type exists - it's in the standard but it's optional.) [0] https://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html https://commandcenter.blogspot.com/2012/04/byte-order-fallac... ( discussion: https://news.ycombinator.com/item?id=3796378 https://news.ycombinator.com/item?id=3796378 ) [1] https://en.cppreference.com/w/c/atomic/atomic_is_lock_free https://en.cppreference.com/w/c/atomic/atomic_is_lock_free [2] https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free
    - JonChesterfield 2y ago
      If you do the loads as uint32, you lose the single atomic operations on two different values which was the whole point of this exercise. Using a single uint64 as the memory type works, but you no longer have two different names fields and have to pack/unpack them by hand. There's no ub if you use the compiler extension, just totally clear code that does the right thing
      - MaxBarraclough 2y ago
        > If you do the loads as uint32, you lose the single atomic operations on two different values which was the whole point of this exercise. There's no need for any flirting with undefined behaviour through type-punning. When doing the atomic write, you prepare the uint64_t value to write by using bitwise operations, and then perform the atomic write of the resultant uint64_t value. When doing the atomic read, you atomically read the uint64_t value, then use bitwise operations to unpack the original pair of uint32_t values. Put differently, writing is done by pack-then-atomically-write, and reading is done by atomically-read-then-unpack. Turns out we're both overthinking it though, there's a more direct way: use a struct containing an array of 2 uint32_t elements, or declare a struct with 2 uint32_t members. Both C and C++ support atomic reads and writes of user-defined types. For a C++ example showing this see [0]. This will be atomic and, presumably, should be lock-free where possible (hard to imagine the compiler would introduce padding in the struct type that would sabotage this). > Using a single uint64 as the memory type works, but you no longer have two different names fields and have to pack/unpack them by hand. Yes, the stored variable would hold 2 different meaningful values, which is a little ugly. > There's no ub if you use the compiler extension, just totally clear code that does the right thing Anyone with a deep knowledge of the language will quickly recognise it as incorrect per the language standard. I wouldn't call that totally clear code that does the right thing. Your proposed solution is only assured to behave as expected if the correct compiler-specific flags are used, otherwise it will introduce undefined behaviour. There's no guarantee that a compiler will even offer such a flag. It's also likely to trigger compiler warnings. [0] https://en.cppreference.com/w/cpp/atomic/atomic https://en.cppreference.com/w/cpp/atomic/atomic

zevv 3y ago

Well written article, nice and to the point. Do recommend. Decades ago I declared myself too stupid to use shared memory with threading; I have learned to avoid this whenever possible, or abstract away the memory access under a safe layer as soon as possible. One of the greatest decisions of my career. Memory model semantics is one of the parts of systems programming that is generally poorly understood; I have had long discussions with senior programmers who have spent their careers carelessly threading their code without realizing what is happening under the hood. Not only did some of them not properly understand the acquire/release model, but they were not even aware of its existence. For a more in-depth explanation, I recommend Sutter's excellent talk "Atomic <> weapons": https://www.youtube.com/watch?v=A8eCGOqgvH4 https://www.youtube.com/watch?v=A8eCGOqgvH4. It is a two hour lecture, but it will be worth your time.

toast0 3y ago
> Decades ago I declared myself too stupid to use shared memory with threading; I have learned to avoid this whenever possible, or abstract away the memory access under a safe layer as soon as possible. One of the greatest decisions of my career. This probably qualifies you to do shared memory threading, when it is needed. Such as debugging those abstraction layers. Knowing you don't understand it puts you in the right frame of mind to carefully do the work.
- deleted 2y ago
  [deleted]
ratmeadow 3y ago
That atomics talk by Sutter is a superbly high quality explanation, albeit long. He addresses the topic with exceptional rigor and plenty of examples that show what can and can't happen. It for sure took me from 0 to 100 knowledge on thread safety.
eru 3y ago
I agree. Btw, shared memory by itself is fine, even shared memory with threading. The really dangerous ingredient is mutability. And mutability is already toxic waste on its own, and concurrency amplifies the danger.

newpavlov 3y ago

For a more in-depth understanding, I recommend reading "Rust Atomics and Locks": https://marabos.nl/atomics/ https://marabos.nl/atomics/ It uses Rust for examples, but it more or less applicable to C/C++ as well.

chrisaycock 3y ago

The first explanation that really clarified memory barriers for me was from Paul E. McKenney: http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2...

JonChesterfield 3y ago
That one plus the kernel notes at https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt did the trick for me.

king_geedorah 3y ago

No matter how many times I read about these, I'm always left just slightly confused. Acquire/release is about the ordering of instructions within a thread of execution. So if I have a writer writing X, then writing Y, then I need write-release to make sure that the compiler actually puts the instructions for Y after the instructions for X in the machine code. If I want to guarantee that the results of those writes are visible to another thread, then I need a memory fence to force flushing of the caches out to main memory basically? The author mentions the queue as originally written is technically correct for x86/x86_64. This is true only in the sense that neither the producer or consumer can experience partial reads / partial writes, right? It is still possible that if, say, the consumer were busy waiting for an item to be available then it will spin for as long as it takes for the CPU to decide to flush the producer's writes out to main memory? Whenever I see these concepts discussed, it is in the context of the C++ stdatomic library. If I were writing a program in C99, I would assume it would still be possible to communicate the same intent / restrictions to the compiler, but I'm not sure because I haven't been able to find any resources that discuss doing so. How might one communicate that to the compiler, assuming they are on x86/x86_64 where in theory the CPU should just do the right thing with the right machine code? Finally, does target architecture influence the compiler's behavior in this regard at all? For example, if we take x86/x86_64 as having acquire/release semantics without any further work, does telling the compiler that my target architecture is x86/x86_64 imply that those semantics should be used throughout the program?

gpderetta 3y ago
> Acquire/release is about the ordering of instructions within a thread of execution acquire/release is about visibility. Acquire and release always go in pair. You can't really reason purely about a release and an acquire in isolation and that's why simply thinking about instruction reordering is not enough. > So if I have a writer writing X, then writing Y, then I need write-release to make sure that the compiler actually puts the instructions for Y after the instructions for X in the machine code. If I want to guarantee that the results of those writes are visible to another thread, then I need a memory fence to force flushing of the caches out to main memory basically Whether an explicit memory fence is needed or not depends on the architecture (for example you do not need them on x86). But you do not need to care, if you use the atomic operation with the correct semantic, the compiler will insert any required fence for you. As an aside, typically fences have nothing to do with caches. One a store or a load operation hits the cache, the coherence system takes care that everything works correctly. If fences had to flush the cache, they would be orders of magnitude slower. Instead fences (explicit or otherwise) make sure that either memory operations commit (i.e. are visible at the cache layer) in the expected order or that an application can't tell otherwise, i.e. reordering is still permitted across fences as long as conflicts can be detected and repaired, typically this can only happen for loads that can be retried without side effects. > Whenever I see these concepts discussed, it is in the context of the C++ stdatomic library. If I were writing a program in C99, I would assume it would still be possible to communicate the same intent / restrictions to the compiler formally in C99 multithreaded programs are UB. Of course other standards (POSIX, openmp) and implementations (the old GCC __sync_builtins) could give additional guarantees; but only C11 gave a model defined well enough to reason in depth about the overall CPU+compiler system; before that people just had to make a lot of assumptions. > Finally, does target architecture influence the compiler's behavior in this regard at all? For example, if we take x86/x86_64 as having acquire/release semantics without any further work, does telling the compiler that my target architecture is x86/x86_64 imply that those semantics should be used throughout the program? It does, but note that the compiler will only respect acquire/release semantics for atomic objects operations with the required ordering, not normal load and stores.

ajross 3y ago

This bit isn't quite correct: > Acquire and release semantics don’t have any meaning on Intel- and AMD-brand processors. On x86 CPUs, which is to say, on just about any Intel- or AMD-brand CPU you can buy right now, memory operations on a single CPU core happen in program order. In fact x86 CPUs do allow themselves to reorder reads around other reads[1]. The rule is that no memory access is allowed to cross a write operation[2]. The distinction isn't important to traditional critical section analysis like the article is doing, but there are lockless algorithms out there that depend on fully-ordered reads. Dekker's famous (but mostly useless in practice) algorithm for mutual exclusion is one. [1] Note here I'm using the more traditional and frankly much clearer terminology about actual hardware behavior and not the frustrating abstractions embraced by the language design community. [2] Or one of a handful of "serializing instructions", the most commonly relied on being LOCK CMPXCHG

moonchild 3y ago
> x86 CPUs do allow themselves to reorder reads around other reads. The rule is that no memory access is allowed to cross a write operation That's not correct. Intel manual, vol 3, sec. 9.2.2: > Reads are not reordered with other reads > Writes are not reordered with older reads. > Writes to memory are not reordered with other writes A read may be reordered w.r.t. an older write (and hence tfa is incorrect that po=ppo on x86), but reads are not ordered with other reads. You can see in the c/c++ processor mappings here https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html that load acquire/store release can be mapped to plain loads and stores on x86.
- ajross 3y ago
  Oops, indeed. Must be a bit flip error in my memory.
moonchild 3y ago
> more traditional and frankly much clearer terminology about actual hardware behavior and not the frustrating abstractions embraced by the language design community Axiomatic memory models were pushed as much from the hardware world as from the software world if not more so, and they exist for a reason. Overfitting obligatorily abstract models to the behaviour of a particular microarchitecture benefits neither hardware nor software writers

ratmeadow 3y ago

The article says a lot about CPUs reordering memory instructions - is this actually the main cause of the issues with the shown code? Speaking of x86 specifically, instructions are aggressively reordered but as far as I understood it, the results are generally committed in order. The ISA has rules about what memory reorderings can occur, and looks like most reorderings are forbidden. This stackoverflow explains it well: https://stackoverflow.com/a/50310563/7064452 https://stackoverflow.com/a/50310563/7064452 In this queue example I'd say the elephant in the room is the compiler, not the CPU. The code has no language-level synchronisation, therefore the compiler is free to do whatever - it's not surprising memory ops get reordered. If you want to be pedantic, the code is UB with no synchronisation present. Perhaps besides the point to discuss CPU behaviour in this light.

gpderetta 3y ago
The article does mention in the end that a trivial translation of the queue code to x86 will work. It is broken on other architectures though (aside of the obvious UB because of races).
dbcurtis 3y ago
Yes, having worked on one of the out-of-order Intel CPU's, I can tell you that you are correct. Instructions may be "complete", as in their results can be forwarded to later operations, but the instruction isn't "retired" until it is known that it can not raise an exception, or be cancelled because of branch mis-predict, etc. Programmer-visible architectural state as defined in the ISA is not written until instruction retirement. CPU re-ordering instructions is not going to change semantics (in X86 and similar architectures... there are some archs that relax that guarantee). Compilers are notorious for doing dumb things around locks.... the gnu C for AVR architecture, for instance, looks at the SEI instruction (SEt Interrupt mask bit) and notices that it doesn't modify memory or registers, so hoists it to the top of functions. Eh.. No, SEI; CLI; <code> <critical section> <code> is not what I intended... Also... CPU's with data caches can to smart things with architecturally-defined locking instructions such as "test-and-set' or 'compare-and-exchange' such that the instructions are always cache-coherent across CPU's. If you try to roll-your-own locking code, you had best understand how the cache invalidation mechanism works in your chosen CPU or you are going to have a bad day.

alfiedotwtf 3y ago

I’ve read so much through the years on this, and I feel like it’s our Emperor’s Clothes - people pretend to understand, but does anyone actually understand this magic? Like not theoretically-superficially but in practice, or am I just too dumb to see the King’s new attire?

spacechild1 3y ago
I do understand it to the extent that I can write correct lock-free data structures. For me that's enough, I don't need to know what happens exactly in the CPU for each architecture (altough I have some understanding).
klabb3 2y ago
Mozilla had this famous sign 8ft up on the wall that said “you must be this tall to write multi-threaded code”[1]. A lot of people will claim to be able to master it. The track record shows that even the superhuman domain experts make mistakes frequently, as it’s almost impossible to reason about, verify, debug and importantly maintain the invariants as code evolves. And good luck predicting performance implications on different CPUs and workloads. In either case, for software development it doesn’t really matter if there is such a hypothetical person: because nobody else is. In practice it’s similar to protecting against crypto vulns: don’t roll your own, use trusted libs with very few hard-to-misuse data structures and operations, sometimes rely on lang/compiler features, and runtime analysis tooling. Personally I think we eventually need an overhaul in language design, perhaps new concurrent control flow constructs and operations. Just look at the C code shown.. it’s not even “code” in the sense that one line does some logical operation scoped to the current function. No, it’s “markers” that tells compiler and CPU to flush internal caches, change their optimizations as a thread-global “operation”. And the post is introductory, SPSC which is much simpler, doesn’t cover thread parking, MESI, compiler reordering etc. It’s a red flashing sign that the abstractions are all whack, frankly. It’s the anti-thesis of a neat, modularized Russian dolls we typically enjoy with single threaded code, including C. Now, these things are still critical, they work and it’s the best we got. It’s a genuinely hard-hard problem, which is quite humbling given how prevalent, studied and important concurrency is to virtually every programming domain. [1]: https://bholley.net/blog/2015/must-be-this-tall-to-write-multi-threaded-code.html https://bholley.net/blog/2015/must-be-this-tall-to-write-mul...

cryptonector 3y ago

Solaris/Illumos has a better name for this: `membar_producer()` and `membar_consumer()`. The first is release semantics, and it's what a producer must do before it finishes publishing some memory to a consumer. The second is what a consumer must do before it starts consuming what the producer gave it. I find that naming convention much more intuitive than release/acquire, though release/acquire is more general.

liblfds-temp 3y ago

> See how we added a new fence() call to put()? That fixes the reordering problem we’ve described at length. Now if the CPU gets bored waiting for entries[i] to be read into the cache, and tries to pull up the tail++ line so it happens sooner, bonk!, the tail++ line hits that fence and stops moving. We’ve forced the entry to be written before the tail is bumped. Problem solved! I may be completely wrong, it's a complicated subject, but I think the wording here is potentially misleading. As I understand it (and I may be wrong!), a full fence does the following : "all reads and all writes prior to the fence must occur before any reads or writes after the fence". What I'm concerned about is people thinking this is a blocking behaviour, i.e. when we hit the fence, then at that point all prior reads and writes occur. This is not the case. The reads and writes prior to the fence can occur at any time - they could occur LONG AFTER we pass the fence - but what we do get from the fence is that the reads and writes prior to the fence WILL occur BEFORE any reads or writes after the fence. So, to put it another way, the code is executing, we come to the fence - and absolutely nothing happens. The processor just keeps going. No reads occur, no writes occur. Then at some point later on, both in time and in code, the process comes to another (say) read. NOW, finally, the processor MUST complete all reads and writes which were issued prior to the fence.

liblfds-temp 2y ago
A thread which performs a write, has a fence, and then performs another write, will at the time of the second write due to the fence guarantee the first write has completed. However, "completed" is misleading. The write will still not be seen by readers. "Complete" really means "the writer has done all the work he can do, which is necessary but insufficient". For a reader to see the write, the readers must issue a read memory barrier before reading the value. All of this is due to store buffers and cache invalidation requests. In short, in principle, a write is known about only by the processor it occurred upon; if there are any other processors in the system, then unless special magic is performed (fences and so on), any writes they see from other processors are seen purely by chance and can happen in any order (including going backwards in time), or not happen at all. I once read an article which framed all this in terms of source control. Memory is like SVN, or Git. You make local changes (on your processor, which has its local copy of memory). You then commit (write fence/atomic operation). No one else can see your changes until they update from source control and get the latest version (read fence).