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

#include "maddrcont.h"

/**

Log2 of the minimum granularity and alignment of virtual address allocation.

Must be greater than or equal to #KPageShift+#KPageColourShift.

*/

const TUint KVirtualAllocShift = KPageShift+KPageColourShift;

/**

Log2 of the size of the region covered by a single 'slab' of virtual addresses.

Must be greater than or equal to KChunkShift.

*/

const TUint KVirtualAllocSlabShift = KChunkShift;

/**

Size, in bytes, of the size of the region covered by a single 'slab' of virtual addresses.

*/

const TUint KVirtualAllocSlabSize = 1<<KVirtualAllocSlabShift;

const TUint KVirtualAllocSlabMask = KVirtualAllocSlabSize-1;

__ASSERT_COMPILE(KVirtualAllocShift>=KPageShift+KPageColourShift);

__ASSERT_COMPILE(KVirtualAllocSlabShift>=TUint(KChunkShift));

#if defined(__GCCXML__)

FORCE_INLINE TUint CountLeadingZeroes(TUint32 /*aValue*/)

	{

	// empty

	return 0;

	}

#elif defined(__MARM__)

#ifdef __ARMCC__

FORCE_INLINE TUint CountLeadingZeroes(TUint32 aValue)

	{

	#if __ARMCC_VERSION < 310000

		TUint r;

		asm("clz r,aValue");

		return r;

	#else

		// Inline assembler is deprecated in RVCT 3.1 so we use an intrinsic.

		return __clz(aValue);

	#endif

	}

#endif // __ARMCC__

#ifdef __MARM_ARM4__

__declspec(naked) static TUint CountLeadingZeroes(TUint32)

	{

	CLZ(0,0);

	__JUMP(,lr);

	}

#elif defined(__GNUC__)

FORCE_INLINE TUint CountLeadingZeroes(TUint32 aValue)

	{

	TUint r;

	asm("clz %0,%1" : "=r"(r) : "r"(aValue));

	return r;

	}

#endif //  __GNUC__

#else // !__MARM__

inline TUint CountLeadingZeroes(TUint32 aValue)

	{

	if(!aValue)

		return 32;

	TUint count = 31;

	if(aValue>=(1<<16))

		{

		count -= 16;

		aValue >>= 16;

		}

	if(aValue>=(1<<8))

		{

		count -= 8;

		aValue >>= 8;

		}

	if(aValue>=(1<<4))

		{

		count -= 4;

		aValue >>= 4;

		}

	if(aValue>=(1<<2))

		{

		count -= 2;

		aValue >>= 2;

		}

	count -= aValue>>1;

	return count;

	}

#endif // __MARM__

//

// TLogAllocator

//

/**

Bitmap allocator for allocating regions which have size and alignment which

are a power-of-two.

*/

class TLogAllocator

	{

public:

	TLogAllocator();

	/**

	Find and allocate a free region in the bitmap.

	@param aSizeShift	Log2 of the number of bits to allocate.

	@return If successful, the index of the first bit allocated.

			Otherwise, -1.

	*/

	TInt Alloc(TUint aSizeShift);

	/**

	Allocate a specific region of bits.

	@param aIndex		The index of the first bit to allocated.

						Must be a integer multiple of 2^aSizeShift.

	@param aSizeShift	Log2 of the number of bits to allocate.

	@return KErrNone, if successful;

			KErrAlreadyExists, if any part of the region was already allocated.

	*/

	TInt Alloc(TUint aIndex, TUint aSizeShift);

	/**

	Free a specific region of bits.

	@param aIndex		The index of the first bit to free.

						Must be a integer multiple of 2^aSizeShift.

	@param aSizeShift	Log2 of the number of bits to free.

	@return True, if the slab no longer has any bits allocated.

	*/

	TBool Free(TUint aIndex, TUint aSizeShift);

private:

	enum

		{

		ENumBits = 1<<(KVirtualAllocSlabShift-KVirtualAllocShift),

		ENumWords = (ENumBits+31)/32

		};

	/**

	Number of bits which have been allocated.

	*/

	TUint iAllocCount;

	/**

	Bitmap where a bit set to one indicates 'free' and a bit cleared to zero

	indicates 'allocated'. The most significant bit in each word has the lowest

	index value. E.g.

	- Index 0 is bit 31 of iBits[0]

	- Index 31 is bit 0 of iBits[0]

	- Index 32 is bit 31 of iBits[1]

	*/

	TUint32 iBits[ENumWords];

	};

