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

Starting the Kernel

Before we can create the Kernel component, we need to set some things up. So we define a global function that is called when UOS is started. At the point that the Startup function is called, the only thing that the function can assume is that the HAL is loaded and ready to go. Nothing else is available - additional memory, processor interrupts, file systems, etc. So we must proceed carfully. We can't even create a new component or allocate a buffer since there is no memory or heap management at this point. This need is so fundamental that it is our first order of business. But now we face a catch-22; how do we get a heap manager if we have no heap to use to construct our heap manager in the first place? Fortunately, as part of our kernel code, we have a simple static heap manager object. Most of our class instances are constructed on the heap (hence our problem). But we get an already-constructed static heap class as part of the Kernel code being loaded. You don't need to know all the differences between Pascal dynamic and static objects - just know that there is some RAM allocated for data when the kernel is loaded, and this data area contains our heap object.

Here's the Startup function:

var Kernel : TKernel ;

procedure Startup( H : THAL ) ;

begin
    // Set up the HAL...
    if( H = nil ) then
    begin
        H := Get_HAL ;
    end ;
    if( H = nil ) then // Couldn't get the HAL
    begin
        Halt ;
    end ;

    // Initialize the temporary heap...
    Buffer_Size := H.RAM_Page_Size ;
    while( Buffer_Size < 4096 ) do
    begin
        Buffer_Size := Buffer_Size shl 1 ;
    end ;
    Buffer := H.Allocate_RAM( Buffer_Size ) ;
    Temp_Heap.Init ;
    SetMemoryManager( Temp_MM ) ;

    // Construct and start the Kernel...
    Kernel := TKernel.Create ;
    Kernel.Startup( H ) ;
end ; // Startup

An instance of a HAL is passed to the function, and this should never be null. If it is, however, we call the Get_HAL function to create one. The included function returns nil, but a custom Kernel component could be provided by someone that creates and returns a HAL. In other words, this is a "hook" for someone wanting to write a custom kernel. If the HAL is null even after this, we just end our execution.

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

As can be seen, there are three methods: one to allocate (Getmem), one to deallocate (Free), and one to reallocate (Realloc). These correspond to the Delphi memory management unit needs. Free_Start is the pointer to the first free chunk in the free list (or nil if there is nothing in the list). Here are the constructors and destructors:

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 ;

The constructor calculates a pointer to the end of the heap, and then sets up the first free chunk. This chunk is the entire buffer, so we write the size of the buffer to the beginning of the buffer and 0 pointer after that. Thus, we have a free chunk of the size of the buffer that points to null, indicating that it is the last chunk in the list. Free_Start points to the start of the buffer. Thus, we have a single large free chunk in the list. The destructor does nothing for two reasons: 1) we never get rid of the object, and 2) even if we did destruct it, there isn't anything to do.

Now for the Getmem method.

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

If, for some reason, we cannot allocate the requested amount of memory, we return nil. So we default the result to that. Next, we add the length of an integer to the requested size (to make room for the size prefix). Then we round up to the size of two integers. On a 32-bit system, this would round up to a multiple of 8 bytes.

    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

We start with the beginning of the free list, keeping track of the previous item that we visited on the list (when we start, we have no previous item since we're on the first one). We then loop through each chunk in the list. For each chunk, we get the size from the chunk (Available), and the pointer to the next chunk (Next) in the list. If the chunk is the exact size requested, we are done and we can return the chunk to the user. This is the ideal situation as it means there is no memory fragmentation. The first thing to do is remove the chunk from the free list - if this is the first chunk, we set Free_Start to the next chunk, otherwise we set the previous chunk to point to the next chunk.
If the chunk is smaller than requested, we skip to the next chunk in the list. If the chunk is larger than the requested size, we will divide it into two smaller pieces, one to return to the user and a smaller one for the free list. However, we don't want to leave a free chunk that is smaller than the minimum 8 bytes or we can't link it into the free list. If the leftover is less than 8 bytes, we will just assign the whole chunk for the user. Note that we could search through the list twice looking for a perfect fit the first time and a closest fit the second (if we didn't find the perfect fit). That would reduce memory fragmentation, but the tradeoff is that heap operations would be slower. For this, we will risk fragmentation.
When dividing the chunk, we allocate at the end of the chunk so that we don't have to go back and change the previous pointer. All we need to do is change the size of the free chunk.

The Free method is very simple.

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 ;

First we check to see if the passed pointer is within our heap buffer. If not, we do nothing and exit. Otherwise, since the chunk being deallocated already has a size prefix, all we need to do is set the pointer after the size to the first item in the free list, and then point the free list to this chunk - essentially linking the chunk into free list, at the beginning.

Reallocation is simply a matter of allocating a new chunk of the requested size, copying the data from the old location to the newly allocated location, then deallocating the old chunk. In a more fancy implementation, we'd try to extend the existing chunk (reallocate in place). Here is the implementation for Realloc:

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 ;

The first thing we do is see if the user is trying to reallocate a null pointer. If so, we treat it the same as a simple allocation and pass the request to GetMem. Otherwise, if we are resizing the chunk to size 0, that is the same as deallocating it completely, and we pass the request on to the Free method. Then we have a sanity check to make sure that the passed pointer is within our heap. Thus, if a request comes in to reallocate memory that was allocated by someone else we will halt because this should never happen and if it did, there is no way for us to handle the request. The reason this cannot happen is because up to the point of starting the Kernel, there is no memory management. Such a pointer is probably an errant pointer indicating a rather serious bug in the Kernel.
Assuming all is right with our memory world, we get the size of the chunk being passed to us and we calculate the actual new size (rounding up as we do for new allocations). If the old and new size are the same, we just pass back the existing pointer and we are done. Otherwise we allocate the new buffer via Getmem, copy the data from the old chunk to the new chunk, and then free the old chunk. We then return the pointer to the new chunk. Under what circumstances would the old and new size be the same? One reason could simply be that the user wants to resize something (like a buffer), but it turns out that the new size is the same as the previous size. The user need not keep track of the size for the purposes of allocations/deallocations/reallocations since the heap keeps track of this itself. Another reason could be that the difference in size fits within the resolution of 8 bytes. For instance, if the user requested 10 bytes, we would round up to 16 bytes. If he then resized that same chunk to 12 bytes, we would still round up to 16 bytes, and the actual allocation would be the same.

Here's the code that links the Delphi heap requests with our temporary heap object - the SetMemoryManager call in the Startup function is what makes the connection.

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 ;
                                 ) ;

In the next article, we will look at the Kernel class instantiated and invoked by our startup code. The Kernel never returns control to this routine - it takes control until the system is shut down or powered off.