Re: [RFC] Generalized prio_tree, revisited

From: Rajesh Venkatasubramanian
Date: Thu Dec 16 2004 - 06:21:22 EST

Werner Almesberger wrote:
did you have a chance to look at the prio_tree generalization ?

I admit I haven't gone through the patch carefully yet. Overall
it looks good except for a problem which bothers me. The "raw"
prio_tree can only handle unique intervals, i.e., we cannot
insert two intervals with the same indices. Check vm_set.head
and vma_prio_tree_* functions to see how multiple vmas with
identical indices are handled.

There are currently no in-tree users of the generalized prio_tree,
but an example of one can be found in the elevator code of ABISS
(, where it's used to detect overlapping
requests, which in turn is needed to improve barrier handling in
the elevator.

Maybe in your case you don't have to worry about storing multiple
identical intervals. However, if we are generalizing prio_tree then
we have to consider that, I guess. This is similar to map and multi_map
in C++. I _guess_ in prio_tree case we will be using the multi_
variant more often. So, I was thinking something like this:

struct raw_prio_tree_node {}
/* same as in your patch */
struct unique_prio_tree_node {}
/* same as prio_tree_node in your patch */
struct prio_tree_node {}
/* somthing similar to shared in vm_area_struct */

Jens has also indicated interest in putting overlap
handling into the general block IO layer.

I wish we could have a patch using the generlized prio_tree when
we propose to merge the generalized prio_tree code.

Are there any standard benchmarks I could run to show how/if this
affects VMA performance ? I'd be surprised if there was much of a
change, but you never know.

I don't think the performance drop will be measurable.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at