Is gcc thread-unsafe?

Is gcc thread-unsafe?

[Nick Piggin]

Hi,

Andi spotted this exchange on the gcc list. I don't think he's
brought it up here yet, but it worries me enough that I'd like
to discuss it.

Starts here
http://gcc.gnu.org/ml/gcc/2007-10/msg00266.html

Concrete example here
http://gcc.gnu.org/ml/gcc/2007-10/msg00275.html

Basically, what the gcc developers are saying is that gcc is
free to load and store to any memory location, so long as it
behaves as if the instructions were executed in sequence.

I guess that dynamically allocated memory and computed pointers
are more difficult for gcc to do anything unsafe with, because
it is harder to tell if a given function has deallocated the
memory. However even that could theoretically happen in future
if the compiler can work out the address comes from a global
variable or is not changed intermediately.

Linux makes extensive use of both trylocks and interruptible
locks (ie. which automatically result in divergant code paths,
one of which holds the lock, the other doesn't). However there
are also other code paths which will either hold a particular
lock or will not hold it, depending on context or some flags
etc. barrier() doesn't help.

For x86, obviously the example above shows it can be miscompiled,
but it is probably relatively hard to make it happen for a non
trivial sequence. For an ISA with lots of predicated instructions
like ia64, it would seem to be much more likely. But of course
we don't want even the possibility of failures.

The gcc guys seem to be saying to mark everything volatile that
could be touched in a critical section. This is insane for Linux.

Any thoughts?

Re: Is gcc thread-unsafe?

[Arjan van de Ven]

On Thu, 25 Oct 2007 13:24:49 +1000
Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> Hi,
> 
> Andi spotted this exchange on the gcc list. I don't think he's
> brought it up here yet, but it worries me enough that I'd like
> to discuss it.
> 
> Starts here
> http://gcc.gnu.org/ml/gcc/2007-10/msg00266.html
> 
> Concrete example here
> http://gcc.gnu.org/ml/gcc/2007-10/msg00275.html
> 
> Basically, what the gcc developers are saying is that gcc is
> free to load and store to any memory location, so long as it
> behaves as if the instructions were executed in sequence.
> 


this optimization btw is a serious mis-optimization, it makes memory
more dirty and causes cachelines to become unshared.... I'm sure it
works great on microbenchmarks but it sucks bigtime for anything real

Re: Is gcc thread-unsafe?

[Nick Piggin]

On Thursday 25 October 2007 13:46, Arjan van de Ven wrote:
> On Thu, 25 Oct 2007 13:24:49 +1000
>
> Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> > Hi,
> >
> > Andi spotted this exchange on the gcc list. I don't think he's
> > brought it up here yet, but it worries me enough that I'd like
> > to discuss it.
> >
> > Starts here
> > http://gcc.gnu.org/ml/gcc/2007-10/msg00266.html
> >
> > Concrete example here
> > http://gcc.gnu.org/ml/gcc/2007-10/msg00275.html
> >
> > Basically, what the gcc developers are saying is that gcc is
> > free to load and store to any memory location, so long as it
> > behaves as if the instructions were executed in sequence.
>
> this optimization btw is a serious mis-optimization, it makes memory
> more dirty and causes cachelines to become unshared.... I'm sure it
> works great on microbenchmarks but it sucks bigtime for anything real

Well that's exactly right. For threaded programs (and maybe even
real-world non-threaded ones in general), you don't want to be
even _reading_ global variables if you don't need to. Cache misses
and cacheline bouncing could easily cause performance to completely
tank in some cases while only gaining a cycle or two in
microbenchmarks for doing these funny x86 predication things.

I'm not sure about ia64 -- I _hope_ that for most of their
predication stuff, they also predicate the stores, rather than
just store unconditionally and rely on the source operand not
changing in the case they didn't intend the memory to change.

RE: Is gcc thread-unsafe?

[David Schwartz]

> Well that's exactly right. For threaded programs (and maybe even
> real-world non-threaded ones in general), you don't want to be
> even _reading_ global variables if you don't need to. Cache misses
> and cacheline bouncing could easily cause performance to completely
> tank in some cases while only gaining a cycle or two in
> microbenchmarks for doing these funny x86 predication things.

For some CPUs, replacing an conditional branch with a conditional move is a
*huge* win because it cannot be mispredicted. In general, compilers should
optimize for unshared data since that's much more common in typical code.
Even for shared data, the usual case is that you are going to access the
data few times, so pulling the cache line to the CPU is essentially free
since it will happen eventually.

Heuristics may show that the vast majority of such constructs write anyway.
So the optimization may also be valid based on such heuristics.

A better question is whether it's legal for a compiler that claims to
support POSIX threads. I'm going to post on comp.programming.threads, where
the threading experts hang out.

A very interesting case to be sure.

DS

Re: Is gcc thread-unsafe?

[Arjan van de Ven]

On Wed, 24 Oct 2007 21:29:56 -0700
"David Schwartz" <davids@webmaster.com> wrote:

> 
> > Well that's exactly right. For threaded programs (and maybe even
> > real-world non-threaded ones in general), you don't want to be
> > even _reading_ global variables if you don't need to. Cache misses
> > and cacheline bouncing could easily cause performance to completely
> > tank in some cases while only gaining a cycle or two in
> > microbenchmarks for doing these funny x86 predication things.
> 
> For some CPUs, replacing an conditional branch with a conditional
> move is a *huge* win because it cannot be mispredicted.

please name one...
Hint: It's not one made by either Intel or AMD in the last 4 years...


> In general,
> compilers should optimize for unshared data since that's much more
> common in typical code. Even for shared data, the usual case is that
> you are going to access the data few times, so pulling the cache line
> to the CPU is essentially free since it will happen eventually.

it's not about pulling it to the CPU, it's pulling it *out* of all the
other cpus AS WELL. (and writing it back to memory, taking away memory
bandwidth)


--
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Is gcc thread-unsafe?

[Måns Rullgård]

Arjan van de Ven <arjan@infradead.org> writes:

> On Wed, 24 Oct 2007 21:29:56 -0700
> "David Schwartz" <davids@webmaster.com> wrote:
>
>> 
>> > Well that's exactly right. For threaded programs (and maybe even
>> > real-world non-threaded ones in general), you don't want to be
>> > even _reading_ global variables if you don't need to. Cache misses
>> > and cacheline bouncing could easily cause performance to completely
>> > tank in some cases while only gaining a cycle or two in
>> > microbenchmarks for doing these funny x86 predication things.
>> 
>> For some CPUs, replacing an conditional branch with a conditional
>> move is a *huge* win because it cannot be mispredicted.
>
> please name one...
> Hint: It's not one made by either Intel or AMD in the last 4 years...

ARM.  On ARM1136 (used in the Nokia N800) a mispredicted branch takes
5-7 cycles (a correctly predicted branch takes 0-4 cycles), while a
conditional load, store or arithmetic instruction always takes one
cycle.

-- 
Måns Rullgård
mans@mansr.com

Re: Is gcc thread-unsafe?

[Nick Piggin]

Hi David,

[BTW. can you retain cc lists, please?]

On Thursday 25 October 2007 14:29, David Schwartz wrote:
> > Well that's exactly right. For threaded programs (and maybe even
> > real-world non-threaded ones in general), you don't want to be
> > even _reading_ global variables if you don't need to. Cache misses
> > and cacheline bouncing could easily cause performance to completely
> > tank in some cases while only gaining a cycle or two in
> > microbenchmarks for doing these funny x86 predication things.
>
> For some CPUs, replacing an conditional branch with a conditional move is a
> *huge* win because it cannot be mispredicted.

A *conditional* store should no be a problem.

However the funny trick of doing this conditional add (implemented with
unconditional store), is what is going to cause breakage.

On the CPUs where predicated instructions are a big win, I'd expect
they should also implement a conditional store for use here. However
they might be slower than an unconditional store (eg. x86's cmov),
and in those cases, gcc might just do the non-conditional store.


> In general, compilers should 
> optimize for unshared data since that's much more common in typical code.
> Even for shared data, the usual case is that you are going to access the
> data few times, so pulling the cache line to the CPU is essentially free
> since it will happen eventually.

This is not just a question of data that you were going to use anyway.
gcc generates memory accesses to locations that would never be accessed
Even stores. It is basically impossible to say that this is a real
performance win. Even on single threaded code: consider that cache
misses take the vast majority of time in many loads, which gives a
little hint that maybe it's a bad idea to do this ;)


> Heuristics may show that the vast majority of such constructs write anyway.
> So the optimization may also be valid based on such heuristics.

I'd never say the optimisation would always be useless. But it's a nasty
thing to have on by default, and apparently even with no good way to
supress it even if we want to.


> A better question is whether it's legal for a compiler that claims to
> support POSIX threads. I'm going to post on comp.programming.threads, where
> the threading experts hang out.

Either way, I think we really need a way to turn it off for Linux.

Re: Is gcc thread-unsafe?

[Samuel Tardieu]

>>>>> "Nick" == Nick Piggin <nickpiggin@yahoo.com.au> writes:

Nick> Hi David, [BTW. can you retain cc lists, please?]

Nick> On Thursday 25 October 2007 14:29, David Schwartz wrote:
>> > Well that's exactly right. For threaded programs (and maybe even
>> > real-world non-threaded ones in general), you don't want to be >
>> even _reading_ global variables if you don't need to. Cache misses
>> > and cacheline bouncing could easily cause performance to
>> completely > tank in some cases while only gaining a cycle or two
>> in > microbenchmarks for doing these funny x86 predication things.
>> 
>> For some CPUs, replacing an conditional branch with a conditional
>> move is a *huge* win because it cannot be mispredicted.

