Everything About Memory Allocators, Part 2: malloc and free on a Linked List
文章目录
Part 1 stopped at the header struct. Now we make malloc and free work.
First, a correction. I said the union with char[16] forces 16 byte alignment. It doesn't. On x86_64 that union is 24 bytes with alignment 8, because a char array has alignment 1 and the struct inside only needs 8. I printed sizeof and _Alignof to be sure. malloc must return memory aligned for any normal type, and on x86_64 Linux that means 16 (alignof(max_align_t) is 16). The old header would hand out pointers that were only 8 aligned.
The fix is one keyword. I also added a prev pointer. It costs nothing, since the header pads out to 32 bytes anyway, and part 4 needs it.
#define ALIGN 16
#define F_FREE 1u
typedef struct header {
_Alignas(16) size_t size; // payload size, always a multiple of 16
struct header *next, *prev; // address ordered list
unsigned flags;
} header_t; // sizeof is 32 on x86_64
static header_t *head, *tail;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
A word on names. Everything is my_malloc, my_free and so on. If I used the real names, the test program's own printf would land in a half built allocator. We take over the real names in part 8.
Getting memory from the kernel
static header_t *grow(size_t size) {
uintptr_t cur = (uintptr_t)sbrk(0);
size_t pad = (ALIGN - (cur & (ALIGN - 1))) & (ALIGN - 1);
void *p = sbrk(pad + sizeof(header_t) + size);
if (p == (void *)-1) return NULL;
header_t *h = (header_t *)((char *)p + pad);
h->size = size;
h->flags = 0;
h->next = NULL;
h->prev = tail;
if (tail) tail->next = h; else head = h;
tail = h;
return h;
}
Two details are easy to miss. The break might not be 16 aligned, so we read it with sbrk(0) and pad. And sbrk takes a signed intptr_t, so a huge size turns negative and shrinks the heap instead of failing. That is why the caller rejects anything above INTPTR_MAX / 2.
Finding and taking a block
static void *alloc_locked(size_t size) {
if (size == 0 || size > (size_t)INTPTR_MAX / 2) return NULL;
size = align_up(size);
header_t *h = find_free(size);
if (h) h->flags &= ~F_FREE; else h = grow(size);
return h ? (void *)(h + 1) : NULL;
}
find_free walks from head and returns the first free block with size >= requested. That is first fit. It is not the best strategy, and part 5 measures how much that matters.
free
static void free_locked(void *ptr) {
header_t *h = (header_t *)ptr - 1;
h->flags |= F_FREE;
// give the very last block back to the kernel
if (h == tail && (char *)(h + 1) + h->size == (char *)sbrk(0)) {
if (h->prev) h->prev->next = NULL; else head = NULL;
tail = h->prev;
sbrk(-(intptr_t)(sizeof(header_t) + h->size));
}
}
Freeing sets a flag. The one exception is the last block. If it ends exactly at the current break, we return it with a negative sbrk. I compare against sbrk(0) instead of assuming, because glibc's own malloc may have moved the break behind our back.
Locking
my_malloc and my_free take one global mutex around alloc_locked and free_locked. It is blunt and correct, and it will not scale. The split into _locked functions exists so that realloc in part 3 can call both under a single lock. Locking twice from one thread with a default mutex is undefined behavior, and in practice it hangs.
Run it
gcc -std=c11 -Wall -Wextra -DDEMO -o part2 part2.c -lpthread && ./part2
Output
sizeof(header_t) = 32
after three mallocs
block +0 size 112 used
block +144 size 208 used
block +384 size 64 used
after free(b)
block +0 size 112 used
block +144 size 208 free
block +384 size 64 used
after malloc(150)
block +0 size 112 used
block +144 size 208 used
block +384 size 64 used
d reused b: yes, all 16 aligned: yes
The demo prints with dprintf because printf would call glibc's malloc and move the break under us. Offsets are 144 and 384 because each block is a 32 byte header plus payload: 32 + 112, then 32 + 208.
malloc(150) rounded up to 160 and reused the 208 byte hole, so 48 bytes sit wasted inside it. Part 4 fixes that. Next up is calloc and realloc, which look trivial and aren't.
