Re: AVL trees vs. Red-Black trees

Andrea Arcangeli (andrea@suse.de)
Mon, 29 Nov 1999 21:21:04 +0100 (CET)


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/