Skip to contentSkip to conversation

btrfs: remove some duplicated checks in btrfs_previous_*_item()

PATCH In review Qu Wenruo 4 participants 5 messages Dec 14, 2021 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

PATCH 1/1 btrfs: remove some duplicated checks in btrfs_previous_*_item()

In btrfs_previous_item() and btrfs_previous_extent_item() we check btrfs_header_nritems() in a loop.

But in fact we don't need to do it in a loop at all.

Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.

Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.

So this patch will move all the nritems related checks out of the loop by:

- Check nritems of nodes[0] to do a quick exit

- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.

- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, and btrfs_prev_leaf() will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extra ASSERT() to make sure no tree block is empty.

---
 fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 36 insertions(+), 16 deletions(-)
fs/btrfs/ctree.c +36 -16
index 781537692a4a..555345aed84d 100644
@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root,
 {
 	struct btrfs_key found_key;
 	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
 	int ret;
 
+	/*
+	 * Check nritems first, if the tree is empty we exit immediately.
+	 * And if this leave is not empty, none of the tree blocks of this root
+	 * should be empty.
+	 */
+	if (nritems == 0)
+		return 1;
+
+	/*
+	 * If we're several slots beyond nritems, we reset slot to nritems,
+	 * and it will be handled properly inside the loop.
+	 */
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
 			if (ret != 0)
 				return ret;
-		} else {
-			path->slots[0]--;
 		}
 		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		/*
+		 * This is for both regular case and above btrfs_prev_leaf() case.
+		 * As btrfs_prev_leaf() will return with path->slots[0] == nritems,
+		 * and we're sure no tree block is empty, we can go safely
+		 * reduce slots[0] here.
+		 */
+		path->slots[0]--;
 
 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 		if (found_key.objectid < min_objectid)
@@ -4745,23 +4761,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
 {
 	struct btrfs_key found_key;
 	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
 	int ret;
 
+	/*
+	 * Refer to btrfs_previous_item() for the reason of all nritems related
+	 * checks/modifications.
+	 */
+	if (nritems == 0)
+		return 1;
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
 			if (ret != 0)
 				return ret;
-		} else {
-			path->slots[0]--;
 		}
 		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		path->slots[0]--;
 
 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 		if (found_key.objectid < min_objectid)
Signature · 1 line
2.34.1
#1 lore raw
Quoted 73 lines · Qu Wenruo

In btrfs_previous_item() and btrfs_previous_extent_item() we check btrfs_header_nritems() in a loop.

But in fact we don't need to do it in a loop at all.

Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.

Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.

So this patch will move all the nritems related checks out of the loop by:

- Check nritems of nodes[0] to do a quick exit

- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.

- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, and btrfs_prev_leaf() will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extra ASSERT() to make sure no tree block is empty.

---
 fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 36 insertions(+), 16 deletions(-)
fs/btrfs/ctree.c +16 -6
index 781537692a4a..555345aed84d 100644
@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root,
 {
 	struct btrfs_key found_key;
 	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
 	int ret;
 
+	/*
+	 * Check nritems first, if the tree is empty we exit immediately.
+	 * And if this leave is not empty, none of the tree blocks of this root
+	 * should be empty.
+	 */
+	if (nritems == 0)
+		return 1;
+
+	/*
+	 * If we're several slots beyond nritems, we reset slot to nritems,
+	 * and it will be handled properly inside the loop.
+	 */
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
 			if (ret != 0)
 				return ret;
-		} else {
-			path->slots[0]--;
 		}
 		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;

fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739

Quoted 10 lines
fs/btrfs/ctree.c +8 -2
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		/*
+		 * This is for both regular case and above btrfs_prev_leaf() case.
+		 * As btrfs_prev_leaf() will return with path->slots[0] == nritems,
+		 * and we're sure no tree block is empty, we can go safely
+		 * reduce slots[0] here.
+		 */
+		path->slots[0]--;

No, this is wrong.
btrfs_prev_leaf() computes the previous key and does a search_slot() for it. With this unconditional decrement we can miss the previous key in 2 ways:

1) The previous key exists, and btrfs_prev_leaf() leaves us in a leaf that has it and the slot is btrfs_header_nritems(prev_leaf) - 1 -> the last key on a leaf;

2) The previous key exists, but after btrfs_prev_leaf() released the path and before it called search_slot(), there was a balance operation and it pushed the previous key in the middle of the leaf we had, or some other leaf, and the slot will be something less than btrfs_header_nritems(), it can even be 0.

