• Liam R. Howlett's avatar
    Maple Tree: add new data structure · 54a611b6
    Liam R. Howlett authored
    Patch series "Introducing the Maple Tree"
    
    The maple tree is an RCU-safe range based B-tree designed to use modern
    processor cache efficiently.  There are a number of places in the kernel
    that a non-overlapping range-based tree would be beneficial, especially
    one with a simple interface.  If you use an rbtree with other data
    structures to improve performance or an interval tree to track
    non-overlapping ranges, then this is for you.
    
    The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
    nodes.  With the increased branching factor, it is significantly shorter
    than the rbtree so it has fewer cache misses.  The removal of the linked
    list between subsequent entries also reduces the cache misses and the need
    to pull in the previous and next VMA during many tree alterations.
    
    The first user that is covered in this patch set is the vm_area_struct,
    where three data structures are replaced by the maple tree: the augmented
    rbtree, the vma cache, and the linked list of VMAs in the mm_struct.  The
    long term goal is to reduce or remove the mmap_lock contention.
    
    The plan is to get to the point where we use the maple tree in RCU mode.
    Readers will not block for writers.  A single write operation will be
    allowed at a time.  A reader re-walks if stale data is encountered.  VMAs
    would be RCU enabled and this mode would be entered once multiple tasks
    are using the mm_struct.
    
    Davidlor said
    
    : Yes I like the maple tree, and at this stage I don't think we can ask for
    : more from this series wrt the MM - albeit there seems to still be some
    : folks reporting breakage.  Fundamentally I see Liam's work to (re)move
    : complexity out of the MM (not to say that the actual maple tree is not
    : complex) by consolidating the three complimentary data structures very
    : much worth it considering performance does not take a hit.  This was very
    : much a turn off with the range locking approach, which worst case scenario
    : incurred in prohibitive overhead.  Also as Liam and Matthew have
    : mentioned, RCU opens up a lot of nice performance opportunities, and in
    : addition academia[1] has shown outstanding scalability of address spaces
    : with the foundation of replacing the locked rbtree with RCU aware trees.
    
    A similar work has been discovered in the academic press
    
    	https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf
    
    Sheer coincidence.  We designed our tree with the intention of solving the
    hardest problem first.  Upon settling on a b-tree variant and a rough
    outline, we researched ranged based b-trees and RCU b-trees and did find
    that article.  So it was nice to find reassurances that we were on the
    right path, but our design choice of using ranges made that paper unusable
    for us.
    
    This patch (of 70):
    
    The maple tree is an RCU-safe range based B-tree designed to use modern
    processor cache efficiently.  There are a number of places in the kernel
    that a non-overlapping range-based tree would be beneficial, especially
    one with a simple interface.  If you use an rbtree with other data
    structures to improve performance or an interval tree to track
    non-overlapping ranges, then this is for you.
    
    The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
    nodes.  With the increased branching factor, it is significantly shorter
    than the rbtree so it has fewer cache misses.  The removal of the linked
    list between subsequent entries also reduces the cache misses and the need
    to pull in the previous and next VMA during many tree alterations.
    
    The first user that is covered in this patch set is the vm_area_struct,
    where three data structures are replaced by the maple tree: the augmented
    rbtree, the vma cache, and the linked list of VMAs in the mm_struct.  The
    long term goal is to reduce or remove the mmap_lock contention.
    
    The plan is to get to the point where we use the maple tree in RCU mode.
    Readers will not block for writers.  A single write operation will be
    allowed at a time.  A reader re-walks if stale data is encountered.  VMAs
    would be RCU enabled and this mode would be entered once multiple tasks
    are using the mm_struct.
    
    There is additional BUG_ON() calls added within the tree, most of which
    are in debug code.  These will be replaced with a WARN_ON() call in the
    future.  There is also additional BUG_ON() calls within the code which
    will also be reduced in number at a later date.  These exist to catch
    things such as out-of-range accesses which would crash anyways.
    
    Link: https://lkml.kernel.org/r/20220906194824.2110408-1-Liam.Howlett@oracle.com
    Link: https://lkml.kernel.org/r/20220906194824.2110408-2-Liam.Howlett@oracle.comSigned-off-by: default avatarLiam R. Howlett <Liam.Howlett@oracle.com>
    Signed-off-by: default avatarMatthew Wilcox (Oracle) <willy@infradead.org>
    Tested-by: default avatarDavid Howells <dhowells@redhat.com>
    Tested-by: default avatarSven Schnelle <svens@linux.ibm.com>
    Tested-by: default avatarYu Zhao <yuzhao@google.com>
    Cc: Vlastimil Babka <vbabka@suse.cz>
    Cc: David Hildenbrand <david@redhat.com>
    Cc: Davidlohr Bueso <dave@stgolabs.net>
    Cc: Catalin Marinas <catalin.marinas@arm.com>
    Cc: SeongJae Park <sj@kernel.org>
    Cc: Will Deacon <will@kernel.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    54a611b6
Makefile 14.1 KB