10 ms·

A one in a million bug in Switch kernel

682 points by vedanshbhartia 5y ago

throwaway5371 5y ago
offtopic: I really wish reading preformatted text files on ios safari was good.. I have to export the file to Books in order to read it properly
- broodbucket 5y ago
  Firefox reader mode is nice for taking various webpages, whether it's a news article with bloated JS, a wiki page, simple plaintext etc and giving it a common presentation that you can configure to your liking. No clue if that's a solution for you on iOS but it's a great feature.
  - zinekeller 5y ago
    > No clue if that's a solution for you on iOS but it's a great feature. Unfortunately, iOS browsers tends to be just reskins of Safari (because it's required by Apple).
    - astrange 5y ago
      Reader mode would work in such a reskin I think, but Safari has its own reader mode anyway. The original Readability was a bookmarklet that worked in any browser.
- deleted 5y ago
  [deleted]
- terhechte 5y ago
  I just tried it out on iOS in Safari's reader mode, and it looks quite good. What don't you like about the output?
  - jez 5y ago
    The file has diagrams that are meant to be viewed on a screen with enough space to leave long lines unbroken. If you attempt to get things to fit onto a single line by turning the phone sideways, it just zooms the text, instead of reflowing the text onto a larger line width. The problem exists in both the default rendering and the reader view. Opening in iBooks essentially prints the text file to a PDF, which defaults to US Letter paper size, which has the effect of making line widths large enough for most 80-character text files to fit without awkward mid-line soft breaks. The only other solution I know of is to manually zoom the page out to 50%. Luckily the zoom setting is saved by domain, so in this case if you want all raw githubusercontent files to view zoomed out iOS will remember that, but on domains where it’s a mix of text and HTML it’s more annoying.
- eqtn 5y ago
  iOS Firefox - https://i.imgur.com/1f5PElQ.jpeg https://i.imgur.com/1f5PElQ.jpeg iOS Safari Reader mode - https://i.imgur.com/nDnBSAM.jpeg https://i.imgur.com/nDnBSAM.jpeg iOS Safari - https://i.imgur.com/AhtWv9G.jpeg https://i.imgur.com/AhtWv9G.jpeg
- aspenmayer 5y ago
  https://gist.github.com/plutooo/2aadbd4a718e269df474079dd2e584fb/ https://gist.github.com/plutooo/2aadbd4a718e269df474079dd2e5...
- kevincox 5y ago
  I think people need to use text files less. Or at least stop hard-wapping them.
  - hoseja 5y ago
    Hard-wrapping is my bane. Especially in RFCs.
  - Thrymr 5y ago
    Does that mean that a browser shouldn't be able to display a text file with explicit line breaks, though?
  - opan 5y ago
    I love text files and kinda like hard wrapping as well.
zinekeller 5y ago
> This bug has existed since day zero, which means that it took 5 years (!) for Nintendo to track it down. Credits to whoever nameless employee at Nintendo found this bug! The attention to detail is incredible. And how do you even find / debug a bug like this? Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it! Considering the various kernel-level races in mainstream kernels (*BSD, Darwin, Linux and NT), I actually doubt that these kinds of bug are fully eliminated (only fixed in cases where such race has security implications).
broodbucket 5y ago
>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 to expose things that were thought to be fine. Also fuzzing.
- ajross 5y ago
  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're supposed to magically guess on a per-IP basis which state isn't? Yikes. I mean, the fix is the same. But arguing about which OSes "handle this properly" is missing the point. The question to ask is which core IPs (and which configurations thereof, remember the Tegra in question has both A53 and A57 cores) require barriers on interrupt entry, and under what circumstances. If ARM isn't going to publish that errata then asking for OS authors to magically figure it out is just asking for bugs.
  - rustybolt 5y ago
    I might be missing something but don't see your point. If you want every interrupt to act as a memory barrier you can just insert a memory barrier in the interrupt handler. A reason not to do this is the overhead. Also, if you know the interrupt handler will not interact with memory from the thing it interrupted or migrate the task it interrupted between cores, it isn't necessary to have a memory barrier.
  - jmgao 5y ago
    Knowing the Tegra chip in question, I'd bet it's probably not ARM's fault. Tegra X1, unlike pretty much every other SoC, did big.LITTLE via cluster migration with a custom cache coherence system, instead of just having a bunch of heterogenous cores. It turns out that their custom cache coherence was unfixably broken and would randomly corrupt memory when doing migration between the big and little cores, so everyone was forced to just entirely disable one set of cores. At least NVIDIA managed to fix this one in software?
omegacharlie 5y ago
> And how do you even find / debug a bug like this? I would imagine it takes a hardware debbugger for breakpoints, inspecting CPU register state, etc. offtopic: This is a post with link to the raw gist and another to gist.github.com
jeffybefffy519 5y ago
I love these kinda of bugs, so simple yet so complex.
veltas 5y ago
> 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, especially with context switching involved. Another possibility is that the bug is more deterministic than it looks, under the right conditions, and they managed to replicate it and analyse it in a debugger.
- retSava 5y ago
  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 :)
  - veltas 5y ago
    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.
    - IshKebab 5y ago
      Sometimes you can figure out the bug without reliably reproducing it if you have enough logs/stack traces etc.
      - foobiekr 5y ago
        a lot of bugs in the embedded world get fixed just by code inspection; I think most people who have done systems or embedded coding have casually noted bugs just by going through some code looking for something else or adding a new path or feature.
    - dspillett 5y ago
