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

Our File System

So far we have only dealt with individual file access. But a file system needs to handle multiple files on a store, as well as a way to organize those files in a way that is useful to the user. In the olden days, there were no such things as folders - all the files existed in a single group. As storage devices increased in capacity, the number of files on a device increased and the need arose for the user to be able to organize the files in a hierarchical manner. RSTS/E support a three-level folder (or "directory") structure. Modern file systems allow any number of levels. UOS does the same. There is, in essence, no limit to the number of levels of folders in UOS. The question before us is: what data structure do we use to maintain, and use, the folder structure on the store? Note that we are assuming a modern random-access store (such as a disk, or RAM disk) - we don't support a UOS file system on a serial device, such as a tape. We will address the file structure of such devices later. Thus far, our classes have been functionally small - meaning that they did one or two things and that was it. The file system, however, has a lot of functionality and so we will spend the next several articles on various features of our file system. As one example, remember those file header flags? This is where we make use of them. The previous classes are used internal to our file system class and we can do whatever we want with them. However, file systems are accessed by other UOS components and will have a very specific interface that we will have to provide. I'll try to keep things as simple as possible, but we are going to cover a lot of ground before we are finished with this component. Let's dive right in...

Folders
In the case of RSTS/E and MSDOS, and other older operating systems, the folder structure and file headers were structures that the OS would follow across the disk, by means of pointers - much like our Cluster Allocation chains. In VMS, the file headers were all kept in a file called INDEXF.SYS. When the disk was initialized, INDEXF.SYS was created as a fixed-size contiguous file, which set an upper limit to the number of files that could be contained on the disk (basically dictated by the number of file headers that could fit into the file). In a previous File System class that I wrote (no, this is not my first rodeo), the folders and the files existed as a binary tree structure. Part of the reason for that was to keep the files in sorted order, by name. Many other types of file system structures have been used, or proposed, over the years by system designers. One of the more interesting ideas was to put all the file header information in an SQL database. Simple SQL statements could easily locate the files that one wants, create and delete files, and sort your results any way you wanted. We will not be going this route with UOS because 1) we want to keep the footprint small and an SQL database would require additional storage space for indexes, etc, and 2) the ease of use and general applicability of an SQL database involves additional processing overhead that will slow down our file system operations. It is a rule of thumb that the less-specific the code is, the faster it operates. My experience shows that generalized code is about 10% slower than specialized code (or worse). Sometimes the tradeoff is worth it, sometimes not.
Including the file headers within a file is a way to simplify the handling of folders. However, I don't like the idea of including everything in a single file, as VMS does. First, there is a problem of having to follow links around within the file when processing a single folder, since files from all folders are all mixed up together in the file. Note that the fixed-sized contiguous nature of the file is an implementation decision the VMS designers made for the sake of performance and isn't inherent to the concept of file headers within a file. Second, a single file makes the store overhead for files part of system overhead rather than associating the space required for file headers with the user who owns the files. In cases where we want to limit the space that a given user can use, this is a fairer approach - a user with thousands of small files may end up using as much storage space as a user with a few large files. We could figure out how much space a user uses in a single file, but it becomes more complicated and costly to determine in that case. So, UOS will implement a modified VMS approach. We will keep the file headers within a file for each folder, but each folder will be a separate file. We will make no effort to keep the files sorted in any order in the folder files. This is for file system performance, simplification, and the fact that the user may wish to sort by something other than name (such as date created or size). Why go to the trouble to sort by some metric that the user doesn't use? We will let the directory/explorer utility manage the sorting of files based on whatever criteria the user wants. There is also no limit to the number of files on a given store, other than the total capacity of that store.

The folder file will simply be an array of file header records. When a file is deleted, the name entry of the file header will be set to 0. When a new file is created, we will use the first unused header (one with a name of 0) and write our header there. If we run out of space in the file, we will simply extend it with another header. Iterating through the files in the folder is as easy as reading through the headers, skipping the unused ones.

Logically all folders exist within another folder, except for the topmost level of folder (the root folder). That is, each folder's parent contains a header for the child folder, which points to the folder file that contains the headers for the files in that child folder. Some of those files may be children folders of that folder, and so on. The root folder is a special case, because it has no parent folder, which begs the question: how do we find the root folder file so that we can find the rest of the files on the store? In some operating systems, the root folder is in a fixed location on the disk. In UOS, we will have a store header, which contains information about the store as well as a pointer to the root folder file.

