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