fs/zfs/metaslab.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
 * Copyright (c) 2011, 2018 by Delphix. All rights reserved.
 * Copyright (c) 2013 by Saso Kiselkov. All rights reserved.
 * Copyright (c) 2014 Integros [integros.com]
 * Copyright (c) 2017, Intel Corporation.
 */

#include <sys/zfs_context.h>
#include <sys/dmu.h>
#include <sys/dmu_tx.h>
#include <sys/space_map.h>
#include <sys/metaslab_impl.h>
#include <sys/vdev_impl.h>
#include <sys/zio.h>
#include <sys/spa_impl.h>
#include <sys/zfeature.h>
#include <sys/vdev_indirect_mapping.h>
#include <sys/zap.h>
#include <sys/btree.h>

#define	GANG_ALLOCATION(flags) \
	((flags) & (METASLAB_GANG_CHILD | METASLAB_GANG_HEADER))

uint64_t metaslab_aliquot = 512ULL << 10;
uint64_t metaslab_force_ganging = SPA_MAXBLOCKSIZE + 1;	/* force gang blocks */

/*
 * In pools where the log space map feature is not enabled we touch
 * multiple metaslabs (and their respective space maps) with each
 * transaction group. Thus, we benefit from having a small space map
 * block size since it allows us to issue more I/O operations scattered
 * around the disk. So a sane default for the space map block size
 * is 8~16K.
 */
int zfs_metaslab_sm_blksz_no_log = (1 << 14);

/*
 * When the log space map feature is enabled, we accumulate a lot of
 * changes per metaslab that are flushed once in a while so we benefit
 * from a bigger block size like 128K for the metaslab space maps.
 */
int zfs_metaslab_sm_blksz_with_log = (1 << 17);

/*
 * The in-core space map representation is more compact than its on-disk form.
 * The zfs_condense_pct determines how much more compact the in-core
 * space map representation must be before we compact it on-disk.
 * Values should be greater than or equal to 100.
 */
int zfs_condense_pct = 200;

/*
 * Condensing a metaslab is not guaranteed to actually reduce the amount of
 * space used on disk. In particular, a space map uses data in increments of
 * MAX(1 << ashift, space_map_blksize), so a metaslab might use the
 * same number of blocks after condensing. Since the goal of condensing is to
 * reduce the number of IOPs required to read the space map, we only want to
 * condense when we can be sure we will reduce the number of blocks used by the
 * space map. Unfortunately, we cannot precisely compute whether or not this is
 * the case in metaslab_should_condense since we are holding ms_lock. Instead,
 * we apply the following heuristic: do not condense a spacemap unless the
 * uncondensed size consumes greater than zfs_metaslab_condense_block_threshold
 * blocks.
 */
int zfs_metaslab_condense_block_threshold = 4;

/*
 * The zfs_mg_noalloc_threshold defines which metaslab groups should
 * be eligible for allocation. The value is defined as a percentage of
 * free space. Metaslab groups that have more free space than
 * zfs_mg_noalloc_threshold are always eligible for allocations. Once
 * a metaslab group's free space is less than or equal to the
 * zfs_mg_noalloc_threshold the allocator will avoid allocating to that
 * group unless all groups in the pool have reached zfs_mg_noalloc_threshold.
 * Once all groups in the pool reach zfs_mg_noalloc_threshold then all
 * groups are allowed to accept allocations. Gang blocks are always
 * eligible to allocate on any metaslab group. The default value of 0 means
 * no metaslab group will be excluded based on this criterion.
 */
int zfs_mg_noalloc_threshold = 0;

/*
 * Metaslab groups are considered eligible for allocations if their
 * fragmenation metric (measured as a percentage) is less than or
 * equal to zfs_mg_fragmentation_threshold. If a metaslab group
 * exceeds this threshold then it will be skipped unless all metaslab
 * groups within the metaslab class have also crossed this threshold.
 *
 * This tunable was introduced to avoid edge cases where we continue
 * allocating from very fragmented disks in our pool while other, less
 * fragmented disks, exists. On the other hand, if all disks in the
 * pool are uniformly approaching the threshold, the threshold can
 * be a speed bump in performance, where we keep switching the disks
 * that we allocate from (e.g. we allocate some segments from disk A
 * making it bypassing the threshold while freeing segments from disk
 * B getting its fragmentation below the threshold).
 *
 * Empirically, we've seen that our vdev selection for allocations is
 * good enough that fragmentation increases uniformly across all vdevs
 * the majority of the time. Thus we set the threshold percentage high
 * enough to avoid hitting the speed bump on pools that are being pushed
 * to the edge.
 */
int zfs_mg_fragmentation_threshold = 95;

/*
 * Allow metaslabs to keep their active state as long as their fragmentation
 * percentage is less than or equal to zfs_metaslab_fragmentation_threshold. An
 * active metaslab that exceeds this threshold will no longer keep its active
 * status allowing better metaslabs to be selected.
 */
int zfs_metaslab_fragmentation_threshold = 70;

/*
 * When set will load all metaslabs when pool is first opened.
 */
int metaslab_debug_load = 0;

/*
 * When set will prevent metaslabs from being unloaded.
 */
int metaslab_debug_unload = 0;

/*
 * Minimum size which forces the dynamic allocator to change
 * it's allocation strategy.  Once the space map cannot satisfy
 * an allocation of this size then it switches to using more
 * aggressive strategy (i.e search by size rather than offset).
 */
uint64_t metaslab_df_alloc_threshold = SPA_OLD_MAXBLOCKSIZE;

/*
 * The minimum free space, in percent, which must be available
 * in a space map to continue allocations in a first-fit fashion.
 * Once the space map's free space drops below this level we dynamically
 * switch to using best-fit allocations.
 */
int metaslab_df_free_pct = 4;

/*
 * Maximum distance to search forward from the last offset. Without this
 * limit, fragmented pools can see >100,000 iterations and
 * metaslab_block_picker() becomes the performance limiting factor on
 * high-performance storage.
 *
 * With the default setting of 16MB, we typically see less than 500
 * iterations, even with very fragmented, ashift=9 pools. The maximum number
 * of iterations possible is:
 *     metaslab_df_max_search / (2 * (1<<ashift))
 * With the default setting of 16MB this is 16*1024 (with ashift=9) or
 * 2048 (with ashift=12).
 */
int metaslab_df_max_search = 16 * 1024 * 1024;

/*
 * Forces the metaslab_block_picker function to search for at least this many
 * segments forwards until giving up on finding a segment that the allocation
 * will fit into.
 */
uint32_t metaslab_min_search_count = 100;

/*
 * If we are not searching forward (due to metaslab_df_max_search,
 * metaslab_df_free_pct, or metaslab_df_alloc_threshold), this tunable
 * controls what segment is used.  If it is set, we will use the largest free
 * segment.  If it is not set, we will use a segment of exactly the requested
 * size (or larger).
 */
int metaslab_df_use_largest_segment = B_FALSE;

/*
 * A metaslab is considered "free" if it contains a contiguous
 * segment which is greater than metaslab_min_alloc_size.
 */
uint64_t metaslab_min_alloc_size = DMU_MAX_ACCESS;

/*
 * Percentage of all cpus that can be used by the metaslab taskq.
 */
int metaslab_load_pct = 50;

/*
 * These tunables control how long a metaslab will remain loaded after the
 * last allocation from it.  A metaslab can't be unloaded until at least
 * metaslab_unload_delay TXG's and metaslab_unload_delay_ms milliseconds
 * have elapsed.  However, zfs_metaslab_mem_limit may cause it to be
 * unloaded sooner.  These settings are intended to be generous -- to keep
 * metaslabs loaded for a long time, reducing the rate of metaslab loading.
 */
int metaslab_unload_delay = 32;
int metaslab_unload_delay_ms = 10 * 60 * 1000; /* ten minutes */

/*
 * Max number of metaslabs per group to preload.
 */
int metaslab_preload_limit = 10;

/*
 * Enable/disable preloading of metaslab.
 */
boolean_t metaslab_preload_enabled = B_TRUE;

/*
 * Enable/disable fragmentation weighting on metaslabs.
 */
boolean_t metaslab_fragmentation_factor_enabled = B_TRUE;

/*
 * Enable/disable lba weighting (i.e. outer tracks are given preference).
 */
boolean_t metaslab_lba_weighting_enabled = B_TRUE;

/*
 * Enable/disable metaslab group biasing.
 */
boolean_t metaslab_bias_enabled = B_TRUE;

/*
 * Enable/disable remapping of indirect DVAs to their concrete vdevs.
 */
boolean_t zfs_remap_blkptr_enable = B_TRUE;

/*
 * Enable/disable segment-based metaslab selection.
 */
boolean_t zfs_metaslab_segment_weight_enabled = B_TRUE;

/*
 * When using segment-based metaslab selection, we will continue
 * allocating from the active metaslab until we have exhausted
 * zfs_metaslab_switch_threshold of its buckets.
 */
int zfs_metaslab_switch_threshold = 2;

/*
 * Internal switch to enable/disable the metaslab allocation tracing
 * facility.
 */
boolean_t metaslab_trace_enabled = B_TRUE;

/*
 * Maximum entries that the metaslab allocation tracing facility will keep
 * in a given list when running in non-debug mode. We limit the number
 * of entries in non-debug mode to prevent us from using up too much memory.
 * The limit should be sufficiently large that we don't expect any allocation
 * to every exceed this value. In debug mode, the system will panic if this
 * limit is ever reached allowing for further investigation.
 */
uint64_t metaslab_trace_max_entries = 5000;

/*
 * Maximum number of metaslabs per group that can be disabled
 * simultaneously.
 */
int max_disabled_ms = 3;

/*
 * Time (in seconds) to respect ms_max_size when the metaslab is not loaded.
 * To avoid 64-bit overflow, don't set above UINT32_MAX.
 */
unsigned long zfs_metaslab_max_size_cache_sec = 3600; /* 1 hour */

/*
 * Maximum percentage of memory to use on storing loaded metaslabs. If loading
 * a metaslab would take it over this percentage, the oldest selected metaslab
 * is automatically unloaded.
 */
int zfs_metaslab_mem_limit = 75;

/*
 * Force the per-metaslab range trees to use 64-bit integers to store
 * segments. Used for debugging purposes.
 */
boolean_t zfs_metaslab_force_large_segs = B_FALSE;

/*
 * By default we only store segments over a certain size in the size-sorted
 * metaslab trees (ms_allocatable_by_size and
 * ms_unflushed_frees_by_size). This dramatically reduces memory usage and
 * improves load and unload times at the cost of causing us to use slightly
 * larger segments than we would otherwise in some cases.
 */
uint32_t metaslab_by_size_min_shift = 14;

static uint64_t metaslab_weight(metaslab_t *);
static void metaslab_set_fragmentation(metaslab_t *);
static void metaslab_free_impl(vdev_t *, uint64_t, uint64_t, boolean_t);
static void metaslab_check_free_impl(vdev_t *, uint64_t, uint64_t);
static void metaslab_passivate(metaslab_t *msp, uint64_t weight);
static uint64_t metaslab_weight_from_range_tree(metaslab_t *msp);
static void metaslab_flush_update(metaslab_t *, dmu_tx_t *);
static unsigned int metaslab_idx_func(multilist_t *, void *);
static void metaslab_evict(metaslab_t *, uint64_t);
static void metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg);

kmem_cache_t *metaslab_alloc_trace_cache;

typedef struct metaslab_stats {
	kstat_named_t metaslabstat_trace_over_limit;
	kstat_named_t metaslabstat_df_find_under_floor;
	kstat_named_t metaslabstat_reload_tree;
} metaslab_stats_t;

static metaslab_stats_t metaslab_stats = {
	{ "trace_over_limit",		KSTAT_DATA_UINT64 },
	{ "df_find_under_floor",	KSTAT_DATA_UINT64 },
	{ "reload_tree",		KSTAT_DATA_UINT64 },
};

#define	METASLABSTAT_BUMP(stat) \
	atomic_inc_64(&metaslab_stats.stat.value.ui64);


kstat_t *metaslab_ksp;

void
metaslab_stat_init(void)
{
	ASSERT(metaslab_alloc_trace_cache == NULL);
	metaslab_alloc_trace_cache = kmem_cache_create(
	    "metaslab_alloc_trace_cache", sizeof (metaslab_alloc_trace_t),
	    0, NULL, NULL, NULL, NULL, NULL, 0);
	metaslab_ksp = kstat_create("zfs", 0, "metaslab_stats",
	    "misc", KSTAT_TYPE_NAMED, sizeof (metaslab_stats) /
	    sizeof (kstat_named_t), KSTAT_FLAG_VIRTUAL);
	if (metaslab_ksp != NULL) {
		metaslab_ksp->ks_data = &metaslab_stats;
		kstat_install(metaslab_ksp);
	}
}

void
metaslab_stat_fini(void)
{
	if (metaslab_ksp != NULL) {
		kstat_delete(metaslab_ksp);
		metaslab_ksp = NULL;
	}

	kmem_cache_destroy(metaslab_alloc_trace_cache);
	metaslab_alloc_trace_cache = NULL;
}

/*
 * ==========================================================================
 * Metaslab classes
 * ==========================================================================
 */
metaslab_class_t *
metaslab_class_create(spa_t *spa, metaslab_ops_t *ops)
{
	metaslab_class_t *mc;

	mc = kmem_zalloc(sizeof (metaslab_class_t), KM_SLEEP);

	mc->mc_spa = spa;
	mc->mc_rotor = NULL;
	mc->mc_ops = ops;
	mutex_init(&mc->mc_lock, NULL, MUTEX_DEFAULT, NULL);
	mc->mc_metaslab_txg_list = multilist_create(sizeof (metaslab_t),
	    offsetof(metaslab_t, ms_class_txg_node), metaslab_idx_func);
	mc->mc_alloc_slots = kmem_zalloc(spa->spa_alloc_count *
	    sizeof (zfs_refcount_t), KM_SLEEP);
	mc->mc_alloc_max_slots = kmem_zalloc(spa->spa_alloc_count *
	    sizeof (uint64_t), KM_SLEEP);
	for (int i = 0; i < spa->spa_alloc_count; i++)
		zfs_refcount_create_tracked(&mc->mc_alloc_slots[i]);

	return (mc);
}

void
metaslab_class_destroy(metaslab_class_t *mc)
{
	ASSERT(mc->mc_rotor == NULL);
	ASSERT(mc->mc_alloc == 0);
	ASSERT(mc->mc_deferred == 0);
	ASSERT(mc->mc_space == 0);
	ASSERT(mc->mc_dspace == 0);

	for (int i = 0; i < mc->mc_spa->spa_alloc_count; i++)
		zfs_refcount_destroy(&mc->mc_alloc_slots[i]);
	kmem_free(mc->mc_alloc_slots, mc->mc_spa->spa_alloc_count *
	    sizeof (zfs_refcount_t));
	kmem_free(mc->mc_alloc_max_slots, mc->mc_spa->spa_alloc_count *
	    sizeof (uint64_t));
	mutex_destroy(&mc->mc_lock);
	multilist_destroy(mc->mc_metaslab_txg_list);
	kmem_free(mc, sizeof (metaslab_class_t));
}

