Re: Minutes from Feb 21 LSE Call

Daniel Phillips
2003-02-26T20:47:12Z

On Wednesday 26 February 2003 17:02, Rik van Riel wrote:
> On Tue, 25 Feb 2003, Martin J. Bligh wrote:
> > It seemed, at least on the simple kernel compile tests that I did, that
> > all the long chains are not anonymous. It killed 95% of the space issue,
> > which given the simplicity of the patch was pretty damned stunning. Yes,
> > there's a pointer per page I guess we could kill in the struct page
> > itself, but I think you already have a better method for killing mem_map
> > bloat ;-)
>
> Also, with copy-on-write and mremap after fork, doing an
> object based rmap scheme for anonymous pages is just complex,
> almost certainly far too complex to be worth it, since it just
> has too many issues. Just read the patches by bcrl and davem,
> things get hairy fast.
>
> The pte chain rmap scheme is clean, but suffers from too much
> overhead for file mappings.

There is a lot of redundancy in the rmap chains that could be exploited. If
a pte page happens to reference a group of (say) 32 anon pages, then you can
set each anon page's page->index to its position in the group and let a
pte_chain node point at the pte of the first page of the group. You can then
find each page's pte by adding its page->index to the pte_chain node's pte
pointer. This allows a single rmap chain to be shared by all the pages in
the group.

This much of the idea is simple, however there are some tricky details to
take care of. How does a copy-on-write break out one page of the group from
one of the pte pages? I tried putting a (32 bit) bitmap in each pte_chain
node to indicate which pte entries actually belong to the group, and that
wasn't too bad except for doubling the per-link memory usage, turning a best
case 32x gain into only 16x. It's probably better to break the group up,
creating log2(groupsize) new chains. (This can be avoided in the common case
that you already know every page in the group is going to be copied, as with
a copy_from_user.) Getting rid of the bitmaps makes the single-page case the
same as the current arrangement and makes it easy to let the size of a page
be as large as the capacity of a whole pte page.

There's also the problem of detecting groupable clusters of pages, e.g., in
do_anon_page. Swap-out and swap-in introduce more messiness, as does mremap.
In the end, I decided it's not needed in the current cycle, but probably
worth investigating later.

My purpose in bringing it up now is to show that there are still some more
incremental gains to be had without needing radical surgery.

> As shown by Dave's patch, a hybrid system really is simple and
> clean, and it removes most of the pte chain overhead while still
> keeping the code nice and efficient.
>
> I think this hybrid system is the way to go, possibly with a few
> more tweaks left and right...

Emphatically, yes.

Regards,

Daniel