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



//
// RSlabAllocatorBase
//

RSlabAllocatorBase::RSlabAllocatorBase(TBool aDelayedCleanup)
	:	iFreeCount(0), iReserveCount(0),
		iSpinLock(TSpinLock::EOrderGenericIrqHigh3),
		iDelayedCleanup(aDelayedCleanup), iSlabMap(0), iMemory(0), iMapping(0)
	{
	}


RSlabAllocatorBase::~RSlabAllocatorBase()
	{
	delete iSlabMap;
	MM::MappingDestroy(iMapping);
	MM::MemoryDestroy(iMemory);
	}


TInt RSlabAllocatorBase::Construct(TUint aMaxSlabs, TUint aObjectSize)
	{
	return Construct(aMaxSlabs,aObjectSize,0);
	}


TInt RSlabAllocatorBase::Construct(TUint aMaxSlabs, TUint aObjectSize, TLinAddr aBase)
	{
	TRACE2(("RSlabAllocatorBase::Construct(0x%08x,0x%08x,0x%08x)",aMaxSlabs,aObjectSize,aBase));

	// set sizes...
	iObjectSize = aObjectSize;
	iObjectsPerSlab = ((KPageSize-sizeof(TSlabHeader))/aObjectSize);

	// sanity check arguments...
	__NK_ASSERT_DEBUG(iObjectsPerSlab);
	__NK_ASSERT_DEBUG(aObjectSize>=sizeof(SDblQueLink));
	__NK_ASSERT_DEBUG(aObjectSize%sizeof(TAny*)==0);

	// construct bitmap for slabs...
	iSlabMap = TBitMapAllocator::New(aMaxSlabs,ETrue);
	if(!iSlabMap)
		return KErrNoMemory;

	if(aBase)
		{
		// setup base address, we expect one slab to already be mapped at this address...
		iBase = aBase;

		// initialise first slab...
		iSlabMap->Alloc(0,1);
		InitSlab(iBase);
		}
	else
		{
		// construct memory object for slabs...
		__NK_ASSERT_DEBUG(!iMemory);
		TInt r = MM::MemoryNew(iMemory,EMemoryObjectUnpaged,aMaxSlabs);
		if(r!=KErrNone)
			return r;

		// construct memory mapping for slabs...
		r = MM::MappingNew(iMapping,iMemory,ESupervisorReadWrite,KKernelOsAsid);
		if(r!=KErrNone)
			return r;

		// setup base address...
		iBase = MM::MappingBase(iMapping);
		}

	// done...
	return KErrNone;
	}


TAny* RSlabAllocatorBase::Alloc()
	{
#ifdef _DEBUG
	RamAllocLock::Lock();
	TBool fail = K::CheckForSimulatedAllocFail();
	RamAllocLock::Unlock();
	if(fail)
		return 0;
#endif
	__SPIN_LOCK_IRQ(iSpinLock);

	// check if we need to allocate a new slab...
	if(iFreeCount<=iReserveCount && !NewSlab())
		{
		__SPIN_UNLOCK_IRQ(iSpinLock);
		return 0;
		}

	// get a slab with unused objects...
	TSlabHeader* slab = (TSlabHeader*)iFreeList.iA.iNext;
	__NK_ASSERT_DEBUG(slab!=(TSlabHeader*)&iFreeList.iA.iNext);
#ifdef _DEBUG
	CheckSlab(slab);
#endif

	// get object from slab...
	SDblQueLink* object = (SDblQueLink*)slab->iFreeList.iA.iNext;
	TRACE2(("RSlabAllocatorBase::Alloc got 0x%08x",object));
	object->Deque();
	__NK_ASSERT_DEBUG(slab->iAllocCount<iObjectsPerSlab);
	++slab->iAllocCount;
	--iFreeCount;

	// see if there are uninitialised free objects after the one just allocated...
	if(slab->iHighWaterMark==object)
		{
		SDblQueLink* nextFree = (SDblQueLink*)((TLinAddr)object+iObjectSize);
		if((TAny*)((TLinAddr)nextFree+iObjectSize)<=slab)
			{
			slab->iHighWaterMark = nextFree;
			slab->iFreeList.Add(nextFree);
			}
		}

	// if slab has no more free objects, remove it from the free list...
	if(slab->iFreeList.iA.iNext==&slab->iFreeList.iA)
		slab->Deque();

	__SPIN_UNLOCK_IRQ(iSpinLock);

	return object;
	}


