Commit | Line | Data |
---|---|---|
dc17ff8f CM |
1 | /* |
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 | ||
25 | struct tree_entry { | |
26 | u64 root_objectid; | |
27 | u64 objectid; | |
28 | struct rb_node rb_node; | |
29 | }; | |
30 | ||
31 | /* | |
32 | * returns > 0 if entry passed (root, objectid) is > entry, | |
33 | * < 0 if (root, objectid) < entry and zero if they are equal | |
34 | */ | |
35 | static int comp_entry(struct tree_entry *entry, u64 root_objectid, | |
36 | u64 objectid) | |
37 | { | |
38 | if (root_objectid < entry->root_objectid) | |
39 | return -1; | |
40 | if (root_objectid > entry->root_objectid) | |
41 | return 1; | |
42 | if (objectid < entry->objectid) | |
43 | return -1; | |
44 | if (objectid > entry->objectid) | |
45 | return 1; | |
46 | return 0; | |
47 | } | |
48 | ||
49 | static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid, | |
50 | u64 objectid, struct rb_node *node) | |
51 | { | |
52 | struct rb_node ** p = &root->rb_node; | |
53 | struct rb_node * parent = NULL; | |
54 | struct tree_entry *entry; | |
55 | int comp; | |
56 | ||
57 | while(*p) { | |
58 | parent = *p; | |
59 | entry = rb_entry(parent, struct tree_entry, rb_node); | |
60 | ||
61 | comp = comp_entry(entry, root_objectid, objectid); | |
62 | if (comp < 0) | |
63 | p = &(*p)->rb_left; | |
64 | else if (comp > 0) | |
65 | p = &(*p)->rb_right; | |
66 | else | |
67 | return parent; | |
68 | } | |
69 | ||
70 | rb_link_node(node, parent, p); | |
71 | rb_insert_color(node, root); | |
72 | return NULL; | |
73 | } | |
74 | ||
75 | static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid, | |
76 | u64 objectid, struct rb_node **prev_ret) | |
77 | { | |
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; | |
82 | int comp; | |
83 | ||
84 | while(n) { | |
85 | entry = rb_entry(n, struct tree_entry, rb_node); | |
86 | prev = n; | |
87 | prev_entry = entry; | |
88 | comp = comp_entry(entry, root_objectid, objectid); | |
89 | ||
90 | if (comp < 0) | |
91 | n = n->rb_left; | |
92 | else if (comp > 0) | |
93 | n = n->rb_right; | |
94 | else | |
95 | return n; | |
96 | } | |
97 | if (!prev_ret) | |
98 | return NULL; | |
99 | ||
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); | |
103 | } | |
104 | *prev_ret = prev; | |
105 | return NULL; | |
106 | } | |
107 | ||
108 | static inline struct rb_node *tree_search(struct rb_root *root, | |
109 | u64 root_objectid, u64 objectid) | |
110 | { | |
111 | struct rb_node *prev; | |
112 | struct rb_node *ret; | |
113 | ret = __tree_search(root, root_objectid, objectid, &prev); | |
114 | if (!ret) | |
115 | return prev; | |
116 | return ret; | |
117 | } | |
118 | ||
119 | int btrfs_add_ordered_inode(struct inode *inode) | |
120 | { | |
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; | |
127 | ||
128 | if (transid <= BTRFS_I(inode)->ordered_trans) | |
129 | return 0; | |
130 | ||
131 | tree = &root->fs_info->running_transaction->ordered_inode_tree; | |
132 | ||
133 | read_lock(&tree->lock); | |
134 | node = __tree_search(&tree->tree, root_objectid, inode->i_ino, NULL); | |
135 | read_unlock(&tree->lock); | |
136 | if (node) { | |
137 | return 0; | |
138 | } | |
139 | ||
140 | entry = kmalloc(sizeof(*entry), GFP_NOFS); | |
141 | if (!entry) | |
142 | return -ENOMEM; | |
143 | ||
144 | write_lock(&tree->lock); | |
145 | entry->objectid = inode->i_ino; | |
146 | entry->root_objectid = root_objectid; | |
147 | ||
148 | node = tree_insert(&tree->tree, root_objectid, | |
149 | inode->i_ino, &entry->rb_node); | |
150 | ||
151 | BTRFS_I(inode)->ordered_trans = transid; | |
152 | ||
153 | write_unlock(&tree->lock); | |
154 | if (node) | |
155 | kfree(entry); | |
156 | return 0; | |
157 | } | |
158 | ||
159 | int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, | |
160 | u64 *root_objectid, u64 *objectid) | |
161 | { | |
162 | struct tree_entry *entry; | |
163 | struct rb_node *node; | |
164 | ||
165 | write_lock(&tree->lock); | |
166 | node = tree_search(&tree->tree, *root_objectid, *objectid); | |
167 | if (!node) { | |
168 | write_unlock(&tree->lock); | |
169 | return 0; | |
170 | } | |
171 | entry = rb_entry(node, struct tree_entry, rb_node); | |
172 | ||
173 | while(comp_entry(entry, *root_objectid, *objectid) >= 0) { | |
174 | node = rb_next(node); | |
175 | if (!node) | |
176 | break; | |
177 | entry = rb_entry(node, struct tree_entry, rb_node); | |
178 | } | |
179 | if (!node) { | |
180 | write_unlock(&tree->lock); | |
181 | return 0; | |
182 | } | |
183 | ||
184 | *root_objectid = entry->root_objectid; | |
185 | *objectid = entry->objectid; | |
186 | write_unlock(&tree->lock); | |
187 | return 1; | |
188 | } | |
189 | ||
190 | int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, | |
191 | u64 *root_objectid, u64 *objectid) | |
192 | { | |
193 | struct tree_entry *entry; | |
194 | struct rb_node *node; | |
195 | ||
196 | write_lock(&tree->lock); | |
197 | node = tree_search(&tree->tree, *root_objectid, *objectid); | |
198 | if (!node) { | |
199 | write_unlock(&tree->lock); | |
200 | return 0; | |
201 | } | |
202 | ||
203 | entry = rb_entry(node, struct tree_entry, rb_node); | |
204 | while(comp_entry(entry, *root_objectid, *objectid) >= 0) { | |
205 | node = rb_next(node); | |
206 | if (!node) | |
207 | break; | |
208 | entry = rb_entry(node, struct tree_entry, rb_node); | |
209 | } | |
210 | if (!node) { | |
211 | write_unlock(&tree->lock); | |
212 | return 0; | |
213 | } | |
214 | ||
215 | *root_objectid = entry->root_objectid; | |
216 | *objectid = entry->objectid; | |
217 | rb_erase(node, &tree->tree); | |
218 | write_unlock(&tree->lock); | |
219 | kfree(entry); | |
220 | return 1; | |
221 | } |