dm-raid.c

/*
 * Copyright (C) 2010-2011 Neil Brown
 * Copyright (C) 2010-2016 Red Hat, Inc. All rights reserved.
 *
 * This file is released under the GPL.
 */

#include <linux/slab.h>
#include <linux/module.h>

#include "md.h"
#include "raid1.h"
#include "raid5.h"
#include "raid10.h"
#include "bitmap.h"

#include <linux/device-mapper.h>

#define DM_MSG_PREFIX "raid"
#define	MAX_RAID_DEVICES	253 /* md-raid kernel limit */

/*
 * Minimum sectors of free reshape space per raid device
 */
#define	MIN_FREE_RESHAPE_SPACE to_sector(4*4096)

static bool devices_handle_discard_safely = false;

/*
 * The following flags are used by dm-raid.c to set up the array state.
 * They must be cleared before md_run is called.
 */
#define FirstUse 10		/* rdev flag */

struct raid_dev {
	/*
	 * Two DM devices, one to hold metadata and one to hold the
	 * actual data/parity.	The reason for this is to not confuse
	 * ti->len and give more flexibility in altering size and
	 * characteristics.
	 *
	 * While it is possible for this device to be associated
	 * with a different physical device than the data_dev, it
	 * is intended for it to be the same.
	 *    |--------- Physical Device ---------|
	 *    |- meta_dev -|------ data_dev ------|
	 */
	struct dm_dev *meta_dev;
	struct dm_dev *data_dev;
	struct md_rdev rdev;
};

/*
 * Bits for establishing rs->ctr_flags
 *
 * 1 = no flag value
 * 2 = flag with value
 */
#define __CTR_FLAG_SYNC			0  /* 1 */ /* Not with raid0! */
#define __CTR_FLAG_NOSYNC		1  /* 1 */ /* Not with raid0! */
#define __CTR_FLAG_REBUILD		2  /* 2 */ /* Not with raid0! */
#define __CTR_FLAG_DAEMON_SLEEP		3  /* 2 */ /* Not with raid0! */
#define __CTR_FLAG_MIN_RECOVERY_RATE	4  /* 2 */ /* Not with raid0! */
#define __CTR_FLAG_MAX_RECOVERY_RATE	5  /* 2 */ /* Not with raid0! */
#define __CTR_FLAG_MAX_WRITE_BEHIND	6  /* 2 */ /* Only with raid1! */
#define __CTR_FLAG_WRITE_MOSTLY		7  /* 2 */ /* Only with raid1! */
#define __CTR_FLAG_STRIPE_CACHE		8  /* 2 */ /* Only with raid4/5/6! */
#define __CTR_FLAG_REGION_SIZE		9  /* 2 */ /* Not with raid0! */
#define __CTR_FLAG_RAID10_COPIES	10 /* 2 */ /* Only with raid10 */
#define __CTR_FLAG_RAID10_FORMAT	11 /* 2 */ /* Only with raid10 */
/* New for v1.9.0 */
#define __CTR_FLAG_DELTA_DISKS		12 /* 2 */ /* Only with reshapable raid1/4/5/6/10! */
#define __CTR_FLAG_DATA_OFFSET		13 /* 2 */ /* Only with reshapable raid4/5/6/10! */
#define __CTR_FLAG_RAID10_USE_NEAR_SETS 14 /* 2 */ /* Only with raid10! */

/*
 * Flags for rs->ctr_flags field.
 */
#define CTR_FLAG_SYNC			(1 << __CTR_FLAG_SYNC)
#define CTR_FLAG_NOSYNC			(1 << __CTR_FLAG_NOSYNC)
#define CTR_FLAG_REBUILD		(1 << __CTR_FLAG_REBUILD)
#define CTR_FLAG_DAEMON_SLEEP		(1 << __CTR_FLAG_DAEMON_SLEEP)
#define CTR_FLAG_MIN_RECOVERY_RATE	(1 << __CTR_FLAG_MIN_RECOVERY_RATE)
#define CTR_FLAG_MAX_RECOVERY_RATE	(1 << __CTR_FLAG_MAX_RECOVERY_RATE)
#define CTR_FLAG_MAX_WRITE_BEHIND	(1 << __CTR_FLAG_MAX_WRITE_BEHIND)
#define CTR_FLAG_WRITE_MOSTLY		(1 << __CTR_FLAG_WRITE_MOSTLY)
#define CTR_FLAG_STRIPE_CACHE		(1 << __CTR_FLAG_STRIPE_CACHE)
#define CTR_FLAG_REGION_SIZE		(1 << __CTR_FLAG_REGION_SIZE)
#define CTR_FLAG_RAID10_COPIES		(1 << __CTR_FLAG_RAID10_COPIES)
#define CTR_FLAG_RAID10_FORMAT		(1 << __CTR_FLAG_RAID10_FORMAT)
#define CTR_FLAG_DELTA_DISKS		(1 << __CTR_FLAG_DELTA_DISKS)
#define CTR_FLAG_DATA_OFFSET		(1 << __CTR_FLAG_DATA_OFFSET)
#define CTR_FLAG_RAID10_USE_NEAR_SETS	(1 << __CTR_FLAG_RAID10_USE_NEAR_SETS)

/*
 * Definitions of various constructor flags to
 * be used in checks of valid / invalid flags
 * per raid level.
 */
/* Define all any sync flags */
#define	CTR_FLAGS_ANY_SYNC		(CTR_FLAG_SYNC | CTR_FLAG_NOSYNC)

/* Define flags for options without argument (e.g. 'nosync') */
#define	CTR_FLAG_OPTIONS_NO_ARGS	(CTR_FLAGS_ANY_SYNC | \
					 CTR_FLAG_RAID10_USE_NEAR_SETS)

