Skip to contentSkip to conversation

btrfs: relocation: Add an introduction for how relocation works.

PATCH Superseded Qu Wenruo 3 participants 4 messages Jan 15, 2020 Btrfs file system

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

PATCH 1/1 btrfs: relocation: Add an introduction for how relocation works.

Relocation is one of the most complex part of btrfs, while it's also the foundation stone for online resizing, profile converting.

For such a complex facility, we should at least have some introduction to it.

This patch will add an basic introduction at pretty a high level, explaining:
- What relocation does
- How relocation is done
Only mentioning how data reloc tree and reloc tree are involved in the operation.
No details like the backref cache, or the data reloc tree contents.
- Which function to refer.

More detailed comments will be added for reloc tree creation, data reloc tree creation and backref cache.

For now the introduction should save reader some time before digging into the rabbit hole.

---
 fs/btrfs/relocation.c | 44 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
fs/btrfs/relocation.c +44 -0
index d897a8e5e430..cd3a15f1716d 100644
@@ -23,6 +23,50 @@
 #include "delalloc-space.h"
 #include "block-group.h"
 
+/*
+ * Introduction for btrfs relocation.
+ *
+ * [What does relocation do]
+ * The objective of relocation is to relocate all or some extents of one block
+ * group to other block groups.
+ * This is utilized by resize (shrink only), profile converting, or just
+ * balance routine to free some block groups.
+ *
+ * In short, relocation wants to do:
+ * 		Before		|		After
+ * ------------------------------------------------------------------
+ *  BG A: 10 data extents	| BG A: deleted
+ *  BG B:  2 data extents	| BG B: 10 data extents (2 old + 8 relocated)
+ *  BG C:  1 extents		| BG C:  3 data extents (1 old + 2 relocated)
+ *
+ * [How does relocation work]
+ * 1.   Mark the target bg RO
+ *      So that new extents won't be allocated from the target bg.
+ *
+ * 2.1  Record each extent in the target bg
+ *      To build a proper map of extents to be relocated.
+ *
+ * 2.2  Build data reloc tree and reloc trees
+ *      Data reloc tree will contain an inode, recording all newly relocated
+ *      data extents.
+ *      There will be only one data reloc tree for one data block group.
+ *
+ *      Reloc tree will be a special snapshot of its source tree, containing
+ *      relocated tree blocks.
+ *      Each tree referring to a tree block in target bg will get its reloc
+ *      tree built.
+ *
+ * 2.3  Swap source tree with its corresponding reloc tree
+ *      So that each involved tree only refers to new extents after swap.
+ *
+ * 3.   Cleanup reloc trees and data reloc tree.
+ *      As old extents in the target bg is still referred by reloc trees,
+ *      we need to clean them up before really freeing the target bg.
+ *
+ * The main complexity is in step 2.2 and 2.3.
+ *
+ * The core entrance for relocation is relocate_block_group() function.
+ */
 /*
  * backref_node, mapping_node and tree_block start with this
  */
Signature · 1 line
2.24.1
#1 lore raw
Quoted 32 lines · Qu Wenruo

Relocation is one of the most complex part of btrfs, while it's also the foundation stone for online resizing, profile converting.

For such a complex facility, we should at least have some introduction to it.

This patch will add an basic introduction at pretty a high level, explaining:
- What relocation does
- How relocation is done
Only mentioning how data reloc tree and reloc tree are involved in the operation.
No details like the backref cache, or the data reloc tree contents.
- Which function to refer.

More detailed comments will be added for reloc tree creation, data reloc tree creation and backref cache.

For now the introduction should save reader some time before digging into the rabbit hole.

---
 fs/btrfs/relocation.c | 44 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
fs/btrfs/relocation.c +0 -0
index d897a8e5e430..cd3a15f1716d 100644

fs/btrfs/relocation.c line 29

Quoted 7 lines
fs/btrfs/relocation.c +4 -0
@@ -23,6 +23,50 @@
 #include "delalloc-space.h"
 #include "block-group.h"
 
