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

 #include "mslaballoc.h"

 static RStaticSlabAllocator<RPageArray::TSegment,KPageArraySegmentBase,KPageArraySegmentEnd> PageSegmentAllocator;

 //

 // RPageArray::TSegment

 //

 RPageArray::TSegment* RPageArray::TSegment::New()

 	{

 	__NK_ASSERT_DEBUG(!MmuLock::IsHeld());

 	// allocate segment...

 	TSegment* s = PageSegmentAllocator.Alloc();

 	if(!s)

 		return s;

 	// initialise segment...

 	s->iCounts = 1; // lock count = 1, alloc count = 0

 	TPhysAddr* p = s->iPages;

 	TPhysAddr* pEnd = p+KPageArraySegmentSize;

 	TPhysAddr nullPage = EEmptyEntry;

 	do *p++ = nullPage;

 	while(p<pEnd);

 	return s;

 	}

 RPageArray::TSegment* RPageArray::TSegment::Delete(TSegment* aSegment)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aSegment->iCounts==0);

 #ifdef _DEBUG

 	TPhysAddr* p = aSegment->iPages;

 	TPhysAddr* pEnd = p+KPageArraySegmentSize;

 	do

 		{

 		TPhysAddr a = *p++;

 		if(IsPresent(a))

 			{

 			Kern::Printf("TSegment Delete with allocated pages! [%d]=0x%08x",p-aSegment->iPages-1,a);

 			__NK_ASSERT_DEBUG(0);

 			}

 		}

 	while(p<pEnd);

 #endif

 	PageSegmentAllocator.Free(aSegment);

 	return 0;

 	}

 FORCE_INLINE void RPageArray::TSegment::Lock(TUint aCount)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__e32_atomic_add_ord32(&iCounts, (TUint32)aCount);

 	__NK_ASSERT_DEBUG((iCounts&KPageArraySegmentLockCountMask));

 	}

 /**

 @return True if segment still exists, false if segment was deleted.

 */

 TBool RPageArray::TSegment::Unlock(TSegment*& aSegment, TUint aCount)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	TSegment* s = aSegment;

 	__NK_ASSERT_DEBUG(s);

 	TUint oldCounts = (TUint)__e32_atomic_add_ord32(&s->iCounts, (TUint32)-(TInt)aCount);

 	__NK_ASSERT_DEBUG(oldCounts&KPageArraySegmentLockCountMask); // alloc count must have been non-zero before decrementing

 #ifdef _DEBUG

 	if((oldCounts&KPageArraySegmentLockCountMask)==aCount)

 		{

 		// check alloc count is consistent...

 		TUint allocCount = s->iCounts>>KPageArraySegmentAllocCountShift;

 		__NK_ASSERT_DEBUG(allocCount<=KPageArraySegmentSize);

 		TUint realAllocCount = 0;

 		TPhysAddr* p = s->iPages;

 		TPhysAddr* pEnd = p+KPageArraySegmentSize;

 		do

 			{

 			if(IsPresent(*p++))

 				++realAllocCount;

 			}

 		while(p<pEnd);

 		if(realAllocCount!=allocCount)

 			{

 			Kern::Printf("TSegment::Unlock alloc count missmatch %u!=%u",realAllocCount,allocCount);

 			__NK_ASSERT_DEBUG(0);

 			}

 		}

 #endif

 	if(oldCounts>1)

 		return oldCounts; // return 'true' to indicate segment still exists

 	// delete segment...

 	aSegment = 0;

 	return (TBool)Delete(s); // returns 'false'

 	}

 FORCE_INLINE void RPageArray::TSegment::AdjustAllocCount(TInt aDelta)

 	{

 	__NK_ASSERT_DEBUG((iCounts&KPageArraySegmentLockCountMask));

 	__e32_atomic_add_ord32(&iCounts, TUint32(aDelta)<<KPageArraySegmentAllocCountShift);

 	}

 #ifdef _DEBUG

 void RPageArray::TSegment::Dump()

 	{

 	TUint allocCount = iCounts>>KPageArraySegmentAllocCountShift;

 	TUint lockCount = iCounts&KPageArraySegmentLockCountMask;

 	Kern::Printf("RPageArray::TSegment[0x%08x]::Dump() allocCount=%d lockCount=%d",this,allocCount,lockCount);

 	for(TUint i=0; i<KPageArraySegmentSize; i+=4)

 		Kern::Printf("  %08x %08x %08x %08x",iPages[i+0],iPages[i+1],iPages[i+2],iPages[i+3]);

 	}

 #endif

 //

 // RPageArray::TIter

 //

 TUint RPageArray::TIter::Pages(TPhysAddr*& aStart, TUint aMaxCount)

 	{

 	// MmuLock *may* be needed, depends if segments have been locked

 	TUint index = iIndex;

 	TUint size = iEndIndex-index;

 	if(!size)

 		return 0;

 	TUint offset = index&KPageArraySegmentMask;

 	aStart = iSegments[index>>KPageArraySegmentShift]->iPages+offset;

 	TUint n = KPageArraySegmentSize-offset;

 	if(n>aMaxCount)

 		n = aMaxCount;

 	if(n>size)

 		n = size;

 	return n;

 	}

 TUint RPageArray::TIter::AddFind(TIter& aPageList)

 	{

 	TRACE2(("RPageArray::TIter::AddFind range 0x%x..0x%x",iIndex,iEndIndex));

 	TUint index = iIndex;

 	TUint endIndex = iEndIndex;

 	if(index==endIndex)

 		{

 nothing_found:

 		aPageList.iIndex = endIndex;

 		aPageList.iEndIndex = endIndex;

 		TRACE2(("RPageArray::TIter::AddFind returns 0x%x+0x%x",iEndIndex,0));

 		return 0;

 		}

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	TPhysAddr* p;

 	TUint limit;

 	MmuLock::Lock();

 	// scan for empty entries...

 	do

 		{

 		// get segment...

 		p = (*pS++)->iPages+(index&KPageArraySegmentMask);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		// scan segment...

 		do

 			{

 			TPhysAddr page = *p;

 			if(!IsPresent(page))

 				goto find_start;

 #if _DEBUG

 			if(State(page)!=ECommitted)

 				{

 				Kern::Printf("RPageArray::TIter::AddFind found unexpected page: %x",page);

 				__NK_ASSERT_DEBUG(0);

 				// *p = (page&~(EStateMask|EVetoed))|ECommitted; // mark page as allocated again

 				}

 #endif

 			++p;

 			}

 		while(++index<limit);

 		MmuLock::Flash();

 		}

 	while(index<endIndex);

 	MmuLock::Unlock();

 	goto nothing_found;

 find_start:

 	TUint startIndex = index;

 	// scan for end of empty region...

 	for(;;)

 		{

 		// scan segment...

 		do

 			{

 			if(IsPresent(*p++))

 				goto find_end;

 			}

 		while(++index<limit);

 		// check for end...

 		if(index>=endIndex)

 			break;

 		MmuLock::Flash();

 		// get next segment...

 		p = (*pS++)->iPages;

 		TUint nextIndex = index+KPageArraySegmentSize;

 		limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		}

 find_end:

 	MmuLock::Unlock();

 	aPageList.iSegments = iSegments;

 	aPageList.iIndex = startIndex;

 	aPageList.iEndIndex = index;

 	iIndex = index;

 	TUint n = index-startIndex;

 	TRACE2(("RPageArray::TIter::AddFind returns 0x%x+0x%x",startIndex,n));

 	return n;

 	}

 void RPageArray::TIter::Add(TUint aCount, TPhysAddr* aPages)

 	{

 	// MmuLock NOT required because...

 	// 1. AddStart has ensured all segments are allocated and locked (so they can't be deleted)

 	// 2. AddFind returns an unallocated region. This can only be changed by Adding pages

 	//    and we only allow one thread to do this at a time (i.e. the thread calling this function.)

 	TRACE2(("RPageArray::TIter::Add 0x%x+0x%x",iIndex,aCount));

 	__NK_ASSERT_DEBUG(aCount);

 	TUint index = iIndex;

 	TUint endIndex = index+aCount;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	do

 		{

 		// get segment...

 		TSegment* s = *pS++;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		// add pages to segment...

 		s->AdjustAllocCount(limit-index);

 		do

 			{

 			__NK_ASSERT_DEBUG((*aPages&KPageMask)==0);

 			__NK_ASSERT_DEBUG(!IsPresent(*p)); // AddFind only found not-present entries

 			*p++ = *aPages++|ECommitted;

 			}

 		while(++index<limit);

 		}

 	while(index<endIndex);

 	iIndex = index;

 	}

 void RPageArray::TIter::AddContiguous(TUint aCount, TPhysAddr aPhysAddr)

 	{

 	// MmuLock NOT required because...

 	// 1. AddStart has ensured all segments are allocated and locked (so they can't be deleted)

 	// 2. AddFind returns an unallocated region. This can only be changed by Adding pages

 	//    and we only allow one thread to do this at a time (i.e. the thread calling this function.)

 	TRACE2(("RPageArray::TIter::AddContiguous 0x%x+0x%x",iIndex,aCount));

 	__NK_ASSERT_DEBUG(aCount);

 	__NK_ASSERT_DEBUG((aPhysAddr&KPageMask)==0);

 	TUint index = iIndex;

 	TUint endIndex = index+aCount;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	do

 		{

 		// get segment...

 		TSegment* s = *pS++;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		// add pages to segment...

 		s->AdjustAllocCount(limit-index);

 		do

 			{

 			__NK_ASSERT_DEBUG(!IsPresent(*p)); // AddFind only found not-present entries

 			*p++ = aPhysAddr|ECommitted;

 			aPhysAddr += KPageSize;

 			}

 		while(++index<limit);

 		}

 	while(index<endIndex);

 	iIndex = index;

 	}

 void RPageArray::TIter::Added(TUint aCount, TUint aChanged)

 	{

 	__NK_ASSERT_DEBUG(aCount);

 	__NK_ASSERT_DEBUG(aChanged<=aCount);

 	TUint index = iIndex;

 	__NK_ASSERT_DEBUG((index>>KPageArraySegmentShift)==((index+aCount-1)>>KPageArraySegmentShift));

 	TSegment* s = iSegments[index>>KPageArraySegmentShift];

 	__NK_ASSERT_DEBUG(s);

 	__NK_ASSERT_DEBUG(s->iCounts&KPageArraySegmentLockCountMask);

 	s->AdjustAllocCount(aChanged);

 	Skip(aCount);

 	}

 TUint RPageArray::TIter::Find(TIter& aPageList)

 	{

 	TRACE2(("RPageArray::TIter::Find range 0x%x..0x%x",iIndex,iEndIndex));

 	MmuLock::Lock();

 	TUint index = iIndex;

 	TUint endIndex = iEndIndex;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 	// search for first page...

 	while(index<endIndex)

 		{

 		TSegment* s = *pS;

 		if(!s)

 			index = nextIndex;

 		else

 			{

 			// search segment...

 			TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 			TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 			do

 				{

 				if(RPageArray::IsPresent(*p++))

 					goto start_done;

 				}

 			while(++index<limit);

 			}

 		// next segment...

 		MmuLock::Flash();

 		++pS;

 		nextIndex = index+KPageArraySegmentSize;

 		}

 start_done:

 	// we can't flash or release the MmuLock until we've Locked the segment we found!

 	iIndex = index;

 	// search for range of allocated pages...

 	while(index<endIndex)

 		{

 		// check first entry...

 		TSegment* s = *pS;

 		if(!s)

 			break;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		if(!RPageArray::IsPresent(*p++))

 			break;

 		// segment has pages, lock it...

 		s->Lock();

 		// scan rest of entries...

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		while(++index<limit)

 			if(!RPageArray::IsPresent(*p++))

 				goto done;

 		// next segment...

 		MmuLock::Flash();

 		++pS;

 		}

 done:

 	MmuLock::Unlock();

 	aPageList.iSegments = iSegments;

 	aPageList.iIndex = iIndex;

 	aPageList.iEndIndex = index;

 	TInt n = index-iIndex;

 	TRACE2(("RPageArray::TIter::Find returns 0x%x+0x%x",iIndex,n));

 	return n;

 	}

 void RPageArray::TIter::FindRelease(TUint aCount)

 	{

 	TUint index = iIndex;

 	Skip(aCount);

 	RPageArray::Release(iSegments,index,aCount);

 	}

 TUint RPageArray::TIter::RemoveFind(TIter& aPageList)

 	{

 	TRACE2(("RPageArray::TIter::RemoveFind range 0x%x..0x%x",iIndex,iEndIndex));

 	MmuLock::Lock();

 	TUint index = iIndex;

 	TUint endIndex = iEndIndex;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 	// search for first page...

 	while(index<endIndex)

 		{

 		TSegment* s = *pS;

 		if(!s)

 			index = nextIndex;

 		else

 			{

 			// search segment...

 			TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 			TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 			do

 				{

 				if(State(*p++)>=EDecommitting)

 					goto start_done;

 				}

 			while(++index<limit);

 			}

 		// next segment...

 		MmuLock::Flash();

 		++pS;

 		nextIndex = index+KPageArraySegmentSize;

 		}

 start_done:

 	// we can't flash or release the MmuLock until we've Locked the segment we found!

 	iIndex = index;

 	// search for range of allocated pages, marking them EDecommitting...

 	while(index<endIndex)

 		{

 		// check first entry...

 		TSegment* s = *pS;

 		if(!s)

 			break;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		TPhysAddr page = *p++;

 		if(State(page)<EDecommitting)

 			break;

 		p[-1] = (page&~EStateMask)|EDecommitting;

 		// segment has pages, lock it...

 		s->Lock();

 		// scan rest of entries...

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		while(++index<limit)

 			{

 			TPhysAddr page = *p++;

 			if(State(page)<EDecommitting)

 				goto done;

 			p[-1] = (page&~EStateMask)|EDecommitting;

 			}

 		// next segment...

 		MmuLock::Flash();

 		++pS;

 		}

 done:

 	MmuLock::Unlock();

 	aPageList.iSegments = iSegments;

 	aPageList.iIndex = iIndex;

 	aPageList.iEndIndex = index;

 	TInt n = index-iIndex;

 	TRACE2(("RPageArray::TIter::RemoveFind returns 0x%x+0x%x",iIndex,n));

 	return n;

 	}

 TUint RPageArray::TIter::Remove(TUint aMaxCount, TPhysAddr* aPages)

 	{

 	TRACE2(("RPageArray::TIter::Remove 0x%x..0x%x max=0x%x",iIndex,iEndIndex,aMaxCount));

 	__NK_ASSERT_DEBUG(aMaxCount);

 	TUint count = 0;

 	TUint index = iIndex;

 	TUint endIndex = iEndIndex;

 	if(index==endIndex)

 		return 0;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	MmuLock::Lock();

 	do

 		{

 		// get segment...

 		TSegment* s = *pS++;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		// remove pages from segment...

 		do

 			{

 			TPhysAddr page = *p++;

 			__NK_ASSERT_DEBUG(State(page)!=EStealing); // can't be stealing as that only happens with the RamAllocLock held, which we should already hold if freeing demand paged pages

 			if(State(page)==EDecommitting || State(page)==EDecommitted)

 				{

 				// remove a page...

 				if(page&EUnmapVetoed)

 					{

 					p[-1] = (page&~(EUnmapVetoed|EStateMask))|EDecommitted; // change to EDecommitted state

 					}

 				else

 					{

 					p[-1] = EEmptyEntry;

 					s->AdjustAllocCount(-1);

 					TPhysAddr pagePhys = page&~KPageMask;

 					aPages[count++] = pagePhys;

 					TRACE2(("RPageArray::TIter::Remove index=0x%x returns 0x%08x",index,pagePhys));

 					if(count>=aMaxCount)

 						{

 						++index;

 						goto done;

 						}

 					}

 				// check not removing managed pages without the RamAllocLock...

 				__NK_ASSERT_DEBUG(RamAllocLock::IsHeld()

 					|| SPageInfo::FromPhysAddr(page)->Type()!=SPageInfo::EManaged);

 				}

 			}

 		while(++index<limit);

 		MmuLock::Flash();

 		}

 	while(index<endIndex);

 done:

 	MmuLock::Unlock();

 	iIndex = index;

 	return count;

 	}

 void RPageArray::TIter::VetoUnmap()

 	{

 	TUint index = iIndex;

 	TUint endIndex = iEndIndex;

 	if(index==endIndex)

 		return;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	MmuLock::Lock();

 	do

 		{

 		// get segment...

 		TSegment* s = *pS++;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		// veto pages in segment...

 		do

 			{

 			TPhysAddr page = *p++;

 			TRACE2(("RPageArray::TIter::Veto() yes/no=%d page=0x%08x",IsPresent(page) && TargetStateIsDecommitted(page),page));

 			if(IsPresent(page) && TargetStateIsDecommitted(page))

 				p[-1] = page|EUnmapVetoed;

 			}

 		while(++index<limit);

 		MmuLock::Flash();

 		}

 	while(index<endIndex);

 	MmuLock::Unlock();

 	}

 void RPageArray::TIter::VetoRestrict(TBool aPageMoving)

 	{

 	TUint index = iIndex;

 	TUint endIndex = iEndIndex;

 	if(index==endIndex)

 		return;

 	RPageArray::TState operation = 	aPageMoving ? RPageArray::EMoving : RPageArray::ERestrictingNA;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	MmuLock::Lock();

 	do

 		{

 		// get segment...

 		TSegment* s = *pS++;

 		TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		// veto pages in segment...

 		do

 			{

 			TPhysAddr page = *p++;

 			TRACE2(("RPageArray::TIter::VetoRestrict() yes/no=%d page=0x%08x",State(page)==operation,page));

 			if(State(page)==operation)

 				{

 				// to veto a 'restrict page' operation, we put the page back into the committed...

 				p[-1] = (page&~EStateMask)|ECommitted;

 				}

 			}

 		while(++index<limit);

 		MmuLock::Flash();

 		}

 	while(index<endIndex);

 	MmuLock::Unlock();

 	}

 FORCE_INLINE void RPageArray::TIter::Set(RPageArray::TSegment** aSegments, TUint aIndex, TUint aEndIndex)

 	{

 	iSegments = aSegments;

 	iIndex = aIndex;

 	iEndIndex = aEndIndex;

 	}

 //

 // RPageArray

 //

 void RPageArray::Init2A()

 	{

 	TInt r = PageSegmentAllocator.Construct();

 	__NK_ASSERT_ALWAYS(r==KErrNone);

 	}

 void RPageArray::Init2B(DMutex* aLock)

 	{

 	// construct memory object for slabs...

 	DMemoryObject* memory;

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

 	TMemoryAttributes memAttr = EMemoryAttributeStandard;

 	TInt r = MM::InitFixedKernelMemory(memory, KPageArraySegmentBase, KPageArraySegmentEnd, KPageSize, EMemoryObjectUnpaged, EMemoryCreateNoWipe, memAttr, mapFlags);

 	__NK_ASSERT_ALWAYS(r==KErrNone);

 	MM::MemorySetLock(memory,aLock);

 	PageSegmentAllocator.SetMemory(memory,1);

 	}

 RPageArray::RPageArray()

 	{

 	__NK_ASSERT_DEBUG(!iSegments);

 	}

 TInt RPageArray::Construct(TUint aMaxPages, TBool aPreallocateMemory)

 	{

 	iNumSegments = (aMaxPages+KPageArraySegmentMask)>>KPageArraySegmentShift;

 	iSegments = (TSegment**)Kern::AllocZ(iNumSegments*sizeof(TSegment*));

 	if(!iSegments)

 		return KErrNoMemory;

 	if(!aPreallocateMemory)

 		return KErrNone;

 	return PreallocateMemory();

 	}

 TInt RPageArray::PreallocateMemory()

 	{

 	MmuLock::Lock();

 	__NK_ASSERT_DEBUG(!iPreallocatedMemory);

 	iPreallocatedMemory = true;

 	TSegment** pS = iSegments;

 	TSegment** pGEnd = pS+iNumSegments;

 	do

 		{

 		if(!GetOrAllocateSegment(pS,1))

 			{

 			iNumSegments = pS-iSegments; // truncate to amount successfully allocated

 			MmuLock::Unlock();

 			return KErrNoMemory;

 			}

 		}

 	while(++pS<pGEnd);

 	MmuLock::Unlock();

 	return KErrNone;

 	}

 RPageArray::~RPageArray()

 	{

 	TSegment** pS = iSegments;

 	if(pS)

 		{

 		TSegment** pGEnd = pS+iNumSegments;

 		if(!iPreallocatedMemory)

 			{

 			// check all segments have already been deleted...

 			while(pS<pGEnd)

 				{

 #ifdef _DEBUG

 				if(*pS)

 					(*pS)->Dump();

 #endif

 				__NK_ASSERT_DEBUG(!*pS);

 				++pS;

 				}

 			}

 		else

 			{

 			MmuLock::Lock();

 			while(pS<pGEnd)

 				{

 				__NK_ASSERT_DEBUG(*pS);

 				TSegment::Unlock(*pS);

 #ifdef _DEBUG

 				if(*pS)

 					(*pS)->Dump();

 #endif

 				__NK_ASSERT_DEBUG(!*pS);

 				TRACE2(("RPageArray::~RPageArray delete segment=%d",pS-iSegments));

 				++pS;

 				if(pS<pGEnd)

 					MmuLock::Flash();

 				}

 			MmuLock::Unlock();

 			}

 		Kern::Free(iSegments);

 		}

 	}

 RPageArray::TSegment* RPageArray::GetOrAllocateSegment(TSegment** aSegmentEntry, TUint aLockCount)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aLockCount);

 	for(;;)

 		{

 		TSegment* s = *aSegmentEntry;

 		if(s)

 			{

 			s->Lock(aLockCount);

 			return s;

 			}

 		// no segment, so allocate one...

 		MmuLock::Unlock();

 		s = TSegment::New();

 		MmuLock::Lock();

 		if(!s)

 			return s;

 		// if someone else allocated one...

 		if(*aSegmentEntry)

 			{

 			// free the one we created...

 			TSegment::Unlock(s); 

 			//and retry...

 			continue;

 			}

 		// use new segment...

 		TRACE2(("RPageArray::GetOrAllocateSegment new segment=%d",aSegmentEntry-iSegments));

 		*aSegmentEntry = s;

 		if(--aLockCount)

 			s->Lock(aLockCount);

 		return s;

 		}

 	}

 TInt RPageArray::Alloc(TUint aIndex, TUint aCount)

 	{

 	TRACE2(("RPageArray::Alloc(0x%x,0x%x)",aIndex,aCount));

 	__NK_ASSERT_DEBUG(aIndex+aCount<=iNumSegments*KPageArraySegmentSize);

 	__NK_ASSERT_DEBUG(aIndex+aCount>=aIndex);

 	MmuLock::Lock();

 	TUint index = aIndex;

 	TUint endIndex = aIndex+aCount;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	while(index<endIndex)

 		{

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		TUint lockCount = limit-index;

 		index = limit;

 		TSegment* s = GetOrAllocateSegment(pS++,lockCount);

 		if(!s)

 			goto no_memory;

 		}

 	MmuLock::Unlock();

 	return KErrNone;

 no_memory:

 	MmuLock::Unlock();

 	// free what we actually alloced...

 	endIndex = index&~KPageArraySegmentMask;

 	Free(aIndex,endIndex-aIndex);

 	return KErrNoMemory;

 	}

 void RPageArray::Free(TUint aIndex, TUint aCount)

 	{

 	TRACE2(("RPageArray::Free(0x%x,0x%x)",aIndex,aCount));

 	__NK_ASSERT_DEBUG(aIndex+aCount<=iNumSegments*KPageArraySegmentSize);

 	__NK_ASSERT_DEBUG(aIndex+aCount>aIndex);

 	MmuLock::Lock();

 	TUint index = aIndex;

 	TUint endIndex = aIndex+aCount;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	while(index<endIndex)

 		{

 		__NK_ASSERT_DEBUG(*pS);

 		TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 		TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 		TSegment::Unlock(*pS,limit-index);

 		index = limit;

 		++pS;

 		}

 	MmuLock::Unlock();

 	}

 TInt RPageArray::AddStart(TUint aIndex, TUint aCount, TIter& aIter, TBool aAllowExisting)

 	{

 	TRACE2(("RPageArray::AddStart(0x%x,0x%x,?,%d)",aIndex,aCount,aAllowExisting));

 	__NK_ASSERT_DEBUG(aIndex+aCount<=iNumSegments*KPageArraySegmentSize);

 	__NK_ASSERT_DEBUG(aIndex+aCount>aIndex);

 	aIter.Set(iSegments,aIndex,aIndex+aCount);

 	MmuLock::Lock();

 	TInt r;

 	TUint index = aIndex;

 	TUint endIndex = aIndex+aCount;

 	TSegment** pS = iSegments+(index>>KPageArraySegmentShift);

 	while(index<endIndex)

 		{

 		TSegment* s = *pS;

 		if(!s)

 			{

 			// no segment, so allocate one...

 			MmuLock::Unlock();

 			s = TSegment::New();

 			MmuLock::Lock();

 			if(!s)

 				goto no_memory;

 			// if someone else allocated one

 			if(*pS)

 				{

 				// free the one we created...

 				TSegment::Unlock(s); 

 				//and retry...

 				continue;

 				}

 			// use new segment...

 			TRACE2(("RPageArray::AddStart new segment=%d",pS-iSegments));

 			*pS = s;

 			// move on...

 			index = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 			}

 		else

 			{

 			TUint nextIndex = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 			if(aAllowExisting)

 				{

 				// just move on to next segment...

 				index = (index+KPageArraySegmentSize)&~KPageArraySegmentMask;

 				}

 			else

 				{

 				// check page entries are empty...

 				TPhysAddr* p = s->iPages+(index&KPageArraySegmentMask);

 				TUint limit = (nextIndex<endIndex) ? nextIndex : endIndex;

 				do

 					{

 					if(IsPresent(*p++))

 						goto already_exists;

 					}

 				while(++index<limit);

 				}

 			// lock segment so that it doesn't go away...

 			s->Lock();

 			if(index<endIndex)

 				MmuLock::Flash();

 			}

 		++pS;

 		}

 	// done...

 	MmuLock::Unlock();

 	return KErrNone;

 no_memory:

 	r = KErrNoMemory;

 	goto error;

 already_exists:

 	r = KErrAlreadyExists;

 error:

 	MmuLock::Unlock();

 	// unlock any segments that we locked...

 	endIndex = index&~KPageArraySegmentMask;

 	if(endIndex>aIndex)

 		Release(iSegments,aIndex,endIndex-aIndex);

 	// return error...

 	return r;

 	}

 void RPageArray::AddEnd(TUint aIndex, TUint aCount)

 	{

 	Release(iSegments,aIndex,aCount);

 	}

 void RPageArray::FindStart(TUint aIndex, TUint aCount, TIter& aIter)

 	{

 	TRACE2(("RPageArray::FindStart(0x%x,0x%x,?)",aIndex,aCount));

 	__NK_ASSERT_DEBUG(aIndex+aCount<=iNumSegments*KPageArraySegmentSize);

 	__NK_ASSERT_DEBUG(aIndex+aCount>aIndex);

 	aIter.Set(iSegments,aIndex,aIndex+aCount);

 	}

 void RPageArray::Release(TSegment** aSegments, TUint aIndex, TUint aCount)

 	{

 	__NK_ASSERT_DEBUG(aIndex+aCount>aIndex);

 	MmuLock::Lock();

 	TSegment** pS = aSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment** pGLast = aSegments+((aIndex+aCount-1)>>KPageArraySegmentShift);

 	__NK_ASSERT_DEBUG(pS<=pGLast);

 	TUint flash = 0;

 	do

 		{

 		MmuLock::Flash(flash,KMaxPagesInOneGo);

 		if(TSegment::Unlock(*pS)==0)

 			{

 			TRACE2(("RPageArray::Release delete segment=%d",pS-aSegments));

 			}

 		++pS;

 		}

 	while(pS<=pGLast);

 	MmuLock::Unlock();

 	}

 TPhysAddr* RPageArray::AddPageStart(TUint aIndex, TIter& aPageList)

 	{

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	MmuLock::Lock();

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = GetOrAllocateSegment(pS,1);

 	MmuLock::Unlock();

 	if(!s)

 		return 0;

 	aPageList.Set(iSegments,aIndex,aIndex+1);

 	return s->iPages+(aIndex&KPageArraySegmentMask);

 	}

 TPhysAddr* RPageArray::RemovePageStart(TUint aIndex, TIter& aPageList)

 	{

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	MmuLock::Lock();

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	if(!s)

 		{

 		MmuLock::Unlock();

 		return 0;

 		}

 	TPhysAddr* p = s->iPages+(aIndex&KPageArraySegmentMask);

 	TPhysAddr page = *p;

 	if(State(page)<EDecommitting)

 		{

 		MmuLock::Unlock();

 		return 0;

 		}

 	*p = (page&~EStateMask)|EDecommitting;

 	s->Lock();

 	MmuLock::Unlock();

 	aPageList.Set(iSegments,aIndex,aIndex+1);

 	return p;

 	}

 TPhysAddr RPageArray::RemovePage(TPhysAddr* aPageEntry)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	TPhysAddr page = *aPageEntry;

 	__NK_ASSERT_DEBUG(State(page)!=EStealing); // can't be stealing as that only happens with the RamAllocLock held, which we should already hold if freeing demand paged pages

 	if(State(page)==EDecommitting || State(page)==EDecommitted)

 		{

 		// remove a page...

 		if(page&EUnmapVetoed)

 			{

 			*aPageEntry = (page&~(EUnmapVetoed|EStateMask))|EDecommitted; // change to EDecommitted state

 			}

 		else

 			{

 			*aPageEntry = EEmptyEntry;

 			return page&~KPageMask;

 			}

 		// check not removing managed pages without the RamAllocLock...

 		__NK_ASSERT_DEBUG(RamAllocLock::IsHeld()

 			|| SPageInfo::FromPhysAddr(page)->Type()!=SPageInfo::EManaged);

 		}

 	return KPhysAddrInvalid;

 	}

 TPhysAddr* RPageArray::RestrictPageNAStart(TUint aIndex, TIter& aPageList)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	if(!s)

 		return 0;

 	TPhysAddr* p = s->iPages+(aIndex&KPageArraySegmentMask);

 	TPhysAddr page = *p;

 	if(State(page) < RPageArray::ERestrictingNA)

 		return 0;

 	*p = (page&~EStateMask) | RPageArray::ERestrictingNA;

 	s->Lock();

 	aPageList.Set(iSegments,aIndex,aIndex+1);

 	return p;

 	}

 TPhysAddr* RPageArray::StealPageStart(TUint aIndex, TIter& aPageList)

 	{

 	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	__NK_ASSERT_DEBUG(s); // we only steal pages in the live list and these can not go away yet because we hold the RamAllocLock

 	TPhysAddr* p = s->iPages+(aIndex&KPageArraySegmentMask);

 	TPhysAddr page = *p;

 	if(State(page)>EStealing)

 		*p = (page&~EStateMask)|EStealing;

 	s->Lock();

 	aPageList.Set(iSegments,aIndex,aIndex+1);

 	return p;

 	}

 TPhysAddr* RPageArray::MovePageStart(TUint aIndex, TIter& aPageList)

 	{

 	__NK_ASSERT_DEBUG(RamAllocLock::IsHeld());

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex <= iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	// The segment should always exist for a page that is being moved.

 	__NK_ASSERT_DEBUG(s);

 	TPhysAddr* p = s->iPages+(aIndex&KPageArraySegmentMask);

 	TPhysAddr page = *p;

 	if(State(page) <= RPageArray::EMoving)

 		return NULL;

 	*p = (page & ~EStateMask) | EMoving;

 	aPageList.Set(iSegments, aIndex, aIndex+1);

 	return p;

 	}

 void RPageArray::ReleasePage(TUint aIndex, TInt aDelta)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	__NK_ASSERT_DEBUG(s); // must exist because FindPageStart/AddPageStart locked it

 	__NK_ASSERT_DEBUG(aDelta>=-1 && aDelta<=1);

 	if(aDelta)

 		s->AdjustAllocCount(aDelta);

 	if(TSegment::Unlock(*pS)==0)

 		{

 		TRACE2(("RPageArray::ReleasePage delete segment=%d",pS-iSegments));

 		}

 	}

 TPhysAddr RPageArray::Page(TUint aIndex)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	if(!s)

 		return ENotPresent;

 	return s->iPages[aIndex&KPageArraySegmentMask];

 	}

 TPhysAddr* RPageArray::PageEntry(TUint aIndex)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	if(!s)

 		return NULL;

 	return s->iPages + (aIndex & KPageArraySegmentMask);

 	}

 TUint RPageArray::PagingManagerData(TUint aIndex)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	__NK_ASSERT_DEBUG(s);

 	TPhysAddr* p = &s->iPages[aIndex&KPageArraySegmentMask];

 	TPhysAddr entry = *p;

 	if(IsPresent(entry))

 		{

 #ifdef _DEBUG

 		SPageInfo* pi = SPageInfo::SafeFromPhysAddr(entry&~KPageMask);

 		if(!pi)

 			Kern::Printf("RPageArray::PagingManagerData bad entry 0x%08x",entry);

 		__NK_ASSERT_DEBUG(pi);

 #else

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

 #endif

 		entry = pi->PagingManagerData();

 		}

 	__NK_ASSERT_DEBUG((entry&(EFlagsMask|EStateMask))==ENotPresent);

 	return entry>>(EFlagsShift+EStateShift);

 	}

 void RPageArray::SetPagingManagerData(TUint aIndex, TUint aValue)

 	{

 	aValue = (aValue<<(EFlagsShift+EStateShift))|ENotPresent;

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	__NK_ASSERT_DEBUG(s);

 	TPhysAddr* p = &s->iPages[aIndex&KPageArraySegmentMask];

 	TPhysAddr entry = *p;

 	if(!IsPresent(entry))

 		*p = aValue;

 	else

 		{

 #ifdef _DEBUG

 		SPageInfo* pi = SPageInfo::SafeFromPhysAddr(entry&~KPageMask);

 		if(!pi)

 			Kern::Printf("RPageArray::SetPagingManagerData bad entry 0x%08x",entry);

 		__NK_ASSERT_DEBUG(pi);

 #else

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

 #endif

 		pi->SetPagingManagerData(aValue);

 		}

 	}

 TPhysAddr RPageArray::PhysAddr(TUint aIndex)

 	{

 	__NK_ASSERT_DEBUG(MmuLock::IsHeld());

 	__NK_ASSERT_DEBUG(aIndex<=iNumSegments*KPageArraySegmentSize);

 	TSegment** pS = iSegments+(aIndex>>KPageArraySegmentShift);

 	TSegment* s = *pS;

 	if(s)

 		{

 		TPhysAddr page = s->iPages[aIndex&KPageArraySegmentMask];

 		if(IsPresent(page))

 			{

 			return page&~KPageMask;

 			}

 		}

 	return KPhysAddrInvalid;

 	}

 TInt RPageArray::PhysAddr(TUint aIndex, TUint aCount, TPhysAddr& aPhysicalAddress, TPhysAddr* aPhysicalPageList)

 	{

 	__NK_ASSERT_DEBUG(aCount);

 	MmuLock::Lock();

 	TUint32* pageList = aPhysicalPageList;

 	// get first page...

 	TPhysAddr physStart = PhysAddr(aIndex++);

 	if(physStart==KPhysAddrInvalid)

 		{

 		MmuLock::Unlock();

 		return KErrNotFound;

 		}

 	if(pageList)

 		*pageList++ = physStart;

 	TUint32 nextPhys = physStart+KPageSize;

 	TUint flash = 0;

 	while(--aCount)

 		{

 		MmuLock::Flash(flash,KMaxPagesInOneGo);

 		// get next page...

 		TPhysAddr phys = PhysAddr(aIndex++);

 		if(phys==KPhysAddrInvalid)

 			{

 			MmuLock::Unlock();

 			return KErrNotFound;

 			}

 		if(pageList)

 			*pageList++ = phys;

 		// check for contiguity...

 		if(phys!=nextPhys)

 			nextPhys = KPhysAddrInvalid;

 		else

 			nextPhys += KPageSize;

 		}

 	MmuLock::Unlock();

 	if(nextPhys==KPhysAddrInvalid)

 		{

 		// memory is discontiguous...

 		if(!aPhysicalPageList)

 			return KErrNotFound;

 		aPhysicalAddress = KPhysAddrInvalid;

 		return 1;

 		}

 	else

 		{

 		// memory is contiguous...

 		aPhysicalAddress = physStart;

 		return KErrNone;

 		}

 	}