// 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 "mpagecleaner.h"

#include "cache_maintenance.inl"

const TUint16 KDefaultYoungOldRatio = 3;

const TUint16 KDefaultMinPages = 256;

const TUint16 KDefaultOldOldestRatio = 3;

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;

/*

Limit the maximum number of oldest pages to bound the time taken by SelectPagesToClean(), which is

called with the MmuLock held.

*/

const TUint KMaxOldestPages = 32;

static DMutex* ThePageCleaningLock = NULL;

DPager ThePager;

DPager::DPager()

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

	  iYoungCount(0), iOldCount(0), iOldestCleanCount(0),

	  iNumberOfFreePages(0), iReservePageCount(0), iMinimumPageLimit(0)

#ifdef __DEMAND_PAGING_BENCHMARKS__

	, iBenchmarkLock(TSpinLock::EOrderGenericIrqHigh3)

#endif	  

	{

	}

void DPager::InitCache()

	{

	//

	// 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.

	//

	TRACEB(("DPager::InitCache()"));

	// If any pages have been reserved then they will have already been allocated and 

	// therefore should be counted as part of iMinimumPageCount.

	__NK_ASSERT_DEBUG(iReservePageCount == iMinimumPageCount);

	__NK_ASSERT_DEBUG(!CacheInitialised());

#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 X86 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.

	TInt numberOfCpus = NKern::NumberOfCpus();

	iMinYoungPages *= numberOfCpus;

#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);

	// Read any paging config data.

	SDemandPagingConfig config = TheRomHeader().iDemandPagingConfig;

	// Set the list ratios...

	iYoungOldRatio = KDefaultYoungOldRatio;

	if(config.iYoungOldRatio)

		iYoungOldRatio = config.iYoungOldRatio;

	iOldOldestRatio = KDefaultOldOldestRatio;

	if(config.iSpare[2])

		iOldOldestRatio = config.iSpare[2];

	// Set the minimum page counts...

	iMinimumPageLimit = iMinYoungPages * (1 + iYoungOldRatio) / iYoungOldRatio

									   + DPageReadRequest::ReservedPagesRequired();

	if(iMinimumPageLimit < iAbsoluteMinPageCount)

		iMinimumPageLimit = iAbsoluteMinPageCount;

	if (K::MemModelAttributes & (EMemModelAttrRomPaging | EMemModelAttrCodePaging | EMemModelAttrDataPaging))

	    iMinimumPageCount = KDefaultMinPages; 

	else

		{// No paging is enabled so set the minimum cache size to the minimum

		// allowable with the current young old ratio.

	    iMinimumPageCount = iMinYoungPages * (iYoungOldRatio + 1);

		}

	if(config.iMinPages)

		iMinimumPageCount = config.iMinPages;

	if(iMinimumPageCount < iAbsoluteMinPageCount)

		iMinimumPageCount = iAbsoluteMinPageCount;

	if (iMinimumPageLimit + iReservePageCount > iMinimumPageCount)

		iMinimumPageCount = iMinimumPageLimit + iReservePageCount;

	iInitMinimumPageCount = iMinimumPageCount;

	// Set the maximum page counts...

	iMaximumPageCount = KMaxTInt;

	if(config.iMaxPages)

		iMaximumPageCount = config.iMaxPages;

	if (iMaximumPageCount > KAbsoluteMaxPageCount)

		iMaximumPageCount = KAbsoluteMaxPageCount;

	iInitMaximumPageCount = iMaximumPageCount;

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

	// Verify the page counts are valid.

	__NK_ASSERT_ALWAYS(iMaximumPageCount >= iMinimumPageCount);

	TUint minOldAndOldest = iMinimumPageCount / (1 + iYoungOldRatio);

	__NK_ASSERT_ALWAYS(minOldAndOldest >= KMinOldPages);

	__NK_ASSERT_ALWAYS(iMinimumPageCount >= minOldAndOldest);

	// Need at least iMinYoungPages pages mapped to execute worst case CPU instruction

	TUint minYoung = iMinimumPageCount - minOldAndOldest;

	__NK_ASSERT_ALWAYS(minYoung >= iMinYoungPages);

	// Verify that the young old ratio can be met even when there is only the 

	// minimum number of old pages.

	TInt ratioLimit = (iMinimumPageCount-KMinOldPages)/KMinOldPages;

	__NK_ASSERT_ALWAYS(iYoungOldRatio <= ratioLimit);

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

	TUint oldestCount = minOldAndOldest / (1 + iOldOldestRatio);

	__NK_ASSERT_ALWAYS(oldestCount);

	iNumberOfFreePages = 0;

	iNumberOfDirtyPages = 0;

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

	// Reserved pages have already been allocated and already placed on the

	// old list so don't allocate them again.

	RamAllocLock::Lock();

	iYoungCount = 0;

	iOldCount = 0;

	iOldestDirtyCount = 0;

	__NK_ASSERT_DEBUG(iOldestCleanCount == iReservePageCount);

	Mmu& m = TheMmu;

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

		{

		// Allocate a single page

		TPhysAddr pagePhys;

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

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

							EPageDiscard);

		__NK_ASSERT_ALWAYS(r == KErrNone);

		MmuLock::Lock();

		AddAsFreePage(SPageInfo::FromPhysAddr(pagePhys));

		MmuLock::Unlock();

		}

	RamAllocLock::Unlock();

	__NK_ASSERT_DEBUG(CacheInitialised());

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

	}

