First version of Ext2_Block_Map
diff --git a/src/filo-fs-ext2.adb b/src/filo-fs-ext2.adb
index af6db70..aeff958 100644
--- a/src/filo-fs-ext2.adb
+++ b/src/filo-fs-ext2.adb
@@ -33,9 +33,6 @@
FEATURE_INCOMPAT_EXTENTS : constant := 16#0040#;
FEATURE_INCOMPAT_64BIT : constant := 16#0080#;
- -- Minimum ext2 block size is 1KiB (two 512B blocks)
- type FSBlock_Offset is new Block_Offset range 0 .. Block_Offset'Last / 2;
-
procedure Mount
(State : in out T;
Part_Len : in Partition_Length;
@@ -151,6 +148,135 @@
Blockdev.Read (Buf, Blockdev_Length (FSBlock) * Block_Size, Success);
end Read_FSBlock;
+ procedure Ext2_Block_Map
+ (State : in out T;
+ Logical : in FSBlock_Logical;
+ Physical : out FSBlock_Offset;
+ Success : out Boolean)
+ is
+ Block_Size : constant Natural := 2 ** State.Block_Size_Bits;
+ Addr_Per_Block : constant FSBlock_Logical := FSBlock_Logical (Block_Size / 4);
+ Max_Addr_Per_Block : constant FSBlock_Logical := FSBlock_Logical (2 ** Log_Block_Size'Last / 4);
+ type Addr_In_Block_Range is range 0 .. Max_Addr_Per_Block - 1;
+
+ procedure Indirect_Block_Lookup
+ (Indirect_Block_Phys : in FSBlock_Offset;
+ Addr_In_Block : in Addr_In_Block_Range;
+ Level : in Block_Cache_Index;
+ Logical_Off : in FSBlock_Logical;
+ Next_Physical : out FSBlock_Offset;
+ Success : out Boolean)
+ with
+ Pre => FSBlock_Logical (Addr_In_Block) < Addr_Per_Block
+ is
+ -- Limit cache usage in case of incredibly huge block size:
+ Cache_Level : constant Block_Cache_Index :=
+ (if State.Block_Size_Bits > 15 then Any
+ elsif State.Block_Size_Bits > 14 and Level > Any then Last_Level
+ else Level);
+ Cache_Index : constant Index_Type :=
+ Block_Cache_Index'Pos (Cache_Level) * Block_Size;
+ Cache_End : constant Index_Type := Cache_Index + Block_Size - 1;
+ begin
+ if State.Block_Cache_Index (Cache_Level) /= Logical_Off then
+ Read_FSBlock
+ (State => State,
+ Buf => State.Block_Cache (Cache_Index .. Cache_End),
+ FSBlock => Indirect_Block_Phys,
+ Success => Success);
+ State.Block_Cache_Index (Cache_Level) := Logical_Off;
+ if not Success then
+ return;
+ end if;
+ end if;
+
+ Next_Physical := FSBlock_Offset (Read_LE32
+ (Buf => State.Block_Cache (Cache_Index .. Cache_End),
+ Off => Natural (Addr_In_Block) * 4));
+ Success := True;
+ end Indirect_Block_Lookup;
+
+ Logical_Rest : FSBlock_Logical := Logical;
+ begin
+ if Logical_Rest < Direct_Blocks then
+ Physical := FSBlock_Offset (State.Direct_Blocks (Natural (Logical)));
+ Success := True;
+ return;
+ end if;
+
+ Logical_Rest := Logical_Rest - Direct_Blocks;
+ if Logical_Rest < Addr_Per_Block then
+ Indirect_Block_Lookup
+ (Indirect_Block_Phys => FSBlock_Offset (State.Indirect_Block),
+ Addr_In_Block => Addr_In_Block_Range (Logical_Rest),
+ Level => Last_Level,
+ Logical_Off => Logical - Logical_Rest,
+ Next_Physical => Physical,
+ Success => Success);
+ return;
+ end if;
+
+ Logical_Rest := Logical_Rest - Addr_Per_Block;
+ if Logical_Rest < Addr_Per_Block ** 2 then
+ Indirect_Block_Lookup
+ (Indirect_Block_Phys => FSBlock_Offset (State.Double_Indirect),
+ Addr_In_Block => Addr_In_Block_Range (Logical_Rest / Addr_Per_Block),
+ Level => Second_Last_Level,
+ Logical_Off => Logical - Logical_Rest,
+ Next_Physical => Physical,
+ Success => Success);
+ if not Success then
+ return;
+ end if;
+
+ Indirect_Block_Lookup
+ (Indirect_Block_Phys => Physical,
+ Addr_In_Block => Addr_In_Block_Range (Logical_Rest mod Addr_Per_Block),
+ Level => Last_Level,
+ Logical_Off => Logical - (Logical_Rest mod Addr_Per_Block),
+ Next_Physical => Physical,
+ Success => Success);
+ return;
+ end if;
+
+ Logical_Rest := Logical_Rest - Addr_Per_Block ** 2;
+ if Logical_Rest < Addr_Per_Block ** 3 then
+ Indirect_Block_Lookup
+ (Indirect_Block_Phys => FSBlock_Offset (State.Triple_Indirect),
+ Addr_In_Block => Addr_In_Block_Range (Logical_Rest / Addr_Per_Block ** 2),
+ Level => First_Level,
+ Logical_Off => Logical - Logical_Rest,
+ Next_Physical => Physical,
+ Success => Success);
+ if not Success then
+ return;
+ end if;
+
+ Indirect_Block_Lookup
+ (Indirect_Block_Phys => Physical,
+ Addr_In_Block => Addr_In_Block_Range (Logical_Rest / Addr_Per_Block mod Addr_Per_Block),
+ Level => Second_Last_Level,
+ Logical_Off => Logical - (Logical_Rest mod Addr_Per_Block ** 2),
+ Next_Physical => Physical,
+ Success => Success);
+ if not Success then
+ return;
+ end if;
+
+ Indirect_Block_Lookup
+ (Indirect_Block_Phys => Physical,
+ Addr_In_Block => Addr_In_Block_Range (Logical_Rest mod Addr_Per_Block),
+ Level => Last_Level,
+ Logical_Off => Logical - (Logical_Rest mod Addr_Per_Block),
+ Next_Physical => Physical,
+ Success => Success);
+ return;
+ end if;
+
+ -- Logical address was just too high.
+ Success := False;
+ end Ext2_Block_Map;
+
procedure Open
(State : in out T;
File_Len : out File_Length;
diff --git a/src/filo-fs-ext2.ads b/src/filo-fs-ext2.ads
index b26b103..96bd102 100644
--- a/src/filo-fs-ext2.ads
+++ b/src/filo-fs-ext2.ads
@@ -44,6 +44,25 @@
-- maximum block size is 64KiB (2^16):
subtype Log_Block_Size is Positive range 10 .. 16;
+ subtype Max_Block_Index is Index_Type range 0 .. 2 ** Log_Block_Size'Last - 1;
+
+ -- Minimum ext2 block size is 1KiB (two 512B blocks)
+ type FSBlock_Offset is new Block_Offset range 0 .. Block_Offset'Last / 2;
+ type FSBlock_Logical is new Block_Offset range 0 .. Block_Offset'Last / 2;
+
+ -- We use a 64KiB cache.
+ -- * If that's the block size, only the `Any` entry is used.
+ -- * For a 32KiB block size, `Any` and `Last_Level` (for indirect block
+ -- lookups) are used.
+ -- * For smaller block sizes, the most common case, we cache four blocks.
+ -- For the `Any` entry, we note the logical block address (block offset
+ -- within a file). For the indirect entries, we note the *first* logical
+ -- block that they map.
+ type Block_Cache_Index is (Any, Last_Level, Second_Last_Level, First_Level);
+ type Block_Cache_Type is array (Block_Cache_Index) of FSBlock_Logical;
+
+ Direct_Blocks : constant := 12;
+ type Direct_Blocks_Array is array (Natural range 0 .. Direct_Blocks - 1) of Unsigned_32;
subtype Inode_Size is Positive range 128 .. Positive (Unsigned_16'Last);
subtype Desc_Size is Positive range 32 .. Positive (Unsigned_16'Last);
@@ -58,6 +77,12 @@
Desc_Size : Ext2.Desc_Size := Ext2.Desc_Size'First;
Feature_Extents : Boolean := False;
Feature_64Bit : Boolean := False;
+ Direct_Blocks : Direct_Blocks_Array := (others => 0);
+ Indirect_Block : Unsigned_32 := 0;
+ Double_Indirect : Unsigned_32 := 0;
+ Triple_Indirect : Unsigned_32 := 0;
+ Block_Cache_Index : Block_Cache_Type := (others => 0);
+ Block_Cache : Buffer_Type (Max_Block_Index) := (others => 16#00#);
end record;
end FILO.FS.Ext2;