int
metaslab_class_validate(metaslab_class_t *mc)
{
	metaslab_group_t *mg;
	vdev_t *vd;

	/*
	 * Must hold one of the spa_config locks.
	 */
	ASSERT(spa_config_held(mc->mc_spa, SCL_ALL, RW_READER) ||
	    spa_config_held(mc->mc_spa, SCL_ALL, RW_WRITER));

	if ((mg = mc->mc_rotor) == NULL)
		return (0);

	do {
		vd = mg->mg_vd;
		ASSERT(vd->vdev_mg != NULL);
		ASSERT3P(vd->vdev_top, ==, vd);
		ASSERT3P(mg->mg_class, ==, mc);
		ASSERT3P(vd->vdev_ops, !=, &vdev_hole_ops);
	} while ((mg = mg->mg_next) != mc->mc_rotor);

	return (0);
}

static void
metaslab_class_space_update(metaslab_class_t *mc, int64_t alloc_delta,
    int64_t defer_delta, int64_t space_delta, int64_t dspace_delta)
{
	atomic_add_64(&mc->mc_alloc, alloc_delta);
	atomic_add_64(&mc->mc_deferred, defer_delta);
	atomic_add_64(&mc->mc_space, space_delta);
	atomic_add_64(&mc->mc_dspace, dspace_delta);
}

uint64_t
metaslab_class_get_alloc(metaslab_class_t *mc)
{
	return (mc->mc_alloc);
}

uint64_t
metaslab_class_get_deferred(metaslab_class_t *mc)
{
	return (mc->mc_deferred);
}

uint64_t
metaslab_class_get_space(metaslab_class_t *mc)
{
	return (mc->mc_space);
}

uint64_t
metaslab_class_get_dspace(metaslab_class_t *mc)
{
	return (spa_deflate(mc->mc_spa) ? mc->mc_dspace : mc->mc_space);
}

void
metaslab_class_histogram_verify(metaslab_class_t *mc)
{
	spa_t *spa = mc->mc_spa;
	vdev_t *rvd = spa->spa_root_vdev;
	uint64_t *mc_hist;
	int i;

	if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0)
		return;

	mc_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE,
	    KM_SLEEP);

	for (int c = 0; c < rvd->vdev_children; c++) {
		vdev_t *tvd = rvd->vdev_child[c];
		metaslab_group_t *mg = tvd->vdev_mg;

		/*
		 * Skip any holes, uninitialized top-levels, or
		 * vdevs that are not in this metalab class.
		 */
		if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 ||
		    mg->mg_class != mc) {
			continue;
		}

		for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++)
			mc_hist[i] += mg->mg_histogram[i];
	}

	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++)
		VERIFY3U(mc_hist[i], ==, mc->mc_histogram[i]);

	kmem_free(mc_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE);
}

/*
 * Calculate the metaslab class's fragmentation metric. The metric
 * is weighted based on the space contribution of each metaslab group.
 * The return value will be a number between 0 and 100 (inclusive), or
 * ZFS_FRAG_INVALID if the metric has not been set. See comment above the
 * zfs_frag_table for more information about the metric.
 */
uint64_t
metaslab_class_fragmentation(metaslab_class_t *mc)
{
	vdev_t *rvd = mc->mc_spa->spa_root_vdev;
	uint64_t fragmentation = 0;

	spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER);

	for (int c = 0; c < rvd->vdev_children; c++) {
		vdev_t *tvd = rvd->vdev_child[c];
		metaslab_group_t *mg = tvd->vdev_mg;

		/*
		 * Skip any holes, uninitialized top-levels,
		 * or vdevs that are not in this metalab class.
		 */
		if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 ||
		    mg->mg_class != mc) {
			continue;
		}

		/*
		 * If a metaslab group does not contain a fragmentation
		 * metric then just bail out.
		 */
		if (mg->mg_fragmentation == ZFS_FRAG_INVALID) {
			spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG);
			return (ZFS_FRAG_INVALID);
		}

		/*
		 * Determine how much this metaslab_group is contributing
		 * to the overall pool fragmentation metric.
		 */
		fragmentation += mg->mg_fragmentation *
		    metaslab_group_get_space(mg);
	}
	fragmentation /= metaslab_class_get_space(mc);

	ASSERT3U(fragmentation, <=, 100);
	spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG);
	return (fragmentation);
}

/*
 * Calculate the amount of expandable space that is available in
 * this metaslab class. If a device is expanded then its expandable
 * space will be the amount of allocatable space that is currently not
 * part of this metaslab class.
 */
uint64_t
metaslab_class_expandable_space(metaslab_class_t *mc)
{
	vdev_t *rvd = mc->mc_spa->spa_root_vdev;
	uint64_t space = 0;

	spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER);
	for (int c = 0; c < rvd->vdev_children; c++) {
		uint64_t tspace;
		vdev_t *tvd = rvd->vdev_child[c];
		metaslab_group_t *mg = tvd->vdev_mg;

		if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 ||
		    mg->mg_class != mc) {
			continue;
		}

		/*
		 * Calculate if we have enough space to add additional
		 * metaslabs. We report the expandable space in terms
		 * of the metaslab size since that's the unit of expansion.
		 * Adjust by efi system partition size.
		 */
		tspace = tvd->vdev_max_asize - tvd->vdev_asize;
		if (tspace > mc->mc_spa->spa_bootsize) {
			tspace -= mc->mc_spa->spa_bootsize;
		}
		space += P2ALIGN(tspace, 1ULL << tvd->vdev_ms_shift);
	}
	spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG);
	return (space);
}

void
metaslab_class_evict_old(metaslab_class_t *mc, uint64_t txg)
{
	multilist_t *ml = mc->mc_metaslab_txg_list;
	for (int i = 0; i < multilist_get_num_sublists(ml); i++) {
		multilist_sublist_t *mls = multilist_sublist_lock(ml, i);
		metaslab_t *msp = multilist_sublist_head(mls);
		multilist_sublist_unlock(mls);
		while (msp != NULL) {
			mutex_enter(&msp->ms_lock);

			/*
			 * If the metaslab has been removed from the list
			 * (which could happen if we were at the memory limit
			 * and it was evicted during this loop), then we can't
			 * proceed and we should restart the sublist.
			 */
			if (!multilist_link_active(&msp->ms_class_txg_node)) {
				mutex_exit(&msp->ms_lock);
				i--;
				break;
			}
			mls = multilist_sublist_lock(ml, i);
			metaslab_t *next_msp = multilist_sublist_next(mls, msp);
			multilist_sublist_unlock(mls);
			if (txg >
			    msp->ms_selected_txg + metaslab_unload_delay &&
			    gethrtime() > msp->ms_selected_time +
			    (uint64_t)MSEC2NSEC(metaslab_unload_delay_ms)) {
				metaslab_evict(msp, txg);
			} else {
				/*
				 * Once we've hit a metaslab selected too
				 * recently to evict, we're done evicting for
				 * now.
				 */
				mutex_exit(&msp->ms_lock);
				break;
			}
			mutex_exit(&msp->ms_lock);
			msp = next_msp;
		}
	}
}

static int
metaslab_compare(const void *x1, const void *x2)
{
	const metaslab_t *m1 = (const metaslab_t *)x1;
	const metaslab_t *m2 = (const metaslab_t *)x2;

	int sort1 = 0;
	int sort2 = 0;
	if (m1->ms_allocator != -1 && m1->ms_primary)
		sort1 = 1;
	else if (m1->ms_allocator != -1 && !m1->ms_primary)
		sort1 = 2;
	if (m2->ms_allocator != -1 && m2->ms_primary)
		sort2 = 1;
	else if (m2->ms_allocator != -1 && !m2->ms_primary)
		sort2 = 2;

	/*
	 * Sort inactive metaslabs first, then primaries, then secondaries. When
	 * selecting a metaslab to allocate from, an allocator first tries its
	 * primary, then secondary active metaslab. If it doesn't have active
	 * metaslabs, or can't allocate from them, it searches for an inactive
	 * metaslab to activate. If it can't find a suitable one, it will steal
	 * a primary or secondary metaslab from another allocator.
	 */
	if (sort1 < sort2)
		return (-1);
	if (sort1 > sort2)
		return (1);

	int cmp = TREE_CMP(m2->ms_weight, m1->ms_weight);
	if (likely(cmp))
		return (cmp);

	IMPLY(TREE_CMP(m1->ms_start, m2->ms_start) == 0, m1 == m2);

	return (TREE_CMP(m1->ms_start, m2->ms_start));
}

/*
 * ==========================================================================
 * Metaslab groups
 * ==========================================================================
 */
/*
 * Update the allocatable flag and the metaslab group's capacity.
 * The allocatable flag is set to true if the capacity is below
 * the zfs_mg_noalloc_threshold or has a fragmentation value that is
 * greater than zfs_mg_fragmentation_threshold. If a metaslab group
 * transitions from allocatable to non-allocatable or vice versa then the
 * metaslab group's class is updated to reflect the transition.
 */
static void
metaslab_group_alloc_update(metaslab_group_t *mg)
{
	vdev_t *vd = mg->mg_vd;
	metaslab_class_t *mc = mg->mg_class;
	vdev_stat_t *vs = &vd->vdev_stat;
	boolean_t was_allocatable;
	boolean_t was_initialized;

	ASSERT(vd == vd->vdev_top);
	ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_READER), ==,
	    SCL_ALLOC);

	mutex_enter(&mg->mg_lock);
	was_allocatable = mg->mg_allocatable;
	was_initialized = mg->mg_initialized;

	mg->mg_free_capacity = ((vs->vs_space - vs->vs_alloc) * 100) /
	    (vs->vs_space + 1);

	mutex_enter(&mc->mc_lock);

	/*
	 * If the metaslab group was just added then it won't
	 * have any space until we finish syncing out this txg.
	 * At that point we will consider it initialized and available
	 * for allocations.  We also don't consider non-activated
	 * metaslab groups (e.g. vdevs that are in the middle of being removed)
	 * to be initialized, because they can't be used for allocation.
	 */
	mg->mg_initialized = metaslab_group_initialized(mg);
	if (!was_initialized && mg->mg_initialized) {
		mc->mc_groups++;
	} else if (was_initialized && !mg->mg_initialized) {
		ASSERT3U(mc->mc_groups, >, 0);
		mc->mc_groups--;
	}
	if (mg->mg_initialized)
		mg->mg_no_free_space = B_FALSE;

	/*
	 * A metaslab group is considered allocatable if it has plenty
	 * of free space or is not heavily fragmented. We only take
	 * fragmentation into account if the metaslab group has a valid
	 * fragmentation metric (i.e. a value between 0 and 100).
	 */
	mg->mg_allocatable = (mg->mg_activation_count > 0 &&
	    mg->mg_free_capacity > zfs_mg_noalloc_threshold &&
	    (mg->mg_fragmentation == ZFS_FRAG_INVALID ||
	    mg->mg_fragmentation <= zfs_mg_fragmentation_threshold));

	/*
	 * The mc_alloc_groups maintains a count of the number of
	 * groups in this metaslab class that are still above the
	 * zfs_mg_noalloc_threshold. This is used by the allocating
	 * threads to determine if they should avoid allocations to
	 * a given group. The allocator will avoid allocations to a group
	 * if that group has reached or is below the zfs_mg_noalloc_threshold
	 * and there are still other groups that are above the threshold.
	 * When a group transitions from allocatable to non-allocatable or
	 * vice versa we update the metaslab class to reflect that change.
	 * When the mc_alloc_groups value drops to 0 that means that all
	 * groups have reached the zfs_mg_noalloc_threshold making all groups
	 * eligible for allocations. This effectively means that all devices
	 * are balanced again.
	 */
	if (was_allocatable && !mg->mg_allocatable)
		mc->mc_alloc_groups--;
	else if (!was_allocatable && mg->mg_allocatable)
		mc->mc_alloc_groups++;
	mutex_exit(&mc->mc_lock);

	mutex_exit(&mg->mg_lock);
}

int
metaslab_sort_by_flushed(const void *va, const void *vb)
{
	const metaslab_t *a = va;
	const metaslab_t *b = vb;

	int cmp = TREE_CMP(a->ms_unflushed_txg, b->ms_unflushed_txg);
	if (likely(cmp))
		return (cmp);

	uint64_t a_vdev_id = a->ms_group->mg_vd->vdev_id;
	uint64_t b_vdev_id = b->ms_group->mg_vd->vdev_id;
	cmp = TREE_CMP(a_vdev_id, b_vdev_id);
	if (cmp)
		return (cmp);

	return (TREE_CMP(a->ms_id, b->ms_id));
}

metaslab_group_t *
metaslab_group_create(metaslab_class_t *mc, vdev_t *vd, int allocators)
{
	metaslab_group_t *mg;

	mg = kmem_zalloc(sizeof (metaslab_group_t), KM_SLEEP);
	mutex_init(&mg->mg_lock, NULL, MUTEX_DEFAULT, NULL);
	mutex_init(&mg->mg_ms_disabled_lock, NULL, MUTEX_DEFAULT, NULL);
	cv_init(&mg->mg_ms_disabled_cv, NULL, CV_DEFAULT, NULL);
	mg->mg_primaries = kmem_zalloc(allocators * sizeof (metaslab_t *),
	    KM_SLEEP);
	mg->mg_secondaries = kmem_zalloc(allocators * sizeof (metaslab_t *),
	    KM_SLEEP);
	avl_create(&mg->mg_metaslab_tree, metaslab_compare,
	    sizeof (metaslab_t), offsetof(metaslab_t, ms_group_node));
	mg->mg_vd = vd;
	mg->mg_class = mc;
	mg->mg_activation_count = 0;
	mg->mg_initialized = B_FALSE;
	mg->mg_no_free_space = B_TRUE;
	mg->mg_allocators = allocators;

	mg->mg_alloc_queue_depth = kmem_zalloc(allocators *
	    sizeof (zfs_refcount_t), KM_SLEEP);
	mg->mg_cur_max_alloc_queue_depth = kmem_zalloc(allocators *
	    sizeof (uint64_t), KM_SLEEP);
	for (int i = 0; i < allocators; i++) {
		zfs_refcount_create_tracked(&mg->mg_alloc_queue_depth[i]);
		mg->mg_cur_max_alloc_queue_depth[i] = 0;
	}

	mg->mg_taskq = taskq_create("metaslab_group_taskq", metaslab_load_pct,
	    minclsyspri, 10, INT_MAX, TASKQ_THREADS_CPU_PCT);

	return (mg);
}

void
metaslab_group_destroy(metaslab_group_t *mg)
{
	ASSERT(mg->mg_prev == NULL);
	ASSERT(mg->mg_next == NULL);
	/*
	 * We may have gone below zero with the activation count
	 * either because we never activated in the first place or
	 * because we're done, and possibly removing the vdev.
	 */
	ASSERT(mg->mg_activation_count <= 0);

	taskq_destroy(mg->mg_taskq);
	avl_destroy(&mg->mg_metaslab_tree);
	kmem_free(mg->mg_primaries, mg->mg_allocators * sizeof (metaslab_t *));
	kmem_free(mg->mg_secondaries, mg->mg_allocators *
	    sizeof (metaslab_t *));
	mutex_destroy(&mg->mg_lock);
	mutex_destroy(&mg->mg_ms_disabled_lock);
	cv_destroy(&mg->mg_ms_disabled_cv);

	for (int i = 0; i < mg->mg_allocators; i++) {
		zfs_refcount_destroy(&mg->mg_alloc_queue_depth[i]);
		mg->mg_cur_max_alloc_queue_depth[i] = 0;
	}
	kmem_free(mg->mg_alloc_queue_depth, mg->mg_allocators *
	    sizeof (zfs_refcount_t));
	kmem_free(mg->mg_cur_max_alloc_queue_depth, mg->mg_allocators *
	    sizeof (uint64_t));

	kmem_free(mg, sizeof (metaslab_group_t));
}

void
metaslab_group_activate(metaslab_group_t *mg)
{
	metaslab_class_t *mc = mg->mg_class;
	metaslab_group_t *mgprev, *mgnext;

	ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_WRITER), !=, 0);

	ASSERT(mc->mc_rotor != mg);
	ASSERT(mg->mg_prev == NULL);
	ASSERT(mg->mg_next == NULL);
	ASSERT(mg->mg_activation_count <= 0);

	if (++mg->mg_activation_count <= 0)
		return;

	mg->mg_aliquot = metaslab_aliquot * MAX(1, mg->mg_vd->vdev_children);
	metaslab_group_alloc_update(mg);

	if ((mgprev = mc->mc_rotor) == NULL) {
		mg->mg_prev = mg;
		mg->mg_next = mg;
	} else {
		mgnext = mgprev->mg_next;
		mg->mg_prev = mgprev;
		mg->mg_next = mgnext;
		mgprev->mg_next = mg;
		mgnext->mg_prev = mg;
	}
	mc->mc_rotor = mg;
}

/*
 * Passivate a metaslab group and remove it from the allocation rotor.
 * Callers must hold both the SCL_ALLOC and SCL_ZIO lock prior to passivating
 * a metaslab group. This function will momentarily drop spa_config_locks
 * that are lower than the SCL_ALLOC lock (see comment below).
 */
void
metaslab_group_passivate(metaslab_group_t *mg)
{
	metaslab_class_t *mc = mg->mg_class;
	spa_t *spa = mc->mc_spa;
	metaslab_group_t *mgprev, *mgnext;
	int locks = spa_config_held(spa, SCL_ALL, RW_WRITER);

	ASSERT3U(spa_config_held(spa, SCL_ALLOC | SCL_ZIO, RW_WRITER), ==,
	    (SCL_ALLOC | SCL_ZIO));

	if (--mg->mg_activation_count != 0) {
		ASSERT(mc->mc_rotor != mg);
		ASSERT(mg->mg_prev == NULL);
		ASSERT(mg->mg_next == NULL);
		ASSERT(mg->mg_activation_count < 0);
		return;
	}

	/*
	 * The spa_config_lock is an array of rwlocks, ordered as
	 * follows (from highest to lowest):
	 *	SCL_CONFIG > SCL_STATE > SCL_L2ARC > SCL_ALLOC >
	 *	SCL_ZIO > SCL_FREE > SCL_VDEV
	 * (For more information about the spa_config_lock see spa_misc.c)
	 * The higher the lock, the broader its coverage. When we passivate
	 * a metaslab group, we must hold both the SCL_ALLOC and the SCL_ZIO
	 * config locks. However, the metaslab group's taskq might be trying
	 * to preload metaslabs so we must drop the SCL_ZIO lock and any
	 * lower locks to allow the I/O to complete. At a minimum,
	 * we continue to hold the SCL_ALLOC lock, which prevents any future
	 * allocations from taking place and any changes to the vdev tree.
	 */
	spa_config_exit(spa, locks & ~(SCL_ZIO - 1), spa);
	taskq_wait(mg->mg_taskq);
	spa_config_enter(spa, locks & ~(SCL_ZIO - 1), spa, RW_WRITER);
	metaslab_group_alloc_update(mg);
	for (int i = 0; i < mg->mg_allocators; i++) {
		metaslab_t *msp = mg->mg_primaries[i];
		if (msp != NULL) {
			mutex_enter(&msp->ms_lock);
			metaslab_passivate(msp,
			    metaslab_weight_from_range_tree(msp));
			mutex_exit(&msp->ms_lock);
		}
		msp = mg->mg_secondaries[i];
		if (msp != NULL) {
			mutex_enter(&msp->ms_lock);
			metaslab_passivate(msp,
			    metaslab_weight_from_range_tree(msp));
			mutex_exit(&msp->ms_lock);
		}
	}

	mgprev = mg->mg_prev;
	mgnext = mg->mg_next;

	if (mg == mgnext) {
		mc->mc_rotor = NULL;
	} else {
		mc->mc_rotor = mgnext;
		mgprev->mg_next = mgnext;
		mgnext->mg_prev = mgprev;
	}

	mg->mg_prev = NULL;
	mg->mg_next = NULL;
}

boolean_t
metaslab_group_initialized(metaslab_group_t *mg)
{
	vdev_t *vd = mg->mg_vd;
	vdev_stat_t *vs = &vd->vdev_stat;

	return (vs->vs_space != 0 && mg->mg_activation_count > 0);
}

uint64_t
metaslab_group_get_space(metaslab_group_t *mg)
{
	return ((1ULL << mg->mg_vd->vdev_ms_shift) * mg->mg_vd->vdev_ms_count);
}

void
metaslab_group_histogram_verify(metaslab_group_t *mg)
{
	uint64_t *mg_hist;
	vdev_t *vd = mg->mg_vd;
	uint64_t ashift = vd->vdev_ashift;
	int i;

	if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0)
		return;

	mg_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE,
	    KM_SLEEP);

	ASSERT3U(RANGE_TREE_HISTOGRAM_SIZE, >=,
	    SPACE_MAP_HISTOGRAM_SIZE + ashift);

	for (int m = 0; m < vd->vdev_ms_count; m++) {
		metaslab_t *msp = vd->vdev_ms[m];

		/* skip if not active or not a member */
		if (msp->ms_sm == NULL || msp->ms_group != mg)
			continue;

		for (i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++)
			mg_hist[i + ashift] +=
			    msp->ms_sm->sm_phys->smp_histogram[i];
	}

	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i ++)
		VERIFY3U(mg_hist[i], ==, mg->mg_histogram[i]);

	kmem_free(mg_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE);
}

static void
metaslab_group_histogram_add(metaslab_group_t *mg, metaslab_t *msp)
{
	metaslab_class_t *mc = mg->mg_class;
	uint64_t ashift = mg->mg_vd->vdev_ashift;

	ASSERT(MUTEX_HELD(&msp->ms_lock));
	if (msp->ms_sm == NULL)
		return;

	mutex_enter(&mg->mg_lock);
	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
		mg->mg_histogram[i + ashift] +=
		    msp->ms_sm->sm_phys->smp_histogram[i];
		mc->mc_histogram[i + ashift] +=
		    msp->ms_sm->sm_phys->smp_histogram[i];
	}
	mutex_exit(&mg->mg_lock);
}

void
metaslab_group_histogram_remove(metaslab_group_t *mg, metaslab_t *msp)
{
	metaslab_class_t *mc = mg->mg_class;
	uint64_t ashift = mg->mg_vd->vdev_ashift;

	ASSERT(MUTEX_HELD(&msp->ms_lock));
	if (msp->ms_sm == NULL)
		return;

	mutex_enter(&mg->mg_lock);
	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
		ASSERT3U(mg->mg_histogram[i + ashift], >=,
		    msp->ms_sm->sm_phys->smp_histogram[i]);
		ASSERT3U(mc->mc_histogram[i + ashift], >=,
		    msp->ms_sm->sm_phys->smp_histogram[i]);

		mg->mg_histogram[i + ashift] -=
		    msp->ms_sm->sm_phys->smp_histogram[i];
		mc->mc_histogram[i + ashift] -=
		    msp->ms_sm->sm_phys->smp_histogram[i];
	}
	mutex_exit(&mg->mg_lock);
}

static void
metaslab_group_add(metaslab_group_t *mg, metaslab_t *msp)
{
	ASSERT(msp->ms_group == NULL);
	mutex_enter(&mg->mg_lock);
	msp->ms_group = mg;
	msp->ms_weight = 0;
	avl_add(&mg->mg_metaslab_tree, msp);
	mutex_exit(&mg->mg_lock);

	mutex_enter(&msp->ms_lock);
	metaslab_group_histogram_add(mg, msp);
	mutex_exit(&msp->ms_lock);
}

static void
metaslab_group_remove(metaslab_group_t *mg, metaslab_t *msp)
{
	mutex_enter(&msp->ms_lock);
	metaslab_group_histogram_remove(mg, msp);
	mutex_exit(&msp->ms_lock);

	mutex_enter(&mg->mg_lock);
	ASSERT(msp->ms_group == mg);
	avl_remove(&mg->mg_metaslab_tree, msp);

	metaslab_class_t *mc = msp->ms_group->mg_class;
	multilist_sublist_t *mls =
	    multilist_sublist_lock_obj(mc->mc_metaslab_txg_list, msp);
	if (multilist_link_active(&msp->ms_class_txg_node))
		multilist_sublist_remove(mls, msp);
	multilist_sublist_unlock(mls);

	msp->ms_group = NULL;
	mutex_exit(&mg->mg_lock);
}

static void
metaslab_group_sort_impl(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));
	ASSERT(MUTEX_HELD(&mg->mg_lock));
	ASSERT(msp->ms_group == mg);

	avl_remove(&mg->mg_metaslab_tree, msp);
	msp->ms_weight = weight;
	avl_add(&mg->mg_metaslab_tree, msp);

}

static void
metaslab_group_sort(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight)
{
	/*
	 * Although in principle the weight can be any value, in
	 * practice we do not use values in the range [1, 511].
	 */
	ASSERT(weight >= SPA_MINBLOCKSIZE || weight == 0);
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	mutex_enter(&mg->mg_lock);
	metaslab_group_sort_impl(mg, msp, weight);
	mutex_exit(&mg->mg_lock);
}

/*
 * Calculate the fragmentation for a given metaslab group. We can use
 * a simple average here since all metaslabs within the group must have
 * the same size. The return value will be a value between 0 and 100
 * (inclusive), or ZFS_FRAG_INVALID if less than half of the metaslab in this
 * group have a fragmentation metric.
 */
uint64_t
metaslab_group_fragmentation(metaslab_group_t *mg)
{
	vdev_t *vd = mg->mg_vd;
	uint64_t fragmentation = 0;
	uint64_t valid_ms = 0;

	for (int m = 0; m < vd->vdev_ms_count; m++) {
		metaslab_t *msp = vd->vdev_ms[m];

		if (msp->ms_fragmentation == ZFS_FRAG_INVALID)
			continue;
		if (msp->ms_group != mg)
			continue;

		valid_ms++;
		fragmentation += msp->ms_fragmentation;
	}

	if (valid_ms <= mg->mg_vd->vdev_ms_count / 2)
		return (ZFS_FRAG_INVALID);

	fragmentation /= valid_ms;
	ASSERT3U(fragmentation, <=, 100);
	return (fragmentation);
}

/*
 * Determine if a given metaslab group should skip allocations. A metaslab
 * group should avoid allocations if its free capacity is less than the
 * zfs_mg_noalloc_threshold or its fragmentation metric is greater than
 * zfs_mg_fragmentation_threshold and there is at least one metaslab group
 * that can still handle allocations. If the allocation throttle is enabled
 * then we skip allocations to devices that have reached their maximum
 * allocation queue depth unless the selected metaslab group is the only
 * eligible group remaining.
 */
static boolean_t
metaslab_group_allocatable(metaslab_group_t *mg, metaslab_group_t *rotor,
    uint64_t psize, int allocator, int d)
{
	spa_t *spa = mg->mg_vd->vdev_spa;
	metaslab_class_t *mc = mg->mg_class;

	/*
	 * We can only consider skipping this metaslab group if it's
	 * in the normal metaslab class and there are other metaslab
	 * groups to select from. Otherwise, we always consider it eligible
	 * for allocations.
	 */
	if ((mc != spa_normal_class(spa) &&
	    mc != spa_special_class(spa) &&
	    mc != spa_dedup_class(spa)) ||
	    mc->mc_groups <= 1)
		return (B_TRUE);

	/*
	 * If the metaslab group's mg_allocatable flag is set (see comments
	 * in metaslab_group_alloc_update() for more information) and
	 * the allocation throttle is disabled then allow allocations to this
	 * device. However, if the allocation throttle is enabled then
	 * check if we have reached our allocation limit (mg_alloc_queue_depth)
	 * to determine if we should allow allocations to this metaslab group.
	 * If all metaslab groups are no longer considered allocatable
	 * (mc_alloc_groups == 0) or we're trying to allocate the smallest
	 * gang block size then we allow allocations on this metaslab group
	 * regardless of the mg_allocatable or throttle settings.
	 */
	if (mg->mg_allocatable) {
		metaslab_group_t *mgp;
		int64_t qdepth;
		uint64_t qmax = mg->mg_cur_max_alloc_queue_depth[allocator];

		if (!mc->mc_alloc_throttle_enabled)
			return (B_TRUE);

		/*
		 * If this metaslab group does not have any free space, then
		 * there is no point in looking further.
		 */
		if (mg->mg_no_free_space)
			return (B_FALSE);

		/*
		 * Relax allocation throttling for ditto blocks.  Due to
		 * random imbalances in allocation it tends to push copies
		 * to one vdev, that looks a bit better at the moment.
		 */
		qmax = qmax * (4 + d) / 4;

		qdepth = zfs_refcount_count(
		    &mg->mg_alloc_queue_depth[allocator]);

		/*
		 * If this metaslab group is below its qmax or it's
		 * the only allocatable metasable group, then attempt
		 * to allocate from it.
		 */
		if (qdepth < qmax || mc->mc_alloc_groups == 1)
			return (B_TRUE);
		ASSERT3U(mc->mc_alloc_groups, >, 1);

		/*
		 * Since this metaslab group is at or over its qmax, we
		 * need to determine if there are metaslab groups after this
		 * one that might be able to handle this allocation. This is
		 * racy since we can't hold the locks for all metaslab
		 * groups at the same time when we make this check.
		 */
		for (mgp = mg->mg_next; mgp != rotor; mgp = mgp->mg_next) {
			qmax = mgp->mg_cur_max_alloc_queue_depth[allocator];
			qmax = qmax * (4 + d) / 4;
			qdepth = zfs_refcount_count(
			    &mgp->mg_alloc_queue_depth[allocator]);

			/*
			 * If there is another metaslab group that
			 * might be able to handle the allocation, then
			 * we return false so that we skip this group.
			 */
			if (qdepth < qmax && !mgp->mg_no_free_space)
				return (B_FALSE);
		}

		/*
		 * We didn't find another group to handle the allocation
		 * so we can't skip this metaslab group even though
		 * we are at or over our qmax.
		 */
		return (B_TRUE);

	} else if (mc->mc_alloc_groups == 0 || psize == SPA_MINBLOCKSIZE) {
		return (B_TRUE);
	}
	return (B_FALSE);
}

