aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/extent-tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/extent-tree.c')
-rw-r--r--fs/btrfs/extent-tree.c296
1 files changed, 296 insertions, 0 deletions
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
new file mode 100644
index 000000000000..2b663ef84496
--- /dev/null
+++ b/fs/btrfs/extent-tree.c
@@ -0,0 +1,296 @@
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
9/*
10 * pending extents are blocks that we're trying to allocate in the extent
11 * map while trying to grow the map because of other allocations. To avoid
12 * recursing, they are tagged in the radix tree and cleaned up after
13 * other allocations are done. The pending tag is also used in the same
14 * manner for deletes.
15 */
16#define CTREE_EXTENT_PENDING 0
17
18/*
19 * find all the blocks marked as pending in the radix tree and remove
20 * them from the extent map
21 */
22static int del_pending_extents(struct ctree_root *extent_root)
23{
24 int ret;
25 struct key key;
26 struct tree_buffer *gang[4];
27 int i;
28 struct ctree_path path;
29
30 while(1) {
31 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
32 (void **)gang, 0,
33 ARRAY_SIZE(gang),
34 CTREE_EXTENT_PENDING);
35 if (!ret)
36 break;
37 for (i = 0; i < ret; i++) {
38 key.objectid = gang[i]->blocknr;
39 key.flags = 0;
40 key.offset = 1;
41 init_path(&path);
42 ret = search_slot(extent_root, &key, &path, 0);
43 if (ret) {
44 print_tree(extent_root, extent_root->node);
45 printf("unable to find %lu\n", key.objectid);
46 BUG();
47 // FIXME undo it and return sane
48 return ret;
49 }
50 ret = del_item(extent_root, &path);
51 if (ret) {
52 BUG();
53 return ret;
54 }
55 release_path(extent_root, &path);
56 radix_tree_tag_clear(&extent_root->cache_radix,
57 gang[i]->blocknr,
58 CTREE_EXTENT_PENDING);
59 tree_block_release(extent_root, gang[i]);
60 }
61 }
62 return 0;
63}
64
65/*
66 * remove an extent from the root, returns 0 on success
67 */
68int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
69{
70 struct ctree_path path;
71 struct key key;
72 struct ctree_root *extent_root = root->extent_root;
73 struct tree_buffer *t;
74 int pending_ret;
75 int ret;
76 key.objectid = blocknr;
77 key.flags = 0;
78 key.offset = num_blocks;
79 if (root == extent_root) {
80 t = read_tree_block(root, key.objectid);
81 radix_tree_tag_set(&root->cache_radix, key.objectid,
82 CTREE_EXTENT_PENDING);
83 return 0;
84 }
85 init_path(&path);
86 ret = search_slot(extent_root, &key, &path, 0);
87 if (ret) {
88 print_tree(extent_root, extent_root->node);
89 printf("failed to find %lu\n", key.objectid);
90 BUG();
91 }
92 ret = del_item(extent_root, &path);
93 if (ret)
94 BUG();
95 release_path(extent_root, &path);
96 pending_ret = del_pending_extents(root->extent_root);
97 return ret ? ret : pending_ret;
98}
99
100/*
101 * walks the btree of allocated extents and find a hole of a given size.
102 * The key ins is changed to record the hole:
103 * ins->objectid == block start
104 * ins->flags = 0
105 * ins->offset == number of blocks
106 * Any available blocks before search_start are skipped.
107 */
108int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
109 u64 search_start, u64 search_end, struct key *ins)
110{
111 struct ctree_path path;
112 struct key *key;
113 int ret;
114 u64 hole_size = 0;
115 int slot = 0;
116 u64 last_block;
117 int start_found;
118 struct leaf *l;
119 struct ctree_root * root = orig_root->extent_root;
120
121check_failed:
122 init_path(&path);
123 ins->objectid = search_start;
124 ins->offset = 0;
125 ins->flags = 0;
126 start_found = 0;
127 ret = search_slot(root, ins, &path, 0);
128 while (1) {
129 l = &path.nodes[0]->leaf;
130 slot = path.slots[0];
131 if (slot >= l->header.nritems) {
132 ret = next_leaf(root, &path);
133 if (ret == 0)
134 continue;
135 if (!start_found) {
136 ins->objectid = search_start;
137 ins->offset = num_blocks;
138 start_found = 1;
139 goto check_pending;
140 }
141 ins->objectid = last_block > search_start ?
142 last_block : search_start;
143 ins->offset = num_blocks;
144 goto check_pending;
145 }
146 key = &l->items[slot].key;
147 if (key->objectid >= search_start) {
148 if (start_found) {
149 hole_size = key->objectid - last_block;
150 if (hole_size > num_blocks) {
151 ins->objectid = last_block;
152 ins->offset = num_blocks;
153 goto check_pending;
154 }
155 } else
156 start_found = 1;
157 last_block = key->objectid + key->offset;
158 }
159 path.slots[0]++;
160 }
161 // FIXME -ENOSPC
162check_pending:
163 /* we have to make sure we didn't find an extent that has already
164 * been allocated by the map tree or the original allocation
165 */
166 release_path(root, &path);
167 BUG_ON(ins->objectid < search_start);
168 if (orig_root->extent_root == orig_root) {
169 BUG_ON(num_blocks != 1);
170 if ((root->current_insert.objectid <= ins->objectid &&
171 root->current_insert.objectid +
172 root->current_insert.offset > ins->objectid) ||
173 (root->current_insert.objectid > ins->objectid &&
174 root->current_insert.objectid <= ins->objectid +
175 ins->offset) ||
176 radix_tree_tag_get(&root->cache_radix, ins->objectid,
177 CTREE_EXTENT_PENDING)) {
178 search_start = ins->objectid + 1;
179 goto check_failed;
180 }
181 }
182 if (ins->offset != 1)
183 BUG();
184 return 0;
185}
186
187/*
188 * insert all of the pending extents reserved during the original
189 * allocation. (CTREE_EXTENT_PENDING). Returns zero if it all worked out
190 */
191static int insert_pending_extents(struct ctree_root *extent_root)
192{
193 int ret;
194 struct key key;
195 struct extent_item item;
196 struct tree_buffer *gang[4];
197 int i;
198
199 // FIXME -ENOSPC
200 item.refs = 1;
201 item.owner = extent_root->node->node.header.parentid;
202 while(1) {
203 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
204 (void **)gang, 0,
205 ARRAY_SIZE(gang),
206 CTREE_EXTENT_PENDING);
207 if (!ret)
208 break;
209 for (i = 0; i < ret; i++) {
210 key.objectid = gang[i]->blocknr;
211 key.flags = 0;
212 key.offset = 1;
213 ret = insert_item(extent_root, &key, &item,
214 sizeof(item));
215 if (ret) {
216 BUG();
217 // FIXME undo it and return sane
218 return ret;
219 }
220 radix_tree_tag_clear(&extent_root->cache_radix,
221 gang[i]->blocknr,
222 CTREE_EXTENT_PENDING);
223 tree_block_release(extent_root, gang[i]);
224 }
225 }
226 return 0;
227}
228
229/*
230 * finds a free extent and does all the dirty work required for allocation
231 * returns the key for the extent through ins, and a tree buffer for
232 * the first block of the extent through buf.
233 *
234 * returns 0 if everything worked, non-zero otherwise.
235 */
236int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
237 u64 search_end, u64 owner, struct key *ins,
238 struct tree_buffer **buf)
239{
240 int ret;
241 int pending_ret;
242 struct extent_item extent_item;
243 extent_item.refs = 1;
244 extent_item.owner = owner;
245
246 ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
247 if (ret)
248 return ret;
249 if (root != root->extent_root) {
250 memcpy(&root->extent_root->current_insert, ins, sizeof(*ins));
251 ret = insert_item(root->extent_root, ins, &extent_item,
252 sizeof(extent_item));
253 memset(&root->extent_root->current_insert, 0,
254 sizeof(struct key));
255 pending_ret = insert_pending_extents(root->extent_root);
256 if (ret)
257 return ret;
258 if (pending_ret)
259 return pending_ret;
260 *buf = find_tree_block(root, ins->objectid);
261 return 0;
262 }
263 /* we're allocating an extent for the extent tree, don't recurse */
264 BUG_ON(ins->offset != 1);
265 *buf = find_tree_block(root, ins->objectid);
266 BUG_ON(!*buf);
267 radix_tree_tag_set(&root->cache_radix, ins->objectid,
268 CTREE_EXTENT_PENDING);
269 (*buf)->count++;
270 return 0;
271
272}
273
274/*
275 * helper function to allocate a block for a given tree
276 * returns the tree buffer or NULL.
277 */
278struct tree_buffer *alloc_free_block(struct ctree_root *root)
279{
280 struct key ins;
281 int ret;
282 struct tree_buffer *buf = NULL;
283
284 ret = alloc_extent(root, 1, 0, (unsigned long)-1,
285 root->node->node.header.parentid,
286 &ins, &buf);
287
288 if (ret) {
289 BUG();
290 return NULL;
291 }
292 if (root != root->extent_root)
293 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
294 buf->blocknr, CTREE_EXTENT_PENDING));
295 return buf;
296}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-04 08:08:58 -0500