ctree.c (1ac731c529cd4d6adbce134754b51ff7d822b145) ctree.c (48774f3bf8b4dd3b1a0e155825c9ce48483db14c)
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2007,2008 Oracle. All rights reserved.
4 */
5
6#include <linux/sched.h>
7#include <linux/slab.h>
8#include <linux/rbtree.h>

--- 23 unchanged lines hidden (view full) ---

32 const struct btrfs_key *ins_key, struct btrfs_path *path,
33 int data_size, int extend);
34static int push_node_left(struct btrfs_trans_handle *trans,
35 struct extent_buffer *dst,
36 struct extent_buffer *src, int empty);
37static int balance_node_right(struct btrfs_trans_handle *trans,
38 struct extent_buffer *dst_buf,
39 struct extent_buffer *src_buf);
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2007,2008 Oracle. All rights reserved.
4 */
5
6#include <linux/sched.h>
7#include <linux/slab.h>
8#include <linux/rbtree.h>

--- 23 unchanged lines hidden (view full) ---

32 const struct btrfs_key *ins_key, struct btrfs_path *path,
33 int data_size, int extend);
34static int push_node_left(struct btrfs_trans_handle *trans,
35 struct extent_buffer *dst,
36 struct extent_buffer *src, int empty);
37static int balance_node_right(struct btrfs_trans_handle *trans,
38 struct extent_buffer *dst_buf,
39 struct extent_buffer *src_buf);
40static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
41 int level, int slot);
42
43static const struct btrfs_csums {
44 u16 size;
45 const char name[10];
46 const char driver[12];
47} btrfs_csums[] = {
48 [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" },
49 [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" },

--- 95 unchanged lines hidden (view full) ---

145 const struct extent_buffer *src,
146 int dst_item, int src_item, int nr_items)
147{
148 copy_extent_buffer(dst, src, btrfs_item_nr_offset(dst, dst_item),
149 btrfs_item_nr_offset(src, src_item),
150 nr_items * sizeof(struct btrfs_item));
151}
152
40
41static const struct btrfs_csums {
42 u16 size;
43 const char name[10];
44 const char driver[12];
45} btrfs_csums[] = {
46 [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" },
47 [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" },

--- 95 unchanged lines hidden (view full) ---

143 const struct extent_buffer *src,
144 int dst_item, int src_item, int nr_items)
145{
146 copy_extent_buffer(dst, src, btrfs_item_nr_offset(dst, dst_item),
147 btrfs_item_nr_offset(src, src_item),
148 nr_items * sizeof(struct btrfs_item));
149}
150
151/* This exists for btrfs-progs usages. */
152u16 btrfs_csum_type_size(u16 type)
153{
154 return btrfs_csums[type].size;
155}
156
153int btrfs_super_csum_size(const struct btrfs_super_block *s)
154{
155 u16 t = btrfs_super_csum_type(s);
156 /*
157 * csum type is validated at mount time
158 */
157int btrfs_super_csum_size(const struct btrfs_super_block *s)
158{
159 u16 t = btrfs_super_csum_type(s);
160 /*
161 * csum type is validated at mount time
162 */
159 return btrfs_csums[t].size;
163 return btrfs_csum_type_size(t);
160}
161
162const char *btrfs_super_csum_name(u16 csum_type)
163{
164 /* csum type is validated at mount time */
165 return btrfs_csums[csum_type].name;
166}
167

--- 244 unchanged lines hidden (view full) ---

412 */
413
414 if (btrfs_block_can_be_shared(root, buf)) {
415 ret = btrfs_lookup_extent_info(trans, fs_info, buf->start,
416 btrfs_header_level(buf), 1,
417 &refs, &flags);
418 if (ret)
419 return ret;
164}
165
166const char *btrfs_super_csum_name(u16 csum_type)
167{
168 /* csum type is validated at mount time */
169 return btrfs_csums[csum_type].name;
170}
171

--- 244 unchanged lines hidden (view full) ---

416 */
417
418 if (btrfs_block_can_be_shared(root, buf)) {
419 ret = btrfs_lookup_extent_info(trans, fs_info, buf->start,
420 btrfs_header_level(buf), 1,
421 &refs, &flags);
422 if (ret)
423 return ret;
420 if (refs == 0) {
421 ret = -EROFS;
422 btrfs_handle_fs_error(fs_info, ret, NULL);
424 if (unlikely(refs == 0)) {
425 btrfs_crit(fs_info,
426 "found 0 references for tree block at bytenr %llu level %d root %llu",
427 buf->start, btrfs_header_level(buf),
428 btrfs_root_id(root));
429 ret = -EUCLEAN;
430 btrfs_abort_transaction(trans, ret);
423 return ret;
424 }
425 } else {
426 refs = 1;
427 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
428 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
429 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
430 else

--- 28 unchanged lines hidden (view full) ---

459 BTRFS_TREE_RELOC_OBJECTID)
460 ret = btrfs_inc_ref(trans, root, cow, 1);
461 else
462 ret = btrfs_inc_ref(trans, root, cow, 0);
463 if (ret)
464 return ret;
465 }
466 if (new_flags != 0) {
431 return ret;
432 }
433 } else {
434 refs = 1;
435 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
436 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
437 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
438 else

--- 28 unchanged lines hidden (view full) ---

467 BTRFS_TREE_RELOC_OBJECTID)
468 ret = btrfs_inc_ref(trans, root, cow, 1);
469 else
470 ret = btrfs_inc_ref(trans, root, cow, 0);
471 if (ret)
472 return ret;
473 }
474 if (new_flags != 0) {
467 int level = btrfs_header_level(buf);
468
469 ret = btrfs_set_disk_extent_flags(trans, buf,
470 new_flags, level);
475 ret = btrfs_set_disk_extent_flags(trans, buf, new_flags);
471 if (ret)
472 return ret;
473 }
474 } else {
475 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
476 if (root->root_key.objectid ==
477 BTRFS_TREE_RELOC_OBJECTID)
478 ret = btrfs_inc_ref(trans, root, cow, 1);

--- 99 unchanged lines hidden (view full) ---

578 }
579
580 if (buf == root->node) {
581 WARN_ON(parent && parent != buf);
582 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
583 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
584 parent_start = buf->start;
585
476 if (ret)
477 return ret;
478 }
479 } else {
480 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
481 if (root->root_key.objectid ==
482 BTRFS_TREE_RELOC_OBJECTID)
483 ret = btrfs_inc_ref(trans, root, cow, 1);

--- 99 unchanged lines hidden (view full) ---

583 }
584
585 if (buf == root->node) {
586 WARN_ON(parent && parent != buf);
587 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
588 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
589 parent_start = buf->start;
590
586 atomic_inc(&cow->refs);
587 ret = btrfs_tree_mod_log_insert_root(root->node, cow, true);
591 ret = btrfs_tree_mod_log_insert_root(root->node, cow, true);
588 BUG_ON(ret < 0);
592 if (ret < 0) {
593 btrfs_tree_unlock(cow);
594 free_extent_buffer(cow);
595 btrfs_abort_transaction(trans, ret);
596 return ret;
597 }
598 atomic_inc(&cow->refs);
589 rcu_assign_pointer(root->node, cow);
590
591 btrfs_free_tree_block(trans, btrfs_root_id(root), buf,
592 parent_start, last_ref);
593 free_extent_buffer(buf);
594 add_root_to_dirty_list(root);
595 } else {
596 WARN_ON(trans->transid != btrfs_header_generation(parent));
599 rcu_assign_pointer(root->node, cow);
600
601 btrfs_free_tree_block(trans, btrfs_root_id(root), buf,
602 parent_start, last_ref);
603 free_extent_buffer(buf);
604 add_root_to_dirty_list(root);
605 } else {
606 WARN_ON(trans->transid != btrfs_header_generation(parent));
597 btrfs_tree_mod_log_insert_key(parent, parent_slot,
598 BTRFS_MOD_LOG_KEY_REPLACE);
607 ret = btrfs_tree_mod_log_insert_key(parent, parent_slot,
608 BTRFS_MOD_LOG_KEY_REPLACE);
609 if (ret) {
610 btrfs_tree_unlock(cow);
611 free_extent_buffer(cow);
612 btrfs_abort_transaction(trans, ret);
613 return ret;
614 }
599 btrfs_set_node_blockptr(parent, parent_slot,
600 cow->start);
601 btrfs_set_node_ptr_generation(parent, parent_slot,
602 trans->transid);
603 btrfs_mark_buffer_dirty(parent);
604 if (last_ref) {
605 ret = btrfs_tree_mod_log_free_eb(buf);
606 if (ret) {

--- 58 unchanged lines hidden (view full) ---

665 struct btrfs_fs_info *fs_info = root->fs_info;
666 u64 search_start;
667 int ret;
668
669 if (test_bit(BTRFS_ROOT_DELETING, &root->state))
670 btrfs_err(fs_info,
671 "COW'ing blocks on a fs root that's being dropped");
672
615 btrfs_set_node_blockptr(parent, parent_slot,
616 cow->start);
617 btrfs_set_node_ptr_generation(parent, parent_slot,
618 trans->transid);
619 btrfs_mark_buffer_dirty(parent);
620 if (last_ref) {
621 ret = btrfs_tree_mod_log_free_eb(buf);
622 if (ret) {

--- 58 unchanged lines hidden (view full) ---

681 struct btrfs_fs_info *fs_info = root->fs_info;
682 u64 search_start;
683 int ret;
684
685 if (test_bit(BTRFS_ROOT_DELETING, &root->state))
686 btrfs_err(fs_info,
687 "COW'ing blocks on a fs root that's being dropped");
688
673 if (trans->transaction != fs_info->running_transaction)
674 WARN(1, KERN_CRIT "trans %llu running %llu\n",
675 trans->transid,
676 fs_info->running_transaction->transid);
689 /*
690 * COWing must happen through a running transaction, which always
691 * matches the current fs generation (it's a transaction with a state
692 * less than TRANS_STATE_UNBLOCKED). If it doesn't, then turn the fs
693 * into error state to prevent the commit of any transaction.
694 */
695 if (unlikely(trans->transaction != fs_info->running_transaction ||
696 trans->transid != fs_info->generation)) {
697 btrfs_abort_transaction(trans, -EUCLEAN);
698 btrfs_crit(fs_info,
699"unexpected transaction when attempting to COW block %llu on root %llu, transaction %llu running transaction %llu fs generation %llu",
700 buf->start, btrfs_root_id(root), trans->transid,
701 fs_info->running_transaction->transid,
702 fs_info->generation);
703 return -EUCLEAN;
704 }
677
705
678 if (trans->transid != fs_info->generation)
679 WARN(1, KERN_CRIT "trans %llu running %llu\n",
680 trans->transid, fs_info->generation);
681
682 if (!should_cow_block(trans, root, buf)) {
683 *cow_ret = buf;
684 return 0;
685 }
686
687 search_start = buf->start & ~((u64)SZ_1G - 1);
688
689 /*

--- 333 unchanged lines hidden (view full) ---

1023
1024 if (btrfs_header_nritems(mid) != 1)
1025 return 0;
1026
1027 /* promote the child to a root */
1028 child = btrfs_read_node_slot(mid, 0);
1029 if (IS_ERR(child)) {
1030 ret = PTR_ERR(child);
706 if (!should_cow_block(trans, root, buf)) {
707 *cow_ret = buf;
708 return 0;
709 }
710
711 search_start = buf->start & ~((u64)SZ_1G - 1);
712
713 /*

--- 333 unchanged lines hidden (view full) ---

1047
1048 if (btrfs_header_nritems(mid) != 1)
1049 return 0;
1050
1051 /* promote the child to a root */
1052 child = btrfs_read_node_slot(mid, 0);
1053 if (IS_ERR(child)) {
1054 ret = PTR_ERR(child);
1031 btrfs_handle_fs_error(fs_info, ret, NULL);
1032 goto enospc;
1055 goto out;
1033 }
1034
1035 btrfs_tree_lock(child);
1036 ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
1037 BTRFS_NESTING_COW);
1038 if (ret) {
1039 btrfs_tree_unlock(child);
1040 free_extent_buffer(child);
1056 }
1057
1058 btrfs_tree_lock(child);
1059 ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
1060 BTRFS_NESTING_COW);
1061 if (ret) {
1062 btrfs_tree_unlock(child);
1063 free_extent_buffer(child);
1041 goto enospc;
1064 goto out;
1042 }
1043
1044 ret = btrfs_tree_mod_log_insert_root(root->node, child, true);
1065 }
1066
1067 ret = btrfs_tree_mod_log_insert_root(root->node, child, true);
1045 BUG_ON(ret < 0);
1068 if (ret < 0) {
1069 btrfs_tree_unlock(child);
1070 free_extent_buffer(child);
1071 btrfs_abort_transaction(trans, ret);
1072 goto out;
1073 }
1046 rcu_assign_pointer(root->node, child);
1047
1048 add_root_to_dirty_list(root);
1049 btrfs_tree_unlock(child);
1050
1051 path->locks[level] = 0;
1052 path->nodes[level] = NULL;
1053 btrfs_clear_buffer_dirty(trans, mid);

--- 11 unchanged lines hidden (view full) ---

1065 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
1066 return 0;
1067
1068 if (pslot) {
1069 left = btrfs_read_node_slot(parent, pslot - 1);
1070 if (IS_ERR(left)) {
1071 ret = PTR_ERR(left);
1072 left = NULL;
1074 rcu_assign_pointer(root->node, child);
1075
1076 add_root_to_dirty_list(root);
1077 btrfs_tree_unlock(child);
1078
1079 path->locks[level] = 0;
1080 path->nodes[level] = NULL;
1081 btrfs_clear_buffer_dirty(trans, mid);

--- 11 unchanged lines hidden (view full) ---

1093 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
1094 return 0;
1095
1096 if (pslot) {
1097 left = btrfs_read_node_slot(parent, pslot - 1);
1098 if (IS_ERR(left)) {
1099 ret = PTR_ERR(left);
1100 left = NULL;
1073 goto enospc;
1101 goto out;
1074 }
1075
1076 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
1077 wret = btrfs_cow_block(trans, root, left,
1078 parent, pslot - 1, &left,
1079 BTRFS_NESTING_LEFT_COW);
1080 if (wret) {
1081 ret = wret;
1102 }
1103
1104 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
1105 wret = btrfs_cow_block(trans, root, left,
1106 parent, pslot - 1, &left,
1107 BTRFS_NESTING_LEFT_COW);
1108 if (wret) {
1109 ret = wret;
1082 goto enospc;
1110 goto out;
1083 }
1084 }
1085
1086 if (pslot + 1 < btrfs_header_nritems(parent)) {
1087 right = btrfs_read_node_slot(parent, pslot + 1);
1088 if (IS_ERR(right)) {
1089 ret = PTR_ERR(right);
1090 right = NULL;
1111 }
1112 }
1113
1114 if (pslot + 1 < btrfs_header_nritems(parent)) {
1115 right = btrfs_read_node_slot(parent, pslot + 1);
1116 if (IS_ERR(right)) {
1117 ret = PTR_ERR(right);
1118 right = NULL;
1091 goto enospc;
1119 goto out;
1092 }
1093
1094 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
1095 wret = btrfs_cow_block(trans, root, right,
1096 parent, pslot + 1, &right,
1097 BTRFS_NESTING_RIGHT_COW);
1098 if (wret) {
1099 ret = wret;
1120 }
1121
1122 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
1123 wret = btrfs_cow_block(trans, root, right,
1124 parent, pslot + 1, &right,
1125 BTRFS_NESTING_RIGHT_COW);
1126 if (wret) {
1127 ret = wret;
1100 goto enospc;
1128 goto out;
1101 }
1102 }
1103
1104 /* first, try to make some room in the middle buffer */
1105 if (left) {
1106 orig_slot += btrfs_header_nritems(left);
1107 wret = push_node_left(trans, left, mid, 1);
1108 if (wret < 0)

--- 5 unchanged lines hidden (view full) ---

1114 */
1115 if (right) {
1116 wret = push_node_left(trans, mid, right, 1);
1117 if (wret < 0 && wret != -ENOSPC)
1118 ret = wret;
1119 if (btrfs_header_nritems(right) == 0) {
1120 btrfs_clear_buffer_dirty(trans, right);
1121 btrfs_tree_unlock(right);
1129 }
1130 }
1131
1132 /* first, try to make some room in the middle buffer */
1133 if (left) {
1134 orig_slot += btrfs_header_nritems(left);
1135 wret = push_node_left(trans, left, mid, 1);
1136 if (wret < 0)

--- 5 unchanged lines hidden (view full) ---

1142 */
1143 if (right) {
1144 wret = push_node_left(trans, mid, right, 1);
1145 if (wret < 0 && wret != -ENOSPC)
1146 ret = wret;
1147 if (btrfs_header_nritems(right) == 0) {
1148 btrfs_clear_buffer_dirty(trans, right);
1149 btrfs_tree_unlock(right);
1122 del_ptr(root, path, level + 1, pslot + 1);
1150 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot + 1);
1151 if (ret < 0) {
1152 free_extent_buffer_stale(right);
1153 right = NULL;
1154 goto out;
1155 }
1123 root_sub_used(root, right->len);
1124 btrfs_free_tree_block(trans, btrfs_root_id(root), right,
1125 0, 1);
1126 free_extent_buffer_stale(right);
1127 right = NULL;
1128 } else {
1129 struct btrfs_disk_key right_key;
1130 btrfs_node_key(right, &right_key, 0);
1131 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1132 BTRFS_MOD_LOG_KEY_REPLACE);
1156 root_sub_used(root, right->len);
1157 btrfs_free_tree_block(trans, btrfs_root_id(root), right,
1158 0, 1);
1159 free_extent_buffer_stale(right);
1160 right = NULL;
1161 } else {
1162 struct btrfs_disk_key right_key;
1163 btrfs_node_key(right, &right_key, 0);
1164 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1165 BTRFS_MOD_LOG_KEY_REPLACE);
1133 BUG_ON(ret < 0);
1166 if (ret < 0) {
1167 btrfs_abort_transaction(trans, ret);
1168 goto out;
1169 }
1134 btrfs_set_node_key(parent, &right_key, pslot + 1);
1135 btrfs_mark_buffer_dirty(parent);
1136 }
1137 }
1138 if (btrfs_header_nritems(mid) == 1) {
1139 /*
1140 * we're not allowed to leave a node with one item in the
1141 * tree during a delete. A deletion from lower in the tree
1142 * could try to delete the only pointer in this node.
1143 * So, pull some keys from the left.
1144 * There has to be a left pointer at this point because
1145 * otherwise we would have pulled some pointers from the
1146 * right
1147 */
1170 btrfs_set_node_key(parent, &right_key, pslot + 1);
1171 btrfs_mark_buffer_dirty(parent);
1172 }
1173 }
1174 if (btrfs_header_nritems(mid) == 1) {
1175 /*
1176 * we're not allowed to leave a node with one item in the
1177 * tree during a delete. A deletion from lower in the tree
1178 * could try to delete the only pointer in this node.
1179 * So, pull some keys from the left.
1180 * There has to be a left pointer at this point because
1181 * otherwise we would have pulled some pointers from the
1182 * right
1183 */
1148 if (!left) {
1149 ret = -EROFS;
1150 btrfs_handle_fs_error(fs_info, ret, NULL);
1151 goto enospc;
1184 if (unlikely(!left)) {
1185 btrfs_crit(fs_info,
1186"missing left child when middle child only has 1 item, parent bytenr %llu level %d mid bytenr %llu root %llu",
1187 parent->start, btrfs_header_level(parent),
1188 mid->start, btrfs_root_id(root));
1189 ret = -EUCLEAN;
1190 btrfs_abort_transaction(trans, ret);
1191 goto out;
1152 }
1153 wret = balance_node_right(trans, mid, left);
1154 if (wret < 0) {
1155 ret = wret;
1192 }
1193 wret = balance_node_right(trans, mid, left);
1194 if (wret < 0) {
1195 ret = wret;
1156 goto enospc;
1196 goto out;
1157 }
1158 if (wret == 1) {
1159 wret = push_node_left(trans, left, mid, 1);
1160 if (wret < 0)
1161 ret = wret;
1162 }
1163 BUG_ON(wret == 1);
1164 }
1165 if (btrfs_header_nritems(mid) == 0) {
1166 btrfs_clear_buffer_dirty(trans, mid);
1167 btrfs_tree_unlock(mid);
1197 }
1198 if (wret == 1) {
1199 wret = push_node_left(trans, left, mid, 1);
1200 if (wret < 0)
1201 ret = wret;
1202 }
1203 BUG_ON(wret == 1);
1204 }
1205 if (btrfs_header_nritems(mid) == 0) {
1206 btrfs_clear_buffer_dirty(trans, mid);
1207 btrfs_tree_unlock(mid);
1168 del_ptr(root, path, level + 1, pslot);
1208 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
1209 if (ret < 0) {
1210 free_extent_buffer_stale(mid);
1211 mid = NULL;
1212 goto out;
1213 }
1169 root_sub_used(root, mid->len);
1170 btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1);
1171 free_extent_buffer_stale(mid);
1172 mid = NULL;
1173 } else {
1174 /* update the parent key to reflect our changes */
1175 struct btrfs_disk_key mid_key;
1176 btrfs_node_key(mid, &mid_key, 0);
1177 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1178 BTRFS_MOD_LOG_KEY_REPLACE);
1214 root_sub_used(root, mid->len);
1215 btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1);
1216 free_extent_buffer_stale(mid);
1217 mid = NULL;
1218 } else {
1219 /* update the parent key to reflect our changes */
1220 struct btrfs_disk_key mid_key;
1221 btrfs_node_key(mid, &mid_key, 0);
1222 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1223 BTRFS_MOD_LOG_KEY_REPLACE);
1179 BUG_ON(ret < 0);
1224 if (ret < 0) {
1225 btrfs_abort_transaction(trans, ret);
1226 goto out;
1227 }
1180 btrfs_set_node_key(parent, &mid_key, pslot);
1181 btrfs_mark_buffer_dirty(parent);
1182 }
1183
1184 /* update the path */
1185 if (left) {
1186 if (btrfs_header_nritems(left) > orig_slot) {
1187 atomic_inc(&left->refs);

--- 9 unchanged lines hidden (view full) ---

1197 orig_slot -= btrfs_header_nritems(left);
1198 path->slots[level] = orig_slot;
1199 }
1200 }
1201 /* double check we haven't messed things up */
1202 if (orig_ptr !=
1203 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1204 BUG();
1228 btrfs_set_node_key(parent, &mid_key, pslot);
1229 btrfs_mark_buffer_dirty(parent);
1230 }
1231
1232 /* update the path */
1233 if (left) {
1234 if (btrfs_header_nritems(left) > orig_slot) {
1235 atomic_inc(&left->refs);

--- 9 unchanged lines hidden (view full) ---

1245 orig_slot -= btrfs_header_nritems(left);
1246 path->slots[level] = orig_slot;
1247 }
1248 }
1249 /* double check we haven't messed things up */
1250 if (orig_ptr !=
1251 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1252 BUG();
1205enospc:
1253out:
1206 if (right) {
1207 btrfs_tree_unlock(right);
1208 free_extent_buffer(right);
1209 }
1210 if (left) {
1211 if (path->nodes[level] != left)
1212 btrfs_tree_unlock(left);
1213 free_extent_buffer(left);

--- 59 unchanged lines hidden (view full) ---

1273 if (wret < 0)
1274 ret = wret;
1275 if (wret == 0) {
1276 struct btrfs_disk_key disk_key;
1277 orig_slot += left_nr;
1278 btrfs_node_key(mid, &disk_key, 0);
1279 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1280 BTRFS_MOD_LOG_KEY_REPLACE);
1254 if (right) {
1255 btrfs_tree_unlock(right);
1256 free_extent_buffer(right);
1257 }
1258 if (left) {
1259 if (path->nodes[level] != left)
1260 btrfs_tree_unlock(left);
1261 free_extent_buffer(left);

--- 59 unchanged lines hidden (view full) ---

1321 if (wret < 0)
1322 ret = wret;
1323 if (wret == 0) {
1324 struct btrfs_disk_key disk_key;
1325 orig_slot += left_nr;
1326 btrfs_node_key(mid, &disk_key, 0);
1327 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1328 BTRFS_MOD_LOG_KEY_REPLACE);
1281 BUG_ON(ret < 0);
1329 if (ret < 0) {
1330 btrfs_tree_unlock(left);
1331 free_extent_buffer(left);
1332 btrfs_abort_transaction(trans, ret);
1333 return ret;
1334 }
1282 btrfs_set_node_key(parent, &disk_key, pslot);
1283 btrfs_mark_buffer_dirty(parent);
1284 if (btrfs_header_nritems(left) > orig_slot) {
1285 path->nodes[level] = left;
1286 path->slots[level + 1] -= 1;
1287 path->slots[level] = orig_slot;
1288 btrfs_tree_unlock(mid);
1289 free_extent_buffer(mid);

--- 38 unchanged lines hidden (view full) ---

1328 if (wret < 0)
1329 ret = wret;
1330 if (wret == 0) {
1331 struct btrfs_disk_key disk_key;
1332
1333 btrfs_node_key(right, &disk_key, 0);
1334 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1335 BTRFS_MOD_LOG_KEY_REPLACE);
1335 btrfs_set_node_key(parent, &disk_key, pslot);
1336 btrfs_mark_buffer_dirty(parent);
1337 if (btrfs_header_nritems(left) > orig_slot) {
1338 path->nodes[level] = left;
1339 path->slots[level + 1] -= 1;
1340 path->slots[level] = orig_slot;
1341 btrfs_tree_unlock(mid);
1342 free_extent_buffer(mid);

--- 38 unchanged lines hidden (view full) ---

1381 if (wret < 0)
1382 ret = wret;
1383 if (wret == 0) {
1384 struct btrfs_disk_key disk_key;
1385
1386 btrfs_node_key(right, &disk_key, 0);
1387 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1388 BTRFS_MOD_LOG_KEY_REPLACE);
1336 BUG_ON(ret < 0);
1389 if (ret < 0) {
1390 btrfs_tree_unlock(right);
1391 free_extent_buffer(right);
1392 btrfs_abort_transaction(trans, ret);
1393 return ret;
1394 }
1337 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1338 btrfs_mark_buffer_dirty(parent);
1339
1340 if (btrfs_header_nritems(mid) <= orig_slot) {
1341 path->nodes[level] = right;
1342 path->slots[level + 1] += 1;
1343 path->slots[level] = orig_slot -
1344 btrfs_header_nritems(mid);

--- 1029 unchanged lines hidden (view full) ---

2374done:
2375 if (ret < 0)
2376 btrfs_release_path(p);
2377
2378 return ret;
2379}
2380
2381/*
1395 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1396 btrfs_mark_buffer_dirty(parent);
1397
1398 if (btrfs_header_nritems(mid) <= orig_slot) {
1399 path->nodes[level] = right;
1400 path->slots[level + 1] += 1;
1401 path->slots[level] = orig_slot -
1402 btrfs_header_nritems(mid);

--- 1029 unchanged lines hidden (view full) ---

2432done:
2433 if (ret < 0)
2434 btrfs_release_path(p);
2435
2436 return ret;
2437}
2438
2439/*
2440 * Search the tree again to find a leaf with smaller keys.
2441 * Returns 0 if it found something.
2442 * Returns 1 if there are no smaller keys.
2443 * Returns < 0 on error.
2444 *
2445 * This may release the path, and so you may lose any locks held at the
2446 * time you call it.
2447 */
2448static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2449{
2450 struct btrfs_key key;
2451 struct btrfs_key orig_key;
2452 struct btrfs_disk_key found_key;
2453 int ret;
2454
2455 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
2456 orig_key = key;
2457
2458 if (key.offset > 0) {
2459 key.offset--;
2460 } else if (key.type > 0) {
2461 key.type--;
2462 key.offset = (u64)-1;
2463 } else if (key.objectid > 0) {
2464 key.objectid--;
2465 key.type = (u8)-1;
2466 key.offset = (u64)-1;
2467 } else {
2468 return 1;
2469 }
2470
2471 btrfs_release_path(path);
2472 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2473 if (ret <= 0)
2474 return ret;
2475
2476 /*
2477 * Previous key not found. Even if we were at slot 0 of the leaf we had
2478 * before releasing the path and calling btrfs_search_slot(), we now may
2479 * be in a slot pointing to the same original key - this can happen if
2480 * after we released the path, one of more items were moved from a
2481 * sibling leaf into the front of the leaf we had due to an insertion
2482 * (see push_leaf_right()).
2483 * If we hit this case and our slot is > 0 and just decrement the slot
2484 * so that the caller does not process the same key again, which may or
2485 * may not break the caller, depending on its logic.
2486 */
2487 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
2488 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
2489 ret = comp_keys(&found_key, &orig_key);
2490 if (ret == 0) {
2491 if (path->slots[0] > 0) {
2492 path->slots[0]--;
2493 return 0;
2494 }
2495 /*
2496 * At slot 0, same key as before, it means orig_key is
2497 * the lowest, leftmost, key in the tree. We're done.
2498 */
2499 return 1;
2500 }
2501 }
2502
2503 btrfs_item_key(path->nodes[0], &found_key, 0);
2504 ret = comp_keys(&found_key, &key);
2505 /*
2506 * We might have had an item with the previous key in the tree right
2507 * before we released our path. And after we released our path, that
2508 * item might have been pushed to the first slot (0) of the leaf we
2509 * were holding due to a tree balance. Alternatively, an item with the
2510 * previous key can exist as the only element of a leaf (big fat item).
2511 * Therefore account for these 2 cases, so that our callers (like
2512 * btrfs_previous_item) don't miss an existing item with a key matching
2513 * the previous key we computed above.
2514 */
2515 if (ret <= 0)
2516 return 0;
2517 return 1;
2518}
2519
2520/*
2382 * helper to use instead of search slot if no exact match is needed but
2383 * instead the next or previous item should be returned.
2384 * When find_higher is true, the next higher item is returned, the next lower
2385 * otherwise.
2386 * When return_any and find_higher are both true, and no higher item is found,
2387 * return the next lower instead.
2388 * When return_any is true and find_higher is false, and no lower item is found,
2389 * return the next higher instead.

--- 157 unchanged lines hidden (view full) ---

2547 struct extent_buffer *eb;
2548 int slot;
2549
2550 eb = path->nodes[0];
2551 slot = path->slots[0];
2552 if (slot > 0) {
2553 btrfs_item_key(eb, &disk_key, slot - 1);
2554 if (unlikely(comp_keys(&disk_key, new_key) >= 0)) {
2521 * helper to use instead of search slot if no exact match is needed but
2522 * instead the next or previous item should be returned.
2523 * When find_higher is true, the next higher item is returned, the next lower
2524 * otherwise.
2525 * When return_any and find_higher are both true, and no higher item is found,
2526 * return the next lower instead.
2527 * When return_any is true and find_higher is false, and no lower item is found,
2528 * return the next higher instead.

--- 157 unchanged lines hidden (view full) ---

2686 struct extent_buffer *eb;
2687 int slot;
2688
2689 eb = path->nodes[0];
2690 slot = path->slots[0];
2691 if (slot > 0) {
2692 btrfs_item_key(eb, &disk_key, slot - 1);
2693 if (unlikely(comp_keys(&disk_key, new_key) >= 0)) {
2694 btrfs_print_leaf(eb);
2555 btrfs_crit(fs_info,
2556 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2557 slot, btrfs_disk_key_objectid(&disk_key),
2558 btrfs_disk_key_type(&disk_key),
2559 btrfs_disk_key_offset(&disk_key),
2560 new_key->objectid, new_key->type,
2561 new_key->offset);
2695 btrfs_crit(fs_info,
2696 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2697 slot, btrfs_disk_key_objectid(&disk_key),
2698 btrfs_disk_key_type(&disk_key),
2699 btrfs_disk_key_offset(&disk_key),
2700 new_key->objectid, new_key->type,
2701 new_key->offset);
2562 btrfs_print_leaf(eb);
2563 BUG();
2564 }
2565 }
2566 if (slot < btrfs_header_nritems(eb) - 1) {
2567 btrfs_item_key(eb, &disk_key, slot + 1);
2568 if (unlikely(comp_keys(&disk_key, new_key) <= 0)) {
2702 BUG();
2703 }
2704 }
2705 if (slot < btrfs_header_nritems(eb) - 1) {
2706 btrfs_item_key(eb, &disk_key, slot + 1);
2707 if (unlikely(comp_keys(&disk_key, new_key) <= 0)) {
2708 btrfs_print_leaf(eb);
2569 btrfs_crit(fs_info,
2570 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2571 slot, btrfs_disk_key_objectid(&disk_key),
2572 btrfs_disk_key_type(&disk_key),
2573 btrfs_disk_key_offset(&disk_key),
2574 new_key->objectid, new_key->type,
2575 new_key->offset);
2709 btrfs_crit(fs_info,
2710 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2711 slot, btrfs_disk_key_objectid(&disk_key),
2712 btrfs_disk_key_type(&disk_key),
2713 btrfs_disk_key_offset(&disk_key),
2714 new_key->objectid, new_key->type,
2715 new_key->offset);
2576 btrfs_print_leaf(eb);
2577 BUG();
2578 }
2579 }
2580
2581 btrfs_cpu_key_to_disk(&disk_key, new_key);
2582 btrfs_set_item_key(eb, &disk_key, slot);
2583 btrfs_mark_buffer_dirty(eb);
2584 if (slot == 0)

--- 36 unchanged lines hidden (view full) ---

2621 if (level) {
2622 btrfs_node_key_to_cpu(left, &left_last, nr_left - 1);
2623 btrfs_node_key_to_cpu(right, &right_first, 0);
2624 } else {
2625 btrfs_item_key_to_cpu(left, &left_last, nr_left - 1);
2626 btrfs_item_key_to_cpu(right, &right_first, 0);
2627 }
2628
2716 BUG();
2717 }
2718 }
2719
2720 btrfs_cpu_key_to_disk(&disk_key, new_key);
2721 btrfs_set_item_key(eb, &disk_key, slot);
2722 btrfs_mark_buffer_dirty(eb);
2723 if (slot == 0)

--- 36 unchanged lines hidden (view full) ---

2760 if (level) {
2761 btrfs_node_key_to_cpu(left, &left_last, nr_left - 1);
2762 btrfs_node_key_to_cpu(right, &right_first, 0);
2763 } else {
2764 btrfs_item_key_to_cpu(left, &left_last, nr_left - 1);
2765 btrfs_item_key_to_cpu(right, &right_first, 0);
2766 }
2767
2629 if (btrfs_comp_cpu_keys(&left_last, &right_first) >= 0) {
2768 if (unlikely(btrfs_comp_cpu_keys(&left_last, &right_first) >= 0)) {
2630 btrfs_crit(left->fs_info, "left extent buffer:");
2631 btrfs_print_tree(left, false);
2632 btrfs_crit(left->fs_info, "right extent buffer:");
2633 btrfs_print_tree(right, false);
2634 btrfs_crit(left->fs_info,
2635"bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)",
2636 left_last.objectid, left_last.type,
2637 left_last.offset, right_first.objectid,

--- 60 unchanged lines hidden (view full) ---

2698 }
2699 copy_extent_buffer(dst, src,
2700 btrfs_node_key_ptr_offset(dst, dst_nritems),
2701 btrfs_node_key_ptr_offset(src, 0),
2702 push_items * sizeof(struct btrfs_key_ptr));
2703
2704 if (push_items < src_nritems) {
2705 /*
2769 btrfs_crit(left->fs_info, "left extent buffer:");
2770 btrfs_print_tree(left, false);
2771 btrfs_crit(left->fs_info, "right extent buffer:");
2772 btrfs_print_tree(right, false);
2773 btrfs_crit(left->fs_info,
2774"bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)",
2775 left_last.objectid, left_last.type,
2776 left_last.offset, right_first.objectid,

--- 60 unchanged lines hidden (view full) ---

2837 }
2838 copy_extent_buffer(dst, src,
2839 btrfs_node_key_ptr_offset(dst, dst_nritems),
2840 btrfs_node_key_ptr_offset(src, 0),
2841 push_items * sizeof(struct btrfs_key_ptr));
2842
2843 if (push_items < src_nritems) {
2844 /*
2706 * Don't call btrfs_tree_mod_log_insert_move() here, key removal
2707 * was already fully logged by btrfs_tree_mod_log_eb_copy() above.
2845 * btrfs_tree_mod_log_eb_copy handles logging the move, so we
2846 * don't need to do an explicit tree mod log operation for it.
2708 */
2709 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(src, 0),
2710 btrfs_node_key_ptr_offset(src, push_items),
2711 (src_nritems - push_items) *
2712 sizeof(struct btrfs_key_ptr));
2713 }
2714 btrfs_set_header_nritems(src, src_nritems - push_items);
2715 btrfs_set_header_nritems(dst, dst_nritems + push_items);

--- 44 unchanged lines hidden (view full) ---

2760 push_items = max_push;
2761
2762 /* dst is the right eb, src is the middle eb */
2763 if (check_sibling_keys(src, dst)) {
2764 ret = -EUCLEAN;
2765 btrfs_abort_transaction(trans, ret);
2766 return ret;
2767 }
2847 */
2848 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(src, 0),
2849 btrfs_node_key_ptr_offset(src, push_items),
2850 (src_nritems - push_items) *
2851 sizeof(struct btrfs_key_ptr));
2852 }
2853 btrfs_set_header_nritems(src, src_nritems - push_items);
2854 btrfs_set_header_nritems(dst, dst_nritems + push_items);