/* Define flags for options with one argument (e.g. 'delta_disks +2') */
#define CTR_FLAG_OPTIONS_ONE_ARG (CTR_FLAG_REBUILD | \
				  CTR_FLAG_WRITE_MOSTLY | \
				  CTR_FLAG_DAEMON_SLEEP | \
				  CTR_FLAG_MIN_RECOVERY_RATE | \
				  CTR_FLAG_MAX_RECOVERY_RATE | \
				  CTR_FLAG_MAX_WRITE_BEHIND | \
				  CTR_FLAG_STRIPE_CACHE | \
				  CTR_FLAG_REGION_SIZE | \
				  CTR_FLAG_RAID10_COPIES | \
				  CTR_FLAG_RAID10_FORMAT | \
				  CTR_FLAG_DELTA_DISKS | \
				  CTR_FLAG_DATA_OFFSET)

/* Valid options definitions per raid level... */

/* "raid0" does only accept data offset */
#define RAID0_VALID_FLAGS	(CTR_FLAG_DATA_OFFSET)

/* "raid1" does not accept stripe cache, data offset, delta_disks or any raid10 options */
#define RAID1_VALID_FLAGS	(CTR_FLAGS_ANY_SYNC | \
				 CTR_FLAG_REBUILD | \
				 CTR_FLAG_WRITE_MOSTLY | \
				 CTR_FLAG_DAEMON_SLEEP | \
				 CTR_FLAG_MIN_RECOVERY_RATE | \
				 CTR_FLAG_MAX_RECOVERY_RATE | \
				 CTR_FLAG_MAX_WRITE_BEHIND | \
				 CTR_FLAG_REGION_SIZE | \
				 CTR_FLAG_DELTA_DISKS | \
				 CTR_FLAG_DATA_OFFSET)

/* "raid10" does not accept any raid1 or stripe cache options */
#define RAID10_VALID_FLAGS	(CTR_FLAGS_ANY_SYNC | \
				 CTR_FLAG_REBUILD | \
				 CTR_FLAG_DAEMON_SLEEP | \
				 CTR_FLAG_MIN_RECOVERY_RATE | \
				 CTR_FLAG_MAX_RECOVERY_RATE | \
				 CTR_FLAG_REGION_SIZE | \
				 CTR_FLAG_RAID10_COPIES | \
				 CTR_FLAG_RAID10_FORMAT | \
				 CTR_FLAG_DELTA_DISKS | \
				 CTR_FLAG_DATA_OFFSET | \
				 CTR_FLAG_RAID10_USE_NEAR_SETS)

/*
 * "raid4/5/6" do not accept any raid1 or raid10 specific options
 *
 * "raid6" does not accept "nosync", because it is not guaranteed
 * that both parity and q-syndrome are being written properly with
 * any writes
 */
#define RAID45_VALID_FLAGS	(CTR_FLAGS_ANY_SYNC | \
				 CTR_FLAG_REBUILD | \
				 CTR_FLAG_DAEMON_SLEEP | \
				 CTR_FLAG_MIN_RECOVERY_RATE | \
				 CTR_FLAG_MAX_RECOVERY_RATE | \
				 CTR_FLAG_MAX_WRITE_BEHIND | \
				 CTR_FLAG_STRIPE_CACHE | \
				 CTR_FLAG_REGION_SIZE | \
				 CTR_FLAG_DELTA_DISKS | \
				 CTR_FLAG_DATA_OFFSET)

#define RAID6_VALID_FLAGS	(CTR_FLAG_SYNC | \
				 CTR_FLAG_REBUILD | \
				 CTR_FLAG_DAEMON_SLEEP | \
				 CTR_FLAG_MIN_RECOVERY_RATE | \
				 CTR_FLAG_MAX_RECOVERY_RATE | \
				 CTR_FLAG_MAX_WRITE_BEHIND | \
				 CTR_FLAG_STRIPE_CACHE | \
				 CTR_FLAG_REGION_SIZE | \
				 CTR_FLAG_DELTA_DISKS | \
				 CTR_FLAG_DATA_OFFSET)
/* ...valid options definitions per raid level */

/*
 * Flags for rs->runtime_flags field
 * (RT_FLAG prefix meaning "runtime flag")
 *
 * These are all internal and used to define runtime state,
 * e.g. to prevent another resume from preresume processing
 * the raid set all over again.
 */
#define RT_FLAG_RS_PRERESUMED		0
#define RT_FLAG_RS_RESUMED		1
#define RT_FLAG_RS_BITMAP_LOADED	2
#define RT_FLAG_UPDATE_SBS		3
#define RT_FLAG_RESHAPE_RS		4
#define RT_FLAG_KEEP_RS_FROZEN		5

/* Array elements of 64 bit needed for rebuild/failed disk bits */
#define DISKS_ARRAY_ELEMS ((MAX_RAID_DEVICES + (sizeof(uint64_t) * 8 - 1)) / sizeof(uint64_t) / 8)

/*
 * raid set level, layout and chunk sectors backup/restore
 */
struct rs_layout {
	int new_level;
	int new_layout;
	int new_chunk_sectors;
};

struct raid_set {
	struct dm_target *ti;

	uint32_t bitmap_loaded;
	uint32_t stripe_cache_entries;
	unsigned long ctr_flags;
	unsigned long runtime_flags;

	uint64_t rebuild_disks[DISKS_ARRAY_ELEMS];

	int raid_disks;
	int delta_disks;
	int data_offset;
	int raid10_copies;
	int requested_bitmap_chunk_sectors;

	struct mddev md;
	struct raid_type *raid_type;
	struct dm_target_callbacks callbacks;

