2 * Copyright (C) 2008 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/sched.h>
21 #include "ref-cache.h"
22 #include "transaction.h"
25 * leaf refs are used to cache the information about which extents
26 * a given leaf has references on. This allows us to process that leaf
27 * in btrfs_drop_snapshot without needing to read it back from disk.
31 * kmalloc a leaf reference struct and update the counters for the
32 * total ref cache size
34 struct btrfs_leaf_ref
*btrfs_alloc_leaf_ref(struct btrfs_root
*root
,
37 struct btrfs_leaf_ref
*ref
;
38 size_t size
= btrfs_leaf_ref_size(nr_extents
);
40 ref
= kmalloc(size
, GFP_NOFS
);
42 spin_lock(&root
->fs_info
->ref_cache_lock
);
43 root
->fs_info
->total_ref_cache_size
+= size
;
44 spin_unlock(&root
->fs_info
->ref_cache_lock
);
46 memset(ref
, 0, sizeof(*ref
));
47 atomic_set(&ref
->usage
, 1);
48 INIT_LIST_HEAD(&ref
->list
);
54 * free a leaf reference struct and update the counters for the
55 * total ref cache size
57 void btrfs_free_leaf_ref(struct btrfs_root
*root
, struct btrfs_leaf_ref
*ref
)
61 WARN_ON(atomic_read(&ref
->usage
) == 0);
62 if (atomic_dec_and_test(&ref
->usage
)) {
63 size_t size
= btrfs_leaf_ref_size(ref
->nritems
);
68 spin_lock(&root
->fs_info
->ref_cache_lock
);
69 root
->fs_info
->total_ref_cache_size
-= size
;
70 spin_unlock(&root
->fs_info
->ref_cache_lock
);
74 static struct rb_node
*tree_insert(struct rb_root
*root
, u64 bytenr
,
77 struct rb_node
**p
= &root
->rb_node
;
78 struct rb_node
*parent
= NULL
;
79 struct btrfs_leaf_ref
*entry
;
83 entry
= rb_entry(parent
, struct btrfs_leaf_ref
, rb_node
);
85 if (bytenr
< entry
->bytenr
)
87 else if (bytenr
> entry
->bytenr
)
93 entry
= rb_entry(node
, struct btrfs_leaf_ref
, rb_node
);
94 rb_link_node(node
, parent
, p
);
95 rb_insert_color(node
, root
);
99 static struct rb_node
*tree_search(struct rb_root
*root
, u64 bytenr
)
101 struct rb_node
*n
= root
->rb_node
;
102 struct btrfs_leaf_ref
*entry
;
105 entry
= rb_entry(n
, struct btrfs_leaf_ref
, rb_node
);
106 WARN_ON(!entry
->in_tree
);
108 if (bytenr
< entry
->bytenr
)
110 else if (bytenr
> entry
->bytenr
)
118 int btrfs_remove_leaf_refs(struct btrfs_root
*root
, u64 max_root_gen
,
121 struct btrfs_leaf_ref
*ref
= NULL
;
122 struct btrfs_leaf_ref_tree
*tree
= root
->ref_tree
;
125 tree
= &root
->fs_info
->shared_ref_tree
;
129 spin_lock(&tree
->lock
);
130 while (!list_empty(&tree
->list
)) {
131 ref
= list_entry(tree
->list
.next
, struct btrfs_leaf_ref
, list
);
132 BUG_ON(ref
->tree
!= tree
);
133 if (ref
->root_gen
> max_root_gen
)
135 if (!xchg(&ref
->in_tree
, 0)) {
136 cond_resched_lock(&tree
->lock
);
140 rb_erase(&ref
->rb_node
, &tree
->root
);
141 list_del_init(&ref
->list
);
143 spin_unlock(&tree
->lock
);
144 btrfs_free_leaf_ref(root
, ref
);
146 spin_lock(&tree
->lock
);
148 spin_unlock(&tree
->lock
);
153 * find the leaf ref for a given extent. This returns the ref struct with
154 * a usage reference incremented
156 struct btrfs_leaf_ref
*btrfs_lookup_leaf_ref(struct btrfs_root
*root
,
160 struct btrfs_leaf_ref
*ref
= NULL
;
161 struct btrfs_leaf_ref_tree
*tree
= root
->ref_tree
;
164 spin_lock(&tree
->lock
);
165 rb
= tree_search(&tree
->root
, bytenr
);
167 ref
= rb_entry(rb
, struct btrfs_leaf_ref
, rb_node
);
169 atomic_inc(&ref
->usage
);
170 spin_unlock(&tree
->lock
);
174 if (tree
!= &root
->fs_info
->shared_ref_tree
) {
175 tree
= &root
->fs_info
->shared_ref_tree
;
182 * add a fully filled in leaf ref struct
183 * remove all the refs older than a given root generation
185 int btrfs_add_leaf_ref(struct btrfs_root
*root
, struct btrfs_leaf_ref
*ref
,
190 struct btrfs_leaf_ref_tree
*tree
= root
->ref_tree
;
193 tree
= &root
->fs_info
->shared_ref_tree
;
195 spin_lock(&tree
->lock
);
196 rb
= tree_insert(&tree
->root
, ref
->bytenr
, &ref
->rb_node
);
200 atomic_inc(&ref
->usage
);
203 list_add_tail(&ref
->list
, &tree
->list
);
205 spin_unlock(&tree
->lock
);
210 * remove a single leaf ref from the tree. This drops the ref held by the tree
213 int btrfs_remove_leaf_ref(struct btrfs_root
*root
, struct btrfs_leaf_ref
*ref
)
215 struct btrfs_leaf_ref_tree
*tree
;
217 if (!xchg(&ref
->in_tree
, 0))
221 spin_lock(&tree
->lock
);
223 rb_erase(&ref
->rb_node
, &tree
->root
);
224 list_del_init(&ref
->list
);
226 spin_unlock(&tree
->lock
);
228 btrfs_free_leaf_ref(root
, ref
);