Custom malloc implementation

Question

I have a malloc() implementation that relies purely on mmap. I'm fairly sure that it doesn't overwrite any of the internal structures or have any other breaking issues, but I'm not totally sure about that.

Some details:

• __PTRx__ (where x is 16, 32, or 64) is defined when a pointer is x bits in size.
• I would appreciate any notes as to if this isn't ISO C or POSIX-compatible.
• I'm going for compiled code-size.
• Please, no notes on goto.

Here's the code:

allocation.c:

#include <unistd.h>
#include <stddef.h>
#include <sys/mman.h>

#include "malloc.h"

int __get_next_allocation(size_t size)
{
    size_t ctr = 0;
    int found_allocation = 0;
    struct allocation_info *tmp_alloc = NULL;
    struct malloc_chunk *tmp_chnk = NULL;

    if(!__mallchunk)
        if(__get_next_chunk())
            return -1;

    if(!__allocinfo)
        __allocinfo = __mallchunk->start;

    tmp_alloc = __allocinfo;
    tmp_chnk = __mallchunk;

    while(tmp_chnk->prev != NULL)
        tmp_chnk = tmp_chnk->prev;

    for(ctr = 0;
        ctr < tmp_chnk->alloc_cnt && tmp_alloc;
        ctr++, tmp_alloc = tmp_alloc->next)
    {
        if( tmp_alloc->free &&
            tmp_alloc->size >= size )
        {
            found_allocation = 1;
            tmp_alloc->prev->next = tmp_alloc->next;
            tmp_alloc->next->prev = tmp_alloc->prev;
            tmp_alloc->next = NULL;
            break;
        }
    }

    if(!found_allocation)
    {
        if((size_t)(__allocinfo->start - __mallchunk->start)
                > ((CHUNK_SIZE - size) - sizeof(*tmp_alloc)))
        {
            if(__get_next_chunk())
                return -1;
            tmp_alloc = __mallchunk->start;
        }
        else
        {
            tmp_alloc = __allocinfo->start +
                        __allocinfo->size;
        }

        tmp_alloc->start = (void *)tmp_alloc
                    + sizeof(*tmp_alloc);
        tmp_alloc->next = NULL;
    }
    __allocinfo->next = tmp_alloc;
    __allocinfo->next->prev = __allocinfo;
    __allocinfo = __allocinfo->next;
    __allocinfo->size = size;
    __allocinfo->free = 0;
    __mallchunk->alloc_cnt++;
    return 0;
}

calloc.c:

#include <stddef.h>
#include <stdlib.h>
#include <string.h>

void *calloc(size_t nmemb, size_t size)
{
    void *ret;

    if(size % 2) size++;
    if(nmemb % 2) nmemb++;

    size *= nmemb;
    ret = malloc(size);

    if(!ret) return NULL;
    return memset(ret, 0, size);
}

chunk.c:

#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>
#include <stddef.h>
#include <stdlib.h>
#include <sys/mman.h>

#include "malloc.h"

int __get_next_chunk(void)
{
    struct malloc_chunk *mallchunk = mmap(NULL,
                                    CHUNK_SIZE,
                        PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS,
                                            -1,
                                            0);
    if(mallchunk == MAP_FAILED)
    {
        errno = ENOMEM;
        return -1;
    }

    if (!__mallchunk)
    {
        __mallchunk = mallchunk;
        __mallchunk->chunk_cnt = 0;
        __mallchunk->alloc_cnt = 0;
        __mallchunk->prev = NULL;
        __mallchunk->next = NULL;
    }
    else
    {
        __mallchunk->chunk_cnt++;
        __mallchunk->next = mallchunk;
        __mallchunk->next->chunk_cnt =
                __mallchunk->chunk_cnt;
        __mallchunk->next->prev = __mallchunk;
        __mallchunk = __mallchunk->next;
        __mallchunk->alloc_cnt = 0;
        __mallchunk->next = NULL;
    }

    __mallchunk->start = (void *)__mallchunk +
                        sizeof(*__mallchunk);
    return 0;
}

