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