new malloc

#include <basic.h>
#include <debug.h>
#include <stdint.h>
#include <stdio.h>
// #include <stdlib.h>
#include <string.h>
#include <mutex.h>
#include <vmm.h>
#include "malloc.h"

#if X86_64
#define MALLOC_POOL (void*)0xFFFFFF0000000000
#elif I686
#define MALLOC_POOL (void*)0xC0000000
#endif

#define ROUND_UP(x, to) ((x + to-1) & ~(to-1))
#define PTR_ADD(p, off) (void*)(((char*)p) + off)

#define error_printf printf

void* malloc(size_t len);
void* realloc(void* allocation, size_t len);
void free(void* allocation);
void* allogned_alloc(size_t alignment, size_t len);

#define MAGIC_NUMBER_1 (~12L)
#define MAGIC_NUMBER_2 (0xDEADBEEFCAFEBABE)

#define STATUS_FREE  (1)
#define STATUS_INUSE (2)

typedef struct mregion mregion;
struct mregion {
    unsigned long magic_number_1;
    mregion* previous;
    mregion* next;
    unsigned long length;
    int status;
    unsigned long magic_number_2;
};

#define MINIMUM_BLOCK (1 << 8) // 256B - is this too low (or high)?

// don't split a region if we're going to use most of it anyway
// ( don't leave lots of tiny gaps )
int should_split_mregion(mregion* orig, size_t candidiate);

mregion* split_mregion(mregion* orig, size_t split_at);
mregion* merge_mregion(mregion* r1, mregion* r2);

// check magics and status are valid
int validate_mregion(mregion* r);

#define POOL_LENGTH (1 << 24) // 16MB

void* pool = MALLOC_POOL;
mregion* region_0;

void malloc_initialize() {
    region_0 = pool;

    vmm_create_unbacked_range((uintptr_t)pool, POOL_LENGTH, PAGE_WRITEABLE);

    region_0->magic_number_1 = MAGIC_NUMBER_1;
    region_0->previous = NULL;
    region_0->next = NULL;
    region_0->length = POOL_LENGTH - sizeof(mregion);
    region_0->status = STATUS_FREE;
    region_0->magic_number_2 = MAGIC_NUMBER_2;
}

int validate_mregion(mregion* r) {
    return
        r->magic_number_1 == MAGIC_NUMBER_1 &&
        r->magic_number_2 == MAGIC_NUMBER_2 &&
        (r->status & !0x3) == 0;
}

int should_split_mregion(mregion* r, size_t candidate) {
    if (r->length < candidate) {
        // not big enough
        return 0;
    }

    if (r->length - candidate < MINIMUM_BLOCK + sizeof(mregion)) {
        // wouldn't leave enough space
        return 0;
    }
    // should we split in the case that we leave only a 256b hole?
    return 1;
}

mregion* split_mregion(mregion* r, size_t split_at) {
    size_t actual_offset = ROUND_UP(split_at, MINIMUM_BLOCK);

    if (!should_split_mregion(r, actual_offset)) {
        return NULL;
    }

    mregion* new_region = PTR_ADD(r, sizeof(mregion) + actual_offset);
    new_region->magic_number_1 = MAGIC_NUMBER_1;
    new_region->previous = r;
    new_region->next = r->next;
    new_region->length = r->length - actual_offset - sizeof(mregion);
    new_region->status = STATUS_FREE;
    new_region->magic_number_2 = MAGIC_NUMBER_2;

    r->next = new_region;
    r->length = actual_offset;
    if (new_region->next) {
        new_region->next->previous = new_region;
    }

    return new_region;
}

