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