[[Real_time_Reverse_Mapping_Btree]]
=== Reverse-Mapping B+tree

If the reverse-mapping B+tree and real-time storage device features
are enabled, each real-time group has its own reverse block-mapping
B+tree.

As mentioned in the chapter about xref:Reconstruction[reconstruction],
this data structure is another piece of the puzzle necessary to
reconstruct the data or attribute fork of a file from reverse-mapping
records; we can also use it to double-check allocations to ensure that
we are not accidentally cross-linking blocks, which can cause severe
damage to the filesystem.

This B+tree is only present if the +XFS_SB_FEAT_RO_COMPAT_RMAPBT+
feature is enabled and a real time device is present.  The feature
requires a version 5 filesystem.

The rtgroup reverse mapping B+tree is rooted in an inode's data fork; the inode
number can be found by resolving the path +/rtgroups/$rgno.rmap+ in the
metadata directory tree.  The B+tree blocks themselves are stored on the data
volume.  The structures used for an inode's B+tree root are:

[source, c]
----
struct xfs_rtrmap_root {
     __be16                     bb_level;
     __be16                     bb_numrecs;
};
----

* If the B+tree contains only a single level, the ondisk data fork area begins
with a +xfs_rtrmap_root+ header followed by an array of +xfs_rmap_rec+ leaf
records.

* Otherwise, the ondisk data fork area begins with the +xfs_rtrmap_root+
header and is followed first by an array of doubled up +xfs_rmap_key+ values
and then an array of +xfs_rtrmap_ptr_t+ values.  The size of both arrays is
specified by the header's +bb_numrecs+ value.

* The root node in the inode can only contain up to 14 leaf records or 7
key/pointer pairs for a standard 512 byte inode before a new level of nodes is
added between the root and the leaves.

Each record in an rtgroup reverse-mapping B+tree has the same structure as an
AG reverse mapping btree:

[source, c]
----
struct xfs_rmap_rec {
     __be32                     rm_startblock;
     __be32                     rm_blockcount;
     __be64                     rm_owner;
     __be64                     rm_fork:1;
     __be64                     rm_bmbt:1;
     __be64                     rm_unwritten:1;
     __be64                     rm_offset:61;
};
----

*rm_startblock*::
rtgroup block number of this record.

*rm_blockcount*::
The length of this extent, in rt blocks.

*rm_owner*::
A 64-bit number describing the owner of this extent.  This must be
+XFS_RMAP_OWN_FS+ for the first extent in the realtime group zero if realtime
superblocks are enabled.  For all other records, it must be an inode number,
because the real-time volume does not store any other metadata.

*rm_fork*::
This value will always be zero.

*rm_bmbt*::
This value will always be zero.

*rm_unwritten*::
A flag indicating that the extent is unwritten.  This corresponds to
the flag in the xref:Data_Extents[extent record] format which means
+XFS_EXT_UNWRITTEN+.

*rm_offset*::
The 61-bit logical file block offset, if +rm_owner+ describes an
inode.

[NOTE]
The single-bit flag values +rm_unwritten+, +rm_fork+, and +rm_bmbt+
are packed into the larger fields in the C structure definition.

The key has the following structure:

[source, c]
----
struct xfs_rmap_key {
     __be32                     rm_startblock;
     __be64                     rm_owner;
     __be64                     rm_fork:1;
     __be64                     rm_bmbt:1;
     __be64                     rm_reserved:1;
     __be64                     rm_offset:61;
};
----

* All block numbers in records and keys are 32-bit real-time group block
numbers.

* The +bb_magic+ value is ``MAPR'' (0x4d415052).

* The +struct xfs_btree_lblock+ header is used for intermediate B+tree node as
well as the leaves.

* Each pointer is associated with two keys.  The first of these is the
"low key", which is the key of the smallest record accessible through
the pointer.  This low key has the same meaning as the key in all
other btrees.  The second key is the high key, which is the maximum of
the largest key that can be used to access a given record underneath
the pointer.  Recall that each record in the rtgroup reverse mapping
b+tree describes an interval of physical blocks mapped to an interval
of logical file block offsets; therefore, it makes sense that a range
of keys can be used to find to a record.

==== xfs_db rtrmapbt Example

This example shows a real-time reverse-mapping B+tree from a freshly
populated root filesystem:

----
xfs_db> path -m /rtgroups/0.rmap
xfs_db> p
core.magic = 0x494e
core.mode = 0100000
core.version = 3
core.format = 5 (rmap)
...
u3.rtrmapbt.level = 1
u3.rtrmapbt.numrecs = 3
u3.rtrmapbt.keys[1-3] = [startblock,owner,offset,attrfork,bmbtblock,
			 startblock_hi,owner_hi,offset_hi,attrfork_hi,
			 bmbtblock_hi] 
1:[0,-3,0,0,0,682,10015,681,0,0] 
2:[228,10014,227,0,0,454,10014,453,0,0] 
3:[456,10014,455,0,0,682,10014,681,0,0]
u3.rtrmapbt.ptrs[1-3] = 1:10 2:11 3:12
---

This is a two-level tree, so we should follow it towards the leaves.

---
xfs_db> addr u3.rtrmapbt.ptrs[1]
xfs_db> p
magic = 0x4d415052
level = 0
numrecs = 115
leftsib = null
rightsib = 11
bno = 80
lsn = 0
uuid = 23d157a4-8ca7-4fca-8782-637dc6746105
owner = 133
crc = 0x4c046e7d (correct)
recs[1-115] = [startblock,blockcount,owner,offset,extentflag,attrfork,bmbtblock] 
1:[0,1,-3,0,0,0,0] 
2:[1,682,10015,0,0,0,0] 
3:[2,1,10014,1,0,0,0] 
4:[4,1,10014,3,0,0,0] 
5:[6,1,10014,5,0,0,0] 
6:[8,1,10014,7,0,0,0] 
7:[10,1,10014,9,0,0,0] 
8:[12,1,10014,11,0,0,0] 
9:[14,1,10014,13,0,0,0] 
...
112:[220,1,10014,219,0,0,0] 
113:[222,1,10014,221,0,0,0] 
114:[224,1,10014,223,0,0,0] 
115:[226,1,10014,225,0,0,0]
----

Several interesting things pop out here.  The first record shows that inode
10,014 has mapped real-time block 225 at offset 225.  We confirm this by
looking at the block map for that inode:

----
xfs_db> inode 10014
xfs_db> p core.realtime
core.realtime = 1
xfs_db> bmap 220 10
data offset 221 startblock 222 (0/222) count 1 flag 0
data offset 223 startblock 224 (0/224) count 1 flag 0
data offset 225 startblock 226 (0/226) count 1 flag 0
data offset 227 startblock 228 (0/228) count 1 flag 0
data offset 229 startblock 230 (0/230) count 1 flag 0
----

Notice that inode 10,014 has the real-time flag set, which means that its
data blocks are all allocated from the real-time device.
