Btrfs: switch to early splits

Signed-off-by: Chris Mason <chris.mason@oracle.com>

1 files changed, 118 insertions, 145 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 2891b582e26f..1b4e82d8074d 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -5,7 +5,12 @@
 #include "ctree.h"
 #include "disk-io.h"
 
+#define SEARCH_READ 0
+#define SEARCH_WRITE 1
+
 static int refill_alloc_extent(struct ctree_root *root);
+int split_node(struct ctree_root *root, struct ctree_path *path, int level);
+int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size);
 
 static inline void init_path(struct ctree_path *p)
 {
@@ -125,14 +130,14 @@ int bin_search(struct node *c, struct key *key, int *slot)
  * If the key isn't found, the path points to the slot where it should
  * be inserted.
  */
-int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p)
+int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p, int ins_len)
 {
         struct tree_buffer *b = root->node;
         struct node *c;
-
         int slot;
         int ret;
         int level;
+
         b->count++;
         while (b) {
                 c = &b->node;
@@ -143,10 +148,26 @@ int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p)
                         if (ret && slot > 0)
                                 slot -= 1;
                         p->slots[level] = slot;
+                        if (ins_len && c->header.nritems == NODEPTRS_PER_BLOCK) {
+                                int sret = split_node(root, p, level);
+                                BUG_ON(sret > 0);
+                                if (sret)
+                                        return sret;
+                                b = p->nodes[level];
+                                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;
+                        if (ins_len && leaf_free_space(l) <  sizeof(struct item) + ins_len) {
+                                int sret = split_leaf(root, p, ins_len);
+                                BUG_ON(sret > 0);
+                                if (sret)
+                                        return sret;
+                        }
                         return ret;
                 }
         }
@@ -331,50 +352,54 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level)
         return 0;
 }
 
+static int insert_new_root(struct ctree_root *root, struct ctree_path *path, int level)
+{
+        struct tree_buffer *t;
+        struct node *lower;
+        struct node *c;
+        struct key *lower_key;
+
+        BUG_ON(path->nodes[level]);
+        BUG_ON(path->nodes[level-1] != root->node);
+
+        t = alloc_free_block(root);
+        c = &t->node;
+        memset(c, 0, sizeof(c));
+        c->header.nritems = 1;
+        c->header.flags = node_level(level);
+        c->header.blocknr = t->blocknr;
+        c->header.parentid = root->node->node.header.parentid;
+        lower = &path->nodes[level-1]->node;
+        if (is_leaf(lower->header.flags))
+                lower_key = &((struct leaf *)lower)->items[0].key;
+        else
+                lower_key = lower->keys;
+        memcpy(c->keys, lower_key, sizeof(struct key));
+        c->blockptrs[0] = path->nodes[level-1]->blocknr;
+        /* the super has an extra ref to root->node */
+        tree_block_release(root, root->node);
+        root->node = t;
+        t->count++;
+        write_tree_block(root, t);
+        path->nodes[level] = t;
+        path->slots[level] = 0;
+        return 0;
+}
+
 /*
  * worker function to insert a single pointer in a node.
  * the node should have enough room for the pointer already
  * slot and level indicate where you want the key to go, and
  * blocknr is the block the key points to.
  */
-int __insert_ptr(struct ctree_root *root,
+int insert_ptr(struct ctree_root *root,
                 struct ctree_path *path, struct key *key,
                 u64 blocknr, int slot, int level)
 {
-        struct node *c;
         struct node *lower;
-        struct key *lower_key;
         int nritems;
-        /* need a new root */
-        if (!path->nodes[level]) {
-                struct tree_buffer *t;
-                t = alloc_free_block(root);
-                c = &t->node;
-                memset(c, 0, sizeof(c));
-                c->header.nritems = 2;
-                c->header.flags = node_level(level);
-                c->header.blocknr = t->blocknr;
-                c->header.parentid = root->node->node.header.parentid;
-                lower = &path->nodes[level-1]->node;
-                if (is_leaf(lower->header.flags))
-                        lower_key = &((struct leaf *)lower)->items[0].key;
-                else
-                        lower_key = lower->keys;
-                memcpy(c->keys, lower_key, sizeof(struct key));
-                memcpy(c->keys + 1, key, sizeof(struct key));
-                c->blockptrs[0] = path->nodes[level-1]->blocknr;
-                c->blockptrs[1] = blocknr;
-                /* the super has an extra ref to root->node */
-                tree_block_release(root, root->node);
-                root->node = t;
-                t->count++;
-                write_tree_block(root, t);
-                path->nodes[level] = t;
-                path->slots[level] = 0;
-                if (c->keys[1].objectid == 0)
-                        BUG();
-                return 0;
-        }
+
+        BUG_ON(!path->nodes[level]);
         lower = &path->nodes[level]->node;
         nritems = lower->header.nritems;
         if (slot > nritems)
@@ -396,93 +421,54 @@ int __insert_ptr(struct ctree_root *root,
         return 0;
 }
 
-
-/*
- * insert a key,blocknr pair into the tree at a given level
- * If the node at that level in the path doesn't have room,
- * it is split or shifted as appropriate.
- */
-int insert_ptr(struct ctree_root *root,
-                struct ctree_path *path, struct key *key,
-                u64 blocknr, int level)
+int split_node(struct ctree_root *root, struct ctree_path *path, int level)
 {
-        struct tree_buffer *t = path->nodes[level];
-        struct node *c = &path->nodes[level]->node;
-        struct node *b;
-        struct tree_buffer *b_buffer;
-        struct tree_buffer *bal[MAX_LEVEL];
-        int bal_level = level;
+        struct tree_buffer *t;
+        struct node *c;
+        struct tree_buffer *split_buffer;
+        struct node *split;
         int mid;
-        int bal_start = -1;
-
-        /*
-         * check to see if we need to make room in the node for this
-         * pointer.  If we do, keep walking the tree, making sure there
-         * is enough room in each level for the required insertions.
-         *
-         * The bal array is filled in with any nodes to be inserted
-         * due to splitting.  Once we've done all the splitting required
-         * do the inserts based on the data in the bal array.
-         */
-        memset(bal, 0, sizeof(bal));
-        while(t && t->node.header.nritems == NODEPTRS_PER_BLOCK) {
-                c = &t->node;
-                if (push_node_left(root, path,
-                   node_level(c->header.flags)) == 0)
-                        break;
-                if (push_node_right(root, path,
-                   node_level(c->header.flags)) == 0)
-                        break;
-                bal_start = bal_level;
-                if (bal_level == MAX_LEVEL - 1)
-                        BUG();
-                b_buffer = alloc_free_block(root);
-                b = &b_buffer->node;
-                b->header.flags = c->header.flags;
-                b->header.blocknr = b_buffer->blocknr;
-                b->header.parentid = root->node->node.header.parentid;
-                mid = (c->header.nritems + 1) / 2;
-                memcpy(b->keys, c->keys + mid,
-                        (c->header.nritems - mid) * sizeof(struct key));
-                memcpy(b->blockptrs, c->blockptrs + mid,
-                        (c->header.nritems - mid) * sizeof(u64));
-                b->header.nritems = c->header.nritems - mid;
-                c->header.nritems = mid;
-
-                write_tree_block(root, t);
-                write_tree_block(root, b_buffer);
+        int ret;
 
-                bal[bal_level] = b_buffer;
-                if (bal_level == MAX_LEVEL - 1)
-                        break;
-                bal_level += 1;
-                t = path->nodes[bal_level];
+        ret = push_node_left(root, path, level);
+        if (!ret)
+                return 0;
+        ret = push_node_right(root, path, level);
+        if (!ret)
+                return 0;
+        t = path->nodes[level];
+        c = &t->node;
+        if (t == root->node) {
+                /* trying to split the root, lets make a new one */
+                ret = insert_new_root(root, path, level + 1);
+                if (ret)
+                        return ret;
         }
-        /*
-         * bal_start tells us the first level in the tree that needed to
-         * be split.  Go through the bal array inserting the new nodes
-         * as needed.  The path is fixed as we go.
-         */
-        while(bal_start > 0) {
-                b_buffer = bal[bal_start];
-                c = &path->nodes[bal_start]->node;
-                __insert_ptr(root, path, b_buffer->node.keys, b_buffer->blocknr,
-                                path->slots[bal_start + 1] + 1, bal_start + 1);
-                if (path->slots[bal_start] >= c->header.nritems) {
-                        path->slots[bal_start] -= c->header.nritems;
-                        tree_block_release(root, path->nodes[bal_start]);
-                        path->nodes[bal_start] = b_buffer;
-                        path->slots[bal_start + 1] += 1;
-                } else {
-                        tree_block_release(root, b_buffer);
-                }
-                bal_start--;
-                if (!bal[bal_start])
-                        break;
+        split_buffer = alloc_free_block(root);
+        split = &split_buffer->node;
+        split->header.flags = c->header.flags;
+        split->header.blocknr = split_buffer->blocknr;
+        split->header.parentid = root->node->node.header.parentid;
+        mid = (c->header.nritems + 1) / 2;
+        memcpy(split->keys, c->keys + mid,
+                (c->header.nritems - mid) * sizeof(struct key));
+        memcpy(split->blockptrs, c->blockptrs + mid,
+                (c->header.nritems - mid) * sizeof(u64));
+        split->header.nritems = c->header.nritems - mid;
+        c->header.nritems = mid;
+        write_tree_block(root, t);
+        write_tree_block(root, split_buffer);
+        insert_ptr(root, path, split->keys, split_buffer->blocknr,
+                     path->slots[level + 1] + 1, level + 1);
+        if (path->slots[level] > mid) {
+                path->slots[level] -= mid;
+                tree_block_release(root, t);
+                path->nodes[level] = split_buffer;
+                path->slots[level + 1] += 1;
+        } else {
+                tree_block_release(root, split_buffer);
         }
-        /* Now that the tree has room, insert the requested pointer */
-        return __insert_ptr(root, path, key, blocknr, path->slots[level] + 1,
-                            level);
+        return 0;
 }
 
 /*
@@ -623,6 +609,11 @@ int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size)
                 if (leaf_free_space(l) >= sizeof(struct item) + data_size)
                         return 0;
         }
+        if (!path->nodes[1]) {
+                ret = insert_new_root(root, path, 1);
+                if (ret)
+                        return ret;
+        }
         slot = path->slots[0];
         nritems = l->header.nritems;
         mid = (nritems + 1)/ 2;
@@ -659,8 +650,7 @@ int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size)
 
         l->header.nritems = mid;
         ret = insert_ptr(root, path, &right->items[0].key,
-                          right_buffer->blocknr, 1);
-
+                          right_buffer->blocknr, path->slots[1] + 1, 1);
         write_tree_block(root, right_buffer);
         write_tree_block(root, l_buf);
 
@@ -695,21 +685,10 @@ int insert_item(struct ctree_root *root, struct key *key,
         refill_alloc_extent(root);
 
         /* create a root if there isn't one */
-        if (!root->node) {
+        if (!root->node)
                 BUG();
-#if 0
-                struct tree_buffer *t;
-                t = alloc_free_block(root);
-                BUG_ON(!t);
-                t->node.header.nritems = 0;
-                t->node.header.flags = node_level(0);
-                t->node.header.blocknr = t->blocknr;
-                root->node = t;
-                write_tree_block(root, t);
-#endif
-        }
         init_path(&path);
-        ret = search_slot(root, key, &path);
+        ret = search_slot(root, key, &path, data_size);
         if (ret == 0) {
                 release_path(root, &path);
                 return -EEXIST;
@@ -719,12 +698,6 @@ int insert_item(struct ctree_root *root, struct key *key,
         leaf_buf = path.nodes[0];
         leaf = &leaf_buf->leaf;
 
-        /* make room if needed */
-        if (leaf_free_space(leaf) <  sizeof(struct item) + data_size) {
-                split_leaf(root, &path, data_size);
-                leaf_buf = path.nodes[0];
-                leaf = &path.nodes[0]->leaf;
-        }
         nritems = leaf->header.nritems;
         data_end = leaf_data_end(leaf);
 
@@ -950,7 +923,7 @@ int alloc_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start,
         ins->offset = 0;
         ins->flags = 0;
 
-        ret = search_slot(root, ins, &path);
+        ret = search_slot(root, ins, &path, sizeof(struct extent_item));
         while (1) {
                 l = &path.nodes[0]->leaf;
                 slot = path.slots[0];
@@ -1097,8 +1070,8 @@ void print_tree(struct ctree_root *root, struct tree_buffer *t)
 
 /* for testing only */
 int next_key(int i, int max_key) {
-        return rand() % max_key;
-        // return i;
+        // return rand() % max_key;
+        return i;
 }
 
 int main() {
@@ -1154,7 +1127,7 @@ int main() {
                 num = next_key(i, max_key);
                 ins.objectid = num;
                 init_path(&path);
-                ret = search_slot(root, &ins, &path);
+                ret = search_slot(root, &ins, &path, 0);
                 if (ret) {
                         print_tree(root, root->node);
                         printf("unable to find %d\n", num);
@@ -1176,7 +1149,7 @@ int main() {
                 num = next_key(i, max_key);
                 ins.objectid = num;
                 init_path(&path);
-                ret = search_slot(root, &ins, &path);
+                ret = search_slot(root, &ins, &path, 0);
                 if (ret)
                         continue;
                 ret = del_item(root, &path);
@@ -1204,7 +1177,7 @@ int main() {
                 num = next_key(i, max_key);
                 ins.objectid = num;
                 init_path(&path);
-                ret = search_slot(root, &ins, &path);
+                ret = search_slot(root, &ins, &path, 0);
                 if (ret) {
                         print_tree(root, root->node);
                         printf("unable to find %d\n", num);
@@ -1218,7 +1191,7 @@ int main() {
                 int slot;
                 ins.objectid = (u64)-1;
                 init_path(&path);
-                ret = search_slot(root, &ins, &path);
+                ret = search_slot(root, &ins, &path, 0);
                 if (ret == 0)
                         BUG();