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