1// SPDX-License-Identifier: GPL-2.0
2/*
3 * f2fs extent cache support
4 *
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>
9 *
10 * block_age-based extent cache added by:
11 * Copyright (c) 2022 xiaomi Co., Ltd.
12 * http://www.xiaomi.com/
13 */
14
15#include <linux/fs.h>
16#include <linux/f2fs_fs.h>
17
18#include "f2fs.h"
19#include "node.h"
20#include <trace/events/f2fs.h>
21
22bool sanity_check_extent_cache(struct inode *inode, struct folio *ifolio)
23{
24 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
25 struct f2fs_extent *i_ext = &F2FS_INODE(folio: ifolio)->i_ext;
26 struct extent_info ei;
27 int devi;
28
29 get_read_extent_info(ext: &ei, i_ext);
30
31 if (!ei.len)
32 return true;
33
34 if (!f2fs_is_valid_blkaddr(sbi, blkaddr: ei.blk, type: DATA_GENERIC_ENHANCE) ||
35 !f2fs_is_valid_blkaddr(sbi, blkaddr: ei.blk + ei.len - 1,
36 type: DATA_GENERIC_ENHANCE)) {
37 f2fs_warn(sbi, "%s: inode (ino=%lx) extent info [%u, %u, %u] is incorrect, run fsck to fix",
38 __func__, inode->i_ino,
39 ei.blk, ei.fofs, ei.len);
40 return false;
41 }
42
43 if (!IS_DEVICE_ALIASING(inode))
44 return true;
45
46 for (devi = 0; devi < sbi->s_ndevs; devi++) {
47 if (FDEV(devi).start_blk != ei.blk ||
48 FDEV(devi).end_blk != ei.blk + ei.len - 1)
49 continue;
50
51 if (devi == 0) {
52 f2fs_warn(sbi,
53 "%s: inode (ino=%lx) is an alias of meta device",
54 __func__, inode->i_ino);
55 return false;
56 }
57
58 if (bdev_is_zoned(FDEV(devi).bdev)) {
59 f2fs_warn(sbi,
60 "%s: device alias inode (ino=%lx)'s extent info "
61 "[%u, %u, %u] maps to zoned block device",
62 __func__, inode->i_ino, ei.blk, ei.fofs, ei.len);
63 return false;
64 }
65 return true;
66 }
67
68 f2fs_warn(sbi, "%s: device alias inode (ino=%lx)'s extent info "
69 "[%u, %u, %u] is inconsistent w/ any devices",
70 __func__, inode->i_ino, ei.blk, ei.fofs, ei.len);
71 return false;
72}
73
74static void __set_extent_info(struct extent_info *ei,
75 unsigned int fofs, unsigned int len,
76 block_t blk, bool keep_clen,
77 unsigned long age, unsigned long last_blocks,
78 enum extent_type type)
79{
80 ei->fofs = fofs;
81 ei->len = len;
82
83 if (type == EX_READ) {
84 ei->blk = blk;
85 if (keep_clen)
86 return;
87#ifdef CONFIG_F2FS_FS_COMPRESSION
88 ei->c_len = 0;
89#endif
90 } else if (type == EX_BLOCK_AGE) {
91 ei->age = age;
92 ei->last_blocks = last_blocks;
93 }
94}
95
96static bool __init_may_extent_tree(struct inode *inode, enum extent_type type)
97{
98 if (type == EX_READ)
99 return test_opt(F2FS_I_SB(inode), READ_EXTENT_CACHE) &&
100 S_ISREG(inode->i_mode);
101 if (type == EX_BLOCK_AGE)
102 return test_opt(F2FS_I_SB(inode), AGE_EXTENT_CACHE) &&
103 (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode));
104 return false;
105}
106
107static bool __may_extent_tree(struct inode *inode, enum extent_type type)
108{
109 if (IS_DEVICE_ALIASING(inode) && type == EX_READ)
110 return true;
111
112 /*
113 * for recovered files during mount do not create extents
114 * if shrinker is not registered.
115 */
116 if (list_empty(head: &F2FS_I_SB(inode)->s_list))
117 return false;
118
119 if (!__init_may_extent_tree(inode, type))
120 return false;
121
122 if (type == EX_READ) {
123 if (is_inode_flag_set(inode, flag: FI_NO_EXTENT))
124 return false;
125 if (is_inode_flag_set(inode, flag: FI_COMPRESSED_FILE) &&
126 !f2fs_sb_has_readonly(sbi: F2FS_I_SB(inode)))
127 return false;
128 } else if (type == EX_BLOCK_AGE) {
129 if (is_inode_flag_set(inode, flag: FI_COMPRESSED_FILE))
130 return false;
131 if (file_is_cold(inode))
132 return false;
133 }
134 return true;
135}
136
137static void __try_update_largest_extent(struct extent_tree *et,
138 struct extent_node *en)
139{
140 if (et->type != EX_READ)
141 return;
142 if (en->ei.len <= et->largest.len)
143 return;
144
145 et->largest = en->ei;
146 et->largest_updated = true;
147}
148
149static bool __is_extent_mergeable(struct extent_info *back,
150 struct extent_info *front, enum extent_type type)
151{
152 if (type == EX_READ) {
153#ifdef CONFIG_F2FS_FS_COMPRESSION
154 if (back->c_len && back->len != back->c_len)
155 return false;
156 if (front->c_len && front->len != front->c_len)
157 return false;
158#endif
159 return (back->fofs + back->len == front->fofs &&
160 back->blk + back->len == front->blk);
161 } else if (type == EX_BLOCK_AGE) {
162 return (back->fofs + back->len == front->fofs &&
163 abs(back->age - front->age) <= SAME_AGE_REGION &&
164 abs(back->last_blocks - front->last_blocks) <=
165 SAME_AGE_REGION);
166 }
167 return false;
168}
169
170static bool __is_back_mergeable(struct extent_info *cur,
171 struct extent_info *back, enum extent_type type)
172{
173 return __is_extent_mergeable(back, front: cur, type);
174}
175
176static bool __is_front_mergeable(struct extent_info *cur,
177 struct extent_info *front, enum extent_type type)
178{
179 return __is_extent_mergeable(back: cur, front, type);
180}
181
182static struct extent_node *__lookup_extent_node(struct rb_root_cached *root,
183 struct extent_node *cached_en, unsigned int fofs)
184{
185 struct rb_node *node = root->rb_root.rb_node;
186 struct extent_node *en;
187
188 /* check a cached entry */
189 if (cached_en && cached_en->ei.fofs <= fofs &&
190 cached_en->ei.fofs + cached_en->ei.len > fofs)
191 return cached_en;
192
193 /* check rb_tree */
194 while (node) {
195 en = rb_entry(node, struct extent_node, rb_node);
196
197 if (fofs < en->ei.fofs)
198 node = node->rb_left;
199 else if (fofs >= en->ei.fofs + en->ei.len)
200 node = node->rb_right;
201 else
202 return en;
203 }
204 return NULL;
205}
206
207/*
208 * lookup rb entry in position of @fofs in rb-tree,
209 * if hit, return the entry, otherwise, return NULL
210 * @prev_ex: extent before fofs
211 * @next_ex: extent after fofs
212 * @insert_p: insert point for new extent at fofs
213 * in order to simplify the insertion after.
214 * tree must stay unchanged between lookup and insertion.
215 */
216static struct extent_node *__lookup_extent_node_ret(struct rb_root_cached *root,
217 struct extent_node *cached_en,
218 unsigned int fofs,
219 struct extent_node **prev_entry,
220 struct extent_node **next_entry,
221 struct rb_node ***insert_p,
222 struct rb_node **insert_parent,
223 bool *leftmost)
224{
225 struct rb_node **pnode = &root->rb_root.rb_node;
226 struct rb_node *parent = NULL, *tmp_node;
227 struct extent_node *en = cached_en;
228
229 *insert_p = NULL;
230 *insert_parent = NULL;
231 *prev_entry = NULL;
232 *next_entry = NULL;
233
234 if (RB_EMPTY_ROOT(&root->rb_root))
235 return NULL;
236
237 if (en && en->ei.fofs <= fofs && en->ei.fofs + en->ei.len > fofs)
238 goto lookup_neighbors;
239
240 *leftmost = true;
241
242 while (*pnode) {
243 parent = *pnode;
244 en = rb_entry(*pnode, struct extent_node, rb_node);
245
246 if (fofs < en->ei.fofs) {
247 pnode = &(*pnode)->rb_left;
248 } else if (fofs >= en->ei.fofs + en->ei.len) {
249 pnode = &(*pnode)->rb_right;
250 *leftmost = false;
251 } else {
252 goto lookup_neighbors;
253 }
254 }
255
256 *insert_p = pnode;
257 *insert_parent = parent;
258
259 en = rb_entry(parent, struct extent_node, rb_node);
260 tmp_node = parent;
261 if (parent && fofs > en->ei.fofs)
262 tmp_node = rb_next(parent);
263 *next_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node);
264
265 tmp_node = parent;
266 if (parent && fofs < en->ei.fofs)
267 tmp_node = rb_prev(parent);
268 *prev_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node);
269 return NULL;
270
271lookup_neighbors:
272 if (fofs == en->ei.fofs) {
273 /* lookup prev node for merging backward later */
274 tmp_node = rb_prev(&en->rb_node);
275 *prev_entry = rb_entry_safe(tmp_node,
276 struct extent_node, rb_node);
277 }
278 if (fofs == en->ei.fofs + en->ei.len - 1) {
279 /* lookup next node for merging frontward later */
280 tmp_node = rb_next(&en->rb_node);
281 *next_entry = rb_entry_safe(tmp_node,
282 struct extent_node, rb_node);
283 }
284 return en;
285}
286
287static struct kmem_cache *extent_tree_slab;
288static struct kmem_cache *extent_node_slab;
289
290static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
291 struct extent_tree *et, struct extent_info *ei,
292 struct rb_node *parent, struct rb_node **p,
293 bool leftmost)
294{
295 struct extent_tree_info *eti = &sbi->extent_tree[et->type];
296 struct extent_node *en;
297
298 en = f2fs_kmem_cache_alloc(cachep: extent_node_slab, GFP_ATOMIC, nofail: false, sbi);
299 if (!en)
300 return NULL;
301
302 en->ei = *ei;
303 INIT_LIST_HEAD(list: &en->list);
304 en->et = et;
305
306 rb_link_node(node: &en->rb_node, parent, rb_link: p);
307 rb_insert_color_cached(node: &en->rb_node, root: &et->root, leftmost);
308 atomic_inc(v: &et->node_cnt);
309 atomic_inc(v: &eti->total_ext_node);
310 return en;
311}
312
313static void __detach_extent_node(struct f2fs_sb_info *sbi,
314 struct extent_tree *et, struct extent_node *en)
315{
316 struct extent_tree_info *eti = &sbi->extent_tree[et->type];
317
318 rb_erase_cached(node: &en->rb_node, root: &et->root);
319 atomic_dec(v: &et->node_cnt);
320 atomic_dec(v: &eti->total_ext_node);
321
322 if (et->cached_en == en)
323 et->cached_en = NULL;
324 kmem_cache_free(s: extent_node_slab, objp: en);
325}
326
327/*
328 * Flow to release an extent_node:
329 * 1. list_del_init
330 * 2. __detach_extent_node
331 * 3. kmem_cache_free.
332 */
333static void __release_extent_node(struct f2fs_sb_info *sbi,
334 struct extent_tree *et, struct extent_node *en)
335{
336 struct extent_tree_info *eti = &sbi->extent_tree[et->type];
337
338 spin_lock(lock: &eti->extent_lock);
339 f2fs_bug_on(sbi, list_empty(&en->list));
340 list_del_init(entry: &en->list);
341 spin_unlock(lock: &eti->extent_lock);
342
343 __detach_extent_node(sbi, et, en);
344}
345
346static struct extent_tree *__grab_extent_tree(struct inode *inode,
347 enum extent_type type)
348{
349 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
350 struct extent_tree_info *eti = &sbi->extent_tree[type];
351 struct extent_tree *et;
352 nid_t ino = inode->i_ino;
353
354 mutex_lock(&eti->extent_tree_lock);
355 et = radix_tree_lookup(&eti->extent_tree_root, ino);
356 if (!et) {
357 et = f2fs_kmem_cache_alloc(cachep: extent_tree_slab,
358 GFP_NOFS, nofail: true, NULL);
359 f2fs_radix_tree_insert(root: &eti->extent_tree_root, index: ino, item: et);
360 memset(et, 0, sizeof(struct extent_tree));
361 et->ino = ino;
362 et->type = type;
363 et->root = RB_ROOT_CACHED;
364 et->cached_en = NULL;
365 rwlock_init(&et->lock);
366 INIT_LIST_HEAD(list: &et->list);
367 atomic_set(v: &et->node_cnt, i: 0);
368 atomic_inc(v: &eti->total_ext_tree);
369 } else {
370 atomic_dec(v: &eti->total_zombie_tree);
371 list_del_init(entry: &et->list);
372 }
373 mutex_unlock(lock: &eti->extent_tree_lock);
374
375 /* never died until evict_inode */
376 F2FS_I(inode)->extent_tree[type] = et;
377
378 return et;
379}
380
381static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
382 struct extent_tree *et, unsigned int nr_shrink)
383{
384 struct rb_node *node, *next;
385 struct extent_node *en;
386 unsigned int count;
387
388 node = rb_first_cached(&et->root);
389
390 for (count = 0; node && count < nr_shrink; count++) {
391 next = rb_next(node);
392 en = rb_entry(node, struct extent_node, rb_node);
393 __release_extent_node(sbi, et, en);
394 node = next;
395 }
396
397 return count;
398}
399
400static void __drop_largest_extent(struct extent_tree *et,
401 pgoff_t fofs, unsigned int len)
402{
403 if (fofs < (pgoff_t)et->largest.fofs + et->largest.len &&
404 fofs + len > et->largest.fofs) {
405 et->largest.len = 0;
406 et->largest_updated = true;
407 }
408}
409
410void f2fs_init_read_extent_tree(struct inode *inode, struct folio *ifolio)
411{
412 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
413 struct extent_tree_info *eti = &sbi->extent_tree[EX_READ];
414 struct f2fs_extent *i_ext = &F2FS_INODE(folio: ifolio)->i_ext;
415 struct extent_tree *et;
416 struct extent_node *en;
417 struct extent_info ei = {0};
418
419 if (!__may_extent_tree(inode, type: EX_READ)) {
420 /* drop largest read extent */
421 if (i_ext->len) {
422 f2fs_folio_wait_writeback(folio: ifolio, type: NODE, ordered: true, locked: true);
423 i_ext->len = 0;
424 folio_mark_dirty(folio: ifolio);
425 }
426 set_inode_flag(inode, flag: FI_NO_EXTENT);
427 return;
428 }
429
430 et = __grab_extent_tree(inode, type: EX_READ);
431
432 get_read_extent_info(ext: &ei, i_ext);
433
434 write_lock(&et->lock);
435 if (atomic_read(v: &et->node_cnt) || !ei.len)
436 goto skip;
437
438 if (IS_DEVICE_ALIASING(inode)) {
439 et->largest = ei;
440 goto skip;
441 }
442
443 en = __attach_extent_node(sbi, et, ei: &ei, NULL,
444 p: &et->root.rb_root.rb_node, leftmost: true);
445 if (en) {
446 et->largest = en->ei;
447 et->cached_en = en;
448
449 spin_lock(lock: &eti->extent_lock);
450 list_add_tail(new: &en->list, head: &eti->extent_list);
451 spin_unlock(lock: &eti->extent_lock);
452 }
453skip:
454 /* Let's drop, if checkpoint got corrupted. */
455 if (f2fs_cp_error(sbi)) {
456 et->largest.len = 0;
457 et->largest_updated = true;
458 }
459 write_unlock(&et->lock);
460}
461
462void f2fs_init_age_extent_tree(struct inode *inode)
463{
464 if (!__init_may_extent_tree(inode, type: EX_BLOCK_AGE))
465 return;
466 __grab_extent_tree(inode, type: EX_BLOCK_AGE);
467}
468
469void f2fs_init_extent_tree(struct inode *inode)
470{
471 /* initialize read cache */
472 if (__init_may_extent_tree(inode, type: EX_READ))
473 __grab_extent_tree(inode, type: EX_READ);
474
475 /* initialize block age cache */
476 if (__init_may_extent_tree(inode, type: EX_BLOCK_AGE))
477 __grab_extent_tree(inode, type: EX_BLOCK_AGE);
478}
479
480static bool __lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
481 struct extent_info *ei, enum extent_type type)
482{
483 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
484 struct extent_tree_info *eti = &sbi->extent_tree[type];
485 struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
486 struct extent_node *en;
487 bool ret = false;
488
489 if (!et)
490 return false;
491
492 trace_f2fs_lookup_extent_tree_start(inode, pgofs, type);
493
494 read_lock(&et->lock);
495
496 if (type == EX_READ &&
497 et->largest.fofs <= pgofs &&
498 (pgoff_t)et->largest.fofs + et->largest.len > pgofs) {
499 *ei = et->largest;
500 ret = true;
501 stat_inc_largest_node_hit(sbi);
502 goto out;
503 }
504
505 if (IS_DEVICE_ALIASING(inode)) {
506 ret = false;
507 goto out;
508 }
509
510 en = __lookup_extent_node(root: &et->root, cached_en: et->cached_en, fofs: pgofs);
511 if (!en)
512 goto out;
513
514 if (en == et->cached_en)
515 stat_inc_cached_node_hit(sbi, type);
516 else
517 stat_inc_rbtree_node_hit(sbi, type);
518
519 *ei = en->ei;
520 spin_lock(lock: &eti->extent_lock);
521 if (!list_empty(head: &en->list)) {
522 list_move_tail(list: &en->list, head: &eti->extent_list);
523 et->cached_en = en;
524 }
525 spin_unlock(lock: &eti->extent_lock);
526 ret = true;
527out:
528 stat_inc_total_hit(sbi, type);
529 read_unlock(&et->lock);
530
531 if (type == EX_READ)
532 trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei);
533 else if (type == EX_BLOCK_AGE)
534 trace_f2fs_lookup_age_extent_tree_end(inode, pgofs, ei);
535 return ret;
536}
537
538static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
539 struct extent_tree *et, struct extent_info *ei,
540 struct extent_node *prev_ex,
541 struct extent_node *next_ex)
542{
543 struct extent_tree_info *eti = &sbi->extent_tree[et->type];
544 struct extent_node *en = NULL;
545
546 if (prev_ex && __is_back_mergeable(cur: ei, back: &prev_ex->ei, type: et->type)) {
547 prev_ex->ei.len += ei->len;
548 ei = &prev_ex->ei;
549 en = prev_ex;
550 }
551
552 if (next_ex && __is_front_mergeable(cur: ei, front: &next_ex->ei, type: et->type)) {
553 next_ex->ei.fofs = ei->fofs;
554 next_ex->ei.len += ei->len;
555 if (et->type == EX_READ)
556 next_ex->ei.blk = ei->blk;
557 if (en)
558 __release_extent_node(sbi, et, en: prev_ex);
559
560 en = next_ex;
561 }
562
563 if (!en)
564 return NULL;
565
566 __try_update_largest_extent(et, en);
567
568 spin_lock(lock: &eti->extent_lock);
569 if (!list_empty(head: &en->list)) {
570 list_move_tail(list: &en->list, head: &eti->extent_list);
571 et->cached_en = en;
572 }
573 spin_unlock(lock: &eti->extent_lock);
574 return en;
575}
576
577static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
578 struct extent_tree *et, struct extent_info *ei,
579 struct rb_node **insert_p,
580 struct rb_node *insert_parent,
581 bool leftmost)
582{
583 struct extent_tree_info *eti = &sbi->extent_tree[et->type];
584 struct rb_node **p = &et->root.rb_root.rb_node;
585 struct rb_node *parent = NULL;
586 struct extent_node *en = NULL;
587
588 if (insert_p && insert_parent) {
589 parent = insert_parent;
590 p = insert_p;
591 goto do_insert;
592 }
593
594 leftmost = true;
595
596 /* look up extent_node in the rb tree */
597 while (*p) {
598 parent = *p;
599 en = rb_entry(parent, struct extent_node, rb_node);
600
601 if (ei->fofs < en->ei.fofs) {
602 p = &(*p)->rb_left;
603 } else if (ei->fofs >= en->ei.fofs + en->ei.len) {
604 p = &(*p)->rb_right;
605 leftmost = false;
606 } else {
607 f2fs_err_ratelimited(sbi, "%s: corrupted extent, type: %d, "
608 "extent node in rb tree [%u, %u, %u], age [%llu, %llu], "
609 "extent node to insert [%u, %u, %u], age [%llu, %llu]",
610 __func__, et->type, en->ei.fofs, en->ei.blk, en->ei.len, en->ei.age,
611 en->ei.last_blocks, ei->fofs, ei->blk, ei->len, ei->age, ei->last_blocks);
612 f2fs_bug_on(sbi, 1);
613 return NULL;
614 }
615 }
616
617do_insert:
618 en = __attach_extent_node(sbi, et, ei, parent, p, leftmost);
619 if (!en)
620 return NULL;
621
622 __try_update_largest_extent(et, en);
623
624 /* update in global extent list */
625 spin_lock(lock: &eti->extent_lock);
626 list_add_tail(new: &en->list, head: &eti->extent_list);
627 et->cached_en = en;
628 spin_unlock(lock: &eti->extent_lock);
629 return en;
630}
631
632static unsigned int __destroy_extent_node(struct inode *inode,
633 enum extent_type type)
634{
635 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
636 struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
637 unsigned int nr_shrink = type == EX_READ ?
638 READ_EXTENT_CACHE_SHRINK_NUMBER :
639 AGE_EXTENT_CACHE_SHRINK_NUMBER;
640 unsigned int node_cnt = 0;
641
642 if (!et || !atomic_read(v: &et->node_cnt))
643 return 0;
644
645 while (atomic_read(v: &et->node_cnt)) {
646 write_lock(&et->lock);
647 node_cnt += __free_extent_tree(sbi, et, nr_shrink);
648 write_unlock(&et->lock);
649 }
650
651 f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
652
653 return node_cnt;
654}
655
656static void __update_extent_tree_range(struct inode *inode,
657 struct extent_info *tei, enum extent_type type)
658{
659 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
660 struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
661 struct extent_node *en = NULL, *en1 = NULL;
662 struct extent_node *prev_en = NULL, *next_en = NULL;
663 struct extent_info ei, dei, prev;
664 struct rb_node **insert_p = NULL, *insert_parent = NULL;
665 unsigned int fofs = tei->fofs, len = tei->len;
666 unsigned int end = fofs + len;
667 bool updated = false;
668 bool leftmost = false;
669
670 if (!et)
671 return;
672
673 if (unlikely(len == 0)) {
674 f2fs_err_ratelimited(sbi, "%s: extent len is zero, type: %d, "
675 "extent [%u, %u, %u], age [%llu, %llu]",
676 __func__, type, tei->fofs, tei->blk, tei->len,
677 tei->age, tei->last_blocks);
678 f2fs_bug_on(sbi, 1);
679 return;
680 }
681
682 if (type == EX_READ)
683 trace_f2fs_update_read_extent_tree_range(inode, pgofs: fofs, len,
684 blkaddr: tei->blk, c_len: 0);
685 else if (type == EX_BLOCK_AGE)
686 trace_f2fs_update_age_extent_tree_range(inode, pgofs: fofs, len,
687 age: tei->age, last_blks: tei->last_blocks);
688
689 write_lock(&et->lock);
690
691 if (type == EX_READ) {
692 if (is_inode_flag_set(inode, flag: FI_NO_EXTENT)) {
693 write_unlock(&et->lock);
694 return;
695 }
696
697 prev = et->largest;
698 dei.len = 0;
699
700 /*
701 * drop largest extent before lookup, in case it's already
702 * been shrunk from extent tree
703 */
704 __drop_largest_extent(et, fofs, len);
705 }
706
707 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
708 en = __lookup_extent_node_ret(root: &et->root,
709 cached_en: et->cached_en, fofs,
710 prev_entry: &prev_en, next_entry: &next_en,
711 insert_p: &insert_p, insert_parent: &insert_parent,
712 leftmost: &leftmost);
713 if (!en)
714 en = next_en;
715
716 /* 2. invalidate all extent nodes in range [fofs, fofs + len - 1] */
717 while (en && en->ei.fofs < end) {
718 unsigned int org_end;
719 int parts = 0; /* # of parts current extent split into */
720
721 next_en = en1 = NULL;
722
723 dei = en->ei;
724 org_end = dei.fofs + dei.len;
725 f2fs_bug_on(sbi, fofs >= org_end);
726
727 if (fofs > dei.fofs && (type != EX_READ ||
728 fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) {
729 en->ei.len = fofs - en->ei.fofs;
730 prev_en = en;
731 parts = 1;
732 }
733
734 if (end < org_end && (type != EX_READ ||
735 (org_end - end >= F2FS_MIN_EXTENT_LEN &&
736 atomic_read(v: &et->node_cnt) <
737 sbi->max_read_extent_count))) {
738 if (parts) {
739 __set_extent_info(ei: &ei,
740 fofs: end, len: org_end - end,
741 blk: end - dei.fofs + dei.blk, keep_clen: false,
742 age: dei.age, last_blocks: dei.last_blocks,
743 type);
744 en1 = __insert_extent_tree(sbi, et, ei: &ei,
745 NULL, NULL, leftmost: true);
746 next_en = en1;
747 } else {
748 __set_extent_info(ei: &en->ei,
749 fofs: end, len: en->ei.len - (end - dei.fofs),
750 blk: en->ei.blk + (end - dei.fofs), keep_clen: true,
751 age: dei.age, last_blocks: dei.last_blocks,
752 type);
753 next_en = en;
754 }
755 parts++;
756 }
757
758 if (!next_en) {
759 struct rb_node *node = rb_next(&en->rb_node);
760
761 next_en = rb_entry_safe(node, struct extent_node,
762 rb_node);
763 }
764
765 if (parts)
766 __try_update_largest_extent(et, en);
767 else
768 __release_extent_node(sbi, et, en);
769
770 /*
771 * if original extent is split into zero or two parts, extent
772 * tree has been altered by deletion or insertion, therefore
773 * invalidate pointers regard to tree.
774 */
775 if (parts != 1) {
776 insert_p = NULL;
777 insert_parent = NULL;
778 }
779 en = next_en;
780 }
781
782 if (type == EX_BLOCK_AGE)
783 goto update_age_extent_cache;
784
785 /* 3. update extent in read extent cache */
786 BUG_ON(type != EX_READ);
787
788 if (tei->blk) {
789 __set_extent_info(ei: &ei, fofs, len, blk: tei->blk, keep_clen: false,
790 age: 0, last_blocks: 0, type: EX_READ);
791 if (!__try_merge_extent_node(sbi, et, ei: &ei, prev_ex: prev_en, next_ex: next_en))
792 __insert_extent_tree(sbi, et, ei: &ei,
793 insert_p, insert_parent, leftmost);
794
795 /* give up extent_cache, if split and small updates happen */
796 if (dei.len >= 1 &&
797 prev.len < F2FS_MIN_EXTENT_LEN &&
798 et->largest.len < F2FS_MIN_EXTENT_LEN) {
799 et->largest.len = 0;
800 et->largest_updated = true;
801 set_inode_flag(inode, flag: FI_NO_EXTENT);
802 }
803 }
804
805 if (et->largest_updated) {
806 et->largest_updated = false;
807 updated = true;
808 }
809 goto out_read_extent_cache;
810update_age_extent_cache:
811 if (tei->last_blocks == F2FS_EXTENT_AGE_INVALID)
812 goto out_read_extent_cache;
813
814 __set_extent_info(ei: &ei, fofs, len, blk: 0, keep_clen: false,
815 age: tei->age, last_blocks: tei->last_blocks, type: EX_BLOCK_AGE);
816 if (!__try_merge_extent_node(sbi, et, ei: &ei, prev_ex: prev_en, next_ex: next_en))
817 __insert_extent_tree(sbi, et, ei: &ei,
818 insert_p, insert_parent, leftmost);
819out_read_extent_cache:
820 write_unlock(&et->lock);
821
822 if (is_inode_flag_set(inode, flag: FI_NO_EXTENT))
823 __destroy_extent_node(inode, type: EX_READ);
824
825 if (updated)
826 f2fs_mark_inode_dirty_sync(inode, sync: true);
827}
828
829#ifdef CONFIG_F2FS_FS_COMPRESSION
830void f2fs_update_read_extent_tree_range_compressed(struct inode *inode,
831 pgoff_t fofs, block_t blkaddr, unsigned int llen,
832 unsigned int c_len)
833{
834 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
835 struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ];
836 struct extent_node *en = NULL;
837 struct extent_node *prev_en = NULL, *next_en = NULL;
838 struct extent_info ei;
839 struct rb_node **insert_p = NULL, *insert_parent = NULL;
840 bool leftmost = false;
841
842 trace_f2fs_update_read_extent_tree_range(inode, pgofs: fofs, len: llen,
843 blkaddr, c_len);
844
845 /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */
846 if (is_inode_flag_set(inode, flag: FI_NO_EXTENT))
847 return;
848
849 write_lock(&et->lock);
850
851 en = __lookup_extent_node_ret(root: &et->root,
852 cached_en: et->cached_en, fofs,
853 prev_entry: &prev_en, next_entry: &next_en,
854 insert_p: &insert_p, insert_parent: &insert_parent,
855 leftmost: &leftmost);
856 if (en)
857 goto unlock_out;
858
859 __set_extent_info(ei: &ei, fofs, len: llen, blk: blkaddr, keep_clen: true, age: 0, last_blocks: 0, type: EX_READ);
860 ei.c_len = c_len;
861
862 if (!__try_merge_extent_node(sbi, et, ei: &ei, prev_ex: prev_en, next_ex: next_en))
863 __insert_extent_tree(sbi, et, ei: &ei,
864 insert_p, insert_parent, leftmost);
865unlock_out:
866 write_unlock(&et->lock);
867}
868#endif
869
870static unsigned long long __calculate_block_age(struct f2fs_sb_info *sbi,
871 unsigned long long new,
872 unsigned long long old)
873{
874 unsigned int rem_old, rem_new;
875 unsigned long long res;
876 unsigned int weight = sbi->last_age_weight;
877
878 res = div_u64_rem(dividend: new, divisor: 100, remainder: &rem_new) * (100 - weight)
879 + div_u64_rem(dividend: old, divisor: 100, remainder: &rem_old) * weight;
880
881 if (rem_new)
882 res += rem_new * (100 - weight) / 100;
883 if (rem_old)
884 res += rem_old * weight / 100;
885
886 return res;
887}
888
889/* This returns a new age and allocated blocks in ei */
890static int __get_new_block_age(struct inode *inode, struct extent_info *ei,
891 block_t blkaddr)
892{
893 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
894 loff_t f_size = i_size_read(inode);
895 unsigned long long cur_blocks =
896 atomic64_read(v: &sbi->allocated_data_blocks);
897 struct extent_info tei = *ei; /* only fofs and len are valid */
898
899 /*
900 * When I/O is not aligned to a PAGE_SIZE, update will happen to the last
901 * file block even in seq write. So don't record age for newly last file
902 * block here.
903 */
904 if ((f_size >> PAGE_SHIFT) == ei->fofs && f_size & (PAGE_SIZE - 1) &&
905 blkaddr == NEW_ADDR)
906 return -EINVAL;
907
908 if (__lookup_extent_tree(inode, pgofs: ei->fofs, ei: &tei, type: EX_BLOCK_AGE)) {
909 unsigned long long cur_age;
910
911 if (cur_blocks >= tei.last_blocks)
912 cur_age = cur_blocks - tei.last_blocks;
913 else
914 /* allocated_data_blocks overflow */
915 cur_age = (ULLONG_MAX - 1) - tei.last_blocks + cur_blocks;
916
917 if (tei.age)
918 ei->age = __calculate_block_age(sbi, new: cur_age, old: tei.age);
919 else
920 ei->age = cur_age;
921 ei->last_blocks = cur_blocks;
922 WARN_ON(ei->age > cur_blocks);
923 return 0;
924 }
925
926 f2fs_bug_on(sbi, blkaddr == NULL_ADDR);
927
928 /* the data block was allocated for the first time */
929 if (blkaddr == NEW_ADDR)
930 goto out;
931
932 if (__is_valid_data_blkaddr(blkaddr) &&
933 !f2fs_is_valid_blkaddr(sbi, blkaddr, type: DATA_GENERIC_ENHANCE))
934 return -EINVAL;
935out:
936 /*
937 * init block age with zero, this can happen when the block age extent
938 * was reclaimed due to memory constraint or system reboot
939 */
940 ei->age = 0;
941 ei->last_blocks = cur_blocks;
942 return 0;
943}
944
945static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type)
946{
947 struct extent_info ei = {};
948
949 if (!__may_extent_tree(inode: dn->inode, type))
950 return;
951
952 ei.fofs = f2fs_start_bidx_of_node(node_ofs: ofs_of_node(node_folio: dn->node_folio), inode: dn->inode) +
953 dn->ofs_in_node;
954 ei.len = 1;
955
956 if (type == EX_READ) {
957 if (dn->data_blkaddr == NEW_ADDR)
958 ei.blk = NULL_ADDR;
959 else
960 ei.blk = dn->data_blkaddr;
961 } else if (type == EX_BLOCK_AGE) {
962 if (__get_new_block_age(inode: dn->inode, ei: &ei, blkaddr: dn->data_blkaddr))
963 return;
964 }
965 __update_extent_tree_range(inode: dn->inode, tei: &ei, type);
966}
967
968static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink,
969 enum extent_type type)
970{
971 struct extent_tree_info *eti = &sbi->extent_tree[type];
972 struct extent_tree *et, *next;
973 struct extent_node *en;
974 unsigned int node_cnt = 0, tree_cnt = 0;
975 int remained;
976
977 if (!atomic_read(v: &eti->total_zombie_tree))
978 goto free_node;
979
980 if (!mutex_trylock(&eti->extent_tree_lock))
981 goto out;
982
983 /* 1. remove unreferenced extent tree */
984 list_for_each_entry_safe(et, next, &eti->zombie_list, list) {
985 if (atomic_read(v: &et->node_cnt)) {
986 write_lock(&et->lock);
987 node_cnt += __free_extent_tree(sbi, et,
988 nr_shrink: nr_shrink - node_cnt - tree_cnt);
989 write_unlock(&et->lock);
990 }
991
992 if (atomic_read(v: &et->node_cnt))
993 goto unlock_out;
994
995 list_del_init(entry: &et->list);
996 radix_tree_delete(&eti->extent_tree_root, et->ino);
997 kmem_cache_free(s: extent_tree_slab, objp: et);
998 atomic_dec(v: &eti->total_ext_tree);
999 atomic_dec(v: &eti->total_zombie_tree);
1000 tree_cnt++;
1001
1002 if (node_cnt + tree_cnt >= nr_shrink)
1003 goto unlock_out;
1004 cond_resched();
1005 }
1006 mutex_unlock(lock: &eti->extent_tree_lock);
1007
1008free_node:
1009 /* 2. remove LRU extent entries */
1010 if (!mutex_trylock(&eti->extent_tree_lock))
1011 goto out;
1012
1013 remained = nr_shrink - (node_cnt + tree_cnt);
1014
1015 spin_lock(lock: &eti->extent_lock);
1016 for (; remained > 0; remained--) {
1017 if (list_empty(head: &eti->extent_list))
1018 break;
1019 en = list_first_entry(&eti->extent_list,
1020 struct extent_node, list);
1021 et = en->et;
1022 if (!write_trylock(&et->lock)) {
1023 /* refresh this extent node's position in extent list */
1024 list_move_tail(list: &en->list, head: &eti->extent_list);
1025 continue;
1026 }
1027
1028 list_del_init(entry: &en->list);
1029 spin_unlock(lock: &eti->extent_lock);
1030
1031 __detach_extent_node(sbi, et, en);
1032
1033 write_unlock(&et->lock);
1034 node_cnt++;
1035 spin_lock(lock: &eti->extent_lock);
1036 }
1037 spin_unlock(lock: &eti->extent_lock);
1038
1039unlock_out:
1040 mutex_unlock(lock: &eti->extent_tree_lock);
1041out:
1042 trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type);
1043
1044 return node_cnt + tree_cnt;
1045}
1046
1047/* read extent cache operations */
1048bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs,
1049 struct extent_info *ei)
1050{
1051 if (!__may_extent_tree(inode, type: EX_READ))
1052 return false;
1053
1054 return __lookup_extent_tree(inode, pgofs, ei, type: EX_READ);
1055}
1056
1057bool f2fs_lookup_read_extent_cache_block(struct inode *inode, pgoff_t index,
1058 block_t *blkaddr)
1059{
1060 struct extent_info ei = {};
1061
1062 if (!f2fs_lookup_read_extent_cache(inode, pgofs: index, ei: &ei))
1063 return false;
1064 *blkaddr = ei.blk + index - ei.fofs;
1065 return true;
1066}
1067
1068void f2fs_update_read_extent_cache(struct dnode_of_data *dn)
1069{
1070 return __update_extent_cache(dn, type: EX_READ);
1071}
1072
1073void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn,
1074 pgoff_t fofs, block_t blkaddr, unsigned int len)
1075{
1076 struct extent_info ei = {
1077 .fofs = fofs,
1078 .len = len,
1079 .blk = blkaddr,
1080 };
1081
1082 if (!__may_extent_tree(inode: dn->inode, type: EX_READ))
1083 return;
1084
1085 __update_extent_tree_range(inode: dn->inode, tei: &ei, type: EX_READ);
1086}
1087
1088unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
1089{
1090 if (!test_opt(sbi, READ_EXTENT_CACHE))
1091 return 0;
1092
1093 return __shrink_extent_tree(sbi, nr_shrink, type: EX_READ);
1094}
1095
1096/* block age extent cache operations */
1097bool f2fs_lookup_age_extent_cache(struct inode *inode, pgoff_t pgofs,
1098 struct extent_info *ei)
1099{
1100 if (!__may_extent_tree(inode, type: EX_BLOCK_AGE))
1101 return false;
1102
1103 return __lookup_extent_tree(inode, pgofs, ei, type: EX_BLOCK_AGE);
1104}
1105
1106void f2fs_update_age_extent_cache(struct dnode_of_data *dn)
1107{
1108 return __update_extent_cache(dn, type: EX_BLOCK_AGE);
1109}
1110
1111void f2fs_update_age_extent_cache_range(struct dnode_of_data *dn,
1112 pgoff_t fofs, unsigned int len)
1113{
1114 struct extent_info ei = {
1115 .fofs = fofs,
1116 .len = len,
1117 .last_blocks = F2FS_EXTENT_AGE_INVALID,
1118 };
1119
1120 if (!__may_extent_tree(inode: dn->inode, type: EX_BLOCK_AGE))
1121 return;
1122
1123 __update_extent_tree_range(inode: dn->inode, tei: &ei, type: EX_BLOCK_AGE);
1124}
1125
1126unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
1127{
1128 if (!test_opt(sbi, AGE_EXTENT_CACHE))
1129 return 0;
1130
1131 return __shrink_extent_tree(sbi, nr_shrink, type: EX_BLOCK_AGE);
1132}
1133
1134void f2fs_destroy_extent_node(struct inode *inode)
1135{
1136 __destroy_extent_node(inode, type: EX_READ);
1137 __destroy_extent_node(inode, type: EX_BLOCK_AGE);
1138}
1139
1140static void __drop_extent_tree(struct inode *inode, enum extent_type type)
1141{
1142 struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
1143 bool updated = false;
1144
1145 if (!__may_extent_tree(inode, type))
1146 return;
1147
1148 write_lock(&et->lock);
1149 if (type == EX_READ) {
1150 set_inode_flag(inode, flag: FI_NO_EXTENT);
1151 if (et->largest.len) {
1152 et->largest.len = 0;
1153 updated = true;
1154 }
1155 }
1156 write_unlock(&et->lock);
1157
1158 __destroy_extent_node(inode, type);
1159
1160 if (updated)
1161 f2fs_mark_inode_dirty_sync(inode, sync: true);
1162}
1163
1164void f2fs_drop_extent_tree(struct inode *inode)
1165{
1166 __drop_extent_tree(inode, type: EX_READ);
1167 __drop_extent_tree(inode, type: EX_BLOCK_AGE);
1168}
1169
1170static void __destroy_extent_tree(struct inode *inode, enum extent_type type)
1171{
1172 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
1173 struct extent_tree_info *eti = &sbi->extent_tree[type];
1174 struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
1175 unsigned int node_cnt = 0;
1176
1177 if (!et)
1178 return;
1179
1180 if (inode->i_nlink && !is_bad_inode(inode) &&
1181 atomic_read(v: &et->node_cnt)) {
1182 mutex_lock(&eti->extent_tree_lock);
1183 list_add_tail(new: &et->list, head: &eti->zombie_list);
1184 atomic_inc(v: &eti->total_zombie_tree);
1185 mutex_unlock(lock: &eti->extent_tree_lock);
1186 return;
1187 }
1188
1189 /* free all extent info belong to this extent tree */
1190 node_cnt = __destroy_extent_node(inode, type);
1191
1192 /* delete extent tree entry in radix tree */
1193 mutex_lock(&eti->extent_tree_lock);
1194 f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
1195 radix_tree_delete(&eti->extent_tree_root, inode->i_ino);
1196 kmem_cache_free(s: extent_tree_slab, objp: et);
1197 atomic_dec(v: &eti->total_ext_tree);
1198 mutex_unlock(lock: &eti->extent_tree_lock);
1199
1200 F2FS_I(inode)->extent_tree[type] = NULL;
1201
1202 trace_f2fs_destroy_extent_tree(inode, node_cnt, type);
1203}
1204
1205void f2fs_destroy_extent_tree(struct inode *inode)
1206{
1207 __destroy_extent_tree(inode, type: EX_READ);
1208 __destroy_extent_tree(inode, type: EX_BLOCK_AGE);
1209}
1210
1211static void __init_extent_tree_info(struct extent_tree_info *eti)
1212{
1213 INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO);
1214 mutex_init(&eti->extent_tree_lock);
1215 INIT_LIST_HEAD(list: &eti->extent_list);
1216 spin_lock_init(&eti->extent_lock);
1217 atomic_set(v: &eti->total_ext_tree, i: 0);
1218 INIT_LIST_HEAD(list: &eti->zombie_list);
1219 atomic_set(v: &eti->total_zombie_tree, i: 0);
1220 atomic_set(v: &eti->total_ext_node, i: 0);
1221}
1222
1223void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi)
1224{
1225 __init_extent_tree_info(eti: &sbi->extent_tree[EX_READ]);
1226 __init_extent_tree_info(eti: &sbi->extent_tree[EX_BLOCK_AGE]);
1227
1228 /* initialize for block age extents */
1229 atomic64_set(v: &sbi->allocated_data_blocks, i: 0);
1230 sbi->hot_data_age_threshold = DEF_HOT_DATA_AGE_THRESHOLD;
1231 sbi->warm_data_age_threshold = DEF_WARM_DATA_AGE_THRESHOLD;
1232 sbi->last_age_weight = LAST_AGE_WEIGHT;
1233 sbi->max_read_extent_count = DEF_MAX_READ_EXTENT_COUNT;
1234}
1235
1236int __init f2fs_create_extent_cache(void)
1237{
1238 extent_tree_slab = f2fs_kmem_cache_create(name: "f2fs_extent_tree",
1239 size: sizeof(struct extent_tree));
1240 if (!extent_tree_slab)
1241 return -ENOMEM;
1242 extent_node_slab = f2fs_kmem_cache_create(name: "f2fs_extent_node",
1243 size: sizeof(struct extent_node));
1244 if (!extent_node_slab) {
1245 kmem_cache_destroy(s: extent_tree_slab);
1246 return -ENOMEM;
1247 }
1248 return 0;
1249}
1250
1251void f2fs_destroy_extent_cache(void)
1252{
1253 kmem_cache_destroy(s: extent_node_slab);
1254 kmem_cache_destroy(s: extent_tree_slab);
1255}
1256

source code of linux/fs/f2fs/extent_cache.c