--- 44 unchanged lines hidden (view full) ---

2899 push_items = max_push;
2900
2901 /* dst is the right eb, src is the middle eb */
2902 if (check_sibling_keys(src, dst)) {
2903 ret = -EUCLEAN;
2904 btrfs_abort_transaction(trans, ret);
2905 return ret;
2906 }
2768 ret = btrfs_tree_mod_log_insert_move(dst, push_items, 0, dst_nritems);
2769 BUG_ON(ret < 0);
2907
2908 /*
2909 * btrfs_tree_mod_log_eb_copy handles logging the move, so we don't
2910 * need to do an explicit tree mod log operation for it.
2911 */
2770 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(dst, push_items),
2771 btrfs_node_key_ptr_offset(dst, 0),
2772 (dst_nritems) *
2773 sizeof(struct btrfs_key_ptr));
2774
2775 ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
2776 push_items);
2777 if (ret) {

--- 57 unchanged lines hidden (view full) ---

2835 WARN_ON(lower_gen != trans->transid);
2836
2837 btrfs_set_node_ptr_generation(c, 0, lower_gen);
2838
2839 btrfs_mark_buffer_dirty(c);
2840
2841 old = root->node;
2842 ret = btrfs_tree_mod_log_insert_root(root->node, c, false);
2912 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(dst, push_items),
2913 btrfs_node_key_ptr_offset(dst, 0),
2914 (dst_nritems) *
2915 sizeof(struct btrfs_key_ptr));
2916
2917 ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
2918 push_items);
2919 if (ret) {

--- 57 unchanged lines hidden (view full) ---

2977 WARN_ON(lower_gen != trans->transid);
2978
2979 btrfs_set_node_ptr_generation(c, 0, lower_gen);
2980
2981 btrfs_mark_buffer_dirty(c);
2982
2983 old = root->node;
2984 ret = btrfs_tree_mod_log_insert_root(root->node, c, false);
2843 BUG_ON(ret < 0);
2985 if (ret < 0) {
2986 btrfs_free_tree_block(trans, btrfs_root_id(root), c, 0, 1);
2987 btrfs_tree_unlock(c);
2988 free_extent_buffer(c);
2989 return ret;
2990 }
2844 rcu_assign_pointer(root->node, c);
2845
2846 /* the super has an extra ref to root->node */
2847 free_extent_buffer(old);
2848
2849 add_root_to_dirty_list(root);
2850 atomic_inc(&c->refs);
2851 path->nodes[level] = c;

--- 4 unchanged lines hidden (view full) ---

2856
2857/*
2858 * worker function to insert a single pointer in a node.
2859 * the node should have enough room for the pointer already
2860 *
2861 * slot and level indicate where you want the key to go, and
2862 * blocknr is the block the key points to.
2863 */
2991 rcu_assign_pointer(root->node, c);
2992
2993 /* the super has an extra ref to root->node */
2994 free_extent_buffer(old);
2995
2996 add_root_to_dirty_list(root);
2997 atomic_inc(&c->refs);
2998 path->nodes[level] = c;

--- 4 unchanged lines hidden (view full) ---

3003
3004/*
3005 * worker function to insert a single pointer in a node.
3006 * the node should have enough room for the pointer already
3007 *
3008 * slot and level indicate where you want the key to go, and
3009 * blocknr is the block the key points to.
3010 */
2864static void insert_ptr(struct btrfs_trans_handle *trans,
2865 struct btrfs_path *path,
2866 struct btrfs_disk_key *key, u64 bytenr,
2867 int slot, int level)
3011static int insert_ptr(struct btrfs_trans_handle *trans,
3012 struct btrfs_path *path,
3013 struct btrfs_disk_key *key, u64 bytenr,
3014 int slot, int level)
2868{
2869 struct extent_buffer *lower;
2870 int nritems;
2871 int ret;
2872
2873 BUG_ON(!path->nodes[level]);
2874 btrfs_assert_tree_write_locked(path->nodes[level]);
2875 lower = path->nodes[level];
2876 nritems = btrfs_header_nritems(lower);
2877 BUG_ON(slot > nritems);
2878 BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
2879 if (slot != nritems) {
2880 if (level) {
2881 ret = btrfs_tree_mod_log_insert_move(lower, slot + 1,
2882 slot, nritems - slot);
3015{
3016 struct extent_buffer *lower;
3017 int nritems;
3018 int ret;
3019
3020 BUG_ON(!path->nodes[level]);
3021 btrfs_assert_tree_write_locked(path->nodes[level]);
3022 lower = path->nodes[level];
3023 nritems = btrfs_header_nritems(lower);
3024 BUG_ON(slot > nritems);
3025 BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
3026 if (slot != nritems) {
3027 if (level) {
3028 ret = btrfs_tree_mod_log_insert_move(lower, slot + 1,
3029 slot, nritems - slot);
2883 BUG_ON(ret < 0);
3030 if (ret < 0) {
3031 btrfs_abort_transaction(trans, ret);
3032 return ret;
3033 }
2884 }
2885 memmove_extent_buffer(lower,
2886 btrfs_node_key_ptr_offset(lower, slot + 1),
2887 btrfs_node_key_ptr_offset(lower, slot),
2888 (nritems - slot) * sizeof(struct btrfs_key_ptr));
2889 }
2890 if (level) {
2891 ret = btrfs_tree_mod_log_insert_key(lower, slot,
2892 BTRFS_MOD_LOG_KEY_ADD);
3034 }
3035 memmove_extent_buffer(lower,
3036 btrfs_node_key_ptr_offset(lower, slot + 1),
3037 btrfs_node_key_ptr_offset(lower, slot),
3038 (nritems - slot) * sizeof(struct btrfs_key_ptr));
3039 }
3040 if (level) {
3041 ret = btrfs_tree_mod_log_insert_key(lower, slot,
3042 BTRFS_MOD_LOG_KEY_ADD);
2893 BUG_ON(ret < 0);
3043 if (ret < 0) {
3044 btrfs_abort_transaction(trans, ret);
3045 return ret;
3046 }
2894 }
2895 btrfs_set_node_key(lower, key, slot);
2896 btrfs_set_node_blockptr(lower, slot, bytenr);
2897 WARN_ON(trans->transid == 0);
2898 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2899 btrfs_set_header_nritems(lower, nritems + 1);
2900 btrfs_mark_buffer_dirty(lower);
3047 }
3048 btrfs_set_node_key(lower, key, slot);
3049 btrfs_set_node_blockptr(lower, slot, bytenr);
3050 WARN_ON(trans->transid == 0);
3051 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
3052 btrfs_set_header_nritems(lower, nritems + 1);
3053 btrfs_mark_buffer_dirty(lower);
3054
3055 return 0;
2901}
2902
2903/*
2904 * split the node at the specified level in path in two.
2905 * The path is corrected to point to the appropriate node after the split
2906 *
2907 * Before splitting this tries to make some room in the node by pushing
2908 * left and right, if either one works, it returns right away.

--- 48 unchanged lines hidden (view full) ---

2957 if (IS_ERR(split))
2958 return PTR_ERR(split);
2959
2960 root_add_used(root, fs_info->nodesize);
2961 ASSERT(btrfs_header_level(c) == level);
2962
2963 ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid);
2964 if (ret) {
3056}
3057
3058/*
3059 * split the node at the specified level in path in two.
3060 * The path is corrected to point to the appropriate node after the split
3061 *
3062 * Before splitting this tries to make some room in the node by pushing
3063 * left and right, if either one works, it returns right away.

--- 48 unchanged lines hidden (view full) ---

3112 if (IS_ERR(split))
3113 return PTR_ERR(split);
3114
3115 root_add_used(root, fs_info->nodesize);
3116 ASSERT(btrfs_header_level(c) == level);
3117
3118 ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid);
3119 if (ret) {
3120 btrfs_tree_unlock(split);
3121 free_extent_buffer(split);
2965 btrfs_abort_transaction(trans, ret);
2966 return ret;
2967 }
2968 copy_extent_buffer(split, c,
2969 btrfs_node_key_ptr_offset(split, 0),
2970 btrfs_node_key_ptr_offset(c, mid),
2971 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2972 btrfs_set_header_nritems(split, c_nritems - mid);
2973 btrfs_set_header_nritems(c, mid);
2974
2975 btrfs_mark_buffer_dirty(c);
2976 btrfs_mark_buffer_dirty(split);
2977
3122 btrfs_abort_transaction(trans, ret);
3123 return ret;
3124 }
3125 copy_extent_buffer(split, c,
3126 btrfs_node_key_ptr_offset(split, 0),
3127 btrfs_node_key_ptr_offset(c, mid),
3128 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
3129 btrfs_set_header_nritems(split, c_nritems - mid);
3130 btrfs_set_header_nritems(c, mid);
3131
3132 btrfs_mark_buffer_dirty(c);
3133 btrfs_mark_buffer_dirty(split);
3134
2978 insert_ptr(trans, path, &disk_key, split->start,
2979 path->slots[level + 1] + 1, level + 1);
3135 ret = insert_ptr(trans, path, &disk_key, split->start,
3136 path->slots[level + 1] + 1, level + 1);
3137 if (ret < 0) {
3138 btrfs_tree_unlock(split);
3139 free_extent_buffer(split);
3140 return ret;
3141 }
2980
2981 if (path->slots[level] >= mid) {
2982 path->slots[level] -= mid;
2983 btrfs_tree_unlock(c);
2984 free_extent_buffer(c);
2985 path->nodes[level] = split;
2986 path->slots[level + 1] += 1;
2987 } else {
2988 btrfs_tree_unlock(split);
2989 free_extent_buffer(split);
2990 }
2991 return 0;
2992}
2993
2994/*
2995 * how many bytes are required to store the items in a leaf. start
2996 * and nr indicate which items in the leaf to check. This totals up the
2997 * space used both by the item structs and the item data
2998 */
3142
3143 if (path->slots[level] >= mid) {
3144 path->slots[level] -= mid;
3145 btrfs_tree_unlock(c);
3146 free_extent_buffer(c);
3147 path->nodes[level] = split;
3148 path->slots[level + 1] += 1;
3149 } else {
3150 btrfs_tree_unlock(split);
3151 free_extent_buffer(split);
3152 }
3153 return 0;
3154}
3155
3156/*
3157 * how many bytes are required to store the items in a leaf. start
3158 * and nr indicate which items in the leaf to check. This totals up the
3159 * space used both by the item structs and the item data
3160 */
2999static int leaf_space_used(struct extent_buffer *l, int start, int nr)
3161static int leaf_space_used(const struct extent_buffer *l, int start, int nr)
3000{
3001 int data_len;
3002 int nritems = btrfs_header_nritems(l);
3003 int end = min(nritems, start + nr) - 1;
3004
3005 if (!nr)
3006 return 0;
3007 data_len = btrfs_item_offset(l, start) + btrfs_item_size(l, start);
3008 data_len = data_len - btrfs_item_offset(l, end);
3009 data_len += sizeof(struct btrfs_item) * nr;
3010 WARN_ON(data_len < 0);
3011 return data_len;
3012}
3013
3014/*
3015 * The space between the end of the leaf items and
3016 * the start of the leaf data. IOW, how much room
3017 * the leaf has left for both items and data
3018 */
3162{
3163 int data_len;
3164 int nritems = btrfs_header_nritems(l);
3165 int end = min(nritems, start + nr) - 1;
3166
3167 if (!nr)
3168 return 0;
3169 data_len = btrfs_item_offset(l, start) + btrfs_item_size(l, start);
3170 data_len = data_len - btrfs_item_offset(l, end);
3171 data_len += sizeof(struct btrfs_item) * nr;
3172 WARN_ON(data_len < 0);
3173 return data_len;
3174}
3175
3176/*
3177 * The space between the end of the leaf items and
3178 * the start of the leaf data. IOW, how much room
3179 * the leaf has left for both items and data
3180 */
3019noinline int btrfs_leaf_free_space(struct extent_buffer *leaf)
3181int btrfs_leaf_free_space(const struct extent_buffer *leaf)
3020{
3021 struct btrfs_fs_info *fs_info = leaf->fs_info;
3022 int nritems = btrfs_header_nritems(leaf);
3023 int ret;
3024
3025 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
3026 if (ret < 0) {
3027 btrfs_crit(fs_info,

--- 420 unchanged lines hidden (view full) ---

3448 free_extent_buffer(left);
3449 return ret;
3450}
3451
3452/*
3453 * split the path's leaf in two, making sure there is at least data_size
3454 * available for the resulting leaf level of the path.
3455 */
3182{
3183 struct btrfs_fs_info *fs_info = leaf->fs_info;
3184 int nritems = btrfs_header_nritems(leaf);
3185 int ret;
3186
3187 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
3188 if (ret < 0) {
3189 btrfs_crit(fs_info,

--- 420 unchanged lines hidden (view full) ---

3610 free_extent_buffer(left);
3611 return ret;
3612}
3613
3614/*
3615 * split the path's leaf in two, making sure there is at least data_size
3616 * available for the resulting leaf level of the path.
3617 */
3456static noinline void copy_for_split(struct btrfs_trans_handle *trans,
3457 struct btrfs_path *path,
3458 struct extent_buffer *l,
3459 struct extent_buffer *right,
3460 int slot, int mid, int nritems)
3618static noinline int copy_for_split(struct btrfs_trans_handle *trans,
3619 struct btrfs_path *path,
3620 struct extent_buffer *l,
3621 struct extent_buffer *right,
3622 int slot, int mid, int nritems)
3461{
3462 struct btrfs_fs_info *fs_info = trans->fs_info;
3463 int data_copy_size;
3464 int rt_data_off;
3465 int i;
3623{
3624 struct btrfs_fs_info *fs_info = trans->fs_info;
3625 int data_copy_size;
3626 int rt_data_off;
3627 int i;
3628 int ret;
3466 struct btrfs_disk_key disk_key;
3467 struct btrfs_map_token token;
3468
3469 nritems = nritems - mid;
3470 btrfs_set_header_nritems(right, nritems);
3471 data_copy_size = btrfs_item_data_end(l, mid) - leaf_data_end(l);
3472
3473 copy_leaf_items(right, l, 0, mid, nritems);

--- 8 unchanged lines hidden (view full) ---

3482 u32 ioff;
3483
3484 ioff = btrfs_token_item_offset(&token, i);
3485 btrfs_set_token_item_offset(&token, i, ioff + rt_data_off);
3486 }
3487
3488 btrfs_set_header_nritems(l, mid);
3489 btrfs_item_key(right, &disk_key, 0);
3629 struct btrfs_disk_key disk_key;
3630 struct btrfs_map_token token;
3631
3632 nritems = nritems - mid;
3633 btrfs_set_header_nritems(right, nritems);
3634 data_copy_size = btrfs_item_data_end(l, mid) - leaf_data_end(l);
3635
3636 copy_leaf_items(right, l, 0, mid, nritems);

--- 8 unchanged lines hidden (view full) ---

3645 u32 ioff;
3646
3647 ioff = btrfs_token_item_offset(&token, i);
3648 btrfs_set_token_item_offset(&token, i, ioff + rt_data_off);
3649 }
3650
3651 btrfs_set_header_nritems(l, mid);
3652 btrfs_item_key(right, &disk_key, 0);
3490 insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
3653 ret = insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
3654 if (ret < 0)
3655 return ret;
3491
3492 btrfs_mark_buffer_dirty(right);
3493 btrfs_mark_buffer_dirty(l);
3494 BUG_ON(path->slots[0] != slot);
3495
3496 if (mid <= slot) {
3497 btrfs_tree_unlock(path->nodes[0]);
3498 free_extent_buffer(path->nodes[0]);
3499 path->nodes[0] = right;
3500 path->slots[0] -= mid;
3501 path->slots[1] += 1;
3502 } else {
3503 btrfs_tree_unlock(right);
3504 free_extent_buffer(right);
3505 }
3506
3507 BUG_ON(path->slots[0] < 0);
3656
3657 btrfs_mark_buffer_dirty(right);
3658 btrfs_mark_buffer_dirty(l);
3659 BUG_ON(path->slots[0] != slot);
3660
3661 if (mid <= slot) {
3662 btrfs_tree_unlock(path->nodes[0]);
3663 free_extent_buffer(path->nodes[0]);
3664 path->nodes[0] = right;
3665 path->slots[0] -= mid;
3666 path->slots[1] += 1;
3667 } else {
3668 btrfs_tree_unlock(right);
3669 free_extent_buffer(right);
3670 }
3671
3672 BUG_ON(path->slots[0] < 0);
3673
3674 return 0;
3508}
3509
3510/*
3511 * double splits happen when we need to insert a big item in the middle
3512 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3513 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3514 * A B C
3515 *

--- 182 unchanged lines hidden (view full) ---

3698 if (IS_ERR(right))
3699 return PTR_ERR(right);
3700
3701 root_add_used(root, fs_info->nodesize);
3702
3703 if (split == 0) {
3704 if (mid <= slot) {
3705 btrfs_set_header_nritems(right, 0);
3675}
3676
3677/*
3678 * double splits happen when we need to insert a big item in the middle
3679 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3680 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3681 * A B C
3682 *

--- 182 unchanged lines hidden (view full) ---

3865 if (IS_ERR(right))
3866 return PTR_ERR(right);
3867
3868 root_add_used(root, fs_info->nodesize);
3869
3870 if (split == 0) {
3871 if (mid <= slot) {
3872 btrfs_set_header_nritems(right, 0);
3706 insert_ptr(trans, path, &disk_key,
3707 right->start, path->slots[1] + 1, 1);
3873 ret = insert_ptr(trans, path, &disk_key,
3874 right->start, path->slots[1] + 1, 1);
3875 if (ret < 0) {
3876 btrfs_tree_unlock(right);
3877 free_extent_buffer(right);
3878 return ret;
3879 }
3708 btrfs_tree_unlock(path->nodes[0]);
3709 free_extent_buffer(path->nodes[0]);
3710 path->nodes[0] = right;
3711 path->slots[0] = 0;
3712 path->slots[1] += 1;
3713 } else {
3714 btrfs_set_header_nritems(right, 0);
3880 btrfs_tree_unlock(path->nodes[0]);
3881 free_extent_buffer(path->nodes[0]);
3882 path->nodes[0] = right;
3883 path->slots[0] = 0;
3884 path->slots[1] += 1;
3885 } else {
3886 btrfs_set_header_nritems(right, 0);
3715 insert_ptr(trans, path, &disk_key,
3716 right->start, path->slots[1], 1);
3887 ret = insert_ptr(trans, path, &disk_key,
3888 right->start, path->slots[1], 1);
3889 if (ret < 0) {
3890 btrfs_tree_unlock(right);
3891 free_extent_buffer(right);
3892 return ret;
3893 }
3717 btrfs_tree_unlock(path->nodes[0]);
3718 free_extent_buffer(path->nodes[0]);
3719 path->nodes[0] = right;
3720 path->slots[0] = 0;
3721 if (path->slots[1] == 0)
3722 fixup_low_keys(path, &disk_key, 1);
3723 }
3724 /*
3725 * We create a new leaf 'right' for the required ins_len and
3726 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
3727 * the content of ins_len to 'right'.
3728 */
3729 return ret;
3730 }
3731
3894 btrfs_tree_unlock(path->nodes[0]);
3895 free_extent_buffer(path->nodes[0]);
3896 path->nodes[0] = right;
3897 path->slots[0] = 0;
3898 if (path->slots[1] == 0)
3899 fixup_low_keys(path, &disk_key, 1);
3900 }
3901 /*
3902 * We create a new leaf 'right' for the required ins_len and
3903 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
3904 * the content of ins_len to 'right'.
3905 */
3906 return ret;
3907 }
3908
3732 copy_for_split(trans, path, l, right, slot, mid, nritems);
3909 ret = copy_for_split(trans, path, l, right, slot, mid, nritems);
3910 if (ret < 0) {
3911 btrfs_tree_unlock(right);
3912 free_extent_buffer(right);
3913 return ret;
3914 }
3733
3734 if (split == 2) {
3735 BUG_ON(num_doubles != 0);
3736 num_doubles++;
3737 goto again;
3738 }
3739
3740 return 0;

--- 80 unchanged lines hidden (view full) ---

3821 int orig_slot, slot;
3822 char *buf;
3823 u32 nritems;
3824 u32 item_size;
3825 u32 orig_offset;
3826 struct btrfs_disk_key disk_key;
3827
3828 leaf = path->nodes[0];
3915
3916 if (split == 2) {
3917 BUG_ON(num_doubles != 0);
3918 num_doubles++;
3919 goto again;
3920 }
3921
3922 return 0;

--- 80 unchanged lines hidden (view full) ---

4003 int orig_slot, slot;
4004 char *buf;
4005 u32 nritems;
4006 u32 item_size;
4007 u32 orig_offset;
4008 struct btrfs_disk_key disk_key;
4009
4010 leaf = path->nodes[0];
3829 BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item));
4011 /*
4012 * Shouldn't happen because the caller must have previously called
4013 * setup_leaf_for_split() to make room for the new item in the leaf.
4014 */
4015 if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)))
4016 return -ENOSPC;
3830
3831 orig_slot = path->slots[0];
3832 orig_offset = btrfs_item_offset(leaf, path->slots[0]);
3833 item_size = btrfs_item_size(leaf, path->slots[0]);
3834
3835 buf = kmalloc(item_size, GFP_NOFS);
3836 if (!buf)
3837 return -ENOMEM;