Boot blocks and store headers
We have essentially defined the file system structure for the UOS file system (UOSFS) in the previous paragraphs. But there are some other considerations before we can start writing our UOSFS class. Hard disks have the possibility of being bootable - that is, being able to load an OS from (loading the OS is called "booting"). This is handled by considering the first sector of the disk to be a boot block. A boot block contains a "bootstrap", which is a small program that loads the operating system. The term "bootstrap" came from the old saying "pulling yourself up by your bootstraps". The computer hardware automatically loads the boot block and starts executing the code loaded from that block. Even non-bootable disks have a bootstrap - the bootstrap simply tells the user that the disk isn't bootable. Thus, we cannot place the store header in the first sector. In fact, we can't be sure that the bootstrap doesn't take more than one sector, depending upon the hardware that UOS is running on. So, how can we place the store header in a place that we can find no matter what? The approach we will take is to include a pointer to the store header within the boot sector. We will place it at offset 16 in the header, which will allow the bootstrap to jump over the 8-byte-long value, but allow us to find it easily. This should work on any hardware that UOS will run on, and allows us to place the store header anywhere on the store. Here is the first part of the bootstrap layout and store header layout. Note that there will be more items in the store header, but we will address those later.

type FS_Boot_Record = packed record // First 24 bytes of store header
                          Bootstrap1 : array[ 0..15 ] of byte ;
                          Header : TStore_Address64 ;
                      end ;

     FS_Header = packed record
                     ID : smallint ; // -1
                     ID1 : byte ; // 135
                     Version : byte ; { UOSFS format version 10 = V1.0 }
                     AT_Offset : TStore_Adddress64 ; { Current AT location }
                     AT_Size : TStore_Size64 ; { AT size }
                     Flags : int64 ;
                     Clustersize : cardinal ; // Volume clustersize
                     Folder_Clustersize : cardinal ; // Default folder file clustersize
                 end ;

We don't know how ahead of time how large a boot block is, since they will vary from store to store. So, we only define the first 24 bytes of the boot block - basically the header pointer and the code prior to it.
The ID and ID1 items are special codes that allow us to verify that this is a valid UOSFS header. If the header pointer is invalid or the cluster it points to does not have a valid header (as defined by the special codes), we know that this store does not have a valid UOS file system on it. It may have some other file system or be uninitialized. Version indicates the version of the file system (in case we make future revisions). For now, it should be 10 to indicate version 1.0. Clustersize indicates the minimum allocation cluster size for the store. Folder_Clustersize indicates the clustersize for folder files. AT_Size and AT_Offset indicate the location of the allocation table, which is used by the managed store to keep track of what clusters are allocated.

Allocation tables
The allocation table is an array of bits that indicate which store clusters are allocated. Each byte holds flags for eight clusters. To calculate the length of the allocation table, take the size of the disk, divide by the store clustersize (either physical or the clustersize in the header) to get the total number of clusters on the store. Divide by eight and that is the number of bytes required to represent the entire store. The smaller the store's cluster size, the more clusters exist on the store, and the larger the allocation table will be. In terms of store footprint, we are trading allocation table footprint with file overhead. A larger allocation table means more efficient use of the rest of the store. However that is not the only issue to consider. For performance sake, the allocation table will be kept and modified in memory until such time as the system has an orderly shut down. That way we save a bunch of I/O operations from not having to write the table back to the store on each allocation/deallocation. This means that there is a memory footprint component to the allocation table size. We will default things for the user, but we will also allow the user to optimize the size to fit their unique performance profile. But wait! Don't we run the risk of corrupting data if we don't update the allocation table on the store when it changes? If we simply used the store allocation table on start up, that is a very real possibility. However, we won't do that. One of the flags in the store header indicates whether or not the store is "dirty". The flag is set when the store is "mounted" (made ready for access), and cleared when the store is "dismounted" (usually when UOS shuts down). Before we clear the flag, we write the current allocation table out to the store. When we mount the store, we first check to see if the dirty flag is set. If so, we know that the store wasn't dismounted and the allocation table may not be accurate. In this case, we will rebuild the allocation table from scratch by following the data structures in our file system and marking used clusters as such. This rebuild process will result in any "lost" clusters (if an error happened between clearing a pointer and the actual deallocation) being recovered as well.
Note that there are two types of stores: 1) fixed stores, such as hard disks, and 2) variable stores, such as container files. In the second case, AT_Size grows as the store grows and AT_Offset is managed by the store itself. Either way, we tell the store our AT size and offset. Whether or not it uses it is up to the store itself and isn't something we need to concern ourselves with in the file system class.

