Re: [RFC] 2.3/4 VM queues idea

Jamie Lokier
2000-05-26T11:38:12Z

Matthew Dillon wrote:
> 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)

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.

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

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

> 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