Skip to contentSkip to conversation

btrfs: add a find_contiguous_extent_bit helper and use it for safe isize

PATCH In review Josef Bacik 4 participants 7 messages Feb 12, 2020 – Feb 14, 2020 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 btrfs: add a find_contiguous_extent_bit helper and use it for safe isize

Filipe noticed a race where we would sometimes get the wrong answer for the i_disk_size for !NO_HOLES with my patch. That is because I expected that find_first_extent_bit() would find the contiguous range, since I'm only ever setting EXTENT_DIRTY. However the way set_extent_bit() works is it'll temporarily split the range, loop around and set our bits, and then merge the state. When it loops it drops the tree->lock, so there is a window where we can have two adjacent states instead of one large state. Fix this by walking forward until we find a non-contiguous state, and set our end_ret to the end of our logically contiguous area. This fixes the problem without relying on specific behavior from set_extent_bit().

Fixes 79ceff7f6e5d ("btrfs: introduce per-inode file extent tree")

---
Dave, I assume you'll want to fold this in to the referenced patch, if not let me know and I'll rework the series to include this as a different patch.

 fs/btrfs/extent-io-tree.h |  2 ++
 fs/btrfs/extent_io.c      | 36 ++++++++++++++++++++++++++++++++++++
 fs/btrfs/file-item.c      |  4 ++--
 3 files changed, 40 insertions(+), 2 deletions(-)
fs/btrfs/extent-io-tree.h +2 -0
index 16fd403447eb..cc3037f9765e 100644
@@ -223,6 +223,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
 			  struct extent_state **cached_state);
 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
 				 u64 *start_ret, u64 *end_ret, unsigned bits);
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+			       u64 *start_ret, u64 *end_ret, unsigned bits);
 int extent_invalidatepage(struct extent_io_tree *tree,
 			  struct page *page, unsigned long offset);
 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
fs/btrfs/extent_io.c +36 -0
index d91a48d73e8f..50bbaf1c7cf0 100644
@@ -1578,6 +1578,42 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
 	return ret;
 }
 
+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set
+ *
+ * set_extent_bit anc clear_extent_bit can temporarily split contiguous ranges
+ * to set bits appropriately, and then merge them again.  During this time it
+ * will drop the tree->lock, so use this helper if you want to find the actual
+ * contiguous area for given bits.  We will search to the first bit we find, and
+ * then walk down the tree until we find a non-contiguous area.  The area
+ * returned will be the full contiguous area with the bits set.
+ */
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+			       u64 *start_ret, u64 *end_ret, unsigned bits)
+{
+	struct extent_state *state;
+	int ret = 1;
+
+	spin_lock(&tree->lock);
+	state = find_first_extent_bit_state(tree, start, bits);
+	if (state) {
+		*start_ret = state->start;
+		*end_ret = state->end;
+		while ((state = next_state(state)) != NULL) {
+			if (state->start > (*end_ret + 1))
+				break;
+			*end_ret = state->end;
+		}
+		ret = 0;
+	}
+	spin_unlock(&tree->lock);
+	return ret;
+}
+
 /**
  * find_first_clear_extent_bit - find the first range that has @bits not set.
  * This range could start before @start.
fs/btrfs/file-item.c +2 -2
index a73878051761..6c849e8fd5a1 100644
@@ -51,8 +51,8 @@ void btrfs_inode_safe_disk_i_size_write(struct inode *inode, u64 new_i_size)
 	}
 
 	spin_lock(&BTRFS_I(inode)->lock);
-	ret = find_first_extent_bit(&BTRFS_I(inode)->file_extent_tree, 0,
-				    &start, &end, EXTENT_DIRTY, NULL);
+	ret = find_contiguous_extent_bit(&BTRFS_I(inode)->file_extent_tree, 0,
+					 &start, &end, EXTENT_DIRTY);
 	if (!ret && start == 0)
 		i_size = min(i_size, end + 1);
 	else
Signature · 1 line
2.24.1
#1 lore raw
Quoted 66 lines · Josef Bacik

Filipe noticed a race where we would sometimes get the wrong answer for the i_disk_size for !NO_HOLES with my patch. That is because I expected that find_first_extent_bit() would find the contiguous range, since I'm only ever setting EXTENT_DIRTY. However the way set_extent_bit() works is it'll temporarily split the range, loop around and set our bits, and then merge the state. When it loops it drops the tree->lock, so there is a window where we can have two adjacent states instead of one large state. Fix this by walking forward until we find a non-contiguous state, and set our end_ret to the end of our logically contiguous area. This fixes the problem without relying on specific behavior from set_extent_bit().

Fixes 79ceff7f6e5d ("btrfs: introduce per-inode file extent tree")

---
Dave, I assume you'll want to fold this in to the referenced patch, if not let me know and I'll rework the series to include this as a different patch.

 fs/btrfs/extent-io-tree.h |  2 ++
 fs/btrfs/extent_io.c      | 36 ++++++++++++++++++++++++++++++++++++
 fs/btrfs/file-item.c      |  4 ++--
 3 files changed, 40 insertions(+), 2 deletions(-)
fs/btrfs/extent-io-tree.h +2 -0
index 16fd403447eb..cc3037f9765e 100644
@@ -223,6 +223,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
                          struct extent_state **cached_state);
 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
                                 u64 *start_ret, u64 *end_ret, unsigned bits);
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits);
 int extent_invalidatepage(struct extent_io_tree *tree,
                          struct page *page, unsigned long offset);
 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
fs/btrfs/extent_io.c +21 -0
index d91a48d73e8f..50bbaf1c7cf0 100644
@@ -1578,6 +1578,42 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
        return ret;
 }
 
+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set
+ *
+ * set_extent_bit anc clear_extent_bit can temporarily split contiguous ranges
+ * to set bits appropriately, and then merge them again.  During this time it
+ * will drop the tree->lock, so use this helper if you want to find the actual
+ * contiguous area for given bits.  We will search to the first bit we find, and
+ * then walk down the tree until we find a non-contiguous area.  The area
+ * returned will be the full contiguous area with the bits set.
+ */
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits)
+{
+       struct extent_state *state;
+       int ret = 1;
+
+       spin_lock(&tree->lock);

fs/btrfs/extent_io.c int find_first_extent_bit(struct extent_io_tree *tree, u64 start, · line 1611

Quoted 10 lines
fs/btrfs/extent_io.c +10 -0
+       state = find_first_extent_bit_state(tree, start, bits);
+       if (state) {
+               *start_ret = state->start;
+               *end_ret = state->end;
+               while ((state = next_state(state)) != NULL) {
+                       if (state->start > (*end_ret + 1))
+                               break;
+                       *end_ret = state->end;
+               }
+               ret = 0;

So as long as the tree is not empty, we will always be returning 0 (success), right?
If we break from the while loop we should return with 1, but this makes us return 0.

thanks

Quoted 26 lines
fs/btrfs/extent_io.c +5 -0
+       }
+       spin_unlock(&tree->lock);
+       return ret;
+}
+
 /**
  * find_first_clear_extent_bit - find the first range that has @bits not set.
  * This range could start before @start.
fs/btrfs/file-item.c +2 -3
index a73878051761..6c849e8fd5a1 100644
@@ -51,8 +51,8 @@ void btrfs_inode_safe_disk_i_size_write(struct inode *inode, u64 new_i_size)
        }
 
        spin_lock(&BTRFS_I(inode)->lock);
-       ret = find_first_extent_bit(&BTRFS_I(inode)->file_extent_tree, 0,
-                                   &start, &end, EXTENT_DIRTY, NULL);
+       ret = find_contiguous_extent_bit(&BTRFS_I(inode)->file_extent_tree, 0,
+                                        &start, &end, EXTENT_DIRTY);
        if (!ret && start == 0)
                i_size = min(i_size, end + 1);
        else
--

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 74 lines · Filipe Manana
Quoted 73 lines · Josef Bacik

Filipe noticed a race where we would sometimes get the wrong answer for the i_disk_size for !NO_HOLES with my patch. That is because I expected that find_first_extent_bit() would find the contiguous range, since I'm only ever setting EXTENT_DIRTY. However the way set_extent_bit() works is it'll temporarily split the range, loop around and set our bits, and then merge the state. When it loops it drops the tree->lock, so there is a window where we can have two adjacent states instead of one large state. Fix this by walking forward until we find a non-contiguous state, and set our end_ret to the end of our logically contiguous area. This fixes the problem without relying on specific behavior from set_extent_bit().

Fixes 79ceff7f6e5d ("btrfs: introduce per-inode file extent tree")

---
Dave, I assume you'll want to fold this in to the referenced patch, if not let me know and I'll rework the series to include this as a different patch.

  fs/btrfs/extent-io-tree.h |  2 ++
  fs/btrfs/extent_io.c      | 36 ++++++++++++++++++++++++++++++++++++
  fs/btrfs/file-item.c      |  4 ++--
  3 files changed, 40 insertions(+), 2 deletions(-)
fs/btrfs/extent-io-tree.h +2 -0
index 16fd403447eb..cc3037f9765e 100644
@@ -223,6 +223,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
                           struct extent_state **cached_state);
  void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
                                  u64 *start_ret, u64 *end_ret, unsigned bits);
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits);
  int extent_invalidatepage(struct extent_io_tree *tree,
                           struct page *page, unsigned long offset);
  bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
fs/btrfs/extent_io.c +28 -0
index d91a48d73e8f..50bbaf1c7cf0 100644
@@ -1578,6 +1578,42 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
         return ret;
  }
 
+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set
+ *
+ * set_extent_bit anc clear_extent_bit can temporarily split contiguous ranges
+ * to set bits appropriately, and then merge them again.  During this time it
+ * will drop the tree->lock, so use this helper if you want to find the actual
+ * contiguous area for given bits.  We will search to the first bit we find, and
+ * then walk down the tree until we find a non-contiguous area.  The area
+ * returned will be the full contiguous area with the bits set.
+ */
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits)
+{
+       struct extent_state *state;
+       int ret = 1;
+
+       spin_lock(&tree->lock);
+       state = find_first_extent_bit_state(tree, start, bits);
+       if (state) {
+               *start_ret = state->start;
+               *end_ret = state->end;
+               while ((state = next_state(state)) != NULL) {
+                       if (state->start > (*end_ret + 1))
+                               break;
Quoted 9 lines

fs/btrfs/extent_io.c int find_first_extent_bit(struct extent_io_tree *tree, u64 start, · line 1611

Quoted 3 lines
fs/btrfs/extent_io.c +3 -0
+                       *end_ret = state->end;
+               }
+               ret = 0;

So as long as the tree is not empty, we will always be returning 0 (success), right?
If we break from the while loop we should return with 1, but this makes us return 0.

Yeah, that's the same behavior we have with find_first_extent_bit, that's why we do

if (!ret && start == 0)

	i_size = min(i_size, end + 1);
else
	i_size = 0;

Thanks,

Josef

#3 lore raw
Quoted 86 lines · Josef Bacik
Quoted 74 lines · Filipe Manana
Quoted 73 lines · Josef Bacik

Filipe noticed a race where we would sometimes get the wrong answer for the i_disk_size for !NO_HOLES with my patch. That is because I expected that find_first_extent_bit() would find the contiguous range, since I'm only ever setting EXTENT_DIRTY. However the way set_extent_bit() works is it'll temporarily split the range, loop around and set our bits, and then merge the state. When it loops it drops the tree->lock, so there is a window where we can have two adjacent states instead of one large state. Fix this by walking forward until we find a non-contiguous state, and set our end_ret to the end of our logically contiguous area. This fixes the problem without relying on specific behavior from set_extent_bit().

Fixes 79ceff7f6e5d ("btrfs: introduce per-inode file extent tree")

---
Dave, I assume you'll want to fold this in to the referenced patch, if not let me know and I'll rework the series to include this as a different patch.

  fs/btrfs/extent-io-tree.h |  2 ++
  fs/btrfs/extent_io.c      | 36 ++++++++++++++++++++++++++++++++++++
  fs/btrfs/file-item.c      |  4 ++--
  3 files changed, 40 insertions(+), 2 deletions(-)
fs/btrfs/extent-io-tree.h +2 -0
index 16fd403447eb..cc3037f9765e 100644
@@ -223,6 +223,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
                           struct extent_state **cached_state);
  void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
                                  u64 *start_ret, u64 *end_ret, unsigned bits);
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits);
  int extent_invalidatepage(struct extent_io_tree *tree,
                           struct page *page, unsigned long offset);
  bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
