os/graphics/fbs/fontandbitmapserver/sfbs/PILE.CPP
changeset 0 bde4ae8d615e
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/os/graphics/fbs/fontandbitmapserver/sfbs/PILE.CPP	Fri Jun 15 03:10:57 2012 +0200
     1.3 @@ -0,0 +1,315 @@
     1.4 +// Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).
     1.5 +// All rights reserved.
     1.6 +// This component and the accompanying materials are made available
     1.7 +// under the terms of "Eclipse Public License v1.0"
     1.8 +// which accompanies this distribution, and is available
     1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
    1.10 +//
    1.11 +// Initial Contributors:
    1.12 +// Nokia Corporation - initial contribution.
    1.13 +//
    1.14 +// Contributors:
    1.15 +//
    1.16 +// Description:
    1.17 +//
    1.18 +
    1.19 +#include <hal.h>
    1.20 +#include <fbs.h>
    1.21 +#include <bitmap.h>
    1.22 +#include "UTILS.H"
    1.23 +
    1.24 +
    1.25 +GLREF_C void Panic(TFbsPanic aPanic);
    1.26 +
    1.27 +LOCAL_C TInt GranularRoundUp(TInt aCount)
    1.28 +	{
    1.29 +	return (aCount + 7) & ~7;
    1.30 +	}
    1.31 +
    1.32 +CChunkPile::CChunkPile(const RChunk& aChunk)
    1.33 +:	iChunk(aChunk)
    1.34 +	{}
    1.35 +
    1.36 +EXPORT_C CChunkPile::~CChunkPile()
    1.37 +	{
    1.38 +	iChunk.Close();
    1.39 +	iSmallCells.Close();
    1.40 +	iFreeSmallCellLinks.Close();
    1.41 +	iLargeCells.Close();
    1.42 +	iFreeLargeCellLinks.Close();
    1.43 +	iLock.Close();
    1.44 +	}
    1.45 +
    1.46 +EXPORT_C CChunkPile* CChunkPile::NewL(const RChunk& aChunk)
    1.47 +	{
    1.48 +	CChunkPile* thisptr=new(ELeave) CChunkPile(aChunk);
    1.49 +	CleanupStack::PushL(thisptr);
    1.50 +	thisptr->ConstructL();
    1.51 +	CleanupStack::Pop();
    1.52 +	return(thisptr);
    1.53 +	}
    1.54 +
    1.55 +void CChunkPile::ConstructL()
    1.56 +	{
    1.57 +	TInt ret = iChunk.Duplicate(RThread());
    1.58 +	__ASSERT_ALWAYS(ret == KErrNone, Panic(EFbsPanicChunkError));
    1.59 +	HAL::Get(HAL::EMemoryPageSize, iPageSize);
    1.60 +	__ASSERT_ALWAYS(iPageSize > 4, Panic(EFbsPanicChunkError));
    1.61 +	iPageMask = iPageSize - 1; // assume page size is a power of 2
    1.62 +	__ASSERT_ALWAYS(KFbServLargeChunkMinPhysicalSize > 0, Panic(EFbsPanicChunkError));
    1.63 +	User::LeaveIfError(iChunk.Commit(iPageSize, KFbServLargeChunkMinPhysicalSize));
    1.64 +	iSmallCells.AppendL(iChunk.Base() + iPageSize); // prevent a data offset of 0 from chunk base
    1.65 +	iSmallCells.AppendL(iChunk.Base() + iPageSize + KFbServLargeChunkMinPhysicalSize);
    1.66 +	iFreeSmallCellLinks.AppendL(0);
    1.67 +	iLargeSectionBottom = iChunk.MaxSize() >> KFbServLargeChunkSizeShifter;
    1.68 +	iLargeCells.AppendL(iChunk.Base() + iLargeSectionBottom);
    1.69 +	iLargeCells.AppendL(iChunk.Base() + iChunk.MaxSize());
    1.70 +	iFreeLargeCellLinks.AppendL(0);
    1.71 +	User::LeaveIfError(iLock.CreateLocal());
    1.72 +	}
    1.73 +
    1.74 +EXPORT_C TUint8* CChunkPile::ChunkBase() const
    1.75 +	{
    1.76 +	return(iChunk.Base());
    1.77 +	}
    1.78 +
    1.79 +EXPORT_C TInt CChunkPile::VirtualSize()
    1.80 +	{
    1.81 +	TInt maxmem = 0;
    1.82 +	HAL::Get(HALData::EMemoryRAM, maxmem);
    1.83 +	ASSERT(maxmem > 0);
    1.84 +	return Min(Max(KFbServLargeChunkMinVirtualSize, maxmem << KFbServLargeChunkSizeShifter), KFbServLargeChunkMaxVirtualSize);
    1.85 +	}
    1.86 +
    1.87 +EXPORT_C TUint8* CChunkPile::Alloc(TInt aSize)
    1.88 +	{
    1.89 +	__ASSERT_ALWAYS(aSize > 0 && aSize < KMaxTInt / 2, Panic(EFbsPanicChunkError));
    1.90 +	TUint8* cell;
    1.91 +	iLock.Wait();
    1.92 +	if (aSize < KMaxLargeBitmapAlloc)
    1.93 +		{
    1.94 +		aSize = Align4(aSize); // round size up to nearest four bytes
    1.95 +		TInt err = DoAlloc(cell, aSize, iSmallCells, iFreeSmallCellLinks, EFalse);
    1.96 +		if (err != KErrNone && cell != NULL)
    1.97 +			{
    1.98 +			// OOM after the small section grew? if so decommit as much physical memory as possible
    1.99 +			TInt topIndex = iSmallCells.Count() - 1;
   1.100 +			if (cell == iSmallCells[topIndex - 1])
   1.101 +				ShrinkSmallSection((iSmallCells[topIndex] - cell) & ~iPageMask);
   1.102 +			cell = NULL;
   1.103 +			}
   1.104 +		}
   1.105 +	else
   1.106 +		{
   1.107 +		aSize = (aSize + iPageMask) & ~iPageMask; // round size up to nearest page boundary
   1.108 +		TInt err = DoAlloc(cell, aSize, iLargeCells, iFreeLargeCellLinks, ETrue);
   1.109 +		if (err != KErrNone && cell != NULL)
   1.110 +			{
   1.111 +			iChunk.Decommit(cell - iChunk.Base(), aSize);
   1.112 +			cell = NULL;
   1.113 +			}
   1.114 +		}
   1.115 +	iLock.Signal();
   1.116 +	return cell;
   1.117 +	}
   1.118 +
   1.119 +EXPORT_C void CChunkPile::Free(TAny* aCell)
   1.120 +	{
   1.121 +	iLock.Wait();
   1.122 +	if (static_cast<TUint8*>(aCell) < iChunk.Base() + iLargeSectionBottom)
   1.123 +		DoFree(static_cast<TUint8*>(aCell), iSmallCells, iFreeSmallCellLinks, EFalse);
   1.124 +	else
   1.125 +		DoFree(static_cast<TUint8*>(aCell), iLargeCells, iFreeLargeCellLinks, ETrue);
   1.126 +	iLock.Signal();
   1.127 +	}
   1.128 +
   1.129 +TInt CChunkPile::DoAlloc(TUint8*& aCell, TInt aSize, RPointerArray<TUint8>& aCells, RArray<TInt>& aFreeCellLinks, TBool aLarge)
   1.130 +/*
   1.131 +This function tries to allocate a cell of aSize bytes and returns its address in aCell if successful.
   1.132 +In case of failure aCell is either NULL, if there is not enough memory for a cell of that size,
   1.133 +or it contains the address of a free cell of at least aSize bytes,
   1.134 +if there is not enough memory for the internal structures used by CChunkPile.
   1.135 +*/
   1.136 +	{
   1.137 +	__ASSERT_DEBUG(aCells.Count() >= 2, Panic(EFbsPanicChunkError));
   1.138 +	aCell = NULL;
   1.139 +	TInt cellIndex = 0;
   1.140 +	TInt freeCount = aFreeCellLinks.Count();
   1.141 +	for (TInt freeIndex = 0; freeIndex < freeCount; ++freeIndex)
   1.142 +		{
   1.143 +		TInt freeCellLink = aFreeCellLinks[freeIndex];
   1.144 +		cellIndex += freeCellLink;
   1.145 +		TInt size = aCells[cellIndex + 1] - aCells[cellIndex];
   1.146 +		if (size >= aSize)
   1.147 +			{
   1.148 +			if (aLarge)
   1.149 +				{
   1.150 +				TInt err = iChunk.Commit(aCells[cellIndex] - iChunk.Base(), aSize);
   1.151 +				if (err != KErrNone)
   1.152 +					return err;
   1.153 +				}
   1.154 +			aCell = aCells[cellIndex];
   1.155 +			if (size == aSize) // exact fit?
   1.156 +				{
   1.157 +				aFreeCellLinks.Remove(freeIndex);
   1.158 +				if (freeIndex < aFreeCellLinks.Count())
   1.159 +					aFreeCellLinks[freeIndex] += freeCellLink;
   1.160 +				}
   1.161 +			else
   1.162 +				{
   1.163 +				// make sure there are always enough empty slots in aFreeCellLinks
   1.164 +				TInt err = aFreeCellLinks.Reserve(GranularRoundUp((aCells.Count() + 1) >> 1));
   1.165 +				if (err != KErrNone)
   1.166 +					return err;
   1.167 +				err = aCells.Insert(aCell + aSize, cellIndex + 1);
   1.168 +				if (err != KErrNone)
   1.169 +					return err;
   1.170 +				++aFreeCellLinks[freeIndex];
   1.171 +				}
   1.172 +			return KErrNone;
   1.173 +			}
   1.174 +		}
   1.175 +	if (aLarge)
   1.176 +		return KErrNoMemory;
   1.177 +	TInt err = GrowSmallSection(aSize, cellIndex);
   1.178 +	if (err != KErrNone)
   1.179 +		return err;
   1.180 +	TInt topIndex = iSmallCells.Count() - 1;
   1.181 +	aCell = iSmallCells[topIndex - 1];
   1.182 +	if (iSmallCells[topIndex] - aCell == aSize) // exact fit?
   1.183 +		{
   1.184 +		iFreeSmallCellLinks.Remove(iFreeSmallCellLinks.Count() - 1);
   1.185 +		}
   1.186 +	else
   1.187 +		{
   1.188 +		// make sure there are always enough empty slots in aFreeCellLinks
   1.189 +		err = iFreeSmallCellLinks.Reserve(GranularRoundUp((iSmallCells.Count() + 1) >> 1));
   1.190 +		if (err != KErrNone)
   1.191 +			return err;
   1.192 +		err = iSmallCells.Insert(aCell + aSize, topIndex);
   1.193 +		if (err != KErrNone)
   1.194 +			return err;
   1.195 +		++iFreeSmallCellLinks[iFreeSmallCellLinks.Count() - 1];
   1.196 +		}
   1.197 +	return KErrNone;
   1.198 +	}
   1.199 +
   1.200 +void CChunkPile::DoFree(TUint8* aCell, RPointerArray<TUint8>& aCells, RArray<TInt>& aFreeCellLinks, TBool aLarge)
   1.201 +	{
   1.202 +	TInt cellIndex = aCells.FindInAddressOrder(aCell);
   1.203 +	__ASSERT_DEBUG(cellIndex >= 0 && cellIndex < aCells.Count() - 1, Panic(EFbsPanicChunkError));
   1.204 +	if (cellIndex < 0 || cellIndex == aCells.Count() - 1)
   1.205 +		return;
   1.206 +	TInt prevIndex = KMaxTInt;
   1.207 +	TInt nextIndex = 0;
   1.208 +	TInt freeCount = aFreeCellLinks.Count();
   1.209 +	TInt freeIndex;
   1.210 +	for (freeIndex = 0; freeIndex < freeCount; ++freeIndex)
   1.211 +		{
   1.212 +		nextIndex += aFreeCellLinks[freeIndex];
   1.213 +		if (nextIndex >= cellIndex)
   1.214 +			{
   1.215 +			__ASSERT_DEBUG(nextIndex > cellIndex, Panic(EFbsPanicChunkError));
   1.216 +			if (nextIndex == cellIndex)
   1.217 +				return;
   1.218 +			break;
   1.219 +			}
   1.220 +		prevIndex = nextIndex;
   1.221 +		}
   1.222 +	if (aLarge)
   1.223 +		iChunk.Decommit(aCell - iChunk.Base(), aCells[cellIndex + 1] - aCell);
   1.224 +	if (prevIndex == cellIndex - 1 && nextIndex == cellIndex + 1)
   1.225 +		{
   1.226 +		aFreeCellLinks.Remove(freeIndex);
   1.227 +		aCells.Remove(cellIndex + 1);
   1.228 +		aCells.Remove(cellIndex--);
   1.229 +		}
   1.230 +	else if (prevIndex == cellIndex - 1)
   1.231 +		{
   1.232 +		if (freeIndex < freeCount)
   1.233 +			--aFreeCellLinks[freeIndex];
   1.234 +		aCells.Remove(cellIndex--);
   1.235 +		}
   1.236 +	else if (nextIndex == cellIndex + 1)
   1.237 +		{
   1.238 +		--aFreeCellLinks[freeIndex];
   1.239 +		aCells.Remove(cellIndex + 1);
   1.240 +		}
   1.241 +	else
   1.242 +		{
   1.243 +		if (freeIndex < freeCount)
   1.244 +			aFreeCellLinks[freeIndex] = nextIndex - cellIndex;
   1.245 +		aFreeCellLinks.Insert(freeIndex > 0 ? cellIndex - prevIndex : cellIndex, freeIndex); // can't fail
   1.246 +		}
   1.247 +	if (aLarge)
   1.248 +		return;
   1.249 +	TInt topIndex = aCells.Count() - 1;
   1.250 +	if (cellIndex == topIndex - 1)
   1.251 +		{
   1.252 +		// last cell is free and has just grown, shrink with granularity iPageSize << KFbServLargeChunkGrowByShifter
   1.253 +		TInt roundMask = (iPageSize << KFbServLargeChunkGrowByShifter) - 1;
   1.254 +		ShrinkSmallSection((aCells[topIndex] - aCells[cellIndex]) & ~roundMask);
   1.255 +		}
   1.256 +	}
   1.257 +
   1.258 +TInt CChunkPile::GrowSmallSection(TInt aSize, TInt aLastFreeCell)
   1.259 +/*
   1.260 +This function tries to grow the section for small cells with granularity iPageSize << KFbServLargeChunkGrowByShifter.
   1.261 +It appends or expands the last free cell so that it has at least aSize bytes if successful.
   1.262 +aLastFreeCell must be the index of the last free cell in the small section or 0 if there is none.
   1.263 +*/
   1.264 +	{
   1.265 +	TInt roundMask = (iPageSize << KFbServLargeChunkGrowByShifter) - 1;
   1.266 +	TInt topIndex = iSmallCells.Count() - 1;
   1.267 +	TInt maxGrowBy = (iChunk.Base() + iLargeSectionBottom) - iSmallCells[topIndex];
   1.268 +	__ASSERT_DEBUG(maxGrowBy >= 0, Panic(EFbsPanicChunkError));
   1.269 +	if (iFreeSmallCellLinks.Count() > 0 && aLastFreeCell == topIndex - 1)
   1.270 +		{
   1.271 +		// last cell is free
   1.272 +		TInt growBy = (iSmallCells[aLastFreeCell] + aSize) - iSmallCells[topIndex];
   1.273 +		__ASSERT_DEBUG(growBy > 0, Panic(EFbsPanicChunkError));
   1.274 +		if (growBy > maxGrowBy)
   1.275 +			return KErrNoMemory;
   1.276 +		growBy = Min((growBy + roundMask) & ~roundMask, maxGrowBy);
   1.277 +		TInt err = iChunk.Commit(iSmallCells[topIndex] - iChunk.Base(), growBy);
   1.278 +		if (err != KErrNone)
   1.279 +			return err;
   1.280 +		iSmallCells[topIndex] += growBy;
   1.281 +		}
   1.282 +	else
   1.283 +		{
   1.284 +		// last cell is not free
   1.285 +		if (aSize > maxGrowBy)
   1.286 +			return KErrNoMemory;
   1.287 +		TInt growBy = Min((aSize + roundMask) & ~roundMask, maxGrowBy);
   1.288 +		TInt err = iSmallCells.Reserve(GranularRoundUp(iSmallCells.Count() + 1));
   1.289 +		if (err != KErrNone)
   1.290 +			return err;
   1.291 +		err = iFreeSmallCellLinks.Reserve(GranularRoundUp((iSmallCells.Count() + 1) >> 1));
   1.292 +		if (err != KErrNone)
   1.293 +			return err;
   1.294 +		err = iChunk.Commit(iSmallCells[topIndex] - iChunk.Base(), growBy);
   1.295 +		if (err != KErrNone)
   1.296 +			return err;
   1.297 +		iSmallCells.Append(iSmallCells[topIndex] + growBy); // can't fail
   1.298 +		iFreeSmallCellLinks.Append(topIndex - aLastFreeCell); // can't fail
   1.299 +		}
   1.300 +	return KErrNone;
   1.301 +	}
   1.302 +
   1.303 +void CChunkPile::ShrinkSmallSection(TInt aShrinkBy)
   1.304 +	{
   1.305 +	TInt topIndex = iSmallCells.Count() - 1;
   1.306 +	TInt maxShrinkBy = (iSmallCells[topIndex] - iChunk.Base()) - (KFbServLargeChunkMinPhysicalSize + iPageSize);
   1.307 +	__ASSERT_DEBUG(maxShrinkBy >= 0, Panic(EFbsPanicChunkError));
   1.308 +	aShrinkBy = Min(aShrinkBy, maxShrinkBy);
   1.309 +	if (aShrinkBy > 0)
   1.310 +		{
   1.311 +		iChunk.Decommit((iSmallCells[topIndex] -= aShrinkBy) - iChunk.Base(), aShrinkBy);
   1.312 +		if (iSmallCells[topIndex] == iSmallCells[topIndex - 1])
   1.313 +			{
   1.314 +			iSmallCells.Remove(topIndex);
   1.315 +			iFreeSmallCellLinks.Remove(iFreeSmallCellLinks.Count() - 1);
   1.316 +			}
   1.317 +		}
   1.318 +	}