Fun with Stores: RAID

RAID stands for Redundant Array of Independent Disks. RAID is a stragegy of using multiple disks as a single logical volume for purposes of reliability and/or performance. There are seven "levels" of RAID, each of which provides a unique configuration of disks in a "RAID set". Frankly, I find the terminology of "levels" to be misleading - as if a higher "level" provides advantages over a lower level. Instead, the levels simply describe different data storage schemes. For instance, RAID 0 combines disks in the set into one large disk that has the capacity of the sum of the members of the set. RAID 1 is called "mirroring" and saves identical copies of disk data on each member of the set. Other RAID schemes split the data across multiple disks, often including parity for error correction. We won't go over every scheme in detail here. You can read about them in this wikipedia article.

RAID can be implemented via hardware or software, although hardware is obviously a higher performance option. Some RAID schemes are prohibitively expensive to implement in software. Consider, for instance, RAID 2, which splits individual bits across the disks. This is done so that the loss of part of one disk (or an entire disk) results in no loss of data, since the lost bits can be reconstructed by way of parity stored on another disk. But imagine the work of a store that had to split each byte into individual bits across 9 (or more) separate physical stores. There are other considerations here as well. For instance, if the disks have a sector size of 512, and the bits are spread across 8 disks, then each sector in the RAID set is 4,096 bytes because the disks have to be accessed by sector. Each byte written to the RAID set results in only one bit written to each physical disk. 512 bytes times 8 disks = 4,096 bytes. So, we will leave most types of RAID to the hardware (and many consumer motherboards support hardware RAID). But on systems without hardware RAID support, it would be nice for UOS to provide some RAID support in software. Because of the aforementioned performance issues, we will only concern ourselves with RAID 0 and RAID 1.

One problem with RAID 0 is that there is that the loss of one disk is equivalent to losing a large chunk of a physical disk. If the allocation table for the logical disk happens to reside on that disk, the entire set becomes unusable. UOS provides a more robust method for logically combining multiple disks into a larger logical store. This is done via something we call a public pool which we'll discuss in article. Which leaves us with RAID 1, or "mirroring". Whether implemented in software or hardware, mirroring provides two advantages: 1) because the data exists on multiple disks, the loss of one disk prevents the loss of data - it can be retrived from one of the other mirror disks in the set. Another advantage is that read operations from the set will be faster than read operations from any one of the disks. However, write operations will be slower. To understand these performance characteristics, we need to understand how hard disks operate.

Hard disks consist of one or more platters that rotate at high speed (in excess of 5,000 rpm). The rings represent the tracks that exist on the surface of the platter (we only show the outer two tracks). Sectors overlay the tracks like slices of a pie. We only show a couple of the slices here. The intersection of this slice and a track indicates a sector. The black area represents a single sector on the outer track. As the disk rotates, the sector will move past the read/write head at which point the head can read or write the sector contents. The time it takes for the sector to rotate into position under the read/write head is called "rotational latency". But the read/write arm needs to move in and out so that the r/w head (at the end of the arm) is positioned over the correct track when the sector rotates into place. This head movement is called "seeking" and the time to move the head into place is called the "seek time". No matter how fast the disk spins and the head moves, even the fastest disks can take many milliseconds to respond with the requested data (or finish the write) due to the seek time and rotational latency. Since all disks in a mirrored set do the same read and write operations in parallel, the heads of all disks will always be in the same position (over the same track). However, the location of the desired sector will differ between the various disks. Separate disks cannot be synchronized such that the sectors are all in the same position relative to the r/w head. Even on identical disk models, due to very small discrepencies in motor speed, bearing wear (which determines how long it takes a disk spin down when turned off and how long to spin up when turned on), differences in manufacturing, and other factors, the time it takes for the desired sector to move into position will be the latency of one disk divided by the total number of disks in the mirror set. So, with two disks, the same sector will be, on average, on exactly opposite sides. That is, if the sector is at the top oof our diagram on one disk, then it will be at the bottom of the diagram on the other. Thus, the sector will only have to travel no more than one half a rotation to be available on one of the other disks. With additional disks in the set, the average latency will be even less. So, essentially, a read operation is issued to all disks in the set, and the first one to respond completes the read operation. The remaining reads are ignored. So, that gives us data redundency and faster reads. However, there is a down-side. Because we have to keep the data synchronized between all the disks in the set, the completion of a write operation is going to be limited to the write speed of the slowest disk in the set, and we have to wait for the sector to move into place for all the disks. This is going to be, on average, slower than waiting on a single disk. In fact, this will average to twice as slow, regardless of the number of disks in the set. Well, you win some and you lose some. These are just the trade-offs one must consider when using RAID. Obviously, for a disk that is read a lot but written less frequently, a mirrored disk set will be a performance improvement over non-mirrored disks. In fact, except for RAID level 0, all RAID levels have slower write characteristics than non-RAID disks, and most have slower read performance as well. We've mentioned before that decisions in operating systems are always trade-offs. In this case, we are trading performance for the sake of data integrity through redundancy. Of course, with caching, much of the performance degredation can be mitigated.

So, we will provide the user with the option of mirroring. If they want other types of RAID, they will have to get hardware that supports it. As we described above, the implementation of mirroring is simple. However, in the case of Init, we do all operations synchronously, so we see no performance benefit - just that of data redundancy. We'll look at asychronous store access when we get into the File Processor. So then, how do we implement RAID? With stores, of course! Hardware-based RAID will make the RAID set look like a single physical device to the BIOS (and HAL), so we need make no provision for it. From the HAL's perspective, its just another disk. But if we are mirroring stores, we will need to write a store class that can make the mirror set look like a single store.

At first, I considered using the SNIA standard for RAID data structures, but I decided against it. Without going into the gory details, there were several disadvantages to the SNIA approach. In the process of looking into it, I was thinking of using a separate UOS mirrored set implementation, but still allow the use of SNIA structures on pre-existing RAID 1 disks. However, that would require a lot of extra complexity for something that would probably never be used. Some of the major restrictions with SNIA include:

SNIA makes certain assumptions, such as that the members of RAID sets are statically configured, whereas UOS allows the mirrored disks to be dynamically configured.
SNIA mandates a minimum of 32 Mb of overhead on each disk. UOS requires only a single cluster, which means it can be used on smaller disks.
SNIA doesn't allow mirrored partitions - only mirrored disks. UOS allows any store to be mirrored, even if it is a partition.

The approach we are taking is to write a header of mirror information at the end of the store. We could have written it at the start of the store, but that could interfere with the boot block on bootable stores. As it turns out, the SNIA standard also writes the RAID information at the end of the device, but we are more concerned with keeping the boot block understandable by BIOS and other software. The Mirror header is written in the last physical cluster of the store. However, on stores with small cluster sizes, it is possible that the header will be larger a single cluster. Therefore, we write the header starting at the last cluster that we can start at while still having enough room for the header. So, if our header is 256 bytes, it will take up the last two clusters on a store that has a minimum cluster size of 128. On stores with minimum cluster sizes larger than the mirror header, the part of the cluster after the end of the header is unused and undefined. Here is the mirror header structure:

type TGUID = array[ 0..1 ] of int64 ;

type TMirror_Header = packed record // Mirror header
                          Signature : int64 ; // 7F FF 8C 01 00 8C FF FF
                          Set_Name : array[ 0..63 ] of char ;
                          Set_GUID : TGUID ;
                          Flags : cardinal ; // and 1 = applies to partition
                          Sequence : int64 ;
                          Timestamp : int64 ;
                          Reserved : array[ 0..147 ] of byte ;
                      end ; // TMirror_Header

The signature is an 8-byte "magic" value that helps to ensure that this is a mirror header structure. The Set Name is a name given by the user when the mirror set was created. Set_GUID is a 128-byte value that uniquely identifies the mirror set. Flags contains further information, which we will discuss later. Sequence is a numeric value that is incremented each time the set is shut down. And Timestamp is the last time that the set was shut down. Timestamp and Sequence are used to keep the members of the set synchronized. We will talk about synchronization in a bit.

Here is the class for the Mirrored Store:

