2 * linux/fs/ext2/namei.c
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/namei.c
13 * Copyright (C) 1991, 1992 Linus Torvalds
15 * Big-endian to little-endian byte-swapping/bitmaps by
16 * David S. Miller (davem@caip.rutgers.edu), 1995
17 * Directory entry file type support and forward compatibility hooks
18 * for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998
22 #include <linux/locks.h>
23 #include <linux/quotaops.h>
28 * define how far ahead to read directories while searching them.
30 #define NAMEI_RA_CHUNKS 2
31 #define NAMEI_RA_BLOCKS 4
32 #define NAMEI_RA_SIZE (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
33 #define NAMEI_RA_INDEX(c,b) (((c) * NAMEI_RA_BLOCKS) + (b))
36 * NOTE! unlike strncmp, ext2_match returns 1 for success, 0 for failure.
38 * `len <= EXT2_NAME_LEN' is guaranteed by caller.
39 * `de != NULL' is guaranteed by caller.
41 static inline int ext2_match (int len
, const char * const name
,
42 struct ext2_dir_entry_2
* de
)
44 if (len
!= de
->name_len
)
48 return !memcmp(name
, de
->name
, len
);
54 * finds an entry in the specified directory with the wanted name. It
55 * returns the cache buffer in which the entry was found, and the entry
56 * itself (as a parameter - res_dir). It does NOT read the inode of the
57 * entry - you'll have to do that yourself if you want to.
59 static struct buffer_head
* ext2_find_entry (struct inode
* dir
,
60 const char * const name
, int namelen
,
61 struct ext2_dir_entry_2
** res_dir
)
63 struct super_block
* sb
;
64 struct buffer_head
* bh_use
[NAMEI_RA_SIZE
];
65 struct buffer_head
* bh_read
[NAMEI_RA_SIZE
];
67 int block
, toread
, i
, err
;
72 if (namelen
> EXT2_NAME_LEN
)
75 memset (bh_use
, 0, sizeof (bh_use
));
77 for (block
= 0; block
< NAMEI_RA_SIZE
; ++block
) {
78 struct buffer_head
* bh
;
80 if ((block
<< EXT2_BLOCK_SIZE_BITS (sb
)) >= dir
->i_size
)
82 bh
= ext2_getblk (dir
, block
, 0, &err
);
84 if (bh
&& !buffer_uptodate(bh
))
85 bh_read
[toread
++] = bh
;
88 for (block
= 0, offset
= 0; offset
< dir
->i_size
; block
++) {
89 struct buffer_head
* bh
;
90 struct ext2_dir_entry_2
* de
;
93 if ((block
% NAMEI_RA_BLOCKS
) == 0 && toread
) {
94 ll_rw_block (READ
, toread
, bh_read
);
97 bh
= bh_use
[block
% NAMEI_RA_SIZE
];
100 ext2_error (sb
, "ext2_find_entry",
101 "directory #%lu contains a hole at offset %lu",
104 offset
+= sb
->s_blocksize
;
108 if (!buffer_uptodate(bh
)) {
110 * read error: all bets are off
115 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
116 dlimit
= bh
->b_data
+ sb
->s_blocksize
;
117 while ((char *) de
< dlimit
) {
118 /* this code is executed quadratically often */
119 /* do minimal checking `by hand' */
122 if ((char *) de
+ namelen
<= dlimit
&&
123 ext2_match (namelen
, name
, de
)) {
125 just to be sure, do a full check */
126 if (!ext2_check_dir_entry("ext2_find_entry",
127 dir
, de
, bh
, offset
))
129 for (i
= 0; i
< NAMEI_RA_SIZE
; ++i
) {
136 /* prevent looping on a bad block */
137 de_len
= le16_to_cpu(de
->rec_len
);
141 de
= (struct ext2_dir_entry_2
*)
142 ((char *) de
+ de_len
);
146 if (((block
+ NAMEI_RA_SIZE
) << EXT2_BLOCK_SIZE_BITS (sb
)) >=
150 bh
= ext2_getblk (dir
, block
+ NAMEI_RA_SIZE
, 0, &err
);
151 bh_use
[block
% NAMEI_RA_SIZE
] = bh
;
152 if (bh
&& !buffer_uptodate(bh
))
153 bh_read
[toread
++] = bh
;
157 for (i
= 0; i
< NAMEI_RA_SIZE
; ++i
)
162 static struct dentry
*ext2_lookup(struct inode
* dir
, struct dentry
*dentry
)
164 struct inode
* inode
;
165 struct ext2_dir_entry_2
* de
;
166 struct buffer_head
* bh
;
168 if (dentry
->d_name
.len
> EXT2_NAME_LEN
)
169 return ERR_PTR(-ENAMETOOLONG
);
171 bh
= ext2_find_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
, &de
);
174 unsigned long ino
= le32_to_cpu(de
->inode
);
176 inode
= iget(dir
->i_sb
, ino
);
179 return ERR_PTR(-EACCES
);
181 d_add(dentry
, inode
);
185 static inline void ext2_set_de_type(struct super_block
*sb
,
186 struct ext2_dir_entry_2
*de
,
188 if (!EXT2_HAS_INCOMPAT_FEATURE(sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
))
191 de
->file_type
= EXT2_FT_REG_FILE
;
192 else if (S_ISDIR(mode
))
193 de
->file_type
= EXT2_FT_DIR
;
194 else if (S_ISLNK(mode
))
195 de
->file_type
= EXT2_FT_SYMLINK
;
196 else if (S_ISSOCK(mode
))
197 de
->file_type
= EXT2_FT_SOCK
;
198 else if (S_ISFIFO(mode
))
199 de
->file_type
= EXT2_FT_FIFO
;
200 else if (S_ISCHR(mode
))
201 de
->file_type
= EXT2_FT_CHRDEV
;
202 else if (S_ISBLK(mode
))
203 de
->file_type
= EXT2_FT_BLKDEV
;
209 * adds a file entry to the specified directory.
211 int ext2_add_entry (struct inode
* dir
, const char * name
, int namelen
,
214 unsigned long offset
;
215 unsigned short rec_len
;
216 struct buffer_head
* bh
;
217 struct ext2_dir_entry_2
* de
, * de1
;
218 struct super_block
* sb
;
225 bh
= ext2_bread (dir
, 0, 0, &retval
);
228 rec_len
= EXT2_DIR_REC_LEN(namelen
);
230 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
232 if ((char *)de
>= sb
->s_blocksize
+ bh
->b_data
) {
235 bh
= ext2_bread (dir
, offset
>> EXT2_BLOCK_SIZE_BITS(sb
), 1, &retval
);
238 if (dir
->i_size
<= offset
) {
239 if (dir
->i_size
== 0) {
243 ext2_debug ("creating next block\n");
245 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
247 de
->rec_len
= le16_to_cpu(sb
->s_blocksize
);
248 dir
->i_size
= offset
+ sb
->s_blocksize
;
249 dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
250 mark_inode_dirty(dir
);
253 ext2_debug ("skipping to next block\n");
255 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
258 if (!ext2_check_dir_entry ("ext2_add_entry", dir
, de
, bh
,
263 if (ext2_match (namelen
, name
, de
)) {
267 if ((le32_to_cpu(de
->inode
) == 0 && le16_to_cpu(de
->rec_len
) >= rec_len
) ||
268 (le16_to_cpu(de
->rec_len
) >= EXT2_DIR_REC_LEN(de
->name_len
) + rec_len
)) {
269 offset
+= le16_to_cpu(de
->rec_len
);
270 if (le32_to_cpu(de
->inode
)) {
271 de1
= (struct ext2_dir_entry_2
*) ((char *) de
+
272 EXT2_DIR_REC_LEN(de
->name_len
));
273 de1
->rec_len
= cpu_to_le16(le16_to_cpu(de
->rec_len
) -
274 EXT2_DIR_REC_LEN(de
->name_len
));
275 de
->rec_len
= cpu_to_le16(EXT2_DIR_REC_LEN(de
->name_len
));
278 de
->file_type
= EXT2_FT_UNKNOWN
;
280 de
->inode
= cpu_to_le32(inode
->i_ino
);
281 ext2_set_de_type(dir
->i_sb
, de
, inode
->i_mode
);
284 de
->name_len
= namelen
;
285 memcpy (de
->name
, name
, namelen
);
287 * XXX shouldn't update any times until successful
288 * completion of syscall, but too many callers depend
291 * XXX similarly, too many callers depend on
292 * ext2_new_inode() setting the times, but error
293 * recovery deletes the inode, so the worst that can
294 * happen is that the times are slightly out of date
295 * and/or different from the directory change time.
297 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
298 dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
299 mark_inode_dirty(dir
);
300 dir
->i_version
= ++event
;
301 mark_buffer_dirty(bh
, 1);
303 ll_rw_block (WRITE
, 1, &bh
);
309 offset
+= le16_to_cpu(de
->rec_len
);
310 de
= (struct ext2_dir_entry_2
*) ((char *) de
+ le16_to_cpu(de
->rec_len
));
317 * ext2_delete_entry deletes a directory entry by merging it with the
320 static int ext2_delete_entry (struct inode
* dir
,
321 struct ext2_dir_entry_2
* de_del
,
322 struct buffer_head
* bh
)
324 struct ext2_dir_entry_2
* de
, * pde
;
329 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
330 while (i
< bh
->b_size
) {
331 if (!ext2_check_dir_entry ("ext2_delete_entry", NULL
,
337 cpu_to_le16(le16_to_cpu(pde
->rec_len
) +
338 le16_to_cpu(de
->rec_len
));
341 dir
->i_version
= ++event
;
342 mark_buffer_dirty(bh
, 1);
344 ll_rw_block (WRITE
, 1, &bh
);
349 i
+= le16_to_cpu(de
->rec_len
);
351 de
= (struct ext2_dir_entry_2
*) ((char *) de
+ le16_to_cpu(de
->rec_len
));
357 * By the time this is called, we already have created
358 * the directory cache entry for the new file, but it
359 * is so far negative - it has no inode.
361 * If the create succeeds, we fill in the inode information
362 * with d_instantiate().
364 static int ext2_create (struct inode
* dir
, struct dentry
* dentry
, int mode
)
366 struct inode
* inode
;
369 inode
= ext2_new_inode (dir
, mode
, &err
);
373 inode
->i_op
= &ext2_file_inode_operations
;
374 inode
->i_fop
= &ext2_file_operations
;
375 inode
->i_mapping
->a_ops
= &ext2_aops
;
376 inode
->i_mode
= mode
;
377 mark_inode_dirty(inode
);
378 err
= ext2_add_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
,
382 mark_inode_dirty(inode
);
386 d_instantiate(dentry
, inode
);
390 static int ext2_mknod (struct inode
* dir
, struct dentry
*dentry
, int mode
, int rdev
)
392 struct inode
* inode
;
395 inode
= ext2_new_inode (dir
, mode
, &err
);
399 inode
->i_uid
= current
->fsuid
;
400 init_special_inode(inode
, mode
, rdev
);
401 err
= ext2_add_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
,
405 mark_inode_dirty(inode
);
406 d_instantiate(dentry
, inode
);
411 mark_inode_dirty(inode
);
416 static int ext2_mkdir(struct inode
* dir
, struct dentry
* dentry
, int mode
)
418 struct inode
* inode
;
419 struct buffer_head
* dir_block
;
420 struct ext2_dir_entry_2
* de
;
423 if (dir
->i_nlink
>= EXT2_LINK_MAX
)
426 inode
= ext2_new_inode (dir
, S_IFDIR
, &err
);
430 inode
->i_op
= &ext2_dir_inode_operations
;
431 inode
->i_fop
= &ext2_dir_operations
;
432 inode
->i_size
= inode
->i_sb
->s_blocksize
;
434 dir_block
= ext2_bread (inode
, 0, 1, &err
);
436 inode
->i_nlink
--; /* is this nlink == 0? */
437 mark_inode_dirty(inode
);
441 de
= (struct ext2_dir_entry_2
*) dir_block
->b_data
;
442 de
->inode
= cpu_to_le32(inode
->i_ino
);
444 de
->rec_len
= cpu_to_le16(EXT2_DIR_REC_LEN(de
->name_len
));
445 strcpy (de
->name
, ".");
446 ext2_set_de_type(dir
->i_sb
, de
, S_IFDIR
);
447 de
= (struct ext2_dir_entry_2
*) ((char *) de
+ le16_to_cpu(de
->rec_len
));
448 de
->inode
= cpu_to_le32(dir
->i_ino
);
449 de
->rec_len
= cpu_to_le16(inode
->i_sb
->s_blocksize
- EXT2_DIR_REC_LEN(1));
451 strcpy (de
->name
, "..");
452 ext2_set_de_type(dir
->i_sb
, de
, S_IFDIR
);
454 mark_buffer_dirty(dir_block
, 1);
456 inode
->i_mode
= S_IFDIR
| mode
;
457 if (dir
->i_mode
& S_ISGID
)
458 inode
->i_mode
|= S_ISGID
;
459 mark_inode_dirty(inode
);
460 err
= ext2_add_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
,
465 dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
466 mark_inode_dirty(dir
);
467 d_instantiate(dentry
, inode
);
472 mark_inode_dirty(inode
);
478 * routine to check that the specified directory is empty (for rmdir)
480 static int empty_dir (struct inode
* inode
)
482 unsigned long offset
;
483 struct buffer_head
* bh
;
484 struct ext2_dir_entry_2
* de
, * de1
;
485 struct super_block
* sb
;
489 if (inode
->i_size
< EXT2_DIR_REC_LEN(1) + EXT2_DIR_REC_LEN(2) ||
490 !(bh
= ext2_bread (inode
, 0, 0, &err
))) {
491 ext2_warning (inode
->i_sb
, "empty_dir",
492 "bad directory (dir #%lu) - no data block",
496 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
497 de1
= (struct ext2_dir_entry_2
*) ((char *) de
+ le16_to_cpu(de
->rec_len
));
498 if (le32_to_cpu(de
->inode
) != inode
->i_ino
|| !le32_to_cpu(de1
->inode
) ||
499 strcmp (".", de
->name
) || strcmp ("..", de1
->name
)) {
500 ext2_warning (inode
->i_sb
, "empty_dir",
501 "bad directory (dir #%lu) - no `.' or `..'",
506 offset
= le16_to_cpu(de
->rec_len
) + le16_to_cpu(de1
->rec_len
);
507 de
= (struct ext2_dir_entry_2
*) ((char *) de1
+ le16_to_cpu(de1
->rec_len
));
508 while (offset
< inode
->i_size
) {
509 if (!bh
|| (void *) de
>= (void *) (bh
->b_data
+ sb
->s_blocksize
)) {
511 bh
= ext2_bread (inode
, offset
>> EXT2_BLOCK_SIZE_BITS(sb
), 0, &err
);
514 ext2_error (sb
, "empty_dir",
515 "directory #%lu contains a hole at offset %lu",
516 inode
->i_ino
, offset
);
518 offset
+= sb
->s_blocksize
;
521 de
= (struct ext2_dir_entry_2
*) bh
->b_data
;
523 if (!ext2_check_dir_entry ("empty_dir", inode
, de
, bh
,
528 if (le32_to_cpu(de
->inode
)) {
532 offset
+= le16_to_cpu(de
->rec_len
);
533 de
= (struct ext2_dir_entry_2
*) ((char *) de
+ le16_to_cpu(de
->rec_len
));
539 static int ext2_rmdir (struct inode
* dir
, struct dentry
*dentry
)
542 struct inode
* inode
;
543 struct buffer_head
* bh
;
544 struct ext2_dir_entry_2
* de
;
547 bh
= ext2_find_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
, &de
);
551 inode
= dentry
->d_inode
;
555 if (le32_to_cpu(de
->inode
) != inode
->i_ino
)
559 if (!empty_dir (inode
))
562 retval
= ext2_delete_entry(dir
, de
, bh
);
565 if (inode
->i_nlink
!= 2)
566 ext2_warning (inode
->i_sb
, "ext2_rmdir",
567 "empty directory has nlink!=2 (%d)",
569 inode
->i_version
= ++event
;
572 mark_inode_dirty(inode
);
574 inode
->i_ctime
= dir
->i_ctime
= dir
->i_mtime
= CURRENT_TIME
;
575 dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
576 mark_inode_dirty(dir
);
583 static int ext2_unlink(struct inode
* dir
, struct dentry
*dentry
)
586 struct inode
* inode
;
587 struct buffer_head
* bh
;
588 struct ext2_dir_entry_2
* de
;
591 bh
= ext2_find_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
, &de
);
595 inode
= dentry
->d_inode
;
599 if (le32_to_cpu(de
->inode
) != inode
->i_ino
)
602 if (!inode
->i_nlink
) {
603 ext2_warning (inode
->i_sb
, "ext2_unlink",
604 "Deleting nonexistent file (%lu), %d",
605 inode
->i_ino
, inode
->i_nlink
);
608 retval
= ext2_delete_entry(dir
, de
, bh
);
611 dir
->i_ctime
= dir
->i_mtime
= CURRENT_TIME
;
612 dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
613 mark_inode_dirty(dir
);
615 mark_inode_dirty(inode
);
616 inode
->i_ctime
= dir
->i_ctime
;
624 static int ext2_symlink (struct inode
* dir
, struct dentry
*dentry
, const char * symname
)
626 struct inode
* inode
;
629 l
= strlen(symname
)+1;
630 if (l
> dir
->i_sb
->s_blocksize
)
631 return -ENAMETOOLONG
;
633 if (!(inode
= ext2_new_inode (dir
, S_IFLNK
, &err
)))
636 inode
->i_mode
= S_IFLNK
| S_IRWXUGO
;
638 if (l
> sizeof (inode
->u
.ext2_i
.i_data
)) {
639 inode
->i_op
= &page_symlink_inode_operations
;
640 inode
->i_mapping
->a_ops
= &ext2_aops
;
641 err
= block_symlink(inode
, symname
, l
);
645 inode
->i_op
= &ext2_fast_symlink_inode_operations
;
646 memcpy((char*)&inode
->u
.ext2_i
.i_data
,symname
,l
);
649 mark_inode_dirty(inode
);
651 err
= ext2_add_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
,
655 d_instantiate(dentry
, inode
);
660 mark_inode_dirty(inode
);
665 static int ext2_link (struct dentry
* old_dentry
,
666 struct inode
* dir
, struct dentry
*dentry
)
668 struct inode
*inode
= old_dentry
->d_inode
;
671 if (S_ISDIR(inode
->i_mode
))
674 if (inode
->i_nlink
>= EXT2_LINK_MAX
)
677 err
= ext2_add_entry (dir
, dentry
->d_name
.name
, dentry
->d_name
.len
,
683 inode
->i_ctime
= CURRENT_TIME
;
684 mark_inode_dirty(inode
);
685 atomic_inc(&inode
->i_count
);
686 d_instantiate(dentry
, inode
);
690 #define PARENT_INO(buffer) \
691 ((struct ext2_dir_entry_2 *) ((char *) buffer + \
692 le16_to_cpu(((struct ext2_dir_entry_2 *) buffer)->rec_len)))->inode
695 * Anybody can rename anything with this: the permission checks are left to the
696 * higher-level routines.
698 static int ext2_rename (struct inode
* old_dir
, struct dentry
*old_dentry
,
699 struct inode
* new_dir
,struct dentry
*new_dentry
)
701 struct inode
* old_inode
, * new_inode
;
702 struct buffer_head
* old_bh
, * new_bh
, * dir_bh
;
703 struct ext2_dir_entry_2
* old_de
, * new_de
;
706 old_bh
= new_bh
= dir_bh
= NULL
;
708 old_bh
= ext2_find_entry (old_dir
, old_dentry
->d_name
.name
, old_dentry
->d_name
.len
, &old_de
);
710 * Check for inode number is _not_ due to possible IO errors.
711 * We might rmdir the source, keep it as pwd of some process
712 * and merrily kill the link to whatever was created under the
713 * same name. Goodbye sticky bit ;-<
715 old_inode
= old_dentry
->d_inode
;
717 if (!old_bh
|| le32_to_cpu(old_de
->inode
) != old_inode
->i_ino
)
720 new_inode
= new_dentry
->d_inode
;
721 new_bh
= ext2_find_entry (new_dir
, new_dentry
->d_name
.name
,
722 new_dentry
->d_name
.len
, &new_de
);
728 DQUOT_INIT(new_inode
);
731 if (S_ISDIR(old_inode
->i_mode
)) {
734 if (!empty_dir (new_inode
))
738 dir_bh
= ext2_bread (old_inode
, 0, 0, &retval
);
741 if (le32_to_cpu(PARENT_INO(dir_bh
->b_data
)) != old_dir
->i_ino
)
744 if (!new_inode
&& new_dir
!=old_dir
&&
745 new_dir
->i_nlink
>= EXT2_LINK_MAX
)
749 retval
= ext2_add_entry (new_dir
, new_dentry
->d_name
.name
,
750 new_dentry
->d_name
.len
,
755 new_de
->inode
= le32_to_cpu(old_inode
->i_ino
);
756 if (EXT2_HAS_INCOMPAT_FEATURE(new_dir
->i_sb
,
757 EXT2_FEATURE_INCOMPAT_FILETYPE
))
758 new_de
->file_type
= old_de
->file_type
;
759 new_dir
->i_version
= ++event
;
760 mark_buffer_dirty(new_bh
, 1);
761 if (IS_SYNC(new_dir
)) {
762 ll_rw_block (WRITE
, 1, &new_bh
);
763 wait_on_buffer (new_bh
);
770 * Like most other Unix systems, set the ctime for inodes on a
773 old_inode
->i_ctime
= CURRENT_TIME
;
774 mark_inode_dirty(old_inode
);
779 ext2_delete_entry(old_dir
, old_de
, old_bh
);
782 new_inode
->i_nlink
--;
783 new_inode
->i_ctime
= CURRENT_TIME
;
784 mark_inode_dirty(new_inode
);
786 old_dir
->i_ctime
= old_dir
->i_mtime
= CURRENT_TIME
;
787 old_dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
788 mark_inode_dirty(old_dir
);
790 PARENT_INO(dir_bh
->b_data
) = le32_to_cpu(new_dir
->i_ino
);
791 mark_buffer_dirty(dir_bh
, 1);
793 mark_inode_dirty(old_dir
);
795 new_inode
->i_nlink
--;
796 mark_inode_dirty(new_inode
);
799 new_dir
->u
.ext2_i
.i_flags
&= ~EXT2_BTREE_FL
;
800 mark_inode_dirty(new_dir
);
814 * directories can handle most operations...
816 struct inode_operations ext2_dir_inode_operations
= {
821 symlink
: ext2_symlink
,