Allocation Table

In the previous article, we described the UOS Managed Store. That class uses an allocation table class, which we'll examine here. Here is the abstract class definition:

type TCOM_Allocator64 = class( TBase_Delphi_Object )
                           public { API... }
                               function Get_Offset : TStore_Address64 ;
                                   virtual ; abstract ;
                               function Get_Resolution : cardinal ;
                                   virtual ; abstract ;
                               function Get_Size : cardinal ; virtual ;
                                   abstract ;
                               function Get_Store : TCOM_Store64 ; virtual ;
                                   abstract ;

                               procedure Set_Offset( Value : TStore_Address64 ) ;
                                   virtual ; abstract ;
                               procedure Set_Resolution( Value : cardinal ) ;
                                   virtual ; abstract ;
                               procedure Set_Size( Value : cardinal ) ;
                                   virtual ; abstract ;
                               procedure Set_Store( Value : TCOM_Store64 ) ;
                                   virtual ; abstract ;

                           public { API... }
                               procedure Flush ; virtual ;
                                   abstract ;
                               function Allocate( Size : TStore_Address64 ) : TStore_Address64 ;
                                   virtual ; abstract ;
                               function Allocate_At( Pos, Size : TStore_Address64 ) : boolean ;
                                   virtual ; abstract ;
                               procedure Deallocate( PTR : TStore_Address64 ;
                                   Size : TStore_Address64 ) ; virtual ;
                                   abstract ;
                               procedure Load_Table ; virtual ; abstract ;
                               function MaxSpace : TStore_Size64 ; virtual ; abstract ;
                               function SpaceAvail : TStore_Size64 ; virtual ; abstract ;
                               function Get_Data : pointer ; virtual ; abstract ;
                               procedure Set_Data( Value : pointer ;
                                   Size : cardinal ) ; virtual ; abstract ;
                       end ; { TCOM_Allocator64 }

And here is the definition for our allocation table class:

     TAT64 = class( TCOM_Allocator64 )
               public { Constructors and destructors... }
                   constructor Create( _Resolution : cardinal ) ;
                   destructor Destroy ; override ;

               private { Instance data... }
                   _AT : pByte_Array ; // Allocation table image
                   Byte_Mapping : cardinal ; 
		   // How much storage is mapped by one byte (8*Resolution)
                   _Offset : TStore_Address64 ; { AT offset in store }
                   _Size : cardinal ; { AT size, in bytes }
                   _Store : TCOM_Store64 ; { Store where table is saved }
                   Lowest_Free_Space : TStore_Address64 ; { Address of lowest unallocated space }
                   Modified : boolean ; { True if unsaved modifications }
                   Resolution : cardinal ; { How many bytes each bit represents }

               private { Internal utility routines... }
                   function AT : pByte_Array ;

               public { API... }
                   function Get_Modified : boolean ; virtual ;
                   function Get_Offset : TStore_Address64 ; override ;
                   function Get_Resolution : cardinal ; override ;
                   function Get_Size : cardinal ; override ;
                   function Get_Store : TCOM_Store64 ; override ;

                   procedure Set_Modified( Value : boolean ) ; virtual ;
                   procedure Set_Offset( Value : TStore_Address64 ) ; override ;
                   procedure Set_Resolution( Value : cardinal ) ; override ;
                   procedure Set_Size( Value : cardinal ) ; override ;
                   procedure Set_Store( Value : TCOM_Store64 ) ; override ;

               public { API... }
                   procedure Flush ; override ; { Write AT changes to store }
                   function Allocate( Size : TStore_Address64 ) : TStore_Address64 ;
                       override ;
                   function Allocate_At( Pos, Size : TStore_Address64 ) : boolean ;
                       override ;
                   procedure Deallocate( PTR : TStore_Address64 ;
                       Size : TStore_Size64 ) ; override ;
                   function Debugger : TDebug_Interface ; override ;
                   procedure Load_Table ; override ;
                   function MaxSpace : TStore_Size64 ; override ;
		           function SpaceAvail : TStore_Size64 ; override ;
                   function Get_Data : pointer ; override ;
                   procedure Set_Data( Value : pointer ; Size : cardinal ) ;
                       override ;
           end ; { TAT64 }

