test: memory.c Source File

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