Rebuilding the File System

We have previously discussed the need for a process to recover from a dirty shutdown of the file system. That is, the system is turned off or crashes before the on-store allocation table is updated from the in-memory copy. Attempting to use the file system in this state is almost guaranteed to corrupt files. Thus, if we want to safely use the file system, we need a way to rebuild the allocation table on the store. We were careful to do operations in an order that guaranteed that if something went wrong that the file structure wouldn't be corrupted, although some allocated space may not have be returned to the free space. The rebuild process will make sure that those unused, but allocated, areas are returned to the free space of the store. When finished, we will have a clean file system structure that can be used safely. Let's review this method:

function TUOS_Native_File_System.Rebuild : boolean ;

var Buffer : PChar ;
    C, Cluster : int64 ;
    FSHeader : FS_Header ;
    P, P1 : TStore_Address64 ;
    FRoot : TUOS_Native_File ;
    UEC : TUnified_Exception ;
    
begin // TUOS_Native_File_System.Rebuild
    Result := False ;
    if( _Store = nil ) then
    begin
        exit ;
    end ;
    if( Mounted ) then
    begin
        Set_Last_Error( Create_Exception( UOS_File_System_Already_Mounted, nil ) ) ;
        exit ; // Cannot rebuild a mounted file system
    end ;

First we see if the file system is already mounted. We can't repair the allocation table while the file system is in use. Rebuilding has to happen before the store is mounted.

    Set_Last_Error( nil ) ;
    if( not Valid_File_System ) then
    begin
        exit ;
    end ;

The Valid_File_System methods checks that we have a valid file system structure on the store. If not, there is no way we can rebuild the allocation table and so we exit.

    Buffer := allocmem( Store.Min_Storage ) ;
    try
        // Ensure the store is marked as dirty...
        Store.Read_Data( Buffer[ 0 ], P, sizeof( FSHeader ), UEC ) ;
        FSHeader.Flags := FSHeader.Flags or UOSFSF_Dirty ;
        move( FSHeader, Buffer[ 0 ], sizeof( FSHeader ) ) ;
        Store.Write_Data( Buffer[ 0 ], P, sizeof( FSHeader ), UEC ) ;
        if( UEC <> nil ) then
        begin
            exit ;
        end ;

We can run the rebuild process even on a clean store, in which case we need to make sure the file system is marked as dirty in case the rebuild process is aborted (via a power failure, for instance). So we set the dirty flag regardless.

        // Get root directory...
        FRoot := TUOS_Native_File.Create ;
        Store.Read_Data( Buffer[ 0 ], FSHeader.Root, sizeof( FRoot.Header ), UEC ) ;
        if( UEC <> nil ) then
        begin
            exit ;
        end ;
        move( Buffer^, FRoot.Header, sizeof( FRoot.Header ) ) ;
        FRoot.Store := Store ;

        // Clear the allocation table...
        Store.Set_Min_Storage( FSHeader.Clustersize ) ;
        Store.Deallocate( FSHeader.Clustersize, Store.Max_Storage ) ;

First we create a root directory file instance, and then deallocate all the storage on the store. This will clear the allocation table.

        // Reallocate allocation rable, store header, and root directory header...
        C := _Store.Max_Storage div FSHeader.Clustersize ; // Total clusters
        Store.Allocate_At( FSHeader.AT_Offset, C div 8 ) ;
        Store.Allocate_At( FSHeader.Root, FSHeader.Clustersize ) ;
        Store.Allocate_At( P, FSHeader.Clustersize ) ;

Now that the allocation table is clear, we mark the used areas via the Allocate_At method, for the header, the root cluster, and the root folder header.

        // Handle allocation chain of the root folder...
        Cluster := 0 ;
        P1 := FRoot.Get_Allocation_Cluster( 0, Cluster ) ;
        while( P1 > 0 ) do
        begin
            if( not Store.Allocate_At( P1, FRoot.Header.Clustersize ) ) then
            begin
                // Cluster already allocated.  Something has corrupted the file structure
                Result := True ;
            end ;
            inc( Cluster ) ;
            P1 := FRoot.Get_Allocation_Cluster( 0, Cluster ) ;
        end ;

Next we go through the allocation cluster for the root folder and allocate the clusters for it.

        // Process the file structure...
        Process( FRoot ) ;

The workhouse of the method is the local Process procedure, which we will look at in a bit.

        // Cleanup...
        FRoot.Free ;

        // Persist the updated allocation table...
        Store.Set_Allocation_Table_Offset( FSHeader.AT_Offset ) ;
        Store.Flush_Allocation_Table ;

        // Mark store as clean...
        FSHeader.Flags := FSHeader.Flags and ( not UOSFSF_Dirty ) ;
        move( FSHeader, Buffer[ 0 ], sizeof( FSHeader ) ) ;
        Store.Write_Data( Buffer[ 0 ], P, sizeof( FSHeader ), UEC ) ;
        if( UEC <> nil ) then
        begin
            exit ;
        end ;
    finally
        freemem( Buffer ) ;
    end ;
end ; // TUOS_Native_File_System.Rebuild

Finally, we clean up our work variables, flush the now-complete allocation table to the store, and mark the file system as clean.

