12 ms·

A bug that doesn’t exist on x86: Exploiting an ARM-only race condition

291 points by stong1 5y ago

cookiewill 5y ago
Is it normal for the .got.plt section to be writable rather than read-only?
im3w1l 5y ago
And arm-windows will (does already?) run x86 binaries with weaker memory ordering than they were written for. So this could be a real thing soon.
- kevingadd 5y ago
  Are you sure the translators don't insert code necessary to maintain ordering? I would be shocked if most threaded code works when you throw out the x86 memory model. Managed runtimes like .NET definitely generate code for each target designed to maintain the correct memory model.
  - pmuderoc 5y ago
    They better do, but then, how would an automatic translator know that this is a "release semantics" atomic store operation? Because on x86 it is, no special barriers or instructions necessary. mov [shared_data], 1 mov [release_flag], 1
    - my123 5y ago
      It’s pessimistic and converts over a lot of memory accesses to RCpc or atomics. (on ARMv8.0 where you don’t have those, barriers are used more) TSO pessimization is the only way to make the thing work at a translation time cost that isn’t too high.
      - gpderetta 5y ago
        Or you support TSO directly on your cpu like Apple does on M1.
        tsimionescu 5y ago
        Sure, but Windows on ARM has to run on many ARM processors, not a specific one designed by MS. They could detect if the processor has non-standard TSO support and use that when running an x86 app, but they still have to do something to run the x86 app on a standard ARM processor.
  - my123 5y ago
    Maintaining the memory model guarantees is what causes the steep cost in performance when using x86 apps on Windows on Arm. That said, heuristics are used to speed it up. I would recommend not sharing values in the stack between threads for synchronisation for example.
  - nyanpasu64 5y ago
    https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on-arm-program-compat-troubleshooter https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on... > You can also select multi-core settings, as shown here... These settings change the number of memory barriers used to synchronize memory accesses between cores in apps during emulation. Fast is the default mode, but the strict and very strict options will increase the number of barriers. This slows down the app, but reduces the risk of app errors. The single-core option removes all barriers but forces all app threads to run on a single core. https://news.ycombinator.com/item?id=28732273 https://news.ycombinator.com/item?id=28732273 zamadatix's interprets this as Microsoft saying that by default, Windows on ARM runs x86 apps without x86 TSO, and turns on extra memory barriers using per-app compatibility settings. But if an app needs TSO but isn't in Windows's database, it will crash or silently corrupt data.
- xxs 5y ago
  Normally the code should have all the needed memory fences as if running on DEC Alpha, e.g. linux does that, and the compilers omit the unneeded ones.
  - monocasa 5y ago
    And since the compiler omitted it on x86, an x86 emulator doesn't have access to where they're required as seen by the compiler.
    - xxs 5y ago
      emulator would have a zero issue, if it's a direct transfer for assembly (not an emulator), it'd need either hardware support - e.g. apple chips, or memory barriers. The differences between arm and x86 are known for 15y+, there is nothing new about it. Also concurrency support is one of the major benefits of languages with proper memory model - java started it with JMM[0] [0]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedL...
      - gpderetta 5y ago
        Any emulator that wants to be remotely performance competitive will do dynamic translation (i.e JIT). In fact ahead-of-time translation is not really feasible. Memory models and JVM are not really relevant when discussing running binaries for a different architecture.
        secondcoming 5y ago
        Doesn't the JVM define its own memory model?
        gpderetta 5y ago
        Sure, but how's that relevant when discussing running x86 binaries on ARM?
- belter 5y ago
  Now I am worried. Do you have a reference please?
  - im3w1l 5y ago
    Best I could find. It's not a great reference because it doesn't give any details but it does prove that it's a thing. https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on-arm-program-compat-troubleshooter https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on...
half-kh-hacker 5y ago
this slaps. I always see perfect blue a few places above us!
- nyanpasu64 5y ago
  Context for downvoters: "perfect blue" is the CTF group writing this article, and "a few places" means CTF team rankings in competitions.
