Btrfs: try harder to migrate items to left sibling before splitting a leaf

PATCH In review [email protected] 2 participants 4 messages Feb 20, 2017 – Feb 22, 2017 Btrfs file system

lore

Share & tools

lore

[email protected]

author

2017-02-20 13:56 UTC #0 lore raw

PATCH 1/1 Btrfs: try harder to migrate items to left sibling before splitting a leaf

From: Filipe Manana <[email protected]>

Before attempting to split a leaf we try to migrate items from the leaf to its right and left siblings. We start by trying to move items into the rigth sibling and, if the new item is meant to be inserted at the end of our leaf, we try to free from our leaf an amount of bytes equal to the number of bytes used by the new item, by setting the variable space_needed to the byte size of that new item. However if we fail to move enough items to the right sibling due to lack of space in that sibling, we then try to move items into the left sibling, and in that case we try to free an amount equal to the size of the new item from our leaf, when we need only to free an amount corresponding to the size of the new item minus the current free space of our leaf. So make sure that before we try to move items to the left sibling we do set the variable space_needed with a value corresponding to the new item's size minus the leaf's current free space.

Signed-off-by Filipe Manana <[email protected]>

---
 fs/btrfs/ctree.c | 7 +++++++
 1 file changed, 7 insertions(+)

fs/btrfs/ctree.c +7 -0

index a426dc8..1d66761 100644
@@ -4160,6 +4160,9 @@ static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
 
 	/* try to push all the items before our slot into the next leaf */
 	slot = path->slots[0];
+	space_needed = data_size;
+	if (slot > 0)
+		space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
 	ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
 	if (ret < 0)
 		return ret;