That's why we have the call to header_nritems() in the loop, and check if slots[0] is == to nritems before decrementing...

Thanks.

Quoted 42 lines
fs/btrfs/ctree.c +12 -8
 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 		if (found_key.objectid < min_objectid)
@@ -4745,23 +4761,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
 {
 	struct btrfs_key found_key;
 	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
 	int ret;
 
+	/*
+	 * Refer to btrfs_previous_item() for the reason of all nritems related
+	 * checks/modifications.
+	 */
+	if (nritems == 0)
+		return 1;
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
 			if (ret != 0)
 				return ret;
-		} else {
-			path->slots[0]--;
 		}
 		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		path->slots[0]--;
 
 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 		if (found_key.objectid < min_objectid)
Signature · 1 line
2.34.1
#2 lore raw
Quoted 89 lines · Filipe Manana
Quoted 73 lines · Qu Wenruo

In btrfs_previous_item() and btrfs_previous_extent_item() we check btrfs_header_nritems() in a loop.

But in fact we don't need to do it in a loop at all.

Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.

Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.

So this patch will move all the nritems related checks out of the loop by:

- Check nritems of nodes[0] to do a quick exit

- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.

- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, and btrfs_prev_leaf() will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extra ASSERT() to make sure no tree block is empty.

---
  fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++---------------
  1 file changed, 36 insertions(+), 16 deletions(-)
fs/btrfs/ctree.c +16 -6
index 781537692a4a..555345aed84d 100644
@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root,
  {
  	struct btrfs_key found_key;
  	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
  	int ret;
 
+	/*
+	 * Check nritems first, if the tree is empty we exit immediately.
+	 * And if this leave is not empty, none of the tree blocks of this root
+	 * should be empty.
+	 */
+	if (nritems == 0)
+		return 1;
+
+	/*
+	 * If we're several slots beyond nritems, we reset slot to nritems,
+	 * and it will be handled properly inside the loop.
+	 */
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
  	while (1) {
  		if (path->slots[0] == 0) {
  			ret = btrfs_prev_leaf(root, path);
  			if (ret != 0)
  				return ret;
-		} else {
-			path->slots[0]--;
  		}
  		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;

fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739

Quoted 10 lines
fs/btrfs/ctree.c +8 -2
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		/*
+		 * This is for both regular case and above btrfs_prev_leaf() case.
+		 * As btrfs_prev_leaf() will return with path->slots[0] == nritems,
+		 * and we're sure no tree block is empty, we can go safely
+		 * reduce slots[0] here.
+		 */
+		path->slots[0]--;

No, this is wrong.
btrfs_prev_leaf() computes the previous key and does a search_slot() for it. With this unconditional decrement we can miss the previous key in 2 ways:

Quoted 7 lines

1) The previous key exists, and btrfs_prev_leaf() leaves us in a leaf that has it

    and the slot is btrfs_header_nritems(prev_leaf) - 1 -> the last key on a leaf;

2) The previous key exists, but after btrfs_prev_leaf() released the path and before it called search_slot(), there was a balance operation and it pushed the previous key in the middle of the leaf we had, or some other leaf, and the slot will be something less than btrfs_header_nritems(), it can even be 0.

You're totally right about both cases.

I totally forget that btrfs_prev_leaf() is using serch_slot() other than going up several levels to find the sibling leaf.

Please discard the patch.

Thanks,
Qu

Quoted 49 lines

That's why we have the call to header_nritems() in the loop, and check if slots[0] is == to nritems before decrementing...

Thanks.

Quoted 42 lines
fs/btrfs/ctree.c +12 -9
  		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  		if (found_key.objectid < min_objectid)
@@ -4745,23 +4761,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
  {
  	struct btrfs_key found_key;
  	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
  	int ret;
 
+	/*
+	 * Refer to btrfs_previous_item() for the reason of all nritems related
+	 * checks/modifications.
+	 */
+	if (nritems == 0)
+		return 1;
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
  	while (1) {
  		if (path->slots[0] == 0) {
  			ret = btrfs_prev_leaf(root, path);
  			if (ret != 0)
  				return ret;
-		} else {
-			path->slots[0]--;
  		}
  		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		path->slots[0]--;
 
  		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  		if (found_key.objectid < min_objectid)
--

2.34.1

#3 lore raw
In reply to Qu Wenruo
Quoted 73 lines · Qu Wenruo

In btrfs_previous_item() and btrfs_previous_extent_item() we check btrfs_header_nritems() in a loop.

But in fact we don't need to do it in a loop at all.

Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.

Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.

So this patch will move all the nritems related checks out of the loop by:

- Check nritems of nodes[0] to do a quick exit

- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.

- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, and btrfs_prev_leaf() will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extra ASSERT() to make sure no tree block is empty.

---
 fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 36 insertions(+), 16 deletions(-)
fs/btrfs/ctree.c +16 -6
index 781537692a4a..555345aed84d 100644
@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root,
 {
 	struct btrfs_key found_key;
 	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
 	int ret;
 
+	/*
+	 * Check nritems first, if the tree is empty we exit immediately.
+	 * And if this leave is not empty, none of the tree blocks of this root
+	 * should be empty.
+	 */
+	if (nritems == 0)
+		return 1;
+
+	/*
+	 * If we're several slots beyond nritems, we reset slot to nritems,
+	 * and it will be handled properly inside the loop.
+	 */
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
 			if (ret != 0)
 				return ret;
-		} else {
-			path->slots[0]--;
 		}
 		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;

fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739

Quoted 10 lines
fs/btrfs/ctree.c +8 -2
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		/*
+		 * This is for both regular case and above btrfs_prev_leaf() case.
+		 * As btrfs_prev_leaf() will return with path->slots[0] == nritems,
+		 * and we're sure no tree block is empty, we can go safely
+		 * reduce slots[0] here.
+		 */
+		path->slots[0]--;

This requires trusting that the thing on disk was ok. The tree-checker won't complain if we read a block with nritems == 0. I think it would be better to do

	if (btrfs_header_nritems(leaf) == 0) {
		ASSERT(btrfs_header_nritems(leaf));
		return -EUCLEAN;
	}

so we don't get ourselves in trouble. Thanks,

Josef

#4 lore raw
Quoted 88 lines · Josef Bacik
Quoted 73 lines · Qu Wenruo

In btrfs_previous_item() and btrfs_previous_extent_item() we check btrfs_header_nritems() in a loop.

But in fact we don't need to do it in a loop at all.

Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.

Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.

So this patch will move all the nritems related checks out of the loop by:

- Check nritems of nodes[0] to do a quick exit

- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.

- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, and btrfs_prev_leaf() will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extra ASSERT() to make sure no tree block is empty.

---
  fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++---------------
  1 file changed, 36 insertions(+), 16 deletions(-)
fs/btrfs/ctree.c +16 -6
index 781537692a4a..555345aed84d 100644
@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root,
  {
  	struct btrfs_key found_key;
  	struct extent_buffer *leaf;
-	u32 nritems;
+	const u32 nritems = btrfs_header_nritems(path->nodes[0]);
  	int ret;
 
+	/*
+	 * Check nritems first, if the tree is empty we exit immediately.
+	 * And if this leave is not empty, none of the tree blocks of this root
+	 * should be empty.
+	 */
+	if (nritems == 0)
+		return 1;
+
+	/*
+	 * If we're several slots beyond nritems, we reset slot to nritems,
+	 * and it will be handled properly inside the loop.
+	 */
+	if (unlikely(path->slots[0] > nritems))
+		path->slots[0] = nritems;
+
  	while (1) {
  		if (path->slots[0] == 0) {
  			ret = btrfs_prev_leaf(root, path);
  			if (ret != 0)
  				return ret;
-		} else {
-			path->slots[0]--;
  		}
  		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;

fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739

Quoted 10 lines
fs/btrfs/ctree.c +8 -2
-		if (path->slots[0] == nritems)
-			path->slots[0]--;
+		ASSERT(btrfs_header_nritems(leaf));
+		/*
+		 * This is for both regular case and above btrfs_prev_leaf() case.
+		 * As btrfs_prev_leaf() will return with path->slots[0] == nritems,
+		 * and we're sure no tree block is empty, we can go safely
+		 * reduce slots[0] here.
+		 */
+		path->slots[0]--;

This requires trusting that the thing on disk was ok. The tree-checker won't complain if we read a block with nritems == 0. I think it would be better to do

Quoted 6 lines
	if (btrfs_header_nritems(leaf) == 0) {
		ASSERT(btrfs_header_nritems(leaf));
		return -EUCLEAN;
	}

so we don't get ourselves in trouble. Thanks,

Please discard the patch completely.

Filipe pointed out that, btrfs_prev_leaf() is a btrfs_search_slot() call in fact, by searching previous key (current leave's first key value - 1).

Which could lead to a search slot hit (ret == 0), thus this patch is completely screwed up.

Thanks,
Qu

Quoted 2 lines

Josef