fs/f2fs/extent_cache.c

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