Managed Store redux
Let's take a deeper look at managed stores. We can view a managed store as a layer over an unmanaged store that uses an allocation table to keep track of allocated space, although the actual implementation may differ. In fact, all normal store operations are passed on to the store that we are managing. We only handle those operations that involve the allocation table. So, let's write our generic managed store. Here is the class definition:

type TManaged_Store_Statistics64 = packed record
                                       Bytes_Allocated : int64 ; 
				       { Sum total size of allocations }
                                       Bytes_Deallocated : int64 ;
				       { Sum total size of deallocations }
                                       Allocations : int64 ; { Count of allocations }
                                       Deallocations : int64 ; { Count of deallocations }
                                       Reallocations : int64 ;
				       { Count of physical reallocations }
                                       Reallocations_In_Place : int64 ;
                                       { Count of reallocations not requiring physical
				         reallocation }
                                       Root_Writes : int64 ; { Count of writes to root }
                                       Root_Reads : int64 ; { Count of reads from root }
                                       Copies : int64 ; { Copy operation count }
                                       Bytes_Copied : int64 ;
				       { Bytes copied via Copy method }
                                       Fills : int64 ; { Fill operation count }
                                       Bytes_Filled : int64 ;
				       { Bytes modified via Fill method }
                                       Extensions : int64 ;
				       { Number of extension operations }
                                   end ; { TManaged_Store_Statistics64 }


type TCOM_Managed_Store64 = class( TStandard_COM_Store64 )
                                public { Instance data... }
                                    Statistics : TManaged_Store_Statistics64 ;

                                public { API... }
                                    function Allocate( Size : TStore_Address64 ) : 
					TStore_Address64 ;
                                        virtual ; stdcall ; { Allocate space}
                                    function Allocate_At( Offset, 
					Size : TStore_Address64 ) : boolean ;
                                        virtual ; stdcall ;
					{ Allocate space at specific  location }
                                    procedure Copy( Source, Destination : TStore_Address64 ;
                                        Count : integer ) ; virtual ; stdcall ; { Copy data }
                                    procedure Deallocate( PTR, Size : TStore_Address64 ) ;
                                        virtual ; stdcall ; { Deallocate space }
                                    procedure Fill( PTR : TStore_Address64 ;
					Count : integer ; Value : byte ) ;
					virtual ; stdcall ;
                                    function Reallocate( PTR, Old,
					New : TStore_Address64 ) : TStore_Address64 ;
                                        virtual ; stdcall ;
                                    procedure Read( PTR, Size : TStore_Address64 ;
                                        var Buffer ) ; virtual ; stdcall ; { Read data }
                                    procedure Write( PTR, Size : TStore_Address64 ;
                                        var Buffer ) ; virtual ; stdcall ; { Write data }
                                    function SpaceAvail : TStore_Address64 ;
                                        virtual ; stdcall ;
                                    function XSpaceAvail : TStore_Address64 ;
                                        virtual ; stdcall ;
                                    function MaxSpace : TStore_Address64 ;
                                        virtual ; stdcall ;
                                    procedure Get_Root( var Buf ) ;
                                        virtual ; stdcall ;
                                    procedure Set_Root( var Buf ) ;
                                        virtual ; stdcall ;
                                    function Allocation_Table_Size : longint ;
                                        virtual ; stdcall ;
                                    procedure Get_Allocation_Table_Data( Buff : pointer ;
                                        _Size : longint ) ;
                                        virtual ; stdcall ;
                                    procedure Set_Allocation_Table_Data( Buff : pointer ;
                                        _Size : longint ) ;
                                        virtual ; stdcall ;
                                    procedure Set_Min_Storage( _Size : longint ) ;
                                        virtual ; stdcall ;
                                    procedure Set_Allocation_Table_Offset( Value : TStore_Address64 ) ;
                                        virtual ; stdcall ;
                                    function Get_Allocation_Table_Offset : TStore_Address64 ;
                                        virtual ; stdcall ;
                                    procedure Flush_Allocation_Table ;
                                        virtual ; stdcall ;
                                    function Get_Store : TCOM_Store64 ;
                                        virtual ; stdcall ;
                                    procedure Set_Store( _S : TCOM_Store64 ) ;
                                        virtual ; stdcall ;
                            end ; { TCOM_Managed_Store64 }

The first thing we see is the Statistics. This is a series of counters that the class will update as operations happen. The user can examine the statistics and gain a better understanding of the performance profile of his system. You may notice that there are no statistics for actual reads and writes. This is because the ancestor store class has those counters.
This is the base class for all managed 64-bit stores, so we will need to create a descendent implementation. Here is our class definition:
type TUOS_Managed_Store = class( TCOM_Managed_Store64 )
                              public // Constructors and destructors...
                                  destructor Destroy ; override ;

                              private // Instance data...
                                  _Store : TCOM_Store64 ;
                                  _Clustersize : cardinal ;
                                  _AT : TAT64 ;

                              protected // Internal utility routines...
                                  function AT : TAT64 ;
                                  function Clustersize : cardinal ;

                              public { Overrides... }
                                  function Is_Class( Name : PChar ) : boolean ;
                                      override ;

                                  function Read_Data( var Data ; Address,
                                      _Size : TStore_Address64 ;
                                      var UEC : TUnified_Exception ) : TStore_Address64 ;
                                      override ;

                                  function Write_Data( var Data ; Address,
                                      _Size : TStore_Address64 ;
                                      var UEC : TUnified_Exception ) : TStore_Address64 ;
                                      override ;

                                  function Max_Storage : TStore_Size64 ;
                                      override ;

                                  function Min_Storage : TStore_Address64 ;
                                      override ;

                                  function Extend( Amount : TStore_Address64 ) :
                                      TStore_Address64 ; override ;

                                  function Get_Read_Only : boolean ;
                                      override ;

                                  function Get_Write_Only : boolean ;
                                      override ;

                                  procedure Format ; override ;

                                  function Get_Name : PChar ; override ;

                                  function Get_Cache : TCOM_Cache64 ;
                                      override ;

                                  procedure Set_Cache( Value : TCOM_Cache64 ) ;
                                      override ;

                                  function Contiguous_Store : boolean ;
                                      override ;

                                  procedure Set_Max_Storage( Value : TStore_Address64 ;
                                      var Res : TUnified_Exception ) ;
                                      override ;

                                  function Extended_Size : TStore_Address64 ;
                                      override ;

                                  procedure Set_Read_Only( Value : boolean ) ;
                                      override ;
                                  procedure Set_Write_Only( Value : boolean ) ;
                                      override ;

                                  function Allocate( Size : TStore_Address64 ) :
                                      TStore_Address64 ; override ;
                                  function Allocate_At( Offset,
                                      Size : TStore_Address64 ) : boolean ;
                                      override ;
                                  procedure Copy( Source,
                                      Destination : TStore_Address64 ;
                                      Count : integer ) ; override ; { Copy data }
                                  procedure Deallocate( PTR,
                                      Size : TStore_Address64 ) ;
                                      override ;
                                  procedure Fill( PTR : TStore_Address64 ;
                                      Count : integer ; Value : byte ) ;
                                      override ;
                                  function Reallocate( PTR, Old,
                                      New : TStore_Address64 ) : TStore_Address64 ;
                                      override ;
                                  function SpaceAvail : TStore_Address64 ;
                                      override ;
                                  function XSpaceAvail : TStore_Address64 ;
                                      override ;
                                  function MaxSpace : TStore_Address64 ;
                                      override ;
                                  procedure Get_Root( var Buf ) ; override ;
                                  procedure Set_Root( var Buf ) ; override ;
                                  function Allocation_Table_Size : longint ;
                                      override ;
                                  procedure Get_Allocation_Table_Data( Buff : pointer ;
                                      _Size : longint ) ;
                                      override ;
                                  procedure Set_Allocation_Table_Data( Buff : pointer ;
                                      _Size : longint ) ;
                                      override ;
                                  procedure Set_Min_Storage( _Size : longint ) ;
                                      override ;
                                  procedure Set_Allocation_Table_Offset( Value : TStore_Address64 ) ;
                                      override ;
                                  function Get_Allocation_Table_Offset : TStore_Address64 ;
                                      override ;
                                  procedure Flush_Allocation_Table ; override ;
                                  function Get_Store : TCOM_Store64 ; override ;
                                  procedure Set_Store( Value : TCOM_Store64 ) ;
                                      override ;
                          end ; { TUOS_Managed_Store }

Here is our destructor.

destructor TUOS_Managed_Store.Destroy ;

begin
    Set_Store( nil ) ;

    inherited Destroy ;
end ;