Nick> A *conditional* store should no be a problem.

Nick> However the funny trick of doing this conditional add
Nick> (implemented with unconditional store), is what is going to
Nick> cause breakage.

Nick> On the CPUs where predicated instructions are a big win, I'd
Nick> expect they should also implement a conditional store for use
Nick> here. However they might be slower than an unconditional store
Nick> (eg. x86's cmov), and in those cases, gcc might just do the
Nick> non-conditional store.


>> In general, compilers should optimize for unshared data since
>> that's much more common in typical code.  Even for shared data, the
>> usual case is that you are going to access the data few times, so
>> pulling the cache line to the CPU is essentially free since it will
>> happen eventually.

Nick> This is not just a question of data that you were going to use
Nick> anyway.  gcc generates memory accesses to locations that would
Nick> never be accessed Even stores. It is basically impossible to say
Nick> that this is a real performance win. Even on single threaded
Nick> code: consider that cache misses take the vast majority of time
Nick> in many loads, which gives a little hint that maybe it's a bad
Nick> idea to do this ;)


>> Heuristics may show that the vast majority of such constructs write
>> anyway.  So the optimization may also be valid based on such
>> heuristics.

Nick> I'd never say the optimisation would always be useless. But it's
Nick> a nasty thing to have on by default, and apparently even with no
Nick> good way to supress it even if we want to.


>> A better question is whether it's legal for a compiler that claims
>> to support POSIX threads. I'm going to post on
>> comp.programming.threads, where the threading experts hang out.

Nick> Either way, I think we really need a way to turn it off for
Nick> Linux.

-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/

Re: Is gcc thread-unsafe?

[Samuel Tardieu]

>>>>> "Nick" == Nick Piggin <nickpiggin@yahoo.com.au> writes:

Nick> Either way, I think we really need a way to turn it off for
Nick> Linux.

Someone would need to add an option to disable the "cselim" pass in
GCC tree-ssa-phiopt.c as far as I can tell from reading GCC source.

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/

Re: Is gcc thread-unsafe?

[Samuel Tardieu]

>>>>> "Sam" == Samuel Tardieu <sam@rfc1149.net> writes:
>>>>> "Nick" == Nick Piggin <nickpiggin@yahoo.com.au> writes:

Nick> Either way, I think we really need a way to turn it off for
Nick> Linux.

Sam> Someone would need to add an option to disable the "cselim" pass
Sam> in GCC tree-ssa-phiopt.c as far as I can tell from reading GCC
Sam> source.

Mmm, it looks like there is an option already (-fno-tree-cselim), but
it looks like it has no visible effect in my version of GCC
(yesterday's SVN). I'll ask on the GCC mailing-list.

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/

Re: Is gcc thread-unsafe?

[Andi Kleen]

On Thursday 25 October 2007 11:44:28 Samuel Tardieu wrote:
> >>>>> "Nick" == Nick Piggin <nickpiggin@yahoo.com.au> writes:
> 
> Nick> Either way, I think we really need a way to turn it off for
> Nick> Linux.
> 
> Someone would need to add an option to disable the "cselim" pass in
> GCC tree-ssa-phiopt.c as far as I can tell from reading GCC source.

Note the test case was for 3.4.x which doesn't have tree-ssa at all.
It does if-conversion on the RTL level 

-Andi

Re: Is gcc thread-unsafe?

[Andi Kleen]

On Thursday 25 October 2007 05:24, Nick Piggin wrote:

> Basically, what the gcc developers are saying is that gcc is
> free to load and store to any memory location, so long as it
> behaves as if the instructions were executed in sequence.

This case is clearly a bug, a very likely code pessimization.
I guess it wasn't intentional, just an optimization that is useful
for local register values doing too much.

> I guess that dynamically allocated memory and computed pointers
> are more difficult for gcc to do anything unsafe with, because
> it is harder to tell if a given function has deallocated the
> memory. 

Often accesses happen without function calls inbetween.
Also I think newer gcc (not 3.x) can determine if a pointer
"escapes" or not so that might not protect against it.

> Any thoughts?

We don't have much choice: If such a case is found it has to be marked
volatile or that particular compiler version be unsupported.

It might be useful to come up with some kind of assembler pattern
matcher to check if any such code is generated for the kernel
and try it with different compiler versions.

-Andi

Re: Is gcc thread-unsafe?

[linux-os (Dick Johnson)]

On Thu, 25 Oct 2007, Andi Kleen wrote:

> On Thursday 25 October 2007 05:24, Nick Piggin wrote:
>
>> Basically, what the gcc developers are saying is that gcc is
>> free to load and store to any memory location, so long as it
>> behaves as if the instructions were executed in sequence.
>
> This case is clearly a bug, a very likely code pessimization.
> I guess it wasn't intentional, just an optimization that is useful
> for local register values doing too much.


I don't think it is a BUG, but one should certainly be able
to turn it off. Gcc is correct in that the 'C' language allows
a lot of implimentation details that are not covered by the
language. In other words, 'C' is not assembly-language.


>
>> I guess that dynamically allocated memory and computed pointers
>> are more difficult for gcc to do anything unsafe with, because
>> it is harder to tell if a given function has deallocated the
>> memory.
>
> Often accesses happen without function calls inbetween.
> Also I think newer gcc (not 3.x) can determine if a pointer
> "escapes" or not so that might not protect against it.
>
>> Any thoughts?
>
> We don't have much choice: If such a case is found it has to be marked
> volatile or that particular compiler version be unsupported.
>
> It might be useful to come up with some kind of assembler pattern
> matcher to check if any such code is generated for the kernel
> and try it with different compiler versions.
>
> -Andi

Cheers,
Dick Johnson
Penguin : Linux version 2.6.16.24 on an i686 machine (5592.59 BogoMips).
My book : http://www.AbominableFirebug.com/
_


****************************************************************
The information transmitted in this message is confidential and may be privileged.  Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited.  If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to DeliveryErrors@analogic.com - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

Re: Is gcc thread-unsafe?

[Andi Kleen]

On Thursday 25 October 2007 13:58:56 linux-os (Dick Johnson) wrote:
> 
> On Thu, 25 Oct 2007, Andi Kleen wrote:
> 
> > On Thursday 25 October 2007 05:24, Nick Piggin wrote:
> >
> >> Basically, what the gcc developers are saying is that gcc is
> >> free to load and store to any memory location, so long as it
> >> behaves as if the instructions were executed in sequence.
> >
> > This case is clearly a bug, a very likely code pessimization.
> > I guess it wasn't intentional, just an optimization that is useful
> > for local register values doing too much.
> 
> 
> I don't think it is a BUG,

Bug as in an optimization that makes the code slower than it was
before. That is clearly a bug in a compiler.

-Andi

Re: Is gcc thread-unsafe?

[Nick Piggin]

On Thursday 25 October 2007 17:15, Andi Kleen wrote:
> On Thursday 25 October 2007 05:24, Nick Piggin wrote:
> > Basically, what the gcc developers are saying is that gcc is
> > free to load and store to any memory location, so long as it
> > behaves as if the instructions were executed in sequence.
>
> This case is clearly a bug, a very likely code pessimization.
> I guess it wasn't intentional, just an optimization that is useful
> for local register values doing too much.

Although there can be cases where it looks much more like an
optimisation (eg. where the branch and increment occurs much
more often), but it would still be a bug. Granted they are
rather constructed cases, but I don't think you want to rely on
the fact that most of the time it's OK.


> > I guess that dynamically allocated memory and computed pointers
> > are more difficult for gcc to do anything unsafe with, because
> > it is harder to tell if a given function has deallocated the
> > memory.
>
> Often accesses happen without function calls inbetween.
> Also I think newer gcc (not 3.x) can determine if a pointer
> "escapes" or not so that might not protect against it.
>
> > Any thoughts?
>
> We don't have much choice: If such a case is found it has to be marked
> volatile or that particular compiler version be unsupported.

Marking volatile I think is out of the question. To start with,
volatile creates really poor code (and most of the time we actually
do want the code in critical sections to be as tight as possible).
But also because I don't think these bugs are just going to be
found easily.


> It might be useful to come up with some kind of assembler pattern
> matcher to check if any such code is generated for the kernel
> and try it with different compiler versions.

Hard to know how to do it. If you can, then it would be interesting.

Re: Is gcc thread-unsafe?

[Andi Kleen]

On Friday 26 October 2007 00:49:42 Nick Piggin wrote:
> On Thursday 25 October 2007 17:15, Andi Kleen wrote:
> > On Thursday 25 October 2007 05:24, Nick Piggin wrote:
> > > Basically, what the gcc developers are saying is that gcc is
> > > free to load and store to any memory location, so long as it
> > > behaves as if the instructions were executed in sequence.
> >
> > This case is clearly a bug, a very likely code pessimization.
> > I guess it wasn't intentional, just an optimization that is useful
> > for local register values doing too much.
> 
> Although there can be cases where it looks much more like an
> optimisation (eg. where the branch and increment occurs much
> more often), but it would still be a bug. Granted they are
> rather constructed cases, but I don't think you want to rely on
> the fact that most of the time it's OK.
> 
> 
> > > I guess that dynamically allocated memory and computed pointers
> > > are more difficult for gcc to do anything unsafe with, because
> > > it is harder to tell if a given function has deallocated the
> > > memory.
> >
> > Often accesses happen without function calls inbetween.
> > Also I think newer gcc (not 3.x) can determine if a pointer
> > "escapes" or not so that might not protect against it.
> >
> > > Any thoughts?
> >
> > We don't have much choice: If such a case is found it has to be marked
> > volatile or that particular compiler version be unsupported.
> 
> Marking volatile I think is out of the question. To start with,
> volatile creates really poor code (and most of the time we actually
> do want the code in critical sections to be as tight as possible).

Poor code is better than broken code I would say. Besides
the cross CPU synchronization paths are likely dominated by 
cache misses anyways; it's unlikely they're actually limited
by the core CPU. So it'll probably not matter all that much
if the code is poor or not.

But it's all theoretical for now.

> But also because I don't think these bugs are just going to be
> found easily.
> 
> 
> > It might be useful to come up with some kind of assembler pattern
> > matcher to check if any such code is generated for the kernel
> > and try it with different compiler versions.
> 
> Hard to know how to do it. If you can, then it would be interesting.

I checked my kernel for "adc" at least (for the trylock/++ pattern) 
and couldn't find any (in fact all of them were in 
data the compiler thought to be code). That was not a allyesconfig build,
so i missed some code. 

