// Copyright (c) 2005-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:

//

#include "memmodel.h"

#include "mm.h"

#include "mmu.h"

#include "mpager.h"

#include "mrom.h"

#include "mobject.h"

#include "mmapping.h"

#include "maddressspace.h"

#include "mmanager.h"

#include "mptalloc.h"

#include "mpagearray.h"

#include "mswap.h"

#include "mthrash.h"

#include "cache_maintenance.inl"

const TUint16 KDefaultYoungOldRatio = 3;

const TUint16 KDefaultMinPages = 256;

#ifdef _USE_OLDEST_LISTS

const TUint16 KDefaultOldOldestRatio = 3;

#endif

const TUint KMinOldPages = 1;

/*	On a 32 bit system without PAE can't have more than 2^(32-KPageShift) pages.

 *	Subtract 1 so it doesn't overflow when converted to bytes.

*/

const TUint	KAbsoluteMaxPageCount = (1u<<(32-KPageShift))-1u;

DPager ThePager;

DPager::DPager()

	: iMinimumPageCount(0), iMaximumPageCount(0), iYoungOldRatio(0),

	  iYoungCount(0),iOldCount(0),iNumberOfFreePages(0)

	{

	}

void DPager::Init2()

	{

	TRACEB(("DPager::Init2()"));

#if defined(__CPU_ARM)

/** Minimum number of young pages the demand paging live list may have.

	Need at least 4 mapped pages to guarantee to be able to execute all ARM instructions,

	plus enough pages for 4 page tables to map those pages, plus enough pages for the

	page table info structures of those page tables.

	(Worst case is a Thumb-2 STM instruction with both instruction and data straddling chunk

	boundaries.)

*/

	iMinYoungPages = 4											// pages

					+(4+KPtClusterSize-1)/KPtClusterSize		// page table pages

					+(4+KPageTableInfosPerPage-1)/KPageTableInfosPerPage;	// page table info pages

#elif defined(__CPU_X86)

/*	Need at least 6 mapped pages to guarantee to be able to execute all ARM instructions,

	plus enough pages for 6 page tables to map those pages, plus enough pages for the

	page table info structures of those page tables.

	(Worst case is (?) a MOV [X],[Y] instruction with instruction, 'X' and 'Y' all

	straddling chunk boundaries.)

*/

	iMinYoungPages = 6											// pages

					+(6+KPtClusterSize-1)/KPtClusterSize		// page table pages

					+(6+KPageTableInfosPerPage-1)/KPageTableInfosPerPage;	// page table info pages

#else

#error Unknown CPU

#endif

#ifdef __SMP__

	// Adjust min page count so that all CPUs are guaranteed to make progress.

	// NOTE: Can't use NKern::NumberOfCpus here because we haven't finished booting yet and will

	// always have only one CPU running at this point...

	// TODO: Before we can enable this the base test configuration needs

	// updating to have a sufficient minimum page size...

	//

	// iMinYoungPages *= KMaxCpus;

#endif

	// A minimum young/old ratio of 1 means that we need at least twice iMinYoungPages pages...

	iAbsoluteMinPageCount = 2*iMinYoungPages;

	__NK_ASSERT_DEBUG(KMinOldPages<=iAbsoluteMinPageCount/2);

	// initialise live list...

	TUint minimumPageCount = 0;

	TUint maximumPageCount = 0;

	SDemandPagingConfig config = TheRomHeader().iDemandPagingConfig;

	iMinimumPageCount = KDefaultMinPages;

	if(minimumPageCount)

		iMinimumPageCount = minimumPageCount;

	if(config.iMinPages)

		iMinimumPageCount = config.iMinPages;

	if(iMinimumPageCount<iAbsoluteMinPageCount)

		iMinimumPageCount = iAbsoluteMinPageCount;

	iInitMinimumPageCount = iMinimumPageCount;

	iMaximumPageCount = KMaxTInt;

	if(maximumPageCount)

		iMaximumPageCount = maximumPageCount;

	if(config.iMaxPages)

		iMaximumPageCount = config.iMaxPages;

	if (iMaximumPageCount > KAbsoluteMaxPageCount)

		iMaximumPageCount = KAbsoluteMaxPageCount;

	iInitMaximumPageCount = iMaximumPageCount;

	iYoungOldRatio = KDefaultYoungOldRatio;

	if(config.iYoungOldRatio)

		iYoungOldRatio = config.iYoungOldRatio;

	TInt ratioLimit = (iMinimumPageCount-KMinOldPages)/KMinOldPages;

	if(iYoungOldRatio>ratioLimit)

		iYoungOldRatio = ratioLimit;

#ifdef _USE_OLDEST_LISTS

	iOldOldestRatio = KDefaultOldOldestRatio;

	if(config.iSpare[2])

		iOldOldestRatio = config.iSpare[2];

#endif

	iMinimumPageLimit = (iMinYoungPages * (1 + iYoungOldRatio)) / iYoungOldRatio;

	if(iMinimumPageLimit<iAbsoluteMinPageCount)

		iMinimumPageLimit = iAbsoluteMinPageCount;

	TRACEB(("DPager::Init2() live list min=%d max=%d ratio=%d",iMinimumPageCount,iMaximumPageCount,iYoungOldRatio));

	if(iMaximumPageCount<iMinimumPageCount)

		__NK_ASSERT_ALWAYS(0);

	//

	// This routine doesn't acquire any mutexes because it should be called before the system

	// is fully up and running. I.e. called before another thread can preempt this.

	//

	// Calculate page counts

	TUint minOldAndOldest = iMinimumPageCount / (1 + iYoungOldRatio);

	if(minOldAndOldest < KMinOldPages)

		__NK_ASSERT_ALWAYS(0);

	if (iMinimumPageCount < minOldAndOldest)

		__NK_ASSERT_ALWAYS(0);

	TUint minYoung = iMinimumPageCount - minOldAndOldest;

	if(minYoung < iMinYoungPages)

		__NK_ASSERT_ALWAYS(0); // Need at least iMinYoungPages pages mapped to execute worst case CPU instruction

#ifdef _USE_OLDEST_LISTS

	// There should always be enough old pages to allow the oldest lists ratio.

	TUint oldestCount = minOldAndOldest / (1 + iOldOldestRatio);

	if (!oldestCount)

		__NK_ASSERT_ALWAYS(0);

#endif

	iNumberOfFreePages = 0;

	iNumberOfDirtyPages = 0;

	// Allocate RAM pages and put them all on the old list

	RamAllocLock::Lock();

	iYoungCount = 0;

	iOldCount = 0;

#ifdef _USE_OLDEST_LISTS

	iOldestCleanCount = 0;

	iOldestDirtyCount = 0;

#endif

	Mmu& m = TheMmu;

	for(TUint i=0; i<iMinimumPageCount; i++)

		{

		// Allocate a single page

		TPhysAddr pagePhys;

		TInt r = m.AllocRam(&pagePhys, 1, 

							(Mmu::TRamAllocFlags)(EMemAttNormalCached|Mmu::EAllocNoWipe|Mmu::EAllocNoPagerReclaim), 

							EPageDiscard);

		if(r!=KErrNone)

			__NK_ASSERT_ALWAYS(0);

		MmuLock::Lock();

		AddAsFreePage(SPageInfo::FromPhysAddr(pagePhys));

		MmuLock::Unlock();

		}

	RamAllocLock::Unlock();

#ifdef _USE_OLDEST_LISTS

	TRACEB(("DPager::Init2() end with young=%d old=%d oldClean=%d oldDirty=%d min=%d free=%d max=%d",iYoungCount,iOldCount,iOldestCleanCount,iOldestDirtyCount,iMinimumPageCount,iNumberOfFreePages,iMaximumPageCount));

#else

	TRACEB(("DPager::Init2() end with young=%d old=%d min=%d free=%d max=%d",iYoungCount,iOldCount,iMinimumPageCount,iNumberOfFreePages,iMaximumPageCount));

#endif

	}

