// Copyright (c) 1994-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of the License "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// e32\common\heap.cpp

// 

//

#include "common.h"

#ifdef __KERNEL_MODE__

#include <kernel/kern_priv.h>

#endif

#ifdef _DEBUG

#define __SIMULATE_ALLOC_FAIL(s)	if (CheckForSimulatedAllocFail()) {s}

#define	__CHECK_CELL(p)				CheckCell(p)

#define	__ZAP_CELL(p)				memset( ((TUint8*)p) + RHeap::EAllocCellSize, 0xde, p->len - RHeap::EAllocCellSize)

#define __DEBUG_SAVE(p)				TInt dbgNestLevel = ((SDebugCell*)p)->nestingLevel

#define __DEBUG_RESTORE(p)			((SDebugCell*)(((TUint8*)p)-EAllocCellSize))->nestingLevel = dbgNestLevel

#else

#define __SIMULATE_ALLOC_FAIL(s)

#define	__CHECK_CELL(p)

#define	__ZAP_CELL(p)

#define __DEBUG_SAVE(p)

#define __DEBUG_RESTORE(p)

#endif

#define __NEXT_CELL(p)				((SCell*)(((TUint8*)p)+p->len))

#define __POWER_OF_2(x)				((TUint32)((x)^((x)-1))>=(TUint32)(x))

#define __MEMORY_MONITOR_CHECK_CELL(p) \

					{ \

					TLinAddr m = TLinAddr(iAlign-1); \

					SCell* c = (SCell*)(((TUint8*)p)-EAllocCellSize); \

					if((c->len & m) || (c->len<iMinCell) || ((TUint8*)c<iBase) || ((TUint8*)__NEXT_CELL(c)>iTop)) \

						BTraceContext12(BTrace::EHeap, BTrace::EHeapCorruption, (TUint32)this, (TUint32)p, (TUint32)c->len-EAllocCellSize); \

					}

/**

@SYMPatchable

@publishedPartner

@released

Defines the minimum cell size of  a heap.

The constant can be changed at ROM build time using patchdata OBY keyword.

*/

#ifdef __X86GCC__	// For X86GCC we dont use the proper data import attribute

#undef IMPORT_D		// since the constant is not really imported. GCC doesn't 

#define IMPORT_D	// allow imports from self.

#endif

IMPORT_D extern const TInt KHeapMinCellSize;

/**

@SYMPatchable

@publishedPartner

@released

This constant defines the ratio that determines the amount of hysteresis between heap growing and heap

shrinking.

It is a 32-bit fixed point number where the radix point is defined to be

between bits 7 and 8 (where the LSB is bit 0) i.e. using standard notation, a Q8 or a fx24.8

fixed point number.  For example, for a ratio of 2.0, set KHeapShrinkHysRatio=0x200.

The heap shrinking hysteresis value is calculated to be:

@code

KHeapShrinkHysRatio*(iGrowBy>>8)

@endcode

where iGrowBy is a page aligned value set by the argument, aGrowBy, to the RHeap constructor.

The default hysteresis value is iGrowBy bytes i.e. KHeapShrinkHysRatio=2.0.

Memory usage may be improved by reducing the heap shrinking hysteresis

by setting 1.0 < KHeapShrinkHysRatio < 2.0.  Heap shrinking hysteresis is disabled/removed

when KHeapShrinkHysRatio <= 1.0.

The constant can be changed at ROM build time using patchdata OBY keyword.

*/

IMPORT_D extern const TInt KHeapShrinkHysRatio;

#pragma warning( disable : 4705 )	// statement has no effect

UEXPORT_C RHeap::RHeap(TInt aMaxLength, TInt aAlign, TBool aSingleThread)

/**

@internalComponent

*/

//

// Constructor for fixed size heap

//

	:	iMinLength(aMaxLength), iMaxLength(aMaxLength), iOffset(0), iGrowBy(0), iChunkHandle(0),

		iNestingLevel(0), iAllocCount(0), iFailType(ENone), iTestData(NULL)

	{

	iAlign = aAlign ? aAlign : ECellAlignment;

	iPageSize = 0;

	iFlags = aSingleThread ? (ESingleThreaded|EFixedSize) : EFixedSize;

	Initialise();

	}

#pragma warning( default : 4705 )

UEXPORT_C RHeap::RHeap(TInt aChunkHandle, TInt aOffset, TInt aMinLength, TInt aMaxLength, TInt aGrowBy, TInt aAlign, TBool aSingleThread)

/**

@internalComponent

*/

//

// Constructor for chunk heaps.