Azsy 5y ago
Have i told you about our lord and savior Rust? Anyways, https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom is used by any serious library doing atomic ops/synchronization and it blew me away with how fast it can catch most bugs like this.
- nyanpasu64 5y ago
  Rust doesn't catch memory ordering errors, which can result in behavioral bugs in safe Rust and data races and memory unsafety in unsafe Rust. But Loom is an excellent tool for catching ordering errors, though its UnsafeCell API differs from std's (and worse yet, some people report Loom returns false positives/negatives in some cases: https://github.com/tokio-rs/loom/issues/180 https://github.com/tokio-rs/loom/issues/180, possibly https://github.com/tokio-rs/loom/issues/166 https://github.com/tokio-rs/loom/issues/166).
  - Fiahil 5y ago
    I think it's fixable, the main reactor is what matters. You can add or remove as many synchronisation primitive as you like. Other tooling, like Jepsen, will interact with your program at a higher level.
  - CodesInChaos 5y ago
    It doesn't catch all of them. But data-races on plain memory access are impossible in safe rust. And atomics force you to specify an ordering on every access, which helps both the writer (forced to think about which ordering they need) and reviewer (by communicating intent).
  - tialaramex 5y ago
    > which can result in behavioral bugs in safe Rust For example, Rust doesn't have any way to know that your chosen lock-free algorithm relies on Acquire-release semantics to perform as intended, and so if you write safe Rust to implement it with Relaxed ordering, it will compile, and run, and on x86-64 it will even work just fine because the cheap behaviour on x86-64 has Acquire-release semantics anyway. But on ARM your program doesn't work because ARM really does have a Relaxed mode and without Acquire-release what you've got is not the clever lock-free algorithm you intended after all. However, if you don't even understand what Ordering is, and just try to implement the naive algorithm in Rust without Atomic operations that take an Ordering, Rust won't compile your program at all because it could race. So this way you are at least confronted with the fact that it's time to learn about Ordering if you want to implement this algorithm and if you pick Relaxed you can keep the resulting (safe) mess you made.
agalunar 5y ago
Great write-up! There may be a typo in section 3: > It will happily retire instruction 6 before instruction 5. If memory serves, although instructions can execute out-of-order, they retire in-order (hence the "re-order buffer").
- colejohnson66 5y ago
  You are correct. The retire unit ensures that all micro ops are retired in order
- stong1 5y ago
  Nice catch. I fixed it. I should have said "execute" rather than "retire".
beebmam 5y ago
Like quantum physics, memory ordering is deeply unintuitive (on platforms like ARM). Unlike quantum physics, which is an unfortunate immutable fact of the universe, we got ourselves into this mess and we have no one to blame but ourselves for it. I'm only somewhat joking. People need to understand these memory models if they intend on writing atomic operations in their software, even if they aren't currently targeting ARM platforms. In this era, it's absurdly easy to change an an LLVM compiler to target aarch64, and it will happen for plenty of software that was written without ever considering the differences in atomic behavior on this platform.
- newpavlov 5y ago
  Memory ordering gets somewhat easier after you understand that flat memory shared by execution units is a leaky abstraction desperately patched over decades by layer and layers of hardware and software. Memory ordering is one way to represent message passing and synchronization between different cores and RAM. This why I think that "lock-free algorithms" is a misnomer, you still have synchronization, but you simply rely on hardware for it.
  - gpderetta 5y ago
    That's actually a common misconception. Memory ordering, on the majority of common cpus, has nothing to do with interprocessor communication or processor-ram communication. Common memory coherency protocols (I.e. MESI and derivatives) guarantee that all caches have a consistent view of memory. Usually memory reordering is purely artifact of the way CPUs access their private L1-cache.
    - yvdriess 5y ago
      For the record, this is false. It is conflating memory coherency with consistency. Nearly everything in a modern processor is a source of reordering, from branch prediction to basically everything in the OoO backend. Any time you leave the core, there's reordering happening in the network. And yes, that includes caches, which involve a heavy amount of inter-core communication. When you issue two successive loads to different cache lines, which one is going to return first? The OoO backend itself manages hazards and ensures that ld/st instructions are retired in the correct order to maintain the processor's memory consistency model. Software can build on top of that, e.g. with fences, to impose stricter consistency models.
amelius 5y ago
Does the race condition exist when emulating x86 on Apple M1?
- saagarjha 5y ago
  No. Rosetta emulates TSO correctly.
  - addaon 5y ago
    To draw together the two answers here to the original question. 1) Emulating an ISA includes emulating its memory model. As saagarjha says, this means that Rosetta 2 must (and does) correctly implement total store ordering. 2) There are various ways to implement this. For emulators that include a binary translation layer (that is, that translate x86 opcodes into a sequence of ARM opcodes), one route is to generate the appropriate ARM memory barriers as part of the translation. Even with optimization to reduce the number of necessary barriers, though, this is expensive. Instead, as mmwelt mentions, Apple took an unusual route here. The Apple Silicon MMU can be configured on a per-page basis to use either the relaxed ARM memory model or the TSO x86 memory model. There is a performance cost at the hardware level for using TSO, and there is a cost in silicon area for supporting both; but from the point of view of Rosetta 2, all it has to do is mark x86-accessed pages as TSO and the hardware takes care of the details, no software memory barriers needed.
    - saagarjha 5y ago
      TSO is a per-thread flag; it’s implemented as a write to a MSR on context switch to switch it on or off.
      - gpderetta 5y ago
        Right, is it POWER that has a per page TSO flag?
        saagarjha 5y ago
secondcoming 5y ago
There is a proposal (possibly accepted) to deprecate 'volatile' in C++. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1152r0.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p115...
- tialaramex 5y ago
  Yes P1152 was taken for C++ 20. The purpose of abolishing volatile isn't so much to reinforce that it's not intended for this sort of threading nonsense (indeed on Windows the MSVC guarantees mean it almost is intended for this sort of nonsense) but to make it explicit that "volatile variables" were never really a thing anyway by abolishing the volatile qualifier on variables. The thing your hardware can actually do is almost exactly: https://doc.rust-lang.org/core/ptr/fn.read_volatile.html https://doc.rust-lang.org/core/ptr/fn.read_volatile.html and https://doc.rust-lang.org/core/ptr/fn.write_volatile.html https://doc.rust-lang.org/core/ptr/fn.write_volatile.html And sure enough that's equivalent to what is proposed for C++ although not in just this one paper. With "volatile variables" you can use compound assignment operators on the variable. What does that even mean? Nothing. It means nothing, it's gibberish, but you can do it and people do. They presumably thought it meant something and since it doesn't they were wrong. So, deprecate this and maybe they'll go read up on the subject. You can also in C++ declare things that clearly aren't in the least bit volatile, as volatile anyway. C++ has volatile member variables, volatile member functions, volatile parameters... Any code that seems to rely on this probably doesn't do what the people who wrote it thought it does, run away.
  - mhh__ 5y ago
    volatile primitives is how D does volatile as well. I do sort of miss having a basic volatile (although I can write my own type somewhat effectively) just for benchmarking's sake sometimes.
  - agent327 5y ago
    >With "volatile variables" you can use compound assignment operators on the variable. What does that even mean? Nothing. It means exactly the same thing as on a normal variable, and it boggles the mind that people somehow not understand that. Given 'volatile int i', 'i++' means the exact same thing as 'i = i + 1'. Does that also not make any sense to you? If it does, can you explain why you believe they are different? Volatile member functions and parameters make no sense, but volatile member variables most certainly do. And there is considerable pushback in the C++ community because this is a significant loss of compatibility with various C-headers used frequently in embedded applications. I wouldn't be surprised if the deprecated features will be reinstated in the language in the end.
