2 * Copyright (C) 2007 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/gfp.h>
20 #include <linux/slab.h>
22 #include "transaction.h"
23 #include "btrfs_inode.h"
28 struct rb_node rb_node
;
32 * returns > 0 if entry passed (root, objectid) is > entry,
33 * < 0 if (root, objectid) < entry and zero if they are equal
35 static int comp_entry(struct tree_entry
*entry
, u64 root_objectid
,
38 if (root_objectid
< entry
->root_objectid
)
40 if (root_objectid
> entry
->root_objectid
)
42 if (objectid
< entry
->objectid
)
44 if (objectid
> entry
->objectid
)
49 static struct rb_node
*tree_insert(struct rb_root
*root
, u64 root_objectid
,
50 u64 objectid
, struct rb_node
*node
)
52 struct rb_node
** p
= &root
->rb_node
;
53 struct rb_node
* parent
= NULL
;
54 struct tree_entry
*entry
;
59 entry
= rb_entry(parent
, struct tree_entry
, rb_node
);
61 comp
= comp_entry(entry
, root_objectid
, objectid
);
70 rb_link_node(node
, parent
, p
);
71 rb_insert_color(node
, root
);
75 static struct rb_node
*__tree_search(struct rb_root
*root
, u64 root_objectid
,
76 u64 objectid
, struct rb_node
**prev_ret
)
78 struct rb_node
* n
= root
->rb_node
;
79 struct rb_node
*prev
= NULL
;
80 struct tree_entry
*entry
;
81 struct tree_entry
*prev_entry
= NULL
;
85 entry
= rb_entry(n
, struct tree_entry
, rb_node
);
88 comp
= comp_entry(entry
, root_objectid
, objectid
);
100 while(prev
&& comp_entry(prev_entry
, root_objectid
, objectid
) >= 0) {
101 prev
= rb_next(prev
);
102 prev_entry
= rb_entry(prev
, struct tree_entry
, rb_node
);
108 static inline struct rb_node
*tree_search(struct rb_root
*root
,
109 u64 root_objectid
, u64 objectid
)
111 struct rb_node
*prev
;
113 ret
= __tree_search(root
, root_objectid
, objectid
, &prev
);
119 int btrfs_add_ordered_inode(struct inode
*inode
)
121 struct btrfs_root
*root
= BTRFS_I(inode
)->root
;
122 u64 root_objectid
= root
->root_key
.objectid
;
123 u64 transid
= root
->fs_info
->running_transaction
->transid
;
124 struct tree_entry
*entry
;
125 struct rb_node
*node
;
126 struct btrfs_ordered_inode_tree
*tree
;
128 if (transid
<= BTRFS_I(inode
)->ordered_trans
)
131 tree
= &root
->fs_info
->running_transaction
->ordered_inode_tree
;
133 read_lock(&tree
->lock
);
134 node
= __tree_search(&tree
->tree
, root_objectid
, inode
->i_ino
, NULL
);
135 read_unlock(&tree
->lock
);
140 entry
= kmalloc(sizeof(*entry
), GFP_NOFS
);
144 write_lock(&tree
->lock
);
145 entry
->objectid
= inode
->i_ino
;
146 entry
->root_objectid
= root_objectid
;
148 node
= tree_insert(&tree
->tree
, root_objectid
,
149 inode
->i_ino
, &entry
->rb_node
);
151 BTRFS_I(inode
)->ordered_trans
= transid
;
153 write_unlock(&tree
->lock
);
159 int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree
*tree
,
160 u64
*root_objectid
, u64
*objectid
)
162 struct tree_entry
*entry
;
163 struct rb_node
*node
;
165 write_lock(&tree
->lock
);
166 node
= tree_search(&tree
->tree
, *root_objectid
, *objectid
);
168 write_unlock(&tree
->lock
);
171 entry
= rb_entry(node
, struct tree_entry
, rb_node
);
173 while(comp_entry(entry
, *root_objectid
, *objectid
) >= 0) {
174 node
= rb_next(node
);
177 entry
= rb_entry(node
, struct tree_entry
, rb_node
);
180 write_unlock(&tree
->lock
);
184 *root_objectid
= entry
->root_objectid
;
185 *objectid
= entry
->objectid
;
186 write_unlock(&tree
->lock
);
190 int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree
*tree
,
191 u64
*root_objectid
, u64
*objectid
)
193 struct tree_entry
*entry
;
194 struct rb_node
*node
;
196 write_lock(&tree
->lock
);
197 node
= tree_search(&tree
->tree
, *root_objectid
, *objectid
);
199 write_unlock(&tree
->lock
);
203 entry
= rb_entry(node
, struct tree_entry
, rb_node
);
204 while(comp_entry(entry
, *root_objectid
, *objectid
) >= 0) {
205 node
= rb_next(node
);
208 entry
= rb_entry(node
, struct tree_entry
, rb_node
);
211 write_unlock(&tree
->lock
);
215 *root_objectid
= entry
->root_objectid
;
216 *objectid
= entry
->objectid
;
217 rb_erase(node
, &tree
->tree
);
218 write_unlock(&tree
->lock
);
223 static int __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree
*tree
,
224 u64 root_objectid
, u64 objectid
)
226 struct tree_entry
*entry
;
227 struct rb_node
*node
;
228 struct rb_node
*prev
;
230 write_lock(&tree
->lock
);
231 node
= __tree_search(&tree
->tree
, root_objectid
, objectid
, &prev
);
233 write_unlock(&tree
->lock
);
236 rb_erase(node
, &tree
->tree
);
237 write_unlock(&tree
->lock
);
238 entry
= rb_entry(node
, struct tree_entry
, rb_node
);
243 int btrfs_del_ordered_inode(struct inode
*inode
)
245 struct btrfs_root
*root
= BTRFS_I(inode
)->root
;
246 u64 root_objectid
= root
->root_key
.objectid
;
248 spin_lock(&root
->fs_info
->new_trans_lock
);
249 if (root
->fs_info
->running_transaction
) {
250 struct btrfs_ordered_inode_tree
*tree
;
251 tree
= &root
->fs_info
->running_transaction
->ordered_inode_tree
;
252 __btrfs_del_ordered_inode(tree
, root_objectid
, inode
->i_ino
);
254 spin_unlock(&root
->fs_info
->new_trans_lock
);
This page took 0.043701 seconds and 5 git commands to generate.