sl@0: // Copyright (c) 2005-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 the License "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: // x86pc\nkern\tlsf.cpp sl@0: // sl@0: // sl@0: sl@0: #include sl@0: sl@0: extern "C" { sl@0: extern TLinAddr RomHeaderAddress; sl@0: extern TLinAddr SuperPageAddress; sl@0: } sl@0: sl@0: #define BLOCK_STATUS_FREE 1u // bit set if SBlock free sl@0: #define BLOCK_STATUS_FINAL 2u // bit set if this is last physical SBlock sl@0: #define BLOCK_SIZE_MASK 0xfffffffcu sl@0: sl@0: struct SBlock sl@0: { sl@0: TUint32 size; // bits 2-31 give size, bits 0,1 are status bits sl@0: SBlock* predecessor; // previous SBlock in physical address order sl@0: }; sl@0: sl@0: struct SFreeBlock sl@0: { sl@0: SBlock b; sl@0: SFreeBlock* next; // next SBlock in same bucket, circular list sl@0: SFreeBlock* prev; // previous SBlock in same bucket, circular list sl@0: }; sl@0: sl@0: struct STlsfAllocator sl@0: { sl@0: public: sl@0: static STlsfAllocator* Create(TAny* aBase, TUint32 aTotalSize); sl@0: TAny* Alloc(TUint32 aSize); sl@0: void Free(TAny* aCell); sl@0: TAny* ReAlloc(TAny* aCell, TUint32 aSize); sl@0: sl@0: void Init(TUint32 aTotalSize); sl@0: void InsertFree(SFreeBlock* aB); sl@0: TUint32 MapSize(TUint32 aSize, TUint32* p_sli, TInt round_up); sl@0: SFreeBlock* FindFree(TUint32 aSize); sl@0: void RemoveFree(SFreeBlock* aB); sl@0: TUint32 ConsistencyCheck(); sl@0: public: sl@0: TUint32 imin_size; // minimum SBlock size sl@0: TUint32 itotal_size; // total size of allocated and free blocks sl@0: TUint32 il2min; // log2 min size sl@0: TUint32 infl; // number of first level lists sl@0: TUint32 insl; // number of second level lists sl@0: TUint32 il2nsl; sl@0: SFreeBlock** isll; // pointer to first second level list pointer for minimum size sl@0: TUint32 iflb; // first level bitmap sl@0: SBlock* iff; // first free address sl@0: TUint32 islb[1]; // second level bitmaps, one for each first level list sl@0: // second level lists follow, nsl pointers for each first level list sl@0: }; sl@0: sl@0: STlsfAllocator* TheAllocator; sl@0: NFastMutex AllocMutex; sl@0: sl@0: STlsfAllocator* STlsfAllocator::Create(void* aBase, TUint32 aTotalSize) sl@0: { sl@0: STlsfAllocator* p = (STlsfAllocator*)aBase; sl@0: p->Init(aTotalSize); sl@0: return p; sl@0: } sl@0: sl@0: void STlsfAllocator::Init(TUint32 total_size) sl@0: { sl@0: TUint32 a; sl@0: imin_size = 16; sl@0: il2min = 4; sl@0: insl = 16; sl@0: il2nsl = 4; sl@0: itotal_size = total_size; sl@0: infl = __e32_find_ms1_32(total_size) - il2min + 1; sl@0: iflb = 0; sl@0: a = (TUint32)&islb[infl]; sl@0: a = (a+63)&~63; sl@0: isll = (SFreeBlock**)a; sl@0: a += insl * infl * sizeof(TUint32*); sl@0: iff = (SBlock*)a; sl@0: a -= (TUint32)this; sl@0: memset(islb, 0, total_size - sizeof(STlsfAllocator) + sizeof(TUint32)); sl@0: iff->size = (total_size - a) | BLOCK_STATUS_FINAL; sl@0: iff->predecessor = 0; sl@0: Free(iff+1); sl@0: } sl@0: sl@0: // size already rounded up to multiple of min_size sl@0: TUint32 STlsfAllocator::MapSize(TUint32 size, TUint32* p_sli, TInt round_up) sl@0: { sl@0: TUint32 sli = size >> il2min; sl@0: TUint32 fli = __e32_find_ms1_32(sli); sl@0: sli -= (1u< il2nsl) sl@0: { sl@0: TUint32 sls = (fli - il2nsl); sl@0: TUint32 sz2 = sli; sl@0: sli >>= sls; sl@0: if (round_up && ((sli << sls) < sz2) ) sl@0: { sl@0: if (++sli == insl) sl@0: sli=0, ++fli; sl@0: } sl@0: } sl@0: *p_sli = sli; sl@0: return fli; sl@0: } sl@0: sl@0: SFreeBlock* STlsfAllocator::FindFree(TUint32 size) sl@0: { sl@0: TUint32 sli; sl@0: TUint32 fli = MapSize(size, &sli, 1); sl@0: TUint32 sli2; sl@0: TUint32 fli2; sl@0: SFreeBlock** sll; sl@0: SFreeBlock* b; sl@0: TUint32 act_sz; sl@0: sl@0: if ((iflb >> fli) & 1) sl@0: { sl@0: if ((islb[fli]>>sli)==0) sl@0: ++fli, sli=0; sl@0: } sl@0: else sl@0: sli = 0; sl@0: if (fli >= infl) sl@0: return 0; sl@0: fli2 = __e32_find_ls1_32(iflb >> fli); sl@0: if ((TInt)fli2 < 0) sl@0: return 0; sl@0: fli2 += fli; sl@0: sli2 = __e32_find_ls1_32(islb[fli2] >> sli) + sli; // must find a 1 sl@0: sll = &isll[(fli2 << il2nsl) | sli2]; sl@0: b = *sll; sl@0: if (b->next == b) sl@0: { sl@0: // list now empty sl@0: *sll = 0; sl@0: if ( (islb[fli2] &= ~(1u<next; sl@0: b->next->prev = b->prev; sl@0: b->prev->next = b->next; sl@0: } sl@0: act_sz = b->b.size & BLOCK_SIZE_MASK; sl@0: if (act_sz > size) sl@0: { sl@0: // free the extra sl@0: SBlock* nfb = (SBlock*)((TUint32)b + size); sl@0: nfb->size = (act_sz - size) | (b->b.size & BLOCK_STATUS_FINAL); sl@0: nfb->predecessor = &b->b; sl@0: if (!(b->b.size & BLOCK_STATUS_FINAL)) sl@0: { sl@0: // if this isn't final SBlock, update predecessor of following SBlock sl@0: SBlock* nb = (SBlock*)((TUint32)b + act_sz); sl@0: nb->predecessor = nfb; sl@0: } sl@0: InsertFree((SFreeBlock*)nfb); sl@0: b->b.size = 0; // allocated SBlock can't be final sl@0: } sl@0: b->b.size &= BLOCK_STATUS_FINAL; sl@0: b->b.size |= size; sl@0: return b; sl@0: } sl@0: sl@0: void STlsfAllocator::InsertFree(SFreeBlock* b) sl@0: { sl@0: TUint32 size = b->b.size & BLOCK_SIZE_MASK; sl@0: TUint32 sli; sl@0: TUint32 fli = MapSize(size, &sli, 0); sl@0: SFreeBlock** sll = &isll[(fli << il2nsl) | sli]; sl@0: if (*sll) sl@0: { sl@0: SFreeBlock* first = *sll; sl@0: b->next = first; sl@0: b->prev = first->prev; sl@0: first->prev->next = b; sl@0: first->prev = b; sl@0: } sl@0: else sl@0: { sl@0: b->next = b; sl@0: b->prev = b; sl@0: islb[fli] |= (1u<b.size |= BLOCK_STATUS_FREE; sl@0: } sl@0: sl@0: void STlsfAllocator::RemoveFree(SFreeBlock* b) sl@0: { sl@0: TUint32 size = b->b.size & BLOCK_SIZE_MASK; sl@0: TUint32 sli; sl@0: TUint32 fli = MapSize(size, &sli, 0); sl@0: SFreeBlock** sll = &isll[(fli << il2nsl) | sli]; sl@0: if (b->next != b) sl@0: { sl@0: if (*sll == b) sl@0: *sll = b->next; sl@0: b->next->prev = b->prev; sl@0: b->prev->next = b->next; sl@0: return; sl@0: } sl@0: *sll = 0; sl@0: if ( (islb[fli] &= ~(1u<next; sl@0: return 0; sl@0: } sl@0: sl@0: void STlsfAllocator::Free(TAny* cell) sl@0: { sl@0: SBlock* b = ((SBlock*)cell) - 1; sl@0: // SFreeBlock* fb = (SFreeBlock*)b; sl@0: TUint32 size; sl@0: if (!cell) sl@0: return; sl@0: size = b->size & BLOCK_SIZE_MASK; sl@0: if (!(b->size & BLOCK_STATUS_FINAL)) sl@0: { sl@0: // not last SBlock sl@0: SBlock* nb = (SBlock*)((TUint32)b + size); sl@0: TUint32 nbs = nb->size; sl@0: if (nbs & BLOCK_STATUS_FREE) sl@0: { sl@0: // following SBlock is free sl@0: RemoveFree((SFreeBlock*)nb); sl@0: b->size = size + (nbs &~ BLOCK_STATUS_FREE); // keeps final flag from following SBlock sl@0: size = b->size & BLOCK_SIZE_MASK; sl@0: if (!(nbs & BLOCK_STATUS_FINAL)) sl@0: { sl@0: nb = (SBlock*)((TUint32)b + size); sl@0: nb->predecessor = b; sl@0: } sl@0: } sl@0: } sl@0: if (b->predecessor && b->predecessor->size & BLOCK_STATUS_FREE) sl@0: { sl@0: // predecessor SBlock is free sl@0: TUint32 psz = b->predecessor->size & BLOCK_SIZE_MASK; sl@0: RemoveFree((SFreeBlock*)b->predecessor); sl@0: psz += b->size; // keeps final flag if necessary sl@0: b->predecessor->size = psz; sl@0: b = b->predecessor; sl@0: if (!(psz & BLOCK_STATUS_FINAL)) sl@0: { sl@0: // need to adjust prev pointer of following SBlock sl@0: SBlock* nb = (SBlock*)((TUint32)b + psz); sl@0: nb->predecessor = b; sl@0: } sl@0: } sl@0: InsertFree((SFreeBlock*)b); sl@0: } sl@0: sl@0: TAny* STlsfAllocator::ReAlloc(TAny* cell, TUint32 newsize) sl@0: { sl@0: SBlock* b; sl@0: TUint32 size; sl@0: TUint32 msm; sl@0: SBlock* nb; sl@0: TAny* newcell; sl@0: sl@0: if (!cell) sl@0: return (newsize>0) ? Alloc(newsize) : 0; sl@0: if (newsize == 0) sl@0: { sl@0: Free(cell); sl@0: return 0; sl@0: } sl@0: b = ((SBlock*)cell) - 1; sl@0: size = b->size & BLOCK_SIZE_MASK; sl@0: msm = imin_size - 1; sl@0: newsize = (newsize + sizeof(SBlock) + msm) &~ msm; sl@0: if (newsize > size) sl@0: { sl@0: nb = (SBlock*)((TUint32)b + size); sl@0: if (nb->size & BLOCK_STATUS_FREE) sl@0: { sl@0: // following SBlock is free sl@0: TUint32 nbs = nb->size; sl@0: if (nbs + size >= newsize) sl@0: { sl@0: // we can expand in place - grab the entire free SBlock for now sl@0: // it will be split if necessary in the next section of code sl@0: RemoveFree((SFreeBlock*)nb); sl@0: b->size = size + (nbs &~ BLOCK_STATUS_FREE); // keeps final flag from following SBlock sl@0: size = b->size & BLOCK_SIZE_MASK; sl@0: if (!(nbs & BLOCK_STATUS_FINAL)) sl@0: { sl@0: SBlock* nnb = (SBlock*)((TUint32)b + size); sl@0: nnb->predecessor = b; sl@0: } sl@0: } sl@0: } sl@0: } sl@0: if (newsize == size) sl@0: return cell; sl@0: if (newsize < size) sl@0: { sl@0: // shrinking - split SBlock sl@0: TUint32 final = b->size & BLOCK_STATUS_FINAL; sl@0: SBlock* nfb = (SBlock*)((TUint32)b + newsize); sl@0: nfb->size = (size - newsize) | final; sl@0: nfb->predecessor = b; sl@0: if (!final) sl@0: { sl@0: // if this isn't final SBlock, update predecessor of following SBlock sl@0: nb = (SBlock*)((TUint32)b + size); sl@0: nb->predecessor = nfb; sl@0: } sl@0: b->size = newsize; // original SBlock can't be final sl@0: Free((SBlock*)nfb + 1); sl@0: return cell; sl@0: } sl@0: sl@0: // must move SBlock to expand sl@0: newcell = Alloc(newsize); sl@0: if (newcell) sl@0: { sl@0: memcpy(newcell, cell, size); sl@0: Free(cell); sl@0: } sl@0: return newcell; sl@0: } sl@0: sl@0: TUint32 STlsfAllocator::ConsistencyCheck() sl@0: { sl@0: TUint32 a; sl@0: TUint32 szs = 0; sl@0: TUint32 size; sl@0: TUint32 total_user_size; sl@0: TUint32 total_block_size = 0; sl@0: TUint32 block_count = 0; sl@0: TUint32 flb = 0; sl@0: TUint32 slb[32]; sl@0: TUint32 sli; sl@0: TUint32 fli; sl@0: TUint32 total_free = 0; sl@0: SBlock* b = iff; sl@0: SBlock* pb = 0; sl@0: sl@0: memset(slb, 0, sizeof(slb)); sl@0: __NK_ASSERT_DEBUG(imin_size == 16); sl@0: __NK_ASSERT_DEBUG(insl == 16); sl@0: __NK_ASSERT_DEBUG(il2min == 4); sl@0: __NK_ASSERT_DEBUG(il2nsl == 4); sl@0: __NK_ASSERT_DEBUG(infl == __e32_find_ms1_32(itotal_size) - il2min + 1); sl@0: a = (TUint32)&islb[infl]; sl@0: a = (a+63)&~63; sl@0: __NK_ASSERT_DEBUG(isll == (SFreeBlock**)a); sl@0: a += insl * infl * sizeof(TUint32*); sl@0: __NK_ASSERT_DEBUG(iff == (SBlock*)a); sl@0: total_user_size = itotal_size - (a - (TUint32)this); sl@0: sl@0: do { sl@0: szs = b->size; sl@0: size = szs & BLOCK_SIZE_MASK; sl@0: __NK_ASSERT_DEBUG(b->predecessor == pb); sl@0: __NK_ASSERT_DEBUG(size > 0); sl@0: __NK_ASSERT_DEBUG(size <= total_user_size); sl@0: __NK_ASSERT_DEBUG(size == ((size >> il2min) << il2min)); sl@0: total_block_size += size; sl@0: ++block_count; sl@0: pb = b; sl@0: b = (SBlock*)((TUint32)b + size); sl@0: } while(!(szs & BLOCK_STATUS_FINAL)); sl@0: __NK_ASSERT_DEBUG((TUint32)b == (TUint32)this + itotal_size); sl@0: __NK_ASSERT_DEBUG(total_block_size == total_user_size); sl@0: sl@0: b = iff; sl@0: do { sl@0: szs = b->size; sl@0: size = szs & BLOCK_SIZE_MASK; sl@0: if (szs & BLOCK_STATUS_FREE) sl@0: { sl@0: SFreeBlock* fb = (SFreeBlock*)b; sl@0: SFreeBlock* pfb = fb; sl@0: SFreeBlock* lh; sl@0: TUint32 lhi; sl@0: TInt lh_found = 0; sl@0: TInt c = (TInt)block_count; sl@0: TUint32 fli = __e32_find_ms1_32(size) - il2min; sl@0: TUint32 sli = (size >> il2min) - (1u << fli); sl@0: TUint32 sli2; sl@0: TUint32 fli2 = MapSize(size, &sli2, 0); sl@0: (void)sli2, (void)fli2; sl@0: if (fli > il2nsl) sl@0: sli >>= (fli - il2nsl); sl@0: __NK_ASSERT_DEBUG(fli == fli2); sl@0: __NK_ASSERT_DEBUG(sli == sli2); sl@0: flb |= (1u << fli); sl@0: slb[fli] |= (1u << sli); sl@0: lhi = (fli << il2nsl) | sli; sl@0: lh = isll[lhi]; sl@0: do { sl@0: if (fb == lh) sl@0: lh_found = 1; sl@0: pfb = fb; sl@0: fb = fb->next; sl@0: __NK_ASSERT_DEBUG(fb->prev == pfb); sl@0: __NK_ASSERT_DEBUG(fb->b.size & BLOCK_STATUS_FREE); sl@0: } while ((fb != (SFreeBlock*)b) && --c>=0); sl@0: __NK_ASSERT_DEBUG(fb == (SFreeBlock*)b); sl@0: __NK_ASSERT_DEBUG(lh_found); sl@0: total_free += size; sl@0: } sl@0: b = (SBlock*)((TUint32)b + size); sl@0: } while(!(szs & BLOCK_STATUS_FINAL)); sl@0: sl@0: __NK_ASSERT_DEBUG(flb == iflb); sl@0: for (fli=0; fli sl@0: #include "kernboot.h" sl@0: sl@0: extern "C" { sl@0: void SetupMemoryAllocator() sl@0: { sl@0: const SSuperPageBase& sp = *(const SSuperPageBase*)SuperPageAddress; sl@0: const TRomHeader& romHdr = *(const TRomHeader*)RomHeaderAddress; sl@0: const TRomEntry* primaryEntry = (const TRomEntry*)sp.iPrimaryEntry; sl@0: const TRomImageHeader* primaryImageHeader = (const TRomImageHeader*)primaryEntry->iAddressLin; sl@0: TLinAddr stack = romHdr.iKernDataAddress + round_to_page(romHdr.iTotalSvDataSize); sl@0: TLinAddr heapbase = stack + round_to_page(primaryImageHeader->iStackSize); sl@0: TLinAddr heapsize = sp.iInitialHeapSize; sl@0: sl@0: KPrintf("Heap base %08x size %08x", heapbase, heapsize); sl@0: TheAllocator = STlsfAllocator::Create((TAny*)heapbase, heapsize); sl@0: } sl@0: sl@0: extern TBool InitialThreadDefined; sl@0: sl@0: TAny* malloc(TUint32 aSize) sl@0: { sl@0: // __KTRACE_OPT(KMMU,DEBUGPRINT("malloc(%d)",aSize)); sl@0: if (InitialThreadDefined) sl@0: NKern::FMWait(&AllocMutex); sl@0: TAny* p = TheAllocator->Alloc(aSize); sl@0: if (InitialThreadDefined) sl@0: NKern::FMSignal(&AllocMutex); sl@0: __KTRACE_OPT(KMMU,DEBUGPRINT("malloc(%d)->%08x",aSize,p)); sl@0: return p; sl@0: } sl@0: sl@0: void free(TAny* aCell) sl@0: { sl@0: __KTRACE_OPT(KMMU,DEBUGPRINT("free(%08x)",aCell)); sl@0: #ifdef _DEBUG sl@0: if (aCell) sl@0: { sl@0: SBlock* b = (SBlock*)aCell; sl@0: TUint32 size = b[-1].size & BLOCK_SIZE_MASK; sl@0: memset(aCell, 0xde, size - sizeof(SBlock)); sl@0: } sl@0: #endif sl@0: NKern::FMWait(&AllocMutex); sl@0: TheAllocator->Free(aCell); sl@0: NKern::FMSignal(&AllocMutex); sl@0: } sl@0: sl@0: TAny* realloc(TAny* aCell, TUint32 aSize) sl@0: { sl@0: NKern::FMWait(&AllocMutex); sl@0: TAny* p = TheAllocator->ReAlloc(aCell, aSize); sl@0: NKern::FMSignal(&AllocMutex); sl@0: return p; sl@0: } sl@0: } sl@0: