The case of the overly anonymous anon

The case of the overly anonymous anon_vma

Posted Apr 24, 2010 20:33 UTC (Sat) by efexis (guest, #26355)
In reply to: The case of the overly anonymous anon_vma by ewen
Parent article: The case of the overly anonymous anon_vma

"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.

(Log in to post comments)

The case of the overly anonymous anon_vma

Posted Apr 24, 2010 21:08 UTC (Sat) by ewen (subscriber, #4772) [Link]

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

Posted Apr 24, 2010 21:46 UTC (Sat) by efexis (guest, #26355) [Link]

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

Posted Apr 24, 2010 22:21 UTC (Sat) by ewen (subscriber, #4772) [Link]

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