/*
 * Copyright (C) 2016 Oracle.  All Rights Reserved.
 *
 * Author: Darrick J. Wong <darrick.wong@oracle.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA.
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
#include "xfs_bit.h"
#include "xfs_sb.h"
#include "xfs_mount.h"
#include "xfs_defer.h"
#include "xfs_trans.h"
#include "xfs_trace.h"

/*
 * Deferred Operations in XFS
 *
 * Due to the way locking rules work in XFS, certain transactions (block
 * mapping and unmapping, typically) have permanent reservations so that
 * we can roll the transaction to adhere to AG locking order rules and
 * to unlock buffers between metadata updates.  Prior to rmap/reflink,
 * the mapping code had a mechanism to perform these deferrals for
 * extents that were going to be freed; this code makes that facility
 * more generic.
 *
 * When adding the reverse mapping and reflink features, it became
 * necessary to perform complex remapping multi-transactions to comply
 * with AG locking order rules, and to be able to spread a single
 * refcount update operation (an operation on an n-block extent can
 * update as many as n records!) among multiple transactions.  XFS can
 * roll a transaction to facilitate this, but using this facility
 * requires us to log "intent" items in case log recovery needs to
 * redo the operation, and to log "done" items to indicate that redo
 * is not necessary.
 *
 * Deferred work is tracked in xfs_defer_pending items.  Each pending
 * item tracks one type of deferred work.  Incoming work items (which
 * have not yet had an intent logged) are attached to a pending item
 * on the dop_intake list, where they wait for the caller to finish
 * the deferred operations.
 *
 * Finishing a set of deferred operations is an involved process.  To
 * start, we define "rolling a deferred-op transaction" as follows:
 *
 * > For each xfs_defer_pending item on the dop_intake list,
 *   - Sort the work items in AG order.  XFS locking
 *     order rules require us to lock buffers in AG order.
 *   - Create a log intent item for that type.
 *   - Attach it to the pending item.
 *   - Move the pending item from the dop_intake list to the
 *     dop_pending list.
 * > Roll the transaction.
 *
 * NOTE: To avoid exceeding the transaction reservation, we limit the
 * number of items that we attach to a given xfs_defer_pending.
 *
 * The actual finishing process looks like this:
 *
 * > For each xfs_defer_pending in the dop_pending list,
 *   - Roll the deferred-op transaction as above.
 *   - Create a log done item for that type, and attach it to the
 *     log intent item.
 *   - For each work item attached to the log intent item,
 *     * Perform the described action.
 *     * Attach the work item to the log done item.
 *     * If the result of doing the work was -EAGAIN, ->finish work
 *       wants a new transaction.  See the "Requesting a Fresh
 *       Transaction while Finishing Deferred Work" section below for
 *       details.
 *
 * The key here is that we must log an intent item for all pending
 * work items every time we roll the transaction, and that we must log
 * a done item as soon as the work is completed.  With this mechanism
 * we can perform complex remapping operations, chaining intent items
 * as needed.
 *
 * Requesting a Fresh Transaction while Finishing Deferred Work
 *
 * If ->finish_item decides that it needs a fresh transaction to
 * finish the work, it must ask its caller (xfs_defer_finish) for a
 * continuation.  The most likely cause of this circumstance are the
 * refcount adjust functions deciding that they've logged enough items
 * to be at risk of exceeding the transaction reservation.
 *
 * To get a fresh transaction, we want to log the existing log done
 * item to prevent the log intent item from replaying, immediately log
 * a new log intent item with the unfinished work items, roll the
 * transaction, and re-call ->finish_item wherever it left off.  The
 * log done item and the new log intent item must be in the same
 * transaction or atomicity cannot be guaranteed; defer_finish ensures
 * that this happens.
 *
 * This requires some coordination between ->finish_item and
 * defer_finish.  Upon deciding to request a new transaction,
 * ->finish_item should update the current work item to reflect the
 * unfinished work.  Next, it should reset the log done item's list
 * count to the number of items finished, and return -EAGAIN.
 * defer_finish sees the -EAGAIN, logs the new log intent item
 * with the remaining work items, and leaves the xfs_defer_pending
 * item at the head of the dop_work queue.  Then it rolls the
 * transaction and picks up processing where it left off.  It is
 * required that ->finish_item must be careful to leave enough
 * transaction reservation to fit the new log intent item.
 *
 * This is an example of remapping the extent (E, E+B) into file X at
 * offset A and dealing with the extent (C, C+B) already being mapped
 * there:
 * +-------------------------------------------------+
 * | Unmap file X startblock C offset A length B     | t0
 * | Intent to reduce refcount for extent (C, B)     |
 * | Intent to remove rmap (X, C, A, B)              |
 * | Intent to free extent (D, 1) (bmbt block)       |
 * | Intent to map (X, A, B) at startblock E         |
 * +-------------------------------------------------+
 * | Map file X startblock E offset A length B       | t1
 * | Done mapping (X, E, A, B)                       |
 * | Intent to increase refcount for extent (E, B)   |
 * | Intent to add rmap (X, E, A, B)                 |
 * +-------------------------------------------------+
 * | Reduce refcount for extent (C, B)               | t2
 * | Done reducing refcount for extent (C, 9)        |
 * | Intent to reduce refcount for extent (C+9, B-9) |
 * | (ran out of space after 9 refcount updates)     |
 * +-------------------------------------------------+
 * | Reduce refcount for extent (C+9, B+9)           | t3
 * | Done reducing refcount for extent (C+9, B-9)    |
 * | Increase refcount for extent (E, B)             |
 * | Done increasing refcount for extent (E, B)      |
 * | Intent to free extent (C, B)                    |
 * | Intent to free extent (F, 1) (refcountbt block) |
 * | Intent to remove rmap (F, 1, REFC)              |
 * +-------------------------------------------------+
 * | Remove rmap (X, C, A, B)                        | t4
 * | Done removing rmap (X, C, A, B)                 |
 * | Add rmap (X, E, A, B)                           |
 * | Done adding rmap (X, E, A, B)                   |
 * | Remove rmap (F, 1, REFC)                        |
 * | Done removing rmap (F, 1, REFC)                 |
 * +-------------------------------------------------+
 * | Free extent (C, B)                              | t5
 * | Done freeing extent (C, B)                      |
 * | Free extent (D, 1)                              |
 * | Done freeing extent (D, 1)                      |
 * | Free extent (F, 1)                              |
 * | Done freeing extent (F, 1)                      |
 * +-------------------------------------------------+
 *
 * If we should crash before t2 commits, log recovery replays
 * the following intent items:
 *
 * - Intent to reduce refcount for extent (C, B)
 * - Intent to remove rmap (X, C, A, B)
 * - Intent to free extent (D, 1) (bmbt block)
 * - Intent to increase refcount for extent (E, B)
 * - Intent to add rmap (X, E, A, B)
 *
 * In the process of recovering, it should also generate and take care
 * of these intent items:
 *
 * - Intent to free extent (C, B)
 * - Intent to free extent (F, 1) (refcountbt block)
 * - Intent to remove rmap (F, 1, REFC)
 *
 * Note that the continuation requested between t2 and t3 is likely to
 * reoccur.
 */

