The problem with accumulating changes at a logical level (i.e. just using the existing log item dirty region tracking) is that when it comes to writing the changes to the log buffers, we need to ensure that the object we are formatting is not changing while we do this. This requires locking the object to prevent concurrent modification. Hence flushing the logical changes to the log would require us to lock every object, format them, and then unlock them again.

This introduces lots of scope for deadlocks with transactions that are already running. For example, a transaction has object A locked and modified, but needs the delayed logging tracking lock to commit the transaction. However, the flushing thread has the delayed logging tracking lock already held, and is trying to get the lock on object A to flush it to the log buffer. This appears to be an unsolvable deadlock condition, and it was solving this problem that was the barrier to implementing delayed logging for so long.

The solution is relatively simple - it just took a long time to recognise it. Put simply, the current logging code formats the changes to each item into an vector array that points to the changed regions in the item. The log write code simply copies the memory these vectors point to into the log buffer during transaction commit while the item is locked in the transaction. Instead of using the log buffer as the destination of the formatting code, we can use an allocated memory buffer big enough to fit the formatted vector.

If we then copy the vector into the memory buffer and rewrite the vector to point to the memory buffer rather than the object itself, we now have a copy of the changes in a format that is compatible with the log buffer writing code. that does not require us to lock the item to access. This formatting and rewriting can all be done while the object is locked during transaction commit, resulting in a vector that is transactionally consistent and can be accessed without needing to lock the owning item.

Hence we avoid the need to lock items when we need to flush outstanding asynchronous transactions to the log. The differences between the existing formatting method and the delayed logging formatting can be seen in the diagram below.

Current format log vector:

Object    +---------------------------------------------+
Vector 1      +----+
Vector 2                    +----+
Vector 3                                   +----------+

After formatting:

Log Buffer    +-V1-+-V2-+----V3----+

Delayed logging vector:

Object    +---------------------------------------------+
Vector 1      +----+
Vector 2                    +----+
Vector 3                                   +----------+

After formatting:

Memory Buffer +-V1-+-V2-+----V3----+
Vector 1      +----+
Vector 2           +----+
Vector 3                +----------+

The memory buffer and associated vector need to be passed as a single object, but still need to be associated with the parent object so if the object is relogged we can replace the current memory buffer with a new memory buffer that contains the latest changes.

The reason for keeping the vector around after we’ve formatted the memory buffer is to support splitting vectors across log buffer boundaries correctly. If we don’t keep the vector around, we do not know where the region boundaries are in the item, so we’d need a new encapsulation method for regions in the log buffer writing (i.e. double encapsulation). This would be an on-disk format change and as such is not desirable. It also means we’d have to write the log region headers in the formatting stage, which is problematic as there is per region state that needs to be placed into the headers during the log write.

Hence we need to keep the vector, but by attaching the memory buffer to it and rewriting the vector addresses to point at the memory buffer we end up with a self-describing object that can be passed to the log buffer write code to be handled in exactly the same manner as the existing log vectors are handled. Hence we avoid needing a new on-disk format to handle items that have been relogged in memory.

Now that we can record transactional changes in memory in a form that allows them to be used without limitations, we need to be able to track and accumulate them so that they can be written to the log at some later point in time. The log item is the natural place to store this vector and buffer, and also makes sense to be the object that is used to track committed objects as it will always exist once the object has been included in a transaction.

The log item is already used to track the log items that have been written to the log but not yet written to disk. Such log items are considered "active" and as such are stored in the Active Item List (AIL) which is a LSN-ordered double linked list. Items are inserted into this list during log buffer IO completion, after which they are unpinned and can be written to disk. An object that is in the AIL can be relogged, which causes the object to be pinned again and then moved forward in the AIL when the log buffer IO completes for that transaction.

Essentially, this shows that an item that is in the AIL can still be modified and relogged, so any tracking must be separate to the AIL infrastructure. As such, we cannot reuse the AIL list pointers for tracking committed items, nor can we store state in any field that is protected by the AIL lock. Hence the committed item tracking needs it’s own locks, lists and state fields in the log item.

Similar to the AIL, tracking of committed items is done through a new list called the Committed Item List (CIL). The list tracks log items that have been committed and have formatted memory buffers attached to them. It tracks objects in transaction commit order, so when an object is relogged it is removed from it’s place in the list and re-inserted at the tail. This is entirely arbitrary and done to make it easy for debugging - the last items in the list are the ones that are most recently modified. Ordering of the CIL is not necessary for transactional integrity (as discussed in the next section) so the ordering is done for convenience/sanity of the developers.

When we have a log synchronisation event, commonly known as a "log force", all the items in the CIL must be written into the log via the log buffers. We need to write these items in the order that they exist in the CIL, and they need to be written as an atomic transaction. The need for all the objects to be written as an atomic transaction comes from the requirements of relogging and log replay - all the changes in all the objects in a given transaction must either be completely replayed during log recovery, or not replayed at all. If a transaction is not replayed because it is not complete in the log, then no later transactions should be replayed, either.

To fulfill this requirement, we need to write the entire CIL in a single log transaction. Fortunately, the XFS log code has no fixed limit on the size of a transaction, nor does the log replay code. The only fundamental limit is that the transaction cannot be larger than just under half the size of the log. The reason for this limit is that to find the head and tail of the log, there must be at least one complete transaction in the log at any given time. If a transaction is larger than half the log, then there is the possibility that a crash during the write of a such a transaction could partially overwrite the only complete previous transaction in the log. This will result in a recovery failure and an inconsistent filesystem and hence we must enforce the maximum size of a checkpoint to be slightly less than a half the log.

Apart from this size requirement, a checkpoint transaction looks no different to any other transaction - it contains a transaction header, a series of formatted log items and a commit record at the tail. From a recovery perspective, the checkpoint transaction is also no different - just a lot bigger with a lot more items in it. The worst case effect of this is that we might need to tune the recovery transaction object hash size.

Because the checkpoint is just another transaction and all the changes to log items are stored as log vectors, we can use the existing log buffer writing code to write the changes into the log. To do this efficiently, we need to minimise the time we hold the CIL locked while writing the checkpoint transaction. The current log write code enables us to do this easily with the way it separates the writing of the transaction contents (the log vectors) from the transaction commit record, but tracking this requires us to have a per-checkpoint context that travels through the log write process through to checkpoint completion.

Hence a checkpoint has a context that tracks the state of the current checkpoint from initiation to checkpoint completion. A new context is initiated at the same time a checkpoint transaction is started. That is, when we remove all the current items from the CIL during a checkpoint operation, we move all those changes into the current checkpoint context. We then initialise a new context and attach that to the CIL for aggregation of new transactions.

This allows us to unlock the CIL immediately after transfer of all the committed items and effectively allow new transactions to be issued while we are formatting the checkpoint into the log. It also allows concurrent checkpoints to be written into the log buffers in the case of log force heavy workloads, just like the existing transaction commit code does. This, however, requires that we strictly order the commit records in the log so that checkpoint sequence order is maintained during log replay.

To ensure that we can be writing an item into a checkpoint transaction at the same time another transaction modifies the item and inserts the log item into the new CIL, then checkpoint transaction commit code cannot use log items to store the list of log vectors that need to be written into the transaction. Hence log vectors need to be able to be chained together to allow them to be detached from the log items. That is, when the CIL is flushed the memory buffer and log vector attached to each log item needs to be attached to the checkpoint context so that the log item can be released. In diagrammatic form, the CIL would look like this before the flush:

        CIL Head
           |
           V
        Log Item <-> log vector 1       -> memory buffer
           |                            -> vector array
           V
        Log Item <-> log vector 2       -> memory buffer
           |                            -> vector array
           V
        ......
           |
           V
        Log Item <-> log vector N-1     -> memory buffer
           |                            -> vector array
           V
        Log Item <-> log vector N       -> memory buffer
                                        -> vector array

And after the flush the CIL head is empty, and the checkpoint context log vector list would look like:

        Checkpoint Context
           |
           V
        log vector 1    -> memory buffer
           |            -> vector array
           |            -> Log Item
           V
        log vector 2    -> memory buffer
           |            -> vector array
           |            -> Log Item
           V
        ......
           |
           V
        log vector N-1  -> memory buffer
           |            -> vector array
           |            -> Log Item
           V
        log vector N    -> memory buffer
                        -> vector array
                        -> Log Item

Once this transfer is done, the CIL can be unlocked and new transactions can start, while the checkpoint flush code works over the log vector chain to commit the checkpoint.

Once the checkpoint is written into the log buffers, the checkpoint context is attached to the log buffer that the commit record was written to along with a completion callback. Log IO completion will call that callback, which can then run transaction committed processing for the log items (i.e. insert into AIL and unpin) in the log vector chain and then free the log vector chain and checkpoint context.

Discussion Point: I am uncertain as to whether the log item is the most efficient way to track vectors, even though it seems like the natural way to do it. The fact that we walk the log items (in the CIL) just to chain the log vectors and break the link between the log item and the log vector means that we take a cache line hit for the log item list modification, then another for the log vector chaining. If we track by the log vectors, then we only need to break the link between the log item and the log vector, which means we should dirty only the log item cachelines. Normally I wouldn’t be concerned about one vs two dirty cachelines except for the fact I’ve seen upwards of 80,000 log vectors in one checkpoint transaction. I’d guess this is a "measure and compare" situation that can be done after a working and reviewed implementation is in the dev tree….

One of the key aspects of the XFS transaction subsystem is that it tags committed transactions with the log sequence number of the transaction commit. This allows transactions to be issued asynchronously even though there may be future operations that cannot be completed until that transaction is fully committed to the log. In the rare case that a dependent operation occurs (e.g. re-using a freed metadata extent for a data extent), a special, optimised log force can be issued to force the dependent transaction to disk immediately.

To do this, transactions need to record the LSN of the commit record of the transaction. This LSN comes directly from the log buffer the transaction is written into. While this works just fine for the existing transaction mechanism, it does not work for delayed logging because transactions are not written directly into the log buffers. Hence some other method of sequencing transactions is required.

As discussed in the checkpoint section, delayed logging uses per-checkpoint contexts, and as such it is simple to assign a sequence number to each checkpoint. Because the switching of checkpoint contexts must be done atomically, it is simple to ensure that each new context has a monotonically increasing sequence number assigned to it without the need for an external atomic counter - we can just take the current context sequence number and add one to it for the new context.

Then, instead of assigning a log buffer LSN to the transaction commit LSN during the commit, we can assign the current checkpoint sequence. This allows operations that track transactions that have not yet completed know what checkpoint sequence needs to be committed before they can continue. As a result, the code that forces the log to a specific LSN now needs to ensure that the log forces to a specific checkpoint.

To ensure that we can do this, we need to track all the checkpoint contexts that are currently committing to the log. When we flush a checkpoint, the context gets added to a "committing" list which can be searched. When a checkpoint commit completes, it is removed from the committing list. Because the checkpoint context records the LSN of the commit record for the checkpoint, we can also wait on the log buffer that contains the commit record, thereby using the existing log force mechanisms to execute synchronous forces.

