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;
 }