Re: new allocation algorithm

["Stephen C. Tweedie" <sct@dcs.ed.ac.uk>]

Hi,

On Fri, 27 Mar 1998 09:30:40 -0800 (PST), Linus Torvalds
<torvalds@transmeta.com> said:

> The current scheme is fairly efficient and extremely stable, and gives
> good behaviour for the cases we _really_ care about (pageorders 0, 1 and
> to some degree 2). It comes reasonably close to working for the higher
> orders too, but they really aren't as critical..

Sorry to put a spanner in the works at this stage, but there's
something we haven't really considered yet in the page balancing.  The
aim I'm currently working towards is to eliminate free memory as much
as possible, by replacing "free" space with reserved, lazy-reclaimed
cache memory.  We ought to be able to maintain 5-10% memory in this
form with much less performance impact than we would have if that
memory was truly free, but the downside is that this nearly-free
memory is not on our free page lists and therefore we have no simple
way of assessing the fragmentation of the lazy-reclaimable pages.

Now, this is both a blessing and a curse.  The positive side is that
we can do what to some extent happens today, and keep as much memory
as possible on the lazy list in the blind hope that we will be able to
find free higher order pages when we need them by returning lazy pages
to the free list one by one.  The drawback is that we don't have an
easy way of suspending kswapd when we get enough free higher order
pages.

This is just an observation --- we cannot tune this stuff until it is
stable enough to integrate, but the impact on our free space
heuristics may be worth thinking about now.

--Stephen