1 /*---------------------------------------------------------------------------*
2 Project: MEM library
3 File: mem_heapCommon.c
4 Programmers: Takano Makoto
5
6 Copyright 2005 Nintendo. All rights reserved.
7
8 These coded instructions, statements, and computer programs contain
9 proprietary information of Nintendo of America Inc. and/or Nintendo
10 Company Ltd., and are protected by Federal copyright law. They may
11 not be disclosed to third parties or copied or duplicated in any form,
12 in whole or in part, without the prior written consent of Nintendo.
13 *---------------------------------------------------------------------------*/
14
15 #include <revolution/mem.h>
16 #include "heapCommoni.h"
17
18 /* ========================================================================
19 static variables
20 ======================================================================== */
21
22 /* ------------------------------------------------------------------------
23 list related
24 ------------------------------------------------------------------------ */
25
26 static MEMList sRootList; // root heap list
27 static BOOL sRootListInitialized = FALSE; // if sRootList is initialized, true
28 static OSMutex sRootMutex; // multi-heap management exclusion controls (24B)
29
30 /* ------------------------------------------------------------------------
31 fill related
32 ------------------------------------------------------------------------ */
33
34 #if defined(_DEBUG)
35
36 static u32 sFillVals[ MEM_HEAP_FILL_MAX ] =
37 {
38 0xC3C3C3C3, // Value to fill with when creating heap
39 0xF3F3F3F3, // Value to fill with when allocating memory block
40 0xD3D3D3D3, // Value to fill with when deallocating memory block
41 };
42
43 // #if defined(_DEBUG)
44 #endif
45
46
47 /* ========================================================================
48 static functions
49 ======================================================================== */
50
51 /* ------------------------------------------------------------------------
52 list related
53 ------------------------------------------------------------------------ */
54
55 /*---------------------------------------------------------------------------*
56 Name: FindContainHeap_
57
58 Description: Recursively searches the heap containing the specified memory block from the list.
59
60
61 Arguments: pList: pointer to list
62 memBlock: pointer to memory block
63
64 Returns: If the heap that allocated the specified memory block is found, returns a pointer to that heap.
65
66 Returns NULL if it is not found.
67 *---------------------------------------------------------------------------*/
68 static MEMiHeapHead*
FindContainHeap_(MEMList * pList,const void * memBlock)69 FindContainHeap_(
70 MEMList* pList,
71 const void* memBlock
72 )
73 {
74 MEMiHeapHead* pHeapHd = NULL;
75 while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(pList, pHeapHd) ) )
76 {
77 if ( GetUIntPtr( pHeapHd->heapStart ) <= GetUIntPtr( memBlock )
78 && GetUIntPtr( memBlock ) < GetUIntPtr( pHeapHd->heapEnd )
79 )
80 {
81 MEMiHeapHead* pChildHeapHd = FindContainHeap_( &pHeapHd->childList, memBlock );
82 if ( pChildHeapHd )
83 {
84 return pChildHeapHd;
85 }
86 return pHeapHd;
87 }
88 }
89 return NULL;
90 }
91
92
93 /*---------------------------------------------------------------------------*
94 Name: FindParentHeap_
95
96 Description: Searches for the parent heap for the specified heap, under the node indicated in the arguments.
97 Arguments: pNodeHeap:
98 pTargetHeap:
99
100 Returns: Returns a pointer to the heap's header when the parent heap is found.
101 Returns NULL if not found.
102 *---------------------------------------------------------------------------*/
103 static MEMiHeapHead*
FindParentHeap_(MEMiHeapHead * pNodeHeap,const MEMiHeapHead * pTargetHeap)104 FindParentHeap_(
105 MEMiHeapHead* pNodeHeap,
106 const MEMiHeapHead* pTargetHeap
107 )
108 {
109 MEMList* pList = &pNodeHeap->childList;
110 MEMiHeapHead* pHeapHd = NULL;
111
112 while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(pList, pHeapHd) ) )
113 {
114 if ( pHeapHd == pTargetHeap )
115 {
116 // is a parent heap if the child heap member and target match
117 return pNodeHeap;
118 }
119
120 // continues the search for children if the target address is included
121 if ( GetUIntPtr( pHeapHd->heapStart ) <= GetUIntPtr( pTargetHeap )
122 && GetUIntPtr( pTargetHeap ) < GetUIntPtr( pHeapHd->heapEnd )
123 )
124 {
125 return FindParentHeap_( pHeapHd, pTargetHeap );
126 }
127 }
128 return NULL;
129 }
130
131 /*---------------------------------------------------------------------------*
132 Name: FindListContainHeap_
133
134 Description: Searches the parent heap that contains the heap, and returns a pointer to the parent heap list.
135
136
137 Arguments: pHeapHd: Pointer to the header of search target heap.
138
139 Returns: Returns a pointer to the child list of the parent heap if a parent heap containing the specified heap was found.
140
141 If the parent heap is not found, a pointer to the root list is returned.
142 *---------------------------------------------------------------------------*/
143 static MEMList*
FindListContainHeap_(const MEMiHeapHead * pHeapHd)144 FindListContainHeap_( const MEMiHeapHead* pHeapHd )
145 {
146 MEMList* pList = &sRootList;
147
148 MEMiHeapHead* pContainHeap = FindContainHeap_( &sRootList, pHeapHd );
149
150 if ( pContainHeap )
151 {
152 pList = &pContainHeap->childList;
153 }
154
155 return pList;
156 }
157
158 /*---------------------------------------------------------------------------*
159 Name: ListContainsHeap_
160
161 Description: Checks whether the specified heap is inside the list.
162
163 Arguments: list: Pointer to the heap list structure
164 heap: Pointer to the heap to be searched for
165
166 Returns: If the list includes the specified heap, TRUE.
167 If the list does not have the specified heap, FALSE.
168 *---------------------------------------------------------------------------*/
169 static BOOL
ListContainsHeap_(MEMList * list,const MEMiHeapHead * heap)170 ListContainsHeap_( MEMList* list, const MEMiHeapHead* heap )
171 {
172 MEMiHeapHead* pHeapHd = NULL;
173
174 while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(list, pHeapHd) ) )
175 {
176 if ( pHeapHd == heap )
177 {
178 return TRUE;
179 }
180 }
181 return FALSE;
182 }
183
184
185 /* ========================================================================
186 External Functions (Non-Public)
187 ======================================================================== */
188
189 /*---------------------------------------------------------------------------*
190 Name: MEMiInitHeapHead
191
192 Description: Initializes the heap header.
193
194 Arguments: pHeapHd: Pointer to the heap header.
195 signature: The signature.
196 heapStart: The start address of heap memory.
197 heapEnd: The end address +1 of heap memory.
198 optFlag: The heap option.
199
200 Returns: None.
201 *---------------------------------------------------------------------------*/
202 void
MEMiInitHeapHead(MEMiHeapHead * pHeapHd,u32 signature,void * heapStart,void * heapEnd,u16 optFlag)203 MEMiInitHeapHead(
204 MEMiHeapHead* pHeapHd,
205 u32 signature,
206 void* heapStart,
207 void* heapEnd,
208 u16 optFlag
209 )
210 {
211 pHeapHd->signature = signature;
212
213 pHeapHd->heapStart = heapStart;
214 pHeapHd->heapEnd = heapEnd;
215
216 pHeapHd->attribute.val = 0;
217
218 SetOptForHeap( pHeapHd, optFlag );
219
220 FillNoUseMemory(
221 pHeapHd,
222 heapStart,
223 GetOffsetFromPtr( heapStart, heapEnd )
224 );
225
226 MEM_INIT_LIST( &pHeapHd->childList, MEMiHeapHead, link );
227
228 // performs initialization when the heap list is first created
229 if ( ! sRootListInitialized )
230 {
231 MEM_INIT_LIST( &sRootList, MEMiHeapHead, link );
232 OSInitMutex( &sRootMutex );
233 sRootListInitialized = TRUE;
234 }
235
236 // Mutex initialization
237 OSInitMutex( &pHeapHd->mutex );
238
239 // addition to the multi-heap list
240 OSLockMutex( &sRootMutex );
241 MEMAppendListObject( FindListContainHeap_( pHeapHd ), pHeapHd );
242 OSUnlockMutex( &sRootMutex );
243
244 }
245
246 /*---------------------------------------------------------------------------*
247 Name: MEMiFinalizeHeap
248
249 Description: Performs common heap cleanup.
250
251 Arguments: pHeapHd: Pointer to the heap header.
252
253 Returns: None.
254 *---------------------------------------------------------------------------*/
255 void
MEMiFinalizeHeap(MEMiHeapHead * pHeapHd)256 MEMiFinalizeHeap( MEMiHeapHead* pHeapHd )
257 {
258 MEMList* pList;
259
260 // deletion from the multi-heap list
261 OSLockMutex( &sRootMutex );
262
263 pList = FindListContainHeap_( pHeapHd );
264 ASSERT( ListContainsHeap_( pList, pHeapHd ) ); // Check whether the heap is inside the tree
265 MEMRemoveListObject( pList, pHeapHd );
266 OSUnlockMutex( &sRootMutex );
267 pHeapHd->signature = 0;
268 }
269
270
271 /*---------------------------------------------------------------------------*
272 Name: MEMiDumpHeapHead
273
274 Description: Displays heap header information.
275
276 Arguments: pHeapHd: Pointer to the heap header.
277
278 Returns: None.
279 *---------------------------------------------------------------------------*/
280 void
MEMiDumpHeapHead(MEMiHeapHead * pHeapHd)281 MEMiDumpHeapHead( MEMiHeapHead* pHeapHd )
282 {
283 OSReport("[OS Foundation ");
284
285 switch ( pHeapHd->signature )
286 {
287 case MEMi_EXPHEAP_SIGNATURE: { OSReport("Exp"); break; }
288 case MEMi_FRMHEAP_SIGNATURE: { OSReport("Frame"); break; }
289 case MEMi_UNTHEAP_SIGNATURE: { OSReport("Unit"); break; }
290 default:
291 ASSERT( FALSE );
292 }
293
294 OSReport(" Heap]\n");
295
296 OSReport(" whole [%p - %p)\n", pHeapHd, pHeapHd->heapEnd);
297 }
298
299
300
301 /* ========================================================================
302 External functions (public)
303 ======================================================================== */
304
305 /*---------------------------------------------------------------------------*
306 Name: MEMFindContainHeap
307
308 Description: Searches for the heap containing the memory block.
309
310 Arguments: memBlock: The memory block to be searched for.
311
312 Returns: If a heap containing the specified memory block was found, returns that heap's handle.
313
314 Returns HEAP_INVALID_HANDLE if not found.
315 *---------------------------------------------------------------------------*/
316 MEMHeapHandle
MEMFindContainHeap(const void * memBlock)317 MEMFindContainHeap( const void* memBlock )
318 {
319 return FindContainHeap_( &sRootList, memBlock );
320 }
321
322
323 /*---------------------------------------------------------------------------*
324 Name: MEMFindParentHeap
325
326 Description: Searches for the parent heap.
327
328 Arguments: memBlock: The memory block to be searched for.
329
330 Returns: If a heap containing the specified memory block was found, returns that heap's handle.
331
332 Returns HEAP_INVALID_HANDLE if not found.
333 *---------------------------------------------------------------------------*/
334 MEMHeapHandle
MEMFindParentHeap(MEMHeapHandle heap)335 MEMFindParentHeap( MEMHeapHandle heap )
336 {
337 MEMiHeapHead* pHeapHd = NULL;
338
339 while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(&sRootList, pHeapHd) ) )
340 {
341 if ( pHeapHd == heap )
342 {
343 return MEM_HEAP_INVALID_HANDLE;
344 }
345 // searches for children if the target address is included
346 if ( GetUIntPtr( pHeapHd->heapStart ) <= GetUIntPtr( heap )
347 && GetUIntPtr( heap ) < GetUIntPtr( pHeapHd->heapEnd )
348 )
349 {
350 return FindParentHeap_( pHeapHd, heap );
351 }
352 }
353 return MEM_HEAP_INVALID_HANDLE;
354 }
355
356
357 #if defined(_DEBUG)
358
359 /*---------------------------------------------------------------------------*
360 Name: MEMDumpHeap
361
362 Description: Displays the information in the heap.
363 This function is used for debugging.
364
365 Arguments: heap: Handle for the frame heap
366
367 Returns: None.
368 *---------------------------------------------------------------------------*/
369
370 void
MEMDumpHeap(MEMHeapHandle heap)371 MEMDumpHeap( MEMHeapHandle heap )
372 {
373 MEMiHeapHead* pHeapHd = heap;
374 switch ( pHeapHd->signature )
375 {
376 case MEMi_EXPHEAP_SIGNATURE:
377 {
378 LockHeap( heap );
379 MEMiDumpExpHeap(heap);
380 UnlockHeap( heap );
381 }
382 break;
383 case MEMi_FRMHEAP_SIGNATURE:
384 {
385 LockHeap( heap );
386 MEMiDumpFrmHeap(heap);
387 UnlockHeap( heap );
388 }
389 break;
390 case MEMi_UNTHEAP_SIGNATURE:
391 {
392 LockHeap( heap );
393 MEMiDumpUnitHeap(heap);
394 UnlockHeap( heap );
395 }
396 break;
397 default:
398 OSReport("[OS Foundation] dump heap : unknown heap. - %p\n", heap);
399 }
400 }
401
402
403 /*---------------------------------------------------------------------------*
404 Name: MEMSetFillValForHeap
405
406 Description: Sets the fill value used when creating the heap and allocating/deallocating memory blocks.
407
408 This function is for use in debugging.
409 Always returns 0 in the final ROM version library.
410
411 Arguments: type: the type of value to get
412 val: the value to set
413
414 Returns: Returns the previous value that was set in memory when the memory block was allocated.
415 *---------------------------------------------------------------------------*/
416 u32
MEMSetFillValForHeap(int type,u32 val)417 MEMSetFillValForHeap(
418 int type,
419 u32 val
420 )
421 {
422 ASSERT( type < MEM_HEAP_FILL_MAX );
423
424 {
425 u32 oldVal = sFillVals[type];
426 sFillVals[type] = val;
427 return oldVal;
428 }
429 }
430
431
432 /*---------------------------------------------------------------------------*
433 Name: MEMGetFillValForHeap
434
435 Description: Gets the fill value used when creating the heap and allocating/deallocating memory blocks.
436
437 This function is for use in debugging.
438 Always returns 0 in the final ROM version library.
439
440 Arguments: type: the type of value to get
441
442 Returns: Returns the value set in the memory of the type specified.
443 *---------------------------------------------------------------------------*/
444 u32
MEMGetFillValForHeap(int type)445 MEMGetFillValForHeap( int type )
446 {
447 ASSERT( type < MEM_HEAP_FILL_MAX );
448
449 return sFillVals[ type ];
450 }
451
452 // #if defined(_DEBUG)
453 #endif
454
455