summaryrefslogtreecommitdiffstats
path: root/fs/f2fs
diff options
context:
space:
mode:
authorChao Yu <chao2.yu@samsung.com>2015-07-08 05:59:36 -0400
committerJaegeuk Kim <jaegeuk@kernel.org>2015-08-04 17:09:58 -0400
commita28ef1f5aebe1068fc5fd65c4699c1c3b1e9094b (patch)
treec66873bd837f453243bde9b6342346e8e992f313 /fs/f2fs
parent3c7df87dad065a4656b13115593c59c8a324a108 (diff)
f2fs: maintain extent cache in separated file
This patch moves extent cache related code from data.c into extent_cache.c since extent cache is independent feature, and its codes are not relate to others in data.c, it's better for us to maintain them in separated place. There is no functionality change, but several small coding style fixes including: * rename __drop_largest_extent to f2fs_drop_largest_extent for exporting; * rename misspelled word 'untill' to 'until'; * remove unneeded 'return' in the end of f2fs_destroy_extent_tree(). Signed-off-by: Chao Yu <chao2.yu@samsung.com> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
Diffstat (limited to 'fs/f2fs')
-rw-r--r--fs/f2fs/Makefile2
-rw-r--r--fs/f2fs/data.c578
-rw-r--r--fs/f2fs/extent_cache.c594
-rw-r--r--fs/f2fs/f2fs.h22
4 files changed, 610 insertions, 586 deletions
diff --git a/fs/f2fs/Makefile b/fs/f2fs/Makefile
index 005251b8d459..08e101ed914c 100644
--- a/fs/f2fs/Makefile
+++ b/fs/f2fs/Makefile
@@ -2,7 +2,7 @@ obj-$(CONFIG_F2FS_FS) += f2fs.o
2 2
3f2fs-y := dir.o file.o inode.o namei.o hash.o super.o inline.o 3f2fs-y := dir.o file.o inode.o namei.o hash.o super.o inline.o
4f2fs-y += checkpoint.o gc.o data.o node.o segment.o recovery.o 4f2fs-y += checkpoint.o gc.o data.o node.o segment.o recovery.o
5f2fs-y += shrinker.o 5f2fs-y += shrinker.o extent_cache.o
6f2fs-$(CONFIG_F2FS_STAT_FS) += debug.o 6f2fs-$(CONFIG_F2FS_STAT_FS) += debug.o
7f2fs-$(CONFIG_F2FS_FS_XATTR) += xattr.o 7f2fs-$(CONFIG_F2FS_FS_XATTR) += xattr.o
8f2fs-$(CONFIG_F2FS_FS_POSIX_ACL) += acl.o 8f2fs-$(CONFIG_F2FS_FS_POSIX_ACL) += acl.o
diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index ce0d5ec8e770..ef30b59756c6 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -26,9 +26,6 @@
26#include "trace.h" 26#include "trace.h"
27#include <trace/events/f2fs.h> 27#include <trace/events/f2fs.h>
28 28
29static struct kmem_cache *extent_tree_slab;
30static struct kmem_cache *extent_node_slab;
31
32static void f2fs_read_end_io(struct bio *bio, int err) 29static void f2fs_read_end_io(struct bio *bio, int err)
33{ 30{
34 struct bio_vec *bvec; 31 struct bio_vec *bvec;
@@ -266,548 +263,6 @@ int f2fs_reserve_block(struct dnode_of_data *dn, pgoff_t index)
266 return err; 263 return err;
267} 264}
268 265
269static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
270 struct extent_tree *et, struct extent_info *ei,
271 struct rb_node *parent, struct rb_node **p)
272{
273 struct extent_node *en;
274
275 en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC);
276 if (!en)
277 return NULL;
278
279 en->ei = *ei;
280 INIT_LIST_HEAD(&en->list);
281
282 rb_link_node(&en->rb_node, parent, p);
283 rb_insert_color(&en->rb_node, &et->root);
284 et->count++;
285 atomic_inc(&sbi->total_ext_node);
286 return en;
287}
288
289static void __detach_extent_node(struct f2fs_sb_info *sbi,
290 struct extent_tree *et, struct extent_node *en)
291{
292 rb_erase(&en->rb_node, &et->root);
293 et->count--;
294 atomic_dec(&sbi->total_ext_node);
295
296 if (et->cached_en == en)
297 et->cached_en = NULL;
298}
299
300static struct extent_tree *__grab_extent_tree(struct inode *inode)
301{
302 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
303 struct extent_tree *et;
304 nid_t ino = inode->i_ino;
305
306 down_write(&sbi->extent_tree_lock);
307 et = radix_tree_lookup(&sbi->extent_tree_root, ino);
308 if (!et) {
309 et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS);
310 f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et);
311 memset(et, 0, sizeof(struct extent_tree));
312 et->ino = ino;
313 et->root = RB_ROOT;
314 et->cached_en = NULL;
315 rwlock_init(&et->lock);
316 atomic_set(&et->refcount, 0);
317 et->count = 0;
318 sbi->total_ext_tree++;
319 }
320 atomic_inc(&et->refcount);
321 up_write(&sbi->extent_tree_lock);
322
323 /* never died untill evict_inode */
324 F2FS_I(inode)->extent_tree = et;
325
326 return et;
327}
328
329static struct extent_node *__lookup_extent_tree(struct extent_tree *et,
330 unsigned int fofs)
331{
332 struct rb_node *node = et->root.rb_node;
333 struct extent_node *en;
334
335 if (et->cached_en) {
336 struct extent_info *cei = &et->cached_en->ei;
337
338 if (cei->fofs <= fofs && cei->fofs + cei->len > fofs)
339 return et->cached_en;
340 }
341
342 while (node) {
343 en = rb_entry(node, struct extent_node, rb_node);
344
345 if (fofs < en->ei.fofs)
346 node = node->rb_left;
347 else if (fofs >= en->ei.fofs + en->ei.len)
348 node = node->rb_right;
349 else
350 return en;
351 }
352 return NULL;
353}
354
355static struct extent_node *__try_back_merge(struct f2fs_sb_info *sbi,
356 struct extent_tree *et, struct extent_node *en)
357{
358 struct extent_node *prev;
359 struct rb_node *node;
360
361 node = rb_prev(&en->rb_node);
362 if (!node)
363 return NULL;
364
365 prev = rb_entry(node, struct extent_node, rb_node);
366 if (__is_back_mergeable(&en->ei, &prev->ei)) {
367 en->ei.fofs = prev->ei.fofs;
368 en->ei.blk = prev->ei.blk;
369 en->ei.len += prev->ei.len;
370 __detach_extent_node(sbi, et, prev);
371 return prev;
372 }
373 return NULL;
374}
375
376static struct extent_node *__try_front_merge(struct f2fs_sb_info *sbi,
377 struct extent_tree *et, struct extent_node *en)
378{
379 struct extent_node *next;
380 struct rb_node *node;
381
382 node = rb_next(&en->rb_node);
383 if (!node)
384 return NULL;
385
386 next = rb_entry(node, struct extent_node, rb_node);
387 if (__is_front_mergeable(&en->ei, &next->ei)) {
388 en->ei.len += next->ei.len;
389 __detach_extent_node(sbi, et, next);
390 return next;
391 }
392 return NULL;
393}
394
395static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
396 struct extent_tree *et, struct extent_info *ei,
397 struct extent_node **den)
398{
399 struct rb_node **p = &et->root.rb_node;
400 struct rb_node *parent = NULL;
401 struct extent_node *en;
402
403 while (*p) {
404 parent = *p;
405 en = rb_entry(parent, struct extent_node, rb_node);
406
407 if (ei->fofs < en->ei.fofs) {
408 if (__is_front_mergeable(ei, &en->ei)) {
409 f2fs_bug_on(sbi, !den);
410 en->ei.fofs = ei->fofs;
411 en->ei.blk = ei->blk;
412 en->ei.len += ei->len;
413 *den = __try_back_merge(sbi, et, en);
414 goto update_out;
415 }
416 p = &(*p)->rb_left;
417 } else if (ei->fofs >= en->ei.fofs + en->ei.len) {
418 if (__is_back_mergeable(ei, &en->ei)) {
419 f2fs_bug_on(sbi, !den);
420 en->ei.len += ei->len;
421 *den = __try_front_merge(sbi, et, en);
422 goto update_out;
423 }
424 p = &(*p)->rb_right;
425 } else {
426 f2fs_bug_on(sbi, 1);
427 }
428 }
429
430 en = __attach_extent_node(sbi, et, ei, parent, p);
431 if (!en)
432 return NULL;
433update_out:
434 if (en->ei.len > et->largest.len)
435 et->largest = en->ei;
436 et->cached_en = en;
437 return en;
438}
439
440static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
441 struct extent_tree *et, bool free_all)
442{
443 struct rb_node *node, *next;
444 struct extent_node *en;
445 unsigned int count = et->count;
446
447 node = rb_first(&et->root);
448 while (node) {
449 next = rb_next(node);
450 en = rb_entry(node, struct extent_node, rb_node);
451
452 if (free_all) {
453 spin_lock(&sbi->extent_lock);
454 if (!list_empty(&en->list))
455 list_del_init(&en->list);
456 spin_unlock(&sbi->extent_lock);
457 }
458
459 if (free_all || list_empty(&en->list)) {
460 __detach_extent_node(sbi, et, en);
461 kmem_cache_free(extent_node_slab, en);
462 }
463 node = next;
464 }
465
466 return count - et->count;
467}
468
469static void __drop_largest_extent(struct inode *inode, pgoff_t fofs)
470{
471 struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest;
472
473 if (largest->fofs <= fofs && largest->fofs + largest->len > fofs)
474 largest->len = 0;
475}
476
477void f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext)
478{
479 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
480 struct extent_tree *et;
481 struct extent_node *en;
482 struct extent_info ei;
483
484 if (!f2fs_may_extent_tree(inode))
485 return;
486
487 et = __grab_extent_tree(inode);
488
489 if (!i_ext || le32_to_cpu(i_ext->len) < F2FS_MIN_EXTENT_LEN)
490 return;
491
492 set_extent_info(&ei, le32_to_cpu(i_ext->fofs),
493 le32_to_cpu(i_ext->blk), le32_to_cpu(i_ext->len));
494
495 write_lock(&et->lock);
496 if (et->count)
497 goto out;
498
499 en = __insert_extent_tree(sbi, et, &ei, NULL);
500 if (en) {
501 spin_lock(&sbi->extent_lock);
502 list_add_tail(&en->list, &sbi->extent_list);
503 spin_unlock(&sbi->extent_lock);
504 }
505out:
506 write_unlock(&et->lock);
507}
508
509static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
510 struct extent_info *ei)
511{
512 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
513 struct extent_tree *et = F2FS_I(inode)->extent_tree;
514 struct extent_node *en;
515 bool ret = false;
516
517 f2fs_bug_on(sbi, !et);
518
519 trace_f2fs_lookup_extent_tree_start(inode, pgofs);
520
521 read_lock(&et->lock);
522
523 if (et->largest.fofs <= pgofs &&
524 et->largest.fofs + et->largest.len > pgofs) {
525 *ei = et->largest;
526 ret = true;
527 stat_inc_read_hit(sbi->sb);
528 goto out;
529 }
530
531 en = __lookup_extent_tree(et, pgofs);
532 if (en) {
533 *ei = en->ei;
534 spin_lock(&sbi->extent_lock);
535 if (!list_empty(&en->list))
536 list_move_tail(&en->list, &sbi->extent_list);
537 et->cached_en = en;
538 spin_unlock(&sbi->extent_lock);
539 ret = true;
540 stat_inc_read_hit(sbi->sb);
541 }
542out:
543 stat_inc_total_hit(sbi->sb);
544 read_unlock(&et->lock);
545
546 trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei);
547 return ret;
548}
549
550/* return true, if on-disk extent should be updated */
551static bool f2fs_update_extent_tree(struct inode *inode, pgoff_t fofs,
552 block_t blkaddr)
553{
554 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
555 struct extent_tree *et = F2FS_I(inode)->extent_tree;
556 struct extent_node *en = NULL, *en1 = NULL, *en2 = NULL, *en3 = NULL;
557 struct extent_node *den = NULL;
558 struct extent_info ei, dei, prev;
559 unsigned int endofs;
560
561 if (!et)
562 return false;
563
564 trace_f2fs_update_extent_tree(inode, fofs, blkaddr);
565
566 write_lock(&et->lock);
567
568 if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) {
569 write_unlock(&et->lock);
570 return false;
571 }
572
573 prev = et->largest;
574 dei.len = 0;
575
576 /* we do not guarantee that the largest extent is cached all the time */
577 __drop_largest_extent(inode, fofs);
578
579 /* 1. lookup and remove existing extent info in cache */
580 en = __lookup_extent_tree(et, fofs);
581 if (!en)
582 goto update_extent;
583
584 dei = en->ei;
585 __detach_extent_node(sbi, et, en);
586
587 /* 2. if extent can be split more, split and insert the left part */
588 if (dei.len > F2FS_MIN_EXTENT_LEN) {
589 /* insert left part of split extent into cache */
590 if (fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN) {
591 set_extent_info(&ei, dei.fofs, dei.blk,
592 fofs - dei.fofs);
593 en1 = __insert_extent_tree(sbi, et, &ei, NULL);
594 }
595
596 /* insert right part of split extent into cache */
597 endofs = dei.fofs + dei.len - 1;
598 if (endofs - fofs >= F2FS_MIN_EXTENT_LEN) {
599 set_extent_info(&ei, fofs + 1,
600 fofs - dei.fofs + dei.blk + 1, endofs - fofs);
601 en2 = __insert_extent_tree(sbi, et, &ei, NULL);
602 }
603 }
604
605update_extent:
606 /* 3. update extent in extent cache */
607 if (blkaddr) {
608 set_extent_info(&ei, fofs, blkaddr, 1);
609 en3 = __insert_extent_tree(sbi, et, &ei, &den);
610
611 /* give up extent_cache, if split and small updates happen */
612 if (dei.len >= 1 &&
613 prev.len < F2FS_MIN_EXTENT_LEN &&
614 et->largest.len < F2FS_MIN_EXTENT_LEN) {
615 et->largest.len = 0;
616 set_inode_flag(F2FS_I(inode), FI_NO_EXTENT);
617 }
618 }
619
620 /* 4. update in global extent list */
621 spin_lock(&sbi->extent_lock);
622 if (en && !list_empty(&en->list))
623 list_del(&en->list);
624 /*
625 * en1 and en2 split from en, they will become more and more smaller
626 * fragments after splitting several times. So if the length is smaller
627 * than F2FS_MIN_EXTENT_LEN, we will not add them into extent tree.
628 */
629 if (en1)
630 list_add_tail(&en1->list, &sbi->extent_list);
631 if (en2)
632 list_add_tail(&en2->list, &sbi->extent_list);
633 if (en3) {
634 if (list_empty(&en3->list))
635 list_add_tail(&en3->list, &sbi->extent_list);
636 else
637 list_move_tail(&en3->list, &sbi->extent_list);
638 }
639 if (den && !list_empty(&den->list))
640 list_del(&den->list);
641 spin_unlock(&sbi->extent_lock);
642
643 /* 5. release extent node */
644 if (en)
645 kmem_cache_free(extent_node_slab, en);
646 if (den)
647 kmem_cache_free(extent_node_slab, den);
648
649 if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
650 __free_extent_tree(sbi, et, true);
651
652 write_unlock(&et->lock);
653
654 return !__is_extent_same(&prev, &et->largest);
655}
656
657unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
658{
659 struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
660 struct extent_node *en, *tmp;
661 unsigned long ino = F2FS_ROOT_INO(sbi);
662 struct radix_tree_root *root = &sbi->extent_tree_root;
663 unsigned int found;
664 unsigned int node_cnt = 0, tree_cnt = 0;
665 int remained;
666
667 if (!test_opt(sbi, EXTENT_CACHE))
668 return 0;
669
670 if (!down_write_trylock(&sbi->extent_tree_lock))
671 goto out;
672
673 /* 1. remove unreferenced extent tree */
674 while ((found = radix_tree_gang_lookup(root,
675 (void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
676 unsigned i;
677
678 ino = treevec[found - 1]->ino + 1;
679 for (i = 0; i < found; i++) {
680 struct extent_tree *et = treevec[i];
681
682 if (!atomic_read(&et->refcount)) {
683 write_lock(&et->lock);
684 node_cnt += __free_extent_tree(sbi, et, true);
685 write_unlock(&et->lock);
686
687 radix_tree_delete(root, et->ino);
688 kmem_cache_free(extent_tree_slab, et);
689 sbi->total_ext_tree--;
690 tree_cnt++;
691
692 if (node_cnt + tree_cnt >= nr_shrink)
693 goto unlock_out;
694 }
695 }
696 }
697 up_write(&sbi->extent_tree_lock);
698
699 /* 2. remove LRU extent entries */
700 if (!down_write_trylock(&sbi->extent_tree_lock))
701 goto out;
702
703 remained = nr_shrink - (node_cnt + tree_cnt);
704
705 spin_lock(&sbi->extent_lock);
706 list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
707 if (!remained--)
708 break;
709 list_del_init(&en->list);
710 }
711 spin_unlock(&sbi->extent_lock);
712
713 while ((found = radix_tree_gang_lookup(root,
714 (void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
715 unsigned i;
716
717 ino = treevec[found - 1]->ino + 1;
718 for (i = 0; i < found; i++) {
719 struct extent_tree *et = treevec[i];
720
721 write_lock(&et->lock);
722 node_cnt += __free_extent_tree(sbi, et, false);
723 write_unlock(&et->lock);
724
725 if (node_cnt + tree_cnt >= nr_shrink)
726 break;
727 }
728 }
729unlock_out:
730 up_write(&sbi->extent_tree_lock);
731out:
732 trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
733
734 return node_cnt + tree_cnt;
735}
736
737unsigned int f2fs_destroy_extent_node(struct inode *inode)
738{
739 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
740 struct extent_tree *et = F2FS_I(inode)->extent_tree;
741 unsigned int node_cnt = 0;
742
743 if (!et)
744 return 0;
745
746 write_lock(&et->lock);
747 node_cnt = __free_extent_tree(sbi, et, true);
748 write_unlock(&et->lock);
749
750 return node_cnt;
751}
752
753void f2fs_destroy_extent_tree(struct inode *inode)
754{
755 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
756 struct extent_tree *et = F2FS_I(inode)->extent_tree;
757 unsigned int node_cnt = 0;
758
759 if (!et)
760 return;
761
762 if (inode->i_nlink && !is_bad_inode(inode) && et->count) {
763 atomic_dec(&et->refcount);
764 return;
765 }
766
767 /* free all extent info belong to this extent tree */
768 node_cnt = f2fs_destroy_extent_node(inode);
769
770 /* delete extent tree entry in radix tree */
771 down_write(&sbi->extent_tree_lock);
772 atomic_dec(&et->refcount);
773 f2fs_bug_on(sbi, atomic_read(&et->refcount) || et->count);
774 radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
775 kmem_cache_free(extent_tree_slab, et);
776 sbi->total_ext_tree--;
777 up_write(&sbi->extent_tree_lock);
778
779 F2FS_I(inode)->extent_tree = NULL;
780
781 trace_f2fs_destroy_extent_tree(inode, node_cnt);
782 return;
783}
784
785static bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
786 struct extent_info *ei)
787{
788 if (!f2fs_may_extent_tree(inode))
789 return false;
790
791 return f2fs_lookup_extent_tree(inode, pgofs, ei);
792}
793
794void f2fs_update_extent_cache(struct dnode_of_data *dn)
795{
796 struct f2fs_inode_info *fi = F2FS_I(dn->inode);
797 pgoff_t fofs;
798
799 if (!f2fs_may_extent_tree(dn->inode))
800 return;
801
802 f2fs_bug_on(F2FS_I_SB(dn->inode), dn->data_blkaddr == NEW_ADDR);
803
804 fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) +
805 dn->ofs_in_node;
806
807 if (f2fs_update_extent_tree(dn->inode, fofs, dn->data_blkaddr))
808 sync_inode_page(dn);
809}
810
811struct page *get_read_data_page(struct inode *inode, pgoff_t index, int rw) 266struct page *get_read_data_page(struct inode *inode, pgoff_t index, int rw)
812{ 267{
813 struct address_space *mapping = inode->i_mapping; 268 struct address_space *mapping = inode->i_mapping;
@@ -1017,7 +472,7 @@ alloc:
1017 i_size_write(dn->inode, ((fofs + 1) << PAGE_CACHE_SHIFT)); 472 i_size_write(dn->inode, ((fofs + 1) << PAGE_CACHE_SHIFT));
1018 473
1019 /* direct IO doesn't use extent cache to maximize the performance */ 474 /* direct IO doesn't use extent cache to maximize the performance */
1020 __drop_largest_extent(dn->inode, fofs); 475 f2fs_drop_largest_extent(dn->inode, fofs);
1021 476
1022 return 0; 477 return 0;
1023} 478}
@@ -1997,37 +1452,6 @@ static sector_t f2fs_bmap(struct address_space *mapping, sector_t block)
1997 return generic_block_bmap(mapping, block, get_data_block); 1452 return generic_block_bmap(mapping, block, get_data_block);
1998} 1453}
1999 1454
2000void init_extent_cache_info(struct f2fs_sb_info *sbi)
2001{
2002 INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO);
2003 init_rwsem(&sbi->extent_tree_lock);
2004 INIT_LIST_HEAD(&sbi->extent_list);
2005 spin_lock_init(&sbi->extent_lock);
2006 sbi->total_ext_tree = 0;
2007 atomic_set(&sbi->total_ext_node, 0);
2008}
2009
2010int __init create_extent_cache(void)
2011{
2012 extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
2013 sizeof(struct extent_tree));
2014 if (!extent_tree_slab)
2015 return -ENOMEM;
2016 extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
2017 sizeof(struct extent_node));
2018 if (!extent_node_slab) {
2019 kmem_cache_destroy(extent_tree_slab);
2020 return -ENOMEM;
2021 }
2022 return 0;
2023}
2024
2025void destroy_extent_cache(void)
2026{
2027 kmem_cache_destroy(extent_node_slab);
2028 kmem_cache_destroy(extent_tree_slab);
2029}
2030
2031const struct address_space_operations f2fs_dblock_aops = { 1455const struct address_space_operations f2fs_dblock_aops = {
2032 .readpage = f2fs_read_data_page, 1456 .readpage = f2fs_read_data_page,
2033 .readpages = f2fs_read_data_pages, 1457 .readpages = f2fs_read_data_pages,
diff --git a/fs/f2fs/extent_cache.c b/fs/f2fs/extent_cache.c
new file mode 100644
index 000000000000..5f78fc1e818a
--- /dev/null
+++ b/fs/f2fs/extent_cache.c
@@ -0,0 +1,594 @@
1/*
2 * f2fs extent cache support
3 *
4 * Copyright (c) 2015 Motorola Mobility
5 * Copyright (c) 2015 Samsung Electronics
6 * Authors: Jaegeuk Kim <jaegeuk@kernel.org>
7 * Chao Yu <chao2.yu@samsung.com>
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
12 */
13
14#include <linux/fs.h>
15#include <linux/f2fs_fs.h>
16
17#include "f2fs.h"
18#include "node.h"
19#include <trace/events/f2fs.h>
20
21static struct kmem_cache *extent_tree_slab;
22static struct kmem_cache *extent_node_slab;
23
24static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
25 struct extent_tree *et, struct extent_info *ei,
26 struct rb_node *parent, struct rb_node **p)
27{
28 struct extent_node *en;
29
30 en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC);
31 if (!en)
32 return NULL;
33
34 en->ei = *ei;
35 INIT_LIST_HEAD(&en->list);
36
37 rb_link_node(&en->rb_node, parent, p);
38 rb_insert_color(&en->rb_node, &et->root);
39 et->count++;
40 atomic_inc(&sbi->total_ext_node);
41 return en;
42}
43
44static void __detach_extent_node(struct f2fs_sb_info *sbi,
45 struct extent_tree *et, struct extent_node *en)
46{
47 rb_erase(&en->rb_node, &et->root);
48 et->count--;
49 atomic_dec(&sbi->total_ext_node);
50
51 if (et->cached_en == en)
52 et->cached_en = NULL;
53}
54
55static struct extent_tree *__grab_extent_tree(struct inode *inode)
56{
57 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
58 struct extent_tree *et;
59 nid_t ino = inode->i_ino;
60
61 down_write(&sbi->extent_tree_lock);
62 et = radix_tree_lookup(&sbi->extent_tree_root, ino);
63 if (!et) {
64 et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS);
65 f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et);
66 memset(et, 0, sizeof(struct extent_tree));
67 et->ino = ino;
68 et->root = RB_ROOT;
69 et->cached_en = NULL;
70 rwlock_init(&et->lock);
71 atomic_set(&et->refcount, 0);
72 et->count = 0;
73 sbi->total_ext_tree++;
74 }
75 atomic_inc(&et->refcount);
76 up_write(&sbi->extent_tree_lock);
77
78 /* never died until evict_inode */
79 F2FS_I(inode)->extent_tree = et;
80
81 return et;
82}
83
84static struct extent_node *__lookup_extent_tree(struct extent_tree *et,
85 unsigned int fofs)
86{
87 struct rb_node *node = et->root.rb_node;
88 struct extent_node *en;
89
90 if (et->cached_en) {
91 struct extent_info *cei = &et->cached_en->ei;
92
93 if (cei->fofs <= fofs && cei->fofs + cei->len > fofs)
94 return et->cached_en;
95 }
96
97 while (node) {
98 en = rb_entry(node, struct extent_node, rb_node);
99
100 if (fofs < en->ei.fofs)
101 node = node->rb_left;
102 else if (fofs >= en->ei.fofs + en->ei.len)
103 node = node->rb_right;
104 else
105 return en;
106 }
107 return NULL;
108}
109
110static struct extent_node *__try_back_merge(struct f2fs_sb_info *sbi,
111 struct extent_tree *et, struct extent_node *en)
112{
113 struct extent_node *prev;
114 struct rb_node *node;
115
116 node = rb_prev(&en->rb_node);
117 if (!node)
118 return NULL;
119
120 prev = rb_entry(node, struct extent_node, rb_node);
121 if (__is_back_mergeable(&en->ei, &prev->ei)) {
122 en->ei.fofs = prev->ei.fofs;
123 en->ei.blk = prev->ei.blk;
124 en->ei.len += prev->ei.len;
125 __detach_extent_node(sbi, et, prev);
126 return prev;
127 }
128 return NULL;
129}
130
131static struct extent_node *__try_front_merge(struct f2fs_sb_info *sbi,
132 struct extent_tree *et, struct extent_node *en)
133{
134 struct extent_node *next;
135 struct rb_node *node;
136
137 node = rb_next(&en->rb_node);
138 if (!node)
139 return NULL;
140
141 next = rb_entry(node, struct extent_node, rb_node);
142 if (__is_front_mergeable(&en->ei, &next->ei)) {
143 en->ei.len += next->ei.len;
144 __detach_extent_node(sbi, et, next);
145 return next;
146 }
147 return NULL;
148}
149
150static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
151 struct extent_tree *et, struct extent_info *ei,
152 struct extent_node **den)
153{
154 struct rb_node **p = &et->root.rb_node;
155 struct rb_node *parent = NULL;
156 struct extent_node *en;
157
158 while (*p) {
159 parent = *p;
160 en = rb_entry(parent, struct extent_node, rb_node);
161
162 if (ei->fofs < en->ei.fofs) {
163 if (__is_front_mergeable(ei, &en->ei)) {
164 f2fs_bug_on(sbi, !den);
165 en->ei.fofs = ei->fofs;
166 en->ei.blk = ei->blk;
167 en->ei.len += ei->len;
168 *den = __try_back_merge(sbi, et, en);
169 goto update_out;
170 }
171 p = &(*p)->rb_left;
172 } else if (ei->fofs >= en->ei.fofs + en->ei.len) {
173 if (__is_back_mergeable(ei, &en->ei)) {
174 f2fs_bug_on(sbi, !den);
175 en->ei.len += ei->len;
176 *den = __try_front_merge(sbi, et, en);
177 goto update_out;
178 }
179 p = &(*p)->rb_right;
180 } else {
181 f2fs_bug_on(sbi, 1);
182 }
183 }
184
185 en = __attach_extent_node(sbi, et, ei, parent, p);
186 if (!en)
187 return NULL;
188update_out:
189 if (en->ei.len > et->largest.len)
190 et->largest = en->ei;
191 et->cached_en = en;
192 return en;
193}
194
195static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
196 struct extent_tree *et, bool free_all)
197{
198 struct rb_node *node, *next;
199 struct extent_node *en;
200 unsigned int count = et->count;
201
202 node = rb_first(&et->root);
203 while (node) {
204 next = rb_next(node);
205 en = rb_entry(node, struct extent_node, rb_node);
206
207 if (free_all) {
208 spin_lock(&sbi->extent_lock);
209 if (!list_empty(&en->list))
210 list_del_init(&en->list);
211 spin_unlock(&sbi->extent_lock);
212 }
213
214 if (free_all || list_empty(&en->list)) {
215 __detach_extent_node(sbi, et, en);
216 kmem_cache_free(extent_node_slab, en);
217 }
218 node = next;
219 }
220
221 return count - et->count;
222}
223
224void f2fs_drop_largest_extent(struct inode *inode, pgoff_t fofs)
225{
226 struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest;
227
228 if (largest->fofs <= fofs && largest->fofs + largest->len > fofs)
229 largest->len = 0;
230}
231
232void f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext)
233{
234 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
235 struct extent_tree *et;
236 struct extent_node *en;
237 struct extent_info ei;
238
239 if (!f2fs_may_extent_tree(inode))
240 return;
241
242 et = __grab_extent_tree(inode);
243
244 if (!i_ext || le32_to_cpu(i_ext->len) < F2FS_MIN_EXTENT_LEN)
245 return;
246
247 set_extent_info(&ei, le32_to_cpu(i_ext->fofs),
248 le32_to_cpu(i_ext->blk), le32_to_cpu(i_ext->len));
249
250 write_lock(&et->lock);
251 if (et->count)
252 goto out;
253
254 en = __insert_extent_tree(sbi, et, &ei, NULL);
255 if (en) {
256 spin_lock(&sbi->extent_lock);
257 list_add_tail(&en->list, &sbi->extent_list);
258 spin_unlock(&sbi->extent_lock);
259 }
260out:
261 write_unlock(&et->lock);
262}
263
264static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
265 struct extent_info *ei)
266{
267 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
268 struct extent_tree *et = F2FS_I(inode)->extent_tree;
269 struct extent_node *en;
270 bool ret = false;
271
272 f2fs_bug_on(sbi, !et);
273
274 trace_f2fs_lookup_extent_tree_start(inode, pgofs);
275
276 read_lock(&et->lock);
277
278 if (et->largest.fofs <= pgofs &&
279 et->largest.fofs + et->largest.len > pgofs) {
280 *ei = et->largest;
281 ret = true;
282 stat_inc_read_hit(sbi->sb);
283 goto out;
284 }
285
286 en = __lookup_extent_tree(et, pgofs);
287 if (en) {
288 *ei = en->ei;
289 spin_lock(&sbi->extent_lock);
290 if (!list_empty(&en->list))
291 list_move_tail(&en->list, &sbi->extent_list);
292 et->cached_en = en;
293 spin_unlock(&sbi->extent_lock);
294 ret = true;
295 stat_inc_read_hit(sbi->sb);
296 }
297out:
298 stat_inc_total_hit(sbi->sb);
299 read_unlock(&et->lock);
300
301 trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei);
302 return ret;
303}
304
305/* return true, if on-disk extent should be updated */
306static bool f2fs_update_extent_tree(struct inode *inode, pgoff_t fofs,
307 block_t blkaddr)
308{
309 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
310 struct extent_tree *et = F2FS_I(inode)->extent_tree;
311 struct extent_node *en = NULL, *en1 = NULL, *en2 = NULL, *en3 = NULL;
312 struct extent_node *den = NULL;
313 struct extent_info ei, dei, prev;
314 unsigned int endofs;
315
316 if (!et)
317 return false;
318
319 trace_f2fs_update_extent_tree(inode, fofs, blkaddr);
320
321 write_lock(&et->lock);
322
323 if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) {
324 write_unlock(&et->lock);
325 return false;
326 }
327
328 prev = et->largest;
329 dei.len = 0;
330
331 /* we do not guarantee that the largest extent is cached all the time */
332 f2fs_drop_largest_extent(inode, fofs);
333
334 /* 1. lookup and remove existing extent info in cache */
335 en = __lookup_extent_tree(et, fofs);
336 if (!en)
337 goto update_extent;
338
339 dei = en->ei;
340 __detach_extent_node(sbi, et, en);
341
342 /* 2. if extent can be split more, split and insert the left part */
343 if (dei.len > F2FS_MIN_EXTENT_LEN) {
344 /* insert left part of split extent into cache */
345 if (fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN) {
346 set_extent_info(&ei, dei.fofs, dei.blk,
347 fofs - dei.fofs);
348 en1 = __insert_extent_tree(sbi, et, &ei, NULL);
349 }
350
351 /* insert right part of split extent into cache */
352 endofs = dei.fofs + dei.len - 1;
353 if (endofs - fofs >= F2FS_MIN_EXTENT_LEN) {
354 set_extent_info(&ei, fofs + 1,
355 fofs - dei.fofs + dei.blk + 1, endofs - fofs);
356 en2 = __insert_extent_tree(sbi, et, &ei, NULL);
357 }
358 }
359
360update_extent:
361 /* 3. update extent in extent cache */
362 if (blkaddr) {
363 set_extent_info(&ei, fofs, blkaddr, 1);
364 en3 = __insert_extent_tree(sbi, et, &ei, &den);
365
366 /* give up extent_cache, if split and small updates happen */
367 if (dei.len >= 1 &&
368 prev.len < F2FS_MIN_EXTENT_LEN &&
369 et->largest.len < F2FS_MIN_EXTENT_LEN) {
370 et->largest.len = 0;
371 set_inode_flag(F2FS_I(inode), FI_NO_EXTENT);
372 }
373 }
374
375 /* 4. update in global extent list */
376 spin_lock(&sbi->extent_lock);
377 if (en && !list_empty(&en->list))
378 list_del(&en->list);
379 /*
380 * en1 and en2 split from en, they will become more and more smaller
381 * fragments after splitting several times. So if the length is smaller
382 * than F2FS_MIN_EXTENT_LEN, we will not add them into extent tree.
383 */
384 if (en1)
385 list_add_tail(&en1->list, &sbi->extent_list);
386 if (en2)
387 list_add_tail(&en2->list, &sbi->extent_list);
388 if (en3) {
389 if (list_empty(&en3->list))
390 list_add_tail(&en3->list, &sbi->extent_list);
391 else
392 list_move_tail(&en3->list, &sbi->extent_list);
393 }
394 if (den && !list_empty(&den->list))
395 list_del(&den->list);
396 spin_unlock(&sbi->extent_lock);
397
398 /* 5. release extent node */
399 if (en)
400 kmem_cache_free(extent_node_slab, en);
401 if (den)
402 kmem_cache_free(extent_node_slab, den);
403
404 if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
405 __free_extent_tree(sbi, et, true);
406
407 write_unlock(&et->lock);
408
409 return !__is_extent_same(&prev, &et->largest);
410}
411
412unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
413{
414 struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
415 struct extent_node *en, *tmp;
416 unsigned long ino = F2FS_ROOT_INO(sbi);
417 struct radix_tree_root *root = &sbi->extent_tree_root;
418 unsigned int found;
419 unsigned int node_cnt = 0, tree_cnt = 0;
420 int remained;
421
422 if (!test_opt(sbi, EXTENT_CACHE))
423 return 0;
424
425 if (!down_write_trylock(&sbi->extent_tree_lock))
426 goto out;
427
428 /* 1. remove unreferenced extent tree */
429 while ((found = radix_tree_gang_lookup(root,
430 (void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
431 unsigned i;
432
433 ino = treevec[found - 1]->ino + 1;
434 for (i = 0; i < found; i++) {
435 struct extent_tree *et = treevec[i];
436
437 if (!atomic_read(&et->refcount)) {
438 write_lock(&et->lock);
439 node_cnt += __free_extent_tree(sbi, et, true);
440 write_unlock(&et->lock);
441
442 radix_tree_delete(root, et->ino);
443 kmem_cache_free(extent_tree_slab, et);
444 sbi->total_ext_tree--;
445 tree_cnt++;
446
447 if (node_cnt + tree_cnt >= nr_shrink)
448 goto unlock_out;
449 }
450 }
451 }
452 up_write(&sbi->extent_tree_lock);
453
454 /* 2. remove LRU extent entries */
455 if (!down_write_trylock(&sbi->extent_tree_lock))
456 goto out;
457
458 remained = nr_shrink - (node_cnt + tree_cnt);
459
460 spin_lock(&sbi->extent_lock);
461 list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
462 if (!remained--)
463 break;
464 list_del_init(&en->list);
465 }
466 spin_unlock(&sbi->extent_lock);
467
468 while ((found = radix_tree_gang_lookup(root,
469 (void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
470 unsigned i;
471
472 ino = treevec[found - 1]->ino + 1;
473 for (i = 0; i < found; i++) {
474 struct extent_tree *et = treevec[i];
475
476 write_lock(&et->lock);
477 node_cnt += __free_extent_tree(sbi, et, false);
478 write_unlock(&et->lock);
479
480 if (node_cnt + tree_cnt >= nr_shrink)
481 break;
482 }
483 }
484unlock_out:
485 up_write(&sbi->extent_tree_lock);
486out:
487 trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
488
489 return node_cnt + tree_cnt;
490}
491
492unsigned int f2fs_destroy_extent_node(struct inode *inode)
493{
494 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
495 struct extent_tree *et = F2FS_I(inode)->extent_tree;
496 unsigned int node_cnt = 0;
497
498 if (!et)
499 return 0;
500
501 write_lock(&et->lock);
502 node_cnt = __free_extent_tree(sbi, et, true);
503 write_unlock(&et->lock);
504
505 return node_cnt;
506}
507
508void f2fs_destroy_extent_tree(struct inode *inode)
509{
510 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
511 struct extent_tree *et = F2FS_I(inode)->extent_tree;
512 unsigned int node_cnt = 0;
513
514 if (!et)
515 return;
516
517 if (inode->i_nlink && !is_bad_inode(inode) && et->count) {
518 atomic_dec(&et->refcount);
519 return;
520 }
521
522 /* free all extent info belong to this extent tree */
523 node_cnt = f2fs_destroy_extent_node(inode);
524
525 /* delete extent tree entry in radix tree */
526 down_write(&sbi->extent_tree_lock);
527 atomic_dec(&et->refcount);
528 f2fs_bug_on(sbi, atomic_read(&et->refcount) || et->count);
529 radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
530 kmem_cache_free(extent_tree_slab, et);
531 sbi->total_ext_tree--;
532 up_write(&sbi->extent_tree_lock);
533
534 F2FS_I(inode)->extent_tree = NULL;
535
536 trace_f2fs_destroy_extent_tree(inode, node_cnt);
537}
538
539bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
540 struct extent_info *ei)
541{
542 if (!f2fs_may_extent_tree(inode))
543 return false;
544
545 return f2fs_lookup_extent_tree(inode, pgofs, ei);
546}
547
548void f2fs_update_extent_cache(struct dnode_of_data *dn)
549{
550 struct f2fs_inode_info *fi = F2FS_I(dn->inode);
551 pgoff_t fofs;
552
553 if (!f2fs_may_extent_tree(dn->inode))
554 return;
555
556 f2fs_bug_on(F2FS_I_SB(dn->inode), dn->data_blkaddr == NEW_ADDR);
557
558 fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) +
559 dn->ofs_in_node;
560
561 if (f2fs_update_extent_tree(dn->inode, fofs, dn->data_blkaddr))
562 sync_inode_page(dn);
563}
564
565void init_extent_cache_info(struct f2fs_sb_info *sbi)
566{
567 INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO);
568 init_rwsem(&sbi->extent_tree_lock);
569 INIT_LIST_HEAD(&sbi->extent_list);
570 spin_lock_init(&sbi->extent_lock);
571 sbi->total_ext_tree = 0;
572 atomic_set(&sbi->total_ext_node, 0);
573}
574
575int __init create_extent_cache(void)
576{
577 extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
578 sizeof(struct extent_tree));
579 if (!extent_tree_slab)
580 return -ENOMEM;
581 extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
582 sizeof(struct extent_node));
583 if (!extent_node_slab) {
584 kmem_cache_destroy(extent_tree_slab);
585 return -ENOMEM;
586 }
587 return 0;
588}
589
590void destroy_extent_cache(void)
591{
592 kmem_cache_destroy(extent_node_slab);
593 kmem_cache_destroy(extent_tree_slab);
594}
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 1e6f54d8b464..88b05cba3d4a 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -1766,20 +1766,12 @@ void f2fs_submit_page_mbio(struct f2fs_io_info *);
1766void set_data_blkaddr(struct dnode_of_data *); 1766void set_data_blkaddr(struct dnode_of_data *);
1767int reserve_new_block(struct dnode_of_data *); 1767int reserve_new_block(struct dnode_of_data *);
1768int f2fs_reserve_block(struct dnode_of_data *, pgoff_t); 1768int f2fs_reserve_block(struct dnode_of_data *, pgoff_t);
1769unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *, int);
1770void f2fs_init_extent_tree(struct inode *, struct f2fs_extent *);
1771unsigned int f2fs_destroy_extent_node(struct inode *);
1772void f2fs_destroy_extent_tree(struct inode *);
1773void f2fs_update_extent_cache(struct dnode_of_data *);
1774struct page *get_read_data_page(struct inode *, pgoff_t, int); 1769struct page *get_read_data_page(struct inode *, pgoff_t, int);
1775struct page *find_data_page(struct inode *, pgoff_t); 1770struct page *find_data_page(struct inode *, pgoff_t);
1776struct page *get_lock_data_page(struct inode *, pgoff_t); 1771struct page *get_lock_data_page(struct inode *, pgoff_t);
1777struct page *get_new_data_page(struct inode *, struct page *, pgoff_t, bool); 1772struct page *get_new_data_page(struct inode *, struct page *, pgoff_t, bool);
1778int do_write_data_page(struct f2fs_io_info *); 1773int do_write_data_page(struct f2fs_io_info *);
1779int f2fs_fiemap(struct inode *inode, struct fiemap_extent_info *, u64, u64); 1774int f2fs_fiemap(struct inode *inode, struct fiemap_extent_info *, u64, u64);
1780void init_extent_cache_info(struct f2fs_sb_info *);
1781int __init create_extent_cache(void);
1782void destroy_extent_cache(void);
1783void f2fs_invalidate_page(struct page *, unsigned int, unsigned int); 1775void f2fs_invalidate_page(struct page *, unsigned int, unsigned int);
1784int f2fs_release_page(struct page *, gfp_t); 1776int f2fs_release_page(struct page *, gfp_t);
1785 1777
@@ -1977,6 +1969,20 @@ void f2fs_join_shrinker(struct f2fs_sb_info *);
1977void f2fs_leave_shrinker(struct f2fs_sb_info *); 1969void f2fs_leave_shrinker(struct f2fs_sb_info *);
1978 1970
1979/* 1971/*
1972 * extent_cache.c
1973 */
1974unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *, int);
1975void f2fs_drop_largest_extent(struct inode *, pgoff_t);
1976void f2fs_init_extent_tree(struct inode *, struct f2fs_extent *);
1977unsigned int f2fs_destroy_extent_node(struct inode *);
1978void f2fs_destroy_extent_tree(struct inode *);
1979bool f2fs_lookup_extent_cache(struct inode *, pgoff_t, struct extent_info *);
1980void f2fs_update_extent_cache(struct dnode_of_data *);
1981void init_extent_cache_info(struct f2fs_sb_info *);
1982int __init create_extent_cache(void);
1983void destroy_extent_cache(void);
1984
1985/*
1980 * crypto support 1986 * crypto support
1981 */ 1987 */
1982static inline int f2fs_encrypted_inode(struct inode *inode) 1988static inline int f2fs_encrypted_inode(struct inode *inode)
generated by cgit v1.2.2 (git 2.25.0) at 2025-02-13 20:57:59 -0500