The Compiler Is Wrong
“It’s never the compiler” is a good rule. My first task on a new team at Facebook was the exception. It started with a crash in production and ended with a bug report against GCC.
A welcome gift
In late 2013 I joined the team behind Sigma, Facebook’s rule engine for catching spam and other abuse. Someone before me had tried to move the service to GCC 4.8. It crashed in production. Finding out why was my first task.
That was thirteen years ago, and I have to reach deep for the details.
I think the stack traces had unique_ptr at the top, with different callers below it from run to run.
The last suspect
When a program breaks after a compiler upgrade, the compiler is the last suspect. Much more often the code has undefined behaviour that the old compiler tolerated and the new optimizer takes advantage of. So before I could say “the compiler is wrong”, I had to make sure we weren’t triggering undefined behaviour ourselves. You can’t do that for a whole service. You can do it for a program small enough to read.
A few days of reducing
Getting to that small program took a few days.
I started by reproducing the crash on my dev machine, replaying traffic through the full service. Then I started removing major subsystems, the data sources.
The crash turned out to be a poor signal. Removing dead code, paths the replayed traffic never reached, would sometimes make it go away. A crash that comes and goes when you delete code that never runs looks like memory corruption in your own program. This was before my team used AddressSanitizer (ASAN). Getting it running on the service became one of my later tasks.
Eventually I realized that I could bisect the compiler flags instead of the code. That made the code reduction a lot faster too, because my oracle, the question “does it still crash?”, got more accurate. With fewer optimizations switched on, a crash that went away much more often meant I had removed something it needed.
From there it was down to making the smallest file possible, while reducing the flags in parallel.
It ended at 48 lines and a single flag on top of -O: -ftree-slp-vectorize.
That flag is GCC’s basic block vectorizer.
It looks for runs of similar scalar operations in straight-line code and merges them into vector instructions.
GCC 4.8 turns it on at -O3.
48 lines
This is the test case from my bug report:
#include <memory>
#include <iostream>
using namespace std;
class Foo {};
class Bar : public Foo {};
struct StlAllocator {
StlAllocator() : alloc_(nullptr) {}
explicit StlAllocator(void* p) : alloc_(p) {}
void* alloc_;
};
struct BarDelete : public StlAllocator {
void operator()(void*) const {}
};
struct FooDelete : public StlAllocator {
FooDelete() = default;
/* implicit */ FooDelete(const BarDelete& other) : StlAllocator(other.alloc_)
{}
void operator()(void*) const {}
};
unique_ptr<Bar, BarDelete> myalloc() {
return unique_ptr<Bar, BarDelete>(new Bar);
}
void fun(const unique_ptr<Foo, FooDelete>& foo) {
cout << "fun " << foo.get() << endl;
}
int main(int, char **) {
std::unique_ptr<Foo, FooDelete> foo;
std::unique_ptr<Bar, BarDelete> bar = myalloc();
foo = std::move(bar);
auto p = foo.get();
cout << "p " << p << endl;
if (p != foo.get()) {
cout << "wtf" << endl;
abort();
}
fun(foo);
return 0;
}
$ g++ -std=c++11 -O -ftree-slp-vectorize SmallCore.cpp
$ ./a.out
p 0x602010
wtf
Aborted
It moves a unique_ptr to a derived class into a unique_ptr to its base class.
Then it asks foo for its pointer twice and compares the two answers.
They differ.
Both deleters carry a pointer.
StlAllocator and alloc_ are names from folly, where a deleter remembers which allocator its object came from.
Our service used arena allocators, and its unique_ptrs had deleters like these.
There is nothing exotic in those lines: no casts, no uninitialized memory, no aliasing tricks. To my eyes it had no undefined behaviour. I wanted more confidence than that before filing a public bug report, and the file was now small enough to show to a couple of C++ experts and ask. That ruled it out.
What the compiler did
A plain unique_ptr is 8 bytes, because its default deleter is empty.
These are 16 bytes each: the deleter’s pointer, then the pointer to the object.
Moving one into the other comes down to four statements.
This is how Richard Biener later wrote them in plain C, with a for bar and b for foo (the comments are mine):
void *tem = a.b; // take the object pointer out of bar
a.b = (void *)0; // bar gives up ownership
b.b = tem; // foo gets the object pointer
b.a = a.a; // foo gets the deleter
The vectorizer saw two 8-byte copies between neighbouring fields and merged them into one 16-byte copy.
It put the 16-byte read after the write that empties bar.
This is what GCC 4.8.5 generates for the C++ test case:
mov 0x18(%rsp),%rbx # rbx = bar's object pointer
movq $0x0,0x18(%rsp) # bar's object pointer = null
movdqa 0x10(%rsp),%xmm0 # read 16 bytes of bar; its pointer is already null
movdqa %xmm0,(%rsp) # write 16 bytes to foo
foo now owns a null pointer, and the real one survives only in a register.
That explains the strange output.
The first foo.get() prints the right address, because the compiler answers it from the register.
The second is read back from memory, and it’s null.
In a real program that is a unique_ptr that looks fine where it’s moved and is null wherever it’s used next.
Thirteen hours
I filed GCC bug 59374 on Monday, December 2, 2013, at 4:02 in the afternoon in Menlo Park. The test case failed on GCC 4.8.1 and on a fresh build of trunk.
Nine hours later Richard Biener confirmed it.
Two hours after that he posted the code before and after the vectorizer and wrote: “obvious violating a WAR dependency. I’m sure it was me who broke this.”
WAR is write-after-read: the write that empties bar has to stay after the read.
Seven minutes later he had the same failure in 20 lines of plain C.
A little over an hour later he attached a patch.
That’s thirteen hours from my report to a patch. It was there at five the next morning, my time, and in GCC’s trunk two days after that.
Older than it looked
In January Richard came back to the bug. He wrote that backporting the fix to 4.8 would be hard, and that it wasn’t complete. He had found another way to trigger the miscompile, and committed a second fix with the comment “Now hopefully really fixed on trunk ;)”.
Jakub Jelinek bisected the C test case to a change from September 2010. The bug page lists GCC 4.6.4, 4.7.3 and 4.8.5 as failing, so the faulty check went out in three release series. My C++ test case passed on GCC 4.7.1 and failed on 4.8.1.
The fix shipped in GCC 4.9.0 in April 2014. At Facebook another team, one closer to build support, backported the patch to GCC 4.8, and we eventually migrated to a newer version.
Upstream, the fix never reached the 4.8 branch. The following July someone else filed “Data corruption when creating temporary object” about a move constructor under GCC 4.8. It was the same bug.
While writing this post I had a clanker fetch GCC 4.8.5, the last 4.8 release, from the Nix binary cache and compile the test case again.
It still prints wtf:
$ nix shell --impure --expr '(import (fetchTarball
"https://github.com/NixOS/nixpkgs/archive/nixos-19.09.tar.gz")
{ system = "x86_64-linux"; }).gcc48' \
-c g++ -std=c++11 -O -ftree-slp-vectorize SmallCore.cpp
$ ./a.out
p 0x3a0a1260
wtf
Aborted (core dumped)
GCC 4.9.4 gets it right.
That run also showed my unreliable oracle in miniature.
The 48 lines fail with -O -ftree-slp-vectorize and pass at -O3, where the vectorizer runs too.
At -O2 and above GCC inlines myalloc, bar never exists in memory, and there are no copies left to merge.
An optimization that has nothing to do with the bug decides whether it shows.
Still in the test suite
Richard’s reductions of the crash are still in GCC, as three files in its test suite: pr59374-1.c, pr59374-2.c and pr59374-3.c.
Nice welcome gift.