fs/f2fs/extent_cache.c

   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
  11 #include <linux/fs.h>
  12 #include <linux/f2fs_fs.h>
  13
  14 #include "f2fs.h"
  15 #include "node.h"
  16 #include <trace/events/f2fs.h>
  17
  18 bool sanity_check_extent_cache(struct inode *inode)
  19 {
  20         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
  21         struct f2fs_inode_info *fi = F2FS_I(inode);
  22         struct extent_info *ei;
  23
  24         if (!fi->extent_tree[EX_READ])
  25                 return true;
  26
  27         ei = &fi->extent_tree[EX_READ]->largest;
  28
  29         if (ei->len &&
  30                 (!f2fs_is_valid_blkaddr(sbi, ei->blk,
  31                                         DATA_GENERIC_ENHANCE) ||
  32                 !f2fs_is_valid_blkaddr(sbi, ei->blk + ei->len - 1,
  33                                         DATA_GENERIC_ENHANCE))) {
  34                 set_sbi_flag(sbi, SBI_NEED_FSCK);
  35                 f2fs_warn(sbi, "%s: inode (ino=%lx) extent info [%u, %u, %u] is incorrect, run fsck to fix",
  36                           __func__, inode->i_ino,
  37                           ei->blk, ei->fofs, ei->len);
  38                 return false;
  39         }
  40         return true;
  41 }
  42
  43 static void __set_extent_info(struct extent_info *ei,
  44                                 unsigned int fofs, unsigned int len,
  45                                 block_t blk, bool keep_clen,
  46                                 enum extent_type type)
  47 {
  48         ei->fofs = fofs;
  49         ei->len = len;
  50
  51         if (type == EX_READ) {
  52                 ei->blk = blk;
  53                 if (keep_clen)
  54                         return;
  55 #ifdef CONFIG_F2FS_FS_COMPRESSION
  56                 ei->c_len = 0;
  57 #endif
  58         }
  59 }
  60
  61 static bool __may_read_extent_tree(struct inode *inode)
  62 {
  63         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
  64
  65         if (!test_opt(sbi, READ_EXTENT_CACHE))
  66                 return false;
  67         if (is_inode_flag_set(inode, FI_NO_EXTENT))
  68                 return false;
  69         if (is_inode_flag_set(inode, FI_COMPRESSED_FILE) &&
  70                          !f2fs_sb_has_readonly(sbi))
  71                 return false;
  72         return S_ISREG(inode->i_mode);
  73 }
  74
  75 static bool __init_may_extent_tree(struct inode *inode, enum extent_type type)
  76 {
  77         if (type == EX_READ)
  78                 return __may_read_extent_tree(inode);
  79         return false;
  80 }
  81
  82 static bool __may_extent_tree(struct inode *inode, enum extent_type type)
  83 {
  84         /*
  85          * for recovered files during mount do not create extents
  86          * if shrinker is not registered.
  87          */
  88         if (list_empty(&F2FS_I_SB(inode)->s_list))
  89                 return false;
  90
  91         return __init_may_extent_tree(inode, type);
  92 }
  93
  94 static void __try_update_largest_extent(struct extent_tree *et,
  95                                                 struct extent_node *en)
  96 {
  97         if (et->type != EX_READ)
  98                 return;
  99         if (en->ei.len <= et->largest.len)
 100                 return;
 101
 102         et->largest = en->ei;
 103         et->largest_updated = true;
 104 }
 105
 106 static bool __is_extent_mergeable(struct extent_info *back,
 107                 struct extent_info *front, enum extent_type type)
 108 {
 109         if (type == EX_READ) {
 110 #ifdef CONFIG_F2FS_FS_COMPRESSION
 111                 if (back->c_len && back->len != back->c_len)
 112                         return false;
 113                 if (front->c_len && front->len != front->c_len)
 114                         return false;
 115 #endif
 116                 return (back->fofs + back->len == front->fofs &&
 117                                 back->blk + back->len == front->blk);
 118         }
 119         return false;
 120 }
 121
 122 static bool __is_back_mergeable(struct extent_info *cur,
 123                 struct extent_info *back, enum extent_type type)
 124 {
 125         return __is_extent_mergeable(back, cur, type);
 126 }
 127
 128 static bool __is_front_mergeable(struct extent_info *cur,
 129                 struct extent_info *front, enum extent_type type)
 130 {
 131         return __is_extent_mergeable(cur, front, type);
 132 }
 133
 134 static struct rb_entry *__lookup_rb_tree_fast(struct rb_entry *cached_re,
 135                                                         unsigned int ofs)
 136 {
 137         if (cached_re) {
 138                 if (cached_re->ofs <= ofs &&
 139                                 cached_re->ofs + cached_re->len > ofs) {
 140                         return cached_re;
 141                 }
 142         }
 143         return NULL;
 144 }
 145
 146 static struct rb_entry *__lookup_rb_tree_slow(struct rb_root_cached *root,
 147                                                         unsigned int ofs)
 148 {
 149         struct rb_node *node = root->rb_root.rb_node;
 150         struct rb_entry *re;
 151
 152         while (node) {
 153                 re = rb_entry(node, struct rb_entry, rb_node);
 154
 155                 if (ofs < re->ofs)
 156                         node = node->rb_left;
 157                 else if (ofs >= re->ofs + re->len)
 158                         node = node->rb_right;
 159                 else
 160                         return re;
 161         }
 162         return NULL;
 163 }
 164
 165 struct rb_entry *f2fs_lookup_rb_tree(struct rb_root_cached *root,
 166                                 struct rb_entry *cached_re, unsigned int ofs)
 167 {
 168         struct rb_entry *re;
 169
 170         re = __lookup_rb_tree_fast(cached_re, ofs);
 171         if (!re)
 172                 return __lookup_rb_tree_slow(root, ofs);
 173
 174         return re;
 175 }
 176
 177 struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi,
 178                                 struct rb_root_cached *root,
 179                                 struct rb_node **parent,
 180                                 unsigned int ofs, bool *leftmost)
 181 {
 182         struct rb_node **p = &root->rb_root.rb_node;
 183         struct rb_entry *re;
 184
 185         while (*p) {
 186                 *parent = *p;
 187                 re = rb_entry(*parent, struct rb_entry, rb_node);
 188
 189                 if (ofs < re->ofs) {
 190                         p = &(*p)->rb_left;
 191                 } else if (ofs >= re->ofs + re->len) {
 192                         p = &(*p)->rb_right;
 193                         *leftmost = false;
 194                 } else {
 195                         f2fs_bug_on(sbi, 1);
 196                 }
 197         }
 198
 199         return p;
 200 }
 201
 202 /*
 203  * lookup rb entry in position of @ofs in rb-tree,
 204  * if hit, return the entry, otherwise, return NULL
 205  * @prev_ex: extent before ofs
 206  * @next_ex: extent after ofs
 207  * @insert_p: insert point for new extent at ofs
 208  * in order to simpfy the insertion after.
 209  * tree must stay unchanged between lookup and insertion.
 210  */
 211 struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root_cached *root,
 212                                 struct rb_entry *cached_re,
 213                                 unsigned int ofs,
 214                                 struct rb_entry **prev_entry,
 215                                 struct rb_entry **next_entry,
 216                                 struct rb_node ***insert_p,
 217                                 struct rb_node **insert_parent,
 218                                 bool force, bool *leftmost)
 219 {
 220         struct rb_node **pnode = &root->rb_root.rb_node;
 221         struct rb_node *parent = NULL, *tmp_node;
 222         struct rb_entry *re = cached_re;
 223
 224         *insert_p = NULL;
 225         *insert_parent = NULL;
 226         *prev_entry = NULL;
 227         *next_entry = NULL;
 228
 229         if (RB_EMPTY_ROOT(&root->rb_root))
 230                 return NULL;
 231
 232         if (re) {
 233                 if (re->ofs <= ofs && re->ofs + re->len > ofs)
 234                         goto lookup_neighbors;
 235         }
 236
 237         if (leftmost)
 238                 *leftmost = true;
 239
 240         while (*pnode) {
 241                 parent = *pnode;
 242                 re = rb_entry(*pnode, struct rb_entry, rb_node);
 243
 244                 if (ofs < re->ofs) {
 245                         pnode = &(*pnode)->rb_left;
 246                 } else if (ofs >= re->ofs + re->len) {
 247                         pnode = &(*pnode)->rb_right;
 248                         if (leftmost)
 249                                 *leftmost = false;
 250                 } else {
 251                         goto lookup_neighbors;
 252                 }
 253         }
 254
 255         *insert_p = pnode;
 256         *insert_parent = parent;
 257
 258         re = rb_entry(parent, struct rb_entry, rb_node);
 259         tmp_node = parent;
 260         if (parent && ofs > re->ofs)
 261                 tmp_node = rb_next(parent);
 262         *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
 263
 264         tmp_node = parent;
 265         if (parent && ofs < re->ofs)
 266                 tmp_node = rb_prev(parent);
 267         *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
 268         return NULL;
 269
 270 lookup_neighbors:
 271         if (ofs == re->ofs || force) {
 272                 /* lookup prev node for merging backward later */
 273                 tmp_node = rb_prev(&re->rb_node);
 274                 *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
 275         }
 276         if (ofs == re->ofs + re->len - 1 || force) {
 277                 /* lookup next node for merging frontward later */
 278                 tmp_node = rb_next(&re->rb_node);
 279                 *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
 280         }
 281         return re;
 282 }
 283
 284 bool f2fs_check_rb_tree_consistence(struct f2fs_sb_info *sbi,
 285                                 struct rb_root_cached *root)
 286 {
 287 #ifdef CONFIG_F2FS_CHECK_FS
 288         struct rb_node *cur = rb_first_cached(root), *next;
 289         struct rb_entry *cur_re, *next_re;
 290
 291         if (!cur)
 292                 return true;
 293
 294         while (cur) {
 295                 next = rb_next(cur);
 296                 if (!next)
 297                         return true;
 298
 299                 cur_re = rb_entry(cur, struct rb_entry, rb_node);
 300                 next_re = rb_entry(next, struct rb_entry, rb_node);
 301
 302                 if (cur_re->ofs + cur_re->len > next_re->ofs) {
 303                         f2fs_info(sbi, "inconsistent rbtree, cur(%u, %u) next(%u, %u)",
 304                                   cur_re->ofs, cur_re->len,
 305                                   next_re->ofs, next_re->len);
 306                         return false;
 307                 }
 308                 cur = next;
 309         }
 310 #endif
 311         return true;
 312 }
 313
 314 static struct kmem_cache *extent_tree_slab;
 315 static struct kmem_cache *extent_node_slab;
 316
 317 static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
 318                                 struct extent_tree *et, struct extent_info *ei,
 319                                 struct rb_node *parent, struct rb_node **p,
 320                                 bool leftmost)
 321 {
 322         struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 323         struct extent_node *en;
 324
 325         en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi);
 326         if (!en)
 327                 return NULL;
 328
 329         en->ei = *ei;
 330         INIT_LIST_HEAD(&en->list);
 331         en->et = et;
 332
 333         rb_link_node(&en->rb_node, parent, p);
 334         rb_insert_color_cached(&en->rb_node, &et->root, leftmost);
 335         atomic_inc(&et->node_cnt);
 336         atomic_inc(&eti->total_ext_node);
 337         return en;
 338 }
 339
 340 static void __detach_extent_node(struct f2fs_sb_info *sbi,
 341                                 struct extent_tree *et, struct extent_node *en)
 342 {
 343         struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 344
 345         rb_erase_cached(&en->rb_node, &et->root);
 346         atomic_dec(&et->node_cnt);
 347         atomic_dec(&eti->total_ext_node);
 348
 349         if (et->cached_en == en)
 350                 et->cached_en = NULL;
 351         kmem_cache_free(extent_node_slab, en);
 352 }
 353
 354 /*
 355  * Flow to release an extent_node:
 356  * 1. list_del_init
 357  * 2. __detach_extent_node
 358  * 3. kmem_cache_free.
 359  */
 360 static void __release_extent_node(struct f2fs_sb_info *sbi,
 361                         struct extent_tree *et, struct extent_node *en)
 362 {
 363         struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 364
 365         spin_lock(&eti->extent_lock);
 366         f2fs_bug_on(sbi, list_empty(&en->list));
 367         list_del_init(&en->list);
 368         spin_unlock(&eti->extent_lock);
 369
 370         __detach_extent_node(sbi, et, en);
 371 }
 372
 373 static struct extent_tree *__grab_extent_tree(struct inode *inode,
 374                                                 enum extent_type type)
 375 {
 376         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 377         struct extent_tree_info *eti = &sbi->extent_tree[type];
 378         struct extent_tree *et;
 379         nid_t ino = inode->i_ino;
 380
 381         mutex_lock(&eti->extent_tree_lock);
 382         et = radix_tree_lookup(&eti->extent_tree_root, ino);
 383         if (!et) {
 384                 et = f2fs_kmem_cache_alloc(extent_tree_slab,
 385                                         GFP_NOFS, true, NULL);
 386                 f2fs_radix_tree_insert(&eti->extent_tree_root, ino, et);
 387                 memset(et, 0, sizeof(struct extent_tree));
 388                 et->ino = ino;
 389                 et->type = type;
 390                 et->root = RB_ROOT_CACHED;
 391                 et->cached_en = NULL;
 392                 rwlock_init(&et->lock);
 393                 INIT_LIST_HEAD(&et->list);
 394                 atomic_set(&et->node_cnt, 0);
 395                 atomic_inc(&eti->total_ext_tree);
 396         } else {
 397                 atomic_dec(&eti->total_zombie_tree);
 398                 list_del_init(&et->list);
 399         }
 400         mutex_unlock(&eti->extent_tree_lock);
 401
 402         /* never died until evict_inode */
 403         F2FS_I(inode)->extent_tree[type] = et;
 404
 405         return et;
 406 }
 407
 408 static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
 409                                         struct extent_tree *et)
 410 {
 411         struct rb_node *node, *next;
 412         struct extent_node *en;
 413         unsigned int count = atomic_read(&et->node_cnt);
 414
 415         node = rb_first_cached(&et->root);
 416         while (node) {
 417                 next = rb_next(node);
 418                 en = rb_entry(node, struct extent_node, rb_node);
 419                 __release_extent_node(sbi, et, en);
 420                 node = next;
 421         }
 422
 423         return count - atomic_read(&et->node_cnt);
 424 }
 425
 426 static void __drop_largest_extent(struct extent_tree *et,
 427                                         pgoff_t fofs, unsigned int len)
 428 {
 429         if (fofs < et->largest.fofs + et->largest.len &&
 430                         fofs + len > et->largest.fofs) {
 431                 et->largest.len = 0;
 432                 et->largest_updated = true;
 433         }
 434 }
 435
 436 void f2fs_init_read_extent_tree(struct inode *inode, struct page *ipage)
 437 {
 438         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 439         struct extent_tree_info *eti = &sbi->extent_tree[EX_READ];
 440         struct f2fs_extent *i_ext = &F2FS_INODE(ipage)->i_ext;
 441         struct extent_tree *et;
 442         struct extent_node *en;
 443         struct extent_info ei;
 444
 445         if (!__may_extent_tree(inode, EX_READ)) {
 446                 /* drop largest read extent */
 447                 if (i_ext && i_ext->len) {
 448                         f2fs_wait_on_page_writeback(ipage, NODE, true, true);
 449                         i_ext->len = 0;
 450                         set_page_dirty(ipage);
 451                 }
 452                 goto out;
 453         }
 454
 455         et = __grab_extent_tree(inode, EX_READ);
 456
 457         if (!i_ext || !i_ext->len)
 458                 goto out;
 459
 460         get_read_extent_info(&ei, i_ext);
 461
 462         write_lock(&et->lock);
 463         if (atomic_read(&et->node_cnt))
 464                 goto unlock_out;
 465
 466         en = __attach_extent_node(sbi, et, &ei, NULL,
 467                                 &et->root.rb_root.rb_node, true);
 468         if (en) {
 469                 et->largest = en->ei;
 470                 et->cached_en = en;
 471
 472                 spin_lock(&eti->extent_lock);
 473                 list_add_tail(&en->list, &eti->extent_list);
 474                 spin_unlock(&eti->extent_lock);
 475         }
 476 unlock_out:
 477         write_unlock(&et->lock);
 478 out:
 479         if (!F2FS_I(inode)->extent_tree[EX_READ])
 480                 set_inode_flag(inode, FI_NO_EXTENT);
 481 }
 482
 483 void f2fs_init_extent_tree(struct inode *inode)
 484 {
 485         /* initialize read cache */
 486         if (__init_may_extent_tree(inode, EX_READ))
 487                 __grab_extent_tree(inode, EX_READ);
 488 }
 489
 490 static bool __lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
 491                         struct extent_info *ei, enum extent_type type)
 492 {
 493         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 494         struct extent_tree_info *eti = &sbi->extent_tree[type];
 495         struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 496         struct extent_node *en;
 497         bool ret = false;
 498
 499         if (!et)
 500                 return false;
 501
 502         trace_f2fs_lookup_extent_tree_start(inode, pgofs, type);
 503
 504         read_lock(&et->lock);
 505
 506         if (type == EX_READ &&
 507                         et->largest.fofs <= pgofs &&
 508                         et->largest.fofs + et->largest.len > pgofs) {
 509                 *ei = et->largest;
 510                 ret = true;
 511                 stat_inc_largest_node_hit(sbi);
 512                 goto out;
 513         }
 514
 515         en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root,
 516                                 (struct rb_entry *)et->cached_en, pgofs);
 517         if (!en)
 518                 goto out;
 519
 520         if (en == et->cached_en)
 521                 stat_inc_cached_node_hit(sbi, type);
 522         else
 523                 stat_inc_rbtree_node_hit(sbi, type);
 524
 525         *ei = en->ei;
 526         spin_lock(&eti->extent_lock);
 527         if (!list_empty(&en->list)) {
 528                 list_move_tail(&en->list, &eti->extent_list);
 529                 et->cached_en = en;
 530         }
 531         spin_unlock(&eti->extent_lock);
 532         ret = true;
 533 out:
 534         stat_inc_total_hit(sbi, type);
 535         read_unlock(&et->lock);
 536
 537         if (type == EX_READ)
 538                 trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei);
 539         return ret;
 540 }
 541
 542 static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
 543                                 struct extent_tree *et, struct extent_info *ei,
 544                                 struct extent_node *prev_ex,
 545                                 struct extent_node *next_ex)
 546 {
 547         struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 548         struct extent_node *en = NULL;
 549
 550         if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei, et->type)) {
 551                 prev_ex->ei.len += ei->len;
 552                 ei = &prev_ex->ei;
 553                 en = prev_ex;
 554         }
 555
 556         if (next_ex && __is_front_mergeable(ei, &next_ex->ei, et->type)) {
 557                 next_ex->ei.fofs = ei->fofs;
 558                 next_ex->ei.len += ei->len;
 559                 if (et->type == EX_READ)
 560                         next_ex->ei.blk = ei->blk;
 561                 if (en)
 562                         __release_extent_node(sbi, et, prev_ex);
 563
 564                 en = next_ex;
 565         }
 566
 567         if (!en)
 568                 return NULL;
 569
 570         __try_update_largest_extent(et, en);
 571
 572         spin_lock(&eti->extent_lock);
 573         if (!list_empty(&en->list)) {
 574                 list_move_tail(&en->list, &eti->extent_list);
 575                 et->cached_en = en;
 576         }
 577         spin_unlock(&eti->extent_lock);
 578         return en;
 579 }
 580
 581 static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
 582                                 struct extent_tree *et, struct extent_info *ei,
 583                                 struct rb_node **insert_p,
 584                                 struct rb_node *insert_parent,
 585                                 bool leftmost)
 586 {
 587         struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 588         struct rb_node **p;
 589         struct rb_node *parent = NULL;
 590         struct extent_node *en = NULL;
 591
 592         if (insert_p && insert_parent) {
 593                 parent = insert_parent;
 594                 p = insert_p;
 595                 goto do_insert;
 596         }
 597
 598         leftmost = true;
 599
 600         p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent,
 601                                                 ei->fofs, &leftmost);
 602 do_insert:
 603         en = __attach_extent_node(sbi, et, ei, parent, p, leftmost);
 604         if (!en)
 605                 return NULL;
 606
 607         __try_update_largest_extent(et, en);
 608
 609         /* update in global extent list */
 610         spin_lock(&eti->extent_lock);
 611         list_add_tail(&en->list, &eti->extent_list);
 612         et->cached_en = en;
 613         spin_unlock(&eti->extent_lock);
 614         return en;
 615 }
 616
 617 static void __update_extent_tree_range(struct inode *inode,
 618                         struct extent_info *tei, enum extent_type type)
 619 {
 620         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 621         struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 622         struct extent_node *en = NULL, *en1 = NULL;
 623         struct extent_node *prev_en = NULL, *next_en = NULL;
 624         struct extent_info ei, dei, prev;
 625         struct rb_node **insert_p = NULL, *insert_parent = NULL;
 626         unsigned int fofs = tei->fofs, len = tei->len;
 627         unsigned int end = fofs + len;
 628         bool updated = false;
 629         bool leftmost = false;
 630
 631         if (!et)
 632                 return;
 633
 634         if (type == EX_READ)
 635                 trace_f2fs_update_read_extent_tree_range(inode, fofs, len,
 636                                                 tei->blk, 0);
 637         write_lock(&et->lock);
 638
 639         if (type == EX_READ) {
 640                 if (is_inode_flag_set(inode, FI_NO_EXTENT)) {
 641                         write_unlock(&et->lock);
 642                         return;
 643                 }
 644
 645                 prev = et->largest;
 646                 dei.len = 0;
 647
 648                 /*
 649                  * drop largest extent before lookup, in case it's already
 650                  * been shrunk from extent tree
 651                  */
 652                 __drop_largest_extent(et, fofs, len);
 653         }
 654
 655         /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
 656         en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root,
 657                                         (struct rb_entry *)et->cached_en, fofs,
 658                                         (struct rb_entry **)&prev_en,
 659                                         (struct rb_entry **)&next_en,
 660                                         &insert_p, &insert_parent, false,
 661                                         &leftmost);
 662         if (!en)
 663                 en = next_en;
 664
 665         /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */
 666         while (en && en->ei.fofs < end) {
 667                 unsigned int org_end;
 668                 int parts = 0;  /* # of parts current extent split into */
 669
 670                 next_en = en1 = NULL;
 671
 672                 dei = en->ei;
 673                 org_end = dei.fofs + dei.len;
 674                 f2fs_bug_on(sbi, fofs >= org_end);
 675
 676                 if (fofs > dei.fofs && (type != EX_READ ||
 677                                 fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) {
 678                         en->ei.len = fofs - en->ei.fofs;
 679                         prev_en = en;
 680                         parts = 1;
 681                 }
 682
 683                 if (end < org_end && (type != EX_READ ||
 684                                 org_end - end >= F2FS_MIN_EXTENT_LEN)) {
 685                         if (parts) {
 686                                 __set_extent_info(&ei,
 687                                         end, org_end - end,
 688                                         end - dei.fofs + dei.blk, false,
 689                                         type);
 690                                 en1 = __insert_extent_tree(sbi, et, &ei,
 691                                                         NULL, NULL, true);
 692                                 next_en = en1;
 693                         } else {
 694                                 __set_extent_info(&en->ei,
 695                                         end, en->ei.len - (end - dei.fofs),
 696                                         en->ei.blk + (end - dei.fofs), true,
 697                                         type);
 698                                 next_en = en;
 699                         }
 700                         parts++;
 701                 }
 702
 703                 if (!next_en) {
 704                         struct rb_node *node = rb_next(&en->rb_node);
 705
 706                         next_en = rb_entry_safe(node, struct extent_node,
 707                                                 rb_node);
 708                 }
 709
 710                 if (parts)
 711                         __try_update_largest_extent(et, en);
 712                 else
 713                         __release_extent_node(sbi, et, en);
 714
 715                 /*
 716                  * if original extent is split into zero or two parts, extent
 717                  * tree has been altered by deletion or insertion, therefore
 718                  * invalidate pointers regard to tree.
 719                  */
 720                 if (parts != 1) {
 721                         insert_p = NULL;
 722                         insert_parent = NULL;
 723                 }
 724                 en = next_en;
 725         }
 726
 727         /* 3. update extent in read extent cache */
 728         BUG_ON(type != EX_READ);
 729
 730         if (tei->blk) {
 731                 __set_extent_info(&ei, fofs, len, tei->blk, false, EX_READ);
 732                 if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
 733                         __insert_extent_tree(sbi, et, &ei,
 734                                         insert_p, insert_parent, leftmost);
 735
 736                 /* give up extent_cache, if split and small updates happen */
 737                 if (dei.len >= 1 &&
 738                                 prev.len < F2FS_MIN_EXTENT_LEN &&
 739                                 et->largest.len < F2FS_MIN_EXTENT_LEN) {
 740                         et->largest.len = 0;
 741                         et->largest_updated = true;
 742                         set_inode_flag(inode, FI_NO_EXTENT);
 743                 }
 744         }
 745
 746         if (is_inode_flag_set(inode, FI_NO_EXTENT))
 747                 __free_extent_tree(sbi, et);
 748
 749         if (et->largest_updated) {
 750                 et->largest_updated = false;
 751                 updated = true;
 752         }
 753
 754         write_unlock(&et->lock);
 755
 756         if (updated)
 757                 f2fs_mark_inode_dirty_sync(inode, true);
 758 }
 759
 760 #ifdef CONFIG_F2FS_FS_COMPRESSION
 761 void f2fs_update_read_extent_tree_range_compressed(struct inode *inode,
 762                                 pgoff_t fofs, block_t blkaddr, unsigned int llen,
 763                                 unsigned int c_len)
 764 {
 765         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 766         struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ];
 767         struct extent_node *en = NULL;
 768         struct extent_node *prev_en = NULL, *next_en = NULL;
 769         struct extent_info ei;
 770         struct rb_node **insert_p = NULL, *insert_parent = NULL;
 771         bool leftmost = false;
 772
 773         trace_f2fs_update_read_extent_tree_range(inode, fofs, llen,
 774                                                 blkaddr, c_len);
 775
 776         /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */
 777         if (is_inode_flag_set(inode, FI_NO_EXTENT))
 778                 return;
 779
 780         write_lock(&et->lock);
 781
 782         en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root,
 783                                 (struct rb_entry *)et->cached_en, fofs,
 784                                 (struct rb_entry **)&prev_en,
 785                                 (struct rb_entry **)&next_en,
 786                                 &insert_p, &insert_parent, false,
 787                                 &leftmost);
 788         if (en)
 789                 goto unlock_out;
 790
 791         __set_extent_info(&ei, fofs, llen, blkaddr, true, EX_READ);
 792         ei.c_len = c_len;
 793
 794         if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
 795                 __insert_extent_tree(sbi, et, &ei,
 796                                 insert_p, insert_parent, leftmost);
 797 unlock_out:
 798         write_unlock(&et->lock);
 799 }
 800 #endif
 801
 802 static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type)
 803 {
 804         struct extent_info ei;
 805
 806         if (!__may_extent_tree(dn->inode, type))
 807                 return;
 808
 809         ei.fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) +
 810                                                                 dn->ofs_in_node;
 811         ei.len = 1;
 812
 813         if (type == EX_READ) {
 814                 if (dn->data_blkaddr == NEW_ADDR)
 815                         ei.blk = NULL_ADDR;
 816                 else
 817                         ei.blk = dn->data_blkaddr;
 818         }
 819         __update_extent_tree_range(dn->inode, &ei, type);
 820 }
 821
 822 static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink,
 823                                         enum extent_type type)
 824 {
 825         struct extent_tree_info *eti = &sbi->extent_tree[type];
 826         struct extent_tree *et, *next;
 827         struct extent_node *en;
 828         unsigned int node_cnt = 0, tree_cnt = 0;
 829         int remained;
 830
 831         if (!atomic_read(&eti->total_zombie_tree))
 832                 goto free_node;
 833
 834         if (!mutex_trylock(&eti->extent_tree_lock))
 835                 goto out;
 836
 837         /* 1. remove unreferenced extent tree */
 838         list_for_each_entry_safe(et, next, &eti->zombie_list, list) {
 839                 if (atomic_read(&et->node_cnt)) {
 840                         write_lock(&et->lock);
 841                         node_cnt += __free_extent_tree(sbi, et);
 842                         write_unlock(&et->lock);
 843                 }
 844                 f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
 845                 list_del_init(&et->list);
 846                 radix_tree_delete(&eti->extent_tree_root, et->ino);
 847                 kmem_cache_free(extent_tree_slab, et);
 848                 atomic_dec(&eti->total_ext_tree);
 849                 atomic_dec(&eti->total_zombie_tree);
 850                 tree_cnt++;
 851
 852                 if (node_cnt + tree_cnt >= nr_shrink)
 853                         goto unlock_out;
 854                 cond_resched();
 855         }
 856         mutex_unlock(&eti->extent_tree_lock);
 857
 858 free_node:
 859         /* 2. remove LRU extent entries */
 860         if (!mutex_trylock(&eti->extent_tree_lock))
 861                 goto out;
 862
 863         remained = nr_shrink - (node_cnt + tree_cnt);
 864
 865         spin_lock(&eti->extent_lock);
 866         for (; remained > 0; remained--) {
 867                 if (list_empty(&eti->extent_list))
 868                         break;
 869                 en = list_first_entry(&eti->extent_list,
 870                                         struct extent_node, list);
 871                 et = en->et;
 872                 if (!write_trylock(&et->lock)) {
 873                         /* refresh this extent node's position in extent list */
 874                         list_move_tail(&en->list, &eti->extent_list);
 875                         continue;
 876                 }
 877
 878                 list_del_init(&en->list);
 879                 spin_unlock(&eti->extent_lock);
 880
 881                 __detach_extent_node(sbi, et, en);
 882
 883                 write_unlock(&et->lock);
 884                 node_cnt++;
 885                 spin_lock(&eti->extent_lock);
 886         }
 887         spin_unlock(&eti->extent_lock);
 888
 889 unlock_out:
 890         mutex_unlock(&eti->extent_tree_lock);
 891 out:
 892         trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type);
 893
 894         return node_cnt + tree_cnt;
 895 }
 896
 897 /* read extent cache operations */
 898 bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs,
 899                                 struct extent_info *ei)
 900 {
 901         if (!__may_extent_tree(inode, EX_READ))
 902                 return false;
 903
 904         return __lookup_extent_tree(inode, pgofs, ei, EX_READ);
 905 }
 906
 907 void f2fs_update_read_extent_cache(struct dnode_of_data *dn)
 908 {
 909         return __update_extent_cache(dn, EX_READ);
 910 }
 911
 912 void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn,
 913                                 pgoff_t fofs, block_t blkaddr, unsigned int len)
 914 {
 915         struct extent_info ei = {
 916                 .fofs = fofs,
 917                 .len = len,
 918                 .blk = blkaddr,
 919         };
 920
 921         if (!__may_extent_tree(dn->inode, EX_READ))
 922                 return;
 923
 924         __update_extent_tree_range(dn->inode, &ei, EX_READ);
 925 }
 926
 927 unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 928 {
 929         if (!test_opt(sbi, READ_EXTENT_CACHE))
 930                 return 0;
 931
 932         return __shrink_extent_tree(sbi, nr_shrink, EX_READ);
 933 }
 934
 935 static unsigned int __destroy_extent_node(struct inode *inode,
 936                                         enum extent_type type)
 937 {
 938         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 939         struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 940         unsigned int node_cnt = 0;
 941
 942         if (!et || !atomic_read(&et->node_cnt))
 943                 return 0;
 944
 945         write_lock(&et->lock);
 946         node_cnt = __free_extent_tree(sbi, et);
 947         write_unlock(&et->lock);
 948
 949         return node_cnt;
 950 }
 951
 952 void f2fs_destroy_extent_node(struct inode *inode)
 953 {
 954         __destroy_extent_node(inode, EX_READ);
 955 }
 956
 957 static void __drop_extent_tree(struct inode *inode, enum extent_type type)
 958 {
 959         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 960         struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 961         bool updated = false;
 962
 963         if (!__may_extent_tree(inode, type))
 964                 return;
 965
 966         write_lock(&et->lock);
 967         __free_extent_tree(sbi, et);
 968         if (type == EX_READ) {
 969                 set_inode_flag(inode, FI_NO_EXTENT);
 970                 if (et->largest.len) {
 971                         et->largest.len = 0;
 972                         updated = true;
 973                 }
 974         }
 975         write_unlock(&et->lock);
 976         if (updated)
 977                 f2fs_mark_inode_dirty_sync(inode, true);
 978 }
 979
 980 void f2fs_drop_extent_tree(struct inode *inode)
 981 {
 982         __drop_extent_tree(inode, EX_READ);
 983 }
 984
 985 static void __destroy_extent_tree(struct inode *inode, enum extent_type type)
 986 {
 987         struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 988         struct extent_tree_info *eti = &sbi->extent_tree[type];
 989         struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 990         unsigned int node_cnt = 0;
 991
 992         if (!et)
 993                 return;
 994
 995         if (inode->i_nlink && !is_bad_inode(inode) &&
 996                                         atomic_read(&et->node_cnt)) {
 997                 mutex_lock(&eti->extent_tree_lock);
 998                 list_add_tail(&et->list, &eti->zombie_list);
 999                 atomic_inc(&eti->total_zombie_tree);
1000                 mutex_unlock(&eti->extent_tree_lock);
1001                 return;
1002         }
1003
1004         /* free all extent info belong to this extent tree */
1005         node_cnt = __destroy_extent_node(inode, type);
1006
1007         /* delete extent tree entry in radix tree */
1008         mutex_lock(&eti->extent_tree_lock);
1009         f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
1010         radix_tree_delete(&eti->extent_tree_root, inode->i_ino);
1011         kmem_cache_free(extent_tree_slab, et);
1012         atomic_dec(&eti->total_ext_tree);
1013         mutex_unlock(&eti->extent_tree_lock);
1014
1015         F2FS_I(inode)->extent_tree[type] = NULL;
1016
1017         trace_f2fs_destroy_extent_tree(inode, node_cnt, type);
1018 }
1019
1020 void f2fs_destroy_extent_tree(struct inode *inode)
1021 {
1022         __destroy_extent_tree(inode, EX_READ);
1023 }
1024
1025 static void __init_extent_tree_info(struct extent_tree_info *eti)
1026 {
1027         INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO);
1028         mutex_init(&eti->extent_tree_lock);
1029         INIT_LIST_HEAD(&eti->extent_list);
1030         spin_lock_init(&eti->extent_lock);
1031         atomic_set(&eti->total_ext_tree, 0);
1032         INIT_LIST_HEAD(&eti->zombie_list);
1033         atomic_set(&eti->total_zombie_tree, 0);
1034         atomic_set(&eti->total_ext_node, 0);
1035 }
1036
1037 void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi)
1038 {
1039         __init_extent_tree_info(&sbi->extent_tree[EX_READ]);
1040 }
1041
1042 int __init f2fs_create_extent_cache(void)
1043 {
1044         extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
1045                         sizeof(struct extent_tree));
1046         if (!extent_tree_slab)
1047                 return -ENOMEM;
1048         extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
1049                         sizeof(struct extent_node));
1050         if (!extent_node_slab) {
1051                 kmem_cache_destroy(extent_tree_slab);
1052                 return -ENOMEM;
1053         }
1054         return 0;
1055 }
1056
1057 void f2fs_destroy_extent_cache(void)
1058 {
1059         kmem_cache_destroy(extent_node_slab);
1060         kmem_cache_destroy(extent_tree_slab);
1061 }