How to program a malloc() implementation with correct pointer alignment in C

Question

I'm currently trying to recode my own implementation of malloc() in C language. I followed several tutorials but each time the pointer alignment was incorrect (aligned to a power of 4) but according to the ABI it is necessary for malloc() to return a pointer aligned to a power of 8. So I re-adapted one. I recoded malloc(), free(), calloc(), realloc(), reallocf().

When testing malloc() I get silent errors with valgrind. When testing further (multiple calls to malloc(), realloc(), free()) I get a segfault.

Here's the code:

#include <stdio.h>
#include <unistd.h>
#include <stdint.h>
#include <string.h>

typedef struct block_s *block_t;

    struct block_s {
        size_t size;
        block_t next;
        block_t prev;
        int free;
        void *ptr;
        char data[1];
    };


#define BLOCK_SIZE 36

#define align8(x) (((((x) - 1) >> 3) << 3) + 8)

void *base = NULL;

block_t get_block(void *p)
{
    char *tmp;
    tmp = p;
    return (p = tmp -= BLOCK_SIZE);
}

int valid_addr(void *p)
{
    if (base) {
        if (p > base && p < sbrk(0))
            return (p == (get_block(p))->ptr);
    }
    return (0);
}

block_t fusion(block_t b)
{
    if (b->next && b->next->free) {
        b->size += BLOCK_SIZE + b->next->size;
        b->next = b->next->next;
        if (b->next)
            b->next->prev = b;
    }
    return (b);
}

void split_block(block_t b, size_t s)
{
    block_t new;
    new = (block_t) b->data + s;
    new->size = b->size - s - BLOCK_SIZE;
    new->next = b->next;
    new->prev = b;
    new->free = 1;
    new->ptr = new->data;
    b->size = s;
    b->next = new;
    if (new->next)
        new->next->prev = new;
}

block_t find_block(block_t *last, size_t size)
{
    block_t b = sbrk(0);
    while (b && !(b->free && b->size >= size))
    {
        *last = b;
        b = b->next;
    }
    return (b);
}

block_t extend_heap(block_t last, size_t s)
{
    int64_t sb;
    block_t b;
    b = sbrk(0);
    sb = (size_t) sbrk(BLOCK_SIZE + s);
    if (sb < 0)
        return (NULL);
    b->size = s;
    b->next = NULL;
    b->prev = last;
    b->ptr = b->data;
    if (last) {
        last->next = b;
    }
    b->free = 0;
    return (b);
}

void copy_block(block_t src, block_t dest)
{
    size_t *sdata, *ddata;
    size_t i;
    sdata = src->ptr;
    ddata = dest->ptr;
    for (i = 0; (i * 8) < src->size && (i * 8) < dest->size; i++)
        ddata[i] = sdata[i];
}

void my_free(void *p)
{
    block_t b;
    if (valid_addr(p)) {
        b = get_block(p);
        b->free = 1;
        if (b->prev && b->prev->free) {
            b = fusion(b->prev);
        }
        if (b->next) {
            fusion(b);
        } else {
            if (b->prev)
                b->prev->next = NULL;
            else
                base = NULL;
            brk(b);
        }
    }
}

void *my_malloc(size_t size)
{
    block_t b, last;
    size_t s;
    s = align8(size);
    if (base) {
        last = base;
        b = find_block(&last, s);
        if (b) {
            if ((b->size - s) >= (BLOCK_SIZE + 8))
                split_block(b, s);
            b->free = 0;
        } else {
            b = extend_heap(last, s);
            if (!b)
                return (NULL);
        }
    } else {
        b = extend_heap(NULL, s);
        if (!b)
            return (NULL);
        base = b;
    }
    return (b->data);
}

void *my_calloc(size_t number, size_t size)
{
    size_t *new, s8, i;
    new = my_malloc(number * size);
    if (new) {
        s8 = align8(number * size) << 3;
        for (i = 0; i < s8; i++)
            new[i] = 0;
    }
    return (new);
}

void *my_realloc(void *p, size_t size)
{
    size_t s;
    block_t b, new;
    void *newp;
    if (!p) {
        return (my_malloc(size));
    }
    if (valid_addr(p)) {
        s = align8(size);
        b = get_block(p);
        if (b->size >= s) {
            if (b->size - s >= (BLOCK_SIZE + 8)) {
                split_block(b, s);
            }
        } else {
            if (b->next && b->next->free && (b->size + BLOCK_SIZE + b->next->size) >= 5) {
                fusion(b);
                if (b->size - s >= (BLOCK_SIZE + 8)) {
                    split_block(b, s);
                }
            } else {
                newp = my_malloc(s);
                if (!newp) {
                    return (NULL);
                }
                new = get_block(newp);
                copy_block(b, new);
                my_free(p);
                return (newp);
            }
        }
        return (p);
    }
    return (NULL);
}

void *my_reallocf(void *p, size_t size)
{
    void *newp;
    newp = my_realloc(p, size);
    if (!newp)
        my_free(p);
    return (newp);
}

Here is the malloc's test code :

int main(void)
{
    char *str = my_malloc(15 * sizeof(char));
    str = strcpy(str, "Hello World!\0");
    printf("# Malloc test\nString %p = %s\n", str, str);
    my_free(str);
}

And here's the valgrind report:

==56698== Memcheck, a memory error detector
==56698== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==56698== Using Valgrind-3.21.0 and LibVEX; rerun with -h for copyright info
==56698== Command: ./build/my_malloc
==56698== 
==56698== Invalid write of size 8
==56698==    at 0x1098B3: main (my_malloc.c:214)
==56698==  Address 0x403502d is in the brk data segment 0x4035000-0x4035033
==56698== 
==56698== Invalid read of size 1
==56698==    at 0x4847ED4: strlen (vg_replace_strmem.c:501)
==56698==    by 0x48E36E8: __printf_buffer (vfprintf-process-arg.c:435)
==56698==    by 0x48E3E51: __vfprintf_internal (vfprintf-internal.c:1523)
==56698==    by 0x48D92FE: printf (printf.c:33)
==56698==    by 0x1098D9: main (my_malloc.c:215)
==56698==  Address 0x4035034 is 0 bytes after the brk data segment limit 0x4035034
==56698== 
# Malloc test
String 0x4035028 = Hello World!
==56698== 
==56698== HEAP SUMMARY:
==56698==     in use at exit: 0 bytes in 0 blocks
==56698==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==56698== 
==56698== All heap blocks were freed -- no leaks are possible
==56698== 
==56698== For lists of detected and suppressed errors, rerun with: -s
==56698== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

Also, I noticed that Valgrind returned erroneous values (on allocated and freed memory) during my various tests... I have no hypotheses on this subject.

The choice not to use mmap() is deliberate.

I'd also like to point out that my dynamic memory allocator is intended for an environment where the standard C library is absent.

My hypothesis is that I'm miscalculating the block size and/or misaligning my pointers.

By changing the BLOCK_SIZE to 44, the test with a simple malloc / free works, but as soon as there are several it segfault.

Can you tell me how to make this allocator work?

Thanks in advance