1 Introduction
2 Ground Rules

Building a File System
3 File Systems
4 File Content Data Structure
5 Allocation Cluster Manager
6 Exceptions and Emancipation
7 Base Classes, Testing, and More
8 File Meta Data
9 Native File Class
10 Our File System
11 Allocation Table
12 File System Support Code
13 Initializing the File System
14 Contiguous Files
15 Rebuilding the File System
16 Native File System Support Methods
17 Lookups, Wildcards, and Unicode, Oh My
18 Finishing the File System Class

The Init Program
19 Hardware Abstraction and UOS Architecture
20 Init Command Mode
21 Using Our File System
22 Hardware and Device Lists
23 Fun with Stores: Partitions
24 Fun with Stores: RAID
25 Fun with Stores: RAM Disks
26 Init wrap-up

The Executive
27 Overview of The Executive
28 Starting the Kernel
29 The Kernel
30 Making a Store Bootable
31 The MMC
32 The HMC
33 Loading the components
34 Using the File Processor
35 Symbols and the SSC
36 The File Processor and Device Management
37 The File Processor and File System Management
38 Finishing Executive Startup

Users and Security
39 Introduction to Users and Security
40 More Fun With Stores: File Heaps
41 File Heaps, part 2
42 SysUAF
43 TUser
44 SysUAF API

UCL
45 Shells and UCL

Glossary/Index


Download sources
Download binaries

The HMC

Loading the HMC
We now return to the Kernel startup routine. After loading the MMC, we use the same logic to load the HMC (Heap Management Component). Here is that code:

_HMC := TUOS_Heap_Manager( Get_Image( H, S, FSH.HMC_Position, FSH.HMC_Length, 2 ) ) ;
if( _MMC = nil ) then // None specified on boot device
begin
    if( H.Console <> nil ) then
    begin
        H.Console.Output( 'Could not load HMC', -1 ) ;
    end ;
    H.Halt ;
end ;
freemem( Buffer ) ;

The HMC manages the heap for the executive. Why do we need a heap manager component if we already have a memory management component? Can't we combine them into a single component? Well, yes, they both have to do with managing memory, but they perform radically different operations. The MMC provides an abstraction of physical memory pages. The HMC allocates and deallocates arbitrary chunks of memory - asking the MMC for pages of memory and then suballocating from that.

The HMC
How will the HMC differ from the temporary heap that we covered in an earlier article? Although it accomplishes the exact same functions, we use a more sophisticated approach. Note that our implementation could be improved upon, and perhaps we can discuss means of doing so in the future. Although performance could be improved (performance can almost always be improved), one area of concern has to do with memory fragmentation. Eventually we will discuss means of reducing fragmentation (which will also improve performance), but that is for a future article.

The design for our component is to respond to allocation requests by asking the MMC for memory, from which we allocate what was requested. Each chunk of memory requested from the MMC is managed as its own sub-heap. When we get a request, we allocate from one of our sub-heaps. We only ask the MMC for more memory if the request cannot be met with the free memory in any of our sub-heaps. Within each sub-heap, we allocate via an allocation table, as opposed to the chained buffers used in the temporary heap. This is both faster and reduces the chances of fragmentation considerably. But it requires more complicated code than the simple heap.

Here is our Sub_Heap and HMC class definitions:

type TSub_Heap = packed record
                         Start : PChar ; // Starting address of sub-heap
                         Size : int64 ; // Size of sub-heap
                         AT : TAT64 ; // Allocation table for this sub-heap
                 end ;
     PSub_Heap = ^TSub_Heap ;


type THMC = class( TUOS_Heap_Manager )
                public // Constructors and destructors...
                    constructor Create ;

                private // Instance data...
                    _Kernel : TUOS_Kernel ;
                    _MMC : TUOS_Memory_Manager ;

                    _Sub_Heaps : TList ;

                    _Allocation_Count : int64 ;
                    _Deallocation_Count : int64 ;
                    _Reallocation_Count : int64 ;
                    _In_Place_Reallocation_Count : int64 ;
                    _Allocated_Bytes : int64 ;
                    _Deallocated_Bytes : int64 ;
                    _Peak_Allocation : int64 ;
                    _Current_Allocation : int64 ;
                    _Startup : boolean ;

                    In_Getmem : boolean ;
                    SubHeap : TSub_Heap ;
                    Preallocated : integer ;

                protected // Utility routines...
                    function Sub_Heaps : TList ;
                    function MMC : TUOS_Memory_Manager ;
                    procedure Start_Subheap ;
                    function Max_Currently_Available : int64 ;

                public // API...
                    procedure Set_Error( E : longint ) ;
                    procedure Set_Kernel( K : TUOS_Kernel ) ; override ;

                    function Getmem( Size : Integer ) : Pointer ; override ;
                    procedure Free( P : pointer ) ; override ;
                    function Realloc( P : pointer ; Size : longint ) : pointer ;
                        override ;
                    function MaxAvailable : int64 ; override ;
                    function MemAvailable : int64 ; override ;
                    procedure End_Startup ; override ;

                public // Statistics...
                    function Is_Class( Name : PChar ) : boolean ; override ;
                    function Allocation_Count : int64 ; override ;
                    function Deallocation_Count : int64 ; override ;
                    function Reallocation_Count : int64 ; override ;
                    function In_Place_Reallocation_Count : int64 ; override ;
                    function Allocated_Bytes : int64 ; override ;
                    function Deallocated_Bytes : int64 ; override ;
                    function Subheap_Count : int64 ; override ;
                    function Peak_Allocation : int64 ; override ;
                    procedure Clear_Metrics ; override ;
            end ; // THMC

