The R13B03 release.OTP_R13B03

1 files changed, 2334 insertions, 0 deletions

diff --git a/erts/emulator/beam/elib_malloc.c b/erts/emulator/beam/elib_malloc.c
new file mode 100644
index 0000000000..b18c48d8d6
--- /dev/null
+++ b/erts/emulator/beam/elib_malloc.c
@@ -0,0 +1,2334 @@
+/*
+ * %CopyrightBegin%
+ * 
+ * Copyright Ericsson AB 1997-2009. All Rights Reserved.
+ * 
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ * 
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ * 
+ * %CopyrightEnd%
+ */
+
+/*
+** Description: Faster malloc().
+*/
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif
+
+#include "sys.h"
+
+#ifdef ENABLE_ELIB_MALLOC
+
+#undef THREAD_SAFE_ELIB_MALLOC
+#ifdef USE_THREADS
+#define THREAD_SAFE_ELIB_MALLOC 1
+#else
+#define THREAD_SAFE_ELIB_MALLOC 0
+#endif
+
+#include "erl_driver.h"
+#include "erl_threads.h"
+#include "elib_stat.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+/* To avoid clobbering of names becaure of reclaim on VxWorks,
+   we undefine all possible malloc, calloc etc. */
+#undef malloc
+#undef calloc
+#undef free
+#undef realloc
+
+#define ELIB_INLINE         /* inline all possible functions */
+
+#ifndef ELIB_ALIGN
+#define ELIB_ALIGN             sizeof(double)
+#endif
+
+#ifndef ELIB_HEAP_SIZE
+#define ELIB_HEAP_SIZE         (64*1024)  /* Default 64K */
+#endif
+
+#ifndef ELIB_HEAP_INCREAMENT
+#define ELIB_HEAP_INCREAMENT   (32*1024)  /* Default 32K */
+#endif
+
+#ifndef ELIB_FAILURE
+#define ELIB_FAILURE    abort()
+#endif
+
+#undef ASSERT
+#ifdef DEBUG
+#define ASSERT(B) \
+ ((void) ((B) ? 1 : (fprintf(stderr, "%s:%d: Assertion failed: %s\n", \
+			     __FILE__, __LINE__, #B), abort(), 0)))
+#else
+#define ASSERT(B) ((void) 1)
+#endif
+
+#ifndef USE_RECURSIVE_MALLOC_MUTEX
+#define USE_RECURSIVE_MALLOC_MUTEX 0
+#endif
+
+#if USE_RECURSIVE_MALLOC_MUTEX
+static erts_mtx_t malloc_mutex = ERTS_REC_MTX_INITER;
+#else /* #if USE_RECURSIVE_MALLOC_MUTEX */
+static erts_mtx_t malloc_mutex = ERTS_MTX_INITER;
+#if THREAD_SAFE_ELIB_MALLOC
+static erts_cnd_t  malloc_cond  = ERTS_CND_INITER;
+#endif
+#endif  /* #if USE_RECURSIVE_MALLOC_MUTEX */
+
+typedef unsigned long EWord;       /* Assume 32-bit in this implementation */
+typedef unsigned short EHalfWord;  /* Assume 16-bit in this implementation */
+typedef unsigned char EByte;       /* Assume 8-bit byte */
+
+
+#define elib_printf fprintf
+#define elib_putc   fputc
+
+
+#if defined(__STDC__) || defined(__WIN32__)
+#define CONCAT(x,y) x##y
+#else
+#define CONCAT(x,y) x/**/y
+#endif
+
+
+#ifdef ELIB_DEBUG
+#define ELIB_PREFIX(fun, args) CONCAT(elib__,fun) args
+#else
+#define ELIB_PREFIX(fun, args) CONCAT(elib_,fun) args
+#endif
+
+#if defined(__STDC__)
+void *ELIB_PREFIX(malloc, (size_t));
+void *ELIB_PREFIX(calloc, (size_t, size_t));
+void ELIB_PREFIX(cfree, (EWord *));
+void ELIB_PREFIX(free, (EWord *));
+void *ELIB_PREFIX(realloc, (EWord *, size_t));
+void* ELIB_PREFIX(memresize, (EWord *, int));
+void* ELIB_PREFIX(memalign, (int, int));
+void* ELIB_PREFIX(valloc, (int));
+void* ELIB_PREFIX(pvalloc, (int));
+int ELIB_PREFIX(memsize, (EWord *));
+/* Extern interfaces used by VxWorks */
+size_t elib_sizeof(void *);
+void elib_init(EWord *, EWord);
+void elib_force_init(EWord *, EWord);
+#endif
+
+#if defined(__STDC__)
+/* define prototypes for missing */
+void* memalign(size_t a, size_t s);
+void* pvalloc(size_t nb);
+void* memresize(void *p, int nb);
+int memsize(void *p);
+#endif
+
+/* bytes to pages */
+#define PAGES(x)      (((x)+page_size-1) / page_size)
+#define PAGE_ALIGN(p) ((char*)((((EWord)(p))+page_size-1)&~(page_size-1)))
+
+/* bytes to words */
+#define WORDS(x)      (((x)+sizeof(EWord)-1) / sizeof(EWord))
+
+/* Align an address */
+#define ALIGN(p)     ((EWord*)((((EWord)(p)+ELIB_ALIGN-1)&~(ELIB_ALIGN-1))))
+
+/* Calculate the size needed to keep alignment */
+
+#define ALIGN_BSZ(nb)  ((nb+sizeof(EWord)+ELIB_ALIGN-1) & ~(ELIB_ALIGN-1))
+
+#define ALIGN_WSZ(nb)  WORDS(ALIGN_BSZ(nb))
+
+#define ALIGN_SIZE(nb) (ALIGN_WSZ(nb) - 1)
+
+
+/* PARAMETERS */
+
+#if defined(ELIB_HEAP_SBRK)
+
+#undef PAGE_SIZE
+
+/* Get the system page size (NEED MORE DEFINES HERE) */
+#ifdef _SC_PAGESIZE
+#define PAGE_SIZE   sysconf(_SC_PAGESIZE)
+#elif defined(_MSC_VER)
+#  ifdef _M_ALPHA
+#    define PAGE_SIZE      0x2000
+#  else
+#    define PAGE_SIZE      0x1000
+#  endif
+#else
+#define PAGE_SIZE   getpagesize()
+#endif
+
+#define ELIB_EXPAND(need)  expand_sbrk(need)
+static FUNCTION(int, expand_sbrk, (EWord));
+
+#elif defined(ELIB_HEAP_FIXED)
+
+#define PAGE_SIZE 1024
+#define ELIB_EXPAND(need) -1
+static EWord fix_heap[WORDS(ELIB_HEAP_SIZE)];
+
+#elif defined(ELIB_HEAP_USER)
+
+#define PAGE_SIZE 1024
+#define ELIB_EXPAND(need) -1
+
+#else
+
+#error "ELIB HEAP TYPE NOT SET"
+
+#endif
+
+
+#define STAT_ALLOCED_BLOCK(SZ)		\
+do {					\
+    tot_allocated += (SZ);		\
+    if (max_allocated < tot_allocated)	\
+	max_allocated = tot_allocated;	\
+} while (0)
+
+#define STAT_FREED_BLOCK(SZ)		\
+do {					\
+    tot_allocated -= (SZ);		\
+} while (0)
+
+static int max_allocated = 0;
+static int tot_allocated = 0;
+static EWord* eheap;        /* Align heap start */
+static EWord* eheap_top;    /* Point to end of heap */
+EWord page_size = 0;        /* Set by elib_init */
+
+#if defined(ELIB_DEBUG) || defined(DEBUG)
+#define ALIGN_CHECK(a, p)						\
+ do {									\
+    if ((EWord)(p) & (a-1)) {						\
+	elib_printf(stderr,						\
+		    "RUNTIME ERROR: bad alignment (0x%lx:%d:%d)\n",	\
+		    (unsigned long) (p), (int) a, __LINE__);			\
+	ELIB_FAILURE;							\
+    }									\
+  } while(0)
+#define ELIB_ALIGN_CHECK(p) ALIGN_CHECK(ELIB_ALIGN, p)
+#else
+#define ALIGN_CHECK(a, p)
+#define ELIB_ALIGN_CHECK(p)
+#endif
+
+#define DYNAMIC 32
+
+/*
+** Free block layout
+**   1 1          30
+**  +--------------------------+
+**  |F|P|        Size          |
+**  +--------------------------+
+**
+** Where F is the free bit
+**       P is the free above bit
+**       Size is messured in words and does not include the hdr word
+**
+** If block is on the free list the size is also stored last in the block.
+** 
+*/
+typedef struct _free_block FreeBlock;
+struct _free_block {
+    EWord hdr;
+    Uint flags;
+    FreeBlock* parent;
+    FreeBlock* left;
+    FreeBlock* right;
+    EWord v[1];
+};
+
+typedef struct _allocated_block {
+    EWord hdr;
+    EWord v[5];
+} AllocatedBlock;
+
+
+/*
+ * Interface to tree routines.
+ */
+typedef Uint Block_t;
+
+static Block_t*	get_free_block(Uint);
+static void link_free_block(Block_t *);
+static void unlink_free_block(Block_t *del);
+
+#define FREE_BIT       0x80000000
+#define FREE_ABOVE_BIT 0x40000000
+#define SIZE_MASK      0x3fffffff     /* 2^30 words = 2^32 bytes */
+
+/* Work on both FreeBlock and AllocatedBlock */
+#define SIZEOF(p)         ((p)->hdr & SIZE_MASK)
+#define IS_FREE(p)        (((p)->hdr & FREE_BIT) != 0)
+#define IS_FREE_ABOVE(p)  (((p)->hdr & FREE_ABOVE_BIT) != 0)
+
+/* Given that we have a free block above find its size */
+#define SIZEOF_ABOVE(p)    *(((EWord*) (p)) - 1)
+
+#define MIN_BLOCK_SIZE      (sizeof(FreeBlock)/sizeof(EWord))
+#define MIN_WORD_SIZE       (MIN_BLOCK_SIZE-1)
+#define MIN_BYTE_SIZE       (sizeof(FreeBlock)-sizeof(EWord))
+
+#define MIN_ALIGN_SIZE      ALIGN_SIZE(MIN_BYTE_SIZE)
+
+
+static AllocatedBlock* heap_head = 0;
+static AllocatedBlock* heap_tail = 0;
+static EWord eheap_size = 0;
+
+static int heap_locked;
+
+static int elib_need_init = 1;
+#if THREAD_SAFE_ELIB_MALLOC
+static int elib_is_initing = 0;
+#endif
+
+typedef FreeBlock RBTree_t;
+
+static RBTree_t* root = NULL;
+
+
+static FUNCTION(void, deallocate, (AllocatedBlock*, int));
+
+/*
+ * Unlink a free block
+ */
+
+#define mark_allocated(p, szp) do { \
+      (p)->hdr = ((p)->hdr & FREE_ABOVE_BIT) | (szp); \
+      (p)->v[szp] &= ~FREE_ABOVE_BIT; \
+   } while(0)
+
+#define mark_free(p, szp) do { \
+      (p)->hdr = FREE_BIT | (szp); \
+      ((FreeBlock *)p)->v[szp-sizeof(FreeBlock)/sizeof(EWord)+1] = (szp); \
+   } while(0)
+
+#if 0
+/* Help macros to log2 */
+#define LOG_1(x)  (((x) > 1) ? 1 : 0)
+#define LOG_2(x)  (((x) > 3) ? 2+LOG_1((x) >> 2) : LOG_1(x))
+#define LOG_4(x)  (((x) > 15) ? 4+LOG_2((x) >> 4) : LOG_2(x))
+#define LOG_8(x)  (((x) > 255) ? 8+LOG_4((x)>>8) : LOG_4(x))
+#define LOG_16(x) (((x) > 65535) ? 16+LOG_8((x)>>16) : LOG_8(x))
+
+#define log2(x)   LOG_16(x)
+#endif
+
+/*
+ * Split a block to be allocated.
+ * Mark block as ALLOCATED and clear
+ * FREE_ABOVE_BIT on next block
+ *
+ * nw is SIZE aligned and szp is SIZE aligned + 1
+ */
+static void
+split_block(FreeBlock* p, EWord nw, EWord szp)
+{
+    EWord szq;
+    FreeBlock* q;
+
+    szq = szp - nw;
+    /* Preserve FREE_ABOVE bit in p->hdr !!! */
+
+    if (szq >= MIN_ALIGN_SIZE+1) {
+	szq--;
+	p->hdr = (p->hdr & FREE_ABOVE_BIT) | nw;
+
+	q = (FreeBlock*) (((EWord*) p) + nw + 1);
+	mark_free(q, szq);
+	link_free_block((Block_t *) q);
+
+	q = (FreeBlock*) (((EWord*) q) + szq + 1);
+	q->hdr |= FREE_ABOVE_BIT;
+    }
+    else {
+	mark_allocated((AllocatedBlock*)p, szp);
+    }
+}
+
+/*
+ * Find a free block
+ */
+static FreeBlock*
+alloc_block(EWord nw)
+{
+    for (;;) {
+	FreeBlock* p = (FreeBlock *) get_free_block(nw);
+
+	if (p != NULL) {
+	    return p;
+	} else if (ELIB_EXPAND(nw+MIN_WORD_SIZE)) {
+	    return 0;
+	}
+    }
+}
+
+
+size_t elib_sizeof(void *p)
+{
+    AllocatedBlock* pp;
+
+    if (p != 0) {
+	pp = (AllocatedBlock*) (((char *)p)-1);
+	return SIZEOF(pp);
+    }
+    return 0;
+}
+
+static void locked_elib_init(EWord*, EWord);
+static void init_elib_malloc(EWord*, EWord);
+
+/*
+** Initialize the elib
+** The addr and sz is only used when compiled with EXPAND_ADDR 
+*/
+/* Not static, this is used by VxWorks */
+void elib_init(EWord* addr, EWord sz)
+{
+    if (!elib_need_init)
+	return;
+    erts_mtx_lock(&malloc_mutex);
+    locked_elib_init(addr, sz);
+    erts_mtx_unlock(&malloc_mutex);
+}
+
+static void locked_elib_init(EWord* addr, EWord sz)
+{
+    if (!elib_need_init)
+	return;
+
+#if THREAD_SAFE_ELIB_MALLOC
+
+#if !USE_RECURSIVE_MALLOC_MUTEX
+    {
+	static erts_tid_t initer_tid;
+
+	if(elib_is_initing) {
+
+	    if(erts_equal_tids(initer_tid, erts_thr_self()))
+		return;
+
+	    /* Wait until initializing thread is done with initialization */
+
+	    while(elib_need_init)
+		erts_cnd_wait(&malloc_cond, &malloc_mutex);
+
+	    return;
+	}
+	else {
+	    initer_tid = erts_thr_self();
+	    elib_is_initing = 1;
+	}
+    }
+#else
+    if(elib_is_initing)
+	return;
+    elib_is_initing = 1;
+#endif
+
+#endif /* #if THREAD_SAFE_ELIB_MALLOC */
+
+    /* Do the actual initialization of the malloc implementation */
+    init_elib_malloc(addr, sz);
+
+#if THREAD_SAFE_ELIB_MALLOC
+
+#if !USE_RECURSIVE_MALLOC_MUTEX
+    erts_mtx_unlock(&malloc_mutex);
+#endif
+
+    /* Recursive calls to malloc are allowed here... */
+    erts_mtx_set_forksafe(&malloc_mutex);
+
+#if !USE_RECURSIVE_MALLOC_MUTEX
+    erts_mtx_lock(&malloc_mutex);
+    elib_is_initing = 0;
+#endif
+
+#endif /* #if THREAD_SAFE_ELIB_MALLOC */
+
+    elib_need_init = 0;
+
+#if THREAD_SAFE_ELIB_MALLOC && !USE_RECURSIVE_MALLOC_MUTEX
+    erts_cnd_broadcast(&malloc_cond);
+#endif
+
+}
+
+static void init_elib_malloc(EWord* addr, EWord sz)
+{
+    int i;
+    FreeBlock* freep;
+    EWord tmp_sz;
+#ifdef ELIB_HEAP_SBRK
+    char* top;
+    EWord n;
+#endif
+
+    max_allocated = 0;
+    tot_allocated = 0;
+    root = NULL;
+
+    /* Get the page size (may involve system call!!!) */
+    page_size = PAGE_SIZE;
+
+#if defined(ELIB_HEAP_SBRK)
+    sz = PAGES(ELIB_HEAP_SIZE)*page_size;
+
+    if ((top = (char*) sbrk(0)) == (char*)-1) {
+	elib_printf(stderr, "could not initialize elib, sbrk(0)");
+	ELIB_FAILURE;
+    }
+    n = PAGE_ALIGN(top) - top;
+    if ((top = (char*) sbrk(n)) == (char*)-1) {
+	elib_printf(stderr, "could not initialize elib, sbrk(n)");
+	ELIB_FAILURE;
+    }
+    if ((eheap = (EWord*) sbrk(sz)) == (EWord*)-1) {
+	elib_printf(stderr, "could not initialize elib, sbrk(SIZE)");
+	ELIB_FAILURE;
+    }
+    sz = WORDS(ELIB_HEAP_SIZE);
+#elif defined(ELIB_HEAP_FIXED)
+    eheap = fix_heap;
+    sz = WORDS(ELIB_HEAP_SIZE);
+#elif defined(ELIB_HEAP_USER)
+    eheap = addr;
+    sz = WORDS(sz);
+#else
+    return -1;
+#endif
+    eheap_size = 0;
+
+    /* Make sure that the first word of the heap_head is aligned */
+    addr = ALIGN(eheap+1);
+    sz -= ((addr - 1) - eheap);      /* Subtract unusable size */
+    eheap_top = eheap = addr - 1;    /* Set new aligned heap start */
+
+    eheap_top[sz-1] = 0;	     /* Heap stop mark */
+
+    addr = eheap;
+    heap_head = (AllocatedBlock*) addr;
+    heap_head->hdr = MIN_ALIGN_SIZE;
+    for (i = 0; i < MIN_ALIGN_SIZE; i++)
+	heap_head->v[i] = 0;
+
+    addr += (MIN_ALIGN_SIZE+1);
+    freep = (FreeBlock*) addr;
+    tmp_sz = sz - (((MIN_ALIGN_SIZE+1) + MIN_BLOCK_SIZE) + 1 + 1);
+    mark_free(freep, tmp_sz);
+    link_free_block((Block_t *) freep);
+
+    /* No need to align heap tail */
+    heap_tail = (AllocatedBlock*) &eheap_top[sz-MIN_BLOCK_SIZE-1];
+    heap_tail->hdr = FREE_ABOVE_BIT | MIN_WORD_SIZE;
+    heap_tail->v[0] = 0;
+    heap_tail->v[1] = 0;
+    heap_tail->v[2] = 0;
+
+    eheap_top += sz;
+    eheap_size += sz;
+
+    heap_locked = 0;
+}
+
+#ifdef ELIB_HEAP_USER
+void elib_force_init(EWord* addr, EWord sz)
+{
+    elib_need_init = 1;
+    elib_init(addr,sz);
+}
+#endif
+
+#ifdef ELIB_HEAP_SBRK
+
+/*
+** need in number of words (should include head and tail words)
+*/
+static int expand_sbrk(EWord sz)
+{
+    EWord* p;
+    EWord  bytes = sz * sizeof(EWord);
+    EWord  size;
+    AllocatedBlock* tail;
+
+    if (bytes < ELIB_HEAP_SIZE)
+	size = PAGES(ELIB_HEAP_INCREAMENT)*page_size;
+    else
+	size = PAGES(bytes)*page_size;
+
+    if ((p = (EWord*) sbrk(size)) == ((EWord*) -1))
+	return -1;
+
+    if (p != eheap_top) {
+	elib_printf(stderr, "panic: sbrk moved\n");
+	ELIB_FAILURE;
+    }
+
+    sz = WORDS(size);
+
+    /* Set new endof heap marker and a new heap tail */
+    eheap_top[sz-1] = 0;
+
+    tail = (AllocatedBlock*) &eheap_top[sz-MIN_BLOCK_SIZE-1];
+    tail->hdr = FREE_ABOVE_BIT | MIN_WORD_SIZE;
+    tail->v[0] = 0;
+    tail->v[1] = 0;
+    tail->v[2] = 0;
+
+    /* Patch old tail with new appended size */
+    heap_tail->hdr = (heap_tail->hdr & FREE_ABOVE_BIT) |
+	(MIN_WORD_SIZE+1+(sz-MIN_BLOCK_SIZE-1));
+    deallocate(heap_tail, 0);
+
+    heap_tail = tail;
+
+    eheap_size += sz;
+    eheap_top += sz;
+
+    return 0;
+}
+
+#endif /* ELIB_HEAP_SBRK */
+
+
+/*
+** Scan heap and check for corrupted heap
+*/
+int elib_check_heap(void)
+{
+    AllocatedBlock* p = heap_head;
+    EWord sz;
+
+    if (heap_locked) {
+	elib_printf(stderr, "heap is locked no info avaiable\n");
+	return 0;
+    }
+
+    while((sz = SIZEOF(p)) != 0) {
+	if (IS_FREE(p)) {
+	    if (p->v[sz-1] != sz) {
+		elib_printf(stderr, "panic: heap corrupted\r\n"); 
+		ELIB_FAILURE;	
+	    }
+	    p = (AllocatedBlock*) (p->v + sz);
+	    if (!IS_FREE_ABOVE(p)) {
+		elib_printf(stderr, "panic: heap corrupted\r\n"); 
+		ELIB_FAILURE;	
+	    }
+	}
+	else
+	    p = (AllocatedBlock*) (p->v + sz);
+    }
+    return 1;
+}
+
+/*
+** Load the byte vector pointed to by v of length vsz
+** with a heap image
+** The scale is defined by vsz and the current heap size
+** free = 0, full = 255
+** 
+** 
+*/
+int elib_heap_map(EByte* v, int vsz)
+{
+    AllocatedBlock* p = heap_head;
+    EWord sz;
+    int gsz = eheap_size / vsz;  /* The granuality used */
+    int fsz = 0;
+    int usz = 0;
+
+    if (gsz == 0)
+	return -1;  /* too good reolution */
+
+    while((sz = SIZEOF(p)) != 0) {
+	if (IS_FREE(p)) {
+	    fsz += sz;
+	    if ((fsz + usz) > gsz) {
+		*v++ = (255*usz)/gsz;
+		fsz -= (gsz - usz);
+		usz = 0;
+		while(fsz >= gsz) {
+		    *v++ = 0;
+		    fsz -= gsz;
+		}
+	    }
+	}
+	else {
+	    usz += sz;
+	    if ((fsz + usz) > gsz) {
+		*v++ = 255 - (255*fsz)/gsz;
+		usz -= (gsz - fsz);
+		fsz = 0;
+		while(usz >= gsz) {
+		    *v++ = 255;
+		    usz -= gsz;
+		}
+	    }
+	}
+	p = (AllocatedBlock*) (p->v + sz);
+    }
+    return 0;
+}
+
+/*
+** Generate a histogram of free/allocated blocks
+** Count granuality of 10 gives
+** (0-10],(10-100],(100-1000],(1000-10000] ...
+** (0-2], (2-4], (4-8], (8-16], ....
+*/
+static int i_logb(EWord size, int base)
+{
+    int lg = 0;
+    while(size >= base) {
+	size /= base;
+	lg++;
+    }
+    return lg;
+}
+
+int elib_histo(EWord* vf, EWord* va, int vsz, int base)
+{
+    AllocatedBlock* p = heap_head;
+    EWord sz;
+    int i;
+    int linear;
+
+    if ((vsz <= 1) || (vf == 0 && va == 0))
+	return -1;
+
+    if (base < 0) {
+	linear = 1;
+	base = -base;
+    }
+    else
+	linear = 0;
+
+    if (base <= 1)
+	return -1;
+
+    if (vf != 0) {
+	for (i = 0; i < vsz; i++)
+	    vf[i] = 0;
+    }
+    if (va != 0) {
+	for (i = 0; i < vsz; i++)
+	    va[i] = 0;
+    }
+
+    while((sz = SIZEOF(p)) != 0) {
+	if (IS_FREE(p)) {
+	    if (vf != 0) {
+		int val;
+		if (linear)
+		    val = sz / base;
+		else
+		    val = i_logb(sz, base);
+		if (val >= vsz)
+		    vf[vsz-1]++;
+		else
+		    vf[val]++;
+	    }
+	}
+	else {
+	    if (va != 0) {
+		int val;
+		if (linear)
+		    val = sz / base;
+		else
+		    val = i_logb(sz, base);
+		if (val >= vsz)
+		    va[vsz-1]++;
+		else
+		    va[val]++;
+	    }
+	}
+	p = (AllocatedBlock*) (p->v + sz);
+    }
+    return 0;
+}
+
+/*
+** Fill the info structure with actual values
+** Total
+** Allocated
+** Free
+** maxMaxFree     
+*/
+void elib_stat(struct elib_stat* info)
+{
+    EWord blks = 0;
+    EWord sz_free = 0;
+    EWord sz_alloc = 0;
+    EWord sz_max_free = 0;
+    EWord sz_min_used = 0x7fffffff;
+    EWord sz;
+    EWord num_free = 0;
+    AllocatedBlock* p = heap_head;
+
+    info->mem_total = eheap_size;
+
+    p = (AllocatedBlock*) (p->v + SIZEOF(p));
+
+    while((sz = SIZEOF(p)) != 0) {
+	blks++;
+	if (IS_FREE(p)) {
+	    if (sz > sz_max_free)
+		sz_max_free = sz;
+	    sz_free += sz;
+	    ++num_free;
+	}
+	else {
+	    if (sz < sz_min_used)
+		sz_min_used = sz;
+	    sz_alloc += sz;
+	}
+	p = (AllocatedBlock*) (p->v + sz);
+    }
+    info->mem_blocks = blks;
+    info->free_blocks = num_free;
+    info->mem_alloc = sz_alloc;
+    info->mem_free = sz_free;
+    info->min_used = sz_min_used;
+    info->max_free = sz_max_free;
+    info->mem_max_alloc = max_allocated;
+    ASSERT(sz_alloc == tot_allocated);
+}
+
+/*
+** Dump the heap
+*/
+void elib_heap_dump(char* label)
+{
+    AllocatedBlock* p = heap_head;
+    EWord sz;
+
+    elib_printf(stderr, "HEAP DUMP (%s)\n", label);
+    if (!elib_check_heap())
+	return;
+    
+    while((sz = SIZEOF(p)) != 0) {
+	if (IS_FREE(p)) {
+	    elib_printf(stderr, "%p: FREE, size = %d\n", p, (int) sz);
+	}
+	else {
+	    elib_printf(stderr, "%p: USED, size = %d %s\n", p, (int) sz,
+		       IS_FREE_ABOVE(p)?"(FREE ABOVE)":"");
+	}
+	p = (AllocatedBlock*) (p->v + sz);
+    }
+}
+
+/*
+**  Scan heaps and count:
+**  free_size, allocated_size, max_free_block
+*/
+void elib_statistics(void* to)
+{
+    struct elib_stat info;
+    EWord frag;
+
+    if (!elib_check_heap())
+	return;
+
+    elib_stat(&info);
+
+    frag = 1000 - ((1000 * info.max_free) / info.mem_free);
+
+    elib_printf(to, "Heap Statistics: total(%d), blocks(%d), frag(%d.%d%%)\n", 
+	       info.mem_total, info.mem_blocks,
+	       (int) frag/10, (int) frag % 10);
+
+    elib_printf(to, "                 allocated(%d), free(%d), "
+		"free_blocks(%d)\n",
+	       info.mem_alloc, info.mem_free,info.free_blocks);
+    elib_printf(to, "                 max_free(%d),  min_used(%d)\n",
+	       info.max_free, info.min_used);
+}
+
+/*
+** Allocate a least nb bytes with alignment a
+** Algorithm:
+**    1) Try locate a block which match exacly among the by direct index.
+**    2) Try using a fix block of greater size
+**    3) Try locate a block by searching in lists where block sizes
+**       X may vary between 2^i < X <= 2^(i+1)
+**
+** Reset memory to zero if clear is true
+*/
+static AllocatedBlock* allocate(EWord nb, EWord a, int clear)
+{
+    FreeBlock* p;
+    EWord nw;
+
+    if (a == ELIB_ALIGN) {
+	/*
+	 * Common case: Called by malloc(), realloc(), calloc().
+	 */
+	nw = nb < MIN_BYTE_SIZE ? MIN_ALIGN_SIZE : ALIGN_SIZE(nb);
+
+	if ((p = alloc_block(nw)) == 0)
+	    return NULL;
+    } else {
+	/*
+	 * Special case: Called by memalign().
+	 */
+	EWord asz, szp, szq, tmpsz;
+	FreeBlock *q;
+
+	if ((p = alloc_block((1+MIN_ALIGN_SIZE)*sizeof(EWord)+a-1+nb)) == 0)
+	    return NULL;
+
+	asz = a - ((EWord) ((AllocatedBlock *)p)->v) % a;
+
+	if (asz != a) {
+	    /* Enforce the alignment requirement by cutting of a free
+	       block at the beginning of the block. */
+
+	    if (asz < (1+MIN_ALIGN_SIZE)*sizeof(EWord) && !IS_FREE_ABOVE(p)) {
+		/* Not enough room to cut of a free block;
+		   increase align size */
+		asz += (((1+MIN_ALIGN_SIZE)*sizeof(EWord) + a - 1)/a)*a;
+	    }
+
+	    szq = ALIGN_SIZE(asz - sizeof(EWord));
+	    szp = SIZEOF(p) - szq - 1;
+
+	    q = p;
+	    p = (FreeBlock*) (((EWord*) q) + szq + 1);
+	    p->hdr = FREE_ABOVE_BIT | FREE_BIT | szp;
+
+	    if (IS_FREE_ABOVE(q)) { /* This should not be possible I think,
+				       but just in case... */
+		tmpsz = SIZEOF_ABOVE(q) + 1;
+		szq += tmpsz;
+		q = (FreeBlock*) (((EWord*) q) - tmpsz);
+		unlink_free_block((Block_t *) q);
+		q->hdr = (q->hdr & FREE_ABOVE_BIT) | FREE_BIT | szq;
+	    }
+	    mark_free(q, szq);
+	    link_free_block((Block_t *) q);
+
+	} /* else already had the correct alignment */
+ 
+	nw = nb < MIN_BYTE_SIZE ? MIN_ALIGN_SIZE : ALIGN_SIZE(nb);
+    }
+
+    split_block(p, nw, SIZEOF(p));
+
+    STAT_ALLOCED_BLOCK(SIZEOF(p));
+
+    if (clear) {
+	EWord* pp = ((AllocatedBlock*)p)->v;
+
+	while(nw--)
+	    *pp++ = 0;
+    }
+
+    return (AllocatedBlock*) p;
+}
+
+
+/*
+** Deallocate memory pointed to by p
+** 1. Merge with block above if this block is free
+** 2. Merge with block below if this block is free
+** Link the block to the correct free list
+**
+** p points to the block header!
+**
+*/
+static void deallocate(AllocatedBlock* p, int stat_count)
+{
+    FreeBlock* q;
+    EWord szq;
+    EWord szp;
+
+    szp = SIZEOF(p);
+
+    if (stat_count)
+	STAT_FREED_BLOCK(SIZEOF(p));
+
+    if (IS_FREE_ABOVE(p)) {
+	szq = SIZEOF_ABOVE(p);
+	q = (FreeBlock*) ( ((EWord*) p) - szq - 1);
+	unlink_free_block((Block_t *) q);
+
+	p = (AllocatedBlock*) q;
+	szp += (szq + 1);
+    }
+    q = (FreeBlock*) (p->v + szp);
+    if (IS_FREE(q)) {
+	szq = SIZEOF(q);
+	unlink_free_block((Block_t *) q);
+	szp += (szq + 1);
+    }
+    else
+	q->hdr |= FREE_ABOVE_BIT;
+
+    /* The block above p can NEVER be free !!! */
+    p->hdr = FREE_BIT | szp;
+    p->v[szp-1] = szp;
+
+    link_free_block((Block_t *) p);
+}
+
+/*
+** Reallocate memory
+** If preserve is true then data is moved if neccesary
+*/
+static AllocatedBlock* reallocate(AllocatedBlock* p, EWord nb, int preserve)
+{
+    EWord szp;
+    EWord szq;
+    EWord sz;
+    EWord nw;
+    FreeBlock* q;
+
+    if (nb < MIN_BYTE_SIZE)
+	nw = MIN_ALIGN_SIZE;
+    else
+	nw = ALIGN_SIZE(nb);
+
+    sz = szp = SIZEOF(p);
+
+    STAT_FREED_BLOCK(szp);
+
+    /* Merge with block below */
+    q = (FreeBlock*) (p->v + szp);
+    if (IS_FREE(q)) {
+	szq = SIZEOF(q);
+	unlink_free_block((Block_t *) q);
+	szp += (szq + 1);
+    }
+
+    if (nw <= szp) {
+	split_block((FreeBlock *) p, nw, szp);
+	STAT_ALLOCED_BLOCK(SIZEOF(p));
+	return p;
+    }
+    else {
+	EWord* dp = p->v;
+	AllocatedBlock* npp;
+
+	if (IS_FREE_ABOVE(p)) {
+	    szq = SIZEOF_ABOVE(p);
+	    if (szq + szp + 1 >= nw) {
+		q = (FreeBlock*) (((EWord*) p) - szq - 1);
+		unlink_free_block((Block_t * )q);
+		szp += (szq + 1);
+		p = (AllocatedBlock*) q;
+
+		if (preserve) {
+		    EWord* pp = p->v;
+		    while(sz--)
+			*pp++ = *dp++;
+		}
+		split_block((FreeBlock *) p, nw, szp);
+		STAT_ALLOCED_BLOCK(SIZEOF(p));
+		return p;
+	    }
+	}
+
+	/*
+	 * Update p so that allocate() and deallocate() works.
+	 * (Note that allocate() may call expand_sbrk(), which in
+	 * in turn calls deallocate().)
+	 */
+
+	p->hdr = (p->hdr & FREE_ABOVE_BIT) | szp;
+	p->v[szp] &= ~FREE_ABOVE_BIT;
+
+	npp = allocate(nb, ELIB_ALIGN, 0);
+	if(npp == NULL)
+	    return NULL;
+	if (preserve) {
+	    EWord* pp = npp->v;
+	    while(sz--)
+		*pp++ = *dp++;
+	}
+	deallocate(p, 0);
+	return npp;
+    }
+}
+
+/*
+** What malloc() and friends should do (and return) when the heap is
+** exhausted.  [sverkerw]
+*/
+static void* heap_exhausted(void)
+{
+    /* Choose behaviour */
+#if 0
+    /* Crash-and-burn --- leave a usable corpse (hopefully) */
+    abort();
+#endif    
+    /* The usual ANSI-compliant behaviour */
+    return NULL;
+}
+
+/*
+** Allocate size bytes of memory
+*/
+void* ELIB_PREFIX(malloc, (size_t nb))
+{
+    void *res;
+    AllocatedBlock* p;
+
+    erts_mtx_lock(&malloc_mutex);
+    if (elib_need_init)
+	locked_elib_init(NULL,(EWord)0);
+
+    if (nb == 0)
+	res = NULL;
+    else if ((p = allocate(nb, ELIB_ALIGN, 0)) != 0) {
+	ELIB_ALIGN_CHECK(p->v);
+	res = p->v;
+    }
+    else
+	res = heap_exhausted();
+
+    erts_mtx_unlock(&malloc_mutex);
+
+    return res;
+}
+
+
+void* ELIB_PREFIX(calloc, (size_t nelem, size_t size))
+{
+    void *res;
+    int nb;
+    AllocatedBlock* p;
+    
+    erts_mtx_lock(&malloc_mutex);
+    if (elib_need_init)
+	locked_elib_init(NULL,(EWord)0);
+
+    if ((nb = nelem * size) == 0)
+	res = NULL;
+    else if ((p = allocate(nb, ELIB_ALIGN, 1)) != 0) {
+	ELIB_ALIGN_CHECK(p->v);
+	res = p->v;
+    }
+    else
+	res = heap_exhausted();
+
+    erts_mtx_unlock(&malloc_mutex);
+
+    return res;
+}
+
+/*
+** Free memory allocated by malloc
+*/
+
+void ELIB_PREFIX(free, (EWord* p))
+{
+    erts_mtx_lock(&malloc_mutex);
+    if (elib_need_init)
+	locked_elib_init(NULL,(EWord)0);
+
+    if (p != 0)
+	deallocate((AllocatedBlock*)(p-1), 1);
+
+    erts_mtx_unlock(&malloc_mutex);
+}
+
+void ELIB_PREFIX(cfree, (EWord* p))
+{
+    ELIB_PREFIX(free, (p));
+}
+
+
+/*
+** Realloc the memory allocated in p to nb number of bytes
+**
+*/
+
+void* ELIB_PREFIX(realloc, (EWord* p, size_t nb))
+{
+    void *res = NULL;
+    AllocatedBlock* pp;
+
+    erts_mtx_lock(&malloc_mutex);
+    if (elib_need_init)
+	locked_elib_init(NULL,(EWord)0);
+
+    if (p != 0) {
+	pp = (AllocatedBlock*) (p-1);
+	if (nb > 0) {
+	    if ((pp = reallocate(pp, nb, 1)) != 0) {
+		ELIB_ALIGN_CHECK(pp->v);
+		res = pp->v;
+	    }
+	}
+	else
+	    deallocate(pp, 1);
+    }
+    else if (nb > 0) {
+	if ((pp = allocate(nb, ELIB_ALIGN, 0)) != 0) {
+	    ELIB_ALIGN_CHECK(pp->v);
+	    res = pp->v;
+	}
+	else
+	    res = heap_exhausted();
+    }
+
+    erts_mtx_unlock(&malloc_mutex);
+
+    return res;
+}
+
+/*
+** Resize the memory area pointed to by p with nb number of bytes
+*/
+void* ELIB_PREFIX(memresize, (EWord* p, int nb))
+{
+    void *res = NULL;
+    AllocatedBlock* pp;
+
+    erts_mtx_lock(&malloc_mutex);
+    if (elib_need_init)
+	locked_elib_init(NULL,(EWord)0);
+
+    if (p != 0) {
+	pp = (AllocatedBlock*) (p-1);
+	if (nb > 0) {
+	    if ((pp = reallocate(pp, nb, 0)) != 0) {
+		ELIB_ALIGN_CHECK(pp->v);
+		res = pp->v;
+	    }
+	}
+	else
+	    deallocate(pp, 1);
+    }
+    else if (nb > 0) {
+	if ((pp = allocate(nb, ELIB_ALIGN, 0)) != 0) {
+	    ELIB_ALIGN_CHECK(pp->v);
+	    res = pp->v;
+	}
+	else
+	    res = heap_exhausted();
+    }
+
+    erts_mtx_unlock(&malloc_mutex);
+
+    return res;
+}
+
+
+/* Create aligned memory a must be a power of 2 !!! */
+
+void* ELIB_PREFIX(memalign, (int a, int nb))
+{
+    void *res;
+    AllocatedBlock* p;
+
+    erts_mtx_lock(&malloc_mutex);
+    if (elib_need_init)
+	locked_elib_init(NULL,(EWord)0);
+
+    if (nb == 0 || a <= 0)
+	res = NULL;
+    else if ((p = allocate(nb, a, 0)) != 0) {
+	ALIGN_CHECK(a, p->v);
+	res = p->v;
+    }
+    else
+	res = heap_exhausted();
+
+    erts_mtx_unlock(&malloc_mutex);
+
+    return res;
+}
+
+void* ELIB_PREFIX(valloc, (int nb))
+{
+    return ELIB_PREFIX(memalign, (page_size, nb));
+}
+
+
+void* ELIB_PREFIX(pvalloc, (int nb))
+{
+    return ELIB_PREFIX(memalign, (page_size, PAGES(nb)*page_size));
+}
+/* Return memory size for pointer p in bytes */
+
+int ELIB_PREFIX(memsize, (p))
+EWord* p;
+{
+    return SIZEOF((AllocatedBlock*)(p-1))*4;
+}
+
+
+/*
+** --------------------------------------------------------------------------
+**   DEBUG LIBRARY
+** --------------------------------------------------------------------------
+*/
+
+#ifdef ELIB_DEBUG
+
+#define IN_HEAP(p)  (((p) >= (char*) eheap) && (p) < (char*) eheap_top)
+/*
+** ptr_to_block: return the pointer to heap block pointed into by ptr
+** Returns 0 if not pointing into a block
+*/
+
+static EWord* ptr_to_block(char* ptr)
+{
+    AllocatedBlock* p = heap_head;
+    EWord sz;
+
+    while((sz = SIZEOF(p)) != 0) {
+	if ((ptr >= (char*) p->v) && (ptr < (char*)(p->v+sz)))
+	    return p->v;
+	p = (AllocatedBlock*) (p->v + sz);
+    }
+    return 0;
+}
+
+/*
+** Validate a pointer
+** returns:
+**      0  - if points to start of a block
+**      1  - if points outsize heap
+**     -1  - if points inside block
+**
+*/
+static int check_pointer(char* ptr)
+{
+    if (IN_HEAP(ptr)) {
+	if (ptr_to_block(ptr) == 0)
+	    return 1;
+	return 0;
+    }
+    return -1;
+}
+
+/*
+** Validate a memory area
+** returns:
+**      0 - if area is included in a block
+**     -1 - if area overlap a heap block
+**      1 - if area is outside heap
+*/
+static int check_area(char* ptr, int n)
+{
+    if (IN_HEAP(ptr)) {
+	if (IN_HEAP(ptr+n-1)) {
+	    EWord* p1 = ptr_to_block(ptr);
+	    EWord* p2 = ptr_to_block(ptr+n-1);
+
+	    if (p1 == p2)
+		return (p1 == 0) ? -1 : 0;
+	    return -1;
+	}
+    }
+    else if (IN_HEAP(ptr+n-1))
+	return -1;
+    return 1;
+}
+
+/*
+** Check if a block write will overwrite heap block
+*/
+static void check_write(char* ptr, int n, char* file, int line, char* fun)
+{
+    if (check_area(ptr, n) == -1) {
+	elib_printf(stderr, "RUNTIME ERROR: %s heap overwrite\n", fun);
+	elib_printf(stderr, "File: %s Line: %d\n", file, line);
+	ELIB_FAILURE;
+    }
+}
+
+/*
+** Check if a pointer is an allocated object
+*/
+static void check_allocated_block(char* ptr, char* file, int line, char* fun)
+{
+    EWord* q;
+
+    if (!IN_HEAP(ptr) || ((q=ptr_to_block(ptr)) == 0) || (ptr != (char*) q)) {
+	elib_printf(stderr, "RUNTIME ERROR: %s non heap pointer\n", fun);
+	elib_printf(stderr, "File: %s Line: %d\n", file, line);
+	ELIB_FAILURE;
+    }
+
+    if (IS_FREE((AllocatedBlock*)(q-1))) {
+	elib_printf(stderr, "RUNTIME ERROR: %s free pointer\n", fun);
+	elib_printf(stderr, "File: %s Line: %d\n", file, line);
+	ELIB_FAILURE;
+    }
+
+}
+
+/*
+** --------------------------------------------------------------------------
+**  DEBUG VERSIONS (COMPILED WITH THE ELIB.H)
+** --------------------------------------------------------------------------
+*/
+
+void* elib_dbg_malloc(int n, char* file, int line)
+{
+    return elib__malloc(n);
+}
+
+void* elib_dbg_calloc(int n, int s, char* file, int line)
+{
+    return elib__calloc(n, s);
+}
+
+void* elib_dbg_realloc(EWord* p, int n, char* file, int line)
+{
+    if (p == 0)
+	return elib__malloc(n);
+    check_allocated_block(p, file, line, "elib_realloc");
+    return elib__realloc(p, n);
+}
+
+void elib_dbg_free(EWord* p, char* file, int line)
+{
+    if (p == 0)
+	return;
+    check_allocated_block(p, file, line, "elib_free");
+    elib__free(p);
+}
+
+void elib_dbg_cfree(EWord* p, char* file, int line)
+{
+    if (p == 0)
+	return;
+    check_allocated_block(p, file, line, "elib_free");
+    elib__cfree(p);
+}
+
+void* elib_dbg_memalign(int a, int n, char* file, int line)
+{
+    return elib__memalign(a, n);
+}
+
+void* elib_dbg_valloc(int n, char* file, int line)
+{
+    return elib__valloc(n);
+}
+
+void* elib_dbg_pvalloc(int n, char* file, int line)
+{
+    return elib__pvalloc(n);
+}
+
+void* elib_dbg_memresize(EWord* p, int n, char* file, int line)
+{
+    if (p == 0)
+	return elib__malloc(n);
+    check_allocated_block(p, file, line, "elib_memresize");
+    return elib__memresize(p, n);
+}
+
+int elib_dbg_memsize(void* p, char* file, int line)
+{
+    check_allocated_block(p, file, line, "elib_memsize");
+    return elib__memsize(p);
+}
+
+/*
+** --------------------------------------------------------------------------
+**  LINK TIME FUNCTIONS (NOT COMPILED CALLS)
+** --------------------------------------------------------------------------
+*/
+
+void* elib_malloc(int n)
+{
+    return elib_dbg_malloc(n, "", -1);
+}
+
+void* elib_calloc(int n, int s)
+{
+    return elib_dbg_calloc(n, s, "", -1);
+}
+
+void* elib_realloc(EWord* p, int n)
+{
+    return elib_dbg_realloc(p, n, "", -1);
+}
+
+void elib_free(EWord* p)
+{
+    elib_dbg_free(p, "", -1);
+}
+
+void elib_cfree(EWord* p)
+{
+    elib_dbg_cfree(p, "", -1);
+}
+
+void* elib_memalign(int a, int n)
+{
+    return elib_dbg_memalign(a, n, "", -1);
+}
+
+void* elib_valloc(int n)
+{
+    return elib_dbg_valloc(n, "", -1);
+}
+
+void* elib_pvalloc(int n)
+{
+    return elib_dbg_pvalloc(n, "", -1);
+}
+
+void* elib_memresize(EWord* p, int n)
+{
+    return elib_dbg_memresize(p, n, "", -1);
+}
+
+
+int elib_memsize(EWord* p)
+{
+    return elib_dbg_memsize(p, "", -1);
+}
+
+#endif /* ELIB_DEBUG */
+
+/*
+** --------------------------------------------------------------------------
+** Map c library functions to elib
+** --------------------------------------------------------------------------
+*/
+
+#if defined(ELIB_ALLOC_IS_CLIB)
+void* malloc(size_t nb)
+{
+    return elib_malloc(nb);
+}
+
+void* calloc(size_t nelem, size_t size)
+{
+    return elib_calloc(nelem, size);
+}
+
+
+void free(void *p)
+{
+    elib_free(p);
+}
+
+void cfree(void *p)
+{
+    elib_cfree(p);
+}
+
+void* realloc(void* p, size_t nb)
+{
+    return elib_realloc(p, nb);
+}
+
+
+void* memalign(size_t a, size_t s)
+{
+    return elib_memalign(a, s);
+}
+
+void* valloc(size_t nb)
+{
+    return elib_valloc(nb);
+}
+
+void* pvalloc(size_t nb)
+{
+    return elib_pvalloc(nb);
+}
+
+#if 0
+void* memresize(void* p, int nb)
+{
+    return elib_memresize(p, nb);
+}
+
+int memsize(void* p)
+{
+    return elib_memsize(p);
+}
+#endif
+#endif /* ELIB_ALLOC_IS_CLIB */
+
+#endif /* ENABLE_ELIB_MALLOC */
+
+void elib_ensure_initialized(void)
+{
+#ifdef ENABLE_ELIB_MALLOC
+#ifndef ELIB_DONT_INITIALIZE
+    elib_init(NULL, 0);
+#endif
+#endif
+}
+
+#ifdef ENABLE_ELIB_MALLOC
+/**
+ ** A Slightly modified version of the "address order best fit" algorithm
+ ** used in erl_bestfit_alloc.c. Comments refer to that implementation.
+ **/
+
+/*
+ * Description:	A combined "address order best fit"/"best fit" allocator
+ *              based on a Red-Black (binary search) Tree. The search,
+ *              insert, and delete operations are all O(log n) operations
+ *              on a Red-Black Tree. In the "address order best fit" case
+ *              n equals number of free blocks, and in the "best fit" case
+ *              n equals number of distinct sizes of free blocks. Red-Black
+ *              Trees are described in "Introduction to Algorithms", by
+ *              Thomas H. Cormen, Charles E. Leiserson, and
+ *              Ronald L. Riverest.
+ *
+ *              This module is a callback-module for erl_alloc_util.c
+ *
+ * Author: 	Rickard Green
+ */
+
+#ifdef DEBUG
+#if 0
+#define HARD_DEBUG
+#endif
+#else
+#undef HARD_DEBUG
+#endif
+
+#define SZ_MASK			SIZE_MASK
+#define FLG_MASK		(~(SZ_MASK))
+
+#define BLK_SZ(B)  (*((Block_t *) (B)) & SZ_MASK)
+
+#define TREE_NODE_FLG		(((Uint) 1) << 0)
+#define RED_FLG			(((Uint) 1) << 1)
+#ifdef HARD_DEBUG
+#  define LEFT_VISITED_FLG	(((Uint) 1) << 2)
+#  define RIGHT_VISITED_FLG	(((Uint) 1) << 3)
+#endif
+
+#define IS_TREE_NODE(N)		(((RBTree_t *) (N))->flags & TREE_NODE_FLG)
+#define IS_LIST_ELEM(N)		(!IS_TREE_NODE(((RBTree_t *) (N))))
+
+#define SET_TREE_NODE(N)	(((RBTree_t *) (N))->flags |= TREE_NODE_FLG)
+#define SET_LIST_ELEM(N)	(((RBTree_t *) (N))->flags &= ~TREE_NODE_FLG)
+
+#define IS_RED(N)		(((RBTree_t *) (N)) \
+				 && ((RBTree_t *) (N))->flags & RED_FLG)
+#define IS_BLACK(N)		(!IS_RED(((RBTree_t *) (N))))
+
+#define SET_RED(N)		(((RBTree_t *) (N))->flags |= RED_FLG)
+#define SET_BLACK(N)		(((RBTree_t *) (N))->flags &= ~RED_FLG)
+
+#undef ASSERT
+#define ASSERT ASSERT_EXPR
+
+#if 1
+#define RBT_ASSERT	ASSERT
+#else
+#define RBT_ASSERT(x)
+#endif
+
+
+#ifdef HARD_DEBUG
+static RBTree_t * check_tree(Uint);
+#endif
+
+#ifdef ERTS_INLINE
+#  ifndef ERTS_CAN_INLINE
+#    define ERTS_CAN_INLINE 1
+#  endif
+#else
+#  if defined(__GNUC__)
+#    define ERTS_CAN_INLINE 1
+#    define ERTS_INLINE __inline__
+#  elif defined(__WIN32__)
+#    define ERTS_CAN_INLINE 1
+#    define ERTS_INLINE __inline
+#  else
+#    define ERTS_CAN_INLINE 0
+#    define ERTS_INLINE
+#  endif
+#endif
+
+/* Types... */
+#if 0
+typedef struct RBTree_t_ RBTree_t;
+
+struct RBTree_t_ {
+    Block_t hdr;
+    Uint flags;
+    RBTree_t *parent;
+    RBTree_t *left;
+    RBTree_t *right;
+};
+#endif
+
+#if 0
+typedef struct {
+    RBTree_t t;
+    RBTree_t *next;
+} RBTreeList_t;
+
+#define LIST_NEXT(N) (((RBTreeList_t *) (N))->next)
+#define LIST_PREV(N) (((RBTreeList_t *) (N))->t.parent)
+#endif
+
+#ifdef DEBUG
+
+/* Destroy all tree fields */
+#define DESTROY_TREE_NODE(N)						\
+  sys_memset((void *) (((Block_t *) (N)) + 1),				\
+	     0xff,							\
+	     (sizeof(RBTree_t) - sizeof(Block_t)))
+
+/* Destroy all tree and list fields */
+#define DESTROY_LIST_ELEM(N)						\
+  sys_memset((void *) (((Block_t *) (N)) + 1),				\
+	     0xff,							\
+	     (sizeof(RBTreeList_t) - sizeof(Block_t)))
+
+#else
+
+#define DESTROY_TREE_NODE(N)
+#define DESTROY_LIST_ELEM(N)
+
+#endif
+
+
+/*
+ * Red-Black Tree operations needed
+ */
+
+static ERTS_INLINE void
+left_rotate(RBTree_t **root, RBTree_t *x)
+{
+    RBTree_t *y = x->right;
+    x->right = y->left;
+    if (y->left)
+	y->left->parent = x;
+    y->parent = x->parent;
+    if (!y->parent) {
+	RBT_ASSERT(*root == x);
+	*root = y;
+    }
+    else if (x == x->parent->left)
+	x->parent->left = y;
+    else {
+	RBT_ASSERT(x == x->parent->right);
+	x->parent->right = y;
+    }
+    y->left = x;
+    x->parent = y;
+}
+
+static ERTS_INLINE void
+right_rotate(RBTree_t **root, RBTree_t *x)
+{
+    RBTree_t *y = x->left;
+    x->left = y->right;
+    if (y->right)
+	y->right->parent = x;
+    y->parent = x->parent;
+    if (!y->parent) {
+	RBT_ASSERT(*root == x);
+	*root = y;
+    }
+    else if (x == x->parent->right)
+	x->parent->right = y;
+    else {
+	RBT_ASSERT(x == x->parent->left);
+	x->parent->left = y;
+    }
+    y->right = x;
+    x->parent = y;
+}
+
+
+/*
+ * Replace node x with node y
+ * NOTE: block header of y is not changed
+ */
+static ERTS_INLINE void
+replace(RBTree_t **root, RBTree_t *x, RBTree_t *y)
+{
+
+    if (!x->parent) {
+	RBT_ASSERT(*root == x);
+	*root = y;
+    }
+    else if (x == x->parent->left)
+	x->parent->left = y;
+    else {
+	RBT_ASSERT(x == x->parent->right);
+	x->parent->right = y;
+    }
+    if (x->left) {
+	RBT_ASSERT(x->left->parent == x);
+	x->left->parent = y;
+    }
+    if (x->right) {
+	RBT_ASSERT(x->right->parent == x);
+	x->right->parent = y;
+    }
+
+    y->flags	= x->flags;
+    y->parent	= x->parent;
+    y->right	= x->right;
+    y->left	= x->left;
+
+    DESTROY_TREE_NODE(x);
+
+}
+
+static void
+tree_insert_fixup(RBTree_t *blk)
+{
+    RBTree_t *x = blk, *y;
+
+    /*
+     * Rearrange the tree so that it satisfies the Red-Black Tree properties
+     */
+
+    RBT_ASSERT(x != root && IS_RED(x->parent));
+    do {
+
+	/*
+	 * x and its parent are both red. Move the red pair up the tree
+	 * until we get to the root or until we can separate them.
+	 */
+
+	RBT_ASSERT(IS_RED(x));
+	RBT_ASSERT(IS_BLACK(x->parent->parent));
+	RBT_ASSERT(x->parent->parent);
+
+	if (x->parent == x->parent->parent->left) {
+	    y = x->parent->parent->right;
+	    if (IS_RED(y)) {
+		SET_BLACK(y);
+		x = x->parent;
+		SET_BLACK(x);
+		x = x->parent;
+		SET_RED(x);
+	    }
+	    else {
+
+		if (x == x->parent->right) {
+		    x = x->parent;
+		    left_rotate(&root, x);
+		}
+
+		RBT_ASSERT(x == x->parent->parent->left->left);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent));
+		RBT_ASSERT(IS_BLACK(x->parent->parent));
+		RBT_ASSERT(IS_BLACK(y));
+
+		SET_BLACK(x->parent);
+		SET_RED(x->parent->parent);
+		right_rotate(&root, x->parent->parent);
+
+		RBT_ASSERT(x == x->parent->left);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent->right));
+		RBT_ASSERT(IS_BLACK(x->parent));
+		break;
+	    }
+	}
+	else {
+	    RBT_ASSERT(x->parent == x->parent->parent->right);
+	    y = x->parent->parent->left;
+	    if (IS_RED(y)) {
+		SET_BLACK(y);
+		x = x->parent;
+		SET_BLACK(x);
+		x = x->parent;
+		SET_RED(x);
+	    }
+	    else {
+
+		if (x == x->parent->left) {
+		    x = x->parent;
+		    right_rotate(&root, x);
+		}
+
+		RBT_ASSERT(x == x->parent->parent->right->right);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent));
+		RBT_ASSERT(IS_BLACK(x->parent->parent));
+		RBT_ASSERT(IS_BLACK(y));
+
+		SET_BLACK(x->parent);
+		SET_RED(x->parent->parent);
+		left_rotate(&root, x->parent->parent);
+
+		RBT_ASSERT(x == x->parent->right);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent->left));
+		RBT_ASSERT(IS_BLACK(x->parent));
+		break;
+	    }
+	}
+    } while (x != root && IS_RED(x->parent));
+
+    SET_BLACK(root);
+}
+
+static void
+unlink_free_block(Block_t *del)
+{
+    Uint spliced_is_black;
+    RBTree_t *x, *y, *z = (RBTree_t *) del;
+    RBTree_t null_x; /* null_x is used to get the fixup started when we
+			splice out a node without children. */
+
+    null_x.parent = NULL;
+
+#ifdef HARD_DEBUG
+    check_tree(0);
+#endif
+
+    /* Remove node from tree... */
+
+    /* Find node to splice out */
+    if (!z->left || !z->right)
+	y = z;
+    else
+	/* Set y to z:s successor */
+	for(y = z->right; y->left; y = y->left);
+    /* splice out y */
+    x = y->left ? y->left : y->right;
+    spliced_is_black = IS_BLACK(y);
+    if (x) {
+	x->parent = y->parent;
+    }
+    else if (!x && spliced_is_black) {
+	x = &null_x;
+	x->flags = 0;
+	SET_BLACK(x);
+	x->right = x->left = NULL;
+	x->parent = y->parent;
+	y->left = x;
+    }
+
+    if (!y->parent) {
+	RBT_ASSERT(root == y);
+	root = x;
+    }
+    else if (y == y->parent->left)
+	y->parent->left = x;
+    else {
+	RBT_ASSERT(y == y->parent->right);
+	y->parent->right = x;
+    }
+    if (y != z) {
+	/* We spliced out the successor of z; replace z by the successor */
+	replace(&root, z, y);
+    }
+
+    if (spliced_is_black) {
+	/* We removed a black node which makes the resulting tree
+	   violate the Red-Black Tree properties. Fixup tree... */
+
+	while (IS_BLACK(x) && x->parent) {
+
+	    /*
+	     * x has an "extra black" which we move up the tree
+	     * until we reach the root or until we can get rid of it.
+	     *
+	     * y is the sibbling of x
+	     */
+
+	    if (x == x->parent->left) {
+		y = x->parent->right;
+		RBT_ASSERT(y);
+		if (IS_RED(y)) {
+		    RBT_ASSERT(y->right);
+		    RBT_ASSERT(y->left);
+		    SET_BLACK(y);
+		    RBT_ASSERT(IS_BLACK(x->parent));
+		    SET_RED(x->parent);
+		    left_rotate(&root, x->parent);
+		    y = x->parent->right;
+		}
+		RBT_ASSERT(y);
+		RBT_ASSERT(IS_BLACK(y));
+		if (IS_BLACK(y->left) && IS_BLACK(y->right)) {
+		    SET_RED(y);
+		    x = x->parent;
+		}
+		else {
+		    if (IS_BLACK(y->right)) {
+			SET_BLACK(y->left);
+			SET_RED(y);
+			right_rotate(&root, y);
+			y = x->parent->right;
+		    }
+		    RBT_ASSERT(y);
+		    if (IS_RED(x->parent)) {
+
+			SET_BLACK(x->parent);
+			SET_RED(y);
+		    }
+		    RBT_ASSERT(y->right);
+		    SET_BLACK(y->right);
+		    left_rotate(&root, x->parent);
+		    x = root;
+		    break;
+		}
+	    }
+	    else {
+		RBT_ASSERT(x == x->parent->right);
+		y = x->parent->left;
+		RBT_ASSERT(y);
+		if (IS_RED(y)) {
+		    RBT_ASSERT(y->right);
+		    RBT_ASSERT(y->left);
+		    SET_BLACK(y);
+		    RBT_ASSERT(IS_BLACK(x->parent));
+		    SET_RED(x->parent);
+		    right_rotate(&root, x->parent);
+		    y = x->parent->left;
+		}
+		RBT_ASSERT(y);
+		RBT_ASSERT(IS_BLACK(y));
+		if (IS_BLACK(y->right) && IS_BLACK(y->left)) {
+		    SET_RED(y);
+		    x = x->parent;
+		}
+		else {
+		    if (IS_BLACK(y->left)) {
+			SET_BLACK(y->right);
+			SET_RED(y);
+			left_rotate(&root, y);
+			y = x->parent->left;
+		    }
+		    RBT_ASSERT(y);
+		    if (IS_RED(x->parent)) {
+			SET_BLACK(x->parent);
+			SET_RED(y);
+		    }
+		    RBT_ASSERT(y->left);
+		    SET_BLACK(y->left);
+		    right_rotate(&root, x->parent);
+		    x = root;
+		    break;
+		}
+	    }
+	}
+	SET_BLACK(x);
+
+	if (null_x.parent) {
+	    if (null_x.parent->left == &null_x)
+		null_x.parent->left = NULL;
+	    else {
+		RBT_ASSERT(null_x.parent->right == &null_x);
+		null_x.parent->right = NULL;
+	    }
+	    RBT_ASSERT(!null_x.left);
+	    RBT_ASSERT(!null_x.right);
+	}
+	else if (root == &null_x) {
+	    root = NULL;
+	    RBT_ASSERT(!null_x.left);
+	    RBT_ASSERT(!null_x.right);
+	}
+    }
+
+
+    DESTROY_TREE_NODE(del);
+
+#ifdef HARD_DEBUG
+    check_tree(0);
+#endif
+
+}
+
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+ * "Address order best fit" specific callbacks.                              *
+\*                                                                           */
+
+static void
+link_free_block(Block_t *block)
+{
+    RBTree_t *blk = (RBTree_t *) block;
+    Uint blk_sz = BLK_SZ(blk);
+
+    blk->flags	= 0;
+    blk->left	= NULL;
+    blk->right	= NULL;
+
+    if (!root) {
+	blk->parent = NULL;
+	SET_BLACK(blk);
+	root = blk;
+    } else {
+	RBTree_t *x = root;
+	while (1) {
+	    Uint size;
+
+	    size = BLK_SZ(x);
+
+	    if (blk_sz < size || (blk_sz == size && blk < x)) {
+		if (!x->left) {
+		    blk->parent = x;
+		    x->left = blk;
+		    break;
+		}
+		x = x->left;
+	    }
+	    else {
+		if (!x->right) {
+		    blk->parent = x;
+		    x->right = blk;
+		    break;
+		}
+		x = x->right;
+	    }
+
+	}
+
+	/* Insert block into size tree */
+	RBT_ASSERT(blk->parent);
+
+	SET_RED(blk);
+	if (IS_RED(blk->parent)) {
+	    tree_insert_fixup(blk);
+	}
+    }
+
+#ifdef HARD_DEBUG
+    check_tree(0);
+#endif
+}
+
+
+static Block_t *
+get_free_block(Uint size)
+{
+    RBTree_t *x = root;
+    RBTree_t *blk = NULL;
+    Uint blk_sz;
+
+    while (x) {
+	blk_sz = BLK_SZ(x);
+	if (blk_sz < size) {
+	    x = x->right;
+	}
+	else {
+	    blk = x;
+	    x = x->left;
+	}
+    }
+    
+    if (!blk)
+	return NULL;
+
+#ifdef HARD_DEBUG
+    ASSERT(blk == check_tree(size));
+#endif
+
+    unlink_free_block((Block_t *) blk);
+
+    return (Block_t *) blk;
+}
+
+
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+ * Debug functions                                                           *
+\*                                                                           */
+
+
+#ifdef HARD_DEBUG
+
+#define IS_LEFT_VISITED(FB)	((FB)->flags & LEFT_VISITED_FLG)
+#define IS_RIGHT_VISITED(FB)	((FB)->flags & RIGHT_VISITED_FLG)
+
+#define SET_LEFT_VISITED(FB)	((FB)->flags |= LEFT_VISITED_FLG)
+#define SET_RIGHT_VISITED(FB)	((FB)->flags |= RIGHT_VISITED_FLG)
+
+#define UNSET_LEFT_VISITED(FB)	((FB)->flags &= ~LEFT_VISITED_FLG)
+#define UNSET_RIGHT_VISITED(FB)	((FB)->flags &= ~RIGHT_VISITED_FLG)
+
+
+#if 0
+#  define PRINT_TREE
+#else
+#  undef PRINT_TREE
+#endif
+
+#ifdef PRINT_TREE
+static void print_tree(void);
+#endif
+
+/*
+ * Checks that the order between parent and children are correct,
+ * and that the Red-Black Tree properies are satisfied. if size > 0,
+ * check_tree() returns a node that satisfies "best fit" resp.
+ * "address order best fit".
+ *
+ * The Red-Black Tree properies are:
+ *   1. Every node is either red or black.
+ *   2. Every leaf (NIL) is black.
+ *   3. If a node is red, then both its children are black.
+ *   4. Every simple path from a node to a descendant leaf
+ *      contains the same number of black nodes.
+ */
+
+static RBTree_t *
+check_tree(Uint size)
+{
+    RBTree_t *res = NULL;
+    Sint blacks;
+    Sint curr_blacks;
+    RBTree_t *x;
+
+#ifdef PRINT_TREE
+    print_tree();
+#endif
+
+    if (!root)
+	return res;
+
+    x = root;
+    ASSERT(IS_BLACK(x));
+    ASSERT(!x->parent);
+    curr_blacks = 1;
+    blacks = -1;
+
+    while (x) {
+	if (!IS_LEFT_VISITED(x)) {
+	    SET_LEFT_VISITED(x);
+	    if (x->left) {
+		x = x->left;
+		if (IS_BLACK(x))
+		    curr_blacks++;
+		continue;
+	    }
+	    else {
+		if (blacks < 0)
+		    blacks = curr_blacks;
+		ASSERT(blacks == curr_blacks);
+	    }
+	}
+
+	if (!IS_RIGHT_VISITED(x)) {
+	    SET_RIGHT_VISITED(x);
+	    if (x->right) {
+		x = x->right;
+		if (IS_BLACK(x))
+		    curr_blacks++;
+		continue;
+	    }
+	    else {
+		if (blacks < 0)
+		    blacks = curr_blacks;
+		ASSERT(blacks == curr_blacks);
+	    }
+	}
+
+
+	if (IS_RED(x)) {
+	    ASSERT(IS_BLACK(x->right));
+	    ASSERT(IS_BLACK(x->left));
+	}
+
+	ASSERT(x->parent || x == root);
+
+	if (x->left) {
+	    ASSERT(x->left->parent == x);
+	    ASSERT(BLK_SZ(x->left) < BLK_SZ(x)
+		   || (BLK_SZ(x->left) == BLK_SZ(x) && x->left < x));
+	}
+
+	if (x->right) {
+	    ASSERT(x->right->parent == x);
+	    ASSERT(BLK_SZ(x->right) > BLK_SZ(x)
+		   || (BLK_SZ(x->right) == BLK_SZ(x) && x->right > x));
+	}
+
+	if (size && BLK_SZ(x) >= size) {
+	    if (!res
+		|| BLK_SZ(x) < BLK_SZ(res)
+		|| (BLK_SZ(x) == BLK_SZ(res) && x < res))
+		res = x;
+	}
+
+	UNSET_LEFT_VISITED(x);
+	UNSET_RIGHT_VISITED(x);
+	if (IS_BLACK(x))
+	    curr_blacks--;
+	x = x->parent;
+
+    }
+
+    ASSERT(curr_blacks == 0);
+
+    UNSET_LEFT_VISITED(root);
+    UNSET_RIGHT_VISITED(root);
+
+    return res;
+
+}
+
+
+#ifdef PRINT_TREE
+#define INDENT_STEP 2
+
+#include <stdio.h>
+
+static void
+print_tree_aux(RBTree_t *x, int indent)
+{
+    int i;
+
+    if (!x) {
+	for (i = 0; i < indent; i++) {
+	    putc(' ', stderr);
+	}
+	fprintf(stderr, "BLACK: nil\r\n");
+    }
+    else {
+	print_tree_aux(x->right, indent + INDENT_STEP);
+	for (i = 0; i < indent; i++) {
+	    putc(' ', stderr);
+	}
+	fprintf(stderr, "%s: sz=%lu addr=0x%lx\r\n",
+		IS_BLACK(x) ? "BLACK" : "RED",
+		BLK_SZ(x),
+		(Uint) x);
+	print_tree_aux(x->left,  indent + INDENT_STEP);
+    }
+}
+
+
+static void
+print_tree(void)
+{
+    fprintf(stderr, " --- Size-Adress tree begin ---\r\n");
+    print_tree_aux(root, 0);
+    fprintf(stderr, " --- Size-Adress tree end ---\r\n");
+}
+
+#endif
+
+#endif
+
+#endif /* ENABLE_ELIB_MALLOC */