TLSF allocator with aligned allocations.
Properties:
- No dependencies. No standard library, no runtime library
- O(1) insertion/deletion (TLSF property)
- 32-bit block headers or 64-bit block headers supported (configurable)
- Minimal control structure memory footprint, minimal memory arena overhead
- Configurable number of classes & class sizes
- Configurable number of subclasses
- For some bit operations, optional use of intrinsics or fallback methods
- Aligned allocation with alignments being powers of 2 (natural alignment is block header size)
- Tested 32-bit/64-bit versions, tested with optimizations -O0, -O1, -O2, -Os, -O3 (no warnings)
- Uses relative offsets for all calculations, can thus be moved in memory by writing just 1 pointer
Allocator behavior:
[H0] - header of block 0
[P1] - leading aligning padding of used block 1
[U2] - user data of used block 2
[F3] - free usable space of block 3
All pointers returned by allocator point at the beginning of [Ux] user data.
1. Initial (F0 = remaining arena): [H0][ F0 ]
2. Alloc U1 (no special alignment): [H1][ U1 ][H0][ F0 ]
3. Alloc U2 (no special alignment): [H1][ U1 ][H2][ U2 ][H0][ F0 ]
4. Alloc U3 (small alignment padding): [H1][ U1 ][H2][ U2 ][H3][P3][ U3 ][H0][ F0 ]
5. Alloc U4 (large alignment padding): [H1][ U1 ][H2][ U2 ][H3][P3][ U3 ][H5][ F5 ][H4][ U4 ][H0][F0]
6. Free U2 (create F6): [H1][ U1 ][H6][ F6 ][H3][ U3 ][H5][ F5 ][H4][ U4 ][H0][F0]
7. Free U1 (create F7): [H7][ F7 ][H3][ U3 ][H5][ F5 ][H4][ U4 ][H0][F0]
8. Alloc U8 (large alignment padding): [H9][ F9 ][H8][ U8 ][H10][ F10 ][H3][ U3 ][H5][ F5 ][H4][ U4 ][H0][F0]
Coalescing rules:
- Padding space (leading unused space of allocated block to force user data alignment):
- If previous block is free, expand the previous block with the padding space
- If previous block is unavailable, but padding is large enough to be its own block, padding space becomes its own free block
- If previous block is unavailable, and padding is too small to be its own block, it stays as padding within used block
- Trailing space (unused end of allocated block beyond user-requested size):
- If next block is free, prepend trailing space to that free block
- If next block is unavailable, but trailing space is large enough to be its own block, trailing space becomes its own free block
- If next block is unavailable, and trailing space is too small to be its own block, it stays as a part of the used block
- Free block coalesces with previous and/or following free block(s)
- Newly freed block coalesces with padding space of the next block, if such padding space exists