aboutsummaryrefslogtreecommitdiffstats
path: root/fs
diff options
context:
space:
mode:
authorChris Mason <chris.mason@oracle.com>2007-03-21 11:12:56 -0400
committerDavid Woodhouse <dwmw2@hera.kernel.org>2007-03-21 11:12:56 -0400
commit2e635a278354a1a7951e16cfea4c247d6d0e7c99 (patch)
tree4b94d54ddcd7cb184681260738b68caef4edee81 /fs
parent1261ec42b3d3a3ad878bd172144940e3ac710749 (diff)
Btrfs: initial move to kernel module land
Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs')
-rw-r--r--fs/btrfs/Makefile50
-rw-r--r--fs/btrfs/ctree.c6
-rw-r--r--fs/btrfs/ctree.h15
-rw-r--r--fs/btrfs/debug-tree.c38
-rw-r--r--fs/btrfs/dir-item.c12
-rw-r--r--fs/btrfs/dir-test.c494
-rw-r--r--fs/btrfs/disk-io.c17
-rw-r--r--fs/btrfs/disk-io.h1
-rw-r--r--fs/btrfs/extent-tree.c10
-rw-r--r--fs/btrfs/file-item.c6
-rw-r--r--fs/btrfs/hash.c1
-rw-r--r--fs/btrfs/hasher.c23
-rw-r--r--fs/btrfs/inode-item.c5
-rw-r--r--fs/btrfs/inode-map.c5
-rw-r--r--fs/btrfs/kerncompat.h96
-rw-r--r--fs/btrfs/list.h418
-rw-r--r--fs/btrfs/mkfs.c255
-rw-r--r--fs/btrfs/print-tree.c30
-rw-r--r--fs/btrfs/quick-test.c179
-rw-r--r--fs/btrfs/radix-tree.c836
-rw-r--r--fs/btrfs/radix-tree.h73
-rw-r--r--fs/btrfs/random-test.c405
-rw-r--r--fs/btrfs/root-tree.c5
-rw-r--r--fs/btrfs/super.c205
24 files changed, 274 insertions, 2911 deletions
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 0720169b6d66..99e45a54ebd6 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -1,40 +1,20 @@
1CC=gcc 1ifneq ($(KERNELRELEASE),)
2CFLAGS = -g -Wall -Werror 2# kbuild part of makefile
3headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h list.h \
4 transaction.h
5objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
6 root-tree.o dir-item.o hash.o file-item.o inode-item.o \
7 inode-map.o \
8 3
9# if you don't have sparse installed, use ls instead 4obj-m := btrfs.o
10CHECKFLAGS=-D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise \ 5btrfs-y := super.o
11 -Wcontext -Wcast-truncate -Wuninitialized -Wshadow -Wundef
12check=sparse $(CHECKFLAGS)
13#check=ls
14 6
15.c.o: 7#btrfs-y := ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
16 $(check) $< 8# root-tree.o dir-item.o hash.o file-item.o inode-item.o \
17 $(CC) $(CFLAGS) -c $< 9# inode-map.o \
18 10
19all: tester debug-tree quick-test dir-test tags mkfs.btrfs 11else
20
21mkfs.btrfs: $(objects) mkfs.o
22 gcc $(CFLAGS) -o mkfs.btrfs $(objects) mkfs.o
23
24debug-tree: $(objects) debug-tree.o
25 gcc $(CFLAGS) -o debug-tree $(objects) debug-tree.o
26
27tester: $(objects) random-test.o
28 gcc $(CFLAGS) -o tester $(objects) random-test.o
29
30dir-test: $(objects) dir-test.o
31 gcc $(CFLAGS) -o dir-test $(objects) dir-test.o
32quick-test: $(objects) quick-test.o
33 gcc $(CFLAGS) -o quick-test $(objects) quick-test.o
34
35$(objects): $(headers)
36
37clean :
38 rm debug-tree tester *.o
39 12
13# Normal Makefile
40 14
15KERNELDIR := /lib/modules/`uname -r`/build
16all::
17 $(MAKE) -C $(KERNELDIR) M=`pwd` modules
18clean::
19 rm *.o btrfs.ko
20endif
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 32922643b5bc..9fbd07c37fde 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -1,10 +1,6 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h" 3#include "disk-io.h"
7#include "print-tree.h"
8 4
9static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 5static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
10 *root, struct btrfs_path *path, int level); 6 *root, struct btrfs_path *path, int level);
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 1a4d1d6fa401..ae8518cb94bf 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1,9 +1,6 @@
1#ifndef __BTRFS__ 1#ifndef __BTRFS__
2#define __BTRFS__ 2#define __BTRFS__
3 3
4#include "list.h"
5#include "kerncompat.h"
6
7struct btrfs_trans_handle; 4struct btrfs_trans_handle;
8 5
9#define BTRFS_MAGIC "_BtRfS_M" 6#define BTRFS_MAGIC "_BtRfS_M"
@@ -75,6 +72,7 @@ struct btrfs_super_block {
75 __le64 root; 72 __le64 root;
76 __le64 total_blocks; 73 __le64 total_blocks;
77 __le64 blocks_used; 74 __le64 blocks_used;
75 __le64 root_dir_objectid;
78} __attribute__ ((__packed__)); 76} __attribute__ ((__packed__));
79 77
80/* 78/*
@@ -693,6 +691,17 @@ static inline void btrfs_set_super_blocksize(struct btrfs_super_block *s,
693 s->blocksize = cpu_to_le32(val); 691 s->blocksize = cpu_to_le32(val);
694} 692}
695 693
694static inline u64 btrfs_super_root_dir(struct btrfs_super_block *s)
695{
696 return le64_to_cpu(s->root_dir_objectid);
697}
698
699static inline void btrfs_set_super_root_dir(struct btrfs_super_block *s, u64
700 val)
701{
702 s->root_dir_objectid = cpu_to_le64(val);
703}
704
696static inline u8 *btrfs_leaf_data(struct btrfs_leaf *l) 705static inline u8 *btrfs_leaf_data(struct btrfs_leaf *l)
697{ 706{
698 return (u8 *)l->items; 707 return (u8 *)l->items;
diff --git a/fs/btrfs/debug-tree.c b/fs/btrfs/debug-tree.c
deleted file mode 100644
index fd07969600c6..000000000000
--- a/fs/btrfs/debug-tree.c
+++ /dev/null
@@ -1,38 +0,0 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7#include "print-tree.h"
8#include "transaction.h"
9
10int main(int ac, char **av) {
11 struct btrfs_super_block super;
12 struct btrfs_root *root;
13
14 if (ac != 2) {
15 fprintf(stderr, "usage: %s device\n", av[0]);
16 exit(1);
17 }
18 radix_tree_init();
19 root = open_ctree(av[1], &super);
20 if (!root) {
21 fprintf(stderr, "unable to open %s\n", av[1]);
22 exit(1);
23 }
24 printf("fs tree\n");
25 btrfs_print_tree(root, root->node);
26 printf("map tree\n");
27 btrfs_print_tree(root->fs_info->extent_root,
28 root->fs_info->extent_root->node);
29 printf("inode tree\n");
30 btrfs_print_tree(root->fs_info->inode_root,
31 root->fs_info->inode_root->node);
32 printf("root tree\n");
33 btrfs_print_tree(root->fs_info->tree_root,
34 root->fs_info->tree_root->node);
35 printf("total blocks %Lu\n", btrfs_super_total_blocks(&super));
36 printf("blocks used %Lu\n", btrfs_super_blocks_used(&super));
37 return 0;
38}
diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c
index 949c4e526798..4d8083d92fa0 100644
--- a/fs/btrfs/dir-item.c
+++ b/fs/btrfs/dir-item.c
@@ -1,7 +1,4 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h" 3#include "disk-io.h"
7#include "hash.h" 4#include "hash.h"
@@ -21,7 +18,12 @@ int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
21 key.objectid = dir; 18 key.objectid = dir;
22 key.flags = 0; 19 key.flags = 0;
23 btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY); 20 btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY);
24 ret = btrfs_name_hash(name, name_len, &key.offset); 21 if (name_len == 1 && *name == '.')
22 key.offset = 1;
23 else if (name_len == 2 && name[0] == '.' && name[1] == '.')
24 key.offset = 2;
25 else
26 ret = btrfs_name_hash(name, name_len, &key.offset);
25 BUG_ON(ret); 27 BUG_ON(ret);
26 btrfs_init_path(&path); 28 btrfs_init_path(&path);
27 data_size = sizeof(*dir_item) + name_len; 29 data_size = sizeof(*dir_item) + name_len;
diff --git a/fs/btrfs/dir-test.c b/fs/btrfs/dir-test.c
deleted file mode 100644
index b673982a1f3c..000000000000
--- a/fs/btrfs/dir-test.c
+++ /dev/null
@@ -1,494 +0,0 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <signal.h>
4#include <unistd.h>
5#include "kerncompat.h"
6#include "radix-tree.h"
7#include "ctree.h"
8#include "disk-io.h"
9#include "print-tree.h"
10#include "hash.h"
11#include "transaction.h"
12
13int keep_running = 1;
14struct btrfs_super_block super;
15static u64 dir_oid = 44556;
16static u64 file_oid = 33778;
17
18static int find_num(struct radix_tree_root *root, unsigned long *num_ret,
19 int exists)
20{
21 unsigned long num = rand();
22 unsigned long res[2];
23 int ret;
24
25again:
26 ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
27 if (exists) {
28 if (ret == 0)
29 return -1;
30 num = res[0];
31 } else if (ret != 0 && num == res[0]) {
32 num++;
33 if (ret > 1 && num == res[1]) {
34 num++;
35 goto again;
36 }
37 }
38 *num_ret = num;
39 return 0;
40}
41
42static void initial_inode_init(struct btrfs_root *root,
43 struct btrfs_inode_item *inode_item)
44{
45 memset(inode_item, 0, sizeof(*inode_item));
46 btrfs_set_inode_generation(inode_item, root->fs_info->generation);
47}
48
49static int ins_one(struct btrfs_trans_handle *trans, struct btrfs_root *root,
50 struct radix_tree_root *radix)
51{
52 int ret;
53 char buf[128];
54 unsigned long oid;
55 u64 objectid;
56 struct btrfs_path path;
57 struct btrfs_key inode_map;
58 struct btrfs_inode_item inode_item;
59
60 find_num(radix, &oid, 0);
61 sprintf(buf, "str-%lu", oid);
62
63 ret = btrfs_find_free_objectid(trans, root, dir_oid + 1, &objectid);
64 if (ret)
65 goto error;
66
67 inode_map.objectid = objectid;
68 inode_map.flags = 0;
69 inode_map.offset = 0;
70
71 ret = btrfs_insert_inode_map(trans, root, objectid, &inode_map);
72 if (ret)
73 goto error;
74
75 initial_inode_init(root, &inode_item);
76 ret = btrfs_insert_inode(trans, root, objectid, &inode_item);
77 if (ret)
78 goto error;
79 ret = btrfs_insert_dir_item(trans, root, buf, strlen(buf), dir_oid,
80 objectid, 1);
81 if (ret)
82 goto error;
83
84 radix_tree_preload(GFP_KERNEL);
85 ret = radix_tree_insert(radix, oid, (void *)oid);
86 radix_tree_preload_end();
87 if (ret)
88 goto error;
89 return ret;
90error:
91 if (ret != -EEXIST)
92 goto fatal;
93
94 /*
95 * if we got an EEXIST, it may be due to hash collision, double
96 * check
97 */
98 btrfs_init_path(&path);
99 ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
100 strlen(buf), 0);
101 if (ret)
102 goto fatal_release;
103 if (!btrfs_match_dir_item_name(root, &path, buf, strlen(buf))) {
104 struct btrfs_dir_item *di;
105 char *found;
106 u32 found_len;
107 u64 myhash;
108 u64 foundhash;
109
110 di = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
111 struct btrfs_dir_item);
112 found = (char *)(di + 1);
113 found_len = btrfs_dir_name_len(di);
114 btrfs_name_hash(buf, strlen(buf), &myhash);
115 btrfs_name_hash(found, found_len, &foundhash);
116 if (myhash != foundhash)
117 goto fatal_release;
118 btrfs_release_path(root, &path);
119 return 0;
120 }
121fatal_release:
122 btrfs_release_path(root, &path);
123fatal:
124 printf("failed to insert %lu ret %d\n", oid, ret);
125 return -1;
126}
127
128static int insert_dup(struct btrfs_trans_handle *trans, struct btrfs_root
129 *root, struct radix_tree_root *radix)
130{
131 int ret;
132 char buf[128];
133 unsigned long oid;
134
135 ret = find_num(radix, &oid, 1);
136 if (ret < 0)
137 return 0;
138 sprintf(buf, "str-%lu", oid);
139
140 ret = btrfs_insert_dir_item(trans, root, buf, strlen(buf), dir_oid,
141 file_oid, 1);
142 if (ret != -EEXIST) {
143 printf("insert on %s gave us %d\n", buf, ret);
144 return 1;
145 }
146 return 0;
147}
148
149static int del_dir_item(struct btrfs_trans_handle *trans,
150 struct btrfs_root *root,
151 struct radix_tree_root *radix,
152 unsigned long radix_index,
153 struct btrfs_path *path)
154{
155 int ret;
156 unsigned long *ptr;
157 u64 file_objectid;
158 struct btrfs_dir_item *di;
159
160 /* find the inode number of the file */
161 di = btrfs_item_ptr(&path->nodes[0]->leaf, path->slots[0],
162 struct btrfs_dir_item);
163 file_objectid = btrfs_dir_objectid(di);
164
165 /* delete the directory item */
166 ret = btrfs_del_item(trans, root, path);
167 if (ret)
168 goto out_release;
169 btrfs_release_path(root, path);
170
171 /* delete the inode */
172 btrfs_init_path(path);
173 ret = btrfs_lookup_inode(trans, root, path, file_objectid, -1);
174 if (ret)
175 goto out_release;
176 ret = btrfs_del_item(trans, root, path);
177 if (ret)
178 goto out_release;
179 btrfs_release_path(root, path);
180
181 /* delete the inode mapping */
182 btrfs_init_path(path);
183 ret = btrfs_lookup_inode_map(trans, root, path, file_objectid, -1);
184 if (ret)
185 goto out_release;
186 ret = btrfs_del_item(trans, root->fs_info->inode_root, path);
187 if (ret)
188 goto out_release;
189
190 if (root->fs_info->last_inode_alloc > file_objectid)
191 root->fs_info->last_inode_alloc = file_objectid;
192 btrfs_release_path(root, path);
193 ptr = radix_tree_delete(radix, radix_index);
194 if (!ptr) {
195 ret = -5555;
196 goto out;
197 }
198 return 0;
199out_release:
200 btrfs_release_path(root, path);
201out:
202 printf("failed to delete %lu %d\n", radix_index, ret);
203 return -1;
204}
205
206static int del_one(struct btrfs_trans_handle *trans, struct btrfs_root *root,
207 struct radix_tree_root *radix)
208{
209 int ret;
210 char buf[128];
211 unsigned long oid;
212 struct btrfs_path path;
213
214 ret = find_num(radix, &oid, 1);
215 if (ret < 0)
216 return 0;
217 sprintf(buf, "str-%lu", oid);
218 btrfs_init_path(&path);
219 ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
220 strlen(buf), -1);
221 if (ret)
222 goto out_release;
223
224 ret = del_dir_item(trans, root, radix, oid, &path);
225 if (ret)
226 goto out_release;
227 return ret;
228out_release:
229 btrfs_release_path(root, &path);
230 printf("failed to delete %lu %d\n", oid, ret);
231 return -1;
232}
233
234static int lookup_item(struct btrfs_trans_handle *trans, struct btrfs_root
235 *root, struct radix_tree_root *radix)
236{
237 struct btrfs_path path;
238 char buf[128];
239 int ret;
240 unsigned long oid;
241 u64 objectid;
242 struct btrfs_dir_item *di;
243
244 ret = find_num(radix, &oid, 1);
245 if (ret < 0)
246 return 0;
247 sprintf(buf, "str-%lu", oid);
248 btrfs_init_path(&path);
249 ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
250 strlen(buf), 0);
251 if (!ret) {
252 di = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
253 struct btrfs_dir_item);
254 objectid = btrfs_dir_objectid(di);
255 btrfs_release_path(root, &path);
256 btrfs_init_path(&path);
257 ret = btrfs_lookup_inode_map(trans, root, &path, objectid, 0);
258 }
259 btrfs_release_path(root, &path);
260 if (ret) {
261 printf("unable to find key %lu\n", oid);
262 return -1;
263 }
264 return 0;
265}
266
267static int lookup_enoent(struct btrfs_trans_handle *trans, struct btrfs_root
268 *root, struct radix_tree_root *radix)
269{
270 struct btrfs_path path;
271 char buf[128];
272 int ret;
273 unsigned long oid;
274
275 ret = find_num(radix, &oid, 0);
276 if (ret < 0)
277 return 0;
278 sprintf(buf, "str-%lu", oid);
279 btrfs_init_path(&path);
280 ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
281 strlen(buf), 0);
282 btrfs_release_path(root, &path);
283 if (!ret) {
284 printf("able to find key that should not exist %lu\n", oid);
285 return -1;
286 }
287 return 0;
288}
289
290static int empty_tree(struct btrfs_trans_handle *trans, struct btrfs_root
291 *root, struct radix_tree_root *radix, int nr)
292{
293 struct btrfs_path path;
294 struct btrfs_key key;
295 unsigned long found = 0;
296 u32 found_len;
297 int ret;
298 int slot;
299 int count = 0;
300 char buf[128];
301 struct btrfs_dir_item *di;
302
303 key.offset = (u64)-1;
304 key.flags = 0;
305 btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY);
306 key.objectid = dir_oid;
307 while(nr-- >= 0) {
308 btrfs_init_path(&path);
309 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
310 if (ret < 0) {
311 btrfs_release_path(root, &path);
312 return ret;
313 }
314 if (ret != 0) {
315 if (path.slots[0] == 0) {
316 btrfs_release_path(root, &path);
317 break;
318 }
319 path.slots[0] -= 1;
320 }
321 slot = path.slots[0];
322 di = btrfs_item_ptr(&path.nodes[0]->leaf, slot,
323 struct btrfs_dir_item);
324 found_len = btrfs_dir_name_len(di);
325 memcpy(buf, (char *)(di + 1), found_len);
326 BUG_ON(found_len > 128);
327 buf[found_len] = '\0';
328 found = atoi(buf + 4);
329 ret = del_dir_item(trans, root, radix, found, &path);
330 count++;
331 if (ret) {
332 fprintf(stderr,
333 "failed to remove %lu from tree\n",
334 found);
335 return -1;
336 }
337 if (!keep_running)
338 break;
339 }
340 return 0;
341 fprintf(stderr, "failed to delete from the radix %lu\n", found);
342 return -1;
343}
344
345static int fill_tree(struct btrfs_trans_handle *trans, struct btrfs_root *root,
346 struct radix_tree_root *radix, int count)
347{
348 int i;
349 int ret = 0;
350 for (i = 0; i < count; i++) {
351 ret = ins_one(trans, root, radix);
352 if (ret) {
353 fprintf(stderr, "fill failed\n");
354 goto out;
355 }
356 if (i % 1000 == 0) {
357 ret = btrfs_commit_transaction(trans, root, &super);
358 if (ret) {
359 fprintf(stderr, "fill commit failed\n");
360 return ret;
361 }
362 }
363 if (i && i % 10000 == 0) {
364 printf("bigfill %d\n", i);
365 }
366 if (!keep_running)
367 break;
368 }
369out:
370 return ret;
371}
372
373static int bulk_op(struct btrfs_trans_handle *trans, struct btrfs_root *root,
374 struct radix_tree_root *radix)
375{
376 int ret;
377 int nr = rand() % 5000;
378 static int run_nr = 0;
379
380 /* do the bulk op much less frequently */
381 if (run_nr++ % 100)
382 return 0;
383 ret = empty_tree(trans, root, radix, nr);
384 if (ret)
385 return ret;
386 ret = fill_tree(trans, root, radix, nr);
387 if (ret)
388 return ret;
389 return 0;
390}
391
392
393int (*ops[])(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct
394 radix_tree_root *radix) =
395 { ins_one, insert_dup, del_one, lookup_item,
396 lookup_enoent, bulk_op };
397
398void sigstopper(int ignored)
399{
400 keep_running = 0;
401 fprintf(stderr, "caught exit signal, stopping\n");
402}
403
404int print_usage(void)
405{
406 printf("usage: tester [-ih] [-c count] [-f count]\n");
407 printf("\t -c count -- iteration count after filling\n");
408 printf("\t -f count -- run this many random inserts before starting\n");
409 printf("\t -i -- only do initial fill\n");
410 printf("\t -h -- this help text\n");
411 exit(1);
412}
413int main(int ac, char **av)
414{
415 RADIX_TREE(radix, GFP_KERNEL);
416 struct btrfs_root *root;
417 int i;
418 int ret;
419 int count;
420 int op;
421 int iterations = 20000;
422 int init_fill_count = 800000;
423 int err = 0;
424 int initial_only = 0;
425 struct btrfs_trans_handle *trans;
426 radix_tree_init();
427
428 root = open_ctree("dbfile", &super);
429 trans = btrfs_start_transaction(root, 1);
430
431 signal(SIGTERM, sigstopper);
432 signal(SIGINT, sigstopper);
433
434 for (i = 1 ; i < ac ; i++) {
435 if (strcmp(av[i], "-i") == 0) {
436 initial_only = 1;
437 } else if (strcmp(av[i], "-c") == 0) {
438 iterations = atoi(av[i+1]);
439 i++;
440 } else if (strcmp(av[i], "-f") == 0) {
441 init_fill_count = atoi(av[i+1]);
442 i++;
443 } else {
444 print_usage();
445 }
446 }
447 printf("initial fill\n");
448 ret = fill_tree(trans, root, &radix, init_fill_count);
449 printf("starting run\n");
450 if (ret) {
451 err = ret;
452 goto out;
453 }
454 if (initial_only == 1) {
455 goto out;
456 }
457 for (i = 0; i < iterations; i++) {
458 op = rand() % ARRAY_SIZE(ops);
459 count = rand() % 128;
460 if (i % 2000 == 0) {
461 printf("%d\n", i);
462 fflush(stdout);
463 }
464 if (i && i % 5000 == 0) {
465 printf("open & close, root level %d nritems %d\n",
466 btrfs_header_level(&root->node->node.header),
467 btrfs_header_nritems(&root->node->node.header));
468 close_ctree(root, &super);
469 root = open_ctree("dbfile", &super);
470 }
471 while(count--) {
472 ret = ops[op](trans, root, &radix);
473 if (ret) {
474 fprintf(stderr, "op %d failed %d:%d\n",
475 op, i, iterations);
476 btrfs_print_tree(root, root->node);
477 fprintf(stderr, "op %d failed %d:%d\n",
478 op, i, iterations);
479 err = ret;
480 goto out;
481 }
482 if (ops[op] == bulk_op)
483 break;
484 if (keep_running == 0) {
485 err = 0;
486 goto out;
487 }
488 }
489 }
490out:
491 close_ctree(root, &super);
492 return err;
493}
494
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 0322c55162cb..05637f9fd7c7 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -267,19 +267,24 @@ static int find_and_setup_root(struct btrfs_super_block *super,
267 267
268struct btrfs_root *open_ctree(char *filename, struct btrfs_super_block *super) 268struct btrfs_root *open_ctree(char *filename, struct btrfs_super_block *super)
269{ 269{
270 int fp;
271
272 fp = open(filename, O_CREAT | O_RDWR, 0600);
273 if (fp < 0) {
274 return NULL;
275 }
276 return open_ctree_fd(fp, super);
277}
278
279struct btrfs_root *open_ctree_fd(int fp, struct btrfs_super_block *super)
280{
270 struct btrfs_root *root = malloc(sizeof(struct btrfs_root)); 281 struct btrfs_root *root = malloc(sizeof(struct btrfs_root));
271 struct btrfs_root *extent_root = malloc(sizeof(struct btrfs_root)); 282 struct btrfs_root *extent_root = malloc(sizeof(struct btrfs_root));
272 struct btrfs_root *tree_root = malloc(sizeof(struct btrfs_root)); 283 struct btrfs_root *tree_root = malloc(sizeof(struct btrfs_root));
273 struct btrfs_root *inode_root = malloc(sizeof(struct btrfs_root)); 284 struct btrfs_root *inode_root = malloc(sizeof(struct btrfs_root));
274 struct btrfs_fs_info *fs_info = malloc(sizeof(*fs_info)); 285 struct btrfs_fs_info *fs_info = malloc(sizeof(*fs_info));
275 int fp;
276 int ret; 286 int ret;
277 287
278 fp = open(filename, O_CREAT | O_RDWR, 0600);
279 if (fp < 0) {
280 free(root);
281 return NULL;
282 }
283 INIT_RADIX_TREE(&fs_info->cache_radix, GFP_KERNEL); 288 INIT_RADIX_TREE(&fs_info->cache_radix, GFP_KERNEL);
284 INIT_RADIX_TREE(&fs_info->pinned_radix, GFP_KERNEL); 289 INIT_RADIX_TREE(&fs_info->pinned_radix, GFP_KERNEL);
285 INIT_LIST_HEAD(&fs_info->trans); 290 INIT_LIST_HEAD(&fs_info->trans);
diff --git a/fs/btrfs/disk-io.h b/fs/btrfs/disk-io.h
index 24a9e77c8311..d888cf5c350b 100644
--- a/fs/btrfs/disk-io.h
+++ b/fs/btrfs/disk-io.h
@@ -24,6 +24,7 @@ int clean_tree_block(struct btrfs_trans_handle *trans,
24int btrfs_commit_transaction(struct btrfs_trans_handle *trans, struct btrfs_root 24int btrfs_commit_transaction(struct btrfs_trans_handle *trans, struct btrfs_root
25 *root, struct btrfs_super_block *s); 25 *root, struct btrfs_super_block *s);
26struct btrfs_root *open_ctree(char *filename, struct btrfs_super_block *s); 26struct btrfs_root *open_ctree(char *filename, struct btrfs_super_block *s);
27struct btrfs_root *open_ctree_fd(int fp, struct btrfs_super_block *super);
27int close_ctree(struct btrfs_root *root, struct btrfs_super_block *s); 28int close_ctree(struct btrfs_root *root, struct btrfs_super_block *s);
28void btrfs_block_release(struct btrfs_root *root, struct btrfs_buffer *buf); 29void btrfs_block_release(struct btrfs_root *root, struct btrfs_buffer *buf);
29int write_ctree_super(struct btrfs_trans_handle *trans, struct btrfs_root *root, 30int write_ctree_super(struct btrfs_trans_handle *trans, struct btrfs_root *root,
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 9bc4ad38876d..53a7550b5c1e 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -1,7 +1,5 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h> 2#include <linux/radix-tree.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 3#include "ctree.h"
6#include "disk-io.h" 4#include "disk-io.h"
7#include "print-tree.h" 5#include "print-tree.h"
@@ -183,9 +181,9 @@ static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
183 btrfs_init_path(&path); 181 btrfs_init_path(&path);
184 ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1); 182 ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
185 if (ret) { 183 if (ret) {
186 printf("failed to find %Lu\n", key.objectid); 184 printk("failed to find %Lu\n", key.objectid);
187 btrfs_print_tree(extent_root, extent_root->node); 185 btrfs_print_tree(extent_root, extent_root->node);
188 printf("failed to find %Lu\n", key.objectid); 186 printk("failed to find %Lu\n", key.objectid);
189 BUG(); 187 BUG();
190 } 188 }
191 ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], 189 ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
diff --git a/fs/btrfs/file-item.c b/fs/btrfs/file-item.c
index 24cfd6d85240..8e1e5b4ccfaf 100644
--- a/fs/btrfs/file-item.c
+++ b/fs/btrfs/file-item.c
@@ -1,9 +1,5 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h"
7#include "transaction.h" 3#include "transaction.h"
8 4
9int btrfs_create_file(struct btrfs_trans_handle *trans, 5int btrfs_create_file(struct btrfs_trans_handle *trans,
diff --git a/fs/btrfs/hash.c b/fs/btrfs/hash.c
index 92c37eece1f2..6c2a71a46c7d 100644
--- a/fs/btrfs/hash.c
+++ b/fs/btrfs/hash.c
@@ -10,7 +10,6 @@
10 * License. 10 * License.
11 */ 11 */
12 12
13#include "kerncompat.h"
14#define DELTA 0x9E3779B9 13#define DELTA 0x9E3779B9
15 14
16static void TEA_transform(__u32 buf[2], __u32 const in[]) 15static void TEA_transform(__u32 buf[2], __u32 const in[])
diff --git a/fs/btrfs/hasher.c b/fs/btrfs/hasher.c
deleted file mode 100644
index 96702da4329c..000000000000
--- a/fs/btrfs/hasher.c
+++ /dev/null
@@ -1,23 +0,0 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include "kerncompat.h"
5#include "hash.h"
6
7int main() {
8 u64 result;
9 int ret;
10 char line[255];
11 char *p;
12 while(1) {
13 p = fgets(line, 255, stdin);
14 if (!p)
15 break;
16 if (strlen(line) == 0)
17 continue;
18 ret = btrfs_name_hash(line, strlen(line), &result);
19 BUG_ON(ret);
20 printf("hash returns %Lu\n", result);
21 }
22 return 0;
23}
diff --git a/fs/btrfs/inode-item.c b/fs/btrfs/inode-item.c
index 7caeb11e8756..8d8c26a6c1a0 100644
--- a/fs/btrfs/inode-item.c
+++ b/fs/btrfs/inode-item.c
@@ -1,7 +1,4 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h" 3#include "disk-io.h"
7#include "transaction.h" 4#include "transaction.h"
diff --git a/fs/btrfs/inode-map.c b/fs/btrfs/inode-map.c
index f412b3392135..c7fda3bf7b21 100644
--- a/fs/btrfs/inode-map.c
+++ b/fs/btrfs/inode-map.c
@@ -1,7 +1,4 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h" 3#include "disk-io.h"
7#include "transaction.h" 4#include "transaction.h"
diff --git a/fs/btrfs/kerncompat.h b/fs/btrfs/kerncompat.h
deleted file mode 100644
index 105d3f584089..000000000000
--- a/fs/btrfs/kerncompat.h
+++ /dev/null
@@ -1,96 +0,0 @@
1#ifndef __KERNCOMPAT
2#define __KERNCOMPAT
3#define gfp_t int
4#define get_cpu_var(p) (p)
5#define __get_cpu_var(p) (p)
6#define BITS_PER_LONG 64
7#define __GFP_BITS_SHIFT 20
8#define __GFP_BITS_MASK ((int)((1 << __GFP_BITS_SHIFT) - 1))
9#define GFP_KERNEL 0
10#define __read_mostly
11#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
12#define PAGE_SHIFT 12
13#define ULONG_MAX (~0UL)
14#define BUG() abort()
15#ifdef __CHECKER__
16#define __force __attribute__((force))
17#define __bitwise__ __attribute__((bitwise))
18#else
19#define __force
20#define __bitwise__
21#endif
22
23typedef unsigned int u32;
24typedef u32 __u32;
25typedef unsigned long long u64;
26typedef unsigned char u8;
27typedef unsigned short u16;
28
29typedef unsigned long pgoff_t;
30
31#include <stdio.h>
32#include <stdlib.h>
33#include <string.h>
34
35struct vma_shared { int prio_tree_node; };
36struct vm_area_struct {
37 unsigned long vm_pgoff;
38 unsigned long vm_start;
39 unsigned long vm_end;
40 struct vma_shared shared;
41};
42
43struct page {
44 unsigned long index;
45};
46
47static inline void preempt_enable(void) { do {; } while(0);}
48static inline void preempt_disable(void) { do {; } while(0);}
49
50static inline void __set_bit(int bit, unsigned long *map) {
51 unsigned long *p = map + bit / BITS_PER_LONG;
52 bit = bit & (BITS_PER_LONG -1);
53 *p |= 1UL << bit;
54}
55
56static inline int test_bit(int bit, unsigned long *map) {
57 unsigned long *p = map + bit / BITS_PER_LONG;
58 bit = bit & (BITS_PER_LONG -1);
59 return *p & (1UL << bit) ? 1 : 0;
60}
61
62static inline void __clear_bit(int bit, unsigned long *map) {
63 unsigned long *p = map + bit / BITS_PER_LONG;
64 bit = bit & (BITS_PER_LONG -1);
65 *p &= ~(1UL << bit);
66}
67#define BUG_ON(c) do { if (c) abort(); } while (0)
68
69#define container_of(ptr, type, member) ({ \
70 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
71 (type *)( (char *)__mptr - __builtin_offsetof(type,member) );})
72
73#define ENOMEM 5
74#define EEXIST 6
75
76#define __CHECK_ENDIAN__
77#ifdef __CHECK_ENDIAN__
78#define __bitwise __bitwise__
79#else
80#define __bitwise
81#endif
82
83typedef u16 __bitwise __le16;
84typedef u16 __bitwise __be16;
85typedef u32 __bitwise __le32;
86typedef u32 __bitwise __be32;
87typedef u64 __bitwise __le64;
88typedef u64 __bitwise __be64;
89
90#define cpu_to_le64(x) ((__force __le64)(u64)(x))
91#define le64_to_cpu(x) ((__force u64)(__le64)(x))
92#define cpu_to_le32(x) ((__force __le32)(u32)(x))
93#define le32_to_cpu(x) ((__force u32)(__le32)(x))
94#define cpu_to_le16(x) ((__force __le16)(u16)(x))
95#define le16_to_cpu(x) ((__force u16)(__le16)(x))
96#endif
diff --git a/fs/btrfs/list.h b/fs/btrfs/list.h
deleted file mode 100644
index 1aafafb13370..000000000000
--- a/fs/btrfs/list.h
+++ /dev/null
@@ -1,418 +0,0 @@
1#ifndef _LINUX_LIST_H
2#define _LINUX_LIST_H
3
4#define LIST_POISON1 ((void *) 0x00100100)
5#define LIST_POISON2 ((void *) 0x00200200)
6
7/*
8 * Simple doubly linked list implementation.
9 *
10 * Some of the internal functions ("__xxx") are useful when
11 * manipulating whole lists rather than single entries, as
12 * sometimes we already know the next/prev entries and we can
13 * generate better code by using them directly rather than
14 * using the generic single-entry routines.
15 */
16
17struct list_head {
18 struct list_head *next, *prev;
19};
20
21#define LIST_HEAD_INIT(name) { &(name), &(name) }
22
23#define LIST_HEAD(name) \
24 struct list_head name = LIST_HEAD_INIT(name)
25
26static inline void INIT_LIST_HEAD(struct list_head *list)
27{
28 list->next = list;
29 list->prev = list;
30}
31
32/*
33 * Insert a new entry between two known consecutive entries.
34 *
35 * This is only for internal list manipulation where we know
36 * the prev/next entries already!
37 */
38#ifndef CONFIG_DEBUG_LIST
39static inline void __list_add(struct list_head *new,
40 struct list_head *prev,
41 struct list_head *next)
42{
43 next->prev = new;
44 new->next = next;
45 new->prev = prev;
46 prev->next = new;
47}
48#else
49extern void __list_add(struct list_head *new,
50 struct list_head *prev,
51 struct list_head *next);
52#endif
53
54/**
55 * list_add - add a new entry
56 * @new: new entry to be added
57 * @head: list head to add it after
58 *
59 * Insert a new entry after the specified head.
60 * This is good for implementing stacks.
61 */
62#ifndef CONFIG_DEBUG_LIST
63static inline void list_add(struct list_head *new, struct list_head *head)
64{
65 __list_add(new, head, head->next);
66}
67#else
68extern void list_add(struct list_head *new, struct list_head *head);
69#endif
70
71
72/**
73 * list_add_tail - add a new entry
74 * @new: new entry to be added
75 * @head: list head to add it before
76 *
77 * Insert a new entry before the specified head.
78 * This is useful for implementing queues.
79 */
80static inline void list_add_tail(struct list_head *new, struct list_head *head)
81{
82 __list_add(new, head->prev, head);
83}
84
85/*
86 * Delete a list entry by making the prev/next entries
87 * point to each other.
88 *
89 * This is only for internal list manipulation where we know
90 * the prev/next entries already!
91 */
92static inline void __list_del(struct list_head * prev, struct list_head * next)
93{
94 next->prev = prev;
95 prev->next = next;
96}
97
98/**
99 * list_del - deletes entry from list.
100 * @entry: the element to delete from the list.
101 * Note: list_empty on entry does not return true after this, the entry is
102 * in an undefined state.
103 */
104#ifndef CONFIG_DEBUG_LIST
105static inline void list_del(struct list_head *entry)
106{
107 __list_del(entry->prev, entry->next);
108 entry->next = LIST_POISON1;
109 entry->prev = LIST_POISON2;
110}
111#else
112extern void list_del(struct list_head *entry);
113#endif
114
115/**
116 * list_replace - replace old entry by new one
117 * @old : the element to be replaced
118 * @new : the new element to insert
119 * Note: if 'old' was empty, it will be overwritten.
120 */
121static inline void list_replace(struct list_head *old,
122 struct list_head *new)
123{
124 new->next = old->next;
125 new->next->prev = new;
126 new->prev = old->prev;
127 new->prev->next = new;
128}
129
130static inline void list_replace_init(struct list_head *old,
131 struct list_head *new)
132{
133 list_replace(old, new);
134 INIT_LIST_HEAD(old);
135}
136/**
137 * list_del_init - deletes entry from list and reinitialize it.
138 * @entry: the element to delete from the list.
139 */
140static inline void list_del_init(struct list_head *entry)
141{
142 __list_del(entry->prev, entry->next);
143 INIT_LIST_HEAD(entry);
144}
145
146/**
147 * list_move - delete from one list and add as another's head
148 * @list: the entry to move
149 * @head: the head that will precede our entry
150 */
151static inline void list_move(struct list_head *list, struct list_head *head)
152{
153 __list_del(list->prev, list->next);
154 list_add(list, head);
155}
156
157/**
158 * list_move_tail - delete from one list and add as another's tail
159 * @list: the entry to move
160 * @head: the head that will follow our entry
161 */
162static inline void list_move_tail(struct list_head *list,
163 struct list_head *head)
164{
165 __list_del(list->prev, list->next);
166 list_add_tail(list, head);
167}
168
169/**
170 * list_is_last - tests whether @list is the last entry in list @head
171 * @list: the entry to test
172 * @head: the head of the list
173 */
174static inline int list_is_last(const struct list_head *list,
175 const struct list_head *head)
176{
177 return list->next == head;
178}
179
180/**
181 * list_empty - tests whether a list is empty
182 * @head: the list to test.
183 */
184static inline int list_empty(const struct list_head *head)
185{
186 return head->next == head;
187}
188
189/**
190 * list_empty_careful - tests whether a list is empty and not being modified
191 * @head: the list to test
192 *
193 * Description:
194 * tests whether a list is empty _and_ checks that no other CPU might be
195 * in the process of modifying either member (next or prev)
196 *
197 * NOTE: using list_empty_careful() without synchronization
198 * can only be safe if the only activity that can happen
199 * to the list entry is list_del_init(). Eg. it cannot be used
200 * if another CPU could re-list_add() it.
201 */
202static inline int list_empty_careful(const struct list_head *head)
203{
204 struct list_head *next = head->next;
205 return (next == head) && (next == head->prev);
206}
207
208static inline void __list_splice(struct list_head *list,
209 struct list_head *head)
210{
211 struct list_head *first = list->next;
212 struct list_head *last = list->prev;
213 struct list_head *at = head->next;
214
215 first->prev = head;
216 head->next = first;
217
218 last->next = at;
219 at->prev = last;
220}
221
222/**
223 * list_splice - join two lists
224 * @list: the new list to add.
225 * @head: the place to add it in the first list.
226 */
227static inline void list_splice(struct list_head *list, struct list_head *head)
228{
229 if (!list_empty(list))
230 __list_splice(list, head);
231}
232
233/**
234 * list_splice_init - join two lists and reinitialise the emptied list.
235 * @list: the new list to add.
236 * @head: the place to add it in the first list.
237 *
238 * The list at @list is reinitialised
239 */
240static inline void list_splice_init(struct list_head *list,
241 struct list_head *head)
242{
243 if (!list_empty(list)) {
244 __list_splice(list, head);
245 INIT_LIST_HEAD(list);
246 }
247}
248
249/**
250 * list_entry - get the struct for this entry
251 * @ptr: the &struct list_head pointer.
252 * @type: the type of the struct this is embedded in.
253 * @member: the name of the list_struct within the struct.
254 */
255#define list_entry(ptr, type, member) \
256 container_of(ptr, type, member)
257
258/**
259 * list_for_each - iterate over a list
260 * @pos: the &struct list_head to use as a loop cursor.
261 * @head: the head for your list.
262 */
263#define list_for_each(pos, head) \
264 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
265 pos = pos->next)
266
267/**
268 * __list_for_each - iterate over a list
269 * @pos: the &struct list_head to use as a loop cursor.
270 * @head: the head for your list.
271 *
272 * This variant differs from list_for_each() in that it's the
273 * simplest possible list iteration code, no prefetching is done.
274 * Use this for code that knows the list to be very short (empty
275 * or 1 entry) most of the time.
276 */
277#define __list_for_each(pos, head) \
278 for (pos = (head)->next; pos != (head); pos = pos->next)
279
280/**
281 * list_for_each_prev - iterate over a list backwards
282 * @pos: the &struct list_head to use as a loop cursor.
283 * @head: the head for your list.
284 */
285#define list_for_each_prev(pos, head) \
286 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
287 pos = pos->prev)
288
289/**
290 * list_for_each_safe - iterate over a list safe against removal of list entry
291 * @pos: the &struct list_head to use as a loop cursor.
292 * @n: another &struct list_head to use as temporary storage
293 * @head: the head for your list.
294 */
295#define list_for_each_safe(pos, n, head) \
296 for (pos = (head)->next, n = pos->next; pos != (head); \
297 pos = n, n = pos->next)
298
299/**
300 * list_for_each_entry - iterate over list of given type
301 * @pos: the type * to use as a loop cursor.
302 * @head: the head for your list.
303 * @member: the name of the list_struct within the struct.
304 */
305#define list_for_each_entry(pos, head, member) \
306 for (pos = list_entry((head)->next, typeof(*pos), member); \
307 prefetch(pos->member.next), &pos->member != (head); \
308 pos = list_entry(pos->member.next, typeof(*pos), member))
309
310/**
311 * list_for_each_entry_reverse - iterate backwards over list of given type.
312 * @pos: the type * to use as a loop cursor.
313 * @head: the head for your list.
314 * @member: the name of the list_struct within the struct.
315 */
316#define list_for_each_entry_reverse(pos, head, member) \
317 for (pos = list_entry((head)->prev, typeof(*pos), member); \
318 prefetch(pos->member.prev), &pos->member != (head); \
319 pos = list_entry(pos->member.prev, typeof(*pos), member))
320
321/**
322 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue
323 * @pos: the type * to use as a start point
324 * @head: the head of the list
325 * @member: the name of the list_struct within the struct.
326 *
327 * Prepares a pos entry for use as a start point in list_for_each_entry_continue.
328 */
329#define list_prepare_entry(pos, head, member) \
330 ((pos) ? : list_entry(head, typeof(*pos), member))
331
332/**
333 * list_for_each_entry_continue - continue iteration over list of given type
334 * @pos: the type * to use as a loop cursor.
335 * @head: the head for your list.
336 * @member: the name of the list_struct within the struct.
337 *
338 * Continue to iterate over list of given type, continuing after
339 * the current position.
340 */
341#define list_for_each_entry_continue(pos, head, member) \
342 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
343 prefetch(pos->member.next), &pos->member != (head); \
344 pos = list_entry(pos->member.next, typeof(*pos), member))
345
346/**
347 * list_for_each_entry_from - iterate over list of given type from the current point
348 * @pos: the type * to use as a loop cursor.
349 * @head: the head for your list.
350 * @member: the name of the list_struct within the struct.
351 *
352 * Iterate over list of given type, continuing from current position.
353 */
354#define list_for_each_entry_from(pos, head, member) \
355 for (; prefetch(pos->member.next), &pos->member != (head); \
356 pos = list_entry(pos->member.next, typeof(*pos), member))
357
358/**
359 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
360 * @pos: the type * to use as a loop cursor.
361 * @n: another type * to use as temporary storage
362 * @head: the head for your list.
363 * @member: the name of the list_struct within the struct.
364 */
365#define list_for_each_entry_safe(pos, n, head, member) \
366 for (pos = list_entry((head)->next, typeof(*pos), member), \
367 n = list_entry(pos->member.next, typeof(*pos), member); \
368 &pos->member != (head); \
369 pos = n, n = list_entry(n->member.next, typeof(*n), member))
370
371/**
372 * list_for_each_entry_safe_continue
373 * @pos: the type * to use as a loop cursor.
374 * @n: another type * to use as temporary storage
375 * @head: the head for your list.
376 * @member: the name of the list_struct within the struct.
377 *
378 * Iterate over list of given type, continuing after current point,
379 * safe against removal of list entry.
380 */
381#define list_for_each_entry_safe_continue(pos, n, head, member) \
382 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
383 n = list_entry(pos->member.next, typeof(*pos), member); \
384 &pos->member != (head); \
385 pos = n, n = list_entry(n->member.next, typeof(*n), member))
386
387/**
388 * list_for_each_entry_safe_from
389 * @pos: the type * to use as a loop cursor.
390 * @n: another type * to use as temporary storage
391 * @head: the head for your list.
392 * @member: the name of the list_struct within the struct.
393 *
394 * Iterate over list of given type from current point, safe against
395 * removal of list entry.
396 */
397#define list_for_each_entry_safe_from(pos, n, head, member) \
398 for (n = list_entry(pos->member.next, typeof(*pos), member); \
399 &pos->member != (head); \
400 pos = n, n = list_entry(n->member.next, typeof(*n), member))
401
402/**
403 * list_for_each_entry_safe_reverse
404 * @pos: the type * to use as a loop cursor.
405 * @n: another type * to use as temporary storage
406 * @head: the head for your list.
407 * @member: the name of the list_struct within the struct.
408 *
409 * Iterate backwards over list of given type, safe against removal
410 * of list entry.
411 */
412#define list_for_each_entry_safe_reverse(pos, n, head, member) \
413 for (pos = list_entry((head)->prev, typeof(*pos), member), \
414 n = list_entry(pos->member.prev, typeof(*pos), member); \
415 &pos->member != (head); \
416 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
417
418#endif
diff --git a/fs/btrfs/mkfs.c b/fs/btrfs/mkfs.c
deleted file mode 100644
index f7efc8a5fb1a..000000000000
--- a/fs/btrfs/mkfs.c
+++ /dev/null
@@ -1,255 +0,0 @@
1#define _XOPEN_SOURCE 500
2#ifndef __CHECKER__
3#include <sys/ioctl.h>
4#include <sys/mount.h>
5#endif
6#include <stdio.h>
7#include <stdlib.h>
8#include <sys/types.h>
9#include <sys/stat.h>
10#include <fcntl.h>
11#include <unistd.h>
12#include "kerncompat.h"
13#include "radix-tree.h"
14#include "ctree.h"
15#include "disk-io.h"
16
17#ifdef __CHECKER__
18#define BLKGETSIZE64 0
19static inline int ioctl(int fd, int define, u64 *size) { return 0; }
20#endif
21
22#if 0
23#if defined(__linux__) && defined(_IOR) && !defined(BLKGETSIZE64)
24# define BLKGETSIZE64 _IOR(0x12, 114, __u64)
25#endif
26#endif
27
28int mkfs(int fd, u64 num_blocks, u32 blocksize)
29{
30 struct btrfs_super_block super;
31 struct btrfs_leaf *empty_leaf;
32 struct btrfs_root_item root_item;
33 struct btrfs_item item;
34 struct btrfs_extent_item extent_item;
35 char *block;
36 int ret;
37 u32 itemoff;
38 u32 start_block = BTRFS_SUPER_INFO_OFFSET / blocksize;
39
40 btrfs_set_super_blocknr(&super, start_block);
41 btrfs_set_super_root(&super, start_block + 1);
42 strcpy((char *)(&super.magic), BTRFS_MAGIC);
43 btrfs_set_super_blocksize(&super, blocksize);
44 btrfs_set_super_total_blocks(&super, num_blocks);
45 btrfs_set_super_blocks_used(&super, start_block + 5);
46
47 block = malloc(blocksize);
48 memset(block, 0, blocksize);
49 BUG_ON(sizeof(super) > blocksize);
50 memcpy(block, &super, sizeof(super));
51 ret = pwrite(fd, block, blocksize, BTRFS_SUPER_INFO_OFFSET);
52 BUG_ON(ret != blocksize);
53
54 /* create the tree of root objects */
55 empty_leaf = malloc(blocksize);
56 memset(empty_leaf, 0, blocksize);
57 btrfs_set_header_parentid(&empty_leaf->header,
58 BTRFS_ROOT_TREE_OBJECTID);
59 btrfs_set_header_blocknr(&empty_leaf->header, start_block + 1);
60 btrfs_set_header_nritems(&empty_leaf->header, 3);
61
62 /* create the items for the root tree */
63 btrfs_set_root_blocknr(&root_item, start_block + 2);
64 btrfs_set_root_refs(&root_item, 1);
65 itemoff = __BTRFS_LEAF_DATA_SIZE(blocksize) - sizeof(root_item);
66 btrfs_set_item_offset(&item, itemoff);
67 btrfs_set_item_size(&item, sizeof(root_item));
68 btrfs_set_disk_key_objectid(&item.key, BTRFS_EXTENT_TREE_OBJECTID);
69 btrfs_set_disk_key_offset(&item.key, 0);
70 btrfs_set_disk_key_flags(&item.key, 0);
71 btrfs_set_disk_key_type(&item.key, BTRFS_ROOT_ITEM_KEY);
72 memcpy(empty_leaf->items, &item, sizeof(item));
73 memcpy(btrfs_leaf_data(empty_leaf) + itemoff,
74 &root_item, sizeof(root_item));
75
76 btrfs_set_root_blocknr(&root_item, start_block + 3);
77 itemoff = itemoff - sizeof(root_item);
78 btrfs_set_item_offset(&item, itemoff);
79 btrfs_set_disk_key_objectid(&item.key, BTRFS_INODE_MAP_OBJECTID);
80 memcpy(empty_leaf->items + 1, &item, sizeof(item));
81 memcpy(btrfs_leaf_data(empty_leaf) + itemoff,
82 &root_item, sizeof(root_item));
83
84 btrfs_set_root_blocknr(&root_item, start_block + 4);
85 itemoff = itemoff - sizeof(root_item);
86 btrfs_set_item_offset(&item, itemoff);
87 btrfs_set_disk_key_objectid(&item.key, BTRFS_FS_TREE_OBJECTID);
88 memcpy(empty_leaf->items + 2, &item, sizeof(item));
89 memcpy(btrfs_leaf_data(empty_leaf) + itemoff,
90 &root_item, sizeof(root_item));
91 ret = pwrite(fd, empty_leaf, blocksize, (start_block + 1) * blocksize);
92
93 /* create the items for the extent tree */
94 btrfs_set_header_parentid(&empty_leaf->header,
95 BTRFS_EXTENT_TREE_OBJECTID);
96 btrfs_set_header_blocknr(&empty_leaf->header, start_block + 2);
97 btrfs_set_header_nritems(&empty_leaf->header, 5);
98
99 /* item1, reserve blocks 0-16 */
100 btrfs_set_disk_key_objectid(&item.key, 0);
101 btrfs_set_disk_key_offset(&item.key, start_block + 1);
102 btrfs_set_disk_key_flags(&item.key, 0);
103 btrfs_set_disk_key_type(&item.key, BTRFS_EXTENT_ITEM_KEY);
104 itemoff = __BTRFS_LEAF_DATA_SIZE(blocksize) -
105 sizeof(struct btrfs_extent_item);
106 btrfs_set_item_offset(&item, itemoff);
107 btrfs_set_item_size(&item, sizeof(struct btrfs_extent_item));
108 btrfs_set_extent_refs(&extent_item, 1);
109 btrfs_set_extent_owner(&extent_item, 0);
110 memcpy(empty_leaf->items, &item, sizeof(item));
111 memcpy(btrfs_leaf_data(empty_leaf) + btrfs_item_offset(&item),
112 &extent_item, btrfs_item_size(&item));
113
114 /* item2, give block 17 to the root */
115 btrfs_set_disk_key_objectid(&item.key, start_block + 1);
116 btrfs_set_disk_key_offset(&item.key, 1);
117 itemoff = itemoff - sizeof(struct btrfs_extent_item);
118 btrfs_set_item_offset(&item, itemoff);
119 btrfs_set_extent_owner(&extent_item, BTRFS_ROOT_TREE_OBJECTID);
120 memcpy(empty_leaf->items + 1, &item, sizeof(item));
121 memcpy(btrfs_leaf_data(empty_leaf) + btrfs_item_offset(&item),
122 &extent_item, btrfs_item_size(&item));
123
124 /* item3, give block 18 to the extent root */
125 btrfs_set_disk_key_objectid(&item.key, start_block + 2);
126 btrfs_set_disk_key_offset(&item.key, 1);
127 itemoff = itemoff - sizeof(struct btrfs_extent_item);
128 btrfs_set_item_offset(&item, itemoff);
129 btrfs_set_extent_owner(&extent_item, BTRFS_EXTENT_TREE_OBJECTID);
130 memcpy(empty_leaf->items + 2, &item, sizeof(item));
131 memcpy(btrfs_leaf_data(empty_leaf) + btrfs_item_offset(&item),
132 &extent_item, btrfs_item_size(&item));
133
134 /* item4, give block 19 to the inode map */
135 btrfs_set_disk_key_objectid(&item.key, start_block + 3);
136 btrfs_set_disk_key_offset(&item.key, 1);
137 itemoff = itemoff - sizeof(struct btrfs_extent_item);
138 btrfs_set_item_offset(&item, itemoff);
139 btrfs_set_extent_owner(&extent_item, BTRFS_INODE_MAP_OBJECTID);
140 memcpy(empty_leaf->items + 3, &item, sizeof(item));
141 memcpy(btrfs_leaf_data(empty_leaf) + btrfs_item_offset(&item),
142 &extent_item, btrfs_item_size(&item));
143 ret = pwrite(fd, empty_leaf, blocksize, (start_block + 2) * blocksize);
144 if (ret != blocksize)
145 return -1;
146
147 /* item5, give block 20 to the FS root */
148 btrfs_set_disk_key_objectid(&item.key, start_block + 4);
149 btrfs_set_disk_key_offset(&item.key, 1);
150 itemoff = itemoff - sizeof(struct btrfs_extent_item);
151 btrfs_set_item_offset(&item, itemoff);
152 btrfs_set_extent_owner(&extent_item, BTRFS_FS_TREE_OBJECTID);
153 memcpy(empty_leaf->items + 4, &item, sizeof(item));
154 memcpy(btrfs_leaf_data(empty_leaf) + btrfs_item_offset(&item),
155 &extent_item, btrfs_item_size(&item));
156 ret = pwrite(fd, empty_leaf, blocksize, (start_block + 2) * blocksize);
157 if (ret != blocksize)
158 return -1;
159
160 /* create the inode map */
161 btrfs_set_header_parentid(&empty_leaf->header,
162 BTRFS_INODE_MAP_OBJECTID);
163 btrfs_set_header_blocknr(&empty_leaf->header, start_block + 3);
164 btrfs_set_header_nritems(&empty_leaf->header, 0);
165 ret = pwrite(fd, empty_leaf, blocksize, (start_block + 3) * blocksize);
166 if (ret != blocksize)
167 return -1;
168
169 /* finally create the FS root */
170 btrfs_set_header_parentid(&empty_leaf->header, BTRFS_FS_TREE_OBJECTID);
171 btrfs_set_header_blocknr(&empty_leaf->header, start_block + 4);
172 btrfs_set_header_nritems(&empty_leaf->header, 0);
173 ret = pwrite(fd, empty_leaf, blocksize, (start_block + 4) * blocksize);
174 if (ret != blocksize)
175 return -1;
176 return 0;
177}
178
179u64 device_size(int fd, struct stat *st)
180{
181 u64 size;
182 if (S_ISREG(st->st_mode)) {
183 return st->st_size;
184 }
185 if (!S_ISBLK(st->st_mode)) {
186 return 0;
187 }
188 if (ioctl(fd, BLKGETSIZE64, &size) >= 0) {
189 return size;
190 }
191 return 0;
192}
193
194int main(int ac, char **av)
195{
196 char *file;
197 u64 block_count = 0;
198 int fd;
199 struct stat st;
200 int ret;
201 int i;
202 char *buf = malloc(4096);
203 if (ac >= 2) {
204 file = av[1];
205 if (ac == 3) {
206 block_count = atoi(av[2]);
207 if (!block_count) {
208 fprintf(stderr, "error finding block count\n");
209 exit(1);
210 }
211 }
212 } else {
213 fprintf(stderr, "usage: mkfs.btrfs file [block count]\n");
214 exit(1);
215 }
216 fd = open(file, O_RDWR);
217 if (fd < 0) {
218 fprintf(stderr, "unable to open %s\n", file);
219 exit(1);
220 }
221 ret = fstat(fd, &st);
222 if (ret < 0) {
223 fprintf(stderr, "unable to stat %s\n", file);
224 exit(1);
225 }
226 if (block_count == 0) {
227 block_count = device_size(fd, &st);
228 if (block_count == 0) {
229 fprintf(stderr, "unable to find %s size\n", file);
230 exit(1);
231 }
232 }
233 block_count /= 4096;
234 if (block_count < 256) {
235 fprintf(stderr, "device %s is too small\n", file);
236 exit(1);
237 }
238 memset(buf, 0, 4096);
239 for(i = 0; i < 6; i++) {
240 ret = write(fd, buf, 4096);
241 if (ret != 4096) {
242 fprintf(stderr, "unable to zero fill device\n");
243 exit(1);
244 }
245 }
246 ret = mkfs(fd, block_count, 4096);
247 if (ret) {
248 fprintf(stderr, "error during mkfs %d\n", ret);
249 exit(1);
250 }
251 printf("fs created on %s blocksize %d blocks %Lu\n",
252 file, 4096, block_count);
253 return 0;
254}
255
diff --git a/fs/btrfs/print-tree.c b/fs/btrfs/print-tree.c
index f53b99da12f3..aa2d3fac8804 100644
--- a/fs/btrfs/print-tree.c
+++ b/fs/btrfs/print-tree.c
@@ -1,7 +1,4 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h" 3#include "disk-io.h"
7 4
@@ -17,14 +14,14 @@ void btrfs_print_leaf(struct btrfs_root *root, struct btrfs_leaf *l)
17 struct btrfs_inode_item *ii; 14 struct btrfs_inode_item *ii;
18 u32 type; 15 u32 type;
19 16
20 printf("leaf %Lu total ptrs %d free space %d\n", 17 printk("leaf %Lu total ptrs %d free space %d\n",
21 btrfs_header_blocknr(&l->header), nr, 18 btrfs_header_blocknr(&l->header), nr,
22 btrfs_leaf_free_space(root, l)); 19 btrfs_leaf_free_space(root, l));
23 fflush(stdout); 20 fflush(stdout);
24 for (i = 0 ; i < nr ; i++) { 21 for (i = 0 ; i < nr ; i++) {
25 item = l->items + i; 22 item = l->items + i;
26 type = btrfs_disk_key_type(&item->key); 23 type = btrfs_disk_key_type(&item->key);
27 printf("\titem %d key (%Lu %u %Lu) itemoff %d itemsize %d\n", 24 printk("\titem %d key (%Lu %u %Lu) itemoff %d itemsize %d\n",
28 i, 25 i,
29 btrfs_disk_key_objectid(&item->key), 26 btrfs_disk_key_objectid(&item->key),
30 btrfs_disk_key_flags(&item->key), 27 btrfs_disk_key_flags(&item->key),
@@ -34,38 +31,39 @@ void btrfs_print_leaf(struct btrfs_root *root, struct btrfs_leaf *l)
34 switch (type) { 31 switch (type) {
35 case BTRFS_INODE_ITEM_KEY: 32 case BTRFS_INODE_ITEM_KEY:
36 ii = btrfs_item_ptr(l, i, struct btrfs_inode_item); 33 ii = btrfs_item_ptr(l, i, struct btrfs_inode_item);
37 printf("\t\tinode generation %Lu size %Lu\n", 34 printk("\t\tinode generation %Lu size %Lu mode %o\n",
38 btrfs_inode_generation(ii), 35 btrfs_inode_generation(ii),
39 btrfs_inode_size(ii)); 36 btrfs_inode_size(ii),
37 btrfs_inode_mode(ii));
40 break; 38 break;
41 case BTRFS_DIR_ITEM_KEY: 39 case BTRFS_DIR_ITEM_KEY:
42 di = btrfs_item_ptr(l, i, struct btrfs_dir_item); 40 di = btrfs_item_ptr(l, i, struct btrfs_dir_item);
43 printf("\t\tdir oid %Lu flags %u type %u\n", 41 printk("\t\tdir oid %Lu flags %u type %u\n",
44 btrfs_dir_objectid(di), 42 btrfs_dir_objectid(di),
45 btrfs_dir_flags(di), 43 btrfs_dir_flags(di),
46 btrfs_dir_type(di)); 44 btrfs_dir_type(di));
47 printf("\t\tname %.*s\n", 45 printk("\t\tname %.*s\n",
48 btrfs_dir_name_len(di),(char *)(di + 1)); 46 btrfs_dir_name_len(di),(char *)(di + 1));
49 break; 47 break;
50 case BTRFS_ROOT_ITEM_KEY: 48 case BTRFS_ROOT_ITEM_KEY:
51 ri = btrfs_item_ptr(l, i, struct btrfs_root_item); 49 ri = btrfs_item_ptr(l, i, struct btrfs_root_item);
52 printf("\t\troot data blocknr %Lu refs %u\n", 50 printk("\t\troot data blocknr %Lu refs %u\n",
53 btrfs_root_blocknr(ri), btrfs_root_refs(ri)); 51 btrfs_root_blocknr(ri), btrfs_root_refs(ri));
54 break; 52 break;
55 case BTRFS_EXTENT_ITEM_KEY: 53 case BTRFS_EXTENT_ITEM_KEY:
56 ei = btrfs_item_ptr(l, i, struct btrfs_extent_item); 54 ei = btrfs_item_ptr(l, i, struct btrfs_extent_item);
57 printf("\t\textent data refs %u owner %Lu\n", 55 printk("\t\textent data refs %u owner %Lu\n",
58 btrfs_extent_refs(ei), btrfs_extent_owner(ei)); 56 btrfs_extent_refs(ei), btrfs_extent_owner(ei));
59 break; 57 break;
60 case BTRFS_INODE_MAP_ITEM_KEY: 58 case BTRFS_INODE_MAP_ITEM_KEY:
61 mi = btrfs_item_ptr(l, i, struct btrfs_inode_map_item); 59 mi = btrfs_item_ptr(l, i, struct btrfs_inode_map_item);
62 printf("\t\tinode map key %Lu %u %Lu\n", 60 printk("\t\tinode map key %Lu %u %Lu\n",
63 btrfs_disk_key_objectid(&mi->key), 61 btrfs_disk_key_objectid(&mi->key),
64 btrfs_disk_key_flags(&mi->key), 62 btrfs_disk_key_flags(&mi->key),
65 btrfs_disk_key_offset(&mi->key)); 63 btrfs_disk_key_offset(&mi->key));
66 break; 64 break;
67 case BTRFS_STRING_ITEM_KEY: 65 case BTRFS_STRING_ITEM_KEY:
68 printf("\t\titem data %.*s\n", btrfs_item_size(item), 66 printk("\t\titem data %.*s\n", btrfs_item_size(item),
69 btrfs_leaf_data(l) + btrfs_item_offset(item)); 67 btrfs_leaf_data(l) + btrfs_item_offset(item));
70 break; 68 break;
71 }; 69 };
@@ -86,12 +84,12 @@ void btrfs_print_tree(struct btrfs_root *root, struct btrfs_buffer *t)
86 btrfs_print_leaf(root, (struct btrfs_leaf *)c); 84 btrfs_print_leaf(root, (struct btrfs_leaf *)c);
87 return; 85 return;
88 } 86 }
89 printf("node %Lu level %d total ptrs %d free spc %u\n", t->blocknr, 87 printk("node %Lu level %d total ptrs %d free spc %u\n", t->blocknr,
90 btrfs_header_level(&c->header), nr, 88 btrfs_header_level(&c->header), nr,
91 (u32)BTRFS_NODEPTRS_PER_BLOCK(root) - nr); 89 (u32)BTRFS_NODEPTRS_PER_BLOCK(root) - nr);
92 fflush(stdout); 90 fflush(stdout);
93 for (i = 0; i < nr; i++) { 91 for (i = 0; i < nr; i++) {
94 printf("\tkey %d (%Lu %u %Lu) block %Lu\n", 92 printk("\tkey %d (%Lu %u %Lu) block %Lu\n",
95 i, 93 i,
96 c->ptrs[i].key.objectid, 94 c->ptrs[i].key.objectid,
97 c->ptrs[i].key.flags, 95 c->ptrs[i].key.flags,
diff --git a/fs/btrfs/quick-test.c b/fs/btrfs/quick-test.c
deleted file mode 100644
index ef12cf888783..000000000000
--- a/fs/btrfs/quick-test.c
+++ /dev/null
@@ -1,179 +0,0 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7#include "print-tree.h"
8#include "transaction.h"
9
10/* for testing only */
11int next_key(int i, int max_key) {
12 return rand() % max_key;
13 // return i;
14}
15
16int main(int ac, char **av) {
17 struct btrfs_key ins;
18 struct btrfs_key last = { (u64)-1, 0, 0};
19 char *buf;
20 int i;
21 int num;
22 int ret;
23 int run_size = 100000;
24 int max_key = 100000000;
25 int tree_size = 0;
26 struct btrfs_path path;
27 struct btrfs_super_block super;
28 struct btrfs_root *root;
29 struct btrfs_trans_handle *trans;
30
31 radix_tree_init();
32
33 root = open_ctree("dbfile", &super);
34 trans = btrfs_start_transaction(root, 1);
35 srand(55);
36 ins.flags = 0;
37 btrfs_set_key_type(&ins, BTRFS_STRING_ITEM_KEY);
38 for (i = 0; i < run_size; i++) {
39 buf = malloc(64);
40 num = next_key(i, max_key);
41 // num = i;
42 sprintf(buf, "string-%d", num);
43 if (i % 10000 == 0)
44 fprintf(stderr, "insert %d:%d\n", num, i);
45 ins.objectid = num;
46 ins.offset = 0;
47 ret = btrfs_insert_item(trans, root, &ins, buf, strlen(buf));
48 if (!ret)
49 tree_size++;
50 free(buf);
51 if (i == run_size - 5) {
52 btrfs_commit_transaction(trans, root, &super);
53 }
54
55 }
56 close_ctree(root, &super);
57
58 root = open_ctree("dbfile", &super);
59 printf("starting search\n");
60 srand(55);
61 for (i = 0; i < run_size; i++) {
62 num = next_key(i, max_key);
63 ins.objectid = num;
64 btrfs_init_path(&path);
65 if (i % 10000 == 0)
66 fprintf(stderr, "search %d:%d\n", num, i);
67 ret = btrfs_search_slot(trans, root, &ins, &path, 0, 0);
68 if (ret) {
69 btrfs_print_tree(root, root->node);
70 printf("unable to find %d\n", num);
71 exit(1);
72 }
73 btrfs_release_path(root, &path);
74 }
75 close_ctree(root, &super);
76 root = open_ctree("dbfile", &super);
77 printf("node %p level %d total ptrs %d free spc %lu\n", root->node,
78 btrfs_header_level(&root->node->node.header),
79 btrfs_header_nritems(&root->node->node.header),
80 BTRFS_NODEPTRS_PER_BLOCK(root) -
81 btrfs_header_nritems(&root->node->node.header));
82 printf("all searches good, deleting some items\n");
83 i = 0;
84 srand(55);
85 for (i = 0 ; i < run_size/4; i++) {
86 num = next_key(i, max_key);
87 ins.objectid = num;
88 btrfs_init_path(&path);
89 ret = btrfs_search_slot(trans, root, &ins, &path, -1, 1);
90 if (!ret) {
91 if (i % 10000 == 0)
92 fprintf(stderr, "del %d:%d\n", num, i);
93 ret = btrfs_del_item(trans, root, &path);
94 if (ret != 0)
95 BUG();
96 tree_size--;
97 }
98 btrfs_release_path(root, &path);
99 }
100 close_ctree(root, &super);
101 root = open_ctree("dbfile", &super);
102 srand(128);
103 for (i = 0; i < run_size; i++) {
104 buf = malloc(64);
105 num = next_key(i, max_key);
106 sprintf(buf, "string-%d", num);
107 ins.objectid = num;
108 if (i % 10000 == 0)
109 fprintf(stderr, "insert %d:%d\n", num, i);
110 ret = btrfs_insert_item(trans, root, &ins, buf, strlen(buf));
111 if (!ret)
112 tree_size++;
113 free(buf);
114 }
115 close_ctree(root, &super);
116 root = open_ctree("dbfile", &super);
117 srand(128);
118 printf("starting search2\n");
119 for (i = 0; i < run_size; i++) {
120 num = next_key(i, max_key);
121 ins.objectid = num;
122 btrfs_init_path(&path);
123 if (i % 10000 == 0)
124 fprintf(stderr, "search %d:%d\n", num, i);
125 ret = btrfs_search_slot(trans, root, &ins, &path, 0, 0);
126 if (ret) {
127 btrfs_print_tree(root, root->node);
128 printf("unable to find %d\n", num);
129 exit(1);
130 }
131 btrfs_release_path(root, &path);
132 }
133 printf("starting big long delete run\n");
134 while(root->node &&
135 btrfs_header_nritems(&root->node->node.header) > 0) {
136 struct btrfs_leaf *leaf;
137 int slot;
138 ins.objectid = (u64)-1;
139 btrfs_init_path(&path);
140 ret = btrfs_search_slot(trans, root, &ins, &path, -1, 1);
141 if (ret == 0)
142 BUG();
143
144 leaf = &path.nodes[0]->leaf;
145 slot = path.slots[0];
146 if (slot != btrfs_header_nritems(&leaf->header))
147 BUG();
148 while(path.slots[0] > 0) {
149 path.slots[0] -= 1;
150 slot = path.slots[0];
151 leaf = &path.nodes[0]->leaf;
152
153 btrfs_disk_key_to_cpu(&last, &leaf->items[slot].key);
154 if (tree_size % 10000 == 0)
155 printf("big del %d:%d\n", tree_size, i);
156 ret = btrfs_del_item(trans, root, &path);
157 if (ret != 0) {
158 printf("del_item returned %d\n", ret);
159 BUG();
160 }
161 tree_size--;
162 }
163 btrfs_release_path(root, &path);
164 }
165 /*
166 printf("previous tree:\n");
167 btrfs_print_tree(root, root->commit_root);
168 printf("map before commit\n");
169 btrfs_print_tree(root->extent_root, root->extent_root->node);
170 */
171 btrfs_commit_transaction(trans, root, &super);
172 printf("tree size is now %d\n", tree_size);
173 printf("root %p commit root %p\n", root->node, root->commit_root);
174 printf("map tree\n");
175 btrfs_print_tree(root->fs_info->extent_root,
176 root->fs_info->extent_root->node);
177 close_ctree(root, &super);
178 return 0;
179}
diff --git a/fs/btrfs/radix-tree.c b/fs/btrfs/radix-tree.c
deleted file mode 100644
index baa25ca1c2ac..000000000000
--- a/fs/btrfs/radix-tree.c
+++ /dev/null
@@ -1,836 +0,0 @@
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation; either version 2, or (at
9 * your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21#include "kerncompat.h"
22#include "radix-tree.h"
23#ifdef __KERNEL__
24#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
25#else
26#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
27#endif
28
29#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
30#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
31
32#define RADIX_TREE_TAG_LONGS \
33 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
34
35struct radix_tree_node {
36 unsigned int count;
37 void *slots[RADIX_TREE_MAP_SIZE];
38 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
39};
40
41struct radix_tree_path {
42 struct radix_tree_node *node;
43 int offset;
44};
45
46#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
47#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
48
49static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
50
51/*
52 * Per-cpu pool of preloaded nodes
53 */
54struct radix_tree_preload {
55 int nr;
56 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
57};
58struct radix_tree_preload radix_tree_preloads = { 0, };
59
60static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
61{
62 return root->gfp_mask & __GFP_BITS_MASK;
63}
64
65static int internal_nodes = 0;
66/*
67 * This assumes that the caller has performed appropriate preallocation, and
68 * that the caller has pinned this thread of control to the current CPU.
69 */
70static struct radix_tree_node *
71radix_tree_node_alloc(struct radix_tree_root *root)
72{
73 struct radix_tree_node *ret;
74 ret = malloc(sizeof(struct radix_tree_node));
75 if (ret) {
76 memset(ret, 0, sizeof(struct radix_tree_node));
77 internal_nodes++;
78 }
79 return ret;
80}
81
82static inline void
83radix_tree_node_free(struct radix_tree_node *node)
84{
85 internal_nodes--;
86 free(node);
87}
88
89/*
90 * Load up this CPU's radix_tree_node buffer with sufficient objects to
91 * ensure that the addition of a single element in the tree cannot fail. On
92 * success, return zero, with preemption disabled. On error, return -ENOMEM
93 * with preemption not disabled.
94 */
95int radix_tree_preload(gfp_t gfp_mask)
96{
97 struct radix_tree_preload *rtp;
98 struct radix_tree_node *node;
99 int ret = -ENOMEM;
100
101 preempt_disable();
102 rtp = &__get_cpu_var(radix_tree_preloads);
103 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
104 preempt_enable();
105 node = radix_tree_node_alloc(NULL);
106 if (node == NULL)
107 goto out;
108 preempt_disable();
109 rtp = &__get_cpu_var(radix_tree_preloads);
110 if (rtp->nr < ARRAY_SIZE(rtp->nodes))
111 rtp->nodes[rtp->nr++] = node;
112 else
113 radix_tree_node_free(node);
114 }
115 ret = 0;
116out:
117 return ret;
118}
119
120static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
121 int offset)
122{
123 __set_bit(offset, node->tags[tag]);
124}
125
126static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
127 int offset)
128{
129 __clear_bit(offset, node->tags[tag]);
130}
131
132static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
133 int offset)
134{
135 return test_bit(offset, node->tags[tag]);
136}
137
138static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
139{
140 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
141}
142
143
144static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
145{
146 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
147}
148
149static inline void root_tag_clear_all(struct radix_tree_root *root)
150{
151 root->gfp_mask &= __GFP_BITS_MASK;
152}
153
154static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
155{
156 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
157}
158
159/*
160 * Returns 1 if any slot in the node has this tag set.
161 * Otherwise returns 0.
162 */
163static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
164{
165 int idx;
166 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
167 if (node->tags[tag][idx])
168 return 1;
169 }
170 return 0;
171}
172
173/*
174 * Return the maximum key which can be store into a
175 * radix tree with height HEIGHT.
176 */
177static inline unsigned long radix_tree_maxindex(unsigned int height)
178{
179 return height_to_maxindex[height];
180}
181
182/*
183 * Extend a radix tree so it can store key @index.
184 */
185static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
186{
187 struct radix_tree_node *node;
188 unsigned int height;
189 int tag;
190
191 /* Figure out what the height should be. */
192 height = root->height + 1;
193 while (index > radix_tree_maxindex(height))
194 height++;
195
196 if (root->rnode == NULL) {
197 root->height = height;
198 goto out;
199 }
200
201 do {
202 if (!(node = radix_tree_node_alloc(root)))
203 return -ENOMEM;
204
205 /* Increase the height. */
206 node->slots[0] = root->rnode;
207
208 /* Propagate the aggregated tag info into the new root */
209 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
210 if (root_tag_get(root, tag))
211 tag_set(node, tag, 0);
212 }
213
214 node->count = 1;
215 root->rnode = node;
216 root->height++;
217 } while (height > root->height);
218out:
219 return 0;
220}
221
222/**
223 * radix_tree_insert - insert into a radix tree
224 * @root: radix tree root
225 * @index: index key
226 * @item: item to insert
227 *
228 * Insert an item into the radix tree at position @index.
229 */
230int radix_tree_insert(struct radix_tree_root *root,
231 unsigned long index, void *item)
232{
233 struct radix_tree_node *node = NULL, *slot;
234 unsigned int height, shift;
235 int offset;
236 int error;
237
238 /* Make sure the tree is high enough. */
239 if (index > radix_tree_maxindex(root->height)) {
240 error = radix_tree_extend(root, index);
241 if (error)
242 return error;
243 }
244
245 slot = root->rnode;
246 height = root->height;
247 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
248
249 offset = 0; /* uninitialised var warning */
250 while (height > 0) {
251 if (slot == NULL) {
252 /* Have to add a child node. */
253 if (!(slot = radix_tree_node_alloc(root)))
254 return -ENOMEM;
255 if (node) {
256 node->slots[offset] = slot;
257 node->count++;
258 } else
259 root->rnode = slot;
260 }
261
262 /* Go a level down */
263 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
264 node = slot;
265 slot = node->slots[offset];
266 shift -= RADIX_TREE_MAP_SHIFT;
267 height--;
268 }
269
270 if (slot != NULL)
271 return -EEXIST;
272
273 if (node) {
274 node->count++;
275 node->slots[offset] = item;
276 BUG_ON(tag_get(node, 0, offset));
277 BUG_ON(tag_get(node, 1, offset));
278 } else {
279 root->rnode = item;
280 BUG_ON(root_tag_get(root, 0));
281 BUG_ON(root_tag_get(root, 1));
282 }
283
284 return 0;
285}
286
287static inline void **__lookup_slot(struct radix_tree_root *root,
288 unsigned long index)
289{
290 unsigned int height, shift;
291 struct radix_tree_node **slot;
292
293 height = root->height;
294
295 if (index > radix_tree_maxindex(height))
296 return NULL;
297
298 if (height == 0 && root->rnode)
299 return (void **)&root->rnode;
300
301 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
302 slot = &root->rnode;
303
304 while (height > 0) {
305 if (*slot == NULL)
306 return NULL;
307
308 slot = (struct radix_tree_node **)
309 ((*slot)->slots +
310 ((index >> shift) & RADIX_TREE_MAP_MASK));
311 shift -= RADIX_TREE_MAP_SHIFT;
312 height--;
313 }
314
315 return (void **)slot;
316}
317
318/**
319 * radix_tree_lookup_slot - lookup a slot in a radix tree
320 * @root: radix tree root
321 * @index: index key
322 *
323 * Lookup the slot corresponding to the position @index in the radix tree
324 * @root. This is useful for update-if-exists operations.
325 */
326void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
327{
328 return __lookup_slot(root, index);
329}
330
331/**
332 * radix_tree_lookup - perform lookup operation on a radix tree
333 * @root: radix tree root
334 * @index: index key
335 *
336 * Lookup the item at the position @index in the radix tree @root.
337 */
338void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
339{
340 void **slot;
341
342 slot = __lookup_slot(root, index);
343 return slot != NULL ? *slot : NULL;
344}
345
346/**
347 * radix_tree_tag_set - set a tag on a radix tree node
348 * @root: radix tree root
349 * @index: index key
350 * @tag: tag index
351 *
352 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
353 * corresponding to @index in the radix tree. From
354 * the root all the way down to the leaf node.
355 *
356 * Returns the address of the tagged item. Setting a tag on a not-present
357 * item is a bug.
358 */
359void *radix_tree_tag_set(struct radix_tree_root *root,
360 unsigned long index, unsigned int tag)
361{
362 unsigned int height, shift;
363 struct radix_tree_node *slot;
364
365 height = root->height;
366 BUG_ON(index > radix_tree_maxindex(height));
367
368 slot = root->rnode;
369 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
370
371 while (height > 0) {
372 int offset;
373
374 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
375 if (!tag_get(slot, tag, offset))
376 tag_set(slot, tag, offset);
377 slot = slot->slots[offset];
378 BUG_ON(slot == NULL);
379 shift -= RADIX_TREE_MAP_SHIFT;
380 height--;
381 }
382
383 /* set the root's tag bit */
384 if (slot && !root_tag_get(root, tag))
385 root_tag_set(root, tag);
386
387 return slot;
388}
389
390/**
391 * radix_tree_tag_clear - clear a tag on a radix tree node
392 * @root: radix tree root
393 * @index: index key
394 * @tag: tag index
395 *
396 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
397 * corresponding to @index in the radix tree. If
398 * this causes the leaf node to have no tags set then clear the tag in the
399 * next-to-leaf node, etc.
400 *
401 * Returns the address of the tagged item on success, else NULL. ie:
402 * has the same return value and semantics as radix_tree_lookup().
403 */
404void *radix_tree_tag_clear(struct radix_tree_root *root,
405 unsigned long index, unsigned int tag)
406{
407 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
408 struct radix_tree_node *slot = NULL;
409 unsigned int height, shift;
410
411 height = root->height;
412 if (index > radix_tree_maxindex(height))
413 goto out;
414
415 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
416 pathp->node = NULL;
417 slot = root->rnode;
418
419 while (height > 0) {
420 int offset;
421
422 if (slot == NULL)
423 goto out;
424
425 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
426 pathp[1].offset = offset;
427 pathp[1].node = slot;
428 slot = slot->slots[offset];
429 pathp++;
430 shift -= RADIX_TREE_MAP_SHIFT;
431 height--;
432 }
433
434 if (slot == NULL)
435 goto out;
436
437 while (pathp->node) {
438 if (!tag_get(pathp->node, tag, pathp->offset))
439 goto out;
440 tag_clear(pathp->node, tag, pathp->offset);
441 if (any_tag_set(pathp->node, tag))
442 goto out;
443 pathp--;
444 }
445
446 /* clear the root's tag bit */
447 if (root_tag_get(root, tag))
448 root_tag_clear(root, tag);
449
450out:
451 return slot;
452}
453
454#ifndef __KERNEL__ /* Only the test harness uses this at present */
455/**
456 * radix_tree_tag_get - get a tag on a radix tree node
457 * @root: radix tree root
458 * @index: index key
459 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
460 *
461 * Return values:
462 *
463 * 0: tag not present or not set
464 * 1: tag set
465 */
466int radix_tree_tag_get(struct radix_tree_root *root,
467 unsigned long index, unsigned int tag)
468{
469 unsigned int height, shift;
470 struct radix_tree_node *slot;
471 int saw_unset_tag = 0;
472
473 height = root->height;
474 if (index > radix_tree_maxindex(height))
475 return 0;
476
477 /* check the root's tag bit */
478 if (!root_tag_get(root, tag))
479 return 0;
480
481 if (height == 0)
482 return 1;
483
484 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
485 slot = root->rnode;
486
487 for ( ; ; ) {
488 int offset;
489
490 if (slot == NULL)
491 return 0;
492
493 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
494
495 /*
496 * This is just a debug check. Later, we can bale as soon as
497 * we see an unset tag.
498 */
499 if (!tag_get(slot, tag, offset))
500 saw_unset_tag = 1;
501 if (height == 1) {
502 int ret = tag_get(slot, tag, offset);
503
504 BUG_ON(ret && saw_unset_tag);
505 return !!ret;
506 }
507 slot = slot->slots[offset];
508 shift -= RADIX_TREE_MAP_SHIFT;
509 height--;
510 }
511}
512#endif
513
514static unsigned int
515__lookup(struct radix_tree_root *root, void **results, unsigned long index,
516 unsigned int max_items, unsigned long *next_index)
517{
518 unsigned int nr_found = 0;
519 unsigned int shift, height;
520 struct radix_tree_node *slot;
521 unsigned long i;
522
523 height = root->height;
524 if (height == 0) {
525 if (root->rnode && index == 0)
526 results[nr_found++] = root->rnode;
527 goto out;
528 }
529
530 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
531 slot = root->rnode;
532
533 for ( ; height > 1; height--) {
534
535 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
536 i < RADIX_TREE_MAP_SIZE; i++) {
537 if (slot->slots[i] != NULL)
538 break;
539 index &= ~((1UL << shift) - 1);
540 index += 1UL << shift;
541 if (index == 0)
542 goto out; /* 32-bit wraparound */
543 }
544 if (i == RADIX_TREE_MAP_SIZE)
545 goto out;
546
547 shift -= RADIX_TREE_MAP_SHIFT;
548 slot = slot->slots[i];
549 }
550
551 /* Bottom level: grab some items */
552 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
553 index++;
554 if (slot->slots[i]) {
555 results[nr_found++] = slot->slots[i];
556 if (nr_found == max_items)
557 goto out;
558 }
559 }
560out:
561 *next_index = index;
562 return nr_found;
563}
564
565/**
566 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
567 * @root: radix tree root
568 * @results: where the results of the lookup are placed
569 * @first_index: start the lookup from this key
570 * @max_items: place up to this many items at *results
571 *
572 * Performs an index-ascending scan of the tree for present items. Places
573 * them at *@results and returns the number of items which were placed at
574 * *@results.
575 *
576 * The implementation is naive.
577 */
578unsigned int
579radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
580 unsigned long first_index, unsigned int max_items)
581{
582 const unsigned long max_index = radix_tree_maxindex(root->height);
583 unsigned long cur_index = first_index;
584 unsigned int ret = 0;
585
586 while (ret < max_items) {
587 unsigned int nr_found;
588 unsigned long next_index; /* Index of next search */
589
590 if (cur_index > max_index)
591 break;
592 nr_found = __lookup(root, results + ret, cur_index,
593 max_items - ret, &next_index);
594 ret += nr_found;
595 if (next_index == 0)
596 break;
597 cur_index = next_index;
598 }
599 return ret;
600}
601
602/*
603 * FIXME: the two tag_get()s here should use find_next_bit() instead of
604 * open-coding the search.
605 */
606static unsigned int
607__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
608 unsigned int max_items, unsigned long *next_index, unsigned int tag)
609{
610 unsigned int nr_found = 0;
611 unsigned int shift;
612 unsigned int height = root->height;
613 struct radix_tree_node *slot;
614
615 if (height == 0) {
616 if (root->rnode && index == 0)
617 results[nr_found++] = root->rnode;
618 goto out;
619 }
620
621 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
622 slot = root->rnode;
623
624 do {
625 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
626
627 for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
628 if (tag_get(slot, tag, i)) {
629 BUG_ON(slot->slots[i] == NULL);
630 break;
631 }
632 index &= ~((1UL << shift) - 1);
633 index += 1UL << shift;
634 if (index == 0)
635 goto out; /* 32-bit wraparound */
636 }
637 if (i == RADIX_TREE_MAP_SIZE)
638 goto out;
639 height--;
640 if (height == 0) { /* Bottom level: grab some items */
641 unsigned long j = index & RADIX_TREE_MAP_MASK;
642
643 for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
644 index++;
645 if (tag_get(slot, tag, j)) {
646 BUG_ON(slot->slots[j] == NULL);
647 results[nr_found++] = slot->slots[j];
648 if (nr_found == max_items)
649 goto out;
650 }
651 }
652 }
653 shift -= RADIX_TREE_MAP_SHIFT;
654 slot = slot->slots[i];
655 } while (height > 0);
656out:
657 *next_index = index;
658 return nr_found;
659}
660
661/**
662 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
663 * based on a tag
664 * @root: radix tree root
665 * @results: where the results of the lookup are placed
666 * @first_index: start the lookup from this key
667 * @max_items: place up to this many items at *results
668 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
669 *
670 * Performs an index-ascending scan of the tree for present items which
671 * have the tag indexed by @tag set. Places the items at *@results and
672 * returns the number of items which were placed at *@results.
673 */
674unsigned int
675radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
676 unsigned long first_index, unsigned int max_items,
677 unsigned int tag)
678{
679 const unsigned long max_index = radix_tree_maxindex(root->height);
680 unsigned long cur_index = first_index;
681 unsigned int ret = 0;
682
683 /* check the root's tag bit */
684 if (!root_tag_get(root, tag))
685 return 0;
686
687 while (ret < max_items) {
688 unsigned int nr_found;
689 unsigned long next_index; /* Index of next search */
690
691 if (cur_index > max_index)
692 break;
693 nr_found = __lookup_tag(root, results + ret, cur_index,
694 max_items - ret, &next_index, tag);
695 ret += nr_found;
696 if (next_index == 0)
697 break;
698 cur_index = next_index;
699 }
700 return ret;
701}
702
703/**
704 * radix_tree_shrink - shrink height of a radix tree to minimal
705 * @root radix tree root
706 */
707static inline void radix_tree_shrink(struct radix_tree_root *root)
708{
709 /* try to shrink tree height */
710 while (root->height > 0 &&
711 root->rnode->count == 1 &&
712 root->rnode->slots[0]) {
713 struct radix_tree_node *to_free = root->rnode;
714
715 root->rnode = to_free->slots[0];
716 root->height--;
717 /* must only free zeroed nodes into the slab */
718 tag_clear(to_free, 0, 0);
719 tag_clear(to_free, 1, 0);
720 to_free->slots[0] = NULL;
721 to_free->count = 0;
722 radix_tree_node_free(to_free);
723 }
724}
725
726/**
727 * radix_tree_delete - delete an item from a radix tree
728 * @root: radix tree root
729 * @index: index key
730 *
731 * Remove the item at @index from the radix tree rooted at @root.
732 *
733 * Returns the address of the deleted item, or NULL if it was not present.
734 */
735void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
736{
737 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
738 struct radix_tree_node *slot = NULL;
739 unsigned int height, shift;
740 int tag;
741 int offset;
742
743 height = root->height;
744 if (index > radix_tree_maxindex(height))
745 goto out;
746
747 slot = root->rnode;
748 if (height == 0 && root->rnode) {
749 root_tag_clear_all(root);
750 root->rnode = NULL;
751 goto out;
752 }
753
754 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
755 pathp->node = NULL;
756
757 do {
758 if (slot == NULL)
759 goto out;
760
761 pathp++;
762 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
763 pathp->offset = offset;
764 pathp->node = slot;
765 slot = slot->slots[offset];
766 shift -= RADIX_TREE_MAP_SHIFT;
767 height--;
768 } while (height > 0);
769
770 if (slot == NULL)
771 goto out;
772
773 /*
774 * Clear all tags associated with the just-deleted item
775 */
776 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
777 if (tag_get(pathp->node, tag, pathp->offset))
778 radix_tree_tag_clear(root, index, tag);
779 }
780
781 /* Now free the nodes we do not need anymore */
782 while (pathp->node) {
783 pathp->node->slots[pathp->offset] = NULL;
784 pathp->node->count--;
785
786 if (pathp->node->count) {
787 if (pathp->node == root->rnode)
788 radix_tree_shrink(root);
789 goto out;
790 }
791
792 /* Node with zero slots in use so free it */
793 radix_tree_node_free(pathp->node);
794
795 pathp--;
796 }
797 root_tag_clear_all(root);
798 root->height = 0;
799 root->rnode = NULL;
800
801out:
802 return slot;
803}
804
805/**
806 * radix_tree_tagged - test whether any items in the tree are tagged
807 * @root: radix tree root
808 * @tag: tag to test
809 */
810int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
811{
812 return root_tag_get(root, tag);
813}
814
815static unsigned long __maxindex(unsigned int height)
816{
817 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
818 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
819
820 if (tmp >= RADIX_TREE_INDEX_BITS)
821 index = ~0UL;
822 return index;
823}
824
825static void radix_tree_init_maxindex(void)
826{
827 unsigned int i;
828
829 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
830 height_to_maxindex[i] = __maxindex(i);
831}
832
833void radix_tree_init(void)
834{
835 radix_tree_init_maxindex();
836}
diff --git a/fs/btrfs/radix-tree.h b/fs/btrfs/radix-tree.h
deleted file mode 100644
index c3ce88137f77..000000000000
--- a/fs/btrfs/radix-tree.h
+++ /dev/null
@@ -1,73 +0,0 @@
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2, or (at
8 * your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19#ifndef _LINUX_RADIX_TREE_H
20#define _LINUX_RADIX_TREE_H
21
22#define RADIX_TREE_MAX_TAGS 2
23
24/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
25struct radix_tree_root {
26 unsigned int height;
27 gfp_t gfp_mask;
28 struct radix_tree_node *rnode;
29};
30
31#define RADIX_TREE_INIT(mask) { \
32 .height = 0, \
33 .gfp_mask = (mask), \
34 .rnode = NULL, \
35}
36
37#define RADIX_TREE(name, mask) \
38 struct radix_tree_root name = RADIX_TREE_INIT(mask)
39
40#define INIT_RADIX_TREE(root, mask) \
41do { \
42 (root)->height = 0; \
43 (root)->gfp_mask = (mask); \
44 (root)->rnode = NULL; \
45} while (0)
46
47int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
48void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
49void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
50void *radix_tree_delete(struct radix_tree_root *, unsigned long);
51unsigned int
52radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
53 unsigned long first_index, unsigned int max_items);
54int radix_tree_preload(gfp_t gfp_mask);
55void radix_tree_init(void);
56void *radix_tree_tag_set(struct radix_tree_root *root,
57 unsigned long index, unsigned int tag);
58void *radix_tree_tag_clear(struct radix_tree_root *root,
59 unsigned long index, unsigned int tag);
60int radix_tree_tag_get(struct radix_tree_root *root,
61 unsigned long index, unsigned int tag);
62unsigned int
63radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
64 unsigned long first_index, unsigned int max_items,
65 unsigned int tag);
66int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
67
68static inline void radix_tree_preload_end(void)
69{
70 preempt_enable();
71}
72
73#endif /* _LINUX_RADIX_TREE_H */
diff --git a/fs/btrfs/random-test.c b/fs/btrfs/random-test.c
deleted file mode 100644
index 3a38ae7a886d..000000000000
--- a/fs/btrfs/random-test.c
+++ /dev/null
@@ -1,405 +0,0 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <signal.h>
4#include "kerncompat.h"
5#include "radix-tree.h"
6#include "ctree.h"
7#include "disk-io.h"
8#include "print-tree.h"
9#include "transaction.h"
10
11int keep_running = 1;
12struct btrfs_super_block super;
13
14static int setup_key(struct radix_tree_root *root, struct btrfs_key *key,
15 int exists)
16{
17 int num = rand();
18 unsigned long res[2];
19 int ret;
20
21 key->flags = 0;
22 btrfs_set_key_type(key, BTRFS_STRING_ITEM_KEY);
23 key->offset = 0;
24again:
25 ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
26 if (exists) {
27 if (ret == 0)
28 return -1;
29 num = res[0];
30 } else if (ret != 0 && num == res[0]) {
31 num++;
32 if (ret > 1 && num == res[1]) {
33 num++;
34 goto again;
35 }
36 }
37 key->objectid = num;
38 return 0;
39}
40
41static int ins_one(struct btrfs_trans_handle *trans, struct btrfs_root *root,
42 struct radix_tree_root *radix)
43{
44 struct btrfs_path path;
45 struct btrfs_key key;
46 int ret;
47 char buf[128];
48 unsigned long oid;
49 btrfs_init_path(&path);
50 ret = setup_key(radix, &key, 0);
51 sprintf(buf, "str-%Lu\n", key.objectid);
52 ret = btrfs_insert_item(trans, root, &key, buf, strlen(buf));
53 if (ret)
54 goto error;
55 oid = (unsigned long)key.objectid;
56 radix_tree_preload(GFP_KERNEL);
57 ret = radix_tree_insert(radix, oid, (void *)oid);
58 radix_tree_preload_end();
59 if (ret)
60 goto error;
61 return ret;
62error:
63 printf("failed to insert %Lu\n", key.objectid);
64 return -1;
65}
66
67static int insert_dup(struct btrfs_trans_handle *trans, struct btrfs_root
68 *root, struct radix_tree_root *radix)
69{
70 struct btrfs_path path;
71 struct btrfs_key key;
72 int ret;
73 char buf[128];
74 btrfs_init_path(&path);
75 ret = setup_key(radix, &key, 1);
76 if (ret < 0)
77 return 0;
78 sprintf(buf, "str-%Lu\n", key.objectid);
79 ret = btrfs_insert_item(trans, root, &key, buf, strlen(buf));
80 if (ret != -EEXIST) {
81 printf("insert on %Lu gave us %d\n", key.objectid, ret);
82 return 1;
83 }
84 return 0;
85}
86
87static int del_one(struct btrfs_trans_handle *trans, struct btrfs_root *root,
88 struct radix_tree_root *radix)
89{
90 struct btrfs_path path;
91 struct btrfs_key key;
92 int ret;
93 unsigned long *ptr;
94 btrfs_init_path(&path);
95 ret = setup_key(radix, &key, 1);
96 if (ret < 0)
97 return 0;
98 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
99 if (ret)
100 goto error;
101 ret = btrfs_del_item(trans, root, &path);
102 btrfs_release_path(root, &path);
103 if (ret != 0)
104 goto error;
105 ptr = radix_tree_delete(radix, key.objectid);
106 if (!ptr)
107 goto error;
108 return 0;
109error:
110 printf("failed to delete %Lu\n", key.objectid);
111 return -1;
112}
113
114static int lookup_item(struct btrfs_trans_handle *trans, struct btrfs_root
115 *root, struct radix_tree_root *radix)
116{
117 struct btrfs_path path;
118 struct btrfs_key key;
119 int ret;
120 btrfs_init_path(&path);
121 ret = setup_key(radix, &key, 1);
122 if (ret < 0)
123 return 0;
124 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
125 btrfs_release_path(root, &path);
126 if (ret)
127 goto error;
128 return 0;
129error:
130 printf("unable to find key %Lu\n", key.objectid);
131 return -1;
132}
133
134static int lookup_enoent(struct btrfs_trans_handle *trans, struct btrfs_root
135 *root, struct radix_tree_root *radix)
136{
137 struct btrfs_path path;
138 struct btrfs_key key;
139 int ret;
140 btrfs_init_path(&path);
141 ret = setup_key(radix, &key, 0);
142 if (ret < 0)
143 return ret;
144 ret = btrfs_search_slot(trans, root, &key, &path, 0, 0);
145 btrfs_release_path(root, &path);
146 if (ret <= 0)
147 goto error;
148 return 0;
149error:
150 printf("able to find key that should not exist %Lu\n", key.objectid);
151 return -1;
152}
153
154static int empty_tree(struct btrfs_trans_handle *trans, struct btrfs_root
155 *root, struct radix_tree_root *radix, int nr)
156{
157 struct btrfs_path path;
158 struct btrfs_key key;
159 unsigned long found = 0;
160 int ret;
161 int slot;
162 int *ptr;
163 int count = 0;
164
165 key.offset = 0;
166 key.flags = 0;
167 btrfs_set_key_type(&key, BTRFS_STRING_ITEM_KEY);
168 key.objectid = (unsigned long)-1;
169 while(nr-- >= 0) {
170 btrfs_init_path(&path);
171 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
172 if (ret < 0) {
173 btrfs_release_path(root, &path);
174 return ret;
175 }
176 if (ret != 0) {
177 if (path.slots[0] == 0) {
178 btrfs_release_path(root, &path);
179 break;
180 }
181 path.slots[0] -= 1;
182 }
183 slot = path.slots[0];
184 found = btrfs_disk_key_objectid(
185 &path.nodes[0]->leaf.items[slot].key);
186 ret = btrfs_del_item(trans, root, &path);
187 count++;
188 if (ret) {
189 fprintf(stderr,
190 "failed to remove %lu from tree\n",
191 found);
192 return -1;
193 }
194 btrfs_release_path(root, &path);
195 ptr = radix_tree_delete(radix, found);
196 if (!ptr)
197 goto error;
198 if (!keep_running)
199 break;
200 }
201 return 0;
202error:
203 fprintf(stderr, "failed to delete from the radix %lu\n", found);
204 return -1;
205}
206
207static int fill_tree(struct btrfs_trans_handle *trans, struct btrfs_root *root,
208 struct radix_tree_root *radix, int count)
209{
210 int i;
211 int ret = 0;
212 for (i = 0; i < count; i++) {
213 ret = ins_one(trans, root, radix);
214 if (ret) {
215 fprintf(stderr, "fill failed\n");
216 goto out;
217 }
218 if (i % 1000 == 0) {
219 ret = btrfs_commit_transaction(trans, root, &super);
220 if (ret) {
221 fprintf(stderr, "fill commit failed\n");
222 return ret;
223 }
224 }
225 if (i && i % 10000 == 0) {
226 printf("bigfill %d\n", i);
227 }
228 if (!keep_running)
229 break;
230 }
231out:
232 return ret;
233}
234
235static int bulk_op(struct btrfs_trans_handle *trans, struct btrfs_root *root,
236 struct radix_tree_root *radix)
237{
238 int ret;
239 int nr = rand() % 5000;
240 static int run_nr = 0;
241
242 /* do the bulk op much less frequently */
243 if (run_nr++ % 100)
244 return 0;
245 ret = empty_tree(trans, root, radix, nr);
246 if (ret)
247 return ret;
248 ret = fill_tree(trans, root, radix, nr);
249 if (ret)
250 return ret;
251 return 0;
252}
253
254
255int (*ops[])(struct btrfs_trans_handle *,
256 struct btrfs_root *root, struct radix_tree_root *radix) =
257 { ins_one, insert_dup, del_one, lookup_item,
258 lookup_enoent, bulk_op };
259
260static int fill_radix(struct btrfs_root *root, struct radix_tree_root *radix)
261{
262 struct btrfs_path path;
263 struct btrfs_key key;
264 unsigned long found;
265 int ret;
266 int slot;
267 int i;
268
269 key.offset = 0;
270 key.flags = 0;
271 btrfs_set_key_type(&key, BTRFS_STRING_ITEM_KEY);
272 key.objectid = (unsigned long)-1;
273 while(1) {
274 btrfs_init_path(&path);
275 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
276 if (ret < 0) {
277 btrfs_release_path(root, &path);
278 return ret;
279 }
280 slot = path.slots[0];
281 if (ret != 0) {
282 if (slot == 0) {
283 btrfs_release_path(root, &path);
284 break;
285 }
286 slot -= 1;
287 }
288 for (i = slot; i >= 0; i--) {
289 found = btrfs_disk_key_objectid(&path.nodes[0]->
290 leaf.items[i].key);
291 radix_tree_preload(GFP_KERNEL);
292 ret = radix_tree_insert(radix, found, (void *)found);
293 if (ret) {
294 fprintf(stderr,
295 "failed to insert %lu into radix\n",
296 found);
297 exit(1);
298 }
299
300 radix_tree_preload_end();
301 }
302 btrfs_release_path(root, &path);
303 key.objectid = found - 1;
304 if (key.objectid > found)
305 break;
306 }
307 return 0;
308}
309void sigstopper(int ignored)
310{
311 keep_running = 0;
312 fprintf(stderr, "caught exit signal, stopping\n");
313}
314
315int print_usage(void)
316{
317 printf("usage: tester [-ih] [-c count] [-f count]\n");
318 printf("\t -c count -- iteration count after filling\n");
319 printf("\t -f count -- run this many random inserts before starting\n");
320 printf("\t -i -- only do initial fill\n");
321 printf("\t -h -- this help text\n");
322 exit(1);
323}
324int main(int ac, char **av)
325{
326 RADIX_TREE(radix, GFP_KERNEL);
327 struct btrfs_root *root;
328 int i;
329 int ret;
330 int count;
331 int op;
332 int iterations = 20000;
333 int init_fill_count = 800000;
334 int err = 0;
335 int initial_only = 0;
336 struct btrfs_trans_handle *trans;
337 radix_tree_init();
338 root = open_ctree("dbfile", &super);
339 fill_radix(root, &radix);
340
341 signal(SIGTERM, sigstopper);
342 signal(SIGINT, sigstopper);
343
344 for (i = 1 ; i < ac ; i++) {
345 if (strcmp(av[i], "-i") == 0) {
346 initial_only = 1;
347 } else if (strcmp(av[i], "-c") == 0) {
348 iterations = atoi(av[i+1]);
349 i++;
350 } else if (strcmp(av[i], "-f") == 0) {
351 init_fill_count = atoi(av[i+1]);
352 i++;
353 } else {
354 print_usage();
355 }
356 }
357 printf("initial fill\n");
358 trans = btrfs_start_transaction(root, 1);
359 ret = fill_tree(trans, root, &radix, init_fill_count);
360 printf("starting run\n");
361 if (ret) {
362 err = ret;
363 goto out;
364 }
365 if (initial_only == 1) {
366 goto out;
367 }
368 for (i = 0; i < iterations; i++) {
369 op = rand() % ARRAY_SIZE(ops);
370 count = rand() % 128;
371 if (i % 2000 == 0) {
372 printf("%d\n", i);
373 fflush(stdout);
374 }
375 if (i && i % 5000 == 0) {
376 printf("open & close, root level %d nritems %d\n",
377 btrfs_header_level(&root->node->node.header),
378 btrfs_header_nritems(&root->node->node.header));
379 close_ctree(root, &super);
380 root = open_ctree("dbfile", &super);
381 }
382 while(count--) {
383 ret = ops[op](trans, root, &radix);
384 if (ret) {
385 fprintf(stderr, "op %d failed %d:%d\n",
386 op, i, iterations);
387 btrfs_print_tree(root, root->node);
388 fprintf(stderr, "op %d failed %d:%d\n",
389 op, i, iterations);
390 err = ret;
391 goto out;
392 }
393 if (ops[op] == bulk_op)
394 break;
395 if (keep_running == 0) {
396 err = 0;
397 goto out;
398 }
399 }
400 }
401out:
402 close_ctree(root, &super);
403 return err;
404}
405
diff --git a/fs/btrfs/root-tree.c b/fs/btrfs/root-tree.c
index 9cccecc0f431..52c83be4b307 100644
--- a/fs/btrfs/root-tree.c
+++ b/fs/btrfs/root-tree.c
@@ -1,7 +1,4 @@
1#include <stdio.h> 1#include <linux/module.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h" 2#include "ctree.h"
6#include "disk-io.h" 3#include "disk-io.h"
7#include "print-tree.h" 4#include "print-tree.h"
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
new file mode 100644
index 000000000000..4ae76044aeab
--- /dev/null
+++ b/fs/btrfs/super.c
@@ -0,0 +1,205 @@
1#include <linux/module.h>
2#include <linux/fs.h>
3#include <linux/pagemap.h>
4#include <linux/highmem.h>
5#include <linux/time.h>
6#include <linux/init.h>
7#include <linux/string.h>
8#include <linux/smp_lock.h>
9#include <linux/backing-dev.h>
10#include "ctree.h"
11
12#define BTRFS_SUPER_MAGIC 0x9123682E
13#if 0
14/* some random number */
15
16static struct super_operations ramfs_ops;
17static struct inode_operations ramfs_dir_inode_operations;
18
19static struct backing_dev_info ramfs_backing_dev_info = {
20 .ra_pages = 0, /* No readahead */
21 .capabilities = BDI_CAP_NO_ACCT_DIRTY | BDI_CAP_NO_WRITEBACK |
22 BDI_CAP_MAP_DIRECT | BDI_CAP_MAP_COPY |
23 BDI_CAP_READ_MAP | BDI_CAP_WRITE_MAP | BDI_CAP_EXEC_MAP,
24};
25
26struct inode *ramfs_get_inode(struct super_block *sb, int mode, dev_t dev)
27{
28 struct inode * inode = new_inode(sb);
29
30 if (inode) {
31 inode->i_mode = mode;
32 inode->i_uid = current->fsuid;
33 inode->i_gid = current->fsgid;
34 inode->i_blocks = 0;
35 inode->i_mapping->a_ops = &ramfs_aops;
36 inode->i_mapping->backing_dev_info = &ramfs_backing_dev_info;
37 inode->i_atime = inode->i_mtime = inode->i_ctime = CURRENT_TIME;
38 switch (mode & S_IFMT) {
39 default:
40 init_special_inode(inode, mode, dev);
41 break;
42 case S_IFREG:
43 inode->i_op = &ramfs_file_inode_operations;
44 inode->i_fop = &ramfs_file_operations;
45 break;
46 case S_IFDIR:
47 inode->i_op = &ramfs_dir_inode_operations;
48 inode->i_fop = &simple_dir_operations;
49
50 /* directory inodes start off with i_nlink == 2 (for "." entry) */
51 inc_nlink(inode);
52 break;
53 case S_IFLNK:
54 inode->i_op = &page_symlink_inode_operations;
55 break;
56 }
57 }
58 return inode;
59}
60
61/*
62 * File creation. Allocate an inode, and we're done..
63 */
64/* SMP-safe */
65static int
66ramfs_mknod(struct inode *dir, struct dentry *dentry, int mode, dev_t dev)
67{
68 struct inode * inode = ramfs_get_inode(dir->i_sb, mode, dev);
69 int error = -ENOSPC;
70
71 if (inode) {
72 if (dir->i_mode & S_ISGID) {
73 inode->i_gid = dir->i_gid;
74 if (S_ISDIR(mode))
75 inode->i_mode |= S_ISGID;
76 }
77 d_instantiate(dentry, inode);
78 dget(dentry); /* Extra count - pin the dentry in core */
79 error = 0;
80 dir->i_mtime = dir->i_ctime = CURRENT_TIME;
81 }
82 return error;
83}
84
85static int ramfs_mkdir(struct inode * dir, struct dentry * dentry, int mode)
86{
87 int retval = ramfs_mknod(dir, dentry, mode | S_IFDIR, 0);
88 if (!retval)
89 inc_nlink(dir);
90 return retval;
91}
92
93static int ramfs_create(struct inode *dir, struct dentry *dentry, int mode, struct nameidata *nd)
94{
95 return ramfs_mknod(dir, dentry, mode | S_IFREG, 0);
96}
97
98static int ramfs_symlink(struct inode * dir, struct dentry *dentry, const char * symname)
99{
100 struct inode *inode;
101 int error = -ENOSPC;
102
103 inode = ramfs_get_inode(dir->i_sb, S_IFLNK|S_IRWXUGO, 0);
104 if (inode) {
105 int l = strlen(symname)+1;
106 error = page_symlink(inode, symname, l);
107 if (!error) {
108 if (dir->i_mode & S_ISGID)
109 inode->i_gid = dir->i_gid;
110 d_instantiate(dentry, inode);
111 dget(dentry);
112 dir->i_mtime = dir->i_ctime = CURRENT_TIME;
113 } else
114 iput(inode);
115 }
116 return error;
117}
118
119static struct inode_operations ramfs_dir_inode_operations = {
120 .create = ramfs_create,
121 .lookup = simple_lookup,
122 .link = simple_link,
123 .unlink = simple_unlink,
124 .symlink = ramfs_symlink,
125 .mkdir = ramfs_mkdir,
126 .rmdir = simple_rmdir,
127 .mknod = ramfs_mknod,
128 .rename = simple_rename,
129};
130#endif
131
132struct inode *btrfs_get_inode(struct super_block *sb, int mode, dev_t dev)
133{
134 struct inode * inode = new_inode(sb);
135
136 if (inode) {
137 inode->i_mode = mode;
138 inode->i_uid = current->fsuid;
139 inode->i_gid = current->fsgid;
140 inode->i_blocks = 0;
141 inode->i_atime = inode->i_mtime = inode->i_ctime = CURRENT_TIME;
142 }
143 return inode;
144}
145
146static struct super_operations btrfs_ops = {
147 .statfs = simple_statfs,
148 .drop_inode = generic_delete_inode,
149};
150
151static int btrfs_fill_super(struct super_block * sb, void * data, int silent)
152{
153 struct inode * inode;
154 struct dentry * root;
155
156 sb->s_maxbytes = MAX_LFS_FILESIZE;
157 sb->s_blocksize = PAGE_CACHE_SIZE;
158 sb->s_blocksize_bits = PAGE_CACHE_SHIFT;
159 sb->s_magic = BTRFS_SUPER_MAGIC;
160 sb->s_op = &btrfs_ops;
161 sb->s_time_gran = 1;
162 inode = btrfs_get_inode(sb, S_IFDIR | 0755, 0);
163 if (!inode)
164 return -ENOMEM;
165
166 root = d_alloc_root(inode);
167 if (!root) {
168 iput(inode);
169 return -ENOMEM;
170 }
171 sb->s_root = root;
172 return 0;
173}
174
175static int btrfs_get_sb(struct file_system_type *fs_type,
176 int flags, const char *dev_name, void *data, struct vfsmount *mnt)
177{
178 return get_sb_bdev(fs_type, flags, dev_name, data,
179 btrfs_fill_super, mnt);
180}
181
182static struct file_system_type btrfs_fs_type = {
183 .owner = THIS_MODULE,
184 .name = "btrfs",
185 .get_sb = btrfs_get_sb,
186 .kill_sb = kill_block_super,
187 .fs_flags = FS_REQUIRES_DEV,
188};
189
190static int __init init_btrfs_fs(void)
191{
192 printk("btrfs loaded!\n");
193 return register_filesystem(&btrfs_fs_type);
194}
195
196static void __exit exit_btrfs_fs(void)
197{
198 unregister_filesystem(&btrfs_fs_type);
199 printk("btrfs unloaded\n");
200}
201
202module_init(init_btrfs_fs)
203module_exit(exit_btrfs_fs)
204
205MODULE_LICENSE("GPL");
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-04 05:24:26 -0500