dstick 5y ago
"In the fragile reality of Discworld, and with the gods who like to play games, a million-to-one chance succeeds nine times out of ten." https://wiki.lspace.org/Million-to-one_chance https://wiki.lspace.org/Million-to-one_chance
- grumple 5y ago
  If you have millions of ops per day, a million-to-one chance of something means you'll see it every day! And it only takes a few noisy customers to bring these issues to light.
  - grayclhn 5y ago
    To be super pedantic, for one million ops it's closer to a 63% chance every day: Pr[something happens across 1_000_000 events] = 1 - Pr[nothing happens across 1_000_000 events] = 1 - Pr[nothing happens once]^1_000_000 ## assuming independence = 1 - (1 - Pr[something happens once])^1_000_000 = 1 - (1 - 1/1_000_000)^1_000_000 ≈ 1 - 0.378 = 0.632 It's still below 99% for 4 million ops.
    - Dylan16807 5y ago
      > for one million ops Okay, but they said millions. > It's still below 99% for 4 million ops. I find this misleading, because it's... 98%. Which completely undermines your argument. If something happens 98% of days, it's fine to call that "every day".
      - grayclhn 5y ago
        Dude, it was meant to be mildly educational, not an "argument."
        Dylan16807 5y ago
        Then present it as a fun fact rather than as a correction? And I'm not trying to be mean but I think the way you phrased your last line is accidentally anti-educational. Your last line treats 1 million ops and 4 million ops as nearly equivalent, when the truth is that 1 million ops is far from "every day" while 4 million ops can easily be called "every day". And if you dislike the word "argument" pretend I said "point"? I think you're reading connotations into that word that I didn't intend.
throwawaylinux 5y ago
> 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/linux.git/tree/kernel/sched/core.c#n3933 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.
- deleted 5y ago
  [deleted]
  - deleted 5y ago
    [deleted]
- bluenose69 5y ago
  Even if you're not following all the arguments involved, you can brighten your day by spending a few moments reading the documentation in this linux code (https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/sched/core.c#n3933 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...), which is a great example of how to document complex code.
- gpderetta 5y ago
  Note that this specific bug seem to happen only after cache operations (i.e. something like CLFLUSH, CLZERO in x86 parlance). It is possible that these instructions on the Switch SoC require a different barrier either because of spec details or hardware bugs.
richardfey 5y ago
Could this have been used for some exploit and that is why Nintendo prioritised it and fixed it?
- TravelPiglet 5y ago
  Or, hopefully, they are releasing a new Switch with more cores and it manifested it self more often on that hardware. :)
  - fallat 5y ago
    ...this sounds so plausible. So so plausible.
  - Agentlien 5y ago
    As a player I feel that would be pretty cool. As a developer I would absolutely love it. edit: this says something about priorities. It bothers me quite a lot how much I need to simplify the graphics for the switch versions of games I work on. It hardly bothers me at all when I play games on switch that the visual fidelity is lower on switch
