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> | |
20 | #include "ctree.h" | |
21 | #include "ref-cache.h" | |
22 | #include "transaction.h" | |
23 | ||
bcc63abb Y |
24 | struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(struct btrfs_root *root, |
25 | int nr_extents) | |
31153d81 YZ |
26 | { |
27 | struct btrfs_leaf_ref *ref; | |
bcc63abb | 28 | size_t size = btrfs_leaf_ref_size(nr_extents); |
31153d81 | 29 | |
bcc63abb | 30 | ref = kmalloc(size, GFP_NOFS); |
31153d81 | 31 | if (ref) { |
bcc63abb Y |
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 | ||
31153d81 YZ |
36 | memset(ref, 0, sizeof(*ref)); |
37 | atomic_set(&ref->usage, 1); | |
017e5369 | 38 | INIT_LIST_HEAD(&ref->list); |
31153d81 YZ |
39 | } |
40 | return ref; | |
41 | } | |
42 | ||
bcc63abb | 43 | void btrfs_free_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) |
31153d81 YZ |
44 | { |
45 | if (!ref) | |
46 | return; | |
47 | WARN_ON(atomic_read(&ref->usage) == 0); | |
48 | if (atomic_dec_and_test(&ref->usage)) { | |
bcc63abb Y |
49 | size_t size = btrfs_leaf_ref_size(ref->nritems); |
50 | ||
31153d81 YZ |
51 | BUG_ON(ref->in_tree); |
52 | kfree(ref); | |
bcc63abb Y |
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); | |
31153d81 YZ |
57 | } |
58 | } | |
59 | ||
017e5369 | 60 | static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr, |
31153d81 YZ |
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; | |
31153d81 YZ |
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 | ||
017e5369 | 72 | if (bytenr < entry->bytenr) |
31153d81 | 73 | p = &(*p)->rb_left; |
017e5369 | 74 | else if (bytenr > entry->bytenr) |
31153d81 YZ |
75 | p = &(*p)->rb_right; |
76 | else | |
77 | return parent; | |
78 | } | |
bcc63abb | 79 | |
31153d81 YZ |
80 | entry = rb_entry(node, struct btrfs_leaf_ref, rb_node); |
81 | entry->in_tree = 1; | |
82 | rb_link_node(node, parent, p); | |
83 | rb_insert_color(node, root); | |
84 | return NULL; | |
85 | } | |
86 | ||
017e5369 | 87 | static struct rb_node *tree_search(struct rb_root *root, u64 bytenr) |
31153d81 YZ |
88 | { |
89 | struct rb_node * n = root->rb_node; | |
90 | struct btrfs_leaf_ref *entry; | |
31153d81 YZ |
91 | |
92 | while(n) { | |
93 | entry = rb_entry(n, struct btrfs_leaf_ref, rb_node); | |
94 | WARN_ON(!entry->in_tree); | |
95 | ||
017e5369 | 96 | if (bytenr < entry->bytenr) |
31153d81 | 97 | n = n->rb_left; |
017e5369 | 98 | else if (bytenr > entry->bytenr) |
31153d81 YZ |
99 | n = n->rb_right; |
100 | else | |
101 | return n; | |
102 | } | |
103 | return NULL; | |
104 | } | |
105 | ||
bcc63abb | 106 | int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen) |
31153d81 | 107 | { |
31153d81 YZ |
108 | struct btrfs_leaf_ref *ref = NULL; |
109 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; | |
110 | ||
111 | if (!tree) | |
112 | return 0; | |
113 | ||
114 | spin_lock(&tree->lock); | |
bcc63abb Y |
115 | while(!list_empty(&tree->list)) { |
116 | ref = list_entry(tree->list.next, struct btrfs_leaf_ref, list); | |
117 | BUG_ON(!ref->in_tree); | |
118 | if (ref->root_gen > max_root_gen) | |
119 | break; | |
120 | ||
31153d81 YZ |
121 | rb_erase(&ref->rb_node, &tree->root); |
122 | ref->in_tree = 0; | |
017e5369 | 123 | list_del_init(&ref->list); |
31153d81 YZ |
124 | |
125 | spin_unlock(&tree->lock); | |
bcc63abb | 126 | btrfs_free_leaf_ref(root, ref); |
31153d81 YZ |
127 | cond_resched(); |
128 | spin_lock(&tree->lock); | |
129 | } | |
130 | spin_unlock(&tree->lock); | |
131 | return 0; | |
132 | } | |
133 | ||
134 | struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root, | |
017e5369 | 135 | u64 bytenr) |
31153d81 YZ |
136 | { |
137 | struct rb_node *rb; | |
138 | struct btrfs_leaf_ref *ref = NULL; | |
139 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; | |
140 | ||
141 | if (!tree) | |
142 | return NULL; | |
143 | ||
144 | spin_lock(&tree->lock); | |
017e5369 CM |
145 | rb = tree_search(&tree->root, bytenr); |
146 | if (rb) | |
147 | ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node); | |
31153d81 YZ |
148 | if (ref) |
149 | atomic_inc(&ref->usage); | |
150 | spin_unlock(&tree->lock); | |
151 | return ref; | |
152 | } | |
153 | ||
154 | int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) | |
155 | { | |
156 | int ret = 0; | |
157 | struct rb_node *rb; | |
31153d81 | 158 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
31153d81 YZ |
159 | |
160 | spin_lock(&tree->lock); | |
017e5369 | 161 | rb = tree_insert(&tree->root, ref->bytenr, &ref->rb_node); |
31153d81 YZ |
162 | if (rb) { |
163 | ret = -EEXIST; | |
164 | } else { | |
31153d81 | 165 | atomic_inc(&ref->usage); |
017e5369 | 166 | list_add_tail(&ref->list, &tree->list); |
31153d81 YZ |
167 | } |
168 | spin_unlock(&tree->lock); | |
169 | return ret; | |
170 | } | |
171 | ||
172 | int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) | |
173 | { | |
31153d81 | 174 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
31153d81 YZ |
175 | |
176 | BUG_ON(!ref->in_tree); | |
177 | spin_lock(&tree->lock); | |
31153d81 | 178 | |
31153d81 YZ |
179 | rb_erase(&ref->rb_node, &tree->root); |
180 | ref->in_tree = 0; | |
017e5369 | 181 | list_del_init(&ref->list); |
31153d81 YZ |
182 | |
183 | spin_unlock(&tree->lock); | |
184 | ||
bcc63abb | 185 | btrfs_free_leaf_ref(root, ref); |
31153d81 YZ |
186 | return 0; |
187 | } |