It should be noted that the synchronous forces may need to be extended with mitigation algorithms similar to the current log buffer code to allow aggregation of multiple synchronous transactions if there are already synchronous transactions being flushed. Investigation of the performance of the current design is needed before making any decisions here.

The main concern with log forces is to ensure that all the previous checkpoints are also committed to disk before the one we need to wait for. Therefore we need to check that all the prior contexts in the committing list are also complete before waiting on the one we need to complete. We do this synchronisation in the log force code so that we don’t need to wait anywhere else for such serialisation - it only matters when we do a log force.

The only remaining complexity is that a log force now also has to handle the case where the forcing sequence number is the same as the current context. That is, we need to flush the CIL and potentially wait for it to complete. This is a simple addition to the existing log forcing code to check the sequence numbers and push if required. Indeed, placing the current sequence checkpoint flush in the log force code enables the current mechanism for issuing synchronous transactions to remain untouched (i.e. commit an asynchronous transaction, then force the log at the LSN of that transaction) and so the higher level code behaves the same regardless of whether delayed logging is being used or not.

The big issue for a checkpoint transaction is the log space reservation for the transaction. We don’t know how big a checkpoint transaction is going to be ahead of time, nor how many log buffers it will take to write out, nor the number of split log vector regions are going to be used. We can track the amount of log space required as we add items to the commit item list, but we still need to reserve the space in the log for the checkpoint.

A typical transaction reserves enough space in the log for the worst case space usage of the transaction. The reservation accounts for log record headers, transaction and region headers, headers for split regions, buffer tail padding, etc. as well as the actual space for all the changed metadata in the transaction. While some of this is fixed overhead, much of it is dependent on the size of the transaction and the number of regions being logged (the number of log vectors in the transaction).

An example of the differences would be logging directory changes versus logging inode changes. If you modify lots of inode cores (e.g. chmod -R g+w *), then there are lots of transactions that only contain an inode core and an inode log format structure. That is, two vectors totaling roughly 150 bytes. If we modify 10,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each vector is 12 bytes, so the total to be logged is approximately 1.75MB. In comparison, if we are logging full directory buffers, they are typically 4KB each, so we in 1.5MB of directory buffers we’d have roughly 400 buffers and a buffer format structure for each buffer - roughly 800 vectors or 1.51MB total space. From this, it should be obvious that a static log space reservation is not particularly flexible and is difficult to select the "optimal value" for all workloads.

Further, if we are going to use a static reservation, which bit of the entire reservation does it cover? We account for space used by the transaction reservation by tracking the space currently used by the object in the CIL and then calculating the increase or decrease in space used as the object is relogged. This allows for a checkpoint reservation to only have to account for log buffer metadata used such as log header records.

However, even using a static reservation for just the log metadata is problematic. Typically log record headers use at least 16KB of log space per 1MB of log space consumed (512 bytes per 32k) and the reservation needs to be large enough to handle arbitrary sized checkpoint transactions. This reservation needs to be made before the checkpoint is started, and we need to be able to reserve the space without sleeping. For a 8MB checkpoint, we need a reservation of around 150KB, which is a non-trivial amount of space.

A static reservation needs to manipulate the log grant counters - we can take a permanent reservation on the space, but we still need to make sure we refresh the write reservation (the actual space available to the transaction) after every checkpoint transaction completion. Unfortunately, if this space is not available when required, then the regrant code will sleep waiting for it.

The problem with this is that it can lead to deadlocks as we may need to commit checkpoints to be able to free up log space (refer back to the description of rolling transactions for an example of this). Hence we must always have space available in the log if we are to use static reservations, and that is very difficult and complex to arrange. It is possible to do, but there is a simpler way.

The simpler way of doing this is tracking the entire log space used by the items in the CIL and using this to dynamically calculate the amount of log space required by the log metadata. If this log metadata space changes as a result of a transaction commit inserting a new memory buffer into the CIL, then the difference in space required is removed from the transaction that causes the change. Transactions at this level will always have enough space available in their reservation for this as they have already reserved the maximal amount of log metadata space they require, and such a delta reservation will always be less than or equal to the maximal amount in the reservation.

Hence we can grow the checkpoint transaction reservation dynamically as items are added to the CIL and avoid the need for reserving and regranting log space up front. This avoids deadlocks and removes a blocking point from the checkpoint flush code.

As mentioned early, transactions can’t grow to more than half the size of the log. Hence as part of the reservation growing, we need to also check the size of the reservation against the maximum allowed transaction size. If we reach the maximum threshold, we need to push the CIL to the log. This is effectively a "background flush" and is done on demand. This is identical to a CIL push triggered by a log force, only that there is no waiting for the checkpoint commit to complete. This background push is checked and executed by transaction commit code.

If the transaction subsystem goes idle while we still have items in the CIL, they will be flushed by the periodic log force issued by the xfssyncd. This log force will push the CIL to disk, and if the transaction subsystem stays idle, allow the idle log to be covered (effectively marked clean) in exactly the same manner that is done for the existing logging method. A discussion point is whether this log force needs to be done more frequently than the current rate which is once every 30s.

Currently log items are pinned during transaction commit while the items are still locked. This happens just after the items are formatted, though it could be done any time before the items are unlocked. The result of this mechanism is that items get pinned once for every transaction that is committed to the log buffers. Hence items that are relogged in the log buffers will have a pin count for every outstanding transaction they were dirtied in. When each of these transactions is completed, they will unpin the item once. As a result, the item only becomes unpinned when all the transactions complete and there are no pending transactions. Thus the pinning and unpinning of a log item is symmetric as there is a 1:1 relationship with transaction commit and log item completion.

For delayed logging, however, we have an asymmetric transaction commit to completion relationship. Every time an object is relogged in the CIL it goes through the commit process without a corresponding completion being registered. That is, we now have a many-to-one relationship between transaction commit and log item completion. The result of this is that pinning and unpinning of the log items becomes unbalanced if we retain the "pin on transaction commit, unpin on transaction completion" model.

To keep pin/unpin symmetry, the algorithm needs to change to a "pin on insertion into the CIL, unpin on checkpoint completion". In other words, the pinning and unpinning becomes symmetric around a checkpoint context. We have to pin the object the first time it is inserted into the CIL - if it is already in the CIL during a transaction commit, then we do not pin it again. Because there can be multiple outstanding checkpoint contexts, we can still see elevated pin counts, but as each checkpoint completes the pin count will retain the correct value according to it’s context.

Just to make matters more slightly more complex, this checkpoint level context for the pin count means that the pinning of an item must take place under the CIL commit/flush lock. If we pin the object outside this lock, we cannot guarantee which context the pin count is associated with. This is because of the fact pinning the item is dependent on whether the item is present in the current CIL or not. If we don’t pin the CIL first before we check and pin the object, we have a race with CIL being flushed between the check and the pin (or not pinning, as the case may be). Hence we must hold the CIL flush/commit lock to guarantee that we pin the items correctly.

A fundamental requirement for the CIL is that accesses through transaction commits must scale to many concurrent commits. The current transaction commit code does not break down even when there are transactions coming from 2048 processors at once. The current transaction code does not go any faster than if there was only one CPU using it, but it does not slow down either.

As a result, the delayed logging transaction commit code needs to be designed for concurrency from the ground up. It is obvious that there are serialisation points in the design - the three important ones are:

Looking at the transaction commit and CIL flushing interactions, it is clear that we have a many-to-one interaction here. That is, the only restriction on the number of concurrent transactions that can be trying to commit at once is the amount of space available in the log for their reservations. The practical limit here is in the order of several hundred concurrent transactions for a 128MB log, which means that it is generally one per CPU in a machine.

The amount of time a transaction commit needs to hold out a flush is a relatively long period of time - the pinning of log items needs to be done while we are holding out a CIL flush, so at the moment that means it is held across the formatting of the objects into memory buffers (i.e. while memcpy()s are in progress). Ultimately a two pass algorithm where the formatting is done separately to the pinning of objects could be used to reduce the hold time of the transaction commit side.

Because of the number of potential transaction commit side holders, the lock really needs to be a sleeping lock - if the CIL flush takes the lock, we do not want every other CPU in the machine spinning on the CIL lock. Given that flushing the CIL could involve walking a list of tens of thousands of log items, it will get held for a significant time and so spin contention is a significant concern. Preventing lots of CPUs spinning doing nothing is the main reason for choosing a sleeping lock even though nothing in either the transaction commit or CIL flush side sleeps with the lock held.

It should also be noted that CIL flushing is also a relatively rare operation compared to transaction commit for asynchronous transaction workloads - only time will tell if using a read-write semaphore for exclusion will limit transaction commit concurrency due to cache line bouncing of the lock on the read side.

The second serialisation point is on the transaction commit side where items are inserted into the CIL. Because transactions can enter this code concurrently, the CIL needs to be protected separately from the above commit/flush exclusion. It also needs to be an exclusive lock but it is only held for a very short time and so a spin lock is appropriate here. It is possible that this lock will become a contention point, but given the short hold time once per transaction I think that contention is unlikely.

The final serialisation point is the checkpoint commit record ordering code that is run as part of the checkpoint commit and log force sequencing. The code path that triggers a CIL flush (i.e. whatever triggers the log force) will enter an ordering loop after writing all the log vectors into the log buffers but before writing the commit record. This loop walks the list of committing checkpoints and needs to block waiting for checkpoints to complete their commit record write. As a result it needs a lock and a wait variable. Log force sequencing also requires the same lock, list walk, and blocking mechanism to ensure completion of checkpoints.

These two sequencing operations can use the mechanism even though the events they are waiting for are different. The checkpoint commit record sequencing needs to wait until checkpoint contexts contain a commit LSN (obtained through completion of a commit record write) while log force sequencing needs to wait until previous checkpoint contexts are removed from the committing list (i.e. they’ve completed). A simple wait variable and broadcast wakeups (thundering herds) has been used to implement these two serialisation queues. They use the same lock as the CIL, too. If we see too much contention on the CIL lock, or too many context switches as a result of the broadcast wakeups these operations can be put under a new spinlock and given separate wait lists to reduce lock contention and the number of processes woken by the wrong event.

The existing log item life cycle is as follows:

        1. Transaction allocate
        2. Transaction reserve
        3. Lock item
        4. Join item to transaction
                If not already attached,
                        Allocate log item
                        Attach log item to owner item
                Attach log item to transaction
        5. Modify item
                Record modifications in log item
        6. Transaction commit
                Pin item in memory
                Format item into log buffer
                Write commit LSN into transaction
                Unlock item
                Attach transaction to log buffer

        <log buffer IO dispatched>
        <log buffer IO completes>

        7. Transaction completion
                Mark log item committed
                Insert log item into AIL
                        Write commit LSN into log item
                Unpin log item
        8. AIL traversal
                Lock item
                Mark log item clean
                Flush item to disk

        <item IO completion>

        9. Log item removed from AIL
                Moves log tail
                Item unlocked

Essentially, steps 1-6 operate independently from step 7, which is also independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9 at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur at the same time. If the log item is in the AIL or between steps 6 and 7 and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9 are entered and completed is the object considered clean.

With delayed logging, there are new steps inserted into the life cycle:

        1. Transaction allocate
        2. Transaction reserve
        3. Lock item
        4. Join item to transaction
                If not already attached,
                        Allocate log item
                        Attach log item to owner item
                Attach log item to transaction
        5. Modify item
                Record modifications in log item
        6. Transaction commit
                Pin item in memory if not pinned in CIL
                Format item into log vector + buffer
                Attach log vector and buffer to log item
                Insert log item into CIL
                Write CIL context sequence into transaction
                Unlock item

        <next log force>

        7. CIL push
                lock CIL flush
                Chain log vectors and buffers together
                Remove items from CIL
                unlock CIL flush
                write log vectors into log
                sequence commit records
                attach checkpoint context to log buffer

        <log buffer IO dispatched>
        <log buffer IO completes>

        8. Checkpoint completion
                Mark log item committed
                Insert item into AIL
                        Write commit LSN into log item
                Unpin log item
        9. AIL traversal
                Lock item
                Mark log item clean
                Flush item to disk
        <item IO completion>
        10. Log item removed from AIL
                Moves log tail
                Item unlocked

From this, it can be seen that the only life cycle differences between the two logging methods are in the middle of the life cycle - they still have the same beginning and end and execution constraints. The only differences are in the committing of the log items to the log itself and the completion processing. Hence delayed logging should not introduce any constraints on log item behaviour, allocation or freeing that don’t already exist.

As a result of this zero-impact "insertion" of delayed logging infrastructure and the design of the internal structures to avoid on disk format changes, we can basically switch between delayed logging and the existing mechanism with a mount option. Fundamentally, there is no reason why the log manager would not be able to swap methods automatically and transparently depending on load characteristics, but this should not be necessary if delayed logging works as designed.

EOF.

A filesystem is made on a single disk with the following command:

# mkfs.xfs -i attr=2 -n size=16384 -f /dev/sda7
meta-data=/dev/sda7              isize=256    agcount=16, agsize=3923122 blks
         =                       sectsz=512   attr=2
data     =                       bsize=4096   blocks=62769952, imaxpct=25
         =                       sunit=0      swidth=0 blks, unwritten=1
naming   =version 2              bsize=16384
log      =internal log           bsize=4096   blocks=30649, version=1
         =                       sectsz=512   sunit=0 blks
realtime =none                   extsz=65536  blocks=0, rtextents=0

And in xfs_db, inspecting the superblock:

xfs_db> sb
xfs_db> p
magicnum = 0x58465342
blocksize = 4096
dblocks = 62769952
rblocks = 0
rextents = 0
uuid = 32b24036-6931-45b4-b68c-cd5e7d9a1ca5
logstart = 33554436
rootino = 128
rbmino = 129
rsumino = 130
rextsize = 16
agblocks = 3923122
agcount = 16
rbmblocks = 0
logblocks = 30649
versionnum = 0xb084
sectsize = 512
inodesize = 256
inopblock = 16
fname = "\000\000\000\000\000\000\000\000\000\000\000\000"
blocklog = 12
sectlog = 9
inodelog = 8
inopblog = 4
agblklog = 22
rextslog = 0
inprogress = 0
imax_pct = 25
icount = 64
ifree = 61
fdblocks = 62739235
frextents = 0
uquotino = 0
gquotino = 0
qflags = 0
flags = 0
shared_vn = 0
inoalignmt = 2
unit = 0
width = 0
dirblklog = 2
logsectlog = 0
logsectsize = 0
logsunit = 0
features2 = 8

The second sector in an AG contains the information about the two free space B+trees and associated free space information for the AG. The “AG Free Space Block” also knows as the AGF, uses the following structure:

struct xfs_agf {
     __be32              agf_magicnum;
     __be32              agf_versionnum;
     __be32              agf_seqno;
     __be32              agf_length;
     __be32              agf_roots[XFS_BTNUM_AGF];
     __be32              agf_levels[XFS_BTNUM_AGF];
     __be32              agf_flfirst;
     __be32              agf_fllast;
     __be32              agf_flcount;
     __be32              agf_freeblks;
     __be32              agf_longest;
     __be32              agf_btreeblks;

     /* version 5 filesystem fields start here */
     uuid_t              agf_uuid;
     __be32              agf_rmap_blocks;
     __be32              agf_refcount_blocks;
     __be32              agf_refcount_root;
     __be32              agf_refcount_level;
     __be64              agf_spare64[14];

     /* unlogged fields, written during buffer writeback. */
     __be64              agf_lsn;
     __be32              agf_crc;
     __be32              agf_spare2;
};

The rest of the bytes in the sector are zeroed. XFS_BTNUM_AGF is set to 3: index 0 for the free space B+tree indexed by block number; index 1 for the free space B+tree indexed by extent size; and index 2 for the reverse-mapping B+tree.

The two Free Space B+trees store a sorted array of block offset and block counts in the leaves of the B+tree. The first B+tree is sorted by the offset, the second by the count or size.

Leaf nodes contain a sorted array of offset/count pairs which are also used for node keys:

struct xfs_alloc_rec {
     __be32                    ar_startblock;
     __be32                    ar_blockcount;
};

Node pointers are an AG relative block pointer:

typedef __be32 xfs_alloc_ptr_t;

The following diagram shows a single level B+tree which consists of one leaf:

Figure 13.2. Freespace B+tree with one leaf.

With the intermediate nodes, the associated leaf pointers are stored in a separate array about two thirds into the block. The following diagram illustrates a 2-level B+tree for a free space B+tree:

Figure 13.3. Multi-level freespace B+tree.

The AG Free List is located in the 4^th sector of each AG and is known as the AGFL. It is an array of AG relative block pointers for reserved space for growing the free space B+trees. This space cannot be used for general user data including inodes, data, directories and extended attributes.

With a freshly made filesystem, 4 blocks are reserved immediately after the free space B+tree root blocks (blocks 4 to 7). As they are used up as the free space fragments, additional blocks will be reserved from the AG and added to the free list array. This size may increase as features are added.

As the free list array is located within a single sector, a typical device will have space for 128 elements in the array (512 bytes per sector, 4 bytes per AG relative block pointer). The actual size can be determined by using the XFS_AGFL_SIZE macro.

Active elements in the array are specified by the AGF’s agf_flfirst, agf_fllast and agf_flcount values. The array is managed as a circular list.

On a v5 filesystem, the following header precedes the free list entries:

struct xfs_agfl {
     __be32              agfl_magicnum;
     __be32              agfl_seqno;
     uuid_t              agfl_uuid;
     __be64              agfl_lsn;
     __be32              agfl_crc;
};

On a v4 filesystem there is no header; the array of free block numbers begins at the beginning of the sector.

Figure 13.4. AG Free List layout

The presence of these reserved blocks guarantees that the free space B+trees can be updated if any blocks are freed by extent changes in a full AG.

xfs_db> agf 0
xfs_db> p
magicnum = 0x58414746
versionnum = 1
seqno = 0
length = 3923122
bnoroot = 7
cntroot = 83343
bnolevel = 2
cntlevel = 2
flfirst = 22
fllast = 27
flcount = 6
freeblks = 3654234
longest = 3384327
btreeblks = 0

xfs_db> agfl 0
xfs_db> p
bno[0-127] = 0:4 1:5 2:6 3:7 4:83342 5:83343 6:83344 7:83345 8:83346 9:83347
             10:4 11:5 12:80205 13:80780 14:81496 15:81766 16:83346 17:4 18:5
             19:80205 20:82449 21:81496 22:81766 23:82455 24:80780 25:5
             26:80205 27:83344

xfs_db> fsblock 7
xfs_db> type bnobt
xfs_db> p
magic = 0x41425442
level = 1
numrecs = 4
leftsib = null
rightsib = null
keys[1-4] = [startblock,blockcount]
           1:[12,16] 2:[184586,3] 3:[225579,1] 4:[511629,1]
ptrs[1-4] = 1:2 2:83347 3:6 4:4

xfs_db> fsblock 83343
xfs_db> type cntbt
xfs_db> p
magic = 0x41425443
level = 1
numrecs = 4
leftsib = null
rightsib = null
keys[1-4] = [blockcount,startblock]
           1:[1,81496] 2:[1,511729] 3:[3,191875] 4:[6,184595]
ptrs[1-4] = 1:3 2:83345 3:83342 4:83346

xfs_db> fsblock 83346
xfs_db> type cntbt
xfs_db> p
magic = 0x41425443
level = 0
numrecs = 344
leftsib = 83342
rightsib = null
recs[1-344] = [startblock,blockcount]
           1:[184595,6] 2:[187573,6] 3:[187776,6]
           ...
           342:[513712,755] 343:[230317,258229] 344:[538795,3384327]

Inode numbers in XFS come in two forms: AG relative and absolute.

AG relative inode numbers always fit within 32 bits. The number of bits actually used is determined by the sum of the superblock’s sb_inoplog and sb_agblklog values. Relative inode numbers are found within the AG’s inode structures.

Absolute inode numbers include the AG number in the high bits, above the bits used for the AG relative inode number. Absolute inode numbers are found in directory entries and the superblock.

Figure 13.5. Inode number formats

Each AG manages its own inodes. The third sector in the AG contains information about the AG’s inodes and is known as the AGI.

The AGI uses the following structure:

struct xfs_agi {
     __be32              agi_magicnum;
     __be32              agi_versionnum;
     __be32              agi_seqno
     __be32              agi_length;
     __be32              agi_count;
     __be32              agi_root;
     __be32              agi_level;
     __be32              agi_freecount;
     __be32              agi_newino;
     __be32              agi_dirino;
     __be32              agi_unlinked[64];

     /*
      * v5 filesystem fields start here; this marks the end of logging region 1
      * and start of logging region 2.
      */
     uuid_t              agi_uuid;
     __be32              agi_crc;
     __be32              agi_pad32;
     __be64              agi_lsn;

     __be32              agi_free_root;
     __be32              agi_free_level;

     __be32              agi_iblocks;
     __be32              agi_fblocks;

}

This is an AGI of a freshly populated filesystem:

xfs_db> agi 0
xfs_db> p
magicnum = 0x58414749
versionnum = 1
seqno = 0
length = 825457
count = 5440
root = 3
level = 1
freecount = 9
newino = 5792
dirino = null
unlinked[0-63] =
uuid = 3dfa1e5c-5a5f-4ca2-829a-000e453600fe
lsn = 0x1000032c2
crc = 0x14cb7e5c (correct)
free_root = 4
free_level = 1

From this example, we see that the inode B+tree is rooted at AG block 3 and that the free inode B+tree is rooted at AG block 4. Let’s look at the inode B+tree:

