1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 /* 22 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved. 23 * Copyright (c) 2011, 2018 by Delphix. All rights reserved. 24 * Copyright (c) 2013 by Saso Kiselkov. All rights reserved. 25 * Copyright (c) 2014 Integros [integros.com] 26 */ 27 28 #include <sys/zfs_context.h> 29 #include <sys/dmu.h> 30 #include <sys/dmu_tx.h> 31 #include <sys/space_map.h> 32 #include <sys/metaslab_impl.h> 33 #include <sys/vdev_impl.h> 34 #include <sys/zio.h> 35 #include <sys/spa_impl.h> 36 #include <sys/zfeature.h> 37 #include <sys/vdev_indirect_mapping.h> 38 #include <sys/zap.h> 39 40 #define GANG_ALLOCATION(flags) \ 41 ((flags) & (METASLAB_GANG_CHILD | METASLAB_GANG_HEADER)) 42 43 uint64_t metaslab_aliquot = 512ULL << 10; 44 uint64_t metaslab_force_ganging = SPA_MAXBLOCKSIZE + 1; /* force gang blocks */ 45 46 /* 47 * Since we can touch multiple metaslabs (and their respective space maps) 48 * with each transaction group, we benefit from having a smaller space map 49 * block size since it allows us to issue more I/O operations scattered 50 * around the disk. 51 */ 52 int zfs_metaslab_sm_blksz = (1 << 12); 53 54 /* 55 * The in-core space map representation is more compact than its on-disk form. 56 * The zfs_condense_pct determines how much more compact the in-core 57 * space map representation must be before we compact it on-disk. 58 * Values should be greater than or equal to 100. 59 */ 60 int zfs_condense_pct = 200; 61 62 /* 63 * Condensing a metaslab is not guaranteed to actually reduce the amount of 64 * space used on disk. In particular, a space map uses data in increments of 65 * MAX(1 << ashift, space_map_blksize), so a metaslab might use the 66 * same number of blocks after condensing. Since the goal of condensing is to 67 * reduce the number of IOPs required to read the space map, we only want to 68 * condense when we can be sure we will reduce the number of blocks used by the 69 * space map. Unfortunately, we cannot precisely compute whether or not this is 70 * the case in metaslab_should_condense since we are holding ms_lock. Instead, 71 * we apply the following heuristic: do not condense a spacemap unless the 72 * uncondensed size consumes greater than zfs_metaslab_condense_block_threshold 73 * blocks. 74 */ 75 int zfs_metaslab_condense_block_threshold = 4; 76 77 /* 78 * The zfs_mg_noalloc_threshold defines which metaslab groups should 79 * be eligible for allocation. The value is defined as a percentage of 80 * free space. Metaslab groups that have more free space than 81 * zfs_mg_noalloc_threshold are always eligible for allocations. Once 82 * a metaslab group's free space is less than or equal to the 83 * zfs_mg_noalloc_threshold the allocator will avoid allocating to that 84 * group unless all groups in the pool have reached zfs_mg_noalloc_threshold. 85 * Once all groups in the pool reach zfs_mg_noalloc_threshold then all 86 * groups are allowed to accept allocations. Gang blocks are always 87 * eligible to allocate on any metaslab group. The default value of 0 means 88 * no metaslab group will be excluded based on this criterion. 89 */ 90 int zfs_mg_noalloc_threshold = 0; 91 92 /* 93 * Metaslab groups are considered eligible for allocations if their 94 * fragmenation metric (measured as a percentage) is less than or equal to 95 * zfs_mg_fragmentation_threshold. If a metaslab group exceeds this threshold 96 * then it will be skipped unless all metaslab groups within the metaslab 97 * class have also crossed this threshold. 98 */ 99 int zfs_mg_fragmentation_threshold = 85; 100 101 /* 102 * Allow metaslabs to keep their active state as long as their fragmentation 103 * percentage is less than or equal to zfs_metaslab_fragmentation_threshold. An 104 * active metaslab that exceeds this threshold will no longer keep its active 105 * status allowing better metaslabs to be selected. 106 */ 107 int zfs_metaslab_fragmentation_threshold = 70; 108 109 /* 110 * When set will load all metaslabs when pool is first opened. 111 */ 112 int metaslab_debug_load = 0; 113 114 /* 115 * When set will prevent metaslabs from being unloaded. 116 */ 117 int metaslab_debug_unload = 0; 118 119 /* 120 * Minimum size which forces the dynamic allocator to change 121 * it's allocation strategy. Once the space map cannot satisfy 122 * an allocation of this size then it switches to using more 123 * aggressive strategy (i.e search by size rather than offset). 124 */ 125 uint64_t metaslab_df_alloc_threshold = SPA_OLD_MAXBLOCKSIZE; 126 127 /* 128 * The minimum free space, in percent, which must be available 129 * in a space map to continue allocations in a first-fit fashion. 130 * Once the space map's free space drops below this level we dynamically 131 * switch to using best-fit allocations. 132 */ 133 int metaslab_df_free_pct = 4; 134 135 /* 136 * A metaslab is considered "free" if it contains a contiguous 137 * segment which is greater than metaslab_min_alloc_size. 138 */ 139 uint64_t metaslab_min_alloc_size = DMU_MAX_ACCESS; 140 141 /* 142 * Percentage of all cpus that can be used by the metaslab taskq. 143 */ 144 int metaslab_load_pct = 50; 145 146 /* 147 * Determines how many txgs a metaslab may remain loaded without having any 148 * allocations from it. As long as a metaslab continues to be used we will 149 * keep it loaded. 150 */ 151 int metaslab_unload_delay = TXG_SIZE * 2; 152 153 /* 154 * Max number of metaslabs per group to preload. 155 */ 156 int metaslab_preload_limit = SPA_DVAS_PER_BP; 157 158 /* 159 * Enable/disable preloading of metaslab. 160 */ 161 boolean_t metaslab_preload_enabled = B_TRUE; 162 163 /* 164 * Enable/disable fragmentation weighting on metaslabs. 165 */ 166 boolean_t metaslab_fragmentation_factor_enabled = B_TRUE; 167 168 /* 169 * Enable/disable lba weighting (i.e. outer tracks are given preference). 170 */ 171 boolean_t metaslab_lba_weighting_enabled = B_TRUE; 172 173 /* 174 * Enable/disable metaslab group biasing. 175 */ 176 boolean_t metaslab_bias_enabled = B_TRUE; 177 178 /* 179 * Enable/disable remapping of indirect DVAs to their concrete vdevs. 180 */ 181 boolean_t zfs_remap_blkptr_enable = B_TRUE; 182 183 /* 184 * Enable/disable segment-based metaslab selection. 185 */ 186 boolean_t zfs_metaslab_segment_weight_enabled = B_TRUE; 187 188 /* 189 * When using segment-based metaslab selection, we will continue 190 * allocating from the active metaslab until we have exhausted 191 * zfs_metaslab_switch_threshold of its buckets. 192 */ 193 int zfs_metaslab_switch_threshold = 2; 194 195 /* 196 * Internal switch to enable/disable the metaslab allocation tracing 197 * facility. 198 */ 199 boolean_t metaslab_trace_enabled = B_TRUE; 200 201 /* 202 * Maximum entries that the metaslab allocation tracing facility will keep 203 * in a given list when running in non-debug mode. We limit the number 204 * of entries in non-debug mode to prevent us from using up too much memory. 205 * The limit should be sufficiently large that we don't expect any allocation 206 * to every exceed this value. In debug mode, the system will panic if this 207 * limit is ever reached allowing for further investigation. 208 */ 209 uint64_t metaslab_trace_max_entries = 5000; 210 211 static uint64_t metaslab_weight(metaslab_t *); 212 static void metaslab_set_fragmentation(metaslab_t *); 213 static void metaslab_free_impl(vdev_t *, uint64_t, uint64_t, boolean_t); 214 static void metaslab_check_free_impl(vdev_t *, uint64_t, uint64_t); 215 static void metaslab_passivate(metaslab_t *msp, uint64_t weight); 216 static uint64_t metaslab_weight_from_range_tree(metaslab_t *msp); 217 218 kmem_cache_t *metaslab_alloc_trace_cache; 219 220 /* 221 * ========================================================================== 222 * Metaslab classes 223 * ========================================================================== 224 */ 225 metaslab_class_t * 226 metaslab_class_create(spa_t *spa, metaslab_ops_t *ops) 227 { 228 metaslab_class_t *mc; 229 230 mc = kmem_zalloc(sizeof (metaslab_class_t), KM_SLEEP); 231 232 mc->mc_spa = spa; 233 mc->mc_rotor = NULL; 234 mc->mc_ops = ops; 235 mutex_init(&mc->mc_lock, NULL, MUTEX_DEFAULT, NULL); 236 mc->mc_alloc_slots = kmem_zalloc(spa->spa_alloc_count * 237 sizeof (refcount_t), KM_SLEEP); 238 mc->mc_alloc_max_slots = kmem_zalloc(spa->spa_alloc_count * 239 sizeof (uint64_t), KM_SLEEP); 240 for (int i = 0; i < spa->spa_alloc_count; i++) 241 refcount_create_tracked(&mc->mc_alloc_slots[i]); 242 243 return (mc); 244 } 245 246 void 247 metaslab_class_destroy(metaslab_class_t *mc) 248 { 249 ASSERT(mc->mc_rotor == NULL); 250 ASSERT(mc->mc_alloc == 0); 251 ASSERT(mc->mc_deferred == 0); 252 ASSERT(mc->mc_space == 0); 253 ASSERT(mc->mc_dspace == 0); 254 255 for (int i = 0; i < mc->mc_spa->spa_alloc_count; i++) 256 refcount_destroy(&mc->mc_alloc_slots[i]); 257 kmem_free(mc->mc_alloc_slots, mc->mc_spa->spa_alloc_count * 258 sizeof (refcount_t)); 259 kmem_free(mc->mc_alloc_max_slots, mc->mc_spa->spa_alloc_count * 260 sizeof (uint64_t)); 261 mutex_destroy(&mc->mc_lock); 262 kmem_free(mc, sizeof (metaslab_class_t)); 263 } 264 265 int 266 metaslab_class_validate(metaslab_class_t *mc) 267 { 268 metaslab_group_t *mg; 269 vdev_t *vd; 270 271 /* 272 * Must hold one of the spa_config locks. 273 */ 274 ASSERT(spa_config_held(mc->mc_spa, SCL_ALL, RW_READER) || 275 spa_config_held(mc->mc_spa, SCL_ALL, RW_WRITER)); 276 277 if ((mg = mc->mc_rotor) == NULL) 278 return (0); 279 280 do { 281 vd = mg->mg_vd; 282 ASSERT(vd->vdev_mg != NULL); 283 ASSERT3P(vd->vdev_top, ==, vd); 284 ASSERT3P(mg->mg_class, ==, mc); 285 ASSERT3P(vd->vdev_ops, !=, &vdev_hole_ops); 286 } while ((mg = mg->mg_next) != mc->mc_rotor); 287 288 return (0); 289 } 290 291 void 292 metaslab_class_space_update(metaslab_class_t *mc, int64_t alloc_delta, 293 int64_t defer_delta, int64_t space_delta, int64_t dspace_delta) 294 { 295 atomic_add_64(&mc->mc_alloc, alloc_delta); 296 atomic_add_64(&mc->mc_deferred, defer_delta); 297 atomic_add_64(&mc->mc_space, space_delta); 298 atomic_add_64(&mc->mc_dspace, dspace_delta); 299 } 300 301 uint64_t 302 metaslab_class_get_alloc(metaslab_class_t *mc) 303 { 304 return (mc->mc_alloc); 305 } 306 307 uint64_t 308 metaslab_class_get_deferred(metaslab_class_t *mc) 309 { 310 return (mc->mc_deferred); 311 } 312 313 uint64_t 314 metaslab_class_get_space(metaslab_class_t *mc) 315 { 316 return (mc->mc_space); 317 } 318 319 uint64_t 320 metaslab_class_get_dspace(metaslab_class_t *mc) 321 { 322 return (spa_deflate(mc->mc_spa) ? mc->mc_dspace : mc->mc_space); 323 } 324 325 void 326 metaslab_class_histogram_verify(metaslab_class_t *mc) 327 { 328 vdev_t *rvd = mc->mc_spa->spa_root_vdev; 329 uint64_t *mc_hist; 330 int i; 331 332 if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0) 333 return; 334 335 mc_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE, 336 KM_SLEEP); 337 338 for (int c = 0; c < rvd->vdev_children; c++) { 339 vdev_t *tvd = rvd->vdev_child[c]; 340 metaslab_group_t *mg = tvd->vdev_mg; 341 342 /* 343 * Skip any holes, uninitialized top-levels, or 344 * vdevs that are not in this metalab class. 345 */ 346 if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 || 347 mg->mg_class != mc) { 348 continue; 349 } 350 351 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) 352 mc_hist[i] += mg->mg_histogram[i]; 353 } 354 355 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) 356 VERIFY3U(mc_hist[i], ==, mc->mc_histogram[i]); 357 358 kmem_free(mc_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE); 359 } 360 361 /* 362 * Calculate the metaslab class's fragmentation metric. The metric 363 * is weighted based on the space contribution of each metaslab group. 364 * The return value will be a number between 0 and 100 (inclusive), or 365 * ZFS_FRAG_INVALID if the metric has not been set. See comment above the 366 * zfs_frag_table for more information about the metric. 367 */ 368 uint64_t 369 metaslab_class_fragmentation(metaslab_class_t *mc) 370 { 371 vdev_t *rvd = mc->mc_spa->spa_root_vdev; 372 uint64_t fragmentation = 0; 373 374 spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER); 375 376 for (int c = 0; c < rvd->vdev_children; c++) { 377 vdev_t *tvd = rvd->vdev_child[c]; 378 metaslab_group_t *mg = tvd->vdev_mg; 379 380 /* 381 * Skip any holes, uninitialized top-levels, 382 * or vdevs that are not in this metalab class. 383 */ 384 if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 || 385 mg->mg_class != mc) { 386 continue; 387 } 388 389 /* 390 * If a metaslab group does not contain a fragmentation 391 * metric then just bail out. 392 */ 393 if (mg->mg_fragmentation == ZFS_FRAG_INVALID) { 394 spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG); 395 return (ZFS_FRAG_INVALID); 396 } 397 398 /* 399 * Determine how much this metaslab_group is contributing 400 * to the overall pool fragmentation metric. 401 */ 402 fragmentation += mg->mg_fragmentation * 403 metaslab_group_get_space(mg); 404 } 405 fragmentation /= metaslab_class_get_space(mc); 406 407 ASSERT3U(fragmentation, <=, 100); 408 spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG); 409 return (fragmentation); 410 } 411 412 /* 413 * Calculate the amount of expandable space that is available in 414 * this metaslab class. If a device is expanded then its expandable 415 * space will be the amount of allocatable space that is currently not 416 * part of this metaslab class. 417 */ 418 uint64_t 419 metaslab_class_expandable_space(metaslab_class_t *mc) 420 { 421 vdev_t *rvd = mc->mc_spa->spa_root_vdev; 422 uint64_t space = 0; 423 424 spa_config_enter(mc->mc_spa, SCL_VDEV, FTAG, RW_READER); 425 for (int c = 0; c < rvd->vdev_children; c++) { 426 uint64_t tspace; 427 vdev_t *tvd = rvd->vdev_child[c]; 428 metaslab_group_t *mg = tvd->vdev_mg; 429 430 if (!vdev_is_concrete(tvd) || tvd->vdev_ms_shift == 0 || 431 mg->mg_class != mc) { 432 continue; 433 } 434 435 /* 436 * Calculate if we have enough space to add additional 437 * metaslabs. We report the expandable space in terms 438 * of the metaslab size since that's the unit of expansion. 439 * Adjust by efi system partition size. 440 */ 441 tspace = tvd->vdev_max_asize - tvd->vdev_asize; 442 if (tspace > mc->mc_spa->spa_bootsize) { 443 tspace -= mc->mc_spa->spa_bootsize; 444 } 445 space += P2ALIGN(tspace, 1ULL << tvd->vdev_ms_shift); 446 } 447 spa_config_exit(mc->mc_spa, SCL_VDEV, FTAG); 448 return (space); 449 } 450 451 static int 452 metaslab_compare(const void *x1, const void *x2) 453 { 454 const metaslab_t *m1 = x1; 455 const metaslab_t *m2 = x2; 456 457 int sort1 = 0; 458 int sort2 = 0; 459 if (m1->ms_allocator != -1 && m1->ms_primary) 460 sort1 = 1; 461 else if (m1->ms_allocator != -1 && !m1->ms_primary) 462 sort1 = 2; 463 if (m2->ms_allocator != -1 && m2->ms_primary) 464 sort2 = 1; 465 else if (m2->ms_allocator != -1 && !m2->ms_primary) 466 sort2 = 2; 467 468 /* 469 * Sort inactive metaslabs first, then primaries, then secondaries. When 470 * selecting a metaslab to allocate from, an allocator first tries its 471 * primary, then secondary active metaslab. If it doesn't have active 472 * metaslabs, or can't allocate from them, it searches for an inactive 473 * metaslab to activate. If it can't find a suitable one, it will steal 474 * a primary or secondary metaslab from another allocator. 475 */ 476 if (sort1 < sort2) 477 return (-1); 478 if (sort1 > sort2) 479 return (1); 480 481 if (m1->ms_weight < m2->ms_weight) 482 return (1); 483 if (m1->ms_weight > m2->ms_weight) 484 return (-1); 485 486 /* 487 * If the weights are identical, use the offset to force uniqueness. 488 */ 489 if (m1->ms_start < m2->ms_start) 490 return (-1); 491 if (m1->ms_start > m2->ms_start) 492 return (1); 493 494 ASSERT3P(m1, ==, m2); 495 496 return (0); 497 } 498 499 /* 500 * Verify that the space accounting on disk matches the in-core range_trees. 501 */ 502 void 503 metaslab_verify_space(metaslab_t *msp, uint64_t txg) 504 { 505 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 506 uint64_t allocated = 0; 507 uint64_t sm_free_space, msp_free_space; 508 509 ASSERT(MUTEX_HELD(&msp->ms_lock)); 510 511 if ((zfs_flags & ZFS_DEBUG_METASLAB_VERIFY) == 0) 512 return; 513 514 /* 515 * We can only verify the metaslab space when we're called 516 * from syncing context with a loaded metaslab that has an allocated 517 * space map. Calling this in non-syncing context does not 518 * provide a consistent view of the metaslab since we're performing 519 * allocations in the future. 520 */ 521 if (txg != spa_syncing_txg(spa) || msp->ms_sm == NULL || 522 !msp->ms_loaded) 523 return; 524 525 sm_free_space = msp->ms_size - space_map_allocated(msp->ms_sm) - 526 space_map_alloc_delta(msp->ms_sm); 527 528 /* 529 * Account for future allocations since we would have already 530 * deducted that space from the ms_freetree. 531 */ 532 for (int t = 0; t < TXG_CONCURRENT_STATES; t++) { 533 allocated += 534 range_tree_space(msp->ms_allocating[(txg + t) & TXG_MASK]); 535 } 536 537 msp_free_space = range_tree_space(msp->ms_allocatable) + allocated + 538 msp->ms_deferspace + range_tree_space(msp->ms_freed); 539 540 VERIFY3U(sm_free_space, ==, msp_free_space); 541 } 542 543 /* 544 * ========================================================================== 545 * Metaslab groups 546 * ========================================================================== 547 */ 548 /* 549 * Update the allocatable flag and the metaslab group's capacity. 550 * The allocatable flag is set to true if the capacity is below 551 * the zfs_mg_noalloc_threshold or has a fragmentation value that is 552 * greater than zfs_mg_fragmentation_threshold. If a metaslab group 553 * transitions from allocatable to non-allocatable or vice versa then the 554 * metaslab group's class is updated to reflect the transition. 555 */ 556 static void 557 metaslab_group_alloc_update(metaslab_group_t *mg) 558 { 559 vdev_t *vd = mg->mg_vd; 560 metaslab_class_t *mc = mg->mg_class; 561 vdev_stat_t *vs = &vd->vdev_stat; 562 boolean_t was_allocatable; 563 boolean_t was_initialized; 564 565 ASSERT(vd == vd->vdev_top); 566 ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_READER), ==, 567 SCL_ALLOC); 568 569 mutex_enter(&mg->mg_lock); 570 was_allocatable = mg->mg_allocatable; 571 was_initialized = mg->mg_initialized; 572 573 mg->mg_free_capacity = ((vs->vs_space - vs->vs_alloc) * 100) / 574 (vs->vs_space + 1); 575 576 mutex_enter(&mc->mc_lock); 577 578 /* 579 * If the metaslab group was just added then it won't 580 * have any space until we finish syncing out this txg. 581 * At that point we will consider it initialized and available 582 * for allocations. We also don't consider non-activated 583 * metaslab groups (e.g. vdevs that are in the middle of being removed) 584 * to be initialized, because they can't be used for allocation. 585 */ 586 mg->mg_initialized = metaslab_group_initialized(mg); 587 if (!was_initialized && mg->mg_initialized) { 588 mc->mc_groups++; 589 } else if (was_initialized && !mg->mg_initialized) { 590 ASSERT3U(mc->mc_groups, >, 0); 591 mc->mc_groups--; 592 } 593 if (mg->mg_initialized) 594 mg->mg_no_free_space = B_FALSE; 595 596 /* 597 * A metaslab group is considered allocatable if it has plenty 598 * of free space or is not heavily fragmented. We only take 599 * fragmentation into account if the metaslab group has a valid 600 * fragmentation metric (i.e. a value between 0 and 100). 601 */ 602 mg->mg_allocatable = (mg->mg_activation_count > 0 && 603 mg->mg_free_capacity > zfs_mg_noalloc_threshold && 604 (mg->mg_fragmentation == ZFS_FRAG_INVALID || 605 mg->mg_fragmentation <= zfs_mg_fragmentation_threshold)); 606 607 /* 608 * The mc_alloc_groups maintains a count of the number of 609 * groups in this metaslab class that are still above the 610 * zfs_mg_noalloc_threshold. This is used by the allocating 611 * threads to determine if they should avoid allocations to 612 * a given group. The allocator will avoid allocations to a group 613 * if that group has reached or is below the zfs_mg_noalloc_threshold 614 * and there are still other groups that are above the threshold. 615 * When a group transitions from allocatable to non-allocatable or 616 * vice versa we update the metaslab class to reflect that change. 617 * When the mc_alloc_groups value drops to 0 that means that all 618 * groups have reached the zfs_mg_noalloc_threshold making all groups 619 * eligible for allocations. This effectively means that all devices 620 * are balanced again. 621 */ 622 if (was_allocatable && !mg->mg_allocatable) 623 mc->mc_alloc_groups--; 624 else if (!was_allocatable && mg->mg_allocatable) 625 mc->mc_alloc_groups++; 626 mutex_exit(&mc->mc_lock); 627 628 mutex_exit(&mg->mg_lock); 629 } 630 631 metaslab_group_t * 632 metaslab_group_create(metaslab_class_t *mc, vdev_t *vd, int allocators) 633 { 634 metaslab_group_t *mg; 635 636 mg = kmem_zalloc(sizeof (metaslab_group_t), KM_SLEEP); 637 mutex_init(&mg->mg_lock, NULL, MUTEX_DEFAULT, NULL); 638 mutex_init(&mg->mg_ms_initialize_lock, NULL, MUTEX_DEFAULT, NULL); 639 cv_init(&mg->mg_ms_initialize_cv, NULL, CV_DEFAULT, NULL); 640 mg->mg_primaries = kmem_zalloc(allocators * sizeof (metaslab_t *), 641 KM_SLEEP); 642 mg->mg_secondaries = kmem_zalloc(allocators * sizeof (metaslab_t *), 643 KM_SLEEP); 644 avl_create(&mg->mg_metaslab_tree, metaslab_compare, 645 sizeof (metaslab_t), offsetof(struct metaslab, ms_group_node)); 646 mg->mg_vd = vd; 647 mg->mg_class = mc; 648 mg->mg_activation_count = 0; 649 mg->mg_initialized = B_FALSE; 650 mg->mg_no_free_space = B_TRUE; 651 mg->mg_allocators = allocators; 652 653 mg->mg_alloc_queue_depth = kmem_zalloc(allocators * sizeof (refcount_t), 654 KM_SLEEP); 655 mg->mg_cur_max_alloc_queue_depth = kmem_zalloc(allocators * 656 sizeof (uint64_t), KM_SLEEP); 657 for (int i = 0; i < allocators; i++) { 658 refcount_create_tracked(&mg->mg_alloc_queue_depth[i]); 659 mg->mg_cur_max_alloc_queue_depth[i] = 0; 660 } 661 662 mg->mg_taskq = taskq_create("metaslab_group_taskq", metaslab_load_pct, 663 minclsyspri, 10, INT_MAX, TASKQ_THREADS_CPU_PCT); 664 665 return (mg); 666 } 667 668 void 669 metaslab_group_destroy(metaslab_group_t *mg) 670 { 671 ASSERT(mg->mg_prev == NULL); 672 ASSERT(mg->mg_next == NULL); 673 /* 674 * We may have gone below zero with the activation count 675 * either because we never activated in the first place or 676 * because we're done, and possibly removing the vdev. 677 */ 678 ASSERT(mg->mg_activation_count <= 0); 679 680 taskq_destroy(mg->mg_taskq); 681 avl_destroy(&mg->mg_metaslab_tree); 682 kmem_free(mg->mg_primaries, mg->mg_allocators * sizeof (metaslab_t *)); 683 kmem_free(mg->mg_secondaries, mg->mg_allocators * 684 sizeof (metaslab_t *)); 685 mutex_destroy(&mg->mg_lock); 686 mutex_destroy(&mg->mg_ms_initialize_lock); 687 cv_destroy(&mg->mg_ms_initialize_cv); 688 689 for (int i = 0; i < mg->mg_allocators; i++) { 690 refcount_destroy(&mg->mg_alloc_queue_depth[i]); 691 mg->mg_cur_max_alloc_queue_depth[i] = 0; 692 } 693 kmem_free(mg->mg_alloc_queue_depth, mg->mg_allocators * 694 sizeof (refcount_t)); 695 kmem_free(mg->mg_cur_max_alloc_queue_depth, mg->mg_allocators * 696 sizeof (uint64_t)); 697 698 kmem_free(mg, sizeof (metaslab_group_t)); 699 } 700 701 void 702 metaslab_group_activate(metaslab_group_t *mg) 703 { 704 metaslab_class_t *mc = mg->mg_class; 705 metaslab_group_t *mgprev, *mgnext; 706 707 ASSERT3U(spa_config_held(mc->mc_spa, SCL_ALLOC, RW_WRITER), !=, 0); 708 709 ASSERT(mc->mc_rotor != mg); 710 ASSERT(mg->mg_prev == NULL); 711 ASSERT(mg->mg_next == NULL); 712 ASSERT(mg->mg_activation_count <= 0); 713 714 if (++mg->mg_activation_count <= 0) 715 return; 716 717 mg->mg_aliquot = metaslab_aliquot * MAX(1, mg->mg_vd->vdev_children); 718 metaslab_group_alloc_update(mg); 719 720 if ((mgprev = mc->mc_rotor) == NULL) { 721 mg->mg_prev = mg; 722 mg->mg_next = mg; 723 } else { 724 mgnext = mgprev->mg_next; 725 mg->mg_prev = mgprev; 726 mg->mg_next = mgnext; 727 mgprev->mg_next = mg; 728 mgnext->mg_prev = mg; 729 } 730 mc->mc_rotor = mg; 731 } 732 733 /* 734 * Passivate a metaslab group and remove it from the allocation rotor. 735 * Callers must hold both the SCL_ALLOC and SCL_ZIO lock prior to passivating 736 * a metaslab group. This function will momentarily drop spa_config_locks 737 * that are lower than the SCL_ALLOC lock (see comment below). 738 */ 739 void 740 metaslab_group_passivate(metaslab_group_t *mg) 741 { 742 metaslab_class_t *mc = mg->mg_class; 743 spa_t *spa = mc->mc_spa; 744 metaslab_group_t *mgprev, *mgnext; 745 int locks = spa_config_held(spa, SCL_ALL, RW_WRITER); 746 747 ASSERT3U(spa_config_held(spa, SCL_ALLOC | SCL_ZIO, RW_WRITER), ==, 748 (SCL_ALLOC | SCL_ZIO)); 749 750 if (--mg->mg_activation_count != 0) { 751 ASSERT(mc->mc_rotor != mg); 752 ASSERT(mg->mg_prev == NULL); 753 ASSERT(mg->mg_next == NULL); 754 ASSERT(mg->mg_activation_count < 0); 755 return; 756 } 757 758 /* 759 * The spa_config_lock is an array of rwlocks, ordered as 760 * follows (from highest to lowest): 761 * SCL_CONFIG > SCL_STATE > SCL_L2ARC > SCL_ALLOC > 762 * SCL_ZIO > SCL_FREE > SCL_VDEV 763 * (For more information about the spa_config_lock see spa_misc.c) 764 * The higher the lock, the broader its coverage. When we passivate 765 * a metaslab group, we must hold both the SCL_ALLOC and the SCL_ZIO 766 * config locks. However, the metaslab group's taskq might be trying 767 * to preload metaslabs so we must drop the SCL_ZIO lock and any 768 * lower locks to allow the I/O to complete. At a minimum, 769 * we continue to hold the SCL_ALLOC lock, which prevents any future 770 * allocations from taking place and any changes to the vdev tree. 771 */ 772 spa_config_exit(spa, locks & ~(SCL_ZIO - 1), spa); 773 taskq_wait(mg->mg_taskq); 774 spa_config_enter(spa, locks & ~(SCL_ZIO - 1), spa, RW_WRITER); 775 metaslab_group_alloc_update(mg); 776 for (int i = 0; i < mg->mg_allocators; i++) { 777 metaslab_t *msp = mg->mg_primaries[i]; 778 if (msp != NULL) { 779 mutex_enter(&msp->ms_lock); 780 metaslab_passivate(msp, 781 metaslab_weight_from_range_tree(msp)); 782 mutex_exit(&msp->ms_lock); 783 } 784 msp = mg->mg_secondaries[i]; 785 if (msp != NULL) { 786 mutex_enter(&msp->ms_lock); 787 metaslab_passivate(msp, 788 metaslab_weight_from_range_tree(msp)); 789 mutex_exit(&msp->ms_lock); 790 } 791 } 792 793 mgprev = mg->mg_prev; 794 mgnext = mg->mg_next; 795 796 if (mg == mgnext) { 797 mc->mc_rotor = NULL; 798 } else { 799 mc->mc_rotor = mgnext; 800 mgprev->mg_next = mgnext; 801 mgnext->mg_prev = mgprev; 802 } 803 804 mg->mg_prev = NULL; 805 mg->mg_next = NULL; 806 } 807 808 boolean_t 809 metaslab_group_initialized(metaslab_group_t *mg) 810 { 811 vdev_t *vd = mg->mg_vd; 812 vdev_stat_t *vs = &vd->vdev_stat; 813 814 return (vs->vs_space != 0 && mg->mg_activation_count > 0); 815 } 816 817 uint64_t 818 metaslab_group_get_space(metaslab_group_t *mg) 819 { 820 return ((1ULL << mg->mg_vd->vdev_ms_shift) * mg->mg_vd->vdev_ms_count); 821 } 822 823 void 824 metaslab_group_histogram_verify(metaslab_group_t *mg) 825 { 826 uint64_t *mg_hist; 827 vdev_t *vd = mg->mg_vd; 828 uint64_t ashift = vd->vdev_ashift; 829 int i; 830 831 if ((zfs_flags & ZFS_DEBUG_HISTOGRAM_VERIFY) == 0) 832 return; 833 834 mg_hist = kmem_zalloc(sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE, 835 KM_SLEEP); 836 837 ASSERT3U(RANGE_TREE_HISTOGRAM_SIZE, >=, 838 SPACE_MAP_HISTOGRAM_SIZE + ashift); 839 840 for (int m = 0; m < vd->vdev_ms_count; m++) { 841 metaslab_t *msp = vd->vdev_ms[m]; 842 843 if (msp->ms_sm == NULL) 844 continue; 845 846 for (i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) 847 mg_hist[i + ashift] += 848 msp->ms_sm->sm_phys->smp_histogram[i]; 849 } 850 851 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i ++) 852 VERIFY3U(mg_hist[i], ==, mg->mg_histogram[i]); 853 854 kmem_free(mg_hist, sizeof (uint64_t) * RANGE_TREE_HISTOGRAM_SIZE); 855 } 856 857 static void 858 metaslab_group_histogram_add(metaslab_group_t *mg, metaslab_t *msp) 859 { 860 metaslab_class_t *mc = mg->mg_class; 861 uint64_t ashift = mg->mg_vd->vdev_ashift; 862 863 ASSERT(MUTEX_HELD(&msp->ms_lock)); 864 if (msp->ms_sm == NULL) 865 return; 866 867 mutex_enter(&mg->mg_lock); 868 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 869 mg->mg_histogram[i + ashift] += 870 msp->ms_sm->sm_phys->smp_histogram[i]; 871 mc->mc_histogram[i + ashift] += 872 msp->ms_sm->sm_phys->smp_histogram[i]; 873 } 874 mutex_exit(&mg->mg_lock); 875 } 876 877 void 878 metaslab_group_histogram_remove(metaslab_group_t *mg, metaslab_t *msp) 879 { 880 metaslab_class_t *mc = mg->mg_class; 881 uint64_t ashift = mg->mg_vd->vdev_ashift; 882 883 ASSERT(MUTEX_HELD(&msp->ms_lock)); 884 if (msp->ms_sm == NULL) 885 return; 886 887 mutex_enter(&mg->mg_lock); 888 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 889 ASSERT3U(mg->mg_histogram[i + ashift], >=, 890 msp->ms_sm->sm_phys->smp_histogram[i]); 891 ASSERT3U(mc->mc_histogram[i + ashift], >=, 892 msp->ms_sm->sm_phys->smp_histogram[i]); 893 894 mg->mg_histogram[i + ashift] -= 895 msp->ms_sm->sm_phys->smp_histogram[i]; 896 mc->mc_histogram[i + ashift] -= 897 msp->ms_sm->sm_phys->smp_histogram[i]; 898 } 899 mutex_exit(&mg->mg_lock); 900 } 901 902 static void 903 metaslab_group_add(metaslab_group_t *mg, metaslab_t *msp) 904 { 905 ASSERT(msp->ms_group == NULL); 906 mutex_enter(&mg->mg_lock); 907 msp->ms_group = mg; 908 msp->ms_weight = 0; 909 avl_add(&mg->mg_metaslab_tree, msp); 910 mutex_exit(&mg->mg_lock); 911 912 mutex_enter(&msp->ms_lock); 913 metaslab_group_histogram_add(mg, msp); 914 mutex_exit(&msp->ms_lock); 915 } 916 917 static void 918 metaslab_group_remove(metaslab_group_t *mg, metaslab_t *msp) 919 { 920 mutex_enter(&msp->ms_lock); 921 metaslab_group_histogram_remove(mg, msp); 922 mutex_exit(&msp->ms_lock); 923 924 mutex_enter(&mg->mg_lock); 925 ASSERT(msp->ms_group == mg); 926 avl_remove(&mg->mg_metaslab_tree, msp); 927 msp->ms_group = NULL; 928 mutex_exit(&mg->mg_lock); 929 } 930 931 static void 932 metaslab_group_sort_impl(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight) 933 { 934 ASSERT(MUTEX_HELD(&mg->mg_lock)); 935 ASSERT(msp->ms_group == mg); 936 avl_remove(&mg->mg_metaslab_tree, msp); 937 msp->ms_weight = weight; 938 avl_add(&mg->mg_metaslab_tree, msp); 939 940 } 941 942 static void 943 metaslab_group_sort(metaslab_group_t *mg, metaslab_t *msp, uint64_t weight) 944 { 945 /* 946 * Although in principle the weight can be any value, in 947 * practice we do not use values in the range [1, 511]. 948 */ 949 ASSERT(weight >= SPA_MINBLOCKSIZE || weight == 0); 950 ASSERT(MUTEX_HELD(&msp->ms_lock)); 951 952 mutex_enter(&mg->mg_lock); 953 metaslab_group_sort_impl(mg, msp, weight); 954 mutex_exit(&mg->mg_lock); 955 } 956 957 /* 958 * Calculate the fragmentation for a given metaslab group. We can use 959 * a simple average here since all metaslabs within the group must have 960 * the same size. The return value will be a value between 0 and 100 961 * (inclusive), or ZFS_FRAG_INVALID if less than half of the metaslab in this 962 * group have a fragmentation metric. 963 */ 964 uint64_t 965 metaslab_group_fragmentation(metaslab_group_t *mg) 966 { 967 vdev_t *vd = mg->mg_vd; 968 uint64_t fragmentation = 0; 969 uint64_t valid_ms = 0; 970 971 for (int m = 0; m < vd->vdev_ms_count; m++) { 972 metaslab_t *msp = vd->vdev_ms[m]; 973 974 if (msp->ms_fragmentation == ZFS_FRAG_INVALID) 975 continue; 976 977 valid_ms++; 978 fragmentation += msp->ms_fragmentation; 979 } 980 981 if (valid_ms <= vd->vdev_ms_count / 2) 982 return (ZFS_FRAG_INVALID); 983 984 fragmentation /= valid_ms; 985 ASSERT3U(fragmentation, <=, 100); 986 return (fragmentation); 987 } 988 989 /* 990 * Determine if a given metaslab group should skip allocations. A metaslab 991 * group should avoid allocations if its free capacity is less than the 992 * zfs_mg_noalloc_threshold or its fragmentation metric is greater than 993 * zfs_mg_fragmentation_threshold and there is at least one metaslab group 994 * that can still handle allocations. If the allocation throttle is enabled 995 * then we skip allocations to devices that have reached their maximum 996 * allocation queue depth unless the selected metaslab group is the only 997 * eligible group remaining. 998 */ 999 static boolean_t 1000 metaslab_group_allocatable(metaslab_group_t *mg, metaslab_group_t *rotor, 1001 uint64_t psize, int allocator) 1002 { 1003 spa_t *spa = mg->mg_vd->vdev_spa; 1004 metaslab_class_t *mc = mg->mg_class; 1005 1006 /* 1007 * We can only consider skipping this metaslab group if it's 1008 * in the normal metaslab class and there are other metaslab 1009 * groups to select from. Otherwise, we always consider it eligible 1010 * for allocations. 1011 */ 1012 if (mc != spa_normal_class(spa) || mc->mc_groups <= 1) 1013 return (B_TRUE); 1014 1015 /* 1016 * If the metaslab group's mg_allocatable flag is set (see comments 1017 * in metaslab_group_alloc_update() for more information) and 1018 * the allocation throttle is disabled then allow allocations to this 1019 * device. However, if the allocation throttle is enabled then 1020 * check if we have reached our allocation limit (mg_alloc_queue_depth) 1021 * to determine if we should allow allocations to this metaslab group. 1022 * If all metaslab groups are no longer considered allocatable 1023 * (mc_alloc_groups == 0) or we're trying to allocate the smallest 1024 * gang block size then we allow allocations on this metaslab group 1025 * regardless of the mg_allocatable or throttle settings. 1026 */ 1027 if (mg->mg_allocatable) { 1028 metaslab_group_t *mgp; 1029 int64_t qdepth; 1030 uint64_t qmax = mg->mg_cur_max_alloc_queue_depth[allocator]; 1031 1032 if (!mc->mc_alloc_throttle_enabled) 1033 return (B_TRUE); 1034 1035 /* 1036 * If this metaslab group does not have any free space, then 1037 * there is no point in looking further. 1038 */ 1039 if (mg->mg_no_free_space) 1040 return (B_FALSE); 1041 1042 qdepth = refcount_count(&mg->mg_alloc_queue_depth[allocator]); 1043 1044 /* 1045 * If this metaslab group is below its qmax or it's 1046 * the only allocatable metasable group, then attempt 1047 * to allocate from it. 1048 */ 1049 if (qdepth < qmax || mc->mc_alloc_groups == 1) 1050 return (B_TRUE); 1051 ASSERT3U(mc->mc_alloc_groups, >, 1); 1052 1053 /* 1054 * Since this metaslab group is at or over its qmax, we 1055 * need to determine if there are metaslab groups after this 1056 * one that might be able to handle this allocation. This is 1057 * racy since we can't hold the locks for all metaslab 1058 * groups at the same time when we make this check. 1059 */ 1060 for (mgp = mg->mg_next; mgp != rotor; mgp = mgp->mg_next) { 1061 qmax = mgp->mg_cur_max_alloc_queue_depth[allocator]; 1062 1063 qdepth = refcount_count( 1064 &mgp->mg_alloc_queue_depth[allocator]); 1065 1066 /* 1067 * If there is another metaslab group that 1068 * might be able to handle the allocation, then 1069 * we return false so that we skip this group. 1070 */ 1071 if (qdepth < qmax && !mgp->mg_no_free_space) 1072 return (B_FALSE); 1073 } 1074 1075 /* 1076 * We didn't find another group to handle the allocation 1077 * so we can't skip this metaslab group even though 1078 * we are at or over our qmax. 1079 */ 1080 return (B_TRUE); 1081 1082 } else if (mc->mc_alloc_groups == 0 || psize == SPA_MINBLOCKSIZE) { 1083 return (B_TRUE); 1084 } 1085 return (B_FALSE); 1086 } 1087 1088 /* 1089 * ========================================================================== 1090 * Range tree callbacks 1091 * ========================================================================== 1092 */ 1093 1094 /* 1095 * Comparison function for the private size-ordered tree. Tree is sorted 1096 * by size, larger sizes at the end of the tree. 1097 */ 1098 static int 1099 metaslab_rangesize_compare(const void *x1, const void *x2) 1100 { 1101 const range_seg_t *r1 = x1; 1102 const range_seg_t *r2 = x2; 1103 uint64_t rs_size1 = r1->rs_end - r1->rs_start; 1104 uint64_t rs_size2 = r2->rs_end - r2->rs_start; 1105 1106 if (rs_size1 < rs_size2) 1107 return (-1); 1108 if (rs_size1 > rs_size2) 1109 return (1); 1110 1111 if (r1->rs_start < r2->rs_start) 1112 return (-1); 1113 1114 if (r1->rs_start > r2->rs_start) 1115 return (1); 1116 1117 return (0); 1118 } 1119 1120 /* 1121 * Create any block allocator specific components. The current allocators 1122 * rely on using both a size-ordered range_tree_t and an array of uint64_t's. 1123 */ 1124 static void 1125 metaslab_rt_create(range_tree_t *rt, void *arg) 1126 { 1127 metaslab_t *msp = arg; 1128 1129 ASSERT3P(rt->rt_arg, ==, msp); 1130 ASSERT(msp->ms_allocatable == NULL); 1131 1132 avl_create(&msp->ms_allocatable_by_size, metaslab_rangesize_compare, 1133 sizeof (range_seg_t), offsetof(range_seg_t, rs_pp_node)); 1134 } 1135 1136 /* 1137 * Destroy the block allocator specific components. 1138 */ 1139 static void 1140 metaslab_rt_destroy(range_tree_t *rt, void *arg) 1141 { 1142 metaslab_t *msp = arg; 1143 1144 ASSERT3P(rt->rt_arg, ==, msp); 1145 ASSERT3P(msp->ms_allocatable, ==, rt); 1146 ASSERT0(avl_numnodes(&msp->ms_allocatable_by_size)); 1147 1148 avl_destroy(&msp->ms_allocatable_by_size); 1149 } 1150 1151 static void 1152 metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg) 1153 { 1154 metaslab_t *msp = arg; 1155 1156 ASSERT3P(rt->rt_arg, ==, msp); 1157 ASSERT3P(msp->ms_allocatable, ==, rt); 1158 VERIFY(!msp->ms_condensing); 1159 avl_add(&msp->ms_allocatable_by_size, rs); 1160 } 1161 1162 static void 1163 metaslab_rt_remove(range_tree_t *rt, range_seg_t *rs, void *arg) 1164 { 1165 metaslab_t *msp = arg; 1166 1167 ASSERT3P(rt->rt_arg, ==, msp); 1168 ASSERT3P(msp->ms_allocatable, ==, rt); 1169 VERIFY(!msp->ms_condensing); 1170 avl_remove(&msp->ms_allocatable_by_size, rs); 1171 } 1172 1173 static void 1174 metaslab_rt_vacate(range_tree_t *rt, void *arg) 1175 { 1176 metaslab_t *msp = arg; 1177 1178 ASSERT3P(rt->rt_arg, ==, msp); 1179 ASSERT3P(msp->ms_allocatable, ==, rt); 1180 1181 /* 1182 * Normally one would walk the tree freeing nodes along the way. 1183 * Since the nodes are shared with the range trees we can avoid 1184 * walking all nodes and just reinitialize the avl tree. The nodes 1185 * will be freed by the range tree, so we don't want to free them here. 1186 */ 1187 avl_create(&msp->ms_allocatable_by_size, metaslab_rangesize_compare, 1188 sizeof (range_seg_t), offsetof(range_seg_t, rs_pp_node)); 1189 } 1190 1191 static range_tree_ops_t metaslab_rt_ops = { 1192 metaslab_rt_create, 1193 metaslab_rt_destroy, 1194 metaslab_rt_add, 1195 metaslab_rt_remove, 1196 metaslab_rt_vacate 1197 }; 1198 1199 /* 1200 * ========================================================================== 1201 * Common allocator routines 1202 * ========================================================================== 1203 */ 1204 1205 /* 1206 * Return the maximum contiguous segment within the metaslab. 1207 */ 1208 uint64_t 1209 metaslab_block_maxsize(metaslab_t *msp) 1210 { 1211 avl_tree_t *t = &msp->ms_allocatable_by_size; 1212 range_seg_t *rs; 1213 1214 if (t == NULL || (rs = avl_last(t)) == NULL) 1215 return (0ULL); 1216 1217 return (rs->rs_end - rs->rs_start); 1218 } 1219 1220 static range_seg_t * 1221 metaslab_block_find(avl_tree_t *t, uint64_t start, uint64_t size) 1222 { 1223 range_seg_t *rs, rsearch; 1224 avl_index_t where; 1225 1226 rsearch.rs_start = start; 1227 rsearch.rs_end = start + size; 1228 1229 rs = avl_find(t, &rsearch, &where); 1230 if (rs == NULL) { 1231 rs = avl_nearest(t, where, AVL_AFTER); 1232 } 1233 1234 return (rs); 1235 } 1236 1237 /* 1238 * This is a helper function that can be used by the allocator to find 1239 * a suitable block to allocate. This will search the specified AVL 1240 * tree looking for a block that matches the specified criteria. 1241 */ 1242 static uint64_t 1243 metaslab_block_picker(avl_tree_t *t, uint64_t *cursor, uint64_t size, 1244 uint64_t align) 1245 { 1246 range_seg_t *rs = metaslab_block_find(t, *cursor, size); 1247 1248 while (rs != NULL) { 1249 uint64_t offset = P2ROUNDUP(rs->rs_start, align); 1250 1251 if (offset + size <= rs->rs_end) { 1252 *cursor = offset + size; 1253 return (offset); 1254 } 1255 rs = AVL_NEXT(t, rs); 1256 } 1257 1258 /* 1259 * If we know we've searched the whole map (*cursor == 0), give up. 1260 * Otherwise, reset the cursor to the beginning and try again. 1261 */ 1262 if (*cursor == 0) 1263 return (-1ULL); 1264 1265 *cursor = 0; 1266 return (metaslab_block_picker(t, cursor, size, align)); 1267 } 1268 1269 /* 1270 * ========================================================================== 1271 * The first-fit block allocator 1272 * ========================================================================== 1273 */ 1274 static uint64_t 1275 metaslab_ff_alloc(metaslab_t *msp, uint64_t size) 1276 { 1277 /* 1278 * Find the largest power of 2 block size that evenly divides the 1279 * requested size. This is used to try to allocate blocks with similar 1280 * alignment from the same area of the metaslab (i.e. same cursor 1281 * bucket) but it does not guarantee that other allocations sizes 1282 * may exist in the same region. 1283 */ 1284 uint64_t align = size & -size; 1285 uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1]; 1286 avl_tree_t *t = &msp->ms_allocatable->rt_root; 1287 1288 return (metaslab_block_picker(t, cursor, size, align)); 1289 } 1290 1291 static metaslab_ops_t metaslab_ff_ops = { 1292 metaslab_ff_alloc 1293 }; 1294 1295 /* 1296 * ========================================================================== 1297 * Dynamic block allocator - 1298 * Uses the first fit allocation scheme until space get low and then 1299 * adjusts to a best fit allocation method. Uses metaslab_df_alloc_threshold 1300 * and metaslab_df_free_pct to determine when to switch the allocation scheme. 1301 * ========================================================================== 1302 */ 1303 static uint64_t 1304 metaslab_df_alloc(metaslab_t *msp, uint64_t size) 1305 { 1306 /* 1307 * Find the largest power of 2 block size that evenly divides the 1308 * requested size. This is used to try to allocate blocks with similar 1309 * alignment from the same area of the metaslab (i.e. same cursor 1310 * bucket) but it does not guarantee that other allocations sizes 1311 * may exist in the same region. 1312 */ 1313 uint64_t align = size & -size; 1314 uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1]; 1315 range_tree_t *rt = msp->ms_allocatable; 1316 avl_tree_t *t = &rt->rt_root; 1317 uint64_t max_size = metaslab_block_maxsize(msp); 1318 int free_pct = range_tree_space(rt) * 100 / msp->ms_size; 1319 1320 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1321 ASSERT3U(avl_numnodes(t), ==, 1322 avl_numnodes(&msp->ms_allocatable_by_size)); 1323 1324 if (max_size < size) 1325 return (-1ULL); 1326 1327 /* 1328 * If we're running low on space switch to using the size 1329 * sorted AVL tree (best-fit). 1330 */ 1331 if (max_size < metaslab_df_alloc_threshold || 1332 free_pct < metaslab_df_free_pct) { 1333 t = &msp->ms_allocatable_by_size; 1334 *cursor = 0; 1335 } 1336 1337 return (metaslab_block_picker(t, cursor, size, 1ULL)); 1338 } 1339 1340 static metaslab_ops_t metaslab_df_ops = { 1341 metaslab_df_alloc 1342 }; 1343 1344 /* 1345 * ========================================================================== 1346 * Cursor fit block allocator - 1347 * Select the largest region in the metaslab, set the cursor to the beginning 1348 * of the range and the cursor_end to the end of the range. As allocations 1349 * are made advance the cursor. Continue allocating from the cursor until 1350 * the range is exhausted and then find a new range. 1351 * ========================================================================== 1352 */ 1353 static uint64_t 1354 metaslab_cf_alloc(metaslab_t *msp, uint64_t size) 1355 { 1356 range_tree_t *rt = msp->ms_allocatable; 1357 avl_tree_t *t = &msp->ms_allocatable_by_size; 1358 uint64_t *cursor = &msp->ms_lbas[0]; 1359 uint64_t *cursor_end = &msp->ms_lbas[1]; 1360 uint64_t offset = 0; 1361 1362 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1363 ASSERT3U(avl_numnodes(t), ==, avl_numnodes(&rt->rt_root)); 1364 1365 ASSERT3U(*cursor_end, >=, *cursor); 1366 1367 if ((*cursor + size) > *cursor_end) { 1368 range_seg_t *rs; 1369 1370 rs = avl_last(&msp->ms_allocatable_by_size); 1371 if (rs == NULL || (rs->rs_end - rs->rs_start) < size) 1372 return (-1ULL); 1373 1374 *cursor = rs->rs_start; 1375 *cursor_end = rs->rs_end; 1376 } 1377 1378 offset = *cursor; 1379 *cursor += size; 1380 1381 return (offset); 1382 } 1383 1384 static metaslab_ops_t metaslab_cf_ops = { 1385 metaslab_cf_alloc 1386 }; 1387 1388 /* 1389 * ========================================================================== 1390 * New dynamic fit allocator - 1391 * Select a region that is large enough to allocate 2^metaslab_ndf_clump_shift 1392 * contiguous blocks. If no region is found then just use the largest segment 1393 * that remains. 1394 * ========================================================================== 1395 */ 1396 1397 /* 1398 * Determines desired number of contiguous blocks (2^metaslab_ndf_clump_shift) 1399 * to request from the allocator. 1400 */ 1401 uint64_t metaslab_ndf_clump_shift = 4; 1402 1403 static uint64_t 1404 metaslab_ndf_alloc(metaslab_t *msp, uint64_t size) 1405 { 1406 avl_tree_t *t = &msp->ms_allocatable->rt_root; 1407 avl_index_t where; 1408 range_seg_t *rs, rsearch; 1409 uint64_t hbit = highbit64(size); 1410 uint64_t *cursor = &msp->ms_lbas[hbit - 1]; 1411 uint64_t max_size = metaslab_block_maxsize(msp); 1412 1413 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1414 ASSERT3U(avl_numnodes(t), ==, 1415 avl_numnodes(&msp->ms_allocatable_by_size)); 1416 1417 if (max_size < size) 1418 return (-1ULL); 1419 1420 rsearch.rs_start = *cursor; 1421 rsearch.rs_end = *cursor + size; 1422 1423 rs = avl_find(t, &rsearch, &where); 1424 if (rs == NULL || (rs->rs_end - rs->rs_start) < size) { 1425 t = &msp->ms_allocatable_by_size; 1426 1427 rsearch.rs_start = 0; 1428 rsearch.rs_end = MIN(max_size, 1429 1ULL << (hbit + metaslab_ndf_clump_shift)); 1430 rs = avl_find(t, &rsearch, &where); 1431 if (rs == NULL) 1432 rs = avl_nearest(t, where, AVL_AFTER); 1433 ASSERT(rs != NULL); 1434 } 1435 1436 if ((rs->rs_end - rs->rs_start) >= size) { 1437 *cursor = rs->rs_start + size; 1438 return (rs->rs_start); 1439 } 1440 return (-1ULL); 1441 } 1442 1443 static metaslab_ops_t metaslab_ndf_ops = { 1444 metaslab_ndf_alloc 1445 }; 1446 1447 metaslab_ops_t *zfs_metaslab_ops = &metaslab_df_ops; 1448 1449 /* 1450 * ========================================================================== 1451 * Metaslabs 1452 * ========================================================================== 1453 */ 1454 1455 /* 1456 * Wait for any in-progress metaslab loads to complete. 1457 */ 1458 static void 1459 metaslab_load_wait(metaslab_t *msp) 1460 { 1461 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1462 1463 while (msp->ms_loading) { 1464 ASSERT(!msp->ms_loaded); 1465 cv_wait(&msp->ms_load_cv, &msp->ms_lock); 1466 } 1467 } 1468 1469 static int 1470 metaslab_load_impl(metaslab_t *msp) 1471 { 1472 int error = 0; 1473 1474 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1475 ASSERT(msp->ms_loading); 1476 1477 /* 1478 * Nobody else can manipulate a loading metaslab, so it's now safe 1479 * to drop the lock. This way we don't have to hold the lock while 1480 * reading the spacemap from disk. 1481 */ 1482 mutex_exit(&msp->ms_lock); 1483 1484 /* 1485 * If the space map has not been allocated yet, then treat 1486 * all the space in the metaslab as free and add it to ms_allocatable. 1487 */ 1488 if (msp->ms_sm != NULL) { 1489 error = space_map_load(msp->ms_sm, msp->ms_allocatable, 1490 SM_FREE); 1491 } else { 1492 range_tree_add(msp->ms_allocatable, 1493 msp->ms_start, msp->ms_size); 1494 } 1495 1496 mutex_enter(&msp->ms_lock); 1497 1498 if (error != 0) 1499 return (error); 1500 1501 ASSERT3P(msp->ms_group, !=, NULL); 1502 msp->ms_loaded = B_TRUE; 1503 1504 /* 1505 * If the metaslab already has a spacemap, then we need to 1506 * remove all segments from the defer tree; otherwise, the 1507 * metaslab is completely empty and we can skip this. 1508 */ 1509 if (msp->ms_sm != NULL) { 1510 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 1511 range_tree_walk(msp->ms_defer[t], 1512 range_tree_remove, msp->ms_allocatable); 1513 } 1514 } 1515 msp->ms_max_size = metaslab_block_maxsize(msp); 1516 1517 return (0); 1518 } 1519 1520 int 1521 metaslab_load(metaslab_t *msp) 1522 { 1523 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1524 1525 /* 1526 * There may be another thread loading the same metaslab, if that's 1527 * the case just wait until the other thread is done and return. 1528 */ 1529 metaslab_load_wait(msp); 1530 if (msp->ms_loaded) 1531 return (0); 1532 VERIFY(!msp->ms_loading); 1533 1534 msp->ms_loading = B_TRUE; 1535 int error = metaslab_load_impl(msp); 1536 msp->ms_loading = B_FALSE; 1537 cv_broadcast(&msp->ms_load_cv); 1538 1539 return (error); 1540 } 1541 1542 void 1543 metaslab_unload(metaslab_t *msp) 1544 { 1545 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1546 range_tree_vacate(msp->ms_allocatable, NULL, NULL); 1547 msp->ms_loaded = B_FALSE; 1548 msp->ms_weight &= ~METASLAB_ACTIVE_MASK; 1549 msp->ms_max_size = 0; 1550 } 1551 1552 int 1553 metaslab_init(metaslab_group_t *mg, uint64_t id, uint64_t object, uint64_t txg, 1554 metaslab_t **msp) 1555 { 1556 vdev_t *vd = mg->mg_vd; 1557 objset_t *mos = vd->vdev_spa->spa_meta_objset; 1558 metaslab_t *ms; 1559 int error; 1560 1561 ms = kmem_zalloc(sizeof (metaslab_t), KM_SLEEP); 1562 mutex_init(&ms->ms_lock, NULL, MUTEX_DEFAULT, NULL); 1563 mutex_init(&ms->ms_sync_lock, NULL, MUTEX_DEFAULT, NULL); 1564 cv_init(&ms->ms_load_cv, NULL, CV_DEFAULT, NULL); 1565 1566 ms->ms_id = id; 1567 ms->ms_start = id << vd->vdev_ms_shift; 1568 ms->ms_size = 1ULL << vd->vdev_ms_shift; 1569 ms->ms_allocator = -1; 1570 ms->ms_new = B_TRUE; 1571 1572 /* 1573 * We only open space map objects that already exist. All others 1574 * will be opened when we finally allocate an object for it. 1575 */ 1576 if (object != 0) { 1577 error = space_map_open(&ms->ms_sm, mos, object, ms->ms_start, 1578 ms->ms_size, vd->vdev_ashift); 1579 1580 if (error != 0) { 1581 kmem_free(ms, sizeof (metaslab_t)); 1582 return (error); 1583 } 1584 1585 ASSERT(ms->ms_sm != NULL); 1586 } 1587 1588 /* 1589 * We create the main range tree here, but we don't create the 1590 * other range trees until metaslab_sync_done(). This serves 1591 * two purposes: it allows metaslab_sync_done() to detect the 1592 * addition of new space; and for debugging, it ensures that we'd 1593 * data fault on any attempt to use this metaslab before it's ready. 1594 */ 1595 ms->ms_allocatable = range_tree_create(&metaslab_rt_ops, ms); 1596 metaslab_group_add(mg, ms); 1597 1598 metaslab_set_fragmentation(ms); 1599 1600 /* 1601 * If we're opening an existing pool (txg == 0) or creating 1602 * a new one (txg == TXG_INITIAL), all space is available now. 1603 * If we're adding space to an existing pool, the new space 1604 * does not become available until after this txg has synced. 1605 * The metaslab's weight will also be initialized when we sync 1606 * out this txg. This ensures that we don't attempt to allocate 1607 * from it before we have initialized it completely. 1608 */ 1609 if (txg <= TXG_INITIAL) 1610 metaslab_sync_done(ms, 0); 1611 1612 /* 1613 * If metaslab_debug_load is set and we're initializing a metaslab 1614 * that has an allocated space map object then load the its space 1615 * map so that can verify frees. 1616 */ 1617 if (metaslab_debug_load && ms->ms_sm != NULL) { 1618 mutex_enter(&ms->ms_lock); 1619 VERIFY0(metaslab_load(ms)); 1620 mutex_exit(&ms->ms_lock); 1621 } 1622 1623 if (txg != 0) { 1624 vdev_dirty(vd, 0, NULL, txg); 1625 vdev_dirty(vd, VDD_METASLAB, ms, txg); 1626 } 1627 1628 *msp = ms; 1629 1630 return (0); 1631 } 1632 1633 void 1634 metaslab_fini(metaslab_t *msp) 1635 { 1636 metaslab_group_t *mg = msp->ms_group; 1637 1638 metaslab_group_remove(mg, msp); 1639 1640 mutex_enter(&msp->ms_lock); 1641 VERIFY(msp->ms_group == NULL); 1642 vdev_space_update(mg->mg_vd, -space_map_allocated(msp->ms_sm), 1643 0, -msp->ms_size); 1644 space_map_close(msp->ms_sm); 1645 1646 metaslab_unload(msp); 1647 range_tree_destroy(msp->ms_allocatable); 1648 range_tree_destroy(msp->ms_freeing); 1649 range_tree_destroy(msp->ms_freed); 1650 1651 for (int t = 0; t < TXG_SIZE; t++) { 1652 range_tree_destroy(msp->ms_allocating[t]); 1653 } 1654 1655 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 1656 range_tree_destroy(msp->ms_defer[t]); 1657 } 1658 ASSERT0(msp->ms_deferspace); 1659 1660 range_tree_destroy(msp->ms_checkpointing); 1661 1662 mutex_exit(&msp->ms_lock); 1663 cv_destroy(&msp->ms_load_cv); 1664 mutex_destroy(&msp->ms_lock); 1665 mutex_destroy(&msp->ms_sync_lock); 1666 ASSERT3U(msp->ms_allocator, ==, -1); 1667 1668 kmem_free(msp, sizeof (metaslab_t)); 1669 } 1670 1671 #define FRAGMENTATION_TABLE_SIZE 17 1672 1673 /* 1674 * This table defines a segment size based fragmentation metric that will 1675 * allow each metaslab to derive its own fragmentation value. This is done 1676 * by calculating the space in each bucket of the spacemap histogram and 1677 * multiplying that by the fragmetation metric in this table. Doing 1678 * this for all buckets and dividing it by the total amount of free 1679 * space in this metaslab (i.e. the total free space in all buckets) gives 1680 * us the fragmentation metric. This means that a high fragmentation metric 1681 * equates to most of the free space being comprised of small segments. 1682 * Conversely, if the metric is low, then most of the free space is in 1683 * large segments. A 10% change in fragmentation equates to approximately 1684 * double the number of segments. 1685 * 1686 * This table defines 0% fragmented space using 16MB segments. Testing has 1687 * shown that segments that are greater than or equal to 16MB do not suffer 1688 * from drastic performance problems. Using this value, we derive the rest 1689 * of the table. Since the fragmentation value is never stored on disk, it 1690 * is possible to change these calculations in the future. 1691 */ 1692 int zfs_frag_table[FRAGMENTATION_TABLE_SIZE] = { 1693 100, /* 512B */ 1694 100, /* 1K */ 1695 98, /* 2K */ 1696 95, /* 4K */ 1697 90, /* 8K */ 1698 80, /* 16K */ 1699 70, /* 32K */ 1700 60, /* 64K */ 1701 50, /* 128K */ 1702 40, /* 256K */ 1703 30, /* 512K */ 1704 20, /* 1M */ 1705 15, /* 2M */ 1706 10, /* 4M */ 1707 5, /* 8M */ 1708 0 /* 16M */ 1709 }; 1710 1711 /* 1712 * Calclate the metaslab's fragmentation metric. A return value 1713 * of ZFS_FRAG_INVALID means that the metaslab has not been upgraded and does 1714 * not support this metric. Otherwise, the return value should be in the 1715 * range [0, 100]. 1716 */ 1717 static void 1718 metaslab_set_fragmentation(metaslab_t *msp) 1719 { 1720 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 1721 uint64_t fragmentation = 0; 1722 uint64_t total = 0; 1723 boolean_t feature_enabled = spa_feature_is_enabled(spa, 1724 SPA_FEATURE_SPACEMAP_HISTOGRAM); 1725 1726 if (!feature_enabled) { 1727 msp->ms_fragmentation = ZFS_FRAG_INVALID; 1728 return; 1729 } 1730 1731 /* 1732 * A null space map means that the entire metaslab is free 1733 * and thus is not fragmented. 1734 */ 1735 if (msp->ms_sm == NULL) { 1736 msp->ms_fragmentation = 0; 1737 return; 1738 } 1739 1740 /* 1741 * If this metaslab's space map has not been upgraded, flag it 1742 * so that we upgrade next time we encounter it. 1743 */ 1744 if (msp->ms_sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) { 1745 uint64_t txg = spa_syncing_txg(spa); 1746 vdev_t *vd = msp->ms_group->mg_vd; 1747 1748 /* 1749 * If we've reached the final dirty txg, then we must 1750 * be shutting down the pool. We don't want to dirty 1751 * any data past this point so skip setting the condense 1752 * flag. We can retry this action the next time the pool 1753 * is imported. 1754 */ 1755 if (spa_writeable(spa) && txg < spa_final_dirty_txg(spa)) { 1756 msp->ms_condense_wanted = B_TRUE; 1757 vdev_dirty(vd, VDD_METASLAB, msp, txg + 1); 1758 zfs_dbgmsg("txg %llu, requesting force condense: " 1759 "ms_id %llu, vdev_id %llu", txg, msp->ms_id, 1760 vd->vdev_id); 1761 } 1762 msp->ms_fragmentation = ZFS_FRAG_INVALID; 1763 return; 1764 } 1765 1766 for (int i = 0; i < SPACE_MAP_HISTOGRAM_SIZE; i++) { 1767 uint64_t space = 0; 1768 uint8_t shift = msp->ms_sm->sm_shift; 1769 1770 int idx = MIN(shift - SPA_MINBLOCKSHIFT + i, 1771 FRAGMENTATION_TABLE_SIZE - 1); 1772 1773 if (msp->ms_sm->sm_phys->smp_histogram[i] == 0) 1774 continue; 1775 1776 space = msp->ms_sm->sm_phys->smp_histogram[i] << (i + shift); 1777 total += space; 1778 1779 ASSERT3U(idx, <, FRAGMENTATION_TABLE_SIZE); 1780 fragmentation += space * zfs_frag_table[idx]; 1781 } 1782 1783 if (total > 0) 1784 fragmentation /= total; 1785 ASSERT3U(fragmentation, <=, 100); 1786 1787 msp->ms_fragmentation = fragmentation; 1788 } 1789 1790 /* 1791 * Compute a weight -- a selection preference value -- for the given metaslab. 1792 * This is based on the amount of free space, the level of fragmentation, 1793 * the LBA range, and whether the metaslab is loaded. 1794 */ 1795 static uint64_t 1796 metaslab_space_weight(metaslab_t *msp) 1797 { 1798 metaslab_group_t *mg = msp->ms_group; 1799 vdev_t *vd = mg->mg_vd; 1800 uint64_t weight, space; 1801 1802 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1803 ASSERT(!vd->vdev_removing); 1804 1805 /* 1806 * The baseline weight is the metaslab's free space. 1807 */ 1808 space = msp->ms_size - space_map_allocated(msp->ms_sm); 1809 1810 if (metaslab_fragmentation_factor_enabled && 1811 msp->ms_fragmentation != ZFS_FRAG_INVALID) { 1812 /* 1813 * Use the fragmentation information to inversely scale 1814 * down the baseline weight. We need to ensure that we 1815 * don't exclude this metaslab completely when it's 100% 1816 * fragmented. To avoid this we reduce the fragmented value 1817 * by 1. 1818 */ 1819 space = (space * (100 - (msp->ms_fragmentation - 1))) / 100; 1820 1821 /* 1822 * If space < SPA_MINBLOCKSIZE, then we will not allocate from 1823 * this metaslab again. The fragmentation metric may have 1824 * decreased the space to something smaller than 1825 * SPA_MINBLOCKSIZE, so reset the space to SPA_MINBLOCKSIZE 1826 * so that we can consume any remaining space. 1827 */ 1828 if (space > 0 && space < SPA_MINBLOCKSIZE) 1829 space = SPA_MINBLOCKSIZE; 1830 } 1831 weight = space; 1832 1833 /* 1834 * Modern disks have uniform bit density and constant angular velocity. 1835 * Therefore, the outer recording zones are faster (higher bandwidth) 1836 * than the inner zones by the ratio of outer to inner track diameter, 1837 * which is typically around 2:1. We account for this by assigning 1838 * higher weight to lower metaslabs (multiplier ranging from 2x to 1x). 1839 * In effect, this means that we'll select the metaslab with the most 1840 * free bandwidth rather than simply the one with the most free space. 1841 */ 1842 if (metaslab_lba_weighting_enabled) { 1843 weight = 2 * weight - (msp->ms_id * weight) / vd->vdev_ms_count; 1844 ASSERT(weight >= space && weight <= 2 * space); 1845 } 1846 1847 /* 1848 * If this metaslab is one we're actively using, adjust its 1849 * weight to make it preferable to any inactive metaslab so 1850 * we'll polish it off. If the fragmentation on this metaslab 1851 * has exceed our threshold, then don't mark it active. 1852 */ 1853 if (msp->ms_loaded && msp->ms_fragmentation != ZFS_FRAG_INVALID && 1854 msp->ms_fragmentation <= zfs_metaslab_fragmentation_threshold) { 1855 weight |= (msp->ms_weight & METASLAB_ACTIVE_MASK); 1856 } 1857 1858 WEIGHT_SET_SPACEBASED(weight); 1859 return (weight); 1860 } 1861 1862 /* 1863 * Return the weight of the specified metaslab, according to the segment-based 1864 * weighting algorithm. The metaslab must be loaded. This function can 1865 * be called within a sync pass since it relies only on the metaslab's 1866 * range tree which is always accurate when the metaslab is loaded. 1867 */ 1868 static uint64_t 1869 metaslab_weight_from_range_tree(metaslab_t *msp) 1870 { 1871 uint64_t weight = 0; 1872 uint32_t segments = 0; 1873 1874 ASSERT(msp->ms_loaded); 1875 1876 for (int i = RANGE_TREE_HISTOGRAM_SIZE - 1; i >= SPA_MINBLOCKSHIFT; 1877 i--) { 1878 uint8_t shift = msp->ms_group->mg_vd->vdev_ashift; 1879 int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1; 1880 1881 segments <<= 1; 1882 segments += msp->ms_allocatable->rt_histogram[i]; 1883 1884 /* 1885 * The range tree provides more precision than the space map 1886 * and must be downgraded so that all values fit within the 1887 * space map's histogram. This allows us to compare loaded 1888 * vs. unloaded metaslabs to determine which metaslab is 1889 * considered "best". 1890 */ 1891 if (i > max_idx) 1892 continue; 1893 1894 if (segments != 0) { 1895 WEIGHT_SET_COUNT(weight, segments); 1896 WEIGHT_SET_INDEX(weight, i); 1897 WEIGHT_SET_ACTIVE(weight, 0); 1898 break; 1899 } 1900 } 1901 return (weight); 1902 } 1903 1904 /* 1905 * Calculate the weight based on the on-disk histogram. This should only 1906 * be called after a sync pass has completely finished since the on-disk 1907 * information is updated in metaslab_sync(). 1908 */ 1909 static uint64_t 1910 metaslab_weight_from_spacemap(metaslab_t *msp) 1911 { 1912 uint64_t weight = 0; 1913 1914 for (int i = SPACE_MAP_HISTOGRAM_SIZE - 1; i >= 0; i--) { 1915 if (msp->ms_sm->sm_phys->smp_histogram[i] != 0) { 1916 WEIGHT_SET_COUNT(weight, 1917 msp->ms_sm->sm_phys->smp_histogram[i]); 1918 WEIGHT_SET_INDEX(weight, i + 1919 msp->ms_sm->sm_shift); 1920 WEIGHT_SET_ACTIVE(weight, 0); 1921 break; 1922 } 1923 } 1924 return (weight); 1925 } 1926 1927 /* 1928 * Compute a segment-based weight for the specified metaslab. The weight 1929 * is determined by highest bucket in the histogram. The information 1930 * for the highest bucket is encoded into the weight value. 1931 */ 1932 static uint64_t 1933 metaslab_segment_weight(metaslab_t *msp) 1934 { 1935 metaslab_group_t *mg = msp->ms_group; 1936 uint64_t weight = 0; 1937 uint8_t shift = mg->mg_vd->vdev_ashift; 1938 1939 ASSERT(MUTEX_HELD(&msp->ms_lock)); 1940 1941 /* 1942 * The metaslab is completely free. 1943 */ 1944 if (space_map_allocated(msp->ms_sm) == 0) { 1945 int idx = highbit64(msp->ms_size) - 1; 1946 int max_idx = SPACE_MAP_HISTOGRAM_SIZE + shift - 1; 1947 1948 if (idx < max_idx) { 1949 WEIGHT_SET_COUNT(weight, 1ULL); 1950 WEIGHT_SET_INDEX(weight, idx); 1951 } else { 1952 WEIGHT_SET_COUNT(weight, 1ULL << (idx - max_idx)); 1953 WEIGHT_SET_INDEX(weight, max_idx); 1954 } 1955 WEIGHT_SET_ACTIVE(weight, 0); 1956 ASSERT(!WEIGHT_IS_SPACEBASED(weight)); 1957 1958 return (weight); 1959 } 1960 1961 ASSERT3U(msp->ms_sm->sm_dbuf->db_size, ==, sizeof (space_map_phys_t)); 1962 1963 /* 1964 * If the metaslab is fully allocated then just make the weight 0. 1965 */ 1966 if (space_map_allocated(msp->ms_sm) == msp->ms_size) 1967 return (0); 1968 /* 1969 * If the metaslab is already loaded, then use the range tree to 1970 * determine the weight. Otherwise, we rely on the space map information 1971 * to generate the weight. 1972 */ 1973 if (msp->ms_loaded) { 1974 weight = metaslab_weight_from_range_tree(msp); 1975 } else { 1976 weight = metaslab_weight_from_spacemap(msp); 1977 } 1978 1979 /* 1980 * If the metaslab was active the last time we calculated its weight 1981 * then keep it active. We want to consume the entire region that 1982 * is associated with this weight. 1983 */ 1984 if (msp->ms_activation_weight != 0 && weight != 0) 1985 WEIGHT_SET_ACTIVE(weight, WEIGHT_GET_ACTIVE(msp->ms_weight)); 1986 return (weight); 1987 } 1988 1989 /* 1990 * Determine if we should attempt to allocate from this metaslab. If the 1991 * metaslab has a maximum size then we can quickly determine if the desired 1992 * allocation size can be satisfied. Otherwise, if we're using segment-based 1993 * weighting then we can determine the maximum allocation that this metaslab 1994 * can accommodate based on the index encoded in the weight. If we're using 1995 * space-based weights then rely on the entire weight (excluding the weight 1996 * type bit). 1997 */ 1998 boolean_t 1999 metaslab_should_allocate(metaslab_t *msp, uint64_t asize) 2000 { 2001 boolean_t should_allocate; 2002 2003 if (msp->ms_max_size != 0) 2004 return (msp->ms_max_size >= asize); 2005 2006 if (!WEIGHT_IS_SPACEBASED(msp->ms_weight)) { 2007 /* 2008 * The metaslab segment weight indicates segments in the 2009 * range [2^i, 2^(i+1)), where i is the index in the weight. 2010 * Since the asize might be in the middle of the range, we 2011 * should attempt the allocation if asize < 2^(i+1). 2012 */ 2013 should_allocate = (asize < 2014 1ULL << (WEIGHT_GET_INDEX(msp->ms_weight) + 1)); 2015 } else { 2016 should_allocate = (asize <= 2017 (msp->ms_weight & ~METASLAB_WEIGHT_TYPE)); 2018 } 2019 return (should_allocate); 2020 } 2021 2022 static uint64_t 2023 metaslab_weight(metaslab_t *msp) 2024 { 2025 vdev_t *vd = msp->ms_group->mg_vd; 2026 spa_t *spa = vd->vdev_spa; 2027 uint64_t weight; 2028 2029 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2030 2031 /* 2032 * If this vdev is in the process of being removed, there is nothing 2033 * for us to do here. 2034 */ 2035 if (vd->vdev_removing) 2036 return (0); 2037 2038 metaslab_set_fragmentation(msp); 2039 2040 /* 2041 * Update the maximum size if the metaslab is loaded. This will 2042 * ensure that we get an accurate maximum size if newly freed space 2043 * has been added back into the free tree. 2044 */ 2045 if (msp->ms_loaded) 2046 msp->ms_max_size = metaslab_block_maxsize(msp); 2047 2048 /* 2049 * Segment-based weighting requires space map histogram support. 2050 */ 2051 if (zfs_metaslab_segment_weight_enabled && 2052 spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM) && 2053 (msp->ms_sm == NULL || msp->ms_sm->sm_dbuf->db_size == 2054 sizeof (space_map_phys_t))) { 2055 weight = metaslab_segment_weight(msp); 2056 } else { 2057 weight = metaslab_space_weight(msp); 2058 } 2059 return (weight); 2060 } 2061 2062 static int 2063 metaslab_activate_allocator(metaslab_group_t *mg, metaslab_t *msp, 2064 int allocator, uint64_t activation_weight) 2065 { 2066 /* 2067 * If we're activating for the claim code, we don't want to actually 2068 * set the metaslab up for a specific allocator. 2069 */ 2070 if (activation_weight == METASLAB_WEIGHT_CLAIM) 2071 return (0); 2072 metaslab_t **arr = (activation_weight == METASLAB_WEIGHT_PRIMARY ? 2073 mg->mg_primaries : mg->mg_secondaries); 2074 2075 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2076 mutex_enter(&mg->mg_lock); 2077 if (arr[allocator] != NULL) { 2078 mutex_exit(&mg->mg_lock); 2079 return (EEXIST); 2080 } 2081 2082 arr[allocator] = msp; 2083 ASSERT3S(msp->ms_allocator, ==, -1); 2084 msp->ms_allocator = allocator; 2085 msp->ms_primary = (activation_weight == METASLAB_WEIGHT_PRIMARY); 2086 mutex_exit(&mg->mg_lock); 2087 2088 return (0); 2089 } 2090 2091 static int 2092 metaslab_activate(metaslab_t *msp, int allocator, uint64_t activation_weight) 2093 { 2094 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2095 2096 if ((msp->ms_weight & METASLAB_ACTIVE_MASK) == 0) { 2097 int error = metaslab_load(msp); 2098 if (error != 0) { 2099 metaslab_group_sort(msp->ms_group, msp, 0); 2100 return (error); 2101 } 2102 if ((msp->ms_weight & METASLAB_ACTIVE_MASK) != 0) { 2103 /* 2104 * The metaslab was activated for another allocator 2105 * while we were waiting, we should reselect. 2106 */ 2107 return (EBUSY); 2108 } 2109 if ((error = metaslab_activate_allocator(msp->ms_group, msp, 2110 allocator, activation_weight)) != 0) { 2111 return (error); 2112 } 2113 2114 msp->ms_activation_weight = msp->ms_weight; 2115 metaslab_group_sort(msp->ms_group, msp, 2116 msp->ms_weight | activation_weight); 2117 } 2118 ASSERT(msp->ms_loaded); 2119 ASSERT(msp->ms_weight & METASLAB_ACTIVE_MASK); 2120 2121 return (0); 2122 } 2123 2124 static void 2125 metaslab_passivate_allocator(metaslab_group_t *mg, metaslab_t *msp, 2126 uint64_t weight) 2127 { 2128 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2129 if (msp->ms_weight & METASLAB_WEIGHT_CLAIM) { 2130 metaslab_group_sort(mg, msp, weight); 2131 return; 2132 } 2133 2134 mutex_enter(&mg->mg_lock); 2135 ASSERT3P(msp->ms_group, ==, mg); 2136 if (msp->ms_primary) { 2137 ASSERT3U(0, <=, msp->ms_allocator); 2138 ASSERT3U(msp->ms_allocator, <, mg->mg_allocators); 2139 ASSERT3P(mg->mg_primaries[msp->ms_allocator], ==, msp); 2140 ASSERT(msp->ms_weight & METASLAB_WEIGHT_PRIMARY); 2141 mg->mg_primaries[msp->ms_allocator] = NULL; 2142 } else { 2143 ASSERT(msp->ms_weight & METASLAB_WEIGHT_SECONDARY); 2144 ASSERT3P(mg->mg_secondaries[msp->ms_allocator], ==, msp); 2145 mg->mg_secondaries[msp->ms_allocator] = NULL; 2146 } 2147 msp->ms_allocator = -1; 2148 metaslab_group_sort_impl(mg, msp, weight); 2149 mutex_exit(&mg->mg_lock); 2150 } 2151 2152 static void 2153 metaslab_passivate(metaslab_t *msp, uint64_t weight) 2154 { 2155 uint64_t size = weight & ~METASLAB_WEIGHT_TYPE; 2156 2157 /* 2158 * If size < SPA_MINBLOCKSIZE, then we will not allocate from 2159 * this metaslab again. In that case, it had better be empty, 2160 * or we would be leaving space on the table. 2161 */ 2162 ASSERT(size >= SPA_MINBLOCKSIZE || 2163 range_tree_is_empty(msp->ms_allocatable)); 2164 ASSERT0(weight & METASLAB_ACTIVE_MASK); 2165 2166 msp->ms_activation_weight = 0; 2167 metaslab_passivate_allocator(msp->ms_group, msp, weight); 2168 ASSERT((msp->ms_weight & METASLAB_ACTIVE_MASK) == 0); 2169 } 2170 2171 /* 2172 * Segment-based metaslabs are activated once and remain active until 2173 * we either fail an allocation attempt (similar to space-based metaslabs) 2174 * or have exhausted the free space in zfs_metaslab_switch_threshold 2175 * buckets since the metaslab was activated. This function checks to see 2176 * if we've exhaused the zfs_metaslab_switch_threshold buckets in the 2177 * metaslab and passivates it proactively. This will allow us to select a 2178 * metaslabs with larger contiguous region if any remaining within this 2179 * metaslab group. If we're in sync pass > 1, then we continue using this 2180 * metaslab so that we don't dirty more block and cause more sync passes. 2181 */ 2182 void 2183 metaslab_segment_may_passivate(metaslab_t *msp) 2184 { 2185 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2186 2187 if (WEIGHT_IS_SPACEBASED(msp->ms_weight) || spa_sync_pass(spa) > 1) 2188 return; 2189 2190 /* 2191 * Since we are in the middle of a sync pass, the most accurate 2192 * information that is accessible to us is the in-core range tree 2193 * histogram; calculate the new weight based on that information. 2194 */ 2195 uint64_t weight = metaslab_weight_from_range_tree(msp); 2196 int activation_idx = WEIGHT_GET_INDEX(msp->ms_activation_weight); 2197 int current_idx = WEIGHT_GET_INDEX(weight); 2198 2199 if (current_idx <= activation_idx - zfs_metaslab_switch_threshold) 2200 metaslab_passivate(msp, weight); 2201 } 2202 2203 static void 2204 metaslab_preload(void *arg) 2205 { 2206 metaslab_t *msp = arg; 2207 spa_t *spa = msp->ms_group->mg_vd->vdev_spa; 2208 2209 ASSERT(!MUTEX_HELD(&msp->ms_group->mg_lock)); 2210 2211 mutex_enter(&msp->ms_lock); 2212 (void) metaslab_load(msp); 2213 msp->ms_selected_txg = spa_syncing_txg(spa); 2214 mutex_exit(&msp->ms_lock); 2215 } 2216 2217 static void 2218 metaslab_group_preload(metaslab_group_t *mg) 2219 { 2220 spa_t *spa = mg->mg_vd->vdev_spa; 2221 metaslab_t *msp; 2222 avl_tree_t *t = &mg->mg_metaslab_tree; 2223 int m = 0; 2224 2225 if (spa_shutting_down(spa) || !metaslab_preload_enabled) { 2226 taskq_wait(mg->mg_taskq); 2227 return; 2228 } 2229 2230 mutex_enter(&mg->mg_lock); 2231 2232 /* 2233 * Load the next potential metaslabs 2234 */ 2235 for (msp = avl_first(t); msp != NULL; msp = AVL_NEXT(t, msp)) { 2236 ASSERT3P(msp->ms_group, ==, mg); 2237 2238 /* 2239 * We preload only the maximum number of metaslabs specified 2240 * by metaslab_preload_limit. If a metaslab is being forced 2241 * to condense then we preload it too. This will ensure 2242 * that force condensing happens in the next txg. 2243 */ 2244 if (++m > metaslab_preload_limit && !msp->ms_condense_wanted) { 2245 continue; 2246 } 2247 2248 VERIFY(taskq_dispatch(mg->mg_taskq, metaslab_preload, 2249 msp, TQ_SLEEP) != NULL); 2250 } 2251 mutex_exit(&mg->mg_lock); 2252 } 2253 2254 /* 2255 * Determine if the space map's on-disk footprint is past our tolerance 2256 * for inefficiency. We would like to use the following criteria to make 2257 * our decision: 2258 * 2259 * 1. The size of the space map object should not dramatically increase as a 2260 * result of writing out the free space range tree. 2261 * 2262 * 2. The minimal on-disk space map representation is zfs_condense_pct/100 2263 * times the size than the free space range tree representation 2264 * (i.e. zfs_condense_pct = 110 and in-core = 1MB, minimal = 1.1MB). 2265 * 2266 * 3. The on-disk size of the space map should actually decrease. 2267 * 2268 * Unfortunately, we cannot compute the on-disk size of the space map in this 2269 * context because we cannot accurately compute the effects of compression, etc. 2270 * Instead, we apply the heuristic described in the block comment for 2271 * zfs_metaslab_condense_block_threshold - we only condense if the space used 2272 * is greater than a threshold number of blocks. 2273 */ 2274 static boolean_t 2275 metaslab_should_condense(metaslab_t *msp) 2276 { 2277 space_map_t *sm = msp->ms_sm; 2278 vdev_t *vd = msp->ms_group->mg_vd; 2279 uint64_t vdev_blocksize = 1 << vd->vdev_ashift; 2280 uint64_t current_txg = spa_syncing_txg(vd->vdev_spa); 2281 2282 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2283 ASSERT(msp->ms_loaded); 2284 2285 /* 2286 * Allocations and frees in early passes are generally more space 2287 * efficient (in terms of blocks described in space map entries) 2288 * than the ones in later passes (e.g. we don't compress after 2289 * sync pass 5) and condensing a metaslab multiple times in a txg 2290 * could degrade performance. 2291 * 2292 * Thus we prefer condensing each metaslab at most once every txg at 2293 * the earliest sync pass possible. If a metaslab is eligible for 2294 * condensing again after being considered for condensing within the 2295 * same txg, it will hopefully be dirty in the next txg where it will 2296 * be condensed at an earlier pass. 2297 */ 2298 if (msp->ms_condense_checked_txg == current_txg) 2299 return (B_FALSE); 2300 msp->ms_condense_checked_txg = current_txg; 2301 2302 /* 2303 * We always condense metaslabs that are empty and metaslabs for 2304 * which a condense request has been made. 2305 */ 2306 if (avl_is_empty(&msp->ms_allocatable_by_size) || 2307 msp->ms_condense_wanted) 2308 return (B_TRUE); 2309 2310 uint64_t object_size = space_map_length(msp->ms_sm); 2311 uint64_t optimal_size = space_map_estimate_optimal_size(sm, 2312 msp->ms_allocatable, SM_NO_VDEVID); 2313 2314 dmu_object_info_t doi; 2315 dmu_object_info_from_db(sm->sm_dbuf, &doi); 2316 uint64_t record_size = MAX(doi.doi_data_block_size, vdev_blocksize); 2317 2318 return (object_size >= (optimal_size * zfs_condense_pct / 100) && 2319 object_size > zfs_metaslab_condense_block_threshold * record_size); 2320 } 2321 2322 /* 2323 * Condense the on-disk space map representation to its minimized form. 2324 * The minimized form consists of a small number of allocations followed by 2325 * the entries of the free range tree. 2326 */ 2327 static void 2328 metaslab_condense(metaslab_t *msp, uint64_t txg, dmu_tx_t *tx) 2329 { 2330 range_tree_t *condense_tree; 2331 space_map_t *sm = msp->ms_sm; 2332 2333 ASSERT(MUTEX_HELD(&msp->ms_lock)); 2334 ASSERT(msp->ms_loaded); 2335 2336 zfs_dbgmsg("condensing: txg %llu, msp[%llu] %p, vdev id %llu, " 2337 "spa %s, smp size %llu, segments %lu, forcing condense=%s", txg, 2338 msp->ms_id, msp, msp->ms_group->mg_vd->vdev_id, 2339 msp->ms_group->mg_vd->vdev_spa->spa_name, 2340 space_map_length(msp->ms_sm), 2341 avl_numnodes(&msp->ms_allocatable->rt_root), 2342 msp->ms_condense_wanted ? "TRUE" : "FALSE"); 2343 2344 msp->ms_condense_wanted = B_FALSE; 2345 2346 /* 2347 * Create an range tree that is 100% allocated. We remove segments 2348 * that have been freed in this txg, any deferred frees that exist, 2349 * and any allocation in the future. Removing segments should be 2350 * a relatively inexpensive operation since we expect these trees to 2351 * have a small number of nodes. 2352 */ 2353 condense_tree = range_tree_create(NULL, NULL); 2354 range_tree_add(condense_tree, msp->ms_start, msp->ms_size); 2355 2356 range_tree_walk(msp->ms_freeing, range_tree_remove, condense_tree); 2357 range_tree_walk(msp->ms_freed, range_tree_remove, condense_tree); 2358 2359 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2360 range_tree_walk(msp->ms_defer[t], 2361 range_tree_remove, condense_tree); 2362 } 2363 2364 for (int t = 1; t < TXG_CONCURRENT_STATES; t++) { 2365 range_tree_walk(msp->ms_allocating[(txg + t) & TXG_MASK], 2366 range_tree_remove, condense_tree); 2367 } 2368 2369 /* 2370 * We're about to drop the metaslab's lock thus allowing 2371 * other consumers to change it's content. Set the 2372 * metaslab's ms_condensing flag to ensure that 2373 * allocations on this metaslab do not occur while we're 2374 * in the middle of committing it to disk. This is only critical 2375 * for ms_allocatable as all other range trees use per txg 2376 * views of their content. 2377 */ 2378 msp->ms_condensing = B_TRUE; 2379 2380 mutex_exit(&msp->ms_lock); 2381 space_map_truncate(sm, zfs_metaslab_sm_blksz, tx); 2382 2383 /* 2384 * While we would ideally like to create a space map representation 2385 * that consists only of allocation records, doing so can be 2386 * prohibitively expensive because the in-core free tree can be 2387 * large, and therefore computationally expensive to subtract 2388 * from the condense_tree. Instead we sync out two trees, a cheap 2389 * allocation only tree followed by the in-core free tree. While not 2390 * optimal, this is typically close to optimal, and much cheaper to 2391 * compute. 2392 */ 2393 space_map_write(sm, condense_tree, SM_ALLOC, SM_NO_VDEVID, tx); 2394 range_tree_vacate(condense_tree, NULL, NULL); 2395 range_tree_destroy(condense_tree); 2396 2397 space_map_write(sm, msp->ms_allocatable, SM_FREE, SM_NO_VDEVID, tx); 2398 mutex_enter(&msp->ms_lock); 2399 msp->ms_condensing = B_FALSE; 2400 } 2401 2402 /* 2403 * Write a metaslab to disk in the context of the specified transaction group. 2404 */ 2405 void 2406 metaslab_sync(metaslab_t *msp, uint64_t txg) 2407 { 2408 metaslab_group_t *mg = msp->ms_group; 2409 vdev_t *vd = mg->mg_vd; 2410 spa_t *spa = vd->vdev_spa; 2411 objset_t *mos = spa_meta_objset(spa); 2412 range_tree_t *alloctree = msp->ms_allocating[txg & TXG_MASK]; 2413 dmu_tx_t *tx; 2414 uint64_t object = space_map_object(msp->ms_sm); 2415 2416 ASSERT(!vd->vdev_ishole); 2417 2418 /* 2419 * This metaslab has just been added so there's no work to do now. 2420 */ 2421 if (msp->ms_freeing == NULL) { 2422 ASSERT3P(alloctree, ==, NULL); 2423 return; 2424 } 2425 2426 ASSERT3P(alloctree, !=, NULL); 2427 ASSERT3P(msp->ms_freeing, !=, NULL); 2428 ASSERT3P(msp->ms_freed, !=, NULL); 2429 ASSERT3P(msp->ms_checkpointing, !=, NULL); 2430 2431 /* 2432 * Normally, we don't want to process a metaslab if there are no 2433 * allocations or frees to perform. However, if the metaslab is being 2434 * forced to condense and it's loaded, we need to let it through. 2435 */ 2436 if (range_tree_is_empty(alloctree) && 2437 range_tree_is_empty(msp->ms_freeing) && 2438 range_tree_is_empty(msp->ms_checkpointing) && 2439 !(msp->ms_loaded && msp->ms_condense_wanted)) 2440 return; 2441 2442 2443 VERIFY(txg <= spa_final_dirty_txg(spa)); 2444 2445 /* 2446 * The only state that can actually be changing concurrently with 2447 * metaslab_sync() is the metaslab's ms_allocatable. No other 2448 * thread can be modifying this txg's alloc, freeing, 2449 * freed, or space_map_phys_t. We drop ms_lock whenever we 2450 * could call into the DMU, because the DMU can call down to us 2451 * (e.g. via zio_free()) at any time. 2452 * 2453 * The spa_vdev_remove_thread() can be reading metaslab state 2454 * concurrently, and it is locked out by the ms_sync_lock. Note 2455 * that the ms_lock is insufficient for this, because it is dropped 2456 * by space_map_write(). 2457 */ 2458 tx = dmu_tx_create_assigned(spa_get_dsl(spa), txg); 2459 2460 if (msp->ms_sm == NULL) { 2461 uint64_t new_object; 2462 2463 new_object = space_map_alloc(mos, zfs_metaslab_sm_blksz, tx); 2464 VERIFY3U(new_object, !=, 0); 2465 2466 VERIFY0(space_map_open(&msp->ms_sm, mos, new_object, 2467 msp->ms_start, msp->ms_size, vd->vdev_ashift)); 2468 ASSERT(msp->ms_sm != NULL); 2469 } 2470 2471 if (!range_tree_is_empty(msp->ms_checkpointing) && 2472 vd->vdev_checkpoint_sm == NULL) { 2473 ASSERT(spa_has_checkpoint(spa)); 2474 2475 uint64_t new_object = space_map_alloc(mos, 2476 vdev_standard_sm_blksz, tx); 2477 VERIFY3U(new_object, !=, 0); 2478 2479 VERIFY0(space_map_open(&vd->vdev_checkpoint_sm, 2480 mos, new_object, 0, vd->vdev_asize, vd->vdev_ashift)); 2481 ASSERT3P(vd->vdev_checkpoint_sm, !=, NULL); 2482 2483 /* 2484 * We save the space map object as an entry in vdev_top_zap 2485 * so it can be retrieved when the pool is reopened after an 2486 * export or through zdb. 2487 */ 2488 VERIFY0(zap_add(vd->vdev_spa->spa_meta_objset, 2489 vd->vdev_top_zap, VDEV_TOP_ZAP_POOL_CHECKPOINT_SM, 2490 sizeof (new_object), 1, &new_object, tx)); 2491 } 2492 2493 mutex_enter(&msp->ms_sync_lock); 2494 mutex_enter(&msp->ms_lock); 2495 2496 /* 2497 * Note: metaslab_condense() clears the space map's histogram. 2498 * Therefore we must verify and remove this histogram before 2499 * condensing. 2500 */ 2501 metaslab_group_histogram_verify(mg); 2502 metaslab_class_histogram_verify(mg->mg_class); 2503 metaslab_group_histogram_remove(mg, msp); 2504 2505 if (msp->ms_loaded && metaslab_should_condense(msp)) { 2506 metaslab_condense(msp, txg, tx); 2507 } else { 2508 mutex_exit(&msp->ms_lock); 2509 space_map_write(msp->ms_sm, alloctree, SM_ALLOC, 2510 SM_NO_VDEVID, tx); 2511 space_map_write(msp->ms_sm, msp->ms_freeing, SM_FREE, 2512 SM_NO_VDEVID, tx); 2513 mutex_enter(&msp->ms_lock); 2514 } 2515 2516 if (!range_tree_is_empty(msp->ms_checkpointing)) { 2517 ASSERT(spa_has_checkpoint(spa)); 2518 ASSERT3P(vd->vdev_checkpoint_sm, !=, NULL); 2519 2520 /* 2521 * Since we are doing writes to disk and the ms_checkpointing 2522 * tree won't be changing during that time, we drop the 2523 * ms_lock while writing to the checkpoint space map. 2524 */ 2525 mutex_exit(&msp->ms_lock); 2526 space_map_write(vd->vdev_checkpoint_sm, 2527 msp->ms_checkpointing, SM_FREE, SM_NO_VDEVID, tx); 2528 mutex_enter(&msp->ms_lock); 2529 space_map_update(vd->vdev_checkpoint_sm); 2530 2531 spa->spa_checkpoint_info.sci_dspace += 2532 range_tree_space(msp->ms_checkpointing); 2533 vd->vdev_stat.vs_checkpoint_space += 2534 range_tree_space(msp->ms_checkpointing); 2535 ASSERT3U(vd->vdev_stat.vs_checkpoint_space, ==, 2536 -vd->vdev_checkpoint_sm->sm_alloc); 2537 2538 range_tree_vacate(msp->ms_checkpointing, NULL, NULL); 2539 } 2540 2541 if (msp->ms_loaded) { 2542 /* 2543 * When the space map is loaded, we have an accurate 2544 * histogram in the range tree. This gives us an opportunity 2545 * to bring the space map's histogram up-to-date so we clear 2546 * it first before updating it. 2547 */ 2548 space_map_histogram_clear(msp->ms_sm); 2549 space_map_histogram_add(msp->ms_sm, msp->ms_allocatable, tx); 2550 2551 /* 2552 * Since we've cleared the histogram we need to add back 2553 * any free space that has already been processed, plus 2554 * any deferred space. This allows the on-disk histogram 2555 * to accurately reflect all free space even if some space 2556 * is not yet available for allocation (i.e. deferred). 2557 */ 2558 space_map_histogram_add(msp->ms_sm, msp->ms_freed, tx); 2559 2560 /* 2561 * Add back any deferred free space that has not been 2562 * added back into the in-core free tree yet. This will 2563 * ensure that we don't end up with a space map histogram 2564 * that is completely empty unless the metaslab is fully 2565 * allocated. 2566 */ 2567 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2568 space_map_histogram_add(msp->ms_sm, 2569 msp->ms_defer[t], tx); 2570 } 2571 } 2572 2573 /* 2574 * Always add the free space from this sync pass to the space 2575 * map histogram. We want to make sure that the on-disk histogram 2576 * accounts for all free space. If the space map is not loaded, 2577 * then we will lose some accuracy but will correct it the next 2578 * time we load the space map. 2579 */ 2580 space_map_histogram_add(msp->ms_sm, msp->ms_freeing, tx); 2581 2582 metaslab_group_histogram_add(mg, msp); 2583 metaslab_group_histogram_verify(mg); 2584 metaslab_class_histogram_verify(mg->mg_class); 2585 2586 /* 2587 * For sync pass 1, we avoid traversing this txg's free range tree 2588 * and instead will just swap the pointers for freeing and 2589 * freed. We can safely do this since the freed_tree is 2590 * guaranteed to be empty on the initial pass. 2591 */ 2592 if (spa_sync_pass(spa) == 1) { 2593 range_tree_swap(&msp->ms_freeing, &msp->ms_freed); 2594 } else { 2595 range_tree_vacate(msp->ms_freeing, 2596 range_tree_add, msp->ms_freed); 2597 } 2598 range_tree_vacate(alloctree, NULL, NULL); 2599 2600 ASSERT0(range_tree_space(msp->ms_allocating[txg & TXG_MASK])); 2601 ASSERT0(range_tree_space(msp->ms_allocating[TXG_CLEAN(txg) 2602 & TXG_MASK])); 2603 ASSERT0(range_tree_space(msp->ms_freeing)); 2604 ASSERT0(range_tree_space(msp->ms_checkpointing)); 2605 2606 mutex_exit(&msp->ms_lock); 2607 2608 if (object != space_map_object(msp->ms_sm)) { 2609 object = space_map_object(msp->ms_sm); 2610 dmu_write(mos, vd->vdev_ms_array, sizeof (uint64_t) * 2611 msp->ms_id, sizeof (uint64_t), &object, tx); 2612 } 2613 mutex_exit(&msp->ms_sync_lock); 2614 dmu_tx_commit(tx); 2615 } 2616 2617 /* 2618 * Called after a transaction group has completely synced to mark 2619 * all of the metaslab's free space as usable. 2620 */ 2621 void 2622 metaslab_sync_done(metaslab_t *msp, uint64_t txg) 2623 { 2624 metaslab_group_t *mg = msp->ms_group; 2625 vdev_t *vd = mg->mg_vd; 2626 spa_t *spa = vd->vdev_spa; 2627 range_tree_t **defer_tree; 2628 int64_t alloc_delta, defer_delta; 2629 boolean_t defer_allowed = B_TRUE; 2630 2631 ASSERT(!vd->vdev_ishole); 2632 2633 mutex_enter(&msp->ms_lock); 2634 2635 /* 2636 * If this metaslab is just becoming available, initialize its 2637 * range trees and add its capacity to the vdev. 2638 */ 2639 if (msp->ms_freed == NULL) { 2640 for (int t = 0; t < TXG_SIZE; t++) { 2641 ASSERT(msp->ms_allocating[t] == NULL); 2642 2643 msp->ms_allocating[t] = range_tree_create(NULL, NULL); 2644 } 2645 2646 ASSERT3P(msp->ms_freeing, ==, NULL); 2647 msp->ms_freeing = range_tree_create(NULL, NULL); 2648 2649 ASSERT3P(msp->ms_freed, ==, NULL); 2650 msp->ms_freed = range_tree_create(NULL, NULL); 2651 2652 for (int t = 0; t < TXG_DEFER_SIZE; t++) { 2653 ASSERT(msp->ms_defer[t] == NULL); 2654 2655 msp->ms_defer[t] = range_tree_create(NULL, NULL); 2656 } 2657 2658 ASSERT3P(msp->ms_checkpointing, ==, NULL); 2659 msp->ms_checkpointing = range_tree_create(NULL, NULL); 2660 2661 vdev_space_update(vd, 0, 0, msp->ms_size); 2662 } 2663 ASSERT0(range_tree_space(msp->ms_freeing)); 2664 ASSERT0(range_tree_space(msp->ms_checkpointing)); 2665 2666 defer_tree = &msp->ms_defer[txg % TXG_DEFER_SIZE]; 2667 2668 uint64_t free_space = metaslab_class_get_space(spa_normal_class(spa)) - 2669 metaslab_class_get_alloc(spa_normal_class(spa)); 2670 if (free_space <= spa_get_slop_space(spa) || vd->vdev_removing) { 2671 defer_allowed = B_FALSE; 2672 } 2673 2674 defer_delta = 0; 2675 alloc_delta = space_map_alloc_delta(msp->ms_sm); 2676 if (defer_allowed) { 2677 defer_delta = range_tree_space(msp->ms_freed) - 2678 range_tree_space(*defer_tree); 2679 } else { 2680 defer_delta -= range_tree_space(*defer_tree); 2681 } 2682 2683 vdev_space_update(vd, alloc_delta + defer_delta, defer_delta, 0); 2684 2685 /* 2686 * If there's a metaslab_load() in progress, wait for it to complete 2687 * so that we have a consistent view of the in-core space map. 2688 */ 2689 metaslab_load_wait(msp); 2690 2691 /* 2692 * Move the frees from the defer_tree back to the free 2693 * range tree (if it's loaded). Swap the freed_tree and 2694 * the defer_tree -- this is safe to do because we've 2695 * just emptied out the defer_tree. 2696 */ 2697 range_tree_vacate(*defer_tree, 2698 msp->ms_loaded ? range_tree_add : NULL, msp->ms_allocatable); 2699 if (defer_allowed) { 2700 range_tree_swap(&msp->ms_freed, defer_tree); 2701 } else { 2702 range_tree_vacate(msp->ms_freed, 2703 msp->ms_loaded ? range_tree_add : NULL, 2704 msp->ms_allocatable); 2705 } 2706 space_map_update(msp->ms_sm); 2707 2708 msp->ms_deferspace += defer_delta; 2709 ASSERT3S(msp->ms_deferspace, >=, 0); 2710 ASSERT3S(msp->ms_deferspace, <=, msp->ms_size); 2711 if (msp->ms_deferspace != 0) { 2712 /* 2713 * Keep syncing this metaslab until all deferred frees 2714 * are back in circulation. 2715 */ 2716 vdev_dirty(vd, VDD_METASLAB, msp, txg + 1); 2717 } 2718 2719 if (msp->ms_new) { 2720 msp->ms_new = B_FALSE; 2721 mutex_enter(&mg->mg_lock); 2722 mg->mg_ms_ready++; 2723 mutex_exit(&mg->mg_lock); 2724 } 2725 /* 2726 * Calculate the new weights before unloading any metaslabs. 2727 * This will give us the most accurate weighting. 2728 */ 2729 metaslab_group_sort(mg, msp, metaslab_weight(msp) | 2730 (msp->ms_weight & METASLAB_ACTIVE_MASK)); 2731 2732 /* 2733 * If the metaslab is loaded and we've not tried to load or allocate 2734 * from it in 'metaslab_unload_delay' txgs, then unload it. 2735 */ 2736 if (msp->ms_loaded && 2737 msp->ms_initializing == 0 && 2738 msp->ms_selected_txg + metaslab_unload_delay < txg) { 2739 for (int t = 1; t < TXG_CONCURRENT_STATES; t++) { 2740 VERIFY0(range_tree_space( 2741 msp->ms_allocating[(txg + t) & TXG_MASK])); 2742 } 2743 if (msp->ms_allocator != -1) { 2744 metaslab_passivate(msp, msp->ms_weight & 2745 ~METASLAB_ACTIVE_MASK); 2746 } 2747 2748 if (!metaslab_debug_unload) 2749 metaslab_unload(msp); 2750 } 2751 2752 ASSERT0(range_tree_space(msp->ms_allocating[txg & TXG_MASK])); 2753 ASSERT0(range_tree_space(msp->ms_freeing)); 2754 ASSERT0(range_tree_space(msp->ms_freed)); 2755 ASSERT0(range_tree_space(msp->ms_checkpointing)); 2756 2757 mutex_exit(&msp->ms_lock); 2758 } 2759 2760 void 2761 metaslab_sync_reassess(metaslab_group_t *mg) 2762 { 2763 spa_t *spa = mg->mg_class->mc_spa; 2764 2765 spa_config_enter(spa, SCL_ALLOC, FTAG, RW_READER); 2766 metaslab_group_alloc_update(mg); 2767 mg->mg_fragmentation = metaslab_group_fragmentation(mg); 2768 2769 /* 2770 * Preload the next potential metaslabs but only on active 2771 * metaslab groups. We can get into a state where the metaslab 2772 * is no longer active since we dirty metaslabs as we remove a 2773 * a device, thus potentially making the metaslab group eligible 2774 * for preloading. 2775 */ 2776 if (mg->mg_activation_count > 0) { 2777 metaslab_group_preload(mg); 2778 } 2779 spa_config_exit(spa, SCL_ALLOC, FTAG); 2780 } 2781 2782 static uint64_t 2783 metaslab_distance(metaslab_t *msp, dva_t *dva) 2784 { 2785 uint64_t ms_shift = msp->ms_group->mg_vd->vdev_ms_shift; 2786 uint64_t offset = DVA_GET_OFFSET(dva) >> ms_shift; 2787 uint64_t start = msp->ms_id; 2788 2789 if (msp->ms_group->mg_vd->vdev_id != DVA_GET_VDEV(dva)) 2790 return (1ULL << 63); 2791 2792 if (offset < start) 2793 return ((start - offset) << ms_shift); 2794 if (offset > start) 2795 return ((offset - start) << ms_shift); 2796 return (0); 2797 } 2798 2799 /* 2800 * ========================================================================== 2801 * Metaslab allocation tracing facility 2802 * ========================================================================== 2803 */ 2804 kstat_t *metaslab_trace_ksp; 2805 kstat_named_t metaslab_trace_over_limit; 2806 2807 void 2808 metaslab_alloc_trace_init(void) 2809 { 2810 ASSERT(metaslab_alloc_trace_cache == NULL); 2811 metaslab_alloc_trace_cache = kmem_cache_create( 2812 "metaslab_alloc_trace_cache", sizeof (metaslab_alloc_trace_t), 2813 0, NULL, NULL, NULL, NULL, NULL, 0); 2814 metaslab_trace_ksp = kstat_create("zfs", 0, "metaslab_trace_stats", 2815 "misc", KSTAT_TYPE_NAMED, 1, KSTAT_FLAG_VIRTUAL); 2816 if (metaslab_trace_ksp != NULL) { 2817 metaslab_trace_ksp->ks_data = &metaslab_trace_over_limit; 2818 kstat_named_init(&metaslab_trace_over_limit, 2819 "metaslab_trace_over_limit", KSTAT_DATA_UINT64); 2820 kstat_install(metaslab_trace_ksp); 2821 } 2822 } 2823 2824 void 2825 metaslab_alloc_trace_fini(void) 2826 { 2827 if (metaslab_trace_ksp != NULL) { 2828 kstat_delete(metaslab_trace_ksp); 2829 metaslab_trace_ksp = NULL; 2830 } 2831 kmem_cache_destroy(metaslab_alloc_trace_cache); 2832 metaslab_alloc_trace_cache = NULL; 2833 } 2834 2835 /* 2836 * Add an allocation trace element to the allocation tracing list. 2837 */ 2838 static void 2839 metaslab_trace_add(zio_alloc_list_t *zal, metaslab_group_t *mg, 2840 metaslab_t *msp, uint64_t psize, uint32_t dva_id, uint64_t offset, 2841 int allocator) 2842 { 2843 if (!metaslab_trace_enabled) 2844 return; 2845 2846 /* 2847 * When the tracing list reaches its maximum we remove 2848 * the second element in the list before adding a new one. 2849 * By removing the second element we preserve the original 2850 * entry as a clue to what allocations steps have already been 2851 * performed. 2852 */ 2853 if (zal->zal_size == metaslab_trace_max_entries) { 2854 metaslab_alloc_trace_t *mat_next; 2855 #ifdef DEBUG 2856 panic("too many entries in allocation list"); 2857 #endif 2858 atomic_inc_64(&metaslab_trace_over_limit.value.ui64); 2859 zal->zal_size--; 2860 mat_next = list_next(&zal->zal_list, list_head(&zal->zal_list)); 2861 list_remove(&zal->zal_list, mat_next); 2862 kmem_cache_free(metaslab_alloc_trace_cache, mat_next); 2863 } 2864 2865 metaslab_alloc_trace_t *mat = 2866 kmem_cache_alloc(metaslab_alloc_trace_cache, KM_SLEEP); 2867 list_link_init(&mat->mat_list_node); 2868 mat->mat_mg = mg; 2869 mat->mat_msp = msp; 2870 mat->mat_size = psize; 2871 mat->mat_dva_id = dva_id; 2872 mat->mat_offset = offset; 2873 mat->mat_weight = 0; 2874 mat->mat_allocator = allocator; 2875 2876 if (msp != NULL) 2877 mat->mat_weight = msp->ms_weight; 2878 2879 /* 2880 * The list is part of the zio so locking is not required. Only 2881 * a single thread will perform allocations for a given zio. 2882 */ 2883 list_insert_tail(&zal->zal_list, mat); 2884 zal->zal_size++; 2885 2886 ASSERT3U(zal->zal_size, <=, metaslab_trace_max_entries); 2887 } 2888 2889 void 2890 metaslab_trace_init(zio_alloc_list_t *zal) 2891 { 2892 list_create(&zal->zal_list, sizeof (metaslab_alloc_trace_t), 2893 offsetof(metaslab_alloc_trace_t, mat_list_node)); 2894 zal->zal_size = 0; 2895 } 2896 2897 void 2898 metaslab_trace_fini(zio_alloc_list_t *zal) 2899 { 2900 metaslab_alloc_trace_t *mat; 2901 2902 while ((mat = list_remove_head(&zal->zal_list)) != NULL) 2903 kmem_cache_free(metaslab_alloc_trace_cache, mat); 2904 list_destroy(&zal->zal_list); 2905 zal->zal_size = 0; 2906 } 2907 2908 /* 2909 * ========================================================================== 2910 * Metaslab block operations 2911 * ========================================================================== 2912 */ 2913 2914 static void 2915 metaslab_group_alloc_increment(spa_t *spa, uint64_t vdev, void *tag, int flags, 2916 int allocator) 2917 { 2918 if (!(flags & METASLAB_ASYNC_ALLOC) || 2919 (flags & METASLAB_DONT_THROTTLE)) 2920 return; 2921 2922 metaslab_group_t *mg = vdev_lookup_top(spa, vdev)->vdev_mg; 2923 if (!mg->mg_class->mc_alloc_throttle_enabled) 2924 return; 2925 2926 (void) refcount_add(&mg->mg_alloc_queue_depth[allocator], tag); 2927 } 2928 2929 static void 2930 metaslab_group_increment_qdepth(metaslab_group_t *mg, int allocator) 2931 { 2932 uint64_t max = mg->mg_max_alloc_queue_depth; 2933 uint64_t cur = mg->mg_cur_max_alloc_queue_depth[allocator]; 2934 while (cur < max) { 2935 if (atomic_cas_64(&mg->mg_cur_max_alloc_queue_depth[allocator], 2936 cur, cur + 1) == cur) { 2937 atomic_inc_64( 2938 &mg->mg_class->mc_alloc_max_slots[allocator]); 2939 return; 2940 } 2941 cur = mg->mg_cur_max_alloc_queue_depth[allocator]; 2942 } 2943 } 2944 2945 void 2946 metaslab_group_alloc_decrement(spa_t *spa, uint64_t vdev, void *tag, int flags, 2947 int allocator, boolean_t io_complete) 2948 { 2949 if (!(flags & METASLAB_ASYNC_ALLOC) || 2950 (flags & METASLAB_DONT_THROTTLE)) 2951 return; 2952 2953 metaslab_group_t *mg = vdev_lookup_top(spa, vdev)->vdev_mg; 2954 if (!mg->mg_class->mc_alloc_throttle_enabled) 2955 return; 2956 2957 (void) refcount_remove(&mg->mg_alloc_queue_depth[allocator], tag); 2958 if (io_complete) 2959 metaslab_group_increment_qdepth(mg, allocator); 2960 } 2961 2962 void 2963 metaslab_group_alloc_verify(spa_t *spa, const blkptr_t *bp, void *tag, 2964 int allocator) 2965 { 2966 #ifdef ZFS_DEBUG 2967 const dva_t *dva = bp->blk_dva; 2968 int ndvas = BP_GET_NDVAS(bp); 2969 2970 for (int d = 0; d < ndvas; d++) { 2971 uint64_t vdev = DVA_GET_VDEV(&dva[d]); 2972 metaslab_group_t *mg = vdev_lookup_top(spa, vdev)->vdev_mg; 2973 VERIFY(refcount_not_held(&mg->mg_alloc_queue_depth[allocator], 2974 tag)); 2975 } 2976 #endif 2977 } 2978 2979 static uint64_t 2980 metaslab_block_alloc(metaslab_t *msp, uint64_t size, uint64_t txg) 2981 { 2982 uint64_t start; 2983 range_tree_t *rt = msp->ms_allocatable; 2984 metaslab_class_t *mc = msp->ms_group->mg_class; 2985 2986 VERIFY(!msp->ms_condensing); 2987 VERIFY0(msp->ms_initializing); 2988 2989 start = mc->mc_ops->msop_alloc(msp, size); 2990 if (start != -1ULL) { 2991 metaslab_group_t *mg = msp->ms_group; 2992 vdev_t *vd = mg->mg_vd; 2993 2994 VERIFY0(P2PHASE(start, 1ULL << vd->vdev_ashift)); 2995 VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift)); 2996 VERIFY3U(range_tree_space(rt) - size, <=, msp->ms_size); 2997 range_tree_remove(rt, start, size); 2998 2999 if (range_tree_is_empty(msp->ms_allocating[txg & TXG_MASK])) 3000 vdev_dirty(mg->mg_vd, VDD_METASLAB, msp, txg); 3001 3002 range_tree_add(msp->ms_allocating[txg & TXG_MASK], start, size); 3003 3004 /* Track the last successful allocation */ 3005 msp->ms_alloc_txg = txg; 3006 metaslab_verify_space(msp, txg); 3007 } 3008 3009 /* 3010 * Now that we've attempted the allocation we need to update the 3011 * metaslab's maximum block size since it may have changed. 3012 */ 3013 msp->ms_max_size = metaslab_block_maxsize(msp); 3014 return (start); 3015 } 3016 3017 /* 3018 * Find the metaslab with the highest weight that is less than what we've 3019 * already tried. In the common case, this means that we will examine each 3020 * metaslab at most once. Note that concurrent callers could reorder metaslabs 3021 * by activation/passivation once we have dropped the mg_lock. If a metaslab is 3022 * activated by another thread, and we fail to allocate from the metaslab we 3023 * have selected, we may not try the newly-activated metaslab, and instead 3024 * activate another metaslab. This is not optimal, but generally does not cause 3025 * any problems (a possible exception being if every metaslab is completely full 3026 * except for the the newly-activated metaslab which we fail to examine). 3027 */ 3028 static metaslab_t * 3029 find_valid_metaslab(metaslab_group_t *mg, uint64_t activation_weight, 3030 dva_t *dva, int d, uint64_t min_distance, uint64_t asize, int allocator, 3031 zio_alloc_list_t *zal, metaslab_t *search, boolean_t *was_active) 3032 { 3033 avl_index_t idx; 3034 avl_tree_t *t = &mg->mg_metaslab_tree; 3035 metaslab_t *msp = avl_find(t, search, &idx); 3036 if (msp == NULL) 3037 msp = avl_nearest(t, idx, AVL_AFTER); 3038 3039 for (; msp != NULL; msp = AVL_NEXT(t, msp)) { 3040 int i; 3041 if (!metaslab_should_allocate(msp, asize)) { 3042 metaslab_trace_add(zal, mg, msp, asize, d, 3043 TRACE_TOO_SMALL, allocator); 3044 continue; 3045 } 3046 3047 /* 3048 * If the selected metaslab is condensing or being 3049 * initialized, skip it. 3050 */ 3051 if (msp->ms_condensing || msp->ms_initializing > 0) 3052 continue; 3053 3054 *was_active = msp->ms_allocator != -1; 3055 /* 3056 * If we're activating as primary, this is our first allocation 3057 * from this disk, so we don't need to check how close we are. 3058 * If the metaslab under consideration was already active, 3059 * we're getting desperate enough to steal another allocator's 3060 * metaslab, so we still don't care about distances. 3061 */ 3062 if (activation_weight == METASLAB_WEIGHT_PRIMARY || *was_active) 3063 break; 3064 3065 uint64_t target_distance = min_distance 3066 + (space_map_allocated(msp->ms_sm) != 0 ? 0 : 3067 min_distance >> 1); 3068 3069 for (i = 0; i < d; i++) { 3070 if (metaslab_distance(msp, &dva[i]) < target_distance) 3071 break; 3072 } 3073 if (i == d) 3074 break; 3075 } 3076 3077 if (msp != NULL) { 3078 search->ms_weight = msp->ms_weight; 3079 search->ms_start = msp->ms_start + 1; 3080 search->ms_allocator = msp->ms_allocator; 3081 search->ms_primary = msp->ms_primary; 3082 } 3083 return (msp); 3084 } 3085 3086 /* ARGSUSED */ 3087 static uint64_t 3088 metaslab_group_alloc_normal(metaslab_group_t *mg, zio_alloc_list_t *zal, 3089 uint64_t asize, uint64_t txg, uint64_t min_distance, dva_t *dva, int d, 3090 int allocator) 3091 { 3092 metaslab_t *msp = NULL; 3093 uint64_t offset = -1ULL; 3094 uint64_t activation_weight; 3095 3096 activation_weight = METASLAB_WEIGHT_PRIMARY; 3097 for (int i = 0; i < d; i++) { 3098 if (activation_weight == METASLAB_WEIGHT_PRIMARY && 3099 DVA_GET_VDEV(&dva[i]) == mg->mg_vd->vdev_id) { 3100 activation_weight = METASLAB_WEIGHT_SECONDARY; 3101 } else if (activation_weight == METASLAB_WEIGHT_SECONDARY && 3102 DVA_GET_VDEV(&dva[i]) == mg->mg_vd->vdev_id) { 3103 activation_weight = METASLAB_WEIGHT_CLAIM; 3104 break; 3105 } 3106 } 3107 3108 /* 3109 * If we don't have enough metaslabs active to fill the entire array, we 3110 * just use the 0th slot. 3111 */ 3112 if (mg->mg_ms_ready < mg->mg_allocators * 3) 3113 allocator = 0; 3114 3115 ASSERT3U(mg->mg_vd->vdev_ms_count, >=, 2); 3116 3117 metaslab_t *search = kmem_alloc(sizeof (*search), KM_SLEEP); 3118 search->ms_weight = UINT64_MAX; 3119 search->ms_start = 0; 3120 /* 3121 * At the end of the metaslab tree are the already-active metaslabs, 3122 * first the primaries, then the secondaries. When we resume searching 3123 * through the tree, we need to consider ms_allocator and ms_primary so 3124 * we start in the location right after where we left off, and don't 3125 * accidentally loop forever considering the same metaslabs. 3126 */ 3127 search->ms_allocator = -1; 3128 search->ms_primary = B_TRUE; 3129 for (;;) { 3130 boolean_t was_active = B_FALSE; 3131 3132 mutex_enter(&mg->mg_lock); 3133 3134 if (activation_weight == METASLAB_WEIGHT_PRIMARY && 3135 mg->mg_primaries[allocator] != NULL) { 3136 msp = mg->mg_primaries[allocator]; 3137 was_active = B_TRUE; 3138 } else if (activation_weight == METASLAB_WEIGHT_SECONDARY && 3139 mg->mg_secondaries[allocator] != NULL) { 3140 msp = mg->mg_secondaries[allocator]; 3141 was_active = B_TRUE; 3142 } else { 3143 msp = find_valid_metaslab(mg, activation_weight, dva, d, 3144 min_distance, asize, allocator, zal, search, 3145 &was_active); 3146 } 3147 3148 mutex_exit(&mg->mg_lock); 3149 if (msp == NULL) { 3150 kmem_free(search, sizeof (*search)); 3151 return (-1ULL); 3152 } 3153 3154 mutex_enter(&msp->ms_lock); 3155 /* 3156 * Ensure that the metaslab we have selected is still 3157 * capable of handling our request. It's possible that 3158 * another thread may have changed the weight while we 3159 * were blocked on the metaslab lock. We check the 3160 * active status first to see if we need to reselect 3161 * a new metaslab. 3162 */ 3163 if (was_active && !(msp->ms_weight & METASLAB_ACTIVE_MASK)) { 3164 mutex_exit(&msp->ms_lock); 3165 continue; 3166 } 3167 3168 /* 3169 * If the metaslab is freshly activated for an allocator that 3170 * isn't the one we're allocating from, or if it's a primary and 3171 * we're seeking a secondary (or vice versa), we go back and 3172 * select a new metaslab. 3173 */ 3174 if (!was_active && (msp->ms_weight & METASLAB_ACTIVE_MASK) && 3175 (msp->ms_allocator != -1) && 3176 (msp->ms_allocator != allocator || ((activation_weight == 3177 METASLAB_WEIGHT_PRIMARY) != msp->ms_primary))) { 3178 mutex_exit(&msp->ms_lock); 3179 continue; 3180 } 3181 3182 if (msp->ms_weight & METASLAB_WEIGHT_CLAIM && 3183 activation_weight != METASLAB_WEIGHT_CLAIM) { 3184 metaslab_passivate(msp, msp->ms_weight & 3185 ~METASLAB_WEIGHT_CLAIM); 3186 mutex_exit(&msp->ms_lock); 3187 continue; 3188 } 3189 3190 if (metaslab_activate(msp, allocator, activation_weight) != 0) { 3191 mutex_exit(&msp->ms_lock); 3192 continue; 3193 } 3194 3195 msp->ms_selected_txg = txg; 3196 3197 /* 3198 * Now that we have the lock, recheck to see if we should 3199 * continue to use this metaslab for this allocation. The 3200 * the metaslab is now loaded so metaslab_should_allocate() can 3201 * accurately determine if the allocation attempt should 3202 * proceed. 3203 */ 3204 if (!metaslab_should_allocate(msp, asize)) { 3205 /* Passivate this metaslab and select a new one. */ 3206 metaslab_trace_add(zal, mg, msp, asize, d, 3207 TRACE_TOO_SMALL, allocator); 3208 goto next; 3209 } 3210 3211 /* 3212 * If this metaslab is currently condensing then pick again as 3213 * we can't manipulate this metaslab until it's committed 3214 * to disk. If this metaslab is being initialized, we shouldn't 3215 * allocate from it since the allocated region might be 3216 * overwritten after allocation. 3217 */ 3218 if (msp->ms_condensing) { 3219 metaslab_trace_add(zal, mg, msp, asize, d, 3220 TRACE_CONDENSING, allocator); 3221 metaslab_passivate(msp, msp->ms_weight & 3222 ~METASLAB_ACTIVE_MASK); 3223 mutex_exit(&msp->ms_lock); 3224 continue; 3225 } else if (msp->ms_initializing > 0) { 3226 metaslab_trace_add(zal, mg, msp, asize, d, 3227 TRACE_INITIALIZING, allocator); 3228 metaslab_passivate(msp, msp->ms_weight & 3229 ~METASLAB_ACTIVE_MASK); 3230 mutex_exit(&msp->ms_lock); 3231 continue; 3232 } 3233 3234 offset = metaslab_block_alloc(msp, asize, txg); 3235 metaslab_trace_add(zal, mg, msp, asize, d, offset, allocator); 3236 3237 if (offset != -1ULL) { 3238 /* Proactively passivate the metaslab, if needed */ 3239 metaslab_segment_may_passivate(msp); 3240 break; 3241 } 3242 next: 3243 ASSERT(msp->ms_loaded); 3244 3245 /* 3246 * We were unable to allocate from this metaslab so determine 3247 * a new weight for this metaslab. Now that we have loaded 3248 * the metaslab we can provide a better hint to the metaslab 3249 * selector. 3250 * 3251 * For space-based metaslabs, we use the maximum block size. 3252 * This information is only available when the metaslab 3253 * is loaded and is more accurate than the generic free 3254 * space weight that was calculated by metaslab_weight(). 3255 * This information allows us to quickly compare the maximum 3256 * available allocation in the metaslab to the allocation 3257 * size being requested. 3258 * 3259 * For segment-based metaslabs, determine the new weight 3260 * based on the highest bucket in the range tree. We 3261 * explicitly use the loaded segment weight (i.e. the range 3262 * tree histogram) since it contains the space that is 3263 * currently available for allocation and is accurate 3264 * even within a sync pass. 3265 */ 3266 if (WEIGHT_IS_SPACEBASED(msp->ms_weight)) { 3267 uint64_t weight = metaslab_block_maxsize(msp); 3268 WEIGHT_SET_SPACEBASED(weight); 3269 metaslab_passivate(msp, weight); 3270 } else { 3271 metaslab_passivate(msp, 3272 metaslab_weight_from_range_tree(msp)); 3273 } 3274 3275 /* 3276 * We have just failed an allocation attempt, check 3277 * that metaslab_should_allocate() agrees. Otherwise, 3278 * we may end up in an infinite loop retrying the same 3279 * metaslab. 3280 */ 3281 ASSERT(!metaslab_should_allocate(msp, asize)); 3282 mutex_exit(&msp->ms_lock); 3283 } 3284 mutex_exit(&msp->ms_lock); 3285 kmem_free(search, sizeof (*search)); 3286 return (offset); 3287 } 3288 3289 static uint64_t 3290 metaslab_group_alloc(metaslab_group_t *mg, zio_alloc_list_t *zal, 3291 uint64_t asize, uint64_t txg, uint64_t min_distance, dva_t *dva, int d, 3292 int allocator) 3293 { 3294 uint64_t offset; 3295 ASSERT(mg->mg_initialized); 3296 3297 offset = metaslab_group_alloc_normal(mg, zal, asize, txg, 3298 min_distance, dva, d, allocator); 3299 3300 mutex_enter(&mg->mg_lock); 3301 if (offset == -1ULL) { 3302 mg->mg_failed_allocations++; 3303 metaslab_trace_add(zal, mg, NULL, asize, d, 3304 TRACE_GROUP_FAILURE, allocator); 3305 if (asize == SPA_GANGBLOCKSIZE) { 3306 /* 3307 * This metaslab group was unable to allocate 3308 * the minimum gang block size so it must be out of 3309 * space. We must notify the allocation throttle 3310 * to start skipping allocation attempts to this 3311 * metaslab group until more space becomes available. 3312 * Note: this failure cannot be caused by the 3313 * allocation throttle since the allocation throttle 3314 * is only responsible for skipping devices and 3315 * not failing block allocations. 3316 */ 3317 mg->mg_no_free_space = B_TRUE; 3318 } 3319 } 3320 mg->mg_allocations++; 3321 mutex_exit(&mg->mg_lock); 3322 return (offset); 3323 } 3324 3325 /* 3326 * If we have to write a ditto block (i.e. more than one DVA for a given BP) 3327 * on the same vdev as an existing DVA of this BP, then try to allocate it 3328 * at least (vdev_asize / (2 ^ ditto_same_vdev_distance_shift)) away from the 3329 * existing DVAs. 3330 */ 3331 int ditto_same_vdev_distance_shift = 3; 3332 3333 /* 3334 * Allocate a block for the specified i/o. 3335 */ 3336 int 3337 metaslab_alloc_dva(spa_t *spa, metaslab_class_t *mc, uint64_t psize, 3338 dva_t *dva, int d, dva_t *hintdva, uint64_t txg, int flags, 3339 zio_alloc_list_t *zal, int allocator) 3340 { 3341 metaslab_group_t *mg, *rotor; 3342 vdev_t *vd; 3343 boolean_t try_hard = B_FALSE; 3344 3345 ASSERT(!DVA_IS_VALID(&dva[d])); 3346 3347 /* 3348 * For testing, make some blocks above a certain size be gang blocks. 3349 */ 3350 if (psize >= metaslab_force_ganging && (ddi_get_lbolt() & 3) == 0) { 3351 metaslab_trace_add(zal, NULL, NULL, psize, d, TRACE_FORCE_GANG, 3352 allocator); 3353 return (SET_ERROR(ENOSPC)); 3354 } 3355 3356 /* 3357 * Start at the rotor and loop through all mgs until we find something. 3358 * Note that there's no locking on mc_rotor or mc_aliquot because 3359 * nothing actually breaks if we miss a few updates -- we just won't 3360 * allocate quite as evenly. It all balances out over time. 3361 * 3362 * If we are doing ditto or log blocks, try to spread them across 3363 * consecutive vdevs. If we're forced to reuse a vdev before we've 3364 * allocated all of our ditto blocks, then try and spread them out on 3365 * that vdev as much as possible. If it turns out to not be possible, 3366 * gradually lower our standards until anything becomes acceptable. 3367 * Also, allocating on consecutive vdevs (as opposed to random vdevs) 3368 * gives us hope of containing our fault domains to something we're 3369 * able to reason about. Otherwise, any two top-level vdev failures 3370 * will guarantee the loss of data. With consecutive allocation, 3371 * only two adjacent top-level vdev failures will result in data loss. 3372 * 3373 * If we are doing gang blocks (hintdva is non-NULL), try to keep 3374 * ourselves on the same vdev as our gang block header. That 3375 * way, we can hope for locality in vdev_cache, plus it makes our 3376 * fault domains something tractable. 3377 */ 3378 if (hintdva) { 3379 vd = vdev_lookup_top(spa, DVA_GET_VDEV(&hintdva[d])); 3380 3381 /* 3382 * It's possible the vdev we're using as the hint no 3383 * longer exists or its mg has been closed (e.g. by 3384 * device removal). Consult the rotor when 3385 * all else fails. 3386 */ 3387 if (vd != NULL && vd->vdev_mg != NULL) { 3388 mg = vd->vdev_mg; 3389 3390 if (flags & METASLAB_HINTBP_AVOID && 3391 mg->mg_next != NULL) 3392 mg = mg->mg_next; 3393 } else { 3394 mg = mc->mc_rotor; 3395 } 3396 } else if (d != 0) { 3397 vd = vdev_lookup_top(spa, DVA_GET_VDEV(&dva[d - 1])); 3398 mg = vd->vdev_mg->mg_next; 3399 } else { 3400 mg = mc->mc_rotor; 3401 } 3402 3403 /* 3404 * If the hint put us into the wrong metaslab class, or into a 3405 * metaslab group that has been passivated, just follow the rotor. 3406 */ 3407 if (mg->mg_class != mc || mg->mg_activation_count <= 0) 3408 mg = mc->mc_rotor; 3409 3410 rotor = mg; 3411 top: 3412 do { 3413 boolean_t allocatable; 3414 3415 ASSERT(mg->mg_activation_count == 1); 3416 vd = mg->mg_vd; 3417 3418 /* 3419 * Don't allocate from faulted devices. 3420 */ 3421 if (try_hard) { 3422 spa_config_enter(spa, SCL_ZIO, FTAG, RW_READER); 3423 allocatable = vdev_allocatable(vd); 3424 spa_config_exit(spa, SCL_ZIO, FTAG); 3425 } else { 3426 allocatable = vdev_allocatable(vd); 3427 } 3428 3429 /* 3430 * Determine if the selected metaslab group is eligible 3431 * for allocations. If we're ganging then don't allow 3432 * this metaslab group to skip allocations since that would 3433 * inadvertently return ENOSPC and suspend the pool 3434 * even though space is still available. 3435 */ 3436 if (allocatable && !GANG_ALLOCATION(flags) && !try_hard) { 3437 allocatable = metaslab_group_allocatable(mg, rotor, 3438 psize, allocator); 3439 } 3440 3441 if (!allocatable) { 3442 metaslab_trace_add(zal, mg, NULL, psize, d, 3443 TRACE_NOT_ALLOCATABLE, allocator); 3444 goto next; 3445 } 3446 3447 ASSERT(mg->mg_initialized); 3448 3449 /* 3450 * Avoid writing single-copy data to a failing, 3451 * non-redundant vdev, unless we've already tried all 3452 * other vdevs. 3453 */ 3454 if ((vd->vdev_stat.vs_write_errors > 0 || 3455 vd->vdev_state < VDEV_STATE_HEALTHY) && 3456 d == 0 && !try_hard && vd->vdev_children == 0) { 3457 metaslab_trace_add(zal, mg, NULL, psize, d, 3458 TRACE_VDEV_ERROR, allocator); 3459 goto next; 3460 } 3461 3462 ASSERT(mg->mg_class == mc); 3463 3464 /* 3465 * If we don't need to try hard, then require that the 3466 * block be 1/8th of the device away from any other DVAs 3467 * in this BP. If we are trying hard, allow any offset 3468 * to be used (distance=0). 3469 */ 3470 uint64_t distance = 0; 3471 if (!try_hard) { 3472 distance = vd->vdev_asize >> 3473 ditto_same_vdev_distance_shift; 3474 if (distance <= (1ULL << vd->vdev_ms_shift)) 3475 distance = 0; 3476 } 3477 3478 uint64_t asize = vdev_psize_to_asize(vd, psize); 3479 ASSERT(P2PHASE(asize, 1ULL << vd->vdev_ashift) == 0); 3480 3481 uint64_t offset = metaslab_group_alloc(mg, zal, asize, txg, 3482 distance, dva, d, allocator); 3483 3484 if (offset != -1ULL) { 3485 /* 3486 * If we've just selected this metaslab group, 3487 * figure out whether the corresponding vdev is 3488 * over- or under-used relative to the pool, 3489 * and set an allocation bias to even it out. 3490 */ 3491 if (mc->mc_aliquot == 0 && metaslab_bias_enabled) { 3492 vdev_stat_t *vs = &vd->vdev_stat; 3493 int64_t vu, cu; 3494 3495 vu = (vs->vs_alloc * 100) / (vs->vs_space + 1); 3496 cu = (mc->mc_alloc * 100) / (mc->mc_space + 1); 3497 3498 /* 3499 * Calculate how much more or less we should 3500 * try to allocate from this device during 3501 * this iteration around the rotor. 3502 * For example, if a device is 80% full 3503 * and the pool is 20% full then we should 3504 * reduce allocations by 60% on this device. 3505 * 3506 * mg_bias = (20 - 80) * 512K / 100 = -307K 3507 * 3508 * This reduces allocations by 307K for this 3509 * iteration. 3510 */ 3511 mg->mg_bias = ((cu - vu) * 3512 (int64_t)mg->mg_aliquot) / 100; 3513 } else if (!metaslab_bias_enabled) { 3514 mg->mg_bias = 0; 3515 } 3516 3517 if (atomic_add_64_nv(&mc->mc_aliquot, asize) >= 3518 mg->mg_aliquot + mg->mg_bias) { 3519 mc->mc_rotor = mg->mg_next; 3520 mc->mc_aliquot = 0; 3521 } 3522 3523 DVA_SET_VDEV(&dva[d], vd->vdev_id); 3524 DVA_SET_OFFSET(&dva[d], offset); 3525 DVA_SET_GANG(&dva[d], !!(flags & METASLAB_GANG_HEADER)); 3526 DVA_SET_ASIZE(&dva[d], asize); 3527 3528 return (0); 3529 } 3530 next: 3531 mc->mc_rotor = mg->mg_next; 3532 mc->mc_aliquot = 0; 3533 } while ((mg = mg->mg_next) != rotor); 3534 3535 /* 3536 * If we haven't tried hard, do so now. 3537 */ 3538 if (!try_hard) { 3539 try_hard = B_TRUE; 3540 goto top; 3541 } 3542 3543 bzero(&dva[d], sizeof (dva_t)); 3544 3545 metaslab_trace_add(zal, rotor, NULL, psize, d, TRACE_ENOSPC, allocator); 3546 return (SET_ERROR(ENOSPC)); 3547 } 3548 3549 void 3550 metaslab_free_concrete(vdev_t *vd, uint64_t offset, uint64_t asize, 3551 boolean_t checkpoint) 3552 { 3553 metaslab_t *msp; 3554 spa_t *spa = vd->vdev_spa; 3555 3556 ASSERT(vdev_is_concrete(vd)); 3557 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 3558 ASSERT3U(offset >> vd->vdev_ms_shift, <, vd->vdev_ms_count); 3559 3560 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 3561 3562 VERIFY(!msp->ms_condensing); 3563 VERIFY3U(offset, >=, msp->ms_start); 3564 VERIFY3U(offset + asize, <=, msp->ms_start + msp->ms_size); 3565 VERIFY0(P2PHASE(offset, 1ULL << vd->vdev_ashift)); 3566 VERIFY0(P2PHASE(asize, 1ULL << vd->vdev_ashift)); 3567 3568 metaslab_check_free_impl(vd, offset, asize); 3569 3570 mutex_enter(&msp->ms_lock); 3571 if (range_tree_is_empty(msp->ms_freeing) && 3572 range_tree_is_empty(msp->ms_checkpointing)) { 3573 vdev_dirty(vd, VDD_METASLAB, msp, spa_syncing_txg(spa)); 3574 } 3575 3576 if (checkpoint) { 3577 ASSERT(spa_has_checkpoint(spa)); 3578 range_tree_add(msp->ms_checkpointing, offset, asize); 3579 } else { 3580 range_tree_add(msp->ms_freeing, offset, asize); 3581 } 3582 mutex_exit(&msp->ms_lock); 3583 } 3584 3585 /* ARGSUSED */ 3586 void 3587 metaslab_free_impl_cb(uint64_t inner_offset, vdev_t *vd, uint64_t offset, 3588 uint64_t size, void *arg) 3589 { 3590 boolean_t *checkpoint = arg; 3591 3592 ASSERT3P(checkpoint, !=, NULL); 3593 3594 if (vd->vdev_ops->vdev_op_remap != NULL) 3595 vdev_indirect_mark_obsolete(vd, offset, size); 3596 else 3597 metaslab_free_impl(vd, offset, size, *checkpoint); 3598 } 3599 3600 static void 3601 metaslab_free_impl(vdev_t *vd, uint64_t offset, uint64_t size, 3602 boolean_t checkpoint) 3603 { 3604 spa_t *spa = vd->vdev_spa; 3605 3606 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 3607 3608 if (spa_syncing_txg(spa) > spa_freeze_txg(spa)) 3609 return; 3610 3611 if (spa->spa_vdev_removal != NULL && 3612 spa->spa_vdev_removal->svr_vdev_id == vd->vdev_id && 3613 vdev_is_concrete(vd)) { 3614 /* 3615 * Note: we check if the vdev is concrete because when 3616 * we complete the removal, we first change the vdev to be 3617 * an indirect vdev (in open context), and then (in syncing 3618 * context) clear spa_vdev_removal. 3619 */ 3620 free_from_removing_vdev(vd, offset, size); 3621 } else if (vd->vdev_ops->vdev_op_remap != NULL) { 3622 vdev_indirect_mark_obsolete(vd, offset, size); 3623 vd->vdev_ops->vdev_op_remap(vd, offset, size, 3624 metaslab_free_impl_cb, &checkpoint); 3625 } else { 3626 metaslab_free_concrete(vd, offset, size, checkpoint); 3627 } 3628 } 3629 3630 typedef struct remap_blkptr_cb_arg { 3631 blkptr_t *rbca_bp; 3632 spa_remap_cb_t rbca_cb; 3633 vdev_t *rbca_remap_vd; 3634 uint64_t rbca_remap_offset; 3635 void *rbca_cb_arg; 3636 } remap_blkptr_cb_arg_t; 3637 3638 void 3639 remap_blkptr_cb(uint64_t inner_offset, vdev_t *vd, uint64_t offset, 3640 uint64_t size, void *arg) 3641 { 3642 remap_blkptr_cb_arg_t *rbca = arg; 3643 blkptr_t *bp = rbca->rbca_bp; 3644 3645 /* We can not remap split blocks. */ 3646 if (size != DVA_GET_ASIZE(&bp->blk_dva[0])) 3647 return; 3648 ASSERT0(inner_offset); 3649 3650 if (rbca->rbca_cb != NULL) { 3651 /* 3652 * At this point we know that we are not handling split 3653 * blocks and we invoke the callback on the previous 3654 * vdev which must be indirect. 3655 */ 3656 ASSERT3P(rbca->rbca_remap_vd->vdev_ops, ==, &vdev_indirect_ops); 3657 3658 rbca->rbca_cb(rbca->rbca_remap_vd->vdev_id, 3659 rbca->rbca_remap_offset, size, rbca->rbca_cb_arg); 3660 3661 /* set up remap_blkptr_cb_arg for the next call */ 3662 rbca->rbca_remap_vd = vd; 3663 rbca->rbca_remap_offset = offset; 3664 } 3665 3666 /* 3667 * The phys birth time is that of dva[0]. This ensures that we know 3668 * when each dva was written, so that resilver can determine which 3669 * blocks need to be scrubbed (i.e. those written during the time 3670 * the vdev was offline). It also ensures that the key used in 3671 * the ARC hash table is unique (i.e. dva[0] + phys_birth). If 3672 * we didn't change the phys_birth, a lookup in the ARC for a 3673 * remapped BP could find the data that was previously stored at 3674 * this vdev + offset. 3675 */ 3676 vdev_t *oldvd = vdev_lookup_top(vd->vdev_spa, 3677 DVA_GET_VDEV(&bp->blk_dva[0])); 3678 vdev_indirect_births_t *vib = oldvd->vdev_indirect_births; 3679 bp->blk_phys_birth = vdev_indirect_births_physbirth(vib, 3680 DVA_GET_OFFSET(&bp->blk_dva[0]), DVA_GET_ASIZE(&bp->blk_dva[0])); 3681 3682 DVA_SET_VDEV(&bp->blk_dva[0], vd->vdev_id); 3683 DVA_SET_OFFSET(&bp->blk_dva[0], offset); 3684 } 3685 3686 /* 3687 * If the block pointer contains any indirect DVAs, modify them to refer to 3688 * concrete DVAs. Note that this will sometimes not be possible, leaving 3689 * the indirect DVA in place. This happens if the indirect DVA spans multiple 3690 * segments in the mapping (i.e. it is a "split block"). 3691 * 3692 * If the BP was remapped, calls the callback on the original dva (note the 3693 * callback can be called multiple times if the original indirect DVA refers 3694 * to another indirect DVA, etc). 3695 * 3696 * Returns TRUE if the BP was remapped. 3697 */ 3698 boolean_t 3699 spa_remap_blkptr(spa_t *spa, blkptr_t *bp, spa_remap_cb_t callback, void *arg) 3700 { 3701 remap_blkptr_cb_arg_t rbca; 3702 3703 if (!zfs_remap_blkptr_enable) 3704 return (B_FALSE); 3705 3706 if (!spa_feature_is_enabled(spa, SPA_FEATURE_OBSOLETE_COUNTS)) 3707 return (B_FALSE); 3708 3709 /* 3710 * Dedup BP's can not be remapped, because ddt_phys_select() depends 3711 * on DVA[0] being the same in the BP as in the DDT (dedup table). 3712 */ 3713 if (BP_GET_DEDUP(bp)) 3714 return (B_FALSE); 3715 3716 /* 3717 * Gang blocks can not be remapped, because 3718 * zio_checksum_gang_verifier() depends on the DVA[0] that's in 3719 * the BP used to read the gang block header (GBH) being the same 3720 * as the DVA[0] that we allocated for the GBH. 3721 */ 3722 if (BP_IS_GANG(bp)) 3723 return (B_FALSE); 3724 3725 /* 3726 * Embedded BP's have no DVA to remap. 3727 */ 3728 if (BP_GET_NDVAS(bp) < 1) 3729 return (B_FALSE); 3730 3731 /* 3732 * Note: we only remap dva[0]. If we remapped other dvas, we 3733 * would no longer know what their phys birth txg is. 3734 */ 3735 dva_t *dva = &bp->blk_dva[0]; 3736 3737 uint64_t offset = DVA_GET_OFFSET(dva); 3738 uint64_t size = DVA_GET_ASIZE(dva); 3739 vdev_t *vd = vdev_lookup_top(spa, DVA_GET_VDEV(dva)); 3740 3741 if (vd->vdev_ops->vdev_op_remap == NULL) 3742 return (B_FALSE); 3743 3744 rbca.rbca_bp = bp; 3745 rbca.rbca_cb = callback; 3746 rbca.rbca_remap_vd = vd; 3747 rbca.rbca_remap_offset = offset; 3748 rbca.rbca_cb_arg = arg; 3749 3750 /* 3751 * remap_blkptr_cb() will be called in order for each level of 3752 * indirection, until a concrete vdev is reached or a split block is 3753 * encountered. old_vd and old_offset are updated within the callback 3754 * as we go from the one indirect vdev to the next one (either concrete 3755 * or indirect again) in that order. 3756 */ 3757 vd->vdev_ops->vdev_op_remap(vd, offset, size, remap_blkptr_cb, &rbca); 3758 3759 /* Check if the DVA wasn't remapped because it is a split block */ 3760 if (DVA_GET_VDEV(&rbca.rbca_bp->blk_dva[0]) == vd->vdev_id) 3761 return (B_FALSE); 3762 3763 return (B_TRUE); 3764 } 3765 3766 /* 3767 * Undo the allocation of a DVA which happened in the given transaction group. 3768 */ 3769 void 3770 metaslab_unalloc_dva(spa_t *spa, const dva_t *dva, uint64_t txg) 3771 { 3772 metaslab_t *msp; 3773 vdev_t *vd; 3774 uint64_t vdev = DVA_GET_VDEV(dva); 3775 uint64_t offset = DVA_GET_OFFSET(dva); 3776 uint64_t size = DVA_GET_ASIZE(dva); 3777 3778 ASSERT(DVA_IS_VALID(dva)); 3779 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 3780 3781 if (txg > spa_freeze_txg(spa)) 3782 return; 3783 3784 if ((vd = vdev_lookup_top(spa, vdev)) == NULL || 3785 (offset >> vd->vdev_ms_shift) >= vd->vdev_ms_count) { 3786 cmn_err(CE_WARN, "metaslab_free_dva(): bad DVA %llu:%llu", 3787 (u_longlong_t)vdev, (u_longlong_t)offset); 3788 ASSERT(0); 3789 return; 3790 } 3791 3792 ASSERT(!vd->vdev_removing); 3793 ASSERT(vdev_is_concrete(vd)); 3794 ASSERT0(vd->vdev_indirect_config.vic_mapping_object); 3795 ASSERT3P(vd->vdev_indirect_mapping, ==, NULL); 3796 3797 if (DVA_GET_GANG(dva)) 3798 size = vdev_psize_to_asize(vd, SPA_GANGBLOCKSIZE); 3799 3800 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 3801 3802 mutex_enter(&msp->ms_lock); 3803 range_tree_remove(msp->ms_allocating[txg & TXG_MASK], 3804 offset, size); 3805 3806 VERIFY(!msp->ms_condensing); 3807 VERIFY3U(offset, >=, msp->ms_start); 3808 VERIFY3U(offset + size, <=, msp->ms_start + msp->ms_size); 3809 VERIFY3U(range_tree_space(msp->ms_allocatable) + size, <=, 3810 msp->ms_size); 3811 VERIFY0(P2PHASE(offset, 1ULL << vd->vdev_ashift)); 3812 VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift)); 3813 range_tree_add(msp->ms_allocatable, offset, size); 3814 mutex_exit(&msp->ms_lock); 3815 } 3816 3817 /* 3818 * Free the block represented by the given DVA. 3819 */ 3820 void 3821 metaslab_free_dva(spa_t *spa, const dva_t *dva, boolean_t checkpoint) 3822 { 3823 uint64_t vdev = DVA_GET_VDEV(dva); 3824 uint64_t offset = DVA_GET_OFFSET(dva); 3825 uint64_t size = DVA_GET_ASIZE(dva); 3826 vdev_t *vd = vdev_lookup_top(spa, vdev); 3827 3828 ASSERT(DVA_IS_VALID(dva)); 3829 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 3830 3831 if (DVA_GET_GANG(dva)) { 3832 size = vdev_psize_to_asize(vd, SPA_GANGBLOCKSIZE); 3833 } 3834 3835 metaslab_free_impl(vd, offset, size, checkpoint); 3836 } 3837 3838 /* 3839 * Reserve some allocation slots. The reservation system must be called 3840 * before we call into the allocator. If there aren't any available slots 3841 * then the I/O will be throttled until an I/O completes and its slots are 3842 * freed up. The function returns true if it was successful in placing 3843 * the reservation. 3844 */ 3845 boolean_t 3846 metaslab_class_throttle_reserve(metaslab_class_t *mc, int slots, int allocator, 3847 zio_t *zio, int flags) 3848 { 3849 uint64_t available_slots = 0; 3850 boolean_t slot_reserved = B_FALSE; 3851 uint64_t max = mc->mc_alloc_max_slots[allocator]; 3852 3853 ASSERT(mc->mc_alloc_throttle_enabled); 3854 mutex_enter(&mc->mc_lock); 3855 3856 uint64_t reserved_slots = 3857 refcount_count(&mc->mc_alloc_slots[allocator]); 3858 if (reserved_slots < max) 3859 available_slots = max - reserved_slots; 3860 3861 if (slots <= available_slots || GANG_ALLOCATION(flags)) { 3862 /* 3863 * We reserve the slots individually so that we can unreserve 3864 * them individually when an I/O completes. 3865 */ 3866 for (int d = 0; d < slots; d++) { 3867 reserved_slots = 3868 refcount_add(&mc->mc_alloc_slots[allocator], 3869 zio); 3870 } 3871 zio->io_flags |= ZIO_FLAG_IO_ALLOCATING; 3872 slot_reserved = B_TRUE; 3873 } 3874 3875 mutex_exit(&mc->mc_lock); 3876 return (slot_reserved); 3877 } 3878 3879 void 3880 metaslab_class_throttle_unreserve(metaslab_class_t *mc, int slots, 3881 int allocator, zio_t *zio) 3882 { 3883 ASSERT(mc->mc_alloc_throttle_enabled); 3884 mutex_enter(&mc->mc_lock); 3885 for (int d = 0; d < slots; d++) { 3886 (void) refcount_remove(&mc->mc_alloc_slots[allocator], 3887 zio); 3888 } 3889 mutex_exit(&mc->mc_lock); 3890 } 3891 3892 static int 3893 metaslab_claim_concrete(vdev_t *vd, uint64_t offset, uint64_t size, 3894 uint64_t txg) 3895 { 3896 metaslab_t *msp; 3897 spa_t *spa = vd->vdev_spa; 3898 int error = 0; 3899 3900 if (offset >> vd->vdev_ms_shift >= vd->vdev_ms_count) 3901 return (ENXIO); 3902 3903 ASSERT3P(vd->vdev_ms, !=, NULL); 3904 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 3905 3906 mutex_enter(&msp->ms_lock); 3907 3908 if ((txg != 0 && spa_writeable(spa)) || !msp->ms_loaded) 3909 error = metaslab_activate(msp, 0, METASLAB_WEIGHT_CLAIM); 3910 /* 3911 * No need to fail in that case; someone else has activated the 3912 * metaslab, but that doesn't preclude us from using it. 3913 */ 3914 if (error == EBUSY) 3915 error = 0; 3916 3917 if (error == 0 && 3918 !range_tree_contains(msp->ms_allocatable, offset, size)) 3919 error = SET_ERROR(ENOENT); 3920 3921 if (error || txg == 0) { /* txg == 0 indicates dry run */ 3922 mutex_exit(&msp->ms_lock); 3923 return (error); 3924 } 3925 3926 VERIFY(!msp->ms_condensing); 3927 VERIFY0(P2PHASE(offset, 1ULL << vd->vdev_ashift)); 3928 VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift)); 3929 VERIFY3U(range_tree_space(msp->ms_allocatable) - size, <=, 3930 msp->ms_size); 3931 range_tree_remove(msp->ms_allocatable, offset, size); 3932 3933 if (spa_writeable(spa)) { /* don't dirty if we're zdb(1M) */ 3934 if (range_tree_is_empty(msp->ms_allocating[txg & TXG_MASK])) 3935 vdev_dirty(vd, VDD_METASLAB, msp, txg); 3936 range_tree_add(msp->ms_allocating[txg & TXG_MASK], 3937 offset, size); 3938 } 3939 3940 mutex_exit(&msp->ms_lock); 3941 3942 return (0); 3943 } 3944 3945 typedef struct metaslab_claim_cb_arg_t { 3946 uint64_t mcca_txg; 3947 int mcca_error; 3948 } metaslab_claim_cb_arg_t; 3949 3950 /* ARGSUSED */ 3951 static void 3952 metaslab_claim_impl_cb(uint64_t inner_offset, vdev_t *vd, uint64_t offset, 3953 uint64_t size, void *arg) 3954 { 3955 metaslab_claim_cb_arg_t *mcca_arg = arg; 3956 3957 if (mcca_arg->mcca_error == 0) { 3958 mcca_arg->mcca_error = metaslab_claim_concrete(vd, offset, 3959 size, mcca_arg->mcca_txg); 3960 } 3961 } 3962 3963 int 3964 metaslab_claim_impl(vdev_t *vd, uint64_t offset, uint64_t size, uint64_t txg) 3965 { 3966 if (vd->vdev_ops->vdev_op_remap != NULL) { 3967 metaslab_claim_cb_arg_t arg; 3968 3969 /* 3970 * Only zdb(1M) can claim on indirect vdevs. This is used 3971 * to detect leaks of mapped space (that are not accounted 3972 * for in the obsolete counts, spacemap, or bpobj). 3973 */ 3974 ASSERT(!spa_writeable(vd->vdev_spa)); 3975 arg.mcca_error = 0; 3976 arg.mcca_txg = txg; 3977 3978 vd->vdev_ops->vdev_op_remap(vd, offset, size, 3979 metaslab_claim_impl_cb, &arg); 3980 3981 if (arg.mcca_error == 0) { 3982 arg.mcca_error = metaslab_claim_concrete(vd, 3983 offset, size, txg); 3984 } 3985 return (arg.mcca_error); 3986 } else { 3987 return (metaslab_claim_concrete(vd, offset, size, txg)); 3988 } 3989 } 3990 3991 /* 3992 * Intent log support: upon opening the pool after a crash, notify the SPA 3993 * of blocks that the intent log has allocated for immediate write, but 3994 * which are still considered free by the SPA because the last transaction 3995 * group didn't commit yet. 3996 */ 3997 static int 3998 metaslab_claim_dva(spa_t *spa, const dva_t *dva, uint64_t txg) 3999 { 4000 uint64_t vdev = DVA_GET_VDEV(dva); 4001 uint64_t offset = DVA_GET_OFFSET(dva); 4002 uint64_t size = DVA_GET_ASIZE(dva); 4003 vdev_t *vd; 4004 4005 if ((vd = vdev_lookup_top(spa, vdev)) == NULL) { 4006 return (SET_ERROR(ENXIO)); 4007 } 4008 4009 ASSERT(DVA_IS_VALID(dva)); 4010 4011 if (DVA_GET_GANG(dva)) 4012 size = vdev_psize_to_asize(vd, SPA_GANGBLOCKSIZE); 4013 4014 return (metaslab_claim_impl(vd, offset, size, txg)); 4015 } 4016 4017 int 4018 metaslab_alloc(spa_t *spa, metaslab_class_t *mc, uint64_t psize, blkptr_t *bp, 4019 int ndvas, uint64_t txg, blkptr_t *hintbp, int flags, 4020 zio_alloc_list_t *zal, zio_t *zio, int allocator) 4021 { 4022 dva_t *dva = bp->blk_dva; 4023 dva_t *hintdva = hintbp->blk_dva; 4024 int error = 0; 4025 4026 ASSERT(bp->blk_birth == 0); 4027 ASSERT(BP_PHYSICAL_BIRTH(bp) == 0); 4028 4029 spa_config_enter(spa, SCL_ALLOC, FTAG, RW_READER); 4030 4031 if (mc->mc_rotor == NULL) { /* no vdevs in this class */ 4032 spa_config_exit(spa, SCL_ALLOC, FTAG); 4033 return (SET_ERROR(ENOSPC)); 4034 } 4035 4036 ASSERT(ndvas > 0 && ndvas <= spa_max_replication(spa)); 4037 ASSERT(BP_GET_NDVAS(bp) == 0); 4038 ASSERT(hintbp == NULL || ndvas <= BP_GET_NDVAS(hintbp)); 4039 ASSERT3P(zal, !=, NULL); 4040 4041 for (int d = 0; d < ndvas; d++) { 4042 error = metaslab_alloc_dva(spa, mc, psize, dva, d, hintdva, 4043 txg, flags, zal, allocator); 4044 if (error != 0) { 4045 for (d--; d >= 0; d--) { 4046 metaslab_unalloc_dva(spa, &dva[d], txg); 4047 metaslab_group_alloc_decrement(spa, 4048 DVA_GET_VDEV(&dva[d]), zio, flags, 4049 allocator, B_FALSE); 4050 bzero(&dva[d], sizeof (dva_t)); 4051 } 4052 spa_config_exit(spa, SCL_ALLOC, FTAG); 4053 return (error); 4054 } else { 4055 /* 4056 * Update the metaslab group's queue depth 4057 * based on the newly allocated dva. 4058 */ 4059 metaslab_group_alloc_increment(spa, 4060 DVA_GET_VDEV(&dva[d]), zio, flags, allocator); 4061 } 4062 4063 } 4064 ASSERT(error == 0); 4065 ASSERT(BP_GET_NDVAS(bp) == ndvas); 4066 4067 spa_config_exit(spa, SCL_ALLOC, FTAG); 4068 4069 BP_SET_BIRTH(bp, txg, txg); 4070 4071 return (0); 4072 } 4073 4074 void 4075 metaslab_free(spa_t *spa, const blkptr_t *bp, uint64_t txg, boolean_t now) 4076 { 4077 const dva_t *dva = bp->blk_dva; 4078 int ndvas = BP_GET_NDVAS(bp); 4079 4080 ASSERT(!BP_IS_HOLE(bp)); 4081 ASSERT(!now || bp->blk_birth >= spa_syncing_txg(spa)); 4082 4083 /* 4084 * If we have a checkpoint for the pool we need to make sure that 4085 * the blocks that we free that are part of the checkpoint won't be 4086 * reused until the checkpoint is discarded or we revert to it. 4087 * 4088 * The checkpoint flag is passed down the metaslab_free code path 4089 * and is set whenever we want to add a block to the checkpoint's 4090 * accounting. That is, we "checkpoint" blocks that existed at the 4091 * time the checkpoint was created and are therefore referenced by 4092 * the checkpointed uberblock. 4093 * 4094 * Note that, we don't checkpoint any blocks if the current 4095 * syncing txg <= spa_checkpoint_txg. We want these frees to sync 4096 * normally as they will be referenced by the checkpointed uberblock. 4097 */ 4098 boolean_t checkpoint = B_FALSE; 4099 if (bp->blk_birth <= spa->spa_checkpoint_txg && 4100 spa_syncing_txg(spa) > spa->spa_checkpoint_txg) { 4101 /* 4102 * At this point, if the block is part of the checkpoint 4103 * there is no way it was created in the current txg. 4104 */ 4105 ASSERT(!now); 4106 ASSERT3U(spa_syncing_txg(spa), ==, txg); 4107 checkpoint = B_TRUE; 4108 } 4109 4110 spa_config_enter(spa, SCL_FREE, FTAG, RW_READER); 4111 4112 for (int d = 0; d < ndvas; d++) { 4113 if (now) { 4114 metaslab_unalloc_dva(spa, &dva[d], txg); 4115 } else { 4116 ASSERT3U(txg, ==, spa_syncing_txg(spa)); 4117 metaslab_free_dva(spa, &dva[d], checkpoint); 4118 } 4119 } 4120 4121 spa_config_exit(spa, SCL_FREE, FTAG); 4122 } 4123 4124 int 4125 metaslab_claim(spa_t *spa, const blkptr_t *bp, uint64_t txg) 4126 { 4127 const dva_t *dva = bp->blk_dva; 4128 int ndvas = BP_GET_NDVAS(bp); 4129 int error = 0; 4130 4131 ASSERT(!BP_IS_HOLE(bp)); 4132 4133 if (txg != 0) { 4134 /* 4135 * First do a dry run to make sure all DVAs are claimable, 4136 * so we don't have to unwind from partial failures below. 4137 */ 4138 if ((error = metaslab_claim(spa, bp, 0)) != 0) 4139 return (error); 4140 } 4141 4142 spa_config_enter(spa, SCL_ALLOC, FTAG, RW_READER); 4143 4144 for (int d = 0; d < ndvas; d++) 4145 if ((error = metaslab_claim_dva(spa, &dva[d], txg)) != 0) 4146 break; 4147 4148 spa_config_exit(spa, SCL_ALLOC, FTAG); 4149 4150 ASSERT(error == 0 || txg == 0); 4151 4152 return (error); 4153 } 4154 4155 /* ARGSUSED */ 4156 static void 4157 metaslab_check_free_impl_cb(uint64_t inner, vdev_t *vd, uint64_t offset, 4158 uint64_t size, void *arg) 4159 { 4160 if (vd->vdev_ops == &vdev_indirect_ops) 4161 return; 4162 4163 metaslab_check_free_impl(vd, offset, size); 4164 } 4165 4166 static void 4167 metaslab_check_free_impl(vdev_t *vd, uint64_t offset, uint64_t size) 4168 { 4169 metaslab_t *msp; 4170 spa_t *spa = vd->vdev_spa; 4171 4172 if ((zfs_flags & ZFS_DEBUG_ZIO_FREE) == 0) 4173 return; 4174 4175 if (vd->vdev_ops->vdev_op_remap != NULL) { 4176 vd->vdev_ops->vdev_op_remap(vd, offset, size, 4177 metaslab_check_free_impl_cb, NULL); 4178 return; 4179 } 4180 4181 ASSERT(vdev_is_concrete(vd)); 4182 ASSERT3U(offset >> vd->vdev_ms_shift, <, vd->vdev_ms_count); 4183 ASSERT3U(spa_config_held(spa, SCL_ALL, RW_READER), !=, 0); 4184 4185 msp = vd->vdev_ms[offset >> vd->vdev_ms_shift]; 4186 4187 mutex_enter(&msp->ms_lock); 4188 if (msp->ms_loaded) 4189 range_tree_verify(msp->ms_allocatable, offset, size); 4190 4191 range_tree_verify(msp->ms_freeing, offset, size); 4192 range_tree_verify(msp->ms_checkpointing, offset, size); 4193 range_tree_verify(msp->ms_freed, offset, size); 4194 for (int j = 0; j < TXG_DEFER_SIZE; j++) 4195 range_tree_verify(msp->ms_defer[j], offset, size); 4196 mutex_exit(&msp->ms_lock); 4197 } 4198 4199 void 4200 metaslab_check_free(spa_t *spa, const blkptr_t *bp) 4201 { 4202 if ((zfs_flags & ZFS_DEBUG_ZIO_FREE) == 0) 4203 return; 4204 4205 spa_config_enter(spa, SCL_VDEV, FTAG, RW_READER); 4206 for (int i = 0; i < BP_GET_NDVAS(bp); i++) { 4207 uint64_t vdev = DVA_GET_VDEV(&bp->blk_dva[i]); 4208 vdev_t *vd = vdev_lookup_top(spa, vdev); 4209 uint64_t offset = DVA_GET_OFFSET(&bp->blk_dva[i]); 4210 uint64_t size = DVA_GET_ASIZE(&bp->blk_dva[i]); 4211 4212 if (DVA_GET_GANG(&bp->blk_dva[i])) 4213 size = vdev_psize_to_asize(vd, SPA_GANGBLOCKSIZE); 4214 4215 ASSERT3P(vd, !=, NULL); 4216 4217 metaslab_check_free_impl(vd, offset, size); 4218 } 4219 spa_config_exit(spa, SCL_VDEV, FTAG); 4220 } 4221