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/pagemap.h>
26 #include <linux/smp_lock.h>
28 typedef struct ext2_dir_entry_2 ext2_dirent
;
31 * ext2 uses block-sized chunks. Arguably, sector-sized ones would be
32 * more robust, but we have what we have
34 static inline unsigned ext2_chunk_size(struct inode
*inode
)
36 return inode
->i_sb
->s_blocksize
;
39 static inline void ext2_put_page(struct page
*page
)
42 page_cache_release(page
);
45 static inline unsigned long dir_pages(struct inode
*inode
)
47 return (inode
->i_size
+PAGE_CACHE_SIZE
-1)>>PAGE_CACHE_SHIFT
;
51 * Return the offset into page `page_nr' of the last valid
52 * byte in that page, plus one.
55 ext2_last_byte(struct inode
*inode
, unsigned long page_nr
)
57 unsigned last_byte
= inode
->i_size
;
59 last_byte
-= page_nr
<< PAGE_CACHE_SHIFT
;
60 if (last_byte
> PAGE_CACHE_SIZE
)
61 last_byte
= PAGE_CACHE_SIZE
;
65 static int ext2_commit_chunk(struct page
*page
, unsigned from
, unsigned to
)
67 struct inode
*dir
= page
->mapping
->host
;
70 page
->mapping
->a_ops
->commit_write(NULL
, page
, from
, to
);
72 err
= write_one_page(page
, 1);
78 static void ext2_check_page(struct page
*page
)
80 struct inode
*dir
= page
->mapping
->host
;
81 struct super_block
*sb
= dir
->i_sb
;
82 unsigned chunk_size
= ext2_chunk_size(dir
);
83 char *kaddr
= page_address(page
);
84 u32 max_inumber
= le32_to_cpu(EXT2_SB(sb
)->s_es
->s_inodes_count
);
85 unsigned offs
, rec_len
;
86 unsigned limit
= PAGE_CACHE_SIZE
;
90 if ((dir
->i_size
>> PAGE_CACHE_SHIFT
) == page
->index
) {
91 limit
= dir
->i_size
& ~PAGE_CACHE_MASK
;
92 if (limit
& (chunk_size
- 1))
97 for (offs
= 0; offs
<= limit
- EXT2_DIR_REC_LEN(1); offs
+= rec_len
) {
98 p
= (ext2_dirent
*)(kaddr
+ offs
);
99 rec_len
= le16_to_cpu(p
->rec_len
);
101 if (rec_len
< EXT2_DIR_REC_LEN(1))
105 if (rec_len
< EXT2_DIR_REC_LEN(p
->name_len
))
107 if (((offs
+ rec_len
- 1) ^ offs
) & ~(chunk_size
-1))
109 if (le32_to_cpu(p
->inode
) > max_inumber
)
115 SetPageChecked(page
);
118 /* Too bad, we had an error */
121 ext2_error(sb
, "ext2_check_page",
122 "size of directory #%lu is not a multiple of chunk size",
127 error
= "rec_len is smaller than minimal";
130 error
= "unaligned directory entry";
133 error
= "rec_len is too small for name_len";
136 error
= "directory entry across blocks";
139 error
= "inode out of bounds";
141 ext2_error (sb
, "ext2_check_page", "bad entry in directory #%lu: %s - "
142 "offset=%lu, inode=%lu, rec_len=%d, name_len=%d",
143 dir
->i_ino
, error
, (page
->index
<<PAGE_CACHE_SHIFT
)+offs
,
144 (unsigned long) le32_to_cpu(p
->inode
),
145 rec_len
, p
->name_len
);
148 p
= (ext2_dirent
*)(kaddr
+ offs
);
149 ext2_error (sb
, "ext2_check_page",
150 "entry in directory #%lu spans the page boundary"
151 "offset=%lu, inode=%lu",
152 dir
->i_ino
, (page
->index
<<PAGE_CACHE_SHIFT
)+offs
,
153 (unsigned long) le32_to_cpu(p
->inode
));
155 SetPageChecked(page
);
159 static struct page
* ext2_get_page(struct inode
*dir
, unsigned long n
)
161 struct address_space
*mapping
= dir
->i_mapping
;
162 struct page
*page
= read_cache_page(mapping
, n
,
163 (filler_t
*)mapping
->a_ops
->readpage
, NULL
);
165 wait_on_page_locked(page
);
167 if (!PageUptodate(page
))
169 if (!PageChecked(page
))
170 ext2_check_page(page
);
178 return ERR_PTR(-EIO
);
182 * NOTE! unlike strncmp, ext2_match returns 1 for success, 0 for failure.
184 * len <= EXT2_NAME_LEN and de != NULL are guaranteed by caller.
186 static inline int ext2_match (int len
, const char * const name
,
187 struct ext2_dir_entry_2
* de
)
189 if (len
!= de
->name_len
)
193 return !memcmp(name
, de
->name
, len
);
197 * p is at least 6 bytes before the end of page
199 static inline ext2_dirent
*ext2_next_entry(ext2_dirent
*p
)
201 return (ext2_dirent
*)((char*)p
+ le16_to_cpu(p
->rec_len
));
204 static inline unsigned
205 ext2_validate_entry(char *base
, unsigned offset
, unsigned mask
)
207 ext2_dirent
*de
= (ext2_dirent
*)(base
+ offset
);
208 ext2_dirent
*p
= (ext2_dirent
*)(base
+ (offset
&mask
));
209 while ((char*)p
< (char*)de
) {
212 p
= ext2_next_entry(p
);
214 return (char *)p
- base
;
217 static unsigned char ext2_filetype_table
[EXT2_FT_MAX
] = {
218 [EXT2_FT_UNKNOWN
] = DT_UNKNOWN
,
219 [EXT2_FT_REG_FILE
] = DT_REG
,
220 [EXT2_FT_DIR
] = DT_DIR
,
221 [EXT2_FT_CHRDEV
] = DT_CHR
,
222 [EXT2_FT_BLKDEV
] = DT_BLK
,
223 [EXT2_FT_FIFO
] = DT_FIFO
,
224 [EXT2_FT_SOCK
] = DT_SOCK
,
225 [EXT2_FT_SYMLINK
] = DT_LNK
,
229 static unsigned char ext2_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
230 [S_IFREG
>> S_SHIFT
] = EXT2_FT_REG_FILE
,
231 [S_IFDIR
>> S_SHIFT
] = EXT2_FT_DIR
,
232 [S_IFCHR
>> S_SHIFT
] = EXT2_FT_CHRDEV
,
233 [S_IFBLK
>> S_SHIFT
] = EXT2_FT_BLKDEV
,
234 [S_IFIFO
>> S_SHIFT
] = EXT2_FT_FIFO
,
235 [S_IFSOCK
>> S_SHIFT
] = EXT2_FT_SOCK
,
236 [S_IFLNK
>> S_SHIFT
] = EXT2_FT_SYMLINK
,
239 static inline void ext2_set_de_type(ext2_dirent
*de
, struct inode
*inode
)
241 mode_t mode
= inode
->i_mode
;
242 if (EXT2_HAS_INCOMPAT_FEATURE(inode
->i_sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
))
243 de
->file_type
= ext2_type_by_mode
[(mode
& S_IFMT
)>>S_SHIFT
];
249 ext2_readdir (struct file
* filp
, void * dirent
, filldir_t filldir
)
251 loff_t pos
= filp
->f_pos
;
252 struct inode
*inode
= filp
->f_dentry
->d_inode
;
253 struct super_block
*sb
= inode
->i_sb
;
254 unsigned int offset
= pos
& ~PAGE_CACHE_MASK
;
255 unsigned long n
= pos
>> PAGE_CACHE_SHIFT
;
256 unsigned long npages
= dir_pages(inode
);
257 unsigned chunk_mask
= ~(ext2_chunk_size(inode
)-1);
258 unsigned char *types
= NULL
;
259 int need_revalidate
= (filp
->f_version
!= inode
->i_version
);
262 if (pos
> inode
->i_size
- EXT2_DIR_REC_LEN(1))
265 if (EXT2_HAS_INCOMPAT_FEATURE(sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
))
266 types
= ext2_filetype_table
;
268 for ( ; n
< npages
; n
++, offset
= 0) {
271 struct page
*page
= ext2_get_page(inode
, n
);
274 ext2_error(sb
, __FUNCTION__
,
277 filp
->f_pos
+= PAGE_CACHE_SIZE
- offset
;
280 kaddr
= page_address(page
);
281 if (need_revalidate
) {
282 offset
= ext2_validate_entry(kaddr
, offset
, chunk_mask
);
285 de
= (ext2_dirent
*)(kaddr
+offset
);
286 limit
= kaddr
+ ext2_last_byte(inode
, n
) - EXT2_DIR_REC_LEN(1);
287 for ( ;(char*)de
<= limit
; de
= ext2_next_entry(de
)) {
288 if (de
->rec_len
== 0) {
289 ext2_error(sb
, __FUNCTION__
,
290 "zero-length directory entry");
297 unsigned char d_type
= DT_UNKNOWN
;
299 if (types
&& de
->file_type
< EXT2_FT_MAX
)
300 d_type
= types
[de
->file_type
];
302 offset
= (char *)de
- kaddr
;
303 over
= filldir(dirent
, de
->name
, de
->name_len
,
304 (n
<<PAGE_CACHE_SHIFT
) | offset
,
305 le32_to_cpu(de
->inode
), d_type
);
311 filp
->f_pos
+= le16_to_cpu(de
->rec_len
);
319 filp
->f_version
= inode
->i_version
;
326 * finds an entry in the specified directory with the wanted name. It
327 * returns the page in which the entry was found, and the entry itself
328 * (as a parameter - res_dir). Page is returned mapped and unlocked.
329 * Entry is guaranteed to be valid.
331 struct ext2_dir_entry_2
* ext2_find_entry (struct inode
* dir
,
332 struct dentry
*dentry
, struct page
** res_page
)
334 const char *name
= dentry
->d_name
.name
;
335 int namelen
= dentry
->d_name
.len
;
336 unsigned reclen
= EXT2_DIR_REC_LEN(namelen
);
337 unsigned long start
, n
;
338 unsigned long npages
= dir_pages(dir
);
339 struct page
*page
= NULL
;
340 struct ext2_inode_info
*ei
= EXT2_I(dir
);
349 start
= ei
->i_dir_start_lookup
;
355 page
= ext2_get_page(dir
, n
);
357 kaddr
= page_address(page
);
358 de
= (ext2_dirent
*) kaddr
;
359 kaddr
+= ext2_last_byte(dir
, n
) - reclen
;
360 while ((char *) de
<= kaddr
) {
361 if (de
->rec_len
== 0) {
362 ext2_error(dir
->i_sb
, __FUNCTION__
,
363 "zero-length directory entry");
367 if (ext2_match (namelen
, name
, de
))
369 de
= ext2_next_entry(de
);
375 } while (n
!= start
);
381 ei
->i_dir_start_lookup
= n
;
385 struct ext2_dir_entry_2
* ext2_dotdot (struct inode
*dir
, struct page
**p
)
387 struct page
*page
= ext2_get_page(dir
, 0);
388 ext2_dirent
*de
= NULL
;
391 de
= ext2_next_entry((ext2_dirent
*) page_address(page
));
397 ino_t
ext2_inode_by_name(struct inode
* dir
, struct dentry
*dentry
)
400 struct ext2_dir_entry_2
* de
;
403 de
= ext2_find_entry (dir
, dentry
, &page
);
405 res
= le32_to_cpu(de
->inode
);
407 page_cache_release(page
);
412 /* Releases the page */
413 void ext2_set_link(struct inode
*dir
, struct ext2_dir_entry_2
*de
,
414 struct page
*page
, struct inode
*inode
)
416 unsigned from
= (char *) de
- (char *) page_address(page
);
417 unsigned to
= from
+ le16_to_cpu(de
->rec_len
);
421 err
= page
->mapping
->a_ops
->prepare_write(NULL
, page
, from
, to
);
424 de
->inode
= cpu_to_le32(inode
->i_ino
);
425 ext2_set_de_type (de
, inode
);
426 err
= ext2_commit_chunk(page
, from
, to
);
428 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
429 EXT2_I(dir
)->i_flags
&= ~EXT2_BTREE_FL
;
430 mark_inode_dirty(dir
);
436 int ext2_add_link (struct dentry
*dentry
, struct inode
*inode
)
438 struct inode
*dir
= dentry
->d_parent
->d_inode
;
439 const char *name
= dentry
->d_name
.name
;
440 int namelen
= dentry
->d_name
.len
;
441 unsigned chunk_size
= ext2_chunk_size(dir
);
442 unsigned reclen
= EXT2_DIR_REC_LEN(namelen
);
443 unsigned short rec_len
, name_len
;
444 struct page
*page
= NULL
;
446 unsigned long npages
= dir_pages(dir
);
453 * We take care of directory expansion in the same loop.
454 * This code plays outside i_size, so it locks the page
455 * to protect that region.
457 for (n
= 0; n
<= npages
; n
++) {
460 page
= ext2_get_page(dir
, n
);
465 kaddr
= page_address(page
);
466 dir_end
= kaddr
+ ext2_last_byte(dir
, n
);
467 de
= (ext2_dirent
*)kaddr
;
468 kaddr
+= PAGE_CACHE_SIZE
- reclen
;
469 while ((char *)de
<= kaddr
) {
470 if ((char *)de
== dir_end
) {
473 rec_len
= chunk_size
;
474 de
->rec_len
= cpu_to_le16(chunk_size
);
478 if (de
->rec_len
== 0) {
479 ext2_error(dir
->i_sb
, __FUNCTION__
,
480 "zero-length directory entry");
485 if (ext2_match (namelen
, name
, de
))
487 name_len
= EXT2_DIR_REC_LEN(de
->name_len
);
488 rec_len
= le16_to_cpu(de
->rec_len
);
489 if (!de
->inode
&& rec_len
>= reclen
)
491 if (rec_len
>= name_len
+ reclen
)
493 de
= (ext2_dirent
*) ((char *) de
+ rec_len
);
502 from
= (char*)de
- (char*)page_address(page
);
504 err
= page
->mapping
->a_ops
->prepare_write(NULL
, page
, from
, to
);
508 ext2_dirent
*de1
= (ext2_dirent
*) ((char *) de
+ name_len
);
509 de1
->rec_len
= cpu_to_le16(rec_len
- name_len
);
510 de
->rec_len
= cpu_to_le16(name_len
);
513 de
->name_len
= namelen
;
514 memcpy (de
->name
, name
, namelen
);
515 de
->inode
= cpu_to_le32(inode
->i_ino
);
516 ext2_set_de_type (de
, inode
);
517 err
= ext2_commit_chunk(page
, from
, to
);
518 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
519 EXT2_I(dir
)->i_flags
&= ~EXT2_BTREE_FL
;
520 mark_inode_dirty(dir
);
532 * ext2_delete_entry deletes a directory entry by merging it with the
533 * previous entry. Page is up-to-date. Releases the page.
535 int ext2_delete_entry (struct ext2_dir_entry_2
* dir
, struct page
* page
)
537 struct address_space
*mapping
= page
->mapping
;
538 struct inode
*inode
= mapping
->host
;
539 char *kaddr
= page_address(page
);
540 unsigned from
= ((char*)dir
- kaddr
) & ~(ext2_chunk_size(inode
)-1);
541 unsigned to
= ((char*)dir
- kaddr
) + le16_to_cpu(dir
->rec_len
);
542 ext2_dirent
* pde
= NULL
;
543 ext2_dirent
* de
= (ext2_dirent
*) (kaddr
+ from
);
546 while ((char*)de
< (char*)dir
) {
547 if (de
->rec_len
== 0) {
548 ext2_error(inode
->i_sb
, __FUNCTION__
,
549 "zero-length directory entry");
554 de
= ext2_next_entry(de
);
557 from
= (char*)pde
- (char*)page_address(page
);
559 err
= mapping
->a_ops
->prepare_write(NULL
, page
, from
, to
);
563 pde
->rec_len
= cpu_to_le16(to
-from
);
565 err
= ext2_commit_chunk(page
, from
, to
);
566 inode
->i_ctime
= inode
->i_mtime
= CURRENT_TIME
;
567 EXT2_I(inode
)->i_flags
&= ~EXT2_BTREE_FL
;
568 mark_inode_dirty(inode
);
575 * Set the first fragment of directory.
577 int ext2_make_empty(struct inode
*inode
, struct inode
*parent
)
579 struct address_space
*mapping
= inode
->i_mapping
;
580 struct page
*page
= grab_cache_page(mapping
, 0);
581 unsigned chunk_size
= ext2_chunk_size(inode
);
582 struct ext2_dir_entry_2
* de
;
588 err
= mapping
->a_ops
->prepare_write(NULL
, page
, 0, chunk_size
);
593 kaddr
= kmap_atomic(page
, KM_USER0
);
594 de
= (struct ext2_dir_entry_2
*)kaddr
;
596 de
->rec_len
= cpu_to_le16(EXT2_DIR_REC_LEN(1));
597 memcpy (de
->name
, ".\0\0", 4);
598 de
->inode
= cpu_to_le32(inode
->i_ino
);
599 ext2_set_de_type (de
, inode
);
601 de
= (struct ext2_dir_entry_2
*)(kaddr
+ EXT2_DIR_REC_LEN(1));
603 de
->rec_len
= cpu_to_le16(chunk_size
- EXT2_DIR_REC_LEN(1));
604 de
->inode
= cpu_to_le32(parent
->i_ino
);
605 memcpy (de
->name
, "..\0", 4);
606 ext2_set_de_type (de
, inode
);
607 kunmap_atomic(kaddr
, KM_USER0
);
608 err
= ext2_commit_chunk(page
, 0, chunk_size
);
610 page_cache_release(page
);
615 * routine to check that the specified directory is empty (for rmdir)
617 int ext2_empty_dir (struct inode
* inode
)
619 struct page
*page
= NULL
;
620 unsigned long i
, npages
= dir_pages(inode
);
622 for (i
= 0; i
< npages
; i
++) {
625 page
= ext2_get_page(inode
, i
);
630 kaddr
= page_address(page
);
631 de
= (ext2_dirent
*)kaddr
;
632 kaddr
+= ext2_last_byte(inode
, i
) - EXT2_DIR_REC_LEN(1);
634 while ((char *)de
<= kaddr
) {
635 if (de
->rec_len
== 0) {
636 ext2_error(inode
->i_sb
, __FUNCTION__
,
637 "zero-length directory entry");
638 printk("kaddr=%p, de=%p\n", kaddr
, de
);
641 if (de
->inode
!= 0) {
642 /* check for . and .. */
643 if (de
->name
[0] != '.')
645 if (de
->name_len
> 2)
647 if (de
->name_len
< 2) {
649 cpu_to_le32(inode
->i_ino
))
651 } else if (de
->name
[1] != '.')
654 de
= ext2_next_entry(de
);
665 struct file_operations ext2_dir_operations
= {
666 .llseek
= generic_file_llseek
,
667 .read
= generic_read_dir
,
668 .readdir
= ext2_readdir
,
670 .fsync
= ext2_sync_file
,