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