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