//

	:	iOffset(aOffset), iChunkHandle(aChunkHandle),

		iNestingLevel(0), iAllocCount(0), iFailType(ENone), iTestData(NULL)

	{

	TInt sz = iBase - ((TUint8*)this - iOffset);

	GET_PAGE_SIZE(iPageSize);

	__ASSERT_ALWAYS(iOffset>=0, HEAP_PANIC(ETHeapNewBadOffset));

	iMinLength = Max(aMinLength, sz + EAllocCellSize);

	iMinLength = _ALIGN_UP(iMinLength, iPageSize);

	iMaxLength = Max(aMaxLength, iMinLength);

	iMaxLength = _ALIGN_UP(iMaxLength, iPageSize);

	iGrowBy = _ALIGN_UP(aGrowBy, iPageSize);

	iFlags = aSingleThread ? ESingleThreaded : 0;

	iAlign = aAlign ? aAlign : ECellAlignment;

	Initialise();

	}

UEXPORT_C TAny* RHeap::operator new(TUint aSize, TAny* aBase) __NO_THROW

/**

@internalComponent

*/

	{

	__ASSERT_ALWAYS(aSize>=sizeof(RHeap), HEAP_PANIC(ETHeapNewBadSize));

	RHeap* h = (RHeap*)aBase;

	h->iAlign = 0x80000000;	// garbage value

	h->iBase = ((TUint8*)aBase) + aSize;

	return aBase;

	}

void RHeap::Initialise()

//

// Initialise the heap.

//

	{

	__ASSERT_ALWAYS((TUint32)iAlign>=sizeof(TAny*) && __POWER_OF_2(iAlign), HEAP_PANIC(ETHeapNewBadAlignment));

	iCellCount = 0;

	iTotalAllocSize = 0;

	iBase = (TUint8*)Align(iBase + EAllocCellSize);

	iBase -= EAllocCellSize;

	TInt b = iBase - ((TUint8*)this - iOffset);

	TInt len = _ALIGN_DOWN(iMinLength - b, iAlign);

	iTop = iBase + len;

	iMinLength = iTop - ((TUint8*)this - iOffset);

	iMinCell = Align(KHeapMinCellSize + Max((TInt)EAllocCellSize, (TInt)EFreeCellSize));

#ifdef _DEBUG

	memset(iBase, 0xa5, len);

#endif

	SCell* pM=(SCell*)iBase; // First free cell

	iFree.next=pM; // Free list points to first free cell

	iFree.len=0; // Stop free from joining this with a free block

	pM->next=NULL; // Terminate the free list

	pM->len=len; // Set the size of the free cell

	}

#ifdef _DEBUG

void RHeap::CheckCell(const SCell* aCell) const

	{

	TLinAddr m = TLinAddr(iAlign - 1);

	__ASSERT_DEBUG(!(aCell->len & m), HEAP_PANIC(ETHeapBadCellAddress));

	__ASSERT_DEBUG(aCell->len >= iMinCell, HEAP_PANIC(ETHeapBadCellAddress));

	__ASSERT_DEBUG((TUint8*)aCell>=iBase, HEAP_PANIC(ETHeapBadCellAddress));

	__ASSERT_DEBUG((TUint8*)__NEXT_CELL(aCell)<=iTop, HEAP_PANIC(ETHeapBadCellAddress));

	}

#endif

UEXPORT_C RHeap::SCell* RHeap::GetAddress(const TAny* aCell) const

//

// As much as possible, check a cell address and backspace it

// to point at the cell header.

//

	{

	TLinAddr m = TLinAddr(iAlign - 1);

	__ASSERT_ALWAYS(!(TLinAddr(aCell)&m), HEAP_PANIC(ETHeapBadCellAddress));

	SCell* pC = (SCell*)(((TUint8*)aCell)-EAllocCellSize);

	__CHECK_CELL(pC);

	return pC;

	}

UEXPORT_C TInt RHeap::AllocLen(const TAny* aCell) const

/**

Gets the length of the available space in the specified allocated cell.

@param aCell A pointer to the allocated cell.

@return The length of the available space in the allocated cell.

@panic USER 42 if aCell does not point to  a valid cell.

*/

	{

	SCell* pC = GetAddress(aCell);

	return pC->len - EAllocCellSize;

	}

#if !defined(__HEAP_MACHINE_CODED__) || defined(_DEBUG)

RHeap::SCell* RHeap::DoAlloc(TInt aSize, SCell*& aLastFree)

//

// Allocate without growing. aSize includes cell header and alignment.

// Lock already held.