	struct raid_dev dev[0];
};

static void rs_config_backup(struct raid_set *rs, struct rs_layout *l)
{
	struct mddev *mddev = &rs->md;

	l->new_level = mddev->new_level;
	l->new_layout = mddev->new_layout;
	l->new_chunk_sectors = mddev->new_chunk_sectors;
}

static void rs_config_restore(struct raid_set *rs, struct rs_layout *l)
{
	struct mddev *mddev = &rs->md;

	mddev->new_level = l->new_level;
	mddev->new_layout = l->new_layout;
	mddev->new_chunk_sectors = l->new_chunk_sectors;
}

/* raid10 algorithms (i.e. formats) */
#define	ALGORITHM_RAID10_DEFAULT	0
#define	ALGORITHM_RAID10_NEAR		1
#define	ALGORITHM_RAID10_OFFSET		2
#define	ALGORITHM_RAID10_FAR		3

/* Supported raid types and properties. */
static struct raid_type {
	const char *name;		/* RAID algorithm. */
	const char *descr;		/* Descriptor text for logging. */
	const unsigned parity_devs;	/* # of parity devices. */
	const unsigned minimal_devs;	/* minimal # of devices in set. */
	const unsigned level;		/* RAID level. */
	const unsigned algorithm;	/* RAID algorithm. */
} raid_types[] = {
	{"raid0",	  "raid0 (striping)",			    0, 2, 0,  0 /* NONE */},
	{"raid1",	  "raid1 (mirroring)",			    0, 2, 1,  0 /* NONE */},
	{"raid10_far",	  "raid10 far (striped mirrors)",	    0, 2, 10, ALGORITHM_RAID10_FAR},
	{"raid10_offset", "raid10 offset (striped mirrors)",	    0, 2, 10, ALGORITHM_RAID10_OFFSET},
	{"raid10_near",	  "raid10 near (striped mirrors)",	    0, 2, 10, ALGORITHM_RAID10_NEAR},
	{"raid10",	  "raid10 (striped mirrors)",		    0, 2, 10, ALGORITHM_RAID10_DEFAULT},
	{"raid4",	  "raid4 (dedicated last parity disk)",	    1, 2, 4,  ALGORITHM_PARITY_N}, /* raid4 layout = raid5_n */
	{"raid5_n",	  "raid5 (dedicated last parity disk)",	    1, 2, 5,  ALGORITHM_PARITY_N},
	{"raid5_ls",	  "raid5 (left symmetric)",		    1, 2, 5,  ALGORITHM_LEFT_SYMMETRIC},
	{"raid5_rs",	  "raid5 (right symmetric)",		    1, 2, 5,  ALGORITHM_RIGHT_SYMMETRIC},
	{"raid5_la",	  "raid5 (left asymmetric)",		    1, 2, 5,  ALGORITHM_LEFT_ASYMMETRIC},
	{"raid5_ra",	  "raid5 (right asymmetric)",		    1, 2, 5,  ALGORITHM_RIGHT_ASYMMETRIC},
	{"raid6_zr",	  "raid6 (zero restart)",		    2, 4, 6,  ALGORITHM_ROTATING_ZERO_RESTART},
	{"raid6_nr",	  "raid6 (N restart)",			    2, 4, 6,  ALGORITHM_ROTATING_N_RESTART},
	{"raid6_nc",	  "raid6 (N continue)",			    2, 4, 6,  ALGORITHM_ROTATING_N_CONTINUE},
	{"raid6_n_6",	  "raid6 (dedicated parity/Q n/6)",	    2, 4, 6,  ALGORITHM_PARITY_N_6},
	{"raid6_ls_6",	  "raid6 (left symmetric dedicated Q 6)",   2, 4, 6,  ALGORITHM_LEFT_SYMMETRIC_6},
	{"raid6_rs_6",	  "raid6 (right symmetric dedicated Q 6)",  2, 4, 6,  ALGORITHM_RIGHT_SYMMETRIC_6},
	{"raid6_la_6",	  "raid6 (left asymmetric dedicated Q 6)",  2, 4, 6,  ALGORITHM_LEFT_ASYMMETRIC_6},
	{"raid6_ra_6",	  "raid6 (right asymmetric dedicated Q 6)", 2, 4, 6,  ALGORITHM_RIGHT_ASYMMETRIC_6}
};

/* True, if @v is in inclusive range [@min, @max] */
static bool __within_range(long v, long min, long max)
{
	return v >= min && v <= max;
}

/* All table line arguments are defined here */
static struct arg_name_flag {
	const unsigned long flag;
	const char *name;
} __arg_name_flags[] = {
	{ CTR_FLAG_SYNC, "sync"},
	{ CTR_FLAG_NOSYNC, "nosync"},
	{ CTR_FLAG_REBUILD, "rebuild"},
	{ CTR_FLAG_DAEMON_SLEEP, "daemon_sleep"},
	{ CTR_FLAG_MIN_RECOVERY_RATE, "min_recovery_rate"},
	{ CTR_FLAG_MAX_RECOVERY_RATE, "max_recovery_rate"},
	{ CTR_FLAG_MAX_WRITE_BEHIND, "max_write_behind"},
	{ CTR_FLAG_WRITE_MOSTLY, "write_mostly"},
	{ CTR_FLAG_STRIPE_CACHE, "stripe_cache"},
	{ CTR_FLAG_REGION_SIZE, "region_size"},
	{ CTR_FLAG_RAID10_COPIES, "raid10_copies"},
	{ CTR_FLAG_RAID10_FORMAT, "raid10_format"},
	{ CTR_FLAG_DATA_OFFSET, "data_offset"},
	{ CTR_FLAG_DELTA_DISKS, "delta_disks"},
	{ CTR_FLAG_RAID10_USE_NEAR_SETS, "raid10_use_near_sets"},
};

