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 release_path(root, &path);
134 l = &path.nodes[0]->leaf;
135 slot = path.slots[0];
136 if (slot >= l->header.nritems) {
137 ret = next_leaf(root, &path);
141 ins->objectid = search_start;
142 ins->offset = num_blocks;
146 ins->objectid = last_block > search_start ?
147 last_block : search_start;
148 ins->offset = num_blocks;
151 key = &l->items[slot].key;
152 if (key->objectid >= search_start) {
154 hole_size = key->objectid - last_block;
155 if (hole_size > num_blocks) {
156 ins->objectid = last_block;
157 ins->offset = num_blocks;
162 last_block = key->objectid + key->offset;
168 /* we have to make sure we didn't find an extent that has already
169 * been allocated by the map tree or the original allocation
171 release_path(root, &path);
172 BUG_ON(ins->objectid < search_start);
173 if (orig_root->extent_root == orig_root) {
174 BUG_ON(num_blocks != 1);
175 if ((root->current_insert.objectid <= ins->objectid &&
176 root->current_insert.objectid +
177 root->current_insert.offset > ins->objectid) ||
178 (root->current_insert.objectid > ins->objectid &&
179 root->current_insert.objectid <= ins->objectid +
181 radix_tree_tag_get(&root->cache_radix, ins->objectid,
182 CTREE_EXTENT_PENDING)) {
183 search_start = ins->objectid + 1;
187 if (ins->offset != 1)
193 * insert all of the pending extents reserved during the original
194 * allocation. (CTREE_EXTENT_PENDING). Returns zero if it all worked out
196 static int insert_pending_extents(struct ctree_root *extent_root)
200 struct extent_item item;
201 struct tree_buffer *gang[4];
206 item.owner = extent_root->node->node.header.parentid;
208 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
211 CTREE_EXTENT_PENDING);
214 for (i = 0; i < ret; i++) {
215 key.objectid = gang[i]->blocknr;
218 ret = insert_item(extent_root, &key, &item,
222 // FIXME undo it and return sane
225 radix_tree_tag_clear(&extent_root->cache_radix,
227 CTREE_EXTENT_PENDING);
228 tree_block_release(extent_root, gang[i]);
235 * finds a free extent and does all the dirty work required for allocation
236 * returns the key for the extent through ins, and a tree buffer for
237 * the first block of the extent through buf.
239 * returns 0 if everything worked, non-zero otherwise.
241 int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
242 u64 search_end, u64 owner, struct key *ins,
243 struct tree_buffer **buf)
247 struct extent_item extent_item;
248 extent_item.refs = 1;
249 extent_item.owner = owner;
251 ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
254 if (root != root->extent_root) {
255 memcpy(&root->extent_root->current_insert, ins, sizeof(*ins));
256 ret = insert_item(root->extent_root, ins, &extent_item,
257 sizeof(extent_item));
258 memset(&root->extent_root->current_insert, 0,
260 pending_ret = insert_pending_extents(root->extent_root);
265 *buf = find_tree_block(root, ins->objectid);
268 /* we're allocating an extent for the extent tree, don't recurse */
269 BUG_ON(ins->offset != 1);
270 *buf = find_tree_block(root, ins->objectid);
272 radix_tree_tag_set(&root->cache_radix, ins->objectid,
273 CTREE_EXTENT_PENDING);
280 * helper function to allocate a block for a given tree
281 * returns the tree buffer or NULL.
283 struct tree_buffer *alloc_free_block(struct ctree_root *root)
287 struct tree_buffer *buf = NULL;
289 ret = alloc_extent(root, 1, 0, (unsigned long)-1,
290 root->node->node.header.parentid,
297 if (root != root->extent_root)
298 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
299 buf->blocknr, CTREE_EXTENT_PENDING));