Fun with Stores: Partitions

In the old days of MSDOS, and early versions of Windows, some disks were larger than the operating system file systems could handle. This was one of those rare instances where the hardware capabilities jumped ahead of the software's ability to deal with it. Granted, this turn of events didn't last too long, but while it did, various means of allowing the operating system to access these disks were invented. One of these means was "disk partitioning". To partition a disk meant to allocate up to four contiguous segments of the disk and treat each of them as if they were a separate disk drive. Besides allowing the older operating systems to use all of the disk's capacity (albeit as multiple disk drives), it also allows the same disk drive to contain multiple file systems. For instance, a partitioned disk could contain a FAT16 partition for MSDOS, a FAT32 partition for Windows, a partition for OS/2, and maybe even one for Linux. But, usually, the partitions were used as multiple logical disks for the same operating system. Pretending to have a logical disk that is part of a physical disk is a type of hardware abstraction which should sound familiar to you after the previous articles. Now what does this remind me of? Oh yes, a store! A store is an abstracted storage device which may or may not have a direct relation to a physical device. For instance, a RAM disk is a store that uses a chunk of RAM. A partition store is simply a store that maps its storage onto a contiguous subset of another store. And that is how we will handle partitions in UOS.

There are many schemes that have been used for partitioning disks over the years. The most common is the MBR (Master Boot Record) approach. It was limited to four partitions of up to 4 billion sectors. For 512-byte sectors, that means MBR can support disks up to about 2.2 Terabytes in size. Over the years, several extensions to the MBR format allowed additional partitions and/or larger disks. Of course, each of these variations was different from the others and none caught on, in general. In 2005, Intel released the UEFI specification, which has gained traction in the marketplace, and defines the GUID partition scheme. It allows up to 128 partitions and much larger disks (larger than anything available today by several orders of magnitude). UOS will support both schemes although, obviously, only one or the other on a given disk.

We won't bother going over the specific code for handling these partitioning schemes. If you want to learn more about them, you can start with the Wikipedia article. Init will support the following partitioning actions:

Adding a partition. If the disk has no partitions already, the user is queried for the type of partitioning scheme to use (defaulting to GUID). If the user chooses GUID, he is asked how many partitions to allow (1-128). MBR supports exactly four partitions, although not all of them must be used. If the disk already has been initialized with a paritioning scheme, that is the scheme that will be used. The user is also asked for the size of the partition. The new partition will be allocated from any deleted partitions of the same size, if any. Otherwise, it is allocated at the end of the partition list (in unused space on the disk).
List partitions. This lists the partitions already on the disk.
Delete a partition. An existing partition can be deleted (which sets it to "inactive"). The partition can be specified as an index (0 being the first partition), as a partition specification ("a" being the first partition), or as a complete device specification, such as "diska1a". The partition can be specified as "ALL" to delete all the partitions. This will also delete the partitioning scheme itself from the disk so that a new one can be defined (or none at all).

Here's the disk partition input loop:

function Disk_Partition_Device( Store : TCOM_Store64 ; St, S : string ) : boolean ;

var Dummy : integer ;
    Prompt : boolean ;
    S1 : string ;