static const struct xfs_defer_op_type *defer_op_types[XFS_DEFER_OPS_TYPE_MAX];

/*
 * For each pending item in the intake list, log its intent item and the
 * associated extents, then add the entire intake list to the end of
 * the pending list.
 */
STATIC void
xfs_defer_intake_work(
        struct xfs_trans                *tp,
        struct xfs_defer_ops            *dop)
{
        struct list_head                *li;
        struct xfs_defer_pending        *dfp;

        list_for_each_entry(dfp, &dop->dop_intake, dfp_list) {
                dfp->dfp_intent = dfp->dfp_type->create_intent(tp,
                                dfp->dfp_count);
                trace_xfs_defer_intake_work(tp->t_mountp, dfp);
                list_sort(tp->t_mountp, &dfp->dfp_work,
                                dfp->dfp_type->diff_items);
                list_for_each(li, &dfp->dfp_work)
                        dfp->dfp_type->log_item(tp, dfp->dfp_intent, li);
        }

        list_splice_tail_init(&dop->dop_intake, &dop->dop_pending);
}

/* Abort all the intents that were committed. */
STATIC void
xfs_defer_trans_abort(
        struct xfs_trans                *tp,
        struct xfs_defer_ops            *dop,
        int                             error)
{
        struct xfs_defer_pending        *dfp;

        trace_xfs_defer_trans_abort(tp->t_mountp, dop);

        /* Abort intent items that don't have a done item. */
        list_for_each_entry(dfp, &dop->dop_pending, dfp_list) {
                trace_xfs_defer_pending_abort(tp->t_mountp, dfp);
                if (dfp->dfp_intent && !dfp->dfp_done) {
                        dfp->dfp_type->abort_intent(dfp->dfp_intent);
                        dfp->dfp_intent = NULL;
                }
        }

        /* Shut down FS. */
        xfs_force_shutdown(tp->t_mountp, (error == -EFSCORRUPTED) ?
                        SHUTDOWN_CORRUPT_INCORE : SHUTDOWN_META_IO_ERROR);
}

