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