erl_memory_trace_block_table.c

OTP是开放电信平台的简称

/* ``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 1000

typedef 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_DEBUG
static void check_table(emtbt_table *table);
#endif

static 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 void
block_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_DEBUG

static void
check_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

}

#endif

static INLINE void
link_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 int
resize_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;
}