Add fsx-style randomized tree tester

Add debug-tree command to print the tree
Add extent-tree.c to the repo
Comment ctree.h

1 files changed, 58 insertions, 4 deletions

diff --git a/ctree.h b/ctree.h
index b92fbbb5..18daccd8 100644
--- a/ctree.h
+++ b/ctree.h
@@ -1,22 +1,36 @@
 #ifndef __CTREE__
 #define __CTREE__
 
-#define CTREE_BLOCKSIZE 4096
+#define CTREE_BLOCKSIZE 1024
 
+/*
+ * the key defines the order in the tree, and so it also defines (optimal)
+ * block layout.  objectid corresonds to the inode number.  The flags
+ * tells us things about the object, and is a kind of stream selector.
+ * so for a given inode, keys with flags of 1 might refer to the inode
+ * data, flags of 2 may point to file data in the btree and flags == 3
+ * may point to extents.
+ *
+ * offset is the starting byte offset for this key in the stream.
+ */
 struct key {
 	u64 objectid;
 	u32 flags;
 	u64 offset;
 } __attribute__ ((__packed__));
 
+/*
+ * every tree block (leaf or node) starts with this header.
+ */
 struct header {
 	u64 fsid[2]; /* FS specific uuid */
-	u64 blocknr;
-	u64 parentid;
+	u64 blocknr; /* which block this node is supposed to live in */
+	u64 parentid; /* objectid of the tree root */
 	u32 csum;
 	u32 ham;
 	u16 nritems;
 	u16 flags;
+	/* generation flags to be added */
 } __attribute__ ((__packed__));
 
 #define NODEPTRS_PER_BLOCK ((CTREE_BLOCKSIZE - sizeof(struct header)) / \
@@ -28,6 +42,11 @@ struct header {
 
 struct tree_buffer;
 
+/*
+ * in ram representation of the tree.  extent_root is used for all allocations
+ * and for the extent tree extent_root root.  current_insert is used
+ * only for the extent tree.
+ */
 struct ctree_root {
 	struct tree_buffer *node;
 	struct ctree_root *extent_root;
@@ -36,27 +55,46 @@ struct ctree_root {
 	struct radix_tree_root cache_radix;
 };
 
+/*
+ * describes a tree on disk
+ */
 struct ctree_root_info {
 	u64 fsid[2]; /* FS specific uuid */
 	u64 blocknr; /* blocknr of this block */
 	u64 objectid; /* inode number of this root */
-	u64 tree_root; /* the tree root */
+	u64 tree_root; /* the tree root block */
 	u32 csum;
 	u32 ham;
 	u64 snapuuid[2]; /* root specific uuid */
 } __attribute__ ((__packed__));
 
+/*
+ * the super block basically lists the main trees of the FS
+ * it currently lacks any block count etc etc
+ */
 struct ctree_super_block {
 	struct ctree_root_info root_info;
 	struct ctree_root_info extent_info;
 } __attribute__ ((__packed__));
 
+/*
+ * A leaf is full of items.  The exact type of item is defined by
+ * the key flags parameter.  offset and size tell us where to find
+ * the item in the leaf (relative to the start of the data area)
+ */
 struct item {
 	struct key key;
 	u16 offset;
 	u16 size;
 } __attribute__ ((__packed__));
 
+/*
+ * leaves have an item area and a data area:
+ * [item0, item1....itemN] [free space] [dataN...data1, data0]
+ *
+ * The data is separate from the items to get the keys closer together
+ * during searches.
+ */
 #define LEAF_DATA_SIZE (CTREE_BLOCKSIZE - sizeof(struct header))
 struct leaf {
 	struct header header;
@@ -66,17 +104,33 @@ struct leaf {
 	};
 } __attribute__ ((__packed__));
 
+/*
+ * all non-leaf blocks are nodes, they hold only keys and pointers to
+ * other blocks
+ */
 struct node {
 	struct header header;
 	struct key keys[NODEPTRS_PER_BLOCK];
 	u64 blockptrs[NODEPTRS_PER_BLOCK];
 } __attribute__ ((__packed__));
 
+/*
+ * items in the extent btree are used to record the objectid of the
+ * owner of the block and the number of references
+ */
 struct extent_item {
 	u32 refs;
 	u64 owner;
 } __attribute__ ((__packed__));
 
+/*
+ * ctree_paths remember the path taken from the root down to the leaf.
+ * level 0 is always the leaf, and nodes[1...MAX_LEVEL] will point
+ * to any other levels that are present.
+ *
+ * The slots array records the index of the item or block pointer
+ * used while walking the tree.
+ */
 struct ctree_path {
 	struct tree_buffer *nodes[MAX_LEVEL];
 	int slots[MAX_LEVEL];