throwawaybyeeee 5y ago
Reminds me of a similar bug that I worked on a few years ago that led to my single-line contribution to xnu (apologies for the dissertation): We had increasing reports of devices panicking because the kernel stopped draining a buffer, causing the buffer to fill. This particular buffer should never fill, so if it does -> panic. The first problem was that this bug was getting 'hot'. The bug needed to be fixed yesterday, and with the number of internal panics being reported, it was looking like it might delay shipping the OS. I was getting pinged constantly, and was expected to give daily updates in a giant cross-org shunning, the "bug review board" or BRB. The second problem was, of course, that all the code looked fine. (Spoiler: it was. Sort of.) The relevant drivers were handling synchronization properly and appeared to be race-free, memory management looked fine, no uninitialized variables, etc. No problem, we'll just reproduce it then... The third problem was that the bug was extremely hard to reproduce. With a single device it could take weeks to hit a single occurrence. So I needed a lot of devices, and every repro had to count. At this point it was clear that I needed some USB hubs, so off to Fry's (RIP). Two giant USB hubs, one Toblerone bar, and an abundance of charity from QA later, I had ~15 devices hooked to a computer. With this battery of devices I was reproducing the issue once every few days. Reproducing the bug reliably was a breakthrough, but root-causing the bug still felt like a dim prospect. The cores from the panics showed no smoking gun (our drivers' state looked fine), and my kernel mods to add simple lockless tracing seemed to suppress the bug, in true heisenbug fashion. And of course you're never sure if it actually suppressed the bug -- maybe you just didn't wait enough days? ~6 weeks had passed, filled with BRBs, all-nighters, working weekends, and testing tons of theories, all to no avail. On a whim I decided to revisit my lockless tracing strategy and remove a memory barrier. Alas! The bug triggered and I had tracing data! Digging into the tracing data, it turned out the problem wasn't in our drivers at all, but was actually in the kernel (IOKit) itself, IOInterruptController specifically. The problem was that IOIC was setting a flag and then immediately enabling interrupts via a MMIO write. With this logic, it was possible for another core to service an interrupt (since they were just enabled via the MMIO write), but still observe the old value of the flag, because there was no barrier between setting the flag and enabling interrupts. (Hence why the barrier added by my original tracing suppressed the bug.) Because IOIC read the wrong flag value, it entered a state that prevented interrupts from being serviced, and our buffer would fill and we'd panic. The fix was to simply add a memory barrier to IOIC between setting the flag and enabling interrupts. To this day I'm still mystified as to why this bug hadn't caused broken interrupts (+ mysterious behavior) or mass panics before then. There must've been some other change to xnu that exposed the bug somehow, but I'll probably never know.
fhars 5y ago
Reminds me of this game: https://deadlockempire.github.io/ https://deadlockempire.github.io/ where you have to think about scheduling problems similar to this.
- sneezey 5y ago
  TIL about this - I've had a few minutes of fun already ha!
jzer0cool 5y ago
What might be a few simple hello world projects to begin a journey understanding how to debug something like this? I suppose understanding of OS is important along with assembly. Given basic knowledge here, could someone list a few lessons to try and any toolsets?
- q3k 5y ago
  Write a toy operating system: https://wiki.osdev.org/Main_Page https://wiki.osdev.org/Main_Page For example, start with https://wiki.osdev.org/Bare_Bones https://wiki.osdev.org/Bare_Bones or https://wiki.osdev.org/Raspberry_Pi_Bare_Bones https://wiki.osdev.org/Raspberry_Pi_Bare_Bones You'll never build anything practical, but it's a great way to learn thing that you'd rarely have the opportunity to learn otherwise. Armed with that wide but shallow knowledge, you'll suddenly see many new opportunities to learn / do things that you wouldn't even have thought of before.
gpderetta 5y ago
First of all, it is amazing that the author managed to analyze the patch in so much details, it probably is an effort comparable to the bug fix itself. Still I think the article is missing some bits. I would expect any core migration to require barriers (either implicit or explicit) on both the old and new core otherwise the process would risk seeing its own stores and loads out of order. But in this case the barrier is predicated on the execution of some cache manipulation instruction, so I suspect things are more complicated. Maybe these specific cache manipulation instructions do not respect the usual architectural memory ordering and require some different set of barriers. Possibly they bypass cache coherence completely and require an actual flush of the cache. That is going to be very expensive and it make sense that it is only done only if the process was actually fiddling with these instructions. 'jmgao' else thread reported that tegra has coherency issues on migration, so it might be related.
- saagarjha 5y ago
  > But in this case the barrier is predicated on the execution of some cache manipulation instruction, so I suspect things are more complicated. Why do you think so? The explanation given seem reasonable to me…
  - gpderetta 5y ago
    As I sad, I would expect the barriers to be needed unconditionally on a core migration. The fact that there is a special flag that is set when (and only when) the cache control instructions are used seem to point to some special handling specifically for those instructions. Edit: having read the page for the nth time, I think I finally understand your point. The code using the cache instructions had an explicit barrier already, but it would be executed on the wrong thread. I know nothing about the arm memory model, but likely the dsb sy barrier is a stronger barrier than needed for intercore communication, and it is needed for IO serialisation, for example with an mapped PCI device. So yes, the article is clear and likely correct, I just failed to understand it fully originally.
    - jacquesm 5y ago
trinovantes 5y ago
CPU interrupts were the bane of my existence back in my undergrad OS class They were incredibly rare/difficult to replicate and reason through. Props to the unknown engineer that solved this
kabdib 5y ago
I spent a couple weeks finding a similar bug, a one instruction window where a hardware "wake up" register could get a stale value if an interrupt-and-reschedule happened at just the right instruction. The fix was to swap two instructions, so a register write happened in the correct order. I still remember the moment of clarity when the very thorny, complicated problem resolved into something obvious and simple, with a trivial fix. Hard problems seldom resolve so easily. You don't get these very often, cherish them :-)
deleted 5y ago
[deleted]
novok 5y ago
I'm surprised that nintendo maintains their own OS for the switch console too, instead of using linux or other unix derivative : https://en.wikipedia.org/wiki/Nintendo_Switch_system_software https://en.wikipedia.org/wiki/Nintendo_Switch_system_softwar...

offtopic: I really wish reading preformatted text files on ios safari was good.. I have to export the file to Books in order to read it properly

broodbucket 5y ago
Firefox reader mode is nice for taking various webpages, whether it's a news article with bloated JS, a wiki page, simple plaintext etc and giving it a common presentation that you can configure to your liking. No clue if that's a solution for you on iOS but it's a great feature.
- zinekeller 5y ago
  > No clue if that's a solution for you on iOS but it's a great feature. Unfortunately, iOS browsers tends to be just reskins of Safari (because it's required by Apple).
  - astrange 5y ago
    Reader mode would work in such a reskin I think, but Safari has its own reader mode anyway. The original Readability was a bookmarklet that worked in any browser.
deleted 5y ago
[deleted]
terhechte 5y ago
I just tried it out on iOS in Safari's reader mode, and it looks quite good. What don't you like about the output?
- jez 5y ago
  The file has diagrams that are meant to be viewed on a screen with enough space to leave long lines unbroken. If you attempt to get things to fit onto a single line by turning the phone sideways, it just zooms the text, instead of reflowing the text onto a larger line width. The problem exists in both the default rendering and the reader view. Opening in iBooks essentially prints the text file to a PDF, which defaults to US Letter paper size, which has the effect of making line widths large enough for most 80-character text files to fit without awkward mid-line soft breaks. The only other solution I know of is to manually zoom the page out to 50%. Luckily the zoom setting is saved by domain, so in this case if you want all raw githubusercontent files to view zoomed out iOS will remember that, but on domains where it’s a mix of text and HTML it’s more annoying.
eqtn 5y ago
iOS Firefox - https://i.imgur.com/1f5PElQ.jpeg https://i.imgur.com/1f5PElQ.jpeg iOS Safari Reader mode - https://i.imgur.com/nDnBSAM.jpeg https://i.imgur.com/nDnBSAM.jpeg iOS Safari - https://i.imgur.com/AhtWv9G.jpeg https://i.imgur.com/AhtWv9G.jpeg
aspenmayer 5y ago
https://gist.github.com/plutooo/2aadbd4a718e269df474079dd2e584fb/ https://gist.github.com/plutooo/2aadbd4a718e269df474079dd2e5...
kevincox 5y ago
I think people need to use text files less. Or at least stop hard-wapping them.
- hoseja 5y ago
  Hard-wrapping is my bane. Especially in RFCs.
- Thrymr 5y ago
  Does that mean that a browser shouldn't be able to display a text file with explicit line breaks, though?
- opan 5y ago
  I love text files and kinda like hard wrapping as well.

zinekeller 5y ago

> This bug has existed since day zero, which means that it took 5 years (!) for Nintendo to track it down. Credits to whoever nameless employee at Nintendo found this bug! The attention to detail is incredible. And how do you even find / debug a bug like this? Makes you think, do Linux, Windows and Mac handle this properly? Honestly, I doubt it! Considering the various kernel-level races in mainstream kernels (*BSD, Darwin, Linux and NT), I actually doubt that these kinds of bug are fully eliminated (only fixed in cases where such race has security implications).

broodbucket 5y ago

>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 to expose things that were thought to be fine. Also fuzzing.

ajross 5y ago
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're supposed to magically guess on a per-IP basis which state isn't? Yikes. I mean, the fix is the same. But arguing about which OSes "handle this properly" is missing the point. The question to ask is which core IPs (and which configurations thereof, remember the Tegra in question has both A53 and A57 cores) require barriers on interrupt entry, and under what circumstances. If ARM isn't going to publish that errata then asking for OS authors to magically figure it out is just asking for bugs.
- rustybolt 5y ago
  I might be missing something but don't see your point. If you want every interrupt to act as a memory barrier you can just insert a memory barrier in the interrupt handler. A reason not to do this is the overhead. Also, if you know the interrupt handler will not interact with memory from the thing it interrupted or migrate the task it interrupted between cores, it isn't necessary to have a memory barrier.
- jmgao 5y ago
  Knowing the Tegra chip in question, I'd bet it's probably not ARM's fault. Tegra X1, unlike pretty much every other SoC, did big.LITTLE via cluster migration with a custom cache coherence system, instead of just having a bunch of heterogenous cores. It turns out that their custom cache coherence was unfixably broken and would randomly corrupt memory when doing migration between the big and little cores, so everyone was forced to just entirely disable one set of cores. At least NVIDIA managed to fix this one in software?

omegacharlie 5y ago

> And how do you even find / debug a bug like this? I would imagine it takes a hardware debbugger for breakpoints, inspecting CPU register state, etc. offtopic: This is a post with link to the raw gist and another to gist.github.com

jeffybefffy519 5y ago

I love these kinda of bugs, so simple yet so complex.

veltas 5y ago

> 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, especially with context switching involved. Another possibility is that the bug is more deterministic than it looks, under the right conditions, and they managed to replicate it and analyse it in a debugger.

retSava 5y ago
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 :)
- veltas 5y ago
  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.
  - IshKebab 5y ago
    Sometimes you can figure out the bug without reliably reproducing it if you have enough logs/stack traces etc.
    - foobiekr 5y ago
      a lot of bugs in the embedded world get fixed just by code inspection; I think most people who have done systems or embedded coding have casually noted bugs just by going through some code looking for something else or adding a new path or feature.
  - dspillett 5y ago

dstick 5y ago

"In the fragile reality of Discworld, and with the gods who like to play games, a million-to-one chance succeeds nine times out of ten." https://wiki.lspace.org/Million-to-one_chance https://wiki.lspace.org/Million-to-one_chance

grumple 5y ago
If you have millions of ops per day, a million-to-one chance of something means you'll see it every day! And it only takes a few noisy customers to bring these issues to light.
- grayclhn 5y ago
  To be super pedantic, for one million ops it's closer to a 63% chance every day: Pr[something happens across 1_000_000 events] = 1 - Pr[nothing happens across 1_000_000 events] = 1 - Pr[nothing happens once]^1_000_000 ## assuming independence = 1 - (1 - Pr[something happens once])^1_000_000 = 1 - (1 - 1/1_000_000)^1_000_000 ≈ 1 - 0.378 = 0.632 It's still below 99% for 4 million ops.
  - Dylan16807 5y ago
    > for one million ops Okay, but they said millions. > It's still below 99% for 4 million ops. I find this misleading, because it's... 98%. Which completely undermines your argument. If something happens 98% of days, it's fine to call that "every day".
    - grayclhn 5y ago
      Dude, it was meant to be mildly educational, not an "argument."
      - Dylan16807 5y ago
        Then present it as a fun fact rather than as a correction? And I'm not trying to be mean but I think the way you phrased your last line is accidentally anti-educational. Your last line treats 1 million ops and 4 million ops as nearly equivalent, when the truth is that 1 million ops is far from "every day" while 4 million ops can easily be called "every day". And if you dislike the word "argument" pretend I said "point"? I think you're reading connotations into that word that I didn't intend.

throwawaylinux 5y ago

> 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/linux.git/tree/kernel/sched/core.c#n3933 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.

deleted 5y ago
[deleted]
- deleted 5y ago
  [deleted]
bluenose69 5y ago
Even if you're not following all the arguments involved, you can brighten your day by spending a few moments reading the documentation in this linux code (https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/sched/core.c#n3933 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...), which is a great example of how to document complex code.
gpderetta 5y ago
Note that this specific bug seem to happen only after cache operations (i.e. something like CLFLUSH, CLZERO in x86 parlance). It is possible that these instructions on the Switch SoC require a different barrier either because of spec details or hardware bugs.

richardfey 5y ago

Could this have been used for some exploit and that is why Nintendo prioritised it and fixed it?

TravelPiglet 5y ago
Or, hopefully, they are releasing a new Switch with more cores and it manifested it self more often on that hardware. :)
- fallat 5y ago
  ...this sounds so plausible. So so plausible.
