4 ms·
"Benign data races" have been considered harmful from a theoretical perspective for decades. But most deployed CPUs had memory semantics that made them work. Mo
by Animats 6y ago
"Benign data races" have been considered harmful from a theoretical perspective for decades. But most deployed CPUs had memory semantics that made them work. Mostly.
On x86 multiprocessors, if, without taking any special measures, you set x=1 from processor 0, and processor 1 reads x shortly, but not too shortly, thereafter, it will see 1. If you try that on, say, an 80-core ARM CPU [1], CPU #53 might not see a 1 for a long time, if ever.[2] You're no longer guaranteed that cache changes propagate unasked. As we get more and more CPUs, the cost of creating the illusion that there's a single memory goes up. It's now important that compilers know what's shared so they can generate the proper fence and barrier instructions. Especially since the latest iteration of ARM has new features such as "non-temporal load and store."
What used to be a theoretical problem, or at most a problem for OS architects, has thus acquired teeth and claws that can bite ordinary applications programmers.
This is where traditional C++ mutexes start to break down. From a theoretical perspective, it's always been annoying that mutexes at the POSIX level have no tie to what they're supposed to be protecting. Hitting a mutex has to mean "flush everything". That's inefficient. Rust has the advantage that its locks own data, so the compiler knows what has to be flushed. That becomes more important as the number of CPU cores becomes very large.
I've said for years that the three issues in C/C++ are "how big is it", "who owns it", and "who locks it". C++ now at least has abstractions for all of these, although they all leak. You can still get raw pointers out to misuse, or, more likely, pass to some API for misuse.
[1] https://venturebeat.com/2020/03/03/ampere-altra-is-the-first-80-core-arm-based-server-processor/ https://venturebeat.com/2020/03/03/ampere-altra-is-the-first...
[2] https://developer.arm.com/documentation/den0024/a/the-a64-instruction-set/memory-access-instructions/memory-barrier-and-fence-instructions https://developer.arm.com/documentation/den0024/a/the-a64-in...
- rrss 6y ago> If you try that on, say, an 80-core ARM CPU [1], CPU #53 might not see a 1 for a long time, if ever.[2] You're no longer guaranteed that cache changes propagate unasked. What do you mean by this? ARM requires cache coherency for data caches, which requires that every store is eventually made visible to all cores. Fences are necessary to impose additional requirements on the order which writes to different addresses are made visible, but AFAIK not necessary to ensure that a single write is eventually visible.
- Animats 6y agoNot sure how Load-Acquire (LDAR) and Store-Release (STLR) fit into this. They seem to be intended to be atomic only against other LDAR/STLR pairs, rather than doing a general flush. There's also the whole "shareability domain" thing - full system, outer sharable, inner sharable, and non-sharable. Barrier instructions get to specify how much consistency breadth to request. So there are situations when every store may not be visible to every CPU core, but the ones that don't get the word shouldn't have access to that memory anyway. You can sort of see the architects of the CPU trying hard to prevent the cache system from choking on inter-CPU traffic, and trying to get more help from the software.
- millstone 6y ago"Atomic" is probably the wrong term at this level. For a CPU, all loads and stores are atomic (assuming aligned and <= word size). On an out-of-order CPU, loads and stores go into a buffer which may process its entries in a different order. Fences like LDA and STL prevent certain reorderings.
- rigtorp 6y agoAll loads and stores are atomic. I'm also pretty sure ARM has coherent caches. What ARM does allow is for CPUs to optimize the order it loads and stores from cache as opposed to x86 TSO guarantee. DMB barrier instruction on ARM allows you to control how L/S may be reordered. Both x86 and ARM have special types of memory regions such as uncachable memory, but that's not something you are going to see outside of kernel space.
- rrss 6y agoInner vs outer shareable is not particularly relevant for applications - from the ARM ARM: > This architecture assumes that all PEs that use the same operating system or hypervisor are in the same Inner Shareable shareability domain. [PE = processing element - i.e. core] i.e. if you a running a userspace program, all the cores are in the same shareability domain. (I think your comments about LDAR/STLR are a response to 'adwn's sibling comment). Eventual write propagation is a very basic liveness guarantee for systems with coherent caches. I'm pretty sure that the ARM architecture requires it for Observers with coherent caches, but event if not, it would be very surprising if a mainstream implementation didn't provide this guarantee. Barrier instructions provide control of ordering relationships between accesses and when accesses complete, but I believe there is a guarantee that accesses eventually complete even without barriers. (Also from the ARM ARM (B2.3.7), "complete" here means "visible to other cores": "Any read to the same Location by an Observer within the shareability domain will either Reads-from W1 or Reads-from a write that is Coherence-after W1.") I'd be very interested to learn that ARM (or Ampere Altra) doesn't guarantee eventual write propragation, but that needs a better source than [2].
- adwn 6y ago> You're no longer guaranteed that cache changes propagate unasked. Huh? Yes, you can: Caches in multi-core ARM systems are still coherent, so once a write operation reaches any level of the cache hierarchy (typically level 1) and updates that cache line, all other cores will see the updated value when they read from that address. That's not what you need memory consistency operations, like load acquire and store release, for. You need those to make sure that a write from a write operation has been written to the cache, because it might still linger in the store buffer, which sits between the execution unit and the cache. > Rust has the advantage that its locks own data, so the compiler knows what has to be flushed. That's absolutely not how Rust works. The Rust compiler has no notion of a mutex, only of atomic operations. Mutexes are purely library constructs – as shown by the parking_lot crate [1], which implements its own mutex independently of the standard library mutex. [1] https://github.com/Amanieu/parking_lot https://github.com/Amanieu/parking_lot
- Animats 6y ago"A lock knows what data it protects, and Rust guarantees that the data can only be accessed when the lock is held. State is never accidentally shared. "Lock data, not code" is enforced in Rust." [1] https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.html https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.h...
- khuey 6y agoThat does not actually boil down to anything at the CPU level. That's just a (better) abstraction for the Rust programmer.
- adwn 6y agoThe issue isn't whether the compiler knows which data is affected and which isn't, but rather that the compiler doesn't know about the semantics of the mutex. However, the library knows about the semantics of the mutex, and it could explicitly instruct the processor to only flush certain memory regions from the store buffer when the mutex is unlocked. But then again, that's not Rust-specific – a C++ library could do the same.
- 6y ago
- sitkack 6y agoThe idea of memory being a shared scratch space for multiple cpus makes a lot of sense for a first order design perspective, but it really no longer holds. CPUs are now distributed systems and should acknowledge that. What do you think about each CPU owning its own memory region and that to send values to other CPUs, one would have to do a send, either symbolically or physically, that could be implementation dependent. Abstractions that aren't total and sound are insufficient and should be flagged by the compiler.
- a1369209993 6y ago> to send values to other CPUs, one would have to do a send, either symbolically or physically The funny thing is, that pretty much is what store-release is (with load-acquire being the corresponding recv), anyway, just without any memory safety or sanity-checking.
- a1369209993 6y ago> without any memory safety Actually, I think that would be memory protection, not safety.
- Animats 6y agoYes. We're there already, with "sharability regions". So far, only the OS has to deal with that; each process (always?) is in one sharability region. (Shared memory between processes, though - how does that work now on machines with sharability regions?) Total sharability slows down systems with large numbers of CPU cores. We're seeing the hardware features appear to allow for less sharability. It's not being used much yet. These have programming implications, and OSs and languages have to keep up. Probably more the OS for now, with groups of CPUs and areas of memory dedicated to each other. Can Linux cgroups be used that way? This has to be invisible to the application programmer, somehow. Or we'll have another hard to program mess like the Cell.