1 /*---------------------------------------------------------------------------*
2 Project: TwlSDK - OS
3 File: os_alloc.c
4
5 Copyright 2003-2008 Nintendo. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Date:: 2008-09-17#$
14 $Rev: 8556 $
15 $Author: okubata_ryoma $
16
17 *---------------------------------------------------------------------------*/
18 #include <nitro/os.h>
19 #include <nitro/os/common/alloc.h>
20
21 /*---------------------------------------------------------------------------*
22 Error messages of OSAlloc.c
23 *---------------------------------------------------------------------------*/
24 #define OS_ERR_ALLOCFROMHEAP_NOHEAP "OS_AllocFromHeap(): heap is not initialized."
25 #define OS_ERR_ALLOCFROMHEAP_INVSIZE "OS_AllocFromHeap(): invalid size."
26 #define OS_ERR_ALLOCFROMHEAP_INVHEAP "OS_AllocFromHeap(): invalid heap handle."
27 #define OS_ERR_ALLOCFROMHEAP_BROKENHEAP "OS_AllocFromHeap(): heap is broken."
28 #define OS_ERR_ALLOCFIXED_NOHEAP "OS_AllocFixed(): heap is not initialized."
29 #define OS_ERR_ALLOCFIXED_INVRANGE "OS_AllocFixed(): invalid range."
30 #define OS_ERR_FREETOHEAP_NOHEAP "OS_FreeToHeap(): heap is not initialized."
31 #define OS_ERR_FREETOHEAP_INVPTR "OS_FreeToHeap(): invalid pointer."
32 #define OS_ERR_FREETOHEAP_INVHEAP "OS_FreeToHeap(): invalid heap handle."
33 #define OS_ERR_SETCURRENTHEAP_NOHEAP "OS_SetCurrentHeap(): heap is not initialized."
34 #define OS_ERR_SETCURRENTHEAP_INVHEAP "OS_SetCurrentHeap(): invalid heap handle."
35 #define OS_ERR_INITALLOC_INVNUMHEAPS "OS_InitAlloc(): invalid number of heaps."
36 #define OS_ERR_INITALLOC_INVRANGE "OS_InitAlloc(): invalid range."
37 #define OS_ERR_INITALLOC_INSRANGE "OS_InitAlloc(): too small range."
38 #define OS_ERR_CLEARALLOC_INVID "OS_ClearAlloc(): invalid arena id."
39 #define OS_ERR_CREATEHEAP_NOHEAP "OS_CreateHeap(): heap is not initialized."
40 #define OS_ERR_CREATEHEAP_INVRANGE "OS_CreateHeap(): invalid range."
41 #define OS_ERR_CREATEHEAP_INSRANGE "OS_CreateHeap(): too small range."
42 #define OS_ERR_DESTROYHEAP_NOHEAP "OS_DestroyHeap(): heap is not initialized."
43 #define OS_ERR_DESTROYHEAP_INVHEAP "OS_DestroyHeap(): invalid heap handle."
44 #define OS_ERR_ADDTOHEAP_NOHEAP "OS_AddToHeap(): heap is not initialized."
45 #define OS_ERR_ADDTOHEAP_INVHEAP "OS_AddToHeap(): invalid heap handle."
46 #define OS_ERR_ADDTOHEAP_INVRANGE "OS_AddToHeap(): invalid range."
47 #define OS_ERR_ADDTOHEAP_INSRANGE "OS_AddToHeap(): too small range."
48 #define OS_ERR_REFERENT_NOHEAP "OS_ReferentSize(): heap is not initialized."
49 #define OS_ERR_REFERENT_INVPTR "OS_ReferentSize(): invalid pointer."
50 #define OS_ERR_DUMPHEAP_NOHEAP "OS_DumpHeap(): heap is not initialized."
51 #define OS_ERR_DUMPHEAP_INVHEAP "OS_DumpHeap(): invalid heap handle."
52 #define OS_ERR_DUMPHEAP_BROKENHEAP "OS_DumpHeap(): heap is broken."
53 #define OS_ERR_ALLOCFROMHEAP_INVID "OS_AllocFromHeap(): illegal arena id."
54 #define OS_ERR_ALLOCFROMHEAP_NOINFO "OS_AllocFromHeap(): heap not initialized."
55 #define OS_ERR_ALLOCFIXED_INVID "OS_AllocFixed(): illegal arena id."
56 #define OS_ERR_ALLOCFIXED_NOINFO "OS_AllocFixed(): heap not initialized."
57 #define OS_ERR_FREETOHEAP_INVID "OS_FreeToHeap(): illegal arena id."
58 #define OS_ERR_FREETOHEAP_NOINFO "OS_FreeToHeap(): heap not initialized."
59 #define OS_ERR_SETCURRENTHEAP_INVID "OS_SetCurrentHeap(): illegal arena id."
60 #define OS_ERR_SETCURRENTHEAP_NOINFO "OS_SetCurrentHeap(): heap not initialized."
61 #define OS_ERR_INITALLOC_INVID "OS_SetInitAlloc(): illegal arena id."
62 #define OS_ERR_INITALLOC_INVINFO "OS_SetInitAlloc(): heap already initialized."
63 #define OS_ERR_CREATEHEAP_INVID "OS_CreateHeap(): illegal arena id."
64 #define OS_ERR_CREATEHEAP_NOINFO "OS_CreateHeap(): heap not initialized."
65 #define OS_ERR_DESTROYHEAP_INVID "OS_DestroyHeap(): illegal arena id."
66 #define OS_ERR_DESTROYHEAP_NOINFO "OS_DestroyHeap(): heap not initialized."
67 #define OS_ERR_ADDTOHEAP_INVID "OS_AddToHeap(): illegal arena id."
68 #define OS_ERR_ADDTOHEAP_NOINFO "OS_AddToHeap(): heap not initialized."
69 #define OS_ERR_CHECKHEAP_INVID "OS_CheckHeap(): illegal arena id."
70 #define OS_ERR_CHECKHEAP_NOINFO "OS_CheckHeap(): heap not initialized."
71 #define OS_ERR_REFERENTSIZE_INVID "OS_ReferentSize(): illegal arena id."
72 #define OS_ERR_REFERENTSIZE_NOINFO "OS_ReferrentSize(): heap not initialized."
73 #define OS_ERR_DUMPHEAP_INVID "OS_DumpHeap(): illegal arena id."
74 #define OS_ERR_DUMPHEAP_NOINFO "OS_DumpHeap(): heap not initialized."
75 #define OS_ERR_VISITALLOCATED_INVID "OS_VisitAllocated(): illegal arena id."
76 #define OS_ERR_VISITALLOCATED_NOINFO "OS_VisitAllocated(): heap not initialized."
77
78
79 #define OFFSET(n, a) (((u32) (n)) & ((a) - 1))
80 #define TRUNC(n, a) (((u32) (n)) & ~((a) - 1))
81 #define ROUND(n, a) (((u32) (n) + (a) - 1) & ~((a) - 1))
82
83 #define ALIGNMENT 32 // alignment in bytes
84 #define MINOBJSIZE (HEADERSIZE + ALIGNMENT) // smallest object
85 #define HEADERSIZE ROUND(sizeof(Cell), ALIGNMENT)
86
87 //---- InRange(): True if a <= targ < b
88 #define InRange(targ, a, b) \
89 ((u32)(a) <= (u32)(targ) && (u32)(targ) < (u32)(b))
90
91 //---- RangeOverlap(): True if the ranges a and b overlap in any way.
92 #define RangeOverlap(aStart, aEnd, bStart, bEnd) \
93 ((u32)(bStart) <= (u32)(aStart) && (u32)(aStart) < (u32)(bEnd) || \
94 (u32)(bStart) < (u32)(aEnd) && (u32)(aEnd) <= (u32)(bEnd))
95
96 //---- RangeSubset(): True if range a is a subset of range b
97 // Assume (aStart < aEnd) and (bStart < bEnd)
98 #define RangeSubset(aStart, aEnd, bStart, bEnd) \
99 ((u32)(bStart) <= (u32)(aStart) && (u32)(aEnd) <= (u32)(bEnd))
100
101 typedef struct Cell Cell;
102 typedef struct HeapDesc HeapDesc;
103
104 // Cell: header of object which resides HEADERSIZE bytes before payload.
105 // doubly linked list are needed because of non-contiguous heaps
106 struct Cell
107 {
108 Cell *prev;
109 Cell *next;
110 long size; // size of object plus HEADERSIZE
111
112 #ifdef SDK_DEBUG
113 HeapDesc *hd; // from which the block is allocated
114 // (NULL in free list).
115 long requested; // size of object to have been requested
116 #endif // SDK_DEBUG
117 };
118
119 struct HeapDesc
120 {
121 long size; // if -1 then heap is free. Note OS_AllocFixed()
122 // could make a heap empty.
123 Cell *free; // pointer to the first free cell
124 Cell *allocated; // pointer to the first used cell
125
126 #ifdef SDK_DEBUG
127 u32 paddingBytes;
128 u32 headerBytes;
129 u32 payloadBytes;
130 #endif // SDK_DEBUG
131 };
132
133
134 //----------------
135 //---- struct of Heap infomation
136 typedef struct
137 {
138 // volatile because some functions use this as hidden macro parameter
139 volatile OSHeapHandle currentHeap;
140 int numHeaps;
141 void *arenaStart;
142 void *arenaEnd;
143 HeapDesc *heapArray;
144 }
145 OSHeapInfo;
146
147 void *OSiHeapInfo[OS_ARENA_MAX] = {
148 NULL,
149 NULL,
150 NULL,
151 NULL,
152 NULL,
153 NULL,
154 NULL,
155 NULL,
156 NULL
157 }; // because OS_ARENA_MAX = 9
158
159 //================================================================================
160 /*---------------------------------------------------------------------------*
161 Name: DLAddFront
162
163 Description: Inserts /cell/ into the head of the list pointed to by /list/
164
165 Arguments: list : pointer to the first cell in the list
166 cell : pointer to a cell to be inserted
167
168 Returns: a pointer to the new first cell
169 *---------------------------------------------------------------------------*/
DLAddFront(Cell * list,Cell * cell)170 static Cell *DLAddFront(Cell * list, Cell * cell)
171 {
172 cell->next = list;
173 cell->prev = NULL;
174 if (list)
175 {
176 list->prev = cell;
177 }
178 return cell;
179 }
180
181 /*---------------------------------------------------------------------------*
182 Name: DLLookup
183
184 Description: Returns /cell/ if /cell/ is found in /list/.
185
186 Arguments: list : pointer to the first cell in the list
187 cell : pointer to a cell to look for
188
189 Returns: /cell/ if /cell/ is in /list/. Otherwise, NULL.
190 *---------------------------------------------------------------------------*/
DLLookup(Cell * list,Cell * cell)191 static Cell *DLLookup(Cell * list, Cell * cell)
192 {
193 for (; list; list = list->next)
194 {
195 if (list == cell)
196 {
197 return list;
198 }
199 }
200 return NULL;
201 }
202
203 /*---------------------------------------------------------------------------*
204 Name: DLExtract
205
206 Description: Extracts /target/ from the list pointed to by /list/.
207 If /target/ is at the head of the list, /list/ will be changed
208 to reflect its removal.
209
210 Arguments: list : pointer to the first cell in the list
211 cell : pointer to a cell to remove
212
213 Returns: a pointer to the new first cell
214 *---------------------------------------------------------------------------*/
DLExtract(Cell * list,Cell * cell)215 static Cell *DLExtract(Cell * list, Cell * cell)
216 {
217 if (cell->next)
218 {
219 cell->next->prev = cell->prev;
220 }
221
222 if (cell->prev == NULL)
223 {
224 return cell->next;
225 }
226 else
227 {
228 cell->prev->next = cell->next;
229 return list;
230 }
231 }
232
233 /*---------------------------------------------------------------------------*
234 Name: DLInsert
235
236 Description: Inserts /cell/ into the list pointed to by /list/ in sorted
237 order by address. Also attempts to coalesce forward and
238 backward blocks if possible.
239
240 Arguments: list : pointer to the first cell in the list
241 cell : pointer to a cell to be inserted
242
243 Returns: a pointer to the new first cell
244 *---------------------------------------------------------------------------*/
DLInsert(Cell * list,Cell * cell)245 static Cell *DLInsert(Cell * list, Cell * cell)
246 {
247 Cell *prev;
248 Cell *next;
249
250 for (next = list, prev = NULL; next; prev = next, next = next->next)
251 {
252 if (cell <= next)
253 {
254 break;
255 }
256 }
257
258 cell->next = next;
259 cell->prev = prev;
260 if (next)
261 {
262 next->prev = cell;
263 if ((char *)cell + cell->size == (char *)next)
264 {
265 //---- Coalesce forward
266 cell->size += next->size;
267 cell->next = next = next->next;
268 if (next)
269 {
270 next->prev = cell;
271 }
272 }
273 }
274 if (prev)
275 {
276 prev->next = cell;
277 if ((char *)prev + prev->size == (char *)cell)
278 {
279 //---- Coalesce back
280 prev->size += cell->size;
281 prev->next = next;
282 if (next)
283 {
284 next->prev = prev;
285 }
286 }
287 return list;
288 }
289 else
290 {
291 return cell; // cell becomes new head of list
292 }
293 }
294
295 /*---------------------------------------------------------------------------*
296 Name: DLOverlap
297
298 Description: returns true if the range delimited by /start/ and /end/
299 overlaps with any element of /list/.
300
301 Arguments: list : pointer to the first cell in the list
302 start : start of range
303 end : end of range
304
305 Returns: TRUE if /start/-/end/ overlaps with any element of /list/
306 *---------------------------------------------------------------------------*/
DLOverlap(Cell * list,void * start,void * end)307 static BOOL DLOverlap(Cell * list, void *start, void *end)
308 {
309 Cell *cell;
310
311 for (cell = list; cell; cell = cell->next)
312 {
313 if (RangeOverlap(cell, (char *)cell + cell->size, start, end))
314 {
315 return TRUE;
316 }
317 }
318 return FALSE;
319 }
320
321 /*---------------------------------------------------------------------------*
322 Name: DLSize
323
324 Description: returns total number of bytes used by every element of /list/.
325
326 Arguments: list : pointer to the first cell in the list
327
328 Returns: total number of bytes used by every cell of /list/
329 *---------------------------------------------------------------------------*/
DLSize(Cell * list)330 static long DLSize(Cell * list)
331 {
332 Cell *cell;
333 long size = 0;
334
335 for (cell = list; cell; cell = cell->next)
336 {
337 size += cell->size;
338 }
339 return size;
340 }
341
342 //================================================================================
343 /*---------------------------------------------------------------------------*
344 Name: OS_AllocFromHeap
345
346 Description: Allocates /size/ bytes from /heap/. Some additional memory
347 will also be consumed from /heap/.
348
349 Arguments: id : arena ID
350 heap : handle to a heap that was returned from OS_CreateHeap()
351 size : size of object to be allocated
352
353 Returns: a null pointer or a pointer to the allocated space aligned
354 with ALIGNMENT bytes boundaries
355 *---------------------------------------------------------------------------*/
OS_AllocFromHeap(OSArenaId id,OSHeapHandle heap,u32 size)356 void *OS_AllocFromHeap(OSArenaId id, OSHeapHandle heap, u32 size)
357 {
358 OSHeapInfo *heapInfo;
359 HeapDesc *hd;
360 Cell *cell; // candidate block
361 Cell *newCell; // ptr to leftover block
362 long leftoverSize; // size of any leftover
363 OSIntrMode enabled = OS_DisableInterrupts();
364
365 //OS_Printf( "id=%d heap=%x size=%x\n",id, heap, size );
366
367 #ifdef SDK_DEBUG
368 long requested = (long)size;
369 #endif // SDK_DEBUG
370
371 //---- check arena id
372 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_ALLOCFROMHEAP_INVID);
373 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_ALLOCFROMHEAP_NOINFO);
374 heapInfo = OSiHeapInfo[id];
375
376 //---- check exist heap and size>0
377 if (!heapInfo)
378 {
379 (void)OS_RestoreInterrupts(enabled);
380 return NULL;
381 }
382
383 //---- heap<0 means current heap
384 if (heap < 0)
385 {
386 heap = heapInfo->currentHeap;
387 }
388
389 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_ALLOCFROMHEAP_NOHEAP);
390 SDK_ASSERTMSG(0 < ((long)size), OS_ERR_ALLOCFROMHEAP_INVSIZE);
391 SDK_ASSERTMSG(0 <= heap && heap < heapInfo->numHeaps, OS_ERR_ALLOCFROMHEAP_INVHEAP);
392 SDK_ASSERTMSG(0 <= heapInfo->heapArray[heap].size, OS_ERR_ALLOCFROMHEAP_INVHEAP);
393
394 hd = &heapInfo->heapArray[heap];
395
396 // Enlarge size to smallest possible cell size
397 size += HEADERSIZE;
398 size = ROUND(size, ALIGNMENT);
399
400 // Search for block large enough
401 for (cell = hd->free; cell != NULL; cell = cell->next)
402 {
403 if ((long)size <= cell->size)
404 {
405 break;
406 }
407 }
408
409 if (cell == NULL)
410 {
411 #ifdef SDK_DEBUG
412 OS_Printf("OS_AllocFromHeap: Warning- failed to allocate %d bytes\n", size);
413 #endif // SDK_DEBUG
414 (void)OS_RestoreInterrupts(enabled);
415 return NULL;
416 }
417
418 SDK_ASSERTMSG(OFFSET(cell, ALIGNMENT) == 0, OS_ERR_ALLOCFROMHEAP_BROKENHEAP);
419 SDK_ASSERTMSG(cell->hd == NULL, OS_ERR_ALLOCFROMHEAP_BROKENHEAP);
420
421 leftoverSize = cell->size - (long)size;
422 if (leftoverSize < MINOBJSIZE)
423 {
424 //---- Just extract this cell out since it's too small to split
425 hd->free = DLExtract(hd->free, cell);
426 }
427 else
428 {
429 //---- cell is large enough to split into two pieces
430 cell->size = (long)size;
431
432 //---- Create a new cell
433 newCell = (Cell *) ((char *)cell + size);
434 newCell->size = leftoverSize;
435 #ifdef SDK_DEBUG
436 newCell->hd = NULL;
437 #endif
438
439 //---- Leave newCell in free, and take cell away
440 newCell->prev = cell->prev;
441 newCell->next = cell->next;
442
443 if (newCell->next != NULL)
444 {
445 newCell->next->prev = newCell;
446 }
447
448 if (newCell->prev != NULL)
449 {
450 newCell->prev->next = newCell;
451 }
452 else
453 {
454 SDK_ASSERTMSG(hd->free == cell, OS_ERR_ALLOCFROMHEAP_BROKENHEAP);
455 hd->free = newCell;
456 }
457 }
458
459 //---- Add to allocated list
460 hd->allocated = DLAddFront(hd->allocated, cell);
461
462 #ifdef SDK_DEBUG
463 cell->hd = hd;
464 cell->requested = requested;
465 hd->headerBytes += HEADERSIZE;
466 hd->paddingBytes += cell->size - (HEADERSIZE + requested);
467 hd->payloadBytes += requested;
468 #endif // SDK_DEBUG
469
470 (void)OS_RestoreInterrupts(enabled);
471
472 return (void *)((char *)cell + HEADERSIZE);
473 }
474
475 /*---------------------------------------------------------------------------*
476 Name: OS_AllocFixed
477
478 Description: Allocates the block of memory specified by /rstart/ and
479 /rend/. Will break up any heap. Will not check for overlap
480 with other fixed blocks. May create a zero-length heap.
481
482 Arguments: id : arena ID
483 rstart : pointer to starting addr of block
484 rend : pointer to ending addr of block
485
486 Returns: a null pointer or a pointer to the allocated space aligned
487 with ALIGNMENT bytes boundaries. /rstart/ and /rend/ might be
488 adjusted to the boundaries of really allocated region.
489 *---------------------------------------------------------------------------*/
OS_AllocFixed(OSArenaId id,void ** rstart,void ** rend)490 void *OS_AllocFixed(OSArenaId id, void **rstart, void **rend)
491 {
492 OSHeapInfo *heapInfo;
493 OSHeapHandle i; // heap iterator
494 Cell *cell; // object iterator
495 Cell *newCell; // for creating new objects if necessary
496 HeapDesc *hd;
497 void *start = (void *)TRUNC(*rstart, ALIGNMENT);
498 void *end = (void *)ROUND(*rend, ALIGNMENT);
499 OSIntrMode enabled = OS_DisableInterrupts();
500
501 //---- check arena id
502 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_ALLOCFIXED_INVID);
503 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_ALLOCFIXED_NOINFO);
504 heapInfo = OSiHeapInfo[id];
505
506 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_ALLOCFIXED_NOHEAP);
507 SDK_ASSERTMSG(start < end, OS_ERR_ALLOCFIXED_INVRANGE);
508 SDK_ASSERTMSG(RangeSubset(start, end, heapInfo->arenaStart, heapInfo->arenaEnd),
509 OS_ERR_ALLOCFIXED_INVRANGE);
510
511 //---- Check overlap with any allocated blocks.
512 for (i = 0; i < heapInfo->numHeaps; i++)
513 {
514 hd = &heapInfo->heapArray[i];
515 if (hd->size < 0) // Is inactive?
516 {
517 continue;
518 }
519
520 if (DLOverlap(hd->allocated, start, end))
521 {
522 #ifdef SDK_DEBUG
523 OS_Printf("OS_AllocFixed: Warning - failed to allocate from %p to %p\n", start, end);
524 #endif // SDK_DEBUG
525 (void)OS_RestoreInterrupts(enabled);
526 return NULL;
527 }
528 }
529
530 /*
531 ASSUME : if we get past all this, the fixed request will
532 not overlap with any non-contiguous free memory.
533
534 Iterate over heaps breaking up appropriate blocks.
535 note that we cannot change the size of the heap by simply subtracting
536 out the overlap area, since the heaps may be non-contiguous.
537 */
538 for (i = 0; i < heapInfo->numHeaps; i++)
539 {
540 //---- for each free obj in heap, find and break overlaps.
541 hd = &heapInfo->heapArray[i];
542
543 if (hd->size < 0) // Is inactive?
544 {
545 continue;
546 }
547
548 for (cell = hd->free; cell; cell = cell->next)
549 {
550 void *cellEnd = (char *)cell + cell->size;
551
552 if ((char *)cellEnd <= (char *)start)
553 {
554 continue;
555 }
556
557 if ((char *)end <= (char *)cell)
558 {
559 break; // Since free is sorted in order of start addresses
560 }
561
562 if (InRange(cell, (char *)start - HEADERSIZE, end) &&
563 InRange((char *)cellEnd, start, (char *)end + MINOBJSIZE))
564 {
565 if ((char *)cell < (char *)start)
566 start = (void *)cell;
567 if ((char *)end < (char *)cellEnd)
568 end = (void *)cellEnd;
569
570 //---- cell is completely overlaped. Just extract this block
571 hd->free = DLExtract(hd->free, cell); // Note cell->next is intact. XXX
572 hd->size -= cell->size; // Update stats
573 continue;
574 }
575
576 if (InRange(cell, (char *)start - HEADERSIZE, end))
577 {
578 if ((char *)cell < (char *)start)
579 {
580 start = (void *)cell;
581 }
582
583 // Start of object in middle of range. break off top.
584 // Avoid DLExtract() and DLInsert() since we already know
585 // exactly where the block should go
586 SDK_ASSERT(MINOBJSIZE <= (char *)cellEnd - (char *)end);
587 newCell = (Cell *) end;
588 newCell->size = (char *)cellEnd - (char *)end;
589 #ifdef SDK_DEBUG
590 newCell->hd = NULL;
591 #endif // SDK_DEBUG
592 newCell->next = cell->next;
593 if (newCell->next)
594 {
595 newCell->next->prev = newCell;
596 }
597 newCell->prev = cell->prev;
598 if (newCell->prev)
599 {
600 newCell->prev->next = newCell;
601 }
602 else
603 {
604 hd->free = newCell; // new head
605 }
606 hd->size -= (char *)end - (char *)cell;
607 break;
608 }
609
610 if (InRange((char *)cellEnd, start, (char *)end + MINOBJSIZE))
611 {
612 if ((char *)end < (char *)cellEnd)
613 {
614 end = (void *)cellEnd;
615 }
616
617 //---- Nothing to change except size
618 SDK_ASSERT(MINOBJSIZE <= (char *)start - (char *)cell);
619 hd->size -= (char *)cellEnd - (char *)start;
620 cell->size = (char *)start - (char *)cell;
621 continue;
622 }
623
624 //---- Create a new cell after end of the fixed block.
625 SDK_ASSERT(MINOBJSIZE <= (char *)cellEnd - (char *)end);
626 newCell = (Cell *) end;
627 newCell->size = (char *)cellEnd - (char *)end;
628 #ifdef SDK_DEBUG
629 newCell->hd = NULL;
630 #endif // SDK_DEBUG
631 newCell->next = cell->next;
632 if (newCell->next)
633 {
634 newCell->next->prev = newCell;
635 }
636 newCell->prev = cell;
637 cell->next = newCell; // cell is before newCell
638 cell->size = (char *)start - (char *)cell;
639 hd->size -= (char *)end - (char *)start;
640 break;
641 }
642 SDK_ASSERT(0 <= hd->size);
643 }
644
645 SDK_ASSERT(OFFSET(start, ALIGNMENT) == 0);
646 SDK_ASSERT(OFFSET(end, ALIGNMENT) == 0);
647 SDK_ASSERT(start < end);
648 *rstart = start;
649 *rend = end;
650
651 (void)OS_RestoreInterrupts(enabled);
652 return *rstart;
653 }
654
655 /*---------------------------------------------------------------------------*
656 Name: OS_FreeToHeap
657
658 Description: Returns obj /ptr/ to /heap/.
659
660 Arguments: id : arena ID
661 heap : handle to the heap that /ptr/ was allocated from
662 ptr : pointer to object previously returned from
663 OS_Alloc() or OS_AllocFromHeap().
664
665 Returns: None.
666 *---------------------------------------------------------------------------*/
OS_FreeToHeap(OSArenaId id,OSHeapHandle heap,void * ptr)667 void OS_FreeToHeap(OSArenaId id, OSHeapHandle heap, void *ptr)
668 {
669 OSHeapInfo *heapInfo;
670 HeapDesc *hd;
671 Cell *cell;
672
673 OSIntrMode enabled = OS_DisableInterrupts();
674
675 //---- check arena id
676 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_FREETOHEAP_INVID);
677 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_FREETOHEAP_NOINFO);
678 heapInfo = OSiHeapInfo[id];
679
680 if (heap < 0)
681 {
682 heap = heapInfo->currentHeap;
683 }
684
685 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_FREETOHEAP_NOHEAP);
686 SDK_ASSERTMSG(InRange
687 (ptr, (char *)heapInfo->arenaStart + HEADERSIZE, (char *)heapInfo->arenaEnd),
688 OS_ERR_FREETOHEAP_INVPTR);
689 SDK_ASSERTMSG(OFFSET(ptr, ALIGNMENT) == 0, OS_ERR_FREETOHEAP_INVPTR);
690 SDK_ASSERTMSG(0 <= heapInfo->heapArray[heap].size, OS_ERR_FREETOHEAP_INVHEAP);
691
692 cell = (Cell *) ((char *)ptr - HEADERSIZE);
693 hd = &heapInfo->heapArray[heap];
694
695 SDK_ASSERTMSG(cell->hd == hd, OS_ERR_FREETOHEAP_INVPTR);
696 SDK_ASSERTMSG(DLLookup(hd->allocated, cell), OS_ERR_FREETOHEAP_INVPTR);
697
698 #ifdef SDK_DEBUG
699 cell->hd = NULL;
700 hd->headerBytes -= HEADERSIZE;
701 hd->paddingBytes -= cell->size - (HEADERSIZE + cell->requested);
702 hd->payloadBytes -= cell->requested;
703 #endif // SDK_DEBUG
704
705 //---- Extract from the allocated list
706 hd->allocated = DLExtract(hd->allocated, cell);
707
708 //---- Add in sorted order to free list (coalesced with next and prev)
709 hd->free = DLInsert(hd->free, cell);
710
711 (void)OS_RestoreInterrupts(enabled);
712 }
713
714 /*---------------------------------------------------------------------------*
715 Name: OS_FreeAllToHeap
716
717 Description: free all allocated block in the specified heap
718
719 Arguments: id : arena ID
720 heap : handle to the heap
721
722 Returns: None.
723 *---------------------------------------------------------------------------*/
OS_FreeAllToHeap(OSArenaId id,OSHeapHandle heap)724 void OS_FreeAllToHeap(OSArenaId id, OSHeapHandle heap)
725 {
726 OSHeapInfo *heapInfo;
727 HeapDesc *hd;
728 Cell *cell;
729
730 OSIntrMode enabled = OS_DisableInterrupts();
731
732 //---- check arena id
733 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_FREETOHEAP_INVID);
734 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_FREETOHEAP_NOINFO);
735 heapInfo = OSiHeapInfo[id];
736
737 if (heap < 0)
738 {
739 heap = heapInfo->currentHeap;
740 }
741
742 SDK_ASSERTMSG(heapInfo->heapArray, "heap not initialized");
743 SDK_ASSERTMSG(0 <= heapInfo->heapArray[heap].size, "invalid heap handle");
744
745 hd = &heapInfo->heapArray[heap];
746 while ((cell = hd->allocated) != NULL)
747 {
748 SDK_ASSERT(cell->hd == hd);
749 SDK_ASSERT(DLLookup(hd->allocated, cell));
750
751 #ifdef SDK_DEBUG
752 cell->hd = NULL;
753 hd->headerBytes -= HEADERSIZE;
754 hd->paddingBytes -= cell->size - (HEADERSIZE + cell->requested);
755 hd->payloadBytes -= cell->requested;
756 #endif // SDK_DEBUG
757
758 //---- Extract from the allocated list
759 hd->allocated = DLExtract(hd->allocated, cell);
760
761 //---- Add in sorted order to free list (coalesced with next and prev)
762 hd->free = DLInsert(hd->free, cell);
763 }
764
765 (void)OS_RestoreInterrupts(enabled);
766 }
767
768 /*---------------------------------------------------------------------------*
769 Name: OS_SetCurrentHeap
770
771 Description: Sets OSi_CurrentHeap to /heap/. All subsequent calls to
772 OS_Alloc() will be performed on this heap until another
773 call to OS_SetCurrentHeap().
774
775 Arguments: id : arena ID
776 heap : handle to a heap that was returned from OS_CreateHeap()
777
778 Returns: previous heap handle.
779 *---------------------------------------------------------------------------*/
OS_SetCurrentHeap(OSArenaId id,OSHeapHandle heap)780 OSHeapHandle OS_SetCurrentHeap(OSArenaId id, OSHeapHandle heap)
781 {
782 OSHeapInfo *heapInfo;
783 OSHeapHandle prev;
784 OSIntrMode enabled = OS_DisableInterrupts();
785
786 //---- check arena id
787 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_SETCURRENTHEAP_INVID);
788 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_SETCURRENTHEAP_NOINFO);
789 heapInfo = OSiHeapInfo[id];
790
791 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_SETCURRENTHEAP_NOHEAP);
792 SDK_ASSERTMSG(0 <= heap && heap < heapInfo->numHeaps, OS_ERR_SETCURRENTHEAP_INVHEAP);
793 SDK_ASSERTMSG(0 <= heapInfo->heapArray[heap].size, OS_ERR_SETCURRENTHEAP_INVHEAP);
794 prev = heapInfo->currentHeap;
795 heapInfo->currentHeap = heap;
796
797 (void)OS_RestoreInterrupts(enabled);
798 return prev;
799 }
800
801 /*---------------------------------------------------------------------------*
802 Name: OS_InitAlloc
803
804 Description: Initializes the arena in which all heaps will reside.
805 Reserves some small amount of memory for array of heap
806 descriptors.
807
808 Arguments: id : arena ID
809 arenaStart : beginning addr of arena
810 arenaEnd : ending addr of arena
811 maxHeaps : Maximum number of active heaps that will be
812 : used in lifetime of program
813
814 Returns: start of real arena, aligned with 32 bytes boundaries, after
815 heap array has been allocated
816 *---------------------------------------------------------------------------*/
OS_InitAlloc(OSArenaId id,void * arenaStart,void * arenaEnd,int maxHeaps)817 void *OS_InitAlloc(OSArenaId id, void *arenaStart, void *arenaEnd, int maxHeaps)
818 {
819 OSHeapInfo *heapInfo;
820 u32 arraySize;
821 OSHeapHandle i;
822 OSIntrMode enabled = OS_DisableInterrupts();
823
824 //---- check arena id
825 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_INITALLOC_INVID);
826 SDK_ASSERTMSG(OSiHeapInfo[id] == NULL, OS_ERR_INITALLOC_INVINFO);
827
828 SDK_ASSERTMSG(0 < maxHeaps, OS_ERR_INITALLOC_INVNUMHEAPS);
829 SDK_ASSERTMSG((char *)arenaStart < (char *)arenaEnd, OS_ERR_INITALLOC_INVRANGE);
830 SDK_ASSERTMSG(maxHeaps <= ((char *)arenaEnd - (char *)arenaStart) / sizeof(HeapDesc),
831 OS_ERR_INITALLOC_INSRANGE);
832
833 //---- save heapInfo
834 heapInfo = arenaStart;
835 OSiHeapInfo[id] = heapInfo;
836
837 //---- Place HeapArray at head of the arena
838 arraySize = sizeof(HeapDesc) * maxHeaps;
839 heapInfo->heapArray = (void *)((u32)arenaStart + sizeof(OSHeapInfo));
840 heapInfo->numHeaps = maxHeaps;
841
842 for (i = 0; i < heapInfo->numHeaps; i++)
843 {
844 HeapDesc *hd = &heapInfo->heapArray[i];
845
846 hd->size = -1;
847 hd->free = hd->allocated = NULL;
848 #ifdef SDK_DEBUG
849 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
850 #endif // SDK_DEBUG
851 }
852
853 //---- Set OSi_CurrentHeap to an invalid value
854 heapInfo->currentHeap = -1;
855
856 //---- Reset arenaStart to the nearest reasonable location
857 arenaStart = (void *)((char *)heapInfo->heapArray + arraySize);
858 arenaStart = (void *)ROUND(arenaStart, ALIGNMENT);
859
860 heapInfo->arenaStart = arenaStart;
861 heapInfo->arenaEnd = (void *)TRUNC(arenaEnd, ALIGNMENT);
862 SDK_ASSERTMSG(MINOBJSIZE <= (char *)heapInfo->arenaEnd - (char *)heapInfo->arenaStart,
863 OS_ERR_INITALLOC_INSRANGE);
864
865 (void)OS_RestoreInterrupts(enabled);
866 return heapInfo->arenaStart;
867 }
868
869 /*---------------------------------------------------------------------------*
870 Name: OS_ClearAlloc
871
872 Description: Clear heap pointer in system shared.
873 After calling this, you can call OS_InitAlloc() again.
874
875 Arguments: id : arena ID
876
877 Returns: None
878 *---------------------------------------------------------------------------*/
OS_ClearAlloc(OSArenaId id)879 void OS_ClearAlloc(OSArenaId id)
880 {
881 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_CLEARALLOC_INVID);
882 OSiHeapInfo[id] = NULL;
883 }
884
885 /*---------------------------------------------------------------------------*
886 Name: OS_CreateHeap
887
888 Description: Reserves area of memory from /start/ to /end/ for use as a
889 heap. Initializes heap descriptor and free list.
890 Will consume one entry in heap array.
891
892 Arguments: id : arena ID
893 start : starting addr of heap
894 end : ending addr of heap
895
896 Returns: If the function succeeds, it returns a new handle to heap
897 for use in OS_AllocFromHeap(), OS_FreeToHeap(), etc.
898 If the function fails, the return value is -1.
899 *---------------------------------------------------------------------------*/
OS_CreateHeap(OSArenaId id,void * start,void * end)900 OSHeapHandle OS_CreateHeap(OSArenaId id, void *start, void *end)
901 {
902 OSHeapInfo *heapInfo;
903 OSHeapHandle heap;
904 HeapDesc *hd;
905 Cell *cell;
906
907 OSIntrMode enabled = OS_DisableInterrupts();
908
909 //OS_Printf( "OS_CreateHeap id=%d start=%x, end=%x\n", id, start, end );
910 //---- check arena id
911 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_CREATEHEAP_INVID);
912 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_CREATEHEAP_NOINFO);
913 heapInfo = OSiHeapInfo[id];
914
915 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_CREATEHEAP_NOHEAP);
916 SDK_ASSERTMSG(start < end, OS_ERR_CREATEHEAP_INVRANGE);
917 start = (void *)ROUND(start, ALIGNMENT);
918 end = (void *)TRUNC(end, ALIGNMENT);
919 SDK_ASSERTMSG(start < end, OS_ERR_CREATEHEAP_INVRANGE);
920 SDK_ASSERTMSG(RangeSubset(start, end, heapInfo->arenaStart, heapInfo->arenaEnd),
921 OS_ERR_CREATEHEAP_INVRANGE);
922 SDK_ASSERTMSG(MINOBJSIZE <= (char *)end - (char *)start, OS_ERR_CREATEHEAP_INSRANGE);
923
924 #ifdef SDK_DEBUG
925 //---- Check that the range does not overlap with
926 // any other block in this or other heaps.
927 for (heap = 0; heap < heapInfo->numHeaps; heap++)
928 {
929 if (heapInfo->heapArray[heap].size < 0)
930 {
931 continue;
932 }
933 SDK_ASSERTMSG(!DLOverlap(heapInfo->heapArray[heap].free, start, end),
934 OS_ERR_CREATEHEAP_INVRANGE);
935 SDK_ASSERTMSG(!DLOverlap(heapInfo->heapArray[heap].allocated, start, end),
936 OS_ERR_CREATEHEAP_INVRANGE);
937 }
938 #endif // SDK_DEBUG
939
940 //---- Search for free descriptor
941 for (heap = 0; heap < heapInfo->numHeaps; heap++)
942 {
943 hd = &heapInfo->heapArray[heap];
944 if (hd->size < 0)
945 {
946 hd->size = (char *)end - (char *)start;
947
948 cell = (Cell *) start;
949 cell->prev = NULL;
950 cell->next = NULL;
951 cell->size = hd->size;
952 #ifdef SDK_DEBUG
953 cell->hd = NULL;
954 #endif // SDK_DEBUG
955
956 hd->free = cell;
957 hd->allocated = 0;
958 #ifdef SDK_DEBUG
959 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
960 #endif // SDK_DEBUG
961
962 (void)OS_RestoreInterrupts(enabled);
963 return heap;
964 }
965 }
966
967 //---- Could not find free descriptor
968 #ifdef SDK_DEBUG
969 OS_Printf("OS_CreateHeap: Warning - Failed to find free heap descriptor.");
970 #endif // SDK_DEBUG
971
972 (void)OS_RestoreInterrupts(enabled);
973 return -1;
974 }
975
976 /*---------------------------------------------------------------------------*
977 Name: OS_DestroyHeap
978
979 Description: Frees up the descriptor for the /heap/. Subsequent
980 allocation requests from this heap will fail unless another
981 heap is created with the same handle.
982
983 Arguments: id : arena ID
984 heap : handle to a live heap, previously created with OS_CreateHeap().
985
986 Returns: None.
987 *---------------------------------------------------------------------------*/
OS_DestroyHeap(OSArenaId id,OSHeapHandle heap)988 void OS_DestroyHeap(OSArenaId id, OSHeapHandle heap)
989 {
990 OSHeapInfo *heapInfo;
991 HeapDesc *hd;
992 #ifdef SDK_DEBUG
993 long size;
994 #endif
995 OSIntrMode enabled = OS_DisableInterrupts();
996
997 //---- check arena id
998 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_DESTROYHEAP_INVID);
999 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_DESTROYHEAP_NOINFO);
1000 heapInfo = OSiHeapInfo[id];
1001
1002 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_DESTROYHEAP_NOHEAP);
1003 SDK_ASSERTMSG(0 <= heap && heap < heapInfo->numHeaps, OS_ERR_DESTROYHEAP_INVHEAP);
1004 SDK_ASSERTMSG(0 <= heapInfo->heapArray[heap].size, OS_ERR_DESTROYHEAP_INVHEAP);
1005
1006 hd = &heapInfo->heapArray[heap];
1007
1008 #ifdef SDK_DEBUG
1009 //---- Check whether entire heap is empty
1010 size = DLSize(hd->free);
1011 if (hd->size != size)
1012 {
1013 OS_Printf("OS_DestroyHeap(%d): Warning - free list size %d, heap size %d\n", heap, size,
1014 hd->size);
1015 }
1016 #endif // SDK_DEBUG
1017
1018 hd->size = -1;
1019 hd->free = hd->allocated = NULL; // add to dolphin src
1020
1021 #ifdef SDK_DEBUG
1022 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
1023 if (heapInfo->currentHeap == heap)
1024 {
1025 heapInfo->currentHeap = -1;
1026 }
1027 #endif // SDK_DEBUG
1028
1029 (void)OS_RestoreInterrupts(enabled);
1030 }
1031
1032 /*---------------------------------------------------------------------------*
1033 Name: OS_AddToHeap
1034
1035 Description: Adds an arbitrary block of memory to /heap/. Used to free
1036 blocks previously allocated with OS_AllocFixed(), or to
1037 create non-contiguous heaps.
1038
1039 Arguments: id : arena ID
1040 heap : handle to live heap, previously created with OS_CreateHeap().
1041 start : starting addr of block to add to /heap/
1042 end : ending addr of block to add to /heap/
1043
1044 Returns: None.
1045 *---------------------------------------------------------------------------*/
OS_AddToHeap(OSArenaId id,OSHeapHandle heap,void * start,void * end)1046 void OS_AddToHeap(OSArenaId id, OSHeapHandle heap, void *start, void *end)
1047 {
1048 OSHeapInfo *heapInfo;
1049 HeapDesc *hd;
1050 Cell *cell;
1051 #ifdef SDK_DEBUG
1052 OSHeapHandle i;
1053 #endif // SDK_DEBUG
1054 OSIntrMode enabled = OS_DisableInterrupts();
1055
1056 //---- check arena id
1057 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_ADDTOHEAP_INVID);
1058 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_ADDTOHEAP_NOINFO);
1059 heapInfo = OSiHeapInfo[id];
1060
1061 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_ADDTOHEAP_NOHEAP);
1062 SDK_ASSERTMSG(0 <= heap && heap < heapInfo->numHeaps, OS_ERR_ADDTOHEAP_INVHEAP);
1063 SDK_ASSERTMSG(0 <= heapInfo->heapArray[heap].size, OS_ERR_ADDTOHEAP_INVHEAP);
1064
1065 hd = &heapInfo->heapArray[heap];
1066
1067 SDK_ASSERTMSG(start < end, OS_ERR_ADDTOHEAP_INVRANGE);
1068 start = (void *)ROUND(start, ALIGNMENT);
1069 end = (void *)TRUNC(end, ALIGNMENT);
1070 SDK_ASSERTMSG(MINOBJSIZE <= (char *)end - (char *)start, OS_ERR_ADDTOHEAP_INSRANGE);
1071 SDK_ASSERTMSG(RangeSubset(start, end, heapInfo->arenaStart, heapInfo->arenaEnd),
1072 OS_ERR_ADDTOHEAP_INVRANGE);
1073
1074 #ifdef SDK_DEBUG
1075 //---- Check that the range does not already overlap with
1076 // any other block in this or other heaps.
1077 for (i = 0; i < heapInfo->numHeaps; i++)
1078 {
1079 if (heapInfo->heapArray[i].size < 0)
1080 {
1081 continue;
1082 }
1083 SDK_ASSERTMSG(!DLOverlap(heapInfo->heapArray[i].free, start, end),
1084 OS_ERR_ADDTOHEAP_INVRANGE);
1085 SDK_ASSERTMSG(!DLOverlap(heapInfo->heapArray[i].allocated, start, end),
1086 OS_ERR_ADDTOHEAP_INVRANGE);
1087 }
1088 #endif // SDK_DEBUG
1089
1090 //---- Create a new cell
1091 cell = (Cell *) start;
1092 cell->size = (char *)end - (char *)start;
1093 #ifdef SDK_DEBUG
1094 cell->hd = NULL;
1095 #endif // SDK_DEBUG
1096
1097 //---- Insert new cell in free
1098 hd->size += cell->size;
1099 hd->free = DLInsert(hd->free, cell);
1100
1101 (void)OS_RestoreInterrupts(enabled);
1102 }
1103
1104 /*---------------------------------------------------------------------------*
1105 Name: OS_CheckHeap
1106
1107 Description: Checks heap sanity for debugging
1108
1109 Arguments: id : arena ID
1110 heap : handle to a live heap.
1111
1112 Returns: -1 if heap is not consistent. Otherwise, returns number
1113 of bytes available in free.
1114 *---------------------------------------------------------------------------*/
1115
1116 #ifndef SDK_NO_MESSAGE
1117 #ifdef SDK_ARM9
1118 #define OSi_CHECK( exp ) \
1119 do \
1120 { \
1121 if ( !(exp) ) \
1122 { \
1123 OS_Printf( "OS_CheckHeap: Failed " #exp " in %d\n", __LINE__ ); \
1124 goto exit_OS_CheckHeap; /* goto is not beautiful, but less codes */ \
1125 } \
1126 } while (0)
1127 #else /* SDK_ARM9 */
1128 #define OSi_CHECK( exp ) \
1129 do \
1130 { \
1131 if ( !(exp) ) \
1132 { \
1133 OS_Printf( "OS_CheckHeap: Failed in %d\n", __LINE__ ); \
1134 goto exit_OS_CheckHeap; /* goto is not beautiful, but less codes */ \
1135 } \
1136 } while (0)
1137 #endif
1138 #else
1139 #define OSi_CHECK( exp ) \
1140 do \
1141 { \
1142 if ( !(exp) ) \
1143 { \
1144 goto exit_OS_CheckHeap; /* goto is not beautiful, but less codes */ \
1145 } \
1146 } while (0)
1147 #endif
1148
OS_CheckHeap(OSArenaId id,OSHeapHandle heap)1149 s32 OS_CheckHeap(OSArenaId id, OSHeapHandle heap)
1150 {
1151 OSHeapInfo *heapInfo;
1152 HeapDesc *hd;
1153 Cell *cell;
1154 long total = 0;
1155 long free = 0;
1156 long retValue = -1;
1157 OSIntrMode enabled = OS_DisableInterrupts();
1158
1159 //---- check arena id
1160 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_CHECKHEAP_INVID);
1161 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_CHECKHEAP_NOINFO);
1162 heapInfo = OSiHeapInfo[id];
1163
1164 //---- heap<0 means current heap
1165 if (heap == OS_CURRENT_HEAP_HANDLE)
1166 {
1167 heap = heapInfo->currentHeap;
1168 }
1169 SDK_ASSERT(heap >= 0);
1170
1171 OSi_CHECK(heapInfo->heapArray);
1172 OSi_CHECK(0 <= heap && heap < heapInfo->numHeaps);
1173
1174 hd = &heapInfo->heapArray[heap];
1175 OSi_CHECK(0 <= hd->size);
1176
1177 OSi_CHECK(hd->allocated == NULL || hd->allocated->prev == NULL);
1178 for (cell = hd->allocated; cell; cell = cell->next)
1179 {
1180 OSi_CHECK(InRange(cell, heapInfo->arenaStart, heapInfo->arenaEnd));
1181 OSi_CHECK(OFFSET(cell, ALIGNMENT) == 0);
1182 OSi_CHECK(cell->next == NULL || cell->next->prev == cell);
1183 OSi_CHECK(MINOBJSIZE <= cell->size);
1184 OSi_CHECK(OFFSET(cell->size, ALIGNMENT) == 0);
1185
1186 total += cell->size;
1187 OSi_CHECK(0 < total && total <= hd->size);
1188
1189 #ifdef SDK_DEBUG
1190 OSi_CHECK(cell->hd == hd);
1191 OSi_CHECK(HEADERSIZE + cell->requested <= cell->size);
1192 #endif // SDK_DEBUG
1193 }
1194
1195 OSi_CHECK(hd->free == NULL || hd->free->prev == NULL);
1196 for (cell = hd->free; cell; cell = cell->next)
1197 {
1198 OSi_CHECK(InRange(cell, heapInfo->arenaStart, heapInfo->arenaEnd));
1199 OSi_CHECK(OFFSET(cell, ALIGNMENT) == 0);
1200 OSi_CHECK(cell->next == NULL || cell->next->prev == cell);
1201 OSi_CHECK(MINOBJSIZE <= cell->size);
1202 OSi_CHECK(OFFSET(cell->size, ALIGNMENT) == 0);
1203 OSi_CHECK(cell->next == NULL || (char *)cell + cell->size < (char *)cell->next);
1204
1205 total += cell->size;
1206 free += cell->size - HEADERSIZE;
1207 OSi_CHECK(0 < total && total <= hd->size);
1208
1209 #ifdef SDK_DEBUG
1210 OSi_CHECK(cell->hd == NULL);
1211 #endif // SDK_DEBUG
1212 }
1213
1214 OSi_CHECK(total == hd->size);
1215 retValue = free;
1216
1217 exit_OS_CheckHeap:
1218 (void)OS_RestoreInterrupts(enabled);
1219 return retValue;
1220 }
1221
1222 /*---------------------------------------------------------------------------*
1223 Name: OS_ReferentSize
1224
1225 Description: Returns size of payload
1226
1227 Arguments: id : arena ID
1228 ptr : pointer to object previously returned from
1229 OS_Alloc() or OSAllocFromHeap().
1230
1231 Returns: size of payload
1232 *---------------------------------------------------------------------------*/
OS_ReferentSize(OSArenaId id,void * ptr)1233 u32 OS_ReferentSize(OSArenaId id, void *ptr)
1234 {
1235 OSHeapInfo *heapInfo;
1236 Cell *cell;
1237 OSIntrMode enabled = OS_DisableInterrupts();
1238
1239 //---- check arena id
1240 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_REFERENTSIZE_INVID);
1241 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_REFERENTSIZE_NOINFO);
1242 heapInfo = OSiHeapInfo[id];
1243
1244 SDK_ASSERTMSG(heapInfo->heapArray, OS_ERR_REFERENT_NOHEAP);
1245 SDK_ASSERTMSG(InRange
1246 (ptr, (char *)heapInfo->arenaStart + HEADERSIZE, (char *)heapInfo->arenaEnd),
1247 OS_ERR_REFERENT_INVPTR);
1248 SDK_ASSERTMSG(OFFSET(ptr, ALIGNMENT) == 0, OS_ERR_REFERENT_INVPTR);
1249
1250 cell = (Cell *) ((char *)ptr - HEADERSIZE);
1251
1252 SDK_ASSERTMSG(cell->hd, OS_ERR_REFERENT_INVPTR);
1253 SDK_ASSERTMSG(((char *)cell->hd - (char *)heapInfo->heapArray) % sizeof(HeapDesc) == 0,
1254 OS_ERR_REFERENT_INVPTR);
1255 SDK_ASSERTMSG(heapInfo->heapArray <= cell->hd
1256 && cell->hd < &heapInfo->heapArray[heapInfo->numHeaps], OS_ERR_REFERENT_INVPTR);
1257 SDK_ASSERTMSG(0 <= cell->hd->size, OS_ERR_REFERENT_INVPTR);
1258 SDK_ASSERTMSG(DLLookup(cell->hd->allocated, cell), OS_ERR_REFERENT_INVPTR);
1259
1260 (void)OS_RestoreInterrupts(enabled);
1261 return (u32)(cell->size - HEADERSIZE);
1262 }
1263
1264 /*---------------------------------------------------------------------------*
1265 Name: OS_DumpHeap
1266
1267 Description: Dumps statistics and elements of a heap
1268
1269 Arguments: id : arena ID
1270 heap : handle to a heap.
1271
1272 Returns: None.
1273 *---------------------------------------------------------------------------*/
OS_DumpHeap(OSArenaId id,OSHeapHandle heap)1274 void OS_DumpHeap(OSArenaId id, OSHeapHandle heap)
1275 {
1276 #ifndef SDK_FINALROM
1277 OSHeapInfo *heapInfo;
1278 HeapDesc *hd;
1279 Cell *cell;
1280 OSIntrMode enabled = OS_DisableInterrupts();
1281
1282 //---- check arena id
1283 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_DUMPHEAP_INVID);
1284 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_DUMPHEAP_NOINFO);
1285 heapInfo = OSiHeapInfo[id];
1286
1287 SDK_ASSERTMSG(heapInfo && heapInfo->heapArray, OS_ERR_DUMPHEAP_NOHEAP);
1288
1289 //---- heap<0 means current heap
1290 if (heap < 0)
1291 {
1292 heap = heapInfo->currentHeap;
1293 }
1294 SDK_ASSERTMSG(0 <= heap && heap < heapInfo->numHeaps, OS_ERR_DUMPHEAP_INVHEAP);
1295
1296 hd = &heapInfo->heapArray[heap];
1297 if (hd->size < 0)
1298 {
1299 OS_Printf("----Inactive\n");
1300 return;
1301 }
1302
1303 SDK_ASSERTMSG(0 <= OS_CheckHeap(id, heap), OS_ERR_DUMPHEAP_BROKENHEAP);
1304
1305 #ifdef SDK_DEBUG
1306 OS_Printf("padding %d/(%f%%) header %d/(%f%%) payload %d/(%f%%)\n",
1307 hd->paddingBytes, 100.0 * hd->paddingBytes / hd->size,
1308 hd->headerBytes, 100.0 * hd->headerBytes / hd->size,
1309 hd->payloadBytes, 100.0 * hd->payloadBytes / hd->size);
1310 #endif // SDK_DEBUG
1311
1312 OS_Printf(" addr size end prev next\n");
1313
1314 OS_Printf("----Allocated\n");
1315 SDK_ASSERTMSG(hd->allocated == NULL || hd->allocated->prev == NULL, OS_ERR_DUMPHEAP_BROKENHEAP);
1316 if ( ! hd->allocated )
1317 {
1318 OS_Printf("None.\n");
1319 }
1320 else
1321 {
1322 for (cell = hd->allocated; cell; cell = cell->next)
1323 {
1324 OS_Printf("%08x %6x %08x %08x %08x\n",
1325 cell, cell->size, (char *)cell + cell->size, cell->prev, cell->next);
1326 }
1327 }
1328
1329 OS_Printf("----Free\n");
1330 if ( ! hd->free )
1331 {
1332 OS_Printf("None.\n");
1333 }
1334 else
1335 {
1336 for (cell = hd->free; cell; cell = cell->next)
1337 {
1338 OS_Printf("%08x %6x %08x %08x %08x\n",
1339 cell, cell->size, (char *)cell + cell->size, cell->prev, cell->next);
1340 }
1341 }
1342
1343 (void)OS_RestoreInterrupts(enabled);
1344 #else // ifndef SDK_FINALROM
1345
1346 #pragma unused( id, heap )
1347
1348 #endif // ifndef SDK_FINALROM
1349 }
1350
1351
1352 /*---------------------------------------------------------------------------*
1353 Name: OS_VisitAllocated
1354
1355 Description: Visits every element of every allocated block of memory,
1356 calling a routine on each one.
1357
1358 Arguments: id : arena ID
1359 visitor : function to be called on each cell
1360
1361 Returns: None.
1362 *---------------------------------------------------------------------------*/
OS_VisitAllocated(OSArenaId id,OSAllocVisitor visitor)1363 void OS_VisitAllocated(OSArenaId id, OSAllocVisitor visitor)
1364 {
1365 OSHeapInfo *heapInfo;
1366 u32 heap;
1367 Cell *cell;
1368
1369 OSIntrMode enabled = OS_DisableInterrupts();
1370
1371 //---- check arena id
1372 SDK_ASSERTMSG(id < OS_ARENA_MAX, OS_ERR_VISITALLOCATED_INVID);
1373 SDK_ASSERTMSG(OSiHeapInfo[id], OS_ERR_VISITALLOCATED_NOINFO);
1374 heapInfo = OSiHeapInfo[id];
1375
1376 for (heap = 0; heap < heapInfo->numHeaps; heap++)
1377 {
1378 if (heapInfo->heapArray[heap].size >= 0)
1379 {
1380 for (cell = heapInfo->heapArray[heap].allocated; cell; cell = cell->next)
1381 {
1382 visitor((void *)((u8 *)cell + HEADERSIZE), (u32)(cell->size - HEADERSIZE));
1383 }
1384 }
1385 }
1386
1387 (void)OS_RestoreInterrupts(enabled);
1388 }
1389
1390 //================================================================================
1391 // Get information about heap
1392 //================================================================================
1393 /*---------------------------------------------------------------------------*
1394 Name: OSi_GetTotalAllocSize
1395
1396 Description: Get sum of allocated block size.
1397 Subroutine for OS_GetTotalAllocSize and OS_GetTotalOccupiedSize.
1398
1399 Arguments: id : arena ID
1400 heap : handle to a heap.
1401 isHeadInclude : whether if including block header.
1402
1403 Returns: sum of allocated block size
1404 *---------------------------------------------------------------------------*/
OSi_GetTotalAllocSize(OSArenaId id,OSHeapHandle heap,BOOL isHeadInclude)1405 u32 OSi_GetTotalAllocSize(OSArenaId id, OSHeapHandle heap, BOOL isHeadInclude)
1406 {
1407 OSHeapInfo *heapInfo;
1408 Cell *cell;
1409 u32 sum = 0;
1410 OSIntrMode enabled = OS_DisableInterrupts();
1411
1412 SDK_ASSERT(id < OS_ARENA_MAX);
1413 heapInfo = OSiHeapInfo[id];
1414 SDK_ASSERT(heapInfo);
1415 SDK_ASSERT(heap < heapInfo->numHeaps);
1416
1417 //---- heap<0 means current heap
1418 if (heap < 0)
1419 {
1420 heap = heapInfo->currentHeap;
1421 }
1422
1423 if (isHeadInclude)
1424 {
1425 for (cell = heapInfo->heapArray[heap].allocated; cell; cell = cell->next)
1426 {
1427 sum += (u32)(cell->size);
1428 }
1429 }
1430 else
1431 {
1432 for (cell = heapInfo->heapArray[heap].allocated; cell; cell = cell->next)
1433 {
1434 sum += (u32)(cell->size - HEADERSIZE);
1435 }
1436 }
1437
1438 (void)OS_RestoreInterrupts(enabled);
1439
1440 return sum;
1441 }
1442
1443 /*---------------------------------------------------------------------------*
1444 Name: OS_GetTotalFreeSize
1445
1446 Description: Get sum of free block size,
1447 not includeing of block header.
1448
1449 Arguments: id : arena ID
1450 heap : handle to a heap.
1451
1452 Returns: sum of free block size
1453 *---------------------------------------------------------------------------*/
OS_GetTotalFreeSize(OSArenaId id,OSHeapHandle heap)1454 u32 OS_GetTotalFreeSize(OSArenaId id, OSHeapHandle heap)
1455 {
1456 OSHeapInfo *heapInfo;
1457 Cell *cell;
1458 u32 sum = 0;
1459 OSIntrMode enabled = OS_DisableInterrupts();
1460
1461 SDK_ASSERT(id < OS_ARENA_MAX);
1462 heapInfo = OSiHeapInfo[id];
1463 SDK_ASSERT(heapInfo);
1464 SDK_ASSERT(heap < heapInfo->numHeaps);
1465
1466 //---- heap<0 means current heap
1467 if (heap < 0)
1468 {
1469 heap = heapInfo->currentHeap;
1470 }
1471
1472 for (cell = heapInfo->heapArray[heap].free; cell; cell = cell->next)
1473 {
1474 sum += (u32)(cell->size - HEADERSIZE);
1475 }
1476
1477 (void)OS_RestoreInterrupts(enabled);
1478
1479 return sum;
1480 }
1481
1482 /*---------------------------------------------------------------------------*
1483 Name: OS_GetMaxFreeSize
1484
1485 Description: Get maximun free block size
1486
1487 Arguments: id : arena ID
1488 heap : handle to a heap.
1489
1490 Returns: maximum free block size.
1491 *---------------------------------------------------------------------------*/
OS_GetMaxFreeSize(OSArenaId id,OSHeapHandle heap)1492 u32 OS_GetMaxFreeSize(OSArenaId id, OSHeapHandle heap)
1493 {
1494 OSHeapInfo *heapInfo;
1495 Cell *cell;
1496 u32 candidate = 0;
1497 OSIntrMode enabled = OS_DisableInterrupts();
1498
1499 SDK_ASSERT(id < OS_ARENA_MAX);
1500 heapInfo = OSiHeapInfo[id];
1501 SDK_ASSERT(heapInfo);
1502 SDK_ASSERT(heap < heapInfo->numHeaps);
1503
1504 //---- heap<0 means current heap
1505 if (heap < 0)
1506 {
1507 heap = heapInfo->currentHeap;
1508 }
1509
1510 for (cell = heapInfo->heapArray[heap].free; cell; cell = cell->next)
1511 {
1512 u32 size = (u32)(cell->size - HEADERSIZE);
1513 if (size > candidate)
1514 {
1515 candidate = size;
1516 }
1517 }
1518
1519 (void)OS_RestoreInterrupts(enabled);
1520
1521 return candidate;
1522 }
1523
1524 //================================================================================
1525 // re-initialize heap.
1526 //================================================================================
1527 /*---------------------------------------------------------------------------*
1528 Name: OS_ClearHeap
1529
1530 Description: re-initialize heap.
1531
1532 Arguments: id : arena ID
1533 heap : handle to a heap.
1534
1535 Returns: None.
1536 *---------------------------------------------------------------------------*/
OS_ClearHeap(OSArenaId id,OSHeapHandle heap,void * start,void * end)1537 void OS_ClearHeap(OSArenaId id, OSHeapHandle heap, void *start, void *end)
1538 {
1539 OSHeapInfo *heapInfo;
1540 HeapDesc *hd;
1541 Cell *cell;
1542
1543 OSIntrMode enabled = OS_DisableInterrupts();
1544
1545 //---- check arena id
1546 SDK_ASSERTMSG(id < OS_ARENA_MAX, "invalid id");
1547
1548 heapInfo = OSiHeapInfo[id];
1549
1550 SDK_ASSERTMSG(heapInfo && heapInfo->heapArray, "heap not initialized");
1551 SDK_ASSERTMSG(start < end, "invalid range");
1552 start = (void *)ROUND(start, ALIGNMENT);
1553 end = (void *)TRUNC(end, ALIGNMENT);
1554 SDK_ASSERTMSG(start < end, "invalid range");
1555 SDK_ASSERTMSG(RangeSubset(start, end, heapInfo->arenaStart, heapInfo->arenaEnd),
1556 "invalid range");
1557 SDK_ASSERTMSG(MINOBJSIZE <= (char *)end - (char *)start, "too small range");
1558
1559 //---- heap<0 means current heap
1560 if (heap < 0)
1561 {
1562 heap = heapInfo->currentHeap;
1563 }
1564
1565 //---- Search for free descriptor
1566 hd = &heapInfo->heapArray[heap];
1567 hd->size = (char *)end - (char *)start;
1568
1569 cell = (Cell *) start;
1570 cell->prev = NULL;
1571 cell->next = NULL;
1572 cell->size = hd->size;
1573 #ifdef SDK_DEBUG
1574 cell->hd = NULL;
1575 #endif // SDK_DEBUG
1576
1577 hd->free = cell;
1578 hd->allocated = 0;
1579 #ifdef SDK_DEBUG
1580 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
1581 #endif // SDK_DEBUG
1582
1583 (void)OS_RestoreInterrupts(enabled);
1584 }
1585