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, 2019 by Delphix. All rights reserved. 24 * Copyright (c) 2013 by Saso Kiselkov. All rights reserved. 25 * Copyright (c) 2015, Nexenta Systems, Inc. All rights reserved. 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/vdev_draid.h> 36 #include <sys/zio.h> 37 #include <sys/spa_impl.h> 38 #include <sys/zfeature.h> 39 #include <sys/vdev_indirect_mapping.h> 40 #include <sys/zap.h> 41 #include <sys/btree.h> 42 43 #define WITH_DF_BLOCK_ALLOCATOR 44 45 #define GANG_ALLOCATION(flags) \ 46 ((flags) & (METASLAB_GANG_CHILD | METASLAB_GANG_HEADER)) 47 48 /* 49 * Metaslab granularity, in bytes. This is roughly similar to what would be 50 * referred to as the "stripe size" in traditional RAID arrays. In normal 51 * operation, we will try to write this amount of data to a top-level vdev 52 * before moving on to the next one. 53 */ 54 unsigned long metaslab_aliquot = 512 << 10; 55 56 /* 57 * For testing, make some blocks above a certain size be gang blocks. 58 */ 59 unsigned long metaslab_force_ganging = SPA_MAXBLOCKSIZE + 1; 60 61 /* 62 * In pools where the log space map feature is not enabled we touch 63 * multiple metaslabs (and their respective space maps) with each 64 * transaction group. Thus, we benefit from having a small space map 65 * block size since it allows us to issue more I/O operations scattered 66 * around the disk. So a sane default for the space map block size 67 * is 8~16K. 68 */ 69 int zfs_metaslab_sm_blksz_no_log = (1 << 14); 70 71 /* 72 * When the log space map feature is enabled, we accumulate a lot of 73 * changes per metaslab that are flushed once in a while so we benefit 74 * from a bigger block size like 128K for the metaslab space maps. 75 */ 76 int zfs_metaslab_sm_blksz_with_log = (1 << 17); 77 78 /* 79 * The in-core space map representation is more compact than its on-disk form. 80 * The zfs_condense_pct determines how much more compact the in-core 81 * space map representation must be before we compact it on-disk. 82 * Values should be greater than or equal to 100. 83 */ 84 int zfs_condense_pct = 200; 85 86 /* 87 * Condensing a metaslab is not guaranteed to actually reduce the amount of 88 * space used on disk. In particular, a space map uses data in increments of 89 * MAX(1 << ashift, space_map_blksz), so a metaslab might use the 90 * same number of blocks after condensing. Since the goal of condensing is to 91 * reduce the number of IOPs required to read the space map, we only want to 92 * condense when we can be sure we will reduce the number of blocks used by the 93 * space map. Unfortunately, we cannot precisely compute whether or not this is 94 * the case in metaslab_should_condense since we are holding ms_lock. Instead, 95 * we apply the following heuristic: do not condense a spacemap unless the 96 * uncondensed size consumes greater than zfs_metaslab_condense_block_threshold 97 * blocks. 98 */ 99 int zfs_metaslab_condense_block_threshold = 4; 100 101 /* 102 * The zfs_mg_noalloc_threshold defines which metaslab groups should 103 * be eligible for allocation. The value is defined as a percentage of 104 * free space. Metaslab groups that have more free space than 105 * zfs_mg_noalloc_threshold are always eligible for allocations. Once 106 * a metaslab group's free space is less than or equal to the 107 * zfs_mg_noalloc_threshold the allocator will avoid allocating to that 108 * group unless all groups in the pool have reached zfs_mg_noalloc_threshold. 109 * Once all groups in the pool reach zfs_mg_noalloc_threshold then all 110 * groups are allowed to accept allocations. Gang blocks are always 111 * eligible to allocate on any metaslab group. The default value of 0 means 112 * no metaslab group will be excluded based on this criterion. 113 */ 114 int zfs_mg_noalloc_threshold = 0; 115 116 /* 117 * Metaslab groups are considered eligible for allocations if their 118 * fragmentation metric (measured as a percentage) is less than or 119 * equal to zfs_mg_fragmentation_threshold. If a metaslab group 120 * exceeds this threshold then it will be skipped unless all metaslab 121 * groups within the metaslab class have also crossed this threshold. 122 * 123 * This tunable was introduced to avoid edge cases where we continue 124 * allocating from very fragmented disks in our pool while other, less 125 * fragmented disks, exists. On the other hand, if all disks in the 126 * pool are uniformly approaching the threshold, the threshold can 127 * be a speed bump in performance, where we keep switching the disks 128 * that we allocate from (e.g. we allocate some segments from disk A 129 * making it bypassing the threshold while freeing segments from disk 130 * B getting its fragmentation below the threshold). 131 * 132 * Empirically, we've seen that our vdev selection for allocations is 133 * good enough that fragmentation increases uniformly across all vdevs 134 * the majority of the time. Thus we set the threshold percentage high 135 * enough to avoid hitting the speed bump on pools that are being pushed 136 * to the edge. 137 */ 138 int zfs_mg_fragmentation_threshold = 95; 139 140 /* 141 * Allow metaslabs to keep their active state as long as their fragmentation 142 * percentage is less than or equal to zfs_metaslab_fragmentation_threshold. An 143 * active metaslab that exceeds this threshold will no longer keep its active 144 * status allowing better metaslabs to be selected. 145 */ 146 int zfs_metaslab_fragmentation_threshold = 70; 147 148 /* 149 * When set will load all metaslabs when pool is first opened. 150 */ 151 int metaslab_debug_load = 0; 152 153 /* 154 * When set will prevent metaslabs from being unloaded. 155 */ 156 int metaslab_debug_unload = 0; 157 158 /* 159 * Minimum size which forces the dynamic allocator to change 160 * it's allocation strategy. Once the space map cannot satisfy 161 * an allocation of this size then it switches to using more 162 * aggressive strategy (i.e search by size rather than offset). 163 */ 164 uint64_t metaslab_df_alloc_threshold = SPA_OLD_MAXBLOCKSIZE; 165 166 /* 167 * The minimum free space, in percent, which must be available 168 * in a space map to continue allocations in a first-fit fashion. 169 * Once the space map's free space drops below this level we dynamically 170 * switch to using best-fit allocations. 171 */ 172 int metaslab_df_free_pct = 4; 173 174 /* 175 * Maximum distance to search forward from the last offset. Without this 176 * limit, fragmented pools can see >100,000 iterations and 177 * metaslab_block_picker() becomes the performance limiting factor on 178 * high-performance storage. 179 * 180 * With the default setting of 16MB, we typically see less than 500 181 * iterations, even with very fragmented, ashift=9 pools. The maximum number 182 * of iterations possible is: 183 * metaslab_df_max_search / (2 * (1<<ashift)) 184 * With the default setting of 16MB this is 16*1024 (with ashift=9) or 185 * 2048 (with ashift=12). 186 */ 187 int metaslab_df_max_search = 16 * 1024 * 1024; 188 189 /* 190 * Forces the metaslab_block_picker function to search for at least this many 191 * segments forwards until giving up on finding a segment that the allocation 192 * will fit into. 193 */ 194 uint32_t metaslab_min_search_count = 100; 195 196 /* 197 * If we are not searching forward (due to metaslab_df_max_search, 198 * metaslab_df_free_pct, or metaslab_df_alloc_threshold), this tunable 199 * controls what segment is used. If it is set, we will use the largest free 200 * segment. If it is not set, we will use a segment of exactly the requested 201 * size (or larger). 202 */ 203 int metaslab_df_use_largest_segment = B_FALSE; 204 205 /* 206 * Percentage of all cpus that can be used by the metaslab taskq. 207 */ 208 int metaslab_load_pct = 50; 209 210 /* 211 * These tunables control how long a metaslab will remain loaded after the 212 * last allocation from it. A metaslab can't be unloaded until at least 213 * metaslab_unload_delay TXG's and metaslab_unload_delay_ms milliseconds 214 * have elapsed. However, zfs_metaslab_mem_limit may cause it to be 215 * unloaded sooner. These settings are intended to be generous -- to keep 216 * metaslabs loaded for a long time, reducing the rate of metaslab loading. 217 */ 218 int metaslab_unload_delay = 32; 219 int metaslab_unload_delay_ms = 10 * 60 * 1000; /* ten minutes */ 220 221 /* 222 * Max number of metaslabs per group to preload. 223 */ 224 int metaslab_preload_limit = 10; 225 226 /* 227 * Enable/disable preloading of metaslab. 228 */ 229 int metaslab_preload_enabled = B_TRUE; 230 231 /* 232 * Enable/disable fragmentation weighting on metaslabs. 233 */ 234 int metaslab_fragmentation_factor_enabled = B_TRUE; 235 236 /* 237 * Enable/disable lba weighting (i.e. outer tracks are given preference). 238 */ 239 int metaslab_lba_weighting_enabled = B_TRUE; 240 241 /* 242 * Enable/disable metaslab group biasing. 243 */ 244 int metaslab_bias_enabled = B_TRUE; 245 246 /* 247 * Enable/disable remapping of indirect DVAs to their concrete vdevs. 248 */ 249 boolean_t zfs_remap_blkptr_enable = B_TRUE; 250 251 /* 252 * Enable/disable segment-based metaslab selection. 253 */ 254 int zfs_metaslab_segment_weight_enabled = B_TRUE; 255 256 /* 257 * When using segment-based metaslab selection, we will continue 258 * allocating from the active metaslab until we have exhausted 259 * zfs_metaslab_switch_threshold of its buckets. 260 */ 261 int zfs_metaslab_switch_threshold = 2; 262 263 /* 264 * Internal switch to enable/disable the metaslab allocation tracing 265 * facility. 266 */ 267 boolean_t metaslab_trace_enabled = B_FALSE; 268 269 /* 270 * Maximum entries that the metaslab allocation tracing facility will keep 271 * in a given list when running in non-debug mode. We limit the number 272 * of entries in non-debug mode to prevent us from using up too much memory. 273 * The limit should be sufficiently large that we don't expect any allocation 274 * to every exceed this value. In debug mode, the system will panic if this 275 * limit is ever reached allowing for further investigation. 276 */ 277 uint64_t metaslab_trace_max_entries = 5000; 278 279 /* 280 * Maximum number of metaslabs per group that can be disabled 281 * simultaneously. 282 */ 283 int max_disabled_ms = 3; 284 285 /* 286 * Time (in seconds) to respect ms_max_size when the metaslab is not loaded. 287 * To avoid 64-bit overflow, don't set above UINT32_MAX. 288 */ 289 unsigned long zfs_metaslab_max_size_cache_sec = 3600; /* 1 hour */ 290 291 /* 292 * Maximum percentage of memory to use on storing loaded metaslabs. If loading 293 * a metaslab would take it over this percentage, the oldest selected metaslab 294 * is automatically unloaded. 295 */ 296 int zfs_metaslab_mem_limit = 25; 297 298 /* 299 * Force the per-metaslab range trees to use 64-bit integers to store 300 * segments. Used for debugging purposes. 301 */ 302 boolean_t zfs_metaslab_force_large_segs = B_FALSE; 303 304 /* 305 * By default we only store segments over a certain size in the size-sorted 306 * metaslab trees (ms_allocatable_by_size and 307 * ms_unflushed_frees_by_size). This dramatically reduces memory usage and 308 * improves load and unload times at the cost of causing us to use slightly 309 * larger segments than we would otherwise in some cases. 310 */ 311 uint32_t metaslab_by_size_min_shift = 14; 312 313 /* 314 * If not set, we will first try normal allocation. If that fails then 315 * we will do a gang allocation. If that fails then we will do a "try hard" 316 * gang allocation. If that fails then we will have a multi-layer gang 317 * block. 318 * 319 * If set, we will first try normal allocation. If that fails then 320 * we will do a "try hard" allocation. If that fails we will do a gang 321 * allocation. If that fails we will do a "try hard" gang allocation. If 322 * that fails then we will have a multi-layer gang block. 323 */ 324 int zfs_metaslab_try_hard_before_gang = B_FALSE; 325 326 /* 327 * When not trying hard, we only consider the best zfs_metaslab_find_max_tries 328 * metaslabs. This improves performance, especially when there are many 329 * metaslabs per vdev and the allocation can't actually be satisfied (so we 330 * would otherwise iterate all the metaslabs). If there is a metaslab with a 331 * worse weight but it can actually satisfy the allocation, we won't find it 332 * until trying hard. This may happen if the worse metaslab is not loaded 333 * (and the true weight is better than we have calculated), or due to weight 334 * bucketization. E.g. we are looking for a 60K segment, and the best 335 * metaslabs all have free segments in the 32-63K bucket, but the best 336 * zfs_metaslab_find_max_tries metaslabs have ms_max_size <60KB, and a 337 * subsequent metaslab has ms_max_size >60KB (but fewer segments in this 338 * bucket, and therefore a lower weight). 339 */ 340 int zfs_metaslab_find_max_tries = 100; 341 342 static uint64_t metaslab_weight(metaslab_t *, boolean_t); 343 static void metaslab_set_fragmentation(metaslab_t *, boolean_t); 344 static void metaslab_free_impl(vdev_t *, uint64_t, uint64_t, boolean_t); 345 static void metaslab_check_free_impl(vdev_t *, uint64_t, uint64_t); 346 347 static void metaslab_passivate(metaslab_t *msp, uint64_t weight); 348 static uint64_t metaslab_weight_from_range_tree(metaslab_t *msp); 349 static void metaslab_flush_update(metaslab_t *, dmu_tx_t *); 350 static unsigned int metaslab_idx_func(multilist_t *, void *); 351 static void metaslab_evict(metaslab_t *, uint64_t); 352 static void metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg); 353 kmem_cache_t *metaslab_alloc_trace_cache; 354 355 typedef struct metaslab_stats { 356 kstat_named_t metaslabstat_trace_over_limit; 357 kstat_named_t metaslabstat_reload_tree; 358 kstat_named_t metaslabstat_too_many_tries; 359 kstat_named_t metaslabstat_try_hard; 360 } metaslab_stats_t; 361 362 static metaslab_stats_t metaslab_stats = { 363 { "trace_over_limit", KSTAT_DATA_UINT64 }, 364 { "reload_tree", KSTAT_DATA_UINT64 }, 365 { "too_many_tries", KSTAT_DATA_UINT64 }, 366 { "try_hard", KSTAT_DATA_UINT64 }, 367 }; 368 369 #define METASLABSTAT_BUMP(stat) \ 370 atomic_inc_64(&metaslab_stats.stat.value.ui64); 371 372 373 kstat_t *metaslab_ksp; 374 375 void 376 metaslab_stat_init(void) 377 { 378 ASSERT(metaslab_alloc_trace_cache == NULL); 379 metaslab_alloc_trace_cache = kmem_cache_create( 380 "metaslab_alloc_trace_cache", sizeof (metaslab_alloc_trace_t), 381 0, NULL, NULL, NULL, NULL, NULL, 0); 382 metaslab_ksp = kstat_create("zfs", 0, "metaslab_stats", 383 "misc", KSTAT_TYPE_NAMED, sizeof (metaslab_stats) / 384 sizeof (kstat_named_t), KSTAT_FLAG_VIRTUAL); 385 if (metaslab_ksp != NULL) { 386 metaslab_ksp->ks_data = &metaslab_stats; 387 kstat_install(metaslab_ksp); 388 } 389 } 390 391 void 392 metaslab_stat_fini(void) 393 { 394 if (metaslab_ksp != NULL) { 395 kstat_delete(metaslab_ksp); 396 metaslab_ksp = NULL; 397 } 398 399 kmem_cache_destroy(metaslab_alloc_trace_cache); 400 metaslab_alloc_trace_cache = NULL; 401 } 402 403 /* 404 * ========================================================================== 405 * Metaslab classes 406 * ========================================================================== 407 */ 408 metaslab_class_t * 409 metaslab_class_create(spa_t *spa, metaslab_ops_t *ops) 410 { 411 metaslab_class_t *mc; 412 413 mc = kmem_zalloc(offsetof(metaslab_class_t, 414 mc_allocator[spa->spa_alloc_count]), KM_SLEEP); 415 416 mc->mc_spa = spa; 417 mc->mc_ops = ops; 418 mutex_init(&mc->mc_lock, NULL, MUTEX_DEFAULT, NULL); 419 multilist_create(&mc->mc_metaslab_txg_list, sizeof (metaslab_t), 420 offsetof(metaslab_t, ms_class_txg_node), metaslab_idx_func); 421 for (int i = 0; i < spa->spa_alloc_count; i++) { 422 metaslab_class_allocator_t *mca = &mc->mc_allocator[i]; 423 mca->mca_rotor = NULL; 424 zfs_refcount_create_tracked(&mca->mca_alloc_slots); 425 } 426 427 return (mc); 428 } 429 430 void 431 metaslab_class_destroy(metaslab_class_t *mc) 432 { 433 spa_t *spa = mc->mc_spa; 434 435 ASSERT(mc->mc_alloc == 0); 436 ASSERT(mc->mc_deferred == 0); 437 ASSERT(mc->mc_space == 0); 438 ASSERT(mc->mc_dspace == 0); 439 440 for (int i = 0; i < spa->spa_alloc_count; i++) { 441 metaslab_class_allocator_t *mca = &mc->mc_allocator[i]; 442 ASSERT(mca->mca_rotor == NULL); 443 zfs_refcount_destroy(&mca->mca_alloc_slots); 444 } 445 mutex_destroy(&mc->mc_lock); 446 multilist_destroy(&mc->mc_metaslab_txg_list); 447 kmem_free(mc, offsetof(metaslab_class_t, 448 mc_allocator[spa->spa_alloc_count])); 449 } 450 451 int 452 metaslab_class_validate(metaslab_class_t *mc) 453 { 454 metaslab_group_t *mg; 455 vdev_t *vd; 456 457 /* 458 * Must hold one of the spa_config locks. 459 */ 460 ASSERT(spa_config_held(mc->mc_spa, SCL_ALL, RW_READER) || 461 spa_config_held(mc->mc_spa, SCL_ALL, RW_WRITER)); 462 463 if ((mg = mc->mc_allocator[0].mca_rotor) == NULL) 464 return (0); 465 466 do { 467 vd = mg->mg_vd; 468 ASSERT(vd->vdev_mg != NULL); 469 ASSERT3P(vd->vdev_top, ==, vd); 470 ASSERT3P(mg->mg_class, ==, mc); 471 ASSERT3P(vd->vdev_ops, !=, &vdev_hole_ops); 472 } while ((mg = mg->mg_next) != mc->mc_allocator[0].mca_rotor); 473 474 return (0); 475 } 476 477 static void 478 metaslab_class_space_update(metaslab_class_t *mc, int64_t alloc_delta, 479 int64_t defer_delta, int64_t space_delta, int64_t dspace_delta) 480 { 481 atomic_add_64(&mc->mc_alloc, alloc_delta); 482 atomic_add_64(&mc->mc_deferred, defer_delta); 483 atomic_add_64(&mc->mc_space, space_delta); 484 atomic_add_64(&mc->mc_dspace, dspace_delta); 485 } 486 487 uint64_t 488 metaslab_class_get_alloc(metaslab_class_t *mc) 489 { 490 return (mc->mc_alloc); 491 } 492 493 uint64_t 494 metaslab_class_get_deferred(metaslab_class_t *mc) 495 { 496 return (mc->mc_deferred); 497 } 498 499 uint64_t 500 metaslab_class_get_space(metaslab_class_t *mc) 501 { 502 return (mc->mc_space); 503 } 504 505 uint64_t 506 metaslab_class_get_dspace(metaslab_class_t *mc) 507 { 508 return (spa_deflate(mc->mc_spa) ? mc->mc_dspace : mc->mc_space); 509 } 510 511 void 512 metaslab_class_histogram_verify(metaslab_class_t *mc) 513 { 514 spa_t *spa = mc->mc_spa; 515 vdev_t *rvd = spa->spa_root_vdev; 516 uint64_t *mc_hist; 517 int i; 518 519 if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0) 520 return; 521 522 mc_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE, 523 KM_SLEEP); 524 525 mutex_enter(&mc->mc_lock); 526 for (int c = 0; c < rvd->vdev_children; c++) { 527 vdev_t *tvd = rvd->vdev_child[c]; 528 metaslab_group_t *mg = vdev_get_mg(tvd, mc); 529 530 /* 531 * Skip any holes, uninitialized top-levels, or 532 * vdevs that are not in this metalab class. 533 */ 534 if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 || 535 mg->mg_class != mc) { 536 continue; 537 } 538 539 IMPLY(mg == mg->mg_vd->vdev_log_mg, 540 mc == spa_embedded_log_class(mg->mg_vd->vdev_spa)); 541 542 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) 543 mc_hist[i] += mg->mg_histogram[i]; 544 } 545 546 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) { 547 VERIFY3U(mc_hist[i], ==, mc->mc_histogram[i]); 548 } 549 550 mutex_exit(&mc->mc_lock); 551 kmem_free(mc_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE); 552 } 553 554 /* 555 * Calculate the metaslab class's fragmentation metric. The metric 556 * is weighted based on the space contribution of each metaslab group. 557 * The return value will be a number between 0 and 100 (inclusive), or 558 * ZFS_FRAG_INVALID if the metric has not been set. See comment above the 559 * zfs_frag_table for more information about the metric. 560 */ 561 uint64_t 562 metaslab_class_fragmentation(metaslab_class_t *mc) 563 { 564 vdev_t *rvd = mc->mc_spa->spa_root_vdev; 565 uint64_t fragmentation = 0; 566 567 spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER); 568 569 for (int c = 0; c < rvd->vdev_children; c++) { 570 vdev_t *tvd = rvd->vdev_child[c]; 571 metaslab_group_t *mg = tvd->vdev_mg; 572 573 /* 574 * Skip any holes, uninitialized top-levels, 575 * or vdevs that are not in this metalab class. 576 */ 577 if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 || 578 mg->mg_class != mc) { 579 continue; 580 } 581 582 /* 583 * If a metaslab group does not contain a fragmentation 584 * metric then just bail out. 585 */ 586 if (mg->mg_fragmentation == ZFS_FRAG_INVALID) { 587 spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG); 588 return (ZFS_FRAG_INVALID); 589 } 590 591 /* 592 * Determine how much this metaslab_group is contributing 593 * to the overall pool fragmentation metric. 594 */ 595 fragmentation += mg->mg_fragmentation * 596 metaslab_group_get_space(mg); 597 } 598 fragmentation /= metaslab_class_get_space(mc); 599 600 ASSERT3U(fragmentation, <=, 100); 601 spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG); 602 return (fragmentation); 603 } 604 605 /* 606 * Calculate the amount of expandable space that is available in 607 * this metaslab class. If a device is expanded then its expandable 608 * space will be the amount of allocatable space that is currently not 609 * part of this metaslab class. 610 */ 611 uint64_t 612 metaslab_class_expandable_space(metaslab_class_t *mc) 613 { 614 vdev_t *rvd = mc->mc_spa->spa_root_vdev; 615 uint64_t space = 0; 616 617 spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER); 618 for (int c = 0; c < rvd->vdev_children; c++) { 619 vdev_t *tvd = rvd->vdev_child[c]; 620 metaslab_group_t *mg = tvd->vdev_mg; 621 622 if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 || 623 mg->mg_class != mc) { 624 continue; 625 } 626 627 /* 628 * Calculate if we have enough space to add additional 629 * metaslabs. We report the expandable space in terms 630 * of the metaslab size since that's the unit of expansion. 631 */ 632 space += P2ALIGN(tvd->vdev_max_asize - tvd->vdev_asize, 633 1ULL << tvd->vdev_ms_shift); 634 } 635 spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG); 636 return (space); 637 } 638 639 void 640 metaslab_class_evict_old(metaslab_class_t *mc, uint64_t txg) 641 { 642 multilist_t *ml = &mc->mc_metaslab_txg_list; 643 for (int i = 0; i < multilist_get_num_sublists(ml); i++) { 644 multilist_sublist_t *mls = multilist_sublist_lock(ml, i); 645 metaslab_t *msp = multilist_sublist_head(mls); 646 multilist_sublist_unlock(mls); 647 while (msp != NULL) { 648 mutex_enter(&msp->ms_lock); 649 650 /* 651 * If the metaslab has been removed from the list 652 * (which could happen if we were at the memory limit 653 * and it was evicted during this loop), then we can't 654 * proceed and we should restart the sublist. 655 */ 656 if (!multilist_link_active(&msp->ms_class_txg_node)) { 657 mutex_exit(&msp->ms_lock); 658 i--; 659 break; 660 } 661 mls = multilist_sublist_lock(ml, i); 662 metaslab_t *next_msp = multilist_sublist_next(mls, msp); 663 multilist_sublist_unlock(mls); 664 if (txg > 665 msp->ms_selected_txg + metaslab_unload_delay && 666 gethrtime() > msp->ms_selected_time + 667 (uint64_t)MSEC2NSEC(metaslab_unload_delay_ms)) { 668 metaslab_evict(msp, txg); 669 } else { 670 /* 671 * Once we've hit a metaslab selected too 672 * recently to evict, we're done evicting for 673 * now. 674 */ 675 mutex_exit(&msp->ms_lock); 676 break; 677 } 678 mutex_exit(&msp->ms_lock); 679 msp = next_msp; 680 } 681 } 682 } 683 684 static int 685 metaslab_compare(const void *x1, const void *x2) 686 { 687 const metaslab_t *m1 = (const metaslab_t *)x1; 688 const metaslab_t *m2 = (const metaslab_t *)x2; 689 690 int sort1 = 0; 691 int sort2 = 0; 692 if (m1->ms_allocator != -1 && m1->ms_primary) 693 sort1 = 1; 694 else if (m1->ms_allocator != -1 && !m1->ms_primary) 695 sort1 = 2; 696 if (m2->ms_allocator != -1 && m2->ms_primary) 697 sort2 = 1; 698 else if (m2->ms_allocator != -1 && !m2->ms_primary) 699 sort2 = 2; 700 701 /* 702 * Sort inactive metaslabs first, then primaries, then secondaries. When 703 * selecting a metaslab to allocate from, an allocator first tries its 704 * primary, then secondary active metaslab. If it doesn't have active 705 * metaslabs, or can't allocate from them, it searches for an inactive 706 * metaslab to activate. If it can't find a suitable one, it will steal 707 * a primary or secondary metaslab from another allocator. 708 */ 709 if (sort1 < sort2) 710 return (-1); 711 if (sort1 > sort2) 712 return (1); 713 714 int cmp = TREE_CMP(m2->ms_weight, m1->ms_weight); 715 if (likely(cmp)) 716 return (cmp); 717 718 IMPLY(TREE_CMP(m1->ms_start, m2->ms_start) == 0, m1 == m2); 719 720 return (TREE_CMP(m1->ms_start, m2->ms_start)); 721 } 722 723 /* 724 * ========================================================================== 725 * Metaslab groups 726 * ========================================================================== 727 */ 728 /* 729 * Update the allocatable flag and the metaslab group's capacity. 730 * The allocatable flag is set to true if the capacity is below 731 * the zfs_mg_noalloc_threshold or has a fragmentation value that is 732 * greater than zfs_mg_fragmentation_threshold. If a metaslab group 733 * transitions from allocatable to non-allocatable or vice versa then the 734 * metaslab group's class is updated to reflect the transition. 735 */ 736 static void 737 metaslab_group_alloc_update(metaslab_group_t *mg) 738 { 739 vdev_t *vd = mg->mg_vd; 740 metaslab_class_t *mc = mg->mg_class; 741 vdev_stat_t *vs = &vd->vdev_stat; 742 boolean_t was_allocatable; 743 boolean_t was_initialized; 744 745 ASSERT(vd == vd->vdev_top); 746 ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_READER), ==, 747 SCL_ALLOC); 748 749 mutex_enter(&mg->mg_lock); 750 was_allocatable = mg->mg_allocatable; 751 was_initialized = mg->mg_initialized; 752 753 mg->mg_free_capacity = ((vs->vs_space - vs->vs_alloc) * 100) / 754 (vs->vs_space + 1); 755 756 mutex_enter(&mc->mc_lock); 757 758 /* 759 * If the metaslab group was just added then it won't 760 * have any space until we finish syncing out this txg. 761 * At that point we will consider it initialized and available 762 * for allocations. We also don't consider non-activated 763 * metaslab groups (e.g. vdevs that are in the middle of being removed) 764 * to be initialized, because they can't be used for allocation. 765 */ 766 mg->mg_initialized = metaslab_group_initialized(mg); 767 if (!was_initialized && mg->mg_initialized) { 768 mc->mc_groups++; 769 } else if (was_initialized && !mg->mg_initialized) { 770 ASSERT3U(mc->mc_groups, >, 0); 771 mc->mc_groups--; 772 } 773 if (mg->mg_initialized) 774 mg->mg_no_free_space = B_FALSE; 775 776 /* 777 * A metaslab group is considered allocatable if it has plenty 778 * of free space or is not heavily fragmented. We only take 779 * fragmentation into account if the metaslab group has a valid 780 * fragmentation metric (i.e. a value between 0 and 100). 781 */ 782 mg->mg_allocatable = (mg->mg_activation_count > 0 && 783 mg->mg_free_capacity > zfs_mg_noalloc_threshold && 784 (mg->mg_fragmentation == ZFS_FRAG_INVALID || 785 mg->mg_fragmentation <= zfs_mg_fragmentation_threshold)); 786 787 /* 788 * The mc_alloc_groups maintains a count of the number of 789 * groups in this metaslab class that are still above the 790 * zfs_mg_noalloc_threshold. This is used by the allocating 791 * threads to determine if they should avoid allocations to 792 * a given group. The allocator will avoid allocations to a group 793 * if that group has reached or is below the zfs_mg_noalloc_threshold 794 * and there are still other groups that are above the threshold. 795 * When a group transitions from allocatable to non-allocatable or 796 * vice versa we update the metaslab class to reflect that change. 797 * When the mc_alloc_groups value drops to 0 that means that all 798 * groups have reached the zfs_mg_noalloc_threshold making all groups 799 * eligible for allocations. This effectively means that all devices 800 * are balanced again. 801 */ 802 if (was_allocatable && !mg->mg_allocatable) 803 mc->mc_alloc_groups--; 804 else if (!was_allocatable && mg->mg_allocatable) 805 mc->mc_alloc_groups++; 806 mutex_exit(&mc->mc_lock); 807 808 mutex_exit(&mg->mg_lock); 809 } 810 811 int 812 metaslab_sort_by_flushed(const void *va, const void *vb) 813 { 814 const metaslab_t *a = va; 815 const metaslab_t *b = vb; 816 817 int cmp = TREE_CMP(a->ms_unflushed_txg, b->ms_unflushed_txg); 818 if (likely(cmp)) 819 return (cmp); 820 821 uint64_t a_vdev_id = a->ms_group->mg_vd->vdev_id; 822 uint64_t b_vdev_id = b->ms_group->mg_vd->vdev_id; 823 cmp = TREE_CMP(a_vdev_id, b_vdev_id); 824 if (cmp) 825 return (cmp); 826 827 return (TREE_CMP(a->ms_id, b->ms_id)); 828 } 829 830 metaslab_group_t * 831 metaslab_group_create(metaslab_class_t *mc, vdev_t *vd, int allocators) 832 { 833 metaslab_group_t *mg; 834 835 mg = kmem_zalloc(offsetof(metaslab_group_t, 836 mg_allocator[allocators]), KM_SLEEP); 837 mutex_init(&mg->mg_lock, NULL, MUTEX_DEFAULT, NULL); 838 mutex_init(&mg->mg_ms_disabled_lock, NULL, MUTEX_DEFAULT, NULL); 839 cv_init(&mg->mg_ms_disabled_cv, NULL, CV_DEFAULT, NULL); 840 avl_create(&mg->mg_metaslab_tree, metaslab_compare, 841 sizeof (metaslab_t), offsetof(metaslab_t, ms_group_node)); 842 mg->mg_vd = vd; 843 mg->mg_class = mc; 844 mg->mg_activation_count = 0; 845 mg->mg_initialized = B_FALSE; 846 mg->mg_no_free_space = B_TRUE; 847 mg->mg_allocators = allocators; 848 849 for (int i = 0; i < allocators; i++) { 850 metaslab_group_allocator_t *mga = &mg->mg_allocator[i]; 851 zfs_refcount_create_tracked(&mga->mga_alloc_queue_depth); 852 } 853 854 mg->mg_taskq = taskq_create("metaslab_group_taskq", metaslab_load_pct, 855 maxclsyspri, 10, INT_MAX, TASKQ_THREADS_CPU_PCT | TASKQ_DYNAMIC); 856 857 return (mg); 858 } 859 860 void 861 metaslab_group_destroy(metaslab_group_t *mg) 862 { 863 ASSERT(mg->mg_prev == NULL); 864 ASSERT(mg->mg_next == NULL); 865 /* 866 * We may have gone below zero with the activation count 867 * either because we never activated in the first place or 868 * because we're done, and possibly removing the vdev. 869 */ 870 ASSERT(mg->mg_activation_count <= 0); 871 872 taskq_destroy(mg->mg_taskq); 873 avl_destroy(&mg->mg_metaslab_tree); 874 mutex_destroy(&mg->mg_lock); 875 mutex_destroy(&mg->mg_ms_disabled_lock); 876 cv_destroy(&mg->mg_ms_disabled_cv); 877 878 for (int i = 0; i < mg->mg_allocators; i++) { 879 metaslab_group_allocator_t *mga = &mg->mg_allocator[i]; 880 zfs_refcount_destroy(&mga->mga_alloc_queue_depth); 881 } 882 kmem_free(mg, offsetof(metaslab_group_t, 883 mg_allocator[mg->mg_allocators])); 884 } 885 886 void 887 metaslab_group_activate(metaslab_group_t *mg) 888 { 889 metaslab_class_t *mc = mg->mg_class; 890 spa_t *spa = mc->mc_spa; 891 metaslab_group_t *mgprev, *mgnext; 892 893 ASSERT3U(spa_config_held(spa, SCL_ALLOC, RW_WRITER), !=, 0); 894 895 ASSERT(mg->mg_prev == NULL); 896 ASSERT(mg->mg_next == NULL); 897 ASSERT(mg->mg_activation_count <= 0); 898 899 if (++mg->mg_activation_count <= 0) 900 return; 901 902 mg->mg_aliquot = metaslab_aliquot * MAX(1, mg->mg_vd->vdev_children); 903 metaslab_group_alloc_update(mg); 904 905 if ((mgprev = mc->mc_allocator[0].mca_rotor) == NULL) { 906 mg->mg_prev = mg; 907 mg->mg_next = mg; 908 } else { 909 mgnext = mgprev->mg_next; 910 mg->mg_prev = mgprev; 911 mg->mg_next = mgnext; 912 mgprev->mg_next = mg; 913 mgnext->mg_prev = mg; 914 } 915 for (int i = 0; i < spa->spa_alloc_count; i++) { 916 mc->mc_allocator[i].mca_rotor = mg; 917 mg = mg->mg_next; 918 } 919 } 920 921 /* 922 * Passivate a metaslab group and remove it from the allocation rotor. 923 * Callers must hold both the SCL_ALLOC and SCL_ZIO lock prior to passivating 924 * a metaslab group. This function will momentarily drop spa_config_locks 925 * that are lower than the SCL_ALLOC lock (see comment below). 926 */ 927 void 928 metaslab_group_passivate(metaslab_group_t *mg) 929 { 930 metaslab_class_t *mc = mg->mg_class; 931 spa_t *spa = mc->mc_spa; 932 metaslab_group_t *mgprev, *mgnext; 933 int locks = spa_config_held(spa, SCL_ALL, RW_WRITER); 934 935 ASSERT3U(spa_config_held(spa, SCL_ALLOC | SCL_ZIO, RW_WRITER), ==, 936 (SCL_ALLOC | SCL_ZIO)); 937 938 if (--mg->mg_activation_count != 0) { 939 for (int i = 0; i < spa->spa_alloc_count; i++) 940 ASSERT(mc->mc_allocator[i].mca_rotor != mg); 941 ASSERT(mg->mg_prev == NULL); 942 ASSERT(mg->mg_next == NULL); 943 ASSERT(mg->mg_activation_count < 0); 944 return; 945 } 946 947 /* 948 * The spa_config_lock is an array of rwlocks, ordered as 949 * follows (from highest to lowest): 950 * SCL_CONFIG > SCL_STATE > SCL_L2ARC > SCL_ALLOC > 951 * SCL_ZIO > SCL_FREE > SCL_VDEV 952 * (For more information about the spa_config_lock see spa_misc.c) 953 * The higher the lock, the broader its coverage. When we passivate 954 * a metaslab group, we must hold both the SCL_ALLOC and the SCL_ZIO 955 * config locks. However, the metaslab group's taskq might be trying 956 * to preload metaslabs so we must drop the SCL_ZIO lock and any 957 * lower locks to allow the I/O to complete. At a minimum, 958 * we continue to hold the SCL_ALLOC lock, which prevents any future 959 * allocations from taking place and any changes to the vdev tree. 960 */ 961 spa_config_exit(spa, locks & ~(SCL_ZIO - 1), spa); 962 taskq_wait_outstanding(mg->mg_taskq, 0); 963 spa_config_enter(spa, locks & ~(SCL_ZIO - 1), spa, RW_WRITER); 964 metaslab_group_alloc_update(mg); 965 for (int i = 0; i < mg->mg_allocators; i++) { 966 metaslab_group_allocator_t *mga = &mg->mg_allocator[i]; 967 metaslab_t *msp = mga->mga_primary; 968 if (msp != NULL) { 969 mutex_enter(&msp->ms_lock); 970 metaslab_passivate(msp, 971 metaslab_weight_from_range_tree(msp)); 972 mutex_exit(&msp->ms_lock); 973 } 974 msp = mga->mga_secondary; 975 if (msp != NULL) { 976 mutex_enter(&msp->ms_lock); 977 metaslab_passivate(msp, 978 metaslab_weight_from_range_tree(msp)); 979 mutex_exit(&msp->ms_lock); 980 } 981 } 982 983 mgprev = mg->mg_prev; 984 mgnext = mg->mg_next; 985 986 if (mg == mgnext) { 987 mgnext = NULL; 988 } else { 989 mgprev->mg_next = mgnext; 990 mgnext->mg_prev = mgprev; 991 } 992 for (int i = 0; i < spa->spa_alloc_count; i++) { 993 if (mc->mc_allocator[i].mca_rotor == mg) 994 mc->mc_allocator[i].mca_rotor = mgnext; 995 } 996 997 mg->mg_prev = NULL; 998 mg->mg_next = NULL; 999 } 1000 1001 boolean_t 1002 metaslab_group_initialized(metaslab_group_t *mg) 1003 { 1004 vdev_t *vd = mg->mg_vd; 1005 vdev_stat_t *vs = &vd->vdev_stat; 1006 1007 return (vs->vs_space != 0 && mg->mg_activation_count > 0); 1008 } 1009 1010 uint64_t 1011 metaslab_group_get_space(metaslab_group_t *mg) 1012 { 1013 /* 1014 * Note that the number of nodes in mg_metaslab_tree may be one less 1015 * than vdev_ms_count, due to the embedded log metaslab. 1016 */ 1017 mutex_enter(&mg->mg_lock); 1018 uint64_t ms_count = avl_numnodes(&mg->mg_metaslab_tree); 1019 mutex_exit(&mg->mg_lock); 1020 return ((1ULL << mg->mg_vd->vdev_ms_shift) * ms_count); 1021 } 1022 1023 void 1024 metaslab_group_histogram_verify(metaslab_group_t *mg) 1025 { 1026 uint64_t *mg_hist; 1027 avl_tree_t *t = &mg->mg_metaslab_tree; 1028 uint64_t ashift = mg->mg_vd->vdev_ashift; 1029 1030 if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0) 1031 return; 1032 1033 mg_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE, 1034 KM_SLEEP); 1035 1036 ASSERT3U(RANGE_TREE_HISTOGRAM_SIZE, >=, 1037 SPACE_MAP_HISTOGRAM_SIZE + ashift); 1038 1039 mutex_enter(&mg->mg_lock); 1040 for (metaslab_t *msp = avl_first(t); 1041 msp != NULL; msp = AVL_NEXT(t, msp)) { 1042 VERIFY3P(msp->ms_group, ==, mg); 1043 /* skip if not active */ 1044 if (msp->ms_sm == NULL) 1045 continue; 1046 1047 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 1048 mg_hist[i + ashift] += 1049 msp->ms_sm->sm_phys->smp_histogram[i]; 1050 } 1051 } 1052 1053 for (int i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i ++) 1054 VERIFY3U(mg_hist[i], ==, mg->mg_histogram[i]); 1055 1056 mutex_exit(&mg->mg_lock); 1057 1058 kmem_free(mg_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE); 1059 } 1060 1061 static void 1062 metaslab_group_histogram_add(metaslab_group_t *mg, metaslab_t *msp) 1063 { 1064 metaslab_class_t *mc = mg->mg_class; 1065 uint64_t ashift = mg->mg_vd->vdev_ashift; 1066 1067 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1068 if (msp->ms_sm == NULL) 1069 return; 1070 1071 mutex_enter(&mg->mg_lock); 1072 mutex_enter(&mc->mc_lock); 1073 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 1074 IMPLY(mg == mg->mg_vd->vdev_log_mg, 1075 mc == spa_embedded_log_class(mg->mg_vd->vdev_spa)); 1076 mg->mg_histogram[i + ashift] += 1077 msp->ms_sm->sm_phys->smp_histogram[i]; 1078 mc->mc_histogram[i + ashift] += 1079 msp->ms_sm->sm_phys->smp_histogram[i]; 1080 } 1081 mutex_exit(&mc->mc_lock); 1082 mutex_exit(&mg->mg_lock); 1083 } 1084 1085 void 1086 metaslab_group_histogram_remove(metaslab_group_t *mg, metaslab_t *msp) 1087 { 1088 metaslab_class_t *mc = mg->mg_class; 1089 uint64_t ashift = mg->mg_vd->vdev_ashift; 1090 1091 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1092 if (msp->ms_sm == NULL) 1093 return; 1094 1095 mutex_enter(&mg->mg_lock); 1096 mutex_enter(&mc->mc_lock); 1097 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 1098 ASSERT3U(mg->mg_histogram[i + ashift], >=, 1099 msp->ms_sm->sm_phys->smp_histogram[i]); 1100 ASSERT3U(mc->mc_histogram[i + ashift], >=, 1101 msp->ms_sm->sm_phys->smp_histogram[i]); 1102 IMPLY(mg == mg->mg_vd->vdev_log_mg, 1103 mc == spa_embedded_log_class(mg->mg_vd->vdev_spa)); 1104 1105 mg->mg_histogram[i + ashift] -= 1106 msp->ms_sm->sm_phys->smp_histogram[i]; 1107 mc->mc_histogram[i + ashift] -= 1108 msp->ms_sm->sm_phys->smp_histogram[i]; 1109 } 1110 mutex_exit(&mc->mc_lock); 1111 mutex_exit(&mg->mg_lock); 1112 } 1113 1114 static void 1115 metaslab_group_add(metaslab_group_t *mg, metaslab_t *msp) 1116 { 1117 ASSERT(msp->ms_group == NULL); 1118 mutex_enter(&mg->mg_lock); 1119 msp->ms_group = mg; 1120 msp->ms_weight = 0; 1121 avl_add(&mg->mg_metaslab_tree, msp); 1122 mutex_exit(&mg->mg_lock); 1123 1124 mutex_enter(&msp->ms_lock); 1125 metaslab_group_histogram_add(mg, msp); 1126 mutex_exit(&msp->ms_lock); 1127 } 1128 1129 static void 1130 metaslab_group_remove(metaslab_group_t *mg, metaslab_t *msp) 1131 { 1132 mutex_enter(&msp->ms_lock); 1133 metaslab_group_histogram_remove(mg, msp); 1134 mutex_exit(&msp->ms_lock); 1135 1136 mutex_enter(&mg->mg_lock); 1137 ASSERT(msp->ms_group == mg); 1138 avl_remove(&mg->mg_metaslab_tree, msp); 1139 1140 metaslab_class_t *mc = msp->ms_group->mg_class; 1141 multilist_sublist_t *mls = 1142 multilist_sublist_lock_obj(&mc->mc_metaslab_txg_list, msp); 1143 if (multilist_link_active(&msp->ms_class_txg_node)) 1144 multilist_sublist_remove(mls, msp); 1145 multilist_sublist_unlock(mls); 1146 1147 msp->ms_group = NULL; 1148 mutex_exit(&mg->mg_lock); 1149 } 1150 1151 static void 1152 metaslab_group_sort_impl(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight) 1153 { 1154 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1155 ASSERT(MUTEX_HELD(&mg->mg_lock)); 1156 ASSERT(msp->ms_group == mg); 1157 1158 avl_remove(&mg->mg_metaslab_tree, msp); 1159 msp->ms_weight = weight; 1160 avl_add(&mg->mg_metaslab_tree, msp); 1161 1162 } 1163 1164 static void 1165 metaslab_group_sort(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight) 1166 { 1167 /* 1168 * Although in principle the weight can be any value, in 1169 * practice we do not use values in the range [1, 511]. 1170 */ 1171 ASSERT(weight >= SPA_MINBLOCKSIZE || weight == 0); 1172 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1173 1174 mutex_enter(&mg->mg_lock); 1175 metaslab_group_sort_impl(mg, msp, weight); 1176 mutex_exit(&mg->mg_lock); 1177 } 1178 1179 /* 1180 * Calculate the fragmentation for a given metaslab group. We can use 1181 * a simple average here since all metaslabs within the group must have 1182 * the same size. The return value will be a value between 0 and 100 1183 * (inclusive), or ZFS_FRAG_INVALID if less than half of the metaslab in this 1184 * group have a fragmentation metric. 1185 */ 1186 uint64_t 1187 metaslab_group_fragmentation(metaslab_group_t *mg) 1188 { 1189 vdev_t *vd = mg->mg_vd; 1190 uint64_t fragmentation = 0; 1191 uint64_t valid_ms = 0; 1192 1193 for (int m = 0; m < vd->vdev_ms_count; m++) { 1194 metaslab_t *msp = vd->vdev_ms[m]; 1195 1196 if (msp->ms_fragmentation == ZFS_FRAG_INVALID) 1197 continue; 1198 if (msp->ms_group != mg) 1199 continue; 1200 1201 valid_ms++; 1202 fragmentation += msp->ms_fragmentation; 1203 } 1204 1205 if (valid_ms <= mg->mg_vd->vdev_ms_count / 2) 1206 return (ZFS_FRAG_INVALID); 1207 1208 fragmentation /= valid_ms; 1209 ASSERT3U(fragmentation, <=, 100); 1210 return (fragmentation); 1211 } 1212 1213 /* 1214 * Determine if a given metaslab group should skip allocations. A metaslab 1215 * group should avoid allocations if its free capacity is less than the 1216 * zfs_mg_noalloc_threshold or its fragmentation metric is greater than 1217 * zfs_mg_fragmentation_threshold and there is at least one metaslab group 1218 * that can still handle allocations. If the allocation throttle is enabled 1219 * then we skip allocations to devices that have reached their maximum 1220 * allocation queue depth unless the selected metaslab group is the only 1221 * eligible group remaining. 1222 */ 1223 static boolean_t 1224 metaslab_group_allocatable(metaslab_group_t *mg, metaslab_group_t *rotor, 1225 uint64_t psize, int allocator, int d) 1226 { 1227 spa_t *spa = mg->mg_vd->vdev_spa; 1228 metaslab_class_t *mc = mg->mg_class; 1229 1230 /* 1231 * We can only consider skipping this metaslab group if it's 1232 * in the normal metaslab class and there are other metaslab 1233 * groups to select from. Otherwise, we always consider it eligible 1234 * for allocations. 1235 */ 1236 if ((mc != spa_normal_class(spa) && 1237 mc != spa_special_class(spa) && 1238 mc != spa_dedup_class(spa)) || 1239 mc->mc_groups <= 1) 1240 return (B_TRUE); 1241 1242 /* 1243 * If the metaslab group's mg_allocatable flag is set (see comments 1244 * in metaslab_group_alloc_update() for more information) and 1245 * the allocation throttle is disabled then allow allocations to this 1246 * device. However, if the allocation throttle is enabled then 1247 * check if we have reached our allocation limit (mga_alloc_queue_depth) 1248 * to determine if we should allow allocations to this metaslab group. 1249 * If all metaslab groups are no longer considered allocatable 1250 * (mc_alloc_groups == 0) or we're trying to allocate the smallest 1251 * gang block size then we allow allocations on this metaslab group 1252 * regardless of the mg_allocatable or throttle settings. 1253 */ 1254 if (mg->mg_allocatable) { 1255 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 1256 int64_t qdepth; 1257 uint64_t qmax = mga->mga_cur_max_alloc_queue_depth; 1258 1259 if (!mc->mc_alloc_throttle_enabled) 1260 return (B_TRUE); 1261 1262 /* 1263 * If this metaslab group does not have any free space, then 1264 * there is no point in looking further. 1265 */ 1266 if (mg->mg_no_free_space) 1267 return (B_FALSE); 1268 1269 /* 1270 * Relax allocation throttling for ditto blocks. Due to 1271 * random imbalances in allocation it tends to push copies 1272 * to one vdev, that looks a bit better at the moment. 1273 */ 1274 qmax = qmax * (4 + d) / 4; 1275 1276 qdepth = zfs_refcount_count(&mga->mga_alloc_queue_depth); 1277 1278 /* 1279 * If this metaslab group is below its qmax or it's 1280 * the only allocatable metasable group, then attempt 1281 * to allocate from it. 1282 */ 1283 if (qdepth < qmax || mc->mc_alloc_groups == 1) 1284 return (B_TRUE); 1285 ASSERT3U(mc->mc_alloc_groups, >, 1); 1286 1287 /* 1288 * Since this metaslab group is at or over its qmax, we 1289 * need to determine if there are metaslab groups after this 1290 * one that might be able to handle this allocation. This is 1291 * racy since we can't hold the locks for all metaslab 1292 * groups at the same time when we make this check. 1293 */ 1294 for (metaslab_group_t *mgp = mg->mg_next; 1295 mgp != rotor; mgp = mgp->mg_next) { 1296 metaslab_group_allocator_t *mgap = 1297 &mgp->mg_allocator[allocator]; 1298 qmax = mgap->mga_cur_max_alloc_queue_depth; 1299 qmax = qmax * (4 + d) / 4; 1300 qdepth = 1301 zfs_refcount_count(&mgap->mga_alloc_queue_depth); 1302 1303 /* 1304 * If there is another metaslab group that 1305 * might be able to handle the allocation, then 1306 * we return false so that we skip this group. 1307 */ 1308 if (qdepth < qmax && !mgp->mg_no_free_space) 1309 return (B_FALSE); 1310 } 1311 1312 /* 1313 * We didn't find another group to handle the allocation 1314 * so we can't skip this metaslab group even though 1315 * we are at or over our qmax. 1316 */ 1317 return (B_TRUE); 1318 1319 } else if (mc->mc_alloc_groups == 0 || psize == SPA_MINBLOCKSIZE) { 1320 return (B_TRUE); 1321 } 1322 return (B_FALSE); 1323 } 1324 1325 /* 1326 * ========================================================================== 1327 * Range tree callbacks 1328 * ========================================================================== 1329 */ 1330 1331 /* 1332 * Comparison function for the private size-ordered tree using 32-bit 1333 * ranges. Tree is sorted by size, larger sizes at the end of the tree. 1334 */ 1335 static int 1336 metaslab_rangesize32_compare(const void *x1, const void *x2) 1337 { 1338 const range_seg32_t *r1 = x1; 1339 const range_seg32_t *r2 = x2; 1340 1341 uint64_t rs_size1 = r1->rs_end - r1->rs_start; 1342 uint64_t rs_size2 = r2->rs_end - r2->rs_start; 1343 1344 int cmp = TREE_CMP(rs_size1, rs_size2); 1345 if (likely(cmp)) 1346 return (cmp); 1347 1348 return (TREE_CMP(r1->rs_start, r2->rs_start)); 1349 } 1350 1351 /* 1352 * Comparison function for the private size-ordered tree using 64-bit 1353 * ranges. Tree is sorted by size, larger sizes at the end of the tree. 1354 */ 1355 static int 1356 metaslab_rangesize64_compare(const void *x1, const void *x2) 1357 { 1358 const range_seg64_t *r1 = x1; 1359 const range_seg64_t *r2 = x2; 1360 1361 uint64_t rs_size1 = r1->rs_end - r1->rs_start; 1362 uint64_t rs_size2 = r2->rs_end - r2->rs_start; 1363 1364 int cmp = TREE_CMP(rs_size1, rs_size2); 1365 if (likely(cmp)) 1366 return (cmp); 1367 1368 return (TREE_CMP(r1->rs_start, r2->rs_start)); 1369 } 1370 typedef struct metaslab_rt_arg { 1371 zfs_btree_t *mra_bt; 1372 uint32_t mra_floor_shift; 1373 } metaslab_rt_arg_t; 1374 1375 struct mssa_arg { 1376 range_tree_t *rt; 1377 metaslab_rt_arg_t *mra; 1378 }; 1379 1380 static void 1381 metaslab_size_sorted_add(void *arg, uint64_t start, uint64_t size) 1382 { 1383 struct mssa_arg *mssap = arg; 1384 range_tree_t *rt = mssap->rt; 1385 metaslab_rt_arg_t *mrap = mssap->mra; 1386 range_seg_max_t seg = {0}; 1387 rs_set_start(&seg, rt, start); 1388 rs_set_end(&seg, rt, start + size); 1389 metaslab_rt_add(rt, &seg, mrap); 1390 } 1391 1392 static void 1393 metaslab_size_tree_full_load(range_tree_t *rt) 1394 { 1395 metaslab_rt_arg_t *mrap = rt->rt_arg; 1396 METASLABSTAT_BUMP(metaslabstat_reload_tree); 1397 ASSERT0(zfs_btree_numnodes(mrap->mra_bt)); 1398 mrap->mra_floor_shift = 0; 1399 struct mssa_arg arg = {0}; 1400 arg.rt = rt; 1401 arg.mra = mrap; 1402 range_tree_walk(rt, metaslab_size_sorted_add, &arg); 1403 } 1404 1405 /* 1406 * Create any block allocator specific components. The current allocators 1407 * rely on using both a size-ordered range_tree_t and an array of uint64_t's. 1408 */ 1409 /* ARGSUSED */ 1410 static void 1411 metaslab_rt_create(range_tree_t *rt, void *arg) 1412 { 1413 metaslab_rt_arg_t *mrap = arg; 1414 zfs_btree_t *size_tree = mrap->mra_bt; 1415 1416 size_t size; 1417 int (*compare) (const void *, const void *); 1418 switch (rt->rt_type) { 1419 case RANGE_SEG32: 1420 size = sizeof (range_seg32_t); 1421 compare = metaslab_rangesize32_compare; 1422 break; 1423 case RANGE_SEG64: 1424 size = sizeof (range_seg64_t); 1425 compare = metaslab_rangesize64_compare; 1426 break; 1427 default: 1428 panic("Invalid range seg type %d", rt->rt_type); 1429 } 1430 zfs_btree_create(size_tree, compare, size); 1431 mrap->mra_floor_shift = metaslab_by_size_min_shift; 1432 } 1433 1434 /* ARGSUSED */ 1435 static void 1436 metaslab_rt_destroy(range_tree_t *rt, void *arg) 1437 { 1438 metaslab_rt_arg_t *mrap = arg; 1439 zfs_btree_t *size_tree = mrap->mra_bt; 1440 1441 zfs_btree_destroy(size_tree); 1442 kmem_free(mrap, sizeof (*mrap)); 1443 } 1444 1445 /* ARGSUSED */ 1446 static void 1447 metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg) 1448 { 1449 metaslab_rt_arg_t *mrap = arg; 1450 zfs_btree_t *size_tree = mrap->mra_bt; 1451 1452 if (rs_get_end(rs, rt) - rs_get_start(rs, rt) < 1453 (1 << mrap->mra_floor_shift)) 1454 return; 1455 1456 zfs_btree_add(size_tree, rs); 1457 } 1458 1459 /* ARGSUSED */ 1460 static void 1461 metaslab_rt_remove(range_tree_t *rt, range_seg_t *rs, void *arg) 1462 { 1463 metaslab_rt_arg_t *mrap = arg; 1464 zfs_btree_t *size_tree = mrap->mra_bt; 1465 1466 if (rs_get_end(rs, rt) - rs_get_start(rs, rt) < (1 << 1467 mrap->mra_floor_shift)) 1468 return; 1469 1470 zfs_btree_remove(size_tree, rs); 1471 } 1472 1473 /* ARGSUSED */ 1474 static void 1475 metaslab_rt_vacate(range_tree_t *rt, void *arg) 1476 { 1477 metaslab_rt_arg_t *mrap = arg; 1478 zfs_btree_t *size_tree = mrap->mra_bt; 1479 zfs_btree_clear(size_tree); 1480 zfs_btree_destroy(size_tree); 1481 1482 metaslab_rt_create(rt, arg); 1483 } 1484 1485 static range_tree_ops_t metaslab_rt_ops = { 1486 .rtop_create = metaslab_rt_create, 1487 .rtop_destroy = metaslab_rt_destroy, 1488 .rtop_add = metaslab_rt_add, 1489 .rtop_remove = metaslab_rt_remove, 1490 .rtop_vacate = metaslab_rt_vacate 1491 }; 1492 1493 /* 1494 * ========================================================================== 1495 * Common allocator routines 1496 * ========================================================================== 1497 */ 1498 1499 /* 1500 * Return the maximum contiguous segment within the metaslab. 1501 */ 1502 uint64_t 1503 metaslab_largest_allocatable(metaslab_t *msp) 1504 { 1505 zfs_btree_t *t = &msp->ms_allocatable_by_size; 1506 range_seg_t *rs; 1507 1508 if (t == NULL) 1509 return (0); 1510 if (zfs_btree_numnodes(t) == 0) 1511 metaslab_size_tree_full_load(msp->ms_allocatable); 1512 1513 rs = zfs_btree_last(t, NULL); 1514 if (rs == NULL) 1515 return (0); 1516 1517 return (rs_get_end(rs, msp->ms_allocatable) - rs_get_start(rs, 1518 msp->ms_allocatable)); 1519 } 1520 1521 /* 1522 * Return the maximum contiguous segment within the unflushed frees of this 1523 * metaslab. 1524 */ 1525 static uint64_t 1526 metaslab_largest_unflushed_free(metaslab_t *msp) 1527 { 1528 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1529 1530 if (msp->ms_unflushed_frees == NULL) 1531 return (0); 1532 1533 if (zfs_btree_numnodes(&msp->ms_unflushed_frees_by_size) == 0) 1534 metaslab_size_tree_full_load(msp->ms_unflushed_frees); 1535 range_seg_t *rs = zfs_btree_last(&msp->ms_unflushed_frees_by_size, 1536 NULL); 1537 if (rs == NULL) 1538 return (0); 1539 1540 /* 1541 * When a range is freed from the metaslab, that range is added to 1542 * both the unflushed frees and the deferred frees. While the block 1543 * will eventually be usable, if the metaslab were loaded the range 1544 * would not be added to the ms_allocatable tree until TXG_DEFER_SIZE 1545 * txgs had passed. As a result, when attempting to estimate an upper 1546 * bound for the largest currently-usable free segment in the 1547 * metaslab, we need to not consider any ranges currently in the defer 1548 * trees. This algorithm approximates the largest available chunk in 1549 * the largest range in the unflushed_frees tree by taking the first 1550 * chunk. While this may be a poor estimate, it should only remain so 1551 * briefly and should eventually self-correct as frees are no longer 1552 * deferred. Similar logic applies to the ms_freed tree. See 1553 * metaslab_load() for more details. 1554 * 1555 * There are two primary sources of inaccuracy in this estimate. Both 1556 * are tolerated for performance reasons. The first source is that we 1557 * only check the largest segment for overlaps. Smaller segments may 1558 * have more favorable overlaps with the other trees, resulting in 1559 * larger usable chunks. Second, we only look at the first chunk in 1560 * the largest segment; there may be other usable chunks in the 1561 * largest segment, but we ignore them. 1562 */ 1563 uint64_t rstart = rs_get_start(rs, msp->ms_unflushed_frees); 1564 uint64_t rsize = rs_get_end(rs, msp->ms_unflushed_frees) - rstart; 1565 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 1566 uint64_t start = 0; 1567 uint64_t size = 0; 1568 boolean_t found = range_tree_find_in(msp->ms_defer[t], rstart, 1569 rsize, &start, &size); 1570 if (found) { 1571 if (rstart == start) 1572 return (0); 1573 rsize = start - rstart; 1574 } 1575 } 1576 1577 uint64_t start = 0; 1578 uint64_t size = 0; 1579 boolean_t found = range_tree_find_in(msp->ms_freed, rstart, 1580 rsize, &start, &size); 1581 if (found) 1582 rsize = start - rstart; 1583 1584 return (rsize); 1585 } 1586 1587 static range_seg_t * 1588 metaslab_block_find(zfs_btree_t *t, range_tree_t *rt, uint64_t start, 1589 uint64_t size, zfs_btree_index_t *where) 1590 { 1591 range_seg_t *rs; 1592 range_seg_max_t rsearch; 1593 1594 rs_set_start(&rsearch, rt, start); 1595 rs_set_end(&rsearch, rt, start + size); 1596 1597 rs = zfs_btree_find(t, &rsearch, where); 1598 if (rs == NULL) { 1599 rs = zfs_btree_next(t, where, where); 1600 } 1601 1602 return (rs); 1603 } 1604 1605 #if defined(WITH_DF_BLOCK_ALLOCATOR) || \ 1606 defined(WITH_CF_BLOCK_ALLOCATOR) 1607 1608 /* 1609 * This is a helper function that can be used by the allocator to find a 1610 * suitable block to allocate. This will search the specified B-tree looking 1611 * for a block that matches the specified criteria. 1612 */ 1613 static uint64_t 1614 metaslab_block_picker(range_tree_t *rt, uint64_t *cursor, uint64_t size, 1615 uint64_t max_search) 1616 { 1617 if (*cursor == 0) 1618 *cursor = rt->rt_start; 1619 zfs_btree_t *bt = &rt->rt_root; 1620 zfs_btree_index_t where; 1621 range_seg_t *rs = metaslab_block_find(bt, rt, *cursor, size, &where); 1622 uint64_t first_found; 1623 int count_searched = 0; 1624 1625 if (rs != NULL) 1626 first_found = rs_get_start(rs, rt); 1627 1628 while (rs != NULL && (rs_get_start(rs, rt) - first_found <= 1629 max_search || count_searched < metaslab_min_search_count)) { 1630 uint64_t offset = rs_get_start(rs, rt); 1631 if (offset + size <= rs_get_end(rs, rt)) { 1632 *cursor = offset + size; 1633 return (offset); 1634 } 1635 rs = zfs_btree_next(bt, &where, &where); 1636 count_searched++; 1637 } 1638 1639 *cursor = 0; 1640 return (-1ULL); 1641 } 1642 #endif /* WITH_DF/CF_BLOCK_ALLOCATOR */ 1643 1644 #if defined(WITH_DF_BLOCK_ALLOCATOR) 1645 /* 1646 * ========================================================================== 1647 * Dynamic Fit (df) block allocator 1648 * 1649 * Search for a free chunk of at least this size, starting from the last 1650 * offset (for this alignment of block) looking for up to 1651 * metaslab_df_max_search bytes (16MB). If a large enough free chunk is not 1652 * found within 16MB, then return a free chunk of exactly the requested size (or 1653 * larger). 1654 * 1655 * If it seems like searching from the last offset will be unproductive, skip 1656 * that and just return a free chunk of exactly the requested size (or larger). 1657 * This is based on metaslab_df_alloc_threshold and metaslab_df_free_pct. This 1658 * mechanism is probably not very useful and may be removed in the future. 1659 * 1660 * The behavior when not searching can be changed to return the largest free 1661 * chunk, instead of a free chunk of exactly the requested size, by setting 1662 * metaslab_df_use_largest_segment. 1663 * ========================================================================== 1664 */ 1665 static uint64_t 1666 metaslab_df_alloc(metaslab_t *msp, uint64_t size) 1667 { 1668 /* 1669 * Find the largest power of 2 block size that evenly divides the 1670 * requested size. This is used to try to allocate blocks with similar 1671 * alignment from the same area of the metaslab (i.e. same cursor 1672 * bucket) but it does not guarantee that other allocations sizes 1673 * may exist in the same region. 1674 */ 1675 uint64_t align = size & -size; 1676 uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1]; 1677 range_tree_t *rt = msp->ms_allocatable; 1678 int free_pct = range_tree_space(rt) * 100 / msp->ms_size; 1679 uint64_t offset; 1680 1681 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1682 1683 /* 1684 * If we're running low on space, find a segment based on size, 1685 * rather than iterating based on offset. 1686 */ 1687 if (metaslab_largest_allocatable(msp) < metaslab_df_alloc_threshold || 1688 free_pct < metaslab_df_free_pct) { 1689 offset = -1; 1690 } else { 1691 offset = metaslab_block_picker(rt, 1692 cursor, size, metaslab_df_max_search); 1693 } 1694 1695 if (offset == -1) { 1696 range_seg_t *rs; 1697 if (zfs_btree_numnodes(&msp->ms_allocatable_by_size) == 0) 1698 metaslab_size_tree_full_load(msp->ms_allocatable); 1699 1700 if (metaslab_df_use_largest_segment) { 1701 /* use largest free segment */ 1702 rs = zfs_btree_last(&msp->ms_allocatable_by_size, NULL); 1703 } else { 1704 zfs_btree_index_t where; 1705 /* use segment of this size, or next largest */ 1706 rs = metaslab_block_find(&msp->ms_allocatable_by_size, 1707 rt, msp->ms_start, size, &where); 1708 } 1709 if (rs != NULL && rs_get_start(rs, rt) + size <= rs_get_end(rs, 1710 rt)) { 1711 offset = rs_get_start(rs, rt); 1712 *cursor = offset + size; 1713 } 1714 } 1715 1716 return (offset); 1717 } 1718 1719 static metaslab_ops_t metaslab_df_ops = { 1720 metaslab_df_alloc 1721 }; 1722 1723 metaslab_ops_t *zfs_metaslab_ops = &metaslab_df_ops; 1724 #endif /* WITH_DF_BLOCK_ALLOCATOR */ 1725 1726 #if defined(WITH_CF_BLOCK_ALLOCATOR) 1727 /* 1728 * ========================================================================== 1729 * Cursor fit block allocator - 1730 * Select the largest region in the metaslab, set the cursor to the beginning 1731 * of the range and the cursor_end to the end of the range. As allocations 1732 * are made advance the cursor. Continue allocating from the cursor until 1733 * the range is exhausted and then find a new range. 1734 * ========================================================================== 1735 */ 1736 static uint64_t 1737 metaslab_cf_alloc(metaslab_t *msp, uint64_t size) 1738 { 1739 range_tree_t *rt = msp->ms_allocatable; 1740 zfs_btree_t *t = &msp->ms_allocatable_by_size; 1741 uint64_t *cursor = &msp->ms_lbas[0]; 1742 uint64_t *cursor_end = &msp->ms_lbas[1]; 1743 uint64_t offset = 0; 1744 1745 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1746 1747 ASSERT3U(*cursor_end, >=, *cursor); 1748 1749 if ((*cursor + size) > *cursor_end) { 1750 range_seg_t *rs; 1751 1752 if (zfs_btree_numnodes(t) == 0) 1753 metaslab_size_tree_full_load(msp->ms_allocatable); 1754 rs = zfs_btree_last(t, NULL); 1755 if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) < 1756 size) 1757 return (-1ULL); 1758 1759 *cursor = rs_get_start(rs, rt); 1760 *cursor_end = rs_get_end(rs, rt); 1761 } 1762 1763 offset = *cursor; 1764 *cursor += size; 1765 1766 return (offset); 1767 } 1768 1769 static metaslab_ops_t metaslab_cf_ops = { 1770 metaslab_cf_alloc 1771 }; 1772 1773 metaslab_ops_t *zfs_metaslab_ops = &metaslab_cf_ops; 1774 #endif /* WITH_CF_BLOCK_ALLOCATOR */ 1775 1776 #if defined(WITH_NDF_BLOCK_ALLOCATOR) 1777 /* 1778 * ========================================================================== 1779 * New dynamic fit allocator - 1780 * Select a region that is large enough to allocate 2^metaslab_ndf_clump_shift 1781 * contiguous blocks. If no region is found then just use the largest segment 1782 * that remains. 1783 * ========================================================================== 1784 */ 1785 1786 /* 1787 * Determines desired number of contiguous blocks (2^metaslab_ndf_clump_shift) 1788 * to request from the allocator. 1789 */ 1790 uint64_t metaslab_ndf_clump_shift = 4; 1791 1792 static uint64_t 1793 metaslab_ndf_alloc(metaslab_t *msp, uint64_t size) 1794 { 1795 zfs_btree_t *t = &msp->ms_allocatable->rt_root; 1796 range_tree_t *rt = msp->ms_allocatable; 1797 zfs_btree_index_t where; 1798 range_seg_t *rs; 1799 range_seg_max_t rsearch; 1800 uint64_t hbit = highbit64(size); 1801 uint64_t *cursor = &msp->ms_lbas[hbit - 1]; 1802 uint64_t max_size = metaslab_largest_allocatable(msp); 1803 1804 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1805 1806 if (max_size < size) 1807 return (-1ULL); 1808 1809 rs_set_start(&rsearch, rt, *cursor); 1810 rs_set_end(&rsearch, rt, *cursor + size); 1811 1812 rs = zfs_btree_find(t, &rsearch, &where); 1813 if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) < size) { 1814 t = &msp->ms_allocatable_by_size; 1815 1816 rs_set_start(&rsearch, rt, 0); 1817 rs_set_end(&rsearch, rt, MIN(max_size, 1ULL << (hbit + 1818 metaslab_ndf_clump_shift))); 1819 1820 rs = zfs_btree_find(t, &rsearch, &where); 1821 if (rs == NULL) 1822 rs = zfs_btree_next(t, &where, &where); 1823 ASSERT(rs != NULL); 1824 } 1825 1826 if ((rs_get_end(rs, rt) - rs_get_start(rs, rt)) >= size) { 1827 *cursor = rs_get_start(rs, rt) + size; 1828 return (rs_get_start(rs, rt)); 1829 } 1830 return (-1ULL); 1831 } 1832 1833 static metaslab_ops_t metaslab_ndf_ops = { 1834 metaslab_ndf_alloc 1835 }; 1836 1837 metaslab_ops_t *zfs_metaslab_ops = &metaslab_ndf_ops; 1838 #endif /* WITH_NDF_BLOCK_ALLOCATOR */ 1839 1840 1841 /* 1842 * ========================================================================== 1843 * Metaslabs 1844 * ========================================================================== 1845 */ 1846 1847 /* 1848 * Wait for any in-progress metaslab loads to complete. 1849 */ 1850 static void 1851 metaslab_load_wait(metaslab_t *msp) 1852 { 1853 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1854 1855 while (msp->ms_loading) { 1856 ASSERT(!msp->ms_loaded); 1857 cv_wait(&msp->ms_load_cv, &msp->ms_lock); 1858 } 1859 } 1860 1861 /* 1862 * Wait for any in-progress flushing to complete. 1863 */ 1864 static void 1865 metaslab_flush_wait(metaslab_t *msp) 1866 { 1867 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1868 1869 while (msp->ms_flushing) 1870 cv_wait(&msp->ms_flush_cv, &msp->ms_lock); 1871 } 1872 1873 static unsigned int 1874 metaslab_idx_func(multilist_t *ml, void *arg) 1875 { 1876 metaslab_t *msp = arg; 1877 1878 /* 1879 * ms_id values are allocated sequentially, so full 64bit 1880 * division would be a waste of time, so limit it to 32 bits. 1881 */ 1882 return ((unsigned int)msp->ms_id % multilist_get_num_sublists(ml)); 1883 } 1884 1885 uint64_t 1886 metaslab_allocated_space(metaslab_t *msp) 1887 { 1888 return (msp->ms_allocated_space); 1889 } 1890 1891 /* 1892 * Verify that the space accounting on disk matches the in-core range_trees. 1893 */ 1894 static void 1895 metaslab_verify_space(metaslab_t *msp, uint64_t txg) 1896 { 1897 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 1898 uint64_t allocating = 0; 1899 uint64_t sm_free_space, msp_free_space; 1900 1901 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1902 ASSERT(!msp->ms_condensing); 1903 1904 if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0) 1905 return; 1906 1907 /* 1908 * We can only verify the metaslab space when we're called 1909 * from syncing context with a loaded metaslab that has an 1910 * allocated space map. Calling this in non-syncing context 1911 * does not provide a consistent view of the metaslab since 1912 * we're performing allocations in the future. 1913 */ 1914 if (txg != spa_syncing_txg(spa) || msp->ms_sm == NULL || 1915 !msp->ms_loaded) 1916 return; 1917 1918 /* 1919 * Even though the smp_alloc field can get negative, 1920 * when it comes to a metaslab's space map, that should 1921 * never be the case. 1922 */ 1923 ASSERT3S(space_map_allocated(msp->ms_sm), >=, 0); 1924 1925 ASSERT3U(space_map_allocated(msp->ms_sm), >=, 1926 range_tree_space(msp->ms_unflushed_frees)); 1927 1928 ASSERT3U(metaslab_allocated_space(msp), ==, 1929 space_map_allocated(msp->ms_sm) + 1930 range_tree_space(msp->ms_unflushed_allocs) - 1931 range_tree_space(msp->ms_unflushed_frees)); 1932 1933 sm_free_space = msp->ms_size - metaslab_allocated_space(msp); 1934 1935 /* 1936 * Account for future allocations since we would have 1937 * already deducted that space from the ms_allocatable. 1938 */ 1939 for (int t = 0; t < TXG_CONCURRENT_STATES; t++) { 1940 allocating += 1941 range_tree_space(msp->ms_allocating[(txg + t) & TXG_MASK]); 1942 } 1943 ASSERT3U(allocating + msp->ms_allocated_this_txg, ==, 1944 msp->ms_allocating_total); 1945 1946 ASSERT3U(msp->ms_deferspace, ==, 1947 range_tree_space(msp->ms_defer[0]) + 1948 range_tree_space(msp->ms_defer[1])); 1949 1950 msp_free_space = range_tree_space(msp->ms_allocatable) + allocating + 1951 msp->ms_deferspace + range_tree_space(msp->ms_freed); 1952 1953 VERIFY3U(sm_free_space, ==, msp_free_space); 1954 } 1955 1956 static void 1957 metaslab_aux_histograms_clear(metaslab_t *msp) 1958 { 1959 /* 1960 * Auxiliary histograms are only cleared when resetting them, 1961 * which can only happen while the metaslab is loaded. 1962 */ 1963 ASSERT(msp->ms_loaded); 1964 1965 bzero(msp->ms_synchist, sizeof (msp->ms_synchist)); 1966 for (int t = 0; t < TXG_DEFER_SIZE; t++) 1967 bzero(msp->ms_deferhist[t], sizeof (msp->ms_deferhist[t])); 1968 } 1969 1970 static void 1971 metaslab_aux_histogram_add(uint64_t *histogram, uint64_t shift, 1972 range_tree_t *rt) 1973 { 1974 /* 1975 * This is modeled after space_map_histogram_add(), so refer to that 1976 * function for implementation details. We want this to work like 1977 * the space map histogram, and not the range tree histogram, as we 1978 * are essentially constructing a delta that will be later subtracted 1979 * from the space map histogram. 1980 */ 1981 int idx = 0; 1982 for (int i = shift; i < RANGE_TREE_HISTOGRAM_SIZE; i++) { 1983 ASSERT3U(i, >=, idx + shift); 1984 histogram[idx] += rt->rt_histogram[i] << (i - idx - shift); 1985 1986 if (idx < SPACE_MAP_HISTOGRAM_SIZE - 1) { 1987 ASSERT3U(idx + shift, ==, i); 1988 idx++; 1989 ASSERT3U(idx, <, SPACE_MAP_HISTOGRAM_SIZE); 1990 } 1991 } 1992 } 1993 1994 /* 1995 * Called at every sync pass that the metaslab gets synced. 1996 * 1997 * The reason is that we want our auxiliary histograms to be updated 1998 * wherever the metaslab's space map histogram is updated. This way 1999 * we stay consistent on which parts of the metaslab space map's 2000 * histogram are currently not available for allocations (e.g because 2001 * they are in the defer, freed, and freeing trees). 2002 */ 2003 static void 2004 metaslab_aux_histograms_update(metaslab_t *msp) 2005 { 2006 space_map_t *sm = msp->ms_sm; 2007 ASSERT(sm != NULL); 2008 2009 /* 2010 * This is similar to the metaslab's space map histogram updates 2011 * that take place in metaslab_sync(). The only difference is that 2012 * we only care about segments that haven't made it into the 2013 * ms_allocatable tree yet. 2014 */ 2015 if (msp->ms_loaded) { 2016 metaslab_aux_histograms_clear(msp); 2017 2018 metaslab_aux_histogram_add(msp->ms_synchist, 2019 sm->sm_shift, msp->ms_freed); 2020 2021 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2022 metaslab_aux_histogram_add(msp->ms_deferhist[t], 2023 sm->sm_shift, msp->ms_defer[t]); 2024 } 2025 } 2026 2027 metaslab_aux_histogram_add(msp->ms_synchist, 2028 sm->sm_shift, msp->ms_freeing); 2029 } 2030 2031 /* 2032 * Called every time we are done syncing (writing to) the metaslab, 2033 * i.e. at the end of each sync pass. 2034 * [see the comment in metaslab_impl.h for ms_synchist, ms_deferhist] 2035 */ 2036 static void 2037 metaslab_aux_histograms_update_done(metaslab_t *msp, boolean_t defer_allowed) 2038 { 2039 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2040 space_map_t *sm = msp->ms_sm; 2041 2042 if (sm == NULL) { 2043 /* 2044 * We came here from metaslab_init() when creating/opening a 2045 * pool, looking at a metaslab that hasn't had any allocations 2046 * yet. 2047 */ 2048 return; 2049 } 2050 2051 /* 2052 * This is similar to the actions that we take for the ms_freed 2053 * and ms_defer trees in metaslab_sync_done(). 2054 */ 2055 uint64_t hist_index = spa_syncing_txg(spa) % TXG_DEFER_SIZE; 2056 if (defer_allowed) { 2057 bcopy(msp->ms_synchist, msp->ms_deferhist[hist_index], 2058 sizeof (msp->ms_synchist)); 2059 } else { 2060 bzero(msp->ms_deferhist[hist_index], 2061 sizeof (msp->ms_deferhist[hist_index])); 2062 } 2063 bzero(msp->ms_synchist, sizeof (msp->ms_synchist)); 2064 } 2065 2066 /* 2067 * Ensure that the metaslab's weight and fragmentation are consistent 2068 * with the contents of the histogram (either the range tree's histogram 2069 * or the space map's depending whether the metaslab is loaded). 2070 */ 2071 static void 2072 metaslab_verify_weight_and_frag(metaslab_t *msp) 2073 { 2074 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2075 2076 if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0) 2077 return; 2078 2079 /* 2080 * We can end up here from vdev_remove_complete(), in which case we 2081 * cannot do these assertions because we hold spa config locks and 2082 * thus we are not allowed to read from the DMU. 2083 * 2084 * We check if the metaslab group has been removed and if that's 2085 * the case we return immediately as that would mean that we are 2086 * here from the aforementioned code path. 2087 */ 2088 if (msp->ms_group == NULL) 2089 return; 2090 2091 /* 2092 * Devices being removed always return a weight of 0 and leave 2093 * fragmentation and ms_max_size as is - there is nothing for 2094 * us to verify here. 2095 */ 2096 vdev_t *vd = msp->ms_group->mg_vd; 2097 if (vd->vdev_removing) 2098 return; 2099 2100 /* 2101 * If the metaslab is dirty it probably means that we've done 2102 * some allocations or frees that have changed our histograms 2103 * and thus the weight. 2104 */ 2105 for (int t = 0; t < TXG_SIZE; t++) { 2106 if (txg_list_member(&vd->vdev_ms_list, msp, t)) 2107 return; 2108 } 2109 2110 /* 2111 * This verification checks that our in-memory state is consistent 2112 * with what's on disk. If the pool is read-only then there aren't 2113 * any changes and we just have the initially-loaded state. 2114 */ 2115 if (!spa_writeable(msp->ms_group->mg_vd->vdev_spa)) 2116 return; 2117 2118 /* some extra verification for in-core tree if you can */ 2119 if (msp->ms_loaded) { 2120 range_tree_stat_verify(msp->ms_allocatable); 2121 VERIFY(space_map_histogram_verify(msp->ms_sm, 2122 msp->ms_allocatable)); 2123 } 2124 2125 uint64_t weight = msp->ms_weight; 2126 uint64_t was_active = msp->ms_weight & METASLAB_ACTIVE_MASK; 2127 boolean_t space_based = WEIGHT_IS_SPACEBASED(msp->ms_weight); 2128 uint64_t frag = msp->ms_fragmentation; 2129 uint64_t max_segsize = msp->ms_max_size; 2130 2131 msp->ms_weight = 0; 2132 msp->ms_fragmentation = 0; 2133 2134 /* 2135 * This function is used for verification purposes and thus should 2136 * not introduce any side-effects/mutations on the system's state. 2137 * 2138 * Regardless of whether metaslab_weight() thinks this metaslab 2139 * should be active or not, we want to ensure that the actual weight 2140 * (and therefore the value of ms_weight) would be the same if it 2141 * was to be recalculated at this point. 2142 * 2143 * In addition we set the nodirty flag so metaslab_weight() does 2144 * not dirty the metaslab for future TXGs (e.g. when trying to 2145 * force condensing to upgrade the metaslab spacemaps). 2146 */ 2147 msp->ms_weight = metaslab_weight(msp, B_TRUE) | was_active; 2148 2149 VERIFY3U(max_segsize, ==, msp->ms_max_size); 2150 2151 /* 2152 * If the weight type changed then there is no point in doing 2153 * verification. Revert fields to their original values. 2154 */ 2155 if ((space_based && !WEIGHT_IS_SPACEBASED(msp->ms_weight)) || 2156 (!space_based && WEIGHT_IS_SPACEBASED(msp->ms_weight))) { 2157 msp->ms_fragmentation = frag; 2158 msp->ms_weight = weight; 2159 return; 2160 } 2161 2162 VERIFY3U(msp->ms_fragmentation, ==, frag); 2163 VERIFY3U(msp->ms_weight, ==, weight); 2164 } 2165 2166 /* 2167 * If we're over the zfs_metaslab_mem_limit, select the loaded metaslab from 2168 * this class that was used longest ago, and attempt to unload it. We don't 2169 * want to spend too much time in this loop to prevent performance 2170 * degradation, and we expect that most of the time this operation will 2171 * succeed. Between that and the normal unloading processing during txg sync, 2172 * we expect this to keep the metaslab memory usage under control. 2173 */ 2174 static void 2175 metaslab_potentially_evict(metaslab_class_t *mc) 2176 { 2177 #ifdef _KERNEL 2178 uint64_t allmem = arc_all_memory(); 2179 uint64_t inuse = spl_kmem_cache_inuse(zfs_btree_leaf_cache); 2180 uint64_t size = spl_kmem_cache_entry_size(zfs_btree_leaf_cache); 2181 int tries = 0; 2182 for (; allmem * zfs_metaslab_mem_limit / 100 < inuse * size && 2183 tries < multilist_get_num_sublists(&mc->mc_metaslab_txg_list) * 2; 2184 tries++) { 2185 unsigned int idx = multilist_get_random_index( 2186 &mc->mc_metaslab_txg_list); 2187 multilist_sublist_t *mls = 2188 multilist_sublist_lock(&mc->mc_metaslab_txg_list, idx); 2189 metaslab_t *msp = multilist_sublist_head(mls); 2190 multilist_sublist_unlock(mls); 2191 while (msp != NULL && allmem * zfs_metaslab_mem_limit / 100 < 2192 inuse * size) { 2193 VERIFY3P(mls, ==, multilist_sublist_lock( 2194 &mc->mc_metaslab_txg_list, idx)); 2195 ASSERT3U(idx, ==, 2196 metaslab_idx_func(&mc->mc_metaslab_txg_list, msp)); 2197 2198 if (!multilist_link_active(&msp->ms_class_txg_node)) { 2199 multilist_sublist_unlock(mls); 2200 break; 2201 } 2202 metaslab_t *next_msp = multilist_sublist_next(mls, msp); 2203 multilist_sublist_unlock(mls); 2204 /* 2205 * If the metaslab is currently loading there are two 2206 * cases. If it's the metaslab we're evicting, we 2207 * can't continue on or we'll panic when we attempt to 2208 * recursively lock the mutex. If it's another 2209 * metaslab that's loading, it can be safely skipped, 2210 * since we know it's very new and therefore not a 2211 * good eviction candidate. We check later once the 2212 * lock is held that the metaslab is fully loaded 2213 * before actually unloading it. 2214 */ 2215 if (msp->ms_loading) { 2216 msp = next_msp; 2217 inuse = 2218 spl_kmem_cache_inuse(zfs_btree_leaf_cache); 2219 continue; 2220 } 2221 /* 2222 * We can't unload metaslabs with no spacemap because 2223 * they're not ready to be unloaded yet. We can't 2224 * unload metaslabs with outstanding allocations 2225 * because doing so could cause the metaslab's weight 2226 * to decrease while it's unloaded, which violates an 2227 * invariant that we use to prevent unnecessary 2228 * loading. We also don't unload metaslabs that are 2229 * currently active because they are high-weight 2230 * metaslabs that are likely to be used in the near 2231 * future. 2232 */ 2233 mutex_enter(&msp->ms_lock); 2234 if (msp->ms_allocator == -1 && msp->ms_sm != NULL && 2235 msp->ms_allocating_total == 0) { 2236 metaslab_unload(msp); 2237 } 2238 mutex_exit(&msp->ms_lock); 2239 msp = next_msp; 2240 inuse = spl_kmem_cache_inuse(zfs_btree_leaf_cache); 2241 } 2242 } 2243 #endif 2244 } 2245 2246 static int 2247 metaslab_load_impl(metaslab_t *msp) 2248 { 2249 int error = 0; 2250 2251 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2252 ASSERT(msp->ms_loading); 2253 ASSERT(!msp->ms_condensing); 2254 2255 /* 2256 * We temporarily drop the lock to unblock other operations while we 2257 * are reading the space map. Therefore, metaslab_sync() and 2258 * metaslab_sync_done() can run at the same time as we do. 2259 * 2260 * If we are using the log space maps, metaslab_sync() can't write to 2261 * the metaslab's space map while we are loading as we only write to 2262 * it when we are flushing the metaslab, and that can't happen while 2263 * we are loading it. 2264 * 2265 * If we are not using log space maps though, metaslab_sync() can 2266 * append to the space map while we are loading. Therefore we load 2267 * only entries that existed when we started the load. Additionally, 2268 * metaslab_sync_done() has to wait for the load to complete because 2269 * there are potential races like metaslab_load() loading parts of the 2270 * space map that are currently being appended by metaslab_sync(). If 2271 * we didn't, the ms_allocatable would have entries that 2272 * metaslab_sync_done() would try to re-add later. 2273 * 2274 * That's why before dropping the lock we remember the synced length 2275 * of the metaslab and read up to that point of the space map, 2276 * ignoring entries appended by metaslab_sync() that happen after we 2277 * drop the lock. 2278 */ 2279 uint64_t length = msp->ms_synced_length; 2280 mutex_exit(&msp->ms_lock); 2281 2282 hrtime_t load_start = gethrtime(); 2283 metaslab_rt_arg_t *mrap; 2284 if (msp->ms_allocatable->rt_arg == NULL) { 2285 mrap = kmem_zalloc(sizeof (*mrap), KM_SLEEP); 2286 } else { 2287 mrap = msp->ms_allocatable->rt_arg; 2288 msp->ms_allocatable->rt_ops = NULL; 2289 msp->ms_allocatable->rt_arg = NULL; 2290 } 2291 mrap->mra_bt = &msp->ms_allocatable_by_size; 2292 mrap->mra_floor_shift = metaslab_by_size_min_shift; 2293 2294 if (msp->ms_sm != NULL) { 2295 error = space_map_load_length(msp->ms_sm, msp->ms_allocatable, 2296 SM_FREE, length); 2297 2298 /* Now, populate the size-sorted tree. */ 2299 metaslab_rt_create(msp->ms_allocatable, mrap); 2300 msp->ms_allocatable->rt_ops = &metaslab_rt_ops; 2301 msp->ms_allocatable->rt_arg = mrap; 2302 2303 struct mssa_arg arg = {0}; 2304 arg.rt = msp->ms_allocatable; 2305 arg.mra = mrap; 2306 range_tree_walk(msp->ms_allocatable, metaslab_size_sorted_add, 2307 &arg); 2308 } else { 2309 /* 2310 * Add the size-sorted tree first, since we don't need to load 2311 * the metaslab from the spacemap. 2312 */ 2313 metaslab_rt_create(msp->ms_allocatable, mrap); 2314 msp->ms_allocatable->rt_ops = &metaslab_rt_ops; 2315 msp->ms_allocatable->rt_arg = mrap; 2316 /* 2317 * The space map has not been allocated yet, so treat 2318 * all the space in the metaslab as free and add it to the 2319 * ms_allocatable tree. 2320 */ 2321 range_tree_add(msp->ms_allocatable, 2322 msp->ms_start, msp->ms_size); 2323 2324 if (msp->ms_new) { 2325 /* 2326 * If the ms_sm doesn't exist, this means that this 2327 * metaslab hasn't gone through metaslab_sync() and 2328 * thus has never been dirtied. So we shouldn't 2329 * expect any unflushed allocs or frees from previous 2330 * TXGs. 2331 */ 2332 ASSERT(range_tree_is_empty(msp->ms_unflushed_allocs)); 2333 ASSERT(range_tree_is_empty(msp->ms_unflushed_frees)); 2334 } 2335 } 2336 2337 /* 2338 * We need to grab the ms_sync_lock to prevent metaslab_sync() from 2339 * changing the ms_sm (or log_sm) and the metaslab's range trees 2340 * while we are about to use them and populate the ms_allocatable. 2341 * The ms_lock is insufficient for this because metaslab_sync() doesn't 2342 * hold the ms_lock while writing the ms_checkpointing tree to disk. 2343 */ 2344 mutex_enter(&msp->ms_sync_lock); 2345 mutex_enter(&msp->ms_lock); 2346 2347 ASSERT(!msp->ms_condensing); 2348 ASSERT(!msp->ms_flushing); 2349 2350 if (error != 0) { 2351 mutex_exit(&msp->ms_sync_lock); 2352 return (error); 2353 } 2354 2355 ASSERT3P(msp->ms_group, !=, NULL); 2356 msp->ms_loaded = B_TRUE; 2357 2358 /* 2359 * Apply all the unflushed changes to ms_allocatable right 2360 * away so any manipulations we do below have a clear view 2361 * of what is allocated and what is free. 2362 */ 2363 range_tree_walk(msp->ms_unflushed_allocs, 2364 range_tree_remove, msp->ms_allocatable); 2365 range_tree_walk(msp->ms_unflushed_frees, 2366 range_tree_add, msp->ms_allocatable); 2367 2368 ASSERT3P(msp->ms_group, !=, NULL); 2369 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2370 if (spa_syncing_log_sm(spa) != NULL) { 2371 ASSERT(spa_feature_is_enabled(spa, 2372 SPA_FEATURE_LOG_SPACEMAP)); 2373 2374 /* 2375 * If we use a log space map we add all the segments 2376 * that are in ms_unflushed_frees so they are available 2377 * for allocation. 2378 * 2379 * ms_allocatable needs to contain all free segments 2380 * that are ready for allocations (thus not segments 2381 * from ms_freeing, ms_freed, and the ms_defer trees). 2382 * But if we grab the lock in this code path at a sync 2383 * pass later that 1, then it also contains the 2384 * segments of ms_freed (they were added to it earlier 2385 * in this path through ms_unflushed_frees). So we 2386 * need to remove all the segments that exist in 2387 * ms_freed from ms_allocatable as they will be added 2388 * later in metaslab_sync_done(). 2389 * 2390 * When there's no log space map, the ms_allocatable 2391 * correctly doesn't contain any segments that exist 2392 * in ms_freed [see ms_synced_length]. 2393 */ 2394 range_tree_walk(msp->ms_freed, 2395 range_tree_remove, msp->ms_allocatable); 2396 } 2397 2398 /* 2399 * If we are not using the log space map, ms_allocatable 2400 * contains the segments that exist in the ms_defer trees 2401 * [see ms_synced_length]. Thus we need to remove them 2402 * from ms_allocatable as they will be added again in 2403 * metaslab_sync_done(). 2404 * 2405 * If we are using the log space map, ms_allocatable still 2406 * contains the segments that exist in the ms_defer trees. 2407 * Not because it read them through the ms_sm though. But 2408 * because these segments are part of ms_unflushed_frees 2409 * whose segments we add to ms_allocatable earlier in this 2410 * code path. 2411 */ 2412 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2413 range_tree_walk(msp->ms_defer[t], 2414 range_tree_remove, msp->ms_allocatable); 2415 } 2416 2417 /* 2418 * Call metaslab_recalculate_weight_and_sort() now that the 2419 * metaslab is loaded so we get the metaslab's real weight. 2420 * 2421 * Unless this metaslab was created with older software and 2422 * has not yet been converted to use segment-based weight, we 2423 * expect the new weight to be better or equal to the weight 2424 * that the metaslab had while it was not loaded. This is 2425 * because the old weight does not take into account the 2426 * consolidation of adjacent segments between TXGs. [see 2427 * comment for ms_synchist and ms_deferhist[] for more info] 2428 */ 2429 uint64_t weight = msp->ms_weight; 2430 uint64_t max_size = msp->ms_max_size; 2431 metaslab_recalculate_weight_and_sort(msp); 2432 if (!WEIGHT_IS_SPACEBASED(weight)) 2433 ASSERT3U(weight, <=, msp->ms_weight); 2434 msp->ms_max_size = metaslab_largest_allocatable(msp); 2435 ASSERT3U(max_size, <=, msp->ms_max_size); 2436 hrtime_t load_end = gethrtime(); 2437 msp->ms_load_time = load_end; 2438 zfs_dbgmsg("metaslab_load: txg %llu, spa %s, vdev_id %llu, " 2439 "ms_id %llu, smp_length %llu, " 2440 "unflushed_allocs %llu, unflushed_frees %llu, " 2441 "freed %llu, defer %llu + %llu, unloaded time %llu ms, " 2442 "loading_time %lld ms, ms_max_size %llu, " 2443 "max size error %lld, " 2444 "old_weight %llx, new_weight %llx", 2445 (u_longlong_t)spa_syncing_txg(spa), spa_name(spa), 2446 (u_longlong_t)msp->ms_group->mg_vd->vdev_id, 2447 (u_longlong_t)msp->ms_id, 2448 (u_longlong_t)space_map_length(msp->ms_sm), 2449 (u_longlong_t)range_tree_space(msp->ms_unflushed_allocs), 2450 (u_longlong_t)range_tree_space(msp->ms_unflushed_frees), 2451 (u_longlong_t)range_tree_space(msp->ms_freed), 2452 (u_longlong_t)range_tree_space(msp->ms_defer[0]), 2453 (u_longlong_t)range_tree_space(msp->ms_defer[1]), 2454 (longlong_t)((load_start - msp->ms_unload_time) / 1000000), 2455 (longlong_t)((load_end - load_start) / 1000000), 2456 (u_longlong_t)msp->ms_max_size, 2457 (u_longlong_t)msp->ms_max_size - max_size, 2458 (u_longlong_t)weight, (u_longlong_t)msp->ms_weight); 2459 2460 metaslab_verify_space(msp, spa_syncing_txg(spa)); 2461 mutex_exit(&msp->ms_sync_lock); 2462 return (0); 2463 } 2464 2465 int 2466 metaslab_load(metaslab_t *msp) 2467 { 2468 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2469 2470 /* 2471 * There may be another thread loading the same metaslab, if that's 2472 * the case just wait until the other thread is done and return. 2473 */ 2474 metaslab_load_wait(msp); 2475 if (msp->ms_loaded) 2476 return (0); 2477 VERIFY(!msp->ms_loading); 2478 ASSERT(!msp->ms_condensing); 2479 2480 /* 2481 * We set the loading flag BEFORE potentially dropping the lock to 2482 * wait for an ongoing flush (see ms_flushing below). This way other 2483 * threads know that there is already a thread that is loading this 2484 * metaslab. 2485 */ 2486 msp->ms_loading = B_TRUE; 2487 2488 /* 2489 * Wait for any in-progress flushing to finish as we drop the ms_lock 2490 * both here (during space_map_load()) and in metaslab_flush() (when 2491 * we flush our changes to the ms_sm). 2492 */ 2493 if (msp->ms_flushing) 2494 metaslab_flush_wait(msp); 2495 2496 /* 2497 * In the possibility that we were waiting for the metaslab to be 2498 * flushed (where we temporarily dropped the ms_lock), ensure that 2499 * no one else loaded the metaslab somehow. 2500 */ 2501 ASSERT(!msp->ms_loaded); 2502 2503 /* 2504 * If we're loading a metaslab in the normal class, consider evicting 2505 * another one to keep our memory usage under the limit defined by the 2506 * zfs_metaslab_mem_limit tunable. 2507 */ 2508 if (spa_normal_class(msp->ms_group->mg_class->mc_spa) == 2509 msp->ms_group->mg_class) { 2510 metaslab_potentially_evict(msp->ms_group->mg_class); 2511 } 2512 2513 int error = metaslab_load_impl(msp); 2514 2515 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2516 msp->ms_loading = B_FALSE; 2517 cv_broadcast(&msp->ms_load_cv); 2518 2519 return (error); 2520 } 2521 2522 void 2523 metaslab_unload(metaslab_t *msp) 2524 { 2525 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2526 2527 /* 2528 * This can happen if a metaslab is selected for eviction (in 2529 * metaslab_potentially_evict) and then unloaded during spa_sync (via 2530 * metaslab_class_evict_old). 2531 */ 2532 if (!msp->ms_loaded) 2533 return; 2534 2535 range_tree_vacate(msp->ms_allocatable, NULL, NULL); 2536 msp->ms_loaded = B_FALSE; 2537 msp->ms_unload_time = gethrtime(); 2538 2539 msp->ms_activation_weight = 0; 2540 msp->ms_weight &= ~METASLAB_ACTIVE_MASK; 2541 2542 if (msp->ms_group != NULL) { 2543 metaslab_class_t *mc = msp->ms_group->mg_class; 2544 multilist_sublist_t *mls = 2545 multilist_sublist_lock_obj(&mc->mc_metaslab_txg_list, msp); 2546 if (multilist_link_active(&msp->ms_class_txg_node)) 2547 multilist_sublist_remove(mls, msp); 2548 multilist_sublist_unlock(mls); 2549 2550 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2551 zfs_dbgmsg("metaslab_unload: txg %llu, spa %s, vdev_id %llu, " 2552 "ms_id %llu, weight %llx, " 2553 "selected txg %llu (%llu ms ago), alloc_txg %llu, " 2554 "loaded %llu ms ago, max_size %llu", 2555 (u_longlong_t)spa_syncing_txg(spa), spa_name(spa), 2556 (u_longlong_t)msp->ms_group->mg_vd->vdev_id, 2557 (u_longlong_t)msp->ms_id, 2558 (u_longlong_t)msp->ms_weight, 2559 (u_longlong_t)msp->ms_selected_txg, 2560 (u_longlong_t)(msp->ms_unload_time - 2561 msp->ms_selected_time) / 1000 / 1000, 2562 (u_longlong_t)msp->ms_alloc_txg, 2563 (u_longlong_t)(msp->ms_unload_time - 2564 msp->ms_load_time) / 1000 / 1000, 2565 (u_longlong_t)msp->ms_max_size); 2566 } 2567 2568 /* 2569 * We explicitly recalculate the metaslab's weight based on its space 2570 * map (as it is now not loaded). We want unload metaslabs to always 2571 * have their weights calculated from the space map histograms, while 2572 * loaded ones have it calculated from their in-core range tree 2573 * [see metaslab_load()]. This way, the weight reflects the information 2574 * available in-core, whether it is loaded or not. 2575 * 2576 * If ms_group == NULL means that we came here from metaslab_fini(), 2577 * at which point it doesn't make sense for us to do the recalculation 2578 * and the sorting. 2579 */ 2580 if (msp->ms_group != NULL) 2581 metaslab_recalculate_weight_and_sort(msp); 2582 } 2583 2584 /* 2585 * We want to optimize the memory use of the per-metaslab range 2586 * trees. To do this, we store the segments in the range trees in 2587 * units of sectors, zero-indexing from the start of the metaslab. If 2588 * the vdev_ms_shift - the vdev_ashift is less than 32, we can store 2589 * the ranges using two uint32_ts, rather than two uint64_ts. 2590 */ 2591 range_seg_type_t 2592 metaslab_calculate_range_tree_type(vdev_t *vdev, metaslab_t *msp, 2593 uint64_t *start, uint64_t *shift) 2594 { 2595 if (vdev->vdev_ms_shift - vdev->vdev_ashift < 32 && 2596 !zfs_metaslab_force_large_segs) { 2597 *shift = vdev->vdev_ashift; 2598 *start = msp->ms_start; 2599 return (RANGE_SEG32); 2600 } else { 2601 *shift = 0; 2602 *start = 0; 2603 return (RANGE_SEG64); 2604 } 2605 } 2606 2607 void 2608 metaslab_set_selected_txg(metaslab_t *msp, uint64_t txg) 2609 { 2610 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2611 metaslab_class_t *mc = msp->ms_group->mg_class; 2612 multilist_sublist_t *mls = 2613 multilist_sublist_lock_obj(&mc->mc_metaslab_txg_list, msp); 2614 if (multilist_link_active(&msp->ms_class_txg_node)) 2615 multilist_sublist_remove(mls, msp); 2616 msp->ms_selected_txg = txg; 2617 msp->ms_selected_time = gethrtime(); 2618 multilist_sublist_insert_tail(mls, msp); 2619 multilist_sublist_unlock(mls); 2620 } 2621 2622 void 2623 metaslab_space_update(vdev_t *vd, metaslab_class_t *mc, int64_t alloc_delta, 2624 int64_t defer_delta, int64_t space_delta) 2625 { 2626 vdev_space_update(vd, alloc_delta, defer_delta, space_delta); 2627 2628 ASSERT3P(vd->vdev_spa->spa_root_vdev, ==, vd->vdev_parent); 2629 ASSERT(vd->vdev_ms_count != 0); 2630 2631 metaslab_class_space_update(mc, alloc_delta, defer_delta, space_delta, 2632 vdev_deflated_space(vd, space_delta)); 2633 } 2634 2635 int 2636 metaslab_init(metaslab_group_t *mg, uint64_t id, uint64_t object, 2637 uint64_t txg, metaslab_t **msp) 2638 { 2639 vdev_t *vd = mg->mg_vd; 2640 spa_t *spa = vd->vdev_spa; 2641 objset_t *mos = spa->spa_meta_objset; 2642 metaslab_t *ms; 2643 int error; 2644 2645 ms = kmem_zalloc(sizeof (metaslab_t), KM_SLEEP); 2646 mutex_init(&ms->ms_lock, NULL, MUTEX_DEFAULT, NULL); 2647 mutex_init(&ms->ms_sync_lock, NULL, MUTEX_DEFAULT, NULL); 2648 cv_init(&ms->ms_load_cv, NULL, CV_DEFAULT, NULL); 2649 cv_init(&ms->ms_flush_cv, NULL, CV_DEFAULT, NULL); 2650 multilist_link_init(&ms->ms_class_txg_node); 2651 2652 ms->ms_id = id; 2653 ms->ms_start = id << vd->vdev_ms_shift; 2654 ms->ms_size = 1ULL << vd->vdev_ms_shift; 2655 ms->ms_allocator = -1; 2656 ms->ms_new = B_TRUE; 2657 2658 vdev_ops_t *ops = vd->vdev_ops; 2659 if (ops->vdev_op_metaslab_init != NULL) 2660 ops->vdev_op_metaslab_init(vd, &ms->ms_start, &ms->ms_size); 2661 2662 /* 2663 * We only open space map objects that already exist. All others 2664 * will be opened when we finally allocate an object for it. 2665 * 2666 * Note: 2667 * When called from vdev_expand(), we can't call into the DMU as 2668 * we are holding the spa_config_lock as a writer and we would 2669 * deadlock [see relevant comment in vdev_metaslab_init()]. in 2670 * that case, the object parameter is zero though, so we won't 2671 * call into the DMU. 2672 */ 2673 if (object != 0) { 2674 error = space_map_open(&ms->ms_sm, mos, object, ms->ms_start, 2675 ms->ms_size, vd->vdev_ashift); 2676 2677 if (error != 0) { 2678 kmem_free(ms, sizeof (metaslab_t)); 2679 return (error); 2680 } 2681 2682 ASSERT(ms->ms_sm != NULL); 2683 ms->ms_allocated_space = space_map_allocated(ms->ms_sm); 2684 } 2685 2686 uint64_t shift, start; 2687 range_seg_type_t type = 2688 metaslab_calculate_range_tree_type(vd, ms, &start, &shift); 2689 2690 ms->ms_allocatable = range_tree_create(NULL, type, NULL, start, shift); 2691 for (int t = 0; t < TXG_SIZE; t++) { 2692 ms->ms_allocating[t] = range_tree_create(NULL, type, 2693 NULL, start, shift); 2694 } 2695 ms->ms_freeing = range_tree_create(NULL, type, NULL, start, shift); 2696 ms->ms_freed = range_tree_create(NULL, type, NULL, start, shift); 2697 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2698 ms->ms_defer[t] = range_tree_create(NULL, type, NULL, 2699 start, shift); 2700 } 2701 ms->ms_checkpointing = 2702 range_tree_create(NULL, type, NULL, start, shift); 2703 ms->ms_unflushed_allocs = 2704 range_tree_create(NULL, type, NULL, start, shift); 2705 2706 metaslab_rt_arg_t *mrap = kmem_zalloc(sizeof (*mrap), KM_SLEEP); 2707 mrap->mra_bt = &ms->ms_unflushed_frees_by_size; 2708 mrap->mra_floor_shift = metaslab_by_size_min_shift; 2709 ms->ms_unflushed_frees = range_tree_create(&metaslab_rt_ops, 2710 type, mrap, start, shift); 2711 2712 ms->ms_trim = range_tree_create(NULL, type, NULL, start, shift); 2713 2714 metaslab_group_add(mg, ms); 2715 metaslab_set_fragmentation(ms, B_FALSE); 2716 2717 /* 2718 * If we're opening an existing pool (txg == 0) or creating 2719 * a new one (txg == TXG_INITIAL), all space is available now. 2720 * If we're adding space to an existing pool, the new space 2721 * does not become available until after this txg has synced. 2722 * The metaslab's weight will also be initialized when we sync 2723 * out this txg. This ensures that we don't attempt to allocate 2724 * from it before we have initialized it completely. 2725 */ 2726 if (txg <= TXG_INITIAL) { 2727 metaslab_sync_done(ms, 0); 2728 metaslab_space_update(vd, mg->mg_class, 2729 metaslab_allocated_space(ms), 0, 0); 2730 } 2731 2732 if (txg != 0) { 2733 vdev_dirty(vd, 0, NULL, txg); 2734 vdev_dirty(vd, VDD_METASLAB, ms, txg); 2735 } 2736 2737 *msp = ms; 2738 2739 return (0); 2740 } 2741 2742 static void 2743 metaslab_fini_flush_data(metaslab_t *msp) 2744 { 2745 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2746 2747 if (metaslab_unflushed_txg(msp) == 0) { 2748 ASSERT3P(avl_find(&spa->spa_metaslabs_by_flushed, msp, NULL), 2749 ==, NULL); 2750 return; 2751 } 2752 ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)); 2753 2754 mutex_enter(&spa->spa_flushed_ms_lock); 2755 avl_remove(&spa->spa_metaslabs_by_flushed, msp); 2756 mutex_exit(&spa->spa_flushed_ms_lock); 2757 2758 spa_log_sm_decrement_mscount(spa, metaslab_unflushed_txg(msp)); 2759 spa_log_summary_decrement_mscount(spa, metaslab_unflushed_txg(msp)); 2760 } 2761 2762 uint64_t 2763 metaslab_unflushed_changes_memused(metaslab_t *ms) 2764 { 2765 return ((range_tree_numsegs(ms->ms_unflushed_allocs) + 2766 range_tree_numsegs(ms->ms_unflushed_frees)) * 2767 ms->ms_unflushed_allocs->rt_root.bt_elem_size); 2768 } 2769 2770 void 2771 metaslab_fini(metaslab_t *msp) 2772 { 2773 metaslab_group_t *mg = msp->ms_group; 2774 vdev_t *vd = mg->mg_vd; 2775 spa_t *spa = vd->vdev_spa; 2776 2777 metaslab_fini_flush_data(msp); 2778 2779 metaslab_group_remove(mg, msp); 2780 2781 mutex_enter(&msp->ms_lock); 2782 VERIFY(msp->ms_group == NULL); 2783 2784 /* 2785 * If this metaslab hasn't been through metaslab_sync_done() yet its 2786 * space hasn't been accounted for in its vdev and doesn't need to be 2787 * subtracted. 2788 */ 2789 if (!msp->ms_new) { 2790 metaslab_space_update(vd, mg->mg_class, 2791 -metaslab_allocated_space(msp), 0, -msp->ms_size); 2792 2793 } 2794 space_map_close(msp->ms_sm); 2795 msp->ms_sm = NULL; 2796 2797 metaslab_unload(msp); 2798 2799 range_tree_destroy(msp->ms_allocatable); 2800 range_tree_destroy(msp->ms_freeing); 2801 range_tree_destroy(msp->ms_freed); 2802 2803 ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=, 2804 metaslab_unflushed_changes_memused(msp)); 2805 spa->spa_unflushed_stats.sus_memused -= 2806 metaslab_unflushed_changes_memused(msp); 2807 range_tree_vacate(msp->ms_unflushed_allocs, NULL, NULL); 2808 range_tree_destroy(msp->ms_unflushed_allocs); 2809 range_tree_destroy(msp->ms_checkpointing); 2810 range_tree_vacate(msp->ms_unflushed_frees, NULL, NULL); 2811 range_tree_destroy(msp->ms_unflushed_frees); 2812 2813 for (int t = 0; t < TXG_SIZE; t++) { 2814 range_tree_destroy(msp->ms_allocating[t]); 2815 } 2816 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2817 range_tree_destroy(msp->ms_defer[t]); 2818 } 2819 ASSERT0(msp->ms_deferspace); 2820 2821 for (int t = 0; t < TXG_SIZE; t++) 2822 ASSERT(!txg_list_member(&vd->vdev_ms_list, msp, t)); 2823 2824 range_tree_vacate(msp->ms_trim, NULL, NULL); 2825 range_tree_destroy(msp->ms_trim); 2826 2827 mutex_exit(&msp->ms_lock); 2828 cv_destroy(&msp->ms_load_cv); 2829 cv_destroy(&msp->ms_flush_cv); 2830 mutex_destroy(&msp->ms_lock); 2831 mutex_destroy(&msp->ms_sync_lock); 2832 ASSERT3U(msp->ms_allocator, ==, -1); 2833 2834 kmem_free(msp, sizeof (metaslab_t)); 2835 } 2836 2837 #define FRAGMENTATION_TABLE_SIZE 17 2838 2839 /* 2840 * This table defines a segment size based fragmentation metric that will 2841 * allow each metaslab to derive its own fragmentation value. This is done 2842 * by calculating the space in each bucket of the spacemap histogram and 2843 * multiplying that by the fragmentation metric in this table. Doing 2844 * this for all buckets and dividing it by the total amount of free 2845 * space in this metaslab (i.e. the total free space in all buckets) gives 2846 * us the fragmentation metric. This means that a high fragmentation metric 2847 * equates to most of the free space being comprised of small segments. 2848 * Conversely, if the metric is low, then most of the free space is in 2849 * large segments. A 10% change in fragmentation equates to approximately 2850 * double the number of segments. 2851 * 2852 * This table defines 0% fragmented space using 16MB segments. Testing has 2853 * shown that segments that are greater than or equal to 16MB do not suffer 2854 * from drastic performance problems. Using this value, we derive the rest 2855 * of the table. Since the fragmentation value is never stored on disk, it 2856 * is possible to change these calculations in the future. 2857 */ 2858 int zfs_frag_table[FRAGMENTATION_TABLE_SIZE] = { 2859 100, /* 512B */ 2860 100, /* 1K */ 2861 98, /* 2K */ 2862 95, /* 4K */ 2863 90, /* 8K */ 2864 80, /* 16K */ 2865 70, /* 32K */ 2866 60, /* 64K */ 2867 50, /* 128K */ 2868 40, /* 256K */ 2869 30, /* 512K */ 2870 20, /* 1M */ 2871 15, /* 2M */ 2872 10, /* 4M */ 2873 5, /* 8M */ 2874 0 /* 16M */ 2875 }; 2876 2877 /* 2878 * Calculate the metaslab's fragmentation metric and set ms_fragmentation. 2879 * Setting this value to ZFS_FRAG_INVALID means that the metaslab has not 2880 * been upgraded and does not support this metric. Otherwise, the return 2881 * value should be in the range [0, 100]. 2882 */ 2883 static void 2884 metaslab_set_fragmentation(metaslab_t *msp, boolean_t nodirty) 2885 { 2886 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2887 uint64_t fragmentation = 0; 2888 uint64_t total = 0; 2889 boolean_t feature_enabled = spa_feature_is_enabled(spa, 2890 SPA_FEATURE_SPACEMAP_HISTOGRAM); 2891 2892 if (!feature_enabled) { 2893 msp->ms_fragmentation = ZFS_FRAG_INVALID; 2894 return; 2895 } 2896 2897 /* 2898 * A null space map means that the entire metaslab is free 2899 * and thus is not fragmented. 2900 */ 2901 if (msp->ms_sm == NULL) { 2902 msp->ms_fragmentation = 0; 2903 return; 2904 } 2905 2906 /* 2907 * If this metaslab's space map has not been upgraded, flag it 2908 * so that we upgrade next time we encounter it. 2909 */ 2910 if (msp->ms_sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) { 2911 uint64_t txg = spa_syncing_txg(spa); 2912 vdev_t *vd = msp->ms_group->mg_vd; 2913 2914 /* 2915 * If we've reached the final dirty txg, then we must 2916 * be shutting down the pool. We don't want to dirty 2917 * any data past this point so skip setting the condense 2918 * flag. We can retry this action the next time the pool 2919 * is imported. We also skip marking this metaslab for 2920 * condensing if the caller has explicitly set nodirty. 2921 */ 2922 if (!nodirty && 2923 spa_writeable(spa) && txg < spa_final_dirty_txg(spa)) { 2924 msp->ms_condense_wanted = B_TRUE; 2925 vdev_dirty(vd, VDD_METASLAB, msp, txg + 1); 2926 zfs_dbgmsg("txg %llu, requesting force condense: " 2927 "ms_id %llu, vdev_id %llu", (u_longlong_t)txg, 2928 (u_longlong_t)msp->ms_id, 2929 (u_longlong_t)vd->vdev_id); 2930 } 2931 msp->ms_fragmentation = ZFS_FRAG_INVALID; 2932 return; 2933 } 2934 2935 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 2936 uint64_t space = 0; 2937 uint8_t shift = msp->ms_sm->sm_shift; 2938 2939 int idx = MIN(shift - SPA_MINBLOCKSHIFT + i, 2940 FRAGMENTATION_TABLE_SIZE - 1); 2941 2942 if (msp->ms_sm->sm_phys->smp_histogram[i] == 0) 2943 continue; 2944 2945 space = msp->ms_sm->sm_phys->smp_histogram[i] << (i + shift); 2946 total += space; 2947 2948 ASSERT3U(idx, <, FRAGMENTATION_TABLE_SIZE); 2949 fragmentation += space * zfs_frag_table[idx]; 2950 } 2951 2952 if (total > 0) 2953 fragmentation /= total; 2954 ASSERT3U(fragmentation, <=, 100); 2955 2956 msp->ms_fragmentation = fragmentation; 2957 } 2958 2959 /* 2960 * Compute a weight -- a selection preference value -- for the given metaslab. 2961 * This is based on the amount of free space, the level of fragmentation, 2962 * the LBA range, and whether the metaslab is loaded. 2963 */ 2964 static uint64_t 2965 metaslab_space_weight(metaslab_t *msp) 2966 { 2967 metaslab_group_t *mg = msp->ms_group; 2968 vdev_t *vd = mg->mg_vd; 2969 uint64_t weight, space; 2970 2971 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2972 2973 /* 2974 * The baseline weight is the metaslab's free space. 2975 */ 2976 space = msp->ms_size - metaslab_allocated_space(msp); 2977 2978 if (metaslab_fragmentation_factor_enabled && 2979 msp->ms_fragmentation != ZFS_FRAG_INVALID) { 2980 /* 2981 * Use the fragmentation information to inversely scale 2982 * down the baseline weight. We need to ensure that we 2983 * don't exclude this metaslab completely when it's 100% 2984 * fragmented. To avoid this we reduce the fragmented value 2985 * by 1. 2986 */ 2987 space = (space * (100 - (msp->ms_fragmentation - 1))) / 100; 2988 2989 /* 2990 * If space < SPA_MINBLOCKSIZE, then we will not allocate from 2991 * this metaslab again. The fragmentation metric may have 2992 * decreased the space to something smaller than 2993 * SPA_MINBLOCKSIZE, so reset the space to SPA_MINBLOCKSIZE 2994 * so that we can consume any remaining space. 2995 */ 2996 if (space > 0 && space < SPA_MINBLOCKSIZE) 2997 space = SPA_MINBLOCKSIZE; 2998 } 2999 weight = space; 3000 3001 /* 3002 * Modern disks have uniform bit density and constant angular velocity. 3003 * Therefore, the outer recording zones are faster (higher bandwidth) 3004 * than the inner zones by the ratio of outer to inner track diameter, 3005 * which is typically around 2:1. We account for this by assigning 3006 * higher weight to lower metaslabs (multiplier ranging from 2x to 1x). 3007 * In effect, this means that we'll select the metaslab with the most 3008 * free bandwidth rather than simply the one with the most free space. 3009 */ 3010 if (!vd->vdev_nonrot && metaslab_lba_weighting_enabled) { 3011 weight = 2 * weight - (msp->ms_id * weight) / vd->vdev_ms_count; 3012 ASSERT(weight >= space && weight <= 2 * space); 3013 } 3014 3015 /* 3016 * If this metaslab is one we're actively using, adjust its 3017 * weight to make it preferable to any inactive metaslab so 3018 * we'll polish it off. If the fragmentation on this metaslab 3019 * has exceed our threshold, then don't mark it active. 3020 */ 3021 if (msp->ms_loaded && msp->ms_fragmentation != ZFS_FRAG_INVALID && 3022 msp->ms_fragmentation <= zfs_metaslab_fragmentation_threshold) { 3023 weight |= (msp->ms_weight & METASLAB_ACTIVE_MASK); 3024 } 3025 3026 WEIGHT_SET_SPACEBASED(weight); 3027 return (weight); 3028 } 3029 3030 /* 3031 * Return the weight of the specified metaslab, according to the segment-based 3032 * weighting algorithm. The metaslab must be loaded. This function can 3033 * be called within a sync pass since it relies only on the metaslab's 3034 * range tree which is always accurate when the metaslab is loaded. 3035 */ 3036 static uint64_t 3037 metaslab_weight_from_range_tree(metaslab_t *msp) 3038 { 3039 uint64_t weight = 0; 3040 uint32_t segments = 0; 3041 3042 ASSERT(msp->ms_loaded); 3043 3044 for (int i = RANGE_TREE_HISTOGRAM_SIZE - 1; i >= SPA_MINBLOCKSHIFT; 3045 i--) { 3046 uint8_t shift = msp->ms_group->mg_vd->vdev_ashift; 3047 int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1; 3048 3049 segments <<= 1; 3050 segments += msp->ms_allocatable->rt_histogram[i]; 3051 3052 /* 3053 * The range tree provides more precision than the space map 3054 * and must be downgraded so that all values fit within the 3055 * space map's histogram. This allows us to compare loaded 3056 * vs. unloaded metaslabs to determine which metaslab is 3057 * considered "best". 3058 */ 3059 if (i > max_idx) 3060 continue; 3061 3062 if (segments != 0) { 3063 WEIGHT_SET_COUNT(weight, segments); 3064 WEIGHT_SET_INDEX(weight, i); 3065 WEIGHT_SET_ACTIVE(weight, 0); 3066 break; 3067 } 3068 } 3069 return (weight); 3070 } 3071 3072 /* 3073 * Calculate the weight based on the on-disk histogram. Should be applied 3074 * only to unloaded metaslabs (i.e no incoming allocations) in-order to 3075 * give results consistent with the on-disk state 3076 */ 3077 static uint64_t 3078 metaslab_weight_from_spacemap(metaslab_t *msp) 3079 { 3080 space_map_t *sm = msp->ms_sm; 3081 ASSERT(!msp->ms_loaded); 3082 ASSERT(sm != NULL); 3083 ASSERT3U(space_map_object(sm), !=, 0); 3084 ASSERT3U(sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t)); 3085 3086 /* 3087 * Create a joint histogram from all the segments that have made 3088 * it to the metaslab's space map histogram, that are not yet 3089 * available for allocation because they are still in the freeing 3090 * pipeline (e.g. freeing, freed, and defer trees). Then subtract 3091 * these segments from the space map's histogram to get a more 3092 * accurate weight. 3093 */ 3094 uint64_t deferspace_histogram[SPACE_MAP_HISTOGRAM_SIZE] = {0}; 3095 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) 3096 deferspace_histogram[i] += msp->ms_synchist[i]; 3097 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 3098 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 3099 deferspace_histogram[i] += msp->ms_deferhist[t][i]; 3100 } 3101 } 3102 3103 uint64_t weight = 0; 3104 for (int i = SPACE_MAP_HISTOGRAM_SIZE - 1; i >= 0; i--) { 3105 ASSERT3U(sm->sm_phys->smp_histogram[i], >=, 3106 deferspace_histogram[i]); 3107 uint64_t count = 3108 sm->sm_phys->smp_histogram[i] - deferspace_histogram[i]; 3109 if (count != 0) { 3110 WEIGHT_SET_COUNT(weight, count); 3111 WEIGHT_SET_INDEX(weight, i + sm->sm_shift); 3112 WEIGHT_SET_ACTIVE(weight, 0); 3113 break; 3114 } 3115 } 3116 return (weight); 3117 } 3118 3119 /* 3120 * Compute a segment-based weight for the specified metaslab. The weight 3121 * is determined by highest bucket in the histogram. The information 3122 * for the highest bucket is encoded into the weight value. 3123 */ 3124 static uint64_t 3125 metaslab_segment_weight(metaslab_t *msp) 3126 { 3127 metaslab_group_t *mg = msp->ms_group; 3128 uint64_t weight = 0; 3129 uint8_t shift = mg->mg_vd->vdev_ashift; 3130 3131 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3132 3133 /* 3134 * The metaslab is completely free. 3135 */ 3136 if (metaslab_allocated_space(msp) == 0) { 3137 int idx = highbit64(msp->ms_size) - 1; 3138 int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1; 3139 3140 if (idx < max_idx) { 3141 WEIGHT_SET_COUNT(weight, 1ULL); 3142 WEIGHT_SET_INDEX(weight, idx); 3143 } else { 3144 WEIGHT_SET_COUNT(weight, 1ULL << (idx - max_idx)); 3145 WEIGHT_SET_INDEX(weight, max_idx); 3146 } 3147 WEIGHT_SET_ACTIVE(weight, 0); 3148 ASSERT(!WEIGHT_IS_SPACEBASED(weight)); 3149 return (weight); 3150 } 3151 3152 ASSERT3U(msp->ms_sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t)); 3153 3154 /* 3155 * If the metaslab is fully allocated then just make the weight 0. 3156 */ 3157 if (metaslab_allocated_space(msp) == msp->ms_size) 3158 return (0); 3159 /* 3160 * If the metaslab is already loaded, then use the range tree to 3161 * determine the weight. Otherwise, we rely on the space map information 3162 * to generate the weight. 3163 */ 3164 if (msp->ms_loaded) { 3165 weight = metaslab_weight_from_range_tree(msp); 3166 } else { 3167 weight = metaslab_weight_from_spacemap(msp); 3168 } 3169 3170 /* 3171 * If the metaslab was active the last time we calculated its weight 3172 * then keep it active. We want to consume the entire region that 3173 * is associated with this weight. 3174 */ 3175 if (msp->ms_activation_weight != 0 && weight != 0) 3176 WEIGHT_SET_ACTIVE(weight, WEIGHT_GET_ACTIVE(msp->ms_weight)); 3177 return (weight); 3178 } 3179 3180 /* 3181 * Determine if we should attempt to allocate from this metaslab. If the 3182 * metaslab is loaded, then we can determine if the desired allocation 3183 * can be satisfied by looking at the size of the maximum free segment 3184 * on that metaslab. Otherwise, we make our decision based on the metaslab's 3185 * weight. For segment-based weighting we can determine the maximum 3186 * allocation based on the index encoded in its value. For space-based 3187 * weights we rely on the entire weight (excluding the weight-type bit). 3188 */ 3189 static boolean_t 3190 metaslab_should_allocate(metaslab_t *msp, uint64_t asize, boolean_t try_hard) 3191 { 3192 /* 3193 * If the metaslab is loaded, ms_max_size is definitive and we can use 3194 * the fast check. If it's not, the ms_max_size is a lower bound (once 3195 * set), and we should use the fast check as long as we're not in 3196 * try_hard and it's been less than zfs_metaslab_max_size_cache_sec 3197 * seconds since the metaslab was unloaded. 3198 */ 3199 if (msp->ms_loaded || 3200 (msp->ms_max_size != 0 && !try_hard && gethrtime() < 3201 msp->ms_unload_time + SEC2NSEC(zfs_metaslab_max_size_cache_sec))) 3202 return (msp->ms_max_size >= asize); 3203 3204 boolean_t should_allocate; 3205 if (!WEIGHT_IS_SPACEBASED(msp->ms_weight)) { 3206 /* 3207 * The metaslab segment weight indicates segments in the 3208 * range [2^i, 2^(i+1)), where i is the index in the weight. 3209 * Since the asize might be in the middle of the range, we 3210 * should attempt the allocation if asize < 2^(i+1). 3211 */ 3212 should_allocate = (asize < 3213 1ULL << (WEIGHT_GET_INDEX(msp->ms_weight) + 1)); 3214 } else { 3215 should_allocate = (asize <= 3216 (msp->ms_weight & ~METASLAB_WEIGHT_TYPE)); 3217 } 3218 3219 return (should_allocate); 3220 } 3221 3222 static uint64_t 3223 metaslab_weight(metaslab_t *msp, boolean_t nodirty) 3224 { 3225 vdev_t *vd = msp->ms_group->mg_vd; 3226 spa_t *spa = vd->vdev_spa; 3227 uint64_t weight; 3228 3229 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3230 3231 metaslab_set_fragmentation(msp, nodirty); 3232 3233 /* 3234 * Update the maximum size. If the metaslab is loaded, this will 3235 * ensure that we get an accurate maximum size if newly freed space 3236 * has been added back into the free tree. If the metaslab is 3237 * unloaded, we check if there's a larger free segment in the 3238 * unflushed frees. This is a lower bound on the largest allocatable 3239 * segment size. Coalescing of adjacent entries may reveal larger 3240 * allocatable segments, but we aren't aware of those until loading 3241 * the space map into a range tree. 3242 */ 3243 if (msp->ms_loaded) { 3244 msp->ms_max_size = metaslab_largest_allocatable(msp); 3245 } else { 3246 msp->ms_max_size = MAX(msp->ms_max_size, 3247 metaslab_largest_unflushed_free(msp)); 3248 } 3249 3250 /* 3251 * Segment-based weighting requires space map histogram support. 3252 */ 3253 if (zfs_metaslab_segment_weight_enabled && 3254 spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM) && 3255 (msp->ms_sm == NULL || msp->ms_sm->sm_dbuf->db_size == 3256 sizeof (space_map_phys_t))) { 3257 weight = metaslab_segment_weight(msp); 3258 } else { 3259 weight = metaslab_space_weight(msp); 3260 } 3261 return (weight); 3262 } 3263 3264 void 3265 metaslab_recalculate_weight_and_sort(metaslab_t *msp) 3266 { 3267 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3268 3269 /* note: we preserve the mask (e.g. indication of primary, etc..) */ 3270 uint64_t was_active = msp->ms_weight & METASLAB_ACTIVE_MASK; 3271 metaslab_group_sort(msp->ms_group, msp, 3272 metaslab_weight(msp, B_FALSE) | was_active); 3273 } 3274 3275 static int 3276 metaslab_activate_allocator(metaslab_group_t *mg, metaslab_t *msp, 3277 int allocator, uint64_t activation_weight) 3278 { 3279 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 3280 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3281 3282 /* 3283 * If we're activating for the claim code, we don't want to actually 3284 * set the metaslab up for a specific allocator. 3285 */ 3286 if (activation_weight == METASLAB_WEIGHT_CLAIM) { 3287 ASSERT0(msp->ms_activation_weight); 3288 msp->ms_activation_weight = msp->ms_weight; 3289 metaslab_group_sort(mg, msp, msp->ms_weight | 3290 activation_weight); 3291 return (0); 3292 } 3293 3294 metaslab_t **mspp = (activation_weight == METASLAB_WEIGHT_PRIMARY ? 3295 &mga->mga_primary : &mga->mga_secondary); 3296 3297 mutex_enter(&mg->mg_lock); 3298 if (*mspp != NULL) { 3299 mutex_exit(&mg->mg_lock); 3300 return (EEXIST); 3301 } 3302 3303 *mspp = msp; 3304 ASSERT3S(msp->ms_allocator, ==, -1); 3305 msp->ms_allocator = allocator; 3306 msp->ms_primary = (activation_weight == METASLAB_WEIGHT_PRIMARY); 3307 3308 ASSERT0(msp->ms_activation_weight); 3309 msp->ms_activation_weight = msp->ms_weight; 3310 metaslab_group_sort_impl(mg, msp, 3311 msp->ms_weight | activation_weight); 3312 mutex_exit(&mg->mg_lock); 3313 3314 return (0); 3315 } 3316 3317 static int 3318 metaslab_activate(metaslab_t *msp, int allocator, uint64_t activation_weight) 3319 { 3320 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3321 3322 /* 3323 * The current metaslab is already activated for us so there 3324 * is nothing to do. Already activated though, doesn't mean 3325 * that this metaslab is activated for our allocator nor our 3326 * requested activation weight. The metaslab could have started 3327 * as an active one for our allocator but changed allocators 3328 * while we were waiting to grab its ms_lock or we stole it 3329 * [see find_valid_metaslab()]. This means that there is a 3330 * possibility of passivating a metaslab of another allocator 3331 * or from a different activation mask, from this thread. 3332 */ 3333 if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) { 3334 ASSERT(msp->ms_loaded); 3335 return (0); 3336 } 3337 3338 int error = metaslab_load(msp); 3339 if (error != 0) { 3340 metaslab_group_sort(msp->ms_group, msp, 0); 3341 return (error); 3342 } 3343 3344 /* 3345 * When entering metaslab_load() we may have dropped the 3346 * ms_lock because we were loading this metaslab, or we 3347 * were waiting for another thread to load it for us. In 3348 * that scenario, we recheck the weight of the metaslab 3349 * to see if it was activated by another thread. 3350 * 3351 * If the metaslab was activated for another allocator or 3352 * it was activated with a different activation weight (e.g. 3353 * we wanted to make it a primary but it was activated as 3354 * secondary) we return error (EBUSY). 3355 * 3356 * If the metaslab was activated for the same allocator 3357 * and requested activation mask, skip activating it. 3358 */ 3359 if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) { 3360 if (msp->ms_allocator != allocator) 3361 return (EBUSY); 3362 3363 if ((msp->ms_weight & activation_weight) == 0) 3364 return (SET_ERROR(EBUSY)); 3365 3366 EQUIV((activation_weight == METASLAB_WEIGHT_PRIMARY), 3367 msp->ms_primary); 3368 return (0); 3369 } 3370 3371 /* 3372 * If the metaslab has literally 0 space, it will have weight 0. In 3373 * that case, don't bother activating it. This can happen if the 3374 * metaslab had space during find_valid_metaslab, but another thread 3375 * loaded it and used all that space while we were waiting to grab the 3376 * lock. 3377 */ 3378 if (msp->ms_weight == 0) { 3379 ASSERT0(range_tree_space(msp->ms_allocatable)); 3380 return (SET_ERROR(ENOSPC)); 3381 } 3382 3383 if ((error = metaslab_activate_allocator(msp->ms_group, msp, 3384 allocator, activation_weight)) != 0) { 3385 return (error); 3386 } 3387 3388 ASSERT(msp->ms_loaded); 3389 ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK); 3390 3391 return (0); 3392 } 3393 3394 static void 3395 metaslab_passivate_allocator(metaslab_group_t *mg, metaslab_t *msp, 3396 uint64_t weight) 3397 { 3398 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3399 ASSERT(msp->ms_loaded); 3400 3401 if (msp->ms_weight & METASLAB_WEIGHT_CLAIM) { 3402 metaslab_group_sort(mg, msp, weight); 3403 return; 3404 } 3405 3406 mutex_enter(&mg->mg_lock); 3407 ASSERT3P(msp->ms_group, ==, mg); 3408 ASSERT3S(0, <=, msp->ms_allocator); 3409 ASSERT3U(msp->ms_allocator, <, mg->mg_allocators); 3410 3411 metaslab_group_allocator_t *mga = &mg->mg_allocator[msp->ms_allocator]; 3412 if (msp->ms_primary) { 3413 ASSERT3P(mga->mga_primary, ==, msp); 3414 ASSERT(msp->ms_weight & METASLAB_WEIGHT_PRIMARY); 3415 mga->mga_primary = NULL; 3416 } else { 3417 ASSERT3P(mga->mga_secondary, ==, msp); 3418 ASSERT(msp->ms_weight & METASLAB_WEIGHT_SECONDARY); 3419 mga->mga_secondary = NULL; 3420 } 3421 msp->ms_allocator = -1; 3422 metaslab_group_sort_impl(mg, msp, weight); 3423 mutex_exit(&mg->mg_lock); 3424 } 3425 3426 static void 3427 metaslab_passivate(metaslab_t *msp, uint64_t weight) 3428 { 3429 uint64_t size __maybe_unused = weight & ~METASLAB_WEIGHT_TYPE; 3430 3431 /* 3432 * If size < SPA_MINBLOCKSIZE, then we will not allocate from 3433 * this metaslab again. In that case, it had better be empty, 3434 * or we would be leaving space on the table. 3435 */ 3436 ASSERT(!WEIGHT_IS_SPACEBASED(msp->ms_weight) || 3437 size >= SPA_MINBLOCKSIZE || 3438 range_tree_space(msp->ms_allocatable) == 0); 3439 ASSERT0(weight & METASLAB_ACTIVE_MASK); 3440 3441 ASSERT(msp->ms_activation_weight != 0); 3442 msp->ms_activation_weight = 0; 3443 metaslab_passivate_allocator(msp->ms_group, msp, weight); 3444 ASSERT0(msp->ms_weight & METASLAB_ACTIVE_MASK); 3445 } 3446 3447 /* 3448 * Segment-based metaslabs are activated once and remain active until 3449 * we either fail an allocation attempt (similar to space-based metaslabs) 3450 * or have exhausted the free space in zfs_metaslab_switch_threshold 3451 * buckets since the metaslab was activated. This function checks to see 3452 * if we've exhausted the zfs_metaslab_switch_threshold buckets in the 3453 * metaslab and passivates it proactively. This will allow us to select a 3454 * metaslab with a larger contiguous region, if any, remaining within this 3455 * metaslab group. If we're in sync pass > 1, then we continue using this 3456 * metaslab so that we don't dirty more block and cause more sync passes. 3457 */ 3458 static void 3459 metaslab_segment_may_passivate(metaslab_t *msp) 3460 { 3461 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 3462 3463 if (WEIGHT_IS_SPACEBASED(msp->ms_weight) || spa_sync_pass(spa) > 1) 3464 return; 3465 3466 /* 3467 * Since we are in the middle of a sync pass, the most accurate 3468 * information that is accessible to us is the in-core range tree 3469 * histogram; calculate the new weight based on that information. 3470 */ 3471 uint64_t weight = metaslab_weight_from_range_tree(msp); 3472 int activation_idx = WEIGHT_GET_INDEX(msp->ms_activation_weight); 3473 int current_idx = WEIGHT_GET_INDEX(weight); 3474 3475 if (current_idx <= activation_idx - zfs_metaslab_switch_threshold) 3476 metaslab_passivate(msp, weight); 3477 } 3478 3479 static void 3480 metaslab_preload(void *arg) 3481 { 3482 metaslab_t *msp = arg; 3483 metaslab_class_t *mc = msp->ms_group->mg_class; 3484 spa_t *spa = mc->mc_spa; 3485 fstrans_cookie_t cookie = spl_fstrans_mark(); 3486 3487 ASSERT(!MUTEX_HELD(&msp->ms_group->mg_lock)); 3488 3489 mutex_enter(&msp->ms_lock); 3490 (void) metaslab_load(msp); 3491 metaslab_set_selected_txg(msp, spa_syncing_txg(spa)); 3492 mutex_exit(&msp->ms_lock); 3493 spl_fstrans_unmark(cookie); 3494 } 3495 3496 static void 3497 metaslab_group_preload(metaslab_group_t *mg) 3498 { 3499 spa_t *spa = mg->mg_vd->vdev_spa; 3500 metaslab_t *msp; 3501 avl_tree_t *t = &mg->mg_metaslab_tree; 3502 int m = 0; 3503 3504 if (spa_shutting_down(spa) || !metaslab_preload_enabled) { 3505 taskq_wait_outstanding(mg->mg_taskq, 0); 3506 return; 3507 } 3508 3509 mutex_enter(&mg->mg_lock); 3510 3511 /* 3512 * Load the next potential metaslabs 3513 */ 3514 for (msp = avl_first(t); msp != NULL; msp = AVL_NEXT(t, msp)) { 3515 ASSERT3P(msp->ms_group, ==, mg); 3516 3517 /* 3518 * We preload only the maximum number of metaslabs specified 3519 * by metaslab_preload_limit. If a metaslab is being forced 3520 * to condense then we preload it too. This will ensure 3521 * that force condensing happens in the next txg. 3522 */ 3523 if (++m > metaslab_preload_limit && !msp->ms_condense_wanted) { 3524 continue; 3525 } 3526 3527 VERIFY(taskq_dispatch(mg->mg_taskq, metaslab_preload, 3528 msp, TQ_SLEEP) != TASKQID_INVALID); 3529 } 3530 mutex_exit(&mg->mg_lock); 3531 } 3532 3533 /* 3534 * Determine if the space map's on-disk footprint is past our tolerance for 3535 * inefficiency. We would like to use the following criteria to make our 3536 * decision: 3537 * 3538 * 1. Do not condense if the size of the space map object would dramatically 3539 * increase as a result of writing out the free space range tree. 3540 * 3541 * 2. Condense if the on on-disk space map representation is at least 3542 * zfs_condense_pct/100 times the size of the optimal representation 3543 * (i.e. zfs_condense_pct = 110 and in-core = 1MB, optimal = 1.1MB). 3544 * 3545 * 3. Do not condense if the on-disk size of the space map does not actually 3546 * decrease. 3547 * 3548 * Unfortunately, we cannot compute the on-disk size of the space map in this 3549 * context because we cannot accurately compute the effects of compression, etc. 3550 * Instead, we apply the heuristic described in the block comment for 3551 * zfs_metaslab_condense_block_threshold - we only condense if the space used 3552 * is greater than a threshold number of blocks. 3553 */ 3554 static boolean_t 3555 metaslab_should_condense(metaslab_t *msp) 3556 { 3557 space_map_t *sm = msp->ms_sm; 3558 vdev_t *vd = msp->ms_group->mg_vd; 3559 uint64_t vdev_blocksize = 1 << vd->vdev_ashift; 3560 3561 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3562 ASSERT(msp->ms_loaded); 3563 ASSERT(sm != NULL); 3564 ASSERT3U(spa_sync_pass(vd->vdev_spa), ==, 1); 3565 3566 /* 3567 * We always condense metaslabs that are empty and metaslabs for 3568 * which a condense request has been made. 3569 */ 3570 if (range_tree_numsegs(msp->ms_allocatable) == 0 || 3571 msp->ms_condense_wanted) 3572 return (B_TRUE); 3573 3574 uint64_t record_size = MAX(sm->sm_blksz, vdev_blocksize); 3575 uint64_t object_size = space_map_length(sm); 3576 uint64_t optimal_size = space_map_estimate_optimal_size(sm, 3577 msp->ms_allocatable, SM_NO_VDEVID); 3578 3579 return (object_size >= (optimal_size * zfs_condense_pct / 100) && 3580 object_size > zfs_metaslab_condense_block_threshold * record_size); 3581 } 3582 3583 /* 3584 * Condense the on-disk space map representation to its minimized form. 3585 * The minimized form consists of a small number of allocations followed 3586 * by the entries of the free range tree (ms_allocatable). The condensed 3587 * spacemap contains all the entries of previous TXGs (including those in 3588 * the pool-wide log spacemaps; thus this is effectively a superset of 3589 * metaslab_flush()), but this TXG's entries still need to be written. 3590 */ 3591 static void 3592 metaslab_condense(metaslab_t *msp, dmu_tx_t *tx) 3593 { 3594 range_tree_t *condense_tree; 3595 space_map_t *sm = msp->ms_sm; 3596 uint64_t txg = dmu_tx_get_txg(tx); 3597 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 3598 3599 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3600 ASSERT(msp->ms_loaded); 3601 ASSERT(msp->ms_sm != NULL); 3602 3603 /* 3604 * In order to condense the space map, we need to change it so it 3605 * only describes which segments are currently allocated and free. 3606 * 3607 * All the current free space resides in the ms_allocatable, all 3608 * the ms_defer trees, and all the ms_allocating trees. We ignore 3609 * ms_freed because it is empty because we're in sync pass 1. We 3610 * ignore ms_freeing because these changes are not yet reflected 3611 * in the spacemap (they will be written later this txg). 3612 * 3613 * So to truncate the space map to represent all the entries of 3614 * previous TXGs we do the following: 3615 * 3616 * 1] We create a range tree (condense tree) that is 100% empty. 3617 * 2] We add to it all segments found in the ms_defer trees 3618 * as those segments are marked as free in the original space 3619 * map. We do the same with the ms_allocating trees for the same 3620 * reason. Adding these segments should be a relatively 3621 * inexpensive operation since we expect these trees to have a 3622 * small number of nodes. 3623 * 3] We vacate any unflushed allocs, since they are not frees we 3624 * need to add to the condense tree. Then we vacate any 3625 * unflushed frees as they should already be part of ms_allocatable. 3626 * 4] At this point, we would ideally like to add all segments 3627 * in the ms_allocatable tree from the condense tree. This way 3628 * we would write all the entries of the condense tree as the 3629 * condensed space map, which would only contain freed 3630 * segments with everything else assumed to be allocated. 3631 * 3632 * Doing so can be prohibitively expensive as ms_allocatable can 3633 * be large, and therefore computationally expensive to add to 3634 * the condense_tree. Instead we first sync out an entry marking 3635 * everything as allocated, then the condense_tree and then the 3636 * ms_allocatable, in the condensed space map. While this is not 3637 * optimal, it is typically close to optimal and more importantly 3638 * much cheaper to compute. 3639 * 3640 * 5] Finally, as both of the unflushed trees were written to our 3641 * new and condensed metaslab space map, we basically flushed 3642 * all the unflushed changes to disk, thus we call 3643 * metaslab_flush_update(). 3644 */ 3645 ASSERT3U(spa_sync_pass(spa), ==, 1); 3646 ASSERT(range_tree_is_empty(msp->ms_freed)); /* since it is pass 1 */ 3647 3648 zfs_dbgmsg("condensing: txg %llu, msp[%llu] %px, vdev id %llu, " 3649 "spa %s, smp size %llu, segments %llu, forcing condense=%s", 3650 (u_longlong_t)txg, (u_longlong_t)msp->ms_id, msp, 3651 (u_longlong_t)msp->ms_group->mg_vd->vdev_id, 3652 spa->spa_name, (u_longlong_t)space_map_length(msp->ms_sm), 3653 (u_longlong_t)range_tree_numsegs(msp->ms_allocatable), 3654 msp->ms_condense_wanted ? "TRUE" : "FALSE"); 3655 3656 msp->ms_condense_wanted = B_FALSE; 3657 3658 range_seg_type_t type; 3659 uint64_t shift, start; 3660 type = metaslab_calculate_range_tree_type(msp->ms_group->mg_vd, msp, 3661 &start, &shift); 3662 3663 condense_tree = range_tree_create(NULL, type, NULL, start, shift); 3664 3665 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 3666 range_tree_walk(msp->ms_defer[t], 3667 range_tree_add, condense_tree); 3668 } 3669 3670 for (int t = 0; t < TXG_CONCURRENT_STATES; t++) { 3671 range_tree_walk(msp->ms_allocating[(txg + t) & TXG_MASK], 3672 range_tree_add, condense_tree); 3673 } 3674 3675 ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=, 3676 metaslab_unflushed_changes_memused(msp)); 3677 spa->spa_unflushed_stats.sus_memused -= 3678 metaslab_unflushed_changes_memused(msp); 3679 range_tree_vacate(msp->ms_unflushed_allocs, NULL, NULL); 3680 range_tree_vacate(msp->ms_unflushed_frees, NULL, NULL); 3681 3682 /* 3683 * We're about to drop the metaslab's lock thus allowing other 3684 * consumers to change it's content. Set the metaslab's ms_condensing 3685 * flag to ensure that allocations on this metaslab do not occur 3686 * while we're in the middle of committing it to disk. This is only 3687 * critical for ms_allocatable as all other range trees use per TXG 3688 * views of their content. 3689 */ 3690 msp->ms_condensing = B_TRUE; 3691 3692 mutex_exit(&msp->ms_lock); 3693 uint64_t object = space_map_object(msp->ms_sm); 3694 space_map_truncate(sm, 3695 spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP) ? 3696 zfs_metaslab_sm_blksz_with_log : zfs_metaslab_sm_blksz_no_log, tx); 3697 3698 /* 3699 * space_map_truncate() may have reallocated the spacemap object. 3700 * If so, update the vdev_ms_array. 3701 */ 3702 if (space_map_object(msp->ms_sm) != object) { 3703 object = space_map_object(msp->ms_sm); 3704 dmu_write(spa->spa_meta_objset, 3705 msp->ms_group->mg_vd->vdev_ms_array, sizeof (uint64_t) * 3706 msp->ms_id, sizeof (uint64_t), &object, tx); 3707 } 3708 3709 /* 3710 * Note: 3711 * When the log space map feature is enabled, each space map will 3712 * always have ALLOCS followed by FREES for each sync pass. This is 3713 * typically true even when the log space map feature is disabled, 3714 * except from the case where a metaslab goes through metaslab_sync() 3715 * and gets condensed. In that case the metaslab's space map will have 3716 * ALLOCS followed by FREES (due to condensing) followed by ALLOCS 3717 * followed by FREES (due to space_map_write() in metaslab_sync()) for 3718 * sync pass 1. 3719 */ 3720 range_tree_t *tmp_tree = range_tree_create(NULL, type, NULL, start, 3721 shift); 3722 range_tree_add(tmp_tree, msp->ms_start, msp->ms_size); 3723 space_map_write(sm, tmp_tree, SM_ALLOC, SM_NO_VDEVID, tx); 3724 space_map_write(sm, msp->ms_allocatable, SM_FREE, SM_NO_VDEVID, tx); 3725 space_map_write(sm, condense_tree, SM_FREE, SM_NO_VDEVID, tx); 3726 3727 range_tree_vacate(condense_tree, NULL, NULL); 3728 range_tree_destroy(condense_tree); 3729 range_tree_vacate(tmp_tree, NULL, NULL); 3730 range_tree_destroy(tmp_tree); 3731 mutex_enter(&msp->ms_lock); 3732 3733 msp->ms_condensing = B_FALSE; 3734 metaslab_flush_update(msp, tx); 3735 } 3736 3737 /* 3738 * Called when the metaslab has been flushed (its own spacemap now reflects 3739 * all the contents of the pool-wide spacemap log). Updates the metaslab's 3740 * metadata and any pool-wide related log space map data (e.g. summary, 3741 * obsolete logs, etc..) to reflect that. 3742 */ 3743 static void 3744 metaslab_flush_update(metaslab_t *msp, dmu_tx_t *tx) 3745 { 3746 metaslab_group_t *mg = msp->ms_group; 3747 spa_t *spa = mg->mg_vd->vdev_spa; 3748 3749 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3750 3751 ASSERT3U(spa_sync_pass(spa), ==, 1); 3752 ASSERT(range_tree_is_empty(msp->ms_unflushed_allocs)); 3753 ASSERT(range_tree_is_empty(msp->ms_unflushed_frees)); 3754 3755 /* 3756 * Just because a metaslab got flushed, that doesn't mean that 3757 * it will pass through metaslab_sync_done(). Thus, make sure to 3758 * update ms_synced_length here in case it doesn't. 3759 */ 3760 msp->ms_synced_length = space_map_length(msp->ms_sm); 3761 3762 /* 3763 * We may end up here from metaslab_condense() without the 3764 * feature being active. In that case this is a no-op. 3765 */ 3766 if (!spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)) 3767 return; 3768 3769 ASSERT(spa_syncing_log_sm(spa) != NULL); 3770 ASSERT(msp->ms_sm != NULL); 3771 ASSERT(metaslab_unflushed_txg(msp) != 0); 3772 ASSERT3P(avl_find(&spa->spa_metaslabs_by_flushed, msp, NULL), ==, msp); 3773 3774 VERIFY3U(tx->tx_txg, <=, spa_final_dirty_txg(spa)); 3775 3776 /* update metaslab's position in our flushing tree */ 3777 uint64_t ms_prev_flushed_txg = metaslab_unflushed_txg(msp); 3778 mutex_enter(&spa->spa_flushed_ms_lock); 3779 avl_remove(&spa->spa_metaslabs_by_flushed, msp); 3780 metaslab_set_unflushed_txg(msp, spa_syncing_txg(spa), tx); 3781 avl_add(&spa->spa_metaslabs_by_flushed, msp); 3782 mutex_exit(&spa->spa_flushed_ms_lock); 3783 3784 /* update metaslab counts of spa_log_sm_t nodes */ 3785 spa_log_sm_decrement_mscount(spa, ms_prev_flushed_txg); 3786 spa_log_sm_increment_current_mscount(spa); 3787 3788 /* cleanup obsolete logs if any */ 3789 uint64_t log_blocks_before = spa_log_sm_nblocks(spa); 3790 spa_cleanup_old_sm_logs(spa, tx); 3791 uint64_t log_blocks_after = spa_log_sm_nblocks(spa); 3792 VERIFY3U(log_blocks_after, <=, log_blocks_before); 3793 3794 /* update log space map summary */ 3795 uint64_t blocks_gone = log_blocks_before - log_blocks_after; 3796 spa_log_summary_add_flushed_metaslab(spa); 3797 spa_log_summary_decrement_mscount(spa, ms_prev_flushed_txg); 3798 spa_log_summary_decrement_blkcount(spa, blocks_gone); 3799 } 3800 3801 boolean_t 3802 metaslab_flush(metaslab_t *msp, dmu_tx_t *tx) 3803 { 3804 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 3805 3806 ASSERT(MUTEX_HELD(&msp->ms_lock)); 3807 ASSERT3U(spa_sync_pass(spa), ==, 1); 3808 ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)); 3809 3810 ASSERT(msp->ms_sm != NULL); 3811 ASSERT(metaslab_unflushed_txg(msp) != 0); 3812 ASSERT(avl_find(&spa->spa_metaslabs_by_flushed, msp, NULL) != NULL); 3813 3814 /* 3815 * There is nothing wrong with flushing the same metaslab twice, as 3816 * this codepath should work on that case. However, the current 3817 * flushing scheme makes sure to avoid this situation as we would be 3818 * making all these calls without having anything meaningful to write 3819 * to disk. We assert this behavior here. 3820 */ 3821 ASSERT3U(metaslab_unflushed_txg(msp), <, dmu_tx_get_txg(tx)); 3822 3823 /* 3824 * We can not flush while loading, because then we would 3825 * not load the ms_unflushed_{allocs,frees}. 3826 */ 3827 if (msp->ms_loading) 3828 return (B_FALSE); 3829 3830 metaslab_verify_space(msp, dmu_tx_get_txg(tx)); 3831 metaslab_verify_weight_and_frag(msp); 3832 3833 /* 3834 * Metaslab condensing is effectively flushing. Therefore if the 3835 * metaslab can be condensed we can just condense it instead of 3836 * flushing it. 3837 * 3838 * Note that metaslab_condense() does call metaslab_flush_update() 3839 * so we can just return immediately after condensing. We also 3840 * don't need to care about setting ms_flushing or broadcasting 3841 * ms_flush_cv, even if we temporarily drop the ms_lock in 3842 * metaslab_condense(), as the metaslab is already loaded. 3843 */ 3844 if (msp->ms_loaded && metaslab_should_condense(msp)) { 3845 metaslab_group_t *mg = msp->ms_group; 3846 3847 /* 3848 * For all histogram operations below refer to the 3849 * comments of metaslab_sync() where we follow a 3850 * similar procedure. 3851 */ 3852 metaslab_group_histogram_verify(mg); 3853 metaslab_class_histogram_verify(mg->mg_class); 3854 metaslab_group_histogram_remove(mg, msp); 3855 3856 metaslab_condense(msp, tx); 3857 3858 space_map_histogram_clear(msp->ms_sm); 3859 space_map_histogram_add(msp->ms_sm, msp->ms_allocatable, tx); 3860 ASSERT(range_tree_is_empty(msp->ms_freed)); 3861 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 3862 space_map_histogram_add(msp->ms_sm, 3863 msp->ms_defer[t], tx); 3864 } 3865 metaslab_aux_histograms_update(msp); 3866 3867 metaslab_group_histogram_add(mg, msp); 3868 metaslab_group_histogram_verify(mg); 3869 metaslab_class_histogram_verify(mg->mg_class); 3870 3871 metaslab_verify_space(msp, dmu_tx_get_txg(tx)); 3872 3873 /* 3874 * Since we recreated the histogram (and potentially 3875 * the ms_sm too while condensing) ensure that the 3876 * weight is updated too because we are not guaranteed 3877 * that this metaslab is dirty and will go through 3878 * metaslab_sync_done(). 3879 */ 3880 metaslab_recalculate_weight_and_sort(msp); 3881 return (B_TRUE); 3882 } 3883 3884 msp->ms_flushing = B_TRUE; 3885 uint64_t sm_len_before = space_map_length(msp->ms_sm); 3886 3887 mutex_exit(&msp->ms_lock); 3888 space_map_write(msp->ms_sm, msp->ms_unflushed_allocs, SM_ALLOC, 3889 SM_NO_VDEVID, tx); 3890 space_map_write(msp->ms_sm, msp->ms_unflushed_frees, SM_FREE, 3891 SM_NO_VDEVID, tx); 3892 mutex_enter(&msp->ms_lock); 3893 3894 uint64_t sm_len_after = space_map_length(msp->ms_sm); 3895 if (zfs_flags & ZFS_DEBUG_LOG_SPACEMAP) { 3896 zfs_dbgmsg("flushing: txg %llu, spa %s, vdev_id %llu, " 3897 "ms_id %llu, unflushed_allocs %llu, unflushed_frees %llu, " 3898 "appended %llu bytes", (u_longlong_t)dmu_tx_get_txg(tx), 3899 spa_name(spa), 3900 (u_longlong_t)msp->ms_group->mg_vd->vdev_id, 3901 (u_longlong_t)msp->ms_id, 3902 (u_longlong_t)range_tree_space(msp->ms_unflushed_allocs), 3903 (u_longlong_t)range_tree_space(msp->ms_unflushed_frees), 3904 (u_longlong_t)(sm_len_after - sm_len_before)); 3905 } 3906 3907 ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=, 3908 metaslab_unflushed_changes_memused(msp)); 3909 spa->spa_unflushed_stats.sus_memused -= 3910 metaslab_unflushed_changes_memused(msp); 3911 range_tree_vacate(msp->ms_unflushed_allocs, NULL, NULL); 3912 range_tree_vacate(msp->ms_unflushed_frees, NULL, NULL); 3913 3914 metaslab_verify_space(msp, dmu_tx_get_txg(tx)); 3915 metaslab_verify_weight_and_frag(msp); 3916 3917 metaslab_flush_update(msp, tx); 3918 3919 metaslab_verify_space(msp, dmu_tx_get_txg(tx)); 3920 metaslab_verify_weight_and_frag(msp); 3921 3922 msp->ms_flushing = B_FALSE; 3923 cv_broadcast(&msp->ms_flush_cv); 3924 return (B_TRUE); 3925 } 3926 3927 /* 3928 * Write a metaslab to disk in the context of the specified transaction group. 3929 */ 3930 void 3931 metaslab_sync(metaslab_t *msp, uint64_t txg) 3932 { 3933 metaslab_group_t *mg = msp->ms_group; 3934 vdev_t *vd = mg->mg_vd; 3935 spa_t *spa = vd->vdev_spa; 3936 objset_t *mos = spa_meta_objset(spa); 3937 range_tree_t *alloctree = msp->ms_allocating[txg & TXG_MASK]; 3938 dmu_tx_t *tx; 3939 3940 ASSERT(!vd->vdev_ishole); 3941 3942 /* 3943 * This metaslab has just been added so there's no work to do now. 3944 */ 3945 if (msp->ms_new) { 3946 ASSERT0(range_tree_space(alloctree)); 3947 ASSERT0(range_tree_space(msp->ms_freeing)); 3948 ASSERT0(range_tree_space(msp->ms_freed)); 3949 ASSERT0(range_tree_space(msp->ms_checkpointing)); 3950 ASSERT0(range_tree_space(msp->ms_trim)); 3951 return; 3952 } 3953 3954 /* 3955 * Normally, we don't want to process a metaslab if there are no 3956 * allocations or frees to perform. However, if the metaslab is being 3957 * forced to condense, it's loaded and we're not beyond the final 3958 * dirty txg, we need to let it through. Not condensing beyond the 3959 * final dirty txg prevents an issue where metaslabs that need to be 3960 * condensed but were loaded for other reasons could cause a panic 3961 * here. By only checking the txg in that branch of the conditional, 3962 * we preserve the utility of the VERIFY statements in all other 3963 * cases. 3964 */ 3965 if (range_tree_is_empty(alloctree) && 3966 range_tree_is_empty(msp->ms_freeing) && 3967 range_tree_is_empty(msp->ms_checkpointing) && 3968 !(msp->ms_loaded && msp->ms_condense_wanted && 3969 txg <= spa_final_dirty_txg(spa))) 3970 return; 3971 3972 3973 VERIFY3U(txg, <=, spa_final_dirty_txg(spa)); 3974 3975 /* 3976 * The only state that can actually be changing concurrently 3977 * with metaslab_sync() is the metaslab's ms_allocatable. No 3978 * other thread can be modifying this txg's alloc, freeing, 3979 * freed, or space_map_phys_t. We drop ms_lock whenever we 3980 * could call into the DMU, because the DMU can call down to 3981 * us (e.g. via zio_free()) at any time. 3982 * 3983 * The spa_vdev_remove_thread() can be reading metaslab state 3984 * concurrently, and it is locked out by the ms_sync_lock. 3985 * Note that the ms_lock is insufficient for this, because it 3986 * is dropped by space_map_write(). 3987 */ 3988 tx = dmu_tx_create_assigned(spa_get_dsl(spa), txg); 3989 3990 /* 3991 * Generate a log space map if one doesn't exist already. 3992 */ 3993 spa_generate_syncing_log_sm(spa, tx); 3994 3995 if (msp->ms_sm == NULL) { 3996 uint64_t new_object = space_map_alloc(mos, 3997 spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP) ? 3998 zfs_metaslab_sm_blksz_with_log : 3999 zfs_metaslab_sm_blksz_no_log, tx); 4000 VERIFY3U(new_object, !=, 0); 4001 4002 dmu_write(mos, vd->vdev_ms_array, sizeof (uint64_t) * 4003 msp->ms_id, sizeof (uint64_t), &new_object, tx); 4004 4005 VERIFY0(space_map_open(&msp->ms_sm, mos, new_object, 4006 msp->ms_start, msp->ms_size, vd->vdev_ashift)); 4007 ASSERT(msp->ms_sm != NULL); 4008 4009 ASSERT(range_tree_is_empty(msp->ms_unflushed_allocs)); 4010 ASSERT(range_tree_is_empty(msp->ms_unflushed_frees)); 4011 ASSERT0(metaslab_allocated_space(msp)); 4012 } 4013 4014 if (metaslab_unflushed_txg(msp) == 0 && 4015 spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)) { 4016 ASSERT(spa_syncing_log_sm(spa) != NULL); 4017 4018 metaslab_set_unflushed_txg(msp, spa_syncing_txg(spa), tx); 4019 spa_log_sm_increment_current_mscount(spa); 4020 spa_log_summary_add_flushed_metaslab(spa); 4021 4022 ASSERT(msp->ms_sm != NULL); 4023 mutex_enter(&spa->spa_flushed_ms_lock); 4024 avl_add(&spa->spa_metaslabs_by_flushed, msp); 4025 mutex_exit(&spa->spa_flushed_ms_lock); 4026 4027 ASSERT(range_tree_is_empty(msp->ms_unflushed_allocs)); 4028 ASSERT(range_tree_is_empty(msp->ms_unflushed_frees)); 4029 } 4030 4031 if (!range_tree_is_empty(msp->ms_checkpointing) && 4032 vd->vdev_checkpoint_sm == NULL) { 4033 ASSERT(spa_has_checkpoint(spa)); 4034 4035 uint64_t new_object = space_map_alloc(mos, 4036 zfs_vdev_standard_sm_blksz, tx); 4037 VERIFY3U(new_object, !=, 0); 4038 4039 VERIFY0(space_map_open(&vd->vdev_checkpoint_sm, 4040 mos, new_object, 0, vd->vdev_asize, vd->vdev_ashift)); 4041 ASSERT3P(vd->vdev_checkpoint_sm, !=, NULL); 4042 4043 /* 4044 * We save the space map object as an entry in vdev_top_zap 4045 * so it can be retrieved when the pool is reopened after an 4046 * export or through zdb. 4047 */ 4048 VERIFY0(zap_add(vd->vdev_spa->spa_meta_objset, 4049 vd->vdev_top_zap, VDEV_TOP_ZAP_POOL_CHECKPOINT_SM, 4050 sizeof (new_object), 1, &new_object, tx)); 4051 } 4052 4053 mutex_enter(&msp->ms_sync_lock); 4054 mutex_enter(&msp->ms_lock); 4055 4056 /* 4057 * Note: metaslab_condense() clears the space map's histogram. 4058 * Therefore we must verify and remove this histogram before 4059 * condensing. 4060 */ 4061 metaslab_group_histogram_verify(mg); 4062 metaslab_class_histogram_verify(mg->mg_class); 4063 metaslab_group_histogram_remove(mg, msp); 4064 4065 if (spa->spa_sync_pass == 1 && msp->ms_loaded && 4066 metaslab_should_condense(msp)) 4067 metaslab_condense(msp, tx); 4068 4069 /* 4070 * We'll be going to disk to sync our space accounting, thus we 4071 * drop the ms_lock during that time so allocations coming from 4072 * open-context (ZIL) for future TXGs do not block. 4073 */ 4074 mutex_exit(&msp->ms_lock); 4075 space_map_t *log_sm = spa_syncing_log_sm(spa); 4076 if (log_sm != NULL) { 4077 ASSERT(spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP)); 4078 4079 space_map_write(log_sm, alloctree, SM_ALLOC, 4080 vd->vdev_id, tx); 4081 space_map_write(log_sm, msp->ms_freeing, SM_FREE, 4082 vd->vdev_id, tx); 4083 mutex_enter(&msp->ms_lock); 4084 4085 ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=, 4086 metaslab_unflushed_changes_memused(msp)); 4087 spa->spa_unflushed_stats.sus_memused -= 4088 metaslab_unflushed_changes_memused(msp); 4089 range_tree_remove_xor_add(alloctree, 4090 msp->ms_unflushed_frees, msp->ms_unflushed_allocs); 4091 range_tree_remove_xor_add(msp->ms_freeing, 4092 msp->ms_unflushed_allocs, msp->ms_unflushed_frees); 4093 spa->spa_unflushed_stats.sus_memused += 4094 metaslab_unflushed_changes_memused(msp); 4095 } else { 4096 ASSERT(!spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP)); 4097 4098 space_map_write(msp->ms_sm, alloctree, SM_ALLOC, 4099 SM_NO_VDEVID, tx); 4100 space_map_write(msp->ms_sm, msp->ms_freeing, SM_FREE, 4101 SM_NO_VDEVID, tx); 4102 mutex_enter(&msp->ms_lock); 4103 } 4104 4105 msp->ms_allocated_space += range_tree_space(alloctree); 4106 ASSERT3U(msp->ms_allocated_space, >=, 4107 range_tree_space(msp->ms_freeing)); 4108 msp->ms_allocated_space -= range_tree_space(msp->ms_freeing); 4109 4110 if (!range_tree_is_empty(msp->ms_checkpointing)) { 4111 ASSERT(spa_has_checkpoint(spa)); 4112 ASSERT3P(vd->vdev_checkpoint_sm, !=, NULL); 4113 4114 /* 4115 * Since we are doing writes to disk and the ms_checkpointing 4116 * tree won't be changing during that time, we drop the 4117 * ms_lock while writing to the checkpoint space map, for the 4118 * same reason mentioned above. 4119 */ 4120 mutex_exit(&msp->ms_lock); 4121 space_map_write(vd->vdev_checkpoint_sm, 4122 msp->ms_checkpointing, SM_FREE, SM_NO_VDEVID, tx); 4123 mutex_enter(&msp->ms_lock); 4124 4125 spa->spa_checkpoint_info.sci_dspace += 4126 range_tree_space(msp->ms_checkpointing); 4127 vd->vdev_stat.vs_checkpoint_space += 4128 range_tree_space(msp->ms_checkpointing); 4129 ASSERT3U(vd->vdev_stat.vs_checkpoint_space, ==, 4130 -space_map_allocated(vd->vdev_checkpoint_sm)); 4131 4132 range_tree_vacate(msp->ms_checkpointing, NULL, NULL); 4133 } 4134 4135 if (msp->ms_loaded) { 4136 /* 4137 * When the space map is loaded, we have an accurate 4138 * histogram in the range tree. This gives us an opportunity 4139 * to bring the space map's histogram up-to-date so we clear 4140 * it first before updating it. 4141 */ 4142 space_map_histogram_clear(msp->ms_sm); 4143 space_map_histogram_add(msp->ms_sm, msp->ms_allocatable, tx); 4144 4145 /* 4146 * Since we've cleared the histogram we need to add back 4147 * any free space that has already been processed, plus 4148 * any deferred space. This allows the on-disk histogram 4149 * to accurately reflect all free space even if some space 4150 * is not yet available for allocation (i.e. deferred). 4151 */ 4152 space_map_histogram_add(msp->ms_sm, msp->ms_freed, tx); 4153 4154 /* 4155 * Add back any deferred free space that has not been 4156 * added back into the in-core free tree yet. This will 4157 * ensure that we don't end up with a space map histogram 4158 * that is completely empty unless the metaslab is fully 4159 * allocated. 4160 */ 4161 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 4162 space_map_histogram_add(msp->ms_sm, 4163 msp->ms_defer[t], tx); 4164 } 4165 } 4166 4167 /* 4168 * Always add the free space from this sync pass to the space 4169 * map histogram. We want to make sure that the on-disk histogram 4170 * accounts for all free space. If the space map is not loaded, 4171 * then we will lose some accuracy but will correct it the next 4172 * time we load the space map. 4173 */ 4174 space_map_histogram_add(msp->ms_sm, msp->ms_freeing, tx); 4175 metaslab_aux_histograms_update(msp); 4176 4177 metaslab_group_histogram_add(mg, msp); 4178 metaslab_group_histogram_verify(mg); 4179 metaslab_class_histogram_verify(mg->mg_class); 4180 4181 /* 4182 * For sync pass 1, we avoid traversing this txg's free range tree 4183 * and instead will just swap the pointers for freeing and freed. 4184 * We can safely do this since the freed_tree is guaranteed to be 4185 * empty on the initial pass. 4186 * 4187 * Keep in mind that even if we are currently using a log spacemap 4188 * we want current frees to end up in the ms_allocatable (but not 4189 * get appended to the ms_sm) so their ranges can be reused as usual. 4190 */ 4191 if (spa_sync_pass(spa) == 1) { 4192 range_tree_swap(&msp->ms_freeing, &msp->ms_freed); 4193 ASSERT0(msp->ms_allocated_this_txg); 4194 } else { 4195 range_tree_vacate(msp->ms_freeing, 4196 range_tree_add, msp->ms_freed); 4197 } 4198 msp->ms_allocated_this_txg += range_tree_space(alloctree); 4199 range_tree_vacate(alloctree, NULL, NULL); 4200 4201 ASSERT0(range_tree_space(msp->ms_allocating[txg & TXG_MASK])); 4202 ASSERT0(range_tree_space(msp->ms_allocating[TXG_CLEAN(txg) 4203 & TXG_MASK])); 4204 ASSERT0(range_tree_space(msp->ms_freeing)); 4205 ASSERT0(range_tree_space(msp->ms_checkpointing)); 4206 4207 mutex_exit(&msp->ms_lock); 4208 4209 /* 4210 * Verify that the space map object ID has been recorded in the 4211 * vdev_ms_array. 4212 */ 4213 uint64_t object; 4214 VERIFY0(dmu_read(mos, vd->vdev_ms_array, 4215 msp->ms_id * sizeof (uint64_t), sizeof (uint64_t), &object, 0)); 4216 VERIFY3U(object, ==, space_map_object(msp->ms_sm)); 4217 4218 mutex_exit(&msp->ms_sync_lock); 4219 dmu_tx_commit(tx); 4220 } 4221 4222 static void 4223 metaslab_evict(metaslab_t *msp, uint64_t txg) 4224 { 4225 if (!msp->ms_loaded || msp->ms_disabled != 0) 4226 return; 4227 4228 for (int t = 1; t < TXG_CONCURRENT_STATES; t++) { 4229 VERIFY0(range_tree_space( 4230 msp->ms_allocating[(txg + t) & TXG_MASK])); 4231 } 4232 if (msp->ms_allocator != -1) 4233 metaslab_passivate(msp, msp->ms_weight & ~METASLAB_ACTIVE_MASK); 4234 4235 if (!metaslab_debug_unload) 4236 metaslab_unload(msp); 4237 } 4238 4239 /* 4240 * Called after a transaction group has completely synced to mark 4241 * all of the metaslab's free space as usable. 4242 */ 4243 void 4244 metaslab_sync_done(metaslab_t *msp, uint64_t txg) 4245 { 4246 metaslab_group_t *mg = msp->ms_group; 4247 vdev_t *vd = mg->mg_vd; 4248 spa_t *spa = vd->vdev_spa; 4249 range_tree_t **defer_tree; 4250 int64_t alloc_delta, defer_delta; 4251 boolean_t defer_allowed = B_TRUE; 4252 4253 ASSERT(!vd->vdev_ishole); 4254 4255 mutex_enter(&msp->ms_lock); 4256 4257 if (msp->ms_new) { 4258 /* this is a new metaslab, add its capacity to the vdev */ 4259 metaslab_space_update(vd, mg->mg_class, 0, 0, msp->ms_size); 4260 4261 /* there should be no allocations nor frees at this point */ 4262 VERIFY0(msp->ms_allocated_this_txg); 4263 VERIFY0(range_tree_space(msp->ms_freed)); 4264 } 4265 4266 ASSERT0(range_tree_space(msp->ms_freeing)); 4267 ASSERT0(range_tree_space(msp->ms_checkpointing)); 4268 4269 defer_tree = &msp->ms_defer[txg % TXG_DEFER_SIZE]; 4270 4271 uint64_t free_space = metaslab_class_get_space(spa_normal_class(spa)) - 4272 metaslab_class_get_alloc(spa_normal_class(spa)); 4273 if (free_space <= spa_get_slop_space(spa) || vd->vdev_removing) { 4274 defer_allowed = B_FALSE; 4275 } 4276 4277 defer_delta = 0; 4278 alloc_delta = msp->ms_allocated_this_txg - 4279 range_tree_space(msp->ms_freed); 4280 4281 if (defer_allowed) { 4282 defer_delta = range_tree_space(msp->ms_freed) - 4283 range_tree_space(*defer_tree); 4284 } else { 4285 defer_delta -= range_tree_space(*defer_tree); 4286 } 4287 metaslab_space_update(vd, mg->mg_class, alloc_delta + defer_delta, 4288 defer_delta, 0); 4289 4290 if (spa_syncing_log_sm(spa) == NULL) { 4291 /* 4292 * If there's a metaslab_load() in progress and we don't have 4293 * a log space map, it means that we probably wrote to the 4294 * metaslab's space map. If this is the case, we need to 4295 * make sure that we wait for the load to complete so that we 4296 * have a consistent view at the in-core side of the metaslab. 4297 */ 4298 metaslab_load_wait(msp); 4299 } else { 4300 ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)); 4301 } 4302 4303 /* 4304 * When auto-trimming is enabled, free ranges which are added to 4305 * ms_allocatable are also be added to ms_trim. The ms_trim tree is 4306 * periodically consumed by the vdev_autotrim_thread() which issues 4307 * trims for all ranges and then vacates the tree. The ms_trim tree 4308 * can be discarded at any time with the sole consequence of recent 4309 * frees not being trimmed. 4310 */ 4311 if (spa_get_autotrim(spa) == SPA_AUTOTRIM_ON) { 4312 range_tree_walk(*defer_tree, range_tree_add, msp->ms_trim); 4313 if (!defer_allowed) { 4314 range_tree_walk(msp->ms_freed, range_tree_add, 4315 msp->ms_trim); 4316 } 4317 } else { 4318 range_tree_vacate(msp->ms_trim, NULL, NULL); 4319 } 4320 4321 /* 4322 * Move the frees from the defer_tree back to the free 4323 * range tree (if it's loaded). Swap the freed_tree and 4324 * the defer_tree -- this is safe to do because we've 4325 * just emptied out the defer_tree. 4326 */ 4327 range_tree_vacate(*defer_tree, 4328 msp->ms_loaded ? range_tree_add : NULL, msp->ms_allocatable); 4329 if (defer_allowed) { 4330 range_tree_swap(&msp->ms_freed, defer_tree); 4331 } else { 4332 range_tree_vacate(msp->ms_freed, 4333 msp->ms_loaded ? range_tree_add : NULL, 4334 msp->ms_allocatable); 4335 } 4336 4337 msp->ms_synced_length = space_map_length(msp->ms_sm); 4338 4339 msp->ms_deferspace += defer_delta; 4340 ASSERT3S(msp->ms_deferspace, >=, 0); 4341 ASSERT3S(msp->ms_deferspace, <=, msp->ms_size); 4342 if (msp->ms_deferspace != 0) { 4343 /* 4344 * Keep syncing this metaslab until all deferred frees 4345 * are back in circulation. 4346 */ 4347 vdev_dirty(vd, VDD_METASLAB, msp, txg + 1); 4348 } 4349 metaslab_aux_histograms_update_done(msp, defer_allowed); 4350 4351 if (msp->ms_new) { 4352 msp->ms_new = B_FALSE; 4353 mutex_enter(&mg->mg_lock); 4354 mg->mg_ms_ready++; 4355 mutex_exit(&mg->mg_lock); 4356 } 4357 4358 /* 4359 * Re-sort metaslab within its group now that we've adjusted 4360 * its allocatable space. 4361 */ 4362 metaslab_recalculate_weight_and_sort(msp); 4363 4364 ASSERT0(range_tree_space(msp->ms_allocating[txg & TXG_MASK])); 4365 ASSERT0(range_tree_space(msp->ms_freeing)); 4366 ASSERT0(range_tree_space(msp->ms_freed)); 4367 ASSERT0(range_tree_space(msp->ms_checkpointing)); 4368 msp->ms_allocating_total -= msp->ms_allocated_this_txg; 4369 msp->ms_allocated_this_txg = 0; 4370 mutex_exit(&msp->ms_lock); 4371 } 4372 4373 void 4374 metaslab_sync_reassess(metaslab_group_t *mg) 4375 { 4376 spa_t *spa = mg->mg_class->mc_spa; 4377 4378 spa_config_enter(spa, SCL_ALLOC, FTAG, RW_READER); 4379 metaslab_group_alloc_update(mg); 4380 mg->mg_fragmentation = metaslab_group_fragmentation(mg); 4381 4382 /* 4383 * Preload the next potential metaslabs but only on active 4384 * metaslab groups. We can get into a state where the metaslab 4385 * is no longer active since we dirty metaslabs as we remove a 4386 * a device, thus potentially making the metaslab group eligible 4387 * for preloading. 4388 */ 4389 if (mg->mg_activation_count > 0) { 4390 metaslab_group_preload(mg); 4391 } 4392 spa_config_exit(spa, SCL_ALLOC, FTAG); 4393 } 4394 4395 /* 4396 * When writing a ditto block (i.e. more than one DVA for a given BP) on 4397 * the same vdev as an existing DVA of this BP, then try to allocate it 4398 * on a different metaslab than existing DVAs (i.e. a unique metaslab). 4399 */ 4400 static boolean_t 4401 metaslab_is_unique(metaslab_t *msp, dva_t *dva) 4402 { 4403 uint64_t dva_ms_id; 4404 4405 if (DVA_GET_ASIZE(dva) == 0) 4406 return (B_TRUE); 4407 4408 if (msp->ms_group->mg_vd->vdev_id != DVA_GET_VDEV(dva)) 4409 return (B_TRUE); 4410 4411 dva_ms_id = DVA_GET_OFFSET(dva) >> msp->ms_group->mg_vd->vdev_ms_shift; 4412 4413 return (msp->ms_id != dva_ms_id); 4414 } 4415 4416 /* 4417 * ========================================================================== 4418 * Metaslab allocation tracing facility 4419 * ========================================================================== 4420 */ 4421 4422 /* 4423 * Add an allocation trace element to the allocation tracing list. 4424 */ 4425 static void 4426 metaslab_trace_add(zio_alloc_list_t *zal, metaslab_group_t *mg, 4427 metaslab_t *msp, uint64_t psize, uint32_t dva_id, uint64_t offset, 4428 int allocator) 4429 { 4430 metaslab_alloc_trace_t *mat; 4431 4432 if (!metaslab_trace_enabled) 4433 return; 4434 4435 /* 4436 * When the tracing list reaches its maximum we remove 4437 * the second element in the list before adding a new one. 4438 * By removing the second element we preserve the original 4439 * entry as a clue to what allocations steps have already been 4440 * performed. 4441 */ 4442 if (zal->zal_size == metaslab_trace_max_entries) { 4443 metaslab_alloc_trace_t *mat_next; 4444 #ifdef ZFS_DEBUG 4445 panic("too many entries in allocation list"); 4446 #endif 4447 METASLABSTAT_BUMP(metaslabstat_trace_over_limit); 4448 zal->zal_size--; 4449 mat_next = list_next(&zal->zal_list, list_head(&zal->zal_list)); 4450 list_remove(&zal->zal_list, mat_next); 4451 kmem_cache_free(metaslab_alloc_trace_cache, mat_next); 4452 } 4453 4454 mat = kmem_cache_alloc(metaslab_alloc_trace_cache, KM_SLEEP); 4455 list_link_init(&mat->mat_list_node); 4456 mat->mat_mg = mg; 4457 mat->mat_msp = msp; 4458 mat->mat_size = psize; 4459 mat->mat_dva_id = dva_id; 4460 mat->mat_offset = offset; 4461 mat->mat_weight = 0; 4462 mat->mat_allocator = allocator; 4463 4464 if (msp != NULL) 4465 mat->mat_weight = msp->ms_weight; 4466 4467 /* 4468 * The list is part of the zio so locking is not required. Only 4469 * a single thread will perform allocations for a given zio. 4470 */ 4471 list_insert_tail(&zal->zal_list, mat); 4472 zal->zal_size++; 4473 4474 ASSERT3U(zal->zal_size, <=, metaslab_trace_max_entries); 4475 } 4476 4477 void 4478 metaslab_trace_init(zio_alloc_list_t *zal) 4479 { 4480 list_create(&zal->zal_list, sizeof (metaslab_alloc_trace_t), 4481 offsetof(metaslab_alloc_trace_t, mat_list_node)); 4482 zal->zal_size = 0; 4483 } 4484 4485 void 4486 metaslab_trace_fini(zio_alloc_list_t *zal) 4487 { 4488 metaslab_alloc_trace_t *mat; 4489 4490 while ((mat = list_remove_head(&zal->zal_list)) != NULL) 4491 kmem_cache_free(metaslab_alloc_trace_cache, mat); 4492 list_destroy(&zal->zal_list); 4493 zal->zal_size = 0; 4494 } 4495 4496 /* 4497 * ========================================================================== 4498 * Metaslab block operations 4499 * ========================================================================== 4500 */ 4501 4502 static void 4503 metaslab_group_alloc_increment(spa_t *spa, uint64_t vdev, void *tag, int flags, 4504 int allocator) 4505 { 4506 if (!(flags & METASLAB_ASYNC_ALLOC) || 4507 (flags & METASLAB_DONT_THROTTLE)) 4508 return; 4509 4510 metaslab_group_t *mg = vdev_lookup_top(spa, vdev)->vdev_mg; 4511 if (!mg->mg_class->mc_alloc_throttle_enabled) 4512 return; 4513 4514 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 4515 (void) zfs_refcount_add(&mga->mga_alloc_queue_depth, tag); 4516 } 4517 4518 static void 4519 metaslab_group_increment_qdepth(metaslab_group_t *mg, int allocator) 4520 { 4521 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 4522 metaslab_class_allocator_t *mca = 4523 &mg->mg_class->mc_allocator[allocator]; 4524 uint64_t max = mg->mg_max_alloc_queue_depth; 4525 uint64_t cur = mga->mga_cur_max_alloc_queue_depth; 4526 while (cur < max) { 4527 if (atomic_cas_64(&mga->mga_cur_max_alloc_queue_depth, 4528 cur, cur + 1) == cur) { 4529 atomic_inc_64(&mca->mca_alloc_max_slots); 4530 return; 4531 } 4532 cur = mga->mga_cur_max_alloc_queue_depth; 4533 } 4534 } 4535 4536 void 4537 metaslab_group_alloc_decrement(spa_t *spa, uint64_t vdev, void *tag, int flags, 4538 int allocator, boolean_t io_complete) 4539 { 4540 if (!(flags & METASLAB_ASYNC_ALLOC) || 4541 (flags & METASLAB_DONT_THROTTLE)) 4542 return; 4543 4544 metaslab_group_t *mg = vdev_lookup_top(spa, vdev)->vdev_mg; 4545 if (!mg->mg_class->mc_alloc_throttle_enabled) 4546 return; 4547 4548 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 4549 (void) zfs_refcount_remove(&mga->mga_alloc_queue_depth, tag); 4550 if (io_complete) 4551 metaslab_group_increment_qdepth(mg, allocator); 4552 } 4553 4554 void 4555 metaslab_group_alloc_verify(spa_t *spa, const blkptr_t *bp, void *tag, 4556 int allocator) 4557 { 4558 #ifdef ZFS_DEBUG 4559 const dva_t *dva = bp->blk_dva; 4560 int ndvas = BP_GET_NDVAS(bp); 4561 4562 for (int d = 0; d < ndvas; d++) { 4563 uint64_t vdev = DVA_GET_VDEV(&dva[d]); 4564 metaslab_group_t *mg = vdev_lookup_top(spa, vdev)->vdev_mg; 4565 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 4566 VERIFY(zfs_refcount_not_held(&mga->mga_alloc_queue_depth, tag)); 4567 } 4568 #endif 4569 } 4570 4571 static uint64_t 4572 metaslab_block_alloc(metaslab_t *msp, uint64_t size, uint64_t txg) 4573 { 4574 uint64_t start; 4575 range_tree_t *rt = msp->ms_allocatable; 4576 metaslab_class_t *mc = msp->ms_group->mg_class; 4577 4578 ASSERT(MUTEX_HELD(&msp->ms_lock)); 4579 VERIFY(!msp->ms_condensing); 4580 VERIFY0(msp->ms_disabled); 4581 4582 start = mc->mc_ops->msop_alloc(msp, size); 4583 if (start != -1ULL) { 4584 metaslab_group_t *mg = msp->ms_group; 4585 vdev_t *vd = mg->mg_vd; 4586 4587 VERIFY0(P2PHASE(start, 1ULL << vd->vdev_ashift)); 4588 VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift)); 4589 VERIFY3U(range_tree_space(rt) - size, <=, msp->ms_size); 4590 range_tree_remove(rt, start, size); 4591 range_tree_clear(msp->ms_trim, start, size); 4592 4593 if (range_tree_is_empty(msp->ms_allocating[txg & TXG_MASK])) 4594 vdev_dirty(mg->mg_vd, VDD_METASLAB, msp, txg); 4595 4596 range_tree_add(msp->ms_allocating[txg & TXG_MASK], start, size); 4597 msp->ms_allocating_total += size; 4598 4599 /* Track the last successful allocation */ 4600 msp->ms_alloc_txg = txg; 4601 metaslab_verify_space(msp, txg); 4602 } 4603 4604 /* 4605 * Now that we've attempted the allocation we need to update the 4606 * metaslab's maximum block size since it may have changed. 4607 */ 4608 msp->ms_max_size = metaslab_largest_allocatable(msp); 4609 return (start); 4610 } 4611 4612 /* 4613 * Find the metaslab with the highest weight that is less than what we've 4614 * already tried. In the common case, this means that we will examine each 4615 * metaslab at most once. Note that concurrent callers could reorder metaslabs 4616 * by activation/passivation once we have dropped the mg_lock. If a metaslab is 4617 * activated by another thread, and we fail to allocate from the metaslab we 4618 * have selected, we may not try the newly-activated metaslab, and instead 4619 * activate another metaslab. This is not optimal, but generally does not cause 4620 * any problems (a possible exception being if every metaslab is completely full 4621 * except for the newly-activated metaslab which we fail to examine). 4622 */ 4623 static metaslab_t * 4624 find_valid_metaslab(metaslab_group_t *mg, uint64_t activation_weight, 4625 dva_t *dva, int d, boolean_t want_unique, uint64_t asize, int allocator, 4626 boolean_t try_hard, zio_alloc_list_t *zal, metaslab_t *search, 4627 boolean_t *was_active) 4628 { 4629 avl_index_t idx; 4630 avl_tree_t *t = &mg->mg_metaslab_tree; 4631 metaslab_t *msp = avl_find(t, search, &idx); 4632 if (msp == NULL) 4633 msp = avl_nearest(t, idx, AVL_AFTER); 4634 4635 int tries = 0; 4636 for (; msp != NULL; msp = AVL_NEXT(t, msp)) { 4637 int i; 4638 4639 if (!try_hard && tries > zfs_metaslab_find_max_tries) { 4640 METASLABSTAT_BUMP(metaslabstat_too_many_tries); 4641 return (NULL); 4642 } 4643 tries++; 4644 4645 if (!metaslab_should_allocate(msp, asize, try_hard)) { 4646 metaslab_trace_add(zal, mg, msp, asize, d, 4647 TRACE_TOO_SMALL, allocator); 4648 continue; 4649 } 4650 4651 /* 4652 * If the selected metaslab is condensing or disabled, 4653 * skip it. 4654 */ 4655 if (msp->ms_condensing || msp->ms_disabled > 0) 4656 continue; 4657 4658 *was_active = msp->ms_allocator != -1; 4659 /* 4660 * If we're activating as primary, this is our first allocation 4661 * from this disk, so we don't need to check how close we are. 4662 * If the metaslab under consideration was already active, 4663 * we're getting desperate enough to steal another allocator's 4664 * metaslab, so we still don't care about distances. 4665 */ 4666 if (activation_weight == METASLAB_WEIGHT_PRIMARY || *was_active) 4667 break; 4668 4669 for (i = 0; i < d; i++) { 4670 if (want_unique && 4671 !metaslab_is_unique(msp, &dva[i])) 4672 break; /* try another metaslab */ 4673 } 4674 if (i == d) 4675 break; 4676 } 4677 4678 if (msp != NULL) { 4679 search->ms_weight = msp->ms_weight; 4680 search->ms_start = msp->ms_start + 1; 4681 search->ms_allocator = msp->ms_allocator; 4682 search->ms_primary = msp->ms_primary; 4683 } 4684 return (msp); 4685 } 4686 4687 static void 4688 metaslab_active_mask_verify(metaslab_t *msp) 4689 { 4690 ASSERT(MUTEX_HELD(&msp->ms_lock)); 4691 4692 if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0) 4693 return; 4694 4695 if ((msp->ms_weight & METASLAB_ACTIVE_MASK) == 0) 4696 return; 4697 4698 if (msp->ms_weight & METASLAB_WEIGHT_PRIMARY) { 4699 VERIFY0(msp->ms_weight & METASLAB_WEIGHT_SECONDARY); 4700 VERIFY0(msp->ms_weight & METASLAB_WEIGHT_CLAIM); 4701 VERIFY3S(msp->ms_allocator, !=, -1); 4702 VERIFY(msp->ms_primary); 4703 return; 4704 } 4705 4706 if (msp->ms_weight & METASLAB_WEIGHT_SECONDARY) { 4707 VERIFY0(msp->ms_weight & METASLAB_WEIGHT_PRIMARY); 4708 VERIFY0(msp->ms_weight & METASLAB_WEIGHT_CLAIM); 4709 VERIFY3S(msp->ms_allocator, !=, -1); 4710 VERIFY(!msp->ms_primary); 4711 return; 4712 } 4713 4714 if (msp->ms_weight & METASLAB_WEIGHT_CLAIM) { 4715 VERIFY0(msp->ms_weight & METASLAB_WEIGHT_PRIMARY); 4716 VERIFY0(msp->ms_weight & METASLAB_WEIGHT_SECONDARY); 4717 VERIFY3S(msp->ms_allocator, ==, -1); 4718 return; 4719 } 4720 } 4721 4722 /* ARGSUSED */ 4723 static uint64_t 4724 metaslab_group_alloc_normal(metaslab_group_t *mg, zio_alloc_list_t *zal, 4725 uint64_t asize, uint64_t txg, boolean_t want_unique, dva_t *dva, int d, 4726 int allocator, boolean_t try_hard) 4727 { 4728 metaslab_t *msp = NULL; 4729 uint64_t offset = -1ULL; 4730 4731 uint64_t activation_weight = METASLAB_WEIGHT_PRIMARY; 4732 for (int i = 0; i < d; i++) { 4733 if (activation_weight == METASLAB_WEIGHT_PRIMARY && 4734 DVA_GET_VDEV(&dva[i]) == mg->mg_vd->vdev_id) { 4735 activation_weight = METASLAB_WEIGHT_SECONDARY; 4736 } else if (activation_weight == METASLAB_WEIGHT_SECONDARY && 4737 DVA_GET_VDEV(&dva[i]) == mg->mg_vd->vdev_id) { 4738 activation_weight = METASLAB_WEIGHT_CLAIM; 4739 break; 4740 } 4741 } 4742 4743 /* 4744 * If we don't have enough metaslabs active to fill the entire array, we 4745 * just use the 0th slot. 4746 */ 4747 if (mg->mg_ms_ready < mg->mg_allocators * 3) 4748 allocator = 0; 4749 metaslab_group_allocator_t *mga = &mg->mg_allocator[allocator]; 4750 4751 ASSERT3U(mg->mg_vd->vdev_ms_count, >=, 2); 4752 4753 metaslab_t *search = kmem_alloc(sizeof (*search), KM_SLEEP); 4754 search->ms_weight = UINT64_MAX; 4755 search->ms_start = 0; 4756 /* 4757 * At the end of the metaslab tree are the already-active metaslabs, 4758 * first the primaries, then the secondaries. When we resume searching 4759 * through the tree, we need to consider ms_allocator and ms_primary so 4760 * we start in the location right after where we left off, and don't 4761 * accidentally loop forever considering the same metaslabs. 4762 */ 4763 search->ms_allocator = -1; 4764 search->ms_primary = B_TRUE; 4765 for (;;) { 4766 boolean_t was_active = B_FALSE; 4767 4768 mutex_enter(&mg->mg_lock); 4769 4770 if (activation_weight == METASLAB_WEIGHT_PRIMARY && 4771 mga->mga_primary != NULL) { 4772 msp = mga->mga_primary; 4773 4774 /* 4775 * Even though we don't hold the ms_lock for the 4776 * primary metaslab, those fields should not 4777 * change while we hold the mg_lock. Thus it is 4778 * safe to make assertions on them. 4779 */ 4780 ASSERT(msp->ms_primary); 4781 ASSERT3S(msp->ms_allocator, ==, allocator); 4782 ASSERT(msp->ms_loaded); 4783 4784 was_active = B_TRUE; 4785 ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK); 4786 } else if (activation_weight == METASLAB_WEIGHT_SECONDARY && 4787 mga->mga_secondary != NULL) { 4788 msp = mga->mga_secondary; 4789 4790 /* 4791 * See comment above about the similar assertions 4792 * for the primary metaslab. 4793 */ 4794 ASSERT(!msp->ms_primary); 4795 ASSERT3S(msp->ms_allocator, ==, allocator); 4796 ASSERT(msp->ms_loaded); 4797 4798 was_active = B_TRUE; 4799 ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK); 4800 } else { 4801 msp = find_valid_metaslab(mg, activation_weight, dva, d, 4802 want_unique, asize, allocator, try_hard, zal, 4803 search, &was_active); 4804 } 4805 4806 mutex_exit(&mg->mg_lock); 4807 if (msp == NULL) { 4808 kmem_free(search, sizeof (*search)); 4809 return (-1ULL); 4810 } 4811 mutex_enter(&msp->ms_lock); 4812 4813 metaslab_active_mask_verify(msp); 4814 4815 /* 4816 * This code is disabled out because of issues with 4817 * tracepoints in non-gpl kernel modules. 4818 */ 4819 #if 0 4820 DTRACE_PROBE3(ms__activation__attempt, 4821 metaslab_t *, msp, uint64_t, activation_weight, 4822 boolean_t, was_active); 4823 #endif 4824 4825 /* 4826 * Ensure that the metaslab we have selected is still 4827 * capable of handling our request. It's possible that 4828 * another thread may have changed the weight while we 4829 * were blocked on the metaslab lock. We check the 4830 * active status first to see if we need to set_selected_txg 4831 * a new metaslab. 4832 */ 4833 if (was_active && !(msp->ms_weight & METASLAB_ACTIVE_MASK)) { 4834 ASSERT3S(msp->ms_allocator, ==, -1); 4835 mutex_exit(&msp->ms_lock); 4836 continue; 4837 } 4838 4839 /* 4840 * If the metaslab was activated for another allocator 4841 * while we were waiting in the ms_lock above, or it's 4842 * a primary and we're seeking a secondary (or vice versa), 4843 * we go back and select a new metaslab. 4844 */ 4845 if (!was_active && (msp->ms_weight & METASLAB_ACTIVE_MASK) && 4846 (msp->ms_allocator != -1) && 4847 (msp->ms_allocator != allocator || ((activation_weight == 4848 METASLAB_WEIGHT_PRIMARY) != msp->ms_primary))) { 4849 ASSERT(msp->ms_loaded); 4850 ASSERT((msp->ms_weight & METASLAB_WEIGHT_CLAIM) || 4851 msp->ms_allocator != -1); 4852 mutex_exit(&msp->ms_lock); 4853 continue; 4854 } 4855 4856 /* 4857 * This metaslab was used for claiming regions allocated 4858 * by the ZIL during pool import. Once these regions are 4859 * claimed we don't need to keep the CLAIM bit set 4860 * anymore. Passivate this metaslab to zero its activation 4861 * mask. 4862 */ 4863 if (msp->ms_weight & METASLAB_WEIGHT_CLAIM && 4864 activation_weight != METASLAB_WEIGHT_CLAIM) { 4865 ASSERT(msp->ms_loaded); 4866 ASSERT3S(msp->ms_allocator, ==, -1); 4867 metaslab_passivate(msp, msp->ms_weight & 4868 ~METASLAB_WEIGHT_CLAIM); 4869 mutex_exit(&msp->ms_lock); 4870 continue; 4871 } 4872 4873 metaslab_set_selected_txg(msp, txg); 4874 4875 int activation_error = 4876 metaslab_activate(msp, allocator, activation_weight); 4877 metaslab_active_mask_verify(msp); 4878 4879 /* 4880 * If the metaslab was activated by another thread for 4881 * another allocator or activation_weight (EBUSY), or it 4882 * failed because another metaslab was assigned as primary 4883 * for this allocator (EEXIST) we continue using this 4884 * metaslab for our allocation, rather than going on to a 4885 * worse metaslab (we waited for that metaslab to be loaded 4886 * after all). 4887 * 4888 * If the activation failed due to an I/O error or ENOSPC we 4889 * skip to the next metaslab. 4890 */ 4891 boolean_t activated; 4892 if (activation_error == 0) { 4893 activated = B_TRUE; 4894 } else if (activation_error == EBUSY || 4895 activation_error == EEXIST) { 4896 activated = B_FALSE; 4897 } else { 4898 mutex_exit(&msp->ms_lock); 4899 continue; 4900 } 4901 ASSERT(msp->ms_loaded); 4902 4903 /* 4904 * Now that we have the lock, recheck to see if we should 4905 * continue to use this metaslab for this allocation. The 4906 * the metaslab is now loaded so metaslab_should_allocate() 4907 * can accurately determine if the allocation attempt should 4908 * proceed. 4909 */ 4910 if (!metaslab_should_allocate(msp, asize, try_hard)) { 4911 /* Passivate this metaslab and select a new one. */ 4912 metaslab_trace_add(zal, mg, msp, asize, d, 4913 TRACE_TOO_SMALL, allocator); 4914 goto next; 4915 } 4916 4917 /* 4918 * If this metaslab is currently condensing then pick again 4919 * as we can't manipulate this metaslab until it's committed 4920 * to disk. If this metaslab is being initialized, we shouldn't 4921 * allocate from it since the allocated region might be 4922 * overwritten after allocation. 4923 */ 4924 if (msp->ms_condensing) { 4925 metaslab_trace_add(zal, mg, msp, asize, d, 4926 TRACE_CONDENSING, allocator); 4927 if (activated) { 4928 metaslab_passivate(msp, msp->ms_weight & 4929 ~METASLAB_ACTIVE_MASK); 4930 } 4931 mutex_exit(&msp->ms_lock); 4932 continue; 4933 } else if (msp->ms_disabled > 0) { 4934 metaslab_trace_add(zal, mg, msp, asize, d, 4935 TRACE_DISABLED, allocator); 4936 if (activated) { 4937 metaslab_passivate(msp, msp->ms_weight & 4938 ~METASLAB_ACTIVE_MASK); 4939 } 4940 mutex_exit(&msp->ms_lock); 4941 continue; 4942 } 4943 4944 offset = metaslab_block_alloc(msp, asize, txg); 4945 metaslab_trace_add(zal, mg, msp, asize, d, offset, allocator); 4946 4947 if (offset != -1ULL) { 4948 /* Proactively passivate the metaslab, if needed */ 4949 if (activated) 4950 metaslab_segment_may_passivate(msp); 4951 break; 4952 } 4953 next: 4954 ASSERT(msp->ms_loaded); 4955 4956 /* 4957 * This code is disabled out because of issues with 4958 * tracepoints in non-gpl kernel modules. 4959 */ 4960 #if 0 4961 DTRACE_PROBE2(ms__alloc__failure, metaslab_t *, msp, 4962 uint64_t, asize); 4963 #endif 4964 4965 /* 4966 * We were unable to allocate from this metaslab so determine 4967 * a new weight for this metaslab. Now that we have loaded 4968 * the metaslab we can provide a better hint to the metaslab 4969 * selector. 4970 * 4971 * For space-based metaslabs, we use the maximum block size. 4972 * This information is only available when the metaslab 4973 * is loaded and is more accurate than the generic free 4974 * space weight that was calculated by metaslab_weight(). 4975 * This information allows us to quickly compare the maximum 4976 * available allocation in the metaslab to the allocation 4977 * size being requested. 4978 * 4979 * For segment-based metaslabs, determine the new weight 4980 * based on the highest bucket in the range tree. We 4981 * explicitly use the loaded segment weight (i.e. the range 4982 * tree histogram) since it contains the space that is 4983 * currently available for allocation and is accurate 4984 * even within a sync pass. 4985 */ 4986 uint64_t weight; 4987 if (WEIGHT_IS_SPACEBASED(msp->ms_weight)) { 4988 weight = metaslab_largest_allocatable(msp); 4989 WEIGHT_SET_SPACEBASED(weight); 4990 } else { 4991 weight = metaslab_weight_from_range_tree(msp); 4992 } 4993 4994 if (activated) { 4995 metaslab_passivate(msp, weight); 4996 } else { 4997 /* 4998 * For the case where we use the metaslab that is 4999 * active for another allocator we want to make 5000 * sure that we retain the activation mask. 5001 * 5002 * Note that we could attempt to use something like 5003 * metaslab_recalculate_weight_and_sort() that 5004 * retains the activation mask here. That function 5005 * uses metaslab_weight() to set the weight though 5006 * which is not as accurate as the calculations 5007 * above. 5008 */ 5009 weight |= msp->ms_weight & METASLAB_ACTIVE_MASK; 5010 metaslab_group_sort(mg, msp, weight); 5011 } 5012 metaslab_active_mask_verify(msp); 5013 5014 /* 5015 * We have just failed an allocation attempt, check 5016 * that metaslab_should_allocate() agrees. Otherwise, 5017 * we may end up in an infinite loop retrying the same 5018 * metaslab. 5019 */ 5020 ASSERT(!metaslab_should_allocate(msp, asize, try_hard)); 5021 5022 mutex_exit(&msp->ms_lock); 5023 } 5024 mutex_exit(&msp->ms_lock); 5025 kmem_free(search, sizeof (*search)); 5026 return (offset); 5027 } 5028 5029 static uint64_t 5030 metaslab_group_alloc(metaslab_group_t *mg, zio_alloc_list_t *zal, 5031 uint64_t asize, uint64_t txg, boolean_t want_unique, dva_t *dva, int d, 5032 int allocator, boolean_t try_hard) 5033 { 5034 uint64_t offset; 5035 ASSERT(mg->mg_initialized); 5036 5037 offset = metaslab_group_alloc_normal(mg, zal, asize, txg, want_unique, 5038 dva, d, allocator, try_hard); 5039 5040 mutex_enter(&mg->mg_lock); 5041 if (offset == -1ULL) { 5042 mg->mg_failed_allocations++; 5043 metaslab_trace_add(zal, mg, NULL, asize, d, 5044 TRACE_GROUP_FAILURE, allocator); 5045 if (asize == SPA_GANGBLOCKSIZE) { 5046 /* 5047 * This metaslab group was unable to allocate 5048 * the minimum gang block size so it must be out of 5049 * space. We must notify the allocation throttle 5050 * to start skipping allocation attempts to this 5051 * metaslab group until more space becomes available. 5052 * Note: this failure cannot be caused by the 5053 * allocation throttle since the allocation throttle 5054 * is only responsible for skipping devices and 5055 * not failing block allocations. 5056 */ 5057 mg->mg_no_free_space = B_TRUE; 5058 } 5059 } 5060 mg->mg_allocations++; 5061 mutex_exit(&mg->mg_lock); 5062 return (offset); 5063 } 5064 5065 /* 5066 * Allocate a block for the specified i/o. 5067 */ 5068 int 5069 metaslab_alloc_dva(spa_t *spa, metaslab_class_t *mc, uint64_t psize, 5070 dva_t *dva, int d, dva_t *hintdva, uint64_t txg, int flags, 5071 zio_alloc_list_t *zal, int allocator) 5072 { 5073 metaslab_class_allocator_t *mca = &mc->mc_allocator[allocator]; 5074 metaslab_group_t *mg, *fast_mg, *rotor; 5075 vdev_t *vd; 5076 boolean_t try_hard = B_FALSE; 5077 5078 ASSERT(!DVA_IS_VALID(&dva[d])); 5079 5080 /* 5081 * For testing, make some blocks above a certain size be gang blocks. 5082 * This will result in more split blocks when using device removal, 5083 * and a large number of split blocks coupled with ztest-induced 5084 * damage can result in extremely long reconstruction times. This 5085 * will also test spilling from special to normal. 5086 */ 5087 if (psize >= metaslab_force_ganging && (random_in_range(100) < 3)) { 5088 metaslab_trace_add(zal, NULL, NULL, psize, d, TRACE_FORCE_GANG, 5089 allocator); 5090 return (SET_ERROR(ENOSPC)); 5091 } 5092 5093 /* 5094 * Start at the rotor and loop through all mgs until we find something. 5095 * Note that there's no locking on mca_rotor or mca_aliquot because 5096 * nothing actually breaks if we miss a few updates -- we just won't 5097 * allocate quite as evenly. It all balances out over time. 5098 * 5099 * If we are doing ditto or log blocks, try to spread them across 5100 * consecutive vdevs. If we're forced to reuse a vdev before we've 5101 * allocated all of our ditto blocks, then try and spread them out on 5102 * that vdev as much as possible. If it turns out to not be possible, 5103 * gradually lower our standards until anything becomes acceptable. 5104 * Also, allocating on consecutive vdevs (as opposed to random vdevs) 5105 * gives us hope of containing our fault domains to something we're 5106 * able to reason about. Otherwise, any two top-level vdev failures 5107 * will guarantee the loss of data. With consecutive allocation, 5108 * only two adjacent top-level vdev failures will result in data loss. 5109 * 5110 * If we are doing gang blocks (hintdva is non-NULL), try to keep 5111 * ourselves on the same vdev as our gang block header. That 5112 * way, we can hope for locality in vdev_cache, plus it makes our 5113 * fault domains something tractable. 5114 */ 5115 if (hintdva) { 5116 vd = vdev_lookup_top(spa, DVA_GET_VDEV(&hintdva[d])); 5117 5118 /* 5119 * It's possible the vdev we're using as the hint no 5120 * longer exists or its mg has been closed (e.g. by 5121 * device removal). Consult the rotor when 5122 * all else fails. 5123 */ 5124 if (vd != NULL && vd->vdev_mg != NULL) { 5125 mg = vdev_get_mg(vd, mc); 5126 5127 if (flags & METASLAB_HINTBP_AVOID && 5128 mg->mg_next != NULL) 5129 mg = mg->mg_next; 5130 } else { 5131 mg = mca->mca_rotor; 5132 } 5133 } else if (d != 0) { 5134 vd = vdev_lookup_top(spa, DVA_GET_VDEV(&dva[d - 1])); 5135 mg = vd->vdev_mg->mg_next; 5136 } else if (flags & METASLAB_FASTWRITE) { 5137 mg = fast_mg = mca->mca_rotor; 5138 5139 do { 5140 if (fast_mg->mg_vd->vdev_pending_fastwrite < 5141 mg->mg_vd->vdev_pending_fastwrite) 5142 mg = fast_mg; 5143 } while ((fast_mg = fast_mg->mg_next) != mca->mca_rotor); 5144 5145 } else { 5146 ASSERT(mca->mca_rotor != NULL); 5147 mg = mca->mca_rotor; 5148 } 5149 5150 /* 5151 * If the hint put us into the wrong metaslab class, or into a 5152 * metaslab group that has been passivated, just follow the rotor. 5153 */ 5154 if (mg->mg_class != mc || mg->mg_activation_count <= 0) 5155 mg = mca->mca_rotor; 5156 5157 rotor = mg; 5158 top: 5159 do { 5160 boolean_t allocatable; 5161 5162 ASSERT(mg->mg_activation_count == 1); 5163 vd = mg->mg_vd; 5164 5165 /* 5166 * Don't allocate from faulted devices. 5167 */ 5168 if (try_hard) { 5169 spa_config_enter(spa, SCL_ZIO, FTAG, RW_READER); 5170 allocatable = vdev_allocatable(vd); 5171 spa_config_exit(spa, SCL_ZIO, FTAG); 5172 } else { 5173 allocatable = vdev_allocatable(vd); 5174 } 5175 5176 /* 5177 * Determine if the selected metaslab group is eligible 5178 * for allocations. If we're ganging then don't allow 5179 * this metaslab group to skip allocations since that would 5180 * inadvertently return ENOSPC and suspend the pool 5181 * even though space is still available. 5182 */ 5183 if (allocatable && !GANG_ALLOCATION(flags) && !try_hard) { 5184 allocatable = metaslab_group_allocatable(mg, rotor, 5185 psize, allocator, d); 5186 } 5187 5188 if (!allocatable) { 5189 metaslab_trace_add(zal, mg, NULL, psize, d, 5190 TRACE_NOT_ALLOCATABLE, allocator); 5191 goto next; 5192 } 5193 5194 ASSERT(mg->mg_initialized); 5195 5196 /* 5197 * Avoid writing single-copy data to a failing, 5198 * non-redundant vdev, unless we've already tried all 5199 * other vdevs. 5200 */ 5201 if ((vd->vdev_stat.vs_write_errors > 0 || 5202 vd->vdev_state < VDEV_STATE_HEALTHY) && 5203 d == 0 && !try_hard && vd->vdev_children == 0) { 5204 metaslab_trace_add(zal, mg, NULL, psize, d, 5205 TRACE_VDEV_ERROR, allocator); 5206 goto next; 5207 } 5208 5209 ASSERT(mg->mg_class == mc); 5210 5211 uint64_t asize = vdev_psize_to_asize(vd, psize); 5212 ASSERT(P2PHASE(asize, 1ULL << vd->vdev_ashift) == 0); 5213 5214 /* 5215 * If we don't need to try hard, then require that the 5216 * block be on a different metaslab from any other DVAs 5217 * in this BP (unique=true). If we are trying hard, then 5218 * allow any metaslab to be used (unique=false). 5219 */ 5220 uint64_t offset = metaslab_group_alloc(mg, zal, asize, txg, 5221 !try_hard, dva, d, allocator, try_hard); 5222 5223 if (offset != -1ULL) { 5224 /* 5225 * If we've just selected this metaslab group, 5226 * figure out whether the corresponding vdev is 5227 * over- or under-used relative to the pool, 5228 * and set an allocation bias to even it out. 5229 * 5230 * Bias is also used to compensate for unequally 5231 * sized vdevs so that space is allocated fairly. 5232 */ 5233 if (mca->mca_aliquot == 0 && metaslab_bias_enabled) { 5234 vdev_stat_t *vs = &vd->vdev_stat; 5235 int64_t vs_free = vs->vs_space - vs->vs_alloc; 5236 int64_t mc_free = mc->mc_space - mc->mc_alloc; 5237 int64_t ratio; 5238 5239 /* 5240 * Calculate how much more or less we should 5241 * try to allocate from this device during 5242 * this iteration around the rotor. 5243 * 5244 * This basically introduces a zero-centered 5245 * bias towards the devices with the most 5246 * free space, while compensating for vdev 5247 * size differences. 5248 * 5249 * Examples: 5250 * vdev V1 = 16M/128M 5251 * vdev V2 = 16M/128M 5252 * ratio(V1) = 100% ratio(V2) = 100% 5253 * 5254 * vdev V1 = 16M/128M 5255 * vdev V2 = 64M/128M 5256 * ratio(V1) = 127% ratio(V2) = 72% 5257 * 5258 * vdev V1 = 16M/128M 5259 * vdev V2 = 64M/512M 5260 * ratio(V1) = 40% ratio(V2) = 160% 5261 */ 5262 ratio = (vs_free * mc->mc_alloc_groups * 100) / 5263 (mc_free + 1); 5264 mg->mg_bias = ((ratio - 100) * 5265 (int64_t)mg->mg_aliquot) / 100; 5266 } else if (!metaslab_bias_enabled) { 5267 mg->mg_bias = 0; 5268 } 5269 5270 if ((flags & METASLAB_FASTWRITE) || 5271 atomic_add_64_nv(&mca->mca_aliquot, asize) >= 5272 mg->mg_aliquot + mg->mg_bias) { 5273 mca->mca_rotor = mg->mg_next; 5274 mca->mca_aliquot = 0; 5275 } 5276 5277 DVA_SET_VDEV(&dva[d], vd->vdev_id); 5278 DVA_SET_OFFSET(&dva[d], offset); 5279 DVA_SET_GANG(&dva[d], 5280 ((flags & METASLAB_GANG_HEADER) ? 1 : 0)); 5281 DVA_SET_ASIZE(&dva[d], asize); 5282 5283 if (flags & METASLAB_FASTWRITE) { 5284 atomic_add_64(&vd->vdev_pending_fastwrite, 5285 psize); 5286 } 5287 5288 return (0); 5289 } 5290 next: 5291 mca->mca_rotor = mg->mg_next; 5292 mca->mca_aliquot = 0; 5293 } while ((mg = mg->mg_next) != rotor); 5294 5295 /* 5296 * If we haven't tried hard, perhaps do so now. 5297 */ 5298 if (!try_hard && (zfs_metaslab_try_hard_before_gang || 5299 GANG_ALLOCATION(flags) || (flags & METASLAB_ZIL) != 0 || 5300 psize <= 1 << spa->spa_min_ashift)) { 5301 METASLABSTAT_BUMP(metaslabstat_try_hard); 5302 try_hard = B_TRUE; 5303 goto top; 5304 } 5305 5306 bzero(&dva[d], sizeof (dva_t)); 5307 5308 metaslab_trace_add(zal, rotor, NULL, psize, d, TRACE_ENOSPC, allocator); 5309 return (SET_ERROR(ENOSPC)); 5310 } 5311 5312 void 5313 metaslab_free_concrete(vdev_t *vd, uint64_t offset, uint64_t asize, 5314 boolean_t checkpoint) 5315 { 5316 metaslab_t *msp; 5317 spa_t *spa = vd->vdev_spa; 5318 5319 ASSERT(vdev_is_concrete(vd)); 5320 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 5321 ASSERT3U(offset >> vd->vdev_ms_shift, <, vd->vdev_ms_count); 5322 5323 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 5324 5325 VERIFY(!msp->ms_condensing); 5326 VERIFY3U(offset, >=, msp->ms_start); 5327 VERIFY3U(offset + asize, <=, msp->ms_start + msp->ms_size); 5328 VERIFY0(P2PHASE(offset, 1ULL << vd->vdev_ashift)); 5329 VERIFY0(P2PHASE(asize, 1ULL << vd->vdev_ashift)); 5330 5331 metaslab_check_free_impl(vd, offset, asize); 5332 5333 mutex_enter(&msp->ms_lock); 5334 if (range_tree_is_empty(msp->ms_freeing) && 5335 range_tree_is_empty(msp->ms_checkpointing)) { 5336 vdev_dirty(vd, VDD_METASLAB, msp, spa_syncing_txg(spa)); 5337 } 5338 5339 if (checkpoint) { 5340 ASSERT(spa_has_checkpoint(spa)); 5341 range_tree_add(msp->ms_checkpointing, offset, asize); 5342 } else { 5343 range_tree_add(msp->ms_freeing, offset, asize); 5344 } 5345 mutex_exit(&msp->ms_lock); 5346 } 5347 5348 /* ARGSUSED */ 5349 void 5350 metaslab_free_impl_cb(uint64_t inner_offset, vdev_t *vd, uint64_t offset, 5351 uint64_t size, void *arg) 5352 { 5353 boolean_t *checkpoint = arg; 5354 5355 ASSERT3P(checkpoint, !=, NULL); 5356 5357 if (vd->vdev_ops->vdev_op_remap != NULL) 5358 vdev_indirect_mark_obsolete(vd, offset, size); 5359 else 5360 metaslab_free_impl(vd, offset, size, *checkpoint); 5361 } 5362 5363 static void 5364 metaslab_free_impl(vdev_t *vd, uint64_t offset, uint64_t size, 5365 boolean_t checkpoint) 5366 { 5367 spa_t *spa = vd->vdev_spa; 5368 5369 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 5370 5371 if (spa_syncing_txg(spa) > spa_freeze_txg(spa)) 5372 return; 5373 5374 if (spa->spa_vdev_removal != NULL && 5375 spa->spa_vdev_removal->svr_vdev_id == vd->vdev_id && 5376 vdev_is_concrete(vd)) { 5377 /* 5378 * Note: we check if the vdev is concrete because when 5379 * we complete the removal, we first change the vdev to be 5380 * an indirect vdev (in open context), and then (in syncing 5381 * context) clear spa_vdev_removal. 5382 */ 5383 free_from_removing_vdev(vd, offset, size); 5384 } else if (vd->vdev_ops->vdev_op_remap != NULL) { 5385 vdev_indirect_mark_obsolete(vd, offset, size); 5386 vd->vdev_ops->vdev_op_remap(vd, offset, size, 5387 metaslab_free_impl_cb, &checkpoint); 5388 } else { 5389 metaslab_free_concrete(vd, offset, size, checkpoint); 5390 } 5391 } 5392 5393 typedef struct remap_blkptr_cb_arg { 5394 blkptr_t *rbca_bp; 5395 spa_remap_cb_t rbca_cb; 5396 vdev_t *rbca_remap_vd; 5397 uint64_t rbca_remap_offset; 5398 void *rbca_cb_arg; 5399 } remap_blkptr_cb_arg_t; 5400 5401 static void 5402 remap_blkptr_cb(uint64_t inner_offset, vdev_t *vd, uint64_t offset, 5403 uint64_t size, void *arg) 5404 { 5405 remap_blkptr_cb_arg_t *rbca = arg; 5406 blkptr_t *bp = rbca->rbca_bp; 5407 5408 /* We can not remap split blocks. */ 5409 if (size != DVA_GET_ASIZE(&bp->blk_dva[0])) 5410 return; 5411 ASSERT0(inner_offset); 5412 5413 if (rbca->rbca_cb != NULL) { 5414 /* 5415 * At this point we know that we are not handling split 5416 * blocks and we invoke the callback on the previous 5417 * vdev which must be indirect. 5418 */ 5419 ASSERT3P(rbca->rbca_remap_vd->vdev_ops, ==, &vdev_indirect_ops); 5420 5421 rbca->rbca_cb(rbca->rbca_remap_vd->vdev_id, 5422 rbca->rbca_remap_offset, size, rbca->rbca_cb_arg); 5423 5424 /* set up remap_blkptr_cb_arg for the next call */ 5425 rbca->rbca_remap_vd = vd; 5426 rbca->rbca_remap_offset = offset; 5427 } 5428 5429 /* 5430 * The phys birth time is that of dva[0]. This ensures that we know 5431 * when each dva was written, so that resilver can determine which 5432 * blocks need to be scrubbed (i.e. those written during the time 5433 * the vdev was offline). It also ensures that the key used in 5434 * the ARC hash table is unique (i.e. dva[0] + phys_birth). If 5435 * we didn't change the phys_birth, a lookup in the ARC for a 5436 * remapped BP could find the data that was previously stored at 5437 * this vdev + offset. 5438 */ 5439 vdev_t *oldvd = vdev_lookup_top(vd->vdev_spa, 5440 DVA_GET_VDEV(&bp->blk_dva[0])); 5441 vdev_indirect_births_t *vib = oldvd->vdev_indirect_births; 5442 bp->blk_phys_birth = vdev_indirect_births_physbirth(vib, 5443 DVA_GET_OFFSET(&bp->blk_dva[0]), DVA_GET_ASIZE(&bp->blk_dva[0])); 5444 5445 DVA_SET_VDEV(&bp->blk_dva[0], vd->vdev_id); 5446 DVA_SET_OFFSET(&bp->blk_dva[0], offset); 5447 } 5448 5449 /* 5450 * If the block pointer contains any indirect DVAs, modify them to refer to 5451 * concrete DVAs. Note that this will sometimes not be possible, leaving 5452 * the indirect DVA in place. This happens if the indirect DVA spans multiple 5453 * segments in the mapping (i.e. it is a "split block"). 5454 * 5455 * If the BP was remapped, calls the callback on the original dva (note the 5456 * callback can be called multiple times if the original indirect DVA refers 5457 * to another indirect DVA, etc). 5458 * 5459 * Returns TRUE if the BP was remapped. 5460 */ 5461 boolean_t 5462 spa_remap_blkptr(spa_t *spa, blkptr_t *bp, spa_remap_cb_t callback, void *arg) 5463 { 5464 remap_blkptr_cb_arg_t rbca; 5465 5466 if (!zfs_remap_blkptr_enable) 5467 return (B_FALSE); 5468 5469 if (!spa_feature_is_enabled(spa, SPA_FEATURE_OBSOLETE_COUNTS)) 5470 return (B_FALSE); 5471 5472 /* 5473 * Dedup BP's can not be remapped, because ddt_phys_select() depends 5474 * on DVA[0] being the same in the BP as in the DDT (dedup table). 5475 */ 5476 if (BP_GET_DEDUP(bp)) 5477 return (B_FALSE); 5478 5479 /* 5480 * Gang blocks can not be remapped, because 5481 * zio_checksum_gang_verifier() depends on the DVA[0] that's in 5482 * the BP used to read the gang block header (GBH) being the same 5483 * as the DVA[0] that we allocated for the GBH. 5484 */ 5485 if (BP_IS_GANG(bp)) 5486 return (B_FALSE); 5487 5488 /* 5489 * Embedded BP's have no DVA to remap. 5490 */ 5491 if (BP_GET_NDVAS(bp) < 1) 5492 return (B_FALSE); 5493 5494 /* 5495 * Note: we only remap dva[0]. If we remapped other dvas, we 5496 * would no longer know what their phys birth txg is. 5497 */ 5498 dva_t *dva = &bp->blk_dva[0]; 5499 5500 uint64_t offset = DVA_GET_OFFSET(dva); 5501 uint64_t size = DVA_GET_ASIZE(dva); 5502 vdev_t *vd = vdev_lookup_top(spa, DVA_GET_VDEV(dva)); 5503 5504 if (vd->vdev_ops->vdev_op_remap == NULL) 5505 return (B_FALSE); 5506 5507 rbca.rbca_bp = bp; 5508 rbca.rbca_cb = callback; 5509 rbca.rbca_remap_vd = vd; 5510 rbca.rbca_remap_offset = offset; 5511 rbca.rbca_cb_arg = arg; 5512 5513 /* 5514 * remap_blkptr_cb() will be called in order for each level of 5515 * indirection, until a concrete vdev is reached or a split block is 5516 * encountered. old_vd and old_offset are updated within the callback 5517 * as we go from the one indirect vdev to the next one (either concrete 5518 * or indirect again) in that order. 5519 */ 5520 vd->vdev_ops->vdev_op_remap(vd, offset, size, remap_blkptr_cb, &rbca); 5521 5522 /* Check if the DVA wasn't remapped because it is a split block */ 5523 if (DVA_GET_VDEV(&rbca.rbca_bp->blk_dva[0]) == vd->vdev_id) 5524 return (B_FALSE); 5525 5526 return (B_TRUE); 5527 } 5528 5529 /* 5530 * Undo the allocation of a DVA which happened in the given transaction group. 5531 */ 5532 void 5533 metaslab_unalloc_dva(spa_t *spa, const dva_t *dva, uint64_t txg) 5534 { 5535 metaslab_t *msp; 5536 vdev_t *vd; 5537 uint64_t vdev = DVA_GET_VDEV(dva); 5538 uint64_t offset = DVA_GET_OFFSET(dva); 5539 uint64_t size = DVA_GET_ASIZE(dva); 5540 5541 ASSERT(DVA_IS_VALID(dva)); 5542 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 5543 5544 if (txg > spa_freeze_txg(spa)) 5545 return; 5546 5547 if ((vd = vdev_lookup_top(spa, vdev)) == NULL || !DVA_IS_VALID(dva) || 5548 (offset >> vd->vdev_ms_shift) >= vd->vdev_ms_count) { 5549 zfs_panic_recover("metaslab_free_dva(): bad DVA %llu:%llu:%llu", 5550 (u_longlong_t)vdev, (u_longlong_t)offset, 5551 (u_longlong_t)size); 5552 return; 5553 } 5554 5555 ASSERT(!vd->vdev_removing); 5556 ASSERT(vdev_is_concrete(vd)); 5557 ASSERT0(vd->vdev_indirect_config.vic_mapping_object); 5558 ASSERT3P(vd->vdev_indirect_mapping, ==, NULL); 5559 5560 if (DVA_GET_GANG(dva)) 5561 size = vdev_gang_header_asize(vd); 5562 5563 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 5564 5565 mutex_enter(&msp->ms_lock); 5566 range_tree_remove(msp->ms_allocating[txg & TXG_MASK], 5567 offset, size); 5568 msp->ms_allocating_total -= size; 5569 5570 VERIFY(!msp->ms_condensing); 5571 VERIFY3U(offset, >=, msp->ms_start); 5572 VERIFY3U(offset + size, <=, msp->ms_start + msp->ms_size); 5573 VERIFY3U(range_tree_space(msp->ms_allocatable) + size, <=, 5574 msp->ms_size); 5575 VERIFY0(P2PHASE(offset, 1ULL << vd->vdev_ashift)); 5576 VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift)); 5577 range_tree_add(msp->ms_allocatable, offset, size); 5578 mutex_exit(&msp->ms_lock); 5579 } 5580 5581 /* 5582 * Free the block represented by the given DVA. 5583 */ 5584 void 5585 metaslab_free_dva(spa_t *spa, const dva_t *dva, boolean_t checkpoint) 5586 { 5587 uint64_t vdev = DVA_GET_VDEV(dva); 5588 uint64_t offset = DVA_GET_OFFSET(dva); 5589 uint64_t size = DVA_GET_ASIZE(dva); 5590 vdev_t *vd = vdev_lookup_top(spa, vdev); 5591 5592 ASSERT(DVA_IS_VALID(dva)); 5593 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 5594 5595 if (DVA_GET_GANG(dva)) { 5596 size = vdev_gang_header_asize(vd); 5597 } 5598 5599 metaslab_free_impl(vd, offset, size, checkpoint); 5600 } 5601 5602 /* 5603 * Reserve some allocation slots. The reservation system must be called 5604 * before we call into the allocator. If there aren't any available slots 5605 * then the I/O will be throttled until an I/O completes and its slots are 5606 * freed up. The function returns true if it was successful in placing 5607 * the reservation. 5608 */ 5609 boolean_t 5610 metaslab_class_throttle_reserve(metaslab_class_t *mc, int slots, int allocator, 5611 zio_t *zio, int flags) 5612 { 5613 metaslab_class_allocator_t *mca = &mc->mc_allocator[allocator]; 5614 uint64_t max = mca->mca_alloc_max_slots; 5615 5616 ASSERT(mc->mc_alloc_throttle_enabled); 5617 if (GANG_ALLOCATION(flags) || (flags & METASLAB_MUST_RESERVE) || 5618 zfs_refcount_count(&mca->mca_alloc_slots) + slots <= max) { 5619 /* 5620 * The potential race between _count() and _add() is covered 5621 * by the allocator lock in most cases, or irrelevant due to 5622 * GANG_ALLOCATION() or METASLAB_MUST_RESERVE set in others. 5623 * But even if we assume some other non-existing scenario, the 5624 * worst that can happen is few more I/Os get to allocation 5625 * earlier, that is not a problem. 5626 * 5627 * We reserve the slots individually so that we can unreserve 5628 * them individually when an I/O completes. 5629 */ 5630 for (int d = 0; d < slots; d++) 5631 zfs_refcount_add(&mca->mca_alloc_slots, zio); 5632 zio->io_flags |= ZIO_FLAG_IO_ALLOCATING; 5633 return (B_TRUE); 5634 } 5635 return (B_FALSE); 5636 } 5637 5638 void 5639 metaslab_class_throttle_unreserve(metaslab_class_t *mc, int slots, 5640 int allocator, zio_t *zio) 5641 { 5642 metaslab_class_allocator_t *mca = &mc->mc_allocator[allocator]; 5643 5644 ASSERT(mc->mc_alloc_throttle_enabled); 5645 for (int d = 0; d < slots; d++) 5646 zfs_refcount_remove(&mca->mca_alloc_slots, zio); 5647 } 5648 5649 static int 5650 metaslab_claim_concrete(vdev_t *vd, uint64_t offset, uint64_t size, 5651 uint64_t txg) 5652 { 5653 metaslab_t *msp; 5654 spa_t *spa = vd->vdev_spa; 5655 int error = 0; 5656 5657 if (offset >> vd->vdev_ms_shift >= vd->vdev_ms_count) 5658 return (SET_ERROR(ENXIO)); 5659 5660 ASSERT3P(vd->vdev_ms, !=, NULL); 5661 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 5662 5663 mutex_enter(&msp->ms_lock); 5664 5665 if ((txg != 0 && spa_writeable(spa)) || !msp->ms_loaded) { 5666 error = metaslab_activate(msp, 0, METASLAB_WEIGHT_CLAIM); 5667 if (error == EBUSY) { 5668 ASSERT(msp->ms_loaded); 5669 ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK); 5670 error = 0; 5671 } 5672 } 5673 5674 if (error == 0 && 5675 !range_tree_contains(msp->ms_allocatable, offset, size)) 5676 error = SET_ERROR(ENOENT); 5677 5678 if (error || txg == 0) { /* txg == 0 indicates dry run */ 5679 mutex_exit(&msp->ms_lock); 5680 return (error); 5681 } 5682 5683 VERIFY(!msp->ms_condensing); 5684 VERIFY0(P2PHASE(offset, 1ULL << vd->vdev_ashift)); 5685 VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift)); 5686 VERIFY3U(range_tree_space(msp->ms_allocatable) - size, <=, 5687 msp->ms_size); 5688 range_tree_remove(msp->ms_allocatable, offset, size); 5689 range_tree_clear(msp->ms_trim, offset, size); 5690 5691 if (spa_writeable(spa)) { /* don't dirty if we're zdb(8) */ 5692 metaslab_class_t *mc = msp->ms_group->mg_class; 5693 multilist_sublist_t *mls = 5694 multilist_sublist_lock_obj(&mc->mc_metaslab_txg_list, msp); 5695 if (!multilist_link_active(&msp->ms_class_txg_node)) { 5696 msp->ms_selected_txg = txg; 5697 multilist_sublist_insert_head(mls, msp); 5698 } 5699 multilist_sublist_unlock(mls); 5700 5701 if (range_tree_is_empty(msp->ms_allocating[txg & TXG_MASK])) 5702 vdev_dirty(vd, VDD_METASLAB, msp, txg); 5703 range_tree_add(msp->ms_allocating[txg & TXG_MASK], 5704 offset, size); 5705 msp->ms_allocating_total += size; 5706 } 5707 5708 mutex_exit(&msp->ms_lock); 5709 5710 return (0); 5711 } 5712 5713 typedef struct metaslab_claim_cb_arg_t { 5714 uint64_t mcca_txg; 5715 int mcca_error; 5716 } metaslab_claim_cb_arg_t; 5717 5718 /* ARGSUSED */ 5719 static void 5720 metaslab_claim_impl_cb(uint64_t inner_offset, vdev_t *vd, uint64_t offset, 5721 uint64_t size, void *arg) 5722 { 5723 metaslab_claim_cb_arg_t *mcca_arg = arg; 5724 5725 if (mcca_arg->mcca_error == 0) { 5726 mcca_arg->mcca_error = metaslab_claim_concrete(vd, offset, 5727 size, mcca_arg->mcca_txg); 5728 } 5729 } 5730 5731 int 5732 metaslab_claim_impl(vdev_t *vd, uint64_t offset, uint64_t size, uint64_t txg) 5733 { 5734 if (vd->vdev_ops->vdev_op_remap != NULL) { 5735 metaslab_claim_cb_arg_t arg; 5736 5737 /* 5738 * Only zdb(8) can claim on indirect vdevs. This is used 5739 * to detect leaks of mapped space (that are not accounted 5740 * for in the obsolete counts, spacemap, or bpobj). 5741 */ 5742 ASSERT(!spa_writeable(vd->vdev_spa)); 5743 arg.mcca_error = 0; 5744 arg.mcca_txg = txg; 5745 5746 vd->vdev_ops->vdev_op_remap(vd, offset, size, 5747 metaslab_claim_impl_cb, &arg); 5748 5749 if (arg.mcca_error == 0) { 5750 arg.mcca_error = metaslab_claim_concrete(vd, 5751 offset, size, txg); 5752 } 5753 return (arg.mcca_error); 5754 } else { 5755 return (metaslab_claim_concrete(vd, offset, size, txg)); 5756 } 5757 } 5758 5759 /* 5760 * Intent log support: upon opening the pool after a crash, notify the SPA 5761 * of blocks that the intent log has allocated for immediate write, but 5762 * which are still considered free by the SPA because the last transaction 5763 * group didn't commit yet. 5764 */ 5765 static int 5766 metaslab_claim_dva(spa_t *spa, const dva_t *dva, uint64_t txg) 5767 { 5768 uint64_t vdev = DVA_GET_VDEV(dva); 5769 uint64_t offset = DVA_GET_OFFSET(dva); 5770 uint64_t size = DVA_GET_ASIZE(dva); 5771 vdev_t *vd; 5772 5773 if ((vd = vdev_lookup_top(spa, vdev)) == NULL) { 5774 return (SET_ERROR(ENXIO)); 5775 } 5776 5777 ASSERT(DVA_IS_VALID(dva)); 5778 5779 if (DVA_GET_GANG(dva)) 5780 size = vdev_gang_header_asize(vd); 5781 5782 return (metaslab_claim_impl(vd, offset, size, txg)); 5783 } 5784 5785 int 5786 metaslab_alloc(spa_t *spa, metaslab_class_t *mc, uint64_t psize, blkptr_t *bp, 5787 int ndvas, uint64_t txg, blkptr_t *hintbp, int flags, 5788 zio_alloc_list_t *zal, zio_t *zio, int allocator) 5789 { 5790 dva_t *dva = bp->blk_dva; 5791 dva_t *hintdva = (hintbp != NULL) ? hintbp->blk_dva : NULL; 5792 int error = 0; 5793 5794 ASSERT(bp->blk_birth == 0); 5795 ASSERT(BP_PHYSICAL_BIRTH(bp) == 0); 5796 5797 spa_config_enter(spa, SCL_ALLOC, FTAG, RW_READER); 5798 5799 if (mc->mc_allocator[allocator].mca_rotor == NULL) { 5800 /* no vdevs in this class */ 5801 spa_config_exit(spa, SCL_ALLOC, FTAG); 5802 return (SET_ERROR(ENOSPC)); 5803 } 5804 5805 ASSERT(ndvas > 0 && ndvas <= spa_max_replication(spa)); 5806 ASSERT(BP_GET_NDVAS(bp) == 0); 5807 ASSERT(hintbp == NULL || ndvas <= BP_GET_NDVAS(hintbp)); 5808 ASSERT3P(zal, !=, NULL); 5809 5810 for (int d = 0; d < ndvas; d++) { 5811 error = metaslab_alloc_dva(spa, mc, psize, dva, d, hintdva, 5812 txg, flags, zal, allocator); 5813 if (error != 0) { 5814 for (d--; d >= 0; d--) { 5815 metaslab_unalloc_dva(spa, &dva[d], txg); 5816 metaslab_group_alloc_decrement(spa, 5817 DVA_GET_VDEV(&dva[d]), zio, flags, 5818 allocator, B_FALSE); 5819 bzero(&dva[d], sizeof (dva_t)); 5820 } 5821 spa_config_exit(spa, SCL_ALLOC, FTAG); 5822 return (error); 5823 } else { 5824 /* 5825 * Update the metaslab group's queue depth 5826 * based on the newly allocated dva. 5827 */ 5828 metaslab_group_alloc_increment(spa, 5829 DVA_GET_VDEV(&dva[d]), zio, flags, allocator); 5830 } 5831 } 5832 ASSERT(error == 0); 5833 ASSERT(BP_GET_NDVAS(bp) == ndvas); 5834 5835 spa_config_exit(spa, SCL_ALLOC, FTAG); 5836 5837 BP_SET_BIRTH(bp, txg, 0); 5838 5839 return (0); 5840 } 5841 5842 void 5843 metaslab_free(spa_t *spa, const blkptr_t *bp, uint64_t txg, boolean_t now) 5844 { 5845 const dva_t *dva = bp->blk_dva; 5846 int ndvas = BP_GET_NDVAS(bp); 5847 5848 ASSERT(!BP_IS_HOLE(bp)); 5849 ASSERT(!now || bp->blk_birth >= spa_syncing_txg(spa)); 5850 5851 /* 5852 * If we have a checkpoint for the pool we need to make sure that 5853 * the blocks that we free that are part of the checkpoint won't be 5854 * reused until the checkpoint is discarded or we revert to it. 5855 * 5856 * The checkpoint flag is passed down the metaslab_free code path 5857 * and is set whenever we want to add a block to the checkpoint's 5858 * accounting. That is, we "checkpoint" blocks that existed at the 5859 * time the checkpoint was created and are therefore referenced by 5860 * the checkpointed uberblock. 5861 * 5862 * Note that, we don't checkpoint any blocks if the current 5863 * syncing txg <= spa_checkpoint_txg. We want these frees to sync 5864 * normally as they will be referenced by the checkpointed uberblock. 5865 */ 5866 boolean_t checkpoint = B_FALSE; 5867 if (bp->blk_birth <= spa->spa_checkpoint_txg && 5868 spa_syncing_txg(spa) > spa->spa_checkpoint_txg) { 5869 /* 5870 * At this point, if the block is part of the checkpoint 5871 * there is no way it was created in the current txg. 5872 */ 5873 ASSERT(!now); 5874 ASSERT3U(spa_syncing_txg(spa), ==, txg); 5875 checkpoint = B_TRUE; 5876 } 5877 5878 spa_config_enter(spa, SCL_FREE, FTAG, RW_READER); 5879 5880 for (int d = 0; d < ndvas; d++) { 5881 if (now) { 5882 metaslab_unalloc_dva(spa, &dva[d], txg); 5883 } else { 5884 ASSERT3U(txg, ==, spa_syncing_txg(spa)); 5885 metaslab_free_dva(spa, &dva[d], checkpoint); 5886 } 5887 } 5888 5889 spa_config_exit(spa, SCL_FREE, FTAG); 5890 } 5891 5892 int 5893 metaslab_claim(spa_t *spa, const blkptr_t *bp, uint64_t txg) 5894 { 5895 const dva_t *dva = bp->blk_dva; 5896 int ndvas = BP_GET_NDVAS(bp); 5897 int error = 0; 5898 5899 ASSERT(!BP_IS_HOLE(bp)); 5900 5901 if (txg != 0) { 5902 /* 5903 * First do a dry run to make sure all DVAs are claimable, 5904 * so we don't have to unwind from partial failures below. 5905 */ 5906 if ((error = metaslab_claim(spa, bp, 0)) != 0) 5907 return (error); 5908 } 5909 5910 spa_config_enter(spa, SCL_ALLOC, FTAG, RW_READER); 5911 5912 for (int d = 0; d < ndvas; d++) { 5913 error = metaslab_claim_dva(spa, &dva[d], txg); 5914 if (error != 0) 5915 break; 5916 } 5917 5918 spa_config_exit(spa, SCL_ALLOC, FTAG); 5919 5920 ASSERT(error == 0 || txg == 0); 5921 5922 return (error); 5923 } 5924 5925 void 5926 metaslab_fastwrite_mark(spa_t *spa, const blkptr_t *bp) 5927 { 5928 const dva_t *dva = bp->blk_dva; 5929 int ndvas = BP_GET_NDVAS(bp); 5930 uint64_t psize = BP_GET_PSIZE(bp); 5931 int d; 5932 vdev_t *vd; 5933 5934 ASSERT(!BP_IS_HOLE(bp)); 5935 ASSERT(!BP_IS_EMBEDDED(bp)); 5936 ASSERT(psize > 0); 5937 5938 spa_config_enter(spa, SCL_VDEV, FTAG, RW_READER); 5939 5940 for (d = 0; d < ndvas; d++) { 5941 if ((vd = vdev_lookup_top(spa, DVA_GET_VDEV(&dva[d]))) == NULL) 5942 continue; 5943 atomic_add_64(&vd->vdev_pending_fastwrite, psize); 5944 } 5945 5946 spa_config_exit(spa, SCL_VDEV, FTAG); 5947 } 5948 5949 void 5950 metaslab_fastwrite_unmark(spa_t *spa, const blkptr_t *bp) 5951 { 5952 const dva_t *dva = bp->blk_dva; 5953 int ndvas = BP_GET_NDVAS(bp); 5954 uint64_t psize = BP_GET_PSIZE(bp); 5955 int d; 5956 vdev_t *vd; 5957 5958 ASSERT(!BP_IS_HOLE(bp)); 5959 ASSERT(!BP_IS_EMBEDDED(bp)); 5960 ASSERT(psize > 0); 5961 5962 spa_config_enter(spa, SCL_VDEV, FTAG, RW_READER); 5963 5964 for (d = 0; d < ndvas; d++) { 5965 if ((vd = vdev_lookup_top(spa, DVA_GET_VDEV(&dva[d]))) == NULL) 5966 continue; 5967 ASSERT3U(vd->vdev_pending_fastwrite, >=, psize); 5968 atomic_sub_64(&vd->vdev_pending_fastwrite, psize); 5969 } 5970 5971 spa_config_exit(spa, SCL_VDEV, FTAG); 5972 } 5973 5974 /* ARGSUSED */ 5975 static void 5976 metaslab_check_free_impl_cb(uint64_t inner, vdev_t *vd, uint64_t offset, 5977 uint64_t size, void *arg) 5978 { 5979 if (vd->vdev_ops == &vdev_indirect_ops) 5980 return; 5981 5982 metaslab_check_free_impl(vd, offset, size); 5983 } 5984 5985 static void 5986 metaslab_check_free_impl(vdev_t *vd, uint64_t offset, uint64_t size) 5987 { 5988 metaslab_t *msp; 5989 spa_t *spa __maybe_unused = vd->vdev_spa; 5990 5991 if ((zfs_flags & ZFS_DEBUG_ZIO_FREE) == 0) 5992 return; 5993 5994 if (vd->vdev_ops->vdev_op_remap != NULL) { 5995 vd->vdev_ops->vdev_op_remap(vd, offset, size, 5996 metaslab_check_free_impl_cb, NULL); 5997 return; 5998 } 5999 6000 ASSERT(vdev_is_concrete(vd)); 6001 ASSERT3U(offset >> vd->vdev_ms_shift, <, vd->vdev_ms_count); 6002 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 6003 6004 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 6005 6006 mutex_enter(&msp->ms_lock); 6007 if (msp->ms_loaded) { 6008 range_tree_verify_not_present(msp->ms_allocatable, 6009 offset, size); 6010 } 6011 6012 /* 6013 * Check all segments that currently exist in the freeing pipeline. 6014 * 6015 * It would intuitively make sense to also check the current allocating 6016 * tree since metaslab_unalloc_dva() exists for extents that are 6017 * allocated and freed in the same sync pass within the same txg. 6018 * Unfortunately there are places (e.g. the ZIL) where we allocate a 6019 * segment but then we free part of it within the same txg 6020 * [see zil_sync()]. Thus, we don't call range_tree_verify() in the 6021 * current allocating tree. 6022 */ 6023 range_tree_verify_not_present(msp->ms_freeing, offset, size); 6024 range_tree_verify_not_present(msp->ms_checkpointing, offset, size); 6025 range_tree_verify_not_present(msp->ms_freed, offset, size); 6026 for (int j = 0; j < TXG_DEFER_SIZE; j++) 6027 range_tree_verify_not_present(msp->ms_defer[j], offset, size); 6028 range_tree_verify_not_present(msp->ms_trim, offset, size); 6029 mutex_exit(&msp->ms_lock); 6030 } 6031 6032 void 6033 metaslab_check_free(spa_t *spa, const blkptr_t *bp) 6034 { 6035 if ((zfs_flags & ZFS_DEBUG_ZIO_FREE) == 0) 6036 return; 6037 6038 spa_config_enter(spa, SCL_VDEV, FTAG, RW_READER); 6039 for (int i = 0; i < BP_GET_NDVAS(bp); i++) { 6040 uint64_t vdev = DVA_GET_VDEV(&bp->blk_dva[i]); 6041 vdev_t *vd = vdev_lookup_top(spa, vdev); 6042 uint64_t offset = DVA_GET_OFFSET(&bp->blk_dva[i]); 6043 uint64_t size = DVA_GET_ASIZE(&bp->blk_dva[i]); 6044 6045 if (DVA_GET_GANG(&bp->blk_dva[i])) 6046 size = vdev_gang_header_asize(vd); 6047 6048 ASSERT3P(vd, !=, NULL); 6049 6050 metaslab_check_free_impl(vd, offset, size); 6051 } 6052 spa_config_exit(spa, SCL_VDEV, FTAG); 6053 } 6054 6055 static void 6056 metaslab_group_disable_wait(metaslab_group_t *mg) 6057 { 6058 ASSERT(MUTEX_HELD(&mg->mg_ms_disabled_lock)); 6059 while (mg->mg_disabled_updating) { 6060 cv_wait(&mg->mg_ms_disabled_cv, &mg->mg_ms_disabled_lock); 6061 } 6062 } 6063 6064 static void 6065 metaslab_group_disabled_increment(metaslab_group_t *mg) 6066 { 6067 ASSERT(MUTEX_HELD(&mg->mg_ms_disabled_lock)); 6068 ASSERT(mg->mg_disabled_updating); 6069 6070 while (mg->mg_ms_disabled >= max_disabled_ms) { 6071 cv_wait(&mg->mg_ms_disabled_cv, &mg->mg_ms_disabled_lock); 6072 } 6073 mg->mg_ms_disabled++; 6074 ASSERT3U(mg->mg_ms_disabled, <=, max_disabled_ms); 6075 } 6076 6077 /* 6078 * Mark the metaslab as disabled to prevent any allocations on this metaslab. 6079 * We must also track how many metaslabs are currently disabled within a 6080 * metaslab group and limit them to prevent allocation failures from 6081 * occurring because all metaslabs are disabled. 6082 */ 6083 void 6084 metaslab_disable(metaslab_t *msp) 6085 { 6086 ASSERT(!MUTEX_HELD(&msp->ms_lock)); 6087 metaslab_group_t *mg = msp->ms_group; 6088 6089 mutex_enter(&mg->mg_ms_disabled_lock); 6090 6091 /* 6092 * To keep an accurate count of how many threads have disabled 6093 * a specific metaslab group, we only allow one thread to mark 6094 * the metaslab group at a time. This ensures that the value of 6095 * ms_disabled will be accurate when we decide to mark a metaslab 6096 * group as disabled. To do this we force all other threads 6097 * to wait till the metaslab's mg_disabled_updating flag is no 6098 * longer set. 6099 */ 6100 metaslab_group_disable_wait(mg); 6101 mg->mg_disabled_updating = B_TRUE; 6102 if (msp->ms_disabled == 0) { 6103 metaslab_group_disabled_increment(mg); 6104 } 6105 mutex_enter(&msp->ms_lock); 6106 msp->ms_disabled++; 6107 mutex_exit(&msp->ms_lock); 6108 6109 mg->mg_disabled_updating = B_FALSE; 6110 cv_broadcast(&mg->mg_ms_disabled_cv); 6111 mutex_exit(&mg->mg_ms_disabled_lock); 6112 } 6113 6114 void 6115 metaslab_enable(metaslab_t *msp, boolean_t sync, boolean_t unload) 6116 { 6117 metaslab_group_t *mg = msp->ms_group; 6118 spa_t *spa = mg->mg_vd->vdev_spa; 6119 6120 /* 6121 * Wait for the outstanding IO to be synced to prevent newly 6122 * allocated blocks from being overwritten. This used by 6123 * initialize and TRIM which are modifying unallocated space. 6124 */ 6125 if (sync) 6126 txg_wait_synced(spa_get_dsl(spa), 0); 6127 6128 mutex_enter(&mg->mg_ms_disabled_lock); 6129 mutex_enter(&msp->ms_lock); 6130 if (--msp->ms_disabled == 0) { 6131 mg->mg_ms_disabled--; 6132 cv_broadcast(&mg->mg_ms_disabled_cv); 6133 if (unload) 6134 metaslab_unload(msp); 6135 } 6136 mutex_exit(&msp->ms_lock); 6137 mutex_exit(&mg->mg_ms_disabled_lock); 6138 } 6139 6140 static void 6141 metaslab_update_ondisk_flush_data(metaslab_t *ms, dmu_tx_t *tx) 6142 { 6143 vdev_t *vd = ms->ms_group->mg_vd; 6144 spa_t *spa = vd->vdev_spa; 6145 objset_t *mos = spa_meta_objset(spa); 6146 6147 ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)); 6148 6149 metaslab_unflushed_phys_t entry = { 6150 .msp_unflushed_txg = metaslab_unflushed_txg(ms), 6151 }; 6152 uint64_t entry_size = sizeof (entry); 6153 uint64_t entry_offset = ms->ms_id * entry_size; 6154 6155 uint64_t object = 0; 6156 int err = zap_lookup(mos, vd->vdev_top_zap, 6157 VDEV_TOP_ZAP_MS_UNFLUSHED_PHYS_TXGS, sizeof (uint64_t), 1, 6158 &object); 6159 if (err == ENOENT) { 6160 object = dmu_object_alloc(mos, DMU_OTN_UINT64_METADATA, 6161 SPA_OLD_MAXBLOCKSIZE, DMU_OT_NONE, 0, tx); 6162 VERIFY0(zap_add(mos, vd->vdev_top_zap, 6163 VDEV_TOP_ZAP_MS_UNFLUSHED_PHYS_TXGS, sizeof (uint64_t), 1, 6164 &object, tx)); 6165 } else { 6166 VERIFY0(err); 6167 } 6168 6169 dmu_write(spa_meta_objset(spa), object, entry_offset, entry_size, 6170 &entry, tx); 6171 } 6172 6173 void 6174 metaslab_set_unflushed_txg(metaslab_t *ms, uint64_t txg, dmu_tx_t *tx) 6175 { 6176 spa_t *spa = ms->ms_group->mg_vd->vdev_spa; 6177 6178 if (!spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)) 6179 return; 6180 6181 ms->ms_unflushed_txg = txg; 6182 metaslab_update_ondisk_flush_data(ms, tx); 6183 } 6184 6185 uint64_t 6186 metaslab_unflushed_txg(metaslab_t *ms) 6187 { 6188 return (ms->ms_unflushed_txg); 6189 } 6190 6191 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, aliquot, ULONG, ZMOD_RW, 6192 "Allocation granularity (a.k.a. stripe size)"); 6193 6194 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, debug_load, INT, ZMOD_RW, 6195 "Load all metaslabs when pool is first opened"); 6196 6197 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, debug_unload, INT, ZMOD_RW, 6198 "Prevent metaslabs from being unloaded"); 6199 6200 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, preload_enabled, INT, ZMOD_RW, 6201 "Preload potential metaslabs during reassessment"); 6202 6203 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, unload_delay, INT, ZMOD_RW, 6204 "Delay in txgs after metaslab was last used before unloading"); 6205 6206 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, unload_delay_ms, INT, ZMOD_RW, 6207 "Delay in milliseconds after metaslab was last used before unloading"); 6208 6209 /* BEGIN CSTYLED */ 6210 ZFS_MODULE_PARAM(zfs_mg, zfs_mg_, noalloc_threshold, INT, ZMOD_RW, 6211 "Percentage of metaslab group size that should be free to make it " 6212 "eligible for allocation"); 6213 6214 ZFS_MODULE_PARAM(zfs_mg, zfs_mg_, fragmentation_threshold, INT, ZMOD_RW, 6215 "Percentage of metaslab group size that should be considered eligible " 6216 "for allocations unless all metaslab groups within the metaslab class " 6217 "have also crossed this threshold"); 6218 6219 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, fragmentation_threshold, INT, 6220 ZMOD_RW, "Fragmentation for metaslab to allow allocation"); 6221 6222 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, fragmentation_factor_enabled, INT, ZMOD_RW, 6223 "Use the fragmentation metric to prefer less fragmented metaslabs"); 6224 /* END CSTYLED */ 6225 6226 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, lba_weighting_enabled, INT, ZMOD_RW, 6227 "Prefer metaslabs with lower LBAs"); 6228 6229 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, bias_enabled, INT, ZMOD_RW, 6230 "Enable metaslab group biasing"); 6231 6232 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, segment_weight_enabled, INT, 6233 ZMOD_RW, "Enable segment-based metaslab selection"); 6234 6235 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, switch_threshold, INT, ZMOD_RW, 6236 "Segment-based metaslab selection maximum buckets before switching"); 6237 6238 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, force_ganging, ULONG, ZMOD_RW, 6239 "Blocks larger than this size are forced to be gang blocks"); 6240 6241 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, df_max_search, INT, ZMOD_RW, 6242 "Max distance (bytes) to search forward before using size tree"); 6243 6244 ZFS_MODULE_PARAM(zfs_metaslab, metaslab_, df_use_largest_segment, INT, ZMOD_RW, 6245 "When looking in size tree, use largest segment instead of exact fit"); 6246 6247 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, max_size_cache_sec, ULONG, 6248 ZMOD_RW, "How long to trust the cached max chunk size of a metaslab"); 6249 6250 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, mem_limit, INT, ZMOD_RW, 6251 "Percentage of memory that can be used to store metaslab range trees"); 6252 6253 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, try_hard_before_gang, INT, 6254 ZMOD_RW, "Try hard to allocate before ganging"); 6255 6256 ZFS_MODULE_PARAM(zfs_metaslab, zfs_metaslab_, find_max_tries, INT, ZMOD_RW, 6257 "Normally only consider this many of the best metaslabs in each vdev"); 6258