Happy Eastern!

http://riemann.fmi.uni-sofia.bg/programs/diet/alloc.tar.gz

I'm finished the work on malloc.  Now it is only 611 bytes
and uses less memory.  It has new very effective algorithm.

Here are my Algorithm.txt and the C source of it.  Olaf if you
read this list let me know.  Many thanks for your wonderful alloc.
I have made only little changes in it ;-)

Nikola

----------------  Algorithm.txt --------------------
The algorithm is very simple:

We have an static array __alloc_t *space[8];
Each pointer is zero or some allocated page.
Let we want to allocate N bytes.  N is power of two
and 16 <= N <= 2048.  I assume that one page is 4096.

let __alloc_t *t = space[X] and  (t != 0).
We check if N >= t->size.  

From all such t we chose the smallest.  This means
that t->size >= N and all other t have bigger size.
If such t exists we do:
    t->size -= size;
    space[X] = (t->size) ? t : 0;
    ptr = (((void*)t) + t->size);

If there is not such t, then there exists at least one X such that
space[X] = 0.  The allocate one new page and set space[X] to the 
address of this page.  Then we continue as above.

Since we chose always the "minimal" t above the algorithm cannot stop!
It si impossible for example to have in all space[X] pages
with free only 128 bytes and we want to allocate 512 bytes.
See also tst-algorithm.c included here.

The worst case is to have in 8 pages
16, 32, 64, ... 2048 bytes free.  Their sum is  4080 bytes.
Average unused RAM is 2048 bytes (for small pages).

The C realization of the above algorithm is even easier than 
current dietlibc alloc.c.  In the worst case it has is:

(4096 - 16) + (4096 - 32) + ... + (4096 - 2148) = 7 pages = 28K.
Average unused RAM is 3.5 pages = 14K.

One can change __alloc_t to be union.  May be on ARCH
where the size ot __alloc_t > 8 one can define.

typedef union {
  void*  next;
  size_t size;
  char *x[8];
} __alloc_t;

Actually with above algorithm we don't need next any more.
It is important only for free.  So the union is OK.


----------------------

static void* REGPARM(1) __small_malloc(size_t size) {
  static __alloc_t *space[8];
  __alloc_t **tt=0, **idx=0, *ptr;
  size_t map_size=MEM_BLOCK_SIZE;

  if (size > __MAX_SMALL_SIZE) {
    map_size=size;

  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;

    ptr->size = map_size;
    goto ready;
  }

  idx=__GET_INDEX(size);
  ptr=*idx;

  if (ptr) {	/* get a free block */
    *idx=ptr->next;
    ptr->next=0;
  } 
  else {
    __alloc_t *t, **min=0, **zero=0;
    for (tt=space; tt < space+8; tt++) {	/* see: Algorithm.txt */
      t = *tt;
      if (t==0) zero = tt;
      else
	if (t->size >= size) {
	  if (min == 0) min = tt;
	  else if (min[0]->size > t->size) min = tt;
	}
    }

    if (min) {	/* get a space in some space[X] */
      tt = min;
      ptr = *tt;
    } else {
      /* zero == 0 is impossible!  prove it ;-) */
      tt = zero;
      goto get_mmap;
    }

  ready:
    t = ptr;
    t->size -= size;
    *tt = (t->size) ? t : 0;
    ptr = (((void*)t) + t->size);
  }
  return ptr;
}