1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kernel/eka/klib/bma.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,800 @@
1.4 +// Copyright (c) 1994-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 the License "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 +// e32\klib\bma.cpp
1.18 +// This file is directly included in the test harness t_tbma
1.19 +//
1.20 +//
1.21 +
1.22 +#include <kernel/kbma.h>
1.23 +
1.24 +#ifdef TBMA_TEST_CODE
1.25 +
1.26 +#ifdef __MARM__
1.27 +#define __TBMA_MACHINE_CODED__
1.28 +#endif
1.29 +
1.30 +#include <e32std.h>
1.31 +#include <e32std_private.h>
1.32 +#include <e32atomics.h>
1.33 +
1.34 +#define __ALLOC(x) User::Alloc(x)
1.35 +
1.36 +void TBmaFault(TInt aLine)
1.37 + {
1.38 + User::Panic(_L("TBMA"),aLine);
1.39 + }
1.40 +
1.41 +#else
1.42 +
1.43 +#include <kernel/kern_priv.h>
1.44 +
1.45 +#define __ALLOC(x) Kern::Alloc(x)
1.46 +
1.47 +void TBmaFault(TInt aLine)
1.48 + {
1.49 + Kern::Fault("TBMA",aLine);
1.50 + }
1.51 +
1.52 +#endif
1.53 +
1.54 +#define TBMA_FAULT() TBmaFault(__LINE__)
1.55 +
1.56 +/** Creates a new TBitMapAllocator object.
1.57 +
1.58 + @param aSize The number of bit positions required, must be >0.
1.59 + @param aState TRUE if all bit positions initially free
1.60 + FALSE if all bit positions initially allocated.
1.61 +
1.62 + @return Pointer to new object, NULL if out of memory.
1.63 +
1.64 + @pre Calling thread must be in a critical section.
1.65 + @pre No fast mutex can be held.
1.66 + @pre Call in a thread context.
1.67 + @pre Interrupts must be enabled.
1.68 + @pre Kernel must be unlocked.
1.69 + */
1.70 +EXPORT_C TBitMapAllocator* TBitMapAllocator::New(TInt aSize, TBool aState)
1.71 + {
1.72 + #ifndef TBMA_TEST_CODE
1.73 + CHECK_PRECONDITIONS(MASK_THREAD_CRITICAL,"TBitMapAllocator::New");
1.74 + #endif
1.75 + TInt nmapw=(aSize+31)>>5;
1.76 + TInt memsz=sizeof(TBitMapAllocator)+(nmapw-1)*sizeof(TUint32);
1.77 + TBitMapAllocator* pA=(TBitMapAllocator*)__ALLOC(memsz);
1.78 + if (pA)
1.79 + new(pA) TBitMapAllocator(aSize, aState);
1.80 + return pA;
1.81 + }
1.82 +
1.83 +
1.84 +/** Finds a set of consecutive bit positions with specified alignment, with
1.85 + support for chaining multiple allocators.
1.86 +
1.87 + Note that this function does not mark the positions as allocated.
1.88 +
1.89 + In first fit mode:
1.90 + 1. Any initial run is added to the carry in
1.91 + 2. If all bits free, if BMA size+carry<=request length return 0 and leave carry alone
1.92 + else add size to carry and return KErrOverflow
1.93 + 3. If request satisfied by initial run + carry return 0 and leave carry alone
1.94 + 4. If request satisfied by an intermediate or final run, return start pos of run and set carry=0
1.95 + 5. Otherwise carry = length of any final run and return KErrNotFound
1.96 +
1.97 + With a single allocator set aCarry (and usually aBase) to zero and ignore
1.98 + aRunLength. The return value then indicates the required position (after
1.99 + being aligned up as necessary) or KErrNotFound.
1.100 +
1.101 + With multiple allocators, this function should be called on each allocator in
1.102 + increasing logical bit number order. The carry should be set to zero initially
1.103 + and if there is a gap in the logical bit number between two allocators, otherwise
1.104 + it should be left alone. The first call which returns a nonnegative value indicates
1.105 + success and the required logical bit position is given by aligning up
1.106 + logical bit number of first bit of allocator + return value - carry
1.107 +
1.108 + In best fit mode:
1.109 + 1. Any initial run is added to the carry in
1.110 + 2. If all bits free, add bma length to carry and return KErrOverflow
1.111 + 3. If any run including initial+carry but not final has length >= request length
1.112 + return start pos and length of smallest such, also set carry = length of final run
1.113 + unless exact match found, when carry is either unchanged or set to 0
1.114 + 4. If only final run large enough, return KErrNotFound and set carry = length of final run
1.115 + carry=0 if no final run
1.116 +
1.117 + Here is an example of how to use this for multiple allocators:
1.118 + @code
1.119 + // aLength = run length required, aAlign = alignment constraint
1.120 + TInt bmalen=0;
1.121 + TInt carry=0;
1.122 + TInt minrun=KMaxTInt; // this will track the length of the shortest useful run
1.123 + TInt minrunpos=KErrNotFound; // this will track the start position of the shortest useful run
1.124 + TUint32 alignsize=1<<aAlign;
1.125 + TUint32 alignmask=alignsize-1;
1.126 + TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
1.127 + TBitMapAllocator** pE=ppA+iNumBmas; // pointer to end of list
1.128 + TInt* pB=iBaseList; // pointer to list of initial logical bit numbers
1.129 + TInt base=*pB;
1.130 + for (; ppA<pE; ++ppA, ++pB)
1.131 + {
1.132 + TBitMapAllocator* pA=*ppA;
1.133 + if (*pB!=base+bmalen)
1.134 + {
1.135 + // this BMA is not contiguous with previous one
1.136 + // check final run of previous BMA
1.137 + if (carry<minrun)
1.138 + {
1.139 + TInt fpos=base+bmalen-carry;
1.140 + TInt lost=((fpos+base+alignmask)&~alignmask)-base-fpos;
1.141 + if (carry-lost>=aLength)
1.142 + {
1.143 + minrun=carry;
1.144 + minrunpos=fpos;
1.145 + }
1.146 + }
1.147 + carry=0;
1.148 + }
1.149 + base=*pB;
1.150 + bmalen=pA->iSize;
1.151 + TInt l=KMaxTInt;
1.152 + TInt oldc=carry; // need to save this for the case where the best run is the initial one
1.153 + TInt r=pA->AllocAligned(aLength,aAlign,base,ETrue,carry,l);
1.154 + if (r>=0)
1.155 + {
1.156 + // check shortest run in this BMA
1.157 + if (l<minrun)
1.158 + {
1.159 + minrun=l;
1.160 + minrunpos=r ? (base+r) : (base-oldc);
1.161 + if (minrun==aLength)
1.162 + break; // exact match so finish
1.163 + }
1.164 + }
1.165 + }
1.166 + // check final run of last BMA (unless exact match already found)
1.167 + if (ppA==pE && carry<minrun)
1.168 + {
1.169 + TInt fpos=base+bmalen-carry;
1.170 + TInt lost=((fpos+alignmask)&~alignmask)-fpos;
1.171 + if (carry-lost>=aLength)
1.172 + {
1.173 + minrun=carry;
1.174 + minrunpos=fpos;
1.175 + }
1.176 + }
1.177 + result = (minrunpos<0) ? minrunpos : ((minrunpos+alignmask)&~alignmask);
1.178 +
1.179 + @endcode
1.180 +
1.181 +
1.182 + @param aLength number of consecutive bit positions to allocate.
1.183 + @param aAlign logarithm to base 2 of the alignment required.
1.184 + @param aBase the alignment of the first bit of this allocator - only significant modulo 2^aAlign.
1.185 + @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit.
1.186 + @param aCarry carry in/carry out.
1.187 + @param aRunLength Holds best run length found so far. This will be set to KMaxTInt when no
1.188 + suitable run length has been found. In best fit mode aCarry should also be
1.189 + checked as aRunLength will not be set if aCarry is the only suitable run length
1.190 + found.
1.191 +
1.192 + @return Start position, if a suitable run was found;
1.193 + KErrNotFound, if no suitable run was found;
1.194 + KErrOverflow, if all positions free and best fit mode, or if all positions free
1.195 + in first fit mode and length requested > number of positions available.
1.196 +
1.197 + @see TBitMapAllocator::AllocConsecutive(TInt aLength, TBool aBestFit)
1.198 + @see TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit)
1.199 + */
1.200 +EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength) const
1.201 + {
1.202 + return AllocAligned(aLength, aAlign, aBase, aBestFit, aCarry, aRunLength, 0);
1.203 + }
1.204 +
1.205 +
1.206 +/** Allocates the next available bit position starting from the specified offset.
1.207 +
1.208 + Note - If no free bit positions can be found after aOffset this method will
1.209 + wrap around and continue the search from the start of the bit map.
1.210 +
1.211 + @param aOffset The offset from the start of the bit map.
1.212 + @return The number of the bit position allocated, -1 if all positions are occupied.
1.213 + */
1.214 +EXPORT_C TInt TBitMapAllocator::AllocFrom(TUint aOffset)
1.215 + {
1.216 + __ASSERT_ALWAYS(aOffset < (TUint)iSize, TBMA_FAULT());
1.217 +
1.218 + if (!iAvail)
1.219 + return -1;
1.220 + --iAvail;
1.221 + const TUint32* pEnd = iMap + ((iSize+31)>>5);
1.222 + TUint32* pW = iMap + (aOffset >> 5);
1.223 + // Only check the bits after aOffset in this word.
1.224 + TUint wordMask = 0xffffffffu >> (aOffset & 0x1f);
1.225 + #ifdef _DEBUG
1.226 + if(!((aOffset&0x1f)==0 || (wordMask&0x80000000u)==0)) // check compiler has done unsigned >>
1.227 + TBMA_FAULT();
1.228 + #endif
1.229 + TUint word = *pW & wordMask;
1.230 + // No free bit positions in this word so search through the rest of the words.
1.231 + while (!word)
1.232 + {
1.233 + ++pW;
1.234 + if (pW >= pEnd)
1.235 + pW = iMap;
1.236 + word = *pW;
1.237 + }
1.238 + TInt n = __e32_find_ms1_32(word);
1.239 + *pW &= ~(1 << n);
1.240 + n = (31 - n) + ((pW - iMap) << 5);
1.241 + return n;
1.242 + }
1.243 +
1.244 +
1.245 +#if !defined( __TBMA_MACHINE_CODED__) | defined(__EABI_CTORS__)
1.246 +/** Constructs a new TBitMapAllocator object.
1.247 +
1.248 + @param aSize The number of bit positions required.
1.249 + @param aState TRUE if all bit positions initially free;
1.250 + FALSE if all bit positions initially allocated.
1.251 + */
1.252 +EXPORT_C TBitMapAllocator::TBitMapAllocator(TInt aSize, TBool aState)
1.253 + {
1.254 + __ASSERT_ALWAYS(aSize>0, TBMA_FAULT());
1.255 + iSize=aSize;
1.256 + if (aState)
1.257 + {
1.258 + iCheckFirst=iMap;
1.259 + iAvail=aSize;
1.260 + TUint32* pW=iMap;
1.261 + for (; aSize>=32; aSize-=32)
1.262 + *pW++=0xffffffff;
1.263 + if (aSize)
1.264 + *pW=((0xffffffffu)<<(32-aSize));
1.265 + }
1.266 + else
1.267 + {
1.268 + TInt nmapw=(aSize+31)>>5;
1.269 + iAvail=0;
1.270 + iCheckFirst=iMap+nmapw-1;
1.271 + memclr(iMap, nmapw*sizeof(TUint32));
1.272 + }
1.273 + }
1.274 +#endif
1.275 +
1.276 +
1.277 +#if !defined( __TBMA_MACHINE_CODED__)
1.278 +/** Allocates the next available bit position.
1.279 +
1.280 + @return Number of position allocated, -1 if all positions occupied.
1.281 + */
1.282 +EXPORT_C TInt TBitMapAllocator::Alloc()
1.283 + {
1.284 + if (!iAvail)
1.285 + return -1;
1.286 + --iAvail;
1.287 + TUint32* pW=iCheckFirst;
1.288 + while (!*pW)
1.289 + ++pW;
1.290 + iCheckFirst=pW;
1.291 + TInt n=__e32_find_ms1_32(*pW);
1.292 + *pW &= ~(1<<n);
1.293 + n=(31-n)+((pW-iMap)<<5);
1.294 + return n;
1.295 + }
1.296 +
1.297 +
1.298 +/** Frees the specified bit position.
1.299 +
1.300 + @param aPos Number of bit position to be freed; must be currently allocated.
1.301 + */
1.302 +EXPORT_C void TBitMapAllocator::Free(TInt aPos)
1.303 + {
1.304 + __ASSERT_ALWAYS(TUint(aPos)<TUint(iSize), TBMA_FAULT());
1.305 + TUint32* pW=iMap+(aPos>>5);
1.306 + TUint32 b=0x80000000u>>(aPos&31);
1.307 + __ASSERT_ALWAYS(!(*pW & b), TBMA_FAULT());
1.308 + *pW |= b;
1.309 + ++iAvail;
1.310 + if (pW<iCheckFirst)
1.311 + iCheckFirst=pW;
1.312 + }
1.313 +
1.314 +
1.315 +/** Allocates a specific range of bit positions.
1.316 +
1.317 + The specified range must lie within the total range for this allocator and all
1.318 + the positions must currently be free.
1.319 +
1.320 + @param aStart First position to allocate.
1.321 + @param aLength Number of consecutive positions to allocate, must be >0.
1.322 + */
1.323 +EXPORT_C void TBitMapAllocator::Alloc(TInt aStart, TInt aLength)
1.324 + {
1.325 + __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
1.326 + __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
1.327 + __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
1.328 + TInt wix=aStart>>5;
1.329 + TInt sbit=aStart&31;
1.330 + TUint32* pW=iMap+wix;
1.331 + iAvail-=aLength;
1.332 + TInt ebit=sbit+aLength;
1.333 + if (ebit<32)
1.334 + {
1.335 + TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
1.336 + TUint32 w=*pW;
1.337 + __ASSERT_ALWAYS((w|b)==w, TBMA_FAULT());
1.338 + *pW=w&~b;
1.339 + return;
1.340 + }
1.341 + TUint32 b=(0xffffffffu>>sbit);
1.342 + while (ebit>0)
1.343 + {
1.344 + TUint32 w=*pW;
1.345 + __ASSERT_ALWAYS((w|b)==w, TBMA_FAULT());
1.346 + *pW++=w&~b;
1.347 + b=0xffffffffu;
1.348 + ebit-=32;
1.349 + if (ebit<32)
1.350 + b=~(b>>ebit);
1.351 + }
1.352 + }
1.353 +
1.354 +
1.355 +/** Frees a specific range of bit positions.
1.356 +
1.357 + The specified range must lie within the total range for this allocator and all
1.358 + the positions must currently be allocated.
1.359 +
1.360 + @param aStart First position to free.
1.361 + @param aLength Number of consecutive positions to free, must be >0.
1.362 + */
1.363 +EXPORT_C void TBitMapAllocator::Free(TInt aStart, TInt aLength)
1.364 + {
1.365 + __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
1.366 + __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
1.367 + __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
1.368 + TInt wix=aStart>>5;
1.369 + TInt sbit=aStart&31;
1.370 + TUint32* pW=iMap+wix;
1.371 + if (!iAvail || pW<iCheckFirst)
1.372 + iCheckFirst=pW;
1.373 + iAvail+=aLength;
1.374 + TInt ebit=sbit+aLength;
1.375 + if (ebit<32)
1.376 + {
1.377 + TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
1.378 + TUint32 w=*pW;
1.379 + __ASSERT_ALWAYS((w&b)==0, TBMA_FAULT());
1.380 + *pW=w|b;
1.381 + return;
1.382 + }
1.383 + TUint32 b=(0xffffffffu>>sbit);
1.384 + while (ebit>0)
1.385 + {
1.386 + TUint32 w=*pW;
1.387 + __ASSERT_ALWAYS((w&b)==0, TBMA_FAULT());
1.388 + *pW++=w|b;
1.389 + b=0xffffffffu;
1.390 + ebit-=32;
1.391 + if (ebit<32)
1.392 + b=~(b>>ebit);
1.393 + }
1.394 + }
1.395 +
1.396 +
1.397 +/** Frees a specific range of bit positions.
1.398 +
1.399 + The specified range must lie within the total range for this allocator but it is
1.400 + not necessary that all the positions are currently allocated.
1.401 +
1.402 + @param aStart First position to free.
1.403 + @param aLength Number of consecutive positions to free, must be >0.
1.404 + */
1.405 +EXPORT_C void TBitMapAllocator::SelectiveFree(TInt aStart, TInt aLength)
1.406 + {
1.407 + __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
1.408 + __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
1.409 + __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
1.410 + TInt wix=aStart>>5;
1.411 + TInt sbit=aStart&31;
1.412 + TUint32* pW=iMap+wix;
1.413 + if (!iAvail || pW<iCheckFirst)
1.414 + iCheckFirst=pW;
1.415 + iAvail+=aLength; // update free count assuming no positions already free
1.416 + TInt ebit=sbit+aLength;
1.417 + if (ebit<32)
1.418 + {
1.419 + TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
1.420 + TUint32 w=*pW;
1.421 + *pW=w|b; // mark all positions free
1.422 + iAvail-=__e32_bit_count_32(w&b); // reduce free count by number of positions already free
1.423 + return;
1.424 + }
1.425 + TUint32 b=(0xffffffffu>>sbit);
1.426 + while (ebit>0)
1.427 + {
1.428 + TUint32 w=*pW;
1.429 + *pW++=w|b; // mark all positions free
1.430 + iAvail-=__e32_bit_count_32(w&b); // reduce free count by number of positions already free
1.431 + b=0xffffffffu;
1.432 + ebit-=32;
1.433 + if (ebit<32)
1.434 + b=~(b>>ebit);
1.435 + }
1.436 + }
1.437 +
1.438 +
1.439 +/** Tests whether a specific range of bit positions are all free.
1.440 +
1.441 + The specified range must lie within the total range for this allocator.
1.442 +
1.443 + @param aStart First position to check.
1.444 + @param aLength Number of consecutive positions to check, must be >0.
1.445 +
1.446 + @return FALSE if all positions free, TRUE if at least one is occupied.
1.447 + */
1.448 +EXPORT_C TBool TBitMapAllocator::NotFree(TInt aStart, TInt aLength) const
1.449 + {
1.450 + // Inverse logic - returns 0 if all positions free, nonzero otherwise
1.451 + __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
1.452 + __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
1.453 + __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
1.454 + TInt wix=aStart>>5;
1.455 + TInt sbit=aStart&31;
1.456 + const TUint32* pW=iMap+wix;
1.457 + TInt ebit=sbit+aLength;
1.458 + if (ebit<32)
1.459 + {
1.460 + TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
1.461 + return (*pW^b)&b;
1.462 + }
1.463 + TUint32 b=(0xffffffffu>>sbit);
1.464 + TUint32 r=0;
1.465 + while (ebit>0)
1.466 + {
1.467 + r|=((*pW++^b)&b);
1.468 + b=0xffffffffu;
1.469 + ebit-=32;
1.470 + if (ebit<32)
1.471 + b=~(b>>ebit);
1.472 + }
1.473 + return r;
1.474 + }
1.475 +
1.476 +
1.477 +/** Tests whether a specific range of bit positions are all occupied.
1.478 +
1.479 + The specified range must lie within the total range for this allocator.
1.480 +
1.481 + @param aStart First position to check.
1.482 + @param aLength Number of consecutive positions to check, must be >0.
1.483 +
1.484 + @return FALSE if all positions occupied, TRUE if at least one is free.
1.485 + */
1.486 +EXPORT_C TBool TBitMapAllocator::NotAllocated(TInt aStart, TInt aLength) const
1.487 + {
1.488 + // Inverse logic - returns 0 if all positions allocated, nonzero otherwise
1.489 + __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
1.490 + __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
1.491 + __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
1.492 + TInt wix=aStart>>5;
1.493 + TInt sbit=aStart&31;
1.494 + const TUint32* pW=iMap+wix;
1.495 + TInt ebit=sbit+aLength;
1.496 + if (ebit<32)
1.497 + {
1.498 + TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
1.499 + return *pW&b;
1.500 + }
1.501 + TUint32 b=(0xffffffffu>>sbit);
1.502 + TUint32 r=0;
1.503 + while (ebit>0)
1.504 + {
1.505 + r|=(*pW++&b);
1.506 + b=0xffffffffu;
1.507 + ebit-=32;
1.508 + if (ebit<32)
1.509 + b=~(b>>ebit);
1.510 + }
1.511 + return r;
1.512 + }
1.513 +
1.514 +
1.515 +/** Allocates up to a specified number of available bit positions.
1.516 +
1.517 + The allocated positions are not required to bear any relationship to
1.518 + each other.
1.519 + If the number of free positions is less than the number requested,
1.520 + allocate all currently free positions.
1.521 +
1.522 + @param aLength Maximum number of positions to allocate.
1.523 + @param aList Pointer to memory area where allocated bit numbers should be stored.
1.524 +
1.525 + @return The number of positions allocated.
1.526 + */
1.527 +EXPORT_C TInt TBitMapAllocator::AllocList(TInt aLength, TInt* aList)
1.528 + {
1.529 + __ASSERT_ALWAYS(aLength>0, TBMA_FAULT());
1.530 + if (aLength>iAvail)
1.531 + aLength=iAvail;
1.532 + TInt c=aLength;
1.533 + while (c--)
1.534 + *aList++=Alloc();
1.535 + return aLength;
1.536 + }
1.537 +
1.538 +
1.539 +/** Finds a set of consecutive bit positions with specified alignment starting the
1.540 + search from the specfied bit position offset, with support for chaining
1.541 + multiple allocators.
1.542 +
1.543 + For further details see:
1.544 + TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength)
1.545 +
1.546 + @param aLength number of consecutive bit positions to allocate.
1.547 + @param aAlign logarithm to base 2 of the alignment required.
1.548 + @param aBase the alignment of the first bit of this allocator - only significant modulo 2^aAlign.
1.549 + @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit.
1.550 + @param aCarry carry in/carry out.
1.551 + @param aRunLength Holds best run length found so far. This will be set to KMaxTInt when no
1.552 + suitable run length has been found. In best fit mode aCarry should also be
1.553 + checked as aRunLength will not be set if aCarry is the only suitable run length
1.554 + found.
1.555 + @param aOffset The bit position to start the search from, set to 0 to search all bit positions.
1.556 + aOffset will be aligned so all bits before an aligned aOffset will be
1.557 + ignored. This can only be non-zero if aCarry is zero as any carry in bits will be
1.558 + ignored if aOffset is non-zero.
1.559 +
1.560 + @return Start position, if a suitable run was found;
1.561 + KErrNotFound, if no suitable run was found;
1.562 + KErrOverflow, if all positions free and best fit mode, or if all positions free
1.563 + in first fit mode and length requested > number of positions available.
1.564 +
1.565 + @see TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength)
1.566 + */
1.567 +EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength, TUint aOffset) const
1.568 + {
1.569 + TInt minrl=KMaxTInt;
1.570 + __ASSERT_ALWAYS(aLength>0, TBMA_FAULT());
1.571 + __ASSERT_ALWAYS(TUint(aAlign)<31, TBMA_FAULT());
1.572 + __ASSERT_ALWAYS(aOffset < (TUint)iSize, TBMA_FAULT());
1.573 + __ASSERT_ALWAYS(!aCarry || !aOffset, TBMA_FAULT());
1.574 + TUint32 alignsize=1<<aAlign;
1.575 + TUint32 alignmask=alignsize-1;
1.576 + aBase&=alignmask;
1.577 + if (iAvail==iSize)
1.578 + {
1.579 + // Align aOffset if it is set so we ignore all bits before the aligned offset.
1.580 + aOffset = (!aOffset)? aOffset : ((aOffset + aBase + alignmask) & ~alignmask) - aBase;
1.581 + TInt runLength = (aOffset < (TUint)iSize)? iSize - aOffset : 0;
1.582 + if (!aBestFit)
1.583 + {
1.584 + TInt alignedStartPos = ((aOffset - aCarry + aBase + alignmask) & ~alignmask) - aBase;
1.585 + TInt lost = alignedStartPos - (aOffset - aCarry);
1.586 + if (runLength + aCarry - lost >= aLength)
1.587 + {
1.588 + aRunLength = runLength;
1.589 + if (alignedStartPos >= 0)
1.590 + {
1.591 + aCarry=0; // clear carry if not initial run
1.592 + }
1.593 + return (alignedStartPos >= 0)? alignedStartPos : 0; // return start pos of exact run
1.594 + }
1.595 + }
1.596 + if (aOffset)
1.597 + aCarry = runLength;
1.598 + else
1.599 + aCarry += iAvail;
1.600 + aRunLength = KMaxTInt;
1.601 + return KErrOverflow;
1.602 + }
1.603 + const TUint32* pW=aCarry?iMap:iCheckFirst;
1.604 + const TUint32* pE=iMap+((iSize+31)>>5);
1.605 + TInt n=((pW-iMap)<<5);
1.606 + TInt p=-1;
1.607 + TInt q=-aCarry;
1.608 + TUint32 s=aCarry?~0:0; // 0 when searching for 1's, FFFFFFFF when searching for 0's
1.609 +
1.610 + TUint32 offsetMask = 0;
1.611 + if (aOffset)
1.612 + {// Start search from aOffset. Only align aOffset if aOffset is to
1.613 + // be used otherwise the best fit mode may fail as aligning aOffset
1.614 + // may cause the search to skip past parts of the bit map.
1.615 + aOffset = ((aOffset + aBase + alignmask) & ~alignmask) - aBase;
1.616 + const TUint32* offsetWord = iMap + (aOffset >> 5);
1.617 + if (offsetWord >= pW)
1.618 + {
1.619 + pW = offsetWord;
1.620 + n = aOffset & 0xffffffe0;
1.621 + offsetMask = 0xffffffff >> (aOffset & 31);
1.622 + __ASSERT_ALWAYS(offsetMask, TBMA_FAULT());
1.623 + }
1.624 + }
1.625 + while (pW<pE)
1.626 + {
1.627 + TUint32 word = *pW++;
1.628 + if (offsetMask)
1.629 + {// Start search after bit aOffset.
1.630 + word &= offsetMask; // Mask off any bits before the aOffset
1.631 + offsetMask = 0; // Reset so future iterations use whole of next word.
1.632 + }
1.633 + if (word==s) // check if any of required bit present
1.634 + {
1.635 + n+=32; // if not, step bit number on by 32
1.636 + continue;
1.637 + }
1.638 + TInt rl=-1;
1.639 + for (TUint32 b=0x80000000; b; ++n, b>>=1)
1.640 + {
1.641 + if ((word ^ s) & b)
1.642 + {
1.643 + if (s && n==iSize)
1.644 + break; // reached end
1.645 + // bit found - invert search bit
1.646 + s=~s;
1.647 + if (s)
1.648 + q=n; // 1 found so save position
1.649 + else
1.650 + {
1.651 + rl=n-q; // 0 found, calculate run length of 1's
1.652 + TInt alignedStartPos = ((q + aBase + alignmask) & ~alignmask) - aBase;
1.653 + TInt lost = alignedStartPos - q;
1.654 + if (rl-lost>=aLength)
1.655 + {
1.656 + if (!aBestFit || rl==aLength)
1.657 + {
1.658 + // first fit or exact match - we're finished
1.659 + if (alignedStartPos >= 0)
1.660 + {
1.661 + aCarry=0; // clear carry if not initial run
1.662 + }
1.663 + aRunLength=rl;
1.664 + return (alignedStartPos >= 0)? alignedStartPos : 0;
1.665 + }
1.666 + if (rl<minrl)
1.667 + {
1.668 + // best fit and this run is smallest so far, so record its position and length
1.669 + minrl=rl;
1.670 + p = (alignedStartPos >= 0)? alignedStartPos : 0;
1.671 + }
1.672 + }
1.673 + }
1.674 + }
1.675 + }
1.676 + }
1.677 + if (minrl!=aLength)
1.678 + {
1.679 + // exact match not found or first fit and no match found
1.680 + TInt rl=0;
1.681 + if (s)
1.682 + {
1.683 + // we were looking for 0, so this counts as a run
1.684 + // get run length
1.685 + rl=n-q;
1.686 + if (!aBestFit)
1.687 + {
1.688 + TInt alignedStartPos = ((q + aBase + alignmask) & ~alignmask) - aBase;
1.689 + TInt lost = alignedStartPos - q;
1.690 + if (rl-lost>=aLength)
1.691 + {// BMA is not totally empty so this can't be the initial run
1.692 + // and the final run. Therefore the start pos must be within
1.693 + // this bma so clear carry and return start pos.
1.694 + aCarry=0;
1.695 + aRunLength=rl;
1.696 + return alignedStartPos;
1.697 + }
1.698 + }
1.699 + }
1.700 + aCarry=rl; // set carry to length of final run or 0 if none
1.701 + }
1.702 + aRunLength=minrl; // return best run length found
1.703 + return p; // return start position of run or -1 if run not found
1.704 + }
1.705 +#endif
1.706 +
1.707 +
1.708 +/** Finds a set of consecutive free positions on a single bit map allocator.
1.709 +
1.710 + @param aLength number of consecutive bit positions to allocate.
1.711 + @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit.
1.712 +
1.713 + @return Start position, if a suitable run was found;
1.714 + KErrNotFound, if no suitable run was found.
1.715 + */
1.716 +EXPORT_C TInt TBitMapAllocator::AllocConsecutive(TInt aLength, TBool aBestFit) const
1.717 + {
1.718 + TInt carry=0;
1.719 + TInt l=KMaxTInt;
1.720 + TInt r=AllocAligned(aLength,0,0,aBestFit,carry,l);
1.721 + if (aBestFit)
1.722 + {
1.723 + // must check final run if any
1.724 + if (carry>=aLength && carry<l)
1.725 + r=iSize-carry;
1.726 + }
1.727 + if (r<0)
1.728 + r=KErrNotFound;
1.729 + return r;
1.730 + }
1.731 +
1.732 +
1.733 +/** Finds a set of consecutive free positions on a single bit map allocator with
1.734 + specified alignment.
1.735 +
1.736 + @param aLength number of consecutive bit positions to allocate.
1.737 + @param aAlign logarithm to base 2 of the alignment required.
1.738 + @param aBase the alignment of the first bit of this allocator - only significant modulo 2^aAlign.
1.739 + @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit.
1.740 +
1.741 + @return Start position, if a suitable run was found;
1.742 + KErrNotFound, if no suitable run was found.
1.743 + */
1.744 +EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit) const
1.745 + {
1.746 + TInt carry=0;
1.747 + TInt l=KMaxTInt;
1.748 + TUint32 alignsize=1<<aAlign;
1.749 + TUint32 alignmask=alignsize-1;
1.750 + aBase&=alignmask;
1.751 + TInt r=AllocAligned(aLength,aAlign,aBase,aBestFit,carry,l);
1.752 + if (aBestFit)
1.753 + {
1.754 + // must check final run if any
1.755 + TInt fpos=iSize-carry;
1.756 + TInt lost=((fpos+aBase+alignmask)&~alignmask)-aBase-fpos;
1.757 + if (carry-lost>=aLength && carry<l)
1.758 + r=fpos+lost;
1.759 + }
1.760 + if (r<0)
1.761 + r=KErrNotFound;
1.762 + else
1.763 + r=((r+aBase+alignmask)&~alignmask)-aBase;
1.764 + return r;
1.765 + }
1.766 +
1.767 +
1.768 +/** Copies a range from another allocator, mark remainder as occupied.
1.769 +
1.770 + Values of bit positions from aFirst to aFirst+aLen-1 inclusive in allocator
1.771 + aA are copied to bit positions in this allocator starting with aFirst mod 32.
1.772 + Remaining bit positions in this allocator are marked as occupied.
1.773 +
1.774 + @param aA Pointer to source allocator.
1.775 + @param aFirst Number in source allocator of first bit to copy.
1.776 + @param aLen Number of bits to copy from source allocator.
1.777 + */
1.778 +EXPORT_C void TBitMapAllocator::CopyAlignedRange(const TBitMapAllocator* aA, TInt aFirst, TInt aLen)
1.779 + {
1.780 + const TUint32* srcptr = aA->iMap + (aFirst>>5);
1.781 + TInt last = aFirst + aLen - 1;
1.782 + TInt len = (((last+32)&~31)-(aFirst&~31))>>3; // bytes
1.783 + __ASSERT_ALWAYS(len<=iSize, TBMA_FAULT());
1.784 + TInt remain = ((iSize+31)&~31)-(len<<3);
1.785 + wordmove(iMap, srcptr, len);
1.786 + memclr(iMap+(len>>2), remain>>3);
1.787 + TUint32* p = iMap;
1.788 + TUint32* pE = p + (len>>2);
1.789 + *p &= (0xffffffffu >> (aFirst&31));
1.790 + pE[-1] &= (0xffffffffu << (31-(last&31)));
1.791 + iCheckFirst = pE-1;
1.792 + iAvail = 0;
1.793 + for (; p<pE; ++p)
1.794 + {
1.795 + TUint32 x = *p;
1.796 + if (x)
1.797 + {
1.798 + if (p<iCheckFirst)
1.799 + iCheckFirst = p;
1.800 + iAvail += __e32_bit_count_32(x);
1.801 + }
1.802 + }
1.803 + }