1 /* $NetBSD: pass1.c,v 1.15 2003/04/02 10:39:28 fvdl 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 <sys/mount.h> 39 #include <sys/buf.h> 40 41 #include <ufs/ufs/inode.h> 42 #include <ufs/ufs/dir.h> 43 #define vnode uvnode 44 #include <ufs/lfs/lfs.h> 45 #undef vnode 46 47 #include <err.h> 48 #include <stdio.h> 49 #include <stdlib.h> 50 #include <string.h> 51 52 #include <signal.h> 53 54 #include "bufcache.h" 55 #include "vnode.h" 56 #include "lfs.h" 57 58 #include "fsck.h" 59 #include "extern.h" 60 #include "fsutil.h" 61 62 SEGUSE *seg_table; 63 extern ufs_daddr_t *din_table; 64 65 ufs_daddr_t badblk; 66 static ufs_daddr_t dupblk; 67 static int i_d_cmp(const void *, const void *); 68 69 struct ino_daddr { 70 ino_t ino; 71 ufs_daddr_t daddr; 72 }; 73 74 static int 75 i_d_cmp(const void *va, const void *vb) 76 { 77 struct ino_daddr *a, *b; 78 79 a = *((struct ino_daddr **) va); 80 b = *((struct ino_daddr **) vb); 81 82 if (a->daddr == b->daddr) { 83 return (a->ino - b->ino); 84 } 85 if (a->daddr > b->daddr) { 86 return 1; 87 } 88 return -1; 89 } 90 91 void 92 pass1() 93 { 94 ino_t inumber; 95 int i; 96 struct inodesc idesc; 97 struct ufs1_dinode *tinode; 98 struct ifile *ifp; 99 struct ubuf *bp; 100 struct ino_daddr **dins; 101 102 /* 103 * Find all allocated blocks, initialize numdirs. 104 */ 105 memset(&idesc, 0, sizeof(struct inodesc)); 106 idesc.id_type = ADDR; 107 idesc.id_func = pass1check; 108 idesc.id_lblkno = 0; 109 inumber = 0; 110 n_files = n_blks = 0; 111 112 if (debug) 113 printf("creating sorted inode address table...\n"); 114 /* Sort by daddr */ 115 dins = (struct ino_daddr **) malloc(maxino * sizeof(*dins)); 116 for (i = 0; i < maxino; i++) { 117 dins[i] = malloc(sizeof(**dins)); 118 dins[i]->ino = i; 119 if (i == fs->lfs_ifile) 120 dins[i]->daddr = fs->lfs_idaddr; 121 else { 122 LFS_IENTRY(ifp, fs, i, bp); 123 dins[i]->daddr = ifp->if_daddr; 124 brelse(bp); 125 } 126 } 127 qsort(dins, maxino, sizeof(*dins), i_d_cmp); 128 129 /* find a value for numdirs, fill in din_table */ 130 if (debug) 131 printf("counting dirs...\n"); 132 numdirs = 0; 133 for (i = 0; i < maxino; i++) { 134 inumber = dins[i]->ino; 135 if (inumber == 0 || dins[i]->daddr == 0) 136 continue; 137 tinode = ginode(inumber); 138 if (tinode && (tinode->di_mode & IFMT) == IFDIR) 139 numdirs++; 140 } 141 142 /* from setup.c */ 143 inplast = 0; 144 listmax = numdirs + 10; 145 inpsort = (struct inoinfo **) calloc((unsigned) listmax, 146 sizeof(struct inoinfo *)); 147 inphead = (struct inoinfo **) calloc((unsigned) numdirs, 148 sizeof(struct inoinfo *)); 149 if (inpsort == NULL || inphead == NULL) { 150 printf("cannot alloc %lu bytes for inphead\n", 151 (unsigned long) numdirs * sizeof(struct inoinfo *)); 152 exit(1); 153 } 154 if (debug) 155 printf("counting blocks...\n"); 156 157 for (i = 0; i < maxino; i++) { 158 inumber = dins[i]->ino; 159 if (inumber == 0 || dins[i]->daddr == 0) { 160 statemap[inumber] = USTATE; 161 continue; 162 } 163 if (dins[i]->daddr != LFS_UNUSED_DADDR) { 164 checkinode(inumber, &idesc); 165 } else { 166 statemap[inumber] = USTATE; 167 } 168 free(dins[i]); 169 } 170 free(dins); 171 } 172 173 void 174 checkinode(ino_t inumber, struct inodesc * idesc) 175 { 176 struct ufs1_dinode *dp; 177 struct uvnode *vp; 178 struct zlncnt *zlnp; 179 int ndb, j; 180 mode_t mode; 181 182 vp = vget(fs, inumber); 183 dp = VTOD(vp); 184 185 if (dp == NULL) { 186 /* pwarn("Could not find inode %ld\n",(long)inumber); */ 187 statemap[inumber] = USTATE; 188 return; 189 } 190 mode = dp->di_mode & IFMT; 191 192 /* XXX - LFS doesn't have this particular problem (?) */ 193 if (mode == 0) { 194 if (memcmp(dp->di_db, zino.di_db, NDADDR * sizeof(ufs_daddr_t)) || 195 memcmp(dp->di_ib, zino.di_ib, NIADDR * sizeof(ufs_daddr_t)) || 196 dp->di_mode || dp->di_size) { 197 pwarn("mode=o%o, ifmt=o%o\n", dp->di_mode, mode); 198 pfatal("PARTIALLY ALLOCATED INODE I=%u", inumber); 199 if (reply("CLEAR") == 1) { 200 vp = vget(fs, inumber); 201 dp = VTOD(vp); 202 clearinode(dp); 203 inodirty(VTOI(vp)); 204 } 205 } 206 statemap[inumber] = USTATE; 207 return; 208 } 209 lastino = inumber; 210 if (dp->di_size < 0 || dp->di_size + fs->lfs_bsize - 1 < dp->di_size) { 211 if (debug) 212 printf("bad size %llu:", 213 (unsigned long long) dp->di_size); 214 goto unknown; 215 } 216 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 217 vp = vget(fs, inumber); 218 dp = VTOD(vp); 219 dp->di_size = fs->lfs_fsize; 220 dp->di_mode = IFREG | 0600; 221 inodirty(VTOI(vp)); 222 } 223 ndb = howmany(dp->di_size, fs->lfs_bsize); 224 if (ndb < 0) { 225 if (debug) 226 printf("bad size %llu ndb %d:", 227 (unsigned long long) dp->di_size, ndb); 228 goto unknown; 229 } 230 if (mode == IFBLK || mode == IFCHR) 231 ndb++; 232 if (mode == IFLNK) { 233 /* 234 * Fake ndb value so direct/indirect block checks below 235 * will detect any garbage after symlink string. 236 */ 237 if (dp->di_size < fs->lfs_maxsymlinklen || 238 (fs->lfs_maxsymlinklen == 0 && dp->di_blocks == 0)) { 239 ndb = howmany(dp->di_size, sizeof(ufs_daddr_t)); 240 if (ndb > NDADDR) { 241 j = ndb - NDADDR; 242 for (ndb = 1; j > 1; j--) 243 ndb *= NINDIR(fs); 244 ndb += NDADDR; 245 } 246 } 247 } 248 for (j = ndb; j < NDADDR; j++) 249 if (dp->di_db[j] != 0) { 250 if (debug) 251 printf("bad direct addr: %d\n", dp->di_db[j]); 252 goto unknown; 253 } 254 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 255 ndb /= NINDIR(fs); 256 for (; j < NIADDR; j++) 257 if (dp->di_ib[j] != 0) { 258 if (debug) 259 printf("bad indirect addr: %d\n", 260 dp->di_ib[j]); 261 /* goto unknown; */ 262 } 263 if (ftypeok(dp) == 0) 264 goto unknown; 265 n_files++; 266 lncntp[inumber] = dp->di_nlink; 267 if (dp->di_nlink <= 0) { 268 zlnp = (struct zlncnt *) malloc(sizeof *zlnp); 269 if (zlnp == NULL) { 270 pfatal("LINK COUNT TABLE OVERFLOW"); 271 if (reply("CONTINUE") == 0) 272 err(8, "%s", ""); 273 } else { 274 zlnp->zlncnt = inumber; 275 zlnp->next = zlnhead; 276 zlnhead = zlnp; 277 } 278 } 279 if (mode == IFDIR) { 280 if (dp->di_size == 0) 281 statemap[inumber] = DCLEAR; 282 else 283 statemap[inumber] = DSTATE; 284 cacheino(dp, inumber); 285 } else 286 statemap[inumber] = FSTATE; 287 typemap[inumber] = IFTODT(mode); 288 badblk = dupblk = 0; 289 idesc->id_number = inumber; 290 (void) ckinode(VTOD(vp), idesc); 291 if (dp->di_blocks != idesc->id_entryno) { 292 pwarn("INCORRECT BLOCK COUNT I=%u (%d should be %d)", 293 inumber, dp->di_blocks, idesc->id_entryno); 294 if (preen) 295 printf(" (CORRECTED)\n"); 296 else if (reply("CORRECT") == 0) 297 return; 298 VTOI(vp)->i_ffs1_blocks = idesc->id_entryno; 299 inodirty(VTOI(vp)); 300 } 301 return; 302 unknown: 303 pfatal("UNKNOWN FILE TYPE I=%u", inumber); 304 statemap[inumber] = FCLEAR; 305 if (reply("CLEAR") == 1) { 306 statemap[inumber] = USTATE; 307 vp = vget(fs, inumber); 308 dp = VTOD(vp); 309 clearinode(dp); 310 inodirty(VTOI(vp)); 311 } 312 } 313 314 int 315 pass1check(struct inodesc *idesc) 316 { 317 int res = KEEPON; 318 int anyout, ndblks; 319 daddr_t blkno = idesc->id_blkno; 320 register struct dups *dlp; 321 struct dups *new; 322 323 if ((anyout = chkrange(blkno, fragstofsb(fs, idesc->id_numfrags))) != 0) { 324 blkerror(idesc->id_number, "BAD", blkno); 325 if (badblk++ >= MAXBAD) { 326 pwarn("EXCESSIVE BAD BLKS I=%u", 327 idesc->id_number); 328 if (preen) 329 printf(" (SKIPPING)\n"); 330 else if (reply("CONTINUE") == 0) 331 err(8, "%s", ""); 332 return (STOP); 333 } 334 } else if (!testbmap(blkno)) { 335 seg_table[dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * fs->lfs_fsize; 336 } 337 for (ndblks = fragstofsb(fs, idesc->id_numfrags); ndblks > 0; blkno++, ndblks--) { 338 if (anyout && chkrange(blkno, 1)) { 339 res = SKIP; 340 } else if (!testbmap(blkno)) { 341 n_blks++; 342 #ifndef VERBOSE_BLOCKMAP 343 setbmap(blkno); 344 #else 345 setbmap(blkno, idesc->id_number); 346 #endif 347 } else { 348 blkerror(idesc->id_number, "DUP", blkno); 349 #ifdef VERBOSE_BLOCKMAP 350 pwarn("(lbn %d: Holder is %d)\n", idesc->id_lblkno, 351 testbmap(blkno)); 352 #endif 353 if (dupblk++ >= MAXDUP) { 354 pwarn("EXCESSIVE DUP BLKS I=%u", 355 idesc->id_number); 356 if (preen) 357 printf(" (SKIPPING)\n"); 358 else if (reply("CONTINUE") == 0) 359 err(8, "%s", ""); 360 return (STOP); 361 } 362 new = (struct dups *) malloc(sizeof(struct dups)); 363 if (new == NULL) { 364 pfatal("DUP TABLE OVERFLOW."); 365 if (reply("CONTINUE") == 0) 366 err(8, "%s", ""); 367 return (STOP); 368 } 369 new->dup = blkno; 370 if (muldup == 0) { 371 duplist = muldup = new; 372 new->next = 0; 373 } else { 374 new->next = muldup->next; 375 muldup->next = new; 376 } 377 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 378 if (dlp->dup == blkno) 379 break; 380 if (dlp == muldup && dlp->dup != blkno) 381 muldup = new; 382 } 383 /* 384 * count the number of blocks found in id_entryno 385 */ 386 idesc->id_entryno++; 387 } 388 return (res); 389 } 390