btrfs: backref: detect tree mod log rewind cycles in add_all_parents()

btrfs: backref: detect tree mod log rewind cycles in add_all_parents()

The tree mod log records internal node operations (pointer add/remove/
move and boundary key replaces) but never leaf item changes. A leaf that
was COWed in the current transaction before a tree mod log user took its
sequence number is modified in place afterwards, with no record kept of
its old contents.

As a result, the "old" view of a subvolume tree presented by
btrfs_search_old_slot() and btrfs_next_old_leaf() is only structurally
consistent: rewound internal nodes carry boundary keys as of time_seq,
while the leaves they point at may have newer contents. When items are
redistributed between sibling leaves (push_leaf_left()/push_leaf_right()),
only the resulting boundary key change in the parent is logged (via
fixup_low_keys()) and therefore rewound - the item moves themselves are
invisible to the log.

When the rewound boundary keys disagree with the actual leaf contents,
btrfs_next_old_leaf() - which advances by re-searching the last key of
the current leaf from the top of the tree - can be routed backwards to a
leaf it already visited. Two leaves in that state form a closed cycle:
walking off the end of leaf L lands on leaf M, and searching for M's
last (too-small) key routes back through L to M again. If this happens
while the walked range contains no items matching the backref being
resolved, the item count never reaches ref->count and the loop in
add_all_parents() spins forever. This is easily reproduced by running
LOGICAL_INO_V2 concurrently with heavy clone activity on the same
files: the ioctl's attached transaction handle then blocks the
transaction commit, which drains all writers, freezing the tree in the
inconsistent state and turning the transient loop into a permanent hang
with the fs wedged behind the blocked commit. If a matching item does
fall inside the cycled range instead, the loop exits after counting it
multiple times, silently returning duplicated parents.

In a consistent view of the tree, item keys must strictly increase as
the walk advances. Remember the previously visited key and bail out
with -EAGAIN if the walk ever observes a key that did not increase,
turning both the hang and the silent duplication into an error.

No attempt is made to retry inside the kernel: a retry could only reuse
the same tree mod log sequence number, and when the trees are no longer
being modified (in particular when a transaction commit is draining
writers and waiting for the walker to release its own transaction
handle - exactly the scenario that makes the cycle permanent) an
identical re-walk fails the same way every time. Returning the error
instead releases the caller's transaction handle, which unblocks the
pending commit, and a retry of the ioctl from user space then attaches
a fresh tree mod log sequence number with a consistent baseline. EAGAIN
tells user space precisely that: try again, nothing is corrupted.

The check cannot fire on commit root walks (commit roots are immutable
for the duration of the walk) or on BTRFS_SEQ_LAST walks (run from the
transaction commit critical section, after all other writers have
drained and with delayed refs fully run, so the trees are quiescent): a
consistent tree view can never present non-increasing item keys,
regardless of the size of the walk. So the qgroup accounting done at
transaction commit can never see this error and abort the transaction.
Only walks with a real time_seq can reach it: the LOGICAL_INO ioctls,
which return it to user space, and the sharedness checks done for
fiemap and swap file activation. If the check ever did fire on an
immutable or quiescent tree, it would mean the tree really has out of
order keys, in which case an error is preferable to the alternative of
btrfs_next_leaf() cycling on the damaged keys forever.

btrfs_is_data_extent_shared() cannot retry with a fresh tree mod log
sequence number from that deep in the call chain, and its callers'
interfaces do not expect transient errors, so the error is handled at
the call sites. Nothing is stored in the sharedness caches for a
failed check.

fiemap conservatively reports the extent as shared: the SHARED flag is
best effort by design, and while the extent's trees are being
concurrently modified, any sharedness answer may be stale by the time
user space sees it anyway.

Swap file activation also fails, with the error converted to the same
-EINVAL that a really shared extent produces: swap_activate is a
cross-filesystem interface and is not expected to start returning
transient error codes, so the EAGAIN is not passed through. A swap file
should be fully written and committed with stable extent sharing before
swapon() is called, so a transient failure here means the file's extent
sharing was still being changed in the same transaction, which is reason
enough to reject it. A distinct warning message replaces "swapfile must
not be copy-on-write" - which would assert a property of the file that
the walk never established - and tells the admin to just retry swapon(),
which attaches a fresh tree mod log sequence number with a consistent
baseline.

Link: https://lore.kernel.org/linux-btrfs/Y28XvZmK0bAS4Ht/@hungrycats.org/
Assisted-by: Claude:claude-fable-5
Signed-off-by: Zygo Blaxell <ce3g8jdj@umail.furryterror.org>