path: root/common/diet/alloc.c

/*
 * malloc/free by O.Dreesen
 *
 * first TRY:
 *   lists w/magics
 * and now the second TRY
 *   let the kernel map all the stuff (if there is something to do)
 */

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

#include <sys/cdefs.h>
#include <sys/types.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#include <sys/shm.h>    /* for PAGE_SIZE */


/* -- HELPER CODE --------------------------------------------------------- */

#ifndef MAP_FAILED
#define MAP_FAILED ((void*)-1)
#endif

#ifndef NULL
#define NULL ((void*)0)
#endif

typedef struct {
  void*  next;
  size_t size;
} __alloc_t;

#define BLOCK_START(b)  (((void*)(b))-sizeof(__alloc_t))
#define BLOCK_RET(b)    (((void*)(b))+sizeof(__alloc_t))

#define MEM_BLOCK_SIZE  PAGE_SIZE
#define PAGE_ALIGN(s)   (((s)+MEM_BLOCK_SIZE-1)&(unsigned long)(~(MEM_BLOCK_SIZE-1)))

/* a simple mmap :) */
#if defined(__i386__)
#define REGPARM(x) __attribute__((regparm(x)))
#else
#define REGPARM(x)
#endif

static void REGPARM(1) *do_mmap(size_t size) {
  return mmap(0, size, PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE, -1, (size_t)0);
}

/* -- SMALL MEM ----------------------------------------------------------- */

static __alloc_t* __small_mem[8];

static int smallalloc[8];
static int smallalloc_max[8];

#define __SMALL_NR(i)       (MEM_BLOCK_SIZE/(i))

#define __MIN_SMALL_SIZE    __SMALL_NR(256)     /*   16 /   32 */
#define __MAX_SMALL_SIZE    __SMALL_NR(2)       /* 2048 / 4096 */

#define GET_SIZE(s)     (__MIN_SMALL_SIZE<<get_index((s)))

#define FIRST_SMALL(p)      (((unsigned long)(p))&(~(MEM_BLOCK_SIZE-1)))

static inline int __ind_shift() { return (MEM_BLOCK_SIZE==4096)?4:5; }

static size_t REGPARM(1) get_index(size_t _size) {
  register size_t idx=0;
//  if (_size) {    /* we already check this in the callers */
    register size_t size=((_size-1)&(MEM_BLOCK_SIZE-1))>>__ind_shift();
    while(size) { size>>=1; ++idx; }
//  }
  return idx;
}

/* small mem */
static void __small_free(void*_ptr,size_t _size) REGPARM(2);

static void REGPARM(2) __small_free(void*_ptr,size_t _size) {
  __alloc_t* ptr=BLOCK_START(_ptr);
  size_t size=_size;
  size_t idx=get_index(size);

  memset(ptr,0,size);   /* allways zero out small mem */

  ptr->next=__small_mem[idx];
  __small_mem[idx]=ptr;

  smallalloc[idx]--;

  if (MEM_BLOCK_SIZE == PAGE_SIZE &&
      smallalloc[idx] == 0 &&
      smallalloc_max[idx] < __SMALL_NR(size)) {
      __alloc_t* p = __small_mem[idx];
      __alloc_t* ph = p - (size_t)p%PAGE_SIZE;
      munmap(ph, MEM_BLOCK_SIZE);
      __small_mem[idx] = 0;
  }
}

static void* REGPARM(1) __small_malloc(size_t _size) {
  __alloc_t *ptr;
  size_t size=_size;
  size_t idx;

  idx=get_index(size);
  ptr=__small_mem[idx];

  if (ptr==0)  {    /* no free blocks ? */
    register int i,nr;
    ptr=do_mmap(MEM_BLOCK_SIZE);
    if (ptr==MAP_FAILED) return MAP_FAILED;

    __small_mem[idx]=ptr;

    nr=__SMALL_NR(size)-1;
    for (i=0;i<nr;i++) {
      ptr->next=(((void*)ptr)+size);
      ptr=ptr->next;
    }
    ptr->next=0;

    ptr=__small_mem[idx];
  }

  /* get a free block */
  __small_mem[idx]=ptr->next;
  ptr->next=0;

  smallalloc[idx]++;
  if(smallalloc[idx] > smallalloc_max[idx])
      smallalloc_max[idx] = smallalloc[idx];

  return ptr;
}

