4 ms·

Note that “slightly off-the-beaten-path concurrency stuff” may not be correct in today’s world, especially if it uses ‘volatile’. This is primarily because memo

Note that “slightly off-the-beaten-path concurrency stuff” may not be correct in today’s world, especially if it uses ‘volatile’. This is primarily because memory accesses can now be reordered throughout the compiler/processor stack, from the optimizer down to out-of-order execution down to the memory hierarchy. In particular, C(++) guarantees that volatile reads/writes will never be reordered with one another, but they may be reordered with reads/writes to other variables [0] (and this ordering may not be consistent across CPU cores). Importantly, the x86 ISA provides much stronger guarantees than C/C++. AFAIK the only memory reordering allowed is that a write followed by a read can be swapped around. This is extremely strict (we can’t even reorder adjacent reads) and literally any other processor architecture will provide much weaker guarantees. And because C and C++ formally defined a weak memory model in 2011, modern compilers are free (even when targeting x86 chips) to perform optimizations that reorder memory accesses in ways programmers familiar with x86’s semantics might not expect. So an algorithm that worked on x86 processors 10-15 years ago may no longer be correct when compiled with a modern optimizing compiler, or when running on ARM. (If in doubt, you should be OK replacing anything volatile with an atomic and specifying sequentially-consistent ordering semantics for all operations — which you can do in Rust!) [0]: https://systemtbe.blogspot.com/2014/05/volatile-memory-barriers-and-loadstore.html?m=1 https://systemtbe.blogspot.com/2014/05/volatile-memory-barri...

gpderetta 5y ago
To be clear, plain C volatile has never been sufficent even on x86. This has not changed with C++11/C11. For example the linux kernel (which has yet to embrace the C11 MM) has always used memory and compiler barriers were needed even on x86 for decades. Java volatile is different of course.
- jstimpfle 5y ago
  As long as you use C's volatile for all the variables that are involved in a (lock-free) transaction, you should be fine I think. For example, volatile is said to be sufficient for interfacing with hardware through memory mapped regions, because that is one area where it is very clear what the outputs are and one can just make all those accesses volatile so they won't get reordered. Although, having to go all-volatile is maybe too much of a constraint, when many algorithms (like lock-free queues etc.) only require like 3 non-reordered accesses (2 to begin, 1 to end?) to safeguard a transaction, and then the remaining reads and writes can be reordered arbitrarily (inside the safe bounds).
  - adwn 5y ago
    > As long as you use C's volatile for all the variables that are involved in a (lock-free) transaction, you should be fine I think. No, you really won't, neither in C nor in Rust. There are (at least) two reasons for that: 1) You can't do atomic read-modify-write operations (like fetch_add) with volatile. 2) "volatile" is meant for the compiler, not for the processor. Volatile accesses are compiled down to regular read and write machine instructions, so you won't get any ordering guarantees for code running concurrently on different cores. The reason "volatile" is useful for memory-mapped IO is that such memory is mapped with different flags for cacheability than regular memory. For example, given the right flags, the processor won't cache stores in a store-buffer, or won't coalesce smaller stores into larger stores before sending them up the memory hierarchy.
    - jstimpfle 5y ago
      > You can't do atomic read-modify-write operations (like fetch_add) with volatile. Are those operations so important? All I've ever done to be honest is implement some lock-free SRSW queues, and those can be easily implemented with just acquire/release semantics. No atomic read-modify-write needed. Could it be that those are only needed when more than 2 threads are involved?
      - adwn 5y ago
        > Are those operations so important? Yes, absolutely. You can't even implement thread-safe reference counting (std::sync::Arc in Rust) without atomic RMW – or even a thread-safe counter. A lock-free single-produce-single-consumer (SPSC) queue is pretty simple. As soon as you have more than one producer or more than one consumer, you need atomic RMW.
  - gpderetta 5y ago
    Peterson algorithm is broken on x86 if implemented with just volatiles. The compiler will not emit the required fences. On x86 if everything that can be potentially shared is volatile, you may get away with it if you only need acquire/release, but in practice not everything being shared are not going to be volatile. For example if you implement a spsc queue only with volatile operations and use it to send a pointer to a non volatile object to another thread, the consumer might see a non initialized object.
