malloc() and free() implementation

Question

I'm looking for a code review of my custom memory allocation library (written for educational purposes), which includes malloc(), calloc(), realloc(), and free() functions.

Review Goals:

1. Does the code ensure that the pointers returned by *alloc() are properly aligned for all types, as required by C standards, to avoid potential undefined behavior?
2. Does any part of my code invokes undefined behavior?
3. General coding comments, style, etc.

Code:

liballoc.h:

#ifndef LIBALLOC_H
#define LIBALLOC_H

/**
*   \brief      The **malloc** function allocates space for an object whose size is specified by *size* 
*               and whose value is indeterminate.
*   \param      size - The size of the object to be allocated.
*   \return     The **malloc** function returns either a null pointer or a pointer to the allocated
*               space. If the size of the space requested is zero, a null pointer is returned.
*/
void *malloc(size_t size);

/**
*   \brief      The **calloc** function allocates space for an array of *nmemb* objects, each of whose size 
*               is *size*. The space is initialized to all bits zero.      
*   \param      nmemb - The number of objects.
*   \param      size  - The size of each object.
*   \return     The **calloc** function returns either a null pointer or a pointer to the allocated space.
*               If the size of the space requested is zero, a null pointer is returned.
*/
void *calloc(size_t nmemb, size_t size);

/**
*   \brief      The **realloc** function deallocates the old object pointed to by *ptr* and returns a pointer to 
*               a new object that has the size specified by *size*. The contents of the new object shall be 
*               the same as that of the old object prior to deallocation, upto the lesser of the new and 
*               old sizes. Any bytes in the new object beyond the size of the old object have indeterminate 
*               values.
*
*       If *ptr* is a null pointer,the **realloc** function behaves like the **malloc** function for the specified *size*.
*       Otherwise, if *ptr* does not match a pointer earlier returned by a memory management function, or if the
*       space has been deallocated by a call to the **free** or **realloc** function, the behavior is undefined. 
*       If *size* is nonzero and memory for the new object is not allocated, the old object is not deallocated.
*       If *size* is zero and memory for the new object is not allocated, the old object is not deallocated,
*       and its value shall be unchanged.
*
*   \param      ptr   - A pointer to the object to be reallocated.
*   \param      size  - The new size.
*   \return     The **realloc** function returns a pointer to the new object, or a null pointer if the new object
*               if the new object has not been allocated. 
*              
*/
void *realloc(void *ptr, size_t size);

/**
*   \brief      The **free** function causes the space pointed to by *ptr* to be deallocated, that is, made
*               unavailable for further allocation. If *ptr* is a null pointer, no action occurs. Otherwise, 
*               if the argument does not match a pointer earlier returned by a memory management function, 
*               or if the space has been deallocated by a call to **free**, the behaviour is undefined.
*   \param      ptr - A pointer to the object to be deallocated.
*   \return     The **free** function returns no value.
*/
void free(void *ptr);

#endif                          /* LIBALLOC_H */

liballoc.c:

#ifdef _POSIX_C_SOURCE
#undef _POSIX_C_SOURCE
#endif

#ifdef _XOPEN_SOURCE
#undef _XOPEN_SOURCE
#endif

#define _POSIX_C_SOURCE 200819L
#define _XOPEN_SOURCE   700
#define _DEFAULT_SOURCE 

#include <unistd.h>
#include <pthread.h>

#include <stdlib.h>
#include <stddef.h>
#include <stdalign.h>
#include <errno.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

#include "liballoc.h"

#define MALLOC_LOCK()               (pthread_mutex_lock (&global_malloc_lock))
#define MALLOC_UNLOCK()             (pthread_mutex_unlock (&global_malloc_lock))
#define CHUNK_SIZE(chunk)           ((chunk)->size)
#define NEXT_CHUNK(chunk)           ((chunk)->next)
#define IS_CHUNK_FREE(chunk)        ((chunk)->is_free)
#define MARK_CHUNK_FREE(chunk)      ((chunk)->is_free = true)
#define MARK_CHUNK_NONFREE(chunk)   ((chunk)->is_free = false)
#define SET_CHUNK_SIZE(chunk, size) ((chunk)->size = (size))
#define SET_NEXT_CHUNK(chunk, val)  ((chunk)->next = (val))
#define SBRK_FAILED                 ((void *) -1)

