Hello! Al Viro posted the following query: ------------------------------------------------------------------------ <viro> fun question regarding barriers, if you have time for that <viro> V->A = V->B = 1; <viro> <viro> CPU1: <viro> to_free = NULL <viro> spin_lock(&LOCK) <viro> if (!smp_load_acquire(&V->B)) <viro> to_free = V <viro> V->A = 0 <viro> spin_unlock(&LOCK) <viro> kfree(to_free) <viro> <viro> CPU2: <viro> to_free = V; <viro> if (READ_ONCE(V->A)) { <viro> spin_lock(&LOCK) <viro> if (V->A) <viro> to_free = NULL <viro> smp_store_release(&V->B, 0); <viro> spin_unlock(&LOCK) <viro> } <viro> kfree(to_free); <viro> 1) is it guaranteed that V will be freed exactly once and that no accesses to *V will happen after freeing it? <viro> 2) do we need smp_store_release() there? I.e. will anything break if it's replaced with plain V->B = 0? ------------------------------------------------------------------------ Of course herd7 supports neither structures nor arrays, but I was crazy enough to try individual variables with made-up address and data dependencies. This litmus test must also detect use-after-free bugs, but a simple variable should be able to do that. So here is a prototype: ------------------------------------------------------------------------ C C-viro-2020.09.29a { int a = 1; int b = 1; int v = 1; } P0(int *a, int *b, int *v, spinlock_t *l) { int r0; int r1; int r2 = 2; int r8; int r9a = 2; int r9b = 2; r0 = 0; spin_lock(l); r9a = READ_ONCE(*v); // Use after free? r8 = r9a - r9a; // Restore address dependency r8 = b + r8; r1 = smp_load_acquire(r8); if (r1 == 0) r0 = 1; r9b = READ_ONCE(*v); // Use after free? WRITE_ONCE(*a, r9b - r9b); // Use data dependency spin_unlock(l); if (r0) { r2 = READ_ONCE(*v); WRITE_ONCE(*v, 0); /* kfree(). */ } } P1(int *a, int *b, int *v, spinlock_t *l) { int r0; int r1; int r1a; int r2 = 2; int r8; int r9a = 2; int r9b = 2; int r9c = 2; r0 = READ_ONCE(*v); r9a = r0; // Use after free? r8 = r9a - r9a; // Restore address dependency r8 = a + r8; r1 = READ_ONCE(*r8); if (r1) { spin_lock(l); r9b = READ_ONCE(*v); // Use after free? r8 = r9b - r9b; // Restore address dependency r8 = a + r8; r1a = READ_ONCE(*r8); if (r1a) r0 = 0; r9c = READ_ONCE(*v); // Use after free? smp_store_release(b, r9c - rc9); // Use data dependency spin_unlock(l); } if (r0) { r2 = READ_ONCE(*v); WRITE_ONCE(*v, 0); /* kfree(). */ } } locations [a;b;v;0:r1;0:r8;1:r1;1:r8] exists (0:r0=1:r0 \/ (* Both or neither did kfree(). *) v=1 \/ (* Neither did kfree, redundant check. *) 0:r2=0 \/ 1:r2=0 \/ (* Both did kfree, redundant check. *) 0:r9a=0 \/ 0:r9b=0 \/ 1:r9a=0 \/ (* CPU1 use after free. *) 1:r9b=0 \/ 1:r9c=0) (* CPU2 use after free. *) ------------------------------------------------------------------------ This "exists" clause is satisfied: ------------------------------------------------------------------------ $ herd7 -conf linux-kernel.cfg ~/paper/scalability/LWNLinuxMM/litmus/manual/kernel/C-viro-2020.09.29a.litmus Test C-viro-2020.09.29a Allowed States 5 0:r0=0; 0:r1=1; 0:r2=2; 0:r8=b; 0:r9a=0; 0:r9b=0; 1:r0=1; 1:r1=0; 1:r2=1; 1:r8=a; 1:r9a=1; 1:r9b=2; 1:r9c=2; a=0; b=1; v=0; 0:r0=0; 0:r1=1; 0:r2=2; 0:r8=b; 0:r9a=1; 0:r9b=0; 1:r0=1; 1:r1=0; 1:r2=1; 1:r8=a; 1:r9a=1; 1:r9b=2; 1:r9c=2; a=0; b=1; v=0; 0:r0=0; 0:r1=1; 0:r2=2; 0:r8=b; 0:r9a=1; 0:r9b=1; 1:r0=0; 1:r1=1; 1:r2=2; 1:r8=a; 1:r9a=1; 1:r9b=1; 1:r9c=1; a=0; b=1; v=1; 0:r0=0; 0:r1=1; 0:r2=2; 0:r8=b; 0:r9a=1; 0:r9b=1; 1:r0=1; 1:r1=0; 1:r2=1; 1:r8=a; 1:r9a=1; 1:r9b=2; 1:r9c=2; a=0; b=1; v=0; 0:r0=0; 0:r1=1; 0:r2=2; 0:r8=b; 0:r9a=1; 0:r9b=1; 1:r0=1; 1:r1=1; 1:r2=1; 1:r8=a; 1:r9a=1; 1:r9b=1; 1:r9c=1; a=0; b=1; v=0; Ok Witnesses Positive: 3 Negative: 2 Condition exists (0:r0=1:r0 \/ v=1 \/ 0:r2=0 \/ 1:r2=0 \/ 0:r9a=0 \/ 0:r9b=0 \/ 1:r9a=0 \/ 1:r9b=0 \/ 1:r9c=0) Observation C-viro-2020.09.29a Sometimes 3 2 Time C-viro-2020.09.29a 14.33 Hash=89f74abff4de682ee0bea8ee6dd53134 ------------------------------------------------------------------------ So did we end up with herd7 not respecting "fake" dependencies like those shown above, or have I just messed up the translation from Al's example to the litmus test? (Given one thing and another over the past couple of days, my guess would be that I just messed up the translation, especially given that I don't see a reference to fake dependencies in the documentation, but I figured that I should ask.) Thanx, Paul