diff options
| -rw-r--r-- | fs/btrfs/ctree.c | 420 |
1 files changed, 200 insertions, 220 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 273239932255..df4a19d65206 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c @@ -10,11 +10,10 @@ static int split_node(struct ctree_root *root, struct ctree_path *path, int level); static int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size); -static int push_node_left(struct ctree_root *root, struct ctree_path *path, - int level); -static int push_node_right(struct ctree_root *root, - struct ctree_path *path, int level); -static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level); +static int push_node_left(struct ctree_root *root, struct tree_buffer *dst, + struct tree_buffer *src); +static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, + int slot); inline void init_path(struct ctree_path *p) { @@ -192,6 +191,138 @@ int bin_search(struct node *c, struct key *key, int *slot) return -1; } +struct tree_buffer *read_node_slot(struct ctree_root *root, + struct tree_buffer *parent_buf, + int slot) +{ + struct node *node = &parent_buf->node; + if (slot < 0) + return NULL; + if (slot >= node->header.nritems) + return NULL; + return read_tree_block(root, node->blockptrs[slot]); +} + +static int balance_level(struct ctree_root *root, struct ctree_path *path, + int level) +{ + struct tree_buffer *right_buf; + struct tree_buffer *mid_buf; + struct tree_buffer *left_buf; + struct tree_buffer *parent_buf = NULL; + struct node *right = NULL; + struct node *mid; + struct node *left = NULL; + struct node *parent = NULL; + int ret = 0; + int wret; + int pslot; + int used = 0; + int count; + int orig_slot = path->slots[level]; + + if (level == 0) + return 0; + + mid_buf = path->nodes[level]; + mid = &mid_buf->node; + if (level < MAX_LEVEL - 1) + parent_buf = path->nodes[level + 1]; + pslot = path->slots[level + 1]; + + if (!parent_buf) { + struct tree_buffer *child; + u64 blocknr = mid_buf->blocknr; + + if (mid->header.nritems != 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 */ + tree_block_release(root, mid_buf); + /* once for the root ptr */ + tree_block_release(root, mid_buf); + return free_extent(root, blocknr, 1); + } + parent = &parent_buf->node; + + if (mid->header.nritems > NODEPTRS_PER_BLOCK / 4) + return 0; + + // print_tree(root, root->node); + left_buf = read_node_slot(root, parent_buf, pslot - 1); + right_buf = read_node_slot(root, parent_buf, pslot + 1); + if (right_buf) { + right = &right_buf->node; + used = right->header.nritems; + count = 1; + } + if (left_buf) { + left = &left_buf->node; + used += left->header.nritems; + orig_slot += left->header.nritems; + count++; + } + if (left_buf) + push_node_left(root, left_buf, mid_buf); + if (right_buf) { + push_node_left(root, mid_buf, right_buf); + if (right->header.nritems == 0) { + u64 blocknr = right_buf->blocknr; + tree_block_release(root, right_buf); + right_buf = NULL; + right = NULL; + wret = del_ptr(root, path, level + 1, pslot + 1); + if (wret) + ret = wret; + wret = free_extent(root, blocknr, 1); + if (wret) + ret = wret; + } else { + memcpy(parent->keys + pslot + 1, right->keys, + sizeof(struct key)); + } + } + if (mid->header.nritems == 0) { + u64 blocknr = mid_buf->blocknr; + tree_block_release(root, mid_buf); + mid_buf = NULL; + mid = NULL; + wret = del_ptr(root, path, level + 1, pslot); + if (wret) + ret = wret; + wret = free_extent(root, blocknr, 1); + if (wret) + ret = wret; + } else + memcpy(parent->keys + pslot, mid->keys, sizeof(struct key)); + + if (left_buf) { + if (left->header.nritems >= 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) + tree_block_release(root, mid_buf); + } else { + orig_slot -= left->header.nritems; + path->slots[level] = orig_slot; + } + } + + if (right_buf) + tree_block_release(root, right_buf); + if (left_buf) + tree_block_release(root, left_buf); + + return ret; +} + /* * look for key in the tree. path is filled in with nodes along the way * if key is found, we return zero and you can find the item in the leaf @@ -208,12 +339,14 @@ int bin_search(struct node *c, struct key *key, int *slot) int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p, int ins_len) { - struct tree_buffer *b = root->node; + struct tree_buffer *b; struct node *c; int slot; int ret; int level; +again: + b = root->node; b->count++; while (b) { c = &b->node; @@ -236,9 +369,17 @@ int search_slot(struct ctree_root *root, struct key *key, b = p->nodes[level]; c = &b->node; slot = p->slots[level]; + } else if (ins_len < 0) { + int sret = balance_level(root, p, level); + if (sret) + return sret; + b = p->nodes[level]; + if (!b) + goto again; + c = &b->node; + slot = p->slots[level]; } b = read_tree_block(root, c->blockptrs[slot]); - continue; } else { struct leaf *l = (struct leaf *)c; p->slots[level] = slot; @@ -249,9 +390,11 @@ int search_slot(struct ctree_root *root, struct key *key, if (sret) return sret; } + BUG_ON(root->node->count == 1); return ret; } } + BUG_ON(root->node->count == 1); return 1; } @@ -301,164 +444,50 @@ static int fixup_low_keys(struct ctree_root *root, * returns 0 if some ptrs were pushed left, < 0 if there was some horrible * error, and > 0 if there was no room in the left hand block. */ -static int push_node_left(struct ctree_root *root, struct ctree_path *path, - int level) +static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, + struct tree_buffer *src_buf) { - int slot; - struct node *left; - struct node *right; + struct node *src = &src_buf->node; + struct node *dst = &dst_buf->node; int push_items = 0; - int left_nritems; - int right_nritems; - struct tree_buffer *t; - struct tree_buffer *right_buf; + int src_nritems; + int dst_nritems; int ret = 0; int wret; - if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) - return 1; - slot = path->slots[level + 1]; - if (slot == 0) - return 1; - - t = read_tree_block(root, - path->nodes[level + 1]->node.blockptrs[slot - 1]); - left = &t->node; - right_buf = path->nodes[level]; - right = &right_buf->node; - left_nritems = left->header.nritems; - right_nritems = right->header.nritems; - push_items = NODEPTRS_PER_BLOCK - (left_nritems + 1); + src_nritems = src->header.nritems; + dst_nritems = dst->header.nritems; + push_items = NODEPTRS_PER_BLOCK - dst_nritems; if (push_items <= 0) { - tree_block_release(root, t); return 1; } - if (right_nritems < push_items) - push_items = right_nritems; - memcpy(left->keys + left_nritems, right->keys, + if (src_nritems < push_items) + push_items =src_nritems; + memcpy(dst->keys + dst_nritems, src->keys, push_items * sizeof(struct key)); - memcpy(left->blockptrs + left_nritems, right->blockptrs, + memcpy(dst->blockptrs + dst_nritems, src->blockptrs, push_items * sizeof(u64)); - memmove(right->keys, right->keys + push_items, - (right_nritems - push_items) * sizeof(struct key)); - memmove(right->blockptrs, right->blockptrs + push_items, - (right_nritems - push_items) * sizeof(u64)); - right->header.nritems -= push_items; - left->header.nritems += push_items; - - /* adjust the pointers going up the tree */ - wret = fixup_low_keys(root, path, right->keys, level + 1); - if (wret < 0) - ret = wret; + if (push_items < src_nritems) { + memmove(src->keys, src->keys + push_items, + (src_nritems - push_items) * sizeof(struct key)); + memmove(src->blockptrs, src->blockptrs + push_items, + (src_nritems - push_items) * sizeof(u64)); + } + src->header.nritems -= push_items; + dst->header.nritems += push_items; - wret = write_tree_block(root, t); + wret = write_tree_block(root, src_buf); if (wret < 0) ret = wret; - wret = write_tree_block(root, right_buf); + wret = write_tree_block(root, dst_buf); if (wret < 0) ret = wret; - - /* then fixup the leaf pointer in the path */ - if (path->slots[level] < push_items) { - path->slots[level] += left_nritems; - tree_block_release(root, path->nodes[level]); - path->nodes[level] = t; - path->slots[level + 1] -= 1; - } else { - path->slots[level] -= push_items; - tree_block_release(root, t); - } return ret; } /* - * try to push data from one node into the next node right in the - * tree. The src node is found at specified level in the path. - * If some bytes were pushed, return 0, otherwise return 1. - * - * Lower nodes/leaves in the path are not touched, higher nodes may - * be modified to reflect the push. - * - * The path is altered to reflect the push. - * - * returns 0 if some ptrs were pushed, < 0 if there was some horrible - * error, and > 0 if there was no room in the right hand block. - */ -static int push_node_right(struct ctree_root *root, struct ctree_path *path, - int level) -{ - int slot; - struct tree_buffer *t; - struct tree_buffer *src_buffer; - struct node *dst; - struct node *src; - int push_items = 0; - int dst_nritems; - int src_nritems; - - /* can't push from the root */ - if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) - return 1; - - /* only try to push inside the node higher up */ - slot = path->slots[level + 1]; - if (slot == NODEPTRS_PER_BLOCK - 1) - return 1; - - if (slot >= path->nodes[level + 1]->node.header.nritems -1) - return 1; - - t = read_tree_block(root, - path->nodes[level + 1]->node.blockptrs[slot + 1]); - dst = &t->node; - src_buffer = path->nodes[level]; - src = &src_buffer->node; - dst_nritems = dst->header.nritems; - src_nritems = src->header.nritems; - push_items = NODEPTRS_PER_BLOCK - (dst_nritems + 1); - if (push_items <= 0) { - tree_block_release(root, t); - return 1; - } - - if (src_nritems < push_items) - push_items = src_nritems; - memmove(dst->keys + push_items, dst->keys, - dst_nritems * sizeof(struct key)); - memcpy(dst->keys, src->keys + src_nritems - push_items, - push_items * sizeof(struct key)); - - memmove(dst->blockptrs + push_items, dst->blockptrs, - dst_nritems * sizeof(u64)); - memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, - push_items * sizeof(u64)); - - src->header.nritems -= push_items; - dst->header.nritems += push_items; - - /* adjust the pointers going up the tree */ - memcpy(path->nodes[level + 1]->node.keys + path->slots[level + 1] + 1, - dst->keys, sizeof(struct key)); - - write_tree_block(root, path->nodes[level + 1]); - write_tree_block(root, t); - write_tree_block(root, src_buffer); - - /* then fixup the pointers in the path */ - if (path->slots[level] >= src->header.nritems) { - path->slots[level] -= src->header.nritems; - tree_block_release(root, path->nodes[level]); - path->nodes[level] = t; - path->slots[level + 1] += 1; - } else { - tree_block_release(root, t); - } - return 0; -} - -/* * helper function to insert a new root level in the tree. * A new node is allocated, and a single item is inserted to * point to the existing root @@ -558,16 +587,6 @@ static int split_node(struct ctree_root *root, struct ctree_path *path, int ret; int wret; - ret = push_node_left(root, path, level); - if (!ret) - return 0; - if (ret < 0) - return ret; - ret = push_node_right(root, path, level); - if (!ret) - return 0; - if (ret < 0) - return ret; t = path->nodes[level]; c = &t->node; if (t == root->node) { @@ -1011,6 +1030,7 @@ int insert_item(struct ctree_root *root, struct key *key, if (leaf_free_space(leaf) < 0) BUG(); + check_leaf(&path, 0); release_path(root, &path); return ret; } @@ -1022,77 +1042,38 @@ int insert_item(struct ctree_root *root, struct key *key, * continuing all the way the root if required. The root is converted into * a leaf if all the nodes are emptied. */ -static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) +static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, + int slot) { - int slot; - struct tree_buffer *t; struct node *node; + struct tree_buffer *parent = path->nodes[level]; int nritems; - u64 blocknr; - int wret; int ret = 0; + int wret; - while(1) { - t = path->nodes[level]; - if (!t) - break; - node = &t->node; - slot = path->slots[level]; - nritems = node->header.nritems; - - if (slot != nritems -1) { - memmove(node->keys + slot, node->keys + slot + 1, - sizeof(struct key) * (nritems - slot - 1)); - memmove(node->blockptrs + slot, - node->blockptrs + slot + 1, - sizeof(u64) * (nritems - slot - 1)); - } - node->header.nritems--; - blocknr = t->blocknr; - write_tree_block(root, t); - if (node->header.nritems != 0) { - int tslot; - if (slot == 0) { - wret = fixup_low_keys(root, path, - node->keys, - level + 1); - if (wret) - ret = wret; - } - tslot = path->slots[level + 1]; - t->count++; - wret = push_node_left(root, path, level); - if (wret < 0) { - ret = wret; - break; - } - if (node->header.nritems != 0) { - wret = push_node_right(root, path, level); - if (wret < 0) { - ret = wret; - break; - } - } - path->slots[level + 1] = tslot; - if (node->header.nritems != 0) { - tree_block_release(root, t); - break; - } - tree_block_release(root, t); - } - if (t == root->node) { - /* just turn the root into a leaf and break */ - root->node->node.header.flags = node_level(0); - write_tree_block(root, t); - break; - } - level++; - wret = free_extent(root, blocknr, 1); + node = &parent->node; + nritems = node->header.nritems; + + if (slot != nritems -1) { + memmove(node->keys + slot, node->keys + slot + 1, + sizeof(struct key) * (nritems - slot - 1)); + memmove(node->blockptrs + slot, + node->blockptrs + slot + 1, + sizeof(u64) * (nritems - slot - 1)); + } + node->header.nritems--; + if (node->header.nritems == 0 && parent == root->node) { + BUG_ON(node_level(root->node->node.header.flags) != 1); + /* just turn the root into a leaf and break */ + root->node->node.header.flags = node_level(0); + } else if (slot == 0) { + wret = fixup_low_keys(root, path, node->keys, level + 1); if (wret) ret = wret; - if (!path->nodes[level]) - BUG(); } + wret = write_tree_block(root, parent); + if (wret) + ret = wret; return ret; } @@ -1135,7 +1116,7 @@ int del_item(struct ctree_root *root, struct ctree_path *path) leaf->header.flags = node_level(0); write_tree_block(root, leaf_buf); } else { - wret = del_ptr(root, path, 1); + wret = del_ptr(root, path, 1, path->slots[1]); if (wret) ret = wret; wret = free_extent(root, leaf_buf->blocknr, 1); @@ -1172,8 +1153,7 @@ int del_item(struct ctree_root *root, struct ctree_path *path) } if (leaf->header.nritems == 0) { u64 blocknr = leaf_buf->blocknr; - path->slots[1] = slot; - wret = del_ptr(root, path, 1); + wret = del_ptr(root, path, 1, slot); if (wret) ret = wret; tree_block_release(root, leaf_buf); |