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