Essentially, the class does nothing more than manage an array of bits. In all cases of manipulating the bits, we have to map from a byte address on the store into a byte offset and bit(s) within the allocation table. The comments on the instance data explain what they are used for. Here are our constructors, destructors, getters, and setters.

constructor TAT64.Create( _Resolution : cardinal ) ;

begin
    inherited Create ;

    Resolution := _Resolution ;
    Byte_Mapping := 8 * Resolution ; { How much one AT byte maps }
end ;


destructor TAT64.Destroy ;

begin
    Flush ; { Update store }
    Set_Size( 0 ) ; { Clear cache }

    inherited Destroy ;
end ;


function TAT64.Get_Modified : boolean ;

begin
    Get_Modified := Modified ;
end ;


function TAT64.Get_Offset : TStore_Address64 ;

begin
    Get_Offset := _Offset ;
end ;


function TAT64.Get_Resolution : cardinal ;

begin
    Get_Resolution := Resolution ;
end ;


function TAT64.Get_Size : cardinal ;

begin
    Get_Size := _Size ;
end ;


function TAT64.Get_Store : TCOM_Store64 ;

begin
    Get_Store := _Store ;
end ;


procedure TAT64.Set_Modified( Value : boolean ) ;

begin
    Modified := Value ;
end ;


procedure TAT64.Set_Offset( Value : TStore_Address64 ) ;

begin
    if( _Offset <> Value ) then
    begin
        _Offset := Value ;
    end ;
end ;


procedure TAT64.Set_Resolution( Value : cardinal ) ;

begin
    if( Value <> Resolution ) then
    begin
        Resolution := Value ;
    end ;
end ;


procedure TAT64.Set_Size( Value : cardinal ) ;

begin
    if( _Size <> Value ) then
    begin
        if( _AT <> nil ) then
        begin
            reallocmem( pointer( _AT ), _Size, Value ) ;
        end ;
        _Size := Value ;
    end ;
end ; { TAT64.Set_Size }


procedure TAT64.Set_Store( Value : TCOM_Store64 ) ;

var C : int64 ;

begin
    if( Value <> nil ) then
    begin
        Value.Attach ;
        if( Resolution < Value.Min_Storage ) then
        begin
            Resolution := Value.Min_Storage ;
        end ;
        C := Value.Max_Storage div Resolution ; // Total clusters on store
        _Size := C div 8 ; // Size of AT
        Byte_Mapping := 8 * Resolution ; { How much one AT byte maps }
    end ;
    if( _Store <> nil ) then
    begin
        _Store.Detach ;
    end ;
    _Store := Value ;
end ;

In the case of the size being set, we make sure to reallocate the AT buffer so it is the correct size. When the store is set, we recalculate the AT size. In general, we will call either Set_Size or Set_Store, but not both.

Our internal utility routine allows us to delay the allocation of the Allocation Table buffer (AT) until we need to access it.

function TAT64.AT : pByte_Array ;

begin
    if( _AT = nil ) then
    begin
        _AT := Allocmem( _Size ) ;
        fillchar( _AT^, _Size, 0 ) ;
        _AT^[ 0 ] := 1 ; // Lowest cluster is always allocated
        Lowest_Free_Space := Resolution ;
    end ;
    Result := _AT ;
end ;

Now to the meat of the class:

procedure TAT64.Flush ; { Write AT changes to store }

var UEC : TUnified_Exception ;

begin
    if( ( _Offset <> 0 ) and ( _Store <> nil ) and Modified ) then
    begin
        _Store.Write_Data( AT^, _Offset, _Size, UEC ) ;
        Set_Last_Error( UEC ) ;
        Modified := False ;
    end ;
end ; { TAT64.Flush }

We don't write the allocation table to the store until explicitly requested to, so this method isn't called within our class. The one exception is in the destructor, where we do call Flush. If the calling code doesn't want the table written, it should set the offset to 0 before destructing the class.

procedure TAT64.Load_Table ; { Load from store }

var Dummy : TRecord_Size ;
    P : TStore_Address ;
    U_E : TUnified_Exception ;

