Messages in this thread | | | Date | Fri, 16 Apr 2004 00:40:05 +0200 | From | Andrea Arcangeli <> | Subject | Re: [PATCH] anobjrmap 9 priority mjb tree |
| |
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. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |