clean up collapse range and handle post-eof delalloc

The collapse range implementation uses a transaction per extent shift. The progress of the overall operation is tracked via the current extent index of the in-core extent list. This is racy because the ilock must be dropped and reacquired for each transaction according to locking and log reservation rules. Therefore, writeback to prior regions of the file is possible and can change the extent count. This changes the extent to which the current index refers and causes the collapse to fail mid operation. To avoid this problem, the entire file is currently written back before the collapse operation starts.

To eliminate the need to flush the entire file, use the file offset (fsb) to track the progress of the overall extent shift operation rather than the extent index. Modify xfs_bmap_shift_extents() to unconditionally convert the start_fsb parameter to an extent index and return the file offset of the extent where the shift left off, if further extents exist. The bulk of ths function can remain based on extent index as ilock is held by the caller. xfs_collapse_file_space() now uses the fsb output as the starting point for the subsequent shift.

Signed-off-by Brian Foster <[email protected]>

The extent shift mechanism in xfs_bmap_shift_extents() is complicated and handles several different, non-deterministic scenarios. These include extent shifts, extent merges and potential btree updates in either of the former scenarios.

Refactor the code to be more linear and readable. The loop logic in xfs_bmap_shift_extents() and some initial error checking is adjusted slightly. The associated btree lookup and update/delete operations are condensed into single blocks of code. This reduces the number of btree-specific blocks and facilitates the separation of the merge operation into a new xfs_bmap_shift_extents_merge() helper. The merge check is also separated into an inline.

This is a code refactor only. The behavior of extent shift and collapse range is not modified.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_bmap.c | 243 ++++++++++++++++++++++++++++++++---------------
 1 file changed, 168 insertions(+), 75 deletions(-)

fs/xfs/libxfs/xfs_bmap.c +0 -0

index 4b3f1b9..449a016 100644

fs/xfs/libxfs/xfs_bmap.c +67 -0

