blob: 3ee51e10c187be432251ca96a9b7fb376815b30b [file] [log] [blame]
Chris Masondc17ff82008-01-08 15:46:30 -05001/*
2 * Copyright (C) 2007 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/gfp.h>
20#include <linux/slab.h>
21#include "ctree.h"
22#include "transaction.h"
23#include "btrfs_inode.h"
24
25struct tree_entry {
26 u64 root_objectid;
27 u64 objectid;
Chris Mason4d5e74b2008-01-16 16:09:22 -050028 struct inode *inode;
Chris Masondc17ff82008-01-08 15:46:30 -050029 struct rb_node rb_node;
30};
31
32/*
33 * returns > 0 if entry passed (root, objectid) is > entry,
34 * < 0 if (root, objectid) < entry and zero if they are equal
35 */
36static int comp_entry(struct tree_entry *entry, u64 root_objectid,
37 u64 objectid)
38{
39 if (root_objectid < entry->root_objectid)
40 return -1;
41 if (root_objectid > entry->root_objectid)
42 return 1;
43 if (objectid < entry->objectid)
44 return -1;
45 if (objectid > entry->objectid)
46 return 1;
47 return 0;
48}
49
50static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid,
51 u64 objectid, struct rb_node *node)
52{
53 struct rb_node ** p = &root->rb_node;
54 struct rb_node * parent = NULL;
55 struct tree_entry *entry;
56 int comp;
57
58 while(*p) {
59 parent = *p;
60 entry = rb_entry(parent, struct tree_entry, rb_node);
61
62 comp = comp_entry(entry, root_objectid, objectid);
63 if (comp < 0)
64 p = &(*p)->rb_left;
65 else if (comp > 0)
66 p = &(*p)->rb_right;
67 else
68 return parent;
69 }
70
71 rb_link_node(node, parent, p);
72 rb_insert_color(node, root);
73 return NULL;
74}
75
76static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid,
77 u64 objectid, struct rb_node **prev_ret)
78{
79 struct rb_node * n = root->rb_node;
80 struct rb_node *prev = NULL;
81 struct tree_entry *entry;
82 struct tree_entry *prev_entry = NULL;
83 int comp;
84
85 while(n) {
86 entry = rb_entry(n, struct tree_entry, rb_node);
87 prev = n;
88 prev_entry = entry;
89 comp = comp_entry(entry, root_objectid, objectid);
90
91 if (comp < 0)
92 n = n->rb_left;
93 else if (comp > 0)
94 n = n->rb_right;
95 else
96 return n;
97 }
98 if (!prev_ret)
99 return NULL;
100
101 while(prev && comp_entry(prev_entry, root_objectid, objectid) >= 0) {
102 prev = rb_next(prev);
103 prev_entry = rb_entry(prev, struct tree_entry, rb_node);
104 }
105 *prev_ret = prev;
106 return NULL;
107}
108
109static inline struct rb_node *tree_search(struct rb_root *root,
110 u64 root_objectid, u64 objectid)
111{
112 struct rb_node *prev;
113 struct rb_node *ret;
114 ret = __tree_search(root, root_objectid, objectid, &prev);
115 if (!ret)
116 return prev;
117 return ret;
118}
119
120int btrfs_add_ordered_inode(struct inode *inode)
121{
122 struct btrfs_root *root = BTRFS_I(inode)->root;
123 u64 root_objectid = root->root_key.objectid;
124 u64 transid = root->fs_info->running_transaction->transid;
125 struct tree_entry *entry;
126 struct rb_node *node;
127 struct btrfs_ordered_inode_tree *tree;
128
129 if (transid <= BTRFS_I(inode)->ordered_trans)
130 return 0;
131
132 tree = &root->fs_info->running_transaction->ordered_inode_tree;
133
134 read_lock(&tree->lock);
135 node = __tree_search(&tree->tree, root_objectid, inode->i_ino, NULL);
136 read_unlock(&tree->lock);
137 if (node) {
138 return 0;
139 }
140
141 entry = kmalloc(sizeof(*entry), GFP_NOFS);
142 if (!entry)
143 return -ENOMEM;
144
145 write_lock(&tree->lock);
146 entry->objectid = inode->i_ino;
147 entry->root_objectid = root_objectid;
Chris Mason4d5e74b2008-01-16 16:09:22 -0500148 entry->inode = inode;
Chris Masondc17ff82008-01-08 15:46:30 -0500149
150 node = tree_insert(&tree->tree, root_objectid,
151 inode->i_ino, &entry->rb_node);
152
153 BTRFS_I(inode)->ordered_trans = transid;
154
155 write_unlock(&tree->lock);
156 if (node)
157 kfree(entry);
Chris Mason2da98f02008-01-16 11:44:43 -0500158 else
159 igrab(inode);
Chris Masondc17ff82008-01-08 15:46:30 -0500160 return 0;
161}
162
163int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
Chris Mason4d5e74b2008-01-16 16:09:22 -0500164 u64 *root_objectid, u64 *objectid,
165 struct inode **inode)
Chris Masondc17ff82008-01-08 15:46:30 -0500166{
167 struct tree_entry *entry;
168 struct rb_node *node;
169
170 write_lock(&tree->lock);
171 node = tree_search(&tree->tree, *root_objectid, *objectid);
172 if (!node) {
173 write_unlock(&tree->lock);
174 return 0;
175 }
176 entry = rb_entry(node, struct tree_entry, rb_node);
177
178 while(comp_entry(entry, *root_objectid, *objectid) >= 0) {
179 node = rb_next(node);
180 if (!node)
181 break;
182 entry = rb_entry(node, struct tree_entry, rb_node);
183 }
184 if (!node) {
185 write_unlock(&tree->lock);
186 return 0;
187 }
188
189 *root_objectid = entry->root_objectid;
Chris Mason4d5e74b2008-01-16 16:09:22 -0500190 *inode = entry->inode;
191 atomic_inc(&entry->inode->i_count);
Chris Masondc17ff82008-01-08 15:46:30 -0500192 *objectid = entry->objectid;
193 write_unlock(&tree->lock);
194 return 1;
195}
196
197int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
Chris Mason4d5e74b2008-01-16 16:09:22 -0500198 u64 *root_objectid, u64 *objectid,
199 struct inode **inode)
Chris Masondc17ff82008-01-08 15:46:30 -0500200{
201 struct tree_entry *entry;
202 struct rb_node *node;
203
204 write_lock(&tree->lock);
205 node = tree_search(&tree->tree, *root_objectid, *objectid);
206 if (!node) {
207 write_unlock(&tree->lock);
208 return 0;
209 }
210
211 entry = rb_entry(node, struct tree_entry, rb_node);
212 while(comp_entry(entry, *root_objectid, *objectid) >= 0) {
213 node = rb_next(node);
214 if (!node)
215 break;
216 entry = rb_entry(node, struct tree_entry, rb_node);
217 }
218 if (!node) {
219 write_unlock(&tree->lock);
220 return 0;
221 }
222
223 *root_objectid = entry->root_objectid;
224 *objectid = entry->objectid;
Chris Mason4d5e74b2008-01-16 16:09:22 -0500225 *inode = entry->inode;
226 atomic_inc(&entry->inode->i_count);
Chris Masondc17ff82008-01-08 15:46:30 -0500227 rb_erase(node, &tree->tree);
228 write_unlock(&tree->lock);
229 kfree(entry);
230 return 1;
231}
Chris Masoncee36a02008-01-15 08:40:48 -0500232
233static int __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree,
Chris Mason2da98f02008-01-16 11:44:43 -0500234 struct inode *inode,
Chris Masoncee36a02008-01-15 08:40:48 -0500235 u64 root_objectid, u64 objectid)
236{
237 struct tree_entry *entry;
238 struct rb_node *node;
239 struct rb_node *prev;
240
241 write_lock(&tree->lock);
242 node = __tree_search(&tree->tree, root_objectid, objectid, &prev);
243 if (!node) {
244 write_unlock(&tree->lock);
245 return 0;
246 }
247 rb_erase(node, &tree->tree);
Chris Mason2da98f02008-01-16 11:44:43 -0500248 BTRFS_I(inode)->ordered_trans = 0;
Chris Masoncee36a02008-01-15 08:40:48 -0500249 write_unlock(&tree->lock);
250 entry = rb_entry(node, struct tree_entry, rb_node);
251 kfree(entry);
252 return 1;
253}
254
255int btrfs_del_ordered_inode(struct inode *inode)
256{
257 struct btrfs_root *root = BTRFS_I(inode)->root;
258 u64 root_objectid = root->root_key.objectid;
Chris Mason2da98f02008-01-16 11:44:43 -0500259 int ret = 0;
Chris Masoncee36a02008-01-15 08:40:48 -0500260
261 spin_lock(&root->fs_info->new_trans_lock);
262 if (root->fs_info->running_transaction) {
263 struct btrfs_ordered_inode_tree *tree;
264 tree = &root->fs_info->running_transaction->ordered_inode_tree;
Chris Mason2da98f02008-01-16 11:44:43 -0500265 ret = __btrfs_del_ordered_inode(tree, inode, root_objectid,
266 inode->i_ino);
Chris Masoncee36a02008-01-15 08:40:48 -0500267 }
268 spin_unlock(&root->fs_info->new_trans_lock);
Chris Mason2da98f02008-01-16 11:44:43 -0500269 return ret;
Chris Masoncee36a02008-01-15 08:40:48 -0500270}
271