sbin/fsck_lfs/pass1.c

   1 /* $NetBSD: pass1.c,v 1.28 2006/11/09 19:36:36 christos Exp $    */
   2
   3 /*
   4  * Copyright (c) 1980, 1986, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 #include <sys/param.h>
  33 #include <sys/time.h>
  34 #include <sys/mount.h>
  35 #include <sys/buf.h>
  36
  37 #include <ufs/ufs/inode.h>
  38 #include <ufs/ufs/dir.h>
  39 #define vnode uvnode
  40 #include <ufs/lfs/lfs.h>
  41 #undef vnode
  42
  43 #include <err.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <signal.h>
  48 #include <util.h>
  49
  50 #include "bufcache.h"
  51 #include "vnode.h"
  52 #include "lfs_user.h"
  53
  54 #include "fsck.h"
  55 #include "extern.h"
  56 #include "fsutil.h"
  57
  58 SEGUSE *seg_table;
  59 extern ufs_daddr_t *din_table;
  60
  61 ufs_daddr_t badblk;
  62 static ufs_daddr_t dupblk;
  63 static int i_d_cmp(const void *, const void *);
  64
  65 struct ino_daddr {
  66         ino_t ino;
  67         ufs_daddr_t daddr;
  68 };
  69
  70 static int
  71 i_d_cmp(const void *va, const void *vb)
  72 {
  73         const struct ino_daddr *a, *b;
  74
  75         a = *((const struct ino_daddr *const *) va);
  76         b = *((const struct ino_daddr *const *) vb);
  77
  78         if (a->daddr == b->daddr) {
  79                 return (a->ino - b->ino);
  80         }
  81         if (a->daddr > b->daddr) {
  82                 return 1;
  83         }
  84         return -1;
  85 }
  86
  87 void
  88 pass1(void)
  89 {
  90         ino_t inumber;
  91         int i;
  92         struct inodesc idesc;
  93         struct ufs1_dinode *tinode;
  94         struct ifile *ifp;
  95         struct ubuf *bp;
  96         struct ino_daddr **dins;
  97
  98         /*
  99          * Find all allocated blocks, initialize numdirs.
 100          */
 101         memset(&idesc, 0, sizeof(struct inodesc));
 102         idesc.id_type = ADDR;
 103         idesc.id_func = pass1check;
 104         idesc.id_lblkno = 0;
 105         inumber = 0;
 106         n_files = n_blks = 0;
 107
 108         if (debug)
 109                 printf("creating sorted inode address table...\n");
 110         /* Sort by daddr */
 111         dins = ecalloc(maxino, sizeof(*dins));
 112         for (i = 0; i < maxino; i++) {
 113                 dins[i] = emalloc(sizeof(**dins));
 114                 dins[i]->ino = i;
 115                 if (i == fs->lfs_ifile)
 116                         dins[i]->daddr = fs->lfs_idaddr;
 117                 else {
 118                         LFS_IENTRY(ifp, fs, i, bp);
 119                         dins[i]->daddr = ifp->if_daddr;
 120                         brelse(bp, 0);
 121                 }
 122         }
 123         qsort(dins, maxino, sizeof(*dins), i_d_cmp);
 124
 125         /* find a value for numdirs, fill in din_table */
 126         if (debug)
 127                 printf("counting dirs...\n");
 128         numdirs = 0;
 129         for (i = 0; i < maxino; i++) {
 130                 inumber = dins[i]->ino;
 131                 if (inumber == 0 || dins[i]->daddr == 0)
 132                         continue;
 133                 tinode = ginode(inumber);
 134                 if (tinode && (tinode->di_mode & IFMT) == IFDIR)
 135                         numdirs++;
 136         }
 137
 138         /* from setup.c */
 139         inplast = 0;
 140         listmax = numdirs + 10;
 141         inpsort = ecalloc(listmax, sizeof(struct inoinfo *));
 142         inphead = ecalloc(numdirs, sizeof(struct inoinfo *));
 143         if (debug)
 144                 printf("counting blocks...\n");
 145
 146         for (i = 0; i < maxino; i++) {
 147                 inumber = dins[i]->ino;
 148                 if (inumber == 0 || dins[i]->daddr == 0) {
 149                         statemap[inumber] = USTATE;
 150                         continue;
 151                 }
 152                 if (dins[i]->daddr != LFS_UNUSED_DADDR) {
 153                         checkinode(inumber, &idesc);
 154                 } else {
 155                         statemap[inumber] = USTATE;
 156                 }
 157                 free(dins[i]);
 158         }
 159         free(dins);
 160 }
 161
 162 void
 163 checkinode(ino_t inumber, struct inodesc * idesc)
 164 {
 165         struct ufs1_dinode *dp;
 166         struct uvnode  *vp;
 167         struct zlncnt *zlnp;
 168         struct ubuf *bp;
 169         IFILE *ifp;
 170         int ndb, j;
 171         mode_t mode;
 172
 173         vp = vget(fs, inumber);
 174         if (vp)
 175                 dp = VTOD(vp);
 176         else
 177                 dp = NULL;
 178
 179         if (dp == NULL) {
 180                 statemap[inumber] = USTATE;
 181                 return;
 182         }
 183         mode = dp->di_mode & IFMT;
 184
 185         /* XXX - LFS doesn't have this particular problem (?) */
 186         if (mode == 0) {
 187                 if (memcmp(dp->di_db, zino.di_db, NDADDR * sizeof(ufs_daddr_t)) ||
 188                     memcmp(dp->di_ib, zino.di_ib, NIADDR * sizeof(ufs_daddr_t)) ||
 189                     dp->di_mode || dp->di_size) {
 190                         pwarn("mode=o%o, ifmt=o%o\n", dp->di_mode, mode);
 191                         pfatal("PARTIALLY ALLOCATED INODE I=%llu",
 192                             (unsigned long long)inumber);
 193                         if (reply("CLEAR") == 1) {
 194                                 vp = vget(fs, inumber);
 195                                 clearinode(inumber);
 196                                 vnode_destroy(vp);
 197                         }
 198                 }
 199                 statemap[inumber] = USTATE;
 200                 return;
 201         }
 202         lastino = inumber;
 203         if (/* dp->di_size < 0 || */
 204             dp->di_size + fs->lfs_bsize - 1 < dp->di_size) {
 205                 if (debug)
 206                         printf("bad size %llu:",
 207                             (unsigned long long) dp->di_size);
 208                 goto unknown;
 209         }
 210         if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) {
 211                 vp = vget(fs, inumber);
 212                 dp = VTOD(vp);
 213                 dp->di_size = fs->lfs_fsize;
 214                 dp->di_mode = IFREG | 0600;
 215                 inodirty(VTOI(vp));
 216         }
 217         ndb = howmany(dp->di_size, fs->lfs_bsize);
 218         if (ndb < 0) {
 219                 if (debug)
 220                         printf("bad size %llu ndb %d:",
 221                             (unsigned long long) dp->di_size, ndb);
 222                 goto unknown;
 223         }
 224         if (mode == IFBLK || mode == IFCHR)
 225                 ndb++;
 226         if (mode == IFLNK) {
 227                 /*
 228                  * Fake ndb value so direct/indirect block checks below
 229                  * will detect any garbage after symlink string.
 230                  */
 231                 if (dp->di_size < fs->lfs_maxsymlinklen ||
 232                     (fs->lfs_maxsymlinklen == 0 && dp->di_blocks == 0)) {
 233                         ndb = howmany(dp->di_size, sizeof(ufs_daddr_t));
 234                         if (ndb > NDADDR) {
 235                                 j = ndb - NDADDR;
 236                                 for (ndb = 1; j > 1; j--)
 237                                         ndb *= NINDIR(fs);
 238                                 ndb += NDADDR;
 239                         }
 240                 }
 241         }
 242         for (j = ndb; j < NDADDR; j++)
 243                 if (dp->di_db[j] != 0) {
 244                         if (debug)
 245                                 printf("bad direct addr for size %lld lbn %d: 0x%x\n",
 246                                         (long long)dp->di_size, j, (unsigned)dp->di_db[j]);
 247                         goto unknown;
 248                 }
 249         for (j = 0, ndb -= NDADDR; ndb > 0; j++)
 250                 ndb /= NINDIR(fs);
 251         for (; j < NIADDR; j++)
 252                 if (dp->di_ib[j] != 0) {
 253                         if (debug)
 254                                 printf("bad indirect addr for size %lld # %d: 0x%x\n",
 255                                         (long long)dp->di_size, j, (unsigned)dp->di_ib[j]);
 256                         goto unknown;
 257                 }
 258         if (ftypeok(dp) == 0)
 259                 goto unknown;
 260         n_files++;
 261         lncntp[inumber] = dp->di_nlink;
 262         if (dp->di_nlink <= 0) {
 263                 zlnp = emalloc(sizeof *zlnp);
 264                 zlnp->zlncnt = inumber;
 265                 zlnp->next = zlnhead;
 266                 zlnhead = zlnp;
 267         }
 268         if (mode == IFDIR) {
 269                 if (dp->di_size == 0)
 270                         statemap[inumber] = DCLEAR;
 271                 else
 272                         statemap[inumber] = DSTATE;
 273                 cacheino(dp, inumber);
 274         } else
 275                 statemap[inumber] = FSTATE;
 276
 277         /*
 278          * Check for an orphaned file.  These happen when the cleaner has
 279          * to rewrite blocks from a file whose directory operation (removal)
 280          * is in progress.
 281          */
 282         if (dp->di_nlink <= 0) {
 283                 LFS_IENTRY(ifp, fs, inumber, bp);
 284                 if (ifp->if_nextfree == LFS_ORPHAN_NEXTFREE) {
 285                         statemap[inumber] = (mode == IFDIR ? DCLEAR : FCLEAR);
 286                         /* Add this to our list of orphans */
 287                         zlnp = emalloc(sizeof *zlnp);
 288                         zlnp->zlncnt = inumber;
 289                         zlnp->next = orphead;
 290                         orphead = zlnp;
 291                 }
 292                 brelse(bp, 0);
 293         }
 294
 295         typemap[inumber] = IFTODT(mode);
 296         badblk = dupblk = 0;
 297         idesc->id_number = inumber;
 298         (void) ckinode(VTOD(vp), idesc);
 299         if (dp->di_blocks != idesc->id_entryno) {
 300                 pwarn("INCORRECT BLOCK COUNT I=%llu (%d SHOULD BE %d)",
 301                     (unsigned long long)inumber, dp->di_blocks,
 302                     idesc->id_entryno);
 303                 if (preen)
 304                         printf(" (CORRECTED)\n");
 305                 else if (reply("CORRECT") == 0)
 306                         return;
 307                 VTOI(vp)->i_ffs1_blocks = idesc->id_entryno;
 308                 inodirty(VTOI(vp));
 309         }
 310         return;
 311 unknown:
 312         pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber);
 313         statemap[inumber] = FCLEAR;
 314         if (reply("CLEAR") == 1) {
 315                 statemap[inumber] = USTATE;
 316                 vp = vget(fs, inumber);
 317                 clearinode(inumber);
 318                 vnode_destroy(vp);
 319         }
 320 }
 321
 322 int
 323 pass1check(struct inodesc *idesc)
 324 {
 325         int res = KEEPON;
 326         int anyout, ndblks;
 327         daddr_t blkno = idesc->id_blkno;
 328         struct dups *dlp;
 329         struct dups *new;
 330
 331         if ((anyout = chkrange(blkno, fragstofsb(fs, idesc->id_numfrags))) != 0) {
 332                 blkerror(idesc->id_number, "BAD", blkno);
 333                 if (badblk++ >= MAXBAD) {
 334                         pwarn("EXCESSIVE BAD BLKS I=%llu",
 335                             (unsigned long long)idesc->id_number);
 336                         if (preen)
 337                                 printf(" (SKIPPING)\n");
 338                         else if (reply("CONTINUE") == 0)
 339                                 err(EEXIT, "%s", "");
 340                         return (STOP);
 341                 }
 342         } else if (!testbmap(blkno)) {
 343                 seg_table[dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * fs->lfs_fsize;
 344         }
 345         for (ndblks = fragstofsb(fs, idesc->id_numfrags); ndblks > 0; blkno++, ndblks--) {
 346                 if (anyout && chkrange(blkno, 1)) {
 347                         res = SKIP;
 348                 } else if (!testbmap(blkno)) {
 349                         n_blks++;
 350 #ifndef VERBOSE_BLOCKMAP
 351                         setbmap(blkno);
 352 #else
 353                         setbmap(blkno, idesc->id_number);
 354 #endif
 355                 } else {
 356                         blkerror(idesc->id_number, "DUP", blkno);
 357 #ifdef VERBOSE_BLOCKMAP
 358                         pwarn("(lbn %lld: Holder is %lld)\n",
 359                                 (long long)idesc->id_lblkno,
 360                                 (long long)testbmap(blkno));
 361 #endif
 362                         if (dupblk++ >= MAXDUP) {
 363                                 pwarn("EXCESSIVE DUP BLKS I=%llu",
 364                                     (unsigned long long)idesc->id_number);
 365                                 if (preen)
 366                                         printf(" (SKIPPING)\n");
 367                                 else if (reply("CONTINUE") == 0)
 368                                         err(EEXIT, "%s", "");
 369                                 return (STOP);
 370                         }
 371                         new = emalloc(sizeof(struct dups));
 372                         new->dup = blkno;
 373                         if (muldup == 0) {
 374                                 duplist = muldup = new;
 375                                 new->next = 0;
 376                         } else {
 377                                 new->next = muldup->next;
 378                                 muldup->next = new;
 379                         }
 380                         for (dlp = duplist; dlp != muldup; dlp = dlp->next)
 381                                 if (dlp->dup == blkno)
 382                                         break;
 383                         if (dlp == muldup && dlp->dup != blkno)
 384                                 muldup = new;
 385                 }
 386                 /*
 387                  * count the number of blocks found in id_entryno
 388                  */
 389                 idesc->id_entryno++;
 390         }
 391         return (res);
 392 }