Messages in this thread | | | Date | Mon, 29 Nov 1999 21:21:04 +0100 (CET) | From | Andrea Arcangeli <> | Subject | Re: 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/
| |