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