• Namhyung Kim's avatar
    mm: nommu: sort mm->mmap list properly · 6038def0
    Namhyung Kim authored
    When I was reading nommu code, I found that it handles the vma list/tree
    in an unusual way.  IIUC, because there can be more than one
    identical/overrapped vmas in the list/tree, it sorts the tree more
    strictly and does a linear search on the tree.  But it doesn't applied to
    the list (i.e.  the list could be constructed in a different order than
    the tree so that we can't use the list when finding the first vma in that
    order).
    
    Since inserting/sorting a vma in the tree and link is done at the same
    time, we can easily construct both of them in the same order.  And linear
    searching on the tree could be more costly than doing it on the list, it
    can be converted to use the list.
    
    Also, after the commit 297c5eee ("mm: make the vma list be doubly
    linked") made the list be doubly linked, there were a couple of code need
    to be fixed to construct the list properly.
    
    Patch 1/6 is a preparation.  It maintains the list sorted same as the tree
    and construct doubly-linked list properly.  Patch 2/6 is a simple
    optimization for the vma deletion.  Patch 3/6 and 4/6 convert tree
    traversal to list traversal and the rest are simple fixes and cleanups.
    
    This patch:
    
    @vma added into @mm should be sorted by start addr, end addr and VMA
    struct addr in that order because we may get identical VMAs in the @mm.
    However this was true only for the rbtree, not for the list.
    
    This patch fixes this by remembering 'rb_prev' during the tree traversal
    like find_vma_prepare() does and linking the @vma via __vma_link_list().
    After this patch, we can iterate the whole VMAs in correct order simply by
    using @mm->mmap list.
    
    [akpm@linux-foundation.org: avoid duplicating __vma_link_list()]
    Signed-off-by: default avatarNamhyung Kim <namhyung@gmail.com>
    Acked-by: default avatarGreg Ungerer <gerg@uclinux.org>
    Cc: David Howells <dhowells@redhat.com>
    Cc: Paul Mundt <lethal@linux-sh.org>
    Cc: Geert Uytterhoeven <geert@linux-m68k.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    6038def0
util.c 7.29 KB