An aligned memory allocator
In “An unaligned memory allocator”, we built a memory allocator that allocated memory to unaligned addresses.
Is it fun getting nastygrams from clang and lldb about all your misaligned addresses?
No. No it is not.
In this post, we’ll talk about what that means, why we would want to allocate to aligned addresses, and the code to do so.
A working version of all this code can be found here.
Here’s what we want our heap to look like. Every header starts at an address that’s a multiple of 16. This is a 16 byte aligned allocator. Note that we’re paying wasted space (internal fragmentation) for alignment, in contrast to our prior allocator which was unaligned but very efficient at byte packing.
Memory allocated by the fixed alignment allocator. Less packed, but overall better!
Alignment
Alignment refers to the fact that memory gets allocated to addresses that are a multiple of the alignment base.
With natural alignment, an int gets allocated to memory addresses that are multiples of 4, longs get allocated to memory addresses that are multiples of 8, and so on.
People also often talk about cache alignment, which has to do with making sure that you don’t straddle cache lines (which are usually bigger things like 64 bytes).
In the code in this post, we just align everything to 16, the highest scalar alignment base that C++ offers. So, all memory gets allocated at addresses 0, 16, 32, etc.
That’s in contrast to our prior unaligned allocator, which allocates at the next available free spot. Ignoring headers, it might allocate an int (4 bytes) at 0, a 7 byte size struct at 4, another int at 11, and so on.
We want our allocator to allocate memory to aligned addresses for a variety of reasons:
- The C++ standard requires it and various compiler choices depend on it. (As you can obviously tell from the abundant warnings when you compile 😬)
- Memory may straddle cache lines or pages, which worsens performance.
- Straddling cache lines requires two lookups during CPU memory loads. That can be 1.5x to 2x more cycles (~5->~10).
- As an extension of the last, two lookups means two chances to miss the CPU cache and need to go to DRAM. That can be ~50x more cycles (~5->~250).
- Straddling pages means also straddling a cache line. So, same issue as above: 1.5x to 2x more cycles. But also, it’s two TLB entries, so you have double the chance to miss the TLB and need to go do page walking.
Aligning
The good news for us is that alignment is pretty easy. Let’s see how to do it:
// C++ helpfully provides a type whose alignment requirement is at least as
// strict (as large) as that of every scalar type.
constexpr int alignment = alignof(std::max_align_t);
constexpr int heap_size = 4096;
// We align heap so that it itself starts on an address which is a multiple of
// `alignment`. It wouldn't do us much good for all our memory in here to be
// aligned, but the whole heap to be misaligned!
alignas(alignment) char heap[heap_size] = {};
We’re going to need a way to ask for the next alignment multiple above any arbitrary size, so let’s make a function for that:
// Returns the next highest multiple of alignment above n.
constexpr int align_up(int n) {
int rem = n % alignment;
if (rem == 0) return n;
return n + alignment - rem;
}
Ok, now let’s fix our headers so that we pad them to the nearest alignment.
Luckily in this case, it’s actually easier to do this than the byte packing we
were doing before, since we can now just std::memcpy the struct directly
without concern for the extra padding (we want the extra padding!):
constexpr int header_size = align_up(sizeof(header));
header read_header(std::span<const char> bytes) {
header out;
std::memcpy(&out, bytes.data(), sizeof out);
return out;
}
void write_header(std::span<char> bytes, const header& h) {
std::memcpy(bytes.data(), &h, sizeof h);
}
And finally, our malloc and free. Mostly these are identical, except that malloc needs to size up any request to the nearest multiple of alignment:
void* specialmalloc(int size) {
if (size <= 0) return nullptr; // Junk request.
int offset = 0;
header h;
while (true) {
offset += header_size;
h = read_header(std::span(heap).subspan(offset));
if (h.footer) {
return nullptr; // Walked every block, nothing fits.
}
bool enough_space_in_heap = offset + header_size + align_up(size) <= heap_size - header_size;
if (h.len == 0 && !enough_space_in_heap) {
return nullptr; // Fresh space is the tail, so nothing further fits.
}
bool unused = !h.used;
bool enough_space = h.len == 0 || align_up(h.len) >= size;
if (unused && enough_space) {
break; // Got a spot: break and use it.
}
offset += align_up(h.len);
}
// If the pre-existing len is larger, keep it so the walk still jumps over
// the whole block.
int len = (h.len == 0) ? size : h.len;
write_header(std::span(heap).subspan(offset), header{.len = len, .used = true});
offset += header_size;
return &heap[offset];
}
void specialfree(void* ptr) {
if (ptr == nullptr) return; // Junk request.
uintptr_t addr = (uintptr_t)ptr;
uintptr_t base = (uintptr_t)heap;
uintptr_t offset = addr - base - header_size;
header h = read_header(std::span(heap).subspan(offset));
h.used = false;
write_header(std::span(heap).subspan(offset), h);
}
Next up
This is great, and solves the alignment issues as the image at the top showed. Huzzah! But, we have a major issue: fragmentation.
When memory gets allocated, it takes the first available aligned amount. If 128 bytes are requested, that’s what gets returned. When memory is returned, that 128 bytes becomes available… without splitting! The header for those 128 bytes is just marked available.
If a request comes in for 8 bytes, it will see that the 128 bytes is the first available spot, claim it, and write 8 bytes. That means 120 bytes are wasted and will remain unusable until the 8 bytes are freed.
Furthermore, if a request for 129 bytes comes in, it won’t be able to make use of those 128 bytes, even if the next spot adjacent to it is free (we’d want to coalesce those two into one to serve the 129 byte request).
In the next post, we’ll talk about splitting and coalescing.