type TMirror_Store = class( TCOM_Store64 )
                         public // Constructors and destructors...
                             constructor Create ;
                             destructor Destroy ; override ;

                         public // Instance data...
                             Force_Read_Only : boolean ;
                             Written : boolean ; // True if store has been updated
                             Synchronous : boolean ;

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

                         private // Instance data...
                             Dirty : int64 ; // Dirty flags
                             Stores : TList ; // List of TCOM_Store64
                             _Cache : TCOM_Cache64 ;
                             _Read_Only : boolean ;
                             _Write_Only : boolean ;
                             Reconcile_Store : TCOM_Store64 ;
                             Reconcile_Offset : int64 ;
                             _Set_Name : string ;

                         private // Utility routines...
                             function Get_Buffer( var Size : integer ) : PChar ;

                         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 ;

                         public // API...
                             procedure Add_Store( S : TCOM_Store64 ) ;
                                 virtual ;
                             procedure Remove_Store( S : TCOM_Store64 ) ;
                                 virtual ;
                             procedure Close_All( Force : boolean ) ;
                                 virtual ;
                             procedure Recalculate ; virtual ;
                             procedure Reconcile ; virtual ;
                             procedure Set_Mirror_Set_Name( Value : string ) ;
                             function Get_Mirror_Set_Name : string ;
                             function Count : integer ;
                             function GUID : TGUID ;
                             function Timestamp : int64 ;
                             function Sequence : int64 ;

                         public // Properties...
                             property Mirror_Set_Name : string
                                 read Get_Mirror_Set_Name
                                 write Set_Mirror_Set_Name ;
                     end ; // TMirror_Store

This is just a descendent of the same TCOM_Store64 store that you are used to, with a few additional routines to support the mirror sets. The overrides are very simple - most of the work is not in the reading and writing of data to the mirror set, but in managing the list of stores. The Stores list contains pointers to each of the members of our mirror set.

First, let's take a look at the overriden methods:

// TMirror_Store methods...

// Constructors and destructors...

constructor TMirror_Store.Create ;

begin
    inherited Create ;

    Stores := TList.Create ;
end ;


destructor TMirror_Store.Destroy ;

begin
    Stores.Free ;
    Stores := nil ;

    inherited Destroy ;
end ;


// Utility routines...

function TMirror_Store.Get_Buffer( var Size : integer ) : PChar ;

begin
    Size := Round_Up( sizeof( TMirror_Header ), TCOM_Store64( Stores[ 0 ] ).Min_Storage ) ;
    Result := allocmem( Size ) ;
end ;

This internal method allocates a buffer of the appropriate size and returns it (and the size). The reason for this is to make sure we allocate the number of bytes equal to the number of clusters required to hold a mirror set header.

// Overrides...

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

var Store : TCOM_Store64 ;

begin
    if( Stores.Count = 0 ) then
    begin
        Result := 0 ;
        UEC := Create_Exception( Mirror_Error_No_Stores_In_Set, nil ) ;
        exit ;
    end ;
    Store := TCOM_Store64( Stores[ 0 ] ) ;
    Store.Read_Data( Data, Address, _Size, UEC ) ;
end ;


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

var Loop : integer ;
    Store : TCOM_Store64 ;
    E : TUnified_Exception ;

begin
    if( Stores.Count = 0 ) then
    begin
        Result := 0 ;
        UEC := Create_Exception( Mirror_Error_No_Stores_In_Set, nil ) ;
        exit ;
    end ;
    Written := True ;
    for Loop := 0 to Stores.Count - 1 do
    begin
        Store := TCOM_Store64( Stores[ Loop ] ) ;
        Store.Write_Data( Data, Address, _Size, E ) ;
        if( E <> nil ) then
        begin
            UEC := E ;
        end ;
    end ;
end ;


function TMirror_Store.Max_Storage : TStore_Size64 ;

var Store : TCOM_Store64 ;

begin
    if( Stores.Count = 0 ) then
    begin
        Result := 0 ;
        exit ;
    end ;
    Store := TCOM_Store64( Stores[ 0 ] ) ;
    Result := Store.Max_Storage - Round_Up( sizeof( TMirror_Header ), Store.Min_Storage ) ;
end ;


function TMirror_Store.Min_Storage : TStore_Address64 ;

var Store : TCOM_Store64 ;

begin
    if( Stores.Count = 0 ) then
    begin
        Result := 0 ;
        exit ;
    end ;
    Store := TCOM_Store64( Stores[ 0 ] ) ;
    Result := Store.Min_Storage ;
end ;


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

begin
    Result := Max_Storage ;
end ;


function TMirror_Store.Get_Read_Only : boolean ;

begin
    Result := _Read_Only
end ;


function TMirror_Store.Get_Write_Only : boolean ;

begin
    Result := _Write_Only ;
end ;


procedure TMirror_Store.Format ;

begin
end ;


function TMirror_Store.Get_Name : PChar ;

begin
    Result := nil ;
end ;


function TMirror_Store.Get_Cache : TCOM_Cache64 ;

begin
    Result := _Cache ;
end ;


procedure TMirror_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 TMirror_Store.Contiguous_Store : boolean ;

begin
    Result := True ;
end ;


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

begin
end ;


function TMirror_Store.Extended_Size : TStore_Address64 ;

begin
    Result := Max_Storage ;
end ;


function TMirror_Store.Get_Bytes_Read : longint ;

begin
    Result := _Bytes_Read ;
end ;


function TMirror_Store.Get_Bytes_Written : longint ;

begin
    Result := _Bytes_Written ;
end ;


function TMirror_Store.Get_Reads : longint ;

begin
    Result := _Reads ;
end ;


function TMirror_Store.Get_Writes : longint ;

begin
    Result := _Writes ;
end ;


function TMirror_Store.Get_Error_Count : longint ;

begin
    Result := _Error_Count ;
end ;


procedure TMirror_Store.Set_Bytes_Read( Value : longint ) ;

begin
    _Bytes_Read := Value ;
end ;


procedure TMirror_Store.Set_Bytes_Written( Value : longint ) ;

begin
    _Bytes_Written := Value ;
end ;


procedure TMirror_Store.Set_Reads( Value : longint ) ;

begin
    _Reads := Value ;
end ;


procedure TMirror_Store.Set_Writes( Value : longint ) ;

begin
    _Writes := Value ;
end ;


procedure TMirror_Store.Set_Error_Count( Value : longint ) ;

begin
    _Error_Count := Value ;
end ;


procedure TMirror_Store.Set_Read_Only( Value : boolean ) ;

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


procedure TMirror_Store.Set_Write_Only( Value : boolean ) ;

begin
    _Write_Only := Value ;
end ;

The performance advantages to mirror sets comes as a result of being able to asynchronously issue reads and then respond to the first store that responds. However, in Init we don't bother. That is, we do things synchronously (ie we wait for each I/O operation to finish before we continue). When we look at the UOS, proper, we will get into the asynchronous I/O. The Sychronous instance data determines how the mirror set operates. Why not do asynchronous operations in Init? Well, we could, but the purpose of Init is to have things set up before we start UOS. If we do the operations asynchronously, the user could start UOS before the mirror set was finished synchronizing. In this case, we simply read from the first store in the set, and loop through all the stores when writing.

GUIDs
You may notice the use of TGUID, which is a structure that is simply two 64-bit integer values - in essence, a single 128-bit integer value. The term means "Globally Unique IDentifier" and is used to automatically assign a unique value to something. The reason GUIDs are used is as a means of uniquely marking something such that it will not be confused with something else. In theory, by assigning a random 128-bit value, we have very little chance of assigning the same GUID to an object as we (or someone else) assigns to some other object. The following shows the code used to generate a GUID.

procedure Generate_GUID( var GUID : TGUID ) ;

var RNG : TRNG64 ;

begin
    RNG.Randomize ;
    GUID[ 0 ] := RNG.Generate ;
    RNG.Randomize ;
    GUID[ 1 ] := RNG.Generate ;
    if( GUID[ 0 ] = GUID[ 1 ] ) then // Randomized to same seed
    begin
        GUID[ 1 ] := RNG.Generate ;
    end ;
end ;

Random Numbers
Random numbers are important in computing, serving in applications as different as games, simulations, and cryptography. But consider the difficulting in constructing a truly random value by means of hardware which is designed to be deterministic. We want computers to be reliable and perform the same task over and over exactly the same way every time. Imagine how useless they would be if the programs you wrote acted in a random fashion. Would you be happy with an online store that charged you random amounts? So, how does one generate a random value with a deterministic tool?

