Received-SPF: pass (google.com: domain of linux-kernel+bounces-204677-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
Date: Thu, 6 Jun 2024 18:13:32 +0200
From: Andrea Parri <parri.andrea@gmail.com>
To: Alan Stern <stern@rowland.harvard.edu>
Cc: "Paul E. McKenney" <paulmck@kernel.org>, will@kernel.org,
	peterz@infradead.org, boqun.feng@gmail.com, npiggin@gmail.com,
	dhowells@redhat.com, j.alglave@ucl.ac.uk, luc.maranget@inria.fr,
	akiyks@gmail.com, dlustig@nvidia.com, joel@joelfernandes.org,
	linux-kernel@vger.kernel.org, hernan.poncedeleon@huaweicloud.com,
	jonas.oberhauser@huaweicloud.com
Subject: Re: [PATCH 1/2] tools/memory-model: Fix bug in lock.cat
Message-ID: <ZmHgLFJNRekyVAiH@andrea>
References: <eb202b3b-7408-4ab9-be82-81ca554b7603@rowland.harvard.edu>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <eb202b3b-7408-4ab9-be82-81ca554b7603@rowland.harvard.edu>

On Thu, Jun 06, 2024 at 09:57:55AM -0400, Alan Stern wrote:
> Andrea reported that the following innocuous litmus test:
> 
> C T
> 
> {}
> 
> P0(spinlock_t *x)
> {
> 	int r0;
> 
> 	spin_lock(x);
> 	spin_unlock(x);
> 	r0 = spin_is_locked(x);
> }
> 
> gives rise to a nonsensical empty result with no executions:
> 
> $ herd7 -conf linux-kernel.cfg T.litmus
> Test T Required
> States 0
> Ok
> Witnesses
> Positive: 0 Negative: 0
> Condition forall (true)
> Observation T Never 0 0
> Time T 0.00
> Hash=6fa204e139ddddf2cb6fa963bad117c0
> 
> The problem is caused by a bug in the lock.cat part of the LKMM.  Its
> computation of the rf relation for RU (read-unlocked) events is
> faulty; it implicitly assumes that every RU event must read from
> either a UL (unlock) event in another thread or from the lock's
> initial state.  Neither is true in the litmus test above, so the
> computation yields no possible executions.
> 
> The lock.cat code tries to make up for this deficiency by allowing RU
> events outside of critical sections to read from the last po-previous
> UL event.  But it does this incorrectly, trying to keep these rfi links
> separate from the rfe links that might also be needed, and passing only
> the latter to herd7's cross() macro.
> 
> The problem is fixed by merging the two sets of possible rf links for
> RU events and using them all in the call to cross().
> 
> Signed-off-by: Alan Stern <stern@rowland.harvard.edu>
> Reported-and-tested-by: Andrea Parri <parri.andrea@gmail.com>
> Closes: https://lore.kernel.org/linux-arch/ZlC0IkzpQdeGj+a3@andrea/
> Fixes: 15553dcbca06 ("tools/memory-model: Add model support for spin_is_locked()")

Acked-by: Andrea Parri <parri.andrea@gmail.com>

  Andrea