TLogAllocator::TLogAllocator()

	{

	iAllocCount = 0;

	memset(iBits,~0u,sizeof(iBits)); // unallocated bits are set to one

	}

TInt TLogAllocator::Alloc(TUint aSizeShift)

	{

	TUint size = 1<<aSizeShift;

	__NK_ASSERT_DEBUG(size<=ENumBits); // check in range

	TUint32* bits = iBits;

	TUint32* bitsEnd = bits+ENumWords;

	TUint32 b;

	switch(aSizeShift)

		{

	case 0: // find word with any unallocated bits...

		do

			{

			b = *bits++;

			if(b)

				goto small_found;

			}

		while(bits<bitsEnd);

		break;

	case 1: // find word with 2 adjacent unallocated bits...

		do

			{

			b = *bits++;

			b &= b<<1;

			b &= 0xaaaaaaaa;

			if(b)

				goto small_found;

			}

		while(bits<bitsEnd);

		break;

	case 2: // find word with 4 adjacent unallocated bits...

		do

			{

			b = *bits++;

			b &= b<<1;

			b &= b<<2;

			b &= 0x88888888;

			if(b)

				goto small_found;

			}

		while(bits<bitsEnd);

		break;

	case 3: // find word with 8 adjacent unallocated bits...

		do

			{

			b = *bits++;

			b &= b<<1;

			b &= b<<2;

			b &= b<<4;

			b &= 0x80808080;

			if(b)

				goto small_found;

			}

		while(bits<bitsEnd);

		break;

	case 4: // find word with 16 adjacent unallocated bits...

		do

			{

			b = *bits++;

			b &= b<<1;

			b &= b<<2;

			b &= b<<4;

			b &= b<<8;

			b &= 0x80008000;

			if(b)

				goto small_found;

			}

		while(bits<bitsEnd);

		break;

	case 5: // find word which is totally unallocated (has 32 bits free)...

		do

			{

			b = *bits++;

			if(b==0xffffffffu)

				goto big_found;

			}

		while(bits<bitsEnd);

		break;

	default: // find relevant number of words which are unallocated...

		{

		do

			{

			// AND words together...

			TUint32* end = (TUint32*)((TUint8*)bits+(size>>3));

			TUint32 b = 0xffffffffu;

			do b &= *bits++;

			while(bits<end);

			if(b==0xffffffffu)

				goto big_found; // all were free

			}

		while(bits<bitsEnd);

		break;

		}

		}

	__NK_ASSERT_DEBUG(bits==bitsEnd);

	return -1;

small_found:

	{

	// find first position in word which have free region (a bit set to one)...

	TUint offset = CountLeadingZeroes(b);

	// clear bits...

	TUint32 mask = 0xffffffffu;

	mask >>= size;

	mask = ~mask;

	mask >>= offset;

	*--bits &= ~mask;

	// calculate index for allocated region...

	TUint index = (bits-iBits)*32+offset;

	iAllocCount += size;

	return index;

	}

big_found:

	{

	// clear bits...

	TUint32* start = (TUint32*)((TUint8*)bits-(size>>3));

	do *--bits = 0;

	while(bits>start);

	// calculate index for allocated region...

	TUint index = (bits-iBits)*32;

	iAllocCount += size;

	return index;

	}

	}

TInt TLogAllocator::Alloc(TUint aIndex, TUint aSizeShift)

	{

	TUint size = 1<<aSizeShift;

	__NK_ASSERT_DEBUG(aIndex+size>aIndex); // check overflow

	__NK_ASSERT_DEBUG(aIndex+size<=ENumBits); // check in range

	__NK_ASSERT_DEBUG(((aIndex>>aSizeShift)<<aSizeShift)==aIndex); // check alignment

	TUint32* bits = iBits+(aIndex>>5);

	if(size<32)

		{

		TUint32 mask = 0xffffffffu;

		mask >>= size;

		mask = ~mask;

		mask >>= aIndex&31;

		TUint32 b = *bits;

		if((b&mask)!=mask)

			return KErrAlreadyExists;

		*bits = b&~mask;

		}

	else

		{

		TUint32* start = bits;

		TUint32* end = bits+(size>>5);

		do if(*bits++!=0xffffffffu) return KErrAlreadyExists;

		while(bits<end);

		bits = start;

		do *bits++ = 0;

		while(bits<end);

		}

	iAllocCount += size;

	return KErrNone;

	}

