Btrfs: Add backing store, memory management

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

1 files changed, 272 insertions, 160 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 4bf5e92584bd..6f0522f21082 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -1,68 +1,25 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "kerncompat.h"
-
-#define BLOCKSIZE 4096
-
-struct key {
-        u64 objectid;
-        u32 flags;
-        u64 offset;
-} __attribute__ ((__packed__));
-
-struct header {
-        u64 fsid[2]; /* FS specific uuid */
-        u64 blocknum;
-        u64 parentid;
-        u32 csum;
-        u32 ham;
-        u16 nritems;
-        u16 flags;
-} __attribute__ ((__packed__));
-
-#define NODEPTRS_PER_BLOCK ((BLOCKSIZE - sizeof(struct header)) / \
-                            (sizeof(struct key) + sizeof(u64)))
-
-#define LEVEL_BITS 3
-#define MAX_LEVEL (1 << LEVEL_BITS)
-#define node_level(f) ((f) & (MAX_LEVEL-1))
-#define is_leaf(f) (node_level(f) == 0)
-
-struct ctree_root {
-        struct node *node;
-};
-
-struct item {
-        struct key key;
-        u16 offset;
-        u16 size;
-} __attribute__ ((__packed__));
-
-#define LEAF_DATA_SIZE (BLOCKSIZE - sizeof(struct header))
-struct leaf {
-        struct header header;
-        union {
-                struct item items[LEAF_DATA_SIZE/sizeof(struct item)];
-                u8 data[BLOCKSIZE-sizeof(struct header)];
-        };
-} __attribute__ ((__packed__));
-
-struct node {
-        struct header header;
-        struct key keys[NODEPTRS_PER_BLOCK];
-        u64 blockptrs[NODEPTRS_PER_BLOCK];
-} __attribute__ ((__packed__));
-
-struct ctree_path {
-        struct node *nodes[MAX_LEVEL];
-        int slots[MAX_LEVEL];
-};
+#include "radix-tree.h"
+#include "ctree.h"
+#include "disk-io.h"
 
 static inline void init_path(struct ctree_path *p)
 {
         memset(p, 0, sizeof(*p));
 }
 
+static void release_path(struct ctree_root *root, struct ctree_path *p)
+{
+        int i;
+        for (i = 0; i < MAX_LEVEL; i++) {
+                if (!p->nodes[i])
+                        break;
+                tree_block_release(root, p->nodes[i]);
+        }
+}
+
 static inline unsigned int leaf_data_end(struct leaf *leaf)
 {
         unsigned int nr = leaf->header.nritems;
@@ -135,26 +92,25 @@ int bin_search(struct node *c, struct key *key, int *slot)
         return -1;
 }
 
-void *read_block(u64 blocknum)
-{
-        return (void *)blocknum;
-}
-
 int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p)
 {
-        struct node *c = root->node;
+        struct tree_buffer *b = root->node;
+        struct node *c;
+
         int slot;
         int ret;
         int level;
-        while (c) {
+        b->count++;
+        while (b) {
+                c = &b->node;
                 level = node_level(c->header.flags);
-                p->nodes[level] = c;
+                p->nodes[level] = b;
                 ret = bin_search(c, key, &slot);
                 if (!is_leaf(c->header.flags)) {
                         if (ret && slot > 0)
                                 slot -= 1;
                         p->slots[level] = slot;
-                        c = read_block(c->blockptrs[slot]);
+                        b = read_tree_block(root, c->blockptrs[slot]);
                         continue;
                 } else {
                         p->slots[level] = slot;
@@ -164,17 +120,20 @@ int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p)
         return -1;
 }
 
-static void fixup_low_keys(struct ctree_path *path, struct key *key,
-                             int level)
+static void fixup_low_keys(struct ctree_root *root,
+                           struct ctree_path *path, struct key *key,
+                           int level)
 {
         int i;
         /* adjust the pointers going up the tree */
         for (i = level; i < MAX_LEVEL; i++) {
-                struct node *t = path->nodes[i];
+                struct node *t;
                 int tslot = path->slots[i];
-                if (!t)
+                if (!path->nodes[i])
                         break;
+                t = &path->nodes[i]->node;
                 memcpy(t->keys + tslot, key, sizeof(*key));
+                write_tree_block(root, path->nodes[i]);
                 if (tslot != 0)
                         break;
         }
@@ -190,27 +149,34 @@ int __insert_ptr(struct ctree_root *root,
         int nritems;
         /* need a new root */
         if (!path->nodes[level]) {
-                c = malloc(sizeof(struct node));
+                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);
-                lower = path->nodes[level-1];
+                c->header.blocknr = t->blocknr;
+                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] = (u64)lower;
+                c->blockptrs[0] = path->nodes[level-1]->blocknr;
                 c->blockptrs[1] = blocknr;
-                root->node = c;
-                path->nodes[level] = c;
+                /* the path 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;
         }
-        lower = path->nodes[level];
+        lower = &path->nodes[level]->node;
         nritems = lower->header.nritems;
         if (slot > nritems)
                 BUG();
@@ -227,6 +193,7 @@ int __insert_ptr(struct ctree_root *root,
         lower->header.nritems++;
         if (lower->keys[1].objectid == 0)
                         BUG();
+        write_tree_block(root, path->nodes[level]);
         return 0;
 }
 
@@ -238,6 +205,8 @@ int push_node_left(struct ctree_root *root, struct ctree_path *path, int level)
         int push_items = 0;
         int left_nritems;
         int right_nritems;
+        struct tree_buffer *t;
+        struct tree_buffer *right_buf;
 
         if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0)
                 return 1;
@@ -245,13 +214,18 @@ int push_node_left(struct ctree_root *root, struct ctree_path *path, int level)
         if (slot == 0)
                 return 1;
 
-        left = read_block(path->nodes[level + 1]->blockptrs[slot - 1]);
-        right = path->nodes[level];
+        t = read_tree_block(root,
+                            path->nodes[level + 1]->node.blockptrs[slot - 1]);
+        left = &t->node;
+        right_buf = path->nodes[level];
+        right = &right_buf->node;
         left_nritems = left->header.nritems;
         right_nritems = right->header.nritems;
         push_items = NODEPTRS_PER_BLOCK - (left_nritems + 1);
-        if (push_items <= 0)
+        if (push_items <= 0) {
+                tree_block_release(root, t);
                 return 1;
+        }
 
         if (right_nritems < push_items)
                 push_items = right_nritems;
@@ -267,15 +241,20 @@ int push_node_left(struct ctree_root *root, struct ctree_path *path, int level)
         left->header.nritems += push_items;
 
         /* adjust the pointers going up the tree */
-        fixup_low_keys(path, right->keys, level + 1);
+        fixup_low_keys(root, path, right->keys, level + 1);
+
+        write_tree_block(root, t);
+        write_tree_block(root, right_buf);
 
         /* then fixup the leaf pointer in the path */
         if (path->slots[level] < push_items) {
                 path->slots[level] += left_nritems;
-                path->nodes[level] = (struct node*)left;
+                tree_block_release(root, path->nodes[level]);
+                path->nodes[level] = t;
                 path->slots[level + 1] -= 1;
         } else {
                 path->slots[level] -= push_items;
+                tree_block_release(root, t);
         }
         return 0;
 }
@@ -283,6 +262,8 @@ int push_node_left(struct ctree_root *root, struct ctree_path *path, int level)
 int push_node_right(struct ctree_root *root, struct ctree_path *path, int level)
 {
         int slot;
+        struct tree_buffer *t;
+        struct tree_buffer *src_buffer;
         struct node *dst;
         struct node *src;
         int push_items = 0;
@@ -295,16 +276,21 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level)
         if (slot == NODEPTRS_PER_BLOCK - 1)
                 return 1;
 
-        if (slot >= path->nodes[level + 1]->header.nritems -1)
+        if (slot >= path->nodes[level + 1]->node.header.nritems -1)
                 return 1;
 
-        dst = read_block(path->nodes[level + 1]->blockptrs[slot + 1]);
-        src = path->nodes[level];
+        t = read_tree_block(root,
+                            path->nodes[level + 1]->node.blockptrs[slot + 1]);
+        dst = &t->node;
+        src_buffer = path->nodes[level];
+        src = &src_buffer->node;
         dst_nritems = dst->header.nritems;
         src_nritems = src->header.nritems;
         push_items = NODEPTRS_PER_BLOCK - (dst_nritems + 1);
-        if (push_items <= 0)
+        if (push_items <= 0) {
+                tree_block_release(root, t);
                 return 1;
+        }
 
         if (src_nritems < push_items)
                 push_items = src_nritems;
@@ -322,13 +308,21 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level)
         dst->header.nritems += push_items;
 
         /* adjust the pointers going up the tree */
-        memcpy(path->nodes[level + 1]->keys + path->slots[level + 1] + 1,
+        memcpy(path->nodes[level + 1]->node.keys + path->slots[level + 1] + 1,
                 dst->keys, sizeof(struct key));
+
+        write_tree_block(root, path->nodes[level + 1]);
+        write_tree_block(root, t);
+        write_tree_block(root, src_buffer);
+
         /* then fixup the leaf pointer in the path */
         if (path->slots[level] >= src->header.nritems) {
                 path->slots[level] -= src->header.nritems;
-                path->nodes[level] = (struct node*)dst;
+                tree_block_release(root, path->nodes[level]);
+                path->nodes[level] = t;
                 path->slots[level + 1] += 1;
+        } else {
+                tree_block_release(root, t);
         }
         return 0;
 }
@@ -337,15 +331,18 @@ int insert_ptr(struct ctree_root *root,
                 struct ctree_path *path, struct key *key,
                 u64 blocknr, int level)
 {
-        struct node *c = path->nodes[level];
+        struct tree_buffer *t = path->nodes[level];
+        struct node *c = &path->nodes[level]->node;
         struct node *b;
-        struct node *bal[MAX_LEVEL];
+        struct tree_buffer *b_buffer;
+        struct tree_buffer *bal[MAX_LEVEL];
         int bal_level = level;
         int mid;
         int bal_start = -1;
 
         memset(bal, 0, ARRAY_SIZE(bal));
-        while(c && c->header.nritems == NODEPTRS_PER_BLOCK) {
+        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;
@@ -355,8 +352,10 @@ int insert_ptr(struct ctree_root *root,
                 bal_start = bal_level;
                 if (bal_level == MAX_LEVEL - 1)
                         BUG();
-                b = malloc(sizeof(struct node));
+                b_buffer = alloc_free_block(root);
+                b = &b_buffer->node;
                 b->header.flags = c->header.flags;
+                b->header.blocknr = b_buffer->blocknr;
                 mid = (c->header.nritems + 1) / 2;
                 memcpy(b->keys, c->keys + mid,
                         (c->header.nritems - mid) * sizeof(struct key));
@@ -364,21 +363,28 @@ int insert_ptr(struct ctree_root *root,
                         (c->header.nritems - mid) * sizeof(u64));
                 b->header.nritems = c->header.nritems - mid;
                 c->header.nritems = mid;
-                bal[bal_level] = b;
+
+                write_tree_block(root, t);
+                write_tree_block(root, b_buffer);
+
+                bal[bal_level] = b_buffer;
                 if (bal_level == MAX_LEVEL - 1)
                         break;
                 bal_level += 1;
-                c = path->nodes[bal_level];
+                t = path->nodes[bal_level];
         }
         while(bal_start > 0) {
-                b = bal[bal_start];
-                c = path->nodes[bal_start];
-                __insert_ptr(root, path, b->keys, (u64)b,
+                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;
-                        path->nodes[bal_start] = b;
+                        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])
@@ -404,7 +410,9 @@ int leaf_space_used(struct leaf *l, int start, int nr)
 int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
                    int data_size)
 {
-        struct leaf *right = (struct leaf *)path->nodes[0];
+        struct tree_buffer *right_buf = path->nodes[0];
+        struct leaf *right = &right_buf->leaf;
+        struct tree_buffer *t;
         struct leaf *left;
         int slot;
         int i;
@@ -421,9 +429,11 @@ int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
         if (!path->nodes[1]) {
                 return 1;
         }
-        left = read_block(path->nodes[1]->blockptrs[slot - 1]);
+        t = read_tree_block(root, path->nodes[1]->node.blockptrs[slot - 1]);
+        left = &t->leaf;
         free_space = leaf_free_space(left);
         if (free_space < data_size + sizeof(struct item)) {
+                tree_block_release(root, t);
                 return 1;
         }
         for (i = 0; i < right->header.nritems; i++) {
@@ -436,6 +446,7 @@ int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
                 push_space += item->size + sizeof(*item);
         }
         if (push_items == 0) {
+                tree_block_release(root, t);
                 return 1;
         }
         /* push data from right to left */
@@ -446,6 +457,8 @@ int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
                 right->data + right->items[push_items - 1].offset,
                 push_space);
         old_left_nritems = left->header.nritems;
+        BUG_ON(old_left_nritems < 0);
+
         for(i = old_left_nritems; i < old_left_nritems + push_items; i++) {
                 left->items[i].offset -= LEAF_DATA_SIZE -
                         left->items[old_left_nritems -1].offset;
@@ -460,30 +473,40 @@ int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
                 (right->header.nritems - push_items) * sizeof(struct item));
         right->header.nritems -= push_items;
         push_space = LEAF_DATA_SIZE;
+
         for (i = 0; i < right->header.nritems; i++) {
                 right->items[i].offset = push_space - right->items[i].size;
                 push_space = right->items[i].offset;
         }
-        fixup_low_keys(path, &right->items[0].key, 1);
+
+        write_tree_block(root, t);
+        write_tree_block(root, right_buf);
+
+        fixup_low_keys(root, path, &right->items[0].key, 1);
 
         /* then fixup the leaf pointer in the path */
         if (path->slots[0] < push_items) {
                 path->slots[0] += old_left_nritems;
-                path->nodes[0] = (struct node*)left;
+                tree_block_release(root, path->nodes[0]);
+                path->nodes[0] = t;
                 path->slots[1] -= 1;
         } else {
+                tree_block_release(root, t);
                 path->slots[0] -= push_items;
         }
+        BUG_ON(path->slots[0] < 0);
         return 0;
 }
 
 int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size)
 {
-        struct leaf *l = (struct leaf *)path->nodes[0];
-        int nritems = l->header.nritems;
-        int mid = (nritems + 1)/ 2;
-        int slot = path->slots[0];
+        struct tree_buffer *l_buf = path->nodes[0];
+        struct leaf *l = &l_buf->leaf;
+        int nritems;
+        int mid;
+        int slot;
         struct leaf *right;
+        struct tree_buffer *right_buffer;
         int space_needed = data_size + sizeof(struct item);
         int data_copy_size;
         int rt_data_off;
@@ -491,9 +514,19 @@ int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size)
         int ret;
 
         if (push_leaf_left(root, path, data_size) == 0) {
-                return 0;
+                l_buf = path->nodes[0];
+                l = &l_buf->leaf;
+                if (leaf_free_space(l) >= sizeof(struct item) + data_size)
+                        return 0;
         }
-        right = malloc(sizeof(struct leaf));
+        slot = path->slots[0];
+        nritems = l->header.nritems;
+        mid = (nritems + 1)/ 2;
+
+        right_buffer = alloc_free_block(root);
+        BUG_ON(!right_buffer);
+        BUG_ON(mid == nritems);
+        right = &right_buffer->leaf;
         memset(right, 0, sizeof(*right));
         if (mid <= slot) {
                 if (leaf_space_used(l, mid, nritems - mid) + space_needed >
@@ -505,6 +538,8 @@ int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size)
                         BUG();
         }
         right->header.nritems = nritems - mid;
+        right->header.blocknr = right_buffer->blocknr;
+        right->header.flags = node_level(0);
         data_copy_size = l->items[mid].offset + l->items[mid].size -
                          leaf_data_end(l);
         memcpy(right->items, l->items + mid,
@@ -518,12 +553,20 @@ 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,
-                          (u64)right, 1);
+                          right_buffer->blocknr, 1);
+
+        write_tree_block(root, right_buffer);
+        write_tree_block(root, l_buf);
+
+        BUG_ON(path->slots[0] != slot);
         if (mid <= slot) {
-                path->nodes[0] = (struct node *)right;
+                tree_block_release(root, path->nodes[0]);
+                path->nodes[0] = right_buffer;
                 path->slots[0] -= mid;
                 path->slots[1] += 1;
-        }
+        } else
+                tree_block_release(root, right_buffer);
+        BUG_ON(path->slots[0] < 0);
         return ret;
 }
 
@@ -532,28 +575,48 @@ int insert_item(struct ctree_root *root, struct key *key,
 {
         int ret;
         int slot;
+        int slot_orig;
         struct leaf *leaf;
+        struct tree_buffer *leaf_buf;
         unsigned int nritems;
         unsigned int data_end;
         struct ctree_path path;
 
+        if (!root->node) {
+                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);
+        }
         init_path(&path);
         ret = search_slot(root, key, &path);
-        if (ret == 0)
+        if (ret == 0) {
+                release_path(root, &path);
                 return -EEXIST;
+        }
 
-        leaf = (struct leaf *)path.nodes[0];
-        if (leaf_free_space(leaf) <  sizeof(struct item) + data_size)
+        slot_orig = path.slots[0];
+        leaf_buf = path.nodes[0];
+        leaf = &leaf_buf->leaf;
+        if (leaf_free_space(leaf) <  sizeof(struct item) + data_size) {
                 split_leaf(root, &path, data_size);
-        leaf = (struct leaf *)path.nodes[0];
+                leaf_buf = path.nodes[0];
+                leaf = &path.nodes[0]->leaf;
+        }
         nritems = leaf->header.nritems;
         data_end = leaf_data_end(leaf);
+
         if (leaf_free_space(leaf) <  sizeof(struct item) + data_size)
                 BUG();
 
         slot = path.slots[0];
+        BUG_ON(slot < 0);
         if (slot == 0)
-                fixup_low_keys(&path, key, 1);
+                fixup_low_keys(root, &path, key, 1);
         if (slot != nritems) {
                 int i;
                 unsigned int old_data = leaf->items[slot].offset +
@@ -580,21 +643,25 @@ int insert_item(struct ctree_root *root, struct key *key,
         leaf->items[slot].size = data_size;
         memcpy(leaf->data + data_end - data_size, data, data_size);
         leaf->header.nritems += 1;
+        write_tree_block(root, leaf_buf);
         if (leaf_free_space(leaf) < 0)
                 BUG();
+        release_path(root, &path);
         return 0;
 }
 
 int del_ptr(struct ctree_root *root, struct ctree_path *path, int level)
 {
         int slot;
+        struct tree_buffer *t;
         struct node *node;
         int nritems;
 
         while(1) {
-                node = path->nodes[level];
-                if (!node)
+                t = path->nodes[level];
+                if (!t)
                         break;
+                node = &t->node;
                 slot = path->slots[level];
                 nritems = node->header.nritems;
 
@@ -606,28 +673,34 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level)
                                 sizeof(u64) * (nritems - slot - 1));
                 }
                 node->header.nritems--;
+                write_tree_block(root, t);
                 if (node->header.nritems != 0) {
                         int tslot;
                         if (slot == 0)
-                                fixup_low_keys(path, node->keys, level + 1);
+                                fixup_low_keys(root, path, node->keys,
+                                               level + 1);
                         tslot = path->slots[level+1];
+                        t->count++;
                         push_node_left(root, path, level);
                         if (node->header.nritems) {
                                 push_node_right(root, path, level);
                         }
-                        if (node->header.nritems)
+                        if (node->header.nritems) {
+                                tree_block_release(root, t);
                                 break;
+                        }
+                        tree_block_release(root, t);
                         path->slots[level+1] = tslot;
                 }
-                if (node == root->node) {
-                        printf("root is now null!\n");
-                        root->node = NULL;
+                if (t == root->node) {
+                        /* just turn the root into a leaf and break */
+                        root->node->node.header.flags = node_level(0);
+                        write_tree_block(root, t);
                         break;
                 }
                 level++;
                 if (!path->nodes[level])
                         BUG();
-                free(node);
         }
         return 0;
 }