+/*
+ * Introduction for btrfs relocation.
+ *
+ * [What does relocation do]

For readability, a blank line here would help.

fs/btrfs/relocation.c line 31

Quoted 2 lines
fs/btrfs/relocation.c +2 -0
+ * The objective of relocation is to relocate all or some extents of one block
+ * group to other block groups.

Some? We always relocate all extents of a block group (except if errors happen of course).

Quoted 25 lines
fs/btrfs/relocation.c +25 -0
+ * This is utilized by resize (shrink only), profile converting, or just
+ * balance routine to free some block groups.
+ *
+ * In short, relocation wants to do:
+ *             Before          |               After
+ * ------------------------------------------------------------------
+ *  BG A: 10 data extents      | BG A: deleted
+ *  BG B:  2 data extents      | BG B: 10 data extents (2 old + 8 relocated)
+ *  BG C:  1 extents           | BG C:  3 data extents (1 old + 2 relocated)
+ *
+ * [How does relocation work]
+ * 1.   Mark the target bg RO
+ *      So that new extents won't be allocated from the target bg.
+ *
+ * 2.1  Record each extent in the target bg
+ *      To build a proper map of extents to be relocated.
+ *
+ * 2.2  Build data reloc tree and reloc trees
+ *      Data reloc tree will contain an inode, recording all newly relocated
+ *      data extents.
+ *      There will be only one data reloc tree for one data block group.
+ *
+ *      Reloc tree will be a special snapshot of its source tree, containing
+ *      relocated tree blocks.
+ *      Each tree referring to a tree block in target bg will get its reloc

fs/btrfs/relocation.c line 66

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+ *      tree built.
+ *
+ * 2.3  Swap source tree with its corresponding reloc tree
+ *      So that each involved tree only refers to new extents after swap.
+ *
+ * 3.   Cleanup reloc trees and data reloc tree.
+ *      As old extents in the target bg is still referred by reloc trees,
+ *      we need to clean them up before really freeing the target bg.
+ *
+ * The main complexity is in step 2.2 and 2.3.

step -> steps

Thanks.

Quoted 9 lines
fs/btrfs/relocation.c +3 -1
+ *
+ * The core entrance for relocation is relocate_block_group() function.
+ */
 /*
  * backref_node, mapping_node and tree_block start with this
  */
--

2.24.1

Signature · 3 lines
Filipe David Manana,

“Whether you think you can, or you think you can't — you're right.”
#2 lore raw
Quoted 43 lines · Filipe Manana
Quoted 32 lines · Qu Wenruo

Relocation is one of the most complex part of btrfs, while it's also the foundation stone for online resizing, profile converting.

For such a complex facility, we should at least have some introduction to it.

This patch will add an basic introduction at pretty a high level, explaining:
- What relocation does
- How relocation is done
Only mentioning how data reloc tree and reloc tree are involved in the operation.
No details like the backref cache, or the data reloc tree contents.
- Which function to refer.

More detailed comments will be added for reloc tree creation, data reloc tree creation and backref cache.

For now the introduction should save reader some time before digging into the rabbit hole.

---
 fs/btrfs/relocation.c | 44 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
fs/btrfs/relocation.c +0 -0
index d897a8e5e430..cd3a15f1716d 100644

fs/btrfs/relocation.c line 29

Quoted 7 lines
fs/btrfs/relocation.c +4 -0
@@ -23,6 +23,50 @@
 #include "delalloc-space.h"
 #include "block-group.h"
 
+/*
+ * Introduction for btrfs relocation.
+ *
+ * [What does relocation do]

For readability, a blank line here would help.

Quoted 5 lines

fs/btrfs/relocation.c line 31

Quoted 2 lines
fs/btrfs/relocation.c +2 -0
+ * The objective of relocation is to relocate all or some extents of one block
+ * group to other block groups.

Some? We always relocate all extents of a block group (except if errors happen of course).

Error is the exact reason I mention "some".

Thanks,
Qu

Quoted 52 lines
Quoted 26 lines
fs/btrfs/relocation.c +25 -0
+ * This is utilized by resize (shrink only), profile converting, or just
+ * balance routine to free some block groups.
+ *
+ * In short, relocation wants to do:
+ *             Before          |               After
+ * ------------------------------------------------------------------
+ *  BG A: 10 data extents      | BG A: deleted
+ *  BG B:  2 data extents      | BG B: 10 data extents (2 old + 8 relocated)
+ *  BG C:  1 extents           | BG C:  3 data extents (1 old + 2 relocated)
+ *
+ * [How does relocation work]
+ * 1.   Mark the target bg RO
+ *      So that new extents won't be allocated from the target bg.
+ *
+ * 2.1  Record each extent in the target bg
+ *      To build a proper map of extents to be relocated.
+ *
+ * 2.2  Build data reloc tree and reloc trees
+ *      Data reloc tree will contain an inode, recording all newly relocated
+ *      data extents.
+ *      There will be only one data reloc tree for one data block group.
+ *
+ *      Reloc tree will be a special snapshot of its source tree, containing
+ *      relocated tree blocks.
+ *      Each tree referring to a tree block in target bg will get its reloc

fs/btrfs/relocation.c line 66

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+ *      tree built.
+ *
+ * 2.3  Swap source tree with its corresponding reloc tree
+ *      So that each involved tree only refers to new extents after swap.
+ *
+ * 3.   Cleanup reloc trees and data reloc tree.
+ *      As old extents in the target bg is still referred by reloc trees,
+ *      we need to clean them up before really freeing the target bg.
+ *
+ * The main complexity is in step 2.2 and 2.3.

step -> steps

Thanks.

Quoted 9 lines
fs/btrfs/relocation.c +3 -1
+ *
+ * The core entrance for relocation is relocate_block_group() function.
+ */
 /*
  * backref_node, mapping_node and tree_block start with this
  */