Before we can answer that question, we need to address just what "random" means. Consider the way a single raindrop splatters on the sidewalk. The pattern, though similar to other splatters from other raindrops, will still be unique if viewed closely enough. This is due to numerous causes - from small imperfections in the sidewalk's surface, the amount (and type) of substances on the sidewalk, the temperature of the water droplet and the sidewalk, the velocity and size of the drop, air movement, and even small pertubations from local and distant gravitational sources - just to mention a few of the variables. The splatter appears random to us, but if we knew all the variables and had a sufficiently powerful computer, we could theoretically predict the exact shape of the splatter. However, since we don't currently have that kind of capability, the splatter is, for all intents and purposes, random to us. Its apparent randomness is what is important. Likewise, we can use deterministic hardware and software to generate apparently random nmbers. And these will be sufficient for our needs. We call these psuedo-random numbers. For a technical discussion of generating psuedo-random numbers, I recommend the series of books by Donald Knuth entitled "The Art of Computer Programming" (volume 2, "Seminumerical Algorithms", addresses psudeo-random numbers). Really, the whole series should be on the shelf of (and read by) every serious software developer. I won't repeat that content here, but suffice it to say that some random number generators are not very good (that is, they generate predictable patterns). Writing a good one is what Knuth discusses.

A good algorithm will generate a series of random numbers that will cover the whole range of available integer values. So, an 8-bit random number generator (RNG) will generate a series that is 256 integers long. A 16-bit RNG will generate a 65,536 integer long series. The random number generator we use follows the Knuth guidelines for a "good" psuedo-random number generator and uses 64-bit math to provide a very long series. Because an RNG generates the series by using a mathematical formula, the series is static and starting in the same place will always generate the same numbers in the same sequence each time you run it. This is actually a good thing, as certain applications (such as cryptography) require the ability to repeat the random sequence. In cases, where we don't want this, we need to start at a random location in the series. We do this by setting the "seed" value of the RNG, which is essentially the value corresponding to some location in the series. But how do we get a random value to seed our random series with? Isn't this a "chicken or the egg" quandry?

As it turns out, a good RNG will vary the values in the series so well that even a small difference in the starting seed will generate wildly different starting points. So, all we need is a somewhat unique value. This can be done by various methods, but probably the simplest is just using the current date/time stamp. This is what the randomize call, above, does: it takes the current time and uses it as a seed. We get the first 64-bit value, then call randomize again and get the second. We do this because without the second randomize, we will get the next value in the random sequence, but randomizing again will give us a value from another part of the sequence. This just makes it more likely to get a (globally) unique value.

Back to TMirror_Store
Now let us examine the API for managing the store.

function Get_Header_Set_Name( Header : TMirror_Header ) : string ;

begin
    setlength( Result, sizeof( Header.Set_Name ) ) ;
    move( Header.Set_Name, PChar( Result )[ 0 ], length( Result ) ) ;
    Result := Edit( Result, 4 or 128 ) ; // Trim nulls
end ;

The name in the mirror header is a 64-character long string. It is zero-filled after the last characeter for names less than 64-characters in length. This function simply pulls the data from the passed header and returns it as a string value, minus the nuls (0s).

procedure TMirror_Store.Add_Store( S : TCOM_Store64 ) ;

var Buffer : PChar ;
    Header, MHeader : TMirror_Header ;
    Sequence : int64 ;
    Size : integer ;
    Store : TCOM_Store64 ;
    E : TUnified_Exception ;

begin
    if( ( S = nil ) or ( Stores.Count > 63 ) ) then
    begin
        exit ;
    end ;

    Header := Get_Mirror_Info( S ) ;
    if( not Valid_Header( Header ) ) then
    begin
        Sequence := 0 ;
    end else
    begin
        Sequence := Header.Sequence ;
    end ;
    if( Stores.Count > 0 ) then // Not the first store in this set
    begin
        if( S.Min_Storage <> Min_Storage ) then
        begin
            exit ;
        end ;
        Store := TCOM_Store64( Stores[ 0 ] ) ;
        MHeader := Get_Mirror_Info( Store ) ;
        if( not Valid_Header( Header ) ) then // New store is not already a member
        begin
            Dirty := Dirty or XBit_Values[ Stores.Count ] ;
            Stores.Add( S ) ;
        end else
        if( MHeader.Sequence < Sequence ) then
        begin
            Stores.Insert( 0, S ) ;
            Dirty := ( Dirty shl 1 ) or 2 ;
        end else
        begin
            if( MHeader.Sequence > Sequence ) then
            begin
                Dirty := Dirty or XBit_Values[ Stores.Count ] ;
            end ;
            Stores.Add( S ) ;
        end ;
    end else
    begin
        Stores.Add( S ) ; // Add new store to the end of the store list

        // Make sure new store has proper mirror header...
        if( Valid_Header( Header ) ) then
        begin
            // Get the set name...
            _Set_Name := Get_Header_Set_Name( Header ) ;
        end else
        begin
            fillchar( Header, sizeof( Header ), 0 ) ;
            Buffer := Get_Buffer( Size ) ;
            try
                Header.Signature := $7FFF8C01008CFFFF ;
                fillchar( Header.Set_Name, sizeof( Header.Set_Name ), 0 ) ;
                move( PChar( _Set_Name )[ 0 ], Header.Set_Name, length( _Set_Name ) ) ;
                Generate_GUID( Header.Set_GUID ) ;
                Header.Sequence := 1 ;
                Header.Timestamp := Timestamp ;
                if( S is TPartition_Store ) then
                begin
                    Header.Flags := Header.Flags or 1 ;
                end ;
                move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
                S.Write_Data( Buffer[ 0 ], S.Max_Storage - Size, Size, E ) ;
            finally
                freemem( Buffer ) ;
            end ;
        end ; // if( not Valid_Header( Header ) )
    end ; // if( Stores.Count > 0 )
    Recalculate ;
end ; // TMirror_Store.Add_Store

This method adds a store to the mirror set. We allow a maximum of 64 members in a store set. So, if there are already 64 stores, we exit. Next we get the mirror header for the store. If it is invalid, that means that the store is new to this (or any) mirror set. In this case, we assume a sequence number of 0. Otherwise we get the sequence number from the store's header.
Now we have two possible situations. 1) we are adding the store to an existing mirror set, or 2) this is the first store in the set.

Before we go further, we need to understand the concept of "dirty" members. These are stores which are not currently synchronized with the rest of the mirror set. The Dirty instance variable is nothing more than a set of 64 flags indicating which (if any) of the members are dirty. Dirty members are not queried for data since we cannot be sure if the data we are getting from them matches the actual data stored in the set. We do update dirty stores on all writes, because we don't know how far we are in the process of reconciling the dirty store to the rest of the set - if the cluster in question has already been reconciled, then we need to write the change so that the cluster stays reconciled. If the cluster hasn't been reconciled yet, writing to it does no harm. How does a member become dirty? There are several possible scenarios. The simplest one is when we are adding a new store to the set for the first time. The new store doesn't match the data on the mirror set and so we have to copy the data from the current mirror set to the store. When that process is finished, the new store is consistent with the rest of the mirror set and can be marked as not dirty. But there are other ways that the member can become dirty. These include such things as unplugging the physical drive without shutting down the mirror set. The mirror set will continue to operate, and the data will continue to change, except on the unplugged drive. When it is plugged back in, it can no longer assumed to be consistent with the rest of the mirror set and is therefore marked dirty until it can be reconciled. In fact this same condition exists if the member is unplugged after the set has been shut down properly but not plugged back in when the mirror set is used again.

It is this ability to dynamically add and remove mirror set members that makes UOS mirroring so easy for the user, although it adds more complexity to the code. This is one of the reasons we assign a GUID to each mirror set, so that when a pre-existing member of a mirror set is added to the computer, we can make sure that it isn't added to the wrong mirror set - even if it was removed from a mirror set on a different computer.

So, back to the code. If we already have members in the mirror set, we add the new store to the list. If the member store has no header, or its sequence number is less than the current sequence number, then we mark it as dirty so it can be reconciled. Otherwise, it is a more recent version of the set data than what we already have, and it is moved to the first position in the Stores list and the rest of the stores are marked as dirty. Note that the Stores[ 0 ] always contains the latest version of the mirror set and all the rest of the members are kept synchronized to it. We sometimes refer to this store as the "reference store".

