• Peter Zijlstra's avatar
    rbtree: Make lockless searches non-fatal · d72da4a4
    Peter Zijlstra authored
    Change the insert and erase code such that lockless searches are
    non-fatal.
    
    In and of itself an rbtree cannot be correctly searched while
    in-modification, we can however provide weaker guarantees that will
    allow the rbtree to be used in conjunction with other techniques, such
    as latches; see 9b0fd802 ("seqcount: Add raw_write_seqcount_latch()").
    
    For this to work we need the following guarantees from the rbtree
    code:
    
     1) a lockless reader must not see partial stores, this would allow it
        to observe nodes that are invalid memory.
    
     2) there must not be (temporary) loops in the tree structure in the
        modifier's program order, this would cause a lookup which
        interrupts the modifier to get stuck indefinitely.
    
    For 1) we must use WRITE_ONCE() for all updates to the tree structure;
    in particular this patch only does rb_{left,right} as those are the
    only element required for simple searches.
    
    It generates slightly worse code, probably because volatile. But in
    pointer chasing heavy code a few instructions more should not matter.
    
    For 2) I have carefully audited the code and drawn every intermediate
    link state and not found a loop.
    
    Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
    Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
    Cc: Oleg Nesterov <oleg@redhat.com>
    Cc: Andrea Arcangeli <aarcange@redhat.com>
    Cc: David Woodhouse <David.Woodhouse@intel.com>
    Cc: Rik van Riel <riel@redhat.com>
    Reviewed-by: default avatarMichel Lespinasse <walken@google.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
    d72da4a4
rbtree_augmented.h 7.5 KB