From: Will Deacon <will@kernel.org>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Haas <t.haas@tu-bs.de>,
Alan Stern <stern@rowland.harvard.edu>,
Andrea Parri <parri.andrea@gmail.com>,
Boqun Feng <boqun.feng@gmail.com>,
Nicholas Piggin <npiggin@gmail.com>,
David Howells <dhowells@redhat.com>,
Jade Alglave <j.alglave@ucl.ac.uk>,
Luc Maranget <luc.maranget@inria.fr>,
"Paul E. McKenney" <paulmck@kernel.org>,
Akira Yokosawa <akiyks@gmail.com>,
Daniel Lustig <dlustig@nvidia.com>,
Joel Fernandes <joelagnelf@nvidia.com>,
linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org,
lkmm@lists.linux.dev, hernan.poncedeleon@huaweicloud.com,
jonas.oberhauser@huaweicloud.com,
"r.maseli@tu-bs.de" <r.maseli@tu-bs.de>
Subject: Re: [RFC] Potential problem in qspinlock due to mixed-size accesses
Date: Mon, 16 Jun 2025 15:23:48 +0100 [thread overview]
Message-ID: <20250616142347.GA17781@willie-the-truck> (raw)
In-Reply-To: <20250613075501.GI2273038@noisy.programming.kicks-ass.net>
On Fri, Jun 13, 2025 at 09:55:01AM +0200, Peter Zijlstra wrote:
> On Thu, Jun 12, 2025 at 04:55:28PM +0200, Thomas Haas wrote:
> > We have been taking a look if mixed-size accesses (MSA) can affect the
> > correctness of qspinlock.
> > We are focusing on aarch64 which is the only memory model with MSA support
> > [1].
> > For this we extended the dartagnan [2] tool to support MSA and now it
> > reports liveness, synchronization, and mutex issues.
> > Notice that we did something similar in the past for LKMM, but we were
> > ignoring MSA [3].
> >
> > The culprit of all these issues is that atomicity of single load
> > instructions is not guaranteed in the presence of smaller-sized stores
> > (observed on real hardware according to [1] and Fig. 21/22)
> > Consider the following pseudo code:
> >
> > int16 old = xchg16_rlx(&lock, 42);
> > int32 l = load32_acq(&lock);
> >
> > Then the hardware can treat the code as (likely due to store-forwarding)
> >
> > int16 old = xchg16_rlx(&lock, 42);
> > int16 l1 = load16_acq(&lock);
> > int16 l2 = load16_acq(&lock + 2); // Assuming byte-precise pointer
> > arithmetic
> >
> > and reorder it to
> >
> > int16 l2 = load16_acq(&lock + 2);
> > int16 old = xchg16_rlx(&lock, 42);
> > int16 l1 = load16_acq(&lock);
> >
> > Now another thread can overwrite "lock" in between the first two accesses so
> > that the original l (l1 and l2) ends up containing
> > parts of a lock value that is older than what the xchg observed.
>
> Oops :-(
>
> (snip the excellent details)
>
> > ### Solutions
> >
> > The problematic executions rely on the fact that T2 can move half of its
> > load operation (1) to before the xchg_tail (3).
> > Preventing this reordering solves all issues. Possible solutions are:
> > - make the xchg_tail full-sized (i.e, also touch lock/pending bits).
> > Note that if the kernel is configured with >= 16k cpus, then the tail
> > becomes larger than 16 bits and needs to be encoded in parts of the pending
> > byte as well.
> > In this case, the kernel makes a full-sized (32-bit) access for the
> > xchg. So the above bugs are only present in the < 16k cpus setting.
>
> Right, but that is the more expensive option for some.
>
> > - make the xchg_tail an acquire operation.
> > - make the xchg_tail a release operation (this is an odd solution by
> > itself but works for aarch64 because it preserves REL->ACQ ordering). In
> > this case, maybe the preceding "smp_wmb()" can be removed.
>
> I think I prefer this one, it move a barrier, not really adding
> additional overhead. Will?
I'm half inclined to think that the Arm memory model should be tightened
here; I can raise that with Arm and see what they say.
Although the cited paper does give examples of store-forwarding from a
narrow store to a wider load, the case in qspinlock is further
constrained by having the store come from an atomic rmw and the load
having acquire semantics. Setting aside the MSA part, that specific case
_is_ ordered in the Arm memory model (and C++ release sequences rely on
it iirc), so it's fair to say that Arm CPUs don't permit forwarding from
an atomic rmw to an acquire load.
Given that, I don't see how this is going to occur in practice.
Will
next prev parent reply other threads:[~2025-06-16 14:23 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-06-12 14:55 [RFC] Potential problem in qspinlock due to mixed-size accesses Thomas Haas
2025-06-13 7:55 ` Peter Zijlstra
2025-06-13 11:17 ` Andrea Parri
[not found] ` <9264df13-36db-4b25-b2c4-7a9701df2f4d@tu-bs.de>
2025-06-16 6:21 ` Andrea Parri
2025-06-16 14:11 ` Alan Stern
2025-06-17 14:09 ` Andrea Parri
2025-06-19 14:27 ` Thomas Haas
2025-06-19 14:32 ` Alan Stern
2025-06-19 14:59 ` Thomas Haas
2025-06-19 17:56 ` Alan Stern
2025-06-19 18:21 ` Thomas Haas
2025-06-16 14:23 ` Will Deacon [this message]
2025-06-17 6:19 ` Thomas Haas
2025-06-17 8:42 ` Hernan Ponce de Leon
2025-06-17 14:17 ` Will Deacon
2025-06-17 14:23 ` Thomas Haas
2025-06-17 19:00 ` Hernan Ponce de Leon
2025-06-19 12:30 ` Will Deacon
2025-06-19 14:11 ` Thomas Haas
2025-06-18 6:51 ` Paul E. McKenney
2025-06-18 12:11 ` Paul E. McKenney
2025-12-17 19:05 ` Thomas Haas
2025-12-18 22:02 ` Andrea Parri
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250616142347.GA17781@willie-the-truck \
--to=will@kernel.org \
--cc=akiyks@gmail.com \
--cc=boqun.feng@gmail.com \
--cc=dhowells@redhat.com \
--cc=dlustig@nvidia.com \
--cc=hernan.poncedeleon@huaweicloud.com \
--cc=j.alglave@ucl.ac.uk \
--cc=joelagnelf@nvidia.com \
--cc=jonas.oberhauser@huaweicloud.com \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=lkmm@lists.linux.dev \
--cc=luc.maranget@inria.fr \
--cc=npiggin@gmail.com \
--cc=parri.andrea@gmail.com \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=r.maseli@tu-bs.de \
--cc=stern@rowland.harvard.edu \
--cc=t.haas@tu-bs.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).