Gfrktyl

I've written an implementation of malloc, realloc, and free. I wanted to make a malloc implementation that is sufficiently simple and easy to maintain.

I don't care so much for performance, but I'd like to know if anything stands out that can easily be fixed.

An explanation of how it works is in the source file. Other malloc reviews I've seen on this site use linked lists, but just note that this implementation does not.

The prefix alloy is the name of the project, so if you see it in the global functions, that's what it means and you can ignore it.

Here's malloc.h

#ifndef alloy_malloc_h

#define alloy_malloc_h



#ifdef __cplusplus

extern "C" {

#endif



#ifndef NULL



/** This value represents an invalid memory address.

 * It contains a value of zero, by default. Zero is

 * usually the standard value of a 'null' pointer. */

#define NULL ((void *) 0x00)



#endif



/** This function must be called for the memory

 * allocation functions to work. It tells malloc

 * where it can find extra memory at.

 * @param addr The base address to allocate memory at.

 * @param size The max number of bytes that can be allocated.

 * This must be at least 64 bytes on 64-bit systems and

 * 32 bytes on 32-bit systems.

 * @returns Zero on success, a negative one on failure. */

int alloy_init_heap(void *addr, unsigned long int size);



/** This function allocates a new memory section of a specified size.

 * @param size The number of bytes to allocate.

 * @returns A pointer to the memory section, if one is

 * found that can fit the number of bytes requested.

 * If the memory can't be allocated, then a @ref NULL

 * value is returned instead. */

void *alloy_malloc(unsigned long int size);



/** Resizes an existing memory section that was allocated with @ref alloy_malloc.

 * New memory can also be allocated with this function, by passing @p addr with

 * a value of @ref NULL. The data from the previous section is copied to the new section.

 * @param addr The address of the memory section to resize.

 * @param size The number of bytes to resize the section to.

 * @returns A pointer to the newly allocation memory section.

 * If space could not be found for the new section, then a value

 * of @ref NULL is returned instead and the memory section remains unchanged. */

void *alloy_realloc(void *addr, unsigned long int size);



/** Releases memory previously allocated with @ref alloy_malloc

 * or @ref alloy_realloc. If the memory address passed to this

 * function does not exist within the heap, then this function has no effect.

 * @param addr The address of the memory section to free. */

void alloy_free(void *addr);



#ifdef __cplusplus

} /* extern "C" */

#endif



#endif // alloy_malloc_h

Here's malloc.c

#include "malloc.h"



/* This file contains the malloc implementation for the Alloy project.

 *

 * Here's how it works.

 *

 * The implementation is made up of a 'header' and an allocation table.

 *

 * The header is used for tracking the position of the allocation table

 * entries, then number of allocations, and the size of the heap. The header

 * sits at the very beginning of the heap and remains there for the duration

 * of the library usage.

 *

 * The allocation table is used for keeping track of the memory sections

 * to ensure that they don't overlap. When the heap is first initialized,

 * the allocation table begins immediately after the header. As more allocations

 * are added to the table, it gets resized and moved around the heap. The

 * first two allocations in the allocation table that are made is the heap

 * header allocation and the allocation entry for the allocation table itself.

 * Thus, the allocation table is able to resize itself.

 * */



/** Used for memory sizes. */

typedef unsigned long int size_type;



/** The base address of the heap. */

unsigned char *heap_addr = NULL;



/** A single memory allocation. */

struct allocation {

    /// The memory address that the

    /// allocation is responsible for.

    void *addr;

    /// The number of bytes allocated

    /// for the address.

    size_type size;

};



/** Gives the allocation the highest address value

 * and a size of zero. */

static void mark_allocation_invalid(struct allocation *allocation) {

    allocation->addr = (void *) 0xffffffffffffffff;

    allocation->size = 0;

}



/** Indicates whether or not an allocation is invalid. */

static unsigned int is_invalid_allocation(const struct allocation *allocation) {

    return allocation->addr == ((void *) 0xffffffffffffffff);

}



/** Magic number used for sanity checking (= speed of light in m/s). */

const size_type valid_magic_number = 299792458;



/** Used at the start of the heap

 * to keep track of the allocation table. */

struct header {

    /** Used for verifying that the

     * heap was initialized properly. */

    size_type magic_number;

    /** The array of allocations. */

    struct allocation *allocations;

    /** The number of allocations made. */

    size_type allocation_count;

    /** The size of the heap (including this header.) */

    size_type heap_size;

};



/** Retrieves the header from the heap address.

 * This function also checks to ensure that the

 * heap has been initialized first.

 * @returns A pointer to the header. */

static struct header *get_header() {



    if (heap_addr == NULL) {

        return NULL;

    }



    struct header *header = (struct header *) heap_addr;



