aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/btrfs/Makefile2
-rw-r--r--fs/btrfs/ctree.c9
-rw-r--r--fs/btrfs/ctree.h4
-rw-r--r--fs/btrfs/disk-io.c31
-rw-r--r--fs/btrfs/disk-io.h4
-rw-r--r--fs/btrfs/extent-tree.c291
-rw-r--r--fs/btrfs/print-tree.c6
-rw-r--r--fs/btrfs/quick-test.c26
-rw-r--r--fs/btrfs/random-test.c21
9 files changed, 267 insertions, 127 deletions
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 756b1cd4cf4d..ae7f4c00c39c 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -1,7 +1,7 @@
1 1
2CC=gcc 2CC=gcc
3CFLAGS = -g -Wall 3CFLAGS = -g -Wall
4headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h 4headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h list.h
5objects = ctree.o disk-io.o radix-tree.o mkfs.o extent-tree.o print-tree.o 5objects = ctree.o disk-io.o radix-tree.o mkfs.o extent-tree.o print-tree.o
6 6
7# if you don't have sparse installed, use ls instead 7# if you don't have sparse installed, use ls instead
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 1118986d7569..72816381d203 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -50,16 +50,17 @@ int btrfs_cow_block(struct ctree_root *root,
50 memcpy(&cow->node, &buf->node, sizeof(buf->node)); 50 memcpy(&cow->node, &buf->node, sizeof(buf->node));
51 cow->node.header.blocknr = cow->blocknr; 51 cow->node.header.blocknr = cow->blocknr;
52 *cow_ret = cow; 52 *cow_ret = cow;
53 btrfs_inc_ref(root, buf);
53 if (buf == root->node) { 54 if (buf == root->node) {
54 root->node = cow; 55 root->node = cow;
55 cow->count++; 56 cow->count++;
57 if (buf != root->commit_root)
58 free_extent(root, buf->blocknr, 1);
56 tree_block_release(root, buf); 59 tree_block_release(root, buf);
57 } else { 60 } else {
58 parent->node.blockptrs[parent_slot] = cow->blocknr; 61 parent->node.blockptrs[parent_slot] = cow->blocknr;
59 BUG_ON(list_empty(&parent->dirty)); 62 BUG_ON(list_empty(&parent->dirty));
60 } 63 free_extent(root, buf->blocknr, 1);
61 if (0 && root != root->extent_root && !is_leaf(cow->node.header.flags)) {
62 btrfs_inc_ref(root, cow);
63 } 64 }
64 tree_block_release(root, buf); 65 tree_block_release(root, buf);
65 return 0; 66 return 0;
@@ -1018,7 +1019,6 @@ static int split_leaf(struct ctree_root *root, struct ctree_path *path,
1018 slot = path->slots[0]; 1019 slot = path->slots[0];
1019 nritems = l->header.nritems; 1020 nritems = l->header.nritems;
1020 mid = (nritems + 1)/ 2; 1021 mid = (nritems + 1)/ 2;
1021
1022 right_buffer = alloc_free_block(root); 1022 right_buffer = alloc_free_block(root);
1023 BUG_ON(!right_buffer); 1023 BUG_ON(!right_buffer);
1024 BUG_ON(mid == nritems); 1024 BUG_ON(mid == nritems);
@@ -1170,7 +1170,6 @@ static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level,
1170 1170
1171 node = &parent->node; 1171 node = &parent->node;
1172 nritems = node->header.nritems; 1172 nritems = node->header.nritems;
1173
1174 if (slot != nritems -1) { 1173 if (slot != nritems -1) {
1175 memmove(node->keys + slot, node->keys + slot + 1, 1174 memmove(node->keys + slot, node->keys + slot + 1,
1176 sizeof(struct key) * (nritems - slot - 1)); 1175 sizeof(struct key) * (nritems - slot - 1));
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 9fe8ba6e25c1..4a7bc4e6e747 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -51,10 +51,12 @@ struct tree_buffer;
51 */ 51 */
52struct ctree_root { 52struct ctree_root {
53 struct tree_buffer *node; 53 struct tree_buffer *node;
54 struct tree_buffer *commit_root;
54 struct ctree_root *extent_root; 55 struct ctree_root *extent_root;
55 struct key current_insert; 56 struct key current_insert;
56 int fp; 57 int fp;
57 struct radix_tree_root cache_radix; 58 struct radix_tree_root cache_radix;
59 struct radix_tree_root pinned_radix;
58 struct list_head trans; 60 struct list_head trans;
59 struct list_head cache; 61 struct list_head cache;
60 int cache_size; 62 int cache_size;
@@ -151,4 +153,6 @@ int del_item(struct ctree_root *root, struct ctree_path *path);
151int insert_item(struct ctree_root *root, struct key *key, void *data, int data_size); 153int insert_item(struct ctree_root *root, struct key *key, void *data, int data_size);
152int next_leaf(struct ctree_root *root, struct ctree_path *path); 154int next_leaf(struct ctree_root *root, struct ctree_path *path);
153int leaf_free_space(struct leaf *leaf); 155int leaf_free_space(struct leaf *leaf);
156int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap);
157int btrfs_finish_extent_commit(struct ctree_root *root);
154#endif 158#endif
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 0e1c31e682fb..2fe31c3508c1 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -153,13 +153,24 @@ static int __commit_transaction(struct ctree_root *root)
153 return ret; 153 return ret;
154} 154}
155 155
156int commit_transaction(struct ctree_root *root) 156int commit_transaction(struct ctree_root *root, struct ctree_super_block *s)
157{ 157{
158 int ret; 158 int ret = 0;
159
159 ret = __commit_transaction(root); 160 ret = __commit_transaction(root);
160 if (!ret && root != root->extent_root) 161 if (!ret && root != root->extent_root)
161 ret = __commit_transaction(root->extent_root); 162 ret = __commit_transaction(root->extent_root);
162 BUG_ON(ret); 163 BUG_ON(ret);
164 if (root->commit_root != root->node) {
165 struct tree_buffer *snap = root->commit_root;
166 root->commit_root = root->node;
167 root->node->count++;
168 ret = btrfs_drop_snapshot(root, snap);
169 BUG_ON(ret);
170 tree_block_release(root, snap);
171 }
172 write_ctree_super(root, s);
173 btrfs_finish_extent_commit(root);
163 return ret; 174 return ret;
164} 175}
165 176
@@ -168,10 +179,13 @@ static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root,
168{ 179{
169 INIT_LIST_HEAD(&root->trans); 180 INIT_LIST_HEAD(&root->trans);
170 INIT_LIST_HEAD(&root->cache); 181 INIT_LIST_HEAD(&root->cache);
182 root->cache_size = 0;
171 root->fp = fp; 183 root->fp = fp;
172 root->node = NULL; 184 root->node = NULL;
173 root->node = read_tree_block(root, info->tree_root);
174 root->extent_root = extent_root; 185 root->extent_root = extent_root;
186 root->commit_root = NULL;
187 root->node = read_tree_block(root, info->tree_root);
188 memset(&root->current_insert, 0, sizeof(root->current_insert));
175 return 0; 189 return 0;
176} 190}
177 191
@@ -188,6 +202,8 @@ struct ctree_root *open_ctree(char *filename, struct ctree_super_block *super)
188 return NULL; 202 return NULL;
189 } 203 }
190 INIT_RADIX_TREE(&root->cache_radix, GFP_KERNEL); 204 INIT_RADIX_TREE(&root->cache_radix, GFP_KERNEL);
205 INIT_RADIX_TREE(&root->pinned_radix, GFP_KERNEL);
206 INIT_RADIX_TREE(&extent_root->pinned_radix, GFP_KERNEL);
191 INIT_RADIX_TREE(&extent_root->cache_radix, GFP_KERNEL); 207 INIT_RADIX_TREE(&extent_root->cache_radix, GFP_KERNEL);
192 ret = pread(fp, super, sizeof(struct ctree_super_block), 208 ret = pread(fp, super, sizeof(struct ctree_super_block),
193 CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 209 CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE));
@@ -204,6 +220,8 @@ struct ctree_root *open_ctree(char *filename, struct ctree_super_block *super)
204 BUG_ON(ret < 0); 220 BUG_ON(ret < 0);
205 __setup_root(root, extent_root, &super->root_info, fp); 221 __setup_root(root, extent_root, &super->root_info, fp);
206 __setup_root(extent_root, extent_root, &super->extent_info, fp); 222 __setup_root(extent_root, extent_root, &super->extent_info, fp);
223 root->commit_root = root->node;
224 root->node->count++;
207 return root; 225 return root;
208} 226}
209 227
@@ -236,9 +254,11 @@ static int drop_cache(struct ctree_root *root)
236 } 254 }
237 return 0; 255 return 0;
238} 256}
239int close_ctree(struct ctree_root *root) 257int close_ctree(struct ctree_root *root, struct ctree_super_block *s)
240{ 258{
241 commit_transaction(root); 259 commit_transaction(root, s);
260 __commit_transaction(root->extent_root);
261 write_ctree_super(root, s);
242 drop_cache(root->extent_root); 262 drop_cache(root->extent_root);
243 drop_cache(root); 263 drop_cache(root);
244 BUG_ON(!list_empty(&root->trans)); 264 BUG_ON(!list_empty(&root->trans));
@@ -249,6 +269,7 @@ int close_ctree(struct ctree_root *root)
249 tree_block_release(root, root->node); 269 tree_block_release(root, root->node);
250 if (root->extent_root->node) 270 if (root->extent_root->node)
251 tree_block_release(root->extent_root, root->extent_root->node); 271 tree_block_release(root->extent_root, root->extent_root->node);
272 tree_block_release(root, root->commit_root);
252 free(root); 273 free(root);
253 printf("on close %d blocks are allocated\n", allocated_blocks); 274 printf("on close %d blocks are allocated\n", allocated_blocks);
254 return 0; 275 return 0;
diff --git a/fs/btrfs/disk-io.h b/fs/btrfs/disk-io.h
index b5dee2fae4da..1c0af7c56c21 100644
--- a/fs/btrfs/disk-io.h
+++ b/fs/btrfs/disk-io.h
@@ -18,9 +18,9 @@ struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr);
18int write_tree_block(struct ctree_root *root, struct tree_buffer *buf); 18int write_tree_block(struct ctree_root *root, struct tree_buffer *buf);
19int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf); 19int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf);
20int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf); 20int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf);
21int commit_transaction(struct ctree_root *root); 21int commit_transaction(struct ctree_root *root, struct ctree_super_block *s);
22struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s); 22struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s);
23int close_ctree(struct ctree_root *root); 23int close_ctree(struct ctree_root *root, struct ctree_super_block *s);
24void tree_block_release(struct ctree_root *root, struct tree_buffer *buf); 24void tree_block_release(struct ctree_root *root, struct tree_buffer *buf);
25int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s); 25int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s);
26int mkfs(int fd); 26int mkfs(int fd);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 25d9cd169209..0723b7f3f0c3 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -13,7 +13,8 @@
13 * other allocations are done. The pending tag is also used in the same 13 * other allocations are done. The pending tag is also used in the same
14 * manner for deletes. 14 * manner for deletes.
15 */ 15 */
16#define CTREE_EXTENT_PENDING 0 16#define CTREE_EXTENT_PENDING_ADD 0
17#define CTREE_EXTENT_PENDING_DEL 1
17 18
18static int inc_block_ref(struct ctree_root *root, u64 blocknr) 19static int inc_block_ref(struct ctree_root *root, u64 blocknr)
19{ 20{
@@ -27,20 +28,51 @@ static int inc_block_ref(struct ctree_root *root, u64 blocknr)
27 key.flags = 0; 28 key.flags = 0;
28 key.offset = 1; 29 key.offset = 1;
29 ret = search_slot(root->extent_root, &key, &path, 0, 1); 30 ret = search_slot(root->extent_root, &key, &path, 0, 1);
31 if (ret != 0)
32 BUG();
30 BUG_ON(ret != 0); 33 BUG_ON(ret != 0);
31 l = &path.nodes[0]->leaf; 34 l = &path.nodes[0]->leaf;
32 item = (struct extent_item *)(l->data + 35 item = (struct extent_item *)(l->data +
33 l->items[path.slots[0]].offset); 36 l->items[path.slots[0]].offset);
34 item->refs++; 37 item->refs++;
38
35 BUG_ON(list_empty(&path.nodes[0]->dirty)); 39 BUG_ON(list_empty(&path.nodes[0]->dirty));
36 release_path(root->extent_root, &path); 40 release_path(root->extent_root, &path);
37 return 0; 41 return 0;
38} 42}
39 43
44static int lookup_block_ref(struct ctree_root *root, u64 blocknr, int *refs)
45{
46 struct ctree_path path;
47 int ret;
48 struct key key;
49 struct leaf *l;
50 struct extent_item *item;
51 init_path(&path);
52 key.objectid = blocknr;
53 key.flags = 0;
54 key.offset = 1;
55 ret = search_slot(root->extent_root, &key, &path, 0, 0);
56 if (ret != 0)
57 BUG();
58 l = &path.nodes[0]->leaf;
59 item = (struct extent_item *)(l->data +
60 l->items[path.slots[0]].offset);
61 *refs = item->refs;
62 release_path(root->extent_root, &path);
63 return 0;
64}
65
40int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf) 66int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf)
41{ 67{
42 u64 blocknr; 68 u64 blocknr;
43 int i; 69 int i;
70
71 if (root == root->extent_root)
72 return 0;
73 if (is_leaf(buf->node.header.flags))
74 return 0;
75
44 for (i = 0; i < buf->node.header.nritems; i++) { 76 for (i = 0; i < buf->node.header.nritems; i++) {
45 blocknr = buf->node.blockptrs[i]; 77 blocknr = buf->node.blockptrs[i];
46 inc_block_ref(root, blocknr); 78 inc_block_ref(root, blocknr);
@@ -48,85 +80,187 @@ int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf)
48 return 0; 80 return 0;
49} 81}
50 82
83int btrfs_finish_extent_commit(struct ctree_root *root)
84{
85 struct ctree_root *extent_root = root->extent_root;
86 unsigned long gang[8];
87 int ret;
88 int i;
89
90 while(1) {
91 ret = radix_tree_gang_lookup(&extent_root->pinned_radix,
92 (void **)gang, 0,
93 ARRAY_SIZE(gang));
94 if (!ret)
95 break;
96 for (i = 0; i < ret; i++)
97 radix_tree_delete(&extent_root->pinned_radix, gang[i]);
98 }
99 return 0;
100}
101
51/* 102/*
52 * find all the blocks marked as pending in the radix tree and remove 103 * remove an extent from the root, returns 0 on success
53 * them from the extent map
54 */ 104 */
55static int del_pending_extents(struct ctree_root *extent_root) 105int __free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
106{
107 struct ctree_path path;
108 struct key key;
109 struct ctree_root *extent_root = root->extent_root;
110 int ret;
111 struct item *item;
112 struct extent_item *ei;
113 key.objectid = blocknr;
114 key.flags = 0;
115 key.offset = num_blocks;
116
117 init_path(&path);
118 ret = search_slot(extent_root, &key, &path, -1, 1);
119 if (ret) {
120 printf("failed to find %Lu\n", key.objectid);
121 print_tree(extent_root, extent_root->node);
122 printf("failed to find %Lu\n", key.objectid);
123 BUG();
124 }
125 item = path.nodes[0]->leaf.items + path.slots[0];
126 ei = (struct extent_item *)(path.nodes[0]->leaf.data + item->offset);
127 BUG_ON(ei->refs == 0);
128 ei->refs--;
129 if (ei->refs == 0) {
130 if (root == extent_root) {
131 int err;
132 radix_tree_preload(GFP_KERNEL);
133 err = radix_tree_insert(&extent_root->pinned_radix,
134 blocknr, (void *)blocknr);
135 BUG_ON(err);
136 radix_tree_preload_end();
137 }
138 ret = del_item(extent_root, &path);
139 if (ret)
140 BUG();
141 }
142 release_path(extent_root, &path);
143 return ret;
144}
145
146/*
147 * insert all of the pending extents reserved during the original
148 * allocation. (CTREE_EXTENT_PENDING). Returns zero if it all worked out
149 */
150static int insert_pending_extents(struct ctree_root *extent_root)
56{ 151{
57 int ret; 152 int ret;
58 struct key key; 153 struct key key;
154 struct extent_item item;
59 struct tree_buffer *gang[4]; 155 struct tree_buffer *gang[4];
60 int i; 156 int i;
61 struct ctree_path path;
62 157
158 // FIXME -ENOSPC
159 item.owner = extent_root->node->node.header.parentid;
160 item.refs = 1;
63 while(1) { 161 while(1) {
64 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix, 162 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
65 (void **)gang, 0, 163 (void **)gang, 0,
66 ARRAY_SIZE(gang), 164 ARRAY_SIZE(gang),
67 CTREE_EXTENT_PENDING); 165 CTREE_EXTENT_PENDING_ADD);
68 if (!ret) 166 if (!ret)
69 break; 167 break;
70 for (i = 0; i < ret; i++) { 168 for (i = 0; i < ret; i++) {
71 key.objectid = gang[i]->blocknr; 169 key.objectid = gang[i]->blocknr;
72 key.flags = 0; 170 key.flags = 0;
73 key.offset = 1; 171 key.offset = 1;
74 init_path(&path); 172 ret = insert_item(extent_root, &key, &item,
75 ret = search_slot(extent_root, &key, &path, -1, 1); 173 sizeof(item));
76 if (ret) { 174 if (ret) {
175 printf("%Lu already in tree\n", key.objectid);
77 print_tree(extent_root, extent_root->node); 176 print_tree(extent_root, extent_root->node);
78 printf("unable to find %Lu\n", key.objectid);
79 BUG(); 177 BUG();
80 // FIXME undo it and return sane 178 // FIXME undo it and return sane
81 return ret; 179 return ret;
82 } 180 }
83 ret = del_item(extent_root, &path); 181 radix_tree_tag_clear(&extent_root->cache_radix,
84 if (ret) { 182 gang[i]->blocknr,
85 BUG(); 183 CTREE_EXTENT_PENDING_ADD);
86 return ret; 184 tree_block_release(extent_root, gang[i]);
87 } 185 }
88 release_path(extent_root, &path); 186 }
187 return 0;
188}
189
190/*
191 * find all the blocks marked as pending in the radix tree and remove
192 * them from the extent map
193 */
194static int del_pending_extents(struct ctree_root *extent_root)
195{
196 int ret;
197 struct tree_buffer *gang[4];
198 int i;
199
200 while(1) {
201 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
202 (void **)gang, 0,
203 ARRAY_SIZE(gang),
204 CTREE_EXTENT_PENDING_DEL);
205 if (!ret)
206 break;
207 for (i = 0; i < ret; i++) {
208 ret = __free_extent(extent_root, gang[i]->blocknr, 1);
89 radix_tree_tag_clear(&extent_root->cache_radix, 209 radix_tree_tag_clear(&extent_root->cache_radix,
90 gang[i]->blocknr, 210 gang[i]->blocknr,
91 CTREE_EXTENT_PENDING); 211 CTREE_EXTENT_PENDING_DEL);
92 tree_block_release(extent_root, gang[i]); 212 tree_block_release(extent_root, gang[i]);
93 } 213 }
94 } 214 }
95 return 0; 215 return 0;
96} 216}
97 217
218static int run_pending(struct ctree_root *extent_root)
219{
220 while(radix_tree_tagged(&extent_root->cache_radix,
221 CTREE_EXTENT_PENDING_DEL) ||
222 radix_tree_tagged(&extent_root->cache_radix,
223 CTREE_EXTENT_PENDING_ADD)) {
224 insert_pending_extents(extent_root);
225 del_pending_extents(extent_root);
226 }
227 return 0;
228}
229
230
98/* 231/*
99 * remove an extent from the root, returns 0 on success 232 * remove an extent from the root, returns 0 on success
100 */ 233 */
101int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks) 234int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
102{ 235{
103 struct ctree_path path;
104 struct key key; 236 struct key key;
105 struct ctree_root *extent_root = root->extent_root; 237 struct ctree_root *extent_root = root->extent_root;
106 struct tree_buffer *t; 238 struct tree_buffer *t;
107 int pending_ret; 239 int pending_ret;
108 int ret; 240 int ret;
109 key.objectid = blocknr; 241
110 key.flags = 0;
111 key.offset = num_blocks;
112 if (root == extent_root) { 242 if (root == extent_root) {
113 t = read_tree_block(root, key.objectid); 243 t = find_tree_block(root, blocknr);
114 radix_tree_tag_set(&root->cache_radix, key.objectid, 244 if (radix_tree_tag_get(&root->cache_radix, blocknr,
115 CTREE_EXTENT_PENDING); 245 CTREE_EXTENT_PENDING_ADD)) {
246 radix_tree_tag_clear(&root->cache_radix,
247 blocknr,
248 CTREE_EXTENT_PENDING_ADD);
249 /* once for us */
250 tree_block_release(root, t);
251 /* once for the pending add */
252 tree_block_release(root, t);
253 } else {
254 radix_tree_tag_set(&root->cache_radix, blocknr,
255 CTREE_EXTENT_PENDING_DEL);
256 }
116 return 0; 257 return 0;
117 } 258 }
118 init_path(&path); 259 key.objectid = blocknr;
119 ret = search_slot(extent_root, &key, &path, -1, 1); 260 key.flags = 0;
120 if (ret) { 261 key.offset = num_blocks;
121 print_tree(extent_root, extent_root->node); 262 ret = __free_extent(root, blocknr, num_blocks);
122 printf("failed to find %Lu\n", key.objectid); 263 pending_ret = run_pending(root->extent_root);
123 BUG();
124 }
125 ret = del_item(extent_root, &path);
126 if (ret)
127 BUG();
128 release_path(extent_root, &path);
129 pending_ret = del_pending_extents(root->extent_root);
130 return ret ? ret : pending_ret; 264 return ret ? ret : pending_ret;
131} 265}
132 266
@@ -203,7 +337,7 @@ check_pending:
203 */ 337 */
204 release_path(root, &path); 338 release_path(root, &path);
205 BUG_ON(ins->objectid < search_start); 339 BUG_ON(ins->objectid < search_start);
206 if (orig_root->extent_root == orig_root) { 340 if (1 || orig_root->extent_root == orig_root) {
207 BUG_ON(num_blocks != 1); 341 BUG_ON(num_blocks != 1);
208 if ((root->current_insert.objectid <= ins->objectid && 342 if ((root->current_insert.objectid <= ins->objectid &&
209 root->current_insert.objectid + 343 root->current_insert.objectid +
@@ -211,8 +345,9 @@ check_pending:
211 (root->current_insert.objectid > ins->objectid && 345 (root->current_insert.objectid > ins->objectid &&
212 root->current_insert.objectid <= ins->objectid + 346 root->current_insert.objectid <= ins->objectid +
213 ins->offset) || 347 ins->offset) ||
348 radix_tree_lookup(&root->pinned_radix, ins->objectid) ||
214 radix_tree_tag_get(&root->cache_radix, ins->objectid, 349 radix_tree_tag_get(&root->cache_radix, ins->objectid,
215 CTREE_EXTENT_PENDING)) { 350 CTREE_EXTENT_PENDING_ADD)) {
216 search_start = ins->objectid + 1; 351 search_start = ins->objectid + 1;
217 goto check_failed; 352 goto check_failed;
218 } 353 }
@@ -226,51 +361,6 @@ error:
226} 361}
227 362
228/* 363/*
229 * insert all of the pending extents reserved during the original
230 * allocation. (CTREE_EXTENT_PENDING). Returns zero if it all worked out
231 */
232static int insert_pending_extents(struct ctree_root *extent_root)
233{
234 int ret;
235 struct key key;
236 struct extent_item item;
237 struct tree_buffer *gang[4];
238 int i;
239
240 // FIXME -ENOSPC
241 item.refs = 1;
242 item.owner = extent_root->node->node.header.parentid;
243 while(1) {
244 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
245 (void **)gang, 0,
246 ARRAY_SIZE(gang),
247 CTREE_EXTENT_PENDING);
248 if (!ret)
249 break;
250 for (i = 0; i < ret; i++) {
251 key.objectid = gang[i]->blocknr;
252 key.flags = 0;
253 key.offset = 1;
254 ret = insert_item(extent_root, &key, &item,
255 sizeof(item));
256 if (ret) {
257 printf("%Lu already in tree\n", key.objectid);
258 print_tree(extent_root, extent_root->node);
259 BUG();
260 // FIXME undo it and return sane
261 return ret;
262 }
263 radix_tree_tag_clear(&extent_root->cache_radix,
264 gang[i]->blocknr,
265 CTREE_EXTENT_PENDING);
266 printf("%Lu is not pending\n", gang[i]->blocknr);
267 tree_block_release(extent_root, gang[i]);
268 }
269 }
270 return 0;
271}
272
273/*
274 * finds a free extent and does all the dirty work required for allocation 364 * finds a free extent and does all the dirty work required for allocation
275 * returns the key for the extent through ins, and a tree buffer for 365 * returns the key for the extent through ins, and a tree buffer for
276 * the first block of the extent through buf. 366 * the first block of the extent through buf.
@@ -296,7 +386,7 @@ int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
296 sizeof(extent_item)); 386 sizeof(extent_item));
297 memset(&root->extent_root->current_insert, 0, 387 memset(&root->extent_root->current_insert, 0,
298 sizeof(struct key)); 388 sizeof(struct key));
299 pending_ret = insert_pending_extents(root->extent_root); 389 pending_ret = run_pending(root->extent_root);
300 if (ret) 390 if (ret)
301 return ret; 391 return ret;
302 if (pending_ret) 392 if (pending_ret)
@@ -309,9 +399,8 @@ int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
309 BUG_ON(ins->offset != 1); 399 BUG_ON(ins->offset != 1);
310 *buf = find_tree_block(root, ins->objectid); 400 *buf = find_tree_block(root, ins->objectid);
311 BUG_ON(!*buf); 401 BUG_ON(!*buf);
312 printf("%Lu is pending\n", ins->objectid);
313 radix_tree_tag_set(&root->cache_radix, ins->objectid, 402 radix_tree_tag_set(&root->cache_radix, ins->objectid,
314 CTREE_EXTENT_PENDING); 403 CTREE_EXTENT_PENDING_ADD);
315 (*buf)->count++; 404 (*buf)->count++;
316 dirty_tree_block(root, *buf); 405 dirty_tree_block(root, *buf);
317 return 0; 406 return 0;
@@ -331,13 +420,41 @@ struct tree_buffer *alloc_free_block(struct ctree_root *root)
331 ret = alloc_extent(root, 1, 0, (unsigned long)-1, 420 ret = alloc_extent(root, 1, 0, (unsigned long)-1,
332 root->node->node.header.parentid, 421 root->node->node.header.parentid,
333 &ins, &buf); 422 &ins, &buf);
334
335 if (ret) { 423 if (ret) {
336 BUG(); 424 BUG();
337 return NULL; 425 return NULL;
338 } 426 }
339 if (root != root->extent_root) 427 if (root != root->extent_root)
340 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix, 428 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
341 buf->blocknr, CTREE_EXTENT_PENDING)); 429 buf->blocknr,
430 CTREE_EXTENT_PENDING_ADD));
342 return buf; 431 return buf;
343} 432}
433
434int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap)
435{
436 int ret;
437 int level;
438 int refs;
439 u64 blocknr = snap->blocknr;
440
441 level = node_level(snap->node.header.flags);
442 ret = lookup_block_ref(root, snap->blocknr, &refs);
443 BUG_ON(ret);
444 if (refs == 1 && level != 0) {
445 struct node *n = &snap->node;
446 struct tree_buffer *b;
447 int i;
448 for (i = 0; i < n->header.nritems; i++) {
449 b = read_tree_block(root, n->blockptrs[i]);
450 /* FIXME, don't recurse here */
451 ret = btrfs_drop_snapshot(root, b);
452 BUG_ON(ret);
453 tree_block_release(root, b);
454 }
455 }
456 ret = free_extent(root, blocknr, 1);
457 BUG_ON(ret);
458 return 0;
459}
460
diff --git a/fs/btrfs/print-tree.c b/fs/btrfs/print-tree.c
index dda08f32c154..e32a959dd3e5 100644
--- a/fs/btrfs/print-tree.c
+++ b/fs/btrfs/print-tree.c
@@ -21,9 +21,11 @@ void print_leaf(struct leaf *l)
21 item->key.objectid, item->key.flags, item->key.offset, 21 item->key.objectid, item->key.flags, item->key.offset,
22 item->offset, item->size); 22 item->offset, item->size);
23 fflush(stdout); 23 fflush(stdout);
24 printf("\t\titem data %.*s\n", item->size, l->data+item->offset); 24 printf("\t\titem data %.*s\n", item->size,
25 l->data+item->offset);
25 ei = (struct extent_item *)(l->data + item->offset); 26 ei = (struct extent_item *)(l->data + item->offset);
26 printf("\t\textent data %u %Lu\n", ei->refs, ei->owner); 27 printf("\t\textent data refs %u owner %Lu\n", ei->refs,
28 ei->owner);
27 fflush(stdout); 29 fflush(stdout);
28 } 30 }
29} 31}
diff --git a/fs/btrfs/quick-test.c b/fs/btrfs/quick-test.c
index 8255f79ceca5..6400c7100a6a 100644
--- a/fs/btrfs/quick-test.c
+++ b/fs/btrfs/quick-test.c
@@ -19,7 +19,7 @@ int main(int ac, char **av) {
19 int i; 19 int i;
20 int num; 20 int num;
21 int ret; 21 int ret;
22 int run_size = 1024; 22 int run_size = 100000;
23 int max_key = 100000000; 23 int max_key = 100000000;
24 int tree_size = 0; 24 int tree_size = 0;
25 struct ctree_path path; 25 struct ctree_path path;
@@ -44,9 +44,9 @@ int main(int ac, char **av) {
44 if (!ret) 44 if (!ret)
45 tree_size++; 45 tree_size++;
46 free(buf); 46 free(buf);
47
47 } 48 }
48 write_ctree_super(root, &super); 49 close_ctree(root, &super);
49 close_ctree(root);
50 50
51 root = open_ctree("dbfile", &super); 51 root = open_ctree("dbfile", &super);
52 printf("starting search\n"); 52 printf("starting search\n");
@@ -65,8 +65,7 @@ int main(int ac, char **av) {
65 } 65 }
66 release_path(root, &path); 66 release_path(root, &path);
67 } 67 }
68 write_ctree_super(root, &super); 68 close_ctree(root, &super);
69 close_ctree(root);
70 root = open_ctree("dbfile", &super); 69 root = open_ctree("dbfile", &super);
71 printf("node %p level %d total ptrs %d free spc %lu\n", root->node, 70 printf("node %p level %d total ptrs %d free spc %lu\n", root->node,
72 node_level(root->node->node.header.flags), 71 node_level(root->node->node.header.flags),
@@ -90,8 +89,7 @@ int main(int ac, char **av) {
90 } 89 }
91 release_path(root, &path); 90 release_path(root, &path);
92 } 91 }
93 write_ctree_super(root, &super); 92 close_ctree(root, &super);
94 close_ctree(root);
95 root = open_ctree("dbfile", &super); 93 root = open_ctree("dbfile", &super);
96 srand(128); 94 srand(128);
97 for (i = 0; i < run_size; i++) { 95 for (i = 0; i < run_size; i++) {
@@ -106,8 +104,7 @@ int main(int ac, char **av) {
106 tree_size++; 104 tree_size++;
107 free(buf); 105 free(buf);
108 } 106 }
109 write_ctree_super(root, &super); 107 close_ctree(root, &super);
110 close_ctree(root);
111 root = open_ctree("dbfile", &super); 108 root = open_ctree("dbfile", &super);
112 srand(128); 109 srand(128);
113 printf("starting search2\n"); 110 printf("starting search2\n");
@@ -156,10 +153,17 @@ int main(int ac, char **av) {
156 } 153 }
157 release_path(root, &path); 154 release_path(root, &path);
158 } 155 }
156 /*
157 printf("previous tree:\n");
158 print_tree(root, root->commit_root);
159 printf("map before commit\n");
160 print_tree(root->extent_root, root->extent_root->node);
161 */
162 commit_transaction(root, &super);
159 printf("tree size is now %d\n", tree_size); 163 printf("tree size is now %d\n", tree_size);
164 printf("root %p commit root %p\n", root->node, root->commit_root);
160 printf("map tree\n"); 165 printf("map tree\n");
161 print_tree(root->extent_root, root->extent_root->node); 166 print_tree(root->extent_root, root->extent_root->node);
162 write_ctree_super(root, &super); 167 close_ctree(root, &super);
163 close_ctree(root);
164 return 0; 168 return 0;
165} 169}
diff --git a/fs/btrfs/random-test.c b/fs/btrfs/random-test.c
index dcc852ad6737..7b37b6bae105 100644
--- a/fs/btrfs/random-test.c
+++ b/fs/btrfs/random-test.c
@@ -8,6 +8,7 @@
8#include "print-tree.h" 8#include "print-tree.h"
9 9
10int keep_running = 1; 10int keep_running = 1;
11struct ctree_super_block super;
11 12
12static int setup_key(struct radix_tree_root *root, struct key *key, int exists) 13static int setup_key(struct radix_tree_root *root, struct key *key, int exists)
13{ 14{
@@ -59,11 +60,6 @@ error:
59 return -1; 60 return -1;
60} 61}
61 62
62static int run_commit(struct ctree_root *root, struct radix_tree_root *radix)
63{
64 return commit_transaction(root);
65}
66
67static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix) 63static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
68{ 64{
69 struct ctree_path path; 65 struct ctree_path path;
@@ -210,7 +206,7 @@ static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix,
210 goto out; 206 goto out;
211 } 207 }
212 if (i % 1000 == 0) { 208 if (i % 1000 == 0) {
213 ret = commit_transaction(root); 209 ret = commit_transaction(root, &super);
214 if (ret) { 210 if (ret) {
215 fprintf(stderr, "fill commit failed\n"); 211 fprintf(stderr, "fill commit failed\n");
216 return ret; 212 return ret;
@@ -229,7 +225,7 @@ out:
229static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix) 225static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
230{ 226{
231 int ret; 227 int ret;
232 int nr = rand() % 20000; 228 int nr = rand() % 5000;
233 static int run_nr = 0; 229 static int run_nr = 0;
234 230
235 /* do the bulk op much less frequently */ 231 /* do the bulk op much less frequently */
@@ -247,7 +243,7 @@ static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
247 243
248int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) = 244int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
249 { ins_one, insert_dup, del_one, lookup_item, 245 { ins_one, insert_dup, del_one, lookup_item,
250 lookup_enoent, bulk_op, run_commit }; 246 lookup_enoent, bulk_op };
251 247
252static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix) 248static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
253{ 249{
@@ -314,7 +310,6 @@ int print_usage(void)
314int main(int ac, char **av) 310int main(int ac, char **av)
315{ 311{
316 RADIX_TREE(radix, GFP_KERNEL); 312 RADIX_TREE(radix, GFP_KERNEL);
317 struct ctree_super_block super;
318 struct ctree_root *root; 313 struct ctree_root *root;
319 int i; 314 int i;
320 int ret; 315 int ret;
@@ -365,8 +360,7 @@ int main(int ac, char **av)
365 printf("open & close, root level %d nritems %d\n", 360 printf("open & close, root level %d nritems %d\n",
366 node_level(root->node->node.header.flags), 361 node_level(root->node->node.header.flags),
367 root->node->node.header.nritems); 362 root->node->node.header.nritems);
368 write_ctree_super(root, &super); 363 close_ctree(root, &super);
369 close_ctree(root);
370 root = open_ctree("dbfile", &super); 364 root = open_ctree("dbfile", &super);
371 } 365 }
372 while(count--) { 366 while(count--) {
@@ -380,7 +374,7 @@ int main(int ac, char **av)
380 err = ret; 374 err = ret;
381 goto out; 375 goto out;
382 } 376 }
383 if (ops[op] == bulk_op || ops[op] == run_commit) 377 if (ops[op] == bulk_op)
384 break; 378 break;
385 if (keep_running == 0) { 379 if (keep_running == 0) {
386 err = 0; 380 err = 0;
@@ -389,8 +383,7 @@ int main(int ac, char **av)
389 } 383 }
390 } 384 }
391out: 385out:
392 write_ctree_super(root, &super); 386 close_ctree(root, &super);
393 close_ctree(root);
394 return err; 387 return err;
395} 388}
396 389
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-23 17:19:37 -0500