2022 APFS Advent Challenge Day 8 - Object Maps
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 headerom_flags
: OMAP flags (see below)om_snap_count
: The number of snapshotsom_tree_type
: The type of OMAP tree. This is currently always a physical B-Tree Root Nodeom_snapshot_tree_type
: The type of Snapshot tree. This is currently always a physical B-Tree Root Nodeom_tree_oid
: The physical object identifier of the omap’s B-Treeom_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 snapshotom_pending_revert_min
: The earliest transaction identifier for an in-progress revertom_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 identifierok_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
- paddingoms_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.
Find an issue or technical inaccuracy in this post? Please file an issue so that it may be corrected.