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