#ifdef _DEBUG

#ifdef FMM_PAGER_CHECK_LISTS

TBool CheckList(SDblQueLink* aHead, TUint aCount)

	{

	SDblQueLink* link = aHead;

	while(aCount--)

		{

		link = link->iNext;

		if(link == aHead)

			return EFalse;

		}

	link = link->iNext;

	if(link != aHead)

		return EFalse;

	return ETrue;

	}

#endif // #ifdef FMM_PAGER_CHECK_LISTS

TBool DPager::CheckLists()

	{

#ifdef FMM_PAGER_CHECK_LISTS

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	if (!CheckList(&iOldList.iA, iOldCount))

		return EFalse;

	if (!CheckList(&iYoungList.iA, iYoungCount))

		return EFalse;

	if (!CheckList(&iOldestCleanList.iA, iOldestCleanCount))

		return EFalse;

	if (!CheckList(&iOldestDirtyList.iA, iOldestDirtyCount))

		return EFalse;

	TRACEP(("DP: y=%d o=%d oc=%d od=%d f=%d", iYoungCount, iOldCount, 

			iOldestCleanCount, iOldestDirtyCount, iNumberOfFreePages));

	TraceCounts();

#endif // #ifdef FMM_PAGER_CHECK_LISTS

	return true;

	}

void DPager::TraceCounts()

	{

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

		iYoungCount, iOldCount, iOldestCleanCount, iOldestDirtyCount, 

		iNumberOfFreePages, iMinimumPageCount, iMaximumPageCount,

		iMinimumPageLimit, iReservePageCount));

	}

#endif //#ifdef _DEBUG

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...

	aPageInfo->SetPagedState(SPageInfo::EPagedOldestClean);

	iOldestCleanList.Add(&aPageInfo->iLink);

	++iOldestCleanCount;

	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;

	case SPageInfo::EPagedOldestClean:

		__NK_ASSERT_DEBUG(iOldestCleanCount);

		aPageInfo->iLink.Deque();

		--iOldestCleanCount;

		break;

	case SPageInfo::EPagedOldestDirty:

		__NK_ASSERT_DEBUG(iOldestDirtyCount);

		aPageInfo->iLink.Deque();

		--iOldestDirtyCount;

		break;

	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.

	default:

		__NK_ASSERT_DEBUG(0);

		return KErrNotFound;

		}

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

	if (aPageInfo->IsDirty())

		{

		aPageInfo->SetReadOnly();

		SetClean(*aPageInfo);

		}

	// add as oldest page...

	aPageInfo->SetPagedState(SPageInfo::EPagedOldestClean);

	iOldestCleanList.Add(&aPageInfo->iLink);

	++iOldestCleanCount;

	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;

	case SPageInfo::EPagedOldestClean:

		__NK_ASSERT_DEBUG(iOldestCleanCount);

		aPageInfo->iLink.Deque();

		--iOldestCleanCount;

		break;

	case SPageInfo::EPagedOldestDirty:

		__NK_ASSERT_DEBUG(iOldestDirtyCount);

		aPageInfo->iLink.Deque();

		--iOldestDirtyCount;

		break;

	case SPageInfo::EPagedPinned:

		__NK_ASSERT_DEBUG(0);

	case SPageInfo::EUnpaged:

#ifdef _DEBUG

		if (!IsPageTableUnpagedRemoveAllowed(aPageInfo))

			__NK_ASSERT_DEBUG(0);

		break;

	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;

		}	

	}

TInt DPager::TryStealOldestPage(SPageInfo*& aPageInfoOut)

	{

	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	// find oldest page in list...

	SDblQueLink* link;

	if (iOldestCleanCount)

		{

		__NK_ASSERT_DEBUG(!iOldestCleanList.IsEmpty());

		link = iOldestCleanList.Last();

		}

	else if (iOldestDirtyCount)

		{

		__NK_ASSERT_DEBUG(!iOldestDirtyList.IsEmpty());

		link = iOldestDirtyList.Last();

		}

	else if (iOldCount)

		{

		__NK_ASSERT_DEBUG(!iOldList.IsEmpty());

		link = iOldList.Last();

		}

	else

		{

		__NK_ASSERT_DEBUG(iYoungCount);

		__NK_ASSERT_ALWAYS(!iYoungList.IsEmpty());

		link = iYoungList.Last();