1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright (C) 2018 Intel Corporation. 3 * Copyright 2023 Solidigm All Rights Reserved 4 * All rights reserved. 5 */ 6 7 #include "spdk/stdinc.h" 8 #include "spdk/crc32.h" 9 #include "spdk/likely.h" 10 #include "spdk/util.h" 11 #include "spdk/ftl.h" 12 13 #include "ftl_band.h" 14 #include "ftl_io.h" 15 #include "ftl_core.h" 16 #include "ftl_debug.h" 17 #include "ftl_internal.h" 18 #include "utils/ftl_md.h" 19 #include "utils/ftl_defs.h" 20 21 static uint64_t 22 ftl_band_tail_md_offset(const struct ftl_band *band) 23 { 24 return ftl_get_num_blocks_in_band(band->dev) - 25 ftl_tail_md_num_blocks(band->dev); 26 } 27 28 int 29 ftl_band_filled(struct ftl_band *band, size_t offset) 30 { 31 return offset == ftl_band_tail_md_offset(band); 32 } 33 34 static void 35 ftl_band_free_p2l_map(struct ftl_band *band) 36 { 37 struct spdk_ftl_dev *dev = band->dev; 38 struct ftl_p2l_map *p2l_map = &band->p2l_map; 39 40 assert(band->md->state == FTL_BAND_STATE_CLOSED || 41 band->md->state == FTL_BAND_STATE_FREE); 42 assert(p2l_map->ref_cnt == 0); 43 assert(p2l_map->band_map != NULL); 44 45 band->md->df_p2l_map = FTL_DF_OBJ_ID_INVALID; 46 ftl_mempool_put(dev->p2l_pool, p2l_map->band_map); 47 p2l_map->band_map = NULL; 48 } 49 50 51 static void 52 ftl_band_free_md_entry(struct ftl_band *band) 53 { 54 struct spdk_ftl_dev *dev = band->dev; 55 struct ftl_p2l_map *p2l_map = &band->p2l_map; 56 57 assert(band->md->state == FTL_BAND_STATE_CLOSED || 58 band->md->state == FTL_BAND_STATE_FREE); 59 assert(p2l_map->band_dma_md != NULL); 60 61 ftl_mempool_put(dev->band_md_pool, p2l_map->band_dma_md); 62 p2l_map->band_dma_md = NULL; 63 } 64 65 static void 66 _ftl_band_set_free(struct ftl_band *band) 67 { 68 struct spdk_ftl_dev *dev = band->dev; 69 70 /* Add the band to the free band list */ 71 TAILQ_INSERT_TAIL(&dev->free_bands, band, queue_entry); 72 band->md->close_seq_id = 0; 73 band->reloc = false; 74 75 dev->num_free++; 76 ftl_apply_limits(dev); 77 78 band->md->p2l_map_checksum = 0; 79 } 80 81 static void 82 _ftl_band_set_preparing(struct ftl_band *band) 83 { 84 struct spdk_ftl_dev *dev = band->dev; 85 86 /* Remove band from free list */ 87 TAILQ_REMOVE(&dev->free_bands, band, queue_entry); 88 89 band->md->wr_cnt++; 90 91 assert(dev->num_free > 0); 92 dev->num_free--; 93 94 ftl_apply_limits(dev); 95 } 96 97 static void 98 _ftl_band_set_closed_cb(struct ftl_band *band, bool valid) 99 { 100 struct spdk_ftl_dev *dev = band->dev; 101 102 assert(valid == true); 103 104 /* Set the state as free_md() checks for that */ 105 band->md->state = FTL_BAND_STATE_CLOSED; 106 if (band->owner.state_change_fn) { 107 band->owner.state_change_fn(band); 108 } 109 110 ftl_p2l_validate_ckpt(band); 111 112 /* Free the P2L map if there are no outstanding IOs */ 113 ftl_band_release_p2l_map(band); 114 assert(band->p2l_map.ref_cnt == 0); 115 116 TAILQ_INSERT_TAIL(&dev->shut_bands, band, queue_entry); 117 } 118 119 static void 120 _ftl_band_set_closed(struct ftl_band *band) 121 { 122 /* Verify that band's metadata is consistent with l2p */ 123 ftl_band_validate_md(band, _ftl_band_set_closed_cb); 124 } 125 126 ftl_addr 127 ftl_band_tail_md_addr(struct ftl_band *band) 128 { 129 ftl_addr addr; 130 131 /* Metadata should be aligned to xfer size */ 132 assert(ftl_band_tail_md_offset(band) % band->dev->xfer_size == 0); 133 134 addr = ftl_band_tail_md_offset(band) + band->start_addr; 135 136 return addr; 137 } 138 139 const char * 140 ftl_band_get_state_name(struct ftl_band *band) 141 { 142 static const char *names[] = { 143 "FREE", "PREPARING", "OPENING", "OPEN", "FULL", "CLOSING", 144 "CLOSED", 145 }; 146 147 assert(band->md->state < SPDK_COUNTOF(names)); 148 if (band->md->state < SPDK_COUNTOF(names)) { 149 return names[band->md->state]; 150 } else { 151 assert(false); 152 return "?"; 153 } 154 } 155 156 void 157 ftl_band_set_state(struct ftl_band *band, enum ftl_band_state state) 158 { 159 switch (state) { 160 case FTL_BAND_STATE_FREE: 161 assert(band->md->state == FTL_BAND_STATE_CLOSED); 162 _ftl_band_set_free(band); 163 break; 164 165 case FTL_BAND_STATE_PREP: 166 assert(band->md->state == FTL_BAND_STATE_FREE); 167 _ftl_band_set_preparing(band); 168 break; 169 170 case FTL_BAND_STATE_CLOSED: 171 if (band->md->state != FTL_BAND_STATE_CLOSED) { 172 assert(band->md->state == FTL_BAND_STATE_CLOSING); 173 _ftl_band_set_closed(band); 174 return; /* state can be changed asynchronously */ 175 } 176 break; 177 178 case FTL_BAND_STATE_OPEN: 179 band->md->p2l_map_checksum = 0; 180 break; 181 case FTL_BAND_STATE_OPENING: 182 case FTL_BAND_STATE_FULL: 183 case FTL_BAND_STATE_CLOSING: 184 break; 185 default: 186 FTL_ERRLOG(band->dev, "Unknown band state, %u", state); 187 assert(false); 188 break; 189 } 190 191 band->md->state = state; 192 } 193 194 void 195 ftl_band_set_type(struct ftl_band *band, enum ftl_band_type type) 196 { 197 switch (type) { 198 case FTL_BAND_TYPE_COMPACTION: 199 case FTL_BAND_TYPE_GC: 200 band->md->type = type; 201 break; 202 default: 203 assert(false); 204 break; 205 } 206 } 207 208 void 209 ftl_band_set_p2l(struct ftl_band *band, uint64_t lba, ftl_addr addr, uint64_t seq_id) 210 { 211 struct ftl_p2l_map *p2l_map = &band->p2l_map; 212 uint64_t offset; 213 214 offset = ftl_band_block_offset_from_addr(band, addr); 215 216 p2l_map->band_map[offset].lba = lba; 217 p2l_map->band_map[offset].seq_id = seq_id; 218 } 219 220 void 221 ftl_band_set_addr(struct ftl_band *band, uint64_t lba, ftl_addr addr) 222 { 223 band->p2l_map.num_valid++; 224 ftl_bitmap_set(band->dev->valid_map, addr); 225 } 226 227 size_t 228 ftl_band_user_blocks_left(const struct ftl_band *band, size_t offset) 229 { 230 size_t tail_md_offset = ftl_band_tail_md_offset(band); 231 232 if (spdk_unlikely(offset > tail_md_offset)) { 233 return 0; 234 } 235 236 return tail_md_offset - offset; 237 } 238 239 size_t 240 ftl_band_user_blocks(const struct ftl_band *band) 241 { 242 return ftl_get_num_blocks_in_band(band->dev) - 243 ftl_tail_md_num_blocks(band->dev); 244 } 245 246 static inline uint64_t 247 ftl_addr_get_band(const struct spdk_ftl_dev *dev, ftl_addr addr) 248 { 249 return (addr - dev->bands->start_addr) / ftl_get_num_blocks_in_band(dev); 250 } 251 252 struct ftl_band * 253 ftl_band_from_addr(struct spdk_ftl_dev *dev, ftl_addr addr) 254 { 255 uint64_t band_id = ftl_addr_get_band(dev, addr); 256 257 assert(band_id < ftl_get_num_bands(dev)); 258 return &dev->bands[band_id]; 259 } 260 261 uint64_t 262 ftl_band_block_offset_from_addr(struct ftl_band *band, ftl_addr addr) 263 { 264 assert(ftl_addr_get_band(band->dev, addr) == band->id); 265 return addr - band->start_addr; 266 } 267 268 ftl_addr 269 ftl_band_next_xfer_addr(struct ftl_band *band, ftl_addr addr, size_t num_blocks) 270 { 271 struct spdk_ftl_dev *dev = band->dev; 272 size_t num_xfers; 273 uint64_t offset; 274 275 assert(ftl_addr_get_band(dev, addr) == band->id); 276 277 offset = addr - band->start_addr; 278 279 /* In case starting address wasn't aligned to xfer_size, we'll align for consistent calculation 280 * purposes - the unaligned value will be preserved at the end however. 281 */ 282 num_blocks += (offset % dev->xfer_size); 283 offset -= (offset % dev->xfer_size); 284 285 /* Calculate offset based on xfer_size aligned writes */ 286 num_xfers = (num_blocks / dev->xfer_size); 287 offset += num_xfers * dev->xfer_size; 288 num_blocks -= num_xfers * dev->xfer_size; 289 290 if (offset > ftl_get_num_blocks_in_band(dev)) { 291 return FTL_ADDR_INVALID; 292 } 293 294 /* If there's any unalignment (either starting addr value or num_blocks), reintroduce it to the final address 295 */ 296 if (num_blocks) { 297 offset += num_blocks; 298 if (offset > ftl_get_num_blocks_in_band(dev)) { 299 return FTL_ADDR_INVALID; 300 } 301 } 302 303 addr = band->start_addr + offset; 304 return addr; 305 } 306 307 ftl_addr 308 ftl_band_addr_from_block_offset(struct ftl_band *band, uint64_t block_off) 309 { 310 ftl_addr addr; 311 312 addr = block_off + band->start_addr; 313 return addr; 314 } 315 316 ftl_addr 317 ftl_band_next_addr(struct ftl_band *band, ftl_addr addr, size_t offset) 318 { 319 uint64_t block_off = ftl_band_block_offset_from_addr(band, addr); 320 321 return ftl_band_addr_from_block_offset(band, block_off + offset); 322 } 323 324 void 325 ftl_band_acquire_p2l_map(struct ftl_band *band) 326 { 327 assert(band->p2l_map.band_map != NULL); 328 band->p2l_map.ref_cnt++; 329 } 330 331 static int 332 ftl_band_alloc_md_entry(struct ftl_band *band) 333 { 334 struct spdk_ftl_dev *dev = band->dev; 335 struct ftl_p2l_map *p2l_map = &band->p2l_map; 336 struct ftl_layout_region *region = ftl_layout_region_get(dev, FTL_LAYOUT_REGION_TYPE_BAND_MD); 337 338 p2l_map->band_dma_md = ftl_mempool_get(dev->band_md_pool); 339 340 if (!p2l_map->band_dma_md) { 341 return -1; 342 } 343 344 memset(p2l_map->band_dma_md, 0, region->entry_size * FTL_BLOCK_SIZE); 345 return 0; 346 } 347 348 int 349 ftl_band_alloc_p2l_map(struct ftl_band *band) 350 { 351 struct spdk_ftl_dev *dev = band->dev; 352 struct ftl_p2l_map *p2l_map = &band->p2l_map; 353 354 assert(p2l_map->ref_cnt == 0); 355 assert(p2l_map->band_map == NULL); 356 357 assert(band->md->df_p2l_map == FTL_DF_OBJ_ID_INVALID); 358 p2l_map->band_map = ftl_mempool_get(dev->p2l_pool); 359 if (!p2l_map->band_map) { 360 return -1; 361 } 362 363 if (ftl_band_alloc_md_entry(band)) { 364 ftl_band_free_p2l_map(band); 365 return -1; 366 } 367 368 band->md->df_p2l_map = ftl_mempool_get_df_obj_id(dev->p2l_pool, p2l_map->band_map); 369 370 /* Set the P2L to FTL_LBA_INVALID */ 371 memset(p2l_map->band_map, -1, FTL_BLOCK_SIZE * ftl_p2l_map_num_blocks(band->dev)); 372 373 ftl_band_acquire_p2l_map(band); 374 return 0; 375 } 376 377 int 378 ftl_band_open_p2l_map(struct ftl_band *band) 379 { 380 struct spdk_ftl_dev *dev = band->dev; 381 struct ftl_p2l_map *p2l_map = &band->p2l_map; 382 383 assert(p2l_map->ref_cnt == 0); 384 assert(p2l_map->band_map == NULL); 385 386 assert(band->md->df_p2l_map != FTL_DF_OBJ_ID_INVALID); 387 388 if (ftl_band_alloc_md_entry(band)) { 389 p2l_map->band_map = NULL; 390 return -1; 391 } 392 393 p2l_map->band_map = ftl_mempool_claim_df(dev->p2l_pool, band->md->df_p2l_map); 394 395 ftl_band_acquire_p2l_map(band); 396 return 0; 397 } 398 399 void 400 ftl_band_release_p2l_map(struct ftl_band *band) 401 { 402 struct ftl_p2l_map *p2l_map = &band->p2l_map; 403 404 assert(p2l_map->band_map != NULL); 405 assert(p2l_map->ref_cnt > 0); 406 p2l_map->ref_cnt--; 407 408 if (p2l_map->ref_cnt == 0) { 409 if (p2l_map->p2l_ckpt) { 410 ftl_p2l_ckpt_release(band->dev, p2l_map->p2l_ckpt); 411 p2l_map->p2l_ckpt = NULL; 412 } 413 ftl_band_free_p2l_map(band); 414 ftl_band_free_md_entry(band); 415 } 416 } 417 418 ftl_addr 419 ftl_band_p2l_map_addr(struct ftl_band *band) 420 { 421 return band->tail_md_addr; 422 } 423 424 int 425 ftl_band_write_prep(struct ftl_band *band) 426 { 427 struct spdk_ftl_dev *dev = band->dev; 428 429 if (ftl_band_alloc_p2l_map(band)) { 430 return -1; 431 } 432 433 band->p2l_map.p2l_ckpt = ftl_p2l_ckpt_acquire(dev); 434 band->md->p2l_md_region = ftl_p2l_ckpt_region_type(band->p2l_map.p2l_ckpt); 435 ftl_band_iter_init(band); 436 437 band->md->seq = ftl_get_next_seq_id(dev); 438 439 FTL_DEBUGLOG(dev, "Band to write, id %u seq %"PRIu64"\n", band->id, band->md->seq); 440 return 0; 441 } 442 443 size_t 444 ftl_p2l_map_pool_elem_size(struct spdk_ftl_dev *dev) 445 { 446 /* Map pool element holds the whole tail md */ 447 return ftl_tail_md_num_blocks(dev) * FTL_BLOCK_SIZE; 448 } 449 450 double 451 ftl_band_invalidity(struct ftl_band *band) 452 { 453 double valid = band->p2l_map.num_valid; 454 double count = ftl_band_user_blocks(band); 455 456 return 1.0 - (valid / count); 457 } 458 459 static void 460 dump_bands_under_relocation(struct spdk_ftl_dev *dev) 461 { 462 uint64_t i = dev->sb_shm->gc_info.current_band_id; 463 uint64_t end = dev->sb_shm->gc_info.current_band_id + dev->num_logical_bands_in_physical; 464 465 for (; i < end; i++) { 466 struct ftl_band *band = &dev->bands[i]; 467 468 FTL_DEBUGLOG(dev, "Band, id %u, phys_is %u, wr cnt = %u, invalidity = %u%%\n", 469 band->id, band->phys_id, (uint32_t)band->md->wr_cnt, 470 (uint32_t)(ftl_band_invalidity(band) * 100)); 471 } 472 } 473 474 static bool 475 is_band_relocateable(struct ftl_band *band) 476 { 477 /* Can only move data from closed bands */ 478 if (FTL_BAND_STATE_CLOSED != band->md->state) { 479 return false; 480 } 481 482 /* Band is already under relocation, skip it */ 483 if (band->reloc) { 484 return false; 485 } 486 487 return true; 488 } 489 490 static void 491 get_band_phys_info(struct spdk_ftl_dev *dev, uint64_t phys_id, 492 double *invalidity, double *wr_cnt) 493 { 494 struct ftl_band *band; 495 uint64_t band_id = phys_id * dev->num_logical_bands_in_physical; 496 497 *wr_cnt = *invalidity = 0.0L; 498 for (; band_id < ftl_get_num_bands(dev); band_id++) { 499 band = &dev->bands[band_id]; 500 501 if (phys_id != band->phys_id) { 502 break; 503 } 504 505 *wr_cnt += band->md->wr_cnt; 506 507 if (!is_band_relocateable(band)) { 508 continue; 509 } 510 511 *invalidity += ftl_band_invalidity(band); 512 } 513 514 *invalidity /= dev->num_logical_bands_in_physical; 515 *wr_cnt /= dev->num_logical_bands_in_physical; 516 } 517 518 static bool 519 band_cmp(double a_invalidity, double a_wr_cnt, 520 double b_invalidity, double b_wr_cnt, 521 uint64_t a_id, uint64_t b_id) 522 { 523 assert(a_id != FTL_BAND_PHYS_ID_INVALID); 524 assert(b_id != FTL_BAND_PHYS_ID_INVALID); 525 double diff = a_invalidity - b_invalidity; 526 if (diff < 0.0L) { 527 diff *= -1.0L; 528 } 529 530 /* Use the following metrics for picking bands for GC (in order): 531 * - relative invalidity 532 * - if invalidity is similar (within 10% points), then their write counts (how many times band was written to) 533 * - if write count is equal, then pick based on their placement on base device (lower LBAs win) 534 */ 535 if (diff > 0.1L) { 536 return a_invalidity > b_invalidity; 537 } 538 539 if (a_wr_cnt != b_wr_cnt) { 540 return a_wr_cnt < b_wr_cnt; 541 } 542 543 return a_id < b_id; 544 } 545 546 static void 547 band_start_gc(struct spdk_ftl_dev *dev, struct ftl_band *band) 548 { 549 ftl_bug(false == is_band_relocateable(band)); 550 551 TAILQ_REMOVE(&dev->shut_bands, band, queue_entry); 552 band->reloc = true; 553 554 FTL_DEBUGLOG(dev, "Band to GC, id %u\n", band->id); 555 } 556 557 static struct ftl_band * 558 gc_high_priority_band(struct spdk_ftl_dev *dev) 559 { 560 struct ftl_band *band; 561 uint64_t high_prio_id = dev->sb_shm->gc_info.band_id_high_prio; 562 563 if (FTL_BAND_ID_INVALID != high_prio_id) { 564 ftl_bug(high_prio_id >= dev->num_bands); 565 566 band = &dev->bands[high_prio_id]; 567 dev->sb_shm->gc_info.band_id_high_prio = FTL_BAND_ID_INVALID; 568 569 band_start_gc(dev, band); 570 FTL_NOTICELOG(dev, "GC takes high priority band, id %u\n", band->id); 571 return band; 572 } 573 574 return 0; 575 } 576 577 static void 578 ftl_band_reset_gc_iter(struct spdk_ftl_dev *dev) 579 { 580 dev->sb->gc_info.is_valid = 0; 581 dev->sb->gc_info.current_band_id = FTL_BAND_ID_INVALID; 582 dev->sb->gc_info.band_id_high_prio = FTL_BAND_ID_INVALID; 583 dev->sb->gc_info.band_phys_id = FTL_BAND_PHYS_ID_INVALID; 584 585 dev->sb_shm->gc_info = dev->sb->gc_info; 586 } 587 588 struct ftl_band * 589 ftl_band_search_next_to_reloc(struct spdk_ftl_dev *dev) 590 { 591 double invalidity, max_invalidity = 0.0L; 592 double wr_cnt, max_wr_cnt = 0.0L; 593 uint64_t phys_id = FTL_BAND_PHYS_ID_INVALID; 594 struct ftl_band *band; 595 uint64_t i, band_count; 596 uint64_t phys_count; 597 598 band = gc_high_priority_band(dev); 599 if (spdk_unlikely(NULL != band)) { 600 return band; 601 } 602 603 phys_count = dev->num_logical_bands_in_physical; 604 band_count = ftl_get_num_bands(dev); 605 606 for (; dev->sb_shm->gc_info.current_band_id < band_count;) { 607 band = &dev->bands[dev->sb_shm->gc_info.current_band_id]; 608 if (band->phys_id != dev->sb_shm->gc_info.band_phys_id) { 609 break; 610 } 611 612 if (false == is_band_relocateable(band)) { 613 dev->sb_shm->gc_info.current_band_id++; 614 continue; 615 } 616 617 band_start_gc(dev, band); 618 return band; 619 } 620 621 for (i = 0; i < band_count; i += phys_count) { 622 band = &dev->bands[i]; 623 624 /* Calculate entire band physical group invalidity */ 625 get_band_phys_info(dev, band->phys_id, &invalidity, &wr_cnt); 626 627 if (invalidity != 0.0L) { 628 if (phys_id == FTL_BAND_PHYS_ID_INVALID || 629 band_cmp(invalidity, wr_cnt, max_invalidity, max_wr_cnt, 630 band->phys_id, phys_id)) { 631 max_wr_cnt = wr_cnt; 632 phys_id = band->phys_id; 633 634 if (invalidity > max_invalidity) { 635 max_invalidity = invalidity; 636 } 637 } 638 } 639 } 640 641 if (FTL_BAND_PHYS_ID_INVALID != phys_id) { 642 FTL_DEBUGLOG(dev, "Band physical id %"PRIu64" to GC\n", phys_id); 643 dev->sb_shm->gc_info.is_valid = 0; 644 dev->sb_shm->gc_info.current_band_id = phys_id * phys_count; 645 dev->sb_shm->gc_info.band_phys_id = phys_id; 646 dev->sb_shm->gc_info.is_valid = 1; 647 dump_bands_under_relocation(dev); 648 return ftl_band_search_next_to_reloc(dev); 649 } else { 650 ftl_band_reset_gc_iter(dev); 651 } 652 653 return NULL; 654 } 655 656 void 657 ftl_band_init_gc_iter(struct spdk_ftl_dev *dev) 658 { 659 if (dev->conf.mode & SPDK_FTL_MODE_CREATE) { 660 ftl_band_reset_gc_iter(dev); 661 return; 662 } 663 664 if (dev->sb->clean) { 665 dev->sb_shm->gc_info = dev->sb->gc_info; 666 return; 667 } 668 669 if (ftl_fast_startup(dev) || ftl_fast_recovery(dev)) { 670 return; 671 } 672 673 /* We lost GC state due to dirty shutdown, reset GC state to start over */ 674 ftl_band_reset_gc_iter(dev); 675 } 676 677 void 678 ftl_valid_map_load_state(struct spdk_ftl_dev *dev) 679 { 680 uint64_t i; 681 struct ftl_band *band; 682 683 for (i = 0; i < dev->num_bands; i++) { 684 band = &dev->bands[i]; 685 band->p2l_map.num_valid = ftl_bitmap_count_set(band->p2l_map.valid); 686 } 687 } 688 689 void 690 ftl_band_initialize_free_state(struct ftl_band *band) 691 { 692 /* All bands start on the shut list during startup, removing it manually here */ 693 TAILQ_REMOVE(&band->dev->shut_bands, band, queue_entry); 694 _ftl_band_set_free(band); 695 } 696 697 int 698 ftl_bands_load_state(struct spdk_ftl_dev *dev) 699 { 700 uint64_t i; 701 struct ftl_band *band; 702 703 for (i = 0; i < dev->num_bands; i++) { 704 band = &dev->bands[i]; 705 706 if (band->md->version != FTL_BAND_VERSION_CURRENT) { 707 FTL_ERRLOG(dev, "Invalid band version detected, %"PRIu64" (expected %d)\n", 708 band->md->version, FTL_BAND_VERSION_CURRENT); 709 return -1; 710 } 711 712 if (band->md->state == FTL_BAND_STATE_FREE) { 713 ftl_band_initialize_free_state(band); 714 } 715 } 716 717 return 0; 718 } 719