void RSlabAllocatorBase::Free(TAny* aObject)
	{
	TRACE2(("RSlabAllocatorBase::Free(0x%08x)",aObject));

	if(!aObject)
		{
		// nothing to do
		return; 
		}

	__SPIN_LOCK_IRQ(iSpinLock);

	// check object address is valid...
	__NK_ASSERT_DEBUG((TLinAddr)aObject-iBase < iSlabMap->iSize*(TLinAddr)KPageSize); // in range
	__NK_ASSERT_DEBUG(((TLinAddr)aObject&KPageMask)%iObjectSize==0); // aligned correctly
	__NK_ASSERT_DEBUG(((TLinAddr)aObject&KPageMask)<iObjectSize*iObjectsPerSlab); // in slab

	// get slab for object...
	TSlabHeader* slab = (TSlabHeader*)(((TLinAddr)aObject|KPageMask)+1)-1;
#ifdef _DEBUG
	CheckSlab(slab);
#endif

	// if slab didn't previously have any free objects, add it to the free list...
	if(slab->iFreeList.iA.iNext==&slab->iFreeList.iA)
		iFreeList.AddHead(slab);

	// add object to slab's free list...
	slab->iFreeList.AddHead((SDblQueLink*)(TAny*)aObject);
	TUint allocCount = --slab->iAllocCount;
	__NK_ASSERT_DEBUG(allocCount<iObjectsPerSlab);
	++iFreeCount;

	if(!allocCount)
		{
		// if slab is empty, put it on end of free list...
		slab->Deque();
		iFreeList.Add(slab);
		}
	else
		{
		// migrate slab to try and keep fuller slabs near the free list start...
		TSlabHeader* nextSlab = (TSlabHeader*)slab->iNext;
		if(nextSlab!=(SDblQueLink*)&iFreeList && allocCount<=nextSlab->iAllocCount)
			{
			slab->Deque();
			slab->InsertAfter(nextSlab);
			}
		}

#ifdef _DEBUG
	CheckSlab(slab);
#endif

	// check for spare empty slab...
	TSlabHeader* lastSlab = (TSlabHeader*)iFreeList.iA.iPrev;
	if(lastSlab->iNext!=lastSlab->iPrev && lastSlab->iAllocCount==0) // not only slab and it's empty...
		{
		// free up slab...
		if(!iDelayedCleanup)
			{
			// free up slab now, (this also relinquishes iSpinLock)...
			FreeSlab(lastSlab);
			}
		else
			{
			// queue later cleanup...
			__SPIN_UNLOCK_IRQ(iSpinLock);
			iCleanup.Add(CleanupTrampoline,this);
			}
		}
	else
		{
		__SPIN_UNLOCK_IRQ(iSpinLock);
		}
	}


#ifdef _DEBUG

void RSlabAllocatorBase::CheckSlab(TSlabHeader* aSlab)
	{
//	Kern::Printf("CheckSlab %x %x %d",aSlab,aSlab->iHighWaterMark,aSlab->iAllocCount);
	TAny* base = (TAny*)((TLinAddr)aSlab&~KPageMask);
	SDblQueLink* o = aSlab->iFreeList.First();
	TUint max = ((TLinAddr)aSlab->iHighWaterMark-(TLinAddr)base)/iObjectSize+1;
	__NK_ASSERT_DEBUG(aSlab->iAllocCount<=max);
	__NK_ASSERT_DEBUG(max<=iObjectsPerSlab);
	TUint freeCount = max-aSlab->iAllocCount;
	while(freeCount)
		{
//		Kern::Printf("CheckSlab o=%x",o);
		__NK_ASSERT_DEBUG(o>=base);
		__NK_ASSERT_DEBUG(o<=aSlab->iHighWaterMark);
		__NK_ASSERT_DEBUG((((TLinAddr)o-(TLinAddr)base)%iObjectSize)==0);
		o = o->iNext;
		--freeCount;
		}
	__NK_ASSERT_DEBUG(o==&aSlab->iFreeList.iA);
	}