--- 430 unchanged lines hidden (view full) ---

4268 return 0;
4269}
4270
4271/*
4272 * delete the pointer from a given node.
4273 *
4274 * the tree should have been previously balanced so the deletion does not
4275 * empty a node.
4017
4018 orig_slot = path->slots[0];
4019 orig_offset = btrfs_item_offset(leaf, path->slots[0]);
4020 item_size = btrfs_item_size(leaf, path->slots[0]);
4021
4022 buf = kmalloc(item_size, GFP_NOFS);
4023 if (!buf)
4024 return -ENOMEM;

--- 430 unchanged lines hidden (view full) ---

4455 return 0;
4456}
4457
4458/*
4459 * delete the pointer from a given node.
4460 *
4461 * the tree should have been previously balanced so the deletion does not
4462 * empty a node.
4463 *
4464 * This is exported for use inside btrfs-progs, don't un-export it.
4276 */
4465 */
4277static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
4278 int level, int slot)
4466int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4467 struct btrfs_path *path, int level, int slot)
4279{
4280 struct extent_buffer *parent = path->nodes[level];
4281 u32 nritems;
4282 int ret;
4283
4284 nritems = btrfs_header_nritems(parent);
4285 if (slot != nritems - 1) {
4286 if (level) {
4287 ret = btrfs_tree_mod_log_insert_move(parent, slot,
4288 slot + 1, nritems - slot - 1);
4468{
4469 struct extent_buffer *parent = path->nodes[level];
4470 u32 nritems;
4471 int ret;
4472
4473 nritems = btrfs_header_nritems(parent);
4474 if (slot != nritems - 1) {
4475 if (level) {
4476 ret = btrfs_tree_mod_log_insert_move(parent, slot,
4477 slot + 1, nritems - slot - 1);
4289 BUG_ON(ret < 0);
4478 if (ret < 0) {
4479 btrfs_abort_transaction(trans, ret);
4480 return ret;
4481 }
4290 }
4291 memmove_extent_buffer(parent,
4292 btrfs_node_key_ptr_offset(parent, slot),
4293 btrfs_node_key_ptr_offset(parent, slot + 1),
4294 sizeof(struct btrfs_key_ptr) *
4295 (nritems - slot - 1));
4296 } else if (level) {
4297 ret = btrfs_tree_mod_log_insert_key(parent, slot,
4298 BTRFS_MOD_LOG_KEY_REMOVE);
4482 }
4483 memmove_extent_buffer(parent,
4484 btrfs_node_key_ptr_offset(parent, slot),
4485 btrfs_node_key_ptr_offset(parent, slot + 1),
4486 sizeof(struct btrfs_key_ptr) *
4487 (nritems - slot - 1));
4488 } else if (level) {
4489 ret = btrfs_tree_mod_log_insert_key(parent, slot,
4490 BTRFS_MOD_LOG_KEY_REMOVE);
4299 BUG_ON(ret < 0);
4491 if (ret < 0) {
4492 btrfs_abort_transaction(trans, ret);
4493 return ret;
4494 }
4300 }
4301
4302 nritems--;
4303 btrfs_set_header_nritems(parent, nritems);
4304 if (nritems == 0 && parent == root->node) {
4305 BUG_ON(btrfs_header_level(root->node) != 1);
4306 /* just turn the root into a leaf and break */
4307 btrfs_set_header_level(root->node, 0);
4308 } else if (slot == 0) {
4309 struct btrfs_disk_key disk_key;
4310
4311 btrfs_node_key(parent, &disk_key, 0);
4312 fixup_low_keys(path, &disk_key, level + 1);
4313 }
4314 btrfs_mark_buffer_dirty(parent);
4495 }
4496
4497 nritems--;
4498 btrfs_set_header_nritems(parent, nritems);
4499 if (nritems == 0 && parent == root->node) {
4500 BUG_ON(btrfs_header_level(root->node) != 1);
4501 /* just turn the root into a leaf and break */
4502 btrfs_set_header_level(root->node, 0);
4503 } else if (slot == 0) {
4504 struct btrfs_disk_key disk_key;
4505
4506 btrfs_node_key(parent, &disk_key, 0);
4507 fixup_low_keys(path, &disk_key, level + 1);
4508 }
4509 btrfs_mark_buffer_dirty(parent);
4510 return 0;
4315}
4316
4317/*
4318 * a helper function to delete the leaf pointed to by path->slots[1] and
4319 * path->nodes[1].
4320 *
4321 * This deletes the pointer in path->nodes[1] and frees the leaf
4322 * block extent. zero is returned if it all worked out, < 0 otherwise.
4323 *
4324 * The path must have already been setup for deleting the leaf, including
4325 * all the proper balancing. path->nodes[1] must be locked.
4326 */
4511}
4512
4513/*
4514 * a helper function to delete the leaf pointed to by path->slots[1] and
4515 * path->nodes[1].
4516 *
4517 * This deletes the pointer in path->nodes[1] and frees the leaf
4518 * block extent. zero is returned if it all worked out, < 0 otherwise.
4519 *
4520 * The path must have already been setup for deleting the leaf, including
4521 * all the proper balancing. path->nodes[1] must be locked.
4522 */
4327static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans,
4328 struct btrfs_root *root,
4329 struct btrfs_path *path,
4330 struct extent_buffer *leaf)
4523static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
4524 struct btrfs_root *root,
4525 struct btrfs_path *path,
4526 struct extent_buffer *leaf)
4331{
4527{
4528 int ret;
4529
4332 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4530 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4333 del_ptr(root, path, 1, path->slots[1]);
4531 ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]);
4532 if (ret < 0)
4533 return ret;
4334
4335 /*
4336 * btrfs_free_extent is expensive, we want to make sure we
4337 * aren't holding any locks when we call it
4338 */
4339 btrfs_unlock_up_safe(path, 0);
4340
4341 root_sub_used(root, leaf->len);
4342
4343 atomic_inc(&leaf->refs);
4344 btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1);
4345 free_extent_buffer_stale(leaf);
4534
4535 /*
4536 * btrfs_free_extent is expensive, we want to make sure we
4537 * aren't holding any locks when we call it
4538 */
4539 btrfs_unlock_up_safe(path, 0);
4540
4541 root_sub_used(root, leaf->len);
4542
4543 atomic_inc(&leaf->refs);
4544 btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1);
4545 free_extent_buffer_stale(leaf);
4546 return 0;
4346}
4347/*
4348 * delete the item at the leaf level in path. If that empties
4349 * the leaf, remove it from the tree
4350 */
4351int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4352 struct btrfs_path *path, int slot, int nr)
4353{

--- 33 unchanged lines hidden (view full) ---

4387 nritems -= nr;
4388
4389 /* delete the leaf if we've emptied it */
4390 if (nritems == 0) {
4391 if (leaf == root->node) {
4392 btrfs_set_header_level(leaf, 0);
4393 } else {
4394 btrfs_clear_buffer_dirty(trans, leaf);
4547}
4548/*
4549 * delete the item at the leaf level in path. If that empties
4550 * the leaf, remove it from the tree
4551 */
4552int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4553 struct btrfs_path *path, int slot, int nr)
4554{

--- 33 unchanged lines hidden (view full) ---

4588 nritems -= nr;
4589
4590 /* delete the leaf if we've emptied it */
4591 if (nritems == 0) {
4592 if (leaf == root->node) {
4593 btrfs_set_header_level(leaf, 0);
4594 } else {
4595 btrfs_clear_buffer_dirty(trans, leaf);
4395 btrfs_del_leaf(trans, root, path, leaf);
4596 ret = btrfs_del_leaf(trans, root, path, leaf);
4597 if (ret < 0)
4598 return ret;
4396 }
4397 } else {
4398 int used = leaf_space_used(leaf, 0, nritems);
4399 if (slot == 0) {
4400 struct btrfs_disk_key disk_key;
4401
4402 btrfs_item_key(leaf, &disk_key, 0);
4403 fixup_low_keys(path, &disk_key, 1);

--- 7 unchanged lines hidden (view full) ---

4411 * items, or items from other leaves might be moved later into our
4412 * leaf due to deletions on those leaves.
4413 */
4414 if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) {
4415 u32 min_push_space;
4416
4417 /* push_leaf_left fixes the path.
4418 * make sure the path still points to our leaf
4599 }
4600 } else {
4601 int used = leaf_space_used(leaf, 0, nritems);
4602 if (slot == 0) {
4603 struct btrfs_disk_key disk_key;
4604
4605 btrfs_item_key(leaf, &disk_key, 0);
4606 fixup_low_keys(path, &disk_key, 1);

--- 7 unchanged lines hidden (view full) ---

4614 * items, or items from other leaves might be moved later into our
4615 * leaf due to deletions on those leaves.
4616 */
4617 if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) {
4618 u32 min_push_space;
4619
4620 /* push_leaf_left fixes the path.
4621 * make sure the path still points to our leaf
4419 * for possible call to del_ptr below
4622 * for possible call to btrfs_del_ptr below
4420 */
4421 slot = path->slots[1];
4422 atomic_inc(&leaf->refs);
4423 /*
4424 * We want to be able to at least push one item to the
4425 * left neighbour leaf, and that's the first item.
4426 */
4427 min_push_space = sizeof(struct btrfs_item) +

--- 20 unchanged lines hidden (view full) ---

4448 wret = push_leaf_right(trans, root, path, 0,
4449 min_push_space, 1, 0);
4450 if (wret < 0 && wret != -ENOSPC)
4451 ret = wret;
4452 }
4453
4454 if (btrfs_header_nritems(leaf) == 0) {
4455 path->slots[1] = slot;
4623 */
4624 slot = path->slots[1];
4625 atomic_inc(&leaf->refs);
4626 /*
4627 * We want to be able to at least push one item to the
4628 * left neighbour leaf, and that's the first item.
4629 */
4630 min_push_space = sizeof(struct btrfs_item) +

--- 20 unchanged lines hidden (view full) ---

4651 wret = push_leaf_right(trans, root, path, 0,
4652 min_push_space, 1, 0);
4653 if (wret < 0 && wret != -ENOSPC)
4654 ret = wret;
4655 }
4656
4657 if (btrfs_header_nritems(leaf) == 0) {
4658 path->slots[1] = slot;
4456 btrfs_del_leaf(trans, root, path, leaf);
4659 ret = btrfs_del_leaf(trans, root, path, leaf);
4660 if (ret < 0)
4661 return ret;
4457 free_extent_buffer(leaf);
4458 ret = 0;
4459 } else {
4460 /* if we're still in the path, make sure
4461 * we're dirty. Otherwise, one of the
4462 * push_leaf functions must have already
4463 * dirtied this buffer
4464 */

--- 4 unchanged lines hidden (view full) ---

4469 } else {
4470 btrfs_mark_buffer_dirty(leaf);
4471 }
4472 }
4473 return ret;
4474}
4475
4476/*
4662 free_extent_buffer(leaf);
4663 ret = 0;
4664 } else {
4665 /* if we're still in the path, make sure
4666 * we're dirty. Otherwise, one of the
4667 * push_leaf functions must have already
4668 * dirtied this buffer
4669 */

--- 4 unchanged lines hidden (view full) ---

4674 } else {
4675 btrfs_mark_buffer_dirty(leaf);
4676 }
4677 }
4678 return ret;
4679}
4680
4681/*
4477 * search the tree again to find a leaf with lesser keys
4478 * returns 0 if it found something or 1 if there are no lesser leaves.
4479 * returns < 0 on io errors.
4480 *
4481 * This may release the path, and so you may lose any locks held at the
4482 * time you call it.
4483 */
4484int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
4485{
4486 struct btrfs_key key;
4487 struct btrfs_key orig_key;
4488 struct btrfs_disk_key found_key;
4489 int ret;
4490
4491 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
4492 orig_key = key;
4493
4494 if (key.offset > 0) {
4495 key.offset--;
4496 } else if (key.type > 0) {
4497 key.type--;
4498 key.offset = (u64)-1;
4499 } else if (key.objectid > 0) {
4500 key.objectid--;
4501 key.type = (u8)-1;
4502 key.offset = (u64)-1;
4503 } else {
4504 return 1;
4505 }
4506
4507 btrfs_release_path(path);
4508 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4509 if (ret <= 0)
4510 return ret;
4511
4512 /*
4513 * Previous key not found. Even if we were at slot 0 of the leaf we had
4514 * before releasing the path and calling btrfs_search_slot(), we now may
4515 * be in a slot pointing to the same original key - this can happen if
4516 * after we released the path, one of more items were moved from a
4517 * sibling leaf into the front of the leaf we had due to an insertion
4518 * (see push_leaf_right()).
4519 * If we hit this case and our slot is > 0 and just decrement the slot
4520 * so that the caller does not process the same key again, which may or
4521 * may not break the caller, depending on its logic.
4522 */
4523 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
4524 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
4525 ret = comp_keys(&found_key, &orig_key);
4526 if (ret == 0) {
4527 if (path->slots[0] > 0) {
4528 path->slots[0]--;
4529 return 0;
4530 }
4531 /*
4532 * At slot 0, same key as before, it means orig_key is
4533 * the lowest, leftmost, key in the tree. We're done.
4534 */
4535 return 1;
4536 }
4537 }
4538
4539 btrfs_item_key(path->nodes[0], &found_key, 0);
4540 ret = comp_keys(&found_key, &key);
4541 /*
4542 * We might have had an item with the previous key in the tree right
4543 * before we released our path. And after we released our path, that
4544 * item might have been pushed to the first slot (0) of the leaf we
4545 * were holding due to a tree balance. Alternatively, an item with the
4546 * previous key can exist as the only element of a leaf (big fat item).
4547 * Therefore account for these 2 cases, so that our callers (like
4548 * btrfs_previous_item) don't miss an existing item with a key matching
4549 * the previous key we computed above.
4550 */
4551 if (ret <= 0)
4552 return 0;
4553 return 1;
4554}
4555
4556/*
4557 * A helper function to walk down the tree starting at min_key, and looking
4558 * for nodes or leaves that are have a minimum transaction id.
4559 * This is used by the btree defrag code, and tree logging
4560 *
4561 * This does not cow, but it does stuff the starting key it finds back
4562 * into min_key, so you can call btrfs_search_slot with cow=1 on the
4563 * key and get a writable path.
4564 *

--- 497 unchanged lines hidden --- 		4682 * A helper function to walk down the tree starting at min_key, and looking
4683 * for nodes or leaves that are have a minimum transaction id.
4684 * This is used by the btree defrag code, and tree logging
4685 *
4686 * This does not cow, but it does stuff the starting key it finds back
4687 * into min_key, so you can call btrfs_search_slot with cow=1 on the
4688 * key and get a writable path.
4689 *

--- 497 unchanged lines hidden ---