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

A one in a million bug in Switch kernel

gist.githubusercontent.com

Post reply on HN
Print view View original

21–30 of 95 posts

Re: A one in a million bug in Switch kernel

#21

Post by AceJohnny2 »

broodbucket wrote: post #7

>Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it! Context switches, idle state transitions, etc tend to be fairly delicately handled as a common cause of CVEs and Heisenbugs. I'm sure there's still plenty of bugs but more attention ends up being paid to these things on general purpose operating systems. More eyeballs on the code, more security researchers, more hardware variants…

Cache coherency on SoCs is one of the more hairy aspects, and one that's getting an increasing amount of attention from the software world.

Certainly for Mac it's a well-known topic, though I won't necessarily say it's all safe. Like I said: it's hairy.

(fun fact: when you have 10s-100s of millions of units out there, those "1 in a million" chances become all too frequent...)

Re: A one in a million bug in Switch kernel

#22

Post by tedunangst »

ajross wrote: post #11
broodbucket wrote: post #7

>Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it! Context switches, idle state transitions, etc tend to be fairly delicately handled as a common cause of CVEs and Heisenbugs. I'm sure there's still plenty of bugs but more attention ends up being paid to these things on general purpose operating systems. More eyeballs on the code, more security researchers, more hardware variants…

FWIW: I re-read this a bunch of times, and I don't understand how this isn't a hardware bug. How can an asynchronous interrupt be specified in any rigorous way if it does NOT act as a memory barrier to the interrupted code? Clearly the CPU isn't going to cache its in-flight state for every interrupt (and remember interrupts can be themselves interrupted!). So certainly "most" of its state is being serialized. And we'…

It makes sense to me you might need a memory flush when doing a core migration. Everything is still coherent from a single core perspective. But if you point a different core at the same PC, well, maybe it sees things differently that haven't been flushed.

Re: A one in a million bug in Switch kernel

#23

Post by saagarjha »

chc4 wrote: post #20
broodbucket wrote: post #7

>Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it! Context switches, idle state transitions, etc tend to be fairly delicately handled as a common cause of CVEs and Heisenbugs. I'm sure there's still plenty of bugs but more attention ends up being paid to these things on general purpose operating systems. More eyeballs on the code, more security researchers, more hardware variants…

For the record: Returning from an interrupt is fully serializing on x86, which I believe means that all modern operating systems on x86 will handle this properly. https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-r... is a very good blog post about exploiting this for a high-performance membarrier daemon.

Right, but it's possible that this is just a side effect of x86 doing TSO, so any stores are visible just by executing the instruction, so I'm not convinced (at least by that snippet) that interrupts have to be fully serializing. If they're not, I wonder if it's possible to observe load-store reordering across a privilege boundary…

Re: A one in a million bug in Switch kernel

#24

Post by chc4 »

saagarjha wrote: post #23
chc4 wrote: post #20

Earlier quoted context omitted.

For the record: Returning from an interrupt is fully serializing on x86, which I believe means that all modern operating systems on x86 will handle this properly. https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-r... is a very good blog post about exploiting this for a high-performance membarrier daemon.

Right, but it's possible that this is just a side effect of x86 doing TSO, so any stores are visible just by executing the instruction, so I'm not convinced (at least by that snippet) that interrupts have to be fully serializing. If they're not, I wonder if it's possible to observe load-store reordering across a privilege boundary…

I'm not sure what you mean; it is documented in the Intel instruction set reference that IRET is a serializing instruction. It is not only the case that it happens to appear that way due to stores by chance always being retired before the interrupt returns.

It also references Section 8.3 of the Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A, which also says IRET is a serializing instruction.

Re: A one in a million bug in Switch kernel

#25

Post by retSava »

veltas wrote: post #19

> And how do you even find / debug a bug like this? As someone who has worked on cache code, I suspect it's quite possible they were just reviewing this code again and realised the potential hole. Or they were trying to track down some horrific bug and fixed this along the way (whether or not it caused it), reviewing anything to do with caching is probably worth doing because it's notoriously difficult to get right,…

Even low-probability bugs will surface often enough if you give it enough potential times to do so. There are >100 Mn Switch'es out there, and the interrupts happens at least tens to hundreds of times a second when in use, so plenty of opportunities :)

Re: A one in a million bug in Switch kernel

#26

