+static struct btrfs_buffer *read_node_slot(struct btrfs_root *root,
+ struct btrfs_buffer *parent_buf,
+ int slot)
+{
+ struct btrfs_node *node = &parent_buf->node;
+ if (slot < 0)
+ return NULL;
+ if (slot >= btrfs_header_nritems(&node->header))
+ return NULL;
+ return read_tree_block(root, btrfs_node_blockptr(node, slot));
+}
+
+static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
+ *root, struct btrfs_path *path, int level)
+{
+ struct btrfs_buffer *right_buf;
+ struct btrfs_buffer *mid_buf;
+ struct btrfs_buffer *left_buf;
+ struct btrfs_buffer *parent_buf = NULL;
+ struct btrfs_node *right = NULL;
+ struct btrfs_node *mid;
+ struct btrfs_node *left = NULL;
+ struct btrfs_node *parent = NULL;
+ int ret = 0;
+ int wret;
+ int pslot;
+ int orig_slot = path->slots[level];
+ u64 orig_ptr;
+
+ if (level == 0)
+ return 0;
+
+ mid_buf = path->nodes[level];
+ mid = &mid_buf->node;
+ orig_ptr = btrfs_node_blockptr(mid, orig_slot);
+
+ if (level < BTRFS_MAX_LEVEL - 1)
+ parent_buf = path->nodes[level + 1];
+ pslot = path->slots[level + 1];
+
+ /*
+ * deal with the case where there is only one pointer in the root
+ * by promoting the node below to a root
+ */
+ if (!parent_buf) {
+ struct btrfs_buffer *child;
+ u64 blocknr = mid_buf->blocknr;
+
+ if (btrfs_header_nritems(&mid->header) != 1)
+ return 0;
+
+ /* promote the child to a root */
+ child = read_node_slot(root, mid_buf, 0);
+ BUG_ON(!child);
+ root->node = child;
+ path->nodes[level] = NULL;
+ /* once for the path */
+ btrfs_block_release(root, mid_buf);
+ /* once for the root ptr */
+ btrfs_block_release(root, mid_buf);
+ clean_tree_block(trans, root, mid_buf);
+ return btrfs_free_extent(trans, root, blocknr, 1, 1);
+ }
+ parent = &parent_buf->node;
+
+ if (btrfs_header_nritems(&mid->header) >
+ BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
+ return 0;
+
+ left_buf = read_node_slot(root, parent_buf, pslot - 1);
+ right_buf = read_node_slot(root, parent_buf, pslot + 1);
+
+ /* first, try to make some room in the middle buffer */
+ if (left_buf) {
+ btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1,
+ &left_buf);
+ left = &left_buf->node;
+ orig_slot += btrfs_header_nritems(&left->header);
+ wret = push_node_left(trans, root, left_buf, mid_buf);
+ if (wret < 0)
+ ret = wret;
+ }
+
+ /*
+ * then try to empty the right most buffer into the middle
+ */
+ if (right_buf) {
+ btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1,
+ &right_buf);
+ right = &right_buf->node;
+ wret = push_node_left(trans, root, mid_buf, right_buf);
+ if (wret < 0)
+ ret = wret;
+ if (btrfs_header_nritems(&right->header) == 0) {
+ u64 blocknr = right_buf->blocknr;
+ btrfs_block_release(root, right_buf);
+ clean_tree_block(trans, root, right_buf);
+ right_buf = NULL;
+ right = NULL;
+ wret = del_ptr(trans, root, path, level + 1, pslot +
+ 1);
+ if (wret)
+ ret = wret;
+ wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
+ if (wret)
+ ret = wret;
+ } else {
+ memcpy(&parent->ptrs[pslot + 1].key,
+ &right->ptrs[0].key,
+ sizeof(struct btrfs_disk_key));
+ BUG_ON(list_empty(&parent_buf->dirty));
+ }
+ }
+ if (btrfs_header_nritems(&mid->header) == 1) {
+ /*
+ * we're not allowed to leave a node with one item in the
+ * tree during a delete. A deletion from lower in the tree
+ * could try to delete the only pointer in this node.
+ * So, pull some keys from the left.
+ * There has to be a left pointer at this point because
+ * otherwise we would have pulled some pointers from the
+ * right
+ */
+ BUG_ON(!left_buf);
+ wret = balance_node_right(trans, root, mid_buf, left_buf);
+ if (wret < 0)
+ ret = wret;
+ BUG_ON(wret == 1);
+ }
+ if (btrfs_header_nritems(&mid->header) == 0) {
+ /* we've managed to empty the middle node, drop it */
+ u64 blocknr = mid_buf->blocknr;
+ btrfs_block_release(root, mid_buf);
+ clean_tree_block(trans, root, mid_buf);
+ mid_buf = NULL;
+ mid = NULL;
+ wret = del_ptr(trans, root, path, level + 1, pslot);
+ if (wret)
+ ret = wret;
+ wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
+ if (wret)
+ ret = wret;
+ } else {
+ /* update the parent key to reflect our changes */
+ memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key,
+ sizeof(struct btrfs_disk_key));
+ BUG_ON(list_empty(&parent_buf->dirty));
+ }
+
+ /* update the path */
+ if (left_buf) {
+ if (btrfs_header_nritems(&left->header) > orig_slot) {
+ left_buf->count++; // released below
+ path->nodes[level] = left_buf;
+ path->slots[level + 1] -= 1;
+ path->slots[level] = orig_slot;
+ if (mid_buf)
+ btrfs_block_release(root, mid_buf);
+ } else {
+ orig_slot -= btrfs_header_nritems(&left->header);
+ path->slots[level] = orig_slot;
+ }
+ }
+ /* double check we haven't messed things up */
+ check_block(root, path, level);
+ if (orig_ptr != btrfs_node_blockptr(&path->nodes[level]->node,
+ path->slots[level]))
+ BUG();
+
+ if (right_buf)
+ btrfs_block_release(root, right_buf);
+ if (left_buf)
+ btrfs_block_release(root, left_buf);
+ return ret;
+}
+