1a28ef1f5SChao Yu /* 2a28ef1f5SChao Yu * f2fs extent cache support 3a28ef1f5SChao Yu * 4a28ef1f5SChao Yu * Copyright (c) 2015 Motorola Mobility 5a28ef1f5SChao Yu * Copyright (c) 2015 Samsung Electronics 6a28ef1f5SChao Yu * Authors: Jaegeuk Kim <jaegeuk@kernel.org> 7a28ef1f5SChao Yu * Chao Yu <chao2.yu@samsung.com> 8a28ef1f5SChao Yu * 9a28ef1f5SChao Yu * This program is free software; you can redistribute it and/or modify 10a28ef1f5SChao Yu * it under the terms of the GNU General Public License version 2 as 11a28ef1f5SChao Yu * published by the Free Software Foundation. 12a28ef1f5SChao Yu */ 13a28ef1f5SChao Yu 14a28ef1f5SChao Yu #include <linux/fs.h> 15a28ef1f5SChao Yu #include <linux/f2fs_fs.h> 16a28ef1f5SChao Yu 17a28ef1f5SChao Yu #include "f2fs.h" 18a28ef1f5SChao Yu #include "node.h" 19a28ef1f5SChao Yu #include <trace/events/f2fs.h> 20a28ef1f5SChao Yu 21a28ef1f5SChao Yu static struct kmem_cache *extent_tree_slab; 22a28ef1f5SChao Yu static struct kmem_cache *extent_node_slab; 23a28ef1f5SChao Yu 24a28ef1f5SChao Yu static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi, 25a28ef1f5SChao Yu struct extent_tree *et, struct extent_info *ei, 26a28ef1f5SChao Yu struct rb_node *parent, struct rb_node **p) 27a28ef1f5SChao Yu { 28a28ef1f5SChao Yu struct extent_node *en; 29a28ef1f5SChao Yu 30a28ef1f5SChao Yu en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC); 31a28ef1f5SChao Yu if (!en) 32a28ef1f5SChao Yu return NULL; 33a28ef1f5SChao Yu 34a28ef1f5SChao Yu en->ei = *ei; 35a28ef1f5SChao Yu INIT_LIST_HEAD(&en->list); 36201ef5e0SHou Pengyang en->et = et; 37a28ef1f5SChao Yu 38a28ef1f5SChao Yu rb_link_node(&en->rb_node, parent, p); 39a28ef1f5SChao Yu rb_insert_color(&en->rb_node, &et->root); 4068e35385SChao Yu atomic_inc(&et->node_cnt); 41a28ef1f5SChao Yu atomic_inc(&sbi->total_ext_node); 42a28ef1f5SChao Yu return en; 43a28ef1f5SChao Yu } 44a28ef1f5SChao Yu 45a28ef1f5SChao Yu static void __detach_extent_node(struct f2fs_sb_info *sbi, 46a28ef1f5SChao Yu struct extent_tree *et, struct extent_node *en) 47a28ef1f5SChao Yu { 48a28ef1f5SChao Yu rb_erase(&en->rb_node, &et->root); 4968e35385SChao Yu atomic_dec(&et->node_cnt); 50a28ef1f5SChao Yu atomic_dec(&sbi->total_ext_node); 51a28ef1f5SChao Yu 52a28ef1f5SChao Yu if (et->cached_en == en) 53a28ef1f5SChao Yu et->cached_en = NULL; 54a03f01f2SHou Pengyang kmem_cache_free(extent_node_slab, en); 55a03f01f2SHou Pengyang } 56a03f01f2SHou Pengyang 57a03f01f2SHou Pengyang /* 58a03f01f2SHou Pengyang * Flow to release an extent_node: 59a03f01f2SHou Pengyang * 1. list_del_init 60a03f01f2SHou Pengyang * 2. __detach_extent_node 61a03f01f2SHou Pengyang * 3. kmem_cache_free. 62a03f01f2SHou Pengyang */ 63a03f01f2SHou Pengyang static void __release_extent_node(struct f2fs_sb_info *sbi, 64a03f01f2SHou Pengyang struct extent_tree *et, struct extent_node *en) 65a03f01f2SHou Pengyang { 66a03f01f2SHou Pengyang spin_lock(&sbi->extent_lock); 67201ef5e0SHou Pengyang f2fs_bug_on(sbi, list_empty(&en->list)); 68a03f01f2SHou Pengyang list_del_init(&en->list); 69a03f01f2SHou Pengyang spin_unlock(&sbi->extent_lock); 70a03f01f2SHou Pengyang 71a03f01f2SHou Pengyang __detach_extent_node(sbi, et, en); 72a28ef1f5SChao Yu } 73a28ef1f5SChao Yu 74a28ef1f5SChao Yu static struct extent_tree *__grab_extent_tree(struct inode *inode) 75a28ef1f5SChao Yu { 76a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 77a28ef1f5SChao Yu struct extent_tree *et; 78a28ef1f5SChao Yu nid_t ino = inode->i_ino; 79a28ef1f5SChao Yu 80a28ef1f5SChao Yu down_write(&sbi->extent_tree_lock); 81a28ef1f5SChao Yu et = radix_tree_lookup(&sbi->extent_tree_root, ino); 82a28ef1f5SChao Yu if (!et) { 83a28ef1f5SChao Yu et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS); 84a28ef1f5SChao Yu f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et); 85a28ef1f5SChao Yu memset(et, 0, sizeof(struct extent_tree)); 86a28ef1f5SChao Yu et->ino = ino; 87a28ef1f5SChao Yu et->root = RB_ROOT; 88a28ef1f5SChao Yu et->cached_en = NULL; 89a28ef1f5SChao Yu rwlock_init(&et->lock); 90137d09f0SJaegeuk Kim INIT_LIST_HEAD(&et->list); 9168e35385SChao Yu atomic_set(&et->node_cnt, 0); 927441ccefSJaegeuk Kim atomic_inc(&sbi->total_ext_tree); 9374fd8d99SJaegeuk Kim } else { 9474fd8d99SJaegeuk Kim atomic_dec(&sbi->total_zombie_tree); 95137d09f0SJaegeuk Kim list_del_init(&et->list); 96a28ef1f5SChao Yu } 97a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 98a28ef1f5SChao Yu 99a28ef1f5SChao Yu /* never died until evict_inode */ 100a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = et; 101a28ef1f5SChao Yu 102a28ef1f5SChao Yu return et; 103a28ef1f5SChao Yu } 104a28ef1f5SChao Yu 10591c481ffSChao Yu static struct extent_node *__lookup_extent_tree(struct f2fs_sb_info *sbi, 10691c481ffSChao Yu struct extent_tree *et, unsigned int fofs) 107a28ef1f5SChao Yu { 108a28ef1f5SChao Yu struct rb_node *node = et->root.rb_node; 109f8b703daSFan Li struct extent_node *en = et->cached_en; 110a28ef1f5SChao Yu 111f8b703daSFan Li if (en) { 112f8b703daSFan Li struct extent_info *cei = &en->ei; 113a28ef1f5SChao Yu 11491c481ffSChao Yu if (cei->fofs <= fofs && cei->fofs + cei->len > fofs) { 11591c481ffSChao Yu stat_inc_cached_node_hit(sbi); 116f8b703daSFan Li return en; 117a28ef1f5SChao Yu } 11891c481ffSChao Yu } 119a28ef1f5SChao Yu 120a28ef1f5SChao Yu while (node) { 121a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 122a28ef1f5SChao Yu 123029e13ccSChao Yu if (fofs < en->ei.fofs) { 124a28ef1f5SChao Yu node = node->rb_left; 125029e13ccSChao Yu } else if (fofs >= en->ei.fofs + en->ei.len) { 126a28ef1f5SChao Yu node = node->rb_right; 127029e13ccSChao Yu } else { 128029e13ccSChao Yu stat_inc_rbtree_node_hit(sbi); 129a28ef1f5SChao Yu return en; 130a28ef1f5SChao Yu } 131029e13ccSChao Yu } 132a28ef1f5SChao Yu return NULL; 133a28ef1f5SChao Yu } 134a28ef1f5SChao Yu 135a6f78345SChao Yu static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi, 136a6f78345SChao Yu struct extent_tree *et, struct extent_info *ei) 137a28ef1f5SChao Yu { 138a28ef1f5SChao Yu struct rb_node **p = &et->root.rb_node; 139a28ef1f5SChao Yu struct extent_node *en; 140a28ef1f5SChao Yu 141a6f78345SChao Yu en = __attach_extent_node(sbi, et, ei, NULL, p); 142a28ef1f5SChao Yu if (!en) 143a28ef1f5SChao Yu return NULL; 144a6f78345SChao Yu 145a28ef1f5SChao Yu et->largest = en->ei; 146a28ef1f5SChao Yu et->cached_en = en; 147a28ef1f5SChao Yu return en; 148a28ef1f5SChao Yu } 149a28ef1f5SChao Yu 150a28ef1f5SChao Yu static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, 151201ef5e0SHou Pengyang struct extent_tree *et) 152a28ef1f5SChao Yu { 153a28ef1f5SChao Yu struct rb_node *node, *next; 154a28ef1f5SChao Yu struct extent_node *en; 15568e35385SChao Yu unsigned int count = atomic_read(&et->node_cnt); 156a28ef1f5SChao Yu 157a28ef1f5SChao Yu node = rb_first(&et->root); 158a28ef1f5SChao Yu while (node) { 159a28ef1f5SChao Yu next = rb_next(node); 160a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 161a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 162a28ef1f5SChao Yu node = next; 163a28ef1f5SChao Yu } 164a28ef1f5SChao Yu 16568e35385SChao Yu return count - atomic_read(&et->node_cnt); 166a28ef1f5SChao Yu } 167a28ef1f5SChao Yu 16841a099deSFan Li static void __drop_largest_extent(struct inode *inode, 16941a099deSFan Li pgoff_t fofs, unsigned int len) 170a28ef1f5SChao Yu { 171a28ef1f5SChao Yu struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest; 172a28ef1f5SChao Yu 173205b9822SJaegeuk Kim if (fofs < largest->fofs + largest->len && fofs + len > largest->fofs) { 174a28ef1f5SChao Yu largest->len = 0; 175205b9822SJaegeuk Kim mark_inode_dirty_sync(inode); 176205b9822SJaegeuk Kim } 177a28ef1f5SChao Yu } 178a28ef1f5SChao Yu 179ed3d1256SJaegeuk Kim /* return true, if inode page is changed */ 180ed3d1256SJaegeuk Kim bool f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext) 181a28ef1f5SChao Yu { 182a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 183a28ef1f5SChao Yu struct extent_tree *et; 184a28ef1f5SChao Yu struct extent_node *en; 185a28ef1f5SChao Yu struct extent_info ei; 186a28ef1f5SChao Yu 187ed3d1256SJaegeuk Kim if (!f2fs_may_extent_tree(inode)) { 188ed3d1256SJaegeuk Kim /* drop largest extent */ 189ed3d1256SJaegeuk Kim if (i_ext && i_ext->len) { 190ed3d1256SJaegeuk Kim i_ext->len = 0; 191ed3d1256SJaegeuk Kim return true; 192ed3d1256SJaegeuk Kim } 193ed3d1256SJaegeuk Kim return false; 194ed3d1256SJaegeuk Kim } 195a28ef1f5SChao Yu 196a28ef1f5SChao Yu et = __grab_extent_tree(inode); 197a28ef1f5SChao Yu 198ed3d1256SJaegeuk Kim if (!i_ext || !i_ext->len) 199ed3d1256SJaegeuk Kim return false; 200a28ef1f5SChao Yu 201bd933d4fSChao Yu get_extent_info(&ei, i_ext); 202a28ef1f5SChao Yu 203a28ef1f5SChao Yu write_lock(&et->lock); 20468e35385SChao Yu if (atomic_read(&et->node_cnt)) 205a28ef1f5SChao Yu goto out; 206a28ef1f5SChao Yu 207a6f78345SChao Yu en = __init_extent_tree(sbi, et, &ei); 208a28ef1f5SChao Yu if (en) { 209a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 210a28ef1f5SChao Yu list_add_tail(&en->list, &sbi->extent_list); 211a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 212a28ef1f5SChao Yu } 213a28ef1f5SChao Yu out: 214a28ef1f5SChao Yu write_unlock(&et->lock); 215ed3d1256SJaegeuk Kim return false; 216a28ef1f5SChao Yu } 217a28ef1f5SChao Yu 218a28ef1f5SChao Yu static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs, 219a28ef1f5SChao Yu struct extent_info *ei) 220a28ef1f5SChao Yu { 221a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 222a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 223a28ef1f5SChao Yu struct extent_node *en; 224a28ef1f5SChao Yu bool ret = false; 225a28ef1f5SChao Yu 226a28ef1f5SChao Yu f2fs_bug_on(sbi, !et); 227a28ef1f5SChao Yu 228a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_start(inode, pgofs); 229a28ef1f5SChao Yu 230a28ef1f5SChao Yu read_lock(&et->lock); 231a28ef1f5SChao Yu 232a28ef1f5SChao Yu if (et->largest.fofs <= pgofs && 233a28ef1f5SChao Yu et->largest.fofs + et->largest.len > pgofs) { 234a28ef1f5SChao Yu *ei = et->largest; 235a28ef1f5SChao Yu ret = true; 23691c481ffSChao Yu stat_inc_largest_node_hit(sbi); 237a28ef1f5SChao Yu goto out; 238a28ef1f5SChao Yu } 239a28ef1f5SChao Yu 24091c481ffSChao Yu en = __lookup_extent_tree(sbi, et, pgofs); 241a28ef1f5SChao Yu if (en) { 242a28ef1f5SChao Yu *ei = en->ei; 243a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 24442926744SJaegeuk Kim if (!list_empty(&en->list)) { 245a28ef1f5SChao Yu list_move_tail(&en->list, &sbi->extent_list); 246a28ef1f5SChao Yu et->cached_en = en; 24742926744SJaegeuk Kim } 248a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 249a28ef1f5SChao Yu ret = true; 250a28ef1f5SChao Yu } 251a28ef1f5SChao Yu out: 252727edac5SChao Yu stat_inc_total_hit(sbi); 253a28ef1f5SChao Yu read_unlock(&et->lock); 254a28ef1f5SChao Yu 255a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei); 256a28ef1f5SChao Yu return ret; 257a28ef1f5SChao Yu } 258a28ef1f5SChao Yu 2590f825ee6SFan Li 2600f825ee6SFan Li /* 2610f825ee6SFan Li * lookup extent at @fofs, if hit, return the extent 2620f825ee6SFan Li * if not, return NULL and 2630f825ee6SFan Li * @prev_ex: extent before fofs 2640f825ee6SFan Li * @next_ex: extent after fofs 2650f825ee6SFan Li * @insert_p: insert point for new extent at fofs 2660f825ee6SFan Li * in order to simpfy the insertion after. 2670f825ee6SFan Li * tree must stay unchanged between lookup and insertion. 2680f825ee6SFan Li */ 2690f825ee6SFan Li static struct extent_node *__lookup_extent_tree_ret(struct extent_tree *et, 27091c481ffSChao Yu unsigned int fofs, 27191c481ffSChao Yu struct extent_node **prev_ex, 2720f825ee6SFan Li struct extent_node **next_ex, 2730f825ee6SFan Li struct rb_node ***insert_p, 2740f825ee6SFan Li struct rb_node **insert_parent) 2750f825ee6SFan Li { 2760f825ee6SFan Li struct rb_node **pnode = &et->root.rb_node; 2770f825ee6SFan Li struct rb_node *parent = NULL, *tmp_node; 278dac2ddefSChao Yu struct extent_node *en = et->cached_en; 2790f825ee6SFan Li 280dac2ddefSChao Yu *insert_p = NULL; 281dac2ddefSChao Yu *insert_parent = NULL; 282dac2ddefSChao Yu *prev_ex = NULL; 283dac2ddefSChao Yu *next_ex = NULL; 284dac2ddefSChao Yu 285dac2ddefSChao Yu if (RB_EMPTY_ROOT(&et->root)) 286dac2ddefSChao Yu return NULL; 287dac2ddefSChao Yu 288dac2ddefSChao Yu if (en) { 289dac2ddefSChao Yu struct extent_info *cei = &en->ei; 2900f825ee6SFan Li 2910f825ee6SFan Li if (cei->fofs <= fofs && cei->fofs + cei->len > fofs) 292dac2ddefSChao Yu goto lookup_neighbors; 2930f825ee6SFan Li } 2940f825ee6SFan Li 2950f825ee6SFan Li while (*pnode) { 2960f825ee6SFan Li parent = *pnode; 2970f825ee6SFan Li en = rb_entry(*pnode, struct extent_node, rb_node); 2980f825ee6SFan Li 2990f825ee6SFan Li if (fofs < en->ei.fofs) 3000f825ee6SFan Li pnode = &(*pnode)->rb_left; 3010f825ee6SFan Li else if (fofs >= en->ei.fofs + en->ei.len) 3020f825ee6SFan Li pnode = &(*pnode)->rb_right; 3030f825ee6SFan Li else 304dac2ddefSChao Yu goto lookup_neighbors; 3050f825ee6SFan Li } 3060f825ee6SFan Li 3070f825ee6SFan Li *insert_p = pnode; 3080f825ee6SFan Li *insert_parent = parent; 3090f825ee6SFan Li 3100f825ee6SFan Li en = rb_entry(parent, struct extent_node, rb_node); 3110f825ee6SFan Li tmp_node = parent; 3120f825ee6SFan Li if (parent && fofs > en->ei.fofs) 3130f825ee6SFan Li tmp_node = rb_next(parent); 3140f825ee6SFan Li *next_ex = tmp_node ? 3150f825ee6SFan Li rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 3160f825ee6SFan Li 3170f825ee6SFan Li tmp_node = parent; 3180f825ee6SFan Li if (parent && fofs < en->ei.fofs) 3190f825ee6SFan Li tmp_node = rb_prev(parent); 3200f825ee6SFan Li *prev_ex = tmp_node ? 3210f825ee6SFan Li rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 3220f825ee6SFan Li return NULL; 323dac2ddefSChao Yu 324dac2ddefSChao Yu lookup_neighbors: 325dac2ddefSChao Yu if (fofs == en->ei.fofs) { 326dac2ddefSChao Yu /* lookup prev node for merging backward later */ 327dac2ddefSChao Yu tmp_node = rb_prev(&en->rb_node); 328dac2ddefSChao Yu *prev_ex = tmp_node ? 329dac2ddefSChao Yu rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 330dac2ddefSChao Yu } 331dac2ddefSChao Yu if (fofs == en->ei.fofs + en->ei.len - 1) { 332dac2ddefSChao Yu /* lookup next node for merging frontward later */ 333dac2ddefSChao Yu tmp_node = rb_next(&en->rb_node); 334dac2ddefSChao Yu *next_ex = tmp_node ? 335dac2ddefSChao Yu rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 336dac2ddefSChao Yu } 337dac2ddefSChao Yu return en; 3380f825ee6SFan Li } 3390f825ee6SFan Li 340205b9822SJaegeuk Kim static struct extent_node *__try_merge_extent_node(struct inode *inode, 3410f825ee6SFan Li struct extent_tree *et, struct extent_info *ei, 3420f825ee6SFan Li struct extent_node *prev_ex, 343ef05e221SChao Yu struct extent_node *next_ex) 3440f825ee6SFan Li { 345205b9822SJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 3460f825ee6SFan Li struct extent_node *en = NULL; 3470f825ee6SFan Li 3480f825ee6SFan Li if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) { 3490f825ee6SFan Li prev_ex->ei.len += ei->len; 3500f825ee6SFan Li ei = &prev_ex->ei; 3510f825ee6SFan Li en = prev_ex; 3520f825ee6SFan Li } 353ef05e221SChao Yu 3540f825ee6SFan Li if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) { 355a03f01f2SHou Pengyang if (en) 356a03f01f2SHou Pengyang __release_extent_node(sbi, et, prev_ex); 3570f825ee6SFan Li next_ex->ei.fofs = ei->fofs; 3580f825ee6SFan Li next_ex->ei.blk = ei->blk; 3590f825ee6SFan Li next_ex->ei.len += ei->len; 3600f825ee6SFan Li en = next_ex; 3610f825ee6SFan Li } 362ef05e221SChao Yu 36343a2fa18SJaegeuk Kim if (!en) 36443a2fa18SJaegeuk Kim return NULL; 36543a2fa18SJaegeuk Kim 366205b9822SJaegeuk Kim __try_update_largest_extent(inode, et, en); 36743a2fa18SJaegeuk Kim 36843a2fa18SJaegeuk Kim spin_lock(&sbi->extent_lock); 36942926744SJaegeuk Kim if (!list_empty(&en->list)) { 37043a2fa18SJaegeuk Kim list_move_tail(&en->list, &sbi->extent_list); 37142926744SJaegeuk Kim et->cached_en = en; 37242926744SJaegeuk Kim } 37343a2fa18SJaegeuk Kim spin_unlock(&sbi->extent_lock); 374ef05e221SChao Yu return en; 375ef05e221SChao Yu } 376ef05e221SChao Yu 377205b9822SJaegeuk Kim static struct extent_node *__insert_extent_tree(struct inode *inode, 378ef05e221SChao Yu struct extent_tree *et, struct extent_info *ei, 379ef05e221SChao Yu struct rb_node **insert_p, 380ef05e221SChao Yu struct rb_node *insert_parent) 381ef05e221SChao Yu { 382205b9822SJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 383ef05e221SChao Yu struct rb_node **p = &et->root.rb_node; 384ef05e221SChao Yu struct rb_node *parent = NULL; 385ef05e221SChao Yu struct extent_node *en = NULL; 3860f825ee6SFan Li 3870f825ee6SFan Li if (insert_p && insert_parent) { 3880f825ee6SFan Li parent = insert_parent; 3890f825ee6SFan Li p = insert_p; 3900f825ee6SFan Li goto do_insert; 3910f825ee6SFan Li } 3920f825ee6SFan Li 3930f825ee6SFan Li while (*p) { 3940f825ee6SFan Li parent = *p; 3950f825ee6SFan Li en = rb_entry(parent, struct extent_node, rb_node); 3960f825ee6SFan Li 3970f825ee6SFan Li if (ei->fofs < en->ei.fofs) 3980f825ee6SFan Li p = &(*p)->rb_left; 3990f825ee6SFan Li else if (ei->fofs >= en->ei.fofs + en->ei.len) 4000f825ee6SFan Li p = &(*p)->rb_right; 4010f825ee6SFan Li else 4020f825ee6SFan Li f2fs_bug_on(sbi, 1); 4030f825ee6SFan Li } 4040f825ee6SFan Li do_insert: 4050f825ee6SFan Li en = __attach_extent_node(sbi, et, ei, parent, p); 4060f825ee6SFan Li if (!en) 4070f825ee6SFan Li return NULL; 408ef05e221SChao Yu 409205b9822SJaegeuk Kim __try_update_largest_extent(inode, et, en); 41043a2fa18SJaegeuk Kim 41143a2fa18SJaegeuk Kim /* update in global extent list */ 41243a2fa18SJaegeuk Kim spin_lock(&sbi->extent_lock); 41343a2fa18SJaegeuk Kim list_add_tail(&en->list, &sbi->extent_list); 41442926744SJaegeuk Kim et->cached_en = en; 41543a2fa18SJaegeuk Kim spin_unlock(&sbi->extent_lock); 4160f825ee6SFan Li return en; 4170f825ee6SFan Li } 4180f825ee6SFan Li 419514053e4SJaegeuk Kim static unsigned int f2fs_update_extent_tree_range(struct inode *inode, 42019b2c30dSChao Yu pgoff_t fofs, block_t blkaddr, unsigned int len) 421a28ef1f5SChao Yu { 422a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 423a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 4244d1fa815SFan Li struct extent_node *en = NULL, *en1 = NULL; 42519b2c30dSChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 426a28ef1f5SChao Yu struct extent_info ei, dei, prev; 4270f825ee6SFan Li struct rb_node **insert_p = NULL, *insert_parent = NULL; 42819b2c30dSChao Yu unsigned int end = fofs + len; 42919b2c30dSChao Yu unsigned int pos = (unsigned int)fofs; 430a28ef1f5SChao Yu 431a28ef1f5SChao Yu if (!et) 432a28ef1f5SChao Yu return false; 433a28ef1f5SChao Yu 434744288c7SChao Yu trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, len); 435744288c7SChao Yu 436a28ef1f5SChao Yu write_lock(&et->lock); 437a28ef1f5SChao Yu 43891942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) { 439a28ef1f5SChao Yu write_unlock(&et->lock); 440a28ef1f5SChao Yu return false; 441a28ef1f5SChao Yu } 442a28ef1f5SChao Yu 443a28ef1f5SChao Yu prev = et->largest; 444a28ef1f5SChao Yu dei.len = 0; 445a28ef1f5SChao Yu 4464d1fa815SFan Li /* 4474d1fa815SFan Li * drop largest extent before lookup, in case it's already 4484d1fa815SFan Li * been shrunk from extent tree 4494d1fa815SFan Li */ 45041a099deSFan Li __drop_largest_extent(inode, fofs, len); 451a28ef1f5SChao Yu 45219b2c30dSChao Yu /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ 45319b2c30dSChao Yu en = __lookup_extent_tree_ret(et, fofs, &prev_en, &next_en, 4540f825ee6SFan Li &insert_p, &insert_parent); 4554d1fa815SFan Li if (!en) 45619b2c30dSChao Yu en = next_en; 45719b2c30dSChao Yu 45819b2c30dSChao Yu /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */ 4594d1fa815SFan Li while (en && en->ei.fofs < end) { 4604d1fa815SFan Li unsigned int org_end; 4614d1fa815SFan Li int parts = 0; /* # of parts current extent split into */ 46219b2c30dSChao Yu 4634d1fa815SFan Li next_en = en1 = NULL; 464a28ef1f5SChao Yu 465a28ef1f5SChao Yu dei = en->ei; 4664d1fa815SFan Li org_end = dei.fofs + dei.len; 4674d1fa815SFan Li f2fs_bug_on(sbi, pos >= org_end); 46819b2c30dSChao Yu 4694d1fa815SFan Li if (pos > dei.fofs && pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) { 4704d1fa815SFan Li en->ei.len = pos - en->ei.fofs; 4714d1fa815SFan Li prev_en = en; 4724d1fa815SFan Li parts = 1; 47319b2c30dSChao Yu } 47419b2c30dSChao Yu 4754d1fa815SFan Li if (end < org_end && org_end - end >= F2FS_MIN_EXTENT_LEN) { 4764d1fa815SFan Li if (parts) { 4774d1fa815SFan Li set_extent_info(&ei, end, 4784d1fa815SFan Li end - dei.fofs + dei.blk, 4794d1fa815SFan Li org_end - end); 480205b9822SJaegeuk Kim en1 = __insert_extent_tree(inode, et, &ei, 4814d1fa815SFan Li NULL, NULL); 4824d1fa815SFan Li next_en = en1; 4834d1fa815SFan Li } else { 48419b2c30dSChao Yu en->ei.fofs = end; 48519b2c30dSChao Yu en->ei.blk += end - dei.fofs; 48619b2c30dSChao Yu en->ei.len -= end - dei.fofs; 4874d1fa815SFan Li next_en = en; 4884d1fa815SFan Li } 4894d1fa815SFan Li parts++; 49019b2c30dSChao Yu } 49119b2c30dSChao Yu 4924d1fa815SFan Li if (!next_en) { 4934d1fa815SFan Li struct rb_node *node = rb_next(&en->rb_node); 4944d1fa815SFan Li 4954d1fa815SFan Li next_en = node ? 4964d1fa815SFan Li rb_entry(node, struct extent_node, rb_node) 4974d1fa815SFan Li : NULL; 4984d1fa815SFan Li } 4994d1fa815SFan Li 5004abd3f5aSChao Yu if (parts) 501205b9822SJaegeuk Kim __try_update_largest_extent(inode, et, en); 5024abd3f5aSChao Yu else 503a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 50419b2c30dSChao Yu 50519b2c30dSChao Yu /* 5064d1fa815SFan Li * if original extent is split into zero or two parts, extent 5074d1fa815SFan Li * tree has been altered by deletion or insertion, therefore 5084d1fa815SFan Li * invalidate pointers regard to tree. 50919b2c30dSChao Yu */ 5104d1fa815SFan Li if (parts != 1) { 51119b2c30dSChao Yu insert_p = NULL; 51219b2c30dSChao Yu insert_parent = NULL; 51319b2c30dSChao Yu } 5144d1fa815SFan Li en = next_en; 51519b2c30dSChao Yu } 516a28ef1f5SChao Yu 517a28ef1f5SChao Yu /* 3. update extent in extent cache */ 518a28ef1f5SChao Yu if (blkaddr) { 51919b2c30dSChao Yu 52019b2c30dSChao Yu set_extent_info(&ei, fofs, blkaddr, len); 521205b9822SJaegeuk Kim if (!__try_merge_extent_node(inode, et, &ei, prev_en, next_en)) 522205b9822SJaegeuk Kim __insert_extent_tree(inode, et, &ei, 523ef05e221SChao Yu insert_p, insert_parent); 524a28ef1f5SChao Yu 525a28ef1f5SChao Yu /* give up extent_cache, if split and small updates happen */ 526a28ef1f5SChao Yu if (dei.len >= 1 && 527a28ef1f5SChao Yu prev.len < F2FS_MIN_EXTENT_LEN && 528a28ef1f5SChao Yu et->largest.len < F2FS_MIN_EXTENT_LEN) { 529205b9822SJaegeuk Kim __drop_largest_extent(inode, 0, UINT_MAX); 53091942321SJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 531a28ef1f5SChao Yu } 53219b2c30dSChao Yu } 533a28ef1f5SChao Yu 53491942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) 535201ef5e0SHou Pengyang __free_extent_tree(sbi, et); 536a28ef1f5SChao Yu 537a28ef1f5SChao Yu write_unlock(&et->lock); 538a28ef1f5SChao Yu 539a28ef1f5SChao Yu return !__is_extent_same(&prev, &et->largest); 540a28ef1f5SChao Yu } 541a28ef1f5SChao Yu 542a28ef1f5SChao Yu unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 543a28ef1f5SChao Yu { 544137d09f0SJaegeuk Kim struct extent_tree *et, *next; 545201ef5e0SHou Pengyang struct extent_node *en; 546a28ef1f5SChao Yu unsigned int node_cnt = 0, tree_cnt = 0; 547a28ef1f5SChao Yu int remained; 548a28ef1f5SChao Yu 549a28ef1f5SChao Yu if (!test_opt(sbi, EXTENT_CACHE)) 550a28ef1f5SChao Yu return 0; 551a28ef1f5SChao Yu 55274fd8d99SJaegeuk Kim if (!atomic_read(&sbi->total_zombie_tree)) 55374fd8d99SJaegeuk Kim goto free_node; 55474fd8d99SJaegeuk Kim 555a28ef1f5SChao Yu if (!down_write_trylock(&sbi->extent_tree_lock)) 556a28ef1f5SChao Yu goto out; 557a28ef1f5SChao Yu 558a28ef1f5SChao Yu /* 1. remove unreferenced extent tree */ 559137d09f0SJaegeuk Kim list_for_each_entry_safe(et, next, &sbi->zombie_list, list) { 5609b72a388SChao Yu if (atomic_read(&et->node_cnt)) { 561a28ef1f5SChao Yu write_lock(&et->lock); 562201ef5e0SHou Pengyang node_cnt += __free_extent_tree(sbi, et); 563a28ef1f5SChao Yu write_unlock(&et->lock); 5649b72a388SChao Yu } 565201ef5e0SHou Pengyang f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 566137d09f0SJaegeuk Kim list_del_init(&et->list); 567137d09f0SJaegeuk Kim radix_tree_delete(&sbi->extent_tree_root, et->ino); 568a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 5697441ccefSJaegeuk Kim atomic_dec(&sbi->total_ext_tree); 57074fd8d99SJaegeuk Kim atomic_dec(&sbi->total_zombie_tree); 571a28ef1f5SChao Yu tree_cnt++; 572a28ef1f5SChao Yu 573a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 574a28ef1f5SChao Yu goto unlock_out; 5756fe2bc95SJaegeuk Kim cond_resched(); 576a28ef1f5SChao Yu } 577a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 578a28ef1f5SChao Yu 57974fd8d99SJaegeuk Kim free_node: 580a28ef1f5SChao Yu /* 2. remove LRU extent entries */ 581a28ef1f5SChao Yu if (!down_write_trylock(&sbi->extent_tree_lock)) 582a28ef1f5SChao Yu goto out; 583a28ef1f5SChao Yu 584a28ef1f5SChao Yu remained = nr_shrink - (node_cnt + tree_cnt); 585a28ef1f5SChao Yu 586a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 587201ef5e0SHou Pengyang for (; remained > 0; remained--) { 588201ef5e0SHou Pengyang if (list_empty(&sbi->extent_list)) 589a28ef1f5SChao Yu break; 590201ef5e0SHou Pengyang en = list_first_entry(&sbi->extent_list, 591201ef5e0SHou Pengyang struct extent_node, list); 592201ef5e0SHou Pengyang et = en->et; 593201ef5e0SHou Pengyang if (!write_trylock(&et->lock)) { 594201ef5e0SHou Pengyang /* refresh this extent node's position in extent list */ 595201ef5e0SHou Pengyang list_move_tail(&en->list, &sbi->extent_list); 596201ef5e0SHou Pengyang continue; 597201ef5e0SHou Pengyang } 598201ef5e0SHou Pengyang 599a28ef1f5SChao Yu list_del_init(&en->list); 600201ef5e0SHou Pengyang spin_unlock(&sbi->extent_lock); 601201ef5e0SHou Pengyang 602201ef5e0SHou Pengyang __detach_extent_node(sbi, et, en); 603201ef5e0SHou Pengyang 604201ef5e0SHou Pengyang write_unlock(&et->lock); 605201ef5e0SHou Pengyang node_cnt++; 606201ef5e0SHou Pengyang spin_lock(&sbi->extent_lock); 607a28ef1f5SChao Yu } 608a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 609a28ef1f5SChao Yu 610a28ef1f5SChao Yu unlock_out: 611a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 612a28ef1f5SChao Yu out: 613a28ef1f5SChao Yu trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt); 614a28ef1f5SChao Yu 615a28ef1f5SChao Yu return node_cnt + tree_cnt; 616a28ef1f5SChao Yu } 617a28ef1f5SChao Yu 618a28ef1f5SChao Yu unsigned int f2fs_destroy_extent_node(struct inode *inode) 619a28ef1f5SChao Yu { 620a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 621a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 622a28ef1f5SChao Yu unsigned int node_cnt = 0; 623a28ef1f5SChao Yu 6249b72a388SChao Yu if (!et || !atomic_read(&et->node_cnt)) 625a28ef1f5SChao Yu return 0; 626a28ef1f5SChao Yu 627a28ef1f5SChao Yu write_lock(&et->lock); 628201ef5e0SHou Pengyang node_cnt = __free_extent_tree(sbi, et); 629a28ef1f5SChao Yu write_unlock(&et->lock); 630a28ef1f5SChao Yu 631a28ef1f5SChao Yu return node_cnt; 632a28ef1f5SChao Yu } 633a28ef1f5SChao Yu 634a28ef1f5SChao Yu void f2fs_destroy_extent_tree(struct inode *inode) 635a28ef1f5SChao Yu { 636a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 637a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 638a28ef1f5SChao Yu unsigned int node_cnt = 0; 639a28ef1f5SChao Yu 640a28ef1f5SChao Yu if (!et) 641a28ef1f5SChao Yu return; 642a28ef1f5SChao Yu 64368e35385SChao Yu if (inode->i_nlink && !is_bad_inode(inode) && 64468e35385SChao Yu atomic_read(&et->node_cnt)) { 645137d09f0SJaegeuk Kim down_write(&sbi->extent_tree_lock); 646137d09f0SJaegeuk Kim list_add_tail(&et->list, &sbi->zombie_list); 64774fd8d99SJaegeuk Kim atomic_inc(&sbi->total_zombie_tree); 648137d09f0SJaegeuk Kim up_write(&sbi->extent_tree_lock); 649a28ef1f5SChao Yu return; 650a28ef1f5SChao Yu } 651a28ef1f5SChao Yu 652a28ef1f5SChao Yu /* free all extent info belong to this extent tree */ 653a28ef1f5SChao Yu node_cnt = f2fs_destroy_extent_node(inode); 654a28ef1f5SChao Yu 655a28ef1f5SChao Yu /* delete extent tree entry in radix tree */ 656a28ef1f5SChao Yu down_write(&sbi->extent_tree_lock); 65768e35385SChao Yu f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 658a28ef1f5SChao Yu radix_tree_delete(&sbi->extent_tree_root, inode->i_ino); 659a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 6607441ccefSJaegeuk Kim atomic_dec(&sbi->total_ext_tree); 661a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 662a28ef1f5SChao Yu 663a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = NULL; 664a28ef1f5SChao Yu 665a28ef1f5SChao Yu trace_f2fs_destroy_extent_tree(inode, node_cnt); 666a28ef1f5SChao Yu } 667a28ef1f5SChao Yu 668a28ef1f5SChao Yu bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs, 669a28ef1f5SChao Yu struct extent_info *ei) 670a28ef1f5SChao Yu { 671a28ef1f5SChao Yu if (!f2fs_may_extent_tree(inode)) 672a28ef1f5SChao Yu return false; 673a28ef1f5SChao Yu 674a28ef1f5SChao Yu return f2fs_lookup_extent_tree(inode, pgofs, ei); 675a28ef1f5SChao Yu } 676a28ef1f5SChao Yu 677a28ef1f5SChao Yu void f2fs_update_extent_cache(struct dnode_of_data *dn) 678a28ef1f5SChao Yu { 679a28ef1f5SChao Yu pgoff_t fofs; 680f28b3434SChao Yu block_t blkaddr; 681a28ef1f5SChao Yu 682a28ef1f5SChao Yu if (!f2fs_may_extent_tree(dn->inode)) 683a28ef1f5SChao Yu return; 684a28ef1f5SChao Yu 685f28b3434SChao Yu if (dn->data_blkaddr == NEW_ADDR) 686f28b3434SChao Yu blkaddr = NULL_ADDR; 687f28b3434SChao Yu else 688f28b3434SChao Yu blkaddr = dn->data_blkaddr; 68919b2c30dSChao Yu 69081ca7350SChao Yu fofs = start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) + 691a28ef1f5SChao Yu dn->ofs_in_node; 692*ee6d182fSJaegeuk Kim f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, 1); 69319b2c30dSChao Yu } 69419b2c30dSChao Yu 69519b2c30dSChao Yu void f2fs_update_extent_cache_range(struct dnode_of_data *dn, 69619b2c30dSChao Yu pgoff_t fofs, block_t blkaddr, unsigned int len) 69719b2c30dSChao Yu 69819b2c30dSChao Yu { 69919b2c30dSChao Yu if (!f2fs_may_extent_tree(dn->inode)) 70019b2c30dSChao Yu return; 70119b2c30dSChao Yu 702*ee6d182fSJaegeuk Kim f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len); 703a28ef1f5SChao Yu } 704a28ef1f5SChao Yu 705a28ef1f5SChao Yu void init_extent_cache_info(struct f2fs_sb_info *sbi) 706a28ef1f5SChao Yu { 707a28ef1f5SChao Yu INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO); 708a28ef1f5SChao Yu init_rwsem(&sbi->extent_tree_lock); 709a28ef1f5SChao Yu INIT_LIST_HEAD(&sbi->extent_list); 710a28ef1f5SChao Yu spin_lock_init(&sbi->extent_lock); 7117441ccefSJaegeuk Kim atomic_set(&sbi->total_ext_tree, 0); 712137d09f0SJaegeuk Kim INIT_LIST_HEAD(&sbi->zombie_list); 71374fd8d99SJaegeuk Kim atomic_set(&sbi->total_zombie_tree, 0); 714a28ef1f5SChao Yu atomic_set(&sbi->total_ext_node, 0); 715a28ef1f5SChao Yu } 716a28ef1f5SChao Yu 717a28ef1f5SChao Yu int __init create_extent_cache(void) 718a28ef1f5SChao Yu { 719a28ef1f5SChao Yu extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 720a28ef1f5SChao Yu sizeof(struct extent_tree)); 721a28ef1f5SChao Yu if (!extent_tree_slab) 722a28ef1f5SChao Yu return -ENOMEM; 723a28ef1f5SChao Yu extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 724a28ef1f5SChao Yu sizeof(struct extent_node)); 725a28ef1f5SChao Yu if (!extent_node_slab) { 726a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 727a28ef1f5SChao Yu return -ENOMEM; 728a28ef1f5SChao Yu } 729a28ef1f5SChao Yu return 0; 730a28ef1f5SChao Yu } 731a28ef1f5SChao Yu 732a28ef1f5SChao Yu void destroy_extent_cache(void) 733a28ef1f5SChao Yu { 734a28ef1f5SChao Yu kmem_cache_destroy(extent_node_slab); 735a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 736a28ef1f5SChao Yu } 737