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 41656756 : static struct btrfs_root *btrfs_free_space_root(
25 : struct btrfs_block_group *block_group)
26 : {
27 41656756 : struct btrfs_key key = {
28 : .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
29 : .type = BTRFS_ROOT_ITEM_KEY,
30 : .offset = 0,
31 : };
32 :
33 41656756 : if (btrfs_fs_incompat(block_group->fs_info, EXTENT_TREE_V2))
34 0 : key.offset = block_group->global_root_id;
35 41656756 : return btrfs_global_root(block_group->fs_info, &key);
36 : }
37 :
38 26407 : void set_free_space_tree_thresholds(struct btrfs_block_group *cache)
39 : {
40 26407 : u32 bitmap_range;
41 26407 : size_t bitmap_size;
42 26407 : u64 num_bitmaps, total_bitmap_size;
43 :
44 26407 : 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 26407 : bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
53 26407 : num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range);
54 26407 : bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
55 26407 : total_bitmap_size = num_bitmaps * bitmap_size;
56 26407 : 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 26407 : if (cache->bitmap_high_thresh > 100)
64 18423 : cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
65 : else
66 7984 : cache->bitmap_low_thresh = 0;
67 26407 : }
68 :
69 1469 : 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 1469 : struct btrfs_root *root = btrfs_free_space_root(block_group);
74 1469 : struct btrfs_free_space_info *info;
75 1469 : struct btrfs_key key;
76 1469 : struct extent_buffer *leaf;
77 1469 : int ret;
78 :
79 1469 : key.objectid = block_group->start;
80 1469 : key.type = BTRFS_FREE_SPACE_INFO_KEY;
81 1469 : key.offset = block_group->length;
82 :
83 1469 : ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
84 1469 : if (ret)
85 0 : goto out;
86 :
87 1469 : leaf = path->nodes[0];
88 1469 : info = btrfs_item_ptr(leaf, path->slots[0],
89 : struct btrfs_free_space_info);
90 1469 : btrfs_set_free_space_extent_count(leaf, info, 0);
91 1469 : btrfs_set_free_space_flags(leaf, info, 0);
92 1469 : btrfs_mark_buffer_dirty(leaf);
93 :
94 1469 : ret = 0;
95 1469 : out:
96 1469 : btrfs_release_path(path);
97 1469 : return ret;
98 : }
99 :
100 : EXPORT_FOR_TESTS
101 23519907 : 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 23519907 : struct btrfs_fs_info *fs_info = block_group->fs_info;
107 23519907 : struct btrfs_root *root = btrfs_free_space_root(block_group);
108 23519908 : struct btrfs_key key;
109 23519908 : int ret;
110 :
111 23519908 : key.objectid = block_group->start;
112 23519908 : key.type = BTRFS_FREE_SPACE_INFO_KEY;
113 23519908 : key.offset = block_group->length;
114 :
115 23519908 : ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
116 23519908 : if (ret < 0)
117 0 : return ERR_PTR(ret);
118 23519908 : 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 23519908 : 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 21471508 : 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 21471508 : int ret;
139 :
140 21471508 : ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
141 21471508 : if (ret < 0)
142 : return ret;
143 :
144 21471508 : if (ret == 0) {
145 : ASSERT(0);
146 : return -EIO;
147 : }
148 :
149 21471508 : if (p->slots[0] == 0) {
150 : ASSERT(0);
151 : return -EIO;
152 : }
153 21471508 : p->slots[0]--;
154 :
155 21471508 : return 0;
156 : }
157 :
158 : static inline u32 free_space_bitmap_size(const struct btrfs_fs_info *fs_info,
159 : u64 size)
160 : {
161 40017 : return DIV_ROUND_UP(size >> fs_info->sectorsize_bits, BITS_PER_BYTE);
162 : }
163 :
164 1182 : static unsigned long *alloc_bitmap(u32 bitmap_size)
165 : {
166 1182 : unsigned long *ret;
167 1182 : unsigned int nofs_flag;
168 1182 : 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 1182 : nofs_flag = memalloc_nofs_save();
179 1182 : ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL);
180 1182 : memalloc_nofs_restore(nofs_flag);
181 1182 : return ret;
182 : }
183 :
184 60468 : static void le_bitmap_set(unsigned long *map, unsigned int start, int len)
185 : {
186 60468 : u8 *p = ((u8 *)map) + BIT_BYTE(start);
187 60468 : const unsigned int size = start + len;
188 60468 : int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE);
189 60468 : u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start);
190 :
191 678930 : while (len - bits_to_set >= 0) {
192 618462 : *p |= mask_to_set;
193 618462 : len -= bits_to_set;
194 618462 : bits_to_set = BITS_PER_BYTE;
195 618462 : mask_to_set = ~0;
196 618462 : p++;
197 : }
198 60468 : if (len) {
199 36353 : mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
200 36353 : *p |= mask_to_set;
201 : }
202 60468 : }
203 :
204 : EXPORT_FOR_TESTS
205 165 : 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 165 : struct btrfs_fs_info *fs_info = trans->fs_info;
210 165 : struct btrfs_root *root = btrfs_free_space_root(block_group);
211 165 : struct btrfs_free_space_info *info;
212 165 : struct btrfs_key key, found_key;
213 165 : struct extent_buffer *leaf;
214 165 : unsigned long *bitmap;
215 165 : char *bitmap_cursor;
216 165 : u64 start, end;
217 165 : u64 bitmap_range, i;
218 165 : u32 bitmap_size, flags, expected_extent_count;
219 165 : u32 extent_count = 0;
220 165 : int done = 0, nr;
221 165 : int ret;
222 :
223 165 : bitmap_size = free_space_bitmap_size(fs_info, block_group->length);
224 165 : bitmap = alloc_bitmap(bitmap_size);
225 165 : if (!bitmap) {
226 0 : ret = -ENOMEM;
227 0 : goto out;
228 : }
229 :
230 165 : start = block_group->start;
231 165 : end = block_group->start + block_group->length;
232 :
233 165 : key.objectid = end - 1;
234 165 : key.type = (u8)-1;
235 165 : key.offset = (u64)-1;
236 :
237 389 : while (!done) {
238 224 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
239 224 : if (ret)
240 0 : goto out;
241 :
242 224 : leaf = path->nodes[0];
243 224 : nr = 0;
244 224 : path->slots[0]++;
245 224 : while (path->slots[0] > 0) {
246 60633 : btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
247 :
248 60633 : if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
249 165 : ASSERT(found_key.objectid == block_group->start);
250 165 : ASSERT(found_key.offset == block_group->length);
251 165 : done = 1;
252 165 : break;
253 60468 : } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
254 60468 : u64 first, last;
255 :
256 60468 : ASSERT(found_key.objectid >= start);
257 60468 : ASSERT(found_key.objectid < end);
258 60468 : ASSERT(found_key.objectid + found_key.offset <= end);
259 :
260 60468 : first = div_u64(found_key.objectid - start,
261 : fs_info->sectorsize);
262 60468 : last = div_u64(found_key.objectid + found_key.offset - start,
263 : fs_info->sectorsize);
264 60468 : le_bitmap_set(bitmap, first, last - first);
265 :
266 60468 : extent_count++;
267 60468 : nr++;
268 60468 : path->slots[0]--;
269 : } else {
270 60692 : ASSERT(0);
271 : }
272 : }
273 :
274 224 : ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
275 224 : if (ret)
276 0 : goto out;
277 224 : btrfs_release_path(path);
278 : }
279 :
280 165 : info = search_free_space_info(trans, block_group, path, 1);
281 165 : if (IS_ERR(info)) {
282 0 : ret = PTR_ERR(info);
283 0 : goto out;
284 : }
285 165 : leaf = path->nodes[0];
286 165 : flags = btrfs_free_space_flags(leaf, info);
287 165 : flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
288 165 : btrfs_set_free_space_flags(leaf, info, flags);
289 165 : expected_extent_count = btrfs_free_space_extent_count(leaf, info);
290 165 : btrfs_mark_buffer_dirty(leaf);
291 165 : btrfs_release_path(path);
292 :
293 165 : 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 165 : bitmap_cursor = (char *)bitmap;
304 165 : bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
305 165 : i = start;
306 5540 : while (i < end) {
307 5375 : unsigned long ptr;
308 5375 : u64 extent_size;
309 5375 : u32 data_size;
310 :
311 5375 : extent_size = min(end - i, bitmap_range);
312 5375 : data_size = free_space_bitmap_size(fs_info, extent_size);
313 :
314 5375 : key.objectid = i;
315 5375 : key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
316 5375 : key.offset = extent_size;
317 :
318 5375 : ret = btrfs_insert_empty_item(trans, root, path, &key,
319 : data_size);
320 5375 : if (ret)
321 0 : goto out;
322 :
323 5375 : leaf = path->nodes[0];
324 5375 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
325 5375 : write_extent_buffer(leaf, bitmap_cursor, ptr,
326 : data_size);
327 5375 : btrfs_mark_buffer_dirty(leaf);
328 5375 : btrfs_release_path(path);
329 :
330 5375 : i += extent_size;
331 5375 : bitmap_cursor += data_size;
332 : }
333 :
334 : ret = 0;
335 165 : out:
336 165 : kvfree(bitmap);
337 165 : if (ret)
338 0 : btrfs_abort_transaction(trans, ret);
339 165 : return ret;
340 : }
341 :
342 : EXPORT_FOR_TESTS
343 1017 : 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 1017 : struct btrfs_fs_info *fs_info = trans->fs_info;
348 1017 : struct btrfs_root *root = btrfs_free_space_root(block_group);
349 1017 : struct btrfs_free_space_info *info;
350 1017 : struct btrfs_key key, found_key;
351 1017 : struct extent_buffer *leaf;
352 1017 : unsigned long *bitmap;
353 1017 : u64 start, end;
354 1017 : u32 bitmap_size, flags, expected_extent_count;
355 1017 : unsigned long nrbits, start_bit, end_bit;
356 1017 : u32 extent_count = 0;
357 1017 : int done = 0, nr;
358 1017 : int ret;
359 :
360 1017 : bitmap_size = free_space_bitmap_size(fs_info, block_group->length);
361 1017 : bitmap = alloc_bitmap(bitmap_size);
362 1017 : if (!bitmap) {
363 0 : ret = -ENOMEM;
364 0 : goto out;
365 : }
366 :
367 1017 : start = block_group->start;
368 1017 : end = block_group->start + block_group->length;
369 :
370 1017 : key.objectid = end - 1;
371 1017 : key.type = (u8)-1;
372 1017 : key.offset = (u64)-1;
373 :
374 2062 : while (!done) {
375 1045 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
376 1045 : if (ret)
377 0 : goto out;
378 :
379 1045 : leaf = path->nodes[0];
380 1045 : nr = 0;
381 1045 : path->slots[0]++;
382 1045 : while (path->slots[0] > 0) {
383 34477 : btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
384 :
385 34477 : if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
386 1017 : ASSERT(found_key.objectid == block_group->start);
387 1017 : ASSERT(found_key.offset == block_group->length);
388 1017 : done = 1;
389 1017 : break;
390 33460 : } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
391 33460 : unsigned long ptr;
392 33460 : char *bitmap_cursor;
393 33460 : u32 bitmap_pos, data_size;
394 :
395 33460 : ASSERT(found_key.objectid >= start);
396 33460 : ASSERT(found_key.objectid < end);
397 33460 : ASSERT(found_key.objectid + found_key.offset <= end);
398 :
399 33460 : bitmap_pos = div_u64(found_key.objectid - start,
400 33460 : fs_info->sectorsize *
401 : BITS_PER_BYTE);
402 33460 : bitmap_cursor = ((char *)bitmap) + bitmap_pos;
403 33460 : data_size = free_space_bitmap_size(fs_info,
404 : found_key.offset);
405 :
406 33460 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
407 33460 : read_extent_buffer(leaf, bitmap_cursor, ptr,
408 : data_size);
409 :
410 33460 : nr++;
411 33460 : path->slots[0]--;
412 : } else {
413 34505 : ASSERT(0);
414 : }
415 : }
416 :
417 1045 : ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
418 1045 : if (ret)
419 0 : goto out;
420 1045 : btrfs_release_path(path);
421 : }
422 :
423 1017 : info = search_free_space_info(trans, block_group, path, 1);
424 1017 : if (IS_ERR(info)) {
425 0 : ret = PTR_ERR(info);
426 0 : goto out;
427 : }
428 1017 : leaf = path->nodes[0];
429 1017 : flags = btrfs_free_space_flags(leaf, info);
430 1017 : flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
431 1017 : btrfs_set_free_space_flags(leaf, info, flags);
432 1017 : expected_extent_count = btrfs_free_space_extent_count(leaf, info);
433 1017 : btrfs_mark_buffer_dirty(leaf);
434 1017 : btrfs_release_path(path);
435 :
436 1017 : nrbits = block_group->length >> block_group->fs_info->sectorsize_bits;
437 1017 : start_bit = find_next_bit_le(bitmap, nrbits, 0);
438 :
439 42412 : while (start_bit < nrbits) {
440 41395 : end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit);
441 41395 : ASSERT(start_bit < end_bit);
442 :
443 41395 : key.objectid = start + start_bit * block_group->fs_info->sectorsize;
444 41395 : key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
445 41395 : key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize;
446 :
447 41395 : ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
448 41395 : if (ret)
449 0 : goto out;
450 41395 : btrfs_release_path(path);
451 :
452 41395 : extent_count++;
453 :
454 41395 : start_bit = find_next_bit_le(bitmap, nrbits, end_bit);
455 : }
456 :
457 1017 : 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 1017 : out:
469 1017 : kvfree(bitmap);
470 1017 : if (ret)
471 0 : btrfs_abort_transaction(trans, ret);
472 1017 : return ret;
473 : }
474 :
475 18127543 : 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 18127543 : struct btrfs_free_space_info *info;
481 18127543 : u32 flags;
482 18127543 : u32 extent_count;
483 18127543 : int ret = 0;
484 :
485 18127543 : if (new_extents == 0)
486 : return 0;
487 :
488 5385058 : info = search_free_space_info(trans, block_group, path, 1);
489 5385057 : if (IS_ERR(info)) {
490 0 : ret = PTR_ERR(info);
491 0 : goto out;
492 : }
493 5385057 : flags = btrfs_free_space_flags(path->nodes[0], info);
494 5385057 : extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
495 :
496 5385057 : extent_count += new_extents;
497 5385057 : btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
498 5385058 : btrfs_mark_buffer_dirty(path->nodes[0]);
499 5385058 : btrfs_release_path(path);
500 :
501 5385058 : if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
502 848710 : extent_count > block_group->bitmap_high_thresh) {
503 165 : ret = convert_free_space_to_bitmaps(trans, block_group, path);
504 5384893 : } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
505 4536348 : extent_count < block_group->bitmap_low_thresh) {
506 1017 : ret = convert_free_space_to_extents(trans, block_group, path);
507 : }
508 :
509 5383876 : out:
510 : return ret;
511 : }
512 :
513 : EXPORT_FOR_TESTS
514 86121666 : int free_space_test_bit(struct btrfs_block_group *block_group,
515 : struct btrfs_path *path, u64 offset)
516 : {
517 86121666 : struct extent_buffer *leaf;
518 86121666 : struct btrfs_key key;
519 86121666 : u64 found_start, found_end;
520 86121666 : unsigned long ptr, i;
521 :
522 86121666 : leaf = path->nodes[0];
523 86121666 : btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
524 86121645 : ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
525 :
526 86121645 : found_start = key.objectid;
527 86121645 : found_end = key.objectid + key.offset;
528 86121645 : ASSERT(offset >= found_start && offset < found_end);
529 :
530 86121645 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
531 86121655 : i = div_u64(offset - found_start,
532 86121655 : block_group->fs_info->sectorsize);
533 86121655 : return !!extent_buffer_test_bit(leaf, ptr, i);
534 : }
535 :
536 10325746 : 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 10325746 : struct btrfs_fs_info *fs_info = block_group->fs_info;
541 10325746 : struct extent_buffer *leaf;
542 10325746 : struct btrfs_key key;
543 10325746 : u64 end = *start + *size;
544 10325746 : u64 found_start, found_end;
545 10325746 : unsigned long ptr, first, last;
546 :
547 10325746 : leaf = path->nodes[0];
548 10325746 : btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
549 10325745 : ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
550 :
551 10325745 : found_start = key.objectid;
552 10325745 : found_end = key.objectid + key.offset;
553 10325745 : ASSERT(*start >= found_start && *start < found_end);
554 10325745 : ASSERT(end > found_start);
555 :
556 10325745 : if (end > found_end)
557 : end = found_end;
558 :
559 10325745 : ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
560 10325745 : first = (*start - found_start) >> fs_info->sectorsize_bits;
561 10325745 : last = (end - found_start) >> fs_info->sectorsize_bits;
562 10325745 : if (bit)
563 5062098 : extent_buffer_bitmap_set(leaf, ptr, first, last - first);
564 : else
565 5263647 : extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
566 10325746 : btrfs_mark_buffer_dirty(leaf);
567 :
568 10325746 : *size -= end - *start;
569 10325746 : *start = end;
570 10325746 : }
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 32235 : static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
579 : struct btrfs_root *root, struct btrfs_path *p)
580 : {
581 32235 : struct btrfs_key key;
582 :
583 32235 : if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
584 32009 : p->slots[0]++;
585 32009 : return 0;
586 : }
587 :
588 226 : btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
589 226 : btrfs_release_path(p);
590 :
591 226 : key.objectid += key.offset;
592 226 : key.type = (u8)-1;
593 226 : key.offset = (u64)-1;
594 :
595 226 : 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 10324777 : 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 10324777 : struct btrfs_root *root = btrfs_free_space_root(block_group);
609 10324777 : struct btrfs_key key;
610 10324777 : u64 end = start + size;
611 10324777 : u64 cur_start, cur_size;
612 10324777 : int prev_bit, next_bit;
613 10324777 : int new_extents;
614 10324777 : 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 10324777 : if (start > block_group->start) {
621 10321040 : u64 prev_block = start - block_group->fs_info->sectorsize;
622 :
623 10321040 : key.objectid = prev_block;
624 10321040 : key.type = (u8)-1;
625 10321040 : key.offset = (u64)-1;
626 :
627 10321040 : ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
628 10321039 : if (ret)
629 0 : goto out;
630 :
631 10321039 : prev_bit = free_space_test_bit(block_group, path, prev_block);
632 :
633 : /* The previous block may have been in the previous bitmap. */
634 10321040 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
635 10321040 : if (start >= key.objectid + key.offset) {
636 15254 : ret = free_space_next_bitmap(trans, root, path);
637 15254 : if (ret)
638 0 : goto out;
639 : }
640 : } else {
641 3737 : key.objectid = start;
642 3737 : key.type = (u8)-1;
643 3737 : key.offset = (u64)-1;
644 :
645 3737 : ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
646 3737 : 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 10324777 : cur_start = start;
657 10324777 : cur_size = size;
658 10325746 : while (1) {
659 10325746 : free_space_set_bits(block_group, path, &cur_start, &cur_size,
660 : !remove);
661 10325746 : if (cur_size == 0)
662 : break;
663 969 : ret = free_space_next_bitmap(trans, root, path);
664 969 : 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 10324777 : if (end < block_group->start + block_group->length) {
673 : /* The next block may be in the next bitmap. */
674 10322268 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
675 10322268 : if (end >= key.objectid + key.offset) {
676 16012 : ret = free_space_next_bitmap(trans, root, path);
677 16012 : if (ret)
678 0 : goto out;
679 : }
680 :
681 10322268 : next_bit = free_space_test_bit(block_group, path, end);
682 : } else {
683 : next_bit = -1;
684 : }
685 :
686 10324777 : if (remove) {
687 5263139 : new_extents = -1;
688 5263139 : if (prev_bit == 1) {
689 : /* Leftover on the left. */
690 276182 : new_extents++;
691 : }
692 5263139 : if (next_bit == 1) {
693 : /* Leftover on the right. */
694 3734141 : new_extents++;
695 : }
696 : } else {
697 5061638 : new_extents = 1;
698 5061638 : if (prev_bit == 1) {
699 : /* Merging with neighbor on the left. */
700 2549585 : new_extents--;
701 : }
702 5061638 : if (next_bit == 1) {
703 : /* Merging with neighbor on the right. */
704 1224571 : new_extents--;
705 : }
706 : }
707 :
708 10324777 : btrfs_release_path(path);
709 10324777 : ret = update_free_space_extent_count(trans, block_group, path,
710 : new_extents);
711 :
712 10324776 : out:
713 10324776 : return ret;
714 : }
715 :
716 4455172 : 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 4455172 : struct btrfs_root *root = btrfs_free_space_root(block_group);
722 4455172 : struct btrfs_key key;
723 4455172 : u64 found_start, found_end;
724 4455172 : u64 end = start + size;
725 4455172 : int new_extents = -1;
726 4455172 : int ret;
727 :
728 4455172 : key.objectid = start;
729 4455172 : key.type = (u8)-1;
730 4455172 : key.offset = (u64)-1;
731 :
732 4455172 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
733 4455172 : if (ret)
734 0 : goto out;
735 :
736 4455172 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
737 :
738 4455172 : ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
739 :
740 4455172 : found_start = key.objectid;
741 4455172 : found_end = key.objectid + key.offset;
742 4455172 : 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 4455172 : ret = btrfs_del_item(trans, root, path);
765 4455172 : if (ret)
766 0 : goto out;
767 :
768 : /* Add a key for leftovers at the beginning (cases 3 and 4). */
769 4455172 : if (start > found_start) {
770 196386 : key.objectid = found_start;
771 196386 : key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
772 196386 : key.offset = start - found_start;
773 :
774 196386 : btrfs_release_path(path);
775 196386 : ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
776 196386 : 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 4455172 : if (end < found_end) {
783 4363027 : key.objectid = end;
784 4363027 : key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
785 4363027 : key.offset = found_end - end;
786 :
787 4363027 : btrfs_release_path(path);
788 4363027 : ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
789 4363027 : if (ret)
790 0 : goto out;
791 4363027 : new_extents++;
792 : }
793 :
794 4455172 : btrfs_release_path(path);
795 4455172 : ret = update_free_space_extent_count(trans, block_group, path,
796 : new_extents);
797 :
798 4455172 : out:
799 4455172 : return ret;
800 : }
801 :
802 : EXPORT_FOR_TESTS
803 9718311 : 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 9718311 : struct btrfs_free_space_info *info;
808 9718311 : u32 flags;
809 9718311 : int ret;
810 :
811 19436622 : if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) {
812 2 : ret = __add_block_group_free_space(trans, block_group, path);
813 2 : if (ret)
814 : return ret;
815 : }
816 :
817 9718311 : info = search_free_space_info(NULL, block_group, path, 0);
818 9718310 : if (IS_ERR(info))
819 0 : return PTR_ERR(info);
820 9718310 : flags = btrfs_free_space_flags(path->nodes[0], info);
821 9718310 : btrfs_release_path(path);
822 :
823 9718311 : if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
824 5263139 : return modify_free_space_bitmap(trans, block_group, path,
825 : start, size, 1);
826 : } else {
827 4455172 : return remove_free_space_extent(trans, block_group, path,
828 : start, size);
829 : }
830 : }
831 :
832 9718644 : int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
833 : u64 start, u64 size)
834 : {
835 9718644 : struct btrfs_block_group *block_group;
836 9718644 : struct btrfs_path *path;
837 9718644 : int ret;
838 :
839 9718644 : if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
840 : return 0;
841 :
842 9718310 : path = btrfs_alloc_path();
843 9718310 : if (!path) {
844 0 : ret = -ENOMEM;
845 0 : goto out;
846 : }
847 :
848 9718310 : block_group = btrfs_lookup_block_group(trans->fs_info, start);
849 9718308 : if (!block_group) {
850 0 : ASSERT(0);
851 0 : ret = -ENOENT;
852 0 : goto out;
853 : }
854 :
855 9718308 : mutex_lock(&block_group->free_space_lock);
856 9718311 : ret = __remove_from_free_space_tree(trans, block_group, path, start,
857 : size);
858 9718311 : mutex_unlock(&block_group->free_space_lock);
859 :
860 9718311 : btrfs_put_block_group(block_group);
861 9718311 : out:
862 9718311 : btrfs_free_path(path);
863 9718310 : if (ret)
864 0 : btrfs_abort_transaction(trans, ret);
865 : return ret;
866 : }
867 :
868 3347594 : 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 3347594 : struct btrfs_root *root = btrfs_free_space_root(block_group);
874 3347594 : struct btrfs_key key, new_key;
875 3347594 : u64 found_start, found_end;
876 3347594 : u64 end = start + size;
877 3347594 : int new_extents = 1;
878 3347594 : 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 3347594 : new_key.objectid = start;
899 3347594 : new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
900 3347594 : new_key.offset = size;
901 :
902 : /* Search for a neighbor on the left. */
903 3347594 : if (start == block_group->start)
904 3707 : goto right;
905 3343887 : key.objectid = start - 1;
906 3343887 : key.type = (u8)-1;
907 3343887 : key.offset = (u64)-1;
908 :
909 3343887 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
910 3343887 : if (ret)
911 0 : goto out;
912 :
913 3343887 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
914 :
915 3343887 : if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
916 5380 : ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
917 5380 : btrfs_release_path(path);
918 5380 : goto right;
919 : }
920 :
921 3338507 : found_start = key.objectid;
922 3338507 : found_end = key.objectid + key.offset;
923 3338507 : ASSERT(found_start >= block_group->start &&
924 : found_end > block_group->start);
925 3338507 : 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 3338507 : if (found_end == start) {
932 3060042 : ret = btrfs_del_item(trans, root, path);
933 3060042 : if (ret)
934 0 : goto out;
935 3060042 : new_key.objectid = found_start;
936 3060042 : new_key.offset += key.offset;
937 3060042 : new_extents--;
938 : }
939 3338507 : btrfs_release_path(path);
940 :
941 3347594 : right:
942 : /* Search for a neighbor on the right. */
943 3347594 : if (end == block_group->start + block_group->length)
944 1948 : goto insert;
945 3345646 : key.objectid = end;
946 3345646 : key.type = (u8)-1;
947 3345646 : key.offset = (u64)-1;
948 :
949 3345646 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
950 3345646 : if (ret)
951 0 : goto out;
952 :
953 3345646 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
954 :
955 3345646 : if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
956 1914160 : ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
957 1914160 : btrfs_release_path(path);
958 1914160 : goto insert;
959 : }
960 :
961 1431486 : found_start = key.objectid;
962 1431486 : found_end = key.objectid + key.offset;
963 1431486 : ASSERT(found_start >= block_group->start &&
964 : found_end > block_group->start);
965 1431486 : 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 1431486 : if (found_start == end) {
973 352699 : ret = btrfs_del_item(trans, root, path);
974 352699 : if (ret)
975 0 : goto out;
976 352699 : new_key.offset += key.offset;
977 352699 : new_extents--;
978 : }
979 1431486 : btrfs_release_path(path);
980 :
981 3347594 : insert:
982 : /* Insert the new key (cases 1-4). */
983 3347594 : ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
984 3347594 : if (ret)
985 0 : goto out;
986 :
987 3347594 : btrfs_release_path(path);
988 3347594 : ret = update_free_space_extent_count(trans, block_group, path,
989 : new_extents);
990 :
991 3347594 : out:
992 3347594 : return ret;
993 : }
994 :
995 : EXPORT_FOR_TESTS
996 8409231 : 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 8409231 : struct btrfs_free_space_info *info;
1001 8409231 : u32 flags;
1002 8409231 : int ret;
1003 :
1004 16818462 : 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 8409231 : info = search_free_space_info(NULL, block_group, path, 0);
1011 8409232 : if (IS_ERR(info))
1012 0 : return PTR_ERR(info);
1013 8409232 : flags = btrfs_free_space_flags(path->nodes[0], info);
1014 8409232 : btrfs_release_path(path);
1015 :
1016 8409232 : if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
1017 5061638 : return modify_free_space_bitmap(trans, block_group, path,
1018 : start, size, 0);
1019 : } else {
1020 3347594 : return add_free_space_extent(trans, block_group, path, start,
1021 : size);
1022 : }
1023 : }
1024 :
1025 8407825 : int add_to_free_space_tree(struct btrfs_trans_handle *trans,
1026 : u64 start, u64 size)
1027 : {
1028 8407825 : struct btrfs_block_group *block_group;
1029 8407825 : struct btrfs_path *path;
1030 8407825 : int ret;
1031 :
1032 8407825 : if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
1033 : return 0;
1034 :
1035 8407711 : path = btrfs_alloc_path();
1036 8407711 : if (!path) {
1037 0 : ret = -ENOMEM;
1038 0 : goto out;
1039 : }
1040 :
1041 8407711 : block_group = btrfs_lookup_block_group(trans->fs_info, start);
1042 8407709 : if (!block_group) {
1043 0 : ASSERT(0);
1044 0 : ret = -ENOENT;
1045 0 : goto out;
1046 : }
1047 :
1048 8407709 : mutex_lock(&block_group->free_space_lock);
1049 8407711 : ret = __add_to_free_space_tree(trans, block_group, path, start, size);
1050 8407711 : mutex_unlock(&block_group->free_space_lock);
1051 :
1052 8407711 : btrfs_put_block_group(block_group);
1053 8407711 : out:
1054 8407711 : btrfs_free_path(path);
1055 8407711 : if (ret)
1056 0 : btrfs_abort_transaction(trans, ret);
1057 : return ret;
1058 : }
1059 :
1060 : /*
1061 : * Populate the free space tree by walking the extent tree. Operations on the
1062 : * extent tree that happen as a result of writes to the free space tree will go
1063 : * through the normal add/remove hooks.
1064 : */
1065 33 : static int populate_free_space_tree(struct btrfs_trans_handle *trans,
1066 : struct btrfs_block_group *block_group)
1067 : {
1068 33 : struct btrfs_root *extent_root;
1069 33 : struct btrfs_path *path, *path2;
1070 33 : struct btrfs_key key;
1071 33 : u64 start, end;
1072 33 : int ret;
1073 :
1074 33 : path = btrfs_alloc_path();
1075 33 : if (!path)
1076 : return -ENOMEM;
1077 33 : path->reada = READA_FORWARD;
1078 :
1079 33 : path2 = btrfs_alloc_path();
1080 33 : if (!path2) {
1081 0 : btrfs_free_path(path);
1082 0 : return -ENOMEM;
1083 : }
1084 :
1085 33 : ret = add_new_free_space_info(trans, block_group, path2);
1086 33 : if (ret)
1087 0 : goto out;
1088 :
1089 33 : mutex_lock(&block_group->free_space_lock);
1090 :
1091 : /*
1092 : * Iterate through all of the extent and metadata items in this block
1093 : * group, adding the free space between them and the free space at the
1094 : * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
1095 : * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
1096 : * contained in.
1097 : */
1098 33 : key.objectid = block_group->start;
1099 33 : key.type = BTRFS_EXTENT_ITEM_KEY;
1100 33 : key.offset = 0;
1101 :
1102 33 : extent_root = btrfs_extent_root(trans->fs_info, key.objectid);
1103 33 : ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
1104 33 : if (ret < 0)
1105 0 : goto out_locked;
1106 33 : ASSERT(ret == 0);
1107 :
1108 33 : start = block_group->start;
1109 33 : end = block_group->start + block_group->length;
1110 155 : while (1) {
1111 155 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1112 :
1113 155 : if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1114 : key.type == BTRFS_METADATA_ITEM_KEY) {
1115 103 : if (key.objectid >= end)
1116 : break;
1117 :
1118 100 : if (start < key.objectid) {
1119 52 : ret = __add_to_free_space_tree(trans,
1120 : block_group,
1121 : path2, start,
1122 : key.objectid -
1123 : start);
1124 52 : if (ret)
1125 0 : goto out_locked;
1126 : }
1127 100 : start = key.objectid;
1128 100 : if (key.type == BTRFS_METADATA_ITEM_KEY)
1129 98 : start += trans->fs_info->nodesize;
1130 : else
1131 2 : start += key.offset;
1132 52 : } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1133 52 : if (key.objectid != block_group->start)
1134 : break;
1135 : }
1136 :
1137 133 : ret = btrfs_next_item(extent_root, path);
1138 133 : if (ret < 0)
1139 0 : goto out_locked;
1140 133 : if (ret)
1141 : break;
1142 : }
1143 33 : if (start < end) {
1144 33 : ret = __add_to_free_space_tree(trans, block_group, path2,
1145 : start, end - start);
1146 33 : if (ret)
1147 0 : goto out_locked;
1148 : }
1149 :
1150 : ret = 0;
1151 33 : out_locked:
1152 33 : mutex_unlock(&block_group->free_space_lock);
1153 33 : out:
1154 33 : btrfs_free_path(path2);
1155 33 : btrfs_free_path(path);
1156 33 : return ret;
1157 : }
1158 :
1159 2 : int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
1160 : {
1161 2 : struct btrfs_trans_handle *trans;
1162 2 : struct btrfs_root *tree_root = fs_info->tree_root;
1163 2 : struct btrfs_root *free_space_root;
1164 2 : struct btrfs_block_group *block_group;
1165 2 : struct rb_node *node;
1166 2 : int ret;
1167 :
1168 2 : trans = btrfs_start_transaction(tree_root, 0);
1169 2 : if (IS_ERR(trans))
1170 0 : return PTR_ERR(trans);
1171 :
1172 2 : set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1173 2 : set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1174 2 : free_space_root = btrfs_create_tree(trans,
1175 : BTRFS_FREE_SPACE_TREE_OBJECTID);
1176 2 : if (IS_ERR(free_space_root)) {
1177 0 : ret = PTR_ERR(free_space_root);
1178 0 : goto abort;
1179 : }
1180 2 : ret = btrfs_global_root_insert(free_space_root);
1181 2 : if (ret) {
1182 0 : btrfs_put_root(free_space_root);
1183 0 : goto abort;
1184 : }
1185 :
1186 2 : node = rb_first_cached(&fs_info->block_group_cache_tree);
1187 8 : while (node) {
1188 6 : block_group = rb_entry(node, struct btrfs_block_group,
1189 : cache_node);
1190 6 : ret = populate_free_space_tree(trans, block_group);
1191 6 : if (ret)
1192 0 : goto abort;
1193 6 : node = rb_next(node);
1194 : }
1195 :
1196 2 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1197 2 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1198 2 : clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1199 2 : ret = btrfs_commit_transaction(trans);
1200 :
1201 : /*
1202 : * Now that we've committed the transaction any reading of our commit
1203 : * root will be safe, so we can cache from the free space tree now.
1204 : */
1205 2 : clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1206 2 : return ret;
1207 :
1208 0 : abort:
1209 0 : clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1210 0 : clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1211 0 : btrfs_abort_transaction(trans, ret);
1212 0 : btrfs_end_transaction(trans);
1213 0 : return ret;
1214 : }
1215 :
1216 14 : static int clear_free_space_tree(struct btrfs_trans_handle *trans,
1217 : struct btrfs_root *root)
1218 : {
1219 14 : struct btrfs_path *path;
1220 14 : struct btrfs_key key;
1221 14 : int nr;
1222 14 : int ret;
1223 :
1224 14 : path = btrfs_alloc_path();
1225 14 : if (!path)
1226 : return -ENOMEM;
1227 :
1228 14 : key.objectid = 0;
1229 14 : key.type = 0;
1230 14 : key.offset = 0;
1231 :
1232 42 : while (1) {
1233 28 : ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1234 28 : if (ret < 0)
1235 0 : goto out;
1236 :
1237 28 : nr = btrfs_header_nritems(path->nodes[0]);
1238 28 : if (!nr)
1239 : break;
1240 :
1241 14 : path->slots[0] = 0;
1242 14 : ret = btrfs_del_items(trans, root, path, 0, nr);
1243 14 : if (ret)
1244 0 : goto out;
1245 :
1246 14 : btrfs_release_path(path);
1247 : }
1248 :
1249 : ret = 0;
1250 14 : out:
1251 14 : btrfs_free_path(path);
1252 14 : return ret;
1253 : }
1254 :
1255 5 : int btrfs_delete_free_space_tree(struct btrfs_fs_info *fs_info)
1256 : {
1257 5 : struct btrfs_trans_handle *trans;
1258 5 : struct btrfs_root *tree_root = fs_info->tree_root;
1259 5 : struct btrfs_key key = {
1260 : .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
1261 : .type = BTRFS_ROOT_ITEM_KEY,
1262 : .offset = 0,
1263 : };
1264 5 : struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key);
1265 5 : int ret;
1266 :
1267 5 : trans = btrfs_start_transaction(tree_root, 0);
1268 5 : if (IS_ERR(trans))
1269 0 : return PTR_ERR(trans);
1270 :
1271 5 : btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1272 5 : btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1273 :
1274 5 : ret = clear_free_space_tree(trans, free_space_root);
1275 5 : if (ret)
1276 0 : goto abort;
1277 :
1278 5 : ret = btrfs_del_root(trans, &free_space_root->root_key);
1279 5 : if (ret)
1280 0 : goto abort;
1281 :
1282 5 : btrfs_global_root_delete(free_space_root);
1283 :
1284 5 : spin_lock(&fs_info->trans_lock);
1285 5 : list_del(&free_space_root->dirty_list);
1286 5 : spin_unlock(&fs_info->trans_lock);
1287 :
1288 5 : btrfs_tree_lock(free_space_root->node);
1289 5 : btrfs_clear_buffer_dirty(trans, free_space_root->node);
1290 5 : btrfs_tree_unlock(free_space_root->node);
1291 5 : btrfs_free_tree_block(trans, btrfs_root_id(free_space_root),
1292 : free_space_root->node, 0, 1);
1293 :
1294 5 : btrfs_put_root(free_space_root);
1295 :
1296 5 : return btrfs_commit_transaction(trans);
1297 :
1298 0 : abort:
1299 0 : btrfs_abort_transaction(trans, ret);
1300 0 : btrfs_end_transaction(trans);
1301 0 : return ret;
1302 : }
1303 :
1304 9 : int btrfs_rebuild_free_space_tree(struct btrfs_fs_info *fs_info)
1305 : {
1306 9 : struct btrfs_trans_handle *trans;
1307 9 : struct btrfs_key key = {
1308 : .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
1309 : .type = BTRFS_ROOT_ITEM_KEY,
1310 : .offset = 0,
1311 : };
1312 9 : struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key);
1313 9 : struct rb_node *node;
1314 9 : int ret;
1315 :
1316 9 : trans = btrfs_start_transaction(free_space_root, 1);
1317 9 : if (IS_ERR(trans))
1318 0 : return PTR_ERR(trans);
1319 :
1320 9 : set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1321 9 : set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1322 :
1323 9 : ret = clear_free_space_tree(trans, free_space_root);
1324 9 : if (ret)
1325 0 : goto abort;
1326 :
1327 9 : node = rb_first_cached(&fs_info->block_group_cache_tree);
1328 36 : while (node) {
1329 27 : struct btrfs_block_group *block_group;
1330 :
1331 27 : block_group = rb_entry(node, struct btrfs_block_group,
1332 : cache_node);
1333 27 : ret = populate_free_space_tree(trans, block_group);
1334 27 : if (ret)
1335 0 : goto abort;
1336 27 : node = rb_next(node);
1337 : }
1338 :
1339 9 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1340 9 : btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1341 9 : clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1342 :
1343 9 : ret = btrfs_commit_transaction(trans);
1344 9 : clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1345 9 : return ret;
1346 0 : abort:
1347 0 : btrfs_abort_transaction(trans, ret);
1348 0 : btrfs_end_transaction(trans);
1349 0 : return ret;
1350 : }
1351 :
1352 1436 : 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 1436 : int ret;
1357 :
1358 1436 : clear_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags);
1359 :
1360 1436 : ret = add_new_free_space_info(trans, block_group, path);
1361 1436 : if (ret)
1362 : return ret;
1363 :
1364 1436 : return __add_to_free_space_tree(trans, block_group, path,
1365 : block_group->start,
1366 : block_group->length);
1367 : }
1368 :
1369 1436 : int add_block_group_free_space(struct btrfs_trans_handle *trans,
1370 : struct btrfs_block_group *block_group)
1371 : {
1372 1436 : struct btrfs_fs_info *fs_info = trans->fs_info;
1373 1436 : struct btrfs_path *path = NULL;
1374 1436 : int ret = 0;
1375 :
1376 1436 : if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1377 : return 0;
1378 :
1379 1436 : mutex_lock(&block_group->free_space_lock);
1380 1436 : if (!test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags))
1381 2 : goto out;
1382 :
1383 1434 : path = btrfs_alloc_path();
1384 1434 : if (!path) {
1385 0 : ret = -ENOMEM;
1386 0 : goto out;
1387 : }
1388 :
1389 1434 : ret = __add_block_group_free_space(trans, block_group, path);
1390 :
1391 1436 : out:
1392 1436 : btrfs_free_path(path);
1393 1436 : mutex_unlock(&block_group->free_space_lock);
1394 1436 : if (ret)
1395 0 : btrfs_abort_transaction(trans, ret);
1396 : return ret;
1397 : }
1398 :
1399 532 : int remove_block_group_free_space(struct btrfs_trans_handle *trans,
1400 : struct btrfs_block_group *block_group)
1401 : {
1402 532 : struct btrfs_root *root = btrfs_free_space_root(block_group);
1403 532 : struct btrfs_path *path;
1404 532 : struct btrfs_key key, found_key;
1405 532 : struct extent_buffer *leaf;
1406 532 : u64 start, end;
1407 532 : int done = 0, nr;
1408 532 : int ret;
1409 :
1410 532 : if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
1411 : return 0;
1412 :
1413 1064 : 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 532 : path = btrfs_alloc_path();
1419 532 : if (!path) {
1420 0 : ret = -ENOMEM;
1421 0 : goto out;
1422 : }
1423 :
1424 532 : start = block_group->start;
1425 532 : end = block_group->start + block_group->length;
1426 :
1427 532 : key.objectid = end - 1;
1428 532 : key.type = (u8)-1;
1429 532 : key.offset = (u64)-1;
1430 :
1431 1064 : while (!done) {
1432 532 : ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
1433 532 : if (ret)
1434 0 : goto out;
1435 :
1436 532 : leaf = path->nodes[0];
1437 532 : nr = 0;
1438 532 : path->slots[0]++;
1439 532 : while (path->slots[0] > 0) {
1440 1070 : btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
1441 :
1442 1070 : if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
1443 532 : ASSERT(found_key.objectid == block_group->start);
1444 532 : ASSERT(found_key.offset == block_group->length);
1445 532 : done = 1;
1446 532 : nr++;
1447 532 : path->slots[0]--;
1448 532 : break;
1449 538 : } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
1450 : found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
1451 538 : ASSERT(found_key.objectid >= start);
1452 538 : ASSERT(found_key.objectid < end);
1453 538 : ASSERT(found_key.objectid + found_key.offset <= end);
1454 538 : nr++;
1455 538 : path->slots[0]--;
1456 : } else {
1457 1070 : ASSERT(0);
1458 : }
1459 : }
1460 :
1461 532 : ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
1462 532 : if (ret)
1463 0 : goto out;
1464 532 : btrfs_release_path(path);
1465 : }
1466 :
1467 : ret = 0;
1468 532 : out:
1469 532 : btrfs_free_path(path);
1470 532 : if (ret)
1471 0 : btrfs_abort_transaction(trans, ret);
1472 : return ret;
1473 : }
1474 :
1475 2231 : static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
1476 : struct btrfs_path *path,
1477 : u32 expected_extent_count)
1478 : {
1479 2231 : struct btrfs_block_group *block_group;
1480 2231 : struct btrfs_fs_info *fs_info;
1481 2231 : struct btrfs_root *root;
1482 2231 : struct btrfs_key key;
1483 2231 : int prev_bit = 0, bit;
1484 : /* Initialize to silence GCC. */
1485 2231 : u64 extent_start = 0;
1486 2231 : u64 end, offset;
1487 2231 : u64 total_found = 0;
1488 2231 : u32 extent_count = 0;
1489 2231 : int ret;
1490 :
1491 2231 : block_group = caching_ctl->block_group;
1492 2231 : fs_info = block_group->fs_info;
1493 2231 : root = btrfs_free_space_root(block_group);
1494 :
1495 2231 : end = block_group->start + block_group->length;
1496 :
1497 34232 : while (1) {
1498 34232 : ret = btrfs_next_item(root, path);
1499 34232 : if (ret < 0)
1500 0 : goto out;
1501 34232 : if (ret)
1502 : break;
1503 :
1504 33035 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1505 :
1506 33035 : if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1507 : break;
1508 :
1509 32001 : ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
1510 32001 : ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1511 :
1512 : offset = key.objectid;
1513 65510385 : while (offset < key.objectid + key.offset) {
1514 65478384 : bit = free_space_test_bit(block_group, path, offset);
1515 65478384 : if (prev_bit == 0 && bit == 1) {
1516 : extent_start = offset;
1517 65431903 : } else if (prev_bit == 1 && bit == 0) {
1518 44274 : total_found += add_new_free_space(block_group,
1519 : extent_start,
1520 : offset);
1521 44274 : if (total_found > CACHING_CTL_WAKE_UP) {
1522 1036 : total_found = 0;
1523 1036 : wake_up(&caching_ctl->wait);
1524 : }
1525 44274 : extent_count++;
1526 : }
1527 65478384 : prev_bit = bit;
1528 65478384 : offset += fs_info->sectorsize;
1529 : }
1530 : }
1531 2231 : if (prev_bit == 1) {
1532 2207 : total_found += add_new_free_space(block_group, extent_start,
1533 : end);
1534 2207 : extent_count++;
1535 : }
1536 :
1537 2231 : 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 2231 : out:
1549 2231 : return ret;
1550 : }
1551 :
1552 3896 : static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
1553 : struct btrfs_path *path,
1554 : u32 expected_extent_count)
1555 : {
1556 3896 : struct btrfs_block_group *block_group;
1557 3896 : struct btrfs_fs_info *fs_info;
1558 3896 : struct btrfs_root *root;
1559 3896 : struct btrfs_key key;
1560 3896 : u64 end;
1561 3896 : u64 total_found = 0;
1562 3896 : u32 extent_count = 0;
1563 3896 : int ret;
1564 :
1565 3896 : block_group = caching_ctl->block_group;
1566 3896 : fs_info = block_group->fs_info;
1567 3896 : root = btrfs_free_space_root(block_group);
1568 :
1569 3896 : end = block_group->start + block_group->length;
1570 :
1571 124696 : while (1) {
1572 64296 : ret = btrfs_next_item(root, path);
1573 64296 : if (ret < 0)
1574 0 : goto out;
1575 64296 : if (ret)
1576 : break;
1577 :
1578 63445 : btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1579 :
1580 63445 : if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1581 : break;
1582 :
1583 60400 : ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
1584 60400 : ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1585 :
1586 120800 : total_found += add_new_free_space(block_group, key.objectid,
1587 60400 : key.objectid + key.offset);
1588 60400 : if (total_found > CACHING_CTL_WAKE_UP) {
1589 11789 : total_found = 0;
1590 11789 : wake_up(&caching_ctl->wait);
1591 : }
1592 60400 : extent_count++;
1593 : }
1594 :
1595 3896 : 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 3896 : out:
1607 3896 : return ret;
1608 : }
1609 :
1610 6127 : int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
1611 : {
1612 6127 : struct btrfs_block_group *block_group;
1613 6127 : struct btrfs_free_space_info *info;
1614 6127 : struct btrfs_path *path;
1615 6127 : u32 extent_count, flags;
1616 6127 : int ret;
1617 :
1618 6127 : block_group = caching_ctl->block_group;
1619 :
1620 6127 : path = btrfs_alloc_path();
1621 6127 : 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 6127 : path->skip_locking = 1;
1629 6127 : path->search_commit_root = 1;
1630 6127 : path->reada = READA_FORWARD;
1631 :
1632 6127 : info = search_free_space_info(NULL, block_group, path, 0);
1633 6127 : if (IS_ERR(info)) {
1634 0 : ret = PTR_ERR(info);
1635 0 : goto out;
1636 : }
1637 6127 : extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
1638 6127 : 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 6127 : if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
1646 2231 : ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
1647 : else
1648 3896 : ret = load_free_space_extents(caching_ctl, path, extent_count);
1649 :
1650 6127 : out:
1651 6127 : btrfs_free_path(path);
1652 6127 : return ret;
1653 : }
|