vitus 5y ago
I spent some time trying to figure out why the lock-free read/write implementation is correct under x86, assuming a multiprocessor environment. My read of the situation was that there's already potential for a double-read / double-write between when the spinlock returns and when the head/tail index is updated. Turns out that I was missing something: there's only one producer thread, and only one consumer thread. If there were multiple of either, then this code would be more fundamentally broken. That said: IMO the use of `new` in modern C++ (as is the case in the writer queue) is often a code smell, especially when std::make_unique would work just as well. Using a unique_ptr would obviate the first concern [0] about the copy constructor not being deleted. (If we used unique_ptr consistently here, we might fix the scary platform-dependent leak in exchange for a likely segfault following a nullptr dereference.) One other comment: the explanation in [1] is slightly incorrect: > we receive back Result* pointers from the results queue rq, then wrap them in a std::unique_ptr and jam them into a vector. We actually receive unique_ptrs from the results queue, then because, um, reasons (probably that we forgot that we made this a unique_ptr), we're wrapping them in another unique_ptr, which works because we're passing a temporary (well, prvalue in C++17) to unique_ptr's constructor -- while that looks like it might invoke the deleted copy-constructor, it's actually an instance of guaranteed copy elision. Also a bit weird to see, but not an issue of correctness. [0] https://github.com/stong/how-to-exploit-a-double-free#0-internal-data-structures https://github.com/stong/how-to-exploit-a-double-free#0-inte... [1] https://github.com/stong/how-to-exploit-a-double-free#2-receive-results https://github.com/stong/how-to-exploit-a-double-free#2-rece...
- stong1 5y ago
  Great points. I made some minor edits to address that and clarify some things. Thanks!
- PaulDavisThe1st 5y ago
  > Turns out that I was missing something: Indeed. It's not safe under x86 either.
- aydwi 5y ago
  > IMO the use of `new` in modern C++ (as is the case in the writer queue) is often a code smell As a naive practitioner of modern C++, I'd love it if you could elaborate on this.
0xfaded 5y ago
My first gen threadripper occasionally deadlocks in futex code within libgomp (gnu implementation of omp). Eventually I gave up and concluded it was either a hardware bug or a bug that incorrectly relies on atomic behaviour of intel CPUs. I eventually switched to using clang with its own omp implementation and the problem magically disappeared.
pcwalton 5y ago
Lock-free programming is really tough. There are really only a few patterns that work (e.g. Treiber stack). Trying to invent a new lock-free algorithm, as this vulnerable code demonstrates, almost always ends in tears.
- nyanpasu64 5y ago
  IMO lock-free MP or MC algorithms are harder to get right than SPSC structures (atomics for shared memory, queues for messaging, triple buffers for tear-free shared memory). But even SPSC algorithms can be tricky; I've found the same (theoretical) ordering error in three separate Rust implementations of triple buffering (one of them mine), written by people who've already learned the ordering rules (which I caught with Loom). And initially learning to reason about memory ordering is a major upfront challenge too.
  - reitzensteinm 5y ago
    I'd be interested in knowing the details of the error!
    - nyanpasu64 5y ago
      https://github.com/HadrienG2/triple-buffer/issues/14 https://github.com/HadrienG2/triple-buffer/issues/14
  - ohazi 5y ago
    I particularly like lock-free (wait-free?) SPSC queues because they're (relatively) easy to get right, and are extremely useful for buffering in embedded systems. I end up with something like this on almost every project: One side of the queue is a peripheral like a serial port that needs to be fed/drained like clockwork to avoid losing data or glitching (e.g. via interrupts or DMA), and the other side is usually software running on the main thread, that wants to be able to work at its own pace and also go to sleep sometimes. An SPSC queue fits this use-case nicely. James Munns has a fancy one written in Rust [1], and I have a ~100 line C template [2]. [1] https://github.com/jamesmunns/bbqueue https://github.com/jamesmunns/bbqueue [2] https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d7017 https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d70...
