Re: userspace pagecache management tool

[Rik van Riel <riel@redhat.com>]

Andrew Morton wrote:
> On Sat, 03 Mar 2007 20:56:27 -0500 Rik van Riel <riel@redhat.com> wrote:
> 
>> Andrew Morton wrote:
>>
>>>>> Doing a refault thing would help a bit, but stops working at a certain point.
>>>> At what point does it stop working?
>>> We need to store that this-page-got-reclaimed info somewhere.  I don't know
>>> how space-efficient that is.  Did anyone ever do an implementation?
>> One 32 bit word per evicted page that we keep track of.
> 
> ok...
> 
> I wonder if we really need a new data structure to track that.  I mean,
> once a file-backed (or indeed swapcache) page has been reclaimed, its
> radix-tree slot is just sitting there with zeroes in it, asking us to reuse
> that space for something interesting, no?
> 
> Of course, if all 64 pages in a radix-tree node get removed, we'll
> currently free the node itself.  We could stop doing that, but the effects
> of that might be pretty bad sometimes.  Instead, it sounds sensible to
> populate the now-null slot in the parent radix-tree node with an
> average/max/min/per-child-bitmap/whatever of the metrics for the 64
> non-resident pages which that non-leaf slot represents.  So as the period
> since a single page got evicted increases and increases, our information
> about its state becomes less and less accurate.
> 
> If that inaccuracy is a problem then perhaps we could defer the collapsing
> of a now-empty node into its parent in some manner.

We know exactly how far to defer that collapsing, too.

We know at what rate we rotate through the active list,
and the size of the active list.

We also know the rate at which we reclaim pages, and
the size of the inactive list.

Combine the two, and you have an idea roughly how many
page faults there are between the accesses to the coldest
page on the active list.

We don't have to keep the evicted page history beyond
that point, because pages that get refaulted after such
a long interval have a longer inter-reference distance
and should go onto the inactive list - ie. the default
list for unknown pages.

>> If you can find holes in http://linux-mm.org/PageReplacementDesign
>> please let me know :)
> 
> That all looks pretty non-crazy and implementable to me.  Alas, getting the
> stuff written and working is 1% of the effort.  The rest is the nasty hunt
> for new corner-cases and general productisation hassle.  But if initial
> results show benefit, I expect we could manage all that.

True, but I've looked through a few hundred VM bugzillas
to validate the design against all the common corner cases,
all the way from RHEL3 (which also has split anon/file
lists) through today.

I'm trying to keep the known-good bits of our policy as
much as possible, introducing big changes only for those
corner cases that plagued multiple VMs in the past.

-- 
Politics is the struggle between those who want to make their country
the best in the world, and those who believe it already is.  Each group
calls the other unpatriotic.