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