malloc() and free() for Linux with system calls

Question

I have written an implementation of malloc() and free() for Linux using the sbrk() system call.

When memory is requested, it checks if there is a large enough chunk available already, if there is then that gets returned to the user, otherwise a new block of memory will be requested from the kernel. When memory is free'd the block is marked as such and kept for later, and adjacent free blocks of memory are merged together. If there is a free block at the end of the heap that is larger than the size of a page then the largest possible multiple of page size bytes is returned to the kernel.

This is the first version of this code and my first time working with system calls, as such I have kept things fairly simple and not included padding or a realloc() implementation. Both of these will feature in the next version along with any improvements suggested here.

malloc.h

#ifndef _MALLOC_H
#define _MALLOC_H

#include <stdbool.h>

#define PAGE_SIZE 4096

typedef struct mem_header mem_header;

struct mem_header {
    size_t size;
    bool free;
    mem_header * prev;
    mem_header * next;
};

void * _malloc(size_t size);
void _free(void * ptr);

#endif

malloc.c

#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include "malloc.h"

static inline void eat_next_block(mem_header * header_ptr);

mem_header * head_ptr = NULL;
mem_header * tail_ptr = NULL;

void * _malloc(size_t size)
{
    if(!size)
        return NULL;

    bool heap_empty = false;
    size_t additional_space = 0;

    if(!head_ptr) {
        /* Try and get the base pointer for the heap, as it is defined sbrk(0) could suprisingly fail */
        if((head_ptr = tail_ptr = sbrk(0)) == (void *) -1)
            return NULL;

        heap_empty = true;
    } else {
        /* Try and find enough free space to give the user */
        for(mem_header * heap_ptr = head_ptr; heap_ptr; heap_ptr = heap_ptr->next) {
            if(heap_ptr->free && heap_ptr->size >= size + sizeof(mem_header)) {
                /* Set up free block, if there is space for one */
                if(heap_ptr->size > size + 2 * sizeof(mem_header)) {
                    mem_header * next_block = (mem_header *)((char *) heap_ptr + size + sizeof(mem_header));
                    next_block->size = heap_ptr->size - size - sizeof(mem_header);
                    next_block->free = true;
                    next_block->prev = heap_ptr;
                    next_block->next = heap_ptr->next;
                    heap_ptr->next = next_block;
                } else {
                    size = heap_ptr->size;
                }

                /* Configure newly allocated block */

                heap_ptr->size = size;
                heap_ptr->free = false;

                if((tail_ptr == heap_ptr) && heap_ptr->next)
                    tail_ptr = heap_ptr->next;

                /* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
                return (void *)((char *) heap_ptr + sizeof(mem_header));
            }
        }

        /* If we have a free block at the end that isn't large enough we can subtract its size from our allocation requirement */
        if(tail_ptr->free)
            additional_space = tail_ptr->size + sizeof(mem_header);
    }

    /* Determine how much we need to grow the heap by, alligned to a multiple of PAGE_SIZE bytes */

    size_t block_size = size + sizeof(mem_header) - additional_space;

    if(block_size % PAGE_SIZE != 0)
        block_size += PAGE_SIZE - (block_size % PAGE_SIZE);

    /* Grow the heap */

    if(sbrk(block_size) == (void *) -1)
        return NULL;

    /* Configure the memory block to be returned */

    if(heap_empty) {
        tail_ptr->prev = NULL;
    } else if(!tail_ptr->free) {
        mem_header * tail_ptr_temp = tail_ptr;
        tail_ptr->next = (mem_header *)((char *) tail_ptr + tail_ptr->size + sizeof(mem_header));
        tail_ptr = tail_ptr->next;
        tail_ptr->prev = tail_ptr_temp;
    }

    tail_ptr->next = NULL;
    tail_ptr->free = false;
    tail_ptr->size = size;

    /* Configure any free space at the top of the heap */

    void * return_ptr = (void *)((char *) tail_ptr + sizeof(mem_header));

    size_t leftover = block_size + additional_space - (size + sizeof(mem_header));

    if(leftover > sizeof(mem_header)) {
        mem_header * tail_ptr_temp = tail_ptr;
        tail_ptr->next = (mem_header *)((char *) tail_ptr + size + sizeof(mem_header));
        tail_ptr = tail_ptr->next;
        tail_ptr->free = true;
        tail_ptr->prev = tail_ptr_temp;
        tail_ptr->next = NULL;
        tail_ptr->size = leftover - sizeof(mem_header);
    } else {
        tail_ptr->size += leftover;
    }

    return return_ptr;
}

void _free(void * ptr)
{
    if(!ptr)
        return;

    mem_header * header_ptr = (mem_header *) ptr;
    header_ptr--;

    if(header_ptr->free)
        return;

    header_ptr->free = true;

    /* If there is a free block in front then consume it */

    if(header_ptr->next && header_ptr->next->free)
        eat_next_block(header_ptr);

    /* If there is a free block directly behind then jump to it and consume the block infront */

    if(header_ptr->prev && header_ptr->prev->free) {
        header_ptr = header_ptr->prev;
        eat_next_block(header_ptr);
    }

    /* If there is a sufficient amount of memory at the end of the heap, return it to the kernel */

    if(!header_ptr->next && header_ptr->size + sizeof(mem_header) >= PAGE_SIZE) {
        size_t leftover = (header_ptr->size + sizeof(mem_header)) % PAGE_SIZE;
        size_t excess = header_ptr->size + sizeof(mem_header) - leftover;

        if(!header_ptr->prev) {
            head_ptr = tail_ptr = NULL;
        } else {
            header_ptr->prev->size += leftover;
            header_ptr->prev->next = NULL;
        }

        sbrk(-excess);
    }

    return;
}

static inline void eat_next_block(mem_header * header_ptr)
{
    header_ptr->size += header_ptr->next->size + sizeof(mem_header);
    header_ptr->next = header_ptr->next->next;

    if(header_ptr->next)
        header_ptr->next->prev = header_ptr;

    return;
}

malloc_test.c

#include <unistd.h>
#include <stdio.h>
#include "malloc.h"

#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*(x)))

int main()
{
    char * mem_block[4];
    char * initial_break = sbrk(0);
    size_t alloc_size[4] = { 8192, 16384, 405, 32768 };

    for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++) {
        if(!(mem_block[i] = _malloc(alloc_size[i] * sizeof(char)))) {
            fprintf(stderr, "Error: Could not allocate memory!\n");
            return -1;
        }
    }

    char * final_malloc_break = sbrk(0);

    for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++)
        for(size_t j = 0; j < alloc_size[i]; j++)
            mem_block[i][j] = 'a';

    _free(mem_block[1]);
    _free(mem_block[0]);
    _free(mem_block[3]);
    _free(mem_block[2]);

    char * final_free_break = sbrk(0);
    size_t total_allocated = (size_t) final_malloc_break - (size_t) initial_break;
    size_t excess_pages = ((size_t) final_free_break - (size_t) initial_break) / PAGE_SIZE;

    printf("\n\tHeap Break Positions\n\nInitial break:\t\t%p\nFinal allocation break:\t%p\nFinal free break:\t%p\n\n", initial_break, final_malloc_break, final_free_break);

    if(excess_pages)
        printf("Error: %zu pages were not free'd\n", excess_pages);
    else
        printf("All allocated pages free'd\n");


    printf("Allocated %zu bytes (%zu pages)\n", total_allocated, total_allocated / PAGE_SIZE);

    return 0;
}

