lkml.org 
[lkml]   [2015]   [Mar]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    SubjectRe: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatal
    From
    On Sat, Feb 28, 2015 at 1:24 PM, Peter Zijlstra <peterz@infradead.org> wrote:
    > 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 9b0fd802e8c0 ("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 gcc stinks at
    > volatile. But in pointer chasing heavy code a few instructions more
    > should not matter.

    So, I was worried that this would penalize all rbtree users, for the
    benefit of just the one you're adding later in this series. We have
    several rbtrees where we care about performance a lot, such as the
    ones used in the scheduler or for indexing vmas.

    That said, I checked with the compiler we are using here (gcc 4.7
    variant) and I didn't see any change in the generated code. So, no
    issue here for me.

    If the object code really is different in your setup, please use the
    lib/rbtree_test module to check the performance impact of the change.

    > For 2) I have carefully audited the code and drawn every intermediate
    > link state and not found a loop.

    As Mathieu remarked, we are never modifying the currently active tree,
    so the interrupt case is not the reason for avoiding loops.


    I think your proposal will work well for the use case you have in mind
    (looking up modules based on address). However, I was wondering how
    you would compare your proposal against an alternative I hard Josh
    Triplett formulate before, where there would be one unique rbtree but
    rotations would allocate new nodes rather than modify the existing
    ones. I think this would be workable as well; I'm just not sure
    whether this would be more or less generally applicable than your
    proposal. Copying Josh in case he wants to chime in.

    Reviewed-by: Michel Lespinasse <walken@google.com>

    --
    Michel "Walken" Lespinasse
    A program is never fully debugged until the last user dies.


    \
     
     \ /
      Last update: 2015-03-01 22:21    [W:4.190 / U:0.372 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site