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