btrfs: qgroup: Introduce per-root swapped blocks infrastructure

To allow delayed subtree swap rescan, btrfs needs to record per-root info about which tree blocks get swapped.

So this patch introduces per-root btrfs_qgroup_swapped_blocks structure, which records which tree blocks get swapped.

The designed workflow will be:

1) Record the subtree root block get swapped.

During subtree swap:
O = Old tree blocks
N = New tree blocks
reloc tree file tree X
Root Root
/ \ / \
NA OB OA OB
/ | | \ / | | \
NC ND OE OF OC OD OE OF

In these case, NA and OA is going to be swapped, record (NA, OA) into file tree X.

2) After subtree swap.
reloc tree file tree X
Root Root
/ \ / \
OA OB NA OB
/ | | \ / | | \
OC OD OE OF NC ND OE OF

3a) CoW happens for OB
If we are going to CoW tree block OB, we check OB's bytenr against tree X's swapped_blocks structure.
It doesn't fit any one, nothing will happen.

3b) CoW happens for NA
Check NA's bytenr against tree X's swapped_blocks, and get a hit. Then we do subtree scan on both subtree OA and NA. Resulting 6 tree blocks to be scanned (OA, OC, OD, NA, NC, ND).

Then no matter what we do to file tree X, qgroup numbers will still be correct.
Then NA's record get removed from X's swapped_blocks.

4) Transaction commit
Any record in X's swapped_blocks get removed, since there is no modification to swapped subtrees, no need to trigger heavy qgroup subtree rescan for them.

This will introduce 128 bytes overhead for each btrfs_root even qgroup is not enabled.

---
changelog:
v1.1
Fix a memory leak cause by using rbtree_postorder_for_each_entry_safe() for emptying rbtree

---
 fs/btrfs/ctree.h       |  13 ++++
 fs/btrfs/disk-io.c     |   1 +
 fs/btrfs/qgroup.c      | 132 +++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/qgroup.h      |  99 +++++++++++++++++++++++++++++++
 fs/btrfs/relocation.c  |   7 +++
 fs/btrfs/transaction.c |   1 +
 6 files changed, 253 insertions(+)

index 53af9f5253f4..5f2b055fcd56 100644
@@ -1157,6 +1157,17 @@ struct btrfs_subvolume_writers {
 #define BTRFS_ROOT_MULTI_LOG_TASKS	7
 #define BTRFS_ROOT_DIRTY		8
 
+/*
+ * Record swapped tree blocks of a file/subvolume tree for delayed subtree
+ * trace code. For detail check comment in fs/btrfs/qgroup.c.
+ */
+struct btrfs_qgroup_swapped_blocks {
+	spinlock_t lock;
+	struct rb_root blocks[BTRFS_MAX_LEVEL];
+	/* RM_EMPTY_ROOT() of above blocks[] */
+	bool swapped;
+};
+
 /*
  * in ram representation of the tree.  extent_root is used for all allocations
  * and for the extent tree extent_root root.

@@ -1285,6 +1296,8 @@ struct btrfs_root {
 	spinlock_t qgroup_meta_rsv_lock;
 	u64 qgroup_meta_rsv_pertrans;
 	u64 qgroup_meta_rsv_prealloc;
+
+	struct btrfs_qgroup_swapped_blocks swapped_blocks;
 };
 
 struct btrfs_file_private {

index 5124c15705ce..d6aa266f0638 100644
@@ -1204,6 +1204,7 @@ static void __setup_root(struct btrfs_root *root, struct btrfs_fs_info *fs_info,
 	root->anon_dev = 0;
 
 	spin_lock_init(&root->root_item_lock);
+	btrfs_qgroup_init_swapped_blocks(&root->swapped_blocks);
 }
 
 static struct btrfs_root *btrfs_alloc_root(struct btrfs_fs_info *fs_info,

index a8b62323f60b..86b8d82b62d8 100644
@@ -1885,6 +1885,13 @@ int replace_path(struct btrfs_trans_handle *trans, struct reloc_control *rc,
 		if (ret < 0)
 			break;
 
+		btrfs_node_key_to_cpu(parent, &first_key, slot);
+		ret = btrfs_qgroup_add_swapped_blocks(trans, dest,
+				rc->block_group, parent, slot,
+				path->nodes[level], path->slots[level],
+				last_snapshot);
+		if (ret < 0)
+			break;
 		/*
 		 * swap blocks in fs tree and reloc tree.
 		 */

index 3b84f5015029..15418cea9eb0 100644
@@ -121,6 +121,7 @@ static noinline void switch_commit_roots(struct btrfs_transaction *trans)
 		if (is_fstree(root->objectid))
 			btrfs_unpin_free_ino(root);
 		clear_btree_io_tree(&root->dirty_log_pages);
+		btrfs_qgroup_clean_swapped_blocks(root);
 	}
 
 	/* We can free old roots now. */

2.19.1