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(int nr_extents)
26 struct btrfs_leaf_ref *ref;
28 ref = kmalloc(btrfs_leaf_ref_size(nr_extents), GFP_NOFS);
30 memset(ref, 0, sizeof(*ref));
31 atomic_set(&ref->usage, 1);
36 void btrfs_free_leaf_ref(struct btrfs_leaf_ref *ref)
40 WARN_ON(atomic_read(&ref->usage) == 0);
41 if (atomic_dec_and_test(&ref->usage)) {
47 static int comp_keys(struct btrfs_key *k1, struct btrfs_key *k2)
49 if (k1->objectid > k2->objectid)
51 if (k1->objectid < k2->objectid)
53 if (k1->type > k2->type)
55 if (k1->type < k2->type)
57 if (k1->offset > k2->offset)
59 if (k1->offset < k2->offset)
64 static struct rb_node *tree_insert(struct rb_root *root, struct btrfs_key *key,
67 struct rb_node ** p = &root->rb_node;
68 struct rb_node * parent = NULL;
69 struct btrfs_leaf_ref *entry;
74 entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
75 WARN_ON(!entry->in_tree);
77 ret = comp_keys(key, &entry->key);
86 entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
88 rb_link_node(node, parent, p);
89 rb_insert_color(node, root);
93 static struct rb_node *tree_search(struct rb_root *root, struct btrfs_key *key)
95 struct rb_node * n = root->rb_node;
96 struct btrfs_leaf_ref *entry;
100 entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
101 WARN_ON(!entry->in_tree);
103 ret = comp_keys(key, &entry->key);
114 int btrfs_remove_leaf_refs(struct btrfs_root *root)
117 struct btrfs_leaf_ref *ref = NULL;
118 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
123 spin_lock(&tree->lock);
124 while(!btrfs_leaf_ref_tree_empty(tree)) {
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);
131 spin_unlock(&tree->lock);
133 btrfs_free_leaf_ref(ref);
136 spin_lock(&tree->lock);
138 spin_unlock(&tree->lock);
142 struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root,
143 struct btrfs_key *key)
146 struct btrfs_leaf_ref *ref = NULL;
147 struct btrfs_leaf_ref_tree *tree = root->ref_tree;
152 spin_lock(&tree->lock);
153 if (tree->last && comp_keys(key, &tree->last->key) == 0) {
156 rb = tree_search(&tree->root, key);
158 ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
163 atomic_inc(&ref->usage);
164 spin_unlock(&tree->lock);
168 int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
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;
176 spin_lock(&tree->lock);
177 rb = tree_insert(&tree->root, &ref->key, &ref->rb_node);
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);
188 atomic_inc(&ref->usage);
190 spin_unlock(&tree->lock);
194 int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
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;
200 BUG_ON(!ref->in_tree);
201 spin_lock(&tree->lock);
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);
209 if (tree->last == ref) {
210 struct rb_node *next = rb_next(&ref->rb_node);
212 tree->last = rb_entry(next, struct btrfs_leaf_ref,
218 rb_erase(&ref->rb_node, &tree->root);
221 spin_unlock(&tree->lock);
223 btrfs_free_leaf_ref(ref);