new malloc

I wrote a new alloc code for dietlibc.  It is with 100 bytes shorter.
May be the main advantage is that one can compile
malloc, free, calloc and realloc in separate files.
For example qmail uses only malloc and free.

Felix, I know you will say Aaaa, Oooo, Uuuu, Difficult...
I think its better and uses less memory!  May be you will accept it ;-)
I ask the community to test it and report about any problems.  

I remember that you made same changes in minit using
__libc_{realloc,malloc,free}.  They will work this alloc.c also.  In
my opinion use my patch for minit.  It removes malloc/realloc/free
code from minit and uses only alloca!  I wrote the patch extra for minit.

Nikola

https://riemann.fmi.uni-sofia.bg/programs/diet/
https://riemann.fmi.uni-sofia.bg/programs/diet/alloc.tar.gz
See the README there.


   text    data     bss     dec     hex filename
     61       0       0      61      3d alloc_calloc.o
     93       0       0      93      5d alloc_free.o
    185       0       0     185      b9 alloc_realloc.o
    331       0       8     339     153 alloc.o

all in one file (depends of dietfeatures.h)
   text    data     bss     dec     hex filename
    671       0       8     679     2a7 alloc.o
    

-------------- 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)
 *
 * modified by Nikola Vladov: 2009-04-05
 *   free, calloc, realloc can be in a separate file.
 */

#include <unistd.h>
#include <sys/mman.h>
#include "dietfeatures.h" /* must be befoore errno.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 */

#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)))

#define __MIN_SMALL_SIZE	MEM_BLOCK_SIZE/256	/*   16 /   32 */
#define __MAX_SMALL_SIZE	MEM_BLOCK_SIZE/2	/* 2048 / 4096 */
#define __GET_SIZE(s)	__diet_get_page_size(s)
#define __GET_INDEX(s)	__diet_get_page_index(s)

extern size_t __diet_get_page_size(size_t size);
extern size_t __diet_get_page_index(size_t size);
extern __alloc_t* __small_mem[8];


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

#ifdef DIET_SKIP_MALLOC_CODE
extern void* __libc_malloc(size_t n);
extern void  __libc_free(void *p);

#else
__alloc_t* __small_mem[8];

size_t __diet_get_page_index(size_t size) {
  size_t len=0;
  for (; size > __MIN_SMALL_SIZE; size /= 2) ++len;
  return len;
}

size_t __diet_get_page_size(size_t size) {
  register size_t len;

  size+=sizeof(__alloc_t);
  if (size<sizeof(__alloc_t)) return 0;

  if (size > __MAX_SMALL_SIZE)
    len = PAGE_ALIGN(size);
  else
    for (len = __MIN_SMALL_SIZE; len < size; ) len *= 2;
  return len;
}


/* -- MALLOC CODE ------------------------------------------------------ */

