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"
24 struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(struct btrfs_root *root,
27 struct btrfs_leaf_ref *ref;
28 size_t size = btrfs_leaf_ref_size(nr_extents);
30 ref = kmalloc(size, GFP_NOFS);
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);
36 memset(ref, 0, sizeof(*ref));
37 atomic_set(&ref->usage, 1);
38 INIT_LIST_HEAD(&ref->list);
43 void btrfs_free_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
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);
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);
60 static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
63 struct rb_node ** p = &root->rb_node;
64 struct rb_node * parent = NULL;
65 struct btrfs_leaf_ref *entry;
69 entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
70 WARN_ON(!entry->in_tree);
72 if (bytenr < entry->bytenr)
74 else if (bytenr > entry->bytenr)
80 entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
81 rb_link_node(node, parent, p);
82 rb_insert_color(node, root);
86 static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
88 struct rb_node * n = root->rb_node;
89 struct btrfs_leaf_ref *entry;
92 entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
93 WARN_ON(!entry->in_tree);
95 if (bytenr < entry->bytenr)
97 else if (bytenr > entry->bytenr)
105 int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen,
108 struct btrfs_leaf_ref *ref = NULL;
109 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
112 tree = &root->fs_info->shared_ref_tree;
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)
122 if (!xchg(&ref->in_tree, 0)) {
123 cond_resched_lock(&tree->lock);
127 rb_erase(&ref->rb_node, &tree->root);
128 list_del_init(&ref->list);
130 spin_unlock(&tree->lock);
131 btrfs_free_leaf_ref(root, ref);
133 spin_lock(&tree->lock);
135 spin_unlock(&tree->lock);
139 struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root,
143 struct btrfs_leaf_ref *ref = NULL;
144 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
147 spin_lock(&tree->lock);
148 rb = tree_search(&tree->root, bytenr);
150 ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
152 atomic_inc(&ref->usage);
153 spin_unlock(&tree->lock);
157 if (tree != &root->fs_info->shared_ref_tree) {
158 tree = &root->fs_info->shared_ref_tree;
164 int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref,
169 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
172 tree = &root->fs_info->shared_ref_tree;
174 spin_lock(&tree->lock);
175 rb = tree_insert(&tree->root, ref->bytenr, &ref->rb_node);
179 atomic_inc(&ref->usage);
182 list_add_tail(&ref->list, &tree->list);
184 spin_unlock(&tree->lock);
188 int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
190 struct btrfs_leaf_ref_tree *tree;
192 if (!xchg(&ref->in_tree, 0))
196 spin_lock(&tree->lock);
198 rb_erase(&ref->rb_node, &tree->root);
199 list_del_init(&ref->list);
201 spin_unlock(&tree->lock);
203 btrfs_free_leaf_ref(root, ref);