Our internal methods provide for delayed creation of the allocation table, and determine our clustersize based on either the store or our assigned value. And we have an override for the Is_Class method.
function TUOS_Managed_Store.AT : TAT64 ;

begin
    if( _AT = nil ) then
    begin
        _AT := TAT64.Create( Clustersize ) ;
        _AT.Set_Store( _Store ) ;
    end ;
    Result := _AT ;
end ;


function TUOS_Managed_Store.Clustersize : cardinal ;

begin
    if( ( _Clustersize = 0 ) and ( _Store <> nil ) ) then
    begin
        Result := _Store.Min_Storage ;
    end else
    begin
        Result := _Clustersize ;
    end ;
end ;


// Overrides...

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

begin
    Result := lowercase( Name ) = 'tuos_managed_store' ;
    if( not Result ) then
    begin
        Result := inherited Is_Class( Name ) ;
    end ;
end ;

Many of our class' methods simply pass the requests on to the store that we are managing. We also propogate exceptions back from the store.
function TUOS_Managed_Store.Read_Data( var Data ;
    Address, _Size : TStore_Address64 ;
    var UEC : TUnified_Exception ) : TStore_Address64 ;

begin
    if( Address < Clustersize ) then
    begin
        // Have to use set/get root methods to read the first cluster
        UEC := Create_Exception( UOS_MStore_Error_Access_Violation, nil ) ;
        _Last_Error := UEC ;
        Result := 0 ;
        exit ;
    end ;
    Result := _Store.Read_Data( Data, Address, _Size, UEC ) ;
    if( UEC <> nil ) then
    begin
        UEC := Create_Exception( UOS_MStore_Error_IO_Failure, UEC ) ;
    end ;
end ;


function TUOS_Managed_Store.Write_Data( var Data ;
    Address, _Size : TStore_Address64 ;
    var UEC : TUnified_Exception ) : TStore_Address64 ;

begin
    if( Address < Clustersize ) then
    begin
        // Have to use set/get root methods to read the first cluster
        UEC := Create_Exception( UOS_MStore_Error_Access_Violation, nil ) ;
        _Last_Error := UEC ;
        Result := 0 ;
        exit ;
    end ;
    Result := _Store.Write_Data( Data, Address, _Size, UEC ) ;
    if( UEC <> nil ) then
    begin
        UEC := Create_Exception( UOS_MStore_Error_IO_Failure, UEC ) ;
    end ;
end ;


function TUOS_Managed_Store.Max_Storage : TStore_Size64 ;

begin
    if( _Store = nil ) then
    begin
        Result := 0 ;
    end else
    begin
        Result := _Store.Max_Storage ;
    end ;
end ;


function TUOS_Managed_Store.Min_Storage : TStore_Address64 ;

begin
    if( _Store = nil ) then
    begin
        Result := 0 ;
    end else
    begin
        Result := _Store.Min_Storage ;
    end ;
end ;


function TUOS_Managed_Store.Extend( Amount : TStore_Address64 ) : TStore_Address64 ;

begin
    if( _Store = nil ) then
    begin
        Result := 0 ;
    end else
    begin
        Result := _Store.Extend( Amount ) ;
        Set_Last_Error( _Store.Last_Error ) ;
        inc( Statistics.Extensions ) ;
    end ;
end ;


function TUOS_Managed_Store.Get_Read_Only : boolean ;

begin
    if( _Store = nil ) then
    begin
        Result := True ;
    end else
    begin
        Result := _Store.Get_Read_Only ;
    end ;
end ;


function TUOS_Managed_Store.Get_Write_Only : boolean ;

begin
    if( _Store = nil ) then
    begin
        Result := False ;
    end else
    begin
        Result := _Store.Get_Write_Only ;
    end ;
end ;


procedure TUOS_Managed_Store.Format ;

begin
    if( _Store <> nil ) then
    begin
        _Store.Format ;
        Set_Last_Error( _Store.Last_Error ) ;
    end ;
end ;


function TUOS_Managed_Store.Get_Name : PChar ;

begin
    if( _Store = nil ) then
    begin
        Result := nil ;
    end else
    begin
        Result := _Store.Get_Name ;
    end ;
end ;


function TUOS_Managed_Store.Get_Cache : TCOM_Cache64 ;

begin
    if( _Store = nil ) then
    begin
        Result := nil ;
    end else
    begin
        Result := _Store.Get_Cache ;
    end ;
end ;