/* Roll a transaction so we can do some deferred op processing. */
STATIC int
xfs_defer_trans_roll(
        struct xfs_trans                **tp,
        struct xfs_defer_ops            *dop,
        struct xfs_inode                *ip)
{
        int                             i;
        int                             error;

        /* Log all the joined inodes except the one we passed in. */
        for (i = 0; i < XFS_DEFER_OPS_NR_INODES && dop->dop_inodes[i]; i++) {
                if (dop->dop_inodes[i] == ip)
                        continue;
                xfs_trans_log_inode(*tp, dop->dop_inodes[i], XFS_ILOG_CORE);
        }

        trace_xfs_defer_trans_roll((*tp)->t_mountp, dop);

        /* Roll the transaction. */
        error = xfs_trans_roll(tp, ip);
        if (error) {
                trace_xfs_defer_trans_roll_error((*tp)->t_mountp, dop, error);
                xfs_defer_trans_abort(*tp, dop, error);
                return error;
        }
        dop->dop_committed = true;

        /* Rejoin the joined inodes except the one we passed in. */
        for (i = 0; i < XFS_DEFER_OPS_NR_INODES && dop->dop_inodes[i]; i++) {
                if (dop->dop_inodes[i] == ip)
                        continue;
                xfs_trans_ijoin(*tp, dop->dop_inodes[i], 0);
        }

        return error;
}

/* Do we have any work items to finish? */
bool
xfs_defer_has_unfinished_work(
        struct xfs_defer_ops            *dop)
{
        return !list_empty(&dop->dop_pending) || !list_empty(&dop->dop_intake);
}

/*
 * Add this inode to the deferred op.  Each joined inode is relogged
 * each time we roll the transaction, in addition to any inode passed
 * to xfs_defer_finish().
 */
int
xfs_defer_join(
        struct xfs_defer_ops            *dop,
        struct xfs_inode                *ip)
{
        int                             i;

        for (i = 0; i < XFS_DEFER_OPS_NR_INODES; i++) {
                if (dop->dop_inodes[i] == ip)
                        return 0;
                else if (dop->dop_inodes[i] == NULL) {
                        dop->dop_inodes[i] = ip;
                        return 0;
                }
        }

        return -EFSCORRUPTED;
}

/*
 * Finish all the pending work.  This involves logging intent items for
 * any work items that wandered in since the last transaction roll (if
 * one has even happened), rolling the transaction, and finishing the
 * work items in the first item on the logged-and-pending list.
 *
 * If an inode is provided, relog it to the new transaction.
 */
int
xfs_defer_finish(
        struct xfs_trans                **tp,
        struct xfs_defer_ops            *dop,
        struct xfs_inode                *ip)
{
        struct xfs_defer_pending        *dfp;
        struct list_head                *li;
        struct list_head                *n;
        void                            *state;
        int                             error = 0;
        void                            (*cleanup_fn)(struct xfs_trans *, void *, int);

        ASSERT((*tp)->t_flags & XFS_TRANS_PERM_LOG_RES);

        trace_xfs_defer_finish((*tp)->t_mountp, dop);

        /* Until we run out of pending work to finish... */
        while (xfs_defer_has_unfinished_work(dop)) {
                /* Log intents for work items sitting in the intake. */
                xfs_defer_intake_work(*tp, dop);

                /* Roll the transaction. */
                error = xfs_defer_trans_roll(tp, dop, ip);
                if (error)
                        goto out;

                /* Log an intent-done item for the first pending item. */
                dfp = list_first_entry(&dop->dop_pending,
                                struct xfs_defer_pending, dfp_list);
                trace_xfs_defer_pending_finish((*tp)->t_mountp, dfp);
                dfp->dfp_done = dfp->dfp_type->create_done(*tp, dfp->dfp_intent,
                                dfp->dfp_count);
                cleanup_fn = dfp->dfp_type->finish_cleanup;

                /* Finish the work items. */
                state = NULL;
                list_for_each_safe(li, n, &dfp->dfp_work) {
                        list_del(li);
                        dfp->dfp_count--;
                        error = dfp->dfp_type->finish_item(*tp, dop, li,
                                        dfp->dfp_done, &state);
                        if (error == -EAGAIN) {
                                /*
                                 * Caller wants a fresh transaction;
                                 * put the work item back on the list
                                 * and jump out.
                                 */
                                list_add(li, &dfp->dfp_work);
                                dfp->dfp_count++;
                                break;
                        } else if (error) {
                                /*
                                 * Clean up after ourselves and jump out.
                                 * xfs_defer_cancel will take care of freeing
                                 * all these lists and stuff.
                                 */
                                if (cleanup_fn)
                                        cleanup_fn(*tp, state, error);
                                xfs_defer_trans_abort(*tp, dop, error);
                                goto out;
                        }
                }
                if (error == -EAGAIN) {
                        /*
                         * Caller wants a fresh transaction, so log a
                         * new log intent item to replace the old one
                         * and roll the transaction.  See "Requesting
                         * a Fresh Transaction while Finishing
                         * Deferred Work" above.
                         */
                        dfp->dfp_intent = dfp->dfp_type->create_intent(*tp,
                                        dfp->dfp_count);
                        dfp->dfp_done = NULL;
                        list_for_each(li, &dfp->dfp_work)
                                dfp->dfp_type->log_item(*tp, dfp->dfp_intent,
                                                li);
                } else {
                        /* Done with the dfp, free it. */
                        list_del(&dfp->dfp_list);
                        kmem_free(dfp);
                }

                if (cleanup_fn)
                        cleanup_fn(*tp, state, error);
        }

out:
        if (error)
                trace_xfs_defer_finish_error((*tp)->t_mountp, dop, error);
        else
                trace_xfs_defer_finish_done((*tp)->t_mountp, dop);
        return error;
}

