• Joonsoo Kim's avatar
    mm, vmalloc: change iterating a vmlist to find_vm_area() · ef932473
    Joonsoo Kim authored
    This patchset removes vm_struct list management after initializing
    vmalloc.  Adding and removing an entry to vmlist is linear time
    complexity, so it is inefficient.  If we maintain this list, overall
    time complexity of adding and removing area to vmalloc space is O(N),
    although we use rbtree for finding vacant place and it's time complexity
    is just O(logN).
    
    And vmlist and vmlist_lock is used many places of outside of vmalloc.c.
    It is preferable that we hide this raw data structure and provide
    well-defined function for supporting them, because it makes that they
    cannot mistake when manipulating theses structure and it makes us easily
    maintain vmalloc layer.
    
    For kexec and makedumpfile, I export vmap_area_list, instead of vmlist.
    This comes from Atsushi's recommendation.  For more information, please
    refer below link.  https://lkml.org/lkml/2012/12/6/184
    
    This patch:
    
    The purpose of iterating a vmlist is finding vm area with specific virtual
    address.  find_vm_area() is provided for this purpose and more efficient,
    because it uses a rbtree.  So change it.
    Signed-off-by: default avatarJoonsoo Kim <js1304@gmail.com>
    Signed-off-by: default avatarJoonsoo Kim <iamjoonsoo.kim@lge.com>
    Acked-by: default avatarGuan Xuetao <gxt@mprc.pku.edu.cn>
    Acked-by: default avatarIngo Molnar <mingo@kernel.org>
    Acked-by: default avatarChris Metcalf <cmetcalf@tilera.com>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: "H. Peter Anvin" <hpa@zytor.com>
    Cc: Atsushi Kumagai <kumagai-atsushi@mxc.nes.nec.co.jp>
    Cc: Dave Anderson <anderson@redhat.com>
    Cc: Eric Biederman <ebiederm@xmission.com>
    Cc: Vivek Goyal <vgoyal@redhat.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    ef932473
pgtable.c 16.4 KB