/* The C Standard states that 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. 
 */
typedef struct header {
    _Alignas (max_align_t) struct header *next;
    size_t size;
    bool is_free;
} header_t;

static header_t *head, *tail;
static pthread_mutex_t global_malloc_lock;

static header_t *get_free_block(size_t size)
{
    /* Ascertain if there's a free block that can accommodate requested size. */
    for (header_t * curr = head; curr; curr = NEXT_CHUNK(curr)) {
        if (IS_CHUNK_FREE(curr) && CHUNK_SIZE(curr) >= size) {
            return curr;
        }
    }
    return NULL;
}

void *malloc(size_t size)
{
    /* The C Standard states that if the size of the space requested is zero, 
     * the behavior is implementation-defined: either a null pointer is returned
     * to indicate an error, or the behavior is as if the size were some non zero
     * value, except that the returned pointer shall not be used to access an object.
     * We shall opt for the former. 
     */
    if (!size || size > SIZE_MAX - sizeof (header_t)) { /* Prevent overflow. */
        return NULL;
    }

    MALLOC_LOCK();
    header_t *header = get_free_block(size);

    if (header) {
        /* We have an apt free block. */
        MARK_CHUNK_NONFREE(header);
        MALLOC_UNLOCK();
        return header + 1;
    }

    /* The size requested needs to be a multiple of alignof (max_align_t). */
    size_t const padding = size % alignof (max_align_t);

    if (padding) {
        size += alignof (max_align_t) - padding;
    }

    intptr_t const total_size = (intptr_t) (sizeof (header_t) + size);
    void *const chunk = sbrk(total_size);

    if (chunk == SBRK_FAILED) {
        MALLOC_UNLOCK();
        return NULL;
    }

    header = chunk;
    SET_CHUNK_SIZE(header, size);
    MARK_CHUNK_NONFREE(header);
    SET_NEXT_CHUNK(header, NULL);

    if (!head) {
        head = header;
    }

    if (tail) {
        SET_NEXT_CHUNK(tail, header);
    }

    tail = header;
    MALLOC_UNLOCK();
    return header + 1;
}

void *calloc(size_t nmemb, size_t size)
{
    if (!nmemb || !size) {
        return NULL;
    }
    
    if (size < SIZE_MAX / nmemb) {      /* Allocation too big. */
        return NULL;
    }

    size *= nmemb;
    void *const chunk = malloc(size);

    if (!chunk) {
        return NULL;
    }

    return memset(chunk, 0X00, size);
}

void *realloc(void *ptr, size_t size)
{
    if (!ptr || !size) {
        return malloc(size);
    }

    const header_t *const header = (header_t *) ptr - 1;

    if (CHUNK_SIZE(header) >= size) {
        return ptr;
    }

    void *const ret = malloc(size);

    if (ret) {
        /* Relocate the contents to the new chunkier chunk and 
         * free the old chunk.
         */
        memcpy(ret, ptr, CHUNK_SIZE(header));
        free(ptr);
    }

    return ret;
}

void free(void *ptr)
{
    if (!ptr) {
        return;
    }

    MALLOC_LOCK();
    header_t *const header = (header_t *) ptr - 1;

    /* Get a pointer to the current program break address. 
     */
    const void *const prog_brk = sbrk(0);

    /* Ascertain whether the block to be freed is the last one in the
     * list. If so, shrink the size of the heap and release the memory
     * to the OS. Else, keep the block but mark it as free for use. 
     */
    if ((char *) ptr + CHUNK_SIZE(header) == prog_brk) {
        if (head == tail) {
            head = tail = NULL;
        } else {
            for (header_t * tmp = head; tmp; tmp = NEXT_CHUNK(tmp)) {
                SET_NEXT_CHUNK(tmp, NULL);
                tail = tmp;
            }
        }

        /* sbrk() with a negative argument decrements the program break,
         * which releases memory the memory back to the OS.
         */
        sbrk((intptr_t) (0 - sizeof (header_t) - CHUNK_SIZE(header)));

        /* This lock does not ensure thread-safety, for sbrk() itself
         * is not thread-safe.
         */
        MALLOC_UNLOCK();
        return;
    }

    MARK_CHUNK_FREE(header);
    MALLOC_UNLOCK();
}