/* -- PUBLIC FUNCTIONS ---------------------------------------------------- */

static void _alloc_libc_free(void *ptr) {
  register size_t size;
  if (ptr) {
    size=((__alloc_t*)BLOCK_START(ptr))->size;
    if (size) {
      if (size<=__MAX_SMALL_SIZE)
    __small_free(ptr,size);
      else
    munmap(BLOCK_START(ptr),size);
    }
  }
}
void __libc_free(void *ptr) __attribute__((alias("_alloc_libc_free")));
void free(void *ptr) __attribute__((weak,alias("_alloc_libc_free")));
void if_freenameindex(void* ptr) __attribute__((alias("free")));

#ifdef WANT_MALLOC_ZERO
static __alloc_t zeromem[2];
#endif

static void* _alloc_libc_malloc(size_t size) {
  __alloc_t* ptr;
  size_t need;
#ifdef WANT_MALLOC_ZERO
  if (!size) return BLOCK_RET(zeromem);
#else
  if (!size) goto err_out;
#endif
  size+=sizeof(__alloc_t);
  if (size<sizeof(__alloc_t)) goto err_out;
  if (size<=__MAX_SMALL_SIZE) {
    need=GET_SIZE(size);
    ptr=__small_malloc(need);
  }
  else {
    need=PAGE_ALIGN(size);
    if (!need) ptr=MAP_FAILED; else ptr=do_mmap(need);
  }
  if (ptr==MAP_FAILED) goto err_out;
  ptr->size=need;
  return BLOCK_RET(ptr);
err_out:
  (*__errno_location())=ENOMEM;
  return 0;
}
void* __libc_malloc(size_t size) __attribute__((alias("_alloc_libc_malloc")));
void* malloc(size_t size) __attribute__((weak,alias("_alloc_libc_malloc")));

void* __libc_calloc(size_t nmemb, size_t _size);
void* __libc_calloc(size_t nmemb, size_t _size) {
  register size_t size=_size*nmemb;
  if (nmemb && size/nmemb!=_size) {
    (*__errno_location())=ENOMEM;
    return 0;
  }
  return malloc(size);
}
void* calloc(size_t nmemb, size_t _size) __attribute__((weak,alias("__libc_calloc")));

void* __libc_realloc(void* ptr, size_t _size);
void* __libc_realloc(void* ptr, size_t _size) {
  register size_t size=_size;
  if (ptr) {
    if (size) {
      __alloc_t* tmp=BLOCK_START(ptr);
      size+=sizeof(__alloc_t);
      if (size<sizeof(__alloc_t)) goto retzero;
      size=(size<=__MAX_SMALL_SIZE)?GET_SIZE(size):PAGE_ALIGN(size);
      if (tmp->size!=size) {
    if ((tmp->size<=__MAX_SMALL_SIZE)) {
      void *new=_alloc_libc_malloc(_size);
      if (new) {
        register __alloc_t* foo=BLOCK_START(new);
        size=foo->size;
        if (size>tmp->size) size=tmp->size;
        if (size) memcpy(new,ptr,size-sizeof(__alloc_t));
        _alloc_libc_free(ptr);
      }
      ptr=new;
    }
    else {
      register __alloc_t* foo;
      size=PAGE_ALIGN(size);
      foo=mremap(tmp,tmp->size,size,MREMAP_MAYMOVE);
      if (foo==MAP_FAILED) {
retzero:
        (*__errno_location())=ENOMEM;
        ptr=0;
      }
      else {
        foo->size=size;
        ptr=BLOCK_RET(foo);
      }
    }
      }
    }
    else { /* size==0 */
      _alloc_libc_free(ptr);
      ptr = NULL;
    }
  }
  else { /* ptr==0 */
    if (size) {
      ptr=_alloc_libc_malloc(size);
    }
  }
  return ptr;
}
void* realloc(void* ptr, size_t size) __attribute__((weak,alias("__libc_realloc")));