[linux-2.6-block.git] / fs / btrfs / ctree.h

#ifndef __CTREE__
#define __CTREE__

#include "list.h"
#include "kerncompat.h"

#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.
 *
 * btrfs_disk_key is in disk byte order.  struct btrfs_key is always
 * in cpu native order.  Otherwise they are identical and their sizes
 * should be the same (ie both packed)
 */
struct btrfs_disk_key {
	__le64 objectid;
	__le32 flags;
	__le64 offset;
} __attribute__ ((__packed__));

struct btrfs_key {
	u64 objectid;
	u32 flags;
	u64 offset;
} __attribute__ ((__packed__));

/*
 * every tree block (leaf or node) starts with this header.
 */
struct btrfs_header {
	__le64 fsid[2]; /* FS specific uuid */
	__le64 blocknr; /* which block this node is supposed to live in */
	__le64 parentid; /* objectid of the tree root */
	__le32 csum;
	__le32 ham;
	__le16 nritems;
	__le16 flags;
	/* generation flags to be added */
} __attribute__ ((__packed__));

#define MAX_LEVEL 8
#define NODEPTRS_PER_BLOCK ((CTREE_BLOCKSIZE - sizeof(struct btrfs_header)) / \
			    (sizeof(struct btrfs_disk_key) + sizeof(u64)))

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 tree_buffer *commit_root;
	struct ctree_root *extent_root;
	struct btrfs_key current_insert;
	struct btrfs_key last_insert;
	int fp;
	struct radix_tree_root cache_radix;
	struct radix_tree_root pinned_radix;
	struct list_head trans;
	struct list_head cache;
	int cache_size;
};

/*
 * 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 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 btrfs_item {
	struct btrfs_disk_key key;
	__le16 offset;
	__le16 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 btrfs_header))
struct leaf {
	struct btrfs_header header;
	union {
		struct btrfs_item items[LEAF_DATA_SIZE/
				        sizeof(struct btrfs_item)];
		u8 data[CTREE_BLOCKSIZE-sizeof(struct btrfs_header)];
	};
} __attribute__ ((__packed__));

/*
 * all non-leaf blocks are nodes, they hold only keys and pointers to
 * other blocks
 */
struct node {
	struct btrfs_header header;
	struct btrfs_disk_key keys[NODEPTRS_PER_BLOCK];
	__le64 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 {
	__le32 refs;
	__le64 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];
};

static inline u64 btrfs_extent_owner(struct extent_item *ei)
{
	return le64_to_cpu(ei->owner);
}

static inline void btrfs_set_extent_owner(struct extent_item *ei, u64 val)
{
	ei->owner = cpu_to_le64(val);
}

static inline u32 btrfs_extent_refs(struct extent_item *ei)
{
	return le32_to_cpu(ei->refs);
}

static inline void btrfs_set_extent_refs(struct extent_item *ei, u32 val)
{
	ei->refs = cpu_to_le32(val);
}

static inline u64 btrfs_node_blockptr(struct node *n, int nr)
{
	return le64_to_cpu(n->blockptrs[nr]);
}

static inline void btrfs_set_node_blockptr(struct node *n, int nr, u64 val)
{
	n->blockptrs[nr] = cpu_to_le64(val);
}

static inline u16 btrfs_item_offset(struct btrfs_item *item)
{
	return le16_to_cpu(item->offset);
}

static inline void btrfs_set_item_offset(struct btrfs_item *item, u16 val)
{
	item->offset = cpu_to_le16(val);
}

static inline u16 btrfs_item_end(struct btrfs_item *item)
{
	return le16_to_cpu(item->offset) + le16_to_cpu(item->size);
}

static inline u16 btrfs_item_size(struct btrfs_item *item)
{
	return le16_to_cpu(item->size);
}

static inline void btrfs_set_item_size(struct btrfs_item *item, u16 val)
{
	item->size = cpu_to_le16(val);
}

static inline void btrfs_disk_key_to_cpu(struct btrfs_key *cpu,
					 struct btrfs_disk_key *disk)
{
	cpu->offset = le64_to_cpu(disk->offset);
	cpu->flags = le32_to_cpu(disk->flags);
	cpu->objectid = le64_to_cpu(disk->objectid);
}

static inline void btrfs_cpu_key_to_disk(struct btrfs_disk_key *disk,
					 struct btrfs_key *cpu)
{
	disk->offset = cpu_to_le64(cpu->offset);
	disk->flags = cpu_to_le32(cpu->flags);
	disk->objectid = cpu_to_le64(cpu->objectid);
}

static inline u64 btrfs_key_objectid(struct btrfs_disk_key *disk)
{
	return le64_to_cpu(disk->objectid);
}

static inline void btrfs_set_key_objectid(struct btrfs_disk_key *disk,
					  u64 val)
{
	disk->objectid = cpu_to_le64(val);
}

static inline u64 btrfs_key_offset(struct btrfs_disk_key *disk)
{
	return le64_to_cpu(disk->offset);
}

static inline void btrfs_set_key_offset(struct btrfs_disk_key *disk,
					  u64 val)
{
	disk->offset = cpu_to_le64(val);
}

static inline u32 btrfs_key_flags(struct btrfs_disk_key *disk)
{
	return le32_to_cpu(disk->flags);
}

static inline void btrfs_set_key_flags(struct btrfs_disk_key *disk,
					  u32 val)
{
	disk->flags = cpu_to_le32(val);
}

static inline u64 btrfs_header_blocknr(struct btrfs_header *h)
{
	return le64_to_cpu(h->blocknr);
}

static inline void btrfs_set_header_blocknr(struct btrfs_header *h, u64 blocknr)
{
	h->blocknr = cpu_to_le64(blocknr);
}

static inline u64 btrfs_header_parentid(struct btrfs_header *h)
{
	return le64_to_cpu(h->parentid);
}

static inline void btrfs_set_header_parentid(struct btrfs_header *h,
					     u64 parentid)
{
	h->parentid = cpu_to_le64(parentid);
}

static inline u16 btrfs_header_nritems(struct btrfs_header *h)
{
	return le16_to_cpu(h->nritems);
}

static inline void btrfs_set_header_nritems(struct btrfs_header *h, u16 val)
{
	h->nritems = cpu_to_le16(val);
}

static inline u16 btrfs_header_flags(struct btrfs_header *h)
{
	return le16_to_cpu(h->flags);
}

static inline void btrfs_set_header_flags(struct btrfs_header *h, u16 val)
{
	h->flags = cpu_to_le16(val);
}

static inline int btrfs_header_level(struct btrfs_header *h)
{
	return btrfs_header_flags(h) & (MAX_LEVEL - 1);
}

static inline void btrfs_set_header_level(struct btrfs_header *h, int level)
{
	u16 flags;
	BUG_ON(level > MAX_LEVEL);
	flags = btrfs_header_flags(h) & ~(MAX_LEVEL - 1);
	btrfs_set_header_flags(h, flags | level);
}

static inline int btrfs_is_leaf(struct node *n)
{
	return (btrfs_header_level(&n->header) == 0);
}

struct tree_buffer *alloc_free_block(struct ctree_root *root);
int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf);
int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks);
int search_slot(struct ctree_root *root, struct btrfs_key *key,
		struct ctree_path *p, int ins_len, int cow);
void release_path(struct ctree_root *root, struct ctree_path *p);
void init_path(struct ctree_path *p);
int del_item(struct ctree_root *root, struct ctree_path *path);
int insert_item(struct ctree_root *root, struct btrfs_key *key,
		void *data, int data_size);
int next_leaf(struct ctree_root *root, struct ctree_path *path);
int leaf_free_space(struct leaf *leaf);
int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap);
int btrfs_finish_extent_commit(struct ctree_root *root);
#endif
Commit	Line	Data
	1	#ifndef __CTREE__
	2	#define __CTREE__
	3
	4	#include "list.h"
	5	#include "kerncompat.h"
	6
	7	#define CTREE_BLOCKSIZE 1024
	8
	9	/*
	10	* the key defines the order in the tree, and so it also defines (optimal)
	11	* block layout. objectid corresonds to the inode number. The flags
	12	* tells us things about the object, and is a kind of stream selector.
	13	* so for a given inode, keys with flags of 1 might refer to the inode
	14	* data, flags of 2 may point to file data in the btree and flags == 3
	15	* may point to extents.
	16	*
	17	* offset is the starting byte offset for this key in the stream.
	18	*
	19	* btrfs_disk_key is in disk byte order. struct btrfs_key is always
	20	* in cpu native order. Otherwise they are identical and their sizes
	21	* should be the same (ie both packed)
	22	*/
	23	struct btrfs_disk_key {
	24	__le64 objectid;
	25	__le32 flags;
	26	__le64 offset;
	27	} __attribute__ ((__packed__));
	28
	29	struct btrfs_key {
	30	u64 objectid;
	31	u32 flags;
	32	u64 offset;
	33	} __attribute__ ((__packed__));
	34
	35	/*
	36	* every tree block (leaf or node) starts with this header.
	37	*/
	38	struct btrfs_header {
	39	__le64 fsid[2]; /* FS specific uuid */
	40	__le64 blocknr; /* which block this node is supposed to live in */
	41	__le64 parentid; /* objectid of the tree root */
	42	__le32 csum;
	43	__le32 ham;
	44	__le16 nritems;
	45	__le16 flags;
	46	/* generation flags to be added */
	47	} __attribute__ ((__packed__));
	48
	49	#define MAX_LEVEL 8
	50	#define NODEPTRS_PER_BLOCK ((CTREE_BLOCKSIZE - sizeof(struct btrfs_header)) / \
	51	(sizeof(struct btrfs_disk_key) + sizeof(u64)))
	52
	53	struct tree_buffer;
	54
	55	/*
	56	* in ram representation of the tree. extent_root is used for all allocations
	57	* and for the extent tree extent_root root. current_insert is used
	58	* only for the extent tree.
	59	*/
	60	struct ctree_root {
	61	struct tree_buffer *node;
	62	struct tree_buffer *commit_root;
	63	struct ctree_root *extent_root;
	64	struct btrfs_key current_insert;
	65	struct btrfs_key last_insert;
	66	int fp;
	67	struct radix_tree_root cache_radix;
	68	struct radix_tree_root pinned_radix;
	69	struct list_head trans;
	70	struct list_head cache;
	71	int cache_size;
	72	};
	73
	74	/*
	75	* describes a tree on disk
	76	*/
	77	struct ctree_root_info {
	78	u64 fsid[2]; /* FS specific uuid */
	79	u64 blocknr; /* blocknr of this block */
	80	u64 objectid; /* inode number of this root */
	81	u64 tree_root; /* the tree root block */
	82	u32 csum;
	83	u32 ham;
	84	u64 snapuuid[2]; /* root specific uuid */
	85	} __attribute__ ((__packed__));
	86
	87	/*
	88	* the super block basically lists the main trees of the FS
	89	* it currently lacks any block count etc etc
	90	*/
	91	struct ctree_super_block {
	92	struct ctree_root_info root_info;
	93	struct ctree_root_info extent_info;
	94	} __attribute__ ((__packed__));
	95
	96	/*
	97	* A leaf is full of items. The exact type of item is defined by
	98	* the key flags parameter. offset and size tell us where to find
	99	* the item in the leaf (relative to the start of the data area)
	100	*/
	101	struct btrfs_item {
	102	struct btrfs_disk_key key;
	103	__le16 offset;
	104	__le16 size;
	105	} __attribute__ ((__packed__));
	106
	107	/*
	108	* leaves have an item area and a data area:
	109	* [item0, item1....itemN] [free space] [dataN...data1, data0]
	110	*
	111	* The data is separate from the items to get the keys closer together
	112	* during searches.
	113	*/
	114	#define LEAF_DATA_SIZE (CTREE_BLOCKSIZE - sizeof(struct btrfs_header))
	115	struct leaf {
	116	struct btrfs_header header;
	117	union {
	118	struct btrfs_item items[LEAF_DATA_SIZE/
	119	sizeof(struct btrfs_item)];
	120	u8 data[CTREE_BLOCKSIZE-sizeof(struct btrfs_header)];
	121	};
	122	} __attribute__ ((__packed__));
	123
	124	/*
	125	* all non-leaf blocks are nodes, they hold only keys and pointers to
	126	* other blocks
	127	*/
	128	struct node {
	129	struct btrfs_header header;
	130	struct btrfs_disk_key keys[NODEPTRS_PER_BLOCK];
	131	__le64 blockptrs[NODEPTRS_PER_BLOCK];
	132	} __attribute__ ((__packed__));
	133
	134	/*
	135	* items in the extent btree are used to record the objectid of the
	136	* owner of the block and the number of references
	137	*/
	138	struct extent_item {
	139	__le32 refs;
	140	__le64 owner;
	141	} __attribute__ ((__packed__));
	142
	143	/*
	144	* ctree_paths remember the path taken from the root down to the leaf.
	145	* level 0 is always the leaf, and nodes[1...MAX_LEVEL] will point
	146	* to any other levels that are present.
	147	*
	148	* The slots array records the index of the item or block pointer
	149	* used while walking the tree.
	150	*/
	151	struct ctree_path {
	152	struct tree_buffer *nodes[MAX_LEVEL];
	153	int slots[MAX_LEVEL];
	154	};
	155
	156	static inline u64 btrfs_extent_owner(struct extent_item *ei)
	157	{
	158	return le64_to_cpu(ei->owner);
	159	}
	160
	161	static inline void btrfs_set_extent_owner(struct extent_item *ei, u64 val)
	162	{
	163	ei->owner = cpu_to_le64(val);
	164	}
	165
	166	static inline u32 btrfs_extent_refs(struct extent_item *ei)
	167	{
	168	return le32_to_cpu(ei->refs);
	169	}
	170
	171	static inline void btrfs_set_extent_refs(struct extent_item *ei, u32 val)
	172	{
	173	ei->refs = cpu_to_le32(val);
	174	}
	175
	176	static inline u64 btrfs_node_blockptr(struct node *n, int nr)
	177	{
	178	return le64_to_cpu(n->blockptrs[nr]);
	179	}
	180
	181	static inline void btrfs_set_node_blockptr(struct node *n, int nr, u64 val)
	182	{
	183	n->blockptrs[nr] = cpu_to_le64(val);
	184	}
	185
	186	static inline u16 btrfs_item_offset(struct btrfs_item *item)
	187	{
	188	return le16_to_cpu(item->offset);
	189	}
	190
	191	static inline void btrfs_set_item_offset(struct btrfs_item *item, u16 val)
	192	{
	193	item->offset = cpu_to_le16(val);
	194	}
	195
	196	static inline u16 btrfs_item_end(struct btrfs_item *item)
	197	{
	198	return le16_to_cpu(item->offset) + le16_to_cpu(item->size);
	199	}
	200
	201	static inline u16 btrfs_item_size(struct btrfs_item *item)
	202	{
	203	return le16_to_cpu(item->size);
	204	}
	205
	206	static inline void btrfs_set_item_size(struct btrfs_item *item, u16 val)
	207	{
	208	item->size = cpu_to_le16(val);
	209	}
	210
	211	static inline void btrfs_disk_key_to_cpu(struct btrfs_key *cpu,
	212	struct btrfs_disk_key *disk)
	213	{
	214	cpu->offset = le64_to_cpu(disk->offset);
	215	cpu->flags = le32_to_cpu(disk->flags);
	216	cpu->objectid = le64_to_cpu(disk->objectid);
	217	}
	218
	219	static inline void btrfs_cpu_key_to_disk(struct btrfs_disk_key *disk,
	220	struct btrfs_key *cpu)
	221	{
	222	disk->offset = cpu_to_le64(cpu->offset);
	223	disk->flags = cpu_to_le32(cpu->flags);
	224	disk->objectid = cpu_to_le64(cpu->objectid);
	225	}
	226
	227	static inline u64 btrfs_key_objectid(struct btrfs_disk_key *disk)
	228	{
	229	return le64_to_cpu(disk->objectid);
	230	}
	231
	232	static inline void btrfs_set_key_objectid(struct btrfs_disk_key *disk,
	233	u64 val)
	234	{
	235	disk->objectid = cpu_to_le64(val);
	236	}
	237
	238	static inline u64 btrfs_key_offset(struct btrfs_disk_key *disk)
	239	{
	240	return le64_to_cpu(disk->offset);
	241	}
	242
	243	static inline void btrfs_set_key_offset(struct btrfs_disk_key *disk,
	244	u64 val)
	245	{
	246	disk->offset = cpu_to_le64(val);
	247	}
	248
	249	static inline u32 btrfs_key_flags(struct btrfs_disk_key *disk)
	250	{
	251	return le32_to_cpu(disk->flags);
	252	}
	253
	254	static inline void btrfs_set_key_flags(struct btrfs_disk_key *disk,
	255	u32 val)
	256	{
	257	disk->flags = cpu_to_le32(val);
	258	}
	259
	260	static inline u64 btrfs_header_blocknr(struct btrfs_header *h)
	261	{
	262	return le64_to_cpu(h->blocknr);
	263	}
	264
	265	static inline void btrfs_set_header_blocknr(struct btrfs_header *h, u64 blocknr)
	266	{
	267	h->blocknr = cpu_to_le64(blocknr);
	268	}
	269
	270	static inline u64 btrfs_header_parentid(struct btrfs_header *h)
	271	{
	272	return le64_to_cpu(h->parentid);
	273	}
	274
	275	static inline void btrfs_set_header_parentid(struct btrfs_header *h,
	276	u64 parentid)
	277	{
	278	h->parentid = cpu_to_le64(parentid);
	279	}
	280
	281	static inline u16 btrfs_header_nritems(struct btrfs_header *h)
	282	{
	283	return le16_to_cpu(h->nritems);
	284	}
	285
	286	static inline void btrfs_set_header_nritems(struct btrfs_header *h, u16 val)
	287	{
	288	h->nritems = cpu_to_le16(val);
	289	}
	290
	291	static inline u16 btrfs_header_flags(struct btrfs_header *h)
	292	{
	293	return le16_to_cpu(h->flags);
	294	}
	295
	296	static inline void btrfs_set_header_flags(struct btrfs_header *h, u16 val)
	297	{
	298	h->flags = cpu_to_le16(val);
	299	}
	300
	301	static inline int btrfs_header_level(struct btrfs_header *h)
	302	{
	303	return btrfs_header_flags(h) & (MAX_LEVEL - 1);
	304	}
	305
	306	static inline void btrfs_set_header_level(struct btrfs_header *h, int level)
	307	{
	308	u16 flags;
	309	BUG_ON(level > MAX_LEVEL);
	310	flags = btrfs_header_flags(h) & ~(MAX_LEVEL - 1);
	311	btrfs_set_header_flags(h, flags \| level);
	312	}
	313
	314	static inline int btrfs_is_leaf(struct node *n)
	315	{
	316	return (btrfs_header_level(&n->header) == 0);
	317	}
	318
	319	struct tree_buffer alloc_free_block(struct ctree_root root);
	320	int btrfs_inc_ref(struct ctree_root root, struct tree_buffer buf);
	321	int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks);
	322	int search_slot(struct ctree_root root, struct btrfs_key key,
	323	struct ctree_path *p, int ins_len, int cow);
	324	void release_path(struct ctree_root root, struct ctree_path p);
	325	void init_path(struct ctree_path *p);
	326	int del_item(struct ctree_root root, struct ctree_path path);
	327	int insert_item(struct ctree_root root, struct btrfs_key key,
	328	void *data, int data_size);
	329	int next_leaf(struct ctree_root root, struct ctree_path path);
	330	int leaf_free_space(struct leaf *leaf);
	331	int btrfs_drop_snapshot(struct ctree_root root, struct tree_buffer snap);
	332	int btrfs_finish_extent_commit(struct ctree_root *root);
	333	#endif