Btrfs: Add fsx-style randomized tree tester

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

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

1 files changed, 58 insertions, 4 deletions

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index b92fbbb5ecd7..18daccd84535 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/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];