Re: [RFC] tree-based bootmem

[Martin Mares <mj@ucw.cz>]

Hello!

> The beauty is in the implementation.  With a linked list implementation,
> you have an exhaustive search and and at-worst O(n) insertion and
> searching complexity.  We also don't end up with any clean way to say
> "memory a belongs to x".  This is where the segment tree comes in, a
> segment tree stores intervals: it is a binary tree where each node
> represents an interval from a to b.  We only need to store nodes that
> have allocated intervals of memory, and insertion is O(log n). 
> Searching is even easier as you just walk the intervals until we get to
> what we want.  Searching would be O(log(n+s)) where s is the number of
> segments we had to walk.  OK, you know this, but my point is its is
> quite applicable.  Besides a performance boost, we end up with a nice
> way to interface with other code to work with bootmem and I think that
> is the main benefit here.

Look at it from the other side: Compare a simple 50-line allocator based
on linked lists which is obviously correct and a complex allocator with
several hundreds lines of code which, although very fast and elegant,
is very far from being understandable in a couple of minutes. And believe
me, bugs in memory allocators are some of the worst to find.

On the other hand, well implemented segment trees might be much more useful for
other stuff, like the vm_area_struct lists.

				Have a nice fortnight
-- 
Martin `MJ' Mares   <mj@ucw.cz>   http://atrey.karlin.mff.cuni.cz/~mj/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
"I don't give a damn for a man that can only spell a word one way." -- M. Twain