For cmov it's at first harder because they're much more frequent
and cmov to memory is a multiple instruction pattern (the instruction
does only support memory source operands). Luckily gcc
doesn't know the if (x) mem = a; => ptr = cmov(x, &a, &dummy); *ptr = a; 
transformation trick so I don't think there are actually any conditional 
stores on current x86. 

It might be a problem on other architectures which support true
conditional stores though (like IA64 or ARM) 

Also I'm not sure if gcc doesn't know any other tricks like the
conditional add using carry, although I cannot think of any related
to stores from the top of my hat.

Anyways, if it's only conditional add if we ever catch such a case
it could be also handled with inline assembly similar to local_inc()

-Andi

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Andi Kleen wrote:
> > 
> > Marking volatile I think is out of the question. To start with,
> > volatile creates really poor code (and most of the time we actually
> > do want the code in critical sections to be as tight as possible).
> 
> Poor code is better than broken code I would say.

No. A *working*compiler* is better than broken code.

There's no way to use volatile for these things, since it can hit 
*anything*. When the compiler generates buggy code, it's buggy code. We 
can't add volatiles to every single data structure. We'd be better off 
having a million monkeys on crack try to hand-assemble the thing, than 
having a totally buggy compiler do it for us.

		Linus

Re: Is gcc thread-unsafe?

[Andi Kleen]

On Friday 26 October 2007 01:14:41 Linus Torvalds wrote:
> 
> On Fri, 26 Oct 2007, Andi Kleen wrote:
> > > 
> > > Marking volatile I think is out of the question. To start with,
> > > volatile creates really poor code (and most of the time we actually
> > > do want the code in critical sections to be as tight as possible).
> > 
> > Poor code is better than broken code I would say.
> 
> No. A *working*compiler* is better than broken code.
> 
> There's no way to use volatile for these things, since it can hit 
> *anything*.

No it can't (at least not on x86) as I have explained in the rest of the mail 
you conveniently snipped.

-Andi

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Andi Kleen wrote:
> 
> No it can't (at least not on x86) as I have explained in the rest of the mail 
> you conveniently snipped.

I "conveniently snipped it" because it was pointless.

"adc" or "cmov" has nothing what-so-ever to do with it. If some routine 
returns 0-vs-1 and gcc then turns "if (routine()) x++" into 
"x+=routine()", what does that have to do with adc or cmov?

The fact is, these kinds of optimizations are *bogus* and they are 
dangerous.

Now, it's equally true that we probably don't have those kinds of patterns 
in the kernel, and we'll probabaly not hit it, but wouldn't it be much 
better to make sure that compilers shouldn't do that?

			Linus

Re: Is gcc thread-unsafe?

[Andi Kleen]

On Friday 26 October 2007 01:32:53 Linus Torvalds wrote:
> 
> On Fri, 26 Oct 2007, Andi Kleen wrote:
> > 
> > No it can't (at least not on x86) as I have explained in the rest of the mail 
> > you conveniently snipped.
> 
> I "conveniently snipped it" because it was pointless.
> 
> "adc" or "cmov" has nothing what-so-ever to do with it. If some routine 
> returns 0-vs-1 and gcc then turns "if (routine()) x++" into 
> "x+=routine()", what does that have to do with adc or cmov?

That is not what gcc did in that case. I don't think it tracks sets of values
over function calls (or even inside functions) at all.

The generated code was

          cmpl    $1, %eax                ; test res
          movl    acquires_count, %edx    ; load
          adcl    $0, %edx                ; maybe add 1
          movl    %edx, acquires_count    ; store

So it just added the result of a comparison into a variable
by (ab)using carry for this.

In theory such things can be done with CMOV too by redirecting
a store into a dummy variable to cancel it, but gcc doesn't
do that on its own.

> The fact is, these kinds of optimizations are *bogus* and they are 
> dangerous.

The conditional add/sub using carry trick is not generally bogus. 
It's just bogus for memory addresses not pretty much guaranteed in L1
[aka small stack frame] because there the pipeline benefit is unlikely to 
offset the memory costs (and of course poor quality of implementation because of the 
missing thread safety). 

But for registers it's a fine optimization.

-Andi

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Andi Kleen wrote:
> 
> The conditional add/sub using carry trick is not generally bogus. 
> But for registers it's a fine optimization.

For registers it's fine. For memory, it's a disaster. It's more than just 
dirty cachelines and introducing race conditions, it's also about 
protection and dirty pages.

So even in user space, to even be correct in the first place, the compiler 
would need to make sure that the variable is writable at all (or you might 
take a SIGSEGV), but I guess that gcc just assumes it is, at least for 
globals (or gcc could depend on seeing *other* writes that are done 
unconditionally).

More likely, the compiler people don't even care, because "the C standard 
doesn't specify that behaviour" - ie things like write-protected memory or 
garbage collection based on dirty/accessed bits are outside the scope of 
what the language specifies. Much less things like pthreads or other 
synchronization primitives in threads.

			Linus

Re: Is gcc thread-unsafe?

[Zachary Amsden]

On Thu, 2007-10-25 at 16:57 -0700, Linus Torvalds wrote:
> 
> On Fri, 26 Oct 2007, Andi Kleen wrote:
> > 
> > The conditional add/sub using carry trick is not generally bogus. 
> > But for registers it's a fine optimization.
> 
> For registers it's fine. For memory, it's a disaster. It's more than just 
> dirty cachelines and introducing race conditions, it's also about 
> protection and dirty pages.
> 
> So even in user space, to even be correct in the first place, the compiler 

It's actually a fair bit worse for us.  We have paths where a false
optimization like this would hyperspace the machine.  In fact, this
frightens me so much I've just gone off to investigate whether gcc has
gone and done this to any of our code.

Clearly the right solution is to introduce threads and write protected
memory into gcc so that the developers are either motivated to ensure
they work or self-destruct.

Zach

Re: Is gcc thread-unsafe?

[Willy Tarreau]