begin
    if( ( _Store <> nil ) and ( _Size > 0 ) ) then
    begin
        P := _Offset ;
        Dummy := _Store.Read_Data( AT^, P, _Size, U_E ) ;
        if( Dummy <> _Size ) then
        begin
            Set_Last_Error( Create_Exception( AT_Error_Load_Failure, _Store.Last_Error ) ) ;
            exit ;
        end ;
        Modified := False ;
    end ;
end ;

Load_Table reads the allocation table in from the store - the inverse of Flush.

Let's look at the allocation methods, whose purpose is to locate free space, mark it as used, and then return the address of the newly allocated area.

function TAT64.Allocate( Size : TStore_Address64 ) : TStore_Address64 ;
{ Allocate Size bytes and return pointer.  Return 0 if error. }

var AT_Byte, AT_Bit : integer ; { Current byte and bit within AT }
    Counter : TStore_Size64 ;
    Offset : TStore_Address64 ;
    Offset_Byte, Offset_Bit : cardinal ;

    procedure Set_Start ;

    begin
        Offset := AT_Byte ; { Allocation table byte offset }
        Offset := Offset * Byte_Mapping + AT_Bit * Resolution ; { Remember start }
        Offset_Byte := AT_Byte ;
        Offset_Bit := AT_Bit ;
    end ;

begin
    Allocate := 0 ; { Return zero (0) if error }
    if( Size < 1 ) then { Cannot allocate nothing, or less than nothing }
    begin
        exit ;
    end ;
    Size := ( Size + Resolution - 1 ) and ( not ( Resolution - 1 ) ) ;
    { Allocate minimum multiple bytes at a time }
    AT_Byte := Lowest_Free_Space div Byte_Mapping ;
    if( AT_Byte + ( ( Size div Resolution + 7 ) div 8 ) > _Size ) then // More space than we have
    begin
        exit ;
    end ;

    { Find a place where we can allocate the requested space... }
    Offset := 0 ; { So we know if allocation failed }
    { Start at the beginning }

    AT_Bit := 0 ;
    Counter := 0 ; { Number of bytes available in current segment }
    while( Counter < Size ) do { Find necessary free space }
    begin
        if( AT^[ AT_Byte ] = 255 ) then { No room in entire byte }
        begin
            Counter := 0 ;
            AT_Bit := 7 ; { Skip rest of bits in this byte }
        end else
        begin
            if(
                ( AT_Bit = 0 )
                and
                ( Size - Counter >= Byte_Mapping )
                and
                ( AT^[ AT_Byte ] = 0 )
              ) then
            begin { Quick check for entire byte }
                if( Counter = 0 ) then
                begin
                    Set_Start ;
                end ;
                Counter := Counter + Byte_Mapping ;
                AT_Bit := 7 ;
                if( Counter >= Size ) then
                begin
                    break ;
                end ;
            end else
            begin { Check bit by bit }
                if( ( AT^[ AT_Byte ] and Bit_Values[ AT_Bit ] ) = 0 ) then
                begin
                    if( Counter = 0 ) then { New/first free block }
                    begin
                        Set_Start ;
                    end ;
                    Counter := Counter + Resolution ; { Count up free bytes }
                    if( Counter >= Size ) then
                    begin
                        break ;
                    end ;
                end else { Ran out of free blocks before we found sufficient space }
                begin
                    Counter := 0 ; { Start over }
                end ;
            end ;
        end ;
        inc( AT_Bit ) ; { Check next bit of current byte }
        if( AT_Bit > 7 ) then { Ran out of bits on this byte }
        begin
            AT_Bit := 0 ; { Start at first bit of next byte }
            inc( AT_Byte ) ; { Move to next byte }
            if( AT_Byte >= _Size ) then { AT was not big enough }
            begin
                exit ;
            end ; { if( AT_Byte > Segment_Size ) }
        end ; { if( AT_Bit > 7 ) }
    end ; { while( Counter > _Size ) }

    { Now mark space as allocated in AT... }
    AT_Byte := Offset_Byte ;
    AT_Bit := Offset_Bit ;
    while( Counter > 0 ) do
    begin
        Modified := True ;
        if( ( AT_Bit = 0 ) and ( Counter >= Byte_Mapping ) ) then
        begin { Quick check for entire byte }
            AT^[ AT_Byte ] := 255 ;
            Counter := Counter - Byte_Mapping ;
            AT_Bit := 7 ;
            if( Counter <= 0 ) then
            begin
                break ;
            end ;
        end else
        begin
            AT^[ AT_Byte ] := AT^[ AT_Byte ] or Bit_Values[ AT_Bit ] ; { Mark as used }
            Counter := Counter - Resolution ;
        end ;
        inc( AT_Bit ) ; { Check next bit of current byte }
        if( AT_Bit > 7 ) then { Ran out of bits on this byte } if( Counter > 0 ) then
        { ...and not yet finished }
        begin
            AT_Bit := 0 ; { Start at first bit... }
            inc( AT_Byte ) ; {...of next byte}
        end ; { if( AT_Bit > 7 ) }
    end ; { while Counter > 0 }
    Modified := True ;
    Allocate := Offset ; { Return offset of allocation }
    if( Offset <> 0 ) then
    begin
        if( Offset = Lowest_Free_Space ) then
        begin
            Lowest_Free_Space := Lowest_Free_Space + Size ;
        end ;
    end ;