TBool TLogAllocator::Free(TUint aIndex, TUint aSizeShift)

	{

	TUint size = 1<<aSizeShift;

	__NK_ASSERT_DEBUG(aIndex+size>aIndex); // check overflow

	__NK_ASSERT_DEBUG(aIndex+size<=ENumBits); // check in range

	__NK_ASSERT_DEBUG(((aIndex>>aSizeShift)<<aSizeShift)==aIndex); // check alignment

	TUint32* bits = iBits+(aIndex>>5);

	if(size<32)

		{

		TUint32 mask = 0xffffffffu;

		mask >>= size;

		mask = ~mask;

		mask >>= aIndex&31;

		TUint32 b = *bits;

		__NK_ASSERT_DEBUG((b&mask)==0); // check was allocated

		*bits = b|mask;

		}

	else

		{

		TUint wordCount = size>>5;

		do

			{

			__NK_ASSERT_DEBUG(bits[0]==0);

			*bits++ = 0xffffffffu;

			}

		while(--wordCount);

		}

	iAllocCount -= size;

	return !iAllocCount;

	}

//

// TVirtualSlab

//

/**

Class for allocating virtual addresses contained in a single 'slab'.

@see RVirtualAllocSlabSet.

*/

class TVirtualSlab

	{

public:

	/**

	@param aHead		The head of a linked list of slabs to which this one should be added.

	@param aBase		The starting virtual address of the region covered by this slab.

	@param aSlabType	The 'slab type'.

	*/

	TVirtualSlab(SDblQue& aHead, TUint aBase, TUint aSlabType);

	~TVirtualSlab();

	/**

	Find an allocate a free region of virtual addresses.

	@param aSizeShift	Log2 of the size, in bytes, of the region.

	@return If successful, the allocated virtual address.

			Otherwise, 0 (zero).

	*/

	TLinAddr Alloc(TUint aSizeShift);

	/**

	Allocate a specific region of virtual addresses.

	@param aAddr		The start address of the region.

						Must be a integer multiple of 2^aSizeShift.

	@param aSizeShift	Log2 of the size, in bytes, of the region.

	@return KErrNone, if successful;

			KErrAlreadyExists, if any part of the region was already allocated.

	*/

	TInt Alloc(TLinAddr aAddr, TUint aSizeShift);

	/**

	Free a specific region of virtual addresses.

	@param aAddr		The start address of the region.

						Must be a integer multiple of 2^aSizeShift.

	@param aSizeShift	Log2 of the size, in bytes, of the region.

	@return True, if the slab no longer has any addresses allocated.

	*/

	TBool Free(TLinAddr aAddr, TUint aSizeShift);

	/**

	Return the starting virtual address of the region covered by this slab.

	*/

	FORCE_INLINE TLinAddr Base() { return iBase; }

	/**

	Return this objects 'slab type'. 

	*/

	FORCE_INLINE TUint SlabType() { return iSlabType; }

private:

	/**

	Link object used to insert this slab into lists.

	*/

	SDblQueLink iLink;

	/**

	The starting virtual address of the region covered by this slab.

	*/

	TLinAddr iBase;

	/**

	This objects 'slab type'. 

	*/

	TUint8 iSlabType;

	/**

	Bitmap allocator used to allocated pages in this slab's virtual address region.

	*/

	TLogAllocator iAllocator;

	friend class RVirtualAllocSlabSet;

	};

TVirtualSlab::TVirtualSlab(SDblQue& aHead, TUint aBase, TUint aSlabType)

	: iBase(aBase),iSlabType(aSlabType)

	{

	TRACE2(("TVirtualSlab::TVirtualSlab(?,0x%08x,%d)",aBase, aSlabType));

	aHead.Add(&iLink);

	}

TVirtualSlab::~TVirtualSlab()

	{

	TRACE2(("TVirtualSlab::~TVirtualSlab base=0x%08x",iBase));

	iLink.Deque();

	}

TLinAddr TVirtualSlab::Alloc(TUint aSizeShift)

	{

	TRACE2(("TVirtualSlab::Alloc(%d)",aSizeShift));

	__NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift);

	aSizeShift -= KVirtualAllocShift;

	TInt index = iAllocator.Alloc(aSizeShift);

	TLinAddr addr = 0;

	if(index>=0)

		addr = iBase+(index<<KVirtualAllocShift);

	TRACE2(("TVirtualSlab::Alloc returns 0x%08x",addr));

	return addr;

	}