GNU Linux-libre 4.9.308-gnu1
[releases.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 /* Returns NULL if no extref found */
95 struct btrfs_inode_extref *
96 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
97                           struct btrfs_root *root,
98                           struct btrfs_path *path,
99                           const char *name, int name_len,
100                           u64 inode_objectid, u64 ref_objectid, int ins_len,
101                           int cow)
102 {
103         int ret;
104         struct btrfs_key key;
105         struct btrfs_inode_extref *extref;
106
107         key.objectid = inode_objectid;
108         key.type = BTRFS_INODE_EXTREF_KEY;
109         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
110
111         ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
112         if (ret < 0)
113                 return ERR_PTR(ret);
114         if (ret > 0)
115                 return NULL;
116         if (!btrfs_find_name_in_ext_backref(path, ref_objectid, name, name_len, &extref))
117                 return NULL;
118         return extref;
119 }
120
121 static int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
122                                   struct btrfs_root *root,
123                                   const char *name, int name_len,
124                                   u64 inode_objectid, u64 ref_objectid,
125                                   u64 *index)
126 {
127         struct btrfs_path *path;
128         struct btrfs_key key;
129         struct btrfs_inode_extref *extref;
130         struct extent_buffer *leaf;
131         int ret;
132         int del_len = name_len + sizeof(*extref);
133         unsigned long ptr;
134         unsigned long item_start;
135         u32 item_size;
136
137         key.objectid = inode_objectid;
138         key.type = BTRFS_INODE_EXTREF_KEY;
139         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
140
141         path = btrfs_alloc_path();
142         if (!path)
143                 return -ENOMEM;
144
145         path->leave_spinning = 1;
146
147         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
148         if (ret > 0)
149                 ret = -ENOENT;
150         if (ret < 0)
151                 goto out;
152
153         /*
154          * Sanity check - did we find the right item for this name?
155          * This should always succeed so error here will make the FS
156          * readonly.
157          */
158         if (!btrfs_find_name_in_ext_backref(path, ref_objectid,
159                                             name, name_len, &extref)) {
160                 btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL);
161                 ret = -EROFS;
162                 goto out;
163         }
164
165         leaf = path->nodes[0];
166         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
167         if (index)
168                 *index = btrfs_inode_extref_index(leaf, extref);
169
170         if (del_len == item_size) {
171                 /*
172                  * Common case only one ref in the item, remove the
173                  * whole item.
174                  */
175                 ret = btrfs_del_item(trans, root, path);
176                 goto out;
177         }
178
179         ptr = (unsigned long)extref;
180         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
181
182         memmove_extent_buffer(leaf, ptr, ptr + del_len,
183                               item_size - (ptr + del_len - item_start));
184
185         btrfs_truncate_item(root, path, item_size - del_len, 1);
186
187 out:
188         btrfs_free_path(path);
189
190         return ret;
191 }
192
193 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
194                         struct btrfs_root *root,
195                         const char *name, int name_len,
196                         u64 inode_objectid, u64 ref_objectid, u64 *index)
197 {
198         struct btrfs_path *path;
199         struct btrfs_key key;
200         struct btrfs_inode_ref *ref;
201         struct extent_buffer *leaf;
202         unsigned long ptr;
203         unsigned long item_start;
204         u32 item_size;
205         u32 sub_item_len;
206         int ret;
207         int search_ext_refs = 0;
208         int del_len = name_len + sizeof(*ref);
209
210         key.objectid = inode_objectid;
211         key.offset = ref_objectid;
212         key.type = BTRFS_INODE_REF_KEY;
213
214         path = btrfs_alloc_path();
215         if (!path)
216                 return -ENOMEM;
217
218         path->leave_spinning = 1;
219
220         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
221         if (ret > 0) {
222                 ret = -ENOENT;
223                 search_ext_refs = 1;
224                 goto out;
225         } else if (ret < 0) {
226                 goto out;
227         }
228         if (!find_name_in_backref(path, name, name_len, &ref)) {
229                 ret = -ENOENT;
230                 search_ext_refs = 1;
231                 goto out;
232         }
233         leaf = path->nodes[0];
234         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
235
236         if (index)
237                 *index = btrfs_inode_ref_index(leaf, ref);
238
239         if (del_len == item_size) {
240                 ret = btrfs_del_item(trans, root, path);
241                 goto out;
242         }
243         ptr = (unsigned long)ref;
244         sub_item_len = name_len + sizeof(*ref);
245         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
246         memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
247                               item_size - (ptr + sub_item_len - item_start));
248         btrfs_truncate_item(root, path, item_size - sub_item_len, 1);
249 out:
250         btrfs_free_path(path);
251
252         if (search_ext_refs) {
253                 /*
254                  * No refs were found, or we could not find the
255                  * name in our ref array. Find and remove the extended
256                  * inode ref then.
257                  */
258                 return btrfs_del_inode_extref(trans, root, name, name_len,
259                                               inode_objectid, ref_objectid, index);
260         }
261
262         return ret;
263 }
264
265 /*
266  * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
267  *
268  * The caller must have checked against BTRFS_LINK_MAX already.
269  */
270 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
271                                      struct btrfs_root *root,
272                                      const char *name, int name_len,
273                                      u64 inode_objectid, u64 ref_objectid, u64 index)
274 {
275         struct btrfs_inode_extref *extref;
276         int ret;
277         int ins_len = name_len + sizeof(*extref);
278         unsigned long ptr;
279         struct btrfs_path *path;
280         struct btrfs_key key;
281         struct extent_buffer *leaf;
282         struct btrfs_item *item;
283
284         key.objectid = inode_objectid;
285         key.type = BTRFS_INODE_EXTREF_KEY;
286         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
287
288         path = btrfs_alloc_path();
289         if (!path)
290                 return -ENOMEM;
291
292         path->leave_spinning = 1;
293         ret = btrfs_insert_empty_item(trans, root, path, &key,
294                                       ins_len);
295         if (ret == -EEXIST) {
296                 if (btrfs_find_name_in_ext_backref(path, ref_objectid,
297                                                    name, name_len, NULL))
298                         goto out;
299
300                 btrfs_extend_item(root, path, ins_len);
301                 ret = 0;
302         }
303         if (ret < 0)
304                 goto out;
305
306         leaf = path->nodes[0];
307         item = btrfs_item_nr(path->slots[0]);
308         ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
309         ptr += btrfs_item_size(leaf, item) - ins_len;
310         extref = (struct btrfs_inode_extref *)ptr;
311
312         btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
313         btrfs_set_inode_extref_index(path->nodes[0], extref, index);
314         btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
315
316         ptr = (unsigned long)&extref->name;
317         write_extent_buffer(path->nodes[0], name, ptr, name_len);
318         btrfs_mark_buffer_dirty(path->nodes[0]);
319
320 out:
321         btrfs_free_path(path);
322         return ret;
323 }
324
325 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
326 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
327                            struct btrfs_root *root,
328                            const char *name, int name_len,
329                            u64 inode_objectid, u64 ref_objectid, u64 index)
330 {
331         struct btrfs_path *path;
332         struct btrfs_key key;
333         struct btrfs_inode_ref *ref;
334         unsigned long ptr;
335         int ret;
336         int ins_len = name_len + sizeof(*ref);
337
338         key.objectid = inode_objectid;
339         key.offset = ref_objectid;
340         key.type = BTRFS_INODE_REF_KEY;
341
342         path = btrfs_alloc_path();
343         if (!path)
344                 return -ENOMEM;
345
346         path->leave_spinning = 1;
347         path->skip_release_on_error = 1;
348         ret = btrfs_insert_empty_item(trans, root, path, &key,
349                                       ins_len);
350         if (ret == -EEXIST) {
351                 u32 old_size;
352
353                 if (find_name_in_backref(path, name, name_len, &ref))
354                         goto out;
355
356                 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
357                 btrfs_extend_item(root, path, ins_len);
358                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
359                                      struct btrfs_inode_ref);
360                 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
361                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
362                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
363                 ptr = (unsigned long)(ref + 1);
364                 ret = 0;
365         } else if (ret < 0) {
366                 if (ret == -EOVERFLOW) {
367                         if (find_name_in_backref(path, name, name_len, &ref))
368                                 ret = -EEXIST;
369                         else
370                                 ret = -EMLINK;
371                 }
372                 goto out;
373         } else {
374                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
375                                      struct btrfs_inode_ref);
376                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
377                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
378                 ptr = (unsigned long)(ref + 1);
379         }
380         write_extent_buffer(path->nodes[0], name, ptr, name_len);
381         btrfs_mark_buffer_dirty(path->nodes[0]);
382
383 out:
384         btrfs_free_path(path);
385
386         if (ret == -EMLINK) {
387                 struct btrfs_super_block *disk_super = root->fs_info->super_copy;
388                 /* We ran out of space in the ref array. Need to
389                  * add an extended ref. */
390                 if (btrfs_super_incompat_flags(disk_super)
391                     & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
392                         ret = btrfs_insert_inode_extref(trans, root, name,
393                                                         name_len,
394                                                         inode_objectid,
395                                                         ref_objectid, index);
396         }
397
398         return ret;
399 }
400
401 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
402                              struct btrfs_root *root,
403                              struct btrfs_path *path, u64 objectid)
404 {
405         struct btrfs_key key;
406         int ret;
407         key.objectid = objectid;
408         key.type = BTRFS_INODE_ITEM_KEY;
409         key.offset = 0;
410
411         ret = btrfs_insert_empty_item(trans, root, path, &key,
412                                       sizeof(struct btrfs_inode_item));
413         return ret;
414 }
415
416 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
417                        *root, struct btrfs_path *path,
418                        struct btrfs_key *location, int mod)
419 {
420         int ins_len = mod < 0 ? -1 : 0;
421         int cow = mod != 0;
422         int ret;
423         int slot;
424         struct extent_buffer *leaf;
425         struct btrfs_key found_key;
426
427         ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
428         if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY &&
429             location->offset == (u64)-1 && path->slots[0] != 0) {
430                 slot = path->slots[0] - 1;
431                 leaf = path->nodes[0];
432                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
433                 if (found_key.objectid == location->objectid &&
434                     found_key.type == location->type) {
435                         path->slots[0]--;
436                         return 0;
437                 }
438         }
439         return ret;
440 }