APFS: Data Recovery Algorithm and File System Structure

ApFS offers an opportunity to restore certain states of the file system, including restoration of old or removed versions of files.. The container superblock contains a link to the element known as checkpoint. Such checkpoint refers to the preceding container superblock which stores the information on an older state of the file system.This way, several older states can be restored by analyzing the chain of the container superblock.

Containers and volumes

The structure of ApFS file system is that of a B-tree, where the root directory containing data is the leaves of such tree. All branch nodes only contain links to the following node until they reach the leaf nodes. This file system uses containers as storage cells, and such cells can contain multiple ApFS volumes. Also, a container is the primary object for storing data. To contain one volume, it should be > 512 Mb, at least > 1024Mb is required to contain more than 2 volumes and so on.

The image below shows an overview of ApFS structure.

Each element of this structure (except for the allocation file) starts with a 32-byte block header, which contains some general information about the block. The element that follows it is the body of the file system. It is composed of the following parts:

• 0x01: Container Superblock
• 0x02: Node
• 0x05: Space manager
• 0x07: Allocation Info File
• 0x0C: Checkpoint
• 0x0D: Volume Superblock

Containers are usually exactly the same as the GUID Partition Table (GPT) entries. They have their own crash protection and disk space allocation scheme. Each container contains one or more volumes or file systems, each of which has its own namespace, and a set of files and directories.

Although ApFS does not directly support software RAID, but it can be used with Apple RAID volumes to support Striping (RAID 0), Mirroring (RAID 1), and Concatenation (JBOD).

With a 64-bit index, ApFS volumes will support up to 9 quintillion (1018) files.

The new file system uses nanoseconds to set timestamps. In HFS+, timestamps were set to the nearest second. This will reduce the number of failures in data transfer and other file operations.

ApFS has a built-in encryption system and uses AES-XTS or AES-CBC systems, depending on the device. You can use several encryption keys to ensure data security even in the case of ”physical compromise” of the medium.

This is far from being a complete list of the innovations that ApFS can boast .

Partitions formatted in ApFS are not recognized by OS X 10.11 Yosemite and earlier versions of the operating system.

Block Header

Each element of the file system structure in ApFS starts with a block header. This header starts with a checksum. Other information in the header includes the copy-on-write version of the block, the block identifier (id) and the block type.

From the table, we can see that 1uint = 1 bit, 8 bit = 1 byte, hence uint64 = 8, uint32 = 4, and uint16 = 2 bytes.

Container Superblock

The CS (Container Superblock) is the entry point to the file system. Because of the file system structure with containers and flexible volumes, allocation needs to be processed at the container level. The Container Superblock contains information on the block size, the number of blocks and pointers for this task in the space manager. In addition, the block identifiers (IDs) of all volumes are stored in the superblock. To map block IDs to block offsets a pointer to a B-tree block map is saved. This B-tree contains entries for each volume with its ID and offset. The Container Superblock is the highest level in the file system.

Types defined:

• uint8 tApFS_Uuid;
• uint64 tApFS_Ident;
• uint64 tApFS_Transaction;
• int64 tApFS_Address;
• uint64 tApFS_BTreeKey;

        struct tApFS_BlockRange
        {
        tApFS_AddressFirst;// First block
        uint64Count;// Number of blocks
        }

        struct tApFS_COH
        {
        uint64CheckSum;// Block checksum
        tApFS_IdentIdent;// Identifier
        tApFS_TransactionTransaction;// Object change transaction number
        uint16Type;// Object type
        uint16Flags;// Object flags
        uint32SubType;// Object subtype
        };

