Btrfs: Add a per-inode csum mutex to avoid races creating csum items
[linux-3.10.git] / fs / btrfs / ordered-data.c
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 <linux/blkdev.h>
22 #include "ctree.h"
23 #include "transaction.h"
24 #include "btrfs_inode.h"
25
26 struct tree_entry {
27         u64 root_objectid;
28         u64 objectid;
29         struct inode *inode;
30         struct rb_node rb_node;
31 };
32
33 /*
34  * returns > 0 if entry passed (root, objectid) is > entry,
35  * < 0 if (root, objectid) < entry and zero if they are equal
36  */
37 static int comp_entry(struct tree_entry *entry, u64 root_objectid,
38                       u64 objectid)
39 {
40         if (root_objectid < entry->root_objectid)
41                 return -1;
42         if (root_objectid > entry->root_objectid)
43                 return 1;
44         if (objectid < entry->objectid)
45                 return -1;
46         if (objectid > entry->objectid)
47                 return 1;
48         return 0;
49 }
50
51 static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid,
52                                    u64 objectid, struct rb_node *node)
53 {
54         struct rb_node ** p = &root->rb_node;
55         struct rb_node * parent = NULL;
56         struct tree_entry *entry;
57         int comp;
58
59         while(*p) {
60                 parent = *p;
61                 entry = rb_entry(parent, struct tree_entry, rb_node);
62
63                 comp = comp_entry(entry, root_objectid, objectid);
64                 if (comp < 0)
65                         p = &(*p)->rb_left;
66                 else if (comp > 0)
67                         p = &(*p)->rb_right;
68                 else
69                         return parent;
70         }
71
72         rb_link_node(node, parent, p);
73         rb_insert_color(node, root);
74         return NULL;
75 }
76
77 static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid,
78                                      u64 objectid, struct rb_node **prev_ret)
79 {
80         struct rb_node * n = root->rb_node;
81         struct rb_node *prev = NULL;
82         struct tree_entry *entry;
83         struct tree_entry *prev_entry = NULL;
84         int comp;
85
86         while(n) {
87                 entry = rb_entry(n, struct tree_entry, rb_node);
88                 prev = n;
89                 prev_entry = entry;
90                 comp = comp_entry(entry, root_objectid, objectid);
91
92                 if (comp < 0)
93                         n = n->rb_left;
94                 else if (comp > 0)
95                         n = n->rb_right;
96                 else
97                         return n;
98         }
99         if (!prev_ret)
100                 return NULL;
101
102         while(prev && comp_entry(prev_entry, root_objectid, objectid) >= 0) {
103                 prev = rb_next(prev);
104                 prev_entry = rb_entry(prev, struct tree_entry, rb_node);
105         }
106         *prev_ret = prev;
107         return NULL;
108 }
109
110 static inline struct rb_node *tree_search(struct rb_root *root,
111                                           u64 root_objectid, u64 objectid)
112 {
113         struct rb_node *prev;
114         struct rb_node *ret;
115         ret = __tree_search(root, root_objectid, objectid, &prev);
116         if (!ret)
117                 return prev;
118         return ret;
119 }
120
121 int btrfs_add_ordered_inode(struct inode *inode)
122 {
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;
129
130         if (transid <= BTRFS_I(inode)->ordered_trans)
131                 return 0;
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)
144                 return -ENOMEM;
145
146         write_lock(&tree->lock);
147         entry->objectid = inode->i_ino;
148         entry->root_objectid = root_objectid;
149         entry->inode = inode;
150
151         node = tree_insert(&tree->tree, root_objectid,
152                            inode->i_ino, &entry->rb_node);
153
154         BTRFS_I(inode)->ordered_trans = transid;
155         if (!node)
156                 igrab(inode);
157
158         write_unlock(&tree->lock);
159
160         if (node)
161                 kfree(entry);
162         return 0;
163 }
164
165 int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
166                                    u64 *root_objectid, u64 *objectid,
167                                    struct inode **inode)
168 {
169         struct tree_entry *entry;
170         struct rb_node *node;
171
172         write_lock(&tree->lock);
173         node = tree_search(&tree->tree, *root_objectid, *objectid);
174         if (!node) {
175                 write_unlock(&tree->lock);
176                 return 0;
177         }
178         entry = rb_entry(node, struct tree_entry, rb_node);
179
180         while(comp_entry(entry, *root_objectid, *objectid) >= 0) {
181                 node = rb_next(node);
182                 if (!node)
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         }
190
191         *root_objectid = entry->root_objectid;
192         *inode = entry->inode;
193         atomic_inc(&entry->inode->i_count);
194         *objectid = entry->objectid;
195         write_unlock(&tree->lock);
196         return 1;
197 }
198
199 int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
200                                        u64 *root_objectid, u64 *objectid,
201                                        struct inode **inode)
202 {
203         struct tree_entry *entry;
204         struct rb_node *node;
205
206         write_lock(&tree->lock);
207         node = tree_search(&tree->tree, *root_objectid, *objectid);
208         if (!node) {
209                 write_unlock(&tree->lock);
210                 return 0;
211         }
212
213         entry = rb_entry(node, struct tree_entry, rb_node);
214         while(comp_entry(entry, *root_objectid, *objectid) >= 0) {
215                 node = rb_next(node);
216                 if (!node)
217                         break;
218                 entry = rb_entry(node, struct tree_entry, rb_node);
219         }
220         if (!node) {
221                 write_unlock(&tree->lock);
222                 return 0;
223         }
224
225         *root_objectid = entry->root_objectid;
226         *objectid = entry->objectid;
227         *inode = entry->inode;
228         atomic_inc(&entry->inode->i_count);
229         rb_erase(node, &tree->tree);
230         write_unlock(&tree->lock);
231         kfree(entry);
232         return 1;
233 }
234
235 static void __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree,
236                                      struct inode *inode,
237                                      u64 root_objectid, u64 objectid)
238 {
239         struct tree_entry *entry;
240         struct rb_node *node;
241         struct rb_node *prev;
242
243         write_lock(&tree->lock);
244         node = __tree_search(&tree->tree, root_objectid, objectid, &prev);
245         if (!node) {
246                 write_unlock(&tree->lock);
247                 return;
248         }
249         rb_erase(node, &tree->tree);
250         BTRFS_I(inode)->ordered_trans = 0;
251         write_unlock(&tree->lock);
252         atomic_dec(&inode->i_count);
253         entry = rb_entry(node, struct tree_entry, rb_node);
254         kfree(entry);
255         return;
256 }
257
258 void btrfs_del_ordered_inode(struct inode *inode, int force)
259 {
260         struct btrfs_root *root = BTRFS_I(inode)->root;
261         u64 root_objectid = root->root_key.objectid;
262
263         if (!BTRFS_I(inode)->ordered_trans) {
264                 return;
265         }
266
267         if (!force && (mapping_tagged(inode->i_mapping, PAGECACHE_TAG_DIRTY) ||
268             mapping_tagged(inode->i_mapping, PAGECACHE_TAG_WRITEBACK)))
269                 return;
270
271         spin_lock(&root->fs_info->new_trans_lock);
272         if (root->fs_info->running_transaction) {
273                 struct btrfs_ordered_inode_tree *tree;
274                 tree = &root->fs_info->running_transaction->ordered_inode_tree;
275                  __btrfs_del_ordered_inode(tree, inode, root_objectid,
276                                                 inode->i_ino);
277         }
278         spin_unlock(&root->fs_info->new_trans_lock);
279 }
280
281 int btrfs_ordered_throttle(struct btrfs_root *root, struct inode *inode)
282 {
283         struct btrfs_transaction *cur = root->fs_info->running_transaction;
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;
293 }