aboutsummaryrefslogtreecommitdiffstats
path: root/fs
diff options
context:
space:
mode:
authorYan Zheng <zheng.yan@oracle.com>2008-07-28 15:32:19 -0400
committerChris Mason <chris.mason@oracle.com>2008-09-25 11:04:05 -0400
commit31153d81284934601d08110ac7698fd9a535e4c0 (patch)
tree38f873fea3012a58d2a8f4d439a9546443617878 /fs
parent3a115f520f391b4ab14041bdd6eedb370d944fa6 (diff)
Btrfs: Add a leaf reference cache
Much of the IO done while dropping snapshots is done looking up leaves in the filesystem trees to see if they point to any extents and to drop the references on any extents found. This creates a cache so that IO isn't required. Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs')
-rw-r--r--fs/btrfs/Makefile3
-rw-r--r--fs/btrfs/ctree.c4
-rw-r--r--fs/btrfs/ctree.h8
-rw-r--r--fs/btrfs/disk-io.c14
-rw-r--r--fs/btrfs/extent-tree.c115
-rw-r--r--fs/btrfs/ref-cache.c226
-rw-r--r--fs/btrfs/ref-cache.h72
-rw-r--r--fs/btrfs/transaction.c67
8 files changed, 476 insertions, 33 deletions
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 5a0fd7b0e3e7..a4b38177abdb 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -6,7 +6,8 @@ btrfs-y := super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.o \
6 hash.o file-item.o inode-item.o inode-map.o disk-io.o \ 6 hash.o file-item.o inode-item.o inode-map.o disk-io.o \
7 transaction.o bit-radix.o inode.o file.o tree-defrag.o \ 7 transaction.o bit-radix.o inode.o file.o tree-defrag.o \
8 extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \ 8 extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
9 extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o 9 extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
10 ref-cache.o
10 11
11btrfs-$(CONFIG_FS_POSIX_ACL) += acl.o 12btrfs-$(CONFIG_FS_POSIX_ACL) += acl.o
12else 13else
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index ab4ac0365c7f..245eb00435dd 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -165,7 +165,7 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
165 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); 165 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
166 166
167 WARN_ON(btrfs_header_generation(buf) > trans->transid); 167 WARN_ON(btrfs_header_generation(buf) > trans->transid);
168 ret = btrfs_inc_ref(trans, new_root, buf); 168 ret = btrfs_inc_ref(trans, new_root, buf, 0);
169 kfree(new_root); 169 kfree(new_root);
170 170
171 if (ret) 171 if (ret)
@@ -232,7 +232,7 @@ int __btrfs_cow_block(struct btrfs_trans_handle *trans,
232 WARN_ON(btrfs_header_generation(buf) > trans->transid); 232 WARN_ON(btrfs_header_generation(buf) > trans->transid);
233 if (btrfs_header_generation(buf) != trans->transid) { 233 if (btrfs_header_generation(buf) != trans->transid) {
234 different_trans = 1; 234 different_trans = 1;
235 ret = btrfs_inc_ref(trans, root, buf); 235 ret = btrfs_inc_ref(trans, root, buf, 1);
236 if (ret) 236 if (ret)
237 return ret; 237 return ret;
238 } else { 238 } else {
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 07d321552dbe..34ed23d64eb5 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -592,6 +592,10 @@ struct btrfs_fs_info {
592 u64 last_alloc; 592 u64 last_alloc;
593 u64 last_data_alloc; 593 u64 last_data_alloc;
594 594
595 spinlock_t ref_cache_lock;
596 u64 total_ref_cache_size;
597 u64 running_ref_cache_size;
598
595 u64 avail_data_alloc_bits; 599 u64 avail_data_alloc_bits;
596 u64 avail_metadata_alloc_bits; 600 u64 avail_metadata_alloc_bits;
597 u64 avail_system_alloc_bits; 601 u64 avail_system_alloc_bits;
@@ -613,6 +617,8 @@ struct btrfs_root {
613 spinlock_t node_lock; 617 spinlock_t node_lock;
614 618
615 struct extent_buffer *commit_root; 619 struct extent_buffer *commit_root;
620 struct btrfs_leaf_ref_tree *ref_tree;
621
616 struct btrfs_root_item root_item; 622 struct btrfs_root_item root_item;
617 struct btrfs_key root_key; 623 struct btrfs_key root_key;
618 struct btrfs_fs_info *fs_info; 624 struct btrfs_fs_info *fs_info;
@@ -1430,7 +1436,7 @@ int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
1430 u64 search_end, struct btrfs_key *ins, 1436 u64 search_end, struct btrfs_key *ins,
1431 u64 data); 1437 u64 data);
1432int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1438int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1433 struct extent_buffer *buf); 1439 struct extent_buffer *buf, int cache_ref);
1434int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root 1440int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1435 *root, u64 bytenr, u64 num_bytes, 1441 *root, u64 bytenr, u64 num_bytes,
1436 u64 root_objectid, u64 ref_generation, 1442 u64 root_objectid, u64 ref_generation,
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index d60923967347..4f0e1d06c384 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -716,6 +716,7 @@ static int __setup_root(u32 nodesize, u32 leafsize, u32 sectorsize,
716 root->node = NULL; 716 root->node = NULL;
717 root->inode = NULL; 717 root->inode = NULL;
718 root->commit_root = NULL; 718 root->commit_root = NULL;
719 root->ref_tree = NULL;
719 root->sectorsize = sectorsize; 720 root->sectorsize = sectorsize;
720 root->nodesize = nodesize; 721 root->nodesize = nodesize;
721 root->leafsize = leafsize; 722 root->leafsize = leafsize;
@@ -1165,12 +1166,19 @@ static int transaction_kthread(void *arg)
1165 vfs_check_frozen(root->fs_info->sb, SB_FREEZE_WRITE); 1166 vfs_check_frozen(root->fs_info->sb, SB_FREEZE_WRITE);
1166 mutex_lock(&root->fs_info->transaction_kthread_mutex); 1167 mutex_lock(&root->fs_info->transaction_kthread_mutex);
1167 1168
1169 printk("btrfs: total reference cache size %Lu\n",
1170 root->fs_info->total_ref_cache_size);
1171
1168 mutex_lock(&root->fs_info->trans_mutex); 1172 mutex_lock(&root->fs_info->trans_mutex);
1169 cur = root->fs_info->running_transaction; 1173 cur = root->fs_info->running_transaction;
1170 if (!cur) { 1174 if (!cur) {
1171 mutex_unlock(&root->fs_info->trans_mutex); 1175 mutex_unlock(&root->fs_info->trans_mutex);
1172 goto sleep; 1176 goto sleep;
1173 } 1177 }
1178
1179 printk("btrfs: running reference cache size %Lu\n",
1180 root->fs_info->running_ref_cache_size);
1181
1174 now = get_seconds(); 1182 now = get_seconds();
1175 if (now < cur->start_time || now - cur->start_time < 30) { 1183 if (now < cur->start_time || now - cur->start_time < 30) {
1176 mutex_unlock(&root->fs_info->trans_mutex); 1184 mutex_unlock(&root->fs_info->trans_mutex);
@@ -1233,6 +1241,7 @@ struct btrfs_root *open_ctree(struct super_block *sb,
1233 spin_lock_init(&fs_info->hash_lock); 1241 spin_lock_init(&fs_info->hash_lock);
1234 spin_lock_init(&fs_info->delalloc_lock); 1242 spin_lock_init(&fs_info->delalloc_lock);
1235 spin_lock_init(&fs_info->new_trans_lock); 1243 spin_lock_init(&fs_info->new_trans_lock);
1244 spin_lock_init(&fs_info->ref_cache_lock);
1236 1245
1237 init_completion(&fs_info->kobj_unregister); 1246 init_completion(&fs_info->kobj_unregister);
1238 fs_info->tree_root = tree_root; 1247 fs_info->tree_root = tree_root;
@@ -1699,6 +1708,11 @@ int close_ctree(struct btrfs_root *root)
1699 printk("btrfs: at unmount delalloc count %Lu\n", 1708 printk("btrfs: at unmount delalloc count %Lu\n",
1700 fs_info->delalloc_bytes); 1709 fs_info->delalloc_bytes);
1701 } 1710 }
1711 if (fs_info->total_ref_cache_size) {
1712 printk("btrfs: at umount reference cache size %Lu\n",
1713 fs_info->total_ref_cache_size);
1714 }
1715
1702 if (fs_info->extent_root->node) 1716 if (fs_info->extent_root->node)
1703 free_extent_buffer(fs_info->extent_root->node); 1717 free_extent_buffer(fs_info->extent_root->node);
1704 1718
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index cdfb4ff4b459..7b24f1511654 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -26,6 +26,7 @@
26#include "transaction.h" 26#include "transaction.h"
27#include "volumes.h" 27#include "volumes.h"
28#include "locking.h" 28#include "locking.h"
29#include "ref-cache.h"
29 30
30#define BLOCK_GROUP_DATA EXTENT_WRITEBACK 31#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
31#define BLOCK_GROUP_METADATA EXTENT_UPTODATE 32#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
@@ -927,7 +928,7 @@ out:
927} 928}
928 929
929int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root, 930int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
930 struct extent_buffer *buf) 931 struct extent_buffer *buf, int cache_ref)
931{ 932{
932 u64 bytenr; 933 u64 bytenr;
933 u32 nritems; 934 u32 nritems;
@@ -937,6 +938,7 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
937 int level; 938 int level;
938 int ret; 939 int ret;
939 int faili; 940 int faili;
941 int nr_file_extents = 0;
940 942
941 if (!root->ref_cows) 943 if (!root->ref_cows)
942 return 0; 944 return 0;
@@ -959,6 +961,9 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
959 if (disk_bytenr == 0) 961 if (disk_bytenr == 0)
960 continue; 962 continue;
961 963
964 if (buf != root->commit_root)
965 nr_file_extents++;
966
962 mutex_lock(&root->fs_info->alloc_mutex); 967 mutex_lock(&root->fs_info->alloc_mutex);
963 ret = __btrfs_inc_extent_ref(trans, root, disk_bytenr, 968 ret = __btrfs_inc_extent_ref(trans, root, disk_bytenr,
964 btrfs_file_extent_disk_num_bytes(buf, fi), 969 btrfs_file_extent_disk_num_bytes(buf, fi),
@@ -988,6 +993,53 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
988 } 993 }
989 } 994 }
990 } 995 }
996 /* cache orignal leaf block's references */
997 if (level == 0 && cache_ref && buf != root->commit_root) {
998 struct btrfs_leaf_ref *ref;
999 struct btrfs_extent_info *info;
1000
1001 ref = btrfs_alloc_leaf_ref(nr_file_extents);
1002 if (!ref) {
1003 WARN_ON(1);
1004 goto out;
1005 }
1006
1007 btrfs_item_key_to_cpu(buf, &ref->key, 0);
1008
1009 ref->bytenr = buf->start;
1010 ref->owner = btrfs_header_owner(buf);
1011 ref->generation = btrfs_header_generation(buf);
1012 ref->nritems = nr_file_extents;
1013 info = ref->extents;
1014
1015 for (i = 0; nr_file_extents > 0 && i < nritems; i++) {
1016 u64 disk_bytenr;
1017 btrfs_item_key_to_cpu(buf, &key, i);
1018 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1019 continue;
1020 fi = btrfs_item_ptr(buf, i,
1021 struct btrfs_file_extent_item);
1022 if (btrfs_file_extent_type(buf, fi) ==
1023 BTRFS_FILE_EXTENT_INLINE)
1024 continue;
1025 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1026 if (disk_bytenr == 0)
1027 continue;
1028
1029 info->bytenr = disk_bytenr;
1030 info->num_bytes =
1031 btrfs_file_extent_disk_num_bytes(buf, fi);
1032 info->objectid = key.objectid;
1033 info->offset = key.offset;
1034 info++;
1035 }
1036
1037 BUG_ON(!root->ref_tree);
1038 ret = btrfs_add_leaf_ref(root, ref);
1039 WARN_ON(ret);
1040 btrfs_free_leaf_ref(ref);
1041 }
1042out:
991 return 0; 1043 return 0;
992fail: 1044fail:
993 WARN_ON(1); 1045 WARN_ON(1);
@@ -2215,9 +2267,9 @@ struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2215 return buf; 2267 return buf;
2216} 2268}
2217 2269
2218static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans, 2270static int noinline drop_leaf_ref_no_cache(struct btrfs_trans_handle *trans,
2219 struct btrfs_root *root, 2271 struct btrfs_root *root,
2220 struct extent_buffer *leaf) 2272 struct extent_buffer *leaf)
2221{ 2273{
2222 u64 leaf_owner; 2274 u64 leaf_owner;
2223 u64 leaf_generation; 2275 u64 leaf_generation;
@@ -2266,6 +2318,30 @@ static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2266 return 0; 2318 return 0;
2267} 2319}
2268 2320
2321static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2322 struct btrfs_root *root,
2323 struct btrfs_leaf_ref *ref)
2324{
2325 int i;
2326 int ret;
2327 struct btrfs_extent_info *info = ref->extents;
2328
2329 mutex_unlock(&root->fs_info->alloc_mutex);
2330 for (i = 0; i < ref->nritems; i++) {
2331 mutex_lock(&root->fs_info->alloc_mutex);
2332 ret = __btrfs_free_extent(trans, root,
2333 info->bytenr, info->num_bytes,
2334 ref->owner, ref->generation,
2335 info->objectid, info->offset, 0);
2336 mutex_unlock(&root->fs_info->alloc_mutex);
2337 BUG_ON(ret);
2338 info++;
2339 }
2340 mutex_lock(&root->fs_info->alloc_mutex);
2341
2342 return 0;
2343}
2344
2269static void noinline reada_walk_down(struct btrfs_root *root, 2345static void noinline reada_walk_down(struct btrfs_root *root,
2270 struct extent_buffer *node, 2346 struct extent_buffer *node,
2271 int slot) 2347 int slot)
@@ -2341,6 +2417,7 @@ static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2341 struct extent_buffer *next; 2417 struct extent_buffer *next;
2342 struct extent_buffer *cur; 2418 struct extent_buffer *cur;
2343 struct extent_buffer *parent; 2419 struct extent_buffer *parent;
2420 struct btrfs_leaf_ref *ref;
2344 u32 blocksize; 2421 u32 blocksize;
2345 int ret; 2422 int ret;
2346 u32 refs; 2423 u32 refs;
@@ -2370,7 +2447,7 @@ static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2370 btrfs_header_nritems(cur)) 2447 btrfs_header_nritems(cur))
2371 break; 2448 break;
2372 if (*level == 0) { 2449 if (*level == 0) {
2373 ret = drop_leaf_ref(trans, root, cur); 2450 ret = drop_leaf_ref_no_cache(trans, root, cur);
2374 BUG_ON(ret); 2451 BUG_ON(ret);
2375 break; 2452 break;
2376 } 2453 }
@@ -2391,6 +2468,21 @@ static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2391 BUG_ON(ret); 2468 BUG_ON(ret);
2392 continue; 2469 continue;
2393 } 2470 }
2471
2472 if (*level == 1) {
2473 struct btrfs_key key;
2474 btrfs_node_key_to_cpu(cur, &key, path->slots[*level]);
2475 ref = btrfs_lookup_leaf_ref(root, &key);
2476 if (ref) {
2477 ret = drop_leaf_ref(trans, root, ref);
2478 BUG_ON(ret);
2479 btrfs_remove_leaf_ref(root, ref);
2480 btrfs_free_leaf_ref(ref);
2481 *level = 0;
2482 break;
2483 }
2484 }
2485
2394 next = btrfs_find_tree_block(root, bytenr, blocksize); 2486 next = btrfs_find_tree_block(root, bytenr, blocksize);
2395 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) { 2487 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2396 free_extent_buffer(next); 2488 free_extent_buffer(next);
@@ -2398,7 +2490,6 @@ static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2398 2490
2399 if (path->slots[*level] == 0) 2491 if (path->slots[*level] == 0)
2400 reada_walk_down(root, cur, path->slots[*level]); 2492 reada_walk_down(root, cur, path->slots[*level]);
2401
2402 next = read_tree_block(root, bytenr, blocksize, 2493 next = read_tree_block(root, bytenr, blocksize,
2403 ptr_gen); 2494 ptr_gen);
2404 cond_resched(); 2495 cond_resched();
@@ -2435,17 +2526,19 @@ out:
2435 WARN_ON(*level >= BTRFS_MAX_LEVEL); 2526 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2436 2527
2437 if (path->nodes[*level] == root->node) { 2528 if (path->nodes[*level] == root->node) {
2438 root_owner = root->root_key.objectid;
2439 parent = path->nodes[*level]; 2529 parent = path->nodes[*level];
2530 bytenr = path->nodes[*level]->start;
2440 } else { 2531 } else {
2441 parent = path->nodes[*level + 1]; 2532 parent = path->nodes[*level + 1];
2442 root_owner = btrfs_header_owner(parent); 2533 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
2443 } 2534 }
2444 2535
2536 blocksize = btrfs_level_size(root, *level);
2537 root_owner = btrfs_header_owner(parent);
2445 root_gen = btrfs_header_generation(parent); 2538 root_gen = btrfs_header_generation(parent);
2446 ret = __btrfs_free_extent(trans, root, path->nodes[*level]->start, 2539
2447 path->nodes[*level]->len, 2540 ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
2448 root_owner, root_gen, 0, 0, 1); 2541 root_owner, root_gen, 0, 0, 1);
2449 free_extent_buffer(path->nodes[*level]); 2542 free_extent_buffer(path->nodes[*level]);
2450 path->nodes[*level] = NULL; 2543 path->nodes[*level] = NULL;
2451 *level += 1; 2544 *level += 1;
diff --git a/fs/btrfs/ref-cache.c b/fs/btrfs/ref-cache.c
new file mode 100644
index 000000000000..95a9faeb9dc4
--- /dev/null
+++ b/fs/btrfs/ref-cache.c
@@ -0,0 +1,226 @@
1/*
2 * Copyright (C) 2008 Oracle. 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/sched.h>
20#include "ctree.h"
21#include "ref-cache.h"
22#include "transaction.h"
23
24struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(int nr_extents)
25{
26 struct btrfs_leaf_ref *ref;
27
28 ref = kmalloc(btrfs_leaf_ref_size(nr_extents), GFP_NOFS);
29 if (ref) {
30 memset(ref, 0, sizeof(*ref));
31 atomic_set(&ref->usage, 1);
32 }
33 return ref;
34}
35
36void btrfs_free_leaf_ref(struct btrfs_leaf_ref *ref)
37{
38 if (!ref)
39 return;
40 WARN_ON(atomic_read(&ref->usage) == 0);
41 if (atomic_dec_and_test(&ref->usage)) {
42 BUG_ON(ref->in_tree);
43 kfree(ref);
44 }
45}
46
47static int comp_keys(struct btrfs_key *k1, struct btrfs_key *k2)
48{
49 if (k1->objectid > k2->objectid)
50 return 1;
51 if (k1->objectid < k2->objectid)
52 return -1;
53 if (k1->type > k2->type)
54 return 1;
55 if (k1->type < k2->type)
56 return -1;
57 if (k1->offset > k2->offset)
58 return 1;
59 if (k1->offset < k2->offset)
60 return -1;
61 return 0;
62}
63
64static struct rb_node *tree_insert(struct rb_root *root, struct btrfs_key *key,
65 struct rb_node *node)
66{
67 struct rb_node ** p = &root->rb_node;
68 struct rb_node * parent = NULL;
69 struct btrfs_leaf_ref *entry;
70 int ret;
71
72 while(*p) {
73 parent = *p;
74 entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
75 WARN_ON(!entry->in_tree);
76
77 ret = comp_keys(key, &entry->key);
78 if (ret < 0)
79 p = &(*p)->rb_left;
80 else if (ret > 0)
81 p = &(*p)->rb_right;
82 else
83 return parent;
84 }
85
86 entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
87 entry->in_tree = 1;
88 rb_link_node(node, parent, p);
89 rb_insert_color(node, root);
90 return NULL;
91}
92
93static struct rb_node *tree_search(struct rb_root *root, struct btrfs_key *key)
94{
95 struct rb_node * n = root->rb_node;
96 struct btrfs_leaf_ref *entry;
97 int ret;
98
99 while(n) {
100 entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
101 WARN_ON(!entry->in_tree);
102
103 ret = comp_keys(key, &entry->key);
104 if (ret < 0)
105 n = n->rb_left;
106 else if (ret > 0)
107 n = n->rb_right;
108 else
109 return n;
110 }
111 return NULL;
112}
113
114int btrfs_remove_leaf_refs(struct btrfs_root *root)
115{
116 struct rb_node *rb;
117 struct btrfs_leaf_ref *ref = NULL;
118 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
119
120 if (!tree)
121 return 0;
122
123 spin_lock(&tree->lock);
124 while(!btrfs_leaf_ref_tree_empty(tree)) {
125 tree->last = NULL;
126 rb = rb_first(&tree->root);
127 ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
128 rb_erase(&ref->rb_node, &tree->root);
129 ref->in_tree = 0;
130
131 spin_unlock(&tree->lock);
132
133 btrfs_free_leaf_ref(ref);
134
135 cond_resched();
136 spin_lock(&tree->lock);
137 }
138 spin_unlock(&tree->lock);
139 return 0;
140}
141
142struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root,
143 struct btrfs_key *key)
144{
145 struct rb_node *rb;
146 struct btrfs_leaf_ref *ref = NULL;
147 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
148
149 if (!tree)
150 return NULL;
151
152 spin_lock(&tree->lock);
153 if (tree->last && comp_keys(key, &tree->last->key) == 0) {
154 ref = tree->last;
155 } else {
156 rb = tree_search(&tree->root, key);
157 if (rb) {
158 ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
159 tree->last = ref;
160 }
161 }
162 if (ref)
163 atomic_inc(&ref->usage);
164 spin_unlock(&tree->lock);
165 return ref;
166}
167
168int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
169{
170 int ret = 0;
171 struct rb_node *rb;
172 size_t size = btrfs_leaf_ref_size(ref->nritems);
173 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
174 struct btrfs_transaction *trans = root->fs_info->running_transaction;
175
176 spin_lock(&tree->lock);
177 rb = tree_insert(&tree->root, &ref->key, &ref->rb_node);
178 if (rb) {
179 ret = -EEXIST;
180 } else {
181 spin_lock(&root->fs_info->ref_cache_lock);
182 root->fs_info->total_ref_cache_size += size;
183 if (trans && tree->generation == trans->transid)
184 root->fs_info->running_ref_cache_size += size;
185 spin_unlock(&root->fs_info->ref_cache_lock);
186
187 tree->last = ref;
188 atomic_inc(&ref->usage);
189 }
190 spin_unlock(&tree->lock);
191 return ret;
192}
193
194int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
195{
196 size_t size = btrfs_leaf_ref_size(ref->nritems);
197 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
198 struct btrfs_transaction *trans = root->fs_info->running_transaction;
199
200 BUG_ON(!ref->in_tree);
201 spin_lock(&tree->lock);
202
203 spin_lock(&root->fs_info->ref_cache_lock);
204 root->fs_info->total_ref_cache_size -= size;
205 if (trans && tree->generation == trans->transid)
206 root->fs_info->running_ref_cache_size -= size;
207 spin_unlock(&root->fs_info->ref_cache_lock);
208
209 if (tree->last == ref) {
210 struct rb_node *next = rb_next(&ref->rb_node);
211 if (next) {
212 tree->last = rb_entry(next, struct btrfs_leaf_ref,
213 rb_node);
214 } else
215 tree->last = NULL;
216 }
217
218 rb_erase(&ref->rb_node, &tree->root);
219 ref->in_tree = 0;
220
221 spin_unlock(&tree->lock);
222
223 btrfs_free_leaf_ref(ref);
224 return 0;
225}
226
diff --git a/fs/btrfs/ref-cache.h b/fs/btrfs/ref-cache.h
new file mode 100644
index 000000000000..79ecc47110f2
--- /dev/null
+++ b/fs/btrfs/ref-cache.h
@@ -0,0 +1,72 @@
1/*
2 * Copyright (C) 2008 Oracle. 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
19struct btrfs_extent_info {
20 u64 bytenr;
21 u64 num_bytes;
22 u64 objectid;
23 u64 offset;
24};
25
26struct btrfs_leaf_ref {
27 struct rb_node rb_node;
28 struct btrfs_key key;
29 int in_tree;
30 atomic_t usage;
31
32 u64 bytenr;
33 u64 owner;
34 u64 generation;
35 int nritems;
36 struct btrfs_extent_info extents[];
37};
38
39struct btrfs_leaf_ref_tree {
40 struct rb_root root;
41 struct btrfs_leaf_ref *last;
42 u64 generation;
43 spinlock_t lock;
44};
45
46static inline size_t btrfs_leaf_ref_size(int nr_extents)
47{
48 return sizeof(struct btrfs_leaf_ref) +
49 sizeof(struct btrfs_extent_info) * nr_extents;
50}
51
52static inline void btrfs_leaf_ref_tree_init(struct btrfs_leaf_ref_tree *tree)
53{
54 tree->root.rb_node = NULL;
55 tree->last = NULL;
56 tree->generation = 0;
57 spin_lock_init(&tree->lock);
58}
59
60static inline int btrfs_leaf_ref_tree_empty(struct btrfs_leaf_ref_tree *tree)
61{
62 return RB_EMPTY_ROOT(&tree->root);
63}
64
65void btrfs_leaf_ref_tree_init(struct btrfs_leaf_ref_tree *tree);
66struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(int nr_extents);
67void btrfs_free_leaf_ref(struct btrfs_leaf_ref *ref);
68struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root,
69 struct btrfs_key *key);
70int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref);
71int btrfs_remove_leaf_refs(struct btrfs_root *root);
72int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref);
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index 768b0d223e68..543e5ee4033a 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -24,6 +24,7 @@
24#include "disk-io.h" 24#include "disk-io.h"
25#include "transaction.h" 25#include "transaction.h"
26#include "locking.h" 26#include "locking.h"
27#include "ref-cache.h"
27 28
28static int total_trans = 0; 29static int total_trans = 0;
29extern struct kmem_cache *btrfs_trans_handle_cachep; 30extern struct kmem_cache *btrfs_trans_handle_cachep;
@@ -31,6 +32,13 @@ extern struct kmem_cache *btrfs_transaction_cachep;
31 32
32#define BTRFS_ROOT_TRANS_TAG 0 33#define BTRFS_ROOT_TRANS_TAG 0
33 34
35struct dirty_root {
36 struct list_head list;
37 struct btrfs_root *root;
38 struct btrfs_root *latest_root;
39 struct btrfs_leaf_ref_tree ref_tree;
40};
41
34static noinline void put_transaction(struct btrfs_transaction *transaction) 42static noinline void put_transaction(struct btrfs_transaction *transaction)
35{ 43{
36 WARN_ON(transaction->use_count == 0); 44 WARN_ON(transaction->use_count == 0);
@@ -84,6 +92,7 @@ static noinline int join_transaction(struct btrfs_root *root)
84 92
85static noinline int record_root_in_trans(struct btrfs_root *root) 93static noinline int record_root_in_trans(struct btrfs_root *root)
86{ 94{
95 struct dirty_root *dirty;
87 u64 running_trans_id = root->fs_info->running_transaction->transid; 96 u64 running_trans_id = root->fs_info->running_transaction->transid;
88 if (root->ref_cows && root->last_trans < running_trans_id) { 97 if (root->ref_cows && root->last_trans < running_trans_id) {
89 WARN_ON(root == root->fs_info->extent_root); 98 WARN_ON(root == root->fs_info->extent_root);
@@ -91,7 +100,25 @@ static noinline int record_root_in_trans(struct btrfs_root *root)
91 radix_tree_tag_set(&root->fs_info->fs_roots_radix, 100 radix_tree_tag_set(&root->fs_info->fs_roots_radix,
92 (unsigned long)root->root_key.objectid, 101 (unsigned long)root->root_key.objectid,
93 BTRFS_ROOT_TRANS_TAG); 102 BTRFS_ROOT_TRANS_TAG);
103
104 dirty = kmalloc(sizeof(*dirty), GFP_NOFS);
105 BUG_ON(!dirty);
106 dirty->root = kmalloc(sizeof(*dirty->root), GFP_NOFS);
107 BUG_ON(!dirty->root);
108
109 dirty->latest_root = root;
110 INIT_LIST_HEAD(&dirty->list);
111 btrfs_leaf_ref_tree_init(&dirty->ref_tree);
112 dirty->ref_tree.generation = running_trans_id;
113
94 root->commit_root = btrfs_root_node(root); 114 root->commit_root = btrfs_root_node(root);
115 root->ref_tree = &dirty->ref_tree;
116
117 memcpy(dirty->root, root, sizeof(*root));
118 spin_lock_init(&dirty->root->node_lock);
119 mutex_init(&dirty->root->objectid_mutex);
120 dirty->root->node = root->commit_root;
121 dirty->root->commit_root = NULL;
95 } else { 122 } else {
96 WARN_ON(1); 123 WARN_ON(1);
97 } 124 }
@@ -310,12 +337,6 @@ int btrfs_commit_tree_roots(struct btrfs_trans_handle *trans,
310 return 0; 337 return 0;
311} 338}
312 339
313struct dirty_root {
314 struct list_head list;
315 struct btrfs_root *root;
316 struct btrfs_root *latest_root;
317};
318
319int btrfs_add_dead_root(struct btrfs_root *root, 340int btrfs_add_dead_root(struct btrfs_root *root,
320 struct btrfs_root *latest, 341 struct btrfs_root *latest,
321 struct list_head *dead_list) 342 struct list_head *dead_list)
@@ -325,8 +346,10 @@ int btrfs_add_dead_root(struct btrfs_root *root,
325 dirty = kmalloc(sizeof(*dirty), GFP_NOFS); 346 dirty = kmalloc(sizeof(*dirty), GFP_NOFS);
326 if (!dirty) 347 if (!dirty)
327 return -ENOMEM; 348 return -ENOMEM;
349 btrfs_leaf_ref_tree_init(&dirty->ref_tree);
328 dirty->root = root; 350 dirty->root = root;
329 dirty->latest_root = latest; 351 dirty->latest_root = latest;
352 root->ref_tree = NULL;
330 list_add(&dirty->list, dead_list); 353 list_add(&dirty->list, dead_list);
331 return 0; 354 return 0;
332} 355}
@@ -354,11 +377,23 @@ static noinline int add_dirty_roots(struct btrfs_trans_handle *trans,
354 radix_tree_tag_clear(radix, 377 radix_tree_tag_clear(radix,
355 (unsigned long)root->root_key.objectid, 378 (unsigned long)root->root_key.objectid,
356 BTRFS_ROOT_TRANS_TAG); 379 BTRFS_ROOT_TRANS_TAG);
380
381 BUG_ON(!root->ref_tree);
382 dirty = container_of(root->ref_tree, struct dirty_root,
383 ref_tree);
384
357 if (root->commit_root == root->node) { 385 if (root->commit_root == root->node) {
358 WARN_ON(root->node->start != 386 WARN_ON(root->node->start !=
359 btrfs_root_bytenr(&root->root_item)); 387 btrfs_root_bytenr(&root->root_item));
388
389 BUG_ON(!btrfs_leaf_ref_tree_empty(
390 root->ref_tree));
360 free_extent_buffer(root->commit_root); 391 free_extent_buffer(root->commit_root);
361 root->commit_root = NULL; 392 root->commit_root = NULL;
393 root->ref_tree = NULL;
394
395 kfree(dirty->root);
396 kfree(dirty);
362 397
363 /* make sure to update the root on disk 398 /* make sure to update the root on disk
364 * so we get any updates to the block used 399 * so we get any updates to the block used
@@ -370,23 +405,12 @@ static noinline int add_dirty_roots(struct btrfs_trans_handle *trans,
370 &root->root_item); 405 &root->root_item);
371 continue; 406 continue;
372 } 407 }
373 dirty = kmalloc(sizeof(*dirty), GFP_NOFS);
374 BUG_ON(!dirty);
375 dirty->root = kmalloc(sizeof(*dirty->root), GFP_NOFS);
376 BUG_ON(!dirty->root);
377 408
378 memset(&root->root_item.drop_progress, 0, 409 memset(&root->root_item.drop_progress, 0,
379 sizeof(struct btrfs_disk_key)); 410 sizeof(struct btrfs_disk_key));
380 root->root_item.drop_level = 0; 411 root->root_item.drop_level = 0;
381
382 memcpy(dirty->root, root, sizeof(*root));
383 dirty->root->node = root->commit_root;
384 dirty->latest_root = root;
385 spin_lock_init(&dirty->root->node_lock);
386 mutex_init(&dirty->root->objectid_mutex);
387
388 root->commit_root = NULL; 412 root->commit_root = NULL;
389 413 root->ref_tree = NULL;
390 root->root_key.offset = root->fs_info->generation; 414 root->root_key.offset = root->fs_info->generation;
391 btrfs_set_root_bytenr(&root->root_item, 415 btrfs_set_root_bytenr(&root->root_item,
392 root->node->start); 416 root->node->start);
@@ -409,6 +433,7 @@ static noinline int add_dirty_roots(struct btrfs_trans_handle *trans,
409 list_add(&dirty->list, list); 433 list_add(&dirty->list, list);
410 } else { 434 } else {
411 WARN_ON(1); 435 WARN_ON(1);
436 free_extent_buffer(dirty->root->node);
412 kfree(dirty->root); 437 kfree(dirty->root);
413 kfree(dirty); 438 kfree(dirty);
414 } 439 }
@@ -514,6 +539,8 @@ static noinline int drop_dirty_roots(struct btrfs_root *tree_root,
514 ret = btrfs_end_transaction(trans, tree_root); 539 ret = btrfs_end_transaction(trans, tree_root);
515 BUG_ON(ret); 540 BUG_ON(ret);
516 541
542 btrfs_remove_leaf_refs(dirty->root);
543
517 free_extent_buffer(dirty->root->node); 544 free_extent_buffer(dirty->root->node);
518 kfree(dirty->root); 545 kfree(dirty->root);
519 kfree(dirty); 546 kfree(dirty);
@@ -698,6 +725,10 @@ int btrfs_commit_transaction(struct btrfs_trans_handle *trans,
698 &dirty_fs_roots); 725 &dirty_fs_roots);
699 BUG_ON(ret); 726 BUG_ON(ret);
700 727
728 spin_lock(&root->fs_info->ref_cache_lock);
729 root->fs_info->running_ref_cache_size = 0;
730 spin_unlock(&root->fs_info->ref_cache_lock);
731
701 ret = btrfs_commit_tree_roots(trans, root); 732 ret = btrfs_commit_tree_roots(trans, root);
702 BUG_ON(ret); 733 BUG_ON(ret);
703 734