/*
 * ==========================================================================
 * Range tree callbacks
 * ==========================================================================
 */

/*
 * Comparison function for the private size-ordered tree using 32-bit
 * ranges. Tree is sorted by size, larger sizes at the end of the tree.
 */
static int
metaslab_rangesize32_compare(const void *x1, const void *x2)
{
	const range_seg32_t *r1 = x1;
	const range_seg32_t *r2 = x2;

	uint64_t rs_size1 = r1->rs_end - r1->rs_start;
	uint64_t rs_size2 = r2->rs_end - r2->rs_start;

	int cmp = TREE_CMP(rs_size1, rs_size2);
	if (likely(cmp))
		return (cmp);

	return (TREE_CMP(r1->rs_start, r2->rs_start));
}

/*
 * Comparison function for the private size-ordered tree using 64-bit
 * ranges. Tree is sorted by size, larger sizes at the end of the tree.
 */
static int
metaslab_rangesize64_compare(const void *x1, const void *x2)
{
	const range_seg64_t *r1 = x1;
	const range_seg64_t *r2 = x2;

	uint64_t rs_size1 = r1->rs_end - r1->rs_start;
	uint64_t rs_size2 = r2->rs_end - r2->rs_start;

	int cmp = TREE_CMP(rs_size1, rs_size2);
	if (likely(cmp))
		return (cmp);

	return (TREE_CMP(r1->rs_start, r2->rs_start));
}
typedef struct metaslab_rt_arg {
	zfs_btree_t *mra_bt;
	uint32_t mra_floor_shift;
} metaslab_rt_arg_t;

struct mssa_arg {
	range_tree_t *rt;
	metaslab_rt_arg_t *mra;
};

static void
metaslab_size_sorted_add(void *arg, uint64_t start, uint64_t size)
{
	struct mssa_arg *mssap = arg;
	range_tree_t *rt = mssap->rt;
	metaslab_rt_arg_t *mrap = mssap->mra;
	range_seg_max_t seg = {0};
	rs_set_start(&seg, rt, start);
	rs_set_end(&seg, rt, start + size);
	metaslab_rt_add(rt, &seg, mrap);
}

static void
metaslab_size_tree_full_load(range_tree_t *rt)
{
	metaslab_rt_arg_t *mrap = rt->rt_arg;
#ifdef _METASLAB_TRACING
	METASLABSTAT_BUMP(metaslabstat_reload_tree);
#endif
	ASSERT0(zfs_btree_numnodes(mrap->mra_bt));
	mrap->mra_floor_shift = 0;
	struct mssa_arg arg = {0};
	arg.rt = rt;
	arg.mra = mrap;
	range_tree_walk(rt, metaslab_size_sorted_add, &arg);
}

/*
 * Create any block allocator specific components. The current allocators
 * rely on using both a size-ordered range_tree_t and an array of uint64_t's.
 */
/* ARGSUSED */
static void
metaslab_rt_create(range_tree_t *rt, void *arg)
{
	metaslab_rt_arg_t *mrap = arg;
	zfs_btree_t *size_tree = mrap->mra_bt;

	size_t size;
	int (*compare) (const void *, const void *);
	switch (rt->rt_type) {
	case RANGE_SEG32:
		size = sizeof (range_seg32_t);
		compare = metaslab_rangesize32_compare;
		break;
	case RANGE_SEG64:
		size = sizeof (range_seg64_t);
		compare = metaslab_rangesize64_compare;
		break;
	default:
		panic("Invalid range seg type %d", rt->rt_type);
	}
	zfs_btree_create(size_tree, compare, size);
	mrap->mra_floor_shift = metaslab_by_size_min_shift;
}

/* ARGSUSED */
static void
metaslab_rt_destroy(range_tree_t *rt, void *arg)
{
	metaslab_rt_arg_t *mrap = arg;
	zfs_btree_t *size_tree = mrap->mra_bt;

	zfs_btree_destroy(size_tree);
	kmem_free(mrap, sizeof (*mrap));
}

/* ARGSUSED */
static void
metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg)
{
	metaslab_rt_arg_t *mrap = arg;
	zfs_btree_t *size_tree = mrap->mra_bt;

	if (rs_get_end(rs, rt) - rs_get_start(rs, rt) <
	    (1 << mrap->mra_floor_shift))
		return;

	zfs_btree_add(size_tree, rs);
}

/* ARGSUSED */
static void
metaslab_rt_remove(range_tree_t *rt, range_seg_t *rs, void *arg)
{
	metaslab_rt_arg_t *mrap = arg;
	zfs_btree_t *size_tree = mrap->mra_bt;

	if (rs_get_end(rs, rt) - rs_get_start(rs, rt) < (1 <<
	    mrap->mra_floor_shift))
		return;

	zfs_btree_remove(size_tree, rs);
}

/* ARGSUSED */
static void
metaslab_rt_vacate(range_tree_t *rt, void *arg)
{
	metaslab_rt_arg_t *mrap = arg;
	zfs_btree_t *size_tree = mrap->mra_bt;
	zfs_btree_clear(size_tree);
	zfs_btree_destroy(size_tree);

	metaslab_rt_create(rt, arg);
}

static range_tree_ops_t metaslab_rt_ops = {
	.rtop_create = metaslab_rt_create,
	.rtop_destroy = metaslab_rt_destroy,
	.rtop_add = metaslab_rt_add,
	.rtop_remove = metaslab_rt_remove,
	.rtop_vacate = metaslab_rt_vacate
};

/*
 * ==========================================================================
 * Common allocator routines
 * ==========================================================================
 */

/*
 * Return the maximum contiguous segment within the metaslab.
 */
uint64_t
metaslab_largest_allocatable(metaslab_t *msp)
{
	zfs_btree_t *t = &msp->ms_allocatable_by_size;
	range_seg_t *rs;

	if (t == NULL)
		return (0);
	if (zfs_btree_numnodes(t) == 0)
		metaslab_size_tree_full_load(msp->ms_allocatable);

	rs = zfs_btree_last(t, NULL);
	if (rs == NULL)
		return (0);

	return (rs_get_end(rs, msp->ms_allocatable) - rs_get_start(rs,
	    msp->ms_allocatable));
}

/*
 * Return the maximum contiguous segment within the unflushed frees of this
 * metaslab.
 */
uint64_t
metaslab_largest_unflushed_free(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	if (msp->ms_unflushed_frees == NULL)
		return (0);

	if (zfs_btree_numnodes(&msp->ms_unflushed_frees_by_size) == 0)
		metaslab_size_tree_full_load(msp->ms_unflushed_frees);
	range_seg_t *rs = zfs_btree_last(&msp->ms_unflushed_frees_by_size,
	    NULL);
	if (rs == NULL)
		return (0);

	/*
	 * When a range is freed from the metaslab, that range is added to
	 * both the unflushed frees and the deferred frees. While the block
	 * will eventually be usable, if the metaslab were loaded the range
	 * would not be added to the ms_allocatable tree until TXG_DEFER_SIZE
	 * txgs had passed.  As a result, when attempting to estimate an upper
	 * bound for the largest currently-usable free segment in the
	 * metaslab, we need to not consider any ranges currently in the defer
	 * trees. This algorithm approximates the largest available chunk in
	 * the largest range in the unflushed_frees tree by taking the first
	 * chunk.  While this may be a poor estimate, it should only remain so
	 * briefly and should eventually self-correct as frees are no longer
	 * deferred. Similar logic applies to the ms_freed tree. See
	 * metaslab_load() for more details.
	 *
	 * There are two primary sources of innacuracy in this estimate. Both
	 * are tolerated for performance reasons. The first source is that we
	 * only check the largest segment for overlaps. Smaller segments may
	 * have more favorable overlaps with the other trees, resulting in
	 * larger usable chunks.  Second, we only look at the first chunk in
	 * the largest segment; there may be other usable chunks in the
	 * largest segment, but we ignore them.
	 */
	uint64_t rstart = rs_get_start(rs, msp->ms_unflushed_frees);
	uint64_t rsize = rs_get_end(rs, msp->ms_unflushed_frees) - rstart;
	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
		uint64_t start = 0;
		uint64_t size = 0;
		boolean_t found = range_tree_find_in(msp->ms_defer[t], rstart,
		    rsize, &start, &size);
		if (found) {
			if (rstart == start)
				return (0);
			rsize = start - rstart;
		}
	}

	uint64_t start = 0;
	uint64_t size = 0;
	boolean_t found = range_tree_find_in(msp->ms_freed, rstart,
	    rsize, &start, &size);
	if (found)
		rsize = start - rstart;

	return (rsize);
}

static range_seg_t *
metaslab_block_find(zfs_btree_t *t, range_tree_t *rt, uint64_t start,
    uint64_t size, zfs_btree_index_t *where)
{
	range_seg_t *rs;
	range_seg_max_t rsearch;

	rs_set_start(&rsearch, rt, start);
	rs_set_end(&rsearch, rt, start + size);

	rs = zfs_btree_find(t, &rsearch, where);
	if (rs == NULL) {
		rs = zfs_btree_next(t, where, where);
	}

	return (rs);
}

/*
 * This is a helper function that can be used by the allocator to find a
 * suitable block to allocate. This will search the specified B-tree looking
 * for a block that matches the specified criteria.
 */
static uint64_t
metaslab_block_picker(range_tree_t *rt, uint64_t *cursor, uint64_t size,
    uint64_t max_search)
{
	if (*cursor == 0)
		*cursor = rt->rt_start;
	zfs_btree_t *bt = &rt->rt_root;
	zfs_btree_index_t where;
	range_seg_t *rs = metaslab_block_find(bt, rt, *cursor, size, &where);
	uint64_t first_found;
	int count_searched = 0;

	if (rs != NULL)
		first_found = rs_get_start(rs, rt);

	while (rs != NULL && (rs_get_start(rs, rt) - first_found <=
	    max_search || count_searched < metaslab_min_search_count)) {
		uint64_t offset = rs_get_start(rs, rt);
		if (offset + size <= rs_get_end(rs, rt)) {
			*cursor = offset + size;
			return (offset);
		}
		rs = zfs_btree_next(bt, &where, &where);
		count_searched++;
	}

	*cursor = 0;
	return (-1ULL);
}

/*
 * ==========================================================================
 * Dynamic Fit (df) block allocator
 *
 * Search for a free chunk of at least this size, starting from the last
 * offset (for this alignment of block) looking for up to
 * metaslab_df_max_search bytes (16MB).  If a large enough free chunk is not
 * found within 16MB, then return a free chunk of exactly the requested size (or
 * larger).
 *
 * If it seems like searching from the last offset will be unproductive, skip
 * that and just return a free chunk of exactly the requested size (or larger).
 * This is based on metaslab_df_alloc_threshold and metaslab_df_free_pct.  This
 * mechanism is probably not very useful and may be removed in the future.
 *
 * The behavior when not searching can be changed to return the largest free
 * chunk, instead of a free chunk of exactly the requested size, by setting
 * metaslab_df_use_largest_segment.
 * ==========================================================================
 */
static uint64_t
metaslab_df_alloc(metaslab_t *msp, uint64_t size)
{
	/*
	 * Find the largest power of 2 block size that evenly divides the
	 * requested size. This is used to try to allocate blocks with similar
	 * alignment from the same area of the metaslab (i.e. same cursor
	 * bucket) but it does not guarantee that other allocations sizes
	 * may exist in the same region.
	 */
	uint64_t align = size & -size;
	uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1];
	range_tree_t *rt = msp->ms_allocatable;
	int free_pct = range_tree_space(rt) * 100 / msp->ms_size;
	uint64_t offset;

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * If we're running low on space, find a segment based on size,
	 * rather than iterating based on offset.
	 */
	if (metaslab_largest_allocatable(msp) < metaslab_df_alloc_threshold ||
	    free_pct < metaslab_df_free_pct) {
		offset = -1;
	} else {
		offset = metaslab_block_picker(rt,
		    cursor, size, metaslab_df_max_search);
	}

	if (offset == -1) {
		range_seg_t *rs;
		if (zfs_btree_numnodes(&msp->ms_allocatable_by_size) == 0)
			metaslab_size_tree_full_load(msp->ms_allocatable);
		if (metaslab_df_use_largest_segment) {
			/* use largest free segment */
			rs = zfs_btree_last(&msp->ms_allocatable_by_size, NULL);
		} else {
			zfs_btree_index_t where;
			/* use segment of this size, or next largest */
#ifdef _METASLAB_TRACING
			metaslab_rt_arg_t *mrap = msp->ms_allocatable->rt_arg;
			if (size < (1 << mrap->mra_floor_shift)) {
				METASLABSTAT_BUMP(
				    metaslabstat_df_find_under_floor);
			}
#endif
			rs = metaslab_block_find(&msp->ms_allocatable_by_size,
			    rt, msp->ms_start, size, &where);
		}
		if (rs != NULL && rs_get_start(rs, rt) + size <= rs_get_end(rs,
		    rt)) {
			offset = rs_get_start(rs, rt);
			*cursor = offset + size;
		}
	}

	return (offset);
}

static metaslab_ops_t metaslab_df_ops = {
	metaslab_df_alloc
};

/*
 * ==========================================================================
 * Cursor fit block allocator -
 * Select the largest region in the metaslab, set the cursor to the beginning
 * of the range and the cursor_end to the end of the range. As allocations
 * are made advance the cursor. Continue allocating from the cursor until
 * the range is exhausted and then find a new range.
 * ==========================================================================
 */
