LWN: Comments on "Betrayed by a bitfield"

Betrayed by a bitfield

jwakely — Fri, 17 Feb 2012 16:20:39 +0000

> as -pthread is supposed to switch on the POSIX memory model in gcc

Says who?

On ia64-linux it appears to be equivalent to just -D_REENTRANT, on x86-linux it also passes -lpthread to the linker, but it has no effect on code-generation.

> they don't want full sequential consistency in all cases because of its efficiency implications.

Which part of the C11 memory model requires sequential consistency?

Betrayed by a bitfield

chrisV — Thu, 16 Feb 2012 20:21:38 +0000

Any chance you could file a bug on this one? It is not so bad if the non-standard use of volatile has this effect (although no doubt still very annoying to the kernel developers), but it seems to me to be something else when the code happens to be POSIX-conforming code and corrupts memory locations.

(Yes I have seen the argument in papers in the early proposals for the C/C++ threading model that "memory location" is ambiguous in Base Definitions, section 4.11, of the SUS, and could refer to a machine's natural word size rather than individual scalars, and so C11/C++11 now explicitly states that "memory location" in its equivalent wording means any scalar or bitfield, but that is a completely perverse construction of the SUS as it makes POSIX threads completely useless as a standard, bringing threading back to individual non-standard ABIs.)

Betrayed by a bitfield

cbf123 — Wed, 15 Feb 2012 17:01:14 +0000

I just tested with gcc version 4.3.2 (Wind River Linux Sourcery G++ 4.3-85) for powerpc. Building the test app (the volatile version) as "gcc x.c -c -m64 -pthread" resulted in the following code, which clearly shows a 64-bit read/write cycle.

0000000000000000 <.wrong>:
   0:   fb e1 ff f8     std     r31,-8(r1)
   4:   f8 21 ff c1     stdu    r1,-64(r1)
   8:   7c 3f 0b 78     mr      r31,r1
   c:   f8 7f 00 70     std     r3,112(r31)
  10:   e9 3f 00 70     ld      r9,112(r31)
  14:   e8 09 00 08     ld      r0,8(r9)
  18:   39 60 00 01     li      r11,1
  1c:   79 60 f8 2c     rldimi  r0,r11,31,32
  20:   f8 09 00 08     std     r0,8(r9)
  24:   e8 21 00 00     ld      r1,0(r1)
  28:   eb e1 ff f8     ld      r31,-8(r1)
  2c:   4e 80 00 20     blr

A single historical context of volatile

dfsmith — Fri, 10 Feb 2012 22:22:30 +0000

To quote from Harbison & Steele 3rd ed. (1991)* section 4.4.5

"... any object ... of a volatile-qualified type should not participate in optimizations that would ... modif[y] the object."

To my mind that prohibition includes non-volatile object optimizations that would clobber volatile objects.

The book then slightly contradicts itself two paragraphs later by saying that "optimizations between sequence points are permitted" before clarifying with a hardware example.

* A standard ANSI C reference manual for programmers and compiler implementers at the time.

Betrayed by a bitfield

jd — Thu, 09 Feb 2012 17:51:34 +0000

Can't we just give a "Compiler On Acid" error?

Betrayed by a bitfield

daglwn — Wed, 08 Feb 2012 15:24:55 +0000

Seeing some of your other posts about -pthread, I think we are in agreement. Apologies if I mischaracterized your understanding.

Betrayed by a bitfield

nix — Wed, 08 Feb 2012 13:57:21 +0000

SPARC is another major example of an arch with alignment-restricted loads and stores. I have dim memories that suggest that MIPS might be as well.

It's actually easier to come up with a list of architectures that do *not* require natural alignment on loads and stores than to come up with a list of those that do.

Betrayed by a bitfield

nix — Wed, 08 Feb 2012 13:51:39 +0000

And, thirdly, the kernel is not C11 code -- yet.

Betrayed by a bitfield

khim — Wed, 08 Feb 2012 08:54:52 +0000

YMMV, as usual.

We recompile the world anyway, so ABI change is less of a problem, but the fact that just a recompilation does not fix the issue and you need to do a lot of investigations is a problem.

Betrayed by a bitfield

daglwn — Wed, 08 Feb 2012 00:11:23 +0000

There are plenty of architectures that have these kinds of restricted loads and stores. The old Cray machines only ever operated on 64 bit words, for example.

And often a machine implements the smaller accesses but there is a performance penalty due to alignment issues and the bus/DRAM access architecture. It's not uncommon for the RMW to be faster.

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 23:32:34 +0000

> And if you get false sharing between two free-standing variables where the > one being operated on is marked volatile, or between fields of a struct
> where the struct is marked volatile, there is a compiler bug.

No, there isn't.

There isn't. Really.

Volatile does not mean what you think it means.

It's a bit like sequential consistency. Just when you think you understand it, something unexpected happens that is both non-intuitive and perfectly legal.

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 23:29:13 +0000

Ah, I read "C11."

Yes, you are correct, but I don't think there's an ABI issue. An ABI issue is much harder to deal with than a semantic change.

With an ABI issue you've got to recompile the world (your project, libraries it links to, etc.) to get a working application. With a semantic change you only recompile the bits that had to recoded to account for the change.

Betrayed by a bitfield

khim — Tue, 07 Feb 2012 20:53:16 +0000

> Perfectly working C++ program can already be broken by recompilation in
> C++11 mode

But as we all know, C++ is not C. :) I don't see this as a problem.

C++ is quite explicitly not C, but C++11 pretends that it's still C++.

Betrayed by a bitfield

chrisV — Tue, 07 Feb 2012 20:18:16 +0000

I want to keep your issues separate and I have asked you under a separate posting about your tests concerned. On the POSIX point, setting out the assembly output of test cases for Itanium, first without -pthread and then with -pthread, and showing the false sharing would be sufficient, as -pthread is supposed to switch on the POSIX memory model in gcc and it will quickly become apparent if it doesn't.

This posting is just to comment on your observations on the C11 memory model. You are quite right in saying it represents accumulated wisdom, because its starting point was the (comparatively under-specified) POSIX memory model for multi-threaded programs. However, if you read the lkml postings in questions, you will see that the kernel community do not want the generalized C11 memory model for the kernel. They want the preclusion of false sharing; they don't want full sequential consistency in all cases because of its efficiency implications.

Betrayed by a bitfield

dlang — Tue, 07 Feb 2012 20:01:12 +0000

the kernel did not have one field marked volatile, but in the research into the problem, someone (I think it was Linus) tested with volatile and the false sharing was happening there as well.

Betrayed by a bitfield

chrisV — Tue, 07 Feb 2012 19:36:31 +0000

And since you refer to "none of the options you are suggesting makes a slight difference", can you also clarify whether you mean you have run a test case demonstrating false sharing even in the case of 64-bit scalars, and/or even in the case of assembly instructions which should have forced synchronization?

Betrayed by a bitfield

chrisV — Tue, 07 Feb 2012 19:21:56 +0000

Are you telling me that you have actually run a test case compiled with the -pthread option which exhibits this problem? If not, I just don't believe you because I have written shed loads of multi-threaded code using POSIX threads which has never encountered a false sharing problem of this kind.

If you run a test case compiled with the -pthread flag which exhibits this problem then this is an egregious failure on the part of the threading implementation of gcc and you should post a bug. (It is far more serious than the non-standards complying kernel code.)

Betrayed by a bitfield

chrisV — Tue, 07 Feb 2012 19:07:43 +0000

I agree. And if you get false sharing between two free-standing variables where the one being operated on is marked volatile, or between fields of a struct where the struct is marked volatile, there is a compiler bug. It is still not clear whether that is the case with the kernel test case (first, the struct was not marked volatile, only one of its fields; and secondly, we don't know whether the test case involved an asynchronous test (as opposed to threads) or not.

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 18:38:57 +0000

> "It says nothing about interrupts."

Thanks for the correction. But the compiler is still correct here. Volatile doesn't say anything about restricting _when_ it is read or written, only that it will get the "latest" value in a single-thread context.

It's perfectly fine for I/O as long as you can guarantee alignment such that there is no "false sharing."

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 18:35:23 +0000

Ah, cool, didn't know about _Alignas. I'm a codegen guy so I'm not playing around in the C frontend very often. I only look at the standard when I really have to. :)

There's still an ABI problem if the compiler always has to align members to uphold the requirement.

> Perfectly working C++ program can already be broken by recompilation in
> C++11 mode

But as we all know, C++ is not C. :) I don't see this as a problem.

Betrayed by a bitfield

BenHutchings — Tue, 07 Feb 2012 17:12:14 +0000

None of the options you are suggesting makes a slight difference to gcc behaviour in this case. In any case, the C11 memory model is to a large extent a codification of what is already understood in the industry to be necessary to support multithreaded C programs.

Your unhelpful standards-lawyering attitude is exactly what many programmers have come to hate about certain compiler developers.

Betrayed by a bitfield

BenHutchings — Tue, 07 Feb 2012 17:06:47 +0000

Insane? I imagine the 6- and 16-bit processor guys said the same when Alpha appeared.

Yes, Alpha's lack of 8- and 16-bit store instructions was insane. That's why they were added in later versions of the architecture.

Betrayed by a bitfield

