--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/kernel/eka/memmodel/epoc/flexible/mmu/maddrcont.cpp Mon Oct 19 15:55:17 2009 +0100
@@ -0,0 +1,337 @@
+// Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies).
+// All rights reserved.
+// This component and the accompanying materials are made available
+// under the terms of the License "Eclipse Public License v1.0"
+// which accompanies this distribution, and is available
+// at the URL "http://www.eclipse.org/legal/epl-v10.html".
+//
+// Initial Contributors:
+// Nokia Corporation - initial contribution.
+//
+// Contributors:
+//
+// Description:
+//
+
+#include <kernel/kern_priv.h>
+#include "maddrcont.h"
+
+RAddressedContainer::RAddressedContainer(NFastMutex* aReadLock, DMutex*& aWriteLock)
+ : iMaxCount(0), iCount(0), iList(0), iReadLock(aReadLock), iWriteLock(aWriteLock)
+ {}
+
+
+RAddressedContainer::~RAddressedContainer()
+ {
+ Kern::Free(iList);
+ }
+
+
+const TUint MinCount = 8; // must be power of two
+
+FORCE_INLINE TUint RAddressedContainer::CalculateGrow()
+ {
+ TUint newMax = iMaxCount;
+
+ if(newMax<MinCount)
+ newMax = MinCount;
+ else
+ newMax <<= 1;
+ return newMax;
+ }
+
+
+TUint RAddressedContainer::CalculateShrink(TUint aCount)
+ {
+ TUint newMax = iMaxCount;
+ if(!aCount)
+ return 0; // empty container should have zero max size
+
+#ifndef _DEBUG
+ // we want at least 'MinCount' free slots after shrinking for hysteresis,
+ // but not in UDEB builds because OOM testing will barf...
+ aCount += MinCount;
+#endif
+
+ TUint tryMax = newMax;
+ do
+ {
+ newMax = tryMax;
+ tryMax >>= 1;
+ }
+ while(tryMax>=aCount);
+
+ if(newMax<MinCount)
+ newMax = MinCount;
+
+ return newMax;
+ }
+
+
+TBool RAddressedContainer::CheckWriteLock()
+ {
+ if(K::Initialising)
+ return true; // check disabled during boot as we are single threaded at that point
+ if(!iWriteLock)
+ return false;
+ if((((TLinAddr)iWriteLock)&1))
+ return true; // its a lock from DMutexPool, we can't check that, assume it's OK
+ return iWriteLock->iCleanup.iThread==&Kern::CurrentThread();
+ }
+
+
+#ifdef _DEBUG
+const TUint KMaxEntriesInOneGo = 4; // small number to improve test coverage
+#else
+const TUint KMaxEntriesInOneGo = 32; // to produce a similar worst case number of cache line accesses to the binary search
+#endif
+
+TInt RAddressedContainer::Add(TLinAddr aAddress, TAny* aObject)
+ {
+ __NK_ASSERT_DEBUG(aObject);
+ __ASSERT_CRITICAL;
+ __NK_ASSERT_DEBUG(CheckWriteLock());
+
+#ifdef _DEBUG
+ if(K::CheckForSimulatedAllocFail())
+ {
+ __KTRACE_OPT(KMMU,Kern::Printf("RAddressedContainer::Add returns simulated OOM %d",KErrNoMemory));
+ return KErrNoMemory;
+ }
+#endif
+
+ // find list insertion point...
+ TUint i = FindIndex(aAddress);
+
+ if(iCount<iMaxCount)
+ {
+ // insert new entry...
+ ReadLock();
+
+ // make room by shuffling entries up in the array KMaxEntriesInOneGo at a time...
+ TEntry* entry = iList+i;
+ TEntry* prev = iList+iCount;
+ ++iCount; // must do this before releasing read lock for the first time
+ for(;;)
+ {
+ TEntry* next = prev-KMaxEntriesInOneGo;
+ if(next<=entry)
+ {
+ // move the final remaining entries...
+ wordmove(entry+1,entry,(TUintPtr)prev-(TUintPtr)entry);
+ break;
+ }
+ wordmove(next+1,next,(TUintPtr)prev-(TUintPtr)next);
+ prev = next;
+ // flash the read lock to give readers a chance to look at the list...
+ ReadFlash();
+ // Note, readers may see a duplicate entry in the list at 'prev' but this
+ // is OK as the Find functions will still work.
+ }
+
+ // copy in new entry...
+ entry->iAddress = aAddress;
+ entry->iObject = aObject;
+
+ ReadUnlock();
+ }
+ else
+ {
+ // list memory needs expanding...
+ TUint newMaxCount = CalculateGrow();
+
+ // allocate new memory...
+ TEntry* newList = (TEntry*)Kern::Alloc(sizeof(TEntry)*newMaxCount);
+ if(!newList)
+ return KErrNoMemory;
+ #ifdef _DEBUG
+ if(iList)
+ K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newList);
+ #endif
+ iMaxCount = newMaxCount;
+
+ // copy list to new memory, and insert new entry...
+ wordmove(newList,iList,sizeof(TEntry)*i);
+ TEntry* entry = newList+i;
+ entry->iAddress = aAddress;
+ entry->iObject = aObject;
+ wordmove(entry+1,iList+i,sizeof(TEntry)*(iCount-i));
+
+ // start using new list...
+ TEntry* oldList = iList;
+ ReadLock();
+ iList = newList;
+ ++iCount;
+ ReadUnlock();
+
+ // free memory used for old list...
+ Kern::Free(oldList);
+ }
+
+ return KErrNone;
+ }
+
+
+TAny* RAddressedContainer::Remove(TLinAddr aAddress)
+ {
+ __ASSERT_CRITICAL;
+ __NK_ASSERT_DEBUG(CheckWriteLock());
+
+ // search for it...
+ TUint i = FindIndex(aAddress);
+ TEntry* entry = iList+i-1;
+
+ if(!i || entry->iAddress!=aAddress)
+ {
+ // not found...
+ return 0;
+ }
+ --i; // make 'i' the index of entry to remove
+
+ // get object...
+ TAny* result = entry->iObject;
+ __NK_ASSERT_DEBUG(result);
+
+ TUint newMaxCount = CalculateShrink(iCount-1);
+
+ if(newMaxCount>=iMaxCount)
+ {
+remove_without_resize:
+ // remove old entry...
+ ReadLock();
+
+ // shuffling entries down in the array KMaxEntriesInOneGo at a time...
+ TEntry* prev = iList+i+1;
+ TEntry* end = iList+iCount;
+ for(;;)
+ {
+ TEntry* next = prev+KMaxEntriesInOneGo;
+ if(next>=end)
+ {
+ // move the final remaining entries...
+ wordmove(prev-1,prev,(TUintPtr)end-(TUintPtr)prev);
+ break;
+ }
+ wordmove(prev-1,prev,(TUintPtr)next-(TUintPtr)prev);
+ prev = next;
+ // flash the read lock to give readers a chance to look at the list...
+ ReadFlash();
+ // Note, readers may see a duplicate entry at the end of the list but this
+ // is OK as the Find functions will still work.
+ }
+
+ --iCount; // must do this after moving all the entries
+ ReadUnlock();
+ }
+ else
+ {
+ // list memory needs shrinking...
+
+ // allocate new memory...
+ TEntry* newList = 0;
+ if(newMaxCount)
+ {
+ newList = (TEntry*)Kern::Alloc(sizeof(TEntry)*newMaxCount);
+ if(!newList)
+ goto remove_without_resize; // have no memory to shrink array
+ #ifdef _DEBUG
+ if(iList)
+ K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newList);
+ #endif
+ }
+ iMaxCount = newMaxCount;
+
+ // copy list to new memory, deleting removed entry...
+ wordmove(newList,iList,sizeof(TEntry)*i);
+ wordmove(newList+i,iList+i+1,sizeof(TEntry)*(iCount-i-1));
+
+ // start using new list...
+ TEntry* oldList = iList;
+ ReadLock();
+ iList = newList;
+ --iCount;
+ ReadUnlock();
+
+ // free memory used for old list...
+ Kern::Free(oldList);
+ }
+
+ return result;
+ }
+
+
+TAny* RAddressedContainer::Find(TLinAddr aAddress)
+ {
+ if(iReadLock)
+ __NK_ASSERT_DEBUG(iReadLock->HeldByCurrentThread());
+ else
+ __NK_ASSERT_DEBUG(CheckWriteLock());
+
+ TUint i = FindIndex(aAddress);
+ TEntry* entry = iList+i;
+ if(i==0)
+ return 0;
+ --entry;
+
+ if(aAddress!=entry->iAddress)
+ return 0;
+
+ TAny* result = entry->iObject;
+ __NK_ASSERT_DEBUG(result);
+ return result;
+ }
+
+
+TAny* RAddressedContainer::Find(TLinAddr aAddress, TUint& aOffset)
+ {
+ if(iReadLock)
+ __NK_ASSERT_DEBUG(iReadLock->HeldByCurrentThread());
+ else
+ __NK_ASSERT_DEBUG(CheckWriteLock());
+
+ TUint i = FindIndex(aAddress);
+ TEntry* entry = iList+i;
+ if(i==0)
+ return 0;
+ --entry;
+
+ aOffset = aAddress-entry->iAddress;
+
+ TAny* result = entry->iObject;
+ __NK_ASSERT_DEBUG(result);
+ return result;
+ }
+
+
+TUint RAddressedContainer::FindIndex(TLinAddr aAddress)
+ {
+ TEntry* list = iList;
+#if 0
+ // linear search from end...
+ TUint count = iCount;
+ while(count)
+ {
+ if(list[count-1].iAddress<=aAddress)
+ break;
+ --count;
+ }
+ return count;
+#else
+ // binary search...
+ TUint l = 0;
+ TUint r = iCount;
+ TUint m;
+ while(l<r)
+ {
+ m = (l+r)>>1;
+ TUint32 x = list[m].iAddress;
+ if(x<=aAddress)
+ l = m+1;
+ else
+ r = m;
+ }
+ return r;
+#endif
+ }
+
+