end ; { TAT64.Allocate }

The first step of the routine is to find an area of contiguous unset bits in the allocation table that match, or exceed, the requested size. Once located, we then set the corresponding bits. This algorithm will locate the first area that is large enough for the requested size. In some algorithms the process is to find the smallest area that is largest enough to fit the request. This approach would result in less fragmented space, but is more complex code with slightly less performance. Since we will be writing a disk defragmentor to optimize the file system structure, we can dispense with the extra complexity here and allow the defragmentor to reduce the fragmentation on the store.

function TAT64.Allocate_At( Pos, Size : TStore_Address64 ) : boolean ;

var AT_Byte, AT_Bit : longint ; { Current byte and bit within AT }
    Counter : TStore_Size64 ;

begin
    Allocate_At := False ; { Return false if error }
    if( ( Size < 1 ) or ( Pos < 1 ) ) then
    begin
        exit ; { Cannot allocate nothing, or at an invalid position }
    end ;
    Size := ( Size + Resolution - 1 ) and ( not ( Resolution - 1 ) ) ;
    { Allocate minimum multiple bytes at a time }

    AT_Byte := Pos div Byte_Mapping ;
    if( AT_Byte >= _Size ) then // Not enough room
    begin
        exit ;
    end ;
    AT_Bit := ( Pos - ( AT_Byte * Byte_Mapping ) ) div Resolution ;
    Counter := 0 ; { Number of bytes available in current segment }
    while( Counter < Size ) do { Check for necessary free space }
    begin
        if(
            ( AT_Bit = 0 )
            and
            ( Size - Counter >= Byte_Mapping )
            and
            ( AT^[ AT_Byte ] = 0 )
          ) then
        begin { Quick check for entire byte }
            Counter := Counter + Byte_Mapping ;
            AT_Bit := 7 ;
            if( Counter >= Size ) then
            begin
                break ;
            end ;
        end else
        begin { Check bit by bit }
            if( ( AT^[ AT_Byte ] and Bit_Values[ AT_Bit ] ) = 0 ) then
            begin
                Counter := Counter + Resolution ; { Count up free bytes }
                if( Counter >= Size ) then
                begin
                    break ;
                end ;
            end else
            begin
                exit ; { Insufficient space at location }
            end ;
        end ;
        inc( AT_Bit ) ; { Check next bit of current byte }
        if( AT_Bit > 7 ) then { Ran out of bits on this byte }
        begin
            AT_Bit := 0 ; { Start at first bit of next byte }
            inc( AT_Byte ) ; { Move to next byte }
        end ; { if( AT_Bit > 7 ) }
    end ; { while( Counter > _Size ) }

    { Now mark space as allocated in AT... }
    AT_Byte := Pos div Byte_Mapping ;
    AT_Bit := ( Pos - ( AT_Byte * Byte_Mapping ) ) div Resolution ;
    while( Counter > 0 ) do
    begin
        Modified := True ;
        if( ( AT_Bit = 0 ) and ( Counter >= Byte_Mapping ) ) then
        begin { Quick check for entire byte }
            AT^[ AT_Byte ] := 255 ;
            Counter := Counter - Byte_Mapping ;
            AT_Bit := 7 ;
            if( Counter <= 0 ) then
            begin
                break ;
            end ;
        end else
        begin
            AT^[ AT_Byte ] := AT^[ AT_Byte ] or Bit_Values[ AT_Bit ] ; { Mark as used }
            Counter := Counter - Resolution ;
        end ;
        inc( AT_Bit ) ; { Check next bit of current byte }
        if( AT_Bit > 7 ) then { Ran out of bits on this byte } if( Counter > 0 ) then
        { ...and not yet finished }
        begin
            AT_Bit := 0 ; { Start at first bit... }
            inc( AT_Byte ) ; {...of next byte}
        end ; { if( AT_Bit > 7 ) }
    end ; { while Counter > 0 }
    Modified := True ;
    Allocate_At := True ; { Success }
    if( Pos = Lowest_Free_Space ) then
    begin
        Lowest_Free_Space := Lowest_Free_Space + Size ;
    end ;
