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