/* Return argument name string for given @flag */
static const char *dm_raid_arg_name_by_flag(const uint32_t flag)
{
	if (hweight32(flag) == 1) {
		struct arg_name_flag *anf = __arg_name_flags + ARRAY_SIZE(__arg_name_flags);

		while (anf-- > __arg_name_flags)
			if (flag & anf->flag)
				return anf->name;

	} else
		DMERR("%s called with more than one flag!", __func__);

	return NULL;
}

/*
 * Bool helpers to test for various raid levels of a raid set.
 * It's level as reported by the superblock rather than
 * the requested raid_type passed to the constructor.
 */
/* Return true, if raid set in @rs is raid0 */
static bool rs_is_raid0(struct raid_set *rs)
{
	return !rs->md.level;
}

/* Return true, if raid set in @rs is raid1 */
static bool rs_is_raid1(struct raid_set *rs)
{
	return rs->md.level == 1;
}

/* Return true, if raid set in @rs is raid10 */
static bool rs_is_raid10(struct raid_set *rs)
{
	return rs->md.level == 10;
}

/* Return true, if raid set in @rs is level 6 */
static bool rs_is_raid6(struct raid_set *rs)
{
	return rs->md.level == 6;
}

/* Return true, if raid set in @rs is level 4, 5 or 6 */
static bool rs_is_raid456(struct raid_set *rs)
{
	return __within_range(rs->md.level, 4, 6);
}

/* Return true, if raid set in @rs is reshapable */
static bool __is_raid10_far(int layout);
static bool rs_is_reshapable(struct raid_set *rs)
{
	return rs_is_raid456(rs) ||
	       (rs_is_raid10(rs) && !__is_raid10_far(rs->md.new_layout));
}

/* Return true, if raid set in @rs is recovering */
static bool rs_is_recovering(struct raid_set *rs)
{
	return rs->md.recovery_cp < rs->dev[0].rdev.sectors;
}

/* Return true, if raid set in @rs is reshaping */
static bool rs_is_reshaping(struct raid_set *rs)
{
	return rs->md.reshape_position != MaxSector;
}

/*
 * bool helpers to test for various raid levels of a raid type @rt
 */

/* Return true, if raid type in @rt is raid0 */
static bool rt_is_raid0(struct raid_type *rt)
{
	return !rt->level;
}

/* Return true, if raid type in @rt is raid1 */
static bool rt_is_raid1(struct raid_type *rt)
{
	return rt->level == 1;
}

/* Return true, if raid type in @rt is raid10 */
static bool rt_is_raid10(struct raid_type *rt)
{
	return rt->level == 10;
}

/* Return true, if raid type in @rt is raid4/5 */
static bool rt_is_raid45(struct raid_type *rt)
{
	return __within_range(rt->level, 4, 5);
}

/* Return true, if raid type in @rt is raid6 */
static bool rt_is_raid6(struct raid_type *rt)
{
	return rt->level == 6;
}

/* Return true, if raid type in @rt is raid4/5/6 */
static bool rt_is_raid456(struct raid_type *rt)
{
	return __within_range(rt->level, 4, 6);
}
/* END: raid level bools */

/* Return valid ctr flags for the raid level of @rs */
static unsigned long __valid_flags(struct raid_set *rs)
{
	if (rt_is_raid0(rs->raid_type))
		return RAID0_VALID_FLAGS;
	else if (rt_is_raid1(rs->raid_type))
		return RAID1_VALID_FLAGS;
	else if (rt_is_raid10(rs->raid_type))
		return RAID10_VALID_FLAGS;
	else if (rt_is_raid45(rs->raid_type))
		return RAID45_VALID_FLAGS;
	else if (rt_is_raid6(rs->raid_type))
		return RAID6_VALID_FLAGS;

	return 0;
}

/*
 * Check for valid flags set on @rs
 *
 * Has to be called after parsing of the ctr flags!
 */
static int rs_check_for_valid_flags(struct raid_set *rs)
{
	if (rs->ctr_flags & ~__valid_flags(rs)) {
		rs->ti->error = "Invalid flags combination";
		return -EINVAL;
	}

	return 0;
}

/* MD raid10 bit definitions and helpers */
#define RAID10_OFFSET			(1 << 16) /* stripes with data copies area adjacent on devices */
#define RAID10_BROCKEN_USE_FAR_SETS	(1 << 17) /* Broken in raid10.c: use sets instead of whole stripe rotation */
#define RAID10_USE_FAR_SETS		(1 << 18) /* Use sets instead of whole stripe rotation */
#define RAID10_FAR_COPIES_SHIFT		8	  /* raid10 # far copies shift (2nd byte of layout) */

/* Return md raid10 near copies for @layout */
static unsigned int __raid10_near_copies(int layout)
{
	return layout & 0xFF;
}

/* Return md raid10 far copies for @layout */
static unsigned int __raid10_far_copies(int layout)
{
	return __raid10_near_copies(layout >> RAID10_FAR_COPIES_SHIFT);
}

/* Return true if md raid10 offset for @layout */
static bool __is_raid10_offset(int layout)
{
	return !!(layout & RAID10_OFFSET);
}

/* Return true if md raid10 near for @layout */
static bool __is_raid10_near(int layout)
{
	return !__is_raid10_offset(layout) && __raid10_near_copies(layout) > 1;
}

/* Return true if md raid10 far for @layout */
static bool __is_raid10_far(int layout)
{
	return !__is_raid10_offset(layout) && __raid10_far_copies(layout) > 1;
}

