/* ``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 via the world wide web 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. *  * The Initial Developer of the Original Code is Ericsson Utvecklings AB. * Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings * AB. All Rights Reserved.'' *  *     $Id$ *//* * Description:	 * * Author: 	Rickard Green *//* Headers to include ... */#ifdef HAVE_CONFIG_H#	include "config.h"#endif#include "erl_memory_trace_block_table.h"#include <errno.h>#undef HARD_DEBUG#undef REALLY_HARD_DEBUG#ifdef DEBUG#  define HARD_DEBUG 0#  define REALLY_HARD_DEBUG 0#else#  define HARD_DEBUG 0#  define REALLY_HARD_DEBUG 0#endif/* Some system specific defines ... */#if defined(__WIN32__) && !defined(__GNUC__)#	define INLINE __forceinline#else#	ifdef __GNUC__#		define INLINE __inline__#	else#		define INLINE#	endif#endif/* Our own assert() ... */#ifdef DEBUG#define ASSERT(A) ((void) ((A) ? 1 : assert_failed(__FILE__, __LINE__, #A)))#include <stdio.h>static int assert_failed(char *f, int l, char *a){    fprintf(stderr, "%s:%d: Assertion failed: %s\n", f, l, a);    abort();    return 0;}#else#define ASSERT(A) ((void) 1)#endif#define EMTBT_BLOCKS_PER_POOL 1000typedef struct emtbt_block_pool_ {    struct emtbt_block_pool_ *next;    emtbt_block blocks[1];} emtbt_block_pool;struct emtbt_table_ {    void * (*alloc)(size_t);    void * (*realloc)(void *, size_t);    void   (*free)(void *);    int is_64_bit;    int no_blocks;    int no_of_buckets;    int max_used_buckets;    int min_used_buckets;    int used_buckets;    int current_size_index;    emtbt_block *blocks;    emtbt_block ** buckets;    /* Fixed size allocation of blocks */    emtbt_block_pool *block_pools;    emtbt_block *free_blocks;    int blocks_per_pool;};static emtbt_block null_blk = {0};/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ * Block table                                                             * *                                                                         *\*                                                                         */#if HARD_DEBUGstatic void check_table(emtbt_table *table);#endifstatic emtbt_block *block_alloc_new_pool(emtbt_table *tab){    size_t size;    emtbt_block_pool *poolp;    size = sizeof(emtbt_block_pool) - sizeof(emtbt_block);    size += tab->blocks_per_pool*sizeof(emtbt_block);    poolp = (*tab->alloc)(size);    if (poolp) {	int i;	emtbt_block *blks;	poolp->next = tab->block_pools;	tab->block_pools = poolp;	blks = (emtbt_block *) poolp->blocks;	for (i = 1; i < tab->blocks_per_pool - 1; i++)	    blks[i].next = &blks[i + 1];	blks[tab->blocks_per_pool - 1].next = NULL;	tab->free_blocks = &blks[1];	return &blks[0];    }    return NULL;}static INLINE emtbt_block *block_alloc(emtbt_table *tab){    emtbt_block *res;#if HARD_DEBUG    check_table(tab);#endif    if (tab->free_blocks) {	res = tab->free_blocks;	tab->free_blocks = tab->free_blocks->next;    }    else {	res = block_alloc_new_pool(tab);    }#ifdef DEBUG    res->next = ((emtbt_block *) 0xfffffff0);    res->prev = ((emtbt_block *) 0xfffffff0);    res->bucket = ((emtbt_block **) 0xfffffff0);#endif#if HARD_DEBUG    check_table(tab);#endif    return res;}static INLINE voidblock_free(emtbt_table *tab, emtbt_block *bp){#if HARD_DEBUG    check_table(tab);#endif    bp->next = tab->free_blocks;    tab->free_blocks = bp;#if HARD_DEBUG    check_table(tab);#endif}#define PRIME0 ((usgnd_int_32) 268438039)#define PRIME1 ((usgnd_int_32) 268440479)#define PRIME2 ((usgnd_int_32) 268439161)#define PRIME3 ((usgnd_int_32) 268437017)#define MK_HASH(H, P, IS64)						\do {									\    (H) = (P) & 0xff;							\    (H) *= PRIME0;							\    (H) += ((P) >> 8) & 0xff;						\    (H) *= PRIME1;							\    (H) += ((P) >> 16) & 0xff;						\    (H) *= PRIME2;							\    (H) += ((P) >> 24) & 0xff;						\    (H) *= PRIME3;							\    if ((IS64)) {							\	(H) += ((P) >> 32) & 0xff;					\	(H) *= PRIME0;							\	(H) += ((P) >> 40) & 0xff;					\	(H) *= PRIME1;							\	(H) += ((P) >> 48) & 0xff;					\	(H) *= PRIME2;							\	(H) += ((P) >> 56) & 0xff;					\	(H) *= PRIME3;							\    }									\} while (0)static const int table_sizes[] = {    3203,    4813,    6421,    9643,    12853,    19289,    25717,    51437,    102877,    205759,    411527,    823117,    1646237,    3292489,    6584983,    13169977,    26339969,    52679969};#if HARD_DEBUGstatic voidcheck_table(emtbt_table *table){    int no_blocks;    emtbt_block *block, *prev_block;    no_blocks = 0;    block = table->blocks;    ASSERT(!block || !block->prev);    prev_block = NULL;    while (block) {	usgnd_int_32 hash;	MK_HASH(hash, block->pointer, table->is_64_bit);	ASSERT(hash == block->hash);	ASSERT(block->bucket - table->buckets	       == hash % table->no_of_buckets);	ASSERT(!prev_block || prev_block == block->prev);	prev_block = block;	block = block->next;	no_blocks++;	ASSERT(table->no_blocks >= no_blocks);    }    ASSERT(table->no_blocks == no_blocks);#if REALLY_HARD_DEBUG    {	int i;	for (i = 0; i < table->no_of_buckets; i++) {	    int bucket_end_found;	    emtbt_block **bucket;	    if (!table->buckets[i])		continue;	    bucket_end_found = 0;	    bucket = &table->buckets[i];	    for (block = table->blocks; block; block = block->next) {		if (block->bucket == bucket) {		    if (!block->prev || block->prev->bucket != bucket)			ASSERT(*bucket == block);		    if (!block->next || block->next->bucket != bucket)			bucket_end_found++;		}	    }	    ASSERT(bucket_end_found);	}    }#endif}#endifstatic INLINE voidlink_block(emtbt_table *table, emtbt_block **bucket, emtbt_block *block){    ASSERT(bucket);    block->bucket = bucket;    if (*bucket) {	block->next = *bucket;	block->prev = (*bucket)->prev;	if (block->prev)	    block->prev->next = block;	else	    table->blocks = block;	block->next->prev = block;    }    else {	block->next = table->blocks;	block->prev = NULL;	if (table->blocks)	    table->blocks->prev = block;	table->blocks = block;	table->used_buckets++;    }    *bucket = block;    table->no_blocks++;#if HARD_DEBUG    check_table(table);#endif}static intresize_table(emtbt_table *table, int new_no_of_buckets){#ifdef DEBUG    int org_no_blocks;#endif    int i;    emtbt_block *block;    emtbt_block **buckets;    if (new_no_of_buckets < table->no_of_buckets) {	/* shrink never fails */	buckets = (emtbt_block **) (*table->realloc)(table->buckets,						     (sizeof(emtbt_block *)						      * new_no_of_buckets));	if (!buckets)	    return 1;    }    else if (new_no_of_buckets > table->no_of_buckets) {	(*table->free)((void *) table->buckets);	buckets = (emtbt_block **) (*table->alloc)((sizeof(emtbt_block *)						    * new_no_of_buckets));	if (!buckets)	    return 0;    }    else	return 1;    table->buckets = buckets;    table->no_of_buckets = new_no_of_buckets;    table->max_used_buckets = (4*new_no_of_buckets)/5;    table->min_used_buckets = new_no_of_buckets/5;    table->used_buckets = 0;#ifdef DEBUG    org_no_blocks = table->no_blocks;#endif    table->no_blocks = 0;        for (i = 0; i < new_no_of_buckets; i++)	buckets[i] = NULL;    block = table->blocks;    table->blocks = NULL;    while (block) {	emtbt_block *next_block = block->next;	link_block(table,&table->buckets[block->hash%new_no_of_buckets],block);	block = next_block;    }    ASSERT(org_no_blocks == table->no_blocks);    return 1;}