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
another GENERIC_PRIO_TREE.

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.

Rajesh
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/