Lines Matching +full:en +full:- +full:global
1 // SPDX-License-Identifier: GPL-2.0
22 if (cached_re->ofs <= ofs && in __lookup_rb_tree_fast()
23 cached_re->ofs + cached_re->len > ofs) { in __lookup_rb_tree_fast()
33 struct rb_node *node = root->rb_root.rb_node; in __lookup_rb_tree_slow()
39 if (ofs < re->ofs) in __lookup_rb_tree_slow()
40 node = node->rb_left; in __lookup_rb_tree_slow()
41 else if (ofs >= re->ofs + re->len) in __lookup_rb_tree_slow()
42 node = node->rb_right; in __lookup_rb_tree_slow()
66 struct rb_node **p = &root->rb_root.rb_node; in f2fs_lookup_rb_tree_ext()
73 if (key < re->key) { in f2fs_lookup_rb_tree_ext()
74 p = &(*p)->rb_left; in f2fs_lookup_rb_tree_ext()
76 p = &(*p)->rb_right; in f2fs_lookup_rb_tree_ext()
89 struct rb_node **p = &root->rb_root.rb_node; in f2fs_lookup_rb_tree_for_insert()
96 if (ofs < re->ofs) { in f2fs_lookup_rb_tree_for_insert()
97 p = &(*p)->rb_left; in f2fs_lookup_rb_tree_for_insert()
98 } else if (ofs >= re->ofs + re->len) { in f2fs_lookup_rb_tree_for_insert()
99 p = &(*p)->rb_right; in f2fs_lookup_rb_tree_for_insert()
110 * lookup rb entry in position of @ofs in rb-tree,
127 struct rb_node **pnode = &root->rb_root.rb_node; in f2fs_lookup_rb_tree_ret()
136 if (RB_EMPTY_ROOT(&root->rb_root)) in f2fs_lookup_rb_tree_ret()
140 if (re->ofs <= ofs && re->ofs + re->len > ofs) in f2fs_lookup_rb_tree_ret()
151 if (ofs < re->ofs) { in f2fs_lookup_rb_tree_ret()
152 pnode = &(*pnode)->rb_left; in f2fs_lookup_rb_tree_ret()
153 } else if (ofs >= re->ofs + re->len) { in f2fs_lookup_rb_tree_ret()
154 pnode = &(*pnode)->rb_right; in f2fs_lookup_rb_tree_ret()
167 if (parent && ofs > re->ofs) in f2fs_lookup_rb_tree_ret()
172 if (parent && ofs < re->ofs) in f2fs_lookup_rb_tree_ret()
178 if (ofs == re->ofs || force) { in f2fs_lookup_rb_tree_ret()
180 tmp_node = rb_prev(&re->rb_node); in f2fs_lookup_rb_tree_ret()
183 if (ofs == re->ofs + re->len - 1 || force) { in f2fs_lookup_rb_tree_ret()
185 tmp_node = rb_next(&re->rb_node); in f2fs_lookup_rb_tree_ret()
210 if (cur_re->key > next_re->key) { in f2fs_check_rb_tree_consistence()
213 cur_re->key, next_re->key); in f2fs_check_rb_tree_consistence()
219 if (cur_re->ofs + cur_re->len > next_re->ofs) { in f2fs_check_rb_tree_consistence()
221 cur_re->ofs, cur_re->len, in f2fs_check_rb_tree_consistence()
222 next_re->ofs, next_re->len); in f2fs_check_rb_tree_consistence()
240 struct extent_node *en; in __attach_extent_node() local
242 en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi); in __attach_extent_node()
243 if (!en) in __attach_extent_node()
246 en->ei = *ei; in __attach_extent_node()
247 INIT_LIST_HEAD(&en->list); in __attach_extent_node()
248 en->et = et; in __attach_extent_node()
250 rb_link_node(&en->rb_node, parent, p); in __attach_extent_node()
251 rb_insert_color_cached(&en->rb_node, &et->root, leftmost); in __attach_extent_node()
252 atomic_inc(&et->node_cnt); in __attach_extent_node()
253 atomic_inc(&sbi->total_ext_node); in __attach_extent_node()
254 return en; in __attach_extent_node()
258 struct extent_tree *et, struct extent_node *en) in __detach_extent_node() argument
260 rb_erase_cached(&en->rb_node, &et->root); in __detach_extent_node()
261 atomic_dec(&et->node_cnt); in __detach_extent_node()
262 atomic_dec(&sbi->total_ext_node); in __detach_extent_node()
264 if (et->cached_en == en) in __detach_extent_node()
265 et->cached_en = NULL; in __detach_extent_node()
266 kmem_cache_free(extent_node_slab, en); in __detach_extent_node()
276 struct extent_tree *et, struct extent_node *en) in __release_extent_node() argument
278 spin_lock(&sbi->extent_lock); in __release_extent_node()
279 f2fs_bug_on(sbi, list_empty(&en->list)); in __release_extent_node()
280 list_del_init(&en->list); in __release_extent_node()
281 spin_unlock(&sbi->extent_lock); in __release_extent_node()
283 __detach_extent_node(sbi, et, en); in __release_extent_node()
290 nid_t ino = inode->i_ino; in __grab_extent_tree()
292 mutex_lock(&sbi->extent_tree_lock); in __grab_extent_tree()
293 et = radix_tree_lookup(&sbi->extent_tree_root, ino); in __grab_extent_tree()
297 f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et); in __grab_extent_tree()
299 et->ino = ino; in __grab_extent_tree()
300 et->root = RB_ROOT_CACHED; in __grab_extent_tree()
301 et->cached_en = NULL; in __grab_extent_tree()
302 rwlock_init(&et->lock); in __grab_extent_tree()
303 INIT_LIST_HEAD(&et->list); in __grab_extent_tree()
304 atomic_set(&et->node_cnt, 0); in __grab_extent_tree()
305 atomic_inc(&sbi->total_ext_tree); in __grab_extent_tree()
307 atomic_dec(&sbi->total_zombie_tree); in __grab_extent_tree()
308 list_del_init(&et->list); in __grab_extent_tree()
310 mutex_unlock(&sbi->extent_tree_lock); in __grab_extent_tree()
313 F2FS_I(inode)->extent_tree = et; in __grab_extent_tree()
321 struct rb_node **p = &et->root.rb_root.rb_node; in __init_extent_tree()
322 struct extent_node *en; in __init_extent_tree() local
324 en = __attach_extent_node(sbi, et, ei, NULL, p, true); in __init_extent_tree()
325 if (!en) in __init_extent_tree()
328 et->largest = en->ei; in __init_extent_tree()
329 et->cached_en = en; in __init_extent_tree()
330 return en; in __init_extent_tree()
337 struct extent_node *en; in __free_extent_tree() local
338 unsigned int count = atomic_read(&et->node_cnt); in __free_extent_tree()
340 node = rb_first_cached(&et->root); in __free_extent_tree()
343 en = rb_entry(node, struct extent_node, rb_node); in __free_extent_tree()
344 __release_extent_node(sbi, et, en); in __free_extent_tree()
348 return count - atomic_read(&et->node_cnt); in __free_extent_tree()
354 if (fofs < et->largest.fofs + et->largest.len && in __drop_largest_extent()
355 fofs + len > et->largest.fofs) { in __drop_largest_extent()
356 et->largest.len = 0; in __drop_largest_extent()
357 et->largest_updated = true; in __drop_largest_extent()
365 struct f2fs_extent *i_ext = ipage ? &F2FS_INODE(ipage)->i_ext : NULL; in __f2fs_init_extent_tree()
367 struct extent_node *en; in __f2fs_init_extent_tree() local
372 if (i_ext && i_ext->len) { in __f2fs_init_extent_tree()
374 i_ext->len = 0; in __f2fs_init_extent_tree()
383 if (!i_ext || !i_ext->len) in __f2fs_init_extent_tree()
388 write_lock(&et->lock); in __f2fs_init_extent_tree()
389 if (atomic_read(&et->node_cnt)) in __f2fs_init_extent_tree()
392 en = __init_extent_tree(sbi, et, &ei); in __f2fs_init_extent_tree()
393 if (en) { in __f2fs_init_extent_tree()
394 spin_lock(&sbi->extent_lock); in __f2fs_init_extent_tree()
395 list_add_tail(&en->list, &sbi->extent_list); in __f2fs_init_extent_tree()
396 spin_unlock(&sbi->extent_lock); in __f2fs_init_extent_tree()
399 write_unlock(&et->lock); in __f2fs_init_extent_tree()
406 if (!F2FS_I(inode)->extent_tree) in f2fs_init_extent_tree()
414 struct extent_tree *et = F2FS_I(inode)->extent_tree; in f2fs_lookup_extent_tree()
415 struct extent_node *en; in f2fs_lookup_extent_tree() local
422 read_lock(&et->lock); in f2fs_lookup_extent_tree()
424 if (et->largest.fofs <= pgofs && in f2fs_lookup_extent_tree()
425 et->largest.fofs + et->largest.len > pgofs) { in f2fs_lookup_extent_tree()
426 *ei = et->largest; in f2fs_lookup_extent_tree()
432 en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root, in f2fs_lookup_extent_tree()
433 (struct rb_entry *)et->cached_en, pgofs); in f2fs_lookup_extent_tree()
434 if (!en) in f2fs_lookup_extent_tree()
437 if (en == et->cached_en) in f2fs_lookup_extent_tree()
442 *ei = en->ei; in f2fs_lookup_extent_tree()
443 spin_lock(&sbi->extent_lock); in f2fs_lookup_extent_tree()
444 if (!list_empty(&en->list)) { in f2fs_lookup_extent_tree()
445 list_move_tail(&en->list, &sbi->extent_list); in f2fs_lookup_extent_tree()
446 et->cached_en = en; in f2fs_lookup_extent_tree()
448 spin_unlock(&sbi->extent_lock); in f2fs_lookup_extent_tree()
452 read_unlock(&et->lock); in f2fs_lookup_extent_tree()
463 struct extent_node *en = NULL; in __try_merge_extent_node() local
465 if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) { in __try_merge_extent_node()
466 prev_ex->ei.len += ei->len; in __try_merge_extent_node()
467 ei = &prev_ex->ei; in __try_merge_extent_node()
468 en = prev_ex; in __try_merge_extent_node()
471 if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) { in __try_merge_extent_node()
472 next_ex->ei.fofs = ei->fofs; in __try_merge_extent_node()
473 next_ex->ei.blk = ei->blk; in __try_merge_extent_node()
474 next_ex->ei.len += ei->len; in __try_merge_extent_node()
475 if (en) in __try_merge_extent_node()
478 en = next_ex; in __try_merge_extent_node()
481 if (!en) in __try_merge_extent_node()
484 __try_update_largest_extent(et, en); in __try_merge_extent_node()
486 spin_lock(&sbi->extent_lock); in __try_merge_extent_node()
487 if (!list_empty(&en->list)) { in __try_merge_extent_node()
488 list_move_tail(&en->list, &sbi->extent_list); in __try_merge_extent_node()
489 et->cached_en = en; in __try_merge_extent_node()
491 spin_unlock(&sbi->extent_lock); in __try_merge_extent_node()
492 return en; in __try_merge_extent_node()
503 struct extent_node *en = NULL; in __insert_extent_tree() local
513 p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent, in __insert_extent_tree()
514 ei->fofs, &leftmost); in __insert_extent_tree()
516 en = __attach_extent_node(sbi, et, ei, parent, p, leftmost); in __insert_extent_tree()
517 if (!en) in __insert_extent_tree()
520 __try_update_largest_extent(et, en); in __insert_extent_tree()
522 /* update in global extent list */ in __insert_extent_tree()
523 spin_lock(&sbi->extent_lock); in __insert_extent_tree()
524 list_add_tail(&en->list, &sbi->extent_list); in __insert_extent_tree()
525 et->cached_en = en; in __insert_extent_tree()
526 spin_unlock(&sbi->extent_lock); in __insert_extent_tree()
527 return en; in __insert_extent_tree()
534 struct extent_tree *et = F2FS_I(inode)->extent_tree; in f2fs_update_extent_tree_range()
535 struct extent_node *en = NULL, *en1 = NULL; in f2fs_update_extent_tree_range() local
549 write_lock(&et->lock); in f2fs_update_extent_tree_range()
552 write_unlock(&et->lock); in f2fs_update_extent_tree_range()
556 prev = et->largest; in f2fs_update_extent_tree_range()
565 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ in f2fs_update_extent_tree_range()
566 en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, in f2fs_update_extent_tree_range()
567 (struct rb_entry *)et->cached_en, fofs, in f2fs_update_extent_tree_range()
572 if (!en) in f2fs_update_extent_tree_range()
573 en = next_en; in f2fs_update_extent_tree_range()
575 /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */ in f2fs_update_extent_tree_range()
576 while (en && en->ei.fofs < end) { in f2fs_update_extent_tree_range()
582 dei = en->ei; in f2fs_update_extent_tree_range()
586 if (pos > dei.fofs && pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) { in f2fs_update_extent_tree_range()
587 en->ei.len = pos - en->ei.fofs; in f2fs_update_extent_tree_range()
588 prev_en = en; in f2fs_update_extent_tree_range()
592 if (end < org_end && org_end - end >= F2FS_MIN_EXTENT_LEN) { in f2fs_update_extent_tree_range()
595 end - dei.fofs + dei.blk, in f2fs_update_extent_tree_range()
596 org_end - end); in f2fs_update_extent_tree_range()
601 en->ei.fofs = end; in f2fs_update_extent_tree_range()
602 en->ei.blk += end - dei.fofs; in f2fs_update_extent_tree_range()
603 en->ei.len -= end - dei.fofs; in f2fs_update_extent_tree_range()
604 next_en = en; in f2fs_update_extent_tree_range()
610 struct rb_node *node = rb_next(&en->rb_node); in f2fs_update_extent_tree_range()
617 __try_update_largest_extent(et, en); in f2fs_update_extent_tree_range()
619 __release_extent_node(sbi, et, en); in f2fs_update_extent_tree_range()
630 en = next_en; in f2fs_update_extent_tree_range()
644 et->largest.len < F2FS_MIN_EXTENT_LEN) { in f2fs_update_extent_tree_range()
645 et->largest.len = 0; in f2fs_update_extent_tree_range()
646 et->largest_updated = true; in f2fs_update_extent_tree_range()
654 if (et->largest_updated) { in f2fs_update_extent_tree_range()
655 et->largest_updated = false; in f2fs_update_extent_tree_range()
659 write_unlock(&et->lock); in f2fs_update_extent_tree_range()
671 struct extent_tree *et = F2FS_I(inode)->extent_tree; in f2fs_update_extent_tree_range_compressed()
672 struct extent_node *en = NULL; in f2fs_update_extent_tree_range_compressed() local
680 /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */ in f2fs_update_extent_tree_range_compressed()
684 write_lock(&et->lock); in f2fs_update_extent_tree_range_compressed()
686 en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root, in f2fs_update_extent_tree_range_compressed()
687 (struct rb_entry *)et->cached_en, fofs, in f2fs_update_extent_tree_range_compressed()
692 if (en) in f2fs_update_extent_tree_range_compressed()
702 write_unlock(&et->lock); in f2fs_update_extent_tree_range_compressed()
709 struct extent_node *en; in f2fs_shrink_extent_tree() local
716 if (!atomic_read(&sbi->total_zombie_tree)) in f2fs_shrink_extent_tree()
719 if (!mutex_trylock(&sbi->extent_tree_lock)) in f2fs_shrink_extent_tree()
723 list_for_each_entry_safe(et, next, &sbi->zombie_list, list) { in f2fs_shrink_extent_tree()
724 if (atomic_read(&et->node_cnt)) { in f2fs_shrink_extent_tree()
725 write_lock(&et->lock); in f2fs_shrink_extent_tree()
727 write_unlock(&et->lock); in f2fs_shrink_extent_tree()
729 f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); in f2fs_shrink_extent_tree()
730 list_del_init(&et->list); in f2fs_shrink_extent_tree()
731 radix_tree_delete(&sbi->extent_tree_root, et->ino); in f2fs_shrink_extent_tree()
733 atomic_dec(&sbi->total_ext_tree); in f2fs_shrink_extent_tree()
734 atomic_dec(&sbi->total_zombie_tree); in f2fs_shrink_extent_tree()
741 mutex_unlock(&sbi->extent_tree_lock); in f2fs_shrink_extent_tree()
745 if (!mutex_trylock(&sbi->extent_tree_lock)) in f2fs_shrink_extent_tree()
748 remained = nr_shrink - (node_cnt + tree_cnt); in f2fs_shrink_extent_tree()
750 spin_lock(&sbi->extent_lock); in f2fs_shrink_extent_tree()
751 for (; remained > 0; remained--) { in f2fs_shrink_extent_tree()
752 if (list_empty(&sbi->extent_list)) in f2fs_shrink_extent_tree()
754 en = list_first_entry(&sbi->extent_list, in f2fs_shrink_extent_tree()
756 et = en->et; in f2fs_shrink_extent_tree()
757 if (!write_trylock(&et->lock)) { in f2fs_shrink_extent_tree()
759 list_move_tail(&en->list, &sbi->extent_list); in f2fs_shrink_extent_tree()
763 list_del_init(&en->list); in f2fs_shrink_extent_tree()
764 spin_unlock(&sbi->extent_lock); in f2fs_shrink_extent_tree()
766 __detach_extent_node(sbi, et, en); in f2fs_shrink_extent_tree()
768 write_unlock(&et->lock); in f2fs_shrink_extent_tree()
770 spin_lock(&sbi->extent_lock); in f2fs_shrink_extent_tree()
772 spin_unlock(&sbi->extent_lock); in f2fs_shrink_extent_tree()
775 mutex_unlock(&sbi->extent_tree_lock); in f2fs_shrink_extent_tree()
785 struct extent_tree *et = F2FS_I(inode)->extent_tree; in f2fs_destroy_extent_node()
788 if (!et || !atomic_read(&et->node_cnt)) in f2fs_destroy_extent_node()
791 write_lock(&et->lock); in f2fs_destroy_extent_node()
793 write_unlock(&et->lock); in f2fs_destroy_extent_node()
801 struct extent_tree *et = F2FS_I(inode)->extent_tree; in f2fs_drop_extent_tree()
807 write_lock(&et->lock); in f2fs_drop_extent_tree()
810 if (et->largest.len) { in f2fs_drop_extent_tree()
811 et->largest.len = 0; in f2fs_drop_extent_tree()
814 write_unlock(&et->lock); in f2fs_drop_extent_tree()
822 struct extent_tree *et = F2FS_I(inode)->extent_tree; in f2fs_destroy_extent_tree()
828 if (inode->i_nlink && !is_bad_inode(inode) && in f2fs_destroy_extent_tree()
829 atomic_read(&et->node_cnt)) { in f2fs_destroy_extent_tree()
830 mutex_lock(&sbi->extent_tree_lock); in f2fs_destroy_extent_tree()
831 list_add_tail(&et->list, &sbi->zombie_list); in f2fs_destroy_extent_tree()
832 atomic_inc(&sbi->total_zombie_tree); in f2fs_destroy_extent_tree()
833 mutex_unlock(&sbi->extent_tree_lock); in f2fs_destroy_extent_tree()
841 mutex_lock(&sbi->extent_tree_lock); in f2fs_destroy_extent_tree()
842 f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); in f2fs_destroy_extent_tree()
843 radix_tree_delete(&sbi->extent_tree_root, inode->i_ino); in f2fs_destroy_extent_tree()
845 atomic_dec(&sbi->total_ext_tree); in f2fs_destroy_extent_tree()
846 mutex_unlock(&sbi->extent_tree_lock); in f2fs_destroy_extent_tree()
848 F2FS_I(inode)->extent_tree = NULL; in f2fs_destroy_extent_tree()
867 if (!f2fs_may_extent_tree(dn->inode)) in f2fs_update_extent_cache()
870 if (dn->data_blkaddr == NEW_ADDR) in f2fs_update_extent_cache()
873 blkaddr = dn->data_blkaddr; in f2fs_update_extent_cache()
875 fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) + in f2fs_update_extent_cache()
876 dn->ofs_in_node; in f2fs_update_extent_cache()
877 f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, 1); in f2fs_update_extent_cache()
884 if (!f2fs_may_extent_tree(dn->inode)) in f2fs_update_extent_cache_range()
887 f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len); in f2fs_update_extent_cache_range()
892 INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO); in f2fs_init_extent_cache_info()
893 mutex_init(&sbi->extent_tree_lock); in f2fs_init_extent_cache_info()
894 INIT_LIST_HEAD(&sbi->extent_list); in f2fs_init_extent_cache_info()
895 spin_lock_init(&sbi->extent_lock); in f2fs_init_extent_cache_info()
896 atomic_set(&sbi->total_ext_tree, 0); in f2fs_init_extent_cache_info()
897 INIT_LIST_HEAD(&sbi->zombie_list); in f2fs_init_extent_cache_info()
898 atomic_set(&sbi->total_zombie_tree, 0); in f2fs_init_extent_cache_info()
899 atomic_set(&sbi->total_ext_node, 0); in f2fs_init_extent_cache_info()
907 return -ENOMEM; in f2fs_create_extent_cache()
912 return -ENOMEM; in f2fs_create_extent_cache()