anyfoo 5y ago
Heh, 10 years ago I gave a presentation about how easy folks used to x86 can trip up when dealing with ARM's weaker memory model. My demonstration then was with a naive implementation of Peterson's algorithm.[1] I have a feeling that we will see a sharp rise of stories like this, now that ARM finds itself in more places which were previously mostly occupied by x86, and all the subtle race conditions that x86's memory model forgave actually start failing, in equally subtle ways. [1] The conclusion for this particular audience was: Don't try to avoid synchronization primitives, or even invent your own. They were not system level nor high perf code programmers, so they had that luxury.
- gpderetta 5y ago
  But Peterson's algorithm requires explicit memory barriers even on x86, it doesn't seem the best example to show the difference.
  - anyfoo 5y ago
    Here are my slides from back then: https://reinference.net/mp-talk.pdf https://reinference.net/mp-talk.pdf You made me wonder, because I definitely remember using Peterson's Algorithm, so I went back to my slides and turns out: I first showed the problem with x86, then indeed added an MFENCE at the right place, and then showed how that was not enough for ARM. So the point back then was to show how weaker memory models can bite you with the example of x86, and then to show how it can still bite you on ARM with its even weaker model (ARMv7 at that time, and C11 atomics aren't mentioned yet either, but their old OS-specific support is).
    - destring 5y ago
      Damn, my knowledge of ARM and x86 memory models was limited to "x86 provides a stronger model" but that was it. So much to learn, thanks for the slides.
    - gpderetta 5y ago
      Oh, right, yes, ARM additionally needs a release barrier on the unlock path.
silisili 5y ago
> Nowadays, high-performance processors, like those found in desktops, servers, and phones, are massively out-of-order to exploit instruction-level parallelism as much as possible. They perform all sorts of tricks to improve performance. Relevant quote from Jim Keller: You run this program a hundred times, it never runs the same way twice. Ever.
- krylon 5y ago
  Heraclitus, mumbling into his beard: "Told you so!" SCNR
- vlovich123 5y ago
  A hundred times is not that much except for really cold code paths. It’s probably in the billions if not more and I have to imagine that software level effects typically swamp HW-level effects here. That’s why you see software typically having a performance deviation no greater than ~5-10% unless you’re running microbenchmarks.
drcongo 5y ago
Nice try Intel.
gpderetta 5y ago
The best part is that the original code is not safe even on x86 as the compiler can still reorder non-volatile accesses to the backing_buf around the volatile accesses to head and tails. Compiler barriers before the volatile stores and after volatile reads are required [1]. It would still be very questionable code, but it would at least have a chance to work on its intended target. tl;dr: just use std::atomic. [1] it is of course possible they are actually present in the original code and just omitted from the explanation for brevity
reitzensteinm 5y ago
For those interested in memory ordering, I have a few posts on my blog where I build a simulator capable of understanding reorderings and analyze examples with it: https://www.reitzen.com/post/temporal-fuzzing-01/ https://www.reitzen.com/post/temporal-fuzzing-01/ https://www.reitzen.com/post/temporal-fuzzing-02/ https://www.reitzen.com/post/temporal-fuzzing-02/ Next step are some lock free queues, although I haven't gotten around to publishing them!
sydthrowaway 5y ago
Any good references on low level details on ARMv8+?
PaulDavisThe1st 5y ago
Either I'm not understanding something that I thought I understood very well, or TFA's author's don't understand something that they think they understand very well. Their code is unsafe even on x86. You cannot write a single-writer, single-reader FIFO on modern processors without the use of memory barriers. Their attempt to use "volatile" instead of memory barriers is not appropriate. It could easily cause problems on x86 platforms in just the same way that it could on ARM. "volatile" does not mean what you think it means; if you're using it for anything other than interacting with hardware registers in a device driver, you're almost certainly using it incorrectly. You must use the correct memory barriers to protect the read/write of what they call "head" and "tail". Without them, the code is just wrong, no matter what the platform.
- deleted 5y ago
  [deleted]
- kloch 5y ago
  > "volatile" does not mean what you think it means; if you're using it for anything other than interacting with hardware registers in a device driver, you're almost certainly using it incorrectly. Another "correct" use of volatile is a hack to prevent compilers from optimizing away certain code. It's pretty rare to need that and often you can just use a lower optimization level (like the usual -O2) but sometimes you need -O3 / -Ofast or something and a strategic volatile type def to keep everything working. A classic example is Kahan summation algorithim. At -O2 it's fine. At -O3 or higher it silently defeats the algorithm while appearing to work (you get a sum but without the error compensation). Defining the working vars as volatile makes it work again. This is noted in the wikipedia pseudocode with the comment "// Algebraically, c should always be zero. Beware overly-aggressive optimizing compilers!" https://en.wikipedia.org/wiki/Kahan_summation_algorithm https://en.wikipedia.org/wiki/Kahan_summation_algorithm Of course -O3 might not be any faster anyway but that's another topic.
  - vlovich123 5y ago
    I can’t imagine it’s an O2 vs O3 thing unless a compiler enables “fast-math” optimization to allow associativity. Neither clang nor GCC do this (neither does MSVC I think) - optimization levels never silently turn off IEEE754 floating point. I don’t know about ICC but it sounds like they stupidly enable fast math by default to try to win at benchmarks. Do you have anything to actually support this statement or did you just assume “overly aggressive optimizing compilers” and “O3” are somehow linked? Generally optimization levels may find more opportunities to exploit UB, but they do not change the semantics of the language, and all languages I’m familiar with define floating point as a non-associative operation because it’s not when you’re working with finite precision. TLDR: Don’t use volatile unless you really know what you’re doing, and unless you know C/C++ really well, you probably do not. If anyone tells you to throw in a volatile to “make things work”, it’s most likely cargo curling bad advice (not always, but probably).

