2022 APFS Advent Challenge Day 8 - Object Maps

Monday, December 12, 2022

Earlier in this series, we discussed APFS Containers and how they address physical objects via a fixed block size. This was followed up with a discussion on enumerating Checkpoint Maps to locate ephemeral objects. The last remaining kind of objects that we need to know how to find are virtual objects. Today, we will discuss an essential specialization of B-Trees, the Object Map (OMAP), and their critical role in managing these virtual objects in APFS.

Object Maps perform two essential roles in APFS. They facilitate the address translation needed to locate virtual objects on disk and provide snapshot capabilities that can instantly roll back the set of virtual objects to an earlier point in time. The Container and each Volume maintain their own independent OMAPs. Each OMAP has its own virtual address space, so when dereferencing a virtual object, it is essential to understand how that object is used to know which object map to query.

On-Disk Structures

OMAP Objects have a relatively straightforward on-disk structure. Along with some minor metadata, the primary use of the OMAP Object is to store the physical address of its tree. Optionally, they also store an address to a Snapshot Tree. Both trees are structured as B-Tree Objects.

Incidentally, there are indications that APFS was intended to support more than one type of tree structure. Until recently, Apple’s apfs.kext contained references to an undocumented “M-Tree” type, which appeared to be designed to be used in place of B-Trees in some instances. M-Trees are never mentioned in Apple’s APFS File System Reference, I have never seen them on disk, and all references of M-Trees were removed from the macOS 13 apfs.kext.

typedef struct omap_phys {
    obj_phys_t om_o;                // 0x00
    uint32_t om_flags;              // 0x20
    uint32_t om_snap_count;         // 0x24
    uint32_t om_tree_type;          // 0x28
    uint32_t om_snapshot_tree_type; // 0x2C
    oid_t om_tree_oid;              // 0x30
    oid_t om_snapshot_tree_oid;     // 0x38
    xid_t om_most_recent_snap;      // 0x40
    xid_t om_pending_revert_min;    // 0x48
    xid_t om_pending_revert_max;    // 0x50
} omap_phys_t;                      // 0x58
  • om_o: The object header
  • om_flags: OMAP flags (see below)
  • om_snap_count: The number of snapshots
  • om_tree_type: The type of OMAP tree. This is currently always a physical B-Tree Root Node
  • om_snapshot_tree_type: The type of Snapshot tree. This is currently always a physical B-Tree Root Node
  • om_tree_oid: The physical object identifier of the omap’s B-Tree
  • om_snapshot_tree_oid: The physical object identifier of the snapshot’s B-Tree or zero if there is none.
  • om_most_recent_snap: The transaction identifier of the latest snapshot
  • om_pending_revert_min: The earliest transaction identifier for an in-progress revert
  • om_pending_revert_max: The latest transaction identifier for an in-progress revert

NOTE: Apple’s APFS File System Reference incorrectly lists the om_tree_oid and om_snapshot_tree_oid members as _virtual object identifiers when they are, in fact, physical.

Object Map Flags

Name Value Description
OMAP_MANUALLY_MANAGED 0x00000001 Does not support snapshots
OMAP_ENCRYPTING 0x00000002 Encryption in progress
OMAP_DECRYPTING 0x00000004 Decryption in progress
OMAP_KEYROLLING 0x00000008 Encryption key change in progress
OMAP_CRYPTO_GENERATION 0x00000010 Encryption change marker (more on this later)

Object Map B-Tree

An OMAP tree is a specialized B-Tree type that maps fixed-size omap_key_t and omap_value_t key/value pairs. There can be more than one referenced object with the same virtual object identifier (oid) stored in the tree. Transaction identifiers (xid) are stored to identify these versions.

Keys are sorted in ascending order, first by oid and then xid. Values contain the size and physical address of the mapped object. We will discuss APFS encryption in the future, but for now, it is sufficient to note that omap_value_t marks encrypted objects via the OMAP_VAL_ENCRYPTED bit-flag.

typedef struct omap_key {
    oid_t ok_oid; // 0x00
    xid_t ok_xid; // 0x08
} omap_key_t;     // 0x10
  • ok_oid: The mapped object’s virtual object identifier
  • ok_xid: The mapped object’s transaction identifier
typedef struct omap_val {
    uint32_t ov_flags; // 0x00
    uint32_t ov_size;  // 0x04
    paddr_t ov_paddr;  // 0x08
} omap_val_t;          // 0x10
  • ov_flags: OMAP value flags (see below)
  • ov_size: Size of the mapped object (in bytes)
  • ov_paddr: The physical address of the start of the mapped object

Object Map Value Flags

Name Value Description
OMAP_VAL_DELETED 0x00000001 Object mapping has been removed from the map and this is a placeholder
OMAP_VAL_SAVED 0x00000002 This object mapping shouldnʼt be replaced when the object is updated. (currently unused)
OMAP_VAL_ENCRYPTED 0x00000004 The mapped object is encrypted
OMAP_VAL_NOHEADER 0x00000008 The mapped object has a zero’d object header
OMAP_VAL_CRYPTO_GENERATION 0x00000010 Encryption change marker

Object Map Snapshot Tree

Checkpoint OMAPs also maintain an entry for each of their snapshots in a Snapshot Tree. These trees map xid_t transaction identifiers to omap_snapshot_t values. Other than the deletion state of a snapshot, there is very little information to be gained from enumerating this tree. Volumes maintain additional trees that store more detailed metadata about snapshots. We will discuss those trees in the future.

typedef struct omap_snapshot {
    uint32_t oms_flags; // 0x00
    uint32_t oms_pad;   // 0x04
    oid_t oms_oid;      // 0x08
} omap_snapshot_t;      // 0x10
  • oms_flags - OMAP Snapshot Flags (see below)
  • oms_pad - padding
  • oms_oid - reserved and unused
Name Value Description
OMAP_SNAPSHOT_DELETED 0x00000001 The snapshot has been deleted
OMAP_SNAPSHOT_REVERTED 0x00000002 The snapshot has been deleted as part of a revert

Parsing Object Maps

Once you understand the structure of the OMAP key/value pairs, the process of parsing an OMAP is the same as parsing other B-Trees. When looking up a virtual object from the active filesystem state, choose the key with the highest xid available. If parsing the state from a snapshot, ignore all keys whose xid is greater than the xid of the snapshot in question.

Conclusion

Object Maps are an essential component of APFS that serve two key roles. They provide the address translation needed to locate virtual objects on disk and enable snapshot capabilities that allow instant rollback to earlier points in time.

Now that we’ve covered the basics, it’s time for us to start diving deeper into APFS and learn how to parse information from the file systems themselves. Check back tomorrow when we begin discussing APFS Volumes and their file systems.

This post is part of my 2022 APFS Advent Challenge

Every weekday in the month of December, I will attempt to post a blog about APFS internals. For each day that I miss a post, I will donate $100 to support humanitarian aid for the Ukrainian people. If you find value in this series, and would like to support this effort, please consider donating to the GoFundMe. Slava Ukraini! 🇺🇦

Find an issue or technical inaccuracy in this post? Please file an issue so that it may be corrected.