/*

 * 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 2009 Sun Microsystems, Inc.  All rights reserved.

 * Use is subject to license terms.

 */

#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>

uint64_t metaslab_aliquot = 512ULL << 10;

uint64_t metaslab_gang_bang = SPA_MAXBLOCKSIZE + 1;	/* force gang blocks */

/*

 * Metaslab debugging: when set, keeps all space maps in core to verify frees.

 */

static int metaslab_debug = 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_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 = 30;

/*

 * ==========================================================================

 * Metaslab classes

 * ==========================================================================

 */

metaslab_class_t *

metaslab_class_create(spa_t *spa, space_map_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;

	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);

	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);

}

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);

}

/*

 * ==========================================================================

 * Metaslab groups

 * ==========================================================================

 */

static int

metaslab_compare(const void *x1, const void *x2)

{

	const metaslab_t *m1 = x1;

	const metaslab_t *m2 = x2;

	if (m1->ms_weight < m2->ms_weight)

		return (1);

	if (m1->ms_weight > m2->ms_weight)

		return (-1);

	/*

	 * If the weights are identical, use the offset to force uniqueness.

	 */

	if (m1->ms_map.sm_start < m2->ms_map.sm_start)

		return (-1);

	if (m1->ms_map.sm_start > m2->ms_map.sm_start)

		return (1);

	ASSERT3P(m1, ==, m2);

	return (0);

}

metaslab_group_t *

metaslab_group_create(metaslab_class_t *mc, vdev_t *vd)

{

	metaslab_group_t *mg;

	mg = kmem_zalloc(sizeof (metaslab_group_t), KM_SLEEP);

	mutex_init(&mg->mg_lock, NULL, MUTEX_DEFAULT, NULL);

	avl_create(&mg->mg_metaslab_tree, metaslab_compare,

	    sizeof (metaslab_t), offsetof(struct metaslab, ms_group_node));

	mg->mg_vd = vd;

	mg->mg_class = mc;

	mg->mg_activation_count = 0;

	return (mg);

}

void

metaslab_group_destroy(metaslab_group_t *mg)

{

	ASSERT(mg->mg_prev == NULL);

	ASSERT(mg->mg_next == NULL);

	avl_destroy(&mg->mg_metaslab_tree);

	mutex_destroy(&mg->mg_lock);

	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;

	ASSERT(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_WRITER));

	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);

	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;

}

void

metaslab_group_passivate(metaslab_group_t *mg)

{

	metaslab_class_t *mc = mg->mg_class;

	metaslab_group_t *mgprev, *mgnext;

	ASSERT(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_WRITER));

	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;

	}

	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;

}

static void

metaslab_group_add(metaslab_group_t *mg, metaslab_t *msp)

{

	mutex_enter(&mg->mg_lock);

	ASSERT(msp->ms_group == NULL);

	msp->ms_group = mg;

	msp->ms_weight = 0;

	avl_add(&mg->mg_metaslab_tree, msp);

	mutex_exit(&mg->mg_lock);

}

static void

metaslab_group_remove(metaslab_group_t *mg, metaslab_t *msp)

{

	mutex_enter(&mg->mg_lock);

	ASSERT(msp->ms_group == mg);

	avl_remove(&mg->mg_metaslab_tree, msp);

	msp->ms_group = NULL;

	mutex_exit(&mg->mg_lock);

}

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, 510].

	 */

	ASSERT(weight >= SPA_MINBLOCKSIZE-1 || weight == 0);

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

	mutex_enter(&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);

	mutex_exit(&mg->mg_lock);

}

/*

 * This is a helper function that can be used by the allocator to find

 * a suitable block to allocate. This will search the specified AVL

 * tree looking for a block that matches the specified criteria.

 */

static uint64_t

metaslab_block_picker(avl_tree_t *t, uint64_t *cursor, uint64_t size,

    uint64_t align)

{

	space_seg_t *ss, ssearch;

	avl_index_t where;

	ssearch.ss_start = *cursor;

	ssearch.ss_end = *cursor + size;

	ss = avl_find(t, &ssearch, &where);

	if (ss == NULL)

		ss = avl_nearest(t, where, AVL_AFTER);

	while (ss != NULL) {

		uint64_t offset = P2ROUNDUP(ss->ss_start, align);

		if (offset + size <= ss->ss_end) {

			*cursor = offset + size;

			return (offset);

		}

		ss = AVL_NEXT(t, ss);

	}

	/*

	 * If we know we've searched the whole map (*cursor == 0), give up.

	 * Otherwise, reset the cursor to the beginning and try again.

	 */

	if (*cursor == 0)

		return (-1ULL);

	*cursor = 0;

	return (metaslab_block_picker(t, cursor, size, align));

}

/*

 * ==========================================================================

 * The first-fit block allocator

 * ==========================================================================

 */

