aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/ordered-data.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/ordered-data.c')
-rw-r--r--fs/btrfs/ordered-data.c455
1 files changed, 285 insertions, 170 deletions
diff --git a/fs/btrfs/ordered-data.c b/fs/btrfs/ordered-data.c
index 254da8225664..6513270f054c 100644
--- a/fs/btrfs/ordered-data.c
+++ b/fs/btrfs/ordered-data.c
@@ -22,48 +22,30 @@
22#include "ctree.h" 22#include "ctree.h"
23#include "transaction.h" 23#include "transaction.h"
24#include "btrfs_inode.h" 24#include "btrfs_inode.h"
25#include "extent_io.h"
25 26
26struct tree_entry {
27 u64 root_objectid;
28 u64 objectid;
29 struct inode *inode;
30 struct rb_node rb_node;
31};
32 27
33/* 28static u64 entry_end(struct btrfs_ordered_extent *entry)
34 * returns > 0 if entry passed (root, objectid) is > entry,
35 * < 0 if (root, objectid) < entry and zero if they are equal
36 */
37static int comp_entry(struct tree_entry *entry, u64 root_objectid,
38 u64 objectid)
39{ 29{
40 if (root_objectid < entry->root_objectid) 30 if (entry->file_offset + entry->len < entry->file_offset)
41 return -1; 31 return (u64)-1;
42 if (root_objectid > entry->root_objectid) 32 return entry->file_offset + entry->len;
43 return 1;
44 if (objectid < entry->objectid)
45 return -1;
46 if (objectid > entry->objectid)
47 return 1;
48 return 0;
49} 33}
50 34
51static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid, 35static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset,
52 u64 objectid, struct rb_node *node) 36 struct rb_node *node)
53{ 37{
54 struct rb_node ** p = &root->rb_node; 38 struct rb_node ** p = &root->rb_node;
55 struct rb_node * parent = NULL; 39 struct rb_node * parent = NULL;
56 struct tree_entry *entry; 40 struct btrfs_ordered_extent *entry;
57 int comp;
58 41
59 while(*p) { 42 while(*p) {
60 parent = *p; 43 parent = *p;
61 entry = rb_entry(parent, struct tree_entry, rb_node); 44 entry = rb_entry(parent, struct btrfs_ordered_extent, rb_node);
62 45
63 comp = comp_entry(entry, root_objectid, objectid); 46 if (file_offset < entry->file_offset)
64 if (comp < 0)
65 p = &(*p)->rb_left; 47 p = &(*p)->rb_left;
66 else if (comp > 0) 48 else if (file_offset >= entry_end(entry))
67 p = &(*p)->rb_right; 49 p = &(*p)->rb_right;
68 else 50 else
69 return parent; 51 return parent;
@@ -74,24 +56,23 @@ static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid,
74 return NULL; 56 return NULL;
75} 57}
76 58
77static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid, 59static struct rb_node *__tree_search(struct rb_root *root, u64 file_offset,
78 u64 objectid, struct rb_node **prev_ret) 60 struct rb_node **prev_ret)
79{ 61{
80 struct rb_node * n = root->rb_node; 62 struct rb_node * n = root->rb_node;
81 struct rb_node *prev = NULL; 63 struct rb_node *prev = NULL;
82 struct tree_entry *entry; 64 struct rb_node *test;
83 struct tree_entry *prev_entry = NULL; 65 struct btrfs_ordered_extent *entry;
84 int comp; 66 struct btrfs_ordered_extent *prev_entry = NULL;
85 67
86 while(n) { 68 while(n) {
87 entry = rb_entry(n, struct tree_entry, rb_node); 69 entry = rb_entry(n, struct btrfs_ordered_extent, rb_node);
88 prev = n; 70 prev = n;
89 prev_entry = entry; 71 prev_entry = entry;
90 comp = comp_entry(entry, root_objectid, objectid);
91 72
92 if (comp < 0) 73 if (file_offset < entry->file_offset)
93 n = n->rb_left; 74 n = n->rb_left;
94 else if (comp > 0) 75 else if (file_offset >= entry_end(entry))
95 n = n->rb_right; 76 n = n->rb_right;
96 else 77 else
97 return n; 78 return n;
@@ -99,195 +80,329 @@ static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid,
99 if (!prev_ret) 80 if (!prev_ret)
100 return NULL; 81 return NULL;
101 82
102 while(prev && comp_entry(prev_entry, root_objectid, objectid) >= 0) { 83 while(prev && file_offset >= entry_end(prev_entry)) {
103 prev = rb_next(prev); 84 test = rb_next(prev);
104 prev_entry = rb_entry(prev, struct tree_entry, rb_node); 85 if (!test)
86 break;
87 prev_entry = rb_entry(test, struct btrfs_ordered_extent,
88 rb_node);
89 if (file_offset < entry_end(prev_entry))
90 break;
91
92 prev = test;
93 }
94 if (prev)
95 prev_entry = rb_entry(prev, struct btrfs_ordered_extent,
96 rb_node);
97 while(prev && file_offset < entry_end(prev_entry)) {
98 test = rb_prev(prev);
99 if (!test)
100 break;
101 prev_entry = rb_entry(test, struct btrfs_ordered_extent,
102 rb_node);
103 prev = test;
105 } 104 }
106 *prev_ret = prev; 105 *prev_ret = prev;
107 return NULL; 106 return NULL;
108} 107}
109 108
110static inline struct rb_node *tree_search(struct rb_root *root, 109static int offset_in_entry(struct btrfs_ordered_extent *entry, u64 file_offset)
111 u64 root_objectid, u64 objectid) 110{
111 if (file_offset < entry->file_offset ||
112 entry->file_offset + entry->len <= file_offset)
113 return 0;
114 return 1;
115}
116
117static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree,
118 u64 file_offset)
112{ 119{
120 struct rb_root *root = &tree->tree;
113 struct rb_node *prev; 121 struct rb_node *prev;
114 struct rb_node *ret; 122 struct rb_node *ret;
115 ret = __tree_search(root, root_objectid, objectid, &prev); 123 struct btrfs_ordered_extent *entry;
124
125 if (tree->last) {
126 entry = rb_entry(tree->last, struct btrfs_ordered_extent,
127 rb_node);
128 if (offset_in_entry(entry, file_offset))
129 return tree->last;
130 }
131 ret = __tree_search(root, file_offset, &prev);
116 if (!ret) 132 if (!ret)
117 return prev; 133 ret = prev;
134 if (ret)
135 tree->last = ret;
118 return ret; 136 return ret;
119} 137}
120 138
121int btrfs_add_ordered_inode(struct inode *inode) 139int btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
140 u64 start, u64 len)
122{ 141{
123 struct btrfs_root *root = BTRFS_I(inode)->root;
124 u64 root_objectid = root->root_key.objectid;
125 u64 transid = root->fs_info->running_transaction->transid;
126 struct tree_entry *entry;
127 struct rb_node *node;
128 struct btrfs_ordered_inode_tree *tree; 142 struct btrfs_ordered_inode_tree *tree;
143 struct rb_node *node;
144 struct btrfs_ordered_extent *entry;
129 145
130 if (transid <= BTRFS_I(inode)->ordered_trans) 146 tree = &BTRFS_I(inode)->ordered_tree;
131 return 0; 147 entry = kzalloc(sizeof(*entry), GFP_NOFS);
132
133 tree = &root->fs_info->running_transaction->ordered_inode_tree;
134
135 read_lock(&tree->lock);
136 node = __tree_search(&tree->tree, root_objectid, inode->i_ino, NULL);
137 read_unlock(&tree->lock);
138 if (node) {
139 return 0;
140 }
141
142 entry = kmalloc(sizeof(*entry), GFP_NOFS);
143 if (!entry) 148 if (!entry)
144 return -ENOMEM; 149 return -ENOMEM;
145 150
146 write_lock(&tree->lock); 151 mutex_lock(&tree->mutex);
147 entry->objectid = inode->i_ino; 152 entry->file_offset = file_offset;
148 entry->root_objectid = root_objectid; 153 entry->start = start;
154 entry->len = len;
149 entry->inode = inode; 155 entry->inode = inode;
156 /* one ref for the tree */
157 atomic_set(&entry->refs, 1);
158 init_waitqueue_head(&entry->wait);
159 INIT_LIST_HEAD(&entry->list);
150 160
151 node = tree_insert(&tree->tree, root_objectid, 161 node = tree_insert(&tree->tree, file_offset,
152 inode->i_ino, &entry->rb_node); 162 &entry->rb_node);
153 163 if (node) {
154 BTRFS_I(inode)->ordered_trans = transid; 164 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
155 if (!node) 165 atomic_inc(&entry->refs);
156 igrab(inode); 166 }
157 167 set_extent_ordered(&BTRFS_I(inode)->io_tree, file_offset,
158 write_unlock(&tree->lock); 168 entry_end(entry) - 1, GFP_NOFS);
159 169
160 if (node) 170 set_bit(BTRFS_ORDERED_START, &entry->flags);
161 kfree(entry); 171 mutex_unlock(&tree->mutex);
172 BUG_ON(node);
162 return 0; 173 return 0;
163} 174}
164 175
165int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, 176int btrfs_add_ordered_sum(struct inode *inode, struct btrfs_ordered_sum *sum)
166 u64 *root_objectid, u64 *objectid,
167 struct inode **inode)
168{ 177{
169 struct tree_entry *entry; 178 struct btrfs_ordered_inode_tree *tree;
170 struct rb_node *node; 179 struct rb_node *node;
180 struct btrfs_ordered_extent *entry;
171 181
172 write_lock(&tree->lock); 182 tree = &BTRFS_I(inode)->ordered_tree;
173 node = tree_search(&tree->tree, *root_objectid, *objectid); 183 mutex_lock(&tree->mutex);
184 node = tree_search(tree, sum->file_offset);
174 if (!node) { 185 if (!node) {
175 write_unlock(&tree->lock); 186search_fail:
176 return 0; 187printk("add ordered sum failed to find a node for inode %lu offset %Lu\n", inode->i_ino, sum->file_offset);
188 node = rb_first(&tree->tree);
189 while(node) {
190 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
191 printk("entry %Lu %Lu %Lu\n", entry->file_offset, entry->file_offset + entry->len, entry->start);
192 node = rb_next(node);
193 }
194 BUG();
177 } 195 }
178 entry = rb_entry(node, struct tree_entry, rb_node); 196 BUG_ON(!node);
179 197
180 while(comp_entry(entry, *root_objectid, *objectid) >= 0) { 198 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
181 node = rb_next(node); 199 if (!offset_in_entry(entry, sum->file_offset)) {
182 if (!node) 200 goto search_fail;
183 break;
184 entry = rb_entry(node, struct tree_entry, rb_node);
185 }
186 if (!node) {
187 write_unlock(&tree->lock);
188 return 0;
189 } 201 }
190 202
191 *root_objectid = entry->root_objectid; 203 list_add_tail(&sum->list, &entry->list);
192 *inode = entry->inode; 204 mutex_unlock(&tree->mutex);
193 atomic_inc(&entry->inode->i_count); 205 return 0;
194 *objectid = entry->objectid;
195 write_unlock(&tree->lock);
196 return 1;
197} 206}
198 207
199int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, 208int btrfs_dec_test_ordered_pending(struct inode *inode,
200 u64 *root_objectid, u64 *objectid, 209 u64 file_offset, u64 io_size)
201 struct inode **inode)
202{ 210{
203 struct tree_entry *entry; 211 struct btrfs_ordered_inode_tree *tree;
204 struct rb_node *node; 212 struct rb_node *node;
205 213 struct btrfs_ordered_extent *entry;
206 write_lock(&tree->lock); 214 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
207 node = tree_search(&tree->tree, *root_objectid, *objectid); 215 int ret;
216
217 tree = &BTRFS_I(inode)->ordered_tree;
218 mutex_lock(&tree->mutex);
219 clear_extent_ordered(io_tree, file_offset, file_offset + io_size - 1,
220 GFP_NOFS);
221 node = tree_search(tree, file_offset);
208 if (!node) { 222 if (!node) {
209 write_unlock(&tree->lock); 223 ret = 1;
210 return 0; 224 goto out;
211 } 225 }
212 226
213 entry = rb_entry(node, struct tree_entry, rb_node); 227 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
214 while(comp_entry(entry, *root_objectid, *objectid) >= 0) { 228 if (!offset_in_entry(entry, file_offset)) {
215 node = rb_next(node); 229 ret = 1;
216 if (!node) 230 goto out;
217 break;
218 entry = rb_entry(node, struct tree_entry, rb_node);
219 } 231 }
220 if (!node) { 232
221 write_unlock(&tree->lock); 233 ret = test_range_bit(io_tree, entry->file_offset,
222 return 0; 234 entry->file_offset + entry->len - 1,
235 EXTENT_ORDERED, 0);
236 if (!test_bit(BTRFS_ORDERED_START, &entry->flags)) {
237printk("inode %lu not ready yet for extent %Lu %Lu\n", inode->i_ino, entry->file_offset, entry_end(entry));
223 } 238 }
239 if (ret == 0)
240 ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags);
241out:
242 mutex_unlock(&tree->mutex);
243 return ret == 0;
244}
224 245
225 *root_objectid = entry->root_objectid; 246int btrfs_put_ordered_extent(struct btrfs_ordered_extent *entry)
226 *objectid = entry->objectid; 247{
227 *inode = entry->inode; 248 if (atomic_dec_and_test(&entry->refs))
228 atomic_inc(&entry->inode->i_count); 249 kfree(entry);
229 rb_erase(node, &tree->tree); 250 return 0;
230 write_unlock(&tree->lock);
231 kfree(entry);
232 return 1;
233} 251}
234 252
235static void __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree, 253int btrfs_remove_ordered_extent(struct inode *inode,
236 struct inode *inode, 254 struct btrfs_ordered_extent *entry)
237 u64 root_objectid, u64 objectid)
238{ 255{
239 struct tree_entry *entry; 256 struct btrfs_ordered_inode_tree *tree;
240 struct rb_node *node; 257 struct rb_node *node;
241 struct rb_node *prev;
242 258
243 write_lock(&tree->lock); 259 tree = &BTRFS_I(inode)->ordered_tree;
244 node = __tree_search(&tree->tree, root_objectid, objectid, &prev); 260 mutex_lock(&tree->mutex);
245 if (!node) { 261 node = &entry->rb_node;
246 write_unlock(&tree->lock);
247 return;
248 }
249 rb_erase(node, &tree->tree); 262 rb_erase(node, &tree->tree);
250 BTRFS_I(inode)->ordered_trans = 0; 263 tree->last = NULL;
251 write_unlock(&tree->lock); 264 set_bit(BTRFS_ORDERED_COMPLETE, &entry->flags);
252 atomic_dec(&inode->i_count); 265 mutex_unlock(&tree->mutex);
253 entry = rb_entry(node, struct tree_entry, rb_node); 266 wake_up(&entry->wait);
254 kfree(entry); 267 return 0;
255 return;
256} 268}
257 269
258void btrfs_del_ordered_inode(struct inode *inode, int force) 270void btrfs_wait_ordered_extent(struct inode *inode,
271 struct btrfs_ordered_extent *entry)
259{ 272{
260 struct btrfs_root *root = BTRFS_I(inode)->root; 273 u64 start = entry->file_offset;
261 u64 root_objectid = root->root_key.objectid; 274 u64 end = start + entry->len - 1;
275#if LINUX_VERSION_CODE < KERNEL_VERSION(2,6,22)
276 do_sync_file_range(file, start, end, SYNC_FILE_RANGE_WRITE);
277#else
278 do_sync_mapping_range(inode->i_mapping, start, end,
279 SYNC_FILE_RANGE_WRITE);
280#endif
281 wait_event(entry->wait,
282 test_bit(BTRFS_ORDERED_COMPLETE, &entry->flags));
283}
262 284
263 if (!BTRFS_I(inode)->ordered_trans) { 285static void btrfs_start_ordered_extent(struct inode *inode,
264 return; 286 struct btrfs_ordered_extent *entry, int wait)
265 } 287{
288 u64 start = entry->file_offset;
289 u64 end = start + entry->len - 1;
266 290
267 if (!force && (mapping_tagged(inode->i_mapping, PAGECACHE_TAG_DIRTY) || 291#if LINUX_VERSION_CODE < KERNEL_VERSION(2,6,22)
268 mapping_tagged(inode->i_mapping, PAGECACHE_TAG_WRITEBACK))) 292 do_sync_file_range(file, start, end, SYNC_FILE_RANGE_WRITE);
269 return; 293#else
294 do_sync_mapping_range(inode->i_mapping, start, end,
295 SYNC_FILE_RANGE_WRITE);
296#endif
297 if (wait)
298 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE,
299 &entry->flags));
300}
270 301
271 spin_lock(&root->fs_info->new_trans_lock); 302void btrfs_wait_ordered_range(struct inode *inode, u64 start, u64 len)
272 if (root->fs_info->running_transaction) { 303{
273 struct btrfs_ordered_inode_tree *tree; 304 u64 end;
274 tree = &root->fs_info->running_transaction->ordered_inode_tree; 305 struct btrfs_ordered_extent *ordered;
275 __btrfs_del_ordered_inode(tree, inode, root_objectid, 306 int found;
276 inode->i_ino); 307 int should_wait = 0;
308
309again:
310 if (start + len < start)
311 end = (u64)-1;
312 else
313 end = start + len - 1;
314 found = 0;
315 while(1) {
316 ordered = btrfs_lookup_first_ordered_extent(inode, end);
317 if (!ordered) {
318 break;
319 }
320 if (ordered->file_offset >= start + len) {
321 btrfs_put_ordered_extent(ordered);
322 break;
323 }
324 if (ordered->file_offset + ordered->len < start) {
325 btrfs_put_ordered_extent(ordered);
326 break;
327 }
328 btrfs_start_ordered_extent(inode, ordered, should_wait);
329 found++;
330 end = ordered->file_offset;
331 btrfs_put_ordered_extent(ordered);
332 if (end == 0)
333 break;
334 end--;
335 }
336 if (should_wait && found) {
337 should_wait = 0;
338 goto again;
277 } 339 }
278 spin_unlock(&root->fs_info->new_trans_lock);
279} 340}
280 341
281int btrfs_ordered_throttle(struct btrfs_root *root, struct inode *inode) 342int btrfs_add_ordered_pending(struct inode *inode,
343 struct btrfs_ordered_extent *ordered,
344 u64 start, u64 len)
282{ 345{
283 struct btrfs_transaction *cur = root->fs_info->running_transaction; 346 WARN_ON(1);
284 while(cur == root->fs_info->running_transaction &&
285 atomic_read(&BTRFS_I(inode)->ordered_writeback)) {
286#if LINUX_VERSION_CODE > KERNEL_VERSION(2,6,18)
287 congestion_wait(WRITE, HZ/20);
288#else
289 blk_congestion_wait(WRITE, HZ/20);
290#endif
291 }
292 return 0; 347 return 0;
348#if 0
349 int ret;
350 struct btrfs_ordered_inode_tree *tree;
351 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
352
353 tree = &BTRFS_I(inode)->ordered_tree;
354 mutex_lock(&tree->mutex);
355 if (test_bit(BTRFS_ORDERED_IO_DONE, &ordered->flags)) {
356 ret = -EAGAIN;
357 goto out;
358 }
359 set_extent_ordered(io_tree, start, start + len - 1, GFP_NOFS);
360 ret = 0;
361out:
362 mutex_unlock(&tree->mutex);
363 return ret;
364#endif
365}
366
367struct btrfs_ordered_extent *btrfs_lookup_ordered_extent(struct inode *inode,
368 u64 file_offset)
369{
370 struct btrfs_ordered_inode_tree *tree;
371 struct rb_node *node;
372 struct btrfs_ordered_extent *entry = NULL;
373
374 tree = &BTRFS_I(inode)->ordered_tree;
375 mutex_lock(&tree->mutex);
376 node = tree_search(tree, file_offset);
377 if (!node)
378 goto out;
379
380 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
381 if (!offset_in_entry(entry, file_offset))
382 entry = NULL;
383 if (entry)
384 atomic_inc(&entry->refs);
385out:
386 mutex_unlock(&tree->mutex);
387 return entry;
388}
389
390struct btrfs_ordered_extent *
391btrfs_lookup_first_ordered_extent(struct inode * inode, u64 file_offset)
392{
393 struct btrfs_ordered_inode_tree *tree;
394 struct rb_node *node;
395 struct btrfs_ordered_extent *entry = NULL;
396
397 tree = &BTRFS_I(inode)->ordered_tree;
398 mutex_lock(&tree->mutex);
399 node = tree_search(tree, file_offset);
400 if (!node)
401 goto out;
402
403 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
404 atomic_inc(&entry->refs);
405out:
406 mutex_unlock(&tree->mutex);
407 return entry;
293} 408}
generated by cgit v1.2.2 (git 2.25.0) at 2024-10-27 02:18:16 -0400