1fa9e406ahrens/*
2fa9e406ahrens * CDDL HEADER START
3fa9e406ahrens *
4fa9e406ahrens * The contents of this file are subject to the terms of the
5ecc2d60bonwick * Common Development and Distribution License (the "License").
6ecc2d60bonwick * You may not use this file except in compliance with the License.
7fa9e406ahrens *
8fa9e406ahrens * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9fa9e406ahrens * or http://www.opensolaris.org/os/licensing.
10fa9e406ahrens * See the License for the specific language governing permissions
11fa9e406ahrens * and limitations under the License.
12fa9e406ahrens *
13fa9e406ahrens * When distributing Covered Code, include this CDDL HEADER in each
14fa9e406ahrens * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15fa9e406ahrens * If applicable, add the following below this CDDL HEADER, with the
16fa9e406ahrens * fields enclosed by brackets "[]" replaced with your own identifying
17fa9e406ahrens * information: Portions Copyright [yyyy] [name of copyright owner]
18fa9e406ahrens *
19fa9e406ahrens * CDDL HEADER END
20fa9e406ahrens */
21fa9e406ahrens/*
22d6e555bGeorge Wilson * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23fa9e406ahrens * Use is subject to license terms.
2401f55e4George Wilson */
2501f55e4George Wilson
2601f55e4George Wilson/*
27814dcd4Serapheim Dimitropoulos * Copyright (c) 2011, 2019 by Delphix. All rights reserved.
28fa9e406ahrens */
29fa9e406ahrens
30fa9e406ahrens#ifndef _SYS_METASLAB_IMPL_H
31fa9e406ahrens#define	_SYS_METASLAB_IMPL_H
32fa9e406ahrens
33fa9e406ahrens#include <sys/metaslab.h>
34fa9e406ahrens#include <sys/space_map.h>
350713e23George Wilson#include <sys/range_tree.h>
36fa9e406ahrens#include <sys/vdev.h>
37fa9e406ahrens#include <sys/txg.h>
38fa9e406ahrens#include <sys/avl.h>
39af1d63aPaul Dagnelie#include <sys/multilist.h>
40fa9e406ahrens
41fa9e406ahrens#ifdef	__cplusplus
42fa9e406ahrensextern "C" {
43fa9e406ahrens#endif
44fa9e406ahrens
452e4c998George Wilson/*
468363e80George Wilson * Metaslab allocation tracing record.
478363e80George Wilson */
488363e80George Wilsontypedef struct metaslab_alloc_trace {
498363e80George Wilson	list_node_t			mat_list_node;
508363e80George Wilson	metaslab_group_t		*mat_mg;
518363e80George Wilson	metaslab_t			*mat_msp;
528363e80George Wilson	uint64_t			mat_size;
538363e80George Wilson	uint64_t			mat_weight;
548363e80George Wilson	uint32_t			mat_dva_id;
558363e80George Wilson	uint64_t			mat_offset;
56f78cdc3Paul Dagnelie	int					mat_allocator;
578363e80George Wilson} metaslab_alloc_trace_t;
588363e80George Wilson
598363e80George Wilson/*
608363e80George Wilson * Used by the metaslab allocation tracing facility to indicate
618363e80George Wilson * error conditions. These errors are stored to the offset member
628363e80George Wilson * of the metaslab_alloc_trace_t record and displayed by mdb.
638363e80George Wilson */
648363e80George Wilsontypedef enum trace_alloc_type {
658363e80George Wilson	TRACE_ALLOC_FAILURE	= -1ULL,
668363e80George Wilson	TRACE_TOO_SMALL		= -2ULL,
678363e80George Wilson	TRACE_FORCE_GANG	= -3ULL,
688363e80George Wilson	TRACE_NOT_ALLOCATABLE	= -4ULL,
698363e80George Wilson	TRACE_GROUP_FAILURE	= -5ULL,
708363e80George Wilson	TRACE_ENOSPC		= -6ULL,
718363e80George Wilson	TRACE_CONDENSING	= -7ULL,
72094e47eGeorge Wilson	TRACE_VDEV_ERROR	= -8ULL,
73084fd14Brian Behlendorf	TRACE_DISABLED		= -9ULL,
748363e80George Wilson} trace_alloc_type_t;
758363e80George Wilson
768363e80George Wilson#define	METASLAB_WEIGHT_PRIMARY		(1ULL << 63)
778363e80George Wilson#define	METASLAB_WEIGHT_SECONDARY	(1ULL << 62)
78f78cdc3Paul Dagnelie#define	METASLAB_WEIGHT_CLAIM		(1ULL << 61)
79f78cdc3Paul Dagnelie#define	METASLAB_WEIGHT_TYPE		(1ULL << 60)
808363e80George Wilson#define	METASLAB_ACTIVE_MASK		\
81f78cdc3Paul Dagnelie	(METASLAB_WEIGHT_PRIMARY | METASLAB_WEIGHT_SECONDARY | \
82f78cdc3Paul Dagnelie	METASLAB_WEIGHT_CLAIM)
838363e80George Wilson
848363e80George Wilson/*
858363e80George Wilson * The metaslab weight is used to encode the amount of free space in a
868363e80George Wilson * metaslab, such that the "best" metaslab appears first when sorting the
878363e80George Wilson * metaslabs by weight. The weight (and therefore the "best" metaslab) can
888363e80George Wilson * be determined in two different ways: by computing a weighted sum of all
898363e80George Wilson * the free space in the metaslab (a space based weight) or by counting only
908363e80George Wilson * the free segments of the largest size (a segment based weight). We prefer
918363e80George Wilson * the segment based weight because it reflects how the free space is
928363e80George Wilson * comprised, but we cannot always use it -- legacy pools do not have the
938363e80George Wilson * space map histogram information necessary to determine the largest
948363e80George Wilson * contiguous regions. Pools that have the space map histogram determine
958363e80George Wilson * the segment weight by looking at each bucket in the histogram and
968363e80George Wilson * determining the free space whose size in bytes is in the range:
978363e80George Wilson *	[2^i, 2^(i+1))
988363e80George Wilson * We then encode the largest index, i, that contains regions into the
998363e80George Wilson * segment-weighted value.
1008363e80George Wilson *
1018363e80George Wilson * Space-based weight:
1028363e80George Wilson *
1038363e80George Wilson *      64      56      48      40      32      24      16      8       0
1048363e80George Wilson *      +-------+-------+-------+-------+-------+-------+-------+-------+
105f78cdc3Paul Dagnelie *      |PSC1|                  weighted-free space                     |
1068363e80George Wilson *      +-------+-------+-------+-------+-------+-------+-------+-------+
1078363e80George Wilson *
1088363e80George Wilson *	PS - indicates primary and secondary activation
109f78cdc3Paul Dagnelie *	C - indicates activation for claimed block zio
1108363e80George Wilson *	space - the fragmentation-weighted space
1118363e80George Wilson *
1128363e80George Wilson * Segment-based weight:
1138363e80George Wilson *
1148363e80George Wilson *      64      56      48      40      32      24      16      8       0
1158363e80George Wilson *      +-------+-------+-------+-------+-------+-------+-------+-------+
116f78cdc3Paul Dagnelie *      |PSC0| idx|            count of segments in region              |
1178363e80George Wilson *      +-------+-------+-------+-------+-------+-------+-------+-------+
1188363e80George Wilson *
1198363e80George Wilson *	PS - indicates primary and secondary activation
120f78cdc3Paul Dagnelie *	C - indicates activation for claimed block zio
1218363e80George Wilson *	idx - index for the highest bucket in the histogram
1228363e80George Wilson *	count - number of segments in the specified bucket
1238363e80George Wilson */
124f78cdc3Paul Dagnelie#define	WEIGHT_GET_ACTIVE(weight)		BF64_GET((weight), 61, 3)
125f78cdc3Paul Dagnelie#define	WEIGHT_SET_ACTIVE(weight, x)		BF64_SET((weight), 61, 3, x)
1268363e80George Wilson
1278363e80George Wilson#define	WEIGHT_IS_SPACEBASED(weight)		\
128f78cdc3Paul Dagnelie	((weight) == 0 || BF64_GET((weight), 60, 1))
129f78cdc3Paul Dagnelie#define	WEIGHT_SET_SPACEBASED(weight)		BF64_SET((weight), 60, 1, 1)
1308363e80George Wilson
1318363e80George Wilson/*
1328363e80George Wilson * These macros are only applicable to segment-based weighting.
1338363e80George Wilson */
134f78cdc3Paul Dagnelie#define	WEIGHT_GET_INDEX(weight)		BF64_GET((weight), 54, 6)
135f78cdc3Paul Dagnelie#define	WEIGHT_SET_INDEX(weight, x)		BF64_SET((weight), 54, 6, x)
136f78cdc3Paul Dagnelie#define	WEIGHT_GET_COUNT(weight)		BF64_GET((weight), 0, 54)
137f78cdc3Paul Dagnelie#define	WEIGHT_SET_COUNT(weight, x)		BF64_SET((weight), 0, 54, x)
1388363e80George Wilson
1398363e80George Wilson/*
1402e4c998George Wilson * A metaslab class encompasses a category of allocatable top-level vdevs.
1412e4c998George Wilson * Each top-level vdev is associated with a metaslab group which defines
1422e4c998George Wilson * the allocatable region for that vdev. Examples of these categories include
1432e4c998George Wilson * "normal" for data block allocations (i.e. main pool allocations) or "log"
1442e4c998George Wilson * for allocations designated for intent log devices (i.e. slog devices).
1452e4c998George Wilson * When a block allocation is requested from the SPA it is associated with a
1462e4c998George Wilson * metaslab_class_t, and only top-level vdevs (i.e. metaslab groups) belonging
1472e4c998George Wilson * to the class can be used to satisfy that request. Allocations are done
1482e4c998George Wilson * by traversing the metaslab groups that are linked off of the mc_rotor field.
1492e4c998George Wilson * This rotor points to the next metaslab group where allocations will be
1502e4c998George Wilson * attempted. Allocating a block is a 3 step process -- select the metaslab
1512e4c998George Wilson * group, select the metaslab, and then allocate the block. The metaslab
1522e4c998George Wilson * class defines the low-level block allocator that will be used as the
1532e4c998George Wilson * final step in allocation. These allocators are pluggable allowing each class
1542e4c998George Wilson * to use a block allocator that best suits that class.
1552e4c998George Wilson */
156fa9e406ahrensstruct metaslab_class {
1570f7643cGeorge Wilson	kmutex_t		mc_lock;
15888ecc94George Wilson	spa_t			*mc_spa;
159fa9e406ahrens	metaslab_group_t	*mc_rotor;
1600713e23George Wilson	metaslab_ops_t		*mc_ops;
161b24ab67Jeff Bonwick	uint64_t		mc_aliquot;
1620f7643cGeorge Wilson
1630f7643cGeorge Wilson	/*
1640f7643cGeorge Wilson	 * Track the number of metaslab groups that have been initialized
1650f7643cGeorge Wilson	 * and can accept allocations. An initialized metaslab group is
1660f7643cGeorge Wilson	 * one has been completely added to the config (i.e. we have
1670f7643cGeorge Wilson	 * updated the MOS config and the space has been added to the pool).
1680f7643cGeorge Wilson	 */
1690f7643cGeorge Wilson	uint64_t		mc_groups;
1700f7643cGeorge Wilson
1710f7643cGeorge Wilson	/*
1720f7643cGeorge Wilson	 * Toggle to enable/disable the allocation throttle.
1730f7643cGeorge Wilson	 */
1740f7643cGeorge Wilson	boolean_t		mc_alloc_throttle_enabled;
1750f7643cGeorge Wilson
1760f7643cGeorge Wilson	/*
1770f7643cGeorge Wilson	 * The allocation throttle works on a reservation system. Whenever
1780f7643cGeorge Wilson	 * an asynchronous zio wants to perform an allocation it must
1790f7643cGeorge Wilson	 * first reserve the number of blocks that it wants to allocate.
1800f7643cGeorge Wilson	 * If there aren't sufficient slots available for the pending zio
1810f7643cGeorge Wilson	 * then that I/O is throttled until more slots free up. The current
1820f7643cGeorge Wilson	 * number of reserved allocations is maintained by the mc_alloc_slots
1830f7643cGeorge Wilson	 * refcount. The mc_alloc_max_slots value determines the maximum
1840f7643cGeorge Wilson	 * number of allocations that the system allows. Gang blocks are
1850f7643cGeorge Wilson	 * allowed to reserve slots even if we've reached the maximum
1860f7643cGeorge Wilson	 * number of allocations allowed.
1870f7643cGeorge Wilson	 */
188f78cdc3Paul Dagnelie	uint64_t		*mc_alloc_max_slots;
189e914aceTim Schumacher	zfs_refcount_t		*mc_alloc_slots;
1900f7643cGeorge Wilson
19122e3098George Wilson	uint64_t		mc_alloc_groups; /* # of allocatable groups */
1920f7643cGeorge Wilson
193b24ab67Jeff Bonwick	uint64_t		mc_alloc;	/* total allocated space */
194b24ab67Jeff Bonwick	uint64_t		mc_deferred;	/* total deferred frees */
195b24ab67Jeff Bonwick	uint64_t		mc_space;	/* total space (alloc + free) */
196b24ab67Jeff Bonwick	uint64_t		mc_dspace;	/* total deflated space */
1972e4c998George Wilson	uint64_t		mc_histogram[RANGE_TREE_HISTOGRAM_SIZE];
198af1d63aPaul Dagnelie
199af1d63aPaul Dagnelie	/*
200af1d63aPaul Dagnelie	 * List of all loaded metaslabs in the class, sorted in order of most
201af1d63aPaul Dagnelie	 * recent use.
202af1d63aPaul Dagnelie	 */
203af1d63aPaul Dagnelie	multilist_t		*mc_metaslab_txg_list;
204fa9e406ahrens};
205fa9e406ahrens
2062e4c998George Wilson/*
2072e4c998George Wilson * Metaslab groups encapsulate all the allocatable regions (i.e. metaslabs)
2082e4c998George Wilson * of a top-level vdev. They are linked togther to form a circular linked
2092e4c998George Wilson * list and can belong to only one metaslab class. Metaslab groups may become
2102e4c998George Wilson * ineligible for allocations for a number of reasons such as limited free
2112e4c998George Wilson * space, fragmentation, or going offline. When this happens the allocator will
2122e4c998George Wilson * simply find the next metaslab group in the linked list and attempt
2132e4c998George Wilson * to allocate from that group instead.
2142e4c998George Wilson */
215fa9e406ahrensstruct metaslab_group {
216fa9e406ahrens	kmutex_t		mg_lock;
217f78cdc3Paul Dagnelie	metaslab_t		**mg_primaries;
218f78cdc3Paul Dagnelie	metaslab_t		**mg_secondaries;
219fa9e406ahrens	avl_tree_t		mg_metaslab_tree;
220fa9e406ahrens	uint64_t		mg_aliquot;
22122e3098George Wilson	boolean_t		mg_allocatable;		/* can we allocate? */
222f78cdc3Paul Dagnelie	uint64_t		mg_ms_ready;
2230f7643cGeorge Wilson
2240f7643cGeorge Wilson	/*
2250f7643cGeorge Wilson	 * A metaslab group is considered to be initialized only after
2260f7643cGeorge Wilson	 * we have updated the MOS config and added the space to the pool.
2270f7643cGeorge Wilson	 * We only allow allocation attempts to a metaslab group if it
2280f7643cGeorge Wilson	 * has been initialized.
2290f7643cGeorge Wilson	 */
2300f7643cGeorge Wilson	boolean_t		mg_initialized;
2310f7643cGeorge Wilson
23222e3098George Wilson	uint64_t		mg_free_capacity;	/* percentage free */
233fa9e406ahrens	int64_t			mg_bias;
234a152156Jeff Bonwick	int64_t			mg_activation_count;
235fa9e406ahrens	metaslab_class_t	*mg_class;
236fa9e406ahrens	vdev_t			*mg_vd;
2370713e23George Wilson	taskq_t			*mg_taskq;
238fa9e406ahrens	metaslab_group_t	*mg_prev;
239fa9e406ahrens	metaslab_group_t	*mg_next;
2400f7643cGeorge Wilson
2410f7643cGeorge Wilson	/*
242f78cdc3Paul Dagnelie	 * In order for the allocation throttle to function properly, we cannot
243f78cdc3Paul Dagnelie	 * have too many IOs going to each disk by default; the throttle
244f78cdc3Paul Dagnelie	 * operates by allocating more work to disks that finish quickly, so
245f78cdc3Paul Dagnelie	 * allocating larger chunks to each disk reduces its effectiveness.
246f78cdc3Paul Dagnelie	 * However, if the number of IOs going to each allocator is too small,
247f78cdc3Paul Dagnelie	 * we will not perform proper aggregation at the vdev_queue layer,
248f78cdc3Paul Dagnelie	 * also resulting in decreased performance. Therefore, we will use a
249f78cdc3Paul Dagnelie	 * ramp-up strategy.
250f78cdc3Paul Dagnelie	 *
251f78cdc3Paul Dagnelie	 * Each allocator in each metaslab group has a current queue depth
252f78cdc3Paul Dagnelie	 * (mg_alloc_queue_depth[allocator]) and a current max queue depth
253f78cdc3Paul Dagnelie	 * (mg_cur_max_alloc_queue_depth[allocator]), and each metaslab group
254f78cdc3Paul Dagnelie	 * has an absolute max queue depth (mg_max_alloc_queue_depth).  We
255f78cdc3Paul Dagnelie	 * add IOs to an allocator until the mg_alloc_queue_depth for that
256f78cdc3Paul Dagnelie	 * allocator hits the cur_max. Every time an IO completes for a given
257f78cdc3Paul Dagnelie	 * allocator on a given metaslab group, we increment its cur_max until
258f78cdc3Paul Dagnelie	 * it reaches mg_max_alloc_queue_depth. The cur_max resets every txg to
259f78cdc3Paul Dagnelie	 * help protect against disks that decrease in performance over time.
260f78cdc3Paul Dagnelie	 *
261f78cdc3Paul Dagnelie	 * It's possible for an allocator to handle more allocations than
262f78cdc3Paul Dagnelie	 * its max. This can occur when gang blocks are required or when other
263f78cdc3Paul Dagnelie	 * groups are unable to handle their share of allocations.
2640f7643cGeorge Wilson	 */
2650f7643cGeorge Wilson	uint64_t		mg_max_alloc_queue_depth;
266f78cdc3Paul Dagnelie	uint64_t		*mg_cur_max_alloc_queue_depth;
267e914aceTim Schumacher	zfs_refcount_t		*mg_alloc_queue_depth;
268f78cdc3Paul Dagnelie	int			mg_allocators;
2690f7643cGeorge Wilson	/*
2700f7643cGeorge Wilson	 * A metalab group that can no longer allocate the minimum block
2710f7643cGeorge Wilson	 * size will set mg_no_free_space. Once a metaslab group is out
2720f7643cGeorge Wilson	 * of space then its share of work must be distributed to other
2730f7643cGeorge Wilson	 * groups.
2740f7643cGeorge Wilson	 */
2750f7643cGeorge Wilson	boolean_t		mg_no_free_space;
2760f7643cGeorge Wilson
2770f7643cGeorge Wilson	uint64_t		mg_allocations;
2780f7643cGeorge Wilson	uint64_t		mg_failed_allocations;
2792e4c998George Wilson	uint64_t		mg_fragmentation;
2802e4c998George Wilson	uint64_t		mg_histogram[RANGE_TREE_HISTOGRAM_SIZE];
281094e47eGeorge Wilson
282084fd14Brian Behlendorf	int			mg_ms_disabled;
283084fd14Brian Behlendorf	boolean_t		mg_disabled_updating;
284084fd14Brian Behlendorf	kmutex_t		mg_ms_disabled_lock;
285084fd14Brian Behlendorf	kcondvar_t		mg_ms_disabled_cv;
286fa9e406ahrens};
287fa9e406ahrens
288fa9e406ahrens/*
2890713e23George Wilson * This value defines the number of elements in the ms_lbas array. The value
2902e4c998George Wilson * of 64 was chosen as it covers all power of 2 buckets up to UINT64_MAX.
2912e4c998George Wilson * This is the equivalent of highbit(UINT64_MAX).
2920713e23George Wilson */
2930713e23George Wilson#define	MAX_LBAS	64
2940713e23George Wilson
2950713e23George Wilson/*
2965f14577Matthew Ahrens * Each metaslab maintains a set of in-core trees to track metaslab
2978671400Serapheim Dimitropoulos * operations.  The in-core free tree (ms_allocatable) contains the list of
2985f14577Matthew Ahrens * free segments which are eligible for allocation.  As blocks are
2998671400Serapheim Dimitropoulos * allocated, the allocated segment are removed from the ms_allocatable and
3008671400Serapheim Dimitropoulos * added to a per txg allocation tree (ms_allocating).  As blocks are
3018671400Serapheim Dimitropoulos * freed, they are added to the free tree (ms_freeing).  These trees
3025cabbc6Prashanth Sreenivasa * allow us to process all allocations and frees in syncing context
3035cabbc6Prashanth Sreenivasa * where it is safe to update the on-disk space maps.  An additional set
3045cabbc6Prashanth Sreenivasa * of in-core trees is maintained to track deferred frees
3058671400Serapheim Dimitropoulos * (ms_defer).  Once a block is freed it will move from the
3068671400Serapheim Dimitropoulos * ms_freed to the ms_defer tree.  A deferred free means that a block
3075f14577Matthew Ahrens * has been freed but cannot be used by the pool until TXG_DEFER_SIZE
3085f14577Matthew Ahrens * transactions groups later.  For example, a block that is freed in txg
3095f14577Matthew Ahrens * 50 will not be available for reallocation until txg 52 (50 +
3105f14577Matthew Ahrens * TXG_DEFER_SIZE).  This provides a safety net for uberblock rollback.
3115f14577Matthew Ahrens * A pool could be safely rolled back TXG_DEFERS_SIZE transactions
3125f14577Matthew Ahrens * groups and ensure that no block has been reallocated.
3130713e23George Wilson *
3140713e23George Wilson * The simplified transition diagram looks like this:
3150713e23George Wilson *
3160713e23George Wilson *
3170713e23George Wilson *      ALLOCATE
3180713e23George Wilson *         |
3190713e23George Wilson *         V
3208671400Serapheim Dimitropoulos *    free segment (ms_allocatable) -> ms_allocating[4] -> (write to space map)
3210713e23George Wilson *         ^
3228671400Serapheim Dimitropoulos *         |                        ms_freeing <--- FREE
3238671400Serapheim Dimitropoulos *         |                             |
3248671400Serapheim Dimitropoulos *         |                             v
3258671400Serapheim Dimitropoulos *         |                         ms_freed
3268671400Serapheim Dimitropoulos *         |                             |
3278671400Serapheim Dimitropoulos *         +-------- ms_defer[2] <-------+-------> (write to space map)
32816a4a80George Wilson *
3290713e23George Wilson *
3300713e23George Wilson * Each metaslab's space is tracked in a single space map in the MOS,
3315f14577Matthew Ahrens * which is only updated in syncing context.  Each time we sync a txg,
3325f14577Matthew Ahrens * we append the allocs and frees from that txg to the space map.  The
3335f14577Matthew Ahrens * pool space is only updated once all metaslabs have finished syncing.
33416a4a80George Wilson *
3355f14577Matthew Ahrens * To load the in-core free tree we read the space map from disk.  This
3365f14577Matthew Ahrens * object contains a series of alloc and free records that are combined
3375f14577Matthew Ahrens * to make up the list of all free segments in this metaslab.  These
3388671400Serapheim Dimitropoulos * segments are represented in-core by the ms_allocatable and are stored
3398671400Serapheim Dimitropoulos * in an AVL tree.
34016a4a80George Wilson *
3410713e23George Wilson * As the space map grows (as a result of the appends) it will
3425f14577Matthew Ahrens * eventually become space-inefficient.  When the metaslab's in-core
3435f14577Matthew Ahrens * free tree is zfs_condense_pct/100 times the size of the minimal
3445f14577Matthew Ahrens * on-disk representation, we rewrite it in its minimized form.  If a
3455f14577Matthew Ahrens * metaslab needs to condense then we must set the ms_condensing flag to
3465f14577Matthew Ahrens * ensure that allocations are not performed on the metaslab that is
3475f14577Matthew Ahrens * being written.
348fa9e406ahrens */
349fa9e406ahrensstruct metaslab {
350555d674Serapheim Dimitropoulos	/*
351555d674Serapheim Dimitropoulos	 * This is the main lock of the metaslab and its purpose is to
352555d674Serapheim Dimitropoulos	 * coordinate our allocations and frees [e.g metaslab_block_alloc(),
353555d674Serapheim Dimitropoulos	 * metaslab_free_concrete(), ..etc] with our various syncing
354555d674Serapheim Dimitropoulos	 * procedures [e.g. metaslab_sync(), metaslab_sync_done(), ..etc].
355555d674Serapheim Dimitropoulos	 *
356555d674Serapheim Dimitropoulos	 * The lock is also used during some miscellaneous operations like
357555d674Serapheim Dimitropoulos	 * using the metaslab's histogram for the metaslab group's histogram
358555d674Serapheim Dimitropoulos	 * aggregation, or marking the metaslab for initialization.
359555d674Serapheim Dimitropoulos	 */
3600713e23George Wilson	kmutex_t	ms_lock;
361555d674Serapheim Dimitropoulos
362555d674Serapheim Dimitropoulos	/*
363555d674Serapheim Dimitropoulos	 * Acquired together with the ms_lock whenever we expect to
364555d674Serapheim Dimitropoulos	 * write to metaslab data on-disk (i.e flushing entries to
365555d674Serapheim Dimitropoulos	 * the metaslab's space map). It helps coordinate readers of
366555d674Serapheim Dimitropoulos	 * the metaslab's space map [see spa_vdev_remove_thread()]
367814dcd4Serapheim Dimitropoulos	 * with writers [see metaslab_sync() or metaslab_flush()].
368555d674Serapheim Dimitropoulos	 *
369555d674Serapheim Dimitropoulos	 * Note that metaslab_load(), even though a reader, uses
370555d674Serapheim Dimitropoulos	 * a completely different mechanism to deal with the reading
371555d674Serapheim Dimitropoulos	 * of the metaslab's space map based on ms_synced_length. That
372555d674Serapheim Dimitropoulos	 * said, the function still uses the ms_sync_lock after it
373555d674Serapheim Dimitropoulos	 * has read the ms_sm [see relevant comment in metaslab_load()
374555d674Serapheim Dimitropoulos	 * as to why].
375555d674Serapheim Dimitropoulos	 */
3765cabbc6Prashanth Sreenivasa	kmutex_t	ms_sync_lock;
377555d674Serapheim Dimitropoulos
3780713e23George Wilson	kcondvar_t	ms_load_cv;
3790713e23George Wilson	space_map_t	*ms_sm;
3800713e23George Wilson	uint64_t	ms_id;
3810713e23George Wilson	uint64_t	ms_start;
3820713e23George Wilson	uint64_t	ms_size;
3832e4c998George Wilson	uint64_t	ms_fragmentation;
3840713e23George Wilson
3858671400Serapheim Dimitropoulos	range_tree_t	*ms_allocating[TXG_SIZE];
3868671400Serapheim Dimitropoulos	range_tree_t	*ms_allocatable;
387555d674Serapheim Dimitropoulos	uint64_t	ms_allocated_this_txg;
388af1d63aPaul Dagnelie	uint64_t	ms_allocating_total;
3890713e23George Wilson
3905f14577Matthew Ahrens	/*
3915f14577Matthew Ahrens	 * The following range trees are accessed only from syncing context.
3925f14577Matthew Ahrens	 * ms_free*tree only have entries while syncing, and are empty
3935f14577Matthew Ahrens	 * between syncs.
3945f14577Matthew Ahrens	 */
3958671400Serapheim Dimitropoulos	range_tree_t	*ms_freeing;	/* to free this syncing txg */
3968671400Serapheim Dimitropoulos	range_tree_t	*ms_freed;	/* already freed this syncing txg */
3978671400Serapheim Dimitropoulos	range_tree_t	*ms_defer[TXG_DEFER_SIZE];
3988671400Serapheim Dimitropoulos	range_tree_t	*ms_checkpointing; /* to add to the checkpoint */
3995f14577Matthew Ahrens
400084fd14Brian Behlendorf	/*
401084fd14Brian Behlendorf	 * The ms_trim tree is the set of allocatable segments which are
402084fd14Brian Behlendorf	 * eligible for trimming. (When the metaslab is loaded, it's a
403084fd14Brian Behlendorf	 * subset of ms_allocatable.)  It's kept in-core as long as the
404084fd14Brian Behlendorf	 * autotrim property is set and is not vacated when the metaslab
405084fd14Brian Behlendorf	 * is unloaded.  Its purpose is to aggregate freed ranges to
406084fd14Brian Behlendorf	 * facilitate efficient trimming.
407084fd14Brian Behlendorf	 */
408084fd14Brian Behlendorf	range_tree_t	*ms_trim;
409084fd14Brian Behlendorf
4100713e23George Wilson	boolean_t	ms_condensing;	/* condensing? */
4112e4c998George Wilson	boolean_t	ms_condense_wanted;
4128363e80George Wilson
413084fd14Brian Behlendorf	/*
414084fd14Brian Behlendorf	 * The number of consumers which have disabled the metaslab.
415084fd14Brian Behlendorf	 */
416084fd14Brian Behlendorf	uint64_t	ms_disabled;
417094e47eGeorge Wilson
4188363e80George Wilson	/*
419a0b03b1Serapheim Dimitropoulos	 * We must always hold the ms_lock when modifying ms_loaded
420a0b03b1Serapheim Dimitropoulos	 * and ms_loading.
4218363e80George Wilson	 */
4220713e23George Wilson	boolean_t	ms_loaded;
4230713e23George Wilson	boolean_t	ms_loading;
424814dcd4Serapheim Dimitropoulos	kcondvar_t	ms_flush_cv;
425814dcd4Serapheim Dimitropoulos	boolean_t	ms_flushing;
4260713e23George Wilson
427555d674Serapheim Dimitropoulos	/*
428555d674Serapheim Dimitropoulos	 * The following histograms count entries that are in the
429555d674Serapheim Dimitropoulos	 * metaslab's space map (and its histogram) but are not in
430555d674Serapheim Dimitropoulos	 * ms_allocatable yet, because they are in ms_freed, ms_freeing,
431555d674Serapheim Dimitropoulos	 * or ms_defer[].
432555d674Serapheim Dimitropoulos	 *
433555d674Serapheim Dimitropoulos	 * When the metaslab is not loaded, its ms_weight needs to
434555d674Serapheim Dimitropoulos	 * reflect what is allocatable (i.e. what will be part of
435555d674Serapheim Dimitropoulos	 * ms_allocatable if it is loaded).  The weight is computed from
436555d674Serapheim Dimitropoulos	 * the spacemap histogram, but that includes ranges that are
437555d674Serapheim Dimitropoulos	 * not yet allocatable (because they are in ms_freed,
438555d674Serapheim Dimitropoulos	 * ms_freeing, or ms_defer[]).  Therefore, when calculating the
439555d674Serapheim Dimitropoulos	 * weight, we need to remove those ranges.
440555d674Serapheim Dimitropoulos	 *
441555d674Serapheim Dimitropoulos	 * The ranges in the ms_freed and ms_defer[] range trees are all
442555d674Serapheim Dimitropoulos	 * present in the spacemap.  However, the spacemap may have
443555d674Serapheim Dimitropoulos	 * multiple entries to represent a contiguous range, because it
444555d674Serapheim Dimitropoulos	 * is written across multiple sync passes, but the changes of
445555d674Serapheim Dimitropoulos	 * all sync passes are consolidated into the range trees.
446555d674Serapheim Dimitropoulos	 * Adjacent ranges that are freed in different sync passes of
447555d674Serapheim Dimitropoulos	 * one txg will be represented separately (as 2 or more entries)
448555d674Serapheim Dimitropoulos	 * in the space map (and its histogram), but these adjacent
449555d674Serapheim Dimitropoulos	 * ranges will be consolidated (represented as one entry) in the
450555d674Serapheim Dimitropoulos	 * ms_freed/ms_defer[] range trees (and their histograms).
451555d674Serapheim Dimitropoulos	 *
452555d674Serapheim Dimitropoulos	 * When calculating the weight, we can not simply subtract the
453555d674Serapheim Dimitropoulos	 * range trees' histograms from the spacemap's histogram,
454555d674Serapheim Dimitropoulos	 * because the range trees' histograms may have entries in
455555d674Serapheim Dimitropoulos	 * higher buckets than the spacemap, due to consolidation.
456555d674Serapheim Dimitropoulos	 * Instead we must subtract the exact entries that were added to
457555d674Serapheim Dimitropoulos	 * the spacemap's histogram.  ms_synchist and ms_deferhist[]
458555d674Serapheim Dimitropoulos	 * represent these exact entries, so we can subtract them from
459555d674Serapheim Dimitropoulos	 * the spacemap's histogram when calculating ms_weight.
460555d674Serapheim Dimitropoulos	 *
461555d674Serapheim Dimitropoulos	 * ms_synchist represents the same ranges as ms_freeing +
462555d674Serapheim Dimitropoulos	 * ms_freed, but without consolidation across sync passes.
463555d674Serapheim Dimitropoulos	 *
464555d674Serapheim Dimitropoulos	 * ms_deferhist[i] represents the same ranges as ms_defer[i],
465555d674Serapheim Dimitropoulos	 * but without consolidation across sync passes.
466555d674Serapheim Dimitropoulos	 */
467555d674Serapheim Dimitropoulos	uint64_t	ms_synchist[SPACE_MAP_HISTOGRAM_SIZE];
468555d674Serapheim Dimitropoulos	uint64_t	ms_deferhist[TXG_DEFER_SIZE][SPACE_MAP_HISTOGRAM_SIZE];
469555d674Serapheim Dimitropoulos
470555d674Serapheim Dimitropoulos	/*
471555d674Serapheim Dimitropoulos	 * Tracks the exact amount of allocated space of this metaslab
472555d674Serapheim Dimitropoulos	 * (and specifically the metaslab's space map) up to the most
473555d674Serapheim Dimitropoulos	 * recently completed sync pass [see usage in metaslab_sync()].
474555d674Serapheim Dimitropoulos	 */
475555d674Serapheim Dimitropoulos	uint64_t	ms_allocated_space;
476468c413Tim Haley	int64_t		ms_deferspace;	/* sum of ms_defermap[] space	*/
477ecc2d60bonwick	uint64_t	ms_weight;	/* weight vs. others in group	*/
4788363e80George Wilson	uint64_t	ms_activation_weight;	/* activation weight	*/
4798363e80George Wilson
4808363e80George Wilson	/*
4818363e80George Wilson	 * Track of whenever a metaslab is selected for loading or allocation.
4828363e80George Wilson	 * We use this value to determine how long the metaslab should
4838363e80George Wilson	 * stay cached.
4848363e80George Wilson	 */
4858363e80George Wilson	uint64_t	ms_selected_txg;
486af1d63aPaul Dagnelie	/*
487af1d63aPaul Dagnelie	 * ms_load/unload_time can be used for performance monitoring
488af1d63aPaul Dagnelie	 * (e.g. by dtrace or mdb).
489af1d63aPaul Dagnelie	 */
490af1d63aPaul Dagnelie	hrtime_t	ms_load_time;	/* time last loaded */
491af1d63aPaul Dagnelie	hrtime_t	ms_unload_time;	/* time last unloaded */
492af1d63aPaul Dagnelie	hrtime_t	ms_selected_time; /* time last allocated from */
4938363e80George Wilson
4948363e80George Wilson	uint64_t	ms_alloc_txg;	/* last successful alloc (debug only) */
4958363e80George Wilson	uint64_t	ms_max_size;	/* maximum allocatable size	*/
4960713e23George Wilson
4970713e23George Wilson	/*
498f78cdc3Paul Dagnelie	 * -1 if it's not active in an allocator, otherwise set to the allocator
499f78cdc3Paul Dagnelie	 * this metaslab is active for.
500f78cdc3Paul Dagnelie	 */
501f78cdc3Paul Dagnelie	int		ms_allocator;
502f78cdc3Paul Dagnelie	boolean_t	ms_primary; /* Only valid if ms_allocator is not -1 */
503f78cdc3Paul Dagnelie
504f78cdc3Paul Dagnelie	/*
5050713e23George Wilson	 * The metaslab block allocators can optionally use a size-ordered
5060713e23George Wilson	 * range tree and/or an array of LBAs. Not all allocators use
5078671400Serapheim Dimitropoulos	 * this functionality. The ms_allocatable_by_size should always
5088671400Serapheim Dimitropoulos	 * contain the same number of segments as the ms_allocatable. The
5098671400Serapheim Dimitropoulos	 * only difference is that the ms_allocatable_by_size is ordered by
5108671400Serapheim Dimitropoulos	 * segment sizes.
5110713e23George Wilson	 */
5124d7988dPaul Dagnelie	zfs_btree_t		ms_allocatable_by_size;
5134d7988dPaul Dagnelie	zfs_btree_t		ms_unflushed_frees_by_size;
5140713e23George Wilson	uint64_t	ms_lbas[MAX_LBAS];
5150713e23George Wilson
516ecc2d60bonwick	metaslab_group_t *ms_group;	/* metaslab group		*/
517ecc2d60bonwick	avl_node_t	ms_group_node;	/* node in metaslab group tree	*/
518ecc2d60bonwick	txg_node_t	ms_txg_node;	/* per-txg dirty metaslab links	*/
519814dcd4Serapheim Dimitropoulos	avl_node_t	ms_spa_txg_node; /* node in spa_metaslabs_by_txg */
520af1d63aPaul Dagnelie	/*
521af1d63aPaul Dagnelie	 * Node in metaslab class's selected txg list
522af1d63aPaul Dagnelie	 */
523af1d63aPaul Dagnelie	multilist_node_t	ms_class_txg_node;
524814dcd4Serapheim Dimitropoulos
525814dcd4Serapheim Dimitropoulos	/*
526814dcd4Serapheim Dimitropoulos	 * Allocs and frees that are committed to the vdev log spacemap but
527814dcd4Serapheim Dimitropoulos	 * not yet to this metaslab's spacemap.
528814dcd4Serapheim Dimitropoulos	 */
529814dcd4Serapheim Dimitropoulos	range_tree_t	*ms_unflushed_allocs;
530814dcd4Serapheim Dimitropoulos	range_tree_t	*ms_unflushed_frees;
531814dcd4Serapheim Dimitropoulos
532814dcd4Serapheim Dimitropoulos	/*
533814dcd4Serapheim Dimitropoulos	 * We have flushed entries up to but not including this TXG. In
534814dcd4Serapheim Dimitropoulos	 * other words, all changes from this TXG and onward should not
535814dcd4Serapheim Dimitropoulos	 * be in this metaslab's space map and must be read from the
536814dcd4Serapheim Dimitropoulos	 * log space maps.
537814dcd4Serapheim Dimitropoulos	 */
538814dcd4Serapheim Dimitropoulos	uint64_t	ms_unflushed_txg;
539f78cdc3Paul Dagnelie
540555d674Serapheim Dimitropoulos	/* updated every time we are done syncing the metaslab's space map */
541555d674Serapheim Dimitropoulos	uint64_t	ms_synced_length;
542555d674Serapheim Dimitropoulos
543f78cdc3Paul Dagnelie	boolean_t	ms_new;
544fa9e406ahrens};
545fa9e406ahrens
546814dcd4Serapheim Dimitropoulostypedef struct metaslab_unflushed_phys {
547814dcd4Serapheim Dimitropoulos	/* on-disk counterpart of ms_unflushed_txg */
548814dcd4Serapheim Dimitropoulos	uint64_t	msp_unflushed_txg;
549814dcd4Serapheim Dimitropoulos} metaslab_unflushed_phys_t;
550814dcd4Serapheim Dimitropoulos
551fa9e406ahrens#ifdef	__cplusplus
552fa9e406ahrens}
553fa9e406ahrens#endif
554fa9e406ahrens
555fa9e406ahrens#endif	/* _SYS_METASLAB_IMPL_H */
556