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    [W:4.827 / U:0.004 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site