Re: freemaps

[Andrew Morton <akpm@digeo.com>]

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.

But:

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

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

- How does it play with non-linear mappings?
--
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/