291 points by stong1 5y ago

Is it normal for the .got.plt section to be writable rather than read-only?

And arm-windows will (does already?) run x86 binaries with weaker memory ordering than they were written for. So this could be a real thing soon.

kevingadd 5y ago
Are you sure the translators don't insert code necessary to maintain ordering? I would be shocked if most threaded code works when you throw out the x86 memory model. Managed runtimes like .NET definitely generate code for each target designed to maintain the correct memory model.
- pmuderoc 5y ago
  They better do, but then, how would an automatic translator know that this is a "release semantics" atomic store operation? Because on x86 it is, no special barriers or instructions necessary. mov [shared_data], 1 mov [release_flag], 1
  - my123 5y ago
    It’s pessimistic and converts over a lot of memory accesses to RCpc or atomics. (on ARMv8.0 where you don’t have those, barriers are used more) TSO pessimization is the only way to make the thing work at a translation time cost that isn’t too high.
    - gpderetta 5y ago
      Or you support TSO directly on your cpu like Apple does on M1.
      - tsimionescu 5y ago
        Sure, but Windows on ARM has to run on many ARM processors, not a specific one designed by MS. They could detect if the processor has non-standard TSO support and use that when running an x86 app, but they still have to do something to run the x86 app on a standard ARM processor.
- my123 5y ago
  Maintaining the memory model guarantees is what causes the steep cost in performance when using x86 apps on Windows on Arm. That said, heuristics are used to speed it up. I would recommend not sharing values in the stack between threads for synchronisation for example.
- nyanpasu64 5y ago
  https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on-arm-program-compat-troubleshooter https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on... > You can also select multi-core settings, as shown here... These settings change the number of memory barriers used to synchronize memory accesses between cores in apps during emulation. Fast is the default mode, but the strict and very strict options will increase the number of barriers. This slows down the app, but reduces the risk of app errors. The single-core option removes all barriers but forces all app threads to run on a single core. https://news.ycombinator.com/item?id=28732273 https://news.ycombinator.com/item?id=28732273 zamadatix's interprets this as Microsoft saying that by default, Windows on ARM runs x86 apps without x86 TSO, and turns on extra memory barriers using per-app compatibility settings. But if an app needs TSO but isn't in Windows's database, it will crash or silently corrupt data.
xxs 5y ago
Normally the code should have all the needed memory fences as if running on DEC Alpha, e.g. linux does that, and the compilers omit the unneeded ones.
- monocasa 5y ago
  And since the compiler omitted it on x86, an x86 emulator doesn't have access to where they're required as seen by the compiler.
  - xxs 5y ago
    emulator would have a zero issue, if it's a direct transfer for assembly (not an emulator), it'd need either hardware support - e.g. apple chips, or memory barriers. The differences between arm and x86 are known for 15y+, there is nothing new about it. Also concurrency support is one of the major benefits of languages with proper memory model - java started it with JMM[0] [0]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedL...
    - gpderetta 5y ago
      Any emulator that wants to be remotely performance competitive will do dynamic translation (i.e JIT). In fact ahead-of-time translation is not really feasible. Memory models and JVM are not really relevant when discussing running binaries for a different architecture.
      - secondcoming 5y ago
        Doesn't the JVM define its own memory model?
        gpderetta 5y ago
        Sure, but how's that relevant when discussing running x86 binaries on ARM?
belter 5y ago
Now I am worried. Do you have a reference please?
- im3w1l 5y ago
  Best I could find. It's not a great reference because it doesn't give any details but it does prove that it's a thing. https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on-arm-program-compat-troubleshooter https://docs.microsoft.com/en-us/windows/uwp/porting/apps-on...

half-kh-hacker 5y ago

this slaps. I always see perfect blue a few places above us!

nyanpasu64 5y ago
Context for downvoters: "perfect blue" is the CTF group writing this article, and "a few places" means CTF team rankings in competitions.

Azsy 5y ago

Have i told you about our lord and savior Rust? Anyways, https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom is used by any serious library doing atomic ops/synchronization and it blew me away with how fast it can catch most bugs like this.

nyanpasu64 5y ago
Rust doesn't catch memory ordering errors, which can result in behavioral bugs in safe Rust and data races and memory unsafety in unsafe Rust. But Loom is an excellent tool for catching ordering errors, though its UnsafeCell API differs from std's (and worse yet, some people report Loom returns false positives/negatives in some cases: https://github.com/tokio-rs/loom/issues/180 https://github.com/tokio-rs/loom/issues/180, possibly https://github.com/tokio-rs/loom/issues/166 https://github.com/tokio-rs/loom/issues/166).
- Fiahil 5y ago
  I think it's fixable, the main reactor is what matters. You can add or remove as many synchronisation primitive as you like. Other tooling, like Jepsen, will interact with your program at a higher level.
- CodesInChaos 5y ago
  It doesn't catch all of them. But data-races on plain memory access are impossible in safe rust. And atomics force you to specify an ordering on every access, which helps both the writer (forced to think about which ordering they need) and reviewer (by communicating intent).
- tialaramex 5y ago
  > which can result in behavioral bugs in safe Rust For example, Rust doesn't have any way to know that your chosen lock-free algorithm relies on Acquire-release semantics to perform as intended, and so if you write safe Rust to implement it with Relaxed ordering, it will compile, and run, and on x86-64 it will even work just fine because the cheap behaviour on x86-64 has Acquire-release semantics anyway. But on ARM your program doesn't work because ARM really does have a Relaxed mode and without Acquire-release what you've got is not the clever lock-free algorithm you intended after all. However, if you don't even understand what Ordering is, and just try to implement the naive algorithm in Rust without Atomic operations that take an Ordering, Rust won't compile your program at all because it could race. So this way you are at least confronted with the fact that it's time to learn about Ordering if you want to implement this algorithm and if you pick Relaxed you can keep the resulting (safe) mess you made.

agalunar 5y ago

Great write-up! There may be a typo in section 3: > It will happily retire instruction 6 before instruction 5. If memory serves, although instructions can execute out-of-order, they retire in-order (hence the "re-order buffer").

colejohnson66 5y ago
You are correct. The retire unit ensures that all micro ops are retired in order
stong1 5y ago
Nice catch. I fixed it. I should have said "execute" rather than "retire".

beebmam 5y ago

Like quantum physics, memory ordering is deeply unintuitive (on platforms like ARM). Unlike quantum physics, which is an unfortunate immutable fact of the universe, we got ourselves into this mess and we have no one to blame but ourselves for it. I'm only somewhat joking. People need to understand these memory models if they intend on writing atomic operations in their software, even if they aren't currently targeting ARM platforms. In this era, it's absurdly easy to change an an LLVM compiler to target aarch64, and it will happen for plenty of software that was written without ever considering the differences in atomic behavior on this platform.

newpavlov 5y ago
Memory ordering gets somewhat easier after you understand that flat memory shared by execution units is a leaky abstraction desperately patched over decades by layer and layers of hardware and software. Memory ordering is one way to represent message passing and synchronization between different cores and RAM. This why I think that "lock-free algorithms" is a misnomer, you still have synchronization, but you simply rely on hardware for it.
- gpderetta 5y ago
  That's actually a common misconception. Memory ordering, on the majority of common cpus, has nothing to do with interprocessor communication or processor-ram communication. Common memory coherency protocols (I.e. MESI and derivatives) guarantee that all caches have a consistent view of memory. Usually memory reordering is purely artifact of the way CPUs access their private L1-cache.
  - yvdriess 5y ago
    For the record, this is false. It is conflating memory coherency with consistency. Nearly everything in a modern processor is a source of reordering, from branch prediction to basically everything in the OoO backend. Any time you leave the core, there's reordering happening in the network. And yes, that includes caches, which involve a heavy amount of inter-core communication. When you issue two successive loads to different cache lines, which one is going to return first? The OoO backend itself manages hazards and ensures that ld/st instructions are retired in the correct order to maintain the processor's memory consistency model. Software can build on top of that, e.g. with fences, to impose stricter consistency models.

amelius 5y ago

Does the race condition exist when emulating x86 on Apple M1?

saagarjha 5y ago
No. Rosetta emulates TSO correctly.
- addaon 5y ago
  To draw together the two answers here to the original question. 1) Emulating an ISA includes emulating its memory model. As saagarjha says, this means that Rosetta 2 must (and does) correctly implement total store ordering. 2) There are various ways to implement this. For emulators that include a binary translation layer (that is, that translate x86 opcodes into a sequence of ARM opcodes), one route is to generate the appropriate ARM memory barriers as part of the translation. Even with optimization to reduce the number of necessary barriers, though, this is expensive. Instead, as mmwelt mentions, Apple took an unusual route here. The Apple Silicon MMU can be configured on a per-page basis to use either the relaxed ARM memory model or the TSO x86 memory model. There is a performance cost at the hardware level for using TSO, and there is a cost in silicon area for supporting both; but from the point of view of Rosetta 2, all it has to do is mark x86-accessed pages as TSO and the hardware takes care of the details, no software memory barriers needed.
  - saagarjha 5y ago
    TSO is a per-thread flag; it’s implemented as a write to a MSR on context switch to switch it on or off.
    - gpderetta 5y ago
      Right, is it POWER that has a per page TSO flag?
      - saagarjha 5y ago

secondcoming 5y ago

There is a proposal (possibly accepted) to deprecate 'volatile' in C++. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1152r0.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p115...

tialaramex 5y ago
Yes P1152 was taken for C++ 20. The purpose of abolishing volatile isn't so much to reinforce that it's not intended for this sort of threading nonsense (indeed on Windows the MSVC guarantees mean it almost is intended for this sort of nonsense) but to make it explicit that "volatile variables" were never really a thing anyway by abolishing the volatile qualifier on variables. The thing your hardware can actually do is almost exactly: https://doc.rust-lang.org/core/ptr/fn.read_volatile.html https://doc.rust-lang.org/core/ptr/fn.read_volatile.html and https://doc.rust-lang.org/core/ptr/fn.write_volatile.html https://doc.rust-lang.org/core/ptr/fn.write_volatile.html And sure enough that's equivalent to what is proposed for C++ although not in just this one paper. With "volatile variables" you can use compound assignment operators on the variable. What does that even mean? Nothing. It means nothing, it's gibberish, but you can do it and people do. They presumably thought it meant something and since it doesn't they were wrong. So, deprecate this and maybe they'll go read up on the subject. You can also in C++ declare things that clearly aren't in the least bit volatile, as volatile anyway. C++ has volatile member variables, volatile member functions, volatile parameters... Any code that seems to rely on this probably doesn't do what the people who wrote it thought it does, run away.
- mhh__ 5y ago
  volatile primitives is how D does volatile as well. I do sort of miss having a basic volatile (although I can write my own type somewhat effectively) just for benchmarking's sake sometimes.
