projects/linux·blob master · refs

1262 lines · 31.8 KiB

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