// Copyright (c) 2007-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 <plat_priv.h>

#include "mm.h"

#include "mmu.h"

#include "mpager.h"

#include "mmanager.h"

#include "mmapping.h"

#include "mobject.h"

#include "mptalloc.h"

#include "cache_maintenance.inl"

/**

@class PageTableAllocator

@details

NOTES

Page tables are mapped into a sparse array in the virtual address range

#KPageTableBase..#KPageTableEnd. For each present page table there is a

corresponding #SPageTableInfo object mapped from #KPageTableInfoBase upwards.

Page tables for demand paged content are kept separate from other page tables,

this enables the memory for these to be freed when the page tables no longer map

any memory i.e. when it has all been paged-out. Pages with these 'paged' page

tables are stored in the demand paging live list, so it participates in the page

aging process.

The 'unpaged' page tables are allocated from the bottom of the array upwards,

via TPtPageAllocator::iLowerAllocator; the 'paged' page tables are allocated

from the top of the array downwards, via TPtPageAllocator::iUpperAllocator.

These two regions are prevented from overlapping, or from coming close enough

together so that the #SPageTableInfo struct for paged and unpaged page tables

lie in the same page. This means that the SPageTableInfo memory for paged page

tables can be discarded when it's page tables are discarded.

Memory for page tables and page table info objects is managed by

#ThePageTableMemoryManager. When allocating memory for demand paged use, this

uses memory from #ThePager which will reclaim paged memory if necessary.

Providing the live list always has #DPager::iMinYoungPages, this guarantees that

handling page faults can never fail by running out of memory.

TODO: In really pathological situations page table allocation can fail due to

being out of virtual address space to map the table, this needs to be prevented

from happening when handling demand paging faults.

*/

PageTableAllocator PageTables;

TBool PageTablesLockIsHeld()

	{

	return ::PageTables.LockIsHeld();

	}

/**

Minimum number of page tables to keep in reserve.

*/

const TUint KNumReservedPageTables = 0; // none needed - page tables for mapping page tables and infos are permanently allocated

/**

Manager for the memory object used to store all the MMU page tables.

*/

class DPageTableMemoryManager : public DMemoryManager

	{

public:

	/**

	Not implemented - page table memory is never destroyed.

	*/

	virtual void Destruct(DMemoryObject* aMemory)

		{}

	virtual TInt StealPage(DMemoryObject* aMemory, SPageInfo* aPageInfo)

		{ return PageTables.StealPage(aPageInfo); }

	/**

	Does nothing, returns KErrNone.

	The RAM containing page tables does not need access restrictions applied for demand paging

	purposes. Page table life-time is implicitly managed through the pages it maps.

	*/

	virtual TInt RestrictPage(DMemoryObject* aMemory, SPageInfo* aPageInfo, TRestrictPagesType aRestriction)

		{ return KErrNone; }

	/**

	Does nothing, returns KErrNone.

	The contents of page tables never need saving as their contents are dynamically generated.

	*/

	virtual TInt CleanPage(DMemoryObject* aMemory, SPageInfo* aPageInfo, TPhysAddr*& aPageArrayEntry)

		{ return KErrNone; }

	/**

	Not implemented, returns KErrNotSupported.

	*/

	virtual TInt Pin(DMemoryObject* aMemory, DMemoryMappingBase* aMapping, TPinArgs& aPinArgs)

		{ return KErrNotSupported; }

	/**

	Not implemented.

	*/

	virtual void Unpin(DMemoryObject* aMemory, DMemoryMappingBase* aMapping, TPinArgs& aPinArgs)

		{ }

	virtual TInt MovePage(	DMemoryObject* aMemory, SPageInfo* aOldPageInfo, 

							TPhysAddr& aNewPage, TUint aBlockZoneId, TBool aBlockRest);

public:

	/**

	Allocate a page of RAM for storing page tables in.

	@param aMemory		A memory object associated with this manager.

	@param aIndex		Page index, within the memory, to allocate the page at.

	@param aDemandPaged	True if the memory is to be used for page tables mapping

						demand paged content.

	@return KErrNone if successful, otherwise one of the system wide error codes.

	*/

	TInt Alloc(DMemoryObject* aMemory, TUint aIndex, TBool aDemandPaged);

	/**

	Allocate a page of RAM being used for storing page tables in.

	@param aMemory		A memory object associated with this manager.

	@param aIndex		Page index, within the memory, to free the page from.

	@param aDemandPaged	True if the memory is being used for page tables mapping

						demand paged content.

	@return KErrNone if successful, otherwise one of the system wide error codes.

	*/

	TInt Free(DMemoryObject* aMemory, TUint aIndex, TBool aDemandPaged);

	};

