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.
21 #include "free-space-cache.h"
22 #include "free-space-tree.h"
24 static struct btrfs_free_space_info
*
25 search_free_space_info(struct btrfs_trans_handle
*trans
,
26 struct btrfs_fs_info
*fs_info
,
27 struct btrfs_block_group_cache
*block_group
,
28 struct btrfs_path
*path
, int cow
)
30 struct btrfs_root
*root
= fs_info
->free_space_root
;
34 key
.objectid
= block_group
->key
.objectid
;
35 key
.type
= BTRFS_FREE_SPACE_INFO_KEY
;
36 key
.offset
= block_group
->key
.offset
;
38 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, cow
);
42 return ERR_PTR(-ENOENT
);
44 return btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
45 struct btrfs_free_space_info
);
48 static int free_space_test_bit(struct btrfs_block_group_cache
*block_group
,
49 struct btrfs_path
*path
, u64 offset
,
52 struct extent_buffer
*leaf
;
54 u64 found_start
, found_end
;
57 leaf
= path
->nodes
[0];
58 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
59 ASSERT(key
.type
== BTRFS_FREE_SPACE_BITMAP_KEY
);
61 found_start
= key
.objectid
;
62 found_end
= key
.objectid
+ key
.offset
;
63 ASSERT(offset
>= found_start
&& offset
< found_end
);
65 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
66 i
= (offset
- found_start
) / sectorsize
;
67 return !!extent_buffer_test_bit(leaf
, ptr
, i
);
70 static int load_free_space_bitmaps(struct btrfs_fs_info
*fs_info
,
71 struct btrfs_block_group_cache
*block_group
,
72 struct btrfs_path
*path
,
73 u32 expected_extent_count
,
76 struct btrfs_root
*root
= fs_info
->free_space_root
;
78 int prev_bit
= 0, bit
;
80 u64 start
, end
, offset
;
84 start
= block_group
->key
.objectid
;
85 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
88 ret
= btrfs_next_item(root
, path
);
94 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
96 if (key
.type
== BTRFS_FREE_SPACE_INFO_KEY
)
99 if (key
.type
!= BTRFS_FREE_SPACE_BITMAP_KEY
) {
100 fprintf(stderr
, "unexpected key of type %u\n", key
.type
);
104 if (key
.objectid
>= end
) {
106 "free space bitmap starts at %llu, beyond end of block group %llu-%llu\n",
107 key
.objectid
, start
, end
);
111 if (key
.objectid
+ key
.offset
> end
) {
113 "free space bitmap ends at %llu, beyond end of block group %llu-%llu\n",
114 key
.objectid
, start
, end
);
119 offset
= key
.objectid
;
120 while (offset
< key
.objectid
+ key
.offset
) {
121 bit
= free_space_test_bit(block_group
, path
, offset
,
123 if (prev_bit
== 0 && bit
== 1) {
124 extent_start
= offset
;
125 } else if (prev_bit
== 1 && bit
== 0) {
126 add_new_free_space(block_group
, fs_info
, extent_start
, offset
);
130 offset
+= root
->sectorsize
;
135 add_new_free_space(block_group
, fs_info
, extent_start
, end
);
139 if (extent_count
!= expected_extent_count
) {
140 fprintf(stderr
, "free space info recorded %u extents, counted %u\n",
141 expected_extent_count
, extent_count
);
150 static int load_free_space_extents(struct btrfs_fs_info
*fs_info
,
151 struct btrfs_block_group_cache
*block_group
,
152 struct btrfs_path
*path
,
153 u32 expected_extent_count
,
156 struct btrfs_root
*root
= fs_info
->free_space_root
;
157 struct btrfs_key key
, prev_key
;
160 u32 extent_count
= 0;
163 start
= block_group
->key
.objectid
;
164 end
= block_group
->key
.objectid
+ block_group
->key
.offset
;
167 ret
= btrfs_next_item(root
, path
);
173 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
175 if (key
.type
== BTRFS_FREE_SPACE_INFO_KEY
)
178 if (key
.type
!= BTRFS_FREE_SPACE_EXTENT_KEY
) {
179 fprintf(stderr
, "unexpected key of type %u\n", key
.type
);
183 if (key
.objectid
>= end
) {
185 "free space extent starts at %llu, beyond end of block group %llu-%llu\n",
186 key
.objectid
, start
, end
);
190 if (key
.objectid
+ key
.offset
> end
) {
192 "free space extent ends at %llu, beyond end of block group %llu-%llu\n",
193 key
.objectid
, start
, end
);
199 u64 cur_start
= key
.objectid
;
200 u64 cur_end
= cur_start
+ key
.offset
;
201 u64 prev_start
= prev_key
.objectid
;
202 u64 prev_end
= prev_start
+ prev_key
.offset
;
204 if (cur_start
< prev_end
) {
206 "free space extent %llu-%llu overlaps with previous %llu-%llu\n",
208 prev_start
, prev_end
);
210 } else if (cur_start
== prev_end
) {
212 "free space extent %llu-%llu is unmerged with previous %llu-%llu\n",
214 prev_start
, prev_end
);
219 add_new_free_space(block_group
, fs_info
, key
.objectid
, key
.objectid
+ key
.offset
);
226 if (extent_count
!= expected_extent_count
) {
227 fprintf(stderr
, "free space info recorded %u extents, counted %u\n",
228 expected_extent_count
, extent_count
);
237 int load_free_space_tree(struct btrfs_fs_info
*fs_info
,
238 struct btrfs_block_group_cache
*block_group
)
240 struct btrfs_free_space_info
*info
;
241 struct btrfs_path
*path
;
242 u32 extent_count
, flags
;
246 path
= btrfs_alloc_path();
251 info
= search_free_space_info(NULL
, fs_info
, block_group
, path
, 0);
256 extent_count
= btrfs_free_space_extent_count(path
->nodes
[0], info
);
257 flags
= btrfs_free_space_flags(path
->nodes
[0], info
);
259 if (flags
& BTRFS_FREE_SPACE_USING_BITMAPS
) {
260 ret
= load_free_space_bitmaps(fs_info
, block_group
, path
,
261 extent_count
, &errors
);
263 ret
= load_free_space_extents(fs_info
, block_group
, path
,
264 extent_count
, &errors
);
271 btrfs_free_path(path
);
272 return ret
? ret
: errors
;