The next thing we do is initialize our static heap. Part of this process is providing our heap with a chunk (buffer) of memory, which is obtained from the HAL. But what size to make this buffer? We ask the HAL for the memory page size. If the size returned is less than 4096 (4K) bytes, we double whatever size is returned. The hope is that we will allocate enough RAM for the heap to support the initial setup of the kernel. We ask for the page size so that we don't waste memory on systems that manage RAM on page-size boundaries. We also don't ask for more than 4K because this heap is temporary and is expected to only be necessary until the kernel sets up memory management. The memory we set aside for the static heap is permanently reserved and we don't want to waste memory. 4K ought to be sufficient for our initial needs. Whatever value we determine, we ask the HAL to set aside that much RAM and point our Buffer pointer to that memory. Buffer and Buffer_Size are global variables that are used by our temporary heap. Then we set the memory management pointers to our new heap (SetMemoryManager). Finally, we construct an instance of the kernel and start it up.

So, let's consider the static heap manager implementation. There are any number of algorithms that have been used for heap managers. One of the simpler kinds is what we will use. Here's how it works: when an allocation request comes in, we locate unused memory that is at least as large as the requested plus enough for a single integer. We place this value at the start of the free memory and place the size of the allocated chunk, in bytes, at this location. We then use the memory location after this value as the actual pointer returned to the caller. In other words, a heap pointer points to data, but prior to that location in memory is a size value.
Where do we find unused memory? The heap object initializer will set that up. But if we only allocated new memory, we would eventually run out. So, we have to return deallocated memory to the available unused memory pool. When a pointer is deallocated, we add the chunk to a "free list". This is done by writing the current Free List pointer to the start of the of the deallocated chunk (just after the size). In this way, we have a single-linked list of free chunks of memory. The advantage of this approach is that it is simple to implement and has relatively little overhead in terms of memory footprint. The disadvantages are that free space can become easily fragmented and to prevent this would require much more complex code. Further, searching for a free chunk of memory can take a long time, depending on how long the free list is, and how large a chunk is being requested from the heap. In general, this is an adequate approach, and has been used in some commercial products, such as older versions of Delphi. In fact, variants of this approach are still used in some popular software.

Because we need an integer size in all cases, and a pointer to link each chunk into the free list, it means that the minimum amount of memory that can be allocated is the size of an integer (for the size) plus the size of a pointer (which will usually default to the size of an integer). Assuming a 32-bit environment, that means that the memory must be allocated in chunks of no less than 8 bytes, regardless of what the user requests. If we allocate less than this, then there isn't room to link the chunk into the free list. So, if the user requests 1 byte from the heap, 8 bytes are still allocated. But if 5 bytes are requested, more than 8 bytes are required. How many? 9? Unlike disks, RAM has a minimum allocation size of 1 byte, since it can be addressed at the byte resolution. The temptation may be to make the minimum allocation equal to the requested bytes, with a minimum of 8. However, most CPUs access RAM more efficiently if the address being accessed is some power of 2, greater than 1 (2, 4, 8, etc). Further, the smaller the size of each chunk, the more likely it is that they heap will be fragmented. This could result in having enough total free memory for a request, but not having any of it be in a large enough contiguous chunk. On the other hand, if we allocate too much, we risk running out of RAM because we wasted too much on each allocation. To illustrate the fragmentation concern, consider the following diagram:

As can be seen from this sample layout of the heap, we have four chunks; 1 of size 128 that is used, 1 of 32 bytes that is free, 1 of 16 bytes that is used, and 1 of 64 bytes that is free. The free pointer points to the first free chunk, which points to the second free chunk, which points to nothing, because it is the end of the free list. Assuming that these chunks represent the entire heap (a very small heap), then there are 96 bytes of free space, but the maximum that could be allocated is 64 bytes. Even if the chunks were next to each other, we have provided no way to coalesce them into a single larger chunk in our very simple heap manager. It may be of no consequence to our temporary heap, but we will be doing a fair number of allocations and deallocations, so we will use a 8 byte resolution just to be safe.

Here is the definition of our global variables and our temporary heap class:

var Buffer_Size : longint ;
    Buffer : PChar ;

type TSTemp_Heap = object
                       public // Constructors and destructors...
                           constructor Init ;
                           destructor Done ;

                       public // Instance data...
                           Free_Start : PChar ; // Pointer to first free memory
                           Heap_Max : PChar ; // Highest address of heap
                           Old_MM : TMemoryManager ; // Previous memory manager

                       public // API...
                           function Getmem( Size : Integer ) : Pointer ;
                               virtual ;
                           function Free( P : Pointer ) : Integer ; virtual ;
                           function Realloc( P : Pointer ;
                               Size : Integer ) : Pointer ; virtual ;
                   end ; // TSTemp_Heap

constructor TSTemp_Heap.Init ;

begin
    Heap_Max := Buffer + Buffer_Size ;
    Free_Start := Buffer ;
    move( Buffer_Size, Free_Start[ 0 ], sizeof( Buffer_Size ) ) ;
    fillchar( Free_Start[ sizeof( integer ) ], sizeof( integer ), 0 ) ;
end ;


destructor TSTemp_Heap.Done ;

