--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kernel/eka/memmodel/epoc/flexible/mmu/mvalloc.cpp	Mon Oct 19 15:55:17 2009 +0100
@@ -0,0 +1,1000 @@
+// 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;
+	}
+
+
+TInt TVirtualSlab::Alloc(TLinAddr aAddr, TUint aSizeShift)
+	{
+	TRACE2(("TVirtualSlab::Alloc(0x%08x,%d)",aAddr,aSizeShift));
+	__NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift);
+	aSizeShift -= KVirtualAllocShift;
+	TUint index = (aAddr-iBase)>>KVirtualAllocShift;
+	__NK_ASSERT_DEBUG(iBase+(index<<KVirtualAllocShift)==aAddr);
+	TInt r = iAllocator.Alloc(index,aSizeShift);
+	if(r<0)
+		return r;
+	TRACE2(("TVirtualSlab::Alloc returns 0x%08x",iBase+(r<<KVirtualAllocShift)));
+	return r;
+	}
+
+
+TBool TVirtualSlab::Free(TLinAddr aAddr, TUint aSizeShift)
+	{
+	TRACE2(("TVirtualSlab::Free(0x%08x,%d)",aAddr,aSizeShift));
+	__NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift);
+	aSizeShift -= KVirtualAllocShift;
+	TUint offset = aAddr-iBase;
+	TUint index = offset>>KVirtualAllocShift;
+	__NK_ASSERT_DEBUG((index<<KVirtualAllocShift)==offset);
+	return iAllocator.Free(index,aSizeShift);
+	}
+
+
+//
+// RVirtualAllocSet
+//
+
+
+/**
+Class used by #RVirtualAllocator for allocating virtual addresses which
+have a size less than a 'chunk' (#KChunkSize).
+
+This consists of a set of #TVirtualSlab objects.
+*/
+class RVirtualAllocSlabSet
+	{
+public:
+	/**
+	Create a new slab set for use with the specified allocator.
+
+	@param aAllocator		The virtual address allocator which will use the slab set.
+	@param aNumSlabTypes	The number of slab types this allocator will support.
+	@param aWriteLock		Reference to the mutex which is being used to protect allocations
+							with this object. This is only used for debug checks and may be
+							a mutex assigned by #DMutexPool. In practice, this will usually be an
+							address space lock DAddressSpace::iLock.
+
+	@return The newly created #RVirtualAllocSlabSet or the null pointer if there was
+			insufficient memory.
+	*/
+	static RVirtualAllocSlabSet* New(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock);
+
+	~RVirtualAllocSlabSet();
+
+	/**
+	Allocate a region of virtual addresses.
+
+	@param[in,out] aAddr	On entry, if this is non-zero it represents
+							the start address a specific region to allocate.
+							On exit, this is set to the start address of the region allocated.
+	@param aSizeShift		Log2 of the size, in bytes, of the region.
+	@param aSlabType		The 'slab type' of the address to be allocated.		
+
+	@return KErrNone, if successful;
+			KErrAlreadyExists, if any part of the region was already allocated.
+
+	@pre The write lock must be held. (The \a aWriteLock argument for the constructor
+		 #RVirtualAllocSlabSet::RVirtualAllocSlabSet.)
+	*/
+	TInt Alloc(TLinAddr& aAddr, TUint aSizeShift, TUint aSlabType);
+
+	/**
+	Free a region of virtual addresses.
+
+	@param aAddr			The start address of the region.
+	@param aSizeShift		Log2 of the size, in bytes, of the region.
+
+	@pre The write lock must be held. (The \a aWriteLock argument for the constructor
+		 #RVirtualAllocSlabSet::RVirtualAllocSlabSet.)
+	*/
+	void Free(TLinAddr aAddr, TUint aSizeShift);
+
+	/**
+	Return true if the the address region specified by \a aAddr and \a aSizeShift was
+	allocated by this allocator using the specified \a aSlabType.
+
+	@pre The write lock must be held. (The \a aWriteLock argument for the constructor
+		 #RVirtualAllocSlabSet::RVirtualAllocSlabSet.)
+	*/
+	TBool CheckSlabType(TLinAddr aAddr, TUint aSizeShift, TUint aSlabType);
+
+private:
+	/**
+	Create a new slab (#TVirtualSlab) for use by this slab set.
+	Newly allocated slabs are added to #iLists[\a aSlabType].
+
+	The virtual address range used by the slab is obtained by
+	by allocating a slab sized region from #iAllocator.
+
+	@param aAddr		A virtual address which must be in the region to be covered by the slab.
+	@param aSlabType	The 'slab type'.
+	*/
+	TVirtualSlab* NewSlab(TLinAddr aAddr, TUint aSlabType);
+
+	/**
+	Delete a slab created with #NewSlab.
+	*/
+	void DeleteSlab(TVirtualSlab* aSlab);
+
+	/**
+	Constructor, for arguments see #New.
+	*/
+	RVirtualAllocSlabSet(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock);
+
+private:
+	/**
+	The virtual allocator which is using this slab set.
+	*/
+	RVirtualAllocator* iAllocator;
+
+	/**
+	Container for all slabs owned by this slab set. This is keyed on the starting
+	virtual address of the region each slab covers.
+
+	Each slab in this container is also linked into the #iLists member appropriate
+	to its slab type..
+	*/
+	RAddressedContainer iSlabs;
+
+	/**
+	The number of different 'slab types' this object can allocate addresses for.
+	*/
+	TUint iNumSlabTypes;
+
+	/**
+	An array of lists which each contain slabs of a single 'slab type'
+	which this object has created. Slabs are linked by their TVirtualSlab::iLink 
+	member.
+
+	This may extend into memory beyond the end of this object and contains
+	#iNumSlabTypes entries.
+
+	Each slab in these lists is also contained in #iSlabs.
+	*/
+	SDblQue iLists[1];
+	};
+
+
+FORCE_INLINE RVirtualAllocSlabSet::RVirtualAllocSlabSet(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock)
+	: iAllocator(aAllocator), iSlabs(0,aWriteLock), iNumSlabTypes(aNumSlabTypes)
+	{
+	while(aNumSlabTypes--)
+		new (&iLists+aNumSlabTypes) SDblQue;
+	}
+
+
+RVirtualAllocSlabSet* RVirtualAllocSlabSet::New(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock)
+	{
+	TUint size = sizeof(RVirtualAllocSlabSet)+sizeof(((RVirtualAllocSlabSet*)0x100)->iSlabs)*(aNumSlabTypes-1);
+	RVirtualAllocSlabSet* set = (RVirtualAllocSlabSet*)Kern::AllocZ(size);
+	if(set)
+		new (set) RVirtualAllocSlabSet(aAllocator,aNumSlabTypes,aWriteLock);
+	return set;
+	}
+
+
+RVirtualAllocSlabSet::~RVirtualAllocSlabSet()
+	{
+	__NK_ASSERT_DEBUG(iSlabs.Count()==0);
+	}
+
+
+TVirtualSlab* RVirtualAllocSlabSet::NewSlab(TLinAddr aAddr, TUint aSlabType)
+	{
+	TRACE2(("RVirtualAllocSlabSet::NewSlab(0x%08x,%d,%d)",aAddr,aSlabType));
+	__NK_ASSERT_DEBUG(aSlabType<iNumSlabTypes);
+
+	TVirtualSlab* slab = 0;
+	TLinAddr base;
+	TUint size;
+	TInt r = iAllocator->Alloc(base,size,aAddr&~KVirtualAllocSlabMask,KVirtualAllocSlabSize,aSlabType);
+	if(r==KErrNone)
+		{
+		slab = new TVirtualSlab(iLists[aSlabType],base,aSlabType);
+		if(slab && iSlabs.Add(base,slab)!=KErrNone)
+			{
+			delete slab;
+			slab = 0;
+			}
+		if(!slab)
+			iAllocator->Free(base,KVirtualAllocSlabSize);
+		}
+
+	TRACE2(("RVirtualAllocSlabSet::NewSlab returns 0x%08x",slab));
+	return slab;
+	}
+
+
+void RVirtualAllocSlabSet::DeleteSlab(TVirtualSlab* aSlab)
+	{
+	TLinAddr base = aSlab->Base();
+#ifdef _DEBUG
+	TAny* removedSlab = 
+#endif
+	iSlabs.Remove(base);
+	__NK_ASSERT_DEBUG(removedSlab==aSlab);
+	delete aSlab;
+	iAllocator->Free(base,KVirtualAllocSlabSize);
+	}
+
+
+TInt RVirtualAllocSlabSet::Alloc(TLinAddr& aAddr, TUint aSizeShift, TUint aSlabType)
+	{
+	__NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift && aSizeShift<KVirtualAllocSlabShift);
+	__NK_ASSERT_DEBUG(aSlabType<iNumSlabTypes);
+
+	if(!aAddr)
+		{
+		SDblQueLink* head = &iLists[aSlabType].iA;
+		SDblQueLink* link = head;
+		while((link=link->iNext)!=head)
+			{
+			TVirtualSlab* slab = _LOFF(link,TVirtualSlab,iLink);
+			TLinAddr addr = slab->Alloc(aSizeShift);
+			if(addr)
+				{
+				aAddr = addr;
+				return KErrNone;
+				}
+			}
+		TVirtualSlab* slab = NewSlab(0,aSlabType);
+		if(!slab)
+			return KErrNoMemory;
+		TLinAddr addr = slab->Alloc(aSizeShift);
+		if(!addr)
+			return KErrNoMemory;
+		aAddr = addr;
+		return KErrNone;
+		}
+
+	TVirtualSlab* slab = (TVirtualSlab*)iSlabs.Find(aAddr&~KVirtualAllocSlabMask);
+	if(!slab)
+		{
+		slab = NewSlab(aAddr,aSlabType);
+		if(!slab)
+			return KErrNoMemory;
+		}
+	else
+		{
+		if(slab->SlabType()!=aSlabType)
+			return KErrAlreadyExists; // slab is of incompatible type
+		}
+	return slab->Alloc(aAddr,aSizeShift);
+	}
+
+
+void RVirtualAllocSlabSet::Free(TLinAddr aAddr, TUint aSizeShift)
+	{
+	__NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift && aSizeShift<KVirtualAllocSlabShift);
+
+	TVirtualSlab* slab = (TVirtualSlab*)iSlabs.Find(aAddr&~KVirtualAllocSlabMask);
+	if(slab)
+		if(slab->Free(aAddr,aSizeShift))
+			DeleteSlab(slab);
+	}
+
+
+TBool RVirtualAllocSlabSet::CheckSlabType(TLinAddr aAddr, TUint aSizeShift, TUint aSlabType)
+	{
+	__NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift && aSizeShift<KVirtualAllocSlabShift);
+
+	TVirtualSlab* slab = (TVirtualSlab*)iSlabs.Find(aAddr&~KVirtualAllocSlabMask);
+	if(!slab)
+		{
+		TRACE2(("RVirtualAllocSlabSet::CheckSlabType returns No Slab"));
+		return false;
+		}
+
+	if(slab->iSlabType!=aSlabType)
+		{
+		TRACE2(("RVirtualAllocSlabSet::CheckSlabType returns Wrong Type"));
+		return false;
+		}
+
+	return true;
+	}
+
+
+//
+// RVirtualAllocator
+//
+
+RVirtualAllocator::RVirtualAllocator()
+	: iBase(0), iSize(0), iAllocator(0), iSlabSet(0)
+	{}
+
+
+RVirtualAllocator::~RVirtualAllocator()
+	{
+	__NK_ASSERT_DEBUG(iAllocator==0 || iAllocator->iAvail==iAllocator->iSize); // should be empty
+	Kern::Free(iAllocator);
+	Kern::Free(iSlabSet);
+	}
+
+
+TInt RVirtualAllocator::Construct(TLinAddr aStart, TLinAddr aEnd, TUint aNumSlabTypes, DMutex*& aWriteLock)
+	{
+	if((aStart|aEnd)&KVirtualAllocSlabMask)
+		return KErrArgument; // region not aligned to KVirtualAllocSlabSize
+	TUint bitSize = (aEnd-aStart)>>KVirtualAllocSlabShift;
+	iAllocator = TBitMapAllocator::New(bitSize, ETrue);
+	if(!iAllocator)
+		return KErrNoMemory;
+	iSlabSet = RVirtualAllocSlabSet::New(this,aNumSlabTypes,aWriteLock);
+	if(!iSlabSet)
+		return KErrNoMemory;
+	iBase = aStart;
+	iSize = aEnd-aStart;
+	return KErrNone;
+	}
+
+
+TUint RVirtualAllocator::AdjustRegion(TLinAddr& aAddr, TUint& aSize)
+	{
+	TLinAddr first = aAddr;
+	TLinAddr last = (aAddr+aSize-1);
+	TLinAddr dif = first^last;
+	TUint granularity = KVirtualAllocShift;
+	while(dif>>granularity && ++granularity<KVirtualAllocSlabShift)
+		{}
+	first >>= granularity;
+	last >>= granularity;
+	aAddr = first<<granularity;
+	aSize = (last-first+1)<<granularity;
+	return granularity;
+	}
+
+
+TInt RVirtualAllocator::Alloc(TLinAddr& aAddr, TUint& aSize, TLinAddr aRequestedAddr, TUint aRequestedSize, TUint aSlabType)
+	{
+	TRACE2(("RVirtualAllocator::Alloc(?,?,0x%08x,0x%08x,%d)",aRequestedAddr,aRequestedSize,aSlabType));
+
+	if(!aRequestedSize)
+		{
+		TRACE2(("RVirtualAllocator::Alloc zero size"));
+		return KErrArgument;
+		}
+
+	aAddr = aRequestedAddr;
+	aSize = aRequestedSize;
+	TUint align = AdjustRegion(aAddr,aSize);
+	TRACE2(("RVirtualAllocator::Alloc adjusted to 0x%08x+0x%08x, align=%d",aAddr,aSize,align));
+
+	if(align<KVirtualAllocSlabShift)
+		return iSlabSet->Alloc(aAddr,align,aSlabType);
+
+	__NK_ASSERT_DEBUG(align==KVirtualAllocSlabShift);
+	TUint size = aSize>>KVirtualAllocSlabShift;
+
+	if(!aAddr)
+		{
+		TInt r = iAllocator->AllocConsecutive(size, EFalse);
+		if(r>=0)
+			{
+			iAllocator->Alloc(r, size);
+			aAddr = iBase+(r<<KVirtualAllocSlabShift);
+			return KErrNone;
+			}
+		return KErrNoMemory;
+		}
+
+	// specific address requested...
+	if(!InRange(aAddr,aSize))
+		{
+		TRACE2(("RVirtualAllocator::Alloc not in range"));
+		return KErrArgument;
+		}
+
+	TUint offset = TUint(aAddr-iBase)>>KVirtualAllocSlabShift;
+	if(!iAllocator->NotFree(offset,size))
+		{
+		iAllocator->Alloc(offset,size);
+		return KErrNone;
+		}
+	else
+		{
+		TRACE2(("RVirtualAllocator::Alloc already allocated!"));
+		return KErrAlreadyExists;
+		}
+	}
+
+
+void RVirtualAllocator::Free(TLinAddr aAddr, TUint aSize)
+	{
+	if(!aSize)
+		return;
+
+	TRACE2(("RVirtualAllocator::Free(0x%08x,0x%08x)",aAddr,aSize));
+
+	TUint align = AdjustRegion(aAddr,aSize);
+	TRACE2(("RVirtualAllocator::Free adjusted to 0x%08x+0x%08x, align=%d",aAddr,aSize,align));
+
+	if(!InRange(aAddr,aSize))
+		{
+		TRACE2(("RVirtualAllocator::Free invalid region"));
+		__NK_ASSERT_ALWAYS(0);
+		return; // invalid region
+		}
+
+	if(align<KVirtualAllocSlabShift)
+		{
+		iSlabSet->Free(aAddr,align);
+		return;
+		}
+
+	__NK_ASSERT_DEBUG(align==KVirtualAllocSlabShift);
+	TUint offset = (aAddr-iBase)>>KVirtualAllocSlabShift;
+	TUint size = aSize>>KVirtualAllocSlabShift;
+	iAllocator->Free(offset,size);
+	}
+
+
+TBool RVirtualAllocator::CheckSlabType(TLinAddr aAddr, TUint aSize, TUint aSlabType)
+	{
+	TRACE2(("RVirtualAllocator::CheckSlabType(0x%08x,0x%08x,%d)",aAddr,aSize,aSlabType));
+	if(!aSize)
+		return false;
+
+	TUint align = AdjustRegion(aAddr,aSize);
+
+	if(!InRange(aAddr,aSize))
+		{
+		TRACE2(("RVirtualAllocator::CheckSlabType not in range"));
+		return false;
+		}
+
+	if(align<KVirtualAllocSlabShift)
+		{
+		return iSlabSet->CheckSlabType(aAddr,align,aSlabType);
+		}
+	else
+		{
+		return true;
+		}
+	}
+
+
+//
+// RBackwardsVirtualAllocator
+//
+
+TInt RBackwardsVirtualAllocator::Alloc(TLinAddr& aAddr, TUint& aSize, TLinAddr aRequestedAddr, TUint aRequestedSize, TUint aSlabType)
+	{
+	if(aRequestedAddr)
+		aRequestedAddr = (iBase+iSize)-(aRequestedAddr+aRequestedSize-iBase);
+	TInt r = RVirtualAllocator::Alloc(aAddr,aSize,aRequestedAddr,aRequestedSize,aSlabType);
+	if(r==KErrNone)
+		aAddr = (iBase+iSize)-(aAddr+aSize-iBase);
+	return r;
+	}
+
+
+void RBackwardsVirtualAllocator::Free(TLinAddr aAddr, TUint aSize)
+	{
+	RVirtualAllocator::Free((iBase+iSize)-(aAddr+aSize-iBase),aSize);
+	}
+
+