btrfs: extent-tree: Add comment for walk_control to explain how btrfs drops a subvolume.
diff mbox series

Message ID 20190723075721.9383-1-wqu@suse.com
State New
Headers show
Series
  • btrfs: extent-tree: Add comment for walk_control to explain how btrfs drops a subvolume.
Related show

Commit Message

Qu Wenruo July 23, 2019, 7:57 a.m. UTC
Btrfs uses several different ways to drop a subvolume. Some methods are
designed to reduce the modification to extent tree.
This design can be very confusing if not familiar with
btrfs_drop_snapshot().

Before wasting time of newcomers, just add some explanation.

Also add some basic comment for members of struct walk_control.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/extent-tree.c | 70 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)

Comments

Diego Calleja July 24, 2019, 10:25 p.m. UTC | #1
El martes, 23 de julio de 2019 9:57:21 (CEST) Qu Wenruo escribió:
> + *       A	<- tree root, level 2
> + *      / \
> + *     B   C    <- tree nodes, level 1
> + *    / \ / \
> + *    D E F G   <- tree leaves, level 0
> + *
> + * 1) Basic dropping.
> + *    All above tree blocks are owned exclusively.
> + *    Drop tree blocks using LRN iteration.
> + *    Tree drop sequence is: D E B F C G A.

Excuse me if I am wrong, but there seems to be a small typo, shouldn't
it be "F G C"?
Qu Wenruo July 24, 2019, 10:55 p.m. UTC | #2
On 2019/7/25 上午6:25, Diego Calleja wrote:
> El martes, 23 de julio de 2019 9:57:21 (CEST) Qu Wenruo escribió:
>> + *       A	<- tree root, level 2
>> + *      / \
>> + *     B   C    <- tree nodes, level 1
>> + *    / \ / \
>> + *    D E F G   <- tree leaves, level 0
>> + *
>> + * 1) Basic dropping.
>> + *    All above tree blocks are owned exclusively.
>> + *    Drop tree blocks using LRN iteration.
>> + *    Tree drop sequence is: D E B F C G A.
> 
> Excuse me if I am wrong, but there seems to be a small typo, shouldn't
> it be "F G C"?

My bad, nice catch!

Thanks,
Qu

Patch
diff mbox series

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 5faf057f6f37..8134273b9b88 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -8617,14 +8617,84 @@  struct extent_buffer *btrfs_alloc_tree_block(struct btrfs_trans_handle *trans,
 	return ERR_PTR(ret);
 }
 
+/*
+ * Btrfs tree walk control for dropping subvolume.
+ *
+ * Btrfs uses btrfs_root_item::drop_level and btrfs_root_item::drop_level
+ * to record where *next* should resume from.
+ *
+ * Btrfs uses several different ways to optimize subvolume deleting.
+ * All the following cases uses the same example tree:
+ * Root->root_key.object = 300
+ *       A	<- tree root, level 2
+ *      / \
+ *     B   C    <- tree nodes, level 1
+ *    / \ / \
+ *    D E F G   <- tree leaves, level 0
+ *
+ * 1) Basic dropping.
+ *    All above tree blocks are owned exclusively.
+ *    Drop tree blocks using LRN iteration.
+ *    Tree drop sequence is: D E B F C G A.
+ *
+ * 2) Dropping highest owned tree block.
+ *    In this example, we have tree 299, also owning tree block B and C
+ *    directly. (Root 299 only exists in this example)
+ *    Root 300 is a snapshot of root 299, no modification between them.
+ *
+ *    In this case, we only need to drop references of B, C
+ *    Tree drop sequence is: B, C
+ *
+ * 3) Convert to FULL_BACKREF, then back to 2)
+ *    For example, we have tree 301, also owning tree block B and C
+ *    directly. (Root 301 only exists in this example)
+ *    Root 301 is a snapshot of root 300, no modification between them.
+ *
+ *    In this case, we can't just drop reference to tree block B and C.
+ *    As in extent tree, tree block D~G are still referred by tree 300, e.g:
+ *            item XX key (bytenr_of_D METADATA_ITEM 0)
+ *              refs 1 gen 8 flags TREE_BLOCK
+ *              tree block skinny level 0
+ *              tree block backref root 300 <<
+ *
+ *    In this case, we convert such tree backref to FULL_BACKREF, which only
+ *    records its parent, so the new backref would look like:
+ *            item XX key (bytenr_of_D METADATA_ITEM 0) itemoff 3449 itemsize 33
+ *              refs 1 gen 8 flags TREE_BLOCK|FULL_BACKREF
+ *              tree block skinny level 0
+ *              shared block backref parent bytenr_of_B
+ *
+ *    By this, we can go back to 2) to drop the minimal number of backref.
+ */
 struct walk_control {
+	/* Number of direct owners of path->nodes[level]. */
 	u64 refs[BTRFS_MAX_LEVEL];
+
+	/* Backref flags, can be either TREE_BLOCK or TREE_BLOCK|FULL_BACKREF */
 	u64 flags[BTRFS_MAX_LEVEL];
+
+	/* Key of next location to update backrefs, in-memory only */
 	struct btrfs_key update_progress;
+
+	/* Key of next location to drop reference */
 	struct btrfs_key drop_progress;
+
+	/* Current drop kevel, used with drop_progress */
 	int drop_level;
+
+	/*
+	 * Either DROP_REFERENCE or UPDATE_BACKREF
+	 *
+	 * In DROP_REFERENCE stage, we drop reference of the target tree block.
+	 * In UPDATE_BACKREF stage, we convert the backref to FULL_BACKREF of
+	 * the target subtree.
+	 */
 	int stage;
+
+	/* Current working level, shared between both stages */
 	int level;
+
+	/* Where the shared node is for case 3) */
 	int shared_level;
 	int update_ref;
 	int keep_locks;