csapp/allocator.c

配套源码，运行方法见同目录 README。返回实验总览。

/* Fixed arena with an implicit free list. Block headers follow physical order.
 * Valid pointers from this allocator only; no realloc, threading, or heap growth. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Block {
    size_t capacity;
    bool available;
    struct Block *prev, *next;
} Block;

typedef struct { unsigned char *memory; size_t bytes; Block *first; } Arena;
#define ALIGNMENT _Alignof(max_align_t)
#define HEADER_SIZE ((sizeof(Block) + ALIGNMENT - 1) / ALIGNMENT * ALIGNMENT)

static bool arena_init(Arena *a, size_t bytes) {
    bytes = bytes / ALIGNMENT * ALIGNMENT;
    if (bytes < HEADER_SIZE + ALIGNMENT) return false;
    a->memory = malloc(bytes);
    if (!a->memory) return false;
    a->bytes = bytes;
    a->first = (Block *)(void *)a->memory;
    *a->first = (Block){bytes - HEADER_SIZE, true, NULL, NULL};
    return true;
}

static void check_arena(const Arena *a) {
    const unsigned char *cursor = a->memory;
    const Block *previous = NULL;
    for (const Block *b = a->first; b; b = b->next) {
        assert((const unsigned char *)(const void *)b == cursor);
        assert(b->prev == previous);
        assert((uintptr_t)b % ALIGNMENT == 0);
        assert(b->capacity >= ALIGNMENT && b->capacity % ALIGNMENT == 0);
        assert(cursor + HEADER_SIZE + b->capacity <= a->memory + a->bytes);
        assert(!previous || !(previous->available && b->available));
        cursor += HEADER_SIZE + b->capacity;
        previous = b;
    }
    assert(cursor == a->memory + a->bytes);
}

static void *arena_alloc(Arena *a, size_t requested) {
    if (!requested || requested > SIZE_MAX - (ALIGNMENT - 1)) return NULL;
    size_t size = (requested + ALIGNMENT - 1) / ALIGNMENT * ALIGNMENT;
    for (Block *b = a->first; b; b = b->next) {
        if (!b->available || b->capacity < size) continue;
        if (b->capacity - size >= HEADER_SIZE + ALIGNMENT) {
            Block *rest = (Block *)(void *)((unsigned char *)(void *)b + HEADER_SIZE + size);
            *rest = (Block){b->capacity - size - HEADER_SIZE, true, b, b->next};
            if (rest->next) rest->next->prev = rest;
            b->next = rest;
            b->capacity = size;
        }
        b->available = false;
        check_arena(a);
        return (unsigned char *)(void *)b + HEADER_SIZE;
    }
    return NULL;
}

static void merge_next(Block *b) {
    Block *next = b->next;
    assert(next && b->available && next->available);
    b->capacity += HEADER_SIZE + next->capacity;
    b->next = next->next;
    if (b->next) b->next->prev = b;
}

static void arena_free(Arena *a, void *pointer) {
    if (!pointer) return;
    Block *b = (Block *)(void *)((unsigned char *)pointer - HEADER_SIZE);
    assert(!b->available); /* Some double frees; stale merged headers are not supported. */
    b->available = true;
    if (b->next && b->next->available) merge_next(b);
    if (b->prev && b->prev->available) merge_next(b->prev);
    check_arena(a);
}

int main(void) {
    Arena arena;
    assert(arena_init(&arena, 4096));
    assert(arena_alloc(&arena, 0) == NULL);
    assert(arena_alloc(&arena, SIZE_MAX) == NULL);
    unsigned char *a = arena_alloc(&arena, 48);
    unsigned char *b = arena_alloc(&arena, 80);
    unsigned char *c = arena_alloc(&arena, 48);
    assert(a && b && c);
    memset(a, 0xa1, 48); memset(b, 0xb2, 80); memset(c, 0xc3, 48);
    arena_free(&arena, b);
    unsigned char *reuse = arena_alloc(&arena, 16);
    assert(reuse == b); /* first-fit reuses the hole, potentially splitting it */
    memset(reuse, 0xdd, 16);
    for (size_t i = 0; i < 48; ++i) assert(a[i] == 0xa1 && c[i] == 0xc3);
    arena_free(&arena, reuse);
    arena_free(&arena, a);
    arena_free(&arena, c); /* coalesce with both sides */
    assert(arena.first->available && arena.first->next == NULL);
    assert(arena.first->capacity == arena.bytes - HEADER_SIZE);
    void *whole = arena_alloc(&arena, arena.bytes - HEADER_SIZE);
    assert(whole && arena_alloc(&arena, 1) == NULL);
    arena_free(&arena, whole);
    /* Deterministic fragmentation workload; inspect every live payload. */
    unsigned char *slots[32] = {0};
    size_t sizes[32] = {0};
    uint32_t rng = 7;
    for (unsigned step = 0; step < 4000; ++step) {
        rng = rng * UINT32_C(1664525) + UINT32_C(1013904223);
        unsigned slot = (rng >> 16) % 32;
        if (slots[slot]) {
            for (size_t i = 0; i < sizes[slot]; ++i) assert(slots[slot][i] == (unsigned char)slot);
            arena_free(&arena, slots[slot]); slots[slot] = NULL;
        } else {
            sizes[slot] = (rng >> 24) + 1;
            slots[slot] = arena_alloc(&arena, sizes[slot]);
            if (slots[slot]) memset(slots[slot], (int)slot, sizes[slot]);
        }
        check_arena(&arena);
        for (unsigned j = 0; j < 32; ++j)
            if (slots[j]) for (size_t i = 0; i < sizes[j]; ++i) assert(slots[j][i] == (unsigned char)j);
    }
    for (unsigned j = 0; j < 32; ++j) arena_free(&arena, slots[j]);
    assert(arena.first->next == NULL && arena.first->capacity == arena.bytes - HEADER_SIZE);
    printf("allocator: split/coalesce/payload checks passed (alignment=%zu, header=%zu)\n",
           (size_t)ALIGNMENT, (size_t)HEADER_SIZE);
    free(arena.memory);
    return 0;
}