procedure TUOS_Managed_Store.Set_Cache( Value : TCOM_Cache64 ) ;

begin
    if( _Store <> nil ) then
    begin
        _Store.Set_Cache( Value ) ;
    end ;
end ;


function TUOS_Managed_Store.Contiguous_Store : boolean ;

begin
    if( _Store = nil ) then
    begin
        Result := True ;
    end else
    begin
        Result := _Store.Contiguous_Store ;
    end ;
end ;


procedure TUOS_Managed_Store.Set_Max_Storage( Value : TStore_Address64 ;
    var Res : TUnified_Exception ) ;

var C : int64 ; // Total clusters on store

begin
    if( _Store = nil ) then
    begin
        Res := nil ;
    end else
    begin
        _Store.Set_Max_Storage( Value, Res ) ;
        if( Res <> nil ) then
        begin
            C := _Store.Max_Storage div _Store.Min_Storage ;
            AT.Set_Size( C div 8 ) ;
        end ;
        Set_Last_Error( _Store.Last_Error ) ;
    end ;
end ;


function TUOS_Managed_Store.Extended_Size : TStore_Address64 ;

begin
    if( _Store = nil ) then
    begin
        Result := 0 ;
    end else
    begin
        Result := _Store.Extended_Size ;
        Set_Last_Error( _Store.Last_Error ) ;
    end ;
end ;


procedure TUOS_Managed_Store.Set_Read_Only( Value : boolean ) ;

begin
    if( _Store <> nil ) then
    begin
        _Store.Set_Read_Only( Value ) ;
    end ;
end ;


procedure TUOS_Managed_Store.Set_Write_Only( Value : boolean ) ;

begin
    if( _Store <> nil ) then
    begin
        _Store.Set_Write_Only( Value ) ;
    end ;
end ;


function TUOS_Managed_Store.Allocate( Size : TStore_Address64 ) : TStore_Address64 ;

begin
    Result := AT.Allocate( Size ) ;
    Set_Last_Error( AT.Last_Error ) ;
    if( Last_Error = nil ) then
    begin
        inc( Statistics.Allocations ) ;
        Statistics.Bytes_Allocated := Statistics.Bytes_Allocated + Size ;
    end ;
end ;


function TUOS_Managed_Store.Allocate_At( Offset,
    Size : TStore_Address64 ) : boolean ;

begin
    Result := AT.Allocate_At( Offset, Size ) ;
    Set_Last_Error( AT.Last_Error ) ;
    if( Last_Error = nil ) then
    begin
        inc( Statistics.Allocations ) ;
        Statistics.Bytes_Allocated := Statistics.Bytes_Allocated + Size ;
    end ;
end ;


procedure TUOS_Managed_Store.Deallocate( PTR, Size : TStore_Address64 ) ;

begin
    AT.Deallocate( PTR, Size ) ;
    Set_Last_Error( AT.Last_Error ) ;
    if( Last_Error = nil ) then
    begin
        inc( Statistics.Deallocations ) ;
        Statistics.Bytes_Deallocated := Statistics.Bytes_Deallocated + Size ;
    end ;
end ;


function TUOS_Managed_Store.SpaceAvail : TStore_Address64 ;

begin
    Result := AT.SpaceAvail ;
    Set_Last_Error( AT.Last_Error ) ;
end ;


function TUOS_Managed_Store.XSpaceAvail : TStore_Address64 ;

begin
    Result := SpaceAvail ;
end ;


function TUOS_Managed_Store.MaxSpace : TStore_Address64 ;

begin
    Result := AT.MaxSpace ;
    Set_Last_Error( AT.Last_Error ) ;
end ;

Now let's look at the managed store portion of our methods:
procedure TUOS_Managed_Store.Copy( Source, Destination : TStore_Address64 ;
    Count : integer ) ;

var Buffer : pointer ;
    UEC : TUnified_Exception ;

