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