// Copyright (c) 1998-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\memmodel\epoc\mmubase\ramalloc.cpp

// 

//

/**

 @file

 @internalComponent

*/

//#define __VERIFY_LEASTMOVDIS

#include <plat_priv.h>

#include <ramalloc.h>

#include <e32btrace.h>

#ifndef __MEMMODEL_FLEXIBLE__

#include <mmubase.inl>

#else

#include "mdefrag.inl"

#endif //__MEMMODEL_FLEXIBLE__

DRamAllocator* DRamAllocator::New()

	{

	return new DRamAllocator;

	}

DRamAllocator* DRamAllocator::New(const SRamInfo& aInfo, const SRamZone* aZoneInfo, TRamZoneCallback aZoneCallback)

	{

	DRamAllocator* pA=New();

	if (!pA)

		Panic(ECreateNoMemory);

	// If this fails then it won't return but panic

	pA->Create(aInfo,aZoneInfo, aZoneCallback);

	return pA;

	}

void DRamAllocator::Panic(TPanic aPanic)

	{

	Kern::Fault("RAM-ALLOC", aPanic);

	}

#ifdef KMMU

void HexDump32(const TAny* a, TInt n, const char* s)

	{

	const TUint32* p=(const TUint32*)a;

	Kern::Printf(s);

	TInt i=0;

	while(n)

		{

		TBuf8<80> b;

		b.AppendNumFixedWidth(i,EHex,4);

		b.Append(':');

		TInt m=Min(n,4);

		n-=m;

		i+=m;

		while(m--)

			{

			b.Append(' ');

			b.AppendNumFixedWidth(*p++,EHex,8);

			}

		Kern::Printf("%S",&b);

		}

	}

void HexDump8(const TAny* a, TInt n, const char* s)

	{

	const TUint8* p=(const TUint8*)a;

	Kern::Printf(s);

	TInt i=0;

	while(n)

		{

		TBuf8<80> b;

		b.AppendNumFixedWidth(i,EHex,4);

		b.Append(':');

		TInt m=Min(n,16);

		n-=m;

		i+=m;

		while(m--)

			{

			b.Append(' ');

			b.AppendNumFixedWidth(*p++,EHex,2);

			}

		Kern::Printf("%S",&b);

		}

	}

void DRamAllocator::DebugDump()

	{

	Kern::Printf("PageSize=%08x PageShift=%d",KPageSize,KPageShift);

	Kern::Printf("Total Pages=%x Total Free=%x",iTotalRamPages,iTotalFreeRamPages);

	Kern::Printf("Number of zones=%d, PowerState=%016lx",iNumZones,iZonePwrState);

	Kern::Printf("PhysAddrBase=%08x, PhysAddrTop=%08x",iPhysAddrBase,iPhysAddrTop);

	TUint i = 0;

	Kern::Printf("Zone Info:");

	for (; i<iNumZones; ++i)

		{

		SZone& z=iZones[i];

		TBitMapAllocator& b = *(z.iBma[KBmaAllPages]);

		Kern::Printf("%x: Avail %x Size %x Phys %08x PhysEnd %08x ID %08x FreePage %x Pref %02x",i,b.iAvail,b.iSize,

										z.iPhysBase, z.iPhysEnd, z.iId,z.iFreePages, z.iPref);

		Kern::Printf("Allocated Unknown %x Fixed %x Movable %x Discardable %x",iZones[i].iAllocPages[EPageUnknown],iZones[i].iAllocPages[EPageFixed],

										iZones[i].iAllocPages[EPageMovable],iZones[i].iAllocPages[EPageDiscard]);

		}

	Kern::Printf("Zone pref order:");

	SDblQueLink* link = iZonePrefList.First();

	for (; link != &iZonePrefList.iA; link = link->iNext)

		{

		SZone& zone = *_LOFF(link, SZone, iPrefLink);

		Kern::Printf("ID0x%x rank0x%x", zone.iId, zone.iPrefRank);

		}

	SZone& zone = *_LOFF(iZoneLeastMovDis, SZone, iPrefLink);

	Kern::Printf("iZoneLeastMovDis ID 0x%x rank 0x%x", zone.iId, iZoneLeastMovDisRank);

	}

#endif

TInt CountBanks(const SRamBank* aBankList)

	{

	TInt banks=0;

	for (; aBankList->iSize; ++banks, ++aBankList);

	return banks;

	}

TUint32 TotalBankSize(const SRamBank* aBankList)

	{

	TUint32 size=0;

	for (; aBankList->iSize; ++aBankList)

		size+=aBankList->iSize;

	return size;

	}

/**

Count how many zones have been specified and do some basic checks on their layout:

	Zones must be distinct, i.e. not overlap

	Zone ID must be unique

	Zones must be page size aligned

	Zones must be big enough to cover all of the allocatable RAM

The end of the list is indicated by a SRamZone.iSize==0. 

@param aZones The list of RAM zones to be setup

*/

void DRamAllocator::CountZones(const SRamZone* aZones)

	{

	TUint32 totalSize = 0;

	TUint32 pageMask = KPageSize-1;

	// Check zones don't overlap each other and while running through the zones

	// calculate how many there are

	const SRamZone* pCurZ = aZones;

	for (; pCurZ->iSize != 0; pCurZ++)

		{

		// Verify zone addresses and alignment

		TUint32 curEnd = pCurZ->iBase + pCurZ->iSize - 1;

		__KTRACE_OPT(KMMU,Kern::Printf("curBase %x curEnd %x pageMask %x",pCurZ->iBase,curEnd,pageMask));

		if (curEnd <= pCurZ->iBase || (((curEnd + 1) | pCurZ->iBase) & pageMask))

			{

			Panic(EZonesAlignment);

			}

		if (pCurZ->iId == KRamZoneInvalidId)

			{

			Panic(EZonesIDInvalid);

			}

		// Check the flags are not set to invalid values

		if (pCurZ->iFlags & KRamZoneFlagInvalid)

			{

			Panic(EZonesFlagsInvalid);

			}

		iNumZones++;

		if (iNumZones > KMaxRamZones)

			{// Too many zones specified

			Panic(EZonesTooNumerousOrFew);

			}

		totalSize += pCurZ->iSize;

		// Verify this zone doesn't overlap any of the previous zones' address space

		const SRamZone* pTmpZ = aZones;

		for (; pTmpZ < pCurZ; pTmpZ++)

			{

			TUint32 tmpEnd = pTmpZ->iBase + pTmpZ->iSize - 1;

			if (tmpEnd >= pCurZ->iBase && pTmpZ->iBase <= curEnd)

				{

				Panic(EZonesNotDistinct);

				}

			if(pTmpZ->iId == pCurZ->iId)

				{

				Panic(EZonesIDNotUnique);

				}

			}

		}

	__KTRACE_OPT(KMMU,Kern::Printf("iNumZones=%d, totalSize=%x",iNumZones,totalSize));

	if (!iNumZones)

		{// no zones specified

		Panic(EZonesTooNumerousOrFew);

		}

	// Together all of the zones should cover the whole of the RAM

	if (totalSize>>KPageShift < iTotalRamPages)

		{

		Panic(EZonesIncomplete);

		}

	}

/**

Get the zone from the ID

@param aId ID of zone to find

@return Pointer to the zone if zone of matching ID found, NULL otherwise

*/

SZone* DRamAllocator::ZoneFromId(TUint aId) const

	{

	SZone* pZ = iZones;

	const SZone* const pEndZone = iZones + iNumZones;

	for (; pZ < pEndZone; pZ++)

		{

		if (aId == pZ->iId)

			{

			return pZ;

			}

		}

	return NULL;

	}

/** Retrieve the physical base address and number of pages in the specified zone.

@param	aZoneId	The ID of the zone

@param 	aPhysBaseAddr	Receives the base address of the zone

@param	aNumPages	Receives the number of pages in the zone

@return KErrNone if zone found, KErrArgument if zone couldn't be found

*/

TInt DRamAllocator::GetZoneAddress(TUint aZoneId, TPhysAddr& aPhysBase, TUint& aNumPages)

	{

	SZone* zone = ZoneFromId(aZoneId);

	if (zone == NULL)

		{

		return KErrArgument;

		}

	aPhysBase = zone->iPhysBase;

	aNumPages = zone->iPhysPages;

	return KErrNone;

	}

#ifdef __MEMMODEL_FLEXIBLE__

/**

@param aAddr The address of page to find the zone of

@param aOffset The page offset from the start of the zone that the page is in

*/

