|
From: Philippe W. <phi...@sk...> - 2012-06-17 13:30:21
|
On Sun, 2012-06-17 at 13:08 +0200, Julian Seward wrote:
> > On the TT/TC, I think we have two remaining problems:
> >
> > 1. race condition on the tt_fast. For this, I hope the "xor" technique
> > can be shown (proved?) as correct.
>
> I should have commented on the xor thing before. Basically I didn't
> understand it. My problem is that (G xor H, H) contains neither less
> nor more information than (G, H) -- given any 2 of G, H, G xor H, we
> can compute the third one. So I don't see how it helps. Also, I didn't
> see any mention of memory barriers/fences in the description, so it
> must be incomplete (?) since we can't specify lockless algorithms
> without also saying where the fences must be.
I understand the idea is:
We have an address G1, and we want to find H1.
G1 is (using shift and mask) used to index in the tt_fast array.
Today (trunk), the array contains pairs (G, H).
After indexing, the pair is checked to be valid by comparing
G1 and G : if equal, the pair can be used, otherwise
the pair cannot be used : it has been replaced by e.g. (G2,H2)
or never corresponded to (G1,H1)
With the xor technique:
Similarly to the above, G1 is used to index tt_fast
However, the array contains pairs (G_xor_H, H).
The pair found from G1 can be:
a valid pair for G1, so be (G1_xor_H1/H1)
a valid pair but not for G1, so e.g. was replaced by (G2_xor_H2/H2)
any invalid pair (where i and j are whatever numbers != 1).
(Gi_xor_Hi,Hj), (G1_xor_H1, Hj), (Gi_xor_Hi, H1)
A pair can be invalid for whatever reason (e.g. in the middle of being
updated by another thread, or because the cpu has only "forwarded" half
of the stores because we have not used fence and atomic instructions).
The idea is that in all of the above valid or invalid cases,
the xor will allow to verify that the pair is valid, corresponds to G1
and so the H (H1) can be used.
Otherwise, the pair cannot be used, the asm dispatcher goes back
to C code, where the full transtab is searched, and tt_fast is
subsequently updated.
The question is: can
Gi_xor_Hi xor Hj give G1
for any other combination than i = 1 and j = 1 ?
(we assume that all Gx are unique and all Hx are unique,
but that looks a sane assumption).
Philippe
|