1 // Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies).

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // Classes which implement a circular doubly linked list of DMemoryMappingBase objects.

    15 // 

    16 //

    17 

    18 /**

    19  @file

    20  @internalComponent

    21 */

    22 

    23 #ifndef MMAPPINGLIST_H

    24 #define MMAPPINGLIST_H

    25 

    26 #include <kernel.h>

    27 #include <nk_priv.h>

    28 

    29 class DMemoryMappingBase;

    30 

    31 

    32 

    33 //

    34 // TMappingListBase

    35 //

    36 

    37 /**

    38 Base class implementing basic list insertion and removal functionality for memory mapping lists.

    39 */

    40 class TMappingListBase

    41 	{

    42 #ifdef _DEBUG

    43 public:

    44 	/**

    45 	Debug check returning true if iSpinLock is held by the current thread.

    46 	In reality this just checks that interrupts are currently disabled as spinlocks

    47 	do not support identifying the thread which holds it.

    48 	*/

    49 	FORCE_INLINE TBool LockIsHeld()

    50 		{

    51 		return InterruptsStatus(false);

    52 		}

    53 #endif

    54 

    55 protected:

    56 	/** Class type id of this object, this is stored in iType. */

    57 	enum TType

    58 		{

    59 		EHead = 1,	///< This object is a TMappingList object

    60 		ELink,		///< This object is a TMappingListLink object

    61 		EIter		///< This object is a TMappingListIter object

    62 		};

    63 

    64 	FORCE_INLINE TMappingListBase(TType aType)

    65 		: iType(aType)

    66 		{

    67 		KillLink();

    68 		}

    69 

    70 	/** Remove this link from the list it is in. */

    71 	FORCE_INLINE void Remove()

    72 		{

    73 		__NK_ASSERT_DEBUG(!IsLinkDead());

    74 		TMappingListBase* next = iNext;

    75 		TMappingListBase* prev = iPrev;

    76 		next->iPrev=prev;

    77 		prev->iNext=next;

    78 		KillLink();

    79 		}

    80 

    81 	/** Insert this link after \a aPrev */

    82 	FORCE_INLINE void InsertAfter(TMappingListBase* aPrev)

    83 		{

    84 		__NK_ASSERT_DEBUG(IsLinkDead());

    85 		TMappingListBase* next = aPrev->iNext;

    86 		iPrev = aPrev;

    87 		iNext = next;

    88 		next->iPrev = this;

    89 		aPrev->iNext = this;

    90 		}

    91 

    92 	/** Insert this link before \a aNext */

    93 	FORCE_INLINE void InsertBefore(TMappingListBase* aNext)

    94 		{

    95 		__NK_ASSERT_DEBUG(IsLinkDead());

    96 		TMappingListBase* prev = aNext->iPrev;

    97 		iNext = aNext;

    98 		iPrev = prev;

    99 		aNext->iPrev = this;

   100 		prev->iNext = this;

   101 		}

   102 

   103 	/**

   104 	In debug builds, munge the iNext and iPrev link values so that if

   105 	they are used an exception is likely.

   106 	*/

   107 	FORCE_INLINE void KillLink()

   108 		{

   109 		#ifdef _DEBUG

   110 			iNext = (TMappingListBase*)KILL_LINK_VALUE;

   111 			iPrev = (TMappingListBase*)KILL_LINK_VALUE;

   112 		#endif

   113 		}

   114 

   115 #ifdef _DEBUG

   116 

   117 	/** Debug check returning true if this link is 'dead', i.e. been killed with KillLink. */

   118 	FORCE_INLINE TBool IsLinkDead()

   119 		{

   120 		// we don't check iNext here because that may have been set to null by

   121 		// TMappingListLink as a non-debug indicator of a link not in a list.

   122 		return iPrev==(TMappingListBase*)KILL_LINK_VALUE;

   123 		}

   124 #endif

   125 

   126 protected:

   127 	TMappingListBase* iNext;	///< Next item in list.

   128 	TMappingListBase* iPrev;	///< Previous item in list.

   129 	TUint8 iType; 				///< Value from enum TType which identifies this object's derived type.

   130 public:

   131 	TUint8 iSpare1;				///< Unused storage available for any purpose.

   132 	TUint8 iSpare2;				///< Unused storage available for any purpose.

   133 	TUint8 iSpare3;				///< Unused storage available for any purpose.

   134 

   135 protected:

   136 	static TSpinLock iSpinLock;	///< Global spinlock used for manipulating all lists.

   137 

   138 	friend class TMappingListIter;

   139 	};

   140 

   141 

   142 //

   143 // TMappingList

   144 //

   145 

   146 /**

   147 Head of a circular doubly linked list of DMemoryMappingBase objects.

   148 */

   149 class TMappingList : public TMappingListBase

   150 	{

   151 public:

   152 	/** Construct an empty list. */

   153 	FORCE_INLINE TMappingList()

   154 		: TMappingListBase(EHead)

   155 		{

   156 		iNext = this;

   157 		iPrev = this;

   158 		}

   159 

   160 	/** Destructor which asserts in debug builds that this list is empty. */

   161 	FORCE_INLINE ~TMappingList()

   162 		{

   163 		__NK_ASSERT_DEBUG(IsEmpty());

   164 		}

   165 

   166 	/**

   167 	Add \a aMapping to the end of this list.

   168 	@pre The list must be locked with #Lock.

   169 	*/

   170 	void Add(DMemoryMappingBase* aMapping);

   171 

   172 	/**

   173 	Remove \a aMapping from this list.

   174 	@pre The list must be locked with #Lock.

   175 	*/

   176 	void Remove(DMemoryMappingBase* aMapping);

   177 

   178 	/**

   179 	Lock the list to prevent other threads changing it.

   180 	This is a spinlock so all operations with the lock held must be very sort.

   181 	@see Unlock

   182 	*/

   183 	FORCE_INLINE void Lock()

   184 		{

   185 		__NK_ASSERT_DEBUG(!LockIsHeld());

   186 		__SPIN_LOCK_IRQ(iSpinLock);

   187 		}

   188 

   189 	/**

   190 	Reverse the action of #Lock.

   191 	*/

   192 	FORCE_INLINE void Unlock()

   193 		{

   194 		__NK_ASSERT_DEBUG(LockIsHeld());

   195 		__SPIN_UNLOCK_IRQ(iSpinLock);

   196 		}

   197 

   198 	/** Return true if this list is empty */

   199 	FORCE_INLINE TBool IsEmpty() const

   200 		{

   201 		return iNext==(TMappingListBase*)this;

   202 		}

   203 

   204 	// Utility methods to call a method on every element of a list

   205 

   206 	/**

   207 	Update the page table entry for a specified page in all mappings in the list that contain it.

   208 

   209 	@param aPages				The page array entry of the page in a memory object. 

   210 								Only array entries which have a target state of 

   211 								RPageArray::ECommitted should be mapped into the 

   212 								mapping's page tables.

   213 

   214 	@param aIndex				The index of the page in the memory object.

   215 

   216 	@param aMapInstanceCount	The instance of this mapping which is to be updated.

   217 								Whenever this no longer matches the current #MapInstanceCount

   218 								the function must not update any more of the mapping's

   219 								page table entries, (but must still return KErrNone).

   220 

   221 	@param	aInvalidateTLB		Set to ETrue when the TLB entries associated with this page

   222 								should be invalidated.  This must be done when there is 

   223 								already a valid pte for this page, i.e. if the page is still 

   224 								mapped.

   225 

   226 	@see #DMemoryMappingBase::RemapPage

   227 	*/

   228 	void RemapPage(TPhysAddr& aPageArray, TUint aIndex, TBool aInvalidateTLB);	

   229 	};

   230 

   231 

   232 

   233 //

   234 // TMappingListLink

   235 //

   236 

   237 /**

   238 A link in a circular doubly linked list of DMemoryMappingBase objects.

   239 This object is the member DMemoryMappingBase::iLink.

   240 */

   241 class TMappingListLink : public TMappingListBase

   242 	{

   243 public:

   244 	/** Construct a link which is not part of any list. */

   245 	FORCE_INLINE TMappingListLink()

   246 		: TMappingListBase(ELink)

   247 		{

   248 		// iNext is the null pointer when link is not on list...

   249 		iNext = 0;

   250 		}

   251 

   252 	/** Destructor which asserts in debug builds that this link isn't in a list. */

   253 	FORCE_INLINE ~TMappingListLink()

   254 		{

   255 		__NK_ASSERT_DEBUG(!IsLinked());

   256 		}

   257 

   258 	/** Return true if link is in any list. */

   259 	FORCE_INLINE TBool IsLinked()

   260 		{

   261 		return iNext!=0;

   262 		}

   263 

   264 private:

   265 	/**

   266 	Remove this link from the list it is in.

   267 	This is for use by class TMappingList.

   268 	*/

   269 	FORCE_INLINE void Remove()

   270 		{

   271 		__NK_ASSERT_DEBUG(LockIsHeld());

   272 		__NK_ASSERT_DEBUG(iNext);

   273 		TMappingListBase::Remove();

   274 		iNext = 0;

   275 		}

   276 

   277 	friend class TMappingList;

   278 	};

   279 

   280 

   281 

   282 //

   283 // TMappingListIter

   284 //

   285 

   286 /**

   287 An iterator for visiting all memory mappings in a list.

   288 

   289 The iterator object itself is linked into the list so that mappings can safely

   290 be removed and added to the list whilst it is being iterated. As new mappings

   291 are only ever added to the end of the list, this ensures that once the iterator

   292 reaches the end of the list it has found all mappings currently present.

   293 

   294 As the spinlock used to guard lists disables interrupts it is very important

   295 to only hold the lock for a very short and bounded time. Specifically, as the

   296 Next() function doesn't necessarily release the lock, any loop iterating over

   297 a list must take care to Unlock() then Lock() again sufficiently often to avoid

   298 adversely impacting interrupt latency.

   299 

   300 Example usage...

   301 

   302 @code

   303 	DMemoryObject* memory;

   304 	memory->iMappings.Lock();

   305 	TMappingListIter iter;

   306 	DMemoryMappingBase* mapping = iter.Start(memory->iMappings);

   307 	while(mapping)

   308 		{

   309 		mapping->Open();

   310 		memory->iMappings.Unlock();

   311 		// mapping may now be used without risk of it being deleted;

   312 		// however, it may still be removed from the list and updated/reused

   313 		// therefore caution must be exercised

   314 		mapping->Close();

   315 		memory->iMappings.Lock();

   316 		mapping = iter.Next();

   317 		}

   318 	iter.Finish();

   319 	memory->iMappings.Unlock();

   320 @endcode

   321 */

   322 class TMappingListIter : public TMappingListBase

   323 	{

   324 public:

   325 	FORCE_INLINE TMappingListIter()

   326 		: TMappingListBase(EIter)

   327 		{

   328 		}

   329 

   330 	/** Destructor which asserts in debug builds that this iterator isn't attached to a list. */

   331 	FORCE_INLINE ~TMappingListIter()

   332 		{

   333 		// check that this isn't still linked into a list...

   334 		__NK_ASSERT_DEBUG(IsLinkDead());

   335 		}

   336 

   337 	/**

   338 	Attach this iterator to list \a aList and return the first mapping in that list.

   339 	The null pointer is returned if the list is empty.

   340 

   341 	Must only be called on a newly constructed iterator object, or after #Finish

   342 	has removed this iterator from a list.

   343 

   344 	@pre The list must be locked with TMappingList::Lock

   345 	*/

   346 	DMemoryMappingBase* Start(TMappingList& aList);

   347 

   348 	/**

   349 	Return the next mapping in the list after the previous one returned by either

   350 	#Start or #Next. The null pointer is returned if the list end has been reached.

   351 

   352 	During its operation, this function may or may not have unlocked the list using

   353 	TMappingList::Unlock. Therefore, when using Next() in a loop, care care must be

   354 	taken to unlock the list sufficiently often to avoid adversely impacting interrupt

   355 	latency.

   356 

   357 	@pre The list must be locked with TMappingList::Lock.

   358 	@pre The iterator must have been previously attached to a list with #Start and not

   359 		 since been removed with #Finish.

   360 

   361 	@post The list will be locked with TMappingList::Lock but this lock may have been

   362 		  released for a period of time by the function during its operation.

   363 	*/

   364 	DMemoryMappingBase* Next();

   365 

   366 	/**

   367 	Remove this iterator from the list it has been attached to.

   368 

   369 	@pre The list must be locked with TMappingList::Lock

   370 	@pre The iterator must have been previously attached to a list with #Start and not

   371 		 since been removed with #Finish.

   372 	*/

   373 	void Finish();

   374 

   375 private:

   376 	/** Implementation factor for #Start and #Next() */

   377 	DMemoryMappingBase* Next(TMappingListBase* aPrev);

   378 	};

   379 

   380 

   381 

   382 #endif