2.3/4 VM queues idea
All right! I think your spec is coming together nicely! The
multi-queue approach is the right way to go (for the same reason FBsd took that approach). The most important aspect of using a multi-queue design is to *not* blow-off the page weighting tests within each queue. Having N queues alone is not fine enough granularity, but having N queues and locating the lowest (in FreeBSD's case 0) weighted pages within a queue is the magic of making it work well.
I actually tried to blow off the weighting tests in FreeBSD, even just a little, but when I did FreeBSD immediately started to stall as the load increased. Needless to say I threw away that patchset :-).
I have three comments:
* On the laundry list. In FreeBSD 3.x we laundered pages as we went
through the inactive queue. In 4.x I changed this to a two-pass
algorithm (vm_pageout_scan() line 674 vm/vm_pageout.c around the
rescan0: label). It tries to locate clean inactive pages in pass1, and if there is still a page shortage (line 927 vm/vm_pageout.c, the launder_loop conditional) we go back up and try again, this time laundering pages.
There is also a heuristic prior to the first loop, around line 650 ('Figure out what to do with dirty pages...'), where it tries to figure out whether it is worth doing two passes or whether it should just start laundering pages immediately.
* On page aging. This is going to be the most difficult item for you
to implement under linux. In FreeBSD the PV entry mmu tracking structures make it fairly easy to scan *physical* pages then check whether they've been used or not by locating all the pte's mapping them, via the PV structures.
In linux this is harder to do, but I still believe it is the right way to do it - that is, have the main page scan loop scan physical pages rather then virtual pages, for reasons I've outlined in previous emails (fairness in the weighting calculation).
(I am *not* advocating a PV tracking structure for linux. I really hate the PV stuff in FBsd).
* On write clustering. In a completely fair aging design, the pages you extract for laundering will tend to appear to be 'random'. Flushing them to disk can be expensive due to seeking.
Two things can be done: First, you collect a bunch of pages to be laundered before issuing the I/O, allowing you to sort the I/O (this is what you suggest in your design ideas email). (p.p.s. don't launder more then 64 or so pages at a time, doing so will just stall other processes trying to do normal I/O).
Second, you can locate other pages nearby the ones you've decided to launder and launder them as well, getting the most out of the disk seeking you have to do anyway.
The first item is important. The second item will help extend the life of the system in a heavy-load environment by being able to sustain a higher pagout rate.
In tests with FBsd, the nearby-write-clustering doubled the pageout rate capability under high disk load situations. This is one of the main reasons why we do 'the weird two-level page scan' stuff.
(ok to reprint this email too!)
-Matt
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 11 lines · Matthew Dillon
All right! I think your spec is coming together nicely! The
multi-queue approach is the right way to go (for the same reason FBsd took that approach). The most important aspect of using a multi-queue design is to *not* blow-off the page weighting tests within each queue. Having N queues alone is not fine enough granularity, but having N queues and locating the lowest (in FreeBSD's case 0) weighted pages within a queue is the magic of making it work well.I actually tried to blow off the weighting tests in FreeBSD, even just a little, but when I did FreeBSD immediately started to stall as the load increased. Needless to say I threw away that patchset :-).
OK, I'll look at implementing this in Linux as well. Maybe it won't work due to the virtual page scanning, but I'll look into it and try a few things. This change should be relatively easy to make.
Quoted 10 lines
I have three comments:
* On the laundry list. In FreeBSD 3.x we laundered pages as we went
through the inactive queue. In 4.x I changed this to a two-pass
algorithm (vm_pageout_scan()line 674vm/vm_pageout.caround the
rescan0: label). It tries to locate clean inactive pages in pass1, and if there is still a page shortage (line 927vm/vm_pageout.c, thelaunder_loopconditional) we go back up and try again, this time laundering pages.
Quoted 4 lines
There is also a heuristic prior to the first loop, around line 650 ('Figure out what to do with dirty pages...'), where it tries to figure out whether it is worth doing two passes or whether it should just start laundering pages immediately.
Another good idea to implement. I don't know in how far it'll interfere with the "age one second" idea though...
(maybe we want to have the inactive list "4 seconds big" so we can implement this FreeBSD idea and still keep our second of aging?)
Quoted 6 lines
* On page aging. This is going to be the most difficult item for you
to implement under linux. In FreeBSD the PV entry mmu tracking structures make it fairly easy to scan *physical* pages then check whether they've been used or not by locating all the pte's mapping them, via the PV structures.
Quoted 7 lines
In linux this is harder to do, but I still believe it is the right way to do it - that is, have the main page scan loop scan physical pages rather then virtual pages, for reasons I've outlined in previous emails (fairness in the weighting calculation).
(I am *not* advocating a PV tracking structure for linux. I really hate the PV stuff in FBsd).
This is something for the 2.5 kernel. The changes involved in doing this are just too invasive right now...
Quoted 10 lines
* On write clustering. In a completely fair aging design, the pages you extract for laundering will tend to appear to be 'random'. Flushing them to disk can be expensive due to seeking.
Two things can be done: First, you collect a bunch of pages to be laundered before issuing the I/O, allowing you to sort the I/O (this is what you suggest in your design ideas email). (p.p.s. don't launder more then 64 or so pages at a time, doing so will just stall other processes trying to do normal I/O).
Quoted 3 lines
Second, you can locate other pages nearby the ones you've decided to launder and launder them as well, getting the most out of the disk seeking you have to do anyway.
Virtual page scanning should provide us with some of these benefits. Also, we'll allocate the swap entry at unmapping time and can make sure to unmap virtually close pages at the same time so they'll end up close to each other in the inactive queue.
This isn't going to be as good as it could be, but it's probably as good as it can get without getting more invasive with our changes to the source tree...
regards,
Rik
--
The Internet is not a network of computers. It is a network of people. That is its real strength.
Wanna talk about the kernel? irc.openprojects.net / #kernelnewbies
http://www.conectiva.com/ http://www.surriel.com/
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Virtual page scanning will help with clustering, but unless you already have a good page candidate to base your virtual scan on you will not be able to *find* a good page candidate to base the clustering around. Or at least not find one easily. Virtual page scanning has severe scaleability problems over physical page scanning. For example, what happens when you have an oracle database running with a hundred independant (non-threaded) processes mapping 300MB+ of shared memory?
On the swap allocation -- I think there are several approaches to this problem, all equally viable. If you do not do object clustering for pageouts then allocating the swap at unmap time is viable -- due to the time delay between unmap and the actual I/O & page-selection for cleaning, your pageouts will be slower but you *will* get locality of reference on your pageins (pageins will be faster).
If you do object clustering then you get the benefit of both worlds. FreeBSD delays swap allocation until it actually decides to swap something, which means that it can take a collection of unrelated pages to be cleaned and assign contiguous swap to them. This results in a very fast, deterministic pageout capability but, without clustering, there will be no locality of reference for pageins. So pageins would be slow.
With clustering, however, the at-swap-time allocation tends to have more locality of reference due to there being additional nearby pages selected from the objects in the mix. It still does not approach the performance you can get from an object-oriented swap allocation scheme, but at least it would no longer be considered 'slow'.
So it can be a toss-up. I don't think *anyone* (linux, freebsd, solaris, or anyone else) has yet written the definitive swap allocation algorithm!
-Matt Matthew Dillon <[email protected]>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 20 lines · Matthew Dillon
:> Two things can be done: First, you collect a bunch of pages to be :> laundered before issuing the I/O, allowing you to sort the I/O :> (this is what you suggest in your design ideas email). (p.p.s. :> don't launder more then 64 or so pages at a time, doing so will just :> stall other processes trying to do normal I/O). :> :> Second, you can locate other pages nearby the ones you've decided to :> launder and launder them as well, getting the most out of the disk :> seeking you have to do anyway.:
:Virtual page scanning should provide us with some of these :benefits. Also, we'll allocate the swap entry at unmapping :time and can make sure to unmap virtually close pages at :the same time so they'll end up close to each other in the :inactive queue.
:
:This isn't going to be as good as it could be, but it's :probably as good as it can get without getting more invasive :with our changes to the source tree...
Quoted 8 lines
Virtual page scanning will help with clustering, but unless you already have a good page candidate to base your virtual scan on you will not be able to *find* a good page candidate to base the clustering around. Or at least not find one easily. Virtual page scanning has severe scaleability problems over physical page scanning. For example, what happens when you have an oracle database running with a hundred independant (non-threaded) processes mapping 300MB+ of shared memory?
Ohhh definately. It's just that coding up the administrative changes required to support this would be too big a change for Linux 2.4...
Quoted 2 lines
So it can be a toss-up. I don't think *anyone* (linux, freebsd, solaris, or anyone else) has yet written the definitive swap allocation algorithm!
We still have some time. There's little chance of implementing it in Linux before kernel version 2.5, so we should have some time left to design the "definitive" algorithm.
For now I'll be focussing on having something decent in kernel 2.4, we really need it to be better than 2.2. Keeping the virtual scanning but combining it with a multi-queue system for the unmapped pages (with all mapped pages residing in the active queue) should at least provide us with a predictable, robust and moderately good VM subsystem for the next stable kernel series.
regards,
Rik
--
The Internet is not a network of computers. It is a network of people. That is its real strength.
Wanna talk about the kernel? irc.openprojects.net / #kernelnewbies
http://www.conectiva.com/ http://www.surriel.com/
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 5 lines · Matthew Dillon
Virtual
page scanning has severe scaleability problems over physical page scanning. For example, what happens when you have an oracle database running with a hundred independant (non-threaded) processes mapping 300MB+ of shared memory?
Actually you can make this scalable quite easily. I think it's
asymptotically equivalent to physical page scanning.
First, ensure the async. unmapper can limit the number of mapped ptes. Method: whenever the number of established ptes increases above a high water mark (e.g. due to a page fault), invoke the unmapper synchronously to push the number below a low water mark. (Both marks can be the same).
Second, make the scanner scale independently of the virtual addresses used. Method: store boundary tags in the /unused/ ptes so that scanning skips unused ptes. Ok, this can have fiddly interactions with not-present swap entries.
In this way, the work required to scan _all_ mapped pages can be strictly bounded.
cheers,
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
:
:Matthew Dillon wrote:
:> Virtual :> page scanning has severe scaleability problems over physical page :> scanning. For example, what happens when you have an oracle database :> running with a hundred independant (non-threaded) processes mapping :> 300MB+ of shared memory?
:
:Actually you can make this scalable quite easily. I think it's
:asymptotically equivalent to physical page scanning.
:
:First, ensure the async. unmapper can limit the number of mapped :ptes. Method: whenever the number of established ptes increases :above a high water mark (e.g. due to a page fault), invoke the unmapper :synchronously to push the number below a low water mark. (Both marks :can be the same).
:
:Second, make the scanner scale independently of the virtual addresses :used. Method: store boundary tags in the /unused/ ptes so that :scanning skips unused ptes. Ok, this can have fiddly interactions with :not-present swap entries.
:
:In this way, the work required to scan _all_ mapped pages can be :strictly bounded.
:
:cheers,
:-- Jamie
Yes, but at an unreasonable cost: Artificially limiting the number of discrete processes able to share a given amount of memory. Any reasonable limit would still be an order of magnitude more expensive then a physical page scan.
And even with limits you still wind up with extremely non-deterministic scanning.
I'm not advocating a physical page scan for the current linux kernel, it just isn't designed for it, but I would argue that doing a physical page scan should be considered after you get past your next release.
-Matt Matthew Dillon <[email protected]>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 4 lines · Matthew Dillon
Yes, but at an unreasonable cost: Artificially limiting the number of discrete processes able to share a given amount of memory. Any reasonable limit would still be an order of magnitude more expensive then a physical page scan.
I disagree. The "amount of sharing" scan-time overhead is there whether you do a physical or virtual scan. For a physical scan, if you have a lot of sharing then you look at a lot of ptes per page.
One possible goal is to limit the total number of mapped ptes in the system. You can still permit a lot of sharing: the number does not have to be limited per task or per mm.
Quoted 2 lines
And even with limits you still wind up with extremely non-deterministic scanning.
How so? You're only scanning currently mapped ptes, and one goal is to keep that number small enough that you can gather good LRU stats of page usage. So the set of mapped ptes at any time should reasonably reflect current usage. If current usage is chewing up a lot of pages, you simply get a lot of page faults and very good LRU stats :-) I don't see how this is particularly non-deterministic.
Quoted 3 lines
I'm not advocating a physical page scan for the current linux kernel, it just isn't designed for it, but I would argue that doing a physical page scan should be considered after you get past your next release.
Agreed. Fwiw, I rather like the idea of physical scanning. A smaller, simpler feedback loop should show much less pathological behaviour with unusual loads.
Fwiw, with COW address_spaces (I posted an article a couple of weeks ago explaining) it should be fairly simple to find all the ptes for a given page without the space overhead of pte chaining.
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 10 lines · Jamie Lokier
Quoted 4 lines · Matthew Dillon
Yes, but at an unreasonable cost: Artificially limiting the number of discrete processes able to share a given amount of memory. Any reasonable limit would still be an order of magnitude more expensive then a physical page scan.
I disagree. The "amount of sharing" scan-time overhead is there whether you do a physical or virtual scan. For a physical scan, if you have a lot of sharing then you look at a lot of ptes per page.
Not really. If there are enough inactive pages, the active pages will never be scanned. And when the active pages get scanned, chances are that only a few of them (the ones near the "end" of the queue) need to be scanned.
With virtual scanning, OTOH, you'll need to scan all pages since you have no "candidate list" of which pages are more likely to be suitable candidates for swapout.
Quoted 3 lines
One possible goal is to limit the total number of mapped ptes in the system. You can still permit a lot of sharing: the number does not have to be limited per task or per mm.
No. The goal is to have an efficient memory management system which supports running a lot of applications efficiently.
This idea would place an artificial limit on the number of shared pages between processes. If your particular workload needs more you'll spend your time handling soft pagefaults and finding pages to unmap. Even though the machine has enough physical memory to hold all the pages (and their pte mappings) and there is no memory load.
If we do NOT have such an artificial restriction, then we could end up with slightly more scanning overhead when we have memory pressure, but at least the system would run fine in situations where we do have enough memory.
Quoted 6 lines
Quoted 2 lines
And even with limits you still wind up with extremely non-deterministic scanning.
How so? You're only scanning currently mapped ptes, and one goal is to keep that number small enough that you can gather good LRU stats of page usage.
Page aging may well be cheaper than continuously unmapping ptes (including tlb flushes and cache flushes of the page tables) and softfaulting them back in.
Quoted 4 lines
Fwiw, with COW
address_spaces(I posted an article a couple of weeks ago explaining) it should be fairly simple to find all the ptes for a given page without the space overhead of pte chaining.
But what if you have a page which is 1) mapped in multiple addresses by different apps and 2) COW shared by subsets of those multiple apps?
We still need pte chaining or something similar.
regards,
Rik
--
The Internet is not a network of computers. It is a network of people. That is its real strength.
Wanna talk about the kernel? irc.openprojects.net / #kernelnewbies
http://www.conectiva.com/ http://www.surriel.com/
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Another big difference is that when you scan by physical page, you can collect a whole lot of information together to help you make the decision on how the adjust the weight.
When you scan by physical page, then locate the VM mappings for that page, you have:
* a count of the number of mappings
* a count of how many of those referenced the page since the last check.
* more determinism (see below)
When you scan by virtual page, then locate the physical mapping:
* you cannot tell how many other virtual mappings referenced the page (short of checking, at which point you might as well be scanning by physical page)
* you have no way of figuring out how many discrete physical pages your virtual page scan has covered. For all you know you could scan 500 virtual mappings and still only have gotten through a handful of physical pages. Big problem!
* you have much less information available to make the decision on how to adjust the weight.
:> How so? You're only scanning currently mapped ptes, and one :> goal is to keep that number small enough that you can gather :> good LRU stats of page usage.
:
:Page aging may well be cheaper than continuously unmapping ptes :(including tlb flushes and cache flushes of the page tables) and :softfaulting them back in.
It's definitely cheaper. If you unmap a page and then have to take a page fault to get it back, the cost is going to be roughly 300 instructions plus other overhead.
Another example of why physical page scanning is better then virtual page scanning: When there is memory pressure and you are scanning by physical page, and the weight reaches 0, you can then turn around and unmap ALL of its virtual pte's all at once (or mark them read-only for a dirty page to allow it to be flushed). Sure you have to eat cpu to find those virtual pte's, but the end result is a page which is now cleanable or freeable.
Now try this with a virtual scan: You do a virtual scan, locate a page you decide is idle, and then... what? Unmap just that one instance of the pte? What about the others? You would have to unmap them too, which would cost as much as it would when doing a physical page scan *EXCEPT* that you are running through a whole lot more virtual pages during the virtual page scan to get the same effect as with the physical page scan (when trying to locate idle pages). It's the difference between O(N) and O(N^2). If the physical page queues are reasonably well ordered, its the difference between O(1) and O(N^2).
-Matt
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 8 lines · Matthew Dillon
When you scan by physical page, then locate the VM mappings for that page, you have:
* a count of the number of mappings
* a count of how many of those referenced the page since the last check.
* more determinism (see below)
Quoted 5 lines
When you scan by virtual page, then locate the physical mapping:
* you cannot tell how many other virtual mappings referenced the page (short of checking, at which point you might as well be scanning by physical page)
But you can at least accumulate the info. If it's just a question of bumping a decaying "page referenced recently" measure, than with virtual scanning you bump it more often (if it's being used in many places); with physical scanning you bump it more in one go.
Quoted 4 lines
* you have no way of figuring out how many discrete physical pages your virtual page scan has covered. For all you know you could scan 500 virtual mappings and still only have gotten through a handful of physical pages. Big problem!
Counters in struct page.
Quoted 7 lines
Another example of why physical page scanning is better then virtual page scanning: When there is memory pressure and you are scanning by physical page, and the weight reaches 0, you can then turn around and unmap ALL of its virtual pte's all at once (or mark them read-only for a dirty page to allow it to be flushed). Sure you have to eat cpu to find those virtual pte's, but the end result is a page which is now cleanable or freeable.
That's obviously a _big_ advantage under memory pressure. A fast feedback loop, so much more robust dynamics.
Quoted 9 lines
Now try this with a virtual scan: You do a virtual scan, locate a page you decide is idle, and then... what? Unmap just that one instance of the pte? What about the others? You would have to unmap them too, which would cost as much as it would when doing a physical page scan *EXCEPT* that you are running through a whole lot more virtual pages during the virtual page scan to get the same effect as with the physical page scan (when trying to locate idle pages). It's the difference between O(N) and O(N^2). If the physical page queues are reasonably well ordered, its the difference between O(1) and O(N^2).
[ Virtual is not O(N^2) if you've limited the number of ptes mapped, but I agree the fixed overhead of that is rather high. ]
Conclusion: _Everyone_ agrees that physical page scanning is better in every way except one: Linux 2.4 wants to be released :-)
But, given its conceptual simplicity, I wonder if it isn't worth trying to implement physical scanning anyway? It would simplify the paging dynamics; I expect tuning etc. would be easier and more robust. And Rik's queues proposal is more or less orthogonal. We need good queues however pages are freed up.
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 4 lines · Jamie Lokier
Fwiw, with COW
address_spaces(I posted an article a couple of weeks ago explaining) it should be fairly simple to find all the ptes for a given page without the space overhead of pte chaining.
Davem's anon area stuff already implements a large chunk of what is needed.
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 5 lines · Stephen C. Tweedie
Quoted 3 lines
Fwiw, with COW
address_spaces(I posted an article a couple of weeks ago explaining) it should be fairly simple to find all the ptes for a given page without the space overhead of pte chaining.Davem's anon area stuff already implements a large chunk of what is needed.
Agreed. I looked at that code though and it seemed very... large. I think COW address_space gets the same results with less code. Fast, too. I know what I've got to do to prove it :-)
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 4 lines · Jamie Lokier
Agreed. I looked at that code though and it seemed very... large. I think COW
address_spacegets the same results with less code. Fast, too. I know what I've got to do to prove it :-)
How will it deal with fork() cases where the child starts mprotecting arbitrary regions, so that you have completely independent vmas all sharing the same private pages?
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 7 lines · Stephen C. Tweedie
Quoted 3 lines
Agreed. I looked at that code though and it seemed very... large. I think COW
address_spacegets the same results with less code. Fast, too. I know what I've got to do to prove it :-)How will it deal with
fork()cases where the child starts mprotecting arbitrary regions, so that you have completely independent vmas all sharing the same private pages?
Each VMA points to an address_space, and each private address_space can have a parent. Pages that aren't hashed in a private address space are found in the parent's address space.
When a VMA is cloned for fork(), they have the same address_space which is now marked as requiring COW. When you modify a page in either, a new space is created which contains the modified pages and the appropriate VMA refers to the new space. Now if it was from a file there were page modifications at all stages by everyone, you have a small tree of 4 address_spaces:
1 - underlying file
|
2 - privately modified pages from the file,
/ \ shared by child & parent
/ \
pages only seen by 3 4 pages only seen by the child
the parent
The beauty here is that the sharing structure is quite explicit.
Note that stacked address_spaces are only created when they actually contain pages, and page counters are used to collapse layers when appropriate.
mprotect & partial munmap are fine. What happens here is that the VMAs created by those functions refer to the same address_space -- this time without COW semantics. For this, all VMAs sharing an address_space that COW as a single unit are linked together. A modification to any one that COWs its address_space updates all its linked VMAs.
You didn't mention it, but that leaves mremap. This is a fiddly one! mremaps that simply expand or shrink a segment are fine by themselves. mremaps that move a segment are fine by themselves. But the combination can cause page offset values to duplicate for different pages.
So mremap needs a fixup to create new address_spaces in certain unusual cases and rehash pages when that happens. I don't think those cases occur in any usual use of mremap.
thanks,
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 1 line · Jamie Lokier
You didn't mention it, but that leaves mremap. This is a fiddly one!
Yes, we know this. :-)
Quoted 2 lines
mremaps that simply expand or shrink a segment are fine by themselves. mremaps that move a segment are fine by themselves.
No, they are not fine. When you move a segment, you end up with pages which have the same offset but are now at a different VA. What that means is that you have no way of finding out, for a given physical page, what the VA of all of the mappings of that page may be. That means that you have no way to find all of the ptes short of scanning all the vmas in order.
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
:Hi,
:
:On Fri, May 26, 2000 at 04:31:29PM +0200, Jamie Lokier wrote:
:
:> You didn't mention it, but that leaves mremap. This is a fiddly one! :
:Yes, we know this. :-)
:
:> mremaps that simply expand or shrink a segment are fine by themselves. :> mremaps that move a segment are fine by themselves.
:
:No, they are not fine. When you move a segment, you end up with pages :which have the same offset but are now at a different VA. What that :means is that you have no way of finding out, for a given physical page, :what the VA of all of the mappings of that page may be. That means that :you have no way to find all of the ptes short of scanning all the vmas :in order.
:
:--Stephen
Basically you have two choices: Either track all the mappings to an underlying object in such a way that you can locate all the potential (object,index) -> (process,va) mappings, or you can track the PTE's themselves as FreeBSD does with its PV entry junk.
I personally hate the PV entry junk in FreeBSD. It's fast, but it has a lot of memory overhead.
I would not be afraid of adding appropriate linked-list fields to your various tracking structures to be able to locate the potential mappings more easily, and I'll bet dollars to donoughts that you would be able to refine the scheme to make it just as fast as our PV entry scheme but without the overhead.
In anycase, locating the pte's would go like this:
* physical page candidate
* direct knowledge of (object,index) for physical page (any given physical page exists in just one VM object. I'm using a FreeBSD style VM object as a reference here).
* scan mapping structures linked to the object for mappings that cover (index).
* Lookup the pte associated with each such mapping (the pte may or may not exist in the actual page table, depending on whether it has been faulted or not, or overloaded by another VM object layer).
* done (you are able to locate all the pte's associated with a physical page)
In FreeBSD, locating the pte's goes like this:
* physical page candidate
* (direct knowledge of (object,index) for physical page, but FreeBSD doesn't use it for this particular operation).
* scan linked list of PV's based in physical page structure.
* each PV represents a *mapped* pte.
(Which is a lot faster and less stressful on the cache, but which also eats a truely disgusting amount of memory having to have a PV entry structure for each pte).
-Matt Matthew Dillon <[email protected]>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 9 lines · Stephen C. Tweedie
Quoted 2 lines
mremaps that simply expand or shrink a segment are fine by themselves. mremaps that move a segment are fine by themselves.
No, they are not fine. When you move a segment, you end up with pages which have the same offset but are now at a different VA. What that means is that you have no way of finding out, for a given physical page, what the VA of all of the mappings of that page may be. That means that you have no way to find all of the ptes short of scanning all the vmas in order.
That's ok. VA == vma->pgoff + page_offset. Move a vma and that's still true. The ptes are found by looking at the list of all vmas referring to all the address_spaces that refer to a page.
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 3 lines · Jamie Lokier
That's ok. VA ==
vma->pgoff+page_offset. Move a vma and that's still true. The ptes are found by looking at the list of all vmas referring to all theaddress_spacesthat refer to a page.
And that is _exactly_ the problem --- especially with heavy mprotect() use, processes can have enormous numbers of vmas. Electric fence and distributed shared memory/persistent object stores are the two big, obvious cases here.
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
:Hi,
:
:On Fri, May 26, 2000 at 06:36:40PM +0200, Jamie Lokier wrote:
:
:> That's ok. VA == vma->pgoff + page_offset. Move a vma and that's still :> true. The ptes are found by looking at the list of all vmas referring :> to all the address_spaces that refer to a page.
:
:And that is _exactly_ the problem --- especially with heavy mprotect() :use, processes can have enormous numbers of vmas. Electric fence and :distributed shared memory/persistent object stores are the two big, :obvious cases here.
:
:--Stephen
I don't think this will be a problem. FreeBSD's vm_map_entry scheme is very similar and we found it to be fairly trivial to optimize adjacent entries in many cases for both madvise() and mprotect(). In fact, half the madvise() calls (such as MADV_WILLNEED, MADV_DONTNEED, and MADV_FREE) have no effect on the vm_map_entry (VMA equivalent) at all, they operate directly on the associated pages.
The only fragmentation issue I've ever seen with our vm_map_entry scheme occurs when you use mprotect() to create a guard page for each thread's stack. The creation of the guard page forces the vm_map_entry to be broken up, preventing the vm_map_entries for adjacent stack segments from being collapsed together into a single entry.
You wind up with two vm_map_entry's per thread. Not really a problem, but somewhat of an eyesore.
In regards to overhead, anything that collects a bunch of pages together (e.g. vm_map_entry, vm_object under FBsd, VMA in Jamie's scheme) simply does not create a memory overhead issue. None at all. It's the things that eat memory on a per-page basis that get annoying.
-Matt Matthew Dillon <[email protected]>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 4 lines · Matthew Dillon
In regards to overhead, anything that collects a bunch of pages together (e.g.
vm_map_entry,vm_objectunder FBsd, VMA in Jamie's scheme) simply does not create a memory overhead issue. None at all. It's the things that eat memory on a per-page basis that get annoying.
Stephen's point is that there are applications which use mprotect() on a per-page basis. Some garbage collectors for example, to track dirtied pages.
And having to scan hundreds of vmas to find one pte sucks :-)
But I addressed that a few minutes ago. In my scheme you don't have to scan lots of vmas to find that pte. Only one or two, or you can choose to increase that number while decreasing memory requirements a little.
-- Jamie
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
:Matthew Dillon wrote:
:> In regards to overhead, anything that collects a bunch of pages together :> (e.g. vm_map_entry, vm_object under FBsd, VMA in Jamie's scheme) :> simply does not create a memory overhead issue. None at all. It's :> the things that eat memory on a per-page basis that get annoying.
:
:Stephen's point is that there are applications which use mprotect() on a :per-page basis. Some garbage collectors for example, to track dirtied :pages.
:
:And having to scan hundreds of vmas to find one pte sucks :-) :
:But I addressed that a few minutes ago. In my scheme you don't have to :scan lots of vmas to find that pte. Only one or two, or you can choose :to increase that number while decreasing memory requirements a little. :
:-- Jamie
Hmm. I know apps which use madvise() to manage allocated/free pages efficiently, but not any that use mprotect(). The madvise() flags typically used effect the underlying pages directly and should not fragment the VMA's at all. In anycase, it's not a big deal because even if you did have to fragment the VMA's, you can still collapse adjacent entries together. i.e. if the garbage collector protects page 1 and then later on protects page 2 the same way, you still need only one VMA to represent both pages.
-Matt Matthew Dillon <[email protected]>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 3 lines · Matthew Dillon
Hmm. I know apps which use
madvise()to manage allocated/free pages efficiently, but not any that usemprotect().
Persistent and distributed data stores use it to mark existing pages as PROT_NONE, so that they can trap accesses to the data and perform the necessary locking to make the local storage consistent with the on-disk data (persistent object stores) or with other machines in the cluster (for distributed shared memory).
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 8 lines · Stephen C. Tweedie
Quoted 3 lines
That's ok. VA ==
vma->pgoff+page_offset. Move a vma and that's still true. The ptes are found by looking at the list of all vmas referring to all theaddress_spacesthat refer to a page.And that is _exactly_ the problem --- especially with heavy
mprotect()use, processes can have enormous numbers of vmas. Electric fence and distributed shared memory/persistent object stores are the two big, obvious cases here.
The stacked private address_spaces I described don't have to be shared between address_spaces in a single mm. You can have one per vma -- that's simple but maybe wasteful. Or one per several vmas. When you divide a single vma into zillions using mprotect(), you're free to split off new spaces to limit the number of vmas per space.
-- Jamie
Quoted 2 lines
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 4 lines · Jamie Lokier
The stacked private
address_spacesI described don't have to be shared betweenaddress_spacesin a single mm. You can have one per vma -- that's simple but maybe wasteful.
That's basically exactly what davem's stuff did.
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 5 lines · Stephen C. Tweedie
Quoted 3 lines
The stacked private
address_spacesI described don't have to be shared betweenaddress_spacesin a single mm. You can have one per vma -- that's simple but maybe wasteful.That's basically exactly what davem's stuff did.
Ok, I shall look more carefully at davem's code.
Is this the most recent one?:
Quoted 6 lines
Date: Wed, 17 May 2000 11:00:34 +0100 Subject: [[email protected]: my paging work] From: "Stephen C. Tweedie" <[email protected]>Hi,
Quoted 7 lines
Here's davem's page-based swapout snapshot. It's UNFINISHED + DANGEROUS
WILL_EAT_YOUR_DISK(his words!), but somebody may want to archive this and pick up on the work in 2.5.--Stephen
----- Forwarded message from "David S. Miller" <[email protected]> -----
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Hi,
Quoted 9 lines · Jamie Lokier
Quoted 5 lines · Stephen C. Tweedie
Quoted 3 lines
The stacked private
address_spacesI described don't have to be shared betweenaddress_spacesin a single mm. You can have one per vma -- that's simple but maybe wasteful.That's basically exactly what davem's stuff did.
Ok, I shall look more carefully at davem's code.
Is this the most recent one?:
Yes, I think he dropped it at this point.
--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
:Stephen C. Tweedie wrote:
:> > Agreed. I looked at that code though and it seemed very... large. :> > I think COW address_space gets the same results with less code. Fast, too. :> > I know what I've got to do to prove it :-)
:>
:> How will it deal with fork() cases where the child starts mprotecting :> arbitrary regions, so that you have completely independent vmas all :> sharing the same private pages?
:
:Each VMA points to an address_space, and each private address_space can :have a parent. Pages that aren't hashed in a private address space are :found in the parent's address space.
:
:When a VMA is cloned for fork(), they have the same address_space which :is now marked as requiring COW. When you modify a page in either, a new :space is created which contains the modified pages and the appropriate :VMA refers to the new space. Now if it was from a file there were page :modifications at all stages by everyone, you have a small tree of 4 :address_spaces:
:
: 1 - underlying file : | : 2 - privately modified pages from the file,
: / \ shared by child & parent
: / \
:pages only seen by 3 4 pages only seen by the child
:the parent
:
:The beauty here is that the sharing structure is quite explicit. :
:Note that stacked address_spaces are only created when they actually :contain pages, and page counters are used to collapse layers when :appropriate.
:...
This appears to be very close to what FreeBSD does with its vm_map_entry and vm_object structures. If you haven't read my article on how VM objects work in FreeBSD, you really should, because you are going to hit exactly the same problems. Ignore the linux jabs in the article :-) and skip to the 'VM objects' section.
http://www.daemonnews.org/200001/freebsd_vm.html
The article describes VM objects, which represent logical entities such
as files or anonymous memory areas. VM objects can be stacked to
implement private adderss spaces (MAP_PRIVATE mappings).
However, in FreeBSD a VM object represents a complete logical entity (such as a file), *NOT* a memory mapping. There is a separate structure called a vm_map_entry which is responsible for mapping portions of a
process's adderss space to portions of a VM object. Things like COW
flags and madvise() flags are stored in the vm_map_entry, not the vm_object. The actual function of doing a copy-on-write involves stacking a new anonymous-memory (swap-backed) VM object in front of the one that took the COW hit, based on the COW flag in the vm_map_entry. Once the vm_map_entry is repointed to the new 'top layer' for that process, the COW flag can be cleared. Write faults always occur in the top layer, so if you attempt to write to a page in a MAP_PRIVATE mapped file and that page cannot be found in the top level VM object (swap-backed anonymous memory object), it will be copied up from the lower level VM object (the one representing the actual file).
-Matt Matthew Dillon <[email protected]>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/
Quoted 8 lines · Stephen C. Tweedie
Quoted 4 lines · Jamie Lokier
Fwiw, with COW
address_spaces(I posted an article a couple of weeks ago explaining) it should be fairly simple to find all the ptes for a given page without the space overhead of pte chaining.Davem's anon area stuff already implements a large chunk of what is needed.
It would be cool if somebody could take the time and implement the rest of what's needed. I'm currently working at making page aging and deferred swapout work, so we have the basic mechanisms for aging the active pages and doing swapout from the inactive queue.
regards,
Rik
--
The Internet is not a network of computers. It is a network of people. That is its real strength.
Wanna talk about the kernel? irc.openprojects.net / #kernelnewbies
http://www.conectiva.com/ http://www.surriel.com/
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/