14 ms·
The Problem with Friendly C
- userbinator 11y agoI think the most important point of Friendly C is not to define the behaviour for what would otherwise be undefined, but to define a behaviour; from this point of view, it would be unnecessary to argue over the examples he mentions like memcpy() vs memmove() and integer shifting --- it only suffices that every implementation define the behaviour, and what that behaviour precisely is can differ between them. A lot differs already between platforms, and so all this basically means is to document those differences. This agrees with the spirit of the language as a "high level assembler", removes all the undefinedness, and would be entirely unsurprising to most programmers. The situation gets worse when we start talking about a friendly semantics for races and OOB array accesses. I don't have anything to say about races, but OOB array accesses should simply do what you'd expect the hardware to do: attempt to access memory at the location the array indexing equation gives. It may segfault, or it may access some other contents in memory. That's what any C programmer would probably expect.
- caf 11y agoYou have to look deeper for the OOB array access question. For example, imagine I have code like this: if (a > 1) b++; array[b] = 0; c = a + 10; Under your suggested semantics, can the compiler use the value loaded from `a` at the point of the if() statement to calculate `a + 10`? Or does it have to emit a reload of `a` after the array access, in case `array[b]` was an OOB access that overwrote `a`?
- Dylan16807 11y agoHow about treating it just like another thread accessing the values? So yes in the general case, no if you put in memory barriers or atomics.
- caf 11y agoRace conditions are generally treated as "you get undefined behavior" for much the same reasons.
- Dylan16807 11y agoI mean race conditions on actual hardware, not the way the standard abandons all hope yet again. Stale reads don't require total chaos.
- userbinator 11y agoI'd say that it doesn't have to read 'a' again because these are separate variables and there's no requirement for 'a' and 'array' to be contiguous, or for that matter 'a' being in memory at all instead of just being in a register. An OOB access could overwrite the memory storing 'a', but I think this case of relying on the ordering and location of objects in memory is just not something any C code would ever have to do.
- lmm 11y agoYou're already allowing undefined behaviour then. Very confusing bugs could result - e.g. the value of 'a' might be different from what it looked like in a debugger, because the array access changed it in memory but the copy in the register hasn't changed.
- nkurz 11y agoI'm not seeing the deeper question, whereas what 'userbinator' said still makes sense to me. The compiler's implementation defined behavior would simply be "if you tell me to write a value to an address, I'll create assembly that tries to write that value to that address". That's all. If this address is outside the allocated range of the array, there is no guarantee that it's safe that write this value, or that it won't break something else. So in your example, no, the compiler is not required to reload 'a'. The compiler is allowed to presume that the array[x] syntax will have no affect on the value of a local variable, whether that variable is stored in a register or on the stack. The compiler is not guaranteeing safety, just best effort.
- caf 11y agoWhen you're saying that the compiler should be allowed to optimise under the assumption that OOB array accesses don't clobber other variables, this means that OOB array accesses can make very weird things happen indeed. For example: if (a > 1) b++; array[b] = 0; if (a > 1) foo(a); We might see foo() called with argument 0 when that's apparently impossible - the OOB write has apparently "reached forward" (it can also "reach backward"). This is why it ends up just being "undefined behaviour" - to do better either you have to somehow exhaustively document all the kinds of weird things that can happen ("it writes to the memory" isn't enough, because of the way that can interact with the optimiser) or you have to unreasonably constrain the optimiser.
- sirclueless 11y agoI don't have anything to say about races, but OOB array accesses should simply do what you'd expect the hardware to do: attempt to access memory at the location the array indexing equation gives. It may segfault, or it may access some other contents in memory. That's what any C programmer would probably expect. The problem is that defining OOB array access this way means throwing out pretty much every semantic guarantee from the rest of the language. There is really no friendly way to define writing an arbitrary value to an arbitrary location. By way of example, pretty much every (non-embedded) C implementation since 1972 supports recursion by writing an address of code to execute to memory. If you have semantics allowing a programmer to write to that location, then you can start executing literally any piece of code you want to. On some platforms like x86 you can execute starting in the middle of an instruction. For example, "return" would stop meaning "execution resumes at the callsite of this function" and instead mean "execution resumes at the callsite of this function or maybe somewhere else if someone wrote to arr[-5]". The article makes a big point about the controversy of giving memcpy() the semantics of memmove(); how would you like the semantics "memmove() unless a concurrent thread is running, in which case anything might be written to dest and src might be overwritten."
- to3m 11y agoIf ((uint32_t)x<<32)==x on one system, and ((uint32_t)x<<32)==0 on another, why is that a problem? The issue isn't that one system behaves differently from another. The issue is that compilers take it upon themselves to decide that because code would behave differently on these different systems - which is why the standard leaves it undefined - it can be considered to fall into some kind of black hole that allows the compiler to do whatever it likes. But why can't it just produce something different on each system? Allow me to call it as I see it: the modern interpretation of undefined behaviour is bullshit. What compilers do today should be the recourse of absolute last resort, and the sort of thing that makes its authors feel bad. But it seems to be treated as a matter of course. I don't know what to say. Mandatory reading: http://robertoconcerto.blogspot.co.uk/2010/10/strict-aliasing.html http://robertoconcerto.blogspot.co.uk/2010/10/strict-aliasin... ("Everyone is fired"); https://groups.google.com/forum/#!msg/boring-crypto/48qa1kWignU/o8GGp2K1DAAJ https://groups.google.com/forum/#!msg/boring-crypto/48qa1kWi... ("these people simply don't understand what most C programmers want"); http://blog.metaobject.com/2014/04/cc-osmartass.html http://blog.metaobject.com/2014/04/cc-osmartass.html ("please don't do this, you're not producing value")
- tormeh 11y agoThe, to me, obvious thing to do with code with undefined behaviour is to emit an error and refuse to compile it. Programmers should never rely on undefined behaviour. Then again, I think languages shouldn't have undefined behaviour and that programmers who use languages with undefined behaviour deserve what they get.
- caf 11y agoIn the most interesting cases, it can't reasonably be detected at compile-time anyway. See also here: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
- daurnimator 11y agoIt's usually only at runtime rather than compile time that such situations arise. At runtime we have the clang and gcc undefined behaviour sanitizers, but they aren't free in terms of performance.
- David 11y agoIt's easier to expand than contract. When the same decision is faced multiple times, it will be made multiple ways, and it's very difficult to remove one of those options once it's in use. On the other hand, if you remove the decision by standardizing on one of the options, you can always allow the other option later. Working in Perl, I run into this a lot. When 'there is more than one way to do it' is a driving principle, it's easy to be inconsistent in usage and design. There's a tradeoff here -- it's easier to write code, because you can pretty much write your solution however it pops into your head. However, it's harder to read and maintain, because you have to recognize many many different patterns of usage. When code has been around for awhile, it starts to get an eclectic mix of patterns blended together, which can be frustrating to run into when you're trying to fix that code. How do other people deal with this? Part of it is language choice, I'm sure. Large companies tend to use languages with less stylistic freedom, which helps teams write code more consistently. But within a given language, how do you balance freedom and consistency, so that people can understand each others' code effectively without being overly burdened by restrictions about how they can write code?
- tamana 11y agoWorking in say Java doesn't really force consistency, it just pushes the inconsistency up a level. Programmers still get painfully "clever" and idiosyncratic.
- cfv 11y agoHow exactly would performance degrade by defining a virtual machine for C programs to run in where assurances are given that all of the standard behavior is fully defined -this operation either fails, or gives THIS result-? It sounds like it could be massively useful, at least for non-realtime applications.
- 2trill2spill 11y agoCreating a C virtual machine might work for most user space applications, but what about operating systems and system libraries? Most operating systems and low level libraries are implemented in C, or at least partially, and implementing a C virtual machine that you then want to run kernel code on top of, seems daunting. Performance wise I would assume a C virtual machine would be on par with java (JVM). So I would say a C virtual machine wouldn't be a very fruitful endeavor, Most user space applications can be written in a Memory safe language, while the most incumbent C code, kernel and system libraries probably can't or at least shouldn't be executed in a virtual machine.
- im2w1l 11y agoLet's say you have a trapping division on the actual CPU you run on. And let's say the virtual machine specifies that division doesn't trap. Then the compiler has to insert checks for invalid inputs to prevent trapping from happening. Those checks may degrade performance.
- lmm 11y agopcwalton claims a factor of 3x to 5x elsewhere in the thread. Honestly I think the biggest problem here is social. Every programmer thinks they're smarter than others. If you give them a button marked "remove all safety checks, increase performance by 1%", they'll press it. Those who wouldn't press it have probably already moved on from C.
- analognoise 11y agoTarget a virtual architecture (LLVM IR). Run the original code in an emulator for the target system (QEMU); give warnings where the two differ, with a switch for the virtual architecture to mimic the behavior of whatever architecture you need. You get friendly C, a new way to think about warnings, and your old code can still be compatible with the new virtual architecture. Next up, world hunger.
- webkike 11y agoThis solution relies on some undecidable problems as being decidable
- analognoise 11y agoHow so? I don't see the connection to undeciability.
- webkike 11y agoIf you have undefined behaviour after an infinite loop that breaks on some condition, then that undefined behaviour will not necessarily have been triggered. Thus, no warning.
- tamana 11y agoRegehr himself "disproved" Fermat's Last Theorem by abusing a non-terminating loop and over-aggressive compilers. http://blog.regehr.org/archives/140 http://blog.regehr.org/archives/140
- webkike 11y agoYes, this I a great example of the consequences of undecidability. Was taught to me in my algorithms and proofs class
- def- 11y agoYou can't simply run code for all possible inputs.
- jerf 11y agoTone: I do not mean this as sarcasm or merely chasing fashion, I'm quite serious. As both theory and practice are showing, you're never going to be able to get the consensus you want out of C. There's no "saving" C... not because that's somehow mathematically impossible, but simply because the project is too staggeringly large for us to even wrap our heads around. It would literally be easier to get people to start using another language... ... so, why not do that then? We have, for perhaps the first time in 40 years, a candidate for a systems language that can truly replace C, that has truly different semantics (i.e., not C++, which is still profoundly C with a lot of stuff bodged on the side). I'd suggest trying to use Rust, and working with that team to nail down whatever remaining issues may yet be undefined in Rust that may cause trouble in the future. Whatever remaining practical problems there may be (and my impression is that that isn't really a long list), work on resolving them. Again, I am not being sarcastic or cynical; it is truly my estimate that it would be easier to get people behind that than to fix C at this point. Probably by a good two or more orders of magnitude. Obviously we're not going to rewrite all existing code. Obviously there's a lot of code still to be written that is so deeply embedded in C that there's no practical alternative to adding more C to it, even in a world of FFI support and such. But if the people who care about the idea of BoringC or Friendly C start getting behind Rust, getting their hands dirty with it, and doing what the Mozilla project is doing to find places where they can start slotting subsystems in cleanly to existing code bases, you may just be able to start creeping out of the mess we're in now. And... who knows. If this becomes acceptable, then generally considered a good idea, then best practice, then perhaps even something you need to do unless you want people to think poorly of you... perhaps real change will prove to be less intractable than we thought. People consistently overestimate change in the short term but underestimate in the long term. It is, perhaps, not too much to hope for that huge swathes of our fundamental systems could be running on Rust in 20 years, instead of C. So I'll reemphasize once again... yes, I know I'm proposing a staggeringly enormous change. The only thing that it has going for it is that I still think it's easier than the staggeringly-enormous-squared other choice. Something's gonna happen. After all... what's the alternative? That C is still the foundational language of the entire computing world in 2035? Seriously?
- steveklabnik 11y agoReghr came to a Bay Area Rust Meetup long ago, we're all generally fans of his work. :)
- guelo 11y agoThe Android team idea didn't make any sense to me.
- account921 11y agoI didn't get that either. They're shipping a totally broken locale.h and should be the last persons ever to get involved in C-language design.
- crawshaw 11y agoI applaud the author for reaching the daunting part of this project and reacting with humility appropriate to the difficulty. I hope they continue in this effort, because they sound like the right person for the job. There are going to be a lot of trade offs in any friendly C spec. Appreciation for both sides of a trade off is valuable in making good decisions.
- petke 11y agoI think this is a fundamental problem with C. Both of the language itself, but also of the C programming culture of insisting on very low levels of abstractions. Bugs and undefined behaviour is too easy for programmers to write when the level of abstraction is low. Too much boilerplate to get wrong. But too low a level is also bad for an optimizer. It cant assume it understand the programmers intention with the code. C++ tries to fix some of this by creating a higher level language and library on top of C. Low level code is considered unsafe, when higher level abstractions can be used as replacements. Some examples of replacing low level with high level. Raw (owning) pointers and manual memory management are replaced with RAII value semantics and occasionally smart pointers. Raw loops are replaced by container iteration and better yet by STL algorithms. Casts are replaced by templates. Threads and mutexes are replaced by tasks and async, etc. Eventually the idea is to subset C++ so that we can rip the C out of C++. https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md https://github.com/isocpp/CppCoreGuidelines/blob/master/CppC...
- nly 11y agoSince, according to Chandler Carruth, the aim for Clang is to not do optimizations based on undefined behaviour without a corresponding instrument in ubsan[0], I don't see much traction on this well-defined/boring C effort. You know, in my experience, things would be great if people actually turned on warnings. I write all my new code with -Weverything with a few noise categories turned off. Everybody should build code at this level from day 1. [0] http://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html http://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
- regehr 11y agoFor new code and for actively maintained old code you are perfectly correct. But there is a huge amount of C code we still rely on that isn't getting enough attention and I don't want that getting broken either.
- regehr 11y agoAlso we're all waiting for the strict aliasing checker.
- dietrichepp 11y agoAt work, we migrated a small codebase this year to VS2008. It was "painful". This week I put it through asan and found five buffer overflows or similar with about a half hour of work, but the thing still spits out a hundred warnings or so when you compile, and that's with default settings. This project is about 1% of the code, by line count, that my team is responsible for. At home, I turn on -Wall -Wextra for starters, enable about a dozen more for good measure, with -Werror as the pièce de réisistance.
- btrask 11y agoThe problem is UBSan is still kind of a pain to use. Just turn all of these optimizations directly into warnings and the problem would be solved--if you want to optimize them, the warnings will let you do it yourself.
- npsimons 11y ago> Everybody should build code at this level from day 1. On the project I run, the CI will reject your code in CR if it doesn't compile under two different compilers with all but a handful of warnings turned on as errors, runs and passes tests, and passes various linters, including a check for undocumented types, variables, parameters and return values. IMNSHO, every project should be like this. Once it's setup, it's a breeze and doesn't impede development speed at all.
- aplorbust 11y agoBeing an ignorant fool with an uninformed opinion, I would like to see a C compiler that is evaluated and critiqued not only based on the warnings and errors it generates but, more importantly, on the assembly it generates. Namely, how compact and readable is the generated asm? When we read the asm, can we easily follow what the compiler has done and _why_? As an ignorant fool, in my mind C is still a shorthand for writing assembly, to save old programmers from continuing to be or new programmers from becoming "assembly language programmers". Obviously many years have passed and "C" has become an institution and means much more to so many people. Aopologies to those people. I am just a fool. I see the _theoretical_ "C compiler" as nothing more than a code generator, spitting out assembly. Obviously the _practical_ C compiler is very different. Base on the way it's used, it seems inextricably linked with a "preprocessor" (glorified sed). It is said that asm has a "one to one" relationship with machine code. Theoretically, we can look at asm and determine its machine code equivalent without any "clever" algorithms. My humble, ignorant fool's opinion is that it would be better if C had a closer relationship to the asm the "C compiler" generates. Maybe not "one to one" but at least "predictable, boring". Forgive me for having opinions about overly complex things few people can comprehend (e.g., a "modern C compiler"). I am just an ignorant fool who likes code generators. Especially ones that output assembly.
- sanxiyn 11y agoI agree it would be an interesting exercise to write a compiler optimized for assembly readability. But I don't think there is enough demand for such a thing so that it will get written. It also would be interesting if those who think there is enough demand start a crowdfunding campaign to prove that there is enough demand.
- xamuel 11y agoYou have to choose whether or not you want the compiler to generate code that spends time doing things that the programmer didn't ask for. If you write a library with a function which accepts variables x and y and computes x[y] (or x<<y), there's no way for the compiler to know in advance whether the user will pass in well-behaved values for x and y. If you insist on the behavior being defined in pathological cases, then the compiler must add some kind of branching logic in there to check what's passed in at runtime. In other words, spend time doing things the programmer didn't ask for. Maybe when we make more progress with formal proof-generating languages, we can create a "friendly" C where the compiler refuses to compile the code until it's accompanied by formal proofs of UB-avoidance.
- Animats 11y ago"Maybe when we make more progress with formal proof-generating languages, we can create a "friendly" C where the compiler refuses to compile the code until it's accompanied by formal proofs of UB-avoidance." That's entirely feasible. I headed a team which did that for a dialect of Pascal over three decades ago.[1] It's since been done for Modula III, Java, Spec#, and Microsoft Windows drivers. One reasonable thing to do is to have the compiler generate run-time assertions for every statement which has a precondition for defined behavior. All pointer dereferences get "assert(p != 0)". The shift problem in the original article gets "assert(n > 0); assert(n <= 32);" Now everything has run-time checks. Then you try to optimize out the run-time checks, or at least hoist them out of loops. A simple prover can remove about 90% of the checks without much effort. [1] http://www.animats.com/papers/verifier/verifiermanual.pdf http://www.animats.com/papers/verifier/verifiermanual.pdf
- praptak 11y agoFun fact about large shifts being undefined. With a 32 bit x, the expression x << b | x >> (32 - b) can be translated to a single "roll x b bits to the left" instruction. But it is only possible if >32 shifts are treated as undefined.
- pbsd 11y agoNot true. In fact, modern x86 backends recognize the safe rotation idiom and also translate it to a single ROL instruction: http://goo.gl/NCMEVu http://goo.gl/NCMEVu http://goo.gl/9Ytsz2 http://goo.gl/9Ytsz2 http://goo.gl/vbzHNW http://goo.gl/vbzHNW
- ryandrake 11y agoI must be missing something here, but can't you simply not invoke undefined behavior in your program? That way, you don't have to worry about what your compiler will do when it encounters undefined behavior.
- marcosdumay 11y agoThat's possible. It requires extreme care (assuring no memeory leaks is comparably a walk in the park), and will make your code much less performant. But it's possible.
- jokoon 11y agoI wonder what Ritchie would be thinking of that. Also, if friendly C is a problem, does that mean that friendly C++ is in the realm of the impossible?