Re: [PATCH 1/4] xfs: use a cursor for bulk AIL insertion

[Alex Elder <aelder@sgi.com>]

On Mon, 2011-07-18 at 13:40 +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.
> 
> This version includes logic improvements from Christoph Hellwig.
> 
> Signed-off-by: Dave Chinner <dchinner@redhat.com>

I think there's a case that can be improved (though
it isn't wrong as-is), and assuming I'm right, I have
provided a modified splice function (not tested), below.

But if you don't want to change anything, this code
looks OK to me, so:

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

. . .

> +
> +/*
> + * 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;

If the AIL was empty, I think we still want to
make the cursor point to the end of the list that's
being spliced in, don't we?

> +			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);
>  }
>  
>  /*


So assuming my comment above is right, how about this:

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;

        /*
         * Use the cursor to determine the insertion point if one is
         * provided.
         */
        lip = cur ? cur->item : NULL;
        if (!lip || (__psint_t) lip & 1)
                lip = __xfs_trans_ail_cursor_last(ailp, lsn);

        /*
         * If a cursor is provided, we know we're processing the AIL
         * in lsn order, and future items to be spliced in will
         * follow the last one being inserted now.  Update the
         * cursor to point to that last item, now while we have a
         * reliable pointer to it.
         */
        if (cur)
                cur->item = list_entry(list->prev, struct xfs_log_item,
li_ail);

        /*
         * Finally perform the splice.  Unless the AIL was empty,
         * lip points to the item in the AIL _after_ which the new
         * items should go.  If lip is null the AIL was empty, so
         * the new items go at the head of the AIL.
         */
        if (lip)
                list_splice(list, &lip->li_ail);
        else
                list_splice(list, &ailp->xa_ail);
}


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