xref: /illumos-gate/usr/src/uts/common/fs/zfs/metaslab.c (revision 9cfcc091)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
23  * Copyright (c) 2011, 2018 by Delphix. All rights reserved.
24  * Copyright (c) 2013 by Saso Kiselkov. All rights reserved.
25  * Copyright (c) 2014 Integros [integros.com]
26  * Copyright (c) 2017, Intel Corporation.
27  */
28 
29 #include <sys/zfs_context.h>
30 #include <sys/dmu.h>
31 #include <sys/dmu_tx.h>
32 #include <sys/space_map.h>
33 #include <sys/metaslab_impl.h>
34 #include <sys/vdev_impl.h>
35 #include <sys/zio.h>
36 #include <sys/spa_impl.h>
37 #include <sys/zfeature.h>
38 #include <sys/vdev_indirect_mapping.h>
39 #include <sys/zap.h>
40 #include <sys/btree.h>
41 
42 #define	GANG_ALLOCATION(flags) \
43 	((flags) & (METASLAB_GANG_CHILD | METASLAB_GANG_HEADER))
44 
45 uint64_t metaslab_aliquot = 512ULL << 10;
46 uint64_t metaslab_force_ganging = SPA_MAXBLOCKSIZE + 1;	/* force gang blocks */
47 
48 /*
49  * In pools where the log space map feature is not enabled we touch
50  * multiple metaslabs (and their respective space maps) with each
51  * transaction group. Thus, we benefit from having a small space map
52  * block size since it allows us to issue more I/O operations scattered
53  * around the disk. So a sane default for the space map block size
54  * is 8~16K.
55  */
56 int zfs_metaslab_sm_blksz_no_log = (1 << 14);
57 
58 /*
59  * When the log space map feature is enabled, we accumulate a lot of
60  * changes per metaslab that are flushed once in a while so we benefit
61  * from a bigger block size like 128K for the metaslab space maps.
62  */
63 int zfs_metaslab_sm_blksz_with_log = (1 << 17);
64 
65 /*
66  * The in-core space map representation is more compact than its on-disk form.
67  * The zfs_condense_pct determines how much more compact the in-core
68  * space map representation must be before we compact it on-disk.
69  * Values should be greater than or equal to 100.
70  */
71 int zfs_condense_pct = 200;
72 
73 /*
74  * Condensing a metaslab is not guaranteed to actually reduce the amount of
75  * space used on disk. In particular, a space map uses data in increments of
76  * MAX(1 << ashift, space_map_blksize), so a metaslab might use the
77  * same number of blocks after condensing. Since the goal of condensing is to
78  * reduce the number of IOPs required to read the space map, we only want to
79  * condense when we can be sure we will reduce the number of blocks used by the
80  * space map. Unfortunately, we cannot precisely compute whether or not this is
81  * the case in metaslab_should_condense since we are holding ms_lock. Instead,
82  * we apply the following heuristic: do not condense a spacemap unless the
83  * uncondensed size consumes greater than zfs_metaslab_condense_block_threshold
84  * blocks.
85  */
86 int zfs_metaslab_condense_block_threshold = 4;
87 
88 /*
89  * The zfs_mg_noalloc_threshold defines which metaslab groups should
90  * be eligible for allocation. The value is defined as a percentage of
91  * free space. Metaslab groups that have more free space than
92  * zfs_mg_noalloc_threshold are always eligible for allocations. Once
93  * a metaslab group's free space is less than or equal to the
94  * zfs_mg_noalloc_threshold the allocator will avoid allocating to that
95  * group unless all groups in the pool have reached zfs_mg_noalloc_threshold.
96  * Once all groups in the pool reach zfs_mg_noalloc_threshold then all
97  * groups are allowed to accept allocations. Gang blocks are always
98  * eligible to allocate on any metaslab group. The default value of 0 means
99  * no metaslab group will be excluded based on this criterion.
100  */
101 int zfs_mg_noalloc_threshold = 0;
102 
103 /*
104  * Metaslab groups are considered eligible for allocations if their
105  * fragmenation metric (measured as a percentage) is less than or
106  * equal to zfs_mg_fragmentation_threshold. If a metaslab group
107  * exceeds this threshold then it will be skipped unless all metaslab
108  * groups within the metaslab class have also crossed this threshold.
109  *
110  * This tunable was introduced to avoid edge cases where we continue
111  * allocating from very fragmented disks in our pool while other, less
112  * fragmented disks, exists. On the other hand, if all disks in the
113  * pool are uniformly approaching the threshold, the threshold can
114  * be a speed bump in performance, where we keep switching the disks
115  * that we allocate from (e.g. we allocate some segments from disk A
116  * making it bypassing the threshold while freeing segments from disk
117  * B getting its fragmentation below the threshold).
118  *
119  * Empirically, we've seen that our vdev selection for allocations is
120  * good enough that fragmentation increases uniformly across all vdevs
121  * the majority of the time. Thus we set the threshold percentage high
122  * enough to avoid hitting the speed bump on pools that are being pushed
123  * to the edge.
124  */
125 int zfs_mg_fragmentation_threshold = 95;
126 
127 /*
128  * Allow metaslabs to keep their active state as long as their fragmentation
129  * percentage is less than or equal to zfs_metaslab_fragmentation_threshold. An
130  * active metaslab that exceeds this threshold will no longer keep its active
131  * status allowing better metaslabs to be selected.
132  */
133 int zfs_metaslab_fragmentation_threshold = 70;
134 
135 /*
136  * When set will load all metaslabs when pool is first opened.
137  */
138 int metaslab_debug_load = 0;
139 
140 /*
141  * When set will prevent metaslabs from being unloaded.
142  */
143 int metaslab_debug_unload = 0;
144 
145 /*
146  * Minimum size which forces the dynamic allocator to change
147  * it's allocation strategy.  Once the space map cannot satisfy
148  * an allocation of this size then it switches to using more
149  * aggressive strategy (i.e search by size rather than offset).
150  */
151 uint64_t metaslab_df_alloc_threshold = SPA_OLD_MAXBLOCKSIZE;
152 
153 /*
154  * The minimum free space, in percent, which must be available
155  * in a space map to continue allocations in a first-fit fashion.
156  * Once the space map's free space drops below this level we dynamically
157  * switch to using best-fit allocations.
158  */
159 int metaslab_df_free_pct = 4;
160 
161 /*
162  * Maximum distance to search forward from the last offset. Without this
163  * limit, fragmented pools can see >100,000 iterations and
164  * metaslab_block_picker() becomes the performance limiting factor on
165  * high-performance storage.
166  *
167  * With the default setting of 16MB, we typically see less than 500
168  * iterations, even with very fragmented, ashift=9 pools. The maximum number
169  * of iterations possible is:
170  *     metaslab_df_max_search / (2 * (1<<ashift))
171  * With the default setting of 16MB this is 16*1024 (with ashift=9) or
172  * 2048 (with ashift=12).
173  */
174 int metaslab_df_max_search = 16 * 1024 * 1024;
175 
176 /*
177  * Forces the metaslab_block_picker function to search for at least this many
178  * segments forwards until giving up on finding a segment that the allocation
179  * will fit into.
180  */
181 uint32_t metaslab_min_search_count = 100;
182 
183 /*
184  * If we are not searching forward (due to metaslab_df_max_search,
185  * metaslab_df_free_pct, or metaslab_df_alloc_threshold), this tunable
186  * controls what segment is used.  If it is set, we will use the largest free
187  * segment.  If it is not set, we will use a segment of exactly the requested
188  * size (or larger).
189  */
190 int metaslab_df_use_largest_segment = B_FALSE;
191 
192 /*
193  * A metaslab is considered "free" if it contains a contiguous
194  * segment which is greater than metaslab_min_alloc_size.
195  */
196 uint64_t metaslab_min_alloc_size = DMU_MAX_ACCESS;
197 
198 /*
199  * Percentage of all cpus that can be used by the metaslab taskq.
200  */
201 int metaslab_load_pct = 50;
202 
203 /*
204  * These tunables control how long a metaslab will remain loaded after the
205  * last allocation from it.  A metaslab can't be unloaded until at least
206  * metaslab_unload_delay TXG's and metaslab_unload_delay_ms milliseconds
207  * have elapsed.  However, zfs_metaslab_mem_limit may cause it to be
208  * unloaded sooner.  These settings are intended to be generous -- to keep
209  * metaslabs loaded for a long time, reducing the rate of metaslab loading.
210  */
211 int metaslab_unload_delay = 32;
212 int metaslab_unload_delay_ms = 10 * 60 * 1000; /* ten minutes */
213 
214 /*
215  * Max number of metaslabs per group to preload.
216  */
217 int metaslab_preload_limit = 10;
218 
219 /*
220  * Enable/disable preloading of metaslab.
221  */
222 boolean_t metaslab_preload_enabled = B_TRUE;
223 
224 /*
225  * Enable/disable fragmentation weighting on metaslabs.
226  */
227 boolean_t metaslab_fragmentation_factor_enabled = B_TRUE;
228 
229 /*
230  * Enable/disable lba weighting (i.e. outer tracks are given preference).
231  */
232 boolean_t metaslab_lba_weighting_enabled = B_TRUE;
233 
234 /*
235  * Enable/disable metaslab group biasing.
236  */
237 boolean_t metaslab_bias_enabled = B_TRUE;
238 
239 /*
240  * Enable/disable remapping of indirect DVAs to their concrete vdevs.
241  */
242 boolean_t zfs_remap_blkptr_enable = B_TRUE;
243 
244 /*
245  * Enable/disable segment-based metaslab selection.
246  */
247 boolean_t zfs_metaslab_segment_weight_enabled = B_TRUE;
248 
249 /*
250  * When using segment-based metaslab selection, we will continue
251  * allocating from the active metaslab until we have exhausted
252  * zfs_metaslab_switch_threshold of its buckets.
253  */
254 int zfs_metaslab_switch_threshold = 2;
255 
256 /*
257  * Internal switch to enable/disable the metaslab allocation tracing
258  * facility.
259  */
260 boolean_t metaslab_trace_enabled = B_TRUE;
261 
262 /*
263  * Maximum entries that the metaslab allocation tracing facility will keep
264  * in a given list when running in non-debug mode. We limit the number
265  * of entries in non-debug mode to prevent us from using up too much memory.
266  * The limit should be sufficiently large that we don't expect any allocation
267  * to every exceed this value. In debug mode, the system will panic if this
268  * limit is ever reached allowing for further investigation.
269  */
270 uint64_t metaslab_trace_max_entries = 5000;
271 
272 /*
273  * Maximum number of metaslabs per group that can be disabled
274  * simultaneously.
275  */
276 int max_disabled_ms = 3;
277 
278 /*
279  * Time (in seconds) to respect ms_max_size when the metaslab is not loaded.
280  * To avoid 64-bit overflow, don't set above UINT32_MAX.
281  */
282 unsigned long zfs_metaslab_max_size_cache_sec = 3600; /* 1 hour */
283 
284 /*
285  * Maximum percentage of memory to use on storing loaded metaslabs. If loading
286  * a metaslab would take it over this percentage, the oldest selected metaslab
287  * is automatically unloaded.
288  */
289 int zfs_metaslab_mem_limit = 75;
290 
291 /*
292  * Force the per-metaslab range trees to use 64-bit integers to store
293  * segments. Used for debugging purposes.
294  */
295 boolean_t zfs_metaslab_force_large_segs = B_FALSE;
296 
297 /*
298  * By default we only store segments over a certain size in the size-sorted
299  * metaslab trees (ms_allocatable_by_size and
300  * ms_unflushed_frees_by_size). This dramatically reduces memory usage and
301  * improves load and unload times at the cost of causing us to use slightly
302  * larger segments than we would otherwise in some cases.
303  */
304 uint32_t metaslab_by_size_min_shift = 14;
305 
306 static uint64_t metaslab_weight(metaslab_t *);
307 static void metaslab_set_fragmentation(metaslab_t *);
308 static void metaslab_free_impl(vdev_t *, uint64_t, uint64_t, boolean_t);
309 static void metaslab_check_free_impl(vdev_t *, uint64_t, uint64_t);
310 static void metaslab_passivate(metaslab_t *msp, uint64_t weight);
311 static uint64_t metaslab_weight_from_range_tree(metaslab_t *msp);
312 static void metaslab_flush_update(metaslab_t *, dmu_tx_t *);
313 static unsigned int metaslab_idx_func(multilist_t *, void *);
314 static void metaslab_evict(metaslab_t *, uint64_t);
315 static void metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg);
316 
317 kmem_cache_t *metaslab_alloc_trace_cache;
318 
319 typedef struct metaslab_stats {
320 	kstat_named_t metaslabstat_trace_over_limit;
321 	kstat_named_t metaslabstat_df_find_under_floor;
322 	kstat_named_t metaslabstat_reload_tree;
323 } metaslab_stats_t;
324 
325 static metaslab_stats_t metaslab_stats = {
326 	{ "trace_over_limit",		KSTAT_DATA_UINT64 },
327 	{ "df_find_under_floor",	KSTAT_DATA_UINT64 },
328 	{ "reload_tree",		KSTAT_DATA_UINT64 },
329 };
330 
331 #define	METASLABSTAT_BUMP(stat) \
332 	atomic_inc_64(&metaslab_stats.stat.value.ui64);
333 
334 
335 kstat_t *metaslab_ksp;
336 
337 void
metaslab_stat_init(void)338 metaslab_stat_init(void)
339 {
340 	ASSERT(metaslab_alloc_trace_cache == NULL);
341 	metaslab_alloc_trace_cache = kmem_cache_create(
342 	    "metaslab_alloc_trace_cache", sizeof (metaslab_alloc_trace_t),
343 	    0, NULL, NULL, NULL, NULL, NULL, 0);
344 	metaslab_ksp = kstat_create("zfs", 0, "metaslab_stats",
345 	    "misc", KSTAT_TYPE_NAMED, sizeof (metaslab_stats) /
346 	    sizeof (kstat_named_t), KSTAT_FLAG_VIRTUAL);
347 	if (metaslab_ksp != NULL) {
348 		metaslab_ksp->ks_data = &metaslab_stats;
349 		kstat_install(metaslab_ksp);
350 	}
351 }
352 
353 void
metaslab_stat_fini(void)354 metaslab_stat_fini(void)
355 {
356 	if (metaslab_ksp != NULL) {
357 		kstat_delete(metaslab_ksp);
358 		metaslab_ksp = NULL;
359 	}
360 
361 	kmem_cache_destroy(metaslab_alloc_trace_cache);
362 	metaslab_alloc_trace_cache = NULL;
363 }
364 
365 /*
366  * ==========================================================================
367  * Metaslab classes
368  * ==========================================================================
369  */
370 metaslab_class_t *
metaslab_class_create(spa_t * spa,metaslab_ops_t * ops)371 metaslab_class_create(spa_t *spa, metaslab_ops_t *ops)
372 {
373 	metaslab_class_t *mc;
374 
375 	mc = kmem_zalloc(sizeof (metaslab_class_t), KM_SLEEP);
376 
377 	mc->mc_spa = spa;
378 	mc->mc_rotor = NULL;
379 	mc->mc_ops = ops;
380 	mutex_init(&mc->mc_lock, NULL, MUTEX_DEFAULT, NULL);
381 	mc->mc_metaslab_txg_list = multilist_create(sizeof (metaslab_t),
382 	    offsetof(metaslab_t, ms_class_txg_node), metaslab_idx_func);
383 	mc->mc_alloc_slots = kmem_zalloc(spa->spa_alloc_count *
384 	    sizeof (zfs_refcount_t), KM_SLEEP);
385 	mc->mc_alloc_max_slots = kmem_zalloc(spa->spa_alloc_count *
386 	    sizeof (uint64_t), KM_SLEEP);
387 	for (int i = 0; i < spa->spa_alloc_count; i++)
388 		zfs_refcount_create_tracked(&mc->mc_alloc_slots[i]);
389 
390 	return (mc);
391 }
392 
393 void
metaslab_class_destroy(metaslab_class_t * mc)394 metaslab_class_destroy(metaslab_class_t *mc)
395 {
396 	ASSERT(mc->mc_rotor == NULL);
397 	ASSERT(mc->mc_alloc == 0);
398 	ASSERT(mc->mc_deferred == 0);
399 	ASSERT(mc->mc_space == 0);
400 	ASSERT(mc->mc_dspace == 0);
401 
402 	for (int i = 0; i < mc->mc_spa->spa_alloc_count; i++)
403 		zfs_refcount_destroy(&mc->mc_alloc_slots[i]);
404 	kmem_free(mc->mc_alloc_slots, mc->mc_spa->spa_alloc_count *
405 	    sizeof (zfs_refcount_t));
406 	kmem_free(mc->mc_alloc_max_slots, mc->mc_spa->spa_alloc_count *
407 	    sizeof (uint64_t));
408 	mutex_destroy(&mc->mc_lock);
409 	multilist_destroy(mc->mc_metaslab_txg_list);
410 	kmem_free(mc, sizeof (metaslab_class_t));
411 }
412 
413 int
metaslab_class_validate(metaslab_class_t * mc)414 metaslab_class_validate(metaslab_class_t *mc)
415 {
416 	metaslab_group_t *mg;
417 	vdev_t *vd;
418 
419 	/*
420 	 * Must hold one of the spa_config locks.
421 	 */
422 	ASSERT(spa_config_held(mc->mc_spa, SCL_ALL, RW_READER) ||
423 	    spa_config_held(mc->mc_spa, SCL_ALL, RW_WRITER));
424 
425 	if ((mg = mc->mc_rotor) == NULL)
426 		return (0);
427 
428 	do {
429 		vd = mg->mg_vd;
430 		ASSERT(vd->vdev_mg != NULL);
431 		ASSERT3P(vd->vdev_top, ==, vd);
432 		ASSERT3P(mg->mg_class, ==, mc);
433 		ASSERT3P(vd->vdev_ops, !=, &vdev_hole_ops);
434 	} while ((mg = mg->mg_next) != mc->mc_rotor);
435 
436 	return (0);
437 }
438 
439 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)440 metaslab_class_space_update(metaslab_class_t *mc, int64_t alloc_delta,
441     int64_t defer_delta, int64_t space_delta, int64_t dspace_delta)
442 {
443 	atomic_add_64(&mc->mc_alloc, alloc_delta);
444 	atomic_add_64(&mc->mc_deferred, defer_delta);
445 	atomic_add_64(&mc->mc_space, space_delta);
446 	atomic_add_64(&mc->mc_dspace, dspace_delta);
447 }
448 
449 uint64_t
metaslab_class_get_alloc(metaslab_class_t * mc)450 metaslab_class_get_alloc(metaslab_class_t *mc)
451 {
452 	return (mc->mc_alloc);
453 }
454 
455 uint64_t
metaslab_class_get_deferred(metaslab_class_t * mc)456 metaslab_class_get_deferred(metaslab_class_t *mc)
457 {
458 	return (mc->mc_deferred);
459 }
460 
461 uint64_t
metaslab_class_get_space(metaslab_class_t * mc)462 metaslab_class_get_space(metaslab_class_t *mc)
463 {
464 	return (mc->mc_space);
465 }
466 
467 uint64_t
metaslab_class_get_dspace(metaslab_class_t * mc)468 metaslab_class_get_dspace(metaslab_class_t *mc)
469 {
470 	return (spa_deflate(mc->mc_spa) ? mc->mc_dspace : mc->mc_space);
471 }
472 
473 void
metaslab_class_histogram_verify(metaslab_class_t * mc)474 metaslab_class_histogram_verify(metaslab_class_t *mc)
475 {
476 	spa_t *spa = mc->mc_spa;
477 	vdev_t *rvd = spa->spa_root_vdev;
478 	uint64_t *mc_hist;
479 	int i;
480 
481 	if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0)
482 		return;
483 
484 	mc_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE,
485 	    KM_SLEEP);
486 
487 	for (int c = 0; c < rvd->vdev_children; c++) {
488 		vdev_t *tvd = rvd->vdev_child[c];
489 		metaslab_group_t *mg = tvd->vdev_mg;
490 
491 		/*
492 		 * Skip any holes, uninitialized top-levels, or
493 		 * vdevs that are not in this metalab class.
494 		 */
495 		if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 ||
496 		    mg->mg_class != mc) {
497 			continue;
498 		}
499 
500 		for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++)
501 			mc_hist[i] += mg->mg_histogram[i];
502 	}
503 
504 	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++)
505 		VERIFY3U(mc_hist[i], ==, mc->mc_histogram[i]);
506 
507 	kmem_free(mc_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE);
508 }
509 
510 /*
511  * Calculate the metaslab class's fragmentation metric. The metric
512  * is weighted based on the space contribution of each metaslab group.
513  * The return value will be a number between 0 and 100 (inclusive), or
514  * ZFS_FRAG_INVALID if the metric has not been set. See comment above the
515  * zfs_frag_table for more information about the metric.
516  */
517 uint64_t
metaslab_class_fragmentation(metaslab_class_t * mc)518 metaslab_class_fragmentation(metaslab_class_t *mc)
519 {
520 	vdev_t *rvd = mc->mc_spa->spa_root_vdev;
521 	uint64_t fragmentation = 0;
522 
523 	spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER);
524 
525 	for (int c = 0; c < rvd->vdev_children; c++) {
526 		vdev_t *tvd = rvd->vdev_child[c];
527 		metaslab_group_t *mg = tvd->vdev_mg;
528 
529 		/*
530 		 * Skip any holes, uninitialized top-levels,
531 		 * or vdevs that are not in this metalab class.
532 		 */
533 		if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 ||
534 		    mg->mg_class != mc) {
535 			continue;
536 		}
537 
538 		/*
539 		 * If a metaslab group does not contain a fragmentation
540 		 * metric then just bail out.
541 		 */
542 		if (mg->mg_fragmentation == ZFS_FRAG_INVALID) {
543 			spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG);
544 			return (ZFS_FRAG_INVALID);
545 		}
546 
547 		/*
548 		 * Determine how much this metaslab_group is contributing
549 		 * to the overall pool fragmentation metric.
550 		 */
551 		fragmentation += mg->mg_fragmentation *
552 		    metaslab_group_get_space(mg);
553 	}
554 	fragmentation /= metaslab_class_get_space(mc);
555 
556 	ASSERT3U(fragmentation, <=, 100);
557 	spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG);
558 	return (fragmentation);
559 }
560 
561 /*
562  * Calculate the amount of expandable space that is available in
563  * this metaslab class. If a device is expanded then its expandable
564  * space will be the amount of allocatable space that is currently not
565  * part of this metaslab class.
566  */
567 uint64_t
metaslab_class_expandable_space(metaslab_class_t * mc)568 metaslab_class_expandable_space(metaslab_class_t *mc)
569 {
570 	vdev_t *rvd = mc->mc_spa->spa_root_vdev;
571 	uint64_t space = 0;
572 
573 	spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER);
574 	for (int c = 0; c < rvd->vdev_children; c++) {
575 		uint64_t tspace;
576 		vdev_t *tvd = rvd->vdev_child[c];
577 		metaslab_group_t *mg = tvd->vdev_mg;
578 
579 		if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 ||
580 		    mg->mg_class != mc) {
581 			continue;
582 		}
583 
584 		/*
585 		 * Calculate if we have enough space to add additional
586 		 * metaslabs. We report the expandable space in terms
587 		 * of the metaslab size since that's the unit of expansion.
588 		 * Adjust by efi system partition size.
589 		 */
590 		tspace = tvd->vdev_max_asize - tvd->vdev_asize;
591 		if (tspace > mc->mc_spa->spa_bootsize) {
592 			tspace -= mc->mc_spa->spa_bootsize;
593 		}
594 		space += P2ALIGN(tspace, 1ULL << tvd->vdev_ms_shift);
595 	}
596 	spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG);
597 	return (space);
598 }
599 
600 void
metaslab_class_evict_old(metaslab_class_t * mc,uint64_t txg)601 metaslab_class_evict_old(metaslab_class_t *mc, uint64_t txg)
602 {
603 	multilist_t *ml = mc->mc_metaslab_txg_list;
604 	for (int i = 0; i < multilist_get_num_sublists(ml); i++) {
605 		multilist_sublist_t *mls = multilist_sublist_lock(ml, i);
606 		metaslab_t *msp = multilist_sublist_head(mls);
607 		multilist_sublist_unlock(mls);
608 		while (msp != NULL) {
609 			mutex_enter(&msp->ms_lock);
610 
611 			/*
612 			 * If the metaslab has been removed from the list
613 			 * (which could happen if we were at the memory limit
614 			 * and it was evicted during this loop), then we can't
615 			 * proceed and we should restart the sublist.
616 			 */
617 			if (!multilist_link_active(&msp->ms_class_txg_node)) {
618 				mutex_exit(&msp->ms_lock);
619 				i--;
620 				break;
621 			}
622 			mls = multilist_sublist_lock(ml, i);
623 			metaslab_t *next_msp = multilist_sublist_next(mls, msp);
624 			multilist_sublist_unlock(mls);
625 			if (txg >
626 			    msp->ms_selected_txg + metaslab_unload_delay &&
627 			    gethrtime() > msp->ms_selected_time +
628 			    (uint64_t)MSEC2NSEC(metaslab_unload_delay_ms)) {
629 				metaslab_evict(msp, txg);
630 			} else {
631 				/*
632 				 * Once we've hit a metaslab selected too
633 				 * recently to evict, we're done evicting for
634 				 * now.
635 				 */
636 				mutex_exit(&msp->ms_lock);
637 				break;
638 			}
639 			mutex_exit(&msp->ms_lock);
640 			msp = next_msp;
641 		}
642 	}
643 }
644 
645 static int
metaslab_compare(const void * x1,const void * x2)646 metaslab_compare(const void *x1, const void *x2)
647 {
648 	const metaslab_t *m1 = (const metaslab_t *)x1;
649 	const metaslab_t *m2 = (const metaslab_t *)x2;
650 
651 	int sort1 = 0;
652 	int sort2 = 0;
653 	if (m1->ms_allocator != -1 && m1->ms_primary)
654 		sort1 = 1;
655 	else if (m1->ms_allocator != -1 && !m1->ms_primary)
656 		sort1 = 2;
657 	if (m2->ms_allocator != -1 && m2->ms_primary)
658 		sort2 = 1;
659 	else if (m2->ms_allocator != -1 && !m2->ms_primary)
660 		sort2 = 2;
661 
662 	/*
663 	 * Sort inactive metaslabs first, then primaries, then secondaries. When
664 	 * selecting a metaslab to allocate from, an allocator first tries its
665 	 * primary, then secondary active metaslab. If it doesn't have active
666 	 * metaslabs, or can't allocate from them, it searches for an inactive
667 	 * metaslab to activate. If it can't find a suitable one, it will steal
668 	 * a primary or secondary metaslab from another allocator.
669 	 */
670 	if (sort1 < sort2)
671 		return (-1);
672 	if (sort1 > sort2)
673 		return (1);
674 
675 	int cmp = TREE_CMP(m2->ms_weight, m1->ms_weight);
676 	if (likely(cmp))
677 		return (cmp);
678 
679 	IMPLY(TREE_CMP(m1->ms_start, m2->ms_start) == 0, m1 == m2);
680 
681 	return (TREE_CMP(m1->ms_start, m2->ms_start));
682 }
683 
684 /*
685  * ==========================================================================
686  * Metaslab groups
687  * ==========================================================================
688  */
689 /*
690  * Update the allocatable flag and the metaslab group's capacity.
691  * The allocatable flag is set to true if the capacity is below
692  * the zfs_mg_noalloc_threshold or has a fragmentation value that is
693  * greater than zfs_mg_fragmentation_threshold. If a metaslab group
694  * transitions from allocatable to non-allocatable or vice versa then the
695  * metaslab group's class is updated to reflect the transition.
696  */
697 static void
metaslab_group_alloc_update(metaslab_group_t * mg)698 metaslab_group_alloc_update(metaslab_group_t *mg)
699 {
700 	vdev_t *vd = mg->mg_vd;
701 	metaslab_class_t *mc = mg->mg_class;
702 	vdev_stat_t *vs = &vd->vdev_stat;
703 	boolean_t was_allocatable;
704 	boolean_t was_initialized;
705 
706 	ASSERT(vd == vd->vdev_top);
707 	ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_READER), ==,
708 	    SCL_ALLOC);
709 
710 	mutex_enter(&mg->mg_lock);
711 	was_allocatable = mg->mg_allocatable;
712 	was_initialized = mg->mg_initialized;
713 
714 	mg->mg_free_capacity = ((vs->vs_space - vs->vs_alloc) * 100) /
715 	    (vs->vs_space + 1);
716 
717 	mutex_enter(&mc->mc_lock);
718 
719 	/*
720 	 * If the metaslab group was just added then it won't
721 	 * have any space until we finish syncing out this txg.
722 	 * At that point we will consider it initialized and available
723 	 * for allocations.  We also don't consider non-activated
724 	 * metaslab groups (e.g. vdevs that are in the middle of being removed)
725 	 * to be initialized, because they can't be used for allocation.
726 	 */
727 	mg->mg_initialized = metaslab_group_initialized(mg);
728 	if (!was_initialized && mg->mg_initialized) {
729 		mc->mc_groups++;
730 	} else if (was_initialized && !mg->mg_initialized) {
731 		ASSERT3U(mc->mc_groups, >, 0);
732 		mc->mc_groups--;
733 	}
734 	if (mg->mg_initialized)
735 		mg->mg_no_free_space = B_FALSE;
736 
737 	/*
738 	 * A metaslab group is considered allocatable if it has plenty
739 	 * of free space or is not heavily fragmented. We only take
740 	 * fragmentation into account if the metaslab group has a valid
741 	 * fragmentation metric (i.e. a value between 0 and 100).
742 	 */
743 	mg->mg_allocatable = (mg->mg_activation_count > 0 &&
744 	    mg->mg_free_capacity > zfs_mg_noalloc_threshold &&
745 	    (mg->mg_fragmentation == ZFS_FRAG_INVALID ||
746 	    mg->mg_fragmentation <= zfs_mg_fragmentation_threshold));
747 
748 	/*
749 	 * The mc_alloc_groups maintains a count of the number of
750 	 * groups in this metaslab class that are still above the
751 	 * zfs_mg_noalloc_threshold. This is used by the allocating
752 	 * threads to determine if they should avoid allocations to
753 	 * a given group. The allocator will avoid allocations to a group
754 	 * if that group has reached or is below the zfs_mg_noalloc_threshold
755 	 * and there are still other groups that are above the threshold.
756 	 * When a group transitions from allocatable to non-allocatable or
757 	 * vice versa we update the metaslab class to reflect that change.
758 	 * When the mc_alloc_groups value drops to 0 that means that all
759 	 * groups have reached the zfs_mg_noalloc_threshold making all groups
760 	 * eligible for allocations. This effectively means that all devices
761 	 * are balanced again.
762 	 */
763 	if (was_allocatable && !mg->mg_allocatable)
764 		mc->mc_alloc_groups--;
765 	else if (!was_allocatable && mg->mg_allocatable)
766 		mc->mc_alloc_groups++;
767 	mutex_exit(&mc->mc_lock);
768 
769 	mutex_exit(&mg->mg_lock);
770 }
771 
772 int
metaslab_sort_by_flushed(const void * va,const void * vb)773 metaslab_sort_by_flushed(const void *va, const void *vb)
774 {
775 	const metaslab_t *a = va;
776 	const metaslab_t *b = vb;
777 
778 	int cmp = TREE_CMP(a->ms_unflushed_txg, b->ms_unflushed_txg);
779 	if (likely(cmp))
780 		return (cmp);
781 
782 	uint64_t a_vdev_id = a->ms_group->mg_vd->vdev_id;
783 	uint64_t b_vdev_id = b->ms_group->mg_vd->vdev_id;
784 	cmp = TREE_CMP(a_vdev_id, b_vdev_id);
785 	if (cmp)
786 		return (cmp);
787 
788 	return (TREE_CMP(a->ms_id, b->ms_id));
789 }
790 
791 metaslab_group_t *
metaslab_group_create(metaslab_class_t * mc,vdev_t * vd,int allocators)792 metaslab_group_create(metaslab_class_t *mc, vdev_t *vd, int allocators)
793 {
794 	metaslab_group_t *mg;
795 
796 	mg = kmem_zalloc(sizeof (metaslab_group_t), KM_SLEEP);
797 	mutex_init(&mg->mg_lock, NULL, MUTEX_DEFAULT, NULL);
798 	mutex_init(&mg->mg_ms_disabled_lock, NULL, MUTEX_DEFAULT, NULL);
799 	cv_init(&mg->mg_ms_disabled_cv, NULL, CV_DEFAULT, NULL);
800 	mg->mg_primaries = kmem_zalloc(allocators * sizeof (metaslab_t *),
801 	    KM_SLEEP);
802 	mg->mg_secondaries = kmem_zalloc(allocators * sizeof (metaslab_t *),
803 	    KM_SLEEP);
804 	avl_create(&mg->mg_metaslab_tree, metaslab_compare,
805 	    sizeof (metaslab_t), offsetof(metaslab_t, ms_group_node));
806 	mg->mg_vd = vd;
807 	mg->mg_class = mc;
808 	mg->mg_activation_count = 0;
809 	mg->mg_initialized = B_FALSE;
810 	mg->mg_no_free_space = B_TRUE;
811 	mg->mg_allocators = allocators;
812 
813 	mg->mg_alloc_queue_depth = kmem_zalloc(allocators *
814 	    sizeof (zfs_refcount_t), KM_SLEEP);
815 	mg->mg_cur_max_alloc_queue_depth = kmem_zalloc(allocators *
816 	    sizeof (uint64_t), KM_SLEEP);
817 	for (int i = 0; i < allocators; i++) {
818 		zfs_refcount_create_tracked(&mg->mg_alloc_queue_depth[i]);
819 		mg->mg_cur_max_alloc_queue_depth[i] = 0;
820 	}
821 
822 	mg->mg_taskq = taskq_create("metaslab_group_taskq", metaslab_load_pct,
823 	    minclsyspri, 10, INT_MAX, TASKQ_THREADS_CPU_PCT);
824 
825 	return (mg);
826 }
827 
828 void
metaslab_group_destroy(metaslab_group_t * mg)829 metaslab_group_destroy(metaslab_group_t *mg)
830 {
831 	ASSERT(mg->mg_prev == NULL);
832 	ASSERT(mg->mg_next == NULL);
833 	/*
834 	 * We may have gone below zero with the activation count
835 	 * either because we never activated in the first place or
836 	 * because we're done, and possibly removing the vdev.
837 	 */
838 	ASSERT(mg->mg_activation_count <= 0);
839 
840 	taskq_destroy(mg->mg_taskq);
841 	avl_destroy(&mg->mg_metaslab_tree);
842 	kmem_free(mg->mg_primaries, mg->mg_allocators * sizeof (metaslab_t *));
843 	kmem_free(mg->mg_secondaries, mg->mg_allocators *
844 	    sizeof (metaslab_t *));
845 	mutex_destroy(&mg->mg_lock);
846 	mutex_destroy(&mg->mg_ms_disabled_lock);
847 	cv_destroy(&mg->mg_ms_disabled_cv);
848 
849 	for (int i = 0; i < mg->mg_allocators; i++) {
850 		zfs_refcount_destroy(&mg->mg_alloc_queue_depth[i]);
851 		mg->mg_cur_max_alloc_queue_depth[i] = 0;
852 	}
853 	kmem_free(mg->mg_alloc_queue_depth, mg->mg_allocators *
854 	    sizeof (zfs_refcount_t));
855 	kmem_free(mg->mg_cur_max_alloc_queue_depth, mg->mg_allocators *
856 	    sizeof (uint64_t));
857 
858 	kmem_free(mg, sizeof (metaslab_group_t));
859 }
860 
861 void
metaslab_group_activate(metaslab_group_t * mg)862 metaslab_group_activate(metaslab_group_t *mg)
863 {
864 	metaslab_class_t *mc = mg->mg_class;
865 	metaslab_group_t *mgprev, *mgnext;
866 
867 	ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_WRITER), !=, 0);
868 
869 	ASSERT(mc->mc_rotor != mg);
870 	ASSERT(mg->mg_prev == NULL);
871 	ASSERT(mg->mg_next == NULL);
872 	ASSERT(mg->mg_activation_count <= 0);
873 
874 	if (++mg->mg_activation_count <= 0)
875 		return;
876 
877 	mg->mg_aliquot = metaslab_aliquot * MAX(1, mg->mg_vd->vdev_children);
878 	metaslab_group_alloc_update(mg);
879 
880 	if ((mgprev = mc->mc_rotor) == NULL) {
881 		mg->mg_prev = mg;
882 		mg->mg_next = mg;
883 	} else {
884 		mgnext = mgprev->mg_next;
885 		mg->mg_prev = mgprev;
886 		mg->mg_next = mgnext;
887 		mgprev->mg_next = mg;
888 		mgnext->mg_prev = mg;
889 	}
890 	mc->mc_rotor = mg;
891 }
892 
893 /*
894  * Passivate a metaslab group and remove it from the allocation rotor.
895  * Callers must hold both the SCL_ALLOC and SCL_ZIO lock prior to passivating
896  * a metaslab group. This function will momentarily drop spa_config_locks
897  * that are lower than the SCL_ALLOC lock (see comment below).
898  */
899 void
metaslab_group_passivate(metaslab_group_t * mg)900 metaslab_group_passivate(metaslab_group_t *mg)
901 {
902 	metaslab_class_t *mc = mg->mg_class;
903 	spa_t *spa = mc->mc_spa;
904 	metaslab_group_t *mgprev, *mgnext;
905 	int locks = spa_config_held(spa, SCL_ALL, RW_WRITER);
906 
907 	ASSERT3U(spa_config_held(spa, SCL_ALLOC | SCL_ZIO, RW_WRITER), ==,
908 	    (SCL_ALLOC | SCL_ZIO));
909 
910 	if (--mg->mg_activation_count != 0) {
911 		ASSERT(mc->mc_rotor != mg);
912 		ASSERT(mg->mg_prev == NULL);
913 		ASSERT(mg->mg_next == NULL);
914 		ASSERT(mg->mg_activation_count < 0);
915 		return;
916 	}
917 
918 	/*
919 	 * The spa_config_lock is an array of rwlocks, ordered as
920 	 * follows (from highest to lowest):
921 	 *	SCL_CONFIG > SCL_STATE > SCL_L2ARC > SCL_ALLOC >
922 	 *	SCL_ZIO > SCL_FREE > SCL_VDEV
923 	 * (For more information about the spa_config_lock see spa_misc.c)
924 	 * The higher the lock, the broader its coverage. When we passivate
925 	 * a metaslab group, we must hold both the SCL_ALLOC and the SCL_ZIO
926 	 * config locks. However, the metaslab group's taskq might be trying
927 	 * to preload metaslabs so we must drop the SCL_ZIO lock and any
928 	 * lower locks to allow the I/O to complete. At a minimum,
929 	 * we continue to hold the SCL_ALLOC lock, which prevents any future
930 	 * allocations from taking place and any changes to the vdev tree.
931 	 */
932 	spa_config_exit(spa, locks & ~(SCL_ZIO - 1), spa);
933 	taskq_wait(mg->mg_taskq);
934 	spa_config_enter(spa, locks & ~(SCL_ZIO - 1), spa, RW_WRITER);
935 	metaslab_group_alloc_update(mg);
936 	for (int i = 0; i < mg->mg_allocators; i++) {
937 		metaslab_t *msp = mg->mg_primaries[i];
938 		if (msp != NULL) {
939 			mutex_enter(&msp->ms_lock);
940 			metaslab_passivate(msp,
941 			    metaslab_weight_from_range_tree(msp));
942 			mutex_exit(&msp->ms_lock);
943 		}
944 		msp = mg->mg_secondaries[i];
945 		if (msp != NULL) {
946 			mutex_enter(&msp->ms_lock);
947 			metaslab_passivate(msp,
948 			    metaslab_weight_from_range_tree(msp));
949 			mutex_exit(&msp->ms_lock);
950 		}
951 	}
952 
953 	mgprev = mg->mg_prev;
954 	mgnext = mg->mg_next;
955 
956 	if (mg == mgnext) {
957 		mc->mc_rotor = NULL;
958 	} else {
959 		mc->mc_rotor = mgnext;
960 		mgprev->mg_next = mgnext;
961 		mgnext->mg_prev = mgprev;
962 	}
963 
964 	mg->mg_prev = NULL;
965 	mg->mg_next = NULL;
966 }
967 
968 boolean_t
metaslab_group_initialized(metaslab_group_t * mg)969 metaslab_group_initialized(metaslab_group_t *mg)
970 {
971 	vdev_t *vd = mg->mg_vd;
972 	vdev_stat_t *vs = &vd->vdev_stat;
973 
974 	return (vs->vs_space != 0 && mg->mg_activation_count > 0);
975 }
976 
977 uint64_t
metaslab_group_get_space(metaslab_group_t * mg)978 metaslab_group_get_space(metaslab_group_t *mg)
979 {
980 	return ((1ULL << mg->mg_vd->vdev_ms_shift) * mg->mg_vd->vdev_ms_count);
981 }
982 
983 void
metaslab_group_histogram_verify(metaslab_group_t * mg)984 metaslab_group_histogram_verify(metaslab_group_t *mg)
985 {
986 	uint64_t *mg_hist;
987 	vdev_t *vd = mg->mg_vd;
988 	uint64_t ashift = vd->vdev_ashift;
989 	int i;
990 
991 	if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0)
992 		return;
993 
994 	mg_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE,
995 	    KM_SLEEP);
996 
997 	ASSERT3U(RANGE_TREE_HISTOGRAM_SIZE, >=,
998 	    SPACE_MAP_HISTOGRAM_SIZE + ashift);
999 
1000 	for (int m = 0; m < vd->vdev_ms_count; m++) {
1001 		metaslab_t *msp = vd->vdev_ms[m];
1002 
1003 		/* skip if not active or not a member */
1004 		if (msp->ms_sm == NULL || msp->ms_group != mg)
1005 			continue;
1006 
1007 		for (i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++)
1008 			mg_hist[i + ashift] +=
1009 			    msp->ms_sm->sm_phys->smp_histogram[i];
1010 	}
1011 
1012 	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i ++)
1013 		VERIFY3U(mg_hist[i], ==, mg->mg_histogram[i]);
1014 
1015 	kmem_free(mg_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE);
1016 }
1017 
1018 static void
metaslab_group_histogram_add(metaslab_group_t * mg,metaslab_t * msp)1019 metaslab_group_histogram_add(metaslab_group_t *mg, metaslab_t *msp)
1020 {
1021 	metaslab_class_t *mc = mg->mg_class;
1022 	uint64_t ashift = mg->mg_vd->vdev_ashift;
1023 
1024 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1025 	if (msp->ms_sm == NULL)
1026 		return;
1027 
1028 	mutex_enter(&mg->mg_lock);
1029 	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
1030 		mg->mg_histogram[i + ashift] +=
1031 		    msp->ms_sm->sm_phys->smp_histogram[i];
1032 		mc->mc_histogram[i + ashift] +=
1033 		    msp->ms_sm->sm_phys->smp_histogram[i];
1034 	}
1035 	mutex_exit(&mg->mg_lock);
1036 }
1037 
1038 void
metaslab_group_histogram_remove(metaslab_group_t * mg,metaslab_t * msp)1039 metaslab_group_histogram_remove(metaslab_group_t *mg, metaslab_t *msp)
1040 {
1041 	metaslab_class_t *mc = mg->mg_class;
1042 	uint64_t ashift = mg->mg_vd->vdev_ashift;
1043 
1044 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1045 	if (msp->ms_sm == NULL)
1046 		return;
1047 
1048 	mutex_enter(&mg->mg_lock);
1049 	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
1050 		ASSERT3U(mg->mg_histogram[i + ashift], >=,
1051 		    msp->ms_sm->sm_phys->smp_histogram[i]);
1052 		ASSERT3U(mc->mc_histogram[i + ashift], >=,
1053 		    msp->ms_sm->sm_phys->smp_histogram[i]);
1054 
1055 		mg->mg_histogram[i + ashift] -=
1056 		    msp->ms_sm->sm_phys->smp_histogram[i];
1057 		mc->mc_histogram[i + ashift] -=
1058 		    msp->ms_sm->sm_phys->smp_histogram[i];
1059 	}
1060 	mutex_exit(&mg->mg_lock);
1061 }
1062 
1063 static void
metaslab_group_add(metaslab_group_t * mg,metaslab_t * msp)1064 metaslab_group_add(metaslab_group_t *mg, metaslab_t *msp)
1065 {
1066 	ASSERT(msp->ms_group == NULL);
1067 	mutex_enter(&mg->mg_lock);
1068 	msp->ms_group = mg;
1069 	msp->ms_weight = 0;
1070 	avl_add(&mg->mg_metaslab_tree, msp);
1071 	mutex_exit(&mg->mg_lock);
1072 
1073 	mutex_enter(&msp->ms_lock);
1074 	metaslab_group_histogram_add(mg, msp);
1075 	mutex_exit(&msp->ms_lock);
1076 }
1077 
1078 static void
metaslab_group_remove(metaslab_group_t * mg,metaslab_t * msp)1079 metaslab_group_remove(metaslab_group_t *mg, metaslab_t *msp)
1080 {
1081 	mutex_enter(&msp->ms_lock);
1082 	metaslab_group_histogram_remove(mg, msp);
1083 	mutex_exit(&msp->ms_lock);
1084 
1085 	mutex_enter(&mg->mg_lock);
1086 	ASSERT(msp->ms_group == mg);
1087 	avl_remove(&mg->mg_metaslab_tree, msp);
1088 
1089 	metaslab_class_t *mc = msp->ms_group->mg_class;
1090 	multilist_sublist_t *mls =
1091 	    multilist_sublist_lock_obj(mc->mc_metaslab_txg_list, msp);
1092 	if (multilist_link_active(&msp->ms_class_txg_node))
1093 		multilist_sublist_remove(mls, msp);
1094 	multilist_sublist_unlock(mls);
1095 
1096 	msp->ms_group = NULL;
1097 	mutex_exit(&mg->mg_lock);
1098 }
1099 
1100 static void
metaslab_group_sort_impl(metaslab_group_t * mg,metaslab_t * msp,uint64_t weight)1101 metaslab_group_sort_impl(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight)
1102 {
1103 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1104 	ASSERT(MUTEX_HELD(&mg->mg_lock));
1105 	ASSERT(msp->ms_group == mg);
1106 
1107 	avl_remove(&mg->mg_metaslab_tree, msp);
1108 	msp->ms_weight = weight;
1109 	avl_add(&mg->mg_metaslab_tree, msp);
1110 
1111 }
1112 
1113 static void
metaslab_group_sort(metaslab_group_t * mg,metaslab_t * msp,uint64_t weight)1114 metaslab_group_sort(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight)
1115 {
1116 	/*
1117 	 * Although in principle the weight can be any value, in
1118 	 * practice we do not use values in the range [1, 511].
1119 	 */
1120 	ASSERT(weight >= SPA_MINBLOCKSIZE || weight == 0);
1121 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1122 
1123 	mutex_enter(&mg->mg_lock);
1124 	metaslab_group_sort_impl(mg, msp, weight);
1125 	mutex_exit(&mg->mg_lock);
1126 }
1127 
1128 /*
1129  * Calculate the fragmentation for a given metaslab group. We can use
1130  * a simple average here since all metaslabs within the group must have
1131  * the same size. The return value will be a value between 0 and 100
1132  * (inclusive), or ZFS_FRAG_INVALID if less than half of the metaslab in this
1133  * group have a fragmentation metric.
1134  */
1135 uint64_t
metaslab_group_fragmentation(metaslab_group_t * mg)1136 metaslab_group_fragmentation(metaslab_group_t *mg)
1137 {
1138 	vdev_t *vd = mg->mg_vd;
1139 	uint64_t fragmentation = 0;
1140 	uint64_t valid_ms = 0;
1141 
1142 	for (int m = 0; m < vd->vdev_ms_count; m++) {
1143 		metaslab_t *msp = vd->vdev_ms[m];
1144 
1145 		if (msp->ms_fragmentation == ZFS_FRAG_INVALID)
1146 			continue;
1147 		if (msp->ms_group != mg)
1148 			continue;
1149 
1150 		valid_ms++;
1151 		fragmentation += msp->ms_fragmentation;
1152 	}
1153 
1154 	if (valid_ms <= mg->mg_vd->vdev_ms_count / 2)
1155 		return (ZFS_FRAG_INVALID);
1156 
1157 	fragmentation /= valid_ms;
1158 	ASSERT3U(fragmentation, <=, 100);
1159 	return (fragmentation);
1160 }
1161 
1162 /*
1163  * Determine if a given metaslab group should skip allocations. A metaslab
1164  * group should avoid allocations if its free capacity is less than the
1165  * zfs_mg_noalloc_threshold or its fragmentation metric is greater than
1166  * zfs_mg_fragmentation_threshold and there is at least one metaslab group
1167  * that can still handle allocations. If the allocation throttle is enabled
1168  * then we skip allocations to devices that have reached their maximum
1169  * allocation queue depth unless the selected metaslab group is the only
1170  * eligible group remaining.
1171  */
1172 static boolean_t
metaslab_group_allocatable(metaslab_group_t * mg,metaslab_group_t * rotor,uint64_t psize,int allocator,int d)1173 metaslab_group_allocatable(metaslab_group_t *mg, metaslab_group_t *rotor,
1174     uint64_t psize, int allocator, int d)
1175 {
1176 	spa_t *spa = mg->mg_vd->vdev_spa;
1177 	metaslab_class_t *mc = mg->mg_class;
1178 
1179 	/*
1180 	 * We can only consider skipping this metaslab group if it's
1181 	 * in the normal metaslab class and there are other metaslab
1182 	 * groups to select from. Otherwise, we always consider it eligible
1183 	 * for allocations.
1184 	 */
1185 	if ((mc != spa_normal_class(spa) &&
1186 	    mc != spa_special_class(spa) &&
1187 	    mc != spa_dedup_class(spa)) ||
1188 	    mc->mc_groups <= 1)
1189 		return (B_TRUE);
1190 
1191 	/*
1192 	 * If the metaslab group's mg_allocatable flag is set (see comments
1193 	 * in metaslab_group_alloc_update() for more information) and
1194 	 * the allocation throttle is disabled then allow allocations to this
1195 	 * device. However, if the allocation throttle is enabled then
1196 	 * check if we have reached our allocation limit (mg_alloc_queue_depth)
1197 	 * to determine if we should allow allocations to this metaslab group.
1198 	 * If all metaslab groups are no longer considered allocatable
1199 	 * (mc_alloc_groups == 0) or we're trying to allocate the smallest
1200 	 * gang block size then we allow allocations on this metaslab group
1201 	 * regardless of the mg_allocatable or throttle settings.
1202 	 */
1203 	if (mg->mg_allocatable) {
1204 		metaslab_group_t *mgp;
1205 		int64_t qdepth;
1206 		uint64_t qmax = mg->mg_cur_max_alloc_queue_depth[allocator];
1207 
1208 		if (!mc->mc_alloc_throttle_enabled)
1209 			return (B_TRUE);
1210 
1211 		/*
1212 		 * If this metaslab group does not have any free space, then
1213 		 * there is no point in looking further.
1214 		 */
1215 		if (mg->mg_no_free_space)
1216 			return (B_FALSE);
1217 
1218 		/*
1219 		 * Relax allocation throttling for ditto blocks.  Due to
1220 		 * random imbalances in allocation it tends to push copies
1221 		 * to one vdev, that looks a bit better at the moment.
1222 		 */
1223 		qmax = qmax * (4 + d) / 4;
1224 
1225 		qdepth = zfs_refcount_count(
1226 		    &mg->mg_alloc_queue_depth[allocator]);
1227 
1228 		/*
1229 		 * If this metaslab group is below its qmax or it's
1230 		 * the only allocatable metasable group, then attempt
1231 		 * to allocate from it.
1232 		 */
1233 		if (qdepth < qmax || mc->mc_alloc_groups == 1)
1234 			return (B_TRUE);
1235 		ASSERT3U(mc->mc_alloc_groups, >, 1);
1236 
1237 		/*
1238 		 * Since this metaslab group is at or over its qmax, we
1239 		 * need to determine if there are metaslab groups after this
1240 		 * one that might be able to handle this allocation. This is
1241 		 * racy since we can't hold the locks for all metaslab
1242 		 * groups at the same time when we make this check.
1243 		 */
1244 		for (mgp = mg->mg_next; mgp != rotor; mgp = mgp->mg_next) {
1245 			qmax = mgp->mg_cur_max_alloc_queue_depth[allocator];
1246 			qmax = qmax * (4 + d) / 4;
1247 			qdepth = zfs_refcount_count(
1248 			    &mgp->mg_alloc_queue_depth[allocator]);
1249 
1250 			/*
1251 			 * If there is another metaslab group that
1252 			 * might be able to handle the allocation, then
1253 			 * we return false so that we skip this group.
1254 			 */
1255 			if (qdepth < qmax && !mgp->mg_no_free_space)
1256 				return (B_FALSE);
1257 		}
1258 
1259 		/*
1260 		 * We didn't find another group to handle the allocation
1261 		 * so we can't skip this metaslab group even though
1262 		 * we are at or over our qmax.
1263 		 */
1264 		return (B_TRUE);
1265 
1266 	} else if (mc->mc_alloc_groups == 0 || psize == SPA_MINBLOCKSIZE) {
1267 		return (B_TRUE);
1268 	}
1269 	return (B_FALSE);
1270 }
1271 
1272 /*
1273  * ==========================================================================
1274  * Range tree callbacks
1275  * ==========================================================================
1276  */
1277 
1278 /*
1279  * Comparison function for the private size-ordered tree using 32-bit
1280  * ranges. Tree is sorted by size, larger sizes at the end of the tree.
1281  */
1282 static int
metaslab_rangesize32_compare(const void * x1,const void * x2)1283 metaslab_rangesize32_compare(const void *x1, const void *x2)
1284 {
1285 	const range_seg32_t *r1 = x1;
1286 	const range_seg32_t *r2 = x2;
1287 
1288 	uint64_t rs_size1 = r1->rs_end - r1->rs_start;
1289 	uint64_t rs_size2 = r2->rs_end - r2->rs_start;
1290 
1291 	int cmp = TREE_CMP(rs_size1, rs_size2);
1292 	if (likely(cmp))
1293 		return (cmp);
1294 
1295 	return (TREE_CMP(r1->rs_start, r2->rs_start));
1296 }
1297 
1298 /*
1299  * Comparison function for the private size-ordered tree using 64-bit
1300  * ranges. Tree is sorted by size, larger sizes at the end of the tree.
1301  */
1302 static int
metaslab_rangesize64_compare(const void * x1,const void * x2)1303 metaslab_rangesize64_compare(const void *x1, const void *x2)
1304 {
1305 	const range_seg64_t *r1 = x1;
1306 	const range_seg64_t *r2 = x2;
1307 
1308 	uint64_t rs_size1 = r1->rs_end - r1->rs_start;
1309 	uint64_t rs_size2 = r2->rs_end - r2->rs_start;
1310 
1311 	int cmp = TREE_CMP(rs_size1, rs_size2);
1312 	if (likely(cmp))
1313 		return (cmp);
1314 
1315 	return (TREE_CMP(r1->rs_start, r2->rs_start));
1316 }
1317 typedef struct metaslab_rt_arg {
1318 	zfs_btree_t *mra_bt;
1319 	uint32_t mra_floor_shift;
1320 } metaslab_rt_arg_t;
1321 
1322 struct mssa_arg {
1323 	range_tree_t *rt;
1324 	metaslab_rt_arg_t *mra;
1325 };
1326 
1327 static void
metaslab_size_sorted_add(void * arg,uint64_t start,uint64_t size)1328 metaslab_size_sorted_add(void *arg, uint64_t start, uint64_t size)
1329 {
1330 	struct mssa_arg *mssap = arg;
1331 	range_tree_t *rt = mssap->rt;
1332 	metaslab_rt_arg_t *mrap = mssap->mra;
1333 	range_seg_max_t seg = {0};
1334 	rs_set_start(&seg, rt, start);
1335 	rs_set_end(&seg, rt, start + size);
1336 	metaslab_rt_add(rt, &seg, mrap);
1337 }
1338 
1339 static void
metaslab_size_tree_full_load(range_tree_t * rt)1340 metaslab_size_tree_full_load(range_tree_t *rt)
1341 {
1342 	metaslab_rt_arg_t *mrap = rt->rt_arg;
1343 #ifdef _METASLAB_TRACING
1344 	METASLABSTAT_BUMP(metaslabstat_reload_tree);
1345 #endif
1346 	ASSERT0(zfs_btree_numnodes(mrap->mra_bt));
1347 	mrap->mra_floor_shift = 0;
1348 	struct mssa_arg arg = {0};
1349 	arg.rt = rt;
1350 	arg.mra = mrap;
1351 	range_tree_walk(rt, metaslab_size_sorted_add, &arg);
1352 }
1353 
1354 /*
1355  * Create any block allocator specific components. The current allocators
1356  * rely on using both a size-ordered range_tree_t and an array of uint64_t's.
1357  */
1358 /* ARGSUSED */
1359 static void
metaslab_rt_create(range_tree_t * rt,void * arg)1360 metaslab_rt_create(range_tree_t *rt, void *arg)
1361 {
1362 	metaslab_rt_arg_t *mrap = arg;
1363 	zfs_btree_t *size_tree = mrap->mra_bt;
1364 
1365 	size_t size;
1366 	int (*compare) (const void *, const void *);
1367 	switch (rt->rt_type) {
1368 	case RANGE_SEG32:
1369 		size = sizeof (range_seg32_t);
1370 		compare = metaslab_rangesize32_compare;
1371 		break;
1372 	case RANGE_SEG64:
1373 		size = sizeof (range_seg64_t);
1374 		compare = metaslab_rangesize64_compare;
1375 		break;
1376 	default:
1377 		panic("Invalid range seg type %d", rt->rt_type);
1378 	}
1379 	zfs_btree_create(size_tree, compare, size);
1380 	mrap->mra_floor_shift = metaslab_by_size_min_shift;
1381 }
1382 
1383 /* ARGSUSED */
1384 static void
metaslab_rt_destroy(range_tree_t * rt,void * arg)1385 metaslab_rt_destroy(range_tree_t *rt, void *arg)
1386 {
1387 	metaslab_rt_arg_t *mrap = arg;
1388 	zfs_btree_t *size_tree = mrap->mra_bt;
1389 
1390 	zfs_btree_destroy(size_tree);
1391 	kmem_free(mrap, sizeof (*mrap));
1392 }
1393 
1394 /* ARGSUSED */
1395 static void
metaslab_rt_add(range_tree_t * rt,range_seg_t * rs,void * arg)1396 metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg)
1397 {
1398 	metaslab_rt_arg_t *mrap = arg;
1399 	zfs_btree_t *size_tree = mrap->mra_bt;
1400 
1401 	if (rs_get_end(rs, rt) - rs_get_start(rs, rt) <
1402 	    (1 << mrap->mra_floor_shift))
1403 		return;
1404 
1405 	zfs_btree_add(size_tree, rs);
1406 }
1407 
1408 /* ARGSUSED */
1409 static void
metaslab_rt_remove(range_tree_t * rt,range_seg_t * rs,void * arg)1410 metaslab_rt_remove(range_tree_t *rt, range_seg_t *rs, void *arg)
1411 {
1412 	metaslab_rt_arg_t *mrap = arg;
1413 	zfs_btree_t *size_tree = mrap->mra_bt;
1414 
1415 	if (rs_get_end(rs, rt) - rs_get_start(rs, rt) < (1 <<
1416 	    mrap->mra_floor_shift))
1417 		return;
1418 
1419 	zfs_btree_remove(size_tree, rs);
1420 }
1421 
1422 /* ARGSUSED */
1423 static void
metaslab_rt_vacate(range_tree_t * rt,void * arg)1424 metaslab_rt_vacate(range_tree_t *rt, void *arg)
1425 {
1426 	metaslab_rt_arg_t *mrap = arg;
1427 	zfs_btree_t *size_tree = mrap->mra_bt;
1428 	zfs_btree_clear(size_tree);
1429 	zfs_btree_destroy(size_tree);
1430 
1431 	metaslab_rt_create(rt, arg);
1432 }
1433 
1434 static range_tree_ops_t metaslab_rt_ops = {
1435 	.rtop_create = metaslab_rt_create,
1436 	.rtop_destroy = metaslab_rt_destroy,
1437 	.rtop_add = metaslab_rt_add,
1438 	.rtop_remove = metaslab_rt_remove,
1439 	.rtop_vacate = metaslab_rt_vacate
1440 };
1441 
1442 /*
1443  * ==========================================================================
1444  * Common allocator routines
1445  * ==========================================================================
1446  */
1447 
1448 /*
1449  * Return the maximum contiguous segment within the metaslab.
1450  */
1451 uint64_t
metaslab_largest_allocatable(metaslab_t * msp)1452 metaslab_largest_allocatable(metaslab_t *msp)
1453 {
1454 	zfs_btree_t *t = &msp->ms_allocatable_by_size;
1455 	range_seg_t *rs;
1456 
1457 	if (t == NULL)
1458 		return (0);
1459 	if (zfs_btree_numnodes(t) == 0)
1460 		metaslab_size_tree_full_load(msp->ms_allocatable);
1461 
1462 	rs = zfs_btree_last(t, NULL);
1463 	if (rs == NULL)
1464 		return (0);
1465 
1466 	return (rs_get_end(rs, msp->ms_allocatable) - rs_get_start(rs,
1467 	    msp->ms_allocatable));
1468 }
1469 
1470 /*
1471  * Return the maximum contiguous segment within the unflushed frees of this
1472  * metaslab.
1473  */
1474 uint64_t
metaslab_largest_unflushed_free(metaslab_t * msp)1475 metaslab_largest_unflushed_free(metaslab_t *msp)
1476 {
1477 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1478 
1479 	if (msp->ms_unflushed_frees == NULL)
1480 		return (0);
1481 
1482 	if (zfs_btree_numnodes(&msp->ms_unflushed_frees_by_size) == 0)
1483 		metaslab_size_tree_full_load(msp->ms_unflushed_frees);
1484 	range_seg_t *rs = zfs_btree_last(&msp->ms_unflushed_frees_by_size,
1485 	    NULL);
1486 	if (rs == NULL)
1487 		return (0);
1488 
1489 	/*
1490 	 * When a range is freed from the metaslab, that range is added to
1491 	 * both the unflushed frees and the deferred frees. While the block
1492 	 * will eventually be usable, if the metaslab were loaded the range
1493 	 * would not be added to the ms_allocatable tree until TXG_DEFER_SIZE
1494 	 * txgs had passed.  As a result, when attempting to estimate an upper
1495 	 * bound for the largest currently-usable free segment in the
1496 	 * metaslab, we need to not consider any ranges currently in the defer
1497 	 * trees. This algorithm approximates the largest available chunk in
1498 	 * the largest range in the unflushed_frees tree by taking the first
1499 	 * chunk.  While this may be a poor estimate, it should only remain so
1500 	 * briefly and should eventually self-correct as frees are no longer
1501 	 * deferred. Similar logic applies to the ms_freed tree. See
1502 	 * metaslab_load() for more details.
1503 	 *
1504 	 * There are two primary sources of innacuracy in this estimate. Both
1505 	 * are tolerated for performance reasons. The first source is that we
1506 	 * only check the largest segment for overlaps. Smaller segments may
1507 	 * have more favorable overlaps with the other trees, resulting in
1508 	 * larger usable chunks.  Second, we only look at the first chunk in
1509 	 * the largest segment; there may be other usable chunks in the
1510 	 * largest segment, but we ignore them.
1511 	 */
1512 	uint64_t rstart = rs_get_start(rs, msp->ms_unflushed_frees);
1513 	uint64_t rsize = rs_get_end(rs, msp->ms_unflushed_frees) - rstart;
1514 	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
1515 		uint64_t start = 0;
1516 		uint64_t size = 0;
1517 		boolean_t found = range_tree_find_in(msp->ms_defer[t], rstart,
1518 		    rsize, &start, &size);
1519 		if (found) {
1520 			if (rstart == start)
1521 				return (0);
1522 			rsize = start - rstart;
1523 		}
1524 	}
1525 
1526 	uint64_t start = 0;
1527 	uint64_t size = 0;
1528 	boolean_t found = range_tree_find_in(msp->ms_freed, rstart,
1529 	    rsize, &start, &size);
1530 	if (found)
1531 		rsize = start - rstart;
1532 
1533 	return (rsize);
1534 }
1535 
1536 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)1537 metaslab_block_find(zfs_btree_t *t, range_tree_t *rt, uint64_t start,
1538     uint64_t size, zfs_btree_index_t *where)
1539 {
1540 	range_seg_t *rs;
1541 	range_seg_max_t rsearch;
1542 
1543 	rs_set_start(&rsearch, rt, start);
1544 	rs_set_end(&rsearch, rt, start + size);
1545 
1546 	rs = zfs_btree_find(t, &rsearch, where);
1547 	if (rs == NULL) {
1548 		rs = zfs_btree_next(t, where, where);
1549 	}
1550 
1551 	return (rs);
1552 }
1553 
1554 /*
1555  * This is a helper function that can be used by the allocator to find a
1556  * suitable block to allocate. This will search the specified B-tree looking
1557  * for a block that matches the specified criteria.
1558  */
1559 static uint64_t
metaslab_block_picker(range_tree_t * rt,uint64_t * cursor,uint64_t size,uint64_t max_search)1560 metaslab_block_picker(range_tree_t *rt, uint64_t *cursor, uint64_t size,
1561     uint64_t max_search)
1562 {
1563 	if (*cursor == 0)
1564 		*cursor = rt->rt_start;
1565 	zfs_btree_t *bt = &rt->rt_root;
1566 	zfs_btree_index_t where;
1567 	range_seg_t *rs = metaslab_block_find(bt, rt, *cursor, size, &where);
1568 	uint64_t first_found;
1569 	int count_searched = 0;
1570 
1571 	if (rs != NULL)
1572 		first_found = rs_get_start(rs, rt);
1573 
1574 	while (rs != NULL && (rs_get_start(rs, rt) - first_found <=
1575 	    max_search || count_searched < metaslab_min_search_count)) {
1576 		uint64_t offset = rs_get_start(rs, rt);
1577 		if (offset + size <= rs_get_end(rs, rt)) {
1578 			*cursor = offset + size;
1579 			return (offset);
1580 		}
1581 		rs = zfs_btree_next(bt, &where, &where);
1582 		count_searched++;
1583 	}
1584 
1585 	*cursor = 0;
1586 	return (-1ULL);
1587 }
1588 
1589 /*
1590  * ==========================================================================
1591  * Dynamic Fit (df) block allocator
1592  *
1593  * Search for a free chunk of at least this size, starting from the last
1594  * offset (for this alignment of block) looking for up to
1595  * metaslab_df_max_search bytes (16MB).  If a large enough free chunk is not
1596  * found within 16MB, then return a free chunk of exactly the requested size (or
1597  * larger).
1598  *
1599  * If it seems like searching from the last offset will be unproductive, skip
1600  * that and just return a free chunk of exactly the requested size (or larger).
1601  * This is based on metaslab_df_alloc_threshold and metaslab_df_free_pct.  This
1602  * mechanism is probably not very useful and may be removed in the future.
1603  *
1604  * The behavior when not searching can be changed to return the largest free
1605  * chunk, instead of a free chunk of exactly the requested size, by setting
1606  * metaslab_df_use_largest_segment.
1607  * ==========================================================================
1608  */
1609 static uint64_t
metaslab_df_alloc(metaslab_t * msp,uint64_t size)1610 metaslab_df_alloc(metaslab_t *msp, uint64_t size)
1611 {
1612 	/*
1613 	 * Find the largest power of 2 block size that evenly divides the
1614 	 * requested size. This is used to try to allocate blocks with similar
1615 	 * alignment from the same area of the metaslab (i.e. same cursor
1616 	 * bucket) but it does not guarantee that other allocations sizes
1617 	 * may exist in the same region.
1618 	 */
1619 	uint64_t align = size & -size;
1620 	uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1];
1621 	range_tree_t *rt = msp->ms_allocatable;
1622 	int free_pct = range_tree_space(rt) * 100 / msp->ms_size;
1623 	uint64_t offset;
1624 
1625 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1626 
1627 	/*
1628 	 * If we're running low on space, find a segment based on size,
1629 	 * rather than iterating based on offset.
1630 	 */
1631 	if (metaslab_largest_allocatable(msp) < metaslab_df_alloc_threshold ||
1632 	    free_pct < metaslab_df_free_pct) {
1633 		offset = -1;
1634 	} else {
1635 		offset = metaslab_block_picker(rt,
1636 		    cursor, size, metaslab_df_max_search);
1637 	}
1638 
1639 	if (offset == -1) {
1640 		range_seg_t *rs;
1641 		if (zfs_btree_numnodes(&msp->ms_allocatable_by_size) == 0)
1642 			metaslab_size_tree_full_load(msp->ms_allocatable);
1643 		if (metaslab_df_use_largest_segment) {
1644 			/* use largest free segment */
1645 			rs = zfs_btree_last(&msp->ms_allocatable_by_size, NULL);
1646 		} else {
1647 			zfs_btree_index_t where;
1648 			/* use segment of this size, or next largest */
1649 #ifdef _METASLAB_TRACING
1650 			metaslab_rt_arg_t *mrap = msp->ms_allocatable->rt_arg;
1651 			if (size < (1 << mrap->mra_floor_shift)) {
1652 				METASLABSTAT_BUMP(
1653 				    metaslabstat_df_find_under_floor);
1654 			}
1655 #endif
1656 			rs = metaslab_block_find(&msp->ms_allocatable_by_size,
1657 			    rt, msp->ms_start, size, &where);
1658 		}
1659 		if (rs != NULL && rs_get_start(rs, rt) + size <= rs_get_end(rs,
1660 		    rt)) {
1661 			offset = rs_get_start(rs, rt);
1662 			*cursor = offset + size;
1663 		}
1664 	}
1665 
1666 	return (offset);
1667 }
1668 
1669 static metaslab_ops_t metaslab_df_ops = {
1670 	metaslab_df_alloc
1671 };
1672 
1673 /*
1674  * ==========================================================================
1675  * Cursor fit block allocator -
1676  * Select the largest region in the metaslab, set the cursor to the beginning
1677  * of the range and the cursor_end to the end of the range. As allocations
1678  * are made advance the cursor. Continue allocating from the cursor until
1679  * the range is exhausted and then find a new range.
1680  * ==========================================================================
1681  */
1682 static uint64_t
metaslab_cf_alloc(metaslab_t * msp,uint64_t size)1683 metaslab_cf_alloc(metaslab_t *msp, uint64_t size)
1684 {
1685 	range_tree_t *rt = msp->ms_allocatable;
1686 	zfs_btree_t *t = &msp->ms_allocatable_by_size;
1687 	uint64_t *cursor = &msp->ms_lbas[0];
1688 	uint64_t *cursor_end = &msp->ms_lbas[1];
1689 	uint64_t offset = 0;
1690 
1691 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1692 
1693 	ASSERT3U(*cursor_end, >=, *cursor);
1694 
1695 	if ((*cursor + size) > *cursor_end) {
1696 		range_seg_t *rs;
1697 
1698 		if (zfs_btree_numnodes(t) == 0)
1699 			metaslab_size_tree_full_load(msp->ms_allocatable);
1700 		rs = zfs_btree_last(t, NULL);
1701 		if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) <
1702 		    size)
1703 			return (-1ULL);
1704 
1705 		*cursor = rs_get_start(rs, rt);
1706 		*cursor_end = rs_get_end(rs, rt);
1707 	}
1708 
1709 	offset = *cursor;
1710 	*cursor += size;
1711 
1712 	return (offset);
1713 }
1714 
1715 static metaslab_ops_t metaslab_cf_ops = {
1716 	metaslab_cf_alloc
1717 };
1718 
1719 /*
1720  * ==========================================================================
1721  * New dynamic fit allocator -
1722  * Select a region that is large enough to allocate 2^metaslab_ndf_clump_shift
1723  * contiguous blocks. If no region is found then just use the largest segment
1724  * that remains.
1725  * ==========================================================================
1726  */
1727 
1728 /*
1729  * Determines desired number of contiguous blocks (2^metaslab_ndf_clump_shift)
1730  * to request from the allocator.
1731  */
1732 uint64_t metaslab_ndf_clump_shift = 4;
1733 
1734 static uint64_t
metaslab_ndf_alloc(metaslab_t * msp,uint64_t size)1735 metaslab_ndf_alloc(metaslab_t *msp, uint64_t size)
1736 {
1737 	zfs_btree_t *t = &msp->ms_allocatable->rt_root;
1738 	range_tree_t *rt = msp->ms_allocatable;
1739 	zfs_btree_index_t where;
1740 	range_seg_t *rs;
1741 	range_seg_max_t rsearch;
1742 	uint64_t hbit = highbit64(size);
1743 	uint64_t *cursor = &msp->ms_lbas[hbit - 1];
1744 	uint64_t max_size = metaslab_largest_allocatable(msp);
1745 
1746 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1747 
1748 	if (max_size < size)
1749 		return (-1ULL);
1750 
1751 	rs_set_start(&rsearch, rt, *cursor);
1752 	rs_set_end(&rsearch, rt, *cursor + size);
1753 
1754 	rs = zfs_btree_find(t, &rsearch, &where);
1755 	if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) < size) {
1756 		t = &msp->ms_allocatable_by_size;
1757 
1758 		rs_set_start(&rsearch, rt, 0);
1759 		rs_set_end(&rsearch, rt, MIN(max_size, 1ULL << (hbit +
1760 		    metaslab_ndf_clump_shift)));
1761 
1762 		rs = zfs_btree_find(t, &rsearch, &where);
1763 		if (rs == NULL)
1764 			rs = zfs_btree_next(t, &where, &where);
1765 		ASSERT(rs != NULL);
1766 	}
1767 
1768 	if ((rs_get_end(rs, rt) - rs_get_start(rs, rt)) >= size) {
1769 		*cursor = rs_get_start(rs, rt) + size;
1770 		return (rs_get_start(rs, rt));
1771 	}
1772 	return (-1ULL);
1773 }
1774 
1775 static metaslab_ops_t metaslab_ndf_ops = {
1776 	metaslab_ndf_alloc
1777 };
1778 
1779 metaslab_ops_t *zfs_metaslab_ops = &metaslab_df_ops;
1780 
1781 /*
1782  * ==========================================================================
1783  * Metaslabs
1784  * ==========================================================================
1785  */
1786 
1787 /*
1788  * Wait for any in-progress metaslab loads to complete.
1789  */
1790 void
metaslab_load_wait(metaslab_t * msp)1791 metaslab_load_wait(metaslab_t *msp)
1792 {
1793 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1794 
1795 	while (msp->ms_loading) {
1796 		ASSERT(!msp->ms_loaded);
1797 		cv_wait(&msp->ms_load_cv, &msp->ms_lock);
1798 	}
1799 }
1800 
1801 /*
1802  * Wait for any in-progress flushing to complete.
1803  */
1804 void
metaslab_flush_wait(metaslab_t * msp)1805 metaslab_flush_wait(metaslab_t *msp)
1806 {
1807 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1808 
1809 	while (msp->ms_flushing)
1810 		cv_wait(&msp->ms_flush_cv, &msp->ms_lock);
1811 }
1812 
1813 static unsigned int
metaslab_idx_func(multilist_t * ml,void * arg)1814 metaslab_idx_func(multilist_t *ml, void *arg)
1815 {
1816 	metaslab_t *msp = arg;
1817 	return (msp->ms_id % multilist_get_num_sublists(ml));
1818 }
1819 
1820 uint64_t
metaslab_allocated_space(metaslab_t * msp)1821 metaslab_allocated_space(metaslab_t *msp)
1822 {
1823 	return (msp->ms_allocated_space);
1824 }
1825 
1826 /*
1827  * Verify that the space accounting on disk matches the in-core range_trees.
1828  */
1829 static void
metaslab_verify_space(metaslab_t * msp,uint64_t txg)1830 metaslab_verify_space(metaslab_t *msp, uint64_t txg)
1831 {
1832 	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
1833 	uint64_t allocating = 0;
1834 	uint64_t sm_free_space, msp_free_space;
1835 
1836 	ASSERT(MUTEX_HELD(&msp->ms_lock));
1837 	ASSERT(!msp->ms_condensing);
1838 
1839 	if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0)
1840 		return;
1841 
1842 	/*
1843 	 * We can only verify the metaslab space when we're called
1844 	 * from syncing context with a loaded metaslab that has an
1845 	 * allocated space map. Calling this in non-syncing context
1846 	 * does not provide a consistent view of the metaslab since
1847 	 * we're performing allocations in the future.
1848 	 */
1849 	if (txg != spa_syncing_txg(spa) || msp->ms_sm == NULL ||
1850 	    !msp->ms_loaded)
1851 		return;
1852 
1853 	/*
1854 	 * Even though the smp_alloc field can get negative,
1855 	 * when it comes to a metaslab's space map, that should
1856 	 * never be the case.
1857 	 */
1858 	ASSERT3S(space_map_allocated(msp->ms_sm), >=, 0);
1859 
1860 	ASSERT3U(space_map_allocated(msp->ms_sm), >=,
1861 	    range_tree_space(msp->ms_unflushed_frees));
1862 
1863 	ASSERT3U(metaslab_allocated_space(msp), ==,
1864 	    space_map_allocated(msp->ms_sm) +
1865 	    range_tree_space(msp->ms_unflushed_allocs) -
1866 	    range_tree_space(msp->ms_unflushed_frees));
1867 
1868 	sm_free_space = msp->ms_size - metaslab_allocated_space(msp);
1869 
1870 	/*
1871 	 * Account for future allocations since we would have
1872 	 * already deducted that space from the ms_allocatable.
1873 	 */
1874 	for (int t = 0; t < TXG_CONCURRENT_STATES; t++) {
1875 		allocating +=
1876 		    range_tree_space(msp->ms_allocating[(txg + t) & TXG_MASK]);
1877 	}
1878 	ASSERT3U(allocating + msp->ms_allocated_this_txg, ==,
1879 	    msp->ms_allocating_total);
1880 
1881 	ASSERT3U(msp->ms_deferspace, ==,
1882 	    range_tree_space(msp->ms_defer[0]) +
1883 	    range_tree_space(msp->ms_defer[1]));
1884 
1885 	msp_free_space = range_tree_space(msp->ms_allocatable) + allocating +
1886 	    msp->ms_deferspace + range_tree_space(msp->ms_freed);
1887 
1888 	VERIFY3U(sm_free_space, ==, msp_free_space);
1889 }
1890 
1891 static void
metaslab_aux_histograms_clear(metaslab_t * msp)1892 metaslab_aux_histograms_clear(metaslab_t *msp)
1893 {
1894 	/*
1895 	 * Auxiliary histograms are only cleared when resetting them,
1896 	 * which can only happen while the metaslab is loaded.
1897 	 */
1898 	ASSERT(msp->ms_loaded);
1899 
1900 	bzero(msp->ms_synchist, sizeof (msp->ms_synchist));
1901 	for (int t = 0; t < TXG_DEFER_SIZE; t++)
1902 		bzero(msp->ms_deferhist[t], sizeof (msp->ms_deferhist[t]));
1903 }
1904 
1905 static void
metaslab_aux_histogram_add(uint64_t * histogram,uint64_t shift,range_tree_t * rt)1906 metaslab_aux_histogram_add(uint64_t *histogram, uint64_t shift,
1907     range_tree_t *rt)
1908 {
1909 	/*
1910 	 * This is modeled after space_map_histogram_add(), so refer to that
1911 	 * function for implementation details. We want this to work like
1912 	 * the space map histogram, and not the range tree histogram, as we
1913 	 * are essentially constructing a delta that will be later subtracted
1914 	 * from the space map histogram.
1915 	 */
1916 	int idx = 0;
1917 	for (int i = shift; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
1918 		ASSERT3U(i, >=, idx + shift);
1919 		histogram[idx] += rt->rt_histogram[i] << (i - idx - shift);
1920 
1921 		if (idx < SPACE_MAP_HISTOGRAM_SIZE - 1) {
1922 			ASSERT3U(idx + shift, ==, i);
1923 			idx++;
1924 			ASSERT3U(idx, <, SPACE_MAP_HISTOGRAM_SIZE);
1925 		}
1926 	}
1927 }
1928 
1929 /*
1930  * Called at every sync pass that the metaslab gets synced.
1931  *
1932  * The reason is that we want our auxiliary histograms to be updated
1933  * wherever the metaslab's space map histogram is updated. This way
1934  * we stay consistent on which parts of the metaslab space map's
1935  * histogram are currently not available for allocations (e.g because
1936  * they are in the defer, freed, and freeing trees).
1937  */
1938 static void
metaslab_aux_histograms_update(metaslab_t * msp)1939 metaslab_aux_histograms_update(metaslab_t *msp)
1940 {
1941 	space_map_t *sm = msp->ms_sm;
1942 	ASSERT(sm != NULL);
1943 
1944 	/*
1945 	 * This is similar to the metaslab's space map histogram updates
1946 	 * that take place in metaslab_sync(). The only difference is that
1947 	 * we only care about segments that haven't made it into the
1948 	 * ms_allocatable tree yet.
1949 	 */
1950 	if (msp->ms_loaded) {
1951 		metaslab_aux_histograms_clear(msp);
1952 
1953 		metaslab_aux_histogram_add(msp->ms_synchist,
1954 		    sm->sm_shift, msp->ms_freed);
1955 
1956 		for (int t = 0; t < TXG_DEFER_SIZE; t++) {
1957 			metaslab_aux_histogram_add(msp->ms_deferhist[t],
1958 			    sm->sm_shift, msp->ms_defer[t]);
1959 		}
1960 	}
1961 
1962 	metaslab_aux_histogram_add(msp->ms_synchist,
1963 	    sm->sm_shift, msp->ms_freeing);
1964 }
1965 
1966 /*
1967  * Called every time we are done syncing (writing to) the metaslab,
1968  * i.e. at the end of each sync pass.
1969  * [see the comment in metaslab_impl.h for ms_synchist, ms_deferhist]
1970  */
1971 static void
metaslab_aux_histograms_update_done(metaslab_t * msp,boolean_t defer_allowed)1972 metaslab_aux_histograms_update_done(metaslab_t *msp, boolean_t defer_allowed)
1973 {
1974 	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
1975 	space_map_t *sm = msp->ms_sm;
1976 
1977 	if (sm == NULL) {
1978 		/*
1979 		 * We came here from metaslab_init() when creating/opening a
1980 		 * pool, looking at a metaslab that hasn't had any allocations
1981 		 * yet.
1982 		 */
1983 		return;
1984 	}
1985 
1986 	/*
1987 	 * This is similar to the actions that we take for the ms_freed
1988 	 * and ms_defer trees in metaslab_sync_done().
1989 	 */
1990 	uint64_t hist_index = spa_syncing_txg(spa) % TXG_DEFER_SIZE;
1991 	if (defer_allowed) {
1992 		bcopy(msp->ms_synchist, msp->ms_deferhist[hist_index],
1993 		    sizeof (msp->ms_synchist));
1994 	} else {
1995 		bzero(msp->ms_deferhist[hist_index],
1996 		    sizeof (msp->ms_deferhist[hist_index]));
1997 	}
1998 	bzero(msp->ms_synchist, sizeof (msp->ms_synchist));
1999 }
2000 
2001 /*
2002  * Ensure that the metaslab's weight and fragmentation are consistent
2003  * with the contents of the histogram (either the range tree's histogram
2004  * or the space map's depending whether the metaslab is loaded).
2005  */
2006 static void
metaslab_verify_weight_and_frag(metaslab_t * msp)2007 metaslab_verify_weight_and_frag(metaslab_t *msp)
2008 {
2009 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2010 
2011 	if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0)
2012 		return;
2013 
2014 	/*
2015 	 * We can end up here from vdev_remove_complete(), in which case we
2016 	 * cannot do these assertions because we hold spa config locks and
2017 	 * thus we are not allowed to read from the DMU.
2018 	 *
2019 	 * We check if the metaslab group has been removed and if that's
2020 	 * the case we return immediately as that would mean that we are
2021 	 * here from the aforementioned code path.
2022 	 */
2023 	if (msp->ms_group == NULL)
2024 		return;
2025 
2026 	/*
2027 	 * Devices being removed always return a weight of 0 and leave
2028 	 * fragmentation and ms_max_size as is - there is nothing for
2029 	 * us to verify here.
2030 	 */
2031 	vdev_t *vd = msp->ms_group->mg_vd;
2032 	if (vd->vdev_removing)
2033 		return;
2034 
2035 	/*
2036 	 * If the metaslab is dirty it probably means that we've done
2037 	 * some allocations or frees that have changed our histograms
2038 	 * and thus the weight.
2039 	 */
2040 	for (int t = 0; t < TXG_SIZE; t++) {
2041 		if (txg_list_member(&vd->vdev_ms_list, msp, t))
2042 			return;
2043 	}
2044 
2045 	/*
2046 	 * This verification checks that our in-memory state is consistent
2047 	 * with what's on disk. If the pool is read-only then there aren't
2048 	 * any changes and we just have the initially-loaded state.
2049 	 */
2050 	if (!spa_writeable(msp->ms_group->mg_vd->vdev_spa))
2051 		return;
2052 
2053 	/* some extra verification for in-core tree if you can */
2054 	if (msp->ms_loaded) {
2055 		range_tree_stat_verify(msp->ms_allocatable);
2056 		VERIFY(space_map_histogram_verify(msp->ms_sm,
2057 		    msp->ms_allocatable));
2058 	}
2059 
2060 	uint64_t weight = msp->ms_weight;
2061 	uint64_t was_active = msp->ms_weight & METASLAB_ACTIVE_MASK;
2062 	boolean_t space_based = WEIGHT_IS_SPACEBASED(msp->ms_weight);
2063 	uint64_t frag = msp->ms_fragmentation;
2064 	uint64_t max_segsize = msp->ms_max_size;
2065 
2066 	msp->ms_weight = 0;
2067 	msp->ms_fragmentation = 0;
2068 
2069 	/*
2070 	 * This function is used for verification purposes. Regardless of
2071 	 * whether metaslab_weight() thinks this metaslab should be active or
2072 	 * not, we want to ensure that the actual weight (and therefore the
2073 	 * value of ms_weight) would be the same if it was to be recalculated
2074 	 * at this point.
2075 	 */
2076 	msp->ms_weight = metaslab_weight(msp) | was_active;
2077 
2078 	VERIFY3U(max_segsize, ==, msp->ms_max_size);
2079 
2080 	/*
2081 	 * If the weight type changed then there is no point in doing
2082 	 * verification. Revert fields to their original values.
2083 	 */
2084 	if ((space_based && !WEIGHT_IS_SPACEBASED(msp->ms_weight)) ||
2085 	    (!space_based && WEIGHT_IS_SPACEBASED(msp->ms_weight))) {
2086 		msp->ms_fragmentation = frag;
2087 		msp->ms_weight = weight;
2088 		return;
2089 	}
2090 
2091 	VERIFY3U(msp->ms_fragmentation, ==, frag);
2092 	VERIFY3U(msp->ms_weight, ==, weight);
2093 }
2094 
2095 /*
2096  * If we're over the zfs_metaslab_mem_limit, select the loaded metaslab from
2097  * this class that was used longest ago, and attempt to unload it.  We don't
2098  * want to spend too much time in this loop to prevent performance
2099  * degredation, and we expect that most of the time this operation will
2100  * succeed. Between that and the normal unloading processing during txg sync,
2101  * we expect this to keep the metaslab memory usage under control.
2102  */
2103 static void
metaslab_potentially_evict(metaslab_class_t * mc)2104 metaslab_potentially_evict(metaslab_class_t *mc)
2105 {
2106 #ifdef _KERNEL
2107 	uint64_t allmem = arc_all_memory();
2108 	extern kmem_cache_t *zfs_btree_leaf_cache;
2109 	uint64_t inuse = kmem_cache_stat(zfs_btree_leaf_cache, "buf_inuse");
2110 	uint64_t size =  kmem_cache_stat(zfs_btree_leaf_cache, "buf_size");
2111 	int tries = 0;
2112 	for (; allmem * zfs_metaslab_mem_limit / 100 < inuse * size &&
2113 	    tries < multilist_get_num_sublists(mc->mc_metaslab_txg_list) * 2;
2114 	    tries++) {
2115 		unsigned int idx = multilist_get_random_index(
2116 		    mc->mc_metaslab_txg_list);
2117 		multilist_sublist_t *mls =
2118 		    multilist_sublist_lock(mc->mc_metaslab_txg_list, idx);
2119 		metaslab_t *msp = multilist_sublist_head(mls);
2120 		multilist_sublist_unlock(mls);
2121 		while (msp != NULL && allmem * zfs_metaslab_mem_limit / 100 <
2122 		    inuse * size) {
2123 			VERIFY3P(mls, ==, multilist_sublist_lock(
2124 			    mc->mc_metaslab_txg_list, idx));
2125 			ASSERT3U(idx, ==,
2126 			    metaslab_idx_func(mc->mc_metaslab_txg_list, msp));
2127 
2128 			if (!multilist_link_active(&msp->ms_class_txg_node)) {
2129 				multilist_sublist_unlock(mls);
2130 				break;
2131 			}
2132 			metaslab_t *next_msp = multilist_sublist_next(mls, msp);
2133 			multilist_sublist_unlock(mls);
2134 			/*
2135 			 * If the metaslab is currently loading there are two
2136 			 * cases. If it's the metaslab we're evicting, we
2137 			 * can't continue on or we'll panic when we attempt to
2138 			 * recursively lock the mutex. If it's another
2139 			 * metaslab that's loading, it can be safely skipped,
2140 			 * since we know it's very new and therefore not a
2141 			 * good eviction candidate. We check later once the
2142 			 * lock is held that the metaslab is fully loaded
2143 			 * before actually unloading it.
2144 			 */
2145 			if (msp->ms_loading) {
2146 				msp = next_msp;
2147 				inuse = kmem_cache_stat(zfs_btree_leaf_cache,
2148 				    "buf_inuse");
2149 				continue;
2150 			}
2151 			/*
2152 			 * We can't unload metaslabs with no spacemap because
2153 			 * they're not ready to be unloaded yet. We can't
2154 			 * unload metaslabs with outstanding allocations
2155 			 * because doing so could cause the metaslab's weight
2156 			 * to decrease while it's unloaded, which violates an
2157 			 * invariant that we use to prevent unnecessary
2158 			 * loading. We also don't unload metaslabs that are
2159 			 * currently active because they are high-weight
2160 			 * metaslabs that are likely to be used in the near
2161 			 * future.
2162 			 */
2163 			mutex_enter(&msp->ms_lock);
2164 			if (msp->ms_allocator == -1 && msp->ms_sm != NULL &&
2165 			    msp->ms_allocating_total == 0) {
2166 				metaslab_unload(msp);
2167 			}
2168 			mutex_exit(&msp->ms_lock);
2169 			msp = next_msp;
2170 			inuse = kmem_cache_stat(zfs_btree_leaf_cache,
2171 			    "buf_inuse");
2172 		}
2173 	}
2174 #endif
2175 }
2176 
2177 static int
metaslab_load_impl(metaslab_t * msp)2178 metaslab_load_impl(metaslab_t *msp)
2179 {
2180 	int error = 0;
2181 
2182 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2183 	ASSERT(msp->ms_loading);
2184 	ASSERT(!msp->ms_condensing);
2185 
2186 	/*
2187 	 * We temporarily drop the lock to unblock other operations while we
2188 	 * are reading the space map. Therefore, metaslab_sync() and
2189 	 * metaslab_sync_done() can run at the same time as we do.
2190 	 *
2191 	 * If we are using the log space maps, metaslab_sync() can't write to
2192 	 * the metaslab's space map while we are loading as we only write to
2193 	 * it when we are flushing the metaslab, and that can't happen while
2194 	 * we are loading it.
2195 	 *
2196 	 * If we are not using log space maps though, metaslab_sync() can
2197 	 * append to the space map while we are loading. Therefore we load
2198 	 * only entries that existed when we started the load. Additionally,
2199 	 * metaslab_sync_done() has to wait for the load to complete because
2200 	 * there are potential races like metaslab_load() loading parts of the
2201 	 * space map that are currently being appended by metaslab_sync(). If
2202 	 * we didn't, the ms_allocatable would have entries that
2203 	 * metaslab_sync_done() would try to re-add later.
2204 	 *
2205 	 * That's why before dropping the lock we remember the synced length
2206 	 * of the metaslab and read up to that point of the space map,
2207 	 * ignoring entries appended by metaslab_sync() that happen after we
2208 	 * drop the lock.
2209 	 */
2210 	uint64_t length = msp->ms_synced_length;
2211 	mutex_exit(&msp->ms_lock);
2212 
2213 	hrtime_t load_start = gethrtime();
2214 	metaslab_rt_arg_t *mrap;
2215 	if (msp->ms_allocatable->rt_arg == NULL) {
2216 		mrap = kmem_zalloc(sizeof (*mrap), KM_SLEEP);
2217 	} else {
2218 		mrap = msp->ms_allocatable->rt_arg;
2219 		msp->ms_allocatable->rt_ops = NULL;
2220 		msp->ms_allocatable->rt_arg = NULL;
2221 	}
2222 	mrap->mra_bt = &msp->ms_allocatable_by_size;
2223 	mrap->mra_floor_shift = metaslab_by_size_min_shift;
2224 
2225 	if (msp->ms_sm != NULL) {
2226 		error = space_map_load_length(msp->ms_sm, msp->ms_allocatable,
2227 		    SM_FREE, length);
2228 
2229 		/* Now, populate the size-sorted tree. */
2230 		metaslab_rt_create(msp->ms_allocatable, mrap);
2231 		msp->ms_allocatable->rt_ops = &metaslab_rt_ops;
2232 		msp->ms_allocatable->rt_arg = mrap;
2233 
2234 		struct mssa_arg arg = {0};
2235 		arg.rt = msp->ms_allocatable;
2236 		arg.mra = mrap;
2237 		range_tree_walk(msp->ms_allocatable, metaslab_size_sorted_add,
2238 		    &arg);
2239 	} else {
2240 		/*
2241 		 * Add the size-sorted tree first, since we don't need to load
2242 		 * the metaslab from the spacemap.
2243 		 */
2244 		metaslab_rt_create(msp->ms_allocatable, mrap);
2245 		msp->ms_allocatable->rt_ops = &metaslab_rt_ops;
2246 		msp->ms_allocatable->rt_arg = mrap;
2247 		/*
2248 		 * The space map has not been allocated yet, so treat
2249 		 * all the space in the metaslab as free and add it to the
2250 		 * ms_allocatable tree.
2251 		 */
2252 		range_tree_add(msp->ms_allocatable,
2253 		    msp->ms_start, msp->ms_size);
2254 
2255 		if (msp->ms_freed != NULL) {
2256 			/*
2257 			 * If the ms_sm doesn't exist, this means that this
2258 			 * metaslab hasn't gone through metaslab_sync() and
2259 			 * thus has never been dirtied. So we shouldn't
2260 			 * expect any unflushed allocs or frees from previous
2261 			 * TXGs.
2262 			 *
2263 			 * Note: ms_freed and all the other trees except for
2264 			 * the ms_allocatable, can be NULL at this point only
2265 			 * if this is a new metaslab of a vdev that just got
2266 			 * expanded.
2267 			 */
2268 			ASSERT(range_tree_is_empty(msp->ms_unflushed_allocs));
2269 			ASSERT(range_tree_is_empty(msp->ms_unflushed_frees));
2270 		}
2271 	}
2272 
2273 	/*
2274 	 * We need to grab the ms_sync_lock to prevent metaslab_sync() from
2275 	 * changing the ms_sm (or log_sm) and the metaslab's range trees
2276 	 * while we are about to use them and populate the ms_allocatable.
2277 	 * The ms_lock is insufficient for this because metaslab_sync() doesn't
2278 	 * hold the ms_lock while writing the ms_checkpointing tree to disk.
2279 	 */
2280 	mutex_enter(&msp->ms_sync_lock);
2281 	mutex_enter(&msp->ms_lock);
2282 
2283 	ASSERT(!msp->ms_condensing);
2284 	ASSERT(!msp->ms_flushing);
2285 
2286 	if (error != 0) {
2287 		mutex_exit(&msp->ms_sync_lock);
2288 		return (error);
2289 	}
2290 
2291 	ASSERT3P(msp->ms_group, !=, NULL);
2292 	msp->ms_loaded = B_TRUE;
2293 
2294 	/*
2295 	 * Apply all the unflushed changes to ms_allocatable right
2296 	 * away so any manipulations we do below have a clear view
2297 	 * of what is allocated and what is free.
2298 	 */
2299 	range_tree_walk(msp->ms_unflushed_allocs,
2300 	    range_tree_remove, msp->ms_allocatable);
2301 	range_tree_walk(msp->ms_unflushed_frees,
2302 	    range_tree_add, msp->ms_allocatable);
2303 
2304 	msp->ms_loaded = B_TRUE;
2305 
2306 	ASSERT3P(msp->ms_group, !=, NULL);
2307 	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
2308 	if (spa_syncing_log_sm(spa) != NULL) {
2309 		ASSERT(spa_feature_is_enabled(spa,
2310 		    SPA_FEATURE_LOG_SPACEMAP));
2311 
2312 		/*
2313 		 * If we use a log space map we add all the segments
2314 		 * that are in ms_unflushed_frees so they are available
2315 		 * for allocation.
2316 		 *
2317 		 * ms_allocatable needs to contain all free segments
2318 		 * that are ready for allocations (thus not segments
2319 		 * from ms_freeing, ms_freed, and the ms_defer trees).
2320 		 * But if we grab the lock in this code path at a sync
2321 		 * pass later that 1, then it also contains the
2322 		 * segments of ms_freed (they were added to it earlier
2323 		 * in this path through ms_unflushed_frees). So we
2324 		 * need to remove all the segments that exist in
2325 		 * ms_freed from ms_allocatable as they will be added
2326 		 * later in metaslab_sync_done().
2327 		 *
2328 		 * When there's no log space map, the ms_allocatable
2329 		 * correctly doesn't contain any segments that exist
2330 		 * in ms_freed [see ms_synced_length].
2331 		 */
2332 		range_tree_walk(msp->ms_freed,
2333 		    range_tree_remove, msp->ms_allocatable);
2334 	}
2335 
2336 	/*
2337 	 * If we are not using the log space map, ms_allocatable
2338 	 * contains the segments that exist in the ms_defer trees
2339 	 * [see ms_synced_length]. Thus we need to remove them
2340 	 * from ms_allocatable as they will be added again in
2341 	 * metaslab_sync_done().
2342 	 *
2343 	 * If we are using the log space map, ms_allocatable still
2344 	 * contains the segments that exist in the ms_defer trees.
2345 	 * Not because it read them through the ms_sm though. But
2346 	 * because these segments are part of ms_unflushed_frees
2347 	 * whose segments we add to ms_allocatable earlier in this
2348 	 * code path.
2349 	 */
2350 	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
2351 		range_tree_walk(msp->ms_defer[t],
2352 		    range_tree_remove, msp->ms_allocatable);
2353 	}
2354 
2355 	/*
2356 	 * Call metaslab_recalculate_weight_and_sort() now that the
2357 	 * metaslab is loaded so we get the metaslab's real weight.
2358 	 *
2359 	 * Unless this metaslab was created with older software and
2360 	 * has not yet been converted to use segment-based weight, we
2361 	 * expect the new weight to be better or equal to the weight
2362 	 * that the metaslab had while it was not loaded. This is
2363 	 * because the old weight does not take into account the
2364 	 * consolidation of adjacent segments between TXGs. [see
2365 	 * comment for ms_synchist and ms_deferhist[] for more info]
2366 	 */
2367 	uint64_t weight = msp->ms_weight;
2368 	uint64_t max_size = msp->ms_max_size;
2369 	metaslab_recalculate_weight_and_sort(msp);
2370 	if (!WEIGHT_IS_SPACEBASED(weight))
2371 		ASSERT3U(weight, <=, msp->ms_weight);
2372 	msp->ms_max_size = metaslab_largest_allocatable(msp);
2373 	ASSERT3U(max_size, <=, msp->ms_max_size);
2374 	hrtime_t load_end = gethrtime();
2375 	msp->ms_load_time = load_end;
2376 	if (zfs_flags & ZFS_DEBUG_LOG_SPACEMAP) {
2377 		zfs_dbgmsg("loading: txg %llu, spa %s, vdev_id %llu, "
2378 		    "ms_id %llu, smp_length %llu, "
2379 		    "unflushed_allocs %llu, unflushed_frees %llu, "
2380 		    "freed %llu, defer %llu + %llu, "
2381 		    "loading_time %lld ms, ms_max_size %llu, "
2382 		    "max size error %llu",
2383 		    spa_syncing_txg(spa), spa_name(spa),
2384 		    msp->ms_group->mg_vd->vdev_id, msp->ms_id,
2385 		    space_map_length(msp->ms_sm),
2386 		    range_tree_space(msp->ms_unflushed_allocs),
2387 		    range_tree_space(msp->ms_unflushed_frees),
2388 		    range_tree_space(msp->ms_freed),
2389 		    range_tree_space(msp->ms_defer[0]),
2390 		    range_tree_space(msp->ms_defer[1]),
2391 		    (longlong_t)((load_end - load_start) / 1000000),
2392 		    msp->ms_max_size, msp->ms_max_size - max_size);
2393 	}
2394 
2395 	metaslab_verify_space(msp, spa_syncing_txg(spa));
2396 	mutex_exit(&msp->ms_sync_lock);
2397 	return (0);
2398 }
2399 
2400 int
metaslab_load(metaslab_t * msp)2401 metaslab_load(metaslab_t *msp)
2402 {
2403 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2404 
2405 	/*
2406 	 * There may be another thread loading the same metaslab, if that's
2407 	 * the case just wait until the other thread is done and return.
2408 	 */
2409 	metaslab_load_wait(msp);
2410 	if (msp->ms_loaded)
2411 		return (0);
2412 	VERIFY(!msp->ms_loading);
2413 	ASSERT(!msp->ms_condensing);
2414 
2415 	/*
2416 	 * We set the loading flag BEFORE potentially dropping the lock to
2417 	 * wait for an ongoing flush (see ms_flushing below). This way other
2418 	 * threads know that there is already a thread that is loading this
2419 	 * metaslab.
2420 	 */
2421 	msp->ms_loading = B_TRUE;
2422 
2423 	/*
2424 	 * Wait for any in-progress flushing to finish as we drop the ms_lock
2425 	 * both here (during space_map_load()) and in metaslab_flush() (when
2426 	 * we flush our changes to the ms_sm).
2427 	 */
2428 	if (msp->ms_flushing)
2429 		metaslab_flush_wait(msp);
2430 
2431 	/*
2432 	 * In the possibility that we were waiting for the metaslab to be
2433 	 * flushed (where we temporarily dropped the ms_lock), ensure that
2434 	 * no one else loaded the metaslab somehow.
2435 	 */
2436 	ASSERT(!msp->ms_loaded);
2437 
2438 	/*
2439 	 * If we're loading a metaslab in the normal class, consider evicting
2440 	 * another one to keep our memory usage under the limit defined by the
2441 	 * zfs_metaslab_mem_limit tunable.
2442 	 */
2443 	if (spa_normal_class(msp->ms_group->mg_class->mc_spa) ==
2444 	    msp->ms_group->mg_class) {
2445 		metaslab_potentially_evict(msp->ms_group->mg_class);
2446 	}
2447 
2448 	int error = metaslab_load_impl(msp);
2449 
2450 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2451 	msp->ms_loading = B_FALSE;
2452 	cv_broadcast(&msp->ms_load_cv);
2453 
2454 	return (error);
2455 }
2456 
2457 void
metaslab_unload(metaslab_t * msp)2458 metaslab_unload(metaslab_t *msp)
2459 {
2460 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2461 
2462 	/*
2463 	 * This can happen if a metaslab is selected for eviction (in
2464 	 * metaslab_potentially_evict) and then unloaded during spa_sync (via
2465 	 * metaslab_class_evict_old).
2466 	 */
2467 	if (!msp->ms_loaded)
2468 		return;
2469 
2470 	range_tree_vacate(msp->ms_allocatable, NULL, NULL);
2471 	msp->ms_loaded = B_FALSE;
2472 	msp->ms_unload_time = gethrtime();
2473 
2474 	msp->ms_activation_weight = 0;
2475 	msp->ms_weight &= ~METASLAB_ACTIVE_MASK;
2476 
2477 	if (msp->ms_group != NULL) {
2478 		metaslab_class_t *mc = msp->ms_group->mg_class;
2479 		multilist_sublist_t *mls =
2480 		    multilist_sublist_lock_obj(mc->mc_metaslab_txg_list, msp);
2481 		if (multilist_link_active(&msp->ms_class_txg_node))
2482 			multilist_sublist_remove(mls, msp);
2483 		multilist_sublist_unlock(mls);
2484 	}
2485 
2486 	/*
2487 	 * We explicitly recalculate the metaslab's weight based on its space
2488 	 * map (as it is now not loaded). We want unload metaslabs to always
2489 	 * have their weights calculated from the space map histograms, while
2490 	 * loaded ones have it calculated from their in-core range tree
2491 	 * [see metaslab_load()]. This way, the weight reflects the information
2492 	 * available in-core, whether it is loaded or not.
2493 	 *
2494 	 * If ms_group == NULL means that we came here from metaslab_fini(),
2495 	 * at which point it doesn't make sense for us to do the recalculation
2496 	 * and the sorting.
2497 	 */
2498 	if (msp->ms_group != NULL)
2499 		metaslab_recalculate_weight_and_sort(msp);
2500 }
2501 
2502 /*
2503  * We want to optimize the memory use of the per-metaslab range
2504  * trees. To do this, we store the segments in the range trees in
2505  * units of sectors, zero-indexing from the start of the metaslab. If
2506  * the vdev_ms_shift - the vdev_ashift is less than 32, we can store
2507  * the ranges using two uint32_ts, rather than two uint64_ts.
2508  */
2509 static range_seg_type_t
metaslab_calculate_range_tree_type(vdev_t * vdev,metaslab_t * msp,uint64_t * start,uint64_t * shift)2510 metaslab_calculate_range_tree_type(vdev_t *vdev, metaslab_t *msp,
2511     uint64_t *start, uint64_t *shift)
2512 {
2513 	if (vdev->vdev_ms_shift - vdev->vdev_ashift < 32 &&
2514 	    !zfs_metaslab_force_large_segs) {
2515 		*shift = vdev->vdev_ashift;
2516 		*start = msp->ms_start;
2517 		return (RANGE_SEG32);
2518 	} else {
2519 		*shift = 0;
2520 		*start = 0;
2521 		return (RANGE_SEG64);
2522 	}
2523 }
2524 
2525 void
metaslab_set_selected_txg(metaslab_t * msp,uint64_t txg)2526 metaslab_set_selected_txg(metaslab_t *msp, uint64_t txg)
2527 {
2528 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2529 	metaslab_class_t *mc = msp->ms_group->mg_class;
2530 	multilist_sublist_t *mls =
2531 	    multilist_sublist_lock_obj(mc->mc_metaslab_txg_list, msp);
2532 	if (multilist_link_active(&msp->ms_class_txg_node))
2533 		multilist_sublist_remove(mls, msp);
2534 	msp->ms_selected_txg = txg;
2535 	msp->ms_selected_time = gethrtime();
2536 	multilist_sublist_insert_tail(mls, msp);
2537 	multilist_sublist_unlock(mls);
2538 }
2539 
2540 void
metaslab_space_update(vdev_t * vd,metaslab_class_t * mc,int64_t alloc_delta,int64_t defer_delta,int64_t space_delta)2541 metaslab_space_update(vdev_t *vd, metaslab_class_t *mc, int64_t alloc_delta,
2542     int64_t defer_delta, int64_t space_delta)
2543 {
2544 	vdev_space_update(vd, alloc_delta, defer_delta, space_delta);
2545 
2546 	ASSERT3P(vd->vdev_spa->spa_root_vdev, ==, vd->vdev_parent);
2547 	ASSERT(vd->vdev_ms_count != 0);
2548 
2549 	metaslab_class_space_update(mc, alloc_delta, defer_delta, space_delta,
2550 	    vdev_deflated_space(vd, space_delta));
2551 }
2552 
2553 int
metaslab_init(metaslab_group_t * mg,uint64_t id,uint64_t object,uint64_t txg,metaslab_t ** msp)2554 metaslab_init(metaslab_group_t *mg, uint64_t id, uint64_t object,
2555     uint64_t txg, metaslab_t **msp)
2556 {
2557 	vdev_t *vd = mg->mg_vd;
2558 	spa_t *spa = vd->vdev_spa;
2559 	objset_t *mos = spa->spa_meta_objset;
2560 	metaslab_t *ms;
2561 	int error;
2562 
2563 	ms = kmem_zalloc(sizeof (metaslab_t), KM_SLEEP);
2564 	mutex_init(&ms->ms_lock, NULL, MUTEX_DEFAULT, NULL);
2565 	mutex_init(&ms->ms_sync_lock, NULL, MUTEX_DEFAULT, NULL);
2566 	cv_init(&ms->ms_load_cv, NULL, CV_DEFAULT, NULL);
2567 	cv_init(&ms->ms_flush_cv, NULL, CV_DEFAULT, NULL);
2568 	multilist_link_init(&ms->ms_class_txg_node);
2569 
2570 	ms->ms_id = id;
2571 	ms->ms_start = id << vd->vdev_ms_shift;
2572 	ms->ms_size = 1ULL << vd->vdev_ms_shift;
2573 	ms->ms_allocator = -1;
2574 	ms->ms_new = B_TRUE;
2575 
2576 	/*
2577 	 * We only open space map objects that already exist. All others
2578 	 * will be opened when we finally allocate an object for it.
2579 	 *
2580 	 * Note:
2581 	 * When called from vdev_expand(), we can't call into the DMU as
2582 	 * we are holding the spa_config_lock as a writer and we would
2583 	 * deadlock [see relevant comment in vdev_metaslab_init()]. in
2584 	 * that case, the object parameter is zero though, so we won't
2585 	 * call into the DMU.
2586 	 */
2587 	if (object != 0) {
2588 		error = space_map_open(&ms->ms_sm, mos, object, ms->ms_start,
2589 		    ms->ms_size, vd->vdev_ashift);
2590 
2591 		if (error != 0) {
2592 			kmem_free(ms, sizeof (metaslab_t));
2593 			return (error);
2594 		}
2595 
2596 		ASSERT(ms->ms_sm != NULL);
2597 		ASSERT3S(space_map_allocated(ms->ms_sm), >=, 0);
2598 		ms->ms_allocated_space = space_map_allocated(ms->ms_sm);
2599 	}
2600 
2601 	range_seg_type_t type;
2602 	uint64_t shift, start;
2603 	type = metaslab_calculate_range_tree_type(vd, ms, &start, &shift);
2604 
2605 	/*
2606 	 * We create the ms_allocatable here, but we don't create the
2607 	 * other range trees until metaslab_sync_done().  This serves
2608 	 * two purposes: it allows metaslab_sync_done() to detect the
2609 	 * addition of new space; and for debugging, it ensures that
2610 	 * we'd data fault on any attempt to use this metaslab before
2611 	 * it's ready.
2612 	 */
2613 	ms->ms_allocatable = range_tree_create(NULL, type, NULL, start, shift);
2614 
2615 	ms->ms_trim = range_tree_create(NULL, type, NULL, start, shift);
2616 
2617 	metaslab_group_add(mg, ms);
2618 	metaslab_set_fragmentation(ms);
2619 
2620 	/*
2621 	 * If we're opening an existing pool (txg == 0) or creating
2622 	 * a new one (txg == TXG_INITIAL), all space is available now.
2623 	 * If we're adding space to an existing pool, the new space
2624 	 * does not become available until after this txg has synced.
2625 	 * The metaslab's weight will also be initialized when we sync
2626 	 * out this txg. This ensures that we don't attempt to allocate
2627 	 * from it before we have initialized it completely.
2628 	 */
2629 	if (txg <= TXG_INITIAL) {
2630 		metaslab_sync_done(ms, 0);
2631 		metaslab_space_update(vd, mg->mg_class,
2632 		    metaslab_allocated_space(ms), 0, 0);
2633 	}
2634 
2635 	if (txg != 0) {
2636 		vdev_dirty(vd, 0, NULL, txg);
2637 		vdev_dirty(vd, VDD_METASLAB, ms, txg);
2638 	}
2639 
2640 	*msp = ms;
2641 
2642 	return (0);
2643 }
2644 
2645 static void
metaslab_fini_flush_data(metaslab_t * msp)2646 metaslab_fini_flush_data(metaslab_t *msp)
2647 {
2648 	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
2649 
2650 	if (metaslab_unflushed_txg(msp) == 0) {
2651 		ASSERT3P(avl_find(&spa->spa_metaslabs_by_flushed, msp, NULL),
2652 		    ==, NULL);
2653 		return;
2654 	}
2655 	ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP));
2656 
2657 	mutex_enter(&spa->spa_flushed_ms_lock);
2658 	avl_remove(&spa->spa_metaslabs_by_flushed, msp);
2659 	mutex_exit(&spa->spa_flushed_ms_lock);
2660 
2661 	spa_log_sm_decrement_mscount(spa, metaslab_unflushed_txg(msp));
2662 	spa_log_summary_decrement_mscount(spa, metaslab_unflushed_txg(msp));
2663 }
2664 
2665 uint64_t
metaslab_unflushed_changes_memused(metaslab_t * ms)2666 metaslab_unflushed_changes_memused(metaslab_t *ms)
2667 {
2668 	return ((range_tree_numsegs(ms->ms_unflushed_allocs) +
2669 	    range_tree_numsegs(ms->ms_unflushed_frees)) *
2670 	    ms->ms_unflushed_allocs->rt_root.bt_elem_size);
2671 }
2672 
2673 void
metaslab_fini(metaslab_t * msp)2674 metaslab_fini(metaslab_t *msp)
2675 {
2676 	metaslab_group_t *mg = msp->ms_group;
2677 	vdev_t *vd = mg->mg_vd;
2678 	spa_t *spa = vd->vdev_spa;
2679 
2680 	metaslab_fini_flush_data(msp);
2681 
2682 	metaslab_group_remove(mg, msp);
2683 
2684 	mutex_enter(&msp->ms_lock);
2685 	VERIFY(msp->ms_group == NULL);
2686 	metaslab_space_update(vd, mg->mg_class,
2687 	    -metaslab_allocated_space(msp), 0, -msp->ms_size);
2688 
2689 	space_map_close(msp->ms_sm);
2690 	msp->ms_sm = NULL;
2691 
2692 	metaslab_unload(msp);
2693 	range_tree_destroy(msp->ms_allocatable);
2694 	range_tree_destroy(msp->ms_freeing);
2695 	range_tree_destroy(msp->ms_freed);
2696 
2697 	ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=,
2698 	    metaslab_unflushed_changes_memused(msp));
2699 	spa->spa_unflushed_stats.sus_memused -=
2700 	    metaslab_unflushed_changes_memused(msp);
2701 	range_tree_vacate(msp->ms_unflushed_allocs, NULL, NULL);
2702 	range_tree_destroy(msp->ms_unflushed_allocs);
2703 	range_tree_vacate(msp->ms_unflushed_frees, NULL, NULL);
2704 	range_tree_destroy(msp->ms_unflushed_frees);
2705 
2706 	for (int t = 0; t < TXG_SIZE; t++) {
2707 		range_tree_destroy(msp->ms_allocating[t]);
2708 	}
2709 
2710 	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
2711 		range_tree_destroy(msp->ms_defer[t]);
2712 	}
2713 	ASSERT0(msp->ms_deferspace);
2714 
2715 	range_tree_destroy(msp->ms_checkpointing);
2716 
2717 	for (int t = 0; t < TXG_SIZE; t++)
2718 		ASSERT(!txg_list_member(&vd->vdev_ms_list, msp, t));
2719 
2720 	range_tree_vacate(msp->ms_trim, NULL, NULL);
2721 	range_tree_destroy(msp->ms_trim);
2722 
2723 	mutex_exit(&msp->ms_lock);
2724 	cv_destroy(&msp->ms_load_cv);
2725 	cv_destroy(&msp->ms_flush_cv);
2726 	mutex_destroy(&msp->ms_lock);
2727 	mutex_destroy(&msp->ms_sync_lock);
2728 	ASSERT3U(msp->ms_allocator, ==, -1);
2729 
2730 	kmem_free(msp, sizeof (metaslab_t));
2731 }
2732 
2733 #define	FRAGMENTATION_TABLE_SIZE	17
2734 
2735 /*
2736  * This table defines a segment size based fragmentation metric that will
2737  * allow each metaslab to derive its own fragmentation value. This is done
2738  * by calculating the space in each bucket of the spacemap histogram and
2739  * multiplying that by the fragmentation metric in this table. Doing
2740  * this for all buckets and dividing it by the total amount of free
2741  * space in this metaslab (i.e. the total free space in all buckets) gives
2742  * us the fragmentation metric. This means that a high fragmentation metric
2743  * equates to most of the free space being comprised of small segments.
2744  * Conversely, if the metric is low, then most of the free space is in
2745  * large segments. A 10% change in fragmentation equates to approximately
2746  * double the number of segments.
2747  *
2748  * This table defines 0% fragmented space using 16MB segments. Testing has
2749  * shown that segments that are greater than or equal to 16MB do not suffer
2750  * from drastic performance problems. Using this value, we derive the rest
2751  * of the table. Since the fragmentation value is never stored on disk, it
2752  * is possible to change these calculations in the future.
2753  */
2754 int zfs_frag_table[FRAGMENTATION_TABLE_SIZE] = {
2755 	100,	/* 512B	*/
2756 	100,	/* 1K	*/
2757 	98,	/* 2K	*/
2758 	95,	/* 4K	*/
2759 	90,	/* 8K	*/
2760 	80,	/* 16K	*/
2761 	70,	/* 32K	*/
2762 	60,	/* 64K	*/
2763 	50,	/* 128K	*/
2764 	40,	/* 256K	*/
2765 	30,	/* 512K	*/
2766 	20,	/* 1M	*/
2767 	15,	/* 2M	*/
2768 	10,	/* 4M	*/
2769 	5,	/* 8M	*/
2770 	0	/* 16M	*/
2771 };
2772 
2773 /*
2774  * Calculate the metaslab's fragmentation metric and set ms_fragmentation.
2775  * Setting this value to ZFS_FRAG_INVALID means that the metaslab has not
2776  * been upgraded and does not support this metric. Otherwise, the return
2777  * value should be in the range [0, 100].
2778  */
2779 static void
metaslab_set_fragmentation(metaslab_t * msp)2780 metaslab_set_fragmentation(metaslab_t *msp)
2781 {
2782 	spa_t *spa = msp->ms_group->mg_vd->vdev_spa;
2783 	uint64_t fragmentation = 0;
2784 	uint64_t total = 0;
2785 	boolean_t feature_enabled = spa_feature_is_enabled(spa,
2786 	    SPA_FEATURE_SPACEMAP_HISTOGRAM);
2787 
2788 	if (!feature_enabled) {
2789 		msp->ms_fragmentation = ZFS_FRAG_INVALID;
2790 		return;
2791 	}
2792 
2793 	/*
2794 	 * A null space map means that the entire metaslab is free
2795 	 * and thus is not fragmented.
2796 	 */
2797 	if (msp->ms_sm == NULL) {
2798 		msp->ms_fragmentation = 0;
2799 		return;
2800 	}
2801 
2802 	/*
2803 	 * If this metaslab's space map has not been upgraded, flag it
2804 	 * so that we upgrade next time we encounter it.
2805 	 */
2806 	if (msp->ms_sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) {
2807 		uint64_t txg = spa_syncing_txg(spa);
2808 		vdev_t *vd = msp->ms_group->mg_vd;
2809 
2810 		/*
2811 		 * If we've reached the final dirty txg, then we must
2812 		 * be shutting down the pool. We don't want to dirty
2813 		 * any data past this point so skip setting the condense
2814 		 * flag. We can retry this action the next time the pool
2815 		 * is imported.
2816 		 */
2817 		if (spa_writeable(spa) && txg < spa_final_dirty_txg(spa)) {
2818 			msp->ms_condense_wanted = B_TRUE;
2819 			vdev_dirty(vd, VDD_METASLAB, msp, txg + 1);
2820 			zfs_dbgmsg("txg %llu, requesting force condense: "
2821 			    "ms_id %llu, vdev_id %llu", txg, msp->ms_id,
2822 			    vd->vdev_id);
2823 		}
2824 		msp->ms_fragmentation = ZFS_FRAG_INVALID;
2825 		return;
2826 	}
2827 
2828 	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
2829 		uint64_t space = 0;
2830 		uint8_t shift = msp->ms_sm->sm_shift;
2831 
2832 		int idx = MIN(shift - SPA_MINBLOCKSHIFT + i,
2833 		    FRAGMENTATION_TABLE_SIZE - 1);
2834 
2835 		if (msp->ms_sm->sm_phys->smp_histogram[i] == 0)
2836 			continue;
2837 
2838 		space = msp->ms_sm->sm_phys->smp_histogram[i] << (i + shift);
2839 		total += space;
2840 
2841 		ASSERT3U(idx, <, FRAGMENTATION_TABLE_SIZE);
2842 		fragmentation += space * zfs_frag_table[idx];
2843 	}
2844 
2845 	if (total > 0)
2846 		fragmentation /= total;
2847 	ASSERT3U(fragmentation, <=, 100);
2848 
2849 	msp->ms_fragmentation = fragmentation;
2850 }
2851 
2852 /*
2853  * Compute a weight -- a selection preference value -- for the given metaslab.
2854  * This is based on the amount of free space, the level of fragmentation,
2855  * the LBA range, and whether the metaslab is loaded.
2856  */
2857 static uint64_t
metaslab_space_weight(metaslab_t * msp)2858 metaslab_space_weight(metaslab_t *msp)
2859 {
2860 	metaslab_group_t *mg = msp->ms_group;
2861 	vdev_t *vd = mg->mg_vd;
2862 	uint64_t weight, space;
2863 
2864 	ASSERT(MUTEX_HELD(&msp->ms_lock));
2865 
2866 	/*
2867 	 * The baseline weight is the metaslab's free space.
2868 	 */
2869 	space = msp->ms_size - metaslab_allocated_space(msp);
2870 
2871 	if (metaslab_fragmentation_factor_enabled &&
2872 	    msp->ms_fragmentation != ZFS_FRAG_INVALID) {
2873 		/*
2874 		 * Use the fragmentation information to inversely scale
2875 		 * down the baseline weight. We need to ensure that we
2876 		 * don't exclude this metaslab completely when it's 100%
2877 		 * fragmented. To avoid this we reduce the fragmented value
2878 		 * by 1.
2879 		 */
2880 		space = (space * (100 - (msp->ms_fragmentation - 1))) / 100;
2881 
2882 		/*
2883 		 * If space < SPA_MINBLOCKSIZE, then we will not allocate from
2884 		 * this metaslab again. The fragmentation metric may have
2885 		 * decreased the space to something smaller than
2886 		 * SPA_MINBLOCKSIZE, so reset the space to SPA_MINBLOCKSIZE
2887 		 * so that we can consume any remaining space.
2888 		 */
2889 		if (space > 0 && space < SPA_MINBLOCKSIZE)
2890 			space = SPA_MINBLOCKSIZE;
2891 	}
2892 	weight = space;
2893 
2894 	/*
2895 	 * Modern disks have uniform bit density and constant angular velocity.
2896 	 * Therefore, the outer recording zones are faster (higher bandwidth)
2897 	 * than the inner zones by the ratio of outer to inner track diameter,
2898 	 * which is typically around 2:1.  We account for this by assigning
2899 	 * higher weight to lower metaslabs (multiplier ranging from 2x to 1x).
2900 	 * In effect, this means that we'll select the metaslab with the most
2901 	 * free bandwidth rather than simply the one with the most free space.
2902 	 */
2903 	if (!vd->vdev_nonrot && metaslab_lba_weighting_enabled) {
2904 		weight = 2 * weight - (msp->ms_id * weight) / vd->vdev_ms_count;
2905 		ASSERT(weight >= space && weight <= 2 * space);
2906 	}
2907 
2908 	/*
2909 	 * If this metaslab is one we're actively using, adjust its
2910 	 * weight to make it preferable to any inactive metaslab so
2911 	 * we'll polish it off. If the fragmentation on this metaslab
2912 	 * has exceed our threshold, then don't mark it active.
2913 	 */
2914 	if (msp->ms_loaded && msp->ms_fragmentation != ZFS_FRAG_INVALID &&
2915 	    msp->ms_fragmentation <= zfs_metaslab_fragmentation_threshold) {
2916 		weight |= (msp->ms_weight & METASLAB_ACTIVE_MASK);
2917 	}
2918 
2919 	WEIGHT_SET_SPACEBASED(weight);
2920 	return (weight);
2921 }
2922 
2923 /*
2924  * Return the weight of the specified metaslab, according to the segment-based
2925  * weighting algorithm. The metaslab must be loaded. This function can
2926  * be called within a sync pass since it relies only on the metaslab's
2927  * range tree which is always accurate when the metaslab is loaded.
2928  */
2929 static uint64_t
metaslab_weight_from_range_tree(metaslab_t * msp)2930 metaslab_weight_from_range_tree(metaslab_t *msp)
2931 {
2932 	uint64_t weight = 0;
2933 	uint32_t segments = 0;
2934 
2935 	ASSERT(msp->ms_loaded);
2936 
2937 	for (int i = RANGE_TREE_HISTOGRAM_SIZE - 1; i >= SPA_MINBLOCKSHIFT;
2938 	    i--) {
2939 		uint8_t shift = msp->ms_group->mg_vd->vdev_ashift;
2940 		int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1;
2941 
2942 		segments <<= 1;
2943 		segments += msp->ms_allocatable->rt_histogram[i];
2944 
2945 		/*
2946 		 * The range tree provides more precision than the space map
2947 		 * and must be downgraded so that all values fit within the
2948 		 * space map's histogram. This allows us to compare loaded
2949 		 * vs. unloaded metaslabs to determine which metaslab is
2950 		 * considered "best".
2951 		 */
2952 		if (i > max_idx)
2953 			continue;
2954 
2955 		if (segments != 0) {
2956 			WEIGHT_SET_COUNT(weight, segments);
2957 			WEIGHT_SET_INDEX(weight, i);
2958 			WEIGHT_SET_ACTIVE(weight, 0);
2959 			break;
2960 		}
2961 	}
2962 	return (weight);
2963 }
2964 
2965 /*
2966  * Calculate the weight based on the on-disk histogram. Should be applied
2967  * only to unloaded metaslabs  (i.e no incoming allocations) in-order to
2968  * give results consistent with the on-disk state
2969  */
2970 static uint64_t
metaslab_weight_from_spacemap(metaslab_t * msp)2971 metaslab_weight_from_spacemap(metaslab_t *msp)
2972 {
2973 	space_map_t *sm = msp->ms_sm;
2974 	ASSERT(!msp->ms_loaded);
2975 	ASSERT(sm != NULL);
2976 	ASSERT3U(space_map_object(sm), !=, 0);
2977 	ASSERT3U(sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t));
2978 
2979 	/*
2980 	 * Create a joint histogram from all the segments that have made
2981 	 * it to the metaslab's space map histogram, that are not yet
2982 	 * available for allocation because they are still in the freeing
2983 	 * pipeline (e.g. freeing, freed, and defer trees). Then subtract
2984 	 * these segments from the space map's histogram to get a more
2985 	 * accurate weight.
2986 	 */
2987 	uint64_t deferspace_histogram[SPACE_MAP_HISTOGRAM_SIZE] = {0};
2988 	for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++)
2989 		deferspace_histogram[i] += msp->ms_synchist[i];
2990 	for (int t = 0; t < TXG_DEFER_SIZE; t++) {
2991 		for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) {
2992 			deferspace_histogram[i] += msp->ms_deferhist[t][i];
2993 		}
2994 	}
2995 
2996 	uint64_t weight = 0;
2997 	for (int i = SPACE_MAP_HISTOGRAM_SIZE - 1; i >= 0; i--) {
2998 		ASSERT3U(sm->sm_phys->smp_histogram[i], >=,
2999 		    deferspace_histogram[i]);
3000 		uint64_t count =
3001 		    sm->sm_phys->smp_histogram[i] - deferspace_histogram[i];
3002 		if (count != 0) {
3003 			WEIGHT_SET_COUNT(weight, count);
3004 			WEIGHT_SET_INDEX(weight, i + sm->sm_shift);
3005 			WEIGHT_SET_ACTIVE(weight, 0);
3006 			break;
3007 		}
3008 	}
3009 	return (weight);
3010 }
3011 
3012 /*
3013  * Compute a segment-based weight for the specified metaslab. The weight
3014  * is determined by highest bucket in the histogram. The information
3015  * for the highest bucket is encoded into the weight value.
3016  */
3017 static uint64_t
metaslab_segment_weight(metaslab_t * msp)3018 metaslab_segment_weight(metaslab_t *msp)
3019 {
3020 	metaslab_group_t *mg = msp->ms_group;
3021 	uint64_t weight = 0;
3022 	uint8_t shift = mg->mg_vd->vdev_ashift;
3023 
3024 	ASSERT(MUTEX_HELD(&msp->ms_lock));
3025 
3026 	/*
3027 	 * The metaslab is completely free.
3028 	 */
3029 	if (metaslab_allocated_space(msp) == 0) {
3030 		int idx = highbit64(msp->ms_size) - 1;
3031 		int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1;
3032 
3033 		if (idx < max_idx) {
3034 			WEIGHT_SET_COUNT(weight, 1ULL);
3035 			WEIGHT_SET_INDEX(weight, idx);
3036 		} else {
3037 			WEIGHT_SET_COUNT(weight, 1ULL << (idx - max_idx));
3038 			WEIGHT_SET_INDEX(weight, max_idx);
3039 		}
3040 		WEIGHT_SET_ACTIVE(weight, 0);
3041 		ASSERT(!WEIGHT_IS_SPACEBASED(weight));
3042 		return (weight);
3043 	}
3044 
3045 	ASSERT3U(msp->ms_sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t));
3046 
3047 	/*
3048 	 * If the metaslab is fully allocated then just make the weight 0.
3049 	 */
3050 	if (metaslab_allocated_space(msp) == msp->ms_size)
3051 		return (0);
3052 	/*
3053 	 * If the metaslab is already loaded, then use the range tree to
3054 	 * determine the weight. Otherwise, we rely on the space map information
3055 	 * to generate the weight.
3056 	 */
3057 	if (msp->ms_loaded) {
3058 		weight = metaslab_weight_from_range_tree(msp);
3059 	} else {
3060 		weight = metaslab_weight_from_spacemap(msp);
3061 	}
3062 
3063 	/*
3064 	 * If the metaslab was active the last time we calculated its weight
3065 	 * then keep it active. We want to consume the entire region that
3066 	 * is associated with this weight.
3067 	 */
3068 	if (msp->ms_activation_weight != 0 && weight != 0)
3069 		WEIGHT_SET_ACTIVE(weight, WEIGHT_GET_ACTIVE(msp->ms_weight));
3070 	return (weight);
3071 }
3072 
3073 /*
3074  * Determine if we should attempt to allocate from this metaslab. If the
3075  * metaslab is loaded, then we can determine if the desired allocation
3076  * can be satisfied by looking at the size of the maximum free segment
3077  * on that metaslab. Otherwise, we make our decision based on the metaslab's
3078  * weight. For segment-based weighting we can determine the maximum
3079  * allocation based on the index encoded in its value. For space-based
3080  * weights we rely on the entire weight (excluding the weight-type bit).
3081  */
3082 boolean_t
metaslab_should_allocate(metaslab_t * msp,uint64_t asize,boolean_t try_hard)3083 metaslab_should_allocate(metaslab_t *msp, uint64_t asize, boolean_t try_hard)
3084 {
3085 	/*
3086 	 * If the metaslab is loaded, ms_max_size is definitive and we can use
3087 	 * the fast check. If it's not, the ms_max_size is a lower bound (once
3088 	 * set), and we should use the fast check as long as we're not in
3089 	 * try_hard and it's been less than zfs_metaslab_max_size_cache_sec
3090 	 * seconds since the metaslab was unloaded.
3091 	 */
3092 	if (msp->ms_loaded ||
3093 	    (msp->ms_max_size != 0 && !try_hard && gethrtime() <
3094 	    msp->ms_unload_time + SEC2NSEC(zfs_metaslab_max_size_cache_sec)))
3095 		return (msp->ms_max_size >= asize);
3096 
3097 	boolean_t should_allocate;
3098 	if (!WEIGHT_IS_SPACEBASED(msp->ms_weight)) {
3099 		/*
3100 		 * The metaslab segment weight indicates segments in the
3101 		 * range [2^i, 2^(i+1)), where i is the index in the weight.
3102 		 * Since the asize might be in the middle of the range, we
3103 		 * should attempt the allocation if asize < 2^(i+1).
3104 		 */
3105 		should_allocate = (asize <
3106 		    1ULL << (WEIGHT_GET_INDEX(msp->ms_weight) + 1));
3107 	} else {
3108 		should_allocate = (asize <=
3109 		    (msp->ms_weight & ~METASLAB_WEIGHT_TYPE));
3110 	}
3111 
3112 	return (should_allocate);
3113 }
3114 
3115 static uint64_t
metaslab_weight(metaslab_t * msp)3116 metaslab_weight(metaslab_t *msp)
3117 {
3118 	vdev_t *vd = msp->ms_group->mg_vd;
3119 	spa_t *spa = vd->vdev_spa;
3120 	uint64_t weight;
3121 
3122 	ASSERT(MUTEX_HELD(&msp->ms_lock));
3123 
3124 	metaslab_set_fragmentation(msp);
3125 
3126 	/*
3127 	 * Update the maximum size. If the metaslab is loaded, this will
3128 	 * ensure that we get an accurate maximum size if newly freed space
3129 	 * has been added back into the free tree. If the metaslab is
3130 	 * unloaded, we check if there's a larger free segment in the
3131 	 * unflushed frees. This is a lower bound on the largest allocatable
3132 	 * segment size. Coalescing of adjacent entries may reveal larger
3133 	 * allocatable segments, but we aren't aware of those until loading
3134 	 * the space map into a range tree.
3135 	 */
3136 	if (msp->ms_loaded) {
3137 		msp->ms_max_size = metaslab_largest_allocatable(msp);
3138 	} else {
3139 		msp->ms_max_size = MAX(msp->ms_max_size,
3140 		    metaslab_largest_unflushed_free(msp));
3141 	}
3142 
3143 	/*
3144 	 * Segment-based weighting requires space map histogram support.
3145 	 */
3146 	if (zfs_metaslab_segment_weight_enabled &&
3147 	    spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM) &&
3148 	    (msp->ms_sm == NULL || msp->ms_sm->sm_dbuf->db_size ==
3149 	    sizeof (space_map_phys_t))) {
3150 		weight = metaslab_segment_weight(msp);
3151 	} else {
3152 		weight = metaslab_space_weight(msp);
3153 	}
3154 	return (weight);
3155 }
3156 
3157 void
metaslab_recalculate_weight_and_sort(metaslab_t * msp)3158 metaslab_recalculate_weight_and_sort(metaslab_t *msp)
3159 {
3160 	ASSERT(MUTEX_HELD(&msp->ms_lock));
3161 
3162 	/* note: we preserve the mask (e.g. indication of primary, etc..) */
3163 	uint64_t was_active = msp->ms_weight & METASLAB_ACTIVE_MASK;
3164 	metaslab_group_sort(msp->ms_group, msp,
3165 	    metaslab_weight(msp) | was_active);
3166 }
3167 
3168 static int
metaslab_activate_allocator(metaslab_group_t * mg,metaslab_t * msp,int allocator,uint64_t activation_weight)3169 metaslab_activate_allocator(metaslab_group_t *mg, metaslab_t *msp,
3170     int allocator, uint64_t activation_weight)
3171 {
3172 	ASSERT(MUTEX_HELD(&msp->ms_lock));
3173 
3174 	/*
3175 	 * If we're activating for the claim code, we don't want to actually
3176 	 * set the metaslab up for a specific allocator.
3177 	 */
3178 	if (activation_weight == METASLAB_WEIGHT_CLAIM) {
3179 		ASSERT0(msp->ms_activation_weight);
3180 		msp->ms_activation_weight = msp->ms_weight;
3181 		metaslab_group_sort(mg, msp, msp->ms_weight |
3182 		    activation_weight);
3183 		return (0);
3184 	}
3185 
3186 	metaslab_t **arr = (activation_weight == METASLAB_WEIGHT_PRIMARY ?
3187 	    mg->mg_primaries : mg->mg_secondaries);
3188 
3189 	mutex_enter(&mg->mg_lock);
3190 	if (arr[allocator] != NULL) {
3191 		mutex_exit(&mg->mg_lock);
3192 		return (EEXIST);
3193 	}
3194 
3195 	arr[allocator] = msp;
3196 	ASSERT3S(msp->ms_allocator, ==, -1);
3197 	msp->ms_allocator = allocator;
3198 	msp->ms_primary = (activation_weight == METASLAB_WEIGHT_PRIMARY);
3199 
3200 	ASSERT0(msp->ms_activation_weight);
3201 	msp->ms_activation_weight = msp->ms_weight;
3202 	metaslab_group_sort_impl(mg, msp,
3203 	    msp->ms_weight | activation_weight);
3204 
3205 	mutex_exit(&mg->mg_lock);
3206 
3207 	return (0);
3208 }
3209 
3210 static int
metaslab_activate(metaslab_t * msp,int allocator,uint64_t activation_weight)3211 metaslab_activate(metaslab_t *msp, int allocator, uint64_t activation_weight)
3212 {
3213 	ASSERT(MUTEX_HELD(&msp->ms_lock));
3214 
3215 	/*
3216 	 * The current metaslab is already activated for us so there
3217 	 * is nothing to do. Already activated though, doesn't mean
3218 	 * that this metaslab is activated for our allocator nor our
3219 	 * requested activation weight. The metaslab could have started
3220 	 * as an active one for our allocator but changed allocators
3221 	 * while we were waiting to grab its ms_lock or we stole it
3222 	 * [see find_valid_metaslab()]. This means that there is a
3223 	 * possibility of passivating a metaslab of another allocator
3224 	 * or from a different activation mask, from this thread.
3225 	 */
3226 	if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) {
3227 		ASSERT(msp->ms_loaded);
3228 		return (0);
3229 	}
3230 
3231 	int error = metaslab_load(msp);
3232 	if (error != 0) {
3233 		metaslab_group_sort(msp->ms_group, msp, 0);
3234 		return (error);
3235 	}
3236 
3237 	/*
3238 	 * When entering metaslab_load() we may have dropped the
3239 	 * ms_lock because we were loading this metaslab, or we
3240 	 * were waiting for another thread to load it for us. In
3241 	 * that scenario, we recheck the weight of the metaslab
3242 	 * to see if it was activated by another thread.
3243 	 *
3244 	 * If the metaslab was activated for another allocator or
3245 	 * it was activated with a different activation weight (e.g.
3246 	 * we wanted to make it a primary but it was activated as
3247 	 * secondary) we return error (EBUSY).
3248 	 *
3249 	 * If the metaslab was activated for the same allocator
3250 	 * and requested activation mask, skip activating it.
3251 	 */
3252 	if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) {
3253 		if (msp->ms_allocator != allocator)
3254 			return (EBUSY);
3255 
3256 		if ((msp->ms_weight & activation_weight) == 0)
3257 			return (EBUSY);
3258 
3259 		EQUIV((activation_weight == METASLAB_WEIGHT_PRIMARY),
3260 		    msp->ms_primary);
3261 		return (0);
3262 	}
3263 
3264 	/*
3265 	 * If the metaslab has literally 0 space, it will have weight 0. In
3266 	 * that case, don't bother activating it. This can happen if the
3267 	 * metaslab had space during find_valid_metaslab, but another thread
3268 	 * loaded it and used all that space while we were waiting to grab the
3269 	 * lock.
3270 	 */
3271 	if (msp->ms_weight == 0) {
3272 		ASSERT0(range_tree_space(msp->ms_allocatable));
3273 		return (SET_ERROR(ENOSPC));
3274 	}
3275 
3276 	if ((error = metaslab_activate_allocator(msp->ms_group, msp,
3277 	    allocator, activation_weight)) != 0) {
3278 		return (error);
3279 	}
3280 
3281 	ASSERT(msp->ms_loaded);
3282 	ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK);
3283 
3284 	return (0);
3285 }
3286 
3287 static void
metaslab_passivate_allocator(metaslab_group_t * mg,metaslab_t * msp,uint64_t weight)3288 metaslab_passivate_allocator(metaslab_group_t *mg, metaslab_t *msp,
3289     uint64_t weight)
3290 {
3291 	ASSERT(MUTEX_HELD(&msp->ms_lock));
3292 	ASSERT(msp->ms_loaded);
3293 
3294 	if (msp->ms_weight & METASLAB_WEIGHT_CLAIM) {
3295 		metaslab_group_sort(mg, msp, weight);
3296 		return;
3297 	}
3298 
3299 	mutex_enter(&mg->mg_lock);
3300 	ASSERT3P(msp->ms_group, ==, mg);
3301 	ASSERT3S(0, <=, msp->ms_allocator);
3302 	ASSERT3U(msp->ms_allocator, <, mg->mg_allocators);
3303 
3304 	if (msp->ms_primary) {
3305 		ASSERT3P(mg->mg_primaries[msp->ms_allocator], ==, msp);
3306 		ASSERT(msp->ms_weight & METASLAB_WEIGHT_PRIMARY);
3307 		mg->mg_primaries[msp->ms_allocator] = NULL;
3308 	} else {
3309 		ASSERT3P(mg->mg_secondaries[msp->ms_allocator], ==, msp);
3310 		ASSERT(msp->ms_weight & METASLAB_WEIGHT_SECONDARY);
3311 		mg->mg_secondaries[msp->ms_allocator] = NULL;
3312 	}
3313 	msp->ms_allocator = -1;
3314 	metaslab_group_sort_impl(mg, msp, weight);
3315 	mutex_exit(&mg->mg_lock);
3316 }
3317 
3318 static void
metaslab_passivate(metaslab_t * msp,uint64_t weight)3319 metaslab_passivate(metaslab_t *msp, uint64_t weight)
3320 {
3321 	uint64_t size = weight & ~METASLAB_WEIGHT_TYPE;
3322 
3323 	/*
3324 	 * If size < SPA_MINBLOCKSIZE, then we will not allocate from
3325 	 * this metaslab again.  In that case, it had better be empty,
3326 	 * or we would be leaving space on the table.
3327 	 */
3328 	ASSERT(size >= SPA_MINBLOCKSIZE ||
3329 	    range_tree_is_empty(msp->ms_allocatable));
3330 	ASSERT0(weight & METASLAB_ACTIVE_MASK);
3331 
3332 	ASSERT(msp->ms_activation_weight != 0);
3333 	msp->ms_activation_weight = 0;
3334 	metaslab_passivate_allocator(msp->ms_group, msp, weight);
3335 	ASSERT0(msp->ms_weight & METASLAB_ACTIVE_MASK);
3336 }
3337 
3338 /*
3339  * Segment-based metaslabs are activated once and remain active until
3340  * we either fail an allocation attempt (similar to space-based metaslabs)
3341  * or have exhausted the free space in zfs_metaslab_switch_threshold
3342  * buckets since the metaslab was activated. This function checks to see
3343  * if we've exhaused the zfs_metaslab_switch_threshold buckets in the
3344  * metaslab and passivates it proactively. This will allow us to select a
3345  * metaslabs with larger contiguous region if any remaining within this
3346  * metaslab group. If we're in sync pass > 1, then we continue using this
3347  * metaslab so that we don't dirty more block and cause more sync passes.
3348  */
3349 void
metaslab_segment_may_passivate(metaslab_t * msp)3350 metaslab_segment_may_passivate(metaslab_t *msp)
3351&