Refactor Pal and LargeAlloc interaction.

[mjp41]

In #212, we built a simple power of two allocator for Open Enclave that is used so that the rest of the system does not have to overallocate to get the required alignment. This is great for improving the heap size on OE, but is bad in that the code is only tested on one platform.

The code is useful on platforms that don't support aligned allocation, as it prevents the need to overallocate and trim, which can lead to fragmentation.

I want to propose the following refactor

Pals

Pals have a minimum allocation size, Pal::min_alloc_size.

Pals provide one of two interfaces for reserving memory, the caller must guarantee to provide a request for at least Pal::min_alloc_size.

• std::pair<void*, size_t> reserve_at_least(size_t size) - provide a natural amount of memory for this platform, could reserve GiB or even TiB, on platforms that don't support aligned allocation. On OE, this would return the entire heap range, and nullptr for all subsequent calls
• void* reserve_aligned(size_t size) where size is a power of two. It is guaranteed to be aligned to the size.

Power of two allocator

Using the code from #212, we implement a layer on top of this, that can allocate any power of two size with natural alignment.

void* reserve(size_t size)

This code is single-threaded in the same way as in #212. All allocation sizes are supported from the smallest up (e.g. 1, 2, 4, 8, ...). This means that the power_two_allocator can be used to fulfil allocation requests from the AllocPool and PageMap where it does not use bss, and the LargeAllocator.

The Power of two allocator, like the Pal, does not support a way to return reserved memory.

The implementation will need to use the code from #212 on platforms that do not support aligned allocation, and for allocations below the min_alloc_size on platforms that do support aligned allocation.

This is effectively half of a buddy allocator that we use for carving up address space.

Benefits

• This code change will simplify a few corner cases around initialisation. The large allocator can depend on this, so its MPMCStacks don't need copying.
• It makes the Pal's simpler, and lets the Pal decide how to over allocate memory.
• Simplify the cross process shared memory use case as the Pal would just provide the entire shared address range. Initial documentation on how Verona / C++ interop should work. verona#140
• We can simplify the LargeAllocator to not perform alloc_chunk as that will just go to the power of two allocator.
• This leads to fewer different code paths across platforms reducing maintenance and testing costs.
• Also has the advantage that reserved space below the SuperslabSize alignment can be used for allocating the meta-data.

Costs

• Time probably a few days of work to get this improvement.