2 * pass2.c --- check directory structure
4 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o
7 * This file may be redistributed under the terms of the GNU Public
11 * Pass 2 of e2fsck iterates through all active directory inodes, and
12 * applies to following tests to each directory entry in the directory
13 * blocks in the inodes:
15 * - The length of the directory entry (rec_len) should be at
16 * least 8 bytes, and no more than the remaining space
17 * left in the directory block.
18 * - The length of the name in the directory entry (name_len)
19 * should be less than (rec_len - 8).
20 * - The inode number in the directory entry should be within
22 * - The inode number should refer to a in-use inode.
23 * - The first entry should be '.', and its inode should be
24 * the inode of the directory.
25 * - The second entry should be '..'.
27 * To minimize disk seek time, the directory blocks are processed in
28 * sorted order of block numbers.
30 * Pass 2 also collects the following information:
31 * - The inode numbers of the subdirectories for each directory.
33 * Pass 2 relies on the following information from previous passes:
34 * - The directory information collected in pass 1.
35 * - The inode_used_map bitmap
36 * - The inode_bad_map bitmap
37 * - The inode_dir_map bitmap
39 * Pass 2 frees the following data structures
40 * - The inode_bad_map bitmap
43 #include "et/com_err.h"
49 * Keeps track of how many times an inode is referenced.
51 ext2_icount_t inode_count
= 0;
53 static void deallocate_inode(ext2_filsys fs
, ino_t ino
,
55 static int process_bad_inode(ext2_filsys fs
, ino_t dir
, ino_t ino
);
56 static int check_dir_block(ext2_filsys fs
,
57 struct ext2_db_entry
*dir_blocks_info
,
59 static int allocate_dir_block(ext2_filsys fs
,
60 struct ext2_db_entry
*dir_blocks_info
,
61 char *buf
, struct problem_context
*pctx
);
62 static int update_dir_block(ext2_filsys fs
,
67 struct check_dir_struct
{
69 struct problem_context pctx
;
72 void pass2(ext2_filsys fs
)
75 struct resource_track rtrack
;
79 struct check_dir_struct cd
;
81 init_resource_track(&rtrack
);
84 mtrace_print("Pass 2");
88 printf("Pass 2: Checking directory structure\n");
89 size
= ext2fs_get_icount_size(inode_link_info
) + 10;
90 retval
= ext2fs_create_icount(fs
, EXT2_ICOUNT_OPT_INCREMENT
,
93 com_err("ext2fs_create_icount", retval
,
94 "while creating inode_count");
97 buf
= allocate_memory(fs
->blocksize
, "directory scan buffer");
100 * Set up the parent pointer for the root directory, if
101 * present. (If the root directory is not present, we will
102 * create it in pass 3.)
104 dir
= get_dir_info(EXT2_ROOT_INO
);
106 dir
->parent
= EXT2_ROOT_INO
;
109 clear_problem_context(&cd
.pctx
);
111 retval
= ext2fs_dblist_iterate(fs
->dblist
, check_dir_block
, &cd
);
114 ext2fs_free_dblist(fs
->dblist
);
117 ext2fs_free_inode_bitmap(inode_bad_map
);
122 print_resource_track(&rtrack
);
127 * Make sure the first entry in the directory is '.', and that the
128 * directory entry is sane.
130 static int check_dot(ext2_filsys fs
,
131 struct ext2_dir_entry
*dirent
,
132 ino_t ino
, struct problem_context
*pctx
)
134 struct ext2_dir_entry
*nextdir
;
141 problem
= PR_2_MISSING_DOT
;
142 else if ((dirent
->name_len
!= 1) ||
143 (dirent
->name
[0] != '.'))
144 problem
= PR_2_1ST_NOT_DOT
;
145 else if (dirent
->name
[1] != '\0')
146 problem
= PR_2_DOT_NULL_TERM
;
149 if (fix_problem(fs
, problem
, pctx
)) {
150 if (dirent
->rec_len
< 12)
151 dirent
->rec_len
= 12;
153 dirent
->name_len
= 1;
154 dirent
->name
[0] = '.';
155 dirent
->name
[1] = '\0';
160 if (dirent
->inode
!= ino
) {
161 if (fix_problem(fs
, PR_2_BAD_INODE_DOT
, pctx
)) {
166 if (dirent
->rec_len
> 12) {
167 new_len
= dirent
->rec_len
- 12;
171 ask("Directory entry for '.' is big. Split", 1)) {
172 nextdir
= (struct ext2_dir_entry
*)
173 ((char *) dirent
+ 12);
174 dirent
->rec_len
= 12;
175 nextdir
->rec_len
= new_len
;
177 nextdir
->name_len
= 0;
186 * Make sure the second entry in the directory is '..', and that the
187 * directory entry is sane. We do not check the inode number of '..'
188 * here; this gets done in pass 3.
190 static int check_dotdot(ext2_filsys fs
,
191 struct ext2_dir_entry
*dirent
,
192 struct dir_info
*dir
, struct problem_context
*pctx
)
197 problem
= PR_2_MISSING_DOT_DOT
;
198 else if ((dirent
->name_len
!= 2) ||
199 (dirent
->name
[0] != '.') ||
200 (dirent
->name
[1] != '.'))
201 problem
= PR_2_2ND_NOT_DOT_DOT
;
202 else if (dirent
->name
[2] != '\0')
203 problem
= PR_2_DOT_DOT_NULL_TERM
;
206 if (fix_problem(fs
, problem
, pctx
)) {
207 if (dirent
->rec_len
< 12)
208 dirent
->rec_len
= 12;
210 * Note: we don't have the parent inode just
211 * yet, so we will fill it in with the root
212 * inode. This will get fixed in pass 3.
214 dirent
->inode
= EXT2_ROOT_INO
;
215 dirent
->name_len
= 2;
216 dirent
->name
[0] = '.';
217 dirent
->name
[1] = '.';
218 dirent
->name
[2] = '\0';
223 dir
->dotdot
= dirent
->inode
;
228 * Check to make sure a directory entry doesn't contain any illegal
231 static int check_name(ext2_filsys fs
,
232 struct ext2_dir_entry
*dirent
,
233 ino_t dir_ino
, struct problem_context
*pctx
)
239 for ( i
= 0; i
< dirent
->name_len
; i
++) {
240 if (dirent
->name
[i
] == '/' || dirent
->name
[i
] == '\0') {
242 fixup
= fix_problem(fs
, PR_2_BAD_NAME
, pctx
);
245 dirent
->name
[i
] = '.';
253 static int check_dir_block(ext2_filsys fs
,
254 struct ext2_db_entry
*db
,
257 struct dir_info
*subdir
, *dir
;
258 struct ext2_dir_entry
*dirent
;
260 int dir_modified
= 0;
263 blk_t block_nr
= db
->blk
;
266 struct check_dir_struct
*cd
= private;
270 * Make sure the inode is still in use (could have been
271 * deleted in the duplicate/bad blocks pass.
273 if (!(ext2fs_test_inode_bitmap(inode_used_map
, ino
)))
277 cd
->pctx
.blk
= block_nr
;
278 cd
->pctx
.blkcount
= db
->blockcnt
;
284 if (allocate_dir_block(fs
, db
, buf
, &cd
->pctx
))
295 printf("In process_dir_block block %lu, #%d, inode %lu\n", block_nr
,
299 retval
= ext2fs_read_dir_block(fs
, block_nr
, buf
);
301 com_err(program_name
, retval
,
302 "while reading directory block %d", block_nr
);
307 dirent
= (struct ext2_dir_entry
*) (buf
+ offset
);
308 cd
->pctx
.dirent
= dirent
;
309 cd
->pctx
.num
= offset
;
310 if (((offset
+ dirent
->rec_len
) > fs
->blocksize
) ||
311 (dirent
->rec_len
< 8) ||
312 ((dirent
->rec_len
% 4) != 0) ||
313 ((dirent
->name_len
+8) > dirent
->rec_len
)) {
314 if (fix_problem(fs
, PR_2_DIR_CORRUPTED
, &cd
->pctx
)) {
315 dirent
->rec_len
= fs
->blocksize
- offset
;
316 dirent
->name_len
= 0;
323 if (dirent
->name_len
> EXT2_NAME_LEN
) {
324 if (fix_problem(fs
, PR_2_FILENAME_LONG
, &cd
->pctx
)) {
325 dirent
->name_len
= EXT2_NAME_LEN
;
330 if (dot_state
== 1) {
331 if (check_dot(fs
, dirent
, ino
, &cd
->pctx
))
333 } else if (dot_state
== 2) {
334 dir
= get_dir_info(ino
);
336 printf("Internal error: couldn't find dir_info for %lu\n",
340 if (check_dotdot(fs
, dirent
, dir
, &cd
->pctx
))
342 } else if (dirent
->inode
== ino
) {
343 if (fix_problem(fs
, PR_2_LINK_DOT
, &cd
->pctx
)) {
352 if (check_name(fs
, dirent
, ino
, &cd
->pctx
))
356 * Make sure the inode listed is a legal one.
358 if (((dirent
->inode
!= EXT2_ROOT_INO
) &&
359 (dirent
->inode
< EXT2_FIRST_INODE(fs
->super
))) ||
360 (dirent
->inode
> fs
->super
->s_inodes_count
)) {
361 if (fix_problem(fs
, PR_2_BAD_INO
, &cd
->pctx
)) {
369 * If the inode is unused, offer to clear it.
371 if (!(ext2fs_test_inode_bitmap(inode_used_map
,
373 if (fix_problem(fs
, PR_2_UNUSED_INODE
, &cd
->pctx
)) {
381 * If the inode is in a bad block, offer to clear it.
384 (ext2fs_test_inode_bitmap(inode_bb_map
,
386 if (fix_problem(fs
, PR_2_BB_INODE
, &cd
->pctx
)) {
394 * If the inode was marked as having bad fields in
395 * pass1, process it and offer to fix/clear it.
396 * (We wait until now so that we can display the
397 * pathname to the user.)
400 ext2fs_test_inode_bitmap(inode_bad_map
,
402 if (process_bad_inode(fs
, ino
, dirent
->inode
)) {
410 * Don't allow links to the root directory. We check
411 * this specially to make sure we catch this error
412 * case even if the root directory hasn't been created
415 if ((dot_state
> 2) && (dirent
->inode
== EXT2_ROOT_INO
)) {
416 if (fix_problem(fs
, PR_2_LINK_ROOT
, &cd
->pctx
)) {
424 * If this is a directory, then mark its parent in its
425 * dir_info structure. If the parent field is already
426 * filled in, then this directory has more than one
427 * hard link. We assume the first link is correct,
428 * and ask the user if he/she wants to clear this one.
430 if ((dot_state
> 2) &&
431 (ext2fs_test_inode_bitmap(inode_dir_map
,
433 subdir
= get_dir_info(dirent
->inode
);
435 printf("INTERNAL ERROR: missing dir %u\n",
439 if (subdir
->parent
) {
440 cd
->pctx
.ino2
= subdir
->parent
;
441 if (fix_problem(fs
, PR_2_LINK_DIR
,
449 subdir
->parent
= ino
;
452 ext2fs_icount_increment(inode_count
, dirent
->inode
, &links
);
457 offset
+= dirent
->rec_len
;
458 } while (offset
< fs
->blocksize
);
462 if (offset
!= fs
->blocksize
) {
463 printf("Final rec_len is %d, should be %d\n",
465 dirent
->rec_len
- fs
->blocksize
+ offset
);
468 retval
= ext2fs_write_dir_block(fs
, block_nr
, buf
);
470 com_err(program_name
, retval
,
471 "while writing directory block %d", block_nr
);
473 ext2fs_mark_changed(fs
);
479 * This function is called to deallocate a block, and is an interator
480 * functioned called by deallocate inode via ext2fs_iterate_block().
482 static int deallocate_inode_block(ext2_filsys fs
,
489 ext2fs_unmark_block_bitmap(block_found_map
, *block_nr
);
490 ext2fs_unmark_block_bitmap(fs
->block_map
, *block_nr
);
495 * This fuction deallocates an inode
497 static void deallocate_inode(ext2_filsys fs
, ino_t ino
,
501 struct ext2_inode inode
;
503 ext2fs_icount_store(inode_link_info
, ino
, 0);
504 e2fsck_read_inode(fs
, ino
, &inode
, "deallocate_inode");
505 inode
.i_links_count
= 0;
506 inode
.i_dtime
= time(0);
507 e2fsck_write_inode(fs
, ino
, &inode
, "deallocate_inode");
510 * Fix up the bitmaps...
513 ext2fs_unmark_inode_bitmap(inode_used_map
, ino
);
514 ext2fs_unmark_inode_bitmap(inode_dir_map
, ino
);
516 ext2fs_unmark_inode_bitmap(inode_bad_map
, ino
);
517 ext2fs_unmark_inode_bitmap(fs
->inode_map
, ino
);
518 ext2fs_mark_ib_dirty(fs
);
520 if (!ext2fs_inode_has_valid_blocks(&inode
))
523 ext2fs_mark_bb_dirty(fs
);
524 retval
= ext2fs_block_iterate(fs
, ino
, 0, block_buf
,
525 deallocate_inode_block
, 0);
527 com_err("deallocate_inode", retval
,
528 "while calling ext2fs_block_iterate for inode %d",
532 static int process_bad_inode(ext2_filsys fs
, ino_t dir
, ino_t ino
)
534 struct ext2_inode inode
;
535 int inode_modified
= 0;
536 unsigned char *frag
, *fsize
;
537 struct problem_context pctx
;
539 e2fsck_read_inode(fs
, ino
, &inode
, "process_bad_inode");
541 clear_problem_context(&pctx
);
546 if (!LINUX_S_ISDIR(inode
.i_mode
) && !LINUX_S_ISREG(inode
.i_mode
) &&
547 !LINUX_S_ISCHR(inode
.i_mode
) && !LINUX_S_ISBLK(inode
.i_mode
) &&
548 !LINUX_S_ISLNK(inode
.i_mode
) && !LINUX_S_ISFIFO(inode
.i_mode
) &&
549 !(LINUX_S_ISSOCK(inode
.i_mode
))) {
550 if (fix_problem(fs
, PR_2_BAD_MODE
, &pctx
)) {
551 deallocate_inode(fs
, ino
, 0);
556 fix_problem(fs
, PR_2_FADDR_ZERO
, &pctx
)) {
561 switch (fs
->super
->s_creator_os
) {
563 frag
= &inode
.osd2
.linux2
.l_i_frag
;
564 fsize
= &inode
.osd2
.linux2
.l_i_fsize
;
567 frag
= &inode
.osd2
.hurd2
.h_i_frag
;
568 fsize
= &inode
.osd2
.hurd2
.h_i_fsize
;
571 frag
= &inode
.osd2
.masix2
.m_i_frag
;
572 fsize
= &inode
.osd2
.masix2
.m_i_fsize
;
579 if (fix_problem(fs
, PR_2_FRAG_ZERO
, &pctx
)) {
585 if (fsize
&& *fsize
) {
587 if (fix_problem(fs
, PR_2_FSIZE_ZERO
, &pctx
)) {
594 if (inode
.i_file_acl
&&
595 fix_problem(fs
, PR_2_FILE_ACL_ZERO
, &pctx
)) {
596 inode
.i_file_acl
= 0;
599 if (inode
.i_dir_acl
&&
600 fix_problem(fs
, PR_2_DIR_ACL_ZERO
, &pctx
)) {
605 e2fsck_write_inode(fs
, ino
, &inode
, "process_bad_inode");
611 * allocate_dir_block --- this function allocates a new directory
612 * block for a particular inode; this is done if a directory has
613 * a "hole" in it, or if a directory has a illegal block number
614 * that was zeroed out and now needs to be replaced.
616 static int allocate_dir_block(ext2_filsys fs
,
617 struct ext2_db_entry
*db
,
618 char *buf
, struct problem_context
*pctx
)
622 struct ext2_inode inode
;
625 if (fix_problem(fs
, PR_2_DIRECTORY_HOLE
, pctx
) == 0)
629 * Read the inode and block bitmaps in; we'll be messing with
635 * First, find a free block
637 retval
= ext2fs_new_block(fs
, 0, block_found_map
, &blk
);
639 com_err("allocate_dir_block", retval
,
640 "while trying to fill a hole in a directory inode");
643 ext2fs_mark_block_bitmap(block_found_map
, blk
);
644 ext2fs_mark_block_bitmap(fs
->block_map
, blk
);
645 ext2fs_mark_bb_dirty(fs
);
648 * Now let's create the actual data block for the inode
651 retval
= ext2fs_new_dir_block(fs
, 0, 0, &block
);
653 retval
= ext2fs_new_dir_block(fs
, db
->ino
, EXT2_ROOT_INO
,
657 com_err("allocate_dir_block", retval
,
658 "while creating new directory block");
662 retval
= ext2fs_write_dir_block(fs
, blk
, block
);
665 com_err("allocate_dir_block", retval
,
666 "while writing an empty directory block");
671 * Update the inode block count
673 e2fsck_read_inode(fs
, db
->ino
, &inode
, "allocate_dir_block");
674 inode
.i_blocks
+= fs
->blocksize
/ 512;
675 if (inode
.i_size
< (db
->blockcnt
+1) * fs
->blocksize
)
676 inode
.i_size
= (db
->blockcnt
+1) * fs
->blocksize
;
677 e2fsck_write_inode(fs
, db
->ino
, &inode
, "allocate_dir_block");
680 * Finally, update the block pointers for the inode
683 retval
= ext2fs_block_iterate(fs
, db
->ino
, BLOCK_FLAG_HOLE
,
684 0, update_dir_block
, db
);
686 com_err("allocate_dir_block", retval
,
687 "while calling ext2fs_block_iterate");
695 * This is a helper function for allocate_dir_block().
697 static int update_dir_block(ext2_filsys fs
,
702 struct ext2_db_entry
*db
= private;
704 if (db
->blockcnt
== blockcnt
) {
706 return BLOCK_CHANGED
;