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