Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

memory.c

Go to the documentation of this file.
00001 #include "precomp.h" 00002 #pragma hdrstop 00003 00004 // 00005 // SEGMENT_HEADER is the header that resides at the beginning of every 00006 // segment of memory managed by this package. For non-growable heaps, 00007 // there is only one segment for the entire heap. For growable heaps, 00008 // segments are created as needed whenever there is not enough free space 00009 // to satisfy an allocation request. 00010 // 00011 typedef struct _SEGMENT_HEADER { 00012 struct _SEGMENT_HEADER *Next; 00013 ULONG Size; 00014 ULONG Spare[ 2 ]; // Make sizeof match granularity 00015 } SEGMENT_HEADER, *PSEGMENT_HEADER; 00016 00017 // 00018 // FREE_HEADER is the header that resides at the beginning of every 00019 // free block of memory managed by this package. All free blocks are 00020 // linked together on a free list rooted in the heap header. The segment 00021 // field of a free header prevents free blocks in different segments from 00022 // being coalesced. 00023 // 00024 typedef struct _FREE_HEADER { 00025 struct _FREE_HEADER *Next; 00026 ULONG Size; 00027 struct _SEGMENT_HEADER *Segment; 00028 ULONG Spare; 00029 } FREE_HEADER, *PFREE_HEADER; 00030 00031 // 00032 // BUSY_HEADER is the header that resides at the beginning of allocated 00033 // block of memory managed by this package. When the block is 00034 // allocated, the Busy structure is valid. The address that the user 00035 // sees actually points to the byte following the header. When the 00036 // block is on the free list, the Free structure is valid. 00037 // 00038 typedef struct _BUSY_HEADER { 00039 struct _SEGMENT_HEADER *Segment; 00040 ULONG Size; 00041 HANDLE HandleValue; 00042 ULONG Spare; 00043 } BUSY_HEADER, *PBUSY_HEADER; 00044 00045 // 00046 // Flags are stored in the low order two bits of the first word of the 00047 // header. This is possible, since all blocks are aligned on 16 byte 00048 // boundaries. To make walking the free list fast, the flag value for 00049 // a free block is zero, so we can use the Next pointer without modification. 00050 // 00051 #define FLAGS_FREE 0x00000000 00052 #define FLAGS_BUSY 0x00000001 00053 #define FLAGS_MASK 0x00000003 00054 00055 // 00056 // All allocations are made as a multiple of ALLOCATION_GRANULARITY. 00057 // The size requested is rounded up to a multiple of the allocation 00058 // granularity. The size of an allocation header is then added and 00059 // that is the amount of memory that is actually allocated. 00060 // 00061 #define ALLOCATION_GRANULARITY 16 // bytes 00062 00063 // 00064 // HEAP_HEADER is the header for a heap. All access to the heap is 00065 // synchronized by the Lock field. 00066 // 00067 typedef struct _HEAP_HEADER { 00068 // 00069 // Heap routines use Length to determine if the heap is valid. 00070 // 00071 ULONG Length; 00072 00073 // 00074 // If the ZeroExtraMemory field is true, then the heap allocation 00075 // logic will zero initialize any extra space at the end of an allocated 00076 // block, due to rounding up to the ALIGNMENT_GRANULARITY amount. 00077 // 00078 BOOLEAN ZeroExtraMemory; 00079 00080 // 00081 // The address of the first valid address at the begining of the 00082 // heap. Used for validating pointers passed to AlFreeHeap 00083 // 00084 PVOID ValidAddress; 00085 00086 // 00087 // The address of the first address of memory beyond the end of the heap 00088 // 00089 PVOID EndAddress; 00090 00091 // 00092 // FreeList is the header for the heap free list. 00093 // 00094 ULONG Spare; // Make free list align on granularity 00095 FREE_HEADER FreeList; 00096 } HEAP_HEADER, *PHEAP_HEADER; 00097 00098 00099 // 00100 // The heap is constructed out of a memory descriptor 00101 // block that is below the descriptor for the loaded program. This block 00102 // also accomodates the loaded program stack. It is essential therefore 00103 // to estimate the stack space requirement for your arc program. (16 pages 00104 // should be enough.) The StackPages and HeapPages are 4K each. 00105 // 00106 00107 #define HEAP_ZERO_EXTRA_MEMORY 0x00000008 00108 // 00109 // Define memory allocation descriptor listhead and heap storage variables. 00110 // 00111 00112 ULONG AlHeapFree; 00113 ULONG AlHeapLimit; 00114 00115 PVOID HeapHandle; 00116 00117 00118 PVOID 00119 AlRtCreateHeap( 00120 IN ULONG Flags, 00121 IN PVOID HeapBase, 00122 IN ULONG Size 00123 ) 00124 00125 /*++ 00126 00127 Routine Description: 00128 00129 This routine initializes a heap. 00130 00131 Arguments: 00132 00133 Flags - Specifies optional attributes of the heap. 00134 00135 Valid Flags Values: 00136 HEAP_ZERO_EXTRA_MEMORY. to make sure that extra memory passed 00137 in is zeroed out. 00138 00139 HeapBase - if not NULL, this specifies the base address for memory 00140 to use as the heap. If NULL, memory is allocated by these routines. 00141 00142 Size - Size of the block of memory passed in to be used as a heap 00143 00144 Return Value: 00145 00146 PVOID - a pointer to be used in accessing the created heap. 00147 00148 --*/ 00149 00150 { 00151 PHEAP_HEADER Heap = NULL; 00152 PFREE_HEADER FreeBlock; 00153 00154 00155 Heap = (PHEAP_HEADER)HeapBase; 00156 Heap->Length = sizeof( HEAP_HEADER ); 00157 Heap->ZeroExtraMemory = (BOOLEAN)((Flags & HEAP_ZERO_EXTRA_MEMORY) ? TRUE : FALSE); 00158 Heap->ValidAddress = (PCH)Heap + ((sizeof(*Heap) + (ALLOCATION_GRANULARITY-1)) & ~(ALLOCATION_GRANULARITY-1)); 00159 Heap->EndAddress = (PCH)Heap + Size; 00160 00161 // 00162 // Initialize the free list to be a single block that starts immediately 00163 // after the heap header. 00164 // 00165 00166 FreeBlock = (PFREE_HEADER)Heap->ValidAddress; 00167 FreeBlock->Next = NULL; 00168 FreeBlock->Size = (ULONG)Heap->EndAddress - 00169 (ULONG)FreeBlock; 00170 FreeBlock->Segment = NULL; 00171 00172 Heap->FreeList.Next = FreeBlock; 00173 Heap->FreeList.Size = 0; 00174 Heap->FreeList.Segment = NULL; 00175 00176 return( (PVOID)Heap ); 00177 } // AlRtCreateHeap 00178 00179 00180 00181 #if DBG 00182 00183 BOOLEAN 00184 DumpHeapSegment( 00185 BOOLEAN DumpHeap, 00186 PHEAP_HEADER Heap, 00187 PVOID FirstValidBlock, 00188 PVOID FirstInvalidBlock, 00189 PULONG CountOfFreeBlocks 00190 ) 00191 { 00192 PVOID CurrentBlock = FirstValidBlock; 00193 PFREE_HEADER FreeBlock; 00194 PBUSY_HEADER BusyBlock; 00195 00196 while (CurrentBlock < FirstInvalidBlock) { 00197 BusyBlock = CurrentBlock; 00198 FreeBlock = CurrentBlock; 00199 if (((ULONG)BusyBlock->Segment & FLAGS_MASK) == FLAGS_BUSY) { 00200 if (DumpHeap) { 00201 AlPrint( " %08lx: BUSY Flags=%lx Size: %lx Segment: %lx\n", 00202 BusyBlock, 00203 (ULONG)BusyBlock->Segment & FLAGS_MASK, 00204 BusyBlock->Size, 00205 (ULONG)BusyBlock->Segment & ~FLAGS_MASK 00206 ); 00207 } 00208 00209 CurrentBlock = (PCH)CurrentBlock + BusyBlock->Size; 00210 } 00211 else 00212 if (((ULONG)FreeBlock->Next & FLAGS_MASK) == FLAGS_FREE) { 00213 *CountOfFreeBlocks += 1; 00214 if (DumpHeap) { 00215 AlPrint( " %08lx: FREE Next=%lx Size: %lx Segment: %lx\n", 00216 FreeBlock, 00217 FreeBlock->Next, 00218 FreeBlock->Size, 00219 FreeBlock->Segment 00220 ); 00221 } 00222 00223 CurrentBlock = (PCH)CurrentBlock + FreeBlock->Size; 00224 } 00225 else { 00226 if (DumpHeap) { 00227 AlPrint( "*** Invalid heap block at %lx\n", CurrentBlock ); 00228 } 00229 00230 return( FALSE ); 00231 } 00232 00233 } 00234 00235 if (CurrentBlock != FirstInvalidBlock) { 00236 if (DumpHeap) { 00237 AlPrint( "*** Heap segment ends at %lx instead of %lx\n", 00238 CurrentBlock, FirstInvalidBlock 00239 ); 00240 } 00241 00242 return( FALSE ); 00243 } 00244 00245 return( TRUE ); 00246 } 00247 00248 00249 BOOLEAN 00250 AlRtValidateHeap( 00251 IN PVOID HeapHandle, 00252 IN BOOLEAN DumpHeap 00253 ) 00254 { 00255 PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle; 00256 PFREE_HEADER FreeBlock; 00257 BOOLEAN HeapValid = TRUE; 00258 ULONG LengthOfFreeList; 00259 ULONG CountOfFreeBlocks; 00260 00261 // 00262 // Validate that HeapAddress points to a HEAP_HEADER structure. 00263 // 00264 00265 if (Heap->Length != sizeof( HEAP_HEADER )) { 00266 if (DumpHeap) { 00267 AlPrint( "AlRtHEAP: Invalid heap header- %lx\n", Heap ); 00268 } 00269 00270 HeapValid = FALSE; 00271 goto exit; 00272 } 00273 00274 00275 if (DumpHeap) { 00276 AlPrint( "Heap at %lx, Length=%lx\n", Heap, Heap->Length ); 00277 AlPrint( " FreeList: Head=%lx\n", Heap->FreeList.Next ); 00278 AlPrint( " Heap: End Address = %lx\n",Heap->EndAddress); 00279 } 00280 00281 00282 if (Heap->FreeList.Size != 0) { 00283 if (DumpHeap) { 00284 AlPrint( "*** head of free list is invalid (size)\n" ); 00285 } 00286 00287 HeapValid = FALSE; 00288 goto exit; 00289 } 00290 00291 LengthOfFreeList = 0; 00292 FreeBlock = Heap->FreeList.Next; 00293 while (FreeBlock) { 00294 if (DumpHeap) { 00295 AlPrint( " %08lx: Next=%lx Size: %lx Segment: %lx\n", 00296 FreeBlock, 00297 FreeBlock->Next, 00298 FreeBlock->Size, 00299 FreeBlock->Segment 00300 ); 00301 } 00302 00303 if (((ULONG)FreeBlock->Next & FLAGS_MASK) != FLAGS_FREE) { 00304 if (DumpHeap) { 00305 AlPrint( "*** free list element is not a valid free block\n" ); 00306 } 00307 00308 HeapValid = FALSE; 00309 goto exit; 00310 } 00311 00312 LengthOfFreeList += 1; 00313 FreeBlock = FreeBlock->Next; 00314 } 00315 00316 CountOfFreeBlocks = 0; 00317 if (DumpHeap) { 00318 AlPrint( " Heap Blocks starting at %lx:\n", Heap->ValidAddress ); 00319 } 00320 00321 HeapValid = DumpHeapSegment( DumpHeap, 00322 Heap, 00323 Heap->ValidAddress, 00324 Heap->EndAddress, 00325 &CountOfFreeBlocks 00326 ); 00327 if (!HeapValid) { 00328 goto exit; 00329 } 00330 00331 if (LengthOfFreeList != CountOfFreeBlocks) { 00332 if (DumpHeap) { 00333 AlPrint( "*** Number of free blocks in arena (%ld) does not match number in the free list (%ld)\n", 00334 CountOfFreeBlocks, 00335 LengthOfFreeList 00336 ); 00337 } 00338 00339 HeapValid = FALSE; 00340 goto exit; 00341 } 00342 00343 exit: 00344 return( HeapValid ); 00345 00346 } // AlRtValidateHeap 00347 00348 00349 #else 00350 00351 BOOLEAN 00352 AlRtValidateHeap( 00353 IN PVOID HeapHandle, 00354 IN BOOLEAN DumpHeap 00355 ) 00356 { 00357 return( TRUE ); 00358 } 00359 00360 #endif 00361 00362 00363 00364 PVOID 00365 AlRtAllocateHeap( 00366 IN PVOID HeapHandle, 00367 IN ULONG Size 00368 ) 00369 { 00370 PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle; 00371 ULONG allocationSize; 00372 // PSEGMENT_HEADER Segment; 00373 PFREE_HEADER FreeBlock; 00374 PFREE_HEADER PreviousFreeBlock; 00375 PFREE_HEADER NewFreeBlock; 00376 PBUSY_HEADER BusyBlock; 00377 00378 00379 // 00380 // Validate that HeapAddress points to a HEAP_HEADER structure. 00381 // 00382 00383 if (Heap->Length != sizeof( HEAP_HEADER )) { 00384 #if DBG 00385 AlPrint( "ALHEAP: Invalid heap header- %lx\n", Heap ); 00386 #endif // DBG 00387 return( NULL ); 00388 } 00389 00390 // 00391 // Additional check, see if the heap is valid, call the heap validation 00392 // code, requesting it to not dump stuff. 00393 // 00394 if(!AlRtValidateHeap( HeapHandle, FALSE)) { 00395 00396 #if DBG 00397 AlPrint("Heap validation failed\n"); 00398 #endif 00399 return ( NULL ); 00400 } 00401 00402 00403 // 00404 // Round the requested size up to the allocation granularity. Note 00405 // that if the request is for 0 bytes, we still allocate memory. 00406 // 00407 00408 allocationSize = ((Size ? Size : ALLOCATION_GRANULARITY) + 00409 sizeof( BUSY_HEADER ) + 00410 ALLOCATION_GRANULARITY - 00411 1 00412 ) & ~(ALLOCATION_GRANULARITY - 1); 00413 if (allocationSize < Size) { 00414 #if DBG 00415 AlPrint( "ALHEAP: Invalid heap size - %lx\n", Size ); 00416 // RtlpBreakPointHeap(); 00417 #endif // DBG 00418 return( NULL ); 00419 } 00420 00421 // 00422 // Point to the free list header. 00423 // 00424 00425 FreeBlock = &Heap->FreeList; 00426 #if DBG 00427 if (FreeBlock->Size != 0) { 00428 AlPrint( "ALHEAP: Heap free list HEAD hosed at %lx\n", FreeBlock ); 00429 // RtlpBreakPointHeap(); 00430 00431 return( NULL ); 00432 } 00433 #endif // DBG 00434 00435 // 00436 // Continuous loop. We'll break out of the loop when we've found 00437 // (or created) some free memory. 00438 // 00439 00440 while (TRUE) { 00441 // 00442 // Have we reached the end of the free list? 00443 // 00444 00445 if (FreeBlock->Next == NULL) 00446 return( NULL ); 00447 else { 00448 // 00449 // Point to the next free block, saving a pointer to the 00450 // previous one. 00451 // 00452 00453 PreviousFreeBlock = FreeBlock; 00454 FreeBlock = PreviousFreeBlock->Next; 00455 } 00456 00457 #if DBG 00458 if (FreeBlock->Size == 0) { 00459 AlPrint( "ALHEAP: Heap free list ENTRY hosed at %lx\n", 00460 FreeBlock 00461 ); 00462 // RtlpBreakPointHeap(); 00463 return( NULL ); 00464 } 00465 #endif // DBG 00466 00467 // 00468 // We haven't exhausted the free list yet. If this block is 00469 // large enough for what we need, break out of the while loop. 00470 // 00471 00472 if (FreeBlock->Size >= allocationSize) { 00473 break; 00474 } 00475 00476 } // while ( TRUE ) 00477 00478 // 00479 // We have found a free block that is large enough to hold what the 00480 // user requested. If it's exactly the right size, simply point the 00481 // previous free block to the successor of this free block. If it's 00482 // larger than what we want, we allocate from the front of the block, 00483 // leaving the trailing part free. Exactly the right size is fuzzy, 00484 // as if we decide to split we need at least enough extra space for 00485 // a free header plus some space to statisfy an allocation. 00486 // 00487 00488 if ((FreeBlock->Size - allocationSize) < (2 * sizeof( FREE_HEADER ))) { 00489 // 00490 // If the amount of extra space is less than twice the size of 00491 // a free header, just give the caller all the space, as the 00492 // extra amount is too small to waste a free block on. 00493 // 00494 00495 allocationSize = FreeBlock->Size; 00496 00497 // 00498 // Exactly the right size. Point previous free block to the 00499 // next free block. 00500 // 00501 00502 PreviousFreeBlock->Next = FreeBlock->Next; 00503 00504 } 00505 else { 00506 00507 // 00508 // More memory than we need. Make the trailing part of the block 00509 // into a free block. Point the previous block to the new block 00510 // and the new block to the next block. 00511 // 00512 00513 NewFreeBlock = (PFREE_HEADER)((PCH)FreeBlock + allocationSize); 00514 PreviousFreeBlock->Next = NewFreeBlock; 00515 NewFreeBlock->Next = FreeBlock->Next; 00516 NewFreeBlock->Size = FreeBlock->Size - allocationSize; 00517 NewFreeBlock->Segment = FreeBlock->Segment; 00518 } 00519 00520 // 00521 // Set up the header for the allocated block. 00522 // 00523 00524 BusyBlock = (PBUSY_HEADER)FreeBlock; 00525 BusyBlock->Segment = (PSEGMENT_HEADER)((ULONG)FreeBlock->Segment | 00526 FLAGS_BUSY 00527 ); 00528 BusyBlock->Size = allocationSize; 00529 BusyBlock->HandleValue = NULL; 00530 00531 if (Heap->ZeroExtraMemory) { 00532 ULONG extraSize; 00533 00534 extraSize = allocationSize - Size - sizeof( BUSY_HEADER ); 00535 memset( (PCHAR)BusyBlock + (allocationSize - extraSize), 00536 0, 00537 extraSize 00538 ); 00539 } 00540 00541 #if DBG 00542 BusyBlock->Spare = 0; 00543 #endif 00544 00545 // 00546 // Return the address of the user portion of the allocated block. 00547 // This is the byte following the header. 00548 // 00549 00550 return( (PVOID)(BusyBlock + 1) ); 00551 } // AlRtAllocateHeap 00552 00553 00554 PVOID 00555 AlRtFreeHeap( 00556 IN PVOID HeapHandle, 00557 IN PVOID BaseAddress 00558 ) 00559 { 00560 PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle; 00561 PFREE_HEADER FreeBlock; 00562 PFREE_HEADER PreviousFreeBlock; 00563 PFREE_HEADER SecondPrevFreeBlock; 00564 PBUSY_HEADER BusyBlock; 00565 PSEGMENT_HEADER BusySegment; 00566 ULONG BusyFlags; 00567 ULONG BusySize; 00568 00569 if (BaseAddress == NULL) { 00570 return( NULL ); 00571 } 00572 00573 // 00574 // Validate that HeapAddress points to a HEAP_HEADER structure. 00575 // 00576 00577 if (Heap->Length != sizeof( HEAP_HEADER )) { 00578 #if DBG 00579 AlPrint( "ALHEAP: Invalid heap header- %lx\n", Heap ); 00580 // RtlpBreakPointHeap(); 00581 #endif // DBG 00582 return( BaseAddress ); 00583 } 00584 00585 // 00586 // Additional check, see if the heap is valid, call the heap validation 00587 // code, requesting it to not dump stuff. 00588 // 00589 if(!AlRtValidateHeap( HeapHandle, FALSE)) { 00590 00591 #if DBG 00592 AlPrint("Heap validation failed\n"); 00593 #endif 00594 return ( BaseAddress ); 00595 } 00596 00597 00598 // 00599 // Get the 'real' address of the allocation unit. (That is, the 00600 // address of the allocation header.) Make sure the address lies 00601 // within the bounds of the valid portion of the heap. 00602 // 00603 00604 BusyBlock = (PBUSY_HEADER)BaseAddress - 1; 00605 BusyFlags = (ULONG)BusyBlock->Segment & FLAGS_MASK; 00606 BusySegment = (PSEGMENT_HEADER)((ULONG)BusyBlock->Segment & ~FLAGS_MASK); 00607 BusySize = BusyBlock->Size; 00608 00609 if (BusyFlags != FLAGS_BUSY 00610 #if DBG 00611 || (BusySegment == NULL && 00612 ((PCHAR)BusyBlock < (PCHAR)Heap->ValidAddress || 00613 (PCHAR)BusyBlock >= (PCHAR)Heap->EndAddress 00614 ) 00615 ) || 00616 (BusySegment != NULL && 00617 (BusyBlock < (PBUSY_HEADER)(BusySegment+1) || 00618 BusyBlock >= (PBUSY_HEADER)((ULONG)BusySegment + BusySegment->Size) 00619 ) 00620 ) || 00621 (BusySize < ALLOCATION_GRANULARITY 00622 ) || 00623 (BusySize & (ALLOCATION_GRANULARITY-1) != 0 00624 ) 00625 #endif // DBG 00626 ) { 00627 #if DBG 00628 AlPrint( "ALHEAP: Invalid Address specified to AlRtFreeHeap( %lx, %lx )\n", 00629 Heap, 00630 BaseAddress 00631 ); 00632 // RtlpBreakPointHeap(); 00633 #endif // DBG 00634 return( BaseAddress ); 00635 } 00636 00637 00638 // 00639 // Free blocks are stored in the free list in ascending order by 00640 // base address. As we search the free list to find the place for 00641 // this block, we remember the previous two free blocks that we 00642 // passed through. These are used during combining of adjacent 00643 // free blocks. 00644 // 00645 00646 SecondPrevFreeBlock = NULL; 00647 PreviousFreeBlock = &Heap->FreeList; 00648 #if DBG 00649 if (PreviousFreeBlock->Size != 0) { 00650 AlPrint( "ALHEAP: Heap free list HEAD hosed at %lx\n", 00651 PreviousFreeBlock 00652 ); 00653 // RtlpBreakPointHeap(); 00654 00655 return( BaseAddress ); 00656 } 00657 #endif // DBG 00658 00659 // 00660 // Continuous loop. We'll break out of the loop when we've found 00661 // the first block of free memory whose address is larger than the 00662 // address of the block being freed. (Or the end of the free list.) 00663 // 00664 00665 while (TRUE) { 00666 00667 // 00668 // Get the address of the next free block. If we've exhausted 00669 // the free list, break out of the loop -- the block we're 00670 // freeing goes at the end of the list. 00671 // 00672 00673 FreeBlock = PreviousFreeBlock->Next; 00674 00675 if (FreeBlock == NULL) { 00676 break; 00677 } 00678 00679 #if DBG 00680 if (FreeBlock->Size == 0) { 00681 AlPrint( "ALHEAP: Heap free list ENTRY hosed at %lx\n", 00682 FreeBlock 00683 ); 00684 // RtlpBreakPointHeap(); 00685 00686 return( BaseAddress ); 00687 } 00688 #endif // DBG 00689 00690 // 00691 // If the address of the current block is higher than the 00692 // address of the block we're freeing, break out of the loop. 00693 // The freed block goes immediately before the current block. 00694 // 00695 00696 if (FreeBlock > (PFREE_HEADER)BusyBlock) { 00697 break; 00698 } 00699 00700 // 00701 // We haven't found the spot yet. Remember the last two blocks. 00702 // 00703 00704 SecondPrevFreeBlock = PreviousFreeBlock; 00705 PreviousFreeBlock = FreeBlock; 00706 00707 } // while ( TRUE ) 00708 00709 00710 // 00711 // We've found the place for the block we're freeing. If the previous 00712 // block is adjacent to this one, merge the two by summing their sizes, 00713 // adjusting the address of the block being freed, and making the second 00714 // previous block the first previous block. (Note that the previous 00715 // block may actually be the listhead. In this case, the if condition 00716 // will never be true, because the Size of the listhead is 0.) 00717 // 00718 00719 if (((PCH)PreviousFreeBlock + PreviousFreeBlock->Size) == (PCH)BusyBlock && 00720 PreviousFreeBlock->Segment == BusySegment 00721 ) { 00722 BusySize += PreviousFreeBlock->Size; 00723 BusyBlock = (PBUSY_HEADER)PreviousFreeBlock; 00724 PreviousFreeBlock = SecondPrevFreeBlock; 00725 #if DBG 00726 } 00727 else 00728 if ((PreviousFreeBlock != &Heap->FreeList) && 00729 ((PCH)PreviousFreeBlock + PreviousFreeBlock->Size) > (PCH)BusyBlock 00730 ) { 00731 AlPrint( "ALHEAP: Heap free list overlaps freed block at %lx\n", 00732 BusyBlock 00733 ); 00734 // RtlpBreakPointHeap(); 00735 00736 return( BaseAddress ); 00737 #endif // DBG 00738 } 00739 00740 // 00741 // If the block being freed is adjacent to the current block, merge 00742 // the two by summing their sizes and making the next block the 00743 // current block. (Note that the current block may not exist, in 00744 // which case FreeBlock == NULL, and the if condition will not be 00745 // true.) 00746 //*** There is an assumption here that we'll never EVER use the 00747 //*** very highest part of the address space for user mode allocatable 00748 //*** memory! 00749 // 00750 00751 if (((PCH)BusyBlock + BusySize) == (PCH)FreeBlock && 00752 FreeBlock->Segment == BusySegment 00753 ) { 00754 BusySize += FreeBlock->Size; 00755 FreeBlock = FreeBlock->Next; 00756 #if DBG 00757 if (FreeBlock != NULL) { 00758 if (FreeBlock->Size == 0) { 00759 AlPrint( "ALHEAP: Heap free list ENTRY hosed at %lx\n", 00760 FreeBlock 00761 ); 00762 // RtlpBreakPointHeap(); 00763 00764 return( BaseAddress ); 00765 } 00766 } 00767 } 00768 else 00769 if ((FreeBlock != NULL) && 00770 ((PCH)BusyBlock + BusySize) > (PCH)FreeBlock 00771 ) { 00772 AlPrint( "ALHEAP: Freed block overlaps heap free list at %lx\n", 00773 BusyBlock 00774 ); 00775 // RtlpBreakPointHeap(); 00776 00777 return( BaseAddress ); 00778 #endif // DBG 00779 } 00780 00781 // 00782 // Done merging. Update the free list and the free block header. 00783 //*** May want to reclaim (i.e., release) pages sometime. That is, 00784 //*** if we find ourselves with oodles of contiguous pages on the 00785 //*** free list, we could delete them from our address space. On 00786 //*** the other hand, it probably doesn't cost very much to keep 00787 //*** them around, and if the process needed that much memory once, 00788 //*** it's likely to need it again. 00789 // 00790 00791 PreviousFreeBlock->Next = (PFREE_HEADER)BusyBlock; 00792 ((PFREE_HEADER)BusyBlock)->Next = FreeBlock; 00793 ((PFREE_HEADER)BusyBlock)->Size = BusySize; 00794 ((PFREE_HEADER)BusyBlock)->Segment = BusySegment; 00795 00796 // 00797 // Release the free list lock and return to the caller. 00798 // 00799 00800 00801 return( NULL ); 00802 } // AlRtFreeHeap 00803 00804 00805 00806 PVOID 00807 AlRtReAllocateHeap( 00808 IN PVOID HeapHandle, 00809 IN PVOID BaseAddress, 00810 IN ULONG Size 00811 ) 00812 { 00813 PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle; 00814 PVOID NewBaseAddress; 00815 ULONG allocationSize; 00816 PBUSY_HEADER BusyBlock; 00817 PBUSY_HEADER ExtraBusyBlock; 00818 PSEGMENT_HEADER BusySegment; 00819 ULONG BusyFlags; 00820 ULONG BusySize; 00821 LONG DeltaSize; 00822 00823 // 00824 // Validate that HeapAddress points to a HEAP_HEADER structure. 00825 // 00826 00827 if (Heap->Length != sizeof( HEAP_HEADER )) { 00828 #if DBG 00829 AlPrint( "ALHEAP: Invalid heap header- %lx\n", Heap ); 00830 // RtlpBreakPointHeap(); 00831 #endif // DBG 00832 return( NULL ); 00833 } 00834 00835 // 00836 // Additional check, see if the heap is valid, call the heap validation 00837 // code, requesting it to not dump stuff. 00838 // 00839 if(!AlRtValidateHeap( HeapHandle, FALSE)) { 00840 00841 #if DBG 00842 AlPrint("Heap validation failed\n"); 00843 #endif 00844 return ( NULL ); 00845 } 00846 00847 00848 // 00849 // Round the requested size up to the allocation granularity. Note 00850 // that if the request is for 0 bytes, we still allocate memory. 00851 // 00852 00853 allocationSize = ((Size ? Size : ALLOCATION_GRANULARITY) + 00854 sizeof( BUSY_HEADER ) + 00855 ALLOCATION_GRANULARITY - 00856 1 00857 ) & ~(ALLOCATION_GRANULARITY - 1); 00858 00859 if (allocationSize < Size) { 00860 #if DBG 00861 AlPrint( "ALHEAP: Invalid heap size - %lx\n", Size ); 00862 // RtlpBreakPointHeap(); 00863 #endif // DBG 00864 return( NULL ); 00865 } 00866 00867 if (BaseAddress == NULL) { 00868 #if DBG 00869 AlPrint( "ALHEAP: Invalid heap address - %lx\n", BaseAddress ); 00870 // RtlpBreakPointHeap(); 00871 #endif // DBG 00872 return( NULL ); 00873 } 00874 00875 // 00876 // Get the 'real' address of the allocation unit. (That is, the 00877 // address of the allocation header.) Make sure the address lies 00878 // within the bounds of the valid portion of the heap. 00879 // 00880 00881 BusyBlock = (PBUSY_HEADER)BaseAddress - 1; 00882 BusySize = BusyBlock->Size; 00883 BusySegment = (PSEGMENT_HEADER)((ULONG)BusyBlock->Segment & ~FLAGS_MASK); 00884 BusyFlags = (ULONG)BusyBlock->Segment & FLAGS_MASK; 00885 00886 if (BusyFlags != FLAGS_BUSY 00887 #if DBG 00888 || (BusySegment == NULL && 00889 ((PCHAR)BusyBlock < (PCHAR)Heap->ValidAddress || 00890 (PCHAR)BusyBlock >= (PCHAR)Heap->EndAddress 00891 ) 00892 ) || 00893 (BusySegment != NULL && 00894 (BusyBlock < (PBUSY_HEADER)(BusySegment+1) || 00895 BusyBlock >= (PBUSY_HEADER)((ULONG)BusySegment + BusySegment->Size) 00896 ) 00897 ) || 00898 (BusySize < ALLOCATION_GRANULARITY 00899 ) || 00900 (BusySize & (ALLOCATION_GRANULARITY-1) != 0 00901 ) 00902 #endif // DBG 00903 ) { 00904 #if DBG 00905 AlPrint( "ALHEAP: Invalid Address specified to AlRtFreeHeap( %lx, %lx )\n", 00906 Heap, 00907 BaseAddress 00908 ); 00909 // RtlpBreakPointHeap(); 00910 #endif // DBG 00911 return( NULL ); 00912 } 00913 00914 00915 // 00916 // See if new size less than or equal to the current size. 00917 // 00918 00919 DeltaSize = (LONG)(BusySize - allocationSize); 00920 if (DeltaSize >= 0) { 00921 // 00922 // Then shrinking block. If amount of shrinkage is less than 00923 // the size of a free block, then nothing to do. 00924 // 00925 00926 if (DeltaSize < sizeof( FREE_HEADER )) { 00927 if (Heap->ZeroExtraMemory) { 00928 memset( (PCHAR)BusyBlock + (allocationSize - DeltaSize),0, 00929 DeltaSize 00930 ); 00931 } 00932 00933 return( BaseAddress ); 00934 } 00935 00936 // 00937 // Otherwise, shrink size of this block to new size, and make extra 00938 // space at end look like another busy block and call AlRtFreeHeap 00939 // to free it. 00940 // 00941 00942 BusyBlock->Size = allocationSize; 00943 ExtraBusyBlock = (PBUSY_HEADER)((PCH)BusyBlock + allocationSize); 00944 ExtraBusyBlock->Segment = BusyBlock->Segment; 00945 ExtraBusyBlock->Size = (ULONG)(DeltaSize); 00946 #if DBG 00947 ExtraBusyBlock->Spare = 0; 00948 #endif 00949 00950 AlRtFreeHeap( HeapHandle, (PVOID)(ExtraBusyBlock+1) ); 00951 00952 if (Heap->ZeroExtraMemory) { 00953 ULONG extraSize; 00954 00955 extraSize = allocationSize - Size - sizeof( BUSY_HEADER ); 00956 memset( (PCHAR)BusyBlock + (allocationSize - extraSize),0, 00957 extraSize 00958 ); 00959 } 00960 00961 return( BaseAddress ); 00962 } 00963 00964 // 00965 // Otherwise growing block, so allocate a new block with the bigger 00966 // size, copy the contents of the old block to the new block and then 00967 // free the old block. Return the address of the new block. 00968 // 00969 00970 NewBaseAddress = AlRtAllocateHeap( HeapHandle, Size ); 00971 if (NewBaseAddress != NULL) { 00972 #if DBG 00973 ExtraBusyBlock = (PBUSY_HEADER)NewBaseAddress - 1; 00974 ExtraBusyBlock->Spare = 0; 00975 #endif 00976 memmove( NewBaseAddress, 00977 BaseAddress, 00978 BusySize - sizeof( BUSY_HEADER ) 00979 ); 00980 00981 AlRtFreeHeap( HeapHandle, BaseAddress ); 00982 } 00983 00984 return( NewBaseAddress ); 00985 } 00986 00987 00988 00989 00990 ARC_STATUS 00991 AlMemoryInitialize ( 00992 ULONG StackPages, 00993 ULONG HeapPages 00994 ) 00995 00996 /*++ 00997 00998 Routine Description: 00999 01000 This routine allocates stack space for the OS loader, initializes 01001 heap storage, and initializes the memory allocation list. 01002 01003 Arguments: 01004 01005 None. 01006 01007 Return Value: 01008 01009 ESUCCESS is returned if the initialization is successful. Otherwise, 01010 ENOMEM is returned. 01011 01012 --*/ 01013 01014 { 01015 01016 PMEMORY_DESCRIPTOR FreeDescriptor; 01017 PMEMORY_DESCRIPTOR ProgramDescriptor; 01018 01019 // 01020 // Find the memory descriptor that describes the allocation for the OS 01021 // loader itself. 01022 // 01023 01024 ProgramDescriptor = NULL; 01025 while ((ProgramDescriptor = ArcGetMemoryDescriptor(ProgramDescriptor)) != NULL) { 01026 if (ProgramDescriptor->MemoryType == MemoryLoadedProgram) { 01027 break; 01028 } 01029 } 01030 01031 // 01032 // If a loaded program memory descriptor was found, then it must be 01033 // for the OS loader since that is the only program that can be loaded. 01034 // If a loaded program memory descriptor was not found, then firmware 01035 // is not functioning properly and an unsuccessful status is returned. 01036 // 01037 01038 if (ProgramDescriptor == NULL) { 01039 return ENOMEM; 01040 } 01041 01042 // 01043 // Find the free memory descriptor that is just below the loaded 01044 // program in memory. There should be several megabytes of free 01045 // memory just preceeding the OS loader. 01046 // 01047 01048 FreeDescriptor = NULL; 01049 while ((FreeDescriptor = ArcGetMemoryDescriptor(FreeDescriptor)) != NULL) { 01050 if ((FreeDescriptor->MemoryType == MemoryFree) && 01051 (FreeDescriptor->PageCount >= (StackPages+HeapPages))) { 01052 break; 01053 } 01054 } 01055 01056 // 01057 // If a free memory descriptor was not found that describes the free 01058 // memory just below the OS loader, then firmware is not functioning 01059 // properly and an unsuccessful status is returned. 01060 // 01061 01062 if (FreeDescriptor == NULL) { 01063 return ENOMEM; 01064 } 01065 01066 // 01067 // Check to determine if enough free memory is available for the OS 01068 // loader stack and the heap area. If enough memory is not available, 01069 // then return an unsuccessful status. 01070 // 01071 01072 if (FreeDescriptor->PageCount < (StackPages + HeapPages)) { 01073 return ENOMEM; 01074 } 01075 01076 // 01077 // Compute the address of the loader heap, initialize the heap 01078 // allocation variables, and zero the heap memory. 01079 // 01080 01081 AlHeapFree = KSEG0_BASE | ((ProgramDescriptor->BasePage - 01082 (StackPages + HeapPages)) << PAGE_SHIFT); 01083 01084 AlHeapLimit = AlHeapFree + (HeapPages << PAGE_SHIFT); 01085 01086 memset((PVOID)AlHeapFree, 0,HeapPages << PAGE_SHIFT); 01087 01088 01089 // 01090 // Changed to new heap allocater 01091 // 01092 01093 if ((HeapHandle = AlRtCreateHeap 01094 ( 01095 HEAP_ZERO_EXTRA_MEMORY, 01096 (PVOID)AlHeapFree, 01097 HeapPages << PAGE_SHIFT 01098 )) 01099 == NULL) 01100 return ENOMEM; 01101 else 01102 return ESUCCESS; 01103 01104 } 01105 01106 01107 // 01108 // AlAllocateHeap. 01109 // 01110 // Heap space allocator. Size is in bytes required. 01111 01112 PVOID 01113 AlAllocateHeap ( 01114 IN ULONG Size 01115 ) 01116 { 01117 return (AlRtAllocateHeap 01118 ( 01119 HeapHandle, 01120 Size 01121 )); 01122 01123 } 01124 01125 01126 01127 // 3. AlDeallocateHeap 01128 // 01129 // Heap Deallocation needs to be defined and implemented. 01130 // 01131 // 01132 01133 PVOID 01134 AlDeallocateHeap ( 01135 IN PVOID HeapAddress 01136 ) 01137 { 01138 return (AlRtFreeHeap 01139 ( 01140 HeapHandle, 01141 HeapAddress 01142 )); 01143 } 01144 01145 01146 // 01147 // 4. AlReallocateHeap 01148 // 01149 // 01150 // 01151 01152 PVOID 01153 AlReallocateHeap ( 01154 IN PVOID HeapAddress, 01155 IN ULONG NewSize 01156 ) 01157 { 01158 return (AlRtReAllocateHeap 01159 ( 01160 HeapHandle, 01161 HeapAddress, 01162 NewSize 01163 )); 01164 } 01165 01166 // 01167 // 5. AlValidateHeap 01168 // 01169 // Heap validation 01170 // 01171 // 01172 01173 BOOLEAN 01174 AlValidateHeap( 01175 IN BOOLEAN DumpHeap 01176 ) 01177 { 01178 return (AlRtValidateHeap 01179 ( 01180 HeapHandle, 01181 DumpHeap 01182 )); 01183 } 01184

Generated on Sat May 15 19:40:43 2004 for test by doxygen 1.3.7