- agent327 5y ago
  >With "volatile variables" you can use compound assignment operators on the variable. What does that even mean? Nothing. It means exactly the same thing as on a normal variable, and it boggles the mind that people somehow not understand that. Given 'volatile int i', 'i++' means the exact same thing as 'i = i + 1'. Does that also not make any sense to you? If it does, can you explain why you believe they are different? Volatile member functions and parameters make no sense, but volatile member variables most certainly do. And there is considerable pushback in the C++ community because this is a significant loss of compatibility with various C-headers used frequently in embedded applications. I wouldn't be surprised if the deprecated features will be reinstated in the language in the end.

vitus 5y ago

I spent some time trying to figure out why the lock-free read/write implementation is correct under x86, assuming a multiprocessor environment. My read of the situation was that there's already potential for a double-read / double-write between when the spinlock returns and when the head/tail index is updated. Turns out that I was missing something: there's only one producer thread, and only one consumer thread. If there were multiple of either, then this code would be more fundamentally broken. That said: IMO the use of `new` in modern C++ (as is the case in the writer queue) is often a code smell, especially when std::make_unique would work just as well. Using a unique_ptr would obviate the first concern [0] about the copy constructor not being deleted. (If we used unique_ptr consistently here, we might fix the scary platform-dependent leak in exchange for a likely segfault following a nullptr dereference.) One other comment: the explanation in [1] is slightly incorrect: > we receive back Result* pointers from the results queue rq, then wrap them in a std::unique_ptr and jam them into a vector. We actually receive unique_ptrs from the results queue, then because, um, reasons (probably that we forgot that we made this a unique_ptr), we're wrapping them in another unique_ptr, which works because we're passing a temporary (well, prvalue in C++17) to unique_ptr's constructor -- while that looks like it might invoke the deleted copy-constructor, it's actually an instance of guaranteed copy elision. Also a bit weird to see, but not an issue of correctness. [0] https://github.com/stong/how-to-exploit-a-double-free#0-internal-data-structures https://github.com/stong/how-to-exploit-a-double-free#0-inte... [1] https://github.com/stong/how-to-exploit-a-double-free#2-receive-results https://github.com/stong/how-to-exploit-a-double-free#2-rece...

stong1 5y ago
Great points. I made some minor edits to address that and clarify some things. Thanks!
PaulDavisThe1st 5y ago
> Turns out that I was missing something: Indeed. It's not safe under x86 either.
aydwi 5y ago
> IMO the use of `new` in modern C++ (as is the case in the writer queue) is often a code smell As a naive practitioner of modern C++, I'd love it if you could elaborate on this.

0xfaded 5y ago

My first gen threadripper occasionally deadlocks in futex code within libgomp (gnu implementation of omp). Eventually I gave up and concluded it was either a hardware bug or a bug that incorrectly relies on atomic behaviour of intel CPUs. I eventually switched to using clang with its own omp implementation and the problem magically disappeared.

pcwalton 5y ago

Lock-free programming is really tough. There are really only a few patterns that work (e.g. Treiber stack). Trying to invent a new lock-free algorithm, as this vulnerable code demonstrates, almost always ends in tears.

nyanpasu64 5y ago
IMO lock-free MP or MC algorithms are harder to get right than SPSC structures (atomics for shared memory, queues for messaging, triple buffers for tear-free shared memory). But even SPSC algorithms can be tricky; I've found the same (theoretical) ordering error in three separate Rust implementations of triple buffering (one of them mine), written by people who've already learned the ordering rules (which I caught with Loom). And initially learning to reason about memory ordering is a major upfront challenge too.
- reitzensteinm 5y ago
  I'd be interested in knowing the details of the error!
  - nyanpasu64 5y ago
    https://github.com/HadrienG2/triple-buffer/issues/14 https://github.com/HadrienG2/triple-buffer/issues/14
- ohazi 5y ago
  I particularly like lock-free (wait-free?) SPSC queues because they're (relatively) easy to get right, and are extremely useful for buffering in embedded systems. I end up with something like this on almost every project: One side of the queue is a peripheral like a serial port that needs to be fed/drained like clockwork to avoid losing data or glitching (e.g. via interrupts or DMA), and the other side is usually software running on the main thread, that wants to be able to work at its own pace and also go to sleep sometimes. An SPSC queue fits this use-case nicely. James Munns has a fancy one written in Rust [1], and I have a ~100 line C template [2]. [1] https://github.com/jamesmunns/bbqueue https://github.com/jamesmunns/bbqueue [2] https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d7017 https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d70...

anyfoo 5y ago

Heh, 10 years ago I gave a presentation about how easy folks used to x86 can trip up when dealing with ARM's weaker memory model. My demonstration then was with a naive implementation of Peterson's algorithm.[1] I have a feeling that we will see a sharp rise of stories like this, now that ARM finds itself in more places which were previously mostly occupied by x86, and all the subtle race conditions that x86's memory model forgave actually start failing, in equally subtle ways. [1] The conclusion for this particular audience was: Don't try to avoid synchronization primitives, or even invent your own. They were not system level nor high perf code programmers, so they had that luxury.

