/*
 * raid5.c : Multiple Devices driver for Linux
 *         Copyright (C) 1996, 1997 Ingo Molnar, Miguel de Icaza, Gadi Oxman
 *         Copyright (C) 1999, 2000 Ingo Molnar
 *         Copyright (C) 2002, 2003 H. Peter Anvin
 *
 * RAID-4/5/6 management functions.
 * Thanks to Penguin Computing for making the RAID-6 development possible
 * by donating a test server!
 *
 * 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, or (at your option)
 * any later version.
 *
 * You should have received a copy of the GNU General Public License
 * (for example /usr/src/linux/COPYING); if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 * BITMAP UNPLUGGING:
 *
 * The sequencing for updating the bitmap reliably is a little
 * subtle (and I got it wrong the first time) so it deserves some
 * explanation.
 *
 * We group bitmap updates into batches.  Each batch has a number.
 * We may write out several batches at once, but that isn't very important.
 * conf->seq_write is the number of the last batch successfully written.
 * conf->seq_flush is the number of the last batch that was closed to
 *    new additions.
 * When we discover that we will need to write to any block in a stripe
 * (in add_stripe_bio) we update the in-memory bitmap and record in sh->bm_seq
 * the number of the batch it will be in. This is seq_flush+1.
 * When we are ready to do a write, if that batch hasn't been written yet,
 *   we plug the array and queue the stripe for later.
 * When an unplug happens, we increment bm_flush, thus closing the current
 *   batch.
 * When we notice that bm_flush > bm_write, we write out all pending updates
 * to the bitmap, and advance bm_write to where bm_flush was.
 * This may occasionally write a bit out twice, but is sure never to
 * miss any bits.
 */

#include <linux/blkdev.h>
#include <linux/kthread.h>
#include <linux/raid/pq.h>
#include <linux/async_tx.h>
#include <linux/module.h>
#include <linux/async.h>
#include <linux/seq_file.h>
#include <linux/cpu.h>
#include <linux/slab.h>
#include <linux/ratelimit.h>
#include <linux/nodemask.h>
#include <linux/flex_array.h>
#include <linux/sched/signal.h>

#include <trace/events/block.h>
#include <linux/list_sort.h>

#include "md.h"
#include "raid5.h"
#include "raid0.h"
#include "bitmap.h"
#include "raid5-log.h"

#define UNSUPPORTED_MDDEV_FLAGS (1L << MD_FAILFAST_SUPPORTED)

#define cpu_to_group(cpu) cpu_to_node(cpu)
#define ANY_GROUP NUMA_NO_NODE

static bool devices_handle_discard_safely = false;
module_param(devices_handle_discard_safely, bool, 0644);
MODULE_PARM_DESC(devices_handle_discard_safely,
                 "Set to Y if all devices in each array reliably return zeroes on reads from discarded regions");
static struct workqueue_struct *raid5_wq;

static inline struct hlist_head *stripe_hash(struct r5conf *conf, sector_t sect)
{
        int hash = (sect >> STRIPE_SHIFT) & HASH_MASK;
        return &conf->stripe_hashtbl[hash];
}

static inline int stripe_hash_locks_hash(sector_t sect)
{
        return (sect >> STRIPE_SHIFT) & STRIPE_HASH_LOCKS_MASK;
}

static inline void lock_device_hash_lock(struct r5conf *conf, int hash)
{
        spin_lock_irq(conf->hash_locks + hash);
        spin_lock(&conf->device_lock);
}

static inline void unlock_device_hash_lock(struct r5conf *conf, int hash)
{
        spin_unlock(&conf->device_lock);
        spin_unlock_irq(conf->hash_locks + hash);
}

static inline void lock_all_device_hash_locks_irq(struct r5conf *conf)
{
        int i;
        spin_lock_irq(conf->hash_locks);
        for (i = 1; i < NR_STRIPE_HASH_LOCKS; i++)
                spin_lock_nest_lock(conf->hash_locks + i, conf->hash_locks);
        spin_lock(&conf->device_lock);
}

static inline void unlock_all_device_hash_locks_irq(struct r5conf *conf)
{
        int i;
        spin_unlock(&conf->device_lock);
        for (i = NR_STRIPE_HASH_LOCKS - 1; i; i--)
                spin_unlock(conf->hash_locks + i);
        spin_unlock_irq(conf->hash_locks);
}

/* Find first data disk in a raid6 stripe */
static inline int raid6_d0(struct stripe_head *sh)
{
        if (sh->ddf_layout)
                /* ddf always start from first device */
                return 0;
        /* md starts just after Q block */
        if (sh->qd_idx == sh->disks - 1)
                return 0;
        else
                return sh->qd_idx + 1;
}
static inline int raid6_next_disk(int disk, int raid_disks)
{
        disk++;
        return (disk < raid_disks) ? disk : 0;
}

/* When walking through the disks in a raid5, starting at raid6_d0,
 * We need to map each disk to a 'slot', where the data disks are slot
 * 0 .. raid_disks-3, the parity disk is raid_disks-2 and the Q disk
 * is raid_disks-1.  This help does that mapping.
 */
static int raid6_idx_to_slot(int idx, struct stripe_head *sh,
                             int *count, int syndrome_disks)
{
        int slot = *count;

        if (sh->ddf_layout)
                (*count)++;
        if (idx == sh->pd_idx)
                return syndrome_disks;
        if (idx == sh->qd_idx)
                return syndrome_disks + 1;
        if (!sh->ddf_layout)
                (*count)++;
        return slot;
}

static void print_raid5_conf (struct r5conf *conf);

static int stripe_operations_active(struct stripe_head *sh)
{
        return sh->check_state || sh->reconstruct_state ||
               test_bit(STRIPE_BIOFILL_RUN, &sh->state) ||
               test_bit(STRIPE_COMPUTE_RUN, &sh->state);
}

static bool stripe_is_lowprio(struct stripe_head *sh)
{
        return (test_bit(STRIPE_R5C_FULL_STRIPE, &sh->state) ||
                test_bit(STRIPE_R5C_PARTIAL_STRIPE, &sh->state)) &&
               !test_bit(STRIPE_R5C_CACHING, &sh->state);
}

static void raid5_wakeup_stripe_thread(struct stripe_head *sh)
{
        struct r5conf *conf = sh->raid_conf;
        struct r5worker_group *group;
        int thread_cnt;
        int i, cpu = sh->cpu;

        if (!cpu_online(cpu)) {
                cpu = cpumask_any(cpu_online_mask);
                sh->cpu = cpu;
        }

        if (list_empty(&sh->lru)) {
                struct r5worker_group *group;
                group = conf->worker_groups + cpu_to_group(cpu);
                if (stripe_is_lowprio(sh))
                        list_add_tail(&sh->lru, &group->loprio_list);
                else
                        list_add_tail(&sh->lru, &group->handle_list);
                group->stripes_cnt++;
                sh->group = group;
        }

        if (conf->worker_cnt_per_group == 0) {
                md_wakeup_thread(conf->mddev->thread);
                return;
        }

        group = conf->worker_groups + cpu_to_group(sh->cpu);

        group->workers[0].working = true;
        /* at least one worker should run to avoid race */
        queue_work_on(sh->cpu, raid5_wq, &group->workers[0].work);

        thread_cnt = group->stripes_cnt / MAX_STRIPE_BATCH - 1;
        /* wakeup more workers */
        for (i = 1; i < conf->worker_cnt_per_group && thread_cnt > 0; i++) {
                if (group->workers[i].working == false) {
                        group->workers[i].working = true;
                        queue_work_on(sh->cpu, raid5_wq,
                                      &group->workers[i].work);
                        thread_cnt--;
                }
        }
}

static void do_release_stripe(struct r5conf *conf, struct stripe_head *sh,
                              struct list_head *temp_inactive_list)
{
        int i;
        int injournal = 0;      /* number of date pages with R5_InJournal */

        BUG_ON(!list_empty(&sh->lru));
        BUG_ON(atomic_read(&conf->active_stripes)==0);

        if (r5c_is_writeback(conf->log))
                for (i = sh->disks; i--; )
                        if (test_bit(R5_InJournal, &sh->dev[i].flags))
                                injournal++;
        /*
         * In the following cases, the stripe cannot be released to cached
         * lists. Therefore, we make the stripe write out and set
         * STRIPE_HANDLE:
         *   1. when quiesce in r5c write back;
         *   2. when resync is requested fot the stripe.
         */
        if (test_bit(STRIPE_SYNC_REQUESTED, &sh->state) ||
            (conf->quiesce && r5c_is_writeback(conf->log) &&
             !test_bit(STRIPE_HANDLE, &sh->state) && injournal != 0)) {
                if (test_bit(STRIPE_R5C_CACHING, &sh->state))
                        r5c_make_stripe_write_out(sh);
                set_bit(STRIPE_HANDLE, &sh->state);
        }

        if (test_bit(STRIPE_HANDLE, &sh->state)) {
                if (test_bit(STRIPE_DELAYED, &sh->state) &&
                    !test_bit(STRIPE_PREREAD_ACTIVE, &sh->state))
                        list_add_tail(&sh->lru, &conf->delayed_list);
                else if (test_bit(STRIPE_BIT_DELAY, &sh->state) &&
                           sh->bm_seq - conf->seq_write > 0)
                        list_add_tail(&sh->lru, &conf->bitmap_list);
                else {
                        clear_bit(STRIPE_DELAYED, &sh->state);
                        clear_bit(STRIPE_BIT_DELAY, &sh->state);
                        if (conf->worker_cnt_per_group == 0) {
                                if (stripe_is_lowprio(sh))
                                        list_add_tail(&sh->lru,
                                                        &conf->loprio_list);
                                else
                                        list_add_tail(&sh->lru,
                                                        &conf->handle_list);
                        } else {
                                raid5_wakeup_stripe_thread(sh);
                                return;
                        }
                }
                md_wakeup_thread(conf->mddev->thread);
        } else {
                BUG_ON(stripe_operations_active(sh));
                if (test_and_clear_bit(STRIPE_PREREAD_ACTIVE, &sh->state))
                        if (atomic_dec_return(&conf->preread_active_stripes)
                            < IO_THRESHOLD)
                                md_wakeup_thread(conf->mddev->thread);
                atomic_dec(&conf->active_stripes);
                if (!test_bit(STRIPE_EXPANDING, &sh->state)) {
                        if (!r5c_is_writeback(conf->log))
                                list_add_tail(&sh->lru, temp_inactive_list);
                        else {
                                WARN_ON(test_bit(R5_InJournal, &sh->dev[sh->pd_idx].flags));
                                if (injournal == 0)
                                        list_add_tail(&sh->lru, temp_inactive_list);
                                else if (injournal == conf->raid_disks - conf->max_degraded) {
                                        /* full stripe */
                                        if (!test_and_set_bit(STRIPE_R5C_FULL_STRIPE, &sh->state))
                                                atomic_inc(&conf->r5c_cached_full_stripes);
                                        if (test_and_clear_bit(STRIPE_R5C_PARTIAL_STRIPE, &sh->state))
                                                atomic_dec(&conf->r5c_cached_partial_stripes);
                                        list_add_tail(&sh->lru, &conf->r5c_full_stripe_list);
                                        r5c_check_cached_full_stripe(conf);
                                } else
                                        /*
                                         * STRIPE_R5C_PARTIAL_STRIPE is set in
                                         * r5c_try_caching_write(). No need to
                                         * set it again.
                                         */
                                        list_add_tail(&sh->lru, &conf->r5c_partial_stripe_list);
                        }
                }
        }
}

static void __release_stripe(struct r5conf *conf, struct stripe_head *sh,
                             struct list_head *temp_inactive_list)
{
        if (atomic_dec_and_test(&sh->count))
                do_release_stripe(conf, sh, temp_inactive_list);
}

/*
 * @hash could be NR_STRIPE_HASH_LOCKS, then we have a list of inactive_list
 *
 * Be careful: Only one task can add/delete stripes from temp_inactive_list at
 * given time. Adding stripes only takes device lock, while deleting stripes
 * only takes hash lock.
 */
static void release_inactive_stripe_list(struct r5conf *conf,
                                         struct list_head *temp_inactive_list,
                                         int hash)
{
        int size;
        bool do_wakeup = false;
        unsigned long flags;

        if (hash == NR_STRIPE_HASH_LOCKS) {
                size = NR_STRIPE_HASH_LOCKS;
                hash = NR_STRIPE_HASH_LOCKS - 1;
        } else
                size = 1;
        while (size) {
                struct list_head *list = &temp_inactive_list[size - 1];

                /*
                 * We don't hold any lock here yet, raid5_get_active_stripe() might
                 * remove stripes from the list
                 */
                if (!list_empty_careful(list)) {
                        spin_lock_irqsave(conf->hash_locks + hash, flags);
                        if (list_empty(conf->inactive_list + hash) &&
                            !list_empty(list))
                                atomic_dec(&conf->empty_inactive_list_nr);
                        list_splice_tail_init(list, conf->inactive_list + hash);
                        do_wakeup = true;
                        spin_unlock_irqrestore(conf->hash_locks + hash, flags);
                }
                size--;
                hash--;
        }

        if (do_wakeup) {
                wake_up(&conf->wait_for_stripe);
                if (atomic_read(&conf->active_stripes) == 0)
                        wake_up(&conf->wait_for_quiescent);
                if (conf->retry_read_aligned)
                        md_wakeup_thread(conf->mddev->thread);
        }
}

/* should hold conf->device_lock already */
static int release_stripe_list(struct r5conf *conf,
                               struct list_head *temp_inactive_list)
{
        struct stripe_head *sh, *t;
        int count = 0;
        struct llist_node *head;

        head = llist_del_all(&conf->released_stripes);
        head = llist_reverse_order(head);
        llist_for_each_entry_safe(sh, t, head, release_list) {
                int hash;

                /* sh could be readded after STRIPE_ON_RELEASE_LIST is cleard */
                smp_mb();
                clear_bit(STRIPE_ON_RELEASE_LIST, &sh->state);
                /*
                 * Don't worry the bit is set here, because if the bit is set
                 * again, the count is always > 1. This is true for
                 * STRIPE_ON_UNPLUG_LIST bit too.
                 */
                hash = sh->hash_lock_index;
                __release_stripe(conf, sh, &temp_inactive_list[hash]);
                count++;
        }

        return count;
}

void raid5_release_stripe(struct stripe_head *sh)
{
        struct r5conf *conf = sh->raid_conf;
        unsigned long flags;
        struct list_head list;
        int hash;
        bool wakeup;

        /* Avoid release_list until the last reference.
         */
        if (atomic_add_unless(&sh->count, -1, 1))
                return;

        if (unlikely(!conf->mddev->thread) ||
                test_and_set_bit(STRIPE_ON_RELEASE_LIST, &sh->state))
                goto slow_path;
        wakeup = llist_add(&sh->release_list, &conf->released_stripes);
        if (wakeup)
                md_wakeup_thread(conf->mddev->thread);
        return;
slow_path:
        local_irq_save(flags);
        /* we are ok here if STRIPE_ON_RELEASE_LIST is set or not */
        if (atomic_dec_and_lock(&sh->count, &conf->device_lock)) {
                INIT_LIST_HEAD(&list);
                hash = sh->hash_lock_index;
                do_release_stripe(conf, sh, &list);
                spin_unlock(&conf->device_lock);
                release_inactive_stripe_list(conf, &list, hash);
        }
        local_irq_restore(flags);
}

static inline void remove_hash(struct stripe_head *sh)
{
        pr_debug("remove_hash(), stripe %llu\n",
                (unsigned long long)sh->sector);

        hlist_del_init(&sh->hash);
}

static inline void insert_hash(struct r5conf *conf, struct stripe_head *sh)
{
        struct hlist_head *hp = stripe_hash(conf, sh->sector);

        pr_debug("insert_hash(), stripe %llu\n",
                (unsigned long long)sh->sector);

        hlist_add_head(&sh->hash, hp);
}

/* find an idle stripe, make sure it is unhashed, and return it. */
static struct stripe_head *get_free_stripe(struct r5conf *conf, int hash)
{
        struct stripe_head *sh = NULL;
        struct list_head *first;

        if (list_empty(conf->inactive_list + hash))
                goto out;
        first = (conf->inactive_list + hash)->next;
        sh = list_entry(first, struct stripe_head, lru);
        list_del_init(first);
        remove_hash(sh);
        atomic_inc(&conf->active_stripes);
        BUG_ON(hash != sh->hash_lock_index);
        if (list_empty(conf->inactive_list + hash))
                atomic_inc(&conf->empty_inactive_list_nr);
out:
        return sh;
}

static void shrink_buffers(struct stripe_head *sh)
{
        struct page *p;
        int i;
        int num = sh->raid_conf->pool_size;

        for (i = 0; i < num ; i++) {
                WARN_ON(sh->dev[i].page != sh->dev[i].orig_page);
                p = sh->dev[i].page;
                if (!p)
                        continue;
                sh->dev[i].page = NULL;
                put_page(p);
        }
}

static int grow_buffers(struct stripe_head *sh, gfp_t gfp)
{
        int i;
        int num = sh->raid_conf->pool_size;

        for (i = 0; i < num; i++) {
                struct page *page;

                if (!(page = alloc_page(gfp))) {
                        return 1;
                }
                sh->dev[i].page = page;
                sh->dev[i].orig_page = page;
        }

        return 0;
}

static void raid5_build_block(struct stripe_head *sh, int i, int previous);
static void stripe_set_idx(sector_t stripe, struct r5conf *conf, int previous,
                            struct stripe_head *sh);

static void init_stripe(struct stripe_head *sh, sector_t sector, int previous)
{
        struct r5conf *conf = sh->raid_conf;
        int i, seq;

        BUG_ON(atomic_read(&sh->count) != 0);
        BUG_ON(test_bit(STRIPE_HANDLE, &sh->state));
        BUG_ON(stripe_operations_active(sh));
        BUG_ON(sh->batch_head);

        pr_debug("init_stripe called, stripe %llu\n",
                (unsigned long long)sector);
retry:
        seq = read_seqcount_begin(&conf->gen_lock);
        sh->generation = conf->generation - previous;
        sh->disks = previous ? conf->previous_raid_disks : conf->raid_disks;
        sh->sector = sector;
        stripe_set_idx(sector, conf, previous, sh);
        sh->state = 0;

        for (i = sh->disks; i--; ) {
                struct r5dev *dev = &sh->dev[i];

                if (dev->toread || dev->read || dev->towrite || dev->written ||
                    test_bit(R5_LOCKED, &dev->flags)) {
                        pr_err("sector=%llx i=%d %p %p %p %p %d\n",
                               (unsigned long long)sh->sector, i, dev->toread,
                               dev->read, dev->towrite, dev->written,
                               test_bit(R5_LOCKED, &dev->flags));
                        WARN_ON(1);
                }
                dev->flags = 0;
                raid5_build_block(sh, i, previous);
        }
        if (read_seqcount_retry(&conf->gen_lock, seq))
                goto retry;
        sh->overwrite_disks = 0;
        insert_hash(conf, sh);
        sh->cpu = smp_processor_id();
        set_bit(STRIPE_BATCH_READY, &sh->state);
}

static struct stripe_head *__find_stripe(struct r5conf *conf, sector_t sector,
                                         short generation)
{
        struct stripe_head *sh;

        pr_debug("__find_stripe, sector %llu\n", (unsigned long long)sector);
        hlist_for_each_entry(sh, stripe_hash(conf, sector), hash)
                if (sh->sector == sector && sh->generation == generation)
                        return sh;
        pr_debug("__stripe %llu not in cache\n", (unsigned long long)sector);
        return NULL;
}

/*
 * Need to check if array has failed when deciding whether to:
 *  - start an array
 *  - remove non-faulty devices
 *  - add a spare
 *  - allow a reshape
 * This determination is simple when no reshape is happening.
 * However if there is a reshape, we need to carefully check
 * both the before and after sections.
 * This is because some failed devices may only affect one
 * of the two sections, and some non-in_sync devices may
 * be insync in the section most affected by failed devices.
 */
int raid5_calc_degraded(struct r5conf *conf)
{
        int degraded, degraded2;
        int i;

        rcu_read_lock();
        degraded = 0;
        for (i = 0; i < conf->previous_raid_disks; i++) {
                struct md_rdev *rdev = rcu_dereference(conf->disks[i].rdev);
                if (rdev && test_bit(Faulty, &rdev->flags))
                        rdev = rcu_dereference(conf->disks[i].replacement);
                if (!rdev || test_bit(Faulty, &rdev->flags))
                        degraded++;
                else if (test_bit(In_sync, &rdev->flags))
                        ;
                else
                        /* not in-sync or faulty.
                         * If the reshape increases the number of devices,
                         * this is being recovered by the reshape, so
                         * this 'previous' section is not in_sync.
                         * If the number of devices is being reduced however,
                         * the device can only be part of the array if
                         * we are reverting a reshape, so this section will
                         * be in-sync.
                         */
                        if (conf->raid_disks >= conf->previous_raid_disks)
                                degraded++;
        }
        rcu_read_unlock();
        if (conf->raid_disks == conf->previous_raid_disks)
                return degraded;
        rcu_read_lock();
        degraded2 = 0;
        for (i = 0; i < conf->raid_disks; i++) {
                struct md_rdev *rdev = rcu_dereference(conf->disks[i].rdev);
                if (rdev && test_bit(Faulty, &rdev->flags))
                        rdev = rcu_dereference(conf->disks[i].replacement);
                if (!rdev || test_bit(Faulty, &rdev->flags))
                        degraded2++;
                else if (test_bit(In_sync, &rdev->flags))
                        ;
                else
                        /* not in-sync or faulty.
                         * If reshape increases the number of devices, this
                         * section has already been recovered, else it
                         * almost certainly hasn't.
                         */
                        if (conf->raid_disks <= conf->previous_raid_disks)
                                degraded2++;
        }
        rcu_read_unlock();
        if (degraded2 > degraded)
                return degraded2;
        return degraded;
}

static int has_failed(struct r5conf *conf)
{
        int degraded;

        if (conf->mddev->reshape_position == MaxSector)
                return conf->mddev->degraded > conf->max_degraded;

        degraded = raid5_calc_degraded(conf);
        if (degraded > conf->max_degraded)
                return 1;
        return 0;
}

struct stripe_head *
raid5_get_active_stripe(struct r5conf *conf, sector_t sector,
                        int previous, int noblock, int noquiesce)
{
        struct stripe_head *sh;
        int hash = stripe_hash_locks_hash(sector);
        int inc_empty_inactive_list_flag;

        pr_debug("get_stripe, sector %llu\n", (unsigned long long)sector);

        spin_lock_irq(conf->hash_locks + hash);

        do {
                wait_event_lock_irq(conf->wait_for_quiescent,
                                    conf->quiesce == 0 || noquiesce,
                                    *(conf->hash_locks + hash));
                sh = __find_stripe(conf, sector, conf->generation - previous);
                if (!sh) {
                        if (!test_bit(R5_INACTIVE_BLOCKED, &conf->cache_state)) {
                                sh = get_free_stripe(conf, hash);
                                if (!sh && !test_bit(R5_DID_ALLOC,
                                                     &conf->cache_state))
                                        set_bit(R5_ALLOC_MORE,
                                                &conf->cache_state);
                        }
                        if (noblock && sh == NULL)
                                break;

                        r5c_check_stripe_cache_usage(conf);
                        if (!sh) {
                                set_bit(R5_INACTIVE_BLOCKED,
                                        &conf->cache_state);
                                r5l_wake_reclaim(conf->log, 0);
                                wait_event_lock_irq(
                                        conf->wait_for_stripe,
                                        !list_empty(conf->inactive_list + hash) &&
                                        (atomic_read(&conf->active_stripes)
                                         < (conf->max_nr_stripes * 3 / 4)
                                         || !test_bit(R5_INACTIVE_BLOCKED,
                                                      &conf->cache_state)),
                                        *(conf->hash_locks + hash));
                                clear_bit(R5_INACTIVE_BLOCKED,
                                          &conf->cache_state);
                        } else {
                                init_stripe(sh, sector, previous);
                                atomic_inc(&sh->count);
                        }
                } else if (!atomic_inc_not_zero(&sh->count)) {
                        spin_lock(&conf->device_lock);
                        if (!atomic_read(&sh->count)) {
                                if (!test_bit(STRIPE_HANDLE, &sh->state))
                                        atomic_inc(&conf->active_stripes);
                                BUG_ON(list_empty(&sh->lru) &&
                                       !test_bit(STRIPE_EXPANDING, &sh->state));
                                inc_empty_inactive_list_flag = 0;
                                if (!list_empty(conf->inactive_list + hash))
                                        inc_empty_inactive_list_flag = 1;
                                list_del_init(&sh->lru);
                                if (list_empty(conf->inactive_list + hash) && inc_empty_inactive_list_flag)
                                        atomic_inc(&conf->empty_inactive_list_nr);
                                if (sh->group) {
                                        sh->group->stripes_cnt--;
                                        sh->group = NULL;
                                }
                        }
                        atomic_inc(&sh->count);
                        spin_unlock(&conf->device_lock);
                }
        } while (sh == NULL);

        spin_unlock_irq(conf->hash_locks + hash);
        return sh;
}

static bool is_full_stripe_write(struct stripe_head *sh)
{
        BUG_ON(sh->overwrite_disks > (sh->disks - sh->raid_conf->max_degraded));
        return sh->overwrite_disks == (sh->disks - sh->raid_conf->max_degraded);
}

static void lock_two_stripes(struct stripe_head *sh1, struct stripe_head *sh2)
{
        if (sh1 > sh2) {
                spin_lock_irq(&sh2->stripe_lock);
                spin_lock_nested(&sh1->stripe_lock, 1);
        } else {
                spin_lock_irq(&sh1->stripe_lock);
                spin_lock_nested(&sh2->stripe_lock, 1);
        }
}

static void unlock_two_stripes(struct stripe_head *sh1, struct stripe_head *sh2)
{
        spin_unlock(&sh1->stripe_lock);
        spin_unlock_irq(&sh2->stripe_lock);
}

/* Only freshly new full stripe normal write stripe can be added to a batch list */
static bool stripe_can_batch(struct stripe_head *sh)
{
        struct r5conf *conf = sh->raid_conf;

        if (conf->log || raid5_has_ppl(conf))
                return false;
        return test_bit(STRIPE_BATCH_READY, &sh->state) &&
                !test_bit(STRIPE_BITMAP_PENDING, &sh->state) &&
                is_full_stripe_write(sh);
}

/* we only do back search */
static void stripe_add_to_batch_list(struct r5conf *conf, struct stripe_head *sh)
{
        struct stripe_head *head;
        sector_t head_sector, tmp_sec;
        int hash;
        int dd_idx;
        int inc_empty_inactive_list_flag;

        /* Don't cross chunks, so stripe pd_idx/qd_idx is the same */
        tmp_sec = sh->sector;
        if (!sector_div(tmp_sec, conf->chunk_sectors))
                return;
        head_sector = sh->sector - STRIPE_SECTORS;

        hash = stripe_hash_locks_hash(head_sector);
        spin_lock_irq(conf->hash_locks + hash);
        head = __find_stripe(conf, head_sector, conf->generation);
        if (head && !atomic_inc_not_zero(&head->count)) {
                spin_lock(&conf->device_lock);
                if (!atomic_read(&head->count)) {
                        if (!test_bit(STRIPE_HANDLE, &head->state))
                                atomic_inc(&conf->active_stripes);
                        BUG_ON(list_empty(&head->lru) &&
                               !test_bit(STRIPE_EXPANDING, &head->state));
                        inc_empty_inactive_list_flag = 0;
                        if (!list_empty(conf->inactive_list + hash))
                                inc_empty_inactive_list_flag = 1;
                        list_del_init(&head->lru);
                        if (list_empty(conf->inactive_list + hash) && inc_empty_inactive_list_flag)
                                atomic_inc(&conf->empty_inactive_list_nr);
                        if (head->group) {
                                head->group->stripes_cnt--;
                                head->group = NULL;
                        }
                }
                atomic_inc(&head->count);
                spin_unlock(&conf->device_lock);
        }
        spin_unlock_irq(conf->hash_locks + hash);

        if (!head)
                return;
        if (!stripe_can_batch(head))
                goto out;

        lock_two_stripes(head, sh);
        /* clear_batch_ready clear the flag */
        if (!stripe_can_batch(head) || !stripe_can_batch(sh))
                goto unlock_out;

        if (sh->batch_head)
                goto unlock_out;

        dd_idx = 0;
        while (dd_idx == sh->pd_idx || dd_idx == sh->qd_idx)
                dd_idx++;
        if (head->dev[dd_idx].towrite->bi_opf != sh->dev[dd_idx].towrite->bi_opf ||
            bio_op(head->dev[dd_idx].towrite) != bio_op(sh->dev[dd_idx].towrite))
                goto unlock_out;

        if (head->batch_head) {
                spin_lock(&head->batch_head->batch_lock);
                /* This batch list is already running */
                if (!stripe_can_batch(head)) {
                        spin_unlock(&head->batch_head->batch_lock);
                        goto unlock_out;
                }

                /*
                 * at this point, head's BATCH_READY could be cleared, but we
                 * can still add the stripe to batch list
                 */
                list_add(&sh->batch_list, &head->batch_list);
                spin_unlock(&head->batch_head->batch_lock);

                sh->batch_head = head->batch_head;
        } else {
                head->batch_head = head;
                sh->batch_head = head->batch_head;
                spin_lock(&head->batch_lock);
                list_add_tail(&sh->batch_list, &head->batch_list);
                spin_unlock(&head->batch_lock);
        }

        if (test_and_clear_bit(STRIPE_PREREAD_ACTIVE, &sh->state))
                if (atomic_dec_return(&conf->preread_active_stripes)
                    < IO_THRESHOLD)
                        md_wakeup_thread(conf->mddev->thread);

        if (test_and_clear_bit(STRIPE_BIT_DELAY, &sh->state)) {
                int seq = sh->bm_seq;
                if (test_bit(STRIPE_BIT_DELAY, &sh->batch_head->state) &&
                    sh->batch_head->bm_seq > seq)
                        seq = sh->batch_head->bm_seq;
                set_bit(STRIPE_BIT_DELAY, &sh->batch_head->state);
                sh->batch_head->bm_seq = seq;
        }

        atomic_inc(&sh->count);
unlock_out:
        unlock_two_stripes(head, sh);
out:
        raid5_release_stripe(head);
}

/* Determine if 'data_offset' or 'new_data_offset' should be used
 * in this stripe_head.
 */
static int use_new_offset(struct r5conf *conf, struct stripe_head *sh)
{
        sector_t progress = conf->reshape_progress;
        /* Need a memory barrier to make sure we see the value
         * of conf->generation, or ->data_offset that was set before
         * reshape_progress was updated.
         */
        smp_rmb();
        if (progress == MaxSector)
                return 0;
        if (sh->generation == conf->generation - 1)
                return 0;
        /* We are in a reshape, and this is a new-generation stripe,
         * so use new_data_offset.
         */
        return 1;
}

static void dispatch_bio_list(struct bio_list *tmp)
{
        struct bio *bio;

        while ((bio = bio_list_pop(tmp)))
                generic_make_request(bio);
}

static int cmp_stripe(void *priv, struct list_head *a, struct list_head *b)
{
        const struct r5pending_data *da = list_entry(a,
                                struct r5pending_data, sibling);
        const struct r5pending_data *db = list_entry(b,
                                struct r5pending_data, sibling);
        if (da->sector > db->sector)
                return 1;
        if (da->sector < db->sector)
                return -1;
        return 0;
}

static void dispatch_defer_bios(struct r5conf *conf, int target,
                                struct bio_list *list)
{
        struct r5pending_data *data;
        struct list_head *first, *next = NULL;
        int cnt = 0;

        if (conf->pending_data_cnt == 0)
                return;

        list_sort(NULL, &conf->pending_list, cmp_stripe);

        first = conf->pending_list.next;

        /* temporarily move the head */
        if (conf->next_pending_data)
                list_move_tail(&conf->pending_list,
                                &conf->next_pending_data->sibling);

        while (!list_empty(&conf->pending_list)) {
                data = list_first_entry(&conf->pending_list,
                        struct r5pending_data, sibling);
                if (&data->sibling == first)
                        first = data->sibling.next;
                next = data->sibling.next;

                bio_list_merge(list, &data->bios);
                list_move(&data->sibling, &conf->free_list);
                cnt++;
                if (cnt >= target)
                        break;
        }
        conf->pending_data_cnt -= cnt;
        BUG_ON(conf->pending_data_cnt < 0 || cnt < target);

        if (next != &conf->pending_list)
                conf->next_pending_data = list_entry(next,
                                struct r5pending_data, sibling);
        else
                conf->next_pending_data = NULL;
        /* list isn't empty */
        if (first != &conf->pending_list)
                list_move_tail(&conf->pending_list, first);
}

static void flush_deferred_bios(struct r5conf *conf)
{
        struct bio_list tmp = BIO_EMPTY_LIST;

        if (conf->pending_data_cnt == 0)
                return;

        spin_lock(&conf->pending_bios_lock);
        dispatch_defer_bios(conf, conf->pending_data_cnt, &tmp);
        BUG_ON(conf->pending_data_cnt != 0);
        spin_unlock(&conf->pending_bios_lock);

        dispatch_bio_list(&tmp);
}

static void defer_issue_bios(struct r5conf *conf, sector_t sector,
                                struct bio_list *bios)
{
        struct bio_list tmp = BIO_EMPTY_LIST;
        struct r5pending_data *ent;

        spin_lock(&conf->pending_bios_lock);
        ent = list_first_entry(&conf->free_list, struct r5pending_data,
                                                        sibling);
        list_move_tail(&ent->sibling, &conf->pending_list);
        ent->sector = sector;
        bio_list_init(&ent->bios);
        bio_list_merge(&ent->bios, bios);
        conf->pending_data_cnt++;
        if (conf->pending_data_cnt >= PENDING_IO_MAX)
                dispatch_defer_bios(conf, PENDING_IO_ONE_FLUSH, &tmp);

        spin_unlock(&conf->pending_bios_lock);

        dispatch_bio_list(&tmp);
}

static void
raid5_end_read_request(struct bio *bi);
static void
raid5_end_write_request(struct bio *bi);

static void ops_run_io(struct stripe_head *sh, struct stripe_head_state *s)
{
        struct r5conf *conf = sh->raid_conf;
        int i, disks = sh->disks;
        struct stripe_head *head_sh = sh;
        struct bio_list pending_bios = BIO_EMPTY_LIST;
        bool should_defer;

        might_sleep();

        if (log_stripe(sh, s) == 0)
                return;

        should_defer = conf->batch_bio_dispatch && conf->group_cnt;

        for (i = disks; i--; ) {
                int op, op_flags = 0;
                int replace_only = 0;
                struct bio *bi, *rbi;

                struct md_rdev *rdev, *rrdev = NULL;

                sh = head_sh;
                if (test_and_clear_bit(R5_Wantwrite, &sh->dev[i].flags)) {
                        op = REQ_OP_WRITE;
                        if (test_and_clear_bit(R5_WantFUA, &sh->dev[i].flags))
                                op_flags = REQ_FUA;
                        if (test_bit(R5_Discard, &sh->dev[i].flags))
                                op = REQ_OP_DISCARD;
                } else if (test_and_clear_bit(R5_Wantread, &sh->dev[i].flags))
                        op = REQ_OP_READ;
                else if (test_and_clear_bit(R5_WantReplace,
                                            &sh->dev[i].flags)) {
                        op = REQ_OP_WRITE;
                        replace_only = 1;
                } else
                        continue;
                if (test_and_clear_bit(R5_SyncIO, &sh->dev[i].flags))
                        op_flags |= REQ_SYNC;

again:
                bi = &sh->dev[i].req;
                rbi = &sh->dev[i].rreq; /* For writing to replacement */

                rcu_read_lock();
                rrdev = rcu_dereference(conf->disks[i].replacement);
                smp_mb(); /* Ensure that if rrdev is NULL, rdev won't be */
                rdev = rcu_dereference(conf->disks[i].rdev);
                if (!rdev) {
                        rdev = rrdev;
                        rrdev = NULL;
                }
                if (op_is_write(op)) {
                        if (replace_only)
                                rdev = NULL;
                        if (rdev == rrdev)
                                /* We raced and saw duplicates */
                                rrdev = NULL;
                } else {
                        if (test_bit(R5_ReadRepl, &head_sh->dev[i].flags) && rrdev)
                                rdev = rrdev;
                        rrdev = NULL;
                }

                if (rdev && test_bit(Faulty, &rdev->flags))
                        rdev = NULL;
                if (rdev)
                        atomic_inc(&rdev->nr_pending);
                if (rrdev && test_bit(Faulty, &rrdev->flags))
                        rrdev = NULL;
                if (rrdev)
                        atomic_inc(&rrdev->nr_pending);
                rcu_read_unlock();

                /* We have already checked bad blocks for reads.  Now
                 * need to check for writes.  We never accept write errors
                 * on the replacement, so we don't to check rrdev.
                 */
                while (op_is_write(op) && rdev &&
                       test_bit(WriteErrorSeen, &rdev->flags)) {
                        sector_t first_bad;
                        int bad_sectors;
                        int bad = is_badblock(rdev, sh->sector, STRIPE_SECTORS,
                                              &first_bad, &bad_sectors);
                        if (!bad)
                                break;

                        if (bad < 0) {
                                set_bit(BlockedBadBlocks, &rdev->flags);
                                if (!conf->mddev->external &&
                                    conf->mddev->sb_flags) {
                                        /* It is very unlikely, but we might
                                         * still need to write out the
                                         * bad block log - better give it
                                         * a chance*/
                                        md_check_recovery(conf->mddev);
                                }
                                /*
                                 * Because md_wait_for_blocked_rdev
                                 * will dec nr_pending, we must
                                 * increment it first.
                                 */
                                atomic_inc(&rdev->nr_pending);
                                md_wait_for_blocked_rdev(rdev, conf->mddev);
                        } else {
                                /* Acknowledged bad block - skip the write */
                                rdev_dec_pending(rdev, conf->mddev);
                                rdev = NULL;
                        }
                }

                if (rdev) {
                        if (s->syncing || s->expanding || s->expanded
                            || s->replacing)
                                md_sync_acct(rdev->bdev, STRIPE_SECTORS);

                        set_bit(STRIPE_IO_STARTED, &sh->state);

                        bi->bi_bdev = rdev->bdev;
                        bio_set_op_attrs(bi, op, op_flags);
                        bi->bi_end_io = op_is_write(op)
                                ? raid5_end_write_request
                                : raid5_end_read_request;
                        bi->bi_private = sh;

                        pr_debug("%s: for %llu schedule op %d on disc %d\n",
                                __func__, (unsigned long long)sh->sector,
                                bi->bi_opf, i);
                        atomic_inc(&sh->count);
                        if (sh != head_sh)
                                atomic_inc(&head_sh->count);
                        if (use_new_offset(conf, sh))
                                bi->bi_iter.bi_sector = (sh->sector
                                                 + rdev->new_data_offset);
                        else
                                bi->bi_iter.bi_sector = (sh->sector
                                                 + rdev->data_offset);
                        if (test_bit(R5_ReadNoMerge, &head_sh->dev[i].flags))
                                bi->bi_opf |= REQ_NOMERGE;

                        if (test_bit(R5_SkipCopy, &sh->dev[i].flags))
                                WARN_ON(test_bit(R5_UPTODATE, &sh->dev[i].flags));

                        if (!op_is_write(op) &&
                            test_bit(R5_InJournal, &sh->dev[i].flags))
                                /*
                                 * issuing read for a page in journal, this
                                 * must be preparing for prexor in rmw; read
                                 * the data into orig_page
                                 */
                                sh->dev[i].vec.bv_page = sh->dev[i].orig_page;
                        else
                                sh->dev[i].vec.bv_page = sh->dev[i].page;
                        bi->bi_vcnt = 1;
                        bi->bi_io_vec[0].bv_len = STRIPE_SIZE;
                        bi->bi_io_vec[0].bv_offset = 0;
                        bi->bi_iter.bi_size = STRIPE_SIZE;
                        /*
                         * If this is discard request, set bi_vcnt 0. We don't
                         * want to confuse SCSI because SCSI will replace payload
                         */
                        if (op == REQ_OP_DISCARD)
                                bi->bi_vcnt = 0;
                        if (rrdev)
                                set_bit(R5_DOUBLE_LOCKED, &sh->dev[i].flags);

                        if (conf->mddev->gendisk)
                                trace_block_bio_remap(bdev_get_queue(bi->bi_bdev),
                                                      bi, disk_devt(conf->mddev->gendisk),
                                                      sh->dev[i].sector);
                        if (should_defer && op_is_write(op))
                                bio_list_add(&pending_bios, bi);
                        else
                                generic_make_request(bi);
                }
                if (rrdev) {
                        if (s->syncing || s->expanding || s->expanded
                            || s->replacing)
                                md_sync_acct(rrdev->bdev, STRIPE_SECTORS);

                        set_bit(STRIPE_IO_STARTED, &sh->state);

                        rbi->bi_bdev = rrdev->bdev;
                        bio_set_op_attrs(rbi, op, op_flags);
                        BUG_ON(!op_is_write(op));
                        rbi->bi_end_io = raid5_end_write_request;
                        rbi->bi_private = sh;

                        pr_debug("%s: for %llu schedule op %d on "
                                 "replacement disc %d\n",
                                __func__, (unsigned long long)sh->sector,
                                rbi->bi_opf, i);
                        atomic_inc(&sh->count);
                        if (sh != head_sh)
                                atomic_inc(&head_sh->count);
                        if (use_new_offset(conf, sh))
                                rbi->bi_iter.bi_sector = (sh->sector
                                                  + rrdev->new_data_offset);
                        else
                                rbi->bi_iter.bi_sector = (sh->sector
                                                  + rrdev->data_offset);
                        if (test_bit(R5_SkipCopy, &sh->dev[i].flags))
                                WARN_ON(test_bit(R5_UPTODATE, &sh->dev[i].flags));
                        sh->dev[i].rvec.bv_page = sh->dev[i].page;
                        rbi->bi_vcnt = 1;
                        rbi->bi_io_vec[0].bv_len = STRIPE_SIZE;
                        rbi->bi_io_vec[0].bv_offset = 0;
                        rbi->bi_iter.bi_size = STRIPE_SIZE;
                        /*
                         * If this is discard request, set bi_vcnt 0. We don't
                         * want to confuse SCSI because SCSI will replace payload
                         */
                        if (op == REQ_OP_DISCARD)
                                rbi->bi_vcnt = 0;
                        if (conf->mddev->gendisk)
                                trace_block_bio_remap(bdev_get_queue(rbi->bi_bdev),
                                                      rbi, disk_devt(conf->mddev->gendisk),
                                                      sh->dev[i].sector);
                        if (should_defer && op_is_write(op))
                                bio_list_add(&pending_bios, rbi);
                        else
                                generic_make_request(rbi);
                }
                if (!rdev && !rrdev) {
                        if (op_is_write(op))
                                set_bit(STRIPE_DEGRADED, &sh->state);
                        pr_debug("skip op %d on disc %d for sector %llu\n",
                                bi->bi_opf, i, (unsigned long long)sh->sector);
                        clear_bit(R5_LOCKED, &sh->dev[i].flags);
                        set_bit(STRIPE_HANDLE, &sh->state);
                }

                if (!head_sh->batch_head)
                        continue;
                sh = list_first_entry(&sh->batch_list, struct stripe_head,
                                      batch_list);
                if (sh != head_sh)
                        goto again;
        }

        if (should_defer && !bio_list_empty(&pending_bios))
                defer_issue_bios(conf, head_sh->sector, &pending_bios);
}

static struct dma_async_tx_descriptor *
async_copy_data(int frombio, struct bio *bio, struct page **page,
        sector_t sector, struct dma_async_tx_descriptor *tx,
        struct stripe_head *sh, int no_skipcopy)
{
        struct bio_vec bvl;
        struct bvec_iter iter;
        struct page *bio_page;
        int page_offset;
        struct async_submit_ctl submit;
        enum async_tx_flags flags = 0;

        if (bio->bi_iter.bi_sector >= sector)
                page_offset = (signed)(bio->bi_iter.bi_sector - sector) * 512;
        else
                page_offset = (signed)(sector - bio->bi_iter.bi_sector) * -512;

        if (frombio)
                flags |= ASYNC_TX_FENCE;
        init_async_submit(&submit, flags, tx, NULL, NULL, NULL);

        bio_for_each_segment(bvl, bio, iter) {
                int len = bvl.bv_len;
                int clen;
                int b_offset = 0;

                if (page_offset < 0) {
                        b_offset = -page_offset;
                        page_offset += b_offset;
                        len -= b_offset;
                }

                if (len > 0 && page_offset + len > STRIPE_SIZE)
                        clen = STRIPE_SIZE - page_offset;
                else
                        clen = len;

                if (clen > 0) {
                        b_offset += bvl.bv_offset;
                        bio_page = bvl.bv_page;
                        if (frombio) {
                                if (sh->raid_conf->skip_copy &&
                                    b_offset == 0 && page_offset == 0 &&
                                    clen == STRIPE_SIZE &&
                                    !no_skipcopy)
                                        *page = bio_page;
                                else
                                        tx = async_memcpy(*page, bio_page, page_offset,
                                                  b_offset, clen, &submit);
                        } else
                                tx = async_memcpy(bio_page, *page, b_offset,
                                                  page_offset, clen, &submit);
                }
                /* chain the operations */
                submit.depend_tx = tx;

                if (clen < len) /* hit end of page */
                        break;
                page_offset +=  len;
        }

        return tx;
}

static void ops_complete_biofill(void *stripe_head_ref)
{
        struct stripe_head *sh = stripe_head_ref;
        int i;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        /* clear completed biofills */
        for (i = sh->disks; i--; ) {
                struct r5dev *dev = &sh->dev[i];

                /* acknowledge completion of a biofill operation */
                /* and check if we need to reply to a read request,
                 * new R5_Wantfill requests are held off until
                 * !STRIPE_BIOFILL_RUN
                 */
                if (test_and_clear_bit(R5_Wantfill, &dev->flags)) {
                        struct bio *rbi, *rbi2;

                        BUG_ON(!dev->read);
                        rbi = dev->read;
                        dev->read = NULL;
                        while (rbi && rbi->bi_iter.bi_sector <
                                dev->sector + STRIPE_SECTORS) {
                                rbi2 = r5_next_bio(rbi, dev->sector);
                                bio_endio(rbi);
                                rbi = rbi2;
                        }
                }
        }
        clear_bit(STRIPE_BIOFILL_RUN, &sh->state);

        set_bit(STRIPE_HANDLE, &sh->state);
        raid5_release_stripe(sh);
}

static void ops_run_biofill(struct stripe_head *sh)
{
        struct dma_async_tx_descriptor *tx = NULL;
        struct async_submit_ctl submit;
        int i;

        BUG_ON(sh->batch_head);
        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        for (i = sh->disks; i--; ) {
                struct r5dev *dev = &sh->dev[i];
                if (test_bit(R5_Wantfill, &dev->flags)) {
                        struct bio *rbi;
                        spin_lock_irq(&sh->stripe_lock);
                        dev->read = rbi = dev->toread;
                        dev->toread = NULL;
                        spin_unlock_irq(&sh->stripe_lock);
                        while (rbi && rbi->bi_iter.bi_sector <
                                dev->sector + STRIPE_SECTORS) {
                                tx = async_copy_data(0, rbi, &dev->page,
                                                     dev->sector, tx, sh, 0);
                                rbi = r5_next_bio(rbi, dev->sector);
                        }
                }
        }

        atomic_inc(&sh->count);
        init_async_submit(&submit, ASYNC_TX_ACK, tx, ops_complete_biofill, sh, NULL);
        async_trigger_callback(&submit);
}

static void mark_target_uptodate(struct stripe_head *sh, int target)
{
        struct r5dev *tgt;

        if (target < 0)
                return;

        tgt = &sh->dev[target];
        set_bit(R5_UPTODATE, &tgt->flags);
        BUG_ON(!test_bit(R5_Wantcompute, &tgt->flags));
        clear_bit(R5_Wantcompute, &tgt->flags);
}

static void ops_complete_compute(void *stripe_head_ref)
{
        struct stripe_head *sh = stripe_head_ref;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        /* mark the computed target(s) as uptodate */
        mark_target_uptodate(sh, sh->ops.target);
        mark_target_uptodate(sh, sh->ops.target2);

        clear_bit(STRIPE_COMPUTE_RUN, &sh->state);
        if (sh->check_state == check_state_compute_run)
                sh->check_state = check_state_compute_result;
        set_bit(STRIPE_HANDLE, &sh->state);
        raid5_release_stripe(sh);
}

/* return a pointer to the address conversion region of the scribble buffer */
static addr_conv_t *to_addr_conv(struct stripe_head *sh,
                                 struct raid5_percpu *percpu, int i)
{
        void *addr;

        addr = flex_array_get(percpu->scribble, i);
        return addr + sizeof(struct page *) * (sh->disks + 2);
}

/* return a pointer to the address conversion region of the scribble buffer */
static struct page **to_addr_page(struct raid5_percpu *percpu, int i)
{
        void *addr;

        addr = flex_array_get(percpu->scribble, i);
        return addr;
}

static struct dma_async_tx_descriptor *
ops_run_compute5(struct stripe_head *sh, struct raid5_percpu *percpu)
{
        int disks = sh->disks;
        struct page **xor_srcs = to_addr_page(percpu, 0);
        int target = sh->ops.target;
        struct r5dev *tgt = &sh->dev[target];
        struct page *xor_dest = tgt->page;
        int count = 0;
        struct dma_async_tx_descriptor *tx;
        struct async_submit_ctl submit;
        int i;

        BUG_ON(sh->batch_head);

        pr_debug("%s: stripe %llu block: %d\n",
                __func__, (unsigned long long)sh->sector, target);
        BUG_ON(!test_bit(R5_Wantcompute, &tgt->flags));

        for (i = disks; i--; )
                if (i != target)
                        xor_srcs[count++] = sh->dev[i].page;

        atomic_inc(&sh->count);

        init_async_submit(&submit, ASYNC_TX_FENCE|ASYNC_TX_XOR_ZERO_DST, NULL,
                          ops_complete_compute, sh, to_addr_conv(sh, percpu, 0));
        if (unlikely(count == 1))
                tx = async_memcpy(xor_dest, xor_srcs[0], 0, 0, STRIPE_SIZE, &submit);
        else
                tx = async_xor(xor_dest, xor_srcs, 0, count, STRIPE_SIZE, &submit);

        return tx;
}

/* set_syndrome_sources - populate source buffers for gen_syndrome
 * @srcs - (struct page *) array of size sh->disks
 * @sh - stripe_head to parse
 *
 * Populates srcs in proper layout order for the stripe and returns the
 * 'count' of sources to be used in a call to async_gen_syndrome.  The P
 * destination buffer is recorded in srcs[count] and the Q destination
 * is recorded in srcs[count+1]].
 */
static int set_syndrome_sources(struct page **srcs,
                                struct stripe_head *sh,
                                int srctype)
{
        int disks = sh->disks;
        int syndrome_disks = sh->ddf_layout ? disks : (disks - 2);
        int d0_idx = raid6_d0(sh);
        int count;
        int i;

        for (i = 0; i < disks; i++)
                srcs[i] = NULL;

        count = 0;
        i = d0_idx;
        do {
                int slot = raid6_idx_to_slot(i, sh, &count, syndrome_disks);
                struct r5dev *dev = &sh->dev[i];

                if (i == sh->qd_idx || i == sh->pd_idx ||
                    (srctype == SYNDROME_SRC_ALL) ||
                    (srctype == SYNDROME_SRC_WANT_DRAIN &&
                     (test_bit(R5_Wantdrain, &dev->flags) ||
                      test_bit(R5_InJournal, &dev->flags))) ||
                    (srctype == SYNDROME_SRC_WRITTEN &&
                     (dev->written ||
                      test_bit(R5_InJournal, &dev->flags)))) {
                        if (test_bit(R5_InJournal, &dev->flags))
                                srcs[slot] = sh->dev[i].orig_page;
                        else
                                srcs[slot] = sh->dev[i].page;
                }
                i = raid6_next_disk(i, disks);
        } while (i != d0_idx);

        return syndrome_disks;
}

static struct dma_async_tx_descriptor *
ops_run_compute6_1(struct stripe_head *sh, struct raid5_percpu *percpu)
{
        int disks = sh->disks;
        struct page **blocks = to_addr_page(percpu, 0);
        int target;
        int qd_idx = sh->qd_idx;
        struct dma_async_tx_descriptor *tx;
        struct async_submit_ctl submit;
        struct r5dev *tgt;
        struct page *dest;
        int i;
        int count;

        BUG_ON(sh->batch_head);
        if (sh->ops.target < 0)
                target = sh->ops.target2;
        else if (sh->ops.target2 < 0)
                target = sh->ops.target;
        else
                /* we should only have one valid target */
                BUG();
        BUG_ON(target < 0);
        pr_debug("%s: stripe %llu block: %d\n",
                __func__, (unsigned long long)sh->sector, target);

        tgt = &sh->dev[target];
        BUG_ON(!test_bit(R5_Wantcompute, &tgt->flags));
        dest = tgt->page;

        atomic_inc(&sh->count);

        if (target == qd_idx) {
                count = set_syndrome_sources(blocks, sh, SYNDROME_SRC_ALL);
                blocks[count] = NULL; /* regenerating p is not necessary */
                BUG_ON(blocks[count+1] != dest); /* q should already be set */
                init_async_submit(&submit, ASYNC_TX_FENCE, NULL,
                                  ops_complete_compute, sh,
                                  to_addr_conv(sh, percpu, 0));
                tx = async_gen_syndrome(blocks, 0, count+2, STRIPE_SIZE, &submit);
        } else {
                /* Compute any data- or p-drive using XOR */
                count = 0;
                for (i = disks; i-- ; ) {
                        if (i == target || i == qd_idx)
                                continue;
                        blocks[count++] = sh->dev[i].page;
                }

                init_async_submit(&submit, ASYNC_TX_FENCE|ASYNC_TX_XOR_ZERO_DST,
                                  NULL, ops_complete_compute, sh,
                                  to_addr_conv(sh, percpu, 0));
                tx = async_xor(dest, blocks, 0, count, STRIPE_SIZE, &submit);
        }

        return tx;
}

static struct dma_async_tx_descriptor *
ops_run_compute6_2(struct stripe_head *sh, struct raid5_percpu *percpu)
{
        int i, count, disks = sh->disks;
        int syndrome_disks = sh->ddf_layout ? disks : disks-2;
        int d0_idx = raid6_d0(sh);
        int faila = -1, failb = -1;
        int target = sh->ops.target;
        int target2 = sh->ops.target2;
        struct r5dev *tgt = &sh->dev[target];
        struct r5dev *tgt2 = &sh->dev[target2];
        struct dma_async_tx_descriptor *tx;
        struct page **blocks = to_addr_page(percpu, 0);
        struct async_submit_ctl submit;

        BUG_ON(sh->batch_head);
        pr_debug("%s: stripe %llu block1: %d block2: %d\n",
                 __func__, (unsigned long long)sh->sector, target, target2);
        BUG_ON(target < 0 || target2 < 0);
        BUG_ON(!test_bit(R5_Wantcompute, &tgt->flags));
        BUG_ON(!test_bit(R5_Wantcompute, &tgt2->flags));

        /* we need to open-code set_syndrome_sources to handle the
         * slot number conversion for 'faila' and 'failb'
         */
        for (i = 0; i < disks ; i++)
                blocks[i] = NULL;
        count = 0;
        i = d0_idx;
        do {
                int slot = raid6_idx_to_slot(i, sh, &count, syndrome_disks);

                blocks[slot] = sh->dev[i].page;

                if (i == target)
                        faila = slot;
                if (i == target2)
                        failb = slot;
                i = raid6_next_disk(i, disks);
        } while (i != d0_idx);

        BUG_ON(faila == failb);
        if (failb < faila)
                swap(faila, failb);
        pr_debug("%s: stripe: %llu faila: %d failb: %d\n",
                 __func__, (unsigned long long)sh->sector, faila, failb);

        atomic_inc(&sh->count);

        if (failb == syndrome_disks+1) {
                /* Q disk is one of the missing disks */
                if (faila == syndrome_disks) {
                        /* Missing P+Q, just recompute */
                        init_async_submit(&submit, ASYNC_TX_FENCE, NULL,
                                          ops_complete_compute, sh,
                                          to_addr_conv(sh, percpu, 0));
                        return async_gen_syndrome(blocks, 0, syndrome_disks+2,
                                                  STRIPE_SIZE, &submit);
                } else {
                        struct page *dest;
                        int data_target;
                        int qd_idx = sh->qd_idx;

                        /* Missing D+Q: recompute D from P, then recompute Q */
                        if (target == qd_idx)
                                data_target = target2;
                        else
                                data_target = target;

                        count = 0;
                        for (i = disks; i-- ; ) {
                                if (i == data_target || i == qd_idx)
                                        continue;
                                blocks[count++] = sh->dev[i].page;
                        }
                        dest = sh->dev[data_target].page;
                        init_async_submit(&submit,
                                          ASYNC_TX_FENCE|ASYNC_TX_XOR_ZERO_DST,
                                          NULL, NULL, NULL,
                                          to_addr_conv(sh, percpu, 0));
                        tx = async_xor(dest, blocks, 0, count, STRIPE_SIZE,
                                       &submit);

                        count = set_syndrome_sources(blocks, sh, SYNDROME_SRC_ALL);
                        init_async_submit(&submit, ASYNC_TX_FENCE, tx,
                                          ops_complete_compute, sh,
                                          to_addr_conv(sh, percpu, 0));
                        return async_gen_syndrome(blocks, 0, count+2,
                                                  STRIPE_SIZE, &submit);
                }
        } else {
                init_async_submit(&submit, ASYNC_TX_FENCE, NULL,
                                  ops_complete_compute, sh,
                                  to_addr_conv(sh, percpu, 0));
                if (failb == syndrome_disks) {
                        /* We're missing D+P. */
                        return async_raid6_datap_recov(syndrome_disks+2,
                                                       STRIPE_SIZE, faila,
                                                       blocks, &submit);
                } else {
                        /* We're missing D+D. */
                        return async_raid6_2data_recov(syndrome_disks+2,
                                                       STRIPE_SIZE, faila, failb,
                                                       blocks, &submit);
                }
        }
}

static void ops_complete_prexor(void *stripe_head_ref)
{
        struct stripe_head *sh = stripe_head_ref;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        if (r5c_is_writeback(sh->raid_conf->log))
                /*
                 * raid5-cache write back uses orig_page during prexor.
                 * After prexor, it is time to free orig_page
                 */
                r5c_release_extra_page(sh);
}

static struct dma_async_tx_descriptor *
ops_run_prexor5(struct stripe_head *sh, struct raid5_percpu *percpu,
                struct dma_async_tx_descriptor *tx)
{
        int disks = sh->disks;
        struct page **xor_srcs = to_addr_page(percpu, 0);
        int count = 0, pd_idx = sh->pd_idx, i;
        struct async_submit_ctl submit;

        /* existing parity data subtracted */
        struct page *xor_dest = xor_srcs[count++] = sh->dev[pd_idx].page;

        BUG_ON(sh->batch_head);
        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        for (i = disks; i--; ) {
                struct r5dev *dev = &sh->dev[i];
                /* Only process blocks that are known to be uptodate */
                if (test_bit(R5_InJournal, &dev->flags))
                        xor_srcs[count++] = dev->orig_page;
                else if (test_bit(R5_Wantdrain, &dev->flags))
                        xor_srcs[count++] = dev->page;
        }

        init_async_submit(&submit, ASYNC_TX_FENCE|ASYNC_TX_XOR_DROP_DST, tx,
                          ops_complete_prexor, sh, to_addr_conv(sh, percpu, 0));
        tx = async_xor(xor_dest, xor_srcs, 0, count, STRIPE_SIZE, &submit);

        return tx;
}

static struct dma_async_tx_descriptor *
ops_run_prexor6(struct stripe_head *sh, struct raid5_percpu *percpu,
                struct dma_async_tx_descriptor *tx)
{
        struct page **blocks = to_addr_page(percpu, 0);
        int count;
        struct async_submit_ctl submit;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        count = set_syndrome_sources(blocks, sh, SYNDROME_SRC_WANT_DRAIN);

        init_async_submit(&submit, ASYNC_TX_FENCE|ASYNC_TX_PQ_XOR_DST, tx,
                          ops_complete_prexor, sh, to_addr_conv(sh, percpu, 0));
        tx = async_gen_syndrome(blocks, 0, count+2, STRIPE_SIZE,  &submit);

        return tx;
}

static struct dma_async_tx_descriptor *
ops_run_biodrain(struct stripe_head *sh, struct dma_async_tx_descriptor *tx)
{
        struct r5conf *conf = sh->raid_conf;
        int disks = sh->disks;
        int i;
        struct stripe_head *head_sh = sh;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        for (i = disks; i--; ) {
                struct r5dev *dev;
                struct bio *chosen;

                sh = head_sh;
                if (test_and_clear_bit(R5_Wantdrain, &head_sh->dev[i].flags)) {
                        struct bio *wbi;

again:
                        dev = &sh->dev[i];
                        /*
                         * clear R5_InJournal, so when rewriting a page in
                         * journal, it is not skipped by r5l_log_stripe()
                         */
                        clear_bit(R5_InJournal, &dev->flags);
                        spin_lock_irq(&sh->stripe_lock);
                        chosen = dev->towrite;
                        dev->towrite = NULL;
                        sh->overwrite_disks = 0;
                        BUG_ON(dev->written);
                        wbi = dev->written = chosen;
                        spin_unlock_irq(&sh->stripe_lock);
                        WARN_ON(dev->page != dev->orig_page);

                        while (wbi && wbi->bi_iter.bi_sector <
                                dev->sector + STRIPE_SECTORS) {
                                if (wbi->bi_opf & REQ_FUA)
                                        set_bit(R5_WantFUA, &dev->flags);
                                if (wbi->bi_opf & REQ_SYNC)
                                        set_bit(R5_SyncIO, &dev->flags);
                                if (bio_op(wbi) == REQ_OP_DISCARD)
                                        set_bit(R5_Discard, &dev->flags);
                                else {
                                        tx = async_copy_data(1, wbi, &dev->page,
                                                             dev->sector, tx, sh,
                                                             r5c_is_writeback(conf->log));
                                        if (dev->page != dev->orig_page &&
                                            !r5c_is_writeback(conf->log)) {
                                                set_bit(R5_SkipCopy, &dev->flags);
                                                clear_bit(R5_UPTODATE, &dev->flags);
                                                clear_bit(R5_OVERWRITE, &dev->flags);
                                        }
                                }
                                wbi = r5_next_bio(wbi, dev->sector);
                        }

                        if (head_sh->batch_head) {
                                sh = list_first_entry(&sh->batch_list,
                                                      struct stripe_head,
                                                      batch_list);
                                if (sh == head_sh)
                                        continue;
                                goto again;
                        }
                }
        }

        return tx;
}

static void ops_complete_reconstruct(void *stripe_head_ref)
{
        struct stripe_head *sh = stripe_head_ref;
        int disks = sh->disks;
        int pd_idx = sh->pd_idx;
        int qd_idx = sh->qd_idx;
        int i;
        bool fua = false, sync = false, discard = false;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        for (i = disks; i--; ) {
                fua |= test_bit(R5_WantFUA, &sh->dev[i].flags);
                sync |= test_bit(R5_SyncIO, &sh->dev[i].flags);
                discard |= test_bit(R5_Discard, &sh->dev[i].flags);
        }

        for (i = disks; i--; ) {
                struct r5dev *dev = &sh->dev[i];

                if (dev->written || i == pd_idx || i == qd_idx) {
                        if (!discard && !test_bit(R5_SkipCopy, &dev->flags))
                                set_bit(R5_UPTODATE, &dev->flags);
                        if (fua)
                                set_bit(R5_WantFUA, &dev->flags);
                        if (sync)
                                set_bit(R5_SyncIO, &dev->flags);
                }
        }

        if (sh->reconstruct_state == reconstruct_state_drain_run)
                sh->reconstruct_state = reconstruct_state_drain_result;
        else if (sh->reconstruct_state == reconstruct_state_prexor_drain_run)
                sh->reconstruct_state = reconstruct_state_prexor_drain_result;
        else {
                BUG_ON(sh->reconstruct_state != reconstruct_state_run);
                sh->reconstruct_state = reconstruct_state_result;
        }

        set_bit(STRIPE_HANDLE, &sh->state);
        raid5_release_stripe(sh);
}

static void
ops_run_reconstruct5(struct stripe_head *sh, struct raid5_percpu *percpu,
                     struct dma_async_tx_descriptor *tx)
{
        int disks = sh->disks;
        struct page **xor_srcs;
        struct async_submit_ctl submit;
        int count, pd_idx = sh->pd_idx, i;
        struct page *xor_dest;
        int prexor = 0;
        unsigned long flags;
        int j = 0;
        struct stripe_head *head_sh = sh;
        int last_stripe;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        for (i = 0; i < sh->disks; i++) {
                if (pd_idx == i)
                        continue;
                if (!test_bit(R5_Discard, &sh->dev[i].flags))
                        break;
        }
        if (i >= sh->disks) {
                atomic_inc(&sh->count);
                set_bit(R5_Discard, &sh->dev[pd_idx].flags);
                ops_complete_reconstruct(sh);
                return;
        }
again:
        count = 0;
        xor_srcs = to_addr_page(percpu, j);
        /* check if prexor is active which means only process blocks
         * that are part of a read-modify-write (written)
         */
        if (head_sh->reconstruct_state == reconstruct_state_prexor_drain_run) {
                prexor = 1;
                xor_dest = xor_srcs[count++] = sh->dev[pd_idx].page;
                for (i = disks; i--; ) {
                        struct r5dev *dev = &sh->dev[i];
                        if (head_sh->dev[i].written ||
                            test_bit(R5_InJournal, &head_sh->dev[i].flags))
                                xor_srcs[count++] = dev->page;
                }
        } else {
                xor_dest = sh->dev[pd_idx].page;
                for (i = disks; i--; ) {
                        struct r5dev *dev = &sh->dev[i];
                        if (i != pd_idx)
                                xor_srcs[count++] = dev->page;
                }
        }