free.c:

#include "malloc.h"

#include <stdlib.h>
#include <string.h>

void free(void *ptr)
{
    struct allocation_info *tmp_allinfo = __allocinfo;

    if(!ptr) return;

    while(tmp_allinfo->prev)
        tmp_allinfo = tmp_allinfo->prev;

    while(tmp_allinfo && tmp_allinfo->start != ptr)
        tmp_allinfo = tmp_allinfo->next;

    if(!tmp_allinfo) return;

    memset(tmp_allinfo->start, 0, tmp_allinfo->size);
    tmp_allinfo->free = 1;
}

malloc.c:

#include <stdlib.h>
#include <unistd.h>

#include "malloc.h"

void *malloc(size_t size)
{
    if(__get_next_allocation(size))
        return NULL;
    return __allocinfo->start;
}

malloc.h:

#ifndef _MALLOC_H
#define _MALLOC_H 1

#include <features.h>
#include <sys/types.h>

#ifdef __PTR16__
# define CHUNK_SIZE (0x4000) /* 16K */
#else
# define CHUNK_SIZE (0x10000) /* 64K */
#endif

struct malloc_chunk
{
    void *start;
    size_t alloc_cnt;
    size_t chunk_cnt;
    struct malloc_chunk *prev;
    struct malloc_chunk *next;
};

struct allocation_info
{
    void *start;
    size_t size;
    int free;
    struct allocation_info *prev;
    struct allocation_info *next;
};

extern struct malloc_chunk *__mallchunk;
extern struct allocation_info *__allocinfo;

extern int __get_next_chunk(void);
extern int __get_next_allocation(size_t size);

#endif

metadata.c:

#include "malloc.h"

struct malloc_chunk *__mallchunk;
struct allocation_info *__allocinfo;

realloc.c:

#include "malloc.h"

#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define LESSER(x,y) ((x) > (y) ? (y) : (x))

void *realloc(void *ptr, size_t size)
{
    size_t newsize = 0;
    void *newptr = malloc(size);

    struct allocation_info *tmp_allinfo = __allocinfo;

    if(!ptr) goto end;

    while(tmp_allinfo->prev)
        tmp_allinfo = tmp_allinfo->prev;

    while(tmp_allinfo && tmp_allinfo->start != ptr)
        tmp_allinfo = tmp_allinfo->next;

    if(!tmp_allinfo)
        return NULL;

    newsize = LESSER(tmp_allinfo->size, size);

    memcpy(newptr, ptr, newsize);

end:
    free(ptr);
    return newptr;
}

EDIT: If anybody wants to use this code, it's licensed under the LGPL: link to repository

Answer 1

Unnecessary code

There is no need to make size, nemb even values.

if(size % 2) size++;
if(nmemb % 2) nmemb++;

__get_next_allocation(size_t size) may benefit with rounding up of size

Say you want allocations to be a multiple of 8.

#define ALLOC_MULTIPLE 8
int __get_next_allocation(size_t size) {
  if (size % ALLOC_MULTIPLE) {
    if (size > SIZE_MAX - ALLOC_MULTIPLE) {
      return -1;
    }
    size += ALLOC_MULTIPLE - (size % ALLOC_MULTIPLE); 
  }
  ...

calloc() does not detect overflow

if (nmemb > 0 && SIZE_MAX/nmemb > size) {
  return NULL;  // allocation too big.
} 
// Now safe to multiply.
size *= nmemb;

Non compliant math

In C, adding to a void * is UB. May be OK in Posix.

// (void *)tmp_alloc + sizeof(*tmp_alloc);
(char *)tmp_alloc + sizeof(*tmp_alloc);

Note: ENOMEM is not ISO C.

Non compliant alignment

The value returned from *alloc() is expected to be aligned for all types. By adding sizeof(*__mallchunk), coding may lose this vital property - thus UB. Various ways to handle this, yet code needs to insure __mallchunk->start has an aligned value.

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 and then used to access such an object or an array of such objects in the space allocated §7.22.3 1.