summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/btrfs/Makefile2
-rw-r--r--fs/btrfs/TODO1
-rw-r--r--fs/btrfs/ctree.c51
-rw-r--r--fs/btrfs/ctree.h182
-rw-r--r--fs/btrfs/dir-item.c102
-rw-r--r--fs/btrfs/extent-tree.c17
-rw-r--r--fs/btrfs/hash.c86
-rw-r--r--fs/btrfs/hasher.c23
-rw-r--r--fs/btrfs/kerncompat.h1
-rw-r--r--fs/btrfs/mkfs.c28
-rw-r--r--fs/btrfs/print-tree.c36
-rw-r--r--fs/btrfs/quick-test.c3
-rw-r--r--fs/btrfs/random-test.c10
-rw-r--r--fs/btrfs/root-tree.c2
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;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-24 00:21:24 +0100