blob: 48b8fda93132b799b695efc4f1bd9e59cca1f064 [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
186int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
Chris Mason39544012007-12-12 14:38:19 -0500187 struct btrfs_root *root,
188 const char *name, int name_len,
Josef Bacikaec74772008-07-24 12:12:38 -0400189 u64 inode_objectid, u64 ref_objectid, u64 *index)
Chris Mason39544012007-12-12 14:38:19 -0500190{
191 struct btrfs_path *path;
192 struct btrfs_key key;
Mark Fashehf1863732012-08-08 11:32:27 -0700193 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
251out:
252 btrfs_free_path(path);
253
254 return ret;
255}
256
257int 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;
Chris Mason39544012007-12-12 14:38:19 -0500264 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;
Mark Fashehf1863732012-08-08 11:32:27 -0700271 int search_ext_refs = 0;
Chris Mason39544012007-12-12 14:38:19 -0500272 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
Chris Masonb9473432009-03-13 11:00:37 -0400282 path->leave_spinning = 1;
283
Chris Mason39544012007-12-12 14:38:19 -0500284 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
285 if (ret > 0) {
286 ret = -ENOENT;
Mark Fashehf1863732012-08-08 11:32:27 -0700287 search_ext_refs = 1;
Chris Mason39544012007-12-12 14:38:19 -0500288 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;
Mark Fashehf1863732012-08-08 11:32:27 -0700294 search_ext_refs = 1;
Chris Mason39544012007-12-12 14:38:19 -0500295 goto out;
296 }
297 leaf = path->nodes[0];
298 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
Josef Bacikaec74772008-07-24 12:12:38 -0400299
300 if (index)
301 *index = btrfs_inode_ref_index(leaf, ref);
302
Chris Mason39544012007-12-12 14:38:19 -0500303 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));
Mark Fashehf1863732012-08-08 11:32:27 -0700312 btrfs_truncate_item(trans, root, path, item_size - sub_item_len, 1);
313out:
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 */
334static 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
Chris Mason39544012007-12-12 14:38:19 -0500384out:
385 btrfs_free_path(path);
386 return ret;
387}
388
Jeff Mahoney79787ea2012-03-12 16:03:00 +0100389/* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
Chris Mason39544012007-12-12 14:38:19 -0500390int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
391 struct btrfs_root *root,
392 const char *name, int name_len,
Josef Bacikaec74772008-07-24 12:12:38 -0400393 u64 inode_objectid, u64 ref_objectid, u64 index)
Chris Mason39544012007-12-12 14:38:19 -0500394{
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
Chris Masonb9473432009-03-13 11:00:37 -0400410 path->leave_spinning = 1;
Chris Mason39544012007-12-12 14:38:19 -0500411 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]);
Jeff Mahoney143bede2012-03-01 14:56:26 +0100420 btrfs_extend_item(trans, root, path, ins_len);
Chris Mason39544012007-12-12 14:38:19 -0500421 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);
Josef Bacikaec74772008-07-24 12:12:38 -0400425 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
Chris Mason39544012007-12-12 14:38:19 -0500426 ptr = (unsigned long)(ref + 1);
427 ret = 0;
428 } else if (ret < 0) {
Yan, Zhenga5719522009-09-24 09:17:31 -0400429 if (ret == -EOVERFLOW)
430 ret = -EMLINK;
Chris Mason39544012007-12-12 14:38:19 -0500431 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);
Josef Bacikaec74772008-07-24 12:12:38 -0400436 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
Chris Mason39544012007-12-12 14:38:19 -0500437 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
442out:
443 btrfs_free_path(path);
Mark Fashehf1863732012-08-08 11:32:27 -0700444
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
Chris Mason39544012007-12-12 14:38:19 -0500457 return ret;
458}
459
Chris Mason5f39d392007-10-15 16:14:19 -0400460int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
461 struct btrfs_root *root,
462 struct btrfs_path *path, u64 objectid)
Chris Mason1e1d2702007-03-15 19:03:33 -0400463{
Chris Mason1e1d2702007-03-15 19:03:33 -0400464 struct btrfs_key key;
465 int ret;
466 key.objectid = objectid;
Chris Mason1e1d2702007-03-15 19:03:33 -0400467 btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY);
468 key.offset = 0;
469
Chris Mason5f39d392007-10-15 16:14:19 -0400470 ret = btrfs_insert_empty_item(trans, root, path, &key,
471 sizeof(struct btrfs_inode_item));
Chris Mason1e1d2702007-03-15 19:03:33 -0400472 return ret;
473}
474
Chris Masone089f052007-03-16 16:20:31 -0400475int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masond6e4a422007-04-06 15:37:36 -0400476 *root, struct btrfs_path *path,
477 struct btrfs_key *location, int mod)
Chris Mason1e1d2702007-03-15 19:03:33 -0400478{
Chris Mason1e1d2702007-03-15 19:03:33 -0400479 int ins_len = mod < 0 ? -1 : 0;
480 int cow = mod != 0;
Chris Masond6e4a422007-04-06 15:37:36 -0400481 int ret;
482 int slot;
Chris Mason5f39d392007-10-15 16:14:19 -0400483 struct extent_buffer *leaf;
Chris Masond6e4a422007-04-06 15:37:36 -0400484 struct btrfs_key found_key;
Chris Mason1e1d2702007-03-15 19:03:33 -0400485
Chris Masond6e4a422007-04-06 15:37:36 -0400486 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;
Chris Mason5f39d392007-10-15 16:14:19 -0400490 leaf = path->nodes[0];
491 btrfs_item_key_to_cpu(leaf, &found_key, slot);
Chris Masond6e4a422007-04-06 15:37:36 -0400492 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;
Chris Mason1e1d2702007-03-15 19:03:33 -0400499}