Commit | Line | Data |
---|---|---|
fec577fb CM |
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 | */ | |
22 | static 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); | |
7cf75962 | 45 | printf("unable to find %Lu\n", key.objectid); |
fec577fb CM |
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 | */ | |
68 | int 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); | |
7cf75962 | 89 | printf("failed to find %Lu\n", key.objectid); |
fec577fb CM |
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 | */ | |
108 | int 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 | ||
121 | check_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 | |
162 | check_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 | */ | |
191 | static 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 | */ | |
236 | int 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 | */ | |
278 | struct 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 | } |