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
25static 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
54int 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 */
95struct btrfs_inode_extref *
96btrfs_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
121static 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_std_error(root->fs_info, -ENOENT);
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
187out:
188	btrfs_free_path(path);
189
190	return ret;
191}
192
193int 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);
249out:
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 */
270static 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
320out:
321	btrfs_free_path(path);
322	return ret;
323}
324
325/* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
326int 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
383out:
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
401int 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
416int 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}
441