/**

The single instance of the #DPageTableMemoryManager class.

*/

DPageTableMemoryManager ThePageTableMemoryManager;

TInt DPageTableMemoryManager::Alloc(DMemoryObject* aMemory, TUint aIndex, TBool aDemandPaged)

	{

	TRACE2(("DPageTableMemoryManager::Alloc(0x%08x,0x%x,%d)",aMemory, aIndex, aDemandPaged));

	__NK_ASSERT_DEBUG(MemoryObjectLock::IsHeld(aMemory));

	// allocate page array entry...

	RPageArray::TIter pageList;

	TPhysAddr* p = aMemory->iPages.AddPageStart(aIndex,pageList);

	if(!p)

		return KErrNoMemory;

	// allocate RAM...

	RamAllocLock::Lock();

	TPhysAddr pagePhys;

	TInt r;

	if(aDemandPaged)

		{

		r = ThePager.PageInAllocPages(&pagePhys,1,aMemory->RamAllocFlags());

		__NK_ASSERT_DEBUG(r!=KErrNoMemory);

		}

	else

		{// Allocate fixed paged as page tables aren't movable.

		r = TheMmu.AllocRam(&pagePhys, 1, aMemory->RamAllocFlags(), EPageFixed);

		}

	RamAllocLock::Unlock();

	TUint usedNew = 0;

	if(r==KErrNone)

		{

		// add RAM to page array...

		MmuLock::Lock();

		if(aDemandPaged)

			ThePager.Event(DPager::EEventPagePageTableAlloc,SPageInfo::FromPhysAddr(pagePhys));

		SPageInfo* pi = SPageInfo::FromPhysAddr(pagePhys);

		pi->SetManaged(aMemory,aIndex,aMemory->PageInfoFlags());

		RPageArray::AddPage(p,pagePhys);

		MmuLock::Unlock();

		usedNew = 1;

		// map page...

		r = aMemory->MapPages(pageList);

		}

	// release page array entry...

	aMemory->iPages.AddPageEnd(aIndex,usedNew);

	// revert if error...

	if(r!=KErrNone)

		Free(aMemory,aIndex,aDemandPaged);

	return r;

	}

TInt DPageTableMemoryManager::Free(DMemoryObject* aMemory, TUint aIndex, TBool aDemandPaged)

	{

	TRACE2(("DPageTableMemoryManager::Free(0x%08x,0x%x,%d)",aMemory, aIndex, aDemandPaged));

	__NK_ASSERT_DEBUG(MemoryObjectLock::IsHeld(aMemory));

	// find page array entry...

	RPageArray::TIter pageList;

	TPhysAddr* p = aMemory->iPages.RemovePageStart(aIndex,pageList);

	if(!p)

		return KErrNoMemory;

	// unmap page...

	aMemory->UnmapPages(pageList,true);

	RamAllocLock::Lock();

	// remove page...

	MmuLock::Lock();

	TPhysAddr pagePhys = RPageArray::RemovePage(p);

	MmuLock::Unlock();

	TInt r;

	if(pagePhys==KPhysAddrInvalid)

		{

		// no page removed...

		r = 0;

		}

	else

		{

		// free the removed page...

		if(aDemandPaged)

			ThePager.PageInFreePages(&pagePhys,1);

		else

			TheMmu.FreeRam(&pagePhys, 1, EPageFixed);

		r = 1;

		}

	RamAllocLock::Unlock();

	// cleanup...

	aMemory->iPages.RemovePageEnd(aIndex,r);

	return r;

	}

