1 /*---------------------------------------------------------------------------*
2 Project: OS - Memory Manager
3 File: OSAlloc.c
4
5 Copyright 1998 - 2006 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 $Log: OSAlloc.c,v $
14 Revision 1.3 2006/02/20 05:25:24 hirose
15 Changed location of include headers.
16
17 Revision 1.2 2006/01/20 01:07:52 hirose
18 (none)
19
20 Revision 1.1.1.1 2005/12/29 06:53:27 hiratsu
21 Initial import.
22
23 Revision 1.1.1.1 2005/05/12 02:15:49 yasuh-to
24 Ported from dolphin source tree.
25
26
27 2 2004/01/09 9:24 Shiki
28 Fixed OSDestroyHeap to re-initialize hd->free to NULL to prevent
29 subsequent OSAlloc in non-debug build.
30
31 15 1999/11/01 6:16p Tian
32 Added OSVisitAllocated to iterate over all allocated memory
33
34 13 1999/06/03 6:37p Shiki
35 Implemented error messages.
36
37 12 1999/06/01 3:01p Shiki
38 Revised function description of OSDestroyHeap().
39
40 11 1999/05/26 9:16a Shiki
41 Fixed OSAllocFixed(), etc.
42
43 10 1999/05/25 9:55p Shiki
44 Modified OSCheckHeap()to return # of available bytes in free.
45
46 9 1999/05/23 6:57p Shiki
47 Fixed OSAllocFixed().
48 Added sanity check function.
49
50 8 1999/05/22 7:59p Shiki
51 Refined less-efficient array references by pointers.
52
53 7 1999/05/22 7:30p Shiki
54 Revised doubly-linked list manipulation functions.
55
56 6 1999/05/21 8:06p Shiki
57 Fixed spell misses.
58
59 5 1999/05/21 7:56p Shiki
60 Revised.
61
62 3 1999/05/19 5:12p Shiki
63 Renamed Halt() to OSHalt().
64
65 2 1999/05/11 4:36p Shiki
66 Refreshed include tree.
67
68 1 1999/04/30 12:47p Tianli01
69
70 4 1999/04/15 2:49p Tianli01
71 Fixes for PPC (no floats). Changed failure semantics slightly (NULL
72 return on run out of memory).
73
74 3 1999/04/13 9:44a Tianli01
75 Fixed compile warnings
76
77 2 1999/03/26 2:10p Tianli01
78 Removed OSEvent reliance.
79
80 1 1999/03/09 11:43a Tianli01
81 Fixed negated assertions
82
83 1 1999/03/04 2:23p Tianli01
84 Initial check-in to new tree.
85
86 1 1998/12/22 10:29a Tianli01
87 Initial check-in. To be implemented : OSEvent integration, Sanity
88 checking
89
90 $NoKeywords: $
91 *---------------------------------------------------------------------------*/
92
93 #include <revolution/types.h>
94 #include <revolution/os.h>
95 #include <revolution/os/OSAlloc.h>
96 #include "OSAssert.h"
97
98 #define OFFSET(n, a) (((u32) (n)) & ((a) - 1))
99 #define TRUNC(n, a) (((u32) (n)) & ~((a) - 1))
100 #define ROUND(n, a) (((u32) (n) + (a) - 1) & ~((a) - 1))
101
102 #define ALIGNMENT 32 // alignment in bytes
103 #define MINOBJSIZE (HEADERSIZE + ALIGNMENT) // smallest object
104 #define HEADERSIZE ROUND(sizeof(Cell), ALIGNMENT)
105
106 // InRange(): True if a <= targ < b
107 #define InRange(targ, a, b) \
108 ((u32)(a) <= (u32)(targ) && (u32)(targ) < (u32)(b))
109
110 // RangeOverlap(): True if the ranges a and b overlap in any way.
111 #define RangeOverlap(aStart, aEnd, bStart, bEnd) \
112 ((u32)(bStart) <= (u32)(aStart) && (u32)(aStart) < (u32)(bEnd) || \
113 (u32)(bStart) < (u32)(aEnd) && (u32)(aEnd) <= (u32)(bEnd))
114
115 // RangeSubset(): True if range a is a subset of range b
116 // Assume (aStart < aEnd) and (bStart < bEnd)
117 #define RangeSubset(aStart, aEnd, bStart, bEnd) \
118 ((u32)(bStart) <= (u32)(aStart) && (u32)(aEnd) <= (u32)(bEnd))
119
120 typedef struct Cell Cell;
121 typedef struct HeapDesc HeapDesc;
122
123 // Cell: header of object which resides HEADERSIZE bytes before payload.
124 // doubly linked list are needed because of non-contiguous heaps
125 struct Cell
126 {
127 Cell* prev;
128 Cell* next;
129 long size; // size of object plus HEADERSIZE
130
131 #ifdef _DEBUG
132 HeapDesc* hd; // from which the block is allocated
133 // (NULL in free list).
134 long requested; // size of object to have been requested
135 #endif // _DEBUG
136 };
137
138 struct HeapDesc
139 {
140 long size; // if -1 then heap is free. Note OSAllocFixed()
141 // could make a heap empty.
142 Cell* free; // pointer to the first free cell
143 Cell* allocated; // pointer to the first used cell
144
145 #ifdef _DEBUG
146 u32 paddingBytes;
147 u32 headerBytes;
148 u32 payloadBytes;
149 #endif // _DEBUG
150 };
151
152 // volatile because some functions use this as hidden macro parameter
153 volatile OSHeapHandle __OSCurrHeap = -1;
154
155 static HeapDesc* HeapArray; // array of current heap descriptors
156 static int NumHeaps; // number of heaps
157 static void* ArenaStart; // specified by OSInitAlloc()
158 static void* ArenaEnd; // specified by OSInitAlloc()
159
160 /*---------------------------------------------------------------------------*
161 Name: DLAddFront
162
163 Description: Inserts /cell/ into the head of the list pointed to by
164 /list/
165
166 Arguments: list: pointer to the first cell in the list
167 cell: pointer to a cell to be inserted
168
169 Returns: a pointer to the new first cell
170 *---------------------------------------------------------------------------*/
DLAddFront(Cell * list,Cell * cell)171 static Cell* DLAddFront(Cell* list, Cell* cell)
172 {
173 cell->next = list;
174 cell->prev = NULL;
175 if (list)
176 list->prev = cell;
177 return cell;
178 }
179
180 /*---------------------------------------------------------------------------*
181 Name: DLLookup
182
183 Description: Returns /cell/ if /cell/ is found in /list/.
184
185 Arguments: list: pointer to the first cell in the list
186 cell: pointer to a cell to look for
187
188 Returns: /cell/ if /cell/ is in /list/. Otherwise, NULL.
189 *---------------------------------------------------------------------------*/
DLLookup(Cell * list,Cell * cell)190 static Cell* DLLookup(Cell* list, Cell* cell)
191 {
192 for (; list; list = list->next)
193 {
194 if (list == cell)
195 return list;
196 }
197 return NULL;
198 }
199
200 /*---------------------------------------------------------------------------*
201 Name: DLExtract
202
203 Description: Extracts /target/ from the list pointed to by /list/.
204 If /target/ is at the head of the list, /list/ will be changed
205 to reflect its removal.
206
207 Arguments: list: pointer to the first cell in the list
208 cell: pointer to a cell to remove
209
210 Returns: a pointer to the new first cell
211 *---------------------------------------------------------------------------*/
DLExtract(Cell * list,Cell * cell)212 static Cell* DLExtract(Cell* list, Cell* cell)
213 {
214 if (cell->next)
215 cell->next->prev = cell->prev;
216 if (cell->prev == NULL)
217 return cell->next;
218 else
219 {
220 cell->prev->next = cell->next;
221 return list;
222 }
223 }
224
225 /*---------------------------------------------------------------------------*
226 Name: DLInsert
227
228 Description: Inserts /cell/ into the list pointed to by /list/ in sorted
229 order by address. Also attempts to coalesce forward and
230 backward blocks if possible.
231
232 Arguments: list: pointer to the first cell in the list
233 cell: pointer to a cell to be inserted
234
235 Returns: a pointer to the new first cell
236 *---------------------------------------------------------------------------*/
DLInsert(Cell * list,Cell * cell)237 static Cell* DLInsert(Cell* list, Cell* cell)
238 {
239 Cell* prev;
240 Cell* next;
241
242 for (next = list, prev = NULL; next; prev = next, next = next->next)
243 {
244 if (cell <= next)
245 break;
246 }
247 cell->next = next;
248 cell->prev = prev;
249 if (next)
250 {
251 next->prev = cell;
252 if ((char*) cell + cell->size == (char*) next)
253 {
254 // Coalesce forward
255 cell->size += next->size;
256 cell->next = next = next->next;
257 if (next)
258 next->prev = cell;
259 }
260 }
261 if (prev)
262 {
263 prev->next = cell;
264 if ((char*) prev + prev->size == (char*) cell)
265 {
266 // Coalesce back
267 prev->size += cell->size;
268 prev->next = next;
269 if (next)
270 next->prev = prev;
271 }
272 return list;
273 }
274 else
275 {
276 return cell; // cell becomes new head of list
277 }
278 }
279
280 /*---------------------------------------------------------------------------*
281 Name: DLOverlap
282
283 Description: returns true if the range delimited by /start/ and /end/
284 overlaps with any element of /list/.
285
286 Arguments: list: pointer to the first cell in the list
287 start: start of range
288 end: end of range
289
290 Returns: TRUE if /start/-/end/ overlaps with any element of /list/
291 *---------------------------------------------------------------------------*/
DLOverlap(Cell * list,void * start,void * end)292 static BOOL DLOverlap(Cell* list, void* start, void* end)
293 {
294 Cell* cell;
295
296 for (cell = list; cell; cell = cell->next)
297 {
298 if (RangeOverlap(cell, (char*) cell + cell->size, start, end))
299 return TRUE;
300 }
301 return FALSE;
302 }
303
304 /*---------------------------------------------------------------------------*
305 Name: DLSize
306
307 Description: returns total number of bytes used by every element of /list/.
308
309 Arguments: list: pointer to the first cell in the list
310
311 Returns: total number of bytes used by every cell of /list/
312 *---------------------------------------------------------------------------*/
DLSize(Cell * list)313 static long DLSize(Cell* list)
314 {
315 Cell* cell;
316 long size = 0;
317
318 for (cell = list; cell; cell = cell->next)
319 {
320 size += cell->size;
321 }
322 return size;
323 }
324
325 /*---------------------------------------------------------------------------*
326 Name: OSAllocFromHeap
327
328 Description: Allocates /size/ bytes from /heap/. Some additional memory
329 will also be consumed from /heap/.
330
331 Arguments: heap: handle to a heap that was returned from
332 OSCreateHeap()
333 size: size of object to be allocated
334
335 Returns: a null pointer or a pointer to the allocated space aligned
336 with ALIGNMENT bytes boundaries
337 *---------------------------------------------------------------------------*/
OSAllocFromHeap(OSHeapHandle heap,u32 size)338 void* OSAllocFromHeap(OSHeapHandle heap, u32 size)
339 {
340 HeapDesc* hd;
341 Cell* cell; // candidate block
342 Cell* newCell; // ptr to leftover block
343 long leftoverSize; // size of any leftover
344
345 #ifdef _DEBUG
346 long requested = (long) size;
347 #endif // _DEBUG
348
349 ASSERTMSG(HeapArray, OS_ERR_ALLOCFROMHEAP_NOHEAP);
350 ASSERTMSG(0 < ((long) size), OS_ERR_ALLOCFROMHEAP_INVSIZE);
351 ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_ALLOCFROMHEAP_INVHEAP);
352 ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_ALLOCFROMHEAP_INVHEAP);
353
354 hd = &HeapArray[heap];
355
356 // Enlarge size to smallest possible cell size
357 size += HEADERSIZE;
358 size = ROUND(size, ALIGNMENT);
359
360 // Search for block large enough
361 for (cell = hd->free; cell != NULL; cell = cell->next)
362 {
363 if ((long) size <= cell->size)
364 break;
365 }
366
367 if (cell == NULL)
368 {
369 #ifdef _DEBUG
370 OSReport("OSAllocFromHeap: Warning- failed to allocate %d bytes\n",
371 size);
372 #endif // _DEBUG
373 return NULL;
374 }
375
376 ASSERTMSG(OFFSET(cell, ALIGNMENT) == 0, OS_ERR_ALLOCFROMHEAP_BROKENHEAP);
377 ASSERTMSG(cell->hd == NULL, OS_ERR_ALLOCFROMHEAP_BROKENHEAP);
378
379 leftoverSize = cell->size - (long) size;
380 if (leftoverSize < MINOBJSIZE)
381 {
382 // Just extract this cell out since it's too small to split
383 hd->free = DLExtract(hd->free, cell);
384 }
385 else
386 {
387 // cell is large enough to split into two pieces
388 cell->size = (long) size;
389
390 // Create a new cell
391 newCell = (Cell*) ((char*) cell + size);
392 newCell->size = leftoverSize;
393 #ifdef _DEBUG
394 newCell->hd = NULL;
395 #endif
396
397 // Leave newCell in free, and take cell away
398 newCell->prev = cell->prev;
399 newCell->next = cell->next;
400 if (newCell->next != NULL)
401 newCell->next->prev = newCell;
402 if (newCell->prev != NULL)
403 newCell->prev->next = newCell;
404 else
405 {
406 ASSERTMSG(hd->free == cell, OS_ERR_ALLOCFROMHEAP_BROKENHEAP);
407 hd->free = newCell;
408 }
409 }
410
411 // Add to allocated list
412 hd->allocated = DLAddFront(hd->allocated, cell);
413
414 #ifdef _DEBUG
415 cell->hd = hd;
416 cell->requested = requested;
417 hd->headerBytes += HEADERSIZE;
418 hd->paddingBytes += cell->size - (HEADERSIZE + requested);
419 hd->payloadBytes += requested;
420 #endif // _DEBUG
421
422 return (void*) ((char*) cell + HEADERSIZE);
423 }
424
425 /*---------------------------------------------------------------------------*
426 Name: OSAllocFixed
427
428 Description: Allocates the block of memory specified by /rstart/ and
429 /rend/. Will break up any heap. Will not check for overlap
430 with other fixed blocks. May create a zero-length heap.
431
432 Arguments: rstart: pointer to starting addr of block
433 rend: pointer to ending addr of block
434
435 Returns: a null pointer or a pointer to the allocated space aligned
436 with ALIGNMENT bytes boundaries. /rstart/ and /rend/ might be
437 adjusted to the boundaries of really allocated region.
438 *---------------------------------------------------------------------------*/
OSAllocFixed(void ** rstart,void ** rend)439 void* OSAllocFixed(void** rstart, void** rend)
440 {
441 OSHeapHandle i; // heap iterator
442 Cell* cell; // object iterator
443 Cell* newCell; // for creating new objects if necessary
444 HeapDesc* hd;
445 void* start = (void*) TRUNC(*rstart, ALIGNMENT);
446 void* end = (void*) ROUND(*rend, ALIGNMENT);
447
448 ASSERTMSG(HeapArray, OS_ERR_ALLOCFIXED_NOHEAP);
449 ASSERTMSG(start < end, OS_ERR_ALLOCFIXED_INVRANGE);
450 ASSERTMSG(RangeSubset(start, end, ArenaStart, ArenaEnd),
451 OS_ERR_ALLOCFIXED_INVRANGE);
452
453 // Check overlap with any allocated blocks.
454 for (i = 0; i < NumHeaps; i++)
455 {
456 hd = &HeapArray[i];
457 if (hd->size < 0) // Is inactive?
458 continue;
459 if (DLOverlap(hd->allocated, start, end))
460 {
461 #ifdef _DEBUG
462 OSReport("OSAllocFixed: Warning - failed to allocate from %p to %p\n",
463 start, end);
464 #endif // _DEBUG
465 return NULL;
466 }
467 }
468
469 /*
470 ASSUME : if we get past all this, the fixed request will
471 not overlap with any non-contiguous free memory.
472
473 Iterate over heaps breaking up appropriate blocks.
474 note that we cannot change the size of the heap by simply subtracting
475 out the overlap area, since the heaps may be non-contiguous.
476 */
477 for (i = 0; i < NumHeaps; i++)
478 {
479 // for each free obj in heap, find and break overlaps.
480 hd = &HeapArray[i];
481
482 if (hd->size < 0) // Is inactive?
483 continue;
484 for (cell = hd->free; cell; cell = cell->next)
485 {
486 void* cellEnd = (char*) cell + cell->size;
487
488 if ((char*) cellEnd <= (char*) start)
489 continue;
490 if ((char*) end <= (char*) cell)
491 break; // Since free is sorted in order of start addresses
492
493 if (InRange(cell, (char*) start - HEADERSIZE, end) &&
494 InRange((char*) cellEnd, start, (char*) end + MINOBJSIZE))
495 {
496 if ((char*) cell < (char*) start)
497 start = (void*) cell;
498 if ((char*) end < (char*) cellEnd)
499 end = (void*) cellEnd;
500
501 // cell is completely overlaped. Just extract this block
502 hd->free = DLExtract(hd->free, cell); // Note cell->next is intact. XXX
503 hd->size -= cell->size; // Update stats
504 continue;
505 }
506
507 if (InRange(cell, (char*) start - HEADERSIZE, end))
508 {
509 if ((char*) cell < (char*) start)
510 start = (void*) cell;
511
512 // Start of object in middle of range. break off top.
513 // Avoid DLExtract() and DLInsert() since we already know
514 // exactly where the block should go
515 ASSERT(MINOBJSIZE <= (char*) cellEnd - (char*) end);
516 newCell = (Cell*) end;
517 newCell->size = (char*) cellEnd - (char*) end;
518 #ifdef _DEBUG
519 newCell->hd = NULL;
520 #endif // _DEBUG
521 newCell->next = cell->next;
522 if (newCell->next)
523 newCell->next->prev = newCell;
524 newCell->prev = cell->prev;
525 if (newCell->prev)
526 newCell->prev->next = newCell;
527 else
528 hd->free = newCell; // new head
529 hd->size -= (char*) end - (char*) cell;
530 break;
531 }
532
533 if (InRange((char*) cellEnd,
534 start, (char*) end + MINOBJSIZE))
535 {
536 if ((char*) end < (char*) cellEnd)
537 end = (void*) cellEnd;
538
539 // Nothing to change except size
540 ASSERT(MINOBJSIZE <= (char*) start - (char*) cell);
541 hd->size -= (char*) cellEnd - (char*) start;
542 cell->size = (char*) start - (char*) cell;
543 continue;
544 }
545
546 // Create a new cell after end of the fixed block.
547 ASSERT(MINOBJSIZE <= (char*) cellEnd - (char*) end);
548 newCell = (Cell*) end;
549 newCell->size = (char*) cellEnd - (char*) end;
550 #ifdef _DEBUG
551 newCell->hd = NULL;
552 #endif // _DEBUG
553 newCell->next = cell->next;
554 if (newCell->next)
555 newCell->next->prev = newCell;
556 newCell->prev = cell;
557 cell->next = newCell; // cell is before newCell
558 cell->size = (char*) start - (char*) cell;
559 hd->size -= (char*) end - (char*) start;
560 break;
561 }
562 ASSERT(0 <= hd->size);
563 }
564
565 ASSERT(OFFSET(start, ALIGNMENT) == 0);
566 ASSERT(OFFSET(end, ALIGNMENT) == 0);
567 ASSERT(start < end);
568 *rstart = start;
569 *rend = end;
570 return *rstart;
571 }
572
573 /*---------------------------------------------------------------------------*
574 Name: OSFreeToHeap
575
576 Description: Returns obj /ptr/ to /heap/.
577
578 Arguments: heap: handle to the heap that /ptr/ was allocated from
579 ptr: pointer to object previously returned from
580 OSAlloc() or OSAllocFromHeap().
581
582 Returns: None.
583 *---------------------------------------------------------------------------*/
OSFreeToHeap(OSHeapHandle heap,void * ptr)584 void OSFreeToHeap(OSHeapHandle heap, void* ptr)
585 {
586 HeapDesc* hd;
587 Cell* cell;
588
589 ASSERTMSG(HeapArray, OS_ERR_FREETOHEAP_NOHEAP);
590 ASSERTMSG(InRange(ptr, (char*) ArenaStart + HEADERSIZE, (char*) ArenaEnd),
591 OS_ERR_FREETOHEAP_INVPTR);
592 ASSERTMSG(OFFSET(ptr, ALIGNMENT) == 0, OS_ERR_FREETOHEAP_INVPTR);
593 ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_FREETOHEAP_INVHEAP);
594
595 cell = (Cell*) ((char*) ptr - HEADERSIZE);
596 hd = &HeapArray[heap];
597
598 ASSERTMSG(cell->hd == hd, OS_ERR_FREETOHEAP_INVPTR);
599 ASSERTMSG(DLLookup(hd->allocated, cell),OS_ERR_FREETOHEAP_INVPTR);
600
601 #ifdef _DEBUG
602 cell->hd = NULL;
603 hd->headerBytes -= HEADERSIZE;
604 hd->paddingBytes -= cell->size - (HEADERSIZE + cell->requested);
605 hd->payloadBytes -= cell->requested;
606 #endif // _DEBUG
607
608 // Extract from the allocated list
609 hd->allocated = DLExtract(hd->allocated, cell);
610
611 // Add in sorted order to free list (coalesced with next and prev)
612 hd->free = DLInsert(hd->free, cell);
613 }
614
615 /*---------------------------------------------------------------------------*
616 Name: OSSetCurrentHeap
617
618 Description: Sets __OSCurrHeap to /heap/. All subsequent calls to
619 OSAlloc() will be performed on this heap until another
620 call to OSSetCurrentHeap().
621
622 Arguments: heap: handle to a heap that was returned from
623 OSCreateHeap()
624
625 Returns: previous heap handle.
626 *---------------------------------------------------------------------------*/
OSSetCurrentHeap(OSHeapHandle heap)627 OSHeapHandle OSSetCurrentHeap(OSHeapHandle heap)
628 {
629 OSHeapHandle prev;
630
631 ASSERTMSG(HeapArray, OS_ERR_SETCURRENTHEAP_NOHEAP);
632 ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_SETCURRENTHEAP_INVHEAP);
633 ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_SETCURRENTHEAP_INVHEAP);
634 prev = __OSCurrHeap;
635 __OSCurrHeap = heap;
636 return prev;
637 }
638
639 /*---------------------------------------------------------------------------*
640 Name: OSInitAlloc
641
642 Description: Initializes the arena in which all heaps will reside.
643 Reserves some small amount of memory for array of heap
644 descriptors.
645
646 Arguments: arenaStart: beginning addr of arena
647 arenaEnd: ending addr of arena
648 maxHeaps: Maximum number of active heaps that will be
649 used in lifetime of program
650
651 Returns: start of real arena, aligned with 32 bytes boundaries, after
652 heap array has been allocated
653 *---------------------------------------------------------------------------*/
OSInitAlloc(void * arenaStart,void * arenaEnd,int maxHeaps)654 void* OSInitAlloc(void* arenaStart, void* arenaEnd, int maxHeaps)
655 {
656 u32 arraySize;
657 OSHeapHandle i;
658
659 ASSERTMSG(0 < maxHeaps, OS_ERR_INITALLOC_INVNUMHEAPS);
660 ASSERTMSG((char*) arenaStart < (char*) arenaEnd,
661 OS_ERR_INITALLOC_INVRANGE);
662 ASSERTMSG(maxHeaps <=
663 ((char*) arenaEnd - (char*) arenaStart) / sizeof(HeapDesc),
664 OS_ERR_INITALLOC_INSRANGE);
665
666 // Place HeapArray at head of the arena
667 arraySize = sizeof(HeapDesc) * maxHeaps;
668 HeapArray = arenaStart;
669 NumHeaps = maxHeaps;
670
671 for (i = 0; i < NumHeaps; i++)
672 {
673 HeapDesc* hd = &HeapArray[i];
674
675 hd->size = -1;
676 hd->free = hd->allocated = NULL;
677 #ifdef _DEBUG
678 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
679 #endif // _DEBUG
680 }
681
682 // Set __OSCurrHeap to an invalid value
683 __OSCurrHeap = -1;
684
685 // Reset arenaStart to the nearest reasonable location
686 arenaStart = (void*) ((char*) HeapArray + arraySize);
687 arenaStart = (void*) ROUND(arenaStart, ALIGNMENT);
688
689 ArenaStart = arenaStart;
690 ArenaEnd = (void*) TRUNC(arenaEnd, ALIGNMENT);
691 ASSERTMSG(MINOBJSIZE <= (char*) ArenaEnd - (char*) ArenaStart,
692 OS_ERR_INITALLOC_INSRANGE);
693
694 return arenaStart;
695 }
696
697 /*---------------------------------------------------------------------------*
698 Name: OSCreateHeap
699
700 Description: Reserves area of memory from /start/ to /end/ for use as a
701 heap. Initializes heap descriptor and free list.
702 Will consume one entry in heap array.
703
704 Arguments: start: starting addr of heap
705 end: ending addr of heap
706
707 Returns: If the function succeeds, it returns a new handle to heap
708 for use in OSAllocFromHeap(), OSFreeToHeap(), etc.
709 If the function fails, the return value is -1.
710 *---------------------------------------------------------------------------*/
OSCreateHeap(void * start,void * end)711 OSHeapHandle OSCreateHeap(void* start, void* end)
712 {
713 OSHeapHandle heap;
714 HeapDesc* hd;
715 Cell* cell;
716
717 ASSERTMSG(HeapArray, OS_ERR_CREATEHEAP_NOHEAP);
718 ASSERTMSG(start < end, OS_ERR_CREATEHEAP_INVRANGE);
719 start = (void*) ROUND(start, ALIGNMENT);
720 end = (void*) TRUNC(end, ALIGNMENT);
721 ASSERTMSG(start < end, OS_ERR_CREATEHEAP_INVRANGE);
722 ASSERTMSG(RangeSubset(start, end, ArenaStart, ArenaEnd),
723 OS_ERR_CREATEHEAP_INVRANGE);
724 ASSERTMSG(MINOBJSIZE <= (char*) end - (char*) start,
725 OS_ERR_CREATEHEAP_INSRANGE);
726
727 #ifdef _DEBUG
728 // Check that the range does not overlap with
729 // any other block in this or other heaps.
730 for (heap = 0; heap < NumHeaps; heap++)
731 {
732 if (HeapArray[heap].size < 0)
733 continue;
734 ASSERTMSG(!DLOverlap(HeapArray[heap].free, start, end),
735 OS_ERR_CREATEHEAP_INVRANGE);
736 ASSERTMSG(!DLOverlap(HeapArray[heap].allocated, start, end),
737 OS_ERR_CREATEHEAP_INVRANGE);
738 }
739 #endif // _DEBUG
740
741 // Search for free descriptor
742 for (heap = 0; heap < NumHeaps; heap++)
743 {
744 hd = &HeapArray[heap];
745 if (hd->size < 0)
746 {
747 hd->size = (char*) end - (char*) start;
748
749 cell = (Cell*) start;
750 cell->prev = NULL;
751 cell->next = NULL;
752 cell->size = hd->size;
753 #ifdef _DEBUG
754 cell->hd = NULL;
755 #endif // _DEBUG
756
757 hd->free = cell;
758 hd->allocated = 0;
759 #ifdef _DEBUG
760 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
761 #endif // _DEBUG
762
763 return heap;
764 // NOT REACHED HERE
765 }
766 }
767
768 // Could not find free descriptor
769 #ifdef _DEBUG
770 OSReport("OSCreateHeap: Warning - Failed to find free heap descriptor.");
771 #endif // _DEBUG
772 return -1;
773 }
774
775 /*---------------------------------------------------------------------------*
776 Name: OSDestroyHeap
777
778 Description: Frees up the descriptor for the /heap/. Subsequent
779 allocation requests from this heap will fail unless another
780 heap is created with the same handle.
781
782 Arguments: heap: handle to a live heap, previously created with
783 OSCreateHeap().
784
785 Returns: None.
786 *---------------------------------------------------------------------------*/
OSDestroyHeap(OSHeapHandle heap)787 void OSDestroyHeap(OSHeapHandle heap)
788 {
789 HeapDesc* hd;
790 #ifdef _DEBUG
791 long size;
792 #endif
793
794 ASSERTMSG(HeapArray, OS_ERR_DESTROYHEAP_NOHEAP);
795 ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_DESTROYHEAP_INVHEAP);
796 ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_DESTROYHEAP_INVHEAP);
797
798 hd = &HeapArray[heap];
799
800 #ifdef _DEBUG
801 // Check whether entire heap is empty
802 size = DLSize(hd->free);
803 if (hd->size != size)
804 {
805 OSReport("OSDestroyHeap(%d): Warning - free list size %d, heap size %d\n",
806 heap, size, hd->size);
807 }
808 #endif // _DEBUG
809
810 hd->size = -1;
811 hd->free = hd->allocated = NULL;
812
813 #ifdef _DEBUG
814 hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0;
815 if (__OSCurrHeap == heap)
816 __OSCurrHeap = -1;
817 #endif // _DEBUG
818 }
819
820 /*---------------------------------------------------------------------------*
821 Name: OSAddToHeap
822
823 Description: Adds an arbitrary block of memory to /heap/. Used to free
824 blocks previously allocated with OSAllocFixed(), or to
825 create non-contiguous heaps.
826
827 Arguments: heap: handle to live heap, previously created with
828 OSCreateHeap().
829 start: starting addr of block to add to /heap/
830 end: ending addr of block to add to /heap/
831
832 Returns: None.
833 *---------------------------------------------------------------------------*/
OSAddToHeap(OSHeapHandle heap,void * start,void * end)834 void OSAddToHeap(OSHeapHandle heap, void* start, void* end)
835 {
836 HeapDesc* hd;
837 Cell* cell;
838 #ifdef _DEBUG
839 OSHeapHandle i;
840 #endif // _DEBUG
841
842 ASSERTMSG(HeapArray, OS_ERR_ADDTOHEAP_NOHEAP);
843 ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_ADDTOHEAP_INVHEAP);
844 ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_ADDTOHEAP_INVHEAP);
845
846 hd = &HeapArray[heap];
847
848 ASSERTMSG(start < end, OS_ERR_ADDTOHEAP_INVRANGE);
849 start = (void*) ROUND(start, ALIGNMENT);
850 end = (void*) TRUNC(end, ALIGNMENT);
851 ASSERTMSG(MINOBJSIZE <= (char*) end - (char*) start,
852 OS_ERR_ADDTOHEAP_INSRANGE);
853 ASSERTMSG(RangeSubset(start, end, ArenaStart, ArenaEnd),
854 OS_ERR_ADDTOHEAP_INVRANGE);
855
856 #ifdef _DEBUG
857 // Check that the range does not already overlap with
858 // any other block in this or other heaps.
859 for (i = 0; i < NumHeaps; i++)
860 {
861 if (HeapArray[i].size < 0)
862 continue;
863 ASSERTMSG(!DLOverlap(HeapArray[i].free, start, end),
864 OS_ERR_ADDTOHEAP_INVRANGE);
865 ASSERTMSG(!DLOverlap(HeapArray[i].allocated, start, end),
866 OS_ERR_ADDTOHEAP_INVRANGE);
867 }
868 #endif // _DEBUG
869
870 // Create a new cell
871 cell = (Cell*) start;
872 cell->size = (char*) end - (char*) start;
873 #ifdef _DEBUG
874 cell->hd = NULL;
875 #endif // _DEBUG
876
877 // Insert new cell in free
878 hd->size += cell->size;
879 hd->free = DLInsert(hd->free, cell);
880 }
881
882 /*---------------------------------------------------------------------------*
883 Name: OSCheckHeap
884
885 Description: Checks heap sanity for debugging
886
887 Arguments: heap: handle to a live heap.
888
889 Returns: -1 if heap is not consistent. Otherwise, returns number
890 of bytes available in free.
891 *---------------------------------------------------------------------------*/
892
893 #define CHECK(exp) \
894 do \
895 { \
896 if (!(exp)) \
897 { \
898 OSReport("OSCheckHeap: Failed " #exp " in %d", __LINE__); \
899 return -1; \
900 } \
901 } while (0)
902
OSCheckHeap(OSHeapHandle heap)903 long OSCheckHeap(OSHeapHandle heap)
904 {
905 HeapDesc* hd;
906 Cell* cell;
907 long total = 0;
908 long free = 0;
909
910 CHECK(HeapArray);
911 CHECK(0 <= heap && heap < NumHeaps);
912
913 hd = &HeapArray[heap];
914 CHECK(0 <= hd->size);
915
916 CHECK(hd->allocated == NULL || hd->allocated->prev == NULL);
917 for (cell = hd->allocated; cell; cell = cell->next)
918 {
919 CHECK(InRange(cell, ArenaStart, ArenaEnd));
920 CHECK(OFFSET(cell, ALIGNMENT) == 0);
921 CHECK(cell->next == NULL || cell->next->prev == cell);
922 CHECK(MINOBJSIZE <= cell->size);
923 CHECK(OFFSET(cell->size, ALIGNMENT) == 0);
924
925 total += cell->size;
926 CHECK(0 < total && total <= hd->size);
927
928 #ifdef _DEBUG
929 CHECK(cell->hd == hd);
930 CHECK(HEADERSIZE + cell->requested <= cell->size);
931 #endif // _DEBUG
932 }
933
934 CHECK(hd->free == NULL || hd->free->prev == NULL);
935 for (cell = hd->free; cell; cell = cell->next)
936 {
937 CHECK(InRange(cell, ArenaStart, ArenaEnd));
938 CHECK(OFFSET(cell, ALIGNMENT) == 0);
939 CHECK(cell->next == NULL || cell->next->prev == cell);
940 CHECK(MINOBJSIZE <= cell->size);
941 CHECK(OFFSET(cell->size, ALIGNMENT) == 0);
942 CHECK(cell->next == NULL || (char*) cell + cell->size < (char*) cell->next);
943
944 total += cell->size;
945 free += cell->size - HEADERSIZE;
946 CHECK(0 < total && total <= hd->size);
947
948 #ifdef _DEBUG
949 CHECK(cell->hd == NULL);
950 #endif // _DEBUG
951 }
952
953 CHECK(total == hd->size);
954
955 return free;
956 }
957
958 /*---------------------------------------------------------------------------*
959 Name: OSReferentSize
960
961 Description: Returns size of payload
962
963 Arguments: ptr: pointer to object previously returned from
964 OSAlloc() or OSAllocFromHeap().
965
966 Returns: size of payload
967 *---------------------------------------------------------------------------*/
OSReferentSize(void * ptr)968 u32 OSReferentSize(void* ptr)
969 {
970 Cell* cell;
971
972 ASSERTMSG(HeapArray, OS_ERR_REFERENT_NOHEAP);
973 ASSERTMSG(InRange(ptr, (char*) ArenaStart + HEADERSIZE, (char*) ArenaEnd),
974 OS_ERR_REFERENT_INVPTR);
975 ASSERTMSG(OFFSET(ptr, ALIGNMENT) == 0, OS_ERR_REFERENT_INVPTR);
976
977 cell = (Cell*) ((char*) ptr - HEADERSIZE);
978
979 ASSERTMSG(cell->hd, OS_ERR_REFERENT_INVPTR);
980 ASSERTMSG(((char*) cell->hd - (char*) HeapArray) % sizeof(HeapDesc) == 0,
981 OS_ERR_REFERENT_INVPTR);
982 ASSERTMSG(HeapArray <= cell->hd && cell->hd < &HeapArray[NumHeaps],
983 OS_ERR_REFERENT_INVPTR);
984 ASSERTMSG(0 <= cell->hd->size, OS_ERR_REFERENT_INVPTR);
985 ASSERTMSG(DLLookup(cell->hd->allocated, cell),
986 OS_ERR_REFERENT_INVPTR);
987
988 return (u32) (cell->size - HEADERSIZE);
989 }
990
991 /*---------------------------------------------------------------------------*
992 Name: OSDumpHeap
993
994 Description: Dumps statistics and elements of a heap
995
996 Arguments: heap: handle to a heap.
997
998 Returns: None.
999 *---------------------------------------------------------------------------*/
OSDumpHeap(OSHeapHandle heap)1000 void OSDumpHeap(OSHeapHandle heap)
1001 {
1002 HeapDesc* hd;
1003 Cell* cell;
1004
1005 OSReport("\nOSDumpHeap(%d):\n", heap);
1006
1007 ASSERTMSG(HeapArray, OS_ERR_DUMPHEAP_NOHEAP);
1008 ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_DUMPHEAP_INVHEAP);
1009
1010 hd = &HeapArray[heap];
1011 if (hd->size < 0)
1012 {
1013 OSReport("--------Inactive\n");
1014 return;
1015 }
1016
1017 ASSERTMSG(0 <= OSCheckHeap(heap), OS_ERR_DUMPHEAP_BROKENHEAP);
1018
1019 #ifdef _DEBUG
1020 OSReport("padding %d/(%f%%) header %d/(%f%%) payload %d/(%f%%)\n",
1021 hd->paddingBytes, 100.0 * hd->paddingBytes / hd->size,
1022 hd->headerBytes, 100.0 * hd->headerBytes / hd->size,
1023 hd->payloadBytes, 100.0 * hd->payloadBytes / hd->size
1024 );
1025 #endif // _DEBUG
1026
1027 OSReport("addr\tsize\t\tend\tprev\tnext\n");
1028 OSReport("--------Allocated\n");
1029 ASSERTMSG(hd->allocated == NULL || hd->allocated->prev == NULL,
1030 OS_ERR_DUMPHEAP_BROKENHEAP);
1031 for (cell = hd->allocated; cell; cell = cell->next)
1032 {
1033 OSReport("%x\t%d\t%x\t%x\t%x\n",
1034 cell,
1035 cell->size,
1036 (char*) cell + cell->size,
1037 cell->prev,
1038 cell->next
1039 );
1040 }
1041
1042 OSReport("--------Free\n");
1043 for (cell = hd->free; cell; cell = cell->next)
1044 {
1045 OSReport("%x\t%d\t%x\t%x\t%x\n",
1046 cell,
1047 cell->size,
1048 (char*) cell + cell->size,
1049 cell->prev,
1050 cell->next
1051 );
1052 }
1053 }
1054
1055
1056 /*---------------------------------------------------------------------------*
1057 Name: OSVisitAllocated
1058
1059 Description: Visits every element of every allocated block of memory,
1060 calling a routine on each one.
1061
1062 Arguments: visitor: function to be called on each cell
1063
1064 Returns: None.
1065 *---------------------------------------------------------------------------*/
OSVisitAllocated(OSAllocVisitor visitor)1066 void OSVisitAllocated(OSAllocVisitor visitor)
1067 {
1068 u32 heap;
1069 Cell* cell;
1070
1071 for (heap = 0; heap < NumHeaps; heap++)
1072 {
1073 if (HeapArray[heap].size >= 0)
1074 {
1075 for (cell = HeapArray[heap].allocated; cell; cell = cell->next)
1076 {
1077 visitor((void*)((u8*)cell + HEADERSIZE), (u32)cell->size);
1078 }
1079 }
1080 }
1081 }
1082
1083