In the case where this is the first member in the set, it is assumed to be the latest version of the data and automatically has position 0 in the Stores list. If the store already has a mirror header, we grab the set name from there and we drop down to the recalculate call. Otherwise, the header is set up and written to the end of the store. The name of the set comes from instance data which the caller should have set up prior to this call. Note that we set the low bit in the header flags if the store given to us is a partition on some other store. Why? Well, how do we know if it is a partitioned mirror or merely the last partition on the drive that is mirrored? Herein lies a potential point of confusion for the software (and the user). That's why we clear the partition information when creating a mirror, and clear the mirror header when creating a partition. If you think about it, it makes no sense for a store to be both partitioned and mirrored. You can partition a mirror set and you can mirror a partition. You could even partition a mirror, then mirror one of its partitions. But from the standpoint of UOS, a given store is either one or the other (or neither). But if we mirror the last partition on a store, then the mirror header is written to the last cluster of the partition, which is also the last cluster of the store that contains the partition. In that case, how would we know if we have a mirror set that is paritioned or a partitioned store whose last partition is mirrored? That is the purpose of the flag. If the flag is set then we know that the mirror header refers to the partition rather than the store. At the end of the method, we call the Recalculate method to synchronize the data.

procedure TMirror_Store.Remove_Store( S : TCOM_Store64 ) ;

var Index : integer ;
    Work : int64 ;

begin
    Index := Stores.Indexof( S ) ;
    if( Index >= 0 ) then
    begin
        Stores.Delete( Index ) ;
        Work := Dirty and ( XBit_Values[ Index ] - 1 ) ;
        Dirty := ( Dirty shr 1 ) and ( not ( XBit_Values[ Index ] - 1 ) ) ;
        Dirty := Dirty or Work ;
        Recalculate ;
    end ;
end ;

This method removes a store from the set. Note that it doesn't delete the header. But the store management should be done via the TMirror_Manager class (discussed later) rather than by directly calling these routines. When a store is removed from the list, the stores in indexes above it drop down to a lower index. Since the store index corresponds to the Dirty flags (for instance, store index 0 is bit 0) we have to shift the flags down so they still correspond to the correct stores. We do this by preserving the flags lower than the index of the store being removed, then shift the dirty flags one bit to the right, mask out the bits that below the removed index, then we put the saved bits back in.

procedure TMirror_Store.Close_All( Force : boolean ) ;

var Buffer : PChar ;
    Header : TMirror_Header ;
    Loop, Size : integer ;
    Store : TCOM_Store64 ;
    E : TUnified_Exception ;

begin
    if( Stores.Count = 0 ) then
    begin
        exit ;
    end ;

    if( not Force ) then
    begin
        // Make sure data is consistent across the set
        while( Dirty <> 0 ) do
        begin
            Reconcile ;
        end ;

        // Update all of the headers...
        Header := Get_Mirror_Info( TCOM_Store64( Stores[ 0 ] ) ) ;
        inc( Header.Sequence ) ;
        Header.Timestamp := Timestamp ;
        Buffer := Get_Buffer( Size ) ;
        try
            move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
            for Loop := 0 to Stores.Count - 1 do
            begin
                Store := TCOM_Store64( Stores[ Loop ] ) ;
                Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
            end ;
        finally
            freemem( Buffer ) ;
        end ;
    end ; // if( not Force )
    Stores.Clear ;
end ; // TMirror_Store.Close_All

Close_All is the proper way to close a mirror set. There are two ways to call it. If Force is true, it clears the members from the set but doesn't reset the headers for the members. That means that the next time they are added to a mirror set, they will have to be reconciled. Otherwise, if false is passed, each member's header is updated so that the next time they are added to the mirror no reconciliation will be needed.

procedure TMirror_Store.Recalculate ;

var Current : int64 ;
    Header : TMirror_Header ;
    Loop : integer ;
    Latest_Index : integer ;
    Latest_Sequence : int64 ;
    Store : TCOM_Store64 ;

begin
    // Setup...
    Dirty := 0 ;
    Latest_Index := 0 ;
    Latest_Sequence := 0 ;

    // Find latest store in set...
    for Loop := 0 to Stores.Count - 1 do
    begin
        Store := TCOM_Store64( Stores[ Loop ] ) ;
        Header := Get_Mirror_Info( Store ) ;
        if( Header.Sequence > Latest_Sequence ) then
        begin
            Latest_Sequence := Header.Sequence ;
            Latest_Index := Loop ;
        end ;
    end ; // for Loop := 0 to Stores.Count - 1

    // Move latest to first position
    if( Latest_Index > 0 ) then
    begin
        Store := TCOM_Store64( Stores[ Latest_Index ] ) ;
        Stores.Delete( Latest_Index ) ;
        Stores.Insert( 0, Store ) ;
    end ;

    // Set the dirty flags...
    Current := 2 ;
    for Loop := 1 to Stores.Count - 1 do
    begin
        Store := TCOM_Store64( Stores[ Loop ] ) ;
        Header := Get_Mirror_Info( Store ) ;
        if(
            ( Header.Signature = 0 )
            or
            ( Header.Sequence < Latest_Sequence )
          ) then
        begin
            Dirty := Dirty or Current ;
        end ;
        Current := Current shl 1 ;
    end ;

    // Start reconciliation
    if( Dirty <> 0 ) then
    begin
        Reconcile ;
    end ;
end ; // TMirror_Store.Recalculate

The Recalculate method is used to determine which of the members in the set is the latest version and move that to index 0 of the Stores list, then mark all the stores that are out of date as dirty. In the end, the Reconcile method is called.

procedure TMirror_Store.Reconcile ;

var Clear : int64 ;
    Header : TMirror_Header ;
    Loop : integer ;
    Buffer : PChar ;
    E : TUnified_Exception ;
    Size : integer ;

begin
    Clear := 2 ;
    Buffer := Get_Buffer( Size ) ;
    try
        for Loop := 1 to Stores.Count - 1 do
        begin
            if( ( Dirty and Clear ) <> 0 ) then // A dirty store
            begin
                Reconcile_Store := TCOM_Store64( Stores[ Loop ] ) ;
                Reconcile_Offset := 0 ;
                if( Synchronous ) then
                begin
                    while( Reconcile_Offset < Max_Storage ) do
                    begin
                        TCOM_Store64( Stores[ 0 ] ).Read_Data( Buffer[ 0 ], Reconcile_Offset, Min_Storage, E ) ;
                        if( E <> nil ) then
                        begin
                            break ;
                        end ;
                        Reconcile_Store.Write_Data( Buffer[ 0 ], Reconcile_Offset, Min_Storage, E ) ;
                        if( E <> nil ) then
                        begin
                            break ;
                        end ;
                        Reconcile_Offset := Reconcile_Offset + Min_Storage ;
                    end ;
                    if( E <> nil ) then
                    begin
                        Clear := Clear shl 1 ;
                        continue ;
                    end ;
                    TCOM_Store64( Stores[ 0 ] ).Read_Data( Buffer[ 0 ], Reconcile_Store.Max_Storage - Size,
                        Size, E ) ;
                    if( E <> nil ) then
                    begin
                        Clear := Clear shl 1 ;
                        continue ;
                    end ;
                    move( Buffer[ 0 ], Header, sizeof( Header ) ) ;
                    if( Reconcile_Store is TPartition_Store ) then
                    begin
                        Header.Flags := Header.Flags or 1 ;
                    end ;
                    move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
                    Reconcile_Store.Write_Data( Buffer[ 0 ], Reconcile_Store.Max_Storage - Size, Size, E ) ;
                end ; // if( Synchronous )
                Dirty := Dirty and ( not Clear ) ;
            end ; // if( ( Dirty and Clear ) <> 0 )
            Clear := Clear shl 1 ;
        end ; // for Loop := 1 to Stores.Count - 1
    finally
        freemem( Buffer ) ;
    end ;
end ; // TMirror_Store.Reconcile

The Reconcile method loops through the stores in the list, and if the corresponding bit in the Dirty flags is set, we then copy from the store at index 0 (our reference store) to the current store, from the first to last cluster, then mark the store as clean by clearing its corresponding dirty flag. If the Synchronous flag is set, we do this all in a single operation. As we discussed earlier, we will handle asynchronous reconciliation in the future. Hint: the Reconcile_Store and Reconcile_Offset instance variables are essential to the asynchronous approach.

procedure TMirror_Store.Set_Mirror_Set_Name( Value : string ) ;

var Buffer : PChar ;
    Header : TMirror_Header ;
    Loop : integer ;
    Size : integer ;
    Store : TCOM_Store64 ;
    E : TUnified_Exception ;