begin
end ;

function TSTemp_Heap.Getmem( Size : Integer ) : Pointer ;

var Available : integer ; // Available memory in current heap block
    Address : PChar ; // Address of current heap block
    Next : PChar ; // Next free segment in heap block
    Previous : PChar ; // Previous free segment

begin
    // Setup...
    Result := nil ;
    if( Size = 0 ) then
    begin
        exit ;
    end ;
    Size := Size + sizeof( Size ) ; // Add-in the size longword
    Size := ( Size + sizeof( Size ) * 2 - 1 ) and ( not ( sizeof( Size ) * 2 - 1 ) ) ;
    // Round size to multiple of 2 pointers

    Address := Free_Start ;
    Previous := nil ;
    while( Address <> nil ) do
    begin
        move( Address[ 0 ], Available, sizeof( Available ) ) ; // Get size of this free segment
        move( Address[ sizeof( Size ) ], Next, sizeof( Next ) ) ; // Get pointer to next free
        if( Available = Size - sizeof( Size ) ) then // Exact match
        begin
            Result := Address + sizeof( Size ) ;
            if( Previous = nil ) then
            begin
                Free_Start := Next ;
            end else
            begin
                // Update previous segment to point around this one
                move( Next, Previous[ sizeof( Size ) ], sizeof( Next ) ) ;
            end ;
        end else
        if( Available >= Size ) then // Found room in this segment
        begin
            if( Size + 2 * sizeof( Address ) > Available ) then
            begin
                Size := Available ; // Don't leave pieces smaller than two pointers
            end ;
            if( Available = Size ) then // Allocating whole chunk
            begin
                Result := Address + sizeof( Size ) ; 
                if( Previous = nil ) then
                begin
                    Free_Start := Next ;
                end else
                begin
                    // Update previous segment to point around this one
                    move( Next, Previous[ sizeof( Size ) ], sizeof( Next ) ) ;
                end ;
            end else
            begin
                { Allocate required portion of available space and update it's
                  remaining available size.  Note: we allocate at the end of the
                  current chunk to avoid adjusting the free chain. }
                Available := Available - Size ;
                Result := Address + Available + sizeof( Size ) ;
                move( Available, Address[ 0 ], sizeof( Available ) ) ; // Resize the available chunk
                move( Size, Address[ Available ], sizeof( Size ) ) ;
            end ;
            exit ;
        end ; // if( Available >= Size )
        Previous := Address ;
        Address := Next ;
    end ; // while( Address <> nil )

    // Couldn't allocate any memory...
    Result := nil ;
end ; // TSTemp_Heap.Getmem

function TSTemp_Heap.Free( P : Pointer ) : Integer ;

begin
    Result := 0 ; // Success
    if( ( P < Buffer ) or ( P > Heap_Max ) ) then
    begin
        halt ;
    end ;

    move( Free_Start, PChar( P )[ 0 ], sizeof( Free_Start ) ) ;
    Free_Start := PChar( P ) - sizeof( Free_Start ) ;
end ;

function TSTemp_Heap.Realloc( P : Pointer ; Size : Integer ) : Pointer ;

var S : integer ;
    PC : PChar ;

begin
    if( P = nil ) then
    begin
        Result := GetMem( Size ) ;
    end else
    begin
        if( Size = 0 ) then
        begin
            Free( P ) ;
            Result := nil ;
        end else
        begin
            if( ( P < Buffer ) or ( P > Heap_Max ) ) then
            begin
                halt ;
            end ;
            Size := Size + sizeof( Size ) ; // Add-in the size longword
            Size := ( Size + sizeof( Size ) * 2 - 1 ) and ( not ( sizeof( Size ) * 2 - 1 ) ) ;
            // Round size to multiple of 2 pointers
            PC := PChar( P ) ;
            Move( PC[ -sizeof( Size ) ], S, sizeof( S ) ) ; // Get size of old chunk
            if( S <> Size ) then // Something to actually do
            begin
                // Copy data to new location...
                Result := GetMem( Size - sizeof( Size ) ) ;
                if( S < Size ) then // Don't over-read or overwrite
                begin
                    move( P^, Result^, S - sizeof( Size ) ) ;
                end else
                begin
                    move( P^, Result^, Size - sizeof( Size ) ) ;
                end ;
                Free( P ) ; // ...and deallocate old allocation
            end else
            begin
                Result := P ;
            end ;
        end ; // if( Size = 0 )
    end ; // if( P = nil )
end ;

var Temp_Heap : TSTemp_Heap ;

function NewGetMem( Size : Integer ) : Pointer ;

begin
    Result := Temp_Heap.Getmem( Size ) ;
end ;


function NewFreeMem( P : Pointer ) : Integer ;

begin
    Result := 0 ;
    Temp_Heap.Free( P ) ;
end ;


function NewReallocMem( P : Pointer ; Size : Integer ) : Pointer ;

begin
    Result := Temp_Heap.Realloc( P, Size ) ;
end ;


const Temp_MM : TMemoryManager = (
                                    GetMem : NewGetMem ;
                                    FreeMem : NewFreeMem ;
                                    ReallocMem : NewReallocMem ;
                                 ) ;