All code was compiled with gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) and tested on Debian GNU/Linux 9.5 (stretch) with the command gcc malloc.c malloc_test.c -o malloc -Wall -Wextra -Wpedantic

Note: This code was designed to fulfill a specification for one of my classes, which included a page size of 4096 bytes and function names starting with underscores. I was unaware about the portability concerns arising from these and even though it wasn't a tag, portability is something I definitely want to know about

Answer 1

Names beginning with _ are reserved for the implementation; I'm surprised that -Wpedantic doesn't help with this!

Include what you use - it helps if your implementation and test program include malloc.h before any standard headers. In this case, it's depending on <stddef.h> (or one of the other headers which define size_t).

With -Wconversion, I get a couple of warnings:

206988.c:92:13: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
     if(sbrk(block_size) == (void *) -1)
             ^~~~~~~~~~
206988.c: In function ‘_free’:
206988.c:169:14: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
         sbrk(-excess);
              ^~~~~~~

The first warrants an explicit cast to draw attention. The second of these could be an error; we want to cast before negating:

         sbrk(-(intptr_t)excess);

---

#define PAGE_SIZE 4096

Although that's a common page size, this assumption does make your code less portable. You might be able to find it available in system headers (I can't remember where, if so); it certainly makes sense to guard it so it can be overridden from the compile command:

#ifndef PAGE_SIZE
#define PAGE_SIZE 4096
#endif

---

I don't see any attention to alignment - you do need to ensure that the result of malloc() is suitably aligned for all types. You might be testing on a platform that compensates for unaligned access with just a performance drop - on other systems, you might get a bus error or simply unexpected results.

---

The linear search is going to be very inefficient after a few allocations. Real implementations have several lists, holding different size blocks.

---

There's no need for the (void*) cast here:

        /* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
        return (void *)((char *) heap_ptr + sizeof(mem_header));

Since all pointers convert implicitly to void*, that becomes simply

            /* Add enough bytes for a header */
            return (char*)heap_ptr + sizeof (mem_header);

You might even get away with

            /* Advance pointer beyond the header before passing to user */
            return heap_ptr + 1;

Similarly,

    void * return_ptr = tail_ptr + 1;

---

In the case where we called sbrk() to create more memory, it might make sense to simply add the new memory to the start of free list and immediately re-enter malloc() (which of course will now be able to satisfy the request). That way, there's a single path for successful allocations, which might be handy if you want to "colour" the memory according to its status, for debugging.

It may be necessary to call eat_next_block to join a final free block with newly-created address space; I couldn't quite see how this is done at present, and the test code doesn't exercise that path.

---

Some minor bits in the test program:

• sizeof (char) is always 1, since results are in units of char. So multiplying by that is pointless.
• We can use ptrdiff_t for the result of pointer subtraction, instead of casting to size_t first (where intptr_t would be safer).

• This is a convoluted way to write memset(mem_block[i], 'a', alloc_size[i]):

  for(size_t j = 0; j < alloc_size[i]; j++)
      mem_block[i][j] = 'a';
  

(But thank you for sharing the test program - it really makes reviewing easier).

Answer 2

size + sizeof(mem_header) assumes correct alignment

Memory management functions

The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement C11 §7.22.3 1

The returned pointer from _malloc() needs to meet the fundamental alignment requirement and it is not known the struct mem_header meets that. So possibly sizeof(mem_header) + something_more + size is needed. Then (char *) heap_ptr + sizeof(mem_header) will work per the C spec. @Peter Cordes

With C11, this is easy with _Alignas and max_align_t to insure struct mem_header is aligned well.

An object type imposes an alignment requirement on every object of that type: stricter alignment can be requested using the _Alignas keyword. §6.2.8 1

struct _Alignas(max_align_t) mem_header {
  size_t size;
  bool free;
  mem_header * prev;
  mem_header * next;
};

A pre-C11 approach. Align for the widest base types. The may cause super alignment.

union my_wide_union {
  int (*foo)();
  void *v;
  double d;
  long l;
  // for C99
    long double ld;
    uintmax_t um;
    long double _Complex z; // for select C99 or later
};

union mem_header {
  union my_wide_union dummy;
  struct {
    size_t size;
    bool free;
    mem_header * prev;
    mem_header * next;
  }
};

---

Another alignment issue

The size requested also needs to be a multiple of alignof(max_align_t). Recommend

size_t padding = size % alignof(max_align_t);
if (padding) size += alignof(max_align_t) - padding;

---

Prevent overflow

//if(!size)
if(size == 0 || size > SIZE_MAX - sizeof(struct mem_header)) {
    return NULL;
}