    if (header->magic_number != valid_magic_number) {

        return NULL;

    }



    return header;

}



/** Copies memory from one location to another. */

static void alloy_memcpy(void *dst, const void *src, size_type size) {



    unsigned char *d = (unsigned char *) dst;



    const unsigned char *s = (const unsigned char *) src;



    for (size_type i = 0; i < size; i++) {

        d[i] = s[i];

    }

}



/** Performs a single iteration of the bubblesort algorithm,

 * where the sort key is the allocation address. The number of

 * sorted items is returned. */

static size_type single_bubblesort(struct allocation *allocations,

                                   size_type allocation_count) {



    struct allocation *a;

    struct allocation *b;

    struct allocation tmp;



    size_type sorted = 0;



    for (size_type i = 0; (i + 1) < allocation_count; i++) {

        a = &allocations[i];

        b = &allocations[i + 1];

        size_type a_addr = (size_type) a->addr;

        size_type b_addr = (size_type) b->addr;

        if (a_addr > b_addr) {

            tmp.addr = a->addr;

            tmp.size = a->size;

            a->addr = b->addr;

            a->size = b->size;

            b->addr = tmp.addr;

            b->size = tmp.size;

            sorted = 1;

        }

    }



    return sorted;

}



/** Sorts the allocations to have ascending

 * starting addresses. Should be called whenever

 * the allocation table is modified. */

static void sort_allocations() {



    struct header *header = get_header();

    if (header == NULL) {

        return;

    }



    size_type sorted = 0;



    for (;;) {

        sorted = single_bubblesort(header->allocations, header->allocation_count);

        if (!sorted) {

            break;

        }

    }

}



/** Locates an address that will fit the specified size.

 * This function does not reserve the address that is found,

 * it just locates an address that will fit the space requested. */

static void *find_space_for(size_type size) {



    struct header *header = get_header();

    if (header == NULL) {

        return NULL;

    }



    size_type next_addr = (size_type) heap_addr;



    for (size_type i = 0; i < header->allocation_count; i++) {



        struct allocation *allocation = &header->allocations[i];



        size_type allocation_addr = (size_type) allocation->addr;



        if ((next_addr + size) <= allocation_addr) {

            break;

        } else {

            next_addr = allocation_addr + allocation->size;

        }

    }



    if ((next_addr + size) <= (((size_type) heap_addr) + header->heap_size)) {

        return (void *) next_addr;

    }



    return NULL;

}



/** Locates an allocation using iterative binary search algorithm,

 * where the search key is the allocation address. */

static struct allocation *binary_search(struct allocation *allocations,

                                        size_type left_index,

                                        size_type right_index,

                                        size_type addr) {



    while (left_index <= right_index) {



        size_type middle_index = left_index + ((right_index - left_index) / 2);



        size_type candidate_addr = (size_type) allocations[middle_index].addr;



        if (candidate_addr == addr) {

            return &allocations[middle_index];

        } else if (candidate_addr < addr) {

            left_index = middle_index + 1;

        } else {

            right_index = middle_index - 1;

        }

    }



    return NULL;

}



/** Locates the allocation entry for a specified address.

 * If no allocation exists for the specified address,

 * then a null pointer is returned. */

static struct allocation *find_allocation(void *addr) {



    /* Check if addr is NULL so we can just quickly exit. */

    if (addr == NULL) {

        return NULL;

    }



    struct header *header = get_header();



    if (header == NULL) {

        return NULL;

    }



    return binary_search(header->allocations, 0, header->allocation_count, (size_type) addr);

}



/** Creates an allocation entry within the allocation table. */

static struct allocation *create_allocation(void) {



    struct header *header = get_header();



    if (header == NULL) {

        return NULL;

    }



    size_type next_allocations_size = sizeof(struct allocation) * (header->allocation_count + 1);



    struct allocation *next_allocations = find_space_for(next_allocations_size);

    if (next_allocations == NULL) {

        return NULL;

    }



    for (size_type i = 0; i < header->allocation_count; i++) {

        struct allocation *allocation = &header->allocations[i];

        if (allocation->addr == header->allocations) {

            allocation->addr = next_allocations;

            allocation->size = next_allocations_size;

            sort_allocations();

            break;

        }

    }



    alloy_memcpy(next_allocations, header->allocations, sizeof(struct allocation) * header->allocation_count);



    header->allocations = next_allocations;

    header->allocation_count++;



    struct allocation *new_allocation = &next_allocations[header->allocation_count - 1];

    mark_allocation_invalid(new_allocation);

    return new_allocation;

}



/** Removes an invalid allocation from the end of the

 * allocation table, if one is present. */