#ifdef _DEBUG

TBool DPager::CheckLists()

	{

#if 0

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	SDblQueLink* head = &iOldList.iA;

	TInt n = iOldCount;

	SDblQueLink* link = head;

	while(n--)

		{

		link = link->iNext;

		if(link==head)

			return false;

		}

	link = link->iNext;

	if(link!=head)

		return false;

	head = &iYoungList.iA;

	n = iYoungCount;

	link = head;

	while(n--)

		{

		link = link->iNext;

		if(link==head)

			return false;

		}

	link = link->iNext;

	if(link!=head)

		return false;

//	TRACEP(("DP: y=%d o=%d f=%d",iYoungCount,iOldCount,iNumberOfFreePages));

#endif

//	TraceCounts();

	return true;

	}

void DPager::TraceCounts()

	{

	TRACEP(("DP: y=%d o=%d f=%d min=%d max=%d ml=%d res=%d",

		iYoungCount,iOldCount,iNumberOfFreePages,iMinimumPageCount,

		iMaximumPageCount,iMinimumPageLimit,iReservePageCount));

	}

#endif

TBool DPager::HaveTooManyPages()

	{

	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	return iMinimumPageCount+iNumberOfFreePages > iMaximumPageCount;

	}

TBool DPager::HaveMaximumPages()

	{

	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	return iMinimumPageCount+iNumberOfFreePages >= iMaximumPageCount;

	}

void DPager::AddAsYoungestPage(SPageInfo* aPageInfo)

	{

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	__NK_ASSERT_DEBUG(CheckLists());

	__NK_ASSERT_DEBUG(aPageInfo->PagedState()==SPageInfo::EUnpaged);

	aPageInfo->SetPagedState(SPageInfo::EPagedYoung);

	iYoungList.AddHead(&aPageInfo->iLink);

	++iYoungCount;

	}

void DPager::AddAsFreePage(SPageInfo* aPageInfo)

	{

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	__NK_ASSERT_DEBUG(CheckLists());

	__NK_ASSERT_DEBUG(aPageInfo->PagedState()==SPageInfo::EUnpaged);

	TheMmu.PageFreed(aPageInfo);

	__NK_ASSERT_DEBUG(aPageInfo->PagedState()==SPageInfo::EUnpaged);

	// add as oldest page...

#ifdef _USE_OLDEST_LISTS

	aPageInfo->SetPagedState(SPageInfo::EPagedOldestClean);

	iOldestCleanList.Add(&aPageInfo->iLink);

	++iOldestCleanCount;

#else

	aPageInfo->SetPagedState(SPageInfo::EPagedOld);

	iOldList.Add(&aPageInfo->iLink);

	++iOldCount;

#endif

	Event(EEventPageInFree,aPageInfo);

	}

TInt DPager::PageFreed(SPageInfo* aPageInfo)

	{

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	__NK_ASSERT_DEBUG(CheckLists());

	switch(aPageInfo->PagedState())

		{

	case SPageInfo::EUnpaged:

		return KErrNotFound;

	case SPageInfo::EPagedYoung:

		__NK_ASSERT_DEBUG(iYoungCount);

		aPageInfo->iLink.Deque();

		--iYoungCount;

		break;

	case SPageInfo::EPagedOld:

		__NK_ASSERT_DEBUG(iOldCount);

		aPageInfo->iLink.Deque();

		--iOldCount;

		break;

#ifdef _USE_OLDEST_LISTS

	case SPageInfo::EPagedOldestClean:

		__NK_ASSERT_DEBUG(iOldestCleanCount);

		aPageInfo->iLink.Deque();

		--iOldestCleanCount;

		break;

	case SPageInfo::EPagedOldestDirty:

		__NK_ASSERT_DEBUG(iOldestDirtyCount);

		aPageInfo->iLink.Deque();

		--iOldestDirtyCount;

		break;

#endif

	case SPageInfo::EPagedPinned:

		// this can occur if a pinned mapping is being unmapped when memory is decommitted.

		// the decommit will have succeeded because the the mapping no longer vetoes this,

		// however the unpinning hasn't yet got around to changing the page state.

		// When the state change happens the page will be put back on the live list so

		// we don't have to do anything now...

		return KErrNone;

	case SPageInfo::EPagedPinnedMoved:

		// This page was pinned when it was moved but it has not been returned 

		// to the free pool yet so make sure it is...

		aPageInfo->SetPagedState(SPageInfo::EUnpaged);	// Must be unpaged before returned to free pool.

		return KErrNotFound;

	default:

		__NK_ASSERT_DEBUG(0);

		return KErrNotFound;

		}

	// Update the dirty page count as required...

	if (aPageInfo->IsDirty())

		SetClean(*aPageInfo);

	// add as oldest page...

#ifdef _USE_OLDEST_LISTS

	aPageInfo->SetPagedState(SPageInfo::EPagedOldestClean);

	iOldestCleanList.Add(&aPageInfo->iLink);

	++iOldestCleanCount;

#else

	aPageInfo->SetPagedState(SPageInfo::EPagedOld);

	iOldList.Add(&aPageInfo->iLink);

	++iOldCount;

#endif

	return KErrNone;

	}

extern TBool IsPageTableUnpagedRemoveAllowed(SPageInfo* aPageInfo);

