1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * f2fs extent cache support 4 * 5 * Copyright (c) 2015 Motorola Mobility 6 * Copyright (c) 2015 Samsung Electronics 7 * Authors: Jaegeuk Kim <jaegeuk@kernel.org> 8 * Chao Yu <chao2.yu@samsung.com> 9 * 10 * block_age-based extent cache added by: 11 * Copyright (c) 2022 xiaomi Co., Ltd. 12 * http://www.xiaomi.com/ 13 */ 14 15 #include <linux/fs.h> 16 #include <linux/f2fs_fs.h> 17 18 #include "f2fs.h" 19 #include "node.h" 20 #include "segment.h" 21 #include <trace/events/f2fs.h> 22 23 bool sanity_check_extent_cache(struct inode *inode, struct f2fs_cached_block *ientry) 24 { 25 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 26 struct f2fs_extent *i_ext = &F2FS_INODE(ientry)->i_ext; 27 struct extent_info ei; 28 int devi; 29 30 get_read_extent_info(&ei, i_ext); 31 32 if (!ei.len) 33 return true; 34 35 if (!f2fs_is_valid_blkaddr(sbi, ei.blk, DATA_GENERIC_ENHANCE) || 36 !f2fs_is_valid_blkaddr(sbi, ei.blk + ei.len - 1, 37 DATA_GENERIC_ENHANCE)) { 38 f2fs_warn(sbi, "%s: inode (ino=%llx) extent info [%u, %u, %u] is incorrect, run fsck to fix", 39 __func__, inode->i_ino, 40 ei.blk, ei.fofs, ei.len); 41 return false; 42 } 43 44 if (!IS_DEVICE_ALIASING(inode)) 45 return true; 46 47 for (devi = 0; devi < sbi->s_ndevs; devi++) { 48 if (FDEV(devi).start_blk != ei.blk || 49 FDEV(devi).end_blk != ei.blk + ei.len - 1) 50 continue; 51 52 if (devi == 0) { 53 f2fs_warn(sbi, 54 "%s: inode (ino=%llx) is an alias of meta device", 55 __func__, inode->i_ino); 56 return false; 57 } 58 59 if (bdev_is_zoned(FDEV(devi).bdev)) { 60 f2fs_warn(sbi, 61 "%s: device alias inode (ino=%llx)'s extent info " 62 "[%u, %u, %u] maps to zoned block device", 63 __func__, inode->i_ino, ei.blk, ei.fofs, ei.len); 64 return false; 65 } 66 67 if ((GET_SEGOFF_FROM_SEG0(sbi, ei.blk) % BLKS_PER_SEC(sbi)) || 68 (ei.len % BLKS_PER_SEC(sbi))) { 69 f2fs_warn(sbi, "%s: device alias inode (ino=%llx)'s extent info [%u, %u, %u] is not aligned to section size %u", 70 __func__, inode->i_ino, ei.blk, ei.fofs, ei.len, 71 BLKS_PER_SEC(sbi)); 72 return false; 73 } 74 return true; 75 } 76 77 f2fs_warn(sbi, "%s: device alias inode (ino=%llx)'s extent info " 78 "[%u, %u, %u] is inconsistent w/ any devices", 79 __func__, inode->i_ino, ei.blk, ei.fofs, ei.len); 80 return false; 81 } 82 83 static void __set_extent_info(struct extent_info *ei, 84 unsigned int fofs, unsigned int len, 85 block_t blk, bool keep_clen, 86 unsigned long age, unsigned long last_blocks, 87 enum extent_type type) 88 { 89 ei->fofs = fofs; 90 ei->len = len; 91 92 if (type == EX_READ) { 93 ei->blk = blk; 94 if (keep_clen) 95 return; 96 #ifdef CONFIG_F2FS_FS_COMPRESSION 97 ei->c_len = 0; 98 #endif 99 } else if (type == EX_BLOCK_AGE) { 100 ei->age = age; 101 ei->last_blocks = last_blocks; 102 } 103 } 104 105 static bool __init_may_extent_tree(struct inode *inode, enum extent_type type) 106 { 107 if (type == EX_READ) 108 return test_opt(F2FS_I_SB(inode), READ_EXTENT_CACHE) && 109 S_ISREG(inode->i_mode); 110 if (type == EX_BLOCK_AGE) 111 return test_opt(F2FS_I_SB(inode), AGE_EXTENT_CACHE) && 112 (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode)); 113 return false; 114 } 115 116 static bool __may_extent_tree(struct inode *inode, enum extent_type type) 117 { 118 if (IS_DEVICE_ALIASING(inode) && type == EX_READ) 119 return true; 120 121 /* 122 * for recovered files during mount do not create extents 123 * if shrinker is not registered. 124 */ 125 if (list_empty(&F2FS_I_SB(inode)->s_list)) 126 return false; 127 128 if (!__init_may_extent_tree(inode, type)) 129 return false; 130 131 if (type == EX_READ) { 132 if (is_inode_flag_set(inode, FI_NO_EXTENT)) 133 return false; 134 if (is_inode_flag_set(inode, FI_COMPRESSED_FILE) && 135 !f2fs_sb_has_readonly(F2FS_I_SB(inode))) 136 return false; 137 } else if (type == EX_BLOCK_AGE) { 138 if (is_inode_flag_set(inode, FI_COMPRESSED_FILE)) 139 return false; 140 if (file_is_cold(inode)) 141 return false; 142 } 143 return true; 144 } 145 146 static void __try_update_largest_extent(struct extent_tree *et, 147 struct extent_node *en) 148 { 149 if (et->type != EX_READ) 150 return; 151 if (en->ei.len <= et->largest.len) 152 return; 153 154 et->largest = en->ei; 155 et->largest_updated = true; 156 } 157 158 static bool __is_extent_mergeable(struct extent_info *back, 159 struct extent_info *front, enum extent_type type) 160 { 161 if (type == EX_READ) { 162 #ifdef CONFIG_F2FS_FS_COMPRESSION 163 if (back->c_len && back->len != back->c_len) 164 return false; 165 if (front->c_len && front->len != front->c_len) 166 return false; 167 #endif 168 return (back->fofs + back->len == front->fofs && 169 back->blk + back->len == front->blk); 170 } else if (type == EX_BLOCK_AGE) { 171 return (back->fofs + back->len == front->fofs && 172 abs(back->age - front->age) <= SAME_AGE_REGION && 173 abs(back->last_blocks - front->last_blocks) <= 174 SAME_AGE_REGION); 175 } 176 return false; 177 } 178 179 static bool __is_back_mergeable(struct extent_info *cur, 180 struct extent_info *back, enum extent_type type) 181 { 182 return __is_extent_mergeable(back, cur, type); 183 } 184 185 static bool __is_front_mergeable(struct extent_info *cur, 186 struct extent_info *front, enum extent_type type) 187 { 188 return __is_extent_mergeable(cur, front, type); 189 } 190 191 static struct extent_node *__lookup_extent_node(struct rb_root_cached *root, 192 struct extent_node *cached_en, unsigned int fofs) 193 { 194 struct rb_node *node = root->rb_root.rb_node; 195 struct extent_node *en; 196 197 /* check a cached entry */ 198 if (cached_en && cached_en->ei.fofs <= fofs && 199 cached_en->ei.fofs + cached_en->ei.len > fofs) 200 return cached_en; 201 202 /* check rb_tree */ 203 while (node) { 204 en = rb_entry(node, struct extent_node, rb_node); 205 206 if (fofs < en->ei.fofs) 207 node = node->rb_left; 208 else if (fofs >= en->ei.fofs + en->ei.len) 209 node = node->rb_right; 210 else 211 return en; 212 } 213 return NULL; 214 } 215 216 /* 217 * lookup rb entry in position of @fofs in rb-tree, 218 * if hit, return the entry, otherwise, return NULL 219 * @prev_ex: extent before fofs 220 * @next_ex: extent after fofs 221 * @insert_p: insert point for new extent at fofs 222 * in order to simplify the insertion after. 223 * tree must stay unchanged between lookup and insertion. 224 */ 225 static struct extent_node *__lookup_extent_node_ret(struct rb_root_cached *root, 226 struct extent_node *cached_en, 227 unsigned int fofs, 228 struct extent_node **prev_entry, 229 struct extent_node **next_entry, 230 struct rb_node ***insert_p, 231 struct rb_node **insert_parent, 232 bool *leftmost) 233 { 234 struct rb_node **pnode = &root->rb_root.rb_node; 235 struct rb_node *parent = NULL, *tmp_node; 236 struct extent_node *en = cached_en; 237 238 *insert_p = NULL; 239 *insert_parent = NULL; 240 *prev_entry = NULL; 241 *next_entry = NULL; 242 243 if (RB_EMPTY_ROOT(&root->rb_root)) 244 return NULL; 245 246 if (en && en->ei.fofs <= fofs && en->ei.fofs + en->ei.len > fofs) 247 goto lookup_neighbors; 248 249 *leftmost = true; 250 251 while (*pnode) { 252 parent = *pnode; 253 en = rb_entry(*pnode, struct extent_node, rb_node); 254 255 if (fofs < en->ei.fofs) { 256 pnode = &(*pnode)->rb_left; 257 } else if (fofs >= en->ei.fofs + en->ei.len) { 258 pnode = &(*pnode)->rb_right; 259 *leftmost = false; 260 } else { 261 goto lookup_neighbors; 262 } 263 } 264 265 *insert_p = pnode; 266 *insert_parent = parent; 267 268 en = rb_entry(parent, struct extent_node, rb_node); 269 tmp_node = parent; 270 if (parent && fofs > en->ei.fofs) 271 tmp_node = rb_next(parent); 272 *next_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node); 273 274 tmp_node = parent; 275 if (parent && fofs < en->ei.fofs) 276 tmp_node = rb_prev(parent); 277 *prev_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node); 278 return NULL; 279 280 lookup_neighbors: 281 if (fofs == en->ei.fofs) { 282 /* lookup prev node for merging backward later */ 283 tmp_node = rb_prev(&en->rb_node); 284 *prev_entry = rb_entry_safe(tmp_node, 285 struct extent_node, rb_node); 286 } 287 if (fofs == en->ei.fofs + en->ei.len - 1) { 288 /* lookup next node for merging frontward later */ 289 tmp_node = rb_next(&en->rb_node); 290 *next_entry = rb_entry_safe(tmp_node, 291 struct extent_node, rb_node); 292 } 293 return en; 294 } 295 296 static struct kmem_cache *extent_tree_slab; 297 static struct kmem_cache *extent_node_slab; 298 299 static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi, 300 struct extent_tree *et, struct extent_info *ei, 301 struct rb_node *parent, struct rb_node **p, 302 bool leftmost) 303 { 304 struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 305 struct extent_node *en; 306 307 en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi); 308 if (!en) 309 return NULL; 310 311 en->ei = *ei; 312 INIT_LIST_HEAD(&en->list); 313 en->et = et; 314 315 rb_link_node(&en->rb_node, parent, p); 316 rb_insert_color_cached(&en->rb_node, &et->root, leftmost); 317 atomic_inc(&et->node_cnt); 318 atomic_inc(&eti->total_ext_node); 319 return en; 320 } 321 322 static void __detach_extent_node(struct f2fs_sb_info *sbi, 323 struct extent_tree *et, struct extent_node *en) 324 { 325 struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 326 327 rb_erase_cached(&en->rb_node, &et->root); 328 atomic_dec(&et->node_cnt); 329 atomic_dec(&eti->total_ext_node); 330 331 if (et->cached_en == en) 332 et->cached_en = NULL; 333 kmem_cache_free(extent_node_slab, en); 334 } 335 336 /* 337 * Flow to release an extent_node: 338 * 1. list_del_init 339 * 2. __detach_extent_node 340 * 3. kmem_cache_free. 341 */ 342 static void __release_extent_node(struct f2fs_sb_info *sbi, 343 struct extent_tree *et, struct extent_node *en) 344 { 345 struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 346 347 spin_lock(&eti->extent_lock); 348 f2fs_bug_on(sbi, list_empty(&en->list)); 349 list_del_init(&en->list); 350 spin_unlock(&eti->extent_lock); 351 352 __detach_extent_node(sbi, et, en); 353 } 354 355 static struct extent_tree *__grab_extent_tree(struct inode *inode, 356 enum extent_type type) 357 { 358 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 359 struct extent_tree_info *eti = &sbi->extent_tree[type]; 360 struct extent_tree *et; 361 nid_t ino = inode->i_ino; 362 363 mutex_lock(&eti->extent_tree_lock); 364 et = radix_tree_lookup(&eti->extent_tree_root, ino); 365 if (!et) { 366 et = f2fs_kmem_cache_alloc(extent_tree_slab, 367 GFP_NOFS, true, NULL); 368 f2fs_radix_tree_insert(&eti->extent_tree_root, ino, et); 369 memset(et, 0, sizeof(struct extent_tree)); 370 et->ino = ino; 371 et->type = type; 372 et->root = RB_ROOT_CACHED; 373 et->cached_en = NULL; 374 rwlock_init(&et->lock); 375 INIT_LIST_HEAD(&et->list); 376 atomic_set(&et->node_cnt, 0); 377 atomic_inc(&eti->total_ext_tree); 378 } else { 379 atomic_dec(&eti->total_zombie_tree); 380 list_del_init(&et->list); 381 } 382 mutex_unlock(&eti->extent_tree_lock); 383 384 /* never died until evict_inode */ 385 F2FS_I(inode)->extent_tree[type] = et; 386 387 return et; 388 } 389 390 static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, 391 struct extent_tree *et, unsigned int nr_shrink) 392 { 393 struct rb_node *node, *next; 394 struct extent_node *en; 395 unsigned int count; 396 397 node = rb_first_cached(&et->root); 398 399 for (count = 0; node && count < nr_shrink; count++) { 400 next = rb_next(node); 401 en = rb_entry(node, struct extent_node, rb_node); 402 __release_extent_node(sbi, et, en); 403 node = next; 404 } 405 406 return count; 407 } 408 409 static void __drop_largest_extent(struct extent_tree *et, 410 pgoff_t fofs, unsigned int len) 411 { 412 if (fofs < (pgoff_t)et->largest.fofs + et->largest.len && 413 fofs + len > et->largest.fofs) { 414 et->largest.len = 0; 415 et->largest_updated = true; 416 } 417 } 418 419 void f2fs_init_read_extent_tree(struct inode *inode, struct f2fs_cached_block *ientry) 420 { 421 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 422 struct extent_tree_info *eti = &sbi->extent_tree[EX_READ]; 423 struct f2fs_extent *i_ext = &F2FS_INODE(ientry)->i_ext; 424 struct extent_tree *et; 425 struct extent_node *en; 426 struct extent_info ei = {0}; 427 428 if (!__may_extent_tree(inode, EX_READ)) { 429 /* drop largest read extent */ 430 if (i_ext->len) { 431 f2fs_cache_wait_writeback(ientry); 432 i_ext->len = 0; 433 f2fs_mark_cache_dirty(ientry); 434 } 435 set_inode_flag(inode, FI_NO_EXTENT); 436 return; 437 } 438 439 et = __grab_extent_tree(inode, EX_READ); 440 441 get_read_extent_info(&ei, i_ext); 442 443 write_lock(&et->lock); 444 if (atomic_read(&et->node_cnt) || !ei.len) 445 goto skip; 446 447 if (IS_DEVICE_ALIASING(inode)) { 448 et->largest = ei; 449 goto skip; 450 } 451 452 en = __attach_extent_node(sbi, et, &ei, NULL, 453 &et->root.rb_root.rb_node, true); 454 if (en) { 455 et->largest = en->ei; 456 et->cached_en = en; 457 458 spin_lock(&eti->extent_lock); 459 list_add_tail(&en->list, &eti->extent_list); 460 spin_unlock(&eti->extent_lock); 461 } 462 skip: 463 /* Let's drop, if checkpoint got corrupted. */ 464 if (f2fs_cp_error(sbi)) { 465 et->largest.len = 0; 466 et->largest_updated = true; 467 } 468 write_unlock(&et->lock); 469 } 470 471 void f2fs_init_age_extent_tree(struct inode *inode) 472 { 473 if (!__init_may_extent_tree(inode, EX_BLOCK_AGE)) 474 return; 475 __grab_extent_tree(inode, EX_BLOCK_AGE); 476 } 477 478 void f2fs_init_extent_tree(struct inode *inode) 479 { 480 /* initialize read cache */ 481 if (__init_may_extent_tree(inode, EX_READ)) 482 __grab_extent_tree(inode, EX_READ); 483 484 /* initialize block age cache */ 485 if (__init_may_extent_tree(inode, EX_BLOCK_AGE)) 486 __grab_extent_tree(inode, EX_BLOCK_AGE); 487 } 488 489 static bool __lookup_extent_tree(struct inode *inode, pgoff_t pgofs, 490 struct extent_info *ei, enum extent_type type) 491 { 492 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 493 struct extent_tree_info *eti = &sbi->extent_tree[type]; 494 struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 495 struct extent_node *en; 496 bool ret = false; 497 498 if (!et) 499 return false; 500 501 trace_f2fs_lookup_extent_tree_start(inode, pgofs, type); 502 503 read_lock(&et->lock); 504 505 if (type == EX_READ && 506 et->largest.fofs <= pgofs && 507 (pgoff_t)et->largest.fofs + et->largest.len > pgofs) { 508 *ei = et->largest; 509 ret = true; 510 stat_inc_largest_node_hit(sbi); 511 goto out; 512 } 513 514 if (IS_DEVICE_ALIASING(inode)) { 515 ret = false; 516 goto out; 517 } 518 519 en = __lookup_extent_node(&et->root, et->cached_en, pgofs); 520 if (!en) 521 goto out; 522 523 if (en == et->cached_en) 524 stat_inc_cached_node_hit(sbi, type); 525 else 526 stat_inc_rbtree_node_hit(sbi, type); 527 528 *ei = en->ei; 529 spin_lock(&eti->extent_lock); 530 if (!list_empty(&en->list)) { 531 list_move_tail(&en->list, &eti->extent_list); 532 et->cached_en = en; 533 } 534 spin_unlock(&eti->extent_lock); 535 ret = true; 536 out: 537 stat_inc_total_hit(sbi, type); 538 read_unlock(&et->lock); 539 540 if (type == EX_READ) 541 trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei); 542 else if (type == EX_BLOCK_AGE) 543 trace_f2fs_lookup_age_extent_tree_end(inode, pgofs, ei); 544 return ret; 545 } 546 547 static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi, 548 struct extent_tree *et, struct extent_info *ei, 549 struct extent_node *prev_ex, 550 struct extent_node *next_ex) 551 { 552 struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 553 struct extent_node *en = NULL; 554 555 if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei, et->type)) { 556 prev_ex->ei.len += ei->len; 557 ei = &prev_ex->ei; 558 en = prev_ex; 559 } 560 561 if (next_ex && __is_front_mergeable(ei, &next_ex->ei, et->type)) { 562 next_ex->ei.fofs = ei->fofs; 563 next_ex->ei.len += ei->len; 564 if (et->type == EX_READ) 565 next_ex->ei.blk = ei->blk; 566 if (en) 567 __release_extent_node(sbi, et, prev_ex); 568 569 en = next_ex; 570 } 571 572 if (!en) 573 return NULL; 574 575 __try_update_largest_extent(et, en); 576 577 spin_lock(&eti->extent_lock); 578 if (!list_empty(&en->list)) { 579 list_move_tail(&en->list, &eti->extent_list); 580 et->cached_en = en; 581 } 582 spin_unlock(&eti->extent_lock); 583 return en; 584 } 585 586 static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, 587 struct extent_tree *et, struct extent_info *ei, 588 struct rb_node **insert_p, 589 struct rb_node *insert_parent, 590 bool leftmost) 591 { 592 struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 593 struct rb_node **p = &et->root.rb_root.rb_node; 594 struct rb_node *parent = NULL; 595 struct extent_node *en = NULL; 596 597 if (insert_p && insert_parent) { 598 parent = insert_parent; 599 p = insert_p; 600 goto do_insert; 601 } 602 603 leftmost = true; 604 605 /* look up extent_node in the rb tree */ 606 while (*p) { 607 parent = *p; 608 en = rb_entry(parent, struct extent_node, rb_node); 609 610 if (ei->fofs < en->ei.fofs) { 611 p = &(*p)->rb_left; 612 } else if (ei->fofs >= en->ei.fofs + en->ei.len) { 613 p = &(*p)->rb_right; 614 leftmost = false; 615 } else { 616 f2fs_err_ratelimited(sbi, "%s: corrupted extent, type: %d, " 617 "extent node in rb tree [%u, %u, %u], age [%llu, %llu], " 618 "extent node to insert [%u, %u, %u], age [%llu, %llu]", 619 __func__, et->type, en->ei.fofs, en->ei.blk, en->ei.len, en->ei.age, 620 en->ei.last_blocks, ei->fofs, ei->blk, ei->len, ei->age, ei->last_blocks); 621 f2fs_bug_on(sbi, 1); 622 return NULL; 623 } 624 } 625 626 do_insert: 627 en = __attach_extent_node(sbi, et, ei, parent, p, leftmost); 628 if (!en) 629 return NULL; 630 631 __try_update_largest_extent(et, en); 632 633 /* update in global extent list */ 634 spin_lock(&eti->extent_lock); 635 list_add_tail(&en->list, &eti->extent_list); 636 et->cached_en = en; 637 spin_unlock(&eti->extent_lock); 638 return en; 639 } 640 641 static unsigned int __destroy_extent_node(struct inode *inode, 642 enum extent_type type) 643 { 644 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 645 struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 646 unsigned int nr_shrink = type == EX_READ ? 647 READ_EXTENT_CACHE_SHRINK_NUMBER : 648 AGE_EXTENT_CACHE_SHRINK_NUMBER; 649 unsigned int node_cnt = 0; 650 651 if (!et || !atomic_read(&et->node_cnt)) 652 return 0; 653 654 while (atomic_read(&et->node_cnt)) { 655 write_lock(&et->lock); 656 node_cnt += __free_extent_tree(sbi, et, nr_shrink); 657 write_unlock(&et->lock); 658 } 659 660 return node_cnt; 661 } 662 663 static void __update_extent_tree_range(struct inode *inode, 664 struct extent_info *tei, enum extent_type type) 665 { 666 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 667 struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 668 struct extent_node *en = NULL, *en1 = NULL; 669 struct extent_node *prev_en = NULL, *next_en = NULL; 670 struct extent_info ei, dei, prev; 671 struct rb_node **insert_p = NULL, *insert_parent = NULL; 672 unsigned int fofs = tei->fofs, len = tei->len; 673 unsigned int end = fofs + len; 674 bool updated = false; 675 bool leftmost = false; 676 677 if (!et) 678 return; 679 680 if (unlikely(len == 0)) { 681 f2fs_err_ratelimited(sbi, "%s: extent len is zero, type: %d, " 682 "extent [%u, %u, %u], age [%llu, %llu]", 683 __func__, type, tei->fofs, tei->blk, tei->len, 684 tei->age, tei->last_blocks); 685 f2fs_bug_on(sbi, 1); 686 return; 687 } 688 689 if (type == EX_READ) 690 trace_f2fs_update_read_extent_tree_range(inode, fofs, len, 691 tei->blk, 0); 692 else if (type == EX_BLOCK_AGE) 693 trace_f2fs_update_age_extent_tree_range(inode, fofs, len, 694 tei->age, tei->last_blocks); 695 696 write_lock(&et->lock); 697 698 if (type == EX_READ) { 699 if (is_inode_flag_set(inode, FI_NO_EXTENT)) { 700 write_unlock(&et->lock); 701 return; 702 } 703 704 prev = et->largest; 705 dei.len = 0; 706 707 /* 708 * drop largest extent before lookup, in case it's already 709 * been shrunk from extent tree 710 */ 711 __drop_largest_extent(et, fofs, len); 712 } 713 714 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ 715 en = __lookup_extent_node_ret(&et->root, 716 et->cached_en, fofs, 717 &prev_en, &next_en, 718 &insert_p, &insert_parent, 719 &leftmost); 720 if (!en) 721 en = next_en; 722 723 /* 2. invalidate all extent nodes in range [fofs, fofs + len - 1] */ 724 while (en && en->ei.fofs < end) { 725 unsigned int org_end; 726 int parts = 0; /* # of parts current extent split into */ 727 728 next_en = en1 = NULL; 729 730 dei = en->ei; 731 org_end = dei.fofs + dei.len; 732 f2fs_bug_on(sbi, fofs >= org_end); 733 734 if (fofs > dei.fofs && (type != EX_READ || 735 fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) { 736 en->ei.len = fofs - en->ei.fofs; 737 prev_en = en; 738 parts = 1; 739 } 740 741 if (end < org_end && (type != EX_READ || 742 (org_end - end >= F2FS_MIN_EXTENT_LEN && 743 atomic_read(&et->node_cnt) < 744 sbi->max_read_extent_count))) { 745 if (parts) { 746 __set_extent_info(&ei, 747 end, org_end - end, 748 end - dei.fofs + dei.blk, false, 749 dei.age, dei.last_blocks, 750 type); 751 en1 = __insert_extent_tree(sbi, et, &ei, 752 NULL, NULL, true); 753 next_en = en1; 754 } else { 755 __set_extent_info(&en->ei, 756 end, en->ei.len - (end - dei.fofs), 757 en->ei.blk + (end - dei.fofs), true, 758 dei.age, dei.last_blocks, 759 type); 760 next_en = en; 761 } 762 parts++; 763 } 764 765 if (!next_en) { 766 struct rb_node *node = rb_next(&en->rb_node); 767 768 next_en = rb_entry_safe(node, struct extent_node, 769 rb_node); 770 } 771 772 if (parts) 773 __try_update_largest_extent(et, en); 774 else 775 __release_extent_node(sbi, et, en); 776 777 /* 778 * if original extent is split into zero or two parts, extent 779 * tree has been altered by deletion or insertion, therefore 780 * invalidate pointers regard to tree. 781 */ 782 if (parts != 1) { 783 insert_p = NULL; 784 insert_parent = NULL; 785 } 786 en = next_en; 787 } 788 789 if (type == EX_BLOCK_AGE) 790 goto update_age_extent_cache; 791 792 /* 3. update extent in read extent cache */ 793 BUG_ON(type != EX_READ); 794 795 if (tei->blk) { 796 __set_extent_info(&ei, fofs, len, tei->blk, false, 797 0, 0, EX_READ); 798 if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 799 __insert_extent_tree(sbi, et, &ei, 800 insert_p, insert_parent, leftmost); 801 802 /* give up extent_cache, if split and small updates happen */ 803 if (dei.len >= 1 && 804 prev.len < F2FS_MIN_EXTENT_LEN && 805 et->largest.len < F2FS_MIN_EXTENT_LEN) { 806 et->largest.len = 0; 807 et->largest_updated = true; 808 set_inode_flag(inode, FI_NO_EXTENT); 809 } 810 } 811 812 if (et->largest_updated) { 813 et->largest_updated = false; 814 updated = true; 815 } 816 goto out_read_extent_cache; 817 update_age_extent_cache: 818 if (tei->last_blocks == F2FS_EXTENT_AGE_INVALID) 819 goto out_read_extent_cache; 820 821 __set_extent_info(&ei, fofs, len, 0, false, 822 tei->age, tei->last_blocks, EX_BLOCK_AGE); 823 if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 824 __insert_extent_tree(sbi, et, &ei, 825 insert_p, insert_parent, leftmost); 826 out_read_extent_cache: 827 write_unlock(&et->lock); 828 829 if (is_inode_flag_set(inode, FI_NO_EXTENT)) 830 __destroy_extent_node(inode, EX_READ); 831 832 if (updated) 833 f2fs_mark_inode_dirty_sync(inode, true); 834 } 835 836 #ifdef CONFIG_F2FS_FS_COMPRESSION 837 void f2fs_update_read_extent_tree_range_compressed(struct inode *inode, 838 pgoff_t fofs, block_t blkaddr, unsigned int llen, 839 unsigned int c_len) 840 { 841 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 842 struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ]; 843 struct extent_node *en = NULL; 844 struct extent_node *prev_en = NULL, *next_en = NULL; 845 struct extent_info ei; 846 struct rb_node **insert_p = NULL, *insert_parent = NULL; 847 bool leftmost = false; 848 849 trace_f2fs_update_read_extent_tree_range(inode, fofs, llen, 850 blkaddr, c_len); 851 852 /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */ 853 if (is_inode_flag_set(inode, FI_NO_EXTENT)) 854 return; 855 856 write_lock(&et->lock); 857 858 en = __lookup_extent_node_ret(&et->root, 859 et->cached_en, fofs, 860 &prev_en, &next_en, 861 &insert_p, &insert_parent, 862 &leftmost); 863 if (en) 864 goto unlock_out; 865 866 __set_extent_info(&ei, fofs, llen, blkaddr, true, 0, 0, EX_READ); 867 ei.c_len = c_len; 868 869 if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 870 __insert_extent_tree(sbi, et, &ei, 871 insert_p, insert_parent, leftmost); 872 unlock_out: 873 write_unlock(&et->lock); 874 } 875 #endif 876 877 static unsigned long long __calculate_block_age(struct f2fs_sb_info *sbi, 878 unsigned long long new, 879 unsigned long long old) 880 { 881 unsigned int rem_old, rem_new; 882 unsigned long long res; 883 unsigned int weight = sbi->last_age_weight; 884 885 res = div_u64_rem(new, 100, &rem_new) * (100 - weight) 886 + div_u64_rem(old, 100, &rem_old) * weight; 887 888 if (rem_new) 889 res += rem_new * (100 - weight) / 100; 890 if (rem_old) 891 res += rem_old * weight / 100; 892 893 return res; 894 } 895 896 /* This returns a new age and allocated blocks in ei */ 897 static int __get_new_block_age(struct inode *inode, struct extent_info *ei, 898 block_t blkaddr) 899 { 900 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 901 loff_t f_size = i_size_read(inode); 902 unsigned long long cur_blocks = 903 atomic64_read(&sbi->allocated_data_blocks); 904 struct extent_info tei = *ei; /* only fofs and len are valid */ 905 906 /* 907 * When I/O is not aligned to the filesystem block size, update will 908 * happen to the last file block even in seq write. Do not record the age 909 * of the new last file block here. 910 */ 911 if ((f_size >> sbi->log_blocksize) == ei->fofs && 912 f_size & F2FS_BLKSIZE_MASK(sbi) && 913 blkaddr == NEW_ADDR) 914 return -EINVAL; 915 916 if (__lookup_extent_tree(inode, ei->fofs, &tei, EX_BLOCK_AGE)) { 917 unsigned long long cur_age; 918 919 if (cur_blocks >= tei.last_blocks) 920 cur_age = cur_blocks - tei.last_blocks; 921 else 922 /* allocated_data_blocks overflow */ 923 cur_age = (ULLONG_MAX - 1) - tei.last_blocks + cur_blocks; 924 925 if (tei.age) 926 ei->age = __calculate_block_age(sbi, cur_age, tei.age); 927 else 928 ei->age = cur_age; 929 ei->last_blocks = cur_blocks; 930 WARN_ON(ei->age > cur_blocks); 931 return 0; 932 } 933 934 f2fs_bug_on(sbi, blkaddr == NULL_ADDR); 935 936 /* the data block was allocated for the first time */ 937 if (blkaddr == NEW_ADDR) 938 goto out; 939 940 if (__is_valid_data_blkaddr(blkaddr) && 941 !f2fs_is_valid_blkaddr(sbi, blkaddr, DATA_GENERIC_ENHANCE)) 942 return -EINVAL; 943 out: 944 /* 945 * init block age with zero, this can happen when the block age extent 946 * was reclaimed due to memory constraint or system reboot 947 */ 948 ei->age = 0; 949 ei->last_blocks = cur_blocks; 950 return 0; 951 } 952 953 static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type) 954 { 955 struct extent_info ei = {}; 956 957 if (!__may_extent_tree(dn->inode, type)) 958 return; 959 960 ei.fofs = f2fs_start_bidx_of_node(ofs_of_node(F2FS_I_SB(dn->inode), 961 dn->node_entry), dn->inode) + dn->ofs_in_node; 962 ei.len = 1; 963 964 if (type == EX_READ) { 965 if (dn->data_blkaddr == NEW_ADDR) 966 ei.blk = NULL_ADDR; 967 else 968 ei.blk = dn->data_blkaddr; 969 } else if (type == EX_BLOCK_AGE) { 970 if (__get_new_block_age(dn->inode, &ei, dn->data_blkaddr)) 971 return; 972 } 973 __update_extent_tree_range(dn->inode, &ei, type); 974 } 975 976 static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink, 977 enum extent_type type) 978 { 979 struct extent_tree_info *eti = &sbi->extent_tree[type]; 980 struct extent_tree *et, *next; 981 struct extent_node *en; 982 unsigned int node_cnt = 0, tree_cnt = 0; 983 int remained; 984 985 if (!atomic_read(&eti->total_zombie_tree)) 986 goto free_node; 987 988 if (!mutex_trylock(&eti->extent_tree_lock)) 989 goto out; 990 991 /* 1. remove unreferenced extent tree */ 992 list_for_each_entry_safe(et, next, &eti->zombie_list, list) { 993 if (atomic_read(&et->node_cnt)) { 994 write_lock(&et->lock); 995 node_cnt += __free_extent_tree(sbi, et, 996 nr_shrink - node_cnt - tree_cnt); 997 write_unlock(&et->lock); 998 } 999 1000 if (atomic_read(&et->node_cnt)) 1001 goto unlock_out; 1002 1003 list_del_init(&et->list); 1004 radix_tree_delete(&eti->extent_tree_root, et->ino); 1005 kmem_cache_free(extent_tree_slab, et); 1006 atomic_dec(&eti->total_ext_tree); 1007 atomic_dec(&eti->total_zombie_tree); 1008 tree_cnt++; 1009 1010 if (node_cnt + tree_cnt >= nr_shrink) 1011 goto unlock_out; 1012 cond_resched(); 1013 } 1014 mutex_unlock(&eti->extent_tree_lock); 1015 1016 free_node: 1017 /* 2. remove LRU extent entries */ 1018 if (!mutex_trylock(&eti->extent_tree_lock)) 1019 goto out; 1020 1021 remained = nr_shrink - (node_cnt + tree_cnt); 1022 1023 spin_lock(&eti->extent_lock); 1024 for (; remained > 0; remained--) { 1025 if (list_empty(&eti->extent_list)) 1026 break; 1027 en = list_first_entry(&eti->extent_list, 1028 struct extent_node, list); 1029 et = en->et; 1030 if (!write_trylock(&et->lock)) { 1031 /* refresh this extent node's position in extent list */ 1032 list_move_tail(&en->list, &eti->extent_list); 1033 continue; 1034 } 1035 1036 list_del_init(&en->list); 1037 spin_unlock(&eti->extent_lock); 1038 1039 __detach_extent_node(sbi, et, en); 1040 1041 write_unlock(&et->lock); 1042 node_cnt++; 1043 spin_lock(&eti->extent_lock); 1044 } 1045 spin_unlock(&eti->extent_lock); 1046 1047 unlock_out: 1048 mutex_unlock(&eti->extent_tree_lock); 1049 out: 1050 trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type); 1051 1052 return node_cnt + tree_cnt; 1053 } 1054 1055 /* read extent cache operations */ 1056 bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs, 1057 struct extent_info *ei) 1058 { 1059 if (!__may_extent_tree(inode, EX_READ)) 1060 return false; 1061 1062 return __lookup_extent_tree(inode, pgofs, ei, EX_READ); 1063 } 1064 1065 bool f2fs_lookup_read_extent_cache_block(struct inode *inode, pgoff_t index, 1066 block_t *blkaddr) 1067 { 1068 struct extent_info ei = {}; 1069 1070 if (!f2fs_lookup_read_extent_cache(inode, index, &ei)) 1071 return false; 1072 *blkaddr = ei.blk + index - ei.fofs; 1073 return true; 1074 } 1075 1076 void f2fs_update_read_extent_cache(struct dnode_of_data *dn) 1077 { 1078 return __update_extent_cache(dn, EX_READ); 1079 } 1080 1081 void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn, 1082 pgoff_t fofs, block_t blkaddr, unsigned int len) 1083 { 1084 struct extent_info ei = { 1085 .fofs = fofs, 1086 .len = len, 1087 .blk = blkaddr, 1088 }; 1089 1090 if (!__may_extent_tree(dn->inode, EX_READ)) 1091 return; 1092 1093 __update_extent_tree_range(dn->inode, &ei, EX_READ); 1094 } 1095 1096 unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 1097 { 1098 if (!test_opt(sbi, READ_EXTENT_CACHE)) 1099 return 0; 1100 1101 return __shrink_extent_tree(sbi, nr_shrink, EX_READ); 1102 } 1103 1104 /* block age extent cache operations */ 1105 bool f2fs_lookup_age_extent_cache(struct inode *inode, pgoff_t pgofs, 1106 struct extent_info *ei) 1107 { 1108 if (!__may_extent_tree(inode, EX_BLOCK_AGE)) 1109 return false; 1110 1111 return __lookup_extent_tree(inode, pgofs, ei, EX_BLOCK_AGE); 1112 } 1113 1114 void f2fs_update_age_extent_cache(struct dnode_of_data *dn) 1115 { 1116 return __update_extent_cache(dn, EX_BLOCK_AGE); 1117 } 1118 1119 void f2fs_update_age_extent_cache_range(struct dnode_of_data *dn, 1120 pgoff_t fofs, unsigned int len) 1121 { 1122 struct extent_info ei = { 1123 .fofs = fofs, 1124 .len = len, 1125 .last_blocks = F2FS_EXTENT_AGE_INVALID, 1126 }; 1127 1128 if (!__may_extent_tree(dn->inode, EX_BLOCK_AGE)) 1129 return; 1130 1131 __update_extent_tree_range(dn->inode, &ei, EX_BLOCK_AGE); 1132 } 1133 1134 unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 1135 { 1136 if (!test_opt(sbi, AGE_EXTENT_CACHE)) 1137 return 0; 1138 1139 return __shrink_extent_tree(sbi, nr_shrink, EX_BLOCK_AGE); 1140 } 1141 1142 void f2fs_destroy_extent_node(struct inode *inode) 1143 { 1144 __destroy_extent_node(inode, EX_READ); 1145 __destroy_extent_node(inode, EX_BLOCK_AGE); 1146 } 1147 1148 static void __drop_extent_tree(struct inode *inode, enum extent_type type) 1149 { 1150 struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1151 bool updated = false; 1152 1153 if (!__may_extent_tree(inode, type)) 1154 return; 1155 1156 write_lock(&et->lock); 1157 if (type == EX_READ) { 1158 set_inode_flag(inode, FI_NO_EXTENT); 1159 if (et->largest.len) { 1160 et->largest.len = 0; 1161 updated = true; 1162 } 1163 } 1164 write_unlock(&et->lock); 1165 1166 __destroy_extent_node(inode, type); 1167 1168 if (updated) 1169 f2fs_mark_inode_dirty_sync(inode, true); 1170 } 1171 1172 void f2fs_drop_extent_tree(struct inode *inode) 1173 { 1174 __drop_extent_tree(inode, EX_READ); 1175 __drop_extent_tree(inode, EX_BLOCK_AGE); 1176 } 1177 1178 static void __destroy_extent_tree(struct inode *inode, enum extent_type type) 1179 { 1180 struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1181 struct extent_tree_info *eti = &sbi->extent_tree[type]; 1182 struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1183 unsigned int node_cnt = 0; 1184 1185 if (!et) 1186 return; 1187 1188 if (inode->i_nlink && !is_bad_inode(inode) && 1189 atomic_read(&et->node_cnt)) { 1190 mutex_lock(&eti->extent_tree_lock); 1191 list_add_tail(&et->list, &eti->zombie_list); 1192 atomic_inc(&eti->total_zombie_tree); 1193 mutex_unlock(&eti->extent_tree_lock); 1194 return; 1195 } 1196 1197 /* free all extent info belong to this extent tree */ 1198 node_cnt = __destroy_extent_node(inode, type); 1199 1200 /* delete extent tree entry in radix tree */ 1201 mutex_lock(&eti->extent_tree_lock); 1202 f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 1203 radix_tree_delete(&eti->extent_tree_root, inode->i_ino); 1204 kmem_cache_free(extent_tree_slab, et); 1205 atomic_dec(&eti->total_ext_tree); 1206 mutex_unlock(&eti->extent_tree_lock); 1207 1208 F2FS_I(inode)->extent_tree[type] = NULL; 1209 1210 trace_f2fs_destroy_extent_tree(inode, node_cnt, type); 1211 } 1212 1213 void f2fs_destroy_extent_tree(struct inode *inode) 1214 { 1215 __destroy_extent_tree(inode, EX_READ); 1216 __destroy_extent_tree(inode, EX_BLOCK_AGE); 1217 } 1218 1219 static void __init_extent_tree_info(struct extent_tree_info *eti) 1220 { 1221 INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO); 1222 mutex_init(&eti->extent_tree_lock); 1223 INIT_LIST_HEAD(&eti->extent_list); 1224 spin_lock_init(&eti->extent_lock); 1225 atomic_set(&eti->total_ext_tree, 0); 1226 INIT_LIST_HEAD(&eti->zombie_list); 1227 atomic_set(&eti->total_zombie_tree, 0); 1228 atomic_set(&eti->total_ext_node, 0); 1229 } 1230 1231 void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi) 1232 { 1233 __init_extent_tree_info(&sbi->extent_tree[EX_READ]); 1234 __init_extent_tree_info(&sbi->extent_tree[EX_BLOCK_AGE]); 1235 1236 /* initialize for block age extents */ 1237 atomic64_set(&sbi->allocated_data_blocks, 0); 1238 sbi->hot_data_age_threshold = DEF_HOT_DATA_AGE_THRESHOLD; 1239 sbi->warm_data_age_threshold = DEF_WARM_DATA_AGE_THRESHOLD; 1240 sbi->last_age_weight = LAST_AGE_WEIGHT; 1241 sbi->max_read_extent_count = DEF_MAX_READ_EXTENT_COUNT; 1242 } 1243 1244 int __init f2fs_create_extent_cache(void) 1245 { 1246 extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 1247 sizeof(struct extent_tree)); 1248 if (!extent_tree_slab) 1249 return -ENOMEM; 1250 extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 1251 sizeof(struct extent_node)); 1252 if (!extent_node_slab) { 1253 kmem_cache_destroy(extent_tree_slab); 1254 return -ENOMEM; 1255 } 1256 return 0; 1257 } 1258 1259 void f2fs_destroy_extent_cache(void) 1260 { 1261 kmem_cache_destroy(extent_node_slab); 1262 kmem_cache_destroy(extent_tree_slab); 1263 } 1264