xfs
[Top] [All Lists]

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

To: Dave Chinner <david@xxxxxxxxxxxxx>
Subject: Re: [PATCH 1/4] xfs: use a cursor for bulk AIL insertion
From: Alex Elder <aelder@xxxxxxx>
Date: Tue, 19 Jul 2011 18:03:44 -0500
Cc: <xfs@xxxxxxxxxxx>
In-reply-to: <1310960419-9875-2-git-send-email-david@xxxxxxxxxxxxx>
References: <1310960419-9875-1-git-send-email-david@xxxxxxxxxxxxx> <1310960419-9875-2-git-send-email-david@xxxxxxxxxxxxx>
Reply-to: <aelder@xxxxxxx>
On Mon, 2011-07-18 at 13:40 +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@xxxxxxxxxx>
> 
> 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@xxxxxxxxxx>

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@xxxxxxx>

. . .

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


<Prev in Thread] Current Thread [Next in Thread>