with list of object types:

        enumeApFS_ObjectType
        {
        eApFS_ObjectType_01_SuperBlock=0x0001,//Containersuperblockа
        eApFS_ObjectType_02_BTreeRoot=0x0002,//B-Tree:rootnode
        eApFS_ObjectType_03_BTreeNode=0x0003,//B-Tree:non-root node
        eApFS_ObjectType_05_SpaceManager=0x0005,//Spacemanager
        eApFS_ObjectType_06_SpaceManagerCAB=0x0006,//Spacemanager:segments’addresses
        eApFS_ObjectType_07_SpaceManagerCIB=0x0007,//Spacemanager:segments’information
        eApFS_ObjectType_08_SpaceManagerBitmap=0x0008,//Freeсspacebitmapused bySpacemanager
        eApFS_ObjectType_09_SpaceManagerFreeQueue=0x0009,//Freespaceused bySpacemanager_(keys-_tApFS_09_SpaceManagerFreeQueue_Key_,values-_tApFS_09_SpaceManagerFreeQueue_Value_)
        eApFS_ObjectType_0A_ExtentListTree=0x000A,//Extents’listtree(keys–offsetbeginningextent_tApFS_Address_,value–physicaldatalocation_tApFS_BlockRange_)
        eApFS_ObjectType_0B_ObjectsMap=0x000B,//Type–Objectsmap;subType–Objectmaprecordtree(keys-_tApFS_0B_ObjectsMap_Key_,values-_tApFS_0B_ObjectsMap_Value_)
        eApFS_ObjectType_0C_CheckPointMap=0x000C,//Checkpointmap
        eApFS_ObjectType_0D_FileSystem=0x000D,//Volumefilesystem
        eApFS_ObjectType_0E_FileSystemTree=0x000E,//Filesystemtree(keysstart fromс_tApFS_BTreeKey_,describeskeytypeandvalue)
        eApFS_ObjectType_0F_BlockReferenceTree=0x000F,//Blockreferencetree(keys-_tApFS_BTreeKey_,values-_tApFS_0F_BlockReferenceTree_Value_)
        eApFS_ObjectType_10_SnapshotMetaTree=0x0010,//Snapshot metatree(keys-_tApFS_BTreeKey_,values-_tApFS_10_SnapshotMetaTree_Value_)
        eApFS_ObjectType_11_Reaper=0x0011,//Reaper
        eApFS_ObjectType_12_ReaperList=0x0012,//ReaperList
        eApFS_ObjectType_13_ObjectsMapSnapshot=0x0013,//Objectsmapsnapshottree(keys-_tApFS_Transaction_,values-_tApFS_13_ObjectsMapSnapshot_Value_)
        eApFS_ObjectType_14_JumpStartEFI=0x0014,//EFILoader
        eApFS_ObjectType_15_FusionMiddleTree=0x0015,//FusiondevicestreetotrackSSDcachedHDD,blocks(keys-_tApFS_Address_,values-_tApFS_15_FusionMiddleTree_Value_)
        eApFS_ObjectType_16_FusionWriteBack=0x0016,//Fusiondeviceswritebackcachestatus
        eApFS_ObjectType_17_FusionWriteBackList=0x0017,//Fusiondeviceswritebackcachelist
        eApFS_ObjectType_18_EncryptionState=0x0018,//Encryption
        eApFS_ObjectType_19_GeneralBitmap=0x0019,//GeneralBitmap
        eApFS_ObjectType_1A_GeneralBitmapTree=0x001A,//GeneralBitmapTree(keys-uint64,keys-uint64)
        eApFS_ObjectType_1B_GeneralBitmapBlock=0x001B,//GeneralBitmapBlock
        eApFS_ObjectType_00_Invalid=0x0000,//Non-validasa typeorabsentsubtype
        eApFS_ObjectType_FF_Test=0x00FF//Reservedfortesting(neverstoredonmedia)
        eApFS_ObjectType_FF_Test=0x00FF//Reservedfortesting(neverstoredonmedia)
        };

        enumeApFS_ObjectFlag
        {
        eApFS_ObjectFlag_Virtual=0x0000,//Virtualobject
        eApFS_ObjectFlag_Ephemeral=0x8000,//Ephemeralobject
        eApFS_ObjectFlag_Physical=0x4000,//Physicalobject
        eApFS_ObjectFlag_NoHeader=0x2000,//Objectwithno header_tApFS_ContainerObjectHeader_(for example,Space(bitmap)managerbitmap)
        eApFS_ObjectFlag_Encrypted=0x1000,//Encryptedobject
        eApFS_ObjectFlag_NonPersistent=0x0800,//Objectwiththisflagisneversavedonmedia
        eApFS_ObjectFlag_StorageTypeMask=0xC000,//Bitmask(bitmask)forдляaccessingкobjectcategoryflags
        eApFS_ObjectFlag_ValidMask=0xF800//Validflagbitmask
        };

        structtApFS_0B_ObjectsMap_Key
        {
        tApFS_IdentObjectIdent;//Objectidentifier
        tApFS_TransactionTransaction;//Transactionnumber
        };

        structtApFS_0B_ObjectsMap_Value
        {
        uint32Flags;//Flags
        uint32Size;//Objectsizeinbytes(multipleof containerруblocksize)
        tApFS_AddressAddress;//Objectaddress
        };

        structtApFS_09_SpaceManagerFreeQueue_Key
        {
        tApFS_Transactionsfqk_xid;
        tApFS_Addresssfqk_paddr;
        };

        structtApFS_09_SpaceManagerFreeQueue_Value
        {
        uint64sfq_count;
        tApFS_Identsfq_tree_oid;
        tApFS_Transactionsfq_oldest_xid;
        uint16sfq_tree_node_limit;
        uint16sfq_pad16;
        uint32sfq_pad32;
        uint64sfq_reserved;
        };

        structtApFS_10_SnapshotMetaTree_Value
        {
        tApFS_IdentExtentRefIdent;//Identifier of B-Treephysicalobject,thatstorestheextentinformation
        tApFS_IdentSuperBlockIdent;//Superblockidentifier
        uint64CreatedTime;//Snapshotcreationtime(innanosecondsfrommidnight01/01/1970)
        uint64LastModifiedTime;//Snapshotlastmodified time(innanosecondsfrommidnight01/01/1970)
        uint64iNum;
        uint32ExtentRefTreeType;//Type ofB-tree,thatstoresextentinformation
        uint16NameLength;//Snapshotnamelength(includingendofline character)
        uint8Name[];//Snapshotname(endingwith0)
        };

        structtApFS_13_ObjectsMapSnapshot_Value
        {
        uint32Flags;//Snapshotflags
        uint32Padding;//Reserved(foradjustment)
        tApFS_IdentReserved;//Reserved
        };

        structtApFS_15_FusionMiddleTree_Value
        {
        tApFS_Addressfmv_lba;
        uint32fmv_length;
        uint32fmv_flags;
        };  

An example of ApFS structure:

Volume Superblock

The Volume Superblock exists for each volume within the file system. It contains the volume name, identifier (ID) and a timestamp. Similarly to the Container Superblock, it contains a pointer to a block map which represents block IDs to block offsets. Moreover, the Volume Superblock contains a pointer to the root directory which is stored as a node.

A detailed view of APFS: