Btrfs: Use a chunk of the key flags to record the item type.

Add (untested and simple) directory item code
Fix comp_keys to use the new key ordering
Add btrfs_insert_empty_item

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

14 files changed, 435 insertions, 109 deletions

diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 13ed6313ac85..ee78cdd08c04 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -3,7 +3,7 @@ CC=gcc
 CFLAGS = -g -Wall
 headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h list.h
 objects = ctree.o disk-io.o radix-tree.o mkfs.o extent-tree.o print-tree.o \
-	  root-tree.o
+	  root-tree.o dir-item.o hash.o
 
 # if you don't have sparse installed, use ls instead
 CHECKFLAGS=-D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise \
diff --git a/fs/btrfs/TODO b/fs/btrfs/TODO
index 8142be88d71c..249e2e90bea8 100644
--- a/fs/btrfs/TODO
+++ b/fs/btrfs/TODO
@@ -8,6 +8,7 @@
 * Add block mapping tree (simple dm layer)
 * Add simple tree locking (semaphore per tree)
 * Make allocator smarter
+* Do actual block accounting
 * Port into the kernel
 * Add virtual filesystems, mountable snapshots
 * Get rid of struct ctree_path, limiting tree levels held at one time
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index ece8de7f38ef..7edfbd468042 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -107,14 +107,14 @@ static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
 		return 1;
 	if (k1.objectid < k2->objectid)
 		return -1;
-	if (k1.flags > k2->flags)
-		return 1;
-	if (k1.flags < k2->flags)
-		return -1;
 	if (k1.offset > k2->offset)
 		return 1;
 	if (k1.offset < k2->offset)
 		return -1;
+	if (k1.flags > k2->flags)
+		return 1;
+	if (k1.flags < k2->flags)
+		return -1;
 	return 0;
 }
 
@@ -1122,8 +1122,8 @@ static int split_leaf(struct btrfs_root *root, struct btrfs_path *path,
  * Given a key and some data, insert an item into the tree.
  * This does all the path init required, making room in the tree if needed.
  */
-int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key,
-			  void *data, int data_size)
+int btrfs_insert_empty_item(struct btrfs_root *root, struct btrfs_path *path,
+			    struct btrfs_key *cpu_key, u32 data_size)
 {
 	int ret = 0;
 	int slot;
@@ -1132,7 +1132,6 @@ int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key,
 	struct btrfs_buffer *leaf_buf;
 	u32 nritems;
 	unsigned int data_end;
-	struct btrfs_path path;
 	struct btrfs_disk_key disk_key;
 
 	btrfs_cpu_key_to_disk(&disk_key, cpu_key);
@@ -1140,17 +1139,16 @@ int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key,
 	/* create a root if there isn't one */
 	if (!root->node)
 		BUG();
-	btrfs_init_path(&path);
-	ret = btrfs_search_slot(root, cpu_key, &path, data_size, 1);
+	ret = btrfs_search_slot(root, cpu_key, path, data_size, 1);
 	if (ret == 0) {
-		btrfs_release_path(root, &path);
+		btrfs_release_path(root, path);
 		return -EEXIST;
 	}
 	if (ret < 0)
 		goto out;
 
-	slot_orig = path.slots[0];
-	leaf_buf = path.nodes[0];
+	slot_orig = path->slots[0];
+	leaf_buf = path->nodes[0];
 	leaf = &leaf_buf->leaf;
 
 	nritems = btrfs_header_nritems(&leaf->header);
@@ -1160,7 +1158,7 @@ int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key,
 	    sizeof(struct btrfs_item) + data_size)
 		BUG();
 
-	slot = path.slots[0];
+	slot = path->slots[0];
 	BUG_ON(slot < 0);
 	if (slot != nritems) {
 		int i;
@@ -1186,23 +1184,42 @@ int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key,
 		        data_end, old_data - data_end);
 		data_end = old_data;
 	}
-	/* copy the new data in */
+	/* setup the item for the new data */
 	memcpy(&leaf->items[slot].key, &disk_key,
 		sizeof(struct btrfs_disk_key));
 	btrfs_set_item_offset(leaf->items + slot, data_end - data_size);
 	btrfs_set_item_size(leaf->items + slot, data_size);
-	memcpy(btrfs_leaf_data(leaf) + data_end - data_size, data, data_size);
 	btrfs_set_header_nritems(&leaf->header, nritems + 1);
 
 	ret = 0;
 	if (slot == 0)
-		ret = fixup_low_keys(root, &path, &disk_key, 1);
+		ret = fixup_low_keys(root, path, &disk_key, 1);
 
 	BUG_ON(list_empty(&leaf_buf->dirty));
 	if (btrfs_leaf_free_space(root, leaf) < 0)
 		BUG();
-	check_leaf(root, &path, 0);
+	check_leaf(root, path, 0);
 out:
+	return ret;
+}
+
+/*
+ * Given a key and some data, insert an item into the tree.
+ * This does all the path init required, making room in the tree if needed.
+ */
+int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key,
+			  void *data, u32 data_size)
+{
+	int ret = 0;
+	struct btrfs_path path;
+	u8 *ptr;
+
+	btrfs_init_path(&path);
+	ret = btrfs_insert_empty_item(root, &path, cpu_key, data_size);
+	if (!ret) {
+		ptr = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], u8);
+		memcpy(ptr, data, data_size);
+	}
 	btrfs_release_path(root, &path);
 	return ret;
 }
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 73ebc824924a..e8a26fd8ea9f 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -58,39 +58,6 @@ struct btrfs_header {
 #define BTRFS_LEAF_DATA_SIZE(r) (__BTRFS_LEAF_DATA_SIZE(r->blocksize))
 
 struct btrfs_buffer;
-
-struct btrfs_root_item {
-	__le64 blocknr;
-	__le32 flags;
-	__le64 block_limit;
-	__le64 blocks_used;
-	__le32 refs;
-};
-
-/*
- * 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 btrfs_root {
-	struct btrfs_buffer *node;
-	struct btrfs_buffer *commit_root;
-	struct btrfs_root *extent_root;
-	struct btrfs_root *tree_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;
-	int ref_cows;
-	struct btrfs_root_item root_item;
-	struct btrfs_key root_key;
-	u32 blocksize;
-};
-
 /*
  * the super block basically lists the main trees of the FS
  * it currently lacks any block count etc etc
@@ -108,8 +75,7 @@ struct btrfs_super_block {
 } __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
+ * A leaf is full of items. offset and size tell us where to find
  * the item in the leaf (relative to the start of the data area)
  */
 struct btrfs_item {
@@ -145,15 +111,6 @@ struct btrfs_node {
 } __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 btrfs_extent_item {
-	__le32 refs;
-	__le64 owner;
-} __attribute__ ((__packed__));
-
-/*
  * btrfs_paths remember the path taken from the root down to the leaf.
  * level 0 is always the leaf, and nodes[1...BTRFS_MAX_LEVEL] will point
  * to any other levels that are present.
@@ -166,6 +123,94 @@ struct btrfs_path {
 	int slots[BTRFS_MAX_LEVEL];
 };
 
+/*
+ * items in the extent btree are used to record the objectid of the
+ * owner of the block and the number of references
+ */
+struct btrfs_extent_item {
+	__le32 refs;
+	__le64 owner;
+} __attribute__ ((__packed__));
+
+struct btrfs_dir_item {
+	__le64 objectid;
+	__le16 flags;
+	u8 type;
+} __attribute__ ((__packed__));
+
+struct btrfs_root_item {
+	__le64 blocknr;
+	__le32 flags;
+	__le64 block_limit;
+	__le64 blocks_used;
+	__le32 refs;
+};
+
+/*
+ * 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 btrfs_root {
+	struct btrfs_buffer *node;
+	struct btrfs_buffer *commit_root;
+	struct btrfs_root *extent_root;
+	struct btrfs_root *tree_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;
+	int ref_cows;
+	struct btrfs_root_item root_item;
+	struct btrfs_key root_key;
+	u32 blocksize;
+};
+
+
+/* the lower bits in the key flags defines the item type */
+#define BTRFS_KEY_TYPE_MAX	256
+#define BTRFS_KEY_TYPE_MASK	(BTRFS_KEY_TYPE_MAX - 1)
+#define BTRFS_INODE_ITEM_KEY	1
+#define BTRFS_DIR_ITEM_KEY	2
+#define BTRFS_ROOT_ITEM_KEY	3
+#define BTRFS_EXTENT_ITEM_KEY	4
+#define BTRFS_STRING_ITEM_KEY	5
+
+static inline u64 btrfs_dir_objectid(struct btrfs_dir_item *d)
+{
+	return le64_to_cpu(d->objectid);
+}
+
+static inline void btrfs_set_dir_objectid(struct btrfs_dir_item *d, u64 val)
+{
+	d->objectid = cpu_to_le64(val);
+}
+
+static inline u16 btrfs_dir_flags(struct btrfs_dir_item *d)
+{
+	return le16_to_cpu(d->flags);
+}
+
+static inline void btrfs_set_dir_flags(struct btrfs_dir_item *d, u16 val)
+{
+	d->flags = cpu_to_le16(val);
+}
+
+static inline u8 btrfs_dir_type(struct btrfs_dir_item *d)
+{
+	return d->type;
+}
+
+static inline void btrfs_set_dir_type(struct btrfs_dir_item *d, u8 val)
+{
+	d->type = val;
+}
+
+
 static inline u64 btrfs_extent_owner(struct btrfs_extent_item *ei)
 {
 	return le64_to_cpu(ei->owner);
@@ -238,39 +283,65 @@ static inline void btrfs_cpu_key_to_disk(struct btrfs_disk_key *disk,
 	disk->objectid = cpu_to_le64(cpu->objectid);
 }
 
-static inline u64 btrfs_key_objectid(struct btrfs_disk_key *disk)
+static inline u64 btrfs_disk_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)
+static inline void btrfs_set_disk_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)
+static inline u64 btrfs_disk_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)
+static inline void btrfs_set_disk_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)
+static inline u32 btrfs_disk_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)
+static inline void btrfs_set_disk_key_flags(struct btrfs_disk_key *disk,
+					    u32 val)
 {
 	disk->flags = cpu_to_le32(val);
 }
 
