CPlay/freelist/main.c

#include "freelist.h"
#include "hexdump.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int x, y, z;
} Vec3;

Vec3 vec3_new(int a, int b, int c) {
    return (Vec3){a, b, c};
}

// Print function
void printvec(const Vec3 *v) {
    printf("Vec3: (%d, %d, %d)\n", v->x, v->y, v->z);
}

/* For testing crc poly 0x04C11DB7 */
uint32_t crc32(const uint8_t *data, size_t length);

#define BUFFER_SIZE (128)

int main() {
    FreeList fl;

    /* Here we split our malloc'ed memory into three parts, we pass one of
     * them to our freelist, and keep the other two (head/tail) to check for
     * overwrites:
     *
     *   | Headblock |      Freelist block     | Tailblock |
     *   |    1x     |            2x           |     1x    |
     */
    void *headblock = malloc(BUFFER_SIZE * 2);
    void *tailblock = headblock + (BUFFER_SIZE + BUFFER_SIZE / 2);
    void *mem = headblock + (BUFFER_SIZE / 2);

    /* Set these buffers to something known and randomize the buffer we give to the freelist */
    memset(mem, arc4random(), BUFFER_SIZE);
    memset(headblock, 0xAB, BUFFER_SIZE / 2);
    memset(tailblock, 0xF0, BUFFER_SIZE / 2);

    /* Store these for reference at the end of the testing */
    const uint32_t tail_crc = crc32(tailblock, BUFFER_SIZE / 2);
    const uint32_t head_crc = crc32(headblock, BUFFER_SIZE / 2);

    /* Display a nice hexdump so you can see the layout */
    hexdump(headblock, BUFFER_SIZE * 2, 32);

    if (!fl_init(&fl, (uintptr_t)mem, BUFFER_SIZE, sizeof(Vec3))) {
        printf("Freelist failed to initialize!\n");
        exit(EXIT_FAILURE);
    }

    const size_t cap = fl_capacity(&fl);

    printf("Item size: %lu\n", sizeof(Vec3));
    printf("FreeList Capacity: %lu\n", cap);
    printf("Buffer size: %d\n", BUFFER_SIZE);
    printf("Freelist Blocksize: %lu\n", fl.size);
    printf("Space utilization internal: %.2f%%\n", 100.0 * fl_utilization(&fl, sizeof(Vec3)));
    printf("Space utilization external: %.2f%%\n", 100.0 * ((float)fl.size * cap) / BUFFER_SIZE);

    assert(fl_available(&fl) == cap);
    assert(fl_check(&fl) == cap);

    Vec3 *a = fl_alloc(&fl);
    Vec3 *b = fl_alloc(&fl);
    Vec3 *c = fl_alloc(&fl);

    memset(a, 0xCA, sizeof(Vec3));
    memset(b, 0xCB, sizeof(Vec3));
    memset(c, 0xCC, sizeof(Vec3));

    *a = vec3_new(0xAAAA, 0xAAAA, 0xAAAA);
    *b = vec3_new(192, 199, 435);
    *c = vec3_new(432, 11, 435);

    printvec(a);
    printvec(b);
    printvec(c);

    assert(fl_check(&fl) == cap - 3);
    assert(fl_capacity(&fl) == fl_available(&fl) + 3);

    printf("Available: %zu of %zu\n", fl_available(&fl), fl_capacity(&fl));

    assert(fl_free(&fl, a));
    assert(fl_free(&fl, b));
    assert(fl_free(&fl, c));

    printf("Available: %zu of %zu\n", fl_available(&fl), fl_capacity(&fl));

    assert(fl_check(&fl) == fl_capacity(&fl) - fl_allocated(&fl));
    assert(fl_allocated(&fl) == 0);

    /* All memory is free here */

    uintptr_t *ptr_buf = malloc(sizeof(uintptr_t) * fl_capacity(&fl));

    /* Fill it up */
    for (int i = 0; i < fl_capacity(&fl); i++) {
        ptr_buf[i] = (uintptr_t)fl_alloc(&fl);
    }

    /* Write some data to the last element to catch out of bounds writes */
    size_t last_elem = fl_capacity(&fl) - 1;
    memset((void *)ptr_buf[last_elem], 0x42, sizeof(Vec3));

    assert(0 == fl_available(&fl));
    assert(fl_allocated(&fl) == fl_capacity(&fl));
    assert(fl_check(&fl) == 0);

    /* Return it all */
    for (int i = 0; i < fl_capacity(&fl); i++) {
        fl_free(&fl, (void *)ptr_buf[i]);
    }

    free(ptr_buf);

    /* All slots are free here */
    assert(cap == fl_available(&fl));
    assert(fl_allocated(&fl) == 0);
    assert(fl_check(&fl) == cap);

    /* Check so our head and tail blocks are intact */
    assert(crc32(headblock, BUFFER_SIZE / 2) == head_crc);
    assert(crc32(tailblock, BUFFER_SIZE / 2) == tail_crc);

    /* Hexdump the heap, free the block and declare victory */
    hexdump(headblock, BUFFER_SIZE * 2, 32);
    free(headblock);
    printf("All tests passed!\n");
    return 0;
}

uint32_t crc32(const uint8_t *data, size_t length) {
    uint32_t crc = 0xFFFFFFFF;
    uint32_t poly = 0x04C11DB7;

    for (size_t i = 0; i < length; i++) {
        crc ^= ((uint32_t)data[i]) << 24;

        for (int j = 0; j < 8; j++) {
            if (crc & 0x80000000) {
                crc = (crc << 1) ^ poly;
            } else {
                crc <<= 1;
            }
        }
    }

    return crc ^ 0xFFFFFFFF;
}