--

2.24.1

#3 lore raw
Quoted 47 lines · Qu Wenruo
Quoted 43 lines · Filipe Manana
Quoted 32 lines · Qu Wenruo

Relocation is one of the most complex part of btrfs, while it's also the foundation stone for online resizing, profile converting.

For such a complex facility, we should at least have some introduction to it.

This patch will add an basic introduction at pretty a high level, explaining:
- What relocation does
- How relocation is done
Only mentioning how data reloc tree and reloc tree are involved in the operation.
No details like the backref cache, or the data reloc tree contents.
- Which function to refer.

More detailed comments will be added for reloc tree creation, data reloc tree creation and backref cache.

For now the introduction should save reader some time before digging into the rabbit hole.

---
 fs/btrfs/relocation.c | 44 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
fs/btrfs/relocation.c +0 -0
index d897a8e5e430..cd3a15f1716d 100644

fs/btrfs/relocation.c line 29

Quoted 7 lines
fs/btrfs/relocation.c +4 -0
@@ -23,6 +23,50 @@
 #include "delalloc-space.h"
 #include "block-group.h"
 
+/*
+ * Introduction for btrfs relocation.
+ *
+ * [What does relocation do]

For readability, a blank line here would help.

Quoted 7 lines
Quoted 5 lines

fs/btrfs/relocation.c line 31

Quoted 2 lines
fs/btrfs/relocation.c +2 -0
+ * The objective of relocation is to relocate all or some extents of one block
+ * group to other block groups.

Some? We always relocate all extents of a block group (except if errors happen of course).

Error is the exact reason I mention "some".

Then it should be rephrased imo. It's confusing. The objective is to always relocate all extents.
You can mention instead in parentheses or in a separate statement that in case of an error only some may be relocated:

The objective of relocation is to relocate all the extents of one block group to other block groups.
If an error happens during relocation, it's possible that only some extents were relocated.

Thanks.

Quoted 57 lines

Thanks,
Qu

Quoted 52 lines
Quoted 26 lines
fs/btrfs/relocation.c +25 -0
+ * This is utilized by resize (shrink only), profile converting, or just
+ * balance routine to free some block groups.
+ *
+ * In short, relocation wants to do:
+ *             Before          |               After
+ * ------------------------------------------------------------------
+ *  BG A: 10 data extents      | BG A: deleted
+ *  BG B:  2 data extents      | BG B: 10 data extents (2 old + 8 relocated)
+ *  BG C:  1 extents           | BG C:  3 data extents (1 old + 2 relocated)
+ *
+ * [How does relocation work]
+ * 1.   Mark the target bg RO
+ *      So that new extents won't be allocated from the target bg.
+ *
+ * 2.1  Record each extent in the target bg
+ *      To build a proper map of extents to be relocated.
+ *
+ * 2.2  Build data reloc tree and reloc trees
+ *      Data reloc tree will contain an inode, recording all newly relocated
+ *      data extents.
+ *      There will be only one data reloc tree for one data block group.
+ *
+ *      Reloc tree will be a special snapshot of its source tree, containing
+ *      relocated tree blocks.
+ *      Each tree referring to a tree block in target bg will get its reloc

fs/btrfs/relocation.c line 66

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+ *      tree built.
+ *
+ * 2.3  Swap source tree with its corresponding reloc tree
+ *      So that each involved tree only refers to new extents after swap.
+ *
+ * 3.   Cleanup reloc trees and data reloc tree.
+ *      As old extents in the target bg is still referred by reloc trees,
+ *      we need to clean them up before really freeing the target bg.
+ *
+ * The main complexity is in step 2.2 and 2.3.

step -> steps

Thanks.

Quoted 9 lines
fs/btrfs/relocation.c +3 -1
+ *
+ * The core entrance for relocation is relocate_block_group() function.
+ */
 /*
  * backref_node, mapping_node and tree_block start with this
  */
--

2.24.1

Signature · 3 lines
Filipe David Manana,

“Whether you think you can, or you think you can't — you're right.”