+static inline u32 btrfs_key_type(struct btrfs_key *key)
+{
+	return key->flags & BTRFS_KEY_TYPE_MASK;
+}
+
+static inline u32 btrfs_disk_key_type(struct btrfs_disk_key *key)
+{
+	return le32_to_cpu(key->flags) & BTRFS_KEY_TYPE_MASK;
+}
+
+static inline void btrfs_set_key_type(struct btrfs_key *key, u32 type)
+{
+	BUG_ON(type >= BTRFS_KEY_TYPE_MAX);
+	key->flags = (key->flags & ~((u64)BTRFS_KEY_TYPE_MASK)) | type;
+}
+
+static inline void btrfs_set_disk_key_type(struct btrfs_disk_key *key, u32 type)
+{
+	u32 flags = btrfs_disk_key_flags(key);
+	BUG_ON(type >= BTRFS_KEY_TYPE_MAX);
+	flags = (flags & ~((u64)BTRFS_KEY_TYPE_MASK)) | type;
+	btrfs_set_disk_key_flags(key, flags);
+}
+
+
+
 static inline u64 btrfs_header_blocknr(struct btrfs_header *h)
 {
 	return le64_to_cpu(h->blocknr);
@@ -407,7 +478,6 @@ static inline u8 *btrfs_leaf_data(struct btrfs_leaf *l)
 {
 	return (u8 *)l->items;
 }
-
 /* helper function to cast into the data area of the leaf. */
 #define btrfs_item_ptr(leaf, slot, type) \
 	((type *)(btrfs_leaf_data(leaf) + \
@@ -422,7 +492,9 @@ void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p);
 void btrfs_init_path(struct btrfs_path *p);
 int btrfs_del_item(struct btrfs_root *root, struct btrfs_path *path);
 int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *key,
-		void *data, int data_size);
+		void *data, u32 data_size);
+int btrfs_insert_empty_item(struct btrfs_root *root, struct btrfs_path *path,
+			    struct btrfs_key *cpu_key, u32 data_size);
 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path);
 int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf);
 int btrfs_drop_snapshot(struct btrfs_root *root, struct btrfs_buffer *snap);
diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c
new file mode 100644
index 000000000000..2a888e97e1a2
--- /dev/null
+++ b/fs/btrfs/dir-item.c
@@ -0,0 +1,102 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "kerncompat.h"
+#include "radix-tree.h"
+#include "ctree.h"
+#include "disk-io.h"
+#include "hash.h"
+
+int btrfs_insert_dir_item(struct btrfs_root *root, char *name, int name_len,
+			  u64 dir, u64 objectid, u8 type)
+{
+	int ret = 0;
+	struct btrfs_path path;
+	struct btrfs_dir_item *dir_item;
+	char *name_ptr;
+	struct btrfs_key key;
+	u32 data_size;
+
+	key.objectid = dir;
+	key.flags = 0;
+	ret = btrfs_name_hash(name, name_len, &key.offset);
+	BUG_ON(ret);
+	btrfs_init_path(&path);
+	data_size = sizeof(*dir_item) + name_len;
+	ret = btrfs_insert_empty_item(root, &path, &key, data_size);
+	if (ret)
+		goto out;
+
+	dir_item = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
+				  struct btrfs_dir_item);
+	btrfs_set_dir_objectid(dir_item, objectid);
+	btrfs_set_dir_type(dir_item, type);
+	btrfs_set_dir_flags(dir_item, 0);
+	name_ptr = (char *)(dir_item + 1);
+	memcpy(name_ptr, name, name_len);
+out:
+	btrfs_release_path(root, &path);
+	return ret;
+}
+
+int btrfs_del_dir_item(struct btrfs_root *root, u64 dir, char *name,
+		       int name_len)
+{
+	int ret = 0;
+	struct btrfs_path path;
+	struct btrfs_key key;
+
+	key.objectid = dir;
+	key.flags = 0;
+	ret = btrfs_name_hash(name, name_len, &key.offset);
+	BUG_ON(ret);
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(root, &key, &path, 0, 1);
+	if (ret)
+		goto out;
+	ret = btrfs_del_item(root, &path);
+out:
+	btrfs_release_path(root, &path);
+	return ret;
+}
+
+int btrfs_lookup_dir_item(struct btrfs_root *root, u64 dir, char *name,
+			  int name_len, u64 *objectid)
+{
+	int ret = 0;
+	struct btrfs_path path;
+	struct btrfs_dir_item *dir_item;
+	char *name_ptr;
+	struct btrfs_key key;
+	u32 item_len;
+	struct btrfs_item *item;
+
+	key.objectid = dir;
+	key.flags = 0;
+	ret = btrfs_name_hash(name, name_len, &key.offset);
+	BUG_ON(ret);
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(root, &key, &path, 0, 0);
+	if (ret)
+		goto out;
+
+	dir_item = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
+				  struct btrfs_dir_item);
+
+	item = path.nodes[0]->leaf.items + path.slots[0];
+	item_len = btrfs_item_size(item);
+	if (item_len != name_len + sizeof(struct btrfs_dir_item)) {
+		BUG();
+		ret = 1;
+		goto out;
+	}
+	name_ptr = (char *)(dir_item + 1);
+	if (memcmp(name_ptr, name, name_len)) {
+		BUG();
+		ret = 1;
+		goto out;
+	}
+	*objectid = btrfs_dir_objectid(dir_item);
+out:
+	btrfs_release_path(root, &path);
+	return ret;
+}
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index d4f1ec328399..c81e14162ef1 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -35,6 +35,7 @@ static int inc_block_ref(struct btrfs_root *root, u64 blocknr)
 	btrfs_init_path(&path);
 	key.objectid = blocknr;
 	key.flags = 0;
+	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 	key.offset = 1;
 	ret = btrfs_search_slot(root->extent_root, &key, &path, 0, 1);
 	if (ret != 0)
@@ -61,8 +62,9 @@ static int lookup_block_ref(struct btrfs_root *root, u64 blocknr, u32 *refs)
 	struct btrfs_extent_item *item;
 	btrfs_init_path(&path);
 	key.objectid = blocknr;
-	key.flags = 0;
 	key.offset = 1;
+	key.flags = 0;
+	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 	ret = btrfs_search_slot(root->extent_root, &key, &path, 0, 0);
 	if (ret != 0)
 		BUG();
@@ -123,6 +125,7 @@ static int finish_current_insert(struct btrfs_root *extent_root)
 		btrfs_header_parentid(&extent_root->node->node.header));
 	ins.offset = 1;
 	ins.flags = 0;
+	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 
 	for (i = 0; i < extent_root->current_insert.flags; i++) {
 		ins.objectid = extent_root->current_insert.objectid + i;
@@ -149,6 +152,7 @@ static int __free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks)
 
 	key.objectid = blocknr;
 	key.flags = 0;
+	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 	key.offset = num_blocks;
 
 	find_free_extent(root, 0, 0, (u64)-1, &ins);
