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 549*df9d44b6SJaegeuk Kim if (!et) 550*df9d44b6SJaegeuk Kim return false; 551a28ef1f5SChao Yu 552e7547dacSJaegeuk Kim trace_f2fs_lookup_extent_tree_start(inode, pgofs, type); 553a28ef1f5SChao Yu 554a28ef1f5SChao Yu read_lock(&et->lock); 555a28ef1f5SChao Yu 556e7547dacSJaegeuk Kim if (type == EX_READ && 557e7547dacSJaegeuk Kim et->largest.fofs <= pgofs && 558a28ef1f5SChao Yu et->largest.fofs + et->largest.len > pgofs) { 559a28ef1f5SChao Yu *ei = et->largest; 560a28ef1f5SChao Yu ret = true; 56191c481ffSChao Yu stat_inc_largest_node_hit(sbi); 562a28ef1f5SChao Yu goto out; 563a28ef1f5SChao Yu } 564a28ef1f5SChao Yu 5654d57b86dSChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root, 56654c2258cSChao Yu (struct rb_entry *)et->cached_en, pgofs); 56754c2258cSChao Yu if (!en) 56854c2258cSChao Yu goto out; 56954c2258cSChao Yu 57054c2258cSChao Yu if (en == et->cached_en) 571e7547dacSJaegeuk Kim stat_inc_cached_node_hit(sbi, type); 57254c2258cSChao Yu else 573e7547dacSJaegeuk Kim stat_inc_rbtree_node_hit(sbi, type); 57454c2258cSChao Yu 575a28ef1f5SChao Yu *ei = en->ei; 576e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 57742926744SJaegeuk Kim if (!list_empty(&en->list)) { 578e7547dacSJaegeuk Kim list_move_tail(&en->list, &eti->extent_list); 579a28ef1f5SChao Yu et->cached_en = en; 58042926744SJaegeuk Kim } 581e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 582a28ef1f5SChao Yu ret = true; 583a28ef1f5SChao Yu out: 584e7547dacSJaegeuk Kim stat_inc_total_hit(sbi, type); 585a28ef1f5SChao Yu read_unlock(&et->lock); 586a28ef1f5SChao Yu 587e7547dacSJaegeuk Kim if (type == EX_READ) 588e7547dacSJaegeuk Kim trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei); 58971644dffSJaegeuk Kim else if (type == EX_BLOCK_AGE) 59071644dffSJaegeuk Kim trace_f2fs_lookup_age_extent_tree_end(inode, pgofs, ei); 591a28ef1f5SChao Yu return ret; 592a28ef1f5SChao Yu } 593a28ef1f5SChao Yu 594b430f726SZhikang Zhang static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi, 5950f825ee6SFan Li struct extent_tree *et, struct extent_info *ei, 5960f825ee6SFan Li struct extent_node *prev_ex, 597ef05e221SChao Yu struct extent_node *next_ex) 5980f825ee6SFan Li { 599e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 6000f825ee6SFan Li struct extent_node *en = NULL; 6010f825ee6SFan Li 602e7547dacSJaegeuk Kim if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei, et->type)) { 6030f825ee6SFan Li prev_ex->ei.len += ei->len; 6040f825ee6SFan Li ei = &prev_ex->ei; 6050f825ee6SFan Li en = prev_ex; 6060f825ee6SFan Li } 607ef05e221SChao Yu 608e7547dacSJaegeuk Kim if (next_ex && __is_front_mergeable(ei, &next_ex->ei, et->type)) { 6090f825ee6SFan Li next_ex->ei.fofs = ei->fofs; 6100f825ee6SFan Li next_ex->ei.len += ei->len; 611e7547dacSJaegeuk Kim if (et->type == EX_READ) 612e7547dacSJaegeuk Kim next_ex->ei.blk = ei->blk; 6137855eba4SYunlei He if (en) 6147855eba4SYunlei He __release_extent_node(sbi, et, prev_ex); 6157855eba4SYunlei He 6160f825ee6SFan Li en = next_ex; 6170f825ee6SFan Li } 618ef05e221SChao Yu 61943a2fa18SJaegeuk Kim if (!en) 62043a2fa18SJaegeuk Kim return NULL; 62143a2fa18SJaegeuk Kim 622b430f726SZhikang Zhang __try_update_largest_extent(et, en); 62343a2fa18SJaegeuk Kim 624e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 62542926744SJaegeuk Kim if (!list_empty(&en->list)) { 626e7547dacSJaegeuk Kim list_move_tail(&en->list, &eti->extent_list); 62742926744SJaegeuk Kim et->cached_en = en; 62842926744SJaegeuk Kim } 629e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 630ef05e221SChao Yu return en; 631ef05e221SChao Yu } 632ef05e221SChao Yu 633b430f726SZhikang Zhang static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, 634ef05e221SChao Yu struct extent_tree *et, struct extent_info *ei, 635ef05e221SChao Yu struct rb_node **insert_p, 6364dada3fdSChao Yu struct rb_node *insert_parent, 6374dada3fdSChao Yu bool leftmost) 638ef05e221SChao Yu { 639e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[et->type]; 6408fe326cbSColin Ian King struct rb_node **p; 641ef05e221SChao Yu struct rb_node *parent = NULL; 642ef05e221SChao Yu struct extent_node *en = NULL; 6430f825ee6SFan Li 6440f825ee6SFan Li if (insert_p && insert_parent) { 6450f825ee6SFan Li parent = insert_parent; 6460f825ee6SFan Li p = insert_p; 6470f825ee6SFan Li goto do_insert; 6480f825ee6SFan Li } 6490f825ee6SFan Li 6504dada3fdSChao Yu leftmost = true; 6514dada3fdSChao Yu 6524dada3fdSChao Yu p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent, 6534dada3fdSChao Yu ei->fofs, &leftmost); 6540f825ee6SFan Li do_insert: 6554dada3fdSChao Yu en = __attach_extent_node(sbi, et, ei, parent, p, leftmost); 6560f825ee6SFan Li if (!en) 6570f825ee6SFan Li return NULL; 658ef05e221SChao Yu 659b430f726SZhikang Zhang __try_update_largest_extent(et, en); 66043a2fa18SJaegeuk Kim 66143a2fa18SJaegeuk Kim /* update in global extent list */ 662e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 663e7547dacSJaegeuk Kim list_add_tail(&en->list, &eti->extent_list); 66442926744SJaegeuk Kim et->cached_en = en; 665e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 6660f825ee6SFan Li return en; 6670f825ee6SFan Li } 6680f825ee6SFan Li 669e7547dacSJaegeuk Kim static void __update_extent_tree_range(struct inode *inode, 670e7547dacSJaegeuk Kim struct extent_info *tei, enum extent_type type) 671a28ef1f5SChao Yu { 672a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 673e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 6744d1fa815SFan Li struct extent_node *en = NULL, *en1 = NULL; 67519b2c30dSChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 676a28ef1f5SChao Yu struct extent_info ei, dei, prev; 6770f825ee6SFan Li struct rb_node **insert_p = NULL, *insert_parent = NULL; 678e7547dacSJaegeuk Kim unsigned int fofs = tei->fofs, len = tei->len; 67919b2c30dSChao Yu unsigned int end = fofs + len; 680b430f726SZhikang Zhang bool updated = false; 681f9aa52a8SChao Yu bool leftmost = false; 682a28ef1f5SChao Yu 683a28ef1f5SChao Yu if (!et) 684317e1300SChao Yu return; 685a28ef1f5SChao Yu 686e7547dacSJaegeuk Kim if (type == EX_READ) 687e7547dacSJaegeuk Kim trace_f2fs_update_read_extent_tree_range(inode, fofs, len, 688e7547dacSJaegeuk Kim tei->blk, 0); 68971644dffSJaegeuk Kim else if (type == EX_BLOCK_AGE) 69071644dffSJaegeuk Kim trace_f2fs_update_age_extent_tree_range(inode, fofs, len, 69171644dffSJaegeuk Kim tei->age, tei->last_blocks); 69271644dffSJaegeuk Kim 693a28ef1f5SChao Yu write_lock(&et->lock); 694a28ef1f5SChao Yu 695e7547dacSJaegeuk Kim if (type == EX_READ) { 69691942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) { 697a28ef1f5SChao Yu write_unlock(&et->lock); 698317e1300SChao Yu return; 699a28ef1f5SChao Yu } 700a28ef1f5SChao Yu 701a28ef1f5SChao Yu prev = et->largest; 702a28ef1f5SChao Yu dei.len = 0; 703a28ef1f5SChao Yu 7044d1fa815SFan Li /* 7054d1fa815SFan Li * drop largest extent before lookup, in case it's already 7064d1fa815SFan Li * been shrunk from extent tree 7074d1fa815SFan Li */ 708b430f726SZhikang Zhang __drop_largest_extent(et, fofs, len); 709e7547dacSJaegeuk Kim } 710a28ef1f5SChao Yu 71119b2c30dSChao Yu /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ 7124d57b86dSChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, 71354c2258cSChao Yu (struct rb_entry *)et->cached_en, fofs, 71454c2258cSChao Yu (struct rb_entry **)&prev_en, 71554c2258cSChao Yu (struct rb_entry **)&next_en, 7164dada3fdSChao Yu &insert_p, &insert_parent, false, 7174dada3fdSChao Yu &leftmost); 7184d1fa815SFan Li if (!en) 71919b2c30dSChao Yu en = next_en; 72019b2c30dSChao Yu 72119b2c30dSChao Yu /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */ 7224d1fa815SFan Li while (en && en->ei.fofs < end) { 7234d1fa815SFan Li unsigned int org_end; 7244d1fa815SFan Li int parts = 0; /* # of parts current extent split into */ 72519b2c30dSChao Yu 7264d1fa815SFan Li next_en = en1 = NULL; 727a28ef1f5SChao Yu 728a28ef1f5SChao Yu dei = en->ei; 7294d1fa815SFan Li org_end = dei.fofs + dei.len; 730e7547dacSJaegeuk Kim f2fs_bug_on(sbi, fofs >= org_end); 73119b2c30dSChao Yu 732e7547dacSJaegeuk Kim if (fofs > dei.fofs && (type != EX_READ || 733e7547dacSJaegeuk Kim fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) { 734e7547dacSJaegeuk Kim en->ei.len = fofs - en->ei.fofs; 7354d1fa815SFan Li prev_en = en; 7364d1fa815SFan Li parts = 1; 73719b2c30dSChao Yu } 73819b2c30dSChao Yu 739e7547dacSJaegeuk Kim if (end < org_end && (type != EX_READ || 740e7547dacSJaegeuk Kim org_end - end >= F2FS_MIN_EXTENT_LEN)) { 7414d1fa815SFan Li if (parts) { 7423bac20a8SJaegeuk Kim __set_extent_info(&ei, 7433bac20a8SJaegeuk Kim end, org_end - end, 744e7547dacSJaegeuk Kim end - dei.fofs + dei.blk, false, 74571644dffSJaegeuk Kim dei.age, dei.last_blocks, 746e7547dacSJaegeuk Kim type); 747b430f726SZhikang Zhang en1 = __insert_extent_tree(sbi, et, &ei, 7484dada3fdSChao Yu NULL, NULL, true); 7494d1fa815SFan Li next_en = en1; 7504d1fa815SFan Li } else { 7513bac20a8SJaegeuk Kim __set_extent_info(&en->ei, 7523bac20a8SJaegeuk Kim end, en->ei.len - (end - dei.fofs), 753e7547dacSJaegeuk Kim en->ei.blk + (end - dei.fofs), true, 75471644dffSJaegeuk Kim dei.age, dei.last_blocks, 755e7547dacSJaegeuk Kim type); 7564d1fa815SFan Li next_en = en; 7574d1fa815SFan Li } 7584d1fa815SFan Li parts++; 75919b2c30dSChao Yu } 76019b2c30dSChao Yu 7614d1fa815SFan Li if (!next_en) { 7624d1fa815SFan Li struct rb_node *node = rb_next(&en->rb_node); 7634d1fa815SFan Li 764ed0b5620SGeliang Tang next_en = rb_entry_safe(node, struct extent_node, 765ed0b5620SGeliang Tang rb_node); 7664d1fa815SFan Li } 7674d1fa815SFan Li 7684abd3f5aSChao Yu if (parts) 769b430f726SZhikang Zhang __try_update_largest_extent(et, en); 7704abd3f5aSChao Yu else 771a03f01f2SHou Pengyang __release_extent_node(sbi, et, en); 77219b2c30dSChao Yu 77319b2c30dSChao Yu /* 7744d1fa815SFan Li * if original extent is split into zero or two parts, extent 7754d1fa815SFan Li * tree has been altered by deletion or insertion, therefore 7764d1fa815SFan Li * invalidate pointers regard to tree. 77719b2c30dSChao Yu */ 7784d1fa815SFan Li if (parts != 1) { 77919b2c30dSChao Yu insert_p = NULL; 78019b2c30dSChao Yu insert_parent = NULL; 78119b2c30dSChao Yu } 7824d1fa815SFan Li en = next_en; 78319b2c30dSChao Yu } 784a28ef1f5SChao Yu 78571644dffSJaegeuk Kim if (type == EX_BLOCK_AGE) 78671644dffSJaegeuk Kim goto update_age_extent_cache; 78771644dffSJaegeuk Kim 788e7547dacSJaegeuk Kim /* 3. update extent in read extent cache */ 789e7547dacSJaegeuk Kim BUG_ON(type != EX_READ); 790e7547dacSJaegeuk Kim 791e7547dacSJaegeuk Kim if (tei->blk) { 79271644dffSJaegeuk Kim __set_extent_info(&ei, fofs, len, tei->blk, false, 79371644dffSJaegeuk Kim 0, 0, EX_READ); 794b430f726SZhikang Zhang if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 795b430f726SZhikang Zhang __insert_extent_tree(sbi, et, &ei, 7964dada3fdSChao Yu insert_p, insert_parent, leftmost); 797a28ef1f5SChao Yu 798a28ef1f5SChao Yu /* give up extent_cache, if split and small updates happen */ 799a28ef1f5SChao Yu if (dei.len >= 1 && 800a28ef1f5SChao Yu prev.len < F2FS_MIN_EXTENT_LEN && 801a28ef1f5SChao Yu et->largest.len < F2FS_MIN_EXTENT_LEN) { 802b430f726SZhikang Zhang et->largest.len = 0; 803b430f726SZhikang Zhang et->largest_updated = true; 80491942321SJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 805a28ef1f5SChao Yu } 80619b2c30dSChao Yu } 807a28ef1f5SChao Yu 80891942321SJaegeuk Kim if (is_inode_flag_set(inode, FI_NO_EXTENT)) 809201ef5e0SHou Pengyang __free_extent_tree(sbi, et); 810a28ef1f5SChao Yu 811b430f726SZhikang Zhang if (et->largest_updated) { 812b430f726SZhikang Zhang et->largest_updated = false; 813b430f726SZhikang Zhang updated = true; 814b430f726SZhikang Zhang } 81571644dffSJaegeuk Kim goto out_read_extent_cache; 81671644dffSJaegeuk Kim update_age_extent_cache: 81771644dffSJaegeuk Kim if (!tei->last_blocks) 81871644dffSJaegeuk Kim goto out_read_extent_cache; 819b430f726SZhikang Zhang 82071644dffSJaegeuk Kim __set_extent_info(&ei, fofs, len, 0, false, 82171644dffSJaegeuk Kim tei->age, tei->last_blocks, EX_BLOCK_AGE); 82271644dffSJaegeuk Kim if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 82371644dffSJaegeuk Kim __insert_extent_tree(sbi, et, &ei, 82471644dffSJaegeuk Kim insert_p, insert_parent, leftmost); 82571644dffSJaegeuk Kim out_read_extent_cache: 826a28ef1f5SChao Yu write_unlock(&et->lock); 827b430f726SZhikang Zhang 828b430f726SZhikang Zhang if (updated) 829b430f726SZhikang Zhang f2fs_mark_inode_dirty_sync(inode, true); 830a28ef1f5SChao Yu } 831a28ef1f5SChao Yu 83294afd6d6SChao Yu #ifdef CONFIG_F2FS_FS_COMPRESSION 833e7547dacSJaegeuk Kim void f2fs_update_read_extent_tree_range_compressed(struct inode *inode, 83494afd6d6SChao Yu pgoff_t fofs, block_t blkaddr, unsigned int llen, 83594afd6d6SChao Yu unsigned int c_len) 83694afd6d6SChao Yu { 83794afd6d6SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 838e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ]; 83994afd6d6SChao Yu struct extent_node *en = NULL; 84094afd6d6SChao Yu struct extent_node *prev_en = NULL, *next_en = NULL; 84194afd6d6SChao Yu struct extent_info ei; 84294afd6d6SChao Yu struct rb_node **insert_p = NULL, *insert_parent = NULL; 84394afd6d6SChao Yu bool leftmost = false; 84494afd6d6SChao Yu 845e7547dacSJaegeuk Kim trace_f2fs_update_read_extent_tree_range(inode, fofs, llen, 846e7547dacSJaegeuk Kim blkaddr, c_len); 84794afd6d6SChao Yu 84894afd6d6SChao Yu /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */ 84994afd6d6SChao Yu if (is_inode_flag_set(inode, FI_NO_EXTENT)) 85094afd6d6SChao Yu return; 85194afd6d6SChao Yu 85294afd6d6SChao Yu write_lock(&et->lock); 85394afd6d6SChao Yu 85494afd6d6SChao Yu en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, 85594afd6d6SChao Yu (struct rb_entry *)et->cached_en, fofs, 85694afd6d6SChao Yu (struct rb_entry **)&prev_en, 85794afd6d6SChao Yu (struct rb_entry **)&next_en, 85894afd6d6SChao Yu &insert_p, &insert_parent, false, 85994afd6d6SChao Yu &leftmost); 86094afd6d6SChao Yu if (en) 86194afd6d6SChao Yu goto unlock_out; 86294afd6d6SChao Yu 86371644dffSJaegeuk Kim __set_extent_info(&ei, fofs, llen, blkaddr, true, 0, 0, EX_READ); 86494afd6d6SChao Yu ei.c_len = c_len; 86594afd6d6SChao Yu 86694afd6d6SChao Yu if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) 86794afd6d6SChao Yu __insert_extent_tree(sbi, et, &ei, 86894afd6d6SChao Yu insert_p, insert_parent, leftmost); 86994afd6d6SChao Yu unlock_out: 87094afd6d6SChao Yu write_unlock(&et->lock); 87194afd6d6SChao Yu } 87294afd6d6SChao Yu #endif 87394afd6d6SChao Yu 87471644dffSJaegeuk Kim static unsigned long long __calculate_block_age(unsigned long long new, 87571644dffSJaegeuk Kim unsigned long long old) 87671644dffSJaegeuk Kim { 87771644dffSJaegeuk Kim unsigned long long diff; 87871644dffSJaegeuk Kim 87971644dffSJaegeuk Kim diff = (new >= old) ? new - (new - old) : new + (old - new); 88071644dffSJaegeuk Kim 88171644dffSJaegeuk Kim return div_u64(diff * LAST_AGE_WEIGHT, 100); 88271644dffSJaegeuk Kim } 88371644dffSJaegeuk Kim 88471644dffSJaegeuk Kim /* This returns a new age and allocated blocks in ei */ 885ed272476SJaegeuk Kim static int __get_new_block_age(struct inode *inode, struct extent_info *ei, 886ed272476SJaegeuk Kim block_t blkaddr) 88771644dffSJaegeuk Kim { 88871644dffSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 88971644dffSJaegeuk Kim loff_t f_size = i_size_read(inode); 89071644dffSJaegeuk Kim unsigned long long cur_blocks = 89171644dffSJaegeuk Kim atomic64_read(&sbi->allocated_data_blocks); 89222a341b4SJaegeuk Kim struct extent_info tei = *ei; /* only fofs and len are valid */ 89371644dffSJaegeuk Kim 89471644dffSJaegeuk Kim /* 89571644dffSJaegeuk Kim * When I/O is not aligned to a PAGE_SIZE, update will happen to the last 89671644dffSJaegeuk Kim * file block even in seq write. So don't record age for newly last file 89771644dffSJaegeuk Kim * block here. 89871644dffSJaegeuk Kim */ 89971644dffSJaegeuk Kim if ((f_size >> PAGE_SHIFT) == ei->fofs && f_size & (PAGE_SIZE - 1) && 900ed272476SJaegeuk Kim blkaddr == NEW_ADDR) 90171644dffSJaegeuk Kim return -EINVAL; 90271644dffSJaegeuk Kim 90322a341b4SJaegeuk Kim if (__lookup_extent_tree(inode, ei->fofs, &tei, EX_BLOCK_AGE)) { 90471644dffSJaegeuk Kim unsigned long long cur_age; 90571644dffSJaegeuk Kim 90622a341b4SJaegeuk Kim if (cur_blocks >= tei.last_blocks) 90722a341b4SJaegeuk Kim cur_age = cur_blocks - tei.last_blocks; 90871644dffSJaegeuk Kim else 90971644dffSJaegeuk Kim /* allocated_data_blocks overflow */ 91022a341b4SJaegeuk Kim cur_age = ULLONG_MAX - tei.last_blocks + cur_blocks; 91171644dffSJaegeuk Kim 91222a341b4SJaegeuk Kim if (tei.age) 91322a341b4SJaegeuk Kim ei->age = __calculate_block_age(cur_age, tei.age); 91471644dffSJaegeuk Kim else 91571644dffSJaegeuk Kim ei->age = cur_age; 91671644dffSJaegeuk Kim ei->last_blocks = cur_blocks; 91771644dffSJaegeuk Kim WARN_ON(ei->age > cur_blocks); 91871644dffSJaegeuk Kim return 0; 91971644dffSJaegeuk Kim } 92071644dffSJaegeuk Kim 921ed272476SJaegeuk Kim f2fs_bug_on(sbi, blkaddr == NULL_ADDR); 92271644dffSJaegeuk Kim 92371644dffSJaegeuk Kim /* the data block was allocated for the first time */ 924ed272476SJaegeuk Kim if (blkaddr == NEW_ADDR) 92571644dffSJaegeuk Kim goto out; 92671644dffSJaegeuk Kim 927ed272476SJaegeuk Kim if (__is_valid_data_blkaddr(blkaddr) && 928ed272476SJaegeuk Kim !f2fs_is_valid_blkaddr(sbi, blkaddr, DATA_GENERIC_ENHANCE)) { 92971644dffSJaegeuk Kim f2fs_bug_on(sbi, 1); 93071644dffSJaegeuk Kim return -EINVAL; 93171644dffSJaegeuk Kim } 93271644dffSJaegeuk Kim out: 93371644dffSJaegeuk Kim /* 93471644dffSJaegeuk Kim * init block age with zero, this can happen when the block age extent 93571644dffSJaegeuk Kim * was reclaimed due to memory constraint or system reboot 93671644dffSJaegeuk Kim */ 93771644dffSJaegeuk Kim ei->age = 0; 93871644dffSJaegeuk Kim ei->last_blocks = cur_blocks; 93971644dffSJaegeuk Kim return 0; 94071644dffSJaegeuk Kim } 94171644dffSJaegeuk Kim 942e7547dacSJaegeuk Kim static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type) 943a28ef1f5SChao Yu { 944fe59109aSJaegeuk Kim struct extent_info ei = {}; 945e7547dacSJaegeuk Kim 946e7547dacSJaegeuk Kim if (!__may_extent_tree(dn->inode, type)) 947e7547dacSJaegeuk Kim return; 948e7547dacSJaegeuk Kim 949e7547dacSJaegeuk Kim ei.fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) + 950e7547dacSJaegeuk Kim dn->ofs_in_node; 951e7547dacSJaegeuk Kim ei.len = 1; 952e7547dacSJaegeuk Kim 953e7547dacSJaegeuk Kim if (type == EX_READ) { 954e7547dacSJaegeuk Kim if (dn->data_blkaddr == NEW_ADDR) 955e7547dacSJaegeuk Kim ei.blk = NULL_ADDR; 956e7547dacSJaegeuk Kim else 957e7547dacSJaegeuk Kim ei.blk = dn->data_blkaddr; 95871644dffSJaegeuk Kim } else if (type == EX_BLOCK_AGE) { 959ed272476SJaegeuk Kim if (__get_new_block_age(dn->inode, &ei, dn->data_blkaddr)) 96071644dffSJaegeuk Kim return; 961e7547dacSJaegeuk Kim } 962e7547dacSJaegeuk Kim __update_extent_tree_range(dn->inode, &ei, type); 963e7547dacSJaegeuk Kim } 964e7547dacSJaegeuk Kim 965e7547dacSJaegeuk Kim static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink, 966e7547dacSJaegeuk Kim enum extent_type type) 967e7547dacSJaegeuk Kim { 968e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[type]; 969137d09f0SJaegeuk Kim struct extent_tree *et, *next; 970201ef5e0SHou Pengyang struct extent_node *en; 971a28ef1f5SChao Yu unsigned int node_cnt = 0, tree_cnt = 0; 972a28ef1f5SChao Yu int remained; 973a28ef1f5SChao Yu 974e7547dacSJaegeuk Kim if (!atomic_read(&eti->total_zombie_tree)) 97574fd8d99SJaegeuk Kim goto free_node; 97674fd8d99SJaegeuk Kim 977e7547dacSJaegeuk Kim if (!mutex_trylock(&eti->extent_tree_lock)) 978a28ef1f5SChao Yu goto out; 979a28ef1f5SChao Yu 980a28ef1f5SChao Yu /* 1. remove unreferenced extent tree */ 981e7547dacSJaegeuk Kim list_for_each_entry_safe(et, next, &eti->zombie_list, list) { 9829b72a388SChao Yu if (atomic_read(&et->node_cnt)) { 983a28ef1f5SChao Yu write_lock(&et->lock); 984201ef5e0SHou Pengyang node_cnt += __free_extent_tree(sbi, et); 985a28ef1f5SChao Yu write_unlock(&et->lock); 9869b72a388SChao Yu } 987201ef5e0SHou Pengyang f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 988137d09f0SJaegeuk Kim list_del_init(&et->list); 989e7547dacSJaegeuk Kim radix_tree_delete(&eti->extent_tree_root, et->ino); 990a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 991e7547dacSJaegeuk Kim atomic_dec(&eti->total_ext_tree); 992e7547dacSJaegeuk Kim atomic_dec(&eti->total_zombie_tree); 993a28ef1f5SChao Yu tree_cnt++; 994a28ef1f5SChao Yu 995a28ef1f5SChao Yu if (node_cnt + tree_cnt >= nr_shrink) 996a28ef1f5SChao Yu goto unlock_out; 9976fe2bc95SJaegeuk Kim cond_resched(); 998a28ef1f5SChao Yu } 999e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1000a28ef1f5SChao Yu 100174fd8d99SJaegeuk Kim free_node: 1002a28ef1f5SChao Yu /* 2. remove LRU extent entries */ 1003e7547dacSJaegeuk Kim if (!mutex_trylock(&eti->extent_tree_lock)) 1004a28ef1f5SChao Yu goto out; 1005a28ef1f5SChao Yu 1006a28ef1f5SChao Yu remained = nr_shrink - (node_cnt + tree_cnt); 1007a28ef1f5SChao Yu 1008e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 1009201ef5e0SHou Pengyang for (; remained > 0; remained--) { 1010e7547dacSJaegeuk Kim if (list_empty(&eti->extent_list)) 1011a28ef1f5SChao Yu break; 1012e7547dacSJaegeuk Kim en = list_first_entry(&eti->extent_list, 1013201ef5e0SHou Pengyang struct extent_node, list); 1014201ef5e0SHou Pengyang et = en->et; 1015201ef5e0SHou Pengyang if (!write_trylock(&et->lock)) { 1016201ef5e0SHou Pengyang /* refresh this extent node's position in extent list */ 1017e7547dacSJaegeuk Kim list_move_tail(&en->list, &eti->extent_list); 1018201ef5e0SHou Pengyang continue; 1019201ef5e0SHou Pengyang } 1020201ef5e0SHou Pengyang 1021a28ef1f5SChao Yu list_del_init(&en->list); 1022e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 1023201ef5e0SHou Pengyang 1024201ef5e0SHou Pengyang __detach_extent_node(sbi, et, en); 1025201ef5e0SHou Pengyang 1026201ef5e0SHou Pengyang write_unlock(&et->lock); 1027201ef5e0SHou Pengyang node_cnt++; 1028e7547dacSJaegeuk Kim spin_lock(&eti->extent_lock); 1029a28ef1f5SChao Yu } 1030e7547dacSJaegeuk Kim spin_unlock(&eti->extent_lock); 1031a28ef1f5SChao Yu 1032a28ef1f5SChao Yu unlock_out: 1033e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1034a28ef1f5SChao Yu out: 1035e7547dacSJaegeuk Kim trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type); 1036a28ef1f5SChao Yu 1037a28ef1f5SChao Yu return node_cnt + tree_cnt; 1038a28ef1f5SChao Yu } 1039a28ef1f5SChao Yu 1040e7547dacSJaegeuk Kim /* read extent cache operations */ 1041e7547dacSJaegeuk Kim bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs, 1042e7547dacSJaegeuk Kim struct extent_info *ei) 1043e7547dacSJaegeuk Kim { 1044e7547dacSJaegeuk Kim if (!__may_extent_tree(inode, EX_READ)) 1045e7547dacSJaegeuk Kim return false; 1046e7547dacSJaegeuk Kim 1047e7547dacSJaegeuk Kim return __lookup_extent_tree(inode, pgofs, ei, EX_READ); 1048e7547dacSJaegeuk Kim } 1049e7547dacSJaegeuk Kim 1050e7547dacSJaegeuk Kim void f2fs_update_read_extent_cache(struct dnode_of_data *dn) 1051e7547dacSJaegeuk Kim { 1052e7547dacSJaegeuk Kim return __update_extent_cache(dn, EX_READ); 1053e7547dacSJaegeuk Kim } 1054e7547dacSJaegeuk Kim 1055e7547dacSJaegeuk Kim void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn, 1056e7547dacSJaegeuk Kim pgoff_t fofs, block_t blkaddr, unsigned int len) 1057e7547dacSJaegeuk Kim { 1058e7547dacSJaegeuk Kim struct extent_info ei = { 1059e7547dacSJaegeuk Kim .fofs = fofs, 1060e7547dacSJaegeuk Kim .len = len, 1061e7547dacSJaegeuk Kim .blk = blkaddr, 1062e7547dacSJaegeuk Kim }; 1063e7547dacSJaegeuk Kim 1064e7547dacSJaegeuk Kim if (!__may_extent_tree(dn->inode, EX_READ)) 1065e7547dacSJaegeuk Kim return; 1066e7547dacSJaegeuk Kim 1067e7547dacSJaegeuk Kim __update_extent_tree_range(dn->inode, &ei, EX_READ); 1068e7547dacSJaegeuk Kim } 1069e7547dacSJaegeuk Kim 1070e7547dacSJaegeuk Kim unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 1071e7547dacSJaegeuk Kim { 1072e7547dacSJaegeuk Kim if (!test_opt(sbi, READ_EXTENT_CACHE)) 1073e7547dacSJaegeuk Kim return 0; 1074e7547dacSJaegeuk Kim 1075e7547dacSJaegeuk Kim return __shrink_extent_tree(sbi, nr_shrink, EX_READ); 1076e7547dacSJaegeuk Kim } 1077e7547dacSJaegeuk Kim 107871644dffSJaegeuk Kim /* block age extent cache operations */ 107971644dffSJaegeuk Kim bool f2fs_lookup_age_extent_cache(struct inode *inode, pgoff_t pgofs, 108071644dffSJaegeuk Kim struct extent_info *ei) 108171644dffSJaegeuk Kim { 108271644dffSJaegeuk Kim if (!__may_extent_tree(inode, EX_BLOCK_AGE)) 108371644dffSJaegeuk Kim return false; 108471644dffSJaegeuk Kim 108571644dffSJaegeuk Kim return __lookup_extent_tree(inode, pgofs, ei, EX_BLOCK_AGE); 108671644dffSJaegeuk Kim } 108771644dffSJaegeuk Kim 108871644dffSJaegeuk Kim void f2fs_update_age_extent_cache(struct dnode_of_data *dn) 108971644dffSJaegeuk Kim { 109071644dffSJaegeuk Kim return __update_extent_cache(dn, EX_BLOCK_AGE); 109171644dffSJaegeuk Kim } 109271644dffSJaegeuk Kim 109371644dffSJaegeuk Kim void f2fs_update_age_extent_cache_range(struct dnode_of_data *dn, 109471644dffSJaegeuk Kim pgoff_t fofs, unsigned int len) 109571644dffSJaegeuk Kim { 109671644dffSJaegeuk Kim struct extent_info ei = { 109771644dffSJaegeuk Kim .fofs = fofs, 109871644dffSJaegeuk Kim .len = len, 109971644dffSJaegeuk Kim }; 110071644dffSJaegeuk Kim 110171644dffSJaegeuk Kim if (!__may_extent_tree(dn->inode, EX_BLOCK_AGE)) 110271644dffSJaegeuk Kim return; 110371644dffSJaegeuk Kim 110471644dffSJaegeuk Kim __update_extent_tree_range(dn->inode, &ei, EX_BLOCK_AGE); 110571644dffSJaegeuk Kim } 110671644dffSJaegeuk Kim 110771644dffSJaegeuk Kim unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) 110871644dffSJaegeuk Kim { 110971644dffSJaegeuk Kim if (!test_opt(sbi, AGE_EXTENT_CACHE)) 111071644dffSJaegeuk Kim return 0; 111171644dffSJaegeuk Kim 111271644dffSJaegeuk Kim return __shrink_extent_tree(sbi, nr_shrink, EX_BLOCK_AGE); 111371644dffSJaegeuk Kim } 111471644dffSJaegeuk Kim 1115e7547dacSJaegeuk Kim static unsigned int __destroy_extent_node(struct inode *inode, 1116e7547dacSJaegeuk Kim enum extent_type type) 1117a28ef1f5SChao Yu { 1118a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1119e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1120a28ef1f5SChao Yu unsigned int node_cnt = 0; 1121a28ef1f5SChao Yu 11229b72a388SChao Yu if (!et || !atomic_read(&et->node_cnt)) 1123a28ef1f5SChao Yu return 0; 1124a28ef1f5SChao Yu 1125a28ef1f5SChao Yu write_lock(&et->lock); 1126201ef5e0SHou Pengyang node_cnt = __free_extent_tree(sbi, et); 1127a28ef1f5SChao Yu write_unlock(&et->lock); 1128a28ef1f5SChao Yu 1129a28ef1f5SChao Yu return node_cnt; 1130a28ef1f5SChao Yu } 1131a28ef1f5SChao Yu 1132e7547dacSJaegeuk Kim void f2fs_destroy_extent_node(struct inode *inode) 1133e7547dacSJaegeuk Kim { 1134e7547dacSJaegeuk Kim __destroy_extent_node(inode, EX_READ); 113571644dffSJaegeuk Kim __destroy_extent_node(inode, EX_BLOCK_AGE); 1136e7547dacSJaegeuk Kim } 1137e7547dacSJaegeuk Kim 1138e7547dacSJaegeuk Kim static void __drop_extent_tree(struct inode *inode, enum extent_type type) 11395f281fabSJaegeuk Kim { 11405f281fabSJaegeuk Kim struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1141e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1142b430f726SZhikang Zhang bool updated = false; 11435f281fabSJaegeuk Kim 1144e7547dacSJaegeuk Kim if (!__may_extent_tree(inode, type)) 1145bf617f7aSChao Yu return; 1146bf617f7aSChao Yu 11475f281fabSJaegeuk Kim write_lock(&et->lock); 11485f281fabSJaegeuk Kim __free_extent_tree(sbi, et); 1149e7547dacSJaegeuk Kim if (type == EX_READ) { 1150e7547dacSJaegeuk Kim set_inode_flag(inode, FI_NO_EXTENT); 1151b430f726SZhikang Zhang if (et->largest.len) { 1152b430f726SZhikang Zhang et->largest.len = 0; 1153b430f726SZhikang Zhang updated = true; 1154b430f726SZhikang Zhang } 1155e7547dacSJaegeuk Kim } 11565f281fabSJaegeuk Kim write_unlock(&et->lock); 1157b430f726SZhikang Zhang if (updated) 1158b430f726SZhikang Zhang f2fs_mark_inode_dirty_sync(inode, true); 11595f281fabSJaegeuk Kim } 11605f281fabSJaegeuk Kim 1161e7547dacSJaegeuk Kim void f2fs_drop_extent_tree(struct inode *inode) 1162e7547dacSJaegeuk Kim { 1163e7547dacSJaegeuk Kim __drop_extent_tree(inode, EX_READ); 116471644dffSJaegeuk Kim __drop_extent_tree(inode, EX_BLOCK_AGE); 1165e7547dacSJaegeuk Kim } 1166e7547dacSJaegeuk Kim 1167e7547dacSJaegeuk Kim static void __destroy_extent_tree(struct inode *inode, enum extent_type type) 1168a28ef1f5SChao Yu { 1169a28ef1f5SChao Yu struct f2fs_sb_info *sbi = F2FS_I_SB(inode); 1170e7547dacSJaegeuk Kim struct extent_tree_info *eti = &sbi->extent_tree[type]; 1171e7547dacSJaegeuk Kim struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; 1172a28ef1f5SChao Yu unsigned int node_cnt = 0; 1173a28ef1f5SChao Yu 1174a28ef1f5SChao Yu if (!et) 1175a28ef1f5SChao Yu return; 1176a28ef1f5SChao Yu 117768e35385SChao Yu if (inode->i_nlink && !is_bad_inode(inode) && 117868e35385SChao Yu atomic_read(&et->node_cnt)) { 1179e7547dacSJaegeuk Kim mutex_lock(&eti->extent_tree_lock); 1180e7547dacSJaegeuk Kim list_add_tail(&et->list, &eti->zombie_list); 1181e7547dacSJaegeuk Kim atomic_inc(&eti->total_zombie_tree); 1182e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1183a28ef1f5SChao Yu return; 1184a28ef1f5SChao Yu } 1185a28ef1f5SChao Yu 1186a28ef1f5SChao Yu /* free all extent info belong to this extent tree */ 1187e7547dacSJaegeuk Kim node_cnt = __destroy_extent_node(inode, type); 1188a28ef1f5SChao Yu 1189a28ef1f5SChao Yu /* delete extent tree entry in radix tree */ 1190e7547dacSJaegeuk Kim mutex_lock(&eti->extent_tree_lock); 119168e35385SChao Yu f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); 1192e7547dacSJaegeuk Kim radix_tree_delete(&eti->extent_tree_root, inode->i_ino); 1193a28ef1f5SChao Yu kmem_cache_free(extent_tree_slab, et); 1194e7547dacSJaegeuk Kim atomic_dec(&eti->total_ext_tree); 1195e7547dacSJaegeuk Kim mutex_unlock(&eti->extent_tree_lock); 1196a28ef1f5SChao Yu 1197e7547dacSJaegeuk Kim F2FS_I(inode)->extent_tree[type] = NULL; 1198a28ef1f5SChao Yu 1199e7547dacSJaegeuk Kim trace_f2fs_destroy_extent_tree(inode, node_cnt, type); 1200a28ef1f5SChao Yu } 1201a28ef1f5SChao Yu 1202e7547dacSJaegeuk Kim void f2fs_destroy_extent_tree(struct inode *inode) 1203a28ef1f5SChao Yu { 1204e7547dacSJaegeuk Kim __destroy_extent_tree(inode, EX_READ); 120571644dffSJaegeuk Kim __destroy_extent_tree(inode, EX_BLOCK_AGE); 1206a28ef1f5SChao Yu } 1207a28ef1f5SChao Yu 1208e7547dacSJaegeuk Kim static void __init_extent_tree_info(struct extent_tree_info *eti) 1209a28ef1f5SChao Yu { 1210e7547dacSJaegeuk Kim INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO); 1211e7547dacSJaegeuk Kim mutex_init(&eti->extent_tree_lock); 1212e7547dacSJaegeuk Kim INIT_LIST_HEAD(&eti->extent_list); 1213e7547dacSJaegeuk Kim spin_lock_init(&eti->extent_lock); 1214e7547dacSJaegeuk Kim atomic_set(&eti->total_ext_tree, 0); 1215e7547dacSJaegeuk Kim INIT_LIST_HEAD(&eti->zombie_list); 1216e7547dacSJaegeuk Kim atomic_set(&eti->total_zombie_tree, 0); 1217e7547dacSJaegeuk Kim atomic_set(&eti->total_ext_node, 0); 1218a28ef1f5SChao Yu } 1219a28ef1f5SChao Yu 12204d57b86dSChao Yu void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi) 1221a28ef1f5SChao Yu { 1222e7547dacSJaegeuk Kim __init_extent_tree_info(&sbi->extent_tree[EX_READ]); 122371644dffSJaegeuk Kim __init_extent_tree_info(&sbi->extent_tree[EX_BLOCK_AGE]); 122471644dffSJaegeuk Kim 122571644dffSJaegeuk Kim /* initialize for block age extents */ 122671644dffSJaegeuk Kim atomic64_set(&sbi->allocated_data_blocks, 0); 122771644dffSJaegeuk Kim sbi->hot_data_age_threshold = DEF_HOT_DATA_AGE_THRESHOLD; 122871644dffSJaegeuk Kim sbi->warm_data_age_threshold = DEF_WARM_DATA_AGE_THRESHOLD; 1229a28ef1f5SChao Yu } 1230a28ef1f5SChao Yu 12314d57b86dSChao Yu int __init f2fs_create_extent_cache(void) 1232a28ef1f5SChao Yu { 1233a28ef1f5SChao Yu extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", 1234a28ef1f5SChao Yu sizeof(struct extent_tree)); 1235a28ef1f5SChao Yu if (!extent_tree_slab) 1236a28ef1f5SChao Yu return -ENOMEM; 1237a28ef1f5SChao Yu extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", 1238a28ef1f5SChao Yu sizeof(struct extent_node)); 1239a28ef1f5SChao Yu if (!extent_node_slab) { 1240a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 1241a28ef1f5SChao Yu return -ENOMEM; 1242a28ef1f5SChao Yu } 1243a28ef1f5SChao Yu return 0; 1244a28ef1f5SChao Yu } 1245a28ef1f5SChao Yu 12464d57b86dSChao Yu void f2fs_destroy_extent_cache(void) 1247a28ef1f5SChao Yu { 1248a28ef1f5SChao Yu kmem_cache_destroy(extent_node_slab); 1249a28ef1f5SChao Yu kmem_cache_destroy(extent_tree_slab); 1250a28ef1f5SChao Yu } 1251