Re: [RFC] Generalize prio_tree (1/3)

From: Rajesh Venkatasubramanian
Date: Mon Nov 15 2004 - 16:19:53 EST

On Mon, 15 Nov 2004, Werner Almesberger wrote:

> Rajesh Venkatasubramanian wrote:
> > Again I don't like the following approach fully. I couldn't come
> > out with a clean generalization something like rb_tree code.
> Hmm, GET_INDEX/get_index grows and grows, and also generates a
> hotspot for patch collisions ...
> And what if we took the hit and moved the key into struct
> prio_tree_node ? struct vm_area_struct.shared.vm_set already is
> one word longer than vm_area_struct.shared.prio_tree_node, so
> half of the key is free (in terms of storage - the key updates
> when vm_pgoff, vm_end, or vm_start changes aren't free). The
> other half could also be made free (in terms of storage and
> processing) with a little tweaking, e.g. by adding
> ...
> union {
> unsigned long vm_pgoff;
> struct vm_set {
> unsigned long vm_pgoff;
> ...
> } vm_set;
> struct prio_tree_node prio_tree_node;
> }
> ...
> #define vm_pgoff shared.vm_pgoff
> (Untested. This kind of #define is of course risky, so it may be
> better to just rewrite all the accesses.)

I thought about this, but this will lead to a very intrusive patch.
We have to change the meaning of vm_start and vm_end or increase
the size of vm_area_struct.

> Then, we could have
> struct prio_tree_node {
> unsigned long r_index, h_index;
> ...
> };
> For the elevators, the keys (the "footprint" of a set of overlapping
> requests) are already stored as separate variables, so that could be
> migrated very easily, at no additional cost.

Why can't we have only 2 types of prio_tree. One VMA_PRIO_TREE and

struct generic_prio_tree_node {
unsigned long r_index, h_index;
struct prio_tree_node prio_tree_node;

That way all new users of prio_tree code will use the
generic_prio_tree_node if possible. Moreover, we can avoid
an intrusive patch.

I am only worried about the micro-performance loss due to
get_index in the hot-paths such as vma_prio_tree_insert.

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