linux-kernel - Re: Litmus test for question from Al Viro

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20201001183925.GA259470@rowland.harvard.edu>
Date:   Thu, 1 Oct 2020 14:39:25 -0400
From:   Alan Stern <stern@...land.harvard.edu>
To:     Al Viro <viro@...iv.linux.org.uk>
Cc:     "Paul E. McKenney" <paulmck@...nel.org>, parri.andrea@...il.com,
        will@...nel.org, peterz@...radead.org, boqun.feng@...il.com,
        npiggin@...il.com, dhowells@...hat.com, j.alglave@....ac.uk,
        luc.maranget@...ia.fr, akiyks@...il.com, dlustig@...dia.com,
        joel@...lfernandes.org, linux-kernel@...r.kernel.org,
        linux-arch@...r.kernel.org
Subject: Re: Litmus test for question from Al Viro

On Thu, Oct 01, 2020 at 05:36:46PM +0100, Al Viro wrote:
> On Thu, Oct 01, 2020 at 12:15:29PM -0400, Alan Stern wrote:
> > > <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?
> > 
> > Here are my answers to Al's questions:
> > 
> > 1) It is guaranteed that V will be freed exactly once.  It is not 
> > guaranteed that no accesses to *V will occur after it is freed, because 
> > the test contains a data race.  CPU1's plain "V->A = 0" write races with 
> > CPU2's READ_ONCE;
> 
> What will that READ_ONCE() yield in that case?  If it's non-zero, we should
> be fine - we won't get to kfree() until after we are done with the spinlock.
> And if it's zero...  What will CPU1 do with *V accesses _after_ it has issued
> the store to V->A?
> 
> Confused...

Presumably CPU2's READ_ONCE will yield either 0 or 1.  For the sake of 
argument, suppose it yields 0.  But that's not the problem.

The problem with a plain write is that it isn't guaranteed to be atomic 
in any sense.  In principle, the compiler could generate code for CPU1 
which would write 0 to V->A more than once.

Although I strongly doubt that any real compiler would actually do this, 
the memory model does allow for it, out of an overabundance of caution.  
So what could happen is:

	CPU1				CPU2
	Writes 0 to V->A a first time
					READ_ONCE(V->A) returns 0
					Skips the critical section
					Does kfree(V)
	Tries to write 0 to V->A a
	 second time

> > if the plain write were replaced with 
> > "WRITE_ONCE(V->A, 0)" then the guarantee would hold.  Equally well, 
> > CPU1's smp_load_acquire could be replaced with a plain read while the 
> > plain write is replaced with smp_store_release.
> 
> Er...  Do you mean the write to ->A on CPU1?

Yes; that's the only plain write in the litmus test.

Alan