7
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ What happens if you try to malloc 150K? That's larger than your CHUNK size. realloc will misbehave if the malloc call fails. \$\endgroup\$ – 1201ProgramAlarm Jun 8 at 3:28
  • \$\begingroup\$ @1201ProgramAlarm Yeah, I'm working in fixing that; for now, I'll impose a hard limit. I just fixed a bug (used strace, great tool) that caused this to always allocate a new block of memory every time it was called. I'll keep this as is, though, to see if somebody else catches it (and comes up with a better solution). \$\endgroup\$ – JL2210 Jun 8 at 4:50
  • 1
    \$\begingroup\$ No notes on goto? Not even to say that it's perfectly appropriate here? \$\endgroup\$ – Toby Speight Jun 17 at 17:28
3
\$\begingroup\$

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 ofsize`

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

\$\endgroup\$
  • 1
    \$\begingroup\$ In POSIX, it's also UB. Thanks for pointing that out. \$\endgroup\$ – JL2210 Jun 15 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.