static void remove_invalid_allocation_if_present(void) {



    struct header *header = get_header();

    if (header == NULL) {

        return;

    }



    if (header->allocation_count <= 0) {

        return;

    }



    struct allocation *last_allocation = &header->allocations[header->allocation_count - 1];

    if (is_invalid_allocation(last_allocation)) {

        header->allocation_count--;

    }

}



int alloy_init_heap(void *addr, unsigned long int size) {



    /** Ensure that the heap given can fit a header and two allocations. */

    if (size < (sizeof(struct header) + (sizeof(struct allocation) * 2))) {

        return -1;

    }



    heap_addr = (unsigned char *) addr;



    /** This creates an allocation table for the heap header.

     * This ensures that memory allocations won't allocate space

     * over the header. */

    struct allocation *first_allocation = (struct allocation *) &heap_addr[sizeof(struct header)];

    first_allocation->addr = heap_addr;

    first_allocation->size = sizeof(struct header);



    /** This creates an allocation entry for the allocation table itself.

     * This ensures that memory isn't allocated over the allocation table

     * and it also allows the allocation table to be resized. */

    struct allocation *second_allocation = first_allocation + 1;

    second_allocation->addr = first_allocation;

    second_allocation->size = sizeof(struct allocation) * 2;



    /** Initialize the header. */

    struct header *header = (struct header *) heap_addr;

    header->magic_number = valid_magic_number;

    header->allocations = first_allocation;

    header->allocation_count = 2;

    header->heap_size = size;



    return 0;

}



void *alloy_malloc(unsigned long int size) {

    return alloy_realloc(NULL, size);

}



void *alloy_realloc(void *addr, unsigned long int size) {



    struct header *header = get_header();

    if (header == NULL) {

        return NULL;

    }



    struct allocation *dst_entry = NULL;



    struct allocation *existing_entry = find_allocation(addr);

    if (existing_entry != NULL) {

        dst_entry = existing_entry;

    } else {

        dst_entry = create_allocation();

        if (dst_entry == NULL) {

            return NULL;

        }

    }



    /* align size to 16 bytes. */

    size = ((size + 15) / 16) * 16;



    void *next_addr = find_space_for(size);

    if (next_addr == NULL) {

        remove_invalid_allocation_if_present();

        return NULL;

    }



    if (existing_entry != NULL) {

        alloy_memcpy(next_addr, existing_entry->addr, existing_entry->size);

    }



    dst_entry->addr = next_addr;

    dst_entry->size = size;



    sort_allocations();



    return next_addr;

}



void alloy_free(void *addr) {



    struct header *header = get_header();

    if (header == NULL) {

        return;

    }



    struct allocation *allocation = find_allocation(addr);

    if (allocation != NULL) {

        mark_allocation_invalid(allocation);

        /** Invalid allocations go to the back

         * of the allocation table when sorted. */

        sort_allocations();

        /** Now that the free'd allocation is at

         * the back of the table, just reduce the

         * allocation count to get rid of it. */

        header->allocation_count--;

    }

}

Here's a test I wrote to verify the functions.

#include "malloc.h"



#include <assert.h>

#include <string.h>



int main(void) {



    /* Initialize the heap. */



    unsigned char heap[1024];



    int err = alloy_init_heap(heap, sizeof(heap));

    assert(err == 0);



    /* Allocate memory that is definitely out of range of

     * the heap size given. Ensure that it fails. */



    unsigned char *failed_malloc = (unsigned char *) alloy_malloc(2048);

    assert(failed_malloc == NULL);



    /* Allocate three ranges, A, B, and C and allocate

     * them on the heap. */



    unsigned char a_expected[32];

    memset(a_expected, 'a', sizeof(a_expected));



    unsigned char b_expected[64];

    memset(b_expected, 'b', sizeof(b_expected));



    unsigned char b_expected_2[128];

    memset(b_expected_2, 'B', sizeof(b_expected_2));



    unsigned char c_expected[128];

    memset(c_expected, 'c', sizeof(c_expected));



    unsigned char *a = (unsigned char *) alloy_malloc(32);

    assert(a != NULL);

    memset(a, 'a', 32);



    unsigned char *b = (unsigned char *) alloy_malloc(64);

    assert(b != NULL);

    memset(b, 'b', 64);



    unsigned char *c = (unsigned char *) alloy_malloc(128);

    assert(c != NULL);

    memset(c, 'c', 128);



    /* Check to ensure that all memory ranges contain the

     * values that were given to them. Make sure they aren't

     * overlapping. */



    assert(memcmp(a, a_expected, sizeof(a_expected)) == 0);

    assert(memcmp(b, b_expected, sizeof(b_expected)) == 0);

    assert(memcmp(c, c_expected, sizeof(c_expected)) == 0);



    /* The remaining space is 832 (1024 - (32 + 64 + 128)),

     * but is should fail due to the memory used for housekeeping. */



    failed_malloc = (unsigned char *) alloy_malloc(832);

    assert(failed_malloc == NULL);



    /* Resize section B, ensure that all sections still contain

     * their values. */



    b = alloy_realloc(b, 128);

    assert(b != NULL);



    assert(memcmp(a, a_expected, sizeof(a_expected)) == 0);

    assert(memcmp(b, b_expected, sizeof(b_expected)) == 0);

    assert(memcmp(c, c_expected, sizeof(c_expected)) == 0);



    /* Use the rest of the space in B, ensure that all sections

     * still contain their values. */



    memset(b, 'B', 128);



    assert(memcmp(a, a_expected, sizeof(a_expected)) == 0);

    assert(memcmp(b, b_expected_2, sizeof(b_expected_2)) == 0);

    assert(memcmp(c, c_expected, sizeof(c_expected)) == 0);



    /* Release all the memory and verify that a sufficiently

     * large memory section can be allocated again (that would

     * otherwise fail.) */



    /* 896 is 1024 - 128. */

    void *large_section = alloy_malloc(896);

    assert(large_section == NULL);



    alloy_free(a);

    alloy_free(b);

    alloy_free(c);



    large_section = alloy_malloc(896);

    assert(large_section != NULL);



    return EXIT_SUCCESS;

}

