diff options
Diffstat (limited to 'erts/emulator/beam/elib_malloc.c')
| -rw-r--r-- | erts/emulator/beam/elib_malloc.c | 2334 |
1 files changed, 0 insertions, 2334 deletions
diff --git a/erts/emulator/beam/elib_malloc.c b/erts/emulator/beam/elib_malloc.c deleted file mode 100644 index b18c48d8d6..0000000000 --- a/erts/emulator/beam/elib_malloc.c +++ /dev/null @@ -1,2334 +0,0 @@ -/* - * %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 */ |