2 * Copyright (C) 2007 Oracle. All rights reserved.
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.
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.
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.
21 #include "transaction.h"
22 #include "print-tree.h"
24 int btrfs_find_name_in_backref(struct extent_buffer *leaf, int slot,
26 int name_len, struct btrfs_inode_ref **ref_ret)
28 struct btrfs_inode_ref *ref;
30 unsigned long name_ptr;
35 item_size = btrfs_item_size_nr(leaf, slot);
36 ptr = btrfs_item_ptr_offset(leaf, slot);
37 while (cur_offset < item_size) {
38 ref = (struct btrfs_inode_ref *)(ptr + cur_offset);
39 len = btrfs_inode_ref_name_len(leaf, ref);
40 name_ptr = (unsigned long)(ref + 1);
41 cur_offset += len + sizeof(*ref);
44 if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) {
53 int btrfs_find_name_in_ext_backref(struct extent_buffer *leaf, int slot,
55 const char *name, int name_len,
56 struct btrfs_inode_extref **extref_ret)
58 struct btrfs_inode_extref *extref;
60 unsigned long name_ptr;
65 item_size = btrfs_item_size_nr(leaf, slot);
66 ptr = btrfs_item_ptr_offset(leaf, slot);
69 * Search all extended backrefs in this item. We're only
70 * looking through any collisions so most of the time this is
71 * just going to compare against one buffer. If all is well,
72 * we'll return success and the inode ref object.
74 while (cur_offset < item_size) {
75 extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
76 name_ptr = (unsigned long)(&extref->name);
77 ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
79 if (ref_name_len == name_len &&
80 btrfs_inode_extref_parent(leaf, extref) == ref_objectid &&
81 (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) {
87 cur_offset += ref_name_len + sizeof(*extref);
92 /* Returns NULL if no extref found */
93 struct btrfs_inode_extref *
94 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
95 struct btrfs_root *root,
96 struct btrfs_path *path,
97 const char *name, int name_len,
98 u64 inode_objectid, u64 ref_objectid, int ins_len,
102 struct btrfs_key key;
103 struct btrfs_inode_extref *extref;
105 key.objectid = inode_objectid;
106 key.type = BTRFS_INODE_EXTREF_KEY;
107 key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
109 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
114 if (!btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0],
115 ref_objectid, name, name_len,
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,
127 struct btrfs_path *path;
128 struct btrfs_key key;
129 struct btrfs_inode_extref *extref;
130 struct extent_buffer *leaf;
132 int del_len = name_len + sizeof(*extref);
134 unsigned long item_start;
137 key.objectid = inode_objectid;
138 key.type = BTRFS_INODE_EXTREF_KEY;
139 key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
141 path = btrfs_alloc_path();
145 path->leave_spinning = 1;
147 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
154 * Sanity check - did we find the right item for this name?
155 * This should always succeed so error here will make the FS
158 if (!btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0],
160 name, name_len, &extref)) {
161 btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL);
166 leaf = path->nodes[0];
167 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
169 *index = btrfs_inode_extref_index(leaf, extref);
171 if (del_len == item_size) {
173 * Common case only one ref in the item, remove the
176 ret = btrfs_del_item(trans, root, path);
180 ptr = (unsigned long)extref;
181 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
183 memmove_extent_buffer(leaf, ptr, ptr + del_len,
184 item_size - (ptr + del_len - item_start));
186 btrfs_truncate_item(root->fs_info, path, item_size - del_len, 1);
189 btrfs_free_path(path);
194 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
195 struct btrfs_root *root,
196 const char *name, int name_len,
197 u64 inode_objectid, u64 ref_objectid, u64 *index)
199 struct btrfs_path *path;
200 struct btrfs_key key;
201 struct btrfs_inode_ref *ref;
202 struct extent_buffer *leaf;
204 unsigned long item_start;
208 int search_ext_refs = 0;
209 int del_len = name_len + sizeof(*ref);
211 key.objectid = inode_objectid;
212 key.offset = ref_objectid;
213 key.type = BTRFS_INODE_REF_KEY;
215 path = btrfs_alloc_path();
219 path->leave_spinning = 1;
221 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
226 } else if (ret < 0) {
229 if (!btrfs_find_name_in_backref(path->nodes[0], path->slots[0],
230 name, name_len, &ref)) {
235 leaf = path->nodes[0];
236 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
239 *index = btrfs_inode_ref_index(leaf, ref);
241 if (del_len == item_size) {
242 ret = btrfs_del_item(trans, root, path);
245 ptr = (unsigned long)ref;
246 sub_item_len = name_len + sizeof(*ref);
247 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
248 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
249 item_size - (ptr + sub_item_len - item_start));
250 btrfs_truncate_item(root->fs_info, path, item_size - sub_item_len, 1);
252 btrfs_free_path(path);
254 if (search_ext_refs) {
256 * No refs were found, or we could not find the
257 * name in our ref array. Find and remove the extended
260 return btrfs_del_inode_extref(trans, root, name, name_len,
261 inode_objectid, ref_objectid, index);
268 * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
270 * The caller must have checked against BTRFS_LINK_MAX already.
272 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
273 struct btrfs_root *root,
274 const char *name, int name_len,
275 u64 inode_objectid, u64 ref_objectid, u64 index)
277 struct btrfs_inode_extref *extref;
279 int ins_len = name_len + sizeof(*extref);
281 struct btrfs_path *path;
282 struct btrfs_key key;
283 struct extent_buffer *leaf;
284 struct btrfs_item *item;
286 key.objectid = inode_objectid;
287 key.type = BTRFS_INODE_EXTREF_KEY;
288 key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
290 path = btrfs_alloc_path();
294 path->leave_spinning = 1;
295 ret = btrfs_insert_empty_item(trans, root, path, &key,
297 if (ret == -EEXIST) {
298 if (btrfs_find_name_in_ext_backref(path->nodes[0],
301 name, name_len, NULL))
304 btrfs_extend_item(root->fs_info, path, ins_len);
310 leaf = path->nodes[0];
311 item = btrfs_item_nr(path->slots[0]);
312 ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
313 ptr += btrfs_item_size(leaf, item) - ins_len;
314 extref = (struct btrfs_inode_extref *)ptr;
316 btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
317 btrfs_set_inode_extref_index(path->nodes[0], extref, index);
318 btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
320 ptr = (unsigned long)&extref->name;
321 write_extent_buffer(path->nodes[0], name, ptr, name_len);
322 btrfs_mark_buffer_dirty(path->nodes[0]);
325 btrfs_free_path(path);
329 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
330 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
331 struct btrfs_root *root,
332 const char *name, int name_len,
333 u64 inode_objectid, u64 ref_objectid, u64 index)
335 struct btrfs_fs_info *fs_info = root->fs_info;
336 struct btrfs_path *path;
337 struct btrfs_key key;
338 struct btrfs_inode_ref *ref;
341 int ins_len = name_len + sizeof(*ref);
343 key.objectid = inode_objectid;
344 key.offset = ref_objectid;
345 key.type = BTRFS_INODE_REF_KEY;
347 path = btrfs_alloc_path();
351 path->leave_spinning = 1;
352 path->skip_release_on_error = 1;
353 ret = btrfs_insert_empty_item(trans, root, path, &key,
355 if (ret == -EEXIST) {
358 if (btrfs_find_name_in_backref(path->nodes[0], path->slots[0],
359 name, name_len, &ref))
362 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
363 btrfs_extend_item(fs_info, path, ins_len);
364 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
365 struct btrfs_inode_ref);
366 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
367 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
368 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
369 ptr = (unsigned long)(ref + 1);
371 } else if (ret < 0) {
372 if (ret == -EOVERFLOW) {
373 if (btrfs_find_name_in_backref(path->nodes[0],
375 name, name_len, &ref))
382 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
383 struct btrfs_inode_ref);
384 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
385 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
386 ptr = (unsigned long)(ref + 1);
388 write_extent_buffer(path->nodes[0], name, ptr, name_len);
389 btrfs_mark_buffer_dirty(path->nodes[0]);
392 btrfs_free_path(path);
394 if (ret == -EMLINK) {
395 struct btrfs_super_block *disk_super = fs_info->super_copy;
396 /* We ran out of space in the ref array. Need to
397 * add an extended ref. */
398 if (btrfs_super_incompat_flags(disk_super)
399 & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
400 ret = btrfs_insert_inode_extref(trans, root, name,
403 ref_objectid, index);
409 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
410 struct btrfs_root *root,
411 struct btrfs_path *path, u64 objectid)
413 struct btrfs_key key;
415 key.objectid = objectid;
416 key.type = BTRFS_INODE_ITEM_KEY;
419 ret = btrfs_insert_empty_item(trans, root, path, &key,
420 sizeof(struct btrfs_inode_item));
424 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
425 *root, struct btrfs_path *path,
426 struct btrfs_key *location, int mod)
428 int ins_len = mod < 0 ? -1 : 0;
432 struct extent_buffer *leaf;
433 struct btrfs_key found_key;
435 ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
436 if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY &&
437 location->offset == (u64)-1 && path->slots[0] != 0) {
438 slot = path->slots[0] - 1;
439 leaf = path->nodes[0];
440 btrfs_item_key_to_cpu(leaf, &found_key, slot);
441 if (found_key.objectid == location->objectid &&
442 found_key.type == location->type) {