On Fri, Oct 26, 2007 at 01:42:37AM +0200, Andi Kleen wrote:
> On Friday 26 October 2007 01:32:53 Linus Torvalds wrote:
> > 
> > On Fri, 26 Oct 2007, Andi Kleen wrote:
> > > 
> > > No it can't (at least not on x86) as I have explained in the rest of the mail 
> > > you conveniently snipped.
> > 
> > I "conveniently snipped it" because it was pointless.
> > 
> > "adc" or "cmov" has nothing what-so-ever to do with it. If some routine 
> > returns 0-vs-1 and gcc then turns "if (routine()) x++" into 
> > "x+=routine()", what does that have to do with adc or cmov?
> 
> That is not what gcc did in that case. I don't think it tracks sets of values
> over function calls (or even inside functions) at all.
> 
> The generated code was
> 
>           cmpl    $1, %eax                ; test res
>           movl    acquires_count, %edx    ; load
>           adcl    $0, %edx                ; maybe add 1
>           movl    %edx, acquires_count    ; store
> 
> So it just added the result of a comparison into a variable
> by (ab)using carry for this.

While this is OK in mono-threaded code, it introduces a race condition in
multi-threaded code. The code above tried to acquire a lock, and eax was
set to 1 if it succeeded. And whatever the result, all threads still
happily modify the shared memory area (acquires_count). So the classical
case where two threads perform the same operation at the same time ends
up with a random value in acquires_count.

> In theory such things can be done with CMOV too by redirecting
> a store into a dummy variable to cancel it, but gcc doesn't
> do that on its own.

Even with a CMOV, it's the memory write which should not be performed
if the lock was not acquired.

(...)
> But for registers it's a fine optimization.

100% agree.

What would really be needed is an attribute around conditions to
indicate whether they *may* be optimized or not. Something similar
to the likely/unlikely we currently use, we could have something
like __attribute__((unsafe_cond(cond))). I think that it could still
optimize by default but let the user explicitly state that he is
playing with thread-unsafe code. As you pointed out, you did not
find any such mis-optimization in the kernel, which means that it
does not hit too often. That's the reason why I'd let the user be
careful.

Willy

Re: Is gcc thread-unsafe?

[Nick Piggin]

On Friday 26 October 2007 09:09, Andi Kleen wrote:
> On Friday 26 October 2007 00:49:42 Nick Piggin wrote:

> > Marking volatile I think is out of the question. To start with,
> > volatile creates really poor code (and most of the time we actually
> > do want the code in critical sections to be as tight as possible).
>
> Poor code is better than broken code I would say. Besides
> the cross CPU synchronization paths are likely dominated by
> cache misses anyways; it's unlikely they're actually limited
> by the core CPU. So it'll probably not matter all that much
> if the code is poor or not.

But we have to mark all memory access inside the critical section
as volatile, even after the CPU synchronisation, and often the
common case where there is no contention or cacheline bouncing.

Sure, real code is dominated by cache misses anyway, etc etc.
However volatile prevents a lot of real optimisations that we'd
actually want to do, and increases icache size etc.


> > But also because I don't think these bugs are just going to be
> > found easily.
> >
> > > It might be useful to come up with some kind of assembler pattern
> > > matcher to check if any such code is generated for the kernel
> > > and try it with different compiler versions.
> >
> > Hard to know how to do it. If you can, then it would be interesting.
>
> I checked my kernel for "adc" at least (for the trylock/++ pattern)
> and couldn't find any (in fact all of them were in
> data the compiler thought to be code). That was not a allyesconfig build,
> so i missed some code.

sbb as well.


> For cmov it's at first harder because they're much more frequent
> and cmov to memory is a multiple instruction pattern (the instruction
> does only support memory source operands). Luckily gcc
> doesn't know the if (x) mem = a; => ptr = cmov(x, &a, &dummy); *ptr = a;
> transformation trick so I don't think there are actually any conditional
> stores on current x86.
>
> It might be a problem on other architectures which support true
> conditional stores though (like IA64 or ARM)

It might just depend on the instruction costs that gcc knows about.
For example, if ld/st is expensive, they might hoist them out of
loops etc. You don't even need to have one of these predicate or
pseudo predicate instructions.


> Also I'm not sure if gcc doesn't know any other tricks like the
> conditional add using carry, although I cannot think of any related
> to stores from the top of my hat.
>
> Anyways, if it's only conditional add if we ever catch such a case
> it could be also handled with inline assembly similar to local_inc()

But we don't actually know what it is, and it could change with
different architectures or versions of gcc. I think the sanest thing
is for gcc to help us out here, seeing as there is this very well
defined requirement that we want.

If you really still want the optimisation to occur, I don't think it
is too much to use a local variable for the accumulator (eg. in the
simple example case).

Re: Is gcc thread-unsafe?

[Andi Kleen]

> But we don't actually know what it is, and it could change with
> different architectures or versions of gcc. I think the sanest thing
> is for gcc to help us out here, seeing as there is this very well
> defined requirement that we want.
> 
> If you really still want the optimisation to occur, 

I don't think it makes sense for memory. It may may make sense for registers.

But given that my kernel doesn't seem to contain any instances
at all it's probably not too useful for it anyways.

So I wouldn't have a problem disabling it, but it would
be better if they fixed their heuristics to only apply it when
it makes sense. 

Unfortunately it's not possible as far as I know with current gccs.
I didn't think you can disable only ADC/SBB.

Disabling all of CMOV would be a pity though. Also I don't think
there is any way to do that except selecting a CPU architecture
that doesn't support it which would have other bad side effects
on the code.

-Andi

Re: Is gcc thread-unsafe?

[Nick Piggin]

On Friday 26 October 2007 09:55, Andi Kleen wrote:
> > But we don't actually know what it is, and it could change with
> > different architectures or versions of gcc. I think the sanest thing
> > is for gcc to help us out here, seeing as there is this very well
> > defined requirement that we want.
> >
> > If you really still want the optimisation to occur,
>
> I don't think it makes sense for memory. It may may make sense for
> registers.
>
> But given that my kernel doesn't seem to contain any instances
> at all it's probably not too useful for it anyways.
>
> So I wouldn't have a problem disabling it, but it would
> be better if they fixed their heuristics to only apply it when
> it makes sense.

That's what I mean -- disabling it for memory. I mean, I am just
talking about the conditional => unconditional store to a shared
variable optimisation.

So for example, adc, sbb, and cmov are all still fine when they
are used for the right things. I don't want to turn them off
because they really are quite useful.

As far as it being theoretical... I hope it is. But we should
nip this in the "bud" (gcc 3.x does this too, sigh) before it
causes problems for us (and any and all other threaded programs
and libraries out there). And by that I mean ask them for a
compiler option rather than start adding volatile.

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Thu, 25 Oct 2007, Nick Piggin wrote:
> 
> Andi spotted this exchange on the gcc list. I don't think he's
> brought it up here yet, but it worries me enough that I'd like
> to discuss it.

Are you surprised?

The gcc developers seem to have had a total disregard for what people 
want or need, and every time some code generation issue comes up, there's 
a lot of people on the list that do language-lawyering, rather than admit 
that there might be a problem.

It's happened before, it will happen again. I don't think it's true of all 
gcc developers (or even most, I hope), but it's common enough. For some 
reason, compiler developers seem to be far enough removed from "real life" 
that they have a tendency to talk in terms of "this is what the spec says" 
rather than "this is a problem".

Happily, at least in this kind of situation, threading is a real issue for 
other projects than just the kernel, so maybe it gets solved properly.

