| |||||||||||||
Betrayed by a bitfieldBetrayed by a bitfieldPosted Feb 4, 2012 14:20 UTC (Sat) by nix (subscriber, #2304)In reply to: Betrayed by a bitfield by dlang Parent article: Betrayed by a bitfield
it is violating the part of the spec that says that 'volitile' variables are assumed to be affected by external things and so the compiler cannot make assumptions that the variable has not changed just because it didn't issue any commands to change it.There is no such part (even if you spell it properly and look for 'volatile' :P ). The standard states (with wording identical in C99 and the just-released C11): An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously. What constitutes an access to an object that has volatile-qualified type is implementation- defined.This states how volatile accesses are to be carried out. It does not stipulate that such accesses may not have effects on other, non-volatile-qualified objects (such as adjacent bitfield fields): nor does it state that volatile-qualified objects cannot be modified incidentally by expressions that do not refer to them, nor that you cannot read from one and then store the same data back. All that is required is the usual rule that objects not described as having changed contents between sequence points should appear unchanged at the subsequent sequence point from the point of view of the C abstract machine. And that machine, up till C11, is a serial machine, taking no account of threading. There is no provision whatsoever for avoiding a read-write cycle of the same data from an object back into itself in case other threads might modify it, because in a single-threaded environment this is harmless so the freedom is better granted to implementors than denied. Thus it is not a violation of the (C99) Standard for accesses to a bitfield to unexpectedly issue write cycles to adjacent volatile bitfields for their current content as far as the serial abstract machine is concerned: indeed, on nearly all platforms this is unavoidable if the adjacent bitfields are located within the same byte. It would not be a violation of the Standard for an implementation to do a massive RMW cycle on all of memory every time a variable of any sort was accessed. These are both quality-of-implementation issues, not standards violations. In C11, this has been fixed: as footnote 13 of the new section s5.1.2.4 puts it Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard, since such an assignment might overwrite another assignment by a different thread in cases in which an abstract machine execution would not have encountered a data race. This includes implementations of data member assignment that overwrite adjacent members in separate memory locations. We also generally preclude reordering of atomic loads in cases in which the atomics in question may alias, since this may violate the "visible sequence" rules.However, compiler support for C11 isn't here yet, and the kernel is currently being compiled by a C99 compiler. So this is moot except inasmuch as it guides compiler implementors towards what will be expected in the future. And this fix appeared more than twenty years after the finalization of the first C standard to mention 'volatile'. For all that intervening time, the behaviour of GCC seen here was -- while unpleasant and probably a bug -- not a standards-violation.
(Log in to post comments)
Betrayed by a bitfield Posted Feb 4, 2012 17:56 UTC (Sat) by daglwn (subscriber, #65432) [Link]
> This includes implementations of data member assignment that overwrite
> adjacent members in separate memory locations.
That would seem to be the "out" that gets around the problem of the target machine not having an appropriately-sized load/store instruction to avoid false sharing.
I've not studied the C11 standard yet. Is that the intent of this statement? Otherwise C11 structs with volatile members could be ABI-incompatible with source-equivalent C99 structs due to forced alignment to avoid placing volatile members next to other members in a single load/store access unit.
In other words, what happens if I have a volatile char next to a non-volatile char and my target only has 32-bit loads and stores?
Betrayed by a bitfield Posted Feb 4, 2012 21:27 UTC (Sat) by nix (subscriber, #2304) [Link]
Er, that footnote says that those are *precluded*, not permitted (though of course as a footnote it is not normative).
I'm not sure how you can implement these requirements without either ABI changes or an efficiency reduction (on platforms where sub-maximum-sized writes are inefficient). We might have to eat the efficiency loss: we surely cannot fix this by aligning every member of every structure to cacheline boundaries or something like that, that's ridiculous.
(But I am a neophyte in this area. Someone, anyone, who knows more than me, please chip in!)
Betrayed by a bitfield Posted Feb 6, 2012 18:06 UTC (Mon) by daglwn (subscriber, #65432) [Link]
> Er, that footnote says that those are *precluded*, not permitted (though
> of course as a footnote it is not normative).
I think it's an "out" because the footnote only covers data in "separate memory locations." Two chars that don't cross an alignment boundary would be in the same "memory location" in some sense. They're in the same atomically-readable space.
But I don't know if that's the intent. If not, I think C11 has a serious issue. It will require ABI changes and that's not going to make people happy.
Betrayed by a bitfield Posted Feb 6, 2012 18:38 UTC (Mon) by chrisV (subscriber, #43417) [Link]
Yours cannot be the correct reading. The basic C11 requirement for multi-threaded programs is in §5.1.2.4/4: "Two expression evaluations conflict if one of them modifies a memory location and the other one reads or modifies the same memory location." In this normative provision, "memory location" cannot possibly mean anything other than the internal representation of a built-in type (char, int, or other integer, or a pointer), otherwise writing multi-threaded programs would be impossible. The POSIX standard for pthreads imposes a similar requirement on the implementation.
Note that marking a struct or a field of a struct volatile is irrelevant to all this. This (§5.1.2.4) is a part of the C specification relating to access to an object of a given built-in type by multiple threads within a single process. Volatile is concerned only with asynchronous access to a given memory location by a single thread in a single process (for example, by an interrupt). Of course, if volatile were to work at all in the usage in the kernel, some prior cache synchronization would be required so approximating to what is wanted here. But even so, the compiler is not obliged to provide the behavior demanded by the kernel code in question.
Betrayed by a bitfield Posted Feb 6, 2012 20:02 UTC (Mon) by daglwn (subscriber, #65432) [Link]
Thanks for explaining things.
> But even so, the compiler is not obliged to provide the behavior demanded
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?
Betrayed by a bitfield Posted Feb 6, 2012 21:04 UTC (Mon) by chrisV (subscriber, #43417) [Link]
"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 Posted Feb 6, 2012 21:11 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
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 Posted Feb 6, 2012 21:32 UTC (Mon) by chrisV (subscriber, #43417) [Link]
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 Posted Feb 6, 2012 21:39 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
Linus and several others in the kernel thread on the subject have said this.
Betrayed by a bitfield Posted Feb 7, 2012 0:43 UTC (Tue) by daglwn (subscriber, #65432) [Link]
> 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 Posted Feb 7, 2012 8:43 UTC (Tue) by khim (subscriber, #9252) [Link] 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 Posted Feb 7, 2012 18:35 UTC (Tue) by daglwn (subscriber, #65432) [Link]
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
But as we all know, C++ is not C. :) I don't see this as a problem.
Betrayed by a bitfield Posted Feb 7, 2012 20:53 UTC (Tue) by khim (subscriber, #9252) [Link] > Perfectly working C++ program can already be broken by recompilation in C++ is quite explicitly not C, but C++11 pretends that it's still C++.
Betrayed by a bitfield Posted Feb 7, 2012 23:29 UTC (Tue) by daglwn (subscriber, #65432) [Link]
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 Posted Feb 8, 2012 8:54 UTC (Wed) by khim (subscriber, #9252) [Link] 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 Posted Feb 6, 2012 18:40 UTC (Mon) by nix (subscriber, #2304) [Link] Not quite. s3.14's definition of 'memory location' iseither an object of scalar type, or a maximal sequence of adjacent bit-fields all having nonzero widthTherefore, even a 'long long' variable occupies a single 'memory location' by that defintion. However, a two-byte array of two chars occupies two memory locations. A location is not the same as an address.
Betrayed by a bitfield Posted Feb 4, 2012 21:47 UTC (Sat) by giraffedata (subscriber, #1954) [Link] That's very interesting, because it seems to say the provision for "volatile" is so incomplete as to be a pointless language feature. "volatile" was supposed to deal with C programs running in an address space that includes memory mapped I/O regions. But if the compiler is allowed to write whatever it wants whenever it wants into I/O regions, just as long as it doesn't expect it to stay there, what's the point? You can't confidently run a C program in an address space that contains memory mapped I/O regions.Maybe it's useful in read-only memory mapped I/O regions that just ignore writes.
Betrayed by a bitfield Posted Feb 4, 2012 22:25 UTC (Sat) by nix (subscriber, #2304) [Link] That's very interesting, because it seems to say the provision for "volatile" is so incomplete as to be a pointless language feature.I dunno. As long as compiler vendors cooperate, it's useful for its intended purpose, which was pretty much entirely *reading* from memory-mapped I/O regions and writing into them very carefully, in a serial environment. It wasn't particularly intended for parallel processing environments or multithreading, AIUI (though since I was only 13 when C89 was finalized, I obviously wasn't there and don't know for sure). In general you can't (and never could) rely on 'volatile' without knowing what the compiler would do when you asked it: implementations have had horrible bugs in their treatment of volatile often enough that care is warranted. But at the very least, it provides a way to flag that 'something tricky is happening here, look out'. It's proved more useful than 'register', low bar though that is. :)
Betrayed by a bitfield Posted Feb 4, 2012 22:37 UTC (Sat) by giraffedata (subscriber, #1954) [Link] Right, it's a useful feature of de facto C, but maybe not of standard C. This is just an academic discussion about the standard, since it seems everyone agrees GCC needs to change regardless of whether it presently implements the standard.As long as you know that storing to your memory mapped I/O regions is a no-op, you can use standard C with volatile to usefully fetch from them, but otherwise you need more than standard C. You need common sense C. It just seems strange to me because writable I/O regions did exist at the time this accomodation for reading them was added to the spec.
Betrayed by a bitfield Posted Feb 6, 2012 19:21 UTC (Mon) by chrisV (subscriber, #43417) [Link]
"This is just an academic discussion about the standard, since it seems everyone agrees GCC needs to change regardless of whether it presently implements the standard."
I absolutely don't agree with this. Forbidding 64-bit read/writes for 32-bit scalars within an aligned 64-bit boundary is a pessimization which should be opted into in C99, such as with the -pthread flag as in current gcc implementations (-pthread does require this pessimization if adjacent memory locations would otherwise be corrupted).
Presumably when C11 is implemented in gcc, opting out of this pessimization will also be available. Or possibly gcc will require some specific flag to be set where a multi-threaded program is being compiled, who knows.
Betrayed by a bitfield Posted Feb 6, 2012 18:08 UTC (Mon) by daglwn (subscriber, #65432) [Link]
> 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 (because the unerlying value might change unexpectedly), and little else. But the prohibition on register allocation is a pretty big deal to the compiler.
Betrayed by a bitfield Posted Feb 6, 2012 19:27 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
if it's not allowed to be cached in a register (because it could change unexpectedly), why are you allowed to do a read-write cycle on it? isn't that effectively the same thing?
Betrayed by a bitfield Posted Feb 6, 2012 20:01 UTC (Mon) by chrisV (subscriber, #43417) [Link]
I am not sure if it answers your question, but gcc would only be non-conforming if it carried out a corrupting read-write cycle on the memory location of a volatile variable as also read by an interrupt in the same thread attempting to read the same variable (or vice-versa), where the volatile variable is of type sig_atomic_t.
This is orthogonal to the original problem, which (as far as I can work out) is concerned with concurrent access by different threads.
Betrayed by a bitfield Posted Feb 6, 2012 20:06 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
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 Posted Feb 6, 2012 20:51 UTC (Mon) by chrisV (subscriber, #43417) [Link]
"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 Posted Feb 6, 2012 21:04 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
one of the posts I saw on this topic (I think from Linus) tested the code snippet
volitile int a;
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 Posted Feb 6, 2012 21:16 UTC (Mon) by chrisV (subscriber, #43417) [Link]
"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 Posted Feb 6, 2012 20:05 UTC (Mon) by daglwn (subscriber, #65432) [Link]
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.
Betrayed by a bitfield Posted Feb 6, 2012 20:13 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
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;
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 Posted Feb 7, 2012 0:48 UTC (Tue) by daglwn (subscriber, #65432) [Link]
> 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 Posted Feb 7, 2012 1:03 UTC (Tue) by dlang (✭ supporter ✭, #313) [Link]
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 Posted Feb 7, 2012 16:54 UTC (Tue) by chrisV (subscriber, #43417) [Link]
"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 Posted Feb 7, 2012 18:38 UTC (Tue) by daglwn (subscriber, #65432) [Link]
> "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 Posted Feb 7, 2012 19:07 UTC (Tue) by chrisV (subscriber, #43417) [Link]
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 Posted Feb 7, 2012 20:01 UTC (Tue) by dlang (✭ supporter ✭, #313) [Link]
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 Posted Feb 7, 2012 23:32 UTC (Tue) by daglwn (subscriber, #65432) [Link]
> 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 Posted Feb 8, 2012 15:24 UTC (Wed) by daglwn (subscriber, #65432) [Link]
Seeing some of your other posts about -pthread, I think we are in agreement. Apologies if I mischaracterized your understanding.
Betrayed by a bitfield Posted Feb 8, 2012 13:51 UTC (Wed) by nix (subscriber, #2304) [Link]
And, thirdly, the kernel is not C11 code -- yet.
Betrayed by a bitfield Posted Feb 6, 2012 22:22 UTC (Mon) by giraffedata (subscriber, #1954) [Link] 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 Posted Feb 7, 2012 0:52 UTC (Tue) by daglwn (subscriber, #65432) [Link]
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 Posted Feb 7, 2012 8:46 UTC (Tue) by khim (subscriber, #9252) [Link] 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...
|
|||||||||||||