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 893fd56960a..4bf5e92584b 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;
 }