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
41 * - The inode_reg_map bitmap
44 #define _GNU_SOURCE 1 /* get strnlen() */
51 #ifdef NO_INLINE_FUNCS
54 #define _INLINE_ inline
57 /* #define DX_DEBUG */
60 * Keeps track of how many times an inode is referenced.
62 static void deallocate_inode(e2fsck_t ctx
, ext2_ino_t ino
, char* block_buf
);
63 static int check_dir_block(ext2_filsys fs
,
64 struct ext2_db_entry
*dir_blocks_info
,
66 static int allocate_dir_block(e2fsck_t ctx
,
67 struct ext2_db_entry
*dir_blocks_info
,
68 char *buf
, struct problem_context
*pctx
);
69 static int update_dir_block(ext2_filsys fs
,
75 static void clear_htree(e2fsck_t ctx
, ext2_ino_t ino
);
76 static int htree_depth(struct dx_dir_info
*dx_dir
,
77 struct dx_dirblock_info
*dx_db
);
78 static EXT2_QSORT_TYPE
special_dir_block_cmp(const void *a
, const void *b
);
80 struct check_dir_struct
{
82 struct problem_context pctx
;
87 void e2fsck_pass2(e2fsck_t ctx
)
89 struct ext2_super_block
*sb
= ctx
->fs
->super
;
90 struct problem_context pctx
;
91 ext2_filsys fs
= ctx
->fs
;
94 struct resource_track rtrack
;
96 struct check_dir_struct cd
;
97 struct dx_dir_info
*dx_dir
;
98 struct dx_dirblock_info
*dx_db
, *dx_parent
;
104 #ifdef RESOURCE_TRACK
105 init_resource_track(&rtrack
);
108 clear_problem_context(&cd
.pctx
);
111 mtrace_print("Pass 2");
114 if (!(ctx
->options
& E2F_OPT_PREEN
))
115 fix_problem(ctx
, PR_2_PASS_HEADER
, &cd
.pctx
);
117 e2fsck_setup_tdb_icount(ctx
, EXT2_ICOUNT_OPT_INCREMENT
,
119 if (ctx
->inode_count
)
122 cd
.pctx
.errcode
= ext2fs_create_icount2(fs
,
123 EXT2_ICOUNT_OPT_INCREMENT
,
124 0, ctx
->inode_link_info
,
126 if (cd
.pctx
.errcode
) {
127 fix_problem(ctx
, PR_2_ALLOCATE_ICOUNT
, &cd
.pctx
);
128 ctx
->flags
|= E2F_FLAG_ABORT
;
131 buf
= (char *) e2fsck_allocate_memory(ctx
, 2*fs
->blocksize
,
132 "directory scan buffer");
135 * Set up the parent pointer for the root directory, if
136 * present. (If the root directory is not present, we will
137 * create it in pass 3.)
139 (void) e2fsck_dir_info_set_parent(ctx
, EXT2_ROOT_INO
, EXT2_ROOT_INO
);
144 cd
.max
= ext2fs_dblist_count(fs
->dblist
);
147 (void) (ctx
->progress
)(ctx
, 2, 0, cd
.max
);
149 if (fs
->super
->s_feature_compat
& EXT2_FEATURE_COMPAT_DIR_INDEX
)
150 ext2fs_dblist_sort(fs
->dblist
, special_dir_block_cmp
);
152 cd
.pctx
.errcode
= ext2fs_dblist_iterate(fs
->dblist
, check_dir_block
,
154 if (ctx
->flags
& E2F_FLAG_SIGNAL_MASK
)
156 if (cd
.pctx
.errcode
) {
157 fix_problem(ctx
, PR_2_DBLIST_ITERATE
, &cd
.pctx
);
158 ctx
->flags
|= E2F_FLAG_ABORT
;
163 for (i
=0; (dx_dir
= e2fsck_dx_dir_info_iter(ctx
, &i
)) != 0;) {
164 if (ctx
->flags
& E2F_FLAG_SIGNAL_MASK
)
166 if (dx_dir
->numblocks
== 0)
168 clear_problem_context(&pctx
);
170 pctx
.dir
= dx_dir
->ino
;
171 dx_db
= dx_dir
->dx_block
;
172 if (dx_db
->flags
& DX_FLAG_REFERENCED
)
173 dx_db
->flags
|= DX_FLAG_DUP_REF
;
175 dx_db
->flags
|= DX_FLAG_REFERENCED
;
177 * Find all of the first and last leaf blocks, and
178 * update their parent's min and max hash values
180 for (b
=0, dx_db
= dx_dir
->dx_block
;
181 b
< dx_dir
->numblocks
;
183 if ((dx_db
->type
!= DX_DIRBLOCK_LEAF
) ||
184 !(dx_db
->flags
& (DX_FLAG_FIRST
| DX_FLAG_LAST
)))
186 dx_parent
= &dx_dir
->dx_block
[dx_db
->parent
];
188 * XXX Make sure dx_parent->min_hash > dx_db->min_hash
190 if (dx_db
->flags
& DX_FLAG_FIRST
)
191 dx_parent
->min_hash
= dx_db
->min_hash
;
193 * XXX Make sure dx_parent->max_hash < dx_db->max_hash
195 if (dx_db
->flags
& DX_FLAG_LAST
)
196 dx_parent
->max_hash
= dx_db
->max_hash
;
199 for (b
=0, dx_db
= dx_dir
->dx_block
;
200 b
< dx_dir
->numblocks
;
203 pctx
.group
= dx_db
->parent
;
205 if (!(dx_db
->flags
& DX_FLAG_FIRST
) &&
206 (dx_db
->min_hash
< dx_db
->node_min_hash
)) {
207 pctx
.blk
= dx_db
->min_hash
;
208 pctx
.blk2
= dx_db
->node_min_hash
;
209 code
= PR_2_HTREE_MIN_HASH
;
210 fix_problem(ctx
, code
, &pctx
);
213 if (dx_db
->type
== DX_DIRBLOCK_LEAF
) {
214 depth
= htree_depth(dx_dir
, dx_db
);
215 if (depth
!= dx_dir
->depth
) {
216 code
= PR_2_HTREE_BAD_DEPTH
;
217 fix_problem(ctx
, code
, &pctx
);
222 * This test doesn't apply for the root block
226 (dx_db
->max_hash
> dx_db
->node_max_hash
)) {
227 pctx
.blk
= dx_db
->max_hash
;
228 pctx
.blk2
= dx_db
->node_max_hash
;
229 code
= PR_2_HTREE_MAX_HASH
;
230 fix_problem(ctx
, code
, &pctx
);
233 if (!(dx_db
->flags
& DX_FLAG_REFERENCED
)) {
234 code
= PR_2_HTREE_NOTREF
;
235 fix_problem(ctx
, code
, &pctx
);
237 } else if (dx_db
->flags
& DX_FLAG_DUP_REF
) {
238 code
= PR_2_HTREE_DUPREF
;
239 fix_problem(ctx
, code
, &pctx
);
245 if (bad_dir
&& fix_problem(ctx
, PR_2_HTREE_CLEAR
, &pctx
)) {
246 clear_htree(ctx
, dx_dir
->ino
);
247 dx_dir
->numblocks
= 0;
251 ext2fs_free_mem(&buf
);
252 ext2fs_free_dblist(fs
->dblist
);
254 if (ctx
->inode_bad_map
) {
255 ext2fs_free_inode_bitmap(ctx
->inode_bad_map
);
256 ctx
->inode_bad_map
= 0;
258 if (ctx
->inode_reg_map
) {
259 ext2fs_free_inode_bitmap(ctx
->inode_reg_map
);
260 ctx
->inode_reg_map
= 0;
263 clear_problem_context(&pctx
);
264 if (ctx
->large_files
) {
265 if (!(sb
->s_feature_ro_compat
&
266 EXT2_FEATURE_RO_COMPAT_LARGE_FILE
) &&
267 fix_problem(ctx
, PR_2_FEATURE_LARGE_FILES
, &pctx
)) {
268 sb
->s_feature_ro_compat
|=
269 EXT2_FEATURE_RO_COMPAT_LARGE_FILE
;
270 fs
->flags
&= ~EXT2_FLAG_MASTER_SB_ONLY
;
271 ext2fs_mark_super_dirty(fs
);
273 if (sb
->s_rev_level
== EXT2_GOOD_OLD_REV
&&
274 fix_problem(ctx
, PR_1_FS_REV_LEVEL
, &pctx
)) {
275 ext2fs_update_dynamic_rev(fs
);
276 ext2fs_mark_super_dirty(fs
);
280 #ifdef RESOURCE_TRACK
281 if (ctx
->options
& E2F_OPT_TIME2
) {
282 e2fsck_clear_progbar(ctx
);
283 print_resource_track(_("Pass 2"), &rtrack
);
288 #define MAX_DEPTH 32000
289 static int htree_depth(struct dx_dir_info
*dx_dir
,
290 struct dx_dirblock_info
*dx_db
)
294 while (dx_db
->type
!= DX_DIRBLOCK_ROOT
&& depth
< MAX_DEPTH
) {
295 dx_db
= &dx_dir
->dx_block
[dx_db
->parent
];
301 static int dict_de_cmp(const void *a
, const void *b
)
303 const struct ext2_dir_entry
*de_a
, *de_b
;
306 de_a
= (const struct ext2_dir_entry
*) a
;
307 a_len
= de_a
->name_len
& 0xFF;
308 de_b
= (const struct ext2_dir_entry
*) b
;
309 b_len
= de_b
->name_len
& 0xFF;
312 return (a_len
- b_len
);
314 return strncmp(de_a
->name
, de_b
->name
, a_len
);
318 * This is special sort function that makes sure that directory blocks
319 * with a dirblock of zero are sorted to the beginning of the list.
320 * This guarantees that the root node of the htree directories are
321 * processed first, so we know what hash version to use.
323 static EXT2_QSORT_TYPE
special_dir_block_cmp(const void *a
, const void *b
)
325 const struct ext2_db_entry
*db_a
=
326 (const struct ext2_db_entry
*) a
;
327 const struct ext2_db_entry
*db_b
=
328 (const struct ext2_db_entry
*) b
;
330 if (db_a
->blockcnt
&& !db_b
->blockcnt
)
333 if (!db_a
->blockcnt
&& db_b
->blockcnt
)
336 if (db_a
->blk
!= db_b
->blk
)
337 return (int) (db_a
->blk
- db_b
->blk
);
339 if (db_a
->ino
!= db_b
->ino
)
340 return (int) (db_a
->ino
- db_b
->ino
);
342 return (int) (db_a
->blockcnt
- db_b
->blockcnt
);
347 * Make sure the first entry in the directory is '.', and that the
348 * directory entry is sane.
350 static int check_dot(e2fsck_t ctx
,
351 struct ext2_dir_entry
*dirent
,
352 ext2_ino_t ino
, struct problem_context
*pctx
)
354 struct ext2_dir_entry
*nextdir
;
361 problem
= PR_2_MISSING_DOT
;
362 else if (((dirent
->name_len
& 0xFF) != 1) ||
363 (dirent
->name
[0] != '.'))
364 problem
= PR_2_1ST_NOT_DOT
;
365 else if (dirent
->name
[1] != '\0')
366 problem
= PR_2_DOT_NULL_TERM
;
369 if (fix_problem(ctx
, problem
, pctx
)) {
370 if (dirent
->rec_len
< 12)
371 dirent
->rec_len
= 12;
373 dirent
->name_len
= 1;
374 dirent
->name
[0] = '.';
375 dirent
->name
[1] = '\0';
380 if (dirent
->inode
!= ino
) {
381 if (fix_problem(ctx
, PR_2_BAD_INODE_DOT
, pctx
)) {
386 if (dirent
->rec_len
> 12) {
387 new_len
= dirent
->rec_len
- 12;
390 fix_problem(ctx
, PR_2_SPLIT_DOT
, pctx
)) {
391 nextdir
= (struct ext2_dir_entry
*)
392 ((char *) dirent
+ 12);
393 dirent
->rec_len
= 12;
394 nextdir
->rec_len
= new_len
;
396 nextdir
->name_len
= 0;
405 * Make sure the second entry in the directory is '..', and that the
406 * directory entry is sane. We do not check the inode number of '..'
407 * here; this gets done in pass 3.
409 static int check_dotdot(e2fsck_t ctx
,
410 struct ext2_dir_entry
*dirent
,
411 ext2_ino_t ino
, struct problem_context
*pctx
)
416 problem
= PR_2_MISSING_DOT_DOT
;
417 else if (((dirent
->name_len
& 0xFF) != 2) ||
418 (dirent
->name
[0] != '.') ||
419 (dirent
->name
[1] != '.'))
420 problem
= PR_2_2ND_NOT_DOT_DOT
;
421 else if (dirent
->name
[2] != '\0')
422 problem
= PR_2_DOT_DOT_NULL_TERM
;
425 if (fix_problem(ctx
, problem
, pctx
)) {
426 if (dirent
->rec_len
< 12)
427 dirent
->rec_len
= 12;
429 * Note: we don't have the parent inode just
430 * yet, so we will fill it in with the root
431 * inode. This will get fixed in pass 3.
433 dirent
->inode
= EXT2_ROOT_INO
;
434 dirent
->name_len
= 2;
435 dirent
->name
[0] = '.';
436 dirent
->name
[1] = '.';
437 dirent
->name
[2] = '\0';
442 if (e2fsck_dir_info_set_dotdot(ctx
, ino
, dirent
->inode
)) {
443 fix_problem(ctx
, PR_2_NO_DIRINFO
, pctx
);
450 * Check to make sure a directory entry doesn't contain any illegal
453 static int check_name(e2fsck_t ctx
,
454 struct ext2_dir_entry
*dirent
,
455 ext2_ino_t dir_ino
EXT2FS_ATTR((unused
)),
456 struct problem_context
*pctx
)
462 for ( i
= 0; i
< (dirent
->name_len
& 0xFF); i
++) {
463 if (dirent
->name
[i
] == '/' || dirent
->name
[i
] == '\0') {
465 fixup
= fix_problem(ctx
, PR_2_BAD_NAME
, pctx
);
468 dirent
->name
[i
] = '.';
477 * Check the directory filetype (if present)
479 static _INLINE_
int check_filetype(e2fsck_t ctx
,
480 struct ext2_dir_entry
*dirent
,
481 ext2_ino_t dir_ino
EXT2FS_ATTR((unused
)),
482 struct problem_context
*pctx
)
484 int filetype
= dirent
->name_len
>> 8;
485 int should_be
= EXT2_FT_UNKNOWN
;
486 struct ext2_inode inode
;
488 if (!(ctx
->fs
->super
->s_feature_incompat
&
489 EXT2_FEATURE_INCOMPAT_FILETYPE
)) {
491 !fix_problem(ctx
, PR_2_CLEAR_FILETYPE
, pctx
))
493 dirent
->name_len
= dirent
->name_len
& 0xFF;
497 if (ext2fs_test_inode_bitmap(ctx
->inode_dir_map
, dirent
->inode
)) {
498 should_be
= EXT2_FT_DIR
;
499 } else if (ext2fs_test_inode_bitmap(ctx
->inode_reg_map
,
501 should_be
= EXT2_FT_REG_FILE
;
502 } else if (ctx
->inode_bad_map
&&
503 ext2fs_test_inode_bitmap(ctx
->inode_bad_map
,
507 e2fsck_read_inode(ctx
, dirent
->inode
, &inode
,
509 should_be
= ext2_file_type(inode
.i_mode
);
511 if (filetype
== should_be
)
513 pctx
->num
= should_be
;
515 if (fix_problem(ctx
, filetype
? PR_2_BAD_FILETYPE
: PR_2_SET_FILETYPE
,
519 dirent
->name_len
= (dirent
->name_len
& 0xFF) | should_be
<< 8;
524 static void parse_int_node(ext2_filsys fs
,
525 struct ext2_db_entry
*db
,
526 struct check_dir_struct
*cd
,
527 struct dx_dir_info
*dx_dir
,
530 struct ext2_dx_root_info
*root
;
531 struct ext2_dx_entry
*ent
;
532 struct ext2_dx_countlimit
*limit
;
533 struct dx_dirblock_info
*dx_db
;
534 int i
, expect_limit
, count
;
536 ext2_dirhash_t min_hash
= 0xffffffff;
537 ext2_dirhash_t max_hash
= 0;
538 ext2_dirhash_t hash
= 0, prev_hash
;
540 if (db
->blockcnt
== 0) {
541 root
= (struct ext2_dx_root_info
*) (block_buf
+ 24);
544 printf("Root node dump:\n");
545 printf("\t Reserved zero: %u\n", root
->reserved_zero
);
546 printf("\t Hash Version: %d\n", root
->hash_version
);
547 printf("\t Info length: %d\n", root
->info_length
);
548 printf("\t Indirect levels: %d\n", root
->indirect_levels
);
549 printf("\t Flags: %d\n", root
->unused_flags
);
552 ent
= (struct ext2_dx_entry
*) (block_buf
+ 24 + root
->info_length
);
554 ent
= (struct ext2_dx_entry
*) (block_buf
+8);
556 limit
= (struct ext2_dx_countlimit
*) ent
;
559 printf("Number of entries (count): %d\n",
560 ext2fs_le16_to_cpu(limit
->count
));
561 printf("Number of entries (limit): %d\n",
562 ext2fs_le16_to_cpu(limit
->limit
));
565 count
= ext2fs_le16_to_cpu(limit
->count
);
566 expect_limit
= (fs
->blocksize
- ((char *) ent
- block_buf
)) /
567 sizeof(struct ext2_dx_entry
);
568 if (ext2fs_le16_to_cpu(limit
->limit
) != expect_limit
) {
569 cd
->pctx
.num
= ext2fs_le16_to_cpu(limit
->limit
);
570 if (fix_problem(cd
->ctx
, PR_2_HTREE_BAD_LIMIT
, &cd
->pctx
))
573 if (count
> expect_limit
) {
574 cd
->pctx
.num
= count
;
575 if (fix_problem(cd
->ctx
, PR_2_HTREE_BAD_COUNT
, &cd
->pctx
))
577 count
= expect_limit
;
580 for (i
=0; i
< count
; i
++) {
582 hash
= i
? (ext2fs_le32_to_cpu(ent
[i
].hash
) & ~1) : 0;
584 printf("Entry #%d: Hash 0x%08x, block %u\n", i
,
585 hash
, ext2fs_le32_to_cpu(ent
[i
].block
));
587 blk
= ext2fs_le32_to_cpu(ent
[i
].block
) & 0x0ffffff;
588 /* Check to make sure the block is valid */
589 if (blk
>= (blk_t
) dx_dir
->numblocks
) {
591 if (fix_problem(cd
->ctx
, PR_2_HTREE_BADBLK
,
596 if (hash
< prev_hash
&&
597 fix_problem(cd
->ctx
, PR_2_HTREE_HASH_ORDER
, &cd
->pctx
))
599 dx_db
= &dx_dir
->dx_block
[blk
];
600 if (dx_db
->flags
& DX_FLAG_REFERENCED
) {
601 dx_db
->flags
|= DX_FLAG_DUP_REF
;
603 dx_db
->flags
|= DX_FLAG_REFERENCED
;
604 dx_db
->parent
= db
->blockcnt
;
610 dx_db
->node_min_hash
= hash
;
612 dx_db
->node_max_hash
=
613 ext2fs_le32_to_cpu(ent
[i
+1].hash
) & ~1;
615 dx_db
->node_max_hash
= 0xfffffffe;
616 dx_db
->flags
|= DX_FLAG_LAST
;
619 dx_db
->flags
|= DX_FLAG_FIRST
;
622 printf("Blockcnt = %d, min hash 0x%08x, max hash 0x%08x\n",
623 db
->blockcnt
, min_hash
, max_hash
);
625 dx_db
= &dx_dir
->dx_block
[db
->blockcnt
];
626 dx_db
->min_hash
= min_hash
;
627 dx_db
->max_hash
= max_hash
;
631 clear_htree(cd
->ctx
, cd
->pctx
.ino
);
632 dx_dir
->numblocks
= 0;
634 #endif /* ENABLE_HTREE */
637 * Given a busted directory, try to salvage it somehow.
640 static void salvage_directory(ext2_filsys fs
,
641 struct ext2_dir_entry
*dirent
,
642 struct ext2_dir_entry
*prev
,
643 unsigned int *offset
)
645 char *cp
= (char *) dirent
;
646 int left
= fs
->blocksize
- *offset
- dirent
->rec_len
;
647 unsigned int name_len
= dirent
->name_len
& 0xFF;
650 * Special case of directory entry of size 8: copy what's left
651 * of the directory block up to cover up the invalid hole.
653 if ((left
>= 12) && (dirent
->rec_len
== 8)) {
654 memmove(cp
, cp
+8, left
);
655 memset(cp
+ left
, 0, 8);
659 * If the directory entry overruns the end of the directory
660 * block, and the name is small enough to fit, then adjust the
664 (name_len
+ 8 <= dirent
->rec_len
+ (unsigned) left
) &&
665 dirent
->inode
<= fs
->super
->s_inodes_count
&&
666 strnlen(dirent
->name
, name_len
) == name_len
) {
667 dirent
->rec_len
+= left
;
671 * If the record length of the directory entry is a multiple
672 * of four, and not too big, such that it is valid, let the
673 * previous directory entry absorb the invalid one.
675 if (prev
&& dirent
->rec_len
&& (dirent
->rec_len
% 4) == 0 &&
676 (*offset
+ dirent
->rec_len
<= fs
->blocksize
)) {
677 prev
->rec_len
+= dirent
->rec_len
;
678 *offset
+= dirent
->rec_len
;
682 * Default salvage method --- kill all of the directory
683 * entries for the rest of the block. We will either try to
684 * absorb it into the previous directory entry, or create a
685 * new empty directory entry the rest of the directory block.
688 prev
->rec_len
+= fs
->blocksize
- *offset
;
689 *offset
= fs
->blocksize
;
691 dirent
->rec_len
= fs
->blocksize
- *offset
;
692 dirent
->name_len
= 0;
697 static int check_dir_block(ext2_filsys fs
,
698 struct ext2_db_entry
*db
,
701 struct dx_dir_info
*dx_dir
;
703 struct dx_dirblock_info
*dx_db
= 0;
704 #endif /* ENABLE_HTREE */
705 struct ext2_dir_entry
*dirent
, *prev
;
707 unsigned int offset
= 0;
709 int dir_modified
= 0;
711 blk_t block_nr
= db
->blk
;
712 ext2_ino_t ino
= db
->ino
;
713 ext2_ino_t subdir_parent
;
715 struct check_dir_struct
*cd
;
719 struct ext2_dx_root_info
*root
;
720 struct ext2_dx_countlimit
*limit
;
721 static dict_t de_dict
;
722 struct problem_context pctx
;
726 cd
= (struct check_dir_struct
*) priv_data
;
730 if (ctx
->flags
& E2F_FLAG_SIGNAL_MASK
)
733 if (ctx
->progress
&& (ctx
->progress
)(ctx
, 2, cd
->count
++, cd
->max
))
737 * Make sure the inode is still in use (could have been
738 * deleted in the duplicate/bad blocks pass.
740 if (!(ext2fs_test_inode_bitmap(ctx
->inode_used_map
, ino
)))
744 cd
->pctx
.blk
= block_nr
;
745 cd
->pctx
.blkcount
= db
->blockcnt
;
751 if (allocate_dir_block(ctx
, db
, buf
, &cd
->pctx
))
761 if (ctx
->dirs_to_hash
&&
762 ext2fs_u32_list_test(ctx
->dirs_to_hash
, ino
))
766 printf("In process_dir_block block %lu, #%d, inode %lu\n", block_nr
,
770 old_op
= ehandler_operation(_("reading directory block"));
771 cd
->pctx
.errcode
= ext2fs_read_dir_block(fs
, block_nr
, buf
);
772 ehandler_operation(0);
773 if (cd
->pctx
.errcode
== EXT2_ET_DIR_CORRUPTED
)
774 cd
->pctx
.errcode
= 0; /* We'll handle this ourselves */
775 if (cd
->pctx
.errcode
) {
776 if (!fix_problem(ctx
, PR_2_READ_DIRBLOCK
, &cd
->pctx
)) {
777 ctx
->flags
|= E2F_FLAG_ABORT
;
780 memset(buf
, 0, fs
->blocksize
);
783 dx_dir
= e2fsck_get_dx_dir_info(ctx
, ino
);
784 if (dx_dir
&& dx_dir
->numblocks
) {
785 if (db
->blockcnt
>= dx_dir
->numblocks
) {
786 printf("XXX should never happen!!!\n");
789 dx_db
= &dx_dir
->dx_block
[db
->blockcnt
];
790 dx_db
->type
= DX_DIRBLOCK_LEAF
;
791 dx_db
->phys
= block_nr
;
792 dx_db
->min_hash
= ~0;
795 dirent
= (struct ext2_dir_entry
*) buf
;
796 limit
= (struct ext2_dx_countlimit
*) (buf
+8);
797 if (db
->blockcnt
== 0) {
798 root
= (struct ext2_dx_root_info
*) (buf
+ 24);
799 dx_db
->type
= DX_DIRBLOCK_ROOT
;
800 dx_db
->flags
|= DX_FLAG_FIRST
| DX_FLAG_LAST
;
801 if ((root
->reserved_zero
||
802 root
->info_length
< 8 ||
803 root
->indirect_levels
> 1) &&
804 fix_problem(ctx
, PR_2_HTREE_BAD_ROOT
, &cd
->pctx
)) {
805 clear_htree(ctx
, ino
);
806 dx_dir
->numblocks
= 0;
809 dx_dir
->hashversion
= root
->hash_version
;
810 if ((dx_dir
->hashversion
<= EXT2_HASH_TEA
) &&
811 (fs
->super
->s_flags
& EXT2_FLAGS_UNSIGNED_HASH
))
812 dx_dir
->hashversion
+= 3;
813 dx_dir
->depth
= root
->indirect_levels
+ 1;
814 } else if ((dirent
->inode
== 0) &&
815 (dirent
->rec_len
== fs
->blocksize
) &&
816 (dirent
->name_len
== 0) &&
817 (ext2fs_le16_to_cpu(limit
->limit
) ==
819 sizeof(struct ext2_dx_entry
))))
820 dx_db
->type
= DX_DIRBLOCK_NODE
;
822 #endif /* ENABLE_HTREE */
824 dict_init(&de_dict
, DICTCOUNT_T_MAX
, dict_de_cmp
);
828 dirent
= (struct ext2_dir_entry
*) (buf
+ offset
);
829 cd
->pctx
.dirent
= dirent
;
830 cd
->pctx
.num
= offset
;
831 if (((offset
+ dirent
->rec_len
) > fs
->blocksize
) ||
832 (dirent
->rec_len
< 12) ||
833 ((dirent
->rec_len
% 4) != 0) ||
834 (((dirent
->name_len
& 0xFF)+8) > dirent
->rec_len
)) {
835 if (fix_problem(ctx
, PR_2_DIR_CORRUPTED
, &cd
->pctx
)) {
836 salvage_directory(fs
, dirent
, prev
, &offset
);
840 goto abort_free_dict
;
842 if ((dirent
->name_len
& 0xFF) > EXT2_NAME_LEN
) {
843 if (fix_problem(ctx
, PR_2_FILENAME_LONG
, &cd
->pctx
)) {
844 dirent
->name_len
= EXT2_NAME_LEN
;
849 if (dot_state
== 0) {
850 if (check_dot(ctx
, dirent
, ino
, &cd
->pctx
))
852 } else if (dot_state
== 1) {
853 ret
= check_dotdot(ctx
, dirent
, ino
, &cd
->pctx
);
855 goto abort_free_dict
;
858 } else if (dirent
->inode
== ino
) {
859 problem
= PR_2_LINK_DOT
;
860 if (fix_problem(ctx
, PR_2_LINK_DOT
, &cd
->pctx
)) {
870 * Make sure the inode listed is a legal one.
872 if (((dirent
->inode
!= EXT2_ROOT_INO
) &&
873 (dirent
->inode
< EXT2_FIRST_INODE(fs
->super
))) ||
874 (dirent
->inode
> fs
->super
->s_inodes_count
)) {
875 problem
= PR_2_BAD_INO
;
876 } else if (!(ext2fs_test_inode_bitmap(ctx
->inode_used_map
,
879 * If the inode is unused, offer to clear it.
881 problem
= PR_2_UNUSED_INODE
;
882 } else if (ctx
->inode_bb_map
&&
883 (ext2fs_test_inode_bitmap(ctx
->inode_bb_map
,
886 * If the inode is in a bad block, offer to
889 problem
= PR_2_BB_INODE
;
890 } else if ((dot_state
> 1) &&
891 ((dirent
->name_len
& 0xFF) == 1) &&
892 (dirent
->name
[0] == '.')) {
894 * If there's a '.' entry in anything other
895 * than the first directory entry, it's a
896 * duplicate entry that should be removed.
898 problem
= PR_2_DUP_DOT
;
899 } else if ((dot_state
> 1) &&
900 ((dirent
->name_len
& 0xFF) == 2) &&
901 (dirent
->name
[0] == '.') &&
902 (dirent
->name
[1] == '.')) {
904 * If there's a '..' entry in anything other
905 * than the second directory entry, it's a
906 * duplicate entry that should be removed.
908 problem
= PR_2_DUP_DOT_DOT
;
909 } else if ((dot_state
> 1) &&
910 (dirent
->inode
== EXT2_ROOT_INO
)) {
912 * Don't allow links to the root directory.
913 * We check this specially to make sure we
914 * catch this error case even if the root
915 * directory hasn't been created yet.
917 problem
= PR_2_LINK_ROOT
;
918 } else if ((dot_state
> 1) &&
919 (dirent
->name_len
& 0xFF) == 0) {
921 * Don't allow zero-length directory names.
923 problem
= PR_2_NULL_NAME
;
927 if (fix_problem(ctx
, problem
, &cd
->pctx
)) {
932 ext2fs_unmark_valid(fs
);
933 if (problem
== PR_2_BAD_INO
)
939 * If the inode was marked as having bad fields in
940 * pass1, process it and offer to fix/clear it.
941 * (We wait until now so that we can display the
942 * pathname to the user.)
944 if (ctx
->inode_bad_map
&&
945 ext2fs_test_inode_bitmap(ctx
->inode_bad_map
,
947 if (e2fsck_process_bad_inode(ctx
, ino
,
949 buf
+ fs
->blocksize
)) {
954 if (ctx
->flags
& E2F_FLAG_SIGNAL_MASK
)
958 if (check_name(ctx
, dirent
, ino
, &cd
->pctx
))
961 if (check_filetype(ctx
, dirent
, ino
, &cd
->pctx
))
966 ext2fs_dirhash(dx_dir
->hashversion
, dirent
->name
,
967 (dirent
->name_len
& 0xFF),
968 fs
->super
->s_hash_seed
, &hash
, 0);
969 if (hash
< dx_db
->min_hash
)
970 dx_db
->min_hash
= hash
;
971 if (hash
> dx_db
->max_hash
)
972 dx_db
->max_hash
= hash
;
977 * If this is a directory, then mark its parent in its
978 * dir_info structure. If the parent field is already
979 * filled in, then this directory has more than one
980 * hard link. We assume the first link is correct,
981 * and ask the user if he/she wants to clear this one.
983 if ((dot_state
> 1) &&
984 (ext2fs_test_inode_bitmap(ctx
->inode_dir_map
,
986 if (e2fsck_dir_info_get_parent(ctx
, dirent
->inode
,
988 cd
->pctx
.ino
= dirent
->inode
;
989 fix_problem(ctx
, PR_2_NO_DIRINFO
, &cd
->pctx
);
990 goto abort_free_dict
;
993 cd
->pctx
.ino2
= subdir_parent
;
994 if (fix_problem(ctx
, PR_2_LINK_DIR
,
1002 (void) e2fsck_dir_info_set_parent(ctx
,
1003 dirent
->inode
, ino
);
1009 } else if (dict_lookup(&de_dict
, dirent
)) {
1010 clear_problem_context(&pctx
);
1012 pctx
.dirent
= dirent
;
1013 fix_problem(ctx
, PR_2_REPORT_DUP_DIRENT
, &pctx
);
1014 if (!ctx
->dirs_to_hash
)
1015 ext2fs_u32_list_create(&ctx
->dirs_to_hash
, 50);
1016 if (ctx
->dirs_to_hash
)
1017 ext2fs_u32_list_add(ctx
->dirs_to_hash
, ino
);
1020 dict_alloc_insert(&de_dict
, dirent
, dirent
);
1022 ext2fs_icount_increment(ctx
->inode_count
, dirent
->inode
,
1025 ctx
->fs_links_count
++;
1026 ctx
->fs_total_count
++;
1029 offset
+= dirent
->rec_len
;
1031 } while (offset
< fs
->blocksize
);
1038 printf("db_block %d, type %d, min_hash 0x%0x, max_hash 0x%0x\n",
1039 db
->blockcnt
, dx_db
->type
,
1040 dx_db
->min_hash
, dx_db
->max_hash
);
1042 cd
->pctx
.dir
= cd
->pctx
.ino
;
1043 if ((dx_db
->type
== DX_DIRBLOCK_ROOT
) ||
1044 (dx_db
->type
== DX_DIRBLOCK_NODE
))
1045 parse_int_node(fs
, db
, cd
, dx_dir
, buf
);
1047 #endif /* ENABLE_HTREE */
1048 if (offset
!= fs
->blocksize
) {
1049 cd
->pctx
.num
= dirent
->rec_len
- fs
->blocksize
+ offset
;
1050 if (fix_problem(ctx
, PR_2_FINAL_RECLEN
, &cd
->pctx
)) {
1051 dirent
->rec_len
= cd
->pctx
.num
;
1056 cd
->pctx
.errcode
= ext2fs_write_dir_block(fs
, block_nr
, buf
);
1057 if (cd
->pctx
.errcode
) {
1058 if (!fix_problem(ctx
, PR_2_WRITE_DIRBLOCK
,
1060 goto abort_free_dict
;
1062 ext2fs_mark_changed(fs
);
1064 dict_free_nodes(&de_dict
);
1067 dict_free_nodes(&de_dict
);
1068 ctx
->flags
|= E2F_FLAG_ABORT
;
1069 return DIRENT_ABORT
;
1073 * This function is called to deallocate a block, and is an interator
1074 * functioned called by deallocate inode via ext2fs_iterate_block().
1076 static int deallocate_inode_block(ext2_filsys fs
,
1078 e2_blkcnt_t blockcnt
EXT2FS_ATTR((unused
)),
1079 blk_t ref_block
EXT2FS_ATTR((unused
)),
1080 int ref_offset
EXT2FS_ATTR((unused
)),
1083 e2fsck_t ctx
= (e2fsck_t
) priv_data
;
1085 if (HOLE_BLKADDR(*block_nr
))
1087 if ((*block_nr
< fs
->super
->s_first_data_block
) ||
1088 (*block_nr
>= fs
->super
->s_blocks_count
))
1090 ext2fs_unmark_block_bitmap(ctx
->block_found_map
, *block_nr
);
1091 ext2fs_block_alloc_stats(fs
, *block_nr
, -1);
1096 * This fuction deallocates an inode
1098 static void deallocate_inode(e2fsck_t ctx
, ext2_ino_t ino
, char* block_buf
)
1100 ext2_filsys fs
= ctx
->fs
;
1101 struct ext2_inode inode
;
1102 struct problem_context pctx
;
1105 ext2fs_icount_store(ctx
->inode_link_info
, ino
, 0);
1106 e2fsck_read_inode(ctx
, ino
, &inode
, "deallocate_inode");
1107 inode
.i_links_count
= 0;
1108 inode
.i_dtime
= ctx
->now
;
1109 e2fsck_write_inode(ctx
, ino
, &inode
, "deallocate_inode");
1110 clear_problem_context(&pctx
);
1114 * Fix up the bitmaps...
1116 e2fsck_read_bitmaps(ctx
);
1117 ext2fs_unmark_inode_bitmap(ctx
->inode_used_map
, ino
);
1118 ext2fs_unmark_inode_bitmap(ctx
->inode_dir_map
, ino
);
1119 if (ctx
->inode_bad_map
)
1120 ext2fs_unmark_inode_bitmap(ctx
->inode_bad_map
, ino
);
1121 ext2fs_inode_alloc_stats2(fs
, ino
, -1, LINUX_S_ISDIR(inode
.i_mode
));
1123 if (inode
.i_file_acl
&&
1124 (fs
->super
->s_feature_compat
& EXT2_FEATURE_COMPAT_EXT_ATTR
)) {
1125 pctx
.errcode
= ext2fs_adjust_ea_refcount(fs
, inode
.i_file_acl
,
1126 block_buf
, -1, &count
);
1127 if (pctx
.errcode
== EXT2_ET_BAD_EA_BLOCK_NUM
) {
1132 pctx
.blk
= inode
.i_file_acl
;
1133 fix_problem(ctx
, PR_2_ADJ_EA_REFCOUNT
, &pctx
);
1134 ctx
->flags
|= E2F_FLAG_ABORT
;
1138 ext2fs_unmark_block_bitmap(ctx
->block_found_map
,
1140 ext2fs_block_alloc_stats(fs
, inode
.i_file_acl
, -1);
1142 inode
.i_file_acl
= 0;
1145 if (!ext2fs_inode_has_valid_blocks(&inode
))
1148 if (LINUX_S_ISREG(inode
.i_mode
) &&
1149 (inode
.i_size_high
|| inode
.i_size
& 0x80000000UL
))
1152 pctx
.errcode
= ext2fs_block_iterate2(fs
, ino
, 0, block_buf
,
1153 deallocate_inode_block
, ctx
);
1155 fix_problem(ctx
, PR_2_DEALLOC_INODE
, &pctx
);
1156 ctx
->flags
|= E2F_FLAG_ABORT
;
1162 * This fuction clears the htree flag on an inode
1164 static void clear_htree(e2fsck_t ctx
, ext2_ino_t ino
)
1166 struct ext2_inode inode
;
1168 e2fsck_read_inode(ctx
, ino
, &inode
, "clear_htree");
1169 inode
.i_flags
= inode
.i_flags
& ~EXT2_INDEX_FL
;
1170 e2fsck_write_inode(ctx
, ino
, &inode
, "clear_htree");
1171 if (ctx
->dirs_to_hash
)
1172 ext2fs_u32_list_add(ctx
->dirs_to_hash
, ino
);
1176 extern int e2fsck_process_bad_inode(e2fsck_t ctx
, ext2_ino_t dir
,
1177 ext2_ino_t ino
, char *buf
)
1179 ext2_filsys fs
= ctx
->fs
;
1180 struct ext2_inode inode
;
1181 int inode_modified
= 0;
1183 unsigned char *frag
, *fsize
;
1184 struct problem_context pctx
;
1187 e2fsck_read_inode(ctx
, ino
, &inode
, "process_bad_inode");
1189 clear_problem_context(&pctx
);
1192 pctx
.inode
= &inode
;
1194 if (inode
.i_file_acl
&&
1195 !(fs
->super
->s_feature_compat
& EXT2_FEATURE_COMPAT_EXT_ATTR
)) {
1196 if (fix_problem(ctx
, PR_2_FILE_ACL_ZERO
, &pctx
)) {
1197 inode
.i_file_acl
= 0;
1203 if (!LINUX_S_ISDIR(inode
.i_mode
) && !LINUX_S_ISREG(inode
.i_mode
) &&
1204 !LINUX_S_ISCHR(inode
.i_mode
) && !LINUX_S_ISBLK(inode
.i_mode
) &&
1205 !LINUX_S_ISLNK(inode
.i_mode
) && !LINUX_S_ISFIFO(inode
.i_mode
) &&
1206 !(LINUX_S_ISSOCK(inode
.i_mode
)))
1207 problem
= PR_2_BAD_MODE
;
1208 else if (LINUX_S_ISCHR(inode
.i_mode
)
1209 && !e2fsck_pass1_check_device_inode(fs
, &inode
))
1210 problem
= PR_2_BAD_CHAR_DEV
;
1211 else if (LINUX_S_ISBLK(inode
.i_mode
)
1212 && !e2fsck_pass1_check_device_inode(fs
, &inode
))
1213 problem
= PR_2_BAD_BLOCK_DEV
;
1214 else if (LINUX_S_ISFIFO(inode
.i_mode
)
1215 && !e2fsck_pass1_check_device_inode(fs
, &inode
))
1216 problem
= PR_2_BAD_FIFO
;
1217 else if (LINUX_S_ISSOCK(inode
.i_mode
)
1218 && !e2fsck_pass1_check_device_inode(fs
, &inode
))
1219 problem
= PR_2_BAD_SOCKET
;
1220 else if (LINUX_S_ISLNK(inode
.i_mode
)
1221 && !e2fsck_pass1_check_symlink(fs
, &inode
, buf
)) {
1222 problem
= PR_2_INVALID_SYMLINK
;
1226 if (fix_problem(ctx
, problem
, &pctx
)) {
1227 deallocate_inode(ctx
, ino
, 0);
1228 if (ctx
->flags
& E2F_FLAG_SIGNAL_MASK
)
1236 if (inode
.i_faddr
) {
1237 if (fix_problem(ctx
, PR_2_FADDR_ZERO
, &pctx
)) {
1244 switch (fs
->super
->s_creator_os
) {
1246 frag
= &inode
.osd2
.hurd2
.h_i_frag
;
1247 fsize
= &inode
.osd2
.hurd2
.h_i_fsize
;
1250 frag
= &inode
.osd2
.masix2
.m_i_frag
;
1251 fsize
= &inode
.osd2
.masix2
.m_i_fsize
;
1256 if (frag
&& *frag
) {
1258 if (fix_problem(ctx
, PR_2_FRAG_ZERO
, &pctx
)) {
1265 if (fsize
&& *fsize
) {
1267 if (fix_problem(ctx
, PR_2_FSIZE_ZERO
, &pctx
)) {
1275 if ((fs
->super
->s_creator_os
== EXT2_OS_LINUX
) &&
1276 !(fs
->super
->s_feature_ro_compat
&
1277 EXT4_FEATURE_RO_COMPAT_HUGE_FILE
) &&
1278 (inode
.osd2
.linux2
.l_i_blocks_hi
!= 0)) {
1279 pctx
.num
= inode
.osd2
.linux2
.l_i_blocks_hi
;
1280 if (fix_problem(ctx
, PR_2_BLOCKS_HI_ZERO
, &pctx
)) {
1281 inode
.osd2
.linux2
.l_i_blocks_hi
= 0;
1286 if (inode
.i_file_acl
&&
1287 ((inode
.i_file_acl
< fs
->super
->s_first_data_block
) ||
1288 (inode
.i_file_acl
>= fs
->super
->s_blocks_count
))) {
1289 if (fix_problem(ctx
, PR_2_FILE_ACL_BAD
, &pctx
)) {
1290 inode
.i_file_acl
= 0;
1295 if (inode
.i_dir_acl
&&
1296 LINUX_S_ISDIR(inode
.i_mode
)) {
1297 if (fix_problem(ctx
, PR_2_DIR_ACL_ZERO
, &pctx
)) {
1298 inode
.i_dir_acl
= 0;
1305 e2fsck_write_inode(ctx
, ino
, &inode
, "process_bad_inode");
1306 if (!not_fixed
&& ctx
->inode_bad_map
)
1307 ext2fs_unmark_inode_bitmap(ctx
->inode_bad_map
, ino
);
1313 * allocate_dir_block --- this function allocates a new directory
1314 * block for a particular inode; this is done if a directory has
1315 * a "hole" in it, or if a directory has a illegal block number
1316 * that was zeroed out and now needs to be replaced.
1318 static int allocate_dir_block(e2fsck_t ctx
,
1319 struct ext2_db_entry
*db
,
1320 char *buf
EXT2FS_ATTR((unused
)),
1321 struct problem_context
*pctx
)
1323 ext2_filsys fs
= ctx
->fs
;
1326 struct ext2_inode inode
;
1328 if (fix_problem(ctx
, PR_2_DIRECTORY_HOLE
, pctx
) == 0)
1332 * Read the inode and block bitmaps in; we'll be messing with
1335 e2fsck_read_bitmaps(ctx
);
1338 * First, find a free block
1340 pctx
->errcode
= ext2fs_new_block(fs
, 0, ctx
->block_found_map
, &blk
);
1341 if (pctx
->errcode
) {
1342 pctx
->str
= "ext2fs_new_block";
1343 fix_problem(ctx
, PR_2_ALLOC_DIRBOCK
, pctx
);
1346 ext2fs_mark_block_bitmap(ctx
->block_found_map
, blk
);
1347 ext2fs_mark_block_bitmap(fs
->block_map
, blk
);
1348 ext2fs_mark_bb_dirty(fs
);
1351 * Now let's create the actual data block for the inode
1354 pctx
->errcode
= ext2fs_new_dir_block(fs
, 0, 0, &block
);
1356 pctx
->errcode
= ext2fs_new_dir_block(fs
, db
->ino
,
1357 EXT2_ROOT_INO
, &block
);
1359 if (pctx
->errcode
) {
1360 pctx
->str
= "ext2fs_new_dir_block";
1361 fix_problem(ctx
, PR_2_ALLOC_DIRBOCK
, pctx
);
1365 pctx
->errcode
= ext2fs_write_dir_block(fs
, blk
, block
);
1366 ext2fs_free_mem(&block
);
1367 if (pctx
->errcode
) {
1368 pctx
->str
= "ext2fs_write_dir_block";
1369 fix_problem(ctx
, PR_2_ALLOC_DIRBOCK
, pctx
);
1374 * Update the inode block count
1376 e2fsck_read_inode(ctx
, db
->ino
, &inode
, "allocate_dir_block");
1377 inode
.i_blocks
+= fs
->blocksize
/ 512;
1378 if (inode
.i_size
< (db
->blockcnt
+1) * fs
->blocksize
)
1379 inode
.i_size
= (db
->blockcnt
+1) * fs
->blocksize
;
1380 e2fsck_write_inode(ctx
, db
->ino
, &inode
, "allocate_dir_block");
1383 * Finally, update the block pointers for the inode
1386 pctx
->errcode
= ext2fs_block_iterate2(fs
, db
->ino
, BLOCK_FLAG_HOLE
,
1387 0, update_dir_block
, db
);
1388 if (pctx
->errcode
) {
1389 pctx
->str
= "ext2fs_block_iterate";
1390 fix_problem(ctx
, PR_2_ALLOC_DIRBOCK
, pctx
);
1398 * This is a helper function for allocate_dir_block().
1400 static int update_dir_block(ext2_filsys fs
EXT2FS_ATTR((unused
)),
1402 e2_blkcnt_t blockcnt
,
1403 blk_t ref_block
EXT2FS_ATTR((unused
)),
1404 int ref_offset
EXT2FS_ATTR((unused
)),
1407 struct ext2_db_entry
*db
;
1409 db
= (struct ext2_db_entry
*) priv_data
;
1410 if (db
->blockcnt
== (int) blockcnt
) {
1411 *block_nr
= db
->blk
;
1412 return BLOCK_CHANGED
;