2 * Copyright (C) 2008 Red Hat. All rights reserved.
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.
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.
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.
19 #include <linux/pagemap.h>
20 #include <linux/sched.h>
21 #include <linux/slab.h>
22 #include <linux/math64.h>
23 #include <linux/ratelimit.h>
25 #include "free-space-cache.h"
26 #include "transaction.h"
28 #include "extent_io.h"
29 #include "inode-map.h"
31 #define BITS_PER_BITMAP (PAGE_CACHE_SIZE * 8)
32 #define MAX_CACHE_BYTES_PER_GIG (32 * 1024)
34 static int link_free_space(struct btrfs_free_space_ctl
*ctl
,
35 struct btrfs_free_space
*info
);
36 static void unlink_free_space(struct btrfs_free_space_ctl
*ctl
,
37 struct btrfs_free_space
*info
);
39 static struct inode
*__lookup_free_space_inode(struct btrfs_root
*root
,
40 struct btrfs_path
*path
,
44 struct btrfs_key location
;
45 struct btrfs_disk_key disk_key
;
46 struct btrfs_free_space_header
*header
;
47 struct extent_buffer
*leaf
;
48 struct inode
*inode
= NULL
;
51 key
.objectid
= BTRFS_FREE_SPACE_OBJECTID
;
55 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
59 btrfs_release_path(path
);
60 return ERR_PTR(-ENOENT
);
63 leaf
= path
->nodes
[0];
64 header
= btrfs_item_ptr(leaf
, path
->slots
[0],
65 struct btrfs_free_space_header
);
66 btrfs_free_space_key(leaf
, header
, &disk_key
);
67 btrfs_disk_key_to_cpu(&location
, &disk_key
);
68 btrfs_release_path(path
);
70 inode
= btrfs_iget(root
->fs_info
->sb
, &location
, root
, NULL
);
72 return ERR_PTR(-ENOENT
);
75 if (is_bad_inode(inode
)) {
77 return ERR_PTR(-ENOENT
);
80 mapping_set_gfp_mask(inode
->i_mapping
,
81 mapping_gfp_mask(inode
->i_mapping
) & ~__GFP_FS
);
86 struct inode
*lookup_free_space_inode(struct btrfs_root
*root
,
87 struct btrfs_block_group_cache
88 *block_group
, struct btrfs_path
*path
)
90 struct inode
*inode
= NULL
;
91 u32 flags
= BTRFS_INODE_NODATASUM
| BTRFS_INODE_NODATACOW
;
93 spin_lock(&block_group
->lock
);
94 if (block_group
->inode
)
95 inode
= igrab(block_group
->inode
);
96 spin_unlock(&block_group
->lock
);
100 inode
= __lookup_free_space_inode(root
, path
,
101 block_group
->key
.objectid
);
105 spin_lock(&block_group
->lock
);
106 if (!((BTRFS_I(inode
)->flags
& flags
) == flags
)) {
107 btrfs_info(root
->fs_info
,
108 "Old style space inode found, converting.");
109 BTRFS_I(inode
)->flags
|= BTRFS_INODE_NODATASUM
|
110 BTRFS_INODE_NODATACOW
;
111 block_group
->disk_cache_state
= BTRFS_DC_CLEAR
;
114 if (!block_group
->iref
) {
115 block_group
->inode
= igrab(inode
);
116 block_group
->iref
= 1;
118 spin_unlock(&block_group
->lock
);
123 static int __create_free_space_inode(struct btrfs_root
*root
,
124 struct btrfs_trans_handle
*trans
,
125 struct btrfs_path
*path
,
128 struct btrfs_key key
;
129 struct btrfs_disk_key disk_key
;
130 struct btrfs_free_space_header
*header
;
131 struct btrfs_inode_item
*inode_item
;
132 struct extent_buffer
*leaf
;
133 u64 flags
= BTRFS_INODE_NOCOMPRESS
| BTRFS_INODE_PREALLOC
;
136 ret
= btrfs_insert_empty_inode(trans
, root
, path
, ino
);
140 /* We inline crc's for the free disk space cache */
141 if (ino
!= BTRFS_FREE_INO_OBJECTID
)
142 flags
|= BTRFS_INODE_NODATASUM
| BTRFS_INODE_NODATACOW
;
144 leaf
= path
->nodes
[0];
145 inode_item
= btrfs_item_ptr(leaf
, path
->slots
[0],
146 struct btrfs_inode_item
);
147 btrfs_item_key(leaf
, &disk_key
, path
->slots
[0]);
148 memset_extent_buffer(leaf
, 0, (unsigned long)inode_item
,
149 sizeof(*inode_item
));
150 btrfs_set_inode_generation(leaf
, inode_item
, trans
->transid
);
151 btrfs_set_inode_size(leaf
, inode_item
, 0);
152 btrfs_set_inode_nbytes(leaf
, inode_item
, 0);
153 btrfs_set_inode_uid(leaf
, inode_item
, 0);
154 btrfs_set_inode_gid(leaf
, inode_item
, 0);
155 btrfs_set_inode_mode(leaf
, inode_item
, S_IFREG
| 0600);
156 btrfs_set_inode_flags(leaf
, inode_item
, flags
);
157 btrfs_set_inode_nlink(leaf
, inode_item
, 1);
158 btrfs_set_inode_transid(leaf
, inode_item
, trans
->transid
);
159 btrfs_set_inode_block_group(leaf
, inode_item
, offset
);
160 btrfs_mark_buffer_dirty(leaf
);
161 btrfs_release_path(path
);
163 key
.objectid
= BTRFS_FREE_SPACE_OBJECTID
;
167 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
168 sizeof(struct btrfs_free_space_header
));
170 btrfs_release_path(path
);
173 leaf
= path
->nodes
[0];
174 header
= btrfs_item_ptr(leaf
, path
->slots
[0],
175 struct btrfs_free_space_header
);
176 memset_extent_buffer(leaf
, 0, (unsigned long)header
, sizeof(*header
));
177 btrfs_set_free_space_key(leaf
, header
, &disk_key
);
178 btrfs_mark_buffer_dirty(leaf
);
179 btrfs_release_path(path
);
184 int create_free_space_inode(struct btrfs_root
*root
,
185 struct btrfs_trans_handle
*trans
,
186 struct btrfs_block_group_cache
*block_group
,
187 struct btrfs_path
*path
)
192 ret
= btrfs_find_free_objectid(root
, &ino
);
196 return __create_free_space_inode(root
, trans
, path
, ino
,
197 block_group
->key
.objectid
);
200 int btrfs_check_trunc_cache_free_space(struct btrfs_root
*root
,
201 struct btrfs_block_rsv
*rsv
)
206 /* 1 for slack space, 1 for updating the inode */
207 needed_bytes
= btrfs_calc_trunc_metadata_size(root
, 1) +
208 btrfs_calc_trans_metadata_size(root
, 1);
210 spin_lock(&rsv
->lock
);
211 if (rsv
->reserved
< needed_bytes
)
215 spin_unlock(&rsv
->lock
);
219 int btrfs_truncate_free_space_cache(struct btrfs_root
*root
,
220 struct btrfs_trans_handle
*trans
,
225 btrfs_i_size_write(inode
, 0);
226 truncate_pagecache(inode
, 0);
229 * We don't need an orphan item because truncating the free space cache
230 * will never be split across transactions.
232 ret
= btrfs_truncate_inode_items(trans
, root
, inode
,
233 0, BTRFS_EXTENT_DATA_KEY
);
235 btrfs_abort_transaction(trans
, root
, ret
);
239 ret
= btrfs_update_inode(trans
, root
, inode
);
241 btrfs_abort_transaction(trans
, root
, ret
);
246 static int readahead_cache(struct inode
*inode
)
248 struct file_ra_state
*ra
;
249 unsigned long last_index
;
251 ra
= kzalloc(sizeof(*ra
), GFP_NOFS
);
255 file_ra_state_init(ra
, inode
->i_mapping
);
256 last_index
= (i_size_read(inode
) - 1) >> PAGE_CACHE_SHIFT
;
258 page_cache_sync_readahead(inode
->i_mapping
, ra
, NULL
, 0, last_index
);
269 struct btrfs_root
*root
;
273 unsigned check_crcs
:1;
276 static int io_ctl_init(struct io_ctl
*io_ctl
, struct inode
*inode
,
277 struct btrfs_root
*root
, int write
)
282 num_pages
= DIV_ROUND_UP(i_size_read(inode
), PAGE_CACHE_SIZE
);
284 if (btrfs_ino(inode
) != BTRFS_FREE_INO_OBJECTID
)
287 /* Make sure we can fit our crcs into the first page */
288 if (write
&& check_crcs
&&
289 (num_pages
* sizeof(u32
)) >= PAGE_CACHE_SIZE
)
292 memset(io_ctl
, 0, sizeof(struct io_ctl
));
294 io_ctl
->pages
= kzalloc(sizeof(struct page
*) * num_pages
, GFP_NOFS
);
298 io_ctl
->num_pages
= num_pages
;
300 io_ctl
->check_crcs
= check_crcs
;
305 static void io_ctl_free(struct io_ctl
*io_ctl
)
307 kfree(io_ctl
->pages
);
310 static void io_ctl_unmap_page(struct io_ctl
*io_ctl
)
313 kunmap(io_ctl
->page
);
319 static void io_ctl_map_page(struct io_ctl
*io_ctl
, int clear
)
321 ASSERT(io_ctl
->index
< io_ctl
->num_pages
);
322 io_ctl
->page
= io_ctl
->pages
[io_ctl
->index
++];
323 io_ctl
->cur
= kmap(io_ctl
->page
);
324 io_ctl
->orig
= io_ctl
->cur
;
325 io_ctl
->size
= PAGE_CACHE_SIZE
;
327 memset(io_ctl
->cur
, 0, PAGE_CACHE_SIZE
);
330 static void io_ctl_drop_pages(struct io_ctl
*io_ctl
)
334 io_ctl_unmap_page(io_ctl
);
336 for (i
= 0; i
< io_ctl
->num_pages
; i
++) {
337 if (io_ctl
->pages
[i
]) {
338 ClearPageChecked(io_ctl
->pages
[i
]);
339 unlock_page(io_ctl
->pages
[i
]);
340 page_cache_release(io_ctl
->pages
[i
]);
345 static int io_ctl_prepare_pages(struct io_ctl
*io_ctl
, struct inode
*inode
,
349 gfp_t mask
= btrfs_alloc_write_mask(inode
->i_mapping
);
352 for (i
= 0; i
< io_ctl
->num_pages
; i
++) {
353 page
= find_or_create_page(inode
->i_mapping
, i
, mask
);
355 io_ctl_drop_pages(io_ctl
);
358 io_ctl
->pages
[i
] = page
;
359 if (uptodate
&& !PageUptodate(page
)) {
360 btrfs_readpage(NULL
, page
);
362 if (!PageUptodate(page
)) {
363 btrfs_err(BTRFS_I(inode
)->root
->fs_info
,
364 "error reading free space cache");
365 io_ctl_drop_pages(io_ctl
);
371 for (i
= 0; i
< io_ctl
->num_pages
; i
++) {
372 clear_page_dirty_for_io(io_ctl
->pages
[i
]);
373 set_page_extent_mapped(io_ctl
->pages
[i
]);
379 static void io_ctl_set_generation(struct io_ctl
*io_ctl
, u64 generation
)
383 io_ctl_map_page(io_ctl
, 1);
386 * Skip the csum areas. If we don't check crcs then we just have a
387 * 64bit chunk at the front of the first page.
389 if (io_ctl
->check_crcs
) {
390 io_ctl
->cur
+= (sizeof(u32
) * io_ctl
->num_pages
);
391 io_ctl
->size
-= sizeof(u64
) + (sizeof(u32
) * io_ctl
->num_pages
);
393 io_ctl
->cur
+= sizeof(u64
);
394 io_ctl
->size
-= sizeof(u64
) * 2;
398 *val
= cpu_to_le64(generation
);
399 io_ctl
->cur
+= sizeof(u64
);
402 static int io_ctl_check_generation(struct io_ctl
*io_ctl
, u64 generation
)
407 * Skip the crc area. If we don't check crcs then we just have a 64bit
408 * chunk at the front of the first page.
410 if (io_ctl
->check_crcs
) {
411 io_ctl
->cur
+= sizeof(u32
) * io_ctl
->num_pages
;
412 io_ctl
->size
-= sizeof(u64
) +
413 (sizeof(u32
) * io_ctl
->num_pages
);
415 io_ctl
->cur
+= sizeof(u64
);
416 io_ctl
->size
-= sizeof(u64
) * 2;
420 if (le64_to_cpu(*gen
) != generation
) {
421 printk_ratelimited(KERN_ERR
"BTRFS: space cache generation "
422 "(%Lu) does not match inode (%Lu)\n", *gen
,
424 io_ctl_unmap_page(io_ctl
);
427 io_ctl
->cur
+= sizeof(u64
);
431 static void io_ctl_set_crc(struct io_ctl
*io_ctl
, int index
)
437 if (!io_ctl
->check_crcs
) {
438 io_ctl_unmap_page(io_ctl
);
443 offset
= sizeof(u32
) * io_ctl
->num_pages
;
445 crc
= btrfs_csum_data(io_ctl
->orig
+ offset
, crc
,
446 PAGE_CACHE_SIZE
- offset
);
447 btrfs_csum_final(crc
, (char *)&crc
);
448 io_ctl_unmap_page(io_ctl
);
449 tmp
= kmap(io_ctl
->pages
[0]);
452 kunmap(io_ctl
->pages
[0]);
455 static int io_ctl_check_crc(struct io_ctl
*io_ctl
, int index
)
461 if (!io_ctl
->check_crcs
) {
462 io_ctl_map_page(io_ctl
, 0);
467 offset
= sizeof(u32
) * io_ctl
->num_pages
;
469 tmp
= kmap(io_ctl
->pages
[0]);
472 kunmap(io_ctl
->pages
[0]);
474 io_ctl_map_page(io_ctl
, 0);
475 crc
= btrfs_csum_data(io_ctl
->orig
+ offset
, crc
,
476 PAGE_CACHE_SIZE
- offset
);
477 btrfs_csum_final(crc
, (char *)&crc
);
479 printk_ratelimited(KERN_ERR
"BTRFS: csum mismatch on free "
481 io_ctl_unmap_page(io_ctl
);
488 static int io_ctl_add_entry(struct io_ctl
*io_ctl
, u64 offset
, u64 bytes
,
491 struct btrfs_free_space_entry
*entry
;
497 entry
->offset
= cpu_to_le64(offset
);
498 entry
->bytes
= cpu_to_le64(bytes
);
499 entry
->type
= (bitmap
) ? BTRFS_FREE_SPACE_BITMAP
:
500 BTRFS_FREE_SPACE_EXTENT
;
501 io_ctl
->cur
+= sizeof(struct btrfs_free_space_entry
);
502 io_ctl
->size
-= sizeof(struct btrfs_free_space_entry
);
504 if (io_ctl
->size
>= sizeof(struct btrfs_free_space_entry
))
507 io_ctl_set_crc(io_ctl
, io_ctl
->index
- 1);
509 /* No more pages to map */
510 if (io_ctl
->index
>= io_ctl
->num_pages
)
513 /* map the next page */
514 io_ctl_map_page(io_ctl
, 1);
518 static int io_ctl_add_bitmap(struct io_ctl
*io_ctl
, void *bitmap
)
524 * If we aren't at the start of the current page, unmap this one and
525 * map the next one if there is any left.
527 if (io_ctl
->cur
!= io_ctl
->orig
) {
528 io_ctl_set_crc(io_ctl
, io_ctl
->index
- 1);
529 if (io_ctl
->index
>= io_ctl
->num_pages
)
531 io_ctl_map_page(io_ctl
, 0);
534 memcpy(io_ctl
->cur
, bitmap
, PAGE_CACHE_SIZE
);
535 io_ctl_set_crc(io_ctl
, io_ctl
->index
- 1);
536 if (io_ctl
->index
< io_ctl
->num_pages
)
537 io_ctl_map_page(io_ctl
, 0);
541 static void io_ctl_zero_remaining_pages(struct io_ctl
*io_ctl
)
544 * If we're not on the boundary we know we've modified the page and we
545 * need to crc the page.
547 if (io_ctl
->cur
!= io_ctl
->orig
)
548 io_ctl_set_crc(io_ctl
, io_ctl
->index
- 1);
550 io_ctl_unmap_page(io_ctl
);
552 while (io_ctl
->index
< io_ctl
->num_pages
) {
553 io_ctl_map_page(io_ctl
, 1);
554 io_ctl_set_crc(io_ctl
, io_ctl
->index
- 1);
558 static int io_ctl_read_entry(struct io_ctl
*io_ctl
,
559 struct btrfs_free_space
*entry
, u8
*type
)
561 struct btrfs_free_space_entry
*e
;
565 ret
= io_ctl_check_crc(io_ctl
, io_ctl
->index
);
571 entry
->offset
= le64_to_cpu(e
->offset
);
572 entry
->bytes
= le64_to_cpu(e
->bytes
);
574 io_ctl
->cur
+= sizeof(struct btrfs_free_space_entry
);
575 io_ctl
->size
-= sizeof(struct btrfs_free_space_entry
);
577 if (io_ctl
->size
>= sizeof(struct btrfs_free_space_entry
))
580 io_ctl_unmap_page(io_ctl
);
585 static int io_ctl_read_bitmap(struct io_ctl
*io_ctl
,
586 struct btrfs_free_space
*entry
)
590 ret
= io_ctl_check_crc(io_ctl
, io_ctl
->index
);
594 memcpy(entry
->bitmap
, io_ctl
->cur
, PAGE_CACHE_SIZE
);
595 io_ctl_unmap_page(io_ctl
);
601 * Since we attach pinned extents after the fact we can have contiguous sections
602 * of free space that are split up in entries. This poses a problem with the
603 * tree logging stuff since it could have allocated across what appears to be 2
604 * entries since we would have merged the entries when adding the pinned extents
605 * back to the free space cache. So run through the space cache that we just
606 * loaded and merge contiguous entries. This will make the log replay stuff not
607 * blow up and it will make for nicer allocator behavior.
609 static void merge_space_tree(struct btrfs_free_space_ctl
*ctl
)
611 struct btrfs_free_space
*e
, *prev
= NULL
;
615 spin_lock(&ctl
->tree_lock
);
616 for (n
= rb_first(&ctl
->free_space_offset
); n
; n
= rb_next(n
)) {
617 e
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
620 if (e
->bitmap
|| prev
->bitmap
)
622 if (prev
->offset
+ prev
->bytes
== e
->offset
) {
623 unlink_free_space(ctl
, prev
);
624 unlink_free_space(ctl
, e
);
625 prev
->bytes
+= e
->bytes
;
626 kmem_cache_free(btrfs_free_space_cachep
, e
);
627 link_free_space(ctl
, prev
);
629 spin_unlock(&ctl
->tree_lock
);
635 spin_unlock(&ctl
->tree_lock
);
638 static int __load_free_space_cache(struct btrfs_root
*root
, struct inode
*inode
,
639 struct btrfs_free_space_ctl
*ctl
,
640 struct btrfs_path
*path
, u64 offset
)
642 struct btrfs_free_space_header
*header
;
643 struct extent_buffer
*leaf
;
644 struct io_ctl io_ctl
;
645 struct btrfs_key key
;
646 struct btrfs_free_space
*e
, *n
;
647 struct list_head bitmaps
;
654 INIT_LIST_HEAD(&bitmaps
);
656 /* Nothing in the space cache, goodbye */
657 if (!i_size_read(inode
))
660 key
.objectid
= BTRFS_FREE_SPACE_OBJECTID
;
664 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
668 btrfs_release_path(path
);
674 leaf
= path
->nodes
[0];
675 header
= btrfs_item_ptr(leaf
, path
->slots
[0],
676 struct btrfs_free_space_header
);
677 num_entries
= btrfs_free_space_entries(leaf
, header
);
678 num_bitmaps
= btrfs_free_space_bitmaps(leaf
, header
);
679 generation
= btrfs_free_space_generation(leaf
, header
);
680 btrfs_release_path(path
);
682 if (!BTRFS_I(inode
)->generation
) {
683 btrfs_info(root
->fs_info
,
684 "The free space cache file (%llu) is invalid. skip it\n",
689 if (BTRFS_I(inode
)->generation
!= generation
) {
690 btrfs_err(root
->fs_info
,
691 "free space inode generation (%llu) "
692 "did not match free space cache generation (%llu)",
693 BTRFS_I(inode
)->generation
, generation
);
700 ret
= io_ctl_init(&io_ctl
, inode
, root
, 0);
704 ret
= readahead_cache(inode
);
708 ret
= io_ctl_prepare_pages(&io_ctl
, inode
, 1);
712 ret
= io_ctl_check_crc(&io_ctl
, 0);
716 ret
= io_ctl_check_generation(&io_ctl
, generation
);
720 while (num_entries
) {
721 e
= kmem_cache_zalloc(btrfs_free_space_cachep
,
726 ret
= io_ctl_read_entry(&io_ctl
, e
, &type
);
728 kmem_cache_free(btrfs_free_space_cachep
, e
);
733 kmem_cache_free(btrfs_free_space_cachep
, e
);
737 if (type
== BTRFS_FREE_SPACE_EXTENT
) {
738 spin_lock(&ctl
->tree_lock
);
739 ret
= link_free_space(ctl
, e
);
740 spin_unlock(&ctl
->tree_lock
);
742 btrfs_err(root
->fs_info
,
743 "Duplicate entries in free space cache, dumping");
744 kmem_cache_free(btrfs_free_space_cachep
, e
);
750 e
->bitmap
= kzalloc(PAGE_CACHE_SIZE
, GFP_NOFS
);
753 btrfs_free_space_cachep
, e
);
756 spin_lock(&ctl
->tree_lock
);
757 ret
= link_free_space(ctl
, e
);
758 ctl
->total_bitmaps
++;
759 ctl
->op
->recalc_thresholds(ctl
);
760 spin_unlock(&ctl
->tree_lock
);
762 btrfs_err(root
->fs_info
,
763 "Duplicate entries in free space cache, dumping");
764 kmem_cache_free(btrfs_free_space_cachep
, e
);
767 list_add_tail(&e
->list
, &bitmaps
);
773 io_ctl_unmap_page(&io_ctl
);
776 * We add the bitmaps at the end of the entries in order that
777 * the bitmap entries are added to the cache.
779 list_for_each_entry_safe(e
, n
, &bitmaps
, list
) {
780 list_del_init(&e
->list
);
781 ret
= io_ctl_read_bitmap(&io_ctl
, e
);
786 io_ctl_drop_pages(&io_ctl
);
787 merge_space_tree(ctl
);
790 io_ctl_free(&io_ctl
);
793 io_ctl_drop_pages(&io_ctl
);
794 __btrfs_remove_free_space_cache(ctl
);
798 int load_free_space_cache(struct btrfs_fs_info
*fs_info
,
799 struct btrfs_block_group_cache
*block_group
)
801 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
802 struct btrfs_root
*root
= fs_info
->tree_root
;
804 struct btrfs_path
*path
;
807 u64 used
= btrfs_block_group_used(&block_group
->item
);
810 * If this block group has been marked to be cleared for one reason or
811 * another then we can't trust the on disk cache, so just return.
813 spin_lock(&block_group
->lock
);
814 if (block_group
->disk_cache_state
!= BTRFS_DC_WRITTEN
) {
815 spin_unlock(&block_group
->lock
);
818 spin_unlock(&block_group
->lock
);
820 path
= btrfs_alloc_path();
823 path
->search_commit_root
= 1;
824 path
->skip_locking
= 1;
826 inode
= lookup_free_space_inode(root
, block_group
, path
);
828 btrfs_free_path(path
);
832 /* We may have converted the inode and made the cache invalid. */
833 spin_lock(&block_group
->lock
);
834 if (block_group
->disk_cache_state
!= BTRFS_DC_WRITTEN
) {
835 spin_unlock(&block_group
->lock
);
836 btrfs_free_path(path
);
839 spin_unlock(&block_group
->lock
);
841 ret
= __load_free_space_cache(fs_info
->tree_root
, inode
, ctl
,
842 path
, block_group
->key
.objectid
);
843 btrfs_free_path(path
);
847 spin_lock(&ctl
->tree_lock
);
848 matched
= (ctl
->free_space
== (block_group
->key
.offset
- used
-
849 block_group
->bytes_super
));
850 spin_unlock(&ctl
->tree_lock
);
853 __btrfs_remove_free_space_cache(ctl
);
854 btrfs_warn(fs_info
, "block group %llu has wrong amount of free space",
855 block_group
->key
.objectid
);
860 /* This cache is bogus, make sure it gets cleared */
861 spin_lock(&block_group
->lock
);
862 block_group
->disk_cache_state
= BTRFS_DC_CLEAR
;
863 spin_unlock(&block_group
->lock
);
866 btrfs_warn(fs_info
, "failed to load free space cache for block group %llu, rebuild it now",
867 block_group
->key
.objectid
);
874 static noinline_for_stack
875 int write_cache_extent_entries(struct io_ctl
*io_ctl
,
876 struct btrfs_free_space_ctl
*ctl
,
877 struct btrfs_block_group_cache
*block_group
,
878 int *entries
, int *bitmaps
,
879 struct list_head
*bitmap_list
)
882 struct btrfs_free_cluster
*cluster
= NULL
;
883 struct rb_node
*node
= rb_first(&ctl
->free_space_offset
);
885 /* Get the cluster for this block_group if it exists */
886 if (block_group
&& !list_empty(&block_group
->cluster_list
)) {
887 cluster
= list_entry(block_group
->cluster_list
.next
,
888 struct btrfs_free_cluster
,
892 if (!node
&& cluster
) {
893 node
= rb_first(&cluster
->root
);
897 /* Write out the extent entries */
899 struct btrfs_free_space
*e
;
901 e
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
904 ret
= io_ctl_add_entry(io_ctl
, e
->offset
, e
->bytes
,
910 list_add_tail(&e
->list
, bitmap_list
);
913 node
= rb_next(node
);
914 if (!node
&& cluster
) {
915 node
= rb_first(&cluster
->root
);
924 static noinline_for_stack
int
925 update_cache_item(struct btrfs_trans_handle
*trans
,
926 struct btrfs_root
*root
,
928 struct btrfs_path
*path
, u64 offset
,
929 int entries
, int bitmaps
)
931 struct btrfs_key key
;
932 struct btrfs_free_space_header
*header
;
933 struct extent_buffer
*leaf
;
936 key
.objectid
= BTRFS_FREE_SPACE_OBJECTID
;
940 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
942 clear_extent_bit(&BTRFS_I(inode
)->io_tree
, 0, inode
->i_size
- 1,
943 EXTENT_DIRTY
| EXTENT_DELALLOC
, 0, 0, NULL
,
947 leaf
= path
->nodes
[0];
949 struct btrfs_key found_key
;
950 ASSERT(path
->slots
[0]);
952 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0]);
953 if (found_key
.objectid
!= BTRFS_FREE_SPACE_OBJECTID
||
954 found_key
.offset
!= offset
) {
955 clear_extent_bit(&BTRFS_I(inode
)->io_tree
, 0,
957 EXTENT_DIRTY
| EXTENT_DELALLOC
, 0, 0,
959 btrfs_release_path(path
);
964 BTRFS_I(inode
)->generation
= trans
->transid
;
965 header
= btrfs_item_ptr(leaf
, path
->slots
[0],
966 struct btrfs_free_space_header
);
967 btrfs_set_free_space_entries(leaf
, header
, entries
);
968 btrfs_set_free_space_bitmaps(leaf
, header
, bitmaps
);
969 btrfs_set_free_space_generation(leaf
, header
, trans
->transid
);
970 btrfs_mark_buffer_dirty(leaf
);
971 btrfs_release_path(path
);
979 static noinline_for_stack
int
980 write_pinned_extent_entries(struct btrfs_root
*root
,
981 struct btrfs_block_group_cache
*block_group
,
982 struct io_ctl
*io_ctl
,
985 u64 start
, extent_start
, extent_end
, len
;
986 struct extent_io_tree
*unpin
= NULL
;
993 * We want to add any pinned extents to our free space cache
994 * so we don't leak the space
996 * We shouldn't have switched the pinned extents yet so this is the
999 unpin
= root
->fs_info
->pinned_extents
;
1001 start
= block_group
->key
.objectid
;
1003 while (start
< block_group
->key
.objectid
+ block_group
->key
.offset
) {
1004 ret
= find_first_extent_bit(unpin
, start
,
1005 &extent_start
, &extent_end
,
1006 EXTENT_DIRTY
, NULL
);
1010 /* This pinned extent is out of our range */
1011 if (extent_start
>= block_group
->key
.objectid
+
1012 block_group
->key
.offset
)
1015 extent_start
= max(extent_start
, start
);
1016 extent_end
= min(block_group
->key
.objectid
+
1017 block_group
->key
.offset
, extent_end
+ 1);
1018 len
= extent_end
- extent_start
;
1021 ret
= io_ctl_add_entry(io_ctl
, extent_start
, len
, NULL
);
1031 static noinline_for_stack
int
1032 write_bitmap_entries(struct io_ctl
*io_ctl
, struct list_head
*bitmap_list
)
1034 struct list_head
*pos
, *n
;
1037 /* Write out the bitmaps */
1038 list_for_each_safe(pos
, n
, bitmap_list
) {
1039 struct btrfs_free_space
*entry
=
1040 list_entry(pos
, struct btrfs_free_space
, list
);
1042 ret
= io_ctl_add_bitmap(io_ctl
, entry
->bitmap
);
1045 list_del_init(&entry
->list
);
1051 static int flush_dirty_cache(struct inode
*inode
)
1055 ret
= btrfs_wait_ordered_range(inode
, 0, (u64
)-1);
1057 clear_extent_bit(&BTRFS_I(inode
)->io_tree
, 0, inode
->i_size
- 1,
1058 EXTENT_DIRTY
| EXTENT_DELALLOC
, 0, 0, NULL
,
1064 static void noinline_for_stack
1065 cleanup_write_cache_enospc(struct inode
*inode
,
1066 struct io_ctl
*io_ctl
,
1067 struct extent_state
**cached_state
,
1068 struct list_head
*bitmap_list
)
1070 struct list_head
*pos
, *n
;
1072 list_for_each_safe(pos
, n
, bitmap_list
) {
1073 struct btrfs_free_space
*entry
=
1074 list_entry(pos
, struct btrfs_free_space
, list
);
1075 list_del_init(&entry
->list
);
1077 io_ctl_drop_pages(io_ctl
);
1078 unlock_extent_cached(&BTRFS_I(inode
)->io_tree
, 0,
1079 i_size_read(inode
) - 1, cached_state
,
1084 * __btrfs_write_out_cache - write out cached info to an inode
1085 * @root - the root the inode belongs to
1086 * @ctl - the free space cache we are going to write out
1087 * @block_group - the block_group for this cache if it belongs to a block_group
1088 * @trans - the trans handle
1089 * @path - the path to use
1090 * @offset - the offset for the key we'll insert
1092 * This function writes out a free space cache struct to disk for quick recovery
1093 * on mount. This will return 0 if it was successfull in writing the cache out,
1094 * and -1 if it was not.
1096 static int __btrfs_write_out_cache(struct btrfs_root
*root
, struct inode
*inode
,
1097 struct btrfs_free_space_ctl
*ctl
,
1098 struct btrfs_block_group_cache
*block_group
,
1099 struct btrfs_trans_handle
*trans
,
1100 struct btrfs_path
*path
, u64 offset
)
1102 struct extent_state
*cached_state
= NULL
;
1103 struct io_ctl io_ctl
;
1104 LIST_HEAD(bitmap_list
);
1109 if (!i_size_read(inode
))
1112 ret
= io_ctl_init(&io_ctl
, inode
, root
, 1);
1116 if (block_group
&& (block_group
->flags
& BTRFS_BLOCK_GROUP_DATA
)) {
1117 down_write(&block_group
->data_rwsem
);
1118 spin_lock(&block_group
->lock
);
1119 if (block_group
->delalloc_bytes
) {
1120 block_group
->disk_cache_state
= BTRFS_DC_WRITTEN
;
1121 spin_unlock(&block_group
->lock
);
1122 up_write(&block_group
->data_rwsem
);
1123 BTRFS_I(inode
)->generation
= 0;
1127 spin_unlock(&block_group
->lock
);
1130 /* Lock all pages first so we can lock the extent safely. */
1131 io_ctl_prepare_pages(&io_ctl
, inode
, 0);
1133 lock_extent_bits(&BTRFS_I(inode
)->io_tree
, 0, i_size_read(inode
) - 1,
1136 io_ctl_set_generation(&io_ctl
, trans
->transid
);
1138 /* Write out the extent entries in the free space cache */
1139 ret
= write_cache_extent_entries(&io_ctl
, ctl
,
1140 block_group
, &entries
, &bitmaps
,
1146 * Some spaces that are freed in the current transaction are pinned,
1147 * they will be added into free space cache after the transaction is
1148 * committed, we shouldn't lose them.
1150 ret
= write_pinned_extent_entries(root
, block_group
, &io_ctl
, &entries
);
1154 /* At last, we write out all the bitmaps. */
1155 ret
= write_bitmap_entries(&io_ctl
, &bitmap_list
);
1159 /* Zero out the rest of the pages just to make sure */
1160 io_ctl_zero_remaining_pages(&io_ctl
);
1162 /* Everything is written out, now we dirty the pages in the file. */
1163 ret
= btrfs_dirty_pages(root
, inode
, io_ctl
.pages
, io_ctl
.num_pages
,
1164 0, i_size_read(inode
), &cached_state
);
1168 if (block_group
&& (block_group
->flags
& BTRFS_BLOCK_GROUP_DATA
))
1169 up_write(&block_group
->data_rwsem
);
1171 * Release the pages and unlock the extent, we will flush
1174 io_ctl_drop_pages(&io_ctl
);
1176 unlock_extent_cached(&BTRFS_I(inode
)->io_tree
, 0,
1177 i_size_read(inode
) - 1, &cached_state
, GFP_NOFS
);
1179 /* Flush the dirty pages in the cache file. */
1180 ret
= flush_dirty_cache(inode
);
1184 /* Update the cache item to tell everyone this cache file is valid. */
1185 ret
= update_cache_item(trans
, root
, inode
, path
, offset
,
1188 io_ctl_free(&io_ctl
);
1190 invalidate_inode_pages2(inode
->i_mapping
);
1191 BTRFS_I(inode
)->generation
= 0;
1193 btrfs_update_inode(trans
, root
, inode
);
1197 cleanup_write_cache_enospc(inode
, &io_ctl
, &cached_state
, &bitmap_list
);
1199 if (block_group
&& (block_group
->flags
& BTRFS_BLOCK_GROUP_DATA
))
1200 up_write(&block_group
->data_rwsem
);
1205 int btrfs_write_out_cache(struct btrfs_root
*root
,
1206 struct btrfs_trans_handle
*trans
,
1207 struct btrfs_block_group_cache
*block_group
,
1208 struct btrfs_path
*path
)
1210 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
1211 struct inode
*inode
;
1214 root
= root
->fs_info
->tree_root
;
1216 spin_lock(&block_group
->lock
);
1217 if (block_group
->disk_cache_state
< BTRFS_DC_SETUP
) {
1218 spin_unlock(&block_group
->lock
);
1222 if (block_group
->delalloc_bytes
) {
1223 block_group
->disk_cache_state
= BTRFS_DC_WRITTEN
;
1224 spin_unlock(&block_group
->lock
);
1227 spin_unlock(&block_group
->lock
);
1229 inode
= lookup_free_space_inode(root
, block_group
, path
);
1233 ret
= __btrfs_write_out_cache(root
, inode
, ctl
, block_group
, trans
,
1234 path
, block_group
->key
.objectid
);
1236 spin_lock(&block_group
->lock
);
1237 block_group
->disk_cache_state
= BTRFS_DC_ERROR
;
1238 spin_unlock(&block_group
->lock
);
1241 btrfs_err(root
->fs_info
,
1242 "failed to write free space cache for block group %llu",
1243 block_group
->key
.objectid
);
1251 static inline unsigned long offset_to_bit(u64 bitmap_start
, u32 unit
,
1254 ASSERT(offset
>= bitmap_start
);
1255 offset
-= bitmap_start
;
1256 return (unsigned long)(div_u64(offset
, unit
));
1259 static inline unsigned long bytes_to_bits(u64 bytes
, u32 unit
)
1261 return (unsigned long)(div_u64(bytes
, unit
));
1264 static inline u64
offset_to_bitmap(struct btrfs_free_space_ctl
*ctl
,
1268 u64 bytes_per_bitmap
;
1270 bytes_per_bitmap
= BITS_PER_BITMAP
* ctl
->unit
;
1271 bitmap_start
= offset
- ctl
->start
;
1272 bitmap_start
= div64_u64(bitmap_start
, bytes_per_bitmap
);
1273 bitmap_start
*= bytes_per_bitmap
;
1274 bitmap_start
+= ctl
->start
;
1276 return bitmap_start
;
1279 static int tree_insert_offset(struct rb_root
*root
, u64 offset
,
1280 struct rb_node
*node
, int bitmap
)
1282 struct rb_node
**p
= &root
->rb_node
;
1283 struct rb_node
*parent
= NULL
;
1284 struct btrfs_free_space
*info
;
1288 info
= rb_entry(parent
, struct btrfs_free_space
, offset_index
);
1290 if (offset
< info
->offset
) {
1292 } else if (offset
> info
->offset
) {
1293 p
= &(*p
)->rb_right
;
1296 * we could have a bitmap entry and an extent entry
1297 * share the same offset. If this is the case, we want
1298 * the extent entry to always be found first if we do a
1299 * linear search through the tree, since we want to have
1300 * the quickest allocation time, and allocating from an
1301 * extent is faster than allocating from a bitmap. So
1302 * if we're inserting a bitmap and we find an entry at
1303 * this offset, we want to go right, or after this entry
1304 * logically. If we are inserting an extent and we've
1305 * found a bitmap, we want to go left, or before
1313 p
= &(*p
)->rb_right
;
1315 if (!info
->bitmap
) {
1324 rb_link_node(node
, parent
, p
);
1325 rb_insert_color(node
, root
);
1331 * searches the tree for the given offset.
1333 * fuzzy - If this is set, then we are trying to make an allocation, and we just
1334 * want a section that has at least bytes size and comes at or after the given
1337 static struct btrfs_free_space
*
1338 tree_search_offset(struct btrfs_free_space_ctl
*ctl
,
1339 u64 offset
, int bitmap_only
, int fuzzy
)
1341 struct rb_node
*n
= ctl
->free_space_offset
.rb_node
;
1342 struct btrfs_free_space
*entry
, *prev
= NULL
;
1344 /* find entry that is closest to the 'offset' */
1351 entry
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
1354 if (offset
< entry
->offset
)
1356 else if (offset
> entry
->offset
)
1369 * bitmap entry and extent entry may share same offset,
1370 * in that case, bitmap entry comes after extent entry.
1375 entry
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
1376 if (entry
->offset
!= offset
)
1379 WARN_ON(!entry
->bitmap
);
1382 if (entry
->bitmap
) {
1384 * if previous extent entry covers the offset,
1385 * we should return it instead of the bitmap entry
1387 n
= rb_prev(&entry
->offset_index
);
1389 prev
= rb_entry(n
, struct btrfs_free_space
,
1391 if (!prev
->bitmap
&&
1392 prev
->offset
+ prev
->bytes
> offset
)
1402 /* find last entry before the 'offset' */
1404 if (entry
->offset
> offset
) {
1405 n
= rb_prev(&entry
->offset_index
);
1407 entry
= rb_entry(n
, struct btrfs_free_space
,
1409 ASSERT(entry
->offset
<= offset
);
1418 if (entry
->bitmap
) {
1419 n
= rb_prev(&entry
->offset_index
);
1421 prev
= rb_entry(n
, struct btrfs_free_space
,
1423 if (!prev
->bitmap
&&
1424 prev
->offset
+ prev
->bytes
> offset
)
1427 if (entry
->offset
+ BITS_PER_BITMAP
* ctl
->unit
> offset
)
1429 } else if (entry
->offset
+ entry
->bytes
> offset
)
1436 if (entry
->bitmap
) {
1437 if (entry
->offset
+ BITS_PER_BITMAP
*
1441 if (entry
->offset
+ entry
->bytes
> offset
)
1445 n
= rb_next(&entry
->offset_index
);
1448 entry
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
1454 __unlink_free_space(struct btrfs_free_space_ctl
*ctl
,
1455 struct btrfs_free_space
*info
)
1457 rb_erase(&info
->offset_index
, &ctl
->free_space_offset
);
1458 ctl
->free_extents
--;
1461 static void unlink_free_space(struct btrfs_free_space_ctl
*ctl
,
1462 struct btrfs_free_space
*info
)
1464 __unlink_free_space(ctl
, info
);
1465 ctl
->free_space
-= info
->bytes
;
1468 static int link_free_space(struct btrfs_free_space_ctl
*ctl
,
1469 struct btrfs_free_space
*info
)
1473 ASSERT(info
->bytes
|| info
->bitmap
);
1474 ret
= tree_insert_offset(&ctl
->free_space_offset
, info
->offset
,
1475 &info
->offset_index
, (info
->bitmap
!= NULL
));
1479 ctl
->free_space
+= info
->bytes
;
1480 ctl
->free_extents
++;
1484 static void recalculate_thresholds(struct btrfs_free_space_ctl
*ctl
)
1486 struct btrfs_block_group_cache
*block_group
= ctl
->private;
1490 u64 size
= block_group
->key
.offset
;
1491 u64 bytes_per_bg
= BITS_PER_BITMAP
* ctl
->unit
;
1492 int max_bitmaps
= div64_u64(size
+ bytes_per_bg
- 1, bytes_per_bg
);
1494 max_bitmaps
= max(max_bitmaps
, 1);
1496 ASSERT(ctl
->total_bitmaps
<= max_bitmaps
);
1499 * The goal is to keep the total amount of memory used per 1gb of space
1500 * at or below 32k, so we need to adjust how much memory we allow to be
1501 * used by extent based free space tracking
1503 if (size
< 1024 * 1024 * 1024)
1504 max_bytes
= MAX_CACHE_BYTES_PER_GIG
;
1506 max_bytes
= MAX_CACHE_BYTES_PER_GIG
*
1507 div64_u64(size
, 1024 * 1024 * 1024);
1510 * we want to account for 1 more bitmap than what we have so we can make
1511 * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as
1512 * we add more bitmaps.
1514 bitmap_bytes
= (ctl
->total_bitmaps
+ 1) * PAGE_CACHE_SIZE
;
1516 if (bitmap_bytes
>= max_bytes
) {
1517 ctl
->extents_thresh
= 0;
1522 * we want the extent entry threshold to always be at most 1/2 the maxw
1523 * bytes we can have, or whatever is less than that.
1525 extent_bytes
= max_bytes
- bitmap_bytes
;
1526 extent_bytes
= min_t(u64
, extent_bytes
, div64_u64(max_bytes
, 2));
1528 ctl
->extents_thresh
=
1529 div64_u64(extent_bytes
, (sizeof(struct btrfs_free_space
)));
1532 static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl
*ctl
,
1533 struct btrfs_free_space
*info
,
1534 u64 offset
, u64 bytes
)
1536 unsigned long start
, count
;
1538 start
= offset_to_bit(info
->offset
, ctl
->unit
, offset
);
1539 count
= bytes_to_bits(bytes
, ctl
->unit
);
1540 ASSERT(start
+ count
<= BITS_PER_BITMAP
);
1542 bitmap_clear(info
->bitmap
, start
, count
);
1544 info
->bytes
-= bytes
;
1547 static void bitmap_clear_bits(struct btrfs_free_space_ctl
*ctl
,
1548 struct btrfs_free_space
*info
, u64 offset
,
1551 __bitmap_clear_bits(ctl
, info
, offset
, bytes
);
1552 ctl
->free_space
-= bytes
;
1555 static void bitmap_set_bits(struct btrfs_free_space_ctl
*ctl
,
1556 struct btrfs_free_space
*info
, u64 offset
,
1559 unsigned long start
, count
;
1561 start
= offset_to_bit(info
->offset
, ctl
->unit
, offset
);
1562 count
= bytes_to_bits(bytes
, ctl
->unit
);
1563 ASSERT(start
+ count
<= BITS_PER_BITMAP
);
1565 bitmap_set(info
->bitmap
, start
, count
);
1567 info
->bytes
+= bytes
;
1568 ctl
->free_space
+= bytes
;
1572 * If we can not find suitable extent, we will use bytes to record
1573 * the size of the max extent.
1575 static int search_bitmap(struct btrfs_free_space_ctl
*ctl
,
1576 struct btrfs_free_space
*bitmap_info
, u64
*offset
,
1579 unsigned long found_bits
= 0;
1580 unsigned long max_bits
= 0;
1581 unsigned long bits
, i
;
1582 unsigned long next_zero
;
1583 unsigned long extent_bits
;
1585 i
= offset_to_bit(bitmap_info
->offset
, ctl
->unit
,
1586 max_t(u64
, *offset
, bitmap_info
->offset
));
1587 bits
= bytes_to_bits(*bytes
, ctl
->unit
);
1589 for_each_set_bit_from(i
, bitmap_info
->bitmap
, BITS_PER_BITMAP
) {
1590 next_zero
= find_next_zero_bit(bitmap_info
->bitmap
,
1591 BITS_PER_BITMAP
, i
);
1592 extent_bits
= next_zero
- i
;
1593 if (extent_bits
>= bits
) {
1594 found_bits
= extent_bits
;
1596 } else if (extent_bits
> max_bits
) {
1597 max_bits
= extent_bits
;
1603 *offset
= (u64
)(i
* ctl
->unit
) + bitmap_info
->offset
;
1604 *bytes
= (u64
)(found_bits
) * ctl
->unit
;
1608 *bytes
= (u64
)(max_bits
) * ctl
->unit
;
1612 /* Cache the size of the max extent in bytes */
1613 static struct btrfs_free_space
*
1614 find_free_space(struct btrfs_free_space_ctl
*ctl
, u64
*offset
, u64
*bytes
,
1615 unsigned long align
, u64
*max_extent_size
)
1617 struct btrfs_free_space
*entry
;
1618 struct rb_node
*node
;
1623 if (!ctl
->free_space_offset
.rb_node
)
1626 entry
= tree_search_offset(ctl
, offset_to_bitmap(ctl
, *offset
), 0, 1);
1630 for (node
= &entry
->offset_index
; node
; node
= rb_next(node
)) {
1631 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
1632 if (entry
->bytes
< *bytes
) {
1633 if (entry
->bytes
> *max_extent_size
)
1634 *max_extent_size
= entry
->bytes
;
1638 /* make sure the space returned is big enough
1639 * to match our requested alignment
1641 if (*bytes
>= align
) {
1642 tmp
= entry
->offset
- ctl
->start
+ align
- 1;
1644 tmp
= tmp
* align
+ ctl
->start
;
1645 align_off
= tmp
- entry
->offset
;
1648 tmp
= entry
->offset
;
1651 if (entry
->bytes
< *bytes
+ align_off
) {
1652 if (entry
->bytes
> *max_extent_size
)
1653 *max_extent_size
= entry
->bytes
;
1657 if (entry
->bitmap
) {
1660 ret
= search_bitmap(ctl
, entry
, &tmp
, &size
);
1665 } else if (size
> *max_extent_size
) {
1666 *max_extent_size
= size
;
1672 *bytes
= entry
->bytes
- align_off
;
1679 static void add_new_bitmap(struct btrfs_free_space_ctl
*ctl
,
1680 struct btrfs_free_space
*info
, u64 offset
)
1682 info
->offset
= offset_to_bitmap(ctl
, offset
);
1684 INIT_LIST_HEAD(&info
->list
);
1685 link_free_space(ctl
, info
);
1686 ctl
->total_bitmaps
++;
1688 ctl
->op
->recalc_thresholds(ctl
);
1691 static void free_bitmap(struct btrfs_free_space_ctl
*ctl
,
1692 struct btrfs_free_space
*bitmap_info
)
1694 unlink_free_space(ctl
, bitmap_info
);
1695 kfree(bitmap_info
->bitmap
);
1696 kmem_cache_free(btrfs_free_space_cachep
, bitmap_info
);
1697 ctl
->total_bitmaps
--;
1698 ctl
->op
->recalc_thresholds(ctl
);
1701 static noinline
int remove_from_bitmap(struct btrfs_free_space_ctl
*ctl
,
1702 struct btrfs_free_space
*bitmap_info
,
1703 u64
*offset
, u64
*bytes
)
1706 u64 search_start
, search_bytes
;
1710 end
= bitmap_info
->offset
+ (u64
)(BITS_PER_BITMAP
* ctl
->unit
) - 1;
1713 * We need to search for bits in this bitmap. We could only cover some
1714 * of the extent in this bitmap thanks to how we add space, so we need
1715 * to search for as much as it as we can and clear that amount, and then
1716 * go searching for the next bit.
1718 search_start
= *offset
;
1719 search_bytes
= ctl
->unit
;
1720 search_bytes
= min(search_bytes
, end
- search_start
+ 1);
1721 ret
= search_bitmap(ctl
, bitmap_info
, &search_start
, &search_bytes
);
1722 if (ret
< 0 || search_start
!= *offset
)
1725 /* We may have found more bits than what we need */
1726 search_bytes
= min(search_bytes
, *bytes
);
1728 /* Cannot clear past the end of the bitmap */
1729 search_bytes
= min(search_bytes
, end
- search_start
+ 1);
1731 bitmap_clear_bits(ctl
, bitmap_info
, search_start
, search_bytes
);
1732 *offset
+= search_bytes
;
1733 *bytes
-= search_bytes
;
1736 struct rb_node
*next
= rb_next(&bitmap_info
->offset_index
);
1737 if (!bitmap_info
->bytes
)
1738 free_bitmap(ctl
, bitmap_info
);
1741 * no entry after this bitmap, but we still have bytes to
1742 * remove, so something has gone wrong.
1747 bitmap_info
= rb_entry(next
, struct btrfs_free_space
,
1751 * if the next entry isn't a bitmap we need to return to let the
1752 * extent stuff do its work.
1754 if (!bitmap_info
->bitmap
)
1758 * Ok the next item is a bitmap, but it may not actually hold
1759 * the information for the rest of this free space stuff, so
1760 * look for it, and if we don't find it return so we can try
1761 * everything over again.
1763 search_start
= *offset
;
1764 search_bytes
= ctl
->unit
;
1765 ret
= search_bitmap(ctl
, bitmap_info
, &search_start
,
1767 if (ret
< 0 || search_start
!= *offset
)
1771 } else if (!bitmap_info
->bytes
)
1772 free_bitmap(ctl
, bitmap_info
);
1777 static u64
add_bytes_to_bitmap(struct btrfs_free_space_ctl
*ctl
,
1778 struct btrfs_free_space
*info
, u64 offset
,
1781 u64 bytes_to_set
= 0;
1784 end
= info
->offset
+ (u64
)(BITS_PER_BITMAP
* ctl
->unit
);
1786 bytes_to_set
= min(end
- offset
, bytes
);
1788 bitmap_set_bits(ctl
, info
, offset
, bytes_to_set
);
1790 return bytes_to_set
;
1794 static bool use_bitmap(struct btrfs_free_space_ctl
*ctl
,
1795 struct btrfs_free_space
*info
)
1797 struct btrfs_block_group_cache
*block_group
= ctl
->private;
1800 * If we are below the extents threshold then we can add this as an
1801 * extent, and don't have to deal with the bitmap
1803 if (ctl
->free_extents
< ctl
->extents_thresh
) {
1805 * If this block group has some small extents we don't want to
1806 * use up all of our free slots in the cache with them, we want
1807 * to reserve them to larger extents, however if we have plent
1808 * of cache left then go ahead an dadd them, no sense in adding
1809 * the overhead of a bitmap if we don't have to.
1811 if (info
->bytes
<= block_group
->sectorsize
* 4) {
1812 if (ctl
->free_extents
* 2 <= ctl
->extents_thresh
)
1820 * The original block groups from mkfs can be really small, like 8
1821 * megabytes, so don't bother with a bitmap for those entries. However
1822 * some block groups can be smaller than what a bitmap would cover but
1823 * are still large enough that they could overflow the 32k memory limit,
1824 * so allow those block groups to still be allowed to have a bitmap
1827 if (((BITS_PER_BITMAP
* ctl
->unit
) >> 1) > block_group
->key
.offset
)
1833 static struct btrfs_free_space_op free_space_op
= {
1834 .recalc_thresholds
= recalculate_thresholds
,
1835 .use_bitmap
= use_bitmap
,
1838 static int insert_into_bitmap(struct btrfs_free_space_ctl
*ctl
,
1839 struct btrfs_free_space
*info
)
1841 struct btrfs_free_space
*bitmap_info
;
1842 struct btrfs_block_group_cache
*block_group
= NULL
;
1844 u64 bytes
, offset
, bytes_added
;
1847 bytes
= info
->bytes
;
1848 offset
= info
->offset
;
1850 if (!ctl
->op
->use_bitmap(ctl
, info
))
1853 if (ctl
->op
== &free_space_op
)
1854 block_group
= ctl
->private;
1857 * Since we link bitmaps right into the cluster we need to see if we
1858 * have a cluster here, and if so and it has our bitmap we need to add
1859 * the free space to that bitmap.
1861 if (block_group
&& !list_empty(&block_group
->cluster_list
)) {
1862 struct btrfs_free_cluster
*cluster
;
1863 struct rb_node
*node
;
1864 struct btrfs_free_space
*entry
;
1866 cluster
= list_entry(block_group
->cluster_list
.next
,
1867 struct btrfs_free_cluster
,
1869 spin_lock(&cluster
->lock
);
1870 node
= rb_first(&cluster
->root
);
1872 spin_unlock(&cluster
->lock
);
1873 goto no_cluster_bitmap
;
1876 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
1877 if (!entry
->bitmap
) {
1878 spin_unlock(&cluster
->lock
);
1879 goto no_cluster_bitmap
;
1882 if (entry
->offset
== offset_to_bitmap(ctl
, offset
)) {
1883 bytes_added
= add_bytes_to_bitmap(ctl
, entry
,
1885 bytes
-= bytes_added
;
1886 offset
+= bytes_added
;
1888 spin_unlock(&cluster
->lock
);
1896 bitmap_info
= tree_search_offset(ctl
, offset_to_bitmap(ctl
, offset
),
1903 bytes_added
= add_bytes_to_bitmap(ctl
, bitmap_info
, offset
, bytes
);
1904 bytes
-= bytes_added
;
1905 offset
+= bytes_added
;
1915 if (info
&& info
->bitmap
) {
1916 add_new_bitmap(ctl
, info
, offset
);
1921 spin_unlock(&ctl
->tree_lock
);
1923 /* no pre-allocated info, allocate a new one */
1925 info
= kmem_cache_zalloc(btrfs_free_space_cachep
,
1928 spin_lock(&ctl
->tree_lock
);
1934 /* allocate the bitmap */
1935 info
->bitmap
= kzalloc(PAGE_CACHE_SIZE
, GFP_NOFS
);
1936 spin_lock(&ctl
->tree_lock
);
1937 if (!info
->bitmap
) {
1947 kfree(info
->bitmap
);
1948 kmem_cache_free(btrfs_free_space_cachep
, info
);
1954 static bool try_merge_free_space(struct btrfs_free_space_ctl
*ctl
,
1955 struct btrfs_free_space
*info
, bool update_stat
)
1957 struct btrfs_free_space
*left_info
;
1958 struct btrfs_free_space
*right_info
;
1959 bool merged
= false;
1960 u64 offset
= info
->offset
;
1961 u64 bytes
= info
->bytes
;
1964 * first we want to see if there is free space adjacent to the range we
1965 * are adding, if there is remove that struct and add a new one to
1966 * cover the entire range
1968 right_info
= tree_search_offset(ctl
, offset
+ bytes
, 0, 0);
1969 if (right_info
&& rb_prev(&right_info
->offset_index
))
1970 left_info
= rb_entry(rb_prev(&right_info
->offset_index
),
1971 struct btrfs_free_space
, offset_index
);
1973 left_info
= tree_search_offset(ctl
, offset
- 1, 0, 0);
1975 if (right_info
&& !right_info
->bitmap
) {
1977 unlink_free_space(ctl
, right_info
);
1979 __unlink_free_space(ctl
, right_info
);
1980 info
->bytes
+= right_info
->bytes
;
1981 kmem_cache_free(btrfs_free_space_cachep
, right_info
);
1985 if (left_info
&& !left_info
->bitmap
&&
1986 left_info
->offset
+ left_info
->bytes
== offset
) {
1988 unlink_free_space(ctl
, left_info
);
1990 __unlink_free_space(ctl
, left_info
);
1991 info
->offset
= left_info
->offset
;
1992 info
->bytes
+= left_info
->bytes
;
1993 kmem_cache_free(btrfs_free_space_cachep
, left_info
);
2000 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl
*ctl
,
2001 struct btrfs_free_space
*info
,
2004 struct btrfs_free_space
*bitmap
;
2007 const u64 end
= info
->offset
+ info
->bytes
;
2008 const u64 bitmap_offset
= offset_to_bitmap(ctl
, end
);
2011 bitmap
= tree_search_offset(ctl
, bitmap_offset
, 1, 0);
2015 i
= offset_to_bit(bitmap
->offset
, ctl
->unit
, end
);
2016 j
= find_next_zero_bit(bitmap
->bitmap
, BITS_PER_BITMAP
, i
);
2019 bytes
= (j
- i
) * ctl
->unit
;
2020 info
->bytes
+= bytes
;
2023 bitmap_clear_bits(ctl
, bitmap
, end
, bytes
);
2025 __bitmap_clear_bits(ctl
, bitmap
, end
, bytes
);
2028 free_bitmap(ctl
, bitmap
);
2033 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl
*ctl
,
2034 struct btrfs_free_space
*info
,
2037 struct btrfs_free_space
*bitmap
;
2041 unsigned long prev_j
;
2044 bitmap_offset
= offset_to_bitmap(ctl
, info
->offset
);
2045 /* If we're on a boundary, try the previous logical bitmap. */
2046 if (bitmap_offset
== info
->offset
) {
2047 if (info
->offset
== 0)
2049 bitmap_offset
= offset_to_bitmap(ctl
, info
->offset
- 1);
2052 bitmap
= tree_search_offset(ctl
, bitmap_offset
, 1, 0);
2056 i
= offset_to_bit(bitmap
->offset
, ctl
->unit
, info
->offset
) - 1;
2058 prev_j
= (unsigned long)-1;
2059 for_each_clear_bit_from(j
, bitmap
->bitmap
, BITS_PER_BITMAP
) {
2067 if (prev_j
== (unsigned long)-1)
2068 bytes
= (i
+ 1) * ctl
->unit
;
2070 bytes
= (i
- prev_j
) * ctl
->unit
;
2072 info
->offset
-= bytes
;
2073 info
->bytes
+= bytes
;
2076 bitmap_clear_bits(ctl
, bitmap
, info
->offset
, bytes
);
2078 __bitmap_clear_bits(ctl
, bitmap
, info
->offset
, bytes
);
2081 free_bitmap(ctl
, bitmap
);
2087 * We prefer always to allocate from extent entries, both for clustered and
2088 * non-clustered allocation requests. So when attempting to add a new extent
2089 * entry, try to see if there's adjacent free space in bitmap entries, and if
2090 * there is, migrate that space from the bitmaps to the extent.
2091 * Like this we get better chances of satisfying space allocation requests
2092 * because we attempt to satisfy them based on a single cache entry, and never
2093 * on 2 or more entries - even if the entries represent a contiguous free space
2094 * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry
2097 static void steal_from_bitmap(struct btrfs_free_space_ctl
*ctl
,
2098 struct btrfs_free_space
*info
,
2102 * Only work with disconnected entries, as we can change their offset,
2103 * and must be extent entries.
2105 ASSERT(!info
->bitmap
);
2106 ASSERT(RB_EMPTY_NODE(&info
->offset_index
));
2108 if (ctl
->total_bitmaps
> 0) {
2110 bool stole_front
= false;
2112 stole_end
= steal_from_bitmap_to_end(ctl
, info
, update_stat
);
2113 if (ctl
->total_bitmaps
> 0)
2114 stole_front
= steal_from_bitmap_to_front(ctl
, info
,
2117 if (stole_end
|| stole_front
)
2118 try_merge_free_space(ctl
, info
, update_stat
);
2122 int __btrfs_add_free_space(struct btrfs_free_space_ctl
*ctl
,
2123 u64 offset
, u64 bytes
)
2125 struct btrfs_free_space
*info
;
2128 info
= kmem_cache_zalloc(btrfs_free_space_cachep
, GFP_NOFS
);
2132 info
->offset
= offset
;
2133 info
->bytes
= bytes
;
2134 RB_CLEAR_NODE(&info
->offset_index
);
2136 spin_lock(&ctl
->tree_lock
);
2138 if (try_merge_free_space(ctl
, info
, true))
2142 * There was no extent directly to the left or right of this new
2143 * extent then we know we're going to have to allocate a new extent, so
2144 * before we do that see if we need to drop this into a bitmap
2146 ret
= insert_into_bitmap(ctl
, info
);
2155 * Only steal free space from adjacent bitmaps if we're sure we're not
2156 * going to add the new free space to existing bitmap entries - because
2157 * that would mean unnecessary work that would be reverted. Therefore
2158 * attempt to steal space from bitmaps if we're adding an extent entry.
2160 steal_from_bitmap(ctl
, info
, true);
2162 ret
= link_free_space(ctl
, info
);
2164 kmem_cache_free(btrfs_free_space_cachep
, info
);
2166 spin_unlock(&ctl
->tree_lock
);
2169 printk(KERN_CRIT
"BTRFS: unable to add free space :%d\n", ret
);
2170 ASSERT(ret
!= -EEXIST
);
2176 int btrfs_remove_free_space(struct btrfs_block_group_cache
*block_group
,
2177 u64 offset
, u64 bytes
)
2179 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2180 struct btrfs_free_space
*info
;
2182 bool re_search
= false;
2184 spin_lock(&ctl
->tree_lock
);
2191 info
= tree_search_offset(ctl
, offset
, 0, 0);
2194 * oops didn't find an extent that matched the space we wanted
2195 * to remove, look for a bitmap instead
2197 info
= tree_search_offset(ctl
, offset_to_bitmap(ctl
, offset
),
2201 * If we found a partial bit of our free space in a
2202 * bitmap but then couldn't find the other part this may
2203 * be a problem, so WARN about it.
2211 if (!info
->bitmap
) {
2212 unlink_free_space(ctl
, info
);
2213 if (offset
== info
->offset
) {
2214 u64 to_free
= min(bytes
, info
->bytes
);
2216 info
->bytes
-= to_free
;
2217 info
->offset
+= to_free
;
2219 ret
= link_free_space(ctl
, info
);
2222 kmem_cache_free(btrfs_free_space_cachep
, info
);
2229 u64 old_end
= info
->bytes
+ info
->offset
;
2231 info
->bytes
= offset
- info
->offset
;
2232 ret
= link_free_space(ctl
, info
);
2237 /* Not enough bytes in this entry to satisfy us */
2238 if (old_end
< offset
+ bytes
) {
2239 bytes
-= old_end
- offset
;
2242 } else if (old_end
== offset
+ bytes
) {
2246 spin_unlock(&ctl
->tree_lock
);
2248 ret
= btrfs_add_free_space(block_group
, offset
+ bytes
,
2249 old_end
- (offset
+ bytes
));
2255 ret
= remove_from_bitmap(ctl
, info
, &offset
, &bytes
);
2256 if (ret
== -EAGAIN
) {
2261 spin_unlock(&ctl
->tree_lock
);
2266 void btrfs_dump_free_space(struct btrfs_block_group_cache
*block_group
,
2269 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2270 struct btrfs_free_space
*info
;
2274 for (n
= rb_first(&ctl
->free_space_offset
); n
; n
= rb_next(n
)) {
2275 info
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
2276 if (info
->bytes
>= bytes
&& !block_group
->ro
)
2278 btrfs_crit(block_group
->fs_info
,
2279 "entry offset %llu, bytes %llu, bitmap %s",
2280 info
->offset
, info
->bytes
,
2281 (info
->bitmap
) ? "yes" : "no");
2283 btrfs_info(block_group
->fs_info
, "block group has cluster?: %s",
2284 list_empty(&block_group
->cluster_list
) ? "no" : "yes");
2285 btrfs_info(block_group
->fs_info
,
2286 "%d blocks of free space at or bigger than bytes is", count
);
2289 void btrfs_init_free_space_ctl(struct btrfs_block_group_cache
*block_group
)
2291 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2293 spin_lock_init(&ctl
->tree_lock
);
2294 ctl
->unit
= block_group
->sectorsize
;
2295 ctl
->start
= block_group
->key
.objectid
;
2296 ctl
->private = block_group
;
2297 ctl
->op
= &free_space_op
;
2300 * we only want to have 32k of ram per block group for keeping
2301 * track of free space, and if we pass 1/2 of that we want to
2302 * start converting things over to using bitmaps
2304 ctl
->extents_thresh
= ((1024 * 32) / 2) /
2305 sizeof(struct btrfs_free_space
);
2309 * for a given cluster, put all of its extents back into the free
2310 * space cache. If the block group passed doesn't match the block group
2311 * pointed to by the cluster, someone else raced in and freed the
2312 * cluster already. In that case, we just return without changing anything
2315 __btrfs_return_cluster_to_free_space(
2316 struct btrfs_block_group_cache
*block_group
,
2317 struct btrfs_free_cluster
*cluster
)
2319 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2320 struct btrfs_free_space
*entry
;
2321 struct rb_node
*node
;
2323 spin_lock(&cluster
->lock
);
2324 if (cluster
->block_group
!= block_group
)
2327 cluster
->block_group
= NULL
;
2328 cluster
->window_start
= 0;
2329 list_del_init(&cluster
->block_group_list
);
2331 node
= rb_first(&cluster
->root
);
2335 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
2336 node
= rb_next(&entry
->offset_index
);
2337 rb_erase(&entry
->offset_index
, &cluster
->root
);
2338 RB_CLEAR_NODE(&entry
->offset_index
);
2340 bitmap
= (entry
->bitmap
!= NULL
);
2342 try_merge_free_space(ctl
, entry
, false);
2343 steal_from_bitmap(ctl
, entry
, false);
2345 tree_insert_offset(&ctl
->free_space_offset
,
2346 entry
->offset
, &entry
->offset_index
, bitmap
);
2348 cluster
->root
= RB_ROOT
;
2351 spin_unlock(&cluster
->lock
);
2352 btrfs_put_block_group(block_group
);
2356 static void __btrfs_remove_free_space_cache_locked(
2357 struct btrfs_free_space_ctl
*ctl
)
2359 struct btrfs_free_space
*info
;
2360 struct rb_node
*node
;
2362 while ((node
= rb_last(&ctl
->free_space_offset
)) != NULL
) {
2363 info
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
2364 if (!info
->bitmap
) {
2365 unlink_free_space(ctl
, info
);
2366 kmem_cache_free(btrfs_free_space_cachep
, info
);
2368 free_bitmap(ctl
, info
);
2370 if (need_resched()) {
2371 spin_unlock(&ctl
->tree_lock
);
2373 spin_lock(&ctl
->tree_lock
);
2378 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl
*ctl
)
2380 spin_lock(&ctl
->tree_lock
);
2381 __btrfs_remove_free_space_cache_locked(ctl
);
2382 spin_unlock(&ctl
->tree_lock
);
2385 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache
*block_group
)
2387 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2388 struct btrfs_free_cluster
*cluster
;
2389 struct list_head
*head
;
2391 spin_lock(&ctl
->tree_lock
);
2392 while ((head
= block_group
->cluster_list
.next
) !=
2393 &block_group
->cluster_list
) {
2394 cluster
= list_entry(head
, struct btrfs_free_cluster
,
2397 WARN_ON(cluster
->block_group
!= block_group
);
2398 __btrfs_return_cluster_to_free_space(block_group
, cluster
);
2399 if (need_resched()) {
2400 spin_unlock(&ctl
->tree_lock
);
2402 spin_lock(&ctl
->tree_lock
);
2405 __btrfs_remove_free_space_cache_locked(ctl
);
2406 spin_unlock(&ctl
->tree_lock
);
2410 u64
btrfs_find_space_for_alloc(struct btrfs_block_group_cache
*block_group
,
2411 u64 offset
, u64 bytes
, u64 empty_size
,
2412 u64
*max_extent_size
)
2414 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2415 struct btrfs_free_space
*entry
= NULL
;
2416 u64 bytes_search
= bytes
+ empty_size
;
2419 u64 align_gap_len
= 0;
2421 spin_lock(&ctl
->tree_lock
);
2422 entry
= find_free_space(ctl
, &offset
, &bytes_search
,
2423 block_group
->full_stripe_len
, max_extent_size
);
2428 if (entry
->bitmap
) {
2429 bitmap_clear_bits(ctl
, entry
, offset
, bytes
);
2431 free_bitmap(ctl
, entry
);
2433 unlink_free_space(ctl
, entry
);
2434 align_gap_len
= offset
- entry
->offset
;
2435 align_gap
= entry
->offset
;
2437 entry
->offset
= offset
+ bytes
;
2438 WARN_ON(entry
->bytes
< bytes
+ align_gap_len
);
2440 entry
->bytes
-= bytes
+ align_gap_len
;
2442 kmem_cache_free(btrfs_free_space_cachep
, entry
);
2444 link_free_space(ctl
, entry
);
2447 spin_unlock(&ctl
->tree_lock
);
2450 __btrfs_add_free_space(ctl
, align_gap
, align_gap_len
);
2455 * given a cluster, put all of its extents back into the free space
2456 * cache. If a block group is passed, this function will only free
2457 * a cluster that belongs to the passed block group.
2459 * Otherwise, it'll get a reference on the block group pointed to by the
2460 * cluster and remove the cluster from it.
2462 int btrfs_return_cluster_to_free_space(
2463 struct btrfs_block_group_cache
*block_group
,
2464 struct btrfs_free_cluster
*cluster
)
2466 struct btrfs_free_space_ctl
*ctl
;
2469 /* first, get a safe pointer to the block group */
2470 spin_lock(&cluster
->lock
);
2472 block_group
= cluster
->block_group
;
2474 spin_unlock(&cluster
->lock
);
2477 } else if (cluster
->block_group
!= block_group
) {
2478 /* someone else has already freed it don't redo their work */
2479 spin_unlock(&cluster
->lock
);
2482 atomic_inc(&block_group
->count
);
2483 spin_unlock(&cluster
->lock
);
2485 ctl
= block_group
->free_space_ctl
;
2487 /* now return any extents the cluster had on it */
2488 spin_lock(&ctl
->tree_lock
);
2489 ret
= __btrfs_return_cluster_to_free_space(block_group
, cluster
);
2490 spin_unlock(&ctl
->tree_lock
);
2492 /* finally drop our ref */
2493 btrfs_put_block_group(block_group
);
2497 static u64
btrfs_alloc_from_bitmap(struct btrfs_block_group_cache
*block_group
,
2498 struct btrfs_free_cluster
*cluster
,
2499 struct btrfs_free_space
*entry
,
2500 u64 bytes
, u64 min_start
,
2501 u64
*max_extent_size
)
2503 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2505 u64 search_start
= cluster
->window_start
;
2506 u64 search_bytes
= bytes
;
2509 search_start
= min_start
;
2510 search_bytes
= bytes
;
2512 err
= search_bitmap(ctl
, entry
, &search_start
, &search_bytes
);
2514 if (search_bytes
> *max_extent_size
)
2515 *max_extent_size
= search_bytes
;
2520 __bitmap_clear_bits(ctl
, entry
, ret
, bytes
);
2526 * given a cluster, try to allocate 'bytes' from it, returns 0
2527 * if it couldn't find anything suitably large, or a logical disk offset
2528 * if things worked out
2530 u64
btrfs_alloc_from_cluster(struct btrfs_block_group_cache
*block_group
,
2531 struct btrfs_free_cluster
*cluster
, u64 bytes
,
2532 u64 min_start
, u64
*max_extent_size
)
2534 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2535 struct btrfs_free_space
*entry
= NULL
;
2536 struct rb_node
*node
;
2539 spin_lock(&cluster
->lock
);
2540 if (bytes
> cluster
->max_size
)
2543 if (cluster
->block_group
!= block_group
)
2546 node
= rb_first(&cluster
->root
);
2550 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
2552 if (entry
->bytes
< bytes
&& entry
->bytes
> *max_extent_size
)
2553 *max_extent_size
= entry
->bytes
;
2555 if (entry
->bytes
< bytes
||
2556 (!entry
->bitmap
&& entry
->offset
< min_start
)) {
2557 node
= rb_next(&entry
->offset_index
);
2560 entry
= rb_entry(node
, struct btrfs_free_space
,
2565 if (entry
->bitmap
) {
2566 ret
= btrfs_alloc_from_bitmap(block_group
,
2567 cluster
, entry
, bytes
,
2568 cluster
->window_start
,
2571 node
= rb_next(&entry
->offset_index
);
2574 entry
= rb_entry(node
, struct btrfs_free_space
,
2578 cluster
->window_start
+= bytes
;
2580 ret
= entry
->offset
;
2582 entry
->offset
+= bytes
;
2583 entry
->bytes
-= bytes
;
2586 if (entry
->bytes
== 0)
2587 rb_erase(&entry
->offset_index
, &cluster
->root
);
2591 spin_unlock(&cluster
->lock
);
2596 spin_lock(&ctl
->tree_lock
);
2598 ctl
->free_space
-= bytes
;
2599 if (entry
->bytes
== 0) {
2600 ctl
->free_extents
--;
2601 if (entry
->bitmap
) {
2602 kfree(entry
->bitmap
);
2603 ctl
->total_bitmaps
--;
2604 ctl
->op
->recalc_thresholds(ctl
);
2606 kmem_cache_free(btrfs_free_space_cachep
, entry
);
2609 spin_unlock(&ctl
->tree_lock
);
2614 static int btrfs_bitmap_cluster(struct btrfs_block_group_cache
*block_group
,
2615 struct btrfs_free_space
*entry
,
2616 struct btrfs_free_cluster
*cluster
,
2617 u64 offset
, u64 bytes
,
2618 u64 cont1_bytes
, u64 min_bytes
)
2620 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2621 unsigned long next_zero
;
2623 unsigned long want_bits
;
2624 unsigned long min_bits
;
2625 unsigned long found_bits
;
2626 unsigned long start
= 0;
2627 unsigned long total_found
= 0;
2630 i
= offset_to_bit(entry
->offset
, ctl
->unit
,
2631 max_t(u64
, offset
, entry
->offset
));
2632 want_bits
= bytes_to_bits(bytes
, ctl
->unit
);
2633 min_bits
= bytes_to_bits(min_bytes
, ctl
->unit
);
2637 for_each_set_bit_from(i
, entry
->bitmap
, BITS_PER_BITMAP
) {
2638 next_zero
= find_next_zero_bit(entry
->bitmap
,
2639 BITS_PER_BITMAP
, i
);
2640 if (next_zero
- i
>= min_bits
) {
2641 found_bits
= next_zero
- i
;
2652 cluster
->max_size
= 0;
2655 total_found
+= found_bits
;
2657 if (cluster
->max_size
< found_bits
* ctl
->unit
)
2658 cluster
->max_size
= found_bits
* ctl
->unit
;
2660 if (total_found
< want_bits
|| cluster
->max_size
< cont1_bytes
) {
2665 cluster
->window_start
= start
* ctl
->unit
+ entry
->offset
;
2666 rb_erase(&entry
->offset_index
, &ctl
->free_space_offset
);
2667 ret
= tree_insert_offset(&cluster
->root
, entry
->offset
,
2668 &entry
->offset_index
, 1);
2669 ASSERT(!ret
); /* -EEXIST; Logic error */
2671 trace_btrfs_setup_cluster(block_group
, cluster
,
2672 total_found
* ctl
->unit
, 1);
2677 * This searches the block group for just extents to fill the cluster with.
2678 * Try to find a cluster with at least bytes total bytes, at least one
2679 * extent of cont1_bytes, and other clusters of at least min_bytes.
2682 setup_cluster_no_bitmap(struct btrfs_block_group_cache
*block_group
,
2683 struct btrfs_free_cluster
*cluster
,
2684 struct list_head
*bitmaps
, u64 offset
, u64 bytes
,
2685 u64 cont1_bytes
, u64 min_bytes
)
2687 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2688 struct btrfs_free_space
*first
= NULL
;
2689 struct btrfs_free_space
*entry
= NULL
;
2690 struct btrfs_free_space
*last
;
2691 struct rb_node
*node
;
2696 entry
= tree_search_offset(ctl
, offset
, 0, 1);
2701 * We don't want bitmaps, so just move along until we find a normal
2704 while (entry
->bitmap
|| entry
->bytes
< min_bytes
) {
2705 if (entry
->bitmap
&& list_empty(&entry
->list
))
2706 list_add_tail(&entry
->list
, bitmaps
);
2707 node
= rb_next(&entry
->offset_index
);
2710 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
2713 window_free
= entry
->bytes
;
2714 max_extent
= entry
->bytes
;
2718 for (node
= rb_next(&entry
->offset_index
); node
;
2719 node
= rb_next(&entry
->offset_index
)) {
2720 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
2722 if (entry
->bitmap
) {
2723 if (list_empty(&entry
->list
))
2724 list_add_tail(&entry
->list
, bitmaps
);
2728 if (entry
->bytes
< min_bytes
)
2732 window_free
+= entry
->bytes
;
2733 if (entry
->bytes
> max_extent
)
2734 max_extent
= entry
->bytes
;
2737 if (window_free
< bytes
|| max_extent
< cont1_bytes
)
2740 cluster
->window_start
= first
->offset
;
2742 node
= &first
->offset_index
;
2745 * now we've found our entries, pull them out of the free space
2746 * cache and put them into the cluster rbtree
2751 entry
= rb_entry(node
, struct btrfs_free_space
, offset_index
);
2752 node
= rb_next(&entry
->offset_index
);
2753 if (entry
->bitmap
|| entry
->bytes
< min_bytes
)
2756 rb_erase(&entry
->offset_index
, &ctl
->free_space_offset
);
2757 ret
= tree_insert_offset(&cluster
->root
, entry
->offset
,
2758 &entry
->offset_index
, 0);
2759 total_size
+= entry
->bytes
;
2760 ASSERT(!ret
); /* -EEXIST; Logic error */
2761 } while (node
&& entry
!= last
);
2763 cluster
->max_size
= max_extent
;
2764 trace_btrfs_setup_cluster(block_group
, cluster
, total_size
, 0);
2769 * This specifically looks for bitmaps that may work in the cluster, we assume
2770 * that we have already failed to find extents that will work.
2773 setup_cluster_bitmap(struct btrfs_block_group_cache
*block_group
,
2774 struct btrfs_free_cluster
*cluster
,
2775 struct list_head
*bitmaps
, u64 offset
, u64 bytes
,
2776 u64 cont1_bytes
, u64 min_bytes
)
2778 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2779 struct btrfs_free_space
*entry
;
2781 u64 bitmap_offset
= offset_to_bitmap(ctl
, offset
);
2783 if (ctl
->total_bitmaps
== 0)
2787 * The bitmap that covers offset won't be in the list unless offset
2788 * is just its start offset.
2790 entry
= list_first_entry(bitmaps
, struct btrfs_free_space
, list
);
2791 if (entry
->offset
!= bitmap_offset
) {
2792 entry
= tree_search_offset(ctl
, bitmap_offset
, 1, 0);
2793 if (entry
&& list_empty(&entry
->list
))
2794 list_add(&entry
->list
, bitmaps
);
2797 list_for_each_entry(entry
, bitmaps
, list
) {
2798 if (entry
->bytes
< bytes
)
2800 ret
= btrfs_bitmap_cluster(block_group
, entry
, cluster
, offset
,
2801 bytes
, cont1_bytes
, min_bytes
);
2807 * The bitmaps list has all the bitmaps that record free space
2808 * starting after offset, so no more search is required.
2814 * here we try to find a cluster of blocks in a block group. The goal
2815 * is to find at least bytes+empty_size.
2816 * We might not find them all in one contiguous area.
2818 * returns zero and sets up cluster if things worked out, otherwise
2819 * it returns -enospc
2821 int btrfs_find_space_cluster(struct btrfs_root
*root
,
2822 struct btrfs_block_group_cache
*block_group
,
2823 struct btrfs_free_cluster
*cluster
,
2824 u64 offset
, u64 bytes
, u64 empty_size
)
2826 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2827 struct btrfs_free_space
*entry
, *tmp
;
2834 * Choose the minimum extent size we'll require for this
2835 * cluster. For SSD_SPREAD, don't allow any fragmentation.
2836 * For metadata, allow allocates with smaller extents. For
2837 * data, keep it dense.
2839 if (btrfs_test_opt(root
, SSD_SPREAD
)) {
2840 cont1_bytes
= min_bytes
= bytes
+ empty_size
;
2841 } else if (block_group
->flags
& BTRFS_BLOCK_GROUP_METADATA
) {
2842 cont1_bytes
= bytes
;
2843 min_bytes
= block_group
->sectorsize
;
2845 cont1_bytes
= max(bytes
, (bytes
+ empty_size
) >> 2);
2846 min_bytes
= block_group
->sectorsize
;
2849 spin_lock(&ctl
->tree_lock
);
2852 * If we know we don't have enough space to make a cluster don't even
2853 * bother doing all the work to try and find one.
2855 if (ctl
->free_space
< bytes
) {
2856 spin_unlock(&ctl
->tree_lock
);
2860 spin_lock(&cluster
->lock
);
2862 /* someone already found a cluster, hooray */
2863 if (cluster
->block_group
) {
2868 trace_btrfs_find_cluster(block_group
, offset
, bytes
, empty_size
,
2871 INIT_LIST_HEAD(&bitmaps
);
2872 ret
= setup_cluster_no_bitmap(block_group
, cluster
, &bitmaps
, offset
,
2874 cont1_bytes
, min_bytes
);
2876 ret
= setup_cluster_bitmap(block_group
, cluster
, &bitmaps
,
2877 offset
, bytes
+ empty_size
,
2878 cont1_bytes
, min_bytes
);
2880 /* Clear our temporary list */
2881 list_for_each_entry_safe(entry
, tmp
, &bitmaps
, list
)
2882 list_del_init(&entry
->list
);
2885 atomic_inc(&block_group
->count
);
2886 list_add_tail(&cluster
->block_group_list
,
2887 &block_group
->cluster_list
);
2888 cluster
->block_group
= block_group
;
2890 trace_btrfs_failed_cluster_setup(block_group
);
2893 spin_unlock(&cluster
->lock
);
2894 spin_unlock(&ctl
->tree_lock
);
2900 * simple code to zero out a cluster
2902 void btrfs_init_free_cluster(struct btrfs_free_cluster
*cluster
)
2904 spin_lock_init(&cluster
->lock
);
2905 spin_lock_init(&cluster
->refill_lock
);
2906 cluster
->root
= RB_ROOT
;
2907 cluster
->max_size
= 0;
2908 INIT_LIST_HEAD(&cluster
->block_group_list
);
2909 cluster
->block_group
= NULL
;
2912 static int do_trimming(struct btrfs_block_group_cache
*block_group
,
2913 u64
*total_trimmed
, u64 start
, u64 bytes
,
2914 u64 reserved_start
, u64 reserved_bytes
)
2916 struct btrfs_space_info
*space_info
= block_group
->space_info
;
2917 struct btrfs_fs_info
*fs_info
= block_group
->fs_info
;
2922 spin_lock(&space_info
->lock
);
2923 spin_lock(&block_group
->lock
);
2924 if (!block_group
->ro
) {
2925 block_group
->reserved
+= reserved_bytes
;
2926 space_info
->bytes_reserved
+= reserved_bytes
;
2929 spin_unlock(&block_group
->lock
);
2930 spin_unlock(&space_info
->lock
);
2932 ret
= btrfs_error_discard_extent(fs_info
->extent_root
,
2933 start
, bytes
, &trimmed
);
2935 *total_trimmed
+= trimmed
;
2937 btrfs_add_free_space(block_group
, reserved_start
, reserved_bytes
);
2940 spin_lock(&space_info
->lock
);
2941 spin_lock(&block_group
->lock
);
2942 if (block_group
->ro
)
2943 space_info
->bytes_readonly
+= reserved_bytes
;
2944 block_group
->reserved
-= reserved_bytes
;
2945 space_info
->bytes_reserved
-= reserved_bytes
;
2946 spin_unlock(&space_info
->lock
);
2947 spin_unlock(&block_group
->lock
);
2953 static int trim_no_bitmap(struct btrfs_block_group_cache
*block_group
,
2954 u64
*total_trimmed
, u64 start
, u64 end
, u64 minlen
)
2956 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
2957 struct btrfs_free_space
*entry
;
2958 struct rb_node
*node
;
2964 while (start
< end
) {
2965 spin_lock(&ctl
->tree_lock
);
2967 if (ctl
->free_space
< minlen
) {
2968 spin_unlock(&ctl
->tree_lock
);
2972 entry
= tree_search_offset(ctl
, start
, 0, 1);
2974 spin_unlock(&ctl
->tree_lock
);
2979 while (entry
->bitmap
) {
2980 node
= rb_next(&entry
->offset_index
);
2982 spin_unlock(&ctl
->tree_lock
);
2985 entry
= rb_entry(node
, struct btrfs_free_space
,
2989 if (entry
->offset
>= end
) {
2990 spin_unlock(&ctl
->tree_lock
);
2994 extent_start
= entry
->offset
;
2995 extent_bytes
= entry
->bytes
;
2996 start
= max(start
, extent_start
);
2997 bytes
= min(extent_start
+ extent_bytes
, end
) - start
;
2998 if (bytes
< minlen
) {
2999 spin_unlock(&ctl
->tree_lock
);
3003 unlink_free_space(ctl
, entry
);
3004 kmem_cache_free(btrfs_free_space_cachep
, entry
);
3006 spin_unlock(&ctl
->tree_lock
);
3008 ret
= do_trimming(block_group
, total_trimmed
, start
, bytes
,
3009 extent_start
, extent_bytes
);
3015 if (fatal_signal_pending(current
)) {
3026 static int trim_bitmaps(struct btrfs_block_group_cache
*block_group
,
3027 u64
*total_trimmed
, u64 start
, u64 end
, u64 minlen
)
3029 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
3030 struct btrfs_free_space
*entry
;
3034 u64 offset
= offset_to_bitmap(ctl
, start
);
3036 while (offset
< end
) {
3037 bool next_bitmap
= false;
3039 spin_lock(&ctl
->tree_lock
);
3041 if (ctl
->free_space
< minlen
) {
3042 spin_unlock(&ctl
->tree_lock
);
3046 entry
= tree_search_offset(ctl
, offset
, 1, 0);
3048 spin_unlock(&ctl
->tree_lock
);
3054 ret2
= search_bitmap(ctl
, entry
, &start
, &bytes
);
3055 if (ret2
|| start
>= end
) {
3056 spin_unlock(&ctl
->tree_lock
);
3061 bytes
= min(bytes
, end
- start
);
3062 if (bytes
< minlen
) {
3063 spin_unlock(&ctl
->tree_lock
);
3067 bitmap_clear_bits(ctl
, entry
, start
, bytes
);
3068 if (entry
->bytes
== 0)
3069 free_bitmap(ctl
, entry
);
3071 spin_unlock(&ctl
->tree_lock
);
3073 ret
= do_trimming(block_group
, total_trimmed
, start
, bytes
,
3079 offset
+= BITS_PER_BITMAP
* ctl
->unit
;
3082 if (start
>= offset
+ BITS_PER_BITMAP
* ctl
->unit
)
3083 offset
+= BITS_PER_BITMAP
* ctl
->unit
;
3086 if (fatal_signal_pending(current
)) {
3097 int btrfs_trim_block_group(struct btrfs_block_group_cache
*block_group
,
3098 u64
*trimmed
, u64 start
, u64 end
, u64 minlen
)
3104 ret
= trim_no_bitmap(block_group
, trimmed
, start
, end
, minlen
);
3108 ret
= trim_bitmaps(block_group
, trimmed
, start
, end
, minlen
);
3114 * Find the left-most item in the cache tree, and then return the
3115 * smallest inode number in the item.
3117 * Note: the returned inode number may not be the smallest one in
3118 * the tree, if the left-most item is a bitmap.
3120 u64
btrfs_find_ino_for_alloc(struct btrfs_root
*fs_root
)
3122 struct btrfs_free_space_ctl
*ctl
= fs_root
->free_ino_ctl
;
3123 struct btrfs_free_space
*entry
= NULL
;
3126 spin_lock(&ctl
->tree_lock
);
3128 if (RB_EMPTY_ROOT(&ctl
->free_space_offset
))
3131 entry
= rb_entry(rb_first(&ctl
->free_space_offset
),
3132 struct btrfs_free_space
, offset_index
);
3134 if (!entry
->bitmap
) {
3135 ino
= entry
->offset
;
3137 unlink_free_space(ctl
, entry
);
3141 kmem_cache_free(btrfs_free_space_cachep
, entry
);
3143 link_free_space(ctl
, entry
);
3149 ret
= search_bitmap(ctl
, entry
, &offset
, &count
);
3150 /* Logic error; Should be empty if it can't find anything */
3154 bitmap_clear_bits(ctl
, entry
, offset
, 1);
3155 if (entry
->bytes
== 0)
3156 free_bitmap(ctl
, entry
);
3159 spin_unlock(&ctl
->tree_lock
);
3164 struct inode
*lookup_free_ino_inode(struct btrfs_root
*root
,
3165 struct btrfs_path
*path
)
3167 struct inode
*inode
= NULL
;
3169 spin_lock(&root
->ino_cache_lock
);
3170 if (root
->ino_cache_inode
)
3171 inode
= igrab(root
->ino_cache_inode
);
3172 spin_unlock(&root
->ino_cache_lock
);
3176 inode
= __lookup_free_space_inode(root
, path
, 0);
3180 spin_lock(&root
->ino_cache_lock
);
3181 if (!btrfs_fs_closing(root
->fs_info
))
3182 root
->ino_cache_inode
= igrab(inode
);
3183 spin_unlock(&root
->ino_cache_lock
);
3188 int create_free_ino_inode(struct btrfs_root
*root
,
3189 struct btrfs_trans_handle
*trans
,
3190 struct btrfs_path
*path
)
3192 return __create_free_space_inode(root
, trans
, path
,
3193 BTRFS_FREE_INO_OBJECTID
, 0);
3196 int load_free_ino_cache(struct btrfs_fs_info
*fs_info
, struct btrfs_root
*root
)
3198 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
3199 struct btrfs_path
*path
;
3200 struct inode
*inode
;
3202 u64 root_gen
= btrfs_root_generation(&root
->root_item
);
3204 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
3208 * If we're unmounting then just return, since this does a search on the
3209 * normal root and not the commit root and we could deadlock.
3211 if (btrfs_fs_closing(fs_info
))
3214 path
= btrfs_alloc_path();
3218 inode
= lookup_free_ino_inode(root
, path
);
3222 if (root_gen
!= BTRFS_I(inode
)->generation
)
3225 ret
= __load_free_space_cache(root
, inode
, ctl
, path
, 0);
3229 "failed to load free ino cache for root %llu",
3230 root
->root_key
.objectid
);
3234 btrfs_free_path(path
);
3238 int btrfs_write_out_ino_cache(struct btrfs_root
*root
,
3239 struct btrfs_trans_handle
*trans
,
3240 struct btrfs_path
*path
,
3241 struct inode
*inode
)
3243 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
3246 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
3249 ret
= __btrfs_write_out_cache(root
, inode
, ctl
, NULL
, trans
, path
, 0);
3251 btrfs_delalloc_release_metadata(inode
, inode
->i_size
);
3253 btrfs_err(root
->fs_info
,
3254 "failed to write free ino cache for root %llu",
3255 root
->root_key
.objectid
);
3262 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
3264 * Use this if you need to make a bitmap or extent entry specifically, it
3265 * doesn't do any of the merging that add_free_space does, this acts a lot like
3266 * how the free space cache loading stuff works, so you can get really weird
3269 int test_add_free_space_entry(struct btrfs_block_group_cache
*cache
,
3270 u64 offset
, u64 bytes
, bool bitmap
)
3272 struct btrfs_free_space_ctl
*ctl
= cache
->free_space_ctl
;
3273 struct btrfs_free_space
*info
= NULL
, *bitmap_info
;
3280 info
= kmem_cache_zalloc(btrfs_free_space_cachep
, GFP_NOFS
);
3286 spin_lock(&ctl
->tree_lock
);
3287 info
->offset
= offset
;
3288 info
->bytes
= bytes
;
3289 ret
= link_free_space(ctl
, info
);
3290 spin_unlock(&ctl
->tree_lock
);
3292 kmem_cache_free(btrfs_free_space_cachep
, info
);
3297 map
= kzalloc(PAGE_CACHE_SIZE
, GFP_NOFS
);
3299 kmem_cache_free(btrfs_free_space_cachep
, info
);
3304 spin_lock(&ctl
->tree_lock
);
3305 bitmap_info
= tree_search_offset(ctl
, offset_to_bitmap(ctl
, offset
),
3310 add_new_bitmap(ctl
, info
, offset
);
3315 bytes_added
= add_bytes_to_bitmap(ctl
, bitmap_info
, offset
, bytes
);
3316 bytes
-= bytes_added
;
3317 offset
+= bytes_added
;
3318 spin_unlock(&ctl
->tree_lock
);
3324 kmem_cache_free(btrfs_free_space_cachep
, info
);
3331 * Checks to see if the given range is in the free space cache. This is really
3332 * just used to check the absence of space, so if there is free space in the
3333 * range at all we will return 1.
3335 int test_check_exists(struct btrfs_block_group_cache
*cache
,
3336 u64 offset
, u64 bytes
)
3338 struct btrfs_free_space_ctl
*ctl
= cache
->free_space_ctl
;
3339 struct btrfs_free_space
*info
;
3342 spin_lock(&ctl
->tree_lock
);
3343 info
= tree_search_offset(ctl
, offset
, 0, 0);
3345 info
= tree_search_offset(ctl
, offset_to_bitmap(ctl
, offset
),
3353 u64 bit_off
, bit_bytes
;
3355 struct btrfs_free_space
*tmp
;
3358 bit_bytes
= ctl
->unit
;
3359 ret
= search_bitmap(ctl
, info
, &bit_off
, &bit_bytes
);
3361 if (bit_off
== offset
) {
3364 } else if (bit_off
> offset
&&
3365 offset
+ bytes
> bit_off
) {
3371 n
= rb_prev(&info
->offset_index
);
3373 tmp
= rb_entry(n
, struct btrfs_free_space
,
3375 if (tmp
->offset
+ tmp
->bytes
< offset
)
3377 if (offset
+ bytes
< tmp
->offset
) {
3378 n
= rb_prev(&info
->offset_index
);
3385 n
= rb_next(&info
->offset_index
);
3387 tmp
= rb_entry(n
, struct btrfs_free_space
,
3389 if (offset
+ bytes
< tmp
->offset
)
3391 if (tmp
->offset
+ tmp
->bytes
< offset
) {
3392 n
= rb_next(&info
->offset_index
);
3403 if (info
->offset
== offset
) {
3408 if (offset
> info
->offset
&& offset
< info
->offset
+ info
->bytes
)
3411 spin_unlock(&ctl
->tree_lock
);
3414 #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */