fs/f2fs/dir.c

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