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