/*
* Copyright (c) 2008-2009 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
* This component and the accompanying materials are made available
* under the terms of "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 "allocator.h"
#include <kernel/kern_priv.h>

TAddressAllocator::TAddressAllocator(TLinAddr aMaxSize)
	:iMaxSize(aMaxSize)
	{
	TInt r = iRangeList.Append(TRange(0, iMaxSize, EFalse));
	__NK_ASSERT_ALWAYS(KErrNone==r);

	_LIT(KAllocatorMutex, "PCIAllocatorMutex");
	r = Kern::MutexCreate(iMutex, KAllocatorMutex, KMutexOrdGeneral0);
	__NK_ASSERT_ALWAYS(KErrNone==r);
	}

TAddressAllocator::~TAddressAllocator()
	{
	__NK_ASSERT_DEBUG(iRangeList.Count()==1);
	iRangeList.Reset();
	iMutex->Close(NULL);
	iMutex=NULL;
	}

/**
@return Indicates if alloc succeeded
@param aAddress This will be set to the starting address of the range if allocation succeeded.
@param aSize Size of memory range required in bytes. This must be a power of 2.
*/
TInt TAddressAllocator::Allocate(TLinAddr& aAddress, TLinAddr aSize)
	{
	//check size alignment
	__NK_ASSERT_ALWAYS( (aSize & (aSize - 1)) == 0 ); //assert aSize is power of 2.
	TInt r = KErrNotFound;

	NKern::ThreadEnterCS();
	Kern::MutexWait(*iMutex);

	const TInt count = iRangeList.Count();
	for(TInt i = 0; i < count; ++i)
		{
		TRange& range(iRangeList[i]);
		if(range.iAllocated == EFalse)
			{
			//amount which must be added to start address to align to aSize
			//(aSize must be a power of 2)
			const TLinAddr alignedOffset = (-range.iStart) & (aSize - 1);

			if((alignedOffset + aSize) <= range.iLength)
				{
				const TLinAddr alignedStart = range.iStart + alignedOffset;
				DoAllocate(alignedStart, aSize, i);
				aAddress = alignedStart;
				r = KErrNone;
				break;
				}

			}
		}
	__KTRACE_OPT(KPCI, Kern::Printf("TAddressAllocator::Allocate(): Allocated %d (0x%X) bytes at 0x%X", 
		aSize, aSize, aAddress));
	Kern::MutexSignal(*iMutex);
	NKern::ThreadLeaveCS();
	return r;
	}

/**
Mark region as allocated, with the assumption that region is unallocated.

@param aAddress The start address requested for new region
@param aSize Length of new region
@param aIndex Position to modify in iRangeList
*/
void TAddressAllocator::DoAllocate(TLinAddr aAddress, TLinAddr aSize, TInt aIndex)
	{
	__NK_ASSERT_DEBUG(InvariantCheck());
	//check that new region will lie within existing range
	__NK_ASSERT_ALWAYS(
			(aAddress >= iRangeList[aIndex].iStart) &&
			((aAddress + aSize) <= (iRangeList[aIndex].End() + 1))
			);

	//allocating at start of unallocated region
	if(iRangeList[aIndex].iStart == aAddress)
		{
		//will there be space left at end of region?
		if((iRangeList[aIndex].iLength - aSize) > 0)
			{
			const TRange newFreeRange(iRangeList[aIndex].iStart + aSize, iRangeList[aIndex].iLength - aSize, EFalse);
			const TInt r = iRangeList.Insert(newFreeRange, aIndex + 1);
			__NK_ASSERT_ALWAYS(KErrNone == r);

			iRangeList[aIndex].iLength = aSize;
			}

		iRangeList[aIndex].iAllocated = ETrue;
		}
	else
		{
		//allocating from middle of an unallocated region
		const TRange newAllocRange(aAddress, aSize, ETrue);
		TInt r = iRangeList.Insert(newAllocRange, aIndex + 1);
		__NK_ASSERT_ALWAYS(KErrNone == r);

		//is there an unallocated gap after the newly allocated range?
		TLinAddr diff = iRangeList[aIndex].End() - newAllocRange.End();
		if( diff > 0 )
			{
			const TRange newFreeRange(newAllocRange.End() + 1, diff, EFalse);
			r=iRangeList.Insert(newFreeRange, aIndex + 2);
			__NK_ASSERT_ALWAYS(KErrNone == r);
			}

		iRangeList[aIndex].iLength = aAddress - iRangeList[aIndex].iStart;
		}
	//calculate invariant: run through array to check that ranges are contiguous
	__NK_ASSERT_DEBUG(InvariantCheck());
	}

#if defined (_DEBUG)
void TAddressAllocator::Print()
	{
	__KTRACE_OPT(KPCI, Kern::Printf("TAddressAllocator::Print(): Printing ranges"));
	const TInt count = iRangeList.Count();
	for(TInt i=0; i<count; ++i)
		{
		const TRange& r(iRangeList[i]);
		__KTRACE_OPT(KPCI, Kern::Printf("  index:%d, start:%x, length:%x, end:%x, allocated:%d",
				i, r.iStart, r.iLength, r.End(), r.iAllocated));
		}
	}

