linux-kernel - Re: [PATCH] seqlock: Use WRITE

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: <b00e0fb8-7cd3-4e00-b1ea-92a82681fb99@paulmck-laptop>
Date: Wed, 18 Dec 2024 10:52:27 -0800
From: "Paul E. McKenney" <paulmck@...nel.org>
To: Waiman Long <llong@...hat.com>
Cc: Daniel Xu <dxu@...uu.xyz>, mingo@...hat.com, will@...nel.org,
	peterz@...radead.org, boqun.feng@...il.com,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] seqlock: Use WRITE_ONCE() when updating sequence

On Wed, Dec 18, 2024 at 01:38:17PM -0500, Waiman Long wrote:
> On 12/18/24 11:57 AM, Paul E. McKenney wrote:
> > On Wed, Dec 18, 2024 at 11:10:01AM -0500, Waiman Long wrote:
> > > On 12/18/24 10:45 AM, Paul E. McKenney wrote:
> > > > On Tue, Dec 17, 2024 at 10:30:39PM -0500, Waiman Long wrote:
> > > > > For seqcount, its actual value isn't important. What is important is whether
> > > > > the value changes and whether it is even or odd. So even if store tearing is
> > > > > happening, it shouldn't affect its operation. I doubt we need to use
> > > > > WRITE_ONCE() here. Could you come up with a scenario where store tearing
> > > > > will make it behave incorrectly?
> > > > But why expand the state space?
> > > I don't quite get what you mean by "state space".
> > The state space includes the set of possible values that might be stored
> > in .sequence at any given point in time.  So if you allow the compiler to
> > tear the store, you are increasing the number of values that a concurrent
> > reader can return, and thus also increasing the number of states that must
> > be considered.  On the other hand, if you use WRITE_ONCE() to constrain
> > the compiler to do a single store, then you don't have to even worry
> > about the added states due to these partial updates.
> 
> Thanks for the explanation. Now I know what you mean.
> 
> As I said above, the correct operation of seqcount does not depend on
> getting its intended value right. It is just its odd/even-ness as well as if
> the value has been changed from previous read. That is the state space where
> seqcount is operated on.

Perhaps an example would help.  Given 16-bit store tearing on the 32-bit
unsigned sequence, the following could happen:

..., 0x0000fffe, 0x0000ffff, 0x00000000, 0x00010000, 0x00010001, ...

With the WRITE_ONCE() prohibiting store tearing, one of those values
cannot happen:

..., 0x0000fffe, 0x0000ffff,             0x00010000, 0x00010001, ...

Hence the smaller state space.  Yes, I understand that you can easily
reason you way around this, but would a younger version of yourself if
chasing some other bug through this code while sleep-deprived?

> > > > Also, there are potentially "optimizations" other than store tearing.
> > > > No, I haven't seen them yet, but then again, there were a great many
> > > > optimizations that were not being used back when I started coding C.
> > > All the inc's are bounded by smp_wmb()'s which should limit the kind of
> > > optimizations that can be done by the compiler. That is why I don't see a
> > > need to use WRITE_ONCE() here. Of course, there may be some corner cases
> > > that I may miss. So I ask for whether such a case exists.
> > One other potential optimization is using the variable for scratch storage
> > immediately prior to the update, which could store any value there.
> > I haven't seen this myself, but the standard permits it, and in some
> > cases register pressure might encourage it.
> > 
> > And who knows what else our creative compiler writers will come up with?
> 
> If the compiler really uses the variable as a scratch storage, it will be a
> problem if the variable can be accessed concurrently from multiple CPUs. It
> is a new compiler optimization strategy that I am aware before. In that
> case, we may really need a way to mark these variables as not suitable for
> such advanced optimization.

These markings already exist, namely, the "volatile" keyword, READ_ONCE(),
WRITE_ONCE(), and hopefully soon INC_ONCE().  These last three use
volatile accesses internally.

The scratch-storage possibility exists only just before a normal
C-language store, not before volatile accesses.  So a compiler is
forbidden from doing that scratch-value-store trick before a volatile
store.

							Thanx, Paul