diff options
author | Chris Mason <chris.mason@oracle.com> | 2007-03-06 20:08:01 -0500 |
---|---|---|
committer | David Woodhouse <dwmw2@hera.kernel.org> | 2007-03-06 20:08:01 -0500 |
commit | a28ec19775d62d673b034082128aca95780d3737 (patch) | |
tree | 105694ca29ed0ad6563c45a86df9a7df1abf94ff /fs | |
parent | 02217ed299c6340a35696e0610047eb96826de2d (diff) |
Btrfs: Fixup reference counting on cows
Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs')
-rw-r--r-- | fs/btrfs/Makefile | 2 | ||||
-rw-r--r-- | fs/btrfs/ctree.c | 9 | ||||
-rw-r--r-- | fs/btrfs/ctree.h | 4 | ||||
-rw-r--r-- | fs/btrfs/disk-io.c | 31 | ||||
-rw-r--r-- | fs/btrfs/disk-io.h | 4 | ||||
-rw-r--r-- | fs/btrfs/extent-tree.c | 291 | ||||
-rw-r--r-- | fs/btrfs/print-tree.c | 6 | ||||
-rw-r--r-- | fs/btrfs/quick-test.c | 26 | ||||
-rw-r--r-- | fs/btrfs/random-test.c | 21 |
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 | ||
2 | CC=gcc | 2 | CC=gcc |
3 | CFLAGS = -g -Wall | 3 | CFLAGS = -g -Wall |
4 | headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h | 4 | headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h list.h |
5 | objects = ctree.o disk-io.o radix-tree.o mkfs.o extent-tree.o print-tree.o | 5 | objects = 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 | */ |
52 | struct ctree_root { | 52 | struct 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); | |||
151 | int insert_item(struct ctree_root *root, struct key *key, void *data, int data_size); | 153 | int insert_item(struct ctree_root *root, struct key *key, void *data, int data_size); |
152 | int next_leaf(struct ctree_root *root, struct ctree_path *path); | 154 | int next_leaf(struct ctree_root *root, struct ctree_path *path); |
153 | int leaf_free_space(struct leaf *leaf); | 155 | int leaf_free_space(struct leaf *leaf); |
156 | int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap); | ||
157 | int 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 | ||
156 | int commit_transaction(struct ctree_root *root) | 156 | int 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 | } |
239 | int close_ctree(struct ctree_root *root) | 257 | int 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); | |||
18 | int write_tree_block(struct ctree_root *root, struct tree_buffer *buf); | 18 | int write_tree_block(struct ctree_root *root, struct tree_buffer *buf); |
19 | int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf); | 19 | int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf); |
20 | int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf); | 20 | int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf); |
21 | int commit_transaction(struct ctree_root *root); | 21 | int commit_transaction(struct ctree_root *root, struct ctree_super_block *s); |
22 | struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s); | 22 | struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s); |
23 | int close_ctree(struct ctree_root *root); | 23 | int close_ctree(struct ctree_root *root, struct ctree_super_block *s); |
24 | void tree_block_release(struct ctree_root *root, struct tree_buffer *buf); | 24 | void tree_block_release(struct ctree_root *root, struct tree_buffer *buf); |
25 | int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s); | 25 | int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s); |
26 | int mkfs(int fd); | 26 | int 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 | ||
18 | static int inc_block_ref(struct ctree_root *root, u64 blocknr) | 19 | static 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 | ||
44 | static 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 | |||
40 | int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf) | 66 | int 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 | ||
83 | int 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 | */ |
55 | static int del_pending_extents(struct ctree_root *extent_root) | 105 | int __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 | */ | ||
150 | static 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 | */ | ||
194 | static 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 | ||
218 | static 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 | */ |
101 | int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks) | 234 | int 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 | */ | ||
232 | static 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 | |||
434 | int 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 | ||
10 | int keep_running = 1; | 10 | int keep_running = 1; |
11 | struct ctree_super_block super; | ||
11 | 12 | ||
12 | static int setup_key(struct radix_tree_root *root, struct key *key, int exists) | 13 | static 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 | ||
62 | static int run_commit(struct ctree_root *root, struct radix_tree_root *radix) | ||
63 | { | ||
64 | return commit_transaction(root); | ||
65 | } | ||
66 | |||
67 | static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix) | 63 | static 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: | |||
229 | static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix) | 225 | static 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 | ||
248 | int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) = | 244 | int (*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 | ||
252 | static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix) | 248 | static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix) |
253 | { | 249 | { |
@@ -314,7 +310,6 @@ int print_usage(void) | |||
314 | int main(int ac, char **av) | 310 | int 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 | } |
391 | out: | 385 | out: |
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 | ||