- Agentlien 5y ago
  As a player I feel that would be pretty cool. As a developer I would absolutely love it. edit: this says something about priorities. It bothers me quite a lot how much I need to simplify the graphics for the switch versions of games I work on. It hardly bothers me at all when I play games on switch that the visual fidelity is lower on switch

throwawaybyeeee 5y ago

Reminds me of a similar bug that I worked on a few years ago that led to my single-line contribution to xnu (apologies for the dissertation): We had increasing reports of devices panicking because the kernel stopped draining a buffer, causing the buffer to fill. This particular buffer should never fill, so if it does -> panic. The first problem was that this bug was getting 'hot'. The bug needed to be fixed yesterday, and with the number of internal panics being reported, it was looking like it might delay shipping the OS. I was getting pinged constantly, and was expected to give daily updates in a giant cross-org shunning, the "bug review board" or BRB. The second problem was, of course, that all the code looked fine. (Spoiler: it was. Sort of.) The relevant drivers were handling synchronization properly and appeared to be race-free, memory management looked fine, no uninitialized variables, etc. No problem, we'll just reproduce it then... The third problem was that the bug was extremely hard to reproduce. With a single device it could take weeks to hit a single occurrence. So I needed a lot of devices, and every repro had to count. At this point it was clear that I needed some USB hubs, so off to Fry's (RIP). Two giant USB hubs, one Toblerone bar, and an abundance of charity from QA later, I had ~15 devices hooked to a computer. With this battery of devices I was reproducing the issue once every few days. Reproducing the bug reliably was a breakthrough, but root-causing the bug still felt like a dim prospect. The cores from the panics showed no smoking gun (our drivers' state looked fine), and my kernel mods to add simple lockless tracing seemed to suppress the bug, in true heisenbug fashion. And of course you're never sure if it actually suppressed the bug -- maybe you just didn't wait enough days? ~6 weeks had passed, filled with BRBs, all-nighters, working weekends, and testing tons of theories, all to no avail. On a whim I decided to revisit my lockless tracing strategy and remove a memory barrier. Alas! The bug triggered and I had tracing data! Digging into the tracing data, it turned out the problem wasn't in our drivers at all, but was actually in the kernel (IOKit) itself, IOInterruptController specifically. The problem was that IOIC was setting a flag and then immediately enabling interrupts via a MMIO write. With this logic, it was possible for another core to service an interrupt (since they were just enabled via the MMIO write), but still observe the old value of the flag, because there was no barrier between setting the flag and enabling interrupts. (Hence why the barrier added by my original tracing suppressed the bug.) Because IOIC read the wrong flag value, it entered a state that prevented interrupts from being serviced, and our buffer would fill and we'd panic. The fix was to simply add a memory barrier to IOIC between setting the flag and enabling interrupts. To this day I'm still mystified as to why this bug hadn't caused broken interrupts (+ mysterious behavior) or mass panics before then. There must've been some other change to xnu that exposed the bug somehow, but I'll probably never know.

fhars 5y ago

Reminds me of this game: https://deadlockempire.github.io/ https://deadlockempire.github.io/ where you have to think about scheduling problems similar to this.

sneezey 5y ago
TIL about this - I've had a few minutes of fun already ha!

jzer0cool 5y ago

What might be a few simple hello world projects to begin a journey understanding how to debug something like this? I suppose understanding of OS is important along with assembly. Given basic knowledge here, could someone list a few lessons to try and any toolsets?

q3k 5y ago
Write a toy operating system: https://wiki.osdev.org/Main_Page https://wiki.osdev.org/Main_Page For example, start with https://wiki.osdev.org/Bare_Bones https://wiki.osdev.org/Bare_Bones or https://wiki.osdev.org/Raspberry_Pi_Bare_Bones https://wiki.osdev.org/Raspberry_Pi_Bare_Bones You'll never build anything practical, but it's a great way to learn thing that you'd rarely have the opportunity to learn otherwise. Armed with that wide but shallow knowledge, you'll suddenly see many new opportunities to learn / do things that you wouldn't even have thought of before.

gpderetta 5y ago

First of all, it is amazing that the author managed to analyze the patch in so much details, it probably is an effort comparable to the bug fix itself. Still I think the article is missing some bits. I would expect any core migration to require barriers (either implicit or explicit) on both the old and new core otherwise the process would risk seeing its own stores and loads out of order. But in this case the barrier is predicated on the execution of some cache manipulation instruction, so I suspect things are more complicated. Maybe these specific cache manipulation instructions do not respect the usual architectural memory ordering and require some different set of barriers. Possibly they bypass cache coherence completely and require an actual flush of the cache. That is going to be very expensive and it make sense that it is only done only if the process was actually fiddling with these instructions. 'jmgao' else thread reported that tegra has coherency issues on migration, so it might be related.

saagarjha 5y ago
> But in this case the barrier is predicated on the execution of some cache manipulation instruction, so I suspect things are more complicated. Why do you think so? The explanation given seem reasonable to me…
- gpderetta 5y ago
  As I sad, I would expect the barriers to be needed unconditionally on a core migration. The fact that there is a special flag that is set when (and only when) the cache control instructions are used seem to point to some special handling specifically for those instructions. Edit: having read the page for the nth time, I think I finally understand your point. The code using the cache instructions had an explicit barrier already, but it would be executed on the wrong thread. I know nothing about the arm memory model, but likely the dsb sy barrier is a stronger barrier than needed for intercore communication, and it is needed for IO serialisation, for example with an mapped PCI device. So yes, the article is clear and likely correct, I just failed to understand it fully originally.
  - jacquesm 5y ago

trinovantes 5y ago

CPU interrupts were the bane of my existence back in my undergrad OS class They were incredibly rare/difficult to replicate and reason through. Props to the unknown engineer that solved this

kabdib 5y ago

I spent a couple weeks finding a similar bug, a one instruction window where a hardware "wake up" register could get a stale value if an interrupt-and-reschedule happened at just the right instruction. The fix was to swap two instructions, so a register write happened in the correct order. I still remember the moment of clarity when the very thorny, complicated problem resolved into something obvious and simple, with a trivial fix. Hard problems seldom resolve so easily. You don't get these very often, cherish them :-)

deleted 5y ago

[deleted]

novok 5y ago

I'm surprised that nintendo maintains their own OS for the switch console too, instead of using linux or other unix derivative : https://en.wikipedia.org/wiki/Nintendo_Switch_system_software https://en.wikipedia.org/wiki/Nintendo_Switch_system_softwar...