fs/ext4/namei.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  *  linux/fs/ext4/namei.c
   4  *
   5  * Copyright (C) 1992, 1993, 1994, 1995
   6  * Remy Card (card@masi.ibp.fr)
   7  * Laboratoire MASI - Institut Blaise Pascal
   8  * Universite Pierre et Marie Curie (Paris VI)
   9  *
  10  *  from
  11  *
  12  *  linux/fs/minix/namei.c
  13  *
  14  *  Copyright (C) 1991, 1992  Linus Torvalds
  15  *
  16  *  Big-endian to little-endian byte-swapping/bitmaps by
  17  *        David S. Miller (davem@caip.rutgers.edu), 1995
  18  *  Directory entry file type support and forward compatibility hooks
  19  *      for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998
  20  *  Hash Tree Directory indexing (c)
  21  *      Daniel Phillips, 2001
  22  *  Hash Tree Directory indexing porting
  23  *      Christopher Li, 2002
  24  *  Hash Tree Directory indexing cleanup
  25  *      Theodore Ts'o, 2002
  26  */
  27
  28 #include <linux/fs.h>
  29 #include <linux/pagemap.h>
  30 #include <linux/time.h>
  31 #include <linux/fcntl.h>
  32 #include <linux/stat.h>
  33 #include <linux/string.h>
  34 #include <linux/quotaops.h>
  35 #include <linux/buffer_head.h>
  36 #include <linux/bio.h>
  37 #include <linux/iversion.h>
  38 #include <linux/unicode.h>
  39 #include "ext4.h"
  40 #include "ext4_jbd2.h"
  41
  42 #include "xattr.h"
  43 #include "acl.h"
  44
  45 #include <trace/events/ext4.h>
  46 /*
  47  * define how far ahead to read directories while searching them.
  48  */
  49 #define NAMEI_RA_CHUNKS  2
  50 #define NAMEI_RA_BLOCKS  4
  51 #define NAMEI_RA_SIZE        (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
  52
  53 static struct buffer_head *ext4_append(handle_t *handle,
  54                                         struct inode *inode,
  55                                         ext4_lblk_t *block)
  56 {
  57         struct ext4_map_blocks map;
  58         struct buffer_head *bh;
  59         int err;
  60
  61         if (unlikely(EXT4_SB(inode->i_sb)->s_max_dir_size_kb &&
  62                      ((inode->i_size >> 10) >=
  63                       EXT4_SB(inode->i_sb)->s_max_dir_size_kb)))
  64                 return ERR_PTR(-ENOSPC);
  65
  66         *block = inode->i_size >> inode->i_sb->s_blocksize_bits;
  67         map.m_lblk = *block;
  68         map.m_len = 1;
  69
  70         /*
  71          * We're appending new directory block. Make sure the block is not
  72          * allocated yet, otherwise we will end up corrupting the
  73          * directory.
  74          */
  75         err = ext4_map_blocks(NULL, inode, &map, 0);
  76         if (err < 0)
  77                 return ERR_PTR(err);
  78         if (err) {
  79                 EXT4_ERROR_INODE(inode, "Logical block already allocated");
  80                 return ERR_PTR(-EFSCORRUPTED);
  81         }
  82
  83         bh = ext4_bread(handle, inode, *block, EXT4_GET_BLOCKS_CREATE);
  84         if (IS_ERR(bh))
  85                 return bh;
  86         inode->i_size += inode->i_sb->s_blocksize;
  87         EXT4_I(inode)->i_disksize = inode->i_size;
  88         BUFFER_TRACE(bh, "get_write_access");
  89         err = ext4_journal_get_write_access(handle, bh);
  90         if (err) {
  91                 brelse(bh);
  92                 ext4_std_error(inode->i_sb, err);
  93                 return ERR_PTR(err);
  94         }
  95         return bh;
  96 }
  97
  98 static int ext4_dx_csum_verify(struct inode *inode,
  99                                struct ext4_dir_entry *dirent);
 100
 101 /*
 102  * Hints to ext4_read_dirblock regarding whether we expect a directory
 103  * block being read to be an index block, or a block containing
 104  * directory entries (and if the latter, whether it was found via a
 105  * logical block in an htree index block).  This is used to control
 106  * what sort of sanity checkinig ext4_read_dirblock() will do on the
 107  * directory block read from the storage device.  EITHER will means
 108  * the caller doesn't know what kind of directory block will be read,
 109  * so no specific verification will be done.
 110  */
 111 typedef enum {
 112         EITHER, INDEX, DIRENT, DIRENT_HTREE
 113 } dirblock_type_t;
 114
 115 #define ext4_read_dirblock(inode, block, type) \
 116         __ext4_read_dirblock((inode), (block), (type), __func__, __LINE__)
 117
 118 static struct buffer_head *__ext4_read_dirblock(struct inode *inode,
 119                                                 ext4_lblk_t block,
 120                                                 dirblock_type_t type,
 121                                                 const char *func,
 122                                                 unsigned int line)
 123 {
 124         struct buffer_head *bh;
 125         struct ext4_dir_entry *dirent;
 126         int is_dx_block = 0;
 127
 128         if (block >= inode->i_size >> inode->i_blkbits) {
 129                 ext4_error_inode(inode, func, line, block,
 130                        "Attempting to read directory block (%u) that is past i_size (%llu)",
 131                        block, inode->i_size);
 132                 return ERR_PTR(-EFSCORRUPTED);
 133         }
 134
 135         if (ext4_simulate_fail(inode->i_sb, EXT4_SIM_DIRBLOCK_EIO))
 136                 bh = ERR_PTR(-EIO);
 137         else
 138                 bh = ext4_bread(NULL, inode, block, 0);
 139         if (IS_ERR(bh)) {
 140                 __ext4_warning(inode->i_sb, func, line,
 141                                "inode #%lu: lblock %lu: comm %s: "
 142                                "error %ld reading directory block",
 143                                inode->i_ino, (unsigned long)block,
 144                                current->comm, PTR_ERR(bh));
 145
 146                 return bh;
 147         }
 148         if (!bh && (type == INDEX || type == DIRENT_HTREE)) {
 149                 ext4_error_inode(inode, func, line, block,
 150                                  "Directory hole found for htree %s block",
 151                                  (type == INDEX) ? "index" : "leaf");
 152                 return ERR_PTR(-EFSCORRUPTED);
 153         }
 154         if (!bh)
 155                 return NULL;
 156         dirent = (struct ext4_dir_entry *) bh->b_data;
 157         /* Determine whether or not we have an index block */
 158         if (is_dx(inode)) {
 159                 if (block == 0)
 160                         is_dx_block = 1;
 161                 else if (ext4_rec_len_from_disk(dirent->rec_len,
 162                                                 inode->i_sb->s_blocksize) ==
 163                          inode->i_sb->s_blocksize)
 164                         is_dx_block = 1;
 165         }
 166         if (!is_dx_block && type == INDEX) {
 167                 ext4_error_inode(inode, func, line, block,
 168                        "directory leaf block found instead of index block");
 169                 brelse(bh);
 170                 return ERR_PTR(-EFSCORRUPTED);
 171         }
 172         if (!ext4_has_metadata_csum(inode->i_sb) ||
 173             buffer_verified(bh))
 174                 return bh;
 175
 176         /*
 177          * An empty leaf block can get mistaken for a index block; for
 178          * this reason, we can only check the index checksum when the
 179          * caller is sure it should be an index block.
 180          */
 181         if (is_dx_block && type == INDEX) {
 182                 if (ext4_dx_csum_verify(inode, dirent) &&
 183                     !ext4_simulate_fail(inode->i_sb, EXT4_SIM_DIRBLOCK_CRC))
 184                         set_buffer_verified(bh);
 185                 else {
 186                         ext4_error_inode_err(inode, func, line, block,
 187                                              EFSBADCRC,
 188                                              "Directory index failed checksum");
 189                         brelse(bh);
 190                         return ERR_PTR(-EFSBADCRC);
 191                 }
 192         }
 193         if (!is_dx_block) {
 194                 if (ext4_dirblock_csum_verify(inode, bh) &&
 195                     !ext4_simulate_fail(inode->i_sb, EXT4_SIM_DIRBLOCK_CRC))
 196                         set_buffer_verified(bh);
 197                 else {
 198                         ext4_error_inode_err(inode, func, line, block,
 199                                              EFSBADCRC,
 200                                              "Directory block failed checksum");
 201                         brelse(bh);
 202                         return ERR_PTR(-EFSBADCRC);
 203                 }
 204         }
 205         return bh;
 206 }
 207
 208 #ifndef assert
 209 #define assert(test) J_ASSERT(test)
 210 #endif
 211
 212 #ifdef DX_DEBUG
 213 #define dxtrace(command) command
 214 #else
 215 #define dxtrace(command)
 216 #endif
 217
 218 struct fake_dirent
 219 {
 220         __le32 inode;
 221         __le16 rec_len;
 222         u8 name_len;
 223         u8 file_type;
 224 };
 225
 226 struct dx_countlimit
 227 {
 228         __le16 limit;
 229         __le16 count;
 230 };
 231
 232 struct dx_entry
 233 {
 234         __le32 hash;
 235         __le32 block;
 236 };
 237
 238 /*
 239  * dx_root_info is laid out so that if it should somehow get overlaid by a
 240  * dirent the two low bits of the hash version will be zero.  Therefore, the
 241  * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
 242  */
 243
 244 struct dx_root
 245 {
 246         struct fake_dirent dot;
 247         char dot_name[4];
 248         struct fake_dirent dotdot;
 249         char dotdot_name[4];
 250         struct dx_root_info
 251         {
 252                 __le32 reserved_zero;
 253                 u8 hash_version;
 254                 u8 info_length; /* 8 */
 255                 u8 indirect_levels;
 256                 u8 unused_flags;
 257         }
 258         info;
 259         struct dx_entry entries[];
 260 };
 261
 262 struct dx_node
 263 {
 264         struct fake_dirent fake;
 265         struct dx_entry entries[];
 266 };
 267
 268
 269 struct dx_frame
 270 {
 271         struct buffer_head *bh;
 272         struct dx_entry *entries;
 273         struct dx_entry *at;
 274 };
 275
 276 struct dx_map_entry
 277 {
 278         u32 hash;
 279         u16 offs;
 280         u16 size;
 281 };
 282
 283 /*
 284  * This goes at the end of each htree block.
 285  */
 286 struct dx_tail {
 287         u32 dt_reserved;
 288         __le32 dt_checksum;     /* crc32c(uuid+inum+dirblock) */
 289 };
 290
 291 static inline ext4_lblk_t dx_get_block(struct dx_entry *entry);
 292 static void dx_set_block(struct dx_entry *entry, ext4_lblk_t value);
 293 static inline unsigned dx_get_hash(struct dx_entry *entry);
 294 static void dx_set_hash(struct dx_entry *entry, unsigned value);
 295 static unsigned dx_get_count(struct dx_entry *entries);
 296 static unsigned dx_get_limit(struct dx_entry *entries);
 297 static void dx_set_count(struct dx_entry *entries, unsigned value);
 298 static void dx_set_limit(struct dx_entry *entries, unsigned value);
 299 static unsigned dx_root_limit(struct inode *dir, unsigned infosize);
 300 static unsigned dx_node_limit(struct inode *dir);
 301 static struct dx_frame *dx_probe(struct ext4_filename *fname,
 302                                  struct inode *dir,
 303                                  struct dx_hash_info *hinfo,
 304                                  struct dx_frame *frame);
 305 static void dx_release(struct dx_frame *frames);
 306 static int dx_make_map(struct inode *dir, struct buffer_head *bh,
 307                        struct dx_hash_info *hinfo,
 308                        struct dx_map_entry *map_tail);
 309 static void dx_sort_map(struct dx_map_entry *map, unsigned count);
 310 static struct ext4_dir_entry_2 *dx_move_dirents(char *from, char *to,
 311                 struct dx_map_entry *offsets, int count, unsigned blocksize);
 312 static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize);
 313 static void dx_insert_block(struct dx_frame *frame,
 314                                         u32 hash, ext4_lblk_t block);
 315 static int ext4_htree_next_block(struct inode *dir, __u32 hash,
 316                                  struct dx_frame *frame,
 317                                  struct dx_frame *frames,
 318                                  __u32 *start_hash);
 319 static struct buffer_head * ext4_dx_find_entry(struct inode *dir,
 320                 struct ext4_filename *fname,
 321                 struct ext4_dir_entry_2 **res_dir);
 322 static int ext4_dx_add_entry(handle_t *handle, struct ext4_filename *fname,
 323                              struct inode *dir, struct inode *inode);
 324
 325 /* checksumming functions */
 326 void ext4_initialize_dirent_tail(struct buffer_head *bh,
 327                                  unsigned int blocksize)
 328 {
 329         struct ext4_dir_entry_tail *t = EXT4_DIRENT_TAIL(bh->b_data, blocksize);
 330
 331         memset(t, 0, sizeof(struct ext4_dir_entry_tail));
 332         t->det_rec_len = ext4_rec_len_to_disk(
 333                         sizeof(struct ext4_dir_entry_tail), blocksize);
 334         t->det_reserved_ft = EXT4_FT_DIR_CSUM;
 335 }
 336
 337 /* Walk through a dirent block to find a checksum "dirent" at the tail */
 338 static struct ext4_dir_entry_tail *get_dirent_tail(struct inode *inode,
 339                                                    struct buffer_head *bh)
 340 {
 341         struct ext4_dir_entry_tail *t;
 342
 343 #ifdef PARANOID
 344         struct ext4_dir_entry *d, *top;
 345
 346         d = (struct ext4_dir_entry *)bh->b_data;
 347         top = (struct ext4_dir_entry *)(bh->b_data +
 348                 (EXT4_BLOCK_SIZE(inode->i_sb) -
 349                  sizeof(struct ext4_dir_entry_tail)));
 350         while (d < top && d->rec_len)
 351                 d = (struct ext4_dir_entry *)(((void *)d) +
 352                     le16_to_cpu(d->rec_len));
 353
 354         if (d != top)
 355                 return NULL;
 356
 357         t = (struct ext4_dir_entry_tail *)d;
 358 #else
 359         t = EXT4_DIRENT_TAIL(bh->b_data, EXT4_BLOCK_SIZE(inode->i_sb));
 360 #endif
 361
 362         if (t->det_reserved_zero1 ||
 363             le16_to_cpu(t->det_rec_len) != sizeof(struct ext4_dir_entry_tail) ||
 364             t->det_reserved_zero2 ||
 365             t->det_reserved_ft != EXT4_FT_DIR_CSUM)
 366                 return NULL;
 367
 368         return t;
 369 }
 370
 371 static __le32 ext4_dirblock_csum(struct inode *inode, void *dirent, int size)
 372 {
 373         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 374         struct ext4_inode_info *ei = EXT4_I(inode);
 375         __u32 csum;
 376
 377         csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)dirent, size);
 378         return cpu_to_le32(csum);
 379 }
 380
 381 #define warn_no_space_for_csum(inode)                                   \
 382         __warn_no_space_for_csum((inode), __func__, __LINE__)
 383
 384 static void __warn_no_space_for_csum(struct inode *inode, const char *func,
 385                                      unsigned int line)
 386 {
 387         __ext4_warning_inode(inode, func, line,
 388                 "No space for directory leaf checksum. Please run e2fsck -D.");
 389 }
 390
 391 int ext4_dirblock_csum_verify(struct inode *inode, struct buffer_head *bh)
 392 {
 393         struct ext4_dir_entry_tail *t;
 394
 395         if (!ext4_has_metadata_csum(inode->i_sb))
 396                 return 1;
 397
 398         t = get_dirent_tail(inode, bh);
 399         if (!t) {
 400                 warn_no_space_for_csum(inode);
 401                 return 0;
 402         }
 403
 404         if (t->det_checksum != ext4_dirblock_csum(inode, bh->b_data,
 405                                                   (char *)t - bh->b_data))
 406                 return 0;
 407
 408         return 1;
 409 }
 410
 411 static void ext4_dirblock_csum_set(struct inode *inode,
 412                                  struct buffer_head *bh)
 413 {
 414         struct ext4_dir_entry_tail *t;
 415
 416         if (!ext4_has_metadata_csum(inode->i_sb))
 417                 return;
 418
 419         t = get_dirent_tail(inode, bh);
 420         if (!t) {
 421                 warn_no_space_for_csum(inode);
 422                 return;
 423         }
 424
 425         t->det_checksum = ext4_dirblock_csum(inode, bh->b_data,
 426                                              (char *)t - bh->b_data);
 427 }
 428
 429 int ext4_handle_dirty_dirblock(handle_t *handle,
 430                                struct inode *inode,
 431                                struct buffer_head *bh)
 432 {
 433         ext4_dirblock_csum_set(inode, bh);
 434         return ext4_handle_dirty_metadata(handle, inode, bh);
 435 }
 436
 437 static struct dx_countlimit *get_dx_countlimit(struct inode *inode,
 438                                                struct ext4_dir_entry *dirent,
 439                                                int *offset)
 440 {
 441         struct ext4_dir_entry *dp;
 442         struct dx_root_info *root;
 443         int count_offset;
 444
 445         if (le16_to_cpu(dirent->rec_len) == EXT4_BLOCK_SIZE(inode->i_sb))
 446                 count_offset = 8;
 447         else if (le16_to_cpu(dirent->rec_len) == 12) {
 448                 dp = (struct ext4_dir_entry *)(((void *)dirent) + 12);
 449                 if (le16_to_cpu(dp->rec_len) !=
 450                     EXT4_BLOCK_SIZE(inode->i_sb) - 12)
 451                         return NULL;
 452                 root = (struct dx_root_info *)(((void *)dp + 12));
 453                 if (root->reserved_zero ||
 454                     root->info_length != sizeof(struct dx_root_info))
 455                         return NULL;
 456                 count_offset = 32;
 457         } else
 458                 return NULL;
 459
 460         if (offset)
 461                 *offset = count_offset;
 462         return (struct dx_countlimit *)(((void *)dirent) + count_offset);
 463 }
 464
 465 static __le32 ext4_dx_csum(struct inode *inode, struct ext4_dir_entry *dirent,
 466                            int count_offset, int count, struct dx_tail *t)
 467 {
 468         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 469         struct ext4_inode_info *ei = EXT4_I(inode);
 470         __u32 csum;
 471         int size;
 472         __u32 dummy_csum = 0;
 473         int offset = offsetof(struct dx_tail, dt_checksum);
 474
 475         size = count_offset + (count * sizeof(struct dx_entry));
 476         csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)dirent, size);
 477         csum = ext4_chksum(sbi, csum, (__u8 *)t, offset);
 478         csum = ext4_chksum(sbi, csum, (__u8 *)&dummy_csum, sizeof(dummy_csum));
 479
 480         return cpu_to_le32(csum);
 481 }
 482
 483 static int ext4_dx_csum_verify(struct inode *inode,
 484                                struct ext4_dir_entry *dirent)
 485 {
 486         struct dx_countlimit *c;
 487         struct dx_tail *t;
 488         int count_offset, limit, count;
 489
 490         if (!ext4_has_metadata_csum(inode->i_sb))
 491                 return 1;
 492
 493         c = get_dx_countlimit(inode, dirent, &count_offset);
 494         if (!c) {
 495                 EXT4_ERROR_INODE(inode, "dir seems corrupt?  Run e2fsck -D.");
 496                 return 0;
 497         }
 498         limit = le16_to_cpu(c->limit);
 499         count = le16_to_cpu(c->count);
 500         if (count_offset + (limit * sizeof(struct dx_entry)) >
 501             EXT4_BLOCK_SIZE(inode->i_sb) - sizeof(struct dx_tail)) {
 502                 warn_no_space_for_csum(inode);
 503                 return 0;
 504         }
 505         t = (struct dx_tail *)(((struct dx_entry *)c) + limit);
 506
 507         if (t->dt_checksum != ext4_dx_csum(inode, dirent, count_offset,
 508                                             count, t))
 509                 return 0;
 510         return 1;
 511 }
 512
 513 static void ext4_dx_csum_set(struct inode *inode, struct ext4_dir_entry *dirent)
 514 {
 515         struct dx_countlimit *c;
 516         struct dx_tail *t;
 517         int count_offset, limit, count;
 518
 519         if (!ext4_has_metadata_csum(inode->i_sb))
 520                 return;
 521
 522         c = get_dx_countlimit(inode, dirent, &count_offset);
 523         if (!c) {
 524                 EXT4_ERROR_INODE(inode, "dir seems corrupt?  Run e2fsck -D.");
 525                 return;
 526         }
 527         limit = le16_to_cpu(c->limit);
 528         count = le16_to_cpu(c->count);
 529         if (count_offset + (limit * sizeof(struct dx_entry)) >
 530             EXT4_BLOCK_SIZE(inode->i_sb) - sizeof(struct dx_tail)) {
 531                 warn_no_space_for_csum(inode);
 532                 return;
 533         }
 534         t = (struct dx_tail *)(((struct dx_entry *)c) + limit);
 535
 536         t->dt_checksum = ext4_dx_csum(inode, dirent, count_offset, count, t);
 537 }
 538
 539 static inline int ext4_handle_dirty_dx_node(handle_t *handle,
 540                                             struct inode *inode,
 541                                             struct buffer_head *bh)
 542 {
 543         ext4_dx_csum_set(inode, (struct ext4_dir_entry *)bh->b_data);
 544         return ext4_handle_dirty_metadata(handle, inode, bh);
 545 }
 546
 547 /*
 548  * p is at least 6 bytes before the end of page
 549  */
 550 static inline struct ext4_dir_entry_2 *
 551 ext4_next_entry(struct ext4_dir_entry_2 *p, unsigned long blocksize)
 552 {
 553         return (struct ext4_dir_entry_2 *)((char *)p +
 554                 ext4_rec_len_from_disk(p->rec_len, blocksize));
 555 }
 556
 557 /*
 558  * Future: use high four bits of block for coalesce-on-delete flags
 559  * Mask them off for now.
 560  */
 561
 562 static inline ext4_lblk_t dx_get_block(struct dx_entry *entry)
 563 {
 564         return le32_to_cpu(entry->block) & 0x0fffffff;
 565 }
 566
 567 static inline void dx_set_block(struct dx_entry *entry, ext4_lblk_t value)
 568 {
 569         entry->block = cpu_to_le32(value);
 570 }
 571
 572 static inline unsigned dx_get_hash(struct dx_entry *entry)
 573 {
 574         return le32_to_cpu(entry->hash);
 575 }
 576
 577 static inline void dx_set_hash(struct dx_entry *entry, unsigned value)
 578 {
 579         entry->hash = cpu_to_le32(value);
 580 }
 581
 582 static inline unsigned dx_get_count(struct dx_entry *entries)
 583 {
 584         return le16_to_cpu(((struct dx_countlimit *) entries)->count);
 585 }
 586
 587 static inline unsigned dx_get_limit(struct dx_entry *entries)
 588 {
 589         return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
 590 }
 591
 592 static inline void dx_set_count(struct dx_entry *entries, unsigned value)
 593 {
 594         ((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
 595 }
 596
 597 static inline void dx_set_limit(struct dx_entry *entries, unsigned value)
 598 {
 599         ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
 600 }
 601
 602 static inline unsigned dx_root_limit(struct inode *dir, unsigned infosize)
 603 {
 604         unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(1) -
 605                 EXT4_DIR_REC_LEN(2) - infosize;
 606
 607         if (ext4_has_metadata_csum(dir->i_sb))
 608                 entry_space -= sizeof(struct dx_tail);
 609         return entry_space / sizeof(struct dx_entry);
 610 }
 611
 612 static inline unsigned dx_node_limit(struct inode *dir)
 613 {
 614         unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(0);
 615
 616         if (ext4_has_metadata_csum(dir->i_sb))
 617                 entry_space -= sizeof(struct dx_tail);
 618         return entry_space / sizeof(struct dx_entry);
 619 }
 620
 621 /*
 622  * Debug
 623  */
 624 #ifdef DX_DEBUG
 625 static void dx_show_index(char * label, struct dx_entry *entries)
 626 {
 627         int i, n = dx_get_count (entries);
 628         printk(KERN_DEBUG "%s index", label);
 629         for (i = 0; i < n; i++) {
 630                 printk(KERN_CONT " %x->%lu",
 631                        i ? dx_get_hash(entries + i) : 0,
 632                        (unsigned long)dx_get_block(entries + i));
 633         }
 634         printk(KERN_CONT "\n");
 635 }
 636
 637 struct stats
 638 {
 639         unsigned names;
 640         unsigned space;
 641         unsigned bcount;
 642 };
 643
 644 static struct stats dx_show_leaf(struct inode *dir,
 645                                 struct dx_hash_info *hinfo,
 646                                 struct ext4_dir_entry_2 *de,
 647                                 int size, int show_names)
 648 {
 649         unsigned names = 0, space = 0;
 650         char *base = (char *) de;
 651         struct dx_hash_info h = *hinfo;
 652
 653         printk("names: ");
 654         while ((char *) de < base + size)
 655         {
 656                 if (de->inode)
 657                 {
 658                         if (show_names)
 659                         {
 660 #ifdef CONFIG_FS_ENCRYPTION
 661                                 int len;
 662                                 char *name;
 663                                 struct fscrypt_str fname_crypto_str =
 664                                         FSTR_INIT(NULL, 0);
 665                                 int res = 0;
 666
 667                                 name  = de->name;
 668                                 len = de->name_len;
 669                                 if (IS_ENCRYPTED(dir))
 670                                         res = fscrypt_get_encryption_info(dir);
 671                                 if (res) {
 672                                         printk(KERN_WARNING "Error setting up"
 673                                                " fname crypto: %d\n", res);
 674                                 }
 675                                 if (!fscrypt_has_encryption_key(dir)) {
 676                                         /* Directory is not encrypted */
 677                                         ext4fs_dirhash(dir, de->name,
 678                                                 de->name_len, &h);
 679                                         printk("%*.s:(U)%x.%u ", len,
 680                                                name, h.hash,
 681                                                (unsigned) ((char *) de
 682                                                            - base));
 683                                 } else {
 684                                         struct fscrypt_str de_name =
 685                                                 FSTR_INIT(name, len);
 686
 687                                         /* Directory is encrypted */
 688                                         res = fscrypt_fname_alloc_buffer(
 689                                                 len, &fname_crypto_str);
 690                                         if (res)
 691                                                 printk(KERN_WARNING "Error "
 692                                                         "allocating crypto "
 693                                                         "buffer--skipping "
 694                                                         "crypto\n");
 695                                         res = fscrypt_fname_disk_to_usr(dir,
 696                                                 0, 0, &de_name,
 697                                                 &fname_crypto_str);
 698                                         if (res) {
 699                                                 printk(KERN_WARNING "Error "
 700                                                         "converting filename "
 701                                                         "from disk to usr"
 702                                                         "\n");
 703                                                 name = "??";
 704                                                 len = 2;
 705                                         } else {
 706                                                 name = fname_crypto_str.name;
 707                                                 len = fname_crypto_str.len;
 708                                         }
 709                                         ext4fs_dirhash(dir, de->name,
 710                                                        de->name_len, &h);
 711                                         printk("%*.s:(E)%x.%u ", len, name,
 712                                                h.hash, (unsigned) ((char *) de
 713                                                                    - base));
 714                                         fscrypt_fname_free_buffer(
 715                                                         &fname_crypto_str);
 716                                 }
 717 #else
 718                                 int len = de->name_len;
 719                                 char *name = de->name;
 720                                 ext4fs_dirhash(dir, de->name, de->name_len, &h);
 721                                 printk("%*.s:%x.%u ", len, name, h.hash,
 722                                        (unsigned) ((char *) de - base));
 723 #endif
 724                         }
 725                         space += EXT4_DIR_REC_LEN(de->name_len);
 726                         names++;
 727                 }
 728                 de = ext4_next_entry(de, size);
 729         }
 730         printk(KERN_CONT "(%i)\n", names);
 731         return (struct stats) { names, space, 1 };
 732 }
 733
 734 struct stats dx_show_entries(struct dx_hash_info *hinfo, struct inode *dir,
 735                              struct dx_entry *entries, int levels)
 736 {
 737         unsigned blocksize = dir->i_sb->s_blocksize;
 738         unsigned count = dx_get_count(entries), names = 0, space = 0, i;
 739         unsigned bcount = 0;
 740         struct buffer_head *bh;
 741         printk("%i indexed blocks...\n", count);
 742         for (i = 0; i < count; i++, entries++)
 743         {
 744                 ext4_lblk_t block = dx_get_block(entries);
 745                 ext4_lblk_t hash  = i ? dx_get_hash(entries): 0;
 746                 u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
 747                 struct stats stats;
 748                 printk("%s%3u:%03u hash %8x/%8x ",levels?"":"   ", i, block, hash, range);
 749                 bh = ext4_bread(NULL,dir, block, 0);
 750                 if (!bh || IS_ERR(bh))
 751                         continue;
 752                 stats = levels?
 753                    dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
 754                    dx_show_leaf(dir, hinfo, (struct ext4_dir_entry_2 *)
 755                         bh->b_data, blocksize, 0);
 756                 names += stats.names;
 757                 space += stats.space;
 758                 bcount += stats.bcount;
 759                 brelse(bh);
 760         }
 761         if (bcount)
 762                 printk(KERN_DEBUG "%snames %u, fullness %u (%u%%)\n",
 763                        levels ? "" : "   ", names, space/bcount,
 764                        (space/bcount)*100/blocksize);
 765         return (struct stats) { names, space, bcount};
 766 }
 767 #endif /* DX_DEBUG */
 768
 769 /*
 770  * Probe for a directory leaf block to search.
 771  *
 772  * dx_probe can return ERR_BAD_DX_DIR, which means there was a format
 773  * error in the directory index, and the caller should fall back to
 774  * searching the directory normally.  The callers of dx_probe **MUST**
 775  * check for this error code, and make sure it never gets reflected
 776  * back to userspace.
 777  */
 778 static struct dx_frame *
 779 dx_probe(struct ext4_filename *fname, struct inode *dir,
 780          struct dx_hash_info *hinfo, struct dx_frame *frame_in)
 781 {
 782         unsigned count, indirect, level, i;
 783         struct dx_entry *at, *entries, *p, *q, *m;
 784         struct dx_root *root;
 785         struct dx_frame *frame = frame_in;
 786         struct dx_frame *ret_err = ERR_PTR(ERR_BAD_DX_DIR);
 787         u32 hash;
 788         ext4_lblk_t block;
 789         ext4_lblk_t blocks[EXT4_HTREE_LEVEL];
 790
 791         memset(frame_in, 0, EXT4_HTREE_LEVEL * sizeof(frame_in[0]));
 792         frame->bh = ext4_read_dirblock(dir, 0, INDEX);
 793         if (IS_ERR(frame->bh))
 794                 return (struct dx_frame *) frame->bh;
 795
 796         root = (struct dx_root *) frame->bh->b_data;
 797         if (root->info.hash_version != DX_HASH_TEA &&
 798             root->info.hash_version != DX_HASH_HALF_MD4 &&
 799             root->info.hash_version != DX_HASH_LEGACY) {
 800                 ext4_warning_inode(dir, "Unrecognised inode hash code %u",
 801                                    root->info.hash_version);
 802                 goto fail;
 803         }
 804         if (fname)
 805                 hinfo = &fname->hinfo;
 806         hinfo->hash_version = root->info.hash_version;
 807         if (hinfo->hash_version <= DX_HASH_TEA)
 808                 hinfo->hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
 809         hinfo->seed = EXT4_SB(dir->i_sb)->s_hash_seed;
 810         if (fname && fname_name(fname))
 811                 ext4fs_dirhash(dir, fname_name(fname), fname_len(fname), hinfo);
 812         hash = hinfo->hash;
 813
 814         if (root->info.unused_flags & 1) {
 815                 ext4_warning_inode(dir, "Unimplemented hash flags: %#06x",
 816                                    root->info.unused_flags);
 817                 goto fail;
 818         }
 819
 820         indirect = root->info.indirect_levels;
 821         if (indirect >= ext4_dir_htree_level(dir->i_sb)) {
 822                 ext4_warning(dir->i_sb,
 823                              "Directory (ino: %lu) htree depth %#06x exceed"
 824                              "supported value", dir->i_ino,
 825                              ext4_dir_htree_level(dir->i_sb));
 826                 if (ext4_dir_htree_level(dir->i_sb) < EXT4_HTREE_LEVEL) {
 827                         ext4_warning(dir->i_sb, "Enable large directory "
 828                                                 "feature to access it");
 829                 }
 830                 goto fail;
 831         }
 832
 833         entries = (struct dx_entry *)(((char *)&root->info) +
 834                                       root->info.info_length);
 835
 836         if (dx_get_limit(entries) != dx_root_limit(dir,
 837                                                    root->info.info_length)) {
 838                 ext4_warning_inode(dir, "dx entry: limit %u != root limit %u",
 839                                    dx_get_limit(entries),
 840                                    dx_root_limit(dir, root->info.info_length));
 841                 goto fail;
 842         }
 843
 844         dxtrace(printk("Look up %x", hash));
 845         level = 0;
 846         blocks[0] = 0;
 847         while (1) {
 848                 count = dx_get_count(entries);
 849                 if (!count || count > dx_get_limit(entries)) {
 850                         ext4_warning_inode(dir,
 851                                            "dx entry: count %u beyond limit %u",
 852                                            count, dx_get_limit(entries));
 853                         goto fail;
 854                 }
 855
 856                 p = entries + 1;
 857                 q = entries + count - 1;
 858                 while (p <= q) {
 859                         m = p + (q - p) / 2;
 860                         dxtrace(printk(KERN_CONT "."));
 861                         if (dx_get_hash(m) > hash)
 862                                 q = m - 1;
 863                         else
 864                                 p = m + 1;
 865                 }
 866
 867                 if (0) { // linear search cross check
 868                         unsigned n = count - 1;
 869                         at = entries;
 870                         while (n--)
 871                         {
 872                                 dxtrace(printk(KERN_CONT ","));
 873                                 if (dx_get_hash(++at) > hash)
 874                                 {
 875                                         at--;
 876                                         break;
 877                                 }
 878                         }
 879                         assert (at == p - 1);
 880                 }
 881
 882                 at = p - 1;
 883                 dxtrace(printk(KERN_CONT " %x->%u\n",
 884                                at == entries ? 0 : dx_get_hash(at),
 885                                dx_get_block(at)));
 886                 frame->entries = entries;
 887                 frame->at = at;
 888
 889                 block = dx_get_block(at);
 890                 for (i = 0; i <= level; i++) {
 891                         if (blocks[i] == block) {
 892                                 ext4_warning_inode(dir,
 893                                         "dx entry: tree cycle block %u points back to block %u",
 894                                         blocks[level], block);
 895                                 goto fail;
 896                         }
 897                 }
 898                 if (++level > indirect)
 899                         return frame;
 900                 blocks[level] = block;
 901                 frame++;
 902                 frame->bh = ext4_read_dirblock(dir, block, INDEX);
 903                 if (IS_ERR(frame->bh)) {
 904                         ret_err = (struct dx_frame *) frame->bh;
 905                         frame->bh = NULL;
 906                         goto fail;
 907                 }
 908
 909                 entries = ((struct dx_node *) frame->bh->b_data)->entries;
 910
 911                 if (dx_get_limit(entries) != dx_node_limit(dir)) {
 912                         ext4_warning_inode(dir,
 913                                 "dx entry: limit %u != node limit %u",
 914                                 dx_get_limit(entries), dx_node_limit(dir));
 915                         goto fail;
 916                 }
 917         }
 918 fail:
 919         while (frame >= frame_in) {
 920                 brelse(frame->bh);
 921                 frame--;
 922         }
 923
 924         if (ret_err == ERR_PTR(ERR_BAD_DX_DIR))
 925                 ext4_warning_inode(dir,
 926                         "Corrupt directory, running e2fsck is recommended");
 927         return ret_err;
 928 }
 929
 930 static void dx_release(struct dx_frame *frames)
 931 {
 932         struct dx_root_info *info;
 933         int i;
 934         unsigned int indirect_levels;
 935
 936         if (frames[0].bh == NULL)
 937                 return;
 938
 939         info = &((struct dx_root *)frames[0].bh->b_data)->info;
 940         /* save local copy, "info" may be freed after brelse() */
 941         indirect_levels = info->indirect_levels;
 942         for (i = 0; i <= indirect_levels; i++) {
 943                 if (frames[i].bh == NULL)
 944                         break;
 945                 brelse(frames[i].bh);
 946                 frames[i].bh = NULL;
 947         }
 948 }
 949
 950 /*
 951  * This function increments the frame pointer to search the next leaf
 952  * block, and reads in the necessary intervening nodes if the search
 953  * should be necessary.  Whether or not the search is necessary is
 954  * controlled by the hash parameter.  If the hash value is even, then
 955  * the search is only continued if the next block starts with that
 956  * hash value.  This is used if we are searching for a specific file.
 957  *
 958  * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
 959  *
 960  * This function returns 1 if the caller should continue to search,
 961  * or 0 if it should not.  If there is an error reading one of the
 962  * index blocks, it will a negative error code.
 963  *
 964  * If start_hash is non-null, it will be filled in with the starting
 965  * hash of the next page.
 966  */
 967 static int ext4_htree_next_block(struct inode *dir, __u32 hash,
 968                                  struct dx_frame *frame,
 969                                  struct dx_frame *frames,
 970                                  __u32 *start_hash)
 971 {
 972         struct dx_frame *p;
 973         struct buffer_head *bh;
 974         int num_frames = 0;
 975         __u32 bhash;
 976
 977         p = frame;
 978         /*
 979          * Find the next leaf page by incrementing the frame pointer.
 980          * If we run out of entries in the interior node, loop around and
 981          * increment pointer in the parent node.  When we break out of
 982          * this loop, num_frames indicates the number of interior
 983          * nodes need to be read.
 984          */
 985         while (1) {
 986                 if (++(p->at) < p->entries + dx_get_count(p->entries))
 987                         break;
 988                 if (p == frames)
 989                         return 0;
 990                 num_frames++;
 991                 p--;
 992         }
 993
 994         /*
 995          * If the hash is 1, then continue only if the next page has a
 996          * continuation hash of any value.  This is used for readdir
 997          * handling.  Otherwise, check to see if the hash matches the
 998          * desired contiuation hash.  If it doesn't, return since
 999          * there's no point to read in the successive index pages.
1000          */
1001         bhash = dx_get_hash(p->at);
1002         if (start_hash)
1003                 *start_hash = bhash;
1004         if ((hash & 1) == 0) {
1005                 if ((bhash & ~1) != hash)
1006                         return 0;
1007         }
1008         /*
1009          * If the hash is HASH_NB_ALWAYS, we always go to the next
1010          * block so no check is necessary
1011          */
1012         while (num_frames--) {
1013                 bh = ext4_read_dirblock(dir, dx_get_block(p->at), INDEX);
1014                 if (IS_ERR(bh))
1015                         return PTR_ERR(bh);
1016                 p++;
1017                 brelse(p->bh);
1018                 p->bh = bh;
1019                 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
1020         }
1021         return 1;
1022 }
1023
1024
1025 /*
1026  * This function fills a red-black tree with information from a
1027  * directory block.  It returns the number directory entries loaded
1028  * into the tree.  If there is an error it is returned in err.
1029  */
1030 static int htree_dirblock_to_tree(struct file *dir_file,
1031                                   struct inode *dir, ext4_lblk_t block,
1032                                   struct dx_hash_info *hinfo,
1033                                   __u32 start_hash, __u32 start_minor_hash)
1034 {
1035         struct buffer_head *bh;
1036         struct ext4_dir_entry_2 *de, *top;
1037         int err = 0, count = 0;
1038         struct fscrypt_str fname_crypto_str = FSTR_INIT(NULL, 0), tmp_str;
1039
1040         dxtrace(printk(KERN_INFO "In htree dirblock_to_tree: block %lu\n",
1041                                                         (unsigned long)block));
1042         bh = ext4_read_dirblock(dir, block, DIRENT_HTREE);
1043         if (IS_ERR(bh))
1044                 return PTR_ERR(bh);
1045
1046         de = (struct ext4_dir_entry_2 *) bh->b_data;
1047         top = (struct ext4_dir_entry_2 *) ((char *) de +
1048                                            dir->i_sb->s_blocksize -
1049                                            EXT4_DIR_REC_LEN(0));
1050         /* Check if the directory is encrypted */
1051         if (IS_ENCRYPTED(dir)) {
1052                 err = fscrypt_get_encryption_info(dir);
1053                 if (err < 0) {
1054                         brelse(bh);
1055                         return err;
1056                 }
1057                 err = fscrypt_fname_alloc_buffer(EXT4_NAME_LEN,
1058                                                  &fname_crypto_str);
1059                 if (err < 0) {
1060                         brelse(bh);
1061                         return err;
1062                 }
1063         }
1064
1065         for (; de < top; de = ext4_next_entry(de, dir->i_sb->s_blocksize)) {
1066                 if (ext4_check_dir_entry(dir, NULL, de, bh,
1067                                 bh->b_data, bh->b_size,
1068                                 (block<<EXT4_BLOCK_SIZE_BITS(dir->i_sb))
1069                                          + ((char *)de - bh->b_data))) {
1070                         /* silently ignore the rest of the block */
1071                         break;
1072                 }
1073                 ext4fs_dirhash(dir, de->name, de->name_len, hinfo);
1074                 if ((hinfo->hash < start_hash) ||
1075                     ((hinfo->hash == start_hash) &&
1076                      (hinfo->minor_hash < start_minor_hash)))
1077                         continue;
1078                 if (de->inode == 0)
1079                         continue;
1080                 if (!IS_ENCRYPTED(dir)) {
1081                         tmp_str.name = de->name;
1082                         tmp_str.len = de->name_len;
1083                         err = ext4_htree_store_dirent(dir_file,
1084                                    hinfo->hash, hinfo->minor_hash, de,
1085                                    &tmp_str);
1086                 } else {
1087                         int save_len = fname_crypto_str.len;
1088                         struct fscrypt_str de_name = FSTR_INIT(de->name,
1089                                                                 de->name_len);
1090
1091                         /* Directory is encrypted */
1092                         err = fscrypt_fname_disk_to_usr(dir, hinfo->hash,
1093                                         hinfo->minor_hash, &de_name,
1094                                         &fname_crypto_str);
1095                         if (err) {
1096                                 count = err;
1097                                 goto errout;
1098                         }
1099                         err = ext4_htree_store_dirent(dir_file,
1100                                    hinfo->hash, hinfo->minor_hash, de,
1101                                         &fname_crypto_str);
1102                         fname_crypto_str.len = save_len;
1103                 }
1104                 if (err != 0) {
1105                         count = err;
1106                         goto errout;
1107                 }
1108                 count++;
1109         }
1110 errout:
1111         brelse(bh);
1112         fscrypt_fname_free_buffer(&fname_crypto_str);
1113         return count;
1114 }
1115
1116
1117 /*
1118  * This function fills a red-black tree with information from a
1119  * directory.  We start scanning the directory in hash order, starting
1120  * at start_hash and start_minor_hash.
1121  *
1122  * This function returns the number of entries inserted into the tree,
1123  * or a negative error code.
1124  */
1125 int ext4_htree_fill_tree(struct file *dir_file, __u32 start_hash,
1126                          __u32 start_minor_hash, __u32 *next_hash)
1127 {
1128         struct dx_hash_info hinfo;
1129         struct ext4_dir_entry_2 *de;
1130         struct dx_frame frames[EXT4_HTREE_LEVEL], *frame;
1131         struct inode *dir;
1132         ext4_lblk_t block;
1133         int count = 0;
1134         int ret, err;
1135         __u32 hashval;
1136         struct fscrypt_str tmp_str;
1137
1138         dxtrace(printk(KERN_DEBUG "In htree_fill_tree, start hash: %x:%x\n",
1139                        start_hash, start_minor_hash));
1140         dir = file_inode(dir_file);
1141         if (!(ext4_test_inode_flag(dir, EXT4_INODE_INDEX))) {
1142                 hinfo.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
1143                 if (hinfo.hash_version <= DX_HASH_TEA)
1144                         hinfo.hash_version +=
1145                                 EXT4_SB(dir->i_sb)->s_hash_unsigned;
1146                 hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
1147                 if (ext4_has_inline_data(dir)) {
1148                         int has_inline_data = 1;
1149                         count = ext4_inlinedir_to_tree(dir_file, dir, 0,
1150                                                        &hinfo, start_hash,
1151                                                        start_minor_hash,
1152                                                        &has_inline_data);
1153                         if (has_inline_data) {
1154                                 *next_hash = ~0;
1155                                 return count;
1156                         }
1157                 }
1158                 count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
1159                                                start_hash, start_minor_hash);
1160                 *next_hash = ~0;
1161                 return count;
1162         }
1163         hinfo.hash = start_hash;
1164         hinfo.minor_hash = 0;
1165         frame = dx_probe(NULL, dir, &hinfo, frames);
1166         if (IS_ERR(frame))
1167                 return PTR_ERR(frame);
1168
1169         /* Add '.' and '..' from the htree header */
1170         if (!start_hash && !start_minor_hash) {
1171                 de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
1172                 tmp_str.name = de->name;
1173                 tmp_str.len = de->name_len;
1174                 err = ext4_htree_store_dirent(dir_file, 0, 0,
1175                                               de, &tmp_str);
1176                 if (err != 0)
1177                         goto errout;
1178                 count++;
1179         }
1180         if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
1181                 de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
1182                 de = ext4_next_entry(de, dir->i_sb->s_blocksize);
1183                 tmp_str.name = de->name;
1184                 tmp_str.len = de->name_len;
1185                 err = ext4_htree_store_dirent(dir_file, 2, 0,
1186                                               de, &tmp_str);
1187                 if (err != 0)
1188                         goto errout;
1189                 count++;
1190         }
1191
1192         while (1) {
1193                 if (fatal_signal_pending(current)) {
1194                         err = -ERESTARTSYS;
1195                         goto errout;
1196                 }
1197                 cond_resched();
1198                 block = dx_get_block(frame->at);
1199                 ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo,
1200                                              start_hash, start_minor_hash);
1201                 if (ret < 0) {
1202                         err = ret;
1203                         goto errout;
1204                 }
1205                 count += ret;
1206                 hashval = ~0;
1207                 ret = ext4_htree_next_block(dir, HASH_NB_ALWAYS,
1208                                             frame, frames, &hashval);
1209                 *next_hash = hashval;
1210                 if (ret < 0) {
1211                         err = ret;
1212                         goto errout;
1213                 }
1214                 /*
1215                  * Stop if:  (a) there are no more entries, or
1216                  * (b) we have inserted at least one entry and the
1217                  * next hash value is not a continuation
1218                  */
1219                 if ((ret == 0) ||
1220                     (count && ((hashval & 1) == 0)))
1221                         break;
1222         }
1223         dx_release(frames);
1224         dxtrace(printk(KERN_DEBUG "Fill tree: returned %d entries, "
1225                        "next hash: %x\n", count, *next_hash));
1226         return count;
1227 errout:
1228         dx_release(frames);
1229         return (err);
1230 }
1231
1232 static inline int search_dirblock(struct buffer_head *bh,
1233                                   struct inode *dir,
1234                                   struct ext4_filename *fname,
1235                                   unsigned int offset,
1236                                   struct ext4_dir_entry_2 **res_dir)
1237 {
1238         return ext4_search_dir(bh, bh->b_data, dir->i_sb->s_blocksize, dir,
1239                                fname, offset, res_dir);
1240 }
1241
1242 /*
1243  * Directory block splitting, compacting
1244  */
1245
1246 /*
1247  * Create map of hash values, offsets, and sizes, stored at end of block.
1248  * Returns number of entries mapped.
1249  */
1250 static int dx_make_map(struct inode *dir, struct buffer_head *bh,
1251                        struct dx_hash_info *hinfo,
1252                        struct dx_map_entry *map_tail)
1253 {
1254         int count = 0;
1255         struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)bh->b_data;
1256         unsigned int buflen = bh->b_size;
1257         char *base = bh->b_data;
1258         struct dx_hash_info h = *hinfo;
1259
1260         if (ext4_has_metadata_csum(dir->i_sb))
1261                 buflen -= sizeof(struct ext4_dir_entry_tail);
1262
1263         while ((char *) de < base + buflen) {
1264                 if (ext4_check_dir_entry(dir, NULL, de, bh, base, buflen,
1265                                          ((char *)de) - base))
1266                         return -EFSCORRUPTED;
1267                 if (de->name_len && de->inode) {
1268                         ext4fs_dirhash(dir, de->name, de->name_len, &h);
1269                         map_tail--;
1270                         map_tail->hash = h.hash;
1271                         map_tail->offs = ((char *) de - base)>>2;
1272                         map_tail->size = le16_to_cpu(de->rec_len);
1273                         count++;
1274                         cond_resched();
1275                 }
1276                 de = ext4_next_entry(de, dir->i_sb->s_blocksize);
1277         }
1278         return count;
1279 }
1280
1281 /* Sort map by hash value */
1282 static void dx_sort_map (struct dx_map_entry *map, unsigned count)
1283 {
1284         struct dx_map_entry *p, *q, *top = map + count - 1;
1285         int more;
1286         /* Combsort until bubble sort doesn't suck */
1287         while (count > 2) {
1288                 count = count*10/13;
1289                 if (count - 9 < 2) /* 9, 10 -> 11 */
1290                         count = 11;
1291                 for (p = top, q = p - count; q >= map; p--, q--)
1292                         if (p->hash < q->hash)
1293                                 swap(*p, *q);
1294         }
1295         /* Garden variety bubble sort */
1296         do {
1297                 more = 0;
1298                 q = top;
1299                 while (q-- > map) {
1300                         if (q[1].hash >= q[0].hash)
1301                                 continue;
1302                         swap(*(q+1), *q);
1303                         more = 1;
1304                 }
1305         } while(more);
1306 }
1307
1308 static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
1309 {
1310         struct dx_entry *entries = frame->entries;
1311         struct dx_entry *old = frame->at, *new = old + 1;
1312         int count = dx_get_count(entries);
1313
1314         assert(count < dx_get_limit(entries));
1315         assert(old < entries + count);
1316         memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
1317         dx_set_hash(new, hash);
1318         dx_set_block(new, block);
1319         dx_set_count(entries, count + 1);
1320 }
1321
1322 #ifdef CONFIG_UNICODE
1323 /*
1324  * Test whether a case-insensitive directory entry matches the filename
1325  * being searched for.  If quick is set, assume the name being looked up
1326  * is already in the casefolded form.
1327  *
1328  * Returns: 0 if the directory entry matches, more than 0 if it
1329  * doesn't match or less than zero on error.
1330  */
1331 int ext4_ci_compare(const struct inode *parent, const struct qstr *name,
1332                     const struct qstr *entry, bool quick)
1333 {
1334         const struct super_block *sb = parent->i_sb;
1335         const struct unicode_map *um = sb->s_encoding;
1336         int ret;
1337
1338         if (quick)
1339                 ret = utf8_strncasecmp_folded(um, name, entry);
1340         else
1341                 ret = utf8_strncasecmp(um, name, entry);
1342
1343         if (ret < 0) {
1344                 /* Handle invalid character sequence as either an error
1345                  * or as an opaque byte sequence.
1346                  */
1347                 if (sb_has_strict_encoding(sb))
1348                         return -EINVAL;
1349
1350                 if (name->len != entry->len)
1351                         return 1;
1352
1353                 return !!memcmp(name->name, entry->name, name->len);
1354         }
1355
1356         return ret;
1357 }
1358
1359 void ext4_fname_setup_ci_filename(struct inode *dir, const struct qstr *iname,
1360                                   struct fscrypt_str *cf_name)
1361 {
1362         int len;
1363
1364         if (!IS_CASEFOLDED(dir) || !dir->i_sb->s_encoding) {
1365                 cf_name->name = NULL;
1366                 return;
1367         }
1368
1369         cf_name->name = kmalloc(EXT4_NAME_LEN, GFP_NOFS);
1370         if (!cf_name->name)
1371                 return;
1372
1373         len = utf8_casefold(dir->i_sb->s_encoding,
1374                             iname, cf_name->name,
1375                             EXT4_NAME_LEN);
1376         if (len <= 0) {
1377                 kfree(cf_name->name);
1378                 cf_name->name = NULL;
1379                 return;
1380         }
1381         cf_name->len = (unsigned) len;
1382
1383 }
1384 #endif
1385
1386 /*
1387  * Test whether a directory entry matches the filename being searched for.
1388  *
1389  * Return: %true if the directory entry matches, otherwise %false.
1390  */
1391 static inline bool ext4_match(const struct inode *parent,
1392                               const struct ext4_filename *fname,
1393                               const struct ext4_dir_entry_2 *de)
1394 {
1395         struct fscrypt_name f;
1396 #ifdef CONFIG_UNICODE
1397         const struct qstr entry = {.name = de->name, .len = de->name_len};
1398 #endif
1399
1400         if (!de->inode)
1401                 return false;
1402
1403         f.usr_fname = fname->usr_fname;
1404         f.disk_name = fname->disk_name;
1405 #ifdef CONFIG_FS_ENCRYPTION
1406         f.crypto_buf = fname->crypto_buf;
1407 #endif
1408
1409 #ifdef CONFIG_UNICODE
1410         if (parent->i_sb->s_encoding && IS_CASEFOLDED(parent)) {
1411                 if (fname->cf_name.name) {
1412                         struct qstr cf = {.name = fname->cf_name.name,
1413                                           .len = fname->cf_name.len};
1414                         return !ext4_ci_compare(parent, &cf, &entry, true);
1415                 }
1416                 return !ext4_ci_compare(parent, fname->usr_fname, &entry,
1417                                         false);
1418         }
1419 #endif
1420
1421         return fscrypt_match_name(&f, de->name, de->name_len);
1422 }
1423
1424 /*
1425  * Returns 0 if not found, -1 on failure, and 1 on success
1426  */
1427 int ext4_search_dir(struct buffer_head *bh, char *search_buf, int buf_size,
1428                     struct inode *dir, struct ext4_filename *fname,
1429                     unsigned int offset, struct ext4_dir_entry_2 **res_dir)
1430 {
1431         struct ext4_dir_entry_2 * de;
1432         char * dlimit;
1433         int de_len;
1434
1435         de = (struct ext4_dir_entry_2 *)search_buf;
1436         dlimit = search_buf + buf_size;
1437         while ((char *) de < dlimit - EXT4_BASE_DIR_LEN) {
1438                 /* this code is executed quadratically often */
1439                 /* do minimal checking `by hand' */
1440                 if (de->name + de->name_len <= dlimit &&
1441                     ext4_match(dir, fname, de)) {
1442                         /* found a match - just to be sure, do
1443                          * a full check */
1444                         if (ext4_check_dir_entry(dir, NULL, de, bh, search_buf,
1445                                                  buf_size, offset))
1446                                 return -1;
1447                         *res_dir = de;
1448                         return 1;
1449                 }
1450                 /* prevent looping on a bad block */
1451                 de_len = ext4_rec_len_from_disk(de->rec_len,
1452                                                 dir->i_sb->s_blocksize);
1453                 if (de_len <= 0)
1454                         return -1;
1455                 offset += de_len;
1456                 de = (struct ext4_dir_entry_2 *) ((char *) de + de_len);
1457         }
1458         return 0;
1459 }
1460
1461 static int is_dx_internal_node(struct inode *dir, ext4_lblk_t block,
1462                                struct ext4_dir_entry *de)
1463 {
1464         struct super_block *sb = dir->i_sb;
1465
1466         if (!is_dx(dir))
1467                 return 0;
1468         if (block == 0)
1469                 return 1;
1470         if (de->inode == 0 &&
1471             ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize) ==
1472                         sb->s_blocksize)
1473                 return 1;
1474         return 0;
1475 }
1476
1477 /*
1478  *      __ext4_find_entry()
1479  *
1480  * finds an entry in the specified directory with the wanted name. It
1481  * returns the cache buffer in which the entry was found, and the entry
1482  * itself (as a parameter - res_dir). It does NOT read the inode of the
1483  * entry - you'll have to do that yourself if you want to.
1484  *
1485  * The returned buffer_head has ->b_count elevated.  The caller is expected
1486  * to brelse() it when appropriate.
1487  */
1488 static struct buffer_head *__ext4_find_entry(struct inode *dir,
1489                                              struct ext4_filename *fname,
1490                                              struct ext4_dir_entry_2 **res_dir,
1491                                              int *inlined)
1492 {
1493         struct super_block *sb;
1494         struct buffer_head *bh_use[NAMEI_RA_SIZE];
1495         struct buffer_head *bh, *ret = NULL;
1496         ext4_lblk_t start, block;
1497         const u8 *name = fname->usr_fname->name;
1498         size_t ra_max = 0;      /* Number of bh's in the readahead
1499                                    buffer, bh_use[] */
1500         size_t ra_ptr = 0;      /* Current index into readahead
1501                                    buffer */
1502         ext4_lblk_t  nblocks;
1503         int i, namelen, retval;
1504
1505         *res_dir = NULL;
1506         sb = dir->i_sb;
1507         namelen = fname->usr_fname->len;
1508         if (namelen > EXT4_NAME_LEN)
1509                 return NULL;
1510
1511         if (ext4_has_inline_data(dir)) {
1512                 int has_inline_data = 1;
1513                 ret = ext4_find_inline_entry(dir, fname, res_dir,
1514                                              &has_inline_data);
1515                 if (has_inline_data) {
1516                         if (inlined)
1517                                 *inlined = 1;
1518                         goto cleanup_and_exit;
1519                 }
1520         }
1521
1522         if ((namelen <= 2) && (name[0] == '.') &&
1523             (name[1] == '.' || name[1] == '\0')) {
1524                 /*
1525                  * "." or ".." will only be in the first block
1526                  * NFS may look up ".."; "." should be handled by the VFS
1527                  */
1528                 block = start = 0;
1529                 nblocks = 1;
1530                 goto restart;
1531         }
1532         if (is_dx(dir)) {
1533                 ret = ext4_dx_find_entry(dir, fname, res_dir);
1534                 /*
1535                  * On success, or if the error was file not found,
1536                  * return.  Otherwise, fall back to doing a search the
1537                  * old fashioned way.
1538                  */
1539                 if (!IS_ERR(ret) || PTR_ERR(ret) != ERR_BAD_DX_DIR)
1540                         goto cleanup_and_exit;
1541                 dxtrace(printk(KERN_DEBUG "ext4_find_entry: dx failed, "
1542                                "falling back\n"));
1543                 ret = NULL;
1544         }
1545         nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
1546         if (!nblocks) {
1547                 ret = NULL;
1548                 goto cleanup_and_exit;
1549         }
1550         start = EXT4_I(dir)->i_dir_start_lookup;
1551         if (start >= nblocks)
1552                 start = 0;
1553         block = start;
1554 restart:
1555         do {
1556                 /*
1557                  * We deal with the read-ahead logic here.
1558                  */
1559                 cond_resched();
1560                 if (ra_ptr >= ra_max) {
1561                         /* Refill the readahead buffer */
1562                         ra_ptr = 0;
1563                         if (block < start)
1564                                 ra_max = start - block;
1565                         else
1566                                 ra_max = nblocks - block;
1567                         ra_max = min(ra_max, ARRAY_SIZE(bh_use));
1568                         retval = ext4_bread_batch(dir, block, ra_max,
1569                                                   false /* wait */, bh_use);
1570                         if (retval) {
1571                                 ret = ERR_PTR(retval);
1572                                 ra_max = 0;
1573                                 goto cleanup_and_exit;
1574                         }
1575                 }
1576                 if ((bh = bh_use[ra_ptr++]) == NULL)
1577                         goto next;
1578                 wait_on_buffer(bh);
1579                 if (!buffer_uptodate(bh)) {
1580                         EXT4_ERROR_INODE_ERR(dir, EIO,
1581                                              "reading directory lblock %lu",
1582                                              (unsigned long) block);
1583                         brelse(bh);
1584                         ret = ERR_PTR(-EIO);
1585                         goto cleanup_and_exit;
1586                 }
1587                 if (!buffer_verified(bh) &&
1588                     !is_dx_internal_node(dir, block,
1589                                          (struct ext4_dir_entry *)bh->b_data) &&
1590                     !ext4_dirblock_csum_verify(dir, bh)) {
1591                         EXT4_ERROR_INODE_ERR(dir, EFSBADCRC,
1592                                              "checksumming directory "
1593                                              "block %lu", (unsigned long)block);
1594                         brelse(bh);
1595                         ret = ERR_PTR(-EFSBADCRC);
1596                         goto cleanup_and_exit;
1597                 }
1598                 set_buffer_verified(bh);
1599                 i = search_dirblock(bh, dir, fname,
1600                             block << EXT4_BLOCK_SIZE_BITS(sb), res_dir);
1601                 if (i == 1) {
1602                         EXT4_I(dir)->i_dir_start_lookup = block;
1603                         ret = bh;
1604                         goto cleanup_and_exit;
1605                 } else {
1606                         brelse(bh);
1607                         if (i < 0)
1608                                 goto cleanup_and_exit;
1609                 }
1610         next:
1611                 if (++block >= nblocks)
1612                         block = 0;
1613         } while (block != start);
1614
1615         /*
1616          * If the directory has grown while we were searching, then
1617          * search the last part of the directory before giving up.
1618          */
1619         block = nblocks;
1620         nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
1621         if (block < nblocks) {
1622                 start = 0;
1623                 goto restart;
1624         }
1625
1626 cleanup_and_exit:
1627         /* Clean up the read-ahead blocks */
1628         for (; ra_ptr < ra_max; ra_ptr++)
1629                 brelse(bh_use[ra_ptr]);
1630         return ret;
1631 }
1632
1633 static struct buffer_head *ext4_find_entry(struct inode *dir,
1634                                            const struct qstr *d_name,
1635                                            struct ext4_dir_entry_2 **res_dir,
1636                                            int *inlined)
1637 {
1638         int err;
1639         struct ext4_filename fname;
1640         struct buffer_head *bh;
1641
1642         err = ext4_fname_setup_filename(dir, d_name, 1, &fname);
1643         if (err == -ENOENT)
1644                 return NULL;
1645         if (err)
1646                 return ERR_PTR(err);
1647
1648         bh = __ext4_find_entry(dir, &fname, res_dir, inlined);
1649
1650         ext4_fname_free_filename(&fname);
1651         return bh;
1652 }
1653
1654 static struct buffer_head *ext4_lookup_entry(struct inode *dir,
1655                                              struct dentry *dentry,
1656                                              struct ext4_dir_entry_2 **res_dir)
1657 {
1658         int err;
1659         struct ext4_filename fname;
1660         struct buffer_head *bh;
1661
1662         err = ext4_fname_prepare_lookup(dir, dentry, &fname);
1663         if (err == -ENOENT)
1664                 return NULL;
1665         if (err)
1666                 return ERR_PTR(err);
1667
1668         bh = __ext4_find_entry(dir, &fname, res_dir, NULL);
1669
1670         ext4_fname_free_filename(&fname);
1671         return bh;
1672 }
1673
1674 static struct buffer_head * ext4_dx_find_entry(struct inode *dir,
1675                         struct ext4_filename *fname,
1676                         struct ext4_dir_entry_2 **res_dir)
1677 {
1678         struct super_block * sb = dir->i_sb;
1679         struct dx_frame frames[EXT4_HTREE_LEVEL], *frame;
1680         struct buffer_head *bh;
1681         ext4_lblk_t block;
1682         int retval;
1683
1684 #ifdef CONFIG_FS_ENCRYPTION
1685         *res_dir = NULL;
1686 #endif
1687         frame = dx_probe(fname, dir, NULL, frames);
1688         if (IS_ERR(frame))
1689                 return (struct buffer_head *) frame;
1690         do {
1691                 block = dx_get_block(frame->at);
1692                 bh = ext4_read_dirblock(dir, block, DIRENT_HTREE);
1693                 if (IS_ERR(bh))
1694                         goto errout;
1695
1696                 retval = search_dirblock(bh, dir, fname,
1697                                          block << EXT4_BLOCK_SIZE_BITS(sb),
1698                                          res_dir);
1699                 if (retval == 1)
1700                         goto success;
1701                 brelse(bh);
1702                 if (retval == -1) {
1703                         bh = ERR_PTR(ERR_BAD_DX_DIR);
1704                         goto errout;
1705                 }
1706
1707                 /* Check to see if we should continue to search */
1708                 retval = ext4_htree_next_block(dir, fname->hinfo.hash, frame,
1709                                                frames, NULL);
1710                 if (retval < 0) {
1711                         ext4_warning_inode(dir,
1712                                 "error %d reading directory index block",
1713                                 retval);
1714                         bh = ERR_PTR(retval);
1715                         goto errout;
1716                 }
1717         } while (retval == 1);
1718
1719         bh = NULL;
1720 errout:
1721         dxtrace(printk(KERN_DEBUG "%s not found\n", fname->usr_fname->name));
1722 success:
1723         dx_release(frames);
1724         return bh;
1725 }
1726
1727 static struct dentry *ext4_lookup(struct inode *dir, struct dentry *dentry, unsigned int flags)
1728 {
1729         struct inode *inode;
1730         struct ext4_dir_entry_2 *de;
1731         struct buffer_head *bh;
1732
1733         if (dentry->d_name.len > EXT4_NAME_LEN)
1734                 return ERR_PTR(-ENAMETOOLONG);
1735
1736         bh = ext4_lookup_entry(dir, dentry, &de);
1737         if (IS_ERR(bh))
1738                 return ERR_CAST(bh);
1739         inode = NULL;
1740         if (bh) {
1741                 __u32 ino = le32_to_cpu(de->inode);
1742                 brelse(bh);
1743                 if (!ext4_valid_inum(dir->i_sb, ino)) {
1744                         EXT4_ERROR_INODE(dir, "bad inode number: %u", ino);
1745                         return ERR_PTR(-EFSCORRUPTED);
1746                 }
1747                 if (unlikely(ino == dir->i_ino)) {
1748                         EXT4_ERROR_INODE(dir, "'%pd' linked to parent dir",
1749                                          dentry);
1750                         return ERR_PTR(-EFSCORRUPTED);
1751                 }
1752                 inode = ext4_iget(dir->i_sb, ino, EXT4_IGET_NORMAL);
1753                 if (inode == ERR_PTR(-ESTALE)) {
1754                         EXT4_ERROR_INODE(dir,
1755                                          "deleted inode referenced: %u",
1756                                          ino);
1757                         return ERR_PTR(-EFSCORRUPTED);
1758                 }
1759                 if (!IS_ERR(inode) && IS_ENCRYPTED(dir) &&
1760                     (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode)) &&
1761                     !fscrypt_has_permitted_context(dir, inode)) {
1762                         ext4_warning(inode->i_sb,
1763                                      "Inconsistent encryption contexts: %lu/%lu",
1764                                      dir->i_ino, inode->i_ino);
1765                         iput(inode);
1766                         return ERR_PTR(-EPERM);
1767                 }
1768         }
1769
1770 #ifdef CONFIG_UNICODE
1771         if (!inode && IS_CASEFOLDED(dir)) {
1772                 /* Eventually we want to call d_add_ci(dentry, NULL)
1773                  * for negative dentries in the encoding case as
1774                  * well.  For now, prevent the negative dentry
1775                  * from being cached.
1776                  */
1777                 return NULL;
1778         }
1779 #endif
1780         return d_splice_alias(inode, dentry);
1781 }
1782
1783
1784 struct dentry *ext4_get_parent(struct dentry *child)
1785 {
1786         __u32 ino;
1787         static const struct qstr dotdot = QSTR_INIT("..", 2);
1788         struct ext4_dir_entry_2 * de;
1789         struct buffer_head *bh;
1790
1791         bh = ext4_find_entry(d_inode(child), &dotdot, &de, NULL);
1792         if (IS_ERR(bh))
1793                 return ERR_CAST(bh);
1794         if (!bh)
1795                 return ERR_PTR(-ENOENT);
1796         ino = le32_to_cpu(de->inode);
1797         brelse(bh);
1798
1799         if (!ext4_valid_inum(child->d_sb, ino)) {
1800                 EXT4_ERROR_INODE(d_inode(child),
1801                                  "bad parent inode number: %u", ino);
1802                 return ERR_PTR(-EFSCORRUPTED);
1803         }
1804
1805         return d_obtain_alias(ext4_iget(child->d_sb, ino, EXT4_IGET_NORMAL));
1806 }
1807
1808 /*
1809  * Move count entries from end of map between two memory locations.
1810  * Returns pointer to last entry moved.
1811  */
1812 static struct ext4_dir_entry_2 *
1813 dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count,
1814                 unsigned blocksize)
1815 {
1816         unsigned rec_len = 0;
1817
1818         while (count--) {
1819                 struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)
1820                                                 (from + (map->offs<<2));
1821                 rec_len = EXT4_DIR_REC_LEN(de->name_len);
1822                 memcpy (to, de, rec_len);
1823                 ((struct ext4_dir_entry_2 *) to)->rec_len =
1824                                 ext4_rec_len_to_disk(rec_len, blocksize);
1825                 de->inode = 0;
1826                 map++;
1827                 to += rec_len;
1828         }
1829         return (struct ext4_dir_entry_2 *) (to - rec_len);
1830 }
1831
1832 /*
1833  * Compact each dir entry in the range to the minimal rec_len.
1834  * Returns pointer to last entry in range.
1835  */
1836 static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize)
1837 {
1838         struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base;
1839         unsigned rec_len = 0;
1840
1841         prev = to = de;
1842         while ((char*)de < base + blocksize) {
1843                 next = ext4_next_entry(de, blocksize);
1844                 if (de->inode && de->name_len) {
1845                         rec_len = EXT4_DIR_REC_LEN(de->name_len);
1846                         if (de > to)
1847                                 memmove(to, de, rec_len);
1848                         to->rec_len = ext4_rec_len_to_disk(rec_len, blocksize);
1849                         prev = to;
1850                         to = (struct ext4_dir_entry_2 *) (((char *) to) + rec_len);
1851                 }
1852                 de = next;
1853         }
1854         return prev;
1855 }
1856
1857 /*
1858  * Split a full leaf block to make room for a new dir entry.
1859  * Allocate a new block, and move entries so that they are approx. equally full.
1860  * Returns pointer to de in block into which the new entry will be inserted.
1861  */
1862 static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
1863                         struct buffer_head **bh,struct dx_frame *frame,
1864                         struct dx_hash_info *hinfo)
1865 {
1866         unsigned blocksize = dir->i_sb->s_blocksize;
1867         unsigned continued;
1868         int count;
1869         struct buffer_head *bh2;
1870         ext4_lblk_t newblock;
1871         u32 hash2;
1872         struct dx_map_entry *map;
1873         char *data1 = (*bh)->b_data, *data2;
1874         unsigned split, move, size;
1875         struct ext4_dir_entry_2 *de = NULL, *de2;
1876         int     csum_size = 0;
1877         int     err = 0, i;
1878
1879         if (ext4_has_metadata_csum(dir->i_sb))
1880                 csum_size = sizeof(struct ext4_dir_entry_tail);
1881
1882         bh2 = ext4_append(handle, dir, &newblock);
1883         if (IS_ERR(bh2)) {
1884                 brelse(*bh);
1885                 *bh = NULL;
1886                 return (struct ext4_dir_entry_2 *) bh2;
1887         }
1888
1889         BUFFER_TRACE(*bh, "get_write_access");
1890         err = ext4_journal_get_write_access(handle, *bh);
1891         if (err)
1892                 goto journal_error;
1893
1894         BUFFER_TRACE(frame->bh, "get_write_access");
1895         err = ext4_journal_get_write_access(handle, frame->bh);
1896         if (err)
1897                 goto journal_error;
1898
1899         data2 = bh2->b_data;
1900
1901         /* create map in the end of data2 block */
1902         map = (struct dx_map_entry *) (data2 + blocksize);
1903         count = dx_make_map(dir, *bh, hinfo, map);
1904         if (count < 0) {
1905                 err = count;
1906                 goto journal_error;
1907         }
1908         map -= count;
1909         dx_sort_map(map, count);
1910         /* Ensure that neither split block is over half full */
1911         size = 0;
1912         move = 0;
1913         for (i = count-1; i >= 0; i--) {
1914                 /* is more than half of this entry in 2nd half of the block? */
1915                 if (size + map[i].size/2 > blocksize/2)
1916                         break;
1917                 size += map[i].size;
1918                 move++;
1919         }
1920         /*
1921          * map index at which we will split
1922          *
1923          * If the sum of active entries didn't exceed half the block size, just
1924          * split it in half by count; each resulting block will have at least
1925          * half the space free.
1926          */
1927         if (i > 0)
1928                 split = count - move;
1929         else
1930                 split = count/2;
1931
1932         hash2 = map[split].hash;
1933         continued = hash2 == map[split - 1].hash;
1934         dxtrace(printk(KERN_INFO "Split block %lu at %x, %i/%i\n",
1935                         (unsigned long)dx_get_block(frame->at),
1936                                         hash2, split, count-split));
1937
1938         /* Fancy dance to stay within two buffers */
1939         de2 = dx_move_dirents(data1, data2, map + split, count - split,
1940                               blocksize);
1941         de = dx_pack_dirents(data1, blocksize);
1942         de->rec_len = ext4_rec_len_to_disk(data1 + (blocksize - csum_size) -
1943                                            (char *) de,
1944                                            blocksize);
1945         de2->rec_len = ext4_rec_len_to_disk(data2 + (blocksize - csum_size) -
1946                                             (char *) de2,
1947                                             blocksize);
1948         if (csum_size) {
1949                 ext4_initialize_dirent_tail(*bh, blocksize);
1950                 ext4_initialize_dirent_tail(bh2, blocksize);
1951         }
1952
1953         dxtrace(dx_show_leaf(dir, hinfo, (struct ext4_dir_entry_2 *) data1,
1954                         blocksize, 1));
1955         dxtrace(dx_show_leaf(dir, hinfo, (struct ext4_dir_entry_2 *) data2,
1956                         blocksize, 1));
1957
1958         /* Which block gets the new entry? */
1959         if (hinfo->hash >= hash2) {
1960                 swap(*bh, bh2);
1961                 de = de2;
1962         }
1963         dx_insert_block(frame, hash2 + continued, newblock);
1964         err = ext4_handle_dirty_dirblock(handle, dir, bh2);
1965         if (err)
1966                 goto journal_error;
1967         err = ext4_handle_dirty_dx_node(handle, dir, frame->bh);
1968         if (err)
1969                 goto journal_error;
1970         brelse(bh2);
1971         dxtrace(dx_show_index("frame", frame->entries));
1972         return de;
1973
1974 journal_error:
1975         brelse(*bh);
1976         brelse(bh2);
1977         *bh = NULL;
1978         ext4_std_error(dir->i_sb, err);
1979         return ERR_PTR(err);
1980 }
1981
1982 int ext4_find_dest_de(struct inode *dir, struct inode *inode,
1983                       struct buffer_head *bh,
1984                       void *buf, int buf_size,
1985                       struct ext4_filename *fname,
1986                       struct ext4_dir_entry_2 **dest_de)
1987 {
1988         struct ext4_dir_entry_2 *de;
1989         unsigned short reclen = EXT4_DIR_REC_LEN(fname_len(fname));
1990         int nlen, rlen;
1991         unsigned int offset = 0;
1992         char *top;
1993
1994         de = (struct ext4_dir_entry_2 *)buf;
1995         top = buf + buf_size - reclen;
1996         while ((char *) de <= top) {
1997                 if (ext4_check_dir_entry(dir, NULL, de, bh,
1998                                          buf, buf_size, offset))
1999                         return -EFSCORRUPTED;
2000                 if (ext4_match(dir, fname, de))
2001                         return -EEXIST;
2002                 nlen = EXT4_DIR_REC_LEN(de->name_len);
2003                 rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
2004                 if ((de->inode ? rlen - nlen : rlen) >= reclen)
2005                         break;
2006                 de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
2007                 offset += rlen;
2008         }
2009         if ((char *) de > top)
2010                 return -ENOSPC;
2011
2012         *dest_de = de;
2013         return 0;
2014 }
2015
2016 void ext4_insert_dentry(struct inode *inode,
2017                         struct ext4_dir_entry_2 *de,
2018                         int buf_size,
2019                         struct ext4_filename *fname)
2020 {
2021
2022         int nlen, rlen;
2023
2024         nlen = EXT4_DIR_REC_LEN(de->name_len);
2025         rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
2026         if (de->inode) {
2027                 struct ext4_dir_entry_2 *de1 =
2028                         (struct ext4_dir_entry_2 *)((char *)de + nlen);
2029                 de1->rec_len = ext4_rec_len_to_disk(rlen - nlen, buf_size);
2030                 de->rec_len = ext4_rec_len_to_disk(nlen, buf_size);
2031                 de = de1;
2032         }
2033         de->file_type = EXT4_FT_UNKNOWN;
2034         de->inode = cpu_to_le32(inode->i_ino);
2035         ext4_set_de_type(inode->i_sb, de, inode->i_mode);
2036         de->name_len = fname_len(fname);
2037         memcpy(de->name, fname_name(fname), fname_len(fname));
2038 }
2039
2040 /*
2041  * Add a new entry into a directory (leaf) block.  If de is non-NULL,
2042  * it points to a directory entry which is guaranteed to be large
2043  * enough for new directory entry.  If de is NULL, then
2044  * add_dirent_to_buf will attempt search the directory block for
2045  * space.  It will return -ENOSPC if no space is available, and -EIO
2046  * and -EEXIST if directory entry already exists.
2047  */
2048 static int add_dirent_to_buf(handle_t *handle, struct ext4_filename *fname,
2049                              struct inode *dir,
2050                              struct inode *inode, struct ext4_dir_entry_2 *de,
2051                              struct buffer_head *bh)
2052 {
2053         unsigned int    blocksize = dir->i_sb->s_blocksize;
2054         int             csum_size = 0;
2055         int             err, err2;
2056
2057         if (ext4_has_metadata_csum(inode->i_sb))
2058                 csum_size = sizeof(struct ext4_dir_entry_tail);
2059
2060         if (!de) {
2061                 err = ext4_find_dest_de(dir, inode, bh, bh->b_data,
2062                                         blocksize - csum_size, fname, &de);
2063                 if (err)
2064                         return err;
2065         }
2066         BUFFER_TRACE(bh, "get_write_access");
2067         err = ext4_journal_get_write_access(handle, bh);
2068         if (err) {
2069                 ext4_std_error(dir->i_sb, err);
2070                 return err;
2071         }
2072
2073         /* By now the buffer is marked for journaling */
2074         ext4_insert_dentry(inode, de, blocksize, fname);
2075
2076         /*
2077          * XXX shouldn't update any times until successful
2078          * completion of syscall, but too many callers depend
2079          * on this.
2080          *
2081          * XXX similarly, too many callers depend on
2082          * ext4_new_inode() setting the times, but error
2083          * recovery deletes the inode, so the worst that can
2084          * happen is that the times are slightly out of date
2085          * and/or different from the directory change time.
2086          */
2087         dir->i_mtime = dir->i_ctime = current_time(dir);
2088         ext4_update_dx_flag(dir);
2089         inode_inc_iversion(dir);
2090         err2 = ext4_mark_inode_dirty(handle, dir);
2091         BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
2092         err = ext4_handle_dirty_dirblock(handle, dir, bh);
2093         if (err)
2094                 ext4_std_error(dir->i_sb, err);
2095         return err ? err : err2;
2096 }
2097
2098 /*
2099  * This converts a one block unindexed directory to a 3 block indexed
2100  * directory, and adds the dentry to the indexed directory.
2101  */
2102 static int make_indexed_dir(handle_t *handle, struct ext4_filename *fname,
2103                             struct inode *dir,
2104                             struct inode *inode, struct buffer_head *bh)
2105 {
2106         struct buffer_head *bh2;
2107         struct dx_root  *root;
2108         struct dx_frame frames[EXT4_HTREE_LEVEL], *frame;
2109         struct dx_entry *entries;
2110         struct ext4_dir_entry_2 *de, *de2;
2111         char            *data2, *top;
2112         unsigned        len;
2113         int             retval;
2114         unsigned        blocksize;
2115         ext4_lblk_t  block;
2116         struct fake_dirent *fde;
2117         int csum_size = 0;
2118
2119         if (ext4_has_metadata_csum(inode->i_sb))
2120                 csum_size = sizeof(struct ext4_dir_entry_tail);
2121
2122         blocksize =  dir->i_sb->s_blocksize;
2123         dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino));
2124         BUFFER_TRACE(bh, "get_write_access");
2125         retval = ext4_journal_get_write_access(handle, bh);
2126         if (retval) {
2127                 ext4_std_error(dir->i_sb, retval);
2128                 brelse(bh);
2129                 return retval;
2130         }
2131         root = (struct dx_root *) bh->b_data;
2132
2133         /* The 0th block becomes the root, move the dirents out */
2134         fde = &root->dotdot;
2135         de = (struct ext4_dir_entry_2 *)((char *)fde +
2136                 ext4_rec_len_from_disk(fde->rec_len, blocksize));
2137         if ((char *) de >= (((char *) root) + blocksize)) {
2138                 EXT4_ERROR_INODE(dir, "invalid rec_len for '..'");
2139                 brelse(bh);
2140                 return -EFSCORRUPTED;
2141         }
2142         len = ((char *) root) + (blocksize - csum_size) - (char *) de;
2143
2144         /* Allocate new block for the 0th block's dirents */
2145         bh2 = ext4_append(handle, dir, &block);
2146         if (IS_ERR(bh2)) {
2147                 brelse(bh);
2148                 return PTR_ERR(bh2);
2149         }
2150         ext4_set_inode_flag(dir, EXT4_INODE_INDEX);
2151         data2 = bh2->b_data;
2152
2153         memcpy(data2, de, len);
2154         de = (struct ext4_dir_entry_2 *) data2;
2155         top = data2 + len;
2156         while ((char *)(de2 = ext4_next_entry(de, blocksize)) < top)
2157                 de = de2;
2158         de->rec_len = ext4_rec_len_to_disk(data2 + (blocksize - csum_size) -
2159                                            (char *) de, blocksize);
2160
2161         if (csum_size)
2162                 ext4_initialize_dirent_tail(bh2, blocksize);
2163
2164         /* Initialize the root; the dot dirents already exist */
2165         de = (struct ext4_dir_entry_2 *) (&root->dotdot);
2166         de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(2),
2167                                            blocksize);
2168         memset (&root->info, 0, sizeof(root->info));
2169         root->info.info_length = sizeof(root->info);
2170         root->info.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
2171         entries = root->entries;
2172         dx_set_block(entries, 1);
2173         dx_set_count(entries, 1);
2174         dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
2175
2176         /* Initialize as for dx_probe */
2177         fname->hinfo.hash_version = root->info.hash_version;
2178         if (fname->hinfo.hash_version <= DX_HASH_TEA)
2179                 fname->hinfo.hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
2180         fname->hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
2181         ext4fs_dirhash(dir, fname_name(fname), fname_len(fname), &fname->hinfo);
2182
2183         memset(frames, 0, sizeof(frames));
2184         frame = frames;
2185         frame->entries = entries;
2186         frame->at = entries;
2187         frame->bh = bh;
2188
2189         retval = ext4_handle_dirty_dx_node(handle, dir, frame->bh);
2190         if (retval)
2191                 goto out_frames;
2192         retval = ext4_handle_dirty_dirblock(handle, dir, bh2);
2193         if (retval)
2194                 goto out_frames;
2195
2196         de = do_split(handle,dir, &bh2, frame, &fname->hinfo);
2197         if (IS_ERR(de)) {
2198                 retval = PTR_ERR(de);
2199                 goto out_frames;
2200         }
2201
2202         retval = add_dirent_to_buf(handle, fname, dir, inode, de, bh2);
2203 out_frames:
2204         /*
2205          * Even if the block split failed, we have to properly write
2206          * out all the changes we did so far. Otherwise we can end up
2207          * with corrupted filesystem.
2208          */
2209         if (retval)
2210                 ext4_mark_inode_dirty(handle, dir);
2211         dx_release(frames);
2212         brelse(bh2);
2213         return retval;
2214 }
2215
2216 /*
2217  *      ext4_add_entry()
2218  *
2219  * adds a file entry to the specified directory, using the same
2220  * semantics as ext4_find_entry(). It returns NULL if it failed.
2221  *
2222  * NOTE!! The inode part of 'de' is left at 0 - which means you
2223  * may not sleep between calling this and putting something into
2224  * the entry, as someone else might have used it while you slept.
2225  */
2226 static int ext4_add_entry(handle_t *handle, struct dentry *dentry,
2227                           struct inode *inode)
2228 {
2229         struct inode *dir = d_inode(dentry->d_parent);
2230         struct buffer_head *bh = NULL;
2231         struct ext4_dir_entry_2 *de;
2232         struct super_block *sb;
2233         struct ext4_filename fname;
2234         int     retval;
2235         int     dx_fallback=0;
2236         unsigned blocksize;
2237         ext4_lblk_t block, blocks;
2238         int     csum_size = 0;
2239
2240         if (ext4_has_metadata_csum(inode->i_sb))
2241                 csum_size = sizeof(struct ext4_dir_entry_tail);
2242
2243         sb = dir->i_sb;
2244         blocksize = sb->s_blocksize;
2245         if (!dentry->d_name.len)
2246                 return -EINVAL;
2247
2248         if (fscrypt_is_nokey_name(dentry))
2249                 return -ENOKEY;
2250
2251 #ifdef CONFIG_UNICODE
2252         if (sb_has_strict_encoding(sb) && IS_CASEFOLDED(dir) &&
2253             sb->s_encoding && utf8_validate(sb->s_encoding, &dentry->d_name))
2254                 return -EINVAL;
2255 #endif
2256
2257         retval = ext4_fname_setup_filename(dir, &dentry->d_name, 0, &fname);
2258         if (retval)
2259                 return retval;
2260
2261         if (ext4_has_inline_data(dir)) {
2262                 retval = ext4_try_add_inline_entry(handle, &fname, dir, inode);
2263                 if (retval < 0)
2264                         goto out;
2265                 if (retval == 1) {
2266                         retval = 0;
2267                         goto out;
2268                 }
2269         }
2270
2271         if (is_dx(dir)) {
2272                 retval = ext4_dx_add_entry(handle, &fname, dir, inode);
2273                 if (!retval || (retval != ERR_BAD_DX_DIR))
2274                         goto out;
2275                 /* Can we just ignore htree data? */
2276                 if (ext4_has_metadata_csum(sb)) {
2277                         EXT4_ERROR_INODE(dir,
2278                                 "Directory has corrupted htree index.");
2279                         retval = -EFSCORRUPTED;
2280                         goto out;
2281                 }
2282                 ext4_clear_inode_flag(dir, EXT4_INODE_INDEX);
2283                 dx_fallback++;
2284                 retval = ext4_mark_inode_dirty(handle, dir);
2285                 if (unlikely(retval))
2286                         goto out;
2287         }
2288         blocks = dir->i_size >> sb->s_blocksize_bits;
2289         for (block = 0; block < blocks; block++) {
2290                 bh = ext4_read_dirblock(dir, block, DIRENT);
2291                 if (bh == NULL) {
2292                         bh = ext4_bread(handle, dir, block,
2293                                         EXT4_GET_BLOCKS_CREATE);
2294                         goto add_to_new_block;
2295                 }
2296                 if (IS_ERR(bh)) {
2297                         retval = PTR_ERR(bh);
2298                         bh = NULL;
2299                         goto out;
2300                 }
2301                 retval = add_dirent_to_buf(handle, &fname, dir, inode,
2302                                            NULL, bh);
2303                 if (retval != -ENOSPC)
2304                         goto out;
2305
2306                 if (blocks == 1 && !dx_fallback &&
2307                     ext4_has_feature_dir_index(sb)) {
2308                         retval = make_indexed_dir(handle, &fname, dir,
2309                                                   inode, bh);
2310                         bh = NULL; /* make_indexed_dir releases bh */
2311                         goto out;
2312                 }
2313                 brelse(bh);
2314         }
2315         bh = ext4_append(handle, dir, &block);
2316 add_to_new_block:
2317         if (IS_ERR(bh)) {
2318                 retval = PTR_ERR(bh);
2319                 bh = NULL;
2320                 goto out;
2321         }
2322         de = (struct ext4_dir_entry_2 *) bh->b_data;
2323         de->inode = 0;
2324         de->rec_len = ext4_rec_len_to_disk(blocksize - csum_size, blocksize);
2325
2326         if (csum_size)
2327                 ext4_initialize_dirent_tail(bh, blocksize);
2328
2329         retval = add_dirent_to_buf(handle, &fname, dir, inode, de, bh);
2330 out:
2331         ext4_fname_free_filename(&fname);
2332         brelse(bh);
2333         if (retval == 0)
2334                 ext4_set_inode_state(inode, EXT4_STATE_NEWENTRY);
2335         return retval;
2336 }
2337
2338 /*
2339  * Returns 0 for success, or a negative error value
2340  */
2341 static int ext4_dx_add_entry(handle_t *handle, struct ext4_filename *fname,
2342                              struct inode *dir, struct inode *inode)
2343 {
2344         struct dx_frame frames[EXT4_HTREE_LEVEL], *frame;
2345         struct dx_entry *entries, *at;
2346         struct buffer_head *bh;
2347         struct super_block *sb = dir->i_sb;
2348         struct ext4_dir_entry_2 *de;
2349         int restart;
2350         int err;
2351
2352 again:
2353         restart = 0;
2354         frame = dx_probe(fname, dir, NULL, frames);
2355         if (IS_ERR(frame))
2356                 return PTR_ERR(frame);
2357         entries = frame->entries;
2358         at = frame->at;
2359         bh = ext4_read_dirblock(dir, dx_get_block(frame->at), DIRENT_HTREE);
2360         if (IS_ERR(bh)) {
2361                 err = PTR_ERR(bh);
2362                 bh = NULL;
2363                 goto cleanup;
2364         }
2365
2366         BUFFER_TRACE(bh, "get_write_access");
2367         err = ext4_journal_get_write_access(handle, bh);
2368         if (err)
2369                 goto journal_error;
2370
2371         err = add_dirent_to_buf(handle, fname, dir, inode, NULL, bh);
2372         if (err != -ENOSPC)
2373                 goto cleanup;
2374
2375         err = 0;
2376         /* Block full, should compress but for now just split */
2377         dxtrace(printk(KERN_DEBUG "using %u of %u node entries\n",
2378                        dx_get_count(entries), dx_get_limit(entries)));
2379         /* Need to split index? */
2380         if (dx_get_count(entries) == dx_get_limit(entries)) {
2381                 ext4_lblk_t newblock;
2382                 int levels = frame - frames + 1;
2383                 unsigned int icount;
2384                 int add_level = 1;
2385                 struct dx_entry *entries2;
2386                 struct dx_node *node2;
2387                 struct buffer_head *bh2;
2388
2389                 while (frame > frames) {
2390                         if (dx_get_count((frame - 1)->entries) <
2391                             dx_get_limit((frame - 1)->entries)) {
2392                                 add_level = 0;
2393                                 break;
2394                         }
2395                         frame--; /* split higher index block */
2396                         at = frame->at;
2397                         entries = frame->entries;
2398                         restart = 1;
2399                 }
2400                 if (add_level && levels == ext4_dir_htree_level(sb)) {
2401                         ext4_warning(sb, "Directory (ino: %lu) index full, "
2402                                          "reach max htree level :%d",
2403                                          dir->i_ino, levels);
2404                         if (ext4_dir_htree_level(sb) < EXT4_HTREE_LEVEL) {
2405                                 ext4_warning(sb, "Large directory feature is "
2406                                                  "not enabled on this "
2407                                                  "filesystem");
2408                         }
2409                         err = -ENOSPC;
2410                         goto cleanup;
2411                 }
2412                 icount = dx_get_count(entries);
2413                 bh2 = ext4_append(handle, dir, &newblock);
2414                 if (IS_ERR(bh2)) {
2415                         err = PTR_ERR(bh2);
2416                         goto cleanup;
2417                 }
2418                 node2 = (struct dx_node *)(bh2->b_data);
2419                 entries2 = node2->entries;
2420                 memset(&node2->fake, 0, sizeof(struct fake_dirent));
2421                 node2->fake.rec_len = ext4_rec_len_to_disk(sb->s_blocksize,
2422                                                            sb->s_blocksize);
2423                 BUFFER_TRACE(frame->bh, "get_write_access");
2424                 err = ext4_journal_get_write_access(handle, frame->bh);
2425                 if (err)
2426                         goto journal_error;
2427                 if (!add_level) {
2428                         unsigned icount1 = icount/2, icount2 = icount - icount1;
2429                         unsigned hash2 = dx_get_hash(entries + icount1);
2430                         dxtrace(printk(KERN_DEBUG "Split index %i/%i\n",
2431                                        icount1, icount2));
2432
2433                         BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
2434                         err = ext4_journal_get_write_access(handle,
2435                                                              (frame - 1)->bh);
2436                         if (err)
2437                                 goto journal_error;
2438
2439                         memcpy((char *) entries2, (char *) (entries + icount1),
2440                                icount2 * sizeof(struct dx_entry));
2441                         dx_set_count(entries, icount1);
2442                         dx_set_count(entries2, icount2);
2443                         dx_set_limit(entries2, dx_node_limit(dir));
2444
2445                         /* Which index block gets the new entry? */
2446                         if (at - entries >= icount1) {
2447                                 frame->at = at = at - entries - icount1 + entries2;
2448                                 frame->entries = entries = entries2;
2449                                 swap(frame->bh, bh2);
2450                         }
2451                         dx_insert_block((frame - 1), hash2, newblock);
2452                         dxtrace(dx_show_index("node", frame->entries));
2453                         dxtrace(dx_show_index("node",
2454                                ((struct dx_node *) bh2->b_data)->entries));
2455                         err = ext4_handle_dirty_dx_node(handle, dir, bh2);
2456                         if (err)
2457                                 goto journal_error;
2458                         brelse (bh2);
2459                         err = ext4_handle_dirty_dx_node(handle, dir,
2460                                                    (frame - 1)->bh);
2461                         if (err)
2462                                 goto journal_error;
2463                         err = ext4_handle_dirty_dx_node(handle, dir,
2464                                                         frame->bh);
2465                         if (restart || err)
2466                                 goto journal_error;
2467                 } else {
2468                         struct dx_root *dxroot;
2469                         memcpy((char *) entries2, (char *) entries,
2470                                icount * sizeof(struct dx_entry));
2471                         dx_set_limit(entries2, dx_node_limit(dir));
2472
2473                         /* Set up root */
2474                         dx_set_count(entries, 1);
2475                         dx_set_block(entries + 0, newblock);
2476                         dxroot = (struct dx_root *)frames[0].bh->b_data;
2477                         dxroot->info.indirect_levels += 1;
2478                         dxtrace(printk(KERN_DEBUG
2479                                        "Creating %d level index...\n",
2480                                        dxroot->info.indirect_levels));
2481                         err = ext4_handle_dirty_dx_node(handle, dir, frame->bh);
2482                         if (err)
2483                                 goto journal_error;
2484                         err = ext4_handle_dirty_dx_node(handle, dir, bh2);
2485                         brelse(bh2);
2486                         restart = 1;
2487                         goto journal_error;
2488                 }
2489         }
2490         de = do_split(handle, dir, &bh, frame, &fname->hinfo);
2491         if (IS_ERR(de)) {
2492                 err = PTR_ERR(de);
2493                 goto cleanup;
2494         }
2495         err = add_dirent_to_buf(handle, fname, dir, inode, de, bh);
2496         goto cleanup;
2497
2498 journal_error:
2499         ext4_std_error(dir->i_sb, err); /* this is a no-op if err == 0 */
2500 cleanup:
2501         brelse(bh);
2502         dx_release(frames);
2503         /* @restart is true means htree-path has been changed, we need to
2504          * repeat dx_probe() to find out valid htree-path
2505          */
2506         if (restart && err == 0)
2507                 goto again;
2508         return err;
2509 }
2510
2511 /*
2512  * ext4_generic_delete_entry deletes a directory entry by merging it
2513  * with the previous entry
2514  */
2515 int ext4_generic_delete_entry(struct inode *dir,
2516                               struct ext4_dir_entry_2 *de_del,
2517                               struct buffer_head *bh,
2518                               void *entry_buf,
2519                               int buf_size,
2520                               int csum_size)
2521 {
2522         struct ext4_dir_entry_2 *de, *pde;
2523         unsigned int blocksize = dir->i_sb->s_blocksize;
2524         int i;
2525
2526         i = 0;
2527         pde = NULL;
2528         de = (struct ext4_dir_entry_2 *)entry_buf;
2529         while (i < buf_size - csum_size) {
2530                 if (ext4_check_dir_entry(dir, NULL, de, bh,
2531                                          entry_buf, buf_size, i))
2532                         return -EFSCORRUPTED;
2533                 if (de == de_del)  {
2534                         if (pde)
2535                                 pde->rec_len = ext4_rec_len_to_disk(
2536                                         ext4_rec_len_from_disk(pde->rec_len,
2537                                                                blocksize) +
2538                                         ext4_rec_len_from_disk(de->rec_len,
2539                                                                blocksize),
2540                                         blocksize);
2541                         else
2542                                 de->inode = 0;
2543                         inode_inc_iversion(dir);
2544                         return 0;
2545                 }
2546                 i += ext4_rec_len_from_disk(de->rec_len, blocksize);
2547                 pde = de;
2548                 de = ext4_next_entry(de, blocksize);
2549         }
2550         return -ENOENT;
2551 }
2552
2553 static int ext4_delete_entry(handle_t *handle,
2554                              struct inode *dir,
2555                              struct ext4_dir_entry_2 *de_del,
2556                              struct buffer_head *bh)
2557 {
2558         int err, csum_size = 0;
2559
2560         if (ext4_has_inline_data(dir)) {
2561                 int has_inline_data = 1;
2562                 err = ext4_delete_inline_entry(handle, dir, de_del, bh,
2563                                                &has_inline_data);
2564                 if (has_inline_data)
2565                         return err;
2566         }
2567
2568         if (ext4_has_metadata_csum(dir->i_sb))
2569                 csum_size = sizeof(struct ext4_dir_entry_tail);
2570
2571         BUFFER_TRACE(bh, "get_write_access");
2572         err = ext4_journal_get_write_access(handle, bh);
2573         if (unlikely(err))
2574                 goto out;
2575
2576         err = ext4_generic_delete_entry(dir, de_del, bh, bh->b_data,
2577                                         dir->i_sb->s_blocksize, csum_size);
2578         if (err)
2579                 goto out;
2580
2581         BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
2582         err = ext4_handle_dirty_dirblock(handle, dir, bh);
2583         if (unlikely(err))
2584                 goto out;
2585
2586         return 0;
2587 out:
2588         if (err != -ENOENT)
2589                 ext4_std_error(dir->i_sb, err);
2590         return err;
2591 }
2592
2593 /*
2594  * Set directory link count to 1 if nlinks > EXT4_LINK_MAX, or if nlinks == 2
2595  * since this indicates that nlinks count was previously 1 to avoid overflowing
2596  * the 16-bit i_links_count field on disk.  Directories with i_nlink == 1 mean
2597  * that subdirectory link counts are not being maintained accurately.
2598  *
2599  * The caller has already checked for i_nlink overflow in case the DIR_LINK
2600  * feature is not enabled and returned -EMLINK.  The is_dx() check is a proxy
2601  * for checking S_ISDIR(inode) (since the INODE_INDEX feature will not be set
2602  * on regular files) and to avoid creating huge/slow non-HTREE directories.
2603  */
2604 static void ext4_inc_count(struct inode *inode)
2605 {
2606         inc_nlink(inode);
2607         if (is_dx(inode) &&
2608             (inode->i_nlink > EXT4_LINK_MAX || inode->i_nlink == 2))
2609                 set_nlink(inode, 1);
2610 }
2611
2612 /*
2613  * If a directory had nlink == 1, then we should let it be 1. This indicates
2614  * directory has >EXT4_LINK_MAX subdirs.
2615  */
2616 static void ext4_dec_count(struct inode *inode)
2617 {
2618         if (!S_ISDIR(inode->i_mode) || inode->i_nlink > 2)
2619                 drop_nlink(inode);
2620 }
2621
2622
2623 /*
2624  * Add non-directory inode to a directory. On success, the inode reference is
2625  * consumed by dentry is instantiation. This is also indicated by clearing of
2626  * *inodep pointer. On failure, the caller is responsible for dropping the
2627  * inode reference in the safe context.
2628  */
2629 static int ext4_add_nondir(handle_t *handle,
2630                 struct dentry *dentry, struct inode **inodep)
2631 {
2632         struct inode *dir = d_inode(dentry->d_parent);
2633         struct inode *inode = *inodep;
2634         int err = ext4_add_entry(handle, dentry, inode);
2635         if (!err) {
2636                 err = ext4_mark_inode_dirty(handle, inode);
2637                 if (IS_DIRSYNC(dir))
2638                         ext4_handle_sync(handle);
2639                 d_instantiate_new(dentry, inode);
2640                 *inodep = NULL;
2641                 return err;
2642         }
2643         drop_nlink(inode);
2644         ext4_orphan_add(handle, inode);
2645         unlock_new_inode(inode);
2646         return err;
2647 }
2648
2649 /*
2650  * By the time this is called, we already have created
2651  * the directory cache entry for the new file, but it
2652  * is so far negative - it has no inode.
2653  *
2654  * If the create succeeds, we fill in the inode information
2655  * with d_instantiate().
2656  */
2657 static int ext4_create(struct inode *dir, struct dentry *dentry, umode_t mode,
2658                        bool excl)
2659 {
2660         handle_t *handle;
2661         struct inode *inode;
2662         int err, credits, retries = 0;
2663
2664         err = dquot_initialize(dir);
2665         if (err)
2666                 return err;
2667
2668         credits = (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2669                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3);
2670 retry:
2671         inode = ext4_new_inode_start_handle(dir, mode, &dentry->d_name, 0,
2672                                             NULL, EXT4_HT_DIR, credits);
2673         handle = ext4_journal_current_handle();
2674         err = PTR_ERR(inode);
2675         if (!IS_ERR(inode)) {
2676                 inode->i_op = &ext4_file_inode_operations;
2677                 inode->i_fop = &ext4_file_operations;
2678                 ext4_set_aops(inode);
2679                 err = ext4_add_nondir(handle, dentry, &inode);
2680                 if (!err)
2681                         ext4_fc_track_create(handle, dentry);
2682         }
2683         if (handle)
2684                 ext4_journal_stop(handle);
2685         if (!IS_ERR_OR_NULL(inode))
2686                 iput(inode);
2687         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2688                 goto retry;
2689         return err;
2690 }
2691
2692 static int ext4_mknod(struct inode *dir, struct dentry *dentry,
2693                       umode_t mode, dev_t rdev)
2694 {
2695         handle_t *handle;
2696         struct inode *inode;
2697         int err, credits, retries = 0;
2698
2699         err = dquot_initialize(dir);
2700         if (err)
2701                 return err;
2702
2703         credits = (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2704                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3);
2705 retry:
2706         inode = ext4_new_inode_start_handle(dir, mode, &dentry->d_name, 0,
2707                                             NULL, EXT4_HT_DIR, credits);
2708         handle = ext4_journal_current_handle();
2709         err = PTR_ERR(inode);
2710         if (!IS_ERR(inode)) {
2711                 init_special_inode(inode, inode->i_mode, rdev);
2712                 inode->i_op = &ext4_special_inode_operations;
2713                 err = ext4_add_nondir(handle, dentry, &inode);
2714                 if (!err)
2715                         ext4_fc_track_create(handle, dentry);
2716         }
2717         if (handle)
2718                 ext4_journal_stop(handle);
2719         if (!IS_ERR_OR_NULL(inode))
2720                 iput(inode);
2721         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2722                 goto retry;
2723         return err;
2724 }
2725
2726 static int ext4_tmpfile(struct inode *dir, struct dentry *dentry, umode_t mode)
2727 {
2728         handle_t *handle;
2729         struct inode *inode;
2730         int err, retries = 0;
2731
2732         err = dquot_initialize(dir);
2733         if (err)
2734                 return err;
2735
2736 retry:
2737         inode = ext4_new_inode_start_handle(dir, mode,
2738                                             NULL, 0, NULL,
2739                                             EXT4_HT_DIR,
2740                         EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb) +
2741                           4 + EXT4_XATTR_TRANS_BLOCKS);
2742         handle = ext4_journal_current_handle();
2743         err = PTR_ERR(inode);
2744         if (!IS_ERR(inode)) {
2745                 inode->i_op = &ext4_file_inode_operations;
2746                 inode->i_fop = &ext4_file_operations;
2747                 ext4_set_aops(inode);
2748                 d_tmpfile(dentry, inode);
2749                 err = ext4_orphan_add(handle, inode);
2750                 if (err)
2751                         goto err_unlock_inode;
2752                 mark_inode_dirty(inode);
2753                 unlock_new_inode(inode);
2754         }
2755         if (handle)
2756                 ext4_journal_stop(handle);
2757         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2758                 goto retry;
2759         return err;
2760 err_unlock_inode:
2761         ext4_journal_stop(handle);
2762         unlock_new_inode(inode);
2763         return err;
2764 }
2765
2766 struct ext4_dir_entry_2 *ext4_init_dot_dotdot(struct inode *inode,
2767                           struct ext4_dir_entry_2 *de,
2768                           int blocksize, int csum_size,
2769                           unsigned int parent_ino, int dotdot_real_len)
2770 {
2771         de->inode = cpu_to_le32(inode->i_ino);
2772         de->name_len = 1;
2773         de->rec_len = ext4_rec_len_to_disk(EXT4_DIR_REC_LEN(de->name_len),
2774                                            blocksize);
2775         strcpy(de->name, ".");
2776         ext4_set_de_type(inode->i_sb, de, S_IFDIR);
2777
2778         de = ext4_next_entry(de, blocksize);
2779         de->inode = cpu_to_le32(parent_ino);
2780         de->name_len = 2;
2781         if (!dotdot_real_len)
2782                 de->rec_len = ext4_rec_len_to_disk(blocksize -
2783                                         (csum_size + EXT4_DIR_REC_LEN(1)),
2784                                         blocksize);
2785         else
2786                 de->rec_len = ext4_rec_len_to_disk(
2787                                 EXT4_DIR_REC_LEN(de->name_len), blocksize);
2788         strcpy(de->name, "..");
2789         ext4_set_de_type(inode->i_sb, de, S_IFDIR);
2790
2791         return ext4_next_entry(de, blocksize);
2792 }
2793
2794 int ext4_init_new_dir(handle_t *handle, struct inode *dir,
2795                              struct inode *inode)
2796 {
2797         struct buffer_head *dir_block = NULL;
2798         struct ext4_dir_entry_2 *de;
2799         ext4_lblk_t block = 0;
2800         unsigned int blocksize = dir->i_sb->s_blocksize;
2801         int csum_size = 0;
2802         int err;
2803
2804         if (ext4_has_metadata_csum(dir->i_sb))
2805                 csum_size = sizeof(struct ext4_dir_entry_tail);
2806
2807         if (ext4_test_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA)) {
2808                 err = ext4_try_create_inline_dir(handle, dir, inode);
2809                 if (err < 0 && err != -ENOSPC)
2810                         goto out;
2811                 if (!err)
2812                         goto out;
2813         }
2814
2815         inode->i_size = 0;
2816         dir_block = ext4_append(handle, inode, &block);
2817         if (IS_ERR(dir_block))
2818                 return PTR_ERR(dir_block);
2819         de = (struct ext4_dir_entry_2 *)dir_block->b_data;
2820         ext4_init_dot_dotdot(inode, de, blocksize, csum_size, dir->i_ino, 0);
2821         set_nlink(inode, 2);
2822         if (csum_size)
2823                 ext4_initialize_dirent_tail(dir_block, blocksize);
2824
2825         BUFFER_TRACE(dir_block, "call ext4_handle_dirty_metadata");
2826         err = ext4_handle_dirty_dirblock(handle, inode, dir_block);
2827         if (err)
2828                 goto out;
2829         set_buffer_verified(dir_block);
2830 out:
2831         brelse(dir_block);
2832         return err;
2833 }
2834
2835 static int ext4_mkdir(struct inode *dir, struct dentry *dentry, umode_t mode)
2836 {
2837         handle_t *handle;
2838         struct inode *inode;
2839         int err, err2 = 0, credits, retries = 0;
2840
2841         if (EXT4_DIR_LINK_MAX(dir))
2842                 return -EMLINK;
2843
2844         err = dquot_initialize(dir);
2845         if (err)
2846                 return err;
2847
2848         credits = (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2849                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3);
2850 retry:
2851         inode = ext4_new_inode_start_handle(dir, S_IFDIR | mode,
2852                                             &dentry->d_name,
2853                                             0, NULL, EXT4_HT_DIR, credits);
2854         handle = ext4_journal_current_handle();
2855         err = PTR_ERR(inode);
2856         if (IS_ERR(inode))
2857                 goto out_stop;
2858
2859         inode->i_op = &ext4_dir_inode_operations;
2860         inode->i_fop = &ext4_dir_operations;
2861         err = ext4_init_new_dir(handle, dir, inode);
2862         if (err)
2863                 goto out_clear_inode;
2864         err = ext4_mark_inode_dirty(handle, inode);
2865         if (!err)
2866                 err = ext4_add_entry(handle, dentry, inode);
2867         if (err) {
2868 out_clear_inode:
2869                 clear_nlink(inode);
2870                 ext4_orphan_add(handle, inode);
2871                 unlock_new_inode(inode);
2872                 err2 = ext4_mark_inode_dirty(handle, inode);
2873                 if (unlikely(err2))
2874                         err = err2;
2875                 ext4_journal_stop(handle);
2876                 iput(inode);
2877                 goto out_retry;
2878         }
2879         ext4_inc_count(dir);
2880
2881         ext4_update_dx_flag(dir);
2882         err = ext4_mark_inode_dirty(handle, dir);
2883         if (err)
2884                 goto out_clear_inode;
2885         d_instantiate_new(dentry, inode);
2886         ext4_fc_track_create(handle, dentry);
2887         if (IS_DIRSYNC(dir))
2888                 ext4_handle_sync(handle);
2889
2890 out_stop:
2891         if (handle)
2892                 ext4_journal_stop(handle);
2893 out_retry:
2894         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2895                 goto retry;
2896         return err;
2897 }
2898
2899 /*
2900  * routine to check that the specified directory is empty (for rmdir)
2901  */
2902 bool ext4_empty_dir(struct inode *inode)
2903 {
2904         unsigned int offset;
2905         struct buffer_head *bh;
2906         struct ext4_dir_entry_2 *de;
2907         struct super_block *sb;
2908
2909         if (ext4_has_inline_data(inode)) {
2910                 int has_inline_data = 1;
2911                 int ret;
2912
2913                 ret = empty_inline_dir(inode, &has_inline_data);
2914                 if (has_inline_data)
2915                         return ret;
2916         }
2917
2918         sb = inode->i_sb;
2919         if (inode->i_size < EXT4_DIR_REC_LEN(1) + EXT4_DIR_REC_LEN(2)) {
2920                 EXT4_ERROR_INODE(inode, "invalid size");
2921                 return false;
2922         }
2923         /* The first directory block must not be a hole,
2924          * so treat it as DIRENT_HTREE
2925          */
2926         bh = ext4_read_dirblock(inode, 0, DIRENT_HTREE);
2927         if (IS_ERR(bh))
2928                 return false;
2929
2930         de = (struct ext4_dir_entry_2 *) bh->b_data;
2931         if (ext4_check_dir_entry(inode, NULL, de, bh, bh->b_data, bh->b_size,
2932                                  0) ||
2933             le32_to_cpu(de->inode) != inode->i_ino || strcmp(".", de->name)) {
2934                 ext4_warning_inode(inode, "directory missing '.'");
2935                 brelse(bh);
2936                 return false;
2937         }
2938         offset = ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
2939         de = ext4_next_entry(de, sb->s_blocksize);
2940         if (ext4_check_dir_entry(inode, NULL, de, bh, bh->b_data, bh->b_size,
2941                                  offset) ||
2942             le32_to_cpu(de->inode) == 0 || strcmp("..", de->name)) {
2943                 ext4_warning_inode(inode, "directory missing '..'");
2944                 brelse(bh);
2945                 return false;
2946         }
2947         offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
2948         while (offset < inode->i_size) {
2949                 if (!(offset & (sb->s_blocksize - 1))) {
2950                         unsigned int lblock;
2951                         brelse(bh);
2952                         lblock = offset >> EXT4_BLOCK_SIZE_BITS(sb);
2953                         bh = ext4_read_dirblock(inode, lblock, EITHER);
2954                         if (bh == NULL) {
2955                                 offset += sb->s_blocksize;
2956                                 continue;
2957                         }
2958                         if (IS_ERR(bh))
2959                                 return false;
2960                 }
2961                 de = (struct ext4_dir_entry_2 *) (bh->b_data +
2962                                         (offset & (sb->s_blocksize - 1)));
2963                 if (ext4_check_dir_entry(inode, NULL, de, bh,
2964                                          bh->b_data, bh->b_size, offset) ||
2965                     le32_to_cpu(de->inode)) {
2966                         brelse(bh);
2967                         return false;
2968                 }
2969                 offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
2970         }
2971         brelse(bh);
2972         return true;
2973 }
2974
2975 /*
2976  * ext4_orphan_add() links an unlinked or truncated inode into a list of
2977  * such inodes, starting at the superblock, in case we crash before the
2978  * file is closed/deleted, or in case the inode truncate spans multiple
2979  * transactions and the last transaction is not recovered after a crash.
2980  *
2981  * At filesystem recovery time, we walk this list deleting unlinked
2982  * inodes and truncating linked inodes in ext4_orphan_cleanup().
2983  *
2984  * Orphan list manipulation functions must be called under i_mutex unless
2985  * we are just creating the inode or deleting it.
2986  */
2987 int ext4_orphan_add(handle_t *handle, struct inode *inode)
2988 {
2989         struct super_block *sb = inode->i_sb;
2990         struct ext4_sb_info *sbi = EXT4_SB(sb);
2991         struct ext4_iloc iloc;
2992         int err = 0, rc;
2993         bool dirty = false;
2994
2995         if (!sbi->s_journal || is_bad_inode(inode))
2996                 return 0;
2997
2998         WARN_ON_ONCE(!(inode->i_state & (I_NEW | I_FREEING)) &&
2999                      !inode_is_locked(inode));
3000         /*
3001          * Exit early if inode already is on orphan list. This is a big speedup
3002          * since we don't have to contend on the global s_orphan_lock.
3003          */
3004         if (!list_empty(&EXT4_I(inode)->i_orphan))
3005                 return 0;
3006
3007         /*
3008          * Orphan handling is only valid for files with data blocks
3009          * being truncated, or files being unlinked. Note that we either
3010          * hold i_mutex, or the inode can not be referenced from outside,
3011          * so i_nlink should not be bumped due to race
3012          */
3013         J_ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
3014                   S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
3015
3016         BUFFER_TRACE(sbi->s_sbh, "get_write_access");
3017         err = ext4_journal_get_write_access(handle, sbi->s_sbh);
3018         if (err)
3019                 goto out;
3020
3021         err = ext4_reserve_inode_write(handle, inode, &iloc);
3022         if (err)
3023                 goto out;
3024
3025         mutex_lock(&sbi->s_orphan_lock);
3026         /*
3027          * Due to previous errors inode may be already a part of on-disk
3028          * orphan list. If so skip on-disk list modification.
3029          */
3030         if (!NEXT_ORPHAN(inode) || NEXT_ORPHAN(inode) >
3031             (le32_to_cpu(sbi->s_es->s_inodes_count))) {
3032                 /* Insert this inode at the head of the on-disk orphan list */
3033                 NEXT_ORPHAN(inode) = le32_to_cpu(sbi->s_es->s_last_orphan);
3034                 sbi->s_es->s_last_orphan = cpu_to_le32(inode->i_ino);
3035                 dirty = true;
3036         }
3037         list_add(&EXT4_I(inode)->i_orphan, &sbi->s_orphan);
3038         mutex_unlock(&sbi->s_orphan_lock);
3039
3040         if (dirty) {
3041                 err = ext4_handle_dirty_super(handle, sb);
3042                 rc = ext4_mark_iloc_dirty(handle, inode, &iloc);
3043                 if (!err)
3044                         err = rc;
3045                 if (err) {
3046                         /*
3047                          * We have to remove inode from in-memory list if
3048                          * addition to on disk orphan list failed. Stray orphan
3049                          * list entries can cause panics at unmount time.
3050                          */
3051                         mutex_lock(&sbi->s_orphan_lock);
3052                         list_del_init(&EXT4_I(inode)->i_orphan);
3053                         mutex_unlock(&sbi->s_orphan_lock);
3054                 }
3055         } else
3056                 brelse(iloc.bh);
3057
3058         jbd_debug(4, "superblock will point to %lu\n", inode->i_ino);
3059         jbd_debug(4, "orphan inode %lu will point to %d\n",
3060                         inode->i_ino, NEXT_ORPHAN(inode));
3061 out:
3062         ext4_std_error(sb, err);
3063         return err;
3064 }
3065
3066 /*
3067  * ext4_orphan_del() removes an unlinked or truncated inode from the list
3068  * of such inodes stored on disk, because it is finally being cleaned up.
3069  */
3070 int ext4_orphan_del(handle_t *handle, struct inode *inode)
3071 {
3072         struct list_head *prev;
3073         struct ext4_inode_info *ei = EXT4_I(inode);
3074         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3075         __u32 ino_next;
3076         struct ext4_iloc iloc;
3077         int err = 0;
3078
3079         if (!sbi->s_journal && !(sbi->s_mount_state & EXT4_ORPHAN_FS))
3080                 return 0;
3081
3082         WARN_ON_ONCE(!(inode->i_state & (I_NEW | I_FREEING)) &&
3083                      !inode_is_locked(inode));
3084         /* Do this quick check before taking global s_orphan_lock. */
3085         if (list_empty(&ei->i_orphan))
3086                 return 0;
3087
3088         if (handle) {
3089                 /* Grab inode buffer early before taking global s_orphan_lock */
3090                 err = ext4_reserve_inode_write(handle, inode, &iloc);
3091         }
3092
3093         mutex_lock(&sbi->s_orphan_lock);
3094         jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino);
3095
3096         prev = ei->i_orphan.prev;
3097         list_del_init(&ei->i_orphan);
3098
3099         /* If we're on an error path, we may not have a valid
3100          * transaction handle with which to update the orphan list on
3101          * disk, but we still need to remove the inode from the linked
3102          * list in memory. */
3103         if (!handle || err) {
3104                 mutex_unlock(&sbi->s_orphan_lock);
3105                 goto out_err;
3106         }
3107
3108         ino_next = NEXT_ORPHAN(inode);
3109         if (prev == &sbi->s_orphan) {
3110                 jbd_debug(4, "superblock will point to %u\n", ino_next);
3111                 BUFFER_TRACE(sbi->s_sbh, "get_write_access");
3112                 err = ext4_journal_get_write_access(handle, sbi->s_sbh);
3113                 if (err) {
3114                         mutex_unlock(&sbi->s_orphan_lock);
3115                         goto out_brelse;
3116                 }
3117                 sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
3118                 mutex_unlock(&sbi->s_orphan_lock);
3119                 err = ext4_handle_dirty_super(handle, inode->i_sb);
3120         } else {
3121                 struct ext4_iloc iloc2;
3122                 struct inode *i_prev =
3123                         &list_entry(prev, struct ext4_inode_info, i_orphan)->vfs_inode;
3124
3125                 jbd_debug(4, "orphan inode %lu will point to %u\n",
3126                           i_prev->i_ino, ino_next);
3127                 err = ext4_reserve_inode_write(handle, i_prev, &iloc2);
3128                 if (err) {
3129                         mutex_unlock(&sbi->s_orphan_lock);
3130                         goto out_brelse;
3131                 }
3132                 NEXT_ORPHAN(i_prev) = ino_next;
3133                 err = ext4_mark_iloc_dirty(handle, i_prev, &iloc2);
3134                 mutex_unlock(&sbi->s_orphan_lock);
3135         }
3136         if (err)
3137                 goto out_brelse;
3138         NEXT_ORPHAN(inode) = 0;
3139         err = ext4_mark_iloc_dirty(handle, inode, &iloc);
3140 out_err:
3141         ext4_std_error(inode->i_sb, err);
3142         return err;
3143
3144 out_brelse:
3145         brelse(iloc.bh);
3146         goto out_err;
3147 }
3148
3149 static int ext4_rmdir(struct inode *dir, struct dentry *dentry)
3150 {
3151         int retval;
3152         struct inode *inode;
3153         struct buffer_head *bh;
3154         struct ext4_dir_entry_2 *de;
3155         handle_t *handle = NULL;
3156
3157         if (unlikely(ext4_forced_shutdown(EXT4_SB(dir->i_sb))))
3158                 return -EIO;
3159
3160         /* Initialize quotas before so that eventual writes go in
3161          * separate transaction */
3162         retval = dquot_initialize(dir);
3163         if (retval)
3164                 return retval;
3165         retval = dquot_initialize(d_inode(dentry));
3166         if (retval)
3167                 return retval;
3168
3169         retval = -ENOENT;
3170         bh = ext4_find_entry(dir, &dentry->d_name, &de, NULL);
3171         if (IS_ERR(bh))
3172                 return PTR_ERR(bh);
3173         if (!bh)
3174                 goto end_rmdir;
3175
3176         inode = d_inode(dentry);
3177
3178         retval = -EFSCORRUPTED;
3179         if (le32_to_cpu(de->inode) != inode->i_ino)
3180                 goto end_rmdir;
3181
3182         retval = -ENOTEMPTY;
3183         if (!ext4_empty_dir(inode))
3184                 goto end_rmdir;
3185
3186         handle = ext4_journal_start(dir, EXT4_HT_DIR,
3187                                     EXT4_DATA_TRANS_BLOCKS(dir->i_sb));
3188         if (IS_ERR(handle)) {
3189                 retval = PTR_ERR(handle);
3190                 handle = NULL;
3191                 goto end_rmdir;
3192         }
3193
3194         if (IS_DIRSYNC(dir))
3195                 ext4_handle_sync(handle);
3196
3197         retval = ext4_delete_entry(handle, dir, de, bh);
3198         if (retval)
3199                 goto end_rmdir;
3200         if (!EXT4_DIR_LINK_EMPTY(inode))
3201                 ext4_warning_inode(inode,
3202                              "empty directory '%.*s' has too many links (%u)",
3203                              dentry->d_name.len, dentry->d_name.name,
3204                              inode->i_nlink);
3205         inode_inc_iversion(inode);
3206         clear_nlink(inode);
3207         /* There's no need to set i_disksize: the fact that i_nlink is
3208          * zero will ensure that the right thing happens during any
3209          * recovery. */
3210         inode->i_size = 0;
3211         ext4_orphan_add(handle, inode);
3212         inode->i_ctime = dir->i_ctime = dir->i_mtime = current_time(inode);
3213         retval = ext4_mark_inode_dirty(handle, inode);
3214         if (retval)
3215                 goto end_rmdir;
3216         ext4_dec_count(dir);
3217         ext4_update_dx_flag(dir);
3218         ext4_fc_track_unlink(handle, dentry);
3219         retval = ext4_mark_inode_dirty(handle, dir);
3220
3221 #ifdef CONFIG_UNICODE
3222         /* VFS negative dentries are incompatible with Encoding and
3223          * Case-insensitiveness. Eventually we'll want avoid
3224          * invalidating the dentries here, alongside with returning the
3225          * negative dentries at ext4_lookup(), when it is better
3226          * supported by the VFS for the CI case.
3227          */
3228         if (IS_CASEFOLDED(dir))
3229                 d_invalidate(dentry);
3230 #endif
3231
3232 end_rmdir:
3233         brelse(bh);
3234         if (handle)
3235                 ext4_journal_stop(handle);
3236         return retval;
3237 }
3238
3239 int __ext4_unlink(handle_t *handle, struct inode *dir, const struct qstr *d_name,
3240                   struct inode *inode)
3241 {
3242         int retval = -ENOENT;
3243         struct buffer_head *bh;
3244         struct ext4_dir_entry_2 *de;
3245         int skip_remove_dentry = 0;
3246
3247         bh = ext4_find_entry(dir, d_name, &de, NULL);
3248         if (IS_ERR(bh))
3249                 return PTR_ERR(bh);
3250
3251         if (!bh)
3252                 return -ENOENT;
3253
3254         if (le32_to_cpu(de->inode) != inode->i_ino) {
3255                 /*
3256                  * It's okay if we find dont find dentry which matches
3257                  * the inode. That's because it might have gotten
3258                  * renamed to a different inode number
3259                  */
3260                 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
3261                         skip_remove_dentry = 1;
3262                 else
3263                         goto out;
3264         }
3265
3266         if (IS_DIRSYNC(dir))
3267                 ext4_handle_sync(handle);
3268
3269         if (!skip_remove_dentry) {
3270                 retval = ext4_delete_entry(handle, dir, de, bh);
3271                 if (retval)
3272                         goto out;
3273                 dir->i_ctime = dir->i_mtime = current_time(dir);
3274                 ext4_update_dx_flag(dir);
3275                 retval = ext4_mark_inode_dirty(handle, dir);
3276                 if (retval)
3277                         goto out;
3278         } else {
3279                 retval = 0;
3280         }
3281         if (inode->i_nlink == 0)
3282                 ext4_warning_inode(inode, "Deleting file '%.*s' with no links",
3283                                    d_name->len, d_name->name);
3284         else
3285                 drop_nlink(inode);
3286         if (!inode->i_nlink)
3287                 ext4_orphan_add(handle, inode);
3288         inode->i_ctime = current_time(inode);
3289         retval = ext4_mark_inode_dirty(handle, inode);
3290
3291 out:
3292         brelse(bh);
3293         return retval;
3294 }
3295
3296 static int ext4_unlink(struct inode *dir, struct dentry *dentry)
3297 {
3298         handle_t *handle;
3299         int retval;
3300
3301         if (unlikely(ext4_forced_shutdown(EXT4_SB(dir->i_sb))))
3302                 return -EIO;
3303
3304         trace_ext4_unlink_enter(dir, dentry);
3305         /*
3306          * Initialize quotas before so that eventual writes go
3307          * in separate transaction
3308          */
3309         retval = dquot_initialize(dir);
3310         if (retval)
3311                 goto out_trace;
3312         retval = dquot_initialize(d_inode(dentry));
3313         if (retval)
3314                 goto out_trace;
3315
3316         handle = ext4_journal_start(dir, EXT4_HT_DIR,
3317                                     EXT4_DATA_TRANS_BLOCKS(dir->i_sb));
3318         if (IS_ERR(handle)) {
3319                 retval = PTR_ERR(handle);
3320                 goto out_trace;
3321         }
3322
3323         retval = __ext4_unlink(handle, dir, &dentry->d_name, d_inode(dentry));
3324         if (!retval)
3325                 ext4_fc_track_unlink(handle, dentry);
3326 #ifdef CONFIG_UNICODE
3327         /* VFS negative dentries are incompatible with Encoding and
3328          * Case-insensitiveness. Eventually we'll want avoid
3329          * invalidating the dentries here, alongside with returning the
3330          * negative dentries at ext4_lookup(), when it is  better
3331          * supported by the VFS for the CI case.
3332          */
3333         if (IS_CASEFOLDED(dir))
3334                 d_invalidate(dentry);
3335 #endif
3336         if (handle)
3337                 ext4_journal_stop(handle);
3338
3339 out_trace:
3340         trace_ext4_unlink_exit(dentry, retval);
3341         return retval;
3342 }
3343
3344 static int ext4_symlink(struct inode *dir,
3345                         struct dentry *dentry, const char *symname)
3346 {
3347         handle_t *handle;
3348         struct inode *inode;
3349         int err, len = strlen(symname);
3350         int credits;
3351         struct fscrypt_str disk_link;
3352
3353         if (unlikely(ext4_forced_shutdown(EXT4_SB(dir->i_sb))))
3354                 return -EIO;
3355
3356         err = fscrypt_prepare_symlink(dir, symname, len, dir->i_sb->s_blocksize,
3357                                       &disk_link);
3358         if (err)
3359                 return err;
3360
3361         err = dquot_initialize(dir);
3362         if (err)
3363                 return err;
3364
3365         if ((disk_link.len > EXT4_N_BLOCKS * 4)) {
3366                 /*
3367                  * For non-fast symlinks, we just allocate inode and put it on
3368                  * orphan list in the first transaction => we need bitmap,
3369                  * group descriptor, sb, inode block, quota blocks, and
3370                  * possibly selinux xattr blocks.
3371                  */
3372                 credits = 4 + EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb) +
3373                           EXT4_XATTR_TRANS_BLOCKS;
3374         } else {
3375                 /*
3376                  * Fast symlink. We have to add entry to directory
3377                  * (EXT4_DATA_TRANS_BLOCKS + EXT4_INDEX_EXTRA_TRANS_BLOCKS),
3378                  * allocate new inode (bitmap, group descriptor, inode block,
3379                  * quota blocks, sb is already counted in previous macros).
3380                  */
3381                 credits = EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
3382                           EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3;
3383         }
3384
3385         inode = ext4_new_inode_start_handle(dir, S_IFLNK|S_IRWXUGO,
3386                                             &dentry->d_name, 0, NULL,
3387                                             EXT4_HT_DIR, credits);
3388         handle = ext4_journal_current_handle();
3389         if (IS_ERR(inode)) {
3390                 if (handle)
3391                         ext4_journal_stop(handle);
3392                 return PTR_ERR(inode);
3393         }
3394
3395         if (IS_ENCRYPTED(inode)) {
3396                 err = fscrypt_encrypt_symlink(inode, symname, len, &disk_link);
3397                 if (err)
3398                         goto err_drop_inode;
3399                 inode->i_op = &ext4_encrypted_symlink_inode_operations;
3400         }
3401
3402         if ((disk_link.len > EXT4_N_BLOCKS * 4)) {
3403                 if (!IS_ENCRYPTED(inode))
3404                         inode->i_op = &ext4_symlink_inode_operations;
3405                 inode_nohighmem(inode);
3406                 ext4_set_aops(inode);
3407                 /*
3408                  * We cannot call page_symlink() with transaction started
3409                  * because it calls into ext4_write_begin() which can wait
3410                  * for transaction commit if we are running out of space
3411                  * and thus we deadlock. So we have to stop transaction now
3412                  * and restart it when symlink contents is written.
3413                  *
3414                  * To keep fs consistent in case of crash, we have to put inode
3415                  * to orphan list in the mean time.
3416                  */
3417                 drop_nlink(inode);
3418                 err = ext4_orphan_add(handle, inode);
3419                 if (handle)
3420                         ext4_journal_stop(handle);
3421                 handle = NULL;
3422                 if (err)
3423                         goto err_drop_inode;
3424                 err = __page_symlink(inode, disk_link.name, disk_link.len, 1);
3425                 if (err)
3426                         goto err_drop_inode;
3427                 /*
3428                  * Now inode is being linked into dir (EXT4_DATA_TRANS_BLOCKS
3429                  * + EXT4_INDEX_EXTRA_TRANS_BLOCKS), inode is also modified
3430                  */
3431                 handle = ext4_journal_start(dir, EXT4_HT_DIR,
3432                                 EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
3433                                 EXT4_INDEX_EXTRA_TRANS_BLOCKS + 1);
3434                 if (IS_ERR(handle)) {
3435                         err = PTR_ERR(handle);
3436                         handle = NULL;
3437                         goto err_drop_inode;
3438                 }
3439                 set_nlink(inode, 1);
3440                 err = ext4_orphan_del(handle, inode);
3441                 if (err)
3442                         goto err_drop_inode;
3443         } else {
3444                 /* clear the extent format for fast symlink */
3445                 ext4_clear_inode_flag(inode, EXT4_INODE_EXTENTS);
3446                 if (!IS_ENCRYPTED(inode)) {
3447                         inode->i_op = &ext4_fast_symlink_inode_operations;
3448                         inode->i_link = (char *)&EXT4_I(inode)->i_data;
3449                 }
3450                 memcpy((char *)&EXT4_I(inode)->i_data, disk_link.name,
3451                        disk_link.len);
3452                 inode->i_size = disk_link.len - 1;
3453         }
3454         EXT4_I(inode)->i_disksize = inode->i_size;
3455         err = ext4_add_nondir(handle, dentry, &inode);
3456         if (handle)
3457                 ext4_journal_stop(handle);
3458         if (inode)
3459                 iput(inode);
3460         goto out_free_encrypted_link;
3461
3462 err_drop_inode:
3463         if (handle)
3464                 ext4_journal_stop(handle);
3465         clear_nlink(inode);
3466         unlock_new_inode(inode);
3467         iput(inode);
3468 out_free_encrypted_link:
3469         if (disk_link.name != (unsigned char *)symname)
3470                 kfree(disk_link.name);
3471         return err;
3472 }
3473
3474 int __ext4_link(struct inode *dir, struct inode *inode, struct dentry *dentry)
3475 {
3476         handle_t *handle;
3477         int err, retries = 0;
3478 retry:
3479         handle = ext4_journal_start(dir, EXT4_HT_DIR,
3480                 (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
3481                  EXT4_INDEX_EXTRA_TRANS_BLOCKS) + 1);
3482         if (IS_ERR(handle))
3483                 return PTR_ERR(handle);
3484
3485         if (IS_DIRSYNC(dir))
3486                 ext4_handle_sync(handle);
3487
3488         inode->i_ctime = current_time(inode);
3489         ext4_inc_count(inode);
3490         ihold(inode);
3491
3492         err = ext4_add_entry(handle, dentry, inode);
3493         if (!err) {
3494                 err = ext4_mark_inode_dirty(handle, inode);
3495                 /* this can happen only for tmpfile being
3496                  * linked the first time
3497                  */
3498                 if (inode->i_nlink == 1)
3499                         ext4_orphan_del(handle, inode);
3500                 d_instantiate(dentry, inode);
3501                 ext4_fc_track_link(handle, dentry);
3502         } else {
3503                 drop_nlink(inode);
3504                 iput(inode);
3505         }
3506         ext4_journal_stop(handle);
3507         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
3508                 goto retry;
3509         return err;
3510 }
3511
3512 static int ext4_link(struct dentry *old_dentry,
3513                      struct inode *dir, struct dentry *dentry)
3514 {
3515         struct inode *inode = d_inode(old_dentry);
3516         int err;
3517
3518         if (inode->i_nlink >= EXT4_LINK_MAX)
3519                 return -EMLINK;
3520
3521         err = fscrypt_prepare_link(old_dentry, dir, dentry);
3522         if (err)
3523                 return err;
3524
3525         if ((ext4_test_inode_flag(dir, EXT4_INODE_PROJINHERIT)) &&
3526             (!projid_eq(EXT4_I(dir)->i_projid,
3527                         EXT4_I(old_dentry->d_inode)->i_projid)))
3528                 return -EXDEV;
3529
3530         err = dquot_initialize(dir);
3531         if (err)
3532                 return err;
3533         return __ext4_link(dir, inode, dentry);
3534 }
3535
3536 /*
3537  * Try to find buffer head where contains the parent block.
3538  * It should be the inode block if it is inlined or the 1st block
3539  * if it is a normal dir.
3540  */
3541 static struct buffer_head *ext4_get_first_dir_block(handle_t *handle,
3542                                         struct inode *inode,
3543                                         int *retval,
3544                                         struct ext4_dir_entry_2 **parent_de,
3545                                         int *inlined)
3546 {
3547         struct buffer_head *bh;
3548
3549         if (!ext4_has_inline_data(inode)) {
3550                 struct ext4_dir_entry_2 *de;
3551                 unsigned int offset;
3552
3553                 /* The first directory block must not be a hole, so
3554                  * treat it as DIRENT_HTREE
3555                  */
3556                 bh = ext4_read_dirblock(inode, 0, DIRENT_HTREE);
3557                 if (IS_ERR(bh)) {
3558                         *retval = PTR_ERR(bh);
3559                         return NULL;
3560                 }
3561
3562                 de = (struct ext4_dir_entry_2 *) bh->b_data;
3563                 if (ext4_check_dir_entry(inode, NULL, de, bh, bh->b_data,
3564                                          bh->b_size, 0) ||
3565                     le32_to_cpu(de->inode) != inode->i_ino ||
3566                     strcmp(".", de->name)) {
3567                         EXT4_ERROR_INODE(inode, "directory missing '.'");
3568                         brelse(bh);
3569                         *retval = -EFSCORRUPTED;
3570                         return NULL;
3571                 }
3572                 offset = ext4_rec_len_from_disk(de->rec_len,
3573                                                 inode->i_sb->s_blocksize);
3574                 de = ext4_next_entry(de, inode->i_sb->s_blocksize);
3575                 if (ext4_check_dir_entry(inode, NULL, de, bh, bh->b_data,
3576                                          bh->b_size, offset) ||
3577                     le32_to_cpu(de->inode) == 0 || strcmp("..", de->name)) {
3578                         EXT4_ERROR_INODE(inode, "directory missing '..'");
3579                         brelse(bh);
3580                         *retval = -EFSCORRUPTED;
3581                         return NULL;
3582                 }
3583                 *parent_de = de;
3584
3585                 return bh;
3586         }
3587
3588         *inlined = 1;
3589         return ext4_get_first_inline_block(inode, parent_de, retval);
3590 }
3591
3592 struct ext4_renament {
3593         struct inode *dir;
3594         struct dentry *dentry;
3595         struct inode *inode;
3596         bool is_dir;
3597         int dir_nlink_delta;
3598
3599         /* entry for "dentry" */
3600         struct buffer_head *bh;
3601         struct ext4_dir_entry_2 *de;
3602         int inlined;
3603
3604         /* entry for ".." in inode if it's a directory */
3605         struct buffer_head *dir_bh;
3606         struct ext4_dir_entry_2 *parent_de;
3607         int dir_inlined;
3608 };
3609
3610 static int ext4_rename_dir_prepare(handle_t *handle, struct ext4_renament *ent)
3611 {
3612         int retval;
3613
3614         ent->dir_bh = ext4_get_first_dir_block(handle, ent->inode,
3615                                               &retval, &ent->parent_de,
3616                                               &ent->dir_inlined);
3617         if (!ent->dir_bh)
3618                 return retval;
3619         if (le32_to_cpu(ent->parent_de->inode) != ent->dir->i_ino)
3620                 return -EFSCORRUPTED;
3621         BUFFER_TRACE(ent->dir_bh, "get_write_access");
3622         return ext4_journal_get_write_access(handle, ent->dir_bh);
3623 }
3624
3625 static int ext4_rename_dir_finish(handle_t *handle, struct ext4_renament *ent,
3626                                   unsigned dir_ino)
3627 {
3628         int retval;
3629
3630         ent->parent_de->inode = cpu_to_le32(dir_ino);
3631         BUFFER_TRACE(ent->dir_bh, "call ext4_handle_dirty_metadata");
3632         if (!ent->dir_inlined) {
3633                 if (is_dx(ent->inode)) {
3634                         retval = ext4_handle_dirty_dx_node(handle,
3635                                                            ent->inode,
3636                                                            ent->dir_bh);
3637                 } else {
3638                         retval = ext4_handle_dirty_dirblock(handle, ent->inode,
3639                                                             ent->dir_bh);
3640                 }
3641         } else {
3642                 retval = ext4_mark_inode_dirty(handle, ent->inode);
3643         }
3644         if (retval) {
3645                 ext4_std_error(ent->dir->i_sb, retval);
3646                 return retval;
3647         }
3648         return 0;
3649 }
3650
3651 static int ext4_setent(handle_t *handle, struct ext4_renament *ent,
3652                        unsigned ino, unsigned file_type)
3653 {
3654         int retval, retval2;
3655
3656         BUFFER_TRACE(ent->bh, "get write access");
3657         retval = ext4_journal_get_write_access(handle, ent->bh);
3658         if (retval)
3659                 return retval;
3660         ent->de->inode = cpu_to_le32(ino);
3661         if (ext4_has_feature_filetype(ent->dir->i_sb))
3662                 ent->de->file_type = file_type;
3663         inode_inc_iversion(ent->dir);
3664         ent->dir->i_ctime = ent->dir->i_mtime =
3665                 current_time(ent->dir);
3666         retval = ext4_mark_inode_dirty(handle, ent->dir);
3667         BUFFER_TRACE(ent->bh, "call ext4_handle_dirty_metadata");
3668         if (!ent->inlined) {
3669                 retval2 = ext4_handle_dirty_dirblock(handle, ent->dir, ent->bh);
3670                 if (unlikely(retval2)) {
3671                         ext4_std_error(ent->dir->i_sb, retval2);
3672                         return retval2;
3673                 }
3674         }
3675         return retval;
3676 }
3677
3678 static void ext4_resetent(handle_t *handle, struct ext4_renament *ent,
3679                           unsigned ino, unsigned file_type)
3680 {
3681         struct ext4_renament old = *ent;
3682         int retval = 0;
3683
3684         /*
3685          * old->de could have moved from under us during make indexed dir,
3686          * so the old->de may no longer valid and need to find it again
3687          * before reset old inode info.
3688          */
3689         old.bh = ext4_find_entry(old.dir, &old.dentry->d_name, &old.de, NULL);
3690         if (IS_ERR(old.bh))
3691                 retval = PTR_ERR(old.bh);
3692         if (!old.bh)
3693                 retval = -ENOENT;
3694         if (retval) {
3695                 ext4_std_error(old.dir->i_sb, retval);
3696                 return;
3697         }
3698
3699         ext4_setent(handle, &old, ino, file_type);
3700         brelse(old.bh);
3701 }
3702
3703 static int ext4_find_delete_entry(handle_t *handle, struct inode *dir,
3704                                   const struct qstr *d_name)
3705 {
3706         int retval = -ENOENT;
3707         struct buffer_head *bh;
3708         struct ext4_dir_entry_2 *de;
3709
3710         bh = ext4_find_entry(dir, d_name, &de, NULL);
3711         if (IS_ERR(bh))
3712                 return PTR_ERR(bh);
3713         if (bh) {
3714                 retval = ext4_delete_entry(handle, dir, de, bh);
3715                 brelse(bh);
3716         }
3717         return retval;
3718 }
3719
3720 static void ext4_rename_delete(handle_t *handle, struct ext4_renament *ent,
3721                                int force_reread)
3722 {
3723         int retval;
3724         /*
3725          * ent->de could have moved from under us during htree split, so make
3726          * sure that we are deleting the right entry.  We might also be pointing
3727          * to a stale entry in the unused part of ent->bh so just checking inum
3728          * and the name isn't enough.
3729          */
3730         if (le32_to_cpu(ent->de->inode) != ent->inode->i_ino ||
3731             ent->de->name_len != ent->dentry->d_name.len ||
3732             strncmp(ent->de->name, ent->dentry->d_name.name,
3733                     ent->de->name_len) ||
3734             force_reread) {
3735                 retval = ext4_find_delete_entry(handle, ent->dir,
3736                                                 &ent->dentry->d_name);
3737         } else {
3738                 retval = ext4_delete_entry(handle, ent->dir, ent->de, ent->bh);
3739                 if (retval == -ENOENT) {
3740                         retval = ext4_find_delete_entry(handle, ent->dir,
3741                                                         &ent->dentry->d_name);
3742                 }
3743         }
3744
3745         if (retval) {
3746                 ext4_warning_inode(ent->dir,
3747                                    "Deleting old file: nlink %d, error=%d",
3748                                    ent->dir->i_nlink, retval);
3749         }
3750 }
3751
3752 static void ext4_update_dir_count(handle_t *handle, struct ext4_renament *ent)
3753 {
3754         if (ent->dir_nlink_delta) {
3755                 if (ent->dir_nlink_delta == -1)
3756                         ext4_dec_count(ent->dir);
3757                 else
3758                         ext4_inc_count(ent->dir);
3759                 ext4_mark_inode_dirty(handle, ent->dir);
3760         }
3761 }
3762
3763 static struct inode *ext4_whiteout_for_rename(struct ext4_renament *ent,
3764                                               int credits, handle_t **h)
3765 {
3766         struct inode *wh;
3767         handle_t *handle;
3768         int retries = 0;
3769
3770         /*
3771          * for inode block, sb block, group summaries,
3772          * and inode bitmap
3773          */
3774         credits += (EXT4_MAXQUOTAS_TRANS_BLOCKS(ent->dir->i_sb) +
3775                     EXT4_XATTR_TRANS_BLOCKS + 4);
3776 retry:
3777         wh = ext4_new_inode_start_handle(ent->dir, S_IFCHR | WHITEOUT_MODE,
3778                                          &ent->dentry->d_name, 0, NULL,
3779                                          EXT4_HT_DIR, credits);
3780
3781         handle = ext4_journal_current_handle();
3782         if (IS_ERR(wh)) {
3783                 if (handle)
3784                         ext4_journal_stop(handle);
3785                 if (PTR_ERR(wh) == -ENOSPC &&
3786                     ext4_should_retry_alloc(ent->dir->i_sb, &retries))
3787                         goto retry;
3788         } else {
3789                 *h = handle;
3790                 init_special_inode(wh, wh->i_mode, WHITEOUT_DEV);
3791                 wh->i_op = &ext4_special_inode_operations;
3792         }
3793         return wh;
3794 }
3795
3796 /*
3797  * Anybody can rename anything with this: the permission checks are left to the
3798  * higher-level routines.
3799  *
3800  * n.b.  old_{dentry,inode) refers to the source dentry/inode
3801  * while new_{dentry,inode) refers to the destination dentry/inode
3802  * This comes from rename(const char *oldpath, const char *newpath)
3803  */
3804 static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry,
3805                        struct inode *new_dir, struct dentry *new_dentry,
3806                        unsigned int flags)
3807 {
3808         handle_t *handle = NULL;
3809         struct ext4_renament old = {
3810                 .dir = old_dir,
3811                 .dentry = old_dentry,
3812                 .inode = d_inode(old_dentry),
3813         };
3814         struct ext4_renament new = {
3815                 .dir = new_dir,
3816                 .dentry = new_dentry,
3817                 .inode = d_inode(new_dentry),
3818         };
3819         int force_reread;
3820         int retval;
3821         struct inode *whiteout = NULL;
3822         int credits;
3823         u8 old_file_type;
3824
3825         if (new.inode && new.inode->i_nlink == 0) {
3826                 EXT4_ERROR_INODE(new.inode,
3827                                  "target of rename is already freed");
3828                 return -EFSCORRUPTED;
3829         }
3830
3831         if ((ext4_test_inode_flag(new_dir, EXT4_INODE_PROJINHERIT)) &&
3832             (!projid_eq(EXT4_I(new_dir)->i_projid,
3833                         EXT4_I(old_dentry->d_inode)->i_projid)))
3834                 return -EXDEV;
3835
3836         retval = dquot_initialize(old.dir);
3837         if (retval)
3838                 return retval;
3839         retval = dquot_initialize(new.dir);
3840         if (retval)
3841                 return retval;
3842
3843         /* Initialize quotas before so that eventual writes go
3844          * in separate transaction */
3845         if (new.inode) {
3846                 retval = dquot_initialize(new.inode);
3847                 if (retval)
3848                         return retval;
3849         }
3850
3851         old.bh = ext4_find_entry(old.dir, &old.dentry->d_name, &old.de, NULL);
3852         if (IS_ERR(old.bh))
3853                 return PTR_ERR(old.bh);
3854         /*
3855          *  Check for inode number is _not_ due to possible IO errors.
3856          *  We might rmdir the source, keep it as pwd of some process
3857          *  and merrily kill the link to whatever was created under the
3858          *  same name. Goodbye sticky bit ;-<
3859          */
3860         retval = -ENOENT;
3861         if (!old.bh || le32_to_cpu(old.de->inode) != old.inode->i_ino)
3862                 goto release_bh;
3863
3864         new.bh = ext4_find_entry(new.dir, &new.dentry->d_name,
3865                                  &new.de, &new.inlined);
3866         if (IS_ERR(new.bh)) {
3867                 retval = PTR_ERR(new.bh);
3868                 new.bh = NULL;
3869                 goto release_bh;
3870         }
3871         if (new.bh) {
3872                 if (!new.inode) {
3873                         brelse(new.bh);
3874                         new.bh = NULL;
3875                 }
3876         }
3877         if (new.inode && !test_opt(new.dir->i_sb, NO_AUTO_DA_ALLOC))
3878                 ext4_alloc_da_blocks(old.inode);
3879
3880         credits = (2 * EXT4_DATA_TRANS_BLOCKS(old.dir->i_sb) +
3881                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2);
3882         if (!(flags & RENAME_WHITEOUT)) {
3883                 handle = ext4_journal_start(old.dir, EXT4_HT_DIR, credits);
3884                 if (IS_ERR(handle)) {
3885                         retval = PTR_ERR(handle);
3886                         goto release_bh;
3887                 }
3888         } else {
3889                 whiteout = ext4_whiteout_for_rename(&old, credits, &handle);
3890                 if (IS_ERR(whiteout)) {
3891                         retval = PTR_ERR(whiteout);
3892                         goto release_bh;
3893                 }
3894         }
3895
3896         old_file_type = old.de->file_type;
3897         if (IS_DIRSYNC(old.dir) || IS_DIRSYNC(new.dir))
3898                 ext4_handle_sync(handle);
3899
3900         if (S_ISDIR(old.inode->i_mode)) {
3901                 if (new.inode) {
3902                         retval = -ENOTEMPTY;
3903                         if (!ext4_empty_dir(new.inode))
3904                                 goto end_rename;
3905                 } else {
3906                         retval = -EMLINK;
3907                         if (new.dir != old.dir && EXT4_DIR_LINK_MAX(new.dir))
3908                                 goto end_rename;
3909                 }
3910                 retval = ext4_rename_dir_prepare(handle, &old);
3911                 if (retval)
3912                         goto end_rename;
3913         }
3914         /*
3915          * If we're renaming a file within an inline_data dir and adding or
3916          * setting the new dirent causes a conversion from inline_data to
3917          * extents/blockmap, we need to force the dirent delete code to
3918          * re-read the directory, or else we end up trying to delete a dirent
3919          * from what is now the extent tree root (or a block map).
3920          */
3921         force_reread = (new.dir->i_ino == old.dir->i_ino &&
3922                         ext4_test_inode_flag(new.dir, EXT4_INODE_INLINE_DATA));
3923
3924         if (whiteout) {
3925                 /*
3926                  * Do this before adding a new entry, so the old entry is sure
3927                  * to be still pointing to the valid old entry.
3928                  */
3929                 retval = ext4_setent(handle, &old, whiteout->i_ino,
3930                                      EXT4_FT_CHRDEV);
3931                 if (retval)
3932                         goto end_rename;
3933                 retval = ext4_mark_inode_dirty(handle, whiteout);
3934                 if (unlikely(retval))
3935                         goto end_rename;
3936
3937         }
3938         if (!new.bh) {
3939                 retval = ext4_add_entry(handle, new.dentry, old.inode);
3940                 if (retval)
3941                         goto end_rename;
3942         } else {
3943                 retval = ext4_setent(handle, &new,
3944                                      old.inode->i_ino, old_file_type);
3945                 if (retval)
3946                         goto end_rename;
3947         }
3948         if (force_reread)
3949                 force_reread = !ext4_test_inode_flag(new.dir,
3950                                                      EXT4_INODE_INLINE_DATA);
3951
3952         /*
3953          * Like most other Unix systems, set the ctime for inodes on a
3954          * rename.
3955          */
3956         old.inode->i_ctime = current_time(old.inode);
3957         retval = ext4_mark_inode_dirty(handle, old.inode);
3958         if (unlikely(retval))
3959                 goto end_rename;
3960
3961         if (!whiteout) {
3962                 /*
3963                  * ok, that's it
3964                  */
3965                 ext4_rename_delete(handle, &old, force_reread);
3966         }
3967
3968         if (new.inode) {
3969                 ext4_dec_count(new.inode);
3970                 new.inode->i_ctime = current_time(new.inode);
3971         }
3972         old.dir->i_ctime = old.dir->i_mtime = current_time(old.dir);
3973         ext4_update_dx_flag(old.dir);
3974         if (old.dir_bh) {
3975                 retval = ext4_rename_dir_finish(handle, &old, new.dir->i_ino);
3976                 if (retval)
3977                         goto end_rename;
3978
3979                 ext4_dec_count(old.dir);
3980                 if (new.inode) {
3981                         /* checked ext4_empty_dir above, can't have another
3982                          * parent, ext4_dec_count() won't work for many-linked
3983                          * dirs */
3984                         clear_nlink(new.inode);
3985                 } else {
3986                         ext4_inc_count(new.dir);
3987                         ext4_update_dx_flag(new.dir);
3988                         retval = ext4_mark_inode_dirty(handle, new.dir);
3989                         if (unlikely(retval))
3990                                 goto end_rename;
3991                 }
3992         }
3993         retval = ext4_mark_inode_dirty(handle, old.dir);
3994         if (unlikely(retval))
3995                 goto end_rename;
3996
3997         if (S_ISDIR(old.inode->i_mode)) {
3998                 /*
3999                  * We disable fast commits here that's because the
4000                  * replay code is not yet capable of changing dot dot
4001                  * dirents in directories.
4002                  */
4003                 ext4_fc_mark_ineligible(old.inode->i_sb,
4004                         EXT4_FC_REASON_RENAME_DIR);
4005         } else {
4006                 if (new.inode)
4007                         ext4_fc_track_unlink(handle, new.dentry);
4008                 __ext4_fc_track_link(handle, old.inode, new.dentry);
4009                 __ext4_fc_track_unlink(handle, old.inode, old.dentry);
4010                 if (whiteout)
4011                         __ext4_fc_track_create(handle, whiteout, old.dentry);
4012         }
4013
4014         if (new.inode) {
4015                 retval = ext4_mark_inode_dirty(handle, new.inode);
4016                 if (unlikely(retval))
4017                         goto end_rename;
4018                 if (!new.inode->i_nlink)
4019                         ext4_orphan_add(handle, new.inode);
4020         }
4021         retval = 0;
4022
4023 end_rename:
4024         if (whiteout) {
4025                 if (retval) {
4026                         ext4_resetent(handle, &old,
4027                                       old.inode->i_ino, old_file_type);
4028                         drop_nlink(whiteout);
4029                         ext4_orphan_add(handle, whiteout);
4030                 }
4031                 unlock_new_inode(whiteout);
4032                 ext4_journal_stop(handle);
4033                 iput(whiteout);
4034         } else {
4035                 ext4_journal_stop(handle);
4036         }
4037 release_bh:
4038         brelse(old.dir_bh);
4039         brelse(old.bh);
4040         brelse(new.bh);
4041         return retval;
4042 }
4043
4044 static int ext4_cross_rename(struct inode *old_dir, struct dentry *old_dentry,
4045                              struct inode *new_dir, struct dentry *new_dentry)
4046 {
4047         handle_t *handle = NULL;
4048         struct ext4_renament old = {
4049                 .dir = old_dir,
4050                 .dentry = old_dentry,
4051                 .inode = d_inode(old_dentry),
4052         };
4053         struct ext4_renament new = {
4054                 .dir = new_dir,
4055                 .dentry = new_dentry,
4056                 .inode = d_inode(new_dentry),
4057         };
4058         u8 new_file_type;
4059         int retval;
4060         struct timespec64 ctime;
4061
4062         if ((ext4_test_inode_flag(new_dir, EXT4_INODE_PROJINHERIT) &&
4063              !projid_eq(EXT4_I(new_dir)->i_projid,
4064                         EXT4_I(old_dentry->d_inode)->i_projid)) ||
4065             (ext4_test_inode_flag(old_dir, EXT4_INODE_PROJINHERIT) &&
4066              !projid_eq(EXT4_I(old_dir)->i_projid,
4067                         EXT4_I(new_dentry->d_inode)->i_projid)))
4068                 return -EXDEV;
4069
4070         retval = dquot_initialize(old.dir);
4071         if (retval)
4072                 return retval;
4073         retval = dquot_initialize(new.dir);
4074         if (retval)
4075                 return retval;
4076
4077         old.bh = ext4_find_entry(old.dir, &old.dentry->d_name,
4078                                  &old.de, &old.inlined);
4079         if (IS_ERR(old.bh))
4080                 return PTR_ERR(old.bh);
4081         /*
4082          *  Check for inode number is _not_ due to possible IO errors.
4083          *  We might rmdir the source, keep it as pwd of some process
4084          *  and merrily kill the link to whatever was created under the
4085          *  same name. Goodbye sticky bit ;-<
4086          */
4087         retval = -ENOENT;
4088         if (!old.bh || le32_to_cpu(old.de->inode) != old.inode->i_ino)
4089                 goto end_rename;
4090
4091         new.bh = ext4_find_entry(new.dir, &new.dentry->d_name,
4092                                  &new.de, &new.inlined);
4093         if (IS_ERR(new.bh)) {
4094                 retval = PTR_ERR(new.bh);
4095                 new.bh = NULL;
4096                 goto end_rename;
4097         }
4098
4099         /* RENAME_EXCHANGE case: old *and* new must both exist */
4100         if (!new.bh || le32_to_cpu(new.de->inode) != new.inode->i_ino)
4101                 goto end_rename;
4102
4103         handle = ext4_journal_start(old.dir, EXT4_HT_DIR,
4104                 (2 * EXT4_DATA_TRANS_BLOCKS(old.dir->i_sb) +
4105                  2 * EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2));
4106         if (IS_ERR(handle)) {
4107                 retval = PTR_ERR(handle);
4108                 handle = NULL;
4109                 goto end_rename;
4110         }
4111
4112         if (IS_DIRSYNC(old.dir) || IS_DIRSYNC(new.dir))
4113                 ext4_handle_sync(handle);
4114
4115         if (S_ISDIR(old.inode->i_mode)) {
4116                 old.is_dir = true;
4117                 retval = ext4_rename_dir_prepare(handle, &old);
4118                 if (retval)
4119                         goto end_rename;
4120         }
4121         if (S_ISDIR(new.inode->i_mode)) {
4122                 new.is_dir = true;
4123                 retval = ext4_rename_dir_prepare(handle, &new);
4124                 if (retval)
4125                         goto end_rename;
4126         }
4127
4128         /*
4129          * Other than the special case of overwriting a directory, parents'
4130          * nlink only needs to be modified if this is a cross directory rename.
4131          */
4132         if (old.dir != new.dir && old.is_dir != new.is_dir) {
4133                 old.dir_nlink_delta = old.is_dir ? -1 : 1;
4134                 new.dir_nlink_delta = -old.dir_nlink_delta;
4135                 retval = -EMLINK;
4136                 if ((old.dir_nlink_delta > 0 && EXT4_DIR_LINK_MAX(old.dir)) ||
4137                     (new.dir_nlink_delta > 0 && EXT4_DIR_LINK_MAX(new.dir)))
4138                         goto end_rename;
4139         }
4140
4141         new_file_type = new.de->file_type;
4142         retval = ext4_setent(handle, &new, old.inode->i_ino, old.de->file_type);
4143         if (retval)
4144                 goto end_rename;
4145
4146         retval = ext4_setent(handle, &old, new.inode->i_ino, new_file_type);
4147         if (retval)
4148                 goto end_rename;
4149
4150         /*
4151          * Like most other Unix systems, set the ctime for inodes on a
4152          * rename.
4153          */
4154         ctime = current_time(old.inode);
4155         old.inode->i_ctime = ctime;
4156         new.inode->i_ctime = ctime;
4157         retval = ext4_mark_inode_dirty(handle, old.inode);
4158         if (unlikely(retval))
4159                 goto end_rename;
4160         retval = ext4_mark_inode_dirty(handle, new.inode);
4161         if (unlikely(retval))
4162                 goto end_rename;
4163         ext4_fc_mark_ineligible(new.inode->i_sb,
4164                                 EXT4_FC_REASON_CROSS_RENAME);
4165         if (old.dir_bh) {
4166                 retval = ext4_rename_dir_finish(handle, &old, new.dir->i_ino);
4167                 if (retval)
4168                         goto end_rename;
4169         }
4170         if (new.dir_bh) {
4171                 retval = ext4_rename_dir_finish(handle, &new, old.dir->i_ino);
4172                 if (retval)
4173                         goto end_rename;
4174         }
4175         ext4_update_dir_count(handle, &old);
4176         ext4_update_dir_count(handle, &new);
4177         retval = 0;
4178
4179 end_rename:
4180         brelse(old.dir_bh);
4181         brelse(new.dir_bh);
4182         brelse(old.bh);
4183         brelse(new.bh);
4184         if (handle)
4185                 ext4_journal_stop(handle);
4186         return retval;
4187 }
4188
4189 static int ext4_rename2(struct inode *old_dir, struct dentry *old_dentry,
4190                         struct inode *new_dir, struct dentry *new_dentry,
4191                         unsigned int flags)
4192 {
4193         int err;
4194
4195         if (unlikely(ext4_forced_shutdown(EXT4_SB(old_dir->i_sb))))
4196                 return -EIO;
4197
4198         if (flags & ~(RENAME_NOREPLACE | RENAME_EXCHANGE | RENAME_WHITEOUT))
4199                 return -EINVAL;
4200
4201         err = fscrypt_prepare_rename(old_dir, old_dentry, new_dir, new_dentry,
4202                                      flags);
4203         if (err)
4204                 return err;
4205
4206         if (flags & RENAME_EXCHANGE) {
4207                 return ext4_cross_rename(old_dir, old_dentry,
4208                                          new_dir, new_dentry);
4209         }
4210
4211         return ext4_rename(old_dir, old_dentry, new_dir, new_dentry, flags);
4212 }
4213
4214 /*
4215  * directories can handle most operations...
4216  */
4217 const struct inode_operations ext4_dir_inode_operations = {
4218         .create         = ext4_create,
4219         .lookup         = ext4_lookup,
4220         .link           = ext4_link,
4221         .unlink         = ext4_unlink,
4222         .symlink        = ext4_symlink,
4223         .mkdir          = ext4_mkdir,
4224         .rmdir          = ext4_rmdir,
4225         .mknod          = ext4_mknod,
4226         .tmpfile        = ext4_tmpfile,
4227         .rename         = ext4_rename2,
4228         .setattr        = ext4_setattr,
4229         .getattr        = ext4_getattr,
4230         .listxattr      = ext4_listxattr,
4231         .get_acl        = ext4_get_acl,
4232         .set_acl        = ext4_set_acl,
4233         .fiemap         = ext4_fiemap,
4234 };
4235
4236 const struct inode_operations ext4_special_inode_operations = {
4237         .setattr        = ext4_setattr,
4238         .getattr        = ext4_getattr,
4239         .listxattr      = ext4_listxattr,
4240         .get_acl        = ext4_get_acl,
4241         .set_acl        = ext4_set_acl,
4242 };