LWN: Comments on "The case of the overly anonymous anon_vma"

The case of the overly anonymous anon_vma

efexis — Mon, 03 May 2010 16:51:07 +0000

You're right about the page fault bit, my mistake, a reference count would be sufficient there, the reverse map would be for changing the backing for purposes of swap or migration in a NUMA or HIGHMEM system where quick knowledge page<-->active sets is required.
Reverse mapping for file backed pages don't need anon_vma stuff obviously, because they're not anon. What they use isn't simpler though, as, for example, a library will often be shared by more address spaces than an anon page, it makes more sense to use a search tree (at least this used to be the case, according to a slightly dated early 2.6.x book detailing it. If it's now simpler than this, that would show kernel devs in fact simplifying things, not adding complexity).
If you use none of these, go into your kernel conf and disable CONFIG_SWAP, CONFIG_NUMA and any CONFIG_HIGHMEM entries. If nothing else uses it, it'll either be removed, or worst case, a few greps will show you where the functions are being used elsewhere to throw a few #ifdef's around (I imagine embedded comunity would have interest in already doing this).

The case of the overly anonymous anon_vma

i3839 — Sat, 01 May 2010 12:17:27 +0000

It is. Reverse mapping for file backed pages doesn't need anon_vma stuff, it's a lot simpler.

You don't need a reverse mapping to do COW, when you get a pagefault you know the virtual address which caused it.

Reverse mapping is needed to find all virtual pages belonging to a certain physical one. That isn't needed often for anonymous memory.

The case of the overly anonymous anon_vma

efexis — Fri, 30 Apr 2010 20:02:52 +0000

Hmm... I dunno, I would have thought that this isn't so much only needed for anonymous memory, but this may be the only reason why it's needed for anonymous memory, iyswim... that in other uses there are other reasons for it too, and so it can actually be simpler to just have it, than have it in some places and not in others. Anywhere you have copy-on-write pages it's going to be important, as the way you achieve that is to mark the pages read only. Someone tried to write to it, it causes a memory protection fault, which jumps into the VM code giving it the address of memory that the fault occured while trying to write. So where do you start if you don't have a back link to get from that address to the structures belonging to those using the page? You'd end up just doing loads of searching instead. The same goes for when it's something like memory mapped files, you need to know when the pages have been modified so you know it has to at some point be written back to disk. If you can't look up what's going on from the address it's going on at, things get way more complicated. Seems this is just basic accounting :-/

The case of the overly anonymous anon_vma

i3839 — Mon, 26 Apr 2010 19:09:39 +0000

I hope you're wrong. :-)

This seems more a gradual development, with every thing on its own making sense at the time, but together still going in the wrong direction. It for sure isn't a big enough problem yet.

It would be nice to know what the reverse mapping is used for besides swapping. It seems that the reverse mapping of files is a solved problem, but that all this complexity is only for anonymous memory. Which can only go away is you have swap enabled, or some obscure option like memory hotplug. (In the case of hibernation you need to scan all pages anyway, so no need for this either.) So I guess that my main complaint is that this is done even when not needed.

For swap you only need a reverse mapping for pages that might get swapped out soon. I wonder if it's possible to create that mapping only for inactive pages instead of all of them all the time. Alternatively, swapping out can be done per-process, then there's no need for a reverse map. Shared pages are swapped out less quickly, but that's usually better anyway.

The swapping system needs an overhaul anyway, it's very slow currently. This way both the VM and the swap systems can be improved.

Improving the current code may not be easy, but it for sure is possible.

The case of the overly anonymous anon_vma

efexis — Mon, 26 Apr 2010 03:03:44 +0000

"I don't have time to look further into the details"

Well my guess is that they did, and that code that mostly slowed the memory manager down for savings only in a corner case would have been thrown out by Linus, as is often the way.

The case of the overly anonymous anon_vma

i3839 — Sat, 24 Apr 2010 22:48:50 +0000

You're forgetting the memory overhead (including cache misses), not everything is pure CPU cycles. Besides that, this adds a cost to most memory operations, even if it turns out it was never necessary. Why slow down the common case to speed up special cases in rare situations?

I don't have time to look further into the details, at least not this month. Hopefully next month.