/* Return md raid10 layout string for @layout */
static const char *raid10_md_layout_to_format(int layout)
{
	/*
	 * Bit 16 stands for "offset"
	 * (i.e. adjacent stripes hold copies)
	 *
	 * Refer to MD's raid10.c for details
	 */
	if (__is_raid10_offset(layout))
		return "offset";

	if (__raid10_near_copies(layout) > 1)
		return "near";

	WARN_ON(__raid10_far_copies(layout) < 2);

	return "far";
}

/* Return md raid10 algorithm for @name */
static int raid10_name_to_format(const char *name)
{
	if (!strcasecmp(name, "near"))
		return ALGORITHM_RAID10_NEAR;
	else if (!strcasecmp(name, "offset"))
		return ALGORITHM_RAID10_OFFSET;
	else if (!strcasecmp(name, "far"))
		return ALGORITHM_RAID10_FAR;

	return -EINVAL;
}

/* Return md raid10 copies for @layout */
static unsigned int raid10_md_layout_to_copies(int layout)
{
	return max(__raid10_near_copies(layout), __raid10_far_copies(layout));
}

/* Return md raid10 format id for @format string */
static int raid10_format_to_md_layout(struct raid_set *rs,
				      unsigned int algorithm,
				      unsigned int copies)
{
	unsigned int n = 1, f = 1, r = 0;

	/*
	 * MD resilienece flaw:
	 *
	 * enabling use_far_sets for far/offset formats causes copies
	 * to be colocated on the same devs together with their origins!
	 *
	 * -> disable it for now in the definition above
	 */
	if (algorithm == ALGORITHM_RAID10_DEFAULT ||
	    algorithm == ALGORITHM_RAID10_NEAR)
		n = copies;

	else if (algorithm == ALGORITHM_RAID10_OFFSET) {
		f = copies;
		r = RAID10_OFFSET;
		if (!test_bit(__CTR_FLAG_RAID10_USE_NEAR_SETS, &rs->ctr_flags))
			r |= RAID10_USE_FAR_SETS;

	} else if (algorithm == ALGORITHM_RAID10_FAR) {
		f = copies;
		r = !RAID10_OFFSET;
		if (!test_bit(__CTR_FLAG_RAID10_USE_NEAR_SETS, &rs->ctr_flags))
			r |= RAID10_USE_FAR_SETS;

	} else
		return -EINVAL;

	return r | (f << RAID10_FAR_COPIES_SHIFT) | n;
}
/* END: MD raid10 bit definitions and helpers */

/* Check for any of the raid10 algorithms */
static bool __got_raid10(struct raid_type *rtp, const int layout)
{
	if (rtp->level == 10) {
		switch (rtp->algorithm) {
		case ALGORITHM_RAID10_DEFAULT:
		case ALGORITHM_RAID10_NEAR:
			return __is_raid10_near(layout);
		case ALGORITHM_RAID10_OFFSET:
			return __is_raid10_offset(layout);
		case ALGORITHM_RAID10_FAR:
			return __is_raid10_far(layout);
		default:
			break;
		}
	}

	return false;
}

/* Return raid_type for @name */
static struct raid_type *get_raid_type(const char *name)
{
	struct raid_type *rtp = raid_types + ARRAY_SIZE(raid_types);

	while (rtp-- > raid_types)
		if (!strcasecmp(rtp->name, name))
			return rtp;

	return NULL;
}

/* Return raid_type for @name based derived from @level and @layout */
static struct raid_type *get_raid_type_by_ll(const int level, const int layout)
{
	struct raid_type *rtp = raid_types + ARRAY_SIZE(raid_types);

	while (rtp-- > raid_types) {
		/* RAID10 special checks based on @layout flags/properties */
		if (rtp->level == level &&
		    (__got_raid10(rtp, layout) || rtp->algorithm == layout))
			return rtp;
	}

	return NULL;
}

/*
 * Conditionally change bdev capacity of @rs
 * in case of a disk add/remove reshape
 */
static void rs_set_capacity(struct raid_set *rs)
{
	struct mddev *mddev = &rs->md;
	struct md_rdev *rdev;
	struct gendisk *gendisk = dm_disk(dm_table_get_md(rs->ti->table));

	/*
	 * raid10 sets rdev->sector to the device size, which
	 * is unintended in case of out-of-place reshaping
	 */
	rdev_for_each(rdev, mddev)
		rdev->sectors = mddev->dev_sectors;

	set_capacity(gendisk, mddev->array_sectors);
	revalidate_disk(gendisk);
}

/*
 * Set the mddev properties in @rs to the current
 * ones retrieved from the freshest superblock
 */
static void rs_set_cur(struct raid_set *rs)
{
	struct mddev *mddev = &rs->md;

	mddev->new_level = mddev->level;
	mddev->new_layout = mddev->layout;
	mddev->new_chunk_sectors = mddev->chunk_sectors;
}

/*
 * Set the mddev properties in @rs to the new
 * ones requested by the ctr
 */
static void rs_set_new(struct raid_set *rs)
{
	struct mddev *mddev = &rs->md;

	mddev->level = mddev->new_level;
	mddev->layout = mddev->new_layout;
	mddev->chunk_sectors = mddev->new_chunk_sectors;
	mddev->raid_disks = rs->raid_disks;
	mddev->delta_disks = 0;
}