The sub-heaps have a starting position in memory, a size (in bytes), and an allocation table.
The first thing you might note in the HMC are the metrics, such as _Allocation_Count. These values are counts that are incremented as the HMC runs, allowing us a means of measuring various things, such as the peak amount of allocated memory, which may indicate to us how well we clean up unused memory in the executive. Another is the number of sub-heaps, which may indicate how fragmented the heap has become. We will look at how to use these in a future article.

Here are the functions to access the metrics.
// Statistics...

function THMC.Allocation_Count : int64 ;

begin
    Result := _Allocation_Count ;
end ;


function THMC.Deallocation_Count : int64 ;

begin
    Result := _Deallocation_Count ;
end ;


function THMC.Reallocation_Count : int64 ;

begin
    Result := _Reallocation_Count ;
end ;


function THMC.In_Place_Reallocation_Count : int64 ;

begin
    Result := _In_Place_Reallocation_Count ;
end ;


function THMC.Allocated_Bytes : int64 ;

begin
    Result := _Allocated_Bytes ;
end ;


function THMC.Deallocated_Bytes : int64 ;

begin
    Result := _Deallocated_Bytes ;
end ;


function THMC.Subheap_Count : int64 ;

begin
    Result := Sub_Heaps.Count ;
end ;


function THMC.Peak_Allocation : int64 ;

begin
    Result := _Peak_Allocation ;
end ;


procedure THMC.Clear_Metrics ;

begin
    _Allocation_Count := 0 ;
    _Deallocation_Count := 0 ;
    _Reallocation_Count := 0 ;
    _In_Place_Reallocation_Count := 0 ;
    _Allocated_Bytes := 0 ;
    _Deallocated_Bytes := 0 ;
    _Peak_Allocation := 0 ;
end ;

The last method provides the only means of setting the metrics from outside the class. It is used to reset the counters. The purpose of such a reset is to measure metrics from a given point, such as when changing some setting that might affect heap management/usage. This way the heap usage can be measured from the point of the change.

Here are the utility routines and constructor for our class:

// Constructors and destructors...

constructor THMC.Create ;

begin
    inherited Create ;

    _Startup := True ;
end ;


// Utility routines...

function THMC.Sub_Heaps : TList ;

begin
    if( _Sub_Heaps = nil ) then
    begin
        _Sub_Heaps := TList.Create ;
    end ;
    Result := _Sub_Heaps ;
end ;


function THMC.MMC : TUOS_Memory_Manager ;

begin
    if( _MMC = nil ) then
    begin
        _MMC := _Kernel.MMC ;
    end ;
    Result := _MMC ;
end ;


// API...

procedure THMC.Set_Error( E : longint ) ;

begin
    Set_Last_Error( Create_Error( E ) ) ;
end ;


function THMC.Is_Class( Name : PChar ) : boolean ;

var _N : string ;

begin
    _N := string( Name ) ;
    Result := lowercase( _N ) = 'thmc' ;
end ;


procedure THMC.Set_Kernel( K : TUOS_Kernel ) ;

begin
    _Kernel := K ;
end ;

Like the MMC, we have a startup flag in the HMC, and setting it is the only thing we do in the constructor. The Sub_Heaps function serves up a list of the sub-heaps, and we defer the creation of the list until it is referenced. The other methods are self-explanatory.

Once we are set up, all executive memory requests, including our own, come to us. To make sure our own requests come to us, we set the Delphi memory manager. The following routines handle this.

var _Heap : TUOS_Heap_Manager ;

function NewGetMem( Size : Integer ) : Pointer ;

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


function NewFreeMem( P : Pointer ) : Integer ;

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


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

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