#endif


TBool RSlabAllocatorBase::NewSlab()
	{
	TRACE2(("RSlabAllocatorBase::NewSlab()"));

	for(;;)
		{
		__SPIN_UNLOCK_IRQ(iSpinLock);
		MM::MemoryLock(iMemory);

		if(iAllocatingSlab)
			{
			// we've gone recursive...
			__NK_ASSERT_DEBUG(iFreeCount); // check we still have some reserved objects

			// lie and pretend we've allocated a slab which will allow Alloc() to proceed...
			MM::MemoryUnlock(iMemory);
			__SPIN_LOCK_IRQ(iSpinLock);
			return true;
			}

		iAllocatingSlab = true;

		// still need new slab?
		if(iFreeCount<=iReserveCount)
			{
			// find unused slab...
			TInt i = iSlabMap->Alloc();
			if(i<0)
				break; // out of memory

			// commit memory for slab...
			TInt r = MM::MemoryAlloc(iMemory,i,1);
			if(r!=KErrNone)
				{
				iSlabMap->Free(i);
				break; // error
				}

			// initialise slab...
			TLinAddr page = iBase+(i<<KPageShift);
			InitSlab(page);
			TRACE2(("RSlabAllocatorBase::NewSlab() allocated 0x%08x",(TSlabHeader*)(page+KPageSize)-1));
			}

		iAllocatingSlab = false;

		MM::MemoryUnlock(iMemory);
		__SPIN_LOCK_IRQ(iSpinLock);

		// still need new slab?
		if(iFreeCount>iReserveCount)
			return true; // no, so finish
		}

	// failed...
	iAllocatingSlab = false;
	MM::MemoryUnlock(iMemory);
	__SPIN_LOCK_IRQ(iSpinLock);
	return false;
	}


void RSlabAllocatorBase::InitSlab(TLinAddr aPage)
	{
	TRACE2(("RSlabAllocatorBase::InitSlab(0x%08x)",aPage));

	// header goes at end of slab...
	TSlabHeader* slab = (TSlabHeader*)(aPage+KPageSize)-1;

	// link first object in slab onto the slab's free list...
	SDblQueLink* head = &slab->iFreeList.iA;
	SDblQueLink* first = (SDblQueLink*)aPage;
	head->iNext = first;
	head->iPrev = first;
	first->iPrev = head;
	first->iNext = head;

	// setup rest of slab header...
	slab->iAllocCount = 0;
	slab->iHighWaterMark = first;

	// put new slab at end of free slab list...
	__SPIN_LOCK_IRQ(iSpinLock);
	iFreeList.Add(slab);
	iFreeCount += iObjectsPerSlab;
	__SPIN_UNLOCK_IRQ(iSpinLock);
	}


void RSlabAllocatorBase::FreeSlab(TSlabHeader* aSlab)
	{
	TRACE2(("RSlabAllocatorBase::FreeSlab(0x%08x)",aSlab));

	aSlab->Deque();
	iFreeCount -= iObjectsPerSlab;
	__SPIN_UNLOCK_IRQ(iSpinLock);

	MM::MemoryLock(iMemory);
	TUint i = ((TLinAddr)aSlab-iBase)>>KPageShift;
	MM::MemoryFree(iMemory,i,1);
	iSlabMap->Free(i);
	MM::MemoryUnlock(iMemory);
	}


//
// Cleanup
//

void RSlabAllocatorBase::CleanupTrampoline(TAny* aSelf)
	{
	((RSlabAllocatorBase*)aSelf)->Cleanup();
	}


void RSlabAllocatorBase::Cleanup()
	{
	// free any empty slabs...
	for(;;)
		{
		__SPIN_LOCK_IRQ(iSpinLock);
		TSlabHeader* slab = (TSlabHeader*)iFreeList.iA.iPrev; // get slab from end of list
		if(slab==iFreeList.iA.iNext)
			break; // only slab left, so leave it
		if(slab->iAllocCount!=0)
			break; // slab has allocated objects, so end, (empty slabs are always at end of list)
		FreeSlab(slab);
		}
	__SPIN_UNLOCK_IRQ(iSpinLock);
	}