[PATCH 0/5] xfs: fix AIL bulk insert issues and cleanups

[PATCH 0/5] xfs: fix AIL bulk insert issues and cleanups

[Dave Chinner]

The first two patches fix the recently reported rm -rf performance
and interactivity problems when using delayœd logging. These should
probably be considered for 3.0-rc5.

The last three patches are cleanups and tracepoints that I came
across while finding and fixing the above bugs. They can probably
wait until 3.1.

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH 1/5] xfs: unpin stale inodes directly in IOP_COMMITTED

[Dave Chinner]

From: Dave Chinner <dchinner@redhat.com>

When inodes are marked stale in a transaction, they are treated
specially when the iinode log item is being inserted into the AIL.
It trieѕ to avoid moving the log item forward in the AIL due to a
race condition with the writing the underlying buffer back to disk.
The was "fixed" in commit de25c18 ("xfs: avoid moving stale inodes in
the AIL").

To avoid moving the item forward, we return a LSN smaller than the
commit_lsn of the completing transaction, thereby trying to trick
the commit code into not moving the inode forward at all. I'm not
sure this ever worked as intended - it assumes the inode is already
in the AIL, but I don't think the returned LSN would have been small
enough to prevent moving the inode. It appears that the reason it
worked is that the lower LSN of the inodes meant they were inserted
into the AIL and flushed before the inode buffer (which was moved to
the commit_lsn of the transaction).

The big problem is that with delayed logging, the returning of the
different LSN means insertion takes the slow, non-bulk path.  Worse
yet is that insertion is to a position -before- the commit_lsn so it
is doing a AIL traversal on every insertion, and has to walk over
all the items that have already been inserted into the AIL. It's
expensive.

To compound the matter further, with delayed logging inodes are
likely to go from clean to stale in a single checkpoint, which means
they aren't even in the AIL at all when we come across them at AIL
insertion time. Hence these were all getting inserted into the AIL
when they simply do not need to be as inodes marked XFS_ISTALE are
never written back.

Transactional/recovery integrity is maintained in this case by the
other items in the unlink transaction that were modified (e.g. the
AGI btree blocks) and committed in the same checkpoint.

So to fix this, simply unpin the stale inodes directly in
xfs_inode_item_committed() and return -1 to indicate that the AIL
insertion code does not need to do any further processing of these
inodes.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
---
 fs/xfs/xfs_inode_item.c |   14 ++++++++------
 fs/xfs/xfs_trans.c      |    2 +-
 2 files changed, 9 insertions(+), 7 deletions(-)

diff --git a/fs/xfs/xfs_inode_item.c b/fs/xfs/xfs_inode_item.c
index 09983a3..b1e88d5 100644
--- a/fs/xfs/xfs_inode_item.c
+++ b/fs/xfs/xfs_inode_item.c
@@ -681,15 +681,15 @@ xfs_inode_item_unlock(
  * where the cluster buffer may be unpinned before the inode is inserted into
  * the AIL during transaction committed processing. If the buffer is unpinned
  * before the inode item has been committed and inserted, then it is possible
- * for the buffer to be written and IO completions before the inode is inserted
+ * for the buffer to be written and IO completes before the inode is inserted
  * into the AIL. In that case, we'd be inserting a clean, stale inode into the
  * AIL which will never get removed. It will, however, get reclaimed which
  * triggers an assert in xfs_inode_free() complaining about freein an inode
  * still in the AIL.
  *
- * To avoid this, return a lower LSN than the one passed in so that the
- * transaction committed code will not move the inode forward in the AIL but
- * will still unpin it properly.
+ * To avoid this, just unpin the inode directly and return a LSN of -1 so the
+ * transaction committed code knows that it does not need to do any further
+ * processing on the item.
  */
 STATIC xfs_lsn_t
 xfs_inode_item_committed(
@@ -699,8 +699,10 @@ xfs_inode_item_committed(
 	struct xfs_inode_log_item *iip = INODE_ITEM(lip);
 	struct xfs_inode	*ip = iip->ili_inode;
 
-	if (xfs_iflags_test(ip, XFS_ISTALE))
-		return lsn - 1;
+	if (xfs_iflags_test(ip, XFS_ISTALE)) {
+		xfs_inode_item_unpin(lip, 0);
+		return -1;
+	}
 	return lsn;
 }
 
diff --git a/fs/xfs/xfs_trans.c b/fs/xfs/xfs_trans.c
index 7c7bc2b..3744337 100644
--- a/fs/xfs/xfs_trans.c
+++ b/fs/xfs/xfs_trans.c
@@ -1474,7 +1474,7 @@ xfs_trans_committed_bulk(
 			lip->li_flags |= XFS_LI_ABORTED;
 		item_lsn = IOP_COMMITTED(lip, commit_lsn);
 
-		/* item_lsn of -1 means the item was freed */
+		/* item_lsn of -1 means the item needs no further processing */
 		if (XFS_LSN_CMP(item_lsn, (xfs_lsn_t)-1) == 0)
 			continue;
 
-- 
1.7.5.1

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 1/5] xfs: unpin stale inodes directly in IOP_COMMITTED

[Christoph Hellwig]

On Mon, Jul 04, 2011 at 03:27:36PM +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> When inodes are marked stale in a transaction, they are treated
> specially when the iinode log item is being inserted into the AIL.

s/iinode/inode/

> It trie?? to avoid moving the log item forward in the AIL due to a

Weird character.

Otherwise looks good good.

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 1/5] xfs: unpin stale inodes directly in IOP_COMMITTED

[Alex Elder]

On Mon, 2011-07-04 at 15:27 +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> When inodes are marked stale in a transaction, they are treated
> specially when the iinode log item is being inserted into the AIL.
> It trieѕ to avoid moving the log item forward in the AIL due to a
> race condition with the writing the underlying buffer back to disk.
> The was "fixed" in commit de25c18 ("xfs: avoid moving stale inodes in
> the AIL").
> 
> To avoid moving the item forward, we return a LSN smaller than the
> commit_lsn of the completing transaction, thereby trying to trick
> the commit code into not moving the inode forward at all. I'm not
> sure this ever worked as intended - it assumes the inode is already
> in the AIL, but I don't think the returned LSN would have been small
> enough to prevent moving the inode. It appears that the reason it
> worked is that the lower LSN of the inodes meant they were inserted
> into the AIL and flushed before the inode buffer (which was moved to
> the commit_lsn of the transaction).
> 
> The big problem is that with delayed logging, the returning of the
> different LSN means insertion takes the slow, non-bulk path.  Worse
> yet is that insertion is to a position -before- the commit_lsn so it
> is doing a AIL traversal on every insertion, and has to walk over
> all the items that have already been inserted into the AIL. It's
> expensive.
> 
> To compound the matter further, with delayed logging inodes are
> likely to go from clean to stale in a single checkpoint, which means
> they aren't even in the AIL at all when we come across them at AIL
> insertion time. Hence these were all getting inserted into the AIL
> when they simply do not need to be as inodes marked XFS_ISTALE are
> never written back.
> 
> Transactional/recovery integrity is maintained in this case by the
> other items in the unlink transaction that were modified (e.g. the
> AGI btree blocks) and committed in the same checkpoint.
> 
> So to fix this, simply unpin the stale inodes directly in
> xfs_inode_item_committed() and return -1 to indicate that the AIL
> insertion code does not need to do any further processing of these
> inodes.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>

I suggest one comment update, which I can do for
you or it can be done at another time.

But this looks good.  I'll send it to Linus
tomorrow.

Reviewed-by: Alex Elder <aelder@sgi.com>

> ---
>  fs/xfs/xfs_inode_item.c |   14 ++++++++------
>  fs/xfs/xfs_trans.c      |    2 +-
>  2 files changed, 9 insertions(+), 7 deletions(-)
> 
> diff --git a/fs/xfs/xfs_inode_item.c b/fs/xfs/xfs_inode_item.c
> index 09983a3..b1e88d5 100644

. . .

> diff --git a/fs/xfs/xfs_trans.c b/fs/xfs/xfs_trans.c
> index 7c7bc2b..3744337 100644
> --- a/fs/xfs/xfs_trans.c
> +++ b/fs/xfs/xfs_trans.c
> @@ -1474,7 +1474,7 @@ xfs_trans_committed_bulk(
>  			lip->li_flags |= XFS_LI_ABORTED;
>  		item_lsn = IOP_COMMITTED(lip, commit_lsn);
>  
> -		/* item_lsn of -1 means the item was freed */
> +		/* item_lsn of -1 means the item needs no further processing */

Probably should update the corresponding comment in
xfs_trans_item_committed() too.  I have done this in
my local copy.

>  		if (XFS_LSN_CMP(item_lsn, (xfs_lsn_t)-1) == 0)
>  			continue;
>  



_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Dave Chinner]

From: Dave Chinner <dchinner@redhat.com>

Delayed logging can insert tens of thousands of log items into the
AIL at the same LSN. When the committing of log commit records
occur, we can get insertions occurring at an LSN that is not at the
end of the AIL. If there are thousands of items in the AIL on the
tail LSN, each insertion has to walk the AIL to find the correct
place to insert the new item into the AIL. This can consume large
amounts of CPU time and block other operations from occurring while
the traversals are in progress.

To avoid this repeated walk, use a AIL cursor to record
where we should be inserting the new items into the AIL without
having to repeat the walk. The cursor infrastructure already
provides this functionality for push walks, so is a simple extension
of existing code. While this will not avoid the initial walk, it
will avoid repeating it tens of thousands of times during a single
checkpoint commit.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
---
 fs/xfs/xfs_trans.c      |   27 +++++++++--
 fs/xfs/xfs_trans_ail.c  |  122 +++++++++++++++++++++++++++++++++++++++--------
 fs/xfs/xfs_trans_priv.h |   10 +++-
 3 files changed, 131 insertions(+), 28 deletions(-)

diff --git a/fs/xfs/xfs_trans.c b/fs/xfs/xfs_trans.c
index 3744337..d5d5708 100644
--- a/fs/xfs/xfs_trans.c
+++ b/fs/xfs/xfs_trans.c
@@ -1426,6 +1426,7 @@ xfs_trans_committed(
 static inline void
 xfs_log_item_batch_insert(
 	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
 	struct xfs_log_item	**log_items,
 	int			nr_items,
 	xfs_lsn_t		commit_lsn)
@@ -1434,7 +1435,7 @@ xfs_log_item_batch_insert(
 
 	spin_lock(&ailp->xa_lock);
 	/* xfs_trans_ail_update_bulk drops ailp->xa_lock */
-	xfs_trans_ail_update_bulk(ailp, log_items, nr_items, commit_lsn);
+	xfs_trans_ail_update_bulk(ailp, cur, log_items, nr_items, commit_lsn);
 
 	for (i = 0; i < nr_items; i++)
 		IOP_UNPIN(log_items[i], 0);
@@ -1452,6 +1453,13 @@ xfs_log_item_batch_insert(
  * as an iclog write error even though we haven't started any IO yet. Hence in
  * this case all we need to do is IOP_COMMITTED processing, followed by an
  * IOP_UNPIN(aborted) call.
+ *
+ * The AIL cursor is used to optimise the insert process. If commit_lsn is not
+ * at the end of the AIL, the insert cursor avoids the need to walk
+ * the AIL to find the insertion point on every xfs_log_item_batch_insert()
+ * call. This saves a lot of needless list walking and is a net win, even
+ * though it slightly increases that amount of AIL lock traffic to set it up
+ * and tear it down.
  */
 void
 xfs_trans_committed_bulk(
@@ -1463,8 +1471,13 @@ xfs_trans_committed_bulk(
 #define LOG_ITEM_BATCH_SIZE	32
 	struct xfs_log_item	*log_items[LOG_ITEM_BATCH_SIZE];
 	struct xfs_log_vec	*lv;
+	struct xfs_ail_cursor	cur;
 	int			i = 0;
 
+	spin_lock(&ailp->xa_lock);
+	xfs_trans_ail_cursor_last(ailp, &cur, commit_lsn);
+	spin_unlock(&ailp->xa_lock);
+
 	/* unpin all the log items */
 	for (lv = log_vector; lv; lv = lv->lv_next ) {
 		struct xfs_log_item	*lip = lv->lv_item;
@@ -1493,7 +1506,9 @@ xfs_trans_committed_bulk(
 			/*
 			 * Not a bulk update option due to unusual item_lsn.
 			 * Push into AIL immediately, rechecking the lsn once
-			 * we have the ail lock. Then unpin the item.
+			 * we have the ail lock. Then unpin the item. This does
+			 * not affect the AIL cursor the bulk insert path is
+			 * using.
 			 */
 			spin_lock(&ailp->xa_lock);
 			if (XFS_LSN_CMP(item_lsn, lip->li_lsn) > 0)
@@ -1507,7 +1522,7 @@ xfs_trans_committed_bulk(
 		/* Item is a candidate for bulk AIL insert.  */
 		log_items[i++] = lv->lv_item;
 		if (i >= LOG_ITEM_BATCH_SIZE) {
-			xfs_log_item_batch_insert(ailp, log_items,
+			xfs_log_item_batch_insert(ailp, &cur, log_items,
 					LOG_ITEM_BATCH_SIZE, commit_lsn);
 			i = 0;
 		}
@@ -1515,7 +1530,11 @@ xfs_trans_committed_bulk(
 
 	/* make sure we insert the remainder! */
 	if (i)
-		xfs_log_item_batch_insert(ailp, log_items, i, commit_lsn);
+		xfs_log_item_batch_insert(ailp, &cur, log_items, i, commit_lsn);
+
+	spin_lock(&ailp->xa_lock);
+	xfs_trans_ail_cursor_done(ailp, &cur);
+	spin_unlock(&ailp->xa_lock);
 }
 
 /*
diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
index 5fc2380..272e7fa 100644
--- a/fs/xfs/xfs_trans_ail.c
+++ b/fs/xfs/xfs_trans_ail.c
@@ -272,9 +272,9 @@ xfs_trans_ail_cursor_clear(
 }
 
 /*
- * Return the item in the AIL with the current lsn.
- * Return the current tree generation number for use
- * in calls to xfs_trans_next_ail().
+ * Initialise the cursor to the first item in the AIL with the given @lsn.
+ * This searches the list from lowest LSN to highest. Pass a @lsn of zero
+ * to initialise the cursor to the first item in the AIL.
  */
 xfs_log_item_t *
 xfs_trans_ail_cursor_first(
@@ -300,31 +300,110 @@ out:
 }
 
 /*
- * splice the log item list into the AIL at the given LSN.
+ * Initialise the cursor to the last item in the AIL with the given @lsn.
+ * This searches the list from highest LSN to lowest.
  */
-static void
-xfs_ail_splice(
-	struct xfs_ail  *ailp,
-	struct list_head *list,
-	xfs_lsn_t       lsn)
+static struct xfs_log_item *
+__xfs_trans_ail_cursor_last(
+	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
+	xfs_lsn_t		lsn,
+	bool			do_init)
 {
-	xfs_log_item_t  *next_lip;
+	xfs_log_item_t		*lip = NULL;
 
-	/* If the list is empty, just insert the item.  */
-	if (list_empty(&ailp->xa_ail)) {
-		list_splice(list, &ailp->xa_ail);
-		return;
-	}
+	if (do_init)
+		xfs_trans_ail_cursor_init(ailp, cur);
+
+	if (list_empty(&ailp->xa_ail)) 
+		goto out;
 
-	list_for_each_entry_reverse(next_lip, &ailp->xa_ail, li_ail) {
-		if (XFS_LSN_CMP(next_lip->li_lsn, lsn) <= 0)
+	list_for_each_entry_reverse(lip, &ailp->xa_ail, li_ail) {
+		if (XFS_LSN_CMP(lip->li_lsn, lsn) <= 0)
 			break;
 	}
+out:
+	if (cur)
+		cur->item = lip;
+	return lip;
+}
 
-	ASSERT(&next_lip->li_ail == &ailp->xa_ail ||
-	       XFS_LSN_CMP(next_lip->li_lsn, lsn) <= 0);
+/*
+ * Initialise the cursor to the last item in the AIL with the given @lsn.
+ * This searches the list from highest LSN to lowest.
+ */
+struct xfs_log_item *
+xfs_trans_ail_cursor_last(
+	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
+	xfs_lsn_t		lsn)
+{
+	return __xfs_trans_ail_cursor_last(ailp, cur, lsn, true);
+}
 
-	list_splice_init(list, &next_lip->li_ail);
+/*
+ * splice the log item list into the AIL at the given LSN. We splice to the
+ * tail of the given LSN to maintain insert order for push traversals. The
+ * cursor is optional, allowing repeated updates to the same LSN to avoid
+ * repeated traversals.
+ */
+static void
+xfs_ail_splice(
+	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
+	struct list_head	*list,
+	xfs_lsn_t		lsn)
+{
+	struct xfs_log_item	*lip = cur ? cur->item : NULL;
+	struct xfs_log_item	*next_lip;
+
+	do {
+		/* no placeholder, so get our insert location */
+		if (!lip)
+			lip = __xfs_trans_ail_cursor_last(ailp, cur,
+								lsn, false);
+
+		if (!lip) {
+			/*
+			 * The list is empty, so just splice and return.  Our
+			 * cursor is already guaranteed to be up to date, so we
+			 * don't need to touch it here.
+			 */
+			list_splice(list, &ailp->xa_ail);
+			return;
+		}
+
+		/* The placeholder was invalidated, need to get a new cursor */
+		if ((__psint_t)lip & 1)
+			lip = NULL;
+
+	} while (lip == NULL);
+
+	/*
+	 * Our cursor points to the item we want to insert _after_, so we have
+	 * to update the cursor to point to the end of the list we are splicing
+	 * in so that it points to the correct location for the next splice.
+	 * i.e. before the splice
+	 *
+	 *  lsn -> lsn -> lsn + x -> lsn + x ...
+	 *          ^
+	 *          | cursor points here
+	 *
+	 * After the splice we have:
+	 *
+	 *  lsn -> lsn -> lsn -> lsn -> .... -> lsn -> lsn + x -> lsn + x ...
+	 *          ^                            ^
+	 *          | cursor points here         | needs to move here
+	 *
+	 * So we set the cursor to the last item in the list to be spliced
+	 * before we execute the splice, resulting in the cursor pointing to
+	 * the correct item after the splice occurs.
+	 */
+	if (cur) {
+		next_lip = list_entry(list->prev, struct xfs_log_item, li_ail);
+		cur->item = next_lip;
+	}
+	list_splice_init(list, &lip->li_ail);
 }
 
 /*
@@ -645,6 +724,7 @@ xfs_trans_unlocked_item(
 void
 xfs_trans_ail_update_bulk(
 	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
 	struct xfs_log_item	**log_items,
 	int			nr_items,
 	xfs_lsn_t		lsn) __releases(ailp->xa_lock)
@@ -674,7 +754,7 @@ xfs_trans_ail_update_bulk(
 		list_add(&lip->li_ail, &tmp);
 	}
 
-	xfs_ail_splice(ailp, &tmp, lsn);
+	xfs_ail_splice(ailp, cur, &tmp, lsn);
 
 	if (!mlip_changed) {
 		spin_unlock(&ailp->xa_lock);
diff --git a/fs/xfs/xfs_trans_priv.h b/fs/xfs/xfs_trans_priv.h
index 6b164e9..c0cb408 100644
--- a/fs/xfs/xfs_trans_priv.h
+++ b/fs/xfs/xfs_trans_priv.h
@@ -82,6 +82,7 @@ struct xfs_ail {
 extern struct workqueue_struct	*xfs_ail_wq;	/* AIL workqueue */
 
 void	xfs_trans_ail_update_bulk(struct xfs_ail *ailp,
+				struct xfs_ail_cursor *cur,
 				struct xfs_log_item **log_items, int nr_items,
 				xfs_lsn_t lsn) __releases(ailp->xa_lock);
 static inline void
@@ -90,7 +91,7 @@ xfs_trans_ail_update(
 	struct xfs_log_item	*lip,
 	xfs_lsn_t		lsn) __releases(ailp->xa_lock)
 {
-	xfs_trans_ail_update_bulk(ailp, &lip, 1, lsn);
+	xfs_trans_ail_update_bulk(ailp, NULL, &lip, 1, lsn);
 }
 
 void	xfs_trans_ail_delete_bulk(struct xfs_ail *ailp,
@@ -111,10 +112,13 @@ xfs_lsn_t		xfs_ail_min_lsn(struct xfs_ail *ailp);
 void			xfs_trans_unlocked_item(struct xfs_ail *,
 					xfs_log_item_t *);
 
-struct xfs_log_item	*xfs_trans_ail_cursor_first(struct xfs_ail *ailp,
+struct xfs_log_item *	xfs_trans_ail_cursor_first(struct xfs_ail *ailp,
 					struct xfs_ail_cursor *cur,
 					xfs_lsn_t lsn);
-struct xfs_log_item	*xfs_trans_ail_cursor_next(struct xfs_ail *ailp,
+struct xfs_log_item *	xfs_trans_ail_cursor_last(struct xfs_ail *ailp,
+					struct xfs_ail_cursor *cur,
+					xfs_lsn_t lsn);
+struct xfs_log_item *	xfs_trans_ail_cursor_next(struct xfs_ail *ailp,
 					struct xfs_ail_cursor *cur);
 void			xfs_trans_ail_cursor_done(struct xfs_ail *ailp,
 					struct xfs_ail_cursor *cur);
-- 
1.7.5.1

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Christoph Hellwig]

>  /*
> + * Initialise the cursor to the last item in the AIL with the given @lsn.
> + * This searches the list from highest LSN to lowest.
>   */
> +static struct xfs_log_item *
> +__xfs_trans_ail_cursor_last(
> +	struct xfs_ail		*ailp,
> +	struct xfs_ail_cursor	*cur,
> +	xfs_lsn_t		lsn,
> +	bool			do_init)
>  {
> +	xfs_log_item_t		*lip = NULL;
>  
> +	if (do_init)
> +		xfs_trans_ail_cursor_init(ailp, cur);
> +
> +	if (list_empty(&ailp->xa_ail)) 
> +		goto out;
>  
> +	list_for_each_entry_reverse(lip, &ailp->xa_ail, li_ail) {
> +		if (XFS_LSN_CMP(lip->li_lsn, lsn) <= 0)
>  			break;
>  	}
> +out:
> +	if (cur)
> +		cur->item = lip;
> +	return lip;
> +}

Please just move the xfs_trans_ail_cursor_init call to
xfs_trans_ail_cursor_init instead of adding the do_init parameter.
Also the list_empty check is not needed due to the list_for_each*
macros handling that case just fine.

I haven't looked at the details of the new xfs_ail_splice code yet, so
more updates later.

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Christoph Hellwig]

> +	do {
> +		/* no placeholder, so get our insert location */
> +		if (!lip)
> +			lip = __xfs_trans_ail_cursor_last(ailp, cur,
> +								lsn, false);
> +
> +		if (!lip) {
> +			/*
> +			 * The list is empty, so just splice and return.  Our
> +			 * cursor is already guaranteed to be up to date, so we
> +			 * don't need to touch it here.
> +			 */
> +			list_splice(list, &ailp->xa_ail);
> +			return;
> +		}
> +
> +		/* The placeholder was invalidated, need to get a new cursor */
> +		if ((__psint_t)lip & 1)
> +			lip = NULL;
> +
> +	} while (lip == NULL);

Why do we even need a loop here?  Given that we're under xa_lock
no new cursor will get invalidated.  Isn't the simple code below
equivalent?

	/* no valid placeholder, get us a useful one */
	if (!lip || (__psint_t)lip & 1))
		lip = __xfs_trans_ail_cursor_last(ailp, cur, lsn, false);

	if (!lip) {
		/*
		 * The list is empty, so just splice and return.  Our
		 * cursor is already guaranteed to be up to date, so we
		 * don't need to touch it here.
		 */
		list_splice(list, &ailp->xa_ail);
		return;
	}

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Christoph Hellwig]

FYI: the following patch implementing my suggested cleanups survived a
few rounds of xfsqa:


Index: xfs/fs/xfs/xfs_trans_ail.c
===================================================================
--- xfs.orig/fs/xfs/xfs_trans_ail.c	2011-07-04 16:04:08.932174424 +0200
+++ xfs/fs/xfs/xfs_trans_ail.c	2011-07-04 16:12:51.402677292 +0200
@@ -267,26 +267,14 @@ out:
 static struct xfs_log_item *
 __xfs_trans_ail_cursor_last(
 	struct xfs_ail		*ailp,
-	struct xfs_ail_cursor	*cur,
-	xfs_lsn_t		lsn,
-	bool			do_init)
+	xfs_lsn_t		lsn)
 {
-	xfs_log_item_t		*lip = NULL;
-
-	if (do_init)
-		xfs_trans_ail_cursor_init(ailp, cur);
+	struct xfs_log_item	*lip;
 
-	if (list_empty(&ailp->xa_ail)) 
-		goto out;
-
-	list_for_each_entry_reverse(lip, &ailp->xa_ail, li_ail) {
+	list_for_each_entry_reverse(lip, &ailp->xa_ail, li_ail)
 		if (XFS_LSN_CMP(lip->li_lsn, lsn) <= 0)
-			break;
-	}
-out:
-	if (cur)
-		cur->item = lip;
-	return lip;
+			return lip;
+	return NULL;
 }
 
 /*
@@ -300,7 +288,9 @@ xfs_trans_ail_cursor_last(
 	struct xfs_ail_cursor	*cur,
 	xfs_lsn_t		lsn)
 {
-	return __xfs_trans_ail_cursor_last(ailp, cur, lsn, true);
+	xfs_trans_ail_cursor_init(ailp, cur);
+	cur->item = __xfs_trans_ail_cursor_last(ailp, lsn);
+	return cur->item;
 }
 
 /*
@@ -319,27 +309,22 @@ xfs_ail_splice(
 	struct xfs_log_item	*lip = cur ? cur->item : NULL;
 	struct xfs_log_item	*next_lip;
 
-	do {
-		/* no placeholder, so get our insert location */
-		if (!lip)
-			lip = __xfs_trans_ail_cursor_last(ailp, cur,
-								lsn, false);
-
+	/*
+	 * Get a new cursor if we do not have a placeholder or an
+	 * invalidated one.
+	 */
+	if (!lip || (__psint_t)lip & 1) {
+		lip = __xfs_trans_ail_cursor_last(ailp, lsn);
 		if (!lip) {
 			/*
-			 * The list is empty, so just splice and return.  Our
-			 * cursor is already guaranteed to be up to date, so we
-			 * don't need to touch it here.
+			 * The list is empty, so just splice and return.
 			 */
+			if (cur)
+				cur->item = NULL;
 			list_splice(list, &ailp->xa_ail);
 			return;
 		}
-
-		/* The placeholder was invalidated, need to get a new cursor */
-		if ((__psint_t)lip & 1)
-			lip = NULL;
-
-	} while (lip == NULL);
+	}
 
 	/*
 	 * Our cursor points to the item we want to insert _after_, so we have

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Alex Elder]

On Mon, 2011-07-04 at 17:20 -0400, Christoph Hellwig wrote:
> FYI: the following patch implementing my suggested cleanups survived a
> few rounds of xfsqa:

It also eliminates the concern I had about using the value
of "lip" after falling off the front of the list with a
list_for_each_entry_reverse().  A null pointer signifies
no entry has a lower lsn than the one provided, and
that covers both the "empty list" and the "lower than
all other lsn's in the list" cases.

I think you should base your solution on Christoph's
approach, Dave.

					-Alex


_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Dave Chinner]

On Thu, Jul 07, 2011 at 04:26:16PM -0500, Alex Elder wrote:
> On Mon, 2011-07-04 at 17:20 -0400, Christoph Hellwig wrote:
> > FYI: the following patch implementing my suggested cleanups survived a
> > few rounds of xfsqa:
> 
> It also eliminates the concern I had about using the value
> of "lip" after falling off the front of the list with a
> list_for_each_entry_reverse().  A null pointer signifies
> no entry has a lower lsn than the one provided, and
> that covers both the "empty list" and the "lower than
> all other lsn's in the list" cases.
> 
> I think you should base your solution on Christoph's
> approach, Dave.

Already been updated to use hch's code ;)

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Alex Elder]

On Mon, 2011-07-04 at 15:27 +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> Delayed logging can insert tens of thousands of log items into the
> AIL at the same LSN. When the committing of log commit records
> occur, we can get insertions occurring at an LSN that is not at the
> end of the AIL. If there are thousands of items in the AIL on the
> tail LSN, each insertion has to walk the AIL to find the correct
> place to insert the new item into the AIL. This can consume large
> amounts of CPU time and block other operations from occurring while
> the traversals are in progress.
> 
> To avoid this repeated walk, use a AIL cursor to record
> where we should be inserting the new items into the AIL without
> having to repeat the walk. The cursor infrastructure already
> provides this functionality for push walks, so is a simple extension
> of existing code. While this will not avoid the initial walk, it
> will avoid repeating it tens of thousands of times during a single
> checkpoint commit.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>

I agree with Christoph's comments about both eliminating
the do_init parameter in __xfs_trans_ail_cursor_last(),
and that there's no need for a loop in xfs_ail_splice().

I have some thoughts below, one of which points out what may
be a bug involving the use of list_for_each_entry_reverse().
Someone else should confirm it though.

> ---
>  fs/xfs/xfs_trans.c      |   27 +++++++++--
>  fs/xfs/xfs_trans_ail.c  |  122 +++++++++++++++++++++++++++++++++++++++--------
>  fs/xfs/xfs_trans_priv.h |   10 +++-
>  3 files changed, 131 insertions(+), 28 deletions(-)
> 

. . .

> diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
> index 5fc2380..272e7fa 100644
> --- a/fs/xfs/xfs_trans_ail.c
> +++ b/fs/xfs/xfs_trans_ail.c

. . .

> @@ -300,31 +300,110 @@ out:
>  }
>  
>  /*
> - * splice the log item list into the AIL at the given LSN.
> + * Initialise the cursor to the last item in the AIL with the given @lsn.

I think you should capture here that the cursor points to
the last entry with an lsn lower than the given one if
none with the given lsn is present in the list already.

> + * This searches the list from highest LSN to lowest.
>   */
> -static void
> -xfs_ail_splice(
> -	struct xfs_ail  *ailp,
> -	struct list_head *list,
> -	xfs_lsn_t       lsn)
> +static struct xfs_log_item *
> +__xfs_trans_ail_cursor_last(
> +	struct xfs_ail		*ailp,
> +	struct xfs_ail_cursor	*cur,
> +	xfs_lsn_t		lsn,
> +	bool			do_init)

. . .

> -	list_for_each_entry_reverse(next_lip, &ailp->xa_ail, li_ail) {
> -		if (XFS_LSN_CMP(next_lip->li_lsn, lsn) <= 0)
> +	list_for_each_entry_reverse(lip, &ailp->xa_ail, li_ail) {
> +		if (XFS_LSN_CMP(lip->li_lsn, lsn) <= 0)
>  			break;
>  	}
> +out:
> +	if (cur)
> +		cur->item = lip;

I don't think it's safe to use the value of "lip" here.
I think if list_for_each_entry_reverse() terminates
because it has visited every entry on the list then
its "pos" parameter (lip in this case) does not have
a meaningful value.  The problem case is if the lsn
you are inserting is lower than any already in the AIL.
Can you guarantee that cannot happen?

If not, there doesn't seem to be a way to indicate
to the caller that the new entry belongs at the
beginning of the AIL--"after nothing."  A null
pointer means the list is empty, and maybe that
is in some sense no different from this case, I
don't know.

I haven't looked closely at the new xfs_ail_splice()
yet (below) so maybe this all "just works" but if
it does it may be fragile.

> +	return lip;
> +}
>  
> -	ASSERT(&next_lip->li_ail == &ailp->xa_ail ||
> -	       XFS_LSN_CMP(next_lip->li_lsn, lsn) <= 0);
> +/*

. . .

> +/*
> + * splice the log item list into the AIL at the given LSN. We splice to the
> + * tail of the given LSN to maintain insert order for push traversals. The
> + * cursor is optional, allowing repeated updates to the same LSN to avoid
> + * repeated traversals.

     ...  If supplied, the cursor must have been previously initialized.

> + */
> +static void
> +xfs_ail_splice(
> +	struct xfs_ail		*ailp,
> +	struct xfs_ail_cursor	*cur,
> +	struct list_head	*list,
> +	xfs_lsn_t		lsn)
> +{
> +	struct xfs_log_item	*lip = cur ? cur->item : NULL;
> +	struct xfs_log_item	*next_lip;
> +
> +	do {
> +		/* no placeholder, so get our insert location */
> +		if (!lip)
> +			lip = __xfs_trans_ail_cursor_last(ailp, cur,
> +								lsn, false);
> +
> +		if (!lip) {
> +			/*
> +			 * The list is empty, so just splice and return.  Our
> +			 * cursor is already guaranteed to be up to date, so we
> +			 * don't need to touch it here.
> +			 */
> +			list_splice(list, &ailp->xa_ail);
> +			return;
> +		}
> +
> +		/* The placeholder was invalidated, need to get a new cursor */
> +		if ((__psint_t)lip & 1)
> +			lip = NULL;
> +
> +	} while (lip == NULL);
> +
> +	/*
> +	 * Our cursor points to the item we want to insert _after_, so we have
> +	 * to update the cursor to point to the end of the list we are splicing
> +	 * in so that it points to the correct location for the next splice.
> +	 * i.e. before the splice
> +	 *
> +	 *  lsn -> lsn -> lsn + x -> lsn + x ...
> +	 *          ^
> +	 *          | cursor points here
> +	 *
> +	 * After the splice we have:
> +	 *
> +	 *  lsn -> lsn -> lsn -> lsn -> .... -> lsn -> lsn + x -> lsn + x ...
> +	 *          ^                            ^
> +	 *          | cursor points here         | needs to move here
> +	 *
> +	 * So we set the cursor to the last item in the list to be spliced
> +	 * before we execute the splice, resulting in the cursor pointing to
> +	 * the correct item after the splice occurs.
> +	 */
> +	if (cur) {
> +		next_lip = list_entry(list->prev, struct xfs_log_item, li_ail);
> +		cur->item = next_lip;
> +	}
> +	list_splice_init(list, &lip->li_ail);

I think simply list_splice() is sufficient here (and it was
before as well).  Either that or the empty list case above
should also call list_splice_init().

>  }
>  
>  /*

. . .

> @@ -111,10 +112,13 @@ xfs_lsn_t		xfs_ail_min_lsn(struct xfs_ail *ailp);
>  void			xfs_trans_unlocked_item(struct xfs_ail *,
>  					xfs_log_item_t *);
>  
> -struct xfs_log_item	*xfs_trans_ail_cursor_first(struct xfs_ail *ailp,
> +struct xfs_log_item *	xfs_trans_ail_cursor_first(struct xfs_ail *ailp,
>  					struct xfs_ail_cursor *cur,
>  					xfs_lsn_t lsn);
> -struct xfs_log_item	*xfs_trans_ail_cursor_next(struct xfs_ail *ailp,
> +struct xfs_log_item *	xfs_trans_ail_cursor_last(struct xfs_ail *ailp,
> +					struct xfs_ail_cursor *cur,
> +					xfs_lsn_t lsn);
> +struct xfs_log_item *	xfs_trans_ail_cursor_next(struct xfs_ail *ailp,
>  					struct xfs_ail_cursor *cur);
>  void			xfs_trans_ail_cursor_done(struct xfs_ail *ailp,
>  					struct xfs_ail_cursor *cur);

Curious about the formatting convention here.

I actually toyed with doing exactly this years ago in
my own code, but I seemed to be bucking convention too
much so I went back to the K&R way (I think that's
putting the star adjacent to the function/variable
name comes from).




_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH 3/5] xfs: remove confusing ail cursor wrapper

[Dave Chinner]

From: Dave Chinner <dchinner@redhat.com>

xfs_trans_ail_cursor_set() doesn't set the cursor to the current log
item, it sets it to the next item. There is already a function for
doing this - xfs_trans_ail_cursor_next() - and the _set function is
simply a two line wrapper.  Remove it and open code the setting of
the cursor in the two locations that call it to remove the
confusion.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
---
 fs/xfs/xfs_trans_ail.c |   38 ++++++++++++--------------------------
 1 files changed, 12 insertions(+), 26 deletions(-)

diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
index 272e7fa..de7a52a 100644
--- a/fs/xfs/xfs_trans_ail.c
+++ b/fs/xfs/xfs_trans_ail.c
@@ -189,20 +189,6 @@ xfs_trans_ail_cursor_init(
 }
 
 /*
- * Set the cursor to the next item, because when we look
- * up the cursor the current item may have been freed.
- */
-STATIC void
-xfs_trans_ail_cursor_set(
-	struct xfs_ail		*ailp,
-	struct xfs_ail_cursor	*cur,
-	struct xfs_log_item	*lip)
-{
-	if (lip)
-		cur->item = xfs_ail_next(ailp, lip);
-}
-
-/*
  * Get the next item in the traversal and advance the cursor.
  * If the cursor was invalidated (inidicated by a lip of 1),
  * restart the traversal.
@@ -216,7 +202,8 @@ xfs_trans_ail_cursor_next(
 
 	if ((__psint_t)lip & 1)
 		lip = xfs_ail_min(ailp);
-	xfs_trans_ail_cursor_set(ailp, cur, lip);
+	if (lip)
+		cur->item = xfs_ail_next(ailp, lip);
 	return lip;
 }
 
@@ -272,9 +259,10 @@ xfs_trans_ail_cursor_clear(
 }
 
 /*
- * Initialise the cursor to the first item in the AIL with the given @lsn.
- * This searches the list from lowest LSN to highest. Pass a @lsn of zero
- * to initialise the cursor to the first item in the AIL.
+ * Find the first item in the AIL with the given @lsn by searching in ascending
+ * LSN order and initialise the cursor to point to the next item for a
+ * ascending traversal.  Pass a @lsn of zero to initialise the cursor to the
+ * first item in the AIL. Returns NULL if the list is empty.
  */
 xfs_log_item_t *
 xfs_trans_ail_cursor_first(
@@ -295,14 +283,11 @@ xfs_trans_ail_cursor_first(
 	}
 	lip = NULL;
 out:
-	xfs_trans_ail_cursor_set(ailp, cur, lip);
+	if (lip)
+		cur->item = xfs_ail_next(ailp, lip);
 	return lip;
 }
 
-/*
- * Initialise the cursor to the last item in the AIL with the given @lsn.
- * This searches the list from highest LSN to lowest.
- */
 static struct xfs_log_item *
 __xfs_trans_ail_cursor_last(
 	struct xfs_ail		*ailp,
@@ -329,8 +314,9 @@ out:
 }
 
 /*
- * Initialise the cursor to the last item in the AIL with the given @lsn.
- * This searches the list from highest LSN to lowest.
+ * Find the last item in the AIL with the given @lsn by searching in descending
+ * LSN order and initialise the cursor to point to that item.  Returns NULL is
+ * the list is empty.
  */
 struct xfs_log_item *
 xfs_trans_ail_cursor_last(
@@ -342,7 +328,7 @@ xfs_trans_ail_cursor_last(
 }
 
 /*
- * splice the log item list into the AIL at the given LSN. We splice to the
+ * Splice the log item list into the AIL at the given LSN. We splice to the
  * tail of the given LSN to maintain insert order for push traversals. The
  * cursor is optional, allowing repeated updates to the same LSN to avoid
  * repeated traversals.
-- 
1.7.5.1

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 3/5] xfs: remove confusing ail cursor wrapper

[Christoph Hellwig]

On Mon, Jul 04, 2011 at 03:27:38PM +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> xfs_trans_ail_cursor_set() doesn't set the cursor to the current log
> item, it sets it to the next item. There is already a function for
> doing this - xfs_trans_ail_cursor_next() - and the _set function is
> simply a two line wrapper.  Remove it and open code the setting of
> the cursor in the two locations that call it to remove the
> confusion.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>
> ---
>  fs/xfs/xfs_trans_ail.c |   38 ++++++++++++--------------------------
>  1 files changed, 12 insertions(+), 26 deletions(-)

> @@ -295,14 +283,11 @@ xfs_trans_ail_cursor_first(
>  	}
>  	lip = NULL;
>  out:
> -	xfs_trans_ail_cursor_set(ailp, cur, lip);
> +	if (lip)
> +		cur->item = xfs_ail_next(ailp, lip);
>  	return lip;

The lip = NULL above could nbe turned into a direct return NULL;

Otherwise looks good,


Reviewed-by: Christoph Hellwig <hch@lst.de>

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 3/5] xfs: remove confusing ail cursor wrapper

[Alex Elder]

On Mon, 2011-07-04 at 15:27 +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> xfs_trans_ail_cursor_set() doesn't set the cursor to the current log
> item, it sets it to the next item. There is already a function for
> doing this - xfs_trans_ail_cursor_next() - and the _set function is
> simply a two line wrapper.  Remove it and open code the setting of
> the cursor in the two locations that call it to remove the
> confusion.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>

Good idea.  I also appreciate the comment improvement;
the "returns NULL" is something I wanted to suggest
while looking at the previous patch, but that section
of the file wasn't in that patch.

Reviewed-by: Alex Elder <aelder@sgi.com>


_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH 4/5] xfs: convert AIL cursors to use struct list_head

[Dave Chinner]

From: Dave Chinner <dchinner@redhat.com>

The list of active AIL cursors uses a roll-your-own linked list with
special casing for the AIL push cursor. Simplify this code by
replacing the list with standard struct list_head lists, and use a
separate list_head to track the active cursors so that the code can
just treat the AIL push cursor (which is still embedded into the
struct xfs_ail) as a generic cursor.

Further, fix the duplicate push cursor initialisation that the
special case handling was hiding, and clean up all the comments
around the active cursor list handling.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
---
 fs/xfs/xfs_trans_ail.c  |   68 +++++++++++++++-------------------------------
 fs/xfs/xfs_trans_priv.h |    5 ++-
 2 files changed, 25 insertions(+), 48 deletions(-)

diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
index de7a52a..3b5b5e4 100644
--- a/fs/xfs/xfs_trans_ail.c
+++ b/fs/xfs/xfs_trans_ail.c
@@ -165,15 +165,11 @@ xfs_ail_max_lsn(
 /*
  * AIL traversal cursor initialisation.
  *
- * The cursor keeps track of where our current traversal is up
- * to by tracking the next ƣtem in the list for us. However, for
- * this to be safe, removing an object from the AIL needs to invalidate
- * any cursor that points to it. hence the traversal cursor needs to
- * be linked to the struct xfs_ail so that deletion can search all the
- * active cursors for invalidation.
- *
- * We don't link the push cursor because it is embedded in the struct
- * xfs_ail and hence easily findable.
+ * The cursor keeps track of where our current traversal is up to by tracking
+ * the next ƣtem in the list for us. However, for this to be safe, removing an
+ * object from the AIL needs to invalidate any cursor that points to it. hence
+ * the traversal cursor needs to be linked to the struct xfs_ail so that
+ * deletion can search all the active cursors for invalidation.
  */
 STATIC void
 xfs_trans_ail_cursor_init(
@@ -181,17 +177,13 @@ xfs_trans_ail_cursor_init(
 	struct xfs_ail_cursor	*cur)
 {
 	cur->item = NULL;
-	if (cur == &ailp->xa_cursors)
-		return;
-
-	cur->next = ailp->xa_cursors.next;
-	ailp->xa_cursors.next = cur;
+	INIT_LIST_HEAD(&cur->list);
+	list_add_tail(&cur->list, &ailp->xa_cursors);
 }
 
 /*
- * Get the next item in the traversal and advance the cursor.
- * If the cursor was invalidated (inidicated by a lip of 1),
- * restart the traversal.
+ * Get the next item in the traversal and advance the cursor.  If the cursor
+ * was invalidated (inidicated by a lip of 1), restart the traversal.
  */
 struct xfs_log_item *
 xfs_trans_ail_cursor_next(
@@ -208,39 +200,24 @@ xfs_trans_ail_cursor_next(
 }
 
 /*
- * Now that the traversal is complete, we need to remove the cursor
- * from the list of traversing cursors. Avoid removing the embedded
- * push cursor, but use the fact it is always present to make the
- * list deletion simple.
+ * When the traversal is complete, we need to remove the cursor from the list
+ * of traversing cursors.
  */
 void
 xfs_trans_ail_cursor_done(
 	struct xfs_ail		*ailp,
-	struct xfs_ail_cursor	*done)
+	struct xfs_ail_cursor	*cur)
 {
-	struct xfs_ail_cursor	*prev = NULL;
-	struct xfs_ail_cursor	*cur;
-
-	done->item = NULL;
-	if (done == &ailp->xa_cursors)
-		return;
-	prev = &ailp->xa_cursors;
-	for (cur = prev->next; cur; prev = cur, cur = prev->next) {
-		if (cur == done) {
-			prev->next = cur->next;
-			break;
-		}
-	}
-	ASSERT(cur);
+	cur->item = NULL;
+	list_del_init(&cur->list);
 }
 
 /*
- * Invalidate any cursor that is pointing to this item. This is
- * called when an item is removed from the AIL. Any cursor pointing
- * to this object is now invalid and the traversal needs to be
- * terminated so it doesn't reference a freed object. We set the
- * cursor item to a value of 1 so we can distinguish between an
- * invalidation and the end of the list when getting the next item
+ * Invalidate any cursor that is pointing to this item. This is called when an
+ * item is removed from the AIL. Any cursor pointing to this object is now
+ * invalid and the traversal needs to be terminated so it doesn't reference a
+ * freed object. We set the cursor item to a value of 1 so we can distinguish
+ * between an invalidation and the end of the list when getting the next item
  * from the cursor.
  */
 STATIC void
@@ -250,8 +227,7 @@ xfs_trans_ail_cursor_clear(
 {
 	struct xfs_ail_cursor	*cur;
 
-	/* need to search all cursors */
-	for (cur = &ailp->xa_cursors; cur; cur = cur->next) {
+	list_for_each_entry(cur, &ailp->xa_cursors, list) {
 		if (cur->item == lip)
 			cur->item = (struct xfs_log_item *)
 					((__psint_t)cur->item | 1);
@@ -416,7 +392,7 @@ xfs_ail_worker(
 	struct xfs_ail		*ailp = container_of(to_delayed_work(work),
 					struct xfs_ail, xa_work);
 	xfs_mount_t		*mp = ailp->xa_mount;
-	struct xfs_ail_cursor	*cur = &ailp->xa_cursors;
+	struct xfs_ail_cursor	*cur = &ailp->xa_push_cursor;
 	xfs_log_item_t		*lip;
 	xfs_lsn_t		lsn;
 	xfs_lsn_t		target;
@@ -428,7 +404,6 @@ xfs_ail_worker(
 
 	spin_lock(&ailp->xa_lock);
 	target = ailp->xa_target;
-	xfs_trans_ail_cursor_init(ailp, cur);
 	lip = xfs_trans_ail_cursor_first(ailp, cur, ailp->xa_last_pushed_lsn);
 	if (!lip || XFS_FORCED_SHUTDOWN(mp)) {
 		/*
@@ -859,6 +834,7 @@ xfs_trans_ail_init(
 
 	ailp->xa_mount = mp;
 	INIT_LIST_HEAD(&ailp->xa_ail);
+	INIT_LIST_HEAD(&ailp->xa_cursors);
 	spin_lock_init(&ailp->xa_lock);
 	INIT_DELAYED_WORK(&ailp->xa_work, xfs_ail_worker);
 	mp->m_ail = ailp;
diff --git a/fs/xfs/xfs_trans_priv.h b/fs/xfs/xfs_trans_priv.h
index c0cb408..a394e2c 100644
--- a/fs/xfs/xfs_trans_priv.h
+++ b/fs/xfs/xfs_trans_priv.h
@@ -53,7 +53,7 @@ void	xfs_trans_committed_bulk(struct xfs_ail *ailp, struct xfs_log_vec *lv,
  * of the list to trigger traversal restarts.
  */
 struct xfs_ail_cursor {
-	struct xfs_ail_cursor	*next;
+	struct list_head	list;
 	struct xfs_log_item	*item;
 };
 
@@ -66,7 +66,8 @@ struct xfs_ail {
 	struct xfs_mount	*xa_mount;
 	struct list_head	xa_ail;
 	xfs_lsn_t		xa_target;
-	struct xfs_ail_cursor	xa_cursors;
+	struct list_head	xa_cursors;
+	struct xfs_ail_cursor	xa_push_cursor;
 	spinlock_t		xa_lock;
 	struct delayed_work	xa_work;
 	xfs_lsn_t		xa_last_pushed_lsn;
-- 
1.7.5.1

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 4/5] xfs: convert AIL cursors to use struct list_head

[Christoph Hellwig]

On Mon, Jul 04, 2011 at 03:27:39PM +1000, Dave Chinner wrote:
>  /*
>   * AIL traversal cursor initialisation.
>   *
> + * The cursor keeps track of where our current traversal is up to by tracking
> + * the next ??tem in the list for us. However, for this to be safe, removing an
               ^^
Non-ASCSI character.

> + * object from the AIL needs to invalidate any cursor that points to it. hence
> + * the traversal cursor needs to be linked to the struct xfs_ail so that
> + * deletion can search all the active cursors for invalidation.
>   */
>  STATIC void
>  xfs_trans_ail_cursor_init(
> @@ -181,17 +177,13 @@ xfs_trans_ail_cursor_init(
>  	struct xfs_ail_cursor	*cur)
>  {
>  	cur->item = NULL;
> -	if (cur == &ailp->xa_cursors)
> -		return;
> -
> -	cur->next = ailp->xa_cursors.next;
> -	ailp->xa_cursors.next = cur;
> +	INIT_LIST_HEAD(&cur->list);
> +	list_add_tail(&cur->list, &ailp->xa_cursors);
>  }

There is no need to initialize a list_head before adding it to a list.

Otherwise looks good,

Reviewed-by: Christoph Hellwig <hch@lst.de>

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 4/5] xfs: convert AIL cursors to use struct list_head

[Alex Elder]

On Mon, 2011-07-04 at 15:27 +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> The list of active AIL cursors uses a roll-your-own linked list with
> special casing for the AIL push cursor. Simplify this code by
> replacing the list with standard struct list_head lists, and use a
> separate list_head to track the active cursors so that the code can
> just treat the AIL push cursor (which is still embedded into the
> struct xfs_ail) as a generic cursor.
> 
> Further, fix the duplicate push cursor initialisation that the
> special case handling was hiding, and clean up all the comments
> around the active cursor list handling.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>

I suggest a few comment changes below.  I also have a
question about why the push cursor isn't treated
like any other cursors.  I added a few bits of
commentary as well--you addressed a few things
I had been thinking about earlier.

I guess I'm interested in your response before
signing off.

					-Alex

> ---
>  fs/xfs/xfs_trans_ail.c  |   68 +++++++++++++++-------------------------------
>  fs/xfs/xfs_trans_priv.h |    5 ++-
>  2 files changed, 25 insertions(+), 48 deletions(-)
> 
> diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
> index de7a52a..3b5b5e4 100644
> --- a/fs/xfs/xfs_trans_ail.c
> +++ b/fs/xfs/xfs_trans_ail.c
> @@ -165,15 +165,11 @@ xfs_ail_max_lsn(
>  /*
>   * AIL traversal cursor initialisation.
>   *
> - * The cursor keeps track of where our current traversal is up
> - * to by tracking the next ƣtem in the list for us. However, for
> - * this to be safe, removing an object from the AIL needs to invalidate
> - * any cursor that points to it. hence the traversal cursor needs to
> - * be linked to the struct xfs_ail so that deletion can search all the
> - * active cursors for invalidation.
> - *
> - * We don't link the push cursor because it is embedded in the struct
> - * xfs_ail and hence easily findable.
> + * The cursor keeps track of where our current traversal is up to by tracking
> + * the next ƣtem in the list for us. However, for this to be safe, removing an
               ^
What's up with the weird non-ASCII characters in your code?

> + * object from the AIL needs to invalidate any cursor that points to it. hence
> + * the traversal cursor needs to be linked to the struct xfs_ail so that
> + * deletion can search all the active cursors for invalidation.
>   */
>  STATIC void
>  xfs_trans_ail_cursor_init(
> @@ -181,17 +177,13 @@ xfs_trans_ail_cursor_init(
>  	struct xfs_ail_cursor	*cur)
>  {
>  	cur->item = NULL;
> -	if (cur == &ailp->xa_cursors)
> -		return;
> -
> -	cur->next = ailp->xa_cursors.next;
> -	ailp->xa_cursors.next = cur;
> +	INIT_LIST_HEAD(&cur->list);
> +	list_add_tail(&cur->list, &ailp->xa_cursors);

This is good.  I was thinking as I looked at this earlier
that it would be nicer if newer cursors were added
to the end of the list.

>  }
>  
>  /*
> - * Get the next item in the traversal and advance the cursor.
> - * If the cursor was invalidated (inidicated by a lip of 1),
> - * restart the traversal.
> + * Get the next item in the traversal and advance the cursor.  If the cursor
> + * was invalidated (inidicated by a lip of 1), restart the traversal.
                       indicated

Actually, it's indicated by a low-order bit of 1.  Why is it
that you decided to just set the bit rather than overwrite
the item pointer?  Just for the benefit of debugging?  (That
is a good reason...)  If not, I suggest defining an
XFS_ITEM_INVALID constant pointer rather than just using 1.

>   */
>  struct xfs_log_item *
>  xfs_trans_ail_cursor_next(
> @@ -208,39 +200,24 @@ xfs_trans_ail_cursor_next(
>  }
>  
>  /*
> - * Now that the traversal is complete, we need to remove the cursor
> - * from the list of traversing cursors. Avoid removing the embedded
> - * push cursor, but use the fact it is always present to make the
> - * list deletion simple.
> + * When the traversal is complete, we need to remove the cursor from the list
> + * of traversing cursors.
>   */
>  void
>  xfs_trans_ail_cursor_done(
>  	struct xfs_ail		*ailp,
> -	struct xfs_ail_cursor	*done)
> +	struct xfs_ail_cursor	*cur)
>  {
> -	struct xfs_ail_cursor	*prev = NULL;
> -	struct xfs_ail_cursor	*cur;
> -
> -	done->item = NULL;

This eliminates the curious situation where the
end of the list was marked by a null *item* pointer
rather than something having to do with the next
pointer.

> -	if (done == &ailp->xa_cursors)
> -		return;
> -	prev = &ailp->xa_cursors;
> -	for (cur = prev->next; cur; prev = cur, cur = prev->next) {
> -		if (cur == done) {
> -			prev->next = cur->next;
> -			break;

. . .

> - * invalidation and the end of the list when getting the next item
> + * Invalidate any cursor that is pointing to this item. This is called when an
> + * item is removed from the AIL. Any cursor pointing to this object is now
> + * invalid and the traversal needs to be terminated so it doesn't reference a
> + * freed object. We set the cursor item to a value of 1 so we can distinguish

Fix this comment to reflect the use of the low bit rather than just 1.

> + * between an invalidation and the end of the list when getting the next item
>   * from the cursor.
>   */
>  STATIC void

. . .

> nt_t)cur->item | 1);
> @@ -416,7 +392,7 @@ xfs_ail_worker(
>  	struct xfs_ail		*ailp = container_of(to_delayed_work(work),
>  					struct xfs_ail, xa_work);
>  	xfs_mount_t		*mp = ailp->xa_mount;
> -	struct xfs_ail_cursor	*cur = &ailp->xa_cursors;
> +	struct xfs_ail_cursor	*cur = &ailp->xa_push_cursor;

Is the push cursor defined in the ail structure just
so it's easier to find?

>  	xfs_log_item_t		*lip;
>  	xfs_lsn_t		lsn;
>  	xfs_lsn_t		target;
> @@ -428,7 +404,6 @@ xfs_ail_worker(
>  
>  	spin_lock(&ailp->xa_lock);
>  	target = ailp->xa_target;
> -	xfs_trans_ail_cursor_init(ailp, cur);

I don't see why the push cursor should be treated
any differently from any others.  If something gets
invalidated the push cursor needs to be notified
also, doesn't it?

I must be missing something here...

>  	lip = xfs_trans_ail_cursor_first(ailp, cur, ailp->xa_last_pushed_lsn);
>  	if (!lip || XFS_FORCED_SHUTDOWN(mp)) {
>  		/*

. . .

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 4/5] xfs: convert AIL cursors to use struct list_head

[Dave Chinner]

On Thu, Jul 07, 2011 at 04:15:15PM -0500, Alex Elder wrote:
> On Mon, 2011-07-04 at 15:27 +1000, Dave Chinner wrote:
> > From: Dave Chinner <dchinner@redhat.com>
> > 
> > The list of active AIL cursors uses a roll-your-own linked list with
> > special casing for the AIL push cursor. Simplify this code by
> > replacing the list with standard struct list_head lists, and use a
> > separate list_head to track the active cursors so that the code can
> > just treat the AIL push cursor (which is still embedded into the
> > struct xfs_ail) as a generic cursor.
> > 
> > Further, fix the duplicate push cursor initialisation that the
> > special case handling was hiding, and clean up all the comments
> > around the active cursor list handling.
> > 
> > Signed-off-by: Dave Chinner <dchinner@redhat.com>
> 
> I suggest a few comment changes below.  I also have a
> question about why the push cursor isn't treated
> like any other cursors.  I added a few bits of
> commentary as well--you addressed a few things
> I had been thinking about earlier.
> 
> I guess I'm interested in your response before
> signing off.
> 
> 					-Alex
> 
> > ---
> >  fs/xfs/xfs_trans_ail.c  |   68 +++++++++++++++-------------------------------
> >  fs/xfs/xfs_trans_priv.h |    5 ++-
> >  2 files changed, 25 insertions(+), 48 deletions(-)
> > 
> > diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
> > index de7a52a..3b5b5e4 100644
> > --- a/fs/xfs/xfs_trans_ail.c
> > +++ b/fs/xfs/xfs_trans_ail.c
> > @@ -165,15 +165,11 @@ xfs_ail_max_lsn(
> >  /*
> >   * AIL traversal cursor initialisation.
> >   *
> > - * The cursor keeps track of where our current traversal is up
> > - * to by tracking the next ƣtem in the list for us. However, for
> > - * this to be safe, removing an object from the AIL needs to invalidate
> > - * any cursor that points to it. hence the traversal cursor needs to
> > - * be linked to the struct xfs_ail so that deletion can search all the
> > - * active cursors for invalidation.
> > - *
> > - * We don't link the push cursor because it is embedded in the struct
> > - * xfs_ail and hence easily findable.
> > + * The cursor keeps track of where our current traversal is up to by tracking
> > + * the next ƣtem in the list for us. However, for this to be safe, removing an
>                ^
> What's up with the weird non-ASCII characters in your code?
> 
> > + * object from the AIL needs to invalidate any cursor that points to it. hence
> > + * the traversal cursor needs to be linked to the struct xfs_ail so that
> > + * deletion can search all the active cursors for invalidation.
> >   */
> >  STATIC void
> >  xfs_trans_ail_cursor_init(
> > @@ -181,17 +177,13 @@ xfs_trans_ail_cursor_init(
> >  	struct xfs_ail_cursor	*cur)
> >  {
> >  	cur->item = NULL;
> > -	if (cur == &ailp->xa_cursors)
> > -		return;
> > -
> > -	cur->next = ailp->xa_cursors.next;
> > -	ailp->xa_cursors.next = cur;
> > +	INIT_LIST_HEAD(&cur->list);
> > +	list_add_tail(&cur->list, &ailp->xa_cursors);
> 
> This is good.  I was thinking as I looked at this earlier
> that it would be nicer if newer cursors were added
> to the end of the list.
> 
> >  }
> >  
> >  /*
> > - * Get the next item in the traversal and advance the cursor.
> > - * If the cursor was invalidated (inidicated by a lip of 1),
> > - * restart the traversal.
> > + * Get the next item in the traversal and advance the cursor.  If the cursor
> > + * was invalidated (inidicated by a lip of 1), restart the traversal.
>                        indicated
> 
> Actually, it's indicated by a low-order bit of 1.

True.

> Why is it
> that you decided to just set the bit rather than overwrite
> the item pointer?  Just for the benefit of debugging?  (That
> is a good reason...)  If not, I suggest defining an
> XFS_ITEM_INVALID constant pointer rather than just using 1.

Right, it was mainly for debugging. i.e. if we trip over the item
we'll get a panic but we'll also be left with a corpse that has
intact pointers which might aid finding the cause of the problem.


> > - * invalidation and the end of the list when getting the next item
> > + * Invalidate any cursor that is pointing to this item. This is called when an
> > + * item is removed from the AIL. Any cursor pointing to this object is now
> > + * invalid and the traversal needs to be terminated so it doesn't reference a
> > + * freed object. We set the cursor item to a value of 1 so we can distinguish
> 
> Fix this comment to reflect the use of the low bit rather than just 1.

Will do.

> > + * between an invalidation and the end of the list when getting the next item
> >   * from the cursor.
> >   */
> >  STATIC void
> 
> . . .
> 
> > nt_t)cur->item | 1);
> > @@ -416,7 +392,7 @@ xfs_ail_worker(
> >  	struct xfs_ail		*ailp = container_of(to_delayed_work(work),
> >  					struct xfs_ail, xa_work);
> >  	xfs_mount_t		*mp = ailp->xa_mount;
> > -	struct xfs_ail_cursor	*cur = &ailp->xa_cursors;
> > +	struct xfs_ail_cursor	*cur = &ailp->xa_push_cursor;
> 
> Is the push cursor defined in the ail structure just
> so it's easier to find?

The reason is that 99.9% of traversals are from the push
code, so 99.9% of cursor lookups would be against that cursor.
Embedding it like this avoided the need to add it to or remove it
from a list, and meant that it would also always be cache hot when
the ail structure was accessed.

Realistically, that was probably a case of over-optimisation.

> 
> >  	xfs_log_item_t		*lip;
> >  	xfs_lsn_t		lsn;
> >  	xfs_lsn_t		target;
> > @@ -428,7 +404,6 @@ xfs_ail_worker(
> >  
> >  	spin_lock(&ailp->xa_lock);
> >  	target = ailp->xa_target;
> > -	xfs_trans_ail_cursor_init(ailp, cur);
> 
> I don't see why the push cursor should be treated
> any differently from any others.  If something gets
> invalidated the push cursor needs to be notified
> also, doesn't it?
> 
> I must be missing something here...

No, you are right. Now that the list is generic, there is no reason
to keep the cursor in the AIL structure - each push goes back to the
start of the AIL to begin again, so the only reason for keeping it
in the AIL structure would be if it was cached across multiple push
traversals. I don't think we gain anything by doing that, so we can
just treat it like all other stack based cursors.

I'll update the patch appropriately.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH 5/5] xfs: add size update tracepoint to IO completion

[Dave Chinner]

From: Dave Chinner <dchinner@redhat.com>

For improving insight into IO completion behaviour.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
---
 fs/xfs/linux-2.6/xfs_aops.c  |    1 +
 fs/xfs/linux-2.6/xfs_trace.h |   12 ++++++++----
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/fs/xfs/linux-2.6/xfs_aops.c b/fs/xfs/linux-2.6/xfs_aops.c
index 79ce38b..211abe7 100644
--- a/fs/xfs/linux-2.6/xfs_aops.c
+++ b/fs/xfs/linux-2.6/xfs_aops.c
@@ -181,6 +181,7 @@ xfs_setfilesize(
 
 	isize = xfs_ioend_new_eof(ioend);
 	if (isize) {
+		trace_xfs_setfilesize(ip, ioend->io_offset, ioend->io_size);
 		ip->i_d.di_size = isize;
 		xfs_mark_inode_dirty(ip);
 	}
diff --git a/fs/xfs/linux-2.6/xfs_trace.h b/fs/xfs/linux-2.6/xfs_trace.h
index d48b7a5..97dad27 100644
--- a/fs/xfs/linux-2.6/xfs_trace.h
+++ b/fs/xfs/linux-2.6/xfs_trace.h
@@ -998,7 +998,8 @@ DECLARE_EVENT_CLASS(xfs_simple_io_class,
 	TP_STRUCT__entry(
 		__field(dev_t, dev)
 		__field(xfs_ino_t, ino)
-		__field(loff_t, size)
+		__field(loff_t, isize)
+		__field(loff_t, disize)
 		__field(loff_t, new_size)
 		__field(loff_t, offset)
 		__field(size_t, count)
@@ -1006,16 +1007,18 @@ DECLARE_EVENT_CLASS(xfs_simple_io_class,
 	TP_fast_assign(
 		__entry->dev = VFS_I(ip)->i_sb->s_dev;
 		__entry->ino = ip->i_ino;
-		__entry->size = ip->i_d.di_size;
+		__entry->isize = ip->i_size;
+		__entry->disize = ip->i_d.di_size;
 		__entry->new_size = ip->i_new_size;
 		__entry->offset = offset;
 		__entry->count = count;
 	),
-	TP_printk("dev %d:%d ino 0x%llx size 0x%llx new_size 0x%llx "
+	TP_printk("dev %d:%d ino 0x%llx isize 0x%llx disize 0x%llx new_size 0x%llx "
 		  "offset 0x%llx count %zd",
 		  MAJOR(__entry->dev), MINOR(__entry->dev),
 		  __entry->ino,
-		  __entry->size,
+		  __entry->isize,
+		  __entry->disize,
 		  __entry->new_size,
 		  __entry->offset,
 		  __entry->count)
@@ -1028,6 +1031,7 @@ DEFINE_EVENT(xfs_simple_io_class, name,	\
 DEFINE_SIMPLE_IO_EVENT(xfs_delalloc_enospc);
 DEFINE_SIMPLE_IO_EVENT(xfs_unwritten_convert);
 DEFINE_SIMPLE_IO_EVENT(xfs_get_blocks_notfound);
+DEFINE_SIMPLE_IO_EVENT(xfs_setfilesize);
 
 
 TRACE_EVENT(xfs_itruncate_start,
-- 
1.7.5.1

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 5/5] xfs: add size update tracepoint to IO completion

[Christoph Hellwig]

On Mon, Jul 04, 2011 at 03:27:40PM +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> For improving insight into IO completion behaviour.

Looks fine,

Reviewed-by: Christoph Hellwig <hch@lst.de>

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 5/5] xfs: add size update tracepoint to IO completion

[Alex Elder]

On Mon, 2011-07-04 at 15:27 +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> For improving insight into IO completion behaviour.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>

Looks good.

Reviewed-by: Alex Elder <aelder@sgi.com>


_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 0/5] xfs: fix AIL bulk insert issues and cleanups

[Christoph Hellwig]

On Mon, Jul 04, 2011 at 03:27:35PM +1000, Dave Chinner wrote:
> The first two patches fix the recently reported rm -rf performance
> and interactivity problems when using delay??d logging. These should
> probably be considered for 3.0-rc5.

I think it's a bit late for patch 2.  Patch 1 is triviall, and helps
with a regression introduced in 2.6.39 by switching to the delaylog
mode, but patch 2 is a bit too large for this in the merge window
unless absolutely nessecary. 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH 0/5] xfs: fix AIL bulk insert issues and cleanups

[Dave Chinner]

On Mon, Jul 04, 2011 at 04:13:12AM -0400, Christoph Hellwig wrote:
> On Mon, Jul 04, 2011 at 03:27:35PM +1000, Dave Chinner wrote:
> > The first two patches fix the recently reported rm -rf performance
> > and interactivity problems when using delay??d logging. These should
> > probably be considered for 3.0-rc5.
> 
> I think it's a bit late for patch 2.  Patch 1 is triviall, and helps
> with a regression introduced in 2.6.39 by switching to the delaylog
> mode, but patch 2 is a bit too large for this in the merge window
> unless absolutely nessecary. 

Yeah, that's fair enough. The first patch should prevent the
majority of the problematic occurrences of out-of-order AIL
insertion, so we can live without the second one for the moment.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH 2/5] xfs: use a cursor for bulk AIL insertion

[Christoph Hellwig]

[-- Attachment #1: backport2.diff --]
[-- Type: text/plain, Size: 10134 bytes --]

From: Dave Chinner <dchinner@redhat.com>

commit 1d8c95a363bf8cd4d4182dd19c01693b635311c2 upstream


xfs: use a cursor for bulk AIL insertion

Delayed logging can insert tens of thousands of log items into the
AIL at the same LSN. When the committing of log commit records
occur, we can get insertions occurring at an LSN that is not at the
end of the AIL. If there are thousands of items in the AIL on the
tail LSN, each insertion has to walk the AIL to find the correct
place to insert the new item into the AIL. This can consume large
amounts of CPU time and block other operations from occurring while
the traversals are in progress.

To avoid this repeated walk, use a AIL cursor to record
where we should be inserting the new items into the AIL without
having to repeat the walk. The cursor infrastructure already
provides this functionality for push walks, so is a simple extension
of existing code. While this will not avoid the initial walk, it
will avoid repeating it tens of thousands of times during a single
checkpoint commit.

This version includes logic improvements from Christoph Hellwig.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
Reviewed-by: Christoph Hellwig <hch@lst.de>
Signed-off-by: Alex Elder <aelder@sgi.com>

diff --git a/fs/xfs/xfs_trans.c b/fs/xfs/xfs_trans.c
index c83f63b..efc147f 100644
--- a/fs/xfs/xfs_trans.c
+++ b/fs/xfs/xfs_trans.c
@@ -1426,6 +1426,7 @@ xfs_trans_committed(
 static inline void
 xfs_log_item_batch_insert(
 	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
 	struct xfs_log_item	**log_items,
 	int			nr_items,
 	xfs_lsn_t		commit_lsn)
@@ -1434,7 +1435,7 @@ xfs_log_item_batch_insert(
 
 	spin_lock(&ailp->xa_lock);
 	/* xfs_trans_ail_update_bulk drops ailp->xa_lock */
-	xfs_trans_ail_update_bulk(ailp, log_items, nr_items, commit_lsn);
+	xfs_trans_ail_update_bulk(ailp, cur, log_items, nr_items, commit_lsn);
 
 	for (i = 0; i < nr_items; i++)
 		IOP_UNPIN(log_items[i], 0);
@@ -1452,6 +1453,13 @@ xfs_log_item_batch_insert(
  * as an iclog write error even though we haven't started any IO yet. Hence in
  * this case all we need to do is IOP_COMMITTED processing, followed by an
  * IOP_UNPIN(aborted) call.
+ *
+ * The AIL cursor is used to optimise the insert process. If commit_lsn is not
+ * at the end of the AIL, the insert cursor avoids the need to walk
+ * the AIL to find the insertion point on every xfs_log_item_batch_insert()
+ * call. This saves a lot of needless list walking and is a net win, even
+ * though it slightly increases that amount of AIL lock traffic to set it up
+ * and tear it down.
  */
 void
 xfs_trans_committed_bulk(
@@ -1463,8 +1471,13 @@ xfs_trans_committed_bulk(
 #define LOG_ITEM_BATCH_SIZE	32
 	struct xfs_log_item	*log_items[LOG_ITEM_BATCH_SIZE];
 	struct xfs_log_vec	*lv;
+	struct xfs_ail_cursor	cur;
 	int			i = 0;
 
+	spin_lock(&ailp->xa_lock);
+	xfs_trans_ail_cursor_last(ailp, &cur, commit_lsn);
+	spin_unlock(&ailp->xa_lock);
+
 	/* unpin all the log items */
 	for (lv = log_vector; lv; lv = lv->lv_next ) {
 		struct xfs_log_item	*lip = lv->lv_item;
@@ -1493,7 +1506,9 @@ xfs_trans_committed_bulk(
 			/*
 			 * Not a bulk update option due to unusual item_lsn.
 			 * Push into AIL immediately, rechecking the lsn once
-			 * we have the ail lock. Then unpin the item.
+			 * we have the ail lock. Then unpin the item. This does
+			 * not affect the AIL cursor the bulk insert path is
+			 * using.
 			 */
 			spin_lock(&ailp->xa_lock);
 			if (XFS_LSN_CMP(item_lsn, lip->li_lsn) > 0)
@@ -1507,7 +1522,7 @@ xfs_trans_committed_bulk(
 		/* Item is a candidate for bulk AIL insert.  */
 		log_items[i++] = lv->lv_item;
 		if (i >= LOG_ITEM_BATCH_SIZE) {
-			xfs_log_item_batch_insert(ailp, log_items,
+			xfs_log_item_batch_insert(ailp, &cur, log_items,
 					LOG_ITEM_BATCH_SIZE, commit_lsn);
 			i = 0;
 		}
@@ -1515,7 +1530,11 @@ xfs_trans_committed_bulk(
 
 	/* make sure we insert the remainder! */
 	if (i)
-		xfs_log_item_batch_insert(ailp, log_items, i, commit_lsn);
+		xfs_log_item_batch_insert(ailp, &cur, log_items, i, commit_lsn);
+
+	spin_lock(&ailp->xa_lock);
+	xfs_trans_ail_cursor_done(ailp, &cur);
+	spin_unlock(&ailp->xa_lock);
 }
 
 /*
diff --git a/fs/xfs/xfs_trans_ail.c b/fs/xfs/xfs_trans_ail.c
index 5fc2380..9a69dc0 100644
--- a/fs/xfs/xfs_trans_ail.c
+++ b/fs/xfs/xfs_trans_ail.c
@@ -272,9 +272,9 @@ xfs_trans_ail_cursor_clear(
 }
 
 /*
- * Return the item in the AIL with the current lsn.
- * Return the current tree generation number for use
- * in calls to xfs_trans_next_ail().
+ * Initialise the cursor to the first item in the AIL with the given @lsn.
+ * This searches the list from lowest LSN to highest. Pass a @lsn of zero
+ * to initialise the cursor to the first item in the AIL.
  */
 xfs_log_item_t *
 xfs_trans_ail_cursor_first(
@@ -300,31 +300,97 @@ out:
 }
 
 /*
- * splice the log item list into the AIL at the given LSN.
+ * Initialise the cursor to the last item in the AIL with the given @lsn.
+ * This searches the list from highest LSN to lowest. If there is no item with
+ * the value of @lsn, then it sets the cursor to the last item with an LSN lower
+ * than @lsn.
+ */
+static struct xfs_log_item *
+__xfs_trans_ail_cursor_last(
+	struct xfs_ail		*ailp,
+	xfs_lsn_t		lsn)
+{
+	xfs_log_item_t		*lip;
+
+	list_for_each_entry_reverse(lip, &ailp->xa_ail, li_ail) {
+		if (XFS_LSN_CMP(lip->li_lsn, lsn) <= 0)
+			return lip;
+	}
+	return NULL;
+}
+
+/*
+ * Initialise the cursor to the last item in the AIL with the given @lsn.
+ * This searches the list from highest LSN to lowest.
+ */
+struct xfs_log_item *
+xfs_trans_ail_cursor_last(
+	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
+	xfs_lsn_t		lsn)
+{
+	xfs_trans_ail_cursor_init(ailp, cur);
+	cur->item = __xfs_trans_ail_cursor_last(ailp, lsn);
+	return cur->item;
+}
+
+/*
+ * splice the log item list into the AIL at the given LSN. We splice to the
+ * tail of the given LSN to maintain insert order for push traversals. The
+ * cursor is optional, allowing repeated updates to the same LSN to avoid
+ * repeated traversals.
  */
 static void
 xfs_ail_splice(
-	struct xfs_ail  *ailp,
-	struct list_head *list,
-	xfs_lsn_t       lsn)
+	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
+	struct list_head	*list,
+	xfs_lsn_t		lsn)
 {
-	xfs_log_item_t  *next_lip;
+	struct xfs_log_item	*lip = cur ? cur->item : NULL;
+	struct xfs_log_item	*next_lip;
 
-	/* If the list is empty, just insert the item.  */
-	if (list_empty(&ailp->xa_ail)) {
-		list_splice(list, &ailp->xa_ail);
-		return;
+	/*
+	 * Get a new cursor if we don't have a placeholder or the existing one
+	 * has been invalidated.
+	 */
+	if (!lip || (__psint_t)lip & 1) {
+		lip = __xfs_trans_ail_cursor_last(ailp, lsn);
+
+		if (!lip) {
+			/* The list is empty, so just splice and return.  */
+			if (cur)
+				cur->item = NULL;
+			list_splice(list, &ailp->xa_ail);
+			return;
+		}
 	}
 
-	list_for_each_entry_reverse(next_lip, &ailp->xa_ail, li_ail) {
-		if (XFS_LSN_CMP(next_lip->li_lsn, lsn) <= 0)
-			break;
+	/*
+	 * Our cursor points to the item we want to insert _after_, so we have
+	 * to update the cursor to point to the end of the list we are splicing
+	 * in so that it points to the correct location for the next splice.
+	 * i.e. before the splice
+	 *
+	 *  lsn -> lsn -> lsn + x -> lsn + x ...
+	 *          ^
+	 *          | cursor points here
+	 *
+	 * After the splice we have:
+	 *
+	 *  lsn -> lsn -> lsn -> lsn -> .... -> lsn -> lsn + x -> lsn + x ...
+	 *          ^                            ^
+	 *          | cursor points here         | needs to move here
+	 *
+	 * So we set the cursor to the last item in the list to be spliced
+	 * before we execute the splice, resulting in the cursor pointing to
+	 * the correct item after the splice occurs.
+	 */
+	if (cur) {
+		next_lip = list_entry(list->prev, struct xfs_log_item, li_ail);
+		cur->item = next_lip;
 	}
-
-	ASSERT(&next_lip->li_ail == &ailp->xa_ail ||
-	       XFS_LSN_CMP(next_lip->li_lsn, lsn) <= 0);
-
-	list_splice_init(list, &next_lip->li_ail);
+	list_splice(list, &lip->li_ail);
 }
 
 /*
@@ -645,6 +711,7 @@ xfs_trans_unlocked_item(
 void
 xfs_trans_ail_update_bulk(
 	struct xfs_ail		*ailp,
+	struct xfs_ail_cursor	*cur,
 	struct xfs_log_item	**log_items,
 	int			nr_items,
 	xfs_lsn_t		lsn) __releases(ailp->xa_lock)
@@ -674,7 +741,7 @@ xfs_trans_ail_update_bulk(
 		list_add(&lip->li_ail, &tmp);
 	}
 
-	xfs_ail_splice(ailp, &tmp, lsn);
+	xfs_ail_splice(ailp, cur, &tmp, lsn);
 
 	if (!mlip_changed) {
 		spin_unlock(&ailp->xa_lock);
diff --git a/fs/xfs/xfs_trans_priv.h b/fs/xfs/xfs_trans_priv.h
index 6b164e9..c0cb408 100644
--- a/fs/xfs/xfs_trans_priv.h
+++ b/fs/xfs/xfs_trans_priv.h
@@ -82,6 +82,7 @@ struct xfs_ail {
 extern struct workqueue_struct	*xfs_ail_wq;	/* AIL workqueue */
 
 void	xfs_trans_ail_update_bulk(struct xfs_ail *ailp,
+				struct xfs_ail_cursor *cur,
 				struct xfs_log_item **log_items, int nr_items,
 				xfs_lsn_t lsn) __releases(ailp->xa_lock);
 static inline void
@@ -90,7 +91,7 @@ xfs_trans_ail_update(
 	struct xfs_log_item	*lip,
 	xfs_lsn_t		lsn) __releases(ailp->xa_lock)
 {
-	xfs_trans_ail_update_bulk(ailp, &lip, 1, lsn);
+	xfs_trans_ail_update_bulk(ailp, NULL, &lip, 1, lsn);
 }
 
 void	xfs_trans_ail_delete_bulk(struct xfs_ail *ailp,
@@ -111,10 +112,13 @@ xfs_lsn_t		xfs_ail_min_lsn(struct xfs_ail *ailp);
 void			xfs_trans_unlocked_item(struct xfs_ail *,
 					xfs_log_item_t *);
 
-struct xfs_log_item	*xfs_trans_ail_cursor_first(struct xfs_ail *ailp,
+struct xfs_log_item *	xfs_trans_ail_cursor_first(struct xfs_ail *ailp,
 					struct xfs_ail_cursor *cur,
 					xfs_lsn_t lsn);
-struct xfs_log_item	*xfs_trans_ail_cursor_next(struct xfs_ail *ailp,
+struct xfs_log_item *	xfs_trans_ail_cursor_last(struct xfs_ail *ailp,
+					struct xfs_ail_cursor *cur,
+					xfs_lsn_t lsn);
+struct xfs_log_item *	xfs_trans_ail_cursor_next(struct xfs_ail *ailp,
 					struct xfs_ail_cursor *cur);
 void			xfs_trans_ail_cursor_done(struct xfs_ail *ailp,
 					struct xfs_ail_cursor *cur);

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs