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 84a28ef1f5SChao Yu static struct extent_node *__lookup_extent_tree(struct extent_tree *et, 85a28ef1f5SChao Yu unsigned int fofs) 86a28ef1f5SChao Yu { 87a28ef1f5SChao Yu struct rb_node *node = et->root.rb_node; 88a28ef1f5SChao Yu struct extent_node *en; 89a28ef1f5SChao Yu 90a28ef1f5SChao Yu if (et->cached_en) { 91a28ef1f5SChao Yu struct extent_info *cei = &et->cached_en->ei; 92a28ef1f5SChao Yu 93a28ef1f5SChao Yu if (cei->fofs <= fofs && cei->fofs + cei->len > fofs) 94a28ef1f5SChao Yu return et->cached_en; 95a28ef1f5SChao Yu } 96a28ef1f5SChao Yu 97a28ef1f5SChao Yu while (node) { 98a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 99a28ef1f5SChao Yu 100a28ef1f5SChao Yu if (fofs < en->ei.fofs) 101a28ef1f5SChao Yu node = node->rb_left; 102a28ef1f5SChao Yu else if (fofs >= en->ei.fofs + en->ei.len) 103a28ef1f5SChao Yu node = node->rb_right; 104a28ef1f5SChao Yu else 105a28ef1f5SChao Yu return en; 106a28ef1f5SChao Yu } 107a28ef1f5SChao Yu return NULL; 108a28ef1f5SChao Yu } 109a28ef1f5SChao Yu 110a28ef1f5SChao Yu static struct extent_node *__try_back_merge(struct f2fs_sb_info *sbi, 111a28ef1f5SChao Yu struct extent_tree *et, struct extent_node *en) 112a28ef1f5SChao Yu { 113a28ef1f5SChao Yu struct extent_node *prev; 114a28ef1f5SChao Yu struct rb_node *node; 115a28ef1f5SChao Yu 116a28ef1f5SChao Yu node = rb_prev(&en->rb_node); 117a28ef1f5SChao Yu if (!node) 118a28ef1f5SChao Yu return NULL; 119a28ef1f5SChao Yu 120a28ef1f5SChao Yu prev = rb_entry(node, struct extent_node, rb_node); 121a28ef1f5SChao Yu if (__is_back_mergeable(&en->ei, &prev->ei)) { 122a28ef1f5SChao Yu en->ei.fofs = prev->ei.fofs; 123a28ef1f5SChao Yu en->ei.blk = prev->ei.blk; 124a28ef1f5SChao Yu en->ei.len += prev->ei.len; 125a28ef1f5SChao Yu __detach_extent_node(sbi, et, prev); 126a28ef1f5SChao Yu return prev; 127a28ef1f5SChao Yu } 128a28ef1f5SChao Yu return NULL; 129a28ef1f5SChao Yu } 130a28ef1f5SChao Yu 131a28ef1f5SChao Yu static struct extent_node *__try_front_merge(struct f2fs_sb_info *sbi, 132a28ef1f5SChao Yu struct extent_tree *et, struct extent_node *en) 133a28ef1f5SChao Yu { 134a28ef1f5SChao Yu struct extent_node *next; 135a28ef1f5SChao Yu struct rb_node *node; 136a28ef1f5SChao Yu 137a28ef1f5SChao Yu node = rb_next(&en->rb_node); 138a28ef1f5SChao Yu if (!node) 139a28ef1f5SChao Yu return NULL; 140a28ef1f5SChao Yu 141a28ef1f5SChao Yu next = rb_entry(node, struct extent_node, rb_node); 142a28ef1f5SChao Yu if (__is_front_mergeable(&en->ei, &next->ei)) { 143a28ef1f5SChao Yu en->ei.len += next->ei.len; 144a28ef1f5SChao Yu __detach_extent_node(sbi, et, next); 145a28ef1f5SChao Yu return next; 146a28ef1f5SChao Yu } 147a28ef1f5SChao Yu return NULL; 148a28ef1f5SChao Yu } 149a28ef1f5SChao Yu 150a28ef1f5SChao Yu static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, 151a28ef1f5SChao Yu struct extent_tree *et, struct extent_info *ei, 152a28ef1f5SChao Yu struct extent_node **den) 153a28ef1f5SChao Yu { 154a28ef1f5SChao Yu struct rb_node **p = &et->root.rb_node; 155a28ef1f5SChao Yu struct rb_node *parent = NULL; 156a28ef1f5SChao Yu struct extent_node *en; 157a28ef1f5SChao Yu 158a28ef1f5SChao Yu while (*p) { 159a28ef1f5SChao Yu parent = *p; 160a28ef1f5SChao Yu en = rb_entry(parent, struct extent_node, rb_node); 161a28ef1f5SChao Yu 162a28ef1f5SChao Yu if (ei->fofs < en->ei.fofs) { 163a28ef1f5SChao Yu if (__is_front_mergeable(ei, &en->ei)) { 164a28ef1f5SChao Yu f2fs_bug_on(sbi, !den); 165a28ef1f5SChao Yu en->ei.fofs = ei->fofs; 166a28ef1f5SChao Yu en->ei.blk = ei->blk; 167a28ef1f5SChao Yu en->ei.len += ei->len; 168a28ef1f5SChao Yu *den = __try_back_merge(sbi, et, en); 169a28ef1f5SChao Yu goto update_out; 170a28ef1f5SChao Yu } 171a28ef1f5SChao Yu p = &(*p)->rb_left; 172a28ef1f5SChao Yu } else if (ei->fofs >= en->ei.fofs + en->ei.len) { 173a28ef1f5SChao Yu if (__is_back_mergeable(ei, &en->ei)) { 174a28ef1f5SChao Yu f2fs_bug_on(sbi, !den); 175a28ef1f5SChao Yu en->ei.len += ei->len; 176a28ef1f5SChao Yu *den = __try_front_merge(sbi, et, en); 177a28ef1f5SChao Yu goto update_out; 178a28ef1f5SChao Yu } 179a28ef1f5SChao Yu p = &(*p)->rb_right; 180a28ef1f5SChao Yu } else { 181a28ef1f5SChao Yu f2fs_bug_on(sbi, 1); 182a28ef1f5SChao Yu } 183a28ef1f5SChao Yu } 184a28ef1f5SChao Yu 185a28ef1f5SChao Yu en = __attach_extent_node(sbi, et, ei, parent, p); 186a28ef1f5SChao Yu if (!en) 187a28ef1f5SChao Yu return NULL; 188a28ef1f5SChao Yu update_out: 189a28ef1f5SChao Yu if (en->ei.len > et->largest.len) 190a28ef1f5SChao Yu et->largest = en->ei; 191a28ef1f5SChao Yu et->cached_en = en; 192a28ef1f5SChao Yu return en; 193a28ef1f5SChao Yu } 194a28ef1f5SChao Yu 195a28ef1f5SChao Yu static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, 196a28ef1f5SChao Yu struct extent_tree *et, bool free_all) 197a28ef1f5SChao Yu { 198a28ef1f5SChao Yu struct rb_node *node, *next; 199a28ef1f5SChao Yu struct extent_node *en; 200a28ef1f5SChao Yu unsigned int count = et->count; 201a28ef1f5SChao Yu 202a28ef1f5SChao Yu node = rb_first(&et->root); 203a28ef1f5SChao Yu while (node) { 204a28ef1f5SChao Yu next = rb_next(node); 205a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 206a28ef1f5SChao Yu 207a28ef1f5SChao Yu if (free_all) { 208a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 209a28ef1f5SChao Yu if (!list_empty(&en->list)) 210a28ef1f5SChao Yu list_del_init(&en->list); 211a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 212a28ef1f5SChao Yu } 213a28ef1f5SChao Yu 214a28ef1f5SChao Yu if (free_all || list_empty(&en->list)) { 215a28ef1f5SChao Yu __detach_extent_node(sbi, et, en); 216a28ef1f5SChao Yu kmem_cache_free(extent_node_slab, en); 217a28ef1f5SChao Yu } 218a28ef1f5SChao Yu node = next; 219a28ef1f5SChao Yu } 220a28ef1f5SChao Yu 221a28ef1f5SChao Yu return count - et->count; 222a28ef1f5SChao Yu } 223a28ef1f5SChao Yu 224a28ef1f5SChao Yu void f2fs_drop_largest_extent(struct inode *inode, pgoff_t fofs) 225a28ef1f5SChao Yu { 226a28ef1f5SChao Yu struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest; 227a28ef1f5SChao Yu 228a28ef1f5SChao Yu if (largest->fofs <= fofs && largest->fofs + largest->len > fofs) 229a28ef1f5SChao Yu largest->len = 0; 230a28ef1f5SChao Yu } 231a28ef1f5SChao Yu 232a28ef1f5SChao Yu void f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext) 233a28ef1f5SChao Yu { 234a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 235a28ef1f5SChao Yu struct extent_tree *et; 236a28ef1f5SChao Yu struct extent_node *en; 237a28ef1f5SChao Yu struct extent_info ei; 238a28ef1f5SChao Yu 239a28ef1f5SChao Yu if (!f2fs_may_extent_tree(inode)) 240a28ef1f5SChao Yu return; 241a28ef1f5SChao Yu 242a28ef1f5SChao Yu et = __grab_extent_tree(inode); 243a28ef1f5SChao Yu 244a28ef1f5SChao Yu if (!i_ext || le32_to_cpu(i_ext->len) < F2FS_MIN_EXTENT_LEN) 245a28ef1f5SChao Yu return; 246a28ef1f5SChao Yu 247a28ef1f5SChao Yu set_extent_info(&ei, le32_to_cpu(i_ext->fofs), 248a28ef1f5SChao Yu le32_to_cpu(i_ext->blk), le32_to_cpu(i_ext->len)); 249a28ef1f5SChao Yu 250a28ef1f5SChao Yu write_lock(&et->lock); 251a28ef1f5SChao Yu if (et->count) 252a28ef1f5SChao Yu goto out; 253a28ef1f5SChao Yu 254a28ef1f5SChao Yu en = __insert_extent_tree(sbi, et, &ei, NULL); 255a28ef1f5SChao Yu if (en) { 256a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 257a28ef1f5SChao Yu list_add_tail(&en->list, &sbi->extent_list); 258a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 259a28ef1f5SChao Yu } 260a28ef1f5SChao Yu out: 261a28ef1f5SChao Yu write_unlock(&et->lock); 262a28ef1f5SChao Yu } 263a28ef1f5SChao Yu 264a28ef1f5SChao Yu static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs, 265a28ef1f5SChao Yu struct extent_info *ei) 266a28ef1f5SChao Yu { 267a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 268a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 269a28ef1f5SChao Yu struct extent_node *en; 270a28ef1f5SChao Yu bool ret = false; 271a28ef1f5SChao Yu 272a28ef1f5SChao Yu f2fs_bug_on(sbi, !et); 273a28ef1f5SChao Yu 274a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_start(inode, pgofs); 275a28ef1f5SChao Yu 276a28ef1f5SChao Yu read_lock(&et->lock); 277a28ef1f5SChao Yu 278a28ef1f5SChao Yu if (et->largest.fofs <= pgofs && 279a28ef1f5SChao Yu et->largest.fofs + et->largest.len > pgofs) { 280a28ef1f5SChao Yu *ei = et->largest; 281a28ef1f5SChao Yu ret = true; 282*727edac5SChao Yu stat_inc_read_hit(sbi); 283a28ef1f5SChao Yu goto out; 284a28ef1f5SChao Yu } 285a28ef1f5SChao Yu 286a28ef1f5SChao Yu en = __lookup_extent_tree(et, pgofs); 287a28ef1f5SChao Yu if (en) { 288a28ef1f5SChao Yu *ei = en->ei; 289a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 290a28ef1f5SChao Yu if (!list_empty(&en->list)) 291a28ef1f5SChao Yu list_move_tail(&en->list, &sbi->extent_list); 292a28ef1f5SChao Yu et->cached_en = en; 293a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 294a28ef1f5SChao Yu ret = true; 295*727edac5SChao Yu stat_inc_read_hit(sbi); 296a28ef1f5SChao Yu } 297a28ef1f5SChao Yu out: 298*727edac5SChao Yu stat_inc_total_hit(sbi); 299a28ef1f5SChao Yu read_unlock(&et->lock); 300a28ef1f5SChao Yu 301a28ef1f5SChao Yu trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei); 302a28ef1f5SChao Yu return ret; 303a28ef1f5SChao Yu } 304a28ef1f5SChao Yu 305a28ef1f5SChao Yu /* return true, if on-disk extent should be updated */ 306a28ef1f5SChao Yu static bool f2fs_update_extent_tree(struct inode *inode, pgoff_t fofs, 307a28ef1f5SChao Yu block_t blkaddr) 308a28ef1f5SChao Yu { 309a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 310a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 311a28ef1f5SChao Yu struct extent_node *en = NULL, *en1 = NULL, *en2 = NULL, *en3 = NULL; 312a28ef1f5SChao Yu struct extent_node *den = NULL; 313a28ef1f5SChao Yu struct extent_info ei, dei, prev; 314a28ef1f5SChao Yu unsigned int endofs; 315a28ef1f5SChao Yu 316a28ef1f5SChao Yu if (!et) 317a28ef1f5SChao Yu return false; 318a28ef1f5SChao Yu 319a28ef1f5SChao Yu trace_f2fs_update_extent_tree(inode, fofs, blkaddr); 320a28ef1f5SChao Yu 321a28ef1f5SChao Yu write_lock(&et->lock); 322a28ef1f5SChao Yu 323a28ef1f5SChao Yu if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) { 324a28ef1f5SChao Yu write_unlock(&et->lock); 325a28ef1f5SChao Yu return false; 326a28ef1f5SChao Yu } 327a28ef1f5SChao Yu 328a28ef1f5SChao Yu prev = et->largest; 329a28ef1f5SChao Yu dei.len = 0; 330a28ef1f5SChao Yu 331a28ef1f5SChao Yu /* we do not guarantee that the largest extent is cached all the time */ 332a28ef1f5SChao Yu f2fs_drop_largest_extent(inode, fofs); 333a28ef1f5SChao Yu 334a28ef1f5SChao Yu /* 1. lookup and remove existing extent info in cache */ 335a28ef1f5SChao Yu en = __lookup_extent_tree(et, fofs); 336a28ef1f5SChao Yu if (!en) 337a28ef1f5SChao Yu goto update_extent; 338a28ef1f5SChao Yu 339a28ef1f5SChao Yu dei = en->ei; 340a28ef1f5SChao Yu __detach_extent_node(sbi, et, en); 341a28ef1f5SChao Yu 342a28ef1f5SChao Yu /* 2. if extent can be split more, split and insert the left part */ 343a28ef1f5SChao Yu if (dei.len > F2FS_MIN_EXTENT_LEN) { 344a28ef1f5SChao Yu /* insert left part of split extent into cache */ 345a28ef1f5SChao Yu if (fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN) { 346a28ef1f5SChao Yu set_extent_info(&ei, dei.fofs, dei.blk, 347a28ef1f5SChao Yu fofs - dei.fofs); 348a28ef1f5SChao Yu en1 = __insert_extent_tree(sbi, et, &ei, NULL); 349a28ef1f5SChao Yu } 350a28ef1f5SChao Yu 351a28ef1f5SChao Yu /* insert right part of split extent into cache */ 352a28ef1f5SChao Yu endofs = dei.fofs + dei.len - 1; 353a28ef1f5SChao Yu if (endofs - fofs >= F2FS_MIN_EXTENT_LEN) { 354a28ef1f5SChao Yu set_extent_info(&ei, fofs + 1, 355a28ef1f5SChao Yu fofs - dei.fofs + dei.blk + 1, endofs - fofs); 356a28ef1f5SChao Yu en2 = __insert_extent_tree(sbi, et, &ei, NULL); 357a28ef1f5SChao Yu } 358a28ef1f5SChao Yu } 359a28ef1f5SChao Yu 360a28ef1f5SChao Yu update_extent: 361a28ef1f5SChao Yu /* 3. update extent in extent cache */ 362a28ef1f5SChao Yu if (blkaddr) { 363a28ef1f5SChao Yu set_extent_info(&ei, fofs, blkaddr, 1); 364a28ef1f5SChao Yu en3 = __insert_extent_tree(sbi, et, &ei, &den); 365a28ef1f5SChao Yu 366a28ef1f5SChao Yu /* give up extent_cache, if split and small updates happen */ 367a28ef1f5SChao Yu if (dei.len >= 1 && 368a28ef1f5SChao Yu prev.len < F2FS_MIN_EXTENT_LEN && 369a28ef1f5SChao Yu et->largest.len < F2FS_MIN_EXTENT_LEN) { 370a28ef1f5SChao Yu et->largest.len = 0; 371a28ef1f5SChao Yu set_inode_flag(F2FS_I(inode), FI_NO_EXTENT); 372a28ef1f5SChao Yu } 373a28ef1f5SChao Yu } 374a28ef1f5SChao Yu 375a28ef1f5SChao Yu /* 4. update in global extent list */ 376a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 377a28ef1f5SChao Yu if (en && !list_empty(&en->list)) 378a28ef1f5SChao Yu list_del(&en->list); 379a28ef1f5SChao Yu /* 380a28ef1f5SChao Yu * en1 and en2 split from en, they will become more and more smaller 381a28ef1f5SChao Yu * fragments after splitting several times. So if the length is smaller 382a28ef1f5SChao Yu * than F2FS_MIN_EXTENT_LEN, we will not add them into extent tree. 383a28ef1f5SChao Yu */ 384a28ef1f5SChao Yu if (en1) 385a28ef1f5SChao Yu list_add_tail(&en1->list, &sbi->extent_list); 386a28ef1f5SChao Yu if (en2) 387a28ef1f5SChao Yu list_add_tail(&en2->list, &sbi->extent_list); 388a28ef1f5SChao Yu if (en3) { 389a28ef1f5SChao Yu if (list_empty(&en3->list)) 390a28ef1f5SChao Yu list_add_tail(&en3->list, &sbi->extent_list); 391a28ef1f5SChao Yu else 392a28ef1f5SChao Yu list_move_tail(&en3->list, &sbi->extent_list); 393a28ef1f5SChao Yu } 394a28ef1f5SChao Yu if (den && !list_empty(&den->list)) 395a28ef1f5SChao Yu list_del(&den->list); 396a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 397a28ef1f5SChao Yu 398a28ef1f5SChao Yu /* 5. release extent node */ 399a28ef1f5SChao Yu if (en) 400a28ef1f5SChao Yu kmem_cache_free(extent_node_slab, en); 401a28ef1f5SChao Yu if (den) 402a28ef1f5SChao Yu kmem_cache_free(extent_node_slab, den); 403a28ef1f5SChao Yu 404a28ef1f5SChao Yu if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) 405a28ef1f5SChao Yu __free_extent_tree(sbi, et, true); 406a28ef1f5SChao Yu 407a28ef1f5SChao Yu write_unlock(&et->lock); 408a28ef1f5SChao Yu 409a28ef1f5SChao Yu return !__is_extent_same(&prev, &et->largest); 410a28ef1f5SChao Yu } 411a28ef1f5SChao Yu 412a28ef1f5SChao Yu unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 413a28ef1f5SChao Yu { 414a28ef1f5SChao Yu struct extent_tree *treevec[EXT_TREE_VEC_SIZE]; 415a28ef1f5SChao Yu struct extent_node *en, *tmp; 416a28ef1f5SChao Yu unsigned long ino = F2FS_ROOT_INO(sbi); 417a28ef1f5SChao Yu struct radix_tree_root *root = &sbi->extent_tree_root; 418a28ef1f5SChao Yu unsigned int found; 419a28ef1f5SChao Yu unsigned int node_cnt = 0, tree_cnt = 0; 420a28ef1f5SChao Yu int remained; 421a28ef1f5SChao Yu 422a28ef1f5SChao Yu if (!test_opt(sbi, EXTENT_CACHE)) 423a28ef1f5SChao Yu return 0; 424a28ef1f5SChao Yu 425a28ef1f5SChao Yu if (!down_write_trylock(&sbi->extent_tree_lock)) 426a28ef1f5SChao Yu goto out; 427a28ef1f5SChao Yu 428a28ef1f5SChao Yu /* 1. remove unreferenced extent tree */ 429a28ef1f5SChao Yu while ((found = radix_tree_gang_lookup(root, 430a28ef1f5SChao Yu (void **)treevec, ino, EXT_TREE_VEC_SIZE))) { 431a28ef1f5SChao Yu unsigned i; 432a28ef1f5SChao Yu 433a28ef1f5SChao Yu ino = treevec[found - 1]->ino + 1; 434a28ef1f5SChao Yu for (i = 0; i < found; i++) { 435a28ef1f5SChao Yu struct extent_tree *et = treevec[i]; 436a28ef1f5SChao Yu 437a28ef1f5SChao Yu if (!atomic_read(&et->refcount)) { 438a28ef1f5SChao Yu write_lock(&et->lock); 439a28ef1f5SChao Yu node_cnt += __free_extent_tree(sbi, et, true); 440a28ef1f5SChao Yu write_unlock(&et->lock); 441a28ef1f5SChao Yu 442a28ef1f5SChao Yu radix_tree_delete(root, et->ino); 443a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 444a28ef1f5SChao Yu sbi->total_ext_tree--; 445a28ef1f5SChao Yu tree_cnt++; 446a28ef1f5SChao Yu 447a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 448a28ef1f5SChao Yu goto unlock_out; 449a28ef1f5SChao Yu } 450a28ef1f5SChao Yu } 451a28ef1f5SChao Yu } 452a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 453a28ef1f5SChao Yu 454a28ef1f5SChao Yu /* 2. remove LRU extent entries */ 455a28ef1f5SChao Yu if (!down_write_trylock(&sbi->extent_tree_lock)) 456a28ef1f5SChao Yu goto out; 457a28ef1f5SChao Yu 458a28ef1f5SChao Yu remained = nr_shrink - (node_cnt + tree_cnt); 459a28ef1f5SChao Yu 460a28ef1f5SChao Yu spin_lock(&sbi->extent_lock); 461a28ef1f5SChao Yu list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) { 462a28ef1f5SChao Yu if (!remained--) 463a28ef1f5SChao Yu break; 464a28ef1f5SChao Yu list_del_init(&en->list); 465a28ef1f5SChao Yu } 466a28ef1f5SChao Yu spin_unlock(&sbi->extent_lock); 467a28ef1f5SChao Yu 468a28ef1f5SChao Yu while ((found = radix_tree_gang_lookup(root, 469a28ef1f5SChao Yu (void **)treevec, ino, EXT_TREE_VEC_SIZE))) { 470a28ef1f5SChao Yu unsigned i; 471a28ef1f5SChao Yu 472a28ef1f5SChao Yu ino = treevec[found - 1]->ino + 1; 473a28ef1f5SChao Yu for (i = 0; i < found; i++) { 474a28ef1f5SChao Yu struct extent_tree *et = treevec[i]; 475a28ef1f5SChao Yu 476a28ef1f5SChao Yu write_lock(&et->lock); 477a28ef1f5SChao Yu node_cnt += __free_extent_tree(sbi, et, false); 478a28ef1f5SChao Yu write_unlock(&et->lock); 479a28ef1f5SChao Yu 480a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 481a28ef1f5SChao Yu break; 482a28ef1f5SChao Yu } 483a28ef1f5SChao Yu } 484a28ef1f5SChao Yu unlock_out: 485a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 486a28ef1f5SChao Yu out: 487a28ef1f5SChao Yu trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt); 488a28ef1f5SChao Yu 489a28ef1f5SChao Yu return node_cnt + tree_cnt; 490a28ef1f5SChao Yu } 491a28ef1f5SChao Yu 492a28ef1f5SChao Yu unsigned int f2fs_destroy_extent_node(struct inode *inode) 493a28ef1f5SChao Yu { 494a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 495a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 496a28ef1f5SChao Yu unsigned int node_cnt = 0; 497a28ef1f5SChao Yu 498a28ef1f5SChao Yu if (!et) 499a28ef1f5SChao Yu return 0; 500a28ef1f5SChao Yu 501a28ef1f5SChao Yu write_lock(&et->lock); 502a28ef1f5SChao Yu node_cnt = __free_extent_tree(sbi, et, true); 503a28ef1f5SChao Yu write_unlock(&et->lock); 504a28ef1f5SChao Yu 505a28ef1f5SChao Yu return node_cnt; 506a28ef1f5SChao Yu } 507a28ef1f5SChao Yu 508a28ef1f5SChao Yu void f2fs_destroy_extent_tree(struct inode *inode) 509a28ef1f5SChao Yu { 510a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 511a28ef1f5SChao Yu struct extent_tree *et = F2FS_I(inode)->extent_tree; 512a28ef1f5SChao Yu unsigned int node_cnt = 0; 513a28ef1f5SChao Yu 514a28ef1f5SChao Yu if (!et) 515a28ef1f5SChao Yu return; 516a28ef1f5SChao Yu 517a28ef1f5SChao Yu if (inode->i_nlink && !is_bad_inode(inode) && et->count) { 518a28ef1f5SChao Yu atomic_dec(&et->refcount); 519a28ef1f5SChao Yu return; 520a28ef1f5SChao Yu } 521a28ef1f5SChao Yu 522a28ef1f5SChao Yu /* free all extent info belong to this extent tree */ 523a28ef1f5SChao Yu node_cnt = f2fs_destroy_extent_node(inode); 524a28ef1f5SChao Yu 525a28ef1f5SChao Yu /* delete extent tree entry in radix tree */ 526a28ef1f5SChao Yu down_write(&sbi->extent_tree_lock); 527a28ef1f5SChao Yu atomic_dec(&et->refcount); 528a28ef1f5SChao Yu f2fs_bug_on(sbi, atomic_read(&et->refcount) || et->count); 529a28ef1f5SChao Yu radix_tree_delete(&sbi->extent_tree_root, inode->i_ino); 530a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 531a28ef1f5SChao Yu sbi->total_ext_tree--; 532a28ef1f5SChao Yu up_write(&sbi->extent_tree_lock); 533a28ef1f5SChao Yu 534a28ef1f5SChao Yu F2FS_I(inode)->extent_tree = NULL; 535a28ef1f5SChao Yu 536a28ef1f5SChao Yu trace_f2fs_destroy_extent_tree(inode, node_cnt); 537a28ef1f5SChao Yu } 538a28ef1f5SChao Yu 539a28ef1f5SChao Yu bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs, 540a28ef1f5SChao Yu struct extent_info *ei) 541a28ef1f5SChao Yu { 542a28ef1f5SChao Yu if (!f2fs_may_extent_tree(inode)) 543a28ef1f5SChao Yu return false; 544a28ef1f5SChao Yu 545a28ef1f5SChao Yu return f2fs_lookup_extent_tree(inode, pgofs, ei); 546a28ef1f5SChao Yu } 547a28ef1f5SChao Yu 548a28ef1f5SChao Yu void f2fs_update_extent_cache(struct dnode_of_data *dn) 549a28ef1f5SChao Yu { 550a28ef1f5SChao Yu struct f2fs_inode_info *fi = F2FS_I(dn->inode); 551a28ef1f5SChao Yu pgoff_t fofs; 552a28ef1f5SChao Yu 553a28ef1f5SChao Yu if (!f2fs_may_extent_tree(dn->inode)) 554a28ef1f5SChao Yu return; 555a28ef1f5SChao Yu 556a28ef1f5SChao Yu f2fs_bug_on(F2FS_I_SB(dn->inode), dn->data_blkaddr == NEW_ADDR); 557a28ef1f5SChao Yu 558a28ef1f5SChao Yu fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) + 559a28ef1f5SChao Yu dn->ofs_in_node; 560a28ef1f5SChao Yu 561a28ef1f5SChao Yu if (f2fs_update_extent_tree(dn->inode, fofs, dn->data_blkaddr)) 562a28ef1f5SChao Yu sync_inode_page(dn); 563a28ef1f5SChao Yu } 564a28ef1f5SChao Yu 565a28ef1f5SChao Yu void init_extent_cache_info(struct f2fs_sb_info *sbi) 566a28ef1f5SChao Yu { 567a28ef1f5SChao Yu INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO); 568a28ef1f5SChao Yu init_rwsem(&sbi->extent_tree_lock); 569a28ef1f5SChao Yu INIT_LIST_HEAD(&sbi->extent_list); 570a28ef1f5SChao Yu spin_lock_init(&sbi->extent_lock); 571a28ef1f5SChao Yu sbi->total_ext_tree = 0; 572a28ef1f5SChao Yu atomic_set(&sbi->total_ext_node, 0); 573a28ef1f5SChao Yu } 574a28ef1f5SChao Yu 575a28ef1f5SChao Yu int __init create_extent_cache(void) 576a28ef1f5SChao Yu { 577a28ef1f5SChao Yu extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 578a28ef1f5SChao Yu sizeof(struct extent_tree)); 579a28ef1f5SChao Yu if (!extent_tree_slab) 580a28ef1f5SChao Yu return -ENOMEM; 581a28ef1f5SChao Yu extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 582a28ef1f5SChao Yu sizeof(struct extent_node)); 583a28ef1f5SChao Yu if (!extent_node_slab) { 584a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 585a28ef1f5SChao Yu return -ENOMEM; 586a28ef1f5SChao Yu } 587a28ef1f5SChao Yu return 0; 588a28ef1f5SChao Yu } 589a28ef1f5SChao Yu 590a28ef1f5SChao Yu void destroy_extent_cache(void) 591a28ef1f5SChao Yu { 592a28ef1f5SChao Yu kmem_cache_destroy(extent_node_slab); 593a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 594a28ef1f5SChao Yu } 595