makefile:

CFLAGS  := -s
CFLAGS  += -std=c2x
CFLAGS  += -no-pie
#CFLAGS  += -g3
#CFLAGS  += -ggdb
CFLAGS  += -Wall
CFLAGS  += -Wextra
CFLAGS  += -Warray-bounds
CFLAGS  += -Wconversion
CFLAGS  += -Wmissing-braces
CFLAGS  += -Wno-parentheses
CFLAGS  += -Wno-format-truncation
CFLAGS  += -Wpedantic
CFLAGS  += -Wstrict-prototypes
CFLAGS  += -Wwrite-strings
CFLAGS  += -Winline
CFLAGS  += -O2

NAME    := liballoc_$(shell uname -m)-$(shell uname -s)
LIBDIR  := bin
SLIB    := $(LIBDIR)/$(NAME).a
DLIB    := $(LIBDIR)/$(NAME).so
SRCS    := $(wildcard src/*.c)
OBJS    := $(patsubst src/%.c, obj/%.o, $(SRCS)) 

all: $(SLIB) $(DLIB)

$(SLIB): $(OBJS)
    $(AR) $(ARFLAGS) $@ $^ 

$(DLIB): $(OBJS)
    $(CC) $(CFLAGS) -fPIC -shared $(SRCS) -o $@

obj/%.o: src/%.c
    $(CC) $(CFLAGS) -c $< -o $@

clean:
    $(RM) -rf $(OBJS) 

fclean:
    $(RM) $(SLIB) $(DLIB)

.PHONY: fclean clean all
.DELETE_ON_ERROR:

Answer 1

Documentation:

Be more definite in your descriptions. Does the null pointer returned on requesting zero bytes indicate a failure?

In that case, shorter and unambiguous: "Returns a pointer to the allocated space or a null pointer on failure. Requesting zero bytes always fails."

In the other case, consider this: "Returns a pointer to the allocated space or a null pointer. Requesting zero bytes always succeeds with a null pointer."

Admittedly, that only really gets important when we get to realloc, but it should be consistent throughout: "If *size* is zero and memory for the new object is not allocated, the old object is not deallocated, and its value shall be unchanged."
What? Can we allocate zero bytes? Can/Will that result in a null pointer? Will that indicate success, failure, or Schrödinger?

Also, can shrinking fail? Will it ever free memory?

As the documentation should stand alone, I have ignored the implementation to this point.

---

Tests

Are very much missing.
No wonder the next section has big items.

Implementation bug:

1. You are off by the padding in your implementation of malloc(). size <= SIZE_MAX - sizeof(header_t) still allows size + padding > SIZE_MAX - sizeof(header_t), causing you to pass 0 to sbrk() and assume it got SIZE_MAX + 1 bytes, though the function just returned the current value.

2. Did you try out calloc?
   Your second check goes in the wrong direction.

Implementation:

1. Using macros for the locking allows easy removal of same, so can be justified.
   It allows for easy adoption of the same algorithm for single-threaded and low-contention multi-threaded use.

2. The rest of those macros, used for operations on chunks, just obscure the code though. Best to get rid of the lot.
   Point of fact, I gave up digging into free and thus overlooked another bug Toby Speight found.

3. Consider mmap for private anonymous pages (and mremap for realloc) instead of brk for additional memory. It's the modern approach for good reason, namely playing nicely with ASLR, and still working if there is something in the way of a straight expansion.

   Admittedly, as it works with page-size granularity, it makes invest ing into splitting and coalescing blocks that much more urgent.

4. If you free the last chunk requested from the OS you haven't yet returned, you return it. But all the free chunks next to it will be kept...

5. Consider a uniform limit on the line length, preferably equal to the customary 80.
   Vertical scrolling is bad enough for comprehension, but horizontal scrolling is orders of magnitude worse.
   The makefile already conforms, the implementation file is wrapped just above, but the header file is wrapped significantly later...

Answer 2

Macros

The implementation uses a lot of macros that would be better as functions/constants, or even open-coded.

This one in particular is problematic:

#define SET_CHUNK_SIZE(chunk, size) ((chunk)->size = (size))

I don't think you intended the structure member to be substituted.

---

calloc()

In the implementation of calloc(), why do we return a null pointer when the requested size is less than the maximum allocation?

I would have expected

    if (size >= SIZE_MAX / nmemb) {
//          🔺🔺
        return NULL;
    }

---

0X00 is an unusual spelling of the constant 0. Don't be unconventional without good reason.

---

free()

We have a loop here that will terminate after its first iteration:

        for (header_t * tmp = head; tmp; tmp = NEXT_CHUNK(tmp)) {
            SET_NEXT_CHUNK(tmp, NULL);
            tail = tmp;
        }

It looks like it breaks the list invariants, too.

---

Algorithm

The first-fit algorithm without splitting blocks and the global, unsorted singly-linked list won't give great performance in real applications, nor will the single global lock. There's a lot still to do if you want to make your implementation fast and space-efficient. In particular, consider

• per-thread free-lists (can be accessed without taking the global lock),
• free-lists for blocks in different size ranges (to reduce memory wasted in over-allocation),
• merging freed blocks with free neighbours (to reduce fragmentation)
• change from sbrk to mmap (to allow return of memory from positions other than last, and to work better with ASLR, and to better support per-thread allocation).

Answer 3

Makefile issues.

CFLAGS belongs to the user or distro, yet you're assigning important options into it.

If you have this:

CFLAGS  += -std=c2x

and someone runs make CFLAGS=-O2, your assignment will be ignored, and that c2x dialect won't be selected.

Put your necessary flags into another variable which is referenced in your build recipes, after CFLAGS.

The $(shell uname -m)-$(shell uname -s) trick is hostile to cross-compiling. You're picking up the build machine attributes, not those of the target machine. If you really need the target machine info interpolated into the library name, consider getting it from the compiler specified as $(CC), using the -dumpmachine gcc option:

$ gcc -dumpmachine
i686-linux-gnu

I would just have a regular old fixed name. A user building the library for several different architectures should use separate build directories. It's a packaging issue. *Don't turn important names, like those of the very components you are building, into moving targets!!!

Linking requires LDFLAGS and LDLIBS, not CFLAGS.

$(CC) $(LDFLAGS) $(OBJS) $(LDLIBS) -o whatever

Distro builds specify custom things in these variables.

-fPIC is too late in the linking command line! Code must be compiled position-independent; if you need -fPIC, it has to be in the .c to .o recipe!

Answer 4

Conformance

It is undefined behavior in C to redefine malloc. Choose different names for all your allocator functions, so that your library can be used in a hosted program that already has a C library with malloc.

In the GNU/Linux environment, executables can replace library functions. But still, that foists a big hammer onto the user: every call in every part of their program, plus libraries the program uses, will be routed to the replacement malloc.

If the functions have alternative names, the developer can pick and choose which parts of their program are retargeted to your allocator.

Your header file could provide a switching mechanism between the C library malloc and your routines.

#ifdef XMALLOC_ENABLED
#define xmalloc(size) xmalloc_impl(size)
//...
#else
#define xmalloc(size) malloc(size)
//...
#endif

or something along those lines.

Answer 5

User Debug Idea 1

On malloc(), free(), randomize or fill user data with a garbage pattern to help detect uninitialized malloc() or after free() data usage, perhaps only available in DEBUG mode.

User Debug Idea 2

In writing ones own *alloc()/free() consider adding a frame check, perhaps only available in DEBUG mode.

// Presently
[header][user data](padding)
// Change to 
[header][user data][footer](padding)

The footer consists of a complement copy of the size_t size and is set/accessed via memcpy() as it is unaligned.

On free(),the consistency of the sizes are compared to help detect user buffer overrun. If inconsistent, exit with an error message.

An auxiliary function int alloc_fram_check(ptr) may then be useful for intermediate (before the free()) testing.