17c1a000dSChao Yu // SPDX-License-Identifier: GPL-2.0 2a28ef1f5SChao Yu /* 3a28ef1f5SChao Yu * f2fs extent cache support 4a28ef1f5SChao Yu * 5a28ef1f5SChao Yu * Copyright (c) 2015 Motorola Mobility 6a28ef1f5SChao Yu * Copyright (c) 2015 Samsung Electronics 7a28ef1f5SChao Yu * Authors: Jaegeuk Kim <jaegeuk@kernel.org> 8a28ef1f5SChao Yu * Chao Yu <chao2.yu@samsung.com> 9a28ef1f5SChao Yu */ 10a28ef1f5SChao Yu 11a28ef1f5SChao Yu #include <linux/fs.h> 12a28ef1f5SChao Yu #include <linux/f2fs_fs.h> 13a28ef1f5SChao Yu 14a28ef1f5SChao Yu #include "f2fs.h" 15a28ef1f5SChao Yu #include "node.h" 16a28ef1f5SChao Yu #include <trace/events/f2fs.h> 17a28ef1f5SChao Yu 1854c2258cSChao Yu static struct rb_entry *__lookup_rb_tree_fast(struct rb_entry *cached_re, 1954c2258cSChao Yu unsigned int ofs) 2054c2258cSChao Yu { 2154c2258cSChao Yu if (cached_re) { 2254c2258cSChao Yu if (cached_re->ofs <= ofs && 2354c2258cSChao Yu cached_re->ofs + cached_re->len > ofs) { 2454c2258cSChao Yu return cached_re; 2554c2258cSChao Yu } 2654c2258cSChao Yu } 2754c2258cSChao Yu return NULL; 2854c2258cSChao Yu } 2954c2258cSChao Yu 304dada3fdSChao Yu static struct rb_entry *__lookup_rb_tree_slow(struct rb_root_cached *root, 3154c2258cSChao Yu unsigned int ofs) 3254c2258cSChao Yu { 334dada3fdSChao Yu struct rb_node *node = root->rb_root.rb_node; 3454c2258cSChao Yu struct rb_entry *re; 3554c2258cSChao Yu 3654c2258cSChao Yu while (node) { 3754c2258cSChao Yu re = rb_entry(node, struct rb_entry, rb_node); 3854c2258cSChao Yu 3954c2258cSChao Yu if (ofs < re->ofs) 4054c2258cSChao Yu node = node->rb_left; 4154c2258cSChao Yu else if (ofs >= re->ofs + re->len) 4254c2258cSChao Yu node = node->rb_right; 4354c2258cSChao Yu else 4454c2258cSChao Yu return re; 4554c2258cSChao Yu } 4654c2258cSChao Yu return NULL; 4754c2258cSChao Yu } 4854c2258cSChao Yu 494dada3fdSChao Yu struct rb_entry *f2fs_lookup_rb_tree(struct rb_root_cached *root, 5054c2258cSChao Yu struct rb_entry *cached_re, unsigned int ofs) 5154c2258cSChao Yu { 5254c2258cSChao Yu struct rb_entry *re; 5354c2258cSChao Yu 5454c2258cSChao Yu re = __lookup_rb_tree_fast(cached_re, ofs); 5554c2258cSChao Yu if (!re) 5654c2258cSChao Yu return __lookup_rb_tree_slow(root, ofs); 5754c2258cSChao Yu 5854c2258cSChao Yu return re; 5954c2258cSChao Yu } 6054c2258cSChao Yu 612e9b2bb2SChao Yu struct rb_node **f2fs_lookup_rb_tree_ext(struct f2fs_sb_info *sbi, 622e9b2bb2SChao Yu struct rb_root_cached *root, 632e9b2bb2SChao Yu struct rb_node **parent, 642e9b2bb2SChao Yu unsigned long long key, bool *leftmost) 652e9b2bb2SChao Yu { 662e9b2bb2SChao Yu struct rb_node **p = &root->rb_root.rb_node; 672e9b2bb2SChao Yu struct rb_entry *re; 682e9b2bb2SChao Yu 692e9b2bb2SChao Yu while (*p) { 702e9b2bb2SChao Yu *parent = *p; 712e9b2bb2SChao Yu re = rb_entry(*parent, struct rb_entry, rb_node); 722e9b2bb2SChao Yu 732e9b2bb2SChao Yu if (key < re->key) { 742e9b2bb2SChao Yu p = &(*p)->rb_left; 752e9b2bb2SChao Yu } else { 762e9b2bb2SChao Yu p = &(*p)->rb_right; 772e9b2bb2SChao Yu *leftmost = false; 782e9b2bb2SChao Yu } 792e9b2bb2SChao Yu } 802e9b2bb2SChao Yu 812e9b2bb2SChao Yu return p; 822e9b2bb2SChao Yu } 832e9b2bb2SChao Yu 844d57b86dSChao Yu struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi, 854dada3fdSChao Yu struct rb_root_cached *root, 864dada3fdSChao Yu struct rb_node **parent, 874dada3fdSChao Yu unsigned int ofs, bool *leftmost) 8854c2258cSChao Yu { 894dada3fdSChao Yu struct rb_node **p = &root->rb_root.rb_node; 9054c2258cSChao Yu struct rb_entry *re; 9154c2258cSChao Yu 9254c2258cSChao Yu while (*p) { 9354c2258cSChao Yu *parent = *p; 9454c2258cSChao Yu re = rb_entry(*parent, struct rb_entry, rb_node); 9554c2258cSChao Yu 964dada3fdSChao Yu if (ofs < re->ofs) { 9754c2258cSChao Yu p = &(*p)->rb_left; 984dada3fdSChao Yu } else if (ofs >= re->ofs + re->len) { 9954c2258cSChao Yu p = &(*p)->rb_right; 1004dada3fdSChao Yu *leftmost = false; 1014dada3fdSChao Yu } else { 10254c2258cSChao Yu f2fs_bug_on(sbi, 1); 10354c2258cSChao Yu } 1044dada3fdSChao Yu } 10554c2258cSChao Yu 10654c2258cSChao Yu return p; 10754c2258cSChao Yu } 10854c2258cSChao Yu 10954c2258cSChao Yu /* 11054c2258cSChao Yu * lookup rb entry in position of @ofs in rb-tree, 11154c2258cSChao Yu * if hit, return the entry, otherwise, return NULL 11254c2258cSChao Yu * @prev_ex: extent before ofs 11354c2258cSChao Yu * @next_ex: extent after ofs 11454c2258cSChao Yu * @insert_p: insert point for new extent at ofs 11554c2258cSChao Yu * in order to simpfy the insertion after. 11654c2258cSChao Yu * tree must stay unchanged between lookup and insertion. 11754c2258cSChao Yu */ 1184dada3fdSChao Yu struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root_cached *root, 11954c2258cSChao Yu struct rb_entry *cached_re, 12054c2258cSChao Yu unsigned int ofs, 12154c2258cSChao Yu struct rb_entry **prev_entry, 12254c2258cSChao Yu struct rb_entry **next_entry, 12354c2258cSChao Yu struct rb_node ***insert_p, 124004b6862SChao Yu struct rb_node **insert_parent, 1254dada3fdSChao Yu bool force, bool *leftmost) 12654c2258cSChao Yu { 1274dada3fdSChao Yu struct rb_node **pnode = &root->rb_root.rb_node; 12854c2258cSChao Yu struct rb_node *parent = NULL, *tmp_node; 12954c2258cSChao Yu struct rb_entry *re = cached_re; 13054c2258cSChao Yu 13154c2258cSChao Yu *insert_p = NULL; 13254c2258cSChao Yu *insert_parent = NULL; 13354c2258cSChao Yu *prev_entry = NULL; 13454c2258cSChao Yu *next_entry = NULL; 13554c2258cSChao Yu 1364dada3fdSChao Yu if (RB_EMPTY_ROOT(&root->rb_root)) 13754c2258cSChao Yu return NULL; 13854c2258cSChao Yu 13954c2258cSChao Yu if (re) { 14054c2258cSChao Yu if (re->ofs <= ofs && re->ofs + re->len > ofs) 14154c2258cSChao Yu goto lookup_neighbors; 14254c2258cSChao Yu } 14354c2258cSChao Yu 1444dada3fdSChao Yu if (leftmost) 1454dada3fdSChao Yu *leftmost = true; 1464dada3fdSChao Yu 14754c2258cSChao Yu while (*pnode) { 14854c2258cSChao Yu parent = *pnode; 14954c2258cSChao Yu re = rb_entry(*pnode, struct rb_entry, rb_node); 15054c2258cSChao Yu 1514dada3fdSChao Yu if (ofs < re->ofs) { 15254c2258cSChao Yu pnode = &(*pnode)->rb_left; 1534dada3fdSChao Yu } else if (ofs >= re->ofs + re->len) { 15454c2258cSChao Yu pnode = &(*pnode)->rb_right; 1554dada3fdSChao Yu if (leftmost) 1564dada3fdSChao Yu *leftmost = false; 1574dada3fdSChao Yu } else { 15854c2258cSChao Yu goto lookup_neighbors; 15954c2258cSChao Yu } 1604dada3fdSChao Yu } 16154c2258cSChao Yu 16254c2258cSChao Yu *insert_p = pnode; 16354c2258cSChao Yu *insert_parent = parent; 16454c2258cSChao Yu 16554c2258cSChao Yu re = rb_entry(parent, struct rb_entry, rb_node); 16654c2258cSChao Yu tmp_node = parent; 16754c2258cSChao Yu if (parent && ofs > re->ofs) 16854c2258cSChao Yu tmp_node = rb_next(parent); 16954c2258cSChao Yu *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 17054c2258cSChao Yu 17154c2258cSChao Yu tmp_node = parent; 17254c2258cSChao Yu if (parent && ofs < re->ofs) 17354c2258cSChao Yu tmp_node = rb_prev(parent); 17454c2258cSChao Yu *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 17554c2258cSChao Yu return NULL; 17654c2258cSChao Yu 17754c2258cSChao Yu lookup_neighbors: 178004b6862SChao Yu if (ofs == re->ofs || force) { 17954c2258cSChao Yu /* lookup prev node for merging backward later */ 18054c2258cSChao Yu tmp_node = rb_prev(&re->rb_node); 18154c2258cSChao Yu *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 18254c2258cSChao Yu } 183004b6862SChao Yu if (ofs == re->ofs + re->len - 1 || force) { 18454c2258cSChao Yu /* lookup next node for merging frontward later */ 18554c2258cSChao Yu tmp_node = rb_next(&re->rb_node); 18654c2258cSChao Yu *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 18754c2258cSChao Yu } 18854c2258cSChao Yu return re; 18954c2258cSChao Yu } 19054c2258cSChao Yu 1914d57b86dSChao Yu bool f2fs_check_rb_tree_consistence(struct f2fs_sb_info *sbi, 1922e9b2bb2SChao Yu struct rb_root_cached *root, bool check_key) 193df0f6b44SChao Yu { 194df0f6b44SChao Yu #ifdef CONFIG_F2FS_CHECK_FS 1954dada3fdSChao Yu struct rb_node *cur = rb_first_cached(root), *next; 196df0f6b44SChao Yu struct rb_entry *cur_re, *next_re; 197df0f6b44SChao Yu 198df0f6b44SChao Yu if (!cur) 199df0f6b44SChao Yu return true; 200df0f6b44SChao Yu 201df0f6b44SChao Yu while (cur) { 202df0f6b44SChao Yu next = rb_next(cur); 203df0f6b44SChao Yu if (!next) 204df0f6b44SChao Yu return true; 205df0f6b44SChao Yu 206df0f6b44SChao Yu cur_re = rb_entry(cur, struct rb_entry, rb_node); 207df0f6b44SChao Yu next_re = rb_entry(next, struct rb_entry, rb_node); 208df0f6b44SChao Yu 2092e9b2bb2SChao Yu if (check_key) { 2102e9b2bb2SChao Yu if (cur_re->key > next_re->key) { 2112e9b2bb2SChao Yu f2fs_info(sbi, "inconsistent rbtree, " 2122e9b2bb2SChao Yu "cur(%llu) next(%llu)", 2132e9b2bb2SChao Yu cur_re->key, next_re->key); 2142e9b2bb2SChao Yu return false; 2152e9b2bb2SChao Yu } 2162e9b2bb2SChao Yu goto next; 2172e9b2bb2SChao Yu } 2182e9b2bb2SChao Yu 219df0f6b44SChao Yu if (cur_re->ofs + cur_re->len > next_re->ofs) { 220dcbb4c10SJoe Perches f2fs_info(sbi, "inconsistent rbtree, cur(%u, %u) next(%u, %u)", 221df0f6b44SChao Yu cur_re->ofs, cur_re->len, 222df0f6b44SChao Yu next_re->ofs, next_re->len); 223df0f6b44SChao Yu return false; 224df0f6b44SChao Yu } 2252e9b2bb2SChao Yu next: 226df0f6b44SChao Yu cur = next; 227df0f6b44SChao Yu } 228df0f6b44SChao Yu #endif 229df0f6b44SChao Yu return true; 230df0f6b44SChao Yu } 231df0f6b44SChao Yu 232a28ef1f5SChao Yu static struct kmem_cache *extent_tree_slab; 233a28ef1f5SChao Yu static struct kmem_cache *extent_node_slab; 234a28ef1f5SChao Yu 235a28ef1f5SChao Yu static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi, 236a28ef1f5SChao Yu struct extent_tree *et, struct extent_info *ei, 2374dada3fdSChao Yu struct rb_node *parent, struct rb_node **p, 2384dada3fdSChao Yu bool leftmost) 239a28ef1f5SChao Yu { 240a28ef1f5SChao Yu struct extent_node *en; 241a28ef1f5SChao Yu 242a28ef1f5SChao Yu en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC); 243a28ef1f5SChao Yu if (!en) 244a28ef1f5SChao Yu return NULL; 245a28ef1f5SChao Yu 246a28ef1f5SChao Yu en->ei = *ei; 247a28ef1f5SChao Yu INIT_LIST_HEAD(&en->list); 248201ef5e0SHou Pengyang en->et = et; 249a28ef1f5SChao Yu 250a28ef1f5SChao Yu rb_link_node(&en->rb_node, parent, p); 2514dada3fdSChao Yu rb_insert_color_cached(&en->rb_node, &et->root, leftmost); 25268e35385SChao Yu atomic_inc(&et->node_cnt); 253a28ef1f5SChao Yu atomic_inc(&sbi->total_ext_node); 254a28ef1f5SChao Yu return en; 255a28ef1f5SChao Yu } 256a28ef1f5SChao Yu 257a28ef1f5SChao Yu static void __detach_extent_node(struct f2fs_sb_info *sbi, 258a28ef1f5SChao Yu struct extent_tree *et, struct extent_node *en) 259a28ef1f5SChao Yu { 2604dada3fdSChao Yu rb_erase_cached(&en->rb_node, &et->root); 26168e35385SChao Yu atomic_dec(&et->node_cnt); 262a28ef1f5SChao Yu atomic_dec(&sbi->total_ext_node); 263a28ef1f5SChao Yu 264a28ef1f5SChao Yu if (et->cached_en == en) 265a28ef1f5SChao Yu et->cached_en = NULL; 266a03f01f2SHou Pengyang kmem_cache_free(extent_node_slab, en); 267a03f01f2SHou Pengyang } 268a03f01f2SHou Pengyang 269a03f01f2SHou Pengyang /* 270a03f01f2SHou Pengyang * Flow to release an extent_node: 271a03f01f2SHou Pengyang * 1. list_del_init 272a03f01f2SHou Pengyang * 2. __detach_extent_node 273a03f01f2SHou Pengyang * 3. kmem_cache_free. 274a03f01f2SHou Pengyang */ 275a03f01f2SHou Pengyang static void __release_extent_node(struct f2fs_sb_info *sbi, 276a03f01f2SHou Pengyang struct extent_tree *et, struct extent_node *en) 277a03f01f2SHou Pengyang { 278a03f01f2SHou Pengyang spin_lock(&sbi->extent_lock); 279201ef5e0SHou Pengyang f2fs_bug_on(sbi, list_empty(&en->list)); 280a03f01f2SHou Pengyang list_del_init(&en->list); 281a03f01f2SHou Pengyang spin_unlock(&sbi->extent_lock); 282a03f01f2SHou Pengyang 283a03f01f2SHou Pengyang __detach_extent_node(sbi, et, en); 284a28ef1f5SChao Yu } 285a28ef1f5SChao Yu 286a28ef1f5SChao Yu static struct extent_tree *__grab_extent_tree(struct inode *inode) 287a28ef1f5SChao Yu { 288a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 289a28ef1f5SChao Yu struct extent_tree *et; 290a28ef1f5SChao Yu nid_t ino = inode->i_ino; 291a28ef1f5SChao Yu 2925e8256acSYunlei He mutex_lock(&sbi->extent_tree_lock); 293a28ef1f5SChao Yu et = radix_tree_lookup(&sbi->extent_tree_root, ino); 294a28ef1f5SChao Yu if (!et) { 295a28ef1f5SChao Yu et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS); 296a28ef1f5SChao Yu f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et); 297a28ef1f5SChao Yu memset(et, 0, sizeof(struct extent_tree)); 298a28ef1f5SChao Yu et->ino = ino; 2994dada3fdSChao Yu et->root = RB_ROOT_CACHED; 300a28ef1f5SChao Yu et->cached_en = NULL; 301a28ef1f5SChao Yu rwlock_init(&et->lock); 302137d09f0SJaegeuk Kim INIT_LIST_HEAD(&et->list); 30368e35385SChao Yu atomic_set(&et->node_cnt, 0); 3047441ccefSJaegeuk Kim atomic_inc(&sbi->total_ext_tree); 30574fd8d99SJaegeuk Kim } else { 30674fd8d99SJaegeuk Kim atomic_dec(&sbi->total_zombie_tree); 307137d09f0SJaegeuk Kim list_del_init(&et->list); 308a28ef1f5SChao Yu } 3095e8256acSYunlei He mutex_unlock(&sbi->extent_tree_lock); 310a28ef1f5SChao Yu 311a28ef1f5SChao Yu /* never died until evict_inode */ 312a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = et; 313a28ef1f5SChao Yu 314a28ef1f5SChao Yu return et; 315a28ef1f5SChao Yu } 316a28ef1f5SChao Yu 317a6f78345SChao Yu static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi, 318a6f78345SChao Yu struct extent_tree *et, struct extent_info *ei) 319a28ef1f5SChao Yu { 3204dada3fdSChao Yu struct rb_node **p = &et->root.rb_root.rb_node; 321a28ef1f5SChao Yu struct extent_node *en; 322a28ef1f5SChao Yu 3234dada3fdSChao Yu en = __attach_extent_node(sbi, et, ei, NULL, p, true); 324a28ef1f5SChao Yu if (!en) 325a28ef1f5SChao Yu return NULL; 326a6f78345SChao Yu 327a28ef1f5SChao Yu et->largest = en->ei; 328a28ef1f5SChao Yu et->cached_en = en; 329a28ef1f5SChao Yu return en; 330a28ef1f5SChao Yu } 331a28ef1f5SChao Yu 332a28ef1f5SChao Yu static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, 333201ef5e0SHou Pengyang struct extent_tree *et) 334a28ef1f5SChao Yu { 335a28ef1f5SChao Yu struct rb_node *node, *next; 336a28ef1f5SChao Yu struct extent_node *en; 33768e35385SChao Yu unsigned int count = atomic_read(&et->node_cnt); 338a28ef1f5SChao Yu 3394dada3fdSChao Yu node = rb_first_cached(&et->root); 340a28ef1f5SChao Yu while (node) { 341a28ef1f5SChao Yu next = rb_next(node); 342a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 343a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 344a28ef1f5SChao Yu node = next; 345a28ef1f5SChao Yu } 346a28ef1f5SChao Yu 34768e35385SChao Yu return count - atomic_read(&et->node_cnt); 348a28ef1f5SChao Yu } 349a28ef1f5SChao Yu 350b430f726SZhikang Zhang static void __drop_largest_extent(struct extent_tree *et, 35141a099deSFan Li pgoff_t fofs, unsigned int len) 352a28ef1f5SChao Yu { 353b430f726SZhikang Zhang if (fofs < et->largest.fofs + et->largest.len && 354b430f726SZhikang Zhang fofs + len > et->largest.fofs) { 355b430f726SZhikang Zhang et->largest.len = 0; 356b430f726SZhikang Zhang et->largest_updated = true; 357205b9822SJaegeuk Kim } 358a28ef1f5SChao Yu } 359a28ef1f5SChao Yu 360ed3d1256SJaegeuk Kim /* return true, if inode page is changed */ 361a6d601f3SChao Yu static void __f2fs_init_extent_tree(struct inode *inode, struct page *ipage) 362a28ef1f5SChao Yu { 363a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 364a6d601f3SChao Yu struct f2fs_extent *i_ext = ipage ? &F2FS_INODE(ipage)->i_ext : NULL; 365a28ef1f5SChao Yu struct extent_tree *et; 366a28ef1f5SChao Yu struct extent_node *en; 367a28ef1f5SChao Yu struct extent_info ei; 368a28ef1f5SChao Yu 369ed3d1256SJaegeuk Kim if (!f2fs_may_extent_tree(inode)) { 370ed3d1256SJaegeuk Kim /* drop largest extent */ 371ed3d1256SJaegeuk Kim if (i_ext && i_ext->len) { 372a6d601f3SChao Yu f2fs_wait_on_page_writeback(ipage, NODE, true, true); 373ed3d1256SJaegeuk Kim i_ext->len = 0; 374a6d601f3SChao Yu set_page_dirty(ipage); 375a6d601f3SChao Yu return; 376ed3d1256SJaegeuk Kim } 377a6d601f3SChao Yu return; 378ed3d1256SJaegeuk Kim } 379a28ef1f5SChao Yu 380a28ef1f5SChao Yu et = __grab_extent_tree(inode); 381a28ef1f5SChao Yu 382ed3d1256SJaegeuk Kim if (!i_ext || !i_ext->len) 383a6d601f3SChao Yu return; 384a28ef1f5SChao Yu 385bd933d4fSChao Yu get_extent_info(&ei, i_ext); 386a28ef1f5SChao Yu 387a28ef1f5SChao Yu write_lock(&et->lock); 38868e35385SChao Yu if (atomic_read(&et->node_cnt)) 389a28ef1f5SChao Yu goto out; 390a28ef1f5SChao Yu 391a6f78345SChao Yu en = __init_extent_tree(sbi, et, &ei); 392a28ef1f5SChao Yu if (en) { 393a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 394a28ef1f5SChao Yu list_add_tail(&en->list, &sbi->extent_list); 395a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 396a28ef1f5SChao Yu } 397a28ef1f5SChao Yu out: 398a28ef1f5SChao Yu write_unlock(&et->lock); 399a28ef1f5SChao Yu } 400a28ef1f5SChao Yu 401a6d601f3SChao Yu void f2fs_init_extent_tree(struct inode *inode, struct page *ipage) 402dad48e73SYunlei He { 403a6d601f3SChao Yu __f2fs_init_extent_tree(inode, ipage); 404dad48e73SYunlei He 405dad48e73SYunlei He if (!F2FS_I(inode)->extent_tree) 406dad48e73SYunlei He set_inode_flag(inode, FI_NO_EXTENT); 407dad48e73SYunlei He } 408dad48e73SYunlei He 409a28ef1f5SChao Yu static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs, 410a28ef1f5SChao Yu struct extent_info *ei) 411a28ef1f5SChao Yu { 412a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 413a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 414a28ef1f5SChao Yu struct extent_node *en; 415a28ef1f5SChao Yu bool ret = false; 416a28ef1f5SChao Yu 417a28ef1f5SChao Yu f2fs_bug_on(sbi, !et); 418a28ef1f5SChao Yu 419a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_start(inode, pgofs); 420a28ef1f5SChao Yu 421a28ef1f5SChao Yu read_lock(&et->lock); 422a28ef1f5SChao Yu 423a28ef1f5SChao Yu if (et->largest.fofs <= pgofs && 424a28ef1f5SChao Yu et->largest.fofs + et->largest.len > pgofs) { 425a28ef1f5SChao Yu *ei = et->largest; 426a28ef1f5SChao Yu ret = true; 42791c481ffSChao Yu stat_inc_largest_node_hit(sbi); 428a28ef1f5SChao Yu goto out; 429a28ef1f5SChao Yu } 430a28ef1f5SChao Yu 4314d57b86dSChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root, 43254c2258cSChao Yu (struct rb_entry *)et->cached_en, pgofs); 43354c2258cSChao Yu if (!en) 43454c2258cSChao Yu goto out; 43554c2258cSChao Yu 43654c2258cSChao Yu if (en == et->cached_en) 43754c2258cSChao Yu stat_inc_cached_node_hit(sbi); 43854c2258cSChao Yu else 43954c2258cSChao Yu stat_inc_rbtree_node_hit(sbi); 44054c2258cSChao Yu 441a28ef1f5SChao Yu *ei = en->ei; 442a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 44342926744SJaegeuk Kim if (!list_empty(&en->list)) { 444a28ef1f5SChao Yu list_move_tail(&en->list, &sbi->extent_list); 445a28ef1f5SChao Yu et->cached_en = en; 44642926744SJaegeuk Kim } 447a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 448a28ef1f5SChao Yu ret = true; 449a28ef1f5SChao Yu out: 450727edac5SChao Yu stat_inc_total_hit(sbi); 451a28ef1f5SChao Yu read_unlock(&et->lock); 452a28ef1f5SChao Yu 453a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei); 454a28ef1f5SChao Yu return ret; 455a28ef1f5SChao Yu } 456a28ef1f5SChao Yu 457b430f726SZhikang Zhang static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi, 4580f825ee6SFan Li struct extent_tree *et, struct extent_info *ei, 4590f825ee6SFan Li struct extent_node *prev_ex, 460ef05e221SChao Yu struct extent_node *next_ex) 4610f825ee6SFan Li { 4620f825ee6SFan Li struct extent_node *en = NULL; 4630f825ee6SFan Li 4640f825ee6SFan Li if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) { 4650f825ee6SFan Li prev_ex->ei.len += ei->len; 4660f825ee6SFan Li ei = &prev_ex->ei; 4670f825ee6SFan Li en = prev_ex; 4680f825ee6SFan Li } 469ef05e221SChao Yu 4700f825ee6SFan Li if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) { 4710f825ee6SFan Li next_ex->ei.fofs = ei->fofs; 4720f825ee6SFan Li next_ex->ei.blk = ei->blk; 4730f825ee6SFan Li next_ex->ei.len += ei->len; 4747855eba4SYunlei He if (en) 4757855eba4SYunlei He __release_extent_node(sbi, et, prev_ex); 4767855eba4SYunlei He 4770f825ee6SFan Li en = next_ex; 4780f825ee6SFan Li } 479ef05e221SChao Yu 48043a2fa18SJaegeuk Kim if (!en) 48143a2fa18SJaegeuk Kim return NULL; 48243a2fa18SJaegeuk Kim 483b430f726SZhikang Zhang __try_update_largest_extent(et, en); 48443a2fa18SJaegeuk Kim 48543a2fa18SJaegeuk Kim spin_lock(&sbi->extent_lock); 48642926744SJaegeuk Kim if (!list_empty(&en->list)) { 48743a2fa18SJaegeuk Kim list_move_tail(&en->list, &sbi->extent_list); 48842926744SJaegeuk Kim et->cached_en = en; 48942926744SJaegeuk Kim } 49043a2fa18SJaegeuk Kim spin_unlock(&sbi->extent_lock); 491ef05e221SChao Yu return en; 492ef05e221SChao Yu } 493ef05e221SChao Yu 494b430f726SZhikang Zhang static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, 495ef05e221SChao Yu struct extent_tree *et, struct extent_info *ei, 496ef05e221SChao Yu struct rb_node **insert_p, 4974dada3fdSChao Yu struct rb_node *insert_parent, 4984dada3fdSChao Yu bool leftmost) 499ef05e221SChao Yu { 5008fe326cbSColin Ian King struct rb_node **p; 501ef05e221SChao Yu struct rb_node *parent = NULL; 502ef05e221SChao Yu struct extent_node *en = NULL; 5030f825ee6SFan Li 5040f825ee6SFan Li if (insert_p && insert_parent) { 5050f825ee6SFan Li parent = insert_parent; 5060f825ee6SFan Li p = insert_p; 5070f825ee6SFan Li goto do_insert; 5080f825ee6SFan Li } 5090f825ee6SFan Li 5104dada3fdSChao Yu leftmost = true; 5114dada3fdSChao Yu 5124dada3fdSChao Yu p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent, 5134dada3fdSChao Yu ei->fofs, &leftmost); 5140f825ee6SFan Li do_insert: 5154dada3fdSChao Yu en = __attach_extent_node(sbi, et, ei, parent, p, leftmost); 5160f825ee6SFan Li if (!en) 5170f825ee6SFan Li return NULL; 518ef05e221SChao Yu 519b430f726SZhikang Zhang __try_update_largest_extent(et, en); 52043a2fa18SJaegeuk Kim 52143a2fa18SJaegeuk Kim /* update in global extent list */ 52243a2fa18SJaegeuk Kim spin_lock(&sbi->extent_lock); 52343a2fa18SJaegeuk Kim list_add_tail(&en->list, &sbi->extent_list); 52442926744SJaegeuk Kim et->cached_en = en; 52543a2fa18SJaegeuk Kim spin_unlock(&sbi->extent_lock); 5260f825ee6SFan Li return en; 5270f825ee6SFan Li } 5280f825ee6SFan Li 529317e1300SChao Yu static void f2fs_update_extent_tree_range(struct inode *inode, 53019b2c30dSChao Yu pgoff_t fofs, block_t blkaddr, unsigned int len) 531a28ef1f5SChao Yu { 532a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 533a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 5344d1fa815SFan Li struct extent_node *en = NULL, *en1 = NULL; 53519b2c30dSChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 536a28ef1f5SChao Yu struct extent_info ei, dei, prev; 5370f825ee6SFan Li struct rb_node **insert_p = NULL, *insert_parent = NULL; 53819b2c30dSChao Yu unsigned int end = fofs + len; 53919b2c30dSChao Yu unsigned int pos = (unsigned int)fofs; 540b430f726SZhikang Zhang bool updated = false; 541f9aa52a8SChao Yu bool leftmost = false; 542a28ef1f5SChao Yu 543a28ef1f5SChao Yu if (!et) 544317e1300SChao Yu return; 545a28ef1f5SChao Yu 546744288c7SChao Yu trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, len); 547744288c7SChao Yu 548a28ef1f5SChao Yu write_lock(&et->lock); 549a28ef1f5SChao Yu 55091942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) { 551a28ef1f5SChao Yu write_unlock(&et->lock); 552317e1300SChao Yu return; 553a28ef1f5SChao Yu } 554a28ef1f5SChao Yu 555a28ef1f5SChao Yu prev = et->largest; 556a28ef1f5SChao Yu dei.len = 0; 557a28ef1f5SChao Yu 5584d1fa815SFan Li /* 5594d1fa815SFan Li * drop largest extent before lookup, in case it's already 5604d1fa815SFan Li * been shrunk from extent tree 5614d1fa815SFan Li */ 562b430f726SZhikang Zhang __drop_largest_extent(et, fofs, len); 563a28ef1f5SChao Yu 56419b2c30dSChao Yu /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ 5654d57b86dSChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, 56654c2258cSChao Yu (struct rb_entry *)et->cached_en, fofs, 56754c2258cSChao Yu (struct rb_entry **)&prev_en, 56854c2258cSChao Yu (struct rb_entry **)&next_en, 5694dada3fdSChao Yu &insert_p, &insert_parent, false, 5704dada3fdSChao Yu &leftmost); 5714d1fa815SFan Li if (!en) 57219b2c30dSChao Yu en = next_en; 57319b2c30dSChao Yu 57419b2c30dSChao Yu /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */ 5754d1fa815SFan Li while (en && en->ei.fofs < end) { 5764d1fa815SFan Li unsigned int org_end; 5774d1fa815SFan Li int parts = 0; /* # of parts current extent split into */ 57819b2c30dSChao Yu 5794d1fa815SFan Li next_en = en1 = NULL; 580a28ef1f5SChao Yu 581a28ef1f5SChao Yu dei = en->ei; 5824d1fa815SFan Li org_end = dei.fofs + dei.len; 5834d1fa815SFan Li f2fs_bug_on(sbi, pos >= org_end); 58419b2c30dSChao Yu 5854d1fa815SFan Li if (pos > dei.fofs && pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) { 5864d1fa815SFan Li en->ei.len = pos - en->ei.fofs; 5874d1fa815SFan Li prev_en = en; 5884d1fa815SFan Li parts = 1; 58919b2c30dSChao Yu } 59019b2c30dSChao Yu 5914d1fa815SFan Li if (end < org_end && org_end - end >= F2FS_MIN_EXTENT_LEN) { 5924d1fa815SFan Li if (parts) { 5934d1fa815SFan Li set_extent_info(&ei, end, 5944d1fa815SFan Li end - dei.fofs + dei.blk, 5954d1fa815SFan Li org_end - end); 596b430f726SZhikang Zhang en1 = __insert_extent_tree(sbi, et, &ei, 5974dada3fdSChao Yu NULL, NULL, true); 5984d1fa815SFan Li next_en = en1; 5994d1fa815SFan Li } else { 60019b2c30dSChao Yu en->ei.fofs = end; 60119b2c30dSChao Yu en->ei.blk += end - dei.fofs; 60219b2c30dSChao Yu en->ei.len -= end - dei.fofs; 6034d1fa815SFan Li next_en = en; 6044d1fa815SFan Li } 6054d1fa815SFan Li parts++; 60619b2c30dSChao Yu } 60719b2c30dSChao Yu 6084d1fa815SFan Li if (!next_en) { 6094d1fa815SFan Li struct rb_node *node = rb_next(&en->rb_node); 6104d1fa815SFan Li 611ed0b5620SGeliang Tang next_en = rb_entry_safe(node, struct extent_node, 612ed0b5620SGeliang Tang rb_node); 6134d1fa815SFan Li } 6144d1fa815SFan Li 6154abd3f5aSChao Yu if (parts) 616b430f726SZhikang Zhang __try_update_largest_extent(et, en); 6174abd3f5aSChao Yu else 618a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 61919b2c30dSChao Yu 62019b2c30dSChao Yu /* 6214d1fa815SFan Li * if original extent is split into zero or two parts, extent 6224d1fa815SFan Li * tree has been altered by deletion or insertion, therefore 6234d1fa815SFan Li * invalidate pointers regard to tree. 62419b2c30dSChao Yu */ 6254d1fa815SFan Li if (parts != 1) { 62619b2c30dSChao Yu insert_p = NULL; 62719b2c30dSChao Yu insert_parent = NULL; 62819b2c30dSChao Yu } 6294d1fa815SFan Li en = next_en; 63019b2c30dSChao Yu } 631a28ef1f5SChao Yu 632a28ef1f5SChao Yu /* 3. update extent in extent cache */ 633a28ef1f5SChao Yu if (blkaddr) { 63419b2c30dSChao Yu 63519b2c30dSChao Yu set_extent_info(&ei, fofs, blkaddr, len); 636b430f726SZhikang Zhang if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 637b430f726SZhikang Zhang __insert_extent_tree(sbi, et, &ei, 6384dada3fdSChao Yu insert_p, insert_parent, leftmost); 639a28ef1f5SChao Yu 640a28ef1f5SChao Yu /* give up extent_cache, if split and small updates happen */ 641a28ef1f5SChao Yu if (dei.len >= 1 && 642a28ef1f5SChao Yu prev.len < F2FS_MIN_EXTENT_LEN && 643a28ef1f5SChao Yu et->largest.len < F2FS_MIN_EXTENT_LEN) { 644b430f726SZhikang Zhang et->largest.len = 0; 645b430f726SZhikang Zhang et->largest_updated = true; 64691942321SJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 647a28ef1f5SChao Yu } 64819b2c30dSChao Yu } 649a28ef1f5SChao Yu 65091942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) 651201ef5e0SHou Pengyang __free_extent_tree(sbi, et); 652a28ef1f5SChao Yu 653b430f726SZhikang Zhang if (et->largest_updated) { 654b430f726SZhikang Zhang et->largest_updated = false; 655b430f726SZhikang Zhang updated = true; 656b430f726SZhikang Zhang } 657b430f726SZhikang Zhang 658a28ef1f5SChao Yu write_unlock(&et->lock); 659b430f726SZhikang Zhang 660b430f726SZhikang Zhang if (updated) 661b430f726SZhikang Zhang f2fs_mark_inode_dirty_sync(inode, true); 662a28ef1f5SChao Yu } 663a28ef1f5SChao Yu 664*94afd6d6SChao Yu #ifdef CONFIG_F2FS_FS_COMPRESSION 665*94afd6d6SChao Yu void f2fs_update_extent_tree_range_compressed(struct inode *inode, 666*94afd6d6SChao Yu pgoff_t fofs, block_t blkaddr, unsigned int llen, 667*94afd6d6SChao Yu unsigned int c_len) 668*94afd6d6SChao Yu { 669*94afd6d6SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 670*94afd6d6SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 671*94afd6d6SChao Yu struct extent_node *en = NULL; 672*94afd6d6SChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 673*94afd6d6SChao Yu struct extent_info ei; 674*94afd6d6SChao Yu struct rb_node **insert_p = NULL, *insert_parent = NULL; 675*94afd6d6SChao Yu bool leftmost = false; 676*94afd6d6SChao Yu 677*94afd6d6SChao Yu trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, llen); 678*94afd6d6SChao Yu 679*94afd6d6SChao Yu /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */ 680*94afd6d6SChao Yu if (is_inode_flag_set(inode, FI_NO_EXTENT)) 681*94afd6d6SChao Yu return; 682*94afd6d6SChao Yu 683*94afd6d6SChao Yu write_lock(&et->lock); 684*94afd6d6SChao Yu 685*94afd6d6SChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, 686*94afd6d6SChao Yu (struct rb_entry *)et->cached_en, fofs, 687*94afd6d6SChao Yu (struct rb_entry **)&prev_en, 688*94afd6d6SChao Yu (struct rb_entry **)&next_en, 689*94afd6d6SChao Yu &insert_p, &insert_parent, false, 690*94afd6d6SChao Yu &leftmost); 691*94afd6d6SChao Yu if (en) 692*94afd6d6SChao Yu goto unlock_out; 693*94afd6d6SChao Yu 694*94afd6d6SChao Yu set_extent_info(&ei, fofs, blkaddr, llen); 695*94afd6d6SChao Yu ei.c_len = c_len; 696*94afd6d6SChao Yu 697*94afd6d6SChao Yu if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 698*94afd6d6SChao Yu __insert_extent_tree(sbi, et, &ei, 699*94afd6d6SChao Yu insert_p, insert_parent, leftmost); 700*94afd6d6SChao Yu unlock_out: 701*94afd6d6SChao Yu write_unlock(&et->lock); 702*94afd6d6SChao Yu } 703*94afd6d6SChao Yu #endif 704*94afd6d6SChao Yu 705a28ef1f5SChao Yu unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 706a28ef1f5SChao Yu { 707137d09f0SJaegeuk Kim struct extent_tree *et, *next; 708201ef5e0SHou Pengyang struct extent_node *en; 709a28ef1f5SChao Yu unsigned int node_cnt = 0, tree_cnt = 0; 710a28ef1f5SChao Yu int remained; 711a28ef1f5SChao Yu 712a28ef1f5SChao Yu if (!test_opt(sbi, EXTENT_CACHE)) 713a28ef1f5SChao Yu return 0; 714a28ef1f5SChao Yu 71574fd8d99SJaegeuk Kim if (!atomic_read(&sbi->total_zombie_tree)) 71674fd8d99SJaegeuk Kim goto free_node; 71774fd8d99SJaegeuk Kim 7185e8256acSYunlei He if (!mutex_trylock(&sbi->extent_tree_lock)) 719a28ef1f5SChao Yu goto out; 720a28ef1f5SChao Yu 721a28ef1f5SChao Yu /* 1. remove unreferenced extent tree */ 722137d09f0SJaegeuk Kim list_for_each_entry_safe(et, next, &sbi->zombie_list, list) { 7239b72a388SChao Yu if (atomic_read(&et->node_cnt)) { 724a28ef1f5SChao Yu write_lock(&et->lock); 725201ef5e0SHou Pengyang node_cnt += __free_extent_tree(sbi, et); 726a28ef1f5SChao Yu write_unlock(&et->lock); 7279b72a388SChao Yu } 728201ef5e0SHou Pengyang f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 729137d09f0SJaegeuk Kim list_del_init(&et->list); 730137d09f0SJaegeuk Kim radix_tree_delete(&sbi->extent_tree_root, et->ino); 731a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 7327441ccefSJaegeuk Kim atomic_dec(&sbi->total_ext_tree); 73374fd8d99SJaegeuk Kim atomic_dec(&sbi->total_zombie_tree); 734a28ef1f5SChao Yu tree_cnt++; 735a28ef1f5SChao Yu 736a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 737a28ef1f5SChao Yu goto unlock_out; 7386fe2bc95SJaegeuk Kim cond_resched(); 739a28ef1f5SChao Yu } 7405e8256acSYunlei He mutex_unlock(&sbi->extent_tree_lock); 741a28ef1f5SChao Yu 74274fd8d99SJaegeuk Kim free_node: 743a28ef1f5SChao Yu /* 2. remove LRU extent entries */ 7445e8256acSYunlei He if (!mutex_trylock(&sbi->extent_tree_lock)) 745a28ef1f5SChao Yu goto out; 746a28ef1f5SChao Yu 747a28ef1f5SChao Yu remained = nr_shrink - (node_cnt + tree_cnt); 748a28ef1f5SChao Yu 749a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 750201ef5e0SHou Pengyang for (; remained > 0; remained--) { 751201ef5e0SHou Pengyang if (list_empty(&sbi->extent_list)) 752a28ef1f5SChao Yu break; 753201ef5e0SHou Pengyang en = list_first_entry(&sbi->extent_list, 754201ef5e0SHou Pengyang struct extent_node, list); 755201ef5e0SHou Pengyang et = en->et; 756201ef5e0SHou Pengyang if (!write_trylock(&et->lock)) { 757201ef5e0SHou Pengyang /* refresh this extent node's position in extent list */ 758201ef5e0SHou Pengyang list_move_tail(&en->list, &sbi->extent_list); 759201ef5e0SHou Pengyang continue; 760201ef5e0SHou Pengyang } 761201ef5e0SHou Pengyang 762a28ef1f5SChao Yu list_del_init(&en->list); 763201ef5e0SHou Pengyang spin_unlock(&sbi->extent_lock); 764201ef5e0SHou Pengyang 765201ef5e0SHou Pengyang __detach_extent_node(sbi, et, en); 766201ef5e0SHou Pengyang 767201ef5e0SHou Pengyang write_unlock(&et->lock); 768201ef5e0SHou Pengyang node_cnt++; 769201ef5e0SHou Pengyang spin_lock(&sbi->extent_lock); 770a28ef1f5SChao Yu } 771a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 772a28ef1f5SChao Yu 773a28ef1f5SChao Yu unlock_out: 7745e8256acSYunlei He mutex_unlock(&sbi->extent_tree_lock); 775a28ef1f5SChao Yu out: 776a28ef1f5SChao Yu trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt); 777a28ef1f5SChao Yu 778a28ef1f5SChao Yu return node_cnt + tree_cnt; 779a28ef1f5SChao Yu } 780a28ef1f5SChao Yu 781a28ef1f5SChao Yu unsigned int f2fs_destroy_extent_node(struct inode *inode) 782a28ef1f5SChao Yu { 783a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 784a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 785a28ef1f5SChao Yu unsigned int node_cnt = 0; 786a28ef1f5SChao Yu 7879b72a388SChao Yu if (!et || !atomic_read(&et->node_cnt)) 788a28ef1f5SChao Yu return 0; 789a28ef1f5SChao Yu 790a28ef1f5SChao Yu write_lock(&et->lock); 791201ef5e0SHou Pengyang node_cnt = __free_extent_tree(sbi, et); 792a28ef1f5SChao Yu write_unlock(&et->lock); 793a28ef1f5SChao Yu 794a28ef1f5SChao Yu return node_cnt; 795a28ef1f5SChao Yu } 796a28ef1f5SChao Yu 7975f281fabSJaegeuk Kim void f2fs_drop_extent_tree(struct inode *inode) 7985f281fabSJaegeuk Kim { 7995f281fabSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 8005f281fabSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree; 801b430f726SZhikang Zhang bool updated = false; 8025f281fabSJaegeuk Kim 803bf617f7aSChao Yu if (!f2fs_may_extent_tree(inode)) 804bf617f7aSChao Yu return; 805bf617f7aSChao Yu 8065f281fabSJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 8075f281fabSJaegeuk Kim 8085f281fabSJaegeuk Kim write_lock(&et->lock); 8095f281fabSJaegeuk Kim __free_extent_tree(sbi, et); 810b430f726SZhikang Zhang if (et->largest.len) { 811b430f726SZhikang Zhang et->largest.len = 0; 812b430f726SZhikang Zhang updated = true; 813b430f726SZhikang Zhang } 8145f281fabSJaegeuk Kim write_unlock(&et->lock); 815b430f726SZhikang Zhang if (updated) 816b430f726SZhikang Zhang f2fs_mark_inode_dirty_sync(inode, true); 8175f281fabSJaegeuk Kim } 8185f281fabSJaegeuk Kim 819a28ef1f5SChao Yu void f2fs_destroy_extent_tree(struct inode *inode) 820a28ef1f5SChao Yu { 821a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 822a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 823a28ef1f5SChao Yu unsigned int node_cnt = 0; 824a28ef1f5SChao Yu 825a28ef1f5SChao Yu if (!et) 826a28ef1f5SChao Yu return; 827a28ef1f5SChao Yu 82868e35385SChao Yu if (inode->i_nlink && !is_bad_inode(inode) && 82968e35385SChao Yu atomic_read(&et->node_cnt)) { 8305e8256acSYunlei He mutex_lock(&sbi->extent_tree_lock); 831137d09f0SJaegeuk Kim list_add_tail(&et->list, &sbi->zombie_list); 83274fd8d99SJaegeuk Kim atomic_inc(&sbi->total_zombie_tree); 8335e8256acSYunlei He mutex_unlock(&sbi->extent_tree_lock); 834a28ef1f5SChao Yu return; 835a28ef1f5SChao Yu } 836a28ef1f5SChao Yu 837a28ef1f5SChao Yu /* free all extent info belong to this extent tree */ 838a28ef1f5SChao Yu node_cnt = f2fs_destroy_extent_node(inode); 839a28ef1f5SChao Yu 840a28ef1f5SChao Yu /* delete extent tree entry in radix tree */ 8415e8256acSYunlei He mutex_lock(&sbi->extent_tree_lock); 84268e35385SChao Yu f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 843a28ef1f5SChao Yu radix_tree_delete(&sbi->extent_tree_root, inode->i_ino); 844a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 8457441ccefSJaegeuk Kim atomic_dec(&sbi->total_ext_tree); 8465e8256acSYunlei He mutex_unlock(&sbi->extent_tree_lock); 847a28ef1f5SChao Yu 848a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = NULL; 849a28ef1f5SChao Yu 850a28ef1f5SChao Yu trace_f2fs_destroy_extent_tree(inode, node_cnt); 851a28ef1f5SChao Yu } 852a28ef1f5SChao Yu 853a28ef1f5SChao Yu bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs, 854a28ef1f5SChao Yu struct extent_info *ei) 855a28ef1f5SChao Yu { 856a28ef1f5SChao Yu if (!f2fs_may_extent_tree(inode)) 857a28ef1f5SChao Yu return false; 858a28ef1f5SChao Yu 859a28ef1f5SChao Yu return f2fs_lookup_extent_tree(inode, pgofs, ei); 860a28ef1f5SChao Yu } 861a28ef1f5SChao Yu 862a28ef1f5SChao Yu void f2fs_update_extent_cache(struct dnode_of_data *dn) 863a28ef1f5SChao Yu { 864a28ef1f5SChao Yu pgoff_t fofs; 865f28b3434SChao Yu block_t blkaddr; 866a28ef1f5SChao Yu 867a28ef1f5SChao Yu if (!f2fs_may_extent_tree(dn->inode)) 868a28ef1f5SChao Yu return; 869a28ef1f5SChao Yu 870f28b3434SChao Yu if (dn->data_blkaddr == NEW_ADDR) 871f28b3434SChao Yu blkaddr = NULL_ADDR; 872f28b3434SChao Yu else 873f28b3434SChao Yu blkaddr = dn->data_blkaddr; 87419b2c30dSChao Yu 8754d57b86dSChao Yu fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) + 876a28ef1f5SChao Yu dn->ofs_in_node; 877ee6d182fSJaegeuk Kim f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, 1); 87819b2c30dSChao Yu } 87919b2c30dSChao Yu 88019b2c30dSChao Yu void f2fs_update_extent_cache_range(struct dnode_of_data *dn, 88119b2c30dSChao Yu pgoff_t fofs, block_t blkaddr, unsigned int len) 88219b2c30dSChao Yu 88319b2c30dSChao Yu { 88419b2c30dSChao Yu if (!f2fs_may_extent_tree(dn->inode)) 88519b2c30dSChao Yu return; 88619b2c30dSChao Yu 887ee6d182fSJaegeuk Kim f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len); 888a28ef1f5SChao Yu } 889a28ef1f5SChao Yu 8904d57b86dSChao Yu void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi) 891a28ef1f5SChao Yu { 892a28ef1f5SChao Yu INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO); 8935e8256acSYunlei He mutex_init(&sbi->extent_tree_lock); 894a28ef1f5SChao Yu INIT_LIST_HEAD(&sbi->extent_list); 895a28ef1f5SChao Yu spin_lock_init(&sbi->extent_lock); 8967441ccefSJaegeuk Kim atomic_set(&sbi->total_ext_tree, 0); 897137d09f0SJaegeuk Kim INIT_LIST_HEAD(&sbi->zombie_list); 89874fd8d99SJaegeuk Kim atomic_set(&sbi->total_zombie_tree, 0); 899a28ef1f5SChao Yu atomic_set(&sbi->total_ext_node, 0); 900a28ef1f5SChao Yu } 901a28ef1f5SChao Yu 9024d57b86dSChao Yu int __init f2fs_create_extent_cache(void) 903a28ef1f5SChao Yu { 904a28ef1f5SChao Yu extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 905a28ef1f5SChao Yu sizeof(struct extent_tree)); 906a28ef1f5SChao Yu if (!extent_tree_slab) 907a28ef1f5SChao Yu return -ENOMEM; 908a28ef1f5SChao Yu extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 909a28ef1f5SChao Yu sizeof(struct extent_node)); 910a28ef1f5SChao Yu if (!extent_node_slab) { 911a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 912a28ef1f5SChao Yu return -ENOMEM; 913a28ef1f5SChao Yu } 914a28ef1f5SChao Yu return 0; 915a28ef1f5SChao Yu } 916a28ef1f5SChao Yu 9174d57b86dSChao Yu void f2fs_destroy_extent_cache(void) 918a28ef1f5SChao Yu { 919a28ef1f5SChao Yu kmem_cache_destroy(extent_node_slab); 920a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 921a28ef1f5SChao Yu } 922