Re: freemaps

[Ingo Molnar <mingo@elte.hu>]

On Sun, 15 Dec 2002, Andrew Morton wrote:

> Ingo Molnar wrote:
> > 
> > ...
> > another approach might be to maintain some sort of tree of holes.
> 
> This one, I'd suggest.  If we're going to fix this we may as
> well fix it right.  Otherwise there will always be whacky failure
> modes.
> 
> Trees are tricky, because we don't like to recur.
> 
> I expect this could be solved with two trees:
> 
> - For searching, a radix-tree indexed by hole size.  A list
>   of same-sized holes at each leaf.
> 
> - For insertion (where we must perform merging) an rbtree.

yes. I suspect this is close to what Andrea has/had in mind?

> But:
> 
> - Do we need to keep the lists of same-sized holes sorted by
>   virtual address, to avoid fragmentation?

the best anti-fragmentation technique is i guess what we have now: to use
the smallest matching hole at the lowest possible address. I think we
should give up strong anti-fragmentation techniques only once 32-bit
address spaces have become a distant memory, definitely not these days,
when the problems created by the limits of the 32-bit address space are
probably at their peak point in history.

but, before we go forward, i'd really suggest to run _real_ tests. The
free-area cache i added was to address one specific real-life workload.  
Frederic's test i dont know. One area i'd suspect we still suck somewhat
are the JITs and the memory protectorsm, but the loss due to the free-area
searching has to be quantified. Obviously, until trees are introduced
there will always be regressions.

> - Do all mm's incur all this stuff, or do we build it all when
>   some threshold is crossed?

we had some sort of threshold ages ago - i'd rather have a fast
constructor for this stuff instead of trying to hide the costs by cutting
off the small-size cases. I think basically everything but benchmarks will
have more than just a few mappings.

> - How does it play with non-linear mappings?

nonlinear mappings do not care about the structure of vmas (and the
structure of inverse vmas) - they are special types of vmas.

	Ingo


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/