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); 36a28ef1f5SChao Yu 37a28ef1f5SChao Yu rb_link_node(&en->rb_node, parent, p); 38a28ef1f5SChao Yu rb_insert_color(&en->rb_node, &et->root); 39a28ef1f5SChao Yu et->count++; 40a28ef1f5SChao Yu atomic_inc(&sbi->total_ext_node); 41a28ef1f5SChao Yu return en; 42a28ef1f5SChao Yu } 43a28ef1f5SChao Yu 44a28ef1f5SChao Yu static void __detach_extent_node(struct f2fs_sb_info *sbi, 45a28ef1f5SChao Yu struct extent_tree *et, struct extent_node *en) 46a28ef1f5SChao Yu { 47a28ef1f5SChao Yu rb_erase(&en->rb_node, &et->root); 48a28ef1f5SChao Yu et->count--; 49a28ef1f5SChao Yu atomic_dec(&sbi->total_ext_node); 50a28ef1f5SChao Yu 51a28ef1f5SChao Yu if (et->cached_en == en) 52a28ef1f5SChao Yu et->cached_en = NULL; 53a28ef1f5SChao Yu } 54a28ef1f5SChao Yu 55a28ef1f5SChao Yu static struct extent_tree *__grab_extent_tree(struct inode *inode) 56a28ef1f5SChao Yu { 57a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 58a28ef1f5SChao Yu struct extent_tree *et; 59a28ef1f5SChao Yu nid_t ino = inode->i_ino; 60a28ef1f5SChao Yu 61a28ef1f5SChao Yu down_write(&sbi->extent_tree_lock); 62a28ef1f5SChao Yu et = radix_tree_lookup(&sbi->extent_tree_root, ino); 63a28ef1f5SChao Yu if (!et) { 64a28ef1f5SChao Yu et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS); 65a28ef1f5SChao Yu f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et); 66a28ef1f5SChao Yu memset(et, 0, sizeof(struct extent_tree)); 67a28ef1f5SChao Yu et->ino = ino; 68a28ef1f5SChao Yu et->root = RB_ROOT; 69a28ef1f5SChao Yu et->cached_en = NULL; 70a28ef1f5SChao Yu rwlock_init(&et->lock); 71a28ef1f5SChao Yu atomic_set(&et->refcount, 0); 72a28ef1f5SChao Yu et->count = 0; 73a28ef1f5SChao Yu sbi->total_ext_tree++; 74a28ef1f5SChao Yu } 75a28ef1f5SChao Yu atomic_inc(&et->refcount); 76a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 77a28ef1f5SChao Yu 78a28ef1f5SChao Yu /* never died until evict_inode */ 79a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = et; 80a28ef1f5SChao Yu 81a28ef1f5SChao Yu return et; 82a28ef1f5SChao Yu } 83a28ef1f5SChao Yu 8491c481ffSChao Yu static struct extent_node *__lookup_extent_tree(struct f2fs_sb_info *sbi, 8591c481ffSChao Yu struct extent_tree *et, unsigned int fofs) 86a28ef1f5SChao Yu { 87a28ef1f5SChao Yu struct rb_node *node = et->root.rb_node; 88f8b703daSFan Li struct extent_node *en = et->cached_en; 89a28ef1f5SChao Yu 90f8b703daSFan Li if (en) { 91f8b703daSFan Li struct extent_info *cei = &en->ei; 92a28ef1f5SChao Yu 9391c481ffSChao Yu if (cei->fofs <= fofs && cei->fofs + cei->len > fofs) { 9491c481ffSChao Yu stat_inc_cached_node_hit(sbi); 95f8b703daSFan Li return en; 96a28ef1f5SChao Yu } 9791c481ffSChao Yu } 98a28ef1f5SChao Yu 99a28ef1f5SChao Yu while (node) { 100a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 101a28ef1f5SChao Yu 102029e13ccSChao Yu if (fofs < en->ei.fofs) { 103a28ef1f5SChao Yu node = node->rb_left; 104029e13ccSChao Yu } else if (fofs >= en->ei.fofs + en->ei.len) { 105a28ef1f5SChao Yu node = node->rb_right; 106029e13ccSChao Yu } else { 107029e13ccSChao Yu stat_inc_rbtree_node_hit(sbi); 108a28ef1f5SChao Yu return en; 109a28ef1f5SChao Yu } 110029e13ccSChao Yu } 111a28ef1f5SChao Yu return NULL; 112a28ef1f5SChao Yu } 113a28ef1f5SChao Yu 114a6f78345SChao Yu static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi, 115a6f78345SChao Yu struct extent_tree *et, struct extent_info *ei) 116a28ef1f5SChao Yu { 117a28ef1f5SChao Yu struct rb_node **p = &et->root.rb_node; 118a28ef1f5SChao Yu struct extent_node *en; 119a28ef1f5SChao Yu 120a6f78345SChao Yu en = __attach_extent_node(sbi, et, ei, NULL, p); 121a28ef1f5SChao Yu if (!en) 122a28ef1f5SChao Yu return NULL; 123a6f78345SChao Yu 124a28ef1f5SChao Yu et->largest = en->ei; 125a28ef1f5SChao Yu et->cached_en = en; 126a28ef1f5SChao Yu return en; 127a28ef1f5SChao Yu } 128a28ef1f5SChao Yu 129a28ef1f5SChao Yu static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, 130a28ef1f5SChao Yu struct extent_tree *et, bool free_all) 131a28ef1f5SChao Yu { 132a28ef1f5SChao Yu struct rb_node *node, *next; 133a28ef1f5SChao Yu struct extent_node *en; 134a28ef1f5SChao Yu unsigned int count = et->count; 135a28ef1f5SChao Yu 136a28ef1f5SChao Yu node = rb_first(&et->root); 137a28ef1f5SChao Yu while (node) { 138a28ef1f5SChao Yu next = rb_next(node); 139a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 140a28ef1f5SChao Yu 141a28ef1f5SChao Yu if (free_all) { 142a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 143a28ef1f5SChao Yu if (!list_empty(&en->list)) 144a28ef1f5SChao Yu list_del_init(&en->list); 145a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 146a28ef1f5SChao Yu } 147a28ef1f5SChao Yu 148a28ef1f5SChao Yu if (free_all || list_empty(&en->list)) { 149a28ef1f5SChao Yu __detach_extent_node(sbi, et, en); 150a28ef1f5SChao Yu kmem_cache_free(extent_node_slab, en); 151a28ef1f5SChao Yu } 152a28ef1f5SChao Yu node = next; 153a28ef1f5SChao Yu } 154a28ef1f5SChao Yu 155a28ef1f5SChao Yu return count - et->count; 156a28ef1f5SChao Yu } 157a28ef1f5SChao Yu 15854d71856SChao Yu static void __drop_largest_extent(struct inode *inode, pgoff_t fofs) 159a28ef1f5SChao Yu { 160a28ef1f5SChao Yu struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest; 161a28ef1f5SChao Yu 162a28ef1f5SChao Yu if (largest->fofs <= fofs && largest->fofs + largest->len > fofs) 163a28ef1f5SChao Yu largest->len = 0; 164a28ef1f5SChao Yu } 165a28ef1f5SChao Yu 16654d71856SChao Yu void f2fs_drop_largest_extent(struct inode *inode, pgoff_t fofs) 16754d71856SChao Yu { 16854d71856SChao Yu if (!f2fs_may_extent_tree(inode)) 16954d71856SChao Yu return; 17054d71856SChao Yu 17154d71856SChao Yu __drop_largest_extent(inode, fofs); 17254d71856SChao Yu } 17354d71856SChao Yu 174a28ef1f5SChao Yu void f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext) 175a28ef1f5SChao Yu { 176a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 177a28ef1f5SChao Yu struct extent_tree *et; 178a28ef1f5SChao Yu struct extent_node *en; 179a28ef1f5SChao Yu struct extent_info ei; 180a28ef1f5SChao Yu 181a28ef1f5SChao Yu if (!f2fs_may_extent_tree(inode)) 182a28ef1f5SChao Yu return; 183a28ef1f5SChao Yu 184a28ef1f5SChao Yu et = __grab_extent_tree(inode); 185a28ef1f5SChao Yu 186a28ef1f5SChao Yu if (!i_ext || le32_to_cpu(i_ext->len) < F2FS_MIN_EXTENT_LEN) 187a28ef1f5SChao Yu return; 188a28ef1f5SChao Yu 189a28ef1f5SChao Yu set_extent_info(&ei, le32_to_cpu(i_ext->fofs), 190a28ef1f5SChao Yu le32_to_cpu(i_ext->blk), le32_to_cpu(i_ext->len)); 191a28ef1f5SChao Yu 192a28ef1f5SChao Yu write_lock(&et->lock); 193a28ef1f5SChao Yu if (et->count) 194a28ef1f5SChao Yu goto out; 195a28ef1f5SChao Yu 196a6f78345SChao Yu en = __init_extent_tree(sbi, et, &ei); 197a28ef1f5SChao Yu if (en) { 198a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 199a28ef1f5SChao Yu list_add_tail(&en->list, &sbi->extent_list); 200a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 201a28ef1f5SChao Yu } 202a28ef1f5SChao Yu out: 203a28ef1f5SChao Yu write_unlock(&et->lock); 204a28ef1f5SChao Yu } 205a28ef1f5SChao Yu 206a28ef1f5SChao Yu static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs, 207a28ef1f5SChao Yu struct extent_info *ei) 208a28ef1f5SChao Yu { 209a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 210a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 211a28ef1f5SChao Yu struct extent_node *en; 212a28ef1f5SChao Yu bool ret = false; 213a28ef1f5SChao Yu 214a28ef1f5SChao Yu f2fs_bug_on(sbi, !et); 215a28ef1f5SChao Yu 216a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_start(inode, pgofs); 217a28ef1f5SChao Yu 218a28ef1f5SChao Yu read_lock(&et->lock); 219a28ef1f5SChao Yu 220a28ef1f5SChao Yu if (et->largest.fofs <= pgofs && 221a28ef1f5SChao Yu et->largest.fofs + et->largest.len > pgofs) { 222a28ef1f5SChao Yu *ei = et->largest; 223a28ef1f5SChao Yu ret = true; 22491c481ffSChao Yu stat_inc_largest_node_hit(sbi); 225a28ef1f5SChao Yu goto out; 226a28ef1f5SChao Yu } 227a28ef1f5SChao Yu 22891c481ffSChao Yu en = __lookup_extent_tree(sbi, et, pgofs); 229a28ef1f5SChao Yu if (en) { 230a28ef1f5SChao Yu *ei = en->ei; 231a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 232a28ef1f5SChao Yu if (!list_empty(&en->list)) 233a28ef1f5SChao Yu list_move_tail(&en->list, &sbi->extent_list); 234a28ef1f5SChao Yu et->cached_en = en; 235a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 236a28ef1f5SChao Yu ret = true; 237a28ef1f5SChao Yu } 238a28ef1f5SChao Yu out: 239727edac5SChao Yu stat_inc_total_hit(sbi); 240a28ef1f5SChao Yu read_unlock(&et->lock); 241a28ef1f5SChao Yu 242a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei); 243a28ef1f5SChao Yu return ret; 244a28ef1f5SChao Yu } 245a28ef1f5SChao Yu 2460f825ee6SFan Li 2470f825ee6SFan Li /* 2480f825ee6SFan Li * lookup extent at @fofs, if hit, return the extent 2490f825ee6SFan Li * if not, return NULL and 2500f825ee6SFan Li * @prev_ex: extent before fofs 2510f825ee6SFan Li * @next_ex: extent after fofs 2520f825ee6SFan Li * @insert_p: insert point for new extent at fofs 2530f825ee6SFan Li * in order to simpfy the insertion after. 2540f825ee6SFan Li * tree must stay unchanged between lookup and insertion. 2550f825ee6SFan Li */ 2560f825ee6SFan Li static struct extent_node *__lookup_extent_tree_ret(struct extent_tree *et, 25791c481ffSChao Yu unsigned int fofs, 25891c481ffSChao Yu struct extent_node **prev_ex, 2590f825ee6SFan Li struct extent_node **next_ex, 2600f825ee6SFan Li struct rb_node ***insert_p, 2610f825ee6SFan Li struct rb_node **insert_parent) 2620f825ee6SFan Li { 2630f825ee6SFan Li struct rb_node **pnode = &et->root.rb_node; 2640f825ee6SFan Li struct rb_node *parent = NULL, *tmp_node; 265dac2ddefSChao Yu struct extent_node *en = et->cached_en; 2660f825ee6SFan Li 267dac2ddefSChao Yu *insert_p = NULL; 268dac2ddefSChao Yu *insert_parent = NULL; 269dac2ddefSChao Yu *prev_ex = NULL; 270dac2ddefSChao Yu *next_ex = NULL; 271dac2ddefSChao Yu 272dac2ddefSChao Yu if (RB_EMPTY_ROOT(&et->root)) 273dac2ddefSChao Yu return NULL; 274dac2ddefSChao Yu 275dac2ddefSChao Yu if (en) { 276dac2ddefSChao Yu struct extent_info *cei = &en->ei; 2770f825ee6SFan Li 2780f825ee6SFan Li if (cei->fofs <= fofs && cei->fofs + cei->len > fofs) 279dac2ddefSChao Yu goto lookup_neighbors; 2800f825ee6SFan Li } 2810f825ee6SFan Li 2820f825ee6SFan Li while (*pnode) { 2830f825ee6SFan Li parent = *pnode; 2840f825ee6SFan Li en = rb_entry(*pnode, struct extent_node, rb_node); 2850f825ee6SFan Li 2860f825ee6SFan Li if (fofs < en->ei.fofs) 2870f825ee6SFan Li pnode = &(*pnode)->rb_left; 2880f825ee6SFan Li else if (fofs >= en->ei.fofs + en->ei.len) 2890f825ee6SFan Li pnode = &(*pnode)->rb_right; 2900f825ee6SFan Li else 291dac2ddefSChao Yu goto lookup_neighbors; 2920f825ee6SFan Li } 2930f825ee6SFan Li 2940f825ee6SFan Li *insert_p = pnode; 2950f825ee6SFan Li *insert_parent = parent; 2960f825ee6SFan Li 2970f825ee6SFan Li en = rb_entry(parent, struct extent_node, rb_node); 2980f825ee6SFan Li tmp_node = parent; 2990f825ee6SFan Li if (parent && fofs > en->ei.fofs) 3000f825ee6SFan Li tmp_node = rb_next(parent); 3010f825ee6SFan Li *next_ex = tmp_node ? 3020f825ee6SFan Li rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 3030f825ee6SFan Li 3040f825ee6SFan Li tmp_node = parent; 3050f825ee6SFan Li if (parent && fofs < en->ei.fofs) 3060f825ee6SFan Li tmp_node = rb_prev(parent); 3070f825ee6SFan Li *prev_ex = tmp_node ? 3080f825ee6SFan Li rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 3090f825ee6SFan Li return NULL; 310dac2ddefSChao Yu 311dac2ddefSChao Yu lookup_neighbors: 312dac2ddefSChao Yu if (fofs == en->ei.fofs) { 313dac2ddefSChao Yu /* lookup prev node for merging backward later */ 314dac2ddefSChao Yu tmp_node = rb_prev(&en->rb_node); 315dac2ddefSChao Yu *prev_ex = tmp_node ? 316dac2ddefSChao Yu rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 317dac2ddefSChao Yu } 318dac2ddefSChao Yu if (fofs == en->ei.fofs + en->ei.len - 1) { 319dac2ddefSChao Yu /* lookup next node for merging frontward later */ 320dac2ddefSChao Yu tmp_node = rb_next(&en->rb_node); 321dac2ddefSChao Yu *next_ex = tmp_node ? 322dac2ddefSChao Yu rb_entry(tmp_node, struct extent_node, rb_node) : NULL; 323dac2ddefSChao Yu } 324dac2ddefSChao Yu return en; 3250f825ee6SFan Li } 3260f825ee6SFan Li 327ef05e221SChao Yu static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi, 3280f825ee6SFan Li struct extent_tree *et, struct extent_info *ei, 3290f825ee6SFan Li struct extent_node **den, 3300f825ee6SFan Li struct extent_node *prev_ex, 331ef05e221SChao Yu struct extent_node *next_ex) 3320f825ee6SFan Li { 3330f825ee6SFan Li struct extent_node *en = NULL; 3340f825ee6SFan Li 3350f825ee6SFan Li if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) { 3360f825ee6SFan Li prev_ex->ei.len += ei->len; 3370f825ee6SFan Li ei = &prev_ex->ei; 3380f825ee6SFan Li en = prev_ex; 3390f825ee6SFan Li } 340ef05e221SChao Yu 3410f825ee6SFan Li if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) { 342ef05e221SChao Yu if (en) { 3430f825ee6SFan Li __detach_extent_node(sbi, et, prev_ex); 3440f825ee6SFan Li *den = prev_ex; 3450f825ee6SFan Li } 3460f825ee6SFan Li next_ex->ei.fofs = ei->fofs; 3470f825ee6SFan Li next_ex->ei.blk = ei->blk; 3480f825ee6SFan Li next_ex->ei.len += ei->len; 3490f825ee6SFan Li en = next_ex; 3500f825ee6SFan Li } 351ef05e221SChao Yu 352ef05e221SChao Yu if (en) { 353ef05e221SChao Yu if (en->ei.len > et->largest.len) 354ef05e221SChao Yu et->largest = en->ei; 355ef05e221SChao Yu et->cached_en = en; 356ef05e221SChao Yu } 357ef05e221SChao Yu return en; 358ef05e221SChao Yu } 359ef05e221SChao Yu 360ef05e221SChao Yu static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, 361ef05e221SChao Yu struct extent_tree *et, struct extent_info *ei, 362ef05e221SChao Yu struct rb_node **insert_p, 363ef05e221SChao Yu struct rb_node *insert_parent) 364ef05e221SChao Yu { 365ef05e221SChao Yu struct rb_node **p = &et->root.rb_node; 366ef05e221SChao Yu struct rb_node *parent = NULL; 367ef05e221SChao Yu struct extent_node *en = NULL; 3680f825ee6SFan Li 3690f825ee6SFan Li if (insert_p && insert_parent) { 3700f825ee6SFan Li parent = insert_parent; 3710f825ee6SFan Li p = insert_p; 3720f825ee6SFan Li goto do_insert; 3730f825ee6SFan Li } 3740f825ee6SFan Li 3750f825ee6SFan Li while (*p) { 3760f825ee6SFan Li parent = *p; 3770f825ee6SFan Li en = rb_entry(parent, struct extent_node, rb_node); 3780f825ee6SFan Li 3790f825ee6SFan Li if (ei->fofs < en->ei.fofs) 3800f825ee6SFan Li p = &(*p)->rb_left; 3810f825ee6SFan Li else if (ei->fofs >= en->ei.fofs + en->ei.len) 3820f825ee6SFan Li p = &(*p)->rb_right; 3830f825ee6SFan Li else 3840f825ee6SFan Li f2fs_bug_on(sbi, 1); 3850f825ee6SFan Li } 3860f825ee6SFan Li do_insert: 3870f825ee6SFan Li en = __attach_extent_node(sbi, et, ei, parent, p); 3880f825ee6SFan Li if (!en) 3890f825ee6SFan Li return NULL; 390ef05e221SChao Yu 3910f825ee6SFan Li if (en->ei.len > et->largest.len) 3920f825ee6SFan Li et->largest = en->ei; 3930f825ee6SFan Li et->cached_en = en; 3940f825ee6SFan Li return en; 3950f825ee6SFan Li } 3960f825ee6SFan Li 39719b2c30dSChao Yu unsigned int f2fs_update_extent_tree_range(struct inode *inode, 39819b2c30dSChao Yu pgoff_t fofs, block_t blkaddr, unsigned int len) 399a28ef1f5SChao Yu { 400a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 401a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 402a28ef1f5SChao Yu struct extent_node *en = NULL, *en1 = NULL, *en2 = NULL, *en3 = NULL; 40319b2c30dSChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 404a28ef1f5SChao Yu struct extent_info ei, dei, prev; 4050f825ee6SFan Li struct rb_node **insert_p = NULL, *insert_parent = NULL; 40619b2c30dSChao Yu unsigned int end = fofs + len; 40719b2c30dSChao Yu unsigned int pos = (unsigned int)fofs; 408a28ef1f5SChao Yu 409a28ef1f5SChao Yu if (!et) 410a28ef1f5SChao Yu return false; 411a28ef1f5SChao Yu 412*744288c7SChao Yu trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, len); 413*744288c7SChao Yu 414a28ef1f5SChao Yu write_lock(&et->lock); 415a28ef1f5SChao Yu 416a28ef1f5SChao Yu if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) { 417a28ef1f5SChao Yu write_unlock(&et->lock); 418a28ef1f5SChao Yu return false; 419a28ef1f5SChao Yu } 420a28ef1f5SChao Yu 421a28ef1f5SChao Yu prev = et->largest; 422a28ef1f5SChao Yu dei.len = 0; 423a28ef1f5SChao Yu 424a28ef1f5SChao Yu /* we do not guarantee that the largest extent is cached all the time */ 42554d71856SChao Yu __drop_largest_extent(inode, fofs); 426a28ef1f5SChao Yu 42719b2c30dSChao Yu /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ 42819b2c30dSChao Yu en = __lookup_extent_tree_ret(et, fofs, &prev_en, &next_en, 4290f825ee6SFan Li &insert_p, &insert_parent); 43019b2c30dSChao Yu if (!en) { 43119b2c30dSChao Yu if (next_en) { 43219b2c30dSChao Yu en = next_en; 43319b2c30dSChao Yu f2fs_bug_on(sbi, en->ei.fofs <= pos); 43419b2c30dSChao Yu pos = en->ei.fofs; 43519b2c30dSChao Yu } else { 43619b2c30dSChao Yu /* 43719b2c30dSChao Yu * skip searching in the tree since there is no 43819b2c30dSChao Yu * larger extent node in the cache. 43919b2c30dSChao Yu */ 440a28ef1f5SChao Yu goto update_extent; 44119b2c30dSChao Yu } 44219b2c30dSChao Yu } 44319b2c30dSChao Yu 44419b2c30dSChao Yu /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */ 44519b2c30dSChao Yu while (en) { 44619b2c30dSChao Yu struct rb_node *node; 44719b2c30dSChao Yu 44819b2c30dSChao Yu if (pos >= end) 44919b2c30dSChao Yu break; 450a28ef1f5SChao Yu 451a28ef1f5SChao Yu dei = en->ei; 45219b2c30dSChao Yu en1 = en2 = NULL; 45319b2c30dSChao Yu 45419b2c30dSChao Yu node = rb_next(&en->rb_node); 45519b2c30dSChao Yu 45619b2c30dSChao Yu /* 45719b2c30dSChao Yu * 2.1 there are four cases when we invalidate blkaddr in extent 45819b2c30dSChao Yu * node, |V: valid address, X: will be invalidated| 45919b2c30dSChao Yu */ 46019b2c30dSChao Yu /* case#1, invalidate right part of extent node |VVVVVXXXXX| */ 46119b2c30dSChao Yu if (pos > dei.fofs && end >= dei.fofs + dei.len) { 46219b2c30dSChao Yu en->ei.len = pos - dei.fofs; 46319b2c30dSChao Yu 46419b2c30dSChao Yu if (en->ei.len < F2FS_MIN_EXTENT_LEN) { 46519b2c30dSChao Yu __detach_extent_node(sbi, et, en); 46619b2c30dSChao Yu insert_p = NULL; 46719b2c30dSChao Yu insert_parent = NULL; 46819b2c30dSChao Yu goto update; 46919b2c30dSChao Yu } 47019b2c30dSChao Yu 47119b2c30dSChao Yu if (__is_extent_same(&dei, &et->largest)) 47219b2c30dSChao Yu et->largest = en->ei; 47319b2c30dSChao Yu goto next; 47419b2c30dSChao Yu } 47519b2c30dSChao Yu 47619b2c30dSChao Yu /* case#2, invalidate left part of extent node |XXXXXVVVVV| */ 47719b2c30dSChao Yu if (pos <= dei.fofs && end < dei.fofs + dei.len) { 47819b2c30dSChao Yu en->ei.fofs = end; 47919b2c30dSChao Yu en->ei.blk += end - dei.fofs; 48019b2c30dSChao Yu en->ei.len -= end - dei.fofs; 48119b2c30dSChao Yu 48219b2c30dSChao Yu if (en->ei.len < F2FS_MIN_EXTENT_LEN) { 48319b2c30dSChao Yu __detach_extent_node(sbi, et, en); 48419b2c30dSChao Yu insert_p = NULL; 48519b2c30dSChao Yu insert_parent = NULL; 48619b2c30dSChao Yu goto update; 48719b2c30dSChao Yu } 48819b2c30dSChao Yu 48919b2c30dSChao Yu if (__is_extent_same(&dei, &et->largest)) 49019b2c30dSChao Yu et->largest = en->ei; 49119b2c30dSChao Yu goto next; 49219b2c30dSChao Yu } 49319b2c30dSChao Yu 494a28ef1f5SChao Yu __detach_extent_node(sbi, et, en); 495a28ef1f5SChao Yu 49619b2c30dSChao Yu /* 49719b2c30dSChao Yu * if we remove node in rb-tree, our parent node pointer may 49819b2c30dSChao Yu * point the wrong place, discard them. 49919b2c30dSChao Yu */ 50019b2c30dSChao Yu insert_p = NULL; 50119b2c30dSChao Yu insert_parent = NULL; 50219b2c30dSChao Yu 50319b2c30dSChao Yu /* case#3, invalidate entire extent node |XXXXXXXXXX| */ 50419b2c30dSChao Yu if (pos <= dei.fofs && end >= dei.fofs + dei.len) { 50519b2c30dSChao Yu if (__is_extent_same(&dei, &et->largest)) 50619b2c30dSChao Yu et->largest.len = 0; 50719b2c30dSChao Yu goto update; 50819b2c30dSChao Yu } 50919b2c30dSChao Yu 51019b2c30dSChao Yu /* 51119b2c30dSChao Yu * case#4, invalidate data in the middle of extent node 51219b2c30dSChao Yu * |VVVXXXXVVV| 51319b2c30dSChao Yu */ 514a28ef1f5SChao Yu if (dei.len > F2FS_MIN_EXTENT_LEN) { 51519b2c30dSChao Yu unsigned int endofs; 51619b2c30dSChao Yu 517a28ef1f5SChao Yu /* insert left part of split extent into cache */ 51819b2c30dSChao Yu if (pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) { 519a28ef1f5SChao Yu set_extent_info(&ei, dei.fofs, dei.blk, 52019b2c30dSChao Yu pos - dei.fofs); 52119b2c30dSChao Yu en1 = __insert_extent_tree(sbi, et, &ei, 52219b2c30dSChao Yu NULL, NULL); 523a28ef1f5SChao Yu } 524a28ef1f5SChao Yu 525a28ef1f5SChao Yu /* insert right part of split extent into cache */ 52619b2c30dSChao Yu endofs = dei.fofs + dei.len; 52719b2c30dSChao Yu if (endofs - end >= F2FS_MIN_EXTENT_LEN) { 52819b2c30dSChao Yu set_extent_info(&ei, end, 52919b2c30dSChao Yu end - dei.fofs + dei.blk, 53019b2c30dSChao Yu endofs - end); 53119b2c30dSChao Yu en2 = __insert_extent_tree(sbi, et, &ei, 53219b2c30dSChao Yu NULL, NULL); 533a28ef1f5SChao Yu } 534a28ef1f5SChao Yu } 53519b2c30dSChao Yu update: 53619b2c30dSChao Yu /* 2.2 update in global extent list */ 53719b2c30dSChao Yu spin_lock(&sbi->extent_lock); 53819b2c30dSChao Yu if (en && !list_empty(&en->list)) 53919b2c30dSChao Yu list_del(&en->list); 54019b2c30dSChao Yu if (en1) 54119b2c30dSChao Yu list_add_tail(&en1->list, &sbi->extent_list); 54219b2c30dSChao Yu if (en2) 54319b2c30dSChao Yu list_add_tail(&en2->list, &sbi->extent_list); 54419b2c30dSChao Yu spin_unlock(&sbi->extent_lock); 54519b2c30dSChao Yu 54619b2c30dSChao Yu /* 2.3 release extent node */ 54719b2c30dSChao Yu if (en) 54819b2c30dSChao Yu kmem_cache_free(extent_node_slab, en); 54919b2c30dSChao Yu next: 55019b2c30dSChao Yu en = node ? rb_entry(node, struct extent_node, rb_node) : NULL; 55119b2c30dSChao Yu next_en = en; 55219b2c30dSChao Yu if (en) 55319b2c30dSChao Yu pos = en->ei.fofs; 55419b2c30dSChao Yu } 555a28ef1f5SChao Yu 556a28ef1f5SChao Yu update_extent: 557a28ef1f5SChao Yu /* 3. update extent in extent cache */ 558a28ef1f5SChao Yu if (blkaddr) { 55919b2c30dSChao Yu struct extent_node *den = NULL; 56019b2c30dSChao Yu 56119b2c30dSChao Yu set_extent_info(&ei, fofs, blkaddr, len); 562ef05e221SChao Yu en3 = __try_merge_extent_node(sbi, et, &ei, &den, 56319b2c30dSChao Yu prev_en, next_en); 564ef05e221SChao Yu if (!en3) 565ef05e221SChao Yu en3 = __insert_extent_tree(sbi, et, &ei, 566ef05e221SChao Yu insert_p, insert_parent); 567a28ef1f5SChao Yu 568a28ef1f5SChao Yu /* give up extent_cache, if split and small updates happen */ 569a28ef1f5SChao Yu if (dei.len >= 1 && 570a28ef1f5SChao Yu prev.len < F2FS_MIN_EXTENT_LEN && 571a28ef1f5SChao Yu et->largest.len < F2FS_MIN_EXTENT_LEN) { 572a28ef1f5SChao Yu et->largest.len = 0; 573a28ef1f5SChao Yu set_inode_flag(F2FS_I(inode), FI_NO_EXTENT); 574a28ef1f5SChao Yu } 575a28ef1f5SChao Yu 576a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 577a28ef1f5SChao Yu if (en3) { 578a28ef1f5SChao Yu if (list_empty(&en3->list)) 579a28ef1f5SChao Yu list_add_tail(&en3->list, &sbi->extent_list); 580a28ef1f5SChao Yu else 581a28ef1f5SChao Yu list_move_tail(&en3->list, &sbi->extent_list); 582a28ef1f5SChao Yu } 583a28ef1f5SChao Yu if (den && !list_empty(&den->list)) 584a28ef1f5SChao Yu list_del(&den->list); 585a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 586a28ef1f5SChao Yu 587a28ef1f5SChao Yu if (den) 588a28ef1f5SChao Yu kmem_cache_free(extent_node_slab, den); 58919b2c30dSChao Yu } 590a28ef1f5SChao Yu 591a28ef1f5SChao Yu if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) 592a28ef1f5SChao Yu __free_extent_tree(sbi, et, true); 593a28ef1f5SChao Yu 594a28ef1f5SChao Yu write_unlock(&et->lock); 595a28ef1f5SChao Yu 596a28ef1f5SChao Yu return !__is_extent_same(&prev, &et->largest); 597a28ef1f5SChao Yu } 598a28ef1f5SChao Yu 599a28ef1f5SChao Yu unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 600a28ef1f5SChao Yu { 601a28ef1f5SChao Yu struct extent_tree *treevec[EXT_TREE_VEC_SIZE]; 602a28ef1f5SChao Yu struct extent_node *en, *tmp; 603a28ef1f5SChao Yu unsigned long ino = F2FS_ROOT_INO(sbi); 604a28ef1f5SChao Yu struct radix_tree_root *root = &sbi->extent_tree_root; 605a28ef1f5SChao Yu unsigned int found; 606a28ef1f5SChao Yu unsigned int node_cnt = 0, tree_cnt = 0; 607a28ef1f5SChao Yu int remained; 608a28ef1f5SChao Yu 609a28ef1f5SChao Yu if (!test_opt(sbi, EXTENT_CACHE)) 610a28ef1f5SChao Yu return 0; 611a28ef1f5SChao Yu 612a28ef1f5SChao Yu if (!down_write_trylock(&sbi->extent_tree_lock)) 613a28ef1f5SChao Yu goto out; 614a28ef1f5SChao Yu 615a28ef1f5SChao Yu /* 1. remove unreferenced extent tree */ 616a28ef1f5SChao Yu while ((found = radix_tree_gang_lookup(root, 617a28ef1f5SChao Yu (void **)treevec, ino, EXT_TREE_VEC_SIZE))) { 618a28ef1f5SChao Yu unsigned i; 619a28ef1f5SChao Yu 620a28ef1f5SChao Yu ino = treevec[found - 1]->ino + 1; 621a28ef1f5SChao Yu for (i = 0; i < found; i++) { 622a28ef1f5SChao Yu struct extent_tree *et = treevec[i]; 623a28ef1f5SChao Yu 624a28ef1f5SChao Yu if (!atomic_read(&et->refcount)) { 625a28ef1f5SChao Yu write_lock(&et->lock); 626a28ef1f5SChao Yu node_cnt += __free_extent_tree(sbi, et, true); 627a28ef1f5SChao Yu write_unlock(&et->lock); 628a28ef1f5SChao Yu 629a28ef1f5SChao Yu radix_tree_delete(root, et->ino); 630a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 631a28ef1f5SChao Yu sbi->total_ext_tree--; 632a28ef1f5SChao Yu tree_cnt++; 633a28ef1f5SChao Yu 634a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 635a28ef1f5SChao Yu goto unlock_out; 636a28ef1f5SChao Yu } 637a28ef1f5SChao Yu } 638a28ef1f5SChao Yu } 639a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 640a28ef1f5SChao Yu 641a28ef1f5SChao Yu /* 2. remove LRU extent entries */ 642a28ef1f5SChao Yu if (!down_write_trylock(&sbi->extent_tree_lock)) 643a28ef1f5SChao Yu goto out; 644a28ef1f5SChao Yu 645a28ef1f5SChao Yu remained = nr_shrink - (node_cnt + tree_cnt); 646a28ef1f5SChao Yu 647a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 648a28ef1f5SChao Yu list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) { 649a28ef1f5SChao Yu if (!remained--) 650a28ef1f5SChao Yu break; 651a28ef1f5SChao Yu list_del_init(&en->list); 652a28ef1f5SChao Yu } 653a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 654a28ef1f5SChao Yu 655a28ef1f5SChao Yu while ((found = radix_tree_gang_lookup(root, 656a28ef1f5SChao Yu (void **)treevec, ino, EXT_TREE_VEC_SIZE))) { 657a28ef1f5SChao Yu unsigned i; 658a28ef1f5SChao Yu 659a28ef1f5SChao Yu ino = treevec[found - 1]->ino + 1; 660a28ef1f5SChao Yu for (i = 0; i < found; i++) { 661a28ef1f5SChao Yu struct extent_tree *et = treevec[i]; 662a28ef1f5SChao Yu 663a28ef1f5SChao Yu write_lock(&et->lock); 664a28ef1f5SChao Yu node_cnt += __free_extent_tree(sbi, et, false); 665a28ef1f5SChao Yu write_unlock(&et->lock); 666a28ef1f5SChao Yu 667a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 668a28ef1f5SChao Yu break; 669a28ef1f5SChao Yu } 670a28ef1f5SChao Yu } 671a28ef1f5SChao Yu unlock_out: 672a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 673a28ef1f5SChao Yu out: 674a28ef1f5SChao Yu trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt); 675a28ef1f5SChao Yu 676a28ef1f5SChao Yu return node_cnt + tree_cnt; 677a28ef1f5SChao Yu } 678a28ef1f5SChao Yu 679a28ef1f5SChao Yu unsigned int f2fs_destroy_extent_node(struct inode *inode) 680a28ef1f5SChao Yu { 681a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 682a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 683a28ef1f5SChao Yu unsigned int node_cnt = 0; 684a28ef1f5SChao Yu 685a28ef1f5SChao Yu if (!et) 686a28ef1f5SChao Yu return 0; 687a28ef1f5SChao Yu 688a28ef1f5SChao Yu write_lock(&et->lock); 689a28ef1f5SChao Yu node_cnt = __free_extent_tree(sbi, et, true); 690a28ef1f5SChao Yu write_unlock(&et->lock); 691a28ef1f5SChao Yu 692a28ef1f5SChao Yu return node_cnt; 693a28ef1f5SChao Yu } 694a28ef1f5SChao Yu 695a28ef1f5SChao Yu void f2fs_destroy_extent_tree(struct inode *inode) 696a28ef1f5SChao Yu { 697a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 698a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 699a28ef1f5SChao Yu unsigned int node_cnt = 0; 700a28ef1f5SChao Yu 701a28ef1f5SChao Yu if (!et) 702a28ef1f5SChao Yu return; 703a28ef1f5SChao Yu 704a28ef1f5SChao Yu if (inode->i_nlink && !is_bad_inode(inode) && et->count) { 705a28ef1f5SChao Yu atomic_dec(&et->refcount); 706a28ef1f5SChao Yu return; 707a28ef1f5SChao Yu } 708a28ef1f5SChao Yu 709a28ef1f5SChao Yu /* free all extent info belong to this extent tree */ 710a28ef1f5SChao Yu node_cnt = f2fs_destroy_extent_node(inode); 711a28ef1f5SChao Yu 712a28ef1f5SChao Yu /* delete extent tree entry in radix tree */ 713a28ef1f5SChao Yu down_write(&sbi->extent_tree_lock); 714a28ef1f5SChao Yu atomic_dec(&et->refcount); 715a28ef1f5SChao Yu f2fs_bug_on(sbi, atomic_read(&et->refcount) || et->count); 716a28ef1f5SChao Yu radix_tree_delete(&sbi->extent_tree_root, inode->i_ino); 717a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 718a28ef1f5SChao Yu sbi->total_ext_tree--; 719a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 720a28ef1f5SChao Yu 721a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = NULL; 722a28ef1f5SChao Yu 723a28ef1f5SChao Yu trace_f2fs_destroy_extent_tree(inode, node_cnt); 724a28ef1f5SChao Yu } 725a28ef1f5SChao Yu 726a28ef1f5SChao Yu bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs, 727a28ef1f5SChao Yu struct extent_info *ei) 728a28ef1f5SChao Yu { 729a28ef1f5SChao Yu if (!f2fs_may_extent_tree(inode)) 730a28ef1f5SChao Yu return false; 731a28ef1f5SChao Yu 732a28ef1f5SChao Yu return f2fs_lookup_extent_tree(inode, pgofs, ei); 733a28ef1f5SChao Yu } 734a28ef1f5SChao Yu 735a28ef1f5SChao Yu void f2fs_update_extent_cache(struct dnode_of_data *dn) 736a28ef1f5SChao Yu { 737a28ef1f5SChao Yu struct f2fs_inode_info *fi = F2FS_I(dn->inode); 738a28ef1f5SChao Yu pgoff_t fofs; 739a28ef1f5SChao Yu 740a28ef1f5SChao Yu if (!f2fs_may_extent_tree(dn->inode)) 741a28ef1f5SChao Yu return; 742a28ef1f5SChao Yu 743a28ef1f5SChao Yu f2fs_bug_on(F2FS_I_SB(dn->inode), dn->data_blkaddr == NEW_ADDR); 744a28ef1f5SChao Yu 74519b2c30dSChao Yu 746a28ef1f5SChao Yu fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) + 747a28ef1f5SChao Yu dn->ofs_in_node; 748a28ef1f5SChao Yu 74919b2c30dSChao Yu if (f2fs_update_extent_tree_range(dn->inode, fofs, dn->data_blkaddr, 1)) 75019b2c30dSChao Yu sync_inode_page(dn); 75119b2c30dSChao Yu } 75219b2c30dSChao Yu 75319b2c30dSChao Yu void f2fs_update_extent_cache_range(struct dnode_of_data *dn, 75419b2c30dSChao Yu pgoff_t fofs, block_t blkaddr, unsigned int len) 75519b2c30dSChao Yu 75619b2c30dSChao Yu { 75719b2c30dSChao Yu if (!f2fs_may_extent_tree(dn->inode)) 75819b2c30dSChao Yu return; 75919b2c30dSChao Yu 76019b2c30dSChao Yu if (f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len)) 761a28ef1f5SChao Yu sync_inode_page(dn); 762a28ef1f5SChao Yu } 763a28ef1f5SChao Yu 764a28ef1f5SChao Yu void init_extent_cache_info(struct f2fs_sb_info *sbi) 765a28ef1f5SChao Yu { 766a28ef1f5SChao Yu INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO); 767a28ef1f5SChao Yu init_rwsem(&sbi->extent_tree_lock); 768a28ef1f5SChao Yu INIT_LIST_HEAD(&sbi->extent_list); 769a28ef1f5SChao Yu spin_lock_init(&sbi->extent_lock); 770a28ef1f5SChao Yu sbi->total_ext_tree = 0; 771a28ef1f5SChao Yu atomic_set(&sbi->total_ext_node, 0); 772a28ef1f5SChao Yu } 773a28ef1f5SChao Yu 774a28ef1f5SChao Yu int __init create_extent_cache(void) 775a28ef1f5SChao Yu { 776a28ef1f5SChao Yu extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 777a28ef1f5SChao Yu sizeof(struct extent_tree)); 778a28ef1f5SChao Yu if (!extent_tree_slab) 779a28ef1f5SChao Yu return -ENOMEM; 780a28ef1f5SChao Yu extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 781a28ef1f5SChao Yu sizeof(struct extent_node)); 782a28ef1f5SChao Yu if (!extent_node_slab) { 783a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 784a28ef1f5SChao Yu return -ENOMEM; 785a28ef1f5SChao Yu } 786a28ef1f5SChao Yu return 0; 787a28ef1f5SChao Yu } 788a28ef1f5SChao Yu 789a28ef1f5SChao Yu void destroy_extent_cache(void) 790a28ef1f5SChao Yu { 791a28ef1f5SChao Yu kmem_cache_destroy(extent_node_slab); 792a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 793a28ef1f5SChao Yu } 794