1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kerneltest/e32test/nkernsa/tlsf.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,527 @@
1.4 +// Copyright (c) 2005-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 +// x86pc\nkern\tlsf.cpp
1.18 +//
1.19 +//
1.20 +
1.21 +#include <nktest/nkutils.h>
1.22 +
1.23 +extern "C" {
1.24 +extern TLinAddr RomHeaderAddress;
1.25 +extern TLinAddr SuperPageAddress;
1.26 +}
1.27 +
1.28 +#define BLOCK_STATUS_FREE 1u // bit set if SBlock free
1.29 +#define BLOCK_STATUS_FINAL 2u // bit set if this is last physical SBlock
1.30 +#define BLOCK_SIZE_MASK 0xfffffffcu
1.31 +
1.32 +struct SBlock
1.33 + {
1.34 + TUint32 size; // bits 2-31 give size, bits 0,1 are status bits
1.35 + SBlock* predecessor; // previous SBlock in physical address order
1.36 + };
1.37 +
1.38 +struct SFreeBlock
1.39 + {
1.40 + SBlock b;
1.41 + SFreeBlock* next; // next SBlock in same bucket, circular list
1.42 + SFreeBlock* prev; // previous SBlock in same bucket, circular list
1.43 + };
1.44 +
1.45 +struct STlsfAllocator
1.46 + {
1.47 +public:
1.48 + static STlsfAllocator* Create(TAny* aBase, TUint32 aTotalSize);
1.49 + TAny* Alloc(TUint32 aSize);
1.50 + void Free(TAny* aCell);
1.51 + TAny* ReAlloc(TAny* aCell, TUint32 aSize);
1.52 +
1.53 + void Init(TUint32 aTotalSize);
1.54 + void InsertFree(SFreeBlock* aB);
1.55 + TUint32 MapSize(TUint32 aSize, TUint32* p_sli, TInt round_up);
1.56 + SFreeBlock* FindFree(TUint32 aSize);
1.57 + void RemoveFree(SFreeBlock* aB);
1.58 + TUint32 ConsistencyCheck();
1.59 +public:
1.60 + TUint32 imin_size; // minimum SBlock size
1.61 + TUint32 itotal_size; // total size of allocated and free blocks
1.62 + TUint32 il2min; // log2 min size
1.63 + TUint32 infl; // number of first level lists
1.64 + TUint32 insl; // number of second level lists
1.65 + TUint32 il2nsl;
1.66 + SFreeBlock** isll; // pointer to first second level list pointer for minimum size
1.67 + TUint32 iflb; // first level bitmap
1.68 + SBlock* iff; // first free address
1.69 + TUint32 islb[1]; // second level bitmaps, one for each first level list
1.70 + // second level lists follow, nsl pointers for each first level list
1.71 + };
1.72 +
1.73 +STlsfAllocator* TheAllocator;
1.74 +NFastMutex AllocMutex;
1.75 +
1.76 +STlsfAllocator* STlsfAllocator::Create(void* aBase, TUint32 aTotalSize)
1.77 + {
1.78 + STlsfAllocator* p = (STlsfAllocator*)aBase;
1.79 + p->Init(aTotalSize);
1.80 + return p;
1.81 + }
1.82 +
1.83 +void STlsfAllocator::Init(TUint32 total_size)
1.84 + {
1.85 + TUint32 a;
1.86 + imin_size = 16;
1.87 + il2min = 4;
1.88 + insl = 16;
1.89 + il2nsl = 4;
1.90 + itotal_size = total_size;
1.91 + infl = __e32_find_ms1_32(total_size) - il2min + 1;
1.92 + iflb = 0;
1.93 + a = (TUint32)&islb[infl];
1.94 + a = (a+63)&~63;
1.95 + isll = (SFreeBlock**)a;
1.96 + a += insl * infl * sizeof(TUint32*);
1.97 + iff = (SBlock*)a;
1.98 + a -= (TUint32)this;
1.99 + memset(islb, 0, total_size - sizeof(STlsfAllocator) + sizeof(TUint32));
1.100 + iff->size = (total_size - a) | BLOCK_STATUS_FINAL;
1.101 + iff->predecessor = 0;
1.102 + Free(iff+1);
1.103 + }
1.104 +
1.105 +// size already rounded up to multiple of min_size
1.106 +TUint32 STlsfAllocator::MapSize(TUint32 size, TUint32* p_sli, TInt round_up)
1.107 + {
1.108 + TUint32 sli = size >> il2min;
1.109 + TUint32 fli = __e32_find_ms1_32(sli);
1.110 + sli -= (1u<<fli);
1.111 + if (fli > il2nsl)
1.112 + {
1.113 + TUint32 sls = (fli - il2nsl);
1.114 + TUint32 sz2 = sli;
1.115 + sli >>= sls;
1.116 + if (round_up && ((sli << sls) < sz2) )
1.117 + {
1.118 + if (++sli == insl)
1.119 + sli=0, ++fli;
1.120 + }
1.121 + }
1.122 + *p_sli = sli;
1.123 + return fli;
1.124 + }
1.125 +
1.126 +SFreeBlock* STlsfAllocator::FindFree(TUint32 size)
1.127 + {
1.128 + TUint32 sli;
1.129 + TUint32 fli = MapSize(size, &sli, 1);
1.130 + TUint32 sli2;
1.131 + TUint32 fli2;
1.132 + SFreeBlock** sll;
1.133 + SFreeBlock* b;
1.134 + TUint32 act_sz;
1.135 +
1.136 + if ((iflb >> fli) & 1)
1.137 + {
1.138 + if ((islb[fli]>>sli)==0)
1.139 + ++fli, sli=0;
1.140 + }
1.141 + else
1.142 + sli = 0;
1.143 + if (fli >= infl)
1.144 + return 0;
1.145 + fli2 = __e32_find_ls1_32(iflb >> fli);
1.146 + if ((TInt)fli2 < 0)
1.147 + return 0;
1.148 + fli2 += fli;
1.149 + sli2 = __e32_find_ls1_32(islb[fli2] >> sli) + sli; // must find a 1
1.150 + sll = &isll[(fli2 << il2nsl) | sli2];
1.151 + b = *sll;
1.152 + if (b->next == b)
1.153 + {
1.154 + // list now empty
1.155 + *sll = 0;
1.156 + if ( (islb[fli2] &= ~(1u<<sli2)) == 0 )
1.157 + iflb &= ~(1u<<fli2);
1.158 + }
1.159 + else
1.160 + {
1.161 + *sll = b->next;
1.162 + b->next->prev = b->prev;
1.163 + b->prev->next = b->next;
1.164 + }
1.165 + act_sz = b->b.size & BLOCK_SIZE_MASK;
1.166 + if (act_sz > size)
1.167 + {
1.168 + // free the extra
1.169 + SBlock* nfb = (SBlock*)((TUint32)b + size);
1.170 + nfb->size = (act_sz - size) | (b->b.size & BLOCK_STATUS_FINAL);
1.171 + nfb->predecessor = &b->b;
1.172 + if (!(b->b.size & BLOCK_STATUS_FINAL))
1.173 + {
1.174 + // if this isn't final SBlock, update predecessor of following SBlock
1.175 + SBlock* nb = (SBlock*)((TUint32)b + act_sz);
1.176 + nb->predecessor = nfb;
1.177 + }
1.178 + InsertFree((SFreeBlock*)nfb);
1.179 + b->b.size = 0; // allocated SBlock can't be final
1.180 + }
1.181 + b->b.size &= BLOCK_STATUS_FINAL;
1.182 + b->b.size |= size;
1.183 + return b;
1.184 + }
1.185 +
1.186 +void STlsfAllocator::InsertFree(SFreeBlock* b)
1.187 + {
1.188 + TUint32 size = b->b.size & BLOCK_SIZE_MASK;
1.189 + TUint32 sli;
1.190 + TUint32 fli = MapSize(size, &sli, 0);
1.191 + SFreeBlock** sll = &isll[(fli << il2nsl) | sli];
1.192 + if (*sll)
1.193 + {
1.194 + SFreeBlock* first = *sll;
1.195 + b->next = first;
1.196 + b->prev = first->prev;
1.197 + first->prev->next = b;
1.198 + first->prev = b;
1.199 + }
1.200 + else
1.201 + {
1.202 + b->next = b;
1.203 + b->prev = b;
1.204 + islb[fli] |= (1u<<sli);
1.205 + iflb |= (1u<<fli);
1.206 + }
1.207 + *sll = b;
1.208 + b->b.size |= BLOCK_STATUS_FREE;
1.209 + }
1.210 +
1.211 +void STlsfAllocator::RemoveFree(SFreeBlock* b)
1.212 + {
1.213 + TUint32 size = b->b.size & BLOCK_SIZE_MASK;
1.214 + TUint32 sli;
1.215 + TUint32 fli = MapSize(size, &sli, 0);
1.216 + SFreeBlock** sll = &isll[(fli << il2nsl) | sli];
1.217 + if (b->next != b)
1.218 + {
1.219 + if (*sll == b)
1.220 + *sll = b->next;
1.221 + b->next->prev = b->prev;
1.222 + b->prev->next = b->next;
1.223 + return;
1.224 + }
1.225 + *sll = 0;
1.226 + if ( (islb[fli] &= ~(1u<<sli)) == 0)
1.227 + iflb &= ~(1u<<fli);
1.228 + }
1.229 +
1.230 +TAny* STlsfAllocator::Alloc(TUint32 size)
1.231 + {
1.232 + SFreeBlock* b;
1.233 + TUint32 msm = imin_size - 1;
1.234 +
1.235 + size = (size + sizeof(SBlock) + msm) &~ msm;
1.236 +
1.237 + b = FindFree(size);
1.238 + if (b)
1.239 + return &b->next;
1.240 + return 0;
1.241 + }
1.242 +
1.243 +void STlsfAllocator::Free(TAny* cell)
1.244 + {
1.245 + SBlock* b = ((SBlock*)cell) - 1;
1.246 +// SFreeBlock* fb = (SFreeBlock*)b;
1.247 + TUint32 size;
1.248 + if (!cell)
1.249 + return;
1.250 + size = b->size & BLOCK_SIZE_MASK;
1.251 + if (!(b->size & BLOCK_STATUS_FINAL))
1.252 + {
1.253 + // not last SBlock
1.254 + SBlock* nb = (SBlock*)((TUint32)b + size);
1.255 + TUint32 nbs = nb->size;
1.256 + if (nbs & BLOCK_STATUS_FREE)
1.257 + {
1.258 + // following SBlock is free
1.259 + RemoveFree((SFreeBlock*)nb);
1.260 + b->size = size + (nbs &~ BLOCK_STATUS_FREE); // keeps final flag from following SBlock
1.261 + size = b->size & BLOCK_SIZE_MASK;
1.262 + if (!(nbs & BLOCK_STATUS_FINAL))
1.263 + {
1.264 + nb = (SBlock*)((TUint32)b + size);
1.265 + nb->predecessor = b;
1.266 + }
1.267 + }
1.268 + }
1.269 + if (b->predecessor && b->predecessor->size & BLOCK_STATUS_FREE)
1.270 + {
1.271 + // predecessor SBlock is free
1.272 + TUint32 psz = b->predecessor->size & BLOCK_SIZE_MASK;
1.273 + RemoveFree((SFreeBlock*)b->predecessor);
1.274 + psz += b->size; // keeps final flag if necessary
1.275 + b->predecessor->size = psz;
1.276 + b = b->predecessor;
1.277 + if (!(psz & BLOCK_STATUS_FINAL))
1.278 + {
1.279 + // need to adjust prev pointer of following SBlock
1.280 + SBlock* nb = (SBlock*)((TUint32)b + psz);
1.281 + nb->predecessor = b;
1.282 + }
1.283 + }
1.284 + InsertFree((SFreeBlock*)b);
1.285 + }
1.286 +
1.287 +TAny* STlsfAllocator::ReAlloc(TAny* cell, TUint32 newsize)
1.288 + {
1.289 + SBlock* b;
1.290 + TUint32 size;
1.291 + TUint32 msm;
1.292 + SBlock* nb;
1.293 + TAny* newcell;
1.294 +
1.295 + if (!cell)
1.296 + return (newsize>0) ? Alloc(newsize) : 0;
1.297 + if (newsize == 0)
1.298 + {
1.299 + Free(cell);
1.300 + return 0;
1.301 + }
1.302 + b = ((SBlock*)cell) - 1;
1.303 + size = b->size & BLOCK_SIZE_MASK;
1.304 + msm = imin_size - 1;
1.305 + newsize = (newsize + sizeof(SBlock) + msm) &~ msm;
1.306 + if (newsize > size)
1.307 + {
1.308 + nb = (SBlock*)((TUint32)b + size);
1.309 + if (nb->size & BLOCK_STATUS_FREE)
1.310 + {
1.311 + // following SBlock is free
1.312 + TUint32 nbs = nb->size;
1.313 + if (nbs + size >= newsize)
1.314 + {
1.315 + // we can expand in place - grab the entire free SBlock for now
1.316 + // it will be split if necessary in the next section of code
1.317 + RemoveFree((SFreeBlock*)nb);
1.318 + b->size = size + (nbs &~ BLOCK_STATUS_FREE); // keeps final flag from following SBlock
1.319 + size = b->size & BLOCK_SIZE_MASK;
1.320 + if (!(nbs & BLOCK_STATUS_FINAL))
1.321 + {
1.322 + SBlock* nnb = (SBlock*)((TUint32)b + size);
1.323 + nnb->predecessor = b;
1.324 + }
1.325 + }
1.326 + }
1.327 + }
1.328 + if (newsize == size)
1.329 + return cell;
1.330 + if (newsize < size)
1.331 + {
1.332 + // shrinking - split SBlock
1.333 + TUint32 final = b->size & BLOCK_STATUS_FINAL;
1.334 + SBlock* nfb = (SBlock*)((TUint32)b + newsize);
1.335 + nfb->size = (size - newsize) | final;
1.336 + nfb->predecessor = b;
1.337 + if (!final)
1.338 + {
1.339 + // if this isn't final SBlock, update predecessor of following SBlock
1.340 + nb = (SBlock*)((TUint32)b + size);
1.341 + nb->predecessor = nfb;
1.342 + }
1.343 + b->size = newsize; // original SBlock can't be final
1.344 + Free((SBlock*)nfb + 1);
1.345 + return cell;
1.346 + }
1.347 +
1.348 + // must move SBlock to expand
1.349 + newcell = Alloc(newsize);
1.350 + if (newcell)
1.351 + {
1.352 + memcpy(newcell, cell, size);
1.353 + Free(cell);
1.354 + }
1.355 + return newcell;
1.356 + }
1.357 +
1.358 +TUint32 STlsfAllocator::ConsistencyCheck()
1.359 + {
1.360 + TUint32 a;
1.361 + TUint32 szs = 0;
1.362 + TUint32 size;
1.363 + TUint32 total_user_size;
1.364 + TUint32 total_block_size = 0;
1.365 + TUint32 block_count = 0;
1.366 + TUint32 flb = 0;
1.367 + TUint32 slb[32];
1.368 + TUint32 sli;
1.369 + TUint32 fli;
1.370 + TUint32 total_free = 0;
1.371 + SBlock* b = iff;
1.372 + SBlock* pb = 0;
1.373 +
1.374 + memset(slb, 0, sizeof(slb));
1.375 + __NK_ASSERT_DEBUG(imin_size == 16);
1.376 + __NK_ASSERT_DEBUG(insl == 16);
1.377 + __NK_ASSERT_DEBUG(il2min == 4);
1.378 + __NK_ASSERT_DEBUG(il2nsl == 4);
1.379 + __NK_ASSERT_DEBUG(infl == __e32_find_ms1_32(itotal_size) - il2min + 1);
1.380 + a = (TUint32)&islb[infl];
1.381 + a = (a+63)&~63;
1.382 + __NK_ASSERT_DEBUG(isll == (SFreeBlock**)a);
1.383 + a += insl * infl * sizeof(TUint32*);
1.384 + __NK_ASSERT_DEBUG(iff == (SBlock*)a);
1.385 + total_user_size = itotal_size - (a - (TUint32)this);
1.386 +
1.387 + do {
1.388 + szs = b->size;
1.389 + size = szs & BLOCK_SIZE_MASK;
1.390 + __NK_ASSERT_DEBUG(b->predecessor == pb);
1.391 + __NK_ASSERT_DEBUG(size > 0);
1.392 + __NK_ASSERT_DEBUG(size <= total_user_size);
1.393 + __NK_ASSERT_DEBUG(size == ((size >> il2min) << il2min));
1.394 + total_block_size += size;
1.395 + ++block_count;
1.396 + pb = b;
1.397 + b = (SBlock*)((TUint32)b + size);
1.398 + } while(!(szs & BLOCK_STATUS_FINAL));
1.399 + __NK_ASSERT_DEBUG((TUint32)b == (TUint32)this + itotal_size);
1.400 + __NK_ASSERT_DEBUG(total_block_size == total_user_size);
1.401 +
1.402 + b = iff;
1.403 + do {
1.404 + szs = b->size;
1.405 + size = szs & BLOCK_SIZE_MASK;
1.406 + if (szs & BLOCK_STATUS_FREE)
1.407 + {
1.408 + SFreeBlock* fb = (SFreeBlock*)b;
1.409 + SFreeBlock* pfb = fb;
1.410 + SFreeBlock* lh;
1.411 + TUint32 lhi;
1.412 + TInt lh_found = 0;
1.413 + TInt c = (TInt)block_count;
1.414 + TUint32 fli = __e32_find_ms1_32(size) - il2min;
1.415 + TUint32 sli = (size >> il2min) - (1u << fli);
1.416 + TUint32 sli2;
1.417 + TUint32 fli2 = MapSize(size, &sli2, 0);
1.418 + (void)sli2, (void)fli2;
1.419 + if (fli > il2nsl)
1.420 + sli >>= (fli - il2nsl);
1.421 + __NK_ASSERT_DEBUG(fli == fli2);
1.422 + __NK_ASSERT_DEBUG(sli == sli2);
1.423 + flb |= (1u << fli);
1.424 + slb[fli] |= (1u << sli);
1.425 + lhi = (fli << il2nsl) | sli;
1.426 + lh = isll[lhi];
1.427 + do {
1.428 + if (fb == lh)
1.429 + lh_found = 1;
1.430 + pfb = fb;
1.431 + fb = fb->next;
1.432 + __NK_ASSERT_DEBUG(fb->prev == pfb);
1.433 + __NK_ASSERT_DEBUG(fb->b.size & BLOCK_STATUS_FREE);
1.434 + } while ((fb != (SFreeBlock*)b) && --c>=0);
1.435 + __NK_ASSERT_DEBUG(fb == (SFreeBlock*)b);
1.436 + __NK_ASSERT_DEBUG(lh_found);
1.437 + total_free += size;
1.438 + }
1.439 + b = (SBlock*)((TUint32)b + size);
1.440 + } while(!(szs & BLOCK_STATUS_FINAL));
1.441 +
1.442 + __NK_ASSERT_DEBUG(flb == iflb);
1.443 + for (fli=0; fli<infl; ++fli)
1.444 + {
1.445 + __NK_ASSERT_DEBUG(slb[fli] == islb[fli]);
1.446 + if (!(flb & (1u<<fli)))
1.447 + __NK_ASSERT_DEBUG(slb[fli]==0);
1.448 + for (sli=0; sli<insl; ++sli)
1.449 + {
1.450 + TUint32 lhi = (fli << il2nsl) | sli;
1.451 + (void)lhi;
1.452 + if (!(slb[fli] & (1u<<sli)))
1.453 + __NK_ASSERT_DEBUG(!isll[lhi]);
1.454 + }
1.455 + }
1.456 + return total_free;
1.457 + }
1.458 +
1.459 +#define __E32CMN_H__
1.460 +
1.461 +#undef EXPORT_C
1.462 +#define EXPORT_C /* */
1.463 +
1.464 +class TVersion
1.465 + {
1.466 +public:
1.467 + TInt8 iMajor;
1.468 + TInt8 iMinor;
1.469 + TInt16 iBuild;
1.470 + };
1.471 +
1.472 +class TDesC;
1.473 +
1.474 +#include <e32rom.h>
1.475 +#include "kernboot.h"
1.476 +
1.477 +extern "C" {
1.478 +void SetupMemoryAllocator()
1.479 + {
1.480 + const SSuperPageBase& sp = *(const SSuperPageBase*)SuperPageAddress;
1.481 + const TRomHeader& romHdr = *(const TRomHeader*)RomHeaderAddress;
1.482 + const TRomEntry* primaryEntry = (const TRomEntry*)sp.iPrimaryEntry;
1.483 + const TRomImageHeader* primaryImageHeader = (const TRomImageHeader*)primaryEntry->iAddressLin;
1.484 + TLinAddr stack = romHdr.iKernDataAddress + round_to_page(romHdr.iTotalSvDataSize);
1.485 + TLinAddr heapbase = stack + round_to_page(primaryImageHeader->iStackSize);
1.486 + TLinAddr heapsize = sp.iInitialHeapSize;
1.487 +
1.488 + KPrintf("Heap base %08x size %08x", heapbase, heapsize);
1.489 + TheAllocator = STlsfAllocator::Create((TAny*)heapbase, heapsize);
1.490 + }
1.491 +
1.492 +extern TBool InitialThreadDefined;
1.493 +
1.494 +TAny* malloc(TUint32 aSize)
1.495 + {
1.496 +// __KTRACE_OPT(KMMU,DEBUGPRINT("malloc(%d)",aSize));
1.497 + if (InitialThreadDefined)
1.498 + NKern::FMWait(&AllocMutex);
1.499 + TAny* p = TheAllocator->Alloc(aSize);
1.500 + if (InitialThreadDefined)
1.501 + NKern::FMSignal(&AllocMutex);
1.502 + __KTRACE_OPT(KMMU,DEBUGPRINT("malloc(%d)->%08x",aSize,p));
1.503 + return p;
1.504 + }
1.505 +
1.506 +void free(TAny* aCell)
1.507 + {
1.508 + __KTRACE_OPT(KMMU,DEBUGPRINT("free(%08x)",aCell));
1.509 +#ifdef _DEBUG
1.510 + if (aCell)
1.511 + {
1.512 + SBlock* b = (SBlock*)aCell;
1.513 + TUint32 size = b[-1].size & BLOCK_SIZE_MASK;
1.514 + memset(aCell, 0xde, size - sizeof(SBlock));
1.515 + }
1.516 +#endif
1.517 + NKern::FMWait(&AllocMutex);
1.518 + TheAllocator->Free(aCell);
1.519 + NKern::FMSignal(&AllocMutex);
1.520 + }
1.521 +
1.522 +TAny* realloc(TAny* aCell, TUint32 aSize)
1.523 + {
1.524 + NKern::FMWait(&AllocMutex);
1.525 + TAny* p = TheAllocator->ReAlloc(aCell, aSize);
1.526 + NKern::FMSignal(&AllocMutex);
1.527 + return p;
1.528 + }
1.529 +}
1.530 +