xfs_db> addr root
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 85
leftsib = null
rightsib = null
bno = 24
lsn = 0x1000032c2
uuid = 3dfa1e5c-5a5f-4ca2-829a-000e453600fe
owner = 0
crc = 0x768f9592 (correct)
recs[1-85] = [startino,freecount,free]
        1:[96,0,0] 2:[160,0,0] 3:[224,0,0] 4:[288,0,0]
        5:[352,0,0] 6:[416,0,0] 7:[480,0,0] 8:[544,0,0]
        9:[608,0,0] 10:[672,0,0] 11:[736,0,0] 12:[800,0,0]
        ...
        85:[5792,9,0xff80000000000000]

Most of the inode chunks on this filesystem are totally full, since the free value is zero. This means that we ought to expect inode 160 to be linked somewhere in the directory structure. However, notice that 0xff80000000000000 in record 85 — this means that we would expect inode 5847 to be free. Moving on to the free inode B+tree, we see that this is indeed the case:

xfs_db> addr free_root
xfs_db> p
magic = 0x46494233
level = 0
numrecs = 1
leftsib = null
rightsib = null
bno = 32
lsn = 0x1000032c2
uuid = 3dfa1e5c-5a5f-4ca2-829a-000e453600fe
owner = 0
crc = 0x338af88a (correct)
recs[1] = [startino,freecount,free] 1:[5792,9,0xff80000000000000]

Observe also that the AGI’s agi_newino points to this chunk, which has never been fully allocated.

This example derives from an AG that has been deliberately fragmented. The inode B+tree:

xfs_db> agi 0
xfs_db> p
magicnum = 0x58414749
versionnum = 1
seqno = 0
length = 6400
count = 10432
root = 2381
level = 2
freecount = 0
newino = 14912
dirino = null
unlinked[0-63] =
uuid = b9b4623b-f678-4d48-8ce7-ce08950e3cd6
lsn = 0x600000ac4
crc = 0xef550dbc (correct)
free_root = 4
free_level = 1

This AGI was formatted on a v5 filesystem; notice the extra v5 fields. So far everything else looks much the same as always.

xfs_db> addr root
magic = 0x49414233
level = 1
numrecs = 2
leftsib = null
rightsib = null
bno = 19048
lsn = 0x50000192b
uuid = b9b4623b-f678-4d48-8ce7-ce08950e3cd6
owner = 0
crc = 0xd98cd2ca (correct)
keys[1-2] = [startino] 1:[128] 2:[35136]
ptrs[1-2] = 1:3 2:2380
xfs_db> addr ptrs[1]
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 159
leftsib = null
rightsib = 2380
bno = 24
lsn = 0x600000ac4
uuid = b9b4623b-f678-4d48-8ce7-ce08950e3cd6
owner = 0
crc = 0x836768a6 (correct)
recs[1-159] = [startino,holemask,count,freecount,free]
        1:[128,0,64,0,0]
        2:[14912,0xff,32,0,0xffffffff]
        3:[15040,0,64,0,0]
        4:[15168,0xff00,32,0,0xffffffff00000000]
        5:[15296,0,64,0,0]
        6:[15424,0xff,32,0,0xffffffff]
        7:[15552,0,64,0,0]
        8:[15680,0xff00,32,0,0xffffffff00000000]
        9:[15808,0,64,0,0]
        10:[15936,0xff,32,0,0xffffffff]

Here we see the difference in the inode B+tree records. For example, in record 2, we see that the holemask has a value of 0xff. This means that the first sixteen inodes in this chunk record do not actually map to inode blocks; the first inode in this chunk is actually inode 14944:

xfs_db> inode 14912
Metadata corruption detected at block 0x3a40/0x2000
...
Metadata CRC error detected for ino 14912
xfs_db> p core.magic
core.magic = 0
xfs_db> inode 14944
xfs_db> p core.magic
core.magic = 0x494e

The chunk record also indicates that this chunk has 32 inodes, and that the missing inodes are also “free”.

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

xfs_db> agf 0
xfs_db> addr rmaproot
xfs_db> p
magic = 0x524d4233
level = 1
numrecs = 43
leftsib = null
rightsib = null
bno = 56
lsn = 0x3000004c8
uuid = 1977221d-8345-464e-b1f4-aa2ea36895f4
owner = 0
crc = 0x7cf8be6f (correct)
keys[1-43] = [startblock,owner,offset]
keys[1-43] = [startblock,owner,offset,attrfork,bmbtblock,startblock_hi,owner_hi,
             offset_hi,attrfork_hi,bmbtblock_hi]
        1:[0,-3,0,0,0,351,4418,66,0,0]
        2:[417,285,0,0,0,827,4419,2,0,0]
        3:[829,499,0,0,0,2352,573,55,0,0]
        4:[1292,710,0,0,0,32168,262923,47,0,0]
        5:[32215,-5,0,0,0,34655,2365,3411,0,0]
        6:[34083,1161,0,0,0,34895,265220,1,0,1]
        7:[34896,256191,0,0,0,36522,-9,0,0,0]
        ...
        41:[50998,326734,0,0,0,51430,-5,0,0,0]
        42:[51431,327010,0,0,0,51600,325722,11,0,0]
        43:[51611,327112,0,0,0,94063,23522,28375272,0,0]
ptrs[1-43] = 1:5 2:6 3:8 4:9 5:10 6:11 7:418 ... 41:46377 42:48784 43:49522

We arbitrarily pick pointer 17 to traverse downwards:

xfs_db> addr ptrs[17]
xfs_db> p
magic = 0x524d4233
level = 0
numrecs = 168
leftsib = 36284
rightsib = 37617
bno = 294760
lsn = 0x200002761
uuid = 1977221d-8345-464e-b1f4-aa2ea36895f4
owner = 0
crc = 0x2dad3fbe (correct)
recs[1-168] = [startblock,blockcount,owner,offset,extentflag,attrfork,bmbtblock]
        1:[40326,1,259615,0,0,0,0] 2:[40327,1,-5,0,0,0,0]
        3:[40328,2,259618,0,0,0,0] 4:[40330,1,259619,0,0,0,0]
        ...
        127:[40540,1,324266,0,0,0,0] 128:[40541,1,324266,8388608,0,0,0]
        129:[40542,2,324266,1,0,0,0] 130:[40544,32,-7,0,0,0,0]

Several interesting things pop out here. The first record shows that inode 259,615 has mapped AG block 40,326 at offset 0. We confirm this by looking at the block map for that inode:

xfs_db> inode 259615
xfs_db> bmap
data offset 0 startblock 40326 (0/40326) count 1 flag 0

Next, notice records 127 and 128, which describe neighboring AG blocks that are mapped to non-contiguous logical blocks in inode 324,266. Given the logical offset of 8,388,608 we surmise that this is a leaf directory, but let us confirm:

xfs_db> inode 324266
xfs_db> p core.mode
core.mode = 040755
xfs_db> bmap
data offset 0 startblock 40540 (0/40540) count 1 flag 0
data offset 1 startblock 40542 (0/40542) count 2 flag 0
data offset 3 startblock 40576 (0/40576) count 1 flag 0
data offset 8388608 startblock 40541 (0/40541) count 1 flag 0
xfs_db> p core.mode
core.mode = 0100644
xfs_db> dblock 0
xfs_db> p dhdr.hdr.magic
dhdr.hdr.magic = 0x58444433
xfs_db> dblock 8388608
xfs_db> p lhdr.info.hdr.magic
lhdr.info.hdr.magic = 0x3df1

Indeed, this inode 324,266 appears to be a leaf directory, as it has regular directory data blocks at low offsets, and a single leaf block.

Notice further the two reverse-mapping records with negative owners. An owner of -7 corresponds to XFS_RMAP_OWN_INODES, which is an inode chunk, and an owner code of -5 corresponds to XFS_RMAP_OWN_AG, which covers free space B+trees and free space. Let’s see if block 40,544 is part of an inode chunk:

xfs_db> blockget
xfs_db> fsblock 40544
xfs_db> blockuse
block 40544 (0/40544) type inode
xfs_db> stack
1:
        byte offset 166068224, length 4096
        buffer block 324352 (fsbno 40544), 8 bbs
        inode 324266, dir inode 324266, type data
xfs_db> type inode
xfs_db> p
core.magic = 0x494e

Our suspicions are confirmed. Let’s also see if 40,327 is part of a free space tree:

xfs_db> fsblock 40327
xfs_db> blockuse
block 40327 (0/40327) type btrmap
xfs_db> type rmapbt
xfs_db> p
magic = 0x524d4233

As you can see, the reverse block-mapping B+tree is an important secondary metadata structure, which can be used to reconstruct damaged primary metadata. Now let’s look at an extend rmap btree:

xfs_db> agf 0
xfs_db> addr rmaproot
xfs_db> p
magic = 0x34524d42
level = 1
numrecs = 5
leftsib = null
rightsib = null
bno = 6368
lsn = 0x100000d1b
uuid = 400f0928-6b88-4c37-af1e-cef1f8911f3f
owner = 0
crc = 0x8d4ace05 (correct)
keys[1-5] = [startblock,owner,offset,attrfork,bmbtblock,startblock_hi,owner_hi,offset_hi,attrfork_hi,bmbtblock_hi]
1:[0,-3,0,0,0,705,132,681,0,0]
2:[24,5761,0,0,0,548,5761,524,0,0]
3:[24,5929,0,0,0,380,5929,356,0,0]
4:[24,6097,0,0,0,212,6097,188,0,0]
5:[24,6277,0,0,0,807,-7,0,0,0]
ptrs[1-5] = 1:5 2:771 3:9 4:10 5:11

The second pointer stores both the low key [24,5761,0,0,0] and the high key [548,5761,524,0,0], which means that we can expect block 771 to contain records starting at physical block 24, inode 5761, offset zero; and that one of the records can be used to find a reverse mapping for physical block 548, inode 5761, and offset 524:

xfs_db> addr ptrs[2]
xfs_db> p
magic = 0x34524d42
level = 0
numrecs = 168
leftsib = 5
rightsib = 9
bno = 6168
lsn = 0x100000d1b
uuid = 400f0928-6b88-4c37-af1e-cef1f8911f3f
owner = 0
crc = 0xd58eff0e (correct)
recs[1-168] = [startblock,blockcount,owner,offset,extentflag,attrfork,bmbtblock]
1:[24,525,5761,0,0,0,0]
2:[24,524,5762,0,0,0,0]
3:[24,523,5763,0,0,0,0]
...
166:[24,360,5926,0,0,0,0]
167:[24,359,5927,0,0,0,0]
168:[24,358,5928,0,0,0,0]

Observe that the first record in the block starts at physical block 24, inode 5761, offset zero, just as we expected. Note that this first record is also indexed by the highest key as provided in the node block; physical block 548, inode 5761, offset 524 is the very last block mapped by this record. Furthermore, note that record 168, despite being the last record in this block, has a lower maximum key (physical block 382, inode 5928, offset 23) than the first record.

For this example, an XFS filesystem was populated with a root filesystem and a deduplication program was run to create shared blocks:

xfs_db> agf 0
xfs_db> addr refcntroot
xfs_db> p
magic = 0x52334643
level = 1
numrecs = 6
leftsib = null
rightsib = null
bno = 36892
lsn = 0x200004ec2
uuid = f1f89746-e00b-49c9-96b3-ecef0f2f14ae
owner = 0
crc = 0x75f35128 (correct)
keys[1-6] = [startblock] 1:[14] 2:[65633] 3:[65780] 4:[94571] 5:[117201] 6:[152442]
ptrs[1-6] = 1:7 2:25836 3:25835 4:18447 5:18445 6:18449
xfs_db> addr ptrs[3]
xfs_db> p
magic = 0x52334643
level = 0
numrecs = 80
leftsib = 25836
rightsib = 18447
bno = 51670
lsn = 0x200004ec2
uuid = f1f89746-e00b-49c9-96b3-ecef0f2f14ae
owner = 0
crc = 0xc3962813 (correct)
recs[1-80] = [startblock,blockcount,refcount,cowflag]
        1:[65780,1,2,0] 2:[65781,1,3,0] 3:[65785,2,2,0] 4:[66640,1,2,0]
        5:[69602,4,2,0] 6:[72256,16,2,0] 7:[72871,4,2,0] 8:[72879,20,2,0]
        9:[73395,4,2,0] 10:[75063,4,2,0] 11:[79093,4,2,0] 12:[86344,16,2,0]
        ...
        80:[35235,10,1,1]

Notice record 80. The copy on write flag is set and the reference count is 1, which indicates that the extent 35,235 - 35,244 are being used to stage a copy on write activity. The "cowflag" field is the high bit of rc_startblock.

Record 6 in the reference count B+tree for AG 0 indicates that the AG extent starting at block 72,256 and running for 16 blocks has a reference count of 2. This means that there are two files sharing the block:

xfs_db> blockget -n
xfs_db> fsblock 72256
xfs_db> blockuse
block 72256 (0/72256) type rldata inode 25169197

The blockuse type changes to “rldata” to indicate that the block is shared data. Unfortunately, blockuse only tells us about one block owner. If we happen to have enabled the reverse-mapping B+tree, we can use it to find all inodes that own this block:

xfs_db> agf 0
xfs_db> addr rmaproot
...
xfs_db> addr ptrs[3]
...
xfs_db> addr ptrs[7]
xfs_db> p
magic = 0x524d4233
level = 0
numrecs = 22
leftsib = 65057
rightsib = 65058
bno = 291478
lsn = 0x200004ec2
uuid = f1f89746-e00b-49c9-96b3-ecef0f2f14ae
owner = 0
crc = 0xed7da3f7 (correct)
recs[1-22] = [startblock,blockcount,owner,offset,extentflag,attrfork,bmbtblock]
        1:[68957,8,3201,0,0,0,0] 2:[68965,4,25260953,0,0,0,0]
        ...
        18:[72232,58,3227,0,0,0,0] 19:[72256,16,25169197,24,0,0,0]
        20:[72290,75,3228,0,0,0,0] 21:[72365,46,3229,0,0,0,0]

Records 18 and 19 intersect the block 72,256; they tell us that inodes 3,227 and 25,169,197 both claim ownership. Let us confirm this:

xfs_db> inode 25169197
xfs_db> bmap
data offset 0 startblock 12632259 (3/49347) count 24 flag 0
data offset 24 startblock 72256 (0/72256) count 16 flag 0
data offset 40 startblock 12632299 (3/49387) count 18 flag 0
xfs_db> inode 3227
xfs_db> bmap
data offset 0 startblock 72232 (0/72232) count 58 flag 0

Inodes 25,169,197 and 3,227 both contain mappings to block 0/72,256.

A transaction header is an operation payload that starts a transaction.

typedef struct xfs_trans_header {
     uint                      th_magic;
     uint                      th_type;
     __int32_t                 th_tid;
     uint                      th_num_items;
} xfs_trans_header_t;

The next two operation types work together to handle the freeing of filesystem blocks. Naturally, the ranges of blocks to be freed can be expressed in terms of extents:

typedef struct xfs_extent_32 {
     __uint64_t                ext_start;
     __uint32_t                ext_len;
} __attribute__((packed)) xfs_extent_32_t;

typedef struct xfs_extent_64 {
     __uint64_t                ext_start;
     __uint32_t                ext_len;
     __uint32_t                ext_pad;
} xfs_extent_64_t;

The “extent freeing intent” operation comes first; it tells the log that XFS wants to free some extents. This record is crucial for correct log recovery because it prevents the log from replaying blocks that are subsequently freed. If the log lacks a corresponding “extent freeing done” operation, the recovery process will free the extents.

typedef struct xfs_efi_log_format {
     __uint16_t                efi_type;
     __uint16_t                efi_size;
     __uint32_t                efi_nextents;
     __uint64_t                efi_id;
     xfs_extent_t              efi_extents[1];
} xfs_efi_log_format_t;

The “extent freeing done” operation complements the “extent freeing intent” operation. This second operation indicates that the block freeing actually happened, so that log recovery needn’t try to free the blocks. Typically, the operations to update the free space B+trees follow immediately after the EFD.

typedef struct xfs_efd_log_format {
     __uint16_t                efd_type;
     __uint16_t                efd_size;
     __uint32_t                efd_nextents;
     __uint64_t                efd_efi_id;
     xfs_extent_t              efd_extents[1];
} xfs_efd_log_format_t;

The next two operation types work together to handle deferred reverse mapping updates. Naturally, the mappings to be updated can be expressed in terms of mapping extents:

struct xfs_map_extent {
     __uint64_t                me_owner;
     __uint64_t                me_startblock;
     __uint64_t                me_startoff;
     __uint32_t                me_len;
     __uint32_t                me_flags;
};

The “rmap update intent” operation comes first; it tells the log that XFS wants to update some reverse mappings. This record is crucial for correct log recovery because it enables us to spread a complex metadata update across multiple transactions while ensuring that a crash midway through the complex update will be replayed fully during log recovery.

struct xfs_rui_log_format {
     __uint16_t                rui_type;
     __uint16_t                rui_size;
     __uint32_t                rui_nextents;
     __uint64_t                rui_id;
     struct xfs_map_extent     rui_extents[1];
};

The “reverse mapping update done” operation complements the “reverse mapping update intent” operation. This second operation indicates that the update actually happened, so that log recovery needn’t replay the update. The RUD and the actual updates are typically found in a new transaction following the transaction in which the RUI was logged.

struct xfs_rud_log_format {
      __uint16_t               rud_type;
      __uint16_t               rud_size;
      __uint32_t               __pad;
      __uint64_t               rud_rui_id;
};

The next two operation types work together to handle reference count updates. Naturally, the ranges of extents having reference count updates can be expressed in terms of physical extents:

struct xfs_phys_extent {
     __uint64_t                pe_startblock;
     __uint32_t                pe_len;
     __uint32_t                pe_flags;
};

The “reference count update intent” operation comes first; it tells the log that XFS wants to update some reference counts. This record is crucial for correct log recovery because it enables us to spread a complex metadata update across multiple transactions while ensuring that a crash midway through the complex update will be replayed fully during log recovery.

struct xfs_cui_log_format {
     __uint16_t                cui_type;
     __uint16_t                cui_size;
     __uint32_t                cui_nextents;
     __uint64_t                cui_id;
     struct xfs_map_extent     cui_extents[1];
};

The “reference count update done” operation complements the “reference count update intent” operation. This second operation indicates that the update actually happened, so that log recovery needn’t replay the update. The CUD and the actual updates are typically found in a new transaction following the transaction in which the CUI was logged.

struct xfs_cud_log_format {
      __uint16_t               cud_type;
      __uint16_t               cud_size;
      __uint32_t               __pad;
      __uint64_t               cud_cui_id;
};

The next two operation types work together to handle deferred file block mapping updates. The extents to be mapped are expressed via the xfs_map_extent structure discussed in the section about reverse mapping intents.

The lower byte of the me_flags field is a type code indicating what sort of file block mapping operation we want. The upper three bytes are flag bits.

The “file block mapping update intent” operation comes first; it tells the log that XFS wants to map or unmap some extents in a file. This record is crucial for correct log recovery because it enables us to spread a complex metadata update across multiple transactions while ensuring that a crash midway through the complex update will be replayed fully during log recovery.

struct xfs_bui_log_format {
     __uint16_t                bui_type;
     __uint16_t                bui_size;
     __uint32_t                bui_nextents;
     __uint64_t                bui_id;
     struct xfs_map_extent     bui_extents[1];
};

The “file block mapping update done” operation complements the “file block mapping update intent” operation. This second operation indicates that the update actually happened, so that log recovery needn’t replay the update. The BUD and the actual updates are typically found in a new transaction following the transaction in which the BUI was logged.

struct xfs_bud_log_format {
      __uint16_t               bud_type;
      __uint16_t               bud_size;
      __uint32_t               __pad;
      __uint64_t               bud_bui_id;
};

The next two operation types work together to handle atomic extended attribute updates.

The lower byte of the alfi_op_flags field is a type code indicating what sort of file block mapping operation we want.

The “extended attribute update intent” operation comes first; it tells the log that XFS wants to update one of a file’s extended attributes. This record is crucial for correct log recovery because it enables us to spread a complex metadata update across multiple transactions while ensuring that a crash midway through the complex update will be replayed fully during log recovery.

struct xfs_attri_log_format {
     uint16_t                  alfi_type;
     uint16_t                  alfi_size;
     uint32_t                  alfi_igen;
     uint64_t                  alfi_id;
     uint64_t                  alfi_ino;
     uint32_t                  alfi_op_flags;
     union {
          uint32_t             alfi_name_len;
          struct {
              uint16_t         alfi_old_name_len;
              uint16_t         alfi_new_name_len;
          };
     };
     uint32_t                  alfi_value_len;
     uint32_t                  alfi_attr_filter;
};

For a SET or REPLACE opcode, there should be two regions after the ATTRI intent item. The first region contains the attribute name and the second contains the attribute value.

For a REMOVE opcode, there should only be one region after the ATTRI intent item, and it will contain the attribute name.

For an PPTR_SET or PPTR_REMOVE opcode, there should be two regions after the ATTRI intent item. The first region contains the dirent name as the attribute name. The second region contains a file handle to the parent directory as the attribute value.

For an PPTR_REPLACE opcode, there should be between four regions after the ATTRI intent item. The first region contains the dirent name to remove. The second region contains the dirent name to create. The third region contains the parent directory file handle to remove. The fourth region contains the parent directory file handle to add.

The “extended attribute update done” operation complements the “extended attribute update intent” operation. This second operation indicates that the update actually happened, so that log recovery needn’t replay the update. The ATTRD and the actual updates are typically found in a new transaction following the transaction in which the ATTRI was logged.

struct xfs_attrd_log_format {
      __uint16_t               alfd_type;
      __uint16_t               alfd_size;
      __uint32_t               __pad;
      __uint64_t               alfd_alf_id;
};

These regions contain the name and value components of the extended attribute being updated, as needed. There are no magic numbers; each region contains the data and nothing else.

These two log items work together to track the exchange of mapped extents between the forks of two files. Each operation requires a separate XMI/XMD pair. The log intent item has the following format:

struct xfs_xmi_log_format {
     uint16_t                  xmi_type;
     uint16_t                  xmi_size;
     uint32_t                  __pad;
     uint64_t                  xmi_id;
     uint64_t                  xmi_inode1;
     uint64_t                  xmi_inode2;
     uint32_t                  xmi_igen1;
     uint32_t                  xmi_igen2;
     uint64_t                  xmi_startoff1;
     uint64_t                  xmi_startoff2;
     uint64_t                  xmi_blockcount;
     uint64_t                  xmi_flags;
     int64_t                   xmi_isize1;
     int64_t                   xmi_isize2;
};

The “file mapping exchange done” operation complements the “file mapping exchange intent” operation. This second operation indicates that the update actually happened, so that log recovery needn’t replay the update. The XMD item and the actual updates are typically found in a new transaction following the transaction in which the XMI was logged. The completion has this format:

struct xfs_xmd_log_format {
     uint16_t                  xmd_type;
     uint16_t                  xmd_size;
     uint32_t                  __pad;
     uint64_t                  xmd_xmi_id;
};

This operation records changes to an inode record. There are several types of inode updates, each corresponding to different parts of the inode record. Allowing updates to proceed at a sub-inode granularity reduces contention for the inode, since different parts of the inode can be updated simultaneously.

The actual buffer data are stored in subsequent log items.

The inode log format header is as follows:

typedef struct xfs_inode_log_format_64 {
     __uint16_t                ilf_type;
     __uint16_t                ilf_size;
     __uint32_t                ilf_fields;
     __uint16_t                ilf_asize;
     __uint16_t                ilf_dsize;
     __uint32_t                ilf_pad;
     __uint64_t                ilf_ino;
     union {
          __uint32_t           ilfu_rdev;
          uuid_t               ilfu_uuid;
     } ilf_u;
     __int64_t                 ilf_blkno;
     __int32_t                 ilf_len;
     __int32_t                 ilf_boffset;
} xfs_inode_log_format_64_t;

Be aware that there is a nearly identical xfs_inode_log_format_32 which may appear on disk. It is the same as xfs_inode_log_format_64, except that it is missing the ilf_pad field and is 52 bytes long as opposed to 56 bytes.

This region contains the new contents of a part of an inode, as described in the previous section. There are no magic numbers.

If XFS_ILOG_CORE is set in ilf_fields, the corresponding data buffer must be in the format struct xfs_icdinode, which has the same format as the first 96 bytes of an inode, but is recorded in host byte order.

This operation writes parts of a buffer to disk. The regions to write are tracked in the data map; the actual buffer data are stored in subsequent log items.

typedef struct xfs_buf_log_format {
     unsigned short            blf_type;
     unsigned short            blf_size;
     ushort                    blf_flags;
     ushort                    blf_len;
     __int64_t                 blf_blkno;
     unsigned int              blf_map_size;
     unsigned int              blf_data_map[XFS_BLF_DATAMAP_SIZE];
} xfs_buf_log_format_t;

This region contains the new contents of a part of a buffer, as described in the previous section. There are no magic numbers.

This updates a block in a quota file. The buffer data must be in the next log item.

typedef struct xfs_dq_logformat {
     __uint16_t                qlf_type;
     __uint16_t                qlf_size;
     xfs_dqid_t                qlf_id;
     __int64_t                 qlf_blkno;
     __int32_t                 qlf_len;
     __uint32_t                qlf_boffset;
} xfs_dq_logformat_t;

This region contains the new contents of a part of a buffer, as described in the previous section. There are no magic numbers.

A request to disable quota controls has the following format:

typedef struct xfs_qoff_logformat {
     unsigned short            qf_type;
     unsigned short            qf_size;
     unsigned int              qf_flags;
     char                      qf_pad[12];
} xfs_qoff_logformat_t;

This log item is created when inodes are allocated in-core. When replaying this item, the specified inode records will be zeroed and some of the inode fields populated with default values.

struct xfs_icreate_log {
     __uint16_t                icl_type;
     __uint16_t                icl_size;
     __be32                    icl_ag;
     __be32                    icl_agbno;
     __be32                    icl_count;
     __be32                    icl_isize;
     __be32                    icl_length;
     __be32                    icl_gen;
};

This example shows a metadta directory from a freshly formatted root filesystem:

xfs_db> sb 0
xfs_db> p
magicnum = 0x58465342
blocksize = 4096
dblocks = 5192704
rblocks = 0
rextents = 0
uuid = cbf2ceef-658e-46b0-8f96-785661c37976
logstart = 4194311
rootino = 128
rbmino = 130
rsumino = 131
...
meta_uuid = 00000000-0000-0000-0000-000000000000
metadirino = 129
...

Notice how the listing includes the root of the metadata directory tree (metadirino).

xfs_db> path -m /
xfs_db> ls
8          129                directory      0x0000002e   1 . (good)
10         129                directory      0x0000172e   2 .. (good)
12         33685632           directory      0x2d18ab4c   8 rtgroups (good)

Here we use the path and ls commands to display the root directory of the metadata directory. We can navigate the directory the old way, too:

xfs_db> p
core.magic = 0x494e
core.mode = 040000
core.version = 3
core.format = 1 (local)
core.onlink = 0
core.uid = 0
core.gid = 0
...
v3.flags2 = 0x8000000000000018
v3.cowextsize = 0
v3.crtime.sec = Wed Aug  7 10:22:36 2024
v3.crtime.nsec = 273744000
v3.inumber = 129
v3.uuid = 7e55b909-8728-4d69-a1fa-891427314eea
v3.reflink = 0
v3.cowextsz = 0
v3.dax = 0
v3.bigtime = 1
v3.nrext64 = 1
v3.metadata = 1
u3.sfdir3.hdr.count = 1
u3.sfdir3.hdr.i8count = 0
u3.sfdir3.hdr.parent.i4 = 129
u3.sfdir3.list[0].namelen = 8
u3.sfdir3.list[0].offset = 0x60
u3.sfdir3.list[0].name = "rtgroups"
u3.sfdir3.list[0].inumber.i4 = 33685632
u3.sfdir3.list[0].filetype = 2

The root of the metadata directory is a short format directory, and looks just like any other directory. The only difference is that the metadata flag is set, and the directory can only be viewed in the XFS debugger.

xfs_db> path -m /rtgroups/0.rmap
btdump
u3.rtrmapbt.recs[1] = [startblock,blockcount,owner,offset,extentflag,attrfork,bmbtblock]
1:[0,1,-3,0,0,0,0]

Observe that we can use the xfs_db path command to navigate the metadata directory tree to the user quota file and display its contents.

This example shows a real-time bitmap file from a freshly populated filesystem:

xfs_db> path -m /rtgroups/3.bitmap
xfs_db> p
core.magic = 0x494e
core.mode = 0100000
core.version = 3
core.format = 2 (extents)
core.metatype = 5 (rtbitmap)
core.uid = 0
core.gid = 0
core.nlinkv2 = 1
core.projid_lo = 3
core.projid_hi = 0
core.nextents = 1
core.atime.sec = Tue Oct 15 16:04:02 2024
core.atime.nsec = 769675000
core.mtime.sec = Tue Oct 15 16:04:02 2024
core.mtime.nsec = 769675000
core.ctime.sec = Tue Oct 15 16:04:02 2024
core.ctime.nsec = 769681000
core.size = 135168
core.nblocks = 33
core.extsize = 0
core.naextents = 0
core.forkoff = 24
core.aformat = 1 (local)
core.dmevmask = 0
core.dmstate = 0
core.newrtbm = 0
core.prealloc = 0
core.realtime = 0
core.immutable = 1
core.append = 0
core.sync = 1
core.noatime = 1
core.nodump = 1
core.rtinherit = 0
core.projinherit = 0
core.nosymlinks = 0
core.extsz = 0
core.extszinherit = 0
core.nodefrag = 1
core.filestream = 0
core.gen = 2653591217
next_unlinked = null
v3.crc = 0x34a17119 (correct)
v3.change_count = 3
v3.lsn = 0
v3.flags2 = 0x38
v3.cowextsize = 0
v3.crtime.sec = Tue Oct 15 16:04:02 2024
v3.crtime.nsec = 769675000
v3.inumber = 33685633
v3.uuid = a6575f59-1514-445e-883e-211b2c5a0f05
v3.reflink = 0
v3.cowextsz = 0
v3.dax = 0
v3.bigtime = 1
v3.nrext64 = 1
v3.metadata = 1
u3.bmx[0] = [startoff,startblock,blockcount,extentflag]
0:[0,4210712,33,0]
a.sfattr.hdr.totsize = 27
a.sfattr.hdr.count = 1
a.sfattr.list[0].namelen = 8
a.sfattr.list[0].valuelen = 12
a.sfattr.list[0].root = 0
a.sfattr.list[0].secure = 0
a.sfattr.list[0].parent = 1
a.sfattr.list[0].name = "0.bitmap"
a.sfattr.list[0].parent_dir.inumber = 33685632
a.sfattr.list[0].parent_dir.gen = 142228546
xfs_db> dblock 0
xfs_db> p
magicnum = 0x424d505a
crc = 0xc8b10abf (correct)
owner = 33685633
bno = 20902080
lsn = 0x100007696
uuid = a6575f59-1514-445e-883e-211b2c5a0f05
rtwords[0-1011] = 0:0 1:0 2:0 3:0 4:0 5:0 6:0 7:0 8:0 9:0 10:0 11:0 12:0 13:0
14:0 15:0 16:0 17:0 18:0 19:0 20:0 21:0xfffff800 22:0xffffffff 23:0xffffffff
24:0xffffffff 25:0xffffffff 26:0xffffffff 27:0xffffffff 28:0xffffffff
29:0xffffffff 30:0xffffffff 31:0xffffffff 32:0xffffffff
...
979:0xffffffff 980:0xffffffff 981:0xffffffff 982:0xffffffff 983:0xffffffff
984:0xffffffff 985:0xffffffff 986:0xffffffff 987:0xffffffff 988:0xffffffff
989:0xffffffff 990:0xffffffff 991:0xffffffff 992:0xffffffff 993:0xffffffff
994:0xffffffff 995:0xffffffff 996:0xffffffff 997:0xffffffff 998:0xffffffff
999:0xffffffff 1000:0xffffffff 1001:0xffffffff 1002:0xffffffff 1003:0xffffffff
1004:0xffffffff 1005:0xffffffff 1006:0xffffffff 1007:0xffffffff 1008:0xffffffff
1009:0xffffffff 1010:0xffffffff 1011:0xffffffff

From this example, we can clearly see that this is a bitmap file in the metadata directory tree, and that it is the bitmap file for rtgroup 3. When we access the first block in the bitmap file, we can clearly see the new block header and that the first 179 extents are allocated. The bitmap words were excerpted for brevity.

This example shows a real-time summary file from a freshly populated filesystem:

xfs_db> path -m /rtgroups/3.summary
xfs_db> p
core.magic = 0x494e
core.mode = 0100000
core.version = 3
core.format = 2 (extents)
core.metatype = 6 (rtsummary)
core.uid = 0
core.gid = 0
core.nlinkv2 = 1
core.projid_lo = 3
core.projid_hi = 0
core.nextents = 1
core.atime.sec = Tue Oct 15 16:04:02 2024
core.atime.nsec = 769694000
core.mtime.sec = Tue Oct 15 16:04:02 2024
core.mtime.nsec = 769694000
core.ctime.sec = Tue Oct 15 16:04:02 2024
core.ctime.nsec = 769699000
core.size = 4096
core.nblocks = 1
core.extsize = 0
core.naextents = 0
core.forkoff = 24
core.aformat = 1 (local)
core.dmevmask = 0
core.dmstate = 0
core.newrtbm = 0
core.prealloc = 0
core.realtime = 0
core.immutable = 1
core.append = 0
core.sync = 1
core.noatime = 1
core.nodump = 1
core.rtinherit = 0
core.projinherit = 0
core.nosymlinks = 0
core.extsz = 0
core.extszinherit = 0
core.nodefrag = 1
core.filestream = 0
core.gen = 519466891
next_unlinked = null
v3.crc = 0x54fc58d0 (correct)
v3.change_count = 3
v3.lsn = 0
v3.flags2 = 0x38
v3.cowextsize = 0
v3.crtime.sec = Tue Oct 15 16:04:02 2024
v3.crtime.nsec = 769694000
v3.inumber = 33685634
v3.uuid = a6575f59-1514-445e-883e-211b2c5a0f05
v3.reflink = 0
v3.cowextsz = 0
v3.dax = 0
v3.bigtime = 1
v3.nrext64 = 1
v3.metadata = 1
u3.bmx[0] = [startoff,startblock,blockcount,extentflag]
0:[0,4210703,1,0]
a.sfattr.hdr.totsize = 28
a.sfattr.hdr.count = 1
a.sfattr.list[0].namelen = 9
a.sfattr.list[0].valuelen = 12
a.sfattr.list[0].root = 0
a.sfattr.list[0].secure = 0
a.sfattr.list[0].parent = 1
a.sfattr.list[0].name = "0.summary"
a.sfattr.list[0].parent_dir.inumber = 33685632
a.sfattr.list[0].parent_dir.gen = 142228546
xfs_db> dblock 0
xfs_db> p
magicnum = 0x53554d59
crc = 0x473340a8 (correct)
owner = 33685634
bno = 20902008
lsn = 0x100007696
uuid = a6575f59-1514-445e-883e-211b2c5a0f05
suminfo[0-1011] = 0:0 1:0 2:0 3:0 4:0 5:0 6:0 7:0 8:0 9:0 10:0 11:0 12:0 13:0
14:0 15:0 16:0 17:0 18:0 19:0 20:0 21:0 22:0 23:0 24:0 25:0 26:0 27:0 28:0 29:0
30:0 31:0 32:0
...
618:0 619:0 620:0 621:0 622:0 623:0 624:0 625:0 626:0 627:1 628:0 629:0 630:0
...
979:0 980:0 981:0 982:0 983:0 984:0 985:0 986:0 987:0 988:0 989:0 990:0 991:0
992:0 993:0 994:0 995:0 996:0 997:0 998:0 999:0 1000:0 1001:0 1002:0 1003:0
1004:0 1005:0 1006:0 1007:0 1008:0 1009:0 1010:0 1011:0

From this example, we can clearly see that this is a summary file in the metadata directory tree, and that it is the summary file for rtgroup 3. When we access the first block in the summary file, we can clearly see the new block header and the nonzero counter for the one large free extent in this group. The summary counts were excerpted for brevity.

The first block of each realtime group contains a superblock. These fields must match their counterparts in the filesystem superblock on the data device.

struct xfs_rtsb {
        __be32          rsb_magicnum;
        __le32          rsb_crc;

        __be32          rsb_pad;
        unsigned char   rsb_fname[XFSLABEL_MAX];

        uuid_t          rsb_uuid;
        uuid_t          rsb_meta_uuid;

        /* must be padded to 64 bit alignment */
};

# mkfs.xfs -r rtgroups=1,rgcount=4,rtdev=/dev/sdb /dev/sda -f
meta-data=/dev/sda               isize=512    agcount=4, agsize=1298176 blks
         =                       sectsz=512   attr=2, projid32bit=1
         =                       crc=1        finobt=1, sparse=1, rmapbt=1
         =                       reflink=1    bigtime=1 inobtcount=1 nrext64=1
         =                       metadir=1
data     =                       bsize=4096   blocks=5192704, imaxpct=25
         =                       sunit=0      swidth=0 blks
naming   =version 2              bsize=4096   ascii-ci=0, ftype=1
log      =internal log           bsize=4096   blocks=16384, version=2
         =                       sectsz=512   sunit=0 blks, lazy-count=1
realtime =/dev/sdb               extsz=4096   blocks=5192704, rtextents=5192704
         =                       rgcount=5    rgsize=1048576 extents

# xfs_db -R /dev/sdb /dev/sda
xfs_db> rtsb
xfs_db> print
magicnum = 0x46726f67
crc = 0x759a62d4 (correct)
pad = 0
fname = "\000\000\000\000\000\000\000\000\000\000\000\000"
uuid = 7e55b909-8728-4d69-a1fa-891427314eea
meta_uuid = 7e55b909-8728-4d69-a1fa-891427314eea

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 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:

struct xfs_rtrmap_root {
     __be16                     bb_level;
     __be16                     bb_numrecs;
};

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

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;
};

The key has the following structure:

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;
};

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]

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

If the reflink and real-time storage device features are enabled, each real-time group has its own reference count B+tree.

As mentioned in the chapter about sharing data blocks, this data structure is necessary to track how many times each extent in the realtime volume has been mapped. This is how the copy-on-write code determines what to do when a realtime file is written.

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

The rtgroup reference count B+tree is rooted in an inode’s data fork; the inode number can be found by resolving the path /rtgroups/$rgno.refcount in the metadata directory tree. superblock. The B+tree blocks themselves are stored in the regular filesystem. The structures used for an inode’s B+tree root are:

struct xfs_rtrefcount_root {
     __be16                     bb_level;
     __be16                     bb_numrecs;
};

Each record in an rtgroup reference count B+tree has the same structure as an AG reference count btree:

struct xfs_refcount_rec {
     __be32                     rc_startblock;
     __be32                     rc_blockcount;
     __be32                     rc_refcount;
};

The key has the following structure:

struct xfs_refcount_key {
     __be32                     rc_startblock;
};

xfs_db> path -m /rtgroups/0.refcount
xfs_db> p
core.magic = 0x494e
core.mode = 0100000
core.version = 3
core.format = 6 (refcount)
...
v3.inumber = 134
v3.uuid = 23d157a4-8ca7-4fca-8782-637dc6746105
v3.reflink = 0
v3.cowextsz = 0
v3.dax = 0
v3.bigtime = 1
v3.nrext64 = 1
v3.metadata = 1
u3.rtrefcbt.level = 1
u3.rtrefcbt.numrecs = 2
u3.rtrefcbt.keys[1-2] = [startblock,cowflag]
1:[4,0]
2:[344,0]
u3.rtrefcbt.ptrs[1-2] = 1:8 2:9

xfs_db> addr u3.rtrefcbt.ptrs[2]
xfs_db> p
magic = 0x52434e54
level = 0
numrecs = 170
leftsib = 8
rightsib = null
bno = 72
lsn = 0
uuid = 23d157a4-8ca7-4fca-8782-637dc6746105
owner = 134
crc = 0x21e04c3 (correct)
recs[1-170] = [startblock,blockcount,refcount,cowflag]
1:[344,1,2,0]
2:[346,1,2,0]
3:[348,1,2,0]
4:[350,1,2,0]
5:[352,1,2,0]
6:[354,1,2,0]
...

xfs_db> fsmap -r 354 354
0: 0/1 len 682 owner 10015 offset 0 bmbt 0 attrfork 0 extflag 0
1: 0/354 len 1 owner 10014 offset 353 bmbt 0 attrfork 0 extflag 0

xfs_db> inode 10015
xfs_db> p core.realtime
core.realtime = 1
xfs_db> bmap
data offset 0 startblock 1 (0/1) count 682 flag 0
xfs_db> inode 10014
xfs_db> p core.realtime
core.realtime = 1
xfs_db> bmap 350 10
data offset 351 startblock 352 (0/352) count 1 flag 0
data offset 353 startblock 354 (0/354) count 1 flag 0
data offset 355 startblock 356 (0/356) count 1 flag 0
data offset 357 startblock 358 (0/358) count 1 flag 0
data offset 359 startblock 360 (0/360) count 1 flag 0

The data fork specifies the file’s data extents. The extents specify where the file’s actual data is located within the filesystem. Extents can have 2 formats which is defined by the di_format value:

Details for each of these data extent formats are covered in the Data Extents later on.

The data fork contains the directory’s entries and associated data. The format of the entries is also determined by the di_format value and can be one of 3 formats:

Details for each of these directory formats are covered in the Directories later on.

The data fork contains the contents of the symbolic link. The format of the link is determined by the di_format value and can be one of 2 formats:

Details for symbolic links is covered in the section about Symbolic Links.

For character and block devices (S_IFCHR and S_IFBLK), cast the value from XFS_DFORK_DPTR to xfs_dev_t*.

Extended attributes come in two versions: “attr1” or “attr2”. The attribute version is specified by the XFS_SB_VERSION2_ATTR2BIT  flag in the sb_features2 field in the superblock. It determines how the inode’s extra space is split between di_u and di_a forks which also determines how the di_forkoff value is maintained in the inode’s core.

With “attr1” attributes, the di_forkoff is set to somewhere in the middle of the space between the core and end of the inode and never changes (which has the effect of artificially limiting the space for data information). As the data fork grows, when it gets to di_forkoff, it will move the data to the next format level (ie. local < extent < btree). If very little space is used for either attributes or data, then a good portion of the available inode space is wasted with this version.

“attr2” was introduced to maximum the utilisation of the inode’s literal area. The di_forkoff starts at the end of the inode and works its way to the data fork as attributes are added. Attr2 is highly recommended if extended attributes are used.

The following diagram compares the two versions:

Figure 18.3. Extended attribute layouts

Note that because di_forkoff is an 8-bit value measuring units of 8 bytes, the maximum size of an inode is 2⁸ × 2³ = 2¹¹ = 2048 bytes.

An 8MB file with one extent:

xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 0100644
core.version = 1
core.format = 2 (extents)
...
core.size = 8294400
core.nblocks = 2025
core.extsize = 0
core.nextents = 1
core.naextents = 0
core.forkoff = 0
...
u.bmx[0] = [startoff,startblock,blockcount,extentflag]
        0:[0,25356,2025,0]

A 24MB file with three extents:

xfs_db> inode <inode#>
xfs_db> p
...
core.format = 2 (extents)
...
core.size = 24883200
core.nblocks = 6075
core.nextents = 3
...
u.bmx[0-2] = [startoff,startblock,blockcount,extentflag]
        0:[0,27381,2025,0]
        1:[2025,31431,2025,0]
        2:[4050,35481,2025,0]