        /* 1/ if we prexor'd then the dest is reused as a source
         * 2/ if we did not prexor then we are redoing the parity
         * set ASYNC_TX_XOR_DROP_DST and ASYNC_TX_XOR_ZERO_DST
         * for the synchronous xor case
         */
        last_stripe = !head_sh->batch_head ||
                list_first_entry(&sh->batch_list,
                                 struct stripe_head, batch_list) == head_sh;
        if (last_stripe) {
                flags = ASYNC_TX_ACK |
                        (prexor ? ASYNC_TX_XOR_DROP_DST : ASYNC_TX_XOR_ZERO_DST);

                atomic_inc(&head_sh->count);
                init_async_submit(&submit, flags, tx, ops_complete_reconstruct, head_sh,
                                  to_addr_conv(sh, percpu, j));
        } else {
                flags = prexor ? ASYNC_TX_XOR_DROP_DST : ASYNC_TX_XOR_ZERO_DST;
                init_async_submit(&submit, flags, tx, NULL, NULL,
                                  to_addr_conv(sh, percpu, j));
        }

        if (unlikely(count == 1))
                tx = async_memcpy(xor_dest, xor_srcs[0], 0, 0, STRIPE_SIZE, &submit);
        else
                tx = async_xor(xor_dest, xor_srcs, 0, count, STRIPE_SIZE, &submit);
        if (!last_stripe) {
                j++;
                sh = list_first_entry(&sh->batch_list, struct stripe_head,
                                      batch_list);
                goto again;
        }
}

static void
ops_run_reconstruct6(struct stripe_head *sh, struct raid5_percpu *percpu,
                     struct dma_async_tx_descriptor *tx)
{
        struct async_submit_ctl submit;
        struct page **blocks;
        int count, i, j = 0;
        struct stripe_head *head_sh = sh;
        int last_stripe;
        int synflags;
        unsigned long txflags;

        pr_debug("%s: stripe %llu\n", __func__, (unsigned long long)sh->sector);

        for (i = 0; i < sh->disks; i++) {
                if (sh->pd_idx == i || sh->qd_idx == i)
                        continue;
                if (!test_bit(R5_Discard, &sh->dev[i].flags))
                        break;
        }
        if (i >= sh->disks) {
                atomic_inc(&sh->count);
                set_bit(R5_Discard, &sh->dev[sh->pd_idx].flags);
                set_bit(R5_Discard, &sh->dev[sh->qd_idx].flags);
                ops_complete_reconstruct(sh);
                return;
        }

again:
        blocks = to_addr_page(percpu, j);

        if (sh->reconstruct_state == reconstruct_state_prexor_drain_run) {
                synflags = SYNDROME_SRC_WRITTEN;
                txflags = ASYNC_TX_ACK | ASYNC_TX_PQ_XOR_DST;
        } else {
                synflags = SYNDROME_SRC_ALL;
                txflags = ASYNC_TX_ACK;
        }

        count = set_syndrome_sources(blocks, sh, synflags);
        last_stripe = !head_sh->batch_head ||
                list_first_entry(&sh->batch_list,
                                 struct stripe_head, batch_list) == head_sh;

        if (last_stripe) {
                atomic_inc(&head_sh->count);
                init_async_submit(&submit, txflags, tx, ops_complete_reconstruct,
                                  head_sh, to_addr_conv(sh, percpu, j));
        } else
                init_async_submit(&submit, 0, tx, NULL, NULL,
                                  to_addr_conv(sh, percpu, j));
        tx = async_gen_syndrome(blocks, 0, count+2, STRIPE_SIZE,  &submit);
        if (!last_stripe) {
                j++;
                sh = list_first_entry(&sh->batch_list, struct stripe_head,
                                      batch_list);
                goto again;
        }
}

static void ops_complete_check(void *stripe_head_ref)
{
        struct stripe_head *sh = stripe_head_ref;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        sh->check_state = check_state_check_result;
        set_bit(STRIPE_HANDLE, &sh->state);
        raid5_release_stripe(sh);
}

static void ops_run_check_p(struct stripe_head *sh, struct raid5_percpu *percpu)
{
        int disks = sh->disks;
        int pd_idx = sh->pd_idx;

        int qd_idx = sh->qd_idx;
        struct page *xor_dest;
        struct page **xor_srcs = to_addr_page(percpu, 0);
        struct dma_async_tx_descriptor *tx;
        struct async_submit_ctl submit;
        int count;
        int i;

        pr_debug("%s: stripe %llu\n", __func__,
                (unsigned long long)sh->sector);

        BUG_ON(sh->batch_head);
        count = 0;
        xor_dest = sh->dev[pd_idx].page;
        xor_srcs[count++] = xor_dest;
        for (i = disks; i--; ) {
                if (i == pd_idx || i == qd_idx)
                        continue;
                xor_srcs[count++] = sh->dev[i].page;
        }

        init_async_submit(&submit, 0, NULL, NULL, NULL,
                          to_addr_conv(sh, percpu, 0));
        tx = async_xor_val(xor_dest, xor_srcs, 0, count, STRIPE_SIZE,
                           &sh->ops.zero_sum_result, &submit);

        atomic_inc(&sh->count);
        init_async_submit(&submit, ASYNC_TX_ACK, tx, ops_complete_check, sh, NULL);
        tx = async_trigger_callback(&submit);
}

static void ops_run_check_pq(struct stripe_head *sh, struct raid5_percpu *percpu, int checkp)
{
        struct page **srcs = to_addr_page(percpu, 0);
        struct async_submit_ctl submit;
        int count;

        pr_debug("%s: stripe %llu checkp: %d\n", __func__,
                (unsigned long long)sh->sector, checkp);

        BUG_ON(sh->batch_head);
        count = set_syndrome_sources(srcs, sh, SYNDROME_SRC_ALL);
        if (!checkp)
                srcs[count] = NULL;

        atomic_inc(&sh->count);
        init_async_submit(&submit, ASYNC_TX_ACK, NULL, ops_complete_check,
                          sh, to_addr_conv(sh, percpu, 0));
        async_syndrome_val(srcs, 0, count+2, STRIPE_SIZE,
                           &sh->ops.zero_sum_result, percpu->spare_page, &submit);
}

static void raid_run_ops(struct stripe_head *sh, unsigned long ops_request)
{
        int overlap_clear = 0, i, disks = sh->disks;
        struct dma_async_tx_descriptor *tx = NULL;
        struct r5conf *conf = sh->raid_conf;
        int level = conf->level;
        struct raid5_percpu *percpu;
        unsigned long cpu;

        cpu = get_cpu();
        percpu = per_cpu_ptr(conf->percpu, cpu);
        if (test_bit(STRIPE_OP_BIOFILL, &ops_request)) {
                ops_run_biofill(sh);
                overlap_clear++;
        }

        if (test_bit(STRIPE_OP_COMPUTE_BLK, &ops_request)) {
                if (level < 6)
                        tx = ops_run_compute5(sh, percpu);
                else {
                        if (sh->ops.target2 < 0 || sh->ops.target < 0)
                                tx = ops_run_compute6_1(sh, percpu);
                        else
                                tx = ops_run_compute6_2(sh, percpu);
                }
                /* terminate the chain if reconstruct is not set to be run */
                if (tx && !test_bit(STRIPE_OP_RECONSTRUCT, &ops_request))
                        async_tx_ack(tx);
        }

        if (test_bit(STRIPE_OP_PREXOR, &ops_request)) {
                if (level < 6)
                        tx = ops_run_prexor5(sh, percpu, tx);
                else
                        tx = ops_run_prexor6(sh, percpu, tx);
        }

        if (test_bit(STRIPE_OP_PARTIAL_PARITY, &ops_request))
                tx = ops_run_partial_parity(sh, percpu, tx);

        if (test_bit(STRIPE_OP_BIODRAIN, &ops_request)) {
                tx = ops_run_biodrain(sh, tx);
                overlap_clear++;
        }

        if (test_bit(STRIPE_OP_RECONSTRUCT, &ops_request)) {
                if (level < 6)
                        ops_run_reconstruct5(sh, percpu, tx);
                else
                        ops_run_reconstruct6(sh, percpu, tx);
        }

        if (test_bit(STRIPE_OP_CHECK, &ops_request)) {
                if (sh->check_state == check_state_run)
                        ops_run_check_p(sh, percpu);
                else if (sh->check_state == check_state_run_q)
                        ops_run_check_pq(sh, percpu, 0);
                else if (sh->check_state == check_state_run_pq)
                        ops_run_check_pq(sh, percpu, 1);
                else
                        BUG();
        }

        if (overlap_clear && !sh->batch_head)
                for (i = disks; i--; ) {
                        struct r5dev *dev = &sh->dev[i];
                        if (test_and_clear_bit(R5_Overlap, &dev->flags))
                                wake_up(&sh->raid_conf->wait_for_overlap);
                }
        put_cpu();
}

static void free_stripe(struct kmem_cache *sc, struct stripe_head *sh)
{
        if (sh->ppl_page)
                __free_page(sh->ppl_page);
        kmem_cache_free(sc, sh);
}

static struct stripe_head *alloc_stripe(struct kmem_cache *sc, gfp_t gfp,
        int disks, struct r5conf *conf)
{
        struct stripe_head *sh;
        int i;

        sh = kmem_cache_zalloc(sc, gfp);
        if (sh) {
                spin_lock_init(&sh->stripe_lock);
                spin_lock_init(&sh->batch_lock);
                INIT_LIST_HEAD(&sh->batch_list);
                INIT_LIST_HEAD(&sh->lru);
                INIT_LIST_HEAD(&sh->r5c);
                INIT_LIST_HEAD(&sh->log_list);
                atomic_set(&sh->count, 1);
                sh->raid_conf = conf;
                sh->log_start = MaxSector;
                for (i = 0; i < disks; i++) {
                        struct r5dev *dev = &sh->dev[i];

                        bio_init(&dev->req, &dev->vec, 1);
                        bio_init(&dev->rreq, &dev->rvec, 1);
                }

                if (raid5_has_ppl(conf)) {
                        sh->ppl_page = alloc_page(gfp);
                        if (!sh->ppl_page) {
                                free_stripe(sc, sh);
                                sh = NULL;
                        }
                }
        }
        return sh;
}
static int grow_one_stripe(struct r5conf *conf, gfp_t gfp)
{
        struct stripe_head *sh;

        sh = alloc_stripe(conf->slab_cache, gfp, conf->pool_size, conf);
        if (!sh)
                return 0;

        if (grow_buffers(sh, gfp)) {
                shrink_buffers(sh);
                free_stripe(conf->slab_cache, sh);
                return 0;
        }
        sh->hash_lock_index =
                conf->max_nr_stripes % NR_STRIPE_HASH_LOCKS;
        /* we just created an active stripe so... */
        atomic_inc(&conf->active_stripes);

        raid5_release_stripe(sh);
        conf->max_nr_stripes++;
        return 1;
}

static int grow_stripes(struct r5conf *conf, int num)
{
        struct kmem_cache *sc;
        int devs = max(conf->raid_disks, conf->previous_raid_disks);

        if (conf->mddev->gendisk)
                sprintf(conf->cache_name[0],
                        "raid%d-%s", conf->level, mdname(conf->mddev));
        else
                sprintf(conf->cache_name[0],
                        "raid%d-%p", conf->level, conf->mddev);
        sprintf(conf->cache_name[1], "%s-alt", conf->cache_name[0]);

        conf->active_name = 0;
        sc = kmem_cache_create(conf->cache_name[conf->active_name],
                               sizeof(struct stripe_head)+(devs-1)*sizeof(struct r5dev),
                               0, 0, NULL);
        if (!sc)
                return 1;
        conf->slab_cache = sc;
        conf->pool_size = devs;
        while (num--)
                if (!grow_one_stripe(conf, GFP_KERNEL))
                        return 1;

        return 0;
}

/**
 * scribble_len - return the required size of the scribble region
 * @num - total number of disks in the array
 *
 * The size must be enough to contain:
 * 1/ a struct page pointer for each device in the array +2
 * 2/ room to convert each entry in (1) to its corresponding dma
 *    (dma_map_page()) or page (page_address()) address.
 *
 * Note: the +2 is for the destination buffers of the ddf/raid6 case where we
 * calculate over all devices (not just the data blocks), using zeros in place
 * of the P and Q blocks.
 */
static struct flex_array *scribble_alloc(int num, int cnt, gfp_t flags)
{
        struct flex_array *ret;
        size_t len;

        len = sizeof(struct page *) * (num+2) + sizeof(addr_conv_t) * (num+2);
        ret = flex_array_alloc(len, cnt, flags);
        if (!ret)
                return NULL;
        /* always prealloc all elements, so no locking is required */
        if (flex_array_prealloc(ret, 0, cnt, flags)) {
                flex_array_free(ret);
                return NULL;
        }
        return ret;
}

static int resize_chunks(struct r5conf *conf, int new_disks, int new_sectors)
{
        unsigned long cpu;
        int err = 0;

        /*
         * Never shrink. And mddev_suspend() could deadlock if this is called
         * from raid5d. In that case, scribble_disks and scribble_sectors
         * should equal to new_disks and new_sectors
         */
        if (conf->scribble_disks >= new_disks &&
            conf->scribble_sectors >= new_sectors)
                return 0;
        mddev_suspend(conf->mddev);
        get_online_cpus();
        for_each_present_cpu(cpu) {
                struct raid5_percpu *percpu;
                struct flex_array *scribble;

                percpu = per_cpu_ptr(conf->percpu, cpu);
                scribble = scribble_alloc(new_disks,
                                          new_sectors / STRIPE_SECTORS,
                                          GFP_NOIO);

                if (scribble) {
                        flex_array_free(percpu->scribble);
                        percpu->scribble = scribble;
                } else {
                        err = -ENOMEM;
                        break;
                }
        }
        put_online_cpus();
        mddev_resume(conf->mddev);
        if (!err) {
                conf->scribble_disks = new_disks;
                conf->scribble_sectors = new_sectors;
        }
        return err;
}

