lkml.org 
[lkml]   [2004]   [Nov]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC] Generalize prio_tree (1/3)


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@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:08    [from the cache]
©2003-2011 Jasper Spaans