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
));