Whamcloud - gitweb
ChangeLog, pass1b.c:
[tools/e2fsprogs.git] / e2fsck / pass1b.c
1 /*
2  * pass1b.c --- Pass #1b of e2fsck
3  *
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
6  * than one inode.
7  * 
8  * Pass1B scans the data blocks of all the inodes again, generating a
9  * complete list of duplicate blocks and which inodes have claimed
10  * them.
11  *
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.
15  *
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.
20  * 
21  * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
22  *
23  * %Begin-Header%
24  * This file may be redistributed under the terms of the GNU Public
25  * License.
26  * %End-Header%
27  * 
28  */
29
30 #include <time.h>
31 #ifdef HAVE_ERRNO_H
32 #include <errno.h>
33 #endif
34
35 #include <et/com_err.h>
36 #include "e2fsck.h"
37
38 #include "problem.h"
39
40 /*
41  * This is structure is allocated for each time that a block is
42  * claimed by more than one file.  So if a particular block is claimed
43  * by 3 files, then three copies of this structure will be allocated,
44  * one for each conflict.
45  *
46  * The linked list structure is as follows:
47  *
48  * dup_blk -->  block #34  --> block #35  --> block #47
49  *              inode #12      inode #14      inode #17
50  *              num_bad = 3    num_bad = 2    num_bad = 2
51  *                |              |               |
52  *                V              V               V
53  *              block #34      block #35      block #47
54  *              inode #14      inode #15      inode #23
55  *                |
56  *                V
57  *              block #34
58  *              inode #15
59  *
60  * The num_bad field indicates how many inodes are sharing a
61  * particular block, and is only stored in the first element of the
62  * linked list for a particular block.  As the block conflicts are
63  * resolved, num_bad is decremented; when it reaches 1, then we no
64  * longer need to worry about that block.
65  */
66 struct dup_block {
67         blk_t           block;          /* Block number */
68         ino_t           ino;            /* Inode number */
69         int             num_bad;
70         /* Pointer to next dup record with different block */
71         struct dup_block *next_block;
72         /* Pointer to next dup record with different inode */
73         struct dup_block *next_inode;
74 };
75
76 /*
77  * This structure stores information about a particular inode which
78  * is sharing blocks with other inodes.  This information is collected
79  * to display to the user, so that the user knows what files he or she
80  * is dealing with, when trying to decide how to resolve the conflict
81  * of multiply-claimed blocks.
82  */
83 struct dup_inode {
84         ino_t                   ino, dir;
85         int                     num_dupblocks;
86         struct ext2_inode       inode;
87         struct dup_inode        *next;
88 };
89
90 static int process_pass1b_block(ext2_filsys fs, blk_t   *blocknr,
91                                 int     blockcnt, void  *priv_data);
92 static void delete_file(e2fsck_t ctx, struct dup_inode *dp,
93                         char *block_buf);
94 static int clone_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf);
95 static void pass1b(e2fsck_t ctx, char *block_buf);
96 static void pass1c(e2fsck_t ctx, char *block_buf);
97 static void pass1d(e2fsck_t ctx, char *block_buf);
98
99 static struct dup_block *dup_blk = 0;
100 static struct dup_inode *dup_ino = 0;
101 static int dup_inode_count = 0;
102
103 static ext2fs_inode_bitmap inode_dup_map;
104
105 /*
106  * Main procedure for handling duplicate blocks
107  */
108 void e2fsck_pass1_dupblocks(e2fsck_t ctx, char *block_buf)
109 {
110         ext2_filsys             fs = ctx->fs;
111         struct dup_block        *p, *q, *next_p, *next_q;
112         struct dup_inode        *r, *next_r;
113         struct problem_context  pctx;
114
115         clear_problem_context(&pctx);
116         
117         pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
118                       "multiply claimed inode map", &inode_dup_map);
119         if (pctx.errcode) {
120                 fix_problem(ctx, PR_1B_ALLOCATE_IBITMAP_ERROR, &pctx);
121                 ctx->flags |= E2F_FLAG_ABORT;
122                 return;
123         }
124         
125         pass1b(ctx, block_buf);
126         pass1c(ctx, block_buf);
127         pass1d(ctx, block_buf);
128
129         /*
130          * Time to free all of the accumulated data structures that we
131          * don't need anymore.
132          */
133         ext2fs_free_inode_bitmap(inode_dup_map); inode_dup_map = 0;
134         ext2fs_free_block_bitmap(ctx->block_dup_map); ctx->block_dup_map = 0;
135         for (p = dup_blk; p; p = next_p) {
136                 next_p = p->next_block;
137                 for (q = p; q; q = next_q) {
138                         next_q = q->next_inode;
139                         ext2fs_free_mem((void **) &q);
140                 }
141         }
142         for (r = dup_ino; r; r = next_r) {
143                 next_r = r->next;
144                 ext2fs_free_mem((void **) &r);
145         }
146 }
147
148 /*
149  * Scan the inodes looking for inodes that contain duplicate blocks.
150  */
151 struct process_block_struct {
152         ino_t   ino;
153         int     dup_blocks;
154         e2fsck_t ctx;
155         struct problem_context *pctx;
156 };
157
158 static void pass1b(e2fsck_t ctx, char *block_buf)
159 {
160         ext2_filsys fs = ctx->fs;
161         ino_t   ino;
162         struct ext2_inode inode;
163         ext2_inode_scan scan;
164         errcode_t       retval;
165         struct process_block_struct pb;
166         struct dup_inode *dp;
167         struct problem_context pctx;
168
169         clear_problem_context(&pctx);
170         
171         fix_problem(ctx, PR_1B_PASS_HEADER, &pctx);
172         pctx.errcode = ext2fs_open_inode_scan(fs, ctx->inode_buffer_blocks,
173                                               &scan);
174         if (pctx.errcode) {
175                 fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
176                 ctx->flags |= E2F_FLAG_ABORT;
177                 return;
178         }
179         pctx.errcode = ext2fs_get_next_inode(scan, &ino, &inode);
180         if (pctx.errcode) {
181                 fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
182                 ctx->flags |= E2F_FLAG_ABORT;
183                 return;
184         }
185         ctx->stashed_inode = &inode;
186         pb.ctx = ctx;
187         pb.pctx = &pctx;
188         while (ino) {
189                 pctx.ino = ctx->stashed_ino = ino;
190                 if ((ino != EXT2_BAD_INO) &&
191                     (!ext2fs_test_inode_bitmap(ctx->inode_used_map, ino) ||
192                      !ext2fs_inode_has_valid_blocks(&inode)))
193                         goto next;
194
195                 pb.ino = ino;
196                 pb.dup_blocks = 0;
197                 retval = ext2fs_block_iterate(fs, ino, 0, block_buf,
198                                               process_pass1b_block, &pb);
199                 if (pb.dup_blocks) {
200                         end_problem_latch(ctx, PR_LATCH_DBLOCK);
201                         dp = (struct dup_inode *) e2fsck_allocate_memory(ctx,
202                                     sizeof(struct dup_inode),
203                                     "duplicate inode record");
204                         dp->ino = ino;
205                         dp->dir = 0;
206                         dp->inode = inode;
207                         dp->num_dupblocks = pb.dup_blocks;
208                         dp->next = dup_ino;
209                         dup_ino = dp;
210                         if (ino != EXT2_BAD_INO)
211                                 dup_inode_count++;
212                 }
213                 if (retval)
214                         com_err(ctx->program_name, retval,
215                                 "while calling ext2fs_block_iterate in pass1b");
216                 
217         next:
218                 pctx.errcode = ext2fs_get_next_inode(scan, &ino, &inode);
219                 if (pctx.errcode == EXT2_ET_BAD_BLOCK_IN_INODE_TABLE)
220                         goto next;
221                 if (pctx.errcode) {
222                         fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
223                         ctx->flags |= E2F_FLAG_ABORT;
224                         return;
225                 }
226         }
227         ext2fs_close_inode_scan(scan);
228         fs->get_blocks = 0;
229         fs->check_directory = 0;
230 }
231
232 int process_pass1b_block(ext2_filsys fs,
233                          blk_t  *block_nr,
234                          int blockcnt,
235                          void *priv_data)
236 {
237         struct process_block_struct *p;
238         struct dup_block *dp, *q, *r;
239         int i;
240         e2fsck_t ctx;
241
242         if (!*block_nr)
243                 return 0;
244         p = (struct process_block_struct *) priv_data;
245         ctx = p->ctx;
246         
247         if (ext2fs_test_block_bitmap(ctx->block_dup_map, *block_nr)) {
248                 /* OK, this is a duplicate block */
249                 if (p->ino != EXT2_BAD_INO) {
250                         p->pctx->blk = *block_nr;
251                         fix_problem(ctx, PR_1B_DUP_BLOCK, p->pctx);
252                 }
253                 p->dup_blocks++;
254                 ext2fs_mark_block_bitmap(ctx->block_dup_map, *block_nr);
255                 ext2fs_mark_inode_bitmap(inode_dup_map, p->ino);
256                 dp = (struct dup_block *) e2fsck_allocate_memory(ctx,
257                                             sizeof(struct dup_block),
258                                             "duplicate block record");
259                 dp->block = *block_nr;
260                 dp->ino = p->ino;
261                 dp->num_bad = 0;
262                 q = dup_blk;
263                 while (q) {
264                         if (q->block == *block_nr)
265                                 break;
266                         q = q->next_block;
267                 }
268                 if (q) {
269                         dp->next_inode = q->next_inode;
270                         q->next_inode = dp;
271                 } else {
272                         dp->next_block = dup_blk;
273                         dup_blk = dp;
274                 }
275         }
276         /*
277          * Set the num_bad field
278          */
279         for (q = dup_blk; q; q = q->next_block) {
280                 i = 0;
281                 for (r = q; r; r = r->next_inode)
282                         i++;
283                 q->num_bad = i;
284         }
285         return 0;
286 }
287
288 /*
289  * Pass 1c: Scan directories for inodes with duplicate blocks.  This
290  * is used so that we can print pathnames when prompting the user for
291  * what to do.
292  */
293 struct search_dir_struct {
294         int             count;
295         ino_t           first_inode;
296         ino_t           max_inode;
297 };
298
299 static int search_dirent_proc(ino_t dir, int entry,
300                               struct ext2_dir_entry *dirent,
301                               int offset, int blocksize,
302                               char *buf, void *priv_data)
303 {
304         struct search_dir_struct *sd;
305         struct dup_inode        *p;
306
307         sd = (struct search_dir_struct *) priv_data;
308
309         if (dirent->inode > sd->max_inode)
310                 /* Should abort this inode, but not everything */
311                 return 0;       
312
313         if (!dirent->inode || (entry < DIRENT_OTHER_FILE) ||
314             !ext2fs_test_inode_bitmap(inode_dup_map, dirent->inode))
315                 return 0;
316
317         for (p = dup_ino; p; p = p->next) {
318                 if ((p->ino >= sd->first_inode) && 
319                     (p->ino == dirent->inode))
320                         break;
321         }
322
323         if (!p || p->dir)
324                 return 0;
325
326         p->dir = dir;
327         sd->count--;
328
329         return(sd->count ? 0 : DIRENT_ABORT);
330 }
331
332
333 static void pass1c(e2fsck_t ctx, char *block_buf)
334 {
335         ext2_filsys fs = ctx->fs;
336         struct dup_inode        *p;
337         int     inodes_left = dup_inode_count;
338         struct search_dir_struct sd;
339         struct problem_context pctx;
340
341         clear_problem_context(&pctx);
342
343         fix_problem(ctx, PR_1C_PASS_HEADER, &pctx);
344
345         /*
346          * First check to see if any of the inodes with dup blocks is
347          * a special inode.  (Note that the bad block inode isn't
348          * counted.)
349          */
350         for (p = dup_ino; p; p = p->next) {
351                 if ((p->ino < EXT2_FIRST_INODE(fs->super)) &&
352                     (p->ino != EXT2_BAD_INO))
353                         inodes_left--;
354         }
355
356         /*
357          * Search through all directories to translate inodes to names
358          * (by searching for the containing directory for that inode.)
359          */
360         sd.count = inodes_left;
361         sd.first_inode = EXT2_FIRST_INODE(fs->super);
362         sd.max_inode = fs->super->s_inodes_count;
363         ext2fs_dblist_dir_iterate(fs->dblist, 0, block_buf,
364                                   search_dirent_proc, &sd);
365 }       
366
367 static void pass1d(e2fsck_t ctx, char *block_buf)
368 {
369         ext2_filsys fs = ctx->fs;
370         struct dup_inode        *p, *s;
371         struct dup_block        *q, *r;
372         ino_t   *shared;
373         int     shared_len;
374         int     i;
375         int     file_ok;
376         int     meta_data = 0;
377         struct problem_context pctx;
378
379         clear_problem_context(&pctx);
380         
381         fix_problem(ctx, PR_1D_PASS_HEADER, &pctx);
382         e2fsck_read_bitmaps(ctx);
383
384         pctx.num = dup_inode_count;
385         fix_problem(ctx, PR_1D_NUM_DUP_INODES, &pctx);
386         shared = (ino_t *) e2fsck_allocate_memory(ctx,
387                                 sizeof(ino_t) * dup_inode_count,
388                                 "Shared inode list");
389         for (p = dup_ino; p; p = p->next) {
390                 shared_len = 0;
391                 file_ok = 1;
392                 if (p->ino == EXT2_BAD_INO)
393                         continue;
394
395                 /*
396                  * Search through the duplicate records to see which
397                  * inodes share blocks with this one
398                  */
399                 for (q = dup_blk; q; q = q->next_block) {
400                         /*
401                          * See if this block is used by this inode.
402                          * If it isn't, continue.
403                          */
404                         for (r = q; r; r = r->next_inode)
405                                 if (r->ino == p->ino)
406                                         break;
407                         if (!r)
408                                 continue;
409                         if (q->num_bad > 1)
410                                 file_ok = 0;
411                         if (ext2fs_test_block_bitmap(ctx->block_illegal_map,
412                                                      q->block)) {
413                                 file_ok = 0;
414                                 meta_data = 1;
415                         }
416                         
417                         /*
418                          * Add all inodes used by this block to the
419                          * shared[] --- which is a unique list, so
420                          * if an inode is already in shared[], don't
421                          * add it again.
422                          */
423                         for (r = q; r; r = r->next_inode) {
424                                 if (r->ino == p->ino)
425                                         continue;
426                                 for (i = 0; i < shared_len; i++)
427                                         if (shared[i] == r->ino)
428                                                 break;
429                                 if (i == shared_len) {
430                                         shared[shared_len++] = r->ino;
431                                 }
432                         }
433                 }
434
435                 /*
436                  * Report the inode that we are working on
437                  */
438                 pctx.inode = &p->inode;
439                 pctx.ino = p->ino;
440                 pctx.dir = p->dir;
441                 pctx.blkcount = p->num_dupblocks;
442                 pctx.num = meta_data ? shared_len+1 : shared_len;
443                 fix_problem(ctx, PR_1D_DUP_FILE, &pctx);
444                 pctx.blkcount = 0;
445                 pctx.num = 0;
446                 
447                 if (meta_data)
448                         fix_problem(ctx, PR_1D_SHARE_METADATA, &pctx);
449                 
450                 for (i = 0; i < shared_len; i++) {
451                         for (s = dup_ino; s; s = s->next)
452                                 if (s->ino == shared[i])
453                                         break;
454                         if (!s)
455                                 continue;
456                         /*
457                          * Report the inode that we are sharing with
458                          */
459                         pctx.inode = &s->inode;
460                         pctx.ino = s->ino;
461                         pctx.dir = s->dir;
462                         fix_problem(ctx, PR_1D_DUP_FILE_LIST, &pctx);
463                 }
464                 if (file_ok) {
465                         fix_problem(ctx, PR_1D_DUP_BLOCKS_DEALT, &pctx);
466                         continue;
467                 }
468                 if (fix_problem(ctx, PR_1D_CLONE_QUESTION, &pctx)) {
469                         pctx.errcode = clone_file(ctx, p, block_buf);
470                         if (pctx.errcode)
471                                 fix_problem(ctx, PR_1D_CLONE_ERROR, &pctx);
472                         else
473                                 continue;
474                 }
475                 if (fix_problem(ctx, PR_1D_DELETE_QUESTION, &pctx))
476                         delete_file(ctx, p, block_buf);
477                 else
478                         ext2fs_unmark_valid(fs);
479         }
480         ext2fs_free_mem((void **) &shared);
481 }
482
483 static int delete_file_block(ext2_filsys fs,
484                              blk_t      *block_nr,
485                              int blockcnt,
486                              void *priv_data)
487 {
488         struct process_block_struct *pb;
489         struct dup_block *p;
490         e2fsck_t ctx;
491
492         pb = (struct process_block_struct *) priv_data;
493         ctx = pb->ctx;
494
495         if (!*block_nr)
496                 return 0;
497
498         if (ext2fs_test_block_bitmap(ctx->block_dup_map, *block_nr)) {
499                 for (p = dup_blk; p; p = p->next_block)
500                         if (p->block == *block_nr)
501                                 break;
502                 if (p) {
503                         p->num_bad--;
504                         if (p->num_bad == 1)
505                                 ext2fs_unmark_block_bitmap(ctx->block_dup_map,
506                                                            *block_nr);
507                 } else
508                         com_err("delete_file_block", 0,
509                                 "internal error; can't find dup_blk for %d\n",
510                                 *block_nr);
511         } else {
512                 ext2fs_unmark_block_bitmap(ctx->block_found_map, *block_nr);
513                 ext2fs_unmark_block_bitmap(fs->block_map, *block_nr);
514         }
515                 
516         return 0;
517 }
518                 
519 static void delete_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf)
520 {
521         ext2_filsys fs = ctx->fs;
522         errcode_t       retval;
523         struct process_block_struct pb;
524         struct ext2_inode       inode;
525
526         pb.ino = dp->ino;
527         pb.dup_blocks = dp->num_dupblocks;
528         pb.ctx = ctx;
529         
530         retval = ext2fs_block_iterate(fs, dp->ino, 0, block_buf,
531                                       delete_file_block, &pb);
532         if (retval)
533                 com_err("delete_file", retval,
534                         "while calling ext2fs_block_iterate for inode %d",
535                         dp->ino);
536         ext2fs_unmark_inode_bitmap(ctx->inode_used_map, dp->ino);
537         ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, dp->ino);
538         if (ctx->inode_bad_map)
539                 ext2fs_unmark_inode_bitmap(ctx->inode_bad_map, dp->ino);
540         ext2fs_unmark_inode_bitmap(fs->inode_map, dp->ino);
541         ext2fs_mark_ib_dirty(fs);
542         ext2fs_mark_bb_dirty(fs);
543         e2fsck_read_inode(ctx, dp->ino, &inode, "delete_file");
544         inode.i_links_count = 0;
545         inode.i_dtime = time(0);
546         e2fsck_write_inode(ctx, dp->ino, &inode, "delete_file");
547 }
548
549 struct clone_struct {
550         errcode_t       errcode;
551         ino_t           dir;
552         char    *buf;
553         e2fsck_t ctx;
554 };
555
556 static int clone_file_block(ext2_filsys fs,
557                             blk_t       *block_nr,
558                             int blockcnt,
559                             void *priv_data)
560 {
561         struct dup_block *p;
562         blk_t   new_block;
563         errcode_t       retval;
564         struct clone_struct *cs = (struct clone_struct *) priv_data;
565         e2fsck_t ctx;
566
567         ctx = cs->ctx;
568         
569         if (!*block_nr)
570                 return 0;
571
572         if (ext2fs_test_block_bitmap(ctx->block_dup_map, *block_nr)) {
573                 for (p = dup_blk; p; p = p->next_block)
574                         if (p->block == *block_nr)
575                                 break;
576                 if (p) {
577                         retval = ext2fs_new_block(fs, 0, ctx->block_found_map,
578                                                   &new_block);
579                         if (retval) {
580                                 cs->errcode = retval;
581                                 return BLOCK_ABORT;
582                         }
583                         if (cs->dir) {
584                                 retval = ext2fs_set_dir_block(fs->dblist,
585                                       cs->dir, new_block, blockcnt);
586                                 if (retval) {
587                                         cs->errcode = retval;
588                                         return BLOCK_ABORT;
589                                 }
590                         }
591                         retval = io_channel_read_blk(fs->io, *block_nr, 1,
592                                                      cs->buf);
593                         if (retval) {
594                                 cs->errcode = retval;
595                                 return BLOCK_ABORT;
596                         }
597                         retval = io_channel_write_blk(fs->io, new_block, 1,
598                                                       cs->buf);
599                         if (retval) {
600                                 cs->errcode = retval;
601                                 return BLOCK_ABORT;
602                         }
603                         p->num_bad--;
604                         if (p->num_bad == 1 &&
605                             !ext2fs_test_block_bitmap(ctx->block_illegal_map,
606                                                       *block_nr))
607                                 ext2fs_unmark_block_bitmap(ctx->block_dup_map,
608                                                            *block_nr);
609                         *block_nr = new_block;
610                         ext2fs_mark_block_bitmap(ctx->block_found_map,
611                                                  new_block);
612                         ext2fs_mark_block_bitmap(fs->block_map, new_block);
613                         return BLOCK_CHANGED;
614                 } else
615                         com_err("clone_file_block", 0,
616                                 "internal error; can't find dup_blk for %d\n",
617                                 *block_nr);
618         }
619         return 0;
620 }
621                 
622 static int clone_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf)
623 {
624         ext2_filsys fs = ctx->fs;
625         errcode_t       retval;
626         struct clone_struct cs;
627
628         cs.errcode = 0;
629         cs.dir = 0;
630         cs.ctx = ctx;
631         retval = ext2fs_get_mem(fs->blocksize, (void **) &cs.buf);
632         if (retval)
633                 return retval;
634
635         if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, dp->ino))
636                 cs.dir = dp->ino;
637         
638         retval = ext2fs_block_iterate(fs, dp->ino, 0, block_buf,
639                                       clone_file_block, &cs);
640         ext2fs_mark_bb_dirty(fs);
641         ext2fs_free_mem((void **) &cs.buf);
642         if (retval) {
643                 com_err("clone_file", retval,
644                         "while calling ext2fs_block_iterate for inode %d",
645                         dp->ino);
646                 return retval;
647         }
648         if (cs.errcode) {
649                 com_err("clone_file", cs.errcode,
650                         "returned from clone_file_block");
651                 return retval;
652         }
653         return 0;
654 }