/*
 * Free up any items left in the list.
 */
void
xfs_defer_cancel(
        struct xfs_defer_ops            *dop)
{
        struct xfs_defer_pending        *dfp;
        struct xfs_defer_pending        *pli;
        struct list_head                *pwi;
        struct list_head                *n;

        trace_xfs_defer_cancel(NULL, dop);

        /*
         * Free the pending items.  Caller should already have arranged
         * for the intent items to be released.
         */
        list_for_each_entry_safe(dfp, pli, &dop->dop_intake, dfp_list) {
                trace_xfs_defer_intake_cancel(NULL, dfp);
                list_del(&dfp->dfp_list);
                list_for_each_safe(pwi, n, &dfp->dfp_work) {
                        list_del(pwi);
                        dfp->dfp_count--;
                        dfp->dfp_type->cancel_item(pwi);
                }
                ASSERT(dfp->dfp_count == 0);
                kmem_free(dfp);
        }
        list_for_each_entry_safe(dfp, pli, &dop->dop_pending, dfp_list) {
                trace_xfs_defer_pending_cancel(NULL, dfp);
                list_del(&dfp->dfp_list);
                list_for_each_safe(pwi, n, &dfp->dfp_work) {
                        list_del(pwi);
                        dfp->dfp_count--;
                        dfp->dfp_type->cancel_item(pwi);
                }
                ASSERT(dfp->dfp_count == 0);
                kmem_free(dfp);
        }
}

/* Add an item for later deferred processing. */
void
xfs_defer_add(
        struct xfs_defer_ops            *dop,
        enum xfs_defer_ops_type         type,
        struct list_head                *li)
{
        struct xfs_defer_pending        *dfp = NULL;

        /*
         * Add the item to a pending item at the end of the intake list.
         * If the last pending item has the same type, reuse it.  Else,
         * create a new pending item at the end of the intake list.
         */
        if (!list_empty(&dop->dop_intake)) {
                dfp = list_last_entry(&dop->dop_intake,
                                struct xfs_defer_pending, dfp_list);
                if (dfp->dfp_type->type != type ||
                    (dfp->dfp_type->max_items &&
                     dfp->dfp_count >= dfp->dfp_type->max_items))
                        dfp = NULL;
        }
        if (!dfp) {
                dfp = kmem_alloc(sizeof(struct xfs_defer_pending),
                                KM_SLEEP | KM_NOFS);
                dfp->dfp_type = defer_op_types[type];
                dfp->dfp_intent = NULL;
                dfp->dfp_done = NULL;
                dfp->dfp_count = 0;
                INIT_LIST_HEAD(&dfp->dfp_work);
                list_add_tail(&dfp->dfp_list, &dop->dop_intake);
        }

        list_add_tail(li, &dfp->dfp_work);
        dfp->dfp_count++;
}

/* Initialize a deferred operation list. */
void
xfs_defer_init_op_type(
        const struct xfs_defer_op_type  *type)
{
        defer_op_types[type->type] = type;
}

/* Initialize a deferred operation. */
void
xfs_defer_init(
        struct xfs_defer_ops            *dop,
        xfs_fsblock_t                   *fbp)
{
        dop->dop_committed = false;
        dop->dop_low = false;
        memset(&dop->dop_inodes, 0, sizeof(dop->dop_inodes));
        *fbp = NULLFSBLOCK;
        INIT_LIST_HEAD(&dop->dop_intake);
        INIT_LIST_HEAD(&dop->dop_pending);
        trace_xfs_defer_init(NULL, dop);
}