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 * ext2 directory handling functions
17 * Big-endian to little-endian byte-swapping/bitmaps by
18 * David S. Miller (davem@caip.rutgers.edu), 1995
20 * All code that works with directory layout had been switched to pagecache
25 #include <linux/buffer_head.h>
26 #include <linux/pagemap.h>
27 #include <linux/swap.h>
29 typedef struct ext2_dir_entry_2 ext2_dirent
;
32 * Tests against MAX_REC_LEN etc were put in place for 64k block
33 * sizes; if that is not possible on this arch, we can skip
34 * those tests and speed things up.
36 static inline unsigned ext2_rec_len_from_disk(__le16 dlen
)
38 unsigned len
= le16_to_cpu(dlen
);
40 #if (PAGE_SIZE >= 65536)
41 if (len
== EXT2_MAX_REC_LEN
)
47 static inline __le16
ext2_rec_len_to_disk(unsigned len
)
49 #if (PAGE_SIZE >= 65536)
51 return cpu_to_le16(EXT2_MAX_REC_LEN
);
53 BUG_ON(len
> (1 << 16));
55 return cpu_to_le16(len
);
59 * ext2 uses block-sized chunks. Arguably, sector-sized ones would be
60 * more robust, but we have what we have
62 static inline unsigned ext2_chunk_size(struct inode
*inode
)
64 return inode
->i_sb
->s_blocksize
;
67 static inline void ext2_put_page(struct page
*page
)
74 * Return the offset into page `page_nr' of the last valid
75 * byte in that page, plus one.
78 ext2_last_byte(struct inode
*inode
, unsigned long page_nr
)
80 unsigned last_byte
= inode
->i_size
;
82 last_byte
-= page_nr
<< PAGE_SHIFT
;
83 if (last_byte
> PAGE_SIZE
)
84 last_byte
= PAGE_SIZE
;
88 static int ext2_commit_chunk(struct page
*page
, loff_t pos
, unsigned len
)
90 struct address_space
*mapping
= page
->mapping
;
91 struct inode
*dir
= mapping
->host
;
95 block_write_end(NULL
, mapping
, pos
, len
, len
, page
, NULL
);
97 if (pos
+len
> dir
->i_size
) {
98 i_size_write(dir
, pos
+len
);
99 mark_inode_dirty(dir
);
102 if (IS_DIRSYNC(dir
)) {
103 err
= write_one_page(page
, 1);
105 err
= sync_inode_metadata(dir
, 1);
113 static bool ext2_check_page(struct page
*page
, int quiet
)
115 struct inode
*dir
= page
->mapping
->host
;
116 struct super_block
*sb
= dir
->i_sb
;
117 unsigned chunk_size
= ext2_chunk_size(dir
);
118 char *kaddr
= page_address(page
);
119 u32 max_inumber
= le32_to_cpu(EXT2_SB(sb
)->s_es
->s_inodes_count
);
120 unsigned offs
, rec_len
;
121 unsigned limit
= PAGE_SIZE
;
125 if ((dir
->i_size
>> PAGE_SHIFT
) == page
->index
) {
126 limit
= dir
->i_size
& ~PAGE_MASK
;
127 if (limit
& (chunk_size
- 1))
132 for (offs
= 0; offs
<= limit
- EXT2_DIR_REC_LEN(1); offs
+= rec_len
) {
133 p
= (ext2_dirent
*)(kaddr
+ offs
);
134 rec_len
= ext2_rec_len_from_disk(p
->rec_len
);
136 if (unlikely(rec_len
< EXT2_DIR_REC_LEN(1)))
138 if (unlikely(rec_len
& 3))
140 if (unlikely(rec_len
< EXT2_DIR_REC_LEN(p
->name_len
)))
142 if (unlikely(((offs
+ rec_len
- 1) ^ offs
) & ~(chunk_size
-1)))
144 if (unlikely(le32_to_cpu(p
->inode
) > max_inumber
))
150 SetPageChecked(page
);
153 /* Too bad, we had an error */
157 ext2_error(sb
, __func__
,
158 "size of directory #%lu is not a multiple "
159 "of chunk size", dir
->i_ino
);
162 error
= "rec_len is smaller than minimal";
165 error
= "unaligned directory entry";
168 error
= "rec_len is too small for name_len";
171 error
= "directory entry across blocks";
174 error
= "inode out of bounds";
177 ext2_error(sb
, __func__
, "bad entry in directory #%lu: : %s - "
178 "offset=%lu, inode=%lu, rec_len=%d, name_len=%d",
179 dir
->i_ino
, error
, (page
->index
<<PAGE_SHIFT
)+offs
,
180 (unsigned long) le32_to_cpu(p
->inode
),
181 rec_len
, p
->name_len
);
185 p
= (ext2_dirent
*)(kaddr
+ offs
);
186 ext2_error(sb
, "ext2_check_page",
187 "entry in directory #%lu spans the page boundary"
188 "offset=%lu, inode=%lu",
189 dir
->i_ino
, (page
->index
<<PAGE_SHIFT
)+offs
,
190 (unsigned long) le32_to_cpu(p
->inode
));
197 static struct page
* ext2_get_page(struct inode
*dir
, unsigned long n
,
200 struct address_space
*mapping
= dir
->i_mapping
;
201 struct page
*page
= read_mapping_page(mapping
, n
, NULL
);
204 if (unlikely(!PageChecked(page
))) {
205 if (PageError(page
) || !ext2_check_page(page
, quiet
))
213 return ERR_PTR(-EIO
);
217 * NOTE! unlike strncmp, ext2_match returns 1 for success, 0 for failure.
219 * len <= EXT2_NAME_LEN and de != NULL are guaranteed by caller.
221 static inline int ext2_match (int len
, const char * const name
,
222 struct ext2_dir_entry_2
* de
)
224 if (len
!= de
->name_len
)
228 return !memcmp(name
, de
->name
, len
);
232 * p is at least 6 bytes before the end of page
234 static inline ext2_dirent
*ext2_next_entry(ext2_dirent
*p
)
236 return (ext2_dirent
*)((char *)p
+
237 ext2_rec_len_from_disk(p
->rec_len
));
240 static inline unsigned
241 ext2_validate_entry(char *base
, unsigned offset
, unsigned mask
)
243 ext2_dirent
*de
= (ext2_dirent
*)(base
+ offset
);
244 ext2_dirent
*p
= (ext2_dirent
*)(base
+ (offset
&mask
));
245 while ((char*)p
< (char*)de
) {
248 p
= ext2_next_entry(p
);
250 return (char *)p
- base
;
253 static unsigned char ext2_filetype_table
[EXT2_FT_MAX
] = {
254 [EXT2_FT_UNKNOWN
] = DT_UNKNOWN
,
255 [EXT2_FT_REG_FILE
] = DT_REG
,
256 [EXT2_FT_DIR
] = DT_DIR
,
257 [EXT2_FT_CHRDEV
] = DT_CHR
,
258 [EXT2_FT_BLKDEV
] = DT_BLK
,
259 [EXT2_FT_FIFO
] = DT_FIFO
,
260 [EXT2_FT_SOCK
] = DT_SOCK
,
261 [EXT2_FT_SYMLINK
] = DT_LNK
,
265 static unsigned char ext2_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
266 [S_IFREG
>> S_SHIFT
] = EXT2_FT_REG_FILE
,
267 [S_IFDIR
>> S_SHIFT
] = EXT2_FT_DIR
,
268 [S_IFCHR
>> S_SHIFT
] = EXT2_FT_CHRDEV
,
269 [S_IFBLK
>> S_SHIFT
] = EXT2_FT_BLKDEV
,
270 [S_IFIFO
>> S_SHIFT
] = EXT2_FT_FIFO
,
271 [S_IFSOCK
>> S_SHIFT
] = EXT2_FT_SOCK
,
272 [S_IFLNK
>> S_SHIFT
] = EXT2_FT_SYMLINK
,
275 static inline void ext2_set_de_type(ext2_dirent
*de
, struct inode
*inode
)
277 umode_t mode
= inode
->i_mode
;
278 if (EXT2_HAS_INCOMPAT_FEATURE(inode
->i_sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
))
279 de
->file_type
= ext2_type_by_mode
[(mode
& S_IFMT
)>>S_SHIFT
];
285 ext2_readdir(struct file
*file
, struct dir_context
*ctx
)
287 loff_t pos
= ctx
->pos
;
288 struct inode
*inode
= file_inode(file
);
289 struct super_block
*sb
= inode
->i_sb
;
290 unsigned int offset
= pos
& ~PAGE_MASK
;
291 unsigned long n
= pos
>> PAGE_SHIFT
;
292 unsigned long npages
= dir_pages(inode
);
293 unsigned chunk_mask
= ~(ext2_chunk_size(inode
)-1);
294 unsigned char *types
= NULL
;
295 int need_revalidate
= file
->f_version
!= inode
->i_version
;
297 if (pos
> inode
->i_size
- EXT2_DIR_REC_LEN(1))
300 if (EXT2_HAS_INCOMPAT_FEATURE(sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
))
301 types
= ext2_filetype_table
;
303 for ( ; n
< npages
; n
++, offset
= 0) {
306 struct page
*page
= ext2_get_page(inode
, n
, 0);
309 ext2_error(sb
, __func__
,
312 ctx
->pos
+= PAGE_SIZE
- offset
;
313 return PTR_ERR(page
);
315 kaddr
= page_address(page
);
316 if (unlikely(need_revalidate
)) {
318 offset
= ext2_validate_entry(kaddr
, offset
, chunk_mask
);
319 ctx
->pos
= (n
<<PAGE_SHIFT
) + offset
;
321 file
->f_version
= inode
->i_version
;
324 de
= (ext2_dirent
*)(kaddr
+offset
);
325 limit
= kaddr
+ ext2_last_byte(inode
, n
) - EXT2_DIR_REC_LEN(1);
326 for ( ;(char*)de
<= limit
; de
= ext2_next_entry(de
)) {
327 if (de
->rec_len
== 0) {
328 ext2_error(sb
, __func__
,
329 "zero-length directory entry");
334 unsigned char d_type
= DT_UNKNOWN
;
336 if (types
&& de
->file_type
< EXT2_FT_MAX
)
337 d_type
= types
[de
->file_type
];
339 if (!dir_emit(ctx
, de
->name
, de
->name_len
,
340 le32_to_cpu(de
->inode
),
346 ctx
->pos
+= ext2_rec_len_from_disk(de
->rec_len
);
356 * finds an entry in the specified directory with the wanted name. It
357 * returns the page in which the entry was found (as a parameter - res_page),
358 * and the entry itself. Page is returned mapped and unlocked.
359 * Entry is guaranteed to be valid.
361 struct ext2_dir_entry_2
*ext2_find_entry (struct inode
*dir
,
362 const struct qstr
*child
, struct page
**res_page
)
364 const char *name
= child
->name
;
365 int namelen
= child
->len
;
366 unsigned reclen
= EXT2_DIR_REC_LEN(namelen
);
367 unsigned long start
, n
;
368 unsigned long npages
= dir_pages(dir
);
369 struct page
*page
= NULL
;
370 struct ext2_inode_info
*ei
= EXT2_I(dir
);
372 int dir_has_error
= 0;
380 start
= ei
->i_dir_start_lookup
;
386 page
= ext2_get_page(dir
, n
, dir_has_error
);
388 kaddr
= page_address(page
);
389 de
= (ext2_dirent
*) kaddr
;
390 kaddr
+= ext2_last_byte(dir
, n
) - reclen
;
391 while ((char *) de
<= kaddr
) {
392 if (de
->rec_len
== 0) {
393 ext2_error(dir
->i_sb
, __func__
,
394 "zero-length directory entry");
398 if (ext2_match (namelen
, name
, de
))
400 de
= ext2_next_entry(de
);
408 /* next page is past the blocks we've got */
409 if (unlikely(n
> (dir
->i_blocks
>> (PAGE_SHIFT
- 9)))) {
410 ext2_error(dir
->i_sb
, __func__
,
411 "dir %lu size %lld exceeds block count %llu",
412 dir
->i_ino
, dir
->i_size
,
413 (unsigned long long)dir
->i_blocks
);
416 } while (n
!= start
);
422 ei
->i_dir_start_lookup
= n
;
426 struct ext2_dir_entry_2
* ext2_dotdot (struct inode
*dir
, struct page
**p
)
428 struct page
*page
= ext2_get_page(dir
, 0, 0);
429 ext2_dirent
*de
= NULL
;
432 de
= ext2_next_entry((ext2_dirent
*) page_address(page
));
438 ino_t
ext2_inode_by_name(struct inode
*dir
, const struct qstr
*child
)
441 struct ext2_dir_entry_2
*de
;
444 de
= ext2_find_entry (dir
, child
, &page
);
446 res
= le32_to_cpu(de
->inode
);
452 static int ext2_prepare_chunk(struct page
*page
, loff_t pos
, unsigned len
)
454 return __block_write_begin(page
, pos
, len
, ext2_get_block
);
457 /* Releases the page */
458 void ext2_set_link(struct inode
*dir
, struct ext2_dir_entry_2
*de
,
459 struct page
*page
, struct inode
*inode
, int update_times
)
461 loff_t pos
= page_offset(page
) +
462 (char *) de
- (char *) page_address(page
);
463 unsigned len
= ext2_rec_len_from_disk(de
->rec_len
);
467 err
= ext2_prepare_chunk(page
, pos
, len
);
469 de
->inode
= cpu_to_le32(inode
->i_ino
);
470 ext2_set_de_type(de
, inode
);
471 err
= ext2_commit_chunk(page
, pos
, len
);
474 dir
->i_mtime
= dir
->i_ctime
= current_time(dir
);
475 EXT2_I(dir
)->i_flags
&= ~EXT2_BTREE_FL
;
476 mark_inode_dirty(dir
);
482 int ext2_add_link (struct dentry
*dentry
, struct inode
*inode
)
484 struct inode
*dir
= d_inode(dentry
->d_parent
);
485 const char *name
= dentry
->d_name
.name
;
486 int namelen
= dentry
->d_name
.len
;
487 unsigned chunk_size
= ext2_chunk_size(dir
);
488 unsigned reclen
= EXT2_DIR_REC_LEN(namelen
);
489 unsigned short rec_len
, name_len
;
490 struct page
*page
= NULL
;
492 unsigned long npages
= dir_pages(dir
);
499 * We take care of directory expansion in the same loop.
500 * This code plays outside i_size, so it locks the page
501 * to protect that region.
503 for (n
= 0; n
<= npages
; n
++) {
506 page
= ext2_get_page(dir
, n
, 0);
511 kaddr
= page_address(page
);
512 dir_end
= kaddr
+ ext2_last_byte(dir
, n
);
513 de
= (ext2_dirent
*)kaddr
;
514 kaddr
+= PAGE_SIZE
- reclen
;
515 while ((char *)de
<= kaddr
) {
516 if ((char *)de
== dir_end
) {
519 rec_len
= chunk_size
;
520 de
->rec_len
= ext2_rec_len_to_disk(chunk_size
);
524 if (de
->rec_len
== 0) {
525 ext2_error(dir
->i_sb
, __func__
,
526 "zero-length directory entry");
531 if (ext2_match (namelen
, name
, de
))
533 name_len
= EXT2_DIR_REC_LEN(de
->name_len
);
534 rec_len
= ext2_rec_len_from_disk(de
->rec_len
);
535 if (!de
->inode
&& rec_len
>= reclen
)
537 if (rec_len
>= name_len
+ reclen
)
539 de
= (ext2_dirent
*) ((char *) de
+ rec_len
);
548 pos
= page_offset(page
) +
549 (char*)de
- (char*)page_address(page
);
550 err
= ext2_prepare_chunk(page
, pos
, rec_len
);
554 ext2_dirent
*de1
= (ext2_dirent
*) ((char *) de
+ name_len
);
555 de1
->rec_len
= ext2_rec_len_to_disk(rec_len
- name_len
);
556 de
->rec_len
= ext2_rec_len_to_disk(name_len
);
559 de
->name_len
= namelen
;
560 memcpy(de
->name
, name
, namelen
);
561 de
->inode
= cpu_to_le32(inode
->i_ino
);
562 ext2_set_de_type (de
, inode
);
563 err
= ext2_commit_chunk(page
, pos
, rec_len
);
564 dir
->i_mtime
= dir
->i_ctime
= current_time(dir
);
565 EXT2_I(dir
)->i_flags
&= ~EXT2_BTREE_FL
;
566 mark_inode_dirty(dir
);
578 * ext2_delete_entry deletes a directory entry by merging it with the
579 * previous entry. Page is up-to-date. Releases the page.
581 int ext2_delete_entry (struct ext2_dir_entry_2
* dir
, struct page
* page
)
583 struct inode
*inode
= page
->mapping
->host
;
584 char *kaddr
= page_address(page
);
585 unsigned from
= ((char*)dir
- kaddr
) & ~(ext2_chunk_size(inode
)-1);
586 unsigned to
= ((char *)dir
- kaddr
) +
587 ext2_rec_len_from_disk(dir
->rec_len
);
589 ext2_dirent
* pde
= NULL
;
590 ext2_dirent
* de
= (ext2_dirent
*) (kaddr
+ from
);
593 while ((char*)de
< (char*)dir
) {
594 if (de
->rec_len
== 0) {
595 ext2_error(inode
->i_sb
, __func__
,
596 "zero-length directory entry");
601 de
= ext2_next_entry(de
);
604 from
= (char*)pde
- (char*)page_address(page
);
605 pos
= page_offset(page
) + from
;
607 err
= ext2_prepare_chunk(page
, pos
, to
- from
);
610 pde
->rec_len
= ext2_rec_len_to_disk(to
- from
);
612 err
= ext2_commit_chunk(page
, pos
, to
- from
);
613 inode
->i_ctime
= inode
->i_mtime
= current_time(inode
);
614 EXT2_I(inode
)->i_flags
&= ~EXT2_BTREE_FL
;
615 mark_inode_dirty(inode
);
622 * Set the first fragment of directory.
624 int ext2_make_empty(struct inode
*inode
, struct inode
*parent
)
626 struct page
*page
= grab_cache_page(inode
->i_mapping
, 0);
627 unsigned chunk_size
= ext2_chunk_size(inode
);
628 struct ext2_dir_entry_2
* de
;
635 err
= ext2_prepare_chunk(page
, 0, chunk_size
);
640 kaddr
= kmap_atomic(page
);
641 memset(kaddr
, 0, chunk_size
);
642 de
= (struct ext2_dir_entry_2
*)kaddr
;
644 de
->rec_len
= ext2_rec_len_to_disk(EXT2_DIR_REC_LEN(1));
645 memcpy (de
->name
, ".\0\0", 4);
646 de
->inode
= cpu_to_le32(inode
->i_ino
);
647 ext2_set_de_type (de
, inode
);
649 de
= (struct ext2_dir_entry_2
*)(kaddr
+ EXT2_DIR_REC_LEN(1));
651 de
->rec_len
= ext2_rec_len_to_disk(chunk_size
- EXT2_DIR_REC_LEN(1));
652 de
->inode
= cpu_to_le32(parent
->i_ino
);
653 memcpy (de
->name
, "..\0", 4);
654 ext2_set_de_type (de
, inode
);
655 kunmap_atomic(kaddr
);
656 err
= ext2_commit_chunk(page
, 0, chunk_size
);
663 * routine to check that the specified directory is empty (for rmdir)
665 int ext2_empty_dir (struct inode
* inode
)
667 struct page
*page
= NULL
;
668 unsigned long i
, npages
= dir_pages(inode
);
669 int dir_has_error
= 0;
671 for (i
= 0; i
< npages
; i
++) {
674 page
= ext2_get_page(inode
, i
, dir_has_error
);
681 kaddr
= page_address(page
);
682 de
= (ext2_dirent
*)kaddr
;
683 kaddr
+= ext2_last_byte(inode
, i
) - EXT2_DIR_REC_LEN(1);
685 while ((char *)de
<= kaddr
) {
686 if (de
->rec_len
== 0) {
687 ext2_error(inode
->i_sb
, __func__
,
688 "zero-length directory entry");
689 printk("kaddr=%p, de=%p\n", kaddr
, de
);
692 if (de
->inode
!= 0) {
693 /* check for . and .. */
694 if (de
->name
[0] != '.')
696 if (de
->name_len
> 2)
698 if (de
->name_len
< 2) {
700 cpu_to_le32(inode
->i_ino
))
702 } else if (de
->name
[1] != '.')
705 de
= ext2_next_entry(de
);
716 const struct file_operations ext2_dir_operations
= {
717 .llseek
= generic_file_llseek
,
718 .read
= generic_read_dir
,
719 .iterate_shared
= ext2_readdir
,
720 .unlocked_ioctl
= ext2_ioctl
,
722 .compat_ioctl
= ext2_compat_ioctl
,