@@ -4215,6 +4218,10 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
 		if (wret < 0)
 			return wret;
 		if (wret) {
+			space_needed = data_size;
+			if (slot > 0)
+				space_needed -= btrfs_leaf_free_space(fs_info,
+								      l);
 			wret = push_leaf_left(trans, root, path, space_needed,
 					      space_needed, 0, (u32)-1);
 			if (wret < 0)

Signature · 1 line

2.7.0.rc3

Liu Bo

2017-02-22 00:08 UTC #1 lore raw

Quoted 27 lines · On Sun, Feb 19, 2017 at 08:56:39PM +0000, [email protected] wrote:

From: Filipe Manana <[email protected]>
Before attempting to split a leaf we try to migrate items from the leaf to its right and left siblings. We start by trying to move items into the rigth sibling and, if the new item is meant to be inserted at the end of our leaf, we try to free from our leaf an amount of bytes equal to the number of bytes used by the new item, by setting the variable space_needed to the byte size of that new item. However if we fail to move enough items to the right sibling due to lack of space in that sibling, we then try to move items into the left sibling, and in that case we try to free an amount equal to the size of the new item from our leaf, when we need only to free an amount corresponding to the size of the new item minus the current free space of our leaf. So make sure that before we try to move items to the left sibling we do set the variable space_needed with a value corresponding to the new item's size minus the leaf's current free space.
Signed-off-by Filipe Manana <[email protected]>
---
 fs/btrfs/ctree.c | 7 +++++++
 1 file changed, 7 insertions(+)
fs/btrfs/ctree.c +0 -0
index a426dc8..1d66761 100644

fs/btrfs/ctree.c static noinline int push_for_double_split(struct btrfs_trans_handle *trans, · line 4165

Quoted 6 lines

fs/btrfs/ctree.c +3 -0

@@ -4160,6 +4160,9 @@ static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
 
 	/* try to push all the items before our slot into the next leaf */
 	slot = path->slots[0];
+	space_needed = data_size;
+	if (slot > 0)
+		space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);

Good point.

fs/btrfs/ctree.c static noinline int split_leaf(struct btrfs_trans_handle *trans, · line 4224

Quoted 11 lines

fs/btrfs/ctree.c +4 -0

 	ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
 	if (ret < 0)
 		return ret;

@@ -4215,6 +4218,10 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
 		if (wret < 0)
 			return wret;
 		if (wret) {
+			space_needed = data_size;
+			if (slot > 0)
+				space_needed -= btrfs_leaf_free_space(fs_info,
+								      l);

Not sure if we need this, the above push_leaf_right() was called with @min_data_size == space_needed, thus if @wret == 1, no items have been moved in push_leaf_right() so that leaf 'l' remains unchanged.

Thanks,

-liubo

Quoted 10 lines

fs/btrfs/ctree.c +0 -0

 			wret = push_leaf_left(trans, root, path, space_needed,
 					      space_needed, 0, (u32)-1);
 			if (wret < 0)

Signature · 6 lines

2.7.0.rc3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Filipe Manana

author

2017-02-22 14:05 UTC #2 lore raw

Quoted 37 lines · Liu Bo

Quoted 27 lines · On Sun, Feb 19, 2017 at 08:56:39PM +0000, [email protected] wrote:
From: Filipe Manana <[email protected]>
Before attempting to split a leaf we try to migrate items from the leaf to its right and left siblings. We start by trying to move items into the rigth sibling and, if the new item is meant to be inserted at the end of our leaf, we try to free from our leaf an amount of bytes equal to the number of bytes used by the new item, by setting the variable space_needed to the byte size of that new item. However if we fail to move enough items to the right sibling due to lack of space in that sibling, we then try to move items into the left sibling, and in that case we try to free an amount equal to the size of the new item from our leaf, when we need only to free an amount corresponding to the size of the new item minus the current free space of our leaf. So make sure that before we try to move items to the left sibling we do set the variable space_needed with a value corresponding to the new item's size minus the leaf's current free space.
Signed-off-by Filipe Manana <[email protected]>
---
 fs/btrfs/ctree.c | 7 +++++++
 1 file changed, 7 insertions(+)
fs/btrfs/ctree.c +0 -0
index a426dc8..1d66761 100644
fs/btrfs/ctree.c static noinline int push_for_double_split(struct btrfs_trans_handle *trans, · line 4165
Quoted 6 lines
fs/btrfs/ctree.c +3 -0
@@ -4160,6 +4160,9 @@ static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
 
      /* try to push all the items before our slot into the next leaf */
      slot = path->slots[0];
+     space_needed = data_size;
+     if (slot > 0)
+             space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
Good point.

Quoted 15 lines

fs/btrfs/ctree.c static noinline int split_leaf(struct btrfs_trans_handle *trans, · line 4224

Quoted 11 lines

fs/btrfs/ctree.c +4 -0

      ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
      if (ret < 0)
              return ret;

@@ -4215,6 +4218,10 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
              if (wret < 0)
                      return wret;
              if (wret) {
+                     space_needed = data_size;
+                     if (slot > 0)
+                             space_needed -= btrfs_leaf_free_space(fs_info,
+                                                                   l);

That's exactly the point. If the item is meant to be appended and we failed to move it into the right sibling, we want to try to move items from the leaf into its left sibling with the goal of freeing "new_item_size - leaf_free_space(l)" bytes from our leaf. Without this new assignment, we try to free new_item_size bytes, which has higher chances of not being successful at migrating items into the left sibling (example, the left sibling has less than new_item_size bytes free, but has at least "new_item_size - leaf_free_space(l)" bytes free).

Quoted 14 lines

Thanks,
-liubo
Quoted 10 lines
fs/btrfs/ctree.c +0 -1
                      wret = push_leaf_left(trans, root, path, space_needed,
                                            space_needed, 0, (u32)-1);
                      if (wret < 0)
--
2.7.0.rc3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Liu Bo

Reviewed-by

2017-02-22 17:38 UTC #3 lore raw

Quoted 54 lines · Filipe Manana

Quoted 37 lines · Liu Bo
Quoted 27 lines · On Sun, Feb 19, 2017 at 08:56:39PM +0000, [email protected] wrote:
From: Filipe Manana <[email protected]>
Before attempting to split a leaf we try to migrate items from the leaf to its right and left siblings. We start by trying to move items into the rigth sibling and, if the new item is meant to be inserted at the end of our leaf, we try to free from our leaf an amount of bytes equal to the number of bytes used by the new item, by setting the variable space_needed to the byte size of that new item. However if we fail to move enough items to the right sibling due to lack of space in that sibling, we then try to move items into the left sibling, and in that case we try to free an amount equal to the size of the new item from our leaf, when we need only to free an amount corresponding to the size of the new item minus the current free space of our leaf. So make sure that before we try to move items to the left sibling we do set the variable space_needed with a value corresponding to the new item's size minus the leaf's current free space.
Signed-off-by Filipe Manana <[email protected]>
---
 fs/btrfs/ctree.c | 7 +++++++
 1 file changed, 7 insertions(+)
fs/btrfs/ctree.c +0 -0
index a426dc8..1d66761 100644
fs/btrfs/ctree.c static noinline int push_for_double_split(struct btrfs_trans_handle *trans, · line 4165
Quoted 6 lines
fs/btrfs/ctree.c +3 -0
@@ -4160,6 +4160,9 @@ static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
 
      /* try to push all the items before our slot into the next leaf */
      slot = path->slots[0];
+     space_needed = data_size;
+     if (slot > 0)
+             space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
Good point.
Quoted 15 lines
fs/btrfs/ctree.c static noinline int split_leaf(struct btrfs_trans_handle *trans, · line 4224
Quoted 11 lines
fs/btrfs/ctree.c +4 -0
      ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
      if (ret < 0)
              return ret;
@@ -4215,6 +4218,10 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
              if (wret < 0)
                      return wret;
              if (wret) {
+                     space_needed = data_size;
+                     if (slot > 0)
+                             space_needed -= btrfs_leaf_free_space(fs_info,
+                                                                   l);
Not sure if we need this, the above push_leaf_right() was called with @min_data_size == space_needed, thus if @wret == 1, no items have been moved in push_leaf_right() so that leaf 'l' remains unchanged.

Quoted 10 lines

That's exactly the point. If the item is meant to be appended and we failed to move it into the right sibling, we want to try to move items from the leaf into its left sibling with the goal of freeing "new_item_size - leaf_free_space(l)" bytes from our leaf. Without this new assignment, we try to free new_item_size bytes, which has higher chances of not being successful at migrating items into the left sibling (example, the left sibling has less than new_item_size bytes free, but has at least "new_item_size - leaf_free_space(l)" bytes free).

I see, I missed that we didn't check (slot > 0) before push_leaf_right(), you may add

Reviewed-by Liu Bo <[email protected]>

Thanks,

-liubo

Quoted 14 lines

Quoted 14 lines
Thanks,
-liubo
Quoted 10 lines
fs/btrfs/ctree.c +0 -1
                      wret = push_leaf_left(trans, root, path, space_needed,
                                            space_needed, 0, (u32)-1);
                      if (wret < 0)
--
2.7.0.rc3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html