Re: Litmus test for question from Al Viro
From: Alan Stern <stern@rowland.harvard.edu>
Date: 2020-10-05 02:38:49
Also in:
lkml
On Sun, Oct 04, 2020 at 04:31:46PM -0700, Paul E. McKenney wrote:
quoted hunk ↗ jump to hunk
Nice simple example! How about like this? Thanx, Paul ------------------------------------------------------------------------ commit c964f404eabe4d8ce294e59dda713d8c19d340cf Author: Alan Stern [off-list ref] Date: Sun Oct 4 16:27:03 2020 -0700 manual/kernel: Add a litmus test with a hidden dependency This commit adds a litmus test that has a data dependency that can be hidden by control flow. In this test, both the taken and the not-taken branches of an "if" statement must be accounted for in order to properly analyze the litmus test. But herd7 looks only at individual executions in isolation, so fails to see the dependency. Signed-off-by: Alan Stern [off-list ref] Signed-off-by: Paul E. McKenney [off-list ref]diff --git a/manual/kernel/crypto-control-data.litmus b/manual/kernel/crypto-control-data.litmus new file mode 100644 index 0000000..6baecf9 --- /dev/null +++ b/manual/kernel/crypto-control-data.litmus@@ -0,0 +1,31 @@ +C crypto-control-data +(* + * LB plus crypto-control-data plus data + * + * Result: Sometimes + * + * This is an example of OOTA and we would like it to be forbidden. + * The WRITE_ONCE in P0 is both data-dependent and (at the hardware level) + * control-dependent on the preceding READ_ONCE. But the dependencies are + * hidden by the form of the conditional control construct, hence the + * name "crypto-control-data". The memory model doesn't recognize them. + *) + +{} + +P0(int *x, int *y) +{ + int r1; + + r1 = 1; + if (READ_ONCE(*x) == 0) + r1 = 0; + WRITE_ONCE(*y, r1); +} + +P1(int *x, int *y) +{ + WRITE_ONCE(*x, READ_ONCE(*y)); +} + +exists (0:r1=1)
Considering the bug in herd7 pointed out by Akira, we should rewrite P1 as:
P1(int *x, int *y)
{
int r2;
r = READ_ONCE(*y);
WRITE_ONCE(*x, r2);
}
Other than that, this is fine.
Alan