• Andrew Morton's avatar
    [PATCH] rmap 17: real prio_tree · 2fe9c14c
    Andrew Morton authored
    From: Hugh Dickins <hugh@veritas.com>
    
    Rajesh Venkatasubramanian's implementation of a radix priority search tree of
    vmas, to handle object-based reverse mapping corner cases well.
    
    Amongst the objections to object-based rmap were test cases by akpm and by
    mingo, in which large numbers of vmas mapping disjoint or overlapping parts of
    a file showed strikingly poor performance of the i_mmap lists.  Perhaps those
    tests are irrelevant in the real world?  We cannot be too sure: the prio_tree
    is well-suited to solving precisely that problem, so unless it turns out to
    bring too much overhead, let's include it.
    
    Why is this prio_tree.c placed in mm rather than lib?  See GET_INDEX: this
    implementation is geared throughout to use with vmas, though the first half of
    the file appears more general than the second half.
    
    Each node of the prio_tree is itself (contained within) a vma: might save
    memory by allocating distinct nodes from which to hang vmas, but wouldn't save
    much, and would complicate the usage with preallocations.  Off each node of
    the prio_tree itself hangs a list of like vmas, if any.
    
    The connection from node to list is a little awkward, but probably the best
    compromise: it would be more straightforward to list likes directly from the
    tree node, but that would use more memory per vma, for the list_head and to
    identify that head.  Instead, node's shared.vm_set.head points to next vma
    (whose shared.vm_set.head points back to node vma), and that next contains the
    list_head from which the rest hang - reusing fields already used in the
    prio_tree node itself.
    
    Currently lacks prefetch: Rajesh hopes to add some soon.
    2fe9c14c
Makefile 541 Bytes