Re: [PATCH] anobjrmap 9 priority mjb tree

[Andrea Arcangeli <andrea@suse.de>]

On Thu, Apr 15, 2004 at 10:14:51AM -0700, Martin J. Bligh wrote:
> I still think my list-of-lists patch fixes the original problem, and is
> simpler ... I'll try to get it updated, and sent out.

it's a lot worse than the prio-tree IMHO, when a new range is generated
you've to loop all over the vmas etc... it's O(N) stuff for certain ops,
prio-tree is O(log(N)) for all.

If your object is to be able to use RCU (and implementing a RCU
prio-tree is going to be extremely complicated) you can attempt a
prio-skip-list, that would be a skip-list (that still provides O(log(N))
but that uses lists everywhere so that you can more easily create a
RCU-prio-skip-list, though I didn't even think if the range-lookup can
be implemented reasonably easily on top of a skip-list to create the
prio-skip-list).

but even if we could create the rcu-prio-skip-list (that would solve all
complexity issues like the prio-tree and it would allow lockless lookups
too [unlike prio-tree]) you'd still have to deal with the mess of
freeing vmas with rcu, that would cause everything else over the
vma to be freed with rcu too, mm, pgds etc... that would require quite
some changes, at the very least to be able to garbage collect the mm,pgd
from the vma free operations. I doubt it worth it, for the fast path you
cannot go lockless anyways, the lockless is only for the readonly
operations, and the readonly are the only unlikely ones (namely only
truncate and paging). So it's overdesign.