Linux-BTRFS Archive on lore.kernel.org
 help / color / Atom feed
From: Nikolay Borisov <nborisov@suse.com>
To: linux-btrfs@vger.kernel.org
Cc: dsterba@suse.cz, jeffm@suse.com, Nikolay Borisov <nborisov@suse.com>
Subject: [PATCH v3] btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit
Date: Thu, 31 Jan 2019 17:41:43 +0200
Message-ID: <20190131154143.11411-1-nborisov@suse.com> (raw)
In-Reply-To: <20190130145102.4708-16-nborisov@suse.com>

Instead of always calling the allocator to search for a free extent,
that satisfies the input criteria, switch btrfs_trim_free_extents to
using find_first_clear_extent_bit. With this change it's no longer
necessary to read the device tree in order to figure out holes in
the devices.

Now the code always searches in-memory data structure to figure out the
space range which contains the requested which should result in speed
oups.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
V3: 
 * Switch to using max_t to avoid build warning
V2: 
 * Explicitly ensure that the offset of the passed range is at least 1mb. This 
   mimics the behavior of the chunk allocator where the first megabyte of every 
   device is never touched. This ensures we are not screwing up with any bootloaders
   that might occupy the first megabyte. 
 fs/btrfs/extent-tree.c | 87 ++++++++++++------------------------------
 1 file changed, 24 insertions(+), 63 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index f5005ef39f98..04c5bd555177 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -11127,54 +11127,6 @@ int btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info,
 	return unpin_extent_range(fs_info, start, end, false);
 }
 
-static bool should_skip_trim(struct btrfs_device *device, u64 *start, u64 *len)
-{
-	u64 trimmed_start = 0, trimmed_end = 0;
-	u64 end = *start + *len - 1;
-
-	if (!find_first_extent_bit(&device->alloc_state, *start, &trimmed_start,
-				   &trimmed_end, CHUNK_TRIMMED, NULL)) {
-		u64 trimmed_len = trimmed_end - trimmed_start + 1;
-
-		if (*start < trimmed_start) {
-			if (in_range(end, trimmed_start, trimmed_len) ||
-			    end > trimmed_end) {
-				/*
-				 * start|------|end
-				 *      ts|--|trimmed_len
-				 *      OR
-				 * start|-----|end
-				 *      ts|-----|trimmed_len
-				 */
-				*len = trimmed_start - *start;
-				return false;
-			} else if (end < trimmed_start) {
-				/*
-				 * start|------|end
-				 *             ts|--|trimmed_len
-				 */
-				return false;
-			}
-		} else if (in_range(*start, trimmed_start, trimmed_len)) {
-			if (in_range(end, trimmed_start, trimmed_len)) {
-				/*
-				 * start|------|end
-				 *  ts|----------|trimmed_len
-				 */
-				return true;
-			} else {
-				/*
-				 * start|-----------|end
-				 *  ts|----------|trimmed_len
-				 */
-				*start = trimmed_end + 1;
-				*len = end - *start + 1;
-				return false;
-			}
-		}
-	}
-	return false;
-}
 /*
  * It used to be that old block groups would be left around forever.
  * Iterating over them would be enough to trim unused space.  Since we
@@ -11198,7 +11150,7 @@ static bool should_skip_trim(struct btrfs_device *device, u64 *start, u64 *len)
 static int btrfs_trim_free_extents(struct btrfs_device *device,
 				   struct fstrim_range *range, u64 *trimmed)
 {
-	u64 start = range->start, len = 0;
+	u64 start = max_t(u64, range->start, SZ_1M), len = 0, end = 0;
 	int ret;
 
 	*trimmed = 0;
@@ -11225,34 +11177,43 @@ static int btrfs_trim_free_extents(struct btrfs_device *device,
 		if (ret)
 			break;
 
-		ret = find_free_dev_extent_start(device, range->minlen, start,
-						 &start, &len);
-
+		ret = find_first_clear_extent_bit(&device->alloc_state, start,
+				&start, &end,
+				CHUNK_TRIMMED | CHUNK_ALLOCATED);
 		if (ret) {
 			mutex_unlock(&fs_info->chunk_mutex);
-			if (ret == -ENOSPC)
-				ret = 0;
+			ret = 0;
 			break;
 		}
+		/* If find_first_clear_extent_bit find a range that spans the
+		 * end of the device it will set end to -1, in this case it's up
+		 * to the caller to trim the value to the size of the device.
+		 */
+		end = min(end, device->total_bytes);
+		len = end - start + 1;
+
+		/* Keep going until we satisfy minlen or reach end of space */
+		if (len < range->minlen) {
+			mutex_unlock(&fs_info->chunk_mutex);
+			start += len;
+			continue;
+		}
 
 		/* If we are out of the passed range break */
 		if (start > range->start + range->len - 1) {
 			mutex_unlock(&fs_info->chunk_mutex);
-			ret = 0;
 			break;
 		}
 
 		start = max(range->start, start);
 		len = min(range->len, len);
 
