diff options
| -rw-r--r-- | heap.c | 218 |
1 files changed, 218 insertions, 0 deletions
@@ -0,0 +1,218 @@ +/* Simple heap allocator. + * + * I saw this article: https://samwho.dev/memory-allocation/ + * and was inspired to re-write the heap allocator I made a + * while ago to try to make it faster and less wasteful. + * + * How it works: + * The allocator is given a buffer where all of the allocations + * will go. Each allocation is given a "block" from the buffer + * that is the size of the allocation plus a "header size". The + * header of each block is four bytes: The most significant + * 31 bits represent the size of the allocation and the least + * significant bit (or the "taken" bit) is 1 if the block + * currently represents an allocation and 0 if it's free and + * available for use. + * + * On initialisation, the allocator is given a single free + * block that is the size of the entire buffer. + * + * When heap_alloc is called: + * First, all of the current blocks are iterated. If a free + * block is found that's the same size as the requested + * allocation, then the block's "taken" bit is set to 1 and + * the block's allocation is returned. + * Otherwise, a free block that is larger than the requested + * allocation may be found. In this case, the block is split + * in two such that two blocks remain: A block of the same + * size as the allocation and a block containing the remaining + * half of the block. The former is returned. The free block + * from the split is placed before the returned block (in + * other words, the buffer is filled from back to front), + * that way when the allocator is called on again it might + * well find a suitable block within a few iterations. + * Otherwise, no free blocks were found to be big enough + * and thus the program is out of memory. Here, it just calls + * abort, but this case may want handling more cleanly. + * + * When heap_free is called: + * The header to the allocation is first calculated - it's + * simply the four bytes that come directly before the + * pointer that is given. The header's "taken" bit is set + * to zero to indicate a freed block. + * Then, the allocator is de-fragmented. What this boils + * down to is iterating all of the blocks and recording the + * first free block that is seen. Then, all free blocks after + * that are iterated until a "taken" block is found. Every + * block between the first free block and the first "taken" + * block is coagulated into a single free block before + * continuing from the first step until every block has been + * visited. + * + * There are also functions for aligning allocations, as + * that is also an integral part of any allocator. By default, + * allocations are given an alignment of 4 bytes, which is + * typical of general-purpose allocators on PCs. + */ + +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +typedef struct { + char* buffer; + int size, blocks; +} Heap; + +void init_heap(Heap* heap, char* buf, int size) { + heap->buffer = buf; + heap->size = size; + heap->blocks = 1; + ((int*)buf)[0] = size << 1; +} + +static uintptr_t align_address( + uintptr_t address, + size_t align +) { + size_t m; + m = align - 1; + return (address + m) & ~m; +} + +static void* heap_alloc_impl(Heap* h, int size) { + int* header, * nh, s, f, i, as, p; + i = 0; + as = size + sizeof *header; + p = 0; + for (i = 0; i < h->blocks; i++) { + header = (int*)(h->buffer + p); + s = header[0]; + f = !(s & 1); + s >>= 1; + if (f) { + /* There's no point creating blocks smaller than + * the header. */ + if (as < s - sizeof *header - 1) { + s -= as; + header[0] = (s << 1); + nh = (int*)(h->buffer + p + s); + nh[0] = (as << 1) | 1; + h->blocks++; + return nh + 1; + } else if (s == as) { + header[0] |= 1; + return header + 1; + } + } + p += s; + } + abort(); + return 0; +} + +static void heap_free_impl(Heap* h, void* ptr) { + int* header, *h2, i, j, s, f, d, n, ns, p; + header = &((int*)ptr)[-1]; + *header &= INT32_MAX << 1; + p = n = 0; + for (i = 0; i < h->blocks; i++) { + header = (int*)(h->buffer + p); + s = header[0]; + f = !(s & 1); + s >>= 1; + if (f) { + ns = s; + p += s; + d = 0; + for (j = i + 1; j < h->blocks; j++) { + h2 = (int*)(h->buffer + p); + s = h2[0]; + f = !(s & 1); + if (!f) { break; } + s >>= 1; + p += s; + ns += s; + d++; + } + i = j - 1; + n += d; + if (d) + header[0] = ns << 1; + } else + p += s; + } + h->blocks -= n; +} + +void heap_print_blocks(const Heap* h) { + const int* header; + int s, f, p, i; + p = 0; + printf("%8s %8s %s\n", "offset", "size", "free"); + for (i = 0; i < h->blocks; i++) { + header = (const int*)(h->buffer + p); + s = header[0]; + f = !(s & 1); + s >>= 1; + printf("%8d %8d %d\n", p, s, f); + p += s; + } +} + +void* heap_alloc_aligned(Heap* h, int size, unsigned align) { + unsigned char* p, * a; + ptrdiff_t shift; + size += (int)align; + p = heap_alloc_impl(h, size); + a = (unsigned char*)align_address((uintptr_t)p, align); + a += align * (unsigned)(p == a); + shift = a - p; + a[-1] = shift & 0xff; + return a; +} + +void heap_free_aligned(Heap* h, void* ptr) { + unsigned char* a; + ptrdiff_t shift; + a = ptr; + shift = a[-1]; + shift += 256 * shift == 0; + a -= shift; + heap_free_impl(h, a); +} + +void* heap_alloc(Heap* h, int size) { + return heap_alloc_aligned(h, size, 4); +} + +void heap_free(Heap* h, void* ptr) { + heap_free_aligned(h, ptr); +} + +int main() { + char buffer[4096]; + Heap heap; + int i, s; + void* allocs[64]; + init_heap(&heap, buffer, sizeof buffer); + srand(500); + /* Test: allocate a bunch of random blocks, + * then free them randomly, then allocate some + * more and print the state. */ + for (i = 0; i < 64; i++) { + s = rand() % 32 + 1; + allocs[i] = heap_alloc(&heap, s); + } + for (i = 0; i < 64; i++) { + if (rand() % 5 == 0) { + heap_free(&heap, allocs[i]); + } + } + for (i = 0; i < 32; i++) { + s = rand() % 32 + 1; + heap_alloc(&heap, s); + } + heap_print_blocks(&heap); +} |