New block-structured heap organization for 64-bit

I was having some discussion about GHC's block structured heap with Sergio Benitez and Adam Belay, and during the discussion it was suggested that the way GHC manages the block structured heap is suboptimal when we're on 64-bit architectures.

At the moment, we allocate memory from the operating system per-megablock, storing metadata in the very first megablock. We have to do this because, on 32-bit, we can't generally be too picky about what address our memory ends up living. On 64-bits, we have a lot more flexibility.

Here is the proposal:

1. Statically decide on a maximum heap size in a power of two.
2. Next, probe for some appropriately aligned chunk of available virtual address space for this. On POSIX, we can mmap /dev/null using PROT_NONE and MAP_NORESERVE. On Windows, we can use VirtualAlloc with MEM_RESERVE. (There are few other runtimes which do this trick, including GCC Go.)
3. Divide this region into blocks as before. The maximum heap size is now the megablock size, and the block size is still the same as before. Masking to find the block descriptor works as before.
4. To allocate, we keep track of the high-watermark, and mmap in 1MB pages as they are requested. We also keep track of how much metadata we need, and mmap extra pages to store metadata as necessary.

We still want to request memory from the operating system in conveniently sized chunks, but we can now abolish the notion of a megablock and the megablock allocator, and work purely with block coalescing. Additionally, the recorded heap location means that we can check if a pointer is HEAP_ALLOCED using a mask and equality check, solving #8199 (closed).

What do people think?

Trac metadata

Trac field	Value
Version	7.8.3
Type	Task
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Runtime System
Test case
Differential revisions
BlockedBy
Related
Blocking
CC	simonmar
Operating system
Architecture