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