begin
    Set_Last_Error( nil ) ;
    if( ( Count <= 0 ) or ( Source = Destination ) ) then
    begin
        exit ;
    end ;
    Buffer := allocmem( _Clustersize ) ;
    Count := Count div _Clustersize ; // Number of clusters to copy
    Source := ( Source div Clustersize ) * Clustersize ;
    Destination := ( Destination div Clustersize ) * Clustersize ;
    if( Source < Destination ) then
    begin
        Source := Source + Count * Clustersize ;
        Destination := Destination + Count * Clustersize ;
    end ;
    while( Count > 0 ) do
    begin
        dec( Count ) ;
        _Store.Read_Data( Buffer^, Source, _Clustersize, UEC ) ;
        if( UEC <> nil ) then
        begin
            Set_Last_Error( UEC ) ;
            exit ;
        end ;
        _Store.Write_Data( Buffer^, Destination, _Clustersize, UEC ) ;
        if( UEC <> nil ) then
        begin
            Set_Last_Error( UEC ) ;
            exit ;
        end ;
        if( Source < Destination ) then
        begin
            Source := Source - Clustersize ;
            Destination := Destination - Clustersize ;
        end else
        begin
            Source := Source + Clustersize ;
            Destination := Destination + Clustersize ;
        end ;
    end ;
    freemem( Buffer ) ;
    inc( Statistics.Copies ) ;
    Statistics.Bytes_Copied := Statistics.Bytes_Copied + Count ;
end ;

During a copy operation, we create a local buffer to hold the clusters that we are copying. The operation is simply a matter of reading one cluster, writing it out, and repeating until we are done. First we normalize the source and destination since we only copy entire clusters. There is also code the operates differently depending on whether the source is before or after the destination. The reason for this is that the order we copy the data matters if the ranges (source + size and destination + size) overlap. Let me illustrate with a diagram:

If we copy from range A to range B, the first cluster copied will overwrite the first cluster in range B. But since the first cluster in range B is part of range A, by the time we progress through range A to where range B is, the data will have changed - so, we will have corrupted the data by the time it gets to the destination. For this reason, if the source range starts before the destination, we copy the data from high to low. Otherwise we copy from low to high. If the ranges don't overlap, it doesn't matter in which direction we copy the data, so our logic doesn't change.

procedure TUOS_Managed_Store.Fill( PTR : TStore_Address64 ; Count : integer ;
    Value : byte ) ;

var Buffer : pointer ;
    Original : integer ;

begin
    Set_Last_Error( nil ) ;
    if( ( PTR < Clustersize ) or ( Count < 1 ) ) then
    begin
        exit ;
    end ;
    PTR := ( PTR div Clustersize ) * Clustersize ;
    Count := ( Count div Clustersize ) * Clustersize ;
    Original := Count ;
    Buffer := allocmem( Clustersize ) ;
    fillchar( Buffer^, Clustersize, Value ) ;
    while( Count > 0 ) do
    begin
        Write( PTR, Clustersize, Buffer^ ) ;
        if( Last_Error <> nil ) then
        begin
            exit ;
        end ;
        PTR := PTR + Clustersize ;
        Count := Count - Clustersize ;
    end ;
    freemem( Buffer ) ;
    inc( Statistics.Fills ) ;
    Statistics.Bytes_Filled := Statistics.Bytes_Filled + Original ;
end ;

This method provides a way to fill a given cluster with a value. We don't allow filling the first cluster. Since address 0 indicates no address (like NULL in C++ or nil in Pascal). Instead, the Get_Root and Set_Root methods must be used to access the first cluster on the store.

function TUOS_Managed_Store.Reallocate( PTR, Old,
    New : TStore_Address64 ) : TStore_Address64 ;

begin
    Result := 0 ;
    Set_Last_Error( nil ) ;
    if( ( PTR < Clustersize ) or ( Old < 1 ) or ( New < 1 ) ) then
    begin
        exit ;
    end ;

    PTR := ( PTR div Clustersize ) * Clustersize ;
    Old := ( Old div Clustersize ) * Clustersize ;
    New := ( New div Clustersize ) * Clustersize ;
    Result := PTR ;
    if( Old = New ) then // No change
    begin
        exit ;
    end ;
    if( New < Old ) then // Shrinking
    begin
        AT.Deallocate( PTR + New, Old - New ) ;
        Set_Last_Error( AT.Last_Error ) ;
        inc( Statistics.Reallocations_In_Place ) ;
        exit ;
    end ;

    // Expand...
    if( not AT.Allocate_At( PTR + Old, New - Old ) ) then
    begin
        // Cannot expand in-place, so allocate a new area, 
	// copy old to new, and deallocate old
        Result := AT.Allocate( New ) ;
        if( Result = 0 ) then
        begin
            Result := PTR ;
            Set_Last_Error( AT.Last_Error ) ;
        end else
        begin
            Copy( PTR, Result, Old ) ;
            AT.Deallocate( PTR, Old ) ;
            Set_Last_Error( AT.Last_Error ) ;
            inc( Statistics.Reallocations ) ;
        end ;
    end else
    begin
        inc( Statistics.Reallocations_In_Place ) ;
    end ;
