diff options
author | Chris Mason <chris.mason@oracle.com> | 2010-07-07 10:51:48 -0400 |
---|---|---|
committer | Chris Mason <chris.mason@oracle.com> | 2010-07-19 16:14:50 -0400 |
commit | 99d8f83c98930100cd70437b0c81a935e7a14b0b (patch) | |
tree | db4ea3e51c5cc33b903c498368dc7b14e2a07125 /fs/btrfs | |
parent | 6f902af400b2499c80865c62a06fbbd15cf804fd (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.c | 129 |
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 | */ | ||
2307 | static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, | 2311 | static 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 | */ |
2473 | static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root | 2481 | static 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); |
2519 | out_unlock: | 2528 | out_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 | */ |
2529 | static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, | 2542 | static 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 | */ |
2716 | static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root | 2734 | static 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); | ||
2766 | out: | 2785 | out: |
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 | */ | ||
2886 | static 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 | |||
3107 | push_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 | ||
3024 | static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, | 3115 | static 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 | } |