SZone* DRamAllocator::GetZoneAndOffset(TPhysAddr aAddr, TInt& aOffset)

	{

	// Get the zone from the SPageInfo of the page at aAddr

	SPageInfo* pageInfo = SPageInfo::SafeFromPhysAddr(aAddr);

	if (pageInfo == NULL)

		{

		return NULL;

		}

	// Perform a binary search for the RAM zone, we know aAddr is within a RAM 

	// zone as pageInfo != NULL.

	SZone* left = iZones;

	SZone* mid = iZones + (iNumZones>>1);

	SZone* top = iZones + iNumZones - 1;

	while (mid->iPhysEnd < aAddr || mid->iPhysBase > aAddr)

		{

		if (mid->iPhysEnd < aAddr)

			left = mid + 1;

		else

			top = mid - 1;

		mid = left + ((top - left) >> 1);

		__ASSERT_DEBUG(left <= top && mid <= top && mid >= left, Panic(EAllocRamPagesInconsistent));

		}

	__ASSERT_DEBUG(mid->iPhysBase <= aAddr && mid->iPhysEnd >= aAddr, Panic(EAllocRamPagesInconsistent));

	aOffset = (aAddr - mid->iPhysBase) >> KPageShift;

	__ASSERT_DEBUG((TUint)aOffset < mid->iPhysPages, Panic(EAllocRamPagesInconsistent));

	return mid;

	}

#else

/**

@param aAddr The address of page to find the zone of

@param aOffset The page offset from the start of the zone that the page is in

*/

SZone* DRamAllocator::GetZoneAndOffset(TPhysAddr aAddr, TInt& aOffset)

	{

	// Get the zone from the SPageInfo of the page at aAddr

	SPageInfo* pageInfo = SPageInfo::SafeFromPhysAddr(aAddr);

	if (pageInfo == NULL)

		{

		return NULL;

		}

	SZone* z = iZones + pageInfo->Zone();

	aOffset = (aAddr - z->iPhysBase) >> KPageShift;

	__ASSERT_DEBUG((TUint)aOffset < z->iPhysPages, Panic(EAllocRamPagesInconsistent));

	return z;

	}

#endif

/**

@param aId ID of zone to get page count for

@param aPageData store for page counts

@return KErrNone if zone found, KErrArgument otherwise

*/

TInt DRamAllocator::GetZonePageCount(TUint aId, SRamZonePageCount& aPageData)

	{

	// Search for the zone of ID aId

	const SZone* zone = ZoneFromId(aId);

	if (zone == NULL)

		{

		return KErrArgument;

		}

	aPageData.iFreePages = zone->iFreePages;

	aPageData.iUnknownPages = zone->iAllocPages[EPageUnknown];

	aPageData.iFixedPages = zone->iAllocPages[EPageFixed];

	aPageData.iMovablePages = zone->iAllocPages[EPageMovable];

	aPageData.iDiscardablePages = zone->iAllocPages[EPageDiscard];

	return KErrNone;

	}

/** Update the count of free and allocated pages for the zone with

@param aZone The index of the zone whose counts are being updated

@param aCount The no of pages being allocated

@param aType The type of the pages being allocated

*/

