1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
2ac27a0ecSDave Kleikamp /*
3617ba13bSMingming Cao * linux/fs/ext4/dir.c
4ac27a0ecSDave Kleikamp *
5ac27a0ecSDave Kleikamp * Copyright (C) 1992, 1993, 1994, 1995
6ac27a0ecSDave Kleikamp * Remy Card (card@masi.ibp.fr)
7ac27a0ecSDave Kleikamp * Laboratoire MASI - Institut Blaise Pascal
8ac27a0ecSDave Kleikamp * Universite Pierre et Marie Curie (Paris VI)
9ac27a0ecSDave Kleikamp *
10ac27a0ecSDave Kleikamp * from
11ac27a0ecSDave Kleikamp *
12ac27a0ecSDave Kleikamp * linux/fs/minix/dir.c
13ac27a0ecSDave Kleikamp *
14ac27a0ecSDave Kleikamp * Copyright (C) 1991, 1992 Linus Torvalds
15ac27a0ecSDave Kleikamp *
16617ba13bSMingming Cao * ext4 directory handling functions
17ac27a0ecSDave Kleikamp *
18ac27a0ecSDave Kleikamp * Big-endian to little-endian byte-swapping/bitmaps by
19ac27a0ecSDave Kleikamp * David S. Miller (davem@caip.rutgers.edu), 1995
20ac27a0ecSDave Kleikamp *
21ac27a0ecSDave Kleikamp * Hash Tree Directory indexing (c) 2001 Daniel Phillips
22ac27a0ecSDave Kleikamp *
23ac27a0ecSDave Kleikamp */
24ac27a0ecSDave Kleikamp
25ac27a0ecSDave Kleikamp #include <linux/fs.h>
26ac27a0ecSDave Kleikamp #include <linux/buffer_head.h>
27ac27a0ecSDave Kleikamp #include <linux/slab.h>
28ee73f9a5SJeff Layton #include <linux/iversion.h>
29b886ee3eSGabriel Krisman Bertazi #include <linux/unicode.h>
303dcf5451SChristoph Hellwig #include "ext4.h"
3165d165d9STao Ma #include "xattr.h"
32ac27a0ecSDave Kleikamp
33725bebb2SAl Viro static int ext4_dx_readdir(struct file *, struct dir_context *);
34ac27a0ecSDave Kleikamp
35d1f5273eSFan Yong /**
36c60990b3STheodore Ts'o * is_dx_dir() - check if a directory is using htree indexing
37c60990b3STheodore Ts'o * @inode: directory inode
38c60990b3STheodore Ts'o *
39d1f5273eSFan Yong * Check if the given dir-inode refers to an htree-indexed directory
4070261f56SAnatol Pomozov * (or a directory which could potentially get converted to use htree
41d1f5273eSFan Yong * indexing).
42d1f5273eSFan Yong *
43d1f5273eSFan Yong * Return 1 if it is a dx dir, 0 if not
44d1f5273eSFan Yong */
is_dx_dir(struct inode * inode)45d1f5273eSFan Yong static int is_dx_dir(struct inode *inode)
46d1f5273eSFan Yong {
47d1f5273eSFan Yong struct super_block *sb = inode->i_sb;
48d1f5273eSFan Yong
49e2b911c5SDarrick J. Wong if (ext4_has_feature_dir_index(inode->i_sb) &&
50d1f5273eSFan Yong ((ext4_test_inode_flag(inode, EXT4_INODE_INDEX)) ||
518af0f082STao Ma ((inode->i_size >> sb->s_blocksize_bits) == 1) ||
528af0f082STao Ma ext4_has_inline_data(inode)))
53d1f5273eSFan Yong return 1;
54d1f5273eSFan Yong
55d1f5273eSFan Yong return 0;
56d1f5273eSFan Yong }
57d1f5273eSFan Yong
is_fake_dir_entry(struct ext4_dir_entry_2 * de)58471fbbeaSDaniel Rosenberg static bool is_fake_dir_entry(struct ext4_dir_entry_2 *de)
59471fbbeaSDaniel Rosenberg {
60471fbbeaSDaniel Rosenberg /* Check if . or .. , or skip if namelen is 0 */
61471fbbeaSDaniel Rosenberg if ((de->name_len > 0) && (de->name_len <= 2) && (de->name[0] == '.') &&
62471fbbeaSDaniel Rosenberg (de->name[1] == '.' || de->name[1] == '\0'))
63471fbbeaSDaniel Rosenberg return true;
64471fbbeaSDaniel Rosenberg /* Check if this is a csum entry */
65471fbbeaSDaniel Rosenberg if (de->file_type == EXT4_FT_DIR_CSUM)
66471fbbeaSDaniel Rosenberg return true;
67471fbbeaSDaniel Rosenberg return false;
68471fbbeaSDaniel Rosenberg }
69471fbbeaSDaniel Rosenberg
70cad3f007STheodore Ts'o /*
71cad3f007STheodore Ts'o * Return 0 if the directory entry is OK, and 1 if there is a problem
72cad3f007STheodore Ts'o *
73cad3f007STheodore Ts'o * Note: this is the opposite of what ext2 and ext3 historically returned...
7465d165d9STao Ma *
7565d165d9STao Ma * bh passed here can be an inode block or a dir data block, depending
7665d165d9STao Ma * on the inode inline data flag.
77cad3f007STheodore Ts'o */
__ext4_check_dir_entry(const char * function,unsigned int line,struct inode * dir,struct file * filp,struct ext4_dir_entry_2 * de,struct buffer_head * bh,char * buf,int size,unsigned int offset)7860fd4da3STheodore Ts'o int __ext4_check_dir_entry(const char *function, unsigned int line,
79f7c21177STheodore Ts'o struct inode *dir, struct file *filp,
80617ba13bSMingming Cao struct ext4_dir_entry_2 *de,
81226ba972STao Ma struct buffer_head *bh, char *buf, int size,
82498e5f24STheodore Ts'o unsigned int offset)
83ac27a0ecSDave Kleikamp {
84ac27a0ecSDave Kleikamp const char *error_msg = NULL;
853d0518f4SWei Yongjun const int rlen = ext4_rec_len_from_disk(de->rec_len,
863d0518f4SWei Yongjun dir->i_sb->s_blocksize);
87707d1a2fSTheodore Ts'o const int next_offset = ((char *) de - buf) + rlen;
88471fbbeaSDaniel Rosenberg bool fake = is_fake_dir_entry(de);
89471fbbeaSDaniel Rosenberg bool has_csum = ext4_has_metadata_csum(dir->i_sb);
90ac27a0ecSDave Kleikamp
91471fbbeaSDaniel Rosenberg if (unlikely(rlen < ext4_dir_rec_len(1, fake ? NULL : dir)))
92ac27a0ecSDave Kleikamp error_msg = "rec_len is smaller than minimal";
93cad3f007STheodore Ts'o else if (unlikely(rlen % 4 != 0))
94ac27a0ecSDave Kleikamp error_msg = "rec_len % 4 != 0";
95471fbbeaSDaniel Rosenberg else if (unlikely(rlen < ext4_dir_rec_len(de->name_len,
96471fbbeaSDaniel Rosenberg fake ? NULL : dir)))
97ac27a0ecSDave Kleikamp error_msg = "rec_len is too small for name_len";
98707d1a2fSTheodore Ts'o else if (unlikely(next_offset > size))
994d982e25STheodore Ts'o error_msg = "directory entry overrun";
100471fbbeaSDaniel Rosenberg else if (unlikely(next_offset > size - ext4_dir_rec_len(1,
101471fbbeaSDaniel Rosenberg has_csum ? NULL : dir) &&
102707d1a2fSTheodore Ts'o next_offset != size))
103109ba779SJan Kara error_msg = "directory entry too close to block end";
104cad3f007STheodore Ts'o else if (unlikely(le32_to_cpu(de->inode) >
105cad3f007STheodore Ts'o le32_to_cpu(EXT4_SB(dir->i_sb)->s_es->s_inodes_count)))
106ac27a0ecSDave Kleikamp error_msg = "inode out of bounds";
107cad3f007STheodore Ts'o else
108cad3f007STheodore Ts'o return 0;
109ac27a0ecSDave Kleikamp
110f7c21177STheodore Ts'o if (filp)
1114fda4003SDan Carpenter ext4_error_file(filp, function, line, bh->b_blocknr,
1124d982e25STheodore Ts'o "bad entry in directory: %s - offset=%u, "
113471fbbeaSDaniel Rosenberg "inode=%u, rec_len=%d, size=%d fake=%d",
1144d982e25STheodore Ts'o error_msg, offset, le32_to_cpu(de->inode),
115471fbbeaSDaniel Rosenberg rlen, size, fake);
116f7c21177STheodore Ts'o else
1174fda4003SDan Carpenter ext4_error_inode(dir, function, line, bh->b_blocknr,
1184d982e25STheodore Ts'o "bad entry in directory: %s - offset=%u, "
119471fbbeaSDaniel Rosenberg "inode=%u, rec_len=%d, size=%d fake=%d",
1204d982e25STheodore Ts'o error_msg, offset, le32_to_cpu(de->inode),
121471fbbeaSDaniel Rosenberg rlen, size, fake);
122f7c21177STheodore Ts'o
123cad3f007STheodore Ts'o return 1;
124ac27a0ecSDave Kleikamp }
125ac27a0ecSDave Kleikamp
ext4_readdir(struct file * file,struct dir_context * ctx)126725bebb2SAl Viro static int ext4_readdir(struct file *file, struct dir_context *ctx)
127ac27a0ecSDave Kleikamp {
128498e5f24STheodore Ts'o unsigned int offset;
129aa13d5f6SGiedrius Rekasius int i;
130617ba13bSMingming Cao struct ext4_dir_entry_2 *de;
131ac27a0ecSDave Kleikamp int err;
132725bebb2SAl Viro struct inode *inode = file_inode(file);
133d1f5273eSFan Yong struct super_block *sb = inode->i_sb;
13444614711SMichael Halcrow struct buffer_head *bh = NULL;
135a7550b30SJaegeuk Kim struct fscrypt_str fstr = FSTR_INIT(NULL, 0);
136ac27a0ecSDave Kleikamp
137ec0caa97SEric Biggers err = fscrypt_prepare_readdir(inode);
1383b1ada55SEric Biggers if (err)
13928b4c263STheodore Ts'o return err;
14028b4c263STheodore Ts'o
141d1f5273eSFan Yong if (is_dx_dir(inode)) {
142725bebb2SAl Viro err = ext4_dx_readdir(file, ctx);
143400086d7SMilan Djurovic if (err != ERR_BAD_DX_DIR)
144725bebb2SAl Viro return err;
145400086d7SMilan Djurovic
14648a34311SJan Kara /* Can we just clear INDEX flag to ignore htree information? */
14748a34311SJan Kara if (!ext4_has_metadata_csum(sb)) {
148ac27a0ecSDave Kleikamp /*
149ac27a0ecSDave Kleikamp * We don't set the inode dirty flag since it's not
15048a34311SJan Kara * critical that it gets flushed back to the disk.
151ac27a0ecSDave Kleikamp */
15248a34311SJan Kara ext4_clear_inode_flag(inode, EXT4_INODE_INDEX);
15348a34311SJan Kara }
154ac27a0ecSDave Kleikamp }
1558af0f082STao Ma
1568af0f082STao Ma if (ext4_has_inline_data(inode)) {
1578af0f082STao Ma int has_inline_data = 1;
15844614711SMichael Halcrow err = ext4_read_inline_dir(file, ctx,
1598af0f082STao Ma &has_inline_data);
1608af0f082STao Ma if (has_inline_data)
16144614711SMichael Halcrow return err;
16244614711SMichael Halcrow }
16344614711SMichael Halcrow
164592ddec7SChandan Rajendra if (IS_ENCRYPTED(inode)) {
1658b10fe68SJeff Layton err = fscrypt_fname_alloc_buffer(EXT4_NAME_LEN, &fstr);
166b7236e21STheodore Ts'o if (err < 0)
167b7236e21STheodore Ts'o return err;
1688af0f082STao Ma }
1698af0f082STao Ma
170725bebb2SAl Viro while (ctx->pos < inode->i_size) {
1712ed88685STheodore Ts'o struct ext4_map_blocks map;
172ac27a0ecSDave Kleikamp
1731f60fbe7STheodore Ts'o if (fatal_signal_pending(current)) {
1741f60fbe7STheodore Ts'o err = -ERESTARTSYS;
1751f60fbe7STheodore Ts'o goto errout;
1761f60fbe7STheodore Ts'o }
1771f60fbe7STheodore Ts'o cond_resched();
1784e19d6b6STheodore Ts'o offset = ctx->pos & (sb->s_blocksize - 1);
179725bebb2SAl Viro map.m_lblk = ctx->pos >> EXT4_BLOCK_SIZE_BITS(sb);
1802ed88685STheodore Ts'o map.m_len = 1;
1812ed88685STheodore Ts'o err = ext4_map_blocks(NULL, inode, &map, 0);
1824e19d6b6STheodore Ts'o if (err == 0) {
1834e19d6b6STheodore Ts'o /* m_len should never be zero but let's avoid
1844e19d6b6STheodore Ts'o * an infinite loop if it somehow is */
1854e19d6b6STheodore Ts'o if (map.m_len == 0)
1864e19d6b6STheodore Ts'o map.m_len = 1;
1874e19d6b6STheodore Ts'o ctx->pos += map.m_len * sb->s_blocksize;
1884e19d6b6STheodore Ts'o continue;
1894e19d6b6STheodore Ts'o }
190ac27a0ecSDave Kleikamp if (err > 0) {
1912ed88685STheodore Ts'o pgoff_t index = map.m_pblk >>
19209cbfeafSKirill A. Shutemov (PAGE_SHIFT - inode->i_blkbits);
193725bebb2SAl Viro if (!ra_has_index(&file->f_ra, index))
194cf914a7dSRusty Russell page_cache_sync_readahead(
195dc7868fcSFengguang Wu sb->s_bdev->bd_inode->i_mapping,
196725bebb2SAl Viro &file->f_ra, file,
197cf914a7dSRusty Russell index, 1);
19809cbfeafSKirill A. Shutemov file->f_ra.prev_pos = (loff_t)index << PAGE_SHIFT;
1991c215028STheodore Ts'o bh = ext4_bread(NULL, inode, map.m_lblk, 0);
200c906f38eSKirill Tkhai if (IS_ERR(bh)) {
201c906f38eSKirill Tkhai err = PTR_ERR(bh);
202c906f38eSKirill Tkhai bh = NULL;
203c906f38eSKirill Tkhai goto errout;
204c906f38eSKirill Tkhai }
205ac27a0ecSDave Kleikamp }
206ac27a0ecSDave Kleikamp
207ac27a0ecSDave Kleikamp if (!bh) {
208e6c40211SEric Sandeen /* corrupt size? Maybe no more blocks to read */
209725bebb2SAl Viro if (ctx->pos > inode->i_blocks << 9)
210e6c40211SEric Sandeen break;
211725bebb2SAl Viro ctx->pos += sb->s_blocksize - offset;
212ac27a0ecSDave Kleikamp continue;
213ac27a0ecSDave Kleikamp }
214ac27a0ecSDave Kleikamp
215b0336e8dSDarrick J. Wong /* Check the checksum */
216b0336e8dSDarrick J. Wong if (!buffer_verified(bh) &&
217f036adb3STheodore Ts'o !ext4_dirblock_csum_verify(inode, bh)) {
218725bebb2SAl Viro EXT4_ERROR_FILE(file, 0, "directory fails checksum "
219b0336e8dSDarrick J. Wong "at offset %llu",
220725bebb2SAl Viro (unsigned long long)ctx->pos);
221725bebb2SAl Viro ctx->pos += sb->s_blocksize - offset;
222d5ac7773SGuo Chao brelse(bh);
22344614711SMichael Halcrow bh = NULL;
224b0336e8dSDarrick J. Wong continue;
225b0336e8dSDarrick J. Wong }
226b0336e8dSDarrick J. Wong set_buffer_verified(bh);
227b0336e8dSDarrick J. Wong
228ac27a0ecSDave Kleikamp /* If the dir block has changed since the last call to
229ac27a0ecSDave Kleikamp * readdir(2), then we might be pointing to an invalid
230ac27a0ecSDave Kleikamp * dirent right now. Scan from the start of the block
231ac27a0ecSDave Kleikamp * to make sure. */
232c472c07bSGoffredo Baroncelli if (!inode_eq_iversion(inode, file->f_version)) {
233ac27a0ecSDave Kleikamp for (i = 0; i < sb->s_blocksize && i < offset; ) {
234617ba13bSMingming Cao de = (struct ext4_dir_entry_2 *)
235ac27a0ecSDave Kleikamp (bh->b_data + i);
236ac27a0ecSDave Kleikamp /* It's too expensive to do a full
237ac27a0ecSDave Kleikamp * dirent test each time round this
238ac27a0ecSDave Kleikamp * loop, but we do have to test at
239ac27a0ecSDave Kleikamp * least that it is non-zero. A
240ac27a0ecSDave Kleikamp * failure will be detected in the
241ac27a0ecSDave Kleikamp * dirent test below. */
2423d0518f4SWei Yongjun if (ext4_rec_len_from_disk(de->rec_len,
243471fbbeaSDaniel Rosenberg sb->s_blocksize) < ext4_dir_rec_len(1,
244471fbbeaSDaniel Rosenberg inode))
245ac27a0ecSDave Kleikamp break;
2463d0518f4SWei Yongjun i += ext4_rec_len_from_disk(de->rec_len,
2473d0518f4SWei Yongjun sb->s_blocksize);
248ac27a0ecSDave Kleikamp }
249ac27a0ecSDave Kleikamp offset = i;
250725bebb2SAl Viro ctx->pos = (ctx->pos & ~(sb->s_blocksize - 1))
251ac27a0ecSDave Kleikamp | offset;
252ee73f9a5SJeff Layton file->f_version = inode_query_iversion(inode);
253ac27a0ecSDave Kleikamp }
254ac27a0ecSDave Kleikamp
255725bebb2SAl Viro while (ctx->pos < inode->i_size
256ac27a0ecSDave Kleikamp && offset < sb->s_blocksize) {
257617ba13bSMingming Cao de = (struct ext4_dir_entry_2 *) (bh->b_data + offset);
258725bebb2SAl Viro if (ext4_check_dir_entry(inode, file, de, bh,
259226ba972STao Ma bh->b_data, bh->b_size,
260226ba972STao Ma offset)) {
26163f57933SAndrew Morton /*
262725bebb2SAl Viro * On error, skip to the next block
26363f57933SAndrew Morton */
264725bebb2SAl Viro ctx->pos = (ctx->pos |
265ac27a0ecSDave Kleikamp (sb->s_blocksize - 1)) + 1;
266725bebb2SAl Viro break;
267ac27a0ecSDave Kleikamp }
2683d0518f4SWei Yongjun offset += ext4_rec_len_from_disk(de->rec_len,
2693d0518f4SWei Yongjun sb->s_blocksize);
270ac27a0ecSDave Kleikamp if (le32_to_cpu(de->inode)) {
271592ddec7SChandan Rajendra if (!IS_ENCRYPTED(inode)) {
272725bebb2SAl Viro if (!dir_emit(ctx, de->name,
273ac27a0ecSDave Kleikamp de->name_len,
274ac27a0ecSDave Kleikamp le32_to_cpu(de->inode),
27544614711SMichael Halcrow get_dtype(sb, de->file_type)))
27644614711SMichael Halcrow goto done;
27744614711SMichael Halcrow } else {
278a7550b30SJaegeuk Kim int save_len = fstr.len;
279a7550b30SJaegeuk Kim struct fscrypt_str de_name =
280a7550b30SJaegeuk Kim FSTR_INIT(de->name,
281a7550b30SJaegeuk Kim de->name_len);
282d2299590STheodore Ts'o
28344614711SMichael Halcrow /* Directory is encrypted */
284a7550b30SJaegeuk Kim err = fscrypt_fname_disk_to_usr(inode,
285471fbbeaSDaniel Rosenberg EXT4_DIRENT_HASH(de),
286471fbbeaSDaniel Rosenberg EXT4_DIRENT_MINOR_HASH(de),
287471fbbeaSDaniel Rosenberg &de_name, &fstr);
288ef1eb3aaSEric Biggers de_name = fstr;
289a7550b30SJaegeuk Kim fstr.len = save_len;
290ef1eb3aaSEric Biggers if (err)
29144614711SMichael Halcrow goto errout;
29244614711SMichael Halcrow if (!dir_emit(ctx,
293ef1eb3aaSEric Biggers de_name.name, de_name.len,
29444614711SMichael Halcrow le32_to_cpu(de->inode),
29544614711SMichael Halcrow get_dtype(sb, de->file_type)))
29644614711SMichael Halcrow goto done;
297ac27a0ecSDave Kleikamp }
298725bebb2SAl Viro }
299725bebb2SAl Viro ctx->pos += ext4_rec_len_from_disk(de->rec_len,
3003d0518f4SWei Yongjun sb->s_blocksize);
301ac27a0ecSDave Kleikamp }
302ae05327aSAl Viro if ((ctx->pos < inode->i_size) && !dir_relax_shared(inode))
30344614711SMichael Halcrow goto done;
304ac27a0ecSDave Kleikamp brelse(bh);
30544614711SMichael Halcrow bh = NULL;
306ac27a0ecSDave Kleikamp }
30744614711SMichael Halcrow done:
30844614711SMichael Halcrow err = 0;
30944614711SMichael Halcrow errout:
310a7550b30SJaegeuk Kim fscrypt_fname_free_buffer(&fstr);
31144614711SMichael Halcrow brelse(bh);
31244614711SMichael Halcrow return err;
313ac27a0ecSDave Kleikamp }
314ac27a0ecSDave Kleikamp
is_32bit_api(void)315d1f5273eSFan Yong static inline int is_32bit_api(void)
316d1f5273eSFan Yong {
317d1f5273eSFan Yong #ifdef CONFIG_COMPAT
318121cef8fSAndy Lutomirski return in_compat_syscall();
319d1f5273eSFan Yong #else
320d1f5273eSFan Yong return (BITS_PER_LONG == 32);
321d1f5273eSFan Yong #endif
322d1f5273eSFan Yong }
323d1f5273eSFan Yong
324ac27a0ecSDave Kleikamp /*
325ac27a0ecSDave Kleikamp * These functions convert from the major/minor hash to an f_pos
326d1f5273eSFan Yong * value for dx directories
327ac27a0ecSDave Kleikamp *
328d1f5273eSFan Yong * Upper layer (for example NFS) should specify FMODE_32BITHASH or
329d1f5273eSFan Yong * FMODE_64BITHASH explicitly. On the other hand, we allow ext4 to be mounted
330d1f5273eSFan Yong * directly on both 32-bit and 64-bit nodes, under such case, neither
331d1f5273eSFan Yong * FMODE_32BITHASH nor FMODE_64BITHASH is specified.
332ac27a0ecSDave Kleikamp */
hash2pos(struct file * filp,__u32 major,__u32 minor)333d1f5273eSFan Yong static inline loff_t hash2pos(struct file *filp, __u32 major, __u32 minor)
334d1f5273eSFan Yong {
335d1f5273eSFan Yong if ((filp->f_mode & FMODE_32BITHASH) ||
336d1f5273eSFan Yong (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
337d1f5273eSFan Yong return major >> 1;
338d1f5273eSFan Yong else
339d1f5273eSFan Yong return ((__u64)(major >> 1) << 32) | (__u64)minor;
340d1f5273eSFan Yong }
341d1f5273eSFan Yong
pos2maj_hash(struct file * filp,loff_t pos)342d1f5273eSFan Yong static inline __u32 pos2maj_hash(struct file *filp, loff_t pos)
343d1f5273eSFan Yong {
344d1f5273eSFan Yong if ((filp->f_mode & FMODE_32BITHASH) ||
345d1f5273eSFan Yong (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
346d1f5273eSFan Yong return (pos << 1) & 0xffffffff;
347d1f5273eSFan Yong else
348d1f5273eSFan Yong return ((pos >> 32) << 1) & 0xffffffff;
349d1f5273eSFan Yong }
350d1f5273eSFan Yong
pos2min_hash(struct file * filp,loff_t pos)351d1f5273eSFan Yong static inline __u32 pos2min_hash(struct file *filp, loff_t pos)
352d1f5273eSFan Yong {
353d1f5273eSFan Yong if ((filp->f_mode & FMODE_32BITHASH) ||
354d1f5273eSFan Yong (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
355d1f5273eSFan Yong return 0;
356d1f5273eSFan Yong else
357d1f5273eSFan Yong return pos & 0xffffffff;
358d1f5273eSFan Yong }
359d1f5273eSFan Yong
360d1f5273eSFan Yong /*
361d1f5273eSFan Yong * Return 32- or 64-bit end-of-file for dx directories
362d1f5273eSFan Yong */
ext4_get_htree_eof(struct file * filp)363d1f5273eSFan Yong static inline loff_t ext4_get_htree_eof(struct file *filp)
364d1f5273eSFan Yong {
365d1f5273eSFan Yong if ((filp->f_mode & FMODE_32BITHASH) ||
366d1f5273eSFan Yong (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
367d1f5273eSFan Yong return EXT4_HTREE_EOF_32BIT;
368d1f5273eSFan Yong else
369d1f5273eSFan Yong return EXT4_HTREE_EOF_64BIT;
370d1f5273eSFan Yong }
371d1f5273eSFan Yong
372d1f5273eSFan Yong
373d1f5273eSFan Yong /*
374ec7268ceSEric Sandeen * ext4_dir_llseek() calls generic_file_llseek_size to handle htree
375ec7268ceSEric Sandeen * directories, where the "offset" is in terms of the filename hash
376ec7268ceSEric Sandeen * value instead of the byte offset.
377d1f5273eSFan Yong *
378ec7268ceSEric Sandeen * Because we may return a 64-bit hash that is well beyond offset limits,
379ec7268ceSEric Sandeen * we need to pass the max hash as the maximum allowable offset in
380ec7268ceSEric Sandeen * the htree directory case.
381ec7268ceSEric Sandeen *
382ec7268ceSEric Sandeen * For non-htree, ext4_llseek already chooses the proper max offset.
383d1f5273eSFan Yong */
ext4_dir_llseek(struct file * file,loff_t offset,int whence)384d4e43954SZheng Liu static loff_t ext4_dir_llseek(struct file *file, loff_t offset, int whence)
385d1f5273eSFan Yong {
386d1f5273eSFan Yong struct inode *inode = file->f_mapping->host;
387d1f5273eSFan Yong int dx_dir = is_dx_dir(inode);
388e40ff213STheodore Ts'o loff_t ret, htree_max = ext4_get_htree_eof(file);
389d1f5273eSFan Yong
390ec7268ceSEric Sandeen if (likely(dx_dir))
391e40ff213STheodore Ts'o ret = generic_file_llseek_size(file, offset, whence,
392ec7268ceSEric Sandeen htree_max, htree_max);
393d1f5273eSFan Yong else
394e40ff213STheodore Ts'o ret = ext4_llseek(file, offset, whence);
395e40ff213STheodore Ts'o file->f_version = inode_peek_iversion(inode) - 1;
396e40ff213STheodore Ts'o return ret;
397d1f5273eSFan Yong }
398ac27a0ecSDave Kleikamp
399ac27a0ecSDave Kleikamp /*
400ac27a0ecSDave Kleikamp * This structure holds the nodes of the red-black tree used to store
401ac27a0ecSDave Kleikamp * the directory entry in hash order.
402ac27a0ecSDave Kleikamp */
403ac27a0ecSDave Kleikamp struct fname {
404ac27a0ecSDave Kleikamp __u32 hash;
405ac27a0ecSDave Kleikamp __u32 minor_hash;
406ac27a0ecSDave Kleikamp struct rb_node rb_hash;
407ac27a0ecSDave Kleikamp struct fname *next;
408ac27a0ecSDave Kleikamp __u32 inode;
409ac27a0ecSDave Kleikamp __u8 name_len;
410ac27a0ecSDave Kleikamp __u8 file_type;
411e32ac245SGustavo A. R. Silva char name[];
412ac27a0ecSDave Kleikamp };
413ac27a0ecSDave Kleikamp
414ac27a0ecSDave Kleikamp /*
415*fac88735SChin Yik Ming * This function implements a non-recursive way of freeing all of the
416ac27a0ecSDave Kleikamp * nodes in the red-black tree.
417ac27a0ecSDave Kleikamp */
free_rb_tree_fname(struct rb_root * root)418ac27a0ecSDave Kleikamp static void free_rb_tree_fname(struct rb_root *root)
419ac27a0ecSDave Kleikamp {
420d1866bd0SCody P Schafer struct fname *fname, *next;
421ac27a0ecSDave Kleikamp
422d1866bd0SCody P Schafer rbtree_postorder_for_each_entry_safe(fname, next, root, rb_hash)
423ac27a0ecSDave Kleikamp while (fname) {
424ac27a0ecSDave Kleikamp struct fname *old = fname;
425ac27a0ecSDave Kleikamp fname = fname->next;
426ac27a0ecSDave Kleikamp kfree(old);
427ac27a0ecSDave Kleikamp }
428d1866bd0SCody P Schafer
42964e290ecSVenkatesh Pallipadi *root = RB_ROOT;
430ac27a0ecSDave Kleikamp }
431ac27a0ecSDave Kleikamp
432ac27a0ecSDave Kleikamp
ext4_htree_create_dir_info(struct file * filp,loff_t pos)433d1f5273eSFan Yong static struct dir_private_info *ext4_htree_create_dir_info(struct file *filp,
434d1f5273eSFan Yong loff_t pos)
435ac27a0ecSDave Kleikamp {
436ac27a0ecSDave Kleikamp struct dir_private_info *p;
437ac27a0ecSDave Kleikamp
438d695a1beSMarkus Elfring p = kzalloc(sizeof(*p), GFP_KERNEL);
439ac27a0ecSDave Kleikamp if (!p)
440ac27a0ecSDave Kleikamp return NULL;
441d1f5273eSFan Yong p->curr_hash = pos2maj_hash(filp, pos);
442d1f5273eSFan Yong p->curr_minor_hash = pos2min_hash(filp, pos);
443ac27a0ecSDave Kleikamp return p;
444ac27a0ecSDave Kleikamp }
445ac27a0ecSDave Kleikamp
ext4_htree_free_dir_info(struct dir_private_info * p)446617ba13bSMingming Cao void ext4_htree_free_dir_info(struct dir_private_info *p)
447ac27a0ecSDave Kleikamp {
448ac27a0ecSDave Kleikamp free_rb_tree_fname(&p->root);
449ac27a0ecSDave Kleikamp kfree(p);
450ac27a0ecSDave Kleikamp }
451ac27a0ecSDave Kleikamp
452ac27a0ecSDave Kleikamp /*
453ac27a0ecSDave Kleikamp * Given a directory entry, enter it into the fname rb tree.
4542f61830aSTheodore Ts'o *
4552f61830aSTheodore Ts'o * When filename encryption is enabled, the dirent will hold the
4562f61830aSTheodore Ts'o * encrypted filename, while the htree will hold decrypted filename.
4572f61830aSTheodore Ts'o * The decrypted filename is passed in via ent_name. parameter.
458ac27a0ecSDave Kleikamp */
ext4_htree_store_dirent(struct file * dir_file,__u32 hash,__u32 minor_hash,struct ext4_dir_entry_2 * dirent,struct fscrypt_str * ent_name)459617ba13bSMingming Cao int ext4_htree_store_dirent(struct file *dir_file, __u32 hash,
460ac27a0ecSDave Kleikamp __u32 minor_hash,
4612f61830aSTheodore Ts'o struct ext4_dir_entry_2 *dirent,
462a7550b30SJaegeuk Kim struct fscrypt_str *ent_name)
463ac27a0ecSDave Kleikamp {
464ac27a0ecSDave Kleikamp struct rb_node **p, *parent = NULL;
465ac27a0ecSDave Kleikamp struct fname *fname, *new_fn;
466ac27a0ecSDave Kleikamp struct dir_private_info *info;
467ac27a0ecSDave Kleikamp int len;
468ac27a0ecSDave Kleikamp
469a271fe85SJoe Perches info = dir_file->private_data;
470ac27a0ecSDave Kleikamp p = &info->root.rb_node;
471ac27a0ecSDave Kleikamp
472ac27a0ecSDave Kleikamp /* Create and allocate the fname structure */
4732f61830aSTheodore Ts'o len = sizeof(struct fname) + ent_name->len + 1;
474ac27a0ecSDave Kleikamp new_fn = kzalloc(len, GFP_KERNEL);
475ac27a0ecSDave Kleikamp if (!new_fn)
476ac27a0ecSDave Kleikamp return -ENOMEM;
477ac27a0ecSDave Kleikamp new_fn->hash = hash;
478ac27a0ecSDave Kleikamp new_fn->minor_hash = minor_hash;
479ac27a0ecSDave Kleikamp new_fn->inode = le32_to_cpu(dirent->inode);
4802f61830aSTheodore Ts'o new_fn->name_len = ent_name->len;
481ac27a0ecSDave Kleikamp new_fn->file_type = dirent->file_type;
4822f61830aSTheodore Ts'o memcpy(new_fn->name, ent_name->name, ent_name->len);
483ac27a0ecSDave Kleikamp
484ac27a0ecSDave Kleikamp while (*p) {
485ac27a0ecSDave Kleikamp parent = *p;
486ac27a0ecSDave Kleikamp fname = rb_entry(parent, struct fname, rb_hash);
487ac27a0ecSDave Kleikamp
488ac27a0ecSDave Kleikamp /*
489ac27a0ecSDave Kleikamp * If the hash and minor hash match up, then we put
490ac27a0ecSDave Kleikamp * them on a linked list. This rarely happens...
491ac27a0ecSDave Kleikamp */
492ac27a0ecSDave Kleikamp if ((new_fn->hash == fname->hash) &&
493ac27a0ecSDave Kleikamp (new_fn->minor_hash == fname->minor_hash)) {
494ac27a0ecSDave Kleikamp new_fn->next = fname->next;
495ac27a0ecSDave Kleikamp fname->next = new_fn;
496ac27a0ecSDave Kleikamp return 0;
497ac27a0ecSDave Kleikamp }
498ac27a0ecSDave Kleikamp
499ac27a0ecSDave Kleikamp if (new_fn->hash < fname->hash)
500ac27a0ecSDave Kleikamp p = &(*p)->rb_left;
501ac27a0ecSDave Kleikamp else if (new_fn->hash > fname->hash)
502ac27a0ecSDave Kleikamp p = &(*p)->rb_right;
503ac27a0ecSDave Kleikamp else if (new_fn->minor_hash < fname->minor_hash)
504ac27a0ecSDave Kleikamp p = &(*p)->rb_left;
505ac27a0ecSDave Kleikamp else /* if (new_fn->minor_hash > fname->minor_hash) */
506ac27a0ecSDave Kleikamp p = &(*p)->rb_right;
507ac27a0ecSDave Kleikamp }
508ac27a0ecSDave Kleikamp
509ac27a0ecSDave Kleikamp rb_link_node(&new_fn->rb_hash, parent, p);
510ac27a0ecSDave Kleikamp rb_insert_color(&new_fn->rb_hash, &info->root);
511ac27a0ecSDave Kleikamp return 0;
512ac27a0ecSDave Kleikamp }
513ac27a0ecSDave Kleikamp
514ac27a0ecSDave Kleikamp
515ac27a0ecSDave Kleikamp
516ac27a0ecSDave Kleikamp /*
517617ba13bSMingming Cao * This is a helper function for ext4_dx_readdir. It calls filldir
518*fac88735SChin Yik Ming * for all entries on the fname linked list. (Normally there is only
519ac27a0ecSDave Kleikamp * one entry on the linked list, unless there are 62 bit hash collisions.)
520ac27a0ecSDave Kleikamp */
call_filldir(struct file * file,struct dir_context * ctx,struct fname * fname)521725bebb2SAl Viro static int call_filldir(struct file *file, struct dir_context *ctx,
522725bebb2SAl Viro struct fname *fname)
523ac27a0ecSDave Kleikamp {
524725bebb2SAl Viro struct dir_private_info *info = file->private_data;
525725bebb2SAl Viro struct inode *inode = file_inode(file);
526725bebb2SAl Viro struct super_block *sb = inode->i_sb;
527ac27a0ecSDave Kleikamp
528ac27a0ecSDave Kleikamp if (!fname) {
52992b97816STheodore Ts'o ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: comm %s: "
53092b97816STheodore Ts'o "called with null fname?!?", __func__, __LINE__,
53192b97816STheodore Ts'o inode->i_ino, current->comm);
532ac27a0ecSDave Kleikamp return 0;
533ac27a0ecSDave Kleikamp }
534725bebb2SAl Viro ctx->pos = hash2pos(file, fname->hash, fname->minor_hash);
535ac27a0ecSDave Kleikamp while (fname) {
536725bebb2SAl Viro if (!dir_emit(ctx, fname->name,
537725bebb2SAl Viro fname->name_len,
538ac27a0ecSDave Kleikamp fname->inode,
539725bebb2SAl Viro get_dtype(sb, fname->file_type))) {
540d0156417STheodore Ts'o info->extra_fname = fname;
541725bebb2SAl Viro return 1;
542ac27a0ecSDave Kleikamp }
543ac27a0ecSDave Kleikamp fname = fname->next;
544ac27a0ecSDave Kleikamp }
545ac27a0ecSDave Kleikamp return 0;
546ac27a0ecSDave Kleikamp }
547ac27a0ecSDave Kleikamp
ext4_dx_readdir(struct file * file,struct dir_context * ctx)548725bebb2SAl Viro static int ext4_dx_readdir(struct file *file, struct dir_context *ctx)
549ac27a0ecSDave Kleikamp {
550725bebb2SAl Viro struct dir_private_info *info = file->private_data;
551725bebb2SAl Viro struct inode *inode = file_inode(file);
552ac27a0ecSDave Kleikamp struct fname *fname;
55342cb4474Syangerkun int ret = 0;
554ac27a0ecSDave Kleikamp
555ac27a0ecSDave Kleikamp if (!info) {
556725bebb2SAl Viro info = ext4_htree_create_dir_info(file, ctx->pos);
557ac27a0ecSDave Kleikamp if (!info)
558ac27a0ecSDave Kleikamp return -ENOMEM;
559725bebb2SAl Viro file->private_data = info;
560ac27a0ecSDave Kleikamp }
561ac27a0ecSDave Kleikamp
562725bebb2SAl Viro if (ctx->pos == ext4_get_htree_eof(file))
563ac27a0ecSDave Kleikamp return 0; /* EOF */
564ac27a0ecSDave Kleikamp
565ac27a0ecSDave Kleikamp /* Some one has messed with f_pos; reset the world */
566725bebb2SAl Viro if (info->last_pos != ctx->pos) {
567ac27a0ecSDave Kleikamp free_rb_tree_fname(&info->root);
568ac27a0ecSDave Kleikamp info->curr_node = NULL;
569ac27a0ecSDave Kleikamp info->extra_fname = NULL;
570725bebb2SAl Viro info->curr_hash = pos2maj_hash(file, ctx->pos);
571725bebb2SAl Viro info->curr_minor_hash = pos2min_hash(file, ctx->pos);
572ac27a0ecSDave Kleikamp }
573ac27a0ecSDave Kleikamp
574ac27a0ecSDave Kleikamp /*
575ac27a0ecSDave Kleikamp * If there are any leftover names on the hash collision
576ac27a0ecSDave Kleikamp * chain, return them first.
577ac27a0ecSDave Kleikamp */
578d0156417STheodore Ts'o if (info->extra_fname) {
579725bebb2SAl Viro if (call_filldir(file, ctx, info->extra_fname))
580ac27a0ecSDave Kleikamp goto finished;
581d0156417STheodore Ts'o info->extra_fname = NULL;
5823c37fc86STheodore Ts'o goto next_node;
583d0156417STheodore Ts'o } else if (!info->curr_node)
584ac27a0ecSDave Kleikamp info->curr_node = rb_first(&info->root);
585ac27a0ecSDave Kleikamp
586ac27a0ecSDave Kleikamp while (1) {
587ac27a0ecSDave Kleikamp /*
588ac27a0ecSDave Kleikamp * Fill the rbtree if we have no more entries,
589ac27a0ecSDave Kleikamp * or the inode has changed since we last read in the
590ac27a0ecSDave Kleikamp * cached entries.
591ac27a0ecSDave Kleikamp */
592ac27a0ecSDave Kleikamp if ((!info->curr_node) ||
593c472c07bSGoffredo Baroncelli !inode_eq_iversion(inode, file->f_version)) {
594ac27a0ecSDave Kleikamp info->curr_node = NULL;
595ac27a0ecSDave Kleikamp free_rb_tree_fname(&info->root);
596ee73f9a5SJeff Layton file->f_version = inode_query_iversion(inode);
597725bebb2SAl Viro ret = ext4_htree_fill_tree(file, info->curr_hash,
598ac27a0ecSDave Kleikamp info->curr_minor_hash,
599ac27a0ecSDave Kleikamp &info->next_hash);
600ac27a0ecSDave Kleikamp if (ret < 0)
60142cb4474Syangerkun goto finished;
602ac27a0ecSDave Kleikamp if (ret == 0) {
603725bebb2SAl Viro ctx->pos = ext4_get_htree_eof(file);
604ac27a0ecSDave Kleikamp break;
605ac27a0ecSDave Kleikamp }
606ac27a0ecSDave Kleikamp info->curr_node = rb_first(&info->root);
607ac27a0ecSDave Kleikamp }
608ac27a0ecSDave Kleikamp
609ac27a0ecSDave Kleikamp fname = rb_entry(info->curr_node, struct fname, rb_hash);
610ac27a0ecSDave Kleikamp info->curr_hash = fname->hash;
611ac27a0ecSDave Kleikamp info->curr_minor_hash = fname->minor_hash;
612725bebb2SAl Viro if (call_filldir(file, ctx, fname))
613ac27a0ecSDave Kleikamp break;
6143c37fc86STheodore Ts'o next_node:
615ac27a0ecSDave Kleikamp info->curr_node = rb_next(info->curr_node);
6163c37fc86STheodore Ts'o if (info->curr_node) {
6173c37fc86STheodore Ts'o fname = rb_entry(info->curr_node, struct fname,
6183c37fc86STheodore Ts'o rb_hash);
6193c37fc86STheodore Ts'o info->curr_hash = fname->hash;
6203c37fc86STheodore Ts'o info->curr_minor_hash = fname->minor_hash;
6213c37fc86STheodore Ts'o } else {
622ac27a0ecSDave Kleikamp if (info->next_hash == ~0) {
623725bebb2SAl Viro ctx->pos = ext4_get_htree_eof(file);
624ac27a0ecSDave Kleikamp break;
625ac27a0ecSDave Kleikamp }
626ac27a0ecSDave Kleikamp info->curr_hash = info->next_hash;
627ac27a0ecSDave Kleikamp info->curr_minor_hash = 0;
628ac27a0ecSDave Kleikamp }
629ac27a0ecSDave Kleikamp }
630ac27a0ecSDave Kleikamp finished:
631725bebb2SAl Viro info->last_pos = ctx->pos;
63242cb4474Syangerkun return ret < 0 ? ret : 0;
633ac27a0ecSDave Kleikamp }
634ac27a0ecSDave Kleikamp
ext4_release_dir(struct inode * inode,struct file * filp)635617ba13bSMingming Cao static int ext4_release_dir(struct inode *inode, struct file *filp)
636ac27a0ecSDave Kleikamp {
637ac27a0ecSDave Kleikamp if (filp->private_data)
638617ba13bSMingming Cao ext4_htree_free_dir_info(filp->private_data);
639ac27a0ecSDave Kleikamp
640ac27a0ecSDave Kleikamp return 0;
641ac27a0ecSDave Kleikamp }
642d1f5273eSFan Yong
ext4_check_all_de(struct inode * dir,struct buffer_head * bh,void * buf,int buf_size)64340b163f1SDarrick J. Wong int ext4_check_all_de(struct inode *dir, struct buffer_head *bh, void *buf,
64440b163f1SDarrick J. Wong int buf_size)
64540b163f1SDarrick J. Wong {
64640b163f1SDarrick J. Wong struct ext4_dir_entry_2 *de;
64718017479SEric Engestrom int rlen;
64840b163f1SDarrick J. Wong unsigned int offset = 0;
64940b163f1SDarrick J. Wong char *top;
65040b163f1SDarrick J. Wong
651c30365b9SYu Zhe de = buf;
65240b163f1SDarrick J. Wong top = buf + buf_size;
65340b163f1SDarrick J. Wong while ((char *) de < top) {
65440b163f1SDarrick J. Wong if (ext4_check_dir_entry(dir, NULL, de, bh,
65540b163f1SDarrick J. Wong buf, buf_size, offset))
6566a797d27SDarrick J. Wong return -EFSCORRUPTED;
65740b163f1SDarrick J. Wong rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
65840b163f1SDarrick J. Wong de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
65940b163f1SDarrick J. Wong offset += rlen;
66040b163f1SDarrick J. Wong }
66140b163f1SDarrick J. Wong if ((char *) de > top)
6626a797d27SDarrick J. Wong return -EFSCORRUPTED;
66340b163f1SDarrick J. Wong
66440b163f1SDarrick J. Wong return 0;
66540b163f1SDarrick J. Wong }
66640b163f1SDarrick J. Wong
667d1f5273eSFan Yong const struct file_operations ext4_dir_operations = {
668d1f5273eSFan Yong .llseek = ext4_dir_llseek,
669d1f5273eSFan Yong .read = generic_read_dir,
670ae05327aSAl Viro .iterate_shared = ext4_readdir,
671d1f5273eSFan Yong .unlocked_ioctl = ext4_ioctl,
672d1f5273eSFan Yong #ifdef CONFIG_COMPAT
673d1f5273eSFan Yong .compat_ioctl = ext4_compat_ioctl,
674d1f5273eSFan Yong #endif
675d1f5273eSFan Yong .fsync = ext4_sync_file,
676d1f5273eSFan Yong .release = ext4_release_dir,
677d1f5273eSFan Yong };
678