//

	{

	SCell* pP = &iFree;

	SCell* pC = pP->next;

	for (; pC; pP=pC, pC=pC->next) // Scan the free list

		{

		__CHECK_CELL(pC);

		SCell* pE;

		if (pC->len >= aSize)				// Block size bigger than request

			{

			if (pC->len - aSize < iMinCell)	// Leftover must be large enough to hold an SCell

			   	{

			   	aSize = pC->len;			// It isn't, so take it all

			   	pE = pC->next;				// Set the next field

			   	}

			else

			   	{

			   	pE = (SCell*)(((TUint8*)pC)+aSize); // Take amount required

			   	pE->len = pC->len - aSize;	// Initialize new free cell

			   	pE->next = pC->next;

			   	}

			pP->next = pE;					// Update previous pointer

			pC->len = aSize;				// Set control size word

#if defined(_DEBUG)														

			((SDebugCell*)pC)->nestingLevel = iNestingLevel;

			((SDebugCell*)pC)->allocCount = ++iAllocCount;

#endif

			return pC;

			}

		}

	aLastFree = pP;

	return NULL;

	}

#endif

UEXPORT_C TAny* RHeap::Alloc(TInt aSize)

/**

Allocates a cell of the specified size from the heap.

If there is insufficient memory available on the heap from which to allocate

a cell of the required size, the function returns NULL.

The cell is aligned according to the alignment value specified at construction,

or the default alignment value, if an explict value was not specified.

The resulting size of the allocated cell may be rounded up to a

value greater than aSize, but is guaranteed to be not less than aSize.

@param aSize The 

size of the cell to be allocated from the heap

@return A pointer to the allocated cell. NULL if there is insufficient memory 

        available.

@panic USER 47 if the maximum unsigned value of aSize is greater than or equal

       to the value of KMaxTInt/2; for example, calling Alloc(-1) raises

       this panic.

@see KMaxTInt        

*/

	{

	__CHECK_THREAD_STATE;

	__ASSERT_ALWAYS((TUint)aSize<(KMaxTInt/2),HEAP_PANIC(ETHeapBadAllocatedCellSize));

	__SIMULATE_ALLOC_FAIL(return NULL;)

	TInt origSize = aSize;

	aSize = Max(Align(aSize + EAllocCellSize), iMinCell);

	SCell* pL = NULL;

	Lock();

	SCell* pC = (SCell*)DoAlloc(aSize, pL);

	if (!pC && !(iFlags & EFixedSize))

		{

		// try to grow chunk heap

		TInt r = TryToGrowHeap(aSize, pL);

		if (r==KErrNone)

			pC = DoAlloc(aSize, pL);

		}

	if (pC)

		++iCellCount, iTotalAllocSize += (pC->len - EAllocCellSize);

	Unlock();

	if (pC)

		{

		TAny* result=((TUint8*)pC) + EAllocCellSize;

		if (iFlags & ETraceAllocs)

			{

			TUint32 traceData[2];

			traceData[0] = AllocLen(result);

			traceData[1] = origSize;

			BTraceContextN(BTrace::EHeap, BTrace::EHeapAlloc, (TUint32)this, (TUint32)result, traceData, sizeof(traceData));

			}

#ifdef __KERNEL_MODE__

		memclr(result, pC->len - EAllocCellSize);

#endif		

		return result;

		}

	if (iFlags & ETraceAllocs)						

			BTraceContext8(BTrace::EHeap, BTrace::EHeapAllocFail, (TUint32)this, (TUint32)origSize);

	return NULL;

	}

TInt RHeap::TryToGrowHeap(TInt aSize, SCell* aLastFree)

	{

	TBool at_end = IsLastCell(aLastFree);

	TInt extra = at_end ? aSize - aLastFree->len : aSize;

	extra = (extra + iGrowBy - 1) / iGrowBy;

	extra *= iGrowBy;

	TInt cur_len = _ALIGN_UP(iTop - ((TUint8*)this - iOffset), iPageSize);

	TInt new_len = cur_len + extra;

	TInt r = KErrNoMemory;

	if (new_len <= iMaxLength)

		{

		r = SetBrk(new_len);

		if (r == KErrNone)

			{

			if (at_end)

				aLastFree->len += extra;

			else

				{

				SCell* pC = (SCell*)iTop;

				pC->len = extra;

				pC->next = NULL;

				aLastFree->next = pC;

				}

			iTop += extra;

			}

		}

	return r;

	}

#ifndef __KERNEL_MODE__

EXPORT_C TInt RHeap::Compress()

/**

Compresses the heap.

The function frees excess committed space from the top 

of the heap. The size of the heap is never reduced below the minimum size 

specified during creation of the heap.

@return The space reclaimed. If no space can be reclaimed, then this value 

        is zero.

*/

	{

	if (iFlags & EFixedSize)

		return 0;

	TInt r = 0;

	Lock();

	SCell* pC = &iFree;

	for (; pC->next; pC=pC->next) {}

	if (pC!=&iFree)

		{

		__CHECK_CELL(pC);

		if (IsLastCell(pC))

			r = Reduce(pC);

		}

	Unlock();

	return r;

	}