end ; { TAT64.Allocate_At }

Allocate_At allows us to request an allocation at a specific location on the store, rather than where ever the Allocate decides. This is used to place heavily used files at locations on disks that will minimize the amount of disk head movement. Allocate_At essentially works the same as Allocate, but starts looking at the requested position. If the requested space is not available at the requested position, the function exits with a result of False. Otherwise, the bits are set and True is returned.

procedure TAT64.Deallocate( PTR : TStore_Address64 ; Size : TStore_Address64 ) ;

var AT_Byte, AT_Bit : longint ;

begin
    if( ( Size < 1 ) or ( PTR < Resolution ) ) then
    begin
        exit ;
    end ;
    Size := ( Size + Resolution - 1 ) and ( not ( Resolution - 1 ) ) ;
    { Deallocate minimum multiple bytes at a time }

    if( Lowest_Free_Space > PTR ) then
    begin
        Lowest_Free_Space := PTR ;
    end ;

    AT_Byte := PTR div Byte_Mapping ;
    PTR := PTR - AT_Byte * Byte_Mapping ;
    AT_Bit := PTR div Resolution ;
    while( Size > 0 ) do
    begin
        if( ( AT_Bit = 0 ) and ( Size >= Byte_Mapping ) ) then
        begin
            AT_Bit := 7 ;
            AT^[ AT_Byte ] := 0 ;
            Size := Size - Byte_Mapping ;
        end else
        begin
            AT^[ AT_Byte ] := AT^[ AT_Byte ] and ( not Bit_Values[ AT_Bit ] ) ;
            Size := Size - Resolution ;
        end ;

        if( Size > 0 ) then
        begin
            inc( AT_Bit ) ;
            if( AT_Bit > 7 ) then
            begin
                AT_Bit := 0 ; { Move to first bit... }
                inc( AT_Byte ) ; { ...of next byte }
                if( AT_Byte = _Size ) then
                begin
                    Modified := True ;
                    Size := 0 ; { Done if at end of AT }
                end ;
            end ; { if AT_Bit > 7 }
        end ; { if _Size > 0 }
    end ; { while _Size > 0 }
    Modified := True ;
end ; { TAT64.Deallocate }

The Deallocate routine works similarly to the Allocate routine, but sets the AT bits to 0 - and no searching for contiguous space is required. It is possible, with this routine, to deallocate space that wasn't allocated in the first place. This is not an error, per se, although it may indicate an error in the code that calls the method. Since nothing is harmed by this we don't bother to check for the condition. Deallocating the allocation table itself may cause problems, but we don't try to prevent it since it could be part of a valid process - such as moving the allocation table to a different part of the store. Basically, if the calling code is buggy, we can't do much about it here.

function TAT64.MaxSpace : TStore_Size64 ; { Return largest contiguous space }