Raw disk version of the inode with the third extent highlighted (di_u starts at offset 0x64):

xfs_db> type text
xfs_db> p
00: 49 4e 81 a4 01 02 00 01 00 00 00 00 00 00 00 00 IN..............
10: 00 00 00 01 00 00 00 00 00 00 00 00 00 00 00 01 ................
20: 44 b6 88 dd 2f 8a ed d0 44 b6 88 f7 10 8c 5b de D.......D.......
30: 44 b6 88 f7 10 8c 5b d0 00 00 00 00 01 7b b0 00 D...............
40: 00 00 00 00 00 00 17 bb 00 00 00 00 00 00 00 03 ................
50: 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00 00 ................
60: ff ff ff ff 00 00 00 00 00 00 00 00 00 00 00 0d ................
70: 5e a0 07 e9 00 00 00 00 00 0f d2 00 00 00 00 0f ................
80: 58 e0 07 e9 00 00 00 00 00 1f a4 00 00 00 00 11 X...............
90: 53 20 07 e9 00 00 00 00 00 00 00 00 00 00 00 00 S...............
a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
be: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
co: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
do: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
fo: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................

We can expand the highlighted section into the following bit array from MSB to LSB with the file offset and the block count highlighted:

127-96:  0000 0000 0000 0000  0000 0000 0000 0000
 95-64:  0000 0000 0001 1111  1010 0100 0000 0000
 63-32:  0000 0000 0000 0000  0000 0000 0000 1111
 31-0 :  0101 1000 1110 0000  0000 0111 1110 1001

Grouping by highlights we get:
   file offset = 0x0fd2 (4050)
   start block = 0x7ac7 (31431)
   block count = 0x07e9 (2025)

A 4MB file with two extents and a hole in the middle, the first extent containing 64KB of data, the second about 4MB in containing 32KB (write 64KB, lseek 4MB, write 32KB operations):

xfs_db> inode <inode#>
xfs_db> p
...
core.format = 2 (extents)
...
core.size = 4063232
core.nblocks = 24
core.nextents = 2
...
u.bmx[0-1] = [startoff,startblock,blockcount,extentflag]
        0:[0,37506,16,0]
        1:[984,37522,8,0]

In this example, we dissect the data fork of a VM image that is sufficiently sparse and interleaved to have become a B+tree.

xfs_db> inode 132
xfs_db> p
core.magic = 0x494e
core.mode = 0100600
core.version = 3
core.format = 3 (btree)
...
u3.bmbt.level = 1
u3.bmbt.numrecs = 3
u3.bmbt.keys[1-3] = [startoff] 1:[0] 2:[9072] 3:[13136]
u3.bmbt.ptrs[1-3] = 1:8568 2:8569 3:8570

As you can see, the block map B+tree is rooted in the inode. This tree has two levels, so let’s go down a level to look at the records:

xfs_db> addr u3.bmbt.ptrs[1]
xfs_db> p
magic = 0x424d4133
level = 0
numrecs = 251
leftsib = null
rightsib = 8569
bno = 68544
lsn = 0x100000006
uuid = 9579903c-333f-4673-a7d4-3254c05816ea
owner = 132
crc = 0xc61513dc (correct)
recs[1-251] = [startoff,startblock,blockcount,extentflag]
        1:[0,8520,48,0] 2:[48,4421,16,0] 3:[80,9136,16,0] 4:[96,8569,16,0]
        5:[144,8601,32,0] 6:[192,8637,16,0] 7:[240,8680,16,0] 8:[288,9870,16,0]
        9:[320,9920,16,0] 10:[336,9950,16,0] 11:[384,4004,32,0]
        12:[432,6771,16,0] 13:[480,2702,16,0] 14:[528,8420,16,0]
        ...

A directory is created with 4 files, all inode numbers fitting within 4 bytes:

xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 1 (local)
core.nlinkv1 = 2
...
core.size = 94
core.nblocks = 0
core.extsize = 0
core.nextents = 0
...
u.sfdir2.hdr.count = 4
u.sfdir2.hdr.i8count = 0
u.sfdir2.hdr.parent.i4 = 128              /* parent = root inode */
u.sfdir2.list[0].namelen = 15
u.sfdir2.list[0].offset = 0x30
u.sfdir2.list[0].name = "frame000000.tst"
u.sfdir2.list[0].inumber.i4 = 25165953
u.sfdir2.list[1].namelen = 15
u.sfdir2.list[1].offset = 0x50
u.sfdir2.list[1].name = "frame000001.tst"
u.sfdir2.list[1].inumber.i4 = 25165954
u.sfdir2.list[2].namelen = 15
u.sfdir2.list[2].offset = 0x70
u.sfdir2.list[2].name = "frame000002.tst"
u.sfdir2.list[2].inumber.i4 = 25165955
u.sfdir2.list[3].namelen = 15
u.sfdir2.list[3].offset = 0x90
u.sfdir2.list[3].name = "frame000003.tst"
u.sfdir2.list[3].inumber.i4 = 25165956

The raw data on disk with the first entry highlighted. The six byte header precedes the first entry:

xfs_db> type text
xfs_db> p
00: 49 4e 41 ed 01 01 00 02 00 00 00 00 00 00 00 00 INA.............
10: 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00 02 ................
20: 44 ad 3a 83 1d a9 4a d0 44 ad 3a ab 0b c7 a7 d0 D.....J.D.......
30: 44 ad 3a ab 0b c7 a7 d0 00 00 00 00 00 00 00 5e D...............
40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
50: 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00 00 ................
60: ff ff ff ff 04 00 00 00 00 80 0f 00 30 66 72 61 ............0fra
70: 6d 65 30 30 30 30 30 30 2e 74 73 74 01 80 00 81 me000000.tst....
80: 0f 00 50 66 72 61 6d 65 30 30 30 30 30 31 2e 74 ..Pframe000001.t
90: 73 74 01 80 00 82 0f 00 70 66 72 61 6d 65 30 30 st......pframe00
a0: 30 30 30 32 2e 74 73 74 01 80 00 83 0f 00 90 66 0002.tst........
b0: 72 61 6d 65 30 30 30 30 30 33 2e 74 73 74 01 80 rame000003.tst..
cO: 00 84 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................

Next, an entry is deleted (frame000001.tst), and any entries after the deleted entry are moved or compacted to “cover” the hole:

xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 1 (local)
core.nlinkv1 = 2
...
core.size = 72
core.nblocks = 0
core.extsize = 0
core.nextents = 0
...
u.sfdir2.hdr.count = 3
u.sfdir2.hdr.i8count = 0
u.sfdir2.hdr.parent.i4 = 128
u.sfdir2.list[0].namelen = 15
u.sfdir2.list[0].offset = 0x30
u.sfdir2.list[0].name = "frame000000.tst"
u.sfdir2.list[0].inumber.i4 = 25165953
u.sfdir2.list[1].namelen = 15
u.sfdir2.list[1].offset = 0x70
u.sfdir2.list[1].name = "frame000002.tst"
u.sfdir2.list[1].inumber.i4 = 25165955
u.sfdir2.list[2].namelen = 15
u.sfdir2.list[2].offset = 0x90
u.sfdir2.list[2].name = "frame000003.tst"
u.sfdir2.list[2].inumber.i4 = 25165956

Raw disk data, the space beyond the shortform entries is invalid and could be non-zero:

xfs_db> type text
xfs_db> p
00: 49  4e 41 ed 01 01 00 02 00 00 00 00 00 00 00 00 INA.............
10: 00  00 00 02 00 00 00 00 00 00 00 00 00 00 00 03 ................
20: 44  b2 45 a2 09 fd e4 50 44 b2 45 a3 12 ee b5 d0 D.E....PD.E.....
30: 44  b2 45 a3 12 ee b5 d0 00 00 00 00 00 00 00 48 D.E............H
40: 00  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
50: 00  00 00 02 00 00 00 00 00 00 00 00 00 00 00 00 ................
60: ff  ff ff ff 03 00 00 00 00 80 0f 00 30 66 72 61 ............0fra
70: 6d  65 30 30 30 30 30 30 2e 74 73 74 01 80 00 81 me000000.tst....
80: 0f  00 70 66 72 61 6d 65 30 30 30 30 30 32 2e 74 ..pframe000002.t
90: 73  74 01 80 00 83 0f 00 90 66 72 61 6d 65 30 30 st.......frame00
a0: 30  30 30 33 2e 74 73 74 01 80 00 84 0f 00 90 66 0003.tst.......f
b0: 72  61 6d 65 30 30 30 30 30 33 2e 74 73 74 01 80 rame000003.tst..
c0: 00  84 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................

This is an example of mixed 4-byte and 8-byte inodes in a directory:

xfs_db> inode 1024
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 3
core.format = 1 (local)
core.nlinkv2 = 9
...
core.size = 125
core.nblocks = 0
core.extsize = 0
core.nextents = 0
...
u3.sfdir3.hdr.count = 7
u3.sfdir3.hdr.i8count = 4
u3.sfdir3.hdr.parent.i8 = 1024
u3.sfdir3.list[0].namelen = 3
u3.sfdir3.list[0].offset = 0x60
u3.sfdir3.list[0].name = "git"
u3.sfdir3.list[0].inumber.i8 = 1027
u3.sfdir3.list[0].filetype = 2
u3.sfdir3.list[1].namelen = 4
u3.sfdir3.list[1].offset = 0x70
u3.sfdir3.list[1].name = "home"
u3.sfdir3.list[1].inumber.i8 = 13422826546
u3.sfdir3.list[1].filetype = 2
u3.sfdir3.list[2].namelen = 10
u3.sfdir3.list[2].offset = 0x80
u3.sfdir3.list[2].name = "mike"
u3.sfdir3.list[2].inumber.i8 = 4299308032
u3.sfdir3.list[2].filetype = 2
u3.sfdir3.list[3].namelen = 3
u3.sfdir3.list[3].offset = 0x98
u3.sfdir3.list[3].name = "mtr"
u3.sfdir3.list[3].inumber.i8 = 13433252916
u3.sfdir3.list[3].filetype = 2
u3.sfdir3.list[4].namelen = 3
u3.sfdir3.list[4].offset = 0xa8
u3.sfdir3.list[4].name = "vms"
u3.sfdir3.list[4].inumber.i8 = 16647516355
u3.sfdir3.list[4].filetype = 2
u3.sfdir3.list[5].namelen = 5
u3.sfdir3.list[5].offset = 0xb8
u3.sfdir3.list[5].name = "rsync"
u3.sfdir3.list[5].inumber.i8 = 3494912
u3.sfdir3.list[5].filetype = 2
u3.sfdir3.list[6].namelen = 3
u3.sfdir3.list[6].offset = 0xd0
u3.sfdir3.list[6].name = "tmp"
u3.sfdir3.list[6].inumber.i8 = 1593379
u3.sfdir3.list[6].filetype = 2