The case of the overly anonymous anon_vma

ewen — Sat, 24 Apr 2010 22:21:05 +0000

If you always insert at the start of the list, or always insert at the end of the list, then the order that you are maintaining is "order inserted" (either newest at start or newest at end). This isn't necessarily what one means by an ordered list (except if you actually want a stack or a queue, both of which are "ordered by time"). Inserting anywhere else in the list, to order by a data value, requires finding that location, eg, page address, which requires either knowing the pointer to the immediately prior page address in the list, or going and finding same (O(n)). (As you suggest deletes could be quick if you make the process track a pointer to the relevant entry in the link list, and use a double linked list, something I'd overlooked.)

From what I can see "find by page address" is the only primitive that actually matters here (so you can find the references to that page); "find by process id" seems easiest done starting with the processes structures. And the problem that we started with was a 1,000,000-long linked list which referenced multiple pages held by multiple processes. So any structure which made it faster to find the entries for the appropriate page would help, providing its other overhead wasn't too high.

Ewen

The case of the overly anonymous anon_vma

efexis — Sat, 24 Apr 2010 21:46:37 +0000

Inserts are also quick if you do maintain order, simply by maintaining a pointer to the end of the list. You've only two pointers to update for the list (end of list and pointer to end of list) or am I forgetting something? Deletes could be sped up by making it double linked, and I can't think of why you'd ever need to perform a search... even if you needed to find a particular processes own structure for a page, seems like you'd start the search from that processes page table which can be done in a determinate amount of time, rather than from your own and then through the linked list.

I don't know what other property you could be looking for, other than memory address or process id, that you could use as the value for an index or hash. If you were collecting a stat (such as the process that's using the page that runs the most, which could be a useful thing to know) you'd have to iterate through the lot. Maintaining an index of that value is loads more work that I can't see paying off. What other value, other than page address and process id, would you want to search on?

The case of the overly anonymous anon_vma

efexis — Sat, 24 Apr 2010 21:15:17 +0000

Fantastic. That last diagram is like a punchline, I wasn't completely with it until that last one which triggered what I refer to as a "cascade of realisation", which is like a nice brain massage :-) much appreciated.

Not so appreciated though was the pointing to a 2004 article that I remember reading like it was just erm... 200err... 2007? Way to make me feel old for the first time ever ;-p

The case of the overly anonymous anon_vma

ewen — Sat, 24 Apr 2010 21:08:36 +0000

I had in mind replacing the linked list with, eg, a hash (with buckets, probably), which is O(n) average case, or some sort of tree structure, which is O(log n) average case. Inserts are quick on a linked list if you don't bother to maintain any order, but searching and deletes are not; for most other structures inserts are a bit slower, but you get faster searching and deletes.

Still if the tricky details of the new solution have been sorted out then there's no point in changing back now. I guess time will tell.

Ewen

The case of the overly anonymous anon_vma

efexis — Sat, 24 Apr 2010 20:59:48 +0000

More complex doesn't necessarily mean less efficient. Having to search through all other pages belonging to all other processes, just to see who, if anyone, is sharing it with you, incures considerably more overhead. There're probably more reasons you'd want to do this than just at page swapout time too, maybe dealing with process memory limits - knowing who to charge the memory usage to, or with NUMA systems becoming more common, knowing whether it's worth moving a page to memory closer to the core running the majority of processes accessing it. Sure it's more complex to us, processing this extra information in our heads, but that little extra time can save a lot of time in the long run.

The case of the overly anonymous anon_vma

efexis — Sat, 24 Apr 2010 20:45:29 +0000

"That fix makes me wonder about the "daemon startup" situation"

I don't think that matters (if I've interpreted what's said above correctly), as the page is unlikely to be unlinked from all the processes between the daemon fork()s taking place, as those initial processes are going to be pretty short lived. When the top process terminates, the next process down the list would have to take on the links, which will require some work, but no more than what would have to be done if this was done earlier in the game if you knew that the child was going to live longer. The only way it would save time would be if the memory was unlinked (eg, paged out), then paged back in and linked to the shorter running process - picking the longest running process would be more ideal. But yeah, for a process to be running long enough for this to happen probably rules out the ability to predict which is going to end sooner.

The case of the overly anonymous anon_vma

efexis — Sat, 24 Apr 2010 20:33:43 +0000

"eg, something indexed by page address"

That's what the page table is. But you can only index a fixed number of things from that, once you have a variable number of things (as there being any number of processes sharing that page), that's then another dimension, and can thus not be represented using a single dimension of the page address alone. A linked list might be slow for searching in, but in this case it looks like most operations are going to be either inserts (eg, at fork() time), deletes (at CoW or process termination time), and I guess possibly an action required on the whole group, although I couldn't suggest what. These seem like they'd all about as cheap on a linked list as you can get.

The case of the overly anonymous anon_vma

i3839 — Fri, 23 Apr 2010 16:17:41 +0000

Not only that, if the anon_vma isn't used for file caches, but only for anonymous pages then the whole thing seems dubious when swap is disabled.

In addition to that, anon_vma apparently didn't solve the problem well, but instead of replacing it with something that does, more kludges are added on top of it. I got the feeling that there's some much more elegant solution waiting for someone to find it.

The case of the overly anonymous anon_vma

rilder — Fri, 23 Apr 2010 13:41:45 +0000

Even I feel the same. The scenario "In a workload with 1000 child processes and a VMA with 1000 anonymous pages per process that get COWed," -- may not arise in a normal desktop workload. In such as case won't this introduce additional overhead, unless this feature is introduced as a CONFIG variable which I don't think it is.

Anyone completed the exercise?

pjm — Fri, 16 Apr 2010 04:27:29 +0000

I think the point is just that standard tools like to avoid nodes overlapping each other, so if you have a million nodes on screen then each node must occupy only about 1 pixel, and you wouldn't be able to get any information about the problem other than a million sure is a big number, isn't it?. But it wasn't really a serious suggestion for understanding the bug, which could be illustrated with just one or two child processes.

(I was hoping to be able to point people to a certain impressive tool I've seen for interactively exploring large graphs, but I see that the code isn't yet publicly available. However, it's expected to be redeveloped and GPL'd in a year or two, under the name Dunnart.)

The case of the overly anonymous anon_vma

i3839 — Thu, 15 Apr 2010 22:02:45 +0000

Is it just me who's wondering whether all this complexity is worth it?

What was it needed for again? To have a reverse mapping? Isn't that mostly useful for swapping and not much else? It seems silly to always add the overhead when it's almost never needed. Why not only have the overhead when actually swapping or whenever it's needed? Then this whole mess disappears from the common case and the complex stuff can be separated and isolated.

I have to read more code and think more about it, preferably with a clear mind.

The case of the overly anonymous anon_vma

iabervon — Thu, 15 Apr 2010 20:17:47 +0000

Actually, that's a similar message, but not the one I was thinking of. In that one, he says "So again, I can show that..." I was looking at the first time, and this is the second time. The one I'm thinking of is http://groups.google.com/group/linux.kernel/msg/f9c7ca848... and has a more complete explanation of the middle steps.

The case of the overly anonymous anon_vma

Felix — Thu, 15 Apr 2010 20:09:08 +0000

I think you mean this mail from Linus
http://groups.google.co.id/group/linux.kernel/msg/130d3ea...

(it has a slightly different message id+time but seems to fit)

The case of the overly anonymous anon_vma

Darkmere — Thu, 15 Apr 2010 12:07:15 +0000

I just resubscribed. Still somewhat starving hacker, but it's better than nothing. Now to register a company account once I snipe a creditcard from someone ;)

Anyone completed the exercise?

nikanth — Thu, 15 Apr 2010 06:08:12 +0000

the diagram for the 1000-child scenario which motivated this patch will be left as an exercise for the reader.
Has anyone completed the exercise. ;-)
Probably it shouldn't be daunting using the right tool + script. Even a video may be possible. :)

The case of the overly anonymous anon_vma

mrfredsmoothie — Wed, 14 Apr 2010 19:00:00 +0000

That's precisely the point of the Linus "don't rely on a tool" philosophy of bug-fixing.

If your code cannot be reasoned about by a human, then it cannot be maintained by a human, either.

The case of the overly anonymous anon_vma

