1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2007 Oracle.  All rights reserved.
4  */
5 
6 #include "ctree.h"
7 #include "disk-io.h"
8 #include "transaction.h"
9 #include "print-tree.h"
10 
btrfs_find_name_in_backref(struct extent_buffer * leaf,int slot,const char * name,int name_len,struct btrfs_inode_ref ** ref_ret)11 int btrfs_find_name_in_backref(struct extent_buffer *leaf, int slot,
12 			       const char *name,
13 			       int name_len, struct btrfs_inode_ref **ref_ret)
14 {
15 	struct btrfs_inode_ref *ref;
16 	unsigned long ptr;
17 	unsigned long name_ptr;
18 	u32 item_size;
19 	u32 cur_offset = 0;
20 	int len;
21 
22 	item_size = btrfs_item_size_nr(leaf, slot);
23 	ptr = btrfs_item_ptr_offset(leaf, slot);
24 	while (cur_offset < item_size) {
25 		ref = (struct btrfs_inode_ref *)(ptr + cur_offset);
26 		len = btrfs_inode_ref_name_len(leaf, ref);
27 		name_ptr = (unsigned long)(ref + 1);
28 		cur_offset += len + sizeof(*ref);
29 		if (len != name_len)
30 			continue;
31 		if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) {
32 			if (ref_ret)
33 				*ref_ret = ref;
34 			return 1;
35 		}
36 	}
37 	return 0;
38 }
39 
btrfs_find_name_in_ext_backref(struct extent_buffer * leaf,int slot,u64 ref_objectid,const char * name,int name_len,struct btrfs_inode_extref ** extref_ret)40 int btrfs_find_name_in_ext_backref(struct extent_buffer *leaf, int slot,
41 				   u64 ref_objectid,
42 				   const char *name, int name_len,
43 				   struct btrfs_inode_extref **extref_ret)
44 {
45 	struct btrfs_inode_extref *extref;
46 	unsigned long ptr;
47 	unsigned long name_ptr;
48 	u32 item_size;
49 	u32 cur_offset = 0;
50 	int ref_name_len;
51 
52 	item_size = btrfs_item_size_nr(leaf, slot);
53 	ptr = btrfs_item_ptr_offset(leaf, slot);
54 
55 	/*
56 	 * Search all extended backrefs in this item. We're only
57 	 * looking through any collisions so most of the time this is
58 	 * just going to compare against one buffer. If all is well,
59 	 * we'll return success and the inode ref object.
60 	 */
61 	while (cur_offset < item_size) {
62 		extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
63 		name_ptr = (unsigned long)(&extref->name);
64 		ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
65 
66 		if (ref_name_len == name_len &&
67 		    btrfs_inode_extref_parent(leaf, extref) == ref_objectid &&
68 		    (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) {
69 			if (extref_ret)
70 				*extref_ret = extref;
71 			return 1;
72 		}
73 
74 		cur_offset += ref_name_len + sizeof(*extref);
75 	}
76 	return 0;
77 }
78 
79 /* Returns NULL if no extref found */
80 struct btrfs_inode_extref *
btrfs_lookup_inode_extref(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,const char * name,int name_len,u64 inode_objectid,u64 ref_objectid,int ins_len,int cow)81 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
82 			  struct btrfs_root *root,
83 			  struct btrfs_path *path,
84 			  const char *name, int name_len,
85 			  u64 inode_objectid, u64 ref_objectid, int ins_len,
86 			  int cow)
87 {
88 	int ret;
89 	struct btrfs_key key;
90 	struct btrfs_inode_extref *extref;
91 
92 	key.objectid = inode_objectid;
93 	key.type = BTRFS_INODE_EXTREF_KEY;
94 	key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
95 
96 	ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
97 	if (ret < 0)
98 		return ERR_PTR(ret);
99 	if (ret > 0)
100 		return NULL;
101 	if (!btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0],
102 					    ref_objectid, name, name_len,
103 					    &extref))
104 		return NULL;
105 	return extref;
106 }
107 
btrfs_del_inode_extref(struct btrfs_trans_handle * trans,struct btrfs_root * root,const char * name,int name_len,u64 inode_objectid,u64 ref_objectid,u64 * index)108 static int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
109 				  struct btrfs_root *root,
110 				  const char *name, int name_len,
111 				  u64 inode_objectid, u64 ref_objectid,
112 				  u64 *index)
113 {
114 	struct btrfs_path *path;
115 	struct btrfs_key key;
116 	struct btrfs_inode_extref *extref;
117 	struct extent_buffer *leaf;
118 	int ret;
119 	int del_len = name_len + sizeof(*extref);
120 	unsigned long ptr;
121 	unsigned long item_start;
122 	u32 item_size;
123 
124 	key.objectid = inode_objectid;
125 	key.type = BTRFS_INODE_EXTREF_KEY;
126 	key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
127 
128 	path = btrfs_alloc_path();
129 	if (!path)
130 		return -ENOMEM;
131 
132 	path->leave_spinning = 1;
133 
134 	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
135 	if (ret > 0)
136 		ret = -ENOENT;
137 	if (ret < 0)
138 		goto out;
139 
140 	/*
141 	 * Sanity check - did we find the right item for this name?
142 	 * This should always succeed so error here will make the FS
143 	 * readonly.
144 	 */
145 	if (!btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0],
146 					    ref_objectid,
147 					    name, name_len, &extref)) {
148 		btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL);
149 		ret = -EROFS;
150 		goto out;
151 	}
152 
153 	leaf = path->nodes[0];
154 	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
155 	if (index)
156 		*index = btrfs_inode_extref_index(leaf, extref);
157 
158 	if (del_len == item_size) {
159 		/*
160 		 * Common case only one ref in the item, remove the
161 		 * whole item.
162 		 */
163 		ret = btrfs_del_item(trans, root, path);
164 		goto out;
165 	}
166 
167 	ptr = (unsigned long)extref;
168 	item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
169 
170 	memmove_extent_buffer(leaf, ptr, ptr + del_len,
171 			      item_size - (ptr + del_len - item_start));
172 
173 	btrfs_truncate_item(root->fs_info, path, item_size - del_len, 1);
174 
175 out:
176 	btrfs_free_path(path);
177 
178 	return ret;
179 }
180 
btrfs_del_inode_ref(struct btrfs_trans_handle * trans,struct btrfs_root * root,const char * name,int name_len,u64 inode_objectid,u64 ref_objectid,u64 * index)181 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
182 			struct btrfs_root *root,
183 			const char *name, int name_len,
184 			u64 inode_objectid, u64 ref_objectid, u64 *index)
185 {
186 	struct btrfs_path *path;
187 	struct btrfs_key key;
188 	struct btrfs_inode_ref *ref;
189 	struct extent_buffer *leaf;
190 	unsigned long ptr;
191 	unsigned long item_start;
192 	u32 item_size;
193 	u32 sub_item_len;
194 	int ret;
195 	int search_ext_refs = 0;
196 	int del_len = name_len + sizeof(*ref);
197 
198 	key.objectid = inode_objectid;
199 	key.offset = ref_objectid;
200 	key.type = BTRFS_INODE_REF_KEY;
201 
202 	path = btrfs_alloc_path();
203 	if (!path)
204 		return -ENOMEM;
205 
206 	path->leave_spinning = 1;
207 
208 	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
209 	if (ret > 0) {
210 		ret = -ENOENT;
211 		search_ext_refs = 1;
212 		goto out;
213 	} else if (ret < 0) {
214 		goto out;
215 	}
216 	if (!btrfs_find_name_in_backref(path->nodes[0], path->slots[0],
217 					name, name_len, &ref)) {
218 		ret = -ENOENT;
219 		search_ext_refs = 1;
220 		goto out;
221 	}
222 	leaf = path->nodes[0];
223 	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
224 
225 	if (index)
226 		*index = btrfs_inode_ref_index(leaf, ref);
227 
228 	if (del_len == item_size) {
229 		ret = btrfs_del_item(trans, root, path);
230 		goto out;
231 	}
232 	ptr = (unsigned long)ref;
233 	sub_item_len = name_len + sizeof(*ref);
234 	item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
235 	memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
236 			      item_size - (ptr + sub_item_len - item_start));
237 	btrfs_truncate_item(root->fs_info, path, item_size - sub_item_len, 1);
238 out:
239 	btrfs_free_path(path);
240 
241 	if (search_ext_refs) {
242 		/*
243 		 * No refs were found, or we could not find the
244 		 * name in our ref array. Find and remove the extended
245 		 * inode ref then.
246 		 */
247 		return btrfs_del_inode_extref(trans, root, name, name_len,
248 					      inode_objectid, ref_objectid, index);
249 	}
250 
251 	return ret;
252 }
253 
254 /*
255  * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
256  *
257  * The caller must have checked against BTRFS_LINK_MAX already.
258  */
btrfs_insert_inode_extref(struct btrfs_trans_handle * trans,struct btrfs_root * root,const char * name,int name_len,u64 inode_objectid,u64 ref_objectid,u64 index)259 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
260 				     struct btrfs_root *root,
261 				     const char *name, int name_len,
262 				     u64 inode_objectid, u64 ref_objectid, u64 index)
263 {
264 	struct btrfs_inode_extref *extref;
265 	int ret;
266 	int ins_len = name_len + sizeof(*extref);
267 	unsigned long ptr;
268 	struct btrfs_path *path;
269 	struct btrfs_key key;
270 	struct extent_buffer *leaf;
271 	struct btrfs_item *item;
272 
273 	key.objectid = inode_objectid;
274 	key.type = BTRFS_INODE_EXTREF_KEY;
275 	key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
276 
277 	path = btrfs_alloc_path();
278 	if (!path)
279 		return -ENOMEM;
280 
281 	path->leave_spinning = 1;
282 	ret = btrfs_insert_empty_item(trans, root, path, &key,
283 				      ins_len);
284 	if (ret == -EEXIST) {
285 		if (btrfs_find_name_in_ext_backref(path->nodes[0],
286 						   path->slots[0],
287 						   ref_objectid,
288 						   name, name_len, NULL))
289 			goto out;
290 
291 		btrfs_extend_item(root->fs_info, path, ins_len);
292 		ret = 0;
293 	}
294 	if (ret < 0)
295 		goto out;
296 
297 	leaf = path->nodes[0];
298 	item = btrfs_item_nr(path->slots[0]);
299 	ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
300 	ptr += btrfs_item_size(leaf, item) - ins_len;
301 	extref = (struct btrfs_inode_extref *)ptr;
302 
303 	btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
304 	btrfs_set_inode_extref_index(path->nodes[0], extref, index);
305 	btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
306 
307 	ptr = (unsigned long)&extref->name;
308 	write_extent_buffer(path->nodes[0], name, ptr, name_len);
309 	btrfs_mark_buffer_dirty(path->nodes[0]);
310 
311 out:
312 	btrfs_free_path(path);
313 	return ret;
314 }
315 
316 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
btrfs_insert_inode_ref(struct btrfs_trans_handle * trans,struct btrfs_root * root,const char * name,int name_len,u64 inode_objectid,u64 ref_objectid,u64 index)317 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
318 			   struct btrfs_root *root,
319 			   const char *name, int name_len,
320 			   u64 inode_objectid, u64 ref_objectid, u64 index)
321 {
322 	struct btrfs_fs_info *fs_info = root->fs_info;
323 	struct btrfs_path *path;
324 	struct btrfs_key key;
325 	struct btrfs_inode_ref *ref;
326 	unsigned long ptr;
327 	int ret;
328 	int ins_len = name_len + sizeof(*ref);
329 
330 	key.objectid = inode_objectid;
331 	key.offset = ref_objectid;
332 	key.type = BTRFS_INODE_REF_KEY;
333 
334 	path = btrfs_alloc_path();
335 	if (!path)
336 		return -ENOMEM;
337 
338 	path->leave_spinning = 1;
339 	path->skip_release_on_error = 1;
340 	ret = btrfs_insert_empty_item(trans, root, path, &key,
341 				      ins_len);
342 	if (ret == -EEXIST) {
343 		u32 old_size;
344 
345 		if (btrfs_find_name_in_backref(path->nodes[0], path->slots[0],
346 					       name, name_len, &ref))
347 			goto out;
348 
349 		old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
350 		btrfs_extend_item(fs_info, path, ins_len);
351 		ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
352 				     struct btrfs_inode_ref);
353 		ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
354 		btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
355 		btrfs_set_inode_ref_index(path->nodes[0], ref, index);
356 		ptr = (unsigned long)(ref + 1);
357 		ret = 0;
358 	} else if (ret < 0) {
359 		if (ret == -EOVERFLOW) {
360 			if (btrfs_find_name_in_backref(path->nodes[0],
361 						       path->slots[0],
362 						       name, name_len, &ref))
363 				ret = -EEXIST;
364 			else
365 				ret = -EMLINK;
366 		}
367 		goto out;
368 	} else {
369 		ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
370 				     struct btrfs_inode_ref);
371 		btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
372 		btrfs_set_inode_ref_index(path->nodes[0], ref, index);
373 		ptr = (unsigned long)(ref + 1);
374 	}
375 	write_extent_buffer(path->nodes[0], name, ptr, name_len);
376 	btrfs_mark_buffer_dirty(path->nodes[0]);
377 
378 out:
379 	btrfs_free_path(path);
380 
381 	if (ret == -EMLINK) {
382 		struct btrfs_super_block *disk_super = fs_info->super_copy;
383 		/* We ran out of space in the ref array. Need to
384 		 * add an extended ref. */
385 		if (btrfs_super_incompat_flags(disk_super)
386 		    & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
387 			ret = btrfs_insert_inode_extref(trans, root, name,
388 							name_len,
389 							inode_objectid,
390 							ref_objectid, index);
391 	}
392 
393 	return ret;
394 }
395 
btrfs_insert_empty_inode(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,u64 objectid)396 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
397 			     struct btrfs_root *root,
398 			     struct btrfs_path *path, u64 objectid)
399 {
400 	struct btrfs_key key;
401 	int ret;
402 	key.objectid = objectid;
403 	key.type = BTRFS_INODE_ITEM_KEY;
404 	key.offset = 0;
405 
406 	ret = btrfs_insert_empty_item(trans, root, path, &key,
407 				      sizeof(struct btrfs_inode_item));
408 	return ret;
409 }
410 
btrfs_lookup_inode(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,struct btrfs_key * location,int mod)411 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
412 		       *root, struct btrfs_path *path,
413 		       struct btrfs_key *location, int mod)
414 {
415 	int ins_len = mod < 0 ? -1 : 0;
416 	int cow = mod != 0;
417 	int ret;
418 	int slot;
419 	struct extent_buffer *leaf;
420 	struct btrfs_key found_key;
421 
422 	ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
423 	if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY &&
424 	    location->offset == (u64)-1 && path->slots[0] != 0) {
425 		slot = path->slots[0] - 1;
426 		leaf = path->nodes[0];
427 		btrfs_item_key_to_cpu(leaf, &found_key, slot);
428 		if (found_key.objectid == location->objectid &&
429 		    found_key.type == location->type) {
430 			path->slots[0]--;
431 			return 0;
432 		}
433 	}
434 	return ret;
435 }
436