begin
    _Set_Name := Value ;
    if( Count = 0 ) then
    begin
        exit ;
    end ;
    Store := TCOM_Store64( Stores[ 0 ] ) ;
    Header := Get_Mirror_Info( Store ) ;
    fillchar( Header.Set_Name, sizeof( Header.Set_Name ), 0 ) ;
    if( length( Value ) > sizeof( Header.Set_Name ) ) then
    begin
        setlength( Value, sizeof( Header.Set_Name ) ) ;
    end ;
    move( PChar( Value )[ 0 ], Header.Set_Name, length( Value ) ) ;
    Size := Mirror_Overhead( Store ) ;

    // Update header on all members of the set...
    Buffer := allocmem( Size ) ;
    try
        fillchar( Buffer[ 0 ], sizeof( Size ), 0 ) ;
        move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
        for Loop := 0 to Count - 1 do
        begin
            Store := TCOM_Store64( Stores[ Loop ] ) ;
            Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
        end ;
    finally
        freemem( Buffer ) ;
    end ;
end ; // TMirror_Store.Set_Mirror_Set_Name


function TMirror_Store.Get_Mirror_Set_Name : string ;

var Header : TMirror_Header ;
    Store : TCOM_Store64 ;

begin
    Result := '' ;
    if( Count = 0 ) then
    begin
        exit ;
    end ;
    Store := TCOM_Store64( Stores[ 0 ] ) ;
    Header := Get_Mirror_Info( Store ) ;
    Result := Get_Header_Set_Name( Header ) ;
end ;


function TMirror_Store.Count : integer ;

begin
    Result := Stores.Count ;
end ;


function TMirror_Store.GUID : TGUID ;

var Info : TRAID_Info ;

begin
    fillchar( Result, sizeof( Result ), 0 ) ;
    if( Stores.Count = 0 ) then
    begin
        exit ;
    end ;
    Info := Get_RAID_Info( TCOM_Store64( Stores[ 0 ] ) ) ;
    Result[ 0 ] := Info.RAID_GUID[ 0 ] ;
    Result[ 1 ] := Info.RAID_GUID[ 1 ] ;
end ;


function TMirror_Store.Timestamp : int64 ;

var Info : TRAID_Info ;

begin
    Result := 0 ;
    if( Stores.Count = 0 ) then
    begin
        exit ;
    end ;
    Info := Get_RAID_Info( TCOM_Store64( Stores[ 0 ] ) ) ;
    Result := Info.Timestamp ;
end ;


function TMirror_Store.Sequence : int64 ;

var Info : TRAID_Info ;

begin
    Result := 0 ;
    if( Stores.Count = 0 ) then
    begin
        exit ;
    end ;
    Info := Get_RAID_Info( TCOM_Store64( Stores[ 0 ] ) ) ;
    Result := Info.Sequence ;
end ;

These support routines are fairly self-explanatory. They simply provide information by getting it from the store at index 0. Set_Mirror_Set_Name writes a string value to the mirror header on all the member stores. It is used to change the mirror set's name.

The TMirror_Manager class is used to manage collections of mirrors. That is, there can be any number of mirror sets in use at any one time. Here is the class definition:

type TMirror_Manager = class
                           public // Constructors and destructors...
                               constructor Create ;
                               destructor Destroy ; override ;

                           private // Instance data...
                               Stores : TList ;

                           public // API...
                               procedure Add( Store : TMirror_Store ) ;
                               function Get( Index : integer ) : TMirror_Store ;
                               function Remove( Index : integer ) : TUnified_Exception ;
                                   overload ;
                               function Remove( Store : TCOM_Store64 ) : TUnified_Exception ;
                                   overload ;
                               function Count : integer ;
                               function Store_With_GUID( GUID : TGUID ) : TMirror_Store ;
                       end ; // TMirror_Manager

Now let us look at the implementation of the methods of this class.

// Constructors and destructors...

constructor TMirror_Manager.Create ;

begin
    inherited Create ;

    Stores := TList.Create ;
end ;


destructor TMirror_Manager.Destroy ;

begin
    Stores.Free ;
    Stores := nil ;

    inherited Destroy ;
end ;


// API...

procedure TMirror_Manager.Add( Store : TMirror_Store ) ;

begin
    Stores.Add( Store ) ;
end ;


function TMirror_Manager.Get( Index : integer ) : TMirror_Store ;

begin
    Result := TMirror_Store( Stores[ Index ] ) ;
end ;


function TMirror_Manager.Count : integer ;

begin
    Result := Stores.Count ;
end ;


function TMirror_Manager.Store_With_GUID( GUID : TGUID ) : TMirror_Store ;

var Info : TGUID ;
    Loop : integer ;

begin
    for Loop := 0 to Stores.Count - 1 do
    begin
        Result := TMirror_Store( Stores[ Loop ] ) ;
        Info := Result.GUID ;
        if( ( Info[ 0 ] = GUID[ 0 ] ) and ( Info[ 1 ] = GUID[ 1 ] ) ) then
        begin
            exit ;
        end ;
    end ;
    Result := nil ;
end ;

These are simple constructors, destructors, and functions for adding and getting mirror sets. Count returns the number of mirror sets and Store_With_GUID returns the mirror set which has the passed GUID.

function TMirror_Manager.Remove( Index : integer ) : TUnified_Exception ;

var Loop : integer ;
    MStore : TMirror_Store ;

begin
    Result := nil ;
    if( ( Index < 0 ) or ( Index >= Stores.Count ) ) then
    begin
        exit ;
    end ;
    MStore := TMirror_Store( Stores[ Index ] ) ;
    for Loop := MStore.Count - 1 downto 0 do
    begin
        Result := Remove( TCOM_Store64( MStore.Stores[ Loop ] ) ) ;
        if( Result <> nil ) then
        begin
            exit ;
        end ;
    end ;
    Stores.Delete( Index ) ;
end ; // TMirror_Manager.Remove


function TMirror_Manager.Remove( Store : TCOM_Store64 ) : TUnified_Exception ;

var Buffer : PChar ;
    Loop : integer ;
    MStore : TMirror_Store ;
    Size : integer ;

begin
    // Remove from mirror set...
    for Loop := 0 to Stores.Count - 1 do
    begin
        MStore := Get( Loop ) ;
        MStore.Remove_Store( Store ) ;
    end ;

    // Unmark store are being part of a set...
    Buffer := allocmem( Store.Min_Storage ) ;
    try
        Size := Mirror_Overhead( Store ) ;
        fillchar( Buffer[ 0 ], sizeof( Store.Min_Storage ), 0 ) ;
        Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, Result ) ;
    finally
        freemem( Buffer ) ;
    end ;
end ; // TMirror_Manager.Remove

There are two Remove methods. The first takes an index and deletes that mirror set. It loops through the stores in the set and calls the other Remove method, passing each member. The other Remove method takes a store (but not a mirror store) and removes it from the mirror set, erasing the mirror header on the store.

var _MStores : TMirror_Manager = nil ;

function MStores : TMirror_Manager ;

begin
    if( _MStores = nil ) then
    begin
        _MStores := TMirror_Manager.Create ;
    end ;
    Result := _MStores ;
end ;

This function provides access to the mirror manager, which is a singleton. It is created upon the first reference to MStores.

Here are the rest of the mirror support functions:

function Valid_Header( var Header : TMirror_Header ) : boolean ;

begin
    Result := False ;
    if( Header.Signature <> $7FFF8C01008CFFFF ) then
    begin
        exit ;
    end ;
    Result := True ;
end ; // Valid_Header

This function simply checks the header signature to make sure it is a valid mirror header.

function Get_Mirror_Info( Store : TCOM_Store64 ) : TMirror_Header ;

var Buffer : PChar ;
    E : TUnified_Exception ;
    Size : integer ;

begin
    fillchar( Result, sizeof( Result ), 0 ) ;
    if( Store = nil ) then
    begin
        exit ;
    end ;
    Size := Round_Up( sizeof( Result ), Store.Min_Storage ) ;
    Buffer := allocmem( Size ) ;
    try
        Store.Read_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
        if( E <> nil ) then
        begin
            exit ;
        end ;

        // Check anchor header...
        move( Buffer[ 0 ], Result, sizeof( Result ) ) ;
        if( not Valid_Header( Result ) ) then
        begin
            fillchar( Result, sizeof( Result ), 0 ) ;
            exit ;
        end ;

    finally
        freemem( Buffer ) ;
    end ;
end ; // Get_Mirror_Info

This function retrieves the header for a mirror set.

function RAID_Type( Store : TCOM_Store64 ) : integer ;

var Info : TRAID_Info ;

begin
    Info := Get_RAID_Info( Store ) ;
    Result := Info.RAID_Level ;
end ;


function Get_RAID_Info( Store : TCOM_Store64 ) : TRAID_Info ;

var Header : TMirror_Header ;

