Commit | Line | Data |
---|---|---|
31153d81 YZ |
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> | |
5a0e3ad6 | 20 | #include <linux/slab.h> |
bd56b302 | 21 | #include <linux/sort.h> |
31153d81 YZ |
22 | #include "ctree.h" |
23 | #include "ref-cache.h" | |
24 | #include "transaction.h" | |
25 | ||
d352ac68 CM |
26 | /* |
27 | * leaf refs are used to cache the information about which extents | |
28 | * a given leaf has references on. This allows us to process that leaf | |
29 | * in btrfs_drop_snapshot without needing to read it back from disk. | |
30 | */ | |
31 | ||
32 | /* | |
33 | * kmalloc a leaf reference struct and update the counters for the | |
34 | * total ref cache size | |
35 | */ | |
bcc63abb Y |
36 | struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(struct btrfs_root *root, |
37 | int nr_extents) | |
31153d81 YZ |
38 | { |
39 | struct btrfs_leaf_ref *ref; | |
bcc63abb | 40 | size_t size = btrfs_leaf_ref_size(nr_extents); |
31153d81 | 41 | |
bcc63abb | 42 | ref = kmalloc(size, GFP_NOFS); |
31153d81 | 43 | if (ref) { |
bcc63abb Y |
44 | spin_lock(&root->fs_info->ref_cache_lock); |
45 | root->fs_info->total_ref_cache_size += size; | |
46 | spin_unlock(&root->fs_info->ref_cache_lock); | |
47 | ||
31153d81 YZ |
48 | memset(ref, 0, sizeof(*ref)); |
49 | atomic_set(&ref->usage, 1); | |
017e5369 | 50 | INIT_LIST_HEAD(&ref->list); |
31153d81 YZ |
51 | } |
52 | return ref; | |
53 | } | |
54 | ||
d352ac68 CM |
55 | /* |
56 | * free a leaf reference struct and update the counters for the | |
57 | * total ref cache size | |
58 | */ | |
bcc63abb | 59 | void btrfs_free_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) |
31153d81 YZ |
60 | { |
61 | if (!ref) | |
62 | return; | |
63 | WARN_ON(atomic_read(&ref->usage) == 0); | |
64 | if (atomic_dec_and_test(&ref->usage)) { | |
bcc63abb Y |
65 | size_t size = btrfs_leaf_ref_size(ref->nritems); |
66 | ||
31153d81 YZ |
67 | BUG_ON(ref->in_tree); |
68 | kfree(ref); | |
bcc63abb Y |
69 | |
70 | spin_lock(&root->fs_info->ref_cache_lock); | |
71 | root->fs_info->total_ref_cache_size -= size; | |
72 | spin_unlock(&root->fs_info->ref_cache_lock); | |
31153d81 YZ |
73 | } |
74 | } | |
75 | ||
017e5369 | 76 | static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr, |
31153d81 YZ |
77 | struct rb_node *node) |
78 | { | |
d397712b CM |
79 | struct rb_node **p = &root->rb_node; |
80 | struct rb_node *parent = NULL; | |
31153d81 | 81 | struct btrfs_leaf_ref *entry; |
31153d81 | 82 | |
d397712b | 83 | while (*p) { |
31153d81 YZ |
84 | parent = *p; |
85 | entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node); | |
31153d81 | 86 | |
017e5369 | 87 | if (bytenr < entry->bytenr) |
31153d81 | 88 | p = &(*p)->rb_left; |
017e5369 | 89 | else if (bytenr > entry->bytenr) |
31153d81 YZ |
90 | p = &(*p)->rb_right; |
91 | else | |
92 | return parent; | |
93 | } | |
bcc63abb | 94 | |
31153d81 | 95 | entry = rb_entry(node, struct btrfs_leaf_ref, rb_node); |
31153d81 YZ |
96 | rb_link_node(node, parent, p); |
97 | rb_insert_color(node, root); | |
98 | return NULL; | |
99 | } | |
100 | ||
017e5369 | 101 | static struct rb_node *tree_search(struct rb_root *root, u64 bytenr) |
31153d81 | 102 | { |
d397712b | 103 | struct rb_node *n = root->rb_node; |
31153d81 | 104 | struct btrfs_leaf_ref *entry; |
31153d81 | 105 | |
d397712b | 106 | while (n) { |
31153d81 YZ |
107 | entry = rb_entry(n, struct btrfs_leaf_ref, rb_node); |
108 | WARN_ON(!entry->in_tree); | |
109 | ||
017e5369 | 110 | if (bytenr < entry->bytenr) |
31153d81 | 111 | n = n->rb_left; |
017e5369 | 112 | else if (bytenr > entry->bytenr) |
31153d81 YZ |
113 | n = n->rb_right; |
114 | else | |
115 | return n; | |
116 | } | |
117 | return NULL; | |
118 | } | |
119 | ||
e4657689 ZY |
120 | int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen, |
121 | int shared) | |
31153d81 | 122 | { |
31153d81 YZ |
123 | struct btrfs_leaf_ref *ref = NULL; |
124 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; | |
125 | ||
e4657689 ZY |
126 | if (shared) |
127 | tree = &root->fs_info->shared_ref_tree; | |
31153d81 YZ |
128 | if (!tree) |
129 | return 0; | |
130 | ||
131 | spin_lock(&tree->lock); | |
d397712b | 132 | while (!list_empty(&tree->list)) { |
bcc63abb | 133 | ref = list_entry(tree->list.next, struct btrfs_leaf_ref, list); |
e4657689 | 134 | BUG_ON(ref->tree != tree); |
bcc63abb Y |
135 | if (ref->root_gen > max_root_gen) |
136 | break; | |
e4657689 ZY |
137 | if (!xchg(&ref->in_tree, 0)) { |
138 | cond_resched_lock(&tree->lock); | |
139 | continue; | |
140 | } | |
bcc63abb | 141 | |
31153d81 | 142 | rb_erase(&ref->rb_node, &tree->root); |
017e5369 | 143 | list_del_init(&ref->list); |
31153d81 YZ |
144 | |
145 | spin_unlock(&tree->lock); | |
bcc63abb | 146 | btrfs_free_leaf_ref(root, ref); |
31153d81 YZ |
147 | cond_resched(); |
148 | spin_lock(&tree->lock); | |
149 | } | |
150 | spin_unlock(&tree->lock); | |
151 | return 0; | |
152 | } | |
153 | ||
d352ac68 CM |
154 | /* |
155 | * find the leaf ref for a given extent. This returns the ref struct with | |
156 | * a usage reference incremented | |
157 | */ | |
31153d81 | 158 | struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root, |
017e5369 | 159 | u64 bytenr) |
31153d81 YZ |
160 | { |
161 | struct rb_node *rb; | |
162 | struct btrfs_leaf_ref *ref = NULL; | |
163 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; | |
e4657689 ZY |
164 | again: |
165 | if (tree) { | |
166 | spin_lock(&tree->lock); | |
167 | rb = tree_search(&tree->root, bytenr); | |
168 | if (rb) | |
169 | ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node); | |
170 | if (ref) | |
171 | atomic_inc(&ref->usage); | |
172 | spin_unlock(&tree->lock); | |
173 | if (ref) | |
174 | return ref; | |
175 | } | |
176 | if (tree != &root->fs_info->shared_ref_tree) { | |
177 | tree = &root->fs_info->shared_ref_tree; | |
178 | goto again; | |
179 | } | |
180 | return NULL; | |
31153d81 YZ |
181 | } |
182 | ||
d352ac68 CM |
183 | /* |
184 | * add a fully filled in leaf ref struct | |
185 | * remove all the refs older than a given root generation | |
186 | */ | |
e4657689 ZY |
187 | int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref, |
188 | int shared) | |
31153d81 YZ |
189 | { |
190 | int ret = 0; | |
191 | struct rb_node *rb; | |
31153d81 | 192 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
31153d81 | 193 | |
e4657689 ZY |
194 | if (shared) |
195 | tree = &root->fs_info->shared_ref_tree; | |
196 | ||
31153d81 | 197 | spin_lock(&tree->lock); |
017e5369 | 198 | rb = tree_insert(&tree->root, ref->bytenr, &ref->rb_node); |
31153d81 YZ |
199 | if (rb) { |
200 | ret = -EEXIST; | |
201 | } else { | |
31153d81 | 202 | atomic_inc(&ref->usage); |
e4657689 ZY |
203 | ref->tree = tree; |
204 | ref->in_tree = 1; | |
017e5369 | 205 | list_add_tail(&ref->list, &tree->list); |
31153d81 YZ |
206 | } |
207 | spin_unlock(&tree->lock); | |
208 | return ret; | |
209 | } | |
210 | ||
d352ac68 CM |
211 | /* |
212 | * remove a single leaf ref from the tree. This drops the ref held by the tree | |
213 | * only | |
214 | */ | |
31153d81 YZ |
215 | int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) |
216 | { | |
e4657689 ZY |
217 | struct btrfs_leaf_ref_tree *tree; |
218 | ||
219 | if (!xchg(&ref->in_tree, 0)) | |
220 | return 0; | |
31153d81 | 221 | |
e4657689 | 222 | tree = ref->tree; |
31153d81 | 223 | spin_lock(&tree->lock); |
31153d81 | 224 | |
31153d81 | 225 | rb_erase(&ref->rb_node, &tree->root); |
017e5369 | 226 | list_del_init(&ref->list); |
31153d81 YZ |
227 | |
228 | spin_unlock(&tree->lock); | |
229 | ||
bcc63abb | 230 | btrfs_free_leaf_ref(root, ref); |
31153d81 YZ |
231 | return 0; |
232 | } |