39 ms·

ISO C became unusable for operating systems development

203 points by pcw888 5y ago

zokier 5y ago
ISO C is mostly concerned about making sure that stuff is portable; operating systems on the other hand are intrinsically platform-specific to a degree. So it is not really surprising that pure ISO C is not enough for OS development
- yjftsjthsd-h 5y ago
  You can still be portable between compilers; Linux builds with GCC and Clang, and used to build with tcc (although that probably required patches)
  - zokier 5y ago
    Linux builds on clang after a decade of dedicated effort to make it happen, and that is with clang overall being comparatively similar to gcc (e.g clang implements many gcc extensions): https://github.com/ClangBuiltLinux/linux/wiki/Project-history https://github.com/ClangBuiltLinux/linux/wiki/Project-histor...
deleted 5y ago
[deleted]
throwawayvibes 5y ago
foxfluff 5y ago
This was discussed somewhat recently: https://news.ycombinator.com/item?id=28779036 https://news.ycombinator.com/item?id=28779036
h2odragon 5y ago
Torvalds was a strong advocate of GCC 2.95 (iirc), early on in Linux history, because he knew the kind of code it would emit and didn't trust the newer compilers to produce code that was correct in those circumstances. The workarounds and effort required to tell a compiler today that no, you really did want to do the thing you said might well be insupportable. I figure they started going astray about the time self modifying code became frowned upon.
- mananaysiempre 5y ago
  To be fair, the backend in the early GCC 3.x series was just kind of stupid sometimes. Even now I find strange if cheap and harmless heisengremlins in GCC-produced x86 code (like MOV R, S; MOV S, R; MOV R, S) from time to time, while the Clang output, even if not always good, is at least reasonable. This is not to diss the GCC team—the effort required to port a whole compiler to a completely new IR with a completely different organizing principle while keeping it working most of that time boggles the mind, frankly. But the result does occasionally behave in weird ways.
  - usbqk 5y ago
    Can Linux compile under clang nowadays?
    - eminence32 5y ago
      Yes, see: https://www.kernel.org/doc/html/latest/kbuild/llvm.html https://www.kernel.org/doc/html/latest/kbuild/llvm.html
    - yjftsjthsd-h 5y ago
      While sibling comment is correct that the simple answer is "yes", I'd like to add that Google uses Clang as the preferred compiler for Android. There's a little bit of drift between Android's version of Linux and mainline, but the effect is still that building Linux with Cland is being extensively used and tested.
    - pjmlp 5y ago
      Yes, when that Linux variant is called Android. Since almost 5 years by now.
      - deleted 5y ago
        [deleted]