static int resize_stripes(struct r5conf *conf, int newsize)
{
        /* Make all the stripes able to hold 'newsize' devices.
         * New slots in each stripe get 'page' set to a new page.
         *
         * This happens in stages:
         * 1/ create a new kmem_cache and allocate the required number of
         *    stripe_heads.
         * 2/ gather all the old stripe_heads and transfer the pages across
         *    to the new stripe_heads.  This will have the side effect of
         *    freezing the array as once all stripe_heads have been collected,
         *    no IO will be possible.  Old stripe heads are freed once their
         *    pages have been transferred over, and the old kmem_cache is
         *    freed when all stripes are done.
         * 3/ reallocate conf->disks to be suitable bigger.  If this fails,
         *    we simple return a failure status - no need to clean anything up.
         * 4/ allocate new pages for the new slots in the new stripe_heads.
         *    If this fails, we don't bother trying the shrink the
         *    stripe_heads down again, we just leave them as they are.
         *    As each stripe_head is processed the new one is released into
         *    active service.
         *
         * Once step2 is started, we cannot afford to wait for a write,
         * so we use GFP_NOIO allocations.
         */
        struct stripe_head *osh, *nsh;
        LIST_HEAD(newstripes);
        struct disk_info *ndisks;
        int err = 0;
        struct kmem_cache *sc;
        int i;
        int hash, cnt;

        md_allow_write(conf->mddev);

        /* Step 1 */
        sc = kmem_cache_create(conf->cache_name[1-conf->active_name],
                               sizeof(struct stripe_head)+(newsize-1)*sizeof(struct r5dev),
                               0, 0, NULL);
        if (!sc)
                return -ENOMEM;

        /* Need to ensure auto-resizing doesn't interfere */
        mutex_lock(&conf->cache_size_mutex);

        for (i = conf->max_nr_stripes; i; i--) {
                nsh = alloc_stripe(sc, GFP_KERNEL, newsize, conf);
                if (!nsh)
                        break;

                list_add(&nsh->lru, &newstripes);
        }
        if (i) {
                /* didn't get enough, give up */
                while (!list_empty(&newstripes)) {
                        nsh = list_entry(newstripes.next, struct stripe_head, lru);
                        list_del(&nsh->lru);
                        free_stripe(sc, nsh);
                }
                kmem_cache_destroy(sc);
                mutex_unlock(&conf->cache_size_mutex);
                return -ENOMEM;
        }
        /* Step 2 - Must use GFP_NOIO now.
         * OK, we have enough stripes, start collecting inactive
         * stripes and copying them over
         */
        hash = 0;
        cnt = 0;
        list_for_each_entry(nsh, &newstripes, lru) {
                lock_device_hash_lock(conf, hash);
                wait_event_cmd(conf->wait_for_stripe,
                                    !list_empty(conf->inactive_list + hash),
                                    unlock_device_hash_lock(conf, hash),
                                    lock_device_hash_lock(conf, hash));
                osh = get_free_stripe(conf, hash);
                unlock_device_hash_lock(conf, hash);

                for(i=0; i<conf->pool_size; i++) {
                        nsh->dev[i].page = osh->dev[i].page;
                        nsh->dev[i].orig_page = osh->dev[i].page;
                }
                nsh->hash_lock_index = hash;
                free_stripe(conf->slab_cache, osh);
                cnt++;
                if (cnt >= conf->max_nr_stripes / NR_STRIPE_HASH_LOCKS +
                    !!((conf->max_nr_stripes % NR_STRIPE_HASH_LOCKS) > hash)) {
                        hash++;
                        cnt = 0;
                }
        }
        kmem_cache_destroy(conf->slab_cache);

        /* Step 3.
         * At this point, we are holding all the stripes so the array
         * is completely stalled, so now is a good time to resize
         * conf->disks and the scribble region
         */
        ndisks = kzalloc(newsize * sizeof(struct disk_info), GFP_NOIO);
        if (ndisks) {
                for (i = 0; i < conf->pool_size; i++)
                        ndisks[i] = conf->disks[i];

                for (i = conf->pool_size; i < newsize; i++) {
                        ndisks[i].extra_page = alloc_page(GFP_NOIO);
                        if (!ndisks[i].extra_page)
                                err = -ENOMEM;
                }

                if (err) {
                        for (i = conf->pool_size; i < newsize; i++)
                                if (ndisks[i].extra_page)
                                        put_page(ndisks[i].extra_page);
                        kfree(ndisks);
                } else {
                        kfree(conf->disks);
                        conf->disks = ndisks;
                }
        } else
                err = -ENOMEM;

        mutex_unlock(&conf->cache_size_mutex);

        conf->slab_cache = sc;
        conf->active_name = 1-conf->active_name;

        /* Step 4, return new stripes to service */
        while(!list_empty(&newstripes)) {
                nsh = list_entry(newstripes.next, struct stripe_head, lru);
                list_del_init(&nsh->lru);

                for (i=conf->raid_disks; i < newsize; i++)
                        if (nsh->dev[i].page == NULL) {
                                struct page *p = alloc_page(GFP_NOIO);
                                nsh->dev[i].page = p;
                                nsh->dev[i].orig_page = p;
                                if (!p)
                                        err = -ENOMEM;
                        }
                raid5_release_stripe(nsh);
        }
        /* critical section pass, GFP_NOIO no longer needed */

        if (!err)
                conf->pool_size = newsize;
        return err;
}

static int drop_one_stripe(struct r5conf *conf)
{
        struct stripe_head *sh;
        int hash = (conf->max_nr_stripes - 1) & STRIPE_HASH_LOCKS_MASK;

        spin_lock_irq(conf->hash_locks + hash);
        sh = get_free_stripe(conf, hash);
        spin_unlock_irq(conf->hash_locks + hash);
        if (!sh)
                return 0;
        BUG_ON(atomic_read(&sh->count));
        shrink_buffers(sh);
        free_stripe(conf->slab_cache, sh);
        atomic_dec(&conf->active_stripes);
        conf->max_nr_stripes--;
        return 1;
}

static void shrink_stripes(struct r5conf *conf)
{
        while (conf->max_nr_stripes &&
               drop_one_stripe(conf))
                ;

        kmem_cache_destroy(conf->slab_cache);
        conf->slab_cache = NULL;
}

static void raid5_end_read_request(struct bio * bi)
{
        struct stripe_head *sh = bi->bi_private;
        struct r5conf *conf = sh->raid_conf;
        int disks = sh->disks, i;
        char b[BDEVNAME_SIZE];
        struct md_rdev *rdev = NULL;
        sector_t s;

        for (i=0 ; i<disks; i++)
                if (bi == &sh->dev[i].req)
                        break;

        pr_debug("end_read_request %llu/%d, count: %d, error %d.\n",
                (unsigned long long)sh->sector, i, atomic_read(&sh->count),
                bi->bi_error);
        if (i == disks) {
                bio_reset(bi);
                BUG();
                return;
        }
        if (test_bit(R5_ReadRepl, &sh->dev[i].flags))
                /* If replacement finished while this request was outstanding,
                 * 'replacement' might be NULL already.
                 * In that case it moved down to 'rdev'.
                 * rdev is not removed until all requests are finished.
                 */
                rdev = conf->disks[i].replacement;
        if (!rdev)
                rdev = conf->disks[i].rdev;

        if (use_new_offset(conf, sh))
                s = sh->sector + rdev->new_data_offset;
        else
                s = sh->sector + rdev->data_offset;
        if (!bi->bi_error) {
                set_bit(R5_UPTODATE, &sh->dev[i].flags);
                if (test_bit(R5_ReadError, &sh->dev[i].flags)) {
                        /* Note that this cannot happen on a
                         * replacement device.  We just fail those on
                         * any error
                         */
                        pr_info_ratelimited(
                                "md/raid:%s: read error corrected (%lu sectors at %llu on %s)\n",
                                mdname(conf->mddev), STRIPE_SECTORS,
                                (unsigned long long)s,
                                bdevname(rdev->bdev, b));
                        atomic_add(STRIPE_SECTORS, &rdev->corrected_errors);
                        clear_bit(R5_ReadError, &sh->dev[i].flags);
                        clear_bit(R5_ReWrite, &sh->dev[i].flags);
                } else if (test_bit(R5_ReadNoMerge, &sh->dev[i].flags))
                        clear_bit(R5_ReadNoMerge, &sh->dev[i].flags);

                if (test_bit(R5_InJournal, &sh->dev[i].flags))
                        /*
                         * end read for a page in journal, this
                         * must be preparing for prexor in rmw
                         */
                        set_bit(R5_OrigPageUPTDODATE, &sh->dev[i].flags);

                if (atomic_read(&rdev->read_errors))
                        atomic_set(&rdev->read_errors, 0);
        } else {
                const char *bdn = bdevname(rdev->bdev, b);
                int retry = 0;
                int set_bad = 0;

                clear_bit(R5_UPTODATE, &sh->dev[i].flags);
                atomic_inc(&rdev->read_errors);
                if (test_bit(R5_ReadRepl, &sh->dev[i].flags))
                        pr_warn_ratelimited(
                                "md/raid:%s: read error on replacement device (sector %llu on %s).\n",
                                mdname(conf->mddev),
                                (unsigned long long)s,
                                bdn);
                else if (conf->mddev->degraded >= conf->max_degraded) {
                        set_bad = 1;
                        pr_warn_ratelimited(
                                "md/raid:%s: read error not correctable (sector %llu on %s).\n",
                                mdname(conf->mddev),
                                (unsigned long long)s,
                                bdn);
                } else if (test_bit(R5_ReWrite, &sh->dev[i].flags)) {
                        /* Oh, no!!! */
                        set_bad = 1;
                        pr_warn_ratelimited(
                                "md/raid:%s: read error NOT corrected!! (sector %llu on %s).\n",
                                mdname(conf->mddev),
                                (unsigned long long)s,
                                bdn);
                } else if (atomic_read(&rdev->read_errors)
                         > conf->max_nr_stripes)
                        pr_warn("md/raid:%s: Too many read errors, failing device %s.\n",
                               mdname(conf->mddev), bdn);
                else
                        retry = 1;
                if (set_bad && test_bit(In_sync, &rdev->flags)
                    && !test_bit(R5_ReadNoMerge, &sh->dev[i].flags))
                        retry = 1;
                if (retry)
                        if (test_bit(R5_ReadNoMerge, &sh->dev[i].flags)) {
                                set_bit(R5_ReadError, &sh->dev[i].flags);
                                clear_bit(R5_ReadNoMerge, &sh->dev[i].flags);
                        } else
                                set_bit(R5_ReadNoMerge, &sh->dev[i].flags);
                else {
                        clear_bit(R5_ReadError, &sh->dev[i].flags);
                        clear_bit(R5_ReWrite, &sh->dev[i].flags);
                        if (!(set_bad
                              && test_bit(In_sync, &rdev->flags)
                              && rdev_set_badblocks(
                                      rdev, sh->sector, STRIPE_SECTORS, 0)))
                                md_error(conf->mddev, rdev);
                }
        }
        rdev_dec_pending(rdev, conf->mddev);
        bio_reset(bi);
        clear_bit(R5_LOCKED, &sh->dev[i].flags);
        set_bit(STRIPE_HANDLE, &sh->state);
        raid5_release_stripe(sh);
}

static void raid5_end_write_request(struct bio *bi)
{
        struct stripe_head *sh = bi->bi_private;
        struct r5conf *conf = sh->raid_conf;
        int disks = sh->disks, i;
        struct md_rdev *uninitialized_var(rdev);
        sector_t first_bad;
        int bad_sectors;
        int replacement = 0;

        for (i = 0 ; i < disks; i++) {
                if (bi == &sh->dev[i].req) {
                        rdev = conf->disks[i].rdev;
                        break;
                }
                if (bi == &sh->dev[i].rreq) {
                        rdev = conf->disks[i].replacement;
                        if (rdev)
                                replacement = 1;
                        else
                                /* rdev was removed and 'replacement'
                                 * replaced it.  rdev is not removed
                                 * until all requests are finished.
                                 */
                                rdev = conf->disks[i].rdev;
                        break;
                }
        }
        pr_debug("end_write_request %llu/%d, count %d, error: %d.\n",
                (unsigned long long)sh->sector, i, atomic_read(&sh->count),
                bi->bi_error);
        if (i == disks) {
                bio_reset(bi);
                BUG();
                return;
        }

        if (replacement) {
                if (bi->bi_error)
                        md_error(conf->mddev, rdev);
                else if (is_badblock(rdev, sh->sector,
                                     STRIPE_SECTORS,
                                     &first_bad, &bad_sectors))
                        set_bit(R5_MadeGoodRepl, &sh->dev[i].flags);
        } else {
                if (bi->bi_error) {
                        set_bit(STRIPE_DEGRADED, &sh->state);
                        set_bit(WriteErrorSeen, &rdev->flags);
                        set_bit(R5_WriteError, &sh->dev[i].flags);
                        if (!test_and_set_bit(WantReplacement, &rdev->flags))
                                set_bit(MD_RECOVERY_NEEDED,
                                        &rdev->mddev->recovery);
                } else if (is_badblock(rdev, sh->sector,
                                       STRIPE_SECTORS,
                                       &first_bad, &bad_sectors)) {
                        set_bit(R5_MadeGood, &sh->dev[i].flags);
                        if (test_bit(R5_ReadError, &sh->dev[i].flags))
                                /* That was a successful write so make
                                 * sure it looks like we already did
                                 * a re-write.
                                 */
                                set_bit(R5_ReWrite, &sh->dev[i].flags);
                }
        }
        rdev_dec_pending(rdev, conf->mddev);

        if (sh->batch_head && bi->bi_error && !replacement)
                set_bit(STRIPE_BATCH_ERR, &sh->batch_head->state);

        bio_reset(bi);
        if (!test_and_clear_bit(R5_DOUBLE_LOCKED, &sh->dev[i].flags))
                clear_bit(R5_LOCKED, &sh->dev[i].flags);
        set_bit(STRIPE_HANDLE, &sh->state);
        raid5_release_stripe(sh);

        if (sh->batch_head && sh != sh->batch_head)
                raid5_release_stripe(sh->batch_head);
}

