Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Making Sense of Acquire-Release Semantics

davekilian.com

Post reply on HN
Print view View original

21–30 of 72 posts

Re: Making Sense of Acquire-Release Semantics

#21

Post by JonChesterfield »

mevric wrote: post #19
catlifeonmars wrote: post #2

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.

I am curious to understand how the following is achieved? Is there a material on this? "storing two uint32 as a uint64"

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.

Re: Making Sense of Acquire-Release Semantics

#22

Post by toast0 »

zevv wrote: post #3

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 lo…

> 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.

Re: Making Sense of Acquire-Release Semantics

#23

Post by king_geedorah »

moonchild wrote: post #11
king_geedorah wrote: post #6

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 ar…

> 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 You cannot. See boehm, 'threads cannot be implemented as a library' ( https://web.archive.org/web/20240118063106if_/https://www.hp... ). You can do that in c11, however, which includes fun…

Claro. Thank you for the threads as libraries link; very interesting.

Re: Making Sense of Acquire-Release Semantics

#24

Post by ajross »

gary_0 wrote: post #16
ajross wrote: post #14

Earlier quoted context omitted.

> Overfitting obligatorily abstract models to the behaviour of a particular microarchitecture benefits neither hardware nor software writers I'm too dumb to know what the first clause means. But the second is silly: understanding how to control the ordering of the actual memory operations (i.e. the mapping to actual behavior as seen on a bus/interconnect somewhere) can only benefit hardware writers (because it tells…

What moonchild meant is that higher-level semantics are necessary because directly describing what the hardware is doing won't work because almost every model of CPU does something slightly different. Your argument that the higher-level terminology the industry settled on is confusing is valid (albeit subjective). > Acquire/release is abstract egghead stuff The article explains why this functionality is named that wa…

> What moonchild meant

To spell it out: I know very well what moonchild meant, and am no stranger to lockless algorithm design or memory ordering semantics. It was a turn of phrase riffing on the point that "memory ordering semantics are APIs" and thus should have been designed with an eye toward clarity and comprehension for the working programmers who need to use them.

Acquire/release was intended to make the job of a compiler author easier, by trying to home in on the differences between hardware that might be reasonably abstracted as a single API. And I'm saying that's a bad trade, because the compiler nerds are doing just fine and what the dumb jocks in the trenches want is read and write barriers.

Re: Making Sense of Acquire-Release Semantics

#25

Post by king_geedorah »

JonChesterfield wrote: post #18
king_geedorah wrote: post #6

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 ar…

If you program without fences, instructions are reordered by the compiler and/or the processor as they see fit provided the single threaded semantics are unchanged. This is why alias analysis is a big deal. A store can be moved before a load if they are independent, i.e. do not alias. A store followed by a load can be simplified to use the value already in a register if there is no other store in the meantime. This d…

Would it be correct to say that acquire-release is in some sense "higher level" than memory fences, with acq-rel implemented in terms of fences (and restrictions on code-gen?) and fences being all that the CPU actually knows about at least in the case of x86_64?

Re: Making Sense of Acquire-Release Semantics

#26

Post by mevric »

JonChesterfield wrote: post #21
mevric wrote: post #19

Earlier quoted context omitted.

I am curious to understand how the following is achieved? Is there a material on this? "storing two uint32 as a uint64"

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.

Thank you!!

Re: Making Sense of Acquire-Release Semantics

#27

Post by ratmeadow »

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

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.

Re: Making Sense of Acquire-Release Semantics

#28

Post by gpderetta »

ratmeadow wrote: post #27

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 we…

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).

Re: Making Sense of Acquire-Release Semantics

#29

Post by gpderetta »

king_geedorah wrote: post #25
JonChesterfield wrote: post #18

Earlier quoted context omitted.

If you program without fences, instructions are reordered by the compiler and/or the processor as they see fit provided the single threaded semantics are unchanged. This is why alias analysis is a big deal. A store can be moved before a load if they are independent, i.e. do not alias. A store followed by a load can be simplified to use the value already in a register if there is no other store in the meantime. This d…

Would it be correct to say that acquire-release is in some sense "higher level" than memory fences, with acq-rel implemented in terms of fences (and restrictions on code-gen?) and fences being all that the CPU actually knows about at least in the case of x86_64?

Acquire/release is higher level because it is more of a theoretical description than an hardware description. But acq/rel is not implemented using fences on x86. On this arch all loads and stores have implicit acquire and release semantics respectively, while all RMW are sequentially consistent acq+rel. The compiler will need to emit explicit fences very rarely on x86.

Re: Making Sense of Acquire-Release Semantics

#30

Post by dbcurtis »

ratmeadow wrote: post #27

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 we…

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; 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.

Post reply on HN