But I have to admit that for the last five years or so, I've really wanted 
some other compiler team to come up with a good open-source compiler. 
Exactly due to issues like this (Q: "Gcc creates bogus code that doesn't 
work!" A: "It's not bogus, it's technically allowed by the language specs 
that don't talk about xyz, the fact that it doesn't work isn't our 
problem").

I think the OpenBSD people decided to actually do something about this, 
and I suspect it had *nothing* to do with license issues, and everything 
to do with these kinds of problems. I wish them all the luck, although 
personally I think LLVM is a much more interesting project.

			Linus

Re: Is gcc thread-unsafe?

[Pekka Enberg]

Hi,

On 10/25/07, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> I think the OpenBSD people decided to actually do something about this,
> and I suspect it had *nothing* to do with license issues, and everything
> to do with these kinds of problems. I wish them all the luck, although
> personally I think LLVM is a much more interesting project.

The BSD people are adopting pcc [1] which is a rewritten version of
some C compiler originally developed in the late 70s. And yeah, it's
basically because they think gcc is becoming too painful to live with
[2].

                                  Pekka

  1. http://pcc.ludd.ltu.se/
  2. http://www.thejemreport.com/mambo/content/view/369/

RE: Is gcc thread-unsafe?

[David Schwartz]

	I asked a collection of knowledgeable people I know about the issue. The
consensus is that the optimization is not permitted in POSIX code but that
it is permitted in pure C code. The basic argument goes like this:

	To make POSIX-compliant code even possible, surely optimizations that add
writes to variables must be prohibited. That is -- if POSIX prohibits
writing to a variable in certain cases only the programmer can detect, then
a POSIX-compliant compiler cannot write to a variable except where
explicitly told to do so. Any optimization that *adds* a write to a variable
that would not otherwise occur *must* be prohibited.

	Otherwise, it is literally impossible to comply with the POSIX requirement
that concurrent modifications and reads to shared variables take place while
holding a mutex.

	The simplest solution is simply to ditch the optimization. If it really
isn't even an optimization, then that's an easy way out.

	DS

Re: Is gcc thread-unsafe?

[Nick Piggin]

Can you retain cc list, please?

On Friday 26 October 2007 07:42, David Schwartz wrote:
> 	I asked a collection of knowledgeable people I know about the issue. The
> consensus is that the optimization is not permitted in POSIX code but that
> it is permitted in pure C code. The basic argument goes like this:
>
> 	To make POSIX-compliant code even possible, surely optimizations that add
> writes to variables must be prohibited. That is -- if POSIX prohibits
> writing to a variable in certain cases only the programmer can detect, then
> a POSIX-compliant compiler cannot write to a variable except where
> explicitly told to do so. Any optimization that *adds* a write to a
> variable that would not otherwise occur *must* be prohibited.
>
> 	Otherwise, it is literally impossible to comply with the POSIX requirement
> that concurrent modifications and reads to shared variables take place
> while holding a mutex.

Now all you have to do is tell this to the gcc developers ;)


> 	The simplest solution is simply to ditch the optimization. If it really
> isn't even an optimization, then that's an easy way out.

For some things, I'd expect it will be an optimisation, which is why
they're even doing it. Even on x86 perhaps, where they do tricks with
sbb/adc. If it avoids an unpredictable branch, it could help. Actually
a silly microbenchmark shows it's worth 10% to do a cmov vs an
unpredictable conditional jump, but another 2.5% to do the adc and
unconditional store (which is the problematic bit).

And for unshared things like local variables where their address
hasn't escaped, it's fine.

Still, I guess that for most non-stack variables, you would actually
_want_ to do a cmov rather than the adc, even in a single threaded
program. Because you don't want to touch the cacheline if possible,
let alone dirty it.

Re: Is gcc thread-unsafe?

[Andrew Haley]

[ I had to resend this message.  Sorry if you received two copies. ]

Nick Piggin writes:
 > Can you retain cc list, please?
 > 
 > On Friday 26 October 2007 07:42, David Schwartz wrote:

 > > 	I asked a collection of knowledgeable people I know about the
 > > issue. The consensus is that the optimization is not permitted in
 > > POSIX code but that it is permitted in pure C code. The basic
 > > argument goes like this:
 > >
 > > 	To make POSIX-compliant code even possible, surely
 > > optimizations that add writes to variables must be
 > > prohibited. That is -- if POSIX prohibits writing to a variable
 > > in certain cases only the programmer can detect, then a
 > > POSIX-compliant compiler cannot write to a variable except where
 > > explicitly told to do so. Any optimization that *adds* a write to
 > > a variable that would not otherwise occur *must* be prohibited.

I don't think that POSIX is quite as explicit as that.  See
http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

 > > 	Otherwise, it is literally impossible to comply with the POSIX
 > > requirement that concurrent modifications and reads to shared
 > > variables take place while holding a mutex.
 > 
 > Now all you have to do is tell this to the gcc developers ;)

We're listening, really.  It's unacceptable that gcc should break
code.

However, fixing it is hard.  The best plan is probably to implement
(part of) the proposed standard memory model, and that requires
careful consideration.  We could in theory simply disable this
particular optimization, but that probably isn't a good idea on its
own because other optimizations might well break other code in a
similar way.  We need to have a very close look at the thread-safe
memory model in order to determine where we do things that might
break.

An official standard containing this is still at least two years out.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

Re: Is gcc thread-unsafe?

[Andrew Haley]

Nick Piggin writes:
 > Can you retain cc list, please?
 > 
 > On Friday 26 October 2007 07:42, David Schwartz wrote:

 > > 	I asked a collection of knowledgeable people I know about the
 > > issue. The consensus is that the optimization is not permitted in
 > > POSIX code but that it is permitted in pure C code. The basic
 > > argument goes like this:
 > >
 > > 	To make POSIX-compliant code even possible, surely
 > > optimizations that add writes to variables must be
 > > prohibited. That is -- if POSIX prohibits writing to a variable
 > > in certain cases only the programmer can detect, then a
 > > POSIX-compliant compiler cannot write to a variable except where
 > > explicitly told to do so. Any optimization that *adds* a write to
 > > a variable that would not otherwise occur *must* be prohibited.

I don't think that POSIX is quite as explicit as that.  See
http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

 > > 	Otherwise, it is literally impossible to comply with the POSIX
 > > requirement that concurrent modifications and reads to shared
 > > variables take place while holding a mutex.
 > 
 > Now all you have to do is tell this to the gcc developers ;)

We're listening, really.  It's unacceptable that gcc should break
code.

However, fixing it is hard.  The best plan is probably to implement
(part of) the proposed standard memory model, and that requires
careful consideration.  We could in theory simply disable this
particular optimization, but that probably isn't a good idea on its
own because other optimizations might well break other code in a
similar way.  We need to have a very close look at the thread-safe
memory model in order to determine where we do things that might
break.

An official standard containing this is still at least two years out.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

Re: Is gcc thread-unsafe?

[Chris Friesen]

Andrew Haley wrote:

> We're listening, really.  It's unacceptable that gcc should break
> code.

In that case a conversion of a conditional branch to an unconditional 
write to a visible variable is not an acceptable behaviour.  Aside from 
the kernel issues, it would break any number of threaded userspace apps.

As was mentioned elsewhere, it's akin to sprinkling

int j = i; i = j;

throughout the code.  If "i" is accessed by multiple threads, this is 
not allowed unless a lock is held.

Chris

Re: Is gcc thread-unsafe?

[Ismail Dönmez]

Thursday 25 October 2007 Tarihinde 17:55:00 yazmıştı:
> I think the OpenBSD people decided to actually do something about this,
> and I suspect it had *nothing* to do with license issues, and everything
> to do with these kinds of problems. I wish them all the luck, although
> personally I think LLVM is a much more interesting project.

And on the LLVM side all hopes for clang [0] at least for better C++ error 
reporting ;-)

[0] http://clang.llvm.org/

-- 
Faith is believing what you know isn't so -- Mark Twain

Re: Is gcc thread-unsafe?

[Jeff Garzik]

Ismail Dönmez wrote:
> Thursday 25 October 2007 Tarihinde 17:55:00 yazmıştı:
>> I think the OpenBSD people decided to actually do something about this,
>> and I suspect it had *nothing* to do with license issues, and everything
>> to do with these kinds of problems. I wish them all the luck, although
>> personally I think LLVM is a much more interesting project.
> 
> And on the LLVM side all hopes for clang [0] at least for better C++ error 
> reporting ;-)
> 
> [0] http://clang.llvm.org/

Someone should take 'sparse' and use that as a C language front-end to 
LLVM...

	Jeff

Re: Is gcc thread-unsafe?

[Jeff Garzik]

Jeff Garzik wrote:
> Ismail Dönmez wrote:
>> Thursday 25 October 2007 Tarihinde 17:55:00 yazmıştı:
>>> I think the OpenBSD people decided to actually do something about this,
>>> and I suspect it had *nothing* to do with license issues, and everything
>>> to do with these kinds of problems. I wish them all the luck, although
>>> personally I think LLVM is a much more interesting project.
>>
>> And on the LLVM side all hopes for clang [0] at least for better C++ 
>> error reporting ;-)
>>
>> [0] http://clang.llvm.org/
> 
> Someone should take 'sparse' and use that as a C language front-end to 
> LLVM...

Among clang's "features":
	"A single unified parser for C/ObjC/C++"

bleh.  I cannot imagine how ugly a C parser gets, after being taught 
C++.  IMO since you can basically redefine everything in C++, it's not a 
language but a proto-language.

	Jeff

Re: Is gcc thread-unsafe?

[Phillip Susi]

>             pushl   %ebp
>             movl    %esp, %ebp
>             cmpl    $0, 8(%ebp)
>             movl    $1, %eax
>             cmove   v, %eax        ; load (maybe)
>             movl    %eax, v        ; store (always)
>             popl    %ebp
>             ret

How is this even an optimization?  It looks SLOWER to me.  The 
conditional read wastes memory bandwidth sometimes, if the condition is 
true, and v isn't already in the cache.  The unconditional write wastes 
memory bandwidth ALL the time, and dirties/flushes caches, in addition 
to not being thread safe.

This SHOULD be using a conditional write instead of a conditional read 
and an unconditional write.