static void raid5_build_block(struct stripe_head *sh, int i, int previous)
{
        struct r5dev *dev = &sh->dev[i];

        dev->flags = 0;
        dev->sector = raid5_compute_blocknr(sh, i, previous);
}

static void raid5_error(struct mddev *mddev, struct md_rdev *rdev)
{
        char b[BDEVNAME_SIZE];
        struct r5conf *conf = mddev->private;
        unsigned long flags;
        pr_debug("raid456: error called\n");

        spin_lock_irqsave(&conf->device_lock, flags);
        clear_bit(In_sync, &rdev->flags);
        mddev->degraded = raid5_calc_degraded(conf);
        spin_unlock_irqrestore(&conf->device_lock, flags);
        set_bit(MD_RECOVERY_INTR, &mddev->recovery);

        set_bit(Blocked, &rdev->flags);
        set_bit(Faulty, &rdev->flags);
        set_mask_bits(&mddev->sb_flags, 0,
                      BIT(MD_SB_CHANGE_DEVS) | BIT(MD_SB_CHANGE_PENDING));
        pr_crit("md/raid:%s: Disk failure on %s, disabling device.\n"
                "md/raid:%s: Operation continuing on %d devices.\n",
                mdname(mddev),
                bdevname(rdev->bdev, b),
                mdname(mddev),
                conf->raid_disks - mddev->degraded);
        r5c_update_on_rdev_error(mddev, rdev);
}

/*
 * Input: a 'big' sector number,
 * Output: index of the data and parity disk, and the sector # in them.
 */
sector_t raid5_compute_sector(struct r5conf *conf, sector_t r_sector,
                              int previous, int *dd_idx,
                              struct stripe_head *sh)
{
        sector_t stripe, stripe2;
        sector_t chunk_number;
        unsigned int chunk_offset;
        int pd_idx, qd_idx;
        int ddf_layout = 0;
        sector_t new_sector;
        int algorithm = previous ? conf->prev_algo
                                 : conf->algorithm;
        int sectors_per_chunk = previous ? conf->prev_chunk_sectors
                                         : conf->chunk_sectors;
        int raid_disks = previous ? conf->previous_raid_disks
                                  : conf->raid_disks;
        int data_disks = raid_disks - conf->max_degraded;

        /* First compute the information on this sector */

        /*
         * Compute the chunk number and the sector offset inside the chunk
         */
        chunk_offset = sector_div(r_sector, sectors_per_chunk);
        chunk_number = r_sector;

        /*
         * Compute the stripe number
         */
        stripe = chunk_number;
        *dd_idx = sector_div(stripe, data_disks);
        stripe2 = stripe;
        /*
         * Select the parity disk based on the user selected algorithm.
         */
        pd_idx = qd_idx = -1;
        switch(conf->level) {
        case 4:
                pd_idx = data_disks;
                break;
        case 5:
                switch (algorithm) {
                case ALGORITHM_LEFT_ASYMMETRIC:
                        pd_idx = data_disks - sector_div(stripe2, raid_disks);
                        if (*dd_idx >= pd_idx)
                                (*dd_idx)++;
                        break;
                case ALGORITHM_RIGHT_ASYMMETRIC:
                        pd_idx = sector_div(stripe2, raid_disks);
                        if (*dd_idx >= pd_idx)
                                (*dd_idx)++;
                        break;
                case ALGORITHM_LEFT_SYMMETRIC:
                        pd_idx = data_disks - sector_div(stripe2, raid_disks);
                        *dd_idx = (pd_idx + 1 + *dd_idx) % raid_disks;
                        break;
                case ALGORITHM_RIGHT_SYMMETRIC:
                        pd_idx = sector_div(stripe2, raid_disks);
                        *dd_idx = (pd_idx + 1 + *dd_idx) % raid_disks;
                        break;
                case ALGORITHM_PARITY_0:
                        pd_idx = 0;
                        (*dd_idx)++;
                        break;
                case ALGORITHM_PARITY_N:
                        pd_idx = data_disks;
                        break;
                default:
                        BUG();
                }
                break;
        case 6:

                switch (algorithm) {
                case ALGORITHM_LEFT_ASYMMETRIC:
                        pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
                        qd_idx = pd_idx + 1;
                        if (pd_idx == raid_disks-1) {
                                (*dd_idx)++;    /* Q D D D P */
                                qd_idx = 0;
                        } else if (*dd_idx >= pd_idx)
                                (*dd_idx) += 2; /* D D P Q D */
                        break;
                case ALGORITHM_RIGHT_ASYMMETRIC:
                        pd_idx = sector_div(stripe2, raid_disks);
                        qd_idx = pd_idx + 1;
                        if (pd_idx == raid_disks-1) {
                                (*dd_idx)++;    /* Q D D D P */
                                qd_idx = 0;
                        } else if (*dd_idx >= pd_idx)
                                (*dd_idx) += 2; /* D D P Q D */
                        break;
                case ALGORITHM_LEFT_SYMMETRIC:
                        pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
                        qd_idx = (pd_idx + 1) % raid_disks;
                        *dd_idx = (pd_idx + 2 + *dd_idx) % raid_disks;
                        break;
                case ALGORITHM_RIGHT_SYMMETRIC:
                        pd_idx = sector_div(stripe2, raid_disks);
                        qd_idx = (pd_idx + 1) % raid_disks;
                        *dd_idx = (pd_idx + 2 + *dd_idx) % raid_disks;
                        break;

                case ALGORITHM_PARITY_0:
                        pd_idx = 0;
                        qd_idx = 1;
                        (*dd_idx) += 2;
                        break;
                case ALGORITHM_PARITY_N:
                        pd_idx = data_disks;
                        qd_idx = data_disks + 1;
                        break;

                case ALGORITHM_ROTATING_ZERO_RESTART:
                        /* Exactly the same as RIGHT_ASYMMETRIC, but or
                         * of blocks for computing Q is different.
                         */
                        pd_idx = sector_div(stripe2, raid_disks);
                        qd_idx = pd_idx + 1;
                        if (pd_idx == raid_disks-1) {
                                (*dd_idx)++;    /* Q D D D P */
                                qd_idx = 0;
                        } else if (*dd_idx >= pd_idx)
                                (*dd_idx) += 2; /* D D P Q D */
                        ddf_layout = 1;
                        break;

                case ALGORITHM_ROTATING_N_RESTART:
                        /* Same a left_asymmetric, by first stripe is
                         * D D D P Q  rather than
                         * Q D D D P
                         */
                        stripe2 += 1;
                        pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
                        qd_idx = pd_idx + 1;
                        if (pd_idx == raid_disks-1) {
                                (*dd_idx)++;    /* Q D D D P */
                                qd_idx = 0;
                        } else if (*dd_idx >= pd_idx)
                                (*dd_idx) += 2; /* D D P Q D */
                        ddf_layout = 1;
                        break;

                case ALGORITHM_ROTATING_N_CONTINUE:
                        /* Same as left_symmetric but Q is before P */
                        pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
                        qd_idx = (pd_idx + raid_disks - 1) % raid_disks;
                        *dd_idx = (pd_idx + 1 + *dd_idx) % raid_disks;
                        ddf_layout = 1;
                        break;

                case ALGORITHM_LEFT_ASYMMETRIC_6:
                        /* RAID5 left_asymmetric, with Q on last device */
                        pd_idx = data_disks - sector_div(stripe2, raid_disks-1);
                        if (*dd_idx >= pd_idx)
                                (*dd_idx)++;
                        qd_idx = raid_disks - 1;
                        break;

                case ALGORITHM_RIGHT_ASYMMETRIC_6:
                        pd_idx = sector_div(stripe2, raid_disks-1);
                        if (*dd_idx >= pd_idx)
                                (*dd_idx)++;
                        qd_idx = raid_disks - 1;
                        break;

                case ALGORITHM_LEFT_SYMMETRIC_6:
                        pd_idx = data_disks - sector_div(stripe2, raid_disks-1);
                        *dd_idx = (pd_idx + 1 + *dd_idx) % (raid_disks-1);
                        qd_idx = raid_disks - 1;
                        break;

                case ALGORITHM_RIGHT_SYMMETRIC_6:
                        pd_idx = sector_div(stripe2, raid_disks-1);
                        *dd_idx = (pd_idx + 1 + *dd_idx) % (raid_disks-1);
                        qd_idx = raid_disks - 1;
                        break;

                case ALGORITHM_PARITY_0_6:
                        pd_idx = 0;
                        (*dd_idx)++;
                        qd_idx = raid_disks - 1;
                        break;

                default:
                        BUG();
                }
                break;
        }

        if (sh) {
                sh->pd_idx = pd_idx;
                sh->qd_idx = qd_idx;
                sh->ddf_layout = ddf_layout;
        }
        /*
         * Finally, compute the new sector number
         */
        new_sector = (sector_t)stripe * sectors_per_chunk + chunk_offset;
        return new_sector;
}

sector_t raid5_compute_blocknr(struct stripe_head *sh, int i, int previous)
{
        struct r5conf *conf = sh->raid_conf;
        int raid_disks = sh->disks;
        int data_disks = raid_disks - conf->max_degraded;
        sector_t new_sector = sh->sector, check;
        int sectors_per_chunk = previous ? conf->prev_chunk_sectors
                                         : conf->chunk_sectors;
        int algorithm = previous ? conf->prev_algo
                                 : conf->algorithm;
        sector_t stripe;
        int chunk_offset;
        sector_t chunk_number;
        int dummy1, dd_idx = i;
        sector_t r_sector;
        struct stripe_head sh2;

        chunk_offset = sector_div(new_sector, sectors_per_chunk);
        stripe = new_sector;

        if (i == sh->pd_idx)
                return 0;
        switch(conf->level) {
        case 4: break;
        case 5:
                switch (algorithm) {
                case ALGORITHM_LEFT_ASYMMETRIC:
                case ALGORITHM_RIGHT_ASYMMETRIC:
                        if (i > sh->pd_idx)
                                i--;
                        break;
                case ALGORITHM_LEFT_SYMMETRIC:
                case ALGORITHM_RIGHT_SYMMETRIC:
                        if (i < sh->pd_idx)
                                i += raid_disks;
                        i -= (sh->pd_idx + 1);
                        break;
                case ALGORITHM_PARITY_0:
                        i -= 1;
                        break;
                case ALGORITHM_PARITY_N:
                        break;
                default:
                        BUG();
                }
                break;
        case 6:
                if (i == sh->qd_idx)
                        return 0; /* It is the Q disk */
                switch (algorithm) {
                case ALGORITHM_LEFT_ASYMMETRIC:
                case ALGORITHM_RIGHT_ASYMMETRIC:
                case ALGORITHM_ROTATING_ZERO_RESTART:
                case ALGORITHM_ROTATING_N_RESTART:
                        if (sh->pd_idx == raid_disks-1)
                                i--;    /* Q D D D P */
                        else if (i > sh->pd_idx)
                                i -= 2; /* D D P Q D */
                        break;
                case ALGORITHM_LEFT_SYMMETRIC:
                case ALGORITHM_RIGHT_SYMMETRIC:
                        if (sh->pd_idx == raid_disks-1)
                                i--; /* Q D D D P */
                        else {
                                /* D D P Q D */
                                if (i < sh->pd_idx)
                                        i += raid_disks;
                                i -= (sh->pd_idx + 2);
                        }
                        break;
                case ALGORITHM_PARITY_0:
                        i -= 2;
                        break;
                case ALGORITHM_PARITY_N:
                        break;
                case ALGORITHM_ROTATING_N_CONTINUE:
                        /* Like left_symmetric, but P is before Q */
                        if (sh->pd_idx == 0)
                                i--;    /* P D D D Q */
                        else {
                                /* D D Q P D */
                                if (i < sh->pd_idx)
                                        i += raid_disks;
                                i -= (sh->pd_idx + 1);
                        }
                        break;
                case ALGORITHM_LEFT_ASYMMETRIC_6:
                case ALGORITHM_RIGHT_ASYMMETRIC_6:
                        if (i > sh->pd_idx)
                                i--;
                        break;
                case ALGORITHM_LEFT_SYMMETRIC_6:
                case ALGORITHM_RIGHT_SYMMETRIC_6:
                        if (i < sh->pd_idx)
                                i += data_disks + 1;
                        i -= (sh->pd_idx + 1);