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/jbd2.h>
26 #include <linux/buffer_head.h>
27 #include <linux/slab.h>
28 #include <linux/rbtree.h>
31 static unsigned char ext4_filetype_table
[] = {
32 DT_UNKNOWN
, DT_REG
, DT_DIR
, DT_CHR
, DT_BLK
, DT_FIFO
, DT_SOCK
, DT_LNK
35 static int ext4_dx_readdir(struct file
*filp
,
36 void *dirent
, filldir_t filldir
);
38 static unsigned char get_dtype(struct super_block
*sb
, int filetype
)
40 if (!EXT4_HAS_INCOMPAT_FEATURE(sb
, EXT4_FEATURE_INCOMPAT_FILETYPE
) ||
41 (filetype
>= EXT4_FT_MAX
))
44 return (ext4_filetype_table
[filetype
]);
48 * Check if the given dir-inode refers to an htree-indexed directory
49 * (or a directory which chould potentially get coverted to use htree
52 * Return 1 if it is a dx dir, 0 if not
54 static int is_dx_dir(struct inode
*inode
)
56 struct super_block
*sb
= inode
->i_sb
;
58 if (EXT4_HAS_COMPAT_FEATURE(inode
->i_sb
,
59 EXT4_FEATURE_COMPAT_DIR_INDEX
) &&
60 ((ext4_test_inode_flag(inode
, EXT4_INODE_INDEX
)) ||
61 ((inode
->i_size
>> sb
->s_blocksize_bits
) == 1)))
68 * Return 0 if the directory entry is OK, and 1 if there is a problem
70 * Note: this is the opposite of what ext2 and ext3 historically returned...
72 int __ext4_check_dir_entry(const char *function
, unsigned int line
,
73 struct inode
*dir
, struct file
*filp
,
74 struct ext4_dir_entry_2
*de
,
75 struct buffer_head
*bh
,
78 const char *error_msg
= NULL
;
79 const int rlen
= ext4_rec_len_from_disk(de
->rec_len
,
80 dir
->i_sb
->s_blocksize
);
82 if (unlikely(rlen
< EXT4_DIR_REC_LEN(1)))
83 error_msg
= "rec_len is smaller than minimal";
84 else if (unlikely(rlen
% 4 != 0))
85 error_msg
= "rec_len % 4 != 0";
86 else if (unlikely(rlen
< EXT4_DIR_REC_LEN(de
->name_len
)))
87 error_msg
= "rec_len is too small for name_len";
88 else if (unlikely(((char *) de
- bh
->b_data
) + rlen
>
89 dir
->i_sb
->s_blocksize
))
90 error_msg
= "directory entry across blocks";
91 else if (unlikely(le32_to_cpu(de
->inode
) >
92 le32_to_cpu(EXT4_SB(dir
->i_sb
)->s_es
->s_inodes_count
)))
93 error_msg
= "inode out of bounds";
98 ext4_error_file(filp
, function
, line
, bh
->b_blocknr
,
99 "bad entry in directory: %s - offset=%u(%u), "
100 "inode=%u, rec_len=%d, name_len=%d",
101 error_msg
, (unsigned) (offset
% bh
->b_size
),
102 offset
, le32_to_cpu(de
->inode
),
105 ext4_error_inode(dir
, function
, line
, bh
->b_blocknr
,
106 "bad entry in directory: %s - offset=%u(%u), "
107 "inode=%u, rec_len=%d, name_len=%d",
108 error_msg
, (unsigned) (offset
% bh
->b_size
),
109 offset
, le32_to_cpu(de
->inode
),
115 static int ext4_readdir(struct file
*filp
,
116 void *dirent
, filldir_t filldir
)
121 struct ext4_dir_entry_2
*de
;
123 struct inode
*inode
= filp
->f_path
.dentry
->d_inode
;
124 struct super_block
*sb
= inode
->i_sb
;
126 int dir_has_error
= 0;
128 if (is_dx_dir(inode
)) {
129 err
= ext4_dx_readdir(filp
, dirent
, filldir
);
130 if (err
!= ERR_BAD_DX_DIR
) {
135 * We don't set the inode dirty flag since it's not
136 * critical that it get flushed back to the disk.
138 ext4_clear_inode_flag(filp
->f_path
.dentry
->d_inode
,
142 offset
= filp
->f_pos
& (sb
->s_blocksize
- 1);
144 while (!error
&& !stored
&& filp
->f_pos
< inode
->i_size
) {
145 struct ext4_map_blocks map
;
146 struct buffer_head
*bh
= NULL
;
148 map
.m_lblk
= filp
->f_pos
>> EXT4_BLOCK_SIZE_BITS(sb
);
150 err
= ext4_map_blocks(NULL
, inode
, &map
, 0);
152 pgoff_t index
= map
.m_pblk
>>
153 (PAGE_CACHE_SHIFT
- inode
->i_blkbits
);
154 if (!ra_has_index(&filp
->f_ra
, index
))
155 page_cache_sync_readahead(
156 sb
->s_bdev
->bd_inode
->i_mapping
,
159 filp
->f_ra
.prev_pos
= (loff_t
)index
<< PAGE_CACHE_SHIFT
;
160 bh
= ext4_bread(NULL
, inode
, map
.m_lblk
, 0, &err
);
164 * We ignore I/O errors on directories so users have a chance
165 * of recovering data when there's a bad sector
168 if (!dir_has_error
) {
169 EXT4_ERROR_FILE(filp
, 0,
170 "directory contains a "
171 "hole at offset %llu",
172 (unsigned long long) filp
->f_pos
);
175 /* corrupt size? Maybe no more blocks to read */
176 if (filp
->f_pos
> inode
->i_blocks
<< 9)
178 filp
->f_pos
+= sb
->s_blocksize
- offset
;
183 /* If the dir block has changed since the last call to
184 * readdir(2), then we might be pointing to an invalid
185 * dirent right now. Scan from the start of the block
187 if (filp
->f_version
!= inode
->i_version
) {
188 for (i
= 0; i
< sb
->s_blocksize
&& i
< offset
; ) {
189 de
= (struct ext4_dir_entry_2
*)
191 /* It's too expensive to do a full
192 * dirent test each time round this
193 * loop, but we do have to test at
194 * least that it is non-zero. A
195 * failure will be detected in the
196 * dirent test below. */
197 if (ext4_rec_len_from_disk(de
->rec_len
,
198 sb
->s_blocksize
) < EXT4_DIR_REC_LEN(1))
200 i
+= ext4_rec_len_from_disk(de
->rec_len
,
204 filp
->f_pos
= (filp
->f_pos
& ~(sb
->s_blocksize
- 1))
206 filp
->f_version
= inode
->i_version
;
209 while (!error
&& filp
->f_pos
< inode
->i_size
210 && offset
< sb
->s_blocksize
) {
211 de
= (struct ext4_dir_entry_2
*) (bh
->b_data
+ offset
);
212 if (ext4_check_dir_entry(inode
, filp
, de
,
215 * On error, skip the f_pos to the next block
217 filp
->f_pos
= (filp
->f_pos
|
218 (sb
->s_blocksize
- 1)) + 1;
223 offset
+= ext4_rec_len_from_disk(de
->rec_len
,
225 if (le32_to_cpu(de
->inode
)) {
226 /* We might block in the next section
227 * if the data destination is
228 * currently swapped out. So, use a
229 * version stamp to detect whether or
230 * not the directory has been modified
231 * during the copy operation.
233 u64 version
= filp
->f_version
;
235 error
= filldir(dirent
, de
->name
,
238 le32_to_cpu(de
->inode
),
239 get_dtype(sb
, de
->file_type
));
242 if (version
!= filp
->f_version
)
246 filp
->f_pos
+= ext4_rec_len_from_disk(de
->rec_len
,
256 static inline int is_32bit_api(void)
259 return is_compat_task();
261 return (BITS_PER_LONG
== 32);
266 * These functions convert from the major/minor hash to an f_pos
267 * value for dx directories
269 * Upper layer (for example NFS) should specify FMODE_32BITHASH or
270 * FMODE_64BITHASH explicitly. On the other hand, we allow ext4 to be mounted
271 * directly on both 32-bit and 64-bit nodes, under such case, neither
272 * FMODE_32BITHASH nor FMODE_64BITHASH is specified.
274 static inline loff_t
hash2pos(struct file
*filp
, __u32 major
, __u32 minor
)
276 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
277 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
280 return ((__u64
)(major
>> 1) << 32) | (__u64
)minor
;
283 static inline __u32
pos2maj_hash(struct file
*filp
, loff_t pos
)
285 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
286 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
287 return (pos
<< 1) & 0xffffffff;
289 return ((pos
>> 32) << 1) & 0xffffffff;
292 static inline __u32
pos2min_hash(struct file
*filp
, loff_t pos
)
294 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
295 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
298 return pos
& 0xffffffff;
302 * Return 32- or 64-bit end-of-file for dx directories
304 static inline loff_t
ext4_get_htree_eof(struct file
*filp
)
306 if ((filp
->f_mode
& FMODE_32BITHASH
) ||
307 (!(filp
->f_mode
& FMODE_64BITHASH
) && is_32bit_api()))
308 return EXT4_HTREE_EOF_32BIT
;
310 return EXT4_HTREE_EOF_64BIT
;
315 * ext4_dir_llseek() based on generic_file_llseek() to handle both
316 * non-htree and htree directories, where the "offset" is in terms
317 * of the filename hash value instead of the byte offset.
319 * NOTE: offsets obtained *before* ext4_set_inode_flag(dir, EXT4_INODE_INDEX)
320 * will be invalid once the directory was converted into a dx directory
322 loff_t
ext4_dir_llseek(struct file
*file
, loff_t offset
, int origin
)
324 struct inode
*inode
= file
->f_mapping
->host
;
325 loff_t ret
= -EINVAL
;
326 int dx_dir
= is_dx_dir(inode
);
328 mutex_lock(&inode
->i_mutex
);
330 /* NOTE: relative offsets with dx directories might not work
331 * as expected, as it is difficult to figure out the
332 * correct offset between dx hashes */
336 if (unlikely(offset
> 0))
337 goto out_err
; /* not supported for directories */
339 /* so only negative offsets are left, does that have a
340 * meaning for directories at all? */
342 offset
+= ext4_get_htree_eof(file
);
344 offset
+= inode
->i_size
;
348 * Here we special-case the lseek(fd, 0, SEEK_CUR)
349 * position-querying operation. Avoid rewriting the "same"
350 * f_pos value back to the file because a concurrent read(),
351 * write() or lseek() might have altered it
354 offset
= file
->f_pos
;
358 offset
+= file
->f_pos
;
362 if (unlikely(offset
< 0))
366 if (offset
> inode
->i_sb
->s_maxbytes
)
368 } else if (offset
> ext4_get_htree_eof(file
))
371 /* Special lock needed here? */
372 if (offset
!= file
->f_pos
) {
373 file
->f_pos
= offset
;
380 mutex_unlock(&inode
->i_mutex
);
386 * This structure holds the nodes of the red-black tree used to store
387 * the directory entry in hash order.
392 struct rb_node rb_hash
;
401 * This functoin implements a non-recursive way of freeing all of the
402 * nodes in the red-black tree.
404 static void free_rb_tree_fname(struct rb_root
*root
)
406 struct rb_node
*n
= root
->rb_node
;
407 struct rb_node
*parent
;
411 /* Do the node's children first */
421 * The node has no children; free it, and then zero
422 * out parent's link to it. Finally go to the
423 * beginning of the loop and try to free the parent
426 parent
= rb_parent(n
);
427 fname
= rb_entry(n
, struct fname
, rb_hash
);
429 struct fname
*old
= fname
;
435 else if (parent
->rb_left
== n
)
436 parent
->rb_left
= NULL
;
437 else if (parent
->rb_right
== n
)
438 parent
->rb_right
= NULL
;
444 static struct dir_private_info
*ext4_htree_create_dir_info(struct file
*filp
,
447 struct dir_private_info
*p
;
449 p
= kzalloc(sizeof(struct dir_private_info
), GFP_KERNEL
);
452 p
->curr_hash
= pos2maj_hash(filp
, pos
);
453 p
->curr_minor_hash
= pos2min_hash(filp
, pos
);
457 void ext4_htree_free_dir_info(struct dir_private_info
*p
)
459 free_rb_tree_fname(&p
->root
);
464 * Given a directory entry, enter it into the fname rb tree.
466 int ext4_htree_store_dirent(struct file
*dir_file
, __u32 hash
,
468 struct ext4_dir_entry_2
*dirent
)
470 struct rb_node
**p
, *parent
= NULL
;
471 struct fname
*fname
, *new_fn
;
472 struct dir_private_info
*info
;
475 info
= dir_file
->private_data
;
476 p
= &info
->root
.rb_node
;
478 /* Create and allocate the fname structure */
479 len
= sizeof(struct fname
) + dirent
->name_len
+ 1;
480 new_fn
= kzalloc(len
, GFP_KERNEL
);
484 new_fn
->minor_hash
= minor_hash
;
485 new_fn
->inode
= le32_to_cpu(dirent
->inode
);
486 new_fn
->name_len
= dirent
->name_len
;
487 new_fn
->file_type
= dirent
->file_type
;
488 memcpy(new_fn
->name
, dirent
->name
, dirent
->name_len
);
489 new_fn
->name
[dirent
->name_len
] = 0;
493 fname
= rb_entry(parent
, struct fname
, rb_hash
);
496 * If the hash and minor hash match up, then we put
497 * them on a linked list. This rarely happens...
499 if ((new_fn
->hash
== fname
->hash
) &&
500 (new_fn
->minor_hash
== fname
->minor_hash
)) {
501 new_fn
->next
= fname
->next
;
502 fname
->next
= new_fn
;
506 if (new_fn
->hash
< fname
->hash
)
508 else if (new_fn
->hash
> fname
->hash
)
510 else if (new_fn
->minor_hash
< fname
->minor_hash
)
512 else /* if (new_fn->minor_hash > fname->minor_hash) */
516 rb_link_node(&new_fn
->rb_hash
, parent
, p
);
517 rb_insert_color(&new_fn
->rb_hash
, &info
->root
);
524 * This is a helper function for ext4_dx_readdir. It calls filldir
525 * for all entres on the fname linked list. (Normally there is only
526 * one entry on the linked list, unless there are 62 bit hash collisions.)
528 static int call_filldir(struct file
*filp
, void *dirent
,
529 filldir_t filldir
, struct fname
*fname
)
531 struct dir_private_info
*info
= filp
->private_data
;
533 struct inode
*inode
= filp
->f_path
.dentry
->d_inode
;
534 struct super_block
*sb
;
540 ext4_msg(sb
, KERN_ERR
, "%s:%d: inode #%lu: comm %s: "
541 "called with null fname?!?", __func__
, __LINE__
,
542 inode
->i_ino
, current
->comm
);
545 curr_pos
= hash2pos(filp
, fname
->hash
, fname
->minor_hash
);
547 error
= filldir(dirent
, fname
->name
,
548 fname
->name_len
, curr_pos
,
550 get_dtype(sb
, fname
->file_type
));
552 filp
->f_pos
= curr_pos
;
553 info
->extra_fname
= fname
;
561 static int ext4_dx_readdir(struct file
*filp
,
562 void *dirent
, filldir_t filldir
)
564 struct dir_private_info
*info
= filp
->private_data
;
565 struct inode
*inode
= filp
->f_path
.dentry
->d_inode
;
570 info
= ext4_htree_create_dir_info(filp
, filp
->f_pos
);
573 filp
->private_data
= info
;
576 if (filp
->f_pos
== ext4_get_htree_eof(filp
))
579 /* Some one has messed with f_pos; reset the world */
580 if (info
->last_pos
!= filp
->f_pos
) {
581 free_rb_tree_fname(&info
->root
);
582 info
->curr_node
= NULL
;
583 info
->extra_fname
= NULL
;
584 info
->curr_hash
= pos2maj_hash(filp
, filp
->f_pos
);
585 info
->curr_minor_hash
= pos2min_hash(filp
, filp
->f_pos
);
589 * If there are any leftover names on the hash collision
590 * chain, return them first.
592 if (info
->extra_fname
) {
593 if (call_filldir(filp
, dirent
, filldir
, info
->extra_fname
))
595 info
->extra_fname
= NULL
;
597 } else if (!info
->curr_node
)
598 info
->curr_node
= rb_first(&info
->root
);
602 * Fill the rbtree if we have no more entries,
603 * or the inode has changed since we last read in the
606 if ((!info
->curr_node
) ||
607 (filp
->f_version
!= inode
->i_version
)) {
608 info
->curr_node
= NULL
;
609 free_rb_tree_fname(&info
->root
);
610 filp
->f_version
= inode
->i_version
;
611 ret
= ext4_htree_fill_tree(filp
, info
->curr_hash
,
612 info
->curr_minor_hash
,
617 filp
->f_pos
= ext4_get_htree_eof(filp
);
620 info
->curr_node
= rb_first(&info
->root
);
623 fname
= rb_entry(info
->curr_node
, struct fname
, rb_hash
);
624 info
->curr_hash
= fname
->hash
;
625 info
->curr_minor_hash
= fname
->minor_hash
;
626 if (call_filldir(filp
, dirent
, filldir
, fname
))
629 info
->curr_node
= rb_next(info
->curr_node
);
630 if (info
->curr_node
) {
631 fname
= rb_entry(info
->curr_node
, struct fname
,
633 info
->curr_hash
= fname
->hash
;
634 info
->curr_minor_hash
= fname
->minor_hash
;
636 if (info
->next_hash
== ~0) {
637 filp
->f_pos
= ext4_get_htree_eof(filp
);
640 info
->curr_hash
= info
->next_hash
;
641 info
->curr_minor_hash
= 0;
645 info
->last_pos
= filp
->f_pos
;
649 static int ext4_release_dir(struct inode
*inode
, struct file
*filp
)
651 if (filp
->private_data
)
652 ext4_htree_free_dir_info(filp
->private_data
);
657 const struct file_operations ext4_dir_operations
= {
658 .llseek
= ext4_dir_llseek
,
659 .read
= generic_read_dir
,
660 .readdir
= ext4_readdir
,
661 .unlocked_ioctl
= ext4_ioctl
,
663 .compat_ioctl
= ext4_compat_ioctl
,
665 .fsync
= ext4_sync_file
,
666 .release
= ext4_release_dir
,