@@ -636,10 +709,12 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
 {
         int slot;
         struct leaf *leaf;
+        struct tree_buffer *leaf_buf;
         int doff;
         int dsize;
 
-        leaf = (struct leaf *)path->nodes[0];
+        leaf_buf = path->nodes[0];
+        leaf = &leaf_buf->leaf;
         slot = path->slots[0];
         doff = leaf->items[slot].offset;
         dsize = leaf->items[slot].size;
@@ -658,14 +733,15 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
         }
         leaf->header.nritems -= 1;
         if (leaf->header.nritems == 0) {
-                if (leaf == (struct leaf *)root->node)
-                        root->node = NULL;
-                else
+                if (leaf_buf == root->node) {
+                        leaf->header.flags = node_level(0);
+                        write_tree_block(root, leaf_buf);
+                } else
                         del_ptr(root, path, 1);
-                free(leaf);
         } else {
                 if (slot == 0)
-                        fixup_low_keys(path, &leaf->items[0].key, 1);
+                        fixup_low_keys(root, path, &leaf->items[0].key, 1);
+                write_tree_block(root, leaf_buf);
                 if (leaf_space_used(leaf, 0, leaf->header.nritems) <
                     LEAF_DATA_SIZE / 4) {
                         /* push_leaf_left fixes the path.
@@ -673,12 +749,13 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
                          * for possible call to del_ptr below
                          */
                         slot = path->slots[1];
+                        leaf_buf->count++;
                         push_leaf_left(root, path, 1);
                         if (leaf->header.nritems == 0) {
-                                free(leaf);
                                 path->slots[1] = slot;
                                 del_ptr(root, path, 1);
                         }
+                        tree_block_release(root, leaf_buf);
                 }
         }
         return 0;