begin
    fillchar( Result, sizeof( Result ), 0 ) ;
    Result.RAID_Level := -1 ; // Unknown
    Header := Get_Mirror_Info( Store ) ;
    if( not Valid_Header( Header ) ) then
    begin
        exit ;
    end ;
    if( not ( Store is TPartition_Store ) ) then
    begin
        if( ( Header.Flags and 1 ) <> 0 ) then
        begin
            exit ; // RAID is for a partition and this store isn't a partition
        end ;
    end ;

    Result.RAID_Level := 1 ;
    Result.RAID_Name[ 0 ] := #64 ;
    move( Header.Set_Name, Result.RAID_Name[ 1 ], length( Result.RAID_Name ) ) ;
    Result.RAID_Name := Edit( Result.RAID_Name, 4 ) ;
    Result.RAID_GUID[ 0 ] := Header.Set_GUID[ 0 ] ;
    Result.RAID_GUID[ 1 ] := Header.Set_GUID[ 1 ] ;
    Result.Timestamp := Header.Timestamp ;
    Result.Sequence := Header.Sequence ;
    Result.Flags := Header.Flags ;
end ; // Get_RAID_Info

This function returns information about a RAID set. Rather than return a mirror header, the function translates it into an independent format which allows us to modify the header format without breaking the Init code that depends upon it.

procedure Remove_From_Set( Store : TCOM_Store64 ) ;

var Buffer : PChar ;
    Size : integer ;
    E : TUnified_Exception ;

begin
    if( Store = nil ) then
    begin
        exit ;
    end ;
    Buffer := _Get_Buffer( Store, Size ) ;
    try
        fillchar( Buffer[ 0 ], Size, 0 ) ;
        Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
    finally
        freemem( Buffer ) ;
    end ;
end ;

This function clears the mirror header for a store, essentially removing it from any mirror set.

procedure New_Set( Store : TCOM_Store64 ) ;

var Buffer : PChar ;
    Header : TMirror_Header ;
    Size : integer ;
    E : TUnified_Exception ;

begin
    if( Store = nil ) then
    begin
        exit ;
    end ;
    Buffer := _Get_Buffer( Store, Size ) ;
    try
        Store.Read_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
        if( E <> nil ) then
        begin
            exit ;
        end ;
        move( Buffer[ 0 ], Header, sizeof( Header ) ) ;
        Header.Sequence := 0 ;
        Header.Timestamp := Sirius_Timestamp ;
        Generate_GUID( Header.Set_GUID ) ;
        move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
        Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
    finally
        freemem( Buffer ) ;
    end ;
end ;

This function creates a new mirror set on the passed store.

procedure Synchronize_Store( Store : TCOM_Store64 ; MStore : TMirror_Store ) ;

var Buffer : PChar ;
    Header : TMirror_Header ;
    Size : integer ;
    E : TUnified_Exception ;

begin
    if( ( Store = nil ) or ( MStore = nil ) ) then
    begin
        exit ;
    end ;
    Buffer := _Get_Buffer( Store, Size ) ;
    try
        Store.Read_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
        if( E <> nil ) then
        begin
            exit ;
        end ;
        move( Buffer[ 0 ], Header, sizeof( Header ) ) ;
        Header.Sequence := MStore.Sequence + 1 ;
        Header.Timestamp := Sirius_TimeStamp ;
        move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
        Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
    finally
        freemem( Buffer ) ;
    end ;
    MStore.Add_Store( Store ) ;
end ;

This function makes the passed store the reference store of the mirror set passed as MStore. This is done by updating the timestamp to the current time and setting the sequence to the current sequence, plus one. Then adding the passed store to the mirror set.

function Mirror_Overhead( Store : TCOM_Store64 ) : integer ;

begin
    Result := Round_Up( sizeof( TMirror_Header ), Store.Min_Storage ) ;
end ;

This function simply rounds the size of the mirror header up to the cluster size of the store, thus giving the actual overhead of the mirror header on this store.

procedure Refresh_Store( Store : TCOM_Store64 ) ;

var Buffer : PChar ;
    Header : TMirror_Header ;
    Size : integer ;
    E : TUnified_Exception ;

begin
    if( Store = nil ) then
    begin
        exit ;
    end ;
    Buffer := _Get_Buffer( Store, Size ) ;
    try
        Store.Read_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
        if( E <> nil ) then
        begin
            exit ;
        end ;
        move( Buffer[ 0 ], Header, sizeof( Header ) ) ;
        Header.Sequence := 0 ;
        Header.Timestamp := 0 ;
        move( Header, Buffer[ 0 ], sizeof( Header ) ) ;
        Store.Write_Data( Buffer[ 0 ], Store.Max_Storage - Size, Size, E ) ;
    finally
        freemem( Buffer ) ;
    end ;
end ;

This function clears the timestamp and sequence in the mirror header of the passed store. This will cause the store to be synchronized to the rest of the mirror set when the store is added to one.

Back to Init
We now need to provide Init with a means of referencing this new mirror store. Since it is a logical construct, there is no controller that we can associate with it (in fact, disks in the set may reside on multiple different controllers). For this reason, we reserve controller 26 (DISKZ) as a logical controller for these logical constructs. That leaves us 25 other possible controllers for stores, which should be adequate. Note: in truth, there are some other special cases which reduce the number of possible physical controllers, but more about that in the future.

We need to also prevent the set members from being independently accessed outside of the mirror store. To allow otherwise would be to open the mirror set to data corruption. It is essential that the set members only be accessed via the mirror store. That is why the mirror header is deleted when a store is partitioned (and vice versa).

Just as was the case with partitions, the HAL doesn't know about UOS mirror sets since they are a software construct instead of hardware. So, the Parse_Device function has to be changed to handle them. The following code is added to the function:

if( Controller = 25 ) then // RAID device
begin
    if( _Unit < RAID_Count ) then
    begin
        Result := MStores.Get( _Unit ) ;
    end ;
    exit ;
end ;

This simply returns the mirror set store that corresponds to the specified unit of controller 25.

function RAID_Count : integer ;

begin
    if( First_Time ) then
    begin
        First_Time := False ;
        Locate_RAID ;
    end ;
    Result := MStores.Count ;
end ;

The RAID_Count function returns the count of mirrors from the mirror manager, but first makes sure that the mirror manager has been initialized with all of the mirror sets that have been defined. The first time we ask for RAID or device information, we make sure that we locate all possible mirror sets, by looking at each store connected to the system (including partitions). References to HAL.Stores and HAL.Device are wrapped with functions (HAL_Stores and HAL_Device) that take mirror sets into account, thus providing a unified interface to all devices.

Here are these routines:

var First_Time : boolean = True ;

procedure Locate_RAID ;

var Count, Index : integer ;
    Info : TDevice_Info ;
    RInfo : TRAID_Info ;
    Store, PStore : TCOM_Store64 ;

begin
    // Run through the physical devices, looking for any RAID sets...
    Index := 0 ;
    while( True ) do
    begin
        Info := HAL.Device( Index ) ;
        if( Info.Device_Type = DT_Non_Existant ) then
        begin
            exit ; // No more devices
        end ;
        if( Info.Device_Type = DT_Store ) then
        begin
            Store := HAL.Store( Index ) ;
            RInfo := Get_RAID_Info( Store ) ;
            if( RInfo.RAID_Level < 0 ) then // Not a mirror member
            begin
                // Check partitions...
                Count := Partition_Count( Store ) ;
                while( Count > 0 ) do
                begin
                    PStore := Get_Partition( Store, Count - 1 ) ;
                    Check_Store( Device_Name( Info ) + Partition_Spec( Count - 1 ), PStore ) ;
                    dec( Count ) ;
                end ;
            end else
            begin
                Check_Store( Device_Name( Info ), Store ) ;
            end ;
        end ;
        inc( Index ) ;
    end ; // while( True )
end ; // Locate_RAID

This function loops through the physical devices, looking for stores. If the store is partitioned, it loops through the partitions as well. When a new Mirror set GUID is found, a new mirror set is created. Here's the Check_Store code:

procedure Check_Store( Name : string ; Store : TCOM_Store64 ) ;

var RInfo : TRAID_Info ;
    MStore : TMirror_Store ;
    S : string ;

label Ask_Again, Ask_Again1 ;

begin
    if( Store = nil ) then
    begin
        exit ;
    end ;
    RInfo := Get_RAID_Info( Store ) ;
    if( RInfo.RAID_Level = 1 ) then // Found a mirror member
    begin
        MStore := MStores.Store_With_GUID( RInfo.RAID_GUID ) ;
        if( MStore = nil ) then
        begin
            MStore := TMirror_Store.Create ;
            MStore.Synchronous := True ;
            MStores.Add( MStore ) ;
        end else
        if(
            ( MStore.Min_Storage <> Store.Min_Storage )
            or
            ( MStore.Max_Storage <> Store.Max_Storage - Mirror_Overhead( Store ) )
          ) then
        begin
