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