Now let us examine the local Process procedure. It is called recursively, with the root folder file being passed in the initial call from the body of the method. As other folders are found in the root folder, the function recursively calls itself - passing each subfolder in turn. As each of those folders is processed, any subfolders are handled similarly.

    procedure Process( Folder : TUOS_Native_File ) ;

    var Cluster : int64 ;
        F : TUOS_Native_File ;
        Header : TUOS_File_Header ;
        Index : integer ;
        P : TStore_Address64 ;
        Stream : integer ;

    begin
        Index := 0 ;
        while( Folder.Read( 0, Index * sizeof( Header ), sizeof( Header ), Header ) > 0 ) do
        begin
            inc( Index ) ;

As you (hopefully) recall, each folder is a file containing file headers. We iterate through each header in the folder until the Read method returns 0, indicating that we reached the end of the folder.

            if( Header.Name <> 0 ) then
            begin
                if( Header.Clustersize = 0 ) then
                begin
                    Header.Clustersize := Store.Min_Storage ;
                end ;
                F := TUOS_Native_File.Create ;
                try
                    F.Store := Store ;
                    F.Header := Header ;

Some headers may be unused (either for a file that was deleted or one that was never used). If the Name is 0, it is unused and we will skip it. Otherwise, we create an instance of our file class.

                    for Stream := 0 to F.Max_Stream do
                    begin
                        Cluster := 0 ;
                        P := F.Get_Allocation_Cluster( Stream, Cluster ) ;
                        if( ( Stream = 0 ) and ( ( Header.Flags and FAF_Contiguous ) <> 0 ) ) then
                        begin
                            if( not Store.Allocate_At( P, Header.Size ) ) then
                            begin
                                // Cluster(s) already allocated.  Something has corrupted the file structure
                                Result := True ;
                            end ;
                        end else
                        while( P > 0 ) do
                        begin
                            if( not Store.Allocate_At( P, Header.Clustersize ) ) then
                            begin
                                // Cluster already allocated.  Something has corrupted the file structure
                                Result := True ;
                            end ;
                            inc( Cluster ) ;
                            P := F.Get_Allocation_Cluster( Stream, Cluster ) ;
                        end ;
                    end ;

We iterate through each possible stream in the file, since each one will have its own allocation cluster chain. We handle the special case of a contiguous file on the file data (stream 0). In that case, we simply allocate the entire data chunk in one call. In all other cases, we read through the allocation clusters until we get a cluster value of 0, which indicates the end of the allocation chain. For each cluster we then allocate it in the allocation table. We check for a failure to allocate a specific cluster and return True when we are done. We don't stop the rebuild process - just note the problem. The only way this should happen is if the some other file also pointed to the same cluster that this file points to. In theory, no file operations should be able to result in this kind of corruption of the file system structure. But we can't discount bugs. Further, a user with sufficient privileges could conceivably corrupt the structure. Or maybe someone used a stand-alone utility to modify the disk. Or maybe there is a bad spot on the disk where the data was corrupted. In any case, this should be an extremely unlikely event, but we need to check for it in any case. Being able to correct this kind of corruption is beyond the program's ability. It may even be beyond a human's ability to correct. But we'll hope for the best and the calling code can inform the user if the method returns True so they can run tools to recover the corrupted files. In fact, one of the UOS utilities that we will eventually write will help the user to do just this.

                    if( ( Header.Flags and FAF_DIRECTORY ) <> 0 ) then
                    begin
                        Process( F ) ;
                    end ;
                finally
                    F.Free ;
                end ;
            end ; // if( Header.Name <> 0 ) 
        end ; // while
    end ; // TUOS_Native_File_System.Rebuild.Process

Once we have reallocated the clusters for this file - whether or not it is a folder - we see if it is a folder (directory). If so, we recursively call ourself passing this folder. When done with this file, we free the object instance and loop back to the next header in the current folder.
When we write our disk defragmentation utility, we will be using a routine that is very close to this one. In fact, it will only differ by a handful of lines. But we will save that for later - there is a long road to travel before we get to that point.

Next we will examine the Valid_File_System method:

function TUOS_Native_File_System.Valid_File_System : boolean ;

var P : TStore_Address64 ;
    UEC : TUnified_Exception ;

begin
    // Validate that the file system structure is valid...
    Result := False ;

    Store.Get_Root( Buffer^ ) ;
    move( Buffer[ 16 ], P, 8 ) ; // Get store header address
    if( odd( P ) or ( P <= Store.Min_Storage ) ) then
    begin
        exit ;
    end ;
    Store.Read_Data( Buffer[ 0 ], P, sizeof( _Header ), UEC ) ;
    if( UEC <> nil ) then
    begin
        Set_Last_Error( UEC ) ;
        exit ;
    end ;
    move( Buffer[ 0 ], _Header, sizeof( _Header ) ) ;
    if( ( _Header.ID <> -1 ) or ( _Header.ID1 <> 135 ) or ( _Header.Version > 10 ) ) then
    begin
        exit ;
    end ;

    Result := True ;
end ;

This method checks the store header address in the root cluster. If it is an odd value or points to the first cluster, it is not a valid pointer and not a valid file system. Otherwise, we read the header that is pointed to. We then check the IDs and version in the header. If they are not valid it is not a valid file system. Otherwise we assume that everything is fine. However, it is possible that we could randomly find the values that indicate a valid file system even when there isn't one. Fortunately, the chances of random data matching our checks is very low - on the order of 1 in 2^48th.

In the next article, we will address other support methods for our file system class.