gpderetta 5y ago
But Peterson's algorithm requires explicit memory barriers even on x86, it doesn't seem the best example to show the difference.
- anyfoo 5y ago
  Here are my slides from back then: https://reinference.net/mp-talk.pdf https://reinference.net/mp-talk.pdf You made me wonder, because I definitely remember using Peterson's Algorithm, so I went back to my slides and turns out: I first showed the problem with x86, then indeed added an MFENCE at the right place, and then showed how that was not enough for ARM. So the point back then was to show how weaker memory models can bite you with the example of x86, and then to show how it can still bite you on ARM with its even weaker model (ARMv7 at that time, and C11 atomics aren't mentioned yet either, but their old OS-specific support is).
  - destring 5y ago
    Damn, my knowledge of ARM and x86 memory models was limited to "x86 provides a stronger model" but that was it. So much to learn, thanks for the slides.
  - gpderetta 5y ago
    Oh, right, yes, ARM additionally needs a release barrier on the unlock path.

silisili 5y ago

> Nowadays, high-performance processors, like those found in desktops, servers, and phones, are massively out-of-order to exploit instruction-level parallelism as much as possible. They perform all sorts of tricks to improve performance. Relevant quote from Jim Keller: You run this program a hundred times, it never runs the same way twice. Ever.

krylon 5y ago
Heraclitus, mumbling into his beard: "Told you so!" SCNR
vlovich123 5y ago
A hundred times is not that much except for really cold code paths. It’s probably in the billions if not more and I have to imagine that software level effects typically swamp HW-level effects here. That’s why you see software typically having a performance deviation no greater than ~5-10% unless you’re running microbenchmarks.

drcongo 5y ago

Nice try Intel.

gpderetta 5y ago

The best part is that the original code is not safe even on x86 as the compiler can still reorder non-volatile accesses to the backing_buf around the volatile accesses to head and tails. Compiler barriers before the volatile stores and after volatile reads are required [1]. It would still be very questionable code, but it would at least have a chance to work on its intended target. tl;dr: just use std::atomic. [1] it is of course possible they are actually present in the original code and just omitted from the explanation for brevity

reitzensteinm 5y ago

For those interested in memory ordering, I have a few posts on my blog where I build a simulator capable of understanding reorderings and analyze examples with it: https://www.reitzen.com/post/temporal-fuzzing-01/ https://www.reitzen.com/post/temporal-fuzzing-01/ https://www.reitzen.com/post/temporal-fuzzing-02/ https://www.reitzen.com/post/temporal-fuzzing-02/ Next step are some lock free queues, although I haven't gotten around to publishing them!

sydthrowaway 5y ago

Any good references on low level details on ARMv8+?

PaulDavisThe1st 5y ago

Either I'm not understanding something that I thought I understood very well, or TFA's author's don't understand something that they think they understand very well. Their code is unsafe even on x86. You cannot write a single-writer, single-reader FIFO on modern processors without the use of memory barriers. Their attempt to use "volatile" instead of memory barriers is not appropriate. It could easily cause problems on x86 platforms in just the same way that it could on ARM. "volatile" does not mean what you think it means; if you're using it for anything other than interacting with hardware registers in a device driver, you're almost certainly using it incorrectly. You must use the correct memory barriers to protect the read/write of what they call "head" and "tail". Without them, the code is just wrong, no matter what the platform.

deleted 5y ago
[deleted]
kloch 5y ago
> "volatile" does not mean what you think it means; if you're using it for anything other than interacting with hardware registers in a device driver, you're almost certainly using it incorrectly. Another "correct" use of volatile is a hack to prevent compilers from optimizing away certain code. It's pretty rare to need that and often you can just use a lower optimization level (like the usual -O2) but sometimes you need -O3 / -Ofast or something and a strategic volatile type def to keep everything working. A classic example is Kahan summation algorithim. At -O2 it's fine. At -O3 or higher it silently defeats the algorithm while appearing to work (you get a sum but without the error compensation). Defining the working vars as volatile makes it work again. This is noted in the wikipedia pseudocode with the comment "// Algebraically, c should always be zero. Beware overly-aggressive optimizing compilers!" https://en.wikipedia.org/wiki/Kahan_summation_algorithm https://en.wikipedia.org/wiki/Kahan_summation_algorithm Of course -O3 might not be any faster anyway but that's another topic.
- vlovich123 5y ago
  I can’t imagine it’s an O2 vs O3 thing unless a compiler enables “fast-math” optimization to allow associativity. Neither clang nor GCC do this (neither does MSVC I think) - optimization levels never silently turn off IEEE754 floating point. I don’t know about ICC but it sounds like they stupidly enable fast math by default to try to win at benchmarks. Do you have anything to actually support this statement or did you just assume “overly aggressive optimizing compilers” and “O3” are somehow linked? Generally optimization levels may find more opportunities to exploit UB, but they do not change the semantics of the language, and all languages I’m familiar with define floating point as a non-associative operation because it’s not when you’re working with finite precision. TLDR: Don’t use volatile unless you really know what you’re doing, and unless you know C/C++ really well, you probably do not. If anyone tells you to throw in a volatile to “make things work”, it’s most likely cargo curling bad advice (not always, but probably).