void DPager::RemovePage(SPageInfo* aPageInfo)

	{

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	__NK_ASSERT_DEBUG(CheckLists());

	switch(aPageInfo->PagedState())

		{

	case SPageInfo::EPagedYoung:

		__NK_ASSERT_DEBUG(iYoungCount);

		aPageInfo->iLink.Deque();

		--iYoungCount;

		break;

	case SPageInfo::EPagedOld:

		__NK_ASSERT_DEBUG(iOldCount);

		aPageInfo->iLink.Deque();

		--iOldCount;

		break;

#ifdef _USE_OLDEST_LISTS

	case SPageInfo::EPagedOldestClean:

		__NK_ASSERT_DEBUG(iOldestCleanCount);

		aPageInfo->iLink.Deque();

		--iOldestCleanCount;

		break;

	case SPageInfo::EPagedOldestDirty:

		__NK_ASSERT_DEBUG(iOldestDirtyCount);

		aPageInfo->iLink.Deque();

		--iOldestDirtyCount;

		break;

#endif

	case SPageInfo::EPagedPinned:

		__NK_ASSERT_DEBUG(0);

	case SPageInfo::EUnpaged:

#ifdef _DEBUG

		if (!IsPageTableUnpagedRemoveAllowed(aPageInfo))

			__NK_ASSERT_DEBUG(0);

		break;

#endif

	default:

		__NK_ASSERT_DEBUG(0);

		return;

		}

	aPageInfo->SetPagedState(SPageInfo::EUnpaged);

	}

void DPager::ReplacePage(SPageInfo& aOldPageInfo, SPageInfo& aNewPageInfo)

	{

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	__NK_ASSERT_DEBUG(CheckLists());

	__NK_ASSERT_DEBUG(aOldPageInfo.PagedState() == aNewPageInfo.PagedState());

	switch(aOldPageInfo.PagedState())

		{

		case SPageInfo::EPagedYoung:

		case SPageInfo::EPagedOld:

		case SPageInfo::EPagedOldestClean:

		case SPageInfo::EPagedOldestDirty:

			{// Update the list links point to the new page.

			__NK_ASSERT_DEBUG(iYoungCount);

			SDblQueLink* prevLink = aOldPageInfo.iLink.iPrev;

#ifdef _DEBUG

			SDblQueLink* nextLink = aOldPageInfo.iLink.iNext;

			__NK_ASSERT_DEBUG(prevLink == aOldPageInfo.iLink.iPrev);

			__NK_ASSERT_DEBUG(prevLink->iNext == &aOldPageInfo.iLink);

			__NK_ASSERT_DEBUG(nextLink == aOldPageInfo.iLink.iNext);

			__NK_ASSERT_DEBUG(nextLink->iPrev == &aOldPageInfo.iLink);

#endif

			aOldPageInfo.iLink.Deque();

			aNewPageInfo.iLink.InsertAfter(prevLink);

			aOldPageInfo.SetPagedState(SPageInfo::EUnpaged);

#ifdef _DEBUG

			__NK_ASSERT_DEBUG(prevLink == aNewPageInfo.iLink.iPrev);

			__NK_ASSERT_DEBUG(prevLink->iNext == &aNewPageInfo.iLink);

			__NK_ASSERT_DEBUG(nextLink == aNewPageInfo.iLink.iNext);

			__NK_ASSERT_DEBUG(nextLink->iPrev == &aNewPageInfo.iLink);

#endif

			}

			break;

		case SPageInfo::EPagedPinned:

			// Mark the page as 'pinned moved' so that when the page moving invokes 

			// Mmu::FreeRam() it returns this page to the free pool.

			aOldPageInfo.ClearPinCount();

			aOldPageInfo.SetPagedState(SPageInfo::EPagedPinnedMoved);

			break;

		case SPageInfo::EPagedPinnedMoved:

			// Shouldn't happen as the ram alloc mutex will be held for the 

			// entire time the page's is paged state == EPagedPinnedMoved.

		case SPageInfo::EUnpaged:

			// Shouldn't happen as we only move pinned memory and unpinning will 

			// atomically add the page to the live list and it can't be removed 

			// from the live list without the ram alloc mutex.

			__NK_ASSERT_DEBUG(0);

			break;

		}	

	}

SPageInfo* DPager::StealOldestPage()

	{

	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	for(;;)

		{

		// find oldest page in list...

		SDblQueLink* link;

#ifdef _USE_OLDEST_LISTS

		if (iOldestCleanCount)

			{

			__NK_ASSERT_DEBUG(!iOldestCleanList.IsEmpty());

			link = iOldestCleanList.Last();

			}

		else if (iOldestDirtyCount)

			{

			__NK_ASSERT_DEBUG(!iOldestDirtyList.IsEmpty());

			link = iOldestDirtyList.Last();

			}

		else if (iOldCount)

#else

		if (iOldCount)

#endif

			{

			__NK_ASSERT_DEBUG(!iOldList.IsEmpty());

			link = iOldList.Last();

			}

		else

			{

			__NK_ASSERT_DEBUG(iYoungCount);

			__NK_ASSERT_ALWAYS(!iYoungList.IsEmpty());

			link = iYoungList.Last();

			}

		SPageInfo* pageInfo = SPageInfo::FromLink(link);

		// steal it from owning object...

		TInt r = StealPage(pageInfo);

		BalanceAges();

		if(r==KErrNone)

			return pageInfo; // done