btrfs: resume the delayed-ref merge walk instead of restarting it

btrfs: resume the delayed-ref merge walk instead of restarting it

btrfs_merge_delayed_refs() restarts its walk of a head's ref tree from
rb_first_cached() every time merge_ref() reports a merge:

	again:
		for (node = rb_first_cached(&head->ref_tree); node;
		     node = rb_next(node)) {
			ref = rb_entry(node, ...);
			if (seq && ref->seq >= seq)
				continue;
			if (merge_ref(fs_info, delayed_refs, head, ref, seq))
				goto again;
		}

The restart is there because merge_ref() returns true only when it has
freed the caller's cursor node, so the caller cannot call rb_next() on it.
That makes the walk quadratic in the number of refs on the head, and it
runs with head->lock held -- a spinlock -- so it cannot be broken up.

On a filesystem doing continuous backref resolution this is not
theoretical. Each backref walk advances fs_info->tree_mod_seq, and
init_delayed_ref_common() stamps that seq into every new fs-tree ref, so
refs to the same block and root stop comparing equal and stop being merged
at insert time by insert_delayed_ref().  They accumulate as separate nodes
in one contiguous group instead, and the merge walk restarts across the
whole group on every cancelling pair.

Measured with the ftrace function profiler on a filesystem running a
dedupe agent and a verifier that both walk backrefs continuously, during a
stall, over a 60 second window:

  btrfs_merge_delayed_refs()         115,166 calls
  comp_refs()                  1,171,273,171 calls

comp_refs() is called once per node the merge walk compares, so that is
10,170 comparisons per walk.  Solving the restart structure's N^2/2 puts
roughly 143 refs on a head.  comp_refs() is a leaf, so its own total is
not distorted by nesting: 38.9 CPU-seconds of that 60 second window went
to comparing delayed refs and nothing else, with the transaction thread
pinned at 100% of a core and zero tasks anywhere in the machine waiting on
IO.

The cost is not subtle.  Every other task queued behind the commit;
relocation of a single block group made no progress for three and a half
hours; snapshot deletion, which had been clearing about 49 subvolumes a
minute, stopped entirely.  An earlier instance on the same machine
produced a 26 second soft lockup with the stack inside the merge walk.

merge_ref() does not actually need the caller to restart.  It advances its
own cursor past a node before freeing that node:

		next = rb_entry(node, ...);
		node = rb_next(node);
		...
		drop_delayed_ref(fs_info, delayed_refs, head, next);

so it always holds a position that survives the frees, and there are only
three ways it can end having freed the caller's node:

 - it swapped, and the survivor keeps a non-zero ref_mod.  The caller's node is
   freed; the survivor is still in the tree and may still merge with what
   follows, so the walk resumes at the survivor.

 - the caller's ref_mod reached zero, with or without a swap.  Both nodes are
   gone, and the local cursor -- already advanced past the freed one -- is the
   resume point, or NULL to end the walk.

Return whether @ref was freed, and hand the position back through an out
parameter.  The two cannot be folded into one pointer: the resume position
is legitimately NULL when the freed node was last in the tree, and a NULL
return would then tell the caller its own node is still live. The walk becomes strictly forward and linear, and nothing is left
unmerged.

Skipping the re-examination that the restart performed does not lose
merges. comp_refs() keys on type and root-or-parent, neither of which any
merge changes, so merging cannot make two previously incomparable refs
comparable. Mergeable refs are contiguous, because the tree is sorted by
comp_refs(..., check_seq = true) and the merge key is the same comparison
without the seq -- a prefix of the sort key.  And a ref skipped by the seq
test stays skipped, since seq is read once per btrfs_merge_delayed_refs()
call.

The restart has had this shape since commit 0e0adbcfdc90 ("btrfs: track
refs in a rb_tree instead of a list") in v4.15.

Assisted-by: Claude:claude-opus-5[1m]