TInt DPageTableMemoryManager::MovePage(	DMemoryObject* aMemory, SPageInfo* aOldPageInfo, 

										TPhysAddr& aNewPage, TUint aBlockZoneId, TBool aBlockRest)

		{

		// This could be a demand paged page table info which can be discarded 

		// but let the PageTableAllocator handle that.

		return ::PageTables.MovePage(aMemory, aOldPageInfo, aBlockZoneId, aBlockRest);

		}

//

// PageTableAllocator

//

void PageTableAllocator::Init2(DMutex* aLock)

	{

	TRACEB(("PageTableAllocator::Init2(0x%x)",aLock));

	iLock = aLock;

	__NK_ASSERT_DEBUG(iUnpagedAllocator.CheckFreeList());

	// scan for already allocated page tables

	// (assumes the first page table is used to map page tables)...

	SPageTableInfo* pti = (SPageTableInfo*)KPageTableInfoBase;

	TUint pages = 0;

	for(;;)

		{

		TPte pte = ((TPte*)KPageTableBase)[pages];

		if(pte==KPteUnallocatedEntry)

			break; // end (assumes no gaps in page table allocation) 

		// process free page tables in this page...

		TUint freeCount = 0;

		do

			{

			if(pti->IsUnused())

				{

				pti->PtClusterAlloc();

				iUnpagedAllocator.iFreeList.Add(&pti->FreeLink());

				++freeCount;

				}

#ifdef _DEBUG

			else

				__NK_ASSERT_DEBUG(pti->IsPtClusterAllocated());

#endif

			}

		while(!(++pti)->IsFirstInPage());

		iUnpagedAllocator.iFreeCount += freeCount;

		__NK_ASSERT_DEBUG(iUnpagedAllocator.CheckFreeList());

		TRACE2(("PT page 0x%08x has %d free tables",pti[-KPtClusterSize].PageTable(),freeCount));

		// count page, and move on to next one...

		++pages;

		__NK_ASSERT_DEBUG(pages<KChunkSize/KPageSize); // we've assumed less than one page table of page tables

		}

	// construct allocator for page table pages...

	iPtPageAllocator.Init2(pages);

	// initialise allocator page table infos...

	iPageTableGroupCounts[0] = pages;

	__NK_ASSERT_DEBUG(pages/KPageTableGroupSize==0); // we've assumed less than 1 page of page table infos

	// FOLLOWING CODE WILL USE THIS OBJECT TO ALLOCATE SOME PAGE TABLES,

	// SO ALLOCATOR MUST BE INITIALISED TO A FIT STATE BEFORE THIS POINT!

	// construct memory object for page tables...

	TMappingCreateFlags mapFlags = (TMappingCreateFlags)(EMappingCreateFixedVirtual|EMappingCreateReserveAllResources);

#if defined(__CPU_PAGE_TABLES_FULLY_CACHED)

	TMemoryAttributes memAttr = EMemoryAttributeStandard;

#else

	TMemoryAttributes memAttr = (TMemoryAttributes)(EMemoryAttributeNormalUncached|EMemoryAttributeDefaultShareable);

#endif

	TMemoryCreateFlags createFlags = (TMemoryCreateFlags)(EMemoryCreateNoWipe|EMemoryCreateCustomManager);

	TInt r = MM::InitFixedKernelMemory(iPageTableMemory, KPageTableBase, KPageTableEnd, pages<<KPageShift, (TMemoryObjectType)(T_UintPtr)&ThePageTableMemoryManager, createFlags, memAttr, mapFlags);

	__NK_ASSERT_ALWAYS(r==KErrNone);

	MM::MemorySetLock(iPageTableMemory,aLock);

	// construct memory object for page table infos...

	memAttr = EMemoryAttributeStandard;

	TUint size = pages*KPtClusterSize*sizeof(SPageTableInfo);

	size = (size+KPageMask)&~KPageMask;

	r = MM::InitFixedKernelMemory(iPageTableInfoMemory, KPageTableInfoBase, KPageTableInfoEnd, size, (TMemoryObjectType)(T_UintPtr)&ThePageTableMemoryManager, createFlags, memAttr, mapFlags);

	__NK_ASSERT_ALWAYS(r==KErrNone);

	MM::MemorySetLock(iPageTableInfoMemory,aLock);

	// make sure we have enough reserve page tables...

	Lock();

	iUnpagedAllocator.Init2(this,KNumReservedPageTables,false);

	iPagedAllocator.Init2(this,0,true);

	Unlock();

	TRACEB(("PageTableAllocator::Init2 done"));

	}

