4 * Copyright (C) 1992, 1993, 1994, 1995
5 * Remy Card (card@masi.ibp.fr)
6 * Laboratoire MASI - Institut Blaise Pascal
7 * Universite Pierre et Marie Curie (Paris VI)
11 * linux/fs/minix/dir.c
13 * Copyright (C) 1991, 1992 Linus Torvalds
15 * ext4 directory handling functions
17 * Big-endian to little-endian byte-swapping/bitmaps by
18 * David S. Miller (davem@caip.rutgers.edu), 1995
20 * Hash Tree Directory indexing (c) 2001 Daniel Phillips
25 #include <linux/buffer_head.h>
26 #include <linux/slab.h>
30 static int ext4_dx_readdir(struct file
*, struct dir_context
*);
33 * Check if the given dir-inode refers to an htree-indexed directory
34 * (or a directory which could potentially get converted to use htree
37 * Return 1 if it is a dx dir, 0 if not
39 static int is_dx_dir(struct inode
*inode
)
41 struct super_block
*sb
= inode
->i_sb
;
43 if (EXT4_HAS_COMPAT_FEATURE(inode
->i_sb
,
44 EXT4_FEATURE_COMPAT_DIR_INDEX
) &&
45 ((ext4_test_inode_flag(inode
, EXT4_INODE_INDEX
)) ||
46 ((inode
->i_size
>> sb
->s_blocksize_bits
) == 1) ||
47 ext4_has_inline_data(inode
)))
54 * Return 0 if the directory entry is OK, and 1 if there is a problem
56 * Note: this is the opposite of what ext2 and ext3 historically returned...
58 * bh passed here can be an inode block or a dir data block, depending
59 * on the inode inline data flag.
61 int __ext4_check_dir_entry(const char *function
, unsigned int line
,
62 struct inode
*dir
, struct file
*filp
,
63 struct ext4_dir_entry_2
*de
,
64 struct buffer_head
*bh
, char *buf
, int size
,
67 const char *error_msg
= NULL
;
68 const int rlen
= ext4_rec_len_from_disk(de
->rec_len
,
69 dir
->i_sb
->s_blocksize
);
71 if (unlikely(rlen
< EXT4_DIR_REC_LEN(1)))
72 error_msg
= "rec_len is smaller than minimal";
73 else if (unlikely(rlen
% 4 != 0))
74 error_msg
= "rec_len % 4 != 0";
75 else if (unlikely(rlen
< EXT4_DIR_REC_LEN(de
->name_len
)))
76 error_msg
= "rec_len is too small for name_len";
77 else if (unlikely(((char *) de
- buf
) + rlen
> size
))
78 error_msg
= "directory entry across range";
79 else if (unlikely(le32_to_cpu(de
->inode
) >
80 le32_to_cpu(EXT4_SB(dir
->i_sb
)->s_es
->s_inodes_count
)))
81 error_msg
= "inode out of bounds";
86 ext4_error_file(filp
, function
, line
, bh
->b_blocknr
,
87 "bad entry in directory: %s - offset=%u(%u), "
88 "inode=%u, rec_len=%d, name_len=%d",
89 error_msg
, (unsigned) (offset
% size
),
90 offset
, le32_to_cpu(de
->inode
),
93 ext4_error_inode(dir
, function
, line
, bh
->b_blocknr
,
94 "bad entry in directory: %s - offset=%u(%u), "
95 "inode=%u, rec_len=%d, name_len=%d",
96 error_msg
, (unsigned) (offset
% size
),
97 offset
, le32_to_cpu(de
->inode
),
103 static int ext4_readdir(struct file
*file
, struct dir_context
*ctx
)
107 struct ext4_dir_entry_2
*de
;
109 struct inode
*inode
= file_inode(file
);
110 struct super_block
*sb
= inode
->i_sb
;
111 int dir_has_error
= 0;
113 if (is_dx_dir(inode
)) {
114 err
= ext4_dx_readdir(file
, ctx
);
115 if (err
!= ERR_BAD_DX_DIR
) {
119 * We don't set the inode dirty flag since it's not
120 * critical that it get flushed back to the disk.
122 ext4_clear_inode_flag(file_inode(file
),
126 if (ext4_has_inline_data(inode
)) {
127 int has_inline_data
= 1;
128 int ret
= ext4_read_inline_dir(file
, ctx
,
134 offset
= ctx
->pos
& (sb
->s_blocksize
- 1);
136 while (ctx
->pos
< inode
->i_size
) {
137 struct ext4_map_blocks map
;
138 struct buffer_head
*bh
= NULL
;
140 map
.m_lblk
= ctx
->pos
>> EXT4_BLOCK_SIZE_BITS(sb
);
142 err
= ext4_map_blocks(NULL
, inode
, &map
, 0);
144 pgoff_t index
= map
.m_pblk
>>
145 (PAGE_CACHE_SHIFT
- inode
->i_blkbits
);
146 if (!ra_has_index(&file
->f_ra
, index
))
147 page_cache_sync_readahead(
148 sb
->s_bdev
->bd_inode
->i_mapping
,
151 file
->f_ra
.prev_pos
= (loff_t
)index
<< PAGE_CACHE_SHIFT
;
152 bh
= ext4_bread(NULL
, inode
, map
.m_lblk
, 0);
158 if (!dir_has_error
) {
159 EXT4_ERROR_FILE(file
, 0,
160 "directory contains a "
161 "hole at offset %llu",
162 (unsigned long long) ctx
->pos
);
165 /* corrupt size? Maybe no more blocks to read */
166 if (ctx
->pos
> inode
->i_blocks
<< 9)
168 ctx
->pos
+= sb
->s_blocksize
- offset
;
172 /* Check the checksum */
173 if (!buffer_verified(bh
) &&
174 !ext4_dirent_csum_verify(inode
,
175 (struct ext4_dir_entry
*)bh
->b_data
)) {
176 EXT4_ERROR_FILE(file
, 0, "directory fails checksum "
178 (unsigned long long)ctx
->pos
);
179 ctx
->pos
+= sb
->s_blocksize
- offset
;
183 set_buffer_verified(bh
);
185 /* If the dir block has changed since the last call to
186 * readdir(2), then we might be pointing to an invalid
187 * dirent right now. Scan from the start of the block
189 if (file
->f_version
!= inode
->i_version
) {
190 for (i
= 0; i
< sb
->s_blocksize
&& i
< offset
; ) {
191 de
= (struct ext4_dir_entry_2
*)
193 /* It's too expensive to do a full
194 * dirent test each time round this
195 * loop, but we do have to test at
196 * least that it is non-zero. A
197 * failure will be detected in the
198 * dirent test below. */
199 if (ext4_rec_len_from_disk(de
->rec_len
,
200 sb
->s_blocksize
) < EXT4_DIR_REC_LEN(1))
202 i
+= ext4_rec_len_from_disk(de
->rec_len
,
206 ctx
->pos
= (ctx
->pos
& ~(sb
->s_blocksize
- 1))
208 file
->f_version
= inode
->i_version
;
211 while (ctx
->pos
< inode
->i_size
212 && offset
< sb
->s_blocksize
) {
213 de
= (struct ext4_dir_entry_2
*) (bh
->b_data
+ offset
);
214 if (ext4_check_dir_entry(inode
, file
, de
, bh
,
215 bh
->b_data
, bh
->b_size
,
218 * On error, skip to the next block
220 ctx
->pos
= (ctx
->pos
|
221 (sb
->s_blocksize
- 1)) + 1;
224 offset
+= ext4_rec_len_from_disk(de
->rec_len
,
226 if (le32_to_cpu(de
->inode
)) {
227 if (!dir_emit(ctx
, de
->name
,
229 le32_to_cpu(de
->inode
),
230 get_dtype(sb
, de
->file_type
))) {
235 ctx
->pos
+= ext4_rec_len_from_disk(de
->rec_len
,
240 if (ctx
->pos
< inode
->i_size
) {
241 if (!dir_relax(inode
))
248 static inline int is_32bit_api(void)
251 return is_compat_task();
253 return (BITS_PER_LONG
== 32);
258 * These functions convert from the major/minor hash to an f_pos
259 * value for dx directories
261 * Upper layer (for example NFS) should specify FMODE_32BITHASH or
262 * FMODE_64BITHASH explicitly. On the other hand, we allow ext4 to be mounted
263 * directly on both 32-bit and 64-bit nodes, under such case, neither
264 * FMODE_32BITHASH nor FMODE_64BITHASH is specified.
266 static inline loff_t
hash2pos(struct file
*filp
, __u32 major
, __u32 minor
)
268 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
269 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
272 return ((__u64
)(major
>> 1) << 32) | (__u64
)minor
;
275 static inline __u32
pos2maj_hash(struct file
*filp
, loff_t pos
)
277 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
278 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
279 return (pos
<< 1) & 0xffffffff;
281 return ((pos
>> 32) << 1) & 0xffffffff;
284 static inline __u32
pos2min_hash(struct file
*filp
, loff_t pos
)
286 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
287 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
290 return pos
& 0xffffffff;
294 * Return 32- or 64-bit end-of-file for dx directories
296 static inline loff_t
ext4_get_htree_eof(struct file
*filp
)
298 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
299 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
300 return EXT4_HTREE_EOF_32BIT
;
302 return EXT4_HTREE_EOF_64BIT
;
307 * ext4_dir_llseek() calls generic_file_llseek_size to handle htree
308 * directories, where the "offset" is in terms of the filename hash
309 * value instead of the byte offset.
311 * Because we may return a 64-bit hash that is well beyond offset limits,
312 * we need to pass the max hash as the maximum allowable offset in
313 * the htree directory case.
315 * For non-htree, ext4_llseek already chooses the proper max offset.
317 static loff_t
ext4_dir_llseek(struct file
*file
, loff_t offset
, int whence
)
319 struct inode
*inode
= file
->f_mapping
->host
;
320 int dx_dir
= is_dx_dir(inode
);
321 loff_t htree_max
= ext4_get_htree_eof(file
);
324 return generic_file_llseek_size(file
, offset
, whence
,
325 htree_max
, htree_max
);
327 return ext4_llseek(file
, offset
, whence
);
331 * This structure holds the nodes of the red-black tree used to store
332 * the directory entry in hash order.
337 struct rb_node rb_hash
;
346 * This functoin implements a non-recursive way of freeing all of the
347 * nodes in the red-black tree.
349 static void free_rb_tree_fname(struct rb_root
*root
)
351 struct fname
*fname
, *next
;
353 rbtree_postorder_for_each_entry_safe(fname
, next
, root
, rb_hash
)
355 struct fname
*old
= fname
;
364 static struct dir_private_info
*ext4_htree_create_dir_info(struct file
*filp
,
367 struct dir_private_info
*p
;
369 p
= kzalloc(sizeof(struct dir_private_info
), GFP_KERNEL
);
372 p
->curr_hash
= pos2maj_hash(filp
, pos
);
373 p
->curr_minor_hash
= pos2min_hash(filp
, pos
);
377 void ext4_htree_free_dir_info(struct dir_private_info
*p
)
379 free_rb_tree_fname(&p
->root
);
384 * Given a directory entry, enter it into the fname rb tree.
386 * When filename encryption is enabled, the dirent will hold the
387 * encrypted filename, while the htree will hold decrypted filename.
388 * The decrypted filename is passed in via ent_name. parameter.
390 int ext4_htree_store_dirent(struct file
*dir_file
, __u32 hash
,
392 struct ext4_dir_entry_2
*dirent
,
393 struct ext4_str
*ent_name
)
395 struct rb_node
**p
, *parent
= NULL
;
396 struct fname
*fname
, *new_fn
;
397 struct dir_private_info
*info
;
400 info
= dir_file
->private_data
;
401 p
= &info
->root
.rb_node
;
403 /* Create and allocate the fname structure */
404 len
= sizeof(struct fname
) + ent_name
->len
+ 1;
405 new_fn
= kzalloc(len
, GFP_KERNEL
);
409 new_fn
->minor_hash
= minor_hash
;
410 new_fn
->inode
= le32_to_cpu(dirent
->inode
);
411 new_fn
->name_len
= ent_name
->len
;
412 new_fn
->file_type
= dirent
->file_type
;
413 memcpy(new_fn
->name
, ent_name
->name
, ent_name
->len
);
414 new_fn
->name
[ent_name
->len
] = 0;
418 fname
= rb_entry(parent
, struct fname
, rb_hash
);
421 * If the hash and minor hash match up, then we put
422 * them on a linked list. This rarely happens...
424 if ((new_fn
->hash
== fname
->hash
) &&
425 (new_fn
->minor_hash
== fname
->minor_hash
)) {
426 new_fn
->next
= fname
->next
;
427 fname
->next
= new_fn
;
431 if (new_fn
->hash
< fname
->hash
)
433 else if (new_fn
->hash
> fname
->hash
)
435 else if (new_fn
->minor_hash
< fname
->minor_hash
)
437 else /* if (new_fn->minor_hash > fname->minor_hash) */
441 rb_link_node(&new_fn
->rb_hash
, parent
, p
);
442 rb_insert_color(&new_fn
->rb_hash
, &info
->root
);
449 * This is a helper function for ext4_dx_readdir. It calls filldir
450 * for all entres on the fname linked list. (Normally there is only
451 * one entry on the linked list, unless there are 62 bit hash collisions.)
453 static int call_filldir(struct file
*file
, struct dir_context
*ctx
,
456 struct dir_private_info
*info
= file
->private_data
;
457 struct inode
*inode
= file_inode(file
);
458 struct super_block
*sb
= inode
->i_sb
;
461 ext4_msg(sb
, KERN_ERR
, "%s:%d: inode #%lu: comm %s: "
462 "called with null fname?!?", __func__
, __LINE__
,
463 inode
->i_ino
, current
->comm
);
466 ctx
->pos
= hash2pos(file
, fname
->hash
, fname
->minor_hash
);
468 if (!dir_emit(ctx
, fname
->name
,
471 get_dtype(sb
, fname
->file_type
))) {
472 info
->extra_fname
= fname
;
480 static int ext4_dx_readdir(struct file
*file
, struct dir_context
*ctx
)
482 struct dir_private_info
*info
= file
->private_data
;
483 struct inode
*inode
= file_inode(file
);
488 info
= ext4_htree_create_dir_info(file
, ctx
->pos
);
491 file
->private_data
= info
;
494 if (ctx
->pos
== ext4_get_htree_eof(file
))
497 /* Some one has messed with f_pos; reset the world */
498 if (info
->last_pos
!= ctx
->pos
) {
499 free_rb_tree_fname(&info
->root
);
500 info
->curr_node
= NULL
;
501 info
->extra_fname
= NULL
;
502 info
->curr_hash
= pos2maj_hash(file
, ctx
->pos
);
503 info
->curr_minor_hash
= pos2min_hash(file
, ctx
->pos
);
507 * If there are any leftover names on the hash collision
508 * chain, return them first.
510 if (info
->extra_fname
) {
511 if (call_filldir(file
, ctx
, info
->extra_fname
))
513 info
->extra_fname
= NULL
;
515 } else if (!info
->curr_node
)
516 info
->curr_node
= rb_first(&info
->root
);
520 * Fill the rbtree if we have no more entries,
521 * or the inode has changed since we last read in the
524 if ((!info
->curr_node
) ||
525 (file
->f_version
!= inode
->i_version
)) {
526 info
->curr_node
= NULL
;
527 free_rb_tree_fname(&info
->root
);
528 file
->f_version
= inode
->i_version
;
529 ret
= ext4_htree_fill_tree(file
, info
->curr_hash
,
530 info
->curr_minor_hash
,
535 ctx
->pos
= ext4_get_htree_eof(file
);
538 info
->curr_node
= rb_first(&info
->root
);
541 fname
= rb_entry(info
->curr_node
, struct fname
, rb_hash
);
542 info
->curr_hash
= fname
->hash
;
543 info
->curr_minor_hash
= fname
->minor_hash
;
544 if (call_filldir(file
, ctx
, fname
))
547 info
->curr_node
= rb_next(info
->curr_node
);
548 if (info
->curr_node
) {
549 fname
= rb_entry(info
->curr_node
, struct fname
,
551 info
->curr_hash
= fname
->hash
;
552 info
->curr_minor_hash
= fname
->minor_hash
;
554 if (info
->next_hash
== ~0) {
555 ctx
->pos
= ext4_get_htree_eof(file
);
558 info
->curr_hash
= info
->next_hash
;
559 info
->curr_minor_hash
= 0;
563 info
->last_pos
= ctx
->pos
;
567 static int ext4_release_dir(struct inode
*inode
, struct file
*filp
)
569 if (filp
->private_data
)
570 ext4_htree_free_dir_info(filp
->private_data
);
575 int ext4_check_all_de(struct inode
*dir
, struct buffer_head
*bh
, void *buf
,
578 struct ext4_dir_entry_2
*de
;
580 unsigned int offset
= 0;
583 de
= (struct ext4_dir_entry_2
*)buf
;
584 top
= buf
+ buf_size
;
585 while ((char *) de
< top
) {
586 if (ext4_check_dir_entry(dir
, NULL
, de
, bh
,
587 buf
, buf_size
, offset
))
589 nlen
= EXT4_DIR_REC_LEN(de
->name_len
);
590 rlen
= ext4_rec_len_from_disk(de
->rec_len
, buf_size
);
591 de
= (struct ext4_dir_entry_2
*)((char *)de
+ rlen
);
594 if ((char *) de
> top
)
600 const struct file_operations ext4_dir_operations
= {
601 .llseek
= ext4_dir_llseek
,
602 .read
= generic_read_dir
,
603 .iterate
= ext4_readdir
,
604 .unlocked_ioctl
= ext4_ioctl
,
606 .compat_ioctl
= ext4_compat_ioctl
,
608 .fsync
= ext4_sync_file
,
609 .release
= ext4_release_dir
,