boomp

mail@pastecode.io avatar
unknown
plain_text
a month ago
10 kB
1
Indexable
Never
#define GSCVSID "$Header: /home/cvs/ficc/liberty/src/kool_ade/src/heap.c,v 1.44 2020/09/02 03:38:53 keyalm Exp $"
/****************************************************************
**
**	heap.c
**
**	Copyright 1993 - Goldman Sachs
**
**	$Log: heap.c,v $
**	Revision 1.44  2020/09/02 03:38:53  keyalm
**	IS:6010-5787726 improve documentation of some core stuff
**
**	Revision 1.43  2019/08/12 10:52:46  sharps
**	IS:6010-4718773 Include cleanup. Prefer uint8_t to unsigned char. Predicate use of roundUp on REVERT_KOOL_ADE_HEAP_ROUND_UP
**	
**	Revision 1.42  2019/08/11 23:43:29  sharps
**	IS:6010-4718773 Modernize. Fix walk. GSHeapGetAll only returns valid heaps
**	
**	Revision 1.41  2012/03/16 15:55:23  trifov
**	IS:6012-200334 fixing sign conversion warnings
**	
**	Revision 1.40  2012/01/09 16:00:09  madsej
**	IS:6012-200334 more 64 bit fixes (including hash sorting fix)
**	
**	Revision 1.39  2010/06/01 11:47:45  keatlj
**	IS:6012-93680 show kool_ade on the heap
**	
**	Revision 1.38  2010/05/06 13:23:19  uschoj
**	IS:6012-88940 Move heap.h to kool_ade dir to make gcc4 happy
**	
**	Revision 1.37  2009/05/05 11:16:32  uschoj
**	IS:6012-37805 Win64 changes
**	
**	Revision 1.36  2007/08/09 20:24:53  madsej
**	IS:1706 debug heap bad
**	
**	Revision 1.35  2007/03/24 15:00:33  goodfj
**	IS:21989 Fix namespace/stl macros (review & prodver at will)
**	
**	Revision 1.34  2006/08/17 13:08:43  uschoj
**	Backout 1.24
**	
****************************************************************/

#define BUILDING_KOOL_ADE

// ficc/portable/src/portable
#include <portable.h>

// ficc/liberty/src/kool_ade
#include <kool_ade/heap.h>

#include <cstdlib>   // getenv, calloc, malloc, free
#include <cstring>   // memset
#include <algorithm> // std::find< InputIterator, T >
#include <vector>    // std::vector< T >

#include <stdint.h>  // intptr_t, uint8_t
#include <strings.h> // strcasecmp

#include <vccrtdbg.h>

static std::vector< HEAP* > s_heaps;

std::vector< HEAP* > const& GSHeapGetAll(
)
{
    return s_heaps;
}

namespace {

inline size_t roundUp( size_t const size, size_t const unit )
{
	if( size_t const rem = size % unit )
		return size + ( unit - rem );

	return size;
};

} // namespace

/****************************************************************
**	Routine: GSHeapCreate
**	Returns: New HEAP if created without error
**			 nullptr if HEAP couldn't be created
**	Action : Create a new heap
****************************************************************/
HEAP* GSHeapCreate(
	char const* Name,         // Name of the heap
	size_t      ElementSize,  // Size of elements to allocate from the heap
	size_t      BlockElements // Number of elements/large block
)
{
	HEAP* const Heap = static_cast< HEAP* >( calloc( 1, sizeof( HEAP ) ) );

	if( Heap )
	{
		Heap->Name = Name;
		Heap->ElementSize = ElementSize;
		static char const* const s_revertValue = getenv( "REVERT_KOOL_ADE_HEAP_ROUND_UP" );
		static bool const s_revert = s_revertValue && strcasecmp( s_revertValue, "true" ) == 0;
		if( s_revert )
		Heap->ElementAllocSize = sizeof( void* ) * ( ( ElementSize + sizeof( void* ) - 1 ) / sizeof( void* ) );
		else
		Heap->ElementAllocSize = roundUp( ElementSize, sizeof( void* ) );
		
		if( !BlockElements )
			BlockElements = HEAP_DEFAULT_BLOCK_ELEMENTS;

		Heap->BlockSize = sizeof( HEAP_BLOCK ) + ( Heap->ElementAllocSize * BlockElements );
	    s_heaps.push_back( Heap );
	}

	return Heap;
}