mregion* merge_mregions(mregion* r1, mregion* r2) {
    if (r1->status & STATUS_INUSE || r2->status & STATUS_INUSE) {
        // can't update regions that are in use
        return NULL;
    }

    if (PTR_ADD(r1, sizeof(mregion) + r1->length) != r2) {
        error_printf("tried to merge discontinuous regions (loc compare)\n");
        return NULL;
    }

    if (r2->previous != r1 || r1->next != r2) {
        error_printf("tried to merge discontinuous regions (ptr compare)\n");
        return NULL;
    }

    r1->length += sizeof(mregion) + r2->length;
    r1->next = r2->next;
    if (r1->next) {
        r1->next->previous = r1;
    }

    return r1;
}

void* malloc(size_t len) {
    printf("malloc(%zu)\n", len);
    mregion* cr;
    for (cr=region_0; cr; cr=cr->next) {
        if (cr->status == STATUS_FREE && cr->length >= len)
            break;
    }

    if (!cr) {
        error_printf("no region available to handle malloc(%lu)\n", len);
        return NULL;
    }

    split_mregion(cr, len);

    cr->status = STATUS_INUSE;
    return PTR_ADD(cr, sizeof(mregion));
}

void* realloc(void* allocation, size_t len) {
    if (!allocation) {
        return malloc(len);
    }

    mregion* to_realloc = PTR_ADD(allocation, -sizeof(mregion));
    if (!validate_mregion(to_realloc)) {
        error_printf("invalid pointer passed to realloc: %p\n", allocation);
        return NULL;
    }

    if (len < to_realloc->length) {
        split_mregion(to_realloc, len);
        return allocation;
    }

    size_t old_len = to_realloc->length;

    if (merge_mregions(to_realloc, to_realloc->next)) {
        if (len < to_realloc->length) {
            split_mregion(to_realloc, len);
        }

        return allocation;
    }

    void* new_allocation = malloc(len);
    if (!new_allocation)
        return NULL;
    memcpy(new_allocation, allocation, old_len);
    free(allocation);
    return new_allocation;
}


void* calloc(size_t count, size_t len) {
    void* alloc = malloc(count * len);
    if (!alloc)
        return NULL;

    memset(alloc, 0, len);
    return alloc;
}

void free(void* allocation) {
    if (!allocation) {
        // free(NULL) is a nop
        return;
    }

    mregion* to_free = PTR_ADD(allocation, -sizeof(mregion));
    if (!validate_mregion(to_free)) {
        error_printf("invalid pointer passed to free: %p\n", allocation);
        return;
    }
    to_free->status = STATUS_FREE;

    mregion* freed = to_free;
    if (to_free->previous) {
        freed = merge_mregions(to_free->previous, to_free);
    }
    if (freed && freed->next) {
        merge_mregions(freed, freed->next);
    } else if (!freed && to_free->next) {
        merge_mregions(to_free, to_free->next);
    }

    return;
}


// test stuff

void print_mregion(mregion* r) {
}

void print_pool() {
    printf("region, next, previous, length, status, valid\n");

    mregion* r;
    for (r=region_0; r; r=r->next) {
        printf("%p, %p, %p, %lu, %s, %s\n",
                r, r->next, r->previous, r->length,
                  r->status == STATUS_FREE  ? "free" :
                  r->status == STATUS_INUSE ? "used" : " BAD",
                validate_mregion(r) ? "valid" : "INVALID");
    }
    printf("**\n\n");

    return;
}

void summarize_pool() {
    size_t inuse_len = 0;
    size_t total_len = 0;

    int inuse_regions = 0;
    int total_regions = 0;

    mregion* r;
    for (r=region_0; r; r=r->next) {
        if (r->status == STATUS_INUSE) {
            inuse_len += r->length;
            inuse_regions++;
        }
        total_len += r->length;
        total_regions++;

        if (!validate_mregion(r)) {
            printf("INVALID_REGION: %p\n", r);
        }
    }

    printf("total len: %zu\n", total_len);
    printf("inuse len: %zu\n", inuse_len);
    printf("total regions: %i\n", total_regions);
    printf("inuse regions: %i\n", inuse_regions);
}