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> 971644dffSJaegeuk Kim * 1071644dffSJaegeuk Kim * block_age-based extent cache added by: 1171644dffSJaegeuk Kim * Copyright (c) 2022 xiaomi Co., Ltd. 1271644dffSJaegeuk Kim * http://www.xiaomi.com/ 13a28ef1f5SChao Yu */ 14a28ef1f5SChao Yu 15a28ef1f5SChao Yu #include <linux/fs.h> 16a28ef1f5SChao Yu #include <linux/f2fs_fs.h> 17a28ef1f5SChao Yu 18a28ef1f5SChao Yu #include "f2fs.h" 19a28ef1f5SChao Yu #include "node.h" 20a28ef1f5SChao Yu #include <trace/events/f2fs.h> 21a28ef1f5SChao Yu 223bac20a8SJaegeuk Kim static void __set_extent_info(struct extent_info *ei, 233bac20a8SJaegeuk Kim unsigned int fofs, unsigned int len, 24e7547dacSJaegeuk Kim block_t blk, bool keep_clen, 2571644dffSJaegeuk Kim unsigned long age, unsigned long last_blocks, 26e7547dacSJaegeuk Kim enum extent_type type) 273bac20a8SJaegeuk Kim { 283bac20a8SJaegeuk Kim ei->fofs = fofs; 293bac20a8SJaegeuk Kim ei->len = len; 303bac20a8SJaegeuk Kim 31e7547dacSJaegeuk Kim if (type == EX_READ) { 32e7547dacSJaegeuk Kim ei->blk = blk; 333bac20a8SJaegeuk Kim if (keep_clen) 343bac20a8SJaegeuk Kim return; 353bac20a8SJaegeuk Kim #ifdef CONFIG_F2FS_FS_COMPRESSION 363bac20a8SJaegeuk Kim ei->c_len = 0; 373bac20a8SJaegeuk Kim #endif 3871644dffSJaegeuk Kim } else if (type == EX_BLOCK_AGE) { 3971644dffSJaegeuk Kim ei->age = age; 4071644dffSJaegeuk Kim ei->last_blocks = last_blocks; 413bac20a8SJaegeuk Kim } 42e7547dacSJaegeuk Kim } 433bac20a8SJaegeuk Kim 44e7547dacSJaegeuk Kim static bool __may_read_extent_tree(struct inode *inode) 45e7547dacSJaegeuk Kim { 46e7547dacSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 47e7547dacSJaegeuk Kim 48e7547dacSJaegeuk Kim if (!test_opt(sbi, READ_EXTENT_CACHE)) 49e7547dacSJaegeuk Kim return false; 50e7547dacSJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) 51e7547dacSJaegeuk Kim return false; 52e7547dacSJaegeuk Kim if (is_inode_flag_set(inode, FI_COMPRESSED_FILE) && 53e7547dacSJaegeuk Kim !f2fs_sb_has_readonly(sbi)) 54e7547dacSJaegeuk Kim return false; 55e7547dacSJaegeuk Kim return S_ISREG(inode->i_mode); 56e7547dacSJaegeuk Kim } 57e7547dacSJaegeuk Kim 5871644dffSJaegeuk Kim static bool __may_age_extent_tree(struct inode *inode) 5971644dffSJaegeuk Kim { 6071644dffSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 6171644dffSJaegeuk Kim 6271644dffSJaegeuk Kim if (!test_opt(sbi, AGE_EXTENT_CACHE)) 6371644dffSJaegeuk Kim return false; 6471644dffSJaegeuk Kim /* don't cache block age info for cold file */ 6571644dffSJaegeuk Kim if (is_inode_flag_set(inode, FI_COMPRESSED_FILE)) 6671644dffSJaegeuk Kim return false; 6771644dffSJaegeuk Kim if (file_is_cold(inode)) 6871644dffSJaegeuk Kim return false; 6971644dffSJaegeuk Kim 7071644dffSJaegeuk Kim return S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode); 7171644dffSJaegeuk Kim } 7271644dffSJaegeuk Kim 7372840cccSJaegeuk Kim static bool __init_may_extent_tree(struct inode *inode, enum extent_type type) 7472840cccSJaegeuk Kim { 7572840cccSJaegeuk Kim if (type == EX_READ) 7672840cccSJaegeuk Kim return __may_read_extent_tree(inode); 7771644dffSJaegeuk Kim else if (type == EX_BLOCK_AGE) 7871644dffSJaegeuk Kim return __may_age_extent_tree(inode); 7972840cccSJaegeuk Kim return false; 8072840cccSJaegeuk Kim } 8172840cccSJaegeuk Kim 82e7547dacSJaegeuk Kim static bool __may_extent_tree(struct inode *inode, enum extent_type type) 833bac20a8SJaegeuk Kim { 843bac20a8SJaegeuk Kim /* 853bac20a8SJaegeuk Kim * for recovered files during mount do not create extents 863bac20a8SJaegeuk Kim * if shrinker is not registered. 873bac20a8SJaegeuk Kim */ 8872840cccSJaegeuk Kim if (list_empty(&F2FS_I_SB(inode)->s_list)) 893bac20a8SJaegeuk Kim return false; 903bac20a8SJaegeuk Kim 9172840cccSJaegeuk Kim return __init_may_extent_tree(inode, type); 923bac20a8SJaegeuk Kim } 933bac20a8SJaegeuk Kim 943bac20a8SJaegeuk Kim static void __try_update_largest_extent(struct extent_tree *et, 953bac20a8SJaegeuk Kim struct extent_node *en) 963bac20a8SJaegeuk Kim { 97e7547dacSJaegeuk Kim if (et->type != EX_READ) 98e7547dacSJaegeuk Kim return; 993bac20a8SJaegeuk Kim if (en->ei.len <= et->largest.len) 1003bac20a8SJaegeuk Kim return; 1013bac20a8SJaegeuk Kim 1023bac20a8SJaegeuk Kim et->largest = en->ei; 1033bac20a8SJaegeuk Kim et->largest_updated = true; 1043bac20a8SJaegeuk Kim } 1053bac20a8SJaegeuk Kim 1063bac20a8SJaegeuk Kim static bool __is_extent_mergeable(struct extent_info *back, 107e7547dacSJaegeuk Kim struct extent_info *front, enum extent_type type) 1083bac20a8SJaegeuk Kim { 109e7547dacSJaegeuk Kim if (type == EX_READ) { 1103bac20a8SJaegeuk Kim #ifdef CONFIG_F2FS_FS_COMPRESSION 1113bac20a8SJaegeuk Kim if (back->c_len && back->len != back->c_len) 1123bac20a8SJaegeuk Kim return false; 1133bac20a8SJaegeuk Kim if (front->c_len && front->len != front->c_len) 1143bac20a8SJaegeuk Kim return false; 1153bac20a8SJaegeuk Kim #endif 1163bac20a8SJaegeuk Kim return (back->fofs + back->len == front->fofs && 1173bac20a8SJaegeuk Kim back->blk + back->len == front->blk); 11871644dffSJaegeuk Kim } else if (type == EX_BLOCK_AGE) { 11971644dffSJaegeuk Kim return (back->fofs + back->len == front->fofs && 12071644dffSJaegeuk Kim abs(back->age - front->age) <= SAME_AGE_REGION && 12171644dffSJaegeuk Kim abs(back->last_blocks - front->last_blocks) <= 12271644dffSJaegeuk Kim SAME_AGE_REGION); 1233bac20a8SJaegeuk Kim } 124e7547dacSJaegeuk Kim return false; 125e7547dacSJaegeuk Kim } 1263bac20a8SJaegeuk Kim 1273bac20a8SJaegeuk Kim static bool __is_back_mergeable(struct extent_info *cur, 128e7547dacSJaegeuk Kim struct extent_info *back, enum extent_type type) 1293bac20a8SJaegeuk Kim { 130e7547dacSJaegeuk Kim return __is_extent_mergeable(back, cur, type); 1313bac20a8SJaegeuk Kim } 1323bac20a8SJaegeuk Kim 1333bac20a8SJaegeuk Kim static bool __is_front_mergeable(struct extent_info *cur, 134e7547dacSJaegeuk Kim struct extent_info *front, enum extent_type type) 1353bac20a8SJaegeuk Kim { 136e7547dacSJaegeuk Kim return __is_extent_mergeable(cur, front, type); 1373bac20a8SJaegeuk Kim } 1383bac20a8SJaegeuk Kim 13954c2258cSChao Yu static struct rb_entry *__lookup_rb_tree_fast(struct rb_entry *cached_re, 14054c2258cSChao Yu unsigned int ofs) 14154c2258cSChao Yu { 14254c2258cSChao Yu if (cached_re) { 14354c2258cSChao Yu if (cached_re->ofs <= ofs && 14454c2258cSChao Yu cached_re->ofs + cached_re->len > ofs) { 14554c2258cSChao Yu return cached_re; 14654c2258cSChao Yu } 14754c2258cSChao Yu } 14854c2258cSChao Yu return NULL; 14954c2258cSChao Yu } 15054c2258cSChao Yu 1514dada3fdSChao Yu static struct rb_entry *__lookup_rb_tree_slow(struct rb_root_cached *root, 15254c2258cSChao Yu unsigned int ofs) 15354c2258cSChao Yu { 1544dada3fdSChao Yu struct rb_node *node = root->rb_root.rb_node; 15554c2258cSChao Yu struct rb_entry *re; 15654c2258cSChao Yu 15754c2258cSChao Yu while (node) { 15854c2258cSChao Yu re = rb_entry(node, struct rb_entry, rb_node); 15954c2258cSChao Yu 16054c2258cSChao Yu if (ofs < re->ofs) 16154c2258cSChao Yu node = node->rb_left; 16254c2258cSChao Yu else if (ofs >= re->ofs + re->len) 16354c2258cSChao Yu node = node->rb_right; 16454c2258cSChao Yu else 16554c2258cSChao Yu return re; 16654c2258cSChao Yu } 16754c2258cSChao Yu return NULL; 16854c2258cSChao Yu } 16954c2258cSChao Yu 1704dada3fdSChao Yu struct rb_entry *f2fs_lookup_rb_tree(struct rb_root_cached *root, 17154c2258cSChao Yu struct rb_entry *cached_re, unsigned int ofs) 17254c2258cSChao Yu { 17354c2258cSChao Yu struct rb_entry *re; 17454c2258cSChao Yu 17554c2258cSChao Yu re = __lookup_rb_tree_fast(cached_re, ofs); 17654c2258cSChao Yu if (!re) 17754c2258cSChao Yu return __lookup_rb_tree_slow(root, ofs); 17854c2258cSChao Yu 17954c2258cSChao Yu return re; 18054c2258cSChao Yu } 18154c2258cSChao Yu 1822e9b2bb2SChao Yu struct rb_node **f2fs_lookup_rb_tree_ext(struct f2fs_sb_info *sbi, 1832e9b2bb2SChao Yu struct rb_root_cached *root, 1842e9b2bb2SChao Yu struct rb_node **parent, 1852e9b2bb2SChao Yu unsigned long long key, bool *leftmost) 1862e9b2bb2SChao Yu { 1872e9b2bb2SChao Yu struct rb_node **p = &root->rb_root.rb_node; 1882e9b2bb2SChao Yu struct rb_entry *re; 1892e9b2bb2SChao Yu 1902e9b2bb2SChao Yu while (*p) { 1912e9b2bb2SChao Yu *parent = *p; 1922e9b2bb2SChao Yu re = rb_entry(*parent, struct rb_entry, rb_node); 1932e9b2bb2SChao Yu 1942e9b2bb2SChao Yu if (key < re->key) { 1952e9b2bb2SChao Yu p = &(*p)->rb_left; 1962e9b2bb2SChao Yu } else { 1972e9b2bb2SChao Yu p = &(*p)->rb_right; 1982e9b2bb2SChao Yu *leftmost = false; 1992e9b2bb2SChao Yu } 2002e9b2bb2SChao Yu } 2012e9b2bb2SChao Yu 2022e9b2bb2SChao Yu return p; 2032e9b2bb2SChao Yu } 2042e9b2bb2SChao Yu 2054d57b86dSChao Yu struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi, 2064dada3fdSChao Yu struct rb_root_cached *root, 2074dada3fdSChao Yu struct rb_node **parent, 2084dada3fdSChao Yu unsigned int ofs, bool *leftmost) 20954c2258cSChao Yu { 2104dada3fdSChao Yu struct rb_node **p = &root->rb_root.rb_node; 21154c2258cSChao Yu struct rb_entry *re; 21254c2258cSChao Yu 21354c2258cSChao Yu while (*p) { 21454c2258cSChao Yu *parent = *p; 21554c2258cSChao Yu re = rb_entry(*parent, struct rb_entry, rb_node); 21654c2258cSChao Yu 2174dada3fdSChao Yu if (ofs < re->ofs) { 21854c2258cSChao Yu p = &(*p)->rb_left; 2194dada3fdSChao Yu } else if (ofs >= re->ofs + re->len) { 22054c2258cSChao Yu p = &(*p)->rb_right; 2214dada3fdSChao Yu *leftmost = false; 2224dada3fdSChao Yu } else { 22354c2258cSChao Yu f2fs_bug_on(sbi, 1); 22454c2258cSChao Yu } 2254dada3fdSChao Yu } 22654c2258cSChao Yu 22754c2258cSChao Yu return p; 22854c2258cSChao Yu } 22954c2258cSChao Yu 23054c2258cSChao Yu /* 23154c2258cSChao Yu * lookup rb entry in position of @ofs in rb-tree, 23254c2258cSChao Yu * if hit, return the entry, otherwise, return NULL 23354c2258cSChao Yu * @prev_ex: extent before ofs 23454c2258cSChao Yu * @next_ex: extent after ofs 23554c2258cSChao Yu * @insert_p: insert point for new extent at ofs 23654c2258cSChao Yu * in order to simpfy the insertion after. 23754c2258cSChao Yu * tree must stay unchanged between lookup and insertion. 23854c2258cSChao Yu */ 2394dada3fdSChao Yu struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root_cached *root, 24054c2258cSChao Yu struct rb_entry *cached_re, 24154c2258cSChao Yu unsigned int ofs, 24254c2258cSChao Yu struct rb_entry **prev_entry, 24354c2258cSChao Yu struct rb_entry **next_entry, 24454c2258cSChao Yu struct rb_node ***insert_p, 245004b6862SChao Yu struct rb_node **insert_parent, 2464dada3fdSChao Yu bool force, bool *leftmost) 24754c2258cSChao Yu { 2484dada3fdSChao Yu struct rb_node **pnode = &root->rb_root.rb_node; 24954c2258cSChao Yu struct rb_node *parent = NULL, *tmp_node; 25054c2258cSChao Yu struct rb_entry *re = cached_re; 25154c2258cSChao Yu 25254c2258cSChao Yu *insert_p = NULL; 25354c2258cSChao Yu *insert_parent = NULL; 25454c2258cSChao Yu *prev_entry = NULL; 25554c2258cSChao Yu *next_entry = NULL; 25654c2258cSChao Yu 2574dada3fdSChao Yu if (RB_EMPTY_ROOT(&root->rb_root)) 25854c2258cSChao Yu return NULL; 25954c2258cSChao Yu 26054c2258cSChao Yu if (re) { 26154c2258cSChao Yu if (re->ofs <= ofs && re->ofs + re->len > ofs) 26254c2258cSChao Yu goto lookup_neighbors; 26354c2258cSChao Yu } 26454c2258cSChao Yu 2654dada3fdSChao Yu if (leftmost) 2664dada3fdSChao Yu *leftmost = true; 2674dada3fdSChao Yu 26854c2258cSChao Yu while (*pnode) { 26954c2258cSChao Yu parent = *pnode; 27054c2258cSChao Yu re = rb_entry(*pnode, struct rb_entry, rb_node); 27154c2258cSChao Yu 2724dada3fdSChao Yu if (ofs < re->ofs) { 27354c2258cSChao Yu pnode = &(*pnode)->rb_left; 2744dada3fdSChao Yu } else if (ofs >= re->ofs + re->len) { 27554c2258cSChao Yu pnode = &(*pnode)->rb_right; 2764dada3fdSChao Yu if (leftmost) 2774dada3fdSChao Yu *leftmost = false; 2784dada3fdSChao Yu } else { 27954c2258cSChao Yu goto lookup_neighbors; 28054c2258cSChao Yu } 2814dada3fdSChao Yu } 28254c2258cSChao Yu 28354c2258cSChao Yu *insert_p = pnode; 28454c2258cSChao Yu *insert_parent = parent; 28554c2258cSChao Yu 28654c2258cSChao Yu re = rb_entry(parent, struct rb_entry, rb_node); 28754c2258cSChao Yu tmp_node = parent; 28854c2258cSChao Yu if (parent && ofs > re->ofs) 28954c2258cSChao Yu tmp_node = rb_next(parent); 29054c2258cSChao Yu *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 29154c2258cSChao Yu 29254c2258cSChao Yu tmp_node = parent; 29354c2258cSChao Yu if (parent && ofs < re->ofs) 29454c2258cSChao Yu tmp_node = rb_prev(parent); 29554c2258cSChao Yu *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 29654c2258cSChao Yu return NULL; 29754c2258cSChao Yu 29854c2258cSChao Yu lookup_neighbors: 299004b6862SChao Yu if (ofs == re->ofs || force) { 30054c2258cSChao Yu /* lookup prev node for merging backward later */ 30154c2258cSChao Yu tmp_node = rb_prev(&re->rb_node); 30254c2258cSChao Yu *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 30354c2258cSChao Yu } 304004b6862SChao Yu if (ofs == re->ofs + re->len - 1 || force) { 30554c2258cSChao Yu /* lookup next node for merging frontward later */ 30654c2258cSChao Yu tmp_node = rb_next(&re->rb_node); 30754c2258cSChao Yu *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node); 30854c2258cSChao Yu } 30954c2258cSChao Yu return re; 31054c2258cSChao Yu } 31154c2258cSChao Yu 3124d57b86dSChao Yu bool f2fs_check_rb_tree_consistence(struct f2fs_sb_info *sbi, 3132e9b2bb2SChao Yu struct rb_root_cached *root, bool check_key) 314df0f6b44SChao Yu { 315df0f6b44SChao Yu #ifdef CONFIG_F2FS_CHECK_FS 3164dada3fdSChao Yu struct rb_node *cur = rb_first_cached(root), *next; 317df0f6b44SChao Yu struct rb_entry *cur_re, *next_re; 318df0f6b44SChao Yu 319df0f6b44SChao Yu if (!cur) 320df0f6b44SChao Yu return true; 321df0f6b44SChao Yu 322df0f6b44SChao Yu while (cur) { 323df0f6b44SChao Yu next = rb_next(cur); 324df0f6b44SChao Yu if (!next) 325df0f6b44SChao Yu return true; 326df0f6b44SChao Yu 327df0f6b44SChao Yu cur_re = rb_entry(cur, struct rb_entry, rb_node); 328df0f6b44SChao Yu next_re = rb_entry(next, struct rb_entry, rb_node); 329df0f6b44SChao Yu 3302e9b2bb2SChao Yu if (check_key) { 3312e9b2bb2SChao Yu if (cur_re->key > next_re->key) { 3322e9b2bb2SChao Yu f2fs_info(sbi, "inconsistent rbtree, " 3332e9b2bb2SChao Yu "cur(%llu) next(%llu)", 3342e9b2bb2SChao Yu cur_re->key, next_re->key); 3352e9b2bb2SChao Yu return false; 3362e9b2bb2SChao Yu } 3372e9b2bb2SChao Yu goto next; 3382e9b2bb2SChao Yu } 3392e9b2bb2SChao Yu 340df0f6b44SChao Yu if (cur_re->ofs + cur_re->len > next_re->ofs) { 341dcbb4c10SJoe Perches f2fs_info(sbi, "inconsistent rbtree, cur(%u, %u) next(%u, %u)", 342df0f6b44SChao Yu cur_re->ofs, cur_re->len, 343df0f6b44SChao Yu next_re->ofs, next_re->len); 344df0f6b44SChao Yu return false; 345df0f6b44SChao Yu } 3462e9b2bb2SChao Yu next: 347df0f6b44SChao Yu cur = next; 348df0f6b44SChao Yu } 349df0f6b44SChao Yu #endif 350df0f6b44SChao Yu return true; 351df0f6b44SChao Yu } 352df0f6b44SChao Yu 353a28ef1f5SChao Yu static struct kmem_cache *extent_tree_slab; 354a28ef1f5SChao Yu static struct kmem_cache *extent_node_slab; 355a28ef1f5SChao Yu 356a28ef1f5SChao Yu static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi, 357a28ef1f5SChao Yu struct extent_tree *et, struct extent_info *ei, 3584dada3fdSChao Yu struct rb_node *parent, struct rb_node **p, 3594dada3fdSChao Yu bool leftmost) 360a28ef1f5SChao Yu { 361e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 362a28ef1f5SChao Yu struct extent_node *en; 363a28ef1f5SChao Yu 36432410577SChao Yu en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi); 365a28ef1f5SChao Yu if (!en) 366a28ef1f5SChao Yu return NULL; 367a28ef1f5SChao Yu 368a28ef1f5SChao Yu en->ei = *ei; 369a28ef1f5SChao Yu INIT_LIST_HEAD(&en->list); 370201ef5e0SHou Pengyang en->et = et; 371a28ef1f5SChao Yu 372a28ef1f5SChao Yu rb_link_node(&en->rb_node, parent, p); 3734dada3fdSChao Yu rb_insert_color_cached(&en->rb_node, &et->root, leftmost); 37468e35385SChao Yu atomic_inc(&et->node_cnt); 375e7547dacSJaegeuk Kim atomic_inc(&eti->total_ext_node); 376a28ef1f5SChao Yu return en; 377a28ef1f5SChao Yu } 378a28ef1f5SChao Yu 379a28ef1f5SChao Yu static void __detach_extent_node(struct f2fs_sb_info *sbi, 380a28ef1f5SChao Yu struct extent_tree *et, struct extent_node *en) 381a28ef1f5SChao Yu { 382e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 383e7547dacSJaegeuk Kim 3844dada3fdSChao Yu rb_erase_cached(&en->rb_node, &et->root); 38568e35385SChao Yu atomic_dec(&et->node_cnt); 386e7547dacSJaegeuk Kim atomic_dec(&eti->total_ext_node); 387a28ef1f5SChao Yu 388a28ef1f5SChao Yu if (et->cached_en == en) 389a28ef1f5SChao Yu et->cached_en = NULL; 390a03f01f2SHou Pengyang kmem_cache_free(extent_node_slab, en); 391a03f01f2SHou Pengyang } 392a03f01f2SHou Pengyang 393a03f01f2SHou Pengyang /* 394a03f01f2SHou Pengyang * Flow to release an extent_node: 395a03f01f2SHou Pengyang * 1. list_del_init 396a03f01f2SHou Pengyang * 2. __detach_extent_node 397a03f01f2SHou Pengyang * 3. kmem_cache_free. 398a03f01f2SHou Pengyang */ 399a03f01f2SHou Pengyang static void __release_extent_node(struct f2fs_sb_info *sbi, 400a03f01f2SHou Pengyang struct extent_tree *et, struct extent_node *en) 401a03f01f2SHou Pengyang { 402e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 403e7547dacSJaegeuk Kim 404e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 405201ef5e0SHou Pengyang f2fs_bug_on(sbi, list_empty(&en->list)); 406a03f01f2SHou Pengyang list_del_init(&en->list); 407e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 408a03f01f2SHou Pengyang 409a03f01f2SHou Pengyang __detach_extent_node(sbi, et, en); 410a28ef1f5SChao Yu } 411a28ef1f5SChao Yu 412e7547dacSJaegeuk Kim static struct extent_tree *__grab_extent_tree(struct inode *inode, 413e7547dacSJaegeuk Kim enum extent_type type) 414a28ef1f5SChao Yu { 415a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 416e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[type]; 417a28ef1f5SChao Yu struct extent_tree *et; 418a28ef1f5SChao Yu nid_t ino = inode->i_ino; 419a28ef1f5SChao Yu 420e7547dacSJaegeuk Kim mutex_lock(&eti->extent_tree_lock); 421e7547dacSJaegeuk Kim et = radix_tree_lookup(&eti->extent_tree_root, ino); 422a28ef1f5SChao Yu if (!et) { 42332410577SChao Yu et = f2fs_kmem_cache_alloc(extent_tree_slab, 42432410577SChao Yu GFP_NOFS, true, NULL); 425e7547dacSJaegeuk Kim f2fs_radix_tree_insert(&eti->extent_tree_root, ino, et); 426a28ef1f5SChao Yu memset(et, 0, sizeof(struct extent_tree)); 427a28ef1f5SChao Yu et->ino = ino; 428e7547dacSJaegeuk Kim et->type = type; 4294dada3fdSChao Yu et->root = RB_ROOT_CACHED; 430a28ef1f5SChao Yu et->cached_en = NULL; 431a28ef1f5SChao Yu rwlock_init(&et->lock); 432137d09f0SJaegeuk Kim INIT_LIST_HEAD(&et->list); 43368e35385SChao Yu atomic_set(&et->node_cnt, 0); 434e7547dacSJaegeuk Kim atomic_inc(&eti->total_ext_tree); 43574fd8d99SJaegeuk Kim } else { 436e7547dacSJaegeuk Kim atomic_dec(&eti->total_zombie_tree); 437137d09f0SJaegeuk Kim list_del_init(&et->list); 438a28ef1f5SChao Yu } 439e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 440a28ef1f5SChao Yu 441a28ef1f5SChao Yu /* never died until evict_inode */ 442e7547dacSJaegeuk Kim F2FS_I(inode)->extent_tree[type] = et; 443a28ef1f5SChao Yu 444a28ef1f5SChao Yu return et; 445a28ef1f5SChao Yu } 446a28ef1f5SChao Yu 447a28ef1f5SChao Yu static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, 448201ef5e0SHou Pengyang struct extent_tree *et) 449a28ef1f5SChao Yu { 450a28ef1f5SChao Yu struct rb_node *node, *next; 451a28ef1f5SChao Yu struct extent_node *en; 45268e35385SChao Yu unsigned int count = atomic_read(&et->node_cnt); 453a28ef1f5SChao Yu 4544dada3fdSChao Yu node = rb_first_cached(&et->root); 455a28ef1f5SChao Yu while (node) { 456a28ef1f5SChao Yu next = rb_next(node); 457a28ef1f5SChao Yu en = rb_entry(node, struct extent_node, rb_node); 458a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 459a28ef1f5SChao Yu node = next; 460a28ef1f5SChao Yu } 461a28ef1f5SChao Yu 46268e35385SChao Yu return count - atomic_read(&et->node_cnt); 463a28ef1f5SChao Yu } 464a28ef1f5SChao Yu 465b430f726SZhikang Zhang static void __drop_largest_extent(struct extent_tree *et, 46641a099deSFan Li pgoff_t fofs, unsigned int len) 467a28ef1f5SChao Yu { 468b430f726SZhikang Zhang if (fofs < et->largest.fofs + et->largest.len && 469b430f726SZhikang Zhang fofs + len > et->largest.fofs) { 470b430f726SZhikang Zhang et->largest.len = 0; 471b430f726SZhikang Zhang et->largest_updated = true; 472205b9822SJaegeuk Kim } 473a28ef1f5SChao Yu } 474a28ef1f5SChao Yu 47572840cccSJaegeuk Kim void f2fs_init_read_extent_tree(struct inode *inode, struct page *ipage) 476a28ef1f5SChao Yu { 477a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 47872840cccSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[EX_READ]; 47972840cccSJaegeuk Kim struct f2fs_extent *i_ext = &F2FS_INODE(ipage)->i_ext; 480a28ef1f5SChao Yu struct extent_tree *et; 481a28ef1f5SChao Yu struct extent_node *en; 482a28ef1f5SChao Yu struct extent_info ei; 483a28ef1f5SChao Yu 48472840cccSJaegeuk Kim if (!__may_extent_tree(inode, EX_READ)) { 485e7547dacSJaegeuk Kim /* drop largest read extent */ 48672840cccSJaegeuk Kim if (i_ext && i_ext->len) { 487a6d601f3SChao Yu f2fs_wait_on_page_writeback(ipage, NODE, true, true); 488ed3d1256SJaegeuk Kim i_ext->len = 0; 489a6d601f3SChao Yu set_page_dirty(ipage); 490ed3d1256SJaegeuk Kim } 491e7547dacSJaegeuk Kim goto out; 492ed3d1256SJaegeuk Kim } 493a28ef1f5SChao Yu 49472840cccSJaegeuk Kim et = __grab_extent_tree(inode, EX_READ); 495a28ef1f5SChao Yu 496ed3d1256SJaegeuk Kim if (!i_ext || !i_ext->len) 497e7547dacSJaegeuk Kim goto out; 498e7547dacSJaegeuk Kim 49912607c1bSJaegeuk Kim get_read_extent_info(&ei, i_ext); 500a28ef1f5SChao Yu 501a28ef1f5SChao Yu write_lock(&et->lock); 50268e35385SChao Yu if (atomic_read(&et->node_cnt)) 503e7547dacSJaegeuk Kim goto unlock_out; 504a28ef1f5SChao Yu 505749d543cSJaegeuk Kim en = __attach_extent_node(sbi, et, &ei, NULL, 506749d543cSJaegeuk Kim &et->root.rb_root.rb_node, true); 507a28ef1f5SChao Yu if (en) { 508749d543cSJaegeuk Kim et->largest = en->ei; 509749d543cSJaegeuk Kim et->cached_en = en; 510749d543cSJaegeuk Kim 511e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 512e7547dacSJaegeuk Kim list_add_tail(&en->list, &eti->extent_list); 513e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 514a28ef1f5SChao Yu } 515e7547dacSJaegeuk Kim unlock_out: 516a28ef1f5SChao Yu write_unlock(&et->lock); 517e7547dacSJaegeuk Kim out: 51872840cccSJaegeuk Kim if (!F2FS_I(inode)->extent_tree[EX_READ]) 519e7547dacSJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 520a28ef1f5SChao Yu } 521a28ef1f5SChao Yu 52271644dffSJaegeuk Kim void f2fs_init_age_extent_tree(struct inode *inode) 52371644dffSJaegeuk Kim { 52471644dffSJaegeuk Kim if (!__init_may_extent_tree(inode, EX_BLOCK_AGE)) 52571644dffSJaegeuk Kim return; 52671644dffSJaegeuk Kim __grab_extent_tree(inode, EX_BLOCK_AGE); 52771644dffSJaegeuk Kim } 52871644dffSJaegeuk Kim 52972840cccSJaegeuk Kim void f2fs_init_extent_tree(struct inode *inode) 530dad48e73SYunlei He { 531e7547dacSJaegeuk Kim /* initialize read cache */ 53272840cccSJaegeuk Kim if (__init_may_extent_tree(inode, EX_READ)) 53372840cccSJaegeuk Kim __grab_extent_tree(inode, EX_READ); 53471644dffSJaegeuk Kim 53571644dffSJaegeuk Kim /* initialize block age cache */ 53671644dffSJaegeuk Kim if (__init_may_extent_tree(inode, EX_BLOCK_AGE)) 53771644dffSJaegeuk Kim __grab_extent_tree(inode, EX_BLOCK_AGE); 538dad48e73SYunlei He } 539dad48e73SYunlei He 540e7547dacSJaegeuk Kim static bool __lookup_extent_tree(struct inode *inode, pgoff_t pgofs, 541e7547dacSJaegeuk Kim struct extent_info *ei, enum extent_type type) 542a28ef1f5SChao Yu { 543a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 544e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[type]; 545e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 546a28ef1f5SChao Yu struct extent_node *en; 547a28ef1f5SChao Yu bool ret = false; 548a28ef1f5SChao Yu 549a28ef1f5SChao Yu f2fs_bug_on(sbi, !et); 550a28ef1f5SChao Yu 551e7547dacSJaegeuk Kim trace_f2fs_lookup_extent_tree_start(inode, pgofs, type); 552a28ef1f5SChao Yu 553a28ef1f5SChao Yu read_lock(&et->lock); 554a28ef1f5SChao Yu 555e7547dacSJaegeuk Kim if (type == EX_READ && 556e7547dacSJaegeuk Kim et->largest.fofs <= pgofs && 557a28ef1f5SChao Yu et->largest.fofs + et->largest.len > pgofs) { 558a28ef1f5SChao Yu *ei = et->largest; 559a28ef1f5SChao Yu ret = true; 56091c481ffSChao Yu stat_inc_largest_node_hit(sbi); 561a28ef1f5SChao Yu goto out; 562a28ef1f5SChao Yu } 563a28ef1f5SChao Yu 5644d57b86dSChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root, 56554c2258cSChao Yu (struct rb_entry *)et->cached_en, pgofs); 56654c2258cSChao Yu if (!en) 56754c2258cSChao Yu goto out; 56854c2258cSChao Yu 56954c2258cSChao Yu if (en == et->cached_en) 570e7547dacSJaegeuk Kim stat_inc_cached_node_hit(sbi, type); 57154c2258cSChao Yu else 572e7547dacSJaegeuk Kim stat_inc_rbtree_node_hit(sbi, type); 57354c2258cSChao Yu 574a28ef1f5SChao Yu *ei = en->ei; 575e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 57642926744SJaegeuk Kim if (!list_empty(&en->list)) { 577e7547dacSJaegeuk Kim list_move_tail(&en->list, &eti->extent_list); 578a28ef1f5SChao Yu et->cached_en = en; 57942926744SJaegeuk Kim } 580e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 581a28ef1f5SChao Yu ret = true; 582a28ef1f5SChao Yu out: 583e7547dacSJaegeuk Kim stat_inc_total_hit(sbi, type); 584a28ef1f5SChao Yu read_unlock(&et->lock); 585a28ef1f5SChao Yu 586e7547dacSJaegeuk Kim if (type == EX_READ) 587e7547dacSJaegeuk Kim trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei); 58871644dffSJaegeuk Kim else if (type == EX_BLOCK_AGE) 58971644dffSJaegeuk Kim trace_f2fs_lookup_age_extent_tree_end(inode, pgofs, ei); 590a28ef1f5SChao Yu return ret; 591a28ef1f5SChao Yu } 592a28ef1f5SChao Yu 593b430f726SZhikang Zhang static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi, 5940f825ee6SFan Li struct extent_tree *et, struct extent_info *ei, 5950f825ee6SFan Li struct extent_node *prev_ex, 596ef05e221SChao Yu struct extent_node *next_ex) 5970f825ee6SFan Li { 598e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 5990f825ee6SFan Li struct extent_node *en = NULL; 6000f825ee6SFan Li 601e7547dacSJaegeuk Kim if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei, et->type)) { 6020f825ee6SFan Li prev_ex->ei.len += ei->len; 6030f825ee6SFan Li ei = &prev_ex->ei; 6040f825ee6SFan Li en = prev_ex; 6050f825ee6SFan Li } 606ef05e221SChao Yu 607e7547dacSJaegeuk Kim if (next_ex && __is_front_mergeable(ei, &next_ex->ei, et->type)) { 6080f825ee6SFan Li next_ex->ei.fofs = ei->fofs; 6090f825ee6SFan Li next_ex->ei.len += ei->len; 610e7547dacSJaegeuk Kim if (et->type == EX_READ) 611e7547dacSJaegeuk Kim next_ex->ei.blk = ei->blk; 6127855eba4SYunlei He if (en) 6137855eba4SYunlei He __release_extent_node(sbi, et, prev_ex); 6147855eba4SYunlei He 6150f825ee6SFan Li en = next_ex; 6160f825ee6SFan Li } 617ef05e221SChao Yu 61843a2fa18SJaegeuk Kim if (!en) 61943a2fa18SJaegeuk Kim return NULL; 62043a2fa18SJaegeuk Kim 621b430f726SZhikang Zhang __try_update_largest_extent(et, en); 62243a2fa18SJaegeuk Kim 623e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 62442926744SJaegeuk Kim if (!list_empty(&en->list)) { 625e7547dacSJaegeuk Kim list_move_tail(&en->list, &eti->extent_list); 62642926744SJaegeuk Kim et->cached_en = en; 62742926744SJaegeuk Kim } 628e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 629ef05e221SChao Yu return en; 630ef05e221SChao Yu } 631ef05e221SChao Yu 632b430f726SZhikang Zhang static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, 633ef05e221SChao Yu struct extent_tree *et, struct extent_info *ei, 634ef05e221SChao Yu struct rb_node **insert_p, 6354dada3fdSChao Yu struct rb_node *insert_parent, 6364dada3fdSChao Yu bool leftmost) 637ef05e221SChao Yu { 638e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 6398fe326cbSColin Ian King struct rb_node **p; 640ef05e221SChao Yu struct rb_node *parent = NULL; 641ef05e221SChao Yu struct extent_node *en = NULL; 6420f825ee6SFan Li 6430f825ee6SFan Li if (insert_p && insert_parent) { 6440f825ee6SFan Li parent = insert_parent; 6450f825ee6SFan Li p = insert_p; 6460f825ee6SFan Li goto do_insert; 6470f825ee6SFan Li } 6480f825ee6SFan Li 6494dada3fdSChao Yu leftmost = true; 6504dada3fdSChao Yu 6514dada3fdSChao Yu p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent, 6524dada3fdSChao Yu ei->fofs, &leftmost); 6530f825ee6SFan Li do_insert: 6544dada3fdSChao Yu en = __attach_extent_node(sbi, et, ei, parent, p, leftmost); 6550f825ee6SFan Li if (!en) 6560f825ee6SFan Li return NULL; 657ef05e221SChao Yu 658b430f726SZhikang Zhang __try_update_largest_extent(et, en); 65943a2fa18SJaegeuk Kim 66043a2fa18SJaegeuk Kim /* update in global extent list */ 661e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 662e7547dacSJaegeuk Kim list_add_tail(&en->list, &eti->extent_list); 66342926744SJaegeuk Kim et->cached_en = en; 664e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 6650f825ee6SFan Li return en; 6660f825ee6SFan Li } 6670f825ee6SFan Li 668e7547dacSJaegeuk Kim static void __update_extent_tree_range(struct inode *inode, 669e7547dacSJaegeuk Kim struct extent_info *tei, enum extent_type type) 670a28ef1f5SChao Yu { 671a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 672e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 6734d1fa815SFan Li struct extent_node *en = NULL, *en1 = NULL; 67419b2c30dSChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 675a28ef1f5SChao Yu struct extent_info ei, dei, prev; 6760f825ee6SFan Li struct rb_node **insert_p = NULL, *insert_parent = NULL; 677e7547dacSJaegeuk Kim unsigned int fofs = tei->fofs, len = tei->len; 67819b2c30dSChao Yu unsigned int end = fofs + len; 679b430f726SZhikang Zhang bool updated = false; 680f9aa52a8SChao Yu bool leftmost = false; 681a28ef1f5SChao Yu 682a28ef1f5SChao Yu if (!et) 683317e1300SChao Yu return; 684a28ef1f5SChao Yu 685e7547dacSJaegeuk Kim if (type == EX_READ) 686e7547dacSJaegeuk Kim trace_f2fs_update_read_extent_tree_range(inode, fofs, len, 687e7547dacSJaegeuk Kim tei->blk, 0); 68871644dffSJaegeuk Kim else if (type == EX_BLOCK_AGE) 68971644dffSJaegeuk Kim trace_f2fs_update_age_extent_tree_range(inode, fofs, len, 69071644dffSJaegeuk Kim tei->age, tei->last_blocks); 69171644dffSJaegeuk Kim 692a28ef1f5SChao Yu write_lock(&et->lock); 693a28ef1f5SChao Yu 694e7547dacSJaegeuk Kim if (type == EX_READ) { 69591942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) { 696a28ef1f5SChao Yu write_unlock(&et->lock); 697317e1300SChao Yu return; 698a28ef1f5SChao Yu } 699a28ef1f5SChao Yu 700a28ef1f5SChao Yu prev = et->largest; 701a28ef1f5SChao Yu dei.len = 0; 702a28ef1f5SChao Yu 7034d1fa815SFan Li /* 7044d1fa815SFan Li * drop largest extent before lookup, in case it's already 7054d1fa815SFan Li * been shrunk from extent tree 7064d1fa815SFan Li */ 707b430f726SZhikang Zhang __drop_largest_extent(et, fofs, len); 708e7547dacSJaegeuk Kim } 709a28ef1f5SChao Yu 71019b2c30dSChao Yu /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ 7114d57b86dSChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, 71254c2258cSChao Yu (struct rb_entry *)et->cached_en, fofs, 71354c2258cSChao Yu (struct rb_entry **)&prev_en, 71454c2258cSChao Yu (struct rb_entry **)&next_en, 7154dada3fdSChao Yu &insert_p, &insert_parent, false, 7164dada3fdSChao Yu &leftmost); 7174d1fa815SFan Li if (!en) 71819b2c30dSChao Yu en = next_en; 71919b2c30dSChao Yu 72019b2c30dSChao Yu /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */ 7214d1fa815SFan Li while (en && en->ei.fofs < end) { 7224d1fa815SFan Li unsigned int org_end; 7234d1fa815SFan Li int parts = 0; /* # of parts current extent split into */ 72419b2c30dSChao Yu 7254d1fa815SFan Li next_en = en1 = NULL; 726a28ef1f5SChao Yu 727a28ef1f5SChao Yu dei = en->ei; 7284d1fa815SFan Li org_end = dei.fofs + dei.len; 729e7547dacSJaegeuk Kim f2fs_bug_on(sbi, fofs >= org_end); 73019b2c30dSChao Yu 731e7547dacSJaegeuk Kim if (fofs > dei.fofs && (type != EX_READ || 732e7547dacSJaegeuk Kim fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) { 733e7547dacSJaegeuk Kim en->ei.len = fofs - en->ei.fofs; 7344d1fa815SFan Li prev_en = en; 7354d1fa815SFan Li parts = 1; 73619b2c30dSChao Yu } 73719b2c30dSChao Yu 738e7547dacSJaegeuk Kim if (end < org_end && (type != EX_READ || 739e7547dacSJaegeuk Kim org_end - end >= F2FS_MIN_EXTENT_LEN)) { 7404d1fa815SFan Li if (parts) { 7413bac20a8SJaegeuk Kim __set_extent_info(&ei, 7423bac20a8SJaegeuk Kim end, org_end - end, 743e7547dacSJaegeuk Kim end - dei.fofs + dei.blk, false, 74471644dffSJaegeuk Kim dei.age, dei.last_blocks, 745e7547dacSJaegeuk Kim type); 746b430f726SZhikang Zhang en1 = __insert_extent_tree(sbi, et, &ei, 7474dada3fdSChao Yu NULL, NULL, true); 7484d1fa815SFan Li next_en = en1; 7494d1fa815SFan Li } else { 7503bac20a8SJaegeuk Kim __set_extent_info(&en->ei, 7513bac20a8SJaegeuk Kim end, en->ei.len - (end - dei.fofs), 752e7547dacSJaegeuk Kim en->ei.blk + (end - dei.fofs), true, 75371644dffSJaegeuk Kim dei.age, dei.last_blocks, 754e7547dacSJaegeuk Kim type); 7554d1fa815SFan Li next_en = en; 7564d1fa815SFan Li } 7574d1fa815SFan Li parts++; 75819b2c30dSChao Yu } 75919b2c30dSChao Yu 7604d1fa815SFan Li if (!next_en) { 7614d1fa815SFan Li struct rb_node *node = rb_next(&en->rb_node); 7624d1fa815SFan Li 763ed0b5620SGeliang Tang next_en = rb_entry_safe(node, struct extent_node, 764ed0b5620SGeliang Tang rb_node); 7654d1fa815SFan Li } 7664d1fa815SFan Li 7674abd3f5aSChao Yu if (parts) 768b430f726SZhikang Zhang __try_update_largest_extent(et, en); 7694abd3f5aSChao Yu else 770a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 77119b2c30dSChao Yu 77219b2c30dSChao Yu /* 7734d1fa815SFan Li * if original extent is split into zero or two parts, extent 7744d1fa815SFan Li * tree has been altered by deletion or insertion, therefore 7754d1fa815SFan Li * invalidate pointers regard to tree. 77619b2c30dSChao Yu */ 7774d1fa815SFan Li if (parts != 1) { 77819b2c30dSChao Yu insert_p = NULL; 77919b2c30dSChao Yu insert_parent = NULL; 78019b2c30dSChao Yu } 7814d1fa815SFan Li en = next_en; 78219b2c30dSChao Yu } 783a28ef1f5SChao Yu 78471644dffSJaegeuk Kim if (type == EX_BLOCK_AGE) 78571644dffSJaegeuk Kim goto update_age_extent_cache; 78671644dffSJaegeuk Kim 787e7547dacSJaegeuk Kim /* 3. update extent in read extent cache */ 788e7547dacSJaegeuk Kim BUG_ON(type != EX_READ); 789e7547dacSJaegeuk Kim 790e7547dacSJaegeuk Kim if (tei->blk) { 79171644dffSJaegeuk Kim __set_extent_info(&ei, fofs, len, tei->blk, false, 79271644dffSJaegeuk Kim 0, 0, EX_READ); 793b430f726SZhikang Zhang if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 794b430f726SZhikang Zhang __insert_extent_tree(sbi, et, &ei, 7954dada3fdSChao Yu insert_p, insert_parent, leftmost); 796a28ef1f5SChao Yu 797a28ef1f5SChao Yu /* give up extent_cache, if split and small updates happen */ 798a28ef1f5SChao Yu if (dei.len >= 1 && 799a28ef1f5SChao Yu prev.len < F2FS_MIN_EXTENT_LEN && 800a28ef1f5SChao Yu et->largest.len < F2FS_MIN_EXTENT_LEN) { 801b430f726SZhikang Zhang et->largest.len = 0; 802b430f726SZhikang Zhang et->largest_updated = true; 80391942321SJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 804a28ef1f5SChao Yu } 80519b2c30dSChao Yu } 806a28ef1f5SChao Yu 80791942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) 808201ef5e0SHou Pengyang __free_extent_tree(sbi, et); 809a28ef1f5SChao Yu 810b430f726SZhikang Zhang if (et->largest_updated) { 811b430f726SZhikang Zhang et->largest_updated = false; 812b430f726SZhikang Zhang updated = true; 813b430f726SZhikang Zhang } 81471644dffSJaegeuk Kim goto out_read_extent_cache; 81571644dffSJaegeuk Kim update_age_extent_cache: 81671644dffSJaegeuk Kim if (!tei->last_blocks) 81771644dffSJaegeuk Kim goto out_read_extent_cache; 818b430f726SZhikang Zhang 81971644dffSJaegeuk Kim __set_extent_info(&ei, fofs, len, 0, false, 82071644dffSJaegeuk Kim tei->age, tei->last_blocks, EX_BLOCK_AGE); 82171644dffSJaegeuk Kim if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 82271644dffSJaegeuk Kim __insert_extent_tree(sbi, et, &ei, 82371644dffSJaegeuk Kim insert_p, insert_parent, leftmost); 82471644dffSJaegeuk Kim out_read_extent_cache: 825a28ef1f5SChao Yu write_unlock(&et->lock); 826b430f726SZhikang Zhang 827b430f726SZhikang Zhang if (updated) 828b430f726SZhikang Zhang f2fs_mark_inode_dirty_sync(inode, true); 829a28ef1f5SChao Yu } 830a28ef1f5SChao Yu 83194afd6d6SChao Yu #ifdef CONFIG_F2FS_FS_COMPRESSION 832e7547dacSJaegeuk Kim void f2fs_update_read_extent_tree_range_compressed(struct inode *inode, 83394afd6d6SChao Yu pgoff_t fofs, block_t blkaddr, unsigned int llen, 83494afd6d6SChao Yu unsigned int c_len) 83594afd6d6SChao Yu { 83694afd6d6SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 837e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ]; 83894afd6d6SChao Yu struct extent_node *en = NULL; 83994afd6d6SChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 84094afd6d6SChao Yu struct extent_info ei; 84194afd6d6SChao Yu struct rb_node **insert_p = NULL, *insert_parent = NULL; 84294afd6d6SChao Yu bool leftmost = false; 84394afd6d6SChao Yu 844e7547dacSJaegeuk Kim trace_f2fs_update_read_extent_tree_range(inode, fofs, llen, 845e7547dacSJaegeuk Kim blkaddr, c_len); 84694afd6d6SChao Yu 84794afd6d6SChao Yu /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */ 84894afd6d6SChao Yu if (is_inode_flag_set(inode, FI_NO_EXTENT)) 84994afd6d6SChao Yu return; 85094afd6d6SChao Yu 85194afd6d6SChao Yu write_lock(&et->lock); 85294afd6d6SChao Yu 85394afd6d6SChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, 85494afd6d6SChao Yu (struct rb_entry *)et->cached_en, fofs, 85594afd6d6SChao Yu (struct rb_entry **)&prev_en, 85694afd6d6SChao Yu (struct rb_entry **)&next_en, 85794afd6d6SChao Yu &insert_p, &insert_parent, false, 85894afd6d6SChao Yu &leftmost); 85994afd6d6SChao Yu if (en) 86094afd6d6SChao Yu goto unlock_out; 86194afd6d6SChao Yu 86271644dffSJaegeuk Kim __set_extent_info(&ei, fofs, llen, blkaddr, true, 0, 0, EX_READ); 86394afd6d6SChao Yu ei.c_len = c_len; 86494afd6d6SChao Yu 86594afd6d6SChao Yu if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 86694afd6d6SChao Yu __insert_extent_tree(sbi, et, &ei, 86794afd6d6SChao Yu insert_p, insert_parent, leftmost); 86894afd6d6SChao Yu unlock_out: 86994afd6d6SChao Yu write_unlock(&et->lock); 87094afd6d6SChao Yu } 87194afd6d6SChao Yu #endif 87294afd6d6SChao Yu 87371644dffSJaegeuk Kim static unsigned long long __calculate_block_age(unsigned long long new, 87471644dffSJaegeuk Kim unsigned long long old) 87571644dffSJaegeuk Kim { 87671644dffSJaegeuk Kim unsigned long long diff; 87771644dffSJaegeuk Kim 87871644dffSJaegeuk Kim diff = (new >= old) ? new - (new - old) : new + (old - new); 87971644dffSJaegeuk Kim 88071644dffSJaegeuk Kim return div_u64(diff * LAST_AGE_WEIGHT, 100); 88171644dffSJaegeuk Kim } 88271644dffSJaegeuk Kim 88371644dffSJaegeuk Kim /* This returns a new age and allocated blocks in ei */ 884ed272476SJaegeuk Kim static int __get_new_block_age(struct inode *inode, struct extent_info *ei, 885ed272476SJaegeuk Kim block_t blkaddr) 88671644dffSJaegeuk Kim { 88771644dffSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 88871644dffSJaegeuk Kim loff_t f_size = i_size_read(inode); 88971644dffSJaegeuk Kim unsigned long long cur_blocks = 89071644dffSJaegeuk Kim atomic64_read(&sbi->allocated_data_blocks); 891*22a341b4SJaegeuk Kim struct extent_info tei = *ei; /* only fofs and len are valid */ 89271644dffSJaegeuk Kim 89371644dffSJaegeuk Kim /* 89471644dffSJaegeuk Kim * When I/O is not aligned to a PAGE_SIZE, update will happen to the last 89571644dffSJaegeuk Kim * file block even in seq write. So don't record age for newly last file 89671644dffSJaegeuk Kim * block here. 89771644dffSJaegeuk Kim */ 89871644dffSJaegeuk Kim if ((f_size >> PAGE_SHIFT) == ei->fofs && f_size & (PAGE_SIZE - 1) && 899ed272476SJaegeuk Kim blkaddr == NEW_ADDR) 90071644dffSJaegeuk Kim return -EINVAL; 90171644dffSJaegeuk Kim 902*22a341b4SJaegeuk Kim if (__lookup_extent_tree(inode, ei->fofs, &tei, EX_BLOCK_AGE)) { 90371644dffSJaegeuk Kim unsigned long long cur_age; 90471644dffSJaegeuk Kim 905*22a341b4SJaegeuk Kim if (cur_blocks >= tei.last_blocks) 906*22a341b4SJaegeuk Kim cur_age = cur_blocks - tei.last_blocks; 90771644dffSJaegeuk Kim else 90871644dffSJaegeuk Kim /* allocated_data_blocks overflow */ 909*22a341b4SJaegeuk Kim cur_age = ULLONG_MAX - tei.last_blocks + cur_blocks; 91071644dffSJaegeuk Kim 911*22a341b4SJaegeuk Kim if (tei.age) 912*22a341b4SJaegeuk Kim ei->age = __calculate_block_age(cur_age, tei.age); 91371644dffSJaegeuk Kim else 91471644dffSJaegeuk Kim ei->age = cur_age; 91571644dffSJaegeuk Kim ei->last_blocks = cur_blocks; 91671644dffSJaegeuk Kim WARN_ON(ei->age > cur_blocks); 91771644dffSJaegeuk Kim return 0; 91871644dffSJaegeuk Kim } 91971644dffSJaegeuk Kim 920ed272476SJaegeuk Kim f2fs_bug_on(sbi, blkaddr == NULL_ADDR); 92171644dffSJaegeuk Kim 92271644dffSJaegeuk Kim /* the data block was allocated for the first time */ 923ed272476SJaegeuk Kim if (blkaddr == NEW_ADDR) 92471644dffSJaegeuk Kim goto out; 92571644dffSJaegeuk Kim 926ed272476SJaegeuk Kim if (__is_valid_data_blkaddr(blkaddr) && 927ed272476SJaegeuk Kim !f2fs_is_valid_blkaddr(sbi, blkaddr, DATA_GENERIC_ENHANCE)) { 92871644dffSJaegeuk Kim f2fs_bug_on(sbi, 1); 92971644dffSJaegeuk Kim return -EINVAL; 93071644dffSJaegeuk Kim } 93171644dffSJaegeuk Kim out: 93271644dffSJaegeuk Kim /* 93371644dffSJaegeuk Kim * init block age with zero, this can happen when the block age extent 93471644dffSJaegeuk Kim * was reclaimed due to memory constraint or system reboot 93571644dffSJaegeuk Kim */ 93671644dffSJaegeuk Kim ei->age = 0; 93771644dffSJaegeuk Kim ei->last_blocks = cur_blocks; 93871644dffSJaegeuk Kim return 0; 93971644dffSJaegeuk Kim } 94071644dffSJaegeuk Kim 941e7547dacSJaegeuk Kim static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type) 942a28ef1f5SChao Yu { 943fe59109aSJaegeuk Kim struct extent_info ei = {}; 944e7547dacSJaegeuk Kim 945e7547dacSJaegeuk Kim if (!__may_extent_tree(dn->inode, type)) 946e7547dacSJaegeuk Kim return; 947e7547dacSJaegeuk Kim 948e7547dacSJaegeuk Kim ei.fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) + 949e7547dacSJaegeuk Kim dn->ofs_in_node; 950e7547dacSJaegeuk Kim ei.len = 1; 951e7547dacSJaegeuk Kim 952e7547dacSJaegeuk Kim if (type == EX_READ) { 953e7547dacSJaegeuk Kim if (dn->data_blkaddr == NEW_ADDR) 954e7547dacSJaegeuk Kim ei.blk = NULL_ADDR; 955e7547dacSJaegeuk Kim else 956e7547dacSJaegeuk Kim ei.blk = dn->data_blkaddr; 95771644dffSJaegeuk Kim } else if (type == EX_BLOCK_AGE) { 958ed272476SJaegeuk Kim if (__get_new_block_age(dn->inode, &ei, dn->data_blkaddr)) 95971644dffSJaegeuk Kim return; 960e7547dacSJaegeuk Kim } 961e7547dacSJaegeuk Kim __update_extent_tree_range(dn->inode, &ei, type); 962e7547dacSJaegeuk Kim } 963e7547dacSJaegeuk Kim 964e7547dacSJaegeuk Kim static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink, 965e7547dacSJaegeuk Kim enum extent_type type) 966e7547dacSJaegeuk Kim { 967e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[type]; 968137d09f0SJaegeuk Kim struct extent_tree *et, *next; 969201ef5e0SHou Pengyang struct extent_node *en; 970a28ef1f5SChao Yu unsigned int node_cnt = 0, tree_cnt = 0; 971a28ef1f5SChao Yu int remained; 972a28ef1f5SChao Yu 973e7547dacSJaegeuk Kim if (!atomic_read(&eti->total_zombie_tree)) 97474fd8d99SJaegeuk Kim goto free_node; 97574fd8d99SJaegeuk Kim 976e7547dacSJaegeuk Kim if (!mutex_trylock(&eti->extent_tree_lock)) 977a28ef1f5SChao Yu goto out; 978a28ef1f5SChao Yu 979a28ef1f5SChao Yu /* 1. remove unreferenced extent tree */ 980e7547dacSJaegeuk Kim list_for_each_entry_safe(et, next, &eti->zombie_list, list) { 9819b72a388SChao Yu if (atomic_read(&et->node_cnt)) { 982a28ef1f5SChao Yu write_lock(&et->lock); 983201ef5e0SHou Pengyang node_cnt += __free_extent_tree(sbi, et); 984a28ef1f5SChao Yu write_unlock(&et->lock); 9859b72a388SChao Yu } 986201ef5e0SHou Pengyang f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 987137d09f0SJaegeuk Kim list_del_init(&et->list); 988e7547dacSJaegeuk Kim radix_tree_delete(&eti->extent_tree_root, et->ino); 989a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 990e7547dacSJaegeuk Kim atomic_dec(&eti->total_ext_tree); 991e7547dacSJaegeuk Kim atomic_dec(&eti->total_zombie_tree); 992a28ef1f5SChao Yu tree_cnt++; 993a28ef1f5SChao Yu 994a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 995a28ef1f5SChao Yu goto unlock_out; 9966fe2bc95SJaegeuk Kim cond_resched(); 997a28ef1f5SChao Yu } 998e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 999a28ef1f5SChao Yu 100074fd8d99SJaegeuk Kim free_node: 1001a28ef1f5SChao Yu /* 2. remove LRU extent entries */ 1002e7547dacSJaegeuk Kim if (!mutex_trylock(&eti->extent_tree_lock)) 1003a28ef1f5SChao Yu goto out; 1004a28ef1f5SChao Yu 1005a28ef1f5SChao Yu remained = nr_shrink - (node_cnt + tree_cnt); 1006a28ef1f5SChao Yu 1007e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 1008201ef5e0SHou Pengyang for (; remained > 0; remained--) { 1009e7547dacSJaegeuk Kim if (list_empty(&eti->extent_list)) 1010a28ef1f5SChao Yu break; 1011e7547dacSJaegeuk Kim en = list_first_entry(&eti->extent_list, 1012201ef5e0SHou Pengyang struct extent_node, list); 1013201ef5e0SHou Pengyang et = en->et; 1014201ef5e0SHou Pengyang if (!write_trylock(&et->lock)) { 1015201ef5e0SHou Pengyang /* refresh this extent node's position in extent list */ 1016e7547dacSJaegeuk Kim list_move_tail(&en->list, &eti->extent_list); 1017201ef5e0SHou Pengyang continue; 1018201ef5e0SHou Pengyang } 1019201ef5e0SHou Pengyang 1020a28ef1f5SChao Yu list_del_init(&en->list); 1021e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 1022201ef5e0SHou Pengyang 1023201ef5e0SHou Pengyang __detach_extent_node(sbi, et, en); 1024201ef5e0SHou Pengyang 1025201ef5e0SHou Pengyang write_unlock(&et->lock); 1026201ef5e0SHou Pengyang node_cnt++; 1027e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 1028a28ef1f5SChao Yu } 1029e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 1030a28ef1f5SChao Yu 1031a28ef1f5SChao Yu unlock_out: 1032e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1033a28ef1f5SChao Yu out: 1034e7547dacSJaegeuk Kim trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type); 1035a28ef1f5SChao Yu 1036a28ef1f5SChao Yu return node_cnt + tree_cnt; 1037a28ef1f5SChao Yu } 1038a28ef1f5SChao Yu 1039e7547dacSJaegeuk Kim /* read extent cache operations */ 1040e7547dacSJaegeuk Kim bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs, 1041e7547dacSJaegeuk Kim struct extent_info *ei) 1042e7547dacSJaegeuk Kim { 1043e7547dacSJaegeuk Kim if (!__may_extent_tree(inode, EX_READ)) 1044e7547dacSJaegeuk Kim return false; 1045e7547dacSJaegeuk Kim 1046e7547dacSJaegeuk Kim return __lookup_extent_tree(inode, pgofs, ei, EX_READ); 1047e7547dacSJaegeuk Kim } 1048e7547dacSJaegeuk Kim 1049e7547dacSJaegeuk Kim void f2fs_update_read_extent_cache(struct dnode_of_data *dn) 1050e7547dacSJaegeuk Kim { 1051e7547dacSJaegeuk Kim return __update_extent_cache(dn, EX_READ); 1052e7547dacSJaegeuk Kim } 1053e7547dacSJaegeuk Kim 1054e7547dacSJaegeuk Kim void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn, 1055e7547dacSJaegeuk Kim pgoff_t fofs, block_t blkaddr, unsigned int len) 1056e7547dacSJaegeuk Kim { 1057e7547dacSJaegeuk Kim struct extent_info ei = { 1058e7547dacSJaegeuk Kim .fofs = fofs, 1059e7547dacSJaegeuk Kim .len = len, 1060e7547dacSJaegeuk Kim .blk = blkaddr, 1061e7547dacSJaegeuk Kim }; 1062e7547dacSJaegeuk Kim 1063e7547dacSJaegeuk Kim if (!__may_extent_tree(dn->inode, EX_READ)) 1064e7547dacSJaegeuk Kim return; 1065e7547dacSJaegeuk Kim 1066e7547dacSJaegeuk Kim __update_extent_tree_range(dn->inode, &ei, EX_READ); 1067e7547dacSJaegeuk Kim } 1068e7547dacSJaegeuk Kim 1069e7547dacSJaegeuk Kim unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 1070e7547dacSJaegeuk Kim { 1071e7547dacSJaegeuk Kim if (!test_opt(sbi, READ_EXTENT_CACHE)) 1072e7547dacSJaegeuk Kim return 0; 1073e7547dacSJaegeuk Kim 1074e7547dacSJaegeuk Kim return __shrink_extent_tree(sbi, nr_shrink, EX_READ); 1075e7547dacSJaegeuk Kim } 1076e7547dacSJaegeuk Kim 107771644dffSJaegeuk Kim /* block age extent cache operations */ 107871644dffSJaegeuk Kim bool f2fs_lookup_age_extent_cache(struct inode *inode, pgoff_t pgofs, 107971644dffSJaegeuk Kim struct extent_info *ei) 108071644dffSJaegeuk Kim { 108171644dffSJaegeuk Kim if (!__may_extent_tree(inode, EX_BLOCK_AGE)) 108271644dffSJaegeuk Kim return false; 108371644dffSJaegeuk Kim 108471644dffSJaegeuk Kim return __lookup_extent_tree(inode, pgofs, ei, EX_BLOCK_AGE); 108571644dffSJaegeuk Kim } 108671644dffSJaegeuk Kim 108771644dffSJaegeuk Kim void f2fs_update_age_extent_cache(struct dnode_of_data *dn) 108871644dffSJaegeuk Kim { 108971644dffSJaegeuk Kim return __update_extent_cache(dn, EX_BLOCK_AGE); 109071644dffSJaegeuk Kim } 109171644dffSJaegeuk Kim 109271644dffSJaegeuk Kim void f2fs_update_age_extent_cache_range(struct dnode_of_data *dn, 109371644dffSJaegeuk Kim pgoff_t fofs, unsigned int len) 109471644dffSJaegeuk Kim { 109571644dffSJaegeuk Kim struct extent_info ei = { 109671644dffSJaegeuk Kim .fofs = fofs, 109771644dffSJaegeuk Kim .len = len, 109871644dffSJaegeuk Kim }; 109971644dffSJaegeuk Kim 110071644dffSJaegeuk Kim if (!__may_extent_tree(dn->inode, EX_BLOCK_AGE)) 110171644dffSJaegeuk Kim return; 110271644dffSJaegeuk Kim 110371644dffSJaegeuk Kim __update_extent_tree_range(dn->inode, &ei, EX_BLOCK_AGE); 110471644dffSJaegeuk Kim } 110571644dffSJaegeuk Kim 110671644dffSJaegeuk Kim unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 110771644dffSJaegeuk Kim { 110871644dffSJaegeuk Kim if (!test_opt(sbi, AGE_EXTENT_CACHE)) 110971644dffSJaegeuk Kim return 0; 111071644dffSJaegeuk Kim 111171644dffSJaegeuk Kim return __shrink_extent_tree(sbi, nr_shrink, EX_BLOCK_AGE); 111271644dffSJaegeuk Kim } 111371644dffSJaegeuk Kim 1114e7547dacSJaegeuk Kim static unsigned int __destroy_extent_node(struct inode *inode, 1115e7547dacSJaegeuk Kim enum extent_type type) 1116a28ef1f5SChao Yu { 1117a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1118e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1119a28ef1f5SChao Yu unsigned int node_cnt = 0; 1120a28ef1f5SChao Yu 11219b72a388SChao Yu if (!et || !atomic_read(&et->node_cnt)) 1122a28ef1f5SChao Yu return 0; 1123a28ef1f5SChao Yu 1124a28ef1f5SChao Yu write_lock(&et->lock); 1125201ef5e0SHou Pengyang node_cnt = __free_extent_tree(sbi, et); 1126a28ef1f5SChao Yu write_unlock(&et->lock); 1127a28ef1f5SChao Yu 1128a28ef1f5SChao Yu return node_cnt; 1129a28ef1f5SChao Yu } 1130a28ef1f5SChao Yu 1131e7547dacSJaegeuk Kim void f2fs_destroy_extent_node(struct inode *inode) 1132e7547dacSJaegeuk Kim { 1133e7547dacSJaegeuk Kim __destroy_extent_node(inode, EX_READ); 113471644dffSJaegeuk Kim __destroy_extent_node(inode, EX_BLOCK_AGE); 1135e7547dacSJaegeuk Kim } 1136e7547dacSJaegeuk Kim 1137e7547dacSJaegeuk Kim static void __drop_extent_tree(struct inode *inode, enum extent_type type) 11385f281fabSJaegeuk Kim { 11395f281fabSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1140e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1141b430f726SZhikang Zhang bool updated = false; 11425f281fabSJaegeuk Kim 1143e7547dacSJaegeuk Kim if (!__may_extent_tree(inode, type)) 1144bf617f7aSChao Yu return; 1145bf617f7aSChao Yu 11465f281fabSJaegeuk Kim write_lock(&et->lock); 11475f281fabSJaegeuk Kim __free_extent_tree(sbi, et); 1148e7547dacSJaegeuk Kim if (type == EX_READ) { 1149e7547dacSJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 1150b430f726SZhikang Zhang if (et->largest.len) { 1151b430f726SZhikang Zhang et->largest.len = 0; 1152b430f726SZhikang Zhang updated = true; 1153b430f726SZhikang Zhang } 1154e7547dacSJaegeuk Kim } 11555f281fabSJaegeuk Kim write_unlock(&et->lock); 1156b430f726SZhikang Zhang if (updated) 1157b430f726SZhikang Zhang f2fs_mark_inode_dirty_sync(inode, true); 11585f281fabSJaegeuk Kim } 11595f281fabSJaegeuk Kim 1160e7547dacSJaegeuk Kim void f2fs_drop_extent_tree(struct inode *inode) 1161e7547dacSJaegeuk Kim { 1162e7547dacSJaegeuk Kim __drop_extent_tree(inode, EX_READ); 116371644dffSJaegeuk Kim __drop_extent_tree(inode, EX_BLOCK_AGE); 1164e7547dacSJaegeuk Kim } 1165e7547dacSJaegeuk Kim 1166e7547dacSJaegeuk Kim static void __destroy_extent_tree(struct inode *inode, enum extent_type type) 1167a28ef1f5SChao Yu { 1168a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1169e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[type]; 1170e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1171a28ef1f5SChao Yu unsigned int node_cnt = 0; 1172a28ef1f5SChao Yu 1173a28ef1f5SChao Yu if (!et) 1174a28ef1f5SChao Yu return; 1175a28ef1f5SChao Yu 117668e35385SChao Yu if (inode->i_nlink && !is_bad_inode(inode) && 117768e35385SChao Yu atomic_read(&et->node_cnt)) { 1178e7547dacSJaegeuk Kim mutex_lock(&eti->extent_tree_lock); 1179e7547dacSJaegeuk Kim list_add_tail(&et->list, &eti->zombie_list); 1180e7547dacSJaegeuk Kim atomic_inc(&eti->total_zombie_tree); 1181e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1182a28ef1f5SChao Yu return; 1183a28ef1f5SChao Yu } 1184a28ef1f5SChao Yu 1185a28ef1f5SChao Yu /* free all extent info belong to this extent tree */ 1186e7547dacSJaegeuk Kim node_cnt = __destroy_extent_node(inode, type); 1187a28ef1f5SChao Yu 1188a28ef1f5SChao Yu /* delete extent tree entry in radix tree */ 1189e7547dacSJaegeuk Kim mutex_lock(&eti->extent_tree_lock); 119068e35385SChao Yu f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 1191e7547dacSJaegeuk Kim radix_tree_delete(&eti->extent_tree_root, inode->i_ino); 1192a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 1193e7547dacSJaegeuk Kim atomic_dec(&eti->total_ext_tree); 1194e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1195a28ef1f5SChao Yu 1196e7547dacSJaegeuk Kim F2FS_I(inode)->extent_tree[type] = NULL; 1197a28ef1f5SChao Yu 1198e7547dacSJaegeuk Kim trace_f2fs_destroy_extent_tree(inode, node_cnt, type); 1199a28ef1f5SChao Yu } 1200a28ef1f5SChao Yu 1201e7547dacSJaegeuk Kim void f2fs_destroy_extent_tree(struct inode *inode) 1202a28ef1f5SChao Yu { 1203e7547dacSJaegeuk Kim __destroy_extent_tree(inode, EX_READ); 120471644dffSJaegeuk Kim __destroy_extent_tree(inode, EX_BLOCK_AGE); 1205a28ef1f5SChao Yu } 1206a28ef1f5SChao Yu 1207e7547dacSJaegeuk Kim static void __init_extent_tree_info(struct extent_tree_info *eti) 1208a28ef1f5SChao Yu { 1209e7547dacSJaegeuk Kim INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO); 1210e7547dacSJaegeuk Kim mutex_init(&eti->extent_tree_lock); 1211e7547dacSJaegeuk Kim INIT_LIST_HEAD(&eti->extent_list); 1212e7547dacSJaegeuk Kim spin_lock_init(&eti->extent_lock); 1213e7547dacSJaegeuk Kim atomic_set(&eti->total_ext_tree, 0); 1214e7547dacSJaegeuk Kim INIT_LIST_HEAD(&eti->zombie_list); 1215e7547dacSJaegeuk Kim atomic_set(&eti->total_zombie_tree, 0); 1216e7547dacSJaegeuk Kim atomic_set(&eti->total_ext_node, 0); 1217a28ef1f5SChao Yu } 1218a28ef1f5SChao Yu 12194d57b86dSChao Yu void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi) 1220a28ef1f5SChao Yu { 1221e7547dacSJaegeuk Kim __init_extent_tree_info(&sbi->extent_tree[EX_READ]); 122271644dffSJaegeuk Kim __init_extent_tree_info(&sbi->extent_tree[EX_BLOCK_AGE]); 122371644dffSJaegeuk Kim 122471644dffSJaegeuk Kim /* initialize for block age extents */ 122571644dffSJaegeuk Kim atomic64_set(&sbi->allocated_data_blocks, 0); 122671644dffSJaegeuk Kim sbi->hot_data_age_threshold = DEF_HOT_DATA_AGE_THRESHOLD; 122771644dffSJaegeuk Kim sbi->warm_data_age_threshold = DEF_WARM_DATA_AGE_THRESHOLD; 1228a28ef1f5SChao Yu } 1229a28ef1f5SChao Yu 12304d57b86dSChao Yu int __init f2fs_create_extent_cache(void) 1231a28ef1f5SChao Yu { 1232a28ef1f5SChao Yu extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 1233a28ef1f5SChao Yu sizeof(struct extent_tree)); 1234a28ef1f5SChao Yu if (!extent_tree_slab) 1235a28ef1f5SChao Yu return -ENOMEM; 1236a28ef1f5SChao Yu extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 1237a28ef1f5SChao Yu sizeof(struct extent_node)); 1238a28ef1f5SChao Yu if (!extent_node_slab) { 1239a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 1240a28ef1f5SChao Yu return -ENOMEM; 1241a28ef1f5SChao Yu } 1242a28ef1f5SChao Yu return 0; 1243a28ef1f5SChao Yu } 1244a28ef1f5SChao Yu 12454d57b86dSChao Yu void f2fs_destroy_extent_cache(void) 1246a28ef1f5SChao Yu { 1247a28ef1f5SChao Yu kmem_cache_destroy(extent_node_slab); 1248a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 1249a28ef1f5SChao Yu } 1250