Re: Is gcc thread-unsafe?

[Robert Hancock]

Arjan van de Ven wrote:
> On Wed, 24 Oct 2007 21:29:56 -0700
> "David Schwartz" <davids@webmaster.com> wrote:
> 
>>> Well that's exactly right. For threaded programs (and maybe even
>>> real-world non-threaded ones in general), you don't want to be
>>> even _reading_ global variables if you don't need to. Cache misses
>>> and cacheline bouncing could easily cause performance to completely
>>> tank in some cases while only gaining a cycle or two in
>>> microbenchmarks for doing these funny x86 predication things.
>> For some CPUs, replacing an conditional branch with a conditional
>> move is a *huge* win because it cannot be mispredicted.
> 
> please name one...
> Hint: It's not one made by either Intel or AMD in the last 4 years...

It is a win if the branch cannot be effectively predicted, i.e. if the 
outcome is essentially random, as may occur with data-dependent 
conditionals. I've seen a doubling of performance on one workload using 
a predicated instruction instead of a branch on newer Xeons in such a case.

I suspect that if branch prediction fails often, the data dependency 
created by the cmov, etc. is less expensive than the pipeline flush 
required by mispredicts..

-- 
Robert Hancock      Saskatoon, SK, Canada
To email, remove "nospam" from hancockr@nospamshaw.ca
Home Page: http://www.roberthancock.com/

Re: Is gcc thread-unsafe?

[Bart Van Assche]

On 10/25/07, Linus Torvalds <> wrote:

> The gcc developers seem to have had a total disregard for what people
> want or need, and every time some code generation issue comes up, there's
> a lot of people on the list that do language-lawyering, rather than admit
> that there might be a problem.

Please make a proposal for how gcc should be modified instead of just
shooting on the gcc people -- the root cause here is the way the C/C++
memory model is defined. (Note: I'm not in any way involved in gcc
development.)

You can find my proposal to improve gcc here:
http://gcc.gnu.org/ml/gcc/2007-10/msg00465.html

Bart Van Assche.

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Bart Van Assche wrote:
> On 10/25/07, Linus Torvalds <> wrote:
> > 
> > The gcc developers seem to have had a total disregard for what people
> > want or need, and every time some code generation issue comes up, there's
> > a lot of people on the list that do language-lawyering, rather than admit
> > that there might be a problem.
> 
> Please make a proposal for how gcc should be modified instead of just
> shooting on the gcc people -- the root cause here is the way the C/C++
> memory model is defined. (Note: I'm not in any way involved in gcc
> development.)

Note that I'm very ambivalent about gcc. I think it's a *great* compiler. 
I have my doubts about some of the things it does, but hey, it is an old 
project, it has accumulated cruft over time, and cleaning things up is 
often almost impossible.

And bugs happen. I'm not complaining about that at all either, even if 
sometimes a compiler bug is damn frustrating.

And the fact is, most of the gcc developers are great.

So my basic worry about gcc is in fact none of the individual technical 
problems themselves - those can be fixed. No, the problem I've seen in gcc 
is that _some_ of the developers seem to be total d*ckheads when it comes 
to "language definition", and seem to think that it's more important to 
read the language spec like a lawyer than it is to solve actual user 
problems.

And that has come up before. It has nothing to do with this particular 
"gcc doesn't create thread-safe code" issue. We had the exact same issue 
with gcc creating totally unusable code due to having a fundamentally 
braindead memory aliasing model. The language-lawyering people basically 
could push their *idiotic* model onto gcc, just by quoting the standard, 
and not caring about actual users at all.

And that's a problem. In the kernel, we've historically always cared a lot 
about POSIX and SuS, but while conforming to standards have been primary 
goals since pretty much day one (ie I asked around about POSIX before the 
very first release, and it's how I met some suckers^Wupstanding citizens 
to try those early kernels), it has *always* taken a back seat to things 
like compatibility with existing apps.

The gcc lists seem to often get to the point where people quote the 
standard, and that's that. In that environment, the paper standard (that 
hass *nothing* to do with reality) trumps any other argument. "What we do 
is _allowed_ by the standard" seems to be a good argument, even if it 
breaks real code and there is no sane way to avoid doing it.

And I really don't think it's everybody. At all. But I think it's the case 
that sometimes it's easier to quote the standard than write good code, and 
so gcc lists have more people quoting the papers than trying to fix some 
problem.

			Linus

Re: Is gcc thread-unsafe?

[Andrew Haley]

Linus Torvalds writes:
 
 > So my basic worry about gcc is in fact none of the individual
 > technical problems themselves - those can be fixed. No, the problem
 > I've seen in gcc is that _some_ of the developers seem to be total
 > d*ckheads when it comes to "language definition", and seem to think
 > that it's more important to read the language spec like a lawyer
 > than it is to solve actual user problems.

Well, yeah.  I know what you mean.  However, at this moment, some gcc
developers are trying really hard not to be total d*ckheads about this
issue, but get gcc fixed.  Give us a chance.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

RE: Is gcc thread-unsafe?

[David Schwartz]

> Well, yeah.  I know what you mean.  However, at this moment, some gcc
> developers are trying really hard not to be total d*ckheads about this
> issue, but get gcc fixed.  Give us a chance.
>
> Andrew.

Can we get some kind of consensus that 'optimizations' that add writes to
any object that the programmer might have taken the address of are invalid
on any platform that supports memory protection? That seems like obvious
common sense to me.

And it has the advantage that it can't be language-lawyered. There is no
document that states the rational requirements of a compiler that's going to
support a memory protection model. So they can be anything rational people
think they should be.

DS

RE: Is gcc thread-unsafe?

[Andrew Haley]

David Schwartz writes:
 > 
 > > Well, yeah.  I know what you mean.  However, at this moment, some
 > > gcc developers are trying really hard not to be total d*ckheads
 > > about this issue, but get gcc fixed.  Give us a chance.
 > 
 > Can we get some kind of consensus that 'optimizations' that add
 > writes to any object that the programmer might have taken the
 > address of are invalid on any platform that supports memory
 > protection?

That's what the proposed standard language says, kinda-sorta.  There's
an informal description at
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html.

Anyway, we have fixed this bug and are committing it to all open gcc
branches.  Credit to Ian Taylor for writing the patch.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

Re: Is gcc thread-unsafe?

[Bart Van Assche]

On 10/30/07, Andrew Haley <aph@redhat.com> wrote:
> David Schwartz writes:
> >
> > Can we get some kind of consensus that 'optimizations' that add
> > writes to any object that the programmer might have taken the
> > address of are invalid on any platform that supports memory
> > protection?
>
> That's what the proposed standard language says, kinda-sorta.  There's
> an informal description at
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html.

There is other important information in the cited text. A.o. it is
explained that register promotion of potentially shared variables can
introduce data races. Or: register promotion can introduce bugs in
multithreaded software when compiled with optimization enabled. Are
there any register promotion transformations implemented in gcc that
can introduce data races in multithreaded software ? This is very
important information both for kernel developers and for developers of
multithreaded userspace applications.

Another conclusion from the cited text is that in contrast with what
was stated before on the gcc mailing list, it is not required to
declare thread-shared variables volatile if that thread-shared data is
consistently protected by calls to locking functions.

Bart Van Assche.

Re: Is gcc thread-unsafe?

[Andrew Haley]

Bart Van Assche writes:
 > On 10/30/07, Andrew Haley <aph@redhat.com> wrote:
 > > David Schwartz writes:
 > > >
 > > > Can we get some kind of consensus that 'optimizations' that add
 > > > writes to any object that the programmer might have taken the
 > > > address of are invalid on any platform that supports memory
 > > > protection?
 > >
 > > That's what the proposed standard language says, kinda-sorta.  There's
 > > an informal description at
 > > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html.
 > 
 > There is other important information in the cited text. A.o. it is
 > explained that register promotion of potentially shared variables
 > can introduce data races. Or: register promotion can introduce bugs
 > in multithreaded software when compiled with optimization
 > enabled. Are there any register promotion transformations
 > implemented in gcc that can introduce data races in multithreaded
 > software ?

I expect so.  We're going to have to audit this whole enormous code
base to find them all and take them out.

Note that some of these optimizations have been around since gcc 3.4.

 > This is very important information both for kernel developers and
 > for developers of multithreaded userspace applications.

 > Another conclusion from the cited text is that in contrast with
 > what was stated before on the gcc mailing list, it is not required
 > to declare thread-shared variables volatile if that thread-shared
 > data is consistently protected by calls to locking functions.

Well, let's be clear: ISO 9899:1999 doesn't say so, but the proposed
standard language does.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

Re: Is gcc thread-unsafe?

[Bart Van Assche]

On 11/2/07, Andrew Haley <aph@redhat.com> wrote:
> Bart Van Assche writes:
> > On 10/30/07, Andrew Haley <aph@redhat.com> wrote:
> > > That's what the proposed standard language says, kinda-sorta.  There's
> > > an informal description at
> > > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html.
> >
> > There is other important information in the cited text. A.o. it is
> > explained that register promotion of potentially shared variables
> > can introduce data races. Or: register promotion can introduce bugs
> > in multithreaded software when compiled with optimization
> > enabled. Are there any register promotion transformations
> > implemented in gcc that can introduce data races in multithreaded
> > software ?
>
> I expect so.  We're going to have to audit this whole enormous code
> base to find them all and take them out.
>
> Note that some of these optimizations have been around since gcc 3.4.

Has it already been decided who will do this audit, and when this
audit will happen ? Has a target date been set when this audit should
be complete, or is the completion of this audit a requirement for the
release of a specific gcc version ?

And if there would exist register promotion transformations in gcc
that can introduce data races, which would be the optimization levels
that enable these transformations ?

Bart Van Assche.

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Sun, 4 Nov 2007, Bart Van Assche wrote:
> 
> Has it already been decided who will do this audit, and when this
> audit will happen ? Has a target date been set when this audit should
> be complete, or is the completion of this audit a requirement for the
> release of a specific gcc version ?

I am told that the gcc people realized that was indeed a bug (people were 
able to show problems even in non-threaded environments with mprotect()), 
and have now fixed it in the current gcc sources. That still leaves the 
old versions with potential problems, but I think it makes it much less 
interesting to audit for these things.

		Linus

Re: Is gcc thread-unsafe?

[Andrew Haley]

Linus Torvalds writes:
 > 
 > 
 > On Sun, 4 Nov 2007, Bart Van Assche wrote:
 > > 
 > > Has it already been decided who will do this audit, and when this
 > > audit will happen ? Has a target date been set when this audit
 > > should be complete, or is the completion of this audit a
 > > requirement for the release of a specific gcc version ?
 > 
 > I am told that the gcc people realized that was indeed a bug
 > (people were able to show problems even in non-threaded
 > environments with mprotect()), and have now fixed it in the current
 > gcc sources. That still leaves the old versions with potential
 > problems, but I think it makes it much less interesting to audit
 > for these things.

We're back-porting the patch to all open branches.  However, this
patch only affects one paticular case where gcc introduces a data
race; we're sure there are others not fixed.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

Re: Is gcc thread-unsafe?

[Bart Van Assche]

On 11/4/07, Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
> On Sun, 4 Nov 2007, Bart Van Assche wrote:
> >
> > Has it already been decided who will do this audit, and when this
> > audit will happen ? Has a target date been set when this audit should
> > be complete, or is the completion of this audit a requirement for the
> > release of a specific gcc version ?
>
> I am told that the gcc people realized that was indeed a bug (people were
> able to show problems even in non-threaded environments with mprotect()),
> and have now fixed it in the current gcc sources. That still leaves the
> old versions with potential problems, but I think it makes it much less
> interesting to audit for these things.
>
>                 Linus

What I understood from the gcc mailing list is that a patch has been
applied to the gcc sources that solves the issue with speculative
stores that was already discussed here on the LKML
(http://gcc.gnu.org/ml/gcc/2007-10/msg00554.html).

But the issue I am referring to is a different issue: namely that a
compiler optimization called register promotion can introduce data
races. Hans J. Boehm has a clear explanation of this -- see also
paragraph 4.3 in
http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf or
http://portal.acm.org/citation.cfm?id=1064978.1065042 .

Bart Van Assche.

RE: Is gcc thread-unsafe?

[David Schwartz]

> Another conclusion from the cited text is that in contrast with what
> was stated before on the gcc mailing list, it is not required to
> declare thread-shared variables volatile if that thread-shared data is
> consistently protected by calls to locking functions.
>
> Bart Van Assche.

It all depends upon what threading standard you are using. If GCC is going
to support POSIX threading, it cannot require that thread-shared data be
marked 'volatile' since POSIX does not require this.

It can offer semantic guarantees for volatile-qualified data if it wants to.
But POSIX provides a set of guarantees that do not require marking data as
'volatile' and if GCC is going to support POSIX threading, it has to support
providing those guarantees.

As far as I know, no threading standard either requires 'volatile' or states
that it is sufficient for any particular purpose. So there seems to be no
reason to declare thread-shared variables as
volatile except as some kind of platform-specific optimization.

POSIX mutexes are sufficient. They are necessary if there is no other way to
get the guarantees you need. Nothing prevents GCC from providing any
guarantees it wants for 'volatile' qualified data. But POSIX mutexes must
work as POSIX specifies or GCC cannot support POSIX threading.

This is the nightmare scenario (thanks to Hans-J. Boehm):

int x;
bool need_to_lock;
pthread_mutex_t mutex;

for(int i=0; i<50; i++)
{
 if(unlikely(need_to_lock)) pthread_mutex_lock(&mutex);
 x++;
 if(unlikely(need_to_lock)) pthread_mutex_unlock(&mutex);
}

Now suppose the compiler optimizes this as follows:

register=x;
for(int i=0; i<50; i++)
{
 if(need_to_lock)
 {
  x=register; pthread_mutex_lock(&mutex) register=x;
 }
 register++;
 if(need_to_lock)
 {
  x=register; pthread_mutex_unlock(&mutex); register=x;
 }
}
x=register;

This is a perfectly legal optimization for single-threaded code. It may in
fact be an actual optimization. Clearly, it totally destroys threaded code.

This shows that, unfortunately, the normal assumption that not knowing
anything about the pthread functions ensures that optimizations won't break
them is incorrect.

DS

Re: Is gcc thread-unsafe?

[Giacomo Catenazzi]

Linus Torvalds wrote:

> The gcc lists seem to often get to the point where people quote the 
> standard, and that's that. In that environment, the paper standard (that 
> hass *nothing* to do with reality) trumps any other argument. "What we do 
> is _allowed_ by the standard" seems to be a good argument, even if it 
> breaks real code and there is no sane way to avoid doing it.

So we have the great opportunity to change the standard, then
gcc will change ;-)

C is in pre-review phase, and it is taking proposal and correction for the C1x
(so in few kernel release ;-) )

ciao
	cate

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Giacomo Catenazzi wrote:
> 
> So we have the great opportunity to change the standard, then
> gcc will change ;-)

I see the smiley, but sadly, new standards take ten years or more to 
mature. Which means that even if the upcoming one is "perfect", things 
will be wrong with it, if only because people will have new usage 
scenarios where the standard simply isn't relevant or that it otherwise 
just doesn't address, and that then gets us back to the same issues 
somewhere else.

So it would be much better if developers just didn't think the standard 
trumped "real and existing code and problems", and shot down the language 
lawyers (and don't get me wrong - it's not just in gcc, btw. We _have_ had 
some of the same behavior in the kernel, although I will argue that our 
"backwards compatibility trumps pretty much everything else" rules at 
least solves _some_ of the problems).

Standards are just papers. Yes, they're important, but they are definitely 
not more important than anything else, and they are a lot _less_ important 
than some people seem to think. Gcc has done more for programming by being 
a de-facto standard and widely available, than the _paper_ standards often 
ever do!

It's also sad that a lot of these things seem to be done in the name of 
optimizing code, and then in many cases it drives people *away* from using 
that optimizer for anything but benchmarking.

In the kernel, we historically used to try for extreme optimizations, 
these days we spend more time tuning the optimizations _down_ because they 
aren't optimizations at all (ie using -Os instead of -O2), or they were 
buggy enough that we have to explicitly disable them (aliasing, 
"unit-at-a-time" etc).

			Linus

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Bart Van Assche wrote:
> 
> You can find my proposal to improve gcc here:
> http://gcc.gnu.org/ml/gcc/2007-10/msg00465.html

Btw, I think this is fine per se, but putting "__attribute__((acquire))" 
on the functions that acquire a lock does seem to be problematic, in that 
quite often you might well want to inline those things. How would you 
handle that?

The fact is, the whole optimization is broken. You should never do 
extraneous writes to anything but registers (or your own spill pool on the 
stack - anything that hasn't had its address taken and cannot be visible 
to outsiders). A C compiler should basically do what the user asks it to 
do, and that means that it simply should be _very_ nervous about doing 
optimizations that can have visible secondary effects.

So the first question that should be asked is: "is that optimization even 
worth it in the first place outside of registers and the spill pool?"

If an optimization introduces visible behaviour differences to the 
"obvious" stupid interpretation of the code, it should automatically be 
something that should be given a lot of thought, and perhaps not enabled 
at all by default (where "default" is certainly normal optimization 
levels).

And different languages have different usages. In C, it's quite common 
(and _possible_) for the programmer to specify how to do things at a 
fairly low level. That's not true in all other languages, and it affects 
how a compiler should optimize things. In C, a compiler should give more 
weight to "this is how the user specified the solution" because in C, 
programmers really *do* that. 

So I don't think your proposal is wrong, but I think before even going to 
something like that, you should ask yourself: "was that a valid 
optimization to start with?"

(That said, there may well be *other* reasons for wanting gcc to know 
about lock/unlock behaviour and teaching gcc about barriers. If gcc starts 
getting more threading knowledge, gcc may well need to have that kind of 
information in other places).

				Linus

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Linus Torvalds wrote:

> 
> 
> On Fri, 26 Oct 2007, Bart Van Assche wrote:
> > 
> > You can find my proposal to improve gcc here:
> > http://gcc.gnu.org/ml/gcc/2007-10/msg00465.html
> 
> Btw, I think this is fine per se, but putting "__attribute__((acquire))" 
> on the functions that acquire a lock does seem to be problematic, in that 
> quite often you might well want to inline those things. How would you 
> handle that?

Thinking some more about this, you really have two cases:

 - full functions taking/releasing locks (possibly conditionally, ie 
   with something lik etrylock and/or based on argument values). 

   You simply *cannot* require these to be marked, because the locking may 
   have been done indirectly. Yes, you can mark things like 
   "pthread_mutex_trylock()" as being an acquire-function, but the fact 
   is, users will then wrap these things in *other* functions, and return 
   their return values.

   Ergo: a compiler *must* assume that a function call that it 
   didn't inline involves locking. There's no point in adding some 
   gcc-specific attributes to system header files, because it's not going 
   to fix anything in any portable program.

 - inline assembly (together with, potentially, compiler primitives). 
   That's the only other way to reliably do locking from C. 

   This one gcc could certainly extend on. But would there really be any 
   upside? It would be easier/better to say that inline assembly (at least 
   if it clobbers memory or is volatile) has the same serialization issues 
   as a function call.

So the fact is, any compiler that turns

	if (conditional)
		x++;

into an unconditional write to x (where 'x' is potentially visible to the 
outside - global visibility or has had its address taken) is just broken. 

No ifs, buts or maybes about it. You simply cannot do that optimization, 
because there is no way for the compiler to know whether the conditional 
implies that you hold a lock or not.

				Linus

Re: Is gcc thread-unsafe?

[Bart Van Assche]

On 10/26/07, Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
> On Fri, 26 Oct 2007, Linus Torvalds wrote:
> >
> > On Fri, 26 Oct 2007, Bart Van Assche wrote:
> > >
> > > You can find my proposal to improve gcc here:
> > > http://gcc.gnu.org/ml/gcc/2007-10/msg00465.html
> >
> > Btw, I think this is fine per se, but putting "__attribute__((acquire))"
> > on the functions that acquire a lock does seem to be problematic, in that
> > quite often you might well want to inline those things. How would you
> > handle that?
>
> Thinking some more about this, you really have two cases:
>  - full functions taking/releasing locks (possibly conditionally, ie
>   with something like trylock and/or based on argument values).
>
>   You simply *cannot* require these to be marked, because the locking may
>   have been done indirectly. Yes, you can mark things like
>   "pthread_mutex_trylock()" as being an acquire-function, but the fact
>   is, users will then wrap these things in *other* functions, and return
>   their return values.
>
>   Ergo: a compiler *must* assume that a function call that it
>   didn't inline involves locking. There's no point in adding some
>   gcc-specific attributes to system header files, because it's not going
>   to fix anything in any portable program.

You have a point here.

>  - inline assembly (together with, potentially, compiler primitives).
>    That's the only other way to reliably do locking from C.
>
>    This one gcc could certainly extend on. But would there really be any
>    upside? It would be easier/better to say that inline assembly (at least
>    if it clobbers memory or is volatile) has the same serialization issues
>    as a function call.

A problem is that the serialization properties defined for functions
in the C standard only apply to volatile variables, not to
non-volatile variables. But for asm statements this can be solved by
adding memory to the list of clobbered registers -- this will prevent
any reordering of manipulations of non-volatile variables and asm
statements.

Andrew, do you know whether gcc currently contains any optimization
that interchanges the order of accesses to non-volatile variables and
function calls ?

> So the fact is, any compiler that turns
>
>         if (conditional)
>                 x++;
>
> into an unconditional write to x (where 'x' is potentially visible to the
> outside - global visibility or has had its address taken) is just broken.
>
> No ifs, buts or maybes about it. You simply cannot do that optimization,
> because there is no way for the compiler to know whether the conditional
> implies that you hold a lock or not.

I agree with the above, but I see this as a different issue -- it
wasn't my intention to solve this with my proposal for acquire and
release attributes.

Bart Van Assche.

Re: Is gcc thread-unsafe?

[Andrew Haley]

Bart Van Assche writes:

 > Andrew, do you know whether gcc currently contains any optimization
 > that interchanges the order of accesses to non-volatile variables
 > and function calls ?

It sure does.

Andrew.

-- 
Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK
Registered in England and Wales No. 3798903

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Andrew Haley wrote:
>
> Bart Van Assche writes:
> 
>  > Andrew, do you know whether gcc currently contains any optimization
>  > that interchanges the order of accesses to non-volatile variables
>  > and function calls ?
> 
> It sure does.

Note that doing so is perfectly fine.

But only for local variables that haven't had their addresses taken.

The fact is, those kinds of variables really *are* special. They are 
provably not accessible from any other context, and re-ordering them (or 
doing anything AT ALL to them - the most basic and very important 
optimization is caching them in registers, of course) is always purely an 
internal compiler issue.

But if gcc re-orders functions calls with *other* memory accesses, gcc is 
totally broken. I doubt it does that. It would break on all but the most 
trivial programs, and it would be a clear violation of even standard C.

HOWEVER: the bug that started this thread isn't even "reordering 
accesses", it's *adding* accesses that weren't there (and please don't mix 
this up with "volatile", since volatile is a totally unrelated issue and 
has nothing what-so-ever to do with anything).

		Linus

Re: Is gcc thread-unsafe?

[Alan Cox]

> non-volatile variables. But for asm statements this can be solved by
> adding memory to the list of clobbered registers -- this will prevent
> any reordering of manipulations of non-volatile variables and asm
> statements.

IFF the processor doesn't reorder them in hardware, which on some
processors is visibly out of order when viewed from an I/O device or
another CPU.

You can stop the compiler but not the CPU - and some processors will
certainly speculatively load across conditionals, reorder writes etc

Re: Is gcc thread-unsafe?

[Linus Torvalds]

On Fri, 26 Oct 2007, Alan Cox wrote:
>
> > non-volatile variables. But for asm statements this can be solved by
> > adding memory to the list of clobbered registers -- this will prevent
> > any reordering of manipulations of non-volatile variables and asm
> > statements.
> 
> IFF the processor doesn't reorder them in hardware, which on some
> processors is visibly out of order when viewed from an I/O device or
> another CPU.
> 
> You can stop the compiler but not the CPU - and some processors will
> certainly speculatively load across conditionals, reorder writes etc

Well, when we're talking inline asms used for locking, the whole point of 
using inline asm is exactly that you cannot do it with regular accesses, 
and have to add architecture-specific barriers. If the user gets that 
wrong, then it's a user problem, not a compiler issue.

So that's not the problem. The problem is if the compiler then does other 
things wrong *despite* the inline asm being correct. 

				Linus

Re: Is gcc thread-unsafe?

[Andi Kleen]

Alan Cox <alan@lxorguk.ukuu.org.uk> writes:
>
> You can stop the compiler but not the CPU - and some processors will
> certainly speculatively load across conditionals, reorder writes etc

The difference is that the CPU knows how to cancel most[1] side effects
of these speculative accesses (e.g. by not issuing exceptions[2] etc.). 

The compiler doesn't normally (except on some architectures with special support like IA64;
but I'm not sure gcc supports it there) 

[1] In some it can't and we've had problems with that in the past. e.g. in
a few cases speculative reads can be a problem. But we generally fix or
workaround those cases in the code.
[2] Modulo hardware bugs -- see the hall of shame in x86_64 fault.c

-Andi

Re: Is gcc thread-unsafe?

[linux]

Just a note on the attribute((acquire,release)) proposal:

It's nice to be able to annotate functions, but please don't forget to
provide a way to write such functions.  Ultimately, there will be an
asm() or assignment that is the acquire or release point, and GCC needs
to know that so it can compile the function itself (possibly inline).

Having just a function attribute leaves the problem that

void __attribute__((noreturn))
_exit(int status)
{
	asm("int 0x80" : : (__NR_exit) "a", (status) "b" );
}

generates a complaint about a noreturn function returning, because
there's no way to tell GCC about a non-returning statement.