/************************************************************************
*
* File: blalloc.c
* Owner: Wohali (Joan Touzet)
* Hacked up for use in ircd by Dianora
*************************************************************************/
/* $Id: blalloc.c,v 1.2 2005/07/05 02:40:01 sheik Exp $ */
/* INCLUDES */
#include "struct.h"
#include "common.h"
#include "sys.h"
#include "h.h"
#include "numeric.h"
#include "blalloc.h"
#include "memcount.h"
/* FUNCTION PROTOTYPES (LOCAL FUNCTIONS ONLY) */
static int newblock(BlockHeap *bh);
/* FUNCTION PROTOTYPES (EXTERN FUNCTIONS ONLY) */
extern void outofmemory(); /* defined in list.c */
/* FUNCTION DOCUMENTATION:
*
* newblock
* Description:
* mallocs a new block for addition to a blockheap
* Parameters:
* bh (IN): Pointer to parent blockheap.
* Returns:
* 0 if successful, 1 if not
*/
static int newblock(BlockHeap *bh)
{
Block *b;
int i;
/* Setup the initial data structure. */
b = (Block *) MyMalloc(sizeof(Block));
if (b == NULL)
return 1;
b->freeElems = bh->elemsPerBlock;
b->next = bh->base;
b->allocMap = (unsigned long *) MyMalloc(sizeof(unsigned long) * (bh->numlongs + 1));
memset((void *) b->allocMap, '\0', (bh->numlongs + 1) * sizeof(unsigned long));
if (b->allocMap == NULL)
{
MyFree(b);
return 1;
}
/* Now allocate the memory for the elems themselves. */
b->elems = (void *) MyMalloc(bh->elemsPerBlock * bh->elemSize);
if (b->elems == NULL)
{
MyFree(b->allocMap);
MyFree(b);
return 1;
}
b->endElem = (void *) ((unsigned long) b->elems +
(unsigned long) ((bh->elemsPerBlock - 1) *
bh->elemSize));
/* Mark all blocks as free */
for (i = 0; i < bh->numlongs; i++)
b->allocMap[i] = 0L;
/* Finally, link it in to the heap. */
++bh->blocksAllocated;
bh->freeElems += bh->elemsPerBlock;
bh->base = b;
return 0;
}
/* FUNCTION DOCUMENTATION:
*
* BlockHeapCreate
*
* Description:
* Creates a new blockheap from which smaller blocks can be allocated.
* Intended to be used instead of multiple calls to malloc() when
* performance is an issue.
* Parameters:
* elemsize (IN): Size of the basic element to be stored
* elemsperblock (IN): Number of elements to be stored in a single
* block of memory. When the blockheap runs out of free memory, it will
* allocate elemsize * elemsperblock more.
* Returns:
* Pointer to new BlockHeap, or NULL if unsuccessful
*/
BlockHeap *BlockHeapCreate(size_t elemsize, int elemsperblock)
{
BlockHeap *bh;
/* Catch idiotic requests up front */
if ((elemsize <= 0) || (elemsperblock <= 0))
{
outofmemory(); /* die.. out of memory */
}
/* Allocate our new BlockHeap */
bh = (BlockHeap *) MyMalloc(sizeof(BlockHeap));
if (bh == NULL)
{
outofmemory(); /* die.. out of memory */
}
elemsize = elemsize + (elemsize & (sizeof(void *) - 1));
bh->elemSize = elemsize;
bh->elemsPerBlock = elemsperblock;
bh->blocksAllocated = 0;
bh->freeElems = 0;
bh->numlongs = (bh->elemsPerBlock / (sizeof(unsigned long) * 8)) + 1;
if ((bh->elemsPerBlock % (sizeof(unsigned long) * 8)) == 0)
bh->numlongs--;
bh->base = NULL;
/* Be sure our malloc was successful */
if (newblock(bh))
{
MyFree(bh);
outofmemory(); /* die.. out of memory */
}
/* DEBUG */
if (bh == NULL)
{
outofmemory(); /* die.. out of memory */
}
return bh;
}
/* FUNCTION DOCUMENTATION:
*
* BlockHeapAlloc
*
* Description:
* Returns a pointer to a struct within our BlockHeap that's free for
* the taking.
* Parameters:
* bh (IN): Pointer to the Blockheap.
* Returns:
* Pointer to a structure (void *), or NULL if unsuccessful.
*/
void *BlockHeapAlloc(BlockHeap *bh)
{
Block *walker;
int unit;
unsigned long mask;
unsigned long ctr;
if (bh == NULL) return ((void *) NULL);
if (bh->freeElems == 0) /* Allocate new block and assign */
{
/* newblock returns 1 if unsuccessful, 0 if not */
if (newblock(bh))
{
return ((void *) NULL);
}
else
{
walker = bh->base;
walker->allocMap[0] = 0x1L;
walker->freeElems--;
bh->freeElems--;
if (bh->base->elems == NULL)
return ((void *) NULL);
}
return ((bh->base)->elems); /* ...and take the first elem. */
}
for (walker = bh->base; walker != NULL; walker = walker->next)
{
if (walker->freeElems > 0)
{
mask = 0x1L;
ctr = 0;
unit = 0;
while (unit < bh->numlongs)
{
if ((mask == 0x1L) && (walker->allocMap[unit] == ~0))
{
/* Entire subunit is used, skip to next one. */
unit++;
ctr = 0;
continue;
}
/* Check the current element, if free allocate block */
if (!(mask & walker->allocMap[unit]))
{
walker->allocMap[unit] |= mask; /* Mark block as used */
walker->freeElems--;
bh->freeElems--;
/* And return the pointer
*
* Address arithemtic is always ca-ca have to make sure
* the the bit pattern for the base address is converted
* into the same number of bits in an integer type, that
* has at least sizeof(unsigned long) at least ==
* sizeof(void *) -Dianora
*/
return ((void *) ((unsigned long) walker->elems +
((unit * sizeof(unsigned long) *
8 + ctr) *
(unsigned long) bh->elemSize)));
}
/* Step up to the next unit */
mask <<= 1;
ctr++;
if (!mask)
{
mask = 0x1L;
unit++;
ctr = 0;
}
} /* while */
} /* if */
} /* for */
return ((void *) NULL); /* If you get here, something bad happened ! */
}
/* FUNCTION DOCUMENTATION:
*
* BlockHeapFree
*
* Description:
* Returns an element to the free pool, does not free()
* Parameters:
* bh (IN): Pointer to BlockHeap containing element
* ptr (in): Pointer to element to be "freed"
* Returns:
* 0 if successful, 1 if element not contained within BlockHeap.
*/
int BlockHeapFree(BlockHeap *bh, void *ptr)
{
Block *walker;
unsigned long ctr;
unsigned long bitmask;
if (bh == NULL)
{
#if defined(USE_SYSLOG) && defined(SYSLOG_BLOCK_ALLOCATOR)
syslog(LOG_DEBUG, "blalloc.c bh == NULL");
#endif
return 1;
}
for (walker = bh->base; walker != NULL; walker = walker->next)
{
if ((ptr >= walker->elems) && (ptr <= walker->endElem))
{
ctr = ((unsigned long) ptr - (unsigned long) (walker->elems)) /
(unsigned long) bh->elemSize;
bitmask = 1L << (ctr % (sizeof(unsigned long) * 8));
ctr = ctr / (sizeof(unsigned long) * 8);
/* Flip the right allocation bit
*
* Complain if the bit is already clear, something is wrong
* (typically, someone freed the same block twice)
*/
if ((walker->allocMap[ctr] & bitmask) == 0)
{
abort(); /* This is more useful than some random complaining */
#if defined(USE_SYSLOG) && defined(SYSLOG_BLOCK_ALLOCATOR)
syslog(LOG_DEBUG, "blalloc.c bit already clear in map!");
#endif
sendto_ops("blalloc.c bit already clear in map!");
sendto_ops("Please report to the solid team!"
"ircd@solid-ircd.com");
}
else
{
walker->allocMap[ctr] = walker->allocMap[ctr] & ~bitmask;
walker->freeElems++;
bh->freeElems++;
}
return 0;
}
}
return 1;
}
/* FUNCTION DOCUMENTATION:
*
* BlockHeapGarbageCollect
*
* Description:
* Performs garbage colletion on the block heap. Any blocks that are
* completely unallocated are removed from the heap. Garbage
* collection will never remove the root node of the heap.
* Parameters:
* bh (IN): Pointer to the BlockHeap to be cleaned up
* Returns:
* 0 if successful, 1 if bh == NULL
*/
int BlockHeapGarbageCollect(BlockHeap *bh)
{
Block *walker, *last;
if (bh == NULL) return 1;
if (bh->freeElems < bh->elemsPerBlock)
{
/* There couldn't possibly be an entire free block. Return. */
return 0;
}
last = NULL;
walker = bh->base;
while (walker)
{
/* This section rewritten Dec 10 1998 - Dianora */
int i;
for (i = 0; i < bh->numlongs; i++)
{
if (walker->allocMap[i])
break;
}
if (i == bh->numlongs)
{
/* This entire block is free. Remove it. */
MyFree(walker->elems);
MyFree(walker->allocMap);
if (last)
{
last->next = walker->next;
MyFree(walker);
walker = last->next;
}
else
{
bh->base = walker->next;
MyFree(walker);
walker = bh->base;
}
bh->blocksAllocated--;
bh->freeElems -= bh->elemsPerBlock;
}
else
{
last = walker;
walker = walker->next;
}
}
return 0;
}
/* FUNCTION DOCUMENTATION:
*
* BlockHeapDestroy
*
* Description:
* Completely free()s a BlockHeap. Use for cleanup.
* Parameters:
* bh (IN): Pointer to the BlockHeap to be destroyed.
* Returns:
* 0 if successful, 1 if bh == NULL
*/
int BlockHeapDestroy(BlockHeap *bh)
{
Block *walker, *next;
if (bh == NULL) return 1;
for (walker = bh->base; walker != NULL; walker = next)
{
next = walker->next;
MyFree(walker->elems);
MyFree(walker->allocMap);
MyFree(walker);
}
MyFree(bh);
return 0;
}
u_long
memcount_BlockHeap(BlockHeap *bh, MCBlockHeap *mc)
{
mc->file = __FILE__;
mc->blocks.c = bh->blocksAllocated;
mc->blocks.m = sizeof(Block) * mc->blocks.c;
mc->blocks.m += (sizeof(unsigned long) * (bh->numlongs + 1))
* mc->blocks.c;
mc->pool.c = bh->blocksAllocated * bh->elemsPerBlock;
mc->pool.m = mc->pool.c * bh->elemSize;
mc->objects.c = mc->pool.c - bh->freeElems;
mc->objects.m = mc->objects.c * bh->elemSize;
mc->management.c = mc->blocks.c + 1;
mc->management.m = mc->blocks.m + sizeof(*bh);
mc->total.c = mc->management.c + mc->pool.c;
mc->total.m = mc->management.m + mc->pool.m;
mc->objsize = bh->elemSize;
return mc->total.m;
}
u_long
memcount_blalloc(MCblalloc *mc)
{
mc->file = __FILE__;
return 0;
}
syntax highlighted by Code2HTML, v. 0.9.1