Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

21–30 of 141 posts

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

#21

Post by beebmam »

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.

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

#22

Post by silisili »

> 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.

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

#23

Post by newpavlov »

beebmam wrote: post #21

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 targetin…

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.

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

#24

Post by gpderetta »

my123 wrote: post #12
pmuderoc wrote: post #10

Earlier quoted context omitted.

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

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.

Or you support TSO directly on your cpu like Apple does on M1.

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

#25

Post by platinumrad »

pcwalton wrote: post #2

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.

There's no new invention in here. Just an (intentional) misuse of "volatile".

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

#27

Post by reitzensteinm »

nyanpasu64 wrote: post #15
pcwalton wrote: post #2

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.

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 wi…

I'd be interested in knowing the details of the error!

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

#28

Post by nyanpasu64 »

reitzensteinm wrote: post #27
nyanpasu64 wrote: post #15

Earlier quoted context omitted.

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 wi…

I'd be interested in knowing the details of the error!

https://github.com/HadrienG2/triple-buffer/issues/14

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

#29

Post by ohazi »

nyanpasu64 wrote: post #15
pcwalton wrote: post #2

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.

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 wi…

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

[2] https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d70...

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

#30

Post by gpderetta »

newpavlov wrote: post #23
beebmam wrote: post #21

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 targetin…

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 r…

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.

Post reply on HN