begin
    Result := False ;
    Prompt := S = '' ;
    while( True ) do
    begin
        if( Prompt ) then
        begin
            Output( 'Disk partition ' + St + '> ' ) ;
            S := Input( 'DISKA0' ) ;
        end ;
        if( S = #3 ) then
        begin
            Result := True ;
            exit ;
        end ;
        if( ( S = ESC ) or ( S = #26 ) ) then
        begin
            exit ;
        end ;
        S := Edit( S, 4 or 8 or 32 or 128 ) ;
        if( S = '' ) then
        begin
            continue ;
        end ;
        Dummy := pos( ' ', S + ' ' ) ;
        S1 := copy( S, Dummy + 1, length( S ) ) ;
        S := copy( S, 1, Dummy - 1 ) ;

        if( ( S = '?' ) or Match( 'HELP', S, 1 ) ) then
        begin
            Output_Line( 'ADD - Add new partition' ) ;
            Output_Line( 'DELETE - Delete partition' ) ;
            Output_Line( 'HELP - Show this text' ) ;
            Output_Line( 'LIST - List partitions' ) ;
            Output_Line( '' ) ;
        end else
        if( Match( 'ADD', S, 1 ) ) then
        begin
            if( Disk_Partition_Device_Add( Store, St ) ) then
            begin
                exit ;
            end ;
        end else
        if( Match( 'DELETE', S, 1 ) ) then
        begin
            if( Disk_Partition_Device_Delete( Store, St, S1 ) ) then
            begin
                exit ;
            end ;
        end else
        if( Match( 'LIST', S, 1 ) ) then
        begin
            if( Disk_Partition_Device_List( Store, St, S1 ) ) then
            begin
                exit ;
            end ;
        end else
        if( S <> '' ) then
        begin
            Output_Line( 'Invalid subcommand' ) ;
        end ;
        if( not Prompt ) then
        begin
            exit ;
        end ;
    end ; // while( True )
end ; // Disk_Partition_Device

Now that support for partitions has been added, we must update the rest of the Init code to recognize them. Here is the updated Disk_List code.

function Disk_List( Command : string ) : boolean ;

var Count, Index, Loop : integer ;
    Info : TDevice_Info ;
    S : string ;
    Store, PStore : TCOM_Store64 ;

begin
    Result := False ;
    Index := 0 ;
    Info := HAL.Device( Index ) ;
    while( Info.Device_Type <> DT_Non_Existant ) do
    begin
        if( Info.Device_Type = DT_Store ) then
        begin
            Store := HAL.Store( Index ) ;
            if( Store <> nil ) then
            begin
                S := 'DISK' + chr( 65 + Info.Controller ) +
                    inttostr( Info.Device_Unit ) + '     ' ;
                Output( S ) ;
                S := inttostr( Store.Max_Storage ) ;
                while( length( S ) < 12 ) do
                begin
                    S := ' ' + S ;
                end ;
                Output_Line( S + '  ' + Abbreviate_Size( Store.Max_Storage ) ) ;

                Count := Partition_Count( Store ) ;
                for Loop := 0 to Count - 1 do
                begin
                    S := '  DISK' + chr( 65 + Info.Controller ) +
                        inttostr( Info.Device_Unit ) + Partition_Spec( Loop ) +
                        '    ' ;
                    Output( S ) ;
                    PStore := Get_Partition( Store, Loop ) ;
                    if( PStore <> nil ) then
                    begin
                        S := inttostr( PStore.Max_Storage ) ;
                        while( length( S ) < 12 ) do
                        begin
                            S := ' ' + S ;
                        end ;
                        Output_Line( S + '  ' + Abbreviate_Size( PStore.Max_Storage ) ) ;
                    end else
                    begin
                        Output_Line( 'unused' ) ;
                    end ;
                end ; // for Loop := 0 to Count - 1
            end ; // if( Store <> nil )
        end ; // if( Info.Device_Type = DT_Store )
        inc( Index ) ;
        Info := HAL.Device( Index ) ;
    end ; // while
end ; // Disk_List

We won't bother covering the Get_Partition code here since it includes a bunch of partition-handling code. But here is the class definition and code for the TPartition_Store.

                         // TPartition_Store class...

type TPartition_Store = class( TCOM_Store64 )
                            public // Instance data...
                                Store : TCOM_Store64 ;
                                Start : int64 ;
                                Max : int64 ;
                                Force_Read_Only : boolean ;

                                _Bytes_Read : int64 ;
                                _Bytes_Written : int64 ;
                                _Reads : int64 ;
                                _Writes : int64 ;
                                _Error_Count : int64 ;

                            private // Instance data...
                                _Cache : TCOM_Cache64 ;
                                _Read_Only : boolean ;
                                _Write_Only : boolean ;

                            public // Overrides...
                                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 ;

                                function Get_Bytes_Read : longint ;
                                    override ;
                                function Get_Bytes_Written : longint ;
                                    override ;
                                function Get_Reads : longint ;
                                    override ;
                                function Get_Writes : longint ;
                                    override ;
                                function Get_Error_Count : longint ;
                                    override ;
                                procedure Set_Bytes_Read( Value : longint ) ;
                                    override ;
                                procedure Set_Bytes_Written( Value : longint ) ;
                                    override ;
                                procedure Set_Reads( Value : longint ) ;
                                    override ;
                                procedure Set_Writes( Value : longint ) ;
                                    override ;
                                procedure Set_Error_Count( Value : longint ) ;
                                    override ;
                                procedure Set_Read_Only( Value : boolean ) ;
                                    override ;
                                procedure Set_Write_Only( Value : boolean ) ;
                                    override ;
                        end ; // TPartition_Store

// Overrides...

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

begin
    if( ( Address < 0 ) or ( Address > Max ) ) then
    begin
        Result := Store.Read_Data( Data, -1, _Size, UEC ) ;
        exit ;
    end ;
    Address := Address + Start ;
    Result := Store.Read_Data( Data, Address, _Size, UEC ) ;
    if( UEC <> nil ) then
    begin
        _Bytes_Read := _Bytes_Read + _Size ;
        inc( _Reads ) ;
    end ;
end ;


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

begin
    if( ( Address < 0 ) or ( Address > Max ) ) then
    begin
        Result := Store.Write_Data( Data, -1, _Size, UEC ) ;
        exit ;
    end ;
    Address := Address + Start ;
    Result := Store.Write_Data( Data, Address, _Size, UEC ) ;
    if( UEC <> nil ) then
    begin
        _Bytes_Written := _Bytes_Written + _Size ;
        inc( _Writes ) ;
    end ;
end ;


function TPartition_Store.Max_Storage : TStore_Size64 ;

begin
    Result := Max - Start + 1 ;
end ;


function TPartition_Store.Min_Storage : TStore_Address64 ;

begin
    Result := Store.Min_Storage ;
end ;


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

begin
    Result := Max_Storage ;
end ;


function TPartition_Store.Get_Read_Only : boolean ;

begin
    Result := _Read_Only
end ;


function TPartition_Store.Get_Write_Only : boolean ;

begin
    Result := _Write_Only ;
end ;


procedure TPartition_Store.Format ;

begin
end ;


function TPartition_Store.Get_Name : PChar ;

begin
    Result := nil ;
end ;


function TPartition_Store.Get_Cache : TCOM_Cache64 ;

begin
    Result := _Cache ;
end ;


procedure TPartition_Store.Set_Cache( Value : TCOM_Cache64 ) ;

begin
    if( Value <> nil ) then
    begin
        Value.Attach ;
    end ;
    if( _Cache <> nil ) then
    begin
        _Cache.Detach ;
    end ;
    _Cache := Value ;
end ;


function TPartition_Store.Contiguous_Store : boolean ;

begin
    Result := True ;
end ;


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

begin
end ;


function TPartition_Store.Extended_Size : TStore_Address64 ;

begin
    Result := Max_Storage ;
end ;


function TPartition_Store.Get_Bytes_Read : longint ;

begin
    Result := _Bytes_Read ;
end ;


function TPartition_Store.Get_Bytes_Written : longint ;

begin
    Result := _Bytes_Written ;
end ;


function TPartition_Store.Get_Reads : longint ;

begin
    Result := _Reads ;
end ;


function TPartition_Store.Get_Writes : longint ;

begin
    Result := _Writes ;
end ;


function TPartition_Store.Get_Error_Count : longint ;

begin
    Result := _Error_Count ;
end ;


procedure TPartition_Store.Set_Bytes_Read( Value : longint ) ;

begin
    _Bytes_Read := Value ;
end ;


procedure TPartition_Store.Set_Bytes_Written( Value : longint ) ;

begin
    _Bytes_Written := Value ;
end ;


procedure TPartition_Store.Set_Reads( Value : longint ) ;

begin
    _Reads := Value ;
end ;


procedure TPartition_Store.Set_Writes( Value : longint ) ;

begin
    _Writes := Value ;
end ;


procedure TPartition_Store.Set_Error_Count( Value : longint ) ;

begin
    _Error_Count := Value ;;
end ;


procedure TPartition_Store.Set_Read_Only( Value : boolean ) ;

begin
    if( not Force_Read_Only ) then
    begin
        _Read_Only := Value ;
    end ;
end ;


procedure TPartition_Store.Set_Write_Only( Value : boolean ) ;

begin
    _Write_Only := Value ;
end ;

As you can see, this class simply wraps another store, mapping reads and writes onto the portion of the store which contains the partition in question. Min_Storage is the same as the physical store and Max_Storage matches the size of the partition. Individual metrics are kept for the partition, and the store can be independently set to read-only or write (although if the physical store is read-only), the partition cannot be made writable. Some methods do nothing, such as Format and Set_Max_Storage, which do not apply in this situation. Obviously, if we have multiple partitions on a physical store, there will be multiple references to the store. But since the physical store doesn't go away, we don't bother with attaching and detaching to it in the partition store.

You may wonder why we have a separate Get_Partition function. I mean, why not include that in the HAL? The main reason is philosophical - the HAL deals only with the actual hardware, it doesn't deal with the data on that hardware (for the same reason, the HAL doesn't contain any keyboard processing code for terminals). Therefore, the HAL knows nothing about the data structures on the store that apply to partitioning, booting, file systems, or anything else. The second reason is practical. Adding partition manipulation code to the HAL increases its size, and what if we decide to support a third or fourth partitioning scheme? We want to keep the HAL as small as possible and layer the other functionality on top of it in UOS and Init.

So, although the HAL handles the stores for the physical devices, we must handle the logical stores (partitions) ourselves. Once a store is created, we want to keep it around for the next time it is referenced (much like the HAL does for physical stores), but we don't want to bother creating stores for every partition until they are requested. We also don't want to ever free one of these instances after requesting it from Get_Partition or else Init will crash. So, the Get_Partition code keeps a list of the stores (including the physical store and the partition index) and creates the store if it isn't in the list. Then it returns the store from that list. This code is called in the same routines as the partition-handling, so we won't cover that here, but when we release the source code (after the next article is done), you can look at the code if you wish. Here is the code which manages our list of partition stores:

var PStores : TList = nil ;

type PStore_Info = class
                       public // API...
                           Store : TCOM_Store64 ;
                           Index : integer ;
                           PStore : TCOM_Store64
                   end ;

procedure Add_PStore( PStore, Store : TCOM_Store64 ; Index : integer ) ;

var Info : PStore_Info ;

begin
    if( PStores = nil ) then
    begin
        PStores := TList.Create ;
    end ;
    Info := PStore_Info.Create ;
    Info.Store := Store ;
    Info.Index := Index ;
    Info.PStore := PStore ;
    PStores.Add( Info ) ;
end ;


function Get_PStore( Store : TCOM_Store64 ; Index : integer ) : TCOM_Store64 ;

var Info : PStore_Info ;
    Loop : integer ;

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

    for Loop := 0 to PStores.Count - 1 do
    begin
        Info := PStore_Info( PStores[ Loop ] ) ;
        if( ( Info.Store = Store ) and (Info.Index = Index ) ) then
        begin
            Result := Info.PStore ;
            exit ;
        end ;
    end ;
end ;


procedure Remove_PStores( Store : TCOM_Store64 ) ;

var Info : PStore_Info ;
    Loop : integer ;

begin
    if( PStores = nil ) then
    begin
        exit ;
    end ;
    for Loop := PStores.Count - 1 downto 0 do
    begin
        Info := PStore_Info( PStores[ Loop ] ) ;
        if( Info.Store = Store ) then
        begin
            Info.Free ;
            PStores.Delete( Loop ) ;
        end ;
    end ;
end ;

function Create_Partition_Store( Store : TCOM_Store64 ; Start, Count : int64 ) : TCOM_Store64 ;

begin
    Result := TPartition_Store.Create ;
    TPartition_Store( Result ).Store := Store ;
    TPartition_Store( Result ).Start := Start * Store.Min_Storage ;
    TPartition_Store( Result ).Max := ( Start + Count ) * Store.Min_Storage - 1 ;
end ;

The way this works is that Get_PStore is called. If no partition store has been created yet, it returns nil. In that case, Create_Partition_Store is called and the resulting Partition store is passed to Add_PStore. In the case where all partitions are deleted from a store, Remove_PStores is called.

Partition_Count returns the count of partitions that exist on a store (returning 0 if the store isn't set up with any paritition scheme).

function Partition_Count( Store : TCOM_Store64 ) : integer ;

var Info : TPartition_Info ;

begin
    Info := Partition_Info( Store ) ;
    Result := Info.Partition_Count ;
end ;

This function calls the Partition_Info function (which we won't cover) which returns a stucture that is defined as follows, and then returns the count of partitions.

// Partition types...
const PT_Unknown = 0 ;
  PT_MBR = 1 ;
  PT_GUID = 2 ;

type TPartition_Info = record
                           Partition_Type : integer ; // See PT_*
                           Free_Partitions : integer ; // Number of unused partitions
                           Partition_Count : integer ; // Number of used partitions
                           Max_Partition_Size : int64 ; // Size of the largest contiguous unused space on store
                           GPT_Header : TGPT_Header ; // GUID Header (only valid if Partition_Type = PT_GUID)
                           Inactive_Partitions : integer ; // Number of inactive partitions
                       end ;

Here is the code for Partition_Spec:

function Partition_Spec( P : integer ) : string ;

begin
    Result := '' ;
    if( P > 25 ) then
    begin
        Result := copy( 'abcdefghijklmnopqrstuvwxyz', ( P div 26 ) + 1, 1 ) ;
    end ;
    Result := Result + copy( 'abcdefghijklmnopqrstuvwxyz', ( P mod 26 ) + 1, 1 ) ;
end ;

It converts a partition index to a textual partition specification.

The only thing left for us is to handle partitions in our Parse_Device function. This will allow us to initialize a file system on a partition. Here is the updated portion of the function:

Result := HAL.Store( Index ) ;
if( Partition >= 0 ) then // Partition specified
begin
    PInfo := Partition_Info( Result ) ;
    if( Partition < PInfo.Partition_Count ) then
    begin
        Result := Get_Partition( Result, Partition ) ;
    end else
    begin
        Result := nil ;
        Output_Line( 'Device not found' ) ;
    end ;
end ;
exit ;

This replaces the block of code that was previously just the following:

Result := HAL.Store( Index ) ;
exit ;

In the next article, we will discuss more things we can do with stores.