Re: [RFC] Generalized prio_tree, revisited

[Rajesh Venkatasubramanian <vrajesh@umich.edu>]

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
> (abiss.sourceforge.net), 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.

Thanks,
Rajesh