aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs
diff options
context:
space:
mode:
authorChris Mason <chris.mason@oracle.com>2010-07-07 10:51:48 -0400
committerChris Mason <chris.mason@oracle.com>2010-07-19 16:14:50 -0400
commit99d8f83c98930100cd70437b0c81a935e7a14b0b (patch)
treedb4ea3e51c5cc33b903c498368dc7b14e2a07125 /fs/btrfs
parent6f902af400b2499c80865c62a06fbbd15cf804fd (diff)
Btrfs: fix split_leaf double split corner case
split_leaf was not properly balancing leaves when it was forced to split a leaf twice. This commit adds an extra push left and right before forcing the double split in hopes of getting the slot where we want to insert at either the start or end of the leaf. If the extra pushes do work, then we are able to avoid splitting twice and we keep the tree properly balanced. Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs/btrfs')
-rw-r--r--fs/btrfs/ctree.c129
1 files changed, 111 insertions, 18 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 0d1d966b0fe4..c3df14ce2cc2 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -2304,12 +2304,17 @@ noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2304 return ret; 2304 return ret;
2305} 2305}
2306 2306
2307/*
2308 * min slot controls the lowest index we're willing to push to the
2309 * right. We'll push up to and including min_slot, but no lower
2310 */
2307static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, 2311static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
2308 struct btrfs_root *root, 2312 struct btrfs_root *root,
2309 struct btrfs_path *path, 2313 struct btrfs_path *path,
2310 int data_size, int empty, 2314 int data_size, int empty,
2311 struct extent_buffer *right, 2315 struct extent_buffer *right,
2312 int free_space, u32 left_nritems) 2316 int free_space, u32 left_nritems,
2317 u32 min_slot)
2313{ 2318{
2314 struct extent_buffer *left = path->nodes[0]; 2319 struct extent_buffer *left = path->nodes[0];
2315 struct extent_buffer *upper = path->nodes[1]; 2320 struct extent_buffer *upper = path->nodes[1];
@@ -2327,7 +2332,7 @@ static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
2327 if (empty) 2332 if (empty)
2328 nr = 0; 2333 nr = 0;
2329 else 2334 else
2330 nr = 1; 2335 nr = max_t(u32, 1, min_slot);
2331 2336
2332 if (path->slots[0] >= left_nritems) 2337 if (path->slots[0] >= left_nritems)
2333 push_space += data_size; 2338 push_space += data_size;
@@ -2469,10 +2474,14 @@ out_unlock:
2469 * 2474 *
2470 * returns 1 if the push failed because the other node didn't have enough 2475 * returns 1 if the push failed because the other node didn't have enough
2471 * room, 0 if everything worked out and < 0 if there were major errors. 2476 * room, 0 if everything worked out and < 0 if there were major errors.
2477 *
2478 * this will push starting from min_slot to the end of the leaf. It won't
2479 * push any slot lower than min_slot
2472 */ 2480 */
2473static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 2481static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2474 *root, struct btrfs_path *path, int data_size, 2482 *root, struct btrfs_path *path,
2475 int empty) 2483 int min_data_size, int data_size,
2484 int empty, u32 min_slot)
2476{ 2485{
2477 struct extent_buffer *left = path->nodes[0]; 2486 struct extent_buffer *left = path->nodes[0];
2478 struct extent_buffer *right; 2487 struct extent_buffer *right;
@@ -2514,8 +2523,8 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2514 if (left_nritems == 0) 2523 if (left_nritems == 0)
2515 goto out_unlock; 2524 goto out_unlock;
2516 2525
2517 return __push_leaf_right(trans, root, path, data_size, empty, 2526 return __push_leaf_right(trans, root, path, min_data_size, empty,
2518 right, free_space, left_nritems); 2527 right, free_space, left_nritems, min_slot);
2519out_unlock: 2528out_unlock:
2520 btrfs_tree_unlock(right); 2529 btrfs_tree_unlock(right);
2521 free_extent_buffer(right); 2530 free_extent_buffer(right);
@@ -2525,12 +2534,17 @@ out_unlock:
2525/* 2534/*
2526 * push some data in the path leaf to the left, trying to free up at 2535 * push some data in the path leaf to the left, trying to free up at
2527 * least data_size bytes. returns zero if the push worked, nonzero otherwise 2536 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2537 *
2538 * max_slot can put a limit on how far into the leaf we'll push items. The
2539 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
2540 * items
2528 */ 2541 */
2529static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, 2542static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
2530 struct btrfs_root *root, 2543 struct btrfs_root *root,
2531 struct btrfs_path *path, int data_size, 2544 struct btrfs_path *path, int data_size,
2532 int empty, struct extent_buffer *left, 2545 int empty, struct extent_buffer *left,
2533 int free_space, int right_nritems) 2546 int free_space, u32 right_nritems,
2547 u32 max_slot)
2534{ 2548{
2535 struct btrfs_disk_key disk_key; 2549 struct btrfs_disk_key disk_key;
2536 struct extent_buffer *right = path->nodes[0]; 2550 struct extent_buffer *right = path->nodes[0];
@@ -2549,9 +2563,9 @@ static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
2549 slot = path->slots[1]; 2563 slot = path->slots[1];
2550 2564
2551 if (empty) 2565 if (empty)
2552 nr = right_nritems; 2566 nr = min(right_nritems, max_slot);
2553 else 2567 else
2554 nr = right_nritems - 1; 2568 nr = min(right_nritems - 1, max_slot);
2555 2569
2556 for (i = 0; i < nr; i++) { 2570 for (i = 0; i < nr; i++) {
2557 item = btrfs_item_nr(right, i); 2571 item = btrfs_item_nr(right, i);
@@ -2712,10 +2726,14 @@ out:
2712/* 2726/*
2713 * push some data in the path leaf to the left, trying to free up at 2727 * push some data in the path leaf to the left, trying to free up at
2714 * least data_size bytes. returns zero if the push worked, nonzero otherwise 2728 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2729 *
2730 * max_slot can put a limit on how far into the leaf we'll push items. The
2731 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
2732 * items
2715 */ 2733 */
2716static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 2734static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2717 *root, struct btrfs_path *path, int data_size, 2735 *root, struct btrfs_path *path, int min_data_size,
2718 int empty) 2736 int data_size, int empty, u32 max_slot)
2719{ 2737{
2720 struct extent_buffer *right = path->nodes[0]; 2738 struct extent_buffer *right = path->nodes[0];
2721 struct extent_buffer *left; 2739 struct extent_buffer *left;
@@ -2761,8 +2779,9 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2761 goto out; 2779 goto out;
2762 } 2780 }
2763 2781
2764 return __push_leaf_left(trans, root, path, data_size, 2782 return __push_leaf_left(trans, root, path, min_data_size,
2765 empty, left, free_space, right_nritems); 2783 empty, left, free_space, right_nritems,
2784 max_slot);
2766out: 2785out:
2767 btrfs_tree_unlock(left); 2786 btrfs_tree_unlock(left);
2768 free_extent_buffer(left); 2787 free_extent_buffer(left);
@@ -2855,6 +2874,64 @@ static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2855} 2874}
2856 2875
2857/* 2876/*
2877 * double splits happen when we need to insert a big item in the middle
2878 * of a leaf. A double split can leave us with 3 mostly empty leaves:
2879 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
2880 * A B C
2881 *
2882 * We avoid this by trying to push the items on either side of our target
2883 * into the adjacent leaves. If all goes well we can avoid the double split
2884 * completely.
2885 */
2886static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
2887 struct btrfs_root *root,
2888 struct btrfs_path *path,
2889 int data_size)
2890{
2891 int ret;
2892 int progress = 0;
2893 int slot;
2894 u32 nritems;
2895
2896 slot = path->slots[0];
2897
2898 /*
2899 * try to push all the items after our slot into the
2900 * right leaf
2901 */
2902 ret = push_leaf_right(trans, root, path, 1, data_size, 0, slot);
2903 if (ret < 0)
2904 return ret;
2905
2906 if (ret == 0)
2907 progress++;
2908
2909 nritems = btrfs_header_nritems(path->nodes[0]);
2910 /*
2911 * our goal is to get our slot at the start or end of a leaf. If
2912 * we've done so we're done
2913 */
2914 if (path->slots[0] == 0 || path->slots[0] == nritems)
2915 return 0;
2916
2917 if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
2918 return 0;
2919
2920 /* try to push all the items before our slot into the next leaf */
2921 slot = path->slots[0];
2922 ret = push_leaf_left(trans, root, path, 1, data_size, 0, slot);
2923 if (ret < 0)
2924 return ret;
2925
2926 if (ret == 0)
2927 progress++;
2928
2929 if (progress)
2930 return 0;
2931 return 1;
2932}
2933
2934/*
2858 * split the path's leaf in two, making sure there is at least data_size 2935 * split the path's leaf in two, making sure there is at least data_size
2859 * available for the resulting leaf level of the path. 2936 * available for the resulting leaf level of the path.
2860 * 2937 *
@@ -2876,6 +2953,7 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
2876 int wret; 2953 int wret;
2877 int split; 2954 int split;
2878 int num_doubles = 0; 2955 int num_doubles = 0;
2956 int tried_avoid_double = 0;
2879 2957
2880 l = path->nodes[0]; 2958 l = path->nodes[0];
2881 slot = path->slots[0]; 2959 slot = path->slots[0];
@@ -2884,12 +2962,14 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
2884 return -EOVERFLOW; 2962 return -EOVERFLOW;
2885 2963
2886 /* first try to make some room by pushing left and right */ 2964 /* first try to make some room by pushing left and right */
2887 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) { 2965 if (data_size) {
2888 wret = push_leaf_right(trans, root, path, data_size, 0); 2966 wret = push_leaf_right(trans, root, path, data_size,
2967 data_size, 0, 0);
2889 if (wret < 0) 2968 if (wret < 0)
2890 return wret; 2969 return wret;
2891 if (wret) { 2970 if (wret) {
2892 wret = push_leaf_left(trans, root, path, data_size, 0); 2971 wret = push_leaf_left(trans, root, path, data_size,
2972 data_size, 0, (u32)-1);
2893 if (wret < 0) 2973 if (wret < 0)
2894 return wret; 2974 return wret;
2895 } 2975 }
@@ -2923,6 +3003,8 @@ again:
2923 if (mid != nritems && 3003 if (mid != nritems &&
2924 leaf_space_used(l, mid, nritems - mid) + 3004 leaf_space_used(l, mid, nritems - mid) +
2925 data_size > BTRFS_LEAF_DATA_SIZE(root)) { 3005 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
3006 if (data_size && !tried_avoid_double)
3007 goto push_for_double;
2926 split = 2; 3008 split = 2;
2927 } 3009 }
2928 } 3010 }
@@ -2939,6 +3021,8 @@ again:
2939 if (mid != nritems && 3021 if (mid != nritems &&
2940 leaf_space_used(l, mid, nritems - mid) + 3022 leaf_space_used(l, mid, nritems - mid) +
2941 data_size > BTRFS_LEAF_DATA_SIZE(root)) { 3023 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
3024 if (data_size && !tried_avoid_double)
3025 goto push_for_double;
2942 split = 2 ; 3026 split = 2 ;
2943 } 3027 }
2944 } 3028 }
@@ -3019,6 +3103,13 @@ again:
3019 } 3103 }
3020 3104
3021 return ret; 3105 return ret;
3106
3107push_for_double:
3108 push_for_double_split(trans, root, path, data_size);
3109 tried_avoid_double = 1;
3110 if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
3111 return 0;
3112 goto again;
3022} 3113}
3023 3114
3024static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3115static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
@@ -3915,13 +4006,15 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3915 extent_buffer_get(leaf); 4006 extent_buffer_get(leaf);
3916 4007
3917 btrfs_set_path_blocking(path); 4008 btrfs_set_path_blocking(path);
3918 wret = push_leaf_left(trans, root, path, 1, 1); 4009 wret = push_leaf_left(trans, root, path, 1, 1,
4010 1, (u32)-1);
3919 if (wret < 0 && wret != -ENOSPC) 4011 if (wret < 0 && wret != -ENOSPC)
3920 ret = wret; 4012 ret = wret;
3921 4013
3922 if (path->nodes[0] == leaf && 4014 if (path->nodes[0] == leaf &&
3923 btrfs_header_nritems(leaf)) { 4015 btrfs_header_nritems(leaf)) {
3924 wret = push_leaf_right(trans, root, path, 1, 1); 4016 wret = push_leaf_right(trans, root, path, 1,
4017 1, 1, 0);
3925 if (wret < 0 && wret != -ENOSPC) 4018 if (wret < 0 && wret != -ENOSPC)
3926 ret = wret; 4019 ret = wret;
3927 } 4020 }