5 ms·

I've been taking a pretty close look at Linux's mm code recently, and I've been wondering why it needs to be as complex as it is. There's a brain-exploding amou

I've been taking a pretty close look at Linux's mm code recently, and I've been wondering why it needs to be as complex as it is. There's a brain-exploding amount of complexity, most of it open-coded, that seems to my eye to be unnecessary, or at least amenable to abstraction. 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?

jacquesm 8y ago
If you strip out all performance optimizations from modern computers they will be a lot more secure but they will run slow as molasses. Starting with the hardware caches and ending with optimizations like these we are not talking 'minor gains' but likely orders of magnitude difference between optimized and non-optimized. And all of those have security trade-offs. 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.
- quotemstr 8y ago
  > If you strip out all performance optimizations from modern computers they will be a lot more secure but they will run slow as molasses 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.
  - Gibbon1 8y ago
    > The fastest code is the code that doesn't run at all. 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 https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf
  - jacquesm 8y ago
    That is mostly true, but the fact is that until 'spectre' and 'meltdown' everybody believed that the security implications of hardware caches were theoretical. It took decades since we started using them for the first practical manifestations of issues that were warned about long ago. 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!
amluto 8y ago
> Do we really need open-coded page table walking? Why duplicate essentially the same logic four times? Historical reasons. There’s an early prototype to get rid of it.
- MBCook 8y ago
  Plus when there were only two levels of page tables it didn’t matter that much. Now that we’re starting to see for and even five it’s becoming an issue.
markjdb 8y ago
Regarding 3), I suspect that the optimization is rather important for page fault scalability when the process has many threads. You would traditionally synchronize access to the VMA tree using some sort of reader-writer lock, but scalable read locks impose a higher cost to writers. It's easy to believe that splay trees wouldn't help and might hurt in this case, as lookups may modify the tree structure and thus can require more synchronization than a read lock. 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.
gshrikant 8y ago
I'm sorry of this is a trivial question but what does open coding mean? This is the first time I've heard of that term.
- tedunangst 8y ago
  Manual inlining. Writing code instead of calling a function.

jacquesm 8y ago

If you strip out all performance optimizations from modern computers they will be a lot more secure but they will run slow as molasses. Starting with the hardware caches and ending with optimizations like these we are not talking 'minor gains' but likely orders of magnitude difference between optimized and non-optimized. And all of those have security trade-offs. 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.

quotemstr 8y ago
> If you strip out all performance optimizations from modern computers they will be a lot more secure but they will run slow as molasses 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.
- Gibbon1 8y ago
  > The fastest code is the code that doesn't run at all. 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 https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf
- jacquesm 8y ago
  That is mostly true, but the fact is that until 'spectre' and 'meltdown' everybody believed that the security implications of hardware caches were theoretical. It took decades since we started using them for the first practical manifestations of issues that were warned about long ago. 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!

amluto 8y ago

> Do we really need open-coded page table walking? Why duplicate essentially the same logic four times? Historical reasons. There’s an early prototype to get rid of it.

MBCook 8y ago
Plus when there were only two levels of page tables it didn’t matter that much. Now that we’re starting to see for and even five it’s becoming an issue.

markjdb 8y ago

Regarding 3), I suspect that the optimization is rather important for page fault scalability when the process has many threads. You would traditionally synchronize access to the VMA tree using some sort of reader-writer lock, but scalable read locks impose a higher cost to writers. It's easy to believe that splay trees wouldn't help and might hurt in this case, as lookups may modify the tree structure and thus can require more synchronization than a read lock. 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.

gshrikant 8y ago

I'm sorry of this is a trivial question but what does open coding mean? This is the first time I've heard of that term.

tedunangst 8y ago
Manual inlining. Writing code instead of calling a function.