fs/btrfs/extent_io.c +28 -0
index d91a48d73e8f..50bbaf1c7cf0 100644
@@ -1578,6 +1578,42 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
         return ret;
  }
 
+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set
+ *
+ * set_extent_bit anc clear_extent_bit can temporarily split contiguous ranges
+ * to set bits appropriately, and then merge them again.  During this time it
+ * will drop the tree->lock, so use this helper if you want to find the actual
+ * contiguous area for given bits.  We will search to the first bit we find, and
+ * then walk down the tree until we find a non-contiguous area.  The area
+ * returned will be the full contiguous area with the bits set.
+ */
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits)
+{
+       struct extent_state *state;
+       int ret = 1;
+
+       spin_lock(&tree->lock);
+       state = find_first_extent_bit_state(tree, start, bits);
+       if (state) {
+               *start_ret = state->start;
+               *end_ret = state->end;
+               while ((state = next_state(state)) != NULL) {
+                       if (state->start > (*end_ret + 1))
+                               break;
Quoted 9 lines

fs/btrfs/extent_io.c int find_first_extent_bit(struct extent_io_tree *tree, u64 start, · line 1611

Quoted 3 lines
fs/btrfs/extent_io.c +3 -0
+                       *end_ret = state->end;
+               }
+               ret = 0;

So as long as the tree is not empty, we will always be returning 0 (success), right?
If we break from the while loop we should return with 1, but this makes us return 0.

Quoted 6 lines

Yeah, that's the same behavior we have with find_first_extent_bit, that's why we do

if (!ret && start == 0)

        i_size = min(i_size, end + 1);
else
        i_size = 0;

Yes, never mind, evening confusion.
It's correct indeed, and it fixes the problem as well (even without my optimization patch).

Quoted 4 lines

Thanks,

Josef

Signature · 3 lines
Filipe David Manana,

“Whether you think you can, or you think you can't — you're right.”
#4 lore raw
In reply to Josef Bacik

On 12/02/2020 19:38, Josef Bacik wrote:
[...]

Quoted 7 lines

+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set
+ *

Nit: The above it missing @bits

Reviewed-by on v1 1/1
#5 lore raw
In reply to Josef Bacik
Quoted 13 lines · Josef Bacik

Filipe noticed a race where we would sometimes get the wrong answer for the i_disk_size for !NO_HOLES with my patch. That is because I expected that find_first_extent_bit() would find the contiguous range, since I'm only ever setting EXTENT_DIRTY. However the way set_extent_bit() works is it'll temporarily split the range, loop around and set our bits, and then merge the state. When it loops it drops the tree->lock, so there is a window where we can have two adjacent states instead of one large state. Fix this by walking forward until we find a non-contiguous state, and set our end_ret to the end of our logically contiguous area. This fixes the problem without relying on specific behavior from set_extent_bit().

Quoted 2 lines
Fixes 79ceff7f6e5d ("btrfs: introduce per-inode file extent tree")

Alright, survived overnight tests (without my optimization patch), so it's all good.
Thanks.

Quoted 87 lines

---
Dave, I assume you'll want to fold this in to the referenced patch, if not let me know and I'll rework the series to include this as a different patch.

 fs/btrfs/extent-io-tree.h |  2 ++
 fs/btrfs/extent_io.c      | 36 ++++++++++++++++++++++++++++++++++++
 fs/btrfs/file-item.c      |  4 ++--
 3 files changed, 40 insertions(+), 2 deletions(-)
fs/btrfs/extent-io-tree.h +2 -0
index 16fd403447eb..cc3037f9765e 100644
@@ -223,6 +223,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
                          struct extent_state **cached_state);
 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
                                 u64 *start_ret, u64 *end_ret, unsigned bits);
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits);
 int extent_invalidatepage(struct extent_io_tree *tree,
                          struct page *page, unsigned long offset);
 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
