2 * Copyright (C) 2015 Facebook. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #include <linux/kernel.h>
20 #include <linux/vmalloc.h>
24 #include "free-space-tree.h"
25 #include "transaction.h"
28 static int __add_block_group_free_space(struct btrfs_trans_handle
*trans
,
29 struct btrfs_fs_info
*fs_info
,
30 struct btrfs_block_group_cache
*block_group
,
31 struct btrfs_path
*path
);
33 void set_free_space_tree_thresholds(struct btrfs_block_group_cache
*cache
)
37 u64 num_bitmaps
, total_bitmap_size
;
40 * We convert to bitmaps when the disk space required for using extents
41 * exceeds that required for using bitmaps.
43 bitmap_range
= cache
->sectorsize
* BTRFS_FREE_SPACE_BITMAP_BITS
;
44 num_bitmaps
= div_u64(cache
->key
.offset
+ bitmap_range
- 1,
46 bitmap_size
= sizeof(struct btrfs_item
) + BTRFS_FREE_SPACE_BITMAP_SIZE
;
47 total_bitmap_size
= num_bitmaps
* bitmap_size
;
48 cache
->bitmap_high_thresh
= div_u64(total_bitmap_size
,
49 sizeof(struct btrfs_item
));
52 * We allow for a small buffer between the high threshold and low
53 * threshold to avoid thrashing back and forth between the two formats.
55 if (cache
->bitmap_high_thresh
> 100)
56 cache
->bitmap_low_thresh
= cache
->bitmap_high_thresh
- 100;
58 cache
->bitmap_low_thresh
= 0;
61 static int add_new_free_space_info(struct btrfs_trans_handle
*trans
,
62 struct btrfs_fs_info
*fs_info
,
63 struct btrfs_block_group_cache
*block_group
,
64 struct btrfs_path
*path
)
66 struct btrfs_root
*root
= fs_info
->free_space_root
;
67 struct btrfs_free_space_info
*info
;
69 struct extent_buffer
*leaf
;
72 key
.objectid
= block_group
->key
.objectid
;
73 key
.type
= BTRFS_FREE_SPACE_INFO_KEY
;
74 key
.offset
= block_group
->key
.offset
;
76 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, sizeof(*info
));
80 leaf
= path
->nodes
[0];
81 info
= btrfs_item_ptr(leaf
, path
->slots
[0],
82 struct btrfs_free_space_info
);
83 btrfs_set_free_space_extent_count(leaf
, info
, 0);
84 btrfs_set_free_space_flags(leaf
, info
, 0);
85 btrfs_mark_buffer_dirty(leaf
);
89 btrfs_release_path(path
);
93 struct btrfs_free_space_info
*
94 search_free_space_info(struct btrfs_trans_handle
*trans
,
95 struct btrfs_fs_info
*fs_info
,
96 struct btrfs_block_group_cache
*block_group
,
97 struct btrfs_path
*path
, int cow
)
99 struct btrfs_root
*root
= fs_info
->free_space_root
;
100 struct btrfs_key key
;
103 key
.objectid
= block_group
->key
.objectid
;
104 key
.type
= BTRFS_FREE_SPACE_INFO_KEY
;
105 key
.offset
= block_group
->key
.offset
;
107 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, cow
);
111 btrfs_warn(fs_info
, "missing free space info for %llu\n",
112 block_group
->key
.objectid
);
114 return ERR_PTR(-ENOENT
);
117 return btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
118 struct btrfs_free_space_info
);
122 * btrfs_search_slot() but we're looking for the greatest key less than the
125 static int btrfs_search_prev_slot(struct btrfs_trans_handle
*trans
,
126 struct btrfs_root
*root
,
127 struct btrfs_key
*key
, struct btrfs_path
*p
,
128 int ins_len
, int cow
)
132 ret
= btrfs_search_slot(trans
, root
, key
, p
, ins_len
, cow
);
141 if (p
->slots
[0] == 0) {
150 static inline u32
free_space_bitmap_size(u64 size
, u32 sectorsize
)
152 return DIV_ROUND_UP((u32
)div_u64(size
, sectorsize
), BITS_PER_BYTE
);
155 static unsigned long *alloc_bitmap(u32 bitmap_size
)
160 * The allocation size varies, observed numbers were < 4K up to 16K.
161 * Using vmalloc unconditionally would be too heavy, we'll try
162 * contiguous allocations first.
164 if (bitmap_size
<= PAGE_SIZE
)
165 return kzalloc(bitmap_size
, GFP_NOFS
);
167 mem
= kzalloc(bitmap_size
, GFP_NOFS
| __GFP_HIGHMEM
| __GFP_NOWARN
);
171 return __vmalloc(bitmap_size
, GFP_NOFS
| __GFP_HIGHMEM
| __GFP_ZERO
,
175 int convert_free_space_to_bitmaps(struct btrfs_trans_handle
*trans
,
176 struct btrfs_fs_info
*fs_info
,
177 struct btrfs_block_group_cache
*block_group
,
178 struct btrfs_path
*path
)
180 struct btrfs_root
*root
= fs_info
->free_space_root
;
181 struct btrfs_free_space_info
*info
;
182 struct btrfs_key key
, found_key
;
183 struct extent_buffer
*leaf
;
184 unsigned long *bitmap
;
188 u32 bitmap_size
, flags
, expected_extent_count
;
189 u32 extent_count
= 0;
193 bitmap_size
= free_space_bitmap_size(block_group
->key
.offset
,
194 block_group
->sectorsize
);
195 bitmap
= alloc_bitmap(bitmap_size
);
201 start
= block_group
->key
.objectid
;
202 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
204 key
.objectid
= end
- 1;
206 key
.offset
= (u64
)-1;
209 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, -1, 1);
213 leaf
= path
->nodes
[0];
216 while (path
->slots
[0] > 0) {
217 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0] - 1);
219 if (found_key
.type
== BTRFS_FREE_SPACE_INFO_KEY
) {
220 ASSERT(found_key
.objectid
== block_group
->key
.objectid
);
221 ASSERT(found_key
.offset
== block_group
->key
.offset
);
224 } else if (found_key
.type
== BTRFS_FREE_SPACE_EXTENT_KEY
) {
227 ASSERT(found_key
.objectid
>= start
);
228 ASSERT(found_key
.objectid
< end
);
229 ASSERT(found_key
.objectid
+ found_key
.offset
<= end
);
231 first
= div_u64(found_key
.objectid
- start
,
232 block_group
->sectorsize
);
233 last
= div_u64(found_key
.objectid
+ found_key
.offset
- start
,
234 block_group
->sectorsize
);
235 bitmap_set(bitmap
, first
, last
- first
);
245 ret
= btrfs_del_items(trans
, root
, path
, path
->slots
[0], nr
);
248 btrfs_release_path(path
);
251 info
= search_free_space_info(trans
, fs_info
, block_group
, path
, 1);
256 leaf
= path
->nodes
[0];
257 flags
= btrfs_free_space_flags(leaf
, info
);
258 flags
|= BTRFS_FREE_SPACE_USING_BITMAPS
;
259 btrfs_set_free_space_flags(leaf
, info
, flags
);
260 expected_extent_count
= btrfs_free_space_extent_count(leaf
, info
);
261 btrfs_mark_buffer_dirty(leaf
);
262 btrfs_release_path(path
);
264 if (extent_count
!= expected_extent_count
) {
265 btrfs_err(fs_info
, "incorrect extent count for %llu; counted %u, expected %u",
266 block_group
->key
.objectid
, extent_count
,
267 expected_extent_count
);
273 bitmap_cursor
= (char *)bitmap
;
274 bitmap_range
= block_group
->sectorsize
* BTRFS_FREE_SPACE_BITMAP_BITS
;
281 extent_size
= min(end
- i
, bitmap_range
);
282 data_size
= free_space_bitmap_size(extent_size
,
283 block_group
->sectorsize
);
286 key
.type
= BTRFS_FREE_SPACE_BITMAP_KEY
;
287 key
.offset
= extent_size
;
289 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
294 leaf
= path
->nodes
[0];
295 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
296 write_extent_buffer(leaf
, bitmap_cursor
, ptr
,
298 btrfs_mark_buffer_dirty(leaf
);
299 btrfs_release_path(path
);
302 bitmap_cursor
+= data_size
;
309 btrfs_abort_transaction(trans
, root
, ret
);
313 int convert_free_space_to_extents(struct btrfs_trans_handle
*trans
,
314 struct btrfs_fs_info
*fs_info
,
315 struct btrfs_block_group_cache
*block_group
,
316 struct btrfs_path
*path
)
318 struct btrfs_root
*root
= fs_info
->free_space_root
;
319 struct btrfs_free_space_info
*info
;
320 struct btrfs_key key
, found_key
;
321 struct extent_buffer
*leaf
;
322 unsigned long *bitmap
;
324 /* Initialize to silence GCC. */
325 u64 extent_start
= 0;
327 u32 bitmap_size
, flags
, expected_extent_count
;
328 int prev_bit
= 0, bit
, bitnr
;
329 u32 extent_count
= 0;
333 bitmap_size
= free_space_bitmap_size(block_group
->key
.offset
,
334 block_group
->sectorsize
);
335 bitmap
= alloc_bitmap(bitmap_size
);
341 start
= block_group
->key
.objectid
;
342 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
344 key
.objectid
= end
- 1;
346 key
.offset
= (u64
)-1;
349 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, -1, 1);
353 leaf
= path
->nodes
[0];
356 while (path
->slots
[0] > 0) {
357 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0] - 1);
359 if (found_key
.type
== BTRFS_FREE_SPACE_INFO_KEY
) {
360 ASSERT(found_key
.objectid
== block_group
->key
.objectid
);
361 ASSERT(found_key
.offset
== block_group
->key
.offset
);
364 } else if (found_key
.type
== BTRFS_FREE_SPACE_BITMAP_KEY
) {
367 u32 bitmap_pos
, data_size
;
369 ASSERT(found_key
.objectid
>= start
);
370 ASSERT(found_key
.objectid
< end
);
371 ASSERT(found_key
.objectid
+ found_key
.offset
<= end
);
373 bitmap_pos
= div_u64(found_key
.objectid
- start
,
374 block_group
->sectorsize
*
376 bitmap_cursor
= ((char *)bitmap
) + bitmap_pos
;
377 data_size
= free_space_bitmap_size(found_key
.offset
,
378 block_group
->sectorsize
);
380 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0] - 1);
381 read_extent_buffer(leaf
, bitmap_cursor
, ptr
,
391 ret
= btrfs_del_items(trans
, root
, path
, path
->slots
[0], nr
);
394 btrfs_release_path(path
);
397 info
= search_free_space_info(trans
, fs_info
, block_group
, path
, 1);
402 leaf
= path
->nodes
[0];
403 flags
= btrfs_free_space_flags(leaf
, info
);
404 flags
&= ~BTRFS_FREE_SPACE_USING_BITMAPS
;
405 btrfs_set_free_space_flags(leaf
, info
, flags
);
406 expected_extent_count
= btrfs_free_space_extent_count(leaf
, info
);
407 btrfs_mark_buffer_dirty(leaf
);
408 btrfs_release_path(path
);
412 while (offset
< end
) {
413 bit
= !!test_bit(bitnr
, bitmap
);
414 if (prev_bit
== 0 && bit
== 1) {
415 extent_start
= offset
;
416 } else if (prev_bit
== 1 && bit
== 0) {
417 key
.objectid
= extent_start
;
418 key
.type
= BTRFS_FREE_SPACE_EXTENT_KEY
;
419 key
.offset
= offset
- extent_start
;
421 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, 0);
424 btrfs_release_path(path
);
429 offset
+= block_group
->sectorsize
;
433 key
.objectid
= extent_start
;
434 key
.type
= BTRFS_FREE_SPACE_EXTENT_KEY
;
435 key
.offset
= end
- extent_start
;
437 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, 0);
440 btrfs_release_path(path
);
445 if (extent_count
!= expected_extent_count
) {
446 btrfs_err(fs_info
, "incorrect extent count for %llu; counted %u, expected %u",
447 block_group
->key
.objectid
, extent_count
,
448 expected_extent_count
);
458 btrfs_abort_transaction(trans
, root
, ret
);
462 static int update_free_space_extent_count(struct btrfs_trans_handle
*trans
,
463 struct btrfs_fs_info
*fs_info
,
464 struct btrfs_block_group_cache
*block_group
,
465 struct btrfs_path
*path
,
468 struct btrfs_free_space_info
*info
;
473 if (new_extents
== 0)
476 info
= search_free_space_info(trans
, fs_info
, block_group
, path
, 1);
481 flags
= btrfs_free_space_flags(path
->nodes
[0], info
);
482 extent_count
= btrfs_free_space_extent_count(path
->nodes
[0], info
);
484 extent_count
+= new_extents
;
485 btrfs_set_free_space_extent_count(path
->nodes
[0], info
, extent_count
);
486 btrfs_mark_buffer_dirty(path
->nodes
[0]);
487 btrfs_release_path(path
);
489 if (!(flags
& BTRFS_FREE_SPACE_USING_BITMAPS
) &&
490 extent_count
> block_group
->bitmap_high_thresh
) {
491 ret
= convert_free_space_to_bitmaps(trans
, fs_info
, block_group
,
493 } else if ((flags
& BTRFS_FREE_SPACE_USING_BITMAPS
) &&
494 extent_count
< block_group
->bitmap_low_thresh
) {
495 ret
= convert_free_space_to_extents(trans
, fs_info
, block_group
,
503 int free_space_test_bit(struct btrfs_block_group_cache
*block_group
,
504 struct btrfs_path
*path
, u64 offset
)
506 struct extent_buffer
*leaf
;
507 struct btrfs_key key
;
508 u64 found_start
, found_end
;
509 unsigned long ptr
, i
;
511 leaf
= path
->nodes
[0];
512 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
513 ASSERT(key
.type
== BTRFS_FREE_SPACE_BITMAP_KEY
);
515 found_start
= key
.objectid
;
516 found_end
= key
.objectid
+ key
.offset
;
517 ASSERT(offset
>= found_start
&& offset
< found_end
);
519 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
520 i
= div_u64(offset
- found_start
, block_group
->sectorsize
);
521 return !!extent_buffer_test_bit(leaf
, ptr
, i
);
524 static void free_space_set_bits(struct btrfs_block_group_cache
*block_group
,
525 struct btrfs_path
*path
, u64
*start
, u64
*size
,
528 struct extent_buffer
*leaf
;
529 struct btrfs_key key
;
530 u64 end
= *start
+ *size
;
531 u64 found_start
, found_end
;
532 unsigned long ptr
, first
, last
;
534 leaf
= path
->nodes
[0];
535 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
536 ASSERT(key
.type
== BTRFS_FREE_SPACE_BITMAP_KEY
);
538 found_start
= key
.objectid
;
539 found_end
= key
.objectid
+ key
.offset
;
540 ASSERT(*start
>= found_start
&& *start
< found_end
);
541 ASSERT(end
> found_start
);
546 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
547 first
= div_u64(*start
- found_start
, block_group
->sectorsize
);
548 last
= div_u64(end
- found_start
, block_group
->sectorsize
);
550 extent_buffer_bitmap_set(leaf
, ptr
, first
, last
- first
);
552 extent_buffer_bitmap_clear(leaf
, ptr
, first
, last
- first
);
553 btrfs_mark_buffer_dirty(leaf
);
555 *size
-= end
- *start
;
560 * We can't use btrfs_next_item() in modify_free_space_bitmap() because
561 * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
562 * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
565 static int free_space_next_bitmap(struct btrfs_trans_handle
*trans
,
566 struct btrfs_root
*root
, struct btrfs_path
*p
)
568 struct btrfs_key key
;
570 if (p
->slots
[0] + 1 < btrfs_header_nritems(p
->nodes
[0])) {
575 btrfs_item_key_to_cpu(p
->nodes
[0], &key
, p
->slots
[0]);
576 btrfs_release_path(p
);
578 key
.objectid
+= key
.offset
;
580 key
.offset
= (u64
)-1;
582 return btrfs_search_prev_slot(trans
, root
, &key
, p
, 0, 1);
586 * If remove is 1, then we are removing free space, thus clearing bits in the
587 * bitmap. If remove is 0, then we are adding free space, thus setting bits in
590 static int modify_free_space_bitmap(struct btrfs_trans_handle
*trans
,
591 struct btrfs_fs_info
*fs_info
,
592 struct btrfs_block_group_cache
*block_group
,
593 struct btrfs_path
*path
,
594 u64 start
, u64 size
, int remove
)
596 struct btrfs_root
*root
= fs_info
->free_space_root
;
597 struct btrfs_key key
;
598 u64 end
= start
+ size
;
599 u64 cur_start
, cur_size
;
600 int prev_bit
, next_bit
;
605 * Read the bit for the block immediately before the extent of space if
606 * that block is within the block group.
608 if (start
> block_group
->key
.objectid
) {
609 u64 prev_block
= start
- block_group
->sectorsize
;
611 key
.objectid
= prev_block
;
613 key
.offset
= (u64
)-1;
615 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, 0, 1);
619 prev_bit
= free_space_test_bit(block_group
, path
, prev_block
);
621 /* The previous block may have been in the previous bitmap. */
622 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
623 if (start
>= key
.objectid
+ key
.offset
) {
624 ret
= free_space_next_bitmap(trans
, root
, path
);
629 key
.objectid
= start
;
631 key
.offset
= (u64
)-1;
633 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, 0, 1);
641 * Iterate over all of the bitmaps overlapped by the extent of space,
642 * clearing/setting bits as required.
647 free_space_set_bits(block_group
, path
, &cur_start
, &cur_size
,
651 ret
= free_space_next_bitmap(trans
, root
, path
);
657 * Read the bit for the block immediately after the extent of space if
658 * that block is within the block group.
660 if (end
< block_group
->key
.objectid
+ block_group
->key
.offset
) {
661 /* The next block may be in the next bitmap. */
662 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
663 if (end
>= key
.objectid
+ key
.offset
) {
664 ret
= free_space_next_bitmap(trans
, root
, path
);
669 next_bit
= free_space_test_bit(block_group
, path
, end
);
677 /* Leftover on the left. */
681 /* Leftover on the right. */
687 /* Merging with neighbor on the left. */
691 /* Merging with neighbor on the right. */
696 btrfs_release_path(path
);
697 ret
= update_free_space_extent_count(trans
, fs_info
, block_group
, path
,
704 static int remove_free_space_extent(struct btrfs_trans_handle
*trans
,
705 struct btrfs_fs_info
*fs_info
,
706 struct btrfs_block_group_cache
*block_group
,
707 struct btrfs_path
*path
,
710 struct btrfs_root
*root
= fs_info
->free_space_root
;
711 struct btrfs_key key
;
712 u64 found_start
, found_end
;
713 u64 end
= start
+ size
;
714 int new_extents
= -1;
717 key
.objectid
= start
;
719 key
.offset
= (u64
)-1;
721 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, -1, 1);
725 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
727 ASSERT(key
.type
== BTRFS_FREE_SPACE_EXTENT_KEY
);
729 found_start
= key
.objectid
;
730 found_end
= key
.objectid
+ key
.offset
;
731 ASSERT(start
>= found_start
&& end
<= found_end
);
734 * Okay, now that we've found the free space extent which contains the
735 * free space that we are removing, there are four cases:
737 * 1. We're using the whole extent: delete the key we found and
738 * decrement the free space extent count.
739 * 2. We are using part of the extent starting at the beginning: delete
740 * the key we found and insert a new key representing the leftover at
741 * the end. There is no net change in the number of extents.
742 * 3. We are using part of the extent ending at the end: delete the key
743 * we found and insert a new key representing the leftover at the
744 * beginning. There is no net change in the number of extents.
745 * 4. We are using part of the extent in the middle: delete the key we
746 * found and insert two new keys representing the leftovers on each
747 * side. Where we used to have one extent, we now have two, so increment
748 * the extent count. We may need to convert the block group to bitmaps
752 /* Delete the existing key (cases 1-4). */
753 ret
= btrfs_del_item(trans
, root
, path
);
757 /* Add a key for leftovers at the beginning (cases 3 and 4). */
758 if (start
> found_start
) {
759 key
.objectid
= found_start
;
760 key
.type
= BTRFS_FREE_SPACE_EXTENT_KEY
;
761 key
.offset
= start
- found_start
;
763 btrfs_release_path(path
);
764 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, 0);
770 /* Add a key for leftovers at the end (cases 2 and 4). */
771 if (end
< found_end
) {
773 key
.type
= BTRFS_FREE_SPACE_EXTENT_KEY
;
774 key
.offset
= found_end
- end
;
776 btrfs_release_path(path
);
777 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, 0);
783 btrfs_release_path(path
);
784 ret
= update_free_space_extent_count(trans
, fs_info
, block_group
, path
,
791 int __remove_from_free_space_tree(struct btrfs_trans_handle
*trans
,
792 struct btrfs_fs_info
*fs_info
,
793 struct btrfs_block_group_cache
*block_group
,
794 struct btrfs_path
*path
, u64 start
, u64 size
)
796 struct btrfs_free_space_info
*info
;
800 if (block_group
->needs_free_space
) {
801 ret
= __add_block_group_free_space(trans
, fs_info
, block_group
,
807 info
= search_free_space_info(NULL
, fs_info
, block_group
, path
, 0);
809 return PTR_ERR(info
);
810 flags
= btrfs_free_space_flags(path
->nodes
[0], info
);
811 btrfs_release_path(path
);
813 if (flags
& BTRFS_FREE_SPACE_USING_BITMAPS
) {
814 return modify_free_space_bitmap(trans
, fs_info
, block_group
,
815 path
, start
, size
, 1);
817 return remove_free_space_extent(trans
, fs_info
, block_group
,
822 int remove_from_free_space_tree(struct btrfs_trans_handle
*trans
,
823 struct btrfs_fs_info
*fs_info
,
826 struct btrfs_block_group_cache
*block_group
;
827 struct btrfs_path
*path
;
830 if (!btrfs_fs_compat_ro(fs_info
, FREE_SPACE_TREE
))
833 path
= btrfs_alloc_path();
839 block_group
= btrfs_lookup_block_group(fs_info
, start
);
846 mutex_lock(&block_group
->free_space_lock
);
847 ret
= __remove_from_free_space_tree(trans
, fs_info
, block_group
, path
,
849 mutex_unlock(&block_group
->free_space_lock
);
851 btrfs_put_block_group(block_group
);
853 btrfs_free_path(path
);
855 btrfs_abort_transaction(trans
, fs_info
->free_space_root
, ret
);
859 static int add_free_space_extent(struct btrfs_trans_handle
*trans
,
860 struct btrfs_fs_info
*fs_info
,
861 struct btrfs_block_group_cache
*block_group
,
862 struct btrfs_path
*path
,
865 struct btrfs_root
*root
= fs_info
->free_space_root
;
866 struct btrfs_key key
, new_key
;
867 u64 found_start
, found_end
;
868 u64 end
= start
+ size
;
873 * We are adding a new extent of free space, but we need to merge
874 * extents. There are four cases here:
876 * 1. The new extent does not have any immediate neighbors to merge
877 * with: add the new key and increment the free space extent count. We
878 * may need to convert the block group to bitmaps as a result.
879 * 2. The new extent has an immediate neighbor before it: remove the
880 * previous key and insert a new key combining both of them. There is no
881 * net change in the number of extents.
882 * 3. The new extent has an immediate neighbor after it: remove the next
883 * key and insert a new key combining both of them. There is no net
884 * change in the number of extents.
885 * 4. The new extent has immediate neighbors on both sides: remove both
886 * of the keys and insert a new key combining all of them. Where we used
887 * to have two extents, we now have one, so decrement the extent count.
890 new_key
.objectid
= start
;
891 new_key
.type
= BTRFS_FREE_SPACE_EXTENT_KEY
;
892 new_key
.offset
= size
;
894 /* Search for a neighbor on the left. */
895 if (start
== block_group
->key
.objectid
)
897 key
.objectid
= start
- 1;
899 key
.offset
= (u64
)-1;
901 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, -1, 1);
905 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
907 if (key
.type
!= BTRFS_FREE_SPACE_EXTENT_KEY
) {
908 ASSERT(key
.type
== BTRFS_FREE_SPACE_INFO_KEY
);
909 btrfs_release_path(path
);
913 found_start
= key
.objectid
;
914 found_end
= key
.objectid
+ key
.offset
;
915 ASSERT(found_start
>= block_group
->key
.objectid
&&
916 found_end
> block_group
->key
.objectid
);
917 ASSERT(found_start
< start
&& found_end
<= start
);
920 * Delete the neighbor on the left and absorb it into the new key (cases
923 if (found_end
== start
) {
924 ret
= btrfs_del_item(trans
, root
, path
);
927 new_key
.objectid
= found_start
;
928 new_key
.offset
+= key
.offset
;
931 btrfs_release_path(path
);
934 /* Search for a neighbor on the right. */
935 if (end
== block_group
->key
.objectid
+ block_group
->key
.offset
)
939 key
.offset
= (u64
)-1;
941 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, -1, 1);
945 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
947 if (key
.type
!= BTRFS_FREE_SPACE_EXTENT_KEY
) {
948 ASSERT(key
.type
== BTRFS_FREE_SPACE_INFO_KEY
);
949 btrfs_release_path(path
);
953 found_start
= key
.objectid
;
954 found_end
= key
.objectid
+ key
.offset
;
955 ASSERT(found_start
>= block_group
->key
.objectid
&&
956 found_end
> block_group
->key
.objectid
);
957 ASSERT((found_start
< start
&& found_end
<= start
) ||
958 (found_start
>= end
&& found_end
> end
));
961 * Delete the neighbor on the right and absorb it into the new key
964 if (found_start
== end
) {
965 ret
= btrfs_del_item(trans
, root
, path
);
968 new_key
.offset
+= key
.offset
;
971 btrfs_release_path(path
);
974 /* Insert the new key (cases 1-4). */
975 ret
= btrfs_insert_empty_item(trans
, root
, path
, &new_key
, 0);
979 btrfs_release_path(path
);
980 ret
= update_free_space_extent_count(trans
, fs_info
, block_group
, path
,
987 int __add_to_free_space_tree(struct btrfs_trans_handle
*trans
,
988 struct btrfs_fs_info
*fs_info
,
989 struct btrfs_block_group_cache
*block_group
,
990 struct btrfs_path
*path
, u64 start
, u64 size
)
992 struct btrfs_free_space_info
*info
;
996 if (block_group
->needs_free_space
) {
997 ret
= __add_block_group_free_space(trans
, fs_info
, block_group
,
1003 info
= search_free_space_info(NULL
, fs_info
, block_group
, path
, 0);
1005 return PTR_ERR(info
);
1006 flags
= btrfs_free_space_flags(path
->nodes
[0], info
);
1007 btrfs_release_path(path
);
1009 if (flags
& BTRFS_FREE_SPACE_USING_BITMAPS
) {
1010 return modify_free_space_bitmap(trans
, fs_info
, block_group
,
1011 path
, start
, size
, 0);
1013 return add_free_space_extent(trans
, fs_info
, block_group
, path
,
1018 int add_to_free_space_tree(struct btrfs_trans_handle
*trans
,
1019 struct btrfs_fs_info
*fs_info
,
1020 u64 start
, u64 size
)
1022 struct btrfs_block_group_cache
*block_group
;
1023 struct btrfs_path
*path
;
1026 if (!btrfs_fs_compat_ro(fs_info
, FREE_SPACE_TREE
))
1029 path
= btrfs_alloc_path();
1035 block_group
= btrfs_lookup_block_group(fs_info
, start
);
1042 mutex_lock(&block_group
->free_space_lock
);
1043 ret
= __add_to_free_space_tree(trans
, fs_info
, block_group
, path
, start
,
1045 mutex_unlock(&block_group
->free_space_lock
);
1047 btrfs_put_block_group(block_group
);
1049 btrfs_free_path(path
);
1051 btrfs_abort_transaction(trans
, fs_info
->free_space_root
, ret
);
1056 * Populate the free space tree by walking the extent tree. Operations on the
1057 * extent tree that happen as a result of writes to the free space tree will go
1058 * through the normal add/remove hooks.
1060 static int populate_free_space_tree(struct btrfs_trans_handle
*trans
,
1061 struct btrfs_fs_info
*fs_info
,
1062 struct btrfs_block_group_cache
*block_group
)
1064 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
1065 struct btrfs_path
*path
, *path2
;
1066 struct btrfs_key key
;
1070 path
= btrfs_alloc_path();
1075 path2
= btrfs_alloc_path();
1077 btrfs_free_path(path
);
1081 ret
= add_new_free_space_info(trans
, fs_info
, block_group
, path2
);
1085 mutex_lock(&block_group
->free_space_lock
);
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
1094 key
.objectid
= block_group
->key
.objectid
;
1095 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
1098 ret
= btrfs_search_slot_for_read(extent_root
, &key
, path
, 1, 0);
1103 start
= block_group
->key
.objectid
;
1104 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
1106 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
1108 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
||
1109 key
.type
== BTRFS_METADATA_ITEM_KEY
) {
1110 if (key
.objectid
>= end
)
1113 if (start
< key
.objectid
) {
1114 ret
= __add_to_free_space_tree(trans
, fs_info
,
1122 start
= key
.objectid
;
1123 if (key
.type
== BTRFS_METADATA_ITEM_KEY
)
1124 start
+= fs_info
->tree_root
->nodesize
;
1126 start
+= key
.offset
;
1127 } else if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
1128 if (key
.objectid
!= block_group
->key
.objectid
)
1132 ret
= btrfs_next_item(extent_root
, path
);
1139 ret
= __add_to_free_space_tree(trans
, fs_info
, block_group
,
1140 path2
, start
, end
- start
);
1147 mutex_unlock(&block_group
->free_space_lock
);
1149 btrfs_free_path(path2
);
1150 btrfs_free_path(path
);
1154 int btrfs_create_free_space_tree(struct btrfs_fs_info
*fs_info
)
1156 struct btrfs_trans_handle
*trans
;
1157 struct btrfs_root
*tree_root
= fs_info
->tree_root
;
1158 struct btrfs_root
*free_space_root
;
1159 struct btrfs_block_group_cache
*block_group
;
1160 struct rb_node
*node
;
1163 trans
= btrfs_start_transaction(tree_root
, 0);
1165 return PTR_ERR(trans
);
1167 fs_info
->creating_free_space_tree
= 1;
1168 free_space_root
= btrfs_create_tree(trans
, fs_info
,
1169 BTRFS_FREE_SPACE_TREE_OBJECTID
);
1170 if (IS_ERR(free_space_root
)) {
1171 ret
= PTR_ERR(free_space_root
);
1174 fs_info
->free_space_root
= free_space_root
;
1176 node
= rb_first(&fs_info
->block_group_cache_tree
);
1178 block_group
= rb_entry(node
, struct btrfs_block_group_cache
,
1180 ret
= populate_free_space_tree(trans
, fs_info
, block_group
);
1183 node
= rb_next(node
);
1186 btrfs_set_fs_compat_ro(fs_info
, FREE_SPACE_TREE
);
1187 btrfs_sysfs_feature_update(fs_info
,
1188 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE
, FEAT_COMPAT_RO
);
1190 fs_info
->creating_free_space_tree
= 0;
1192 ret
= btrfs_commit_transaction(trans
, tree_root
);
1199 fs_info
->creating_free_space_tree
= 0;
1200 btrfs_abort_transaction(trans
, tree_root
, ret
);
1201 btrfs_end_transaction(trans
, tree_root
);
1205 static int clear_free_space_tree(struct btrfs_trans_handle
*trans
,
1206 struct btrfs_root
*root
)
1208 struct btrfs_path
*path
;
1209 struct btrfs_key key
;
1213 path
= btrfs_alloc_path();
1217 path
->leave_spinning
= 1;
1224 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
1228 nr
= btrfs_header_nritems(path
->nodes
[0]);
1233 ret
= btrfs_del_items(trans
, root
, path
, 0, nr
);
1237 btrfs_release_path(path
);
1242 btrfs_free_path(path
);
1246 int btrfs_clear_free_space_tree(struct btrfs_fs_info
*fs_info
)
1248 struct btrfs_trans_handle
*trans
;
1249 struct btrfs_root
*tree_root
= fs_info
->tree_root
;
1250 struct btrfs_root
*free_space_root
= fs_info
->free_space_root
;
1253 trans
= btrfs_start_transaction(tree_root
, 0);
1255 return PTR_ERR(trans
);
1257 btrfs_clear_fs_compat_ro(fs_info
, FREE_SPACE_TREE
);
1258 btrfs_sysfs_feature_update(fs_info
,
1259 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE
, FEAT_COMPAT_RO
);
1261 fs_info
->free_space_root
= NULL
;
1263 ret
= clear_free_space_tree(trans
, free_space_root
);
1267 ret
= btrfs_del_root(trans
, tree_root
, &free_space_root
->root_key
);
1271 list_del(&free_space_root
->dirty_list
);
1273 btrfs_tree_lock(free_space_root
->node
);
1274 clean_tree_block(trans
, tree_root
->fs_info
, free_space_root
->node
);
1275 btrfs_tree_unlock(free_space_root
->node
);
1276 btrfs_free_tree_block(trans
, free_space_root
, free_space_root
->node
,
1279 free_extent_buffer(free_space_root
->node
);
1280 free_extent_buffer(free_space_root
->commit_root
);
1281 kfree(free_space_root
);
1283 ret
= btrfs_commit_transaction(trans
, tree_root
);
1290 btrfs_abort_transaction(trans
, tree_root
, ret
);
1291 btrfs_end_transaction(trans
, tree_root
);
1295 static int __add_block_group_free_space(struct btrfs_trans_handle
*trans
,
1296 struct btrfs_fs_info
*fs_info
,
1297 struct btrfs_block_group_cache
*block_group
,
1298 struct btrfs_path
*path
)
1303 start
= block_group
->key
.objectid
;
1304 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
1306 block_group
->needs_free_space
= 0;
1308 ret
= add_new_free_space_info(trans
, fs_info
, block_group
, path
);
1312 return __add_to_free_space_tree(trans
, fs_info
, block_group
, path
,
1313 block_group
->key
.objectid
,
1314 block_group
->key
.offset
);
1317 int add_block_group_free_space(struct btrfs_trans_handle
*trans
,
1318 struct btrfs_fs_info
*fs_info
,
1319 struct btrfs_block_group_cache
*block_group
)
1321 struct btrfs_path
*path
= NULL
;
1324 if (!btrfs_fs_compat_ro(fs_info
, FREE_SPACE_TREE
))
1327 mutex_lock(&block_group
->free_space_lock
);
1328 if (!block_group
->needs_free_space
)
1331 path
= btrfs_alloc_path();
1337 ret
= __add_block_group_free_space(trans
, fs_info
, block_group
, path
);
1340 btrfs_free_path(path
);
1341 mutex_unlock(&block_group
->free_space_lock
);
1343 btrfs_abort_transaction(trans
, fs_info
->free_space_root
, ret
);
1347 int remove_block_group_free_space(struct btrfs_trans_handle
*trans
,
1348 struct btrfs_fs_info
*fs_info
,
1349 struct btrfs_block_group_cache
*block_group
)
1351 struct btrfs_root
*root
= fs_info
->free_space_root
;
1352 struct btrfs_path
*path
;
1353 struct btrfs_key key
, found_key
;
1354 struct extent_buffer
*leaf
;
1359 if (!btrfs_fs_compat_ro(fs_info
, FREE_SPACE_TREE
))
1362 if (block_group
->needs_free_space
) {
1363 /* We never added this block group to the free space tree. */
1367 path
= btrfs_alloc_path();
1373 start
= block_group
->key
.objectid
;
1374 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
1376 key
.objectid
= end
- 1;
1378 key
.offset
= (u64
)-1;
1381 ret
= btrfs_search_prev_slot(trans
, root
, &key
, path
, -1, 1);
1385 leaf
= path
->nodes
[0];
1388 while (path
->slots
[0] > 0) {
1389 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0] - 1);
1391 if (found_key
.type
== BTRFS_FREE_SPACE_INFO_KEY
) {
1392 ASSERT(found_key
.objectid
== block_group
->key
.objectid
);
1393 ASSERT(found_key
.offset
== block_group
->key
.offset
);
1398 } else if (found_key
.type
== BTRFS_FREE_SPACE_EXTENT_KEY
||
1399 found_key
.type
== BTRFS_FREE_SPACE_BITMAP_KEY
) {
1400 ASSERT(found_key
.objectid
>= start
);
1401 ASSERT(found_key
.objectid
< end
);
1402 ASSERT(found_key
.objectid
+ found_key
.offset
<= end
);
1410 ret
= btrfs_del_items(trans
, root
, path
, path
->slots
[0], nr
);
1413 btrfs_release_path(path
);
1418 btrfs_free_path(path
);
1420 btrfs_abort_transaction(trans
, root
, ret
);
1424 static int load_free_space_bitmaps(struct btrfs_caching_control
*caching_ctl
,
1425 struct btrfs_path
*path
,
1426 u32 expected_extent_count
)
1428 struct btrfs_block_group_cache
*block_group
;
1429 struct btrfs_fs_info
*fs_info
;
1430 struct btrfs_root
*root
;
1431 struct btrfs_key key
;
1432 int prev_bit
= 0, bit
;
1433 /* Initialize to silence GCC. */
1434 u64 extent_start
= 0;
1436 u64 total_found
= 0;
1437 u32 extent_count
= 0;
1440 block_group
= caching_ctl
->block_group
;
1441 fs_info
= block_group
->fs_info
;
1442 root
= fs_info
->free_space_root
;
1444 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
1447 ret
= btrfs_next_item(root
, path
);
1453 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
1455 if (key
.type
== BTRFS_FREE_SPACE_INFO_KEY
)
1458 ASSERT(key
.type
== BTRFS_FREE_SPACE_BITMAP_KEY
);
1459 ASSERT(key
.objectid
< end
&& key
.objectid
+ key
.offset
<= end
);
1461 caching_ctl
->progress
= key
.objectid
;
1463 offset
= key
.objectid
;
1464 while (offset
< key
.objectid
+ key
.offset
) {
1465 bit
= free_space_test_bit(block_group
, path
, offset
);
1466 if (prev_bit
== 0 && bit
== 1) {
1467 extent_start
= offset
;
1468 } else if (prev_bit
== 1 && bit
== 0) {
1469 total_found
+= add_new_free_space(block_group
,
1473 if (total_found
> CACHING_CTL_WAKE_UP
) {
1475 wake_up(&caching_ctl
->wait
);
1480 offset
+= block_group
->sectorsize
;
1483 if (prev_bit
== 1) {
1484 total_found
+= add_new_free_space(block_group
, fs_info
,
1489 if (extent_count
!= expected_extent_count
) {
1490 btrfs_err(fs_info
, "incorrect extent count for %llu; counted %u, expected %u",
1491 block_group
->key
.objectid
, extent_count
,
1492 expected_extent_count
);
1498 caching_ctl
->progress
= (u64
)-1;
1505 static int load_free_space_extents(struct btrfs_caching_control
*caching_ctl
,
1506 struct btrfs_path
*path
,
1507 u32 expected_extent_count
)
1509 struct btrfs_block_group_cache
*block_group
;
1510 struct btrfs_fs_info
*fs_info
;
1511 struct btrfs_root
*root
;
1512 struct btrfs_key key
;
1514 u64 total_found
= 0;
1515 u32 extent_count
= 0;
1518 block_group
= caching_ctl
->block_group
;
1519 fs_info
= block_group
->fs_info
;
1520 root
= fs_info
->free_space_root
;
1522 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
1525 ret
= btrfs_next_item(root
, path
);
1531 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
1533 if (key
.type
== BTRFS_FREE_SPACE_INFO_KEY
)
1536 ASSERT(key
.type
== BTRFS_FREE_SPACE_EXTENT_KEY
);
1537 ASSERT(key
.objectid
< end
&& key
.objectid
+ key
.offset
<= end
);
1539 caching_ctl
->progress
= key
.objectid
;
1541 total_found
+= add_new_free_space(block_group
, fs_info
,
1543 key
.objectid
+ key
.offset
);
1544 if (total_found
> CACHING_CTL_WAKE_UP
) {
1546 wake_up(&caching_ctl
->wait
);
1551 if (extent_count
!= expected_extent_count
) {
1552 btrfs_err(fs_info
, "incorrect extent count for %llu; counted %u, expected %u",
1553 block_group
->key
.objectid
, extent_count
,
1554 expected_extent_count
);
1560 caching_ctl
->progress
= (u64
)-1;
1567 int load_free_space_tree(struct btrfs_caching_control
*caching_ctl
)
1569 struct btrfs_block_group_cache
*block_group
;
1570 struct btrfs_fs_info
*fs_info
;
1571 struct btrfs_free_space_info
*info
;
1572 struct btrfs_path
*path
;
1573 u32 extent_count
, flags
;
1576 block_group
= caching_ctl
->block_group
;
1577 fs_info
= block_group
->fs_info
;
1579 path
= btrfs_alloc_path();
1584 * Just like caching_thread() doesn't want to deadlock on the extent
1585 * tree, we don't want to deadlock on the free space tree.
1587 path
->skip_locking
= 1;
1588 path
->search_commit_root
= 1;
1591 info
= search_free_space_info(NULL
, fs_info
, block_group
, path
, 0);
1593 ret
= PTR_ERR(info
);
1596 extent_count
= btrfs_free_space_extent_count(path
->nodes
[0], info
);
1597 flags
= btrfs_free_space_flags(path
->nodes
[0], info
);
1600 * We left path pointing to the free space info item, so now
1601 * load_free_space_foo can just iterate through the free space tree from
1604 if (flags
& BTRFS_FREE_SPACE_USING_BITMAPS
)
1605 ret
= load_free_space_bitmaps(caching_ctl
, path
, extent_count
);
1607 ret
= load_free_space_extents(caching_ctl
, path
, extent_count
);
1610 btrfs_free_path(path
);