Post by saagarjha »

chc4 wrote: post #24
saagarjha wrote: post #23

Earlier quoted context omitted.

Right, but it's possible that this is just a side effect of x86 doing TSO, so any stores are visible just by executing the instruction, so I'm not convinced (at least by that snippet) that interrupts have to be fully serializing. If they're not, I wonder if it's possible to observe load-store reordering across a privilege boundary…

I'm not sure what you mean; it is documented in the Intel instruction set reference that IRET is a serializing instruction. It is not only the case that it happens to appear that way due to stores by chance always being retired before the interrupt returns. It also references Section 8.3 of the Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A, which also says IRET is a serializing instruction.

Sorry, I forgot to quote the part that I wanted to pick on:

> Interrupt processing (returning from an interrupt handler, actually) is fully serialising on x86, and on other platforms, no doubt: any userspace instruction either fully executes before the interrupt, or is (re-)executed from scratch some time after the return back to userspace.

Approaching this from the perspective of not knowing that iret is serializing, this quote doesn't really provide a good reason for why it should be serializing. You've mentioned the manual, which is probably what should've been quoted, because the thing I extracted out goes on to say that it must be true on other platforms too when it evidently is not. The rest of my comment was a hypothetical on how you might observe if iret was non-serializing, which (given what the manual says) must be unobservable.

Re: A one in a million bug in Switch kernel

#27

Post by veltas »

retSava wrote: post #25
veltas wrote: post #19

> And how do you even find / debug a bug like this? As someone who has worked on cache code, I suspect it's quite possible they were just reviewing this code again and realised the potential hole. Or they were trying to track down some horrific bug and fixed this along the way (whether or not it caused it), reviewing anything to do with caching is probably worth doing because it's notoriously difficult to get right,…

Even low-probability bugs will surface often enough if you give it enough potential times to do so. There are >100 Mn Switch'es out there, and the interrupts happens at least tens to hundreds of times a second when in use, so plenty of opportunities :)

Yep but can they reproduce it? When we say "low probability" we're acting like it's truly random, but in reality they could have stumbled across steps that reproduce it very frequently.

Re: A one in a million bug in Switch kernel

#28

Post by throwawaylinux »

chc4 wrote: post #20
broodbucket wrote: post #7

>Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it! Context switches, idle state transitions, etc tend to be fairly delicately handled as a common cause of CVEs and Heisenbugs. I'm sure there's still plenty of bugs but more attention ends up being paid to these things on general purpose operating systems. More eyeballs on the code, more security researchers, more hardware variants…

For the record: Returning from an interrupt is fully serializing on x86, which I believe means that all modern operating systems on x86 will handle this properly. https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-r... is a very good blog post about exploiting this for a high-performance membarrier daemon.

But a thread can be context switched via a system call, so switching back to it will return to it via a return from system call which is not necessarily serializing on x86. Also memory operations and barriers executed in kernel mode have to be ordered correctly within a thread and context switches there can happen cooperatively so there may be no interrupt at all.

Also a serializing operation is not a memory barrier. It serializes execution of operations in the pipeline, not necessarily coherency operations after completion.

x86 is mostly TSO except possibly some cases of nontemporal stores and write combining memory types. I don't know the minutiae of the ISA and implementations any more but IIRC it could be possible that stores in a a write combining buffer can be visible out of order.

Re: A one in a million bug in Switch kernel

#30

Post by throwawaylinux »

> Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it!

Rubbish. These kernels (well Linux and Windows) run on systems with hundreds even thousands of cores, on CPUs which are very weakly ordered, with a pretty reasonable level of reliability. A race like this will blow up immediately.

Linux handles this by requiring that a context switch operation includes a full memory barrier so switching off CPU0 has a barrier ordering prior stores on CPU0 with storing a field that implies the task can be migrated (it's not currently running), and switching on to CPU1 has a barrier ordering the load of that flag with subsequent loads from the task on CPU1.

EDIT: here - https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

  * The basic program-order guarantee on SMP systems is that when a task [t]
  * migrates, all its activity on its old CPU [c0] happens-before any subsequent
  * execution on its new CPU [c1].
It's informally worded but "activity" basically means memory operations (but could include whacky arch and platform specific things to cover all bases), and "happens before" meaning observable from other CPUs, which is clear in context.
Post reply on HN