@@ -228,7 +232,6 @@ static int run_pending(struct btrfs_root *extent_root)
  */
 int btrfs_free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks)
 {
-	struct btrfs_key key;
 	struct btrfs_root *extent_root = root->extent_root;
 	struct btrfs_buffer *t;
 	int pending_ret;
@@ -240,9 +243,6 @@ int btrfs_free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks)
 				   CTREE_EXTENT_PENDING_DEL);
 		return 0;
 	}
-	key.objectid = blocknr;
-	key.flags = 0;
-	key.offset = num_blocks;
 	ret = __free_extent(root, blocknr, num_blocks);
 	pending_ret = run_pending(root->extent_root);
 	return ret ? ret : pending_ret;
@@ -252,7 +252,7 @@ int btrfs_free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks)
  * walks the btree of allocated extents and find a hole of a given size.
  * The key ins is changed to record the hole:
  * ins->objectid == block start
- * ins->flags = 0
+ * ins->flags = BTRFS_EXTENT_ITEM_KEY
  * ins->offset == number of blocks
  * Any available blocks before search_start are skipped.
  */
@@ -275,11 +275,14 @@ static int find_free_extent(struct btrfs_root *orig_root, u64 num_blocks,
 	total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
 	if (root->last_insert.objectid > search_start)
 		search_start = root->last_insert.objectid;
+
+	ins->flags = 0;
+	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
+
 check_failed:
 	btrfs_init_path(&path);
 	ins->objectid = search_start;
 	ins->offset = 0;
-	ins->flags = 0;
 	start_found = 0;
 	ret = btrfs_search_slot(root, ins, &path, 0, 0);
 	if (ret < 0)
diff --git a/fs/btrfs/hash.c b/fs/btrfs/hash.c
new file mode 100644
index 000000000000..92c37eece1f2
--- /dev/null
+++ b/fs/btrfs/hash.c
@@ -0,0 +1,86 @@
+/*
+ *  Original copy from:
+ *  linux/fs/ext3/hash.c
+ *
+ * Copyright (C) 2002 by Theodore Ts'o
+ *
+ * This file is released under the GPL v2.
+ *
+ * This file may be redistributed under the terms of the GNU Public
+ * License.
+ */
+
+#include "kerncompat.h"
+#define DELTA 0x9E3779B9
+
+static void TEA_transform(__u32 buf[2], __u32 const in[])
+{
+	__u32	sum = 0;
+	__u32	b0 = buf[0], b1 = buf[1];
+	__u32	a = in[0], b = in[1], c = in[2], d = in[3];
+	int	n = 16;
+
+	do {
+		sum += DELTA;
+		b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
+		b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
+	} while(--n);
+
+	buf[0] += b0;
+	buf[1] += b1;
+}
+
+static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
+{
+	__u32	pad, val;
+	int	i;
+
+	pad = (__u32)len | ((__u32)len << 8);
+	pad |= pad << 16;
+
+	val = pad;
+	if (len > num*4)
+		len = num * 4;
+	for (i=0; i < len; i++) {
+		if ((i % 4) == 0)
+			val = pad;
+		val = msg[i] + (val << 8);
+		if ((i % 4) == 3) {
+			*buf++ = val;
+			val = pad;
+			num--;
+		}
+	}
+	if (--num >= 0)
+		*buf++ = val;
+	while (--num >= 0)
+		*buf++ = pad;
+}
+
+int btrfs_name_hash(const char *name, int len, u64 *hash_result)
+{
+	__u32	hash;
+	__u32	minor_hash = 0;
+	const char	*p;
+	__u32		in[8], buf[2];
+
+	/* Initialize the default seed for the hash checksum functions */
+	buf[0] = 0x67452301;
+	buf[1] = 0xefcdab89;
+	buf[2] = 0x98badcfe;
+	buf[3] = 0x10325476;
+
+	p = name;
+	while (len > 0) {
+		str2hashbuf(p, len, in, 4);
+		TEA_transform(buf, in);
+		len -= 16;
+		p += 16;
+	}
+	hash = buf[0];
+	minor_hash = buf[1];
+	*hash_result = buf[0];
+	*hash_result <<= 32;
+	*hash_result |= buf[1];
+	return 0;
+}
diff --git a/fs/btrfs/hasher.c b/fs/btrfs/hasher.c
new file mode 100644
index 000000000000..96702da4329c
--- /dev/null
+++ b/fs/btrfs/hasher.c
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "kerncompat.h"
+#include "hash.h"
+
+int main() {
+	u64 result;
+	int ret;
+	char line[255];
+	char *p;
+	while(1) {
+		p = fgets(line, 255, stdin);
+		if (!p)
+			break;
+		if (strlen(line) == 0)
+			continue;
+		ret = btrfs_name_hash(line, strlen(line), &result);
+		BUG_ON(ret);
+		printf("hash returns %Lu\n", result);
+	}
+	return 0;
+}
diff --git a/fs/btrfs/kerncompat.h b/fs/btrfs/kerncompat.h
index 56239b922ba6..105d3f584089 100644
--- a/fs/btrfs/kerncompat.h
+++ b/fs/btrfs/kerncompat.h
@@ -21,6 +21,7 @@
 #endif
 
 typedef unsigned int u32;
+typedef u32 __u32;
 typedef unsigned long long u64;
 typedef unsigned char u8;
 typedef unsigned short u16;
diff --git a/fs/btrfs/mkfs.c b/fs/btrfs/mkfs.c
index 317d20ce759d..9aa900811c33 100644
--- a/fs/btrfs/mkfs.c
+++ b/fs/btrfs/mkfs.c
@@ -50,9 +50,10 @@ int mkfs(int fd, u64 num_blocks, u32 blocksize)
 	itemoff = __BTRFS_LEAF_DATA_SIZE(blocksize) - sizeof(root_item);
 	btrfs_set_item_offset(&item, itemoff);
 	btrfs_set_item_size(&item, sizeof(root_item));
-	btrfs_set_key_objectid(&item.key, BTRFS_EXTENT_TREE_OBJECTID);
-	btrfs_set_key_offset(&item.key, 0);
-	btrfs_set_key_flags(&item.key, 0);
+	btrfs_set_disk_key_objectid(&item.key, BTRFS_EXTENT_TREE_OBJECTID);
+	btrfs_set_disk_key_offset(&item.key, 0);
+	btrfs_set_disk_key_flags(&item.key, 0);
+	btrfs_set_disk_key_type(&item.key, BTRFS_ROOT_ITEM_KEY);
 	memcpy(empty_leaf->items, &item, sizeof(item));
 	memcpy(btrfs_leaf_data(empty_leaf) + itemoff,
 		&root_item, sizeof(root_item));
@@ -60,7 +61,7 @@ int mkfs(int fd, u64 num_blocks, u32 blocksize)
 	btrfs_set_root_blocknr(&root_item, start_block + 3);
 	itemoff = itemoff - sizeof(root_item);
 	btrfs_set_item_offset(&item, itemoff);
-	btrfs_set_key_objectid(&item.key, BTRFS_FS_TREE_OBJECTID);
+	btrfs_set_disk_key_objectid(&item.key, BTRFS_FS_TREE_OBJECTID);
 	memcpy(empty_leaf->items + 1, &item, sizeof(item));
 	memcpy(btrfs_leaf_data(empty_leaf) + itemoff,
 		&root_item, sizeof(root_item));
@@ -73,9 +74,10 @@ int mkfs(int fd, u64 num_blocks, u32 blocksize)
 	btrfs_set_header_nritems(&empty_leaf->header, 4);
 
 	/* item1, reserve blocks 0-16 */
-	btrfs_set_key_objectid(&item.key, 0);
-	btrfs_set_key_offset(&item.key, start_block + 1);
-	btrfs_set_key_flags(&item.key, 0);
+	btrfs_set_disk_key_objectid(&item.key, 0);
+	btrfs_set_disk_key_offset(&item.key, start_block + 1);
+	btrfs_set_disk_key_flags(&item.key, 0);
+	btrfs_set_disk_key_type(&item.key, BTRFS_EXTENT_ITEM_KEY);
 	itemoff = __BTRFS_LEAF_DATA_SIZE(blocksize) -
 			sizeof(struct btrfs_extent_item);
 	btrfs_set_item_offset(&item, itemoff);
@@ -87,8 +89,8 @@ int mkfs(int fd, u64 num_blocks, u32 blocksize)
 		&extent_item, btrfs_item_size(&item));
 
 	/* item2, give block 17 to the root */
