diff options
| -rw-r--r-- | fs/btrfs/Makefile | 5 | ||||
| -rw-r--r-- | fs/btrfs/ctree.c | 137 | ||||
| -rw-r--r-- | fs/btrfs/quick-test.c | 165 | ||||
| -rw-r--r-- | fs/btrfs/random-test.c | 117 |
4 files changed, 381 insertions, 43 deletions
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile index 58d4260a04b2..756b1cd4cf4d 100644 --- a/fs/btrfs/Makefile +++ b/fs/btrfs/Makefile @@ -14,7 +14,7 @@ check=sparse $(CHECKFLAGS) $(check) $< $(CC) $(CFLAGS) -c $< -all: tester debug-tree +all: tester debug-tree quick-test debug-tree: $(objects) debug-tree.o gcc $(CFLAGS) -o debug-tree $(objects) debug-tree.o @@ -22,6 +22,9 @@ debug-tree: $(objects) debug-tree.o tester: $(objects) random-test.o gcc $(CFLAGS) -o tester $(objects) random-test.o +quick-test: $(objects) quick-test.o + gcc $(CFLAGS) -o quick-test $(objects) quick-test.o + $(objects) : $(headers) clean : diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index df4a19d65206..afa5bc5c7c1a 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c @@ -12,6 +12,9 @@ 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 tree_buffer *dst, struct tree_buffer *src); +static int balance_node_right(struct ctree_root *root, + struct tree_buffer *dst_buf, + struct tree_buffer *src_buf); static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, int slot); @@ -217,15 +220,16 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, int ret = 0; int wret; int pslot; - int used = 0; - int count; 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 = mid->blockptrs[orig_slot]; + if (level < MAX_LEVEL - 1) parent_buf = path->nodes[level + 1]; pslot = path->slots[level + 1]; @@ -253,24 +257,26 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, 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; - } + + /* first, try to make some room in the middle buffer */ if (left_buf) { left = &left_buf->node; - used += left->header.nritems; orig_slot += left->header.nritems; - count++; + wret = push_node_left(root, left_buf, mid_buf); + if (wret < 0) + ret = wret; } - if (left_buf) - push_node_left(root, left_buf, mid_buf); + + /* + * then try to empty the right most buffer into the middle + */ if (right_buf) { - push_node_left(root, mid_buf, right_buf); + right = &right_buf->node; + wret = push_node_left(root, mid_buf, right_buf); + if (wret < 0) + ret = wret; if (right->header.nritems == 0) { u64 blocknr = right_buf->blocknr; tree_block_release(root, right_buf); @@ -285,9 +291,29 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, } else { memcpy(parent->keys + pslot + 1, right->keys, sizeof(struct key)); + wret = write_tree_block(root, parent_buf); + if (wret) + ret = wret; } } + if (mid->header.nritems == 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(root, mid_buf, left_buf); + if (wret < 0) + ret = wret; + BUG_ON(wret == 1); + } if (mid->header.nritems == 0) { + /* we've managed to empty the middle node, drop it */ u64 blocknr = mid_buf->blocknr; tree_block_release(root, mid_buf); mid_buf = NULL; @@ -298,11 +324,17 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, wret = free_extent(root, blocknr, 1); if (wret) ret = wret; - } else + } else { + /* update the parent key to reflect our changes */ memcpy(parent->keys + pslot, mid->keys, sizeof(struct key)); + wret = write_tree_block(root, parent_buf); + if (wret) + ret = wret; + } + /* update the path */ if (left_buf) { - if (left->header.nritems >= orig_slot) { + if (left->header.nritems > orig_slot) { left_buf->count++; // released below path->nodes[level] = left_buf; path->slots[level + 1] -= 1; @@ -314,12 +346,15 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, path->slots[level] = orig_slot; } } + /* double check we haven't messed things up */ + check_block(path, level); + if (orig_ptr != path->nodes[level]->node.blockptrs[path->slots[level]]) + BUG(); if (right_buf) tree_block_release(root, right_buf); if (left_buf) tree_block_release(root, left_buf); - return ret; } @@ -378,6 +413,7 @@ again: goto again; c = &b->node; slot = p->slots[level]; + BUG_ON(c->header.nritems == 1); } b = read_tree_block(root, c->blockptrs[slot]); } else { @@ -433,13 +469,7 @@ static int fixup_low_keys(struct ctree_root *root, /* * try to push data from one node into the next node left 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. + * tree. * * 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. @@ -463,7 +493,8 @@ static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, } if (src_nritems < push_items) - push_items =src_nritems; + push_items = src_nritems; + memcpy(dst->keys + dst_nritems, src->keys, push_items * sizeof(struct key)); memcpy(dst->blockptrs + dst_nritems, src->blockptrs, @@ -488,6 +519,64 @@ static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, } /* + * try to push data from one node into the next node right in the + * tree. + * + * 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. + * + * this will only push up to 1/2 the contents of the left node over + */ +static int balance_node_right(struct ctree_root *root, + struct tree_buffer *dst_buf, + struct tree_buffer *src_buf) +{ + struct node *src = &src_buf->node; + struct node *dst = &dst_buf->node; + int push_items = 0; + int max_push; + int src_nritems; + int dst_nritems; + int ret = 0; + int wret; + + src_nritems = src->header.nritems; + dst_nritems = dst->header.nritems; + push_items = NODEPTRS_PER_BLOCK - dst_nritems; + if (push_items <= 0) { + return 1; + } + + max_push = src_nritems / 2 + 1; + /* don't try to empty the node */ + if (max_push > src_nritems) + return 1; + if (max_push < push_items) + push_items = max_push; + + memmove(dst->keys + push_items, dst->keys, + dst_nritems * sizeof(struct key)); + memmove(dst->blockptrs + push_items, dst->blockptrs, + dst_nritems * sizeof(u64)); + memcpy(dst->keys, src->keys + src_nritems - push_items, + push_items * sizeof(struct key)); + memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, + push_items * sizeof(u64)); + + src->header.nritems -= push_items; + dst->header.nritems += push_items; + + wret = write_tree_block(root, src_buf); + if (wret < 0) + ret = wret; + + wret = write_tree_block(root, dst_buf); + if (wret < 0) + ret = wret; + return ret; +} + +/* * 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 diff --git a/fs/btrfs/quick-test.c b/fs/btrfs/quick-test.c new file mode 100644 index 000000000000..dbd00c3b7ab4 --- /dev/null +++ b/fs/btrfs/quick-test.c @@ -0,0 +1,165 @@ +#include <stdio.h> +#include <stdlib.h> +#include "kerncompat.h" +#include "radix-tree.h" +#include "ctree.h" +#include "disk-io.h" +#include "print-tree.h" + +/* for testing only */ +int next_key(int i, int max_key) { + return rand() % max_key; + //return i; +} + +int main(int ac, char **av) { + struct key ins; + struct key last = { (u64)-1, 0, 0}; + char *buf; + int i; + int num; + int ret; + int run_size = 100000; + int max_key = 100000000; + int tree_size = 0; + struct ctree_path path; + struct ctree_super_block super; + struct ctree_root *root; + + radix_tree_init(); + + root = open_ctree("dbfile", &super); + srand(55); + for (i = 0; i < run_size; i++) { + buf = malloc(64); + num = next_key(i, max_key); + // num = i; + sprintf(buf, "string-%d", num); + if (i % 10000 == 0) + fprintf(stderr, "insert %d:%d\n", num, i); + ins.objectid = num; + ins.offset = 0; + ins.flags = 0; + ret = insert_item(root, &ins, buf, strlen(buf)); + if (!ret) + tree_size++; + free(buf); + } + write_ctree_super(root, &super); + close_ctree(root); + + root = open_ctree("dbfile", &super); + printf("starting search\n"); + srand(55); + for (i = 0; i < run_size; i++) { + num = next_key(i, max_key); + ins.objectid = num; + init_path(&path); + if (i % 10000 == 0) + fprintf(stderr, "search %d:%d\n", num, i); + ret = search_slot(root, &ins, &path, 0); + if (ret) { + print_tree(root, root->node); + printf("unable to find %d\n", num); + exit(1); + } + release_path(root, &path); + } + write_ctree_super(root, &super); + close_ctree(root); + root = open_ctree("dbfile", &super); + printf("node %p level %d total ptrs %d free spc %lu\n", root->node, + node_level(root->node->node.header.flags), + root->node->node.header.nritems, + NODEPTRS_PER_BLOCK - root->node->node.header.nritems); + printf("all searches good, deleting some items\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, -1); + if (!ret) { + if (i % 10000 == 0) + fprintf(stderr, "del %d:%d\n", num, i); + ret = del_item(root, &path); + if (ret != 0) + BUG(); + tree_size--; + } + release_path(root, &path); + } + write_ctree_super(root, &super); + close_ctree(root); + root = open_ctree("dbfile", &super); + 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; + if (i % 10000 == 0) + fprintf(stderr, "insert %d:%d\n", num, i); + ret = insert_item(root, &ins, buf, strlen(buf)); + if (!ret) + tree_size++; + free(buf); + } + write_ctree_super(root, &super); + close_ctree(root); + root = open_ctree("dbfile", &super); + srand(128); + printf("starting search2\n"); + for (i = 0; i < run_size; i++) { + num = next_key(i, max_key); + ins.objectid = num; + init_path(&path); + if (i % 10000 == 0) + fprintf(stderr, "search %d:%d\n", num, i); + ret = search_slot(root, &ins, &path, 0); + if (ret) { + print_tree(root, root->node); + printf("unable to find %d\n", num); + exit(1); + } + release_path(root, &path); + } + printf("starting big long delete run\n"); + while(root->node && root->node->node.header.nritems > 0) { + struct leaf *leaf; + int slot; + ins.objectid = (u64)-1; + init_path(&path); + ret = search_slot(root, &ins, &path, -1); + if (ret == 0) + BUG(); + + leaf = &path.nodes[0]->leaf; + slot = path.slots[0]; + if (slot != leaf->header.nritems) + BUG(); + while(path.slots[0] > 0) { + path.slots[0] -= 1; + slot = path.slots[0]; + leaf = &path.nodes[0]->leaf; + + memcpy(&last, &leaf->items[slot].key, sizeof(last)); + if (tree_size % 10000 == 0) + printf("big del %d:%d\n", tree_size, i); + ret = del_item(root, &path); + if (ret != 0) { + printf("del_item returned %d\n", ret); + BUG(); + } + tree_size--; + } + release_path(root, &path); + } + printf("tree size is now %d\n", tree_size); + printf("map tree\n"); + print_tree(root->extent_root, root->extent_root->node); + write_ctree_super(root, &super); + close_ctree(root); + return 0; +} diff --git a/fs/btrfs/random-test.c b/fs/btrfs/random-test.c index cebaf6483927..bbd554e88db2 100644 --- a/fs/btrfs/random-test.c +++ b/fs/btrfs/random-test.c @@ -142,8 +142,98 @@ error: return -1; } +static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix, + int nr) +{ + struct ctree_path path; + struct key key; + unsigned long found = 0; + int ret; + int slot; + int *ptr; + int count = 0; + + key.offset = 0; + key.flags = 0; + key.objectid = (unsigned long)-1; + while(nr-- >= 0) { + init_path(&path); + ret = search_slot(root, &key, &path, -1); + if (ret < 0) { + release_path(root, &path); + return ret; + } + if (ret != 0) { + if (path.slots[0] == 0) { + release_path(root, &path); + break; + } + path.slots[0] -= 1; + } + slot = path.slots[0]; + found = path.nodes[0]->leaf.items[slot].key.objectid; + ret = del_item(root, &path); + count++; + if (ret) { + fprintf(stderr, + "failed to remove %lu from tree\n", + found); + return -1; + } + release_path(root, &path); + ptr = radix_tree_delete(radix, found); + if (!ptr) + goto error; + if (!keep_running) + break; + } + return 0; +error: + fprintf(stderr, "failed to delete from the radix %lu\n", found); + return -1; +} + +static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix, + int count) +{ + int i; + int err; + int ret = 0; + for (i = 0; i < count; i++) { + ret = ins_one(root, radix); + if (ret) { + printf("fill failed\n"); + err = ret; + goto out; + } + if (!keep_running) + break; + } +out: + return ret; +} + +static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix) +{ + int ret; + int nr = rand() % 20000; + static int run_nr = 0; + + /* do the bulk op much less frequently */ + if (run_nr++ % 100) + return 0; + ret = empty_tree(root, radix, nr); + if (ret) + return ret; + ret = fill_tree(root, radix, nr); + if (ret) + return ret; + return 0; +} + + int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) = -{ ins_one, insert_dup, del_one, lookup_item, lookup_enoent }; +{ ins_one, insert_dup, del_one, lookup_item, lookup_enoent, bulk_op }; static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix) { @@ -192,7 +282,6 @@ static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix) } return 0; } - void sigstopper(int ignored) { keep_running = 0; @@ -241,22 +330,12 @@ int main(int ac, char **av) print_usage(); } } - for (i = 0; i < init_fill_count; i++) { - ret = ins_one(root, &radix); - if (ret) { - printf("initial fill failed\n"); - err = ret; - goto out; - } - if (i % 10000 == 0) { - printf("initial fill %d level %d count %d\n", i, - node_level(root->node->node.header.flags), - root->node->node.header.nritems); - } - if (keep_running == 0) { - err = 0; - goto out; - } + printf("initial fill\n"); + ret = fill_tree(root, &radix, init_fill_count); + printf("starting run\n"); + if (ret) { + err = ret; + goto out; } if (initial_only == 1) { goto out; @@ -287,6 +366,8 @@ int main(int ac, char **av) err = ret; goto out; } + if (ops[op] == bulk_op) + break; if (keep_running == 0) { err = 0; goto out; |