var AT_Byte, AT_Bit : integer ; { Current byte and bit within AT }
    Counter, Max : TStore_Size64 ;

begin
    Result := 0 ;
    AT_Byte := Lowest_Free_Space div Byte_Mapping ;
    if( AT_Byte >= _Size ) then
    begin
        exit ;
    end ;
    AT_Bit := 0 ;
    Counter := 0 ; { Number of bytes available in current segment }
    Max := 0 ; { Maximum space found }
    while( AT_Bit <= 7 ) do { Find free space }
    begin
        if( ( AT_Bit = 0 ) and ( AT^[ AT_Byte ] = 0 ) ) then
        begin
            Counter := Counter + Byte_Mapping ;
            AT_Bit := 7 ;
        end else
        if( ( AT^[ AT_Byte ] and Bit_Values[ AT_Bit ] ) = 0 ) then
        begin
            Counter := Counter + Resolution ; { Count up free bytes }
        end else
        begin { Ran out of free blocks }
            if( Counter > Max ) then
            begin
                Max := Counter ;
            end ;
            Counter := 0 ; { Start over }
        end ;
        inc( AT_Bit ) ; { Check next bit of current byte }
        if( AT_Bit > 7 ) then { Ran out of bits on this byte }
        begin
            AT_Bit := 0 ; { Start at first bit of next byte }
            inc( AT_Byte ) ; { Move to next byte }
            if( AT_Byte >= _Size ) then { AT was not big enough }
            begin
                AT_Bit := 8 ; { Terminate loop }
                if( Counter > Max ) then
                begin
                    Max := Counter ;
                end ;
            end ; { if AT_Byte >= AT_Segment_Size }
        end ; { if AT_Bit > 7 }
    end ; { while AT_Bit <= 7 }
    MaxSpace := Max ;
end ; { TAT64.MaxSpace }


function TAT64.SpaceAvail : TStore_Size64 ;
{ Return available space within table }

var AT_Byte, AT_Bit : integer ; { Current byte and bit within AT }
    Counter : longint ;

begin
    Result := 0 ;
    AT_Byte := Lowest_Free_Space div Byte_Mapping ;
    if( AT_Byte >= _Size ) then
    begin
        exit ;
    end ;
    AT_Bit := 0 ;
    Counter := 0 ; { Number of bytes available in current segment }
    while( AT_Bit <= 7 ) do { Find free space }
    begin
        if( ( AT_Bit = 0 ) and ( AT^[ AT_Byte ] = 0 ) ) then // Whole byte is free
        begin
            Counter := Counter + Byte_Mapping ;
            AT_Bit := 8 ;
        end else
        begin
            if( ( AT^[ AT_Byte ] and Bit_Values[ AT_Bit ] ) = 0 ) then
            begin
                Counter := Counter + Resolution ; { Count up free bytes }
            end ;
            inc( AT_Bit ) ; { Check next bit of current byte }
        end ;
        if( AT_Bit > 7 ) then { Ran out of bits on this byte }
        begin
            AT_Bit := 0 ; { Start at first bit of next byte }
            inc( AT_Byte ) ; { Move to next byte }
            if( AT_Byte >= _Size ) then { AT was not big enough }
            begin
                AT_Bit := 8 ; { Terminate loop }
            end ;
        end ;
    end ;
    SpaceAvail := Counter ;
end ; { TAT64.SpaceAvail }

MaxSpace and SpaceAvail read the unset bits in the allocation table, add up the space and return it. The difference is that MaxSpace locates the largest contiguous set of unset bits, whereas SpaceAvail returns the total unallocated space.

function TAT64.Get_Data : pointer ;

begin
    Result := AT ;
end ;


procedure TAT64.Set_Data( Value : pointer ; Size : cardinal ) ;

var P : pointer ;

begin
    if( _Size < Size ) then
    begin
        P := AT ;
        reallocmem( P, Size, _Size ) ;
        _AT := P ;
        _Size := Size ;
    end ;
    move( Value^, AT^, Size ) ;
end ;

The final methods allow direct access to the allocation table data. This is to allow the file system to rebuild the on-store structure when needed.

In the next article, we will address some other classes that our file system will need.