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

/**

Default limit for the maximum number of oldest pages.

If the data paging device sets iPreferredWriteShift, then this is increased if necessary to allow

that many pages to be present.

This limit exists to make our live list implementation a closer approximation to LRU, and to bound

the time taken by SelectSequentialPagesToClean(), which is called with the MmuLock held.

*/

const TUint KDefaultMaxOldestPages = 32;

static DMutex* ThePageCleaningLock = NULL;

DPager ThePager;

DPager::DPager() :

	iMinimumPageCount(0),

	iMaximumPageCount(0),

	iYoungOldRatio(0),

	iYoungCount(0),

	iOldCount(0),

	iOldestCleanCount(0),

	iMaxOldestPages(KDefaultMaxOldestPages),

	iNumberOfFreePages(0),

	iReservePageCount(0),

	iMinimumPageLimit(0),

	iPagesToClean(1)

#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(RamAllocLock::IsHeld());

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

		return KErrCompletion;

	default:

		__NK_ASSERT_DEBUG(0);

		return KErrNotFound;

		}

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

	if (aPageInfo->IsDirty())

		{

		aPageInfo->SetReadOnly();

		SetClean(*aPageInfo);

		}

	if (iNumberOfFreePages > 0)

		{// The paging cache is not at the minimum size so safe to let the 

		// ram allocator free this page.

		iNumberOfFreePages--;

		aPageInfo->SetPagedState(SPageInfo::EUnpaged);

		return KErrCompletion;

		}

	// Need to hold onto this page as have reached the page cache limit.

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

#endif

		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:

			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::StealOrAllocPage(TBool aAllowAlloc, Mmu::TRamAllocFlags aAllocFlags)

	{

	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

	// The PageCleaningLock may or may not be held to start with

	TBool pageCleaningLockAcquired = EFalse;

	SDblQueLink* link;

	SPageInfo* pageInfo ;

restart:

	// if there is a free page in the live list then use that (it will be at the end)...