@@ -689,7 +766,7 @@ void print_leaf(struct leaf *l)
         int i;
         int nr = l->header.nritems;
         struct item *item;
-        printf("leaf %p total ptrs %d free space %d\n", l, nr,
+        printf("leaf %lu total ptrs %d free space %d\n", l->header.blocknr, nr,
                leaf_free_space(l));
         fflush(stdout);
         for (i = 0 ; i < nr ; i++) {
@@ -703,38 +780,45 @@ void print_leaf(struct leaf *l)
                 fflush(stdout);
         }
 }
-void print_tree(struct node *c)
+void print_tree(struct ctree_root *root, struct tree_buffer *t)
 {
         int i;
         int nr;
+        struct node *c;
 
-        if (!c)
+        if (!t)
                 return;
+        c = &t->node;
         nr = c->header.nritems;
+        if (c->header.blocknr != t->blocknr)
+                BUG();
         if (is_leaf(c->header.flags)) {
                 print_leaf((struct leaf *)c);
                 return;
         }
-        printf("node %p level %d total ptrs %d free spc %lu\n", c,
+        printf("node %lu level %d total ptrs %d free spc %lu\n", t->blocknr,
                 node_level(c->header.flags), c->header.nritems,
                 NODEPTRS_PER_BLOCK - c->header.nritems);
         fflush(stdout);
         for (i = 0; i < nr; i++) {
-                printf("\tkey %d (%lu %u %lu) block %lx\n",
+                printf("\tkey %d (%lu %u %lu) block %lu\n",
                        i,
                        c->keys[i].objectid, c->keys[i].flags, c->keys[i].offset,
                        c->blockptrs[i]);
                 fflush(stdout);
         }
         for (i = 0; i < nr; i++) {
-                struct node *next = read_block(c->blockptrs[i]);
+                struct tree_buffer *next_buf = read_tree_block(root,
+                                                            c->blockptrs[i]);
+                struct node *next = &next_buf->node;
                 if (is_leaf(next->header.flags) &&
                     node_level(c->header.flags) != 1)
                         BUG();
                 if (node_level(next->header.flags) !=
                         node_level(c->header.flags) - 1)
                         BUG();
-                print_tree(next);
+                print_tree(root, next_buf);
+                tree_block_release(root, next_buf);
         }
 
 }
@@ -746,23 +830,24 @@ int next_key(int i, int max_key) {
 }
 
 int main() {
-        struct leaf *first_node = malloc(sizeof(struct leaf));
-        struct ctree_root root;
+        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 = 100000;
+        int run_size = 1000000;
         int max_key = 100000000;
         int tree_size = 0;
         struct ctree_path path;
 
+        radix_tree_init();
+
+
+        root = open_ctree("dbfile");
 
         srand(55);
-        root.node = (struct node *)first_node;
-        memset(first_node, 0, sizeof(*first_node));
         for (i = 0; i < run_size; i++) {
                 buf = malloc(64);
                 num = next_key(i, max_key);
@@ -772,39 +857,46 @@ int main() {
                 ins.objectid = num;
                 ins.offset = 0;
                 ins.flags = 0;
-                ret = insert_item(&root, &ins, buf, strlen(buf));
+                ret = insert_item(root, &ins, buf, strlen(buf));
                 if (!ret)
                         tree_size++;
         }
+        close_ctree(root);
+        root = open_ctree("dbfile");
+        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);
-                ret = search_slot(&root, &ins, &path);
+                ret = search_slot(root, &ins, &path);
                 if (ret) {
-                        print_tree(root.node);
+                        print_tree(root, root->node);
                         printf("unable to find %d\n", num);
                         exit(1);
                 }
-        }
-        printf("node %p level %d total ptrs %d free spc %lu\n", root.node,
-                node_level(root.node->header.flags), root.node->header.nritems,
-                NODEPTRS_PER_BLOCK - root.node->header.nritems);
-        // print_tree(root.node);
-        printf("all searches good\n");
+                release_path(root, &path);
+        }
+        close_ctree(root);
+        root = open_ctree("dbfile");
+        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);
+                ret = search_slot(root, &ins, &path);
                 if (ret)
                         continue;
