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 
10 /*
11  * insert a name into a directory, doing overflow properly if there is a hash
12  * collision.  data_size indicates how big the item inserted should be.  On
13  * success a struct btrfs_dir_item pointer is returned, otherwise it is
14  * an ERR_PTR.
15  *
16  * The name is not copied into the dir item, you have to do that yourself.
17  */
insert_with_overflow(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,struct btrfs_key * cpu_key,u32 data_size,const char * name,int name_len)18 static struct btrfs_dir_item *insert_with_overflow(struct btrfs_trans_handle
19 						   *trans,
20 						   struct btrfs_root *root,
21 						   struct btrfs_path *path,
22 						   struct btrfs_key *cpu_key,
23 						   u32 data_size,
24 						   const char *name,
25 						   int name_len)
26 {
27 	struct btrfs_fs_info *fs_info = root->fs_info;
28 	int ret;
29 	char *ptr;
30 	struct btrfs_item *item;
31 	struct extent_buffer *leaf;
32 
33 	ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
34 	if (ret == -EEXIST) {
35 		struct btrfs_dir_item *di;
36 		di = btrfs_match_dir_item_name(fs_info, path, name, name_len);
37 		if (di)
38 			return ERR_PTR(-EEXIST);
39 		btrfs_extend_item(fs_info, path, data_size);
40 	} else if (ret < 0)
41 		return ERR_PTR(ret);
42 	WARN_ON(ret > 0);
43 	leaf = path->nodes[0];
44 	item = btrfs_item_nr(path->slots[0]);
45 	ptr = btrfs_item_ptr(leaf, path->slots[0], char);
46 	BUG_ON(data_size > btrfs_item_size(leaf, item));
47 	ptr += btrfs_item_size(leaf, item) - data_size;
48 	return (struct btrfs_dir_item *)ptr;
49 }
50 
51 /*
52  * xattrs work a lot like directories, this inserts an xattr item
53  * into the tree
54  */
btrfs_insert_xattr_item(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,u64 objectid,const char * name,u16 name_len,const void * data,u16 data_len)55 int btrfs_insert_xattr_item(struct btrfs_trans_handle *trans,
56 			    struct btrfs_root *root,
57 			    struct btrfs_path *path, u64 objectid,
58 			    const char *name, u16 name_len,
59 			    const void *data, u16 data_len)
60 {
61 	int ret = 0;
62 	struct btrfs_dir_item *dir_item;
63 	unsigned long name_ptr, data_ptr;
64 	struct btrfs_key key, location;
65 	struct btrfs_disk_key disk_key;
66 	struct extent_buffer *leaf;
67 	u32 data_size;
68 
69 	if (name_len + data_len > BTRFS_MAX_XATTR_SIZE(root->fs_info))
70 		return -ENOSPC;
71 
72 	key.objectid = objectid;
73 	key.type = BTRFS_XATTR_ITEM_KEY;
74 	key.offset = btrfs_name_hash(name, name_len);
75 
76 	data_size = sizeof(*dir_item) + name_len + data_len;
77 	dir_item = insert_with_overflow(trans, root, path, &key, data_size,
78 					name, name_len);
79 	if (IS_ERR(dir_item))
80 		return PTR_ERR(dir_item);
81 	memset(&location, 0, sizeof(location));
82 
83 	leaf = path->nodes[0];
84 	btrfs_cpu_key_to_disk(&disk_key, &location);
85 	btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
86 	btrfs_set_dir_type(leaf, dir_item, BTRFS_FT_XATTR);
87 	btrfs_set_dir_name_len(leaf, dir_item, name_len);
88 	btrfs_set_dir_transid(leaf, dir_item, trans->transid);
89 	btrfs_set_dir_data_len(leaf, dir_item, data_len);
90 	name_ptr = (unsigned long)(dir_item + 1);
91 	data_ptr = (unsigned long)((char *)name_ptr + name_len);
92 
93 	write_extent_buffer(leaf, name, name_ptr, name_len);
94 	write_extent_buffer(leaf, data, data_ptr, data_len);
95 	btrfs_mark_buffer_dirty(path->nodes[0]);
96 
97 	return ret;
98 }
99 
100 /*
101  * insert a directory item in the tree, doing all the magic for
102  * both indexes. 'dir' indicates which objectid to insert it into,
103  * 'location' is the key to stuff into the directory item, 'type' is the
104  * type of the inode we're pointing to, and 'index' is the sequence number
105  * to use for the second index (if one is created).
106  * Will return 0 or -ENOMEM
107  */
btrfs_insert_dir_item(struct btrfs_trans_handle * trans,struct btrfs_root * root,const char * name,int name_len,struct btrfs_inode * dir,struct btrfs_key * location,u8 type,u64 index)108 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
109 			  *root, const char *name, int name_len,
110 			  struct btrfs_inode *dir, struct btrfs_key *location,
111 			  u8 type, u64 index)
112 {
113 	int ret = 0;
114 	int ret2 = 0;
115 	struct btrfs_path *path;
116 	struct btrfs_dir_item *dir_item;
117 	struct extent_buffer *leaf;
118 	unsigned long name_ptr;
119 	struct btrfs_key key;
120 	struct btrfs_disk_key disk_key;
121 	u32 data_size;
122 
123 	key.objectid = btrfs_ino(dir);
124 	key.type = BTRFS_DIR_ITEM_KEY;
125 	key.offset = btrfs_name_hash(name, name_len);
126 
127 	path = btrfs_alloc_path();
128 	if (!path)
129 		return -ENOMEM;
130 	path->leave_spinning = 1;
131 
132 	btrfs_cpu_key_to_disk(&disk_key, location);
133 
134 	data_size = sizeof(*dir_item) + name_len;
135 	dir_item = insert_with_overflow(trans, root, path, &key, data_size,
136 					name, name_len);
137 	if (IS_ERR(dir_item)) {
138 		ret = PTR_ERR(dir_item);
139 		if (ret == -EEXIST)
140 			goto second_insert;
141 		goto out_free;
142 	}
143 
144 	leaf = path->nodes[0];
145 	btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
146 	btrfs_set_dir_type(leaf, dir_item, type);
147 	btrfs_set_dir_data_len(leaf, dir_item, 0);
148 	btrfs_set_dir_name_len(leaf, dir_item, name_len);
149 	btrfs_set_dir_transid(leaf, dir_item, trans->transid);
150 	name_ptr = (unsigned long)(dir_item + 1);
151 
152 	write_extent_buffer(leaf, name, name_ptr, name_len);
153 	btrfs_mark_buffer_dirty(leaf);
154 
155 second_insert:
156 	/* FIXME, use some real flag for selecting the extra index */
157 	if (root == root->fs_info->tree_root) {
158 		ret = 0;
159 		goto out_free;
160 	}
161 	btrfs_release_path(path);
162 
163 	ret2 = btrfs_insert_delayed_dir_index(trans, name, name_len, dir,
164 					      &disk_key, type, index);
165 out_free:
166 	btrfs_free_path(path);
167 	if (ret)
168 		return ret;
169 	if (ret2)
170 		return ret2;
171 	return 0;
172 }
173 
174 /*
175  * lookup a directory item based on name.  'dir' is the objectid
176  * we're searching in, and 'mod' tells us if you plan on deleting the
177  * item (use mod < 0) or changing the options (use mod > 0)
178  */
btrfs_lookup_dir_item(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,u64 dir,const char * name,int name_len,int mod)179 struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
180 					     struct btrfs_root *root,
181 					     struct btrfs_path *path, u64 dir,
182 					     const char *name, int name_len,
183 					     int mod)
184 {
185 	int ret;
186 	struct btrfs_key key;
187 	int ins_len = mod < 0 ? -1 : 0;
188 	int cow = mod != 0;
189 
190 	key.objectid = dir;
191 	key.type = BTRFS_DIR_ITEM_KEY;
192 
193 	key.offset = btrfs_name_hash(name, name_len);
194 
195 	ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
196 	if (ret < 0)
197 		return ERR_PTR(ret);
198 	if (ret > 0)
199 		return NULL;
200 
201 	return btrfs_match_dir_item_name(root->fs_info, path, name, name_len);
202 }
203 
btrfs_check_dir_item_collision(struct btrfs_root * root,u64 dir,const char * name,int name_len)204 int btrfs_check_dir_item_collision(struct btrfs_root *root, u64 dir,
205 				   const char *name, int name_len)
206 {
207 	int ret;
208 	struct btrfs_key key;
209 	struct btrfs_dir_item *di;
210 	int data_size;
211 	struct extent_buffer *leaf;
212 	int slot;
213 	struct btrfs_path *path;
214 
215 
216 	path = btrfs_alloc_path();
217 	if (!path)
218 		return -ENOMEM;
219 
220 	key.objectid = dir;
221 	key.type = BTRFS_DIR_ITEM_KEY;
222 	key.offset = btrfs_name_hash(name, name_len);
223 
224 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
225 
226 	/* return back any errors */
227 	if (ret < 0)
228 		goto out;
229 
230 	/* nothing found, we're safe */
231 	if (ret > 0) {
232 		ret = 0;
233 		goto out;
234 	}
235 
236 	/* we found an item, look for our name in the item */
237 	di = btrfs_match_dir_item_name(root->fs_info, path, name, name_len);
238 	if (di) {
239 		/* our exact name was found */
240 		ret = -EEXIST;
241 		goto out;
242 	}
243 
244 	/*
245 	 * see if there is room in the item to insert this
246 	 * name
247 	 */
248 	data_size = sizeof(*di) + name_len;
249 	leaf = path->nodes[0];
250 	slot = path->slots[0];
251 	if (data_size + btrfs_item_size_nr(leaf, slot) +
252 	    sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
253 		ret = -EOVERFLOW;
254 	} else {
255 		/* plenty of insertion room */
256 		ret = 0;
257 	}
258 out:
259 	btrfs_free_path(path);
260 	return ret;
261 }
262 
263 /*
264  * lookup a directory item based on index.  'dir' is the objectid
265  * we're searching in, and 'mod' tells us if you plan on deleting the
266  * item (use mod < 0) or changing the options (use mod > 0)
267  *
268  * The name is used to make sure the index really points to the name you were
269  * looking for.
270  */
271 struct btrfs_dir_item *
btrfs_lookup_dir_index_item(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,u64 dir,u64 objectid,const char * name,int name_len,int mod)272 btrfs_lookup_dir_index_item(struct btrfs_trans_handle *trans,
273 			    struct btrfs_root *root,
274 			    struct btrfs_path *path, u64 dir,
275 			    u64 objectid, const char *name, int name_len,
276 			    int mod)
277 {
278 	int ret;
279 	struct btrfs_key key;
280 	int ins_len = mod < 0 ? -1 : 0;
281 	int cow = mod != 0;
282 
283 	key.objectid = dir;
284 	key.type = BTRFS_DIR_INDEX_KEY;
285 	key.offset = objectid;
286 
287 	ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
288 	if (ret < 0)
289 		return ERR_PTR(ret);
290 	if (ret > 0)
291 		return ERR_PTR(-ENOENT);
292 	return btrfs_match_dir_item_name(root->fs_info, path, name, name_len);
293 }
294 
295 struct btrfs_dir_item *
btrfs_search_dir_index_item(struct btrfs_root * root,struct btrfs_path * path,u64 dirid,const char * name,int name_len)296 btrfs_search_dir_index_item(struct btrfs_root *root,
297 			    struct btrfs_path *path, u64 dirid,
298 			    const char *name, int name_len)
299 {
300 	struct extent_buffer *leaf;
301 	struct btrfs_dir_item *di;
302 	struct btrfs_key key;
303 	u32 nritems;
304 	int ret;
305 
306 	key.objectid = dirid;
307 	key.type = BTRFS_DIR_INDEX_KEY;
308 	key.offset = 0;
309 
310 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
311 	if (ret < 0)
312 		return ERR_PTR(ret);
313 
314 	leaf = path->nodes[0];
315 	nritems = btrfs_header_nritems(leaf);
316 
317 	while (1) {
318 		if (path->slots[0] >= nritems) {
319 			ret = btrfs_next_leaf(root, path);
320 			if (ret < 0)
321 				return ERR_PTR(ret);
322 			if (ret > 0)
323 				break;
324 			leaf = path->nodes[0];
325 			nritems = btrfs_header_nritems(leaf);
326 			continue;
327 		}
328 
329 		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
330 		if (key.objectid != dirid || key.type != BTRFS_DIR_INDEX_KEY)
331 			break;
332 
333 		di = btrfs_match_dir_item_name(root->fs_info, path,
334 					       name, name_len);
335 		if (di)
336 			return di;
337 
338 		path->slots[0]++;
339 	}
340 	return NULL;
341 }
342 
btrfs_lookup_xattr(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,u64 dir,const char * name,u16 name_len,int mod)343 struct btrfs_dir_item *btrfs_lookup_xattr(struct btrfs_trans_handle *trans,
344 					  struct btrfs_root *root,
345 					  struct btrfs_path *path, u64 dir,
346 					  const char *name, u16 name_len,
347 					  int mod)
348 {
349 	int ret;
350 	struct btrfs_key key;
351 	int ins_len = mod < 0 ? -1 : 0;
352 	int cow = mod != 0;
353 
354 	key.objectid = dir;
355 	key.type = BTRFS_XATTR_ITEM_KEY;
356 	key.offset = btrfs_name_hash(name, name_len);
357 	ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
358 	if (ret < 0)
359 		return ERR_PTR(ret);
360 	if (ret > 0)
361 		return NULL;
362 
363 	return btrfs_match_dir_item_name(root->fs_info, path, name, name_len);
364 }
365 
366 /*
367  * helper function to look at the directory item pointed to by 'path'
368  * this walks through all the entries in a dir item and finds one
369  * for a specific name.
370  */
btrfs_match_dir_item_name(struct btrfs_fs_info * fs_info,struct btrfs_path * path,const char * name,int name_len)371 struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_fs_info *fs_info,
372 						 struct btrfs_path *path,
373 						 const char *name, int name_len)
374 {
375 	struct btrfs_dir_item *dir_item;
376 	unsigned long name_ptr;
377 	u32 total_len;
378 	u32 cur = 0;
379 	u32 this_len;
380 	struct extent_buffer *leaf;
381 
382 	leaf = path->nodes[0];
383 	dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
384 
385 	total_len = btrfs_item_size_nr(leaf, path->slots[0]);
386 	while (cur < total_len) {
387 		this_len = sizeof(*dir_item) +
388 			btrfs_dir_name_len(leaf, dir_item) +
389 			btrfs_dir_data_len(leaf, dir_item);
390 		name_ptr = (unsigned long)(dir_item + 1);
391 
392 		if (btrfs_dir_name_len(leaf, dir_item) == name_len &&
393 		    memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)
394 			return dir_item;
395 
396 		cur += this_len;
397 		dir_item = (struct btrfs_dir_item *)((char *)dir_item +
398 						     this_len);
399 	}
400 	return NULL;
401 }
402 
403 /*
404  * given a pointer into a directory item, delete it.  This
405  * handles items that have more than one entry in them.
406  */
btrfs_delete_one_dir_name(struct btrfs_trans_handle * trans,struct btrfs_root * root,struct btrfs_path * path,struct btrfs_dir_item * di)407 int btrfs_delete_one_dir_name(struct btrfs_trans_handle *trans,
408 			      struct btrfs_root *root,
409 			      struct btrfs_path *path,
410 			      struct btrfs_dir_item *di)
411 {
412 
413 	struct extent_buffer *leaf;
414 	u32 sub_item_len;
415 	u32 item_len;
416 	int ret = 0;
417 
418 	leaf = path->nodes[0];
419 	sub_item_len = sizeof(*di) + btrfs_dir_name_len(leaf, di) +
420 		btrfs_dir_data_len(leaf, di);
421 	item_len = btrfs_item_size_nr(leaf, path->slots[0]);
422 	if (sub_item_len == item_len) {
423 		ret = btrfs_del_item(trans, root, path);
424 	} else {
425 		/* MARKER */
426 		unsigned long ptr = (unsigned long)di;
427 		unsigned long start;
428 
429 		start = btrfs_item_ptr_offset(leaf, path->slots[0]);
430 		memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
431 			item_len - (ptr + sub_item_len - start));
432 		btrfs_truncate_item(root->fs_info, path,
433 				    item_len - sub_item_len, 1);
434 	}
435 	return ret;
436 }
437