void DRamAllocator::ZoneAllocPages(SZone* aZone, TUint32 aCount, TZonePageType aType)

	{

#ifdef _DEBUG

	TUint32 free = aZone->iFreePages - aCount;

	TUint32 alloc = aZone->iAllocPages[aType] + aCount;

	TUint32 total_alloc = 	aZone->iAllocPages[EPageUnknown] +

							aZone->iAllocPages[EPageDiscard] + 

							aZone->iAllocPages[EPageMovable] + 

							aZone->iAllocPages[EPageFixed] + aCount;

	if (free > aZone->iFreePages || 

		alloc < aZone->iAllocPages[aType] ||

		free + total_alloc != aZone->iPhysPages ||

		iTotalFreeRamPages > iTotalRamPages)

		{

		__KTRACE_OPT(KMMU,Kern::Printf("TotalFree %x TotalPages %x",iTotalFreeRamPages, iTotalRamPages));

		__KTRACE_OPT(KMMU,Kern::Printf("ZoneFreePages - aCount %x free %x, alloc %x",aCount,free,alloc));	// counts rolled over

		__KTRACE_OPT(KMMU,Kern::Printf("Alloc Unk %x Fx %x Mv %x Dis %x",aZone->iAllocPages[EPageUnknown], 

					aZone->iAllocPages[EPageFixed],	aZone->iAllocPages[EPageMovable],aZone->iAllocPages[EPageDiscard]));

		Panic(EZonesCountErr);

		}

	__KTRACE_OPT(KMMU2,Kern::Printf("ZoneFreePages - aCount %x free %x, alloc %x",aCount,free,alloc));

	__KTRACE_OPT(KMMU2,Kern::Printf("Alloc Unk %x Fx %x Mv %x Dis %x",aZone->iAllocPages[EPageUnknown], 

					aZone->iAllocPages[EPageFixed],	aZone->iAllocPages[EPageMovable],aZone->iAllocPages[EPageDiscard]));

	if (!iContiguousReserved)

		{

		__ASSERT_DEBUG(free == (TUint32)aZone->iBma[KBmaAllPages]->iAvail, Panic(EAllocRamPagesInconsistent));

		TBitMapAllocator& bmaType = *(aZone->iBma[(aType != EPageUnknown)? aType : EPageFixed]);

		TUint allocPages;

		if (aType == EPageFixed || aType == EPageUnknown)

			allocPages = aZone->iAllocPages[EPageUnknown] + aZone->iAllocPages[EPageFixed];

		else

			allocPages = aZone->iAllocPages[aType];

		allocPages += aCount;

		__NK_ASSERT_DEBUG(aZone->iPhysPages - bmaType.iAvail == allocPages);

		__NK_ASSERT_DEBUG((TUint)bmaType.iAvail >= aZone->iFreePages - aCount);

//#define _FULL_VERIFY_TYPE_BMAS

#ifdef _FULL_VERIFY_TYPE_BMAS

		TUint offset = 0;

		TUint matchedPages = 0;

		TInt r = KErrNone;

		while (offset < aZone->iPhysPages && r == KErrNone)

			{

			r = NextAllocatedPage(aZone, offset, EPageTypes);

			if (bmaType.NotFree(offset, 1))

				{

				matchedPages++;

				}

			offset++;

			}

		__NK_ASSERT_DEBUG(matchedPages == allocPages);

#endif

		}

#endif

	// Update counts

	aZone->iAllocPages[aType] += aCount;

	aZone->iFreePages -= aCount;

	aZone->iFlags &= ~KRamZoneFlagMark;	// clear the mark as this zone is active

	// Check if power state of zone needs to be changed

	if (iZonePowerFunc && !(iZonePwrState & (((TUint64)1) << aZone - iZones)))

		{//zone no longer empty so call variant to power RAM zone up if necessary

		iZonePwrState |= (((TUint64)1) << aZone - iZones);

		if (iZoneCallbackInitSent)

			{

			TInt ret = (*iZonePowerFunc)(ERamZoneOp_PowerUp, (TAny*)aZone->iId, (TUint*)&iZonePwrState);

			if (ret != KErrNone && ret != KErrNotSupported)

				{

				Panic(EZonesCallbackErr);

				}

			CHECK_PRECONDITIONS(MASK_THREAD_CRITICAL, "DRamAllocator::ZoneAllocPages");

			}

		}

	// Re-order the zone preference list so that a RAM zone with more immovable pages 

	// is more preferable and secondary to that a RAM zone that is not empty is more

	// preferable than one that is empty.

	while (&aZone->iPrefLink != iZonePrefList.First())

		{

		SZone* prevZ = _LOFF(aZone->iPrefLink.iPrev, SZone, iPrefLink);

		__NK_ASSERT_DEBUG(K::Initialising || prevZ->iPrefRank == aZone->iPrefRank - 1);

		if (prevZ->iPref == aZone->iPref && 

			(prevZ->iAllocPages[EPageFixed] + prevZ->iAllocPages[EPageUnknown] < 

			aZone->iAllocPages[EPageFixed] + aZone->iAllocPages[EPageUnknown] ||

			prevZ->iFreePages == prevZ->iPhysPages))

			{

			__KTRACE_OPT(KMMU, Kern::Printf("a - Reorder aZone 0x%x free 0x%x before prevZ 0x%x free 0x%x", aZone->iId, aZone->iFreePages, prevZ->iId, prevZ->iFreePages));

			// Make this RAM zone more preferable.

			aZone->iPrefLink.Deque();

			aZone->iPrefLink.InsertBefore(&prevZ->iPrefLink);

			aZone->iPrefRank--;

			prevZ->iPrefRank++;

			if (iZoneLeastMovDis == &prevZ->iPrefLink)

				{// Ensure iZoneLeastMovDisRank is kept up to date.

				iZoneLeastMovDisRank = prevZ->iPrefRank;

				}

			if (iZoneLeastMovDis == &aZone->iPrefLink)

				{// Ensure iZoneLeastMovDisRank is kept up to date.

				iZoneLeastMovDisRank = aZone->iPrefRank;		

				// aZone was the least preferable with movable and/or discardable so is it still?		

				if (prevZ->iAllocPages[EPageMovable] || prevZ->iAllocPages[EPageDiscard])

					{// prevZ is now the least preferable RAM zone with movable and/or discardable.

					iZoneLeastMovDis = &prevZ->iPrefLink; 

					iZoneLeastMovDisRank = prevZ->iPrefRank;

					__KTRACE_OPT(KMMU, Kern::Printf("aa - iZoneleastInUse ID 0x%x", (_LOFF(iZoneLeastMovDis, SZone, iPrefLink))->iId));

					}

				__KTRACE_OPT(KMMU, Kern::Printf("iZoneLeastMovDisRank 0x%x", iZoneLeastMovDisRank));

				}

			}

		else

			{

			break;

			}

		}

	// Now that the preference list has been re-ordered check whether

	// iZoneLeastMovDis needs updating.

	if (aType >= EPageMovable && iZoneLeastMovDisRank < aZone->iPrefRank)

		{

		iZoneLeastMovDis = &aZone->iPrefLink;

		iZoneLeastMovDisRank = aZone->iPrefRank;

		__KTRACE_OPT(KMMU, Kern::Printf("a - iZoneleastInUse ID 0x%x", (_LOFF(iZoneLeastMovDis, SZone, iPrefLink))->iId));

		}

	__NK_ASSERT_DEBUG(	K::Initialising || 

						iZoneLeastMovDisRank == _LOFF(iZoneLeastMovDis, SZone, iPrefLink)->iPrefRank);

#ifdef __VERIFY_LEASTMOVDIS

	if (!K::Initialising)

		VerifyLeastPrefMovDis();

#endif

	}