+	struct xfs_bmbt_irec	*left,	/* preceding extent */
+	struct xfs_bmbt_irec	*got,	/* current extent to shift */
+	xfs_fileoff_t		shift)	/* shift fsb */
+{
+	xfs_fileoff_t		startoff;
+
+	startoff = got->br_startoff - shift;
+
+	/*
+	 * The extent, once shifted, must be adjacent in-file and on-disk with
+	 * the preceding extent.
+	 */
+	if ((left->br_startoff + left->br_blockcount != startoff) ||
+	    (left->br_startblock + left->br_blockcount != got->br_startblock) ||
+	    (left->br_state != got->br_state) ||
+	    (left->br_blockcount + got->br_blockcount > MAXEXTLEN))
+		return false;
+
+	return true;
+}
+
+/*
+ * An extent shift adjusts the file offset of an extent to fill a preceding hole
+ * in the file. If an extent shift would result in the extent being fully
+ * adjacent to the extent that currently precedes the hole, we can merge with
+ * the preceding extent rather than do the shift.
+ *
+ * This function assumes the caller has verified a shift-by-merge is possible
+ * with the provided extents via xfs_bmap_shift_extents_can_merge().
+ */
+static int
+xfs_bmap_shift_extents_merge(
+	struct xfs_inode		*ip,
+	int				whichfork,
+	xfs_fileoff_t			shift,		/* shift fsb */
+	int				current_ext,	/* idx of gotp */
+	struct xfs_bmbt_rec_host	*gotp,		/* extent to shift */
+	struct xfs_bmbt_rec_host	*leftp,		/* preceding extent */
+	struct xfs_btree_cur		*cur,
+	int				*logflags)	/* output */
+{
+	struct xfs_ifork		*ifp;
+	struct xfs_bmbt_irec		got;
+	struct xfs_bmbt_irec		left;
+	xfs_filblks_t			blockcount;
+	int				error, i;
+
+	ifp = XFS_IFORK_PTR(ip, whichfork);
+	xfs_bmbt_get_all(gotp, &got);
+	xfs_bmbt_get_all(leftp, &left);
+	blockcount = left.br_blockcount + got.br_blockcount;
+
+	ASSERT(xfs_isilocked(ip, XFS_IOLOCK_EXCL));
+	ASSERT(xfs_isilocked(ip, XFS_ILOCK_EXCL));
+	ASSERT(xfs_bmap_shift_extents_can_merge(&left, &got, shift));
+
+	/*
+	 * Merge the in-core extents. Note that the host record pointers and
+	 * current_ext index are invalid once the extent has been removed via
+	 * xfs_iext_remove().
+	 */
+	xfs_bmbt_set_blockcount(leftp, blockcount);
+	xfs_iext_remove(ip, current_ext, 1, 0);
+
+	/*
+	 * Update the on-disk extent count, the btree if necessary and log the
+	 * inode.

fs/xfs/libxfs/xfs_bmap.c +19 -0

+		XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+		error = xfs_btree_delete(cur, &i);
+		if (error)
+			goto error;
+		XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+		/* lookup and update size of the previous extent */
+		error = xfs_bmbt_lookup_eq(cur, left.br_startoff,
+				left.br_startblock, left.br_blockcount, &i);
+		if (error)
+			goto error;
+		XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+		left.br_blockcount = blockcount;
+
+		error = xfs_bmbt_update(cur, left.br_startoff,
+				left.br_startblock, left.br_blockcount,
+				left.br_state);

fs/xfs/libxfs/xfs_bmap.c +24 -18

@@ -5493,30 +5617,42 @@ xfs_bmap_shift_extents(
 	 */
 	total_extents = ifp->if_bytes / sizeof(xfs_bmbt_rec_t);
 	while (nexts++ < num_exts && current_ext < total_extents) {
-
-		gotp = xfs_iext_get_ext(ifp, current_ext);
-		xfs_bmbt_get_all(gotp, &got);
 		startoff = got.br_startoff - offset_shift_fsb;
 
-		/*
-		 * Before shifting extent into hole, make sure that the hole is
-		 * large enough to accommodate the shift.
-		 */
+		/* grab the left extent and check for a potential merge */
 		if (current_ext > 0) {
-			xfs_bmbt_get_all(xfs_iext_get_ext(ifp, current_ext - 1),
-					 &left);
-			if (startoff < left.br_startoff + left.br_blockcount)
+			leftp = xfs_iext_get_ext(ifp, current_ext - 1);
+			xfs_bmbt_get_all(leftp, &left);
+
+			/* make sure hole is large enough for shift */
+			if (startoff < left.br_startoff + left.br_blockcount) {
 				error = -EINVAL;
-		} else if (offset_shift_fsb > got.br_startoff) {
-			/*
-			 * When first extent is shifted, offset_shift_fsb should
-			 * be less than the stating offset of the first extent.
-			 */
-			error = -EINVAL;
+				goto del_cursor;
+			}
+
+			if (xfs_bmap_shift_extents_can_merge(&left, &got,
+							offset_shift_fsb)) {
+				error = xfs_bmap_shift_extents_merge(ip, whichfork,
+						offset_shift_fsb, current_ext, gotp,
+						leftp, cur, &logflags);
+				if (error)
+					goto del_cursor;
+
+				/*
+				 * The extent was merged so adjust the extent
+				 * index and move onto the next.
+				 */
+				current_ext--;
+				goto next;
+			}
 		}
-		if (error)
-			goto del_cursor;

Quoted 28 lines · Brian Foster

The extent shift mechanism in xfs_bmap_shift_extents() is complicated and handles several different, non-deterministic scenarios. These include extent shifts, extent merges and potential btree updates in either of the former scenarios.

Refactor the code to be more linear and readable. The loop logic in xfs_bmap_shift_extents() and some initial error checking is adjusted slightly. The associated btree lookup and update/delete operations are condensed into single blocks of code. This reduces the number of btree-specific blocks and facilitates the separation of the merge operation into a new xfs_bmap_shift_extents_merge() helper. The merge check is also separated into an inline.

This is a code refactor only. The behavior of extent shift and collapse range is not modified.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_bmap.c | 243 ++++++++++++++++++++++++++++++++---------------
 1 file changed, 168 insertions(+), 75 deletions(-)

fs/xfs/libxfs/xfs_bmap.c +0 -0

index 4b3f1b9..449a016 100644
@@ -5404,6 +5404,120 @@ error0:
 }
 

fs/xfs/libxfs/xfs_bmap.c error0: · line 5411

Quoted 6 lines

fs/xfs/libxfs/xfs_bmap.c +5 -0

 /*
+ * Determine whether an extent shift can be accomplished by a merge with the
+ * extent that precedes the target hole of the shift.
+ */
+static inline bool
+xfs_bmap_shift_extents_can_merge(

No need for "inline" for static functions. The compiler will do that as an optimisation if appropriate.

Quoted 72 lines

fs/xfs/libxfs/xfs_bmap.c +72 -0

+	struct xfs_bmbt_irec	*left,	/* preceding extent */
+	struct xfs_bmbt_irec	*got,	/* current extent to shift */
+	xfs_fileoff_t		shift)	/* shift fsb */
+{
+	xfs_fileoff_t		startoff;
+
+	startoff = got->br_startoff - shift;
+
+	/*
+	 * The extent, once shifted, must be adjacent in-file and on-disk with
+	 * the preceding extent.
+	 */
+	if ((left->br_startoff + left->br_blockcount != startoff) ||
+	    (left->br_startblock + left->br_blockcount != got->br_startblock) ||
+	    (left->br_state != got->br_state) ||
+	    (left->br_blockcount + got->br_blockcount > MAXEXTLEN))
+		return false;
+
+	return true;
+}
+
+/*
+ * An extent shift adjusts the file offset of an extent to fill a preceding hole
+ * in the file. If an extent shift would result in the extent being fully
+ * adjacent to the extent that currently precedes the hole, we can merge with
+ * the preceding extent rather than do the shift.
+ *
+ * This function assumes the caller has verified a shift-by-merge is possible
+ * with the provided extents via xfs_bmap_shift_extents_can_merge().
+ */
+static int
+xfs_bmap_shift_extents_merge(
+	struct xfs_inode		*ip,
+	int				whichfork,
+	xfs_fileoff_t			shift,		/* shift fsb */
+	int				current_ext,	/* idx of gotp */
+	struct xfs_bmbt_rec_host	*gotp,		/* extent to shift */
+	struct xfs_bmbt_rec_host	*leftp,		/* preceding extent */
+	struct xfs_btree_cur		*cur,
+	int				*logflags)	/* output */
+{
+	struct xfs_ifork		*ifp;
+	struct xfs_bmbt_irec		got;
+	struct xfs_bmbt_irec		left;
+	xfs_filblks_t			blockcount;
+	int				error, i;
+
+	ifp = XFS_IFORK_PTR(ip, whichfork);
+	xfs_bmbt_get_all(gotp, &got);
+	xfs_bmbt_get_all(leftp, &left);
+	blockcount = left.br_blockcount + got.br_blockcount;
+
+	ASSERT(xfs_isilocked(ip, XFS_IOLOCK_EXCL));
+	ASSERT(xfs_isilocked(ip, XFS_ILOCK_EXCL));
+	ASSERT(xfs_bmap_shift_extents_can_merge(&left, &got, shift));
+
+	/*
+	 * Merge the in-core extents. Note that the host record pointers and
+	 * current_ext index are invalid once the extent has been removed via
+	 * xfs_iext_remove().
+	 */
+	xfs_bmbt_set_blockcount(leftp, blockcount);
+	xfs_iext_remove(ip, current_ext, 1, 0);
+
+	/*
+	 * Update the on-disk extent count, the btree if necessary and log the
+	 * inode.
+	 */
+	XFS_IFORK_NEXT_SET(ip, whichfork,
+			   XFS_IFORK_NEXTENTS(ip, whichfork) - 1);
+	*logflags |= XFS_ILOG_CORE;
+	if (cur) {

fs/xfs/libxfs/xfs_bmap.c error0: · line 5488

Quoted 5 lines

fs/xfs/libxfs/xfs_bmap.c +5 -0

+		/* lookup and remove the extent to merge */
+		error = xfs_bmbt_lookup_eq(cur, got.br_startoff,
+				got.br_startblock, got.br_blockcount, &i);
+		if (error)
+			goto error;

Probably shouldn't give the jump label the same name as a variable in the function. "out_error" is commonly used here.

Quoted 24 lines

fs/xfs/libxfs/xfs_bmap.c +24 -0

+		XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+		error = xfs_btree_delete(cur, &i);
+		if (error)
+			goto error;
+		XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+		/* lookup and update size of the previous extent */
+		error = xfs_bmbt_lookup_eq(cur, left.br_startoff,
+				left.br_startblock, left.br_blockcount, &i);
+		if (error)
+			goto error;
+		XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+		left.br_blockcount = blockcount;
+
+		error = xfs_bmbt_update(cur, left.br_startoff,
+				left.br_startblock, left.br_blockcount,
+				left.br_state);
+		if (error)
+			goto error;
+	} else {
+		*logflags |= XFS_ILOG_DEXT;
+	}

fs/xfs/libxfs/xfs_bmap.c error0: · line 5517

Quoted 5 lines

fs/xfs/libxfs/xfs_bmap.c +5 -0

+
+	return 0;
+
+error:
+	return error;

This code is much clearer, though I'd get rid of further indents by changing the logic around like so:

....

	*logflags |= XFS_ILOG_CORE;
	if (!cur) {
		*logflags |= XFS_ILOG_DEXT;
		return 0;
	}

	/* lookup and remove the extent to merge */
	error = xfs_bmbt_lookup_eq(cur, got.br_startoff,
				got.br_startblock, got.br_blockcount, &i);
	if (error)
		goto out_error;

.....

	error = xfs_bmbt_update(cur, left.br_startoff,
				left.br_startblock, left.br_blockcount,
				left.br_state);
out_error:
	return error;
}

Quoted 51 lines

fs/xfs/libxfs/xfs_bmap.c +24 -18

@@ -5493,30 +5617,42 @@ xfs_bmap_shift_extents(
 	 */
 	total_extents = ifp->if_bytes / sizeof(xfs_bmbt_rec_t);
 	while (nexts++ < num_exts && current_ext < total_extents) {
-
-		gotp = xfs_iext_get_ext(ifp, current_ext);
-		xfs_bmbt_get_all(gotp, &got);
 		startoff = got.br_startoff - offset_shift_fsb;
 
-		/*
-		 * Before shifting extent into hole, make sure that the hole is
-		 * large enough to accommodate the shift.
-		 */
+		/* grab the left extent and check for a potential merge */
 		if (current_ext > 0) {
-			xfs_bmbt_get_all(xfs_iext_get_ext(ifp, current_ext - 1),
-					 &left);
-			if (startoff < left.br_startoff + left.br_blockcount)
+			leftp = xfs_iext_get_ext(ifp, current_ext - 1);
+			xfs_bmbt_get_all(leftp, &left);
+
+			/* make sure hole is large enough for shift */
+			if (startoff < left.br_startoff + left.br_blockcount) {
 				error = -EINVAL;
-		} else if (offset_shift_fsb > got.br_startoff) {
-			/*
-			 * When first extent is shifted, offset_shift_fsb should
-			 * be less than the stating offset of the first extent.
-			 */
-			error = -EINVAL;
+				goto del_cursor;
+			}
+
+			if (xfs_bmap_shift_extents_can_merge(&left, &got,
+							offset_shift_fsb)) {
+				error = xfs_bmap_shift_extents_merge(ip, whichfork,
+						offset_shift_fsb, current_ext, gotp,
+						leftp, cur, &logflags);
+				if (error)
+					goto del_cursor;
+
+				/*
+				 * The extent was merged so adjust the extent
+				 * index and move onto the next.
+				 */
+				current_ext--;
+				goto next;
+			}
 		}
-		if (error)
-			goto del_cursor;

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_shift_extents( · line 5658

Quoted 10 lines

fs/xfs/libxfs/xfs_bmap.c +6 -0

 
+		/*
+		 * We didn't merge the extent so do the shift. Update the start
+		 * offset in the in-core extent and btree, if necessary.
+		 */
+		xfs_bmbt_set_startoff(gotp, startoff);
+		logflags |= XFS_ILOG_CORE;
 		if (cur) {
 			error = xfs_bmbt_lookup_eq(cur, got.br_startoff,
 						   got.br_startblock,

This doesn't do a lot to improve the code. It increases the level of indent and, IMO, makes it harder to read. It's a classic case of function names getting so long there's no space left for the code...

So, how about s/xfs_bmap_shift_extents/xfs_bmse/ as a means of reducing the namespace verbosity? And, really, that whole loop body could be pushed into a separate function. i.e

        while (nexts++ < num_exts) {
		error = xfs_bmse_collapse_one(ip, ifp, cur, &current_ext, gotp,
					      offset_shift_fsb, &logflags);
		if (error)
			goto del_cursor;

		/* check against total extent count, grab the next record */
		total_extents = ifp->if_bytes / sizeof(xfs_bmbt_rec_t);
		if (current_ext >= total_extents)
			break;
		gotp = xfs_iext_get_ext(ifp, current_ext);
		xfs_bmbt_get_all(gotp, &got);
	}

That reduces all the jumps/error cases simply to return statements, allowing them to be ordered clearly to minimise the indent of the code. It also means that way the value of current_ext changes is obvious, rather than having the decrement/increment because of the "next iteration" handling in the loop always incrementing the value.

Even the initial check outside the loop for:

        if (current_ext == 0 && got.br_startoff < offset_shift_fsb) {
		error = -EINVAL;
		goto del_cursor
	}

could be driven inside xfs_bmse_collapse_one() as the first check that is done, and that would further simplify xfs_bmap_shift_extents(). i.e.

xfs_bmse_collapse_one()

{
	if (*current_ext == 0) {
		if (got.br_startoff < offset_shift_fsb)
			return -EINVAL;
		goto shift_extent;
	}

	/* get left, do merge checks */
	....
	if (!xfs_bmse_can_merge(&left, &got, offset_shift_fsb))
		goto shift_extent;

	return xfs_bmse_merge(ip, whichfork, ...)

shift_extent:

	(*current_ext)++;
	xfs_bmbt_set_startoff(gotp, startoff);
	logflags |= XFS_ILOG_CORE;
	if (!cur)
		*logflags |= XFS_ILOG_DEXT;
		return 0;
	}

	/* do btree shift */
	....
	return error;
}

This way we end up with a set of well defined operations, along with clear logic on how they are iterated to make do the overall shift operation.

What do you think?

Cheers,

Dave.

Signature · 7 lines

Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

The collapse range operation currently writes the entire file before starting the collapse to avoid changes in the in-core extent list due to writeback causing the extent count to change. Now that collapse range is fsb based rather than extent index based it can sustain changes in the extent list during the shift sequence without disruption.

Modify xfs_collapse_file_space() to writeback and invalidate pages associated with the range of the file to be shifted. xfs_free_file_space() currently has similar behavior, but the space free need only affect the region of the file that is freed and this could change in the future.

Also update the comments to reflect the current implementation. We retain the eofblocks trim permanently as a best option for dealing with delalloc extents. We don't shift delalloc extents because this scenario only occurs with post-eof preallocation (since data must be flushed such that the cache can be invalidated and data can be shifted). That means said space must also be initialized before being shifted into the accessible region of the file only to be immediately truncated off as the last part of the collapse. In other words, the eofblocks trim will happen anyways, we just run it first to ensure the file remains in a consistent state throughout the collapse.

Finally, BUG() in the event of a delalloc extent during the extent shift such that a failure is obvious. The implementation explicitly does not support delalloc extents and the caller is expected to prevent this scenario in advance as is done by collapse.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_bmap.c |  2 ++
 fs/xfs/xfs_bmap_util.c   | 32 +++++++++++++++++++-------------
 2 files changed, 21 insertions(+), 13 deletions(-)

fs/xfs/libxfs/xfs_bmap.c +0 -0

index 449a016..1dd04c2 100644

Quoted 34 lines · Brian Foster

The collapse range operation currently writes the entire file before starting the collapse to avoid changes in the in-core extent list due to writeback causing the extent count to change. Now that collapse range is fsb based rather than extent index based it can sustain changes in the extent list during the shift sequence without disruption.

Modify xfs_collapse_file_space() to writeback and invalidate pages associated with the range of the file to be shifted. xfs_free_file_space() currently has similar behavior, but the space free need only affect the region of the file that is freed and this could change in the future.

Also update the comments to reflect the current implementation. We retain the eofblocks trim permanently as a best option for dealing with delalloc extents. We don't shift delalloc extents because this scenario only occurs with post-eof preallocation (since data must be flushed such that the cache can be invalidated and data can be shifted). That means said space must also be initialized before being shifted into the accessible region of the file only to be immediately truncated off as the last part of the collapse. In other words, the eofblocks trim will happen anyways, we just run it first to ensure the file remains in a consistent state throughout the collapse.

Finally, BUG() in the event of a delalloc extent during the extent shift such that a failure is obvious. The implementation explicitly does not support delalloc extents and the caller is expected to prevent this scenario in advance as is done by collapse.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_bmap.c |  2 ++
 fs/xfs/xfs_bmap_util.c   | 32 +++++++++++++++++++-------------
 2 files changed, 21 insertions(+), 13 deletions(-)

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_shift_extents( · line 5621

Quoted 10 lines

fs/xfs/libxfs/xfs_bmap.c +2 -0

index 449a016..1dd04c2 100644
@@ -5617,6 +5617,8 @@ xfs_bmap_shift_extents(
 	 */
 	total_extents = ifp->if_bytes / sizeof(xfs_bmbt_rec_t);
 	while (nexts++ < num_exts && current_ext < total_extents) {
+		/* can't handle delalloc extents */
+		BUG_ON(isnullstartblock(got.br_startblock));

XFS_WANT_CORRUPTED_GOTO() would be better, I think.

Otherwise OK.

Cheers,

Dave.

Signature · 7 lines

Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

xfs_free_file_space() only affects the range of the file for which space is being freed. It currently writes and truncates the page cache from the start offset of the free to EOF.

Modify xfs_free_file_space() to write back and truncate page cache of just the range being freed.

Signed-off-by Brian Foster <[email protected]>