Btrfs: Add shared reference cache
[linux-2.6.git] / fs / btrfs / ref-cache.c
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
24 struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(struct btrfs_root *root,
25                                             int nr_extents)
26 {
27         struct btrfs_leaf_ref *ref;
28         size_t size = btrfs_leaf_ref_size(nr_extents);
29
30         ref = kmalloc(size, GFP_NOFS);
31         if (ref) {
32                 spin_lock(&root->fs_info->ref_cache_lock);
33                 root->fs_info->total_ref_cache_size += size;
34                 spin_unlock(&root->fs_info->ref_cache_lock);
35
36                 memset(ref, 0, sizeof(*ref));
37                 atomic_set(&ref->usage, 1);
38                 INIT_LIST_HEAD(&ref->list);
39         }
40         return ref;
41 }
42
43 void btrfs_free_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
44 {
45         if (!ref)
46                 return;
47         WARN_ON(atomic_read(&ref->usage) == 0);
48         if (atomic_dec_and_test(&ref->usage)) {
49                 size_t size = btrfs_leaf_ref_size(ref->nritems);
50
51                 BUG_ON(ref->in_tree);
52                 kfree(ref);
53
54                 spin_lock(&root->fs_info->ref_cache_lock);
55                 root->fs_info->total_ref_cache_size -= size;
56                 spin_unlock(&root->fs_info->ref_cache_lock);
57         }
58 }
59
60 static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
61                                    struct rb_node *node)
62 {
63         struct rb_node ** p = &root->rb_node;
64         struct rb_node * parent = NULL;
65         struct btrfs_leaf_ref *entry;
66
67         while(*p) {
68                 parent = *p;
69                 entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
70                 WARN_ON(!entry->in_tree);
71
72                 if (bytenr < entry->bytenr)
73                         p = &(*p)->rb_left;
74                 else if (bytenr > entry->bytenr)
75                         p = &(*p)->rb_right;
76                 else
77                         return parent;
78         }
79
80         entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
81         rb_link_node(node, parent, p);
82         rb_insert_color(node, root);
83         return NULL;
84 }
85
86 static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
87 {
88         struct rb_node * n = root->rb_node;
89         struct btrfs_leaf_ref *entry;
90
91         while(n) {
92                 entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
93                 WARN_ON(!entry->in_tree);
94
95                 if (bytenr < entry->bytenr)
96                         n = n->rb_left;
97                 else if (bytenr > entry->bytenr)
98                         n = n->rb_right;
99                 else
100                         return n;
101         }
102         return NULL;
103 }
104
105 int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen,
106                            int shared)
107 {
108         struct btrfs_leaf_ref *ref = NULL;
109         struct btrfs_leaf_ref_tree *tree = root->ref_tree;
110
111         if (shared)
112                 tree = &root->fs_info->shared_ref_tree;
113         if (!tree)
114                 return 0;
115
116         spin_lock(&tree->lock);
117         while(!list_empty(&tree->list)) {
118                 ref = list_entry(tree->list.next, struct btrfs_leaf_ref, list);
119                 BUG_ON(ref->tree != tree);
120                 if (ref->root_gen > max_root_gen)
121                         break;
122                 if (!xchg(&ref->in_tree, 0)) {
123                         cond_resched_lock(&tree->lock);
124                         continue;
125                 }
126
127                 rb_erase(&ref->rb_node, &tree->root);
128                 list_del_init(&ref->list);
129
130                 spin_unlock(&tree->lock);
131                 btrfs_free_leaf_ref(root, ref);
132                 cond_resched();
133                 spin_lock(&tree->lock);
134         }
135         spin_unlock(&tree->lock);
136         return 0;
137 }
138
139 struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root,
140                                              u64 bytenr)
141 {
142         struct rb_node *rb;
143         struct btrfs_leaf_ref *ref = NULL;
144         struct btrfs_leaf_ref_tree *tree = root->ref_tree;
145 again:
146         if (tree) {
147                 spin_lock(&tree->lock);
148                 rb = tree_search(&tree->root, bytenr);
149                 if (rb)
150                         ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
151                 if (ref)
152                         atomic_inc(&ref->usage);
153                 spin_unlock(&tree->lock);
154                 if (ref)
155                         return ref;
156         }
157         if (tree != &root->fs_info->shared_ref_tree) {
158                 tree = &root->fs_info->shared_ref_tree;
159                 goto again;
160         }
161         return NULL;
162 }
163
164 int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref,
165                        int shared)
166 {
167         int ret = 0;
168         struct rb_node *rb;
169         struct btrfs_leaf_ref_tree *tree = root->ref_tree;
170
171         if (shared)
172                 tree = &root->fs_info->shared_ref_tree;
173
174         spin_lock(&tree->lock);
175         rb = tree_insert(&tree->root, ref->bytenr, &ref->rb_node);
176         if (rb) {
177                 ret = -EEXIST;
178         } else {
179                 atomic_inc(&ref->usage);
180                 ref->tree = tree;
181                 ref->in_tree = 1;
182                 list_add_tail(&ref->list, &tree->list);
183         }
184         spin_unlock(&tree->lock);
185         return ret;
186 }
187
188 int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
189 {
190         struct btrfs_leaf_ref_tree *tree;
191
192         if (!xchg(&ref->in_tree, 0))
193                 return 0;
194
195         tree = ref->tree;
196         spin_lock(&tree->lock);
197
198         rb_erase(&ref->rb_node, &tree->root);
199         list_del_init(&ref->list);
200
201         spin_unlock(&tree->lock);
202
203         btrfs_free_leaf_ref(root, ref);
204         return 0;
205 }