chrisV — Tue, 07 Feb 2012 16:54:12 +0000

"It says nothing about interrupts."

I think it does. See §5.1.2.3/5 and /10, which are normative. The principal purpose of volatile is to deal with arbitrary changes of data values outside the program context of the process in which the code is running (ie asynchronous interrupts). (This does not include threads, which are within the program context and which, because they can run on more than one core, require quite different synchronizations, some of which are not async-signal-safe.)

See also the footnote 134 of §6.7.3/8 (which is non-normative despite the "shall not"): "A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function. Actions on objects so declared shall not be 'optimized out' by an implementation or reordered except as permitted by the rules for evaluating expressions." This is a curious note as, as far as I am aware, it is the one and only reference to memory mapping (and about which I mis-spoke in an earlier posting on this article because it is not in C99 which contains no reference to memory mapping).

Betrayed by a bitfield

khim — Tue, 07 Feb 2012 08:46:45 +0000

This is why volatile is non-portable. Unfortunately, C99 has no standard way to force alignment of any object.

GCC, MSCV and other compilers include such an ability and C11 finally adds it to standard so it's all is not so bad...

Betrayed by a bitfield

khim — Tue, 07 Feb 2012 08:43:27 +0000

Since C11 includes _Alignas and you can specify you own alignment it's not a disaster, albeit it is inconvenience.

Perfectly working C++ program can already be broken by recompilation in C++11 mode, so it's not the first time upgrade broke things.

Of course is only possible if original program violated specs and worked by accident (if you can show me genuinely different behavior in standards-compliant program it'll be interesting to know, too, but so far all examples I've seen contained subtle violations of one form or another).

Betrayed by a bitfield

dlang — Tue, 07 Feb 2012 01:03:27 +0000

in that case I have to agree with the other poster who said that if the compiler considers it Ok to write over any arbitrary memory locations, as long as what it's writing matches what the compiler thinks is already there, then that compiler is unsuitable for use with any memory mapped I/O as it will feel free to clobber the new data that is waiting to be read.

since this sort of thing has been part of C's traditional strength, this doesn't seem like a sane interpretation to me.

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 00:52:42 +0000

Again, this is implementation-defined behavior. The standard you're looking for is the ABI for your target. That's where all the memory layout, access size, calling convention and other low-level stuff is specified.

Volatile is perfectly fine for I/O as long as you know the address being accessed is suitably aligned to avoid problems, as the ABI should indicate.

This is why volatile is non-portable. Unfortunately, C99 has no standard way to force alignment of any object.

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 00:48:44 +0000

> if modifying b causes a read/write of a, this is wrong.

No, it's not. Believe me.

The volatile keyword doesn't say anything about when it will change value, be read/written etc. It says simply that it will not be cached in a register such that every read will get the "latest" value expected when executed under the Abstract Machine.

It says nothing about threading.

It says nothing about interrupts.

Simply remember that volatile is not magic. Think of it as the opposite of "register."

Betrayed by a bitfield

daglwn — Tue, 07 Feb 2012 00:43:27 +0000

> If that is not available it may have to pad so that any 32-bit scalar
> occupies 64 bits of space, where necessary to conform to the standard.

Or pad 8 bits to 32, etc. This is what I mean by breaking ABI compatibility. If interfaces include struct values this could be a real nightmare.

Personally, I think this requirement is ridiculous absent some special attribute to enforce it. If there was a qualifier on a type to indicate "shared," _a_la_ UPC, that would be one thing. But to have this requirement for every single data item in the program is a very bad idea.

Betrayed by a bitfield

giraffedata — Mon, 06 Feb 2012 22:22:20 +0000

That's very interesting, because it seems to say the provision for "volatile" is so incomplete as to be a pointless language feature.
Not totally true. It's true that volatile doesn't do what most people expect. Basically, volatile says the data can't be cached in a register ...

I was commenting at a higher level. Never mind what the compiler can and can't do. The question is, what programs can you write in C because it has the "volatile" feature that you couldn't otherwise? Relying on nothing but that the compiler implements the C standard.

I've always understood the originally intended answer to be, "you can write a program that uses memory mapped I/O." But comments in this thread say regardless of how one uses the "volatile" keyword in a program, the compiler may always generate code that arbitrarily writes to memory mapped I/O addresses. There's nothing in the standard to stop it. If so, then you not only can't use memory mapped I/O in a C program, you can't even let a C program — any C program — run in an address space that includes memory mapped I/O regions.

Unless all memory-mapped I/O regions ignore writes.

And it's hard to believe that the definers of "volatile" actually had such a useless thing in mind.

Betrayed by a bitfield

dlang — Mon, 06 Feb 2012 21:39:31 +0000

Linus and several others in the kernel thread on the subject have said this.

Betrayed by a bitfield

chrisV — Mon, 06 Feb 2012 21:32:09 +0000

Well that should make it easier to get the gcc developers to deal with the ia64 at least, although I would take a little persuading that moving memory from 64 bit registers into non-64-bit aligned memory locations didn't cause some slow down in code operating in 64 bit mode. Do you have any citations for that?

Betrayed by a bitfield

chrisV — Mon, 06 Feb 2012 21:16:25 +0000

"no, the item in question wasn't related to interrupts, but the cause of the problem causes the same problem if interrupts were involved."

Not it doesn't. Memory access issues relating to multiple threads (or multiple processes in the case of shared memory) have nothing to do with interrupts, and nothing to do with volatile.

This really is beating a dead horse. Compiler switches are available to ensure memory consistency for the case in question, notably the -pthread switch. I can see why the kernel doesn't want to, or can't, use that. In that case the kernel authors need to write some assembler or use 64-bit values on architectures where it is important, or persuade the gcc developers to provide another compiler switch dealing with this particular problem.

Betrayed by a bitfield

dlang — Mon, 06 Feb 2012 21:11:26 +0000

32 bit operations are not slower on all 64 bit architectures, including specifically the ia64 architecture where this problem was discovered.

Betrayed by a bitfield

chrisV — Mon, 06 Feb 2012 21:04:58 +0000

"Again, not being familiar with C11, what does the memory model give that can help multithreaded programming, then? How does §5.1.2.4/4 work in the case where the machine access granularity is larger than some primitive types and a RMW must happen?"

Discarding volatile, which is irrelevant, it requires the faulty behavior observed in the kernel not to occur. On 64 bit architectures it can do this by various pessimizations. It could use slower 32 bit accesses where available. If that is not available it may have to pad so that any 32-bit scalar occupies 64 bits of space, where necessary to conform to the standard.

None of this is new. gcc's pthreads implementations have been doing this for years. It might be instructive to look at the assembly output of the same test cases compiled with the -pthread switch.

Betrayed by a bitfield

dlang — Mon, 06 Feb 2012 21:04:17 +0000

one of the posts I saw on this topic (I think from Linus) tested the code snippet

volitile int a;
int b;

b++;

and the resulting assembler did the exact same read-write on a that caused the problem with the case in question. If an interrupt were to happen between the read and the write that changed the value of a, the write would cause that value to be lost.

no, the item in question wasn't related to interrupts, but the cause of the problem causes the same problem if interrupts were involved.

If the 32 bit loads and stores were significantly more expensive to use than 64 bit loads and stores, there would be at least some reason to have this behaviour available, but in the case of the architectures in question there isn't a performance benefit to doing it this way.

Betrayed by a bitfield

chrisV — Mon, 06 Feb 2012 20:51:52 +0000

"the thing is, the current GCC behaviour _would_ overwrite the value of a volatile variable that was modified by an interrupt in the middle of the read-modify-write cycle of a different (but adjacent) variable."

I don't believe that has been tested and I don't believe it to be true. On hardware where 64 bit boundaries are important, sig_atomic_t would be likely to be 64-bits wide. (Someone with a ia64 architecture might be able to confirm this.) In that case alignment boundaries would be fully respected.

Also, I can't see that the original problem had anything to do with interrupts. It seems to be concerned with either multi-threading, or shared access by multiple processes.

Lastly, when you refer to "the bug with respect to volatile", you impute that gcc has the bug. If there is a bug, it is a bug in the kernel.

Betrayed by a bitfield

dlang — Mon, 06 Feb 2012 20:13:05 +0000

right, but the programmer is not attempting to do anything with it. The programmer is attempting to do something with another variable, one that just happens to be adjacent to the one in question.

again the code snippit is

volitile int a;
int b;

b++;

if modifying b causes a read/write of a, this is wrong.

the programmer has not made any attempt to specify alignment here.

Betrayed by a bitfield

dlang — Mon, 06 Feb 2012 20:06:07 +0000

the thing is, the current GCC behaviour _would_ overwrite the value of a volatile variable that was modified by an interrupt in the middle of the read-modify-write cycle of a different (but adjacent) variable.

As Linux says, it's possible for someone to fix the bug with respect to volatile, and explicitly leave the bug in for all other accesses (with the claim that the spec allows the compiler to do that), but it would probably be more work to do that then to just change the behaviour across the board.

Betrayed by a bitfield

daglwn — Mon, 06 Feb 2012 20:05:28 +0000

The key work is "cached." On any load/store machine the data must be first loaded into a register to do anything with it. volatile says it must be written back out by the next sequence point. I'm sure language lawyers will find some detail I've missed but that's the way I think about the guarantee.