aboutsummaryrefslogtreecommitdiffstats
path: root/fs
diff options
context:
space:
mode:
authorChris Mason <chris.mason@oracle.com>2008-01-29 15:11:36 -0500
committerChris Mason <chris.mason@oracle.com>2008-09-25 11:04:00 -0400
commit85e21bac165b4ba1f6f90431ad6fc658ffcbaf3a (patch)
tree6483417c9e5c4f3434fd9f2e7e117a4dc46b94c6 /fs
parent70dec8079d78691e476cc6c7cede40656078ad30 (diff)
Btrfs: During deletes and truncate, remove many items at once from the tree
Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs')
-rw-r--r--fs/btrfs/ctree.c38
-rw-r--r--fs/btrfs/ctree.h12
-rw-r--r--fs/btrfs/extent_io.c1
-rw-r--r--fs/btrfs/inode.c114
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 */
2517int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2517int 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);
1038struct btrfs_path *btrfs_alloc_path(void); 1038struct btrfs_path *btrfs_alloc_path(void);
1039void btrfs_free_path(struct btrfs_path *p); 1039void btrfs_free_path(struct btrfs_path *p);
1040void btrfs_init_path(struct btrfs_path *p); 1040void btrfs_init_path(struct btrfs_path *p);
1041int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1041int 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
1044static 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
1043int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 1051int 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);
1045int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1053int 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
695static 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 */
724static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, 703static 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);
737search_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 }
861delete: 845delete:
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 }
870next:
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;
882del_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;
880error: 895error:
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