static struct raid_set *raid_set_alloc(struct dm_target *ti, struct raid_type *raid_type,
				       unsigned raid_devs)
{
	unsigned i;
	struct raid_set *rs;

	if (raid_devs <= raid_type->parity_devs) {
		ti->error = "Insufficient number of devices";
		return ERR_PTR(-EINVAL);
	}

	rs = kzalloc(sizeof(*rs) + raid_devs * sizeof(rs->dev[0]), GFP_KERNEL);
	if (!rs) {
		ti->error = "Cannot allocate raid context";
		return ERR_PTR(-ENOMEM);
	}

	mddev_init(&rs->md);

	rs->raid_disks = raid_devs;
	rs->delta_disks = 0;

	rs->ti = ti;
	rs->raid_type = raid_type;
	rs->stripe_cache_entries = 256;
	rs->md.raid_disks = raid_devs;
	rs->md.level = raid_type->level;
	rs->md.new_level = rs->md.level;
	rs->md.layout = raid_type->algorithm;
	rs->md.new_layout = rs->md.layout;
	rs->md.delta_disks = 0;
	rs->md.recovery_cp = MaxSector;

	for (i = 0; i < raid_devs; i++)
		md_rdev_init(&rs->dev[i].rdev);

	/*
	 * Remaining items to be initialized by further RAID params:
	 *  rs->md.persistent
	 *  rs->md.external
	 *  rs->md.chunk_sectors
	 *  rs->md.new_chunk_sectors
	 *  rs->md.dev_sectors
	 */

	return rs;
}

static void raid_set_free(struct raid_set *rs)
{
	int i;

	for (i = 0; i < rs->raid_disks; i++) {
		if (rs->dev[i].meta_dev)
			dm_put_device(rs->ti, rs->dev[i].meta_dev);
		md_rdev_clear(&rs->dev[i].rdev);
		if (rs->dev[i].data_dev)
			dm_put_device(rs->ti, rs->dev[i].data_dev);
	}

	kfree(rs);
}

/*
 * For every device we have two words
 *  <meta_dev>: meta device name or '-' if missing
 *  <data_dev>: data device name or '-' if missing
 *
 * The following are permitted:
 *    - -
 *    - <data_dev>
 *    <meta_dev> <data_dev>
 *
 * The following is not allowed:
 *    <meta_dev> -
 *
 * This code parses those words.  If there is a failure,
 * the caller must use raid_set_free() to unwind the operations.
 */
static int parse_dev_params(struct raid_set *rs, struct dm_arg_set *as)
{
	int i;
	int rebuild = 0;
	int metadata_available = 0;
	int r = 0;
	const char *arg;

	/* Put off the number of raid devices argument to get to dev pairs */
	arg = dm_shift_arg(as);
	if (!arg)
		return -EINVAL;

	for (i = 0; i < rs->raid_disks; i++) {
		rs->dev[i].rdev.raid_disk = i;

		rs->dev[i].meta_dev = NULL;
		rs->dev[i].data_dev = NULL;

		/*
		 * There are no offsets, since there is a separate device
		 * for data and metadata.
		 */
		rs->dev[i].rdev.data_offset = 0;
		rs->dev[i].rdev.mddev = &rs->md;

		arg = dm_shift_arg(as);
		if (!arg)
			return -EINVAL;

		if (strcmp(arg, "-")) {
			r = dm_get_device(rs->ti, arg, dm_table_get_mode(rs->ti->table),
					  &rs->dev[i].meta_dev);
			if (r) {
				rs->ti->error = "RAID metadata device lookup failure";
				return r;
			}

			rs->dev[i].rdev.sb_page = alloc_page(GFP_KERNEL);
			if (!rs->dev[i].rdev.sb_page) {
				rs->ti->error = "Failed to allocate superblock page";
				return -ENOMEM;
			}
		}

		arg = dm_shift_arg(as);
		if (!arg)
			return -EINVAL;

		if (!strcmp(arg, "-")) {
			if (!test_bit(In_sync, &rs->dev[i].rdev.flags) &&
			    (!rs->dev[i].rdev.recovery_offset)) {
				rs->ti->error = "Drive designated for rebuild not specified";
				return -EINVAL;
			}

			if (rs->dev[i].meta_dev) {
				rs->ti->error = "No data device supplied with metadata device";
				return -EINVAL;
			}

			continue;
		}

		r = dm_get_device(rs->ti, arg, dm_table_get_mode(rs->ti->table),
				  &rs->dev[i].data_dev);
		if (r) {
			rs->ti->error = "RAID device lookup failure";
			return r;
		}

		if (rs->dev[i].meta_dev) {
			metadata_available = 1;
			rs->dev[i].rdev.meta_bdev = rs->dev[i].meta_dev->bdev;
		}
		rs->dev[i].rdev.bdev = rs->dev[i].data_dev->bdev;
		list_add_tail(&rs->dev[i].rdev.same_set, &rs->md.disks);
		if (!test_bit(In_sync, &rs->dev[i].rdev.flags))
			rebuild++;
	}

	if (metadata_available) {
		rs->md.external = 0;
		rs->md.persistent = 1;
		rs->md.major_version = 2;
	} else if (rebuild && !rs->md.recovery_cp) {
		/*
		 * Without metadata, we will not be able to tell if the array
		 * is in-sync or not - we must assume it is not.  Therefore,
		 * it is impossible to rebuild a drive.
		 *
		 * Even if there is metadata, the on-disk information may
		 * indicate that the array is not in-sync and it will then
		 * fail at that time.
		 *
		 * User could specify 'nosync' option if desperate.
		 */
		rs->ti->error = "Unable to rebuild drive while array is not in-sync";
		return -EINVAL;
	}

	return 0;
}

/*
 * validate_region_size
 * @rs
 * @region_size:  region size in sectors.  If 0, pick a size (4MiB default).
 *
 * Set rs->md.bitmap_info.chunksize (which really refers to 'region size').
 * Ensure that (ti->len/region_size < 2^21) - required by MD bitmap.
 *
 * Returns: 0 on success, -EINVAL on failure.
 */
