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.
40 #include "et/com_err.h"
45 static void check_root(ext2_filsys fs);
46 static void check_directory(ext2_filsys fs, struct dir_info *dir,
47 struct problem_context *pctx);
48 static ino_t get_lost_and_found(ext2_filsys fs);
49 static void fix_dotdot(ext2_filsys fs, struct dir_info *dir, ino_t parent);
50 static errcode_t adjust_inode_count(ext2_filsys fs, ino_t ino, int adj);
51 static errcode_t expand_directory(ext2_filsys fs, ino_t dir);
53 static ino_t lost_and_found = 0;
54 static int bad_lost_and_found = 0;
56 static ext2fs_inode_bitmap inode_loop_detect;
57 static ext2fs_inode_bitmap inode_done_map;
59 void pass3(ext2_filsys fs)
63 struct resource_track rtrack;
64 struct problem_context pctx;
67 init_resource_track(&rtrack);
70 mtrace_print("Pass 3");
74 printf("Pass 3: Checking directory connectivity\n");
77 * Allocate some bitmaps to do loop detection.
79 retval = ext2fs_allocate_inode_bitmap(fs,
80 "inode loop detection bitmap",
83 com_err("ext2fs_allocate_inode_bitmap", retval,
84 "while allocating inode_loop_detect");
87 retval = ext2fs_allocate_inode_bitmap(fs, "inode done bitmap",
90 com_err("ext2fs_allocate_inode_bitmap", retval,
91 "while allocating inode_done_map");
95 printf("Peak memory: ");
96 print_resource_track(&global_rtrack);
100 ext2fs_mark_inode_bitmap(inode_done_map, EXT2_ROOT_INO);
102 clear_problem_context(&pctx);
103 for (i=0; (dir = dir_info_iter(&i)) != 0;) {
104 if (ext2fs_test_inode_bitmap(inode_dir_map, dir->ino))
105 check_directory(fs, dir, &pctx);
110 ext2fs_free_inode_bitmap(inode_loop_detect);
111 ext2fs_free_inode_bitmap(inode_done_map);
114 print_resource_track(&rtrack);
119 * This makes sure the root inode is present; if not, we ask if the
120 * user wants us to create it. Not creating it is a fatal error.
122 static void check_root(ext2_filsys fs)
126 struct ext2_inode inode;
129 if (ext2fs_test_inode_bitmap(inode_used_map, EXT2_ROOT_INO)) {
131 * If the root inode is a directory, die here. The
132 * user must have answered 'no' in pass1 when we
133 * offered to clear it.
135 if (!(ext2fs_test_inode_bitmap(inode_dir_map, EXT2_ROOT_INO)))
136 fatal_error("Root inode not directory");
140 if (!fix_problem(fs, PR_3_NO_ROOT_INODE, 0))
141 fatal_error("Cannot proceed without a root inode.");
146 * First, find a free block
148 retval = ext2fs_new_block(fs, 0, block_found_map, &blk);
150 com_err("ext2fs_new_block", retval,
151 "while trying to create root directory");
154 ext2fs_mark_block_bitmap(block_found_map, blk);
155 ext2fs_mark_block_bitmap(fs->block_map, blk);
156 ext2fs_mark_bb_dirty(fs);
159 * Now let's create the actual data block for the inode
161 retval = ext2fs_new_dir_block(fs, EXT2_ROOT_INO, EXT2_ROOT_INO,
164 com_err("ext2fs_new_dir_block", retval,
165 "while creating new root directory");
169 retval = ext2fs_write_dir_block(fs, blk, block);
171 com_err("ext2fs_write_dir_block", retval,
172 "while writing the root directory block");
178 * Set up the inode structure
180 memset(&inode, 0, sizeof(inode));
181 inode.i_mode = 040755;
182 inode.i_size = fs->blocksize;
183 inode.i_atime = inode.i_ctime = inode.i_mtime = time(0);
184 inode.i_links_count = 2;
185 inode.i_blocks = fs->blocksize / 512;
186 inode.i_block[0] = blk;
189 * Write out the inode.
191 retval = ext2fs_write_inode(fs, EXT2_ROOT_INO, &inode);
193 com_err("ext2fs_write_inode", retval,
194 "While trying to create /lost+found");
199 * Miscellaneous bookkeeping...
201 add_dir_info(fs, EXT2_ROOT_INO, EXT2_ROOT_INO);
202 ext2fs_icount_store(inode_count, EXT2_ROOT_INO, 2);
203 ext2fs_icount_store(inode_link_info, EXT2_ROOT_INO, 2);
205 ext2fs_mark_inode_bitmap(inode_used_map, EXT2_ROOT_INO);
206 ext2fs_mark_inode_bitmap(inode_dir_map, EXT2_ROOT_INO);
207 ext2fs_mark_inode_bitmap(fs->inode_map, EXT2_ROOT_INO);
208 ext2fs_mark_ib_dirty(fs);
212 * This subroutine is responsible for making sure that a particular
213 * directory is connected to the root; if it isn't we trace it up as
214 * far as we can go, and then offer to connect the resulting parent to
215 * the lost+found. We have to do loop detection; if we ever discover
216 * a loop, we treat that as a disconnected directory and offer to
217 * reparent it to lost+found.
219 static void check_directory(ext2_filsys fs, struct dir_info *dir,
220 struct problem_context *pctx)
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(fs, PR_3_UNCONNECTED_DIR, pctx)) {
262 if (reconnect_file(fs, p->ino))
263 ext2fs_unmark_valid(fs);
265 p->parent = lost_and_found;
266 fix_dotdot(fs, 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(fs, PR_3_BAD_DOT_DOT, pctx))
280 fix_dotdot(fs, dir, dir->parent);
285 * This routine gets the lost_and_found inode, making it a directory
288 ino_t get_lost_and_found(ext2_filsys fs)
293 struct ext2_inode inode;
295 const char name[] = "lost+found";
297 retval = ext2fs_lookup(fs, EXT2_ROOT_INO, name,
298 sizeof(name)-1, 0, &ino);
301 if (retval != ENOENT)
302 printf("Error while trying to find /lost+found: %s",
303 error_message(retval));
304 if (!fix_problem(fs, PR_3_NO_LF_DIR, 0))
308 * Read the inode and block bitmaps in; we'll be messing with
314 * First, find a free block
316 retval = ext2fs_new_block(fs, 0, block_found_map, &blk);
318 com_err("ext2fs_new_block", retval,
319 "while trying to create /lost+found directory");
322 ext2fs_mark_block_bitmap(block_found_map, blk);
323 ext2fs_mark_block_bitmap(fs->block_map, blk);
324 ext2fs_mark_bb_dirty(fs);
327 * Next find a free inode.
329 retval = ext2fs_new_inode(fs, EXT2_ROOT_INO, 040755, inode_used_map,
332 com_err("ext2fs_new_inode", retval,
333 "while trying to create /lost+found directory");
336 ext2fs_mark_inode_bitmap(inode_used_map, ino);
337 ext2fs_mark_inode_bitmap(inode_dir_map, ino);
338 ext2fs_mark_inode_bitmap(fs->inode_map, ino);
339 ext2fs_mark_ib_dirty(fs);
342 * Now let's create the actual data block for the inode
344 retval = ext2fs_new_dir_block(fs, ino, EXT2_ROOT_INO, &block);
346 com_err("ext2fs_new_dir_block", retval,
347 "while creating new directory block");
351 retval = ext2fs_write_dir_block(fs, blk, block);
354 com_err("ext2fs_write_dir_block", retval,
355 "while writing the directory block for /lost+found");
360 * Set up the inode structure
362 memset(&inode, 0, sizeof(inode));
363 inode.i_mode = 040755;
364 inode.i_size = fs->blocksize;
365 inode.i_atime = inode.i_ctime = inode.i_mtime = time(0);
366 inode.i_links_count = 2;
367 inode.i_blocks = fs->blocksize / 512;
368 inode.i_block[0] = blk;
371 * Next, write out the inode.
373 retval = ext2fs_write_inode(fs, ino, &inode);
375 com_err("ext2fs_write_inode", retval,
376 "While trying to create /lost+found");
380 * Finally, create the directory link
382 retval = ext2fs_link(fs, EXT2_ROOT_INO, name, ino, 0);
384 com_err("ext2fs_link", retval, "While creating /lost+found");
389 * Miscellaneous bookkeeping that needs to be kept straight.
391 add_dir_info(fs, ino, EXT2_ROOT_INO);
392 adjust_inode_count(fs, EXT2_ROOT_INO, +1);
393 ext2fs_icount_store(inode_count, ino, 2);
394 ext2fs_icount_store(inode_link_info, ino, 2);
396 printf("/lost+found created; inode #%lu\n", ino);
402 * This routine will connect a file to lost+found
404 int reconnect_file(ext2_filsys fs, ino_t inode)
409 if (bad_lost_and_found) {
410 printf("Bad or nonexistent /lost+found. Cannot reconnect.\n");
413 if (!lost_and_found) {
414 lost_and_found = get_lost_and_found(fs);
415 if (!lost_and_found) {
416 printf("Bad or nonexistent /lost+found. Cannot reconnect.\n");
417 bad_lost_and_found++;
422 sprintf(name, "#%lu", inode);
423 retval = ext2fs_link(fs, lost_and_found, name, inode, 0);
424 if (retval == EXT2_ET_DIR_NO_SPACE) {
425 if (!fix_problem(fs, PR_3_EXPAND_LF_DIR, 0))
427 retval = expand_directory(fs, lost_and_found);
429 printf("Could not expand /lost+found: %s\n",
430 error_message(retval));
433 retval = ext2fs_link(fs, lost_and_found, name, inode, 0);
436 printf("Could not reconnect %lu: %s\n", inode,
437 error_message(retval));
441 adjust_inode_count(fs, inode, +1);
447 * Utility routine to adjust the inode counts on an inode.
449 static errcode_t adjust_inode_count(ext2_filsys fs, ino_t ino, int adj)
452 struct ext2_inode inode;
457 retval = ext2fs_read_inode(fs, ino, &inode);
462 printf("Adjusting link count for inode %lu by %d (from %d)\n", ino, adj,
463 inode.i_links_count);
466 inode.i_links_count += adj;
468 ext2fs_icount_increment(inode_count, ino, 0);
469 ext2fs_icount_increment(inode_link_info, ino, 0);
471 ext2fs_icount_decrement(inode_count, ino, 0);
472 ext2fs_icount_decrement(inode_link_info, ino, 0);
476 retval = ext2fs_write_inode(fs, ino, &inode);
484 * Fix parent --- this routine fixes up the parent of a directory.
486 struct fix_dotdot_struct {
492 static int fix_dotdot_proc(struct ext2_dir_entry *dirent,
498 struct fix_dotdot_struct *fp = (struct fix_dotdot_struct *) private;
501 if (dirent->name_len != 2)
503 if (strncmp(dirent->name, "..", 2))
506 retval = adjust_inode_count(fp->fs, dirent->inode, -1);
508 printf("Error while adjusting inode count on inode %u\n",
510 retval = adjust_inode_count(fp->fs, fp->parent, 1);
512 printf("Error while adjusting inode count on inode %lu\n",
515 dirent->inode = fp->parent;
518 return DIRENT_ABORT | DIRENT_CHANGED;
521 static void fix_dotdot(ext2_filsys fs, struct dir_info *dir, ino_t parent)
524 struct fix_dotdot_struct fp;
531 printf("Fixing '..' of inode %lu to be %lu...\n", dir->ino, parent);
534 retval = ext2fs_dir_iterate(fs, dir->ino, DIRENT_FLAG_INCLUDE_EMPTY,
535 0, fix_dotdot_proc, &fp);
536 if (retval || !fp.done) {
537 printf("Couldn't fix parent of inode %lu: %s\n\n",
538 dir->ino, retval ? error_message(retval) :
539 "Couldn't find parent direntory entry");
540 ext2fs_unmark_valid(fs);
542 dir->dotdot = parent;
548 * These routines are responsible for expanding a /lost+found if it is
552 struct expand_dir_struct {
557 static int expand_dir_proc(ext2_filsys fs,
562 struct expand_dir_struct *es = (struct expand_dir_struct *) private;
564 static blk_t last_blk = 0;
572 retval = ext2fs_new_block(fs, last_blk, block_found_map, &new_blk);
578 retval = ext2fs_new_dir_block(fs, 0, 0, &block);
585 block = malloc(fs->blocksize);
590 memset(block, 0, fs->blocksize);
592 retval = ext2fs_write_dir_block(fs, new_blk, block);
599 ext2fs_mark_block_bitmap(block_found_map, new_blk);
600 ext2fs_mark_block_bitmap(fs->block_map, new_blk);
601 ext2fs_mark_bb_dirty(fs);
603 return (BLOCK_CHANGED | BLOCK_ABORT);
605 return BLOCK_CHANGED;
608 static errcode_t expand_directory(ext2_filsys fs, ino_t dir)
611 struct expand_dir_struct es;
612 struct ext2_inode inode;
614 if (!(fs->flags & EXT2_FLAG_RW))
615 return EXT2_ET_RO_FILSYS;
617 retval = ext2fs_check_directory(fs, dir);
624 retval = ext2fs_block_iterate(fs, dir, BLOCK_FLAG_APPEND,
625 0, expand_dir_proc, &es);
630 return EXT2_ET_EXPAND_DIR_ERR;
633 * Update the size and block count fields in the inode.
635 retval = ext2fs_read_inode(fs, dir, &inode);
639 inode.i_size += fs->blocksize;
640 inode.i_blocks += fs->blocksize / 512;
642 e2fsck_write_inode(fs, dir, &inode, "expand_directory");