[LLVMdev] GC heap implementation

[Talin]

I'd like to share some code with anyone who is interested.

A while back I started working on the problem of implementing a garbage 
collector using the LLVM primitives. While I managed to accomplish a 
fair bit in this direction, I eventually realized that it was 
distracting me from my main goal, which is implementing a compiler for a 
strongly-typed language of my own design. In other words, I was writing 
a GC implementation because I needed one, not necessarily because I 
wanted to write one. I decided to push the GC project to the back burner 
and focus on my main goal, on the theory that while that was happening 
the GC problem might be worked on by someone else.

Although my GC code was initially intended to support my runtime, I've 
lately been using it in the compiler. I realized that in my case, I 
couldn't keep on using llvm::BumpPtrAllocator because I couldn't make 
guarantees about the lifetime of AST nodes in my compiler, and if I used 
a malloc-based allocator I would have to do something like reference 
counting.

Instead, I took one component of my GC - the general heap implementation 
- and built a trivial mark & sweep collector on top of it, which seems 
to be working very well for my purpose.

This GC heap was to be the foundation for my collector. It's loosely 
inspired by the popular dlmalloc implementation (although it doesn't 
directly take any code from it), but it also supports a number of 
features useful for implementing a collector, such as the ability to 
efficiently walk the heap and free blocks based on a predicate callback. 
It also reserves space in the 8-byte allocation header for an opaque 
type tag pointer (or debug string if you don't need tags) as well as 
room for 2 mark bits. It supports aligned allocations, which is useful 
for doing work with SIMD instructions. It supports compile-time 
configurable guard bytes, small block bins, and other things you would 
expect in a modern allocator. The heap is thread-safe, and uses only 
pthread primitives for locking. It allows the heap to be non-contiguous, 
so if you have other libraries that are calling regular libc malloc you 
can still coexist with them. The code is written in fairly-well 
commented ANSI C and includes a number of unit tests.

In any case, this code is currently lying fallow, so if anyone is 
interested in working with it I will be glad to donate it.

-- Talin