aw1621107 5y ago
Ralf Jung has a blog post looking at some of the claims in this paper [0]. Some hopefully representative quotes: > The paper makes many good points, but I think the author is throwing out the baby with the bathwater by concluding that we should entirely get rid of this kind of Undefined Behavior. The point of this blog post is to argue that we do need UB by showing that even some of the most basic optimizations that all compilers perform require this far-reaching notion of Undefined Behavior. <snip> > I honestly think trying to write a highly optimizing compiler based on a different interpretation of UB would be a worthwhile experiment. We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. > To conclude, I fully agree with Yodaiken that C has a problem, and that reliably writing C has become incredibly hard since undefined behavior is so difficult to avoid. It is certainly worth reducing the amount of things that can cause UB in C, and developing practical tools to detect more advanced kinds of UB such as strict aliasing violations. <snip> > However, I do not think this problem can be solved with a platform-specific interpretation of UB. That would declare all but the most basic C compilers as non-compliant. We need to find some middle ground that actually permits compilers to meaningfully optimize the code, while also enabling programmers to actually write standards-compliant programs. [0]: https://www.ralfj.de/blog/2021/11/24/ub-necessary.html https://www.ralfj.de/blog/2021/11/24/ub-necessary.html
- gavinhoward 5y ago
  >> We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. There actually is data, [1] and it goes against intuition because it shows that UB makes code slower. It turns out that when programmers are faced with the possibility of UB, they (quite rightly) try to work around it. (In my case, I implemented signed two's-complement arithmetic entirely with unsigned types. I also implemented my own array types, including bounds checks when indexing the arrays.) These workarounds make their code slower, in general. When you think about it that way, it makes sense because programmers almost never want UB in their software, so on average, the software that people care about will work around UB and become slower. UB in C was defensible when platforms were not homogenous and when compiler writers did not abuse the spirit of it. But nowadays, most of it is indefensible because platforms are mostly homogenous, and compiler writers have been abusing UB for "performance." We saw the same thing happen with speculative execution in chips. For years, chip manufacturers got away with lots of tricks to increase performance. Then Spectre and Meltdown were discovered. As a result, a lot of software had to be changed, which resulted in the software slowing down. (Yes, there are now mitigations in chips, but I think those mitigations will be successfully attacked too. I think that it will continue that way until most or all speculative execution is removed.) Likewise, with compilers exploiting UB against the original spirit of UB, which was just to make C easy to port to any architecture, we are probably going to have a reckoning about it in the same way we did Spectre and Meltdown. In a way, we already do, but it's spread out like a thousand paper cuts. Maybe that means that it will stay invisible enough that programmers never wake up; I hope not. tl;dr: compilers exploiting UB actually slows down good code in much the same way that Spectre and Meltdown do. [1]: https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_20...
foxfluff 5y ago
I haven't got the time to read the paper yet but I believe I'd emerge with the more or less the same opinion that I've had before: nobody's forcing you to pass -O2 or -O3. It's stupid to ask the compiler to optimize and then whine that it optimizes. I usually am OK with the compiler optimizing, hence I ask it to do so. I'm glad that others who disagree can selectively enable or disable only the optimizations they're concerned about. Most of the optimizations that people whine about seem quite sane to me. Of course, sometimes you find real bugs in the optimizer (yesterday someone on libera/#c posted a snippet where gcc with -O2 (-fdelete-null-pointer-checks) removes completely legit checks)
- phicoh 5y ago
  It seems to me a flaw in a language and in a compiler if the average programmer has to avoid higher levels of optimizating because it cannot be predicted what they do.
  - Wowfunhappy 5y ago
    What if the only languages/compilers without that "flaw" had similar performance to lower optimization levels? (I don't know if that's the case, but it's what I thought the GP was implying.)
    - phicoh 5y ago
      There is a saying that you can make any program run fast if you don't care about correctness. We have reached the point where C programmers cannot understand the language/compiler anymore. Given that this has been going on for a long time, my hope is that Rust will be the next systems programming language.
      - foxfluff 5y ago
        Do you think people understand Rust?
        5y ago
maxlybbert 5y ago
It may be unusable for “modern” operating systems (you could write an early UNIX clone with just ISO C because early UNIX didn’t support much). But that’s basically always been the case. I doubt you could stay within the first ISO C standard and write a modern operating system.
- phicoh 5y ago
  Assuming that an early Unix clone would be written in C plus some amount of assembler. Then what constructs of modern Unix systems make it impossible to in write in the first ISO C standard plus some assembler? For example, 4.4BSD, early Solaris have just about everything you would expect in a modern operating system. And give the age of those systems, they were written in early versions of the C standard.
  - immibis 5y ago
    This is true for any language. An operating system can be written in Java plus some amount of assembler.
  - ErikCorry 5y ago
    Before 1985 there was no C standard, and until 1989 it was only a draft. So I doubt anything was written in standard C in the 1970s or early 1980s.
    - phicoh 5y ago
      C89 is mostly a superset of K&R C. So if you can write an OS in K&R you can write it is C89. The issue was, do modern operating systems require newer versions of the C standard? Or can you write everything in C89.
      - pjmlp 5y ago
        Inline assembly is not part of C89, so a pure C89 compiler needs to rely on an external Assembler for systems programming for example. Same applies to using C in hardware that lacked memory mapped IO.
phicoh 5y ago
One thing that is not mentioned in the article, is that next to undefined behavior, there is also implementation defined behavior. For example, if signed integer overflow would be implementation defined behavior, then any weirdness would be limited to just the integer operation that overflows. Lots of other stuff can be expressed as implementation defined behavior. That would probably kill some optimizations. So the question is more, do we want a portable assembler? In that case as many C constructs as possible need have defined behavior. Either defined by the standard or as part of the compiler documentation. Another possibily is to have standards for C on x86, amd64, arm, etc. Then we can strictly define signed integer overflow, etc. And say that on x86, pointers don't have alignment, so a pointer that points to storage of suitable size can be used to stored an object of different type, etc. If the goal is to run SPEC as fast as possible, then making sure every program trigger undefined behavior is the way to go.
- ErikCorry 5y ago
  In theory the difference between undefined behaviour and implementation defined behaviour is that ID behaviour must be documented. In practice good luck finding that documentation for each CPU and compiler combination. In fact good luck just finding it for LLVM and x64.
  - josephcsible 5y ago
    No, that's the difference between unspecified and implementation defined behavior.
    - ErikCorry 5y ago
      If you want to be pedantic about it then I guess Clang and GCC don't implement the standards since they treat implementation defined as unspecified.
    - astrobe_ 5y ago
      This unspecifed behavior is perhaps a bit lesser-known than UB, here is a (hopefully non-null ;-) pointer: https://stackoverflow.com/questions/18420753/unspecified-undefined-and-implementation-defined-behavior-wiki-for-c https://stackoverflow.com/questions/18420753/unspecified-und...
ErikCorry 5y ago
Similarly, standard C++ is not usable to implement virtual machines like Hotspot, and yet all virtual machines are implemented using C++ compilers.
- pjmlp 5y ago
  Not all, https://www.jikesrvm.org https://www.jikesrvm.org. Just one example, I can't be bothered to post others.
kortex 5y ago
Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. Seems like you'd have to allow only structures which hide memory implementation details if you truly want to avoid all UB. Same goes for any arithmetic which could overflow. That would require kernel devs to radically rethink how they interact with I/O, which would probably require specific architectures. In other words, writing a kernel portable on any of the existing ISAs that is also performant is basically impossible, barring some humongous breakthrough in compiler technology. Seems to me that when it comes to brass tacks, UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined and thus usually does what you want, but can result in bugs.
- immibis 5y ago
  Even kernels only interact with memory in reasonably predictable ways. I think they could all be hidden behind such abstractions, BUT it will make the language a lot more complex.
- CRConrad 5y ago
  > Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. With untyped pointers, yes. But it seems to me that if you have strong typing for function pointers you could mostly avoid that. > UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined Well, no, of course it isn't -- the clue is probably in the first half of the name, "Undefined Behaviour"... ;-)
- ErikCorry 5y ago
  Without concurrency you don't have to have UB to have user-defined pointers. x86 assembly language has no UB and has user-defined pointers.
RcouF1uZ4gsC 5y ago
I think the undefined behavior in C and C++ are even less defensible today than when they started because of the convergence of architectures. Pretty much every non-legacy architecture does IEEE floating point. Pretty much all of them do a flat address space. The word size is some power of 2(32 bit, 64 bit, maybe 128 bit in the future). They are almost always little endian. The memory models are converging towards the C++ memory model. Given that, I think simplifying the language and getting rid of foot guns could be done without losing any significant performance or actual flexibility/portability.
- pjmorris 5y ago
  It could be called 'C--' unless that's been taken.
  - RcouF1uZ4gsC 5y ago
    There is a language C-- created by Microsoft Research (Simon Peyton Jones of Haskel and GHC fame) https://www.microsoft.com/en-us/research/wp-content/uploads/1998/01/pal-manual.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- jandrese 5y ago
  You could also add that they all do 2s complement math. This is what the OpenBSD team did to OpenSSL. If the code has some complexity that is only necessary because it might have been run on a VAX or AIX or early Cray architecture then it is time to excise that complexity. They deleted thousands and thousands of lines of support for architectures that are only seen in museums and landfills today.
  - astrange 5y ago
    C does require 2's complement math. However architectures of the future aren't going to have flat pointers (PAC/CHERI etc), and even current architectures have some non-IEEE floats (https://en.wikipedia.org/wiki/Bfloat16_floating-point_format https://en.wikipedia.org/wiki/Bfloat16_floating-point_format / https://en.wikipedia.org/wiki/Unum_(number_format) https://en.wikipedia.org/wiki/Unum_(number_format)).
abfan1127 5y ago
what's the history of having undefined behavior? why would a language designer not specify?
- gpderetta 5y ago
  Sanitizers attempt to do define the behaviour of undefined constructs, but expect an integer multiple slowdown compared even with unoptimized builds. It is very hard to specify the behaviour of, for example, use-after-free, or accessing an automatic variable after it goes out of scope, or data races, in a C-like language without significant runtime cost.
- rocqua 5y ago
  Because the code should be somewhat portable, and not all processors act the same. This is why left and right shift are weird with overflow. Not consistent between x86 and some other instruction set. Similar for accessing the null address. Besides that, how would you specify the behavior of reading from an address the user randomly generated himself? What is stored at an address not generated by the compiler is out of scope for the compiler. If you try to define something like 'always trap' or 'always return 0', you incur massive overhead. Besides that. The fact that signed integer over/underflow is undefined behavior actually unlocks a lot of reasonable optimizations that treat integers like actual integers. Things like (a+1 > a) always being true.
  - deleted 5y ago
    [deleted]
speedcoder 5y ago
Can you still compile gcc code with -O0 (gcc option to turn optimization off) to get completely defined behavior? When doing so does it actually still turn off all optimizations? Also does -Os (optimization for size) still produce defined behavior?
- foxfluff 5y ago
  > Can you still compile gcc code with -O0 (gcc option to turn optimization off) to get completely defined behavior? No. The standard specifies what's undefined, optimization levels don't change it (though there are compiler flags such as -fwrapv which make undefined things defined). However, turning off optimizations will make behavior easier to predict.
  - lanstin 5y ago
    it used to be passed around never to use -O0 because it was much less used/tested and would generate wrong code more often. Not sure id that was folklore or true.
    - saagarjha 5y ago
      -O0 is "well tested" because everyone uses it for debug builds. If it produced incorrect results people would be fairly upset (and they are when it does…but it's not particularly common, because incorrect optimizations are generally the problem when codegen is incorrect.)
jcranmer 5y ago
I think undefined behavior (as a general concept) gets an unfair share of the blame here. It's notable that almost all criticism of undefined behavior in C tends to focus on just two sources of UB: signed integer overflow and strict aliasing; other sources of UB just don't generate anywhere near the same vitriol [1]. Furthermore, it's notable that people don't complain about UB in Rust... which arguably has a worse issue with UB in that a) there's not even a proper documentation of what is UB in Rust, and b) the requirement that &mut x be the sole reference to x (and therefore is UB if it is not) is far more stringent than anything in C (bar maybe restrict), and I'm sure that most Rust programmers, especially newbies starting out with unsafe, don't realize that that's actually a requirement. There is a necessity for some form of UB in a C-like language, and that has to deal with pointer provenance. You see, in C, everything lives in memory, but on real hardware, you want as much to live in a register as possible. So a compiler needs to be able to have reasonable guarantees that, say, any value whose address is never taken can never be accessed with a pointer, and so can be promoted to a register. As a corollary, this requires that things like out-of-bound memory accesses, or worse, converting integers to pointers (implicating pointer provenance here) need to have UB in at least some cases, since these could in principle "accidentally" compute an address which is the same as a memory location whose address was never taken. That suggests that the problem isn't UB per se. If we look at the two canonical examples, arithmetic overflow and strict aliasing, we can see that one of the features of these things is that they have a pretty obvious well-defined semantics [2] that can be given for them, and furthermore, there's no way to access these well-defined semantics even avoiding this feature altogether. And I think it's the lack of this ability to work around UB that is the real issue with C, not UB itself. [1] For example, it is UB to pass in rand as the comparison function to qsort. I'm sure many people will not realize that before I wrote this, and even parsing the C specification to find out that this is UB is not trivial. For an interesting challenge, try giving a definition of what the behavior should be were it not UB--and no, you can't just say it's impl-defined, since that still requires you to document what the behavior is. [2] I will point out that, for arithmetic overflow, this semantics is usually wrong. There are very few times where you want <large positive number> + <large positive number> = <negative number>, and so you're mostly just swapping out an unpredictably wrong program for a predictably wrong program, which isn't really any better. However, the most common time you do want the wrapping semantics is when you want to check if the overflow happened, and this is where C's lack of any overflow-checked arithmetic option is really, really painful.
nn3 5y ago
Clickbait on arxiv? Et tu, Brute? No, most operating systems that people are actually use are written in ISO C, so the headline is by definition wrong.
- immibis 5y ago
  They are written in non-ISO C
qualudeheart 5y ago
So we can switch to rust now?
- yjftsjthsd-h 5y ago
  Sure; we look forward to your patches (keep in mind that they must preserve compatibility and portability to all currently supported architectures).
  - flykespice 5y ago
    Forgot the main flavor, it must be performing, which is the reason UB were "created" in the ISO C in the first place.
  - qualudeheart 5y ago
    I think my girlfriend can figure something out. She does embedded systems at Anduril using Rust.
mcguire 5y ago
From the paper: "For example, a well-known security issue in the Linux kernel was produced by a compiler incorrectly assuming a pointer null check was unnecessary ([40] fig. 6) and deleting it as an optimization. Or consider this (simplified) patch report for Linux [25]: The test [for termination] in this loop: [...] was getting completely compiled out by my gcc, 7.0.0 20160520. The result was that the loop was going beyond the end of the [...] array and giving me a page fault [...] I strongly suspect it’s because __start_fw and __end_fw are both declared as (separate) arrays, and so gcc concludes that __start_fw can never point to __end_fw. By changing these variables from arrays to pointers, gcc can no longer assume that these are separate arrays." Both of those sound like simple bugs in the compiler optimizer implementation, in which case they could hardly be use as examples of how the current C standard was bad.
- foxfluff 5y ago
  No, they're definitely features. The removal of null pointer checks in gcc is enabled by -fdelete-null-pointer-checks and is often enabled by default.
- TazeTSchnitzel 5y ago
  They aren't bugs. The C standard considers those cases to be undefined.
WalterBright 5y ago
D got around the overflow-is-UB problem by declaring that 2s-complement arithmetic will be used with wraparound semantics. Is there any reason for modern C to still support anything else?
- mhh__ 5y ago
  There are still processors that don't use two's complement, although I'm not sure that should really stop them if they wanted to declare all C implementations must be t-c.
  - WalterBright 5y ago
    Those processors can use a dialect of C that embraces ones-complement. Mandating such support in the Standard has little practical effect on code, I expect most programs would have to be recoded to work on ones-complement anyway.
- zajio1am 5y ago
  Integer overflow is usually logic error, so a reasonable default behavior would be a trap instead of silent overflow (regardless of how signed integrers are stored in memory). Some architectures support that (e.g. MIPS).
  - WalterBright 5y ago
    The article mentions cases where integer overflow is expected behavior.
    - zajio1am 5y ago
      C already offers 'unsigned' type variants that offers defined overflow (together with non-negative range). It would be useful to have another type variant that offers defined overflow (like in unsigned) together with signed range for such cases. But it still makes sense for basic integers to have overflow as UD, as in most cases it is not expected behavior. Note that in current C, if one needs defined overflow on signed integers, one can cast them to unsigned, to the operation and cast result back to int. That makes it implementation-defined instead of undefined.
flykespice 5y ago
Wow, this was an eye-opening read on my trust with ISO C. It makes much more understandable why linux codebase is riddled with compiler extensions, ISO C is simply not reliable anymore. The issue is bigger than what trembles on the surface, just like Dennis Ritchie said, it is a timebomb, soon enough these nuances will burst into a big issue in linux kernel, or worse yet, some essential system like avionics.
RustyRussell 5y ago
I still retch when told memcpy and memset cannot take NULL and 0 length. Try asserting that they're not NULL in glibc and try to boot your machine! Oops... bad compiler people, bad!
WalterBright 5y ago
I had an online discussion some years back where I suggested that C nail the size of char to 8 bits. He responded that there was a CPU that had chars be 32 bits, and wasn't that great that a C compiler for it would be Standard compliant? I replied by pointing out that nearly every non-trivial C program would have to be recoded to work on that architecture. So what purpose did the Standard allowing that actually achieve? I also see no problem for a vendor of a C compiler for that architecture making a reasonable dialect of C for it. After all, to accommodate the memory architecture of the x86, nearly all C compilers in the 80's adopted near/far pointers, and while not Standard compliant, it really didn't matter, and was tremendously successful. D made some decisions early on that worked out very well: 1. 2's complement wraparound arithmetic 2. sizes of basic integer types are fixed at 1 byte for chars, 2 for shorts, 4 for integers, 8 for longs. This worked out very well 3. floating point is IEEE 4. char's are UTF-8 code units (*) 5. chars are unsigned These 5 points make for tremendous simplicity gains for D programmers, and ironically increase portability of D code. After reading the paper, I'm inclined to change the definition of UB in D to not mean it can be assumed to not happen and not be unintended. (*) thanks for the correction
- WalterBright 5y ago
  I had another such discussion where I suggested that C abandon support for EBCDIC. I was told it was great that C supported any character set! I said C certainly does not, and gave RADIX50 as an example. How many C programs today would work with EBCDIC? Zero? There's no modern point in C not requiring ASCII, at a minimum.
  - sedatk 5y ago
    > I was told it was great that C supported any character set I'm all for extensibility mechanisms to shut down the people like this. You want EBCDIC? It's now a github repository; go ahead and maintain it, or shut up.
  - slavik81 5y ago
    What is it about RADIX50 that makes it incompatible with the C standard? The lack of a reserved null value?

203 points by pcw888 5y ago

ISO C is mostly concerned about making sure that stuff is portable; operating systems on the other hand are intrinsically platform-specific to a degree. So it is not really surprising that pure ISO C is not enough for OS development

yjftsjthsd-h 5y ago
You can still be portable between compilers; Linux builds with GCC and Clang, and used to build with tcc (although that probably required patches)
- zokier 5y ago
  Linux builds on clang after a decade of dedicated effort to make it happen, and that is with clang overall being comparatively similar to gcc (e.g clang implements many gcc extensions): https://github.com/ClangBuiltLinux/linux/wiki/Project-history https://github.com/ClangBuiltLinux/linux/wiki/Project-histor...

deleted 5y ago

[deleted]

throwawayvibes 5y ago

foxfluff 5y ago

This was discussed somewhat recently: https://news.ycombinator.com/item?id=28779036 https://news.ycombinator.com/item?id=28779036

h2odragon 5y ago

Torvalds was a strong advocate of GCC 2.95 (iirc), early on in Linux history, because he knew the kind of code it would emit and didn't trust the newer compilers to produce code that was correct in those circumstances. The workarounds and effort required to tell a compiler today that no, you really did want to do the thing you said might well be insupportable. I figure they started going astray about the time self modifying code became frowned upon.

mananaysiempre 5y ago
To be fair, the backend in the early GCC 3.x series was just kind of stupid sometimes. Even now I find strange if cheap and harmless heisengremlins in GCC-produced x86 code (like MOV R, S; MOV S, R; MOV R, S) from time to time, while the Clang output, even if not always good, is at least reasonable. This is not to diss the GCC team—the effort required to port a whole compiler to a completely new IR with a completely different organizing principle while keeping it working most of that time boggles the mind, frankly. But the result does occasionally behave in weird ways.
- usbqk 5y ago
  Can Linux compile under clang nowadays?
  - eminence32 5y ago
    Yes, see: https://www.kernel.org/doc/html/latest/kbuild/llvm.html https://www.kernel.org/doc/html/latest/kbuild/llvm.html
  - yjftsjthsd-h 5y ago
    While sibling comment is correct that the simple answer is "yes", I'd like to add that Google uses Clang as the preferred compiler for Android. There's a little bit of drift between Android's version of Linux and mainline, but the effect is still that building Linux with Cland is being extensively used and tested.
  - pjmlp 5y ago
    Yes, when that Linux variant is called Android. Since almost 5 years by now.
    - deleted 5y ago
      [deleted]

aw1621107 5y ago

Ralf Jung has a blog post looking at some of the claims in this paper [0]. Some hopefully representative quotes: > The paper makes many good points, but I think the author is throwing out the baby with the bathwater by concluding that we should entirely get rid of this kind of Undefined Behavior. The point of this blog post is to argue that we do need UB by showing that even some of the most basic optimizations that all compilers perform require this far-reaching notion of Undefined Behavior. <snip> > I honestly think trying to write a highly optimizing compiler based on a different interpretation of UB would be a worthwhile experiment. We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. > To conclude, I fully agree with Yodaiken that C has a problem, and that reliably writing C has become incredibly hard since undefined behavior is so difficult to avoid. It is certainly worth reducing the amount of things that can cause UB in C, and developing practical tools to detect more advanced kinds of UB such as strict aliasing violations. <snip> > However, I do not think this problem can be solved with a platform-specific interpretation of UB. That would declare all but the most basic C compilers as non-compliant. We need to find some middle ground that actually permits compilers to meaningfully optimize the code, while also enabling programmers to actually write standards-compliant programs. [0]: https://www.ralfj.de/blog/2021/11/24/ub-necessary.html https://www.ralfj.de/blog/2021/11/24/ub-necessary.html

gavinhoward 5y ago
>> We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. There actually is data, [1] and it goes against intuition because it shows that UB makes code slower. It turns out that when programmers are faced with the possibility of UB, they (quite rightly) try to work around it. (In my case, I implemented signed two's-complement arithmetic entirely with unsigned types. I also implemented my own array types, including bounds checks when indexing the arrays.) These workarounds make their code slower, in general. When you think about it that way, it makes sense because programmers almost never want UB in their software, so on average, the software that people care about will work around UB and become slower. UB in C was defensible when platforms were not homogenous and when compiler writers did not abuse the spirit of it. But nowadays, most of it is indefensible because platforms are mostly homogenous, and compiler writers have been abusing UB for "performance." We saw the same thing happen with speculative execution in chips. For years, chip manufacturers got away with lots of tricks to increase performance. Then Spectre and Meltdown were discovered. As a result, a lot of software had to be changed, which resulted in the software slowing down. (Yes, there are now mitigations in chips, but I think those mitigations will be successfully attacked too. I think that it will continue that way until most or all speculative execution is removed.) Likewise, with compilers exploiting UB against the original spirit of UB, which was just to make C easy to port to any architecture, we are probably going to have a reckoning about it in the same way we did Spectre and Meltdown. In a way, we already do, but it's spread out like a thousand paper cuts. Maybe that means that it will stay invisible enough that programmers never wake up; I hope not. tl;dr: compilers exploiting UB actually slows down good code in much the same way that Spectre and Meltdown do. [1]: https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_20...

foxfluff 5y ago

I haven't got the time to read the paper yet but I believe I'd emerge with the more or less the same opinion that I've had before: nobody's forcing you to pass -O2 or -O3. It's stupid to ask the compiler to optimize and then whine that it optimizes. I usually am OK with the compiler optimizing, hence I ask it to do so. I'm glad that others who disagree can selectively enable or disable only the optimizations they're concerned about. Most of the optimizations that people whine about seem quite sane to me. Of course, sometimes you find real bugs in the optimizer (yesterday someone on libera/#c posted a snippet where gcc with -O2 (-fdelete-null-pointer-checks) removes completely legit checks)

phicoh 5y ago
It seems to me a flaw in a language and in a compiler if the average programmer has to avoid higher levels of optimizating because it cannot be predicted what they do.
- Wowfunhappy 5y ago
  What if the only languages/compilers without that "flaw" had similar performance to lower optimization levels? (I don't know if that's the case, but it's what I thought the GP was implying.)
  - phicoh 5y ago
    There is a saying that you can make any program run fast if you don't care about correctness. We have reached the point where C programmers cannot understand the language/compiler anymore. Given that this has been going on for a long time, my hope is that Rust will be the next systems programming language.
    - foxfluff 5y ago
      Do you think people understand Rust?
      - 5y ago

maxlybbert 5y ago

It may be unusable for “modern” operating systems (you could write an early UNIX clone with just ISO C because early UNIX didn’t support much). But that’s basically always been the case. I doubt you could stay within the first ISO C standard and write a modern operating system.

phicoh 5y ago
Assuming that an early Unix clone would be written in C plus some amount of assembler. Then what constructs of modern Unix systems make it impossible to in write in the first ISO C standard plus some assembler? For example, 4.4BSD, early Solaris have just about everything you would expect in a modern operating system. And give the age of those systems, they were written in early versions of the C standard.
- immibis 5y ago
  This is true for any language. An operating system can be written in Java plus some amount of assembler.
- ErikCorry 5y ago
  Before 1985 there was no C standard, and until 1989 it was only a draft. So I doubt anything was written in standard C in the 1970s or early 1980s.
  - phicoh 5y ago
    C89 is mostly a superset of K&R C. So if you can write an OS in K&R you can write it is C89. The issue was, do modern operating systems require newer versions of the C standard? Or can you write everything in C89.
    - pjmlp 5y ago
      Inline assembly is not part of C89, so a pure C89 compiler needs to rely on an external Assembler for systems programming for example. Same applies to using C in hardware that lacked memory mapped IO.

phicoh 5y ago

One thing that is not mentioned in the article, is that next to undefined behavior, there is also implementation defined behavior. For example, if signed integer overflow would be implementation defined behavior, then any weirdness would be limited to just the integer operation that overflows. Lots of other stuff can be expressed as implementation defined behavior. That would probably kill some optimizations. So the question is more, do we want a portable assembler? In that case as many C constructs as possible need have defined behavior. Either defined by the standard or as part of the compiler documentation. Another possibily is to have standards for C on x86, amd64, arm, etc. Then we can strictly define signed integer overflow, etc. And say that on x86, pointers don't have alignment, so a pointer that points to storage of suitable size can be used to stored an object of different type, etc. If the goal is to run SPEC as fast as possible, then making sure every program trigger undefined behavior is the way to go.

ErikCorry 5y ago
In theory the difference between undefined behaviour and implementation defined behaviour is that ID behaviour must be documented. In practice good luck finding that documentation for each CPU and compiler combination. In fact good luck just finding it for LLVM and x64.
- josephcsible 5y ago
  No, that's the difference between unspecified and implementation defined behavior.
  - ErikCorry 5y ago
    If you want to be pedantic about it then I guess Clang and GCC don't implement the standards since they treat implementation defined as unspecified.
  - astrobe_ 5y ago
    This unspecifed behavior is perhaps a bit lesser-known than UB, here is a (hopefully non-null ;-) pointer: https://stackoverflow.com/questions/18420753/unspecified-undefined-and-implementation-defined-behavior-wiki-for-c https://stackoverflow.com/questions/18420753/unspecified-und...

ErikCorry 5y ago

Similarly, standard C++ is not usable to implement virtual machines like Hotspot, and yet all virtual machines are implemented using C++ compilers.

pjmlp 5y ago
Not all, https://www.jikesrvm.org https://www.jikesrvm.org. Just one example, I can't be bothered to post others.

kortex 5y ago

Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. Seems like you'd have to allow only structures which hide memory implementation details if you truly want to avoid all UB. Same goes for any arithmetic which could overflow. That would require kernel devs to radically rethink how they interact with I/O, which would probably require specific architectures. In other words, writing a kernel portable on any of the existing ISAs that is also performant is basically impossible, barring some humongous breakthrough in compiler technology. Seems to me that when it comes to brass tacks, UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined and thus usually does what you want, but can result in bugs.

immibis 5y ago
Even kernels only interact with memory in reasonably predictable ways. I think they could all be hidden behind such abstractions, BUT it will make the language a lot more complex.
CRConrad 5y ago
> Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. With untyped pointers, yes. But it seems to me that if you have strong typing for function pointers you could mostly avoid that. > UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined Well, no, of course it isn't -- the clue is probably in the first half of the name, "Undefined Behaviour"... ;-)
ErikCorry 5y ago
Without concurrency you don't have to have UB to have user-defined pointers. x86 assembly language has no UB and has user-defined pointers.

RcouF1uZ4gsC 5y ago

I think the undefined behavior in C and C++ are even less defensible today than when they started because of the convergence of architectures. Pretty much every non-legacy architecture does IEEE floating point. Pretty much all of them do a flat address space. The word size is some power of 2(32 bit, 64 bit, maybe 128 bit in the future). They are almost always little endian. The memory models are converging towards the C++ memory model. Given that, I think simplifying the language and getting rid of foot guns could be done without losing any significant performance or actual flexibility/portability.

pjmorris 5y ago
It could be called 'C--' unless that's been taken.
- RcouF1uZ4gsC 5y ago
  There is a language C-- created by Microsoft Research (Simon Peyton Jones of Haskel and GHC fame) https://www.microsoft.com/en-us/research/wp-content/uploads/1998/01/pal-manual.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
jandrese 5y ago
You could also add that they all do 2s complement math. This is what the OpenBSD team did to OpenSSL. If the code has some complexity that is only necessary because it might have been run on a VAX or AIX or early Cray architecture then it is time to excise that complexity. They deleted thousands and thousands of lines of support for architectures that are only seen in museums and landfills today.
- astrange 5y ago
  C does require 2's complement math. However architectures of the future aren't going to have flat pointers (PAC/CHERI etc), and even current architectures have some non-IEEE floats (https://en.wikipedia.org/wiki/Bfloat16_floating-point_format https://en.wikipedia.org/wiki/Bfloat16_floating-point_format / https://en.wikipedia.org/wiki/Unum_(number_format) https://en.wikipedia.org/wiki/Unum_(number_format)).

abfan1127 5y ago

what's the history of having undefined behavior? why would a language designer not specify?

gpderetta 5y ago
Sanitizers attempt to do define the behaviour of undefined constructs, but expect an integer multiple slowdown compared even with unoptimized builds. It is very hard to specify the behaviour of, for example, use-after-free, or accessing an automatic variable after it goes out of scope, or data races, in a C-like language without significant runtime cost.
rocqua 5y ago
Because the code should be somewhat portable, and not all processors act the same. This is why left and right shift are weird with overflow. Not consistent between x86 and some other instruction set. Similar for accessing the null address. Besides that, how would you specify the behavior of reading from an address the user randomly generated himself? What is stored at an address not generated by the compiler is out of scope for the compiler. If you try to define something like 'always trap' or 'always return 0', you incur massive overhead. Besides that. The fact that signed integer over/underflow is undefined behavior actually unlocks a lot of reasonable optimizations that treat integers like actual integers. Things like (a+1 > a) always being true.
- deleted 5y ago
  [deleted]

speedcoder 5y ago

Can you still compile gcc code with -O0 (gcc option to turn optimization off) to get completely defined behavior? When doing so does it actually still turn off all optimizations? Also does -Os (optimization for size) still produce defined behavior?

foxfluff 5y ago
> Can you still compile gcc code with -O0 (gcc option to turn optimization off) to get completely defined behavior? No. The standard specifies what's undefined, optimization levels don't change it (though there are compiler flags such as -fwrapv which make undefined things defined). However, turning off optimizations will make behavior easier to predict.
- lanstin 5y ago
  it used to be passed around never to use -O0 because it was much less used/tested and would generate wrong code more often. Not sure id that was folklore or true.
  - saagarjha 5y ago
    -O0 is "well tested" because everyone uses it for debug builds. If it produced incorrect results people would be fairly upset (and they are when it does…but it's not particularly common, because incorrect optimizations are generally the problem when codegen is incorrect.)

jcranmer 5y ago

I think undefined behavior (as a general concept) gets an unfair share of the blame here. It's notable that almost all criticism of undefined behavior in C tends to focus on just two sources of UB: signed integer overflow and strict aliasing; other sources of UB just don't generate anywhere near the same vitriol [1]. Furthermore, it's notable that people don't complain about UB in Rust... which arguably has a worse issue with UB in that a) there's not even a proper documentation of what is UB in Rust, and b) the requirement that &mut x be the sole reference to x (and therefore is UB if it is not) is far more stringent than anything in C (bar maybe restrict), and I'm sure that most Rust programmers, especially newbies starting out with unsafe, don't realize that that's actually a requirement. There is a necessity for some form of UB in a C-like language, and that has to deal with pointer provenance. You see, in C, everything lives in memory, but on real hardware, you want as much to live in a register as possible. So a compiler needs to be able to have reasonable guarantees that, say, any value whose address is never taken can never be accessed with a pointer, and so can be promoted to a register. As a corollary, this requires that things like out-of-bound memory accesses, or worse, converting integers to pointers (implicating pointer provenance here) need to have UB in at least some cases, since these could in principle "accidentally" compute an address which is the same as a memory location whose address was never taken. That suggests that the problem isn't UB per se. If we look at the two canonical examples, arithmetic overflow and strict aliasing, we can see that one of the features of these things is that they have a pretty obvious well-defined semantics [2] that can be given for them, and furthermore, there's no way to access these well-defined semantics even avoiding this feature altogether. And I think it's the lack of this ability to work around UB that is the real issue with C, not UB itself. [1] For example, it is UB to pass in rand as the comparison function to qsort. I'm sure many people will not realize that before I wrote this, and even parsing the C specification to find out that this is UB is not trivial. For an interesting challenge, try giving a definition of what the behavior should be were it not UB--and no, you can't just say it's impl-defined, since that still requires you to document what the behavior is. [2] I will point out that, for arithmetic overflow, this semantics is usually wrong. There are very few times where you want <large positive number> + <large positive number> = <negative number>, and so you're mostly just swapping out an unpredictably wrong program for a predictably wrong program, which isn't really any better. However, the most common time you do want the wrapping semantics is when you want to check if the overflow happened, and this is where C's lack of any overflow-checked arithmetic option is really, really painful.

nn3 5y ago

Clickbait on arxiv? Et tu, Brute? No, most operating systems that people are actually use are written in ISO C, so the headline is by definition wrong.

immibis 5y ago
They are written in non-ISO C

qualudeheart 5y ago

So we can switch to rust now?

yjftsjthsd-h 5y ago
Sure; we look forward to your patches (keep in mind that they must preserve compatibility and portability to all currently supported architectures).
- flykespice 5y ago
  Forgot the main flavor, it must be performing, which is the reason UB were "created" in the ISO C in the first place.
- qualudeheart 5y ago
  I think my girlfriend can figure something out. She does embedded systems at Anduril using Rust.

mcguire 5y ago

From the paper: "For example, a well-known security issue in the Linux kernel was produced by a compiler incorrectly assuming a pointer null check was unnecessary ([40] fig. 6) and deleting it as an optimization. Or consider this (simplified) patch report for Linux [25]: The test [for termination] in this loop: [...] was getting completely compiled out by my gcc, 7.0.0 20160520. The result was that the loop was going beyond the end of the [...] array and giving me a page fault [...] I strongly suspect it’s because __start_fw and __end_fw are both declared as (separate) arrays, and so gcc concludes that __start_fw can never point to __end_fw. By changing these variables from arrays to pointers, gcc can no longer assume that these are separate arrays." Both of those sound like simple bugs in the compiler optimizer implementation, in which case they could hardly be use as examples of how the current C standard was bad.

foxfluff 5y ago
No, they're definitely features. The removal of null pointer checks in gcc is enabled by -fdelete-null-pointer-checks and is often enabled by default.
TazeTSchnitzel 5y ago
They aren't bugs. The C standard considers those cases to be undefined.

WalterBright 5y ago

D got around the overflow-is-UB problem by declaring that 2s-complement arithmetic will be used with wraparound semantics. Is there any reason for modern C to still support anything else?

mhh__ 5y ago
There are still processors that don't use two's complement, although I'm not sure that should really stop them if they wanted to declare all C implementations must be t-c.
- WalterBright 5y ago
  Those processors can use a dialect of C that embraces ones-complement. Mandating such support in the Standard has little practical effect on code, I expect most programs would have to be recoded to work on ones-complement anyway.
zajio1am 5y ago
Integer overflow is usually logic error, so a reasonable default behavior would be a trap instead of silent overflow (regardless of how signed integrers are stored in memory). Some architectures support that (e.g. MIPS).
- WalterBright 5y ago
  The article mentions cases where integer overflow is expected behavior.
  - zajio1am 5y ago
    C already offers 'unsigned' type variants that offers defined overflow (together with non-negative range). It would be useful to have another type variant that offers defined overflow (like in unsigned) together with signed range for such cases. But it still makes sense for basic integers to have overflow as UD, as in most cases it is not expected behavior. Note that in current C, if one needs defined overflow on signed integers, one can cast them to unsigned, to the operation and cast result back to int. That makes it implementation-defined instead of undefined.

flykespice 5y ago

Wow, this was an eye-opening read on my trust with ISO C. It makes much more understandable why linux codebase is riddled with compiler extensions, ISO C is simply not reliable anymore. The issue is bigger than what trembles on the surface, just like Dennis Ritchie said, it is a timebomb, soon enough these nuances will burst into a big issue in linux kernel, or worse yet, some essential system like avionics.

RustyRussell 5y ago

I still retch when told memcpy and memset cannot take NULL and 0 length. Try asserting that they're not NULL in glibc and try to boot your machine! Oops... bad compiler people, bad!

WalterBright 5y ago

I had an online discussion some years back where I suggested that C nail the size of char to 8 bits. He responded that there was a CPU that had chars be 32 bits, and wasn't that great that a C compiler for it would be Standard compliant? I replied by pointing out that nearly every non-trivial C program would have to be recoded to work on that architecture. So what purpose did the Standard allowing that actually achieve? I also see no problem for a vendor of a C compiler for that architecture making a reasonable dialect of C for it. After all, to accommodate the memory architecture of the x86, nearly all C compilers in the 80's adopted near/far pointers, and while not Standard compliant, it really didn't matter, and was tremendously successful. D made some decisions early on that worked out very well: 1. 2's complement wraparound arithmetic 2. sizes of basic integer types are fixed at 1 byte for chars, 2 for shorts, 4 for integers, 8 for longs. This worked out very well 3. floating point is IEEE 4. char's are UTF-8 code units (*) 5. chars are unsigned These 5 points make for tremendous simplicity gains for D programmers, and ironically increase portability of D code. After reading the paper, I'm inclined to change the definition of UB in D to not mean it can be assumed to not happen and not be unintended. (*) thanks for the correction

WalterBright 5y ago
I had another such discussion where I suggested that C abandon support for EBCDIC. I was told it was great that C supported any character set! I said C certainly does not, and gave RADIX50 as an example. How many C programs today would work with EBCDIC? Zero? There's no modern point in C not requiring ASCII, at a minimum.
- sedatk 5y ago
  > I was told it was great that C supported any character set I'm all for extensibility mechanisms to shut down the people like this. You want EBCDIC? It's now a github repository; go ahead and maintain it, or shut up.
- slavik81 5y ago
  What is it about RADIX50 that makes it incompatible with the C standard? The lack of a reserved null value?