TBool TAddressAllocator::InvariantCheck()
	{
	//Print();
	const TInt count = iRangeList.Count();
	__NK_ASSERT_ALWAYS(count>0);
	__NK_ASSERT_ALWAYS(iRangeList[0].iStart==0);
	__NK_ASSERT_ALWAYS(iRangeList[count-1].End()==iMaxSize-1);

	for(TInt i=1; i<count; ++i)
		{
		const TRange& prev = iRangeList[i-1];
		const TRange& curr = iRangeList[i];
		__NK_ASSERT_ALWAYS(prev.End()==curr.iStart-1);
		__NK_ASSERT_ALWAYS(curr.iLength>0);

		//check that free spaces are always consolidated
		if(!prev.iAllocated)
			{
			__NK_ASSERT_ALWAYS(curr.iAllocated);
			}
		}
	return ETrue;
	}
#endif

TInt TAddressAllocator::TRange::OrderByStart(const TRange& aKeyRange, const TRange& aRange)
	{
	if(aKeyRange.iStart > aRange.iStart)
		return 1;
	else if(aKeyRange.iStart < aRange.iStart)
		return -1;
	else
		return 0;
	}

/**
Make a region of PCI memory available again.

@param aAddress Start address of an allocated PCI range to deallocate.
@return
	- KErrNone If the region was deallocated
	- KErrNotFound if aAddress is not the beginning of a previously
	  allocated range.
*/
TInt TAddressAllocator::DeAllocate(TLinAddr aAddress)
	{
	NKern::ThreadEnterCS();
	Kern::MutexWait(*iMutex);

	TInt r=KErrNone;

	TRange key(aAddress, 0, EFalse);
	TLinearOrder<TRange> startOrder(TRange::OrderByStart);
	TInt index = iRangeList.FindInOrder(key, startOrder);

	if(index==KErrNotFound || (!iRangeList[index].iAllocated))
		{
		r=KErrNotFound;
		}
	else
		{
		Remove(index);
		}

	Kern::MutexSignal(*iMutex);
	NKern::ThreadLeaveCS();
	return r;
	}

/**
Remove the allocated region and adjust remaining regions
to consolidate free space.
*/
void TAddressAllocator::Remove(TInt aIndex)
	{
	__KTRACE_OPT(KPCI, Kern::Printf("TAddressAllocator::Remove(): Removing %d (0x%X) bytes at 0x%X", 
		iRangeList[aIndex].iLength, iRangeList[aIndex].iLength, iRangeList[aIndex].iStart));
	__NK_ASSERT_DEBUG(InvariantCheck());
	const TInt count = iRangeList.Count();
	//range is above an unallocated range
	if(aIndex > 0 && (!iRangeList[aIndex - 1].iAllocated) )
		{
		//range is below unallocated range
		if(aIndex < (count - 1) && !(iRangeList[aIndex + 1].iAllocated))
			{
			iRangeList[aIndex - 1].iLength = iRangeList[aIndex + 1].End() + 1 -iRangeList[aIndex - 1].iStart;
			iRangeList.Remove(aIndex);
			iRangeList.Remove(aIndex);
#ifdef _DEBUG
			//The PCI kernel extension contains several persistent dynamic arrays and by default these RArrays 
			//do not free heap for every item that is removed. In order to ensure that  kernel heap checking 
			//succeeds  Compress() calls are needed to force this excess memory to be freed.  This calls are only
			//made in UDEB builds only as KHEAP checks are only performed in UDEB mode.
			iRangeList.Compress();
#endif
			}
		else
			{
			iRangeList[aIndex - 1].iLength = iRangeList[aIndex].End() + 1 - iRangeList[aIndex - 1].iStart;
			iRangeList.Remove(aIndex);
#ifdef _DEBUG			
			//The PCI kernel extension contains several persistent dynamic arrays and by default these RArrays 
			//do not free heap for every item that is removed. In order to ensure that  kernel heap checking 
			//succeeds  Compress() calls are needed to force this excess memory to be freed.  This calls are only
			//made in UDEB builds only as KHEAP checks are only performed in UDEB mode.
			iRangeList.Compress();
#endif
			}
		}
	//range is above allocated range
	else
		{
		//range is below unallocated range
		if(aIndex < (count - 1) && !(iRangeList[aIndex + 1].iAllocated))
			{
			iRangeList[aIndex].iAllocated=EFalse;
			iRangeList[aIndex].iLength=iRangeList[aIndex + 1].End() + 1 - iRangeList[aIndex].iStart;
			iRangeList.Remove(aIndex + 1);
#ifdef _DEBUG
			//The PCI kernel extension contains several persistent dynamic arrays and by default these RArrays 
			//do not free heap for every item that is removed. In order to ensure that  kernel heap checking 
			//succeeds  Compress() calls are needed to force this excess memory to be freed.  This calls are only
			//made in UDEB builds only as KHEAP checks are only performed in UDEB mode.
			iRangeList.Compress();
#endif
			}
		else
			{
			iRangeList[aIndex].iAllocated = EFalse;
			}
		}
	//calculate invariant: run through array to check that ranges are contiguous
	__NK_ASSERT_DEBUG(InvariantCheck());
	}