1 /* $NetBSD: pass1.c,v 1.12 2001/09/25 00:03:25 wiz 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. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #include <sys/param.h> 37 #include <sys/time.h> 38 #include <ufs/ufs/dinode.h> 39 #include <ufs/ufs/dir.h> 40 #include <sys/mount.h> 41 #include <ufs/lfs/lfs.h> 42 43 #include <stdio.h> 44 #include <stdlib.h> 45 #include <string.h> 46 47 #include <signal.h> 48 49 #include "fsck.h" 50 #include "extern.h" 51 #include "fsutil.h" 52 53 SEGUSE *seg_table; 54 extern daddr_t *din_table; 55 56 static daddr_t badblk; 57 static daddr_t dupblk; 58 static void checkinode(ino_t, struct inodesc *); 59 static int i_d_cmp(const void *, const void *); 60 61 struct ino_daddr { 62 ino_t ino; 63 daddr_t daddr; 64 }; 65 66 static int 67 i_d_cmp(const void *va, const void *vb) 68 { 69 struct ino_daddr *a, *b; 70 71 a = *((struct ino_daddr **)va); 72 b = *((struct ino_daddr **)vb); 73 74 if (a->daddr == b->daddr) { 75 return (a->ino - b->ino); 76 } 77 if (a->daddr > b->daddr) { 78 return 1; 79 } 80 return -1; 81 } 82 83 void 84 pass1() 85 { 86 ino_t inumber; 87 int i; 88 struct inodesc idesc; 89 struct dinode *idinode, *tinode; 90 struct ifile *ifp; 91 CLEANERINFO *cp; 92 struct bufarea *bp; 93 struct ino_daddr **dins; 94 95 idinode = lfs_difind(&sblock, sblock.lfs_ifile, &ifblock); 96 97 /* 98 * We now have the ifile's inode block in core. Read out the 99 * number of segments. 100 */ 101 #if 1 102 if (pbp != 0) 103 pbp->b_flags &= ~B_INUSE; 104 pbp = getddblk(idinode->di_db[0], sblock.lfs_bsize); 105 106 cp = (CLEANERINFO *)(pbp->b_un.b_buf); 107 #endif 108 109 /* 110 * Find all allocated blocks, initialize numdirs. 111 */ 112 memset(&idesc, 0, sizeof(struct inodesc)); 113 idesc.id_type = ADDR; 114 idesc.id_func = pass1check; 115 idesc.id_lblkno = 0; 116 inumber = 0; 117 n_files = n_blks = 0; 118 119 if (debug) 120 printf("creating inode address table...\n"); 121 /* Sort by daddr */ 122 dins = (struct ino_daddr **)malloc(maxino * sizeof(*dins)); 123 for (i = 0; i < maxino; i++) { 124 dins[i] = malloc(sizeof(**dins)); 125 dins[i]->ino = i; 126 dins[i]->daddr = lfs_ino_daddr(i); 127 } 128 qsort(dins, maxino, sizeof(*dins), i_d_cmp); 129 130 /* find a value for numdirs, fill in din_table */ 131 if (debug) 132 printf("counting dirs...\n"); 133 numdirs = 0; 134 for (i = 0; i < maxino; i++) { 135 inumber = dins[i]->ino; 136 if (inumber == 0 || dins[i]->daddr == 0) 137 continue; 138 tinode = lfs_ginode(inumber); 139 if (tinode && (tinode->di_mode & IFMT) == IFDIR) 140 numdirs++; 141 } 142 143 /* from setup.c */ 144 inplast = 0; 145 listmax = numdirs + 10; 146 inpsort = (struct inoinfo **)calloc((unsigned) listmax, 147 sizeof(struct inoinfo *)); 148 inphead = (struct inoinfo **)calloc((unsigned) numdirs, 149 sizeof(struct inoinfo *)); 150 if (inpsort == NULL || inphead == NULL) { 151 printf("cannot alloc %lu bytes for inphead\n", 152 (unsigned long)numdirs * sizeof(struct inoinfo *)); 153 exit(1); 154 } 155 /* resetinodebuf(); */ 156 if (debug) 157 printf("counting blocks...\n"); 158 for (i = 0; i < maxino; i++) { 159 inumber = dins[i]->ino; 160 if (inumber == 0 || dins[i]->daddr == 0) { 161 statemap[inumber] = USTATE; 162 continue; 163 } 164 ifp = lfs_ientry(inumber, &bp); 165 if (ifp && ifp->if_daddr != LFS_UNUSED_DADDR) { 166 bp->b_flags &= ~B_INUSE; 167 checkinode(inumber, &idesc); 168 } else { 169 bp->b_flags &= ~B_INUSE; 170 statemap[inumber] = USTATE; 171 } 172 free(dins[i]); 173 } 174 free(dins); 175 176 /* freeinodebuf(); */ 177 } 178 179 static void 180 checkinode(ino_t inumber, struct inodesc * idesc) 181 { 182 register struct dinode *dp; 183 struct zlncnt *zlnp; 184 int ndb, j; 185 mode_t mode; 186 char *symbuf; 187 188 /* dp = getnextinode(inumber); */ 189 dp = lfs_ginode(inumber); 190 191 if (dp == NULL) { 192 /* pwarn("Could not find inode %ld\n",(long)inumber); */ 193 statemap[inumber] = USTATE; 194 return; 195 } 196 mode = dp->di_mode & IFMT; 197 198 /* XXX - LFS doesn't have this particular problem (?) */ 199 if (mode == 0) { 200 if (memcmp(dp->di_db, zino.di_db, NDADDR * sizeof(daddr_t)) || 201 memcmp(dp->di_ib, zino.di_ib, NIADDR * sizeof(daddr_t)) || 202 dp->di_mode || dp->di_size) { 203 pwarn("mode=o%o, ifmt=o%o\n", dp->di_mode, mode); 204 pfatal("PARTIALLY ALLOCATED INODE I=%u", inumber); 205 if (reply("CLEAR") == 1) { 206 dp = ginode(inumber); 207 clearinode(dp); 208 inodirty(); 209 } 210 } 211 statemap[inumber] = USTATE; 212 return; 213 } 214 lastino = inumber; 215 if ( /* dp->di_size < 0 || */ 216 dp->di_size + sblock.lfs_bsize - 1 < dp->di_size) { 217 if (debug) 218 printf("bad size %llu:", 219 (unsigned long long)dp->di_size); 220 goto unknown; 221 } 222 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 223 dp = ginode(inumber); 224 dp->di_size = sblock.lfs_fsize; 225 dp->di_mode = IFREG | 0600; 226 inodirty(); 227 } 228 ndb = howmany(dp->di_size, sblock.lfs_bsize); 229 if (ndb < 0) { 230 if (debug) 231 printf("bad size %llu ndb %d:", 232 (unsigned long long)dp->di_size, ndb); 233 goto unknown; 234 } 235 if (mode == IFBLK || mode == IFCHR) 236 ndb++; 237 if (mode == IFLNK) { 238 /* 239 * Note that the old fastlink format always had di_blocks set 240 * to 0. Other than that we no longer use the `spare' field 241 * (which is now the extended uid)for sanity checking, the 242 * new format is the same as the old. We simply ignore the 243 * conversion altogether. - mycroft, 19MAY1994 244 */ 245 if (doinglevel2 && 246 dp->di_size > 0 && dp->di_size < MAXSYMLINKLEN && 247 dp->di_blocks != 0) { 248 symbuf = alloca(secsize); 249 if (bread(fsreadfd, symbuf, 250 fsbtodb(&sblock, dp->di_db[0]), 251 (long)secsize) != 0) 252 errexit("cannot read symlink\n"); 253 if (debug) { 254 symbuf[dp->di_size] = 0; 255 printf("convert symlink %d(%s)of size %lld\n", 256 inumber, symbuf, (long long)dp->di_size); 257 } 258 dp = ginode(inumber); 259 memcpy(dp->di_shortlink, symbuf, (long)dp->di_size); 260 dp->di_blocks = 0; 261 inodirty(); 262 } 263 /* 264 * Fake ndb value so direct/indirect block checks below 265 * will detect any garbage after symlink string. 266 */ 267 if (dp->di_size < sblock.lfs_maxsymlinklen || 268 (sblock.lfs_maxsymlinklen == 0 && dp->di_blocks == 0)) { 269 ndb = howmany(dp->di_size, sizeof(daddr_t)); 270 if (ndb > NDADDR) { 271 j = ndb - NDADDR; 272 for (ndb = 1; j > 1; j--) 273 ndb *= NINDIR(&sblock); 274 ndb += NDADDR; 275 } 276 } 277 } 278 for (j = ndb; j < NDADDR; j++) 279 if (dp->di_db[j] != 0) { 280 if (debug) 281 printf("bad direct addr: %d\n", dp->di_db[j]); 282 goto unknown; 283 } 284 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 285 ndb /= NINDIR(&sblock); 286 for (; j < NIADDR; j++) 287 if (dp->di_ib[j] != 0) { 288 if (debug) 289 printf("bad indirect addr: %d\n", 290 dp->di_ib[j]); 291 /* goto unknown; */ 292 } 293 if (ftypeok(dp) == 0) 294 goto unknown; 295 n_files++; 296 lncntp[inumber] = dp->di_nlink; 297 if (dp->di_nlink <= 0) { 298 zlnp = (struct zlncnt *)malloc(sizeof *zlnp); 299 if (zlnp == NULL) { 300 pfatal("LINK COUNT TABLE OVERFLOW"); 301 if (reply("CONTINUE") == 0) 302 errexit("%s", ""); 303 } else { 304 zlnp->zlncnt = inumber; 305 zlnp->next = zlnhead; 306 zlnhead = zlnp; 307 } 308 } 309 if (mode == IFDIR) { 310 if (dp->di_size == 0) 311 statemap[inumber] = DCLEAR; 312 else 313 statemap[inumber] = DSTATE; 314 cacheino(dp, inumber); 315 } else 316 statemap[inumber] = FSTATE; 317 typemap[inumber] = IFTODT(mode); 318 #if 0 /* FFS */ 319 if (doinglevel2 && 320 (dp->di_ouid != (u_short) - 1 || dp->di_ogid != (u_short) - 1)) { 321 dp = ginode(inumber); 322 dp->di_uid = dp->di_ouid; 323 dp->di_ouid = -1; 324 dp->di_gid = dp->di_ogid; 325 dp->di_ogid = -1; 326 inodirty(); 327 } 328 #endif 329 badblk = dupblk = 0; 330 idesc->id_number = inumber; 331 (void)ckinode(dp, idesc); 332 if (dp->di_blocks != idesc->id_entryno) { 333 pwarn("INCORRECT BLOCK COUNT I=%u (%d should be %d)", 334 inumber, dp->di_blocks, idesc->id_entryno); 335 if (preen) 336 printf(" (CORRECTED)\n"); 337 else if (reply("CORRECT") == 0) 338 return; 339 dp = ginode(inumber); 340 dp->di_blocks = idesc->id_entryno; 341 inodirty(); 342 } 343 return; 344 unknown: 345 pfatal("UNKNOWN FILE TYPE I=%u", inumber); 346 statemap[inumber] = FCLEAR; 347 if (reply("CLEAR") == 1) { 348 statemap[inumber] = USTATE; 349 dp = ginode(inumber); 350 clearinode(dp); 351 inodirty(); 352 } 353 } 354 355 int 356 pass1check(struct inodesc * idesc) 357 { 358 int res = KEEPON; 359 int anyout, ndblks; 360 daddr_t blkno = idesc->id_blkno; 361 register struct dups *dlp; 362 struct dups *new; 363 364 if ((anyout = chkrange(blkno, fragstofsb(&sblock, idesc->id_numfrags))) != 0) { 365 blkerror(idesc->id_number, "BAD", blkno); 366 if (badblk++ >= MAXBAD) { 367 pwarn("EXCESSIVE BAD BLKS I=%u", 368 idesc->id_number); 369 if (preen) 370 printf(" (SKIPPING)\n"); 371 else if (reply("CONTINUE") == 0) 372 errexit("%s", ""); 373 return (STOP); 374 } 375 } else if (!testbmap(blkno)) { 376 seg_table[dtosn(&sblock, blkno)].su_nbytes += idesc->id_numfrags * sblock.lfs_fsize; 377 } 378 for (ndblks = fragstofsb(&sblock, idesc->id_numfrags); ndblks > 0; blkno++, ndblks--) { 379 if (anyout && chkrange(blkno, 1)) { 380 res = SKIP; 381 } else if (!testbmap(blkno)) { 382 n_blks++; 383 #ifndef VERBOSE_BLOCKMAP 384 setbmap(blkno); 385 #else 386 setbmap(blkno, idesc->id_number); 387 #endif 388 } else { 389 blkerror(idesc->id_number, "DUP", blkno); 390 #ifdef VERBOSE_BLOCKMAP 391 pwarn("(lbn %d: Holder is %d)\n", idesc->id_lblkno, 392 testbmap(blkno)); 393 #endif 394 if (dupblk++ >= MAXDUP) { 395 pwarn("EXCESSIVE DUP BLKS I=%u", 396 idesc->id_number); 397 if (preen) 398 printf(" (SKIPPING)\n"); 399 else if (reply("CONTINUE") == 0) 400 errexit("%s", ""); 401 return (STOP); 402 } 403 new = (struct dups *)malloc(sizeof(struct dups)); 404 if (new == NULL) { 405 pfatal("DUP TABLE OVERFLOW."); 406 if (reply("CONTINUE") == 0) 407 errexit("%s", ""); 408 return (STOP); 409 } 410 new->dup = blkno; 411 if (muldup == 0) { 412 duplist = muldup = new; 413 new->next = 0; 414 } else { 415 new->next = muldup->next; 416 muldup->next = new; 417 } 418 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 419 if (dlp->dup == blkno) 420 break; 421 if (dlp == muldup && dlp->dup != blkno) 422 muldup = new; 423 } 424 /* 425 * count the number of blocks found in id_entryno 426 */ 427 idesc->id_entryno++; 428 } 429 return (res); 430 } 431