Fetch-and-add ordering

Question

I'm working on replacing the allocation system for "stable pointers" in the ghc runtime system, and I'm running up against the limits of my understanding of concurrent programming.

Suppose a variable contains 0. Thread A uses __atomic_fetch_and_add to increment the variable and notifies thread B in some fashion. In response, thread B uses __atomic_fetch_and_add to decrement the same variable, bringing it back to 0. So it seems the variable should go from 0 to 1 and back. Is it guaranteed that another thread C will not see the additions performed in the opposite order to go from 0 to -1 and back?

Answer 1

I just re-read this question adding some additional clarification, and realized I had assumed C11 while your question seems to be using compiler built-ins. From that perspective, if all your memorder use is __ATOMIC_SEQ_CST, there is no case in which you can observe a value of -1 for the same reasons I detail below (from C11).

TL;DR: It depends, but you'd have to really shoot yourself in the foot to not be guaranteed this behavior. Below follows an explanation of why this could happen, how this could happen, and why you're unlikely to run into it happening.

Atomic operations are guaranteed to have a global order, but that global total order is not defined. From the C11 draft, §5.1.2.4p7:

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M.

It is possible by this definition of modifications to M that the total order observed by some other thread is A/B, but B/A is also permitted. This would indeed have the effect of an external observer noticing a value transitioning between -1 and 0 (assuming a signed atomic type).

To deal with this, the standard defines synchronization operations (from paragraph 5 of the same section):

A synchronization operation on one or more memory locations is either an acquire operation, a release operation, both an acquire and release operation, or a consume operation.

Later on, there are some tedious-to-read definitions for how these operations compose to introduce dependencies that ultimately yield a "happens-before" ordering. I'll omit those; §5.1.2.4p14-22 describe observability of side-effects on some object and how dependencies influence that; §7.17.3 describes the API for controlling those dependencies.

Without discussing those sections, it is hopefully enough to say that they do allow for the observer to see the "opposite order" described. You could wind up in this situation when you use atomic_fetch_add_explicit with a memory_order_relaxed argument, and your load is implemented as atomic_load_explicit with the same relaxed memory ordering requirements. In this situation, no "happens-before" relationship is defined, and a system is permitted to allow thread C to observe the modifications in either order.

This is unlikely to be what you would actually do. For one, it's a lot more typing. Secondly, the API naming and use really suggests that you should know what you're doing if you want to use it. This is what I mean in saying you'd really have to shoot yourself in the foot: you're discouraged from doing this sort of thing by default.

If you implemented this purely with atomic_fetch_add, atomic_fetch_sub, and atomic_load (as you would likely do), you would be fine; the standard in §7.17.1p5 states:

The functions not ending in _explicit have the same semantics as the corresponding _explicit function with memory_order_seq_cst for the memory_order argument.

The standard guarantees that this ordering will carry data dependencies such that the write from thread A is seen to "happen-before" the write from thread B. An observer C, with its own consistent memory ordering requirements, is then therefore guaranteed to see operations interleave in the order described as intended.

That all said: if you can use C11, just use ++, --, and =, and you'll be fine. Per §6.5.16.2p3, += and -= operations on atomic types are defined to behave as if using store with memory_order_seq_cst. Per §6.5.3p2, the ++ and -- operators are analogous to the equivalent x+=1 and x-=1 expressions. Simple assignment (§6.5.16.2) specifies that the LHS or RHS can be atomic types, but does not specify the memory order. Jens Gustedt says that operations on _Atomic-qualified objects are guaranteed to have sequential consistency. I can only divine this from footnote 113, and footnotes aren't normative. But I don't think that matters: if all writes are consistent, any read must observe a valid previous state from that total order, which never contains -1.