Btrfs: Faster deletes, add Makefile and kerncompat

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

1 files changed, 61 insertions, 21 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 893fd56960a0..4bf5e92584bd 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -615,9 +615,9 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level)
                         if (node->header.nritems) {
                                 push_node_right(root, path, level);
                         }
-                        path->slots[level+1] = tslot;
                         if (node->header.nritems)
                                 break;
+                        path->slots[level+1] = tslot;
                 }
                 if (node == root->node) {
                         printf("root is now null!\n");
@@ -632,22 +632,15 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level)
         return 0;
 }
 
-int del_item(struct ctree_root *root, struct key *key)
+int del_item(struct ctree_root *root, struct ctree_path *path)
 {
-        int ret;
         int slot;
         struct leaf *leaf;
-        struct ctree_path path;
         int doff;
         int dsize;
 
-        init_path(&path);
-        ret = search_slot(root, key, &path);
-        if (ret != 0)
-                return -1;
-
-        leaf = (struct leaf *)path.nodes[0];
-        slot = path.slots[0];
+        leaf = (struct leaf *)path->nodes[0];
+        slot = path->slots[0];
         doff = leaf->items[slot].offset;
         dsize = leaf->items[slot].size;
 
@@ -665,23 +658,26 @@ int del_item(struct ctree_root *root, struct key *key)
         }
         leaf->header.nritems -= 1;
         if (leaf->header.nritems == 0) {
+                if (leaf == (struct leaf *)root->node)
+                        root->node = NULL;
+                else
+                        del_ptr(root, path, 1);
                 free(leaf);
-                del_ptr(root, &path, 1);
         } else {
                 if (slot == 0)
-                        fixup_low_keys(&path, &leaf->items[0].key, 1);
+                        fixup_low_keys(path, &leaf->items[0].key, 1);
                 if (leaf_space_used(leaf, 0, leaf->header.nritems) <
                     LEAF_DATA_SIZE / 4) {
                         /* push_leaf_left fixes the path.
                          * make sure the path still points to our leaf
                          * for possible call to del_ptr below
                          */
-                        slot = path.slots[1];
-                        push_leaf_left(root, &path, 1);
-                        path.slots[1] = slot;
+                        slot = path->slots[1];
+                        push_leaf_left(root, path, 1);
                         if (leaf->header.nritems == 0) {
                                 free(leaf);
-                                del_ptr(root, &path, 1);
+                                path->slots[1] = slot;
+                                del_ptr(root, path, 1);
                         }
                 }
         }
@@ -753,11 +749,12 @@ int main() {
         struct leaf *first_node = malloc(sizeof(struct leaf));
         struct ctree_root root;
         struct key ins;
+        struct key last = { (u64)-1, 0, 0};
         char *buf;
         int i;
         int num;
         int ret;
-        int run_size = 10000000;
+        int run_size = 100000;
         int max_key = 100000000;
         int tree_size = 0;
         struct ctree_path path;
@@ -783,8 +780,6 @@ int main() {
         for (i = 0; i < run_size; i++) {
                 num = next_key(i, max_key);
                 ins.objectid = num;
-                ins.offset = 0;
-                ins.flags = 0;
                 init_path(&path);
                 ret = search_slot(&root, &ins, &path);
                 if (ret) {
@@ -800,11 +795,56 @@ int main() {
         printf("all searches good\n");
         i = 0;
         srand(55);
+        for (i = 0 ; i < run_size/4; i++) {
+                num = next_key(i, max_key);
+                ins.objectid = num;
+                init_path(&path);
+                ret = search_slot(&root, &ins, &path);
+                if (ret)
+                        continue;
+                ret = del_item(&root, &path);
+                if (ret != 0)
+                        BUG();
+                tree_size--;
+        }
+        srand(128);
         for (i = 0; i < run_size; i++) {
+                buf = malloc(64);
                 num = next_key(i, max_key);
+                sprintf(buf, "string-%d", num);
                 ins.objectid = num;
-                del_item(&root, &ins);
+                ret = insert_item(&root, &ins, buf, strlen(buf));
+                if (!ret)
+                        tree_size++;
+        }
+        while(root.node) {
+                struct leaf *leaf;
+                int slot;
+                ins.objectid = (u64)-1;
+                init_path(&path);
+                ret = search_slot(&root, &ins, &path);
+                if (ret == 0)
+                        BUG();
+
+                leaf = (struct leaf *)(path.nodes[0]);
+                slot = path.slots[0];
+                if (slot != leaf->header.nritems)
+                        BUG();
+                while(path.slots[0] > 0) {
+                        path.slots[0] -= 1;
+                        slot = path.slots[0];
+                        leaf = (struct leaf *)(path.nodes[0]);
+
+                        if (comp_keys(&last, &leaf->items[slot].key) <= 0)
+                                BUG();
+                        memcpy(&last, &leaf->items[slot].key, sizeof(last));
+                        ret = del_item(&root, &path);
+                        if (ret != 0)
+                                BUG();
+                        tree_size--;
+                }
         }
         print_tree(root.node);
+        printf("tree size is now %d\n", tree_size);
         return 0;
 }