xref: /openbmc/linux/fs/f2fs/dir.c (revision d9d6b822)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * fs/f2fs/dir.c
4  *
5  * Copyright (c) 2012 Samsung Electronics Co., Ltd.
6  *             http://www.samsung.com/
7  */
8 #include <asm/unaligned.h>
9 #include <linux/fs.h>
10 #include <linux/f2fs_fs.h>
11 #include <linux/sched/signal.h>
12 #include <linux/unicode.h>
13 #include "f2fs.h"
14 #include "node.h"
15 #include "acl.h"
16 #include "xattr.h"
17 #include <trace/events/f2fs.h>
18 
19 static unsigned long dir_blocks(struct inode *inode)
20 {
21 	return ((unsigned long long) (i_size_read(inode) + PAGE_SIZE - 1))
22 							>> PAGE_SHIFT;
23 }
24 
25 static unsigned int dir_buckets(unsigned int level, int dir_level)
26 {
27 	if (level + dir_level < MAX_DIR_HASH_DEPTH / 2)
28 		return 1 << (level + dir_level);
29 	else
30 		return MAX_DIR_BUCKETS;
31 }
32 
33 static unsigned int bucket_blocks(unsigned int level)
34 {
35 	if (level < MAX_DIR_HASH_DEPTH / 2)
36 		return 2;
37 	else
38 		return 4;
39 }
40 
41 static unsigned char f2fs_filetype_table[F2FS_FT_MAX] = {
42 	[F2FS_FT_UNKNOWN]	= DT_UNKNOWN,
43 	[F2FS_FT_REG_FILE]	= DT_REG,
44 	[F2FS_FT_DIR]		= DT_DIR,
45 	[F2FS_FT_CHRDEV]	= DT_CHR,
46 	[F2FS_FT_BLKDEV]	= DT_BLK,
47 	[F2FS_FT_FIFO]		= DT_FIFO,
48 	[F2FS_FT_SOCK]		= DT_SOCK,
49 	[F2FS_FT_SYMLINK]	= DT_LNK,
50 };
51 
52 static unsigned char f2fs_type_by_mode[S_IFMT >> S_SHIFT] = {
53 	[S_IFREG >> S_SHIFT]	= F2FS_FT_REG_FILE,
54 	[S_IFDIR >> S_SHIFT]	= F2FS_FT_DIR,
55 	[S_IFCHR >> S_SHIFT]	= F2FS_FT_CHRDEV,
56 	[S_IFBLK >> S_SHIFT]	= F2FS_FT_BLKDEV,
57 	[S_IFIFO >> S_SHIFT]	= F2FS_FT_FIFO,
58 	[S_IFSOCK >> S_SHIFT]	= F2FS_FT_SOCK,
59 	[S_IFLNK >> S_SHIFT]	= F2FS_FT_SYMLINK,
60 };
61 
62 static void set_de_type(struct f2fs_dir_entry *de, umode_t mode)
63 {
64 	de->file_type = f2fs_type_by_mode[(mode & S_IFMT) >> S_SHIFT];
65 }
66 
67 unsigned char f2fs_get_de_type(struct f2fs_dir_entry *de)
68 {
69 	if (de->file_type < F2FS_FT_MAX)
70 		return f2fs_filetype_table[de->file_type];
71 	return DT_UNKNOWN;
72 }
73 
74 /* If @dir is casefolded, initialize @fname->cf_name from @fname->usr_fname. */
75 int f2fs_init_casefolded_name(const struct inode *dir,
76 			      struct f2fs_filename *fname)
77 {
78 #ifdef CONFIG_UNICODE
79 	struct super_block *sb = dir->i_sb;
80 	struct f2fs_sb_info *sbi = F2FS_SB(sb);
81 
82 	if (IS_CASEFOLDED(dir)) {
83 		fname->cf_name.name = f2fs_kmalloc(sbi, F2FS_NAME_LEN,
84 						   GFP_NOFS);
85 		if (!fname->cf_name.name)
86 			return -ENOMEM;
87 		fname->cf_name.len = utf8_casefold(sb->s_encoding,
88 						   fname->usr_fname,
89 						   fname->cf_name.name,
90 						   F2FS_NAME_LEN);
91 		if ((int)fname->cf_name.len <= 0) {
92 			kfree(fname->cf_name.name);
93 			fname->cf_name.name = NULL;
94 			if (sb_has_strict_encoding(sb))
95 				return -EINVAL;
96 			/* fall back to treating name as opaque byte sequence */
97 		}
98 	}
99 #endif
100 	return 0;
101 }
102 
103 static int __f2fs_setup_filename(const struct inode *dir,
104 				 const struct fscrypt_name *crypt_name,
105 				 struct f2fs_filename *fname)
106 {
107 	int err;
108 
109 	memset(fname, 0, sizeof(*fname));
110 
111 	fname->usr_fname = crypt_name->usr_fname;
112 	fname->disk_name = crypt_name->disk_name;
113 #ifdef CONFIG_FS_ENCRYPTION
114 	fname->crypto_buf = crypt_name->crypto_buf;
115 #endif
116 	if (crypt_name->is_nokey_name) {
117 		/* hash was decoded from the no-key name */
118 		fname->hash = cpu_to_le32(crypt_name->hash);
119 	} else {
120 		err = f2fs_init_casefolded_name(dir, fname);
121 		if (err) {
122 			f2fs_free_filename(fname);
123 			return err;
124 		}
125 		f2fs_hash_filename(dir, fname);
126 	}
127 	return 0;
128 }
129 
130 /*
131  * Prepare to search for @iname in @dir.  This is similar to
132  * fscrypt_setup_filename(), but this also handles computing the casefolded name
133  * and the f2fs dirhash if needed, then packing all the information about this
134  * filename up into a 'struct f2fs_filename'.
135  */
136 int f2fs_setup_filename(struct inode *dir, const struct qstr *iname,
137 			int lookup, struct f2fs_filename *fname)
138 {
139 	struct fscrypt_name crypt_name;
140 	int err;
141 
142 	err = fscrypt_setup_filename(dir, iname, lookup, &crypt_name);
143 	if (err)
144 		return err;
145 
146 	return __f2fs_setup_filename(dir, &crypt_name, fname);
147 }
148 
149 /*
150  * Prepare to look up @dentry in @dir.  This is similar to
151  * fscrypt_prepare_lookup(), but this also handles computing the casefolded name
152  * and the f2fs dirhash if needed, then packing all the information about this
153  * filename up into a 'struct f2fs_filename'.
154  */
155 int f2fs_prepare_lookup(struct inode *dir, struct dentry *dentry,
156 			struct f2fs_filename *fname)
157 {
158 	struct fscrypt_name crypt_name;
159 	int err;
160 
161 	err = fscrypt_prepare_lookup(dir, dentry, &crypt_name);
162 	if (err)
163 		return err;
164 
165 	return __f2fs_setup_filename(dir, &crypt_name, fname);
166 }
167 
168 void f2fs_free_filename(struct f2fs_filename *fname)
169 {
170 #ifdef CONFIG_FS_ENCRYPTION
171 	kfree(fname->crypto_buf.name);
172 	fname->crypto_buf.name = NULL;
173 #endif
174 #ifdef CONFIG_UNICODE
175 	kfree(fname->cf_name.name);
176 	fname->cf_name.name = NULL;
177 #endif
178 }
179 
180 static unsigned long dir_block_index(unsigned int level,
181 				int dir_level, unsigned int idx)
182 {
183 	unsigned long i;
184 	unsigned long bidx = 0;
185 
186 	for (i = 0; i < level; i++)
187 		bidx += dir_buckets(i, dir_level) * bucket_blocks(i);
188 	bidx += idx * bucket_blocks(level);
189 	return bidx;
190 }
191 
192 static struct f2fs_dir_entry *find_in_block(struct inode *dir,
193 				struct page *dentry_page,
194 				const struct f2fs_filename *fname,
195 				int *max_slots)
196 {
197 	struct f2fs_dentry_block *dentry_blk;
198 	struct f2fs_dentry_ptr d;
199 
200 	dentry_blk = (struct f2fs_dentry_block *)page_address(dentry_page);
201 
202 	make_dentry_ptr_block(dir, &d, dentry_blk);
203 	return f2fs_find_target_dentry(&d, fname, max_slots);
204 }
205 
206 #ifdef CONFIG_UNICODE
207 /*
208  * Test whether a case-insensitive directory entry matches the filename
209  * being searched for.
210  *
211  * Returns 1 for a match, 0 for no match, and -errno on an error.
212  */
213 static int f2fs_match_ci_name(const struct inode *dir, const struct qstr *name,
214 			       const u8 *de_name, u32 de_name_len)
215 {
216 	const struct super_block *sb = dir->i_sb;
217 	const struct unicode_map *um = sb->s_encoding;
218 	struct fscrypt_str decrypted_name = FSTR_INIT(NULL, de_name_len);
219 	struct qstr entry = QSTR_INIT(de_name, de_name_len);
220 	int res;
221 
222 	if (IS_ENCRYPTED(dir)) {
223 		const struct fscrypt_str encrypted_name =
224 			FSTR_INIT((u8 *)de_name, de_name_len);
225 
226 		if (WARN_ON_ONCE(!fscrypt_has_encryption_key(dir)))
227 			return -EINVAL;
228 
229 		decrypted_name.name = kmalloc(de_name_len, GFP_KERNEL);
230 		if (!decrypted_name.name)
231 			return -ENOMEM;
232 		res = fscrypt_fname_disk_to_usr(dir, 0, 0, &encrypted_name,
233 						&decrypted_name);
234 		if (res < 0)
235 			goto out;
236 		entry.name = decrypted_name.name;
237 		entry.len = decrypted_name.len;
238 	}
239 
240 	res = utf8_strncasecmp_folded(um, name, &entry);
241 	/*
242 	 * In strict mode, ignore invalid names.  In non-strict mode,
243 	 * fall back to treating them as opaque byte sequences.
244 	 */
245 	if (res < 0 && !sb_has_strict_encoding(sb)) {
246 		res = name->len == entry.len &&
247 				memcmp(name->name, entry.name, name->len) == 0;
248 	} else {
249 		/* utf8_strncasecmp_folded returns 0 on match */
250 		res = (res == 0);
251 	}
252 out:
253 	kfree(decrypted_name.name);
254 	return res;
255 }
256 #endif /* CONFIG_UNICODE */
257 
258 static inline int f2fs_match_name(const struct inode *dir,
259 				   const struct f2fs_filename *fname,
260 				   const u8 *de_name, u32 de_name_len)
261 {
262 	struct fscrypt_name f;
263 
264 #ifdef CONFIG_UNICODE
265 	if (fname->cf_name.name) {
266 		struct qstr cf = FSTR_TO_QSTR(&fname->cf_name);
267 
268 		return f2fs_match_ci_name(dir, &cf, de_name, de_name_len);
269 	}
270 #endif
271 	f.usr_fname = fname->usr_fname;
272 	f.disk_name = fname->disk_name;
273 #ifdef CONFIG_FS_ENCRYPTION
274 	f.crypto_buf = fname->crypto_buf;
275 #endif
276 	return fscrypt_match_name(&f, de_name, de_name_len);
277 }
278 
279 struct f2fs_dir_entry *f2fs_find_target_dentry(const struct f2fs_dentry_ptr *d,
280 			const struct f2fs_filename *fname, int *max_slots)
281 {
282 	struct f2fs_dir_entry *de;
283 	unsigned long bit_pos = 0;
284 	int max_len = 0;
285 	int res = 0;
286 
287 	if (max_slots)
288 		*max_slots = 0;
289 	while (bit_pos < d->max) {
290 		if (!test_bit_le(bit_pos, d->bitmap)) {
291 			bit_pos++;
292 			max_len++;
293 			continue;
294 		}
295 
296 		de = &d->dentry[bit_pos];
297 
298 		if (unlikely(!de->name_len)) {
299 			bit_pos++;
300 			continue;
301 		}
302 
303 		if (de->hash_code == fname->hash) {
304 			res = f2fs_match_name(d->inode, fname,
305 					      d->filename[bit_pos],
306 					      le16_to_cpu(de->name_len));
307 			if (res < 0)
308 				return ERR_PTR(res);
309 			if (res)
310 				goto found;
311 		}
312 
313 		if (max_slots && max_len > *max_slots)
314 			*max_slots = max_len;
315 		max_len = 0;
316 
317 		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
318 	}
319 
320 	de = NULL;
321 found:
322 	if (max_slots && max_len > *max_slots)
323 		*max_slots = max_len;
324 	return de;
325 }
326 
327 static struct f2fs_dir_entry *find_in_level(struct inode *dir,
328 					unsigned int level,
329 					const struct f2fs_filename *fname,
330 					struct page **res_page)
331 {
332 	int s = GET_DENTRY_SLOTS(fname->disk_name.len);
333 	unsigned int nbucket, nblock;
334 	unsigned int bidx, end_block;
335 	struct page *dentry_page;
336 	struct f2fs_dir_entry *de = NULL;
337 	bool room = false;
338 	int max_slots;
339 
340 	nbucket = dir_buckets(level, F2FS_I(dir)->i_dir_level);
341 	nblock = bucket_blocks(level);
342 
343 	bidx = dir_block_index(level, F2FS_I(dir)->i_dir_level,
344 			       le32_to_cpu(fname->hash) % nbucket);
345 	end_block = bidx + nblock;
346 
347 	for (; bidx < end_block; bidx++) {
348 		/* no need to allocate new dentry pages to all the indices */
349 		dentry_page = f2fs_find_data_page(dir, bidx);
350 		if (IS_ERR(dentry_page)) {
351 			if (PTR_ERR(dentry_page) == -ENOENT) {
352 				room = true;
353 				continue;
354 			} else {
355 				*res_page = dentry_page;
356 				break;
357 			}
358 		}
359 
360 		de = find_in_block(dir, dentry_page, fname, &max_slots);
361 		if (IS_ERR(de)) {
362 			*res_page = ERR_CAST(de);
363 			de = NULL;
364 			break;
365 		} else if (de) {
366 			*res_page = dentry_page;
367 			break;
368 		}
369 
370 		if (max_slots >= s)
371 			room = true;
372 		f2fs_put_page(dentry_page, 0);
373 	}
374 
375 	if (!de && room && F2FS_I(dir)->chash != fname->hash) {
376 		F2FS_I(dir)->chash = fname->hash;
377 		F2FS_I(dir)->clevel = level;
378 	}
379 
380 	return de;
381 }
382 
383 struct f2fs_dir_entry *__f2fs_find_entry(struct inode *dir,
384 					 const struct f2fs_filename *fname,
385 					 struct page **res_page)
386 {
387 	unsigned long npages = dir_blocks(dir);
388 	struct f2fs_dir_entry *de = NULL;
389 	unsigned int max_depth;
390 	unsigned int level;
391 
392 	*res_page = NULL;
393 
394 	if (f2fs_has_inline_dentry(dir)) {
395 		de = f2fs_find_in_inline_dir(dir, fname, res_page);
396 		goto out;
397 	}
398 
399 	if (npages == 0)
400 		goto out;
401 
402 	max_depth = F2FS_I(dir)->i_current_depth;
403 	if (unlikely(max_depth > MAX_DIR_HASH_DEPTH)) {
404 		f2fs_warn(F2FS_I_SB(dir), "Corrupted max_depth of %lu: %u",
405 			  dir->i_ino, max_depth);
406 		max_depth = MAX_DIR_HASH_DEPTH;
407 		f2fs_i_depth_write(dir, max_depth);
408 	}
409 
410 	for (level = 0; level < max_depth; level++) {
411 		de = find_in_level(dir, level, fname, res_page);
412 		if (de || IS_ERR(*res_page))
413 			break;
414 	}
415 out:
416 	/* This is to increase the speed of f2fs_create */
417 	if (!de)
418 		F2FS_I(dir)->task = current;
419 	return de;
420 }
421 
422 /*
423  * Find an entry in the specified directory with the wanted name.
424  * It returns the page where the entry was found (as a parameter - res_page),
425  * and the entry itself. Page is returned mapped and unlocked.
426  * Entry is guaranteed to be valid.
427  */
428 struct f2fs_dir_entry *f2fs_find_entry(struct inode *dir,
429 			const struct qstr *child, struct page **res_page)
430 {
431 	struct f2fs_dir_entry *de = NULL;
432 	struct f2fs_filename fname;
433 	int err;
434 
435 	err = f2fs_setup_filename(dir, child, 1, &fname);
436 	if (err) {
437 		if (err == -ENOENT)
438 			*res_page = NULL;
439 		else
440 			*res_page = ERR_PTR(err);
441 		return NULL;
442 	}
443 
444 	de = __f2fs_find_entry(dir, &fname, res_page);
445 
446 	f2fs_free_filename(&fname);
447 	return de;
448 }
449 
450 struct f2fs_dir_entry *f2fs_parent_dir(struct inode *dir, struct page **p)
451 {
452 	return f2fs_find_entry(dir, &dotdot_name, p);
453 }
454 
455 ino_t f2fs_inode_by_name(struct inode *dir, const struct qstr *qstr,
456 							struct page **page)
457 {
458 	ino_t res = 0;
459 	struct f2fs_dir_entry *de;
460 
461 	de = f2fs_find_entry(dir, qstr, page);
462 	if (de) {
463 		res = le32_to_cpu(de->ino);
464 		f2fs_put_page(*page, 0);
465 	}
466 
467 	return res;
468 }
469 
470 void f2fs_set_link(struct inode *dir, struct f2fs_dir_entry *de,
471 		struct page *page, struct inode *inode)
472 {
473 	enum page_type type = f2fs_has_inline_dentry(dir) ? NODE : DATA;
474 
475 	lock_page(page);
476 	f2fs_wait_on_page_writeback(page, type, true, true);
477 	de->ino = cpu_to_le32(inode->i_ino);
478 	set_de_type(de, inode->i_mode);
479 	set_page_dirty(page);
480 
481 	dir->i_mtime = dir->i_ctime = current_time(dir);
482 	f2fs_mark_inode_dirty_sync(dir, false);
483 	f2fs_put_page(page, 1);
484 }
485 
486 static void init_dent_inode(struct inode *dir, struct inode *inode,
487 			    const struct f2fs_filename *fname,
488 			    struct page *ipage)
489 {
490 	struct f2fs_inode *ri;
491 
492 	if (!fname) /* tmpfile case? */
493 		return;
494 
495 	f2fs_wait_on_page_writeback(ipage, NODE, true, true);
496 
497 	/* copy name info. to this inode page */
498 	ri = F2FS_INODE(ipage);
499 	ri->i_namelen = cpu_to_le32(fname->disk_name.len);
500 	memcpy(ri->i_name, fname->disk_name.name, fname->disk_name.len);
501 	if (IS_ENCRYPTED(dir)) {
502 		file_set_enc_name(inode);
503 		/*
504 		 * Roll-forward recovery doesn't have encryption keys available,
505 		 * so it can't compute the dirhash for encrypted+casefolded
506 		 * filenames.  Append it to i_name if possible.  Else, disable
507 		 * roll-forward recovery of the dentry (i.e., make fsync'ing the
508 		 * file force a checkpoint) by setting LOST_PINO.
509 		 */
510 		if (IS_CASEFOLDED(dir)) {
511 			if (fname->disk_name.len + sizeof(f2fs_hash_t) <=
512 			    F2FS_NAME_LEN)
513 				put_unaligned(fname->hash, (f2fs_hash_t *)
514 					&ri->i_name[fname->disk_name.len]);
515 			else
516 				file_lost_pino(inode);
517 		}
518 	}
519 	set_page_dirty(ipage);
520 }
521 
522 void f2fs_do_make_empty_dir(struct inode *inode, struct inode *parent,
523 					struct f2fs_dentry_ptr *d)
524 {
525 	struct fscrypt_str dot = FSTR_INIT(".", 1);
526 	struct fscrypt_str dotdot = FSTR_INIT("..", 2);
527 
528 	/* update dirent of "." */
529 	f2fs_update_dentry(inode->i_ino, inode->i_mode, d, &dot, 0, 0);
530 
531 	/* update dirent of ".." */
532 	f2fs_update_dentry(parent->i_ino, parent->i_mode, d, &dotdot, 0, 1);
533 }
534 
535 static int make_empty_dir(struct inode *inode,
536 		struct inode *parent, struct page *page)
537 {
538 	struct page *dentry_page;
539 	struct f2fs_dentry_block *dentry_blk;
540 	struct f2fs_dentry_ptr d;
541 
542 	if (f2fs_has_inline_dentry(inode))
543 		return f2fs_make_empty_inline_dir(inode, parent, page);
544 
545 	dentry_page = f2fs_get_new_data_page(inode, page, 0, true);
546 	if (IS_ERR(dentry_page))
547 		return PTR_ERR(dentry_page);
548 
549 	dentry_blk = page_address(dentry_page);
550 
551 	make_dentry_ptr_block(NULL, &d, dentry_blk);
552 	f2fs_do_make_empty_dir(inode, parent, &d);
553 
554 	set_page_dirty(dentry_page);
555 	f2fs_put_page(dentry_page, 1);
556 	return 0;
557 }
558 
559 struct page *f2fs_init_inode_metadata(struct inode *inode, struct inode *dir,
560 			const struct f2fs_filename *fname, struct page *dpage)
561 {
562 	struct page *page;
563 	int err;
564 
565 	if (is_inode_flag_set(inode, FI_NEW_INODE)) {
566 		page = f2fs_new_inode_page(inode);
567 		if (IS_ERR(page))
568 			return page;
569 
570 		if (S_ISDIR(inode->i_mode)) {
571 			/* in order to handle error case */
572 			get_page(page);
573 			err = make_empty_dir(inode, dir, page);
574 			if (err) {
575 				lock_page(page);
576 				goto put_error;
577 			}
578 			put_page(page);
579 		}
580 
581 		err = f2fs_init_acl(inode, dir, page, dpage);
582 		if (err)
583 			goto put_error;
584 
585 		err = f2fs_init_security(inode, dir,
586 					 fname ? fname->usr_fname : NULL, page);
587 		if (err)
588 			goto put_error;
589 
590 		if (IS_ENCRYPTED(inode)) {
591 			err = fscrypt_set_context(inode, page);
592 			if (err)
593 				goto put_error;
594 		}
595 	} else {
596 		page = f2fs_get_node_page(F2FS_I_SB(dir), inode->i_ino);
597 		if (IS_ERR(page))
598 			return page;
599 	}
600 
601 	init_dent_inode(dir, inode, fname, page);
602 
603 	/*
604 	 * This file should be checkpointed during fsync.
605 	 * We lost i_pino from now on.
606 	 */
607 	if (is_inode_flag_set(inode, FI_INC_LINK)) {
608 		if (!S_ISDIR(inode->i_mode))
609 			file_lost_pino(inode);
610 		/*
611 		 * If link the tmpfile to alias through linkat path,
612 		 * we should remove this inode from orphan list.
613 		 */
614 		if (inode->i_nlink == 0)
615 			f2fs_remove_orphan_inode(F2FS_I_SB(dir), inode->i_ino);
616 		f2fs_i_links_write(inode, true);
617 	}
618 	return page;
619 
620 put_error:
621 	clear_nlink(inode);
622 	f2fs_update_inode(inode, page);
623 	f2fs_put_page(page, 1);
624 	return ERR_PTR(err);
625 }
626 
627 void f2fs_update_parent_metadata(struct inode *dir, struct inode *inode,
628 						unsigned int current_depth)
629 {
630 	if (inode && is_inode_flag_set(inode, FI_NEW_INODE)) {
631 		if (S_ISDIR(inode->i_mode))
632 			f2fs_i_links_write(dir, true);
633 		clear_inode_flag(inode, FI_NEW_INODE);
634 	}
635 	dir->i_mtime = dir->i_ctime = current_time(dir);
636 	f2fs_mark_inode_dirty_sync(dir, false);
637 
638 	if (F2FS_I(dir)->i_current_depth != current_depth)
639 		f2fs_i_depth_write(dir, current_depth);
640 
641 	if (inode && is_inode_flag_set(inode, FI_INC_LINK))
642 		clear_inode_flag(inode, FI_INC_LINK);
643 }
644 
645 int f2fs_room_for_filename(const void *bitmap, int slots, int max_slots)
646 {
647 	int bit_start = 0;
648 	int zero_start, zero_end;
649 next:
650 	zero_start = find_next_zero_bit_le(bitmap, max_slots, bit_start);
651 	if (zero_start >= max_slots)
652 		return max_slots;
653 
654 	zero_end = find_next_bit_le(bitmap, max_slots, zero_start);
655 	if (zero_end - zero_start >= slots)
656 		return zero_start;
657 
658 	bit_start = zero_end + 1;
659 
660 	if (zero_end + 1 >= max_slots)
661 		return max_slots;
662 	goto next;
663 }
664 
665 bool f2fs_has_enough_room(struct inode *dir, struct page *ipage,
666 			  const struct f2fs_filename *fname)
667 {
668 	struct f2fs_dentry_ptr d;
669 	unsigned int bit_pos;
670 	int slots = GET_DENTRY_SLOTS(fname->disk_name.len);
671 
672 	make_dentry_ptr_inline(dir, &d, inline_data_addr(dir, ipage));
673 
674 	bit_pos = f2fs_room_for_filename(d.bitmap, slots, d.max);
675 
676 	return bit_pos < d.max;
677 }
678 
679 void f2fs_update_dentry(nid_t ino, umode_t mode, struct f2fs_dentry_ptr *d,
680 			const struct fscrypt_str *name, f2fs_hash_t name_hash,
681 			unsigned int bit_pos)
682 {
683 	struct f2fs_dir_entry *de;
684 	int slots = GET_DENTRY_SLOTS(name->len);
685 	int i;
686 
687 	de = &d->dentry[bit_pos];
688 	de->hash_code = name_hash;
689 	de->name_len = cpu_to_le16(name->len);
690 	memcpy(d->filename[bit_pos], name->name, name->len);
691 	de->ino = cpu_to_le32(ino);
692 	set_de_type(de, mode);
693 	for (i = 0; i < slots; i++) {
694 		__set_bit_le(bit_pos + i, (void *)d->bitmap);
695 		/* avoid wrong garbage data for readdir */
696 		if (i)
697 			(de + i)->name_len = 0;
698 	}
699 }
700 
701 int f2fs_add_regular_entry(struct inode *dir, const struct f2fs_filename *fname,
702 			   struct inode *inode, nid_t ino, umode_t mode)
703 {
704 	unsigned int bit_pos;
705 	unsigned int level;
706 	unsigned int current_depth;
707 	unsigned long bidx, block;
708 	unsigned int nbucket, nblock;
709 	struct page *dentry_page = NULL;
710 	struct f2fs_dentry_block *dentry_blk = NULL;
711 	struct f2fs_dentry_ptr d;
712 	struct page *page = NULL;
713 	int slots, err = 0;
714 
715 	level = 0;
716 	slots = GET_DENTRY_SLOTS(fname->disk_name.len);
717 
718 	current_depth = F2FS_I(dir)->i_current_depth;
719 	if (F2FS_I(dir)->chash == fname->hash) {
720 		level = F2FS_I(dir)->clevel;
721 		F2FS_I(dir)->chash = 0;
722 	}
723 
724 start:
725 	if (time_to_inject(F2FS_I_SB(dir), FAULT_DIR_DEPTH)) {
726 		f2fs_show_injection_info(F2FS_I_SB(dir), FAULT_DIR_DEPTH);
727 		return -ENOSPC;
728 	}
729 
730 	if (unlikely(current_depth == MAX_DIR_HASH_DEPTH))
731 		return -ENOSPC;
732 
733 	/* Increase the depth, if required */
734 	if (level == current_depth)
735 		++current_depth;
736 
737 	nbucket = dir_buckets(level, F2FS_I(dir)->i_dir_level);
738 	nblock = bucket_blocks(level);
739 
740 	bidx = dir_block_index(level, F2FS_I(dir)->i_dir_level,
741 				(le32_to_cpu(fname->hash) % nbucket));
742 
743 	for (block = bidx; block <= (bidx + nblock - 1); block++) {
744 		dentry_page = f2fs_get_new_data_page(dir, NULL, block, true);
745 		if (IS_ERR(dentry_page))
746 			return PTR_ERR(dentry_page);
747 
748 		dentry_blk = page_address(dentry_page);
749 		bit_pos = f2fs_room_for_filename(&dentry_blk->dentry_bitmap,
750 						slots, NR_DENTRY_IN_BLOCK);
751 		if (bit_pos < NR_DENTRY_IN_BLOCK)
752 			goto add_dentry;
753 
754 		f2fs_put_page(dentry_page, 1);
755 	}
756 
757 	/* Move to next level to find the empty slot for new dentry */
758 	++level;
759 	goto start;
760 add_dentry:
761 	f2fs_wait_on_page_writeback(dentry_page, DATA, true, true);
762 
763 	if (inode) {
764 		down_write(&F2FS_I(inode)->i_sem);
765 		page = f2fs_init_inode_metadata(inode, dir, fname, NULL);
766 		if (IS_ERR(page)) {
767 			err = PTR_ERR(page);
768 			goto fail;
769 		}
770 	}
771 
772 	make_dentry_ptr_block(NULL, &d, dentry_blk);
773 	f2fs_update_dentry(ino, mode, &d, &fname->disk_name, fname->hash,
774 			   bit_pos);
775 
776 	set_page_dirty(dentry_page);
777 
778 	if (inode) {
779 		f2fs_i_pino_write(inode, dir->i_ino);
780 
781 		/* synchronize inode page's data from inode cache */
782 		if (is_inode_flag_set(inode, FI_NEW_INODE))
783 			f2fs_update_inode(inode, page);
784 
785 		f2fs_put_page(page, 1);
786 	}
787 
788 	f2fs_update_parent_metadata(dir, inode, current_depth);
789 fail:
790 	if (inode)
791 		up_write(&F2FS_I(inode)->i_sem);
792 
793 	f2fs_put_page(dentry_page, 1);
794 
795 	return err;
796 }
797 
798 int f2fs_add_dentry(struct inode *dir, const struct f2fs_filename *fname,
799 		    struct inode *inode, nid_t ino, umode_t mode)
800 {
801 	int err = -EAGAIN;
802 
803 	if (f2fs_has_inline_dentry(dir))
804 		err = f2fs_add_inline_entry(dir, fname, inode, ino, mode);
805 	if (err == -EAGAIN)
806 		err = f2fs_add_regular_entry(dir, fname, inode, ino, mode);
807 
808 	f2fs_update_time(F2FS_I_SB(dir), REQ_TIME);
809 	return err;
810 }
811 
812 /*
813  * Caller should grab and release a rwsem by calling f2fs_lock_op() and
814  * f2fs_unlock_op().
815  */
816 int f2fs_do_add_link(struct inode *dir, const struct qstr *name,
817 				struct inode *inode, nid_t ino, umode_t mode)
818 {
819 	struct f2fs_filename fname;
820 	struct page *page = NULL;
821 	struct f2fs_dir_entry *de = NULL;
822 	int err;
823 
824 	err = f2fs_setup_filename(dir, name, 0, &fname);
825 	if (err)
826 		return err;
827 
828 	/*
829 	 * An immature stackable filesystem shows a race condition between lookup
830 	 * and create. If we have same task when doing lookup and create, it's
831 	 * definitely fine as expected by VFS normally. Otherwise, let's just
832 	 * verify on-disk dentry one more time, which guarantees filesystem
833 	 * consistency more.
834 	 */
835 	if (current != F2FS_I(dir)->task) {
836 		de = __f2fs_find_entry(dir, &fname, &page);
837 		F2FS_I(dir)->task = NULL;
838 	}
839 	if (de) {
840 		f2fs_put_page(page, 0);
841 		err = -EEXIST;
842 	} else if (IS_ERR(page)) {
843 		err = PTR_ERR(page);
844 	} else {
845 		err = f2fs_add_dentry(dir, &fname, inode, ino, mode);
846 	}
847 	f2fs_free_filename(&fname);
848 	return err;
849 }
850 
851 int f2fs_do_tmpfile(struct inode *inode, struct inode *dir)
852 {
853 	struct page *page;
854 	int err = 0;
855 
856 	down_write(&F2FS_I(inode)->i_sem);
857 	page = f2fs_init_inode_metadata(inode, dir, NULL, NULL);
858 	if (IS_ERR(page)) {
859 		err = PTR_ERR(page);
860 		goto fail;
861 	}
862 	f2fs_put_page(page, 1);
863 
864 	clear_inode_flag(inode, FI_NEW_INODE);
865 	f2fs_update_time(F2FS_I_SB(inode), REQ_TIME);
866 fail:
867 	up_write(&F2FS_I(inode)->i_sem);
868 	return err;
869 }
870 
871 void f2fs_drop_nlink(struct inode *dir, struct inode *inode)
872 {
873 	struct f2fs_sb_info *sbi = F2FS_I_SB(dir);
874 
875 	down_write(&F2FS_I(inode)->i_sem);
876 
877 	if (S_ISDIR(inode->i_mode))
878 		f2fs_i_links_write(dir, false);
879 	inode->i_ctime = current_time(inode);
880 
881 	f2fs_i_links_write(inode, false);
882 	if (S_ISDIR(inode->i_mode)) {
883 		f2fs_i_links_write(inode, false);
884 		f2fs_i_size_write(inode, 0);
885 	}
886 	up_write(&F2FS_I(inode)->i_sem);
887 
888 	if (inode->i_nlink == 0)
889 		f2fs_add_orphan_inode(inode);
890 	else
891 		f2fs_release_orphan_inode(sbi);
892 }
893 
894 /*
895  * It only removes the dentry from the dentry page, corresponding name
896  * entry in name page does not need to be touched during deletion.
897  */
898 void f2fs_delete_entry(struct f2fs_dir_entry *dentry, struct page *page,
899 					struct inode *dir, struct inode *inode)
900 {
901 	struct	f2fs_dentry_block *dentry_blk;
902 	unsigned int bit_pos;
903 	int slots = GET_DENTRY_SLOTS(le16_to_cpu(dentry->name_len));
904 	int i;
905 
906 	f2fs_update_time(F2FS_I_SB(dir), REQ_TIME);
907 
908 	if (F2FS_OPTION(F2FS_I_SB(dir)).fsync_mode == FSYNC_MODE_STRICT)
909 		f2fs_add_ino_entry(F2FS_I_SB(dir), dir->i_ino, TRANS_DIR_INO);
910 
911 	if (f2fs_has_inline_dentry(dir))
912 		return f2fs_delete_inline_entry(dentry, page, dir, inode);
913 
914 	lock_page(page);
915 	f2fs_wait_on_page_writeback(page, DATA, true, true);
916 
917 	dentry_blk = page_address(page);
918 	bit_pos = dentry - dentry_blk->dentry;
919 	for (i = 0; i < slots; i++)
920 		__clear_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap);
921 
922 	/* Let's check and deallocate this dentry page */
923 	bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap,
924 			NR_DENTRY_IN_BLOCK,
925 			0);
926 	set_page_dirty(page);
927 
928 	if (bit_pos == NR_DENTRY_IN_BLOCK &&
929 		!f2fs_truncate_hole(dir, page->index, page->index + 1)) {
930 		f2fs_clear_page_cache_dirty_tag(page);
931 		clear_page_dirty_for_io(page);
932 		f2fs_clear_page_private(page);
933 		ClearPageUptodate(page);
934 		clear_cold_data(page);
935 		inode_dec_dirty_pages(dir);
936 		f2fs_remove_dirty_inode(dir);
937 	}
938 	f2fs_put_page(page, 1);
939 
940 	dir->i_ctime = dir->i_mtime = current_time(dir);
941 	f2fs_mark_inode_dirty_sync(dir, false);
942 
943 	if (inode)
944 		f2fs_drop_nlink(dir, inode);
945 }
946 
947 bool f2fs_empty_dir(struct inode *dir)
948 {
949 	unsigned long bidx;
950 	struct page *dentry_page;
951 	unsigned int bit_pos;
952 	struct f2fs_dentry_block *dentry_blk;
953 	unsigned long nblock = dir_blocks(dir);
954 
955 	if (f2fs_has_inline_dentry(dir))
956 		return f2fs_empty_inline_dir(dir);
957 
958 	for (bidx = 0; bidx < nblock; bidx++) {
959 		dentry_page = f2fs_get_lock_data_page(dir, bidx, false);
960 		if (IS_ERR(dentry_page)) {
961 			if (PTR_ERR(dentry_page) == -ENOENT)
962 				continue;
963 			else
964 				return false;
965 		}
966 
967 		dentry_blk = page_address(dentry_page);
968 		if (bidx == 0)
969 			bit_pos = 2;
970 		else
971 			bit_pos = 0;
972 		bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap,
973 						NR_DENTRY_IN_BLOCK,
974 						bit_pos);
975 
976 		f2fs_put_page(dentry_page, 1);
977 
978 		if (bit_pos < NR_DENTRY_IN_BLOCK)
979 			return false;
980 	}
981 	return true;
982 }
983 
984 int f2fs_fill_dentries(struct dir_context *ctx, struct f2fs_dentry_ptr *d,
985 			unsigned int start_pos, struct fscrypt_str *fstr)
986 {
987 	unsigned char d_type = DT_UNKNOWN;
988 	unsigned int bit_pos;
989 	struct f2fs_dir_entry *de = NULL;
990 	struct fscrypt_str de_name = FSTR_INIT(NULL, 0);
991 	struct f2fs_sb_info *sbi = F2FS_I_SB(d->inode);
992 	struct blk_plug plug;
993 	bool readdir_ra = sbi->readdir_ra == 1;
994 	int err = 0;
995 
996 	bit_pos = ((unsigned long)ctx->pos % d->max);
997 
998 	if (readdir_ra)
999 		blk_start_plug(&plug);
1000 
1001 	while (bit_pos < d->max) {
1002 		bit_pos = find_next_bit_le(d->bitmap, d->max, bit_pos);
1003 		if (bit_pos >= d->max)
1004 			break;
1005 
1006 		de = &d->dentry[bit_pos];
1007 		if (de->name_len == 0) {
1008 			bit_pos++;
1009 			ctx->pos = start_pos + bit_pos;
1010 			printk_ratelimited(
1011 				"%sF2FS-fs (%s): invalid namelen(0), ino:%u, run fsck to fix.",
1012 				KERN_WARNING, sbi->sb->s_id,
1013 				le32_to_cpu(de->ino));
1014 			set_sbi_flag(sbi, SBI_NEED_FSCK);
1015 			continue;
1016 		}
1017 
1018 		d_type = f2fs_get_de_type(de);
1019 
1020 		de_name.name = d->filename[bit_pos];
1021 		de_name.len = le16_to_cpu(de->name_len);
1022 
1023 		/* check memory boundary before moving forward */
1024 		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
1025 		if (unlikely(bit_pos > d->max ||
1026 				le16_to_cpu(de->name_len) > F2FS_NAME_LEN)) {
1027 			f2fs_warn(sbi, "%s: corrupted namelen=%d, run fsck to fix.",
1028 				  __func__, le16_to_cpu(de->name_len));
1029 			set_sbi_flag(sbi, SBI_NEED_FSCK);
1030 			err = -EFSCORRUPTED;
1031 			goto out;
1032 		}
1033 
1034 		if (IS_ENCRYPTED(d->inode)) {
1035 			int save_len = fstr->len;
1036 
1037 			err = fscrypt_fname_disk_to_usr(d->inode,
1038 						(u32)le32_to_cpu(de->hash_code),
1039 						0, &de_name, fstr);
1040 			if (err)
1041 				goto out;
1042 
1043 			de_name = *fstr;
1044 			fstr->len = save_len;
1045 		}
1046 
1047 		if (!dir_emit(ctx, de_name.name, de_name.len,
1048 					le32_to_cpu(de->ino), d_type)) {
1049 			err = 1;
1050 			goto out;
1051 		}
1052 
1053 		if (readdir_ra)
1054 			f2fs_ra_node_page(sbi, le32_to_cpu(de->ino));
1055 
1056 		ctx->pos = start_pos + bit_pos;
1057 	}
1058 out:
1059 	if (readdir_ra)
1060 		blk_finish_plug(&plug);
1061 	return err;
1062 }
1063 
1064 static int f2fs_readdir(struct file *file, struct dir_context *ctx)
1065 {
1066 	struct inode *inode = file_inode(file);
1067 	unsigned long npages = dir_blocks(inode);
1068 	struct f2fs_dentry_block *dentry_blk = NULL;
1069 	struct page *dentry_page = NULL;
1070 	struct file_ra_state *ra = &file->f_ra;
1071 	loff_t start_pos = ctx->pos;
1072 	unsigned int n = ((unsigned long)ctx->pos / NR_DENTRY_IN_BLOCK);
1073 	struct f2fs_dentry_ptr d;
1074 	struct fscrypt_str fstr = FSTR_INIT(NULL, 0);
1075 	int err = 0;
1076 
1077 	if (IS_ENCRYPTED(inode)) {
1078 		err = fscrypt_prepare_readdir(inode);
1079 		if (err)
1080 			goto out;
1081 
1082 		err = fscrypt_fname_alloc_buffer(F2FS_NAME_LEN, &fstr);
1083 		if (err < 0)
1084 			goto out;
1085 	}
1086 
1087 	if (f2fs_has_inline_dentry(inode)) {
1088 		err = f2fs_read_inline_dir(file, ctx, &fstr);
1089 		goto out_free;
1090 	}
1091 
1092 	for (; n < npages; n++, ctx->pos = n * NR_DENTRY_IN_BLOCK) {
1093 
1094 		/* allow readdir() to be interrupted */
1095 		if (fatal_signal_pending(current)) {
1096 			err = -ERESTARTSYS;
1097 			goto out_free;
1098 		}
1099 		cond_resched();
1100 
1101 		/* readahead for multi pages of dir */
1102 		if (npages - n > 1 && !ra_has_index(ra, n))
1103 			page_cache_sync_readahead(inode->i_mapping, ra, file, n,
1104 				min(npages - n, (pgoff_t)MAX_DIR_RA_PAGES));
1105 
1106 		dentry_page = f2fs_find_data_page(inode, n);
1107 		if (IS_ERR(dentry_page)) {
1108 			err = PTR_ERR(dentry_page);
1109 			if (err == -ENOENT) {
1110 				err = 0;
1111 				continue;
1112 			} else {
1113 				goto out_free;
1114 			}
1115 		}
1116 
1117 		dentry_blk = page_address(dentry_page);
1118 
1119 		make_dentry_ptr_block(inode, &d, dentry_blk);
1120 
1121 		err = f2fs_fill_dentries(ctx, &d,
1122 				n * NR_DENTRY_IN_BLOCK, &fstr);
1123 		if (err) {
1124 			f2fs_put_page(dentry_page, 0);
1125 			break;
1126 		}
1127 
1128 		f2fs_put_page(dentry_page, 0);
1129 	}
1130 out_free:
1131 	fscrypt_fname_free_buffer(&fstr);
1132 out:
1133 	trace_f2fs_readdir(inode, start_pos, ctx->pos, err);
1134 	return err < 0 ? err : 0;
1135 }
1136 
1137 const struct file_operations f2fs_dir_operations = {
1138 	.llseek		= generic_file_llseek,
1139 	.read		= generic_read_dir,
1140 	.iterate_shared	= f2fs_readdir,
1141 	.fsync		= f2fs_sync_file,
1142 	.unlocked_ioctl	= f2fs_ioctl,
1143 #ifdef CONFIG_COMPAT
1144 	.compat_ioctl   = f2fs_compat_ioctl,
1145 #endif
1146 };
1147