static void

metaslab_ff_load(space_map_t *sm)

{

	ASSERT(sm->sm_ppd == NULL);

	sm->sm_ppd = kmem_zalloc(64 * sizeof (uint64_t), KM_SLEEP);

	sm->sm_pp_root = NULL;

}

static void

metaslab_ff_unload(space_map_t *sm)

{

	kmem_free(sm->sm_ppd, 64 * sizeof (uint64_t));

	sm->sm_ppd = NULL;

}

static uint64_t

metaslab_ff_alloc(space_map_t *sm, uint64_t size)

{

	avl_tree_t *t = &sm->sm_root;

	uint64_t align = size & -size;

	uint64_t *cursor = (uint64_t *)sm->sm_ppd + highbit(align) - 1;

	return (metaslab_block_picker(t, cursor, size, align));

}

/* ARGSUSED */

static void

metaslab_ff_claim(space_map_t *sm, uint64_t start, uint64_t size)

{

	/* No need to update cursor */

}

/* ARGSUSED */

static void

metaslab_ff_free(space_map_t *sm, uint64_t start, uint64_t size)

{

	/* No need to update cursor */

}

static space_map_ops_t metaslab_ff_ops = {

	metaslab_ff_load,

	metaslab_ff_unload,

	metaslab_ff_alloc,

	metaslab_ff_claim,

	metaslab_ff_free,

	NULL	/* maxsize */

};

/*

 * Dynamic block allocator -

 * Uses the first fit allocation scheme until space get low and then

 * adjusts to a best fit allocation method. Uses metaslab_df_alloc_threshold

 * and metaslab_df_free_pct to determine when to switch the allocation scheme.

 */

uint64_t

metaslab_df_maxsize(space_map_t *sm)

{

	avl_tree_t *t = sm->sm_pp_root;

	space_seg_t *ss;

	if (t == NULL || (ss = avl_last(t)) == NULL)

		return (0ULL);

	return (ss->ss_end - ss->ss_start);

}

static int

metaslab_df_seg_compare(const void *x1, const void *x2)

{

	const space_seg_t *s1 = x1;

	const space_seg_t *s2 = x2;

	uint64_t ss_size1 = s1->ss_end - s1->ss_start;

	uint64_t ss_size2 = s2->ss_end - s2->ss_start;

	if (ss_size1 < ss_size2)

		return (-1);

	if (ss_size1 > ss_size2)

		return (1);

	if (s1->ss_start < s2->ss_start)

		return (-1);

	if (s1->ss_start > s2->ss_start)

		return (1);

	return (0);

}

static void

metaslab_df_load(space_map_t *sm)

{

	space_seg_t *ss;

	ASSERT(sm->sm_ppd == NULL);

	sm->sm_ppd = kmem_zalloc(64 * sizeof (uint64_t), KM_SLEEP);

	sm->sm_pp_root = kmem_alloc(sizeof (avl_tree_t), KM_SLEEP);

	avl_create(sm->sm_pp_root, metaslab_df_seg_compare,

	    sizeof (space_seg_t), offsetof(struct space_seg, ss_pp_node));

	for (ss = avl_first(&sm->sm_root); ss; ss = AVL_NEXT(&sm->sm_root, ss))

		avl_add(sm->sm_pp_root, ss);

}

static void

metaslab_df_unload(space_map_t *sm)

{

	void *cookie = NULL;

	kmem_free(sm->sm_ppd, 64 * sizeof (uint64_t));

	sm->sm_ppd = NULL;

	while (avl_destroy_nodes(sm->sm_pp_root, &cookie) != NULL) {

		/* tear down the tree */

	}

	avl_destroy(sm->sm_pp_root);

	kmem_free(sm->sm_pp_root, sizeof (avl_tree_t));

	sm->sm_pp_root = NULL;

}

static uint64_t

metaslab_df_alloc(space_map_t *sm, uint64_t size)

{

	avl_tree_t *t = &sm->sm_root;

	uint64_t align = size & -size;

	uint64_t *cursor = (uint64_t *)sm->sm_ppd + highbit(align) - 1;

	uint64_t max_size = metaslab_df_maxsize(sm);

	int free_pct = sm->sm_space * 100 / sm->sm_size;

	ASSERT(MUTEX_HELD(sm->sm_lock));

	ASSERT3U(avl_numnodes(&sm->sm_root), ==, avl_numnodes(sm->sm_pp_root));

	if (max_size < size)

		return (-1ULL);

	/*

	 * If we're running low on space switch to using the size

	 * sorted AVL tree (best-fit).

	 */

	if (max_size < metaslab_df_alloc_threshold ||

	    free_pct < metaslab_df_free_pct) {

		t = sm->sm_pp_root;

		*cursor = 0;

	}