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

Alex Elder
2011-07-19T23:03:49Z

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);
}