2 * Copyright (C) 2007 Oracle. 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/delay.h>
20 #include <linux/kthread.h>
21 #include <linux/pagemap.h>
25 #include "free-space-cache.h"
26 #include "inode-map.h"
27 #include "transaction.h"
29 static int caching_kthread(void *data
)
31 struct btrfs_root
*root
= data
;
32 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
33 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
35 struct btrfs_path
*path
;
36 struct extent_buffer
*leaf
;
41 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
44 path
= btrfs_alloc_path();
48 /* Since the commit root is read-only, we can safely skip locking. */
49 path
->skip_locking
= 1;
50 path
->search_commit_root
= 1;
53 key
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
55 key
.type
= BTRFS_INODE_ITEM_KEY
;
57 /* need to make sure the commit_root doesn't disappear */
58 down_read(&fs_info
->commit_root_sem
);
60 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
65 if (btrfs_fs_closing(fs_info
))
68 leaf
= path
->nodes
[0];
69 slot
= path
->slots
[0];
70 if (slot
>= btrfs_header_nritems(leaf
)) {
71 ret
= btrfs_next_leaf(root
, path
);
78 btrfs_transaction_in_commit(fs_info
)) {
79 leaf
= path
->nodes
[0];
81 if (WARN_ON(btrfs_header_nritems(leaf
) == 0))
85 * Save the key so we can advances forward
88 btrfs_item_key_to_cpu(leaf
, &key
, 0);
89 btrfs_release_path(path
);
90 root
->cache_progress
= last
;
91 up_read(&fs_info
->commit_root_sem
);
98 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
100 if (key
.type
!= BTRFS_INODE_ITEM_KEY
)
103 if (key
.objectid
>= root
->highest_objectid
)
106 if (last
!= (u64
)-1 && last
+ 1 != key
.objectid
) {
107 __btrfs_add_free_space(ctl
, last
+ 1,
108 key
.objectid
- last
- 1);
109 wake_up(&root
->cache_wait
);
117 if (last
< root
->highest_objectid
- 1) {
118 __btrfs_add_free_space(ctl
, last
+ 1,
119 root
->highest_objectid
- last
- 1);
122 spin_lock(&root
->cache_lock
);
123 root
->cached
= BTRFS_CACHE_FINISHED
;
124 spin_unlock(&root
->cache_lock
);
126 root
->cache_progress
= (u64
)-1;
127 btrfs_unpin_free_ino(root
);
129 wake_up(&root
->cache_wait
);
130 up_read(&fs_info
->commit_root_sem
);
132 btrfs_free_path(path
);
137 static void start_caching(struct btrfs_root
*root
)
139 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
140 struct task_struct
*tsk
;
144 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
147 spin_lock(&root
->cache_lock
);
148 if (root
->cached
!= BTRFS_CACHE_NO
) {
149 spin_unlock(&root
->cache_lock
);
153 root
->cached
= BTRFS_CACHE_STARTED
;
154 spin_unlock(&root
->cache_lock
);
156 ret
= load_free_ino_cache(root
->fs_info
, root
);
158 spin_lock(&root
->cache_lock
);
159 root
->cached
= BTRFS_CACHE_FINISHED
;
160 spin_unlock(&root
->cache_lock
);
165 * It can be quite time-consuming to fill the cache by searching
166 * through the extent tree, and this can keep ino allocation path
167 * waiting. Therefore at start we quickly find out the highest
168 * inode number and we know we can use inode numbers which fall in
169 * [highest_ino + 1, BTRFS_LAST_FREE_OBJECTID].
171 ret
= btrfs_find_free_objectid(root
, &objectid
);
172 if (!ret
&& objectid
<= BTRFS_LAST_FREE_OBJECTID
) {
173 __btrfs_add_free_space(ctl
, objectid
,
174 BTRFS_LAST_FREE_OBJECTID
- objectid
+ 1);
177 tsk
= kthread_run(caching_kthread
, root
, "btrfs-ino-cache-%llu\n",
178 root
->root_key
.objectid
);
180 btrfs_warn(root
->fs_info
, "failed to start inode caching task");
181 btrfs_clear_and_info(root
, CHANGE_INODE_CACHE
,
182 "disabling inode map caching");
186 int btrfs_find_free_ino(struct btrfs_root
*root
, u64
*objectid
)
188 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
189 return btrfs_find_free_objectid(root
, objectid
);
192 *objectid
= btrfs_find_ino_for_alloc(root
);
199 wait_event(root
->cache_wait
,
200 root
->cached
== BTRFS_CACHE_FINISHED
||
201 root
->free_ino_ctl
->free_space
> 0);
203 if (root
->cached
== BTRFS_CACHE_FINISHED
&&
204 root
->free_ino_ctl
->free_space
== 0)
210 void btrfs_return_ino(struct btrfs_root
*root
, u64 objectid
)
212 struct btrfs_free_space_ctl
*pinned
= root
->free_ino_pinned
;
214 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
217 if (root
->cached
== BTRFS_CACHE_FINISHED
) {
218 __btrfs_add_free_space(pinned
, objectid
, 1);
220 down_write(&root
->fs_info
->commit_root_sem
);
221 spin_lock(&root
->cache_lock
);
222 if (root
->cached
== BTRFS_CACHE_FINISHED
) {
223 spin_unlock(&root
->cache_lock
);
224 up_write(&root
->fs_info
->commit_root_sem
);
227 spin_unlock(&root
->cache_lock
);
231 __btrfs_add_free_space(pinned
, objectid
, 1);
233 up_write(&root
->fs_info
->commit_root_sem
);
238 * When a transaction is committed, we'll move those inode numbers which
239 * are smaller than root->cache_progress from pinned tree to free_ino tree,
240 * and others will just be dropped, because the commit root we were
241 * searching has changed.
243 * Must be called with root->fs_info->commit_root_sem held
245 void btrfs_unpin_free_ino(struct btrfs_root
*root
)
247 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
248 struct rb_root
*rbroot
= &root
->free_ino_pinned
->free_space_offset
;
249 struct btrfs_free_space
*info
;
253 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
257 n
= rb_first(rbroot
);
261 info
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
262 BUG_ON(info
->bitmap
); /* Logic error */
264 if (info
->offset
> root
->cache_progress
)
266 else if (info
->offset
+ info
->bytes
> root
->cache_progress
)
267 count
= root
->cache_progress
- info
->offset
+ 1;
271 __btrfs_add_free_space(ctl
, info
->offset
, count
);
273 rb_erase(&info
->offset_index
, rbroot
);
278 #define INIT_THRESHOLD (((1024 * 32) / 2) / sizeof(struct btrfs_free_space))
279 #define INODES_PER_BITMAP (PAGE_CACHE_SIZE * 8)
282 * The goal is to keep the memory used by the free_ino tree won't
283 * exceed the memory if we use bitmaps only.
285 static void recalculate_thresholds(struct btrfs_free_space_ctl
*ctl
)
287 struct btrfs_free_space
*info
;
292 n
= rb_last(&ctl
->free_space_offset
);
294 ctl
->extents_thresh
= INIT_THRESHOLD
;
297 info
= rb_entry(n
, struct btrfs_free_space
, offset_index
);
300 * Find the maximum inode number in the filesystem. Note we
301 * ignore the fact that this can be a bitmap, because we are
302 * not doing precise calculation.
304 max_ino
= info
->bytes
- 1;
306 max_bitmaps
= ALIGN(max_ino
, INODES_PER_BITMAP
) / INODES_PER_BITMAP
;
307 if (max_bitmaps
<= ctl
->total_bitmaps
) {
308 ctl
->extents_thresh
= 0;
312 ctl
->extents_thresh
= (max_bitmaps
- ctl
->total_bitmaps
) *
313 PAGE_CACHE_SIZE
/ sizeof(*info
);
317 * We don't fall back to bitmap, if we are below the extents threshold
318 * or this chunk of inode numbers is a big one.
320 static bool use_bitmap(struct btrfs_free_space_ctl
*ctl
,
321 struct btrfs_free_space
*info
)
323 if (ctl
->free_extents
< ctl
->extents_thresh
||
324 info
->bytes
> INODES_PER_BITMAP
/ 10)
330 static struct btrfs_free_space_op free_ino_op
= {
331 .recalc_thresholds
= recalculate_thresholds
,
332 .use_bitmap
= use_bitmap
,
335 static void pinned_recalc_thresholds(struct btrfs_free_space_ctl
*ctl
)
339 static bool pinned_use_bitmap(struct btrfs_free_space_ctl
*ctl
,
340 struct btrfs_free_space
*info
)
343 * We always use extents for two reasons:
345 * - The pinned tree is only used during the process of caching
347 * - Make code simpler. See btrfs_unpin_free_ino().
352 static struct btrfs_free_space_op pinned_free_ino_op
= {
353 .recalc_thresholds
= pinned_recalc_thresholds
,
354 .use_bitmap
= pinned_use_bitmap
,
357 void btrfs_init_free_ino_ctl(struct btrfs_root
*root
)
359 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
360 struct btrfs_free_space_ctl
*pinned
= root
->free_ino_pinned
;
362 spin_lock_init(&ctl
->tree_lock
);
366 ctl
->op
= &free_ino_op
;
369 * Initially we allow to use 16K of ram to cache chunks of
370 * inode numbers before we resort to bitmaps. This is somewhat
371 * arbitrary, but it will be adjusted in runtime.
373 ctl
->extents_thresh
= INIT_THRESHOLD
;
375 spin_lock_init(&pinned
->tree_lock
);
378 pinned
->private = NULL
;
379 pinned
->extents_thresh
= 0;
380 pinned
->op
= &pinned_free_ino_op
;
383 int btrfs_save_ino_cache(struct btrfs_root
*root
,
384 struct btrfs_trans_handle
*trans
)
386 struct btrfs_free_space_ctl
*ctl
= root
->free_ino_ctl
;
387 struct btrfs_path
*path
;
389 struct btrfs_block_rsv
*rsv
;
396 /* only fs tree and subvol/snap needs ino cache */
397 if (root
->root_key
.objectid
!= BTRFS_FS_TREE_OBJECTID
&&
398 (root
->root_key
.objectid
< BTRFS_FIRST_FREE_OBJECTID
||
399 root
->root_key
.objectid
> BTRFS_LAST_FREE_OBJECTID
))
402 /* Don't save inode cache if we are deleting this root */
403 if (btrfs_root_refs(&root
->root_item
) == 0)
406 if (!btrfs_test_opt(root
, INODE_MAP_CACHE
))
409 path
= btrfs_alloc_path();
413 rsv
= trans
->block_rsv
;
414 trans
->block_rsv
= &root
->fs_info
->trans_block_rsv
;
416 num_bytes
= trans
->bytes_reserved
;
418 * 1 item for inode item insertion if need
419 * 4 items for inode item update (in the worst case)
420 * 1 items for slack space if we need do truncation
421 * 1 item for free space object
422 * 3 items for pre-allocation
424 trans
->bytes_reserved
= btrfs_calc_trans_metadata_size(root
, 10);
425 ret
= btrfs_block_rsv_add(root
, trans
->block_rsv
,
426 trans
->bytes_reserved
,
427 BTRFS_RESERVE_NO_FLUSH
);
430 trace_btrfs_space_reservation(root
->fs_info
, "ino_cache",
431 trans
->transid
, trans
->bytes_reserved
, 1);
433 inode
= lookup_free_ino_inode(root
, path
);
434 if (IS_ERR(inode
) && (PTR_ERR(inode
) != -ENOENT
|| retry
)) {
435 ret
= PTR_ERR(inode
);
440 BUG_ON(retry
); /* Logic error */
443 ret
= create_free_ino_inode(root
, trans
, path
);
449 BTRFS_I(inode
)->generation
= 0;
450 ret
= btrfs_update_inode(trans
, root
, inode
);
452 btrfs_abort_transaction(trans
, root
, ret
);
456 if (i_size_read(inode
) > 0) {
457 ret
= btrfs_truncate_free_space_cache(root
, trans
, inode
);
460 btrfs_abort_transaction(trans
, root
, ret
);
465 spin_lock(&root
->cache_lock
);
466 if (root
->cached
!= BTRFS_CACHE_FINISHED
) {
468 spin_unlock(&root
->cache_lock
);
471 spin_unlock(&root
->cache_lock
);
473 spin_lock(&ctl
->tree_lock
);
474 prealloc
= sizeof(struct btrfs_free_space
) * ctl
->free_extents
;
475 prealloc
= ALIGN(prealloc
, PAGE_CACHE_SIZE
);
476 prealloc
+= ctl
->total_bitmaps
* PAGE_CACHE_SIZE
;
477 spin_unlock(&ctl
->tree_lock
);
479 /* Just to make sure we have enough space */
480 prealloc
+= 8 * PAGE_CACHE_SIZE
;
482 ret
= btrfs_delalloc_reserve_space(inode
, prealloc
);
486 ret
= btrfs_prealloc_file_range_trans(inode
, trans
, 0, 0, prealloc
,
487 prealloc
, prealloc
, &alloc_hint
);
489 btrfs_delalloc_release_space(inode
, prealloc
);
492 btrfs_free_reserved_data_space(inode
, prealloc
);
494 ret
= btrfs_write_out_ino_cache(root
, trans
, path
, inode
);
498 trace_btrfs_space_reservation(root
->fs_info
, "ino_cache",
499 trans
->transid
, trans
->bytes_reserved
, 0);
500 btrfs_block_rsv_release(root
, trans
->block_rsv
, trans
->bytes_reserved
);
502 trans
->block_rsv
= rsv
;
503 trans
->bytes_reserved
= num_bytes
;
505 btrfs_free_path(path
);
509 static int btrfs_find_highest_objectid(struct btrfs_root
*root
, u64
*objectid
)
511 struct btrfs_path
*path
;
513 struct extent_buffer
*l
;
514 struct btrfs_key search_key
;
515 struct btrfs_key found_key
;
518 path
= btrfs_alloc_path();
522 search_key
.objectid
= BTRFS_LAST_FREE_OBJECTID
;
523 search_key
.type
= -1;
524 search_key
.offset
= (u64
)-1;
525 ret
= btrfs_search_slot(NULL
, root
, &search_key
, path
, 0, 0);
528 BUG_ON(ret
== 0); /* Corruption */
529 if (path
->slots
[0] > 0) {
530 slot
= path
->slots
[0] - 1;
532 btrfs_item_key_to_cpu(l
, &found_key
, slot
);
533 *objectid
= max_t(u64
, found_key
.objectid
,
534 BTRFS_FIRST_FREE_OBJECTID
- 1);
536 *objectid
= BTRFS_FIRST_FREE_OBJECTID
- 1;
540 btrfs_free_path(path
);
544 int btrfs_find_free_objectid(struct btrfs_root
*root
, u64
*objectid
)
547 mutex_lock(&root
->objectid_mutex
);
549 if (unlikely(root
->highest_objectid
< BTRFS_FIRST_FREE_OBJECTID
)) {
550 ret
= btrfs_find_highest_objectid(root
,
551 &root
->highest_objectid
);
556 if (unlikely(root
->highest_objectid
>= BTRFS_LAST_FREE_OBJECTID
)) {
561 *objectid
= ++root
->highest_objectid
;
564 mutex_unlock(&root
->objectid_mutex
);