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