5 ms·

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

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.
masklinn 5y ago
> 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. It's not "sufficient" for MMIO, it's literally the sole use case for it, and the sole situation where it's correct, because the hardware will not fuck with MMIO accesses either (and not eliding reads is important because reads might have side effects). Although even then you may need to use atomics anyway if the driver is concurrent, because volatiles don't guarantee any sort of atomicity and the reaction of MMIO devices to concurrent access is very likely to be funky (then again these days MMIO is usually a thing on uCs where there is no uncontrolled and arbitrary concurrency). > 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). Except your accesses will be reordered arbitrarily: * volatile instructions are only of concern for the compiler, everything below it has no idea about them, and if you're not in an MMIO context they'll absolutely try to reorder and remove them (and even when they won't since volatiles are not synchronisation point you have no idea how they'll propagate) * volatile instructions are not fences, even for the compiler are no "safe bounds" with volatiles unless all the operations are volatile
- jstimpfle 5y ago
  > even for the compiler are no "safe bounds" with volatiles unless all the operations are volatile That's exactly what I said right? But good to know that volatile won't emit fences.
NobodyNada 5y ago
> 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). That “(inside the safe bounds)” disclaimer is the reason we can’t use volatile for anything meaningful, because volatile does not provide that guarantee. The compiler & hardware will happily let the contents of your critical section float right past the volatile reads/writes “protecting” it. If I write a lock-free queue and use volatile for synchronization, then I’m just protecting the queue itself and not the contents. For instance, if I write to some memory and then push a reference to it onto the queue, other cores might see the reference but not the data. Maybe the volatile writes got rushed through the memory hierarchy & to the other cores, but all the non-volatile writes are still stuck in a cache somewhere until next week. And AFAIK volatile still doesn’t guarantee atomicity in the case of concurrent access. If one thread writes to a volatile variable, other threads can easily see torn writes/“pink elephants”/out-of-nowhere values. Again this is somewhere that x86 provides unnecessarily and somewhat ridiculously strong guarantees that nobody else does, so code that worked on dumb compilers in the 90’s may be very, very, broken today. So please just use atomics. They’re very nice, and they solve all of these problems. If you don’t understand memory ordering semantics just mark everything as sequentially consistent and don’t think about it, I don’t care, just please use atomics.
- jstimpfle 5y ago
  Calm yourself, and be reassured, I'm using atomics and not questioning them :-). I also do understand memory ordering well enough for my purposes (I'm not sure I succeeded but I tried to explain just what you said here).
  - NobodyNada 5y ago
    Glad to hear it :) Re-reading your comment again I think you’re right that we really were just saying the same thing in different ways, I just got tripped up on your “volatile should be fine” language and misread the rest of your comment. Sorry about that, it was a valuable insight!

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.

masklinn 5y ago

> 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. It's not "sufficient" for MMIO, it's literally the sole use case for it, and the sole situation where it's correct, because the hardware will not fuck with MMIO accesses either (and not eliding reads is important because reads might have side effects). Although even then you may need to use atomics anyway if the driver is concurrent, because volatiles don't guarantee any sort of atomicity and the reaction of MMIO devices to concurrent access is very likely to be funky (then again these days MMIO is usually a thing on uCs where there is no uncontrolled and arbitrary concurrency). > 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). Except your accesses will be reordered arbitrarily: * volatile instructions are only of concern for the compiler, everything below it has no idea about them, and if you're not in an MMIO context they'll absolutely try to reorder and remove them (and even when they won't since volatiles are not synchronisation point you have no idea how they'll propagate) * volatile instructions are not fences, even for the compiler are no "safe bounds" with volatiles unless all the operations are volatile

jstimpfle 5y ago
> even for the compiler are no "safe bounds" with volatiles unless all the operations are volatile That's exactly what I said right? But good to know that volatile won't emit fences.

NobodyNada 5y ago

> 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). That “(inside the safe bounds)” disclaimer is the reason we can’t use volatile for anything meaningful, because volatile does not provide that guarantee. The compiler & hardware will happily let the contents of your critical section float right past the volatile reads/writes “protecting” it. If I write a lock-free queue and use volatile for synchronization, then I’m just protecting the queue itself and not the contents. For instance, if I write to some memory and then push a reference to it onto the queue, other cores might see the reference but not the data. Maybe the volatile writes got rushed through the memory hierarchy & to the other cores, but all the non-volatile writes are still stuck in a cache somewhere until next week. And AFAIK volatile still doesn’t guarantee atomicity in the case of concurrent access. If one thread writes to a volatile variable, other threads can easily see torn writes/“pink elephants”/out-of-nowhere values. Again this is somewhere that x86 provides unnecessarily and somewhat ridiculously strong guarantees that nobody else does, so code that worked on dumb compilers in the 90’s may be very, very, broken today. So please just use atomics. They’re very nice, and they solve all of these problems. If you don’t understand memory ordering semantics just mark everything as sequentially consistent and don’t think about it, I don’t care, just please use atomics.

jstimpfle 5y ago
Calm yourself, and be reassured, I'm using atomics and not questioning them :-). I also do understand memory ordering well enough for my purposes (I'm not sure I succeeded but I tried to explain just what you said here).
- NobodyNada 5y ago
  Glad to hear it :) Re-reading your comment again I think you’re right that we really were just saying the same thing in different ways, I just got tripped up on your “volatile should be fine” language and misread the rest of your comment. Sorry about that, it was a valuable insight!