static int validate_region_size(struct raid_set *rs, unsigned long region_size)
{
	unsigned long min_region_size = rs->ti->len / (1 << 21);

	if (!region_size) {
		/*
		 * Choose a reasonable default.	 All figures in sectors.
		 */
		if (min_region_size > (1 << 13)) {
			/* If not a power of 2, make it the next power of 2 */
			region_size = roundup_pow_of_two(min_region_size);
			DMINFO("Choosing default region size of %lu sectors",
			       region_size);
		} else {
			DMINFO("Choosing default region size of 4MiB");
			region_size = 1 << 13; /* sectors */
		}
	} else {
		/*
		 * Validate user-supplied value.
		 */
		if (region_size > rs->ti->len) {
			rs->ti->error = "Supplied region size is too large";
			return -EINVAL;
		}

		if (region_size < min_region_size) {
			DMERR("Supplied region_size (%lu sectors) below minimum (%lu)",
			      region_size, min_region_size);
			rs->ti->error = "Supplied region size is too small";
			return -EINVAL;
		}

		if (!is_power_of_2(region_size)) {
			rs->ti->error = "Region size is not a power of 2";
			return -EINVAL;
		}

		if (region_size < rs->md.chunk_sectors) {
			rs->ti->error = "Region size is smaller than the chunk size";
			return -EINVAL;
		}
	}

	/*
	 * Convert sectors to bytes.
	 */
	rs->md.bitmap_info.chunksize = (region_size << 9);

	return 0;
}

/*
 * validate_raid_redundancy
 * @rs
 *
 * Determine if there are enough devices in the array that haven't
 * failed (or are being rebuilt) to form a usable array.
 *
 * Returns: 0 on success, -EINVAL on failure.
 */
static int validate_raid_redundancy(struct raid_set *rs)
{
	unsigned i, rebuild_cnt = 0;
	unsigned rebuilds_per_group = 0, copies;
	unsigned group_size, last_group_start;

	for (i = 0; i < rs->md.raid_disks; i++)
		if (!test_bit(In_sync, &rs->dev[i].rdev.flags) ||
		    !rs->dev[i].rdev.sb_page)
			rebuild_cnt++;

	switch (rs->raid_type->level) {
	case 1:
		if (rebuild_cnt >= rs->md.raid_disks)
			goto too_many;
		break;
	case 4:
	case 5:
	case 6:
		if (rebuild_cnt > rs->raid_type->parity_devs)
			goto too_many;
		break;
	case 10:
		copies = raid10_md_layout_to_copies(rs->md.new_layout);
		if (rebuild_cnt < copies)
			break;

		/*
		 * It is possible to have a higher rebuild count for RAID10,
		 * as long as the failed devices occur in different mirror
		 * groups (i.e. different stripes).
		 *
		 * When checking "near" format, make sure no adjacent devices
		 * have failed beyond what can be handled.  In addition to the
		 * simple case where the number of devices is a multiple of the
		 * number of copies, we must also handle cases where the number
		 * of devices is not a multiple of the number of copies.
		 * E.g.	   dev1 dev2 dev3 dev4 dev5
		 *	    A	 A    B	   B	C
		 *	    C	 D    D	   E	E
		 */
		if (__is_raid10_near(rs->md.new_layout)) {
			for (i = 0; i < rs->md.raid_disks; i++) {
				if (!(i % copies))
					rebuilds_per_group = 0;
				if ((!rs->dev[i].rdev.sb_page ||
				    !test_bit(In_sync, &rs->dev[i].rdev.flags)) &&
				    (++rebuilds_per_group >= copies))
					goto too_many;
			}
			break;
		}

		/*
		 * When checking "far" and "offset" formats, we need to ensure
		 * that the device that holds its copy is not also dead or
		 * being rebuilt.  (Note that "far" and "offset" formats only
		 * support two copies right now.  These formats also only ever
		 * use the 'use_far_sets' variant.)
		 *
		 * This check is somewhat complicated by the need to account
		 * for arrays that are not a multiple of (far) copies.	This
		 * results in the need to treat the last (potentially larger)
		 * set differently.
		 */
		group_size = (rs->md.raid_disks / copies);
		last_group_start = (rs->md.raid_disks / group_size) - 1;
		last_group_start *= group_size;
		for (i = 0; i < rs->md.raid_disks; i++) {
			if (!(i % copies) && !(i > last_group_start))
				rebuilds_per_group = 0;
			if ((!rs->dev[i].rdev.sb_page ||
			     !test_bit(In_sync, &rs->dev[i].rdev.flags)) &&
			    (++rebuilds_per_group >= copies))
					goto too_many;
		}
		break;
	default:
		if (rebuild_cnt)
			return -EINVAL;
	}

	return 0;

too_many:
	return -EINVAL;
}

/*
 * Possible arguments are...
 *	<chunk_size> [optional_args]
 *
 * Argument definitions
 *    <chunk_size>			The number of sectors per disk that
 *					will form the "stripe"
 *    [[no]sync]			Force or prevent recovery of the
 *					entire array
 *    [rebuild <idx>]			Rebuild the drive indicated by the index
 *    [daemon_sleep <ms>]		Time between bitmap daemon work to
 *					clear bits
 *    [min_recovery_rate <kB/sec/disk>]	Throttle RAID initialization
 *    [max_recovery_rate <kB/sec/disk>]	Throttle RAID initialization
 *    [write_mostly <idx>]		Indicate a write mostly drive via index
 *    [max_write_behind <sectors>]	See '-write-behind=' (man mdadm)
 *    [stripe_cache <sectors>]		Stripe cache size for higher RAIDs
 *    [region_size <sectors>]		Defines granularity of bitmap
 *
 * RAID10-only options:
 *    [raid10_copies <# copies>]	Number of copies.  (Default: 2)
 *    [raid10_format <near|far|offset>] Layout algorithm.  (Default: near)
 */
static int parse_raid_params(struct raid_set *rs, struct dm_arg_set *as,
			     unsigned num_raid_params)
{
	int value, raid10_format = ALGORITHM_RAID10_DEFAULT;
	unsigned raid10_copies = 2;
	unsigned i, write_mostly = 0;
	unsigned region_size = 0;
	sector_t max_io_len;
	const char *arg, *key;
	struct raid_dev *rd;
	struct raid_type *rt = rs->raid_type;

	arg = dm_shift_arg(as);
	num_raid_params--; /* Account for chunk_size argument */

	if (kstrtoint(arg, 10, &value) < 0) {
		rs->ti->error = "Bad numerical argument given for chunk_size";
		return -EINVAL;
	}

	/*
	 * First, parse the in-order required arguments
	 * "chunk_size" is the only argument of this type.
	 */
	if (rt_is_raid1(rt)) {
		if (value)
			DMERR("Ignoring chunk size parameter for RAID 1");
		value = 0;
	} else if (!is_power_of_2(value)) {
		rs->ti->error = "Chunk size must be a power of 2";
		return -EINVAL;
	} else if (value < 8) {
		rs->ti->error = "Chunk size value is too small";
		return -EINVAL;
	}

	rs->md.new_chunk_sectors = rs->md.chunk_sectors = value;

	/*
	 * We set each individual device as In_sync with a completed
	 * 'recovery_offset'.  If there has been a device failure or
	 * replacement then one of the following cases applies:
	 *
	 *   1) User specifies 'rebuild'.
	 *	- Device is reset when param is read.
	 *   2) A new device is supplied.
	 *	- No matching superblock found, resets device.
	 *   3) Device failure was transient and returns on reload.
	 *	- Failure noticed, resets device for bitmap replay.
	 *   4) Device hadn't completed recovery after previous failure.
	 *	- Superblock is read and overrides recovery_offset.
	 *
	 * What is found in the superblocks of the devices is always
	 * authoritative, unless 'rebuild' or '[no]sync' was specified.
	 */
	for (i = 0; i < rs->raid_disks; i++) {
		set_bit(In_sync, &rs->dev[i].rdev.flags);
		rs->dev[i].rdev.recovery_offset = MaxSector;
	}

	/*
	 * Second, parse the unordered optional arguments
	 */
	for (i = 0; i < num_raid_params; i++) {
		key = dm_shift_arg(as);
		if (!key) {
			rs->ti->error = "Not enough raid parameters given";
			return -EINVAL;
		}

		if (!strcasecmp(key, dm_raid_arg_name_by_flag(CTR_FLAG_NOSYNC))) {
			if (test_and_set_bit(__CTR_FLAG_NOSYNC, &rs->ctr_flags)) {
				rs->ti->error = "Only one 'nosync' argument allowed";
				return -EINVAL;
			}
			continue;
		}
		if (!strcasecmp(key, dm_raid_arg_name_by_flag(CTR_FLAG_SYNC))) {
			if (test_and_set_bit(__CTR_FLAG_SYNC, &rs->ctr_flags)) {
				rs->ti->error = "Only one 'sync' argument allowed";
				return -EINVAL;
			}
			continue;
		}
		if (!strcasecmp(key, dm_raid_arg_name_by_flag(CTR_FLAG_RAID10_USE_NEAR_SETS))) {
			if (test_and_set_bit(__CTR_FLAG_RAID10_USE_NEAR_SETS, &rs->ctr_flags)) {
				rs->ti->error = "Only one 'raid10_use_new_sets' argument allowed";
				return -EINVAL;
			}
			continue;
		}

		arg = dm_shift_arg(as);
		i++; /* Account for the argument pairs */
		if (!arg) {
			rs->ti->error = "Wrong number of raid parameters given";
			return -EINVAL;
		}

		/*
		 * Parameters that take a string value are checked here.
		 */

		if (!strcasecmp(key, dm_raid_arg_name_by_flag(CTR_FLAG_RAID10_FORMAT))) {
			if (test_and_set_bit(__CTR_FLAG_RAID10_FORMAT, &rs->ctr_flags)) {
				rs->ti->error = "Only one 'raid10_format' argument pair allowed";
				return -EINVAL;
			}
			if (!rt_is_raid10(rt)) {
				rs->ti->error = "'raid10_format' is an invalid parameter for this RAID type";
				return -EINVAL;
			}
			raid10_format = raid10_name_to_format(arg);
			if (raid10_format < 0) {
				rs->ti->error = "Invalid 'raid10_format' value given";
				return raid10_format;
			}
			continue;
		}

		if (kstrtoint(arg, 10, &value) < 0) {
			rs->ti->error = "Bad numerical argument given in raid params";
			return -EINVAL;
		}

		if (!strcasecmp(key, dm_raid_arg_name_by_flag(CTR_FLAG_REBUILD))) {
			/*
			 * "rebuild" is being passed in by userspace to provide
			 * indexes of replaced devices and to set up additional
			 * devices on raid level takeover.
			 */
			if (!__within_range(value, 0, rs->raid_disks - 1)) {
				rs->ti->error = "Invalid rebuild index given";
				return -EINVAL;
			}

			if (test_and_set_bit(value, (void *) rs->rebuild_disks)) {
				rs->ti->error = "rebuild for this index already given";
				return -EINVAL;
			}

			rd = rs->dev + value;
			clear_bit(In_sync, &rd->rdev.flags);
			clear_bit(Faulty, &rd->rdev.flags);
			rd->rdev.recovery_offset = 0;