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