A cache invalidation bug in Linux memory management
googleprojectzero.blogspot.com
googleprojectzero.blogspot.com
32 bits is suitable for things that can only happen once a frame - (2^32/60) seconds = 2.26 years - but not much more than that.
But there's a flip side to computers being able to wrap a uint32_t so quickly: if you've got 32 bits'-worth of combinations, then you can might actually be able to do an exhaustive test. 2^32 microseconds = 71 minutes. Work in C++, run on all threads, and you probably won't even need to wait that long.
Good example: https://randomascii.wordpress.com/2014/01/27/theres-only-fou... - runs in 90 seconds.
I did something similar a few years ago, prototyping a 16x16 multiply routine for an 8-bit CPU. It took about 5 minutes running on both threads on my 2.5GHz dual core laptop, and found some interesting cases I'd got completely wrong.
Edit: sorry, I just don't have the time to get you the details.
Obviously that needs to be multiplied by the number of instructions a test needs to execute (and it has to be well written with AVX 512), but we're not talking nation state levels of resources here for simple cases, and that figure is only going to drop further with time.
Not to mention the potential for FPGA or ASIC implementations if the tests are important enough.
What do you mean by a 'frame' and how does 2.26 years relate to a frame?
For real though, the difference between 60 and 144 is night and day. I can't go back to 60 after playing with 144. I wonder if going beyond 144 would have the same effect.
For me, the biggest bug in the modern x86 chip is ME: a full system that can be turned on, take over everything and eats up valuable core space.
Cryptography actually relies on there being a space that is too large to count though, even in parallel.
I'm skeptical that much changes in the next decade regarding where 64-bit integers are useful. It's been a long time since there are been meaningful clock frequency increases in commodity CPUs. Even if we had a 100Ghz CPU and we had it increment a register once per clock cycle, we're still talking ~6 years for it to overflow. And, thats assuming a 20+ times increase in clock frequency when clock frequencies have been mostly flat for the last 10 years.
> a programmer in the future commenting that 128-bits should have been used, and 128-bits will break in the future of that future, and so on.
I disagree with this statement. With 128-bits, it becomes difficult (though not impossible) to even come up with things that are numerous enough to be unable to count with that number of bits. That was never the case for 64-bit or smaller integers.
Apparently he thought of the spectre-style vulnerabilities while through the Intel processor manuals[1]. How many established engineers would a) read through these reference manuals at all, and b) question the implementations described therein?
[1]: https://www.bloomberg.com/news/articles/2018-01-17/how-a-22-...
That's a pretty bad design decision. I'd much rather have a kernel panic than a kernel that continues to run with known bad datastructures. Like that the bugs will never really shake out, silent failures like that are super dangerous because essentially the system is running in an undefined state past that point.
That's not to say it's a good design choice, but it's certainly a defensible one IMO. You can have the most secure OS in the world, but if no one wants to use it, all you've got is a very secure waste of hard drive space.
After all, a harddrive or a CPU could die just the same.
Especially if the system is still stable enough to write a log entry to disk.
Think of this from the lense of natural selection. There are many many subtle tricky low-level bugs that can result in memory corruption - many drivers, many features, many optimizations, many "cleanups", a surprisingly high rate of code changes. Many of them are caught when they cause problematic corruption. Others, just due to luck, very rarely cause any visible problem, - for months or years. We do want to know about them. We do not want to suicide the whole system, it may be one of those rare bugs that made it this far because it's usually (surprisingly) not fatal on its own.
Anyway, there has been discussion about this issue in general previously on the Linux kernel mailing list, and Linus said [1] that the correct procedure is to first introduce by-default reporting and an opt-in kill switch, then make the kill switch the default, then remove the non-kill option. This is supposed to weed out bugs eventually without disrupting users too much, but I can imagine that it enables some expolits. There was an HN discussion about it too. [2]
[1] https://lkml.org/lkml/2017/11/21/356 [2] https://news.ycombinator.com/item?id=15754988
I mean, that is literally what an Oops is.
Whether you should leave it on in production is debatable, but I like at least having the option of making exceptions raised in drivers nonfatal.
Whenever I had to write device drivers I wrote them under QnX first and only then ported them to other OS's, that saved so much time, at least I knew the hardware interface would be up and running, and the data structures would all work as intended. After that all I then had to do was glue it to whatever calling convention the various *NIX flavors had.
That trick served me well, for motion capture devices as well as for high speed serial cards and some more exotic devices.
Honestly I'm ok with trying to keep the system limping with a huge but - you must, at the point you first detect an error, dump...everything you know. You can try to limp along because you're trying to be a good host, but debugging after that state is, as you said, not trivial.
If you separate the two concerns (post-mortem debugging & uptime) there's a nice medium to be found. Ideally kernel panics aren't the only source of observability. You can have a daemon running that files a bug report to your favorite error tracker (sentry, etc) and (attempts to) gracefully reboot the system. That would be pretty sweet.
Cache invalidation, and naming things. And off by one errors.
(Once someone answers this, I promise to read and process the answer, but I'll go and do something else in the meantime)
For example:
1) Why do we have entirely different management structures for anonymous memory (anon_vma and friends) and shared memory (inodes) when they really end up doing the same job? (Anonymous memory can be shared, so both paths end up needing to do the same kind of thing.) ISTM we can just use shared objects in all cases, tweaking the semantics as needed for shared memory. Anonymous memory is just swap-backed shared memory, after all. It should use the same logic.
(Yes, you need to work without a swapfile. No, that doesn't change the conceptual model.)
2) Do we really need open-coded page table walking? Why duplicate essentially the same logic four times? Sure, you occasionally want to do slightly different things at each page table level, but you can still unify most of the logic. (If you really want, you can encode the per-level differences in code generated via C++ template.)
3) Do micro-optimizations of the sort mentioned in the article really help? If these sequence numbers had been 64 bits long, they wouldn't have overflowed. If the VMA tree had been implemented as a splay tree (like on NT) instead of an RB tree with a per-thread cache, the per-thread cache might not have been needed. (Splay trees automatically cache recently-accessed nodes.) How much do these little tricks actually help? Is their cumulative effect positive?
4) Why is so much of the vm internal logic spread throughout the kernel? Both NT and the BSDs have a well-defined API that separates the MM subsystem from the rest of ring 0, but on Linux, ISTM that lots of code needs to care directly about low-level mm structures and locks. Why should code very far from the mm core (like the i915 driver) take mmap_sem directly? It feels like more abstraction would be possible here.
I get arguments based around ruthless pursuit of performance, but with function calls taking nanoseconds and page faults taking orders of magnitude more time, is anyone saving anything significant?
It's a tough call, the mantra used to be 'get it right, then make it fast', but in practice whoever ships the fastest stuff will win the race, even if it is incorrect. As long as it is correct long enough to run the benchmarks I guess.
This is yet another reason why I love microkernels (real ones), they are a lot easier to reason about and to get right to the point that you can really rely on them not to suddenly exhibit some weird behavior due to the complexity of their execution context.
Each optimization needs to be evaluated on its own. Not every optimization actually helps, and due to the effects of path length, icache pressure, and code complexity, the cumulative effect of many micro-optimizations may end up being negative. (It's why -funroll-all-loops is not in fact very fun.)
There's no forced tradeoff between complexity and speed! The fastest code is the code that doesn't run at all. Often, the best way to optimize a program is to strip it down to the rafters and then re-add only the optimizations that actually help. Simpler is often faster.
For pure software optimizations I would be more than happy to end up with a machine that is half as fast but bulletproof. But I am not sure that I am in the majority there.
And even though you are right that there is no forced tradeoff between complexity and speed in practice this is often the case, so often that we have institutionalized it, we generally accept that in order to make things faster we will have to make them more complex. If not then the most naive version of code would in general be the fastest and this just isn't the case.
So in the end it all boils down to where you draw an arbitrary line and say 'to the right there is too much complexity, to the left we are too slow'. Everybody will want to draw that line somewhere else, so we try to have our cake and eat it too: we optimize as much as we can, make stuff more and more complex and then we try to shoot holes in it. Sometimes successfully!
I'm taken with Daniel Bernstein's observation that speed is totally unimportant for ~95% of the code generated. The reason being it the percentage of the time it runs is a small percentage of the total, or it runs hardly or not at all.
And I'll add that for most programs written, speed isn't important. Because the cost to run them is a small fraction of the cost to write and maintain them.
https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf
Historical reasons. There’s an early prototype to get rid of it.
Calling this a micro-optimization is thus misleading; rather, it probably helps quite a lot in some particular workloads and has a negligible impact on others.
I wonder how freeBSD engineered this...Linux appears to grow organically at times.
FreeBSD doesn't have a per-thread cache, but does similarly use a generation number to allow operations to detect stale state upon reacquiring the vm map lock. I don't see why it isn't prone to the same kinds of bugs.
if (i=0) {
So the bug is still there then? It will just take longer to hit.
Until someone else decides to change the encoding of that field, for some reason, and not initialize it at 0. It instead starts with a random value (for safety reasons). Good luck figuring out that random crash that happens once in a blue moon.
It will take so long that the hardware will have died many times over before the bug triggers, assuming society as we know it is still around.
So:
A) There is no reason whatsoever to randomize the counter B) Even if they did, it wouldn't be a problem because it would still take an absurdly long time to loop around to the starting positions.