static uint64_t
metaslab_cf_alloc(metaslab_t *msp, uint64_t size)
{
	range_tree_t *rt = msp->ms_allocatable;
	zfs_btree_t *t = &msp->ms_allocatable_by_size;
	uint64_t *cursor = &msp->ms_lbas[0];
	uint64_t *cursor_end = &msp->ms_lbas[1];
	uint64_t offset = 0;

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	ASSERT3U(*cursor_end, >=, *cursor);

	if ((*cursor + size) > *cursor_end) {
		range_seg_t *rs;

		if (zfs_btree_numnodes(t) == 0)
			metaslab_size_tree_full_load(msp->ms_allocatable);
		rs = zfs_btree_last(t, NULL);
		if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) <
		    size)
			return (-1ULL);

		*cursor = rs_get_start(rs, rt);
		*cursor_end = rs_get_end(rs, rt);
	}

	offset = *cursor;
	*cursor += size;

	return (offset);
}

static metaslab_ops_t metaslab_cf_ops = {
	metaslab_cf_alloc
};

/*
 * ==========================================================================
 * New dynamic fit allocator -
 * Select a region that is large enough to allocate 2^metaslab_ndf_clump_shift
 * contiguous blocks. If no region is found then just use the largest segment
 * that remains.
 * ==========================================================================
 */

/*
 * Determines desired number of contiguous blocks (2^metaslab_ndf_clump_shift)
 * to request from the allocator.
 */
uint64_t metaslab_ndf_clump_shift = 4;

static uint64_t
metaslab_ndf_alloc(metaslab_t *msp, uint64_t size)
{
	zfs_btree_t *t = &msp->ms_allocatable->rt_root;
	range_tree_t *rt = msp->ms_allocatable;
	zfs_btree_index_t where;
	range_seg_t *rs;
	range_seg_max_t rsearch;
	uint64_t hbit = highbit64(size);
	uint64_t *cursor = &msp->ms_lbas[hbit - 1];
	uint64_t max_size = metaslab_largest_allocatable(msp);

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	if (max_size < size)
		return (-1ULL);

	rs_set_start(&rsearch, rt, *cursor);
	rs_set_end(&rsearch, rt, *cursor + size);

	rs = zfs_btree_find(t, &rsearch, &where);
	if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) < size) {
		t = &msp->ms_allocatable_by_size;

		rs_set_start(&rsearch, rt, 0);
		rs_set_end(&rsearch, rt, MIN(max_size, 1ULL << (hbit +
		    metaslab_ndf_clump_shift)));

		rs = zfs_btree_find(t, &rsearch, &where);
		if (rs == NULL)
			rs = zfs_btree_next(t, &where, &where);
		ASSERT(rs != NULL);
	}

	if ((rs_get_end(rs, rt) - rs_get_start(rs, rt)) >= size) {
		*cursor = rs_get_start(rs, rt) + size;
		return (rs_get_start(rs, rt));
	}
	return (-1ULL);
}

static metaslab_ops_t metaslab_ndf_ops = {
	metaslab_ndf_alloc
};

metaslab_ops_t *zfs_metaslab_ops = &metaslab_df_ops;

/*
 * ==========================================================================
 * Metaslabs
 * ==========================================================================
 */

/*
 * Wait for any in-progress metaslab loads to complete.
 */
void
metaslab_load_wait(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	while (msp->ms_loading) {
		ASSERT(!msp->ms_loaded);
		cv_wait(&msp->ms_load_cv, &msp->ms_lock);
	}
}

/*
 * Wait for any in-progress flushing to complete.
 */
void
metaslab_flush_wait(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	while (msp->ms_flushing)
		cv_wait(&msp->ms_flush_cv, &msp->ms_lock);
}

static unsigned int
metaslab_idx_func(multilist_t *ml, void *arg)
{
	metaslab_t *msp = arg;
	return (msp->ms_id % multilist_get_num_sublists(ml));
}

uint64_t
metaslab_allocated_space(metaslab_t *msp)
{
	return (msp->ms_allocated_space);
}

/*
 * Verify that the space accounting on disk matches the in-core range_trees.
 */
static void
metaslab_verify_space(metaslab_t *msp, uint64_t txg)
{
	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
	uint64_t allocating = 0;
	uint64_t sm_free_space, msp_free_space;

	ASSERT(MUTEX_HELD(&msp->ms_lock));
	ASSERT(!msp->ms_condensing);

	if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0)
		return;

	/*
	 * We can only verify the metaslab space when we're called
	 * from syncing context with a loaded metaslab that has an
	 * allocated space map. Calling this in non-syncing context
	 * does not provide a consistent view of the metaslab since
	 * we're performing allocations in the future.
	 */
	if (txg != spa_syncing_txg(spa) || msp->ms_sm == NULL ||
	    !msp->ms_loaded)
		return;

	/*
	 * Even though the smp_alloc field can get negative,
	 * when it comes to a metaslab's space map, that should
	 * never be the case.
	 */
	ASSERT3S(space_map_allocated(msp->ms_sm), >=, 0);

	ASSERT3U(space_map_allocated(msp->ms_sm), >=,
	    range_tree_space(msp->ms_unflushed_frees));

	ASSERT3U(metaslab_allocated_space(msp), ==,
	    space_map_allocated(msp->ms_sm) +
	    range_tree_space(msp->ms_unflushed_allocs) -
	    range_tree_space(msp->ms_unflushed_frees));

	sm_free_space = msp->ms_size - metaslab_allocated_space(msp);

	/*
	 * Account for future allocations since we would have
	 * already deducted that space from the ms_allocatable.
	 */
	for (int t = 0; t < TXG_CONCURRENT_STATES; t++) {
		allocating +=
		    range_tree_space(msp->ms_allocating[(txg + t) & TXG_MASK]);
	}
	ASSERT3U(allocating + msp->ms_allocated_this_txg, ==,
	    msp->ms_allocating_total);

	ASSERT3U(msp->ms_deferspace, ==,
	    range_tree_space(msp->ms_defer[0]) +
	    range_tree_space(msp->ms_defer[1]));

	msp_free_space = range_tree_space(msp->ms_allocatable) + allocating +
	    msp->ms_deferspace + range_tree_space(msp->ms_freed);

	VERIFY3U(sm_free_space, ==, msp_free_space);
}

static void
metaslab_aux_histograms_clear(metaslab_t *msp)
{
	/*
	 * Auxiliary histograms are only cleared when resetting them,
	 * which can only happen while the metaslab is loaded.
	 */
	ASSERT(msp->ms_loaded);

	bzero(msp->ms_synchist, sizeof (msp->ms_synchist));
	for (int t = 0; t < TXG_DEFER_SIZE; t++)
		bzero(msp->ms_deferhist[t], sizeof (msp->ms_deferhist[t]));
}

static void
metaslab_aux_histogram_add(uint64_t *histogram, uint64_t shift,
    range_tree_t *rt)
{
	/*
	 * This is modeled after space_map_histogram_add(), so refer to that
	 * function for implementation details. We want this to work like
	 * the space map histogram, and not the range tree histogram, as we
	 * are essentially constructing a delta that will be later subtracted
	 * from the space map histogram.
	 */
	int idx = 0;
	for (int i = shift; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
		ASSERT3U(i, >=, idx + shift);
		histogram[idx] += rt->rt_histogram[i] << (i - idx - shift);

		if (idx < SPACE_MAP_HISTOGRAM_SIZE - 1) {
			ASSERT3U(idx + shift, ==, i);
			idx++;
			ASSERT3U(idx, <, SPACE_MAP_HISTOGRAM_SIZE);
		}
	}
}

/*
 * Called at every sync pass that the metaslab gets synced.
 *
 * The reason is that we want our auxiliary histograms to be updated
 * wherever the metaslab's space map histogram is updated. This way
 * we stay consistent on which parts of the metaslab space map's
 * histogram are currently not available for allocations (e.g because
 * they are in the defer, freed, and freeing trees).
 */
static void
metaslab_aux_histograms_update(metaslab_t *msp)
{
	space_map_t *sm = msp->ms_sm;
	ASSERT(sm != NULL);

	/*
	 * This is similar to the metaslab's space map histogram updates
	 * that take place in metaslab_sync(). The only difference is that
	 * we only care about segments that haven't made it into the
	 * ms_allocatable tree yet.
	 */
	if (msp->ms_loaded) {
		metaslab_aux_histograms_clear(msp);

		metaslab_aux_histogram_add(msp->ms_synchist,
		    sm->sm_shift, msp->ms_freed);

		for (int t = 0; t < TXG_DEFER_SIZE; t++) {
			metaslab_aux_histogram_add(msp->ms_deferhist[t],
			    sm->sm_shift, msp->ms_defer[t]);
		}
	}

	metaslab_aux_histogram_add(msp->ms_synchist,
	    sm->sm_shift, msp->ms_freeing);
}

/*
 * Called every time we are done syncing (writing to) the metaslab,
 * i.e. at the end of each sync pass.
 * [see the comment in metaslab_impl.h for ms_synchist, ms_deferhist]
 */
static void
metaslab_aux_histograms_update_done(metaslab_t *msp, boolean_t defer_allowed)
{
	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
	space_map_t *sm = msp->ms_sm;

	if (sm == NULL) {
		/*
		 * We came here from metaslab_init() when creating/opening a
		 * pool, looking at a metaslab that hasn't had any allocations
		 * yet.
		 */
		return;
	}

	/*
	 * This is similar to the actions that we take for the ms_freed
	 * and ms_defer trees in metaslab_sync_done().
	 */
	uint64_t hist_index = spa_syncing_txg(spa) % TXG_DEFER_SIZE;
	if (defer_allowed) {
		bcopy(msp->ms_synchist, msp->ms_deferhist[hist_index],
		    sizeof (msp->ms_synchist));
	} else {
		bzero(msp->ms_deferhist[hist_index],
		    sizeof (msp->ms_deferhist[hist_index]));
	}
	bzero(msp->ms_synchist, sizeof (msp->ms_synchist));
}

/*
 * Ensure that the metaslab's weight and fragmentation are consistent
 * with the contents of the histogram (either the range tree's histogram
 * or the space map's depending whether the metaslab is loaded).
 */
static void
metaslab_verify_weight_and_frag(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0)
		return;

	/*
	 * We can end up here from vdev_remove_complete(), in which case we
	 * cannot do these assertions because we hold spa config locks and
	 * thus we are not allowed to read from the DMU.
	 *
	 * We check if the metaslab group has been removed and if that's
	 * the case we return immediately as that would mean that we are
	 * here from the aforementioned code path.
	 */
	if (msp->ms_group == NULL)
		return;

	/*
	 * Devices being removed always return a weight of 0 and leave
	 * fragmentation and ms_max_size as is - there is nothing for
	 * us to verify here.
	 */
	vdev_t *vd = msp->ms_group->mg_vd;
	if (vd->vdev_removing)
		return;

	/*
	 * If the metaslab is dirty it probably means that we've done
	 * some allocations or frees that have changed our histograms
	 * and thus the weight.
	 */
	for (int t = 0; t < TXG_SIZE; t++) {
		if (txg_list_member(&vd->vdev_ms_list, msp, t))
			return;
	}

	/*
	 * This verification checks that our in-memory state is consistent
	 * with what's on disk. If the pool is read-only then there aren't
	 * any changes and we just have the initially-loaded state.
	 */
	if (!spa_writeable(msp->ms_group->mg_vd->vdev_spa))
		return;

	/* some extra verification for in-core tree if you can */
	if (msp->ms_loaded) {
		range_tree_stat_verify(msp->ms_allocatable);
		VERIFY(space_map_histogram_verify(msp->ms_sm,
		    msp->ms_allocatable));
	}

	uint64_t weight = msp->ms_weight;
	uint64_t was_active = msp->ms_weight & METASLAB_ACTIVE_MASK;
	boolean_t space_based = WEIGHT_IS_SPACEBASED(msp->ms_weight);
	uint64_t frag = msp->ms_fragmentation;
	uint64_t max_segsize = msp->ms_max_size;

	msp->ms_weight = 0;
	msp->ms_fragmentation = 0;

	/*
	 * This function is used for verification purposes. Regardless of
	 * whether metaslab_weight() thinks this metaslab should be active or
	 * not, we want to ensure that the actual weight (and therefore the
	 * value of ms_weight) would be the same if it was to be recalculated
	 * at this point.
	 */
	msp->ms_weight = metaslab_weight(msp) | was_active;

	VERIFY3U(max_segsize, ==, msp->ms_max_size);

	/*
	 * If the weight type changed then there is no point in doing
	 * verification. Revert fields to their original values.
	 */
	if ((space_based && !WEIGHT_IS_SPACEBASED(msp->ms_weight)) ||
	    (!space_based && WEIGHT_IS_SPACEBASED(msp->ms_weight))) {
		msp->ms_fragmentation = frag;
		msp->ms_weight = weight;
		return;
	}

	VERIFY3U(msp->ms_fragmentation, ==, frag);
	VERIFY3U(msp->ms_weight, ==, weight);
}

/*
 * If we're over the zfs_metaslab_mem_limit, select the loaded metaslab from
 * this class that was used longest ago, and attempt to unload it.  We don't
 * want to spend too much time in this loop to prevent performance
 * degredation, and we expect that most of the time this operation will
 * succeed. Between that and the normal unloading processing during txg sync,
 * we expect this to keep the metaslab memory usage under control.
 */
