summaryrefslogtreecommitdiffstats
path: root/fs/f2fs/data.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/f2fs/data.c')
-rw-r--r--fs/f2fs/data.c578
1 files changed, 1 insertions, 577 deletions
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,
generated by cgit v1.2.2 (git 2.25.0) at 2025-02-18 22:39:35 -0500