-                ret = del_item(&root, &path);
+                ret = del_item(root, &path);
                 if (ret != 0)
                         BUG();
+                release_path(root, &path);
                 tree_size--;
         }
         srand(128);
@@ -813,38 +905,58 @@ int main() {
                 num = next_key(i, max_key);
                 sprintf(buf, "string-%d", num);
                 ins.objectid = num;
-                ret = insert_item(&root, &ins, buf, strlen(buf));
+                ret = insert_item(root, &ins, buf, strlen(buf));
                 if (!ret)
                         tree_size++;
         }
-        while(root.node) {
+        close_ctree(root);
+        root = open_ctree("dbfile");
+        printf("starting search2\n");
+        srand(128);
+        for (i = 0; i < run_size; i++) {
+                num = next_key(i, max_key);
+                ins.objectid = num;
+                init_path(&path);
+                ret = search_slot(root, &ins, &path);
+                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);
+                ret = search_slot(root, &ins, &path);
                 if (ret == 0)
                         BUG();
 
-                leaf = (struct leaf *)(path.nodes[0]);
+                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 = (struct leaf *)(path.nodes[0]);
+                        leaf = &path.nodes[0]->leaf;
 
                         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)
+                        ret = del_item(root, &path);
+                        if (ret != 0) {
+                                printf("del_item returned %d\n", ret);
                                 BUG();
+                        }
                         tree_size--;
                 }
+                release_path(root, &path);
         }
-        print_tree(root.node);
+        close_ctree(root);
         printf("tree size is now %d\n", tree_size);
         return 0;
 }