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 + }