Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * Copyright (C) 2015 Facebook. All rights reserved.
4 : */
5 :
6 : #include <linux/kernel.h>
7 : #include <linux/sched/mm.h>
8 : #include "messages.h"
9 : #include "ctree.h"
10 : #include "disk-io.h"
11 : #include "locking.h"
12 : #include "free-space-tree.h"
13 : #include "transaction.h"
14 : #include "block-group.h"
15 : #include "fs.h"
16 : #include "accessors.h"
17 : #include "extent-tree.h"
18 : #include "root-tree.h"
19 :
20 : static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
21 : struct btrfs_block_group *block_group,
22 : struct btrfs_path *path);
23 :
24 42740899 : static struct btrfs_root *btrfs_free_space_root(
25 : struct btrfs_block_group *block_group)
26 : {
27 42740899 : struct btrfs_key key = {
28 : .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
29 : .type = BTRFS_ROOT_ITEM_KEY,
30 : .offset = 0,
31 : };
32 :
33 42740899 : if (btrfs_fs_incompat(block_group->fs_info, EXTENT_TREE_V2))
34 0 : key.offset = block_group->global_root_id;
35 42740899 : return btrfs_global_root(block_group->fs_info, &key);
36 : }
37 :
38 30776 : void set_free_space_tree_thresholds(struct btrfs_block_group *cache)
39 : {
40 30776 : u32 bitmap_range;
41 30776 : size_t bitmap_size;
42 30776 : u64 num_bitmaps, total_bitmap_size;
43 :
44 30776 : if (WARN_ON(cache->length == 0))
45 0 : btrfs_warn(cache->fs_info, "block group %llu length is zero",
46 : cache->start);
47 :
48 : /*
49 : * We convert to bitmaps when the disk space required for using extents
50 : * exceeds that required for using bitmaps.
51 : */
52 30776 : bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
53 30776 : num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range);
54 30776 : bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
55 30776 : total_bitmap_size = num_bitmaps * bitmap_size;
56 30776 : cache->bitmap_high_thresh = div_u64(total_bitmap_size,
57 : sizeof(struct btrfs_item));
58 :
59 : /*
60 : * We allow for a small buffer between the high threshold and low
61 : * threshold to avoid thrashing back and forth between the two formats.
62 : */
63 30776 : if (cache->bitmap_high_thresh > 100)
64 23423 : cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
65 : else
66 7353 : cache->bitmap_low_thresh = 0;
67 30776 : }
68 :
69 1502 : static int add_new_free_space_info(struct btrfs_trans_handle *trans,
70 : struct btrfs_block_group *block_group,
71 : struct btrfs_path *path)
72 : {
73 1502 : struct btrfs_root *root = btrfs_free_space_root(block_group);
74 1502 : struct btrfs_free_space_info *info;
75 1502 : struct btrfs_key key;
76 1502 : struct extent_buffer *leaf;
77 1502 : int ret;
78 :
79 1502 : key.objectid = block_group->start;
80 1502 : key.type = BTRFS_FREE_SPACE_INFO_KEY;
81 1502 : key.offset = block_group->length;
82 :
83 1502 : ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
84 1502 : if (ret)
85 0 : goto out;
86 :
87 1502 : leaf = path->nodes[0];
88 1502 : info = btrfs_item_ptr(leaf, path->slots[0],
89 : struct btrfs_free_space_info);
90 1502 : btrfs_set_free_space_extent_count(leaf, info, 0);
91 1502 : btrfs_set_free_space_flags(leaf, info, 0);
92 1502 : btrfs_mark_buffer_dirty(leaf);
93 :
94 1502 : ret = 0;
95 1502 : out:
96 1502 : btrfs_release_path(path);
97 1502 : return ret;
98 : }
99 :
100 : EXPORT_FOR_TESTS
101 24148619 : struct btrfs_free_space_info *search_free_space_info(
102 : struct btrfs_trans_handle *trans,
103 : struct btrfs_block_group *block_group,
104 : struct btrfs_path *path, int cow)
105 : {
106 24148619 : struct btrfs_fs_info *fs_info = block_group->fs_info;
107 24148619 : struct btrfs_root *root = btrfs_free_space_root(block_group);
108 24148620 : struct btrfs_key key;
109 24148620 : int ret;
110 :
111 24148620 : key.objectid = block_group->start;
112 24148620 : key.type = BTRFS_FREE_SPACE_INFO_KEY;
113 24148620 : key.offset = block_group->length;
114 :
115 24148620 : ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
116 24148615 : if (ret < 0)
117 0 : return ERR_PTR(ret);
118 24148615 : if (ret != 0) {
119 0 : btrfs_warn(fs_info, "missing free space info for %llu",
120 : block_group->start);
121 0 : ASSERT(0);
122 0 : return ERR_PTR(-ENOENT);
123 : }
124 :
125 24148615 : return btrfs_item_ptr(path->nodes[0], path->slots[0],
126 : struct btrfs_free_space_info);
127 : }
128 :
129 : /*
130 : * btrfs_search_slot() but we're looking for the greatest key less than the
131 : * passed key.
132 : */
133 21998341 : static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
134 : struct btrfs_root *root,
135 : struct btrfs_key *key, struct btrfs_path *p,
136 : int ins_len, int cow)
137 : {
138 21998341 : int ret;
139 :
140 21998341 : ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
141 21998342 : if (ret < 0)
142 : return ret;
143 :
144 21998342 : if (ret == 0) {
145 : ASSERT(0);
146 : return -EIO;
147 : }
148 :
149 21998342 : if (p->slots[0] == 0) {
150 : ASSERT(0);
151 : return -EIO;
152 : }
153 21998342 : p->slots[0]--;
154 :
155 21998342 : return 0;
156 : }
157 :
158 : static inline u32 free_space_bitmap_size(const struct btrfs_fs_info *fs_info,
159 : u64 size)
160 : {
161 44909 : return DIV_ROUND_UP(size >> fs_info->sectorsize_bits, BITS_PER_BYTE);
162 : }
163 :
164 1252 : static unsigned long *alloc_bitmap(u32 bitmap_size)
165 : {
166 1252 : unsigned long *ret;
167 1252 : unsigned int nofs_flag;
168 1252 : u32 bitmap_rounded_size = round_up(bitmap_size, sizeof(unsigned long));
169 :
170 : /*
171 : * GFP_NOFS doesn't work with kvmalloc(), but we really can't recurse
172 : * into the filesystem as the free space bitmap can be modified in the
173 : * critical section of a transaction commit.
174 : *
175 : * TODO: push the memalloc_nofs_{save,restore}() to the caller where we
176 : * know that recursion is unsafe.
177 : */
178 1252 : nofs_flag = memalloc_nofs_save();
179 1252 : ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL);
180 1252 : memalloc_nofs_restore(nofs_flag);
181 1252 : return ret;
182 : }
183 :
184 87702 : static void le_bitmap_set(unsigned long *map, unsigned int start, int len)
185 : {
186 87702 : u8 *p = ((u8 *)map) + BIT_BYTE(start);
187 87702 : const unsigned int size = start + len;
188 87702 : int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE);
189 87702 : u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start);
190 :
191 880086 : while (len - bits_to_set >= 0) {
192 792384 : *p |= mask_to_set;
193 792384 : len -= bits_to_set;
194 792384 : bits_to_set = BITS_PER_BYTE;
195 792384 : mask_to_set = ~0;
196 792384 : p++;
197 : }
198 87702 : if (len) {
199 45193 : mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
200 45193 : *p |= mask_to_set;
201 : }
202 87702 : }
203 :
204 : EXPORT_FOR_TESTS
205 199 : int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
206 : struct btrfs_block_group *block_group,
207 : struct btrfs_path *path)
208 : {
209 199 : struct btrfs_fs_info *fs_info = trans->fs_info;
210 199 : struct btrfs_root *root = btrfs_free_space_root(block_group);
211 199 : struct btrfs_free_space_info *info;
212 199 : struct btrfs_key key, found_key;
213 199 : struct extent_buffer *leaf;
214 199 : unsigned long *bitmap;
215 199 : char *bitmap_cursor;
216 199 : u64 start, end;
217 199 : u64 bitmap_range, i;
218 199 : u32 bitmap_size, flags, expected_extent_count;
219 199 : u32 extent_count = 0;
220 199 : int done = 0, nr;
221 199 : int ret;
222 :
223 199 : bitmap_size = free_space_bitmap_size(fs_info, block_group->length);
224 199 : bitmap = alloc_bitmap(bitmap_size);
225 199 : if (!bitmap) {
226 0 : ret = -ENOMEM;
227 0 : goto out;
228 : }
229 :
230 199 : start = block_group->start;
231 199 : end = block_group->start + block_group->length;
232 :
233 199 : key.objectid = end - 1;
234 199 : key.type = (u8)-1;
235 199 : key.offset = (u64)-1;
236 :
237 487 : while (!done) {
238 288 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
239 288 : if (ret)
240 0 : goto out;
241 :
242 288 : leaf = path->nodes[0];
243 288 : nr = 0;
244 288 : path->slots[0]++;
245 288 : while (path->slots[0] > 0) {
246 87901 : btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
247 :
248 87901 : if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
249 199 : ASSERT(found_key.objectid == block_group->start);
250 199 : ASSERT(found_key.offset == block_group->length);
251 199 : done = 1;
252 199 : break;
253 87702 : } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
254 87702 : u64 first, last;
255 :
256 87702 : ASSERT(found_key.objectid >= start);
257 87702 : ASSERT(found_key.objectid < end);
258 87702 : ASSERT(found_key.objectid + found_key.offset <= end);
259 :
260 87702 : first = div_u64(found_key.objectid - start,
261 : fs_info->sectorsize);
262 87702 : last = div_u64(found_key.objectid + found_key.offset - start,
263 : fs_info->sectorsize);
264 87702 : le_bitmap_set(bitmap, first, last - first);
265 :
266 87702 : extent_count++;
267 87702 : nr++;
268 87702 : path->slots[0]--;
269 : } else {
270 87990 : ASSERT(0);
271 : }
272 : }
273 :
274 288 : ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
275 288 : if (ret)
276 0 : goto out;
277 288 : btrfs_release_path(path);
278 : }
279 :
280 199 : info = search_free_space_info(trans, block_group, path, 1);
281 199 : if (IS_ERR(info)) {
282 0 : ret = PTR_ERR(info);
283 0 : goto out;
284 : }
285 199 : leaf = path->nodes[0];
286 199 : flags = btrfs_free_space_flags(leaf, info);
287 199 : flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
288 199 : btrfs_set_free_space_flags(leaf, info, flags);
289 199 : expected_extent_count = btrfs_free_space_extent_count(leaf, info);
290 199 : btrfs_mark_buffer_dirty(leaf);
291 199 : btrfs_release_path(path);
292 :
293 199 : if (extent_count != expected_extent_count) {
294 0 : btrfs_err(fs_info,
295 : "incorrect extent count for %llu; counted %u, expected %u",
296 : block_group->start, extent_count,
297 : expected_extent_count);
298 0 : ASSERT(0);
299 0 : ret = -EIO;
300 0 : goto out;
301 : }
302 :
303 199 : bitmap_cursor = (char *)bitmap;
304 199 : bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
305 199 : i = start;
306 7996 : while (i < end) {
307 7797 : unsigned long ptr;
308 7797 : u64 extent_size;
309 7797 : u32 data_size;
310 :
311 7797 : extent_size = min(end - i, bitmap_range);
312 7797 : data_size = free_space_bitmap_size(fs_info, extent_size);
313 :
314 7797 : key.objectid = i;
315 7797 : key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
316 7797 : key.offset = extent_size;
317 :
318 7797 : ret = btrfs_insert_empty_item(trans, root, path, &key,
319 : data_size);
320 7797 : if (ret)
321 0 : goto out;
322 :
323 7797 : leaf = path->nodes[0];
324 7797 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
325 7797 : write_extent_buffer(leaf, bitmap_cursor, ptr,
326 : data_size);
327 7797 : btrfs_mark_buffer_dirty(leaf);
328 7797 : btrfs_release_path(path);
329 :
330 7797 : i += extent_size;
331 7797 : bitmap_cursor += data_size;
332 : }
333 :
334 : ret = 0;
335 199 : out:
336 199 : kvfree(bitmap);
337 199 : if (ret)
338 0 : btrfs_abort_transaction(trans, ret);
339 199 : return ret;
340 : }
341 :
342 : EXPORT_FOR_TESTS
343 1053 : int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
344 : struct btrfs_block_group *block_group,
345 : struct btrfs_path *path)
346 : {
347 1053 : struct btrfs_fs_info *fs_info = trans->fs_info;
348 1053 : struct btrfs_root *root = btrfs_free_space_root(block_group);
349 1053 : struct btrfs_free_space_info *info;
350 1053 : struct btrfs_key key, found_key;
351 1053 : struct extent_buffer *leaf;
352 1053 : unsigned long *bitmap;
353 1053 : u64 start, end;
354 1053 : u32 bitmap_size, flags, expected_extent_count;
355 1053 : unsigned long nrbits, start_bit, end_bit;
356 1053 : u32 extent_count = 0;
357 1053 : int done = 0, nr;
358 1053 : int ret;
359 :
360 1053 : bitmap_size = free_space_bitmap_size(fs_info, block_group->length);
361 1053 : bitmap = alloc_bitmap(bitmap_size);
362 1053 : if (!bitmap) {
363 0 : ret = -ENOMEM;
364 0 : goto out;
365 : }
366 :
367 1053 : start = block_group->start;
368 1053 : end = block_group->start + block_group->length;
369 :
370 1053 : key.objectid = end - 1;
371 1053 : key.type = (u8)-1;
372 1053 : key.offset = (u64)-1;
373 :
374 2169 : while (!done) {
375 1116 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
376 1116 : if (ret)
377 0 : goto out;
378 :
379 1116 : leaf = path->nodes[0];
380 1116 : nr = 0;
381 1116 : path->slots[0]++;
382 1116 : while (path->slots[0] > 0) {
383 36913 : btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
384 :
385 36913 : if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
386 1053 : ASSERT(found_key.objectid == block_group->start);
387 1053 : ASSERT(found_key.offset == block_group->length);
388 1053 : done = 1;
389 1053 : break;
390 35860 : } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
391 35860 : unsigned long ptr;
392 35860 : char *bitmap_cursor;
393 35860 : u32 bitmap_pos, data_size;
394 :
395 35860 : ASSERT(found_key.objectid >= start);
396 35860 : ASSERT(found_key.objectid < end);
397 35860 : ASSERT(found_key.objectid + found_key.offset <= end);
398 :
399 35860 : bitmap_pos = div_u64(found_key.objectid - start,
400 35860 : fs_info->sectorsize *
401 : BITS_PER_BYTE);
402 35860 : bitmap_cursor = ((char *)bitmap) + bitmap_pos;
403 35860 : data_size = free_space_bitmap_size(fs_info,
404 : found_key.offset);
405 :
406 35860 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
407 35860 : read_extent_buffer(leaf, bitmap_cursor, ptr,
408 : data_size);
409 :
410 35860 : nr++;
411 35860 : path->slots[0]--;
412 : } else {
413 36976 : ASSERT(0);
414 : }
415 : }
416 :
417 1116 : ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
418 1116 : if (ret)
419 0 : goto out;
420 1116 : btrfs_release_path(path);
421 : }
422 :
423 1053 : info = search_free_space_info(trans, block_group, path, 1);
424 1053 : if (IS_ERR(info)) {
425 0 : ret = PTR_ERR(info);
426 0 : goto out;
427 : }
428 1053 : leaf = path->nodes[0];
429 1053 : flags = btrfs_free_space_flags(leaf, info);
430 1053 : flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
431 1053 : btrfs_set_free_space_flags(leaf, info, flags);
432 1053 : expected_extent_count = btrfs_free_space_extent_count(leaf, info);
433 1053 : btrfs_mark_buffer_dirty(leaf);
434 1053 : btrfs_release_path(path);
435 :
436 1053 : nrbits = block_group->length >> block_group->fs_info->sectorsize_bits;
437 1053 : start_bit = find_next_bit_le(bitmap, nrbits, 0);
438 :
439 65765 : while (start_bit < nrbits) {
440 64712 : end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit);
441 64712 : ASSERT(start_bit < end_bit);
442 :
443 64712 : key.objectid = start + start_bit * block_group->fs_info->sectorsize;
444 64712 : key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
445 64712 : key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize;
446 :
447 64712 : ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
448 64712 : if (ret)
449 0 : goto out;
450 64712 : btrfs_release_path(path);
451 :
452 64712 : extent_count++;
453 :
454 64712 : start_bit = find_next_bit_le(bitmap, nrbits, end_bit);
455 : }
456 :
457 1053 : if (extent_count != expected_extent_count) {
458 0 : btrfs_err(fs_info,
459 : "incorrect extent count for %llu; counted %u, expected %u",
460 : block_group->start, extent_count,
461 : expected_extent_count);
462 0 : ASSERT(0);
463 0 : ret = -EIO;
464 0 : goto out;
465 : }
466 :
467 : ret = 0;
468 1053 : out:
469 1053 : kvfree(bitmap);
470 1053 : if (ret)
471 0 : btrfs_abort_transaction(trans, ret);
472 1053 : return ret;
473 : }
474 :
475 18583768 : static int update_free_space_extent_count(struct btrfs_trans_handle *trans,
476 : struct btrfs_block_group *block_group,
477 : struct btrfs_path *path,
478 : int new_extents)
479 : {
480 18583768 : struct btrfs_free_space_info *info;
481 18583768 : u32 flags;
482 18583768 : u32 extent_count;
483 18583768 : int ret = 0;
484 :
485 18583768 : if (new_extents == 0)
486 : return 0;
487 :
488 5558373 : info = search_free_space_info(trans, block_group, path, 1);
489 5558373 : if (IS_ERR(info)) {
490 0 : ret = PTR_ERR(info);
491 0 : goto out;
492 : }
493 5558373 : flags = btrfs_free_space_flags(path->nodes[0], info);
494 5558373 : extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
495 :
496 5558373 : extent_count += new_extents;
497 5558373 : btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
498 5558373 : btrfs_mark_buffer_dirty(path->nodes[0]);
499 5558373 : btrfs_release_path(path);
500 :
501 5558373 : if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
502 919704 : extent_count > block_group->bitmap_high_thresh) {
503 199 : ret = convert_free_space_to_bitmaps(trans, block_group, path);
504 5558174 : } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
505 4638669 : extent_count < block_group->bitmap_low_thresh) {
506 1053 : ret = convert_free_space_to_extents(trans, block_group, path);
507 : }
508 :
509 5557121 : out:
510 : return ret;
511 : }
512 :
513 : EXPORT_FOR_TESTS
514 85636570 : int free_space_test_bit(struct btrfs_block_group *block_group,
515 : struct btrfs_path *path, u64 offset)
516 : {
517 85636570 : struct extent_buffer *leaf;
518 85636570 : struct btrfs_key key;
519 85636570 : u64 found_start, found_end;
520 85636570 : unsigned long ptr, i;
521 :
522 85636570 : leaf = path->nodes[0];
523 85636570 : btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
524 85636555 : ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
525 :
526 85636555 : found_start = key.objectid;
527 85636555 : found_end = key.objectid + key.offset;
528 85636555 : ASSERT(offset >= found_start && offset < found_end);
529 :
530 85636555 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
531 85636553 : i = div_u64(offset - found_start,
532 85636553 : block_group->fs_info->sectorsize);
533 85636553 : return !!extent_buffer_test_bit(leaf, ptr, i);
534 : }
535 :
536 10479712 : static void free_space_set_bits(struct btrfs_block_group *block_group,
537 : struct btrfs_path *path, u64 *start, u64 *size,
538 : int bit)
539 : {
540 10479712 : struct btrfs_fs_info *fs_info = block_group->fs_info;
541 10479712 : struct extent_buffer *leaf;
542 10479712 : struct btrfs_key key;
543 10479712 : u64 end = *start + *size;
544 10479712 : u64 found_start, found_end;
545 10479712 : unsigned long ptr, first, last;
546 :
547 10479712 : leaf = path->nodes[0];
548 10479712 : btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
549 10479712 : ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
550 :
551 10479712 : found_start = key.objectid;
552 10479712 : found_end = key.objectid + key.offset;
553 10479712 : ASSERT(*start >= found_start && *start < found_end);
554 10479712 : ASSERT(end > found_start);
555 :
556 10479712 : if (end > found_end)
557 : end = found_end;
558 :
559 10479712 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
560 10479712 : first = (*start - found_start) >> fs_info->sectorsize_bits;
561 10479712 : last = (end - found_start) >> fs_info->sectorsize_bits;
562 10479712 : if (bit)
563 5146947 : extent_buffer_bitmap_set(leaf, ptr, first, last - first);
564 : else
565 5332765 : extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
566 10479712 : btrfs_mark_buffer_dirty(leaf);
567 :
568 10479712 : *size -= end - *start;
569 10479712 : *start = end;
570 10479712 : }
571 :
572 : /*
573 : * We can't use btrfs_next_item() in modify_free_space_bitmap() because
574 : * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
575 : * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
576 : * looking for.
577 : */
578 34558 : static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
579 : struct btrfs_root *root, struct btrfs_path *p)
580 : {
581 34558 : struct btrfs_key key;
582 :
583 34558 : if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
584 34527 : p->slots[0]++;
585 34527 : return 0;
586 : }
587 :
588 31 : btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
589 31 : btrfs_release_path(p);
590 :
591 31 : key.objectid += key.offset;
592 31 : key.type = (u8)-1;
593 31 : key.offset = (u64)-1;
594 :
595 31 : return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
596 : }
597 :
598 : /*
599 : * If remove is 1, then we are removing free space, thus clearing bits in the
600 : * bitmap. If remove is 0, then we are adding free space, thus setting bits in
601 : * the bitmap.
602 : */
603 10478623 : static int modify_free_space_bitmap(struct btrfs_trans_handle *trans,
604 : struct btrfs_block_group *block_group,
605 : struct btrfs_path *path,
606 : u64 start, u64 size, int remove)
607 : {
608 10478623 : struct btrfs_root *root = btrfs_free_space_root(block_group);
609 10478624 : struct btrfs_key key;
610 10478624 : u64 end = start + size;
611 10478624 : u64 cur_start, cur_size;
612 10478624 : int prev_bit, next_bit;
613 10478624 : int new_extents;
614 10478624 : int ret;
615 :
616 : /*
617 : * Read the bit for the block immediately before the extent of space if
618 : * that block is within the block group.
619 : */
620 10478624 : if (start > block_group->start) {
621 10474148 : u64 prev_block = start - block_group->fs_info->sectorsize;
622 :
623 10474148 : key.objectid = prev_block;
624 10474148 : key.type = (u8)-1;
625 10474148 : key.offset = (u64)-1;
626 :
627 10474148 : ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
628 10474148 : if (ret)
629 0 : goto out;
630 :
631 10474148 : prev_bit = free_space_test_bit(block_group, path, prev_block);
632 :
633 : /* The previous block may have been in the previous bitmap. */
634 10474148 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
635 10474148 : if (start >= key.objectid + key.offset) {
636 17044 : ret = free_space_next_bitmap(trans, root, path);
637 17044 : if (ret)
638 0 : goto out;
639 : }
640 : } else {
641 4476 : key.objectid = start;
642 4476 : key.type = (u8)-1;
643 4476 : key.offset = (u64)-1;
644 :
645 4476 : ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
646 4476 : if (ret)
647 0 : goto out;
648 :
649 : prev_bit = -1;
650 : }
651 :
652 : /*
653 : * Iterate over all of the bitmaps overlapped by the extent of space,
654 : * clearing/setting bits as required.
655 : */
656 10478624 : cur_start = start;
657 10478624 : cur_size = size;
658 10479712 : while (1) {
659 10479712 : free_space_set_bits(block_group, path, &cur_start, &cur_size,
660 : !remove);
661 10479712 : if (cur_size == 0)
662 : break;
663 1088 : ret = free_space_next_bitmap(trans, root, path);
664 1088 : if (ret)
665 0 : goto out;
666 : }
667 :
668 : /*
669 : * Read the bit for the block immediately after the extent of space if
670 : * that block is within the block group.
671 : */
672 10478624 : if (end < block_group->start + block_group->length) {
673 : /* The next block may be in the next bitmap. */
674 10475857 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
675 10475857 : if (end >= key.objectid + key.offset) {
676 16426 : ret = free_space_next_bitmap(trans, root, path);
677 16426 : if (ret)
678 0 : goto out;
679 : }
680 :
681 10475857 : next_bit = free_space_test_bit(block_group, path, end);
682 : } else {
683 : next_bit = -1;
684 : }
685 :
686 10478624 : if (remove) {
687 5332194 : new_extents = -1;
688 5332194 : if (prev_bit == 1) {
689 : /* Leftover on the left. */
690 301147 : new_extents++;
691 : }
692 5332194 : if (next_bit == 1) {
693 : /* Leftover on the right. */
694 3795731 : new_extents++;
695 : }
696 : } else {
697 5146430 : new_extents = 1;
698 5146430 : if (prev_bit == 1) {
699 : /* Merging with neighbor on the left. */
700 2576024 : new_extents--;
701 : }
702 5146430 : if (next_bit == 1) {
703 : /* Merging with neighbor on the right. */
704 1300597 : new_extents--;
705 : }
706 : }
707 :
708 10478624 : btrfs_release_path(path);
709 10478624 : ret = update_free_space_extent_count(trans, block_group, path,
710 : new_extents);
711 :
712 10478624 : out:
713 10478624 : return ret;
714 : }
715 :
716 4686814 : static int remove_free_space_extent(struct btrfs_trans_handle *trans,
717 : struct btrfs_block_group *block_group,
718 : struct btrfs_path *path,
719 : u64 start, u64 size)
720 : {
721 4686814 : struct btrfs_root *root = btrfs_free_space_root(block_group);
722 4686813 : struct btrfs_key key;
723 4686813 : u64 found_start, found_end;
724 4686813 : u64 end = start + size;
725 4686813 : int new_extents = -1;
726 4686813 : int ret;
727 :
728 4686813 : key.objectid = start;
729 4686813 : key.type = (u8)-1;
730 4686813 : key.offset = (u64)-1;
731 :
732 4686813 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
733 4686812 : if (ret)
734 0 : goto out;
735 :
736 4686812 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
737 :
738 4686811 : ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
739 :
740 4686811 : found_start = key.objectid;
741 4686811 : found_end = key.objectid + key.offset;
742 4686811 : ASSERT(start >= found_start && end <= found_end);
743 :
744 : /*
745 : * Okay, now that we've found the free space extent which contains the
746 : * free space that we are removing, there are four cases:
747 : *
748 : * 1. We're using the whole extent: delete the key we found and
749 : * decrement the free space extent count.
750 : * 2. We are using part of the extent starting at the beginning: delete
751 : * the key we found and insert a new key representing the leftover at
752 : * the end. There is no net change in the number of extents.
753 : * 3. We are using part of the extent ending at the end: delete the key
754 : * we found and insert a new key representing the leftover at the
755 : * beginning. There is no net change in the number of extents.
756 : * 4. We are using part of the extent in the middle: delete the key we
757 : * found and insert two new keys representing the leftovers on each
758 : * side. Where we used to have one extent, we now have two, so increment
759 : * the extent count. We may need to convert the block group to bitmaps
760 : * as a result.
761 : */
762 :
763 : /* Delete the existing key (cases 1-4). */
764 4686811 : ret = btrfs_del_item(trans, root, path);
765 4686814 : if (ret)
766 0 : goto out;
767 :
768 : /* Add a key for leftovers at the beginning (cases 3 and 4). */
769 4686814 : if (start > found_start) {
770 210979 : key.objectid = found_start;
771 210979 : key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
772 210979 : key.offset = start - found_start;
773 :
774 210979 : btrfs_release_path(path);
775 210979 : ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
776 210979 : if (ret)
777 0 : goto out;
778 : new_extents++;
779 : }
780 :
781 : /* Add a key for leftovers at the end (cases 2 and 4). */
782 4686814 : if (end < found_end) {
783 4569650 : key.objectid = end;
784 4569650 : key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
785 4569650 : key.offset = found_end - end;
786 :
787 4569650 : btrfs_release_path(path);
788 4569649 : ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
789 4569648 : if (ret)
790 0 : goto out;
791 4569648 : new_extents++;
792 : }
793 :
794 4686812 : btrfs_release_path(path);
795 4686814 : ret = update_free_space_extent_count(trans, block_group, path,
796 : new_extents);
797 :
798 4686814 : out:
799 4686814 : return ret;
800 : }
801 :
802 : EXPORT_FOR_TESTS
803 10019007 : int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
804 : struct btrfs_block_group *block_group,
805 : struct btrfs_path *path, u64 start, u64 size)
806 : {
807 10019007 : struct btrfs_free_space_info *info;
808 10019007 : u32 flags;
809 10019007 : int ret;
810 :
811 20038014 : if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) {
812 11 : ret = __add_block_group_free_space(trans, block_group, path);
813 11 : if (ret)
814 : return ret;
815 : }
816 :
817 10019007 : info = search_free_space_info(NULL, block_group, path, 0);
818 10019004 : if (IS_ERR(info))
819 0 : return PTR_ERR(info);
820 10019004 : flags = btrfs_free_space_flags(path->nodes[0], info);
821 10019006 : btrfs_release_path(path);
822 :
823 10019008 : if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
824 5332194 : return modify_free_space_bitmap(trans, block_group, path,
825 : start, size, 1);
826 : } else {
827 4686814 : return remove_free_space_extent(trans, block_group, path,
828 : start, size);
829 : }
830 : }
831 :
832 10019350 : int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
833 : u64 start, u64 size)
834 : {
835 10019350 : struct btrfs_block_group *block_group;
836 10019350 : struct btrfs_path *path;
837 10019350 : int ret;
838 :
839 10019350 : if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
840 : return 0;
841 :
842 10019007 : path = btrfs_alloc_path();
843 10019006 : if (!path) {
844 0 : ret = -ENOMEM;
845 0 : goto out;
846 : }
847 :
848 10019006 : block_group = btrfs_lookup_block_group(trans->fs_info, start);
849 10019003 : if (!block_group) {
850 0 : ASSERT(0);
851 0 : ret = -ENOENT;
852 0 : goto out;
853 : }
854 :
855 10019003 : mutex_lock(&block_group->free_space_lock);
856 10019007 : ret = __remove_from_free_space_tree(trans, block_group, path, start,
857 : size);
858 10019008 : mutex_unlock(&block_group->free_space_lock);
859 :
860 10019008 : btrfs_put_block_group(block_group);
861 10019006 : out:
862 10019006 : btrfs_free_path(path);
863 10019006 : if (ret)
864 0 : btrfs_abort_transaction(trans, ret);
865 : return ret;
866 : }
867 :
868 3418330 : static int add_free_space_extent(struct btrfs_trans_handle *trans,
869 : struct btrfs_block_group *block_group,
870 : struct btrfs_path *path,
871 : u64 start, u64 size)
872 : {
873 3418330 : struct btrfs_root *root = btrfs_free_space_root(block_group);
874 3418330 : struct btrfs_key key, new_key;
875 3418330 : u64 found_start, found_end;
876 3418330 : u64 end = start + size;
877 3418330 : int new_extents = 1;
878 3418330 : int ret;
879 :
880 : /*
881 : * We are adding a new extent of free space, but we need to merge
882 : * extents. There are four cases here:
883 : *
884 : * 1. The new extent does not have any immediate neighbors to merge
885 : * with: add the new key and increment the free space extent count. We
886 : * may need to convert the block group to bitmaps as a result.
887 : * 2. The new extent has an immediate neighbor before it: remove the
888 : * previous key and insert a new key combining both of them. There is no
889 : * net change in the number of extents.
890 : * 3. The new extent has an immediate neighbor after it: remove the next
891 : * key and insert a new key combining both of them. There is no net
892 : * change in the number of extents.
893 : * 4. The new extent has immediate neighbors on both sides: remove both
894 : * of the keys and insert a new key combining all of them. Where we used
895 : * to have two extents, we now have one, so decrement the extent count.
896 : */
897 :
898 3418330 : new_key.objectid = start;
899 3418330 : new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
900 3418330 : new_key.offset = size;
901 :
902 : /* Search for a neighbor on the left. */
903 3418330 : if (start == block_group->start)
904 3773 : goto right;
905 3414557 : key.objectid = start - 1;
906 3414557 : key.type = (u8)-1;
907 3414557 : key.offset = (u64)-1;
908 :
909 3414557 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
910 3414557 : if (ret)
911 0 : goto out;
912 :
913 3414557 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
914 :
915 3414557 : if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
916 5918 : ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
917 5918 : btrfs_release_path(path);
918 5918 : goto right;
919 : }
920 :
921 3408639 : found_start = key.objectid;
922 3408639 : found_end = key.objectid + key.offset;
923 3408639 : ASSERT(found_start >= block_group->start &&
924 : found_end > block_group->start);
925 3408639 : ASSERT(found_start < start && found_end <= start);
926 :
927 : /*
928 : * Delete the neighbor on the left and absorb it into the new key (cases
929 : * 2 and 4).
930 : */
931 3408639 : if (found_end == start) {
932 3105642 : ret = btrfs_del_item(trans, root, path);
933 3105642 : if (ret)
934 0 : goto out;
935 3105642 : new_key.objectid = found_start;
936 3105642 : new_key.offset += key.offset;
937 3105642 : new_extents--;
938 : }
939 3408639 : btrfs_release_path(path);
940 :
941 3418330 : right:
942 : /* Search for a neighbor on the right. */
943 3418330 : if (end == block_group->start + block_group->length)
944 1950 : goto insert;
945 3416380 : key.objectid = end;
946 3416380 : key.type = (u8)-1;
947 3416380 : key.offset = (u64)-1;
948 :
949 3416380 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
950 3416380 : if (ret)
951 0 : goto out;
952 :
953 3416380 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
954 :
955 3416380 : if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
956 1916492 : ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
957 1916492 : btrfs_release_path(path);
958 1916492 : goto insert;
959 : }
960 :
961 1499888 : found_start = key.objectid;
962 1499888 : found_end = key.objectid + key.offset;
963 1499888 : ASSERT(found_start >= block_group->start &&
964 : found_end > block_group->start);
965 1499888 : ASSERT((found_start < start && found_end <= start) ||
966 : (found_start >= end && found_end > end));
967 :
968 : /*
969 : * Delete the neighbor on the right and absorb it into the new key
970 : * (cases 3 and 4).
971 : */
972 1499888 : if (found_start == end) {
973 362885 : ret = btrfs_del_item(trans, root, path);
974 362885 : if (ret)
975 0 : goto out;
976 362885 : new_key.offset += key.offset;
977 362885 : new_extents--;
978 : }
979 1499888 : btrfs_release_path(path);
980 :
981 3418330 : insert:
982 : /* Insert the new key (cases 1-4). */
983 3418330 : ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
984 3418330 : if (ret)
985 0 : goto out;
986 :
987 3418330 : btrfs_release_path(path);
988 3418330 : ret = update_free_space_extent_count(trans, block_group, path,
989 : new_extents);
990 :
991 3418330 : out:
992 3418330 : return ret;
993 : }
994 :
995 : EXPORT_FOR_TESTS
996 8564759 : int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
997 : struct btrfs_block_group *block_group,
998 : struct btrfs_path *path, u64 start, u64 size)
999 : {
1000 8564759 : struct btrfs_free_space_info *info;
1001 8564759 : u32 flags;
1002 8564759 : int ret;
1003 :
1004 17129518 : if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) {
1005 0 : ret = __add_block_group_free_space(trans, block_group, path);
1006 0 : if (ret)
1007 : return ret;
1008 : }
1009 :
1010 8564759 : info = search_free_space_info(NULL, block_group, path, 0);
1011 8564759 : if (IS_ERR(info))
1012 0 : return PTR_ERR(info);
1013 8564759 : flags = btrfs_free_space_flags(path->nodes[0], info);
1014 8564758 : btrfs_release_path(path);
1015 :
1016 8564759 : if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
1017 5146429 : return modify_free_space_bitmap(trans, block_group, path,
1018 : start, size, 0);
1019 : } else {
1020 3418330 : return add_free_space_extent(trans, block_group, path, start,
1021 : size);
1022 : }
1023 : }
1024 :
1025 8563323 : int add_to_free_space_tree(struct btrfs_trans_handle *trans,
1026 : u64 start, u64 size)
1027 : {
1028 8563323 : struct btrfs_block_group *block_group;
1029 8563323 : struct btrfs_path *path;
1030 8563323 : int ret;
1031 :
1032 8563323 : if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
1033 : return 0;
1034 :
1035 8563206 : path = btrfs_alloc_path();
1036 8563206 : if (!path) {
1037 0 : ret = -ENOMEM;
1038 0 : goto out;
1039 : }
1040 :
1041 8563206 : block_group = btrfs_lookup_block_group(trans->fs_info, start);
1042 8563205 : if (!block_group) {
1043 0 : ASSERT(0);
1044 0 : ret = -ENOENT;
1045 0 : goto out;
1046 : }
1047 :
1048 8563205 : mutex_lock(&block_group->free_space_lock);
1049 8563206 : ret = __add_to_free_space_tree(trans, block_group, path, start, size);
1050 8563206 : mutex_unlock(&block_group->free_space_lock);
1051 :
1052 8563206 : btrfs_put_block_group(block_group);
1053 8563206 : out:
1054 8563206 : btrfs_free_path(path);
1055 8563205 : if (ret)
1056 0 : btrfs_abort_transaction(trans, ret);
1057 : return ret;
1058 : }
1059 :
1060 : /*
1061 : * Populate the free space tree by walking the extent tree. Operations on the
1062 : * extent tree that happen as a result of writes to the free space tree will go
1063 : * through the normal add/remove hooks.
1064 : */
1065 33 : static int populate_free_space_tree(struct btrfs_trans_handle *trans,
1066 : struct btrfs_block_group *block_group)
1067 : {
1068 33 : struct btrfs_root *extent_root;
1069 33 : struct btrfs_path *path, *path2;
1070 33 : struct btrfs_key key;
1071 33 : u64 start, end;
1072 33 : int ret;
1073 :
1074 33 : path = btrfs_alloc_path();
1075 33 : if (!path)
1076 : return -ENOMEM;
1077 33 : path->reada = READA_FORWARD;
1078 :
1079 33 : path2 = btrfs_alloc_path();
1080 33 : if (!path2) {
1081 0 : btrfs_free_path(path);
1082 0 : return -ENOMEM;
1083 : }
1084 :
1085 33 : ret = add_new_free_space_info(trans, block_group, path2);
1086 33 : if (ret)
1087 0 : goto out;
1088 :
1089 33 : mutex_lock(&block_group->free_space_lock);
1090 :
1091 : /*
1092 : * Iterate through all of the extent and metadata items in this block
1093 : * group, adding the free space between them and the free space at the
1094 : * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
1095 : * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
1096 : * contained in.
1097 : */
1098 33 : key.objectid = block_group->start;
1099 33 : key.type = BTRFS_EXTENT_ITEM_KEY;
1100 33 : key.offset = 0;
1101 :
1102 33 : extent_root = btrfs_extent_root(trans->fs_info, key.objectid);
1103 33 : ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
1104 33 : if (ret < 0)
1105 0 : goto out_locked;
1106 33 : ASSERT(ret == 0);
1107 :
1108 33 : start = block_group->start;
1109 33 : end = block_group->start + block_group->length;
1110 155 : while (1) {
1111 155 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1112 :
1113 155 : if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1114 : key.type == BTRFS_METADATA_ITEM_KEY) {
1115 103 : if (key.objectid >= end)
1116 : break;
1117 :
1118 100 : if (start < key.objectid) {
1119 52 : ret = __add_to_free_space_tree(trans,
1120 : block_group,
1121 : path2, start,
1122 : key.objectid -
1123 : start);
1124 52 : if (ret)
1125 0 : goto out_locked;
1126 : }
1127 100 : start = key.objectid;
1128 100 : if (key.type == BTRFS_METADATA_ITEM_KEY)
1129 98 : start += trans->fs_info->nodesize;
1130 : else
1131 2 : start += key.offset;
1132 52 : } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1133 52 : if (key.objectid != block_group->start)
1134 : break;
1135 : }
1136 :
1137 133 : ret = btrfs_next_item(extent_root, path);
1138 133 : if (ret < 0)
1139 0 : goto out_locked;
1140 133 : if (ret)
1141 : break;
1142 : }
1143 33 : if (start < end) {
1144 33 : ret = __add_to_free_space_tree(trans, block_group, path2,
1145 : start, end - start);
1146 33 : if (ret)
1147 0 : goto out_locked;
1148 : }
1149 :
1150 : ret = 0;
1151 33 : out_locked:
1152 33 : mutex_unlock(&block_group->free_space_lock);
1153 33 : out:
1154 33 : btrfs_free_path(path2);
1155 33 : btrfs_free_path(path);
1156 33 : return ret;
1157 : }
1158 :
1159 2 : int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
1160 : {
1161 2 : struct btrfs_trans_handle *trans;
1162 2 : struct btrfs_root *tree_root = fs_info->tree_root;
1163 2 : struct btrfs_root *free_space_root;
1164 2 : struct btrfs_block_group *block_group;
1165 2 : struct rb_node *node;
1166 2 : int ret;
1167 :
1168 2 : trans = btrfs_start_transaction(tree_root, 0);
1169 2 : if (IS_ERR(trans))
1170 0 : return PTR_ERR(trans);
1171 :
1172 2 : set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1173 2 : set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1174 2 : free_space_root = btrfs_create_tree(trans,
1175 : BTRFS_FREE_SPACE_TREE_OBJECTID);
1176 2 : if (IS_ERR(free_space_root)) {
1177 0 : ret = PTR_ERR(free_space_root);
1178 0 : goto abort;
1179 : }
1180 2 : ret = btrfs_global_root_insert(free_space_root);
1181 2 : if (ret) {
1182 0 : btrfs_put_root(free_space_root);
1183 0 : goto abort;
1184 : }
1185 :
1186 2 : node = rb_first_cached(&fs_info->block_group_cache_tree);
1187 8 : while (node) {
1188 6 : block_group = rb_entry(node, struct btrfs_block_group,
1189 : cache_node);
1190 6 : ret = populate_free_space_tree(trans, block_group);
1191 6 : if (ret)
1192 0 : goto abort;
1193 6 : node = rb_next(node);
1194 : }
1195 :
1196 2 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1197 2 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1198 2 : clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1199 2 : ret = btrfs_commit_transaction(trans);
1200 :
1201 : /*
1202 : * Now that we've committed the transaction any reading of our commit
1203 : * root will be safe, so we can cache from the free space tree now.
1204 : */
1205 2 : clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1206 2 : return ret;
1207 :
1208 0 : abort:
1209 0 : clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1210 0 : clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1211 0 : btrfs_abort_transaction(trans, ret);
1212 0 : btrfs_end_transaction(trans);
1213 0 : return ret;
1214 : }
1215 :
1216 14 : static int clear_free_space_tree(struct btrfs_trans_handle *trans,
1217 : struct btrfs_root *root)
1218 : {
1219 14 : struct btrfs_path *path;
1220 14 : struct btrfs_key key;
1221 14 : int nr;
1222 14 : int ret;
1223 :
1224 14 : path = btrfs_alloc_path();
1225 14 : if (!path)
1226 : return -ENOMEM;
1227 :
1228 14 : key.objectid = 0;
1229 14 : key.type = 0;
1230 14 : key.offset = 0;
1231 :
1232 42 : while (1) {
1233 28 : ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1234 28 : if (ret < 0)
1235 0 : goto out;
1236 :
1237 28 : nr = btrfs_header_nritems(path->nodes[0]);
1238 28 : if (!nr)
1239 : break;
1240 :
1241 14 : path->slots[0] = 0;
1242 14 : ret = btrfs_del_items(trans, root, path, 0, nr);
1243 14 : if (ret)
1244 0 : goto out;
1245 :
1246 14 : btrfs_release_path(path);
1247 : }
1248 :
1249 : ret = 0;
1250 14 : out:
1251 14 : btrfs_free_path(path);
1252 14 : return ret;
1253 : }
1254 :
1255 5 : int btrfs_delete_free_space_tree(struct btrfs_fs_info *fs_info)
1256 : {
1257 5 : struct btrfs_trans_handle *trans;
1258 5 : struct btrfs_root *tree_root = fs_info->tree_root;
1259 5 : struct btrfs_key key = {
1260 : .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
1261 : .type = BTRFS_ROOT_ITEM_KEY,
1262 : .offset = 0,
1263 : };
1264 5 : struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key);
1265 5 : int ret;
1266 :
1267 5 : trans = btrfs_start_transaction(tree_root, 0);
1268 5 : if (IS_ERR(trans))
1269 0 : return PTR_ERR(trans);
1270 :
1271 5 : btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1272 5 : btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1273 :
1274 5 : ret = clear_free_space_tree(trans, free_space_root);
1275 5 : if (ret)
1276 0 : goto abort;
1277 :
1278 5 : ret = btrfs_del_root(trans, &free_space_root->root_key);
1279 5 : if (ret)
1280 0 : goto abort;
1281 :
1282 5 : btrfs_global_root_delete(free_space_root);
1283 :
1284 5 : spin_lock(&fs_info->trans_lock);
1285 5 : list_del(&free_space_root->dirty_list);
1286 5 : spin_unlock(&fs_info->trans_lock);
1287 :
1288 5 : btrfs_tree_lock(free_space_root->node);
1289 5 : btrfs_clear_buffer_dirty(trans, free_space_root->node);
1290 5 : btrfs_tree_unlock(free_space_root->node);
1291 5 : btrfs_free_tree_block(trans, btrfs_root_id(free_space_root),
1292 : free_space_root->node, 0, 1);
1293 :
1294 5 : btrfs_put_root(free_space_root);
1295 :
1296 5 : return btrfs_commit_transaction(trans);
1297 :
1298 0 : abort:
1299 0 : btrfs_abort_transaction(trans, ret);
1300 0 : btrfs_end_transaction(trans);
1301 0 : return ret;
1302 : }
1303 :
1304 9 : int btrfs_rebuild_free_space_tree(struct btrfs_fs_info *fs_info)
1305 : {
1306 9 : struct btrfs_trans_handle *trans;
1307 9 : struct btrfs_key key = {
1308 : .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
1309 : .type = BTRFS_ROOT_ITEM_KEY,
1310 : .offset = 0,
1311 : };
1312 9 : struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key);
1313 9 : struct rb_node *node;
1314 9 : int ret;
1315 :
1316 9 : trans = btrfs_start_transaction(free_space_root, 1);
1317 9 : if (IS_ERR(trans))
1318 0 : return PTR_ERR(trans);
1319 :
1320 9 : set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1321 9 : set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1322 :
1323 9 : ret = clear_free_space_tree(trans, free_space_root);
1324 9 : if (ret)
1325 0 : goto abort;
1326 :
1327 9 : node = rb_first_cached(&fs_info->block_group_cache_tree);
1328 36 : while (node) {
1329 27 : struct btrfs_block_group *block_group;
1330 :
1331 27 : block_group = rb_entry(node, struct btrfs_block_group,
1332 : cache_node);
1333 27 : ret = populate_free_space_tree(trans, block_group);
1334 27 : if (ret)
1335 0 : goto abort;
1336 27 : node = rb_next(node);
1337 : }
1338 :
1339 9 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1340 9 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1341 9 : clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1342 :
1343 9 : ret = btrfs_commit_transaction(trans);
1344 9 : clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1345 9 : return ret;
1346 0 : abort:
1347 0 : btrfs_abort_transaction(trans, ret);
1348 0 : btrfs_end_transaction(trans);
1349 0 : return ret;
1350 : }
1351 :
1352 1469 : static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
1353 : struct btrfs_block_group *block_group,
1354 : struct btrfs_path *path)
1355 : {
1356 1469 : int ret;
1357 :
1358 1469 : clear_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags);
1359 :
1360 1469 : ret = add_new_free_space_info(trans, block_group, path);
1361 1469 : if (ret)
1362 : return ret;
1363 :
1364 1469 : return __add_to_free_space_tree(trans, block_group, path,
1365 : block_group->start,
1366 : block_group->length);
1367 : }
1368 :
1369 1470 : int add_block_group_free_space(struct btrfs_trans_handle *trans,
1370 : struct btrfs_block_group *block_group)
1371 : {
1372 1470 : struct btrfs_fs_info *fs_info = trans->fs_info;
1373 1470 : struct btrfs_path *path = NULL;
1374 1470 : int ret = 0;
1375 :
1376 1470 : if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1377 : return 0;
1378 :
1379 1469 : mutex_lock(&block_group->free_space_lock);
1380 1469 : if (!test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags))
1381 11 : goto out;
1382 :
1383 1458 : path = btrfs_alloc_path();
1384 1458 : if (!path) {
1385 0 : ret = -ENOMEM;
1386 0 : goto out;
1387 : }
1388 :
1389 1458 : ret = __add_block_group_free_space(trans, block_group, path);
1390 :
1391 1469 : out:
1392 1469 : btrfs_free_path(path);
1393 1469 : mutex_unlock(&block_group->free_space_lock);
1394 1469 : if (ret)
1395 0 : btrfs_abort_transaction(trans, ret);
1396 : return ret;
1397 : }
1398 :
1399 533 : int remove_block_group_free_space(struct btrfs_trans_handle *trans,
1400 : struct btrfs_block_group *block_group)
1401 : {
1402 533 : struct btrfs_root *root = btrfs_free_space_root(block_group);
1403 533 : struct btrfs_path *path;
1404 533 : struct btrfs_key key, found_key;
1405 533 : struct extent_buffer *leaf;
1406 533 : u64 start, end;
1407 533 : int done = 0, nr;
1408 533 : int ret;
1409 :
1410 533 : if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
1411 : return 0;
1412 :
1413 1066 : if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) {
1414 : /* We never added this block group to the free space tree. */
1415 : return 0;
1416 : }
1417 :
1418 533 : path = btrfs_alloc_path();
1419 533 : if (!path) {
1420 0 : ret = -ENOMEM;
1421 0 : goto out;
1422 : }
1423 :
1424 533 : start = block_group->start;
1425 533 : end = block_group->start + block_group->length;
1426 :
1427 533 : key.objectid = end - 1;
1428 533 : key.type = (u8)-1;
1429 533 : key.offset = (u64)-1;
1430 :
1431 1066 : while (!done) {
1432 533 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
1433 533 : if (ret)
1434 0 : goto out;
1435 :
1436 533 : leaf = path->nodes[0];
1437 533 : nr = 0;
1438 533 : path->slots[0]++;
1439 533 : while (path->slots[0] > 0) {
1440 1072 : btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
1441 :
1442 1072 : if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
1443 533 : ASSERT(found_key.objectid == block_group->start);
1444 533 : ASSERT(found_key.offset == block_group->length);
1445 533 : done = 1;
1446 533 : nr++;
1447 533 : path->slots[0]--;
1448 533 : break;
1449 539 : } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
1450 : found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
1451 539 : ASSERT(found_key.objectid >= start);
1452 539 : ASSERT(found_key.objectid < end);
1453 539 : ASSERT(found_key.objectid + found_key.offset <= end);
1454 539 : nr++;
1455 539 : path->slots[0]--;
1456 : } else {
1457 1072 : ASSERT(0);
1458 : }
1459 : }
1460 :
1461 533 : ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
1462 533 : if (ret)
1463 0 : goto out;
1464 533 : btrfs_release_path(path);
1465 : }
1466 :
1467 : ret = 0;
1468 533 : out:
1469 533 : btrfs_free_path(path);
1470 533 : if (ret)
1471 0 : btrfs_abort_transaction(trans, ret);
1472 : return ret;
1473 : }
1474 :
1475 1845 : static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
1476 : struct btrfs_path *path,
1477 : u32 expected_extent_count)
1478 : {
1479 1845 : struct btrfs_block_group *block_group;
1480 1845 : struct btrfs_fs_info *fs_info;
1481 1845 : struct btrfs_root *root;
1482 1845 : struct btrfs_key key;
1483 1845 : int prev_bit = 0, bit;
1484 : /* Initialize to silence GCC. */
1485 1845 : u64 extent_start = 0;
1486 1845 : u64 end, offset;
1487 1845 : u64 total_found = 0;
1488 1845 : u32 extent_count = 0;
1489 1845 : int ret;
1490 :
1491 1845 : block_group = caching_ctl->block_group;
1492 1845 : fs_info = block_group->fs_info;
1493 1845 : root = btrfs_free_space_root(block_group);
1494 :
1495 1845 : end = block_group->start + block_group->length;
1496 :
1497 33460 : while (1) {
1498 33460 : ret = btrfs_next_item(root, path);
1499 33460 : if (ret < 0)
1500 0 : goto out;
1501 33460 : if (ret)
1502 : break;
1503 :
1504 32263 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1505 :
1506 32263 : if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1507 : break;
1508 :
1509 31615 : ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
1510 31615 : ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1511 :
1512 : offset = key.objectid;
1513 64718191 : while (offset < key.objectid + key.offset) {
1514 64686576 : bit = free_space_test_bit(block_group, path, offset);
1515 64686576 : if (prev_bit == 0 && bit == 1) {
1516 : extent_start = offset;
1517 64640389 : } else if (prev_bit == 1 && bit == 0) {
1518 44360 : u64 space_added;
1519 :
1520 44360 : ret = add_new_free_space(block_group, extent_start,
1521 : offset, &space_added);
1522 44360 : if (ret)
1523 0 : goto out;
1524 44360 : total_found += space_added;
1525 44360 : if (total_found > CACHING_CTL_WAKE_UP) {
1526 768 : total_found = 0;
1527 768 : wake_up(&caching_ctl->wait);
1528 : }
1529 44360 : extent_count++;
1530 : }
1531 64686576 : prev_bit = bit;
1532 64686576 : offset += fs_info->sectorsize;
1533 : }
1534 : }
1535 1845 : if (prev_bit == 1) {
1536 1827 : ret = add_new_free_space(block_group, extent_start, end, NULL);
1537 1827 : if (ret)
1538 0 : goto out;
1539 1827 : extent_count++;
1540 : }
1541 :
1542 1845 : if (extent_count != expected_extent_count) {
1543 0 : btrfs_err(fs_info,
1544 : "incorrect extent count for %llu; counted %u, expected %u",
1545 : block_group->start, extent_count,
1546 : expected_extent_count);
1547 0 : ASSERT(0);
1548 0 : ret = -EIO;
1549 0 : goto out;
1550 : }
1551 :
1552 : ret = 0;
1553 1845 : out:
1554 1845 : return ret;
1555 : }
1556 :
1557 3383 : static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
1558 : struct btrfs_path *path,
1559 : u32 expected_extent_count)
1560 : {
1561 3383 : struct btrfs_block_group *block_group;
1562 3383 : struct btrfs_fs_info *fs_info;
1563 3383 : struct btrfs_root *root;
1564 3383 : struct btrfs_key key;
1565 3383 : u64 end;
1566 3383 : u64 total_found = 0;
1567 3383 : u32 extent_count = 0;
1568 3383 : int ret;
1569 :
1570 3383 : block_group = caching_ctl->block_group;
1571 3383 : fs_info = block_group->fs_info;
1572 3383 : root = btrfs_free_space_root(block_group);
1573 :
1574 3383 : end = block_group->start + block_group->length;
1575 :
1576 101417 : while (1) {
1577 52400 : u64 space_added;
1578 :
1579 52400 : ret = btrfs_next_item(root, path);
1580 52400 : if (ret < 0)
1581 0 : goto out;
1582 52400 : if (ret)
1583 : break;
1584 :
1585 51534 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1586 :
1587 51534 : if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1588 : break;
1589 :
1590 49017 : ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
1591 49017 : ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1592 :
1593 49017 : ret = add_new_free_space(block_group, key.objectid,
1594 49017 : key.objectid + key.offset, &space_added);
1595 49017 : if (ret)
1596 0 : goto out;
1597 49017 : total_found += space_added;
1598 49017 : if (total_found > CACHING_CTL_WAKE_UP) {
1599 11318 : total_found = 0;
1600 11318 : wake_up(&caching_ctl->wait);
1601 : }
1602 49017 : extent_count++;
1603 : }
1604 :
1605 3383 : if (extent_count != expected_extent_count) {
1606 0 : btrfs_err(fs_info,
1607 : "incorrect extent count for %llu; counted %u, expected %u",
1608 : block_group->start, extent_count,
1609 : expected_extent_count);
1610 0 : ASSERT(0);
1611 0 : ret = -EIO;
1612 0 : goto out;
1613 : }
1614 :
1615 : ret = 0;
1616 3383 : out:
1617 3383 : return ret;
1618 : }
1619 :
1620 5228 : int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
1621 : {
1622 5228 : struct btrfs_block_group *block_group;
1623 5228 : struct btrfs_free_space_info *info;
1624 5228 : struct btrfs_path *path;
1625 5228 : u32 extent_count, flags;
1626 5228 : int ret;
1627 :
1628 5228 : block_group = caching_ctl->block_group;
1629 :
1630 5228 : path = btrfs_alloc_path();
1631 5228 : if (!path)
1632 : return -ENOMEM;
1633 :
1634 : /*
1635 : * Just like caching_thread() doesn't want to deadlock on the extent
1636 : * tree, we don't want to deadlock on the free space tree.
1637 : */
1638 5228 : path->skip_locking = 1;
1639 5228 : path->search_commit_root = 1;
1640 5228 : path->reada = READA_FORWARD;
1641 :
1642 5228 : info = search_free_space_info(NULL, block_group, path, 0);
1643 5228 : if (IS_ERR(info)) {
1644 0 : ret = PTR_ERR(info);
1645 0 : goto out;
1646 : }
1647 5228 : extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
1648 5228 : flags = btrfs_free_space_flags(path->nodes[0], info);
1649 :
1650 : /*
1651 : * We left path pointing to the free space info item, so now
1652 : * load_free_space_foo can just iterate through the free space tree from
1653 : * there.
1654 : */
1655 5228 : if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
1656 1845 : ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
1657 : else
1658 3383 : ret = load_free_space_extents(caching_ctl, path, extent_count);
1659 :
1660 5228 : out:
1661 5228 : btrfs_free_path(path);
1662 5228 : return ret;
1663 : }
|