/****************************************************************
**	Routine: GSHeapDestroy
**	Returns: None
**	Action : Destroy a heap
****************************************************************/
void GSHeapDestroy(
	HEAP* Heap
)
{
	while( Heap->BlockList )
	{
		HEAP_BLOCK* const HeapBlock = Heap->BlockList;
		Heap->BlockList = HeapBlock->Next;
		free( HeapBlock );
	}

	free( Heap );

	std::vector< HEAP* >::iterator it = std::find( s_heaps.begin(), s_heaps.end(), Heap );

	if( it != s_heaps.end() )
		s_heaps.erase( it );
}

/****************************************************************
**	Routine: GSHeapStatistics
**	Returns: None
**	Action : Return statistics about a heap
****************************************************************/
void GSHeapStatistics(
	HEAP*       Heap,
	HEAP_STATS* HeapStats
)
{
	memset( HeapStats, 0, sizeof( *HeapStats ) );

	for( HEAP_BLOCK const* HeapBlock = Heap->BlockList; HeapBlock; HeapBlock = HeapBlock->Next )
	{
		HeapStats->BlockCount++;
		HeapStats->TotalMemory += HeapBlock->Size;
		HeapStats->TotalElementCount += ( HeapBlock->Size - sizeof( HEAP_BLOCK ) ) / Heap->ElementAllocSize;
	}

	for( HEAP_ELEMENT const* HeapElement = Heap->FreeElementList; HeapElement; HeapElement = HeapElement->Next )
		HeapStats->FreeElementCount++;

	HeapStats->FreeElementCount += static_cast< size_t >( Heap->BlockEnd - Heap->BlockPtr ) / Heap->ElementAllocSize;

	HeapStats->FreeMemory = HeapStats->FreeElementCount * Heap->ElementAllocSize;
	HeapStats->UsedMemory = HeapStats->TotalMemory - HeapStats->FreeMemory;
	HeapStats->UsedElementCount = HeapStats->TotalElementCount - HeapStats->FreeElementCount;
}

/****************************************************************
**	Routine: GSHeapMalloc
**	Returns: Piece of memory or nullptr if error
**	Action : Malloc a piece of memory from a heap
****************************************************************/
void* GSHeapMalloc(
	HEAP* Heap
)
{
	if( Heap->ElementSize == 0 )
		return CC_NULLPTR;

	HEAP_ELEMENT* HeapElement;

	if( Heap->FreeElementList )
	{
		HeapElement = Heap->FreeElementList;
		Heap->FreeElementList = HeapElement->Next;
	}
	else if( Heap->BlockPtr && Heap->BlockPtr < Heap->BlockEnd )
	{
		HeapElement = reinterpret_cast< HEAP_ELEMENT* >( Heap->BlockPtr );
		Heap->BlockPtr += Heap->ElementAllocSize;
	}
	else if( ( Heap->BlockPtr = static_cast< uint8_t* >( malloc( Heap->BlockSize ) ) ) )
	{
		Heap->BlockEnd = Heap->BlockPtr + Heap->BlockSize;

		HEAP_BLOCK* const HeapBlock = reinterpret_cast< HEAP_BLOCK* >( Heap->BlockPtr );
		HeapBlock->Size	= Heap->BlockSize;
		HeapBlock->Next	= Heap->BlockList;
		Heap->BlockList	= HeapBlock;
		Heap->BlockPtr += sizeof( HEAP_BLOCK );

		HeapElement = reinterpret_cast< HEAP_ELEMENT* >( Heap->BlockPtr );
		Heap->BlockPtr += Heap->ElementAllocSize;
	}
	else
		return CC_NULLPTR;

	return HeapElement;
}

/****************************************************************
**	Routine: GSHeapCalloc
**	Returns: Piece of memory or nullptr if error
**	Action : Calloc a piece of memory from a heap.  The size of
**			 the memory is determined by the heap being used.
****************************************************************/
void* GSHeapCalloc(
	HEAP* Heap
)
{
	if( Heap->ElementSize == 0 )
		return CC_NULLPTR;

	HEAP_ELEMENT* HeapElement;

	if( Heap->FreeElementList )
	{
		HeapElement = Heap->FreeElementList;
		Heap->FreeElementList = HeapElement->Next;
	}
	else if( Heap->BlockPtr && Heap->BlockPtr < Heap->BlockEnd )
	{
		HeapElement = reinterpret_cast< HEAP_ELEMENT* >( Heap->BlockPtr );
		Heap->BlockPtr += Heap->ElementAllocSize;
	}
	else if( ( Heap->BlockPtr = static_cast< uint8_t* >( malloc( Heap->BlockSize ) ) ) )
	{
		Heap->BlockEnd = Heap->BlockPtr + Heap->BlockSize;

		HEAP_BLOCK* const HeapBlock = reinterpret_cast< HEAP_BLOCK* >( Heap->BlockPtr );
		HeapBlock->Size	= Heap->BlockSize;
		HeapBlock->Next	= Heap->BlockList;
		Heap->BlockList	= HeapBlock;
		Heap->BlockPtr += sizeof( HEAP_BLOCK );

		HeapElement = reinterpret_cast< HEAP_ELEMENT* >( Heap->BlockPtr );
		Heap->BlockPtr += Heap->ElementAllocSize;
	}
	else
		return CC_NULLPTR;

	memset( HeapElement, 0, Heap->ElementAllocSize );
	return HeapElement;
}

/****************************************************************
**	Routine: GSHeapFree
**	Returns: None
**	Action : Free a piece of memory allocated from a heap
****************************************************************/
void GSHeapFree(
	HEAP* Heap,
	void* Element
)
{   /**
    *  Premise of this seems to be
    *  a) Element must be a previously GsHeapMalloc/GsHeapCalloc-ed thing
    *  b) We ensured that ElementSize can at least hold a ptr during allocation
    *  c) Since it is being free-d it's value doesnt matter and we can overwrite it partially to store the Next ptr
    *  d) Since the element was previously malloc-ed/calloc-ed , the alignment is good enough to store a ptr.
    *  ( malloc/calloc returns memory suitably aligned for any kind of fundamental type )
    */
	if( Element )
	{
		static_cast< HEAP_ELEMENT* >( Element )->Next = Heap->FreeElementList;
		Heap->FreeElementList = static_cast< HEAP_ELEMENT* >( Element );
	}
}

/****************************************************************
**	Routine: GSHeapWalk::GSHeapWalk
**	Returns: 
**	Action : 
****************************************************************/
GSHeapWalk::GSHeapWalk(
	HEAP* heap
)
: m_heap( heap ), m_free_set( 0, 1 )
{
	// run through free block list and enumerate all free blocks so we can tell while walking which ones are free
	for( HEAP_ELEMENT const* el = m_heap->FreeElementList; el; el = el->Next )
		m_free_set.insert( reinterpret_cast< intptr_t >( el ) );
}

/****************************************************************
**	Routine: GSHeapWalk::walk
**	Returns: 
**	Action : 
****************************************************************/
bool GSHeapWalk::walk(
)
{
	free_set_t::iterator const end_it = m_free_set.end();

	for( HEAP_BLOCK* HeapBlock = m_heap->BlockList; HeapBlock; HeapBlock = HeapBlock->Next )
	{
		uint8_t const* const BlockEnd = reinterpret_cast< uint8_t* >( HeapBlock ) + m_heap->BlockSize;

		for(
			unsigned char* Elem = reinterpret_cast< uint8_t* >( HeapBlock ) + sizeof( HEAP_BLOCK );
			Elem != reinterpret_cast< uint8_t* >( m_heap->BlockPtr ) && Elem < BlockEnd;
			Elem += m_heap->ElementAllocSize
		)
			if( m_free_set.find( reinterpret_cast< intptr_t >( Elem ) ) == end_it )
			{
				if( !( *this )( Elem ) )
					return false;
			}
	}

	return true;
}
Leave a Comment