All of lore.kernel.org
 help / color / mirror / Atom feed
* Litmus test for question from Al Viro
@ 2020-10-01  4:51 Paul E. McKenney
  2020-10-01 16:15 ` Alan Stern
  0 siblings, 1 reply; 52+ messages in thread
From: Paul E. McKenney @ 2020-10-01  4:51 UTC (permalink / raw)
  To: stern, parri.andrea, will, peterz, boqun.feng, npiggin, dhowells,
	j.alglave, luc.maranget, akiyks, dlustig, joel
  Cc: viro, linux-kernel, linux-arch

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

^ permalink raw reply	[flat|nested] 52+ messages in thread

end of thread, other threads:[~2020-10-08 18:32 UTC | newest]

Thread overview: 52+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-01  4:51 Litmus test for question from Al Viro Paul E. McKenney
2020-10-01 16:15 ` Alan Stern
2020-10-01 16:36   ` Al Viro
2020-10-01 18:39     ` Alan Stern
2020-10-01 19:29       ` Al Viro
2020-10-01 21:30   ` Paul E. McKenney
2020-10-03  2:01     ` Alan Stern
2020-10-03 13:22     ` Alan Stern
2020-10-03 15:16       ` Akira Yokosawa
2020-10-03 17:13         ` Bug in herd7 [Was: Re: Litmus test for question from Al Viro] Alan Stern
2020-10-03 22:50           ` Akira Yokosawa
2020-10-04  1:40           ` [PATCH] tools: memory-model: Document that the LKMM can easily miss control dependencies Alan Stern
2020-10-04 21:07             ` joel
2020-10-04 23:12               ` Paul E. McKenney
2020-10-05 15:15           ` Bug in herd7 [Was: Re: Litmus test for question from Al Viro] Luc Maranget
2020-10-05 15:53             ` Alan Stern
2020-10-05 16:52               ` Paul E. McKenney
2020-10-05 18:19                 ` Alan Stern
2020-10-05 19:18                   ` Paul E. McKenney
2020-10-05 19:48                     ` Alan Stern
2020-10-06 16:39                       ` Paul E. McKenney
2020-10-06 17:05                         ` Alan Stern
2020-10-07 17:50                           ` Paul E. McKenney
2020-10-07 19:40                             ` Alan Stern
2020-10-07 22:38                               ` Paul E. McKenney
2020-10-08  2:25                                 ` Alan Stern
2020-10-08  2:50                                   ` Paul E. McKenney
2020-10-08 14:01                                     ` Alan Stern
2020-10-08 18:32                                       ` Paul E. McKenney
2020-10-05 15:54             ` Paul E. McKenney
2020-10-04 23:31       ` Litmus test for question from Al Viro Paul E. McKenney
2020-10-05  2:38         ` Alan Stern
2020-10-05  8:20           ` Will Deacon
2020-10-05  9:12             ` Will Deacon
2020-10-05 14:01               ` Paul E. McKenney
2020-10-05 14:23               ` Alan Stern
2020-10-05 15:13                 ` Will Deacon
2020-10-05 15:16                   ` Alan Stern
2020-10-05 15:35                     ` Peter Zijlstra
2020-10-05 15:49                       ` Paul E. McKenney
2020-10-05 14:16             ` Alan Stern
2020-10-05 14:03           ` Paul E. McKenney
2020-10-05 14:24             ` Alan Stern
2020-10-05 14:44             ` joel
2020-10-05 15:55               ` Paul E. McKenney
2020-10-05  8:36         ` David Laight
2020-10-05 13:59           ` Paul E. McKenney
2020-10-03 16:08     ` joel
2020-10-03 16:11       ` joel
2020-10-04 23:13         ` Paul E. McKenney
2020-10-03  2:35   ` Jon Masters
2020-10-04 23:32     ` Paul E. McKenney

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.