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
11 #include <linux/fs.h>
12 #include <linux/f2fs_fs.h>
13
14 #include "f2fs.h"
15 #include "node.h"
16 #include <trace/events/f2fs.h>
17
__lookup_rb_tree_fast(struct rb_entry * cached_re,unsigned int ofs)18 static struct rb_entry *__lookup_rb_tree_fast(struct rb_entry *cached_re,
19 unsigned int ofs)
20 {
21 if (cached_re) {
22 if (cached_re->ofs <= ofs &&
23 cached_re->ofs + cached_re->len > ofs) {
24 return cached_re;
25 }
26 }
27 return NULL;
28 }
29
__lookup_rb_tree_slow(struct rb_root_cached * root,unsigned int ofs)30 static struct rb_entry *__lookup_rb_tree_slow(struct rb_root_cached *root,
31 unsigned int ofs)
32 {
33 struct rb_node *node = root->rb_root.rb_node;
34 struct rb_entry *re;
35
36 while (node) {
37 re = rb_entry(node, struct rb_entry, rb_node);
38
39 if (ofs < re->ofs)
40 node = node->rb_left;
41 else if (ofs >= re->ofs + re->len)
42 node = node->rb_right;
43 else
44 return re;
45 }
46 return NULL;
47 }
48
f2fs_lookup_rb_tree(struct rb_root_cached * root,struct rb_entry * cached_re,unsigned int ofs)49 struct rb_entry *f2fs_lookup_rb_tree(struct rb_root_cached *root,
50 struct rb_entry *cached_re, unsigned int ofs)
51 {
52 struct rb_entry *re;
53
54 re = __lookup_rb_tree_fast(cached_re, ofs);
55 if (!re)
56 return __lookup_rb_tree_slow(root, ofs);
57
58 return re;
59 }
60
f2fs_lookup_rb_tree_ext(struct f2fs_sb_info * sbi,struct rb_root_cached * root,struct rb_node ** parent,unsigned long long key,bool * leftmost)61 struct rb_node **f2fs_lookup_rb_tree_ext(struct f2fs_sb_info *sbi,
62 struct rb_root_cached *root,
63 struct rb_node **parent,
64 unsigned long long key, bool *leftmost)
65 {
66 struct rb_node **p = &root->rb_root.rb_node;
67 struct rb_entry *re;
68
69 while (*p) {
70 *parent = *p;
71 re = rb_entry(*parent, struct rb_entry, rb_node);
72
73 if (key < re->key) {
74 p = &(*p)->rb_left;
75 } else {
76 p = &(*p)->rb_right;
77 *leftmost = false;
78 }
79 }
80
81 return p;
82 }
83
f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info * sbi,struct rb_root_cached * root,struct rb_node ** parent,unsigned int ofs,bool * leftmost)84 struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi,
85 struct rb_root_cached *root,
86 struct rb_node **parent,
87 unsigned int ofs, bool *leftmost)
88 {
89 struct rb_node **p = &root->rb_root.rb_node;
90 struct rb_entry *re;
91
92 while (*p) {
93 *parent = *p;
94 re = rb_entry(*parent, struct rb_entry, rb_node);
95
96 if (ofs < re->ofs) {
97 p = &(*p)->rb_left;
98 } else if (ofs >= re->ofs + re->len) {
99 p = &(*p)->rb_right;
100 *leftmost = false;
101 } else {
102 f2fs_bug_on(sbi, 1);
103 }
104 }
105
106 return p;
107 }
108
109 /*
110 * lookup rb entry in position of @ofs in rb-tree,
111 * if hit, return the entry, otherwise, return NULL
112 * @prev_ex: extent before ofs
113 * @next_ex: extent after ofs
114 * @insert_p: insert point for new extent at ofs
115 * in order to simpfy the insertion after.
116 * tree must stay unchanged between lookup and insertion.
117 */
f2fs_lookup_rb_tree_ret(struct rb_root_cached * root,struct rb_entry * cached_re,unsigned int ofs,struct rb_entry ** prev_entry,struct rb_entry ** next_entry,struct rb_node *** insert_p,struct rb_node ** insert_parent,bool force,bool * leftmost)118 struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root_cached *root,
119 struct rb_entry *cached_re,
120 unsigned int ofs,
121 struct rb_entry **prev_entry,
122 struct rb_entry **next_entry,
123 struct rb_node ***insert_p,
124 struct rb_node **insert_parent,
125 bool force, bool *leftmost)
126 {
127 struct rb_node **pnode = &root->rb_root.rb_node;
128 struct rb_node *parent = NULL, *tmp_node;
129 struct rb_entry *re = cached_re;
130
131 *insert_p = NULL;
132 *insert_parent = NULL;
133 *prev_entry = NULL;
134 *next_entry = NULL;
135
136 if (RB_EMPTY_ROOT(&root->rb_root))
137 return NULL;
138
139 if (re) {
140 if (re->ofs <= ofs && re->ofs + re->len > ofs)
141 goto lookup_neighbors;
142 }
143
144 if (leftmost)
145 *leftmost = true;
146
147 while (*pnode) {
148 parent = *pnode;
149 re = rb_entry(*pnode, struct rb_entry, rb_node);
150
151 if (ofs < re->ofs) {
152 pnode = &(*pnode)->rb_left;
153 } else if (ofs >= re->ofs + re->len) {
154 pnode = &(*pnode)->rb_right;
155 if (leftmost)
156 *leftmost = false;
157 } else {
158 goto lookup_neighbors;
159 }
160 }
161
162 *insert_p = pnode;
163 *insert_parent = parent;
164
165 re = rb_entry(parent, struct rb_entry, rb_node);
166 tmp_node = parent;
167 if (parent && ofs > re->ofs)
168 tmp_node = rb_next(parent);
169 *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
170
171 tmp_node = parent;
172 if (parent && ofs < re->ofs)
173 tmp_node = rb_prev(parent);
174 *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
175 return NULL;
176
177 lookup_neighbors:
178 if (ofs == re->ofs || force) {
179 /* lookup prev node for merging backward later */
180 tmp_node = rb_prev(&re->rb_node);
181 *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
182 }
183 if (ofs == re->ofs + re->len - 1 || force) {
184 /* lookup next node for merging frontward later */
185 tmp_node = rb_next(&re->rb_node);
186 *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
187 }
188 return re;
189 }
190
f2fs_check_rb_tree_consistence(struct f2fs_sb_info * sbi,struct rb_root_cached * root,bool check_key)191 bool f2fs_check_rb_tree_consistence(struct f2fs_sb_info *sbi,
192 struct rb_root_cached *root, bool check_key)
193 {
194 #ifdef CONFIG_F2FS_CHECK_FS
195 struct rb_node *cur = rb_first_cached(root), *next;
196 struct rb_entry *cur_re, *next_re;
197
198 if (!cur)
199 return true;
200
201 while (cur) {
202 next = rb_next(cur);
203 if (!next)
204 return true;
205
206 cur_re = rb_entry(cur, struct rb_entry, rb_node);
207 next_re = rb_entry(next, struct rb_entry, rb_node);
208
209 if (check_key) {
210 if (cur_re->key > next_re->key) {
211 f2fs_info(sbi, "inconsistent rbtree, "
212 "cur(%llu) next(%llu)",
213 cur_re->key, next_re->key);
214 return false;
215 }
216 goto next;
217 }
218
219 if (cur_re->ofs + cur_re->len > next_re->ofs) {
220 f2fs_info(sbi, "inconsistent rbtree, cur(%u, %u) next(%u, %u)",
221 cur_re->ofs, cur_re->len,
222 next_re->ofs, next_re->len);
223 return false;
224 }
225 next:
226 cur = next;
227 }
228 #endif
229 return true;
230 }
231
232 static struct kmem_cache *extent_tree_slab;
233 static struct kmem_cache *extent_node_slab;
234
__attach_extent_node(struct f2fs_sb_info * sbi,struct extent_tree * et,struct extent_info * ei,struct rb_node * parent,struct rb_node ** p,bool leftmost)235 static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
236 struct extent_tree *et, struct extent_info *ei,
237 struct rb_node *parent, struct rb_node **p,
238 bool leftmost)
239 {
240 struct extent_node *en;
241
242 en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi);
243 if (!en)
244 return NULL;
245
246 en->ei = *ei;
247 INIT_LIST_HEAD(&en->list);
248 en->et = et;
249
250 rb_link_node(&en->rb_node, parent, p);
251 rb_insert_color_cached(&en->rb_node, &et->root, leftmost);
252 atomic_inc(&et->node_cnt);
253 atomic_inc(&sbi->total_ext_node);
254 return en;
255 }
256
__detach_extent_node(struct f2fs_sb_info * sbi,struct extent_tree * et,struct extent_node * en)257 static void __detach_extent_node(struct f2fs_sb_info *sbi,
258 struct extent_tree *et, struct extent_node *en)
259 {
260 rb_erase_cached(&en->rb_node, &et->root);
261 atomic_dec(&et->node_cnt);
262 atomic_dec(&sbi->total_ext_node);
263
264 if (et->cached_en == en)
265 et->cached_en = NULL;
266 kmem_cache_free(extent_node_slab, en);
267 }
268
269 /*
270 * Flow to release an extent_node:
271 * 1. list_del_init
272 * 2. __detach_extent_node
273 * 3. kmem_cache_free.
274 */
__release_extent_node(struct f2fs_sb_info * sbi,struct extent_tree * et,struct extent_node * en)275 static void __release_extent_node(struct f2fs_sb_info *sbi,
276 struct extent_tree *et, struct extent_node *en)
277 {
278 spin_lock(&sbi->extent_lock);
279 f2fs_bug_on(sbi, list_empty(&en->list));
280 list_del_init(&en->list);
281 spin_unlock(&sbi->extent_lock);
282
283 __detach_extent_node(sbi, et, en);
284 }
285
__grab_extent_tree(struct inode * inode)286 static struct extent_tree *__grab_extent_tree(struct inode *inode)
287 {
288 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
289 struct extent_tree *et;
290 nid_t ino = inode->i_ino;
291
292 mutex_lock(&sbi->extent_tree_lock);
293 et = radix_tree_lookup(&sbi->extent_tree_root, ino);
294 if (!et) {
295 et = f2fs_kmem_cache_alloc(extent_tree_slab,
296 GFP_NOFS, true, NULL);
297 f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et);
298 memset(et, 0, sizeof(struct extent_tree));
299 et->ino = ino;
300 et->root = RB_ROOT_CACHED;
301 et->cached_en = NULL;
302 rwlock_init(&et->lock);
303 INIT_LIST_HEAD(&et->list);
304 atomic_set(&et->node_cnt, 0);
305 atomic_inc(&sbi->total_ext_tree);
306 } else {
307 atomic_dec(&sbi->total_zombie_tree);
308 list_del_init(&et->list);
309 }
310 mutex_unlock(&sbi->extent_tree_lock);
311
312 /* never died until evict_inode */
313 F2FS_I(inode)->extent_tree = et;
314
315 return et;
316 }
317
__init_extent_tree(struct f2fs_sb_info * sbi,struct extent_tree * et,struct extent_info * ei)318 static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi,
319 struct extent_tree *et, struct extent_info *ei)
320 {
321 struct rb_node **p = &et->root.rb_root.rb_node;
322 struct extent_node *en;
323
324 en = __attach_extent_node(sbi, et, ei, NULL, p, true);
325 if (!en)
326 return NULL;
327
328 et->largest = en->ei;
329 et->cached_en = en;
330 return en;
331 }
332
__free_extent_tree(struct f2fs_sb_info * sbi,struct extent_tree * et)333 static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
334 struct extent_tree *et)
335 {
336 struct rb_node *node, *next;
337 struct extent_node *en;
338 unsigned int count = atomic_read(&et->node_cnt);
339
340 node = rb_first_cached(&et->root);
341 while (node) {
342 next = rb_next(node);
343 en = rb_entry(node, struct extent_node, rb_node);
344 __release_extent_node(sbi, et, en);
345 node = next;
346 }
347
348 return count - atomic_read(&et->node_cnt);
349 }
350
__drop_largest_extent(struct extent_tree * et,pgoff_t fofs,unsigned int len)351 static void __drop_largest_extent(struct extent_tree *et,
352 pgoff_t fofs, unsigned int len)
353 {
354 if (fofs < et->largest.fofs + et->largest.len &&
355 fofs + len > et->largest.fofs) {
356 et->largest.len = 0;
357 et->largest_updated = true;
358 }
359 }
360
361 /* return true, if inode page is changed */
__f2fs_init_extent_tree(struct inode * inode,struct page * ipage)362 static void __f2fs_init_extent_tree(struct inode *inode, struct page *ipage)
363 {
364 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
365 struct f2fs_extent *i_ext = ipage ? &F2FS_INODE(ipage)->i_ext : NULL;
366 struct extent_tree *et;
367 struct extent_node *en;
368 struct extent_info ei;
369
370 if (!f2fs_may_extent_tree(inode)) {
371 /* drop largest extent */
372 if (i_ext && i_ext->len) {
373 f2fs_wait_on_page_writeback(ipage, NODE, true, true);
374 i_ext->len = 0;
375 set_page_dirty(ipage);
376 return;
377 }
378 return;
379 }
380
381 et = __grab_extent_tree(inode);
382
383 if (!i_ext || !i_ext->len)
384 return;
385
386 get_extent_info(&ei, i_ext);
387
388 write_lock(&et->lock);
389 if (atomic_read(&et->node_cnt))
390 goto out;
391
392 en = __init_extent_tree(sbi, et, &ei);
393 if (en) {
394 spin_lock(&sbi->extent_lock);
395 list_add_tail(&en->list, &sbi->extent_list);
396 spin_unlock(&sbi->extent_lock);
397 }
398 out:
399 write_unlock(&et->lock);
400 }
401
f2fs_init_extent_tree(struct inode * inode,struct page * ipage)402 void f2fs_init_extent_tree(struct inode *inode, struct page *ipage)
403 {
404 __f2fs_init_extent_tree(inode, ipage);
405
406 if (!F2FS_I(inode)->extent_tree)
407 set_inode_flag(inode, FI_NO_EXTENT);
408 }
409
f2fs_lookup_extent_tree(struct inode * inode,pgoff_t pgofs,struct extent_info * ei)410 static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
411 struct extent_info *ei)
412 {
413 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
414 struct extent_tree *et = F2FS_I(inode)->extent_tree;
415 struct extent_node *en;
416 bool ret = false;
417
418 if (!et)
419 return false;
420
421 trace_f2fs_lookup_extent_tree_start(inode, pgofs);
422
423 read_lock(&et->lock);
424
425 if (et->largest.fofs <= pgofs &&
426 et->largest.fofs + et->largest.len > pgofs) {
427 *ei = et->largest;
428 ret = true;
429 stat_inc_largest_node_hit(sbi);
430 goto out;
431 }
432
433 en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root,
434 (struct rb_entry *)et->cached_en, pgofs);
435 if (!en)
436 goto out;
437
438 if (en == et->cached_en)
439 stat_inc_cached_node_hit(sbi);
440 else
441 stat_inc_rbtree_node_hit(sbi);
442
443 *ei = en->ei;
444 spin_lock(&sbi->extent_lock);
445 if (!list_empty(&en->list)) {
446 list_move_tail(&en->list, &sbi->extent_list);
447 et->cached_en = en;
448 }
449 spin_unlock(&sbi->extent_lock);
450 ret = true;
451 out:
452 stat_inc_total_hit(sbi);
453 read_unlock(&et->lock);
454
455 trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei);
456 return ret;
457 }
458
__try_merge_extent_node(struct f2fs_sb_info * sbi,struct extent_tree * et,struct extent_info * ei,struct extent_node * prev_ex,struct extent_node * next_ex)459 static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
460 struct extent_tree *et, struct extent_info *ei,
461 struct extent_node *prev_ex,
462 struct extent_node *next_ex)
463 {
464 struct extent_node *en = NULL;
465
466 if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) {
467 prev_ex->ei.len += ei->len;
468 ei = &prev_ex->ei;
469 en = prev_ex;
470 }
471
472 if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) {
473 next_ex->ei.fofs = ei->fofs;
474 next_ex->ei.blk = ei->blk;
475 next_ex->ei.len += ei->len;
476 if (en)
477 __release_extent_node(sbi, et, prev_ex);
478
479 en = next_ex;
480 }
481
482 if (!en)
483 return NULL;
484
485 __try_update_largest_extent(et, en);
486
487 spin_lock(&sbi->extent_lock);
488 if (!list_empty(&en->list)) {
489 list_move_tail(&en->list, &sbi->extent_list);
490 et->cached_en = en;
491 }
492 spin_unlock(&sbi->extent_lock);
493 return en;
494 }
495
__insert_extent_tree(struct f2fs_sb_info * sbi,struct extent_tree * et,struct extent_info * ei,struct rb_node ** insert_p,struct rb_node * insert_parent,bool leftmost)496 static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
497 struct extent_tree *et, struct extent_info *ei,
498 struct rb_node **insert_p,
499 struct rb_node *insert_parent,
500 bool leftmost)
501 {
502 struct rb_node **p;
503 struct rb_node *parent = NULL;
504 struct extent_node *en = NULL;
505
506 if (insert_p && insert_parent) {
507 parent = insert_parent;
508 p = insert_p;
509 goto do_insert;
510 }
511
512 leftmost = true;
513
514 p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent,
515 ei->fofs, &leftmost);
516 do_insert:
517 en = __attach_extent_node(sbi, et, ei, parent, p, leftmost);
518 if (!en)
519 return NULL;
520
521 __try_update_largest_extent(et, en);
522
523 /* update in global extent list */
524 spin_lock(&sbi->extent_lock);
525 list_add_tail(&en->list, &sbi->extent_list);
526 et->cached_en = en;
527 spin_unlock(&sbi->extent_lock);
528 return en;
529 }
530
f2fs_update_extent_tree_range(struct inode * inode,pgoff_t fofs,block_t blkaddr,unsigned int len)531 static void f2fs_update_extent_tree_range(struct inode *inode,
532 pgoff_t fofs, block_t blkaddr, unsigned int len)
533 {
534 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
535 struct extent_tree *et = F2FS_I(inode)->extent_tree;
536 struct extent_node *en = NULL, *en1 = NULL;
537 struct extent_node *prev_en = NULL, *next_en = NULL;
538 struct extent_info ei, dei, prev;
539 struct rb_node **insert_p = NULL, *insert_parent = NULL;
540 unsigned int end = fofs + len;
541 unsigned int pos = (unsigned int)fofs;
542 bool updated = false;
543 bool leftmost = false;
544
545 if (!et)
546 return;
547
548 trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, len, 0);
549
550 write_lock(&et->lock);
551
552 if (is_inode_flag_set(inode, FI_NO_EXTENT)) {
553 write_unlock(&et->lock);
554 return;
555 }
556
557 prev = et->largest;
558 dei.len = 0;
559
560 /*
561 * drop largest extent before lookup, in case it's already
562 * been shrunk from extent tree
563 */
564 __drop_largest_extent(et, fofs, len);
565
566 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
567 en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root,
568 (struct rb_entry *)et->cached_en, fofs,
569 (struct rb_entry **)&prev_en,
570 (struct rb_entry **)&next_en,
571 &insert_p, &insert_parent, false,
572 &leftmost);
573 if (!en)
574 en = next_en;
575
576 /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */
577 while (en && en->ei.fofs < end) {
578 unsigned int org_end;
579 int parts = 0; /* # of parts current extent split into */
580
581 next_en = en1 = NULL;
582
583 dei = en->ei;
584 org_end = dei.fofs + dei.len;
585 f2fs_bug_on(sbi, pos >= org_end);
586
587 if (pos > dei.fofs && pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) {
588 en->ei.len = pos - en->ei.fofs;
589 prev_en = en;
590 parts = 1;
591 }
592
593 if (end < org_end && org_end - end >= F2FS_MIN_EXTENT_LEN) {
594 if (parts) {
595 set_extent_info(&ei, end,
596 end - dei.fofs + dei.blk,
597 org_end - end);
598 en1 = __insert_extent_tree(sbi, et, &ei,
599 NULL, NULL, true);
600 next_en = en1;
601 } else {
602 en->ei.fofs = end;
603 en->ei.blk += end - dei.fofs;
604 en->ei.len -= end - dei.fofs;
605 next_en = en;
606 }
607 parts++;
608 }
609
610 if (!next_en) {
611 struct rb_node *node = rb_next(&en->rb_node);
612
613 next_en = rb_entry_safe(node, struct extent_node,
614 rb_node);
615 }
616
617 if (parts)
618 __try_update_largest_extent(et, en);
619 else
620 __release_extent_node(sbi, et, en);
621
622 /*
623 * if original extent is split into zero or two parts, extent
624 * tree has been altered by deletion or insertion, therefore
625 * invalidate pointers regard to tree.
626 */
627 if (parts != 1) {
628 insert_p = NULL;
629 insert_parent = NULL;
630 }
631 en = next_en;
632 }
633
634 /* 3. update extent in extent cache */
635 if (blkaddr) {
636
637 set_extent_info(&ei, fofs, blkaddr, len);
638 if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
639 __insert_extent_tree(sbi, et, &ei,
640 insert_p, insert_parent, leftmost);
641
642 /* give up extent_cache, if split and small updates happen */
643 if (dei.len >= 1 &&
644 prev.len < F2FS_MIN_EXTENT_LEN &&
645 et->largest.len < F2FS_MIN_EXTENT_LEN) {
646 et->largest.len = 0;
647 et->largest_updated = true;
648 set_inode_flag(inode, FI_NO_EXTENT);
649 }
650 }
651
652 if (is_inode_flag_set(inode, FI_NO_EXTENT))
653 __free_extent_tree(sbi, et);
654
655 if (et->largest_updated) {
656 et->largest_updated = false;
657 updated = true;
658 }
659
660 write_unlock(&et->lock);
661
662 if (updated)
663 f2fs_mark_inode_dirty_sync(inode, true);
664 }
665
666 #ifdef CONFIG_F2FS_FS_COMPRESSION
f2fs_update_extent_tree_range_compressed(struct inode * inode,pgoff_t fofs,block_t blkaddr,unsigned int llen,unsigned int c_len)667 void f2fs_update_extent_tree_range_compressed(struct inode *inode,
668 pgoff_t fofs, block_t blkaddr, unsigned int llen,
669 unsigned int c_len)
670 {
671 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
672 struct extent_tree *et = F2FS_I(inode)->extent_tree;
673 struct extent_node *en = NULL;
674 struct extent_node *prev_en = NULL, *next_en = NULL;
675 struct extent_info ei;
676 struct rb_node **insert_p = NULL, *insert_parent = NULL;
677 bool leftmost = false;
678
679 trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, llen, c_len);
680
681 /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */
682 if (is_inode_flag_set(inode, FI_NO_EXTENT))
683 return;
684
685 write_lock(&et->lock);
686
687 en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root,
688 (struct rb_entry *)et->cached_en, fofs,
689 (struct rb_entry **)&prev_en,
690 (struct rb_entry **)&next_en,
691 &insert_p, &insert_parent, false,
692 &leftmost);
693 if (en)
694 goto unlock_out;
695
696 set_extent_info(&ei, fofs, blkaddr, llen);
697 ei.c_len = c_len;
698
699 if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
700 __insert_extent_tree(sbi, et, &ei,
701 insert_p, insert_parent, leftmost);
702 unlock_out:
703 write_unlock(&et->lock);
704 }
705 #endif
706
f2fs_shrink_extent_tree(struct f2fs_sb_info * sbi,int nr_shrink)707 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
708 {
709 struct extent_tree *et, *next;
710 struct extent_node *en;
711 unsigned int node_cnt = 0, tree_cnt = 0;
712 int remained;
713
714 if (!test_opt(sbi, EXTENT_CACHE))
715 return 0;
716
717 if (!atomic_read(&sbi->total_zombie_tree))
718 goto free_node;
719
720 if (!mutex_trylock(&sbi->extent_tree_lock))
721 goto out;
722
723 /* 1. remove unreferenced extent tree */
724 list_for_each_entry_safe(et, next, &sbi->zombie_list, list) {
725 if (atomic_read(&et->node_cnt)) {
726 write_lock(&et->lock);
727 node_cnt += __free_extent_tree(sbi, et);
728 write_unlock(&et->lock);
729 }
730 f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
731 list_del_init(&et->list);
732 radix_tree_delete(&sbi->extent_tree_root, et->ino);
733 kmem_cache_free(extent_tree_slab, et);
734 atomic_dec(&sbi->total_ext_tree);
735 atomic_dec(&sbi->total_zombie_tree);
736 tree_cnt++;
737
738 if (node_cnt + tree_cnt >= nr_shrink)
739 goto unlock_out;
740 cond_resched();
741 }
742 mutex_unlock(&sbi->extent_tree_lock);
743
744 free_node:
745 /* 2. remove LRU extent entries */
746 if (!mutex_trylock(&sbi->extent_tree_lock))
747 goto out;
748
749 remained = nr_shrink - (node_cnt + tree_cnt);
750
751 spin_lock(&sbi->extent_lock);
752 for (; remained > 0; remained--) {
753 if (list_empty(&sbi->extent_list))
754 break;
755 en = list_first_entry(&sbi->extent_list,
756 struct extent_node, list);
757 et = en->et;
758 if (!write_trylock(&et->lock)) {
759 /* refresh this extent node's position in extent list */
760 list_move_tail(&en->list, &sbi->extent_list);
761 continue;
762 }
763
764 list_del_init(&en->list);
765 spin_unlock(&sbi->extent_lock);
766
767 __detach_extent_node(sbi, et, en);
768
769 write_unlock(&et->lock);
770 node_cnt++;
771 spin_lock(&sbi->extent_lock);
772 }
773 spin_unlock(&sbi->extent_lock);
774
775 unlock_out:
776 mutex_unlock(&sbi->extent_tree_lock);
777 out:
778 trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
779
780 return node_cnt + tree_cnt;
781 }
782
f2fs_destroy_extent_node(struct inode * inode)783 unsigned int f2fs_destroy_extent_node(struct inode *inode)
784 {
785 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
786 struct extent_tree *et = F2FS_I(inode)->extent_tree;
787 unsigned int node_cnt = 0;
788
789 if (!et || !atomic_read(&et->node_cnt))
790 return 0;
791
792 write_lock(&et->lock);
793 node_cnt = __free_extent_tree(sbi, et);
794 write_unlock(&et->lock);
795
796 return node_cnt;
797 }
798
f2fs_drop_extent_tree(struct inode * inode)799 void f2fs_drop_extent_tree(struct inode *inode)
800 {
801 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
802 struct extent_tree *et = F2FS_I(inode)->extent_tree;
803 bool updated = false;
804
805 if (!f2fs_may_extent_tree(inode))
806 return;
807
808 write_lock(&et->lock);
809 set_inode_flag(inode, FI_NO_EXTENT);
810 __free_extent_tree(sbi, et);
811 if (et->largest.len) {
812 et->largest.len = 0;
813 updated = true;
814 }
815 write_unlock(&et->lock);
816 if (updated)
817 f2fs_mark_inode_dirty_sync(inode, true);
818 }
819
f2fs_destroy_extent_tree(struct inode * inode)820 void f2fs_destroy_extent_tree(struct inode *inode)
821 {
822 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
823 struct extent_tree *et = F2FS_I(inode)->extent_tree;
824 unsigned int node_cnt = 0;
825
826 if (!et)
827 return;
828
829 if (inode->i_nlink && !is_bad_inode(inode) &&
830 atomic_read(&et->node_cnt)) {
831 mutex_lock(&sbi->extent_tree_lock);
832 list_add_tail(&et->list, &sbi->zombie_list);
833 atomic_inc(&sbi->total_zombie_tree);
834 mutex_unlock(&sbi->extent_tree_lock);
835 return;
836 }
837
838 /* free all extent info belong to this extent tree */
839 node_cnt = f2fs_destroy_extent_node(inode);
840
841 /* delete extent tree entry in radix tree */
842 mutex_lock(&sbi->extent_tree_lock);
843 f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
844 radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
845 kmem_cache_free(extent_tree_slab, et);
846 atomic_dec(&sbi->total_ext_tree);
847 mutex_unlock(&sbi->extent_tree_lock);
848
849 F2FS_I(inode)->extent_tree = NULL;
850
851 trace_f2fs_destroy_extent_tree(inode, node_cnt);
852 }
853
f2fs_lookup_extent_cache(struct inode * inode,pgoff_t pgofs,struct extent_info * ei)854 bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
855 struct extent_info *ei)
856 {
857 if (!f2fs_may_extent_tree(inode))
858 return false;
859
860 return f2fs_lookup_extent_tree(inode, pgofs, ei);
861 }
862
f2fs_update_extent_cache(struct dnode_of_data * dn)863 void f2fs_update_extent_cache(struct dnode_of_data *dn)
864 {
865 pgoff_t fofs;
866 block_t blkaddr;
867
868 if (!f2fs_may_extent_tree(dn->inode))
869 return;
870
871 if (dn->data_blkaddr == NEW_ADDR)
872 blkaddr = NULL_ADDR;
873 else
874 blkaddr = dn->data_blkaddr;
875
876 fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) +
877 dn->ofs_in_node;
878 f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, 1);
879 }
880
f2fs_update_extent_cache_range(struct dnode_of_data * dn,pgoff_t fofs,block_t blkaddr,unsigned int len)881 void f2fs_update_extent_cache_range(struct dnode_of_data *dn,
882 pgoff_t fofs, block_t blkaddr, unsigned int len)
883
884 {
885 if (!f2fs_may_extent_tree(dn->inode))
886 return;
887
888 f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len);
889 }
890
f2fs_init_extent_cache_info(struct f2fs_sb_info * sbi)891 void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi)
892 {
893 INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO);
894 mutex_init(&sbi->extent_tree_lock);
895 INIT_LIST_HEAD(&sbi->extent_list);
896 spin_lock_init(&sbi->extent_lock);
897 atomic_set(&sbi->total_ext_tree, 0);
898 INIT_LIST_HEAD(&sbi->zombie_list);
899 atomic_set(&sbi->total_zombie_tree, 0);
900 atomic_set(&sbi->total_ext_node, 0);
901 }
902
f2fs_create_extent_cache(void)903 int __init f2fs_create_extent_cache(void)
904 {
905 extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
906 sizeof(struct extent_tree));
907 if (!extent_tree_slab)
908 return -ENOMEM;
909 extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
910 sizeof(struct extent_node));
911 if (!extent_node_slab) {
912 kmem_cache_destroy(extent_tree_slab);
913 return -ENOMEM;
914 }
915 return 0;
916 }
917
f2fs_destroy_extent_cache(void)918 void f2fs_destroy_extent_cache(void)
919 {
920 kmem_cache_destroy(extent_node_slab);
921 kmem_cache_destroy(extent_tree_slab);
922 }
923