-	btrfs_set_key_objectid(&item.key, start_block + 1);
-	btrfs_set_key_offset(&item.key, 1);
+	btrfs_set_disk_key_objectid(&item.key, start_block + 1);
+	btrfs_set_disk_key_offset(&item.key, 1);
 	itemoff = itemoff - sizeof(struct btrfs_extent_item);
 	btrfs_set_item_offset(&item, itemoff);
 	btrfs_set_extent_owner(&extent_item, BTRFS_ROOT_TREE_OBJECTID);
@@ -97,8 +99,8 @@ int mkfs(int fd, u64 num_blocks, u32 blocksize)
 		&extent_item, btrfs_item_size(&item));
 
 	/* item3, give block 18 to the extent root */
-	btrfs_set_key_objectid(&item.key, start_block + 2);
-	btrfs_set_key_offset(&item.key, 1);
+	btrfs_set_disk_key_objectid(&item.key, start_block + 2);
+	btrfs_set_disk_key_offset(&item.key, 1);
 	itemoff = itemoff - sizeof(struct btrfs_extent_item);
 	btrfs_set_item_offset(&item, itemoff);
 	btrfs_set_extent_owner(&extent_item, BTRFS_EXTENT_TREE_OBJECTID);
@@ -107,8 +109,8 @@ int mkfs(int fd, u64 num_blocks, u32 blocksize)
 		&extent_item, btrfs_item_size(&item));
 
 	/* item4, give block 19 to the FS root */