Here's a test I wrote to benchmark the function (takes 40 seconds on my VM.)

#include "malloc.h"



#include <stdio.h>

#include <stdlib.h>

#include <string.h>



int main(void) {



    /* Initialize the heap (32 MiB). */



    unsigned long int heap_size = 32UL * 1024UL * 1024UL;



    void *heap = malloc(heap_size);

    if (heap == NULL) {

        fprintf(stderr, "Failed to allocate heap space.n");

        return EXIT_FAILURE;

    }



    int err = alloy_init_heap(heap, heap_size);

    if (err != 0) {

        free(heap);

        fprintf(stderr, "Failed to initialize heap.n");

        return EXIT_FAILURE;

    }



    unsigned long int leftover_size = heap_size;



    unsigned long int size_index = 0;



    unsigned long int size_array[8] = {

        8,    16,  32,   64,

        128, 256, 512, 1024

    };



    while (leftover_size > 0) {



        unsigned long int size = size_array[size_index % 8];



        void *addr = alloy_malloc(size);

        if (addr == NULL) {

            break;

        }



        leftover_size -= size;



        size_index++;

    }



    unsigned long int bytes_allocated = heap_size - leftover_size;



    printf("Made %lu allocations.n", size_index);

    printf("Allocated %lu bytes.n", bytes_allocated);

    printf("Used %lu bytes for house keeping.n", leftover_size);



    float space_efficiency = 0.0f;

    space_efficiency += bytes_allocated;

    space_efficiency /= heap_size;

    space_efficiency *= 100.0f;



    printf("Heap space efficiency: %f%%n", space_efficiency);



    free(heap);



    return EXIT_SUCCESS;

}

0x00 can simply be written 0; the hexadecimal notation doesn't buy you anything here.

In your function signatures such as

int alloy_init_heap(void *addr, unsigned long int size);

you should rearrange your code so that you can use your size_type instead of rewriting unsigned long int.

For your structs (allocation, header, etc.) use typedef so that you don't have to re-write struct on instantiation.

In alloy_memcpy, rather than char-by-char copy, consider doing word-by-word copy. 64-bit copies will be much more efficient here.

This loop:

for (;;) {

    sorted = single_bubblesort(header->allocations, header->allocation_count);

    if (!sorted) {

        break;

    }

}

can simply be

while (single_bubblesort(header->allocations, header->allocation_count));

This:

if ((next_addr + size) <= allocation_addr) {

and this:

if ((next_addr + size) <= (((size_type) heap_addr) + header->heap_size)) {

do not need inner parens, due to operator precedence.

Rather than writing unsigned char everywhere, consider using uint8_t from stdint.h.

This:

float space_efficiency = 0.0f;

space_efficiency += bytes_allocated;

space_efficiency /= heap_size;

space_efficiency *= 100.0f;

can simply be

float space_efficiency = bytes_allocated*100. / heap_size;

This array:

unsigned long int size_array[8] = {

    8,    16,  32,   64,

    128, 256, 512, 1024

};

doesn't need to be initialized literally. You can do:

for (int i = 0; i < 8; i++)

    size_array[i] = 8 << i;

Whenever you write 0xffffffffffffffff, you can replace it with -1.

In this function (and similar ones elsewhere):

static struct allocation *create_allocation(void) {

(void) is redundant. Just write ().