Re: bit fields && data tearing

Re: bit fields && data tearing

[Peter Hurley]

[ +cc linux-alpha ]

On 09/04/2014 06:14 PM, H. Peter Anvin wrote:
> On 09/04/2014 02:52 AM, Benjamin Herrenschmidt wrote:
>>
>> Yeah correct, alpha and bytes right ? Is there any other ? That's why I
>> suggested int.
>>
> 
> Even for Alpha it is only the 21064 AFAIK.

For -mcpu=ev5 (21164) and the following test

struct x {
	long a;
	char b;
	char c;
	char d;
	char e;
};

void store_b(struct x *p) {
	p->b = 1;
}

gcc generates:

void store_b(struct x *p) {
   0:	08 00 30 a0 	ldl	t0,8(a0)
   4:	01 f1 3f 44 	andnot	t0,0xff,t0
   8:	01 34 20 44 	or	t0,0x1,t0
   c:	08 00 30 b0 	stl	t0,8(a0)
  10:	01 80 fa 6b 	ret

IOW, rmw on 3 adjacent bytes, which is bad :)
For -mcpu=ev56 (21164A), the generated code is:

void store_b(struct x *p) {
   0:	01 00 3f 20 	lda	t0,1
   4:	08 00 30 38 	stb	t0,8(a0)
   8:	01 80 fa 6b 	ret

which is ok.
I have no idea how prevalent the ev56 is compared to the ev5.
Still we're talking about a chip that came out in 1996.

I still hate split caches though.

Regards,
Peter Hurley

Re: bit fields && data tearing

[Peter Hurley]

[ +cc linux-alpha ]

Hi Paul,

On 09/04/2014 08:17 PM, Paul E. McKenney wrote:
> On Thu, Sep 04, 2014 at 03:16:03PM -0700, H. Peter Anvin wrote:
>> On 09/04/2014 12:42 PM, Peter Hurley wrote:
>>>
>>> Or we could give up on the Alpha.
>>>
>>
>> If Alpha is turning into Voyager (kept alive only as a museum piece, but
>> actively causing problems) then please let's kill it.
> 
> Sorry for being slow to join this thread, but I propose the following
> patch.  If we can remove support for all CPUs that to not support
> direct access to bytes and shorts (which I would very much like to
> see happen), I will remove the last non-guarantee.
> 
> 							Thanx, Paul

Although I don't mind the patch below, I don't think the bitfield thing
happened because anyone was confused about what the compiler would do;
here, it's more a case of legacy code that came out from under the
Big Kernel Lock and the bitfield was an oversight.

However, my patch to fix it by splitting the bitfield into 4 bytes
was rejected as insufficient to prevent accidental sharing. This is
what spun off the Alpha discussion about non-atomic byte updates.

FWIW, there are a bunch of problems with both the documentation and
kernel code if adjacent bytes can be overwritten by a single byte write.

Documentation/atomic-ops.txt claims that properly aligned chars are
atomic in the same sense that ints are, which is not true on the Alpha
(hopefully not a possible optimization on other arches -- I tried
with the ia64 cross compiler but it stuck with byte-sized writes).

Pretty much any large aggregate kernel structure is bound to have some
byte-size fields that are either lockless or serialized by different
locks, which may be corrupted by concurrent updates to adjacent data.
IOW, ACCESS_ONCE(), spinlocks, whatever, doesn't prevent adjacent
byte-sized data from being overwritten. I haven't bothered to count
how many global bools/chars there are and whether they might be
overwritten by adjacent updates.

Documentation/circular-buffers.txt and any lockless implementation based
on or similar to it for bytes or shorts will be corrupted if the head
nears the tail.

I'm sure there's other interesting outcomes that haven't come to light.

I think that 'naturally aligned scalar writes are atomic' should be the
minimum arch guarantee.

Regards,
Peter Hurley


> ------------------------------------------------------------------------
> 
> documentation: Record limitations of bitfields and small variables
> 
> This commit documents the fact that it is not safe to use bitfields
> as shared variables in synchronization algorithms.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index 87be0a8a78de..a28bfe4fd759 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -269,6 +269,26 @@ And there are a number of things that _must_ or _must_not_ be assumed:
>  	STORE *(A + 4) = Y; STORE *A = X;
>  	STORE {*A, *(A + 4) } = {X, Y};
>  
> +And there are anti-guarantees:
> +
> + (*) These guarantees do not apply to bitfields, because compilers often
> +     generate code to modify these using non-atomic read-modify-write
> +     sequences.  Do not attempt to use bitfields to synchronize parallel
> +     algorithms.
> +
> + (*) Even in cases where bitfields are protected by locks, all fields
> +     in a given bitfield must be protected by one lock.  If two fields
> +     in a given bitfield are protected by different locks, the compiler's
> +     non-atomic read-modify-write sequences can cause an update to one
> +     field to corrupt the value of an adjacent field.
> +
> + (*) These guarantees apply only to properly aligned and sized scalar
> +     variables.  "Properly sized" currently means "int" and "long",
> +     because some CPU families do not support loads and stores of
> +     other sizes.  ("Some CPU families" is currently believed to
> +     be only Alpha 21064.  If this is actually the case, a different
> +     non-guarantee is likely to be formulated.)
> +
>  
>  =========================
>  WHAT ARE MEMORY BARRIERS?
 

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/04/2014 05:59 PM, Peter Hurley wrote:
> I have no idea how prevalent the ev56 is compared to the ev5.
> Still we're talking about a chip that came out in 1996.

Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
suffix (EV5).  However, we're still talking about museum pieces here.

I wonder what the one I have in my garage is... I'm sure I could emulate
it faster, though.

	-hpa

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/04/2014 05:59 PM, Peter Hurley wrote:
> I have no idea how prevalent the ev56 is compared to the ev5.
> Still we're talking about a chip that came out in 1996.

Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
suffix (EV5).  However, we're still talking about museum pieces here.

I wonder what the one I have in my garage is... I'm sure I could emulate
it faster, though.

	-hpa


_______________________________________________
Linuxppc-dev mailing list
Linuxppc-dev@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/linuxppc-dev

Re: bit fields && data tearing

[Michael Cree]

On Thu, Sep 04, 2014 at 07:08:48PM -0700, H. Peter Anvin wrote:
> On 09/04/2014 05:59 PM, Peter Hurley wrote:
> > I have no idea how prevalent the ev56 is compared to the ev5.
> > Still we're talking about a chip that came out in 1996.
> 
> Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
> were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
> suffix (EV5).  However, we're still talking about museum pieces here.

Yes, that is correct, EV56 is the first Alpha CPU to have the byte-word
extension (BWX) CPU instructions.

It would not worry me if the kernel decided to assume atomic aligned
scalar accesses for all arches, thus terminating support for Alphas
without BWX.

The X server, ever since the libpciaccess change, does not work on
Alphas without BWX.

Debian Alpha (pretty much up to date at Debian-Ports) is still compiled
for all Alphas, i.e., without BWX.  The last attempt to start compiling
Debian Alpha with BWX, about three years ago when Alpha was kicked out
to Debian-Ports resulted in a couple or so complaints so got nowhere.
It's frustrating supporting the lowest common demoninator as many of
the bugs specific to Alpha can be resolved by recompiling with the BWX.
The kernel no longer supporting Alphas without BWX might just be the
incentive we need to switch Debian Alpha to compiling with BWX.

Cheers
Michael.
_______________________________________________
Linuxppc-dev mailing list
Linuxppc-dev@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/linuxppc-dev

Re: bit fields && data tearing

[Peter Hurley]

On 09/04/2014 10:08 PM, H. Peter Anvin wrote:
> On 09/04/2014 05:59 PM, Peter Hurley wrote:
>> I have no idea how prevalent the ev56 is compared to the ev5.
>> Still we're talking about a chip that came out in 1996.
> 
> Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
> were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
> suffix (EV5).  However, we're still talking about museum pieces here.
> 
> I wonder what the one I have in my garage is... I'm sure I could emulate
> it faster, though.

Which is a bit ironic because I remember when Digital had a team
working on emulating native x86 apps on Alpha/NT.

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/05/2014 08:31 AM, Peter Hurley wrote:
> 
> Which is a bit ironic because I remember when Digital had a team
> working on emulating native x86 apps on Alpha/NT.
> 

Right, because the x86 architecture was obsolete and would never scale...

	-hpa

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 08:16:48PM +1200, Michael Cree wrote:
> On Thu, Sep 04, 2014 at 07:08:48PM -0700, H. Peter Anvin wrote:
> > On 09/04/2014 05:59 PM, Peter Hurley wrote:
> > > I have no idea how prevalent the ev56 is compared to the ev5.
> > > Still we're talking about a chip that came out in 1996.
> > 
> > Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
> > were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
> > suffix (EV5).  However, we're still talking about museum pieces here.
> 
> Yes, that is correct, EV56 is the first Alpha CPU to have the byte-word
> extension (BWX) CPU instructions.
> 
> It would not worry me if the kernel decided to assume atomic aligned
> scalar accesses for all arches, thus terminating support for Alphas
> without BWX.
> 
> The X server, ever since the libpciaccess change, does not work on
> Alphas without BWX.
> 
> Debian Alpha (pretty much up to date at Debian-Ports) is still compiled
> for all Alphas, i.e., without BWX.  The last attempt to start compiling
> Debian Alpha with BWX, about three years ago when Alpha was kicked out
> to Debian-Ports resulted in a couple or so complaints so got nowhere.
> It's frustrating supporting the lowest common demoninator as many of
> the bugs specific to Alpha can be resolved by recompiling with the BWX.
> The kernel no longer supporting Alphas without BWX might just be the
> incentive we need to switch Debian Alpha to compiling with BWX.

Very good, then I update my patch as follows.  Thoughts?

							Thanx, Paul

------------------------------------------------------------------------

documentation: Record limitations of bitfields and small variables

This commit documents the fact that it is not safe to use bitfields as
shared variables in synchronization algorithms.  It also documents that
CPUs must provide one-byte and two-byte load and store instructions
in order to be supported by the Linux kernel.  (Michael Cree
has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
https://lkml.org/lkml/2014/9/5/143.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 87be0a8a78de..455df6b298f7 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -269,6 +269,30 @@ And there are a number of things that _must_ or _must_not_ be assumed:
 	STORE *(A + 4) = Y; STORE *A = X;
 	STORE {*A, *(A + 4) } = {X, Y};
 
+And there are anti-guarantees:
+
+ (*) These guarantees do not apply to bitfields, because compilers often
+     generate code to modify these using non-atomic read-modify-write
+     sequences.  Do not attempt to use bitfields to synchronize parallel
+     algorithms.
+
+ (*) Even in cases where bitfields are protected by locks, all fields
+     in a given bitfield must be protected by one lock.  If two fields
+     in a given bitfield are protected by different locks, the compiler's
+     non-atomic read-modify-write sequences can cause an update to one
+     field to corrupt the value of an adjacent field.
+
+ (*) These guarantees apply only to properly aligned and sized scalar
+     variables.  "Properly sized" currently means variables that are the
+     same size as "char", "short", "int" and "long".  "Properly aligned"
+     means the natural alignment, thus no constraints for "char",
+     two-byte alignment for "short", four-byte alignment for "int",
+     and either four-byte or eight-byte alignment for "long", on 32-bit
+     and 64-bit systems, respectively.  Note that this means that the
+     Linux kernel does not support pre-EV56 Alpha CPUs, because these
+     older CPUs do not provide one-byte and two-byte loads and stores.
+     Alpha EV56 and later Alpha CPUs are still supported.
+
 
 =========================
 WHAT ARE MEMORY BARRIERS?

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 11:09:50AM -0700, Paul E. McKenney wrote:
> On Fri, Sep 05, 2014 at 08:16:48PM +1200, Michael Cree wrote:
> > On Thu, Sep 04, 2014 at 07:08:48PM -0700, H. Peter Anvin wrote:
> > > On 09/04/2014 05:59 PM, Peter Hurley wrote:
> > > > I have no idea how prevalent the ev56 is compared to the ev5.
> > > > Still we're talking about a chip that came out in 1996.
> > > 
> > > Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
> > > were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
> > > suffix (EV5).  However, we're still talking about museum pieces here.
> > 
> > Yes, that is correct, EV56 is the first Alpha CPU to have the byte-word
> > extension (BWX) CPU instructions.
> > 
> > It would not worry me if the kernel decided to assume atomic aligned
> > scalar accesses for all arches, thus terminating support for Alphas
> > without BWX.
> > 
> > The X server, ever since the libpciaccess change, does not work on
> > Alphas without BWX.
> > 
> > Debian Alpha (pretty much up to date at Debian-Ports) is still compiled
> > for all Alphas, i.e., without BWX.  The last attempt to start compiling
> > Debian Alpha with BWX, about three years ago when Alpha was kicked out
> > to Debian-Ports resulted in a couple or so complaints so got nowhere.
> > It's frustrating supporting the lowest common demoninator as many of
> > the bugs specific to Alpha can be resolved by recompiling with the BWX.
> > The kernel no longer supporting Alphas without BWX might just be the
> > incentive we need to switch Debian Alpha to compiling with BWX.
> 
> Very good, then I update my patch as follows.  Thoughts?

And, while I am at it, fix smp_load_acquire() and smp_store_release()
to allow single-byte and double-byte accesses.  (Adding Peter Zijlstra
on CC.)

							Thanx, Paul

------------------------------------------------------------------------

compiler: Allow 1- and 2-byte smp_load_acquire() and smp_store_release()

CPUs without single-byte and double-byte loads and stores place some
"interesting" requirements on concurrent code.  For example (adapted
from Peter Hurley's test code), suppose we have the following structure:
    
    	struct foo {
    		spinlock_t lock1;
    		spinlock_t lock2;
    		char a; /* Protected by lock1. */
    		char b; /* Protected by lock2. */
    	};
    	struct foo *foop;
    
Of course, it is common (and good) practice to place data protected
by different locks in separate cache lines.  However, if the locks are
rarely acquired (for example, only in rare error cases), and there are
a great many instances of the data structure, then memory footprint can
trump false-sharing concerns, so that it can be better to place them in
the same cache cache line as above.

But if the CPU does not support single-byte loads and stores, a store
to foop->a will do a non-atomic read-modify-write operation on foop->b,
which will come as a nasty surprise to someone holding foop->lock2.  So we
now require CPUs to support single-byte and double-byte loads and stores.
Therefore, this commit adjusts the definition of __native_word() to allow
these sizes to be used by smp_load_acquire() and smp_store_release().

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>

diff --git a/include/linux/compiler.h b/include/linux/compiler.h
index d5ad7b1118fc..934a834ab9f9 100644
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -311,7 +311,7 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
 
 /* Is this type a native word size -- useful for atomic operations */
 #ifndef __native_word
-# define __native_word(t) (sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
+# define __native_word(t) (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
 #endif
 
 /* Compile time object size, -1 for unknown */

Re: bit fields && data tearing

[Peter Hurley]

On 09/05/2014 02:09 PM, Paul E. McKenney wrote:
> On Fri, Sep 05, 2014 at 08:16:48PM +1200, Michael Cree wrote:
>> On Thu, Sep 04, 2014 at 07:08:48PM -0700, H. Peter Anvin wrote:
>>> On 09/04/2014 05:59 PM, Peter Hurley wrote:
>>>> I have no idea how prevalent the ev56 is compared to the ev5.
>>>> Still we're talking about a chip that came out in 1996.
>>>
>>> Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
>>> were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
>>> suffix (EV5).  However, we're still talking about museum pieces here.
>>
>> Yes, that is correct, EV56 is the first Alpha CPU to have the byte-word
>> extension (BWX) CPU instructions.
>>
>> It would not worry me if the kernel decided to assume atomic aligned
>> scalar accesses for all arches, thus terminating support for Alphas
>> without BWX.
>>
>> The X server, ever since the libpciaccess change, does not work on
>> Alphas without BWX.
>>
>> Debian Alpha (pretty much up to date at Debian-Ports) is still compiled
>> for all Alphas, i.e., without BWX.  The last attempt to start compiling
>> Debian Alpha with BWX, about three years ago when Alpha was kicked out
>> to Debian-Ports resulted in a couple or so complaints so got nowhere.
>> It's frustrating supporting the lowest common demoninator as many of
>> the bugs specific to Alpha can be resolved by recompiling with the BWX.
>> The kernel no longer supporting Alphas without BWX might just be the
>> incentive we need to switch Debian Alpha to compiling with BWX.
> 
> Very good, then I update my patch as follows.  Thoughts?
> 
> 							Thanx, Paul

Minor [optional] edits.

Thanks,
Peter Hurley

> ------------------------------------------------------------------------
> 
> documentation: Record limitations of bitfields and small variables
> 
> This commit documents the fact that it is not safe to use bitfields as
> shared variables in synchronization algorithms.  It also documents that
> CPUs must provide one-byte and two-byte load and store instructions
                   ^
                atomic
> in order to be supported by the Linux kernel.  (Michael Cree
> has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
> https://lkml.org/lkml/2014/9/5/143.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index 87be0a8a78de..455df6b298f7 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -269,6 +269,30 @@ And there are a number of things that _must_ or _must_not_ be assumed:
>  	STORE *(A + 4) = Y; STORE *A = X;
>  	STORE {*A, *(A + 4) } = {X, Y};
>  
> +And there are anti-guarantees:
> +
> + (*) These guarantees do not apply to bitfields, because compilers often
> +     generate code to modify these using non-atomic read-modify-write
> +     sequences.  Do not attempt to use bitfields to synchronize parallel
> +     algorithms.
> +
> + (*) Even in cases where bitfields are protected by locks, all fields
> +     in a given bitfield must be protected by one lock.  If two fields
> +     in a given bitfield are protected by different locks, the compiler's
> +     non-atomic read-modify-write sequences can cause an update to one
> +     field to corrupt the value of an adjacent field.
> +
> + (*) These guarantees apply only to properly aligned and sized scalar
> +     variables.  "Properly sized" currently means variables that are the
> +     same size as "char", "short", "int" and "long".  "Properly aligned"
> +     means the natural alignment, thus no constraints for "char",
> +     two-byte alignment for "short", four-byte alignment for "int",
> +     and either four-byte or eight-byte alignment for "long", on 32-bit
> +     and 64-bit systems, respectively.  Note that this means that the
> +     Linux kernel does not support pre-EV56 Alpha CPUs, because these
> +     older CPUs do not provide one-byte and two-byte loads and stores.
                                 ^
                            non-atomic
> +     Alpha EV56 and later Alpha CPUs are still supported.
> +
>  
>  =========================
>  WHAT ARE MEMORY BARRIERS?
> 

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 02:50:31PM -0400, Peter Hurley wrote:
> On 09/05/2014 02:09 PM, Paul E. McKenney wrote:
> > On Fri, Sep 05, 2014 at 08:16:48PM +1200, Michael Cree wrote:
> >> On Thu, Sep 04, 2014 at 07:08:48PM -0700, H. Peter Anvin wrote:
> >>> On 09/04/2014 05:59 PM, Peter Hurley wrote:
> >>>> I have no idea how prevalent the ev56 is compared to the ev5.
> >>>> Still we're talking about a chip that came out in 1996.
> >>>
> >>> Ah yes, I stand corrected.  According to Wikipedia, the affected CPUs
> >>> were all the 2106x CPUs (EV4, EV45, LCA4, LCA45) plus the 21164 with no
> >>> suffix (EV5).  However, we're still talking about museum pieces here.
> >>
> >> Yes, that is correct, EV56 is the first Alpha CPU to have the byte-word
> >> extension (BWX) CPU instructions.
> >>
> >> It would not worry me if the kernel decided to assume atomic aligned
> >> scalar accesses for all arches, thus terminating support for Alphas
> >> without BWX.
> >>
> >> The X server, ever since the libpciaccess change, does not work on
> >> Alphas without BWX.
> >>
> >> Debian Alpha (pretty much up to date at Debian-Ports) is still compiled
> >> for all Alphas, i.e., without BWX.  The last attempt to start compiling
> >> Debian Alpha with BWX, about three years ago when Alpha was kicked out
> >> to Debian-Ports resulted in a couple or so complaints so got nowhere.
> >> It's frustrating supporting the lowest common demoninator as many of
> >> the bugs specific to Alpha can be resolved by recompiling with the BWX.
> >> The kernel no longer supporting Alphas without BWX might just be the
> >> incentive we need to switch Debian Alpha to compiling with BWX.
> > 
> > Very good, then I update my patch as follows.  Thoughts?
> > 
> > 							Thanx, Paul
> 
> Minor [optional] edits.
> 
> Thanks,
> Peter Hurley
> 
> > ------------------------------------------------------------------------
> > 
> > documentation: Record limitations of bitfields and small variables
> > 
> > This commit documents the fact that it is not safe to use bitfields as
> > shared variables in synchronization algorithms.  It also documents that
> > CPUs must provide one-byte and two-byte load and store instructions
>                    ^
>                 atomic

Here you meant non-atomic?  My guess is that you are referring to the
fact that you could emulate a one-byte store on pre-EV56 Alpha CPUs
using the ll and sc atomic-read-modify-write instructions, correct?

> > in order to be supported by the Linux kernel.  (Michael Cree
> > has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
> > https://lkml.org/lkml/2014/9/5/143.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > 
> > diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> > index 87be0a8a78de..455df6b298f7 100644
> > --- a/Documentation/memory-barriers.txt
> > +++ b/Documentation/memory-barriers.txt
> > @@ -269,6 +269,30 @@ And there are a number of things that _must_ or _must_not_ be assumed:
> >  	STORE *(A + 4) = Y; STORE *A = X;
> >  	STORE {*A, *(A + 4) } = {X, Y};
> >  
> > +And there are anti-guarantees:
> > +
> > + (*) These guarantees do not apply to bitfields, because compilers often
> > +     generate code to modify these using non-atomic read-modify-write
> > +     sequences.  Do not attempt to use bitfields to synchronize parallel
> > +     algorithms.
> > +
> > + (*) Even in cases where bitfields are protected by locks, all fields
> > +     in a given bitfield must be protected by one lock.  If two fields
> > +     in a given bitfield are protected by different locks, the compiler's
> > +     non-atomic read-modify-write sequences can cause an update to one
> > +     field to corrupt the value of an adjacent field.
> > +
> > + (*) These guarantees apply only to properly aligned and sized scalar
> > +     variables.  "Properly sized" currently means variables that are the
> > +     same size as "char", "short", "int" and "long".  "Properly aligned"
> > +     means the natural alignment, thus no constraints for "char",
> > +     two-byte alignment for "short", four-byte alignment for "int",
> > +     and either four-byte or eight-byte alignment for "long", on 32-bit
> > +     and 64-bit systems, respectively.  Note that this means that the
> > +     Linux kernel does not support pre-EV56 Alpha CPUs, because these
> > +     older CPUs do not provide one-byte and two-byte loads and stores.
>                                  ^
>                             non-atomic

I took this, thank you!

							Thanx, Paul

> > +     Alpha EV56 and later Alpha CPUs are still supported.
> > +
> >  
> >  =========================
> >  WHAT ARE MEMORY BARRIERS?
> > 
> 

Re: bit fields && data tearing

[Peter Hurley]

On 09/05/2014 03:05 PM, Paul E. McKenney wrote:
> On Fri, Sep 05, 2014 at 02:50:31PM -0400, Peter Hurley wrote:
>> On 09/05/2014 02:09 PM, Paul E. McKenney wrote:

[cut]

>>> ------------------------------------------------------------------------
>>>
>>> documentation: Record limitations of bitfields and small variables
>>>
>>> This commit documents the fact that it is not safe to use bitfields as
>>> shared variables in synchronization algorithms.  It also documents that
>>> CPUs must provide one-byte and two-byte load and store instructions
>>                    ^
>>                 atomic
> 
> Here you meant non-atomic?  My guess is that you are referring to the
> fact that you could emulate a one-byte store on pre-EV56 Alpha CPUs
> using the ll and sc atomic-read-modify-write instructions, correct?

Yes, that's what I meant. I must be tired and am misreading the commit
message, or misinterpreting it's meaning.

RE: bit fields && data tearing

[Marc Gauthier]

Paul E. McKenney wrote:
>On Fri, Sep 05, 2014 at 02:50:31PM -0400, Peter Hurley wrote:
>>On 09/05/2014 02:09 PM, Paul E. McKenney wrote:
>>> This commit documents the fact that it is not safe to use bitfields as
>>> shared variables in synchronization algorithms.  It also documents that
>>> CPUs must provide one-byte and two-byte load and store instructions
>>                    ^
>>                 atomic
> 
> Here you meant non-atomic?  My guess is that you are referring to the
> fact that you could emulate a one-byte store on pre-EV56 Alpha CPUs
> using the ll and sc atomic-read-modify-write instructions, correct?
> 
>>> in order to be supported by the Linux kernel.  (Michael Cree
>>> has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
>>> https://lkml.org/lkml/2014/9/5/143.
[...]

>>> +     and 64-bit systems, respectively.  Note that this means that the
>>> +     Linux kernel does not support pre-EV56 Alpha CPUs, because these
>>> +     older CPUs do not provide one-byte and two-byte loads and stores.
>>                                  ^
>>                             non-atomic
> 
> I took this, thank you!

Eum, am I totally lost, or aren't both of these supposed to say "atomic" ?

Can't imagine requiring a CPU to provide non-atomic loads and stores
(i.e. requiring old Alpha behavior?).

-Marc

Re: bit fields && data tearing

[Peter Zijlstra]

On Fri, Sep 05, 2014 at 11:31:09AM -0700, Paul E. McKenney wrote:
> compiler: Allow 1- and 2-byte smp_load_acquire() and smp_store_release()
> 
> CPUs without single-byte and double-byte loads and stores place some
> "interesting" requirements on concurrent code.  For example (adapted
> from Peter Hurley's test code), suppose we have the following structure:
>     
>     	struct foo {
>     		spinlock_t lock1;
>     		spinlock_t lock2;
>     		char a; /* Protected by lock1. */
>     		char b; /* Protected by lock2. */
>     	};
>     	struct foo *foop;
>     
> Of course, it is common (and good) practice to place data protected
> by different locks in separate cache lines.  However, if the locks are
> rarely acquired (for example, only in rare error cases), and there are
> a great many instances of the data structure, then memory footprint can
> trump false-sharing concerns, so that it can be better to place them in
> the same cache cache line as above.
> 
> But if the CPU does not support single-byte loads and stores, a store
> to foop->a will do a non-atomic read-modify-write operation on foop->b,
> which will come as a nasty surprise to someone holding foop->lock2.  So we
> now require CPUs to support single-byte and double-byte loads and stores.
> Therefore, this commit adjusts the definition of __native_word() to allow
> these sizes to be used by smp_load_acquire() and smp_store_release().

So does this patch depends on a patch that removes pre EV56 alpha
support? I'm all for removing that, but I need to see the patch merged
before we can do this.

Re: bit fields && data tearing

[Peter Hurley]

On 09/05/2014 03:52 PM, Peter Zijlstra wrote:
> On Fri, Sep 05, 2014 at 11:31:09AM -0700, Paul E. McKenney wrote:
>> compiler: Allow 1- and 2-byte smp_load_acquire() and smp_store_release()
>>
>> CPUs without single-byte and double-byte loads and stores place some
>> "interesting" requirements on concurrent code.  For example (adapted
>> from Peter Hurley's test code), suppose we have the following structure:
>>     
>>     	struct foo {
>>     		spinlock_t lock1;
>>     		spinlock_t lock2;
>>     		char a; /* Protected by lock1. */
>>     		char b; /* Protected by lock2. */
>>     	};
>>     	struct foo *foop;
>>     
>> Of course, it is common (and good) practice to place data protected
>> by different locks in separate cache lines.  However, if the locks are
>> rarely acquired (for example, only in rare error cases), and there are
>> a great many instances of the data structure, then memory footprint can
>> trump false-sharing concerns, so that it can be better to place them in
>> the same cache cache line as above.
>>
>> But if the CPU does not support single-byte loads and stores, a store
>> to foop->a will do a non-atomic read-modify-write operation on foop->b,
>> which will come as a nasty surprise to someone holding foop->lock2.  So we
>> now require CPUs to support single-byte and double-byte loads and stores.
>> Therefore, this commit adjusts the definition of __native_word() to allow
>> these sizes to be used by smp_load_acquire() and smp_store_release().
> 
> So does this patch depends on a patch that removes pre EV56 alpha
> support? I'm all for removing that, but I need to see the patch merged
> before we can do this.

I'm working on that but Alpha's Kconfig is not quite straightforward.


... and I'm wondering if I should _remove_ pre-EV56 configurations or
move the default choice and produce a warning about unsupported Alpha
CPUs instead?

Regards,
Peter Hurley

[ How does one do a red popup in kbuild?
  The 'comment' approach is too subtle.
]

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 03:24:35PM -0400, Peter Hurley wrote:
> On 09/05/2014 03:05 PM, Paul E. McKenney wrote:
> > On Fri, Sep 05, 2014 at 02:50:31PM -0400, Peter Hurley wrote:
> >> On 09/05/2014 02:09 PM, Paul E. McKenney wrote:
> 
> [cut]
> 
> >>> ------------------------------------------------------------------------
> >>>
> >>> documentation: Record limitations of bitfields and small variables
> >>>
> >>> This commit documents the fact that it is not safe to use bitfields as
> >>> shared variables in synchronization algorithms.  It also documents that
> >>> CPUs must provide one-byte and two-byte load and store instructions
> >>                    ^
> >>                 atomic
> > 
> > Here you meant non-atomic?  My guess is that you are referring to the
> > fact that you could emulate a one-byte store on pre-EV56 Alpha CPUs
> > using the ll and sc atomic-read-modify-write instructions, correct?
> 
> Yes, that's what I meant. I must be tired and am misreading the commit
> message, or misinterpreting it's meaning.

Very good, got it!

							Thanx, Paul

_______________________________________________
Linuxppc-dev mailing list
Linuxppc-dev@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/linuxppc-dev

Re: bit fields && data tearing

[Peter Zijlstra]

On Fri, Sep 05, 2014 at 04:01:35PM -0400, Peter Hurley wrote:
> > So does this patch depends on a patch that removes pre EV56 alpha
> > support? I'm all for removing that, but I need to see the patch merged
> > before we can do this.
> 
> I'm working on that but Alpha's Kconfig is not quite straightforward.
> 
> 
> ... and I'm wondering if I should _remove_ pre-EV56 configurations or
> move the default choice and produce a warning about unsupported Alpha
> CPUs instead?
> 

 depends BROKEN 

or is that deprecated?

Re: bit fields && data tearing

[Peter Hurley]

On 09/05/2014 03:38 PM, Marc Gauthier wrote:
> Paul E. McKenney wrote:
>> On Fri, Sep 05, 2014 at 02:50:31PM -0400, Peter Hurley wrote:
>>> On 09/05/2014 02:09 PM, Paul E. McKenney wrote:
>>>> This commit documents the fact that it is not safe to use bitfields as
>>>> shared variables in synchronization algorithms.  It also documents that
>>>> CPUs must provide one-byte and two-byte load and store instructions
>>>                    ^
>>>                 atomic
>>
>> Here you meant non-atomic?  My guess is that you are referring to the
>> fact that you could emulate a one-byte store on pre-EV56 Alpha CPUs
>> using the ll and sc atomic-read-modify-write instructions, correct?
>>
>>>> in order to be supported by the Linux kernel.  (Michael Cree
>>>> has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
>>>> https://lkml.org/lkml/2014/9/5/143.
> [...]
> 
>>>> +     and 64-bit systems, respectively.  Note that this means that the
>>>> +     Linux kernel does not support pre-EV56 Alpha CPUs, because these
>>>> +     older CPUs do not provide one-byte and two-byte loads and stores.
>>>                                  ^
>>>                             non-atomic
>>
>> I took this, thank you!
> 
> Eum, am I totally lost, or aren't both of these supposed to say "atomic" ?
> 
> Can't imagine requiring a CPU to provide non-atomic loads and stores
> (i.e. requiring old Alpha behavior?).

Here's how I read the two statements.

First, the commit message:

"It [this commit] documents that CPUs [supported by the Linux kernel]
_must provide_ atomic one-byte and two-byte naturally aligned loads and stores."

Second, in the body of the document:

"The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."

Regards,
Peter Hurley

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/05/2014 01:12 PM, Peter Zijlstra wrote:
>>
>> ... and I'm wondering if I should _remove_ pre-EV56 configurations or
>> move the default choice and produce a warning about unsupported Alpha
>> CPUs instead?
>>
> 
>  depends BROKEN 
> 
> or is that deprecated?
> 

Just rip it out, like I did for the i386.

	-hpa

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 04:01:35PM -0400, Peter Hurley wrote:
> On 09/05/2014 03:52 PM, Peter Zijlstra wrote:
> > On Fri, Sep 05, 2014 at 11:31:09AM -0700, Paul E. McKenney wrote:
> >> compiler: Allow 1- and 2-byte smp_load_acquire() and smp_store_release()
> >>
> >> CPUs without single-byte and double-byte loads and stores place some
> >> "interesting" requirements on concurrent code.  For example (adapted
> >> from Peter Hurley's test code), suppose we have the following structure:
> >>     
> >>     	struct foo {
> >>     		spinlock_t lock1;
> >>     		spinlock_t lock2;
> >>     		char a; /* Protected by lock1. */
> >>     		char b; /* Protected by lock2. */
> >>     	};
> >>     	struct foo *foop;
> >>     
> >> Of course, it is common (and good) practice to place data protected
> >> by different locks in separate cache lines.  However, if the locks are
> >> rarely acquired (for example, only in rare error cases), and there are
> >> a great many instances of the data structure, then memory footprint can
> >> trump false-sharing concerns, so that it can be better to place them in
> >> the same cache cache line as above.
> >>
> >> But if the CPU does not support single-byte loads and stores, a store
> >> to foop->a will do a non-atomic read-modify-write operation on foop->b,
> >> which will come as a nasty surprise to someone holding foop->lock2.  So we
> >> now require CPUs to support single-byte and double-byte loads and stores.
> >> Therefore, this commit adjusts the definition of __native_word() to allow
> >> these sizes to be used by smp_load_acquire() and smp_store_release().
> > 
> > So does this patch depends on a patch that removes pre EV56 alpha
> > support? I'm all for removing that, but I need to see the patch merged
> > before we can do this.
> 
> I'm working on that but Alpha's Kconfig is not quite straightforward.
> 
> 
> ... and I'm wondering if I should _remove_ pre-EV56 configurations or
> move the default choice and produce a warning about unsupported Alpha
> CPUs instead?

I suspect that either would work, given that the Alpha community is
pretty close-knit.  Just setting the appropriate flag to make the
compiler generate one-byte and two-byte loads and stores would
probably suffice.  ;-)

							Thanx, Paul

> Regards,
> Peter Hurley
> 
> [ How does one do a red popup in kbuild?
>   The 'comment' approach is too subtle.
> ]
> 
> 
> 

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/05/2014 01:14 PM, Peter Hurley wrote:
> 
> Here's how I read the two statements.
> 
> First, the commit message:
> 
> "It [this commit] documents that CPUs [supported by the Linux kernel]
> _must provide_ atomic one-byte and two-byte naturally aligned loads and stores."
> 
> Second, in the body of the document:
> 
> "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> 

Does this apply in general or only to SMP configurations?  I guess
non-SMP configurations would still have problems if interrupted in the
wrong place...

	-hpa

Re: bit fields && data tearing

[Michael Cree]

On Fri, Sep 05, 2014 at 04:14:48PM -0400, Peter Hurley wrote:
> Second, in the body of the document:
> 
> "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."

Let's be clear here, the pre-EV56 Alpha CPUs do provide an atomic
one-byte and two-byte load and store; it's just that one must use
locked load and store sequences to achieve atomicity.  The point,
I think, is that the pre-EV56 Alpha CPUs provide non-atomic one-byte
and two-byte load and stores as the norm, and that is the problem.

Cheers
Michael.

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 04:14:48PM -0400, Peter Hurley wrote:
> On 09/05/2014 03:38 PM, Marc Gauthier wrote:
> > Paul E. McKenney wrote:
> >> On Fri, Sep 05, 2014 at 02:50:31PM -0400, Peter Hurley wrote:
> >>> On 09/05/2014 02:09 PM, Paul E. McKenney wrote:
> >>>> This commit documents the fact that it is not safe to use bitfields as
> >>>> shared variables in synchronization algorithms.  It also documents that
> >>>> CPUs must provide one-byte and two-byte load and store instructions
> >>>                    ^
> >>>                 atomic
> >>
> >> Here you meant non-atomic?  My guess is that you are referring to the
> >> fact that you could emulate a one-byte store on pre-EV56 Alpha CPUs
> >> using the ll and sc atomic-read-modify-write instructions, correct?
> >>
> >>>> in order to be supported by the Linux kernel.  (Michael Cree
> >>>> has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
> >>>> https://lkml.org/lkml/2014/9/5/143.
> > [...]
> > 
> >>>> +     and 64-bit systems, respectively.  Note that this means that the
> >>>> +     Linux kernel does not support pre-EV56 Alpha CPUs, because these
> >>>> +     older CPUs do not provide one-byte and two-byte loads and stores.
> >>>                                  ^
> >>>                             non-atomic
> >>
> >> I took this, thank you!
> > 
> > Eum, am I totally lost, or aren't both of these supposed to say "atomic" ?
> > 
> > Can't imagine requiring a CPU to provide non-atomic loads and stores
> > (i.e. requiring old Alpha behavior?).
> 
> Here's how I read the two statements.
> 
> First, the commit message:
> 
> "It [this commit] documents that CPUs [supported by the Linux kernel]
> _must provide_ atomic one-byte and two-byte naturally aligned loads and stores."
> 
> Second, in the body of the document:
> 
> "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."

Hmmm...  It is a bit ambiguous.  How about the following?

							Thanx, Paul

------------------------------------------------------------------------

documentation: Record limitations of bitfields and small variables

This commit documents the fact that it is not safe to use bitfields
as shared variables in synchronization algorithms.  It also documents
that CPUs must provide one-byte and two-byte normal load and store
instructions in order to be supported by the Linux kernel.  (Michael
Cree has agreed to the resulting non-support of pre-EV56 Alpha CPUs:
https://lkml.org/lkml/2014/9/5/143.)

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 87be0a8a78de..fe4d51b704c5 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -269,6 +269,37 @@ And there are a number of things that _must_ or _must_not_ be assumed:
 	STORE *(A + 4) = Y; STORE *A = X;
 	STORE {*A, *(A + 4) } = {X, Y};
 
+And there are anti-guarantees:
+
+ (*) These guarantees do not apply to bitfields, because compilers often
+     generate code to modify these using non-atomic read-modify-write
+     sequences.  Do not attempt to use bitfields to synchronize parallel
+     algorithms.
+
+ (*) Even in cases where bitfields are protected by locks, all fields
+     in a given bitfield must be protected by one lock.  If two fields
+     in a given bitfield are protected by different locks, the compiler's
+     non-atomic read-modify-write sequences can cause an update to one
+     field to corrupt the value of an adjacent field.
+
+ (*) These guarantees apply only to properly aligned and sized scalar
+     variables.  "Properly sized" currently means variables that are
+     the same size as "char", "short", "int" and "long".  "Properly
+     aligned" means the natural alignment, thus no constraints for
+     "char", two-byte alignment for "short", four-byte alignment for
+     "int", and either four-byte or eight-byte alignment for "long",
+     on 32-bit and 64-bit systems, respectively.  Note that this means
+     that the Linux kernel does not support pre-EV56 Alpha CPUs,
+     because these older CPUs do not provide one-byte and two-byte
+     load and store instructions.  (In theory, the pre-EV56 Alpha CPUs
+     can emulate these instructions using load-linked/store-conditional
+     instructions, but in practice this approach has excessive overhead.
+     Keep in mind that this emulation would be required on -all- single-
+     and double-byte loads and stores in order to handle adjacent bytes
+     protected by different locks.)
+
+     Alpha EV56 and later Alpha CPUs are still supported.
+
 
 =========================
 WHAT ARE MEMORY BARRIERS?

Re: bit fields && data tearing

[Michael Cree]

On Fri, Sep 05, 2014 at 01:34:52PM -0700, H. Peter Anvin wrote:
> On 09/05/2014 01:14 PM, Peter Hurley wrote:
> > 
> > Here's how I read the two statements.
> > 
> > First, the commit message:
> > 
> > "It [this commit] documents that CPUs [supported by the Linux kernel]
> > _must provide_ atomic one-byte and two-byte naturally aligned loads and stores."
> > 
> > Second, in the body of the document:
> > 
> > "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> > older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> > 
> 
> Does this apply in general or only to SMP configurations?  I guess
> non-SMP configurations would still have problems if interrupted in the
> wrong place...

Yes.

Cheers
Michael.

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 01:34:52PM -0700, H. Peter Anvin wrote:
> On 09/05/2014 01:14 PM, Peter Hurley wrote:
> > 
> > Here's how I read the two statements.
> > 
> > First, the commit message:
> > 
> > "It [this commit] documents that CPUs [supported by the Linux kernel]
> > _must provide_ atomic one-byte and two-byte naturally aligned loads and stores."
> > 
> > Second, in the body of the document:
> > 
> > "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> > older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> > 
> 
> Does this apply in general or only to SMP configurations?  I guess
> non-SMP configurations would still have problems if interrupted in the
> wrong place...

And preemption could cause problems, too.  So I believe that it needs
to be universal.

							Thanx, Paul

Re: bit fields && data tearing

[Thomas Gleixner]

On Fri, 5 Sep 2014, Paul E. McKenney wrote:
> On Fri, Sep 05, 2014 at 01:34:52PM -0700, H. Peter Anvin wrote:
> > On 09/05/2014 01:14 PM, Peter Hurley wrote:
> > > 
> > > Here's how I read the two statements.
> > > 
> > > First, the commit message:
> > > 
> > > "It [this commit] documents that CPUs [supported by the Linux kernel]
> > > _must provide_ atomic one-byte and two-byte naturally aligned loads and stores."
> > > 
> > > Second, in the body of the document:
> > > 
> > > "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> > > older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> > > 
> > 
> > Does this apply in general or only to SMP configurations?  I guess
> > non-SMP configurations would still have problems if interrupted in the
> > wrong place...
> 
> And preemption could cause problems, too.  So I believe that it needs
> to be universal.

Well preemption is usually caused by an interrupt, except you have a
combined load and preempt instruction :)

Thanks,

	tglx

Re: bit fields && data tearing

[Paul E. McKenney]

On Fri, Sep 05, 2014 at 10:48:34PM +0200, Thomas Gleixner wrote:
> On Fri, 5 Sep 2014, Paul E. McKenney wrote:
> > On Fri, Sep 05, 2014 at 01:34:52PM -0700, H. Peter Anvin wrote:
> > > On 09/05/2014 01:14 PM, Peter Hurley wrote:
> > > > 
> > > > Here's how I read the two statements.
> > > > 
> > > > First, the commit message:
> > > > 
> > > > "It [this commit] documents that CPUs [supported by the Linux kernel]
> > > > _must provide_ atomic one-byte and two-byte naturally aligned loads and stores."
> > > > 
> > > > Second, in the body of the document:
> > > > 
> > > > "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> > > > older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> > > > 
> > > 
> > > Does this apply in general or only to SMP configurations?  I guess
> > > non-SMP configurations would still have problems if interrupted in the
> > > wrong place...
> > 
> > And preemption could cause problems, too.  So I believe that it needs
> > to be universal.
> 
> Well preemption is usually caused by an interrupt, except you have a
> combined load and preempt instruction :)

Fair point!  ;-)

							Thanx, Paul

Re: bit fields && data tearing

[Peter Hurley]

On 09/05/2014 04:39 PM, Michael Cree wrote:
> On Fri, Sep 05, 2014 at 04:14:48PM -0400, Peter Hurley wrote:
>> Second, in the body of the document:
>>
>> "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
>> older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> 
> Let's be clear here, the pre-EV56 Alpha CPUs do provide an atomic
> one-byte and two-byte load and store; it's just that one must use
> locked load and store sequences to achieve atomicity.  The point,
> I think, is that the pre-EV56 Alpha CPUs provide non-atomic one-byte
> and two-byte load and stores as the norm, and that is the problem.

I'm all for an Alpha expert to jump in here and meet the criteria;
which is that byte stores cannot corrupt adjacent storage (nor can
aligned short stores).

To my mind, a quick look at Documentation/circular-buffers.txt will
pretty much convince anyone that trying to differentiate by execution
context is undoable.

If someone wants to make Alphas do cmpxchg loops for every byte store,
then ok. Or any other solution that doesn't require subsystem code
changes.

Regards,
Peter Hurley

Re: bit fields && data tearing

[Michael Cree]

On Fri, Sep 05, 2014 at 05:12:28PM -0400, Peter Hurley wrote:
> On 09/05/2014 04:39 PM, Michael Cree wrote:
> > On Fri, Sep 05, 2014 at 04:14:48PM -0400, Peter Hurley wrote:
> >> Second, in the body of the document:
> >>
> >> "The Linux kernel no longer supports pre-EV56 Alpha CPUs, because these
> >> older CPUs _do not provide_ atomic one-byte and two-byte loads and stores."
> > 
> > Let's be clear here, the pre-EV56 Alpha CPUs do provide an atomic
> > one-byte and two-byte load and store; it's just that one must use
> > locked load and store sequences to achieve atomicity.  The point,
> > I think, is that the pre-EV56 Alpha CPUs provide non-atomic one-byte
> > and two-byte load and stores as the norm, and that is the problem.
> 
> I'm all for an Alpha expert to jump in here and meet the criteria;
> which is that byte stores cannot corrupt adjacent storage (nor can
> aligned short stores).
> 
> To my mind, a quick look at Documentation/circular-buffers.txt will
> pretty much convince anyone that trying to differentiate by execution
> context is undoable.
> 
> If someone wants to make Alphas do cmpxchg loops for every byte store,
> then ok. Or any other solution that doesn't require subsystem code
> changes.

I am not suggesting that anyone do that work.  I'm certainly not going
to do it.

All I was pointing out is that the claim that "_do not provide_" made
above with emphasis is, strictly interpreted, not true, thus should not
be committed to the documentation without further clarification.

Cheers
Michael.

Re: bit fields && data tearing

[One Thousand Gnomes]

On Fri, 05 Sep 2014 08:41:52 -0700
"H. Peter Anvin" <hpa@zytor.com> wrote:

> On 09/05/2014 08:31 AM, Peter Hurley wrote:
> > 
> > Which is a bit ironic because I remember when Digital had a team
> > working on emulating native x86 apps on Alpha/NT.
> > 
> 
> Right, because the x86 architecture was obsolete and would never scale...

Talking about "not scaling" can anyone explain how a "you need to use
set_bit() and friends" bug report scaled into a hundred message plus
discussion about ambiguous properties of processors (and nobody has
audited all the embedded platforms we support yet, or the weirder ARMs)
and a propsal to remove Alpha support.

Wouldn't it be *much* simpler to do what I suggested in the first place
and use the existing intended for purpose, deliberately put there,
functions for atomic bitops, because they are fast on sane processors and
they work on everything else.

I think the whole "removing Alpha EV5" support is basically bonkers. Just
use set_bit in the tty layer. Alpha will continue to work as well as it
always has done and you won't design out support for any future processor
that turns out not to do byte aligned stores.

Alan

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
> On Fri, 05 Sep 2014 08:41:52 -0700
> "H. Peter Anvin" <hpa@zytor.com> wrote:
> 
>> On 09/05/2014 08:31 AM, Peter Hurley wrote:
>>>
>>> Which is a bit ironic because I remember when Digital had a team
>>> working on emulating native x86 apps on Alpha/NT.
>>>
>>
>> Right, because the x86 architecture was obsolete and would never scale...
> 
> Talking about "not scaling" can anyone explain how a "you need to use
> set_bit() and friends" bug report scaled into a hundred message plus
> discussion about ambiguous properties of processors (and nobody has
> audited all the embedded platforms we support yet, or the weirder ARMs)
> and a propsal to remove Alpha support.
> 
> Wouldn't it be *much* simpler to do what I suggested in the first place
> and use the existing intended for purpose, deliberately put there,
> functions for atomic bitops, because they are fast on sane processors and
> they work on everything else.
> 
> I think the whole "removing Alpha EV5" support is basically bonkers. Just
> use set_bit in the tty layer. Alpha will continue to work as well as it
> always has done and you won't design out support for any future processor
> that turns out not to do byte aligned stores.
> 
> Alan
> 

Is *that* what we are talking about?  I was added to this conversation
in the middle where it had already generalized, so I had no idea.

	-hpa

Re: bit fields && data tearing

[James Bottomley]

On Mon, 2014-09-08 at 18:52 +0100, One Thousand Gnomes wrote:
> On Fri, 05 Sep 2014 08:41:52 -0700
> "H. Peter Anvin" <hpa@zytor.com> wrote:
> 
> > On 09/05/2014 08:31 AM, Peter Hurley wrote:
> > > 
> > > Which is a bit ironic because I remember when Digital had a team
> > > working on emulating native x86 apps on Alpha/NT.
> > > 
> > 
> > Right, because the x86 architecture was obsolete and would never scale...
> 
> Talking about "not scaling" can anyone explain how a "you need to use
> set_bit() and friends" bug report scaled into a hundred message plus
> discussion about ambiguous properties of processors (and nobody has
> audited all the embedded platforms we support yet, or the weirder ARMs)
> and a propsal to remove Alpha support.
> 
> Wouldn't it be *much* simpler to do what I suggested in the first place
> and use the existing intended for purpose, deliberately put there,
> functions for atomic bitops, because they are fast on sane processors and
> they work on everything else.
> 
> I think the whole "removing Alpha EV5" support is basically bonkers. Just
> use set_bit in the tty layer. Alpha will continue to work as well as it
> always has done and you won't design out support for any future processor
> that turns out not to do byte aligned stores.

Seconded.  We implement via hashed spinlocks on PA ... but hey, we're
not the fastest architecture anyway and semantically it just works.

James

Re: bit fields && data tearing

[One Thousand Gnomes]

> > I think the whole "removing Alpha EV5" support is basically bonkers. Just
> > use set_bit in the tty layer. Alpha will continue to work as well as it
> > always has done and you won't design out support for any future processor
> > that turns out not to do byte aligned stores.
> > 
> > Alan
> > 
> 
> Is *that* what we are talking about?  I was added to this conversation
> in the middle where it had already generalized, so I had no idea.
> 
> 	-hpa

Yes there are some flags in the tty layer that are vulnerable to this
(although they've been vulnerable to it and missing a lock since last
century with no known ill effects).

It's not as if this is causing any work to anyone beyond using the
standard API, no API needs to change.

Alan

Re: bit fields && data tearing

[Peter Hurley]

On 09/08/2014 01:59 PM, H. Peter Anvin wrote:
> On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
>> On Fri, 05 Sep 2014 08:41:52 -0700
>> "H. Peter Anvin" <hpa@zytor.com> wrote:
>>
>>> On 09/05/2014 08:31 AM, Peter Hurley wrote:
>>>>
>>>> Which is a bit ironic because I remember when Digital had a team
>>>> working on emulating native x86 apps on Alpha/NT.
>>>>
>>>
>>> Right, because the x86 architecture was obsolete and would never scale...
>>
>> Talking about "not scaling" can anyone explain how a "you need to use
>> set_bit() and friends" bug report scaled into a hundred message plus
>> discussion about ambiguous properties of processors (and nobody has
>> audited all the embedded platforms we support yet, or the weirder ARMs)
>> and a propsal to remove Alpha support.
>>
>> Wouldn't it be *much* simpler to do what I suggested in the first place
>> and use the existing intended for purpose, deliberately put there,
>> functions for atomic bitops, because they are fast on sane processors and
>> they work on everything else.
>>
>> I think the whole "removing Alpha EV5" support is basically bonkers. Just
>> use set_bit in the tty layer. Alpha will continue to work as well as it
>> always has done and you won't design out support for any future processor
>> that turns out not to do byte aligned stores.
>>
>> Alan
>>
> 
> Is *that* what we are talking about?  I was added to this conversation
> in the middle where it had already generalized, so I had no idea.

No, this is just what brought this craziness to my attention.

For example, byte- and short-sized circular buffers could not possibly
be safe either, when the head nears the tail.

Who has audited global storage and ensured that _every_ byte-sized write
doesn't happen to be adjacent to some other storage that may not happen
to be protected by the same (or any) lock?

Regards,
Peter Hurley

Re: bit fields && data tearing

[Paul E. McKenney]

On Mon, Sep 08, 2014 at 06:47:35PM -0400, Peter Hurley wrote:
> On 09/08/2014 01:59 PM, H. Peter Anvin wrote:
> > On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
> >> On Fri, 05 Sep 2014 08:41:52 -0700
> >> "H. Peter Anvin" <hpa@zytor.com> wrote:
> >>
> >>> On 09/05/2014 08:31 AM, Peter Hurley wrote:
> >>>>
> >>>> Which is a bit ironic because I remember when Digital had a team
> >>>> working on emulating native x86 apps on Alpha/NT.
> >>>>
> >>>
> >>> Right, because the x86 architecture was obsolete and would never scale...
> >>
> >> Talking about "not scaling" can anyone explain how a "you need to use
> >> set_bit() and friends" bug report scaled into a hundred message plus
> >> discussion about ambiguous properties of processors (and nobody has
> >> audited all the embedded platforms we support yet, or the weirder ARMs)
> >> and a propsal to remove Alpha support.
> >>
> >> Wouldn't it be *much* simpler to do what I suggested in the first place
> >> and use the existing intended for purpose, deliberately put there,
> >> functions for atomic bitops, because they are fast on sane processors and
> >> they work on everything else.
> >>
> >> I think the whole "removing Alpha EV5" support is basically bonkers. Just
> >> use set_bit in the tty layer. Alpha will continue to work as well as it
> >> always has done and you won't design out support for any future processor
> >> that turns out not to do byte aligned stores.
> >>
> >> Alan
> >>
> > 
> > Is *that* what we are talking about?  I was added to this conversation
> > in the middle where it had already generalized, so I had no idea.
> 
> No, this is just what brought this craziness to my attention.
> 
> For example, byte- and short-sized circular buffers could not possibly
> be safe either, when the head nears the tail.
> 
> Who has audited global storage and ensured that _every_ byte-sized write
> doesn't happen to be adjacent to some other storage that may not happen
> to be protected by the same (or any) lock?

This was my concern as well.

							Thanx, Paul

Re: bit fields && data tearing

[Peter Hurley]

On 09/08/2014 06:47 PM, Peter Hurley wrote:
> On 09/08/2014 01:59 PM, H. Peter Anvin wrote:
>> On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
>>> On Fri, 05 Sep 2014 08:41:52 -0700
>>> "H. Peter Anvin" <hpa@zytor.com> wrote:
>>>
>>>> On 09/05/2014 08:31 AM, Peter Hurley wrote:
>>>>>
>>>>> Which is a bit ironic because I remember when Digital had a team
>>>>> working on emulating native x86 apps on Alpha/NT.
>>>>>
>>>>
>>>> Right, because the x86 architecture was obsolete and would never scale...
>>>
>>> Talking about "not scaling" can anyone explain how a "you need to use
>>> set_bit() and friends" bug report scaled into a hundred message plus
>>> discussion about ambiguous properties of processors (and nobody has
>>> audited all the embedded platforms we support yet, or the weirder ARMs)
>>> and a propsal to remove Alpha support.
>>>
>>> Wouldn't it be *much* simpler to do what I suggested in the first place
>>> and use the existing intended for purpose, deliberately put there,
>>> functions for atomic bitops, because they are fast on sane processors and
>>> they work on everything else.

And much simpler how?

By turning a 4- line patch into a 400- line patch?

And what about multi-value assignments for which set_bit() doesn't work, like
the byte-sized ->ctrl_status field? Is the expectation to submit a patch
which fixes that for a system from 1995, but already works for everything else?

The extra complexity comes with real cost; reduced reliability for every other
arch .

>>> I think the whole "removing Alpha EV5" support is basically bonkers. Just
>>> use set_bit in the tty layer. Alpha will continue to work as well as it
>>> always has done and you won't design out support for any future processor
>>> that turns out not to do byte aligned stores.

I thought the overriding design principle of this kernel was to support
what exists now, not design-in support for the future which may have
different requirements than expected anyway.


>> Is *that* what we are talking about?  I was added to this conversation
>> in the middle where it had already generalized, so I had no idea.
> 
> No, this is just what brought this craziness to my attention.
> 
> For example, byte- and short-sized circular buffers could not possibly
> be safe either, when the head nears the tail.
> 
> Who has audited global storage and ensured that _every_ byte-sized write
> doesn't happen to be adjacent to some other storage that may not happen
> to be protected by the same (or any) lock?

And add to this list all bitfields because gcc ignores the type
specifier and only allocates the minimum number of bytes to contain the
declared fields.

Regards,
Peter Hurley

Re: bit fields && data tearing

[Peter Hurley]

On 09/08/2014 03:17 PM, One Thousand Gnomes wrote:
>>> I think the whole "removing Alpha EV5" support is basically bonkers. Just
>>> use set_bit in the tty layer. Alpha will continue to work as well as it
>>> always has done and you won't design out support for any future processor
>>> that turns out not to do byte aligned stores.
>>>
>>> Alan
>>>
>>
>> Is *that* what we are talking about?  I was added to this conversation
>> in the middle where it had already generalized, so I had no idea.
>>
>> 	-hpa
> 
> Yes there are some flags in the tty layer that are vulnerable to this
> (although they've been vulnerable to it and missing a lock since last
> century with no known ill effects).

That observation cuts both ways; I'm willing to leave it vulnerable with
'no known ill effects' on the Alpha.
 

Re: bit fields && data tearing

[H. Peter Anvin]

On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
> 
> I think the whole "removing Alpha EV5" support is basically bonkers. Just
> use set_bit in the tty layer. Alpha will continue to work as well as it
> always has done and you won't design out support for any future processor
> that turns out not to do byte aligned stores.
> 

I think it's pretty safe to say such a processor is unlikely to ever be
created, for the same reason there weren't any 48-bit computers when
32-bit computers ran out of steam: it caused more problems than it
solved, and Alpha pretty much proved that.  The engineering advantages
would have to be so overwhelmingly in favor for someone to want to walk
down that road again.

	-hpa

Re: bit fields && data tearing

[Rob Landley]

On Wed, Sep 10, 2014 at 3:18 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
>>
>> I think the whole "removing Alpha EV5" support is basically bonkers. Just
>> use set_bit in the tty layer. Alpha will continue to work as well as it
>> always has done and you won't design out support for any future processor
>> that turns out not to do byte aligned stores.
>>
>
> I think it's pretty safe to say such a processor is unlikely to ever be
> created, for the same reason there weren't any 48-bit computers when
> 32-bit computers ran out of steam: it caused more problems than it
> solved, and Alpha pretty much proved that.  The engineering advantages
> would have to be so overwhelmingly in favor for someone to want to walk
> down that road again.
>
>         -hpa

I note for the record I'm trying to get basic Alpha support working in
http://landley.net/aboriginal/about.html now that qemu at least offers
a qemu-system-alpha, and if I do get it working I may take a stab at
adding alpha support to musl-libc.

It's not just that I want to get cross platform testing of package
builds working on a convenient/reproducible/portable way on as many
different targets as I can. My project is designed the way it is
because I think losing the ability to reproduce things from first
principles (and thus understand why it was done that way in the first
place) is a _bad_idea_. And an increasingly real-world problem, see
http://wrttn.in/04af1a for example. (And the way NASA lost the plans
for the Saturn V rocket... In fact scientists' general disinclination
to reproduce old experimental results to see if they were actually
true or not comes up on a regular basis, most recent I saw was
http://www.theglobeandmail.com/life/health-and-fitness/health/the-curious-case-of-the-cyclists-unshaved-legs/article20370814/
)

Of course Peter has consistently dismissed my concerns as "academic":

http://lkml.iu.edu/hypermail/linux/kernel/0802.1/4400.html

Personally, I hope the projects I work on _do_ outlive me, an try to
make it easy for newbies to recapitulate phylogeny. That's why I
thought requiring perl dependencies to build was a bad idea, and why I
thought removing 386 support entirely (instead of restricting it to
UP) was a bad idea. The idea that Linux no longer needs to build on
the original machine Linus designed it for, and now it no longer needs
to work on the machine the "arch" directory was created for (and the
first 64 bit machine)... These positions would appear to have a single
consistent proponent, with whom I disagree.

Oh well, just wanted to get that out there,

Rob

Re: bit fields && data tearing

[One Thousand Gnomes]

> > Is *that* what we are talking about?  I was added to this conversation
> > in the middle where it had already generalized, so I had no idea.
> 
> No, this is just what brought this craziness to my attention.

None of it is craziness. It's the real world leaking into the crazy
delusional world of sequential programming. Machines are going to get
more not less parallel.

> For example, byte- and short-sized circular buffers could not possibly
> be safe either, when the head nears the tail.
> 
> Who has audited global storage and ensured that _every_ byte-sized write
> doesn't happen to be adjacent to some other storage that may not happen
> to be protected by the same (or any) lock?

Thats a meaningless question. Have you audited it all for correctness of
any other form. Have you mathematically verified the functionality as a
set of formal proofs ? If you can't prove its formally mathematically
functionally correct why are you worried about this ?

Alpha works, maybe it has a near theoretical race on that point. It's not
any worse than it was 15 years ago and nobody has really hit a problem
with it. So from that you can usefully infer that those buffer cases are
not proving a real problem.

The tty locks together on the other hand are asking to hit it, and the
problem you were trying to fix were the ones that need set_bit() to make
the guarantees.

Alan

Re: bit fields && data tearing

[Paul E. McKenney]

On Thu, Sep 11, 2014 at 11:04:11AM +0100, One Thousand Gnomes wrote:
> > > Is *that* what we are talking about?  I was added to this conversation
> > > in the middle where it had already generalized, so I had no idea.
> > 
> > No, this is just what brought this craziness to my attention.
> 
> None of it is craziness. It's the real world leaking into the crazy
> delusional world of sequential programming. Machines are going to get
> more not less parallel.

Amen to that!!!

> > For example, byte- and short-sized circular buffers could not possibly
> > be safe either, when the head nears the tail.
> > 
> > Who has audited global storage and ensured that _every_ byte-sized write
> > doesn't happen to be adjacent to some other storage that may not happen
> > to be protected by the same (or any) lock?
> 
> Thats a meaningless question. Have you audited it all for correctness of
> any other form. Have you mathematically verified the functionality as a
> set of formal proofs ? If you can't prove its formally mathematically
> functionally correct why are you worried about this ?
> 
> Alpha works, maybe it has a near theoretical race on that point. It's not
> any worse than it was 15 years ago and nobody has really hit a problem
> with it. So from that you can usefully infer that those buffer cases are
> not proving a real problem.

Fair enough, I guess.

But Alpha's limitations were given as a reason to restrict
smp_store_release() and smp_load_acquire() from providing one-byte and
two-byte variants.  Of course, I am OK "probabilistically supporting"
pre-EV56 Alpha CPUs, but only if they don't get in the way of us doing
smp_store_release() and smp_load_acquire() on chars and shorts.  So if
pre-EV56 support has to go in order to allow smp_store_release() and
smp_load_acquire() on small data types, then pre-EV56 support simply
has to go.

Alternatively, one way to support this old hardware on a more
deterministic basis is to make the compiler use ll/sc sequences to do
byte and short accesses.  That would be fine as well.

						Thanx, Paul

> The tty locks together on the other hand are asking to hit it, and the
> problem you were trying to fix were the ones that need set_bit() to make
> the guarantees.
> 
> Alan
> 

Re: bit fields && data tearing

[Peter Hurley]

On 09/11/2014 06:04 AM, One Thousand Gnomes wrote:
>>> Is *that* what we are talking about?  I was added to this conversation
>>> in the middle where it had already generalized, so I had no idea.
>>
>> No, this is just what brought this craziness to my attention.
> 
> None of it is craziness. It's the real world leaking into the crazy
> delusional world of sequential programming. Machines are going to get
> more not less parallel.
> 
>> For example, byte- and short-sized circular buffers could not possibly
>> be safe either, when the head nears the tail.
>>
>> Who has audited global storage and ensured that _every_ byte-sized write
>> doesn't happen to be adjacent to some other storage that may not happen
>> to be protected by the same (or any) lock?
> 
> Thats a meaningless question. Have you audited it all for correctness of
> any other form. Have you mathematically verified the functionality as a
> set of formal proofs ? If you can't prove its formally mathematically
> functionally correct why are you worried about this ?
> 
> Alpha works, maybe it has a near theoretical race on that point. It's not
> any worse than it was 15 years ago and nobody has really hit a problem
> with it. So from that you can usefully infer that those buffer cases are
> not proving a real problem.
>
> The tty locks together on the other hand are asking to hit it, and the
> problem you were trying to fix were the ones that need set_bit() to make
> the guarantees.

So a problem that no one has ever complained about on _any_ arch is suddenly
a problem on a subset of Alpha cpus, but a problem I know exists on Alpha
isn't important because no one's filed a bug about it?

The only Alpha person in this discussion has come out clearly in favor
of dropping EV4/5 support.

The fact is that the kernel itself is much more parallel than it was
15 years ago, and that trend is going to continue. Paired with the fact
that the Alpha is the least-parallel-friendly arch, makes improving
parallelism and correctness even harder within kernel subsystems; harder
than it has to be and harder than it should be.

Linus has repeatedly stated that non-arch code should be as
arch-independent as possible, so I believe that working around problems
created by a cpu from 1995 _which no other arch exhibits_ is ludicrous.
Especially in generic kernel code.

That said, if the Alpha community wants to keep _actively_ supporting
the Alpha arch, fine. They could be working toward solutions for
making Alpha workarounds in generic kernel code unnecessary. If that means
compiler changes, ok. If that means arch-independent macros, well, they
can float that idea.

Or if they're comfortable with the status quo, also fine. By that, I mean
the Alpha arch gets no workarounds in generic kernel code, and if something
goes a little sideways only on Alpha, that's to be expected.

As Paul pointed out, a good first step would be for the Alpha community
to contribute byte and short versions of smp_load_acquire() and
smp_store_release() so that the rest of the kernel community can make
forward progress on more parallelism without Alpha-only limitations.

Regards,
Peter Hurley

Re: bit fields && data tearing

[One Thousand Gnomes]

> So a problem that no one has ever complained about on _any_ arch is suddenly
> a problem on a subset of Alpha cpus, but a problem I know exists on Alpha
> isn't important because no one's filed a bug about it?

Yes - because if you think about it that tells you that nobody is hitting
it with the old code and it probably doesn't matter.
 
> The only Alpha person in this discussion has come out clearly in favor
> of dropping EV4/5 support.

That's not a statistically valid sample size btw

Plus as I pointed out (and you ignored) you are shutting out any future
processors with this kind of oddity, and you have not audited all the
embedded devices we support or may support in future.
 
> The fact is that the kernel itself is much more parallel than it was
> 15 years ago, and that trend is going to continue. Paired with the fact
> that the Alpha is the least-parallel-friendly arch, makes improving
> parallelism and correctness even harder within kernel subsystems; harder
> than it has to be and harder than it should be.
> 
> Linus has repeatedly stated that non-arch code should be as
> arch-independent as possible

That's why many many years ago we added set_bit() and the other bit
functions. On sane processors they are very fast. On insane ones they
work. They understand byte tearing, they understand store ordering (which
a simple variable does not so you've got to audit all your memory
barriers too). In many cases they are faster than using memory barriers
to guide the compiler because they invalidate less and allow the compiler
more freedom.

All this started because I suggested you use set_bit and friends and for
some reason you've decided to try and find another way to do it. We have
the bit operations for a reason. On x86 they are very very fast, on
uniprocessor anything they are very fast, on multiprocessor in general
they are very fast, or you are dealing with boxes that have sanity
problems of other kinds.

Alan

Re: bit fields && data tearing

[Paul E. McKenney]

On Mon, Sep 15, 2014 at 12:24:27AM +0100, One Thousand Gnomes wrote:
> > So a problem that no one has ever complained about on _any_ arch is suddenly
> > a problem on a subset of Alpha cpus, but a problem I know exists on Alpha
> > isn't important because no one's filed a bug about it?
> 
> Yes - because if you think about it that tells you that nobody is hitting
> it with the old code and it probably doesn't matter.
> 
> > The only Alpha person in this discussion has come out clearly in favor
> > of dropping EV4/5 support.
> 
> That's not a statistically valid sample size btw

OK, adding the other two Alpha Port maintainers on CC.

Attempted summary for their benefit:

o	There was a bug involving older Alpha CPUs using 32-bit
	memory-reference operations to do smaller memory accesses.
	The suggested resolution was to use set_bit().

o	Peter Hurley called out a number of theoretical issues with
	CPUs lacking 8-bit and 16-bit memory-reference instructions,
	for example, adjacent 8-bit variables protected by different
	locks not being safe on such CPUs.

o	Michael Cree pointed out that some of these issues actually
	happen in the X server ever since the libpciaccess change.
	Michael would like to compile for Alpha with BWX (thus allowing
	8-bit and 16-bit memory references, but disallowing pre-EV56
	CPUs) in order make the X server (and thus Debian) work
	better on newer Alpha CPUs.

	Given that Michael Cree maintains the list of Alpha systems
	running Linux, I took this as my cue to provide a couple of
	patches to that effect.

o	Michael Cree also noted that pre-EV56 Alpha CPUs really can
	do 8-bit and 16-bit accesses in an SMP-safe manner via LL/SC,
	but that this requires some hacking on the compilers.

o	Alan Cox argued that we should support pre-EV56 Alpha CPUs
	without any special defense against issues that might arise
	from their lack of 8-bit and 16-bit memory-reference
	instructions, as you can see above.

Richard, Ivan, Matt, thoughts from your perspectives as Alpha Port
maintainers?

> Plus as I pointed out (and you ignored) you are shutting out any future
> processors with this kind of oddity, and you have not audited all the
> embedded devices we support or may support in future.

True enough, but then again, the Alpha architects did feel the need to
add 8-bit and 16-bit memory reference instructions in EV56.  In addition,
if there are future processors that don't provide 8-bit and 16-bit memory
reference instructions, atomic instructions can be used as a fallback.
This fallback is in fact similar to the set_bit approach.

> > The fact is that the kernel itself is much more parallel than it was
> > 15 years ago, and that trend is going to continue. Paired with the fact
> > that the Alpha is the least-parallel-friendly arch, makes improving
> > parallelism and correctness even harder within kernel subsystems; harder
> > than it has to be and harder than it should be.
> > 
> > Linus has repeatedly stated that non-arch code should be as
> > arch-independent as possible
> 
> That's why many many years ago we added set_bit() and the other bit
> functions. On sane processors they are very fast. On insane ones they
> work. They understand byte tearing, they understand store ordering (which
> a simple variable does not so you've got to audit all your memory
> barriers too). In many cases they are faster than using memory barriers
> to guide the compiler because they invalidate less and allow the compiler
> more freedom.
> 
> All this started because I suggested you use set_bit and friends and for
> some reason you've decided to try and find another way to do it. We have
> the bit operations for a reason. On x86 they are very very fast, on
> uniprocessor anything they are very fast, on multiprocessor in general
> they are very fast, or you are dealing with boxes that have sanity
> problems of other kinds.

Indeed, these email threads do tend to examine alternatives from time
to time.  ;-)

							Thanx, Paul

Re: bit fields && data tearing

[Peter Hurley]

On 09/14/2014 07:24 PM, One Thousand Gnomes wrote:
>> So a problem that no one has ever complained about on _any_ arch is suddenly
>> a problem on a subset of Alpha cpus, but a problem I know exists on Alpha
>> isn't important because no one's filed a bug about it?
> 
> Yes - because if you think about it that tells you that nobody is hitting
> it with the old code and it probably doesn't matter.

I don't understand this reply.

No one ever reported that the tty bitfield was being corrupted on any arch,
even though the serialization was broken because the bitfield was being
accessed with different locks. This was likely never discovered because
the corrupted tty state was unlikely to be reproduced easily.

Nevertheless, it needs fixing because it's wrong; so I did.

You pointed out my original fix was incorrect because Alpha CPUs could
still overwrite adjacent state if only bytes were used as separate memory
locations for each state. Ok.

Likewise, I'm pointing that byte-sized circular buffers will also be 
corrupted under certain circumstances (when the head comes near the tail).

Your claim that no one has complained about it (other than me) is no
different than if I had dismissed your objection to my original fix by
saying no one has complained about it.

There could be many motives for why someone with a 20-year old processor
that sees data corruption occasionally has not filed a bug about it, even
if they did bother to track down the original cause (which is pretty unlikely).

>> The only Alpha person in this discussion has come out clearly in favor
>> of dropping EV4/5 support.
> 
> That's not a statistically valid sample size btw
> 
> Plus as I pointed out (and you ignored) you are shutting out any future
> processors with this kind of oddity, and you have not audited all the
> embedded devices we support or may support in future.

I did not ignore this point.

Firstly, I thought Peter's reply was on-point:

On 09/10/2014 04:18 PM, H. Peter Anvin wrote:
> On 09/08/2014 10:52 AM, One Thousand Gnomes wrote:
>>
>> I think the whole "removing Alpha EV5" support is basically bonkers. Just
>> use set_bit in the tty layer. Alpha will continue to work as well as it
>> always has done and you won't design out support for any future processor
>> that turns out not to do byte aligned stores.
>>
> 
> I think it's pretty safe to say such a processor is unlikely to ever be
> created, for the same reason there weren't any 48-bit computers when
> 32-bit computers ran out of steam: it caused more problems than it
> solved, and Alpha pretty much proved that.  The engineering advantages
> would have to be so overwhelmingly in favor for someone to want to walk
> down that road again.

Secondly, I replied:

On 09/09/2014 07:14 AM, Peter Hurley wrote:
> I thought the overriding design principle of this kernel was to support
> what exists now, not design-in support for the future which may have
> different requirements than expected anyway.

>> The fact is that the kernel itself is much more parallel than it was
>> 15 years ago, and that trend is going to continue. Paired with the fact
>> that the Alpha is the least-parallel-friendly arch, makes improving
>> parallelism and correctness even harder within kernel subsystems; harder
>> than it has to be and harder than it should be.
>>
>> Linus has repeatedly stated that non-arch code should be as
>> arch-independent as possible
> 
> That's why many many years ago we added set_bit() and the other bit
> functions. On sane processors they are very fast. On insane ones they
> work. They understand byte tearing, they understand store ordering (which
> a simple variable does not so you've got to audit all your memory
> barriers too). In many cases they are faster than using memory barriers
> to guide the compiler because they invalidate less and allow the compiler
> more freedom.
> 
> All this started because I suggested you use set_bit and friends and for
> some reason you've decided to try and find another way to do it. We have
> the bit operations for a reason. On x86 they are very very fast, on
> uniprocessor anything they are very fast, on multiprocessor in general
> they are very fast, or you are dealing with boxes that have sanity
> problems of other kinds.

1. The question of why I chose to solve this problem without
set_bit(), et.al. I already answered:

On 09/09/2014 07:14 AM, Peter Hurley wrote:
> And much simpler how?
> 
> By turning a 4- line patch into a 400- line patch?
> 
> And what about multi-value assignments for which set_bit() doesn't work, like
> the byte-sized ->ctrl_status field? Is the expectation to submit a patch
> which fixes that for a system from 1995, but already works for everything else?
> 
> The extra complexity comes with real cost; reduced reliability for every other
> arch .

2. I'm not sure where you arrived at the conclusion that set_bit() et.al. is
fast on x86. Besides the heavy-duty instructions (lgdt, mov cr0, etc), the
bus-locked bit instructions are among the most expensive instructions in the
kernel.

I've attached a smoke test I use for lightweight validation of pty slave reads.
If you run this smoke test under perf, almost every high-value hit is a
bus-locked bit instruction. Check out canon_copy_from_read_buf() which performs
the actual copy of data from the line discipline input buffer to the __user
buffer; the clear_bit() is the performance hit. Check out cpu_idle_loop()...

Regards,
Peter Hurley

How I run perf:
$ echo 0 | sudo tee /proc/sys/kernel/kptr_restrict
$ echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid
$ perf record -a -g ./tty_test1
$ perf report [-k whereever your vmlinux is ]

--- >% ---
/*
 * tty_test1.cpp
 *
 * Description: Validate error-free tty read and write
 *
 * This test repeatedly writes a test pattern from master
 * to slave and verifies the result.
 *
 * Q: Does the slave receive all the data error-free?
 *
 * Expected: PASS
 * Validate: build w/ -DVALIDATE to fail the test
 * Verify: build w/ -DVERIFY to crc-compare the received data
 *         (requires boost)
 *
 * Build: g++ -Wall -o tty_test1 tty_test1.cpp
 *
 */

#include <stdio.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/wait.h>
#include <termios.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <stdarg.h>
#include <signal.h>
#include <limits.h>
#include <unistd.h>

#ifdef VERIFY
#include <boost/crc.hpp>

static uint32_t reference_crc32;
#endif

const unsigned loops_per_crc = 839;  /* prime */
static struct termios termios;


#define XFER_LEN 173	/* prime smaller than PATTERN_SIZE */
static char pattern[] = \
	/*          1         2         3         4         5
	 * 12345678901234567890123456789012345678901234567890 */
	  "+_)(*&^%$#@!~=-0987654321`|}{POIUYTREWQ][poiuytrew"	       /*  50 */
	  "q:LKJHGFDSA;lkjhgfdsa?><MNBVCXZ/.,mnbvcxz"		       /* +41 */
	  "\"\'\\"						       /* + 3 */
	  "+_)(*&^%$#@!~=-0987654321`|}{POIUYTREWQ][poiuytrew"	       /*  50 */
	  "q:LKJHGFDSA;lkjhgfdsa?><MNBV\n";			       /* +29 */
								       /* 173 */


#define error_exit(f, args...)				       		       \
	printf_exit("%s: " f ": %s (code: %d)\n", __func__, ##args,	       \
						  strerror(errno), errno)

#define msg_exit(f, args...) \
	printf_exit("%s: " f "\n", __func__, ##args)


static void printf_exit(const char *f, ...) {
	va_list va;

	va_start(va, f);
	vfprintf(stderr, f, va);
	va_end(va);

	exit(EXIT_FAILURE);
}

static void child(int fd) {
	unsigned char buffer[MAX_INPUT];
#ifdef VERIFY
	boost::crc_32_type crc32;
#endif
	unsigned n = 0;
	unsigned loops = 0;

	printf("Starting slave read loop...\n");

	while (1) {
		int c = read(fd, buffer, sizeof(buffer));
		if (!c)
			break;
		if (c != XFER_LEN) {
			if (c > 0)
				printf("%.*s", (int)c, buffer);
			error_exit("read slave: %zd", c);
		}
#ifdef VERIFY
		crc32.process_bytes(buffer, c);
#endif
		if (++n >= loops_per_crc) {
#ifdef VERIFY
			if (crc32() != reference_crc32) {
				errno = EIO;
				error_exit("failed crc: reference: %x != %x",
					   reference_crc32, crc32());
			}
			crc32.reset();
#endif
#ifdef PROGRESS
			printf(".");
#endif
			n = 0;
		}
		loops++;
	}

	printf("Success: %u loops x %d-byte pattern\n", loops, XFER_LEN);
}

static void master(int fd) {
	int n;
	int c = strlen(pattern);
	unsigned loops = 1000000U;

	printf("Starting master write loop...\n");

	while (loops--) {
		n = write(fd, pattern, c);
		if (n < 0)
			error_exit("master write");
		if (n != c)
			msg_exit("short write of pattern");
	}

	n = write(fd, &termios.c_cc[VEOF], 1);
	if (n < 0)
		error_exit("writing EOF");
	if (n != 1)
		msg_exit("short write of EOF");

}

int main() {
	int fd;
	char pts_name[24];
	int ptn, unlock = 0;
	pid_t child_id, id;
	int status;

	setbuf(stdout, NULL);

#ifdef VERIFY
	boost::crc_32_type reference;

	for (unsigned i = 0; i < loops_per_crc; i++)
		reference.process_bytes( pattern, XFER_LEN);
	reference_crc32 = reference();
#endif

#ifdef VALIDATE
	pattern[50] |= 0x80;
#endif

	fd = open("/dev/ptmx", O_RDWR);
	if (fd < 0)
		error_exit("opening pty master");
	if (ioctl(fd, TIOCSPTLCK, &unlock))
		error_exit("unlocking pty pair");
	if (ioctl(fd, TIOCGPTN, &ptn))
		error_exit("getting pty #");
	snprintf(pts_name, sizeof(pts_name), "/dev/pts/%d", ptn);

	if (tcgetattr(fd, &termios))
		error_exit("getting termios");
	termios.c_lflag &= ~ECHO;
	if (tcsetattr(fd, TCSANOW, &termios))
		error_exit("setting termios");

	switch (child_id = fork()) {
	case -1:
		error_exit("forking child");

	case 0: /* child */
		close(fd);
		fd = open(pts_name, O_RDWR);
		if (fd < 0)
			error_exit("opening pty slave");
		child(fd);
		break;

	default: /* parent */
		master(fd);

		id = waitpid(child_id, &status, 0);
		if (id < 0 || id != child_id)
			error_exit("waiting for child");
		if (id != child_id)
			msg_exit("waitpid returned %d, expected %d", id, child_id);
		break;
	}

	/* child and parent exit here */
	return 0;
}

Re: bit fields && data tearing

[One Thousand Gnomes]

> > Yes - because if you think about it that tells you that nobody is hitting
> > it with the old code and it probably doesn't matter.
> 
> I don't understand this reply.

It's a matter of priorities. There are hundreds of potential security
holes turned up by scanners, 2,500+ filed bugs in kernel bugzilla alone.

Which matters more - fixing the bugs people hit or the ones that they
don't and which have a very high cost impact on other users ?

> Likewise, I'm pointing that byte-sized circular buffers will also be 
> corrupted under certain circumstances (when the head comes near the tail).

Yes. I believe the classic wording is "this problem has not been observed
in the field"
 
> 2. I'm not sure where you arrived at the conclusion that set_bit() et.al. is
> fast on x86. Besides the heavy-duty instructions (lgdt, mov cr0, etc), the
> bus-locked bit instructions are among the most expensive instructions in the
> kernel.

> I've attached a smoke test I use for lightweight validation of pty slave reads.
> If you run this smoke test under perf, almost every high-value hit is a
> bus-locked bit instruction. Check out canon_copy_from_read_buf() which performs
> the actual copy of data from the line discipline input buffer to the __user
> buffer; the clear_bit() is the performance hit. Check out cpu_idle_loop()...

And then go and instrument whether its the bit instructions or the cache
misses ?


If there is a significant performance improvement by spacing the fields
carefully, and you don't have other ordering problems as a result
(remembering that the compiler has a lot of re-ordering options provided
the re-ordering cannot be observed)

If that's the case then fine - submit a patch with numbers and the fields
spaced and quote the performance data.

Alan
_______________________________________________
Linuxppc-dev mailing list
Linuxppc-dev@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/linuxppc-dev