-	btrfs_set_key_objectid(&item.key, start_block + 3);
-	btrfs_set_key_offset(&item.key, 1);
+	btrfs_set_disk_key_objectid(&item.key, start_block + 3);
+	btrfs_set_disk_key_offset(&item.key, 1);
 	itemoff = itemoff - sizeof(struct btrfs_extent_item);
 	btrfs_set_item_offset(&item, itemoff);
 	btrfs_set_extent_owner(&extent_item, BTRFS_FS_TREE_OBJECTID);
diff --git a/fs/btrfs/print-tree.c b/fs/btrfs/print-tree.c
index 4c710190343d..f2745b247473 100644
--- a/fs/btrfs/print-tree.c
+++ b/fs/btrfs/print-tree.c
@@ -12,27 +12,41 @@ void btrfs_print_leaf(struct btrfs_root *root, struct btrfs_leaf *l)
 	struct btrfs_item *item;
 	struct btrfs_extent_item *ei;
 	struct btrfs_root_item *ri;
+	u32 type;
 	printf("leaf %Lu total ptrs %d free space %d\n",
 		btrfs_header_blocknr(&l->header), nr,
 		btrfs_leaf_free_space(root, l));
 	fflush(stdout);
 	for (i = 0 ; i < nr ; i++) {
 		item = l->items + i;
+		type = btrfs_disk_key_type(&item->key);
 		printf("\titem %d key (%Lu %Lu %u) itemoff %d itemsize %d\n",
 			i,
-			btrfs_key_objectid(&item->key),
-			btrfs_key_offset(&item->key),
-			btrfs_key_flags(&item->key),
+			btrfs_disk_key_objectid(&item->key),
+			btrfs_disk_key_offset(&item->key),
+			btrfs_disk_key_flags(&item->key),
 			btrfs_item_offset(item),
 			btrfs_item_size(item));
-		printf("\t\titem data %.*s\n", btrfs_item_size(item),
-			btrfs_leaf_data(l) + btrfs_item_offset(item));
-		ei = btrfs_item_ptr(l, i, struct btrfs_extent_item);
-		printf("\t\textent data refs %u owner %Lu\n",
-			btrfs_extent_refs(ei), btrfs_extent_owner(ei));
-		ri = btrfs_item_ptr(l, i, struct btrfs_root_item);
-		printf("\t\troot data blocknr %Lu refs %u\n",
-			btrfs_root_blocknr(ri), btrfs_root_refs(ri));
+		switch (type) {
+		case BTRFS_INODE_ITEM_KEY:
+			break;
+		case BTRFS_DIR_ITEM_KEY:
+			break;
+		case BTRFS_ROOT_ITEM_KEY:
+			ri = btrfs_item_ptr(l, i, struct btrfs_root_item);
+			printf("\t\troot data blocknr %Lu refs %u\n",
+				btrfs_root_blocknr(ri), btrfs_root_refs(ri));
+			break;
+		case BTRFS_EXTENT_ITEM_KEY:
+			ei = btrfs_item_ptr(l, i, struct btrfs_extent_item);
+			printf("\t\textent data refs %u owner %Lu\n",
+				btrfs_extent_refs(ei), btrfs_extent_owner(ei));
+			break;
+		case BTRFS_STRING_ITEM_KEY:
+			printf("\t\titem data %.*s\n", btrfs_item_size(item),
+				btrfs_leaf_data(l) + btrfs_item_offset(item));
+			break;
+		};
 		fflush(stdout);
 	}
 }