Ask_Again:
            Output_Line( Name + 
                ' is a mirror set member, but is incompatible with the other members of the set.' ) ;
            Output_Line( 'How do you want to resolve this?' ) ;
            Output_Line( 'D - Drop from any/all mirror sets' ) ;
            Output_Line( 'N - Make it a member of a new mirror set' ) ;
            Output( 'Option: ' ) ;
            S := Input( '' ) ;
            if( S = #3 ) then
            begin
                goto Ask_Again ;
            end ;
            if( ( S = ESC ) or ( S = #26 ) ) then
            begin
                goto Ask_Again ;
            end ;
            if( S = 'D' ) then
            begin
                Remove_From_Set( Store ) ;
            end else
            if( S = 'N' ) then
            begin
                New_Set( Store ) ;
            end else
            begin
                Output_Line( 'Invalid option' ) ;
                goto Ask_Again ;
            end ;
        end else
        if(
            (
              ( RInfo.Timestamp > MStore.Timestamp )
              and
              ( RInfo.Sequence <= MStore.Sequence )
            )
            or
            (
              ( RInfo.Timestamp < MStore.Timestamp )
              and
              ( RInfo.Sequence >= MStore.Sequence )
            )
          ) then // Some sort of mismatch
        begin
Ask_Again1:
            Output_Line( Name + 
                ' is a mirror set member, but is inconsistent with the other members of the set.' ) ;
            Output_Line( 'How do you want to resolve this?' ) ;
            Output_Line( 'D - Drop from any/all mirror sets' ) ;
            Output_Line( 'N - Make it a member of a new mirror set' ) ;
            Output_Line( 'S - Synchronize existing mirror set to this store' ) ;
            Output_Line( 'R - Refresh store from other stores in the mirror set' ) ;
            Output( 'Option: ' ) ;
            S := Input( '' ) ;
            if( S = #3 ) then
            begin
                goto Ask_Again1 ;
            end ;
            if( ( S = ESC ) or ( S = #26 ) ) then
            begin
                goto Ask_Again1 ;
            end ;
            if( S = 'D' ) then
            begin
                Remove_From_Set( Store ) ;
            end else
            if( S = 'N' ) then
            begin
                New_Set( Store ) ;
                MStore := TMirror_Store.Create ;
                MStore.Synchronous := True ;
                MStores.Add( MStore ) ;
                MStore.Add_Store( Store ) ;
            end else
            if( S = 'S' ) then
            begin
                Synchronize_Store( Store, MStore ) ;
                MStore.Add_Store( Store ) ;
            end else
            if( S = 'R' ) then
            begin
                Refresh_Store( Store ) ;
                MStore.Add_Store( Store ) ;
            end else
            begin
                Output_Line( 'Invalid option' ) ;
                goto Ask_Again ;
            end ;
        end ;
        MStore.Add_Store( Store ) ;
    end ; // if( RInfo.RAID_Level = 1 )
end ; // Check_Store

Check_Store adds the store to the mirror set, and creates the mirror set if it doesn't exist yet. First it verifies that there isn't some sort of inconsistency between the store and the other members of the set. How could an inconsistency happen? Consider, as one example, this scenario: A mirror set is created and used. Then one of the members is disconnected and used on another computer. Then it is put back after some time has gone by. Now we have a store with the same GUID and a later timestamp, but an earlier sequence number (or, conversely, a later sequence but an earlier timestamp). This is a possible consequence of allowing the user to dynamically add and remove mirror set members. In an example such as I've just provided, it is unclear how to proceed. The user has potentially split the mirror set into two independent ones. There is no way we can reliably reconcile these stores programatically. So, we will ask the user how they want to resolve the issue. In one case, the store sizes and/or minimum cluster sizes don't match. This makes the stores inherently incompatible. The user only has two choices: either remove the offending store from the set or make it part of a different set. In the second case, we have the mismatch in timestamp and sequence. In such case, the user has the aforementioned choices, plus the following two: force the offending store to conform to the existing set data, or force the set data to conform to the offending store. The user will have to make a choice to reconcile any of these conflicts before continuing.

function HAL_Store( Index : integer ) : TCOM_Store64 ;

var I : integer ;
    Last_HAL_Device_Index : integer ;

begin
    if( First_Time ) then
    begin
        First_Time := False ;
        Locate_RAID ;
    end ;
    Result := HAL.Store( Index ) ;
    if( Result <> nil ) then
    begin
        exit ;
    end ;

    I := 0 ;
    while( I <= Index ) do
    begin
        Result := HAL.Store( I ) ;
        if( Result = nil ) then
        begin
            if( I - Last_HAL_Device_Index > MStores.Count ) then
            begin
                exit ;
            end ;
            if( I = Index ) then
            begin
                Result := MStores.Get( I - Last_HAL_Device_Index - 1 ) ;
                exit ;
            end ;
        end else
        begin
            Last_HAL_Device_Index := I ;
        end ;
        inc( I ) ;
    end ; // while( I <= Index )
end ; // HAL_Store

This function loops through the physical stores (HAL.Store), and when we run out of stores, we then loop through the mirror sets.

function HAL_Device( Index : integer ) : TDevice_Info ;

var I : integer ;
    Last_HAL_Device_Index : integer ;

begin
    if( First_Time ) then
    begin
        First_Time := False ;
        Locate_RAID ;
    end ;
    Result := HAL.Device( Index ) ;
    if( Result.Device_Type <> DT_Non_Existant ) then
    begin
        exit ;
    end ;

    I := 0 ;
    while( I <= Index ) do
    begin
        Result := HAL.Device( I ) ;
        if( Result.Device_Type = DT_Non_Existant ) then
        begin
            if( I - Last_HAL_Device_Index > MStores.Count ) then
            begin
                exit ;
            end ;
            if( I = Index ) then
            begin
                Result.Device_Type := DT_Store ;
                Result.Controller := 25 ;
                Result.Device_Unit := I - Last_HAL_Device_Index - 1 ;
                Result.Media_Present := MStores.Count <> 0 ;
                exit ;
            end ;
        end else
        begin
            Last_HAL_Device_Index := I ;
        end ;
        inc( I ) ;
    end ; // while( I <= Index )
end ; // HAL_Device

Similar to the HAL_Store function, this loops through the physical devices (HAL.Device) and when it finishes, it loops through the mirror sets, constructing a result that has a controller of 25 and a unit that matches the mirror set index in MStores. To the rest of the Init code, a mirror set just looks like another physical device.

Here are input loop routines related to mirroring:

function Disk_RAID_Remove( S : string ) : boolean ;

var Prompt : boolean ;
    Store : TCOM_Store64 ;
    E : TUnified_Exception ;

begin
    Result := False ;
    Prompt := S = '' ;
    while( True ) do
    begin
        if( Prompt ) then
        begin
            Output( 'Disk to remove from mirror set: ' ) ;
            S := Input( '' ) ;
        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 ;
        if( copy( S, 1, 5 ) = 'DISKZ' ) then
        begin
            Output_Line( 'Cannot remove a set from the set' ) ;
            continue ;
        end ;
        Store := Parse_Device( S ) ;
        if( Store = nil ) then
        begin
            Output_Line( 'Invalid device' ) ;
        end else
        begin
            E := MStores.Remove( Store ) ;
            if( E <> nil ) then
            begin
                Show_Error( E ) ;
            end ;
        end ;
        if( not Prompt ) then
        begin
            exit ;
        end ;
    end ; // while( True )
end ; // Disk_RAID_Remove


function Disk_RAID_Add : boolean ;

var Disk, Name, S : string ;
    MStore : TMirror_Store ;
    Size : integer ;
    Store : TCOM_Store64 ;

label Ask_Disk, Ask_Name ;

begin
    Result := False ;
    if( RAID_Count = 0 ) then
    begin
        Output_Line( 'No existing mirror sets' ) ;
        exit ;
    end ;

Ask_Name:
    Output( 'Existing mirror set device <DISKZ0> : ' ) ;
    Name := Input( 'DISKZ0' ) ;
    if( Name = #3 ) then
    begin
        Result := True ;
        exit ;
    end ;
    if( ( Name = ESC ) or ( Name = #26 ) ) then
    begin
        exit ;
    end ;
    if( copy( lowercase( Name ), 1, 5 ) <> 'diskz' ) then
    begin
        Output_Line( 'Device is not a mirror set.' ) ;
        goto Ask_Name ;
    end ;
    MStore := TMirror_Store( Parse_Device( Name ) ) ;
    if( MStore = nil ) then
    begin
        Output_Line( 'Invalid device' ) ;
        goto Ask_Name ;
    end ;

Ask_Disk:
    Output( 'Disk to add to mirror set: ' ) ;
    Disk := Input( '' ) ;
    if( Disk = #3 ) then
    begin
        Result := True ;
        exit ;
    end ;
    if( ( Disk = ESC ) or ( Disk = #26 ) ) then
    begin
        goto Ask_Name ;
    end ;

    if( copy( lowercase( Disk ), 1, 5 ) = 'diskz' ) then
    begin
        Output_Line( 'Device is a mirror set and cannot be added as a set member.' ) ;
        goto Ask_Name ;
    end ;
    Store := Parse_Device( Disk ) ;
    if( Store = nil ) then
    begin
        Output_Line( 'Invalid device' ) ;
        goto Ask_Disk ;
    end ;
    if( RAID_Type( Store ) <> -1 ) then
    begin
        Output_Line( 'Device is already part of a RAID set' ) ;
        goto Ask_Disk ;
    end ;
    Size := Mirror_Overhead( Store ) ;
    if(
        ( Store.Min_Storage <> MStore.Min_Storage )
        or
        ( Store.Max_Storage - Size <> MStore.Max_Storage )
      ) then
    begin
        Output_Line( 'Device characteristics do not match' ) ;
        goto Ask_Disk ;
    end ;
    Show_Store_Info( Store ) ;
    Output( 'Any existing data on the device will be lost.  Continue? <NO>: ' ) ;
    S := Input( 'NO' ) ;
    if( S = #3 ) then
    begin
        Result := True ;
        exit ;
    end ;
    if( copy( S, 1, 1 ) <> 'Y' ) then
    begin
        goto Ask_Disk ;
    end ;
    MStore.Add_Store( Store ) ;
end ; // Disk_RAID_Add


function Disk_RAID_Delete( S : string ) : boolean ;

var E : TUnified_Exception ;
    MStore : TCom_Store64 ;
    Prompt : boolean ;

begin
    Result := False ;
    if( MStores.Count = 0 ) then
    begin
        Output_Line( 'No mirror sets exist' ) ;
        exit ;
    end ;
    Prompt := S = '' ;
    while( True ) do
    begin
        if( Prompt ) then
        begin
            Output( 'Mirror set to delete: ' ) ;
            S := Input( '' ) ;
        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 ) ;
        MStore := Parse_Device( S ) ;
        if( MStore = nil ) then
        begin
            Output_Line( 'Invalid device' ) ;
        end else
        if( copy( S, 1, 5 ) <> 'DISKZ' ) then
        begin
            Output_Line( 'Device is not a mirror set' ) ;
        end else
        begin
            E := MStores.Remove( strtoint( copy( S, 6, length( S ) ) ) ) ;
            if( E <> nil ) then
            begin
                Show_Error( E ) ;
            end ;
        end ;
        if( not Prompt ) then
        begin
            exit ;
        end ;
    end ; // while( True )
end ; // Disk_RAID_Delete


function Disk_RAID_Create : boolean ;

var Disk_List : TStringList ;
    Index, Loop : integer ;
    Disk, Name, S : string ;
    First_Store, Store : TCOM_Store64 ;
    MStore, New_MStore : TMirror_Store ;
    E : TUnified_Exception ;

label Ask_Name ;

begin
    Result := False ;
    First_Store := nil ;
    Disk_List := TStringList.Create ;
    try
Ask_Name:
        Output( 'Name for new mirror set <> : ' ) ;
        Name := Input( '', False ) ;
        if( Name = #3 ) then
        begin
            Result := True ;
            exit ;
        end ;
        if( ( Name = ESC ) or ( Name = #26 ) ) then
        begin
            exit ;
        end ;

        Output_Line( 'Enter disks to add to mirror set.' ) ;
        Output_Line( 'After last disk, enter a blank specification to continue.' ) ;
        while( True ) do
        begin
            Output( 'Disk to add <> : ' ) ;
            Disk := Input( '' ) ;
            if( Disk = #3 ) then
            begin
                Result := True ;
                exit ;
            end ;
            if( ( Disk = ESC ) or ( Disk = #26 ) ) then
            begin
                exit ;
            end ;
            if( Disk = '' ) then
            begin
                break ;
            end ;
            if( Disk_List.IndexOf( Disk ) > -1 ) then
            begin
                Output_Line( 'Disk already in list' ) ;
                continue ;
            end ;
            Store := Parse_Device( Disk ) ;
            if( Store = nil ) then
            begin
                Output_Line( 'Invalid device' ) ;
                continue ;
            end ;
            if( First_Store = nil ) then
            begin
                First_Store := Store ;
            end else
            begin
                if(
                    ( First_Store.Min_Storage <> Store.Min_Storage )
                    or
                    ( First_Store.Max_Storage <> Store.Max_Storage )
                  ) then
                begin
                    Output_Line( 'Device characteristics do not match' ) ;
                    continue ;
                end ;
            end ;
            if( RAID_Type( Store ) <> -1 ) then
            begin
                Output_Line( 'Device is already part of a RAID set' ) ;
                continue ;
            end ;
            Show_Store_Info( Store ) ;
            Output( 'Any existing data on the device will be lost.  Continue? <NO>: ' ) ;
            S := Input( 'NO' ) ;
            if( S = #3 ) then
            begin
                Result := True ;
                exit ;
            end ;
            if( copy( S, 1, 1 ) <> 'Y' ) then
            begin
                continue ;
            end ;
            Disk_List.Add( Disk ) ;
        end ; // while( True )
        if( Disk_List.Count > 64 ) then
        begin
            Output_Line( 'Too many devices for mirror set.' ) ;
        end ;

        New_MStore := TMirror_Store.Create ;
        New_MStore.Synchronous := True ;
        for Loop := 0 to Disk_List.Count - 1 do
        begin
            Store := Parse_Device( Disk_List[ Loop ] ) ;
            for Index := 0 to MStores.Count - 1 do
            begin
                MStore := TMirror_Store( MStores.Get( Index ) ) ;
                MStore.Synchronous := True ;
                MStore.Remove_Store( Store ) ;
                if( MStore.Count = 0 ) then // Removed last member of the set
                begin
                    E := MStores.Remove( Index ) ;
                    if( E <> nil ) then
                    begin
                        Show_Error( E ) ;
                    end ;
                end ; // if( MStore.Count = 0 )
            end ; // for Index := 0 to MStores.Count - 1
            New_MStore.Add_Store( Store ) ;
        end ; // for Loop := 0 to Disk_List.Count - 1
        New_MStore.Mirror_Set_Name := Name ;
        MStores.Add( New_MStore ) ;
    finally
        Disk_List.Free ;
    end ;
end ; // Disk_RAID_Create


function Disk_RAID( 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 RAID> ' ) ;
            S := Input( '' ) ;
        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 ) ;
        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 a store to an existing mirror set' ) ;
            Output_Line( 'CREATE - Create a new mirror set' ) ;
            Output_Line( 'DELETE - Delete a mirror set' ) ;
            Output_Line( 'HELP - Show this text' ) ;
            Output_Line( 'REMOVE - Remove a member from a mirror set' ) ;
            Output_Line( '' ) ;
        end else
        if( Match( 'ADD', S, 1 ) ) then
        begin
            if( Disk_RAID_Add ) then
            begin
                Result := True ;
                exit ;
            end ;
        end else
        if( Match( 'CREATE', S, 1 ) ) then
        begin
            if( Disk_RAID_Create ) then
            begin
                Result := True ;
                exit ;
            end ;
        end else
        if( Match( 'DELETE', S, 1 ) ) then
        begin
            if( Disk_RAID_Delete( S1 ) ) then
            begin
                Result := True ;
                exit ;
            end ;
        end else
        if( Match( 'REMOVE', S, 1 ) ) then
        begin
            if( Disk_RAID_Remove( S1 ) ) then
            begin
                Result := True ;
                exit ;
            end ;
        end else
        begin
            Output_Line( 'Invalid subcommand' ) ;
        end ;
        if( not Prompt ) then
        begin
            exit ;
        end ;
    end ; // while( True )
end ; // Disk_RAID

My apologies for the extra long article. In the next article, we will look at yet another use for stores.