static void
metaslab_potentially_evict(metaslab_class_t *mc)
{
#ifdef _KERNEL
	uint64_t allmem = arc_all_memory();
	extern kmem_cache_t *zfs_btree_leaf_cache;
	uint64_t inuse = kmem_cache_stat(zfs_btree_leaf_cache, "buf_inuse");
	uint64_t size =  kmem_cache_stat(zfs_btree_leaf_cache, "buf_size");
	int tries = 0;
	for (; allmem * zfs_metaslab_mem_limit / 100 < inuse * size &&
	    tries < multilist_get_num_sublists(mc->mc_metaslab_txg_list) * 2;
	    tries++) {
		unsigned int idx = multilist_get_random_index(
		    mc->mc_metaslab_txg_list);
		multilist_sublist_t *mls =
		    multilist_sublist_lock(mc->mc_metaslab_txg_list, idx);
		metaslab_t *msp = multilist_sublist_head(mls);
		multilist_sublist_unlock(mls);
		while (msp != NULL && allmem * zfs_metaslab_mem_limit / 100 <
		    inuse * size) {
			VERIFY3P(mls, ==, multilist_sublist_lock(
			    mc->mc_metaslab_txg_list, idx));
			ASSERT3U(idx, ==,
			    metaslab_idx_func(mc->mc_metaslab_txg_list, msp));

			if (!multilist_link_active(&msp->ms_class_txg_node)) {
				multilist_sublist_unlock(mls);
				break;
			}
			metaslab_t *next_msp = multilist_sublist_next(mls, msp);
			multilist_sublist_unlock(mls);
			/*
			 * If the metaslab is currently loading there are two
			 * cases. If it's the metaslab we're evicting, we
			 * can't continue on or we'll panic when we attempt to
			 * recursively lock the mutex. If it's another
			 * metaslab that's loading, it can be safely skipped,
			 * since we know it's very new and therefore not a
			 * good eviction candidate. We check later once the
			 * lock is held that the metaslab is fully loaded
			 * before actually unloading it.
			 */
			if (msp->ms_loading) {
				msp = next_msp;
				inuse = kmem_cache_stat(zfs_btree_leaf_cache,
				    "buf_inuse");
				continue;
			}
			/*
			 * We can't unload metaslabs with no spacemap because
			 * they're not ready to be unloaded yet. We can't
			 * unload metaslabs with outstanding allocations
			 * because doing so could cause the metaslab's weight
			 * to decrease while it's unloaded, which violates an
			 * invariant that we use to prevent unnecessary
			 * loading. We also don't unload metaslabs that are
			 * currently active because they are high-weight
			 * metaslabs that are likely to be used in the near
			 * future.
			 */
			mutex_enter(&msp->ms_lock);
			if (msp->ms_allocator == -1 && msp->ms_sm != NULL &&
			    msp->ms_allocating_total == 0) {
				metaslab_unload(msp);
			}
			mutex_exit(&msp->ms_lock);
			msp = next_msp;
			inuse = kmem_cache_stat(zfs_btree_leaf_cache,
			    "buf_inuse");
		}
	}
#endif
}

static int
metaslab_load_impl(metaslab_t *msp)
{
	int error = 0;

	ASSERT(MUTEX_HELD(&msp->ms_lock));
	ASSERT(msp->ms_loading);
	ASSERT(!msp->ms_condensing);

	/*
	 * We temporarily drop the lock to unblock other operations while we
	 * are reading the space map. Therefore, metaslab_sync() and
	 * metaslab_sync_done() can run at the same time as we do.
	 *
	 * If we are using the log space maps, metaslab_sync() can't write to
	 * the metaslab's space map while we are loading as we only write to
	 * it when we are flushing the metaslab, and that can't happen while
	 * we are loading it.
	 *
	 * If we are not using log space maps though, metaslab_sync() can
	 * append to the space map while we are loading. Therefore we load
	 * only entries that existed when we started the load. Additionally,
	 * metaslab_sync_done() has to wait for the load to complete because
	 * there are potential races like metaslab_load() loading parts of the
	 * space map that are currently being appended by metaslab_sync(). If
	 * we didn't, the ms_allocatable would have entries that
	 * metaslab_sync_done() would try to re-add later.
	 *
	 * That's why before dropping the lock we remember the synced length
	 * of the metaslab and read up to that point of the space map,
	 * ignoring entries appended by metaslab_sync() that happen after we
	 * drop the lock.
	 */
	uint64_t length = msp->ms_synced_length;
	mutex_exit(&msp->ms_lock);

	hrtime_t load_start = gethrtime();
	metaslab_rt_arg_t *mrap;
	if (msp->ms_allocatable->rt_arg == NULL) {
		mrap = kmem_zalloc(sizeof (*mrap), KM_SLEEP);
	} else {
		mrap = msp->ms_allocatable->rt_arg;
		msp->ms_allocatable->rt_ops = NULL;
		msp->ms_allocatable->rt_arg = NULL;
	}
	mrap->mra_bt = &msp->ms_allocatable_by_size;
	mrap->mra_floor_shift = metaslab_by_size_min_shift;

	if (msp->ms_sm != NULL) {
		error = space_map_load_length(msp->ms_sm, msp->ms_allocatable,
		    SM_FREE, length);

		/* Now, populate the size-sorted tree. */
		metaslab_rt_create(msp->ms_allocatable, mrap);
		msp->ms_allocatable->rt_ops = &metaslab_rt_ops;
		msp->ms_allocatable->rt_arg = mrap;

		struct mssa_arg arg = {0};
		arg.rt = msp->ms_allocatable;
		arg.mra = mrap;
		range_tree_walk(msp->ms_allocatable, metaslab_size_sorted_add,
		    &arg);
	} else {
		/*
		 * Add the size-sorted tree first, since we don't need to load
		 * the metaslab from the spacemap.
		 */
		metaslab_rt_create(msp->ms_allocatable, mrap);
		msp->ms_allocatable->rt_ops = &metaslab_rt_ops;
		msp->ms_allocatable->rt_arg = mrap;
		/*
		 * The space map has not been allocated yet, so treat
		 * all the space in the metaslab as free and add it to the
		 * ms_allocatable tree.
		 */
		range_tree_add(msp->ms_allocatable,
		    msp->ms_start, msp->ms_size);

		if (msp->ms_freed != NULL) {
			/*
			 * If the ms_sm doesn't exist, this means that this
			 * metaslab hasn't gone through metaslab_sync() and
			 * thus has never been dirtied. So we shouldn't
			 * expect any unflushed allocs or frees from previous
			 * TXGs.
			 *
			 * Note: ms_freed and all the other trees except for
			 * the ms_allocatable, can be NULL at this point only
			 * if this is a new metaslab of a vdev that just got
			 * expanded.
			 */
			ASSERT(range_tree_is_empty(msp->ms_unflushed_allocs));
			ASSERT(range_tree_is_empty(msp->ms_unflushed_frees));
		}
	}

	/*
	 * We need to grab the ms_sync_lock to prevent metaslab_sync() from
	 * changing the ms_sm (or log_sm) and the metaslab's range trees
	 * while we are about to use them and populate the ms_allocatable.
	 * The ms_lock is insufficient for this because metaslab_sync() doesn't
	 * hold the ms_lock while writing the ms_checkpointing tree to disk.
	 */
	mutex_enter(&msp->ms_sync_lock);
	mutex_enter(&msp->ms_lock);

	ASSERT(!msp->ms_condensing);
	ASSERT(!msp->ms_flushing);

	if (error != 0) {
		mutex_exit(&msp->ms_sync_lock);
		return (error);
	}

	ASSERT3P(msp->ms_group, !=, NULL);
	msp->ms_loaded = B_TRUE;

	/*
	 * Apply all the unflushed changes to ms_allocatable right
	 * away so any manipulations we do below have a clear view
	 * of what is allocated and what is free.
	 */
	range_tree_walk(msp->ms_unflushed_allocs,
	    range_tree_remove, msp->ms_allocatable);
	range_tree_walk(msp->ms_unflushed_frees,
	    range_tree_add, msp->ms_allocatable);

	msp->ms_loaded = B_TRUE;

	ASSERT3P(msp->ms_group, !=, NULL);
	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
	if (spa_syncing_log_sm(spa) != NULL) {
		ASSERT(spa_feature_is_enabled(spa,
		    SPA_FEATURE_LOG_SPACEMAP));

		/*
		 * If we use a log space map we add all the segments
		 * that are in ms_unflushed_frees so they are available
		 * for allocation.
		 *
		 * ms_allocatable needs to contain all free segments
		 * that are ready for allocations (thus not segments
		 * from ms_freeing, ms_freed, and the ms_defer trees).
		 * But if we grab the lock in this code path at a sync
		 * pass later that 1, then it also contains the
		 * segments of ms_freed (they were added to it earlier
		 * in this path through ms_unflushed_frees). So we
		 * need to remove all the segments that exist in
		 * ms_freed from ms_allocatable as they will be added
		 * later in metaslab_sync_done().
		 *
		 * When there's no log space map, the ms_allocatable
		 * correctly doesn't contain any segments that exist
		 * in ms_freed [see ms_synced_length].
		 */
		range_tree_walk(msp->ms_freed,
		    range_tree_remove, msp->ms_allocatable);
	}

	/*
	 * If we are not using the log space map, ms_allocatable
	 * contains the segments that exist in the ms_defer trees
	 * [see ms_synced_length]. Thus we need to remove them
	 * from ms_allocatable as they will be added again in
	 * metaslab_sync_done().
	 *
	 * If we are using the log space map, ms_allocatable still
	 * contains the segments that exist in the ms_defer trees.
	 * Not because it read them through the ms_sm though. But
	 * because these segments are part of ms_unflushed_frees
	 * whose segments we add to ms_allocatable earlier in this
	 * code path.
	 */
	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
		range_tree_walk(msp->ms_defer[t],
		    range_tree_remove, msp->ms_allocatable);
	}

	/*
	 * Call metaslab_recalculate_weight_and_sort() now that the
	 * metaslab is loaded so we get the metaslab's real weight.
	 *
	 * Unless this metaslab was created with older software and
	 * has not yet been converted to use segment-based weight, we
	 * expect the new weight to be better or equal to the weight
	 * that the metaslab had while it was not loaded. This is
	 * because the old weight does not take into account the
	 * consolidation of adjacent segments between TXGs. [see
	 * comment for ms_synchist and ms_deferhist[] for more info]
	 */
	uint64_t weight = msp->ms_weight;
	uint64_t max_size = msp->ms_max_size;
	metaslab_recalculate_weight_and_sort(msp);
	if (!WEIGHT_IS_SPACEBASED(weight))
		ASSERT3U(weight, <=, msp->ms_weight);
	msp->ms_max_size = metaslab_largest_allocatable(msp);
	ASSERT3U(max_size, <=, msp->ms_max_size);
	hrtime_t load_end = gethrtime();
	msp->ms_load_time = load_end;
	if (zfs_flags & ZFS_DEBUG_LOG_SPACEMAP) {
		zfs_dbgmsg("loading: txg %llu, spa %s, vdev_id %llu, "
		    "ms_id %llu, smp_length %llu, "
		    "unflushed_allocs %llu, unflushed_frees %llu, "
		    "freed %llu, defer %llu + %llu, "
		    "loading_time %lld ms, ms_max_size %llu, "
		    "max size error %llu",
		    spa_syncing_txg(spa), spa_name(spa),
		    msp->ms_group->mg_vd->vdev_id, msp->ms_id,
		    space_map_length(msp->ms_sm),
		    range_tree_space(msp->ms_unflushed_allocs),
		    range_tree_space(msp->ms_unflushed_frees),
		    range_tree_space(msp->ms_freed),
		    range_tree_space(msp->ms_defer[0]),
		    range_tree_space(msp->ms_defer[1]),
		    (longlong_t)((load_end - load_start) / 1000000),
		    msp->ms_max_size, msp->ms_max_size - max_size);
	}

	metaslab_verify_space(msp, spa_syncing_txg(spa));
	mutex_exit(&msp->ms_sync_lock);
	return (0);
}

int
metaslab_load(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * There may be another thread loading the same metaslab, if that's
	 * the case just wait until the other thread is done and return.
	 */
	metaslab_load_wait(msp);
	if (msp->ms_loaded)
		return (0);
	VERIFY(!msp->ms_loading);
	ASSERT(!msp->ms_condensing);

	/*
	 * We set the loading flag BEFORE potentially dropping the lock to
	 * wait for an ongoing flush (see ms_flushing below). This way other
	 * threads know that there is already a thread that is loading this
	 * metaslab.
	 */
	msp->ms_loading = B_TRUE;

	/*
	 * Wait for any in-progress flushing to finish as we drop the ms_lock
	 * both here (during space_map_load()) and in metaslab_flush() (when
	 * we flush our changes to the ms_sm).
	 */
	if (msp->ms_flushing)
		metaslab_flush_wait(msp);

	/*
	 * In the possibility that we were waiting for the metaslab to be
	 * flushed (where we temporarily dropped the ms_lock), ensure that
	 * no one else loaded the metaslab somehow.
	 */
	ASSERT(!msp->ms_loaded);

	/*
	 * If we're loading a metaslab in the normal class, consider evicting
	 * another one to keep our memory usage under the limit defined by the
	 * zfs_metaslab_mem_limit tunable.
	 */
	if (spa_normal_class(msp->ms_group->mg_class->mc_spa) ==
	    msp->ms_group->mg_class) {
		metaslab_potentially_evict(msp->ms_group->mg_class);
	}

	int error = metaslab_load_impl(msp);

	ASSERT(MUTEX_HELD(&msp->ms_lock));
	msp->ms_loading = B_FALSE;
	cv_broadcast(&msp->ms_load_cv);

	return (error);
}

void
metaslab_unload(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * This can happen if a metaslab is selected for eviction (in
	 * metaslab_potentially_evict) and then unloaded during spa_sync (via
	 * metaslab_class_evict_old).
	 */
	if (!msp->ms_loaded)
		return;

	range_tree_vacate(msp->ms_allocatable, NULL, NULL);
	msp->ms_loaded = B_FALSE;
	msp->ms_unload_time = gethrtime();

	msp->ms_activation_weight = 0;
	msp->ms_weight &= ~METASLAB_ACTIVE_MASK;

	if (msp->ms_group != NULL) {
		metaslab_class_t *mc = msp->ms_group->mg_class;
		multilist_sublist_t *mls =
		    multilist_sublist_lock_obj(mc->mc_metaslab_txg_list, msp);
		if (multilist_link_active(&msp->ms_class_txg_node))
			multilist_sublist_remove(mls, msp);
		multilist_sublist_unlock(mls);
	}

	/*
	 * We explicitly recalculate the metaslab's weight based on its space
	 * map (as it is now not loaded). We want unload metaslabs to always
	 * have their weights calculated from the space map histograms, while
	 * loaded ones have it calculated from their in-core range tree
	 * [see metaslab_load()]. This way, the weight reflects the information
	 * available in-core, whether it is loaded or not.
	 *
	 * If ms_group == NULL means that we came here from metaslab_fini(),
	 * at which point it doesn't make sense for us to do the recalculation
	 * and the sorting.
	 */
	if (msp->ms_group != NULL)
		metaslab_recalculate_weight_and_sort(msp);
}

/*
 * We want to optimize the memory use of the per-metaslab range
 * trees. To do this, we store the segments in the range trees in
 * units of sectors, zero-indexing from the start of the metaslab. If
 * the vdev_ms_shift - the vdev_ashift is less than 32, we can store
 * the ranges using two uint32_ts, rather than two uint64_ts.
 */
static range_seg_type_t
metaslab_calculate_range_tree_type(vdev_t *vdev, metaslab_t *msp,
    uint64_t *start, uint64_t *shift)
{
	if (vdev->vdev_ms_shift - vdev->vdev_ashift < 32 &&
	    !zfs_metaslab_force_large_segs) {
		*shift = vdev->vdev_ashift;
		*start = msp->ms_start;
		return (RANGE_SEG32);
	} else {
		*shift = 0;
		*start = 0;
		return (RANGE_SEG64);
	}
}