static void* __small_malloc(size_t size) {
  __alloc_t *ptr;
  static void *space;
  static size_t avail;
  size_t map_size, idx=0, len=512; /* power of two!  256 or 512 is good */

  if (size > __MAX_SMALL_SIZE) {
    map_size=size;
    goto get_mmap;
  }

  map_size = MEM_BLOCK_SIZE;
  idx=__GET_INDEX(size);
  ptr=__small_mem[idx];

  if (ptr==0)  {	/* no free blocks ? */
    if (len < size) len = size;
    if (len <= avail) {
    got_free:
      avail -= len;
      ptr = space + avail;
    } else {
    get_mmap:
      ptr = mmap(0, map_size, PROT_READ|PROT_WRITE,
		 MAP_ANONYMOUS|MAP_PRIVATE, -1, (size_t)0);
      if (size > __MAX_SMALL_SIZE ||
	  ptr==MAP_FAILED) return ptr;

      if (avail==0) {
	space = ptr;
	avail = map_size;
	goto got_free;
      }
      len = map_size;
    }

    len /= size;
    __small_mem[idx]=ptr;
    while (len-- > 1) {
      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;

  return ptr;
}

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

static void* _alloc_libc_malloc(size_t size) {
  __alloc_t* ptr;
#ifdef WANT_MALLOC_ZERO
  if (!size) return BLOCK_RET(zeromem);
#else
  if (!size) goto err_out;
#endif
  size=__GET_SIZE(size);
  if (size==0) goto err_out;

  ptr=__small_malloc(size);
  if (ptr==MAP_FAILED) goto err_out;

  ptr->size=size;
  return BLOCK_RET(ptr);
err_out:
  errno=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")));
#endif


/* -- FREE CODE ------------------------------------------------------ */

#ifndef WANT_SEPARATE_FREE
static void _alloc_libc_free(void *_ptr) {
  if (_ptr) {
    __alloc_t *ptr = BLOCK_START(_ptr);
    size_t size=ptr->size;
    if (size) {
      if (size<=__MAX_SMALL_SIZE) {
	size_t idx=__GET_INDEX(size);
	
#ifdef WANT_FREE_OVERWRITE
	memset(ptr,0x55,size);	/* allways zero out small mem */
#else
	memset(ptr,0,size);	/* allways zero out small mem */
#endif
	ptr->next=__small_mem[idx];
	__small_mem[idx]=ptr;
      }
      else
	munmap(ptr,size);
    }
  }
}
void __libc_free(void *ptr) __attribute__((weak,alias("_alloc_libc_free")));
void free(void *ptr) __attribute__((weak,alias("_alloc_libc_free")));
/* void if_freenameindex(void* ptr) __attribute__((alias("free"))); */
#endif


/* -- CALLOC CODE ------------------------------------------------------ */

#ifndef WANT_SEPARATE_CALLOC
static void* _alloc_libc_calloc(size_t nmemb, size_t _size) {
  register size_t size=_size*nmemb;
  if (nmemb && size/nmemb!=_size) {
    errno=ENOMEM;
    return 0;
  }
#ifdef WANT_FREE_OVERWRITE
  if (size<__MAX_SMALL_SIZE) {
    void* x=__libc_malloc(size);
    if (x) memset(x,0,size);
    return x;
  } else
#endif
  return __libc_malloc(size);
}
void* __libc_calloc(size_t nmemb, size_t _size) __attribute__((weak,alias("_alloc_libc_calloc")));
void* calloc(size_t nmemb, size_t _size) __attribute__((weak,alias("_alloc_libc_calloc")));
#endif


/* -- REALLOC CODE ------------------------------------------------------ */

#ifndef WANT_SEPARATE_REALLOC
static void* _alloc_libc_realloc(void* ptr, size_t _size) {
  register __alloc_t* tmp;
  register size_t old_size=0, size=_size;
  if (ptr) {
    if (!size) {
      __libc_free(ptr);
      ptr = NULL;
    } 
    else { /* size > 0 */
      tmp=BLOCK_START(ptr);
      old_size=tmp->size;
      if (!old_size) goto get_mmap;

      size=__GET_SIZE(size);
      if (size==0) goto retzero;

      if (old_size!=size) {
	if (old_size<=__MAX_SMALL_SIZE) goto get_mmap;
	else {
	  tmp=mremap(tmp,old_size,size,MREMAP_MAYMOVE);
	  if (tmp==MAP_FAILED) goto get_mmap;	/* paranoia */
	  tmp->size=size;
	  ptr=BLOCK_RET(tmp);
	}
      }
    }
  }
  else { /* ptr==0 */
    if (size) {
      void *old_ptr;
get_mmap:
      old_ptr = ptr;
      ptr=__libc_malloc(_size);
      if (ptr && old_size) {
	tmp = BLOCK_START(ptr);
	size = tmp->size;
	if (size > old_size) size = old_size;
	memcpy(ptr,old_ptr,size-sizeof(__alloc_t));
	__libc_free(old_ptr);
      }
    }
  }
  return ptr;
retzero:
  errno=ENOMEM;
  return 0;
}
void* __libc_realloc(void* ptr, size_t size) __attribute__((weak,alias("_alloc_libc_realloc")));
void* realloc(void* ptr, size_t size) __attribute__((weak,alias("_alloc_libc_realloc")));
#endif