diff options
author | Chris Mason <chris.mason@oracle.com> | 2008-01-29 15:11:36 -0500 |
---|---|---|
committer | Chris Mason <chris.mason@oracle.com> | 2008-09-25 11:04:00 -0400 |
commit | 85e21bac165b4ba1f6f90431ad6fc658ffcbaf3a (patch) | |
tree | 6483417c9e5c4f3434fd9f2e7e117a4dc46b94c6 | |
parent | 70dec8079d78691e476cc6c7cede40656078ad30 (diff) |
Btrfs: During deletes and truncate, remove many items at once from the tree
Signed-off-by: Chris Mason <chris.mason@oracle.com>
-rw-r--r-- | fs/btrfs/ctree.c | 38 | ||||
-rw-r--r-- | fs/btrfs/ctree.h | 12 | ||||
-rw-r--r-- | fs/btrfs/extent_io.c | 1 | ||||
-rw-r--r-- | fs/btrfs/inode.c | 114 |
4 files changed, 95 insertions, 70 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 43d23148a4fe..84ad53e06b3a 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c | |||
@@ -2514,34 +2514,36 @@ static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, | |||
2514 | * delete the item at the leaf level in path. If that empties | 2514 | * delete the item at the leaf level in path. If that empties |
2515 | * the leaf, remove it from the tree | 2515 | * the leaf, remove it from the tree |
2516 | */ | 2516 | */ |
2517 | int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, | 2517 | int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, |
2518 | struct btrfs_path *path) | 2518 | struct btrfs_path *path, int slot, int nr) |
2519 | { | 2519 | { |
2520 | int slot; | ||
2521 | struct extent_buffer *leaf; | 2520 | struct extent_buffer *leaf; |
2522 | struct btrfs_item *item; | 2521 | struct btrfs_item *item; |
2523 | int doff; | 2522 | int last_off; |
2524 | int dsize; | 2523 | int dsize = 0; |
2525 | int ret = 0; | 2524 | int ret = 0; |
2526 | int wret; | 2525 | int wret; |
2526 | int i; | ||
2527 | u32 nritems; | 2527 | u32 nritems; |
2528 | 2528 | ||
2529 | leaf = path->nodes[0]; | 2529 | leaf = path->nodes[0]; |
2530 | slot = path->slots[0]; | 2530 | last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); |
2531 | doff = btrfs_item_offset_nr(leaf, slot); | 2531 | |
2532 | dsize = btrfs_item_size_nr(leaf, slot); | 2532 | for (i = 0; i < nr; i++) |
2533 | dsize += btrfs_item_size_nr(leaf, slot + i); | ||
2534 | |||
2533 | nritems = btrfs_header_nritems(leaf); | 2535 | nritems = btrfs_header_nritems(leaf); |
2534 | 2536 | ||
2535 | if (slot != nritems - 1) { | 2537 | if (slot + nr != nritems) { |
2536 | int i; | 2538 | int i; |
2537 | int data_end = leaf_data_end(root, leaf); | 2539 | int data_end = leaf_data_end(root, leaf); |
2538 | 2540 | ||
2539 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + | 2541 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + |
2540 | data_end + dsize, | 2542 | data_end + dsize, |
2541 | btrfs_leaf_data(leaf) + data_end, | 2543 | btrfs_leaf_data(leaf) + data_end, |
2542 | doff - data_end); | 2544 | last_off - data_end); |
2543 | 2545 | ||
2544 | for (i = slot + 1; i < nritems; i++) { | 2546 | for (i = slot + nr; i < nritems; i++) { |
2545 | u32 ioff; | 2547 | u32 ioff; |
2546 | 2548 | ||
2547 | item = btrfs_item_nr(leaf, i); | 2549 | item = btrfs_item_nr(leaf, i); |
@@ -2562,12 +2564,12 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, | |||
2562 | } | 2564 | } |
2563 | 2565 | ||
2564 | memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), | 2566 | memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), |
2565 | btrfs_item_nr_offset(slot + 1), | 2567 | btrfs_item_nr_offset(slot + nr), |
2566 | sizeof(struct btrfs_item) * | 2568 | sizeof(struct btrfs_item) * |
2567 | (nritems - slot - 1)); | 2569 | (nritems - slot - nr)); |
2568 | } | 2570 | } |
2569 | btrfs_set_header_nritems(leaf, nritems - 1); | 2571 | btrfs_set_header_nritems(leaf, nritems - nr); |
2570 | nritems--; | 2572 | nritems -= nr; |
2571 | 2573 | ||
2572 | /* delete the leaf if we've emptied it */ | 2574 | /* delete the leaf if we've emptied it */ |
2573 | if (nritems == 0) { | 2575 | if (nritems == 0) { |
@@ -2600,7 +2602,7 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, | |||
2600 | } | 2602 | } |
2601 | 2603 | ||
2602 | /* delete the leaf if it is mostly empty */ | 2604 | /* delete the leaf if it is mostly empty */ |
2603 | if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { | 2605 | if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) { |
2604 | /* push_leaf_left fixes the path. | 2606 | /* push_leaf_left fixes the path. |
2605 | * make sure the path still points to our leaf | 2607 | * make sure the path still points to our leaf |
2606 | * for possible call to del_ptr below | 2608 | * for possible call to del_ptr below |
@@ -2608,13 +2610,13 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, | |||
2608 | slot = path->slots[1]; | 2610 | slot = path->slots[1]; |
2609 | extent_buffer_get(leaf); | 2611 | extent_buffer_get(leaf); |
2610 | 2612 | ||
2611 | wret = push_leaf_right(trans, root, path, 1, 1); | 2613 | wret = push_leaf_left(trans, root, path, 1, 1); |
2612 | if (wret < 0 && wret != -ENOSPC) | 2614 | if (wret < 0 && wret != -ENOSPC) |
2613 | ret = wret; | 2615 | ret = wret; |
2614 | 2616 | ||
2615 | if (path->nodes[0] == leaf && | 2617 | if (path->nodes[0] == leaf && |
2616 | btrfs_header_nritems(leaf)) { | 2618 | btrfs_header_nritems(leaf)) { |
2617 | wret = push_leaf_left(trans, root, path, 1, 1); | 2619 | wret = push_leaf_right(trans, root, path, 1, 1); |
2618 | if (wret < 0 && wret != -ENOSPC) | 2620 | if (wret < 0 && wret != -ENOSPC) |
2619 | ret = wret; | 2621 | ret = wret; |
2620 | } | 2622 | } |
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 6c65473e0fe3..098cf0883150 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h | |||
@@ -1038,8 +1038,16 @@ void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p); | |||
1038 | struct btrfs_path *btrfs_alloc_path(void); | 1038 | struct btrfs_path *btrfs_alloc_path(void); |
1039 | void btrfs_free_path(struct btrfs_path *p); | 1039 | void btrfs_free_path(struct btrfs_path *p); |
1040 | void btrfs_init_path(struct btrfs_path *p); | 1040 | void btrfs_init_path(struct btrfs_path *p); |
1041 | int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, | 1041 | int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, |
1042 | struct btrfs_path *path); | 1042 | struct btrfs_path *path, int slot, int nr); |
1043 | |||
1044 | static inline int btrfs_del_item(struct btrfs_trans_handle *trans, | ||
1045 | struct btrfs_root *root, | ||
1046 | struct btrfs_path *path) | ||
1047 | { | ||
1048 | return btrfs_del_items(trans, root, path, path->slots[0], 1); | ||
1049 | } | ||
1050 | |||
1043 | int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root | 1051 | int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root |
1044 | *root, struct btrfs_key *key, void *data, u32 data_size); | 1052 | *root, struct btrfs_key *key, void *data, u32 data_size); |
1045 | int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root | 1053 | int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root |
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c index 1f734c34dc24..8aec72253a17 100644 --- a/fs/btrfs/extent_io.c +++ b/fs/btrfs/extent_io.c | |||
@@ -2863,7 +2863,6 @@ int read_extent_buffer_pages(struct extent_io_tree *tree, | |||
2863 | if (ret || !wait) { | 2863 | if (ret || !wait) { |
2864 | return ret; | 2864 | return ret; |
2865 | } | 2865 | } |
2866 | |||
2867 | for (i = start_i; i < num_pages; i++) { | 2866 | for (i = start_i; i < num_pages; i++) { |
2868 | page = extent_buffer_page(eb, i); | 2867 | page = extent_buffer_page(eb, i); |
2869 | wait_on_page_locked(page); | 2868 | wait_on_page_locked(page); |
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index bac8722e14e1..0a2fe51c4127 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c | |||
@@ -692,27 +692,6 @@ fail: | |||
692 | return err; | 692 | return err; |
693 | } | 693 | } |
694 | 694 | ||
695 | static int btrfs_free_inode(struct btrfs_trans_handle *trans, | ||
696 | struct btrfs_root *root, | ||
697 | struct inode *inode) | ||
698 | { | ||
699 | struct btrfs_path *path; | ||
700 | int ret; | ||
701 | |||
702 | clear_inode(inode); | ||
703 | |||
704 | path = btrfs_alloc_path(); | ||
705 | BUG_ON(!path); | ||
706 | ret = btrfs_lookup_inode(trans, root, path, | ||
707 | &BTRFS_I(inode)->location, -1); | ||
708 | if (ret > 0) | ||
709 | ret = -ENOENT; | ||
710 | if (!ret) | ||
711 | ret = btrfs_del_item(trans, root, path); | ||
712 | btrfs_free_path(path); | ||
713 | return ret; | ||
714 | } | ||
715 | |||
716 | /* | 695 | /* |
717 | * this can truncate away extent items, csum items and directory items. | 696 | * this can truncate away extent items, csum items and directory items. |
718 | * It starts at a high offset and removes keys until it can't find | 697 | * It starts at a high offset and removes keys until it can't find |
@@ -723,7 +702,8 @@ static int btrfs_free_inode(struct btrfs_trans_handle *trans, | |||
723 | */ | 702 | */ |
724 | static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, | 703 | static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, |
725 | struct btrfs_root *root, | 704 | struct btrfs_root *root, |
726 | struct inode *inode) | 705 | struct inode *inode, |
706 | u32 min_type) | ||
727 | { | 707 | { |
728 | int ret; | 708 | int ret; |
729 | struct btrfs_path *path; | 709 | struct btrfs_path *path; |
@@ -739,6 +719,8 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, | |||
739 | u64 root_owner = 0; | 719 | u64 root_owner = 0; |
740 | int found_extent; | 720 | int found_extent; |
741 | int del_item; | 721 | int del_item; |
722 | int pending_del_nr = 0; | ||
723 | int pending_del_slot = 0; | ||
742 | int extent_type = -1; | 724 | int extent_type = -1; |
743 | 725 | ||
744 | btrfs_drop_extent_cache(inode, inode->i_size, (u64)-1); | 726 | btrfs_drop_extent_cache(inode, inode->i_size, (u64)-1); |
@@ -751,17 +733,19 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, | |||
751 | key.offset = (u64)-1; | 733 | key.offset = (u64)-1; |
752 | key.type = (u8)-1; | 734 | key.type = (u8)-1; |
753 | 735 | ||
736 | btrfs_init_path(path); | ||
737 | search_again: | ||
738 | ret = btrfs_search_slot(trans, root, &key, path, -1, 1); | ||
739 | if (ret < 0) { | ||
740 | goto error; | ||
741 | } | ||
742 | if (ret > 0) { | ||
743 | BUG_ON(path->slots[0] == 0); | ||
744 | path->slots[0]--; | ||
745 | } | ||
746 | |||
754 | while(1) { | 747 | while(1) { |
755 | btrfs_init_path(path); | ||
756 | fi = NULL; | 748 | fi = NULL; |
757 | ret = btrfs_search_slot(trans, root, &key, path, -1, 1); | ||
758 | if (ret < 0) { | ||
759 | goto error; | ||
760 | } | ||
761 | if (ret > 0) { | ||
762 | BUG_ON(path->slots[0] == 0); | ||
763 | path->slots[0]--; | ||
764 | } | ||
765 | leaf = path->nodes[0]; | 749 | leaf = path->nodes[0]; |
766 | btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); | 750 | btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); |
767 | found_type = btrfs_key_type(&found_key); | 751 | found_type = btrfs_key_type(&found_key); |
@@ -769,10 +753,7 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, | |||
769 | if (found_key.objectid != inode->i_ino) | 753 | if (found_key.objectid != inode->i_ino) |
770 | break; | 754 | break; |
771 | 755 | ||
772 | if (found_type != BTRFS_CSUM_ITEM_KEY && | 756 | if (found_type < min_type) |
773 | found_type != BTRFS_DIR_ITEM_KEY && | ||
774 | found_type != BTRFS_DIR_INDEX_KEY && | ||
775 | found_type != BTRFS_EXTENT_DATA_KEY) | ||
776 | break; | 757 | break; |
777 | 758 | ||
778 | item_end = found_key.offset; | 759 | item_end = found_key.offset; |
@@ -801,14 +782,17 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, | |||
801 | found_type = BTRFS_INODE_ITEM_KEY; | 782 | found_type = BTRFS_INODE_ITEM_KEY; |
802 | } else if (found_type == BTRFS_EXTENT_ITEM_KEY) { | 783 | } else if (found_type == BTRFS_EXTENT_ITEM_KEY) { |
803 | found_type = BTRFS_CSUM_ITEM_KEY; | 784 | found_type = BTRFS_CSUM_ITEM_KEY; |
785 | } else if (found_type == BTRFS_EXTENT_DATA_KEY) { | ||
786 | found_type = BTRFS_XATTR_ITEM_KEY; | ||
787 | } else if (found_type == BTRFS_XATTR_ITEM_KEY) { | ||
788 | found_type = BTRFS_INODE_REF_KEY; | ||
804 | } else if (found_type) { | 789 | } else if (found_type) { |
805 | found_type--; | 790 | found_type--; |
806 | } else { | 791 | } else { |
807 | break; | 792 | break; |
808 | } | 793 | } |
809 | btrfs_set_key_type(&key, found_type); | 794 | btrfs_set_key_type(&key, found_type); |
810 | btrfs_release_path(root, path); | 795 | goto next; |
811 | continue; | ||
812 | } | 796 | } |
813 | if (found_key.offset >= inode->i_size) | 797 | if (found_key.offset >= inode->i_size) |
814 | del_item = 1; | 798 | del_item = 1; |
@@ -860,13 +844,21 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, | |||
860 | } | 844 | } |
861 | delete: | 845 | delete: |
862 | if (del_item) { | 846 | if (del_item) { |
863 | ret = btrfs_del_item(trans, root, path); | 847 | if (!pending_del_nr) { |
864 | if (ret) | 848 | /* no pending yet, add ourselves */ |
865 | goto error; | 849 | pending_del_slot = path->slots[0]; |
850 | pending_del_nr = 1; | ||
851 | } else if (pending_del_nr && | ||
852 | path->slots[0] + 1 == pending_del_slot) { | ||
853 | /* hop on the pending chunk */ | ||
854 | pending_del_nr++; | ||
855 | pending_del_slot = path->slots[0]; | ||
856 | } else { | ||
857 | printk("bad pending slot %d pending_del_nr %d pending_del_slot %d\n", path->slots[0], pending_del_nr, pending_del_slot); | ||
858 | } | ||
866 | } else { | 859 | } else { |
867 | break; | 860 | break; |
868 | } | 861 | } |
869 | btrfs_release_path(root, path); | ||
870 | if (found_extent) { | 862 | if (found_extent) { |
871 | ret = btrfs_free_extent(trans, root, extent_start, | 863 | ret = btrfs_free_extent(trans, root, extent_start, |
872 | extent_num_bytes, | 864 | extent_num_bytes, |
@@ -875,9 +867,36 @@ delete: | |||
875 | found_key.offset, 0); | 867 | found_key.offset, 0); |
876 | BUG_ON(ret); | 868 | BUG_ON(ret); |
877 | } | 869 | } |
870 | next: | ||
871 | if (path->slots[0] == 0) { | ||
872 | if (pending_del_nr) | ||
873 | goto del_pending; | ||
874 | btrfs_release_path(root, path); | ||
875 | goto search_again; | ||
876 | } | ||
877 | |||
878 | path->slots[0]--; | ||
879 | if (pending_del_nr && | ||
880 | path->slots[0] + 1 != pending_del_slot) { | ||
881 | struct btrfs_key debug; | ||
882 | del_pending: | ||
883 | btrfs_item_key_to_cpu(path->nodes[0], &debug, | ||
884 | pending_del_slot); | ||
885 | ret = btrfs_del_items(trans, root, path, | ||
886 | pending_del_slot, | ||
887 | pending_del_nr); | ||
888 | BUG_ON(ret); | ||
889 | pending_del_nr = 0; | ||
890 | btrfs_release_path(root, path); | ||
891 | goto search_again; | ||
892 | } | ||
878 | } | 893 | } |
879 | ret = 0; | 894 | ret = 0; |
880 | error: | 895 | error: |
896 | if (pending_del_nr) { | ||
897 | ret = btrfs_del_items(trans, root, path, pending_del_slot, | ||
898 | pending_del_nr); | ||
899 | } | ||
881 | btrfs_release_path(root, path); | 900 | btrfs_release_path(root, path); |
882 | btrfs_free_path(path); | 901 | btrfs_free_path(path); |
883 | inode->i_sb->s_dirt = 1; | 902 | inode->i_sb->s_dirt = 1; |
@@ -1067,16 +1086,12 @@ void btrfs_delete_inode(struct inode *inode) | |||
1067 | trans = btrfs_start_transaction(root, 1); | 1086 | trans = btrfs_start_transaction(root, 1); |
1068 | 1087 | ||
1069 | btrfs_set_trans_block_group(trans, inode); | 1088 | btrfs_set_trans_block_group(trans, inode); |
1070 | ret = btrfs_truncate_in_trans(trans, root, inode); | 1089 | ret = btrfs_truncate_in_trans(trans, root, inode, 0); |
1071 | if (ret) | ||
1072 | goto no_delete_lock; | ||
1073 | ret = btrfs_delete_xattrs(trans, root, inode); | ||
1074 | if (ret) | ||
1075 | goto no_delete_lock; | ||
1076 | ret = btrfs_free_inode(trans, root, inode); | ||
1077 | if (ret) | 1090 | if (ret) |
1078 | goto no_delete_lock; | 1091 | goto no_delete_lock; |
1092 | |||
1079 | nr = trans->blocks_used; | 1093 | nr = trans->blocks_used; |
1094 | clear_inode(inode); | ||
1080 | 1095 | ||
1081 | btrfs_end_transaction(trans, root); | 1096 | btrfs_end_transaction(trans, root); |
1082 | mutex_unlock(&root->fs_info->fs_mutex); | 1097 | mutex_unlock(&root->fs_info->fs_mutex); |
@@ -2190,7 +2205,8 @@ static void btrfs_truncate(struct inode *inode) | |||
2190 | btrfs_set_trans_block_group(trans, inode); | 2205 | btrfs_set_trans_block_group(trans, inode); |
2191 | 2206 | ||
2192 | /* FIXME, add redo link to tree so we don't leak on crash */ | 2207 | /* FIXME, add redo link to tree so we don't leak on crash */ |
2193 | ret = btrfs_truncate_in_trans(trans, root, inode); | 2208 | ret = btrfs_truncate_in_trans(trans, root, inode, |
2209 | BTRFS_EXTENT_DATA_KEY); | ||
2194 | btrfs_update_inode(trans, root, inode); | 2210 | btrfs_update_inode(trans, root, inode); |
2195 | nr = trans->blocks_used; | 2211 | nr = trans->blocks_used; |
2196 | 2212 | ||