adrian_b 5y ago
No, the x86 ISA guarantees only that the writes are never reordered (unless they are marked as non-temporal or they are made to write-combining memory). The reads can always be reordered, unless they access uncacheable memory, which can happen only in device drivers, not in normal applications. x86 provides 3 memory fences (LFENCE, SFENCE, MFENCE) which must be used when you need a certain ordering of the reads or of the reads around writes.
- adrian_b 5y ago
  Someone who downvoted this was right, my memory was wrong. On x86, reads can be reordered between themselves only for non-temporal transfers. For the normal case, when the accesses are made to cacheable read-write memory, the reads are not reordered between themselves.

gpderetta 5y ago

To be clear, plain C volatile has never been sufficent even on x86. This has not changed with C++11/C11. For example the linux kernel (which has yet to embrace the C11 MM) has always used memory and compiler barriers were needed even on x86 for decades. Java volatile is different of course.

jstimpfle 5y ago
As long as you use C's volatile for all the variables that are involved in a (lock-free) transaction, you should be fine I think. For example, volatile is said to be sufficient for interfacing with hardware through memory mapped regions, because that is one area where it is very clear what the outputs are and one can just make all those accesses volatile so they won't get reordered. Although, having to go all-volatile is maybe too much of a constraint, when many algorithms (like lock-free queues etc.) only require like 3 non-reordered accesses (2 to begin, 1 to end?) to safeguard a transaction, and then the remaining reads and writes can be reordered arbitrarily (inside the safe bounds).
- adwn 5y ago
  > As long as you use C's volatile for all the variables that are involved in a (lock-free) transaction, you should be fine I think. No, you really won't, neither in C nor in Rust. There are (at least) two reasons for that: 1) You can't do atomic read-modify-write operations (like fetch_add) with volatile. 2) "volatile" is meant for the compiler, not for the processor. Volatile accesses are compiled down to regular read and write machine instructions, so you won't get any ordering guarantees for code running concurrently on different cores. The reason "volatile" is useful for memory-mapped IO is that such memory is mapped with different flags for cacheability than regular memory. For example, given the right flags, the processor won't cache stores in a store-buffer, or won't coalesce smaller stores into larger stores before sending them up the memory hierarchy.
  - jstimpfle 5y ago
    > You can't do atomic read-modify-write operations (like fetch_add) with volatile. Are those operations so important? All I've ever done to be honest is implement some lock-free SRSW queues, and those can be easily implemented with just acquire/release semantics. No atomic read-modify-write needed. Could it be that those are only needed when more than 2 threads are involved?
    - adwn 5y ago
      > Are those operations so important? Yes, absolutely. You can't even implement thread-safe reference counting (std::sync::Arc in Rust) without atomic RMW – or even a thread-safe counter. A lock-free single-produce-single-consumer (SPSC) queue is pretty simple. As soon as you have more than one producer or more than one consumer, you need atomic RMW.
- gpderetta 5y ago
  Peterson algorithm is broken on x86 if implemented with just volatiles. The compiler will not emit the required fences. On x86 if everything that can be potentially shared is volatile, you may get away with it if you only need acquire/release, but in practice not everything being shared are not going to be volatile. For example if you implement a spsc queue only with volatile operations and use it to send a pointer to a non volatile object to another thread, the consumer might see a non initialized object.

adrian_b 5y ago

No, the x86 ISA guarantees only that the writes are never reordered (unless they are marked as non-temporal or they are made to write-combining memory). The reads can always be reordered, unless they access uncacheable memory, which can happen only in device drivers, not in normal applications. x86 provides 3 memory fences (LFENCE, SFENCE, MFENCE) which must be used when you need a certain ordering of the reads or of the reads around writes.

adrian_b 5y ago
Someone who downvoted this was right, my memory was wrong. On x86, reads can be reordered between themselves only for non-temporal transfers. For the normal case, when the accesses are made to cacheable read-write memory, the reads are not reordered between themselves.