{$WARNINGS OFF}
const _MM : TMemoryManager = (
                                GetMem : NewGetMem ;
                                FreeMem : NewFreeMem ;
                                ReallocMem : NewReallocMem ;
                             ) ;
{$WARNINGS ON}


procedure THMC.End_Startup ;

begin
    _Startup := False ;
    if( SubHeap.Start = nil ) then
    begin
        Start_Subheap ;
    end ;
    if( _Kernel <> nil ) then
    begin
        _Heap := _Kernel.HMC ;
        if( _Heap <> nil ) then
        begin
{$WARNINGS OFF}
            SetMemoryManager( _MM ) ;
{$WARNINGS ON}
        end ;
    end ;
    MMC.End_Startup ;
end ;

The End_Startup function, like its equivalent in the MMC, clears the Startup flag. It also links us to the memory manager, and calls Start_Subheap to initialize the first sub-heap, if it isn't already set up. The only questionable line in the routine is setting the _Heap variable from the Kernel heap rather than setting it to ourselves. This is to support the case when the HMC is hot-swapped after UOS starts up. We will discuss hot-swapping executive components in the future.

And here is the Start_Subheap method:

procedure THMC.Start_Subheap ;

var I, S : int64 ;

begin
    S := 4096 ;
    I := MMC.Allocate( 0, S, 'D', 0, 0 ) ;
    SubHeap.Size := S ;
    SubHeap.Start := pointer( I ) ;
end ;

The SubHeap instance variable is used to hold the first sub-heap that we need, before the list of subheaps is created. We ask the MMC for a chunk of memory that the subheap will point to. We default the size of this chunk to 4Kb, but the MMC may allocate something larger due to page sizes. S (the size) is passed by reference so that the MMC can change it to the actual allocation amount. We then set the sub-heap's size and pointer. We don't create or assign an allocation table, because that would require an allocation. So long as we are in startup mode, any memory requests we get are allocated out of that sub-heap. Shortly, we will see how we manage allocations in this sub-heap without an allocation table.

Now let's look at the method that allocates memory in the heap, Getmem:

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

var Loop : integer ;
    Original : integer ;
    SH : PSub_Heap ;

begin // THMC.Getmem
    // Setup...
    Original := Size ;
    Size := Size + sizeof( integer ) ;

    // Special cases...
    if( In_Getmem or _Startup) then
    begin
        if( SubHeap.Start = nil ) then
        begin
            Start_Subheap ;
        end ;
        Result := SubHeap.Start + Preallocated ;
        if( Preallocated + Size >= SubHeap.Size ) then
        begin
            Result := nil ;
            exit ;
        end ;
        Preallocated := Preallocated + Size ;
        inc( _Allocation_Count ) ;
        _Allocated_Bytes := _Allocated_Bytes + Size ;
        move( Size, PChar( Result )[ 0 ], sizeof( integer ) ) ; // Write buffer size at starting address
        Loop := integer( Result ) + sizeof( integer ) ;
        Result := pointer( Loop ) ;
        exit ;
    end ;

First we save the requested size, then we add the size of an integer to the requested size. Like the temporary heap, the HMC stores the size of the chunk just prior to the pointer that we return. Next, we check to see if we are in startup mode or if we are recursed within another call to Getmem. On some occasions, Getmem needs to allocate memory (such as another subheap). Without this check, such a situation would result in an infinite recursion that would blow the stack. In either case, we want to allocate from our initial sub-heap.
The first thing to do is check to see if the initial sub-heap has been allocated. If not, we call the Start_Subheap method that we discussed above. We set the a temporary result that points to the first free byte in the sub-heap. The Preallocated instance variable is used as a high-water mark to indicate how much of the initial sub-heap has been used. We never make this value less - only more. This saves us from needing an allocation table for the initial sub-heap, but it also prevents us from reusing any of the memory associated with the sub-heap. Requests to free memory in this sub-heap can be made, but the Preallocated variable means that it can never be reused for another allocation request. If the requested size is more than remains in the sub-heap, we return nil. This is probably a fatal error if it occurs. Next we increment the allocation, and the number of bytes allocated, counters. Finally, we store the chunk size, and then return a pointer to the chunk just following this size value. Note that, unlike the temporary heap (or the following code), we do not round the requested size up at all. This means that our allocation resolution is 1 byte, with a minimum allocation of five bytes on a 32-bit system. Because we do not reuse memory in the initial sub-heap, we are not worried about memory fragmentation here. Also, because this is a limited resource that will likely crash the executive if it is exhausted, we don't want to waste even one byte on overhead.

The remaining code in this method deals with the case when we are not in startup mode.

    // Setup...
    Result := nil ;
    Size := ( ( Size + 15 ) and ( not 15 ) ) ;
    if( _Sub_Heaps = nil ) then
    begin
        In_Getmem := True ;
        _Sub_Heaps := TList.Create ;
        In_Getmem := False ;
    end ;

