3 #include "kerncompat.h"
4 #include "radix-tree.h"
7 #include "print-tree.h"
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
16 #define CTREE_EXTENT_PENDING 0
19 * find all the blocks marked as pending in the radix tree and remove
20 * them from the extent map
22 static int del_pending_extents(struct ctree_root *extent_root)
26 struct tree_buffer *gang[4];
28 struct ctree_path path;
31 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
34 CTREE_EXTENT_PENDING);
37 for (i = 0; i < ret; i++) {
38 key.objectid = gang[i]->blocknr;
42 ret = search_slot(extent_root, &key, &path, 0);
44 print_tree(extent_root, extent_root->node);
45 printf("unable to find %lu\n", key.objectid);
47 // FIXME undo it and return sane
50 ret = del_item(extent_root, &path);
55 release_path(extent_root, &path);
56 radix_tree_tag_clear(&extent_root->cache_radix,
58 CTREE_EXTENT_PENDING);
59 tree_block_release(extent_root, gang[i]);
66 * remove an extent from the root, returns 0 on success
68 int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
70 struct ctree_path path;
72 struct ctree_root *extent_root = root->extent_root;
73 struct tree_buffer *t;
76 key.objectid = blocknr;
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);
86 ret = search_slot(extent_root, &key, &path, 0);
88 print_tree(extent_root, extent_root->node);
89 printf("failed to find %lu\n", key.objectid);
92 ret = del_item(extent_root, &path);
95 release_path(extent_root, &path);
96 pending_ret = del_pending_extents(root->extent_root);
97 return ret ? ret : pending_ret;
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
105 * ins->offset == number of blocks
106 * Any available blocks before search_start are skipped.
108 int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
109 u64 search_start, u64 search_end, struct key *ins)
111 struct ctree_path path;
119 struct ctree_root * root = orig_root->extent_root;
123 ins->objectid = search_start;
127 ret = search_slot(root, ins, &path, 0);
129 l = &path.nodes[0]->leaf;
130 slot = path.slots[0];
131 if (slot >= l->header.nritems) {
132 ret = next_leaf(root, &path);
136 ins->objectid = search_start;
137 ins->offset = num_blocks;
141 ins->objectid = last_block > search_start ?
142 last_block : search_start;
143 ins->offset = num_blocks;
146 key = &l->items[slot].key;
147 if (key->objectid >= search_start) {
149 hole_size = key->objectid - last_block;
150 if (hole_size > num_blocks) {
151 ins->objectid = last_block;
152 ins->offset = num_blocks;
157 last_block = key->objectid + key->offset;
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
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 +
176 radix_tree_tag_get(&root->cache_radix, ins->objectid,
177 CTREE_EXTENT_PENDING)) {
178 search_start = ins->objectid + 1;
182 if (ins->offset != 1)
188 * insert all of the pending extents reserved during the original
189 * allocation. (CTREE_EXTENT_PENDING). Returns zero if it all worked out
191 static int insert_pending_extents(struct ctree_root *extent_root)
195 struct extent_item item;
196 struct tree_buffer *gang[4];
201 item.owner = extent_root->node->node.header.parentid;
203 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
206 CTREE_EXTENT_PENDING);
209 for (i = 0; i < ret; i++) {
210 key.objectid = gang[i]->blocknr;
213 ret = insert_item(extent_root, &key, &item,
217 // FIXME undo it and return sane
220 radix_tree_tag_clear(&extent_root->cache_radix,
222 CTREE_EXTENT_PENDING);
223 tree_block_release(extent_root, gang[i]);
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.
234 * returns 0 if everything worked, non-zero otherwise.
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)
242 struct extent_item extent_item;
243 extent_item.refs = 1;
244 extent_item.owner = owner;
246 ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
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,
255 pending_ret = insert_pending_extents(root->extent_root);
260 *buf = find_tree_block(root, ins->objectid);
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);
267 radix_tree_tag_set(&root->cache_radix, ins->objectid,
268 CTREE_EXTENT_PENDING);
275 * helper function to allocate a block for a given tree
276 * returns the tree buffer or NULL.
278 struct tree_buffer *alloc_free_block(struct ctree_root *root)
282 struct tree_buffer *buf = NULL;
284 ret = alloc_extent(root, 1, 0, (unsigned long)-1,
285 root->node->node.header.parentid,
292 if (root != root->extent_root)
293 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
294 buf->blocknr, CTREE_EXTENT_PENDING));