diff --git a/fs/btrfs/quick-test.c b/fs/btrfs/quick-test.c
index d9287cad35c9..3a2571617121 100644
--- a/fs/btrfs/quick-test.c
+++ b/fs/btrfs/quick-test.c
@@ -30,6 +30,8 @@ int main(int ac, char **av) {
 
 	root = open_ctree("dbfile", &super);
 	srand(55);
+	ins.flags = 0;
+	btrfs_set_key_type(&ins, BTRFS_STRING_ITEM_KEY);
 	for (i = 0; i < run_size; i++) {
 		buf = malloc(64);
 		num = next_key(i, max_key);
@@ -39,7 +41,6 @@ int main(int ac, char **av) {
 			fprintf(stderr, "insert %d:%d\n", num, i);
 		ins.objectid = num;
 		ins.offset = 0;
-		ins.flags = 0;
 		ret = btrfs_insert_item(root, &ins, buf, strlen(buf));
 		if (!ret)
 			tree_size++;
diff --git a/fs/btrfs/random-test.c b/fs/btrfs/random-test.c
index a8ef0478991b..f05135f13f9a 100644
--- a/fs/btrfs/random-test.c
+++ b/fs/btrfs/random-test.c
@@ -18,6 +18,7 @@ static int setup_key(struct radix_tree_root *root, struct btrfs_key *key,
 	int ret;
 
 	key->flags = 0;
+	btrfs_set_key_type(key, BTRFS_STRING_ITEM_KEY);
 	key->offset = 0;
 again:
 	ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
@@ -157,6 +158,7 @@ static int empty_tree(struct btrfs_root *root, struct radix_tree_root *radix,
 
 	key.offset = 0;
 	key.flags = 0;
+	btrfs_set_key_type(&key, BTRFS_STRING_ITEM_KEY);
 	key.objectid = (unsigned long)-1;
 	while(nr-- >= 0) {
 		btrfs_init_path(&path);
@@ -173,7 +175,8 @@ static int empty_tree(struct btrfs_root *root, struct radix_tree_root *radix,
 			path.slots[0] -= 1;
 		}
 		slot = path.slots[0];
-		found=btrfs_key_objectid(&path.nodes[0]->leaf.items[slot].key);
+		found = btrfs_disk_key_objectid(
+					&path.nodes[0]->leaf.items[slot].key);
 		ret = btrfs_del_item(root, &path);
 		count++;
 		if (ret) {
@@ -257,6 +260,7 @@ static int fill_radix(struct btrfs_root *root, struct radix_tree_root *radix)
 
 	key.offset = 0;
 	key.flags = 0;
+	btrfs_set_key_type(&key, BTRFS_STRING_ITEM_KEY);
 	key.objectid = (unsigned long)-1;
 	while(1) {
 		btrfs_init_path(&path);
@@ -274,8 +278,8 @@ static int fill_radix(struct btrfs_root *root, struct radix_tree_root *radix)
 			slot -= 1;
 		}
 		for (i = slot; i >= 0; i--) {
-			found = btrfs_key_objectid(&path.nodes[0]->
-						   leaf.items[i].key);
+			found = btrfs_disk_key_objectid(&path.nodes[0]->
+							leaf.items[i].key);
 			radix_tree_preload(GFP_KERNEL);
 			ret = radix_tree_insert(radix, found, (void *)found);
 			if (ret) {
diff --git a/fs/btrfs/root-tree.c b/fs/btrfs/root-tree.c
index 03aa7c2c6336..a24b47274037 100644
--- a/fs/btrfs/root-tree.c
+++ b/fs/btrfs/root-tree.c
@@ -27,7 +27,7 @@ int btrfs_find_last_root(struct btrfs_root *root, u64 objectid,
 	l = &path.nodes[0]->leaf;
 	BUG_ON(path.slots[0] == 0);
 	slot = path.slots[0] - 1;
-	if (btrfs_key_objectid(&l->items[slot].key) != objectid) {
+	if (btrfs_disk_key_objectid(&l->items[slot].key) != objectid) {
 		ret = 1;
 		goto out;
 	}