end ;

For reallocation, we first see if we can reallocate in-place. That is, extend the existing allocated space without moving it. If there isn't sufficient room to expand the data in-place, we allocate space elsewhere and copy the existing data to the new location. Again, we don't allow references to cluster 0.
procedure TUOS_Managed_Store.Get_Root( var Buf ) ;

var UEC : TUnified_Exception ;

begin
    _Store.Read_Data( Buf, 0, Clustersize, UEC ) ;
    Set_Last_Error( UEC ) ;
    inc( Statistics.Root_Reads ) ;
end ;


procedure TUOS_Managed_Store.Set_Root( var Buf ) ;

var UEC : TUnified_Exception ;

begin
    _Store.Write_Data( Buf, 0, Clustersize, UEC ) ;
    Set_Last_Error( UEC ) ;
    inc( Statistics.Root_Writes ) ;
end ;

The Get_Root and Set_Root read and write the first cluster of the store. This guarantees that we only access the first cluster when we intend to and not because of a null pointer.

Now we have methods to allow us access to the allocation table. This will only be necessary when we are initializing the file system or repairing it.

function TUOS_Managed_Store.Allocation_Table_Size : longint ;

begin
    Result := AT.Get_Size ;
    Set_Last_Error( AT.Last_Error ) ;
end ;


procedure TUOS_Managed_Store.Get_Allocation_Table_Data( Buff : pointer ;
    _Size : longint ) ;

begin
    move( AT.Get_Data^, Buff^, _Size ) ;
    Set_Last_Error( AT.Last_Error ) ;
end ;


procedure TUOS_Managed_Store.Set_Allocation_Table_Data( Buff : pointer ;
    _Size : longint ) ;

begin
    AT.Set_Data( Buff, _Size ) ;
    Set_Last_Error( AT.Last_Error ) ;
end ;


procedure TUOS_Managed_Store.Set_Allocation_Table_Offset( Value : TStore_Address64 ) ;

begin
    AT.Set_Offset( Value ) ;
    Set_Last_Error( AT.Last_Error ) ;
end ;


function TUOS_Managed_Store.Get_Allocation_Table_Offset : TStore_Address64 ;

begin
    Result := AT.Get_Offset ;
    Set_Last_Error( AT.Last_Error ) ;
end ;


procedure TUOS_Managed_Store.Flush_Allocation_Table ;

begin
    AT.Flush ;
    Set_Last_Error( AT.Last_Error ) ;
end ;

As we have discussed, the physical minimum storage size of the store can be smaller than the cluster size we want to use while allocating space on the store. The Set_Min_Storage method allows us to set the cluster size. Note that this must be done before the store is used and cannot change after it has been used. Consider the mayhem that would result if we starting allocating data in 1024-byte clusters and then changed the cluster size to 768. That would mean that each bit in the allocation table would map to a different place on the store than it used to, which means that new allocations would likely include data that had already been allocated, and our allocation cluster chains would map less data (if the default store allocatino size is used). Data would be overwritten, lost, and the file structure itself would be corrupted.

procedure TUOS_Managed_Store.Set_Min_Storage( _Size : longint ) ;

begin
    Set_Last_Error( nil ) ;
    _Clustersize := _Size ;
    if( _Store <> nil ) then
    begin
        if( _Clustersize < _Store.Min_Storage ) then
        begin
            _Clustersize := _Store.Min_Storage ;
        end ;
    end ;
end ;

And finally, the store getter and setter methods.
function TUOS_Managed_Store.Get_Store : TCOM_Store64 ;

begin
    Result := _Store ;
end ;


procedure TUOS_Managed_Store.Set_Store( Value : TCOM_Store64 ) ;

begin
    Set_Last_Error( nil ) ;
    if( Value <> nil ) then
    begin
        Value.Attach ;
        if( _Clustersize < Value.Min_Storage ) then
        begin
            _Clustersize := Value.Min_Storage ;
        end ;
        AT.Set_Store( Value ) ;
        AT.Set_Resolution( _Clustersize ) ;
        Set_Last_Error( AT.Last_Error ) ;
    end ;
    if( _Store <> nil ) then
    begin
        _Store.Detach ;
    end ;
    _Store := Value ;
end ;

In the next article, we'll take a look at the allocation table class that this class uses.