2 * f2fs extent cache support
4 * Copyright (c) 2015 Motorola Mobility
5 * Copyright (c) 2015 Samsung Electronics
6 * Authors: Jaegeuk Kim <jaegeuk@kernel.org>
7 * Chao Yu <chao2.yu@samsung.com>
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
15 #include <linux/f2fs_fs.h>
19 #include <trace/events/f2fs.h>
21 static struct kmem_cache
*extent_tree_slab
;
22 static struct kmem_cache
*extent_node_slab
;
24 static struct extent_node
*__attach_extent_node(struct f2fs_sb_info
*sbi
,
25 struct extent_tree
*et
, struct extent_info
*ei
,
26 struct rb_node
*parent
, struct rb_node
**p
)
28 struct extent_node
*en
;
30 en
= kmem_cache_alloc(extent_node_slab
, GFP_ATOMIC
);
35 INIT_LIST_HEAD(&en
->list
);
38 rb_link_node(&en
->rb_node
, parent
, p
);
39 rb_insert_color(&en
->rb_node
, &et
->root
);
40 atomic_inc(&et
->node_cnt
);
41 atomic_inc(&sbi
->total_ext_node
);
45 static void __detach_extent_node(struct f2fs_sb_info
*sbi
,
46 struct extent_tree
*et
, struct extent_node
*en
)
48 rb_erase(&en
->rb_node
, &et
->root
);
49 atomic_dec(&et
->node_cnt
);
50 atomic_dec(&sbi
->total_ext_node
);
52 if (et
->cached_en
== en
)
54 kmem_cache_free(extent_node_slab
, en
);
58 * Flow to release an extent_node:
60 * 2. __detach_extent_node
63 static void __release_extent_node(struct f2fs_sb_info
*sbi
,
64 struct extent_tree
*et
, struct extent_node
*en
)
66 spin_lock(&sbi
->extent_lock
);
67 f2fs_bug_on(sbi
, list_empty(&en
->list
));
68 list_del_init(&en
->list
);
69 spin_unlock(&sbi
->extent_lock
);
71 __detach_extent_node(sbi
, et
, en
);
74 static struct extent_tree
*__grab_extent_tree(struct inode
*inode
)
76 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
77 struct extent_tree
*et
;
78 nid_t ino
= inode
->i_ino
;
80 down_write(&sbi
->extent_tree_lock
);
81 et
= radix_tree_lookup(&sbi
->extent_tree_root
, ino
);
83 et
= f2fs_kmem_cache_alloc(extent_tree_slab
, GFP_NOFS
);
84 f2fs_radix_tree_insert(&sbi
->extent_tree_root
, ino
, et
);
85 memset(et
, 0, sizeof(struct extent_tree
));
89 rwlock_init(&et
->lock
);
90 INIT_LIST_HEAD(&et
->list
);
91 atomic_set(&et
->node_cnt
, 0);
92 atomic_inc(&sbi
->total_ext_tree
);
94 atomic_dec(&sbi
->total_zombie_tree
);
95 list_del_init(&et
->list
);
97 up_write(&sbi
->extent_tree_lock
);
99 /* never died until evict_inode */
100 F2FS_I(inode
)->extent_tree
= et
;
105 static struct extent_node
*__lookup_extent_tree(struct f2fs_sb_info
*sbi
,
106 struct extent_tree
*et
, unsigned int fofs
)
108 struct rb_node
*node
= et
->root
.rb_node
;
109 struct extent_node
*en
= et
->cached_en
;
112 struct extent_info
*cei
= &en
->ei
;
114 if (cei
->fofs
<= fofs
&& cei
->fofs
+ cei
->len
> fofs
) {
115 stat_inc_cached_node_hit(sbi
);
121 en
= rb_entry(node
, struct extent_node
, rb_node
);
123 if (fofs
< en
->ei
.fofs
) {
124 node
= node
->rb_left
;
125 } else if (fofs
>= en
->ei
.fofs
+ en
->ei
.len
) {
126 node
= node
->rb_right
;
128 stat_inc_rbtree_node_hit(sbi
);
135 static struct extent_node
*__init_extent_tree(struct f2fs_sb_info
*sbi
,
136 struct extent_tree
*et
, struct extent_info
*ei
)
138 struct rb_node
**p
= &et
->root
.rb_node
;
139 struct extent_node
*en
;
141 en
= __attach_extent_node(sbi
, et
, ei
, NULL
, p
);
145 et
->largest
= en
->ei
;
150 static unsigned int __free_extent_tree(struct f2fs_sb_info
*sbi
,
151 struct extent_tree
*et
)
153 struct rb_node
*node
, *next
;
154 struct extent_node
*en
;
155 unsigned int count
= atomic_read(&et
->node_cnt
);
157 node
= rb_first(&et
->root
);
159 next
= rb_next(node
);
160 en
= rb_entry(node
, struct extent_node
, rb_node
);
161 __release_extent_node(sbi
, et
, en
);
165 return count
- atomic_read(&et
->node_cnt
);
168 static void __drop_largest_extent(struct inode
*inode
,
169 pgoff_t fofs
, unsigned int len
)
171 struct extent_info
*largest
= &F2FS_I(inode
)->extent_tree
->largest
;
173 if (fofs
< largest
->fofs
+ largest
->len
&& fofs
+ len
> largest
->fofs
)
177 /* return true, if inode page is changed */
178 bool f2fs_init_extent_tree(struct inode
*inode
, struct f2fs_extent
*i_ext
)
180 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
181 struct extent_tree
*et
;
182 struct extent_node
*en
;
183 struct extent_info ei
;
185 if (!f2fs_may_extent_tree(inode
)) {
186 /* drop largest extent */
187 if (i_ext
&& i_ext
->len
) {
194 et
= __grab_extent_tree(inode
);
196 if (!i_ext
|| !i_ext
->len
)
199 get_extent_info(&ei
, i_ext
);
201 write_lock(&et
->lock
);
202 if (atomic_read(&et
->node_cnt
))
205 en
= __init_extent_tree(sbi
, et
, &ei
);
207 spin_lock(&sbi
->extent_lock
);
208 list_add_tail(&en
->list
, &sbi
->extent_list
);
209 spin_unlock(&sbi
->extent_lock
);
212 write_unlock(&et
->lock
);
216 static bool f2fs_lookup_extent_tree(struct inode
*inode
, pgoff_t pgofs
,
217 struct extent_info
*ei
)
219 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
220 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
;
221 struct extent_node
*en
;
224 f2fs_bug_on(sbi
, !et
);
226 trace_f2fs_lookup_extent_tree_start(inode
, pgofs
);
228 read_lock(&et
->lock
);
230 if (et
->largest
.fofs
<= pgofs
&&
231 et
->largest
.fofs
+ et
->largest
.len
> pgofs
) {
234 stat_inc_largest_node_hit(sbi
);
238 en
= __lookup_extent_tree(sbi
, et
, pgofs
);
241 spin_lock(&sbi
->extent_lock
);
242 if (!list_empty(&en
->list
)) {
243 list_move_tail(&en
->list
, &sbi
->extent_list
);
246 spin_unlock(&sbi
->extent_lock
);
250 stat_inc_total_hit(sbi
);
251 read_unlock(&et
->lock
);
253 trace_f2fs_lookup_extent_tree_end(inode
, pgofs
, ei
);
259 * lookup extent at @fofs, if hit, return the extent
260 * if not, return NULL and
261 * @prev_ex: extent before fofs
262 * @next_ex: extent after fofs
263 * @insert_p: insert point for new extent at fofs
264 * in order to simpfy the insertion after.
265 * tree must stay unchanged between lookup and insertion.
267 static struct extent_node
*__lookup_extent_tree_ret(struct extent_tree
*et
,
269 struct extent_node
**prev_ex
,
270 struct extent_node
**next_ex
,
271 struct rb_node
***insert_p
,
272 struct rb_node
**insert_parent
)
274 struct rb_node
**pnode
= &et
->root
.rb_node
;
275 struct rb_node
*parent
= NULL
, *tmp_node
;
276 struct extent_node
*en
= et
->cached_en
;
279 *insert_parent
= NULL
;
283 if (RB_EMPTY_ROOT(&et
->root
))
287 struct extent_info
*cei
= &en
->ei
;
289 if (cei
->fofs
<= fofs
&& cei
->fofs
+ cei
->len
> fofs
)
290 goto lookup_neighbors
;
295 en
= rb_entry(*pnode
, struct extent_node
, rb_node
);
297 if (fofs
< en
->ei
.fofs
)
298 pnode
= &(*pnode
)->rb_left
;
299 else if (fofs
>= en
->ei
.fofs
+ en
->ei
.len
)
300 pnode
= &(*pnode
)->rb_right
;
302 goto lookup_neighbors
;
306 *insert_parent
= parent
;
308 en
= rb_entry(parent
, struct extent_node
, rb_node
);
310 if (parent
&& fofs
> en
->ei
.fofs
)
311 tmp_node
= rb_next(parent
);
312 *next_ex
= tmp_node
?
313 rb_entry(tmp_node
, struct extent_node
, rb_node
) : NULL
;
316 if (parent
&& fofs
< en
->ei
.fofs
)
317 tmp_node
= rb_prev(parent
);
318 *prev_ex
= tmp_node
?
319 rb_entry(tmp_node
, struct extent_node
, rb_node
) : NULL
;
323 if (fofs
== en
->ei
.fofs
) {
324 /* lookup prev node for merging backward later */
325 tmp_node
= rb_prev(&en
->rb_node
);
326 *prev_ex
= tmp_node
?
327 rb_entry(tmp_node
, struct extent_node
, rb_node
) : NULL
;
329 if (fofs
== en
->ei
.fofs
+ en
->ei
.len
- 1) {
330 /* lookup next node for merging frontward later */
331 tmp_node
= rb_next(&en
->rb_node
);
332 *next_ex
= tmp_node
?
333 rb_entry(tmp_node
, struct extent_node
, rb_node
) : NULL
;
338 static struct extent_node
*__try_merge_extent_node(struct f2fs_sb_info
*sbi
,
339 struct extent_tree
*et
, struct extent_info
*ei
,
340 struct extent_node
*prev_ex
,
341 struct extent_node
*next_ex
)
343 struct extent_node
*en
= NULL
;
345 if (prev_ex
&& __is_back_mergeable(ei
, &prev_ex
->ei
)) {
346 prev_ex
->ei
.len
+= ei
->len
;
351 if (next_ex
&& __is_front_mergeable(ei
, &next_ex
->ei
)) {
353 __release_extent_node(sbi
, et
, prev_ex
);
354 next_ex
->ei
.fofs
= ei
->fofs
;
355 next_ex
->ei
.blk
= ei
->blk
;
356 next_ex
->ei
.len
+= ei
->len
;
363 __try_update_largest_extent(et
, en
);
365 spin_lock(&sbi
->extent_lock
);
366 if (!list_empty(&en
->list
)) {
367 list_move_tail(&en
->list
, &sbi
->extent_list
);
370 spin_unlock(&sbi
->extent_lock
);
374 static struct extent_node
*__insert_extent_tree(struct f2fs_sb_info
*sbi
,
375 struct extent_tree
*et
, struct extent_info
*ei
,
376 struct rb_node
**insert_p
,
377 struct rb_node
*insert_parent
)
379 struct rb_node
**p
= &et
->root
.rb_node
;
380 struct rb_node
*parent
= NULL
;
381 struct extent_node
*en
= NULL
;
383 if (insert_p
&& insert_parent
) {
384 parent
= insert_parent
;
391 en
= rb_entry(parent
, struct extent_node
, rb_node
);
393 if (ei
->fofs
< en
->ei
.fofs
)
395 else if (ei
->fofs
>= en
->ei
.fofs
+ en
->ei
.len
)
401 en
= __attach_extent_node(sbi
, et
, ei
, parent
, p
);
405 __try_update_largest_extent(et
, en
);
407 /* update in global extent list */
408 spin_lock(&sbi
->extent_lock
);
409 list_add_tail(&en
->list
, &sbi
->extent_list
);
411 spin_unlock(&sbi
->extent_lock
);
415 static unsigned int f2fs_update_extent_tree_range(struct inode
*inode
,
416 pgoff_t fofs
, block_t blkaddr
, unsigned int len
)
418 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
419 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
;
420 struct extent_node
*en
= NULL
, *en1
= NULL
;
421 struct extent_node
*prev_en
= NULL
, *next_en
= NULL
;
422 struct extent_info ei
, dei
, prev
;
423 struct rb_node
**insert_p
= NULL
, *insert_parent
= NULL
;
424 unsigned int end
= fofs
+ len
;
425 unsigned int pos
= (unsigned int)fofs
;
430 trace_f2fs_update_extent_tree_range(inode
, fofs
, blkaddr
, len
);
432 write_lock(&et
->lock
);
434 if (is_inode_flag_set(F2FS_I(inode
), FI_NO_EXTENT
)) {
435 write_unlock(&et
->lock
);
443 * drop largest extent before lookup, in case it's already
444 * been shrunk from extent tree
446 __drop_largest_extent(inode
, fofs
, len
);
448 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
449 en
= __lookup_extent_tree_ret(et
, fofs
, &prev_en
, &next_en
,
450 &insert_p
, &insert_parent
);
454 /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */
455 while (en
&& en
->ei
.fofs
< end
) {
456 unsigned int org_end
;
457 int parts
= 0; /* # of parts current extent split into */
459 next_en
= en1
= NULL
;
462 org_end
= dei
.fofs
+ dei
.len
;
463 f2fs_bug_on(sbi
, pos
>= org_end
);
465 if (pos
> dei
.fofs
&& pos
- dei
.fofs
>= F2FS_MIN_EXTENT_LEN
) {
466 en
->ei
.len
= pos
- en
->ei
.fofs
;
471 if (end
< org_end
&& org_end
- end
>= F2FS_MIN_EXTENT_LEN
) {
473 set_extent_info(&ei
, end
,
474 end
- dei
.fofs
+ dei
.blk
,
476 en1
= __insert_extent_tree(sbi
, et
, &ei
,
481 en
->ei
.blk
+= end
- dei
.fofs
;
482 en
->ei
.len
-= end
- dei
.fofs
;
489 struct rb_node
*node
= rb_next(&en
->rb_node
);
492 rb_entry(node
, struct extent_node
, rb_node
)
497 __try_update_largest_extent(et
, en
);
499 __release_extent_node(sbi
, et
, en
);
502 * if original extent is split into zero or two parts, extent
503 * tree has been altered by deletion or insertion, therefore
504 * invalidate pointers regard to tree.
508 insert_parent
= NULL
;
513 /* 3. update extent in extent cache */
516 set_extent_info(&ei
, fofs
, blkaddr
, len
);
517 if (!__try_merge_extent_node(sbi
, et
, &ei
, prev_en
, next_en
))
518 __insert_extent_tree(sbi
, et
, &ei
,
519 insert_p
, insert_parent
);
521 /* give up extent_cache, if split and small updates happen */
523 prev
.len
< F2FS_MIN_EXTENT_LEN
&&
524 et
->largest
.len
< F2FS_MIN_EXTENT_LEN
) {
526 set_inode_flag(F2FS_I(inode
), FI_NO_EXTENT
);
530 if (is_inode_flag_set(F2FS_I(inode
), FI_NO_EXTENT
))
531 __free_extent_tree(sbi
, et
);
533 write_unlock(&et
->lock
);
535 return !__is_extent_same(&prev
, &et
->largest
);
538 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info
*sbi
, int nr_shrink
)
540 struct extent_tree
*et
, *next
;
541 struct extent_node
*en
;
542 unsigned int node_cnt
= 0, tree_cnt
= 0;
545 if (!test_opt(sbi
, EXTENT_CACHE
))
548 if (!atomic_read(&sbi
->total_zombie_tree
))
551 if (!down_write_trylock(&sbi
->extent_tree_lock
))
554 /* 1. remove unreferenced extent tree */
555 list_for_each_entry_safe(et
, next
, &sbi
->zombie_list
, list
) {
556 if (atomic_read(&et
->node_cnt
)) {
557 write_lock(&et
->lock
);
558 node_cnt
+= __free_extent_tree(sbi
, et
);
559 write_unlock(&et
->lock
);
561 f2fs_bug_on(sbi
, atomic_read(&et
->node_cnt
));
562 list_del_init(&et
->list
);
563 radix_tree_delete(&sbi
->extent_tree_root
, et
->ino
);
564 kmem_cache_free(extent_tree_slab
, et
);
565 atomic_dec(&sbi
->total_ext_tree
);
566 atomic_dec(&sbi
->total_zombie_tree
);
569 if (node_cnt
+ tree_cnt
>= nr_shrink
)
573 up_write(&sbi
->extent_tree_lock
);
576 /* 2. remove LRU extent entries */
577 if (!down_write_trylock(&sbi
->extent_tree_lock
))
580 remained
= nr_shrink
- (node_cnt
+ tree_cnt
);
582 spin_lock(&sbi
->extent_lock
);
583 for (; remained
> 0; remained
--) {
584 if (list_empty(&sbi
->extent_list
))
586 en
= list_first_entry(&sbi
->extent_list
,
587 struct extent_node
, list
);
589 if (!write_trylock(&et
->lock
)) {
590 /* refresh this extent node's position in extent list */
591 list_move_tail(&en
->list
, &sbi
->extent_list
);
595 list_del_init(&en
->list
);
596 spin_unlock(&sbi
->extent_lock
);
598 __detach_extent_node(sbi
, et
, en
);
600 write_unlock(&et
->lock
);
602 spin_lock(&sbi
->extent_lock
);
604 spin_unlock(&sbi
->extent_lock
);
607 up_write(&sbi
->extent_tree_lock
);
609 trace_f2fs_shrink_extent_tree(sbi
, node_cnt
, tree_cnt
);
611 return node_cnt
+ tree_cnt
;
614 unsigned int f2fs_destroy_extent_node(struct inode
*inode
)
616 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
617 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
;
618 unsigned int node_cnt
= 0;
620 if (!et
|| !atomic_read(&et
->node_cnt
))
623 write_lock(&et
->lock
);
624 node_cnt
= __free_extent_tree(sbi
, et
);
625 write_unlock(&et
->lock
);
630 void f2fs_destroy_extent_tree(struct inode
*inode
)
632 struct f2fs_sb_info
*sbi
= F2FS_I_SB(inode
);
633 struct extent_tree
*et
= F2FS_I(inode
)->extent_tree
;
634 unsigned int node_cnt
= 0;
639 if (inode
->i_nlink
&& !is_bad_inode(inode
) &&
640 atomic_read(&et
->node_cnt
)) {
641 down_write(&sbi
->extent_tree_lock
);
642 list_add_tail(&et
->list
, &sbi
->zombie_list
);
643 atomic_inc(&sbi
->total_zombie_tree
);
644 up_write(&sbi
->extent_tree_lock
);
648 /* free all extent info belong to this extent tree */
649 node_cnt
= f2fs_destroy_extent_node(inode
);
651 /* delete extent tree entry in radix tree */
652 down_write(&sbi
->extent_tree_lock
);
653 f2fs_bug_on(sbi
, atomic_read(&et
->node_cnt
));
654 radix_tree_delete(&sbi
->extent_tree_root
, inode
->i_ino
);
655 kmem_cache_free(extent_tree_slab
, et
);
656 atomic_dec(&sbi
->total_ext_tree
);
657 up_write(&sbi
->extent_tree_lock
);
659 F2FS_I(inode
)->extent_tree
= NULL
;
661 trace_f2fs_destroy_extent_tree(inode
, node_cnt
);
664 bool f2fs_lookup_extent_cache(struct inode
*inode
, pgoff_t pgofs
,
665 struct extent_info
*ei
)
667 if (!f2fs_may_extent_tree(inode
))
670 return f2fs_lookup_extent_tree(inode
, pgofs
, ei
);
673 void f2fs_update_extent_cache(struct dnode_of_data
*dn
)
678 if (!f2fs_may_extent_tree(dn
->inode
))
681 if (dn
->data_blkaddr
== NEW_ADDR
)
684 blkaddr
= dn
->data_blkaddr
;
686 fofs
= start_bidx_of_node(ofs_of_node(dn
->node_page
), dn
->inode
) +
689 if (f2fs_update_extent_tree_range(dn
->inode
, fofs
, blkaddr
, 1))
693 void f2fs_update_extent_cache_range(struct dnode_of_data
*dn
,
694 pgoff_t fofs
, block_t blkaddr
, unsigned int len
)
697 if (!f2fs_may_extent_tree(dn
->inode
))
700 if (f2fs_update_extent_tree_range(dn
->inode
, fofs
, blkaddr
, len
))
704 void init_extent_cache_info(struct f2fs_sb_info
*sbi
)
706 INIT_RADIX_TREE(&sbi
->extent_tree_root
, GFP_NOIO
);
707 init_rwsem(&sbi
->extent_tree_lock
);
708 INIT_LIST_HEAD(&sbi
->extent_list
);
709 spin_lock_init(&sbi
->extent_lock
);
710 atomic_set(&sbi
->total_ext_tree
, 0);
711 INIT_LIST_HEAD(&sbi
->zombie_list
);
712 atomic_set(&sbi
->total_zombie_tree
, 0);
713 atomic_set(&sbi
->total_ext_node
, 0);
716 int __init
create_extent_cache(void)
718 extent_tree_slab
= f2fs_kmem_cache_create("f2fs_extent_tree",
719 sizeof(struct extent_tree
));
720 if (!extent_tree_slab
)
722 extent_node_slab
= f2fs_kmem_cache_create("f2fs_extent_node",
723 sizeof(struct extent_node
));
724 if (!extent_node_slab
) {
725 kmem_cache_destroy(extent_tree_slab
);
731 void destroy_extent_cache(void)
733 kmem_cache_destroy(extent_node_slab
);
734 kmem_cache_destroy(extent_tree_slab
);
This page took 0.05285 seconds and 6 git commands to generate.