free_list.c

Go to the documentation of this file.

 
#include <kiba/allocators/free_list.h>
 
#include <kiba/core/log.h>
#include <kiba/core/memory.h>
 
#define KB_FL_ALLOC_CONSISTENCY_CHECK 0
 
/* Free list */
 
typedef struct free_list_entry {
    usize                   size;
    struct free_list_entry *next;
} free_list_entry;
 
void free_list_entry_create(free_list_entry *entry, usize data_size);
b8   free_list_insert(free_list_entry **head, usize size, void *at);
b8   free_list_remove(free_list_entry **head, usize size, void **res);
 
#define PTR_COMPARE(ptr1, offset1, op, ptr2, offset2) ((((u8 *) (ptr1)) + (offset1)) op(((u8 *) (ptr2)) + (offset2)))
 
void free_list_entry_create(free_list_entry *entry, usize data_size) {
    entry->size = data_size;
    entry->next = KB_NULL;
    KB_TRACE("created free list with data size {usize} for head {pointer}", data_size, (void *) entry);
}
 
b8 free_list_insert(free_list_entry **head, usize size, void *at) {
    free_list_entry *entry    = *head;
    free_list_entry *previous = KB_NULL;
    free_list_entry *at_entry = at;
    --at_entry;  // recover free_list_entry
    KB_TRACE("trying to add entry with size {usize} at {pointer} to free list for head {pointer}",
             size,
             at,
             (void *) head);
    if (entry == KB_NULL) {
        // list is empty -> create new one
        free_list_entry_create(at_entry, size);
        *head = at_entry;
        return true;
    }
    while (entry != KB_NULL) {
        if (PTR_COMPARE(entry + 1, entry->size, ==, at_entry, 0)) {
            // merge with previous
            KB_TRACE("adding new entry by merging with previous entry");
            entry->size += size + sizeof(free_list_entry);
            // optionally merge with next before returning
            if (entry->next && PTR_COMPARE(entry->next, 0, ==, at, size)) {
                KB_TRACE("additionally merging with next entry");
                entry->size += entry->next->size + sizeof(free_list_entry);
                entry->next = entry->next->next;
            }
            return true;
        }
        if (PTR_COMPARE(entry + 1, entry->size, >, at_entry, 0)) {
            if (PTR_COMPARE(entry, 0, ==, at, size)) {
                // merge with next
                KB_TRACE("adding new entry by merging with next entry");
                at_entry->next = entry->next;
                at_entry->size = size + entry->size + sizeof(free_list_entry);
            } else {
                // needs to create new entry
                KB_TRACE("try creating new entry");
                at_entry->size = size;
                at_entry->next = entry;
            }
            if (previous != KB_NULL) {
                KB_TRACE("adding new entry as part of the existing list");
                previous->next = at_entry;
            } else {
                KB_TRACE("adding new entry as new head of the list");
                *head = at_entry;
            }
            return true;
        }
        previous = entry;
        entry    = entry->next;
    }
    // reached end of the list
    KB_TRACE("adding new entry at the end of the list");
    at_entry->size = size;
    at_entry->next = KB_NULL;
    previous->next = at_entry;
    return true;
}
 
b8 free_list_remove(free_list_entry **head, usize size, void **res) {
    free_list_entry *entry    = *head;
    free_list_entry *previous = KB_NULL;
    KB_TRACE("trying to remove entry with size {usize} from free list for head {pointer}", size, (void *) head);
    while (entry != KB_NULL) {
        if (entry->size == size) {
            // skip entry of size 0, keep it for free operation though
            if (previous != KB_NULL) {
                previous->next = entry->next;
            } else {
                *head = entry->next;
            }
            *res           = entry + 1;
            return true;
        } else if (entry->size > size + sizeof(free_list_entry)) {
            u8 *data_ptr = (void *) (entry + 1);
            data_ptr += entry->size - size;  // use memory at the end of the free space to keep the entry stable
            *res = data_ptr;
            entry->size -= size + sizeof(free_list_entry);
            return true;
        }
        previous = entry;
        entry    = entry->next;
    }
    KB_TRACE("did not find fitting entry in free list");
    return false;
}
 
static void free_list_check_consistency(const char *prefix, struct free_list_entry *head) {
#if KB_FL_ALLOC_CONSISTENCY_CHECK == 1
    KB_DEBUG("checking free list {pointer}", head);
    struct free_list_entry *entry    = head;
    struct free_list_entry *previous = KB_NULL;
    while (entry) {
        KB_DEBUG("{16l:raw_string} entry at {10r:u64} with size {10r:usize} (entry:{pointer}, data:{pointer})",
                 prefix,
                 ((u8 *) entry) - ((u8 *) head),
                 entry->size,
                 entry,
                 entry + 1);
        if (previous && PTR_COMPARE(previous + 1, previous->size, >=, entry, 0)) {
            KB_ASSERT(false, "inconsistent free list entry, size overlaps next entry");
        }
        previous = entry;
        entry    = entry->next;
    }
#else
    UNUSED(prefix);
    UNUSED(head);
#endif
}
 
#undef PTR_COMPARE
 
/* Free list allocator */
 
typedef struct free_list_allocator_block {
    void                             *data;
    usize                             size;
    struct free_list_allocator_block *next;
    free_list_entry                  *free_list;
} free_list_allocator_block;
 
free_list_allocator_block *free_list_allocator_block_create(usize size, free_list_allocator_block *next);
void                       free_list_allocator_block_destroy(free_list_allocator_block *block);
 
free_list_allocator_block *free_list_allocator_block_create(usize size, free_list_allocator_block *next) {
    usize                      block_size = 0;
    usize                      header_offset = sizeof(free_list_allocator_block) + sizeof(free_list_entry);
    free_list_allocator_block *block         = memory_page_allocate(header_offset + size, &block_size);
    if (block == KB_NULL) {
        KB_ERROR("could not allocate memory for free_list_allocator_block");
        return KB_NULL;
    }
    block_size -= header_offset;
    block->data = block + 1;
    block->size = block_size;
    block->next = next;
    block->free_list = block->data;
    free_list_entry_create(block->free_list, block_size);
    return block;
}
 
void free_list_allocator_block_destroy(free_list_allocator_block *block) { memory_page_free(block); }
 
b8 free_list_allocator_create(allocator *alloc, usize size) {
    free_list_allocator_block *block = free_list_allocator_block_create(size, KB_NULL);
    if (block == KB_NULL) {
        KB_ERROR("could not allocate memory for initial free_list_allocator_block");
        return false;
    }
    allocator_implementation(alloc,
                             free_list_allocator_destroy,
                             free_list_allocator_allocate,
                             free_list_allocator_free,
                             free_list_allocator_free_all);
    alloc->state = block;
    KB_TRACE("created free_list_allocator with initial size {usize}", size);
    return true;
}
 
void free_list_allocator_destroy(allocator *alloc) {
    free_list_allocator_block *block      = alloc->state;
    free_list_allocator_block *prev_block = KB_NULL;
    while (block != KB_NULL) {
        KB_TRACE("destroying free_list_allocator_block {pointer} and free_list {pointer}",
                 block,
                 (void *) block->free_list);
        prev_block = block;
        block      = block->next;
        free_list_allocator_block_destroy(prev_block);
    }
    KB_TRACE("destroyed free_list_allocator");
}
 
void *free_list_allocator_allocate(allocator *alloc, usize size) {
    free_list_allocator_block *block      = alloc->state;
    free_list_allocator_block *prev_block = KB_NULL;
    void                      *res        = KB_NULL;
    while (block != KB_NULL) {
        free_list_check_consistency("pre-alloc", block->free_list);
        if (free_list_remove(&block->free_list, size, &res)) {
            free_list_check_consistency("post-alloc-succ", block->free_list);
            break;
        }
        prev_block = block;
        block      = block->next;
    }
    if (res == KB_NULL) {
        KB_TRACE("did not find fitting block, creating new one");
        usize new_size = prev_block->size;
        if (size > new_size) {
            KB_TRACE(
                "new block size {usize} is not enough for requested allocation of {usize} bytes, using the requested "
                "size as new block size",
                new_size,
                size);
            new_size = size;
        }
        free_list_allocator_block *fitting_block = free_list_allocator_block_create(new_size, KB_NULL);
        if (fitting_block == KB_NULL) {
            KB_ERROR("could not allocate memory for free_list_allocator_block");
            return KB_NULL;
        }
        prev_block->next = fitting_block;
        KB_TRACE("created new block to hold {usize} bytes", new_size);
        KB_ASSERT(free_list_remove(&fitting_block->free_list, size, &res),
                  "a created block must be able to find space in its free list");
    }
 
    return res;
}
 
void free_list_allocator_free(allocator *alloc, void *mem, usize size) {
    free_list_allocator_block *block = alloc->state;
    while (block != KB_NULL) {
        u8 *mem_tmp = mem;
        if (mem_tmp > (u8 *) block->data && mem_tmp < (u8 *) block->data + block->size) {
            free_list_check_consistency("pre-free", block->free_list);
            if (!free_list_insert(&block->free_list, size, mem)) {
                KB_WARN("free_list_allocator was not able to track freed memory, leaking memory until destruction");
            }
            free_list_check_consistency("post-free-succ", block->free_list);
            break;
        }
        block = block->next;
    }
}
 
void free_list_allocator_free_all(allocator *alloc) {
    free_list_allocator_block *block = alloc->state;
    while (block != KB_NULL) {
        free_list_entry_create(block->free_list, block->size);
        block = block->next;
    }
    KB_TRACE("reset free_list_allocator");
}