lkml.org 
[lkml]   [1999]   [Nov]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: AVL trees vs. Red-Black trees
    On Mon, 29 Nov 1999, Ingo Molnar wrote:

    >guarantees the 'Program Order' shared memory model, which makes

    Unfortunately the empirical test tells that something must be going wrong.
    I have to possible diagnoses:

    1) the speculative `read A` is not invalidated by a further
    `write A` on a parallel CPU. It doesn't matter the delay inserted
    by the write buffer of course. I don't doesn't matter if the
    `write A` gets delayed for one week, it matters that when the
    write become visible, then the speculated value obtained by
    `read A` should be invalidated and the read should be repeated.

    2) the writes become visible in reverse order to the other cpus
    (maybe because the wbuf merge all writes and show them
    in a different order?) That should not be the case, I know of
    course. But if I put a lock on the bus in the middle of the two
    writes (that should drain the wbuf), then readers has no problems
    anymore. But I believe it's a side effect of the lock that
    prevents the reader to speculate someway.

    I believe the right diagnose is (1) (that is exactly the scenario that we
    was assuming as normal starting from the 2.1.x tree). If (2) would be
    true, your causality test could trigger problems too, but it doesn't. So
    it seems to me that only a speculative read is breaking the ordering
    rules.

    Andrea


    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.rutgers.edu
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 13:55    [W:2.869 / U:0.020 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site