/*---------------------------------------------------------------------------
| Copyright (C) 1999-2000 Jochen C. Loewer (loewerj@hotmail.com)
+----------------------------------------------------------------------------
|
| $Id$
|
|
| A special memory allocator, which uses pre-allocated / bit masked
| based administration of memory blocks with fixed sizes, like
| DOM nodes. This will hopefully save some memory.
|
|
| The contents of this file are subject to the Mozilla Public License
| Version 2.0 (the "License"); you may not use this file except in
| compliance with the License. You may obtain a copy of the License at
| http://www.mozilla.org/MPL/
|
| 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 Original Code is tDOM.
|
| The Initial Developer of the Original Code is Jochen Loewer
| Portions created by Jochen Loewer are Copyright (C) 1998, 1999
| Jochen Loewer. All Rights Reserved.
|
| Contributor(s):
|
|
| written by Jochen Loewer
| October, 2000
|
\--------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------
| Includes
|
\--------------------------------------------------------------------------*/
#include <tcl.h>
#include <stdlib.h>
#include <string.h>
#include <domalloc.h>
/*---------------------------------------------------------------------------
| Defines
|
\--------------------------------------------------------------------------*/
#define DBG(x)
#define MAX_BINS 256
#define BIN_HASH_SIZE 512
#define BIN_HASH_MASK 0x01FF
#define CACHE_SIZE 4
#define BLOCK_DATA_SIZE 31000
#define BLOCK_SIZE_BITS 16
/*---------------------------------------------------------------------------
| Typedefs
|
\--------------------------------------------------------------------------*/
typedef struct domAllocBlock {
struct domAllocBin * bin;
void * end;
struct domAllocBlock * prev;
struct domAllocBlock * next;
int hashIndex1;
struct domAllocBlock * hashNext1;
int hashIndex2;
struct domAllocBlock * hashNext2;
int slots;
int freeSlots;
int bitmaps;
int freePos;
int freeBit;
unsigned int freeMask;
} domAllocBlock;
typedef struct domAllocBin {
int size;
int nrSlots;
int freeSlots;
int nrBlocks;
domAllocBlock * freeBlocks;
domAllocBlock * usedBlocks;
} domAllocBin;
typedef struct domAllocBins {
struct domAllocBin * bin[MAX_BINS];
struct domAllocBlock * hashedBlocks[BIN_HASH_SIZE];
struct domAllocBlock * blockCache[CACHE_SIZE];
} domAllocBins;
/*---------------------------------------------------------------------------
| Globals. This is a "single-threaded" allocator.
|
\--------------------------------------------------------------------------*/
static domAllocBins bins;
#ifdef TCL_THREADS
# define TDomThreaded(x) x
static Tcl_Mutex binMutex;
#else
# define TDomThreaded(x)
#endif
/*---------------------------------------------------------------------------
| domAllocInit
|
\--------------------------------------------------------------------------*/
void
domAllocInit()
{
int i;
DBG(fprintf(stderr, "domAllocInit...\n");)
for (i=0; i < MAX_BINS; i++) bins.bin[i] = NULL;
for (i=0; i < CACHE_SIZE; i++) bins.blockCache[i] = NULL;
for (i=0; i < BIN_HASH_SIZE; i++) bins.hashedBlocks[i] = NULL;
}
/*--------------------------------------------------------------------------
| fillHashTable
|
\--------------------------------------------------------------------------*/
static void
fillHashTable (
domAllocBlock * block,
void * mem
)
{
domAllocBlock * hashedBlock;
unsigned int i;
i = ( (unsigned int)mem >> BLOCK_SIZE_BITS) & BIN_HASH_MASK;
hashedBlock = bins.hashedBlocks[i];
while (hashedBlock != NULL) {
if (hashedBlock == block) {
/* all is fine, block is already in hash table */
return;
}
if (hashedBlock->hashIndex1 == (int)i) hashedBlock = hashedBlock->hashNext1;
else if (hashedBlock->hashIndex2 == (int)i) hashedBlock = hashedBlock->hashNext2;
else hashedBlock = NULL;
}
/* add block in hash table */
if (block->hashIndex1 == -1) {
block->hashIndex1 = i;
block->hashNext1 = bins.hashedBlocks[i];
} else
if (block->hashIndex2 == -1) {
block->hashIndex2 = i;
block->hashNext2 = bins.hashedBlocks[i];
} else {
DBG(
fprintf(stderr, "\ntoo many hash entries for %x %x->%d %d,%d!\n",
(unsigned int)block,
(unsigned int)mem, i, block->hashIndex1, block->hashIndex2);)
}
bins.hashedBlocks[i] = block;
}
/*--------------------------------------------------------------------------
| domAlloc
|
\--------------------------------------------------------------------------*/
void *
domAlloc (
int size
)
{
domAllocBin * bin;
domAllocBlock * block;
domAllocBlock * hashedBlock;
int i, j, slots, bitmaps, blockSize;
unsigned int mask;
char * mem;
unsigned int * usedBitmap;
DBG(fprintf(stderr, "\ndomAlloc %d \n", size);)
if (size >= MAX_BINS) {
DBG(fprintf(stderr, "\nSize too large as used for bin!\n");)
return NULL;
}
/*-------------------------------------------------
| FIXME
|
| Rewrite with TSD-based bins to avoid mutex
| contention. Threads are going to step on
| each other toes here which is not what we
| would like to have, don't we ? (zv)
\------------------------------------------------*/
TDomThreaded(Tcl_MutexLock(&binMutex);) /* LOCK !*/
if (bins.bin[size] == NULL) {
/*-------------------------------------------------
| create new bin
\------------------------------------------------*/
bin = (domAllocBin *)malloc(sizeof(domAllocBin));
bin->size = size;
bin->nrSlots = 0;
bin->freeSlots = 0;
bin->nrBlocks = 0;
bin->freeBlocks = NULL;
bin->usedBlocks = NULL;
bins.bin[size] = bin;
} else {
bin = bins.bin[size];
}
if (bin->freeSlots == 0) {
DBG(fprintf(stderr, "allocating new block ... \n");)
/*----------------------------------------------------------------
| allocate and initialize a new block
|
\---------------------------------------------------------------*/
bitmaps = (BLOCK_DATA_SIZE / size) / 32;
slots = bitmaps * 32;
blockSize = sizeof(domAllocBlock) + bitmaps*4 + slots*size;
block = (domAllocBlock *)malloc( blockSize );
block->bin = bin;
block->end = (char*)block + blockSize;
block->slots = slots;
block->freeSlots = slots;
block->bitmaps = bitmaps;
block->freePos = 0;
block->freeBit = 0;
block->freeMask = 0x80000000;
block->hashIndex1 = -1;
block->hashNext1 = NULL;
block->hashIndex2 = -1;
block->hashNext2 = NULL;
usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock));
memset(usedBitmap, 0, bitmaps * 4);
bin->nrSlots += slots;
bin->freeSlots += slots;
bin->nrBlocks++;
block->prev = NULL; /* prepend this new block to free list */
block->next = bin->freeBlocks;
bin->freeBlocks = block;
/*---------------------------------------------------------
| enter block in 'hash' table:
| first and last memory location could have different
| hash entries due to different upper address bits
\--------------------------------------------------------*/
mem = (char*)usedBitmap + bitmaps * 4;
fillHashTable (block, mem);
mem += (slots-1) * size;
fillHashTable (block, mem);
} else {
block = bin->freeBlocks;
}
/*------------------------------------------------------------------------
| find free slot in (partial) free block
|
\-----------------------------------------------------------------------*/
usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock));
i = block->freePos; /* start at old pos to quickly find a free slot */
j = block->freeBit;
mask = block->freeMask;
do {
DBG(fprintf(stderr, "looking %d slot i=%d j=%d %x mask %x\n",
size, i, j, usedBitmap[i], mask); )
if (usedBitmap[i] != 0xFFFFFFFF) {
do {
if ((usedBitmap[i] & mask)==0) {
DBG(fprintf(stderr, "found free slot i=%d j=%d %x mask %x\n",
i, j, usedBitmap[i], mask); )
mem = ((char*)usedBitmap) + (4*block->bitmaps) + ((i*32)+j) * size;
usedBitmap[i] |= mask;
block->freeSlots--;
bin->freeSlots--;
if (block->freeSlots == 0) {
DBG(fprintf(stderr, "freeSlots == 0\n");)
if (block->prev == NULL) { /* remove block from free list */
bin->freeBlocks = block->next;
} else {
block->prev->next = block->next;
}
if (block->next) block->next->prev = block->prev;
block->next = bin->usedBlocks; /* add block to used list */
if (block->next) block->next->prev = block;
block->prev = NULL;
bin->usedBlocks = block;
/* check consistency */
hashedBlock = block->bin->freeBlocks;
while (hashedBlock) {
if (hashedBlock == block) {
DBG(fprintf(stderr, "strange block still in free list \n");)
}
hashedBlock = hashedBlock->next;
}
}
/* keep found free position for later,
* so that next slots can be found quickly
*/
block->freePos = i;
j++; mask = mask >> 1;
if (j >= 32) { j = 0; mask = 0x80000000; }
block->freeBit = j;
block->freeMask = mask;
TDomThreaded(Tcl_MutexUnlock(&binMutex);) /* UNLOCK !*/
return mem;
}
j++; mask = mask >> 1;
if (j >= 32) { j = 0; mask = 0x80000000; }
} while (j != block->freeBit);
}
i++;
if (i >= block->bitmaps) i = 0;
} while (i != block->freePos);
/* TDomThreaded(Tcl_MutexUnlock(&binMutex);) */
DBG(fprintf(stderr, "\ndomAlloc: can't happen! \n");)
*((char*)0) = 0; /* Use Tcl_Panic() for this ? */
return NULL;
}
/*---------------------------------------------------------------------------
| domFree
|
\--------------------------------------------------------------------------*/
void
domFree (
void * mem
)
{
domAllocBlock * block;
domAllocBlock * hashedBlock;
domAllocBlock * prevBlock;
int slotNr, i, foundInCache;
unsigned int * usedBitmap;
unsigned int mask;
DBG(fprintf(stderr, "domFree...\n");)
if (mem == NULL) return;
/*-------------------------------------------------
| FIXME (see domAlloc comments)
|
\------------------------------------------------*/
TDomThreaded(Tcl_MutexLock(&binMutex);)
/*-------------------------------------------------------------------
| Find the block, which corresponds to the given memory location
|
| - First try to look in the memory range cache.
|
\------------------------------------------------------------------*/
block = NULL;
foundInCache = 0;
for (i=0; i < CACHE_SIZE; i++) {
if ((bins.blockCache[i] != NULL) &&
(mem > (void*)(bins.blockCache[i])) &&
(mem < (void*)(bins.blockCache[i]->end))) {
block = bins.blockCache[i];
foundInCache = 1;
break;
}
}
/*-------------------------------------------------------------------
| - Otherwise try to lookup corresponding block in hashtable
|
\------------------------------------------------------------------*/
if (!foundInCache) {
i = ( (unsigned int)mem >> BLOCK_SIZE_BITS) & BIN_HASH_MASK;
block = bins.hashedBlocks[i];
while (block != NULL) {
if ((mem > (void*)block) && (mem < (void*)(block->end))) break;
if (block->hashIndex1 == i) block = block->hashNext1;
else if (block->hashIndex2 == i) block = block->hashNext2;
else block = NULL;
}
}
if (block == NULL) {
DBG(fprintf(stderr, "\n unable to free mem %x !\n", (unsigned int)mem);)
TDomThreaded(Tcl_MutexUnlock(&binMutex);)
return;
}
/*-------------------------------------------------------------------
| clear the allocation bit
\------------------------------------------------------------------*/
usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock));
slotNr = ( (char*)mem - (char*)usedBitmap - block->bitmaps*4 ) / block->bin->size;
DBG(
if (slotNr >= block->slots) {
fprintf(stderr, "assertion failed: slotNr = %d \n", slotNr);
})
i = slotNr >> 5 ; /* slotNr / 32 */
mask = 0x80000000 >> (slotNr % 32);
usedBitmap[i] &= ~mask;
block->freeSlots++;
block->bin->freeSlots++;
DBG(
if ((block->freeSlots < 1) || (block->freeSlots > block->slots)) {
fprintf(stderr, "assertion failed: freeSlots = %d \n", block->freeSlots);
})
/*-------------------------------------------------------------------
| update free/used lists
\------------------------------------------------------------------*/
if (block->freeSlots == 1) {
if (block->prev == NULL) { /* remove block from used list */
block->bin->usedBlocks = block->next;
} else {
block->prev->next = block->next;
}
if (block->next) block->next->prev = block->prev;
block->next = block->bin->freeBlocks; /* add block to free list */
if (block->next) block->next->prev = block;
block->prev = NULL;
block->bin->freeBlocks = block;
DBG(
/* check consistency */
hashedBlock = block->bin->usedBlocks;
while (hashedBlock) {
if (hashedBlock == block) {
fprintf(stderr, "strange block still in used list \n");
}
hashedBlock = hashedBlock->next;
}
)
}
/*-------------------------------------------------------------------
| free the whole block, when all slots are freed
\------------------------------------------------------------------*/
if (block->freeSlots == block->slots) {
DBG(fprintf(stderr, "block completely freed %x\n",
(unsigned int)block);)
if (block->prev == NULL) { /* remove block from free list */
block->bin->freeBlocks = block->next;
} else {
block->prev->next = block->next;
}
if (block->next) block->next->prev = block->prev;
block->bin->nrSlots -= block->slots;
block->bin->freeSlots -= block->slots;
block->bin->nrBlocks--;
/*--------------------------------------------------------------------
| remove block from (two) hash lists
\-------------------------------------------------------------------*/
i = block->hashIndex1;
if (i != -1) {
DBG(fprintf(stderr, "remove from hash list %d \n", i);)
prevBlock = NULL;
hashedBlock = bins.hashedBlocks[i];
while (hashedBlock) {
if (hashedBlock == block) break;
prevBlock = hashedBlock;
if (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1;
else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2;
else hashedBlock = NULL;
}
if (prevBlock == NULL) {
bins.hashedBlocks[i] = block->hashNext1;
} else {
if (prevBlock->hashIndex1 == i) prevBlock->hashNext1 = block->hashNext1;
else if (prevBlock->hashIndex2 == i) prevBlock->hashNext2 = block->hashNext1;
}
}
i = block->hashIndex2;
if (i != -1) {
DBG(fprintf(stderr, "remove from hash list %d \n", i);)
prevBlock = NULL;
hashedBlock = bins.hashedBlocks[i];
while (hashedBlock) {
if (hashedBlock == block) break;
prevBlock = hashedBlock;
if (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1;
else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2;
else hashedBlock = NULL;
}
if (prevBlock == NULL) {
bins.hashedBlocks[i] = block->hashNext2;
} else {
if (prevBlock->hashIndex1 == i) prevBlock->hashNext1 = block->hashNext2;
else if (prevBlock->hashIndex2 == i) prevBlock->hashNext2 = block->hashNext2;
}
}
/*------------------------------------------------------
| remove block from cache, if found
\-----------------------------------------------------*/
for (i=0; i < CACHE_SIZE; i++) {
if (bins.blockCache[i] == block) {
bins.blockCache[i] = NULL;
}
}
DBG(
/* check consistency */
for (i=0; i < block->bitmaps; i++) {
if (usedBitmap[i] != 0) {
fprintf(stderr, "strange bitmap %d is %x \n", i, usedBitmap[i]);
}
}
for (i=0; i < BIN_HASH_SIZE; i++) {
hashedBlock = bins.hashedBlocks[i];
while (hashedBlock) {
if (hashedBlock == block) {
fprintf(stderr, "strange block %d still in hash table \n", i);
}
if (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1;
else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2;
else hashedBlock = NULL;
}
}
hashedBlock = block->bin->freeBlocks;
while (hashedBlock) {
if (hashedBlock == block) {
fprintf(stderr, "strange block still in free list \n");
}
hashedBlock = hashedBlock->next;
}
hashedBlock = block->bin->usedBlocks;
while (hashedBlock) {
if (hashedBlock == block) {
fprintf(stderr, "strange block still in used list \n");
}
hashedBlock = hashedBlock->next;
}
)
free((char*)block);
} else {
/*-----------------------------------------------------------
| update cache
\----------------------------------------------------------*/
if (!foundInCache) {
/* remove oldest entry and add this block */
for (i=1; i < CACHE_SIZE; i++) {
bins.blockCache[i-1] = bins.blockCache[i];
}
bins.blockCache[CACHE_SIZE-1] = block;
}
}
TDomThreaded(Tcl_MutexUnlock(&binMutex);) /* UNLOCK !*/
}