12:44 a.m.
On Mon, 3 Jun 2019, Paul E. McKenney wrote:
On Mon, Jun 03, 2019 at 02:42:00PM +0800, Boqun Feng wrote:
> On Mon, Jun 03, 2019 at 01:26:26PM +0800, Herbert Xu wrote:
> > On Sun, Jun 02, 2019 at 08:47:07PM -0700, Paul E. McKenney wrote:
> > >
> > > 1. These guarantees are of full memory barriers, -not- compiler
> > > barriers.
> >
> > What I'm saying is that wherever they are, they must come with
> > compiler barriers. I'm not aware of any synchronisation mechanism
> > in the kernel that gives a memory barrier without a compiler barrier.
> >
> > > 2. These rules don't say exactly where these full memory barriers
> > > go. SRCU is at one extreme, placing those full barriers in
> > > srcu_read_lock() and srcu_read_unlock(), and !PREEMPT Tree RCU
> > > at the other, placing these barriers entirely within the callback
> > > queueing/invocation, grace-period computation, and the scheduler.
> > > Preemptible Tree RCU is in the middle, with rcu_read_unlock()
> > > sometimes including a full memory barrier, but other times with
> > > the full memory barrier being confined as it is with !PREEMPT
> > > Tree RCU.
> >
> > The rules do say that the (full) memory barrier must precede any
> > RCU read-side that occur after the synchronize_rcu and after the
> > end of any RCU read-side that occur before the synchronize_rcu.
> >
> > All I'm arguing is that wherever that full mb is, as long as it
> > also carries with it a barrier() (which it must do if it's done
> > using an existing kernel mb/locking primitive), then we're fine.
> >
> > > Interleaving and inserting full memory barriers as per the rules above:
> > >
> > > CPU1: WRITE_ONCE(a, 1)
> > > CPU1: synchronize_rcu
> > > /* Could put a full memory barrier here, but it wouldn't help. */
> >
> > CPU1: smp_mb();
> > CPU2: smp_mb();
> >
> > Let's put them in because I think they are critical. smp_mb() also
> > carries with it a barrier().
> >
> > > CPU2: rcu_read_lock();
> > > CPU1: b = 2;
> > > CPU2: if (READ_ONCE(a) == 0)
> > > CPU2: if (b != 1) /* Weakly ordered CPU moved this up! */
> > > CPU2: b = 1;
> > > CPU2: rcu_read_unlock
> > >
> > > In fact, CPU2's load from b might be moved up to race with CPU1's
store,
> > > which (I believe) is why the model complains in this case.
> >
> > Let's put aside my doubt over how we're even allowing a compiler
> > to turn
> >
> > b = 1
> >
> > into
> >
> > if (b != 1)
> > b = 1
Even if you don't think the compiler will ever do this, the C standard
gives compilers the right to invent read accesses if a plain (i.e.,
non-atomic and non-volatile) write is present. The Linux Kernel Memory
Model has to assume that compilers will sometimes do this, even if it
doesn't take the exact form of checking a variable's value before
writing to it.
(Incidentally, regardless of whether the compiler will ever do this, I
have seen examples in the kernel where people did exactly this
manually, in order to avoid dirtying a cache line unnecessarily.)
> > Since you seem to be assuming that (a == 0) is true in this
case
>
> I think Paul's example assuming (a == 0) is false, and maybe
Yes, otherwise, P0()'s write to "b" cannot have happened.
> speculative writes (by compilers) needs to added into consideration?
On the other hand, the C standard does not allow compilers to add
speculative writes. The LKMM assumes they will never occur.
I would instead call it the compiler eliminating needless writes
by inventing reads -- if the variable already has the correct value,
no write happens. So no compiler speculation.
However, it is difficult to create a solid defensible example. Yes,
from LKMM's viewpoint, the weakly reordered invented read from "b"
can be concurrent with P0()'s write to "b", but in that case the value
loaded would have to manage to be equal to 1 for anything bad to happen.
This does feel wrong to me, but again, it is difficult to create a solid
defensible example.
> Please consider the following case (I add a few smp_mb()s), the case may
> be a little bit crasy, you have been warned ;-)
>
> CPU1: WRITE_ONCE(a, 1)
> CPU1: synchronize_rcu called
>
> CPU1: smp_mb(); /* let assume there is one here */
>
> CPU2: rcu_read_lock();
> CPU2: smp_mb(); /* let assume there is one here */
>
> /* "if (b != 1) b = 1" reordered */
> CPU2: r0 = b; /* if (b != 1) reordered here, r0 == 0 */
> CPU2: if (r0 != 1) /* true */
> CPU2: b = 1; /* b == 1 now, this is a speculative write
> by compiler
> */
>
> CPU1: b = 2; /* b == 2 */
>
> CPU2: if (READ_ONCE(a) == 0) /* false */
> CPU2: ...
> CPU2 else /* undo the speculative write */
> CPU2: b = r0; /* b == 0 */
>
> CPU2: smp_mb();
> CPU2: read_read_unlock();
>
> I know this is too crasy for us to think a compiler like this, but this
> might be the reason why the model complain about this.
>
> Paul, did I get this right? Or you mean something else?
Mostly there, except that I am not yet desperate enough to appeal to
compilers speculating stores. ;-)
This example really does point out a weakness in the LKMM's handling of
data races. Herbert's litmus test is a great starting point:
C xu
{}
P0(int *a, int *b)
{
WRITE_ONCE(*a, 1);
synchronize_rcu();
*b = 2;
}
P1(int *a, int *b)
{
rcu_read_lock();
if (READ_ONCE(*a) == 0)
*b = 1;
rcu_read_unlock();
}
exists (~b=2)
Currently the LKMM says the test is allowed and there is a data race,
but this answer clearly is wrong since it would violate the RCU
guarantee.
The problem is that the LKMM currently requires all ordering/visibility
of plain accesses to be mediated by marked accesses. But in this case,
the visibility is mediated by RCU. Technically, we need to add a
relation like
([M] ; po ; rcu-fence ; po ; [M])
into the definitions of ww-vis, wr-vis, and rw-xbstar. Doing so
changes the litmus test's result to "not allowed" and no data race.
However, I'm not certain that this single change is the entire fix;
more thought is needed.
Alan
2:04 a.m.
New subject: rcu_read_lock lost its compiler barrier
On Tue, Jun 4, 2019 at 7:44 AM Alan Stern <stern(a)rowland.harvard.edu> wrote:
Even if you don't think the compiler will ever do this, the C standard
gives compilers the right to invent read accesses if a plain (i.e.,
non-atomic and non-volatile) write is present.
Note that for the kernel, it's not like we go strictly by what the
standard says anyway.
The reason for the "read for write" thing is that obviously you
sometimes have broken architectures (*cough*alpha*cough*) that need to
do some common writes are read-maskmodify-write accesses, and for
bitfields you obviously *always* have that issue.
In general, a sane compiler (as opposed to "we just read the
standard") had better not add random reads, because people might have
some mappings be write-only when the hardware supports it.
And we do generally expect sanity from our compilers, and will add
compiler flags to disable bad behavior if required - even if said
behavior would be "technically allowed by the standard".
(Incidentally, regardless of whether the compiler will ever do this,
I
have seen examples in the kernel where people did exactly this
manually, in order to avoid dirtying a cache line unnecessarily.)
I really hope and expect that this is not something that the compiler ever does.
If a compiler turns "x = y" into if (x != y) x = y" (like we do
manually at times, as you say), that compiler is garbage that we
cannot use for the kernel. It would break things like "smp_wmb()"
ordering guarantees, I'm pretty sure.
And as always, if we're doing actively stupid things, and the compiler
then turns our stupid code into something we don't expect, the
corollary is that then it's on _us_. IOW, if we do
if (x != 1) {
...
}
x = 1;
and the compiler goes "oh, we already checked that 'x == 1'" and moves
that "unconditional" 'x = 1' into the conditional section like
if (x != 1) {
..
x = 1;
}
then that's not something we can then complain about.
So our expectation is that the compiler is _sane_, not that it's some
"C as assembler". Adding spurious reads is not ok. But if we already
had reads in the code and the compiler combines them with other ops,
that's on us.
End result: in general, we do expect that the compiler turns a regular
assignment into a single plain write when that's what the code does,
and does not add extra logic over and beyond that.
In fact, the alpha port was always subtly buggy exactly because of the
"byte write turns into a read-and-masked-write", even if I don't think
anybody ever noticed (we did fix cases where people _did_ notice,
though, and we might still have some cases where we use 'int' for
booleans because of alpha issues.).
So I don't technically disagree with anything you say, I just wanted
to point out that as far as the kernel is concerned, we do have higher
quality expectations from the compiler than just "technically valid
according to the C standard".
Linus
3 a.m.
New subject: rcu_read_lock lost its compiler barrier
On Tue, 4 Jun 2019, Linus Torvalds wrote:
So I don't technically disagree with anything you say,
That's good to know!
I just wanted
to point out that as far as the kernel is concerned, we do have higher
quality expectations from the compiler than just "technically valid
according to the C standard".
Which suggests asking whether these higher expectations should be
reflected in the Linux Kernel Memory Model. So far we have largely
avoided doing that sort of thing, although there are a few exceptions.
(For example, we assume the compiler does not destroy address
dependencies from volatile reads -- but we also warn that this
assumption may fail if the programmer does not follow some rules
described in one of Paul's documentation files.)
Alan
3:29 a.m.
New subject: rcu_read_lock lost its compiler barrier
On Tue, Jun 4, 2019 at 10:00 AM Alan Stern <stern(a)rowland.harvard.edu> wrote:
Which suggests asking whether these higher expectations should be
reflected in the Linux Kernel Memory Model. So far we have largely
avoided doing that sort of thing, although there are a few exceptions.
I think they might be hard to describe - which in turn may be why the
standard leaves it open and only describes the simple cases.
Exactly that "we expect an assignment to be done as a single write" is
probably a good example. Yes, we do have that expectation for the
simple cases. But it's not an absolute rule, obviously, because it's
clearly violated by bitfield writes, and similarly it's obviously
violated for data that is bigger than the word size (ie a "u64"
assignment is obviously not a single write when you're on a 32-bit
target).
And while those cases are static and could be described separately,
the "oh, and we have _other_ accesses to the same variable nearby, and
we expect that the compiler might take those into account unless we
explicitly use WRITE_ONCE()" things make for much more hard to
describe issues.
Doing writes with speculative values is clearly bogus and garbage
(although compiler writers _have_ tried to do that too: "we then
overwrite it with the right value later, so it's ok"), and thankfully
even user space people complain about that due to threading and
signals. But eliding writes entirely by combining them with a later
one is clearly ok - and eliding them when there was an explcit earlier
read and value comparison (like in my example) sounds reasonable to me
too. Yet silently adding the elision that wasn't visible in the source
due to other accesses would be bad.
How do you say "sane and reasonable compiler" in a spec? You usually
don't - or you make the rules so odd and complex than nobody really
understands them any more, and make it all moot ;)
Linus
12:09 a.m.
New subject: inet: frags: Turn fqdir->dead into an int for old Alphas
On Tue, Jun 04, 2019 at 09:04:55AM -0700, Linus Torvalds wrote:
In fact, the alpha port was always subtly buggy exactly because of the
"byte write turns into a read-and-masked-write", even if I don't think
anybody ever noticed (we did fix cases where people _did_ notice,
though, and we might still have some cases where we use 'int' for
booleans because of alpha issues.).
This is in fact a real bug in the code in question that no amount
of READ_ONCE/WRITE_ONCE would have caught. The field fqdir->dead is
declared as boolean so writing to it is not atomic (on old Alphas).
I don't think it currently matters because padding would ensure
that it is in fact 64 bits long. However, should someone add another
char/bool/bitfield in this struct in future it could become an issue.
So let's fix it.
---8<--
The field fqdir->dead is meant to be written (and read) atomically.
As old Alpha CPUs can't write a single byte atomically, we need at
least an int for it to work.
Signed-off-by: Herbert Xu <herbert(a)gondor.apana.org.au>
diff --git a/include/net/inet_frag.h b/include/net/inet_frag.h
index e91b79ad4e4a..8c458fba74ad 100644
--- a/include/net/inet_frag.h
+++ b/include/net/inet_frag.h
@@ -14,7 +14,9 @@ struct fqdir {
int max_dist;
struct inet_frags *f;
struct net *net;
- bool dead;
+
+ /* We can't use boolean because this needs atomic writes. */
+ int dead;
struct rhashtable rhashtable ____cacheline_aligned_in_smp;
diff --git a/net/ipv4/inet_fragment.c b/net/ipv4/inet_fragment.c
index 35e9784fab4e..05aa7c145817 100644
--- a/net/ipv4/inet_fragment.c
+++ b/net/ipv4/inet_fragment.c
@@ -193,7 +193,7 @@ void fqdir_exit(struct fqdir *fqdir)
{
fqdir->high_thresh = 0; /* prevent creation of new frags */
- fqdir->dead = true;
+ fqdir->dead = 1;
/* call_rcu is supposed to provide memory barrier semantics,
* separating the setting of fqdir->dead with the destruction
--
Email: Herbert Xu <herbert(a)gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
1:26 a.m.
New subject: inet: frags: Turn fqdir->dead into an int for old Alphas
On 6/7/19 7:09 AM, Herbert Xu wrote:
On Tue, Jun 04, 2019 at 09:04:55AM -0700, Linus Torvalds wrote:
>
> In fact, the alpha port was always subtly buggy exactly because of the
> "byte write turns into a read-and-masked-write", even if I don't think
> anybody ever noticed (we did fix cases where people _did_ notice,
> though, and we might still have some cases where we use 'int' for
> booleans because of alpha issues.).
This is in fact a real bug in the code in question that no amount
of READ_ONCE/WRITE_ONCE would have caught. The field fqdir->dead is
declared as boolean so writing to it is not atomic (on old Alphas).
I don't think it currently matters because padding would ensure
that it is in fact 64 bits long. However, should someone add another
char/bool/bitfield in this struct in future it could become an issue.
So let's fix it.
There is common knowledge among us programmers that bit fields
(or bool) sharing a common 'word' need to be protected
with a common lock.
Converting all bit fields to plain int/long would be quite a waste of memory.
In this case, fqdir_exit() is called right before the whole
struct fqdir is dismantled, and the only cpu that could possibly
change the thing is ourself, and we are going to start an RCU grace period.
Note that first cache line in 'struct fqdir' is read-only.
Only ->dead field is flipped to one at exit time.
Your patch would send a strong signal to programmers to not even try using
bit fields.
Do we really want that ?
---8<--
The field fqdir->dead is meant to be written (and read) atomically.
As old Alpha CPUs can't write a single byte atomically, we need at
least an int for it to work.
Signed-off-by: Herbert Xu <herbert(a)gondor.apana.org.au>
diff --git a/include/net/inet_frag.h b/include/net/inet_frag.h
index e91b79ad4e4a..8c458fba74ad 100644
--- a/include/net/inet_frag.h
+++ b/include/net/inet_frag.h
@@ -14,7 +14,9 @@ struct fqdir {
int max_dist;
struct inet_frags *f;
struct net *net;
- bool dead;
+
+ /* We can't use boolean because this needs atomic writes. */
+ int dead;
struct rhashtable rhashtable ____cacheline_aligned_in_smp;
diff --git a/net/ipv4/inet_fragment.c b/net/ipv4/inet_fragment.c
index 35e9784fab4e..05aa7c145817 100644
--- a/net/ipv4/inet_fragment.c
+++ b/net/ipv4/inet_fragment.c
@@ -193,7 +193,7 @@ void fqdir_exit(struct fqdir *fqdir)
{
fqdir->high_thresh = 0; /* prevent creation of new frags */
- fqdir->dead = true;
+ fqdir->dead = 1;
/* call_rcu is supposed to provide memory barrier semantics,
* separating the setting of fqdir->dead with the destruction
1:32 a.m.
New subject: inet: frags: Turn fqdir->dead into an int for old Alphas
On Fri, Jun 07, 2019 at 08:26:12AM -0700, Eric Dumazet wrote:
There is common knowledge among us programmers that bit fields
(or bool) sharing a common 'word' need to be protected
with a common lock.
Converting all bit fields to plain int/long would be quite a waste of memory.
In this case, fqdir_exit() is called right before the whole
struct fqdir is dismantled, and the only cpu that could possibly
change the thing is ourself, and we are going to start an RCU grace period.
Note that first cache line in 'struct fqdir' is read-only.
Only ->dead field is flipped to one at exit time.
Your patch would send a strong signal to programmers to not even try using
bit fields.
Do we really want that ?
If this were a bitfield then I'd think it would be safer because
anybody adding a new bitfield is unlikely to try modifying both
fields without locking or atomic ops.
However, because this is a boolean, I can certainly see someone
else coming along and adding another bool right next to it and
expecting writes them to still be atomic.
As it stands, my patch has zero impact on memory usage because
it's simply using existing padding. Should this become an issue
in future, we can always revisit this and use a more appropriate
method of addressing it.
But the point is to alert future developers that this field is
not an ordinary boolean.
Cheers,
--
Email: Herbert Xu <herbert(a)gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
2:13 a.m.
New subject: inet: frags: Turn fqdir->dead into an int for old Alphas
On 6/7/19 8:32 AM, Herbert Xu wrote:
On Fri, Jun 07, 2019 at 08:26:12AM -0700, Eric Dumazet wrote:
>
> There is common knowledge among us programmers that bit fields
> (or bool) sharing a common 'word' need to be protected
> with a common lock.
>
> Converting all bit fields to plain int/long would be quite a waste of memory.
>
> In this case, fqdir_exit() is called right before the whole
> struct fqdir is dismantled, and the only cpu that could possibly
> change the thing is ourself, and we are going to start an RCU grace period.
>
> Note that first cache line in 'struct fqdir' is read-only.
> Only ->dead field is flipped to one at exit time.
>
> Your patch would send a strong signal to programmers to not even try using
> bit fields.
>
> Do we really want that ?
If this were a bitfield then I'd think it would be safer because
anybody adding a new bitfield is unlikely to try modifying both
fields without locking or atomic ops.
However, because this is a boolean, I can certainly see someone
else coming along and adding another bool right next to it and
expecting writes them to still be atomic.
As it stands, my patch has zero impact on memory usage because
it's simply using existing padding. Should this become an issue
in future, we can always revisit this and use a more appropriate
method of addressing it.
But the point is to alert future developers that this field is
not an ordinary boolean.
Okay, but you added a quite redundant comment.
/* We can't use boolean because this needs atomic writes. */
Should we add a similar comment in front of all bit-fields,
or could we factorize this in a proper Documentation perhaps ?
Can we just add a proper bit-field and not the comment ?
unsigned int dead:1;
This way, next programmer can just apply normal rules to add a new bit.
Thanks !
2:19 a.m.
New subject: inet: frags: Turn fqdir->dead into an int for old Alphas
On Fri, Jun 7, 2019 at 8:26 AM Eric Dumazet <eric.dumazet(a)gmail.com> wrote:
There is common knowledge among us programmers that bit fields
(or bool) sharing a common 'word' need to be protected
with a common lock.
Converting all bit fields to plain int/long would be quite a waste of memory.
Yeah, and we really don't care about alpha. So 'char' should be safe.
No compiler actually turns a 'bool' in a struct into a bitfield,
afaik, because you're still supposed to be able to take the address of
a boolean.
But on the whole, I do not believe that we should ever use 'bool' in
structures anyway, because it's such a badly defined type. I think
it's 'char' in practice on just about all architectures, but there
really were traditional use cases where 'bool' was int.
But:
- we shouldn't turn them into 'int' anyway - alpha is dead, and no
sane architecture will make the same mistake anyway. People learnt.
- we might want to make sure 'bool' really is 'char' in practice, to
double-check that fthe compiler doesn't do anything stupid.
- bitfields obviously do need locks. 'char' does not.
If there's somebody who really notices the alpha issue in PRACTICE, we
can then bother to fix it. But there is approximately one user, and
it's not a heavy-duty one.
Linus
2:51 p.m.
New subject: rcu_read_lock lost its compiler barrier
On Tue, Jun 04, 2019 at 10:44:18AM -0400, Alan Stern wrote:
Currently the LKMM says the test is allowed and there is a data race,
but this answer clearly is wrong since it would violate the RCU
guarantee.
Thank you! This is what I tried to say all along in this thread
but you expressed it in a much better way :)
--
Email: Herbert Xu <herbert(a)gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
1199
days inactive
1202
days old
9 comments
4 participants
participants (4)
-
Alan Stern -
Eric Dumazet -
Herbert Xu -
Linus Torvalds