sl@0: // Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: //
sl@0: 
sl@0: #include <hal.h>
sl@0: #include <fbs.h>
sl@0: #include <bitmap.h>
sl@0: #include "UTILS.H"
sl@0: 
sl@0: 
sl@0: GLREF_C void Panic(TFbsPanic aPanic);
sl@0: 
sl@0: LOCAL_C TInt GranularRoundUp(TInt aCount)
sl@0: 	{
sl@0: 	return (aCount + 7) & ~7;
sl@0: 	}
sl@0: 
sl@0: CChunkPile::CChunkPile(const RChunk& aChunk)
sl@0: :	iChunk(aChunk)
sl@0: 	{}
sl@0: 
sl@0: EXPORT_C CChunkPile::~CChunkPile()
sl@0: 	{
sl@0: 	iChunk.Close();
sl@0: 	iSmallCells.Close();
sl@0: 	iFreeSmallCellLinks.Close();
sl@0: 	iLargeCells.Close();
sl@0: 	iFreeLargeCellLinks.Close();
sl@0: 	iLock.Close();
sl@0: 	}
sl@0: 
sl@0: EXPORT_C CChunkPile* CChunkPile::NewL(const RChunk& aChunk)
sl@0: 	{
sl@0: 	CChunkPile* thisptr=new(ELeave) CChunkPile(aChunk);
sl@0: 	CleanupStack::PushL(thisptr);
sl@0: 	thisptr->ConstructL();
sl@0: 	CleanupStack::Pop();
sl@0: 	return(thisptr);
sl@0: 	}
sl@0: 
sl@0: void CChunkPile::ConstructL()
sl@0: 	{
sl@0: 	TInt ret = iChunk.Duplicate(RThread());
sl@0: 	__ASSERT_ALWAYS(ret == KErrNone, Panic(EFbsPanicChunkError));
sl@0: 	HAL::Get(HAL::EMemoryPageSize, iPageSize);
sl@0: 	__ASSERT_ALWAYS(iPageSize > 4, Panic(EFbsPanicChunkError));
sl@0: 	iPageMask = iPageSize - 1; // assume page size is a power of 2
sl@0: 	__ASSERT_ALWAYS(KFbServLargeChunkMinPhysicalSize > 0, Panic(EFbsPanicChunkError));
sl@0: 	User::LeaveIfError(iChunk.Commit(iPageSize, KFbServLargeChunkMinPhysicalSize));
sl@0: 	iSmallCells.AppendL(iChunk.Base() + iPageSize); // prevent a data offset of 0 from chunk base
sl@0: 	iSmallCells.AppendL(iChunk.Base() + iPageSize + KFbServLargeChunkMinPhysicalSize);
sl@0: 	iFreeSmallCellLinks.AppendL(0);
sl@0: 	iLargeSectionBottom = iChunk.MaxSize() >> KFbServLargeChunkSizeShifter;
sl@0: 	iLargeCells.AppendL(iChunk.Base() + iLargeSectionBottom);
sl@0: 	iLargeCells.AppendL(iChunk.Base() + iChunk.MaxSize());
sl@0: 	iFreeLargeCellLinks.AppendL(0);
sl@0: 	User::LeaveIfError(iLock.CreateLocal());
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TUint8* CChunkPile::ChunkBase() const
sl@0: 	{
sl@0: 	return(iChunk.Base());
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TInt CChunkPile::VirtualSize()
sl@0: 	{
sl@0: 	TInt maxmem = 0;
sl@0: 	HAL::Get(HALData::EMemoryRAM, maxmem);
sl@0: 	ASSERT(maxmem > 0);
sl@0: 	return Min(Max(KFbServLargeChunkMinVirtualSize, maxmem << KFbServLargeChunkSizeShifter), KFbServLargeChunkMaxVirtualSize);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TUint8* CChunkPile::Alloc(TInt aSize)
sl@0: 	{
sl@0: 	__ASSERT_ALWAYS(aSize > 0 && aSize < KMaxTInt / 2, Panic(EFbsPanicChunkError));
sl@0: 	TUint8* cell;
sl@0: 	iLock.Wait();
sl@0: 	if (aSize < KMaxLargeBitmapAlloc)
sl@0: 		{
sl@0: 		aSize = Align4(aSize); // round size up to nearest four bytes
sl@0: 		TInt err = DoAlloc(cell, aSize, iSmallCells, iFreeSmallCellLinks, EFalse);
sl@0: 		if (err != KErrNone && cell != NULL)
sl@0: 			{
sl@0: 			// OOM after the small section grew? if so decommit as much physical memory as possible
sl@0: 			TInt topIndex = iSmallCells.Count() - 1;
sl@0: 			if (cell == iSmallCells[topIndex - 1])
sl@0: 				ShrinkSmallSection((iSmallCells[topIndex] - cell) & ~iPageMask);
sl@0: 			cell = NULL;
sl@0: 			}
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		aSize = (aSize + iPageMask) & ~iPageMask; // round size up to nearest page boundary
sl@0: 		TInt err = DoAlloc(cell, aSize, iLargeCells, iFreeLargeCellLinks, ETrue);
sl@0: 		if (err != KErrNone && cell != NULL)
sl@0: 			{
sl@0: 			iChunk.Decommit(cell - iChunk.Base(), aSize);
sl@0: 			cell = NULL;
sl@0: 			}
sl@0: 		}
sl@0: 	iLock.Signal();
sl@0: 	return cell;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void CChunkPile::Free(TAny* aCell)
sl@0: 	{
sl@0: 	iLock.Wait();
sl@0: 	if (static_cast<TUint8*>(aCell) < iChunk.Base() + iLargeSectionBottom)
sl@0: 		DoFree(static_cast<TUint8*>(aCell), iSmallCells, iFreeSmallCellLinks, EFalse);
sl@0: 	else
sl@0: 		DoFree(static_cast<TUint8*>(aCell), iLargeCells, iFreeLargeCellLinks, ETrue);
sl@0: 	iLock.Signal();
sl@0: 	}
sl@0: 
sl@0: TInt CChunkPile::DoAlloc(TUint8*& aCell, TInt aSize, RPointerArray<TUint8>& aCells, RArray<TInt>& aFreeCellLinks, TBool aLarge)
sl@0: /*
sl@0: This function tries to allocate a cell of aSize bytes and returns its address in aCell if successful.
sl@0: In case of failure aCell is either NULL, if there is not enough memory for a cell of that size,
sl@0: or it contains the address of a free cell of at least aSize bytes,
sl@0: if there is not enough memory for the internal structures used by CChunkPile.
sl@0: */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(aCells.Count() >= 2, Panic(EFbsPanicChunkError));
sl@0: 	aCell = NULL;
sl@0: 	TInt cellIndex = 0;
sl@0: 	TInt freeCount = aFreeCellLinks.Count();
sl@0: 	for (TInt freeIndex = 0; freeIndex < freeCount; ++freeIndex)
sl@0: 		{
sl@0: 		TInt freeCellLink = aFreeCellLinks[freeIndex];
sl@0: 		cellIndex += freeCellLink;
sl@0: 		TInt size = aCells[cellIndex + 1] - aCells[cellIndex];
sl@0: 		if (size >= aSize)
sl@0: 			{
sl@0: 			if (aLarge)
sl@0: 				{
sl@0: 				TInt err = iChunk.Commit(aCells[cellIndex] - iChunk.Base(), aSize);
sl@0: 				if (err != KErrNone)
sl@0: 					return err;
sl@0: 				}
sl@0: 			aCell = aCells[cellIndex];
sl@0: 			if (size == aSize) // exact fit?
sl@0: 				{
sl@0: 				aFreeCellLinks.Remove(freeIndex);
sl@0: 				if (freeIndex < aFreeCellLinks.Count())
sl@0: 					aFreeCellLinks[freeIndex] += freeCellLink;
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				// make sure there are always enough empty slots in aFreeCellLinks
sl@0: 				TInt err = aFreeCellLinks.Reserve(GranularRoundUp((aCells.Count() + 1) >> 1));
sl@0: 				if (err != KErrNone)
sl@0: 					return err;
sl@0: 				err = aCells.Insert(aCell + aSize, cellIndex + 1);
sl@0: 				if (err != KErrNone)
sl@0: 					return err;
sl@0: 				++aFreeCellLinks[freeIndex];
sl@0: 				}
sl@0: 			return KErrNone;
sl@0: 			}
sl@0: 		}
sl@0: 	if (aLarge)
sl@0: 		return KErrNoMemory;
sl@0: 	TInt err = GrowSmallSection(aSize, cellIndex);
sl@0: 	if (err != KErrNone)
sl@0: 		return err;
sl@0: 	TInt topIndex = iSmallCells.Count() - 1;
sl@0: 	aCell = iSmallCells[topIndex - 1];
sl@0: 	if (iSmallCells[topIndex] - aCell == aSize) // exact fit?
sl@0: 		{
sl@0: 		iFreeSmallCellLinks.Remove(iFreeSmallCellLinks.Count() - 1);
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		// make sure there are always enough empty slots in aFreeCellLinks
sl@0: 		err = iFreeSmallCellLinks.Reserve(GranularRoundUp((iSmallCells.Count() + 1) >> 1));
sl@0: 		if (err != KErrNone)
sl@0: 			return err;
sl@0: 		err = iSmallCells.Insert(aCell + aSize, topIndex);
sl@0: 		if (err != KErrNone)
sl@0: 			return err;
sl@0: 		++iFreeSmallCellLinks[iFreeSmallCellLinks.Count() - 1];
sl@0: 		}
sl@0: 	return KErrNone;
sl@0: 	}
sl@0: 
sl@0: void CChunkPile::DoFree(TUint8* aCell, RPointerArray<TUint8>& aCells, RArray<TInt>& aFreeCellLinks, TBool aLarge)
sl@0: 	{
sl@0: 	TInt cellIndex = aCells.FindInAddressOrder(aCell);
sl@0: 	__ASSERT_DEBUG(cellIndex >= 0 && cellIndex < aCells.Count() - 1, Panic(EFbsPanicChunkError));
sl@0: 	if (cellIndex < 0 || cellIndex == aCells.Count() - 1)
sl@0: 		return;
sl@0: 	TInt prevIndex = KMaxTInt;
sl@0: 	TInt nextIndex = 0;
sl@0: 	TInt freeCount = aFreeCellLinks.Count();
sl@0: 	TInt freeIndex;
sl@0: 	for (freeIndex = 0; freeIndex < freeCount; ++freeIndex)
sl@0: 		{
sl@0: 		nextIndex += aFreeCellLinks[freeIndex];
sl@0: 		if (nextIndex >= cellIndex)
sl@0: 			{
sl@0: 			__ASSERT_DEBUG(nextIndex > cellIndex, Panic(EFbsPanicChunkError));
sl@0: 			if (nextIndex == cellIndex)
sl@0: 				return;
sl@0: 			break;
sl@0: 			}
sl@0: 		prevIndex = nextIndex;
sl@0: 		}
sl@0: 	if (aLarge)
sl@0: 		iChunk.Decommit(aCell - iChunk.Base(), aCells[cellIndex + 1] - aCell);
sl@0: 	if (prevIndex == cellIndex - 1 && nextIndex == cellIndex + 1)
sl@0: 		{
sl@0: 		aFreeCellLinks.Remove(freeIndex);
sl@0: 		aCells.Remove(cellIndex + 1);
sl@0: 		aCells.Remove(cellIndex--);
sl@0: 		}
sl@0: 	else if (prevIndex == cellIndex - 1)
sl@0: 		{
sl@0: 		if (freeIndex < freeCount)
sl@0: 			--aFreeCellLinks[freeIndex];
sl@0: 		aCells.Remove(cellIndex--);
sl@0: 		}
sl@0: 	else if (nextIndex == cellIndex + 1)
sl@0: 		{
sl@0: 		--aFreeCellLinks[freeIndex];
sl@0: 		aCells.Remove(cellIndex + 1);
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		if (freeIndex < freeCount)
sl@0: 			aFreeCellLinks[freeIndex] = nextIndex - cellIndex;
sl@0: 		aFreeCellLinks.Insert(freeIndex > 0 ? cellIndex - prevIndex : cellIndex, freeIndex); // can't fail
sl@0: 		}
sl@0: 	if (aLarge)
sl@0: 		return;
sl@0: 	TInt topIndex = aCells.Count() - 1;
sl@0: 	if (cellIndex == topIndex - 1)
sl@0: 		{
sl@0: 		// last cell is free and has just grown, shrink with granularity iPageSize << KFbServLargeChunkGrowByShifter
sl@0: 		TInt roundMask = (iPageSize << KFbServLargeChunkGrowByShifter) - 1;
sl@0: 		ShrinkSmallSection((aCells[topIndex] - aCells[cellIndex]) & ~roundMask);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TInt CChunkPile::GrowSmallSection(TInt aSize, TInt aLastFreeCell)
sl@0: /*
sl@0: This function tries to grow the section for small cells with granularity iPageSize << KFbServLargeChunkGrowByShifter.
sl@0: It appends or expands the last free cell so that it has at least aSize bytes if successful.
sl@0: aLastFreeCell must be the index of the last free cell in the small section or 0 if there is none.
sl@0: */
sl@0: 	{
sl@0: 	TInt roundMask = (iPageSize << KFbServLargeChunkGrowByShifter) - 1;
sl@0: 	TInt topIndex = iSmallCells.Count() - 1;
sl@0: 	TInt maxGrowBy = (iChunk.Base() + iLargeSectionBottom) - iSmallCells[topIndex];
sl@0: 	__ASSERT_DEBUG(maxGrowBy >= 0, Panic(EFbsPanicChunkError));
sl@0: 	if (iFreeSmallCellLinks.Count() > 0 && aLastFreeCell == topIndex - 1)
sl@0: 		{
sl@0: 		// last cell is free
sl@0: 		TInt growBy = (iSmallCells[aLastFreeCell] + aSize) - iSmallCells[topIndex];
sl@0: 		__ASSERT_DEBUG(growBy > 0, Panic(EFbsPanicChunkError));
sl@0: 		if (growBy > maxGrowBy)
sl@0: 			return KErrNoMemory;
sl@0: 		growBy = Min((growBy + roundMask) & ~roundMask, maxGrowBy);
sl@0: 		TInt err = iChunk.Commit(iSmallCells[topIndex] - iChunk.Base(), growBy);
sl@0: 		if (err != KErrNone)
sl@0: 			return err;
sl@0: 		iSmallCells[topIndex] += growBy;
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		// last cell is not free
sl@0: 		if (aSize > maxGrowBy)
sl@0: 			return KErrNoMemory;
sl@0: 		TInt growBy = Min((aSize + roundMask) & ~roundMask, maxGrowBy);
sl@0: 		TInt err = iSmallCells.Reserve(GranularRoundUp(iSmallCells.Count() + 1));
sl@0: 		if (err != KErrNone)
sl@0: 			return err;
sl@0: 		err = iFreeSmallCellLinks.Reserve(GranularRoundUp((iSmallCells.Count() + 1) >> 1));
sl@0: 		if (err != KErrNone)
sl@0: 			return err;
sl@0: 		err = iChunk.Commit(iSmallCells[topIndex] - iChunk.Base(), growBy);
sl@0: 		if (err != KErrNone)
sl@0: 			return err;
sl@0: 		iSmallCells.Append(iSmallCells[topIndex] + growBy); // can't fail
sl@0: 		iFreeSmallCellLinks.Append(topIndex - aLastFreeCell); // can't fail
sl@0: 		}
sl@0: 	return KErrNone;
sl@0: 	}
sl@0: 
sl@0: void CChunkPile::ShrinkSmallSection(TInt aShrinkBy)
sl@0: 	{
sl@0: 	TInt topIndex = iSmallCells.Count() - 1;
sl@0: 	TInt maxShrinkBy = (iSmallCells[topIndex] - iChunk.Base()) - (KFbServLargeChunkMinPhysicalSize + iPageSize);
sl@0: 	__ASSERT_DEBUG(maxShrinkBy >= 0, Panic(EFbsPanicChunkError));
sl@0: 	aShrinkBy = Min(aShrinkBy, maxShrinkBy);
sl@0: 	if (aShrinkBy > 0)
sl@0: 		{
sl@0: 		iChunk.Decommit((iSmallCells[topIndex] -= aShrinkBy) - iChunk.Base(), aShrinkBy);
sl@0: 		if (iSmallCells[topIndex] == iSmallCells[topIndex - 1])
sl@0: 			{
sl@0: 			iSmallCells.Remove(topIndex);
sl@0: 			iFreeSmallCellLinks.Remove(iFreeSmallCellLinks.Count() - 1);
sl@0: 			}
sl@0: 		}
sl@0: 	}