void PageTableAllocator::Init2B()

	{

	TRACEB(("PageTableAllocator::Init2B()"));

	TInt r = iPageTableMemory->iPages.PreallocateMemory();

	__NK_ASSERT_ALWAYS(r==KErrNone);

	r = iPageTableInfoMemory->iPages.PreallocateMemory();

	__NK_ASSERT_ALWAYS(r==KErrNone);

	TRACEB(("PageTableAllocator::Init2B done"));

	}

void PageTableAllocator::TSubAllocator::Init2(PageTableAllocator* aAllocator, TUint aReserveCount, TBool aDemandPaged)

	{

	iReserveCount = aReserveCount;

	iDemandPaged = aDemandPaged;

	while(iFreeCount<aReserveCount)

		if(!aAllocator->AllocReserve(*this))

			{

			__NK_ASSERT_ALWAYS(0);

			}

	}

void PageTableAllocator::TPtPageAllocator::Init2(TUint aNumInitPages)

	{

	iLowerAllocator = TBitMapAllocator::New(KMaxPageTablePages,ETrue);

	__NK_ASSERT_ALWAYS(iLowerAllocator);

	iLowerAllocator->Alloc(0,aNumInitPages);

	iLowerWaterMark = aNumInitPages-1;

	iUpperAllocator = TBitMapAllocator::New(KMaxPageTablePages,ETrue);

	__NK_ASSERT_ALWAYS(iUpperAllocator);

	__ASSERT_COMPILE(KMaxPageTablePages > (TUint)KMinUnpinnedPagedPtPages);	// Unlikely to be untrue.

	iUpperWaterMark = KMaxPageTablePages - KMinUnpinnedPagedPtPages;

	iPinnedPageTablePages = 0;	// OK to clear this without MmuLock as only one thread running so far.

	}

static TUint32 RandomSeed = 33333;

TUint PageTableAllocator::TPtPageAllocator::RandomPagedPtPage()

	{

	__NK_ASSERT_DEBUG(PageTablesLockIsHeld());

	// Pick an allocated page at random, from iUpperWaterMark - KMaxPageTablePages.

	RandomSeed = RandomSeed * 69069 + 1; // next 'random' number

	TUint allocRange = KMaxPageTablePages - iUpperWaterMark - 1;

	TUint bit = (TUint64(RandomSeed) * TUint64(allocRange)) >> 32;

	// All page table pages should be allocated or we shouldn't be stealing one at random.

	__NK_ASSERT_DEBUG(iUpperAllocator->NotFree(bit, 1));

	return KMaxPageTablePages - 1 - bit;

	}

TInt PageTableAllocator::TPtPageAllocator::Alloc(TBool aDemandPaged)

	{

	__NK_ASSERT_DEBUG(PageTablesLockIsHeld());

	TUint pageIndex;

	if(aDemandPaged)

		{

		TInt bit = iUpperAllocator->Alloc();

		// There are always unpaged page tables so iUpperAllocator will always have 

		// at least one free bit.

		__NK_ASSERT_DEBUG(bit >= 0);

		pageIndex = KMaxPageTablePages - 1 - bit;

		if(pageIndex < iUpperWaterMark)

			{

			// new upper watermark...

			if((pageIndex & ~(KPageTableGroupSize - 1)) <= iLowerWaterMark)

				{

				// clashes with other bitmap allocator, so fail..

				iUpperAllocator->Free(bit);

				TRACE(("TPtPageAllocator::Alloc too low iUpperWaterMark %d ",iUpperWaterMark));

				return -1;

				}

			// Hold mmu lock so iUpperWaterMark isn't read by pinning before we've updated it.

			MmuLock::Lock();

			iUpperWaterMark = pageIndex;

			MmuLock::Unlock();

			TRACE(("TPtPageAllocator::Alloc new iUpperWaterMark=%d",pageIndex));

			}

		}

	else

		{

		TInt bit = iLowerAllocator->Alloc();

		if(bit < 0)

			return bit;

		pageIndex = bit;

		if(pageIndex > iLowerWaterMark)

			{// iLowerAllocator->Alloc() should only pick the next bit after iLowerWaterMark.

			__NK_ASSERT_DEBUG(pageIndex == iLowerWaterMark + 1);

			MmuLock::Lock();

			// new lower watermark...

			if(	pageIndex >= (iUpperWaterMark & ~(KPageTableGroupSize - 1)) ||

				AtPinnedPagedPtsLimit(iUpperWaterMark, pageIndex, iPinnedPageTablePages))

				{

				// clashes with other bitmap allocator or it would reduce the amount 

				// of available unpinned paged page tables too far, so fail..

				MmuLock::Unlock();

				iLowerAllocator->Free(bit);

				TRACE(("TPtPageAllocator::Alloc iLowerWaterMark=%d",iLowerWaterMark));

				return -1;

				}

			iLowerWaterMark = pageIndex;

			MmuLock::Unlock();

			TRACE(("TPtPageAllocator::Alloc new iLowerWaterMark=%d", iLowerWaterMark));

			}

		}

	return pageIndex;

	}

void PageTableAllocator::TPtPageAllocator::Free(TUint aPageIndex, TBool aDemandPaged)

	{

	__NK_ASSERT_DEBUG(PageTablesLockIsHeld());

	if(aDemandPaged)

		iUpperAllocator->Free(KMaxPageTablePages-1-aPageIndex);

	else

		iLowerAllocator->Free(aPageIndex);

	}

void PageTableAllocator::Lock()

	{

	Kern::MutexWait(*iLock);

	}

void PageTableAllocator::Unlock()

	{

	Kern::MutexSignal(*iLock);

	}

TBool PageTableAllocator::LockIsHeld()

	{

	return iLock->iCleanup.iThread == &Kern::CurrentThread();

	}

TBool PageTableAllocator::AllocReserve(TSubAllocator& aSubAllocator)

	{

	__NK_ASSERT_DEBUG(LockIsHeld());

	TBool demandPaged = aSubAllocator.iDemandPaged;

	// allocate page...

	TInt ptPageIndex = iPtPageAllocator.Alloc(demandPaged);

	if (ptPageIndex < 0) 

		{

		if (demandPaged)

			{

			TInt r;

			do

				{

				// Can't fail to find a demand paged page table, otherwise a page fault 

				// could fail with KErrNoMemory.  Therefore, keep attempting to steal a 

				// demand paged page table page until successful.

				TUint index = iPtPageAllocator.RandomPagedPtPage();

				MmuLock::Lock();

				TLinAddr pageTableLin = KPageTableBase + (index << (KPtClusterShift + KPageTableShift));

				TPhysAddr ptPhysAddr = Mmu::LinearToPhysical(pageTableLin);

				// Page tables must be allocated otherwise we shouldn't be stealing the page.

				__NK_ASSERT_DEBUG(ptPhysAddr != KPhysAddrInvalid);

				SPageInfo* ptSPageInfo = SPageInfo::FromPhysAddr(ptPhysAddr);

				r = StealPage(ptSPageInfo);

				MmuLock::Unlock();

				}