News for hackers. Stuff that matters.
Re:Clang-11.0.0 Miscompiled SQLite by mehrdadn on Thursday June 04, 2020 @01:19AM (#23412767)
Question for any low-level optimizing compiler engineers here: I obviously realize these are all important, but in your judgment, how much of making an error-free compiler would you say is about having a comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews, vs. something else? Put another way, if you were to lose one of these, which ones do you think would have the most/least negative impact (or be the easiest/hardest to make up for with other things) in terms of the correctness of the final product?
Re:Clang-11.0.0 Miscompiled SQLite by g_airborne on Thursday June 04, 2020 @02:35AM (#23413289)
Somewhat unrelated but I read somewhere that the Rust team test their releases by compiling the entirety of crates.io and all Rust GitHub repositories to find regressions. The tool is called Crater. Source: https://www.pietroalbini.org/blog/shipping-a-compiler-every-...
Re:Clang-11.0.0 Miscompiled SQLite by twic on Thursday June 04, 2020 @02:11PM (#23419859)
I was reading the docs of some library the other day, and they had a list of projects using that library. It was an impressive list: long, and with some serious projects on there.

Then i saw that they try building those projects against their library as part of their test pipeline. If you want to add your project to the list, you can submit a pull request. No wonder the list is so substantial - it gets you free testing! Highly ingenious!

Re:Clang-11.0.0 Miscompiled SQLite by grenoire on Thursday June 04, 2020 @04:21AM (#23414056)
No longer the entirety but still a sizeable chunk of it; it helps with regression detection for them. World's biggest test suite?
Re:Clang-11.0.0 Miscompiled SQLite by jfkebwjsbx on Thursday June 04, 2020 @05:38AM (#23414526)
It is very common for compilers to be tested using client code. It is a practice that goes back decades.

Nowadays with so many open source projects and so much distributed computer power, it is even easier.

Re:Clang-11.0.0 Miscompiled SQLite by pornel on Thursday June 04, 2020 @07:12AM (#23415085)
What makes it easy and powerful for Rust is that ~all Rust projects use Cargo as the build system and test runner, so Crater can really test every Rust project in existence, not just code samples hand-picked into compiler's test suite.
Re:Clang-11.0.0 Miscompiled SQLite by jfkebwjsbx on Thursday June 04, 2020 @05:09PM (#23421830)
Only open source projects, which will not be the majority if Rust ends up taking up speed.
Re:Clang-11.0.0 Miscompiled SQLite by neeeeees on Thursday June 04, 2020 @01:26AM (#23412822)
The test suite is ultra important. Even in the unlikely case that you have an engineer who thoroughly understands the machine and language specs, you have a ton of existing, useful, programs that rely on under-defined behaviour in one or both of them.
Re:Clang-11.0.0 Miscompiled SQLite by mehrdadn on Thursday June 04, 2020 @01:29AM (#23412841)
Ah, I might have to tease out my question here. By correctness I'm only referring to the implementation being true to the language specification, not to "not breaking existing programs". So if a program relies on undefined behavior and then gets broken in the next version of the compiler because of that behavior, I don't consider that a correctness problem in the compiler for the purposes of this question. (Which is not to suggest keeping it working isn't a worthwhile goal. I'm saying that's not the aspect of it that I'm asking about.)
Re:Clang-11.0.0 Miscompiled SQLite by pjmlp on Thursday June 04, 2020 @01:44AM (#23412969)
The problem is that many don't learn C and C++ properly, they have read some language introduction book and assume "how my compiler does it" is the right way and probably never touched a copy of ISO.

So plenty of programs rely on UB even without realizing it.

Re:Clang-11.0.0 Miscompiled SQLite by alkonaut on Thursday June 04, 2020 @01:57AM (#23413065)
I have absolutely no problem finding out that we have a dozen new bugs in production for our 15 year old codebase, because we upgraded our compiler and it revealed places we used undefined or unspecified behavior.

I’d much rather have that than a compiler that evolves slower because its developers worry about existing non-conforming code.

I can always use the old version of the compiler if I don’t want it to break.

Re:Clang-11.0.0 Miscompiled SQLite by saagarjha on Thursday June 04, 2020 @02:01AM (#23413092)
You might if the compiler yelled at you for it before you shipped, but it’s just as likely to compile your code into something you didn’t really foresee…
Re:Clang-11.0.0 Miscompiled SQLite by Quekid5 on Thursday June 04, 2020 @02:41AM (#23413338)
How do much do you expect your compiler to yell? Undefined Behavior can result from extremely trivial things like x+1, where x is signed. Obviously, you don't want the compiler yelling at you for almost every single for loop or simple signed addition in your program.

There also seems to be this weird misapprehension (probably not shared by you) that this is the compiler being "out of to get you" for UB. That's not what happens... the compiler ASSUMES that no UB can happen and optimizes accordingly. This can certainly have surprising results, but doing anything else would leave a lot of performance on the floor. What has happened over the last decade is that compilers have become better and better at optimizing leading to more and more surprising results.

To anyone (again, not you) ITT complaining that their program 'used to work fine': It just happened to work, but it's been buggy from the get-go. If that's a problem for your ego, then you need to adjust your ego.

Re:Clang-11.0.0 Miscompiled SQLite by gwd on Thursday June 04, 2020 @04:48AM (#23414222)
> There also seems to be this weird misapprehension (probably not shared by you) that this is the compiler being "out of to get you" for UB.

Of course nobody actually thinks that the compiler is "out to get you". But if you do any work in a security context, that is the attitude you have to take: "If the compiler was lawful evil and trying to put security vulnerabilities into my code, what excuse could it use from the spec to justify doing so?" That's the only way to make sure that you won't get bitten by "well-intentioned" optimizations.

> To anyone (again, not you) ITT complaining that their program 'used to work fine': It just happened to work, but it's been buggy from the get-go. If that's a problem for your ego, then you need to adjust your ego.

This would be valid if what people were complaining about was random cowboy behavior. What people are complaining about is the fact that it is nearly impossible to write code without UB. The fact that UB can result from "trivial things like x+1 where x is signed" is exactly the problem.

Re:Clang-11.0.0 Miscompiled SQLite by saagarjha on Thursday June 04, 2020 @03:13AM (#23413588)
I mostly agree with your points, but I still think compiler authors have dropped the ball by not putting as much effort as detecting cases where they have run optimizations based on undefined behavior as they should have. We’ve seen some of these be rolled back with flags for overflow or null checks (which I personally think is a bit too far in the other direction).
Re:Clang-11.0.0 Miscompiled SQLite by Orphis on Thursday June 04, 2020 @07:17AM (#23415122)
Alternatively, you can instrument the code with checks for UB using a sanitizer. It won't be the compiler screaming at you but your CI running all your tests with this instrumented version of your software.

Not perfect, but should work for most sane people running CI before merging changes.

Re:Clang-11.0.0 Miscompiled SQLite by saagarjha on Thursday June 04, 2020 @02:21PM (#23419955)
Sanitizers don't catch all instances of undefined behavior, and they sure won't find anything that doesn't run…
Re:Clang-11.0.0 Miscompiled SQLite by klodolph on Thursday June 04, 2020 @01:59AM (#23413079)
The compiler doesn’t do a good job of revealing undefined behavior, it usually just makes your program break in mysterious ways.
Re:Clang-11.0.0 Miscompiled SQLite by alkonaut on Thursday June 04, 2020 @02:05AM (#23413119)
A better example is perhaps behavior that shouldn’t be relied upon: a standard library unordered collection (Set) where the implementation for 10 years preserves insertion order but says in the docs not to rely on it. Lots of programs have deliberately or not relied on it. Then suddenly it changes impl to one that doesn’t preserve insertion order for slightly better perf. You don’t want the std library developers to worry about existing code as long as the documentation always said “don’t rely on insertion order”.

Same with a list sort that is stable but never guaranteed it would be, then turns unstable much later. I was bitten by this one in .NET as were many others, and as a response the developers added hacks into the code to simulate the old behavior it detected the code was built against the older lib. That didn’t make the problem easier to find...

Re:Clang-11.0.0 Miscompiled SQLite by saagarjha on Thursday June 04, 2020 @02:09AM (#23413136)
> You don’t want the std library developers to worry about existing code as long as the documentation always said “don’t rely on insertion order”.

Sometime practicality wins out and the change is reverted when it breaks everything. It’s nice to come up with purist views, and in this case being able to point to documentation and say that the entire world needs to change is the morally high stance to take, but it’s not always what happens. (Some may say that this is what needs to happen to undefined behavior, but that one’s still up in the air. As it so happens I am on the “read the standard” camp…)

Re:Clang-11.0.0 Miscompiled SQLite by fit2rule on Thursday June 04, 2020 @01:50AM (#23413014)
More to the point, anyone doing compiler validation work would a) always have a full test suite as their first line of attack, b) always have a well understood developer pipeline in place, to ensure a consistent understanding - coding rules, code review processes, etc. and c) always looks at what the compiler is actually doing, compared to what they think its doing - i.e. is able to navigate code -> assembly and all the stages in between, with competence.

Anything less is asking for trouble.

Re:Clang-11.0.0 Miscompiled SQLite by joosters on Thursday June 04, 2020 @03:06AM (#23413530)
A ‘full’ test suite? I’m not sure that one of those has ever existed for any large program, let alone one under active development. We have to work in the real world here!
Re:Clang-11.0.0 Miscompiled SQLite by fit2rule on Thursday June 04, 2020 @04:13AM (#23414001)
Yes, a full test suite. 100% code coverage is a thing, even in compiler validation.

Also, every test that was ever written for a compiler is still out there, being run, somewhere.

And, for the record, the real world is pretty big.

Re:Clang-11.0.0 Miscompiled SQLite by andrewaylett on Thursday June 04, 2020 @08:56AM (#23415969)
But 100% code coverage isn't necessarily a useful thing in this context, as different code (and different options) mean different interactions between passes. And you're never going to cover all the different paths through the compiler.

Back when I worked on a commercial compiler, we had a smoke test which we ran before committing. It would take ~30 minutes to run. We had a longer, roughly eight hour, set of tests which we ran daily. And we had machines running tests 24/7, which managed to clock up roughly 20 million distinct test cases (combinations of code and options) over the course of a year.

Every single compiler bug we'd ever seen was present (in a reduced form) in the conformance tests we'd run before release. That took about a week.

Re:Clang-11.0.0 Miscompiled SQLite by fit2rule on Thursday June 04, 2020 @09:33AM (#23416300)
>And you're never going to cover all the different paths through the compiler.

Depends who you work for and how willing they are to let such justifications stand in a court of law.

Re:Clang-11.0.0 Miscompiled SQLite by joosters on Thursday June 04, 2020 @11:26AM (#23417887)
100% code coverage does not mean a full test suite. You can still find huge numbers of bugs in code that has 100% coverage in a test suite. The two are not the same!
Re:Clang-11.0.0 Miscompiled SQLite by fit2rule on Thursday June 04, 2020 @03:25PM (#23420709)
I'm not offering 100% coverage as anything but a level playing field, that things are tested. Also, code-path analysis is pretty much more advanced than you might think, especially when you get auto/generated testing rigs configured for particular tasks - and especially if you have a compiler to test, as well as all the (reproducible) applications it may produce ..
Re:Clang-11.0.0 Miscompiled SQLite by perlgeek on Thursday June 04, 2020 @02:25AM (#23413225)
Then the test suite is still hugely important -- you just have to design it to reflect what you consider "true to the language specification".

Or phrased differently, the test suite is (or should be) the machine-readable language specification.

Re:Clang-11.0.0 Miscompiled SQLite by barrkel on Thursday June 04, 2020 @06:50AM (#23414940)
That is only theoretical correctness, not useful correctness.
Re:Clang-11.0.0 Miscompiled SQLite by fluffything on Thursday June 04, 2020 @03:45AM (#23413821)
They all have a critical impact.

If you look at Rust, you cannot commit to master:

- without the resulting master merge passing the whole test suite, which would probably take a day or more to run locally, and - without a review of someone that knows the part of the code you modified well, or somebody they delegate to, and often, of a group of multiple people that know that part of the code well. These people verify that the code is correct, commented, tested, appropriate, etc. Often, a design team in charge of that part of the code that makes sure that the change goes in a direction that aligns with the project strategy/goals (i.e. that this is a change we want to make).

Even the best of the best software developers:

- don't always test that their code compiles before committing: for Rust, they really can't to, they'd need to cross-compile the compiler dozens of times, run these compilers under qemu on different hardware, and verify that they work - too much work for any single human - don't always test that their code passes the test suite: the test suite is _huge_. Its impossible for anybody to test anything locally, takes too much time. - don't always benchmark the compiler after a change on reasonable applications, takes too much time. - etc. point being, you cannot trust the best of the best, much less anyone else. As a Rust compiler dev, the first person that you should not trust is _you_.

The whole point of the process is identifying all possible sources of errors, and making them impossible, or at worst, extremely unlikely to happen.

Most of these errors are only quite unlikely to happen, e.g., because all the automated tooling that exists to prevent them is also written by humans that make mistakes.

But every time a new source of error is identified, there is at least a discussion about how to make it impossible to happen in the future.

Having a test suite, having reviewers, are just two things you have to do to avoid a large set of errors (see a comment below about how each release of Rust is required to succesfully compile all existing public Rust source code and run all their tests succesfully).

They are not barely enough. And even if your process makes errors extremely unlikely, Rust and LLVM have hundreds of PRs on flight and hundreds of developers working on the source code regularly. Throw enough developers at a project, and unlikely events become a daily thing.

Re:Clang-11.0.0 Miscompiled SQLite by mehrdada on Thursday June 04, 2020 @02:55AM (#23413450)
Not a compiler author, but have some experience with finding bugs in compilers. If I had to venture a guess, I'd pick the testsuite (and other tools like fuzzing and mass user base), since the complexity is quite high. In our experience with the EMI project (https://web.cs.ucdavis.edu/~su/publications/emi.pdf), some of the miscompilations were caused by one pass of the compiler emitting code that was considered to have contained undefined behavior by the next pass (see Figure 1(b)). I'd say the code reviewer will catch issues within a single pass, but the interaction between them are less likely to be caught by a human reviewer as the complexity grows.
Re:Clang-11.0.0 Miscompiled SQLite by mehrdadn on Thursday June 04, 2020 @03:28AM (#23413691)
Good thoughts, thanks!
Re:Clang-11.0.0 Miscompiled SQLite by saagarjha on Thursday June 04, 2020 @05:02AM (#23414315)
Completely off topic but reading this thread (without glasses in preparation to go to bed) was a bit confusing until I realized that your usernames differed by a single letter…
Re:Clang-11.0.0 Miscompiled SQLite by mehrdadn on Thursday June 04, 2020 @05:06AM (#23414334)
Haha, glad you cleared it up so that you can sleep easily now :-)
Re:Clang-11.0.0 Miscompiled SQLite by jfoutz on Thursday June 04, 2020 @02:25AM (#23413222)
I'm not quite the class of people you're asking, I worked on an interpreter for an old language for a long time.

Tests are fantastic for defined behavior. but running actual real world gigantic battle tested programs is where I found bugs. It _seems_ like you can just define the behavior. In my experience, the interpreter would mostly do what I wanted, unless like 4 complicated factors were in play. Often, it's so confusing, the user of your language is just trying to make something work. They're under a deadline, they find a way, and they make it work. They're not morons, hell, you have to be pretty sophisticated to find that weird edge to exploit.

I was super new, but I thought of a lot of my coworkers as surgeons. They'd see the problem, and find the smallest possible change to fix a bug. They were very careful.

I dunno. it's super hard. I made some optimizations where I had a choice, I could break a working program (but relying on undefined behavior) in one way or another. Seemed like with those big projects, the optimization is totally worth it. But you have to pick. If you choose the semantics to mean 'a' then X breaks, if you choose 'b' then Y breaks. Our users had been around the block a few times. They were sympathetic, and we held a pretty firm line on undefined behavior.

I dunno. I think rust probably handles this the best, recompiling and retesting against every crate ever. But here's the thing, if you're relying on some weird edge case, the test probably is as well. So you don't actually detect the change in behavior.

I think it's a hard problem, and there's no silver bullet. Write tests. Have careful engineers. Run big programs. In spite of all that, you're going to have to go to your users hat in hand occasionally, because when you build big systems there are lots of subtle edge cases. Shit's hard man.

Re:Clang-11.0.0 Miscompiled SQLite by hedora on Thursday June 04, 2020 @12:13PM (#23418461)
> having a comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews

I’ll be a contrarian, and say the careful software engineers are the most important. They’ll stop feature work to recreate the test suite.

On the other hand, nothing can save a good test suite from being selectively disabled or regressed by sloppy engineers.

Similarly, having a process that dictates careful code reviews just slows everyone down. The careful engineers would have done the code reviews properly without the policy. The sloppy ones will spend more time to produce comparably bad (or even worse) code reviews.

Re:Clang-11.0.0 Miscompiled SQLite by tannhaeuser on Thursday June 04, 2020 @02:03AM (#23413103)
The OpenBSD project used to verify gcc (back when it was at 4.2 or so) as compiler for their O/S. Don't know if they still do; I'd imagine it's a lot of effort, and both clang and gcc have churned out yearly releases with ever-growing complexity since. C was once supposed to be a simple language closer to a portable macro assembler than a high-level language, and one for which writing a compiler is relatively straightforward and takes no longer than a year. This went out of the window with clang, and with gcc (and glibc!) being based on C++. Though of course optimizing out-of-order execution on modern CPUs is much more complex than your olde microcontroller-like CPU.
Re:Clang-11.0.0 Miscompiled SQLite by Quekid5 on Thursday June 04, 2020 @02:56AM (#23413459)
> C was once supposed to be a simple language closer to a portable macro assembler than a high-level language, and one for which writing a compiler is relatively straightforward and takes no longer than a year.

Do you have a source for this claim? AFAIU the history of C, it was invented for entirely pragmatic reasons.

> This went out of the window with clang, and with gcc (and glibc!) being based on C++.

This is nonsensical, whichever way one interprets "being based on C++". The GCC and Clang compilers conform to the standard whichever version of C or C++ you ask them compile. (Anything else is a bug and should be reported. They may accept a few non-conforming programs, but that's allowable under either implementation-defined behavior or undefined behavior. Remember that UB can include 'doing what the programmer expects'.)

Re:Clang-11.0.0 Miscompiled SQLite by GoblinSlayer on Thursday June 04, 2020 @12:24PM (#23418616)
That entirely pragmatic reason was to be assembler with curly braces. See memory capacity of PDP-7 and think what you can reasonably compile with those resources. Fun fact: if you don't specify variable's type, modern C compiler assumes int, this is how the first C compiler worked, you don't need types in assembler, the register type (machine word) is almost the only type you deal with. Implicit function declaration is an assembler feature too.
Re:Clang-11.0.0 Miscompiled SQLite by nineteen999 on Friday June 05, 2020 @07:55AM (#23427457)
First C compiler ran on the PDP-11, rather than the PDP-7 didn't it? Not that it makes a huge different to your point.
Re:Clang-11.0.0 Miscompiled SQLite by tannhaeuser on Friday June 05, 2020 @04:36AM (#23426313)
That's also how tcc (simplistic and functional modern one-pass C compiler) works I guess.
Re:Clang-11.0.0 Miscompiled SQLite by jabl on Thursday June 04, 2020 @02:41AM (#23413335)
> C was once supposed to be a simple language closer to a portable macro assembler than a high-level language,

That might have been K&R's original intention, but that went out the window pretty early on when optimizing compilers arrived on the scene. And eventually when the ANSI spec was written, it was explicitly written to allow all kinds of optimizations (the "as-if" rule).

Re:Clang-11.0.0 Miscompiled SQLite by gwd on Thursday June 04, 2020 @04:54AM (#23414271)
> And eventually when the ANSI spec was written, it was explicitly written to allow all kinds of optimizations (the "as-if" rule).

The ironic thing about that is that when they wrote C89, they said they were trying to standardize existing practice. I don't think they had any idea that they were effectively declaring 90% of all programs buggy.

Re:Clang-11.0.0 Miscompiled SQLite by kps on Thursday June 04, 2020 @12:14PM (#23418469)
> I don't think they had any idea that they were effectively declaring 90% of all programs buggy.

I agree. During the standardization process, there was a proposal (‘noalias’) that dmr described as “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs”, and, that “[i]t negates every brave promise X3J11 ever made about codifying existing practices, preserving the existing body of code, and keeping (dare I say it?) ‘the spirit of C.’”¹

If he or anyone else at the time had realized that ‘undefined behaviour’ would turn out to do the same, there response would have been the same: “[it] must go. This is non-negotiable.”

¹ https://www.lysator.liu.se/c/dmr-on-noalias.html

Re:Clang-11.0.0 Miscompiled SQLite by jfkebwjsbx on Thursday June 04, 2020 @05:19AM (#23414394)
And then retroactively declare that code broken and not conforming. Good times!
Re:Clang-11.0.0 Miscompiled SQLite by jabl on Thursday June 04, 2020 @05:51AM (#23414598)
In defense of whoever was involved in the C89 process, I think they had an impossible task. At the same time they wanted to standardize the "portable macro-assembler" as well as allowing optimizations. With such constraints they could not but fail.

With hindsight, maybe K&R should have consulted with PL experts and researchers and designed a "proper" language with a better emphasis on soundness and safety. I'm not saying they could have invented something like Rust back in the 1970'ies, but even then the state of the art was far ahead of K&R C.

Re:Clang-11.0.0 Miscompiled SQLite by acqq on Thursday June 04, 2020 @04:34AM (#23414156)
> comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews, vs. something else

In practice, you need all, for various reasons.

> in terms of the correctness of the final product

What is there "correctness"? Ah, I see in your later post:

> I'm only referring to the implementation being true to the language specification

The answer is: even checking for that is not something which can put the humans out of the loop. But humans alone (as in "extremely thorough code reviews" or "very careful software engineers") are provably not enough as the "space" that has to be tested is too big to be useful without "a comprehensive test suite." Still I'm not aware that a complete "comprehensive test suite" which would be "enough" for any non-trivial language can exist.

In my experience, non-trivial goals are simply bigger than any "simple" or "single" "solution." So in that sense, any project eventually fails due to the human factor. It's the humans that will use anything else as the tools to achieve the goal. It's the quality of humans that are in charge that is the precondition for everything else.

So the answer is always: prioritize for having good people, anything else will be taken care of by them: they will maintain the tests, be careful, do the reviews etc. Don't expect you can "save" on something.

Re:Clang-11.0.0 Miscompiled SQLite by chandlerc1024 on Thursday June 04, 2020 @08:05AM (#23415511)
Test suite, without a doubt.

Asking humans to be careful at scale (whether authoring or reviewing) just won't work.

Keep in mind that you need loooooots of test suites, not just one.

Re:Clang-11.0.0 Miscompiled SQLite by lanza on Thursday June 04, 2020 @01:21PM (#23419252)
llvm has a very thorough test suite and it's main test suite is exactly for this purpose. The error witnessed here by sqlite will be turned into a test case that takes the C code and compiles it and hand checks whether the output was miscompiled or not.

Here's a test from 2007 that tests a similar error in the instruction selector:

https://github.com/llvm-project/llvm/blob/master/test/CodeGe...

Evidently the error that caused this test to be rewritten reordered the `ret` instruction before the `mov $1, $eax` instruction that sets the return value. This tests assures that the bug will never happen again.