2 * pass1b.c --- Pass #1b of e2fsck
4 * This file contains pass1B, pass1C, and pass1D of e2fsck. They are
5 * only invoked if pass 1 discovered blocks which are in use by more
8 * Pass1B scans the data blocks of all the inodes again, generating a
9 * complete list of duplicate blocks and which inodes have claimed
12 * Pass1C does a tree-traversal of the filesystem, to determine the
13 * parent directories of these inodes. This step is necessary so that
14 * e2fsck can print out the pathnames of affected inodes.
16 * Pass1D is a reconciliation pass. For each inode with duplicate
17 * blocks, the user is prompted if s/he would like to clone the file
18 * (so that the file gets a fresh copy of the duplicated blocks) or
19 * simply to delete the file.
21 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
24 * This file may be redistributed under the terms of the GNU Public
35 #include <et/com_err.h>
40 /* Define an extension to the ext2 library's block count information */
41 #define BLOCK_COUNT_EXTATTR (-5)
44 * This is structure is allocated for each time that a block is
45 * claimed by more than one file. So if a particular block is claimed
46 * by 3 files, then three copies of this structure will be allocated,
47 * one for each conflict.
49 * The linked list structure is as follows:
51 * dup_blk --> block #34 --> block #35 --> block #47
52 * inode #12 inode #14 inode #17
53 * num_bad = 3 num_bad = 2 num_bad = 2
56 * block #34 block #35 block #47
57 * inode #14 inode #15 inode #23
63 * The num_bad field indicates how many inodes are sharing a
64 * particular block, and is only stored in the first element of the
65 * linked list for a particular block. As the block conflicts are
66 * resolved, num_bad is decremented; when it reaches 1, then we no
67 * longer need to worry about that block.
70 blk_t block
; /* Block number */
71 ext2_ino_t ino
; /* Inode number */
74 /* Pointer to next dup record with different block */
75 struct dup_block
*next_block
;
76 /* Pointer to next dup record with different inode */
77 struct dup_block
*next_inode
;
80 #define FLAG_EXTATTR (1)
83 * This structure stores information about a particular inode which
84 * is sharing blocks with other inodes. This information is collected
85 * to display to the user, so that the user knows what files he or she
86 * is dealing with, when trying to decide how to resolve the conflict
87 * of multiply-claimed blocks.
92 struct ext2_inode inode
;
93 struct dup_inode
*next
;
96 static int process_pass1b_block(ext2_filsys fs
, blk_t
*blocknr
,
97 e2_blkcnt_t blockcnt
, blk_t ref_blk
,
98 int ref_offset
, void *priv_data
);
99 static void delete_file(e2fsck_t ctx
, struct dup_inode
*dp
,
101 static int clone_file(e2fsck_t ctx
, struct dup_inode
*dp
, char* block_buf
);
102 static int check_if_fs_block(e2fsck_t ctx
, blk_t test_blk
);
104 static void pass1b(e2fsck_t ctx
, char *block_buf
);
105 static void pass1c(e2fsck_t ctx
, char *block_buf
);
106 static void pass1d(e2fsck_t ctx
, char *block_buf
);
108 static struct dup_block
*dup_blk
= 0;
109 static struct dup_inode
*dup_ino
= 0;
110 static int dup_inode_count
= 0;
112 static ext2fs_inode_bitmap inode_dup_map
;
115 * Main procedure for handling duplicate blocks
117 void e2fsck_pass1_dupblocks(e2fsck_t ctx
, char *block_buf
)
119 ext2_filsys fs
= ctx
->fs
;
120 struct dup_block
*p
, *q
, *next_p
, *next_q
;
121 struct dup_inode
*r
, *next_r
;
122 struct problem_context pctx
;
124 clear_problem_context(&pctx
);
126 pctx
.errcode
= ext2fs_allocate_inode_bitmap(fs
,
127 _("multiply claimed inode map"), &inode_dup_map
);
129 fix_problem(ctx
, PR_1B_ALLOCATE_IBITMAP_ERROR
, &pctx
);
130 ctx
->flags
|= E2F_FLAG_ABORT
;
134 pass1b(ctx
, block_buf
);
135 pass1c(ctx
, block_buf
);
136 pass1d(ctx
, block_buf
);
139 * Time to free all of the accumulated data structures that we
140 * don't need anymore.
142 ext2fs_free_inode_bitmap(inode_dup_map
); inode_dup_map
= 0;
143 ext2fs_free_block_bitmap(ctx
->block_dup_map
); ctx
->block_dup_map
= 0;
144 for (p
= dup_blk
; p
; p
= next_p
) {
145 next_p
= p
->next_block
;
146 for (q
= p
; q
; q
= next_q
) {
147 next_q
= q
->next_inode
;
148 ext2fs_free_mem((void **) &q
);
151 for (r
= dup_ino
; r
; r
= next_r
) {
153 ext2fs_free_mem((void **) &r
);
158 * Scan the inodes looking for inodes that contain duplicate blocks.
160 struct process_block_struct
{
164 struct problem_context
*pctx
;
167 static void pass1b(e2fsck_t ctx
, char *block_buf
)
169 ext2_filsys fs
= ctx
->fs
;
171 struct ext2_inode inode
;
172 ext2_inode_scan scan
;
173 struct process_block_struct pb
;
174 struct dup_inode
*dp
;
175 struct dup_block
*q
, *r
;
176 struct problem_context pctx
;
179 clear_problem_context(&pctx
);
181 fix_problem(ctx
, PR_1B_PASS_HEADER
, &pctx
);
182 pctx
.errcode
= ext2fs_open_inode_scan(fs
, ctx
->inode_buffer_blocks
,
185 fix_problem(ctx
, PR_1B_ISCAN_ERROR
, &pctx
);
186 ctx
->flags
|= E2F_FLAG_ABORT
;
189 pctx
.errcode
= ext2fs_get_next_inode(scan
, &ino
, &inode
);
191 fix_problem(ctx
, PR_1B_ISCAN_ERROR
, &pctx
);
192 ctx
->flags
|= E2F_FLAG_ABORT
;
195 ctx
->stashed_inode
= &inode
;
200 pctx
.ino
= ctx
->stashed_ino
= ino
;
201 if ((ino
!= EXT2_BAD_INO
) &&
202 (!ext2fs_test_inode_bitmap(ctx
->inode_used_map
, ino
) ||
203 !ext2fs_inode_has_valid_blocks(&inode
)))
208 pctx
.errcode
= ext2fs_block_iterate2(fs
, ino
, 0, block_buf
,
209 process_pass1b_block
, &pb
);
210 if (inode
.i_file_acl
)
211 process_pass1b_block(fs
, &inode
.i_file_acl
,
212 BLOCK_COUNT_EXTATTR
, 0, 0, &pb
);
214 end_problem_latch(ctx
, PR_LATCH_DBLOCK
);
215 dp
= (struct dup_inode
*) e2fsck_allocate_memory(ctx
,
216 sizeof(struct dup_inode
),
217 "duplicate inode record");
221 dp
->num_dupblocks
= pb
.dup_blocks
;
224 if (ino
!= EXT2_BAD_INO
)
228 fix_problem(ctx
, PR_1B_BLOCK_ITERATE
, &pctx
);
230 pctx
.errcode
= ext2fs_get_next_inode(scan
, &ino
, &inode
);
231 if (pctx
.errcode
== EXT2_ET_BAD_BLOCK_IN_INODE_TABLE
)
234 fix_problem(ctx
, PR_1B_ISCAN_ERROR
, &pctx
);
235 ctx
->flags
|= E2F_FLAG_ABORT
;
239 ext2fs_close_inode_scan(scan
);
240 e2fsck_use_inode_shortcuts(ctx
, 0);
242 * Set the num_bad field
244 for (q
= dup_blk
; q
; q
= q
->next_block
) {
247 for (r
= q
; r
; r
= r
->next_inode
) {
248 if (r
->flags
& FLAG_EXTATTR
) {
258 static int process_pass1b_block(ext2_filsys fs
,
260 e2_blkcnt_t blockcnt
,
265 struct process_block_struct
*p
;
266 struct dup_block
*dp
, *q
;
269 if (HOLE_BLKADDR(*block_nr
))
271 p
= (struct process_block_struct
*) priv_data
;
274 if (ext2fs_test_block_bitmap(ctx
->block_dup_map
, *block_nr
)) {
275 /* OK, this is a duplicate block */
276 if (p
->ino
!= EXT2_BAD_INO
) {
277 p
->pctx
->blk
= *block_nr
;
278 fix_problem(ctx
, PR_1B_DUP_BLOCK
, p
->pctx
);
281 ext2fs_mark_block_bitmap(ctx
->block_dup_map
, *block_nr
);
282 ext2fs_mark_inode_bitmap(inode_dup_map
, p
->ino
);
283 dp
= (struct dup_block
*) e2fsck_allocate_memory(ctx
,
284 sizeof(struct dup_block
),
285 "duplicate block record");
286 dp
->block
= *block_nr
;
289 dp
->flags
= (blockcnt
== BLOCK_COUNT_EXTATTR
) ?
293 if (q
->block
== *block_nr
)
298 dp
->next_inode
= q
->next_inode
;
301 dp
->next_block
= dup_blk
;
309 * Pass 1c: Scan directories for inodes with duplicate blocks. This
310 * is used so that we can print pathnames when prompting the user for
313 struct search_dir_struct
{
315 ext2_ino_t first_inode
;
316 ext2_ino_t max_inode
;
319 static int search_dirent_proc(ext2_ino_t dir
, int entry
,
320 struct ext2_dir_entry
*dirent
,
321 int offset
, int blocksize
,
322 char *buf
, void *priv_data
)
324 struct search_dir_struct
*sd
;
327 sd
= (struct search_dir_struct
*) priv_data
;
329 if (dirent
->inode
> sd
->max_inode
)
330 /* Should abort this inode, but not everything */
333 if (!dirent
->inode
|| (entry
< DIRENT_OTHER_FILE
) ||
334 !ext2fs_test_inode_bitmap(inode_dup_map
, dirent
->inode
))
337 for (p
= dup_ino
; p
; p
= p
->next
) {
338 if ((p
->ino
>= sd
->first_inode
) &&
339 (p
->ino
== dirent
->inode
))
349 return(sd
->count
? 0 : DIRENT_ABORT
);
353 static void pass1c(e2fsck_t ctx
, char *block_buf
)
355 ext2_filsys fs
= ctx
->fs
;
357 int inodes_left
= dup_inode_count
;
358 struct search_dir_struct sd
;
359 struct problem_context pctx
;
361 clear_problem_context(&pctx
);
363 fix_problem(ctx
, PR_1C_PASS_HEADER
, &pctx
);
366 * First check to see if any of the inodes with dup blocks is
367 * a special inode. (Note that the bad block inode isn't
370 for (p
= dup_ino
; p
; p
= p
->next
) {
371 if ((p
->ino
< EXT2_FIRST_INODE(fs
->super
)) &&
372 (p
->ino
!= EXT2_BAD_INO
))
377 * Search through all directories to translate inodes to names
378 * (by searching for the containing directory for that inode.)
380 sd
.count
= inodes_left
;
381 sd
.first_inode
= EXT2_FIRST_INODE(fs
->super
);
382 sd
.max_inode
= fs
->super
->s_inodes_count
;
383 ext2fs_dblist_dir_iterate(fs
->dblist
, 0, block_buf
,
384 search_dirent_proc
, &sd
);
387 static void pass1d(e2fsck_t ctx
, char *block_buf
)
389 ext2_filsys fs
= ctx
->fs
;
390 struct dup_inode
*p
, *s
;
391 struct dup_block
*q
, *r
;
397 struct problem_context pctx
;
399 clear_problem_context(&pctx
);
401 fix_problem(ctx
, PR_1D_PASS_HEADER
, &pctx
);
402 e2fsck_read_bitmaps(ctx
);
404 pctx
.num
= dup_inode_count
;
405 fix_problem(ctx
, PR_1D_NUM_DUP_INODES
, &pctx
);
406 shared
= (ext2_ino_t
*) e2fsck_allocate_memory(ctx
,
407 sizeof(ext2_ino_t
) * dup_inode_count
,
408 "Shared inode list");
409 for (p
= dup_ino
; p
; p
= p
->next
) {
412 if (p
->ino
== EXT2_BAD_INO
)
416 * Search through the duplicate records to see which
417 * inodes share blocks with this one
419 for (q
= dup_blk
; q
; q
= q
->next_block
) {
421 * See if this block is used by this inode.
422 * If it isn't, continue.
424 for (r
= q
; r
; r
= r
->next_inode
)
425 if (r
->ino
== p
->ino
)
431 if (check_if_fs_block(ctx
, q
->block
)) {
437 * Add all inodes used by this block to the
438 * shared[] --- which is a unique list, so
439 * if an inode is already in shared[], don't
442 for (r
= q
; r
; r
= r
->next_inode
) {
443 if (r
->ino
== p
->ino
)
445 for (i
= 0; i
< shared_len
; i
++)
446 if (shared
[i
] == r
->ino
)
448 if (i
== shared_len
) {
449 shared
[shared_len
++] = r
->ino
;
455 * Report the inode that we are working on
457 pctx
.inode
= &p
->inode
;
460 pctx
.blkcount
= p
->num_dupblocks
;
461 pctx
.num
= meta_data
? shared_len
+1 : shared_len
;
462 fix_problem(ctx
, PR_1D_DUP_FILE
, &pctx
);
467 fix_problem(ctx
, PR_1D_SHARE_METADATA
, &pctx
);
469 for (i
= 0; i
< shared_len
; i
++) {
470 for (s
= dup_ino
; s
; s
= s
->next
)
471 if (s
->ino
== shared
[i
])
476 * Report the inode that we are sharing with
478 pctx
.inode
= &s
->inode
;
481 fix_problem(ctx
, PR_1D_DUP_FILE_LIST
, &pctx
);
484 fix_problem(ctx
, PR_1D_DUP_BLOCKS_DEALT
, &pctx
);
487 if (fix_problem(ctx
, PR_1D_CLONE_QUESTION
, &pctx
)) {
488 pctx
.errcode
= clone_file(ctx
, p
, block_buf
);
490 fix_problem(ctx
, PR_1D_CLONE_ERROR
, &pctx
);
494 if (fix_problem(ctx
, PR_1D_DELETE_QUESTION
, &pctx
))
495 delete_file(ctx
, p
, block_buf
);
497 ext2fs_unmark_valid(fs
);
499 ext2fs_free_mem((void **) &shared
);
503 * Drop the refcount on the dup_block structure, and clear the entry
504 * in the block_dup_map if appropriate.
506 static void decrement_badcount(e2fsck_t ctx
, struct dup_block
*p
)
509 if (p
->num_bad
<= 0 ||
510 (p
->num_bad
== 1 && !check_if_fs_block(ctx
, p
->block
)))
511 ext2fs_unmark_block_bitmap(ctx
->block_dup_map
, p
->block
);
514 static int delete_file_block(ext2_filsys fs
,
516 e2_blkcnt_t blockcnt
,
521 struct process_block_struct
*pb
;
525 pb
= (struct process_block_struct
*) priv_data
;
528 if (HOLE_BLKADDR(*block_nr
))
531 if (ext2fs_test_block_bitmap(ctx
->block_dup_map
, *block_nr
)) {
532 for (p
= dup_blk
; p
; p
= p
->next_block
)
533 if (p
->block
== *block_nr
)
536 decrement_badcount(ctx
, p
);
538 com_err("delete_file_block", 0,
539 _("internal error; can't find dup_blk for %d\n"),
542 ext2fs_unmark_block_bitmap(ctx
->block_found_map
, *block_nr
);
543 ext2fs_unmark_block_bitmap(fs
->block_map
, *block_nr
);
549 static void delete_file(e2fsck_t ctx
, struct dup_inode
*dp
, char* block_buf
)
551 ext2_filsys fs
= ctx
->fs
;
552 struct process_block_struct pb
;
553 struct ext2_inode inode
;
554 struct problem_context pctx
;
556 clear_problem_context(&pctx
);
557 pctx
.ino
= pb
.ino
= dp
->ino
;
558 pb
.dup_blocks
= dp
->num_dupblocks
;
560 pctx
.str
= "delete_file";
562 pctx
.errcode
= ext2fs_block_iterate2(fs
, dp
->ino
, 0, block_buf
,
563 delete_file_block
, &pb
);
565 fix_problem(ctx
, PR_1B_BLOCK_ITERATE
, &pctx
);
566 ext2fs_unmark_inode_bitmap(ctx
->inode_used_map
, dp
->ino
);
567 ext2fs_unmark_inode_bitmap(ctx
->inode_dir_map
, dp
->ino
);
568 if (ctx
->inode_bad_map
)
569 ext2fs_unmark_inode_bitmap(ctx
->inode_bad_map
, dp
->ino
);
570 ext2fs_unmark_inode_bitmap(fs
->inode_map
, dp
->ino
);
571 ext2fs_mark_ib_dirty(fs
);
572 ext2fs_mark_bb_dirty(fs
);
573 e2fsck_read_inode(ctx
, dp
->ino
, &inode
, "delete_file");
574 inode
.i_links_count
= 0;
575 inode
.i_dtime
= time(0);
576 if (inode
.i_file_acl
)
577 delete_file_block(fs
, &inode
.i_file_acl
,
578 BLOCK_COUNT_EXTATTR
, 0, 0, &pb
);
579 e2fsck_write_inode(ctx
, dp
->ino
, &inode
, "delete_file");
582 struct clone_struct
{
589 static int clone_file_block(ext2_filsys fs
,
591 e2_blkcnt_t blockcnt
,
599 struct clone_struct
*cs
= (struct clone_struct
*) priv_data
;
604 if (HOLE_BLKADDR(*block_nr
))
607 if (ext2fs_test_block_bitmap(ctx
->block_dup_map
, *block_nr
)) {
608 for (p
= dup_blk
; p
; p
= p
->next_block
)
609 if (p
->block
== *block_nr
)
612 retval
= ext2fs_new_block(fs
, 0, ctx
->block_found_map
,
615 cs
->errcode
= retval
;
618 if (cs
->dir
&& (blockcnt
>= 0)) {
619 retval
= ext2fs_set_dir_block(fs
->dblist
,
620 cs
->dir
, new_block
, blockcnt
);
622 cs
->errcode
= retval
;
627 printf("Cloning block %u to %u\n", *block_nr
,
630 retval
= io_channel_read_blk(fs
->io
, *block_nr
, 1,
633 cs
->errcode
= retval
;
636 retval
= io_channel_write_blk(fs
->io
, new_block
, 1,
639 cs
->errcode
= retval
;
642 decrement_badcount(ctx
, p
);
643 *block_nr
= new_block
;
644 ext2fs_mark_block_bitmap(ctx
->block_found_map
,
646 ext2fs_mark_block_bitmap(fs
->block_map
, new_block
);
647 return BLOCK_CHANGED
;
649 com_err("clone_file_block", 0,
650 _("internal error; can't find dup_blk for %d\n"),
656 static int clone_file(e2fsck_t ctx
, struct dup_inode
*dp
, char* block_buf
)
658 ext2_filsys fs
= ctx
->fs
;
660 struct clone_struct cs
;
661 struct problem_context pctx
;
664 clear_problem_context(&pctx
);
668 retval
= ext2fs_get_mem(fs
->blocksize
, (void **) &cs
.buf
);
672 if (ext2fs_test_inode_bitmap(ctx
->inode_dir_map
, dp
->ino
))
676 pctx
.str
= "clone_file";
677 pctx
.errcode
= ext2fs_block_iterate2(fs
, dp
->ino
, 0, block_buf
,
678 clone_file_block
, &cs
);
679 ext2fs_mark_bb_dirty(fs
);
681 fix_problem(ctx
, PR_1B_BLOCK_ITERATE
, &pctx
);
682 retval
= pctx
.errcode
;
686 com_err("clone_file", cs
.errcode
,
687 _("returned from clone_file_block"));
691 blk
= dp
->inode
.i_file_acl
;
692 if (blk
&& (clone_file_block(fs
, &dp
->inode
.i_file_acl
,
693 BLOCK_COUNT_EXTATTR
, 0, 0, &cs
) ==
695 struct dup_block
*p
, *q
;
699 * If we cloned the EA block, find all other inodes
700 * which refered to that EA block, and modify
701 * them to point to the new EA block.
703 for (p
= dup_blk
; p
; p
= p
->next_block
) {
707 for (q
= p
; q
; q
= q
->next_inode
) {
708 if (!(q
->flags
& FLAG_EXTATTR
))
710 for (r
= dup_ino
; r
; r
= r
->next
)
711 if (r
->ino
== q
->ino
)
714 r
->inode
.i_file_acl
= dp
->inode
.i_file_acl
;
715 e2fsck_write_inode(ctx
, q
->ino
, &r
->inode
,
718 q
->ino
= 0; /* Should free the structure... */
719 decrement_badcount(ctx
, p
);
724 ext2fs_free_mem((void **) &cs
.buf
);
729 * This routine returns 1 if a block overlaps with one of the superblocks,
730 * group descriptors, inode bitmaps, or block bitmaps.
732 static int check_if_fs_block(e2fsck_t ctx
, blk_t test_block
)
734 ext2_filsys fs
= ctx
->fs
;
738 block
= fs
->super
->s_first_data_block
;
739 for (i
= 0; i
< fs
->group_desc_count
; i
++) {
741 /* Check superblocks/block group descriptros */
742 if (ext2fs_bg_has_super(fs
, i
)) {
743 if (test_block
>= block
&&
744 (test_block
<= block
+ fs
->desc_blocks
))
748 /* Check the inode table */
749 if ((fs
->group_desc
[i
].bg_inode_table
) &&
750 (test_block
>= fs
->group_desc
[i
].bg_inode_table
) &&
751 (test_block
< (fs
->group_desc
[i
].bg_inode_table
+
752 fs
->inode_blocks_per_group
)))
755 /* Check the bitmap blocks */
756 if ((test_block
== fs
->group_desc
[i
].bg_block_bitmap
) ||
757 (test_block
== fs
->group_desc
[i
].bg_inode_bitmap
))
760 block
+= fs
->super
->s_blocks_per_group
;