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