Optimizing a Buddy Allocator

Buddy System Review

Start with a constant heap size, e.g. 1MB
- If we run out of space, we allocate a whole new heap.
- So we innately need to handle multiple arenas - each buddy system heap is a separate arena.
Have an array of free list pointers.
- One bucket for each power of two up to the heap size.
- For a 1MB = 2^20 B heap, that's slots numbered 0..20. We don't use index zero since we can't do 1B allocations, but that's fine.
- Doubly linked for O(1) insert / remove.
Allocate 128k
- Once: Split 1MB => 512k, 512k => 256k, 256k => 128k
- Again: No need to split, we've got one.
- Again: Split 256k => 128k
- Free the first one, no merge.
- Free the last one, no merge.
- Free the middle one, merge back to 1MB.

Problem: Our free list structure too big.

struct cell {
    // in both cell and header
    long size;
    long arena;
    bool used;
    
    // not in header
    cell* next;
    cell* prev;
};

sizeof(cell) = 40

On AMD64, a reasonable minimum header size is 8. Pointers need to be 8-byte aligned, so using a size 8 header maintains that alignment for the pointer we return to the user.

Similarly, a reasonable minimum cell size is 16, since nobody should really expect the allocator to be efficient for allocations smaller than 8.

So let's fit in those sizes:

struct cell {
    // in both cell and header
    uint32_t arena;  // up to 4B of them
    uint8_t  size;   // store which power of two
    uint8_t  used;   // used flag
    uint16_t _pad;
    
    // not in header
    int32_t next;   // offset from start of arena, -1 is EOL
    int32_t prev;   // offset from start of arena, -1 is EOL
};

ntuck@neu

Optimizing a Buddy Allocator

Buddy System Review

Problem: Our free list structure too big.