gwittenburg — Wed, 14 Apr 2010 15:04:07 +0000

+1, same here. Thanks, Jonathan!

The case of the overly anonymous anon_vma

sorpigal — Wed, 14 Apr 2010 11:37:25 +0000

I hereby register one (1) classic "Me too," reply.

The case of the overly anonymous anon_vma

jzbiciak — Wed, 14 Apr 2010 04:57:11 +0000

Ah, ok. I hadn't seen that email. Makes sense.

The case of the overly anonymous anon_vma

iabervon — Wed, 14 Apr 2010 04:44:51 +0000

The message I'm thinking of is <alpine.LFD.2.00.1004061220270.3487@i5.linux-foundation.org> from Apr 6 at 15:35; Linus looks at Steinar Gunderson's disassembly, where %rax is a kernel pointer and %rbx is not %rax+20 like it would be after running the loop, implying that "anon_vma->head.next" is NULL, not some other anon_vma_chain entry. Boris had worked out that there was some problem in the list previously, but Linus identified that the pointer from the anon_vma was bad, rather than the list further down being corrupt. This turned out to be important to the actual bug, which had to do with the anon_vma associated with the page being gone (and its memory reused) rather than some other anon_vma in the vma's chain being gone or something messing up the list. Boris picked up the stuff you'd get from a debugger that had registers but not core; Linus picked up an important detail that one would only normally get from a debugger by inspecting memory.

The case of the overly anonymous anon_vma

jzbiciak — Wed, 14 Apr 2010 04:11:33 +0000

Actually, wasn't that Boris that did the initial assembly dump interpretation?

It's actually not so hard once you've done it a couple times. I've had to chase down bugs in our C compiler at work (ah, the joys of running internal alpha builds!).

The case of the overly anonymous anon_vma

ewen — Tue, 13 Apr 2010 20:22:33 +0000

The fix is straightforward; when linking an existing page to an anon_vma structure, the kernel needs to pick the one which is highest in the process hierarchy; that guarantees that the anon_vma will not go away prematurely.

That fix makes me wonder about the "daemon startup" situation, where the initial process fork()s at least once (sometimes twice), and then the parent process exits. I assume that the structure in the parent of the hierachy is being chosen with the expectation that it'd be longest lived. But in the "daemon startup" case the child ends up being longest lived. Hopefully the other actions to becoming a daemon, such as disassociating itself with parent process (reparenting to process 1) and becoming a new process group mean that the relevant structures get migrated appropriately down into the child.

I'm also left wondering whether a simpler change from "linked list" to, eg, something indexed by page address, would have improved the situation dramatically without the same degree of code complexity, and hence bugs. (Eg, O(n) over 1M pages is non-trivial, O(log n) over 1M pages is almost trivial.)

Ewen

The case of the overly anonymous anon_vma

iabervon — Tue, 13 Apr 2010 18:59:08 +0000

The part I found most impressive was when he identified that something was crashing in the first iteration of a loop by looking at the register contents and assembly decode from the oops report. Where other people would have needed to look at memory in a debugger, he could just look at registers and infer where the bad value was coming from.

The case of the overly anonymous anon_vma

brouhaha — Tue, 13 Apr 2010 18:36:49 +0000

"He fixes radios by thinking!"

-- someone whose radio was repaired by Richard Feynman

The case of the overly anonymous anon_vma

dlang — Tue, 13 Apr 2010 17:49:49 +0000

it was primarily looking at the source and thinking about what was happening.

In the process three other bugs were found and fixed, and the section of code got significant documentation and cleanup improvements.

Linus was unable to reliably replicate the bug, so printf, kgdb, etc could not be used.

The case of the overly anonymous anon_vma

Trelane — Tue, 13 Apr 2010 17:42:39 +0000

Awesome. *This* is why I subscribe to lwn!

The case of the overly anonymous anon_vma

Wummel — Tue, 13 Apr 2010 17:31:32 +0000

It is even more awesome as he seems just to be looking at the source and guesses what could be wrong with it (or does Linus use printf() or even kgdb nowadays for debugging?).

The case of the overly anonymous anon_vma

clugstj — Tue, 13 Apr 2010 16:26:18 +0000

I am in awe of Linus' debugging abilities!