In the case when we're not in startup mode, we first round the requested size (plus integer size) up to a multiple of 16 bytes. Then we see if the _Sub_Heaps list has been instantiated. If not, we create the list. However, before we do that, we set the In_Getmem flag. The call to TList.Create will, in turn, recursively call Getmem. Setting this flag ensures that we go through the startup code (described above) which will allocate from our initial sub-heap. After the list creation, we clear the flag. That means that this block of code is only executed once, since we never set _Sub_Heaps to nil. At this point, the HMC instance is fully set up, and we are ready to do the requested allocation.

    // Find a subheap that can hold the requested data...
    for Loop := 0 to Sub_Heaps.Count - 1 do
    begin
        SH := PSub_Heap( Sub_Heaps[ Loop ] ) ;
        Result := pointer( SH.AT.Allocate( Size ) ) ;
        if( Result <> nil ) then
        begin
            Result := SH.Start + integer( Result ) ; // Convert from AT offset to memory pointer
            move( Size, PChar( Result )[ 0 ], sizeof( Pointer ) ) ; // Write buffer size at starting address
            Result := PChar( Result ) + sizeof( Pointer ) ; // Return buffer just after size bytes
            inc( _Allocation_Count ) ;
            _Allocated_Bytes := _Allocated_Bytes + Size ;
            _Current_Allocation := _Current_Allocation + Size ;
            if( _Current_Allocation > _Peak_Allocation ) then
            begin
                _Peak_Allocation := _Current_Allocation ;
            end ;
            exit ;
        end ; // if( Result <> nil )
    end ; // for Loop := 0 to Sub_Heaps.Count - 1

This loop goes through all of the subheaps, looking for one that has enough contiguous free space to fulfill the requested size. The first line of the loop is not just for shorthand - it also reduces some overhead. We request the allocation from the current sub-heap. If the request returns nil, we continue on to the next sub-heap in the list. If successful, we copy the size value to the lowest address. The address we use is the returned value added to the sub-heap start because the allocation table returns a 0-based offset into the buffer that starts at the sub-heap Start pointer's address. This results in an actual memory address. Then we update the various counters and return the address to the caller.

    // If we get here, there was no room in any of the sub-heaps for the
    // requested amount.
    if( Size <= Kernel_Heap_Incremental_Allocation ) then
    begin
        Size := Kernel_Heap_Incremental_Allocation ;
    end ;
    In_Getmem := True ;
    if( Allocate( Size ) ) then
    begin
        In_Getmem := False ;
        Result := GetMem( Original ) ;
    end ;
    In_Getmem := False ;
end ; // THMC.Getmem

If we get to this point, there were no sub-heaps with sufficient free space. So, we call the local Allocate function to create another sub-heap to allocate from. Kernel_Heap_Incremental_Allocation defines the minimum amount to allocate for a sub-heap when we need to expand the heap. This is currently defaulted to 4Kb. First we see if the amount being requested is greater than this default. We will try to create a sub-heap of a size that is the greater of the two values. If the allocation is successful, we recursively call ourselves to do the actual allocation (whose size was saved in Original). In_Getmem is set before calling Allocate, and cleared afterwards. This is to ensure that any new memory allocations that happen during the Allocate call are met from the initial sub-heap. Otherwise, such an allocation could result in an infinite loop if there is no available space in any of the sub-heaps for whatever the Allocate function requests.

Here is the Allocate function:

function Allocate( Min : longint ) : boolean ;

var Bytes : integer ;
    Includes_Subheap : boolean ;
    P : pointer ;
    PI : integer ;
    S : PSub_Heap ;
    SSize : int64 ;

begin
    //TODO: Merge contiguous subheaps into single subheap
    if( SubHeap.Start = nil ) then
    begin
        Start_Subheap ;
    end ;
    if( ( SubHeap.Size = 0 ) or ( SubHeap.Start = nil ) ) then
    begin
        _Kernel.Halt( UOSErr_Exhausted_Memory ) ;
    end ;

If the initial sub-heap isn't set up yet (SubHeap.Start is nil), we call the Start_Subheap. After this, if it still isn't set up or the size is 0, we halt with an error. This is an unrecoverable error - the executive needs to allocate memory and there is no memory to allocate.

Includes_Subheap := False ;
if( Max_Currently_Available >= sizeof( TSub_Heap ) ) then // Room in heap
begin
    SSize := Size ;
    S := getmem( sizeof( TSub_Heap ) ) ; // Get space from normal heap
    if( S = nil ) then // Could not allocate a new subheap record
    begin
        Result := False ; // Should not happen
        exit ;
    end ;
    SSize := Size + 16 ; // Space for first allocation bit
