Btrfs: rename the scrub context structure
[linux-3.10.git] / fs / btrfs / inode-item.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 "ctree.h"
20 #include "disk-io.h"
21 #include "hash.h"
22 #include "transaction.h"
23 #include "print-tree.h"
24
25 static int find_name_in_backref(struct btrfs_path *path, const char *name,
26                          int name_len, struct btrfs_inode_ref **ref_ret)
27 {
28         struct extent_buffer *leaf;
29         struct btrfs_inode_ref *ref;
30         unsigned long ptr;
31         unsigned long name_ptr;
32         u32 item_size;
33         u32 cur_offset = 0;
34         int len;
35
36         leaf = path->nodes[0];
37         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
38         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
39         while (cur_offset < item_size) {
40                 ref = (struct btrfs_inode_ref *)(ptr + cur_offset);
41                 len = btrfs_inode_ref_name_len(leaf, ref);
42                 name_ptr = (unsigned long)(ref + 1);
43                 cur_offset += len + sizeof(*ref);
44                 if (len != name_len)
45                         continue;
46                 if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) {
47                         *ref_ret = ref;
48                         return 1;
49                 }
50         }
51         return 0;
52 }
53
54 int btrfs_find_name_in_ext_backref(struct btrfs_path *path, u64 ref_objectid,
55                                    const char *name, int name_len,
56                                    struct btrfs_inode_extref **extref_ret)
57 {
58         struct extent_buffer *leaf;
59         struct btrfs_inode_extref *extref;
60         unsigned long ptr;
61         unsigned long name_ptr;
62         u32 item_size;
63         u32 cur_offset = 0;
64         int ref_name_len;
65
66         leaf = path->nodes[0];
67         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
68         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
69
70         /*
71          * Search all extended backrefs in this item. We're only
72          * looking through any collisions so most of the time this is
73          * just going to compare against one buffer. If all is well,
74          * we'll return success and the inode ref object.
75          */
76         while (cur_offset < item_size) {
77                 extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
78                 name_ptr = (unsigned long)(&extref->name);
79                 ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
80
81                 if (ref_name_len == name_len &&
82                     btrfs_inode_extref_parent(leaf, extref) == ref_objectid &&
83                     (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) {
84                         if (extref_ret)
85                                 *extref_ret = extref;
86                         return 1;
87                 }
88
89                 cur_offset += ref_name_len + sizeof(*extref);
90         }
91         return 0;
92 }
93
94 static struct btrfs_inode_ref *
95 btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans,
96                        struct btrfs_root *root,
97                        struct btrfs_path *path,
98                        const char *name, int name_len,
99                        u64 inode_objectid, u64 ref_objectid, int ins_len,
100                        int cow)
101 {
102         int ret;
103         struct btrfs_key key;
104         struct btrfs_inode_ref *ref;
105
106         key.objectid = inode_objectid;
107         key.type = BTRFS_INODE_REF_KEY;
108         key.offset = ref_objectid;
109
110         ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
111         if (ret < 0)
112                 return ERR_PTR(ret);
113         if (ret > 0)
114                 return NULL;
115         if (!find_name_in_backref(path, name, name_len, &ref))
116                 return NULL;
117         return ref;
118 }
119
120 /* Returns NULL if no extref found */
121 struct btrfs_inode_extref *
122 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
123                           struct btrfs_root *root,
124                           struct btrfs_path *path,
125                           const char *name, int name_len,
126                           u64 inode_objectid, u64 ref_objectid, int ins_len,
127                           int cow)
128 {
129         int ret;
130         struct btrfs_key key;
131         struct btrfs_inode_extref *extref;
132
133         key.objectid = inode_objectid;
134         key.type = BTRFS_INODE_EXTREF_KEY;
135         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
136
137         ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
138         if (ret < 0)
139                 return ERR_PTR(ret);
140         if (ret > 0)
141                 return NULL;
142         if (!btrfs_find_name_in_ext_backref(path, ref_objectid, name, name_len, &extref))
143                 return NULL;
144         return extref;
145 }
146
147 int btrfs_get_inode_ref_index(struct btrfs_trans_handle *trans,
148                               struct btrfs_root *root,
149                               struct btrfs_path *path,
150                               const char *name, int name_len,
151                               u64 inode_objectid, u64 ref_objectid, int mod,
152                               u64 *ret_index)
153 {
154         struct btrfs_inode_ref *ref;
155         struct btrfs_inode_extref *extref;
156         int ins_len = mod < 0 ? -1 : 0;
157         int cow = mod != 0;
158
159         ref = btrfs_lookup_inode_ref(trans, root, path, name, name_len,
160                                      inode_objectid, ref_objectid, ins_len,
161                                      cow);
162         if (IS_ERR(ref))
163                 return PTR_ERR(ref);
164
165         if (ref != NULL) {
166                 *ret_index = btrfs_inode_ref_index(path->nodes[0], ref);
167                 return 0;
168         }
169
170         btrfs_release_path(path);
171
172         extref = btrfs_lookup_inode_extref(trans, root, path, name,
173                                            name_len, inode_objectid,
174                                            ref_objectid, ins_len, cow);
175         if (IS_ERR(extref))
176                 return PTR_ERR(extref);
177
178         if (extref) {
179                 *ret_index = btrfs_inode_extref_index(path->nodes[0], extref);
180                 return 0;
181         }
182
183         return -ENOENT;
184 }
185
186 int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
187                            struct btrfs_root *root,
188                            const char *name, int name_len,
189                            u64 inode_objectid, u64 ref_objectid, u64 *index)
190 {
191         struct btrfs_path *path;
192         struct btrfs_key key;
193         struct btrfs_inode_extref *extref;
194         struct extent_buffer *leaf;
195         int ret;
196         int del_len = name_len + sizeof(*extref);
197         unsigned long ptr;
198         unsigned long item_start;
199         u32 item_size;
200
201         key.objectid = inode_objectid;
202         btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY);
203         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
204
205         path = btrfs_alloc_path();
206         if (!path)
207                 return -ENOMEM;
208
209         path->leave_spinning = 1;
210
211         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
212         if (ret > 0)
213                 ret = -ENOENT;
214         if (ret < 0)
215                 goto out;
216
217         /*
218          * Sanity check - did we find the right item for this name?
219          * This should always succeed so error here will make the FS
220          * readonly.
221          */
222         if (!btrfs_find_name_in_ext_backref(path, ref_objectid,
223                                             name, name_len, &extref)) {
224                 btrfs_std_error(root->fs_info, -ENOENT);
225                 ret = -EROFS;
226                 goto out;
227         }
228
229         leaf = path->nodes[0];
230         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
231         if (index)
232                 *index = btrfs_inode_extref_index(leaf, extref);
233
234         if (del_len == item_size) {
235                 /*
236                  * Common case only one ref in the item, remove the
237                  * whole item.
238                  */
239                 ret = btrfs_del_item(trans, root, path);
240                 goto out;
241         }
242
243         ptr = (unsigned long)extref;
244         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
245
246         memmove_extent_buffer(leaf, ptr, ptr + del_len,
247                               item_size - (ptr + del_len - item_start));
248
249         btrfs_truncate_item(trans, root, path, item_size - del_len, 1);
250
251 out:
252         btrfs_free_path(path);
253
254         return ret;
255 }
256
257 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
258                         struct btrfs_root *root,
259                         const char *name, int name_len,
260                         u64 inode_objectid, u64 ref_objectid, u64 *index)
261 {
262         struct btrfs_path *path;
263         struct btrfs_key key;
264         struct btrfs_inode_ref *ref;
265         struct extent_buffer *leaf;
266         unsigned long ptr;
267         unsigned long item_start;
268         u32 item_size;
269         u32 sub_item_len;
270         int ret;
271         int search_ext_refs = 0;
272         int del_len = name_len + sizeof(*ref);
273
274         key.objectid = inode_objectid;
275         key.offset = ref_objectid;
276         btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
277
278         path = btrfs_alloc_path();
279         if (!path)
280                 return -ENOMEM;
281
282         path->leave_spinning = 1;
283
284         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
285         if (ret > 0) {
286                 ret = -ENOENT;
287                 search_ext_refs = 1;
288                 goto out;
289         } else if (ret < 0) {
290                 goto out;
291         }
292         if (!find_name_in_backref(path, name, name_len, &ref)) {
293                 ret = -ENOENT;
294                 search_ext_refs = 1;
295                 goto out;
296         }
297         leaf = path->nodes[0];
298         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
299
300         if (index)
301                 *index = btrfs_inode_ref_index(leaf, ref);
302
303         if (del_len == item_size) {
304                 ret = btrfs_del_item(trans, root, path);
305                 goto out;
306         }
307         ptr = (unsigned long)ref;
308         sub_item_len = name_len + sizeof(*ref);
309         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
310         memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
311                               item_size - (ptr + sub_item_len - item_start));
312         btrfs_truncate_item(trans, root, path, item_size - sub_item_len, 1);
313 out:
314         btrfs_free_path(path);
315
316         if (search_ext_refs) {
317                 /*
318                  * No refs were found, or we could not find the
319                  * name in our ref array. Find and remove the extended
320                  * inode ref then.
321                  */
322                 return btrfs_del_inode_extref(trans, root, name, name_len,
323                                               inode_objectid, ref_objectid, index);
324         }
325
326         return ret;
327 }
328
329 /*
330  * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
331  *
332  * The caller must have checked against BTRFS_LINK_MAX already.
333  */
334 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
335                                      struct btrfs_root *root,
336                                      const char *name, int name_len,
337                                      u64 inode_objectid, u64 ref_objectid, u64 index)
338 {
339         struct btrfs_inode_extref *extref;
340         int ret;
341         int ins_len = name_len + sizeof(*extref);
342         unsigned long ptr;
343         struct btrfs_path *path;
344         struct btrfs_key key;
345         struct extent_buffer *leaf;
346         struct btrfs_item *item;
347
348         key.objectid = inode_objectid;
349         key.type = BTRFS_INODE_EXTREF_KEY;
350         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
351
352         path = btrfs_alloc_path();
353         if (!path)
354                 return -ENOMEM;
355
356         path->leave_spinning = 1;
357         ret = btrfs_insert_empty_item(trans, root, path, &key,
358                                       ins_len);
359         if (ret == -EEXIST) {
360                 if (btrfs_find_name_in_ext_backref(path, ref_objectid,
361                                                    name, name_len, NULL))
362                         goto out;
363
364                 btrfs_extend_item(trans, root, path, ins_len);
365                 ret = 0;
366         }
367         if (ret < 0)
368                 goto out;
369
370         leaf = path->nodes[0];
371         item = btrfs_item_nr(leaf, path->slots[0]);
372         ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
373         ptr += btrfs_item_size(leaf, item) - ins_len;
374         extref = (struct btrfs_inode_extref *)ptr;
375
376         btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
377         btrfs_set_inode_extref_index(path->nodes[0], extref, index);
378         btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
379
380         ptr = (unsigned long)&extref->name;
381         write_extent_buffer(path->nodes[0], name, ptr, name_len);
382         btrfs_mark_buffer_dirty(path->nodes[0]);
383
384 out:
385         btrfs_free_path(path);
386         return ret;
387 }
388
389 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
390 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
391                            struct btrfs_root *root,
392                            const char *name, int name_len,
393                            u64 inode_objectid, u64 ref_objectid, u64 index)
394 {
395         struct btrfs_path *path;
396         struct btrfs_key key;
397         struct btrfs_inode_ref *ref;
398         unsigned long ptr;
399         int ret;
400         int ins_len = name_len + sizeof(*ref);
401
402         key.objectid = inode_objectid;
403         key.offset = ref_objectid;
404         btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
405
406         path = btrfs_alloc_path();
407         if (!path)
408                 return -ENOMEM;
409
410         path->leave_spinning = 1;
411         ret = btrfs_insert_empty_item(trans, root, path, &key,
412                                       ins_len);
413         if (ret == -EEXIST) {
414                 u32 old_size;
415
416                 if (find_name_in_backref(path, name, name_len, &ref))
417                         goto out;
418
419                 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
420                 btrfs_extend_item(trans, root, path, ins_len);
421                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
422                                      struct btrfs_inode_ref);
423                 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
424                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
425                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
426                 ptr = (unsigned long)(ref + 1);
427                 ret = 0;
428         } else if (ret < 0) {
429                 if (ret == -EOVERFLOW)
430                         ret = -EMLINK;
431                 goto out;
432         } else {
433                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
434                                      struct btrfs_inode_ref);
435                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
436                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
437                 ptr = (unsigned long)(ref + 1);
438         }
439         write_extent_buffer(path->nodes[0], name, ptr, name_len);
440         btrfs_mark_buffer_dirty(path->nodes[0]);
441
442 out:
443         btrfs_free_path(path);
444
445         if (ret == -EMLINK) {
446                 struct btrfs_super_block *disk_super = root->fs_info->super_copy;
447                 /* We ran out of space in the ref array. Need to
448                  * add an extended ref. */
449                 if (btrfs_super_incompat_flags(disk_super)
450                     & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
451                         ret = btrfs_insert_inode_extref(trans, root, name,
452                                                         name_len,
453                                                         inode_objectid,
454                                                         ref_objectid, index);
455         }
456
457         return ret;
458 }
459
460 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
461                              struct btrfs_root *root,
462                              struct btrfs_path *path, u64 objectid)
463 {
464         struct btrfs_key key;
465         int ret;
466         key.objectid = objectid;
467         btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY);
468         key.offset = 0;
469
470         ret = btrfs_insert_empty_item(trans, root, path, &key,
471                                       sizeof(struct btrfs_inode_item));
472         return ret;
473 }
474
475 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
476                        *root, struct btrfs_path *path,
477                        struct btrfs_key *location, int mod)
478 {
479         int ins_len = mod < 0 ? -1 : 0;
480         int cow = mod != 0;
481         int ret;
482         int slot;
483         struct extent_buffer *leaf;
484         struct btrfs_key found_key;
485
486         ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
487         if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY &&
488             location->offset == (u64)-1 && path->slots[0] != 0) {
489                 slot = path->slots[0] - 1;
490                 leaf = path->nodes[0];
491                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
492                 if (found_key.objectid == location->objectid &&
493                     btrfs_key_type(&found_key) == btrfs_key_type(location)) {
494                         path->slots[0]--;
495                         return 0;
496                 }
497         }
498         return ret;
499 }