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, e2fsck_reconnect_file() to
29 * reconnect inodes to /lost+found; this subroutine is also used by
30 * pass 4. e2fsck_reconnect_file() calls get_lost_and_found(), which
31 * is responsible 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 e2fsck_pass3(e2fsck_t ctx)
60 ext2_filsys fs = ctx->fs;
63 struct resource_track rtrack;
65 struct problem_context pctx;
67 unsigned long max, count;
70 init_resource_track(&rtrack);
73 clear_problem_context(&pctx);
76 mtrace_print("Pass 3");
79 if (!(ctx->options & E2F_OPT_PREEN))
80 fix_problem(ctx, PR_3_PASS_HEADER, &pctx);
83 * Allocate some bitmaps to do loop detection.
85 pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
86 "inode loop detection bitmap", &inode_loop_detect);
89 fix_problem(ctx, PR_3_ALLOCATE_IBITMAP_ERROR, &pctx);
90 ctx->flags |= E2F_FLAG_ABORT;
93 pctx.errcode = ext2fs_allocate_inode_bitmap(fs, "inode done bitmap",
97 fix_problem(ctx, PR_3_ALLOCATE_IBITMAP_ERROR, &pctx);
98 ctx->flags |= E2F_FLAG_ABORT;
101 #ifdef RESOURCE_TRACK
102 if (ctx->options & E2F_OPT_TIME)
103 print_resource_track("Peak memory", &ctx->global_rtrack);
107 if (ctx->flags & E2F_FLAG_ABORT)
110 ext2fs_mark_inode_bitmap(inode_done_map, EXT2_ROOT_INO);
112 max = e2fsck_get_num_dirinfo(ctx);
116 (ctx->progress)(ctx, 3, 0, max);
117 for (i=0; (dir = e2fsck_dir_info_iter(ctx, &i)) != 0;) {
119 (ctx->progress)(ctx, 3, count++, max);
120 if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, dir->ino))
121 check_directory(ctx, dir, &pctx);
124 (ctx->progress)(ctx, 3, max, max);
126 e2fsck_free_dir_info(ctx);
127 ext2fs_free_inode_bitmap(inode_loop_detect);
128 ext2fs_free_inode_bitmap(inode_done_map);
129 #ifdef RESOURCE_TRACK
130 if (ctx->options & E2F_OPT_TIME2)
131 print_resource_track("Pass 3", &rtrack);
136 * This makes sure the root inode is present; if not, we ask if the
137 * user wants us to create it. Not creating it is a fatal error.
139 static void check_root(e2fsck_t ctx)
141 ext2_filsys fs = ctx->fs;
143 struct ext2_inode inode;
145 struct problem_context pctx;
147 clear_problem_context(&pctx);
149 if (ext2fs_test_inode_bitmap(ctx->inode_used_map, EXT2_ROOT_INO)) {
151 * If the root inode is not a directory, die here. The
152 * user must have answered 'no' in pass1 when we
153 * offered to clear it.
155 if (!(ext2fs_test_inode_bitmap(ctx->inode_dir_map,
157 fix_problem(ctx, PR_3_ROOT_NOT_DIR_ABORT, &pctx);
158 ctx->flags |= E2F_FLAG_ABORT;
163 if (!fix_problem(ctx, PR_3_NO_ROOT_INODE, &pctx)) {
164 fix_problem(ctx, PR_3_NO_ROOT_INODE_ABORT, &pctx);
165 ctx->flags |= E2F_FLAG_ABORT;
169 e2fsck_read_bitmaps(ctx);
172 * First, find a free block
174 pctx.errcode = ext2fs_new_block(fs, 0, ctx->block_found_map, &blk);
176 pctx.str = "ext2fs_new_block";
177 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx);
178 ctx->flags |= E2F_FLAG_ABORT;
181 ext2fs_mark_block_bitmap(ctx->block_found_map, blk);
182 ext2fs_mark_block_bitmap(fs->block_map, blk);
183 ext2fs_mark_bb_dirty(fs);
186 * Now let's create the actual data block for the inode
188 pctx.errcode = ext2fs_new_dir_block(fs, EXT2_ROOT_INO, EXT2_ROOT_INO,
191 pctx.str = "ext2fs_new_dir_block";
192 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx);
193 ctx->flags |= E2F_FLAG_ABORT;
197 pctx.errcode = ext2fs_write_dir_block(fs, blk, block);
199 pctx.str = "ext2fs_write_dir_block";
200 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx);
201 ctx->flags |= E2F_FLAG_ABORT;
204 ext2fs_free_mem((void **) &block);
207 * Set up the inode structure
209 memset(&inode, 0, sizeof(inode));
210 inode.i_mode = 040755;
211 inode.i_size = fs->blocksize;
212 inode.i_atime = inode.i_ctime = inode.i_mtime = time(0);
213 inode.i_links_count = 2;
214 inode.i_blocks = fs->blocksize / 512;
215 inode.i_block[0] = blk;
218 * Write out the inode.
220 pctx.errcode = ext2fs_write_inode(fs, EXT2_ROOT_INO, &inode);
222 pctx.str = "ext2fs_write_inode";
223 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx);
224 ctx->flags |= E2F_FLAG_ABORT;
229 * Miscellaneous bookkeeping...
231 e2fsck_add_dir_info(ctx, EXT2_ROOT_INO, EXT2_ROOT_INO);
232 ext2fs_icount_store(ctx->inode_count, EXT2_ROOT_INO, 2);
233 ext2fs_icount_store(ctx->inode_link_info, EXT2_ROOT_INO, 2);
235 ext2fs_mark_inode_bitmap(ctx->inode_used_map, EXT2_ROOT_INO);
236 ext2fs_mark_inode_bitmap(ctx->inode_dir_map, EXT2_ROOT_INO);
237 ext2fs_mark_inode_bitmap(fs->inode_map, EXT2_ROOT_INO);
238 ext2fs_mark_ib_dirty(fs);
242 * This subroutine is responsible for making sure that a particular
243 * directory is connected to the root; if it isn't we trace it up as
244 * far as we can go, and then offer to connect the resulting parent to
245 * the lost+found. We have to do loop detection; if we ever discover
246 * a loop, we treat that as a disconnected directory and offer to
247 * reparent it to lost+found.
249 static void check_directory(e2fsck_t ctx, struct dir_info *dir,
250 struct problem_context *pctx)
252 ext2_filsys fs = ctx->fs;
253 struct dir_info *p = dir;
255 ext2fs_clear_inode_bitmap(inode_loop_detect);
258 * If we find a parent which we've already checked,
259 * then stop; we know it's either already connected to
260 * the directory tree, or it isn't but the user has
261 * already told us he doesn't want us to reconnect the
262 * disconnected subtree.
264 if (ext2fs_test_inode_bitmap(inode_done_map, p->ino))
267 * Mark this inode as being "done"; by the time we
268 * return from this function, the inode we either be
269 * verified as being connected to the directory tree,
270 * or we will have offered to reconnect this to
273 ext2fs_mark_inode_bitmap(inode_done_map, p->ino);
275 * If this directory doesn't have a parent, or we've
276 * seen the parent once already, then offer to
277 * reparent it to lost+found
280 (ext2fs_test_inode_bitmap(inode_loop_detect,
283 ext2fs_mark_inode_bitmap(inode_loop_detect,
285 p = e2fsck_get_dir_info(ctx, p->parent);
288 * If we've reached here, we've hit a detached directory
289 * inode; offer to reconnect it to lost+found.
292 if (fix_problem(ctx, PR_3_UNCONNECTED_DIR, pctx)) {
293 if (e2fsck_reconnect_file(ctx, p->ino))
294 ext2fs_unmark_valid(fs);
296 p->parent = lost_and_found;
297 fix_dotdot(ctx, p, lost_and_found);
302 * Make sure that .. and the parent directory are the same;
303 * offer to fix it if not.
306 if (dir->parent != dir->dotdot) {
307 pctx->ino = dir->ino;
308 pctx->ino2 = dir->dotdot;
309 pctx->dir = dir->parent;
310 if (fix_problem(ctx, PR_3_BAD_DOT_DOT, pctx))
311 fix_dotdot(ctx, dir, dir->parent);
316 * This routine gets the lost_and_found inode, making it a directory
319 ino_t get_lost_and_found(e2fsck_t ctx)
321 ext2_filsys fs = ctx->fs;
325 struct ext2_inode inode;
327 const char name[] = "lost+found";
328 struct problem_context pctx;
330 clear_problem_context(&pctx);
332 retval = ext2fs_lookup(fs, EXT2_ROOT_INO, name,
333 sizeof(name)-1, 0, &ino);
336 if (retval != EXT2_ET_FILE_NOT_FOUND) {
337 pctx.errcode = retval;
338 fix_problem(ctx, PR_3_ERR_FIND_LPF, &pctx);
340 if (!fix_problem(ctx, PR_3_NO_LF_DIR, 0))
344 * Read the inode and block bitmaps in; we'll be messing with
347 e2fsck_read_bitmaps(ctx);
350 * First, find a free block
352 retval = ext2fs_new_block(fs, 0, ctx->block_found_map, &blk);
354 pctx.errcode = retval;
355 fix_problem(ctx, PR_3_ERR_LPF_NEW_BLOCK, &pctx);
358 ext2fs_mark_block_bitmap(ctx->block_found_map, blk);
359 ext2fs_mark_block_bitmap(fs->block_map, blk);
360 ext2fs_mark_bb_dirty(fs);
363 * Next find a free inode.
365 retval = ext2fs_new_inode(fs, EXT2_ROOT_INO, 040755,
366 ctx->inode_used_map, &ino);
368 pctx.errcode = retval;
369 fix_problem(ctx, PR_3_ERR_LPF_NEW_INODE, &pctx);
372 ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino);
373 ext2fs_mark_inode_bitmap(ctx->inode_dir_map, ino);
374 ext2fs_mark_inode_bitmap(fs->inode_map, ino);
375 ext2fs_mark_ib_dirty(fs);
378 * Now let's create the actual data block for the inode
380 retval = ext2fs_new_dir_block(fs, ino, EXT2_ROOT_INO, &block);
382 pctx.errcode = retval;
383 fix_problem(ctx, PR_3_ERR_LPF_NEW_DIR_BLOCK, &pctx);
387 retval = ext2fs_write_dir_block(fs, blk, block);
388 ext2fs_free_mem((void **) &block);
390 pctx.errcode = retval;
391 fix_problem(ctx, PR_3_ERR_LPF_WRITE_BLOCK, &pctx);
396 * Set up the inode structure
398 memset(&inode, 0, sizeof(inode));
399 inode.i_mode = 040755;
400 inode.i_size = fs->blocksize;
401 inode.i_atime = inode.i_ctime = inode.i_mtime = time(0);
402 inode.i_links_count = 2;
403 inode.i_blocks = fs->blocksize / 512;
404 inode.i_block[0] = blk;
407 * Next, write out the inode.
409 pctx.errcode = ext2fs_write_inode(fs, ino, &inode);
411 pctx.str = "ext2fs_write_inode";
412 fix_problem(ctx, PR_3_CREATE_LPF_ERROR, &pctx);
416 * Finally, create the directory link
418 pctx.errcode = ext2fs_link(fs, EXT2_ROOT_INO, name, ino, 0);
420 pctx.str = "ext2fs_link";
421 fix_problem(ctx, PR_3_CREATE_LPF_ERROR, &pctx);
426 * Miscellaneous bookkeeping that needs to be kept straight.
428 e2fsck_add_dir_info(ctx, ino, EXT2_ROOT_INO);
429 adjust_inode_count(ctx, EXT2_ROOT_INO, +1);
430 ext2fs_icount_store(ctx->inode_count, ino, 2);
431 ext2fs_icount_store(ctx->inode_link_info, ino, 2);
433 printf("/lost+found created; inode #%lu\n", ino);
439 * This routine will connect a file to lost+found
441 int e2fsck_reconnect_file(e2fsck_t ctx, ino_t inode)
443 ext2_filsys fs = ctx->fs;
446 struct problem_context pctx;
448 clear_problem_context(&pctx);
451 if (!bad_lost_and_found && !lost_and_found) {
452 lost_and_found = get_lost_and_found(ctx);
454 bad_lost_and_found++;
456 if (bad_lost_and_found) {
457 fix_problem(ctx, PR_3_NO_LPF, &pctx);
461 sprintf(name, "#%lu", inode);
462 retval = ext2fs_link(fs, lost_and_found, name, inode, 0);
463 if (retval == EXT2_ET_DIR_NO_SPACE) {
464 if (!fix_problem(ctx, PR_3_EXPAND_LF_DIR, &pctx))
466 retval = expand_directory(ctx, lost_and_found);
468 pctx.errcode = retval;
469 fix_problem(ctx, PR_3_CANT_EXPAND_LPF, &pctx);
472 retval = ext2fs_link(fs, lost_and_found, name, inode, 0);
475 pctx.errcode = retval;
476 fix_problem(ctx, PR_3_CANT_RECONNECT, &pctx);
479 adjust_inode_count(ctx, inode, +1);
485 * Utility routine to adjust the inode counts on an inode.
487 static errcode_t adjust_inode_count(e2fsck_t ctx, ino_t ino, int adj)
489 ext2_filsys fs = ctx->fs;
491 struct ext2_inode inode;
496 retval = ext2fs_read_inode(fs, ino, &inode);
501 printf("Adjusting link count for inode %lu by %d (from %d)\n", ino, adj,
502 inode.i_links_count);
505 inode.i_links_count += adj;
507 ext2fs_icount_increment(ctx->inode_count, ino, 0);
508 ext2fs_icount_increment(ctx->inode_link_info, ino, 0);
510 ext2fs_icount_decrement(ctx->inode_count, ino, 0);
511 ext2fs_icount_decrement(ctx->inode_link_info, ino, 0);
515 retval = ext2fs_write_inode(fs, ino, &inode);
523 * Fix parent --- this routine fixes up the parent of a directory.
525 struct fix_dotdot_struct {
532 static int fix_dotdot_proc(struct ext2_dir_entry *dirent,
538 struct fix_dotdot_struct *fp = (struct fix_dotdot_struct *) priv_data;
540 struct problem_context pctx;
542 if (dirent->name_len != 2)
544 if (strncmp(dirent->name, "..", 2))
547 clear_problem_context(&pctx);
549 retval = adjust_inode_count(fp->ctx, dirent->inode, -1);
551 pctx.errcode = retval;
552 fix_problem(fp->ctx, PR_3_ADJUST_INODE, &pctx);
554 retval = adjust_inode_count(fp->ctx, fp->parent, 1);
556 pctx.errcode = retval;
557 fix_problem(fp->ctx, PR_3_ADJUST_INODE, &pctx);
559 dirent->inode = fp->parent;
562 return DIRENT_ABORT | DIRENT_CHANGED;
565 static void fix_dotdot(e2fsck_t ctx, struct dir_info *dir, ino_t parent)
567 ext2_filsys fs = ctx->fs;
569 struct fix_dotdot_struct fp;
570 struct problem_context pctx;
578 printf("Fixing '..' of inode %lu to be %lu...\n", dir->ino, parent);
581 retval = ext2fs_dir_iterate(fs, dir->ino, DIRENT_FLAG_INCLUDE_EMPTY,
582 0, fix_dotdot_proc, &fp);
583 if (retval || !fp.done) {
584 clear_problem_context(&pctx);
586 pctx.errcode = retval;
587 fix_problem(ctx, retval ? PR_3_FIX_PARENT_ERR :
588 PR_3_FIX_PARENT_NOFIND, &pctx);
589 ext2fs_unmark_valid(fs);
591 dir->dotdot = parent;
597 * These routines are responsible for expanding a /lost+found if it is
601 struct expand_dir_struct {
607 static int expand_dir_proc(ext2_filsys fs,
612 struct expand_dir_struct *es = (struct expand_dir_struct *) priv_data;
614 static blk_t last_blk = 0;
625 retval = ext2fs_new_block(fs, last_blk, ctx->block_found_map,
632 retval = ext2fs_new_dir_block(fs, 0, 0, &block);
638 retval = ext2fs_write_dir_block(fs, new_blk, block);
640 retval = ext2fs_get_mem(fs->blocksize, (void **) &block);
645 memset(block, 0, fs->blocksize);
646 retval = io_channel_write_blk(fs->io, new_blk, 1, block);
652 ext2fs_free_mem((void **) &block);
654 ext2fs_mark_block_bitmap(ctx->block_found_map, new_blk);
655 ext2fs_mark_block_bitmap(fs->block_map, new_blk);
656 ext2fs_mark_bb_dirty(fs);
658 return (BLOCK_CHANGED | BLOCK_ABORT);
660 return BLOCK_CHANGED;
663 static errcode_t expand_directory(e2fsck_t ctx, ino_t dir)
665 ext2_filsys fs = ctx->fs;
667 struct expand_dir_struct es;
668 struct ext2_inode inode;
670 if (!(fs->flags & EXT2_FLAG_RW))
671 return EXT2_ET_RO_FILSYS;
674 * Read the inode and block bitmaps in; we'll be messing with
677 e2fsck_read_bitmaps(ctx);
679 retval = ext2fs_check_directory(fs, dir);
687 retval = ext2fs_block_iterate(fs, dir, BLOCK_FLAG_APPEND,
688 0, expand_dir_proc, &es);
693 return EXT2_ET_EXPAND_DIR_ERR;
696 * Update the size and block count fields in the inode.
698 retval = ext2fs_read_inode(fs, dir, &inode);
702 inode.i_size += fs->blocksize;
703 inode.i_blocks += fs->blocksize / 512;
705 e2fsck_write_inode(ctx, dir, &inode, "expand_directory");