end else
begin
    Includes_Subheap := True ;
    SSize := Size + sizeof( TSub_Heap ) + 16 + sizeof( pointer ) ;
    { Try to allocate space for the next subheap record as well (can't be
      sure there is space elsewhere) and lowest bit of AT, and size prefix }
end ;

Besides the memory that we are allocating on behalf of the calling code, we need to allocate memory for the TSub_Heap instance itself. The Max_Currently_Available function returns the maximum size of a memory allocation from our current set of sub-heaps. If there is room in our current set of sub-heaps, we will allocate the TSub_Heap instance from that. Otherwise, we need to include it in the memory that we will request from the MMC. In the latter case, we increase the supplemented size by the size of a TSub_Heap instance (SSize). In either case, we add 16 to the size. This is to compensate for the first allocation bit in the allocation table, which is always set, thus giving us 16 bytes less than (1 bit maps 16 bytes) than the total memory mapped by the allocation table. If we can allocate the memory for the new sub-heap from the existing sub-heaps, we call getmem to do so. In theory, if Max_Currently_Available says there is room, there should be no way for getmem to return nil. But we check anyway, just to be safe.

    if( SSize < Min ) then
    begin
        SSize := Min ;
    end ;
    P := pointer( MMC.Allocate( 0, SSize, 'D', 0, 0 ) ) ;
    if( P = nil ) then
    begin
        SSize := Size + 16 ; 
        // Try without allocating space for the subheap record (hopefully there is some free space elsewhere)

        P := pointer( MMC.Allocate( 0, SSize, 'D', 0, 0 ) ) ;
        if( P = nil ) then
        begin
            SSize := Size ; // Try absolute minimum
            P := pointer( MMC.Allocate( 0, SSize, 'D', 0, 0 ) ) ;
            if( P = nil ) then
            begin
                Result := False ;
                exit ;
            end ;
        end ;
    end ;

Next, we make sure that we are not allocated less than the minimum allocation (the Min parameter). Next, we request the memory from the MMC. If this fails, it will be because there isn't sufficient physical RAM available to supply our request. In such a case, we will try just allocating what the calling code requested, plus the 16 bytes for the first allocation bit (see above discussion). If even this fails, we will try to allocate just the requested amount. One would expect that this would fail to meet the needs of the calling code, and one would be correct with the current allocation table implementation. But this code is there for the eventual change in the allocation table implementation that won't automatically lose the first bit of allocation. But, if even that fails, we exit with a False result - meaning that the allocation failed.

    Result := True ;
    if( Includes_Subheap ) then // If space for subheap was included in the allocation
    begin
        S := P ;
    end ;
    S.Size := SSize ;
    if( Includes_Subheap ) then // If space for subheap was included in the allocation
    begin
        PI := ( sizeof( TSub_Heap ) + sizeof( Pointer ) + 15 ) and ( not 15 ) ;
        move( PI, PChar( P )[ 0 ], sizeof( Pointer ) ) ; // Write buffer size at starting address
    end ;
    S.Start := P ;

Next, we assume that we will succeed, and set our result to True. If we allocated the new sub-heap in the memory we requested from the MMC (Include_Subheap is true), then we point the sub-heap to the starting address of the memory chunk. We set the sub-heap's size, and set the size prefix if the include_subheap is true.

    if( Max_Currently_Available < Size_Needed( sizeof( TAT64 ) ) ) then
    begin
        In_Getmem := True ;
    end ;
    S.AT := TAT64.Create( 16 ) ;
    In_Getmem := False ;

    Bytes := S.Size div 16 div 8 ;
    if( Max_Currently_Available < Size_Needed( Bytes ) ) then
    begin
        In_Getmem := True ;
    end ;
    S.AT.Set_Size( Bytes ) ; // Allocation table size = 8 bits per byte x 16 bytes per bit
    In_Getmem := False ;

    S.AT.Allocate_At( SSize, Bytes * 16 * 8 - SSize ) ;
    // Make sure extra allocation bits are set if Size not on a 8*16 byte boundary

    if( SSize > Size ) then // If space for subheap was included in the allocation
    begin
        In_Getmem := True ;
        S.AT.Allocate( sizeof( TSub_Heap ) + sizeof( pointer ) - 16 ) ;
        { Mark subheap record as allocated memory (-16 because subheap starts in
          reserved first allocation block) }

        In_Getmem := False ;
        _Current_Allocation := _Current_Allocation + sizeof( TSub_Heap ) - 16 ;
        if( _Current_Allocation > _Peak_Allocation ) then
        begin
            _Peak_Allocation := _Current_Allocation ;
        end ;
    end ; // if( SSize > Size )
    In_Getmem := True ;
    Sub_Heaps.Add( S ) ;
    In_Getmem := False ;
