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