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

61–70 of 141 posts

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

#61

Post by stjohnswarts »

anyfoo wrote: post #6

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…

I doubt that. The number of ARM processors is far greater in reality than in x86 if we clarify it by saying “in operation” rather than historically and these stories will become more common but certainly won't see a “sharp increase”.

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

#62

Post by yvdriess »

gpderetta wrote: post #30
newpavlov wrote: post #23

Earlier quoted context omitted.

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.

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.

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

#63

Post by pclmulqdq »

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…

One piece of friction that hurts here is that the C++/Rust and ARM memory models aren't the same, and the consequences of this are unintuitive - compilers and CPUs can both screw with execution ordering.

People who write in C++ should technically _only_ be concerned with the C++ memory model, but x86 has let them be very lax and undisciplined with std::memory_order_relaxed. ARM has some alluring constructs that don't quite fit with the C++ model, which can tempt you to mix and match memory models for performance. All of this means trouble with atomics.

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

#64

Post by mhh__ »

tialaramex wrote: post #54
secondcoming wrote: post #45

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

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…

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.

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

#65

Post by codeflo »

stjohnswarts wrote: post #61
anyfoo wrote: post #6

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…

I doubt that. The number of ARM processors is far greater in reality than in x86 if we clarify it by saying “in operation” rather than historically and these stories will become more common but certainly won't see a “sharp increase”.

This sort of bug only happens when running a multithreaded program (with shared memory) on a multicore processor.

You do need both for the problem to happen: Without shared memory, there’s nothing to exploit. And with a single core only, you get time-sliced multithreading, which orders all operations.

My point is, that combination was a lot rarer in ARM land before people started doing serious server or desktop computing with those chips.

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

#66

Post by gpderetta »

yvdriess wrote: post #62
gpderetta wrote: post #30

Earlier quoted context omitted.

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.

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

Sorry, what is false? You seem to be agreeing with me?

edit: to clarify, I claim that the coherency layer (i.e the L1 cache and beyond), does not introduce any reordering issues, at least for common cpus using variants of MESI.

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

#67

Post by codeflo »

cesarb wrote: post #57
mwcampbell wrote: post #53

Earlier quoted context omitted.

> Don't try to avoid synchronization primitives, or even invent your own. Makes me wonder if it's really a good idea in most cases to use, for example, the Rust parking_lot crate, which reimplements mutexes and RW locks. Besides the speed boost for uncontended RW locks, particularly on x64 Linux, what I really like about parking_lot is that a write lock can be downgraded to a read lock without letting go of the lock.…

Unless you're the maintainer of the parking_lot crate, you're not "inventing your own". And since parking_lot is AFAIK the second most popular implementation of mutexes and RW locks in Rust (the most popular one being obviously the one in the Rust standard library, which wraps the OS-provided lock implementations), you can assume it's well tested.

Everything about which people tell you to “not invent your own” must be invented by someone.

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

#68

Post by PaulDavisThe1st »

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.

This isn't a new lock-free algorithm. Single-reader, single-write FIFOs are one of the oldest approaches around.

They have to be tweaked when execution isn't guaranteed (by using memory barriers). TFA is about an exploit based on code that hasn't added the required memory barriers.

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

#70

Post by PaulDavisThe1st »

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.

Post reply on HN