end ; // THMC.Getmem.Allocate

Next we create the allocation table, and set its size based on the size of the memory we got from the MMC. Note that if Max_Currently_Available indicates that there isn't sufficient heap space to hold the allocation table instance, we set the In_Getmem flag so that it is allocated from the initial heap. We do something similar when we call AT.Set_Size. This function will allocate heap memory to hold the allocation table, which will be the size of the number of bytes that we pass. If this can be allocated from the general heap, we don't need to set the In_Getmem flag. Otherwise, it is allocated from the initial sub-heap.
Next, we make sure that any bits in the allocation table beyond those mapping our buffer are set. The reason for this is because the AT represents the total allocatable area in 8-bit bytes. Each bit matches our minimum heap allocation size of 16 bytes. Thus, each byte in the allocation table maps 128 bytes. But if the MMC returns a value that is not an exact multiple of 128 bytes, some of the bits in the last byte of the allocation table map to addresses outside of our memory chunk. As an example, let's say that the MMC returned a page of memory that was 192 bytes long. That requires 12 bits in the allocation table. However, the allocation table has to allocate in 8-bit chunks, meaning it needs 16 bits to map the 192 byte page. But the last 4 bits map byte offsets 192-255, which are not in the page that the MMC returns to us. If the allocation table ever were to use those bits on an allocation request, it would return addresses that are not in the page that we are using. Use of the returned address could result in any number of possible results - none of them good. In such a case, we make sure those last 4 bits are set, so that the allocation table never thinks they represent available space. In reality, it is unlikely that UOS will run on any system that allocates less than 256-byte pages, so this precaution may never be needed. However, we must try to avoid making assumptions about the hardware we are running on. To set the bits in the allocation table, we simply request an allocation of the appropriate size at the appropriate address. The allocation table will mark those bits as used.
If the new sub-heap was allocated within its own memory, we need to mark that as allocated as well. Otherwise, our first allocation request to the allocation table will point to the memory being occupied by the sub-heap data. Overwriting that with heap data would almost certainly make the executive die. Then we update the various metric data.
Finally, we have our new sub-heap set up and we add it to the Sub_Heaps list. However, we must set In_Getmem to true before doing this, or any memory allocation resulting from this operation will like use memory from our new sub-heap, which might make the available space less that what was needed for the original request which set off this chain of events. So, we force the Sub_Heaps list data to be allocated from the initial sub-heap. Then we clear the flag and the function is done. The calling code will then make the allocation call, which will come from our newly created sub-heap.
Whew! There's a lot of potential work that needs to be done when allocating heap in the executive. Fortunately, the remaning HMC methods are much simpler.

Here is the Free method.

procedure THMC.Free( P : pointer ) ;

var Loop, A, Size : integer ;
    SH : PSub_Heap ;

begin
    if( _Sub_Heaps = nil ) then
    begin
        exit ; // Cannot deallocate when in this mode
    end ;

    // Find the subheap that has the specified pointer...
    for Loop := 0 to Sub_Heaps.Count - 1 do
    begin
        SH := PSub_Heap( Sub_Heaps[ Loop ] ) ;
        if( ( P >= SH.Start ) and ( P < SH.Start + SH.Size - 1 ) ) then
        begin
            A := P - SH.Start - sizeof( Pointer ) ;
            Size := 0 ;
            move( SH.Start[ A ], Size, sizeof( Pointer ) ) ;
            SH.AT.Deallocate( A, Size ) ;
            inc( _Deallocation_Count ) ;
            _Deallocated_Bytes := _Deallocated_Bytes + Size ;
            _Current_Allocation := _Current_Allocation - Size ;
            exit ;
        end ;
    end ;
end ;

If the _Sub_Heaps list is nil, there are no sub-heaps and, thus, nothing we can deallocate. A call to this method in that case may be the result of deallocating something in the initial sub-heap. As mentioned earlier, allocations in the initial sub-heap are permanent. Otherwise, we iterate through the sub-heaps in the list. For each sub-heap, we see if the passed pointer is within the sub-heap's memory. If not, we continue on to the next sub-heap. If so, we grab the size prefix and deallocate the range from the allocation table. Then we update the metrics and exit.

Here is the Realloc method.

function THMC.Realloc( P : pointer ; Size : longint ) : pointer ;

var Loop, Old, Original : integer ;
    SH : PSub_Heap ;
    Header, Destination : pointer ;

