1 // SPDX-License-Identifier: GPL-2.0
3 * f2fs extent cache support
5 * Copyright (c) 2015 Motorola Mobility
6 * Copyright (c) 2015 Samsung Electronics
7 * Authors: Jaegeuk Kim <jaegeuk@kernel.org>
8 * Chao Yu <chao2.yu@samsung.com>
10 * block_age-based extent cache added by:
11 * Copyright (c) 2022 xiaomi Co., Ltd.
12 * http://www.xiaomi.com/
16 #include <linux/f2fs_fs.h>
20 #include <trace/events/f2fs.h>
22 bool sanity_check_extent_cache(struct inode
*inode
)
24 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
25 struct f2fs_inode_info
*fi
= F2FS_I(inode
);
26 struct extent_tree
*et
= fi
->extent_tree
[EX_READ
];
27 struct extent_info
*ei
;
36 /* Let's drop, if checkpoint got corrupted. */
37 if (is_set_ckpt_flags(sbi
, CP_ERROR_FLAG
)) {
39 et
->largest_updated
= true;
43 if (!f2fs_is_valid_blkaddr(sbi
, ei
->blk
, DATA_GENERIC_ENHANCE
) ||
44 !f2fs_is_valid_blkaddr(sbi
, ei
->blk
+ ei
->len
- 1,
45 DATA_GENERIC_ENHANCE
)) {
46 set_sbi_flag(sbi
, SBI_NEED_FSCK
);
47 f2fs_warn(sbi
, "%s: inode (ino=%lx) extent info [%u, %u, %u] is incorrect, run fsck to fix",
48 __func__
, inode
->i_ino
,
49 ei
->blk
, ei
->fofs
, ei
->len
);
55 static void __set_extent_info(struct extent_info
*ei
,
56 unsigned int fofs
, unsigned int len
,
57 block_t blk
, bool keep_clen
,
58 unsigned long age
, unsigned long last_blocks
,
59 enum extent_type type
)
64 if (type
== EX_READ
) {
68 #ifdef CONFIG_F2FS_FS_COMPRESSION
71 } else if (type
== EX_BLOCK_AGE
) {
73 ei
->last_blocks
= last_blocks
;
77 static bool __may_read_extent_tree(struct inode
*inode
)
79 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
81 if (!test_opt(sbi
, READ_EXTENT_CACHE
))
83 if (is_inode_flag_set(inode
, FI_NO_EXTENT
))
85 if (is_inode_flag_set(inode
, FI_COMPRESSED_FILE
) &&
86 !f2fs_sb_has_readonly(sbi
))
88 return S_ISREG(inode
->i_mode
);
91 static bool __may_age_extent_tree(struct inode
*inode
)
93 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
95 if (!test_opt(sbi
, AGE_EXTENT_CACHE
))
97 if (is_inode_flag_set(inode
, FI_COMPRESSED_FILE
))
99 if (file_is_cold(inode
))
102 return S_ISREG(inode
->i_mode
) || S_ISDIR(inode
->i_mode
);
105 static bool __init_may_extent_tree(struct inode
*inode
, enum extent_type type
)
108 return __may_read_extent_tree(inode
);
109 else if (type
== EX_BLOCK_AGE
)
110 return __may_age_extent_tree(inode
);
114 static bool __may_extent_tree(struct inode
*inode
, enum extent_type type
)
117 * for recovered files during mount do not create extents
118 * if shrinker is not registered.
120 if (list_empty(&F2FS_I_SB(inode
)->s_list
))
123 return __init_may_extent_tree(inode
, type
);
126 static void __try_update_largest_extent(struct extent_tree
*et
,
127 struct extent_node
*en
)
129 if (et
->type
!= EX_READ
)
131 if (en
->ei
.len
<= et
->largest
.len
)
134 et
->largest
= en
->ei
;
135 et
->largest_updated
= true;
138 static bool __is_extent_mergeable(struct extent_info
*back
,
139 struct extent_info
*front
, enum extent_type type
)
141 if (type
== EX_READ
) {
142 #ifdef CONFIG_F2FS_FS_COMPRESSION
143 if (back
->c_len
&& back
->len
!= back
->c_len
)
145 if (front
->c_len
&& front
->len
!= front
->c_len
)
148 return (back
->fofs
+ back
->len
== front
->fofs
&&
149 back
->blk
+ back
->len
== front
->blk
);
150 } else if (type
== EX_BLOCK_AGE
) {
151 return (back
->fofs
+ back
->len
== front
->fofs
&&
152 abs(back
->age
- front
->age
) <= SAME_AGE_REGION
&&
153 abs(back
->last_blocks
- front
->last_blocks
) <=
159 static bool __is_back_mergeable(struct extent_info
*cur
,
160 struct extent_info
*back
, enum extent_type type
)
162 return __is_extent_mergeable(back
, cur
, type
);
165 static bool __is_front_mergeable(struct extent_info
*cur
,
166 struct extent_info
*front
, enum extent_type type
)
168 return __is_extent_mergeable(cur
, front
, type
);
171 static struct extent_node
*__lookup_extent_node(struct rb_root_cached
*root
,
172 struct extent_node
*cached_en
, unsigned int fofs
)
174 struct rb_node
*node
= root
->rb_root
.rb_node
;
175 struct extent_node
*en
;
177 /* check a cached entry */
178 if (cached_en
&& cached_en
->ei
.fofs
<= fofs
&&
179 cached_en
->ei
.fofs
+ cached_en
->ei
.len
> fofs
)
184 en
= rb_entry(node
, struct extent_node
, rb_node
);
186 if (fofs
< en
->ei
.fofs
)
187 node
= node
->rb_left
;
188 else if (fofs
>= en
->ei
.fofs
+ en
->ei
.len
)
189 node
= node
->rb_right
;
197 * lookup rb entry in position of @fofs in rb-tree,
198 * if hit, return the entry, otherwise, return NULL
199 * @prev_ex: extent before fofs
200 * @next_ex: extent after fofs
201 * @insert_p: insert point for new extent at fofs
202 * in order to simplify the insertion after.
203 * tree must stay unchanged between lookup and insertion.
205 static struct extent_node
*__lookup_extent_node_ret(struct rb_root_cached
*root
,
206 struct extent_node
*cached_en
,
208 struct extent_node
**prev_entry
,
209 struct extent_node
**next_entry
,
210 struct rb_node
***insert_p
,
211 struct rb_node
**insert_parent
,
214 struct rb_node
**pnode
= &root
->rb_root
.rb_node
;
215 struct rb_node
*parent
= NULL
, *tmp_node
;
216 struct extent_node
*en
= cached_en
;
219 *insert_parent
= NULL
;
223 if (RB_EMPTY_ROOT(&root
->rb_root
))
226 if (en
&& en
->ei
.fofs
<= fofs
&& en
->ei
.fofs
+ en
->ei
.len
> fofs
)
227 goto lookup_neighbors
;
233 en
= rb_entry(*pnode
, struct extent_node
, rb_node
);
235 if (fofs
< en
->ei
.fofs
) {
236 pnode
= &(*pnode
)->rb_left
;
237 } else if (fofs
>= en
->ei
.fofs
+ en
->ei
.len
) {
238 pnode
= &(*pnode
)->rb_right
;
241 goto lookup_neighbors
;
246 *insert_parent
= parent
;
248 en
= rb_entry(parent
, struct extent_node
, rb_node
);
250 if (parent
&& fofs
> en
->ei
.fofs
)
251 tmp_node
= rb_next(parent
);
252 *next_entry
= rb_entry_safe(tmp_node
, struct extent_node
, rb_node
);
255 if (parent
&& fofs
< en
->ei
.fofs
)
256 tmp_node
= rb_prev(parent
);
257 *prev_entry
= rb_entry_safe(tmp_node
, struct extent_node
, rb_node
);
261 if (fofs
== en
->ei
.fofs
) {
262 /* lookup prev node for merging backward later */
263 tmp_node
= rb_prev(&en
->rb_node
);
264 *prev_entry
= rb_entry_safe(tmp_node
,
265 struct extent_node
, rb_node
);
267 if (fofs
== en
->ei
.fofs
+ en
->ei
.len
- 1) {
268 /* lookup next node for merging frontward later */
269 tmp_node
= rb_next(&en
->rb_node
);
270 *next_entry
= rb_entry_safe(tmp_node
,
271 struct extent_node
, rb_node
);
276 static struct kmem_cache
*extent_tree_slab
;
277 static struct kmem_cache
*extent_node_slab
;
279 static struct extent_node
*__attach_extent_node(struct f2fs_sb_info
*sbi
,
280 struct extent_tree
*et
, struct extent_info
*ei
,
281 struct rb_node
*parent
, struct rb_node
**p
,
284 struct extent_tree_info
*eti
= &sbi
->extent_tree
[et
->type
];
285 struct extent_node
*en
;
287 en
= f2fs_kmem_cache_alloc(extent_node_slab
, GFP_ATOMIC
, false, sbi
);
292 INIT_LIST_HEAD(&en
->list
);
295 rb_link_node(&en
->rb_node
, parent
, p
);
296 rb_insert_color_cached(&en
->rb_node
, &et
->root
, leftmost
);
297 atomic_inc(&et
->node_cnt
);
298 atomic_inc(&eti
->total_ext_node
);
302 static void __detach_extent_node(struct f2fs_sb_info
*sbi
,
303 struct extent_tree
*et
, struct extent_node
*en
)
305 struct extent_tree_info
*eti
= &sbi
->extent_tree
[et
->type
];
307 rb_erase_cached(&en
->rb_node
, &et
->root
);
308 atomic_dec(&et
->node_cnt
);
309 atomic_dec(&eti
->total_ext_node
);
311 if (et
->cached_en
== en
)
312 et
->cached_en
= NULL
;
313 kmem_cache_free(extent_node_slab
, en
);
317 * Flow to release an extent_node:
319 * 2. __detach_extent_node
320 * 3. kmem_cache_free.
322 static void __release_extent_node(struct f2fs_sb_info
*sbi
,
323 struct extent_tree
*et
, struct extent_node
*en
)
325 struct extent_tree_info
*eti
= &sbi
->extent_tree
[et
->type
];
327 spin_lock(&eti
->extent_lock
);
328 f2fs_bug_on(sbi
, list_empty(&en
->list
));
329 list_del_init(&en
->list
);
330 spin_unlock(&eti
->extent_lock
);
332 __detach_extent_node(sbi
, et
, en
);
335 static struct extent_tree
*__grab_extent_tree(struct inode
*inode
,
336 enum extent_type type
)
338 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
339 struct extent_tree_info
*eti
= &sbi
->extent_tree
[type
];
340 struct extent_tree
*et
;
341 nid_t ino
= inode
->i_ino
;
343 mutex_lock(&eti
->extent_tree_lock
);
344 et
= radix_tree_lookup(&eti
->extent_tree_root
, ino
);
346 et
= f2fs_kmem_cache_alloc(extent_tree_slab
,
347 GFP_NOFS
, true, NULL
);
348 f2fs_radix_tree_insert(&eti
->extent_tree_root
, ino
, et
);
349 memset(et
, 0, sizeof(struct extent_tree
));
352 et
->root
= RB_ROOT_CACHED
;
353 et
->cached_en
= NULL
;
354 rwlock_init(&et
->lock
);
355 INIT_LIST_HEAD(&et
->list
);
356 atomic_set(&et
->node_cnt
, 0);
357 atomic_inc(&eti
->total_ext_tree
);
359 atomic_dec(&eti
->total_zombie_tree
);
360 list_del_init(&et
->list
);
362 mutex_unlock(&eti
->extent_tree_lock
);
364 /* never died until evict_inode */
365 F2FS_I(inode
)->extent_tree
[type
] = et
;
370 static unsigned int __free_extent_tree(struct f2fs_sb_info
*sbi
,
371 struct extent_tree
*et
)
373 struct rb_node
*node
, *next
;
374 struct extent_node
*en
;
375 unsigned int count
= atomic_read(&et
->node_cnt
);
377 node
= rb_first_cached(&et
->root
);
379 next
= rb_next(node
);
380 en
= rb_entry(node
, struct extent_node
, rb_node
);
381 __release_extent_node(sbi
, et
, en
);
385 return count
- atomic_read(&et
->node_cnt
);
388 static void __drop_largest_extent(struct extent_tree
*et
,
389 pgoff_t fofs
, unsigned int len
)
391 if (fofs
< et
->largest
.fofs
+ et
->largest
.len
&&
392 fofs
+ len
> et
->largest
.fofs
) {
394 et
->largest_updated
= true;
398 void f2fs_init_read_extent_tree(struct inode
*inode
, struct page
*ipage
)
400 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
401 struct extent_tree_info
*eti
= &sbi
->extent_tree
[EX_READ
];
402 struct f2fs_extent
*i_ext
= &F2FS_INODE(ipage
)->i_ext
;
403 struct extent_tree
*et
;
404 struct extent_node
*en
;
405 struct extent_info ei
;
407 if (!__may_extent_tree(inode
, EX_READ
)) {
408 /* drop largest read extent */
409 if (i_ext
&& i_ext
->len
) {
410 f2fs_wait_on_page_writeback(ipage
, NODE
, true, true);
412 set_page_dirty(ipage
);
417 et
= __grab_extent_tree(inode
, EX_READ
);
419 if (!i_ext
|| !i_ext
->len
)
422 get_read_extent_info(&ei
, i_ext
);
424 write_lock(&et
->lock
);
425 if (atomic_read(&et
->node_cnt
))
428 en
= __attach_extent_node(sbi
, et
, &ei
, NULL
,
429 &et
->root
.rb_root
.rb_node
, true);
431 et
->largest
= en
->ei
;
434 spin_lock(&eti
->extent_lock
);
435 list_add_tail(&en
->list
, &eti
->extent_list
);
436 spin_unlock(&eti
->extent_lock
);
439 write_unlock(&et
->lock
);
441 if (!F2FS_I(inode
)->extent_tree
[EX_READ
])
442 set_inode_flag(inode
, FI_NO_EXTENT
);
445 void f2fs_init_age_extent_tree(struct inode
*inode
)
447 if (!__init_may_extent_tree(inode
, EX_BLOCK_AGE
))
449 __grab_extent_tree(inode
, EX_BLOCK_AGE
);
452 void f2fs_init_extent_tree(struct inode
*inode
)
454 /* initialize read cache */
455 if (__init_may_extent_tree(inode
, EX_READ
))
456 __grab_extent_tree(inode
, EX_READ
);
458 /* initialize block age cache */
459 if (__init_may_extent_tree(inode
, EX_BLOCK_AGE
))
460 __grab_extent_tree(inode
, EX_BLOCK_AGE
);
463 static bool __lookup_extent_tree(struct inode
*inode
, pgoff_t pgofs
,
464 struct extent_info
*ei
, enum extent_type type
)
466 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
467 struct extent_tree_info
*eti
= &sbi
->extent_tree
[type
];
468 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
[type
];
469 struct extent_node
*en
;
475 trace_f2fs_lookup_extent_tree_start(inode
, pgofs
, type
);
477 read_lock(&et
->lock
);
479 if (type
== EX_READ
&&
480 et
->largest
.fofs
<= pgofs
&&
481 et
->largest
.fofs
+ et
->largest
.len
> pgofs
) {
484 stat_inc_largest_node_hit(sbi
);
488 en
= __lookup_extent_node(&et
->root
, et
->cached_en
, pgofs
);
492 if (en
== et
->cached_en
)
493 stat_inc_cached_node_hit(sbi
, type
);
495 stat_inc_rbtree_node_hit(sbi
, type
);
498 spin_lock(&eti
->extent_lock
);
499 if (!list_empty(&en
->list
)) {
500 list_move_tail(&en
->list
, &eti
->extent_list
);
503 spin_unlock(&eti
->extent_lock
);
506 stat_inc_total_hit(sbi
, type
);
507 read_unlock(&et
->lock
);
510 trace_f2fs_lookup_read_extent_tree_end(inode
, pgofs
, ei
);
511 else if (type
== EX_BLOCK_AGE
)
512 trace_f2fs_lookup_age_extent_tree_end(inode
, pgofs
, ei
);
516 static struct extent_node
*__try_merge_extent_node(struct f2fs_sb_info
*sbi
,
517 struct extent_tree
*et
, struct extent_info
*ei
,
518 struct extent_node
*prev_ex
,
519 struct extent_node
*next_ex
)
521 struct extent_tree_info
*eti
= &sbi
->extent_tree
[et
->type
];
522 struct extent_node
*en
= NULL
;
524 if (prev_ex
&& __is_back_mergeable(ei
, &prev_ex
->ei
, et
->type
)) {
525 prev_ex
->ei
.len
+= ei
->len
;
530 if (next_ex
&& __is_front_mergeable(ei
, &next_ex
->ei
, et
->type
)) {
531 next_ex
->ei
.fofs
= ei
->fofs
;
532 next_ex
->ei
.len
+= ei
->len
;
533 if (et
->type
== EX_READ
)
534 next_ex
->ei
.blk
= ei
->blk
;
536 __release_extent_node(sbi
, et
, prev_ex
);
544 __try_update_largest_extent(et
, en
);
546 spin_lock(&eti
->extent_lock
);
547 if (!list_empty(&en
->list
)) {
548 list_move_tail(&en
->list
, &eti
->extent_list
);
551 spin_unlock(&eti
->extent_lock
);
555 static struct extent_node
*__insert_extent_tree(struct f2fs_sb_info
*sbi
,
556 struct extent_tree
*et
, struct extent_info
*ei
,
557 struct rb_node
**insert_p
,
558 struct rb_node
*insert_parent
,
561 struct extent_tree_info
*eti
= &sbi
->extent_tree
[et
->type
];
562 struct rb_node
**p
= &et
->root
.rb_root
.rb_node
;
563 struct rb_node
*parent
= NULL
;
564 struct extent_node
*en
= NULL
;
566 if (insert_p
&& insert_parent
) {
567 parent
= insert_parent
;
574 /* look up extent_node in the rb tree */
577 en
= rb_entry(parent
, struct extent_node
, rb_node
);
579 if (ei
->fofs
< en
->ei
.fofs
) {
581 } else if (ei
->fofs
>= en
->ei
.fofs
+ en
->ei
.len
) {
590 en
= __attach_extent_node(sbi
, et
, ei
, parent
, p
, leftmost
);
594 __try_update_largest_extent(et
, en
);
596 /* update in global extent list */
597 spin_lock(&eti
->extent_lock
);
598 list_add_tail(&en
->list
, &eti
->extent_list
);
600 spin_unlock(&eti
->extent_lock
);
604 static void __update_extent_tree_range(struct inode
*inode
,
605 struct extent_info
*tei
, enum extent_type type
)
607 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
608 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
[type
];
609 struct extent_node
*en
= NULL
, *en1
= NULL
;
610 struct extent_node
*prev_en
= NULL
, *next_en
= NULL
;
611 struct extent_info ei
, dei
, prev
;
612 struct rb_node
**insert_p
= NULL
, *insert_parent
= NULL
;
613 unsigned int fofs
= tei
->fofs
, len
= tei
->len
;
614 unsigned int end
= fofs
+ len
;
615 bool updated
= false;
616 bool leftmost
= false;
622 trace_f2fs_update_read_extent_tree_range(inode
, fofs
, len
,
624 else if (type
== EX_BLOCK_AGE
)
625 trace_f2fs_update_age_extent_tree_range(inode
, fofs
, len
,
626 tei
->age
, tei
->last_blocks
);
628 write_lock(&et
->lock
);
630 if (type
== EX_READ
) {
631 if (is_inode_flag_set(inode
, FI_NO_EXTENT
)) {
632 write_unlock(&et
->lock
);
640 * drop largest extent before lookup, in case it's already
641 * been shrunk from extent tree
643 __drop_largest_extent(et
, fofs
, len
);
646 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
647 en
= __lookup_extent_node_ret(&et
->root
,
650 &insert_p
, &insert_parent
,
655 /* 2. invalidate all extent nodes in range [fofs, fofs + len - 1] */
656 while (en
&& en
->ei
.fofs
< end
) {
657 unsigned int org_end
;
658 int parts
= 0; /* # of parts current extent split into */
660 next_en
= en1
= NULL
;
663 org_end
= dei
.fofs
+ dei
.len
;
664 f2fs_bug_on(sbi
, fofs
>= org_end
);
666 if (fofs
> dei
.fofs
&& (type
!= EX_READ
||
667 fofs
- dei
.fofs
>= F2FS_MIN_EXTENT_LEN
)) {
668 en
->ei
.len
= fofs
- en
->ei
.fofs
;
673 if (end
< org_end
&& (type
!= EX_READ
||
674 org_end
- end
>= F2FS_MIN_EXTENT_LEN
)) {
676 __set_extent_info(&ei
,
678 end
- dei
.fofs
+ dei
.blk
, false,
679 dei
.age
, dei
.last_blocks
,
681 en1
= __insert_extent_tree(sbi
, et
, &ei
,
685 __set_extent_info(&en
->ei
,
686 end
, en
->ei
.len
- (end
- dei
.fofs
),
687 en
->ei
.blk
+ (end
- dei
.fofs
), true,
688 dei
.age
, dei
.last_blocks
,
696 struct rb_node
*node
= rb_next(&en
->rb_node
);
698 next_en
= rb_entry_safe(node
, struct extent_node
,
703 __try_update_largest_extent(et
, en
);
705 __release_extent_node(sbi
, et
, en
);
708 * if original extent is split into zero or two parts, extent
709 * tree has been altered by deletion or insertion, therefore
710 * invalidate pointers regard to tree.
714 insert_parent
= NULL
;
719 if (type
== EX_BLOCK_AGE
)
720 goto update_age_extent_cache
;
722 /* 3. update extent in read extent cache */
723 BUG_ON(type
!= EX_READ
);
726 __set_extent_info(&ei
, fofs
, len
, tei
->blk
, false,
728 if (!__try_merge_extent_node(sbi
, et
, &ei
, prev_en
, next_en
))
729 __insert_extent_tree(sbi
, et
, &ei
,
730 insert_p
, insert_parent
, leftmost
);
732 /* give up extent_cache, if split and small updates happen */
734 prev
.len
< F2FS_MIN_EXTENT_LEN
&&
735 et
->largest
.len
< F2FS_MIN_EXTENT_LEN
) {
737 et
->largest_updated
= true;
738 set_inode_flag(inode
, FI_NO_EXTENT
);
742 if (is_inode_flag_set(inode
, FI_NO_EXTENT
))
743 __free_extent_tree(sbi
, et
);
745 if (et
->largest_updated
) {
746 et
->largest_updated
= false;
749 goto out_read_extent_cache
;
750 update_age_extent_cache
:
751 if (!tei
->last_blocks
)
752 goto out_read_extent_cache
;
754 __set_extent_info(&ei
, fofs
, len
, 0, false,
755 tei
->age
, tei
->last_blocks
, EX_BLOCK_AGE
);
756 if (!__try_merge_extent_node(sbi
, et
, &ei
, prev_en
, next_en
))
757 __insert_extent_tree(sbi
, et
, &ei
,
758 insert_p
, insert_parent
, leftmost
);
759 out_read_extent_cache
:
760 write_unlock(&et
->lock
);
763 f2fs_mark_inode_dirty_sync(inode
, true);
766 #ifdef CONFIG_F2FS_FS_COMPRESSION
767 void f2fs_update_read_extent_tree_range_compressed(struct inode
*inode
,
768 pgoff_t fofs
, block_t blkaddr
, unsigned int llen
,
771 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
772 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
[EX_READ
];
773 struct extent_node
*en
= NULL
;
774 struct extent_node
*prev_en
= NULL
, *next_en
= NULL
;
775 struct extent_info ei
;
776 struct rb_node
**insert_p
= NULL
, *insert_parent
= NULL
;
777 bool leftmost
= false;
779 trace_f2fs_update_read_extent_tree_range(inode
, fofs
, llen
,
782 /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */
783 if (is_inode_flag_set(inode
, FI_NO_EXTENT
))
786 write_lock(&et
->lock
);
788 en
= __lookup_extent_node_ret(&et
->root
,
791 &insert_p
, &insert_parent
,
796 __set_extent_info(&ei
, fofs
, llen
, blkaddr
, true, 0, 0, EX_READ
);
799 if (!__try_merge_extent_node(sbi
, et
, &ei
, prev_en
, next_en
))
800 __insert_extent_tree(sbi
, et
, &ei
,
801 insert_p
, insert_parent
, leftmost
);
803 write_unlock(&et
->lock
);
807 static unsigned long long __calculate_block_age(struct f2fs_sb_info
*sbi
,
808 unsigned long long new,
809 unsigned long long old
)
811 unsigned int rem_old
, rem_new
;
812 unsigned long long res
;
813 unsigned int weight
= sbi
->last_age_weight
;
815 res
= div_u64_rem(new, 100, &rem_new
) * (100 - weight
)
816 + div_u64_rem(old
, 100, &rem_old
) * weight
;
819 res
+= rem_new
* (100 - weight
) / 100;
821 res
+= rem_old
* weight
/ 100;
826 /* This returns a new age and allocated blocks in ei */
827 static int __get_new_block_age(struct inode
*inode
, struct extent_info
*ei
,
830 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
831 loff_t f_size
= i_size_read(inode
);
832 unsigned long long cur_blocks
=
833 atomic64_read(&sbi
->allocated_data_blocks
);
834 struct extent_info tei
= *ei
; /* only fofs and len are valid */
837 * When I/O is not aligned to a PAGE_SIZE, update will happen to the last
838 * file block even in seq write. So don't record age for newly last file
841 if ((f_size
>> PAGE_SHIFT
) == ei
->fofs
&& f_size
& (PAGE_SIZE
- 1) &&
845 if (__lookup_extent_tree(inode
, ei
->fofs
, &tei
, EX_BLOCK_AGE
)) {
846 unsigned long long cur_age
;
848 if (cur_blocks
>= tei
.last_blocks
)
849 cur_age
= cur_blocks
- tei
.last_blocks
;
851 /* allocated_data_blocks overflow */
852 cur_age
= ULLONG_MAX
- tei
.last_blocks
+ cur_blocks
;
855 ei
->age
= __calculate_block_age(sbi
, cur_age
, tei
.age
);
858 ei
->last_blocks
= cur_blocks
;
859 WARN_ON(ei
->age
> cur_blocks
);
863 f2fs_bug_on(sbi
, blkaddr
== NULL_ADDR
);
865 /* the data block was allocated for the first time */
866 if (blkaddr
== NEW_ADDR
)
869 if (__is_valid_data_blkaddr(blkaddr
) &&
870 !f2fs_is_valid_blkaddr(sbi
, blkaddr
, DATA_GENERIC_ENHANCE
)) {
876 * init block age with zero, this can happen when the block age extent
877 * was reclaimed due to memory constraint or system reboot
880 ei
->last_blocks
= cur_blocks
;
884 static void __update_extent_cache(struct dnode_of_data
*dn
, enum extent_type type
)
886 struct extent_info ei
= {};
888 if (!__may_extent_tree(dn
->inode
, type
))
891 ei
.fofs
= f2fs_start_bidx_of_node(ofs_of_node(dn
->node_page
), dn
->inode
) +
895 if (type
== EX_READ
) {
896 if (dn
->data_blkaddr
== NEW_ADDR
)
899 ei
.blk
= dn
->data_blkaddr
;
900 } else if (type
== EX_BLOCK_AGE
) {
901 if (__get_new_block_age(dn
->inode
, &ei
, dn
->data_blkaddr
))
904 __update_extent_tree_range(dn
->inode
, &ei
, type
);
907 static unsigned int __shrink_extent_tree(struct f2fs_sb_info
*sbi
, int nr_shrink
,
908 enum extent_type type
)
910 struct extent_tree_info
*eti
= &sbi
->extent_tree
[type
];
911 struct extent_tree
*et
, *next
;
912 struct extent_node
*en
;
913 unsigned int node_cnt
= 0, tree_cnt
= 0;
916 if (!atomic_read(&eti
->total_zombie_tree
))
919 if (!mutex_trylock(&eti
->extent_tree_lock
))
922 /* 1. remove unreferenced extent tree */
923 list_for_each_entry_safe(et
, next
, &eti
->zombie_list
, list
) {
924 if (atomic_read(&et
->node_cnt
)) {
925 write_lock(&et
->lock
);
926 node_cnt
+= __free_extent_tree(sbi
, et
);
927 write_unlock(&et
->lock
);
929 f2fs_bug_on(sbi
, atomic_read(&et
->node_cnt
));
930 list_del_init(&et
->list
);
931 radix_tree_delete(&eti
->extent_tree_root
, et
->ino
);
932 kmem_cache_free(extent_tree_slab
, et
);
933 atomic_dec(&eti
->total_ext_tree
);
934 atomic_dec(&eti
->total_zombie_tree
);
937 if (node_cnt
+ tree_cnt
>= nr_shrink
)
941 mutex_unlock(&eti
->extent_tree_lock
);
944 /* 2. remove LRU extent entries */
945 if (!mutex_trylock(&eti
->extent_tree_lock
))
948 remained
= nr_shrink
- (node_cnt
+ tree_cnt
);
950 spin_lock(&eti
->extent_lock
);
951 for (; remained
> 0; remained
--) {
952 if (list_empty(&eti
->extent_list
))
954 en
= list_first_entry(&eti
->extent_list
,
955 struct extent_node
, list
);
957 if (!write_trylock(&et
->lock
)) {
958 /* refresh this extent node's position in extent list */
959 list_move_tail(&en
->list
, &eti
->extent_list
);
963 list_del_init(&en
->list
);
964 spin_unlock(&eti
->extent_lock
);
966 __detach_extent_node(sbi
, et
, en
);
968 write_unlock(&et
->lock
);
970 spin_lock(&eti
->extent_lock
);
972 spin_unlock(&eti
->extent_lock
);
975 mutex_unlock(&eti
->extent_tree_lock
);
977 trace_f2fs_shrink_extent_tree(sbi
, node_cnt
, tree_cnt
, type
);
979 return node_cnt
+ tree_cnt
;
982 /* read extent cache operations */
983 bool f2fs_lookup_read_extent_cache(struct inode
*inode
, pgoff_t pgofs
,
984 struct extent_info
*ei
)
986 if (!__may_extent_tree(inode
, EX_READ
))
989 return __lookup_extent_tree(inode
, pgofs
, ei
, EX_READ
);
992 bool f2fs_lookup_read_extent_cache_block(struct inode
*inode
, pgoff_t index
,
995 struct extent_info ei
= {};
997 if (!f2fs_lookup_read_extent_cache(inode
, index
, &ei
))
999 *blkaddr
= ei
.blk
+ index
- ei
.fofs
;
1003 void f2fs_update_read_extent_cache(struct dnode_of_data
*dn
)
1005 return __update_extent_cache(dn
, EX_READ
);
1008 void f2fs_update_read_extent_cache_range(struct dnode_of_data
*dn
,
1009 pgoff_t fofs
, block_t blkaddr
, unsigned int len
)
1011 struct extent_info ei
= {
1017 if (!__may_extent_tree(dn
->inode
, EX_READ
))
1020 __update_extent_tree_range(dn
->inode
, &ei
, EX_READ
);
1023 unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info
*sbi
, int nr_shrink
)
1025 if (!test_opt(sbi
, READ_EXTENT_CACHE
))
1028 return __shrink_extent_tree(sbi
, nr_shrink
, EX_READ
);
1031 /* block age extent cache operations */
1032 bool f2fs_lookup_age_extent_cache(struct inode
*inode
, pgoff_t pgofs
,
1033 struct extent_info
*ei
)
1035 if (!__may_extent_tree(inode
, EX_BLOCK_AGE
))
1038 return __lookup_extent_tree(inode
, pgofs
, ei
, EX_BLOCK_AGE
);
1041 void f2fs_update_age_extent_cache(struct dnode_of_data
*dn
)
1043 return __update_extent_cache(dn
, EX_BLOCK_AGE
);
1046 void f2fs_update_age_extent_cache_range(struct dnode_of_data
*dn
,
1047 pgoff_t fofs
, unsigned int len
)
1049 struct extent_info ei
= {
1054 if (!__may_extent_tree(dn
->inode
, EX_BLOCK_AGE
))
1057 __update_extent_tree_range(dn
->inode
, &ei
, EX_BLOCK_AGE
);
1060 unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info
*sbi
, int nr_shrink
)
1062 if (!test_opt(sbi
, AGE_EXTENT_CACHE
))
1065 return __shrink_extent_tree(sbi
, nr_shrink
, EX_BLOCK_AGE
);
1068 static unsigned int __destroy_extent_node(struct inode
*inode
,
1069 enum extent_type type
)
1071 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
1072 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
[type
];
1073 unsigned int node_cnt
= 0;
1075 if (!et
|| !atomic_read(&et
->node_cnt
))
1078 write_lock(&et
->lock
);
1079 node_cnt
= __free_extent_tree(sbi
, et
);
1080 write_unlock(&et
->lock
);
1085 void f2fs_destroy_extent_node(struct inode
*inode
)
1087 __destroy_extent_node(inode
, EX_READ
);
1088 __destroy_extent_node(inode
, EX_BLOCK_AGE
);
1091 static void __drop_extent_tree(struct inode
*inode
, enum extent_type type
)
1093 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
1094 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
[type
];
1095 bool updated
= false;
1097 if (!__may_extent_tree(inode
, type
))
1100 write_lock(&et
->lock
);
1101 __free_extent_tree(sbi
, et
);
1102 if (type
== EX_READ
) {
1103 set_inode_flag(inode
, FI_NO_EXTENT
);
1104 if (et
->largest
.len
) {
1105 et
->largest
.len
= 0;
1109 write_unlock(&et
->lock
);
1111 f2fs_mark_inode_dirty_sync(inode
, true);
1114 void f2fs_drop_extent_tree(struct inode
*inode
)
1116 __drop_extent_tree(inode
, EX_READ
);
1117 __drop_extent_tree(inode
, EX_BLOCK_AGE
);
1120 static void __destroy_extent_tree(struct inode
*inode
, enum extent_type type
)
1122 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
1123 struct extent_tree_info
*eti
= &sbi
->extent_tree
[type
];
1124 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
[type
];
1125 unsigned int node_cnt
= 0;
1130 if (inode
->i_nlink
&& !is_bad_inode(inode
) &&
1131 atomic_read(&et
->node_cnt
)) {
1132 mutex_lock(&eti
->extent_tree_lock
);
1133 list_add_tail(&et
->list
, &eti
->zombie_list
);
1134 atomic_inc(&eti
->total_zombie_tree
);
1135 mutex_unlock(&eti
->extent_tree_lock
);
1139 /* free all extent info belong to this extent tree */
1140 node_cnt
= __destroy_extent_node(inode
, type
);
1142 /* delete extent tree entry in radix tree */
1143 mutex_lock(&eti
->extent_tree_lock
);
1144 f2fs_bug_on(sbi
, atomic_read(&et
->node_cnt
));
1145 radix_tree_delete(&eti
->extent_tree_root
, inode
->i_ino
);
1146 kmem_cache_free(extent_tree_slab
, et
);
1147 atomic_dec(&eti
->total_ext_tree
);
1148 mutex_unlock(&eti
->extent_tree_lock
);
1150 F2FS_I(inode
)->extent_tree
[type
] = NULL
;
1152 trace_f2fs_destroy_extent_tree(inode
, node_cnt
, type
);
1155 void f2fs_destroy_extent_tree(struct inode
*inode
)
1157 __destroy_extent_tree(inode
, EX_READ
);
1158 __destroy_extent_tree(inode
, EX_BLOCK_AGE
);
1161 static void __init_extent_tree_info(struct extent_tree_info
*eti
)
1163 INIT_RADIX_TREE(&eti
->extent_tree_root
, GFP_NOIO
);
1164 mutex_init(&eti
->extent_tree_lock
);
1165 INIT_LIST_HEAD(&eti
->extent_list
);
1166 spin_lock_init(&eti
->extent_lock
);
1167 atomic_set(&eti
->total_ext_tree
, 0);
1168 INIT_LIST_HEAD(&eti
->zombie_list
);
1169 atomic_set(&eti
->total_zombie_tree
, 0);
1170 atomic_set(&eti
->total_ext_node
, 0);
1173 void f2fs_init_extent_cache_info(struct f2fs_sb_info
*sbi
)
1175 __init_extent_tree_info(&sbi
->extent_tree
[EX_READ
]);
1176 __init_extent_tree_info(&sbi
->extent_tree
[EX_BLOCK_AGE
]);
1178 /* initialize for block age extents */
1179 atomic64_set(&sbi
->allocated_data_blocks
, 0);
1180 sbi
->hot_data_age_threshold
= DEF_HOT_DATA_AGE_THRESHOLD
;
1181 sbi
->warm_data_age_threshold
= DEF_WARM_DATA_AGE_THRESHOLD
;
1182 sbi
->last_age_weight
= LAST_AGE_WEIGHT
;
1185 int __init
f2fs_create_extent_cache(void)
1187 extent_tree_slab
= f2fs_kmem_cache_create("f2fs_extent_tree",
1188 sizeof(struct extent_tree
));
1189 if (!extent_tree_slab
)
1191 extent_node_slab
= f2fs_kmem_cache_create("f2fs_extent_node",
1192 sizeof(struct extent_node
));
1193 if (!extent_node_slab
) {
1194 kmem_cache_destroy(extent_tree_slab
);
1200 void f2fs_destroy_extent_cache(void)
1202 kmem_cache_destroy(extent_node_slab
);
1203 kmem_cache_destroy(extent_tree_slab
);