#endif

#if !defined(__HEAP_MACHINE_CODED__) || defined(_DEBUG)

void RHeap::DoFree(SCell* pC)

	{

	__ZAP_CELL(pC);

	SCell* pP = &iFree;

	SCell* pE = pP->next;

	for (; pE && pE<pC; pP=pE, pE=pE->next) {}

	if (pE)			// Is there a following free cell?

		{

		SCell* pN = __NEXT_CELL(pC);

		__ASSERT_ALWAYS(pN<=pE, HEAP_PANIC(ETHeapFreeBadNextCell)); // Following cell overlaps

		if (pN==pE) // Is it adjacent

			{

			pC->len += pE->len; // Yes - coalesce adjacent free cells

			pC->next = pE->next;

			}

		else					// pN<pE, non-adjacent free cells

			pC->next = pE;		// Otherwise just point to it

		}

	else

		pC->next = NULL;		// No following free cell

	SCell* pN = __NEXT_CELL(pP);	// pN=pP=&iFree if no preceding free cell

	__ASSERT_ALWAYS(pN<=pC, HEAP_PANIC(ETHeapFreeBadPrevCell)); // Previous cell overlaps

	if (pN==pC) // Is it adjacent

		{

		pP->len += pC->len;		// Yes - coalesce adjacent free cells

		pP->next = pC->next;

		pC = pP;				// for size reduction check

		}

	else						// pN<pC, non-adjacent free cells

		pP->next = pC;			// point previous cell to the one being freed

	pN = __NEXT_CELL(pC);		// End of amalgamated free cell

	if ((TUint8*)pN==iTop && !(iFlags & EFixedSize) && 

		pC->len >= KHeapShrinkHysRatio*(iGrowBy>>8))

		Reduce(pC);

	}

#endif

UEXPORT_C void RHeap::Free(TAny* aCell)

/**

Frees the specified cell and returns it to the heap.

@param aCell A pointer to a valid cell; this pointer can also be NULL,

             in which case the function does nothing and just returns.

@panic USER 42 if aCell points to an invalid cell.

*/

	{

	__CHECK_THREAD_STATE;

	if (!aCell)

		return;

	Lock();

	if (iFlags & EMonitorMemory)

		__MEMORY_MONITOR_CHECK_CELL(aCell);

	SCell* pC = GetAddress(aCell);

	--iCellCount;

	iTotalAllocSize -= (pC->len - EAllocCellSize);

	DoFree(pC);

	if (iFlags & ETraceAllocs)

		BTraceContext8(BTrace::EHeap, BTrace::EHeapFree, (TUint32)this, (TUint32)aCell);

	Unlock();

	}

TInt RHeap::Reduce(SCell* aCell)

	{

	TInt reduce=0;

	TInt offset=((TUint8*)aCell)-((TUint8*)this - iOffset);

	if (offset>=iMinLength)

		reduce = aCell->len;						// length of entire free cell

	else

		reduce = offset + aCell->len - iMinLength;	// length of free cell past minimum heap size

	reduce = _ALIGN_DOWN(reduce, iPageSize);		// round down to page multiple

	if (reduce<=0)

		return 0;									// can't reduce this heap

	TInt new_cell_len = aCell->len - reduce;		// length of last free cell after reduction

	if (new_cell_len == 0)

		{

		// the free cell can be entirely eliminated

		SCell* pP = &iFree;

		for (; pP->next!=aCell; pP=pP->next) {}

		pP->next = NULL;

		}

	else

		{

		if (new_cell_len < iMinCell)

			{

			// max reduction would leave a cell too small

			reduce -= iPageSize;

			new_cell_len += iPageSize;

			}

		aCell->len = new_cell_len;	// reduce the cell length

		}

	iTop -= reduce;

	TInt new_len = _ALIGN_UP(iTop - ((TUint8*)this - iOffset), iPageSize);

	TInt r = SetBrk(new_len);

	__ASSERT_ALWAYS(r==KErrNone, HEAP_PANIC(ETHeapReduceFailed));

	return reduce;

	}

#ifndef __KERNEL_MODE__

EXPORT_C void RHeap::Reset()

/**

Frees all allocated cells on this heap.

*/

	{

	Lock();

	if (!(iFlags & EFixedSize))

		{

		TInt r = SetBrk(iMinLength);

		__ASSERT_ALWAYS(r==KErrNone, HEAP_PANIC(ETHeapResetFailed));

		}

	Initialise();

	Unlock();

	}