begin
    // Setup...
    if( P = nil ) then // Reallocating a nil is the same as an allocation
    begin
        Result := Getmem( Size ) ;
        exit ;
    end ;
    Result := nil ;
    Header := Get_Size_Header( P ) ;

    // Determine old size and actual new size...
    Original := Size ;
    Size := ( Size + sizeof( pointer ) + 15 ) and ( not 15 ) ; // Round up new size
    Old := 0 ;
    move( Header^, Old, sizeof( Old ) ) ; // Get old size

    // If no change, just return the passed pointer...
    if( Old = Size ) then
    begin
        Result := P ;
        exit ;
    end ;

If the passed pointer is nil, then we are not reallocating, since we don't allow anything to be allocated at address 0. So, we treat it as a straight allocation, and just call Getmem and return. Otherwise, we get the size prefix address via the Get_Size_Header function, round the new size up to a multiple of 16 bytes, and then compare the current and new sizes to see if the request would actually result in a difference in the amount of allocated memory. If not, we simply return the current pointer - this is a logical resize-in-place, with no change in physical allocation.

    // Find appropriate sub-heap...
    for Loop := 0 to Sub_Heaps.Count - 1 do
    begin
        SH := PSub_Heap( Sub_Heaps[ Loop ] ) ;
        if( ( P >= SH.Start ) and ( P < SH.Start + SH.Size - 1 ) ) then // Found it
        begin
            Destination := pointer( SH.AT.Reallocate( Header - SH.Start, Old, Size ) ) ;
            if( Destination = nil ) then // Reallocation failure
            begin
                Destination := pointer( SH.AT.Allocate( Size ) ) ; // Allocate a new chunk
            end ;
            if( Destination = nil ) then // Could not allocate in same subheap
            begin
                Destination := Getmem( Original ) ; // Allocate space for new chunk
                if( Destination = nil ) then
                begin
                    In_Getmem := True ;
                    Destination := Getmem( Original ) ;
                    In_Getmem := False ;
                    if( Destination <> nil ) then // Allocated in reserved area
                    begin
                        // Copy old data to new location...
                        if( Old > Size ) then
                        begin
                            Old := Size ;
                        end ;
                        Old := Old - sizeof( pointer ) ; // Ignore size prefix
                        move( P^, Destination^, Old ) ;
                        Result := Destination ;

                        free( P ) ; // Deallocate old
                        exit ;
                    end ; // if( Destination <> nil )
                end ; // if( Destination <> nil )
            end else
            begin
                Destination := SH.Start + integer( Destination ) + sizeof( pointer ) ;
                // Convert from offset to pointer
            end ;
            if( Destination <> P ) then // Had to allocate to a new area
            begin
                move( P^, Destination^, Old - sizeof( pointer ) ) ;
            end else
            begin
                inc( _In_Place_Reallocation_Count ) ;
                _Current_Allocation := _Current_Allocation + ( Size - Old ) ;
                if( _Current_Allocation > _Peak_Allocation ) then
                begin
                    _Peak_Allocation := _Current_Allocation ;
                end ;
            end ;
            inc( _Reallocation_Count ) ;
            move( Size, Get_Size_Header( Destination )^, sizeof( pointer ) ) ;
            // Update size header

            Result := Destination ; // Return pointer to (new) data
            if( Destination <> P ) then // Had to allocate to a new area
            begin
                free( P ) ; // Deallocate old
            end ;
            exit ;
        end ;
    end ; // for Loop := 0 to Sub_Heaps.Count - 1

The basic operation is to try to reallocate in-place or, failing that, to reallocate within the same sub-heap or, failing that, to reallocate in any sub-heap that has space for the new allocation (in the worst case scenario, a new sub-heap will be created to meet the memory demand). These represent the fastest to slowest means of responding to the request.
As to the actual code - we loop through the sub-heaps, to find the one which corresponds to the passed pointer. Once we find the matching sub-heap, we try to extend the allocation in the allocation table. If that fails (Destination is 0), We try to allocate a buffer of the new size within this sub-heap. If that also fails, we then request a new buffer from Getmem. If that also fails, we set the In_Getmem flag and call Getmem - in effect trying to allocate from the initial heap. If we get here, it means we are desperate and it is better to use more of the initial heap than to fail to allocate memory for the executive. If we succeed, we copy the data from the old location to the new one. We have to make sure that the amount copied is the lesser of the existing or new size. Otherwise we might overwrite some other data or even access non-existant memory. Next we free the old allocation and exit.
If we couldn't reallocate in-place, we copy the data from the old location to the new. Then we update metrics. Finally, we update the size prefix and set the return value to the destination pointer. If the destination pointer is different than the original pointer (P), it means we moved the data and so we free the original pointer.

