1 // SPDX-License-Identifier: GPL-2.0
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)
12 * linux/fs/minix/dir.c
14 * Copyright (C) 1991, 1992 Linus Torvalds
16 * ext4 directory handling functions
18 * Big-endian to little-endian byte-swapping/bitmaps by
19 * David S. Miller (davem@caip.rutgers.edu), 1995
21 * Hash Tree Directory indexing (c) 2001 Daniel Phillips
26 #include <linux/buffer_head.h>
27 #include <linux/slab.h>
28 #include <linux/iversion.h>
29 #include <linux/unicode.h>
33 static int ext4_dx_readdir(struct file
*, struct dir_context
*);
36 * is_dx_dir() - check if a directory is using htree indexing
37 * @inode: directory inode
39 * Check if the given dir-inode refers to an htree-indexed directory
40 * (or a directory which could potentially get converted to use htree
43 * Return 1 if it is a dx dir, 0 if not
45 static int is_dx_dir(struct inode
*inode
)
47 struct super_block
*sb
= inode
->i_sb
;
49 if (ext4_has_feature_dir_index(inode
->i_sb
) &&
50 ((ext4_test_inode_flag(inode
, EXT4_INODE_INDEX
)) ||
51 ((inode
->i_size
>> sb
->s_blocksize_bits
) == 1) ||
52 ext4_has_inline_data(inode
)))
58 static bool is_fake_dir_entry(struct ext4_dir_entry_2
*de
)
60 /* Check if . or .. , or skip if namelen is 0 */
61 if ((de
->name_len
> 0) && (de
->name_len
<= 2) && (de
->name
[0] == '.') &&
62 (de
->name
[1] == '.' || de
->name
[1] == '\0'))
64 /* Check if this is a csum entry */
65 if (de
->file_type
== EXT4_FT_DIR_CSUM
)
71 * Return 0 if the directory entry is OK, and 1 if there is a problem
73 * Note: this is the opposite of what ext2 and ext3 historically returned...
75 * bh passed here can be an inode block or a dir data block, depending
76 * on the inode inline data flag.
78 int __ext4_check_dir_entry(const char *function
, unsigned int line
,
79 struct inode
*dir
, struct file
*filp
,
80 struct ext4_dir_entry_2
*de
,
81 struct buffer_head
*bh
, char *buf
, int size
,
84 const char *error_msg
= NULL
;
85 const int rlen
= ext4_rec_len_from_disk(de
->rec_len
,
86 dir
->i_sb
->s_blocksize
);
87 const int next_offset
= ((char *) de
- buf
) + rlen
;
88 bool fake
= is_fake_dir_entry(de
);
89 bool has_csum
= ext4_has_metadata_csum(dir
->i_sb
);
91 if (unlikely(rlen
< ext4_dir_rec_len(1, fake
? NULL
: dir
)))
92 error_msg
= "rec_len is smaller than minimal";
93 else if (unlikely(rlen
% 4 != 0))
94 error_msg
= "rec_len % 4 != 0";
95 else if (unlikely(rlen
< ext4_dir_rec_len(de
->name_len
,
97 error_msg
= "rec_len is too small for name_len";
98 else if (unlikely(next_offset
> size
))
99 error_msg
= "directory entry overrun";
100 else if (unlikely(next_offset
> size
- ext4_dir_rec_len(1,
101 has_csum
? NULL
: dir
) &&
102 next_offset
!= size
))
103 error_msg
= "directory entry too close to block end";
104 else if (unlikely(le32_to_cpu(de
->inode
) >
105 le32_to_cpu(EXT4_SB(dir
->i_sb
)->s_es
->s_inodes_count
)))
106 error_msg
= "inode out of bounds";
111 ext4_error_file(filp
, function
, line
, bh
->b_blocknr
,
112 "bad entry in directory: %s - offset=%u, "
113 "inode=%u, rec_len=%d, size=%d fake=%d",
114 error_msg
, offset
, le32_to_cpu(de
->inode
),
117 ext4_error_inode(dir
, function
, line
, bh
->b_blocknr
,
118 "bad entry in directory: %s - offset=%u, "
119 "inode=%u, rec_len=%d, size=%d fake=%d",
120 error_msg
, offset
, le32_to_cpu(de
->inode
),
126 static int ext4_readdir(struct file
*file
, struct dir_context
*ctx
)
130 struct ext4_dir_entry_2
*de
;
132 struct inode
*inode
= file_inode(file
);
133 struct super_block
*sb
= inode
->i_sb
;
134 struct buffer_head
*bh
= NULL
;
135 struct fscrypt_str fstr
= FSTR_INIT(NULL
, 0);
137 err
= fscrypt_prepare_readdir(inode
);
141 if (is_dx_dir(inode
)) {
142 err
= ext4_dx_readdir(file
, ctx
);
143 if (err
!= ERR_BAD_DX_DIR
)
146 /* Can we just clear INDEX flag to ignore htree information? */
147 if (!ext4_has_metadata_csum(sb
)) {
149 * We don't set the inode dirty flag since it's not
150 * critical that it gets flushed back to the disk.
152 ext4_clear_inode_flag(inode
, EXT4_INODE_INDEX
);
156 if (ext4_has_inline_data(inode
)) {
157 int has_inline_data
= 1;
158 err
= ext4_read_inline_dir(file
, ctx
,
164 if (IS_ENCRYPTED(inode
)) {
165 err
= fscrypt_fname_alloc_buffer(EXT4_NAME_LEN
, &fstr
);
170 while (ctx
->pos
< inode
->i_size
) {
171 struct ext4_map_blocks map
;
173 if (fatal_signal_pending(current
)) {
178 offset
= ctx
->pos
& (sb
->s_blocksize
- 1);
179 map
.m_lblk
= ctx
->pos
>> EXT4_BLOCK_SIZE_BITS(sb
);
181 err
= ext4_map_blocks(NULL
, inode
, &map
, 0);
183 /* m_len should never be zero but let's avoid
184 * an infinite loop if it somehow is */
187 ctx
->pos
+= map
.m_len
* sb
->s_blocksize
;
191 pgoff_t index
= map
.m_pblk
>>
192 (PAGE_SHIFT
- inode
->i_blkbits
);
193 if (!ra_has_index(&file
->f_ra
, index
))
194 page_cache_sync_readahead(
195 sb
->s_bdev
->bd_inode
->i_mapping
,
198 file
->f_ra
.prev_pos
= (loff_t
)index
<< PAGE_SHIFT
;
199 bh
= ext4_bread(NULL
, inode
, map
.m_lblk
, 0);
208 /* corrupt size? Maybe no more blocks to read */
209 if (ctx
->pos
> inode
->i_blocks
<< 9)
211 ctx
->pos
+= sb
->s_blocksize
- offset
;
215 /* Check the checksum */
216 if (!buffer_verified(bh
) &&
217 !ext4_dirblock_csum_verify(inode
, bh
)) {
218 EXT4_ERROR_FILE(file
, 0, "directory fails checksum "
220 (unsigned long long)ctx
->pos
);
221 ctx
->pos
+= sb
->s_blocksize
- offset
;
226 set_buffer_verified(bh
);
228 /* If the dir block has changed since the last call to
229 * readdir(2), then we might be pointing to an invalid
230 * dirent right now. Scan from the start of the block
232 if (!inode_eq_iversion(inode
, file
->f_version
)) {
233 for (i
= 0; i
< sb
->s_blocksize
&& i
< offset
; ) {
234 de
= (struct ext4_dir_entry_2
*)
236 /* It's too expensive to do a full
237 * dirent test each time round this
238 * loop, but we do have to test at
239 * least that it is non-zero. A
240 * failure will be detected in the
241 * dirent test below. */
242 if (ext4_rec_len_from_disk(de
->rec_len
,
243 sb
->s_blocksize
) < ext4_dir_rec_len(1,
246 i
+= ext4_rec_len_from_disk(de
->rec_len
,
250 ctx
->pos
= (ctx
->pos
& ~(sb
->s_blocksize
- 1))
252 file
->f_version
= inode_query_iversion(inode
);
255 while (ctx
->pos
< inode
->i_size
256 && offset
< sb
->s_blocksize
) {
257 de
= (struct ext4_dir_entry_2
*) (bh
->b_data
+ offset
);
258 if (ext4_check_dir_entry(inode
, file
, de
, bh
,
259 bh
->b_data
, bh
->b_size
,
262 * On error, skip to the next block
264 ctx
->pos
= (ctx
->pos
|
265 (sb
->s_blocksize
- 1)) + 1;
268 offset
+= ext4_rec_len_from_disk(de
->rec_len
,
270 if (le32_to_cpu(de
->inode
)) {
271 if (!IS_ENCRYPTED(inode
)) {
272 if (!dir_emit(ctx
, de
->name
,
274 le32_to_cpu(de
->inode
),
275 get_dtype(sb
, de
->file_type
)))
278 int save_len
= fstr
.len
;
279 struct fscrypt_str de_name
=
283 /* Directory is encrypted */
284 err
= fscrypt_fname_disk_to_usr(inode
,
285 EXT4_DIRENT_HASH(de
),
286 EXT4_DIRENT_MINOR_HASH(de
),
293 de_name
.name
, de_name
.len
,
294 le32_to_cpu(de
->inode
),
295 get_dtype(sb
, de
->file_type
)))
299 ctx
->pos
+= ext4_rec_len_from_disk(de
->rec_len
,
302 if ((ctx
->pos
< inode
->i_size
) && !dir_relax_shared(inode
))
311 fscrypt_fname_free_buffer(&fstr
);
316 static inline int is_32bit_api(void)
319 return in_compat_syscall();
321 return (BITS_PER_LONG
== 32);
326 * These functions convert from the major/minor hash to an f_pos
327 * value for dx directories
329 * Upper layer (for example NFS) should specify FMODE_32BITHASH or
330 * FMODE_64BITHASH explicitly. On the other hand, we allow ext4 to be mounted
331 * directly on both 32-bit and 64-bit nodes, under such case, neither
332 * FMODE_32BITHASH nor FMODE_64BITHASH is specified.
334 static inline loff_t
hash2pos(struct file
*filp
, __u32 major
, __u32 minor
)
336 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
337 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
340 return ((__u64
)(major
>> 1) << 32) | (__u64
)minor
;
343 static inline __u32
pos2maj_hash(struct file
*filp
, loff_t pos
)
345 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
346 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
347 return (pos
<< 1) & 0xffffffff;
349 return ((pos
>> 32) << 1) & 0xffffffff;
352 static inline __u32
pos2min_hash(struct file
*filp
, loff_t pos
)
354 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
355 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
358 return pos
& 0xffffffff;
362 * Return 32- or 64-bit end-of-file for dx directories
364 static inline loff_t
ext4_get_htree_eof(struct file
*filp
)
366 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
367 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
368 return EXT4_HTREE_EOF_32BIT
;
370 return EXT4_HTREE_EOF_64BIT
;
375 * ext4_dir_llseek() calls generic_file_llseek_size to handle htree
376 * directories, where the "offset" is in terms of the filename hash
377 * value instead of the byte offset.
379 * Because we may return a 64-bit hash that is well beyond offset limits,
380 * we need to pass the max hash as the maximum allowable offset in
381 * the htree directory case.
383 * For non-htree, ext4_llseek already chooses the proper max offset.
385 static loff_t
ext4_dir_llseek(struct file
*file
, loff_t offset
, int whence
)
387 struct inode
*inode
= file
->f_mapping
->host
;
388 int dx_dir
= is_dx_dir(inode
);
389 loff_t ret
, htree_max
= ext4_get_htree_eof(file
);
392 ret
= generic_file_llseek_size(file
, offset
, whence
,
393 htree_max
, htree_max
);
395 ret
= ext4_llseek(file
, offset
, whence
);
396 file
->f_version
= inode_peek_iversion(inode
) - 1;
401 * This structure holds the nodes of the red-black tree used to store
402 * the directory entry in hash order.
407 struct rb_node rb_hash
;
416 * This functoin implements a non-recursive way of freeing all of the
417 * nodes in the red-black tree.
419 static void free_rb_tree_fname(struct rb_root
*root
)
421 struct fname
*fname
, *next
;
423 rbtree_postorder_for_each_entry_safe(fname
, next
, root
, rb_hash
)
425 struct fname
*old
= fname
;
434 static struct dir_private_info
*ext4_htree_create_dir_info(struct file
*filp
,
437 struct dir_private_info
*p
;
439 p
= kzalloc(sizeof(*p
), GFP_KERNEL
);
442 p
->curr_hash
= pos2maj_hash(filp
, pos
);
443 p
->curr_minor_hash
= pos2min_hash(filp
, pos
);
447 void ext4_htree_free_dir_info(struct dir_private_info
*p
)
449 free_rb_tree_fname(&p
->root
);
454 * Given a directory entry, enter it into the fname rb tree.
456 * When filename encryption is enabled, the dirent will hold the
457 * encrypted filename, while the htree will hold decrypted filename.
458 * The decrypted filename is passed in via ent_name. parameter.
460 int ext4_htree_store_dirent(struct file
*dir_file
, __u32 hash
,
462 struct ext4_dir_entry_2
*dirent
,
463 struct fscrypt_str
*ent_name
)
465 struct rb_node
**p
, *parent
= NULL
;
466 struct fname
*fname
, *new_fn
;
467 struct dir_private_info
*info
;
470 info
= dir_file
->private_data
;
471 p
= &info
->root
.rb_node
;
473 /* Create and allocate the fname structure */
474 len
= sizeof(struct fname
) + ent_name
->len
+ 1;
475 new_fn
= kzalloc(len
, GFP_KERNEL
);
479 new_fn
->minor_hash
= minor_hash
;
480 new_fn
->inode
= le32_to_cpu(dirent
->inode
);
481 new_fn
->name_len
= ent_name
->len
;
482 new_fn
->file_type
= dirent
->file_type
;
483 memcpy(new_fn
->name
, ent_name
->name
, ent_name
->len
);
487 fname
= rb_entry(parent
, struct fname
, rb_hash
);
490 * If the hash and minor hash match up, then we put
491 * them on a linked list. This rarely happens...
493 if ((new_fn
->hash
== fname
->hash
) &&
494 (new_fn
->minor_hash
== fname
->minor_hash
)) {
495 new_fn
->next
= fname
->next
;
496 fname
->next
= new_fn
;
500 if (new_fn
->hash
< fname
->hash
)
502 else if (new_fn
->hash
> fname
->hash
)
504 else if (new_fn
->minor_hash
< fname
->minor_hash
)
506 else /* if (new_fn->minor_hash > fname->minor_hash) */
510 rb_link_node(&new_fn
->rb_hash
, parent
, p
);
511 rb_insert_color(&new_fn
->rb_hash
, &info
->root
);
518 * This is a helper function for ext4_dx_readdir. It calls filldir
519 * for all entres on the fname linked list. (Normally there is only
520 * one entry on the linked list, unless there are 62 bit hash collisions.)
522 static int call_filldir(struct file
*file
, struct dir_context
*ctx
,
525 struct dir_private_info
*info
= file
->private_data
;
526 struct inode
*inode
= file_inode(file
);
527 struct super_block
*sb
= inode
->i_sb
;
530 ext4_msg(sb
, KERN_ERR
, "%s:%d: inode #%lu: comm %s: "
531 "called with null fname?!?", __func__
, __LINE__
,
532 inode
->i_ino
, current
->comm
);
535 ctx
->pos
= hash2pos(file
, fname
->hash
, fname
->minor_hash
);
537 if (!dir_emit(ctx
, fname
->name
,
540 get_dtype(sb
, fname
->file_type
))) {
541 info
->extra_fname
= fname
;
549 static int ext4_dx_readdir(struct file
*file
, struct dir_context
*ctx
)
551 struct dir_private_info
*info
= file
->private_data
;
552 struct inode
*inode
= file_inode(file
);
557 info
= ext4_htree_create_dir_info(file
, ctx
->pos
);
560 file
->private_data
= info
;
563 if (ctx
->pos
== ext4_get_htree_eof(file
))
566 /* Some one has messed with f_pos; reset the world */
567 if (info
->last_pos
!= ctx
->pos
) {
568 free_rb_tree_fname(&info
->root
);
569 info
->curr_node
= NULL
;
570 info
->extra_fname
= NULL
;
571 info
->curr_hash
= pos2maj_hash(file
, ctx
->pos
);
572 info
->curr_minor_hash
= pos2min_hash(file
, ctx
->pos
);
576 * If there are any leftover names on the hash collision
577 * chain, return them first.
579 if (info
->extra_fname
) {
580 if (call_filldir(file
, ctx
, info
->extra_fname
))
582 info
->extra_fname
= NULL
;
584 } else if (!info
->curr_node
)
585 info
->curr_node
= rb_first(&info
->root
);
589 * Fill the rbtree if we have no more entries,
590 * or the inode has changed since we last read in the
593 if ((!info
->curr_node
) ||
594 !inode_eq_iversion(inode
, file
->f_version
)) {
595 info
->curr_node
= NULL
;
596 free_rb_tree_fname(&info
->root
);
597 file
->f_version
= inode_query_iversion(inode
);
598 ret
= ext4_htree_fill_tree(file
, info
->curr_hash
,
599 info
->curr_minor_hash
,
604 ctx
->pos
= ext4_get_htree_eof(file
);
607 info
->curr_node
= rb_first(&info
->root
);
610 fname
= rb_entry(info
->curr_node
, struct fname
, rb_hash
);
611 info
->curr_hash
= fname
->hash
;
612 info
->curr_minor_hash
= fname
->minor_hash
;
613 if (call_filldir(file
, ctx
, fname
))
616 info
->curr_node
= rb_next(info
->curr_node
);
617 if (info
->curr_node
) {
618 fname
= rb_entry(info
->curr_node
, struct fname
,
620 info
->curr_hash
= fname
->hash
;
621 info
->curr_minor_hash
= fname
->minor_hash
;
623 if (info
->next_hash
== ~0) {
624 ctx
->pos
= ext4_get_htree_eof(file
);
627 info
->curr_hash
= info
->next_hash
;
628 info
->curr_minor_hash
= 0;
632 info
->last_pos
= ctx
->pos
;
633 return ret
< 0 ? ret
: 0;
636 static int ext4_release_dir(struct inode
*inode
, struct file
*filp
)
638 if (filp
->private_data
)
639 ext4_htree_free_dir_info(filp
->private_data
);
644 int ext4_check_all_de(struct inode
*dir
, struct buffer_head
*bh
, void *buf
,
647 struct ext4_dir_entry_2
*de
;
649 unsigned int offset
= 0;
652 de
= (struct ext4_dir_entry_2
*)buf
;
653 top
= buf
+ buf_size
;
654 while ((char *) de
< top
) {
655 if (ext4_check_dir_entry(dir
, NULL
, de
, bh
,
656 buf
, buf_size
, offset
))
657 return -EFSCORRUPTED
;
658 rlen
= ext4_rec_len_from_disk(de
->rec_len
, buf_size
);
659 de
= (struct ext4_dir_entry_2
*)((char *)de
+ rlen
);
662 if ((char *) de
> top
)
663 return -EFSCORRUPTED
;
668 const struct file_operations ext4_dir_operations
= {
669 .llseek
= ext4_dir_llseek
,
670 .read
= generic_read_dir
,
671 .iterate_shared
= ext4_readdir
,
672 .unlocked_ioctl
= ext4_ioctl
,
674 .compat_ioctl
= ext4_compat_ioctl
,
676 .fsync
= ext4_sync_file
,
677 .release
= ext4_release_dir
,