Everything Was Const
Our service had two arena allocators: one per request and one for constants. The constant one turned out not to be constant.
Two arenas
This is the service from The Compiler Is Wrong.
It used arena allocators.
An arena is a suballocator that never frees, and its malloc is just a pointer increment.
This is folly’s Arena as it was then:
void* allocate(size_t size) {
size = roundUp(size);
bytesUsed_ += size;
if (LIKELY(end_ - ptr_ >= size)) {
// Fast path: there's enough room in the current block
char* r = ptr_;
ptr_ += size;
assert(isAligned(r));
return r;
}
// Not enough room in the current block
void* r = allocateSlow(size);
assert(isAligned(r));
return r;
}
void deallocate(void* p) {
// Deallocate? Never!
}
All of the memory goes back at once, when the arena itself is destroyed.
We had two of them. One lived as long as a request. The other was the “constant” arena, for data that was built once and then only read.
There are no locks in that code. For a constant arena that should be fine, because nothing allocates from it once it has been filled.
Random corruption
The crashes were absolutely random memory corruption. The stack traces had nothing in common.
This was more than ten years ago, so part of what follows is me reconstructing how I would have gone about it. I think I ran the service with a single thread, and it didn’t crash. I think we could already build with ASAN by then, and ASAN found nothing. That made it most perplexing.
It took a lot of undirected experiments. They left me with vague intuitions and a better understanding of the codebase. Then, outside work, came a sudden flash that made all the observations make sense.
The tables were const
As I remember it, the team used const as much as it could.
The constant tables were const, and the code that read them could not change them.
It didn’t change them.
It changed the arena they lived in.
I can’t tell you the exact line any more. It was either a copy of a value fetched from a map, or a key constructed for a lookup. The copy is enough to show the mechanism:
typedef std::vector<int, StlAllocator<int> > Ints;
typedef std::map<int, Ints, std::less<int>,
StlAllocator<std::pair<const int, Ints> > > Table;
// A request looks a list up in the constant table and adds it up.
long request(const Table& table, int key) {
const Ints ints = table.find(key)->second;
long sum = 0;
for (size_t i = 0; i < ints.size(); i++) sum += ints[i];
return sum;
}
table is a const reference, find is a const member function and ints is a const local.
Nothing here can change the table, and nothing does.
But ints is a copy, a copy needs memory, and a copy of a container asks the allocator of the original for it.
The allocator is a pointer to the arena, and constness stops at that pointer.
I don’t have the original code. I had a clanker write the smallest complete program with that shape: a table in an arena, built by one thread at startup, then read by requests on several threads.
#include <atomic>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <thread>
#include <vector>
// Like folly::Arena: allocating is a pointer increment, nothing is freed,
// and there are no locks.
struct Arena {
char* ptr_;
std::atomic<long> calls;
explicit Arena(size_t size)
: ptr_(static_cast<char*>(malloc(size))), calls(0) {}
void* allocate(size_t size) {
calls++;
char* r = ptr_;
ptr_ += (size + 15) & ~size_t(15);
return r;
}
};
// Like folly::StlAllocator: lets a standard container allocate from an arena.
template <class T>
struct StlAllocator : std::allocator<T> {
Arena* alloc_;
explicit StlAllocator(Arena* a) : alloc_(a) {}
template <class U> StlAllocator(const StlAllocator<U>& o) : alloc_(o.alloc_) {}
template <class U> struct rebind { typedef StlAllocator<U> other; };
T* allocate(size_t n, const void* = 0) {
return static_cast<T*>(alloc_->allocate(n * sizeof(T)));
}
void deallocate(T*, size_t) {} // Deallocate? Never!
};
template <class T, class U>
bool operator==(const StlAllocator<T>& a, const StlAllocator<U>& b) { return a.alloc_ == b.alloc_; }
template <class T, class U>
bool operator!=(const StlAllocator<T>& a, const StlAllocator<U>& b) { return a.alloc_ != b.alloc_; }
typedef std::vector<int, StlAllocator<int> > Ints;
typedef std::map<int, Ints, std::less<int>,
StlAllocator<std::pair<const int, Ints> > > Table;
// A request looks a list up in the constant table and adds it up.
long request(const Table& table, int key) {
const Ints ints = table.find(key)->second;
long sum = 0;
for (size_t i = 0; i < ints.size(); i++) sum += ints[i];
return sum;
}
int main(int argc, char** argv) {
int nthreads = argc > 1 ? atoi(argv[1]) : 1;
Arena constants(256 << 20);
// Startup: one thread builds the table. After that it is only used as const.
Table building((std::less<int>()),
StlAllocator<std::pair<const int, Ints> >(&constants));
for (int key = 0; key < 100; key++)
building.insert(
std::make_pair(key, Ints(8, key, StlAllocator<int>(&constants))));
const Table& table = building;
long atStartup = constants.calls;
// Requests: the list stored under `key` is eight times `key`.
std::atomic<long> wrong(0);
std::vector<std::thread> threads;
for (int t = 0; t < nthreads; t++)
threads.emplace_back([&table, &wrong] {
for (int i = 0; i < 1000000; i++)
if (request(table, i % 100) != 8 * (i % 100)) wrong++;
});
for (size_t t = 0; t < threads.size(); t++) threads[t].join();
printf("allocations at startup: %ld\n", atStartup);
printf("allocations by requests: %ld\n", constants.calls - atStartup);
printf("wrong answers: %ld\n", wrong.load());
}
$ g++ -std=c++11 -O2 -pthread const_map.cpp
$ ./a.out 1
allocations at startup: 200
allocations by requests: 1000000
wrong answers: 0
$ ./a.out 4
allocations at startup: 200
allocations by requests: 4000000
wrong answers: 47114
With one thread, a million requests take a million allocations out of the constant arena and every answer is right. That is my single-threaded run without crashes.
With four threads the arena hands the same memory to two requests at once, and one of them adds up the other’s list. The number of wrong answers is different on every run: 47,114, then 33,089, then 55,640. In this program the damage is a wrong sum. In a service full of pointers it is a crash somewhere else, later.
C++ was different then, so I also built it with GCC 4.8.5, the compiler from the previous post. It behaves the same.
The copy doesn’t even have to look like one:
for (const std::pair<int, Ints>& entry : table) sum += entry.second.size();
The elements of the map are std::pair<const int, Ints>.
This loop asks for std::pair<int, Ints>, so every element is converted, and the conversion copies the list: one allocation from the constant arena for each entry on each pass.
Today’s GCC warns about that line with -Wall.
GCC 4.8.5 compiles it without a word.
The fix
We forced those copies onto the right allocator. In the program above that is one line: the copy is told which arena to use.
long request(const Table& table, int key, Arena* requestArena) {
const Ints ints(table.find(key)->second, StlAllocator<int>(requestArena));
$ ./a.out 4
allocations at startup: 200
allocations by requests: 0
wrong answers: 0
The counter only watches the constant arena, and here every thread has an arena of its own standing in for the per-request one.
C++11 also has a hook for choosing the allocator of a copy, select_on_container_copy_construction.
Its default is the allocator of the original, and I don’t remember whether we touched it.
The std::pmr containers that came with C++17 made the other choice: a copy gets the default memory resource, not the arena of the original.
What ASAN can’t see
ASAN is awesome.
ASAN is why C++ is bearable.
AddressSanitizer arrived in GCC 4.8, and it had nothing to say about any of this.
Built with -fsanitize=address, the unfixed program still gets a few answers wrong on most runs, and ASAN reports nothing.
ASAN isn’t very useful with suballocators.
It knows which memory is valid because it sees every malloc and free.
An arena takes one big block from malloc and hands out pieces of it on its own.
To ASAN the whole block is a single valid allocation, so whatever goes wrong inside it looks fine.
Nothing is ever freed either, so there is no use after free to catch.
The simplest case is a write that runs off the end of one object and into the next:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sanitizer/asan_interface.h>
struct Arena {
char* block_;
char* ptr_;
explicit Arena(size_t size)
: block_(static_cast<char*>(malloc(size))), ptr_(block_) {}
~Arena() { free(block_); }
void* allocate(size_t size) {
char* r = ptr_;
ptr_ += (size + 15) & ~size_t(15);
#ifdef REDZONES
ptr_ += 16; // a gap after the object, off limits to everyone
ASAN_POISON_MEMORY_REGION(r + size, ptr_ - (r + size));
#endif
return r;
}
};
int main() {
Arena arena(1 << 20);
char* name = static_cast<char*>(arena.allocate(16));
long* balance = static_cast<long*>(arena.allocate(sizeof(long)));
*balance = 100;
memset(name, 'A', 24); // 8 bytes too many
printf("balance = %ld\n", *balance);
return 0;
}
$ g++ -g -fsanitize=address redzone.cpp && ./a.out
balance = 4702111234474983745
The memset writes 8 bytes too many, balance is garbage, and ASAN has nothing to say.
Redzones
But you can plug in and help ASAN help you.
ASAN lets a program mark memory as off limits by hand, with ASAN_POISON_MEMORY_REGION from <sanitizer/asan_interface.h>.
An arena can leave a gap after every object it hands out and poison it.
That gap is a redzone.
In the example above it is the two lines under #ifdef REDZONES.
With them, the same overflow is an error at the line that caused it:
$ g++ -g -fsanitize=address -DREDZONES redzone.cpp && ./a.out
==1211949==ERROR: AddressSanitizer: use-after-poison on address 0x7bb859add810
WRITE of size 24 at 0x7bb859add810 thread T0
#0 0x7fb85b11e6e9 in memset
#1 0x558a3f0922fb in main redzone.cpp:28
The macro compiles to nothing when ASAN is off.
Redzones also catch the bug from this post, some of the time. When two requests are handed the same address and ask for different sizes, the redzone of the smaller object ends up inside the bigger one. The request that owns the bigger one writes there, and ASAN stops it.
I took the unfixed program, gave its lists different lengths, added the same two lines to its arena and ran it with four threads:
==1200332==ERROR: AddressSanitizer: use-after-poison on address 0x7bae74557a50
WRITE of size 4 at 0x7bae74557a50 thread T2
#3 std::vector<int, StlAllocator<int> >::vector(std::vector<int, StlAllocator<int> > const&)
#4 request(std::map<...> const&, int)
0x7bae74557a50 is located 1409616 bytes inside of 268435456-byte region
allocated by thread T0 here:
#0 malloc
#1 Arena::Arena(unsigned long)
#2 main
A request is writing into the block that main allocated for the constant arena.
That report points at the bug.
It is not deterministic, because it takes a collision between two requests that ask for different sizes. This program collides thousands of times per run, and it stopped like this in twelve runs out of twelve. With all the lists the same length it stopped in none of twelve: the two redzones line up, and nobody steps on anything.
The other sanitizer
ThreadSanitizer arrived in the same GCC 4.8, and it sees the cause where redzones see the damage.
On the first program it points at the two lines of allocate that touch ptr_, and at the copy that led there:
$ g++ -std=c++11 -O1 -g -pthread -fsanitize=thread const_map.cpp && ./a.out 4
WARNING: ThreadSanitizer: data race
Read of size 8 by thread T2:
#0 Arena::allocate(unsigned long) const_map.cpp:18
#6 std::vector<int, StlAllocator<int> >::vector(std::vector<int, StlAllocator<int> > const&)
#7 request(std::map<...> const&, int) const_map.cpp:47
Previous write of size 8 by thread T1:
#0 Arena::allocate(unsigned long) const_map.cpp:19
#6 std::vector<int, StlAllocator<int> >::vector(std::vector<int, StlAllocator<int> > const&)
#7 request(std::map<...> const&, int) const_map.cpp:47
A draft I never merged
I wrote redzones for folly::Arena at the time.
It stayed a draft in our code review tool, and I used it for debugging.
I never pushed to merge it.
Redzones cost memory, a gap after every object, and I think that is why.
folly::Arena also wasn’t my team’s core responsibility, and maybe I wasn’t brave enough to change that code for everyone.
And the code that needed it was dying.
It was the interpreter for FXL, the language our rules were written in, and FXL was about to be replaced with Haskell.
We were already migrating the service to Haxl.
There the nursery of the garbage collector takes the place of the arena, and the runtime is strong.
As far as I can tell, folly’s Arena still has no such hooks today.
If you implement a suballocator
Consider redzoning support. It is a few lines in the allocator, and it decides whether ASAN can see anything that lives inside it.