blob: e0b7034d6343eb053d195834cdb88beef7c57689 [file] [log] [blame]
Chris Mason6cbd5572007-06-12 09:07:21 -04001/*
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
Chris Mason1e1d2702007-03-15 19:03:33 -040019#include "ctree.h"
20#include "disk-io.h"
Mark Fashehf1863732012-08-08 11:32:27 -070021#include "hash.h"
Chris Masone089f052007-03-16 16:20:31 -040022#include "transaction.h"
Chris Mason727011e2010-08-06 13:21:20 -040023#include "print-tree.h"
Chris Mason1e1d2702007-03-15 19:03:33 -040024
Christoph Hellwigb2950862008-12-02 09:54:17 -050025static int find_name_in_backref(struct btrfs_path *path, const char *name,
Chris Mason39544012007-12-12 14:38:19 -050026 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
Mark Fashehf1863732012-08-08 11:32:27 -070054int 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)
Yan, Zhenga22285a2010-05-16 10:48:46 -040057{
Mark Fashehf1863732012-08-08 11:32:27 -070058 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
94static struct btrfs_inode_ref *
95btrfs_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;
Yan, Zhenga22285a2010-05-16 10:48:46 -0400103 struct btrfs_key key;
104 struct btrfs_inode_ref *ref;
Yan, Zhenga22285a2010-05-16 10:48:46 -0400105
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
Mark Fashehf1863732012-08-08 11:32:27 -0700120/* Returns NULL if no extref found */
121struct btrfs_inode_extref *
122btrfs_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
147int 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
Eric Sandeen48a3b632013-04-25 20:41:01 +0000186static 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,
190 u64 *index)
Chris Mason39544012007-12-12 14:38:19 -0500191{
192 struct btrfs_path *path;
193 struct btrfs_key key;
Mark Fashehf1863732012-08-08 11:32:27 -0700194 struct btrfs_inode_extref *extref;
195 struct extent_buffer *leaf;
196 int ret;
197 int del_len = name_len + sizeof(*extref);
198 unsigned long ptr;
199 unsigned long item_start;
200 u32 item_size;
201
202 key.objectid = inode_objectid;
203 btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY);
204 key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
205
206 path = btrfs_alloc_path();
207 if (!path)
208 return -ENOMEM;
209
210 path->leave_spinning = 1;
211
212 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
213 if (ret > 0)
214 ret = -ENOENT;
215 if (ret < 0)
216 goto out;
217
218 /*
219 * Sanity check - did we find the right item for this name?
220 * This should always succeed so error here will make the FS
221 * readonly.
222 */
223 if (!btrfs_find_name_in_ext_backref(path, ref_objectid,
224 name, name_len, &extref)) {
225 btrfs_std_error(root->fs_info, -ENOENT);
226 ret = -EROFS;
227 goto out;
228 }
229
230 leaf = path->nodes[0];
231 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
232 if (index)
233 *index = btrfs_inode_extref_index(leaf, extref);
234
235 if (del_len == item_size) {
236 /*
237 * Common case only one ref in the item, remove the
238 * whole item.
239 */
240 ret = btrfs_del_item(trans, root, path);
241 goto out;
242 }
243
244 ptr = (unsigned long)extref;
245 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
246
247 memmove_extent_buffer(leaf, ptr, ptr + del_len,
248 item_size - (ptr + del_len - item_start));
249
Tsutomu Itohafe5fea2013-04-16 05:18:22 +0000250 btrfs_truncate_item(root, path, item_size - del_len, 1);
Mark Fashehf1863732012-08-08 11:32:27 -0700251
252out:
253 btrfs_free_path(path);
254
255 return ret;
256}
257
258int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
259 struct btrfs_root *root,
260 const char *name, int name_len,
261 u64 inode_objectid, u64 ref_objectid, u64 *index)
262{
263 struct btrfs_path *path;
264 struct btrfs_key key;
Chris Mason39544012007-12-12 14:38:19 -0500265 struct btrfs_inode_ref *ref;
266 struct extent_buffer *leaf;
267 unsigned long ptr;
268 unsigned long item_start;
269 u32 item_size;
270 u32 sub_item_len;
271 int ret;
Mark Fashehf1863732012-08-08 11:32:27 -0700272 int search_ext_refs = 0;
Chris Mason39544012007-12-12 14:38:19 -0500273 int del_len = name_len + sizeof(*ref);
274
275 key.objectid = inode_objectid;
276 key.offset = ref_objectid;
277 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
278
279 path = btrfs_alloc_path();
280 if (!path)
281 return -ENOMEM;
282
Chris Masonb9473432009-03-13 11:00:37 -0400283 path->leave_spinning = 1;
284
Chris Mason39544012007-12-12 14:38:19 -0500285 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
286 if (ret > 0) {
287 ret = -ENOENT;
Mark Fashehf1863732012-08-08 11:32:27 -0700288 search_ext_refs = 1;
Chris Mason39544012007-12-12 14:38:19 -0500289 goto out;
290 } else if (ret < 0) {
291 goto out;
292 }
293 if (!find_name_in_backref(path, name, name_len, &ref)) {
294 ret = -ENOENT;
Mark Fashehf1863732012-08-08 11:32:27 -0700295 search_ext_refs = 1;
Chris Mason39544012007-12-12 14:38:19 -0500296 goto out;
297 }
298 leaf = path->nodes[0];
299 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
Josef Bacikaec74772008-07-24 12:12:38 -0400300
301 if (index)
302 *index = btrfs_inode_ref_index(leaf, ref);
303
Chris Mason39544012007-12-12 14:38:19 -0500304 if (del_len == item_size) {
305 ret = btrfs_del_item(trans, root, path);
306 goto out;
307 }
308 ptr = (unsigned long)ref;
309 sub_item_len = name_len + sizeof(*ref);
310 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
311 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
312 item_size - (ptr + sub_item_len - item_start));
Tsutomu Itohafe5fea2013-04-16 05:18:22 +0000313 btrfs_truncate_item(root, path, item_size - sub_item_len, 1);
Mark Fashehf1863732012-08-08 11:32:27 -0700314out:
315 btrfs_free_path(path);
316
317 if (search_ext_refs) {
318 /*
319 * No refs were found, or we could not find the
320 * name in our ref array. Find and remove the extended
321 * inode ref then.
322 */
323 return btrfs_del_inode_extref(trans, root, name, name_len,
324 inode_objectid, ref_objectid, index);
325 }
326
327 return ret;
328}
329
330/*
331 * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
332 *
333 * The caller must have checked against BTRFS_LINK_MAX already.
334 */
335static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
336 struct btrfs_root *root,
337 const char *name, int name_len,
338 u64 inode_objectid, u64 ref_objectid, u64 index)
339{
340 struct btrfs_inode_extref *extref;
341 int ret;
342 int ins_len = name_len + sizeof(*extref);
343 unsigned long ptr;
344 struct btrfs_path *path;
345 struct btrfs_key key;
346 struct extent_buffer *leaf;
347 struct btrfs_item *item;
348
349 key.objectid = inode_objectid;
350 key.type = BTRFS_INODE_EXTREF_KEY;
351 key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
352
353 path = btrfs_alloc_path();
354 if (!path)
355 return -ENOMEM;
356
357 path->leave_spinning = 1;
358 ret = btrfs_insert_empty_item(trans, root, path, &key,
359 ins_len);
360 if (ret == -EEXIST) {
361 if (btrfs_find_name_in_ext_backref(path, ref_objectid,
362 name, name_len, NULL))
363 goto out;
364
Tsutomu Itoh4b90c682013-04-16 05:18:49 +0000365 btrfs_extend_item(root, path, ins_len);
Mark Fashehf1863732012-08-08 11:32:27 -0700366 ret = 0;
367 }
368 if (ret < 0)
369 goto out;
370
371 leaf = path->nodes[0];
372 item = btrfs_item_nr(leaf, path->slots[0]);
373 ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
374 ptr += btrfs_item_size(leaf, item) - ins_len;
375 extref = (struct btrfs_inode_extref *)ptr;
376
377 btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
378 btrfs_set_inode_extref_index(path->nodes[0], extref, index);
379 btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
380
381 ptr = (unsigned long)&extref->name;
382 write_extent_buffer(path->nodes[0], name, ptr, name_len);
383 btrfs_mark_buffer_dirty(path->nodes[0]);
384
Chris Mason39544012007-12-12 14:38:19 -0500385out:
386 btrfs_free_path(path);
387 return ret;
388}
389
Jeff Mahoney79787ea2012-03-12 16:03:00 +0100390/* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
Chris Mason39544012007-12-12 14:38:19 -0500391int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
392 struct btrfs_root *root,
393 const char *name, int name_len,
Josef Bacikaec74772008-07-24 12:12:38 -0400394 u64 inode_objectid, u64 ref_objectid, u64 index)
Chris Mason39544012007-12-12 14:38:19 -0500395{
396 struct btrfs_path *path;
397 struct btrfs_key key;
398 struct btrfs_inode_ref *ref;
399 unsigned long ptr;
400 int ret;
401 int ins_len = name_len + sizeof(*ref);
402
403 key.objectid = inode_objectid;
404 key.offset = ref_objectid;
405 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
406
407 path = btrfs_alloc_path();
408 if (!path)
409 return -ENOMEM;
410
Chris Masonb9473432009-03-13 11:00:37 -0400411 path->leave_spinning = 1;
Chris Mason39544012007-12-12 14:38:19 -0500412 ret = btrfs_insert_empty_item(trans, root, path, &key,
413 ins_len);
414 if (ret == -EEXIST) {
415 u32 old_size;
416
417 if (find_name_in_backref(path, name, name_len, &ref))
418 goto out;
419
420 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
Tsutomu Itoh4b90c682013-04-16 05:18:49 +0000421 btrfs_extend_item(root, path, ins_len);
Chris Mason39544012007-12-12 14:38:19 -0500422 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
423 struct btrfs_inode_ref);
424 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
425 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
Josef Bacikaec74772008-07-24 12:12:38 -0400426 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
Chris Mason39544012007-12-12 14:38:19 -0500427 ptr = (unsigned long)(ref + 1);
428 ret = 0;
429 } else if (ret < 0) {
Yan, Zhenga5719522009-09-24 09:17:31 -0400430 if (ret == -EOVERFLOW)
431 ret = -EMLINK;
Chris Mason39544012007-12-12 14:38:19 -0500432 goto out;
433 } else {
434 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
435 struct btrfs_inode_ref);
436 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
Josef Bacikaec74772008-07-24 12:12:38 -0400437 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
Chris Mason39544012007-12-12 14:38:19 -0500438 ptr = (unsigned long)(ref + 1);
439 }
440 write_extent_buffer(path->nodes[0], name, ptr, name_len);
441 btrfs_mark_buffer_dirty(path->nodes[0]);
442
443out:
444 btrfs_free_path(path);
Mark Fashehf1863732012-08-08 11:32:27 -0700445
446 if (ret == -EMLINK) {
447 struct btrfs_super_block *disk_super = root->fs_info->super_copy;
448 /* We ran out of space in the ref array. Need to
449 * add an extended ref. */
450 if (btrfs_super_incompat_flags(disk_super)
451 & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
452 ret = btrfs_insert_inode_extref(trans, root, name,
453 name_len,
454 inode_objectid,
455 ref_objectid, index);
456 }
457
Chris Mason39544012007-12-12 14:38:19 -0500458 return ret;
459}
460
Chris Mason5f39d392007-10-15 16:14:19 -0400461int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
462 struct btrfs_root *root,
463 struct btrfs_path *path, u64 objectid)
Chris Mason1e1d2702007-03-15 19:03:33 -0400464{
Chris Mason1e1d2702007-03-15 19:03:33 -0400465 struct btrfs_key key;
466 int ret;
467 key.objectid = objectid;
Chris Mason1e1d2702007-03-15 19:03:33 -0400468 btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY);
469 key.offset = 0;
470
Chris Mason5f39d392007-10-15 16:14:19 -0400471 ret = btrfs_insert_empty_item(trans, root, path, &key,
472 sizeof(struct btrfs_inode_item));
Chris Mason1e1d2702007-03-15 19:03:33 -0400473 return ret;
474}
475
Chris Masone089f052007-03-16 16:20:31 -0400476int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masond6e4a422007-04-06 15:37:36 -0400477 *root, struct btrfs_path *path,
478 struct btrfs_key *location, int mod)
Chris Mason1e1d2702007-03-15 19:03:33 -0400479{
Chris Mason1e1d2702007-03-15 19:03:33 -0400480 int ins_len = mod < 0 ? -1 : 0;
481 int cow = mod != 0;
Chris Masond6e4a422007-04-06 15:37:36 -0400482 int ret;
483 int slot;
Chris Mason5f39d392007-10-15 16:14:19 -0400484 struct extent_buffer *leaf;
Chris Masond6e4a422007-04-06 15:37:36 -0400485 struct btrfs_key found_key;
Chris Mason1e1d2702007-03-15 19:03:33 -0400486
Chris Masond6e4a422007-04-06 15:37:36 -0400487 ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
488 if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY &&
489 location->offset == (u64)-1 && path->slots[0] != 0) {
490 slot = path->slots[0] - 1;
Chris Mason5f39d392007-10-15 16:14:19 -0400491 leaf = path->nodes[0];
492 btrfs_item_key_to_cpu(leaf, &found_key, slot);
Chris Masond6e4a422007-04-06 15:37:36 -0400493 if (found_key.objectid == location->objectid &&
494 btrfs_key_type(&found_key) == btrfs_key_type(location)) {
495 path->slots[0]--;
496 return 0;
497 }
498 }
499 return ret;
Chris Mason1e1d2702007-03-15 19:03:33 -0400500}