void
metaslab_set_selected_txg(metaslab_t *msp, uint64_t txg)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));
	metaslab_class_t *mc = msp->ms_group->mg_class;
	multilist_sublist_t *mls =
	    multilist_sublist_lock_obj(mc->mc_metaslab_txg_list, msp);
	if (multilist_link_active(&msp->ms_class_txg_node))
		multilist_sublist_remove(mls, msp);
	msp->ms_selected_txg = txg;
	msp->ms_selected_time = gethrtime();
	multilist_sublist_insert_tail(mls, msp);
	multilist_sublist_unlock(mls);
}

void
metaslab_space_update(vdev_t *vd, metaslab_class_t *mc, int64_t alloc_delta,
    int64_t defer_delta, int64_t space_delta)
{
	vdev_space_update(vd, alloc_delta, defer_delta, space_delta);

	ASSERT3P(vd->vdev_spa->spa_root_vdev, ==, vd->vdev_parent);
	ASSERT(vd->vdev_ms_count != 0);

	metaslab_class_space_update(mc, alloc_delta, defer_delta, space_delta,
	    vdev_deflated_space(vd, space_delta));
}

int
metaslab_init(metaslab_group_t *mg, uint64_t id, uint64_t object,
    uint64_t txg, metaslab_t **msp)
{
	vdev_t *vd = mg->mg_vd;
	spa_t *spa = vd->vdev_spa;
	objset_t *mos = spa->spa_meta_objset;
	metaslab_t *ms;
	int error;

	ms = kmem_zalloc(sizeof (metaslab_t), KM_SLEEP);
	mutex_init(&ms->ms_lock, NULL, MUTEX_DEFAULT, NULL);
	mutex_init(&ms->ms_sync_lock, NULL, MUTEX_DEFAULT, NULL);
	cv_init(&ms->ms_load_cv, NULL, CV_DEFAULT, NULL);
	cv_init(&ms->ms_flush_cv, NULL, CV_DEFAULT, NULL);
	multilist_link_init(&ms->ms_class_txg_node);

	ms->ms_id = id;
	ms->ms_start = id << vd->vdev_ms_shift;
	ms->ms_size = 1ULL << vd->vdev_ms_shift;
	ms->ms_allocator = -1;
	ms->ms_new = B_TRUE;

	/*
	 * We only open space map objects that already exist. All others
	 * will be opened when we finally allocate an object for it.
	 *
	 * Note:
	 * When called from vdev_expand(), we can't call into the DMU as
	 * we are holding the spa_config_lock as a writer and we would
	 * deadlock [see relevant comment in vdev_metaslab_init()]. in
	 * that case, the object parameter is zero though, so we won't
	 * call into the DMU.
	 */
	if (object != 0) {
		error = space_map_open(&ms->ms_sm, mos, object, ms->ms_start,
		    ms->ms_size, vd->vdev_ashift);

		if (error != 0) {
			kmem_free(ms, sizeof (metaslab_t));
			return (error);
		}

		ASSERT(ms->ms_sm != NULL);
		ASSERT3S(space_map_allocated(ms->ms_sm), >=, 0);
		ms->ms_allocated_space = space_map_allocated(ms->ms_sm);
	}

	range_seg_type_t type;
	uint64_t shift, start;
	type = metaslab_calculate_range_tree_type(vd, ms, &start, &shift);

	/*
	 * We create the ms_allocatable here, but we don't create the
	 * other range trees until metaslab_sync_done().  This serves
	 * two purposes: it allows metaslab_sync_done() to detect the
	 * addition of new space; and for debugging, it ensures that
	 * we'd data fault on any attempt to use this metaslab before
	 * it's ready.
	 */
	ms->ms_allocatable = range_tree_create(NULL, type, NULL, start, shift);

	ms->ms_trim = range_tree_create(NULL, type, NULL, start, shift);

	metaslab_group_add(mg, ms);
	metaslab_set_fragmentation(ms);

	/*
	 * If we're opening an existing pool (txg == 0) or creating
	 * a new one (txg == TXG_INITIAL), all space is available now.
	 * If we're adding space to an existing pool, the new space
	 * does not become available until after this txg has synced.
	 * The metaslab's weight will also be initialized when we sync
	 * out this txg. This ensures that we don't attempt to allocate
	 * from it before we have initialized it completely.
	 */
	if (txg <= TXG_INITIAL) {
		metaslab_sync_done(ms, 0);
		metaslab_space_update(vd, mg->mg_class,
		    metaslab_allocated_space(ms), 0, 0);
	}

	if (txg != 0) {
		vdev_dirty(vd, 0, NULL, txg);
		vdev_dirty(vd, VDD_METASLAB, ms, txg);
	}

	*msp = ms;

	return (0);
}

static void
metaslab_fini_flush_data(metaslab_t *msp)
{
	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;

	if (metaslab_unflushed_txg(msp) == 0) {
		ASSERT3P(avl_find(&spa->spa_metaslabs_by_flushed, msp, NULL),
		    ==, NULL);
		return;
	}
	ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP));

	mutex_enter(&spa->spa_flushed_ms_lock);
	avl_remove(&spa->spa_metaslabs_by_flushed, msp);
	mutex_exit(&spa->spa_flushed_ms_lock);

	spa_log_sm_decrement_mscount(spa, metaslab_unflushed_txg(msp));
	spa_log_summary_decrement_mscount(spa, metaslab_unflushed_txg(msp));
}

uint64_t
metaslab_unflushed_changes_memused(metaslab_t *ms)
{
	return ((range_tree_numsegs(ms->ms_unflushed_allocs) +
	    range_tree_numsegs(ms->ms_unflushed_frees)) *
	    ms->ms_unflushed_allocs->rt_root.bt_elem_size);
}

void
metaslab_fini(metaslab_t *msp)
{
	metaslab_group_t *mg = msp->ms_group;
	vdev_t *vd = mg->mg_vd;
	spa_t *spa = vd->vdev_spa;

	metaslab_fini_flush_data(msp);

	metaslab_group_remove(mg, msp);

	mutex_enter(&msp->ms_lock);
	VERIFY(msp->ms_group == NULL);
	metaslab_space_update(vd, mg->mg_class,
	    -metaslab_allocated_space(msp), 0, -msp->ms_size);

	space_map_close(msp->ms_sm);
	msp->ms_sm = NULL;

	metaslab_unload(msp);
	range_tree_destroy(msp->ms_allocatable);
	range_tree_destroy(msp->ms_freeing);
	range_tree_destroy(msp->ms_freed);

	ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=,
	    metaslab_unflushed_changes_memused(msp));
	spa->spa_unflushed_stats.sus_memused -=
	    metaslab_unflushed_changes_memused(msp);
	range_tree_vacate(msp->ms_unflushed_allocs, NULL, NULL);
	range_tree_destroy(msp->ms_unflushed_allocs);
	range_tree_vacate(msp->ms_unflushed_frees, NULL, NULL);
	range_tree_destroy(msp->ms_unflushed_frees);

	for (int t = 0; t < TXG_SIZE; t++) {
		range_tree_destroy(msp->ms_allocating[t]);
	}

	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
		range_tree_destroy(msp->ms_defer[t]);
	}
	ASSERT0(msp->ms_deferspace);

	range_tree_destroy(msp->ms_checkpointing);

	for (int t = 0; t < TXG_SIZE; t++)
		ASSERT(!txg_list_member(&vd->vdev_ms_list, msp, t));

	range_tree_vacate(msp->ms_trim, NULL, NULL);
	range_tree_destroy(msp->ms_trim);

	mutex_exit(&msp->ms_lock);
	cv_destroy(&msp->ms_load_cv);
	cv_destroy(&msp->ms_flush_cv);
	mutex_destroy(&msp->ms_lock);
	mutex_destroy(&msp->ms_sync_lock);
	ASSERT3U(msp->ms_allocator, ==, -1);

	kmem_free(msp, sizeof (metaslab_t));
}

#define	FRAGMENTATION_TABLE_SIZE	17

/*
 * This table defines a segment size based fragmentation metric that will
 * allow each metaslab to derive its own fragmentation value. This is done
 * by calculating the space in each bucket of the spacemap histogram and
 * multiplying that by the fragmentation metric in this table. Doing
 * this for all buckets and dividing it by the total amount of free
 * space in this metaslab (i.e. the total free space in all buckets) gives
 * us the fragmentation metric. This means that a high fragmentation metric
 * equates to most of the free space being comprised of small segments.
 * Conversely, if the metric is low, then most of the free space is in
 * large segments. A 10% change in fragmentation equates to approximately
 * double the number of segments.
 *
 * This table defines 0% fragmented space using 16MB segments. Testing has
 * shown that segments that are greater than or equal to 16MB do not suffer
 * from drastic performance problems. Using this value, we derive the rest
 * of the table. Since the fragmentation value is never stored on disk, it
 * is possible to change these calculations in the future.
 */
int zfs_frag_table[FRAGMENTATION_TABLE_SIZE] = {
	100,	/* 512B	*/
	100,	/* 1K	*/
	98,	/* 2K	*/
	95,	/* 4K	*/
	90,	/* 8K	*/
	80,	/* 16K	*/
	70,	/* 32K	*/
	60,	/* 64K	*/
	50,	/* 128K	*/
	40,	/* 256K	*/
	30,	/* 512K	*/
	20,	/* 1M	*/
	15,	/* 2M	*/
	10,	/* 4M	*/
	5,	/* 8M	*/
	0	/* 16M	*/
};

/*
 * Calculate the metaslab's fragmentation metric and set ms_fragmentation.
 * Setting this value to ZFS_FRAG_INVALID means that the metaslab has not
 * been upgraded and does not support this metric. Otherwise, the return
 * value should be in the range [0, 100].
 */
static void
metaslab_set_fragmentation(metaslab_t *msp)
{
	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
	uint64_t fragmentation = 0;
	uint64_t total = 0;
	boolean_t feature_enabled = spa_feature_is_enabled(spa,
	    SPA_FEATURE_SPACEMAP_HISTOGRAM);

	if (!feature_enabled) {
		msp->ms_fragmentation = ZFS_FRAG_INVALID;
		return;
	}

	/*
	 * A null space map means that the entire metaslab is free
	 * and thus is not fragmented.
	 */
	if (msp->ms_sm == NULL) {
		msp->ms_fragmentation = 0;
		return;
	}

	/*
	 * If this metaslab's space map has not been upgraded, flag it
	 * so that we upgrade next time we encounter it.
	 */
	if (msp->ms_sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) {
		uint64_t txg = spa_syncing_txg(spa);
		vdev_t *vd = msp->ms_group->mg_vd;

		/*
		 * If we've reached the final dirty txg, then we must
		 * be shutting down the pool. We don't want to dirty
		 * any data past this point so skip setting the condense
		 * flag. We can retry this action the next time the pool
		 * is imported.
		 */
		if (spa_writeable(spa) && txg < spa_final_dirty_txg(spa)) {
			msp->ms_condense_wanted = B_TRUE;
			vdev_dirty(vd, VDD_METASLAB, msp, txg + 1);
			zfs_dbgmsg("txg %llu, requesting force condense: "
			    "ms_id %llu, vdev_id %llu", txg, msp->ms_id,
			    vd->vdev_id);
		}
		msp->ms_fragmentation = ZFS_FRAG_INVALID;
		return;
	}

	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
		uint64_t space = 0;
		uint8_t shift = msp->ms_sm->sm_shift;

		int idx = MIN(shift - SPA_MINBLOCKSHIFT + i,
		    FRAGMENTATION_TABLE_SIZE - 1);

		if (msp->ms_sm->sm_phys->smp_histogram[i] == 0)
			continue;

		space = msp->ms_sm->sm_phys->smp_histogram[i] << (i + shift);
		total += space;

		ASSERT3U(idx, <, FRAGMENTATION_TABLE_SIZE);
		fragmentation += space * zfs_frag_table[idx];
	}

	if (total > 0)
		fragmentation /= total;
	ASSERT3U(fragmentation, <=, 100);

	msp->ms_fragmentation = fragmentation;
}

/*
 * Compute a weight -- a selection preference value -- for the given metaslab.
 * This is based on the amount of free space, the level of fragmentation,
 * the LBA range, and whether the metaslab is loaded.
 */
static uint64_t
metaslab_space_weight(metaslab_t *msp)
{
	metaslab_group_t *mg = msp->ms_group;
	vdev_t *vd = mg->mg_vd;
	uint64_t weight, space;

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * The baseline weight is the metaslab's free space.
	 */
	space = msp->ms_size - metaslab_allocated_space(msp);

	if (metaslab_fragmentation_factor_enabled &&
	    msp->ms_fragmentation != ZFS_FRAG_INVALID) {
		/*
		 * Use the fragmentation information to inversely scale
		 * down the baseline weight. We need to ensure that we
		 * don't exclude this metaslab completely when it's 100%
		 * fragmented. To avoid this we reduce the fragmented value
		 * by 1.
		 */
		space = (space * (100 - (msp->ms_fragmentation - 1))) / 100;

		/*
		 * If space < SPA_MINBLOCKSIZE, then we will not allocate from
		 * this metaslab again. The fragmentation metric may have
		 * decreased the space to something smaller than
		 * SPA_MINBLOCKSIZE, so reset the space to SPA_MINBLOCKSIZE
		 * so that we can consume any remaining space.
		 */
		if (space > 0 && space < SPA_MINBLOCKSIZE)
			space = SPA_MINBLOCKSIZE;
	}
	weight = space;

	/*
	 * Modern disks have uniform bit density and constant angular velocity.
	 * Therefore, the outer recording zones are faster (higher bandwidth)
	 * than the inner zones by the ratio of outer to inner track diameter,
	 * which is typically around 2:1.  We account for this by assigning
	 * higher weight to lower metaslabs (multiplier ranging from 2x to 1x).
	 * In effect, this means that we'll select the metaslab with the most
	 * free bandwidth rather than simply the one with the most free space.
	 */
	if (!vd->vdev_nonrot && metaslab_lba_weighting_enabled) {
		weight = 2 * weight - (msp->ms_id * weight) / vd->vdev_ms_count;
		ASSERT(weight >= space && weight <= 2 * space);
	}

	/*
	 * If this metaslab is one we're actively using, adjust its
	 * weight to make it preferable to any inactive metaslab so
	 * we'll polish it off. If the fragmentation on this metaslab
	 * has exceed our threshold, then don't mark it active.
	 */
	if (msp->ms_loaded && msp->ms_fragmentation != ZFS_FRAG_INVALID &&
	    msp->ms_fragmentation <= zfs_metaslab_fragmentation_threshold) {
		weight |= (msp->ms_weight & METASLAB_ACTIVE_MASK);
	}

	WEIGHT_SET_SPACEBASED(weight);
	return (weight);
}

/*
 * Return the weight of the specified metaslab, according to the segment-based
 * weighting algorithm. The metaslab must be loaded. This function can
 * be called within a sync pass since it relies only on the metaslab's
 * range tree which is always accurate when the metaslab is loaded.
 */