-		if (!should_skip_trim(device, &start, &len)) {
-			ret = btrfs_issue_discard(device->bdev, start, len,
-						  &bytes);
-			if (!ret)
-				set_extent_bits(&device->alloc_state, start,
-						start + bytes - 1,
-						CHUNK_TRIMMED);
-		}
+		ret = btrfs_issue_discard(device->bdev, start, len,
+					  &bytes);
+		if (!ret)
+			set_extent_bits(&device->alloc_state, start,
+					start + bytes - 1,
+					CHUNK_TRIMMED);
 		mutex_unlock(&fs_info->chunk_mutex);
 
 		if (ret)
-- 
2.17.1


      parent reply index

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-30 14:50 [PATCH 00/15] Improvements to fitrim Nikolay Borisov
2019-01-30 14:50 ` [PATCH 01/15] btrfs: Honour FITRIM range constraints during free space trim Nikolay Borisov
2019-01-31 15:21   ` David Sterba
2019-01-31 15:35     ` Nikolay Borisov
2019-01-31 15:48       ` David Sterba
2019-01-31 19:30       ` Jeff Mahoney
2019-01-31 21:45         ` Nikolay Borisov
2019-01-30 14:50 ` [PATCH 02/15] btrfs: Make WARN_ON in a canonical form Nikolay Borisov
2019-01-31 15:22   ` David Sterba
2019-02-04 13:12   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 03/15] btrfs: Remove EXTENT_FIRST_DELALLOC bit Nikolay Borisov
2019-01-31 15:23   ` David Sterba
2019-02-04 13:15   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 04/15] btrfs: combine device update operations during transaction commit Nikolay Borisov
2019-02-04 13:25   ` Johannes Thumshirn
2019-02-04 14:48     ` Nikolay Borisov
2019-02-05  9:21       ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 05/15] btrfs: Handle pending/pinned chunks before blockgroup relocation during device shrink Nikolay Borisov
2019-02-04 13:29   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 06/15] btrfs: Rename and export clear_btree_io_tree Nikolay Borisov
2019-02-04 13:31   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 07/15] btrfs: Populate ->orig_block_len during read_one_chunk Nikolay Borisov
2019-01-30 14:50 ` [PATCH 08/15] btrfs: Introduce new bits for device allocation tree Nikolay Borisov
2019-01-30 14:50 ` [PATCH 09/15] btrfs: replace pending/pinned chunks lists with io tree Nikolay Borisov
2019-01-30 14:50 ` [PATCH 10/15] btrfs: Remove 'trans' argument from find_free_dev_extent(_start) Nikolay Borisov
2019-02-04 14:36   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 11/15] btrfs: Factor out in_range macro Nikolay Borisov
2019-02-04 13:57   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 12/15] btrfs: Optimize unallocated chunks discard Nikolay Borisov
2019-01-30 14:51 ` [PATCH 13/15] btrfs: Fix gross misnaming Nikolay Borisov
2019-01-30 14:51 ` [PATCH 14/15] btrfs: Implement find_first_clear_extent_bit Nikolay Borisov
2019-02-04 14:04   ` Johannes Thumshirn
2019-02-04 16:57   ` Nikolay Borisov
2019-01-30 14:51 ` [PATCH 15/15] btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit Nikolay Borisov
2019-01-31 15:38   ` [PATCH v2] " Nikolay Borisov
2019-01-31 15:41   ` Nikolay Borisov [this message]

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190131154143.11411-1-nborisov@suse.com \
    --to=nborisov@suse.com \
    --cc=dsterba@suse.cz \
    --cc=jeffm@suse.com \
    --cc=linux-btrfs@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-BTRFS Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-btrfs/0 linux-btrfs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-btrfs linux-btrfs/ https://lore.kernel.org/linux-btrfs \
		linux-btrfs@vger.kernel.org linux-btrfs@archiver.kernel.org
	public-inbox-index linux-btrfs


Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-btrfs


AGPL code for this site: git clone https://public-inbox.org/ public-inbox