If we make it down to the following code, it means we didn't find the source pointer in any of the sub-heaps (it might be from the initial heap, or maybe from some memory directly allocated from the MMC). This means that we are not responsible for managing the memory pointed to by the passed pointer.

  // Now allocate a new chunk of memory and copy from old to new...
  Result := Getmem( Size ) ;
    if( Result = nil ) then
    begin
        exit ;
    end ;
    if( Old > Size ) then
    begin
        Old := Size ; // Don't copy more than the new size
    end ;
    move( P^, Result^, Old - sizeof( pointer ) ) ;
end ; // THMC.Realloc

In this case, all we can do is allocate the new buffer via Getmem. If that fails, we exit (returning a nil pointer). Otherwise, we determine how much to copy and move the contents from the old to the new buffer. The old memory isn't deallocated, but there is nothing we can do about that.

Here is the code for the Get_Size_Header function:

function Get_Size_Header( P : pointer ) : pointer ;

var I : integer ;

begin
    I := integer( P ) ;
    I := I - sizeof( pointer ) ;
    Result := pointer( I ) ;
end ;

It simply returns a pointer that is one integer worth of bytes less than the passed pointer. Thus, it points to the beginning of the size prefix for the passed pointer.

Now that we have the main methods of Getmem, Free, and Realloc taken care of, we turn our attention to the MaxAvailable method.

function THMC.MaxAvailable : int64 ;

var Loop : integer ;
    M : int64 ;
    SH : PSub_Heap ;

begin
    if( _Sub_Heaps = nil ) then
    begin
        if( SubHeap.Start = nil ) then
        begin
            Start_Subheap ;
        end ;
        Result := SubHeap.Size - Preallocated ; // Untested
        exit ;
    end ;

    Result := 0 ;
    for Loop := 0 to Sub_Heaps.Count - 1 do
    begin
        SH := PSub_Heap( Sub_Heaps[ Loop ] ) ;
        M := SH.AT.MaxSpace ;
        if( M > Result ) then
        begin
            Result := M ;
        end ;
    end ; // for Loop := 0 to Sub_Heaps.Count - 1
    Result := ( Result - sizeof( pointer ) ) and ( not 15 ) ;
    if( Result < 0 ) then
    begin
        Result := 0 ;
    end ;
    M := MMC.MemAvailable( 0, 'D', 0 ) ;
    if( Result < M ) then
    begin
        Result := M ;
    end ;
end ; // THMC.MaxAvailable

This method returns the size of the single largest allocatable chunk of memory. This includes what is potentially available from the MMC. We accomplish this by looping through the sub-heaps and looking at the allocation tables' MaxSpace. If _Sub_Heaps is nil, we are not yet set up. So, we simply return the remaining space in the initial sub-heap and exit. Otherwise, we take the maximum size we found and subtract the size of the size prefix and round down to the nearest 16 bytes. Finally, we see how large a chunk of memory we could get from the MMC. If that is larger than the largest space we've found so far, we return it instead.

A similar method is MemAvailable:

function THMC.MemAvailable : int64 ;

var Loop : integer ;
    SH : PSub_Heap ;

begin
    if( _Sub_Heaps = nil ) then
    begin
        if( SubHeap.Start = nil ) then
        begin
            Start_Subheap ;
        end ;
        Result := SubHeap.Size - Preallocated ; // Untested
        exit ;
    end ;

    Result := 0 ;
    for Loop := 0 to Sub_Heaps.Count - 1 do
    begin
        SH := PSub_Heap( Sub_Heaps[ Loop ] ) ;
        Result := Result + SH.AT.SpaceAvail ;
    end ;
    Result := Result + MMC.MemAvailable( 0, 'D', 0 ) ;
end ; // THMC.MemAvailable

This method does the same thing as MaxAvailable except that it adds up all available (and potential) heap space.

Finally, the Max_Currently_Available method:

function THMC.Max_Currently_Available : int64 ;

var Loop : integer ;
    M : int64 ;
    SH : PSub_Heap ;

begin
    Result := 0 ;
    if( _Sub_Heaps = nil ) then
    begin
        exit ;
    end ;

    for Loop := 0 to Sub_Heaps.Count - 1 do
    begin
        SH := PSub_Heap( Sub_Heaps[ Loop ] ) ;
        M := SH.AT.MaxSpace ;
        if( M > Result ) then
        begin
            Result := M ;
        end ;
    end ; // for Loop := 0 to Sub_Heaps.Count - 1
    Result := ( Result - sizeof( pointer ) ) and ( not 15 ) ;
    if( Result < 0 ) then
    begin
        Result := 0 ;
    end ;
end ; // THMC.Max_Currently_Available

This method is almost exactly the same as the MaxAvailable method except that it doesn't include potential space from the MMC, or from the initial sub-heap.

In the next article, we will discuss loading the other executive components.