/** Update the count of free and allocated pages for the zone with

@param aZone The index of the zone whose counts are being updated

@param aCount The no of pages being freed

@param aType The type of the pages being freed

*/

void DRamAllocator::ZoneFreePages(SZone* aZone, TUint32 aCount, TZonePageType aType)

	{

#ifdef _DEBUG

	TUint32 alloc = aZone->iAllocPages[aType] - aCount;

	TUint32 free = aZone->iFreePages + aCount;

	TUint32 total_alloc = 	aZone->iAllocPages[EPageUnknown] +

							aZone->iAllocPages[EPageDiscard] + 

							aZone->iAllocPages[EPageMovable] + 

							aZone->iAllocPages[EPageFixed] - aCount;

	if (free < aZone->iFreePages ||

		alloc > aZone->iAllocPages[aType] ||

		free + total_alloc != aZone->iPhysPages ||

		iTotalFreeRamPages > iTotalRamPages)

		{

		__KTRACE_OPT(KMMU,Kern::Printf("TotalFree %x TotalPages %x",iTotalFreeRamPages, iTotalRamPages));

		__KTRACE_OPT(KMMU,Kern::Printf("ZoneFreePages - aCount %x free %x, alloc %x",aCount,free,alloc));	// counts rolled over

		__KTRACE_OPT(KMMU,Kern::Printf("Alloc Unk %x Fx %x Mv %x Dis %x",aZone->iAllocPages[EPageUnknown], 

					aZone->iAllocPages[EPageFixed],	aZone->iAllocPages[EPageMovable],aZone->iAllocPages[EPageDiscard]));

		Panic(EZonesCountErr);

		}

	__KTRACE_OPT(KMMU2,Kern::Printf("ZoneFreePages - aCount %x free %x, alloc %x",aCount,free,alloc));

	__KTRACE_OPT(KMMU2,Kern::Printf("Alloc Unk %x Fx %x Mv %x Dis %x",aZone->iAllocPages[EPageUnknown], 

					aZone->iAllocPages[EPageFixed],	aZone->iAllocPages[EPageMovable],aZone->iAllocPages[EPageDiscard]));

	if (!iContiguousReserved)

		{

		__ASSERT_DEBUG(free == (TUint32)aZone->iBma[KBmaAllPages]->iAvail, Panic(EAllocRamPagesInconsistent));

		TBitMapAllocator& bmaType = *(aZone->iBma[(aType != EPageUnknown)? aType : EPageFixed]);

		TUint allocPages;

		if (aType == EPageFixed || aType == EPageUnknown)

			allocPages = aZone->iAllocPages[EPageUnknown] + aZone->iAllocPages[EPageFixed];

		else

			allocPages = aZone->iAllocPages[aType];

		allocPages -= aCount;

		__NK_ASSERT_DEBUG(aZone->iPhysPages - bmaType.iAvail == allocPages);

		__NK_ASSERT_DEBUG((TUint)bmaType.iAvail >= aZone->iFreePages + aCount);

#ifdef _FULL_VERIFY_TYPE_BMAS

		TUint offset = 0;

		TUint matchedPages = 0;

		TInt r = KErrNone;

		while(offset < aZone->iPhysPages && r == KErrNone)

			{

			r = NextAllocatedPage(aZone, offset, EPageTypes);

			if (bmaType.NotFree(offset, 1))

				{

				matchedPages++;

				}

			offset++;

			}