diff options
Diffstat (limited to 'fs')
| -rw-r--r-- | fs/btrfs/Makefile | 7 | ||||
| -rw-r--r-- | fs/btrfs/ctree.c | 82 | ||||
| -rw-r--r-- | fs/btrfs/kerncompat.h | 68 |
3 files changed, 136 insertions, 21 deletions
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile new file mode 100644 index 000000000000..9f84c08baab2 --- /dev/null +++ b/fs/btrfs/Makefile @@ -0,0 +1,7 @@ + +ctree: ctree.o + gcc -g -O2 -Wall -o ctree ctree.c + +clean: + rm ctree ctree.o + 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; } diff --git a/fs/btrfs/kerncompat.h b/fs/btrfs/kerncompat.h new file mode 100644 index 000000000000..3a4bb4d661f9 --- /dev/null +++ b/fs/btrfs/kerncompat.h @@ -0,0 +1,68 @@ +#ifndef __KERNCOMPAT +#define __KERNCOMPAT +#define gfp_t int +#define get_cpu_var(p) (p) +#define __get_cpu_var(p) (p) +#define BITS_PER_LONG 64 +#define __GFP_BITS_SHIFT 20 +#define __GFP_BITS_MASK ((int)((1 << __GFP_BITS_SHIFT) - 1)) +#define __read_mostly +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) +#define __force +#define PAGE_SHIFT 12 +#define ULONG_MAX (~0UL) +#define BUG() abort() + +typedef unsigned int u32; +typedef unsigned long u64; +typedef unsigned char u8; +typedef unsigned short u16; + +typedef unsigned long pgoff_t; + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +struct vma_shared { int prio_tree_node; }; +struct vm_area_struct { + unsigned long vm_pgoff; + unsigned long vm_start; + unsigned long vm_end; + struct vma_shared shared; +}; + +struct page { + unsigned long index; +}; + +static inline void preempt_enable(void) { do {; } while(0);} +static inline void preempt_disable(void) { do {; } while(0);} + +static inline void __set_bit(int bit, unsigned long *map) { + unsigned long *p = map + bit / BITS_PER_LONG; + bit = bit & (BITS_PER_LONG -1); + *p |= 1UL << bit; +} + +static inline int test_bit(int bit, unsigned long *map) { + unsigned long *p = map + bit / BITS_PER_LONG; + bit = bit & (BITS_PER_LONG -1); + return *p & (1UL << bit) ? 1 : 0; +} + +static inline void __clear_bit(int bit, unsigned long *map) { + unsigned long *p = map + bit / BITS_PER_LONG; + bit = bit & (BITS_PER_LONG -1); + *p &= ~(1UL << bit); +} +#define BUG_ON(c) do { if (c) abort(); } while (0) + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - __builtin_offsetof(type,member) );}) + +#endif + +#define ENOMEM 5 +#define EEXIST 6 |