2 * pass3.c -- pass #3 of e2fsck: Check for directory connectivity
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 #3 assures that all directories are connected to the
12 * filesystem tree, using the following algorithm:
14 * First, the root directory is checked to make sure it exists; if
15 * not, e2fsck will offer to create a new one. It is then marked as
18 * Then, pass3 interates over all directory inodes; for each directory
19 * it attempts to trace up the filesystem tree, using dirinfo.parent
20 * until it reaches a directory which has been marked "done". If it
21 * can not do so, then the directory must be disconnected, and e2fsck
22 * will offer to reconnect it to /lost+found. While it is chasing
23 * parent pointers up the filesystem tree, if pass3 sees a directory
24 * twice, then it has detected a filesystem loop, and it will again
25 * offer to reconnect the directory to /lost+found in to break the
28 * Pass 3 also contains the subroutine, reconnect_file() to reconnect
29 * inodes to /lost+found; this subroutine is also used by pass 4.
30 * reconnect_file() calls get_lost_and_found(), which is responsible
31 * for creating /lost+found if it does not exist.
33 * Pass 3 frees the following data structures:
34 * - The dirinfo directory information cache.
44 static void check_root(e2fsck_t ctx
);
45 static void check_directory(e2fsck_t ctx
, struct dir_info
*dir
,
46 struct problem_context
*pctx
);
47 static ino_t
get_lost_and_found(e2fsck_t ctx
);
48 static void fix_dotdot(e2fsck_t ctx
, struct dir_info
*dir
, ino_t parent
);
49 static errcode_t
adjust_inode_count(e2fsck_t ctx
, ino_t ino
, int adj
);
50 static errcode_t
expand_directory(e2fsck_t ctx
, ino_t dir
);
52 static ino_t lost_and_found
= 0;
53 static int bad_lost_and_found
= 0;
55 static ext2fs_inode_bitmap inode_loop_detect
;
56 static ext2fs_inode_bitmap inode_done_map
;
58 void pass3(e2fsck_t ctx
)
60 ext2_filsys fs
= ctx
->fs
;
62 struct resource_track rtrack
;
63 struct problem_context pctx
;
66 init_resource_track(&rtrack
);
68 clear_problem_context(&pctx
);
71 mtrace_print("Pass 3");
74 if (!(ctx
->options
& E2F_OPT_PREEN
))
75 fix_problem(ctx
, PR_3_PASS_HEADER
, &pctx
);
78 * Allocate some bitmaps to do loop detection.
80 pctx
.errcode
= ext2fs_allocate_inode_bitmap(fs
,
81 "inode loop detection bitmap", &inode_loop_detect
);
84 fix_problem(ctx
, PR_3_ALLOCATE_IBITMAP_ERROR
, &pctx
);
87 pctx
.errcode
= ext2fs_allocate_inode_bitmap(fs
, "inode done bitmap",
91 fix_problem(ctx
, PR_3_ALLOCATE_IBITMAP_ERROR
, &pctx
);
94 if (ctx
->options
& E2F_OPT_TIME
)
95 print_resource_track("Peak memory", &ctx
->global_rtrack
);
98 ext2fs_mark_inode_bitmap(inode_done_map
, EXT2_ROOT_INO
);
100 for (i
=0; (dir
= dir_info_iter(&i
)) != 0;) {
101 if (ext2fs_test_inode_bitmap(ctx
->inode_dir_map
, dir
->ino
))
102 check_directory(ctx
, dir
, &pctx
);
107 ext2fs_free_inode_bitmap(inode_loop_detect
);
108 ext2fs_free_inode_bitmap(inode_done_map
);
109 if (ctx
->options
& E2F_OPT_TIME2
)
110 print_resource_track("Pass 3", &rtrack
);
114 * This makes sure the root inode is present; if not, we ask if the
115 * user wants us to create it. Not creating it is a fatal error.
117 static void check_root(e2fsck_t ctx
)
119 ext2_filsys fs
= ctx
->fs
;
121 struct ext2_inode inode
;
123 struct problem_context pctx
;
125 clear_problem_context(&pctx
);
127 if (ext2fs_test_inode_bitmap(ctx
->inode_used_map
, EXT2_ROOT_INO
)) {
129 * If the root inode is a directory, die here. The
130 * user must have answered 'no' in pass1 when we
131 * offered to clear it.
133 if (!(ext2fs_test_inode_bitmap(ctx
->inode_dir_map
,
135 fatal_error("Root inode not directory");
139 if (!fix_problem(ctx
, PR_3_NO_ROOT_INODE
, &pctx
))
140 fatal_error("Cannot proceed without a root inode.");
145 * First, find a free block
147 pctx
.errcode
= ext2fs_new_block(fs
, 0, ctx
->block_found_map
, &blk
);
149 pctx
.str
= "ext2fs_new_block";
150 fix_problem(ctx
, PR_3_CREATE_ROOT_ERROR
, &pctx
);
153 ext2fs_mark_block_bitmap(ctx
->block_found_map
, blk
);
154 ext2fs_mark_block_bitmap(fs
->block_map
, blk
);
155 ext2fs_mark_bb_dirty(fs
);
158 * Now let's create the actual data block for the inode
160 pctx
.errcode
= ext2fs_new_dir_block(fs
, EXT2_ROOT_INO
, EXT2_ROOT_INO
,
163 pctx
.str
= "ext2fs_new_dir_block";
164 fix_problem(ctx
, PR_3_CREATE_ROOT_ERROR
, &pctx
);
168 pctx
.errcode
= ext2fs_write_dir_block(fs
, blk
, block
);
170 pctx
.str
= "ext2fs_write_dir_block";
171 fix_problem(ctx
, PR_3_CREATE_ROOT_ERROR
, &pctx
);
177 * Set up the inode structure
179 memset(&inode
, 0, sizeof(inode
));
180 inode
.i_mode
= 040755;
181 inode
.i_size
= fs
->blocksize
;
182 inode
.i_atime
= inode
.i_ctime
= inode
.i_mtime
= time(0);
183 inode
.i_links_count
= 2;
184 inode
.i_blocks
= fs
->blocksize
/ 512;
185 inode
.i_block
[0] = blk
;
188 * Write out the inode.
190 pctx
.errcode
= ext2fs_write_inode(fs
, EXT2_ROOT_INO
, &inode
);
192 pctx
.str
= "ext2fs_write_inode";
193 fix_problem(ctx
, PR_3_CREATE_ROOT_ERROR
, &pctx
);
198 * Miscellaneous bookkeeping...
200 add_dir_info(fs
, EXT2_ROOT_INO
, EXT2_ROOT_INO
);
201 ext2fs_icount_store(ctx
->inode_count
, EXT2_ROOT_INO
, 2);
202 ext2fs_icount_store(ctx
->inode_link_info
, EXT2_ROOT_INO
, 2);
204 ext2fs_mark_inode_bitmap(ctx
->inode_used_map
, EXT2_ROOT_INO
);
205 ext2fs_mark_inode_bitmap(ctx
->inode_dir_map
, EXT2_ROOT_INO
);
206 ext2fs_mark_inode_bitmap(fs
->inode_map
, EXT2_ROOT_INO
);
207 ext2fs_mark_ib_dirty(fs
);
211 * This subroutine is responsible for making sure that a particular
212 * directory is connected to the root; if it isn't we trace it up as
213 * far as we can go, and then offer to connect the resulting parent to
214 * the lost+found. We have to do loop detection; if we ever discover
215 * a loop, we treat that as a disconnected directory and offer to
216 * reparent it to lost+found.
218 static void check_directory(e2fsck_t ctx
, struct dir_info
*dir
,
219 struct problem_context
*pctx
)
221 ext2_filsys fs
= ctx
->fs
;
222 struct dir_info
*p
= dir
;
224 ext2fs_clear_inode_bitmap(inode_loop_detect
);
227 * If we find a parent which we've already checked,
228 * then stop; we know it's either already connected to
229 * the directory tree, or it isn't but the user has
230 * already told us he doesn't want us to reconnect the
231 * disconnected subtree.
233 if (ext2fs_test_inode_bitmap(inode_done_map
, p
->ino
))
236 * Mark this inode as being "done"; by the time we
237 * return from this function, the inode we either be
238 * verified as being connected to the directory tree,
239 * or we will have offered to reconnect this to
242 ext2fs_mark_inode_bitmap(inode_done_map
, p
->ino
);
244 * If this directory doesn't have a parent, or we've
245 * seen the parent once already, then offer to
246 * reparent it to lost+found
249 (ext2fs_test_inode_bitmap(inode_loop_detect
,
252 ext2fs_mark_inode_bitmap(inode_loop_detect
,
254 p
= get_dir_info(p
->parent
);
257 * If we've reached here, we've hit a detached directory
258 * inode; offer to reconnect it to lost+found.
261 if (fix_problem(ctx
, PR_3_UNCONNECTED_DIR
, pctx
)) {
262 if (reconnect_file(ctx
, p
->ino
))
263 ext2fs_unmark_valid(fs
);
265 p
->parent
= lost_and_found
;
266 fix_dotdot(ctx
, p
, lost_and_found
);
271 * Make sure that .. and the parent directory are the same;
272 * offer to fix it if not.
275 if (dir
->parent
!= dir
->dotdot
) {
276 pctx
->ino
= dir
->ino
;
277 pctx
->ino2
= dir
->dotdot
;
278 pctx
->dir
= dir
->parent
;
279 if (fix_problem(ctx
, PR_3_BAD_DOT_DOT
, pctx
))
280 fix_dotdot(ctx
, dir
, dir
->parent
);
285 * This routine gets the lost_and_found inode, making it a directory
288 ino_t
get_lost_and_found(e2fsck_t ctx
)
290 ext2_filsys fs
= ctx
->fs
;
294 struct ext2_inode inode
;
296 const char name
[] = "lost+found";
297 struct problem_context pctx
;
299 clear_problem_context(&pctx
);
301 retval
= ext2fs_lookup(fs
, EXT2_ROOT_INO
, name
,
302 sizeof(name
)-1, 0, &ino
);
305 if (retval
!= ENOENT
) {
306 pctx
.errcode
= retval
;
307 fix_problem(ctx
, PR_3_ERR_FIND_LPF
, &pctx
);
309 if (!fix_problem(ctx
, PR_3_NO_LF_DIR
, 0))
313 * Read the inode and block bitmaps in; we'll be messing with
319 * First, find a free block
321 retval
= ext2fs_new_block(fs
, 0, ctx
->block_found_map
, &blk
);
323 pctx
.errcode
= retval
;
324 fix_problem(ctx
, PR_3_ERR_LPF_NEW_BLOCK
, &pctx
);
327 ext2fs_mark_block_bitmap(ctx
->block_found_map
, blk
);
328 ext2fs_mark_block_bitmap(fs
->block_map
, blk
);
329 ext2fs_mark_bb_dirty(fs
);
332 * Next find a free inode.
334 retval
= ext2fs_new_inode(fs
, EXT2_ROOT_INO
, 040755,
335 ctx
->inode_used_map
, &ino
);
337 pctx
.errcode
= retval
;
338 fix_problem(ctx
, PR_3_ERR_LPF_NEW_INODE
, &pctx
);
341 ext2fs_mark_inode_bitmap(ctx
->inode_used_map
, ino
);
342 ext2fs_mark_inode_bitmap(ctx
->inode_dir_map
, ino
);
343 ext2fs_mark_inode_bitmap(fs
->inode_map
, ino
);
344 ext2fs_mark_ib_dirty(fs
);
347 * Now let's create the actual data block for the inode
349 retval
= ext2fs_new_dir_block(fs
, ino
, EXT2_ROOT_INO
, &block
);
351 pctx
.errcode
= retval
;
352 fix_problem(ctx
, PR_3_ERR_LPF_NEW_DIR_BLOCK
, &pctx
);
356 retval
= ext2fs_write_dir_block(fs
, blk
, block
);
359 pctx
.errcode
= retval
;
360 fix_problem(ctx
, PR_3_ERR_LPF_WRITE_BLOCK
, &pctx
);
365 * Set up the inode structure
367 memset(&inode
, 0, sizeof(inode
));
368 inode
.i_mode
= 040755;
369 inode
.i_size
= fs
->blocksize
;
370 inode
.i_atime
= inode
.i_ctime
= inode
.i_mtime
= time(0);
371 inode
.i_links_count
= 2;
372 inode
.i_blocks
= fs
->blocksize
/ 512;
373 inode
.i_block
[0] = blk
;
376 * Next, write out the inode.
378 pctx
.errcode
= ext2fs_write_inode(fs
, ino
, &inode
);
380 pctx
.str
= "ext2fs_write_inode";
381 fix_problem(ctx
, PR_3_CREATE_LPF_ERROR
, &pctx
);
385 * Finally, create the directory link
387 pctx
.errcode
= ext2fs_link(fs
, EXT2_ROOT_INO
, name
, ino
, 0);
389 pctx
.str
= "ext2fs_link";
390 fix_problem(ctx
, PR_3_CREATE_LPF_ERROR
, &pctx
);
395 * Miscellaneous bookkeeping that needs to be kept straight.
397 add_dir_info(fs
, ino
, EXT2_ROOT_INO
);
398 adjust_inode_count(ctx
, EXT2_ROOT_INO
, +1);
399 ext2fs_icount_store(ctx
->inode_count
, ino
, 2);
400 ext2fs_icount_store(ctx
->inode_link_info
, ino
, 2);
402 printf("/lost+found created; inode #%lu\n", ino
);
408 * This routine will connect a file to lost+found
410 int reconnect_file(e2fsck_t ctx
, ino_t inode
)
412 ext2_filsys fs
= ctx
->fs
;
415 struct problem_context pctx
;
417 clear_problem_context(&pctx
);
420 if (!bad_lost_and_found
&& !lost_and_found
) {
421 lost_and_found
= get_lost_and_found(ctx
);
423 bad_lost_and_found
++;
425 if (bad_lost_and_found
) {
426 fix_problem(ctx
, PR_3_NO_LPF
, &pctx
);
430 sprintf(name
, "#%lu", inode
);
431 retval
= ext2fs_link(fs
, lost_and_found
, name
, inode
, 0);
432 if (retval
== EXT2_ET_DIR_NO_SPACE
) {
433 if (!fix_problem(ctx
, PR_3_EXPAND_LF_DIR
, &pctx
))
435 retval
= expand_directory(ctx
, lost_and_found
);
437 pctx
.errcode
= retval
;
438 fix_problem(ctx
, PR_3_CANT_EXPAND_LPF
, &pctx
);
441 retval
= ext2fs_link(fs
, lost_and_found
, name
, inode
, 0);
444 pctx
.errcode
= retval
;
445 fix_problem(ctx
, PR_3_CANT_RECONNECT
, &pctx
);
448 adjust_inode_count(ctx
, inode
, +1);
454 * Utility routine to adjust the inode counts on an inode.
456 static errcode_t
adjust_inode_count(e2fsck_t ctx
, ino_t ino
, int adj
)
458 ext2_filsys fs
= ctx
->fs
;
460 struct ext2_inode inode
;
465 retval
= ext2fs_read_inode(fs
, ino
, &inode
);
470 printf("Adjusting link count for inode %lu by %d (from %d)\n", ino
, adj
,
471 inode
.i_links_count
);
474 inode
.i_links_count
+= adj
;
476 ext2fs_icount_increment(ctx
->inode_count
, ino
, 0);
477 ext2fs_icount_increment(ctx
->inode_link_info
, ino
, 0);
479 ext2fs_icount_decrement(ctx
->inode_count
, ino
, 0);
480 ext2fs_icount_decrement(ctx
->inode_link_info
, ino
, 0);
484 retval
= ext2fs_write_inode(fs
, ino
, &inode
);
492 * Fix parent --- this routine fixes up the parent of a directory.
494 struct fix_dotdot_struct
{
501 static int fix_dotdot_proc(struct ext2_dir_entry
*dirent
,
507 struct fix_dotdot_struct
*fp
= (struct fix_dotdot_struct
*) private;
509 struct problem_context pctx
;
511 if (dirent
->name_len
!= 2)
513 if (strncmp(dirent
->name
, "..", 2))
516 clear_problem_context(&pctx
);
518 retval
= adjust_inode_count(fp
->ctx
, dirent
->inode
, -1);
520 pctx
.errcode
= retval
;
521 fix_problem(fp
->ctx
, PR_3_ADJUST_INODE
, &pctx
);
523 retval
= adjust_inode_count(fp
->ctx
, fp
->parent
, 1);
525 pctx
.errcode
= retval
;
526 fix_problem(fp
->ctx
, PR_3_ADJUST_INODE
, &pctx
);
528 dirent
->inode
= fp
->parent
;
531 return DIRENT_ABORT
| DIRENT_CHANGED
;
534 static void fix_dotdot(e2fsck_t ctx
, struct dir_info
*dir
, ino_t parent
)
536 ext2_filsys fs
= ctx
->fs
;
538 struct fix_dotdot_struct fp
;
539 struct problem_context pctx
;
547 printf("Fixing '..' of inode %lu to be %lu...\n", dir
->ino
, parent
);
550 retval
= ext2fs_dir_iterate(fs
, dir
->ino
, DIRENT_FLAG_INCLUDE_EMPTY
,
551 0, fix_dotdot_proc
, &fp
);
552 if (retval
|| !fp
.done
) {
553 clear_problem_context(&pctx
);
555 pctx
.errcode
= retval
;
556 fix_problem(ctx
, retval
? PR_3_FIX_PARENT_ERR
:
557 PR_3_FIX_PARENT_NOFIND
, &pctx
);
558 ext2fs_unmark_valid(fs
);
560 dir
->dotdot
= parent
;
566 * These routines are responsible for expanding a /lost+found if it is
570 struct expand_dir_struct
{
576 static int expand_dir_proc(ext2_filsys fs
,
581 struct expand_dir_struct
*es
= (struct expand_dir_struct
*) private;
583 static blk_t last_blk
= 0;
594 retval
= ext2fs_new_block(fs
, last_blk
, ctx
->block_found_map
,
601 retval
= ext2fs_new_dir_block(fs
, 0, 0, &block
);
608 block
= malloc(fs
->blocksize
);
613 memset(block
, 0, fs
->blocksize
);
615 retval
= ext2fs_write_dir_block(fs
, new_blk
, block
);
622 ext2fs_mark_block_bitmap(ctx
->block_found_map
, new_blk
);
623 ext2fs_mark_block_bitmap(fs
->block_map
, new_blk
);
624 ext2fs_mark_bb_dirty(fs
);
626 return (BLOCK_CHANGED
| BLOCK_ABORT
);
628 return BLOCK_CHANGED
;
631 static errcode_t
expand_directory(e2fsck_t ctx
, ino_t dir
)
633 ext2_filsys fs
= ctx
->fs
;
635 struct expand_dir_struct es
;
636 struct ext2_inode inode
;
638 if (!(fs
->flags
& EXT2_FLAG_RW
))
639 return EXT2_ET_RO_FILSYS
;
641 retval
= ext2fs_check_directory(fs
, dir
);
649 retval
= ext2fs_block_iterate(fs
, dir
, BLOCK_FLAG_APPEND
,
650 0, expand_dir_proc
, &es
);
655 return EXT2_ET_EXPAND_DIR_ERR
;
658 * Update the size and block count fields in the inode.
660 retval
= ext2fs_read_inode(fs
, dir
, &inode
);
664 inode
.i_size
+= fs
->blocksize
;
665 inode
.i_blocks
+= fs
->blocksize
/ 512;
667 e2fsck_write_inode(fs
, dir
, &inode
, "expand_directory");