static uint64_t
metaslab_weight_from_range_tree(metaslab_t *msp)
{
	uint64_t weight = 0;
	uint32_t segments = 0;

	ASSERT(msp->ms_loaded);

	for (int i = RANGE_TREE_HISTOGRAM_SIZE - 1; i >= SPA_MINBLOCKSHIFT;
	    i--) {
		uint8_t shift = msp->ms_group->mg_vd->vdev_ashift;
		int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1;

		segments <<= 1;
		segments += msp->ms_allocatable->rt_histogram[i];

		/*
		 * The range tree provides more precision than the space map
		 * and must be downgraded so that all values fit within the
		 * space map's histogram. This allows us to compare loaded
		 * vs. unloaded metaslabs to determine which metaslab is
		 * considered "best".
		 */
		if (i > max_idx)
			continue;

		if (segments != 0) {
			WEIGHT_SET_COUNT(weight, segments);
			WEIGHT_SET_INDEX(weight, i);
			WEIGHT_SET_ACTIVE(weight, 0);
			break;
		}
	}
	return (weight);
}

/*
 * Calculate the weight based on the on-disk histogram. Should be applied
 * only to unloaded metaslabs  (i.e no incoming allocations) in-order to
 * give results consistent with the on-disk state
 */
static uint64_t
metaslab_weight_from_spacemap(metaslab_t *msp)
{
	space_map_t *sm = msp->ms_sm;
	ASSERT(!msp->ms_loaded);
	ASSERT(sm != NULL);
	ASSERT3U(space_map_object(sm), !=, 0);
	ASSERT3U(sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t));

	/*
	 * Create a joint histogram from all the segments that have made
	 * it to the metaslab's space map histogram, that are not yet
	 * available for allocation because they are still in the freeing
	 * pipeline (e.g. freeing, freed, and defer trees). Then subtract
	 * these segments from the space map's histogram to get a more
	 * accurate weight.
	 */
	uint64_t deferspace_histogram[SPACE_MAP_HISTOGRAM_SIZE] = {0};
	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++)
		deferspace_histogram[i] += msp->ms_synchist[i];
	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
		for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
			deferspace_histogram[i] += msp->ms_deferhist[t][i];
		}
	}

	uint64_t weight = 0;
	for (int i = SPACE_MAP_HISTOGRAM_SIZE - 1; i >= 0; i--) {
		ASSERT3U(sm->sm_phys->smp_histogram[i], >=,
		    deferspace_histogram[i]);
		uint64_t count =
		    sm->sm_phys->smp_histogram[i] - deferspace_histogram[i];
		if (count != 0) {
			WEIGHT_SET_COUNT(weight, count);
			WEIGHT_SET_INDEX(weight, i + sm->sm_shift);
			WEIGHT_SET_ACTIVE(weight, 0);
			break;
		}
	}
	return (weight);
}

/*
 * Compute a segment-based weight for the specified metaslab. The weight
 * is determined by highest bucket in the histogram. The information
 * for the highest bucket is encoded into the weight value.
 */
static uint64_t
metaslab_segment_weight(metaslab_t *msp)
{
	metaslab_group_t *mg = msp->ms_group;
	uint64_t weight = 0;
	uint8_t shift = mg->mg_vd->vdev_ashift;

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * The metaslab is completely free.
	 */
	if (metaslab_allocated_space(msp) == 0) {
		int idx = highbit64(msp->ms_size) - 1;
		int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1;

		if (idx < max_idx) {
			WEIGHT_SET_COUNT(weight, 1ULL);
			WEIGHT_SET_INDEX(weight, idx);
		} else {
			WEIGHT_SET_COUNT(weight, 1ULL << (idx - max_idx));
			WEIGHT_SET_INDEX(weight, max_idx);
		}
		WEIGHT_SET_ACTIVE(weight, 0);
		ASSERT(!WEIGHT_IS_SPACEBASED(weight));
		return (weight);
	}

	ASSERT3U(msp->ms_sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t));

	/*
	 * If the metaslab is fully allocated then just make the weight 0.
	 */
	if (metaslab_allocated_space(msp) == msp->ms_size)
		return (0);
	/*
	 * If the metaslab is already loaded, then use the range tree to
	 * determine the weight. Otherwise, we rely on the space map information
	 * to generate the weight.
	 */
	if (msp->ms_loaded) {
		weight = metaslab_weight_from_range_tree(msp);
	} else {
		weight = metaslab_weight_from_spacemap(msp);
	}

	/*
	 * If the metaslab was active the last time we calculated its weight
	 * then keep it active. We want to consume the entire region that
	 * is associated with this weight.
	 */
	if (msp->ms_activation_weight != 0 && weight != 0)
		WEIGHT_SET_ACTIVE(weight, WEIGHT_GET_ACTIVE(msp->ms_weight));
	return (weight);
}

/*
 * Determine if we should attempt to allocate from this metaslab. If the
 * metaslab is loaded, then we can determine if the desired allocation
 * can be satisfied by looking at the size of the maximum free segment
 * on that metaslab. Otherwise, we make our decision based on the metaslab's
 * weight. For segment-based weighting we can determine the maximum
 * allocation based on the index encoded in its value. For space-based
 * weights we rely on the entire weight (excluding the weight-type bit).
 */
boolean_t
metaslab_should_allocate(metaslab_t *msp, uint64_t asize, boolean_t try_hard)
{
	/*
	 * If the metaslab is loaded, ms_max_size is definitive and we can use
	 * the fast check. If it's not, the ms_max_size is a lower bound (once
	 * set), and we should use the fast check as long as we're not in
	 * try_hard and it's been less than zfs_metaslab_max_size_cache_sec
	 * seconds since the metaslab was unloaded.
	 */
	if (msp->ms_loaded ||
	    (msp->ms_max_size != 0 && !try_hard && gethrtime() <
	    msp->ms_unload_time + SEC2NSEC(zfs_metaslab_max_size_cache_sec)))
		return (msp->ms_max_size >= asize);

	boolean_t should_allocate;
	if (!WEIGHT_IS_SPACEBASED(msp->ms_weight)) {
		/*
		 * The metaslab segment weight indicates segments in the
		 * range [2^i, 2^(i+1)), where i is the index in the weight.
		 * Since the asize might be in the middle of the range, we
		 * should attempt the allocation if asize < 2^(i+1).
		 */
		should_allocate = (asize <
		    1ULL << (WEIGHT_GET_INDEX(msp->ms_weight) + 1));
	} else {
		should_allocate = (asize <=
		    (msp->ms_weight & ~METASLAB_WEIGHT_TYPE));
	}

	return (should_allocate);
}

static uint64_t
metaslab_weight(metaslab_t *msp)
{
	vdev_t *vd = msp->ms_group->mg_vd;
	spa_t *spa = vd->vdev_spa;
	uint64_t weight;

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	metaslab_set_fragmentation(msp);

	/*
	 * Update the maximum size. If the metaslab is loaded, this will
	 * ensure that we get an accurate maximum size if newly freed space
	 * has been added back into the free tree. If the metaslab is
	 * unloaded, we check if there's a larger free segment in the
	 * unflushed frees. This is a lower bound on the largest allocatable
	 * segment size. Coalescing of adjacent entries may reveal larger
	 * allocatable segments, but we aren't aware of those until loading
	 * the space map into a range tree.
	 */
	if (msp->ms_loaded) {
		msp->ms_max_size = metaslab_largest_allocatable(msp);
	} else {
		msp->ms_max_size = MAX(msp->ms_max_size,
		    metaslab_largest_unflushed_free(msp));
	}

	/*
	 * Segment-based weighting requires space map histogram support.
	 */
	if (zfs_metaslab_segment_weight_enabled &&
	    spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM) &&
	    (msp->ms_sm == NULL || msp->ms_sm->sm_dbuf->db_size ==
	    sizeof (space_map_phys_t))) {
		weight = metaslab_segment_weight(msp);
	} else {
		weight = metaslab_space_weight(msp);
	}
	return (weight);
}

void
metaslab_recalculate_weight_and_sort(metaslab_t *msp)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/* note: we preserve the mask (e.g. indication of primary, etc..) */
	uint64_t was_active = msp->ms_weight & METASLAB_ACTIVE_MASK;
	metaslab_group_sort(msp->ms_group, msp,
	    metaslab_weight(msp) | was_active);
}

static int
metaslab_activate_allocator(metaslab_group_t *mg, metaslab_t *msp,
    int allocator, uint64_t activation_weight)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * If we're activating for the claim code, we don't want to actually
	 * set the metaslab up for a specific allocator.
	 */
	if (activation_weight == METASLAB_WEIGHT_CLAIM) {
		ASSERT0(msp->ms_activation_weight);
		msp->ms_activation_weight = msp->ms_weight;
		metaslab_group_sort(mg, msp, msp->ms_weight |
		    activation_weight);
		return (0);
	}

	metaslab_t **arr = (activation_weight == METASLAB_WEIGHT_PRIMARY ?
	    mg->mg_primaries : mg->mg_secondaries);

	mutex_enter(&mg->mg_lock);
	if (arr[allocator] != NULL) {
		mutex_exit(&mg->mg_lock);
		return (EEXIST);
	}

	arr[allocator] = msp;
	ASSERT3S(msp->ms_allocator, ==, -1);
	msp->ms_allocator = allocator;
	msp->ms_primary = (activation_weight == METASLAB_WEIGHT_PRIMARY);

	ASSERT0(msp->ms_activation_weight);
	msp->ms_activation_weight = msp->ms_weight;
	metaslab_group_sort_impl(mg, msp,
	    msp->ms_weight | activation_weight);

	mutex_exit(&mg->mg_lock);

	return (0);
}

static int
metaslab_activate(metaslab_t *msp, int allocator, uint64_t activation_weight)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * The current metaslab is already activated for us so there
	 * is nothing to do. Already activated though, doesn't mean
	 * that this metaslab is activated for our allocator nor our
	 * requested activation weight. The metaslab could have started
	 * as an active one for our allocator but changed allocators
	 * while we were waiting to grab its ms_lock or we stole it
	 * [see find_valid_metaslab()]. This means that there is a
	 * possibility of passivating a metaslab of another allocator
	 * or from a different activation mask, from this thread.
	 */
	if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) {
		ASSERT(msp->ms_loaded);
		return (0);
	}

	int error = metaslab_load(msp);
	if (error != 0) {
		metaslab_group_sort(msp->ms_group, msp, 0);
		return (error);
	}

	/*
	 * When entering metaslab_load() we may have dropped the
	 * ms_lock because we were loading this metaslab, or we
	 * were waiting for another thread to load it for us. In
	 * that scenario, we recheck the weight of the metaslab
	 * to see if it was activated by another thread.
	 *
	 * If the metaslab was activated for another allocator or
	 * it was activated with a different activation weight (e.g.
	 * we wanted to make it a primary but it was activated as
	 * secondary) we return error (EBUSY).
	 *
	 * If the metaslab was activated for the same allocator
	 * and requested activation mask, skip activating it.
	 */
	if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) {
		if (msp->ms_allocator != allocator)
			return (EBUSY);

		if ((msp->ms_weight & activation_weight) == 0)
			return (EBUSY);

		EQUIV((activation_weight == METASLAB_WEIGHT_PRIMARY),
		    msp->ms_primary);
		return (0);
	}

	/*
	 * If the metaslab has literally 0 space, it will have weight 0. In
	 * that case, don't bother activating it. This can happen if the
	 * metaslab had space during find_valid_metaslab, but another thread
	 * loaded it and used all that space while we were waiting to grab the
	 * lock.
	 */
	if (msp->ms_weight == 0) {
		ASSERT0(range_tree_space(msp->ms_allocatable));
		return (SET_ERROR(ENOSPC));
	}

	if ((error = metaslab_activate_allocator(msp->ms_group, msp,
	    allocator, activation_weight)) != 0) {
		return (error);
	}

	ASSERT(msp->ms_loaded);
	ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK);

	return (0);
}

static void
metaslab_passivate_allocator(metaslab_group_t *mg, metaslab_t *msp,
    uint64_t weight)
{
	ASSERT(MUTEX_HELD(&msp->ms_lock));
	ASSERT(msp->ms_loaded);

	if (msp->ms_weight & METASLAB_WEIGHT_CLAIM) {
		metaslab_group_sort(mg, msp, weight);
		return;
	}

	mutex_enter(&mg->mg_lock);
	ASSERT3P(msp->ms_group, ==, mg);
	ASSERT3S(0, <=, msp->ms_allocator);
	ASSERT3U(msp->ms_allocator, <, mg->mg_allocators);

	if (msp->ms_primary) {
		ASSERT3P(mg->mg_primaries[msp->ms_allocator], ==, msp);
		ASSERT(msp->ms_weight & METASLAB_WEIGHT_PRIMARY);
		mg->mg_primaries[msp->ms_allocator] = NULL;
	} else {
		ASSERT3P(mg->mg_secondaries[msp->ms_allocator], ==, msp);
		ASSERT(msp->ms_weight & METASLAB_WEIGHT_SECONDARY);
		mg->mg_secondaries[msp->ms_allocator] = NULL;
	}
	msp->ms_allocator = -1;
	metaslab_group_sort_impl(mg, msp, weight);
	mutex_exit(&mg->mg_lock);
}

static void
metaslab_passivate(metaslab_t *msp, uint64_t weight)
{
	uint64_t size = weight & ~METASLAB_WEIGHT_TYPE;

	/*
	 * If size < SPA_MINBLOCKSIZE, then we will not allocate from
	 * this metaslab again.  In that case, it had better be empty,
	 * or we would be leaving space on the table.
	 */
	ASSERT(size >= SPA_MINBLOCKSIZE ||
	    range_tree_is_empty(msp->ms_allocatable));
	ASSERT0(weight & METASLAB_ACTIVE_MASK);

	ASSERT(msp->ms_activation_weight != 0);
	msp->ms_activation_weight = 0;
	metaslab_passivate_allocator(msp->ms_group, msp, weight);
	ASSERT0(msp->ms_weight & METASLAB_ACTIVE_MASK);
}

/*
 * Segment-based metaslabs are activated once and remain active until
 * we either fail an allocation attempt (similar to space-based metaslabs)
 * or have exhausted the free space in zfs_metaslab_switch_threshold
 * buckets since the metaslab was activated. This function checks to see
 * if we've exhaused the zfs_metaslab_switch_threshold buckets in the
 * metaslab and passivates it proactively. This will allow us to select a
 * metaslabs with larger contiguous region if any remaining within this
 * metaslab group. If we're in sync pass > 1, then we continue using this
 * metaslab so that we don't dirty more block and cause more sync passes.
 */
void
metaslab_segment_may_passivate(metaslab_t *msp)