Live data from Hacker News

Making Sense of Acquire-Release Semantics

davekilian.com

61–70 of 72 posts

Re: Making Sense of Acquire-Release Semantics

#61

Earlier quoted context omitted.

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

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

> 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

Re: Making Sense of Acquire-Release Semantics

#62

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

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

What do you mean? Are you implying that read-modify-writes are treated differently from plain writes by the cache coherency protocol?

Re: Making Sense of Acquire-Release Semantics

#63

Earlier quoted context omitted.

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.

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)

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

I was probably misremembering the details. The manual has to say this regarding #LOCK prefixed operations:

"Software should access semaphores (shared memory used for signalling between multiple processors) using identical addresses and operand lengths. For example, if one processor accesses a semaphore using a word access, other processors should not access the semaphore using a byte access"

which is already vague enough, but regarding general atomic load and stores I couldn't find anything.

Re: Making Sense of Acquire-Release Semantics

#64

Earlier quoted context omitted.

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)

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

Tbf you could say stores happen in order, and loads can happen out of order unless you fence. Personally I don't understand why we need such strong ordering constraints for weakly ordered reads—istm you can go much weaker and maintain sanity.

Re: Making Sense of Acquire-Release Semantics

#65

Earlier quoted context omitted.

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

> 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. What do you mean? Are you implying that read-…

I'm saying that an atomic RMW is going to get the cache line in "exclusive" state, (in typical MESI protocol) but that if you are trying to gin up the equivalent with spin locks you need to think through how that plays out, as the reads might be in "shared" state.

Re: Making Sense of Acquire-Release Semantics

#66

Earlier quoted context omitted.

> 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. What do you mean? Are you implying that read-…

I'm saying that an atomic RMW is going to get the cache line in "exclusive" state, (in typical MESI protocol) but that if you are trying to gin up the equivalent with spin locks you need to think through how that plays out, as the reads might be in "shared" state.

I still don't see what you're getting at. What is the implication of this for software? The implementation of the cache coherency protocol is largely opaque to software.

Re: Making Sense of Acquire-Release Semantics

#67

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

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

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

That's actually not really true, what you are describing is a non-coherent system.

On a cc system, once a store is no longer speculative, it is guaranteed to be flushed out of the store buffer into the cache, and a load that reaches the cache layer is guaranteed to see the last version of the data that was stored in that memory location by any coherent agent in the system.

As pointed out elsethread, you need load barriers specifically to order your loads, so they are needed for ordering, not visibility.

The way that barriers contribute to visibility (and the reason that they need to be paired) is by giving conditionally guarantees: T: S.1; #StoreStore; S.2 T2: L2 #LoadLoad L.1. If T2 observers from its first load at memory location .2 the value stored by S.2, then it is guaranteed that L.1 will observer the value stored by S.1. So cache coherency plus purely local load and store barriers give you the global Acquire/Release model.

Re: Making Sense of Acquire-Release Semantics

#68
post #57

Earlier quoted context omitted.

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

You do not need a load barrier to observe stores from other cores. You need the load barrier so your own core does not reorder loads otherwise you could see wacky loads even if the stores are totally ordered. As a example, suppose we have totally ordered stores, but loads can be reordered freely. Suppose X is 0 and Y is 0, then we store X to 1 then store Y to 1. Therefore, Y can only be 1 after X is 1. But, if you ca…

> You do not need a load barrier to observe stores from other cores. You need the load barrier so your own core does not reorder loads otherwise you could see wacky loads even if the stores are totally ordered.

Yes. I mean, you need the load barrier to see stores safely. Also, in principle, since AFAIK there are no guarantees about cache invalidation request behaviour, in theory it could fail to be read forever - in which case you would in fact literally never see the writes on other cores (until you issued a read barrier).

Re: Making Sense of Acquire-Release Semantics

#69

Earlier quoted context omitted.

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

> 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). That's actually not really true, what you are describing is a non-coherent system. On a cc system, once a store is no longer speculative, it is guaranteed to be flushed out of th…

> On a cc system, once a store is no longer speculative, it is guaranteed to be flushed out of the store buffer into the cache,

That's the thing - I may be wrong, but I'm under the impression store buffers do not guarantee anything. I'm pretty certain they do not on Intel, for example. All you read in the docs is "flushed in a reasonable time", which can mean anything.

> and a load that reaches the cache layer is guaranteed to see the last version of the data that was stored in that memory location by any coherent agent in the system.

Yes.

> As pointed out elsethread, you need load barriers specifically to order your loads, so they are needed for ordering, not visibility.

Mmm - again, I may be wrong; but I think also no guarantees about behaviour of handling of cache invalidation requests. Given no guarantee, then in theory the invalidation request is never handled (unless you force it to be with a read barrier).

When I need a set of data to be written (say a struct - something bigger than you can manage in an atomic op), I'll write to the struct, fence, then perform a throw-away atomic op. The atomic op forces a write (a normal write could just be deferred and not force completion of pre-barrier writes) and then I know my struct has gone out past the store buffer and has reached cache control.

Re: Making Sense of Acquire-Release Semantics

#70

Earlier quoted context omitted.

> 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). That's actually not really true, what you are describing is a non-coherent system. On a cc system, once a store is no longer speculative, it is guaranteed to be flushed out of th…

> On a cc system, once a store is no longer speculative, it is guaranteed to be flushed out of the store buffer into the cache, That's the thing - I may be wrong, but I'm under the impression store buffers do not guarantee anything. I'm pretty certain they do not on Intel, for example. All you read in the docs is "flushed in a reasonable time", which can mean anything. > and a load that reaches the cache layer is gua…

The cpu still need to guarantee forward progress. The store buffer is always flushed as fast as possible (i.e. as soon as the cpu can acquire the cacheline in exclusive mode, which is guaranteed to happen in a finite time). I can't point you to the exact working in the intel docs as they are quite messy, but you can implement a perfectly C++11 compliant SPSC queue purely with load and stores on x86 without any fences or #LOCK operations.

What fences (and atomic RMWs) do on intel is to act as synchronization, preventing subsequent reads to complete before any store preceding the fence. This was originally implemented simply by stalling the pipeline, but these days I suspect the loads have an implicit dependency on a dummy store on the store buffer representing the fence (possibly reusing the alias detection machinery?).

Post reply on HN