fs/btrfs/extent_io.c +36 -0
index d91a48d73e8f..50bbaf1c7cf0 100644
@@ -1578,6 +1578,42 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
        return ret;
 }
 
+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set
+ *
+ * set_extent_bit anc clear_extent_bit can temporarily split contiguous ranges
+ * to set bits appropriately, and then merge them again.  During this time it
+ * will drop the tree->lock, so use this helper if you want to find the actual
+ * contiguous area for given bits.  We will search to the first bit we find, and
+ * then walk down the tree until we find a non-contiguous area.  The area
+ * returned will be the full contiguous area with the bits set.
+ */
+int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
+                              u64 *start_ret, u64 *end_ret, unsigned bits)
+{
+       struct extent_state *state;
+       int ret = 1;
+
+       spin_lock(&tree->lock);
+       state = find_first_extent_bit_state(tree, start, bits);
+       if (state) {
+               *start_ret = state->start;
+               *end_ret = state->end;
+               while ((state = next_state(state)) != NULL) {
+                       if (state->start > (*end_ret + 1))
+                               break;
+                       *end_ret = state->end;
+               }
+               ret = 0;
+       }
+       spin_unlock(&tree->lock);
+       return ret;
+}
+
 /**
  * find_first_clear_extent_bit - find the first range that has @bits not set.
  * This range could start before @start.
fs/btrfs/file-item.c +2 -3
index a73878051761..6c849e8fd5a1 100644
@@ -51,8 +51,8 @@ void btrfs_inode_safe_disk_i_size_write(struct inode *inode, u64 new_i_size)
        }
 
        spin_lock(&BTRFS_I(inode)->lock);
-       ret = find_first_extent_bit(&BTRFS_I(inode)->file_extent_tree, 0,
-                                   &start, &end, EXTENT_DIRTY, NULL);
+       ret = find_contiguous_extent_bit(&BTRFS_I(inode)->file_extent_tree, 0,
+                                        &start, &end, EXTENT_DIRTY);
        if (!ret && start == 0)
                i_size = min(i_size, end + 1);
        else
--

2.24.1

Signature · 3 lines
Filipe David Manana,

“Whether you think you can, or you think you can't — you're right.”
#6 lore raw
In reply to Josef Bacik
Quoted 12 lines · Josef Bacik

Filipe noticed a race where we would sometimes get the wrong answer for the i_disk_size for !NO_HOLES with my patch. That is because I expected that find_first_extent_bit() would find the contiguous range, since I'm only ever setting EXTENT_DIRTY. However the way set_extent_bit() works is it'll temporarily split the range, loop around and set our bits, and then merge the state. When it loops it drops the tree->lock, so there is a window where we can have two adjacent states instead of one large state. Fix this by walking forward until we find a non-contiguous state, and set our end_ret to the end of our logically contiguous area. This fixes the problem without relying on specific behavior from set_extent_bit().

Quoted 5 lines
Fixes 79ceff7f6e5d ("btrfs: introduce per-inode file extent tree")

---
Dave, I assume you'll want to fold this in to the referenced patch, if not let me know and I'll rework the series to include this as a different patch.

Folding looks like a good option, the patch adds other helper for btrfs_inode_clear_file_extent_range so this patch fits in nicely.

Quoted 6 lines

+/**
+ * find_contiguous_extent_bit: find a contiguous area of bits
+ * @tree - io tree to check
+ * @start - offset to start the search from
+ * @start_ret - the first offset we found with the bits set
+ * @end_ret - the final contiguous range of the bits that were set

Quoted 8 lines

+ *
+ * set_extent_bit anc clear_extent_bit can temporarily split contiguous ranges
+ * to set bits appropriately, and then merge them again. During this time it
+ * will drop the tree->lock, so use this helper if you want to find the actual
+ * contiguous area for given bits. We will search to the first bit we find, and
+ * then walk down the tree until we find a non